Smart home IoT systems have become widely deployed in modern households, enabling convenient functionalities such as remote control, automation, and real-time monitoring. A commonly supported and frequently used capability in these ecosystems is device access sharing, which allows a primary device owner to grant other users permission to control or interact with a device. However, despite its security-critical nature, the security and privacy practices involved in the sharing process itself remain largely under-examined. To address this gap, we conduct a systematic study of device access sharing workflows across 56 commercially available smart home IoT devices spanning diverse vendors and product categories. Through comprehensive analysis of real-world sharing mechanisms, we identify 9 recurring classes of security and privacy risks, including coarse device access constraints, coarse sharing constraints, weak or missing sharing credentials, inability to revoke device access, inability to revoke sharing, lack of transparency regarding invitation acceptance, uncontrolled re-sharing, over-privileged access, and unintended privacy exposure. Our findings reveal widespread and systemic weaknesses in the device sharing implementations of current smart home IoT systems, underscoring that insecure sharing workflows can directly expose users to persistent security and privacy threats.

Operating a quantum network incurs high capital and operational expenditures, which are expected to be compensated by the high value of enabled quantum applications. However, existing mechanisms mainly focus on maximizing the entanglement distribution rate and neglect the cost incurred on users. This paper aims to address how to utilize quantum network resources in a cost-efficient manner while sustaining high-quantity and high-quality entanglement distribution. We first consider how to establish a steady stream of entanglements between remote nodes with the minimum cost. Utilizing a recent flow-based abstraction and a novel graph representation, we design an optimal algorithm for min-cost remote entanglement distribution. Next, we consider distributing entanglements with the highest fidelity subject to a cost bound and prove its NP-hardness. To explore the cost-fidelity trade-off due to swapping and purification, we propose an approximation scheme for maximizing fidelity while satisfying an arbitrary cost bound. Our algorithms provide rigorous tools for supporting high-performance quantum network applications with financial consideration and offer strong theoretical guarantees. Extensive simulation results validate the advantageous performance in cost efficiency and/or fidelity compared to existing solutions and heuristics.

The past decade has witnessed significant progress in next-generation wireless networks. Resilient routing is essential for maintaining reliability in mission-critical network services, particularly in dynamic and adversarial environments. Traditional traffic engineering (TE) approaches rely on pre-computed paths. Still, they face performance limitations when the number of pre-computed paths is small and scalability challenges when the number is large. This study seeks to answer the fundamental question:“How can we achieve throughput-guaranteed resilient routing under network failures without pre-computing routing paths?”We propose AEGIS, a novel throughput-guaranteed resilient routing scheme leveraging a conditional value-at-risk (CVaR) approach, which proactively guarantees the required throughput under normal conditions and enables recovery during network failures. Specifically, we propose an optimization problem that minimizes the CVaR of total throughput loss across all the failure situations while respecting user budget and network constraints. The above optimization problem is non-differentiable and non-linear; we then reformulate it as an equivalent linear program (LP) and develop an optimal solution. However, the above solution will induce cyclic flows due to resource reservation behaviors. To achieve a more resource-efficient routing, we propose a bisection approach to obtain a CVaR upper bound so that the corresponding routing is acyclic. Extensive numerical evaluations demonstrate the trade-offs among various approaches and highlight the advantages of AEGIS.

Traffic Engineering (TE) in large-scale networks like cloud Wide Area Networks (WANs) and Low Earth Orbit (LEO) satellite constellations is a critical challenge. Although learning-based approaches have been proposed to address the scalability of traditional TE algorithms, their practical application is often hindered by a lack of generalization, high training overhead, and a failure to respect link capacities. This paper proposes TELGEN, a novel TE algorithm that learns to solve TE problems efficiently in large-scale network scenarios, while achieving superior generalizability across diverse network conditions. TELGEN is based on the novel idea of transforming the problem of “predicting the optimal TE solution” into “predicting the optimal TE algorithm”, which enables TELGEN to learn and efficiently approximate the end-to-end solving process of classical optimal TE algorithms. The learned algorithm is agnostic to the exact underlying network topology or traffic patterns, and is able to very efficiently solve TE problems given arbitrary inputs and generalize well to unseen topologies and demands. We train and evaluate TELGEN with random and real-world topologies, with networks of up to 5000 nodes and 3.6×106links in testing. TELGEN shows less than 3% optimality gap while ensuring feasibility in all testing scenarios, even when the test network has 2-20× more nodes than the largest training network. It also saves up to 84% TE solving time than traditional interior-point method, and reduces up to 79.6% training time per epoch than the state-of-the-art learning-based algorithm.

Payment channel networks (PCNs) have been proposed to tackle the scalability issues in blockchains by enabling off-chain transaction settlement. However, the balance depletion problem caused by unidirectional transactions may jeopardize the payments in PCNs. Existing works address this problem by sending artificial payments to rebalance the payment channels. In this paper, we take advantage of a unique property in PCNs, where the payments of opposite directions between two users can cancel each other out, to mitigate this channel depletion problem. Specifically, we design BAR, a distributed balance-aware payment routing protocol, subject to fee-based conservation, timeliness, and feasibility constraints. Moreover, to ensure payment security, we modify the original Hashed Time-Lock Contract (HTLC) protocol to adapt it to BAR, such that BAR achieves efficiency and atomicity. Extensive simulations demonstrate that BAR outperforms the state-of-the-art algorithms Spider [1] and LND [2] in terms of success ratio and success volume.

Low Earth Orbit Satellite Networks (LSNs), as the new generation of backbone networks, can provide low-latency network connectivity anywhere on Earth. However, their dynamic topology and unpredictable global usage patterns hinder reliable communication, limiting their application in supporting real-time applications that require predictable performance. Specifically, the highly dynamic LSN may experience congestion and energy depletion due to uneven user demands and the periodic movement of satellites. In this paper, we design a Congestion and Energy-Aware pricing and resource Reservation algorithm, CEAR, which enables a LSN to reserve network resources for online arriving real-time communication requests, ensuring reliable communication to support performance-critical applications such as disaster monitoring and remote teleconferencing. To maintain the long-term performance of the network, the LSN operator sets resource prices for link bandwidth and satellite energy consumption across the network. The resource prices act as a proxy between the resource reservation decisions for each communication request and the operator’s objective to maximize throughput and network utility and/or to balance network-wide resource depletion. CEAR is guided by online competitive algorithm design and achieves a competitive social welfare. Extensive simulations using real-world LSN topology show that CEAR achieves high social welfare while maintaining low network-wide congestion and energy deficit.

Recent advances in space quantum communications envision Low Earth Orbit (LEO) satellites for global entanglement distribution. Entanglement distribution in such a network requires considerations such as satellite mobility, ground station mobility due to the Earth’s rotation, inter-satellite links, and multiple orbital shells, all of which have not been thoroughly studied in the networking literature. We ameliorate this deficit by defining a system model which accounts for all of the aforementioned factors. Using this system model, we formulate the dynamic optimal entanglement distribution (DOED) problem. We convert the DOED problem in a dynamic physical network to an instance of the problem in a static logical graph, the latter of which can be used to solve the former. We obtain a reduced logical graph from a logical graph, which can be used to reduce the complexity of solving the DOED problem. We propose two polynomial-time greedy algorithms for computing entanglement paths, as well as an integer linear programming (ILP)-based algorithm as a benchmark. We present evaluation results to demonstrate the advantages of our model and algorithms.

Payment Channel Networks (PCNs) offer an efficient off-chain alternative to the blockchain for transactions. Router nodes in PCNs facilitate transactions between non-adjacent nodes in exchange for a fee. PCN topology tends to be centralized, with a select number of routers known as hubs dominating all payment services. The fee-setting choices of hubs in order to maximize their revenue present fertile grounds for the study of PCN communications and economics. In this paper, we conduct a comprehensive analysis of the Hub Price-Setting (HPS) game. In particular, we define approximate Best Response strategies (ϵ-BR) as well as approximate Nash equilibria (ϵ-NE). We prove that for any ϵ > 0, an ϵ-BR always exists, and can be computed in polynomial time. We also prove that for some ϵ > 0, an ϵ-NE may not exist. We furthermore introduce the notion of conservative estimate and present a max-min approach to the HPS game. Extensive evaluation results demonstrate the power of our proposed approach.

As LEO/VLEO satellites offer many attractive features, such as low transmission delay, they are expected to be an integral part of 6G. Global entanglement distribution over LEO and VLEO satellite network must reckon with satellite movement over time. Current studies do not fully capture the dynamic nature of satellite constellations. We model a dynamic LEO/VLEO satellite network as a time-varying graph and construct a sequence of static graphs to represent a dynamic network. We study the entanglement distribution problem between a set of source-destination node pairs in this dynamic network utilizing Multi-commodity Flow (MCF). Solving MCF over a sequence of graphs independently for each graph may produce a completely different set of paths. Changing the set of paths every time the graph topology changes may involve a significant amount of overhead, as an established set of paths must be taken down and a new set of paths established. We propose a technique that will avoid this overhead by computing only one set of paths P to be used over all the graphs in the sequence. The degraded performance offered by$P$may be viewed as the cost of using P. The benefit of using$P$is the overhead cost of path switching that can be avoided. We provide a cost-benefit analysis in a LEO/VLEO constellation for entanglement distribution between multiple source-destination pairs. Our extensive experimentation shows that a significant amount of savings in overhead can be achieved if one is willing to accept a slightly degraded performance.

Low Earth Orbit (LEO) Earth Observation (EO) satellites have changed the way we monitor Earth. Acting like moving cameras, EO satellites are formed in constellations with different missions and priorities, and capture vast data that needs to be transmitted to the ground for processing. However, EO satellites have very limited downlink communication capability, limited by transmission bandwidth, number and location of ground stations, and small transmission windows due to highvelocity satellite movement. To optimize resource utilization, EO constellations are expected to share communication spectrum and ground stations for maximum communication efficiency. In this paper, we investigate a new attack surface exposed by resource competition in$\mathbf{E O}$constellations, targeting the delay or drop of Earth monitoring data using legitimate EO services. Specifically, an attacker can inject high-priority requests to temporarily preempt low-priority data transmission windows. Furthermore, we show that by utilizing predictable satellite dynamics, an attacker can intelligently target critical data from low-priority satellites, either delaying its delivery or irreversibly dropping the data. We formulate two attacks, the data delay attack and the data overflow attack, design algorithms to assist attackers in devising attack strategies, and analyze their feasibility or optimality in typical scenarios. We then conduct trace-driven simulations using real-world satellite images and orbit data to evaluate the success probability of launching these attacks under realistic satellite communication settings. We also discuss possible defenses against these attacks.

Payment Channel Networks (PCNs) have been proposed as a second-layer solution to the scalability issue of blockchain-based cryptocurrencies, most developed systems still lack effective strategies for further scalability solutions. Virtual payment channel (VPC) has been proposed as an off-chain technique that avoids the involvement of intermediaries for payments in a PCN. However, there is no research on how to efficiently construct VPCs while considering the characteristics of the underlying PCN. To fill this void, this paper focuses on the VPC construction in a PCN. More specifically, we propose a metric, Capacity to the Number of Intermediaries Ratio (CNIR), to consider both the capacity of the constructed VPC and the collateral locked by the involved users. We first study the VPC construction problem for a single pair of users and design an efficient algorithm that achieves the optimal CNIR. Based on this, we propose Thor, a protocol that constructs a virtual payment channel network (VPCN) for multiple pairs. Evaluation results show that Thor can efficiently construct a VPCN and outperform baseline algorithms in terms of the CNIR.

The utilization of Multi-path TCP (MPTCP) has been demonstrated to provide superior transport-layer support for data center networks (DCNs) due to its exceptional resource utilization and load-balancing capabilities. However, the substantial path diversity can make it challenging to utilize network resources to their full potential in DCNs. This paper focuses on studying the resource allocation issue of MPTCP from a resource optimization perspective. Based on theoretical analysis, we propose FMPTCP, which uses a feedback-based congestion control algorithm (FCC) and a feedback-based multi-path routing algorithm (FMP) to jointly achieve high bandwidth utilization and low round-trip time (RTT) in DCNs. The FCC algorithm utilizes probabilistic explicit congestion notification (ECN) to provide feedback on path congestion degree, and uses a gradient descent method to adjust the congestion window for optimal resource utilization and load balancing under a fixed routing topology. On the other hand, the FMP algorithm employs a hop-by-hop feedback mechanism to notify in-network congestion and path delay information, allowing for transparent multi-path routing for MPTCP flows. Our extensive simulations demonstrate that FMPTCP enables effective network resource utilization, which not only enhances overall throughput but also reduces transmission latency for DCNs.

Network administrators face the challenge of efficiently patching overwhelming volumes of vulnerabilities with limited time and resources. To address this issue, they must prioritize vulnerabilities based on the associated risk/severity measurements (i.e., CVSS). Existing solutions struggle to efficiently patch thousands of vulnerabilities on a network. This paper presents ILLATION, a proof-of-concept model that provides network-specific vulnerability risk prioritization to support efficient patching. ILLATION integrates AI techniques, such as neural networks and logical programming, to learn risk patterns from adversaries, vulnerability severity, and the network environment. It provides an integrated solution that learns and infers adversaries' motivation and ability in a network while also learning the constraints that restrict interactions between vulnerabilities and network elements. An evaluation of ILLATION against CVSS base and environmental metrics shows that it reflects changes in vulnerability scores and prioritization ranks as the same pattern as the CVSS model while identifying vulnerabilities with similar risk patterns to given adversaries better. On a simulated network with up to 10k vulnerable hosts and vulnerabilities, ILLATION can assess 1k vulnerabilities in about 4.5 minutes total, with an average running time of 0.19 seconds per vulnerability on a general-purpose computer.

The maturing blockchain technology has gradually promoted decentralized data storage from cryptocurrencies to other applications, such as trust management, resulting in new challenges based on specific scenarios. Taking the mobile trust blockchain within a vehicular network as an example, many users require the system to process massive traffic information for accurate trust assessment, preserve data reliably, and respond quickly. While existing vehicular blockchain systems ensure immutability, transparency, and traceability, they are limited in terms of scalability, performance, and security. To address these issues, this paper proposes a novel decentralized vehicle trust management solution and a well-matched blockchain framework that provides both security and performance. The paper primarily addresses two issues: i) To provide accurate trust evaluation, the trust model adopts a decentralized and peer-review-based trust computation method secured by trusted execution environments (TEEs). ii) To ensure reliable trust management, a multi-shard blockchain framework is developed with a novel hierarchical Byzantine consensus protocol, improving efficiency and security while providing high scalability and performance. The proposed scheme combines the decentralized trust model with a multi-shard blockchain, preserving trust information through a hierarchical consensus protocol. Finally, real-world experiments are conducted by developing a testbed deployed on both local and cloud servers for performance measurements.

A quantum network distributes quantum entanglements between remote nodes, and is key to many applications in secure communication, quantum sensing and distributed quantum computing. This paper explores the fundamental trade-off between the throughput and the quality of entanglement distribution in a multi-hop quantum repeater network. Compared to existing work which aims to heuristically maximize the entanglement distribution rate (EDR) and/or entanglement fidelity, our goal is to characterize the maximum achievable worst-case fidelity, while satisfying a bound on the maximum achievable expected EDR between an arbitrary pair of quantum nodes. This characterization will provide fundamental bounds on the achievable performance region of a quantum network, which can assist with the design of quantum network topology, protocols and applications. However, the task is highly non-trivial and is NP-hard as we shall prove. Our main contribution is a fully polynomial-time approximation scheme to approximate the achievable worst-case fidelity subject to a strict expected EDR bound, combining an optimal fidelity-agnostic EDR-maximizing formulation and a worst-case isotropic noise model. The EDR and fidelity guarantees can be implemented by a post-selection-and-storage protocol with quantum memories. By developing a discrete-time quantum network simulator, we conduct simulations to show the characterized performance region (the approximate Pareto frontier) of a network, and demonstrate that the designed protocol can achieve the performance region while existing protocols exhibit a substantial gap.

Scalability is a critical challenge for blockchain-based cryptocurrencies. Payment channel networks (PCNs) have emerged as a promising solution for this challenge. However, channel balance depletion can significantly limit the capacity and usability of a PCN. Specifically, frequent transactions that result in unbalanced payment flows from two ends of a channel can quickly deplete the balance on one end, thus blocking future payments from that direction. In this paper, we propose Fence, an online balance-aware fee setting algorithm to prevent channel depletion and improve PCN sustainability and long-term throughput. In our algorithm, PCN routers set transaction fees based on the current balance and level of congestion on each channel, in order to incentivize payment senders to utilize paths with more balance and less congestion. Our algorithm is guided by online competitive algorithm design, and achieves an asymptotically tight competitive ratio with constant violation in a unidirectional PCN. We further prove that no online algorithm can achieve a finite competitive ratio in a general PCN. Extensive simulations under a real-world PCN topology show that Fence achieves high throughput and keeps network channels balanced, compared to state-of-the-art PCN routing algorithms.

Edge computing promises to bring low-latency and high-throughput computing, but the limited edge resources may cause frequent congestion and lead to unstable and unpredictable performance. To ensure performance guarantee, application owners can establish Service-Level Agreements (SLAs) with the edge provider for resource reservation or priority usage. But it is cost-inefficient for application owners to lease long-term SLAs based on peak demands, as demands can fluctuate, and the leased resources may be idle or underutilized at most times. This paper studies market mechanism design for short-term edge SLA leases, focusing on real-time big data applications with throughput and latency goals. Applications submit short-term SLA requests to serve users with guaranteed performance during peak hours. As SLA requests arrive over time, the edge provider dynamically provisions edge resources to fulfill the requests, while charging application owners based on the current demands. We design EA-Market, an online combinatorial auction mechanism that achieves a competitive social welfare, while guaranteeing truthfulness, budget balance, individual rationality, and computational efficiency. Notably, our mechanism enables each application owner to bid without knowledge of the edge infrastructure, and gives edge provider full control over resource provisioning to fulfill the requests. We perform theoretical analysis and simulations to evaluate the efficacy of our mechanism.

Smart homes with various Internet of Things (IoT) devices generate a large amount of network traffic carrying rich information and play an important role in our lives. However, there is a lack of educational material with real case studies to teach undergraduate students smart home security. In this poster paper, we present a holistic curriculum design consisting of five components teaching conceptual understanding of smart home vulnerabilities, capturing and interpreting network traffic for normal and abnormal behaviors of home users and smart devices, and writing reports on smart home security analysis and defense recommendations. A case study on a known vulnerability of Ring doorbell which reveals the password of the smart home Wi-Fi during the initial setup stage is illustrated with the network topology and the captured http traffic. The project is at its initial stage of development by students in a cybersecurity concentration at a primarily undergraduate institution. Students have started collecting and analyzing smart home traffic as a project in the Wireless Network and Security class or through supervised individual undergraduate research studies.

Emerging as an alternative to cloud computing, fog computing is expected to provide low-latency, high-throughput, reliable services for ever-growing Internet of Things (IoT) applications, especially real-time applications with strict responsiveness requirements. By offloading time-critical and computation-intensive applications to proximal fog nodes (FNs), both application response time and network congestion can be markedly reduced. However, the FNs commonly suffer from limited resources compared to cloud computing nodes and, hence, may not serve all application users with guaranteed performance. The dynamic and heterogeneous nature of FNs also brings difficulty and overhead to fog computing resource management. These issues are addressed in the present study with the design of a double auction mechanism, namely, truthful auction for the fog system (TAFS), which provides incentives for FNs to satisfy as many application demands as possible with guaranteed performance. TAFS takes into account the latency tolerance of application users during the FN assignment and resource allocation to satisfy real-time requirements. We theoretically prove that TAFS satisfies several desired economic properties, including truthfulness, individual rationality, and budget balance. The performance of TAFS is evaluated through simulation experiments.

With the emergence of more and more powerful chipsets and hardware and the rise of Artificial Intelligence of Things (AIoT), there is a growing trend for bringing Deep Neural Network (DNN) models to empower mobile and edge devices with intelligence such that they can support attractive AI applications in a real-time manner. To leverage heterogeneous computational resources (such as CPU, GPU, DSP, etc.) to effectively and efficiently support the concurrent inference of multiple DNN models on a mobile or edge device, we propose a novel online Co-Scheduling framework based on deep REinforcement Learning, called COSREL. COSREL has the following desirable features: 1) it achieves significant speedup over commonly-used methods by efficiently utilizing all the computational resources on heterogeneous hardware; 2) it leverages emerging Deep Reinforcement Learning (DRL) to make dynamic and wise online scheduling decisions based on system runtime state; 3) it is capable of making a good tradeoff among inference latency, throughput, and energy efficiency; and 4) it makes no changes to given DNN models, thus preserves their accuracies. To evaluate COSREL, we conduct extensive experiments on an off-the-shelf Android smartphone. The experimental results show that COSREL consistently outperforms other baselines in terms of throughput, latency, and energy efficiency.

Multipath TCP (MPTCP) improves the bandwidth utilization in wireless network scenarios, since it can simultaneously utilize multiple interfaces for data transmission. However, with the fast growth of mobile devices and applications, link interruptions caused by handoffs still lead to drastic performance degradation in such scenarios. Typically, a series of packet losses on part of the links will block the transmission of the entire connection when handoff occurs. This paper proposes an Experience-driven Adaptive Redundant packet scheduler (EdAR) for MPTCP, aiming at achieving seamless handoffs in mobile networks. EdAR enables flexibly scheduling redundant packets with an experience-driven learning-based approach in the face of drastic network environment changes for multipath performance enhancement. To enable accurate learning and prediction, both the network environment and the best course of actions are jointly learned via a Deep Reinforcement Learning (DRL) agent, which we design with a hybrid structure to deal with the complexity of system states. Furthermore, both offline and online learning are utilized to allow the agent to adapt to different and changing network environments. Evaluation results show that EdAR outperforms the state-of-the-art MPTCP schedulers in most network scenarios. Specifically in mobile networks with frequent handoffs, EdAR brings$2\times $improvement in terms of the overall goodput.

Payment channel networks (PCNs) are proposed to improve the cryptocurrency scalability by settling off-chain transactions. However, a significant barrier is that a PCN user must solicit sufficient capital owned by the counterparty on its channel (i.e., inbound liquidity) to receive payments. To alleviate this inbound liquidity problem, Channel Liquidity Marketplaces (CLMs), e.g., Bitcoin's Lightning Pool, have been introduced, such that users can buy and sell inbound liquidity by trading crypto capital commitment in PCNs. Existing CLMs lack good incentive mechanisms that can attract more user participation. To fulfill this void, we design Cumulonimbus, an incentive mechanism for trading crypto capital commitment, which satisfies truthfulness, individual rationality, budget balance, and computational efficiency. Particularly, Cumulonimbus considers two unique features of crypto capital commitment, referred to as demand indivisibility and supply divisibility. Extensive simulations demonstrate that Cumulonimbus achieves higher satisfaction ratio, liquidity utilization, and social welfare compared with a state-of-the-art CLM mechanism Lightning Pool [18].

The ubiquitous deployment of IoT devices in smart homes has led to growing research interests in studying the home network traffic for various applications such as network measurements, device profiling, and IoT device event inference. Recent studies have shown that user activities can be inferred from a home network using extracted device event logs. However, existing solutions for user activity inference such as IoTMosaic and$\text{E2AP}$have limitations when handling ambiguities caused by device malfunctions. In this paper, we first identify the challenges faced by the existing user activity inference algorithms and the root causes of their poor performances on certain types of inputs. We then show that useful information can still be obtained even in situations where device malfunctions introduce ambiguities in user activity patterns. We achieve so by designing an extension to the existing algorithms. We also apply our extension in a digital forensics application. Our extensive experimental evaluations demonstrate that our solutions can effectively provide insights to user activity inference despite the presence of indistinguishable user activity patterns.

Recent advances in cyber-physical systems, artificial intelligence, and cloud computing have driven the wide deployment of Internet-of-things (IoT) in smart homes. As IoT devices often directly interact with the users and environments, this paper studies if and how we could explore the collective insights from multiple heterogeneous IoT devices to infer user activities for home safety monitoring and assisted living. Specifically, we develop a new system, namely IoTMosaic, to first profile diverse user activities with distinct IoT device event sequences, which are extracted from smart home network traffic based on their TCP/IP data packet signatures. Given the challenges of missing and out-of-order IoT device events due to device malfunctions or varying network and system latencies, IoTMosaic further develops simple yet effective approximate matching algorithms to identify user activities from real-world IoT network traffic. Our experimental results on thousands of user activities in the smart home environment over two months show that our proposed algorithms can infer different user activities from IoT network traffic in smart homes with the overall accuracy, precision, and recall of 0.99, 0.99, and 1.00, respectively.

The ubiquity of crowdsourcing has reshaped the static sensor-enabled data sensing paradigm with cost efficiency and flexibility. Still, most existing triangular crowdsourcing systems only work under the centralized trust assumption and suffer from various attacks mounted by malicious users. Although incorporating the emerging blockchain technology into crowdsourcing provides a possibility to mitigate some of the issues, how to concretely implement the crucial components and their functionalities in a verifiable and privacy-aware manner remains unaddressed. In this article, we present BRPC, a blockchain-based decentralized system for general crowdsourcing. BRPC integrates the confident-aware truth discovery algorithm to provide task requesters with reliable task truths while evaluating each worker’s data quality. To mitigate the biased evaluation of malicious requesters, we propose a privacy-aware verification protocol leveraging the threshold Paillier cryptosystem, with which a certain number of workers can collaboratively verify the evaluation results without knowing any sensory data. Furthermore, we define the three roles of a user and elaborate a comprehensive reputation evaluation model enforced by smart contracts for its trustworthy running. Financial and social incentives are both offered to motivate users’ honest participation. Finally, we implement a prototype of BRPC and deploy it on the Ethereum blockchain. Theoretical analyses and experiment results show its security and practicality.

The rapid and ubiquitous deployment of Internet of Things (IoT) in smart homes has created unprecedented opportunities to automatically extract environmental knowledge, awareness, and intelligence. Many existing studies have adopted either machine learning approaches or deterministic approaches to infer IoT device events and/or user activities from network traffic in smart homes. In this paper, we study the problem of inferring user activity patterns from a sequence of device events by first deterministically extracting a small number of representative user activity patterns from the sequence of device events, then applying unsupervised learning to compute an optimal subset of these user activity patterns to infer user activity patterns. Based on extensive experiments with sequences of device events triggered by 2,959 real user activities and up to 30,000 synthetic user activities, we demonstrate that our scheme is resilient to device malfunctions and transient failures/delays, and outperforms the state-of-the-art solution.

Cloud radio access networks (CRANs) have become a key enabling technique for the next generation wireless communications. Resource allocation in CRANs still needs to be further improved to reach the objective of minimizing power consumption and meeting demands of wireless users over a long period. Inspired by the success of Deep Reinforcement Learning (DRL) on solving complicated control problems, we present a novel framework,ReCARL, for power-efficient resource allocation in CRANs with deep reinforcement learning. Specifically, we define the state space, action space and reward function for the DRL agent, apply a deep neural network (DNN) to approximating the action-value function, and formally formulate the resource allocation problem (in each decision epoch) as a convex optimization problem. Under ReCARL, we propose two different DRL agents: one has a regular DNN structure trained with the basic deep Q-learning method (ReCARL-Basic); while the other has a context-aware DNN structure trained with a hybrid deep Q-learning method (ReCARL-Hybrid). We evaluated the performance of ReCARL along with the two DRL agents by comparing them with two widely-used baselines via extensive simulation. The simulation results show that ReCARL achieves significant power savings while meeting user demands, and it can well handle highly dynamic cases.

The recent spate of cyber attacks towards Internet of Things (IoT) devices in smart homes calls for effective techniques to understand, characterize, and unveil IoT device activities. In this paper, we present a new system, named IoTAthena, to unveil IoT device activities from raw network traffic consisting of timestamped IP packets. IoTAthena characterizes each IoT device activity using an activity signature consisting of an ordered sequence of IP packets with inter-packet time intervals. IoTAthena has two novel polynomial time algorithms,sigMatchandactExtract. For any given signature,sigMatchcan capture all matches of the signature in the raw network traffic. UsingsigMatchas a subfunction,actExtractcan accurately unveil the sequence of various IoT device activities from the raw network traffic. Using the network traffic of heterogeneous IoT devices collected at the router of a real-world smart home testbed and a public IoT dataset, we demonstrate that IoTAthena is able to characterize and generate activity signatures of IoT device activities and accurately unveil the sequence of IoT device activities from raw network traffic.

This paper studies how to provision edge computing and network resources for complex microservice-based applications (MSAs) in face of uncertain and dynamic geo-distributed demands. The complex inter-dependencies between distributed microservice components make load balancing for MSAs extremely challenging, and the dynamic geo-distributed demands exacerbate load imbalance and consequently congestion and performance loss. In this paper, we develop an edge resource provisioning model that accurately captures the inter-dependencies between microservices and their impact on load balancing across both computation and communication resources. We also propose a robust formulation that employs explicit risk estimation and optimization to hedge against potential worst-case load fluctuations, with controlled robustness-resource trade-off. Utilizing a data-driven approach, we provide a solution that provides risk estimation with measurement data of past load geo-distributions. Simulations with real-world datasets have validated that our solution provides the important robustness crucially needed in MSAs, and performs superiorly compared to baselines that neglect either network or inter-dependency constraints.

Payment channel networks (PCNs) are proposed to improve the cryptocurrency scalability by settling off-chain transactions. However, PCN introduces an undesirable assumption that a channel participant must stay online and be synchronized with the blockchain to defend against frauds. To alleviate this issue, watchtowers have been introduced, such that a hiring party can employ a watchtower to monitor the channel for fraud. However, a watchtower might profit from colluding with a cheating counterparty and fail to perform this job. Existing solutions either focus on heavy cryptographic techniques or require a large collateral. In this work, we leverage smart contracts through economic approaches to counter collusions for watchtowers in PCNs. This brings distrust between the watchtower and the counterparty, so that rational parties do not collude or cheat. We provide detailed analyses on the contracts and rigorously prove that the contracts are effective to counter collusions with minimal on-chain operations. In particular, a watchtower only needs to lock a small collateral, which incentivizes participation of watchtowers and users. We also provide an implementation of the contracts in Solidity and execute them on Ethereum to demonstrate the scalability and efficiency of the contracts.

While Deep Reinforcement Learning has emerged as a de facto approach to many complex experience-driven networking problems, it remains challenging to deploy DRL into real systems. Due to the random exploration or half-trained deep neural networks during the online training process, the DRL agent may make unexpected decisions, which may lead to system performance degradation or even system crash. In this paper, we propose PnP-DRL, an offline-trained, plug and play DRL solution, to leverage the batch reinforcement learning approach to learn the best control policy from pre-collected transition samples without interacting with the system. After being trained without interaction with systems, our Plug and Play DRL agent will start working seamlessly, without additional exploration or possible disruption of the running systems. We implement and evaluate our PnP-DRL solution on a prevalent experience-driven networking problem, Dynamic Adaptive Streaming over HTTP (DASH). Extensive experimental results manifest that 1) The existing batch reinforcement learning method has its limits; 2) Our approach PnP-DRL significantly outperforms classical adaptive bitrate algorithms in average user Quality of Experience (QoE); 3) PnP-DRL, unlike the state-of-the-art online DRL methods, can be off and running without learning gaps, while achieving comparable performances.

Experience-driven networking has emerged as a new and highly effective approach for resource allocation in complex communication networks. Deep Reinforcement Learning (DRL) has been shown to be a useful technique for enabling experience-driven networking. In this paper, we focus on a practical and fundamental problem for experience-driven networking: when network configurations are changed, how to train a new DRL agent to effectively and quickly adapt to the new environment. We present an Actor-Critic-based Transfer learning framework for the Traffic Engineering (TE) problem using policy distillation, which we call ACT-TE. ACT-TE effectively and quickly trains a new DRL agent to solve the TE problem in a new network environment, using both old knowledge (i.e., distilled from the existing agent) and new experience (i.e., newly collected samples). We implement ACT-TE in ns-3, and compare it with commonly-used baselines using packet-level simulations on three representative network topologies: NSFNET, ARPANET and random topology. The extensive simulation results show that 1) The existing well-trained DRL agents do not work well in new network environments; 2) ACT-TE significantly outperforms both two straightforward methods (training from scratch and fine-tuning based on an existing DRL agent) and several widely-used traditional methods in terms of network utility, throughput and delay.

Multipath TCP (MPTCP) utilizes multiple paths for simultaneous data transmission to enhance performance. However, existing MPTCP protocols are still far from satisfactory in wireless networks because of their loss-based congestion control and the difficulty of managing multiple subflows. To overcome these problems, we redesign the coupled congestion control algorithm and scheduler to boost MPTCP in wireless heterogeneous networks. The main purpose is to promote transmission rate under lossy networks, while also provide stability when networks suffer physical link changes and asymmetric links. In this paper, inspired by Bottleneck Bandwidth and Round-trip propagation time (BBR), we first propose Coupled BBR that utilizes detected bandwidth to adjust the sending rate within an MPTCP connection. Coupled BBR provides high loss tolerance as well as balanced congestion among MPTCP subflows. Then, to further improve the performance, we propose an Adaptively Redundant and Predictive packet (AR&P) scheduler to improve adaptability and keep in-order packet delivery in highly dynamic network scenarios. Based on Linux kernel implementation and experiments in both testbed and real network scenarios, we show that the proposed scheme not only provides high throughput in wireless networks, but also improves robustness and reduces out-of-order packets in some harsh circumstances.

Internet of Things (IoT) includes numerous sensing nodes that constitute a large scale-free network. Optimizing the network topology for increased resistance against malicious attacks is an NP-hard problem. Heuristic algorithms, particularly genetic algorithms, can effectively cope with such problems. However, conventional genetic algorithms are prone to falling into premature convergence owing to the lack of global search ability caused by the loss of population diversity during evolution. Although this can be alleviated by increasing population size, additional computational overhead will be incurred. Moreover, after crossover and mutation operations, individual changes in the population are mixed, and loss of optimal individuals may occur, which will slow down the evolution of the population. Therefore, we combine the population state with the evolutionary process and propose an Adaptive Robustness Evolution Algorithm (AREA) with self-competition for scale-free IoT topologies. In AREA, the crossover and mutation operations are dynamically adjusted according to population diversity to ensure global search ability. Moreover, a self-competitive mechanism is used to ensure convergence. The simulation results demonstrate that AREA is more effective in improving the robustness of scale-free IoT networks than several existing methods.

The wide deployment of IoT systems in smart homes has changed the landscape of networked systems, Internet traffic, and data communications in residential broadband networks as well as the Internet at large. However, recent spates of cyber attacks and threats towards IoT systems in smart homes have revealed prevalent vulnerabilities and risks of IoT systems ranging from data link layer protocols to application services. To address the security challenges of IoT systems in smart homes, this paper introduces IoTArgos, a multi-layer security monitoring system, which collects, analyzes, and characterizes data communications of heterogeneous IoT devices via programmable home routers. More importantly, this system extracts a variety of multi-layer data communication features and develops supervised learning methods for classifying intrusion activities at system, network, and application layers. In light of the potential zero-day or unknown attacks, IoTArgos also incorporates unsupervised learning algorithms to discover unusual or suspicious behaviors towards smart home IoT systems. Our extensive experimental evaluations have demonstrated that IoTArgos is able to detect anomalous activities targeting IoT devices in smart homes with a precision of 0.9876 and a recall of 0.9763.

Edge computing is one of the revolutionary technologies that enable high-performance and low-latency modern applications, such as smart cities, connected vehicles, etc. Yet its adoption has been limited by factors including high cost of edge resources, heterogeneous and fluctuating demands, and lack of reliability. In this paper, we study resource provisioning in edge computing, taking into account these different factors. First, based on observations from real demand traces, we propose a time-varying stochastic model to capture the time-dependent and uncertain demand and network dynamics in an edge network. We then apply a novel robustness model that accounts for both expected and worst-case performance of a service. Based on these models, we formulate edge provisioning as a multi-stage stochastic optimization problem. The problem is NP-hard even in the deterministic case. Leveraging the multi-stage structure, we apply nested Benders decomposition to solve the problem. We also describe several efficiency enhancement techniques, including a novel technique for quickly solving the large number of decomposed subproblems. Finally, we present results from real dataset-based simulations, which demonstrate the advantages of the proposed models, algorithm and techniques.

Crowdsensing enables a wide range of data collection, where the data are usually tagged with private locations. Protecting users' location privacy has been a central issue. The study of various location perturbation techniques, e.g., k-anonymity, for location privacy has received widespread attention. Despite the huge promise and considerable attention, provable good algorithms considering the tradeoff between location privacy and location information quality from the optimization perspective in crowdsensing are lacking in the literature. In this article, we study two related optimization problems from two different perspectives. The first problem is to minimize the location quality degradation caused by the protection of users' location privacy. We present an efficient optimal algorithm OLoQ for this problem. The second problem is to maximize the number of protected users, subject to a location quality degradation constraint. To satisfy the different requirements of the platform, we consider two cases for this problem: 1) overlapping and 2) nonoverlapping perturbations. For the former case, we give an efficient optimal algorithm OPUMO. For the latter case, we first prove its NP-hardness. We then design a (1-E)-approximation algorithm NPUMNand a fast and effective heuristic algorithm HPUMN. Extensive simulations demonstrate that OLoQ, OPUMO, and HPUMNsignificantly outperform an existing algorithm.

Electric vehicles can place a significant load on the power grid due to their unscheduled charging events. One way of improving power grid stability is to schedule electric vehicle charging in advance. Before a charging visit, the electric vehicle provides necessary information to request for charging at a charging station, which prepares and reserves the energy before the visit. However, the reported information can cause privacy leakage of the electric vehicle user. Anonymous information reporting can protect user privacy, but also enables attacks on the charging station by unauthorized users. An anonymous authentication system can address these issues, but cannot detect misbehaviors by authenticated users. One remedy to this is revocable anonymity-based authentication, which can revoke the anonymity of malicious users after their misbehaviors. However, we show that such a system is still vulnerable to application-level Denial of Service attacks, where a malicious user requests for large amounts of energy simultaneously from many charging stations, preventing these stations from serving other users. To address this, we improve upon an existing revocable anonymity-based authentication framework. We propose a permit-based mechanism, where each electric vehicle is only issued with one blind signature-based permit at a time. A request is valid only if it contains a valid and unused permit, which protects the system from the application-level Denial of Service attacks. Security analysis and experiments demonstrate that our framework, while ensuring user anonymity and being robust to the aforementioned attack, is also scalable and lightweight.

Recent advances in security and cryptography have enabled new paradigms for secure networking in various scenarios. The payment channel network (PCN) is a notable example, which has emerged from the combination of the traditional credit network in economics and the latest blockchain technology. PCN provides a secure and efficient way for conducting payments, by addressing both the intrinsic financial risk of the credit network and the scalability issue of the blockchain. A crucial challenge in PCN is routing, i.e., to find a set of paths that fulfill a payment request. Due to the fully distributed and dynamic nature of PCN, existing routing algorithms utilize active probing to improve routing success probability. However, while the payment itself is privacy-preserving through existing protocols, the probing process can leak sensitive information including the location of the sender or the recipient. In this paper, we address the privacy of the users in the path probing process, filling in the last piece of the privacy puzzle in PCN. We propose P4PCN, a cryptographic protocol for anonymous active probing without knowing the identities or public keys of the intermediate nodes, while hiding the locations of sender and recipient as well as any path-related information. Our protocol is lightweight and scales with the number of hops a probe explores. We confirm its performance via real-world implementation and simulation experiments.

The past decade has seen vast research on the influence maximization problem in social networks: How to select a subset of individuals to become initial adopters, so that the word-of-mouth effect in the social network is maximized Approximation algorithms have been proposed for this NP-hard problem with knapsack or other constraints. To incentivize influencers to become initial adopters, Singer has initiated budget feasible mechanisms. In this paper, we generalize them to the budget feasible mechanism for k-topic influence maximization problem. We investigate this problem and propose KIMI. We rigorously prove that KIMI achieves 5e/(e-1) approximation and computational efficiency, individual rationality, truthfulness, budget feasibility. Extensive simulations demonstrate that KIMI significantly outperforms baseline methods.

Crowdsensing enables a wide range of data collection, where the data are usually tagged with private locations. Protecting users' location privacy has been a central issue. The study of various location perturbation techniques for protecting users' location privacy has received widespread attention. Despite the huge promise and considerable attention, the location perturbation operation causes inevitable location errors, which can diminish the location quality of the crowdsensing results. Provable good algorithms that consider location quality in privacy preserving crowdsensing from optimization perspectives are still lacking in the literature. In this paper, we investigate the problem of location quality optimization in privacy preserving crowdsensing, which is to minimize the location quality desegregation, while protecting all users' location privacy. We present an optimal algorithm OLQDM for this problem. Extensive simulations demonstrate that OLQDM significantly outperforms an existing algorithm in terms of the location quality and SSE.

Pervasive mobile devices and their advances in sensing and networking have led to an emerging mobile sensing paradigm. The diversity of mobile users and the openness of sensing systems raise several crucial concerns for users' privacy, data quantity, and quality. Although different aspects of these issues were addressed separately in existing researches, there is still a need to provide a holistic solution for secure and privacy-aware mobile sensing. In this paper, we propose a privacy-aware and trustworthy mobile sensing scheme with fair incentives. Leveraging group signature, (partial) blind signature, and limited number of pseudonyms technologies, our scheme enables well-behaved users to contribute their data anonymously, and prevents both greedy and malicious users from abusing the privacy protection. Moreover, we design a fair incentive scheme to stimulate users to contribute high-quality data, based on the data quality and the reputation feedback level. Security analysis demonstrates that our proposed scheme achieves the security goals. Extensive evaluation results are presented which demonstrate the effectiveness and efficiency of our scheme.

The past several years have witnessed an explosive growth in cryptocurrencies, but the blockchain-based cryptocurrencies have also raised many concerns, among which a crucial one is the scalability issue. Suffering from the large overhead of global consensus and security assurance, even the leading cryptocurrencies can only handle up to tens of transactions per second, which largely limits their applications in real-world scenarios. Among many proposals to improve the cryptocurrency scalability, one of the most promising and mature solutions is the payment channel network (PCN), which offers the off-chain settlement of transactions with minimal involvement of expensive blockchain operations. In this paper, we investigate the problem of payment routing in PCNs from an optimization perspective, which is to minimize the transaction fee of a payment path, subject to the timeliness and feasibility constraints. We present an optimal distributed algorithm CheaPay for this problem. Extensive simulations demonstrate that CheaPay significantly outperforms baseline algorithms in terms of the success ratio and the average accepted value.

The rapid proliferation of sensor-embedded devices has enabled the mobile crowdsensing (MCS), a new paradigm which effectively collects sensing data from pervasive users. In order to identify the true information from the noisy data submitted by unreliable users, truth discovery algorithms have been proposed for the MCS systems to aggregate data. However, the power of truth discovery algorithms will be undermined by the Sybil attack, in which an attacker can benefit from using multiple accounts. In addition, an MCS system will be jeopardized unless it is resistant to the Sybil attack. In this paper, we proposed a Sybil-resistant truth discovery framework for MCS, which ensures high accuracy under the Sybil attack. To diminish the impact of the Sybil attack, we design three account grouping methods for the framework, which are used in pair with a truth discovery algorithm. We evaluate the proposed framework through a real-world experiment. The results show that existing truth discovery algorithms are vulnerable to the Sybil attack, and the proposed framework can effectively diminish the impact of the Sybil attack.

Advances in virtualization technologies and edge computing have inspired a new paradigm for Internet-of-Things (IoT) application development. By breaking a monolithic application into loosely coupled microservices, great gain can be achieved in performance, flexibility and robustness. In this paper, we study the important problem of load balancing across IoT microservice instances. A key difficulty in this problem is the interdependencies among microservices: the load on a successor microservice instance directly depends on the load distributed from its predecessor microservice instances. We propose a graph-based model for describing the load dependencies among microservices. Based on the model, we first propose a basic formulation for load balancing, which can be solved optimally in polynomial time. The basic model neglects the quality-of-service (QoS) of the IoT application. We then propose a QoS-aware load balancing model, based on a novel abstraction that captures a realization of the application's internal logic. The QoS-aware load balancing problem is NP-hard. We propose a fully polynomial-time approximation scheme for the QoS-aware problem. We show through simulation experiments that our proposed algorithm achieves enhanced QoS compared to heuristic solutions.

The last decade has witnessed research advances and wide deployment of Internet-of-things (IoT) in smart homes and connected industry. However, the recent spate of cyber attacks exploiting the vulnerabilities and insufficient security management of IoT devices have created serious challenges for securing IoT devices and applications. As a first step towards understanding and mitigating diverse security threats of IoT devices, this paper develops a measurement framework to automatically collect network traffic of IoT devices in edge networks, and build multidimensional behavioral profiles of these devices which characterize who, when, what, and why on the behavioral patterns of IoT devices based on continuously collected traffic data. To the best of our knowledge, this paper is the first effort to shed light on the IP-spatial, temporal, and cloud service patterns of IoT devices in edge networks, and to explore these multidimensional behavioral fingerprints for IoT device classification, anomaly traffic detection, and network security monitoring for millions of vulnerable and resource-constrained IoT devices on the Internet.

In this paper, we aim to study networking problems from a whole new perspective by leveraging emerging deep learning, to develop an experience-driven approach, which enables a network or a protocol to learn the best way to control itself from its own experience (e.g., runtime statistics data), just as a human learns a skill. We present design, implementation and evaluation of a deep reinforcement learning (DRL)-based control framework, DRL-CC (DRL for Congestion Control), which realizes our experience-driven design philosophy on multi-path TCP (MPTCP) congestion control. DRL-CC utilizes a single (instead of multiple independent) agent to dynamically and jointly perform congestion control for all active MPTCP flows on an end host with the objective of maximizing the overall utility. The novelty of our design is to utilize a flexible recurrent neural network, LSTM, under a DRL framework for learning a representation for all active flows and dealing with their dynamics. Moreover, we, for the first time, integrate the above LSTM-based representation network into an actor-critic framework for continuous (congestion) control, which leverages the emerging deterministic policy gradient to train critic, actor, and LSTM networks in an end-to-end manner. We implemented DRL-CC based on the MPTCP implementation in the Linux kernel. The experimental results show that 1) DRL-CC consistently and significantly outperforms a few well-known MPTCP congestion control algorithms in terms of goodput without sacrificing fairness, 2) it is flexible and robust to highly-dynamic network environments with time-varying flows, and 3) it is friendly to regular TCP.

Ubiquitous mobile devices with rich sensors and advanced communication capabilities have given rise to mobile crowdsensing systems. The diverse reliabilities of mobile users and the openness of sensing paradigms raise concerns for data trustworthiness, user privacy, and incentive provision. Instead of considering these issues as isolated modules in most existing researches, we comprehensively capture both conflict and inner-relationship among them. In this paper, we propose a holistic solution for trustworthy and privacy-aware mobile crowdsensing with no need of a trusted third party. Specifically, leveraging cryptographic technologies, we devise a series of protocols to enable benign users to request tasks, contribute their data, and earn rewards anonymously without any data linkability. Meanwhile, an anonymous trust/reputation model is seamlessly integrated into our scheme, which acts as reference for our fair incentive design, and provides evidence to detect malicious users who degrade the data trustworthiness. Particularly, we first propose the idea of limiting the number of issued pseudonyms which serves to efficiently tackle the anonymity abuse issue. Security analysis demonstrates that our proposed scheme achieves stronger security with resilience against possible collusion attacks. Extensive simulations are presented which demonstrate the efficiency and practicality of our scheme.

The Internet-of-Things (IoT) has inspired numerous new applications ever since its invention. Nevertheless, its development and utilization have always been restricted by the limited resources in various application scenarios. In this paper, we study the problem of resource provisioning for real-time IoT applications, i.e., applications that process concurrent data streams from data sources in the network. We investigate joint application placement and data routing to support IoT applications that have both quality-of-service and robustness requirements. We formulate four versions of the provisioning problem, spanning across two important classes of real-time applications (parallelizable and non-parallelizable), and two provisioning scenarios (single application and multiple applications). All versions are proved to be NP-hard. We propose fully polynomial-time approximation schemes for three of the four versions, and a randomized algorithm for the forth. Through simulation experiments, we analyze the impact of parallelizability and robustness on the provisioning performance, and show that our proposed algorithms can greatly improve the quality-of-service of the IoT applications.

The scarcity of spectrum channels resides in the limited bandwidth resource and the exploding demand from spectrum-based services and devices. To help ease this scarcity, the concept of cognitive radio networks (CRNs) is proposed, where licensed spectrum holders (primary users) may lease their channels to unlicensed users (secondary users). Many CRN auctions are thus designed to incentivize primary users (PUs) to share their idle channels with secondary users (SUs). Most of these auctions assume that a transmitting PU does not lease its channel to SUs; if it leases its channel to SUs, it does not transmit itself. To further utilize the resource, researchers have studied the scenario where a transmitting PU is allowed to lease its channels to SUs if the transmissions of the SUs do not undermine the transmission of the PU. However, the study assumes that there is only one PU who owns the licensed channels, whereas in practice, channels may be contributed by multiple PUs. This prevents the result of the study from being directly applied to the multi-PU scenario, as the potential competitions among the PUs are neglected. We extend the scenario to the CRN with multiple PUs and propose TDSA-PS as a Truthful Double Spectrum Auction with transmitting Primary users Sharing. We prove that TDSA-PS is truthful, individually rational, budget-balanced, and computationally efficient.

Although cryptocurrencies have witnessed explosive growth in the past year, they have also raised many concerns, among which a crucial one is the scalability issue of blockchain-based cryptocurrencies. Suffering from the large overhead of global consensus and security assurance, even leading cryptocurrencies can only handle up to tens of transactions per second, which largely limits their applications in real- world scenarios. Among many proposals to improve cryptocurrency scalability, one of the most promising and mature solutions is the payment channel network (PCN), which offers off-chain settlement of transactions with minimal involvement of expensive blockchain operations. In this paper, we investigate the problem of payment routing in PCN. We suggest crucial design goals in PCN routing, and propose a novel distributed dynamic routing mechanism called CoinExpress. Through extensive simulations, we have shown that our proposed mechanism is able to achieve outstanding payment acceptance ratio with low routing overhead.

Crowdsensing leverages the rapid growth of sensor-embedded smartphones and human mobility for pervasive information collection. To incentivize smartphone users to participate in crowdsensing, many auction-based incentive mechanisms have been proposed for both offline and online scenarios. It has been demonstrated that the Sybil attack may undermine these mechanisms. In a Sybil attack, a user illegitimately pretends multiple identities to gain benefits. Sybil-proof incentive mechanisms have been proposed for the offline scenario. However, the problem of designing Sybil-proof online incentive mechanisms for crowdsensing is still open. Compared to the offline scenario, the online scenario provides users one more dimension of flexibility, i.e., active time, to conduct Sybil attacks, which makes this problem more challenging. In this paper, we design Sybil-proof online incentive mechanisms to deter the Sybil attack for crowdsensing. Depending on users' flexibility on performing their tasks, we investigate both single-minded and multi-minded cases and propose SOS and SOM, respectively. SOS achieves computational efficiency, individual rationality, truthfulness, and Sybil-proofness. SOM achieves individual rationality, truthfulness, and Sybil-proofness. Through extensive simulations, we evaluate the performance of SOS and SOM.

S-The emergence of the Internet-of-Things (IoT) has inspired numerous new applications. However, due to the limited resources in current IoT infrastructures and the stringent quality-of-service requirements of the applications, providing computing and communication supports for the applications is becoming increasingly difficult. In this paper, we consider IoT applications that receive continuous data streams from multiple sources in the network, and study joint application placement and data routing to support all data streams with both bandwidth and delay guarantees. We formulate the application provisioning problem both for a single application and for multiple applications, with both cases proved to be NP-hard. For the case with a single application, we propose a fully polynomial-time approximation scheme. For the multi-application scenario, if the applications can be parallelized among multiple distributed instances, we propose a fully polynomial-time approximation scheme; for general non-parallelizable applications, we propose a randomized algorithm and analyze its performance. Simulations show that the proposed algorithms greatly improve the quality-of-service of the IoT applications compared to the heuristics.

Traditional Internet routing is simple, scalable and robust, but cannot provide perfect QoS support due to the current completely distributed hop-by-hop routing architecture. Software defined networking (SDN) opens up the door to traffic engineering innovation and makes possible QoS routing with a broader picture of overall network resources. We further argue that SDN can provide more opportunity for the network users to make their own routing selections with network programmability. In this paper, we propose OpenMCR, a general framework for network users to make their own choice of routing given various requirements. OpenMCR provides routing subject to several additive QoS constraints, which is NP-hard when the number of constraints is two or more. By composing various necessary conditions with different path extension schemes, our platform can customize routing solutions for each network user based on their own requirements. Through experiments in an SDN emulated environment, we evaluate multiple aspects of OpenMCR, demonstrate its effectiveness compared with several baselines and validate our theoretical analysis.

In online surveys, many people are reluctant to provide true answers due to privacy concerns. Thus, anonymity is important for online message collection. Existing solutions let each member blindly shuffle the submitted messages by using an IND-CCA2 secure cryptosystem. In the end, the message sender's identities are protected since no one knows the message submission order. These approaches cannot efficiently handle groups of large size.In this paper, we propose an efficient anonymous message submission protocol aimed at a practical group size. Our protocol is based on a secret sharing scheme and a symmetric key cryptosystem. We propose a novel method to aggregate members' messages into a message vector such that a group member knows only his own position in the submission sequence. The protocol is accountable for capturing malicious members breaking the protocol execution. We provide a theoretical proof showing that our protocol is anonymous under malicious attacks. We also discuss our simulation results to demonstrate the efficiency of our protocol.

How to allocate the limited wireless resource in dense radio access networks (RANs) remains challenging. By leveraging a software-defined control plane, the independent base stations (BSs) are virtualized as a centralized network controller (CNC). Such virtualization decouples the CNC from the wireless service providers (WSPs). We investigate a virtualized RAN, where the CNC auctions channels at the beginning of scheduling slots to the mobile terminals (MTs) based on bids from their subscribing WSPs. Each WSP aims at maximizing the expected long-term payoff from bidding channels to satisfy the MTs for transmitting packets. We formulate the problem as a stochastic game, where the channel auction and packet scheduling decisions of a WSP depend on the state of network and the control policies of its competitors. To approach the equilibrium solution, an abstract stochastic game is proposed with bounded regret. The decision making process of each WSP is modeled as a Markov decision process (MDP). To address the signalling overhead and computational complexity issues, we decompose the MDP into a series of single-agent MDPs with reduced state spaces, and derive an online localized algorithm to learn the state value functions. Our results show significant performance improvements in terms of per-MT average utility.

With the rapid growth of smartphones, mobile crowdsensing emerges as a new paradigm which takes advantage of the pervasive sensor-embedded smartphones to collect data efficiently. Many auction-based incentive mechanisms have been proposed to stimulate smartphone users to participate in the mobile crowdsensing applications and systems. However, none of them has taken into consideration both the bid privacy of smartphone users and the social cost. In this paper, we design two frameworks for privacypreserving auction-based incentive mechanisms that also achieve approximate social cost minimization. In the former, each user submits a bid for a set of tasks it is willing to perform; in the latter, each user submits a bid for each task in its task set. Both frameworks select users based on platform-defined score functions. As examples, we propose two score functions, linear and log functions, to realize the two frameworks. We rigorously prove that both proposed frameworks achieve computational efficiency, individual rationality, truthfulness, differential privacy, and approximate social cost minimization. In addition, with log score function, the two frameworks are asymptotically optimal in terms of the social cost. Extensive simulations evaluate the performance of the two frameworks and demonstrate that our frameworks achieve bid-privacy preservation although sacrificing social cost.

Network disaster recovery is one of the greatest concerns for Mobile Network Operators (MNOs) and first responders during large-scale natural disasters such as earth- quakes. In many recent studies, wireless multi-hop networking has been demonstrated as an effective technique to quickly and efficiently extend the network coverage during disasters. In this paper, we specifically address the network deployment problem by proposing the Population-Aware Relay Placement (PARP) solution, which seeks the efficient deployment of a limited number of relays such that population coverage is maximized in the scenario of network disaster recovery. We provide a graph-based modeling and prove its NP-hardness accordingly. In order to efficiently solve this problem, we propose a heuristic solution, which is constructed in two steps. We first design a simple algorithm based on a disk graph to determine the Steiner locations, which is the biggest challenge in this problem. Then, we formulate the problem as an integer programming problem, which is inspired by the formulation of Prize-Collecting Steiner Tree (PCST). Thus, the integer problem is solved by exploring the similarity of the existing algorithm for PCST. To evaluate the proposed solution extensively, we present numerical results on both real-world and random scenarios, which validate the effectiveness of the proposed solution and show substantial improvement by comparing to the previous one.

With the proliferation of smart mobile devices (smart phone, tablet, and wearable), mobile crowdsensing becomes a powerful sensing and computation paradigm. It has been put into application in many fields, such as spectrum sensing, environmental monitoring, healthcare, and so on. Driven by promising incentives, the power of the crowd grants crowdsensing an advantage in mobilizing users who perform sensing tasks with the embedded sensors on the smart devices. Auction is one of the commonly adopted crowdsensing incentive mechanisms to incentivize users for participation. However, it does not consider the incentive for user solicitation, where in crowdsensing, such incentive would ease the tension when there is a lack of crowdsensing users. To deal with this issue, we aim to design an auction-based incentive tree to offer rewards to users for both participation and solicitation. Meanwhile, we want the incentive mechanism to be robust against dishonest behavior such as untruthful bidding and sybil attacks, to eliminate malicious price manipulations. We design RIT as a Robust Incentive Tree mechanism for mobile crowdsensing which combines the advantages of auctions and incentive trees. We prove that RIT is truthful and sybil-proof with probability at least H, for any given H ∈ (0, 1). We also prove that RIT satisfies individual rationality, computational efficiency, and solicitation incentive. Simulation results of RIT further confirm our analysis.

An improved method for measuring and potentially monitoring surface particle size using satellite multispectral VNIR-SWIR-TIR ASTER TIR imagery was successfully tested for the Mu Us Desert to Loess Plateau region of China. The remote sensing results were validated against field sample data and published work. This work has implications for establishing a new mineral-based Earth Observation indicator for quantitative monitoring process of desertification.

Recent real-world attacks against Certification Authorities (CAs) and fraudulently issued certificates arouse the public to rethink the security of public key infrastructure for web-based connections. To distribute the trust of CAs, notaries, as an independent party, are introduced to record certificates, and a client can request an audit proof of certificates from notaries directly. However, there are two challenges. On one hand, existing works consider the security of notaries insufficiently. Due to lack of systematic mutual verification, notaries might bring safety bottlenecks. On the other hand, the service of these works is not sustainable, when any party leaks its private key or fails. In this paper, we propose a Tripartite Public Key Infrastructure (TriPKI), using Certificates Authorities, Integrity Log Servers, and Domain Name Servers, to provide a basis for establishing secure SSL/TLS connections. Specifically, we apply checks-and balances among those three parties in the structure to make them verify mutually, which avoids any single party compromise. Furthermore, we design a collaborative certificate management scheme to provide sustainable services. The security analysis and experiment results demonstrate that our scheme is suitable for practical usage with moderate overhead.

The rapid growth of sensor-embedded smartphones has led to a new data sensing and collecting paradigm, known as crowdsensing. Many auction-based incentive mechanisms have been proposed to stimulate smartphone users to participate in crowdsensing. However, none of them have taken into consideration the Sybil attack where a user illegitimately pretends multiple identities to gain benefits. This attack may undermine existing inventive mechanisms. To deter the Sybil attack, we design Sybil-proof auction-based incentive mechanisms for crowdsensing in this paper. We investigate both the single-minded and multi-minded cases and propose SPIM-S and SPIM-M, respectively. SPIM-S achieves computational efficiency, individual rationality, truthfulness, and Sybil-proofness. SPIM-M achieves individual rationality, truthfulness, and Sybil-proofness. We evaluate the performance and validate the desired properties of SPIM-S and SPIM-M through extensive simulations.

In this paper, we propose to leverage the emerging deep learning techniques for spatiotemporal modeling and prediction in cellular networks, based on big system data. First, we perform a preliminary analysis for a big dataset from China Mobile, and use traffic load as an example to show non-zero temporal autocorrelation and non-zero spatial correlation among neighboring Base Stations (BSs), which motivate us to discover both temporal and spatial dependencies in our study. Then we present a hybrid deep learning model for spatiotemporal prediction, which includes a novel autoencoder-based deep model for spatial modeling and Long Short-Term Memory units (LSTMs) for temporal modeling. The autoencoder-based model consists of a Global Stacked AutoEncoder (GSAE) and multiple Local SAEs (LSAEs), which can offer good representations for input data, reduced model size, and support for parallel and application-aware training. Moreover, we present a new algorithm for training the proposed spatial model. We conducted extensive experiments to evaluate the performance of the proposed model using the China Mobile dataset. The results show that the proposed deep model significantly improves prediction accuracy compared to two commonly used baseline methods, ARIMA and SVR. We also present some results to justify effectiveness of the autoencoder-based spatial model.

Cloud computing has emerged as a powerful and elastic platform for internet service hosting, yet it also draws concerns of the unpredictable performance of cloud-based services due to network congestion. To offer predictable performance, the virtual cluster abstraction of cloud services has been proposed, which enables allocation and performance isolation regarding both computing resources and network bandwidth in a simplified virtual network model. One issue arisen in virtual cluster allocation is the survivability of tenant services against physical failures. Existing works have studied virtual cluster backup provisioning with fixed primary embeddings, but have not considered the impact of primary embeddings on backup resource consumption. To address this issue, in this paper we study how to embed virtual clusters survivably in the cloud data center, by jointly optimizing primary and backup embeddings of the virtual clusters. We formally define the survivable virtual cluster embedding problem. We then propose a novel algorithm, which computes the most resource-efficient embedding given a tenant request. Since the optimal algorithm has high time complexity, we further propose a faster heuristic algorithm, which is several orders faster than the optimal solution, yet able to achieve similar performance. Besides theoretical analysis, we evaluate our algorithms via extensive simulations.

Crowdsensing is a sensing method which involves participants from general public to collect sensed data from their mobile devices, and also contribute and utilize a common database. To ensure a crowdsensing system to operate properly, there must be certain effective and efficient incentive mechanism to attract users and stimulate them to submit sensing data with high quality. Intuitively, the agreement on the qualities and payments in crowdsensing systems can be best modeled as a contract. However, none of existing incentive mechanisms consider data quality through effective contract design. In this paper, we design two quality-aware contract-based incentive mechanisms for crowdsensing, named QUAC-F and QUAC-I, under full information model and incomplete information model, respectively, which differ in the level of users' information known to the system. Both QUAC-F and QUAC-I are guaranteed to maximize the platform utility while satisfying individual rationality and incentive compatibility. We evaluate the performance of our designed mechanisms based on a real dataset.

Computational Drug Discovery, which uses computational techniques to facilitate and improve the drug discovery process, has aroused considerable interests in recent years. Drug Repositioning (DR) and Drug-Drug Interaction (DDI) prediction are two key problems in drug discovery and many computational techniques have been proposed for them in the last decade. Although these two problems have mostly been researched separately in the past, both DR and DDI can be formulated as the problem of detecting positive interactions between data entities (DR is between drug and disease, and DDI is between pairwise drugs). The challenge in both problems is that we can only observe a very small portion of positive interactions. In this paper, we propose a novel framework called Dyadic Positive-Unlabeled learning (DyPU) to solve the problem of detecting positive interactions. DyPU forces positive data pairs to rank higher than the average score of unlabeled data pairs. Moreover, we also derive the dual formulation of the proposed method with the rectifier scoring function and we show that the associated non-trivial proximal operator admits a closed form solution. Extensive experiments are conducted on real drug data sets and the results show that our method achieves superior performance comparing with the state-of-the-art.

The proof-of-concept software-defined radio access network (RAN) is not flexible enough due to the inherent delay and the necessity of high-capacity fronthaul links. We are hence motivated to propose a hierarchical software-defined RAN architecture, over which the base stations (BSs) are abstracted into multiple virtual local controllers while these local controllers are administered by a high-level controller. Under such a hierarchical network architecture, we particularly investigate in this paper how to adapt the BS transmit power over a long term according to the network dynamics under the constraints of mobile user queue stability and limited fronthaul capacity. We first formulate an off-line stochastic power adaptation problem. Through developing the Lyapunov method, we transform the problem into an approximate on-line optimization task. However, the challenge arises from the introduced per-cluster fronthaul capacity constraint. To solve the task efficiently and avoid extensive information exchange between the high-level controller and the local controllers, we put forward a novel low-complexity algorithm by designing a non- cooperative power adaptation game among the local controllers. Simulations are provided to evaluate the efficacy of the proposed studies.

Radio frequency identification (RFID), which promotes the rapid development of Internet of Things (IoT), has been an emerging technology and widely deployed in various applications such as warehouse management, supply chain management, and social networks. In such applications, objects can be efficiently managed by attaching them with low-cost RFID tags and carefully monitoring them. The missing objects, therefore, can be identified by the readers in the RFID system. Most of prior missing tag identification protocols consider the ideal scenario that all the tags' IDs are known to the reader, which ignore that some tags with unknown IDs, called unknown tags, may be present in the system. In this paper, we investigate the problem of efficiently identifying the missing tags with a predefined reliability for large-scale RFID systems with unknown tags. We first propose a basic efficient and reliable missing tag identification protocol called B-ERMI. Then we propose an enhanced protocol called E-ERMI to further improve the efficiency. The parameters of our proposed ERMI protocols are optimized to minimize the execution time. We also conduct extensive simulations to evaluate the proposed ERMI protocols and the simulation results illustrate that the ERMI protocols outperform other existing ones.

Multimedia communication in the Internet of Things (IoT) can potentially reach into a vast array of areas and touch people’s lives in profound and different ways. For example, real-time multimedia communication could be applied in the current U.S. 911 system to provide responders with detailed information about the nature and severity of an incident before they arrive on the scene, if the callers can transmit image and/or video of the incident site. City governments can also allow citizens to report traffic and road conditions by uploading real-time multimedia data via a specific smartphone app.

The ever-increasing mobile traffic has inspired deployment of capacity and performance enhancing network services within mobile networks. Owing to recent advances in network function virtualization, such network services can be flexibly and cost-efficiently deployed in the mobile network as software components, avoiding the need for costly hardware deployment. Nevertheless, this complicates network planning by bringing the need for service function chaining. In this paper, we study mobile network planning through a software-defined approach, considering both quality-of-service and reliability of different classes of traffic. We define and formulate the traffic steering problem for service function chaining in mobile networks, which turns out to be NP-hard. We then develop a fast approximation scheme for the problem, and evaluate its performance via extensive simulation experiments. The results show that our algorithm is near-optimal, and achieves much better performance compared with baseline algorithms.

The proliferation of crowdsourcing brings both opportunities and challenges in various fields, such as environmental monitoring, healthcare, and so on. Often, the collaborative efforts from a large crowd of users are needed in order to complete crowdsourcing jobs. In recent years, the design of crowdsourcing incentive mechanisms has drawn much interest from the research community, where auction is one of the commonly adopted mechanisms. However, few of these auctions consider the robustness against false-name attacks (a.k.a. sybil attacks), where dishonest users generate fake identities to increase their utilities without devoting more efforts. To provide countermeasures against such attacks, we have designed a Truthful Auction with countermeasures against False-name Attacks (TAFA) as an auction-based incentive mechanism for crowdsourcing. We prove that TAFA is truthful, individually rational, budget-balanced, and computationally efficient. We also prove that TAFA provides countermeasures against false-name attacks, such that each user is better off not generating any false name. Extensive performance evaluations are conducted and the results further confirm our theoretical analysis.

Secure access is one of the fundamental problems in wireless mobile networks. Digital signature is a widely used technique to protect messages' authenticity and nodes' identities. From the practical perspective, to ensure the quality of services in wireless mobile networks, ideally the process of signature verification should introduce minimum delay. Batch cryptography technique is a powerful tool to reduce verification time. However, most of the existing works focus on designing batch verification algorithms for wireless mobile networks without sufficiently considering the impact of invalid signatures, which can lead to verification failures and performance degradation. In this paper, we propose a Batch Identification Game Model (BIGM) in wireless mobile networks, enabling nodes to find invalid signatures with reasonable delay no matter whether the game scenario is complete information or incomplete information. Specifically, we analyze and prove the existence of Nash Equilibriums (NEs) in both scenarios, to select the dominant algorithm for identifying invalid signatures. To optimize the identification algorithm selection, we propose a self-adaptive auto-match protocol which estimates the strategies and states of attackers based on historical information. Comprehensive simulation results in terms of NE reasonability, algorithm selection accuracy, and identification delay are provided to demonstrate that BIGM can identify invalid signatures more efficiently than existing algorithms.

A fundamental problem in cognitive radio networks (CRN) is the following capacity maximization in CRN (CM-CRN) problem: given a set of primary links with a common transmitter, together with a set of secondary links, select a maximum cardinality subset of the links that can concurrently transmit successfully under the constraint that all primary links are selected. This problem is intrinsically different from the well-known link scheduling (LS) problem in wireless mesh networks, which does not have the constraint to select all primary links. In this paper, we make both theoretical and practical contributions to the CM-CRN problem. To achieve deep theoretical understanding of the problem, we show that CM-CRN is NP-hard and design a polynomial time approximation algorithm with a constant approximation ratio. In addition, we extend the designed algorithm to find approximate solutions to two variations of CM-CRN, one with the objective of maximizing the number of selected secondary links and the other with multiple primary users. To achieve good performance in practice, we design a simple but effective heuristic algorithm based on a greedy strategy. We also design an optimal algorithm based on integer linear programming, which serves as a benchmark for evaluating the performance of the approximation algorithm and heuristic algorithm, for problem instances of small sizes. Extensive evaluations show that our proved constant ratio of the approximation algorithm is considerably conservative and our heuristic algorithm produces results that are very close to the optimal solution. Our approximation algorithm for CM-CRN is motivated by and can be viewed as a non-trivial extension of the elegant approximation algorithm for the LS problem by Wan et al. to CRNs.

We propose a new network abstraction, termed critical network flow, which models the bandwidth requirement of modern Internet applications and services. A critical network flow defines a conventional flow in a network with explicit requirement on its aggregate bandwidth, or the flow value as commonly termed. Unlike common bandwidth-guaranteed connections whose bandwidth is only guaranteed during normal operations, a critical network flow demands strictly enforced bandwidth guarantee during various transient network states, such as network reconfiguration or network failures. Such a demand is called the bandwidth criticality of a critical network flow, which is characterized both by its flow value and capability to satisfy bandwidth guarantee in the transient states.We study algorithmic solutions to the accommodation of critical network flows with different bandwidth criticalities, including the basic case with no transient network state considered, the case with network reconfiguration, and the case with survivability against link failures. We present a polynomial-time optimal algorithm for each case. For the survivable case, we further present a faster heuristic algorithm. We have conducted extensive experiments to evaluate our model and validate our algorithms.

The survivable logical topology mapping (routing) problem in IP-over-wavelength-division multiplexing networks is to map each link in the logical topology (IP layer) onto a lightpath in the physical topology (optical layer), such that failure of a physical link does not cause the logical topology to become disconnected. In this paper, we propose a novel approach based on the concept of protecting spanning tree set of the logical topology. We present necessary and sufficient conditions based on this concept and study three optimization problems with varying degrees of difficulty. We study a generalized logical routing problem with the objective to protect the logical topology against maximal number of physical link failures. The new problem aims to find a survivable routing if one exists, or achieve maximal protection of physical link failures otherwise. We also show that the problem is equivalent to the minimum dominating set problem in bipartite graphs. We discuss how one can use the column generation technique to speed up the execution of this formulation, which obviates the need to find all spanning trees at the beginning of the execution of this formulation. In addition, we also present which has several nice features a heuristic approach, which incorporates a method to augment the logical topology with additional links to guarantee a survivable routing, which only requires a shortest path algorithm and an algorithm to generate an appropriate spanning tree. We provide the results of extensive simulations conducted to evaluate our formulations and demonstrate the effectiveness of our new approach.

In this paper, we propose to learn Lifestyles of mobile users via mobile Phone Sensing (LIPS), and we develop a system and algorithms to realize this idea. First, we present the workflow and architecture of our system, LIPS. Combining both unsupervised and supervised learning, we propose a hybrid scheme for lifestyle learning, which consists of two parts: characterization and prediction. Specifically, we present a two-stage algorithm to characterize the lifestyle of a mobile user using Places of Interest (PoIs), which leverages two different algorithms for coarse-grained and fine-grained clustering in two stages respectively. Based on discovered PoIs, we present a method to build a model to predict his/her future activities using a supervised classification algorithm. In addition, we present an adaptive sampling algorithm for improving energy efficiency, which leverages both the discovered PoIs and the lifestyle model for adaptively controlling the sampling rate. We implemented the proposed system and algorithms based on the Android platform. We have validated and evaluated LIPS via extensive field tests carried out for over 1.5 months in 6 cities of USA. The experimental results show that LIPS can 1) well discover PoIs of mobile users, 2) precisely predict their future activities, and 3) achieve significant energy savings (compared to periodic sampling).

As more and more data-intensive applications have been moved to the cloud, the cloud network has become the new performance bottleneck for cloud applications. To boost application performance, the concept of coflow has been proposed to bring application-awareness into the cloud network. A coflow consists of many individual data flows, and a coflow is completed only when all its component flows are transmitted. The network performance of a cloud application is dependent on the completion time of coflows, rather than the completion time of each individual flow. Existing coflow-aware optimization solutions employ flow preemption to reduce the completion time, which brings difficulty in practical implementation and non-negligible overhead. In this paper, we study the non-preemptive coflow scheduling and routing problem in the cloud network. We propose an offline optimization framework for coflow scheduling, as well as two subroutines for coflow routing using single-path routing and multi-path routing respectively. We also show that our proposed framework is easily extensible to the online scenario. Extensive evaluations show that the proposed solutions can greatly reduce coflow completion time compared to coflow-agnostic solutions, and are also computationally efficient.

Spectrum auctions provide a platform for licensed spectrum users to share their underutilized spectrum with unlicensed users. Existing spectrum auctions either use the protocol interference model to characterize interference relationship as binary relationship, or do not allow the primary and secondary users to share channels simultaneously. To fill this void, we design SPA, a spectrum single-sided auction under the physical interference model, which considers the interference to be accumulative. We prove that SPA is truthful, individually rational, and computationally efficient. Results from extensive simulation studies demonstrate that, SPA achieves higher spectrum utilization and buyer satisfaction ratio, compared with an existing auction adapted for the physical interference model.

The ever increasing video demands from mobile users have posed great challenges to cellular networks. To address this issue, video caching in radio access networks (RANs) has been recognized as one of the enabling technologies in future 5G mobile networks, which brings contents near the end-users, reducing the transmission cost of duplicate contents, meanwhile increasing the Quality-of-Experience (QoE) of users. Inspired by the emerging software-defined networking technology, recent proposals have employed centralized collaborative caching among cells to further increase the caching capacity of the RAN. In this paper, we explore a new dimension in video caching in software-defined RANs to expand its capacity. We enable the controller with the capability to adaptively select the bitrates of videos received by users, in order to maximize the number and quality of video requests that can be served, meanwhile minimizing the transmission cost. To achieve this, we further incorporate Scalable Video Coding (SVC), which enables caching and serving sliced video layers that can serve different bitrates. We formulate the problem of joint video caching and scheduling as a reward maximization (cost minimization) problem. Based on the formulation, we further propose a 2-stage rounding-based algorithm to address the problem efficiently. Simulation results show that using SVC with collaborative caching greatly improves the cache capacity and the QoE of users.

Limited research efforts have been made for Mobile CrowdSensing (MCS) to address quality of the recruited crowd, i.e., quality of services/data each individual mobile user and the whole crowd are potentially capable of providing, which is the main focus of the paper. Moreover, to improve flexibility and effectiveness, we consider fine-grained MCS, in which each sensing task is divided into multiple subtasks and a mobile user may make contributions to multiple subtasks. In this paper, we first introduce mathematical models for characterizing the quality of a recruited crowd for different sensing applications. Based on these models, we present a novel auction formulation for quality-aware and fine-grained MCS, which minimizes the expected expenditure subject to the quality requirement of each subtask. Then we discuss how to achieve the optimal expected expenditure, and present a practical incentive mechanism to solve the auction problem, which is shown to have the desirable properties of truthfulness, individual rationality and computational efficiency. We conducted trace-driven simulation using the mobility dataset of San Francisco taxies. Extensive simulation results show the proposed incentive mechanism achieves noticeable expenditure savings compared to two well-designed baseline methods, and moreover, it produces close-to-optimal solutions.

We investigate emerging proximity-based Mobile Crowd Service or pMCS systems, in which services are provided and consumed by users carrying smart mobile devices (e.g., smartphones) and in proximity of each other (e.g., within Bluetooth range). Due to limited resources on smartphones, it is crucial to provide a mechanism to incentivize users' participation and ensure fair trading in a pMCS system. In this paper, we design a multi-market dynamic double auction mechanism for a pMCS system, referred to as MobiAuc, and we show that it is truthful, feasible, individual-rational, no-deficit, and computationally efficient. The novelty and significance of MobiAuc is that it addresses and solves the fair trading problem in a multi-market dynamic double auction setting which naturally occurs in a mobile wireless environment. We demonstrate its efficiency via simulations based on generated user patterns (stochastic arrivals and random market clustering of users) and real-world traces. Our preliminary implementation of MobiAuc and experiments on Android platform have demonstrated the feasibility of MobiAuc mechanism in practice.

Natural disasters can result in severe damage to communication infrastructure, which leads to further chaos to the damaged area. After the disaster strikes, most of the victims would gather at the evacuation sites for food supplies and other necessities. Having a good communication network is very important to help the victims. In this paper, we aim at recovering the network from the still-alive mobile base stations to the out-of-service evacuation sites by using multi-hop relaying technique. We propose to reconstruct the post-disaster network in a capacity-aware way based on prize collecting Steiner tree. The purpose of the proposed scheme is to achieve high capacity connectivity ratio in a cost efficient way. To provide more accurate evaluation results, we evaluate the proposed scheme by using the real evacuation site and base station data in Tokyo area, and utilizing the big data analysis based post-disaster service availability model.

Dynamic Proof of Storage (PoS) is a useful cryptographic primitive that enables a user to check the integrity of outsourced files and to efficiently update the files in a cloud server. Although researchers have proposed many dynamic PoS schemes in singleuser environments, the problem in multi-user environments has not been investigated sufficiently. A practical multi-user cloud storage system needs the secure client-side cross-user deduplication technique, which allows a user to skip the uploading process and obtain the ownership of the files immediately, when other owners of the same files have uploaded them to the cloud server. To the best of our knowledge, none of the existing dynamic PoSs can support this technique. In this paper, we introduce the concept of deduplicatable dynamic proof of storage and propose an efficient construction called DeyPoS, to achieve dynamic PoS and secure cross-user deduplication, simultaneously. Considering the challenges of structure diversity and private tag generation, we exploit a novel tool called Homomorphic Authenticated Tree (HAT). We prove the security of our construction, and the theoretical analysis and experimental results show that our construction is efficient in practice.

Authenticating whether two smartphones are in close proximity is important in smartphone security. For example, the authentication result can be used to pair two devices and construct a secure communication channel between them. Many existing proximity authentication systems rely on short range networks-the communication is usually restricted in short range networks. However, this approach is inadequate when we want to verify whether the communication distance is within a few centimeters, i.e. near field. To address this challenge, many other techniques construct systems based on the near field communication (NFC) system. Unfortunately, only a small portion of smart devices in the current market are equipped with NFC chips. The purpose of this paper is to provide a close proximity authentication system which does not depend on NFC chips. We devise a system to achieve close proximity authentication by using correlated finger movements on the two smartphones. Human input usually contains errors and is of low entropy, which affects the usability and security of our system. We solve these issues in an efficient way, considering the limited computational resources on smart devices. Our system does not need any prior secret information shared between the two devices, and generates the same high-entropy cryptographic key for both devices in a successful authentication. The efficiency of the system is validated by evaluations on Motorola Droid smartphones.

Smartphones are programmable and equipped with a set of cheap but powerful embedded sensors, such as accelerometer, digital compass, gyroscope, GPS, microphone, and camera. These sensors can collectively monitor a diverse range of human activities and the surrounding environment. Crowdsensing is a new paradigm which takes advantage of the pervasive smartphones to sense, collect, and analyze data beyond the scale of what was previously possible. With the crowdsensing system, a crowdsourcer can recruit smartphone users to provide sensing service. Existing crowdsensing applications and systems lack good incentive mechanisms that can attract more user participation. To address this issue, we design incentive mechanisms for crowdsensing. We consider two system models: the crowdsourcer-centric model where the crowdsourcer provides a reward shared by participating users, and the user-centric model where users have more control over the payment they will receive. For the crowdsourcer-centric model, we design an incentive mechanism using a Stackelberg game, where the crowdsourcer is the leader while the users are the followers. We show how to compute the unique Stackelberg Equilibrium, at which the utility of the crowdsourcer is maximized, and none of the users can improve its utility by unilaterally deviating from its current strategy. For the user-centric model, we design an auction-based incentive mechanism, which is computationally efficient, individually rational, profitable, and truthful. Through extensive simulations, we evaluate the performance and validate the theoretical properties of our incentive mechanisms.

Asserting whether two devices are in close proximity is very important to many smartphone assisted security systems. For example, the smartphone based two-factor authentication usually requires the smartphone to stay in close proximity to the other device during authentication. However, relay attacks pose a serious threat to existing approaches for proximity assertions. In this paper, we present a novel near field assertion system that restricts the distance between the two devices to the scale of several centimeters. Our system explores acoustic communications and can prevent relay attacks. The generated assertion is a confidential binary sequence known only to the two devices. Our system is fully automated and light-weight, as demonstrated by extensive evaluations on a prototype.

One of the latest trends of realizing innovative Command and Control (C&C) channels involves leveraging Online Social Networks (OSNs) as a C&C channel. The number of botnets targeting the smartphones and the sophistication of those botnets have progressively increased. Due to their mobility, smartphones connect to a variety of networks which makes it harder for network centric detection of botnets in smartphones. This paper approaches the problem of detecting bot traffic from a host based detection perspective. In this paper, we first propose an innovative C&C that leverages "public information" in OSNs combined with a Username Generation Algorithm. We then propose a new system to detect the bots that leverage the above mentioned type of C&C channel. Our insight is that the user generated web traffic on the smartphones will be significantly different from the requests made by the bots that leverage OSNs as C&C channel. Our approach involves building a profile of the smartphone user based on his web usage and then comparing that profile to subsequent usage to detect anomalous behavior. The Preprocessing phase clusters the web usage based on domains and extracts relevant features. In the next step, we use classification algorithm to build the user profile and assign a score of mismatch to the domains compared to the user behavior. If the score crosses a threshold, then the traffic to that domain is perceived to be different from normal user traffic to that domain and the user will be notified. Based on his response, the model will be updated to incorporate the change into it. We implemented a prototype bot and detection system and evaluated it on real-world user traffic. Our system reports an accuracy of 76%, with false positive rate of less than 1%.

In a mobile crowd sensing system, a smartphone undertakes many different sensing tasks that demand data from various sensors. In this paper, we consider the problem of scheduling different sensing tasks assigned to a smartphone with the objective of minimizing sensing energy consumption while ensuring Quality of SenSing (QoSS). First, we consider a simple case in which each sensing task only requests data from a single sensor. We formally define the corresponding problem as the Minimum Energy Single-sensor task Scheduling (MESS) problem and present a polynomial-time optimal algorithm to solve it. Furthermore, we address a more general case in which some sensing tasks request multiple sensors to report their measurements simultaneously. We present an Integer Linear Programming (ILP) formulation as well as an effective polynomial-time heuristic algorithm, for the corresponding Minimum Energy Multi-sensor task Scheduling (MEMS) problem. Extensive simulation results show that the proposed algorithms achieve over 79% energy savings on average compared to a widely-used baseline approach, and moreover, the proposed heuristic algorithm produces close-to-optimal solutions.

Cloud computing has emerged as a prevailing platform for internet service hosting. To best utilize Cloud resources for profit making, Cloud providers rely on intelligent resource allocation algorithms when provisioning the virtualized environments for tenant service hosting. Conventional resource allocation proposals mainly focus on efficient allocation of the computing and storage resources, with little effort on ensuring the network performance of tenant services. To address this issue, a number of recent efforts abstract tenant services in the form of virtual infrastructures for resource allocation. A virtual infrastructure specifies the tenant's demand of both the computing resources for hosting virtual servers, and the network bandwidth for inter-virtual server communications. With the problem of resource allocation for virtual infrastructures being NP-hard in general networks, heuristic algorithms have been proposed for this problem. In this paper, we propose a novel optimization technique, named sequential rounding, to tackle the resource allocation problem for virtual infrastructures. The proposed technique extends the rounding technique used for the traditional virtual network embedding problem, while minimizing mapping conflicts introduced by the virtual infrastructure embed- ding problem. Experiments show that our proposed algorithm outperforms existing algorithms regarding both the acceptance ratio and average embedding cost of virtual requests.

Crowdsourcing incentive mechanism design has raised numerous interests from research communities in recent years. While most research focuses on contribution-based payment allocation, a solid crowdsourcing incentive mechanism should encourage users to both devote efforts to complete the task and refer other users to join into participation. In this paper, we adopt a data structure called incentive tree which has a unique advantage in incentivizing participants for solicitation. Furthermore, we consider the crowdsourcing scenario where the contribution model is submodular and time-sensitive, which is more realistic compared to the linear summation model adopted by previous works. Under this model, we design a reward mechanism based on the incentive tree, and prove that this mechanism satisfies several economic properties such as continuing contribution incentive, continuing solicitation incentive, θ-reward proportional to contribution, early contribution incentive, and sybil-proofness. We implemented our incentive mechanism and conducted extensive performance evaluations. The evaluation results confirm our theoretical analysis.

Auction is an effective method of allocating scarce spectrum resources in cognitive radio networks, where the primary users are sellers and the secondary users are buyers. In order for the buyers and sellers to act honestly during the auction, truthfulness has been identified as an important property. Current research focuses on the truthfulness and spatial reusability by either assuming that a conflict graph is given under the protocol model, or assuming that the grouping result is given under the physical interference model without power control. To fill this void, we design a framework of truthful double auctions, named TSA, for spectrum sharing in cognitive radio networks. TSA finds a feasible grouping profile such that users in the same group can be assigned to the same channel while each gets a satisfactory SINR value by an appropriate transmitting power allocation. We prove that TSA guarantees all the desired economic properties: individual rationality, budget-balance, computational efficiency, and truthfulness. Extensive performance evaluation also supports our theoretic analysis.

Digital signature has been widely employed in wireless mobile networks to ensure the authenticity of messages and identity of nodes. A paramount concern in signature verification is reducing the verification delay to ensure the network QoS. To address this issue, researchers have proposed the batch cryptography technology. However, most of the existing works focus on designing batch verification algorithms without sufficiently considering the impact of invalid signatures. The performance of batch verification could dramatically drop, if there are verification failures caused by invalid signatures. In this paper, we propose a Game-theory-based Batch Identification Model (GBIM) for wireless mobile networks, enabling nodes to find invalid signatures with the optimal delay under heterogeneous and dynamic attack scenarios. Specifically, we design an incomplete information game model between a verifier and its attackers, and prove the existence of Nash Equilibrium, to select the dominant algorithm for identifying invalid signatures. Moreover, we propose an auto-match protocol to optimize the identification algorithm selection, when the attack strategies can be estimated based on history information. Comprehensive simulation results demonstrate that GBIM can identify invalid signatures more efficiently than existing algorithms.

With the prosperity of smart devices, crowdsourcing has emerged as a new computing/networking paradigm. Through the crowdsourcing platform, service requesters can buy service from service providers. An important component of crowdsourcing is its incentive mechanism. We study three models of crowdsourcing, which involve cooperation and competition among the service providers. Our simplest model generalizes the well-known user-centric model studied in a recent Mobicom paper. We design an incentive mechanism for each of the three models, and prove that these incentive mechanisms are individually rational, budget-balanced, computationally efficient, and truthful.

Welcome to the 34th IEEE International Performance, Computing, and Communications Conference (IPCCC 2015) at Nanjing, China. IPCCC brings together researchers from academia, government, and industry all over the world, to exchange information about the recent research outcomes in the performance of computer and communication systems. We are very happy to see a high quality conference program, including two 2 keynote speeches, 81 papers in the main technical program, and 13 posters.

Mobile data offloading has been introduced to alleviate the congestion of cellular networks and to improve the quality of service for mobile end users. This paper presents a distributed mechanism for mobile data offloading in software defined network (SDN) at the network edge. In SDN, the data traffic of base stations (BSs) can be dynamically offloaded to access points (APs), which is enabled by the SDN controller. The SDN controller formulates a revenue maximization problem to optimize the data offloading decision, and solves the problem in a fully distributed fashion. The proposed mechanism is based on the proximal Jacobian multi-block alternating direction method of multipliers (ADMM). BSs and APs perform the offloading decision update concurrently, and are coordinated by the SDN controller through dual variables to reach a consensus on the offloading demand and supply. Numerical simulations validate the effectiveness of the proposed algorithm.

Crowdsourcing is an emerging paradigm where users can have their tasks completed by paying fees, or receive rewards for providing service. A critical problem that arises in current crowdsourcing mechanisms is how to ensure that users pay or receive what they deserve. Free-riding and false-reporting may make the system vulnerable to dishonest users. In this paper, we design schemes to tackle these problems, so that each individual in the system is better off being honest and each provider prefers completing the assigned task. We first design a mechanism EFF which eliminates dishonest behavior with the help from a trusted third party for arbitration. We then design another mechanism DFF which, without the help from any third party, discourages dishonest behavior. We also prove that DFF is semi-truthful, which discourages dishonest behavior such as free-riding and false-reporting when the rest of the individuals are honest, while guaranteeing transaction-wise budget-balance and computational efficiency. Performance evaluation shows that within our mechanisms, no user could have a utility gain by unilaterally being dishonest.

Crowdsourcing is an emerging paradigm where users can pay for the services they need or receive rewards for providing services. One example in wireless networking is mobile crowdsourcing, which leverages a cloud computing platform for recruiting mobile users to collect data (such as photos, videos, mobile user activities, etc) for applications in various domains, such as environmental monitoring, social networking, healthcare, transportation, etc. However, a critical problem arises as how to ensure that users pay or receive what they deserve. Free-riding and false-reporting may make the system vulnerable to dishonest users. In this paper, we aim to design schemes to tackle these problems, so that each individual in the system is better off being honest. We first design a mechanism EFF which eliminates dishonest behavior with the help from a trusted third party for arbitration. We then design another mechanism DFF which, without the help from any third party, discourages free-riding and false-reporting. We prove that EFF eliminates the existence of free-riding and false-reporting, while guaranteeing truthfulness, individual rationality, budget-balance, and computational efficiency. We also prove that DFF is semi-truthful, which discourages dishonest behavior such as free-riding and false-reporting when the rest of the individuals are honest, while guaranteeing budget-balance and computational efficiency. Performance evaluation shows that within our mechanisms, no dishonest behavior could bring extra benefit for each individual.

Location based service is an indispensable part of today's mobile era. While it brings a lot of benefits to people, the breach to individual location privacy is always a concern and impedes the smooth development of location based service. A user can be easily tracked once she subscribes or uses the service from an untrusted location based service server. In this paper, we try to address this problem by proposing a secure and efficient location based service system. In our system, a user does not leak any of her location information while she can still obtain the desired information associated with the location. We propose a novel method to map a user's current location to the index of the information stored in the location based service server. We demonstrated the efficiency of our system through simulations.

Recent spectrum auction results have shown that the spectrum is usually sold at a very high unit price. Small network providers may not be able to afford it individually. Inspired by the group buying service on the Internet, group buying strategy has been introduced into the design for spectrum auctions to increase the buying power of small network providers as a whole. In this paper, we consider cognitive radio networks with multiple secondary networks, each of which consists of one secondary access point and a number of secondary users interested in accessing channels licensed to the primary user. We propose TRUBA, a truthful group buying-based auction to take advantage of the collective buying power of secondary users within each secondary network. We carefully design the budget extraction for each secondary access point within the secondary network to maximize the budget collected from the secondary users. In addition, we allow the primary user to assign its channels strategically so as to maximize its profit on each secondary network. These two features together make TRUBA significantly improve the system performance, compared to the existing group buying-based auction, in terms of the number of successful transactions (up to 105% in the evaluation results), the number of winning secondary users (up to 129%), the utility of secondary access points (up to 463%), and the utility of the primary user (up to 119%).

In a competitive environment, competing agents would maximize their ideas' influence for higher profits. For example, in an unsaturated market, when a new company participates in the market sharing competition, it would distribute free tryout or discount to several customers, let them adopt the product or service, and influence others to use this product as propagation goes. This situation can also be applied to other scenarios, such as spreading new ideas in online social networks, political elections, and so on. In this paper, we use a model called Dynamic Influence in Competitive Environments (DICE) to perform the influence propagation. We first prove that finding the optimal utility for the new agent is an NP-hard problem under DICE. Then, we provide an algorithm for these new companies, and prove that the algorithm has a (1/3 - ϵ/n)-approximation ratio to the maximum payoff value. Performance results show that our algorithm has a better performance compared to existing strategies in terms of maximizing the utility for new agents.

Reminder applications are essential applications in mobile devices. Since most smart devices are equipped with accurate localization capabilities, location based reminders emerge in recent smart devices. A user could add a location based reminder which reminds the user to do something once she enters or leaves a location. Convenient as these applications are, a user can be easily tracked once she installs these applications. We propose a secure and efficient location based reminder system. In our system, the reminder location and reminder message are stored in the form of ciphertext on the cloud server. The cloud server is able to preform a private location match without knowing anything about the user's location information. We propose a novel method to represent the user's reminder area in order to save the storage space and computation time of both users and the cloud server. We demonstrate the efficiency of our system in our simulations.

Currently, a few online review and recommendation systems (such as Yelp and Trip Advisor) have attracted millions of users and are gaining increasing popularity. They usually rate and rank places and attractions based on subjective ratings provided by users. In this paper, we present design, implementation and evaluation of a mobile phone Sensing based Objective Ranking (SOR) system, which ranks a target place based on data collected via mobile phone sensing. Our system has the following desirable features: 1) it is easy to use, 2) its architecture is so scalable that various embedded and external sensors can be easily integrated into it, 3) an online scheduling algorithm is proposed and used to schedule sensing activities for coverage maximization, which has a constant approximation ratio of 1/2, 4) a personalizable ranking algorithm is developed and used to rank target places based on various sensor readings and user preferences. We validate and evaluate SOR via both field tests (using real hiking trails and coffee shops in Syracuse, NY as target places) and simulation. The field-testing results show that data collected and processed by SOR can well capture characteristics of target places, and personalizable rankings produced by SOR can well match user preferences. In addition, simulation results well justify effectiveness of the proposed scheduling algorithm.

Auctions provide a platform for licensed spectrum users to trade their underutilized spectrum with unlicensed users. Existing spectrum auctions either do not apply to the scenarios where multiple sellers and buyers both make offers, or assume the knowledge of the users' valuation distribution for maximizing the profit of the auction. To fill this void, we design PROMISE, a framework for spectrum double auctions, which jointly considers spectrum reusability, truthfulness, and profit maximization without the distribution knowledge. We propose a novel technique, called cross extraction, to compute the bid representing a group of secondary users, who can share a common channel. We prove that PROMISE is computationally efficient, individual-rational, and truthful. In addition, PROMISE is guaranteed to achieve an approximate profit of the optimal auction.

In this paper, we consider leveraging GPS-less energy-efficient sensing scheduling for mobile crowd sensing. We present a probabilistic model for sensing coverage without accurate location information (provided by GPS), based on which we formally define the Energy-constrained Maximum Coverage Sensing Scheduling (E-MCSS) problem for maximum coverage and the Fair Maximum Coverage Sensing Scheduling (F-MCSS) problem for fairness. Assuming that moving trajectories of mobile users are known beforehand, we present a (1 - 1/e)-approximation algorithm and a 1/2-approximation algorithm to solve the E-MCSS and F-MCSS problems in polynomial time, respectively, which can serve as benchmarks for performance evaluation. Under realistic assumptions, we present a GPS-less energy-efficient protocol for sensing scheduling based on the proposed algorithms. We developed an Android-based mobile crowd sensing system, on which we implemented the proposed protocol. Simulation results and experimental results (from a field test) are presented to validate and justify effectiveness of the proposed algorithms and protocol.

A fundamental problem in survivable routing in wavelength division multiplexing (WDM) optical networks is the computation of a pair of link-disjoint (or node-disjoint) lightpaths connecting a source with a destination, subject to the wavelength continuity constraint. However, this problem is NP-hard when the underlying network topology is a general mesh network. As a result, heuristic algorithms and integer linear programming (ILP) formulations for solving this problem have been proposed. In this paper, we advocate the use of 2-edge connected (or 2-node connected) subgraphs of minimum isolated failure immune networks as the underlying topology for WDM optical networks. We present a polynomial-time algorithm for computing a pair of link-disjoint lightpaths with shortest total length in such networks. The running time of our algorithm is O(nW2), where n is the number of nodes, and W is the number of wavelengths per link. Numerical results are presented to demonstrate the effectiveness and scalability of our algorithm. Extension of our algorithm to the node-disjoint case is straightforward.

In this paper, we propose a secure cloud-assisted location based reminder system. The proposed system is secure and responsive. Our system outsources the location testing task --- testing whether the current location is near a reminder location --- to the cloud server such that the device synchronization is not necessary in the system. This feature makes the proposed system more responsive, especially when the reminder message is of large size, e.g., audio, images. Above all, the proposed system protects a user's location privacy and the confidentiality of the reminder message. The system is designed in a way that the cloud server can perform location testing for a user but cannot learn about her current location, reminder locations, and reminder messages. We prove the security of the proposed system and demonstrate its efficiency using simulations on a Motorola Droid smartphone.

Many smartphone applications use near field communication (NFC) systems to guarantee that two smartphones appear in near field when interactions take place. “Google Wallet” is one such example. This kind of guarantee is called near field authentication, which is to authenticate whether two smartphones stay closely to each other. Using NFC systems is a natural option for near field authentication. However, NFC systems rely on NFC chips, which are not available on many smartphones, especially the low-end smartphones. This obstructs the popularization of NFC applications. In this paper, we propose a simple and lightweight system to perform near field authentication without using NFC chips. The idea is to put two smartphones side by side and let the user slide his finger across the two smartphone screens. The two smartphones then extract correlated feature values from the movement on each screen to authenticate each other. When the two smartphones are in near field, our system generates the same cryptographic key for both. The key can be used by another upper system to carry out confidential communications. Our system is proved to be secure in the random oracle model. We demonstrate its efficiency on Motorola Droid smartphones in our evaluations.

Near field communication (NFC) systems provide a good location-limited channel so that many security systems can use it to force the participants to stay close to each other. Unfortunately, only a small number of smart devices in the market are equipped with NFC chips that are essential for NFC systems. The purpose of this paper is to provide the same feature, called near field authentication (NFA), without using NFC chips. We propose an easy-to-use system to achieve NFA by using human finger movement on the touch screens of two nearby smart devices. Our system does not need any prior secret information shared between two devices and generates the same high-entropy cryptographic key for both devices in a successful authentication. The efficiency of the system is demonstrated by our evaluation on a Motorola Droid smartphone.

Tremendous efforts have been made to protect the location privacy of mobile users. Some of them, e.g., k-anonymity, require the participation of multiple mobile users to impede the adversary from tracing. These participating mobile users constitute an anonymity set. However, not all mobile users are seriously concerned about their location privacy. Therefore, to achieve k-anonymity, we need to provide incentives for mobile users to participate in the anonymity set. In this paper, we study the problem of incentive mechanism design for k-anonymity location privacy. We first consider the case where all mobile users have the same privacy degree requirement. We then study the case where the requirements are different. Finally, we consider a more challenging case where mobile users can cheat about not only their valuations but also their requirements. We design an auction-based incentive mechanism for each of these cases and prove that all the auctions are computational efficient, individually rational, budget-balanced, and truthful. We evaluate the performance of different auctions through extensive simulations.

In current location based social networks (LBSNs), users expose their location when they check in at a venue or search a place. The release of location privacy could lead to a severe breach of other privacy, such as identity or health condition. In this paper, we propose a framework to safeguard users' location information as well as the check-in records. Considering the special demands in LBSNs, we design a novel index structure to provide a fast search for users when they check in at the same venue frequently. At the same time, our framework outsources the heavy cryptographic computations to the server to reduce the computational overhead for mobile clients. Due to the dynamic feature of LBSNs, our framework uses a lightweight approach to handle a user's revoked friends and new friends. We prove the security of our framework in the random oracle model and demonstrate its efficiency on a Motorola Droid phone.

In this paper, we propose a service-aware approach to enhance survivability in virtualized data centers. The idea is to create and maintain a Survivable Virtual Infrastructure (SVI) for each service or tenant, which includes Virtual Machines (VMs) hosting the corresponding application and their backup VMs. A fundamental problem is to determine how to map each SVI to a data center network with minimum operational costs while satisfying each VM's resource requirements and bandwidth demands between VMs before and after failures. This problem can be naturally divided into two subproblems: VM Placement (VMP) and Virtual Link Mapping (VLM). We first present a general optimization framework. Then we propose an efficient algorithm for VMP, and a polynomial-time optimal algorithm for VLM, which can be used as subroutines in the framework. We also present an effective heuristic algorithm that jointly solves two subproblems. It has been shown by extensive simulation results based on the real VM workload traces collected from Syracuse University's green data center that compared to the First Fit Decreasing (FFD) and shortest path routing based baseline algorithm, the proposed algorithms significantly reduce the reserved bandwidth, and yield comparable results in terms of the number of active servers. \begin{keywords}Cloud Computing, Data Center, Service-aware, Survivability, Virtual Machine Management. \end{keywords}

Anypath routing has been proposed to improve the performance of unreliable wireless networks by exploiting the spatial diversity and broadcast nature of the wireless medium. Previous studies on anypath routing have concentrated on finding an anypath, which optimizes a single quality of service (QoS) parameter. In this paper, we study anypath routing subject to multiple constraints. We first prove that the problem is NP-hard when the number of constraints is larger than one. We then present a polynomial time K--approximation algorithm MAP, where K is the number of constraints. Our algorithm is as simple as Dijkstra's shortest path algorithm. Therefore, it is suitable for implementation in wireless routing protocols.

In this paper, we present a game-theoretic study of the problem of routing in networks with max-min fair congestion control at the link level. The problem is formulated as a noncooperative game, in which each user aims to maximize its own bandwidth by selecting its routing path. We first prove the existence of Nash equilibria. This is important, because at a Nash equilibrium (NE), no user has any incentive to change its routing strategy-leading to a stable state. In addition, we investigate how the selfish behavior of users may affect the performance of the network as a whole. We next introduce a novel concept of observed available bandwidth on each link. It allows a user to find a path with maximum bandwidth under max-min fair congestion control in polynomial time, when paths of other users are fixed. We then present a game-based algorithm to compute an NE and prove that by following the natural game course, the network converges to an NE. Extensive simulations show that the algorithm converges to an NE within 10 iterations and also achieves better fairness compared to other algorithms .

Jamming defense is an important yet challenging problem. In this paper, we study the jamming defense problem in the presence of a smart jammer, who can quickly learn the transmission power of the user and adaptively adjust its transmission power to maximize the damaging effect. We consider both the single-channel model and the multi-channel model. By modeling the problem as a Stackelberg game, we compute the optimal transmission power for the user to maximize its utility, in the presence of a smart jammer. For the single-channel model, we prove the existence and uniqueness of the Stackelberg Equilibrium (SE) by giving closed-form expressions for the SE strategies of both the user and the player. For the multi-channel model, we prove the existence of the SE. We design algorithms for computing the jammer's best response strategy and approximating the user's optimal strategy. Finally, we validate our theoretical analysis through extensive simulations.

In a virtualized data center, survivability can be enhanced by creating redundant Virtual Machines (VMs) as backup for VMs such that after VM or server failures, affected services can be quickly switched over to backup VMs. To enable flexible and efficient resource management, we propose to use a service-aware approach in which multiple correlated VMs and their backups are grouped together to form a Survivable Virtual Infrastructure (SVI) for a service or a tenant. A fundamental problem in such a system is to determine how to map each SVI to a physical data center network such that operational costs are minimized subject to the constraints that each VM's resource requirements are met and bandwidth demands between VMs can be guaranteed before and after failures. This problem can be naturally divided into two sub-problems: VM Placement(VMP) and Virtual Link Mapping (VLM). We present a general optimization framework for this mapping problem. Then we present an efficient algorithm for the VMP sub problem as well as a polynomial-time algorithm that optimally solves the VLM sub problem, which can be used as subroutines in the framework. We also present an effective heuristic algorithm that jointly solves the two sub problems. It has been shown by extensive simulation results based on the real VM data traces collected from the green data center at Syracuse University that compared with the First Fit Descending (FFD) and single shortest path based baseline algorithm, both our VMP+VLM algorithm and joint algorithm significantly reduce the reserved bandwidth, and yield comparable results in terms of the number of active servers.

Recent success of online social networks (OSNs) motivates the study of security issues in OSNs. A fundamental but challenging security issue in OSNs is to authenticate a friend's real identity. A solution to this issue will benefit a number of OSN security protocols. Existing solutions require users securely obtain some secret information from their friends before authentication takes place, which is not always possible in OSNs. In this paper, we propose a new authenticated key exchange protocol based on the exclusive secrets shared between friends. It provides identity authentication and key exchange in a plain setting, i.e., users do not need to securely exchange or distribute any information beforehand. The protocol is designed to work with low-entropy input information, because human beings are not good at dealing with a large amount of information. Another advantage of our protocol is its tolerance of input errors considering human error is always a possibility. We prove the security of the protocol in the universal composability (UC) framework and demonstrate its efficiency.

In this paper, we construct a system which can hide users' identity when they visit untrusted third party storage sites. We also define a fine-grained access control policy for the data owner to freely define who can access the record. That is to say, the data owner divide his friends into several groups and issues them corresponding credentials for accessing his data. However, he can adds a friend at any time in a revocation list (RL) so that that friend could not access the data owner's data any more even if he has credentials. We theoretically prove the security of our protocols, and evaluate the performance of our protocols through simulations.

Authenticating users in online social networks (OSNs) is different from traditional authentication, because the participants in the authentication may not share any prior secret information. In this paper, we propose a decentralized authentication framework to help users authenticate unknown users in an OSN. In our framework, a user requests certificates from other trusted users to prove his identity in authentication. However, collecting certificates is constrained by the fact that trust is usually attritted with the length of a trust chain. Considering this constraint, our framework utilizes a decentralized online learning approach to help users collect more certificates. We further prove that the number of the collected certificates by each user using our protocols is close to optimum.

Jamming defense is an important yet challenging problem. In this paper, we study the jamming defense problem in the presence of a smart jammer, who can quickly learn the transmission power of the user and adaptively adjust its transmission power to maximize the damaging effect. By modeling the problem as a Stackelberg game, we compute the optimal transmission power for the user to maximize its utility, in spite of the existence of the smart jammer. We prove that the smart jammer is not more damaging than a jammer without the intelligence, provided that the user plays its strategy corresponding to a Stackelberg equilibrium. This nice property is due to the user's ability to predict the jammer's behavior.

Auction theory has been applied to cooperative communications to either efficiently allocate resources or incentivize wireless devices to participate in cooperative communications. However, a common shortcoming of the existing studies is that the revenue generation is neglected. Revenue generation is the ultimate goal of commercial networks, e.g., WiMAX networks. In this paper, we study the problem of how to use auction mechanisms to allocate the relay nodes and charge the source nodes, such that the revenue of the seller, e.g., the base station, is maximized. We first propose a VCG-based auction mechanism, which can maximize the revenue while enforcing the truthfulness. To overcome the high time complexity of the VCG-based auction mechanism, we further design another truthful auction mechanism with low time complexity. Experiment results show that the suboptimal auction mechanism significantly reduces the time complexity without severely sacrificing the revenue.

Group ranking is a necessary process used to find the best participant from a group. Group ranking has many applications, including online marketing, personal interests matching and proposal ranking. In an online virtual environment, participants want to do group ranking without leaking any of their private information. In this work, we generalize this scenario as a privacy preserving group ranking problem and formulate the privacy requirements of this problem. We propose a fully distributed privacy preserving group ranking framework and prove its security in the honest but curious model. The core of our framework is a novel multiparty sorting protocol, which guarantees that an adversary cannot link the private information to its owner's identity as long as the owner's final ranking is hidden from the adversary. Our protocol is efficient in computational overhead and communication rounds compared to existing works, as demonstrated by our analysis and simulation.

Reliability and energy efficiency are critical issues in wireless sensor networks. In this work, we study Delay-bounded Energy-constrained Adaptive Routing (DEAR) problem with reliability, differential delay, and transmission energy consumption constraints in wireless sensor networks. We aim to route the connections in a manner such that link failure does not shut down the entire stream but allows a continuing flow for a significant portion of the traffic along multiple paths. This flexibility enabled by a multi-path routing scheme has the tradeoff of differential delay among the different paths. This requires increased memory in the base station to buffer the traffic until the data arrives on all the paths. Therefore, differential delay between the multiple paths should be bounded in a range to reduce additional hardware cost in the base station. Moreover, the energy consumption constraint should also be satisfied when transmitting packets among multiple paths. We present a pseudo-polynomial time solution to solve a special case of DEAR, representing edge delays as integers. Next, an (1+α)-approximation algorithm is proposed to solve the optimization version of the DEAR problem. An efficient heuristic is provided for the DEAR problem. We present numerical results confirming the advantage of our schemes as the first solution for the DEAR problem.

Surveillance systems, such as sensor networks and surveillance camera networks, have been widely deployed to monitor events in many different scenarios. One common way to conserve resource (such as energy) usage is to have only a subset of devices activated at any give time. In this paper, we look at this classic problem from a new perspective: we do not try to cover all the event areas as usually studied, but aim to find the most valuable event areas among all the event areas (i.e., the ones leading to the most utility) to monitor, subject to resource constraints. This problem poses two major challenges. First, the utility brought by monitoring an event area is not known beforehand. Second, even if this information is known in advance, solving the problem of which event areas should be monitored to maximize the total utility, subject to resource constraints, is NP-hard. We formulate this problem as a novel programming system, called online integer linear programming, and present a polynomial time algorithm to solve this problem. For any given σ∈(0, 1), we prove a bound on the gap between the expected utility obtained by constantly using the global optimal strategy multiplied by σ and the expected utility obtained by following our algorithm.

In this paper, we study the influence of network entity load constraints on network resource allocation. We focus on the problem of allocating network resources to optimize the total utility of multiple users in a wireless network, taking into account four resource and social requirements: 1) user QoS rate constraints, 2) node max load constraints, 3) node load balance constraints, and 4) node-user load constraints. We formulate this problem as a programming system. In order to solve this programming system, we first propose an optimization framework, called α-approximation dual subgradient algorithm, which may be applicable for many networking optimization problems. Given an approximation/optimal algorithm for solving the subproblem at each iteration, the framework leads to a result that can provide the following bounds at each iteration: 1) the bounds on the Lagrangian multipliers; 2) the bound on the amount of feasibility violation of the generated primal solutions; and 3) the upper and lower bounds on the gap between the optimal solution and the generated primal solutions. Based on this framework, we then present a distributed iterative algorithm to solve the network resource allocation problem. At each iteration, we provide bounds on the amount of feasibility violation, the gap between our solution and the optimal solution, node queue lengths, user utility deficits, and node load violation ratios.

While tremendous efforts have been made on channel allocation problems in wireless networks, most of them are on cooperative networks with few exceptions [6, 8, 31, 32]. Among those works on non-cooperative networks, none of them considers the network with multiple collision domains. Instead, they all assume the single collision domain, where all transmissions interfere with each other if they are on the same channel. In this paper, we fill this void and generalize the channel allocation problem to non-cooperative multi-radio multi-channel wireless networks with multiple collision domains. We formulate the problem as a strategic game, called ChAlloc. We show that the ChAlloc game may result in an oscillation when there are no exogenous factors to influence players' strategies. To avoid this possible oscillation, we design a charging scheme to induce players to converge to a Nash Equilibrium (NE). We bound the convergence speed and prove that the system performance in an NE is at least (1 - r̅/h) of the system performance in an optimal solution, where r̅ is the maximum number of radios equipped on wireless devices and h is the number of available channels. In addition, we develop a localized algorithm for players to find an NE strategy. Finally, we evaluate our design through extensive experiments. The results validate our analysis of the possible oscillation in the ChAlloc game lacking the charging scheme, confirm the convergence of the ChAlloc game with the charging scheme, and verify our proof on the system performance compared to the upper bounds returned by an LP-based algorithm.

In online surveys, many people are not willing to provide true answers due to privacy concerns. Thus, anonymity is important for online message collection. Existing solutions let each member blindly shuffle the submitted messages by using the IND-CCA2 secure cryptosystem. In the end, all messages are randomly shuffled and no one knows the message order. However, the heavy computational overhead and linear communication rounds make it only useful for small groups. In this paper, we propose an efficient anonymous message submission protocol aimed at a practical group size. Our protocol is based on a simplified secret sharing scheme and a symmetric key cryptosystem. We propose a novel method to let all members secretly aggregate their messages into a message vector such that a member knows nothing about other members' message positions.We provide a theoretical proof showing that our protocol is anonymous under malicious attacks. We then conduct a thorough analysis of our protocol, showing that our protocol is computationally more efficient than existing solutions and results in a constant communication rounds with a high probability.

Mobile phone sensing is a new paradigm which takes advantage of the pervasive smartphones to collect and analyze data beyond the scale of what was previously possible. In a mobile phone sensing system, the platform recruits smartphone users to provide sensing service. Existing mobile phone sensing applications and systems lack good incentive mechanisms that can attract more user participation. To address this issue, we design incentive mechanisms for mobile phone sensing. We consider two system models: the platform-centric model where the platform provides a reward shared by participating users, and the user-centric model where users have more control over the payment they will receive. For the platform-centric model, we design an incentive mechanism using a Stackelberg game, where the platform is the leader while the users are the followers. We show how to compute the unique Stackelberg Equilibrium, at which the utility of the platform is maximized, and none of the users can improve its utility by unilaterally deviating from its current strategy. For the user-centric model, we design an auction-based incentive mechanism, which is computationally efficient, individually rational, profitable, and truthful. Through extensive simulations, we evaluate the performance and validate the theoretical properties of our incentive mechanisms.

Exploiting the nature of broadcast and the relaying capability of wireless devices, cooperative communication is becoming a promising technology to increase the channel capacity in wireless networks. In cooperative communication, the scheme for assigning relay nodes to users plays a critical role in the resulting channel capacity. A significant challenge is how to make the scheme robust to selfish and cheating behavior of users while guaranteeing the social optimal system capacity. In this paper, we design an integrated optimal marriage scheme called HERA for cooperative networks. To avoid system performance degradation due to the selfish relay selections by the source nodes, we propose a payment mechanism for charging the source nodes to induce them to converge to the optimal assignment. To prevent relay nodes from manipulating the marriage by reporting transmission power untruthfully, we propose a payment mechanism to pay them for providing relaying service. We also show that HERA is budget-balanced, meaning that the payment collected from source nodes is no smaller than the payment paid to relay nodes.

Delay constrained path selection is concerned with finding a source-to-destination path so that the delay of the path is within a given delay bound. When the network is modeled by a directed graph where the delay of a link is a random variable with a known mean and a known variance, the problem becomes that of computing a most probable delay constrained path. In this paper, we present a comprehensive theoretical study of this problem. First, we prove that the problem is NP-hard. Next, for the case where there exists a source-to-destination path with a delay mean no more than the given delay bound, we present a fully polynomial time approximation scheme. In other words, for any given constant ε such that 0 <; ε <; 1, our algorithm computes a path whose probability of satisfying the delay constraint is at least (1-ε) times the probability that the optimal path satisfies the delay constraint, with a time complexity bounded by a polynomial in the number of network nodes and 1/ε. Finally, for the case where any source-to-destination path has a delay mean larger than the given delay bound, we present a simple approximation algorithm with an approximation ratio bounded by the square root of the hop count of the optimal path.

In wireless sensor networks, relay node placement has been proposed to improve energy efficiency. In this paper, we study two-tiered constrained relay node placement problems, where the relay nodes can be placed only at some prespecified candidate locations. To meet the connectivity requirement, we study the connected single-cover problem where each sensor node is covered by a base station or a relay node (to which the sensor node can transmit data), and the relay nodes form a connected network with the base stations. To meet the survivability requirement, we study the 2-connected double-cover problem where each sensor node is covered by two base stations or relay nodes, and the relay nodes form a 2-connected network with the base stations. We study these problems under the assumption that R \ge 2r > 0, where R and r are the communication ranges of the relay nodes and the sensor nodes, respectively. We investigate the corresponding computational complexities, and propose novel polynomial time approximation algorithms for these problems. Specifically, for the connected single-cover problem, our algorithms have {\cal O}(1)-approximation ratios. For the 2-connected double-cover problem, our algorithms have {\cal O}(1)-approximation ratios for practical settings and {\cal O}(\ln n)-approximation ratios for arbitrary settings. Experimental results show that the number of relay nodes used by our algorithms is no more than twice of that used in an optimal solution.

The smart grid, perceived as the next generation power grid, uses two-way flow of electricity and information to create a widely distributed automated energy delivery network. By grouping distributed renewable energy generations and loads, a microgrid, which is seen as one of the cornerstones of the future smart grids, can disconnect from the macrogrid and function autonomously. This intentional islanding of generations and loads has the potential to provide a higher local reliability than that provided by the power system as a whole. One of the fundamental issues for a user in an islanded microgrid is how to find the one among the distributed renewable energy resources (DRERs) in a microgrid, which can supply the power most efficiently, effectively and reliably, as its power supply source. This problem is difficult since the power pattern of renewable resources, such as wind and solar, is variable and generally speaking is not easy to accurately predict. In order to solve this problem, we first propose a distributed DRER discovery approach to discover all the available DRERs within a microgrid. Furthermore, based on the online machine learning theory, we propose two distributed algorithms according to the information the user can obtain, in order to compute a good DRER access strategy, with no assumption on what distribution the power patterns of the DRERs follow. We prove that when the time horizon is sufficiently large, on average the upper bound on the gap between the expected profit obtained at each time slot by using the global optimal strategy and that by using our algorithms is arbitrarily small.

In the IEEE 802.16j standard, the relay station has been introduced to increase the coverage and the throughput of WiMAX networks. The placement of the relay station plays a critical role in the system performance and therefore draws tremendous attention from the research community. In this paper, we study the relay station placement problem in the WiMAX network, with the cooperative communication as the relaying strategy. In particular, given a base station and a set of subscriber stations, we determine the location of a relay station, and the set of subscriber stations using the relay station. The objective is to minimize the maximum transmission power among all the subscriber stations while satisfying the data rate requirements of the subscriber stations. We develop a near-optimal algorithm to solve this problem and prove that the maximum transmission power computed by our algorithm is at most Popt+ ε, where Poptis the maximum transmission power in the optimal solution and ε >; 0 is an arbitrary constant. The experiments show that we can dramatically reduce the maximum transmission power by deploying the relay station according to our algorithm.

Making new connections is a crucial service in current online social networks. However, such a service can also raise a big security concern. For example, two strangers become friends in the online social network and they want to communicate securely. The messages transmitted between them could be encrypted using their public keys and decrypted using their private keys. However, one can not determine whether this public key indeed belongs to the claimed user. In this paper, we design a system to authenticate two strangers in fast mixing online social networks. We make a thorough analysis on our system and show that there is a high probability of finding witness users in fast mixing social networks.

Anypath routing, a new routing paradigm, has been proposed to improve the performance of wireless networks by exploiting the spatial diversity and broadcast nature of the wireless medium. In this paper, we study the problem of finding an anypath subject to multiple (K) constraints, which has been proved to be NP-hard. We present a polynomial distributed K-approximation routing algorithm. Our algorithm is as simple as Bellman-Ford's shortest path algorithm. Extensive experiments show that our algorithm is very efficient and its result is as good as that obtained by the best centralized algorithm which requires the global information.

Black hole attacks occur when an adversary captures and re-programs a set of nodes in the network to block/drop the packets they receive/generate instead of forwarding them towards the base station. As a result any information that enters the black hole region is captured. Black hole attacks are easy to constitute, and they are capable of undermining network effectiveness by partitioning the network, such that important event information do not reach the base stations. Several techniques based on secret sharing and multipath routing have been proposed in the literature to overcome black hole attacks in the network. However, these techniques are not very effective, and as we demonstrate in this paper, they may even end up making black hole attacks more effective. We propose an efficient technique that uses multiple base stations deployed in the network to counter the impact of black holes on data transmission. Our simulation results demonstrate that our technique can achieve more than 99% packet delivery success. We prove that our scheme can identify 100% of the black hole nodes and demonstrate by simulation results that the technique suffers from very little false positives.

An RFID system generally consists of tags, readers, and backend servers with the readers charged with authenticating/identifying the tags with the help of the servers. Two important enhancements have been suggested for widespread adoption of RFIDs, namely the use of low cost (5¢ or less) passive RFID tags and serverless system design to overcome the need for persistent connection between the readers and the servers. Unfortunately, the low cost tags lack computation and storage capabilities to implement sophisticated security protocols to provide tag privacy and anonymous mutual authentication between the readers and the tags. Although several schemes (including some serverless schemes) have been proposed for authentication between tags and readers, they invariably have stringent computation and storage requirements and cannot be implemented in passive tags. In this paper, we propose SAMA, a novel serverless and anonymous mutual authentication scheme for a system consisting of passive tags and readers. Our scheme uses non-linear feedback shift registers and only logical operations to provide robust and anonymous mutual authentication. We perform security analyses and performance evaluation of SAMA and demonstrate its effectiveness and efficiency in comparison with other popular schemes in the literature. Our scheme requires only three message communications between the tag and the reader. Additionally, it requires only 1393 gates and 70 clock cycles at the tag.

Cooperative communication has been proposed to increase the capacity of wireless networks. By exploiting a relay node, it achieves spatial diversity to cope with fading channel without requiring wireless nodes to be equipped with multiple antennas. However, the selection of relay nodes has a significant impact on the final capacity. In this paper, we study the problem of relay assignment in cooperative networks, where multiple source-destination transmission pairs share the same set of relay nodes. Specifically, we propose a system model where a relay node can be shared by multiple source-destination pairs and present a corresponding formulation for the capacity calculation. Our objective is to find a relay assignment to maximize the total capacity of the network. As the main contribution, we develop an optimal relay assignment algorithm to solve this problem in polynomial time. We also show that our algorithm has several attractive properties.

Opportunistic routing is proposed to improve the performance of wireless networks by exploiting the broadcast nature and spatial diversity of the wireless medium. In this paper, we study the problems of how to choose opportunistic route for each user to optimize the total utility or profit of multiple simultaneous users in a wireless mesh network (WMN) subject to node constraints. We formulate these two problems as two convex programming systems. By combining primal-dual and subgradient methods, we present a distributed iterative algorithm Consort (node-Constrained Opportunistic Routing). In each iteration, Consort updates Lagrange multipliers in a distributed manner according to the user and node behaviors obtained in the previous iteration, and then each user and each node individually adjusts its own behavior based on the updated Lagrange multipliers. We prove the convergence of this iterative algorithm, and provide bounds on the amount of feasibility violation and the gap between our solution and the optimal solution in each iteration.

The notion of probabilistic network has been used to characterize the unpredictable environment in wireless communication networks or other unstable networks. In this paper, we are interested in the problem of placing servers in probabilistic networks subject to budget constraint, so as to maximize the expected number of servable clients that can successfully connect to a server. We study this problem in both the single-hop model and the multi-hop model. We discuss the computational complexity of this problem and show that it is NP-hard under both models.We then develop efficient approximation algorithms, which produce solutions provably close to optimal. If the costs of candidate locations are uniform, when extra budget is available in the future, the progressive feature of our algorithms allows for placing additional servers instead of relocating all the servers, while retaining the guaranteed performance. Results of extensive experiments on different topologies confirm the performance of our algorithms compared to the optimal algorithm and other heuristic algorithms.

The emerging WiMAX technology (IEEE 802.16) is the fourth generation standard for low-cost, high-speed and long-range wireless communications for a large variety of civilian and military applications. IEEE 802.16j has introduced the concept of mesh network model and a special type of node called Relay Station (RS) for traffic relay for Subscriber Stations (SSs). A WiMAX mesh network is able to provide larger wireless coverage, higher network capacity and Non-Line-Of-Sight (NLOS) communications. This paper studies a Distance-Aware Relay Placement (DARP) problem in WiMAX mesh networks, which considers a more realistic model that takes into account physical constraints such as channel capacity, signal strength and network topology, which were largely ignored in previous studies. The goal here is to deploy the minimum number of RSs to meet system requirements such as user data rate requests, signal quality and network topology. We divide the DARP problem into two sub-problems, LOwer-tier Relay Coverage (LORC) Problem and Minimum Upper-tier Steiner Tree (MUST) Problem. For LORC problem, we present two approximation algorithms based on independent set and hitting set, respectively. For MUST problem, an efficient approximation algorithm is provided and proved. Then, an approximation solution for DARP is proposed and proved which combines the solutions of the two sub-problems. We also present numerical results confirming the theoretical analysis of our schemes as the first solution for the DARP problem.

Cooperative communication is becoming a promising technology to increase the channel capacity of wireless networks. The assignment of relay nodes to users plays a critical role to the resulting channel capacity. A significant challenge is how to make the assignment scheme robust to selfish and cheating behavior of users while guaranteeing the social optimal system capacity. In this keynote, we will present an integrated optimal relay assignment scheme for cooperative networks. To avoid system performance degradation due to selfish relay selections by the users, we propose a payment mechanism for charging the users to induce them to converge to the optimal assignment. To prevent relay nodes from manipulating the relay assignment by reporting transmission powers untruthfully, we propose a payment mechanism to pay them for providing relaying service.

Recently Choi et al. designed the first practical wireless full-duplex system, which challenges the basic assumption in wireless communications that a radio cannot transmit and receive on the same frequency at the same time. Along this line, in this paper we study the cross-layer optimization for routing in full-duplex wireless networks, comprehensively considering various resource competitions and constraints. We first propose a collision-free full-duplex broadcast MAC and prove its necessary and sufficient conditions. We then focus on 1) the problem of how to choose routes to maximize the total profit of multiple users subject to node constraints, and 2) the problem of how to choose routes to minimize the network power consumption subject to the minimum user rate demands and node constraints. We formulate these two problems as convex programming systems. By combining Lagrangian decomposition and subgradient methods, we present distributed iterative algorithms to solve these two problems, which compute the optimized user information flow (i.e. user behavior) on the network layer and the optimized node broadcast rate (i.e. node behavior) on the MAC layer. Our algorithms allow each user and each node to adjust its own behavior individually in each iteration. We prove the convergence, and provide bounds on the amount of constraint violation, and the gap between the optimal solution and our solution in each iteration. Our work comprehensively considers various resource competitions and constraints, and provides a theoretical foundation for the future study on full-duplex wireless networks. To the best of our knowledge, this is the first work to study cross-layer optimization for full-duplex wireless networks.

Anypath routing is proposed to improve the performance of wireless networks by exploiting the spatial diversity and broadcast nature of the wireless medium. In this paper, we study anypath routing in wireless networks with directional antennas, and propose DART (Directional Anypath RouTing), a crosslayer design of MAC and routing layers. For the routing layer, we propose two shortest directional anypath routing algorithms based on two antenna models. Our routing algorithms are simple and fast, thus are suitable for implementation in practical protocols. For the MAC layer, we present a directional anycast MAC, which is an enhancement to the IEEE 802.11 MAC, making DART suitable for integration into current systems. Simulation results show that DART can significantly reduce the packet transmission delay.

On one hand, cooperative communication has been gaining more and more popularity since it has great potential to increase the capacity of wireless networks. On the other hand, the applications of cooperative communication technology are rarely seen in reality, even in some scenarios where the demands for bandwidth-hungry applications have pushed the system designers to develop innovative network solutions. A main obstacle lying between the potential capability of channel capacity improvement and the wide adoption of cooperative communication is the lack of incentives for the participating wireless nodes to serve as relay nodes. Hence, in this paper, we design TASC, an auction scheme for the cooperative communications, where wireless node can trade relay services. TASC makes an important contribution of maintaining truthfulness while fulfilling other design objectives. We show analytically that TASC is truthful and has polynomial time complexity. Extensive experiments show that TASC can achieve multiple economic properties without significant performance degradation compared with pure relay assignment algorithms.

In this paper, we propose a new privacy preservation scheme, named pseudonymous authentication-based conditional privacy (PACP), which allows vehicles in a vehicular ad hoc network (VANET) to use pseudonyms instead of their true identity to obtain provably good privacy. In our scheme, vehicles interact with roadside units to help them generate pseudonyms for anonymous communication. In our setup, the pseudonyms are only known to the vehicles but have no other entities in the network. In addition, our scheme provides an efficient revocation mechanism that allows vehicles to be identified and revoked from the network if needed. Thus, we provide conditional privacy to the vehicles in the system, that is, the vehicles will be anonymous in the network until they are revoked, at which point, they cease to be anonymous.

In this paper, we study the problem of maximizing the number of concurrent requests and the problem of minimizing the number of time-slots needed to schedule all requests in wireless networks under the physical interference model. It has been proved that both problems are NP-complete. Thus either approximation algorithms with guaranteed approximation factors or effective heuristics with practically good performances are desirable. We focus on the latter and present simple and effective heuristic algorithms for these two problems. Extensive experiments show that our algorithm for the first problem outperforms the best approximation algorithm by 62%-72% on average, and our two algorithms for the second problem give the best results among existing algorithms.

The recently emerging WiMAX (IEEE 802.16) is a promising telecommunication technology to provide low-cost, high-speed and long-range wireless communications. To meet the growing demand for throughput, Relay Station is introduced by IEEE 802.16j to relay traffic for Subscriber Stations. By incorporating Cooperative Communications scheme in WiMAX, we can further improve the network capacity. In this paper, we study the Relay Station placement problem, which seeks to deploy a minimum number of Relay Stations to satisfy all data rate requests from Subscriber Stations via Cooperative Communications. We analyze the computational complexity of the problem and prove it to be NP- Complete. Then we present efficient algorithms with guaranteed approximation ratios. Extensive experiments show that the number of Relay Stations returned by our algorithms is close to those returned by optimal solution.

In this paper, we study the problem of routing in networks with max-min fair congestion control at the link level. The goal of each user is to maximize its own bandwidth by selecting its path. The problem is formulated as a non-cooperative game. We first prove the existence of Nash Equilibria. This is important, because at a Nash Equilibrium (NE), no user has the incentive to change its routing strategy. In addition, we investigate how the selfish behavior of the users may affect the performance of the network as a whole. We next introduce a novel concept of observed available bandwidth on each link. It allows a user to find a path with maximum bandwidth under max-min fair congestion control in polynomial time. We then present a game based algorithm to compute an NE and prove that by following the natural game course the network converges to an NE. Extensive experiments show that the network can converge to an NE in less than 10 iterations and also significantly improves the fairness compared with other algorithms. Our results have the implication for the future routing protocol design.

Anypath routing has been proposed to improve the performance of unreliable wireless networks by exploiting the spatial diversity and broadcast nature of the wireless medium. In this paper, we focus on anypath routing subject to K constraints, and present a polynomial time K-approximation algorithm. When K = 1, our algorithm is the optimal polynomial time algorithm for the corresponding problem. When K ≥ 2, the corresponding problem is NP-hard. We are the first to present an O(1)-approximation algorithm. Furthermore, our algorithm is as simple as Dijkstra's shortest path algorithm, and is therefore suitable for implementation in actual wireless routing protocols.

In a wireless sensor network, short range multihop transmissions are preferred to prolong the network lifetime due to super-linear nature of energy consumption with communication distance. It has been proposed to deploy some relay nodes such that the sensors can transmit the sensed data to a nearby relay node, which in turn delivers the data to the base stations. In general, the relay node placement problems aim to meet certain connectivity and/or survivability requirements of the network by deploying a minimum number of relay nodes. In this paper, we study two-tiered constrained relay node placement problems, where the relay nodes can only be placed at some pre-specified candidate locations. To meet the connectivity requirement, we study the connected single-cover problem where each sensor node is covered by a relay node (to whom the sensor node can transmit data), and the relay nodes form a connected network with the base stations. To meet the survivability requirement, we study the 2-connected double-cover problem where each sensor node is covered by at least two relay nodes, and the relay nodes form a 2-connected network with the base stations. We focus on the computational complexities of the problems, and propose novel polynomial time approximation algorithms for these problems. For the connected single-cover problem, our algorithms have O(1) approximation ratios. For the 2-connected double-cover problem, our algorithms have O(1) approximation ratios for practical settings and O(lnn) approximation ratios for arbitrary settings. Experimental results show that the number of relay nodes used by our algorithms is no more than twice of the number of relay nodes used in an optimal solution.

In wireless networks, mutual interference prevents wireless devices from correctly receiving packages from others and becomes one of the challenges in the design of protocols for wireless networks. Spatial-reuse time division multiple access (STDMA) has been used to cope with this problem. In this scheme, links are assigned to several time slots and in each slot all the links can transmit simultaneously. In this paper, we propose a greedy link scheduling algorithm to find a short schedule for a problem instance in the physical interference model. Our scheduling algorithm is inspired by the k-MAX-CUT algorithm. Experimental results show that our greedy algorithm can give a better schedule compared with the greedy algorithm, with an improvement about 20%-30% when the density of links is high.

Fault tolerance techniques have been widely used in wireless sensor networks. Base station placement to maximize the network lifetime has also been well studied. However, limited research has been done on the joint base station placement and fault-tolerant routing problem. To fill this void, we study this problem and present a fully polynomial time approximation scheme in this paper. Our scheme can compute a (1 - ¿)approximation with a running time bounded by a polynomial in 1/¿ and the input size of the instance. Despite our solution is presented for the model where the base station can be placed anywhere, however it can be easily extended to cases where forbidden areas are present or candidate locations for the base station are given. To the best of our knowledge, this paper is the first theoretical result on this problem.

Cognitive radios allow unlicensed wireless users to access channels that are in the licensed spectrum bands. However, in a wireless network with cognitive radios, when a licensed user becomes active on a channel in a certain area, nodes and links that were using that channel must release it, which will cause traffic failures. Simple and effective recovery schemes are needed to re-allocate available resources for the failed traffic. In this paper, we study the failure recovery in wireless mesh networks with cognitive radios. We formally formulate the corresponding problems as integer linear programming problems. By solving them, we can obtain optimal solutions. Moreover, an efficient distributed heuristic algorithm is presented for fast recovery. Simulation results show that the performance given by our distributed algorithm is close to that of the optimal solutions.

In this paper, we propose SEAS, a novel privacy preserving, anonymous authentication scheme for RFID tags, which allows the tags to use pseudonyms instead of their true identity for authentication. Using SEAS, a tag generates random numbers and uses them to create a pseudonym as its identity for authentication. The pseudonym does not reveal the identity of the tag and the pseudonyms of multiple authentications appear random and uncorrelated to the adversary. A pseudonym can only be deciphered by the back-end authentication authority to identify the tag. No other entity in the network can link the pseudonym to the identity of the tag. Our scheme is efficient, with a tag needing to perform only simple operations such as XOR, bits shifting, bits concatenation, and random number generation. We perform security analysis of our scheme to show its effectiveness against different forms of attacks. We also perform comparison of our scheme with existing schemes in terms of efficiency in the use of resources. Our scheme performs effectively, while at the same time being better than the other popular schemes in the literature in terms of cost and computation efficiency.

In this paper, we study the problem of multi-path routing with bandwidth and delay constraints, which arises in applications for video delivery over bandwidth limited networks. Assume that each link in the network has a bandwidth and a delay. For a given source-destination pair and a bandwidth requirement, we want to find a set of source to destination paths such that the delay of the longest path is minimized while the aggregated bandwidth of the set of paths meets the bandwidth requirement. This problem is NP-hard, and the state of the art is a maximum flow based heuristic. We first construct a class of examples showing that the maximum flow based heuristic could have very bad performance. We then present a fully polynomial time approximation scheme that can compute a (1 + epsiv) -approximation with running time bounded by a polynomial in 1/epsiv and the input size of the instance. Given the NP-hardness of the problem, our approximation scheme is the best possible. We also present numerical results confirming the advantage of our scheme over the current state of the art.

Given a logical topology GLand a physical topology G, the survivable logical topology design problem in an IP-over- WDM optical network is to map the logical links into lightpaths in G such that GLremains connected after the failure of any edge in G. In view of its fundamental nature and its practical importance, this problem has received considerable attention in the literature. The SMART algorithmic framework based on the circuits in GLis a novel and very significant contribution to this problem. Taking advantage of the dual relationship between circuits and cutsets in a graph, we first present in this paper the primal algorithm CIRCUIT-SMART (similar to SMART) and algorithm CUTSET-SMART that is dual of CIRCUIT-SMART and proofs of correctness of these algorithms. To guarantee survivability we add additional logical links called protection edges, if necessary. This investigation has provided much insight into the structural properties of solutions to this problem and the structure of survivable logical graphs. Specifically, we present a highly simplified version of CUTSET-SMART that always provides a survivable mapping as long as G is 3-edge connected, and a survivable logical topology structure. We also present algorithm INCIDENCE-SMART that uses incidence sets that are special cases of a cut. Two efficient heuristics, one based on maximum matching theory and the other based on both the primal and dual algorithms are also presented. Simulation results comparing the different algorithms in terms of computational time, protection capacity and survivability success rate are also presented.

In this paper, we study QoS routing in wireless mesh networks with cognitive radios, which involves route selection, channel allocation and scheduling. It turns out to be a hard problem because of the impact of interference and channel heterogeneity. We formally model it as an optimization problem and present an integer linear programming (ILP) formulation to provide optimal solutions. We then present a distributed routing protocol which can select a route and allocate resources for a connection request to satisfy its end-to-end bandwidth requirement. NS2 based simulation results show the performance given by our protocol is close to that of the optimal solution.

Most research works in routing and design of optical networks assume that the optical medium can carry signals without any bit error. However, the physical impairments on the optical signal quality introduced by optical components, such as erbium-doped fiber amplifiers (EDFA) and optical cross connects (OXCs), must be considered in the routing and design problems of WDM networks in practice. In this paper, we studied the dynamic connection provisioning problem in WDM networks under multiple signal quality constraints. We present a polynomial time optimal algorithm that finds an active path for an incoming connection request with minimum network resource consumption. Simulation results show that our solution outperforms the previously best solution to the problem.

Node cooperation is one unique feature distinguishing wireless sensor networks (WSNs) from traditional wireless cellular networks. In this paper, we investigate joint clustering and optimal cooperative routing, where neighboring nodes dynamically form coalitions and cooperatively transmit packets to the next hop destination. We show that the cooperative sensor network can be modeled as an edge-weighted graph, based on which minimum energy cooperative routing is characterized by using the standard shortest path algorithm. We then focus on energy-delay-constrained maximum throughput routing, which is known to be NP-hard. We study two interesting cases: (1) For the case where the delay can be expressed in terms of the number of hops, we use the bi-section method to find the maximum throughput routing; (2) For large scale networks where the end-to-end delay can be approximated as the product of the number of hops and the average one-hop delay, we present a polynomial time algorithm to find the maximum throughput routing. Our numerical results confirm that the energy efficient cooperative routing can enhance the performance of WSNs significantly.

The problem of designing high capacity and high bit rate IP-over-WDM networks, which can provide uninterrupted service in the presence of network equipment failures, continues to attract significant interest from the research community. An IP-over-WDM network implements Internet Protocol (IP) directly over physical WDM network by establishing lightpaths using IP routers, optical crossconnects (OXC) and optical fibers. Generally an optical fiber carries several lightpaths and all of them get disconnected, if the fiber carrying them fails. Such failures can quickly impact the performance of the entire network. If IP routers can find paths to all the nodes in the network, then the network can continue to provide service without significant performance degradation. This can be achieved by reserving network resources (protection) or provisioning the network with some additional capacity (restoration). Such networks are usually called survivable networks. In this paper, we propose four algorithms based on SMART framework proposed by Kurant and Thiran, and a hybrid approach by Shenai and Sivalingam. The algorithms use a combination of protection and restoration mechanisms to make IP-over-WDM networks survivable such that the protection capacity required is not significant.

The relay node placement problem for wireless sensor networks is concerned with placing a minimum number of relay nodes into a wireless sensor network to meet certain connectivity and survivability requirements. We study constrained versions of the relay node placement problem, where relay nodes can only be placed at a subset of candidate locations. In the connected relay node placement problem, we want to place a minimum number of relay nodes to ensure the connectivity of the sensor nodes and the base stations. In the survivable relay node placement problem, we want to place a minimum number of relay nodes to ensure the biconnectivity of the sensor nodes and the base stations. For each of the two problems, we discuss its computational complexity, and present a framework of polynomial time O(1) -approximation algorithms with small approximation ratios.

In a wireless network (WN), the wireless devices generally localize themselves with the help of anchors that are pre-deployed in the network. Some of the techniques commonly used for localization are time of arrival (ToA), time difference of arrival (TDoA), angle of arrival (AoA), and time of flight (ToF). In the wireless domain, measurements are susceptible to errors resulting from the nature of the medium, the relatively low precision, and the presence of obstacles, which produce non-line of sight (NLOS) errors. The NLOS errors are a major concern as they could result in significant degradation in accuracy. In this paper, we propose an efficient technique that uses the distance estimates of the device from a group of anchors to localize the device with better accuracy in the presence of NLOS errors. Our technique is based on the notion that in general, for any estimate, the proportion of the NLOS error can be upper bounded. Using this upper bound information our technique reduces the uncertainty in the position of the wireless device that is being localized. The technique is distributed and is simple. In comparison to the standard localization procedure, where localization is done independent of the presence of NLOS errors, our technique uses the information about the NLOS error bounds to improve the accuracy of estimation. Simulation results show that our technique reduces the position error of the wireless device by 40% on an average and by at least 80% in the best case. The uncertainty in localization is also reduced significantly.

A fundamental problem in quality-of-service (QoS) routing is to find a path connecting a source node to a destination node that satisfies K ges 2 additive QoS constraints. This multi-constrained path problem (MCP) is known to be NP-complete. In a recent paper, Xue et at. showed that the shortest path with respect to a single auxiliary edge weight (obtained by combining the K edge weights into a single metric) is a if-approximation to MCP, in the sense thatthelargestratioofpathweightoveritscorrespondingconstraintis within a factor of K from minimum. In this paper, we present a simple greedy algorithm and prove that this greedy algorithm is also a if-approximation algorithm to MCP. Extensive computational results show that this greedy algorithm is superior to the previously best known if-approximation algorithm in terms of the quality of the path computed. Our algorithm is as simple as Dijkstra's shortest path algorithm, and is therefore suitable for implementation in Internet protocols.

In a wireless sensor network (WSN), the sensor nodes (SNs) generally localize themselves with the help of anchors that are pre-deployed in the network. Time of Arrival (ToA) is a commonly used mechanism for SNs localization in WSNs. In ToA, the SNs localize themselves using the positions of the anchors and the time difference between the receipt of a radio and ultrasound signal transmitted by each anchor. In this setting, the localization process has a high risk of being subverted by malicious anchors that lie about their position and/or distance from the SNs. In this paper, we propose an efficient scheme that helps identify and revoke these malicious anchors. We use a mobile verifier (MV) that moves throughout the network, in some pre-determined manner, and obtains multiple location references from each anchor. For each anchor, the MV tests the mean and the variance of the collected sample to identify if the anchor is malicious. We show through simulations that our scheme successfully identifies more than 80% of malicious anchors with less than 60 references from each. Also, the percentage of false positives is close to 0.

Two fundamental functions of the sensor nodes in a wireless sensor network are to sense its environment and to transmit sensed information to a basestation. One approach to prolong sensor network lifetime is to deploy some relay nodes whose main function is to communicate with the sensor nodes, other relay nodes, and the basestations. It is desirable to deploy a minimum number of relay nodes to achieve certain connectivity requirement. In this paper, we study four related fault-tolerant relay node placement problems, each of which has been previously studied only in some restricted form. For each of them, we discuss its computational complexity and present a polynomial time O(1)-approximation algorithm with a small approximation ratio. When the problem reduces to a previously studied form, our algorithm either improves the previous best algorithm or reduces to the previous best algorithm.

In this paper, we study the joint spectrum allocation and scheduling problems with the objectives of maximizing through-put and achieving certain fairness in Dynamic Spectrum Access (DSA) wireless networks. A novel Multi-Channel Contention Graph (MCCG) is proposed to characterize the impact of interference under the protocol interference model. Based on MCCG, we present an optimal scheme to compute maximum throughput solutions. As simply maximizing throughput may result in a severe bias on resource allocation, we take fairness into consideration by presenting optimal schemes to compute fair solutions based on a simplified max-min fairness model and the well-known proportional fairness model. Fast and effective heuristics are also proposed to provide high throughput and fair solutions. Numerical results show that compared with the optimal schemes, our heuristic schemes produce very close performance and our proportional fair schemes achieve a good tradeoff between throughput and fairness. In addition, we extend our research to the physical interference model.

A fundamental problem in quality-of-service (QoS) routing is the multiconstrained path (MCP) problem, where one seeks a source-destination path satisfying K \ge 2 additive QoS constraints in a network with K additive QoS parameters. The MCP problem is known to be NP-complete. One popular approach is to use the shortest path with respect to a single edge weighting function as an approximate solution to MCP. In a pioneering work, Jaffe showed that the shortest path with respect to a scaled 1-norm of the K edge weights is a 2--approximation to MCP in the sense that the sum of the larger of the path weight and its corresponding constraint is within a factor of 2 from minimum. In a recent paper, Xue et al. showed that the shortest path with respect to a scaled \infty-norm of the K edge weights is a K-approximation to MCP, in the sense that the largest ratio of the path weight over its corresponding constraint is within a factor of K from minimum. In this paper, we study the relationship between these two optimization criteria and present a class of provably good approximation algorithms to MCP. We first prove that a good approximation according to the second optimization criterion is also a good approximation according to the first optimization criterion, but not vice versa. We then present a class of very simple K-approximation algorithms according to the second optimization criterion, based on the computation of a shortest path with respect to a single edge weighting function.

In this paper, we study joint rate control, routing and scheduling in multi-channel wireless mesh networks (WMNs), which are traditionally known as transport layer, network layer and MAC layer issues respectively. Our objective is to find a rate allocation along with a flow allocation and a transmission schedule for a set of end-to-end communication sessions such that the network throughput is maximized, which is formally defined as the maximum throughput rate allocation (MRA) problem. As simple throughput maximization may result in a severe bias on rate allocation, we take account of fairness based on a simplified max-min fairness model and the proportional fairness models. We define the max-min guaranteed maximum throughput rate allocation (MMRA) problem and proportional fair rate allocation (PRA) problem. We present efficient linear programming (LP) and convex programming (CP) based schemes to solve these problems. Numerical results show that proportional fair rate allocation schemes achieves a good tradeoff between throughput and fairness.

Wavelength Division Multiplexing (WDM) can increase the carrying capacity of an optical network without laying additional fibers. However, a disruption in such a high speed and high capacity network can quickly impact the entire network. A fast protection and restoration recovery mechanism is needed to provide uninterrupted data delivery. Implementing IP directly over a WDM optical network, using optical crossconnects and IP routers, is emerging as the preferred method to efficiently utilize the enormous bandwidth offered by WDM networks. However, in such networks, a single link failure in the WDM layer can affect multiple links in the IP layer, which may greatly degrade data delivery. Several solutions have been proposed in the literature to avert such a scenario. These solutions mostly focus on finding paths for the IP connections in the WDM layer in such a way that the failure of a single WDM link does not disconnect the IP topology. Such a mapping is called "survivable". Due to the NP-completeness of the problem, various heuristics based on ILP formulations, tabu search, and shortest path variants have been proposed in the literature. In this paper we study a recent approach by Thiran and Kurant, point out certain attractive features and difficulties with this approach, and present enhancements to their basic approach to achieve better fault coverage and to add robustness to the survivable routing schemes. We provide simulation results evaluating the new heuristics.

In this paper, we propose a simple and efficient scheme for establishing anonymity in clustered wireless sensor networks. This scheme is applied to a clustered sensor network in which the nodes in a neighborhood share pairwise keys for authentic and confidential communication. The scheme, named Simple Anonymity Scheme (SAS), uses a range of pseudonyms as identifiers for a node in the network, to ensure concealment of its true identifier (ID). After deployment, neighboring nodes in the network share their individual pseudonyms and use them to ensure that the communication is anonymous and that a node's true ID is kept private. Even when many nodes in a given neighborhood of the network are compromised and are colluding, our scheme ensures that non-compromised nodes are still guaranteed complete anonymity. The compromised nodes cannot identify the sender or the receiver of communication happening between non-compromised nodes. Our scheme requires reasonably low memory and has very low computation cost, needing no change in other protocols of the network stack. It can be embedded into any wireless sensor network routing protocol to ensure anonymity and privacy during node discovery and routing in the network.

Wireless mesh network is designed as an economical solution for last-mile broadband Internet access. In this paper, we study bandwidth allocation in multi-channel multihop wireless mesh networks. Our optimization goals are to maximize the network throughput and, at the same time, to enhance fairness. First, we formulate and present an Linear Programming (LP) formulation to solve the Maximum throughput Bandwidth Allocation (MBA) problem. However, simply maximizing the throughput may lead to a severe bias on bandwidth allocation among wireless mesh nodes. In order to achieve a good tradeoff between fairness and throughput, we consider a simple max-min fairness model which leads to high throughput solutions with guaranteed maximum minimum bandwidth allocation values, and the well-known Lexicographical Max-Min (LMM) model. Correspondingly, we formulate the Max-min guaranteed Maximum throughput Bandwidth Allocation (MMBA) problem and the Lexicographical Max-Min Bandwidth Allocation (LMMBA) problem. For the former one, we present an LP formulation to provide optimal solutions and for the later one, we propose a polynomial time optimal algorithm.

In this paper, we study rate allocation for a set of end-to-end communication sessions in multi-radio wireless mesh networks. We propose cross-layer schemes which can jointly solve rate allocation, channel assignment, routing, scheduling and power control problems in multiple layers. Specifically, a Linear Programming (LP) based scheme is presented to compute end-to-end rate allocation with the goal of maximizing network throughput. As simple throughput maximization may lead to a severe bias on rate allocation, we take fairness into consideration based on a parameter named Demand Satisfaction Factor (DSF), and two fairness models, a simplified max-min fairness model and the well-known proportional fairness model. We propose LP-based and Convex Programming (CP) based schemes to compute fair end-to-end rate allocation. Our schemes can provide upper bounds on achievable network throughput and max-min DSF values. Numerical results show that our proportional fair rate allocation scheme achieves a good tradeoff between throughput and fairness.

Routing and wavelength assignment (RWA) aims to assign the limited number of wavelengths in a wavelength-division multiplexed (WDM) optical network so as to achieve greater capacity. In a recent paper, Datta et al. studied the problem of establishing a set of disjoint lightpaths on a tree topology using a single wavelength to maximize the total traffic supported by the chosen set of lightpaths. They discussed applications of this problem to RWA and presented a dynamic programming algorithm which optimally solves this problem in /spl Oscr/(n/sup 4/+n/spl Dscr//sup 3/) time, where n is the number of nodes in the network and /spl Dscr/ is the maximum node degree. In this paper, we present an improved algorithm with a time complexity of /spl Oscr/(n/sup 2/+n/spl Dscr//sup 2/).

Given a directed network with two integer weights, cost and delay, associated with each link, quality-of-service (QoS) routing requires the determination of a minimum cost path from one node to another node such that the delay of the path is bounded by a specified integer value. This problem, also known as the constrained shortest path problem (CSP), admits an integer linear programming (ILP) formulation. Due to the integrality constraints, the problem is NP-hard. So, approximation algorithms have been presented in the literature. Among these, the LARAC algorithm, based on the dual of the LP relaxation of the CSP problem, is very efficient. In contrast to most of the currently available approaches, we study this problem from a primal perspective. Several issues relating to efficient implementations of our approach are discussed. We present two algorithms of pseudopolynomial time complexity. One of these allows degenerate pivots and uses an anticycling strategy and the other, called the NBS algorithm, is based on a novel strategy which avoids degenerate pivots. Experimental results comparing the NBS algorithm, the LARAC algorithm, and general purpose LP solvers are presented. In all cases, the NBS algorithm compares favorably with others and beats them on dense networks.

Network motifs have been demonstrated to be the building blocks in many biological networks such as transcriptional regulatory networks. Finding network motifs plays a key role in understanding system level functions and design principles of molecular interactions. In this paper, we present a novel definition of the neighborhood of a node. Based on this concept, we formally define and present an effective algorithm for finding network motifs. The method seeks a neighborhood assignment for each node such that the induced neighborhoods are partitioned with no overlap. We then present a parallel algorithm to find network motifs using a parallel cluster. The algorithm is applied on an E. coli transcriptional regulatory network to find motifs with size up to six. Compared with previous algorithms, our algorithm performs better in terms of running time and precision. Based on the motifs that are found in the network, we further analyze the topology and coverage of the motifs. The results suggest that a small number of key motifs can form the motifs of a bigger size. Also, some motifs exhibit a correlation with complex functions. This study presents a framework for detecting the most significant recurring subgraph patterns in transcriptional regulatory networks.

In this paper, we study dynamic light trail routing in a WDM optical network. We present an efficient algorithm for establishing a light trail routing for a new connection request, while using minimum network resources. We also study survivable routing using light trail technology. We present an efficient heuristic for computing a pair of working and protection light trails for a given connection request. Simulation results are presented which demonstrate the advantages of our routing schemes.

Broadcasting and multicasting packets in a power efficient way is a critical task in wireless ad hoc networks. In a recent paper Li et al., (2004) study the minimum energy broadcast (MEB) routing problem in a wireless ad hoc network where every node has an omni-directional antenna and a fixed transmission power level. We extend their work to wireless networks with directional antennas in this paper. We formulate the minimum power multicasting/broadcasting using directional antennas (PMDA/PBDA) problems. For each problem, we present an approximation algorithm with worst- case approximation ratio O(log/sup 2/n), where n is the number of nodes in the network. We also present several effective heuristics to solve the problems, the shortest path tree (SPT) heuristic, the directed minimum spanning tree (DMST) heuristic and a greedy heuristic. Simulation results are presented to show the performance of our algorithms.

As a generalization of the traditional path protection scheme in WDM networks where a backup path is needed for each active path, the partial path protection scheme uses a collection of backup paths to protect an active path, where each backup path in the collection protects one or more links on the active path such that every link on the active path is protected by one of the backup paths. While there is no known polynomial time algorithm for computing an active path and a corresponding backup path using the path protection scheme for a source-destination node pair, we show that an active path and a corresponding collection of backup paths using the partial path protection scheme can be computed in polynomial time, whenever they exist, under each of the following two network models: (a) dedicated protection in WDM networks without wavelength converters; and (b) shared protection in WDM networks without wavelength converters. Under each of the two models, we prove, that for any given source s and destination d in the network, if one candidate active path connecting s and d is protectable using partial path protection, then any candidate active path connecting s and d is also protectable using partial path protection. This fundamental property leads to efficient shortest active path algorithms that can find an active path and its corresponding partial path protections whenever they exist. Simulation results show that shared partial path protection outperforms shared path protection in terms of blocking probability.

Recent research has shown that interference can make a significant impact on the performance of multihop wireless networks. Researchers have studied interference-aware topology control recently [M. Burkhart et al., 2004]. In this paper, we study routing problems in a multihop wireless network using directional antennas with dynamic traffic. We present new definitions of link and path interference that are suitable for designing better routing algorithms. We then formulate and optimally solve two power constrained minimum interference single path routing problems. Routing along paths found by our interference-aware algorithms tends to have less channel collisions and higher network throughput. Our simulation results show that, compared with the minimum power path routing algorithm, our algorithms can reduce average path interference by 40% or more at the cost of a minor power increase. We also extend our work towards survivable routing by formulating and solving the power constrained minimum interference node-disjoint path routing problem.

Medard, Finn, Barry and Gallager proposed an elegant recovery scheme (known as the MFBG scheme) using redundant trees. Xue, Chen and Thulasiraman extended the MFBG scheme and introduced the concept of quality of protection (QoP) as a metric of multifailure recovery capabilities for single failure recovery schemes. In this paper, we present three linear time algorithms for constructing redundant trees for single link failure recovery in 2-edge connected graphs and for single node failure recovery in 2-connected graphs. Our first algorithm aims at high QoP for single link recovery schemes in 2-edge connected graphs. The previous best algorithm has a running time of O(n/sup 2/(m+n)), where n and m are the number of nodes and links in the network. Our algorithm has a running time of O(m+n), with comparable performance. Our second algorithm aims at high QoS for single link recovery schemes in 2-edge connected graphs. Our algorithm improves the previous best algorithm with O(n/sup 2/(m+n)) time complexity to O(m+n) time complexity with comparable performance. Our third algorithm aims at high QoS for single node recovery schemes in 2-connected graphs. Again, our algorithm improves the previous best algorithm with O(n/sup 2/(m+n)) time complexity to O(m+n) time complexity with comparable performance. Simulation results show that our new algorithms outperform previously known linear time algorithms significantly in terms of QoP or QoS, and outperform other known algorithms in terms of running time, with comparable QoP of QoS performance.

We propose a novel approach for sparse topology generation in wireless ad hoc networks based on a graph structure known as /spl beta/-skeletons. Two efficient algorithms are presented in this paper for creating a connected topology from an underlying /spl beta/-skeleton. One algorithm is a localized algorithm that uses two-hop neighborhood information to generate a connected topology, with a running time of O(n). The other is a distributed algorithm that runs on each component of the /spl beta/-skeleton creating a connected structure from the disconnected /spl beta/-skeleton graph, the running time is O(nlogn). Simulations show consistent decrease in node degree in the resulting topology. The observed decrease is greater than 33% in comparison to the relative neighborhood graph (RNG) and greater than 50% in comparison to other topology structures such as, the Gabriel graph (GG) and the Yao construction on GG.

The throughput of wireless networks can be significantly improved by multi-channel communications compared with single-channel communications since the use of multiple channels can reduce interference influence. In this paper, we study interference-aware topology control and QoS routing in IEEE 802.11-based multi-channel wireless mesh networks with dynamic traffic. Channel assignment and routing are two basic issues in such networks. Different channel assignments can lead to different network topologies. We present a novel definition of co-channel interference. Based on this concept, we formally define and present an effective heuristic for the minimum INterference Survivable Topology Control (INSTC) problem which seeks a channel assignment for the given network such that the induced network topology is interference-minimum among all K-connected topologies. We then formulate the Bandwidth-Aware Routing (BAR) problem for a given network topology, which seeks routes for QoS connection requests with bandwidth requirements. We present a polynomial time optimal algorithm to solve the BAR problem under the assumption that traffic demands are splittable. For the non-splittable case, we present a maximum bottleneck capacity path routing heuristic. Simulation results show that compared with the simple common channel assignment and shortest path routing approach, our scheme improves the system performance by 57% on average in terms of connection blocking ratio.

Throughput is an important performance consideration for multihop wireless networks. In this paper, we study the joint link scheduling and power control problem, focusing on maximizing the network throughput. We formulate the maximum throughput link scheduling with power control (MATH-SPC) problem, and present a mixed integer linear programming (MILP) formulation to provide optimal solutions. However, simply maximizing the throughput leads to a severe bias on bandwidth allocation among all links. In order to enhance both throughput and fairness, we define a new parameter, the demand satisfaction factor (DSF), to characterize the fairness of bandwidth allocation. We formulate the maximum throughput fair link scheduling with power control (MATA-SPC) problem and present an MILP formulation for this problem. We also present an effective polynomial time heuristic algorithm, namely, the serial LP rounding (SLPR) heuristic. Our numerical results show that bandwidth can be fairly allocated among all links/flows by solving our MATA-SPC formulation or using our heuristic algorithm at the cost of a minor reduction of network throughput.

Abstract In this paper, we study the bandwidth guaranteed routing and timeslot allocation (BANDRA) in TDMA‐based multihop wireless networks with dynamic traffic. We formally model BANDRA as an optimization problem and present an integer linear programming (ILP) formulation to provide optimal solutions. This problem turns out to be a hard problem because of the impact of interference. Therefore, we propose a two‐step scheme, i.e., seeking a path for routing first and then allocating bandwidth along the found path. We present two routing algorithms to compute interference‐optimal cost‐bounded paths. In addition, we present an optimal bandwidth allocation algorithm to allocate timeslots along the found paths for connection requests with unit bandwidth requirements. For the general case where the bandwidth requirement is larger than one, we present an effective heuristic algorithm. Our simulation results show that the average difference between solutions given by our efficient scheme and optimal ones in terms of call‐blocking ratio is only 7%. Compared with the shortest path routing, our interference‐aware routing algorithms combined with our bandwidth allocation algorithm always reduce call‐blocking ratios. Copyright © 2005 John Wiley & Sons, Ltd.

Efficient transfer of bulk data requires routing that minimizes the net transfer time instead of providing flow level bandwidth guarantees. In this work, we consider a realistic scenario where available bandwidth for each link in a given network is time varying. In such a network and for a given file size, we provide an optimal algorithm that minimizes the total time required to transfer the file from source to destination. We further consider the problem where path shifting is allowed to increase the net throughput for bulk data transfer. For this problem, we provide a dynamic programming based optimal algorithm that minimizes the number of path shifts required to transfer the file in the specified time. Solution to the above problems addresses both the performance and scalability issues that arise in large bulk data transfer for long duration of time.

Survivability and lifetime are two important issues related to routing in wireless ad-hoc networks. Routing using node-disjoint paths enhances both survivability and data confidentiality. An elegant polynomial time algorithm has been reported recently that can compute node-disjoint paths connecting a source node to a destination node with minimum total energy. However, the problem of computing a pair of node-disjoint paths connecting a source node to a destination node with a lifetime no smaller than a given threshold has not been studied before. In this paper, we present efficient algorithms for computing a pair of node-disjoint paths connecting a source node to a destination node which either minimizes energy under lifetime constraint or maximizes lifetime under energy consumption constraint. We study the tradeoffs between path lifetime and total energy consumption in node-disjoint path routing and their effects on network throughput and network lifetime. Our preliminary simulation results show that routing with both path lifetime and total energy consumption considerations leads to significantly better network throughput and network lifetime.

In a WDM optical network, each fiber link can carry a certain set of wavelengths /spl Lambda/= {/spl lambda//sub 1/,/spl lambda//sub 2/,...,/spl lambda//sub W/}. One scheme for tolerating a single link failure (or node failure) in the network is the path protection scheme, which establishes an active path and a link-disjoint (or node-disjoint) backup path, so that in the event of a link failure (node failure) on the active path, data can be quickly re-routed through the backup path. We consider a dynamic scenario, where requests to establish active-backup paths between a specified source-destination node pair arrive sequentially. If a link-disjoint (node-disjoint) active-backup path pair is found at the time of the request, the paths are established; otherwise, the request is blocked. In this scenario, at the time a request arrives, not every fiber link will have all W wavelengths available for new call establishment, as some of the wavelengths may already have been allocated to earlier requests and communication through these paths may still be in progress. We assume that the network nodes do not have any wavelength converters. This paper studies the existence of a pair of link-disjoint (node-disjoint) active-backup paths satisfying the wavelength continuity constraint between a specified source-destination node pair. First we prove that both the link-disjoint and node-disjoint versions of the problem are NP-complete. Then we focus on the link-disjoint version and present an approximation algorithm and an exact algorithm for the problem. Finally, through our experimental evaluations, we demonstrate that our approximation algorithm produces near-optimal solutions in almost all of the instances of the problem in a fraction of the time required by the exact algorithm.

We present a novel time-based positioning scheme (TPS) for efficient location discovery in outdoor sensor networks. TPS relies on TDoA (time-difference-of-arrival) of RF signals measured locally at a sensor to detect range differences from the sensor to three base stations. These range differences are averaged over multiple beacon intervals before they are combined to estimate the sensor location through trilateration. A nice feature of this positioning scheme is that it is purely localized: sensors independently compute their positions. We present a statistical analysis of the performance of TPS in noisy environments. We also identify possible sources of position errors with suggested measures to mitigate them. Our scheme requires no time synchronization in the network and minimal extra hardware in sensor construction. TPS induces no communication overhead for sensors, as they listen to three beacon signals passively during each beacon interval. The computation overhead is low, as the location detection algorithm involves only simple algebraic operations over scalar values. TPS is not adversely affected by increasing network size or density and thus offers scalability. We conduct extensive simulations to test the performance of TPS when TDoA measurement errors are normally distributed or uniformly distributed. The obtained results show that TPS is an effective scheme for outdoor sensor self-positioning.

Reliability is a major issue in mobile ad hoc routing. Shortest paths are usually used to route packets in mobile ad hoc networks (MANET) However, a shortest path may fail quickly, because some of the wireless links on the shortest path may be broken shortly after the path is established due to mobility of mobile nodes. Rediscovering routes can result in substantial data loss and communication overheads. We consider a MANET in the urban environment. We formulate and study two optimization problems related to reliable routing in MANET. In the minimum cost duration-bounded path (MCDBP) routing problem, we seek a minimum cost source to destination path with duration no less than a given threshold. In the maximum duration cost-bounded path (MDCBP) routing problem, we seek a maximum duration source to destination path with cost no greater than a given constraint. We use a waypoint graph to model the working area of a MANET and present an offline algorithm to compute a duration prediction table for the given waypoint graph. An entry in the duration prediction table contains the guaranteed worst-case duration of the corresponding wireless link. We then present an efficient algorithm which computes a minimum cost duration-bounded path, using the information provided in the duration prediction table. We also present an heuristic algorithm for the MDCBP routing problem. Our simulation results show that our mobility prediction based routing algorithms lead to better network throughput and longer average path duration, compared with the shortest path algorithm.

Quality-of-service (QoS) routing problem requires the determination of a minimum cost path from a source node s to a destination node t in a data network such that the delay of the path is bounded by /spl Delta/ (> 0). This problem also known as the constrained shortest path (CSP) problem is NP-hard. So, heuristics and approximation algorithms have been presented in the literature. Among the heuristics, the LARAC algorithm, based on the dual of the LP relaxation or the Lagrangian relaxation of the CSP problem is very efficient. In this paper we study the primal simplex approach to the LP relaxation of the CSP problem and present an approximation algorithm to this problem. Several issues relating to efficient implementations of our approach are discussed. Experimental results comparing the performance of the new algorithm with that of the LARAC algorithm are presented.

Given a communication network modeled as a directed graph with a delay parameter associated with each link, we consider the problem of determining the most probable delay constrained path from a source node to a destination node. Assuming that the link delays are random variables with continuous and differentiable probability density function and using the central limit theorem this problem can be formulated as a path problem which involves simultaneously optimizing two additive path parameters. Two cases arise. When there is one path with mean delay less than the delay bound, we present an exact pseudo polynomial algorithm, a fully polynomial time /spl epsi/-approximation algorithm and a strongly polynomial heuristic algorithm. In the unlikely case when this assumption is violated, the problem is shown to be NP-hard and no constant factor approximation algorithm exists if P /spl ne/ NP. We also study the path protection problem under inaccurate state information.

A fundamental problem in QoS routing is to find a path between a specified source-destination node pair that satisfies a set of end-to-end quality of service constraints. We study this problem in a communication system where there are multiple additive quality of service parameters associated with each link. It is well-known that the multi-constrained path selection problem (MCPS) is NP-complete. In this paper, we present a fully polynomial time approximation scheme for an optimization version of the MCPS problem. This means that for any given /spl epsi/ > 0, we can compute, in time bounded by a polynomial of the input size of the problem and in 1//spl epsi/, a solution whose cost is at most (1 + /spl epsi/) of that of the optimal solution.

The high throughput provided by WDM technology in fiber optic networks has made WDM networks the choice of future high speed networks. Many efficient routing and wavelength assignment algorithms have been proposed in the literature. However, efficient construction of multicast trees in all-optical WDM networks is still a challenging problem. Due to the difficulty of partitioning the destinations into different wavelength groups, minimizing the network usage of a multicast tree in an all-optical WDM network is much harder than its counterpart in IP networks. In this paper, we present a simple greedy heuristic for constructing a dynamic multicast tree in an all-optical WDM network. Our algorithm can establish a multicast tree as long as all destinations are reachable from the source node. Computational results show that: (1) the blocking probability of our algorithm is considerably lower than other known WDM multicast algorithms; (2) the network usage required by our multicast tree is less than that of the multicast tree induced from minimum cost unicasts; (3) the time required to establish a multicast tree is very short.

We study quality-of-service (QoS) and quality-of-protection (QoP) issues in redundant tree based preplanned recovery schemes for a single-link failure in two-edge connected graphs and for a single-node failure in two-connected graphs. We present schemes (to be called G-MFBG schemes) that generalize the schemes (to be called MFBG schemes) developed by Medard et al. (1997) to construct a pair of redundant trees, called red and blue trees, which guarantees fast recovery from any single-link/node failure, as long as the failed node is not the root node. Using the G-MFBG schemes, we study QoS issues relating to red/blue trees. We present effective heuristics for computing a pair of redundant trees with low average delay or small total cost. We develop an optimal algorithm for computing a pair of red/blue trees with maximum bandwidth. Furthermore, a pair of red/blue trees guarantees fast recovery from simultaneous multiple failures if it satisfies certain properties. This leads us to define the concept of QoP of a pair of red/blue trees. We present an effective heuristic to construct a pair of red/blue trees with high QoP. The paper concludes with a discussion of computational results that demonstrate the effectiveness of the different algorithms presented.

In this paper, we study the minimum-cost quality-of-service multicast and unicast routing problems in communication networks. For the multicast problem, we present an efficient approximation algorithm to find a balance between a minimum-cost multicast tree and a minimum-delay multicast tree, with a provably good performance under the condition that link delay and link cost are identical. For the unicast problem, we present an efficient primal-dual heuristic algorithm to find a path which balances path cost and path delay, together with an error bound. The lack of a provably good performance for the second algorithm is complemented by computational results on randomly generated networks. Our algorithm finds optimal solutions in more than 80% of the cases and finds close to optimal solutions in all other cases, while using much less time.

Protection and restoration in high speed networks is an important issue, especially for applications in SONET and WDM networks. We study quality of service issues in preplanned recovery using redundant trees in 2-vertex connected graphs and 2-edge connected graphs. In particular, we present efficient heuristic algorithms for finding a pair of working-protection trees with small delay in the working tree. Extensive computational results show that our algorithms reduce the average delay in the working tree by 60% to 90%. Many challenging problems remain open.

We study quality of service issues in preplanned recovery using redundant trees in vertex-redundant or edge-redundant graphs. In particular, we present efficient heuristic algorithms for finding a pair of working-protection trees with large bandwidth in the working tree. Computational results are presented to demonstrate the effectiveness of our algorithms. Many challenging problems remain open.

We show that, in any given uniform orientation metric plane, the shortest network interconnecting a given set of points under a fixed topology can be computed by solving a linear programming problem whose size is bounded by a polynomial in the number of terminals and the number of legal orientations. When the given topology is restricted to a Steiner topology, our result implies that the Steiner minimum tree under a given Steiner topology can be computed in polynomial time in any given uniform orientation metric with /spl lambda/ legal orientations for any fixed integer /spl lambda/ /spl ges/ 2. This settles an open problem posed by Brazil, Thomas and Weng (2000).

We propose an improvement to a random walk model for personal communications services networks with hexagonal configuration. The number of states required is reduced from n(n + 1)/2 to (n/sup 2/ + 2n + 4)/4 if n is even, and to (n/sup 2/ + 2n + 5) /4 if n is odd, where n is the layers of a cluster.

The high throughput provided by WDM technology in fiber optic networks and the emergence of high speed all-optical wavelength converters have attracted extensive research on lightpath routing in WDM networks. Given a connection request, it is desirable to find a minimum cost lightpath or semi-lightpath to establish the connection without interrupting any existing connections. When a connection cannot be established without rerouting, one would like to establish a connection after rerouting a minimum number of existing lightpaths. In this paper, we present an efficient algorithm for computing a minimum cost route among routes requiring minimum cost reroutings. Our results provide either improvements or generalizations of several recent results in lightpath routing/rerouting.

Advanced resource reservation is a network protocol to guarantee quality of service (QoS) in data transmission. In a previous paper, Xue (see ICT2000: IEEE International Conference on Telecommunications, p.1071-75) introduced a network model using attribute lists to capture the availability of resources in networks with advanced resource reservations and formally defined various QoS routing problems with advanced resource reservation. In this paper, we present an efficient algorithm for computing an optimal solution to the source-waiting QoS routing problem under certain conditions.

In wavelength routed optical networks, wavelength converters can potentially reduce the requirement on the number of wavelengths. The problem of placing a minimum number of wavelength converters in a WDM network so that any routing can be satisfied using no more wavelengths than if there were wavelength converters at every node was raised by Wilfong and Winkler (1998) as the minimum sufficient set problem. This problem is NP-complete in general WDM networks. Wan et al. (1999), showed that the problem is tractable if every edge in the network is bi-directed and the skeleton of the network is a tree of rings. We show that the minimum sufficient set problem is tractable in any directed graph with a general tree of rings skeleton.

In this paper, we present a linear time algorithm for computing the hexagonal Steiner minimum tree for a set of points on the boundary of a regular hexagon. Computational results on randomly generated test problems show that our algorithm can find the optimal solutions on a 200 MHz Pentium within 18 seconds for n as large as 20000. It is expected that techniques of this paper may be generalized to the case where the points are on the boundary of a polygon.

With the advent of deep sub-micron technology, gate delays are much smaller than wire delays. As a result, hexagonal Steiner minimum trees have received extensive study recently because of their applications in VLSI physical design. Just like its rectilinear and Euclidean counterparts, the hexagonal Steiner minimum tree problem can be shown to be NP-hard. Therefore polynomial time approximation algorithms are of great interest. In a recent paper, Lin, Xue and Zhou (1999) proposed a quadratic time algorithm to compute an optimal layout of a hexagonal minimum spanning tree with attractive computational results. In this paper, we present an improved linear time algorithm for computing an optimal layout of a hexagonal minimum spanning tree.

We study end-to-end routing in a communication system where there is a link bandwidth and a link propagation delay associated with each link, as well as a queuing delay associate with each intermediate node. We present a polynomial time algorithm for computing an optimal multi-path end-to-end routing to transmit a given message. Examples are also given to show that a previously published path-based algorithm for this problem is suboptimal.

We studied the Steiner tree problem in four uniform orientations where any line, half-line, or line segment must be on a line which makes an angle of (iπ)/4 with the positive x-axis, for some i ∈ {0, 1, 2, 3}, and the distance between two points is measured as the length of the shortest polygonal path connecting them. We show that for any set P of n terminal points there exists a Steiner minimum tree interconnecting P such that all Steiner points are in 𝒢⌈2n/3⌉ − 1(P), the (⌈(2n)/3⌉ − 1)st-generation grid points of P. Our result improves the previous best result which guarantees that for any set P of n terminal points there is a Steiner minimum tree in which all Steiner points are in 𝒢n − 2(P). © 2000 John Wiley & Sons, Inc.

Multicast is an important operation in communication systems. In many real-time system applications, we are interested in finding a low-cost multicast tree satisfying a set of delay-constraints. Finding a minimum cost multicast tree is NP-hard, even in the case where the cost and delay of an edge are identical. In this paper, we present an efficient approximation algorithm for computing a low-cost multicast tree satisfying delay-constraints. Unlike most algorithms proposed in the literature, our algorithm has a provably good performance bound when the cost and delay of an edge are identical. This is achieved using a trade-off between a Steiner minimum tree and a shortest path tree. We also discuss extensions to communication systems where the cost and delay of an edge are different.

We study algorithms for approximating a Steiner minimal tree interconnecting n points under hexagonal routing. We prove that: (1) every minimum spanning tree is separable; (2) a minimum spanning tree with maximum node degree no more than 5 can be computed in O (n log n) time; (3) an optimal L-shaped layout of a given minimum spanning tree can be computed in O(n) time; (4) an optimal stair-shaped layout of a given minimum spanning tree can be computed in O(n/sup 2/) time. Computational results on standard benchmarks show that our algorithm compares favorably to the current best algorithms.

Chung and Ross [SIAM J. Comput., 20 (1991), pp. 726--736] conjectured that the multirate three-stage Clos network C(n,2n-1,r) is rearrangeable in the general discrete bandwidth case; i.e., each connection has a weight chosen from a given finite set {p 1 , p 2 ,. . .,p k } where $1 \geq p_1 > p_2 > \cdots > p_k > 0$ and p i is an integer multiple of p i , denoted by $p_k \mid p_i$, for $1 \leq i \leq k-1$. In this paper, we prove that multirate three-stage Clos network C(n,2n-1,r) is rearrangeable when each connection has a weight chosen from a given finite set {p 1 , p 2 ,. . .,p k } where $1 \geq p_1 > p_2 > \cdots > p_{h} > 1/2 \geq p_{h+1} > \cdots > p_k > 0$ and p h+2 | p h+1 ,p h+3 |p h+2 ,. . . ,p k | p h+1 . We also prove that C(n,2n-1,r) is two-rate rearrangeable and $C(n, \lceil \frac{7n}{3} \rceil, r)$ is three-rate rearrangeable.

We present the problem of constructing roads of minimum total length to interconnect n highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a set of optimality conditions for the problem and show how to construct a solution to meet this set of optimality conditions.

Given a source node and a set of destination nodes in a communication system in which there is associated with each channel a channel capacity and a channel reliability, an efficient algorithm is developed for computing a multicast tree which maximizes the capacity with reliability not less than a given threshold.

Given a tree network with n vertices where each edge has an operational probability, we are interested in finding a vertex on the tree whose expected number of reachable vertices is maximum. This problem was studied in Networks27 (1996) 219–237, where an O(n3) time algorithm and an O(n2) time algorithm were proposed. In this paper, we present an O(n) time algorithm for the same problem, improving the previously best algorithm by a factor of O(n). We also study a max–min version of the problem and propose an O(n) time algorithm for this problem as well. Examples are provided to illustrate the algorithms. © 1997 John Wiley & Sons, Inc. Networks 30:37–45, 1997

Many fault-detection problems fall into the following model: There is a set of n items, some of which are defective. The goal is to identify the defective items by using the minimum number of tests. Each test is on a subset of items and tells whether the subset contains a defective item or not. Let $M_\alpha (d,n)(M_\alpha (d|n))$ denote the maximum number of tests for an algorithm $\alpha $ to identify d defectives from a set of n items provided that d, the number of defective items, is known (unknown) before the testing. Let $M(d,n) = \min _\alpha M_\alpha (d,n)$. An algorithm a is called a competitive algorithm if there exist constants c and a such that for all $n > d > 0,M_\alpha (d|n) \leqslant cM(d,n) + a$. This paper confirms a recent conjecture that there exists a bisecting algorithm A such that $M_A (d|n) \leqslant 2M(d,n) + 1$. Also, an algorithm B such that $M_B (d|n) \leqslant 1.65M(d,n) + 10$ is presented.

In this paper, we propose a new kind of simulated annealing algorithm called two-level simulated annealing for solving certain class of hard combinatorial optimization problems. This two-level simulated annealing algorithm is less likely to get stuck at a non-global minimizer than conventional simulated annealing algorithms. We also propose a parallel version of our two-level simulated annealing algorithm and discuss its efficiency. This new technique is then applied to the Molecular Conformation problem in 3 dimensional Euclidean space and implemented on the Thinking Machines CM-5. With the full Lennard-Jones potential function, we were able to get satisfactory results for clusters with as many as 100,000 atoms. A peak rate of over 0.8 giga flop per second in 64-bit operations was sustained on a partition with 512 processing elements. To the best of our knowledge, ground states of Lennard-Jones clusters of as large as these have never been reported before.

The Lennard-Jones potential energy function arises in the study of low-energy states of proteins and in the study of cluster statics. This paper presents a mathematical treatment of the potential function, deriving lower bounds as a function of the cluster size, in both two and three dimensional configurations. These results are applied to the minimization of a linear chain, or polymer, in two-dimensional space to illustrate the relationship between energy and cluster size. An algorithm is presented for finding the minimum-energy lattice structure in two dimensions. Computational results obtained on the CM-5, a massively parallel processor, support a mathematical proof showing an essentially linear relationship between minimum potential energy and the number of atoms in a cluster. Computational results for as many as 50000 atoms are presented. This largest case was solved on the CM-5 in approximately 40 minutes at an approximate rate of 1.1 32-bit gigaflops.

A parallel algorithm for minimizing molecular energy potential functions is applied to the case of pure Lennard-Jones (LJ) clusters. The algorithm demonstrates the combination of discrete, lattice-based optimization with continuous optimization (relaxation) techniques. The suggested approach is not restricted to the LJ potential and is aimed at problems in which the potential of interest may be significantly more costly than the LJ. The intended audience includes researchers interested in practical computational problems involving minimum energy cluster conformation, such as may arise in catalysis, and those interested in algorithm development. The advantage of the algorithm is that the time required to find the minimum-energy structure for a relatively large cluster reduces to that of an interactive session. The current parallel implementation is capable of determining the best-known previously published binding energies for n>

The best known first order and second order methods for the Euclidean single facility location problem are Weiszfeld's algorithm and Newton's algorithm, respectively. With only a linear rate of convergence, Weiszfeld's algorithm is a simple closed form iteration formula. With a quadratic rate of convergence, Newton's algorithm is more complicated and requires a line search at each iteration. In this paper, computational comparisons were made between these two algorithms. Both sequential and parallel versions of each algorithm were compared. These results show that the second order method is more efficient for low dimensional problems while the first order method is more efficient for high dimensional problems. A parallel version of each algorithm was implemented on a NCUBE hypercube with 64 processors and tested on randomly generated problems with space dimension from 2 to 9, and the number of existing facilities from 1000 to 9000. A speedup of as high as 58 was achieved with 64 processors. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.