Search

Among the various ranging techniques, Radio Signal Strength (RSS) based approaches attract intensive research interests because of its low cost and wide applicability. RSS-based ranging is apt to be affected by the multipath phenomenon which allows the radio signals to reach the destination through multiple propagation paths. To address this issue, previous works try to profile the environment and refer this profile in run-time. In practical dynamic environments, however, the profile frequently changes and the painful retraining is needed. Rather than such static ways of profiling the environments, in this paper, we try to accommodate the environmental dynamics automatically in real-time. The key observation is that given a pair of nodes, the RSS at different spectrum channels will be different. This difference carries the valuable phase information of the radio signals. By analyzing these RSS values, we are able to identify the amplitude of signals solely from the Line-of-Sight (LOS) path. This LOS amplitude is a simple function of the path length (the physical distance). We find that the analysis is a typical non-linear curvature fitting problem that has no general routing algorithms. We prove this problem format is ill-conditioned which has no stable and trustable solutions. To deal with this issue, we further explore the practical considerations for the problem and reform it to a greatly improved conditioning shape. We solve the problem by numerical iterations and implement these ideas in a real-time indoor tracking system called MuD. MuD employs only three TelosB nodes as anchors. The experiment results show that in a dynamic environment where five people move around, the averaged localization error is 1 meter. Compared with the traditional RSS-based approaches in dynamic environment, the accuracy improves up to 10 times.

Cooperative caching is an efficient way to improve the performance of data access in mobile wireless networks, by cache nodes cooperatively caching copies of data items in their limited storage. With more demands on sharing a video or other data, especially for mobile phone games in an Internet-based Mobile Ad Hoc Network, the relations among data items become much more important than before. However, most of the existing works do not consider inherent relations among these data items. In this paper, we present a novel solution, Gossip-based Cooperative Caching (GosCC), to address the cache placement problem, considering the sequential relation among data items. Each mobile node stores the IDs of data items cached locally and the ID of the data item in use into its progress report. Each mobile node also makes use of these progress reports to determine whether a data item should be cached locally. These progress reports are propagated within the network in a gossip-based way. To improve user experience, GosCC aims to provide users with an uninterrupted data access service. Simulation results show that GosCC achieves better performance than the best one of the existing solutions, Benefit-based Data Caching, in terms of average interruption intervals and average interruption times, while sacrificing message cost to a certain degree.

Quorum-based schemes, e.g., GQS, can ensure asynchronous neighbors to discover each other within bounded time under low-duty-cycle operations. But they are tightly based on the assumption that duty cycles of devices fit some specific prefixed patterns. We tackle this problem by proposing a distributed quorum system to speed up the discovery.

Transceiver-free object tracking is to trace a moving object without carrying any communication device in an environment where the environment is pre-deployed with some monitoring nodes. Among all the tracking technologies, RF-based technology is an emerging research field facing many challenges. Although we proposed the original idea, until now there is no method achieving scalability without sacrificing latency and accuracy. In this paper, we put forward a real-time tracking system RASS, which can achieve this goal and is promising in the applications like the safeguard system. Our basic idea is to divide the tracking field into different areas, with adjacent areas using different communication channels. So the interference among different areas can be prevented. For each area, three communicating nodes are deployed on the ceiling as a regular triangle to monitor this area. In each triangle area, we use a Support Vector Regression (SVR) model to locate the object. This model simulates the relationship between the signal dynamics caused by the object and the object position. It not only considers the ideal case of signal dynamics caused by the object, but also utilizes their irregular information. As a result it can reach the tracking accuracy to around 1m by just using three nodes in a triangle area with 4m in each side. The experiments show that the tracking latency of the proposed RASS system is bounded by only about 0.26s. Our system scales well to a large deployment field without sacrificing the latency and accuracy.

Spectrum sensing is essential for the success of the cognitive radio networks. In traditional spectrum sensing schemes, Secondary Users (SUs) are responsible for the spectrum sensing which could be very time and resource consuming. It leads to a great deal of inefficiency in spectrum usage and introduces many practical challenges. To tackle these challenges and leverage the spectrum opportunity more efficiently, we propose a new system that provides a spectrum sensing service for SUs using dedicated wireless spectrum sensor networks (WSSNs). In this paper we focus on the sensing channel assignment problem in WSSNs and formulate the problem as a Sensing Effectiveness Maximization Problem (SEMP). We prove that SEMP is NP-complete under the ideal case, and show that the more challenges arises in real environments. To address the issues, we systematically study the design tradeoff and critical factors when maximizing the sensing effectiveness. Based on these study results we propose a Sensing Channel Assignment algorithm (SCAS). We conduct test-bed empirical investigations as well as comprehensive simulations. Performance evaluation results show that for both the scenarios of given deployments and manual deployments, SCAS is able to sense more channels to improve the sensing effectiveness. The improvement is up to 300% and the average improvement is 150% compared with other simple alternatives.

Interference is a critical issue in wireless communications. In a typical multiple-user environment, different users may severely interfere with each other. Coordination among users therefore is an indispensable part for interference management in wireless networks. It is known that coordination among multiple nodes is a costly operation taking a significant amount of valuable communication resource. In this paper, we have an interesting observation that by generating intended patterns, some simultaneous transmissions, i.e., "interference,” can be successfully decoded without degrading the effective throughput in original transmission. As such, an extra and "free” coordination channel can be built. Based on this idea, we propose a DC-MAC to leverage this "free” channel for efficient medium access in a multiple-user wireless network. We theoretically analyze the capacity of this channel under different environments with various modulation schemes. USRP2-based implementation experiments show that compared with the widely adopted CSMA, DC-MAC can improve the channel utilization efficiency by up to 250 percent.

Recent years have seen an increasing need of wireless networks in a mobile environment serving for more complex tasks and applications. Mobility becomes an indispensable factor of the system design and has been widely recognized as a general cause of packet loss. Though many works have been done on mobility study, to the best of our knowledge, they are mainly based on simulations or analytical studies that assume idealized link conditions. In this work, we experimentally investigate the nature of the error characteristics of mobility-induced packet losses at "chip-level" in IEEE 802.15.4. We believe this more understanding of mobility-induced packet losses can bring great potential benefits for further study on channel coding, routing and protocol design. Toward this end, we design and implement an efficient algorithm to distinguish mobility-induced packet losses from other packet losses of static environments such as attenuation. Our algorithm is greatly advantaged as it needs no training data even when environment changes. Collecting three corrupted packets is sufficient to obtain a satisfactory performance. This feature makes our design in particular suitable for dynamic and mobile environments, allowing real-time mobility induced loss detection in an online manner. Experiments based on GNU Radio testbed show that our algorithm can provide an accuracy of up to 96%.

Spectrum sensing is one of the key enabling technologies in Cognitive Radio Networks (CRNs). In CRNs, secondary users (SUs) are allowed to exploit the spectrum opportunities by sensing and accessing the spectrum, which exhibit many critical limitations in practical environments. In this paper, we propose a new sensing service model that uses dedicated wireless spectrum sensor networks (WSSN) for spectrum sensing. The major challenge in WSSN is the design of data fusion, for which the traditional fusion scheme will produce a large amount of errors. We formulate the problem as a boundary detection problem with notable unknown erroneous inputs. To solve the problem, we propose a novel cooperative boundary detection scheme that intelligently incorporates the cooperative spectrum sensing concept and the recent advances in support vector machine (SVM). Cooperative boundary detection consists of two major components, a declaration calibration algorithm and a boundary derivation algorithm. We prove that cooperative spectrum sensing can asymptotically approach the optimal solution. A prototype system as well as simulation experiments show that compared with the traditional approaches, cooperative boundary detection can reduce the errors by up to 95% with an average reduction about 85%.

The growing importance of operations such as identification, location sensing and object tracking has led to increasing interests in contact less Radio Frequency Identification (RFID) systems. Enjoying the low cost of RFID tags, modern RFID systems tend to be deployed for large-scale mobile objects. Both the theoretical and experimental results suggest that when tags are mobile and with large numbers, two classical MAC layer collision-arbitration protocols, slotted ALOHA and Tree-traversal, do not satisfy the scalability and time-efficiency requirements of many applications. To address this problem, we propose Adaptively Splitting-based Arbitration Protocol (ASAP), a scheme that provides low-latency RFID identification and has stable performance for massive RFID networks. Theoretical analysis and experimental evaluation show that ASAP outperforms most existing collision-arbitration solutions. ASAP is efficient for both small and large deployment of RFID tags, in terms of time and energy cost. Hence it can benefit dynamic and large-scale RFID systems.

Sensing coverage is essential for most applications in wireless networks. In traditional coverage problem study, the disk coverage model has been widely applied because of its simplicity. Though notable recent works point out that the disk model has many critical limitations when applied in practice, few successful works have been conducted to comprehensively study the issue. Motivated by this, in this paper we propose a new coverage model called T-R model. T-R model is derived from a real application of transceiver-free object detection. Compared with the traditional disk model, T-R model is able to describe many new coverage features such as the probabilistic coverage, the link-centric coverage units and the correlations between multiple coverage units. These new capabilities make T-R model a better abstraction of individual sensors. To evaluate the performance of T-R model, we conduct comprehensive empirical studies based on a test-bed of 30 telosB nodes. Experimental results show that the TR model can adequately describe the sensing behavior in the transceiver-free object detection applications. The average error between the model and the reality is only 8%. Moreover, T-R model presents attractive flexibility, making it more appropriate for general coverage problem studies than the transceiver-free object detection.

Coverage is a fundamental problem in Wireless Sensor Networks (WSNs). Existing studies on this topic focus on 2D ideal plane coverage and 3D full space coverage. The 3D surface of a targeted Field of Interest is complex in many real world applications; and yet, existing studies on coverage do not produce practical results. In this paper, we propose a new coverage model called surface coverage. In surface coverage, the targeted Field of Interest is a complex surface in 3D space and sensors can be deployed only on the surface. We show that existing 2D plane coverage is merely a special case of surface coverage. Simulations point out that existing sensor deployment schemes for a 2D plane cannot be directly applied to surface coverage cases. In this paper, we target two problems assuming cases of surface coverage to be true. One, under stochastic deployment, how many sensors are needed to reach a certain expected coverage ratio? Two, if sensor deployment can be planned, what is the optimal deployment strategy with guaranteed full coverage with the least number of sensors? We show that the latter problem is NP-complete and propose three approximation algorithms. We further prove that these algorithms have a provable approximation ratio. We also conduct comprehensive simulations to evaluate the performance of the proposed algorithms.

Travel route analysis and prediction are essential for the success of many applications in Vehicular Ad-hoc Networks (VANETs). Yet it is quit challenging to make accuracy route prediction for general vehicles in urban settings due to several practical issues such as very complicated traffic networks, the highly dynamic real-time traffic conditions and their interaction with drivers’ route selections. In this paper, we undertake a systematic study on the vehicular route prediction in urban environments where the traffic conditions on complicated road networks keep changing from time to time. Inspired by the observation that a vehicle often has its own route selection flavor when traversing between its sources and destinations, we define a mobility pattern as a consecutive series of road segment selections that exhibit frequent appearance along all the itineraries of the vehicle. We further leverage Variable-order Markov Models (VMMs) to mine mobility patterns from the real taxi GPS trace data collected in Shanghai. In addition, considering the tremendous impact of dynamic traffic conditions to the accuracy of route prediction, we deploy multiple VMMs differentiating different traffic conditions in daytime. Our extensive trace-driven simulation results show that notable patterns can be mined from routes of common vehicles though they usually have no constraints when selecting routes. Given a specific taxi, around 40% next road segments are predictable using our model with a confidence weight of 60%. With multiple VMMs a high route prediction accuracy is achievable from the real traffic trace.

In many mission critical applications, one of the central tasks is to obtain aggregate values, such as AVERAGE and SUM, based on which critical conditions can be detected. Immediate measures can subsequently be taken to remove associated risks timely. However, there is no successful work for detecting such critical events energy efficiently. In this paper we propose a novel approach. A fully distributed algorithm is designed, in which each sensor makes the decision purely locally. The elegance of the algorithm is that a global network behavior can be presented based on individual node actions, without a central authority to coordinate. This effectively reduces unnecessary sensor reports for network-wide coordination. Our proposed algorithm, called MEES, has the property of a zero event-missing rate, i.e., critical events are always detected. There is a trade-off between the energy cost and the false positive. Simulation experimental results show that MEES is more appropriate for large-scale WSNs with highly dynamic sensing environments. The energy cost can be saved up to 70%.

Having an ID being unique within the application domain for each sensor node is the basic assumption in many WSN applications. In traditional assignments, fixed-length ID schemes, which are severely limited by scalability, flexibility and energy efficiency, are adopted. To solve these problems, we propose a novel variable-length ID scheme that allows different nodes to have different ID lengths. To realize this idea, we propose a fully localized ID assignment algorithm called emphself-organized ID assignment (SIDA). SIDA presents great potential on scalability, flexibility and energy efficiency by enabling online ID assignment and various optimizations according to different communication paradigms. Analytical and simulation results show that SIDA has a comparable static ID length while the accumulated communication overhead for multi-hop transmissions can be saved by 20%; the control overhead of the new deployment assignment can be reduced to about 30% compared with fixed-length schemes.

Reliable transmission service is in dire need for many applications in wireless sensor networks (WSNs). Most existing routing protocols however, seriously suffer from low end-to-end success rates in real deployments. Through extensive experiments on a test-bed of Mica2 nodes, we identify three key problems that hinder the reliable packet delivery. In order to address these problems and therefore to provide a reliability-oriented transmission service, we propose a novel in-middle recovery mechanism that fills the gap between the traditional per-hop recovery and end-to-end recovery mechanisms. To realize such an idea, we design and implement proliferation routing that leverages randomized dispersity and reproduction. The distinctive feature of proliferation routing is its great flexibility. Not only can it be applied with any medium access control (MAC) protocol and routing metric, but also a desired service quality can be effectively derived by controlling the system parameters. Such a feature is revealed by theoretical analysis and confirmed by implementation and simulation experiments. In a specific experiment setup, proliferation routing can increase the end-to-end transmission success rate up to 70% compared with the well-known hop-based routing and flooding.

The rapid advancement in wireless communications and mobile computing devices has opened a wide door for developing interesting mobile peer-to-peer multi-player games (MMGs). In this paper we study an important problem of game state update in MMGs. Based on the network coding theory, we design the shift coding algorithm. Shift coding is running on a finely regulated ring overlay and lets each node exchange coded state information with its two immediate neighbors. After a few rounds of exchange, every node is guaranteed to receive the state information of all the other game members. The results of experimental results have shown that shift coding can significantly reduce network traffic under various network configurations.

In this paper we address the problem of energy-efficient event detection in wireless sensor networks (WSNs). Duty cycling is a fundamental approach to conserving energy in WSNs. However, it brings challenges to event detection in the sense that an event may be undetected or undergo a certain delay before it is detected, in particular when sensors are low duty-cycled. We investigate the fundamental relationship between event detection and energy efficiency. Based on a simplified network model, we quantify event detection performance by deriving the closed forms of detection delay and detectability. We also characterize the intrinsic tradeoff that exists between detection performance and system lifetime, which helps flexible design decisions for WSNs. In addition, we propose a completely localized algorithm, CAS, to cooperatively determine sensor wakeups. Without relying on location information, CAS is easy to implement and scalable to network density. Theoretical bounds of event detection are also studied to facilitate the comparative study. Comprehensive experiments are conducted and results demonstrate that CAS significantly improves detection performance.

In wireless mobile ad hoc networks (MANETs), energy is a crucial resource. Topology control technology allows network nodes to reduce their transmission power while preserving the network connectivity. A MANET is a non-cooperative system so that only when a node earns its payment, which can cover its cost, the cooperation can be stimulated. We design a truthful topology control mechanism (TRUECON) for MANETs to induce the selfish, but rational, network nodes to collaborate. Truth-telling is a dominant strategy in TRUECON. A node needs to reveal its true value in order to obtain the maximum expected utility. We prove the overpayment of TRUECON has a bound depending on different radio propagation models

Load balancing is a key technology to achieve high performance as well as high reliability. Most of traditional approaches are based on a critical assumption that the service qualities of channels are already known. With such information, they attempted to preventively disperse workloads to attain fairness and therefore high efficiency. However, in practice, such information is difficult to obtain, especially when dispersion is performed at high-level layers. In this paper, we propose a novel scheme Dynamic dispersion frAMework (DAM), to adoptively disperse the traffic. Based on collected statistics, DAM dynamically adjusts the dispersion strategy to achieve fairness in terms of real capabilities of channels. Our experimental results show that DAM provides an accurate dispersion strategy compared with an offline optimal solution. The other advantage of DAM is that it is transparent to both the user and the server.

In wireless sensor networks, it is critical to provide the data delivery services between sensors and the data collection unit (called sink). Some of the existing approaches require location or II) information which is quite expensive. For those without location or ID information, the usage of the collected information is rather limited. In this paper, we propose a geography-free coordinate system, called GREENWIS, to assist routing. In GREENWIS, sensors are identified by a 4-tuple with which messages are universally transmitted. Our analysis and experiments show that GREENWIS is reliable and power efficient compared with existing approaches.

The emerging peer-to-peer (P2P) model has gained significant attention due to its many unique features in supporting file sharing among a huge number of networked users. However, the mechanism of peers randomly choosing logical neighbors without any knowledge about underlying physical topology can cause a serious topology mismatching between the P2P overlay network and the physical underlying network. Adaptive overlay topology optimization and location-aware topology matching are two techniques aiming at alleviating the mismatching problem and reducing the unnecessary traffic and average query response time of unstructured P2P systems while still retaining the search scope. In this paper we compare the performance of these two approaches through simulation studies.