微信服务号

微信订阅号

2025-5-16- 17
Home > Archive>Volume 17, Issue 2, 2006 >175-184
PDF HTML XML Export Cite reminder
An Algorithm for Minimal Connected Cover Set Problem in Wireless Sensor Networks
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [20]
    • |
  • Related
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    Reducing power consumption to extend network lifetime is one of the most important challenges in designing wireless sensor networks. One promising approach to conserving system energy is to keep only a minimal number of sensors active and put others into low-powered sleep mode, while the active sensors can maintain the communication connectivity and cover the target region completely. The problem of computing such minimal active sensor set is NP-hard. In this paper, a centralized Voronoi tessellation (CVT) based approximate algorithm is proposed to construct a near optimal cover set of active sensors required to cover the target region completely. The communication graph induced by the cover set computed by CVT algorithm is connected if sensor’s communication radius is at least twice of its sensing radius. In case of sensor’s communication radius is smaller than twice of its sensing radius, a minimum spanning tree (MST) based connection algorithm is proposed to ensure the communication connectivity of the cover set. Finally, the performance of the proposed algorithm is evaluated through theoretical analysis and extensive numerical experiments. Experimental results show that the proposed algorithm outperforms the greedy algorithm in terms of the runtime and the size of the constructed connected cover set.

    Reference
    [1]Akyildiz IF,Su W,Sankarasubramaniam Y,Cayirci E.Wireless sensor networks:A survey.Computer Networks,2002,38(4):393-422.
    [2]Elson J,Estrin D.Sensor Networks:A Bridge to the Physical World.Norwell:Kluwer Academic Publishers,2004.3-20.
    [3]Ren FY,Huang HN,Lin C.Wireless sensor networks.Journal of Software,2003,14(7):1282-1291 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/14/1282.htm
    [4]Cui L,Ju HL,Miao Y,Li TP,Liu W,Zhao Z.Overview of wireless sensor networks.Journal of Computer Research and Development,2005,42(1):163-174 (in Chinese with English abstract).
    [5]Slijepcevic S,Potkonjak M.Power efficient organization of wireless sensor networks.In:Proc.of the Int'l Conf.on Communications.Helsinki:IEEE Communication Society,2001.472-476.
    [6]Abrams Z,Goel A,Plotkin S.Set k-cover algorithms for energy efficient monitoring in wireless sensor networks.In:Ramchandran K,Sztipanovits J,eds.Proc.of the 3rd Int'l Conf.on Information Processing in Sensor Networks.Berkeley:ACM Press,2004.424-432.
    [7]Ye F,Zhong G,Lu S,Zhang L.Peas:A robust energy conserving protocol for long-lived sensor networks.In:McKinley PK,Shatz S,eds.Proc.of the 23rd Int'l Conf.on Distributed Computing Systems.Providence:IEEE Press,2003.28-37.
    [8]Tian D,Georganas N.A coverage-preserving node scheduling scheme for large wireless sensor networks.In:Raghavendra CS,Sivalingam KM,eds.Proc.of the 1st ACM Int'l Workshop on Wireless Sensor Networks and Applications.Atlanta:ACM Press,2002.32-41.
    [9]Chen H,Wu H,Tzeng N.Grid-Based approach for working node selection in wireless sensor networks.In:Viginier P,ed.Proc.of the Int'l Conf.on Communications.Paris:IEEE Press,2004.3673-3678.
    [10]Carbunar B,Grama A,Vitek J,Carbunar O.Coverage preserving redundancy elimination in sensor networks.In:Znati T,Raghavendra CS,eds.Proc.of the 1st IEEE Conf.on Sensor and Ad Hoc Communications and Networks.Santa Clara:IEEE Press,2004.377-386.
    [11]Yah T,He T,Stankovic J.Differentiated surveillance service for sensor networks.In:Akyildiz IF,Estion D,eds.Proc.of the 1st Int'l Conf.on Embedded Networked Sensor Systems.Los Angels:ACM Press,2003.51-63.
    [12]Gupta H,Das SR,GU Q.Connected sensor cover:Self-Organization of sensor networks for efficient query execution.In:Gerla M,ed.Proc.of the ACM MobiHoc 2003.Annapolis:ACM Press,2003.189-200.
    [13]Bulusu N,Heidemann J,Estrin D.GPS-Less low cost outdoor localization for very small devices.IEEE Personal Communications Magazine,2000,7(5):28-34.
    [14]He H,Huang C,Blum BM,Stankovic JA,Abdelzaher TF.Range-Free localization schemes in large scale sensor networks.In:Johnson DB,ed.Proc.of the ACM MobiCom 2003.San Diego:ACM Press,2003.81-95.
    [15]Romer K,Zurich E.The lighthouse location system for smart dust.In:Siewiorek D,ed.Proc.of the 1st Int'l Conf.on Mobile Systems,Applications,and Services.San Francisco:ACM Press,2004.15-30.
    [16]Okabe A,Boots B,Sugihara K,Chiu S.Spatial Tessellations:Concepts and Applications of Voronoi Diagram.2nd ed.,New York:John Wiley & Sons,1999.
    [17]Hochbaum DS.Approximation Algorithms for NP-Hard Problems.Cambridge:PWS Publishing Company,1995.
    [18]Cormen TH,Leiserson CE,Rivest RL,Stein C.Introduction to Algorithms.2nd ed.,Cambridge:MIT Press,2001.
    [3]任丰原,黄海宁,林闯.无线传感器网络.软件学报,2003,14(7):1282-1291.http://www.jos.org.cn/1000-9825/14/1282.htm
    [4]崔莉,鞠海玲,苗勇,李天璞,刘巍,赵泽.无线传感器网络研究进展.计算机研究与发展,2005,42(1):163-174.
    Related
    Cited by
Get Citation

蒋杰,方力,张鹤颖,窦文华.无线传感器网络最小连通覆盖集问题求解算法.软件学报,2006,17(2):175-184

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 10,2005
  • Revised:August 03,2005
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2044987Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063