Recent years have witnessed the booming development of RF sensing, which supports both identity authentication and behavior recognition by analysing the signal distortion caused by human body. In particular, RF-based identity authentication is more attractive to researchers, because it can capture the unique biological characteristics of users. However, the openness of wireless transmission raises privacy concerns since human behaviors can expose the massive private information of users, which impedes the real-world implementation of RF-based user authentication applications. Unfortunately, it is difficult to filter out the behavior information from the collected RF signals.In this paper, we propose a privacy-preserving deep neural network named BPCloak to erase the behavior information in RF signals while retaining the ability of user authentication. We conduct extensive experiments over mainstream RF signals collected from three real wireless systems, including the WiFi, Radio Frequency IDentification (RFID), and millimeter-wave (mmWave) systems. The experimental results show that BPCloak significantly reduces the behavior recognition accuracy, i.e., 85%+, 75%+, and 65%+ reduction for WiFi, RFID, and mmWave systems respectively, merely with a slight penalty of accuracy decrease when using these three systems for user authentication, i.e., 1%-, 3%-, and 5%-, respectively.

Due to limited energy supply on many Internet of Things (IoT) devices, asynchronous duty cycle radio management is widely adopted to save energy. Flooding is a critical way to disseminate messages through the whole network. Capture effect enabled concurrent broadcast is appealing to accelerate network flooding in asynchronous duty cycle networks. However, when the flooding payload's size is large, the concurrent broadcast performance is far from efficient due to the frequently unsatisfied capture effect. Intuitively, senders can send a short packet containing partial flooding payload to keep concurrent broadcast efficiency. In practice, we still face two challenges. Considering packet loss, a receiver needs an effective way to recover the entire flooding payload from several received packets as soon as possible. Moreover, considering different channel states of different senders, how a sender chooses the optimal packet length to guarantee high channel utilization is not easy. In this paper, we propose Chase++ a Fountain-code based concurrent broadcast control layer to enable fast flooding in asynchronous duty cycle networks. Chase++ uses Fountain code to alleviate the negative influence of a certain part of the flooding payload's continuous loss. Moreover, Chase++ adaptively selects packet length with the local estimation of channel utilization. Specifically, Chase++ partitions long payload into several short payload blocks, further encoded into many encoded payload blocks by Fountain-code. Then, with temporal and spatial features of the sampled RSS (received signal strength) sequence, a sender estimates the number of concurrent senders. Finally, according to the estimated number of concurrent senders, the sender determines the optimal number of encoded payload blocks in a packet and assembles the encoded payload blocks as lots of packets. Then, the concurrent broadcast layer continuously transmits these packets. Receivers can recover the original flooding payload after several independent encoded payload blocks are collected. We implement Chase++ in TinyOS with TelosB nodes. We further evaluate Chase++ on Local testbed with 50 nodes and Indriya testbed with 95 nodes. The improvement of network flooding speed can reach 23.6% and 13.4%, respectively.

Motivated by the fair rate allocation in a multiaccess Gaussian channel, this paper studies the problem of fair rate allocation over a generalized symmetric polymatroid with box constraints. The best-known algorithm for this problem has time complexity O(n5lnO(1)n). In this paper, we present a divide-and-conquer algorithm for this problem with quadratic running time. It is an implementation of a refined decomposing method for the more general separate concave maximization over a polymatroid with box constraints. A key ingredient of the algorithm is a linear-time algorithm for a generalized knapsack problem.

Due to limited energy supply on many Internet of Things (IoT) devices, asynchronous duty cycle radio management is widely adopted to save energy. Flooding is a critical way to quickly disseminate system parameters to adapt diverse network requirements. Capture effect enabled concurrent broadcast is appealing to accelerate network flooding in asynchronous duty cycle networks. However, when the length of flooding payload is long, due to frequently unsatisfied capture effect construction, the performance of concurrent broadcast is far from efficient. Intuitively, senders can send short packet that contains partial flooding payload to keep the efficiency of concurrent broadcast. In practice, we still face two challenges. Considering packet loss, a receiver needs an effective way to recover entire flooding payload from several received packets as soon as possible. Moreover, considering diverse channel state of different senders, how a sender chooses the optimal packet length to guarantee high channel utilization in a light-weight way is not easy. In this paper, we propose Chase++ a Fountain code based concurrent broadcast control layer to enable fast flooding in asynchronous duty cycle networks. Chase++ uses Fountain code to alleviate the negative influence of the continuous loss of a certain part of flooding payload. Moreover, Chase++ adaptively selects packet length with the local estimation of channel utilization. Specifically, Chase++ partitions long payload into several short payload blocks, which are further encoded into many encoded payload blocks by Fountain code. Then, with temporal and spatial features of the sampled RSS (received signal strength) sequence, a sender estimates the number of concurrent senders. Finally, according to the estimated number of concurrent senders, the sender determines the optimal number of encoded payload blocks in a packet and assembles the encoded payload blocks as lots of packets. Then, concurrent broadcast layer continuously transmits these packets. Receivers can recover original flooding payload after several independent encoded payload blocks are collected. We implement Chase++ in TinyOS with TelosB nodes. We further evaluate Chase++ on local testbed with 50 nodes and Indriya testbed with 95 nodes. The improvement of network flooding speed can reach 23.6% and 13.4%, respectively.

In this paper, we address a critical task of dynamically detecting the simultaneous behavior of driving and texting using smartphone as the sensor. We propose, design, and implement TEXIVE which achieves the goal of detecting texting operations during driving utilizing irregularities and rich micro-movements of users. Without relying on any external infrastructures and additional devices, and no need to bring any modification to vehicles, TEXIVE is able to successfully detect dangerous operations with good sensitivity, specificity, and accuracy by leveraging the inertial sensors integrated in regular smartphones. To validate our approach, we conduct extensive experiments involving in a number of volunteers on various of vehicles and smartphones. Our evaluation results show that TEXIVE has a classification accuracy of 87.18%, and precision of 96.67%.

Device authentication is a critical and challenging issue for the emerging Internet of Things (IoT). One promising solution to authenticate IoT devices is to extract a fingerprint to perform device authentication by exploiting variations in the transmitted signal caused by hardware and manufacturing inconsistencies. In this paper, we propose a lightweight device authentication protocol [named speaker-to-microphone (S2M)] by leveraging the frequency response of a speaker and a microphone from two wireless IoT devices as the acoustic hardware fingerprint. S2M authenticates the legitimate user by matching the fingerprint extracted in the learning process and the verification process, respectively. To validate and evaluate the performance of S2M, we design and implement it in both mobile phones and PCs and the extensive experimental results show that S2M achieves both low false negative rate and low false positive rate in various scenarios under different attacks.

We propose and implement a novel positioning system, WalkieLokie, which directly calculates the relative position from a smart device to a target. The requirement of the target is simple: it is attached with a “dummy” acoustic speaker, which does not have any other rich capabilities, such as audio recording, communication, or computation. Hence, the proliferation of smart devices, together with the cheap accessory (e.g., dummy speaker) embedded in daily used items (e.g., smart clothes), paves the way for WalkieLokie applications. WalkieLokie leverages the walking motion for locating an acoustic speaker. The key insight is that the distance between the user and the speaker varies in real time when the user walks, and the pattern of the variance implies the relative position. We design a novel algorithm to estimate the position and signal processing methods to support accurate positioning. The experiment results show that the mean errors of ranging and direction estimation are 0.63 m and 2.46°, respectively. Extensive experiments conducted in noisy environments validate the robustness of WalkieLokie.

In this paper, we propose and implement WalkieLokie, a novel acoustic-based relative positioning system. WalkieLokie facilitates a multitude of Augmented Reality (AR) applications: users with smart devices can passively acquire surrounding information in real time, similar to the commercial AR system Wikitude; the surrounding presenters, who want to share information or introduce themselves, can actively launch the function on demand. The key rational of WalkieLokie is that a user can perceive a series of spatial-related acoustic signals emitted from a presenter, which depicts the relation position between the user and the presenter. The proliferation of smart devices, together with the cheap accessory (e.g., dummy speaker) embedded in daily used items (e.g., smart clothes), paves the way for WalkieLokie applications. We design a novel algorithm to estimate the position and signal processing methods to support accurate positioning. The experiment results show that the mean error of ranging and direction estimation is 0.63m and 2.46 degrees respectively. Extensive experiments conducted in noisy environments validate the robustness of WalkieLokie.

Industry 4.0 brings forward higher requirements on the monitoring of industrial production. Video surveillance based on Wireless Mesh Networks (WMNs) has demonstrated its effectiveness in a number of applications. Different from some typical applications of WMN that solve the "last mile" Internet access problem, WMN-based video surveillance for industrial monitoring is very likely to work in extreme circumstances or requiring high performance. Thus, the guarantee of video quality is the key for the success of industrial video surveillance. Through extensive experimental research, we find that the state of the art mapping and queuing algorithms are approaching complication and the room for improvement is decreasing. The possible solution for performance breakthrough lies in exploiting the potentials of data granularity for mapping. In this work, we propose IMesh, a video transmission solution based on WMN, which takes frame type, frame location, data packets and other factors into consideration and quantifies their impacts on video quality. The proposed approach is particularly suitable for video surveillance in industrial production under aggressive conditions. To the best of our knowledge, IMesh is the first one that differentiates, prioritizes, and schedules video data in the packet level, which is the finest granularity one can achieve while keep the MAC layer protocol unchanged. Experiment results show that the proposed solution outperforms previous works both in terms of video quality and packet delay.

Duty cycling mode is widely adopted in wireless sensor networks to save energy. Existing duty-cycling protocols cannot well adapt to different data rates and dynamics, resulting in a high energy consumption in real networks. Improving those protocols may require global information or heavy computation and thus may not be practical, leading to many empirical parameters in real protocols. To fill the gap between the application requirement and protocol performance, in this paper, we analyze the energy consumption for duty cycled sensor networks with different data rates. Our analysis shows that existing protocols cannot lead to an efficient energy consumption in various scenarios. Based on the analysis, we design a light-weight adaptive duty-cycling protocol (LAD), which reduces the energy consumption under different data rates and protocol dynamics. LAD can adaptively adjust the protocol parameters according to network conditions such as data rate and achieve an optimal energy efficiency. To make LAD practical in real network, we further pre-calculate optimal parameters offline and store them on sensor nodes, which significantly reduces the computation time. We theoretically validate the performance improvement of the protocol. We implement the protocol in TinyOS and extensively evaluate it on 40 TelosB nodes. The evaluation results show the energy consumption can be reduced by 28.2-40.1 percent compared with state-of-the-art protocols. Results based on data from a 1,200-node operational network further show the effectiveness and scalability of the design.

In this paper, we propose a novel indoor localization scheme, Lightitude, by exploiting ubiquitous visible lights, which are necessarily and densely deployed in almost all indoor environments. Different from existing positioning systems that exploit special LEDs, ubiquitous visible lights lack fingerprints that can uniquely identify the light source, which results in an ambiguity problem that an RLS may correspond to multiple candidate positions. Moreover, received light strength (RLS) is not only determined by device's position, but also seriously affected by its orientation, which causes great complexity in site-survey. To address these challenges, we first propose and validate a realistic light strength model to avoid the expensive site-survey, then harness user's mobility to generate spatial-related RLS to tackle single RLS's position-ambiguity problem. Experiment results show that Lightitude achieves mean accuracy 1.93m and 2.24m in office (720m2) and library scenario (960m2) respectively.

In distributed networks such as wireless ad hoc networks, local and lossy logs are often available on individual nodes. We propose REFILL, which analyzes lossy and unsynchronized logs collected from individual nodes and reconstructs the network behaviors. We design an inference engine based on protocol semantics to abstract states on each node. Further we leverage inherent and implicit event correlations in and between nodes to connect interference engines and analyze logs from different nodes. Based on unsynchronized and incomplete logs, REFILL can reconstruct network behavior, recover the network scenario and understand what has happened in the network. We show that the result of REFILL can be used to guide protocol design, network management, diagnosis, etc. We implement REFILL and apply it to a large-scale wireless sensor network project. REFILL provides a detailed per-packet tracing information based on event flows. We show that REFILL can reveal and verify fundamental issues, like locating packet loss positions and root causes. Further, we present implications and demonstrate how to leverage REFILL to enhance network performance.

We propose an accurate acoustic direction finding scheme, Swadloon, according to the arbitrary pattern of phone shaking in a rough horizontal plane. Swadloon leverages sensors of the smartphone without the requirement of any specialized devices. Our Swadloon design exploits a key observation: the relative displacement and velocity of the phone-shaking movement corresponds to the subtle phase and frequency shift of the Doppler effects experienced in the received acoustic signal by the phone. Swadloon tracks the displacement of smartphone relative to the acoustic direction with the resolution less than 1 millimeter. The direction is then obtained by combining the velocity from the displacement with the one from the inertial sensors. Major challenges in implementing Swadloon are to measure the displacement precisely and to estimate the shaking velocity accurately when the speed of phone-shaking is low and changes arbitrarily. We propose rigorous methods to address these challenges, and apply Swadloon to several case studies: Phone-to-Phone direction finding, indoor localization and tracking. Our extensive experiments show that the mean error of direction finding is around 2.1 degree within the range of 32 m. For indoor localization, the 90-percentile errors are under 0.92 m. For real-time tracking, the errors are within 0.4 m for walks of 51 m.

Many wireless applications urgently demand an efficient neighbor discovery protocol to build up bridges connecting user themselves or to some service providers. However, due to intrinsic constraints of wireless devices, e.g., limited energy and error of clock synchronization, there is still absence of effective and efficient neighbor discovery protocols in the literature. In this work, we propose neighbor discovery protocols for the following two problems. First, we study Asynchronous Symmetry Neighbor Discovery problem, in which potential neighbor devices with asynchronous time clocks but the same duty cycle aim to find each other. Second, we propose an efficient protocol (utilizing Bouncing strategy) named BlindDatewith guaranteed worst-case performance 9/10 (1+δ)2x2where δ is a small fraction of the length of a time slot unit and 1/x is the duty cycle. Third, we extend this strategy to address Asynchronous Asymmetry Neighbor Discovery problem, in which both the time clock and the duty cycles of potential neighbors are considered to be heterogeneous. We conduct extensive experiments and simulations to examine the feasibility and efficiency of the proposed protocols, and results show that BlindDate greatly outperforms existing approaches in average-case. Compared with known protocols, BlindDate also achieves a better worst-case discovery latency bound (e.g., 10 percent performance gain comparing with Searchlight [1]).

We propose an accurate acoustic direction finding scheme, Swadloon, according to the arbitrary pattern of phone shaking in rough horizontal plane. Swadloon tracks the displacement of smartphone relative to the acoustic direction with the resolution less than 1 millimeter. The direction is then obtained by combining the velocity from the displacement with the one from the inertial sensors. Major challenges in implementing Swadloon are to measure the displacement precisely and to estimate the shaking velocity accurately when the speed of phone-shaking is low and changes arbitrarily. We propose rigorous methods to address these challenges, and apply Swadloon to several case studies: Phone-to-Phone direction finding, indoor localization and tracking. Our extensive experiments show that the mean error of direction finding is around 2.1° within the range of 32 m. For indoor localization, the 90-percentile errors are under 0.92 m. For real-time tracking, the errors are within 0.4 m for walks of 51 m.

Duty cycling mode is widely adopted in wireless sensor networks to save energy. Existing duty-cycling protocols cannot well adapt to different data rates and dynamics, resulting in a high energy consumption in real networks. Improving those protocols may require global information or heavy computation and thus may not be practical, leading to empirical parameters in real protocols. To fill the gap between the application requirement and protocol performance, we design a light-weight adaptive duty-cycling protocol (LAD), which reduces the energy consumption under different data rates and protocol dynamics. We theoretically validate the performance improvement of the protocol. We implement the protocol in TinyOS and extensively evaluate it on 40 TelosB nodes. The evaluation results show the energy consumption can be reduced by 28.2%~40.1% compared with state-of-the-art protocols. Results based on data from a 1200-node operational network further show the effectiveness and scalability of the design.

We study throughput-optimum localized link scheduling in wireless networks. The majority of results on link scheduling assume binary interference models that simplify interference constraints in actual wireless communication. While the physical interference model reflects the physical reality more precisely, the problem becomes notoriously harder under the physical interference model. There have been just a few existing results on link scheduling under the physical interference model, and even fewer on more practical distributed or localized scheduling. In this paper, we tackle the challenges of localized link scheduling posed by the complex physical interference constraints. By integrating the partition and shifting strategies into the pick-and-compare scheme, we present a class of localized scheduling algorithms with provable throughput guarantee subject to physical interference constraints. The algorithm in the oblivious power setting is the first localized algorithm that achieves at least a constant fraction of the optimal capacity region subject to physical interference constraints. The algorithm in the uniform power setting is the first localized algorithm with a logarithmic approximation ratio to the optimal solution. Our extensive simulation results demonstrate performance efficiency of our algorithms.

Many wireless applications urgently demand an efficient neighbor discovery protocol to build up a bridge connecting users to service providers or to other users. However, due to intrinsic constraints of wireless devices, e.g., limited energy and error of clock synchronization, there is still absence of effective and efficient neighbor discovery protocols in the literature. In this work, we propose neighbor discovery protocols for the following two problems. We first study Asynchronous Symmetry Neighbor Discovery problem, in which potential neighbor devices with asynchronous time clock but the same duty cycle aim to find each other. We further propose an efficient protocol (using Bouncing strategy) named Blind Date with guaranteed worst-case performance 9/10(1 + δ)2x2where δ is a small fraction of the length of time slot unit and 1/x is the duty cycle. Next, we extend this design to address Asynchronous Asymmetry Neighbor Discovery problem, in which both time clock and the duty cycles of potential neighbors are considered to be heterogeneous. We conduct extensive simulations to examine the feasibility and efficiency of the proposed protocols. Results show that Blind Date protocol outperforms existing approaches in average-case. We conclude that, compared with known protocols, Blind Date achieves a better worst-case discovery latency bound (e.g., 10% performance gain comparing with Searchlight [1]).

Much research has been conducted to securely outsource multiple parties' data aggregation to an untrusted aggregator without disclosing each individual's privately owned data, or to enable multiple parties to jointly aggregate their data while preserving privacy. However, those works either require secure pair-wise communication channels or suffer from high complexity. In this paper, we consider how an external aggregator or multiple parties can learn some algebraic statistics (e.g., sum, product) over participants' privately owned data while preserving the data privacy. We assume all channels are subject to eavesdropping attacks, and all the communications throughout the aggregation are open to others. We propose several protocols that successfully guarantee data privacy under this weak assumption while limiting both the communication and computation complexity of each participant to a small constant.

Leveraging a wireless multi-path channel as a source of common randomness, a number of key generation methods have been proposed according to information-theory security. However, by taking the advantages of node's mobility, existing schemes usually have low generation rate or low entropy. To overcome this limitation, we present a key generation protocol with known Artificial Interference, named Smoke Grenade, a new physical-layer approach for secret key generations in a narrowband fading channel. Our scheme utilizes artificial interference to contribute to the change of the measured values on channel states. The theoretical analysis shows that the key generation rate rises with the increment of the interference power. Particularly, the achievable key rate of Smoke Grenade achieves at least four times better than that of traditional key generation schemes when the average interference power is normalized to 1. Simulation results also show that Smoke Grenade has a higher generation rate and entropy compared with some known state-of-the-art approaches.

In this work, we address a critical task of detecting the user behavior of driving and texting simultaneously using smartphones. We propose, design, and implement TEXIVE which achieves the goal of distinguishing drivers and passengers, and detecting texting operations during driving utilizing irregularities and rich micro-movements of users. Without relying on any external infrastructures and additional devices, and no need to bring any modification to vehicles, TEXIVE is able to successfully detect dangerous operations with good sensitivity, specificity and accuracy. We conduct experimental study of TEXIVE with the help of a number of volunteers using various vehicles and smartphones. Our results indicate that TEXIVE has a classification accuracy of 87.18%, and precision of 96.67%.

We present SmartLoc, a localization system to estimate the location and the traveling distance by leveraging the lower-power inertial sensors embedded in smartphones as a supplementary to GPS. To minimize the negative impact of sensor noises, SmartLoc exploits the intermittent strong GPS signals and uses the linear regression to build a prediction model which is based on the trace estimated from inertial sensors and the one computed from the GPS. Furthermore, we utilize landmarks (e.g., bridge, traffic lights) detected automatically and special driving patterns (e.g., turning, uphill, and downhill) from inertial sensory data to improve the localization accuracy when the GPS signal is weak. Our evaluations of SmartLoc in the city demonstrates its technique viability and significant localization accuracy improvement compared with GPS and other approaches: the error is approximately 20m for 90% of time while the known mean error of GPS is 42.22m.

Leveraging a wireless multipath channel as the source of common randomness, many key generation methods have been proposed according to the information-theory security. However, existing schemes suffer a low generation rate and a low entropy, and mainly rely on nodes' mobility. To overcome this limitation, we present a key generation protocol with known artificial interference, named SmokeGrenade, a new physical-layer approach for secret key generation in a narrowband fading channel. Our scheme utilizes artificial interference to contribute to the change of measured values on channel states. Our theoretical analysis shows that the key generation rate increases with the increment of the interference power. Particularly, the achievable key rate of SmokeGrenade gains three times better than that of the traditional key generation schemes when the average interference power is normalized to 1. Simulation results also demonstrate that SmokeGrenade achieves a higher generation rate and entropy compared with some state-of-the-art approaches.

Constructive interference-based flooding (CIBF) is a latency-optimal flooding protocol, which can realize millisecond network flooding latency and submicrosecond time synchronization accuracy, require no network state information, and be adapted to topology changes. However, constructive interference (CI) has a precondition to function, i.e., the maximum temporal displacement Δ of concurrent packet transmissions should be less than a given hardware constrained threshold (e.g., 0.5 μs, for the IEEE 802.15.4 radio). In this paper, we derive the closed-form packet reception ratio (PRR) formula for CIBF and theoretically disclose that CIBF suffers the scalability problem. The packet reception performance of intermediate nodes degrades significantly as the density or the size of the network increases. We analytically show that CIBF has a PRR lower bound (94.5%) in the grid topology. Based on this observation, we propose the spine constructive interference-based flooding (SCIF) protocol for an arbitrary uniformly distributed topology. Extensive simulations show that SCIF floods the entire network much more reliably than the state-of- the-art Glossy protocol does in high-density or large-scale networks. We further explain the root cause of CI with waveform analysis, which is mainly examined in simulations and experiments.

Coverage is a fundamental problem in wireless sensor networks (WSNs). From both economic and applicable concerns, designers always would like to provide guaranteed QoS of coverage of WSNs. In this paper, we address two path-coverage problems in WSNs, maximum k-support path coverage (a.k.a. best case coverage) and minimum k-breach path coverage (a.k.a. worst case coverage), in which every point on the desired resultant path is covered by at least k sensors simultaneously while optimizing certain objectives. We present two polynomial-time approaches to find optimal solutions for both maximum k-support coverage problem and minimum k-breach coverage problem. The time complexity of both algorithms are O(k2n log n), where n is the number of deployed sensor nodes and k is the coverage degree. In addition, a number of properties of kth-nearest point Voronoi diagram are presented, which is new to the literature.

In low-duty-cycle wireless sensor networks, wireless nodes usually have two states: active state and dormant state. The necessary condition for a successful wireless transmission is that both the sender and the receiver are awake. In this paper, we study the problem: How fast can raw data be collected from all source nodes to a sink in low-duty-cycle WSNs? To address this, we define the Minimum Data Collection Delay (MDCD) problem, and give both the lower and upper tight bounds on the minimum delay for data collection when interfering links are eliminated. Furthermore, a novel concept, Virtual Grid Network (VGN) is introduced to successfully convert the MDCD problem into max-flow problem, and present a MDCD algorithm enlightened by the Ford-fulkerson max-flow method, which is able to find an optimal solution in polynomial time and achieves the lower bound. Extensive simulations are conducted and the results show that the proposed MDCD algorithm significantly outperforms the Shortest Path Routing algorithm (up to 32%) and achieves the lower bound.

As a large scale real sensor network system, GreenOrbs reveals that locating sensor nodes in the forest still faces great challenges because of volatile and fluctuating environmental factors. In this paper, we present a novel localization scheme, EARL, which provides accurate reference nodes and good ranging quality. We exam the range quality along routing paths by taking complex environmental factors into account, such as forest density, temperature and humidity. To improve localization accuracy, we use power scanning technique to judge the accuracy reference nodes and further calibrate the bad nodes through reverse-localization. To overcome the error propagation, we assign different weights to the range measurement according to the ranging quality. We implemented our localization scheme in GreenOrbs testbed, and evaluate through extensive experiments. The results demonstrate that EARL outperforms the current localization approaches with better accuracy. The localization accuracy achieved by our method is around 20% higher than best existing methods.

Motivated by the needs of precise carbon emission measurement and real-time surveillance for CO2management in cities, we present CitySee, a real-time CO2-monitoring system using sensor networks for an urban area (around 100 square kilometers). In order to conduct environment monitoring in a real-time and long-term manner, CitySee has to address the following challenges, including sensor deployment, data collection, data processing, and network management. In this discussion, we mainly focus on the sensor deployment problem so that necessary requirements like connectivity, coverage, data representability are satisfied. We also briefly go through the solutions for the remaining challenges. In CitySee, the sensor deployment problem can be abstracted as a relay node placement problem under hole-constraint. By carefully taking all constraints and real deployment situations into account, we propose efficient and effective approaches and prove that our scheme uses additional relay nodes at most twice of the minimum. We evaluate the performance of our approach through extensive simulations resembling realistic deployment. The results show that our approach outperforms previous strategies. We successfully apply this design into CitySee, a large-scale wireless sensor network consisting of 1096 relay nodes and 100 sensor nodes in Wuxi City, China.

Exploiting constructive interference in wireless networks is an emerging trend for it allows multiple senders transmit an identical packet simultaneously. Constructive interference based flooding can realize millisecond network flooding latency and sub-microsecond time synchronization accuracy, require no network state information and adapt to topology changes. However, constructive interference has a precondition to function, namely, the maximum temporal displacement Δ of concurrent packet transmissions should be less than a given hardware constrained threshold. We disclose that constructive interference based flooding suffers the scalability problem. The packet reception performances of intermediate nodes degrade significantly as the density or the size of the network increases. We theoretically show that constructive interference based flooding has a packet reception ratio (PRR) lower bound (95:4%) in the grid topology. For a general topology, we propose the spine constructive interference based flooding (SCIF) protocol. With little overhead, SCIF floods the entire network much more reliably than Glossy [1] in high density or large-scale networks. Extensive simulations illustrate that the PRR of SCIF keeps stable above 96% as the network size grows from 400 to 4000 while the PRR of Glossy is only 26% when the size of the network is 4000. We also propose to use waveform analysis to explain the root cause of constructive interference, which is mainly examined in simulations and experiments. We further derive the closed-form PRR formula and define interference gain factor (IGF) to quantitatively measure constructive interference.

We study distributed link scheduling for throughput maximization in wireless networks. The majority of results on link scheduling assume binary interference models for simplicity. While the physical interference model reflects the physical reality more precisely, the problem becomes notoriously harder under the physical interference model. There have been just a few existing results on centralized link scheduling under the physical interference model, though distributed schedulings are more practical. In this paper, by leveraging the partition and shifting strategies and the pick-and-compare scheme, we present the first distributed link scheduling algorithm that can achieve a constant fraction of the optimal capacity region subject to physical interference constraints in the linear power setting for multihop wireless networks.

Traffic matrices (TMs) are very important for traffic engineering and if they can be predicted, the network operations can be made beforehand. However, existing prediction methods are neither accurate nor efficient in practice. In this paper, we utilize the spatio-temporal property and low rank nature to directly predict the total TMs. The problem is that conventional matrix interpolation only works well when elements are missing uniformly and randomly. But in the case of TMs prediction, an entire part of the matrix is unknown. To solve this problem, we utilize some essential properties of TMs and add the time series forecasting into the matrix interpolation. We analyze our algorithm and evaluate its performance. The experiment result shows that our method can predict TMs under an NMAE of 30% in most cases, even predicting all the elements of next 3 weeks.

We study the multicast capacity of a random wireless network consisting of n randomly placed ordinary wireless nodes and m regularly placed base stations in a square region, known as a hybrid network. All ordinary wireless nodes have the uniform transmission range r and uniform interference range R=θ(r) and they can transmit/receive at Wa-bps. Each base station can communicate with adjacent base stations directly with a data rate WB-bps and the data transmission rate between a base station and a wireless node is assumed to be Wc-bps. Assume that there is a random set of ns ordinary wireless nodes that will serve as the source nodes of ns multicast flows (each has randomly selected k-1 receivers). Each flow will have data rate λi bps. We found that the minimum per-flow multicast capacity min n s over i = 1 λi for hybrid networks has three regimes, and for each regime we derive matching asymptotic upper and lower bounds. Thus it closes the gap of previous results in the literature.

We study the asymptotic networking-theoretic multicast capacity bounds for random extended networks (REN) under Gaussian channel model, in which all wireless nodes are individually power-constrained. During the transmission, the power decays along path with attenuation exponent \alpha > 2. In REN, n nodes are randomly distributed in the square region of side length \sqrt{n}. There are n_s randomly and independently chosen multicast sessions. Each multicast session has n_d+1 randomly chosen terminals, including one source and n_d destinations. By effectively combining two types of routing and scheduling strategies, we analyze the asymptotic achievable throughput for all n_s=\omega (1) and n_d. As a special case of our results, we show that for n_s=\Theta (n), the per-session multicast capacity for REN is of order \Theta ({1\over \sqrt{n_d n}}) when n_d=O({n\over ({\log n})^{\alpha +1}} ) and is of order \Theta ({1\over n_d} \cdot (\log n)^{-{\alpha \over 2} }) when n_d=\Omega ({n\over \log n} ).

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.

Object tracking is a main application of wireless sensor networks (WSNs), and has been studied widely. In this work, we study multiple objects tracking problem using WSNs, in which we assume no equipment is carried by the object and the tracking procedure is passive. We first show that without carefully design, Received Signal Strength Indicator (RSSI) and Link Quality Indicator (LQI) are not as effective as claimed for passive detection through our testbed studies. We further propose to use light to track moving objects in WSNs. To our best knowledge, this is the first work to study multiple objects tracking using light sensors and general light sources. We propose a novel probabilistic tracking protocol to track multiple objects. We further design several efficient methods to compute some attributes of the moving objects (like heights, moving speeds etc.).

In this paper, we focus on designing efficient query of top-k data produced by sensor nodes in a wireless sensor network (WSN). Assume that we are given a connected WSN of diameter D, consisting of n nodes with maximum node degree Δ. Two different models are studied. In the first model, each node holds a numeric element, the goal is to determine the top-k smallest (or biggest) of these elements from all nodes. In the second model, there are m objects in set ℒ, each node vi, 1 ≤ i ≤ n holds a numeric value Sj(vi) for each object Lj∈ ℒ,1 ≤ j ≤ m, the goal is to find the k objects in ℒ with the k smallest (or biggest) aggregated values /(sj(u1), Sj(v2), ..., Sj(vn)), where f is an aggregation function given in advance. We propose both fast and message efficient methods for conducting top-k queries in the two aforementioned models. Following that we study the minimum delay and messages required by any distributed method for top-k queries in both models. Our analysis shows that our methods are almost optimum. We conducted extensive experiments in both testbed and simulations to study the practical performances of our methods.

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.

In this paper, we study two tightly coupled topics in online social networks (OSN): relationship classification and information propagation. The links in a social network often reflect social relationships among users. In this work, we first investigate identifying the relationships among social network users based on certain social network property and limited pre-known information. Social networks have been widely used for online marketing. A critical step is the propagation maximization by choosing a small set of seeds for marketing. Based on the social relationships learned in the first step, we show how to exploit these relationships to maximize the marketing efficacy. We evaluate our approach on large scale real-world data from Renren network, showing that the performances of our relationship classification and propagation maximization algorithm are pretty good in practice.

We evaluate the performance of epidemic protocol in opportunistic networks. Early works follow an independent model which assumes that different messages in the network disseminate independently. Whereas, most recent work has pointed out that the same event can be detected by multiple nodes at different locations or different moments. Hence, the messages sensed by different nodes, indicating the same event, have spatial-temporal correlations. It is necessary to build an accurate mathematical model for reflecting the message dissemination process of epidemic protocol for further designing or optimizing the family of flooding protocols. However, the independent model does not provide good performance estimates in this situation. In this paper, we try to solve the problem by using a correlated model which takes into account the correlations among messages and permits the different messages denoting the same event to be aggregated in their propagation processes, and the numerical results show a close match with our theoretical analysis. Compared to the previous work, our correlated model, on the one hand, allows a network engineer to implement such a system with optimized performance confidently in an intermittently connected environment, on the other hand, our work offers a fresh insight into the spatial-temporal correlations of the messages and achieves good performance metrics in scalability.

Coverage quality is one critical metric to evaluate the Quality of Service (QoS) provided by wireless sensor net works. In this paper, we address maximum support coverage problem (a.k.a. best case coverage) in wireless sensor networks. Most of the existing work assume that the coverage degree is 1, i.e. every point on the resultant path should fall within the sensing range of at least one sensor node. Here we study the k -coverage problem, in which every point on the resultant path is covered by at least k sensors while optimizing certain objectives. We present tackle this problem under both centralized and distributed setting. The time complexity is bounded by O(k2n log n) where n is the number of deployed sensor nodes. To the best of our knowledge, this is the first work that presents polynomial time algorithms that find optimal k-support paths for a general k.

Barrier coverage is an important problem for sensor networks to fulfill some given sensing tasks. Barrier coverage guarantees the detection of events happened crossing a barrier of sensors. In majority study of barrier coverage using sensor networks, sensors are assumed to have an isotropic sensing model. However, in many applications such as monitoring an area using video camera, the sensors have directional sensing model. In this paper, we investigate strong barrier coverage using directional sensors, where sensors have arbitrarily tunable orientations to provide good coverage. We investigate the problem of finding appropriate orientations of directional sensors such that they can provide strong barrier coverage. By exploiting geographical relations among directional sensors and deployment region boundaries, we first introduce the concept of virtual node to reduce the solution space from continuous domain to discrete domain. We then construct a directional barrier graph (DBG) to model this barrier coverage question such that we can quickly answer whether there are directional sensors' orientations that can provide strong barrier coverage over a given belt region. If the belt region is strong barrier covered, we then develop energy-efficient solutions to find strong barrier path(s) that will approximately minimize the total or the maximum rotation angles of all directional sensors. Extensive simulations are conducted to verify the effectiveness of our solution.

Video surveillance system, which can provide real-time display of the monitored scene and video playback, has been employed in many areas including: commercial security, accident investigation, law enforcement and emergency response. However, audio which carries important information not available in video is usually not taken seriously and used effectively. In this paper, we develop an enhanced surveillance platform by introducing the low-power wireless audio sensor networks (WASNs). We can obtain more comprehensive and precise monitoring without the limitation of the line-of-sight and lighting condition. Moreover, this platform is designed and built for providing key support to varieties of applications. This article describes the platform architecture, including design, implementation, and performance. We describe the audio sensor platform which can deliver high-quality audio over sensor network by multi-hops with low power requirement. In addition, we present the multimedia synchronization mechanism in the heterogeneous network which is the foundation of applications in the proposed platform. Our experiments include an in-depth analysis of the bottlenecks within the platform as well as measurements for the various components.

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

In wireless sensor and actor networks (WSANs), a set of static sensor nodes and a set of (mobile) actor nodes form a network that performs distributed sensing and actuation tasks. In [1], Abbasi et al. presented DARA, a Distributed Actor Recovery Algorithm, which restores the connectivity of the interactor network by efficiently relocating some mobile actors when failure of an actor happens. To restore 1 and 2-connectivity of the network, two algorithms are developed in [1]. Their basic idea is to find the smallest set of actors that needs to be repositioned to restore the required level of connectivity, with the objective to minimize the movement overhead of relocation. Here, we show that the algorithms proposed in [1] will not work smoothly in all scenarios as claimed and give counterexamples for some algorithms and theorems proposed in [1]. We then present a general actor relocation problem and propose methods that will work correctly for several subsets of the problems. Specifically, our method does result in an optimum movement strategy with minimum movement overhead for the problems studied in [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.

We study efficient data collection in wireless sensor networks. We present efficient distributed algorithms with approximately the minimum delay, or the minimum number of messages to be sent by all nodes, or the minimum total energy costs by all nodes. We analytically prove that all proposed methods are either optimum or within constants factor of the optimum. We then investigate the possibility of designing one universal method such that the delay, the messages sent by nodes, and the total energy costs by all nodes are all optimum or within constants factor of optimum. Given a method A for data collection let ρT, ρM, and ρEbe the approximation ratios of A in terms of time complexity, message complexity, and energy complexity respectively. We show that, for data collection, there are networks of n nodes and maximum degree Δ, such that ρMρE= Ω(Δ) for any algorithm.

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.

In this paper, we study efficient data collection and aggregation problem in wireless sensor networks. We first propose efficient distributed algorithms for data collection problem with approximately the minimum delay, or the minimum number of messages to be sent by all wireless nodes, or the minimum total energy consumption by all wireless nodes respectively. For example, given an algorithm A for data collection, let ¿T, ¿M, and ¿Ebe the approximation ratio of A in terms of time complexity, message complexity, and energy complexity respectively. We then show that, for data collection, there are networks of n nodes and maximum degree ¿, such that ¿M¿E= ¿(¿) for any algorithm. In addition, we analytically proved that all our proposed methods are either optimum or within constants factor of the optimum. We further present the message, energy, time complexity and studied the complexity tradeoffs for data aggregation problem.

Opportunistic routing [1, 2] was shown to improve the network throughput greatly. The core idea is to allow any node in the forwarder list, which overhears the transmission and is closer to the destination to participate in forwarding the packet. The nodes in forwarder list are prioritized and the lower priority forwarder will discard the packet if it has been forwarded by a higher priority forwarder. One open problem is how to select and prioritize forwarder list efficiently. In the paper, we investigate how to select and prioritize forwarder list to minimize energy consumptions. We study the case where the transmission power of each node is fixed (known as non-adjustable transmission model) as well as the case where each node is able to adjust its transmission power for each transmission (known as adjustable transmission model). Energy optimum algorithms to select and prioritize forwarder list in both cases are presented and analyzed. Worth to mention that, our methods do not assume any geometrical properties or energy models, they apply to practical and dynamic wireless networks. In addition, we conducted extensive simulations in TOSSIM to study the performance of the proposed routing protocol by comparing it with ExOR [1].

We study the capacity for both random and arbitrary wireless networks under Gaussian Channel model when all wireless nodes have the same constant transmission power P. During the transmission, the power decays along path with attenuation exponent beta > 2. We consider extended networks, where n wireless nodes {v1, v2,hellip, vn} are randomly or arbitrarily distributed in a square region Bawith side-length a. We randomly choose nsmulticast sessions. For each source node vi, we randomly select k points pi,j(1 les j les k) in Baand the node which is closest to pi,jwill serve as a destination node of vi. We derive the achievable upper bounds on unicast capacity and an upper bound (partially achievable) on multicast capacity of the wireless networks under Gaussian Channel model. We found that the unicast (multicast) capacity for wireless networks under Gaussian Channel model has three regimes.

This paper presents novel distributed algorithms for scheduling transmissions in multi-hop wireless networks. Our algorithms generate new schedules in a distributed manner via simple local changes to existing schedules. Two classes of algorithms are designed: one assumes that the location information of all wireless nodes are known, and the other does not. Both classes of algorithms are parameterized by an integer k (called algorithm-k). We show that algorithm-k that uses geometry location achieves (1 - 2/k)2of the capacity region, for every k ges 3; algorithm-k which does not use geometry location achieves 1/rho of the capacity region, for every k ges 3 and a constant rho depending on k. Our algorithms have small worst-case overheads. Both classes of algorithms can generate a new schedule by requiring communications within Theta(k) hops for every node, which can be implemented by letting each node transmit at most O(k) messages. The parameter k explicitly captures the tradeoff between control overhead and the throughput performance of any scheduler. Additionally, the class of algorithms with known geometry location of nodes can And a new schedule in time Theta(k2Delta), where Delta is the minimum mini-time-slots such that each of the n nodes can communicate with its neighbors once, which is the minimum time-slots required by any scheduling algorithm.

In this work, we study indoor passive tracking problem in wireless sensor networks (WSNs), in which we assume the target being tracked is "clean", i.e., there is no any equipment carried by the target and the tracking procedure is considered to be passive. We design, implement and test our tracking methods in a WSN testbed consisting of 40 wireless sensor nodes and one base station (laptop).

Using solar panels to power wireless sensor nodes is feasible in most of WSNs applications. We present an efficient solar-charging system and a remote energy-profile monitoring system which can monitor the dynamic charging procedure of wireless sensor nodes in different environments. We design and implement dynamic routing policies according to the current available energy of nodes for WSNs powered by solar panels.

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.

We study the multicast capacity of a random wireless network consisting of ordinary wireless nodes and base stations, known as a hybrid network. Assume that n ordinary wireless nodes are randomly deployed in a square region and all nodes have the uniform transmission range r and uniform interference range R>r. We further assume that each ordinary wireless node can transmit/receive at W bits/second over a common wireless channel. In addition, there are m additional base stations (neither source nodes nor receiver nodes) placed regularly in this square region and connected by a high-bandwidth wired network. For each ordinary node v, we randomly pick k-1 nodes from the other n-1 ordinary nodes as the receivers of the multicast session at node v. The aggregated multicast capacity is defined as the total data rate of all multicast sessions in this hybrid network.