In key-value storage systems, a lot of traffic is concentrated on some of the hotspots. The servers that keep hotspots will become bottlenecks in the whole system because of this skewed workload. Recent studies have demonstrated that load imbalance can be effectively mitigated by deploying a small cache node in front of the back-end servers—commonly referred to as an in-network cache. With the advent of programmable switches, it has become feasible to position this cache node directly on the switch, a critical point through which all traffic naturally flows. A class of in-network cache solutions is proposed to balance workloads among backend servers, but they fall short in supporting dynamic workloads where hotspots vary quickly with time. We show that the bottleneck is caused by the slow rule update speed on switch hardware and programming abstraction — Match-Action Table (MAT). To achieve faster cache update, we designed a new cache calledRAM cachebased on register arrays that support the write-back method. The update of theRAM cacheis done in a data-flow-driven manner, and we ensure its correctness. However, due to the hardware limitations of programmable switches, the RAM cache cannot implement complex cache update policies and has low space utilization. To address workload dynamics without sacrificing system performance, we then design acache hierarchynamed ICH, which combines the advantages of both MAT and register. We carefully devise thecache admission and evictionto keep the cache coherence, continuously available, and the server workload light. Our ICH prototype and extensive experiments demonstrate ICH improves the key-value store throughput for various access patterns (read/write intensive), especially significantly for highly dynamic workloads (up to 155%).

In a key-value storage system, a small amount of hot item will account for most of the traffic. Skewed workloads can lead to load imbalance between servers, and some servers that keep hotspots will become system bottlenecks and impact the performance of the entire system. The recent studies have shown that the load imbalance can be eliminated by placing a small, fast cache node in front of the back-end servers, i.e., in-network cache. And the appearance of programmable switches made it possible to place this node on the switch, the place through which the traffic must pass. While existing in-network cache effectively balances loads between servers in large-scale storage systems, they struggle in write-intensive workloads and lose scalability with increasing client numbers due to imbalanced cache nodes. This paper introduces HarmonyCache, a scalable and high-performance in-network cache system that supports write-back methods. HarmonyCache use cache replication and read-write separation mode, only one node in all the cache is responsible for handling write requests, the other node can only handle read requests. To achieve system scalability and minimize cache coherence overhead, HarmonyCache proposes an adaptive cache replication scheme to decide where the cache should be replicated and how many replications should be made. Additionally, according to the requirements of different cache nodes, we design different types of in-network caches using different switch resources and propose a hybrid cache scheme. Our HarmonyCache prototype and extensive experiments demonstrate substantial improvements in key-value store throughput across various access patterns (read/write intensive), achieving a throughput gain of up to 7.6× over state-of-the-art solutions under skewed write-intensive workloads.

Online data-intensive services (OLDI) are subject to stringent service-level objectives (SLOs), yet unstable server response times can result in increased Remote Procedure Calls (RPC) tail latency. Request cloning is an effective technique for mitigating tail latency by masking variations in service time. However, traditional static cloning suffers from performance degradation under high load, while the coordinatorbased dynamic cloning scheme introduces additional delays and scalability challenges. Programmable switches present the opportunity to replicate requests dynamically in the network to eliminate additional delays. Still, they face issues with inconsistent server states and inaccurate load perception, which could lead to server overload and queue head blocking. Moreover, congestion control schemes must be considered due to the replication of requests. To address these challenges, we propose RoClone, which combines real-time status updates and fast-responsive server state awareness with congestion control to alleviate server-side pressure. RoClone overcomes memory and access limitations in programmable switches, ensuring low latency even under high load. We implemented RoClone on a Barefoot Tofino switch. Experimental results demonstrate that RoClone significantly reduces tail latency across various loads and maintains low tail latency under high load. The system reduces the 99th percentile latency by at least 60 % compared to NetClone and by at least 40 % compared to the baseline.

Radio Access Networks (RAN) are anticipated to gradually transition towards Cloud RAN (C-RAN), leveraging the full advantages of the cloud-native computing model. While this paradigm shift offers a promising architectural evolution to improve scalability, efficiency, and performance, significant challenges remain in managing the massive computing requirements of physical layer (PHY) processing. To address these challenges and meet the stringent Service Level Objectives (SLOs) in 5G networks, hardware acceleration technologies are essential. In this paper, we aim to mitigate this challenge by offloading 5G modulation mapping, a critical yet demanding function to encode bits into IQ symbols, directly onto the switch ASICs. Specifically, we introduce NetMod, a 5G New Radio (NR) standard-compliant in-network modulation mapper accelerator. NetMod leverages the capabilities of new-generation programmable switches within the C-RAN infrastructure to offload and accelerate PHY modulation functions. We implemented a NetMod prototype on a real-world platform using the Intel Tofino programmable switch and commodity servers running the Data Plane Development Kit (DPDK). Through extensive experiments, we demonstrate that NetMod achieves modulation mapping at switch line rate using minimal switch resources, thereby preserving ample space for traditional switching tasks. Furthermore, comparisons with a GPU-based 5G modulation mapper show that NetMod is 2.2$\boldsymbol{\times}$to 3.3$\boldsymbol{\times}$faster using only a single switch port. These results highlight the potential of in-network acceleration to enhance 5G network performance and efficiency.

In 5G Radio Access Networks (RAN), Cyclic Redundancy Check (CRC) algorithms play a vital role in detecting accidental changes to digital data during transmission. However, due to the massive bandwidth demands in 5G networks, CRC computation is a resource-intensive process. To address this challenge, we propose performing CRC computation and verification directly in the network path. Specifically, we introduce NetCRC-NR, a 5G New Radio (NR) standard-compliant in-network CRC accelerator. NetCRC-NR implements the 5G NR CRC algorithms specified in 3GPP TS 38.212, including CRC24A, CRC24B, CRC24C, CRC16, CRC11, and CRC6. It leverages programmable switches to perform in-network CRC generation and validation for the Transport Blocks (TBs) and Code Blocks (CBs), aiming at providing high CRC computation throughput and alleviating the computational burden on General-Purpose Processors (GPPs). We design and implement NetCRC-NR on Intel Tofino programmable switch and commodity servers running the Data Plane Development Kit (DPDK). Extensive experiments demonstrate that NetCRC-NR performs CRC generation and verification at the switch line rate of up to 4+Tbps CRC throughput, showcasing its efficiency and potential in accelerating the 5G RAN error detection process.

Federated learning (FL) has attracted growing attention since it allows for privacy-preserving collaborative training on decentralized clients without explicitly uploading sensitive data to the central server. However, recent works have revealed that it still has the risk of exposing private data to adversaries. In this paper, we conduct reconstruction attacks and enhance inference attacks on various datasets to better understand that sharing trained classification model parameters to a central server is the main problem of privacy leakage in FL. To tackle this problem, a privacy-preserving image distribution sharing scheme with GAN (PPIDSG) is proposed, which consists of a block scrambling-based encryption algorithm, an image distribution sharing method, and local classification training. Specifically, our method can capture the distribution of a target image domain which is transformed by the block encryption algorithm, and upload generator parameters to avoid classifier sharing with negligible influence on model performance. Furthermore, we apply a feature extractor to motivate model utility and train it separately from the classifier. The extensive experimental results and security analyses demonstrate the superiority of our proposed scheme compared to other state-of-the-art defense methods. The code is available at https://github.com/ytingma/PPIDSG.

The deployment of edge servers make a significant impact on the service quality of a Mobile Edge Computing (MEC) system. This service quality relies on solving two key sub-problems: 1) interference management between servers 2) the placement of MEC servers. To improve the Quality of Service (QoS), we propose a method based on Graph Partition (GP) and Upper Confidence Bound (UCB) for solving these two sub-problems. Regarding interference management, we use an undirected graph to represent the interference between MEC servers so that the overall graph can be divided into multiple subsets of non-interfering MEC servers. Regarding server placement, we propose a Multiple Choice-Upper Confidence Bound (MC-UCB) algorithm that place an collection of interference aware edge servers in each selection. To evaluate the performance, we define a user's QoS function based on transmission delay, throughput, and user density comprehensively and compared with Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) from previous work. The simulation results show that the performance of the proposed algorithms is improved by more than 4% compared with the GA algorithm and 6% compared with the PSO algorithm.

Breakthroughs in Wireless Energy Transfer technologies have revitalized Wireless Rechargeable Sensor Networks. However, how to schedule mobile chargers rationally has been quite a tricky problem. Most of the current work does not consider the variability of scenarios and how many mobile chargers should be scheduled as the most appropriate for each dispatch. At the same time, the focus of most work on the mobile charger scheduling problem has always been on reducing the number of dead nodes, and the most critical metric of network performance, packet arrival rate, is relatively neglected. In this article, we develop a DRL-based Partial Charging algorithm. Based on the number and urgency of charging requests, we classify charging requests into four scenarios. And for each scenario, we design a corresponding request allocation algorithm. Then, a Deep Reinforcement Learning algorithm is employed to train a decision model using environmental information to select which request allocation algorithm is optimal for the current scenario. After the allocation of charging requests is confirmed, to improve the Quality of Service, i.e., the packet arrival rate of the entire network, a partial charging scheduling algorithm is designed to maximize the total charging duration of nodes in the ideal state while ensuring that all charging requests are completed. In addition, we analyze the traffic information of the nodes and use the Analytic Hierarchy Process to determine the importance of the nodes to compensate for the inaccurate estimation of the node’s remaining lifetime in realistic scenarios. Simulation results show that our proposed algorithm outperforms the existing algorithms regarding the number of alive nodes and packet arrival rate.

Cyber Physical Systems (CPS) are networked systems of cyber (computation and communication) and physical (sensors and actuators) components that interact in a feedback loop with the possible help of human intervention, interaction and utilization. These ...

Spatial crowdsourcing as a promising computing paradigm has received significant attention recently. A fundamental issue of spatial crowdsourcing is online task assignment, i.e., the platform must make decisions immediately (assign or reject) for newly arriving objects (tasks or workers). Previous studies mostly focus on the rejection-aware assignment, which rarely considers non-rejection assignment for new arrival objects. To solve this new allocation model, in this paper, we first formulate a novel problem, namely Online Non-rejection aware Task Assignment (ONRTA) in spatial crowdsourcing, where an object cannot be rejected by the platform as long as there is a neighbor that satisfies the matching constraint with it. Then, we develop a non-rejection threshold-based random algorithm ONRTA-RT under the adversarial order model while obtaining a theoretical bound on the competitive ratio. More importantly, we consider a more natural random order model and propose a two-stage-based non-rejection aware task assignment approach, ONRTA-Base, which achieves a competitive ratio of$\frac{1}{4}$. Based on this framework, we further devise two non-rejection assignment approaches, ONRTA-OP and ONRTA-Greedy, which are more effective and run faster with a competitive ratio of$\frac{1}{4}$and$\frac{1}{8}$, respectively. Finally, experiments on synthetic and real datasets demonstrate that our proposed methods outperform the representative methods.

Spatial crowdsourcing platforms have become increasingly popular in people's daily life. A fundamental problem in spatial crowdsourcing is task assignment, which assigns spatial tasks to the workers appropriately in order to satisfy certain objectives. Previous studies usually focus on the real-time micro-task allocation, which does not consider the dependency relationships among tasks. To address this limitation, in this article, we define and formulate a new problem, called Online Dependent Task Assignment (ODTA) in preference aware spatial crowdsourcing. We first prove that ODTA is$\mathcal {NP}$-hard. Then, we design a threshold-based algorithm in the adversarial order model and obtain a near-optimal theoretical bound on the competitive ratio. More importantly, considering the random order arrival model, we further present three algorithms based on a two-stage framework, namely ODTA-Greedy, ODTA-Greedy-OP and ODTA-OPT, which are more effective with a constant competition ratio of$\frac{1}{8}$,$\frac{1}{8}$and$\frac{1}{4}$, respectively. Experimental results on both synthetic and real datasets show that our proposed ODTA-OPT approach outperforms the representative approaches in terms of overall utility.

Massive terminal users have brought explosive need of data residing at edge of overall network. Multiple Mobile Edge Computing (MEC) servers are built in/near base station to meet this need. However, optimal distribution of these servers to multiple users in real time is still a problem. Reinforcement Learning (RL) as a framework to solve interaction problem is a promising solution. In order to apply RL based algorithm into a multi-agent environment, we propose an iterative scheme: select individual users with priorities to interact with the environment iteratively one at a time Furthermore, we tried to optimize the overall system performance based on this scheme. Hence, we construct three objective system performance indicators: average processing cost, delay and energy consumption, improve the existing Deep Q-learning Network (DQN) by using the cost as reward function, changing the fixed exploitation rate into dynamic one that associated with reward and episode time. In order to explore the performance potential of the proposed algorithm, we have simulated the proposed algorithm, DQN algorithm and greedy algorithm under different users and data sizes. The results show that the proposed algorithm had reduced at least 12% of system average processing cost comparing to the greedy algorithm. It also outperform the greedy algorithm and DQN algorithm in delay and energy consumption significantly.

The past decade has witnessed the rapid expansion of demands for mobile traffic, while the traditional mobile traffic pricing schemes cannot accommodate such demands. Sponsored data plan (SDP), which can increase the revenue of all stakeholders in the market through transferring some of the revenue from content providers (CPs) to end users (EUs), is more suitable. However, existing studies have focused more on Internet service providers (ISPs) and CPs, ignoring the influence of EUs (e.g., the inherent attribute differences of EUs and the interaction among EUs) on the market under SDP. Regarding the difficulty of modeling the abstract property about interaction among EUs, we utilize network congestion as the medium and construct the congestion-aware SDP model based on Stackelberg game. The newly proposed model can not only analyze how network congestion affects SDP mechanism, but also elucidate the impact of interactions among EUs. More specifically, through theoretical analysis, we prove that there is a unique dynamic equilibrium in the interaction among EUs (i.e., the traffic consumption of different EUs). By taking into account network congestion, the newly proposed model also more accurately and realistically describes the optimal strategies and computation methods of all stakeholders in the market. Moreover, simulation experiments demonstrate that the positive effect brought by SDP is not as obvious as before, and EUs influence each other instead of being independent of each other. Overall, this paper emphasizes the non-negligible influence of EUs and promotes a deeper understanding of SDP mechanism, which can guide the relevant stakeholders to optimize their own decision-making details.

Intruders on the Internet usually launch network attacks through compromised hosts, called stepping stones, in order to reduce the chance of being detected. With stepping‐stone intrusions, an attacker uses tools such as SSH to log in several compromised hosts remotely and create an interactive connection chain and then sends attacking packets to a target system. An effective method to detect such an intrusion is to estimate the length of a connection chain. In this paper, we develop an efficient algorithm to detect stepping‐stone intrusion by mining network traffic using the k‐means clustering. Existing approaches for connection‐chain‐based stepping‐stone intrusion detection either are not effective or require a large number of TCP packets to be captured and processed and, thus, are not efficient. Our proposed detection algorithm can accurately determine the length of a connection chain without requiring a large number of TCP packets being captured and processed, so it is more efficient. Our proposed detection algorithm is also easier to implement than all existing approaches for stepping‐stone intrusion detection. The effectiveness, correctness, and efficiency of our proposed detection algorithm are verified through well‐designed network experiments.

Attackers on the Internet often launch network intrusions through compromised hosts, called stepping-stones, in order to reduce the chance of being detected. In a stepping-stone attack, an attacker uses a chain of hosts on the Internet as relay machines and remotely login these hosts using tools such as SSH. An effective method to detect stepping-stone intrusion is to estimate the length of a connection chain. In this paper, we develop an efficient algorithm to detect stepping-stone intrusion by mining network traffic using the k-Means clustering algorithm. Our proposed detection algorithm does not require a large number of TCP packets to be captured and processed. The length of a connection chain can be accurately determined by using our proposed detection method. Our proposed detection algorithm is more efficient and easier to implement than all of the existing connection-chain based approaches for stepping-stone intrusion detection. The effectiveness and correctness of our proposed detection algorithm are verified through well-designed network experiments.

The onset of wireless networks globally has thrust researchers in academia and industry to solve problems related to this ever-growing field. In this paper, we study the multi-constrained opportunistic wireless scheduling problem in cognitive radio networks. Given a collection of secondary user communication links, the channel state of each link is unknown due to the unpredictable primary users' activities, but can be estimated by exploring the channel state transitions and channel state feedback. A scheduling algorithm is used to decide a subset of links to transmit each time with both interference-free constraints and power budget constraints. The objective of this paper is to design a scheduling algorithm to optimize the average reward over a long time horizon. Current existing approaches cannot satisfyingly provide solutions for the wireless opportunistic scheduling problem when considering multiple constraints. In this work, we adopt the paradigm of the restless multi-armed bandit and propose a fast and simple approximation algorithm. The performance of the proposed algorithm is verified with a small approximation bound for the multi-constrained wireless opportunistic wireless scheduling problem.

The Roadside Unit (RSU) allocation is critical for the functionality and topology control of Vehicular Ad-Hoc Networks. However, due to the complexity of different transportation scenarios and the challenging coordination among different RSUs, the allocation is still a challenging issue in both the academic and practical industry. In this paper, we utilize the game theoretic RSU deployment to fundamentally improve the allocation of RSUs with practical consideration. Given a set of RSUs of arbitrary covering radii, assuming there is a budget requirement that specifies the total number of RSUs to be placed. In addition, considering the minimum distance requirement between any pair of RSUs, how to select a subset of RSUs to cover the maximum number of Points of Interest (POIs). We consider the selfish behaviors of RSU allocation and apply a game theoretic technique. We propose a mechanism to achieve a small price of anarchy.

We presentH2DP, a holistic heterogeneity-aware data placement scheme for hybrid parallel I/O systems, which consist of HDD servers and SSD servers. Most of the existing approaches focus on server performance or application I/O pattern heterogeneity in data placement.H2DPconsiders three axes of heterogeneity: server performance, server space, and application I/O pattern. More specifically,H2DPdetermines the optimized stripe sizes on servers based on server performance, keeps only critical data on all hybrid servers and the rest data on HDD servers, and dynamically migrates data among different types of servers at run-time. This holistic heterogeneity-awareness enablesH2DPto achieve high performance by alleviating server load imbalance, efficiently utilizing SSD space, and accommodating application pattern variation. We have implemented a prototype ofH2DPunder MPICH2 atop OrangeFS. Extensive experimental results demonstrate thatH2DPsignificantly improve I/O system performance compared to existing data placement schemes.

Security and anonymity are vital components in today's networked world, and play critical roles in several reallife situations, such as whistleblowing, intelligence operations, oppressive governments, etc. In this paper, we study anonymous communications in the context of Delay Tolerant Networks (DTNs). Existing work in this area relies on the standard onion routing paradigm to provide anonymity and is, therefore, vulnerable to malicious nodes. To this end, we introduce a novel message forwarding algorithm that utilizes random walks to deliver messages to their destinations. By removing the requirement to list all the intermediate nodes on the end-to-end path, our method enhances considerably the anonymity of the underlying communications. Our simulation results show that the proposed forwarding algorithm achieves high message delivery rates, at the expense of a moderate computational overhead at the mobile devices.

Vehicular ad-hoc networks (VANETs) have been envisioned to prominently enhance the road safety and traffic efficiency through real-time vehicle- to-vehicle and vehicle-to- infrastructure communications. Roadside Units (RSUs) play an important role in vehicular environments in terms of connectivity, routing, and transmission delay. However, deploying enough RSUs to provide a universal coverage within an area is not feasible. In addition, there still lacks understanding of the performance of message dissemination in urban environments where one deploys RSUs in a stand- alone fashion. In this paper, we study the performance of message dissemination in VANET environments and propose a Safety-Based Disconnected RSU Placement algorithm (S-BRP) that reduces the dissemination delay in some areas. We evaluate the S-BRP algorithm through extensive simulation studies. The proposed algorithm outperforms Mesh, the alternate deployment policy, in terms of the dissemination delay and traffic flow.

In Big Data era, applications are generating orders of magnitude more data in both volume and quantity. While many systems emerge to address such data explosion, the fact that these data's descriptors, i.e., metadata, are also “big” is often overlooked. The conventional approach to address the big metadata issue is to disperse metadata into multiple machines. However, it is extremely difficult to preserve both load-balance and data-locality in this approach. To this end, in this work we propose hierarchical indirection layers for indexing the underlying distributed metadata. By doing this, data locality is achieved efficiently by the indirection while load-balance is preserved. Three key challenges exist in this approach, however: first, how to achieve high resilience; second, how to ensure flexible granularity; third, how to restrain performance overhead. To address above challenges, we design Dindex, a distributed indexing service for metadata. Dindex incorporates a hierarchy of coarse-grained aggregation and horizontal key-coalition. Theoretical analysis shows that the overhead of building Dindex is compensated by only two or three queries. Dindex has been implemented by a lightweight distributed key-value store and integrated to a fully-fledged distributed filesystem. Experiments demonstrated that Dindex accelerated metadata queries by up to 60 percent with a negligible overhead.

Given a set of communication links in cognitive radio networks, assume that the underlying channel state information along each link is unknown; however, we can estimate it by exploiting the feedbacks and evolutions of channel states. Assume time is divided into time-slots. Under the protocol interference model, the opportunistic spectrum scheduling problem aims to select interference-free links to transmit at each time-slot to maximize the average throughput over the long time horizon. Existing works on the opportunistic spectrum scheduling problem cannot satisfyingly address the wireless interference constraints. We apply the framework of restless multi-armed bandit and develop approximation algorithms for the problem with stochastic identical links and nonidentical links respectively. Based on the updated estimations of channel states, the proposed algorithms keep refining future link scheduling decisions. We also obtain approximation bounds of these two proposed algorithms.

We study real-time multicast scheduling in multi- hop wireless sensor networks. Given multiple heterogeneous periodic multicast tasks, for each task, the data produced by the distinguished source node for a certain control application with sufficiently long time horizon need to be delivered to all target nodes periodically, the objective is to design an interference-aware routing and scheduling protocol to meet the delay requirements. In this work, we propose an efficient distributed routing and scheduling protocol under the protocol interference model. We conduct schedulability analysis and the proposed protocol approximately optimize the schedulable load. Based on our protocol design, we propose schedulability test schemes for a set of real-time multicast tasks. The performance evaluation results corroborate our theoretical analysis.

On Demand Frame Contention (ODFC) is designated as a solution to exclusive self-coexistence in wireless regional area networks. According to ODFC, contention winners are selected in a random manner regardless of the users' delay constraints and frame demands. As a result, ODFC may freeze some users due to that their delay constraints are not satisfied. Moreover, it may lead to a unfair resource distribution in terms of frame demands. To fully consider various delay constraints and frame demands, in this paper we formulate the resource allocation optimization problem as an integer programming problem and present a new approach termed \emph{On Demand Delay-constrained Fair Distribution} (ODDFD). ODDFD utilizes an iterative approach to solve the resource allocation problem considering delay constraints and frame demands. The distinguished feature of ODDFD is that it is able to deal with both delay sensitive networks and delay insensitive networks. Specifically, for a delay sensitive network, ODDFD minimizes jitter variance and average unexpected delay. For a delay insensitive network, the resource is allocated based on their frame demands and achieve a fair distribution in terms of their demands. Extensive simulations are conducted and verify that the jitter variance and average unexpected delay are decreased in a delay sensitive network, and the fairness of frame demands is increased in a delay insensitive network.

Motivated by many applications such as cognitive radio spectrum scheduling, downlink fading channel scheduling, and unmanned aerial vehicle dynamic routing, we study two restless bandit problems. Given a bandit consisting of multiple restless arms, the state of each arm evolves as a Markov chain. Assume each arm is associated with a positive weight. At each step, we select a subset of arms to play such that the weighted sum of the selected arms cannot exceed a limit. The reward of playing each arm varies according to the arm's state. The exact state of each arm is only revealed when the arm is played. The problem weighted restless bandit aims to maximize the expected average reward over the infinite horizon. We also study an extended problem called multiply-constrained restless bandit where each time there are two simultaneous constraints on the selected arms. First, the weighted sum of the selected arms cannot exceed a limit, Second, the number of the selected arms is at most a constant K. The objective of multiply-constrained restless bandit is to maximize the long term average reward. Both problems are partially observable Markov decision processes and have been proved to be PSPACE-hard even in their special cases. We propose constant approximation algorithms for both problems. Our method involves solving a semi-infinite program, converting back to a low-complexity policy, and accounting for the average reward via a Lyapunov function analysis.

We study minimum latency multiflow scheduling in duty-cycling multi-hop wireless networks. Given a set of multi-hop flows in duty-cycling wireless networks, each flow has a source node and a destination node, the objective is to schedule all multi-hop flows within a minimum latency. Under the uncoordinated duty-cycling model, we design transmission scheduling that can achieve a small constant factor of the optimal latency. The approximation ratio is independent of the period length p where p is the period length of duty-cycling networks. We also propose a duty-cycle-aware multiflow scheduling method based on node coloring. Finally, we study the routing and scheduling for multi-hop multiflow in wireless networks where each node has a full duty-cycle.

We study stable wireless link scheduling under the physical interference model in wireless networks. Given a set of elastic wireless communication requests arriving in an online fashion, the objective is to perform link scheduling to maximize the network throughput capacity. This well-motivated problem under an arbitrary physical interference model is notoriously hard. In this work, we develop efficient interference-aware scheduling protocols under different transmission power control settings, i.e., uniform power control and monotone power control. The novel proposed scheduling protocols can attain a provable efficiency ratio. The extensive simulations validates the proposed protocols under various environmental settings.

For wireless networks, coverage with different restrictions that can capture the practical requirements have received great research interests. We will study several restricted coverage problems. The first problem is aboutK-coverage, i.e., how to deploy wireless nodes such that each target is covered by at leastKwireless nodes. We study the problem restricted to linear-K-coverage where there is a line, all targets lie in one side of this line and all wireless nodes lie in the other side. Assume each wireless node is associated with a weight, the objective is to select a minimum weighted subset of nodes such that each target isK-covered. We propose a 3-approximation for this problem by exploring geometric properties. The second problem is calledK-road-coverage. Given a road map in a two-dimensional area which contains a set of paths and a set of wireless nodes, the locations of nodes can either be arbitrary or fixed, the objective is to select a minimum number of wireless nodes such that each path can beK-covered. We will reduce the problem toK-coverage and apply the algorithmic results forK-coverage to solve it. Another line of this work is to investigate a well-motivated problem called strongly dominating set, which is intrinsically related to coverage. Given a wireless networking system represented by a digraph G = (V, E⃗). Each wireless node u has a covering disk centering at u with its radius equal to the transmission range of u. We then draw a directed edge uv⃗ in G if u's corresponding covering disk contains v. A subset U ⊆ V of wireless nodes is a strongly dominating set if every wireless node in V \ U has both an in-neighbor in U and an out-neighbor in U. The objective is to find a minimum size strongly dominating set. Our method can achieve an approximation factor of (2 + ε).

Multiple-input multiple-output (MIMO) technology provides a means of boosting network capacity without requiring additional spectrum. It has received widespread attention over the past decade from both industry and academic researchers, now forming a key component of nearly all emerging wireless standards. Despite the huge promise and considerable attention, a rigorous algorithm-theoretic framework for maximizing network capacity in multihop wireless MIMO\ networks is missing in the state of the art. The existing algorithms and protocols for maximizing network capacity in multihop wireless MIMO networks are purely heuristic without any provable performance guarantees. In this paper we conduct a comprehensive algorithm study for maximizing network capacity in multihop wireless MIMO networks with receiver-side interference suppression, including the full characterization of NP-hardness and APX-hardness, the polynomial time approximation schemes, and the practical approximation algorithms with provable performance guarantees.

We study real time periodic query scheduling for data collection in multihop Wireless Sensor Networks (WSNs). Given a set of heterogenous data collection queries in WSNs, each query requires the data from the source sensor nodes to be collected to the control center within a certain end-to-end delay. We first propose almost-tight necessary conditions for a set of different queries to be schedulable by a WSN. We then develop a family of efficient and effective data collection algorithms that can meet the real-time requirement under resource constraints by addressing three tightly coupled tasks: (1) routing tree construction for data collection, (2) link activity scheduling, and (3) packet-level scheduling. Our theoretical analysis for the schedulability of these algorithms show that they can achieve a constant fraction of the maximum schedulable load. For the case of overloaded networks where not all queries can be possibly satisfied, we propose an efficient approximation algorithm to select queries to maximize the total weight of selected schedulable queries. The simulations corroborate our theoretical analysis.

Static greedy link schedulings have much simpler implementation than dynamic greedy link schedulings such as Longest-queue-first (LQF) link scheduling. However, its stability performance in multi-channel multi-radio (MC-MR) wireless networks is largely under-explored. In this paper, we present a stability subregion with closed form of a static greedy link scheduling in MC-MR wireless networks under the 802.11 interference model. By adopting some special static link orderings, the stability subregion is within a constant factor of the stable capacity region of the network. We also obtain constant lower bounds on the throughput efficiency ratios of the static greedy link schedulings in some special static link orderings.

We study delay-efficient data aggregation scheduling in wireless sensor networks subject to signal to interference-plus-noise ratio (SINR) constraints. We construct a routing tree and propose two scheduling algorithms that can generate collision-free link schedules for data aggregation. We prove that the delay of each algorithm is O(R + Δ) time slots, where R and Δ are respectively the graph radius and the maximum node degree in a reduced communication graph of the original network; the proposed algorithms are asymptotically optimum on delay in random wireless sensor networks. We evaluate the performances of the proposed algorithms and the simulation results corroborate our theoretical analysis.

We are in an age where people are paying increasing attention to energy conservation around the world. The heating and air-conditioning systems of buildings introduce one of the largest chunks of energy expenses. In this article, we make a key observation that after a meeting or a class ends in a room, the indoor temperature will not immediately increase to the outdoor temperature. We call this phenomenon thermal inertia . Thus, if we arrange subsequent meetings in the same room rather than in a room that has not been used for some time, we can take advantage of such undissipated cool or heated air and conserve energy. Though many existing energy conservation solutions for buildings can intelligently turn off facilities when people are absent, we believe that understanding thermal inertia can lead system designs to go beyond on-and-off-based solutions to a wider realm. We propose a framework for exploring thermal inertia in room management. Our framework contains two components. (1) The energy-temperature correlation model captures the relation between indoor temperature change and energy consumption. (2) The energy-aware scheduling algorithms: given information for the relation between energy and temperature change, energy-aware scheduling algorithms arrange meetings not only based on common restrictions, such as meeting time and room capacity requirement, but also energy consumptions. We identify the interface between these components so further works towards same on direction can make efforts on individual components. We develop a system to verify our framework. First, it has a wireless sensor network to collect indoor, outdoor temperature and electricity expenses of the heating or air-conditioning devices. Second, we build an energy-temperature correlation model for the energy expenses and the corresponding room temperature. Third, we develop room scheduling algorithms. In detail, we first extend the current sensor hardware so that it can record the electricity expenses in re-heating or re-cooling a room. As the sensor network needs to work unattendedly, we develop a hardware board for long-range communications so that the Imote2 can send data to a remote server without a computer relay close by. An efficient two-tiered sensor network is developed with our extended Imote2 and TelosB sensors. We apply laws of thermodynamics and build a correlation model of the energy needed to re-cool a room to a target temperature. Such model requires parameter calibration and uses the data collected from the sensor network for model refinement. Armed with the energy-temperature correlation model, we develop an optimal algorithm for a specified case, and we further develop two fast heuristics for different practical scenarios. Our demo system is validated with real deployment of a sensor network for data collection and thermodynamics model calibration. We conduct a comprehensive evaluation with synthetic room and meeting configurations, as well as real class schedules and classroom topologies of The Hong Kong Polytechnic University, academic calendar year of Spring 2011. We observe 20% energy savings as compared with the current schedules.

We are in an age where people are paying increasing attention to energy conservation around the world. The heating and air-conditioning systems of buildings introduce one of the largest chunk of energy expenses. In this paper, we make a key observation that after a meeting or a class ends in a room, the indoor temperature will not immediately increase to the outdoor temperature. We call this phenomenon Thermal Inertia. Thus, if we arrange subsequent meetings in the same room; than a room that has not been used for some time, we can take advantage of such un-dissipated cool or heated air and conserve energy. We develop a green room management system with three main components. First, it has a wireless sensor network to collect indoor, outdoor temperature and electricity expenses of the air-conditioning devices. Second, we build an energy-temperature correlation model for the energy expenses and the corresponding room temperature. Third, we develop room scheduling algorithms. Our system is validated with real deployment of a sensor network for data collection and thermodynamics model calibration. We conduct a comprehensive evaluation with synthetic room and meeting configurations. We observe a 30% energy saving as compared with the current schedules.

Data aggregation, as a primitive communication task in wireless networks, can reduce the communication complexity. However, in-network aggregation usually brings an unavoidable security defect. Some malicious nodes may control a large percentage of the whole network data and compel the network misbehave in an arbitrary manner. Thus, locating the malicious nodes to prevent them from further disaster is a practical challenge for data aggregation schemes. Based on the grouping and localization techniques, we propose a novel integrated protocol to locate malicious nodes. The proposed protocol does not rely on any special hardware and requests only incomplete information of the network from the security schemes. We also conduct simulation study to evaluate the proposed protocol.

Due to advances in low power micro-sensor technology, energy harvesting techniques, we can now build large scale solar-powered sensor networks to support long-running operations. Solar powered sensors often harvest variable amounts of energy in different weather conditions. Then a primary requirement for an efficient and a long-running solar-powered sensor system is to adapt to changing environment conditions and resources, and to gather as much valuable data as possible. Sensing and collecting data at a constant rate, without taking into account energy availability or data deliverability, will either drain the battery or waste resources. In this work, we design and test a highly efficient and robust solar-powered system SmartMote; and we further present an energy and value of information (VoI) aware routing strategy, that balances the rates of sensing with packet delivery for SmartMote. SmartMote achieves fairness and near maximum utility across the network. We deploy SmartMote in a forest with 100 sensors in order to monitor the humidity, temperature and luminance intensity. Our experimental results corroborate our design.

Longest-queue-first (LQF) link scheduling is a greedy link scheduling in multihop wireless networks. Its stability performance in single-channel single-radio (SC-SR) wireless networks has been well studied recently. However, its stability performance in multi-channel multi-radio (MC-MR)wireless networks is largely under-explored. In this paper, we present a stability subregion with closed form of the LQF scheduling in MC-MR wireless networks, which is within a constant factor of the network stability region. We also obtain constant lower bounds on the efficiency ratio of the LQF scheduling in MC-MR wireless networks under the 802.11 interference model or the protocol interference model.

In this paper, we study periodic query scheduling for data aggregation with minimum delay under various wireless interference models. Given a setQof periodic aggregation queries, each queryQi∈Qhas its own periodpiand the subset of source nodesSicontaining the data. We first propose a family of efficient and effective real-time scheduling protocols that can answer every job of each query taskQi∈Qwithin a relative delayO(pi) under resource constraints by addressing the following tightly coupled tasks: routing, transmission plan constructions, node activity scheduling, and packet scheduling. Based on our protocol design, we further propose schedulability test schemes to efficiently and effectively test whether, for a set of queries, each query job can be finished within a finite delay. Our theoretical analysis shows that our methods achieve at least a constant fraction of the maximum possible total utilization for query tasks, where the constant depends on wireless interference models. We also conduct extensive simulations to validate the proposed protocol and evaluate its practical performance. The simulations corroborate our theoretical analysis.

ABSTRACT In this paper, we studyk‐road‐coverage problems in wireless sensor networks (WSNs). Assume there is a 2‐dimensional area Ω with a given road map = (V,E) whereEcontains all road segments andVconsists of all intersection points on Ω. The first question we study is about ‘sensor deployment’,i.e., how to deploy a minimum number of sensor nodes on Ω such that each path (each road segment) on isk‐covered when all sensor nodes have the same sensing range. When sensors can only be deployed in a set of discrete locations, we propose an efficient method with the approximation ratio 6 + ϵ for the special case wherek = 1 and O(k) generally. If sensors can be deployed in arbitrary locations, we propose an efficient method with the approximation ratio 24 + ϵ whenk = 1 and O(k) generally. The second question we study is about ‘path query’,i.e., how to find thek‐covered path ork‐support path connecting any given source/destination pair of points on the road map . Basically, given any source/destination pair of pointsSandD, we present two algorithms which can efficiently find ak‐covered path connectingSandDand ak‐supported path connectingSandD, respectively. Copyright © 2010 John Wiley & Sons, Ltd.

Target tracking is a main application of wireless sensor networks (WSNs), and has been studied widely [4], [10]. In this work, we study indoor passive tracking problem using WSNs, in which we assume no equipment is carried by the target and the tracking procedure is passive. We propose to use light to track a moving target in WSNs. To our best knowledge, this is the first work which tracks a moving object by using light sensors and general light sources. We design a novel probabilistic protocol (system) iLight to track a moving target and several efficient methods to compute the target's moving patterns (like height, etc.) at the same time. We implement and evaluate our tracking system iLight in a testbed consisting of 40 sensor nodes, 10 general light sources and one base station. Through extensive experiments, we show that iLight can track a moving target efficiently and accurately.

Link scheduling is a fundamental problem in multihop wireless networks because the capacities of the communication links in multihop wireless networks, rather than being fixed, vary with the underlying link schedule subject to the wireless interference constraint. The majority of algorithmic works on link scheduling in multihop wireless networks assume binary interference models such as the 802.11 interference model and the protocol interference model, which often put severe restrictions on interference constraints for practical applicability of the link schedules. On the other hand, while the physical interference model is much more realistic, the link scheduling problem under physical interference model is notoriously hard to resolve and been studied only recently by a few works. This paper conducts a full-scale algorithmic study of link scheduling for maximizing throughput capacity or minimizing the communication latency in multihop wireless networks under the physical interference model. We build a unified algorithmic framework and develop approximation algorithms for link scheduling with or without power control.

We propose efficient spectrum channel allocation and auction methods for the online wireless channel scheduling. Assume that each user requests for the exclusive usage of a number of wireless channels for a certain time interval. The scheduler has to decide whether to grant its exclusive usage an how much will be charged. To possibly serve users with higher priority, preemptions are allowed with penalties. We analytically prove that our protocols are efficient, truthful, and they have asymptotically optimum competitive ratios. Our extensive simulations show that they perform almost optimum: most of our methods can achieve more than 50% of the optimum by offline method.

In this work, we design efficient algorithms for scheduling node activities, under the physical interference model, to minimize the delay for activating a set of communication links, or for finishing a data aggregation communication task. Given a set of communication links, assume that each link is associated with a positive weight (representing the award of transmission along this link). We consider two problems: the first one is to find an independent set of links with maximum total weight; the second one is to partition all links into independent subsets, such that the number of subsets is minimized. We are the first to develop distributed algorithms with constant approximations for both problems respectively. The other line of this work is to explore the relations between link scheduling and an important practical problem: Minimum Latency Aggregation Scheduling which seeks a shortest schedule for data aggregation in multi-hop wireless networks. By utilizing the algorithmic results for link scheduling, our proposed method can find an aggregation schedule that greatly improves the upper bound on latency, compared to the previous best result.

One of the most fundamental task of wireless networks is to provide coverage of a set of targets. Suppose that all nodes and targets lie in a plane, and all nodes have circular coverage ranges of arbitrary radii. The problem Minimum Wireless Cover (MWC) seeks the fewest nodes to cover the targets. If all nodes are associated with some positive prices, the problem Cheapest Wireless Cover (CWC) seeks a cheapest set of nodes to cover the targets. If all nodes have bounded lives, the problem Max-Life Wireless Cover (MLWC) seeks wireless coverage schedule of maximum life subject to the life constraints of individual nodes. In this paper, we present a polynomial time approximation scheme (PTAS) for MWC, and two randomized 2O(log* n)-approximation algorithms for CWC and MLWC respectively, where n is the number of nodes, and log* n is the iterated logarithm of n with base 2.

Abstract—Opportunistic routing [2], [3] has been shown to improve the network throughput, by allowing nodes that overhear the transmission and closer to the destination to participate in forwarding packets, i.e., in forwarder list. The nodes in forwarder list are prioritized and the lower priority forwarder will discard the packet if the packet has been forwarded by a higher priority forwarder. One challenging problem is to select and prioritize forwarder list such that a certain network performance is optimized. In this paper, we focus on selecting and prioritizing forwarder list to minimize energy consumption by all nodes. We study both cases where the transmission power of each node is fixed or dynamically adjustable. We present an energy-efficient opportunistic routing strategy, denoted as EEOR. Our extensive simulations in TOSSIM show that our protocol EEOR performs better than the well-known ExOR protocol (when adapted in sensor networks) in terms of the energy consumption, the packet loss ratio, and the average delivery delay. Index Terms—Sensor networks, opportunistic routing, energy. Ç 1

Data aggregation is a key functionality in wireless sensor networks (WSNs). This paper focuses on data aggregation scheduling problem to minimize the delay (or latency). We propose an efficient distributed algorithm that produces a collision-free schedule for data aggregation in WSNs. We theoretically prove that the delay of the aggregation schedule generated by our algorithm is at most 16R + Δ - 14 time slots. Here, R is the network radius and Δ is the maximum node degree in the communication graph of the original network. Our algorithm significantly improves the previously known best data aggregation algorithm with an upper bound of delay of 24D + 6Δ + 16 time slots, where D is the network diameter (note that D can be as large as 2R). We conduct extensive simulations to study the practical performances of our proposed data aggregation algorithm. Our simulation results corroborate our theoretical results and show that our algorithms perform better in practice. We prove that the overall lower bound of delay for data aggregation under any interference model is max{log n,R}, where n is the network size. We provide an example to show that the lower bound is (approximately) tight under the protocol interference model when rI= r, where rIis the interference range and r is the transmission range. We also derive the lower bound of delay under the protocol interference model when rII≥ 3r.

We study the problem of gateway placement for cost minimization (GPCM) in two-dimensional wireless mesh networks. We are given a set of mesh routers, assume they have identical transmission range r, represented by unit transmission disks around them. A router may be selected as a gateway at certain placing cost. A router is served by a gateway if and only if the gateway is within its transmission range. The goal of this work is to select a set of mesh routers as gateways to serve the rest routers with minimum overall cost. This problem is NP-hard. To the best of our knowledge, no distributed algorithm with a constant approximation ratio has been given before. When all weights are uniform, the best approximation ratio is 38. We present both centralized and distributed algorithms which can achieve approximation ratios 6 + ϵ and 20 respectively. Our algorithms greatly improve the best approximation ratios.

Shortest link scheduling (SLS) in multihop wireless networks under physical interference model is notoriously hard to resolve and been studied only recently by a few works. Most of the obtained approximation bounds grow linearly with the number of links, and many are only valid with single-hop wireless networks, and some claimed approximation bounds are even false. This paper conducts a rigorous algorithmic study of SLS with power control under the physical interference model. We develop a polynomial O (βlnα)-approximation algorithm for SLS, where α is the independence number and β is the power diversity.

Data aggregation is a primitive communication task in wireless sensor networks (WSNs). In this paper, we study designing data aggregation schedules under the Protocol Interference Model for answering queries. Given a network consisting of a set of nodes V distributed in a two-dimensional plane, we address different kinds of queries in this paper. First and foremost, we consider a single one-off query which requires a subset of source nodes V' C V to send data to a distinguished sink node, we propose a delay-efficient algorithm that produces a collision-free schedule and theoretically prove that the delay achieved by our algorithm is nearly a small constant factor of the optimum. We further extend our discussion to the multiple one-off queries case and periodic query case and propose our data aggregation scheduling algorithms respectively with theoretical performance analysis.

Minimum-latency beaconing schedule (MLBS) in synchronous multihop wireless networks seeks a schedule for beaconing with the shortest latency. This problem is NP-hard even when the interference radius is equal to the transmission radius. All prior works assume that the interference radius is equal to the transmission radius, and the best-known approximation ratio for MLBS under this special interference model is 7. In this paper, we present a new approximation algorithm called strip coloring for MLBS under the general protocol interference model. Its approximation ratio is at most 5 when the interference radius is equal to transmission radius, and is between 3 and 6 in general.

Efficient aggregation of data collected by sensors is crucial for a successful application of wireless sensor networks (WSNs). Both minimizing the energy cost and reducing the time duration (or called latency) of data aggregation have been extensively studied for WSNs. Algorithms with theoretical performance guarantees are only known under the protocol interference model, or graph-based interference models generally. In this paper, we study the problem of designing time efficient aggregation algorithm under the physical interference model. To the best of our knowledge, no algorithms with theoretical performance guarantees are known for this problem in the literature. We propose an efficient algorithm that produces a data aggregation tree and a collision-free aggregation schedule. We theoretically prove that the latency of our aggregation schedule is bounded by O(R+Δ) time-slots. Here R is the network radius and Δ is the maximum node degree in the communication graph of the original network. In addition, we derive the lower-bound of latency for any aggregation scheduling algorithm under the physical interference model. We show that the latency achieved by our algorithm asymptotically matches the lower-bound for random wireless networks. Our extensive simulation results corroborate our theoretical analysis.

The capacity of a wireless network has been widely studied in the literature, including the capacity for unicast and the capacity for broadcast. In this paper, we studied the capacity of a wireless network for broadcast. Previous studies on broadcast capacity either assume that all links in the wireless network has the same channel capacity, or assume that the transmission ranges of a wireless node can be arbitrarily large. In this paper we derive analytical upper bounds and lower bounds on broadcast capacity of a wireless network when all nodes in the network has the same bounded transmission power P and all nodes are placed in a square of side-length a. When the fixed data rate channel is used (each node can send W bits/second to nodes within its transmission range if no interference happened), we prove that the broadcast capacity is Θ(W) under the physical interference model. When the Gaussian channel capacity is used, we show that the total broadcast capacity is only Θ((α√log n/n)−βwhen α√log n/n → ∞. When a α√log n/n → O(1), we show that the broadcast capacity is Θ(1). We also generalize our results to multicast capacity for physical interference model.