WSN - Analysis of fundamental behaviors with respect to coverage, connectivity, liftime and power analysis

1. Overview
2. Research Agenda
3. Participants
4. Major Publications
5. Funding Source
6. Related Links
   

Overview

Driven by advances in MEMS micro-sensors, wireless networking, and embedded processing, ad-hoc networks of devices and sensors with (limited) sensing and wireless communication capabilities are becoming increasingly available for commercial and military applications such as environmental monitoring (e.g., traffic, habitat, security), industrial sensing and diagnostics (e.g., factory, appliances), critical infrastructure protection (e.g., power grids, water distribution, waste disposal), and situational awareness for battlefield applications. Much has been written about how, once deployed, these wireless networks will affect the way we work, learn, interact, organize, get entertained, fight wars, and recover from disasters.

This interest in such types of networks has actually opened up new research venues and led to a fair amount of research activities in the areas of sensor tasking and control, tracking and localization, in-network processing, sensor data fusion, distributed data bases, communication protocol design, and systems building and prototyping. However, comparatively much less work has been carried out on the fundamental concepts related to wireless sensor networks, e.g., the asymptotic behaviors of these networks with respect to network coverage, connectivity, scalabiity, longevity, and critical power required to maintain connectivity.

In this project, we are devoted to the study of performance limits for wireless sensor networks with respect to network coverage, connectivity, lifetime, critical power, as well as to the design of protocols capable of approaching those performance limits. Take the property of network connectivity as an example. On the one hand, we are investigating in an analytic framework critical conditions (such as the transmission range (and hence the transmission power), the number of neighbors, or the node density) in order to ensure connectivity with high probability, and how the critical conditions scales as the number of devices/sensors increases. On the other hand, we are designing distributed and localized algorithms (and their corresponding protocols) that minimize, for example, the total transmission power of all wireless nodes while maintaining connectivity, where by ``localized,'' we mean the algorithms do not rely on global information that needs to be relayed by nodes that are multiple hops away. This feature is especially important in devising practical algorithms that will not incur excessive message exchange and can be readily deployed in wireless sensor networks.

Research Agenda (click here for details)

Irregardless of the quantity/property to analyze, the extreme resource constraints under which wireless sensor networks must operate strongly calls for an understanding of fundamental performance limits of such networks, for those can provide valuable insights into what designs make sense, and can help identify areas in which theory promises performance much better than that attained by existing designs. In this regard, we are carrying out several tasks along the following research thrusts:

1. Coverage and connectivity
2. Lifetime analysis
3. Topology control and management

Participants

• Ning Li (Ph.D. 2005)
• Honghai Zhang (Ph.D. 2005)

Major Publications

1. Ning Li, Jennifer C. Hou, and Lui Sha, ``Design and analysis of a MST-based distributed topology control algorithm for wireless ad-hoc networks,'' Proc. IEEE INFOCOM 2003, April 2003 (acceptance ratio = ~21%).
2. Honghai Zhang and Jennifer C. Hou, ``On deriving the upper bound of alpha-lifetime for large sensor networks,'' Proc. of ACM Mobihoc 2004, May 2004 (acceptance ratio ~ 10%).
3. Ning Li and Jennifer C. Hou, ``Topology control in heterogeneous wireless networks: problems and solutions,'' Proc. of IEEE INFOCOM 2004, March 2004 (acceptance ratio = 18%).
4. Honghai Zhang and Jennifer C. Hou, "Maintaining sensing coverage and connectivity in large sensor networks," NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, February 2004 (invited paper).
5. Ning Li and Jennifer C. Hou, "FLSS: a fault-tolerant topology cntrol algorithm for wireless networks," Proc. ACM Mobicom, September 2004 (acceptance ratio = ~9%).
6. Honghai Zhang and Jennifer C. Hou, "Maintaining sensing coverage and connectivity in large sensor networks," Wireless Ad Hoc and Sensor Networks: An International Journal, Vol. 1, No. 1-2, pp. 89--123, January 2005.
7. Honghai Zhang and Jennifer C. Hou, "On the critical total power for asymptotic k-connectivity in wireless networks," Proc. IEEE INFOCOM, Miami, Florida, March 2005 (acceptance ratio = 17%).
8. Honghai Zhang and Jennifer C. Hou, ``Capacity of wireless ad-hoc networks under ultra wide band with power constraints,'' Proc. IEEE INFOCOM, Miami, Florida, March 2005 (acceptance ratio = 17%).
9. Ning Li, Jennifer C. Hou and Lui Sha, ``Design and analysis of a MST-based distributed topology control algorithm for wireless ad-hoc networks,'' IEEE Trans. on Wireless Communications, Vol. 4, No. 3, pp. 1195-1207, May 2005.
10. Honghai Zhang and Jennifer C. Hou, ``Maximizing alpha-Lifetime for Wireless Sensor Networks,'' Proc. of Third Int'l Workshop on Measurement, Modelling, and Performance Analysis of Wireless Sensor Networks (SenMetrics 2005), July 2005 (invited paper).
11. Ning Li, "Topology control for multi-hop wireless networks," Ph.D. Thesis, Department of Computer Science, University of Illinois at Urbana Champaign, July 2005.
12. Ning Li and Jennifer C. Hou, ``Improving connectivity of wireless ad-hoc networks,'' Proc. of ACM 2nd International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous 2005), July 2005 (acceptance ratio = 28%).
13. Honghai Zhang, "An understanding of fundamental performance limits in wireless sensor networks," Ph.D. Thesis, Department of Computer Science, University of Illinois at Urbana Champaign, August 2005.
14. Honghai Zhang and Jennifer C. Hou, ``On deriving the upper bound of alpha-lifetime for large sensor networks,'' ACM Trans. on Sensor Networks, Vol. 1, No. 2, pp. 272--300, November 2005.
15. Ning Li and Jennifer C. Hou, ``Localized topology control algorithms for heterogeneous wireless networks,'' IEEE/ACM Trans. on Networking, Vol. 13, No. 6, pp. 1313--1324, December 2005.
16. Jennifer C. Hou, Ivan Stojmenovic, and Ning Li, "Topology construction and maintence in sensor networks," Handbook of Sensor Networks: Algorithms and Architectures, pp. 311-342, Ivan Stojmenovic (Ed), John Wiley and Sons, 2005.
17. Ning Li and Jennifer C. Hou, ``Topology control in wireless sensor networks,'' Combinatorial Optimization in Communication Networks, (ISBN: 0-387-29025-7), Maggie Cheng, Yingshu Li, Ding-Zhu Du (Eds), Springer Publishers, 2006.
18. Honghai Zhang and Jennifer C. Hou, "Is deterministic deployment worse than random deployment for wireless sensor networks," Proc. IEEE INFOCOM, March 2006 (acceptance ratio = 18%)
.
19. Ning Li and Jennifer C. Hou, "Localized fault-tolerant topology control in wireless ad hoc networks," IEEE Trans. on Parallel and Distributed Systems, special issue on Localized communication and topology protocols for ad hoc networks, Vol. 17, No. 4, pp. 307--320, April 2006.
20. Honghai Zhang and Jennifer C. Hou, "An algorithm for maximizing alpha-lifetime for wireless sensor networks," International Journal of Sensor Networks (IJSNet), Vol. 1, No. 1/2, pp. 64--71, June 2006 (invited).
21. Honghai Zhang and Jennifer C. Hou, "Maintaining sensing coverage and connectivity in large sensor networks," Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Network, Jie Wu (Ed), Chapter 28, pp. 453-475, Auerbach Publications, 2006.
22. Honghai Zhang and Jennifer C. Hou, "On the asymptotic minimum energy and its implication on deriving the capacity of wireless networks," ACM/IEEE Trans. on Networking, to appear (accepted in August 2006).
23. Ning Li and Jennifer C. Hou, "Improving connectivity of wireless ad-hoc networks," Wireless Networks, to appear (accepted in September 2006).
24. Honghai Zhang and Jennifer C. Hou, "Asymptotic critical total power for k-connectivity of wireless networks," IEEE/ACM Trans. on Networking, to appear (accepted in September 2006).

Funding Source

• NSF Special Projects in Networking
• DoD Multiple University Research Initiatives/ONR

Related Links

1. Prof. Massimo Franceschetti, Department of Electrical and Computer Engineering, University of California, San Diego. He is interested in the broad intellectual theme of information science of complex networks and systems. Specific topics include Phase transitions and critical phenomena, Random Networks, Wave propagation in random media, Wireless communication.
2. Prof. Xiang-Yang Li, Department of Computer Science, Illinois Institute of Technology. His research in wireless networks includes topology control, power-efficient broadcasting, application of computational geometry, ad-hoc routing, coverage in sensor networks, etc
3. Prof. P. R. Kumar, Department of Electrical Engineering, University of Illinois at Urbana-Champaign. His research in wireless networks includes network capacity, MAC protocol design and analysis, power control, clustering, application of information theory, etc.
4. Prof. Mathew D. Penrose Department of Department of Mathematical Sciences, University of Bath, England. His interests include geometric probability, random graphs and stochastic analysis.
5. Dr. Paolo Santi,Istituto di Informatica e Telematica del CNR, Italy
6. Prof. Sergio Servetto and his Communication Networks Research Group, School of Electrical and Computer Engineering, Cornell University. His research in wireless networks include sensor broadcast, sensor reachback, routing, capacity, stability, etc.
7. Prof. Sanjay Shakkottai, Department of Electrical and Computer Engineering at the University of Texas at Austin. His research include wireless Ad-hoc and sensor networks, Scheduling and QoS in wireless networks, Congestion control in the Internet, Resource allocation for heterogeneous networks, etc.
8. Prof. Ivan Stojmenovic, School of Information Technology and Engineering, University of Ottawa. His research in wireless networks includes power-efficient broadcasting, clustering, routing, media access, scheduling, etc.
9. Prof. Peng-Jun Wan , Department of Computer Science, Illinois Institute of Technology. His research interests include wireless networks, optical networks and algorithm design and analysis
10. Prof. Roger Wattenhofer , Distributed Computing Group, Swiss Federal Institute of Technology, Zurich, Switzerland



---

Detailed Description of Research Agenda

1. Coverage and connectivity

We address the issues of maintaining sensing coverage and connectivity by keeping a minimal number of sensor nodes in the active mode in wireless sensor networks. We investigate the relationship between coverage and connectivity by solving the following two sub-problems. First, we prove that if the radio range is at least twice of the sensing range, a complete coverage of a convex area implies connectivity among the working set of nodes. Second, we derive, under the ideal case in which node density is sufficiently high, a set of optimality conditions under which a subset of working sensor nodes can be chosen for full coverage. For example, we show (a) if all sensor nodes completely cover a region R, then minimizing the number of working nodes is equivalent to minimizing the overlap of sensing areas of all the nodes; and (b) under the assumption that different nodes have different sensing ranges, to cover one crossing point of two disks with the minimal overlap, the three disks should be placed such that (Figure 1). If disk A and B are already fixed, disk C should be placed such that










Based on the optimality conditions, we then devise a decentralized density control algorithm, Optimal Geographical Density Control (OGDC), for density control in large scale sensor networks. The OGDC algorithm is fully localized and can maintain coverage as well as connectivity, irregardless of the relationship between the radio range and the sensing range. Ns-2 simulation shows that OGDC outperforms the PEAS algorithm, the CCP algorithm, a hexagon-based GAF-like algorithm, and the sponsor area algorithm with respect to the number of working nodes needed (sometimes with a 50% improvement), and achieves almost the same coverage as the best algorithm. (For example, Figure 2 gives the number of working nodes and coverage versus the number of sensor nodes deployed in the network. Both metrics are measured after the density control process completes. Under most cases, OGDC takes less than 1 seconds to perform density control in each round, while PEAS and CCP may take up to 100 seconds. Moreover, OGDC needs only half as many nodes to operate in the active mode as compared to the hexagon-based GAF-like algorithm, but achieves almost the same coverage (in most cases OGDC achieves more than 99.5% coverage).








2. Lifetime

We explore the fundamental limits of sensor network lifetime that all algorithms can possibly achieve. The derivation is based on the theory of coverage processes and made under the assumptions that the locations of the deployed sensors form a Poisson point process in a square region and that sensor nodes only fail because of power depletion (but not of malicious destruction). First, we prove that a necessary and sufficient condition of complete k-coverage of a square region with side length (in the almost surely sense) is the density of the nodes where as Consequently given such a density and , where , the lifetime upper bound is kT as , where T is a single sensor lifetime. Second, we derive, given a certain density in a finite (but still large) region, the upper bound of the lifetime under the scenario that only -portion of the region is required to be covered. In this scenario, we derive two upper bounds: one holds universally for any possible algorithm, and the other is targeted for algorithms that attempt to completely cover the region initially and gradually reduce the coverage ratio, until it drops below a certain threshold .

We also carry out a simulation study to validate the derived upper bounds of network lifetime and to study to what extent they can be applied to networks in which the assumptions do not hold. Simulation results indicate that the derived upper bounds apply not only to sensor networks of large sizes and with homogeneous nodal distributions, but also to networks of small sizes and with non-homogeneous (e.g., clustering) nodal distributions, although in the latter cases the derived upper bounds may not be tight.

With our derivation and simulation results, we will be able to answer several important questions, e.g., given the lifetime T of a single sensor node, how many sensor nodes (or the sensor density) have to be deployed in a region, in order to continuously monitor the region for a period of kT. We also observe that although it is, in general, desirable to deploy a sensor network of high density to achieve a large lifetime per unit of nodal density, the increase in the lifetime per unit of nodal density becomes marginal when the density exceeds certain threshold. The overhead incurred in maintaining coverage in a distributed manner dominates when the sensor density becomes high.

3. Topology control and management

Topology control and management -- how to determine the transmission power of each node so as to maintain network connectivity while consuming the minimum possible power -- has emerged to be one of the most important issues in wireless multi-hop networks. Instead of transmitting using the maximum possible power, nodes in a wireless multi-hop network collaboratively determine their transmission power and define the topology of the wireless network by the neighbor relation under certain criteria. This is in contrast to the "traditional" network in which each node transmits using its maximum transmission power and the topology is built implicitly by routing protocols (that update their routing caches as timely as possible) without considering the power issue. Not until recently has the issue of topology/power control with respect to maintaining network connectivity, optimizing network spatial reuse, and mitigating MAC-level interference attracted much attention.

The importance of topology control lies in the fact that it critically affects the system performance in several ways. For one, it affects network spatial reuse and hence the traffic carrying capacity. Choosing too large a power level results in excessive interference, while choosing too small a power level may result in a disconnected network. Power control also effects the energy usage of communication, and thus impacts on battery life, a critical resource in many mobile applications. In addition, topology control also impacts on contention for the medium. Collisions can be mitigated as much as possible by choosing the smallest transmission power subject to maintaining network connectivity.

In this part of the project, we have carried out the following R&D tasks:

(a) Under the assumption of homogeneous wireless nodes all with uniform transmission ranges, we devise a Minimum Spanning Tree (MST) based topology control algorithm, called Local Minimum Spanning Tree (LMST), for multi-hop wireless networks with limited mobility. The topology is constructed by each node building its local MST independently (with the use of information locally collected) and keeping only one-hop on-tree nodes as neighbors. There are several salient features of LMST: (i) the topology constructed under LMST preserves the network connectivity, (ii) the degree of any node in the resulting topology is bounded by 6; and (iii) the resulting topology can be converted into one with only bi-directional links (after removal of uni-directional links). Feature (ii) is desirable because a small node degree reduces the MAC-level contention and interference. The capability of forming a topology that consists of only bi-directional links is important for link level acknowledgments, and packet transmissions /retransmissions over the unreliable wire less medium. Bi-directional links are also important for floor acquisition mechanisms such as RTS/CTS in IEEE 802.11.



(b) The assumption of homogeneous wireless nodes all with uniform transmission ranges does not always hold in practice since even devices of the same type may have slightly different maximal transmission power. Unfortunately most existing algorithms cannot be directly applied to heterogeneous wireless multi-hop networks in which the maximal transmission power of each node may be different. Hence, we proceed to explore the connectivity and bi-directionality issue in the heterogeneous wireless networks.

We propose two localized topology control algorithms for heterogeneous wireless multi-hop networks with non-uniform transmission ranges: Directed Relative Neighborhood Graph (DRNG) and Directed Local Spanning Subgrap (DLSS). In both algorithms, the topology is constructed by having each node build its neighbor set and adjust its transmission power based on the locally collected information. We are able to prove that (1) the topology derived under DLSS is a subgraph of that derived by DRNG; (2) the topology derived under both DRNG and DLSS preserves network connectivity, i.e., if the original topology generated by having every node use its maximal transmission power is strongly connected, then the topology generated by either DRNG or DLSS is also strongly connected; (3) the out degree of any node in the topology by DLSS is bounded by a constant, while the out degree of nodes in the topology by DRNG may be unbounded; and (4) the topology generated by DRNG and DLSS preserves network bi-directionality, i.e., if the original topology by having every node use its maximal transmission power is bi-directional, then the topology generated by either DRNG or DLSS is also bi-directional after some simple operations.

(c) By adjusting the transmission power and reducing the number of links in the network, topology control actually decreases the degree of network connectivity, and hence the derived topology is more susceptible to node failures/departures. This situation can be mitigated if we take fault tolerance into consideration. As such, we present a centralized greedy algorithm, Fault-tolerant Global Spanning Subgraph (FGSS_k), which can preserve the k-vertex connectivity and is Min-Max optimal. (The latter property is critical to prolong the network lifetime.) Based on this algorithm, we then propose Fault-tolerant Local Spanning Subgraph (FLSS_k) for topology control in wireless networks. FLSS_k is a fully localized algorithm where each node operates on the information that can be collected locally. This enables FLSS_k to be more adaptive to to topology changes. We prove that FLSS_k preserves the k-vertex connectivity and maintains bi-directionality for all links in the topology, while reducing the transmission power and improving the network capacity. We also prove that FLSS_k is Min-Max optimal among all strictly localized algorithms.

Finally we examine the impact of several widely used assumptions in topology control on the practicality of FGSS_k and FLSS_k, including uniform transmission power, obstacle-free communication channel, capability to obtain position information, and perfect antenna pattern, and show how to relax these assumptions under FGSS_k and FLSS_k.