无线传感器网络最小覆盖集的贪婪近似算法
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.60602066 (国家自然科学基金); the Guangdong Provincial Natural Science Foundation of China under Grant No.2008254 (广东省自然科学基金); the Science and Technology Planning Project of Guangdong Province of China under Grant No.2006B36430001 (广东省科技计划项目)


Greedy Approximation Algorithm of Minimum Cover Set in Wireless Sensor Networks
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [17]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    网络生命期是限制无线传感器网络发展的一个瓶颈.在保证网络监控性能的前提下,仅调度部分节点工作而让其余节点处于低功耗的休眠状态,可以有效节省能耗,延长网络生命期.节点调度的目标是寻找一个能够覆盖监控区域的最小节点集合,这是一个NP难问题,目前,其近似算法的性能较低.提出了一种基于贪婪法的最小覆盖集近似算法,在构造覆盖集的过程中,优先选择扩展面积最大的有效节点加入覆盖集.理论分析表明,该算法能够构造出较好的覆盖集,时间复杂度为O(n),其中,n为初始节点总数.实验数据表明,该算法的性能要优于现有算法,得到的覆盖集的平均大小比现有算法减小了14.2%左右,且执行时间要短于现有算法.当初始节点分布较密时,该算法得到的平均覆盖度小于1.75,近似比小于1.45.

    Abstract:

    Network lifetime is a bottleneck that restricts the development of wireless sensor networks. One approach to save energy effectively and prolong network lifetime is to schedule some nodes to work and put other nodes into a low-powered sleep mode, while monitoring performance of network. The object of scheduling nodes is to obtain a minimum node set that can cover a monitored region. This is a NP-hard problem. Performances of present approximation algorithms have not been good. An approximation algorithm of a minimum cover set problem based on methodology is proposed. During the process of constructing a cover set, effective node that extends to maximal areas are selected to join the cover set. Theoretical analyses show that the algorithm can construct a cover set that perform well and has a time complexity that is O(n), where n is initial node number. Experimental results show that performance of this new algorithm outperform that of present algorithms. The size of a cover set is decreased by 14.2%. Also, execution time is less than that of present algorithms. When initial nodes are deployed densely, the average degree of coverage obtained by the algorithm is below 1.75 and has an approximation ratio below 1.45.

    参考文献
    [1] Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E. Wireless sensor networks: A survey. Computer Networks, 2002,38(4): 393?422. [doi: 10.1016/S1389-1286(01)00302-4]
    [2] Seo HM, Moon Y, Park YK, Kim D, Kim DS, Lee YS, Won KH, Kim SD, Choi P. A low power fully CMOS integrated RF transceiver IC for wireless sensor networks. IEEE Trans. on Very Large Scale Integration Systems, 2007,15(2):227?231. [doi: 10.1109/TVLSI.2007.893586]
    [3] 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). [doi: 10.1360/crad20050121]
    [4] 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/ch/reader/view_abstract.aspx?flag=1&file_no=20030713&journal_id=jos
    [5] Dagher JC, Marcellin MW, Neifeld MA. A theory for maximizing the lifetime of sensor networks. IEEE Trans. on Communications, 2007,55(2):323?332. [doi: 10.1109/TCOMM.2006.887495]
    [6] Wang W, Srinivasan V, Chua KC. Extending the lifetime of wireless sensor networks through mobile relays. ACM Trans. on Networking, 2008,16(5):1108?1120. [doi: 10.1109/TNET.2007.906663]
    [7] Mainwaring A, Polastre J, Szewczyk R, Culler D, Anderson J. Wireless sensor networks for habitat monitoring. In: Reghavendrv CS, ed. Proc. of the 1st ACM Int’l Workshop on Wireless Sensor Networks and Applications. New York: ACM Press, 2002. 88?97.
    [8] 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.
    [9] Vieira MAM, Vieira LFM, Ruiz LB, Loureiro AAF, Fernandes AO, Nogueira JMS. Scheduling nodes in wireless sensor networks: A Voronoi approach. In: Stiller B, George AD, eds. Proc. of the 28th Annual IEEE Int’l Conf. on Local Computer Networks. Washington: IEEE Computer Society, 2003. 423?429.
    [10] 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.
    [11] Slijepcevic S, Potkonjak M. Power efficient organization of wireless sensor networks. In: Proc. of the IEEE Int’l Conf. on Communications. Helsinki: IEEE Communication Society, 2001. 472?476. http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp? punumber=7452
    [12] Chakravarty S, Shekhawat A. Parallel and serial heuristics for the minimum set cover problem. The Journal of Supercomputing, 1992,5(4):331?345. [doi: 10.1007/BF00127952]
    [13] Jiang J, Fang L, Zhang HY, Dou WH. An algorithm for minimal connected cover set problem in wireless sensor networks. Journal of Software, 2006,17(2):175?184 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/175.htm [doi: 10.1360/ jos170175]
    [14] Hochbaum DS. Approximation Algorithms for NP-Hard Problems. Cambridge: PWS Publishing Company, 1995.
    附中文参考文献: [3] 崔莉,鞠海玲,苗勇,李天璞,刘巍,赵泽.无线传感器网络研究进展.计算机研究与发展,2005,42(1):163?174. [doi: 10.1360/ crad20050121]
    [4] 任丰原,黄海宁,林闯.无线传感器网络.软件学报,2003,14(7):1282?1291. http://www.jos.org.cn/ch/reader/view_abstract.aspx? flag=1&file_no=20030713&journal_id=jos
    [13] 蒋杰,方力,张鹤颖,窦文华.无线传感器网络最小连通覆盖集问题求解算法.软件学报,2006,17(2):175?184. http://www.jos.org.cn/ 1000-9825/17/175.htm [doi: 10.1360/jos170175]
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

陆克中,孙宏元.无线传感器网络最小覆盖集的贪婪近似算法.软件学报,2010,21(10):2656-2665

复制
分享
文章指标
  • 点击次数:4871
  • 下载次数: 6559
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2009-01-15
  • 最后修改日期:2009-07-07
文章二维码
您是第20053166位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号