Variable radii connected sensor cover in sensor networks

ABSTRACT

One of the useful approaches to exploit redundancy in a sensor network is to keep active only a small subset of sensors that are sufficient to cover the region required to be monitored. The set of active sensors should also form a connected communication graph, so that they can autonomously respond to application queries and/or tasks. Such a set of active sensors is known as a connected sensor cover, and the problem of selecting a minimum connected sensor cover has been well studied when the transmission radius and sensing radius of each sensor is fixed. In this article, we address the problem of selecting a minimum energy-cost connected sensor cover, when each sensor node can vary its sensing and transmission radius; larger sensing or transmission radius entails higher energy cost.

For the aforesaid problem, we design various centralized and distributed algorithms, and compare their performance through extensive experiments. One of the designed centralized algorithms (called CGA) is shown to perform within an O(log n) factor of the optimal solution, where n is the size of the network. We have also designed a localized algorithm based on Voronoi diagrams which is empirically shown to perform very close to CGA and, due to its communication-efficiency, results in significantly prolonging the network lifetime. We also extend the aforementioned algorithms to incorporate fault tolerance. In particular, we show how to extend the algorithms to address the minimum energy-cost connected sensor k-cover problem, in which every point in the query region needs to be covered by at least k distinct active sensors. The CGA preserves the approximation bound in this case. We also propose a localized topology control scheme to preserve k-connectivity, and use it to extend the Voronoi-based approach to computing a minimum energy-cost k₁-connected k₂-cover. We study the performance of our proposed algorithms through extensive simulations.

REFERENCES

• 1: http://mathworld.wolfram.com/VoronoiDiagram.html.
• 2: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Message-optimal connected dominating sets in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513820]
• 3: Bahramgiri, M., Hajiaghayi, M., and Mirrokni, V. 2002. Fault-Tolerant and 3-dimensional distributed topology control algorithms in wireless multihop networks. In Proceedings of the International Conference on Computer Communications and Networks (IC3N).
• 4: Mario Čagalj , Jean-Pierre Hubaux , Christian Enz, Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570667]
• 5: Cardei, M., Wu, J., Lu, M., and Pervaiz, M. 2005. Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. In Proceedings of the IEEE International Conference on Wireless And Mobile Computing, Networking And Communications (WiMob).
• 6: Cartigny, J., Simplot, D., and Stojmenovic, I. 2003. Localized minimum-energy broadcasting in ad hoc networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).
• 7: Krishnendu Chakrabarty , S. Sitharama Iyengar , Hairong Qi , Eungchun Cho, Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks, IEEE Transactions on Computers, v.51 n.12, p.1448-1453, December 2002 [doi>10.1109/TC.2002.1146711]
• 8: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 9: Yuanzhu Peter Chen , Arthur L. Liestman, Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513821]
• 10: Fei Dai , Jie Wu, On Constructing k-Connected k-Dominating Set in Wireless Networks, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.81.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.302]
• 11: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 12: A. Dhawan , C. T. Vu , A. Zelikovsky , Y. Li , S. K. Prasad, Maximum Lifetime of Sensor Networks with Adjustable Sensing Range, Proceedings of the Seventh ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, p.285-289, June 19-20, 2006 [doi>10.1109/SNPD-SAWN.2006.46]
• 13: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 14: S. Guha , S. Khuller, Approximation Algorithms for Connected Dominating Sets, Algorithmica, v.20 n.4, p.374-387, April 1998 [doi>10.1007/PL00009201]
• 15: Himanshu Gupta , Samir R. Das , Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778438]
• 16: MohammadTaghi Hajiaghayi , Nicole Immorlica , Vahab S. Mirrokni, Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939016]
• 17: Chih-fan Hsin , Mingyan Liu, Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984685]
• 18: Jaromczyk, J. W. and Toussaint, G. T. 1992. Relative neighborhood graphs and their relatives. Proc. IEEE 80, 9.
• 19: Santosh Kumar , Ten H. Lai , József Balogh, On k-coverage in a mostly sleeping sensor network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023735]
• 20: Laouiti, A., Qayyum, A., and Viennot, L. 2002. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. In Proceedings of the Hawaii International Conference on System Sciences.
• 21: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, A cone-based distributed topology-control algorithm for wireless multi-hop networks, IEEE/ACM Transactions on Networking (TON), v.13 n.1, p.147-159, February 2005 [doi>10.1109/TNET.2004.842229]
• 22: Ning Li , Jennifer C. Hou, FLSS: a fault-tolerant topology control algorithm for wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023747]
• 23: Xiang-Yang Li , Peng-Jun Wan , Yu Wang , Chih-Wei Yi, Fault tolerant deployment and topology control in wireless networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778431]
• 24: Meguerdichian, S., Koushanfar, F., Potkonjak, M., and Srivastava, M. 2001. Coverage problems in wireless ad-hoc sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).
• 25: Seapahn Meguerdichian , Farinaz Koushanfar , Gang Qu , Miodrag Potkonjak, Exposure in wireless Ad-Hoc sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.139-150, July 2001, Rome, Italy [doi>10.1145/381677.381691]
• 26: Joseph O'Rourke, Computational geometry in C (2nd ed.), Cambridge University Press, New York, NY, 1998
• 27: Osiris. 2008. Osiris photoelectric sensors. http://schneider-electric.ca/www/en/products/sensors2000/html/osiris.htm.
• 28: Pattem, S., Poduri, S., and Krishnamachari, B. 2003. Energy-Quality tradeoffs for target tracking in wireless sensor networks. In Proceedings of the International Workshop on Information Processing in Sensor Networks (IPSN).
• 29: Shakkottai, S., Srikant, R., and Shroff, N. 2003. Unreliable sensor grids: Coverage, connectivity and diameter. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).
• 30: Slijepcevic, S. and Potkonjak, M. 2001. Power efficient organization of wireless sensor networks. In Proceedings of the International Conference on Communications (ICC).
• 31: Wan, P., Alzoubi, K., and Frieder, O. 2002. Distributed construction of connected dominating set in wireless ad hoc networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).
• 32: Wan, P., Calinescu, G., Li, X., and Frieder, O. 2001. Minimum-energy broadcast routing in static ad hoc wireless networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).
• 33: Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958496]
• 34: Wieselther, J. E., Nguyen, G. D., and Ephremides, A. 2000. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).
• 35: Wu, J. and Dai, F. 2003. Broadcasting in ad hoc networks based on self-pruning. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).
• 36: Wu, J. and Li, H. 2001. A dominating-set-based routing scheme in ad hoc wireless networks. Telecommun. Syst. J. 3.
• 37: Wu, J. and Yang, S. 2004. Coverage and connectivity in sensor networks with adjustable ranges. In Proceedings of the International Workshop on Mobile and Wireless Networking (MWN).
• 38: Ting Yan , Tian He , John A. Stankovic, Differentiated surveillance for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958498]
• 39: Fan Ye , Gary Zhong , Jesse Cheng , Songwu Lu , Lixia Zhang, PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.28, May 19-22, 2003
• 40: Younis, O., Ramasubramanian, S., and Krunz, M. 2007. Location-unaware sensing range assignment in sensor networks. In Proceedings of IFIP Networking Conference.
• 41: Zhou, Z., Das, S., and Gupta, H. 2004. Connected k-coverage problem in sensor networks. In Proceedings of the International Conference on Computer Communications and Networks (IC3N).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms

Keywords:
Topology control, connectivity, coverage, energy conservation, sensor networks