Coordinated Power Management under Sensing and Communication Constraints in Sensor Networks
Energy is a paramount concern in wireless sensor networks that must achieve long lifetimes (from several months to several years) while operating on limited battery energy. A promising approach to reduce energy consumption of sensor networks is to dynamically control the duty cycles of sensors. In such a approach, a small subset of active sensors remain awake all the time to maintain continuous services of the network while all other sensors are scheduled to sleep or enter a power-saving mode to save energy. The energy management problem is especially challenging in many mission-critical sensor networks that must maintain certain performance constraints throughout their operational lifetime. Specifically, wireless sensor networks must satisfy both sensing and communication constraints simultaneously.
Sensing constraints: Since the primary purpose of sensor networks is to monitor the environment, a sensor network must maintain sufficient sensing coverage over the region of interest even when it operates in an energy conservation mode. The requirement of sensing coverage are tightly coupled with distributed sensing applications. 1) A application may require a certain degree of coverage, i.e., every point of some region must be sensed by a certain number of sensors. Different applications require different degrees of sensing coverage. 2) In more realistic sensing models, the sensing coverage can be expressed by the event detection probability and the false alarm rate. For example, a distributed monitoring application may require that the minimal event detection probability over a geographic region to be above certain threshold while the the maximal system false alarm rate below another threshold.
Communication constraints: Meanwhile, both data fusion among multiple sensors and data services for end-users may have quality of service requirements on the communication network. The minimum constraint is that the subset composed of active nodes must guarantee connectivity whenever they need to communicate. Furthermore, end-to-end communication delay are often important to mission-critical applications. For example, a firefighter fighting a wild fire may request periodic updates of a temperature map around his location to maintain awareness of the fire condition. Late data updates may endanger the fire fighter.
Our research results include (see publications for newer results):
Integrated coverage and connectivity configuration: We designed an efficient energy conservation protocol called CCP that selects a small number of active nodes to maintain the sensing coverage and connectivity of a sensor network while scheduling other nodes to sleep. CCP can dynamically configure a sensor network to different degrees of coverage requested by applications. Through geometric analysis and simulation results, we show that CCP can maintain robust sensing coverage and network connectivity when communication range is at least twice sensing range. We integrated CCP with SPAN from MIT to provide both coverage and connectivity guarantees when communication range is shorter than twice sensing range.
Coverage maintenance based on a realistic sensing model: We designed a coverage maintenance protocol called Co-Grid that adopts a distributed detection model based on data fusion that is more consistent with many distributed sensing applications than the simple disc sensing model. Co-Grid organizes the network into coordinating fusion groups located on overlapping virtual grids. Through coordination among neighboring fusion groups, Co-Grid can achieve comparable number of active nodes as a centralized algorithm, while reducing the network configuration time by orders of magnitude.
Impact of coverage on greedy geographic routing algorithms: Sensing coverage imposes certain network properties (e.g., density, node distribution) that have a fundamental impact on the communication performance of the underlying sensor network. We derived theoretical upper bounds on the network dilation of sensing-covered networks under existing greedy geographic routing algorithms. Furthermore, we proposed a new greedy geographic routing algorithm called Bounded Voronoi Greedy Forwarding (BVGF) that allows sensing-covered networks to achieve an asymptotic network dilation lower than 4.62 as long as the communication range is at least twice the sensing range. Our results show that simple greedy geographic routing is an effective routing scheme in many sensing-covered networks.
Publications
Guoliang Xing; Chenyang Lu; Robert Pless; Qingfeng Huang, Impact of Sensing Coverage on Greedy Geographic Routing Algorithms, IEEE Transactions on Parallel and Distributed Systems (TPDS), special issue on Localized communication and topology protocols for ad hoc networks, April, 2006, to appear.
Guoliang Xing, Xiaorui Wang, Yuanfang Zhang, Chenyang Lu, Robert Pless, and Christopher Gill, "Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks," ACM Transactions on Sensor Networks, 1 (1), 2005.
Guoliang Xing, Chenyang Lu, Robert Pless, and Qingfeng Huang, "On Greedy Geographic Routing Algorithms in Sensing-Covered Networks," ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'04), Tokyo, Japan, May 2004.
Guoliang Xing, Chenyang Lu, Robert Pless, and Joseph A. O'Sullivan, "Co-Grid: An Efficient Coverage Maintenance Protocol for Distributed Sensor Networks," International Symposium on Information Processing in Sensor Networks (IPSN'04), Berkeley, CA, April 2004.
Xiaorui Wang, Guoliang Xing, Yuanfang Zhang, Chenyang Lu, Robert Pless, and Christopher Gill, "Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks," First ACM Conference on Embedded Networked Sensor Systems (SenSys'03), Los Angeles, CA, November 2003.
People
Prof. Chenyang Lu
Prof. Robert Pless
Downloads
We implemented CCP in ns2 network simulator based on the SPAN protocol from MIT. The ns2 code of CCP can be downloaded at here. The code is close to (but not exactly is) the snapshot of our SenSys paper. The ns-2 code of SPAN can be downloaded at this website.
Last updated on 02/03/2006