有向传感器网络最大覆盖调度算法
作者:
基金项目:

Supported by the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z213 (国家高技术研究发展计划(863))


Maximal Coverage Scheduling in Wireless Directional Sensor Networks
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [13]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    与传统的全向传感器不同,有向传感器可以切换到不同的方向,并且每个方向覆盖有限角度的感应范围.针对有向传感器网络的区域覆盖问题,研究了“最大有向区域覆盖”MDAC(maximum directional area coverage)问题,期望通过调度传感器的工作方向,最大化覆盖区域面积.首先给出了MDAC 的问题定义,使用整数线性规划描述MDAC 问题,并且证明其是NP 完全的.然后提出一种分布式贪心算法DGreedy(distributed greedy algorithm)解决MDAC 问题.在此基础上,通过计算可能的覆盖贡献比例来反映网络拓扑信息.还提出了一种增强的算法PGreedy(distributed probability-enhanced greedy algorithm)使覆盖区域更大.证明了所提算法的收敛性,并通过详细的模拟实验验证了其有效性.

    Abstract:

    Unlike the traditional omni-directional sensors that always have an omni-angle of sensing range, directional sensors may be able to switch to several directions and each direction has a limited angle of sensingrange. This paper studies a novel “area coverage by directional sensors” problem. It proposes the MaximumDirectional Area Coverage (MDAC) to maximize the covered area by scheduling the working directions of thesensors in the network. This paper proves the MDAC to be NP-complete and proposes two distributed schedulingalgorithms for the MDAC. The proposed algorithms are proved to terminate in finite time. Simulation results demonstrate the effectiveness of the two algorithms.

    参考文献
    [1] Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E. A survey on sensor networks. IEEE Communications Magazine, 2002,40(8):102?114.
    [2] Szewczyk R, Mainwaring AM, Polastre J, Anderson J, Culler DE. An analysis of a large scale habitat monitoring application. In:Proc. of the ACM SenSys. Baltimore: ACM Press, 2004. 214?226. http://portal.acm.org/citation.cfm?id=1031521
    [3] Cardei M, Wu J. Energy-Efficient coverage problems in wireless ad hoc sensor networks. Journal of Computer Communications onSensor Networks, 2005,29(4):413?420.
    [4] Ren Y, Zhang S, Zhang H. Theories and algorithms of coverage control for wireless sensor networks. Journal of Software, 2006,17(3):422?433 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/422.htm
    [5] Rahimi M, Baer R, Iroezi OI, Garcia JC, Warrior J, Estrin D, Srivastava M. Cyclops: In situ image sensing and interpretation in wireless sensor networks. In: Proc. of the ACM SenSys. San Diego: ACM Press, 2005. 192?204. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.92.3772
    [6] Feng W, Kaiser E, Feng WC, Baillif ML. Panoptes: Scalable low-power video sensor networking technologies. ACM Trans. on Multimedia Computing, Communications and Applications, 2005,1(2):151?167.
    [7] Ma H, Tao D. Multimedia sensor network and its research progresses. Journal of Software, 2006,17(9):2013?2028 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/2013.htm
    [8] Slijepcevic S, Potkonjak M. Power efficient organization of wireless sensor networks. In: Proc. of the IEEE Int’l Conf. on Communications. Helsinki: IEEE Press, 2001. 472?476. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=936985
    [9] Gupta H, Zhou Z, Das SR, Gu Q. Connected sensor cover: Self-Organization of sensor networks for efficient query execution.IEEE/ACM Trans. on Networking, 2006,14(1):55?67.
    [10] Chen H, Wu H, Tzeng N. Grid-Based approach for working node selection in wireless sensor networks. In: Proc. of the IEEE Int’l Conf. on Communications (ICC). Paris: ACM Press, 2004. 20?24. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1313228
    [11] Ai J, Abouzeid AA. Coverage by directional sensors in randomly deployed wireless sensor networks. Journal of CombinatorialOptimization, 2006,11(1):21?41. 附中文参考文献:
    [4] 任彦,张思东,张宏科.无线传感器网络中覆盖控制理论与算法.软件学报,2006,17(3):422?433. http://www.jos.org.cn/1000-9825/17/422.htm
    [7] 马华东,陶丹.多媒体传感器网络及其研究进展.软件学报,2006,17(9):2013?2028. http://www.jos.org.cn/1000-9825/17/2013.htm
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

程卫芳,廖湘科,沈昌祥.有向传感器网络最大覆盖调度算法.软件学报,2009,20(4):975-984

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

京公网安备 11040202500063号