微信服务号

微信订阅号

2025年4月3日 14:25 星期四
首页 > 过刊浏览>2009年第20卷第3期 >644-659
PDF HTML阅读 XML下载 导出引用 引用提醒
公平的有向传感器网络方向优化和节点调度算法
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.60603061 (国家自然科学基金)


Equitable Direction Optimizing and Node Scheduling for Coverage in Directional Sensor Networks
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [35]
    • |
  • 相似文献
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    为了解决有向传感器网络中点目标覆盖控制问题,分别提出了两种方向优化算法和一个节点调度协议:改进的贪婪(enhanced greedy algorithm,简称EGA)、公平的方向优化(equitable direction optimization,简称EDO)算法和邻居节点调度协议(neighbors sensing scheduling,NSS).EGA 基于覆盖最多未覆盖的目标数选取工作方向,其不足是可能忽略临界目标.EDO 优化算法调节节点的工作方向,优先覆盖临界目标,公平分配感知资源,减小目标覆盖度的差异,EDO 算法使用效用值评价每个方向对网络覆盖质量的贡献大小,影响效用值的因素包括每个方向上的目标数、目标的覆盖度和邻居节点的方向决策,EDO 总是选择效用值最大的方向作为工作方向.NSS 协议引入局部覆盖集的概念,通过局部覆盖集判断当前节点是否为冗余节点,并在考虑节点剩余能量时决定节点是否可以转为睡眠,调度协议允许一个节点加入多个覆盖集,覆盖集轮流工作,使网络生存期最大化.仿真实验结果表明,分布式的EDO 算法比EGA 算法具有更好的方向优化性能,临界目标的覆盖质量提高了30%,同时明显地提高了网络生存期.

    Abstract:

    To meet the coverage challenges arising in directional wireless sensor networks, this paper presents twodistributed direction optimizing algorithms and a node scheduling: enhanced greedy algorithm (EGA), equitabledirection optimization (EDO) and neighbors sensing scheduling (NSS) protocol. EGA algorithm optimizes directionmerely according to the amount of uncovered targets. It is used as the baseline for comparison. EDO adjusts thedirections of nodes to cover the critical targets superiorly and allocates sensing resource among nodes fairly tominimize the coverage differences between nodes. The utility function is introduced in EDO to assess the value of adirection contributed to overall networks sensing. The factors which affecting the utility are composed of the targetsin per direction, the coverage of targets and the neighbor’s decision of direction. EDO always selects the directionwith the maximum utility as the working direction. NSS arranges all sensors into multiple cover sets and allows anode to join several cover sets. Through employing local cover set, NSS identifies a redundant node and decideswhether it can sleep while taking residual energy to account. Nodes are activated in turn and the energy is consumedevenly to prolong the network life. The simulation shows that EDO outperforms EGA up to 30% in terms of criticalcoverage, and the combination of EDO and NSS prolongs the lifetime distinctly.

    参考文献
    [1] Akyildiz IF, Su W, Sankarasubramaniam Y, Cayirci E. A survey on sensor networks. IEEE Communications Magazine, 2002, 40:101?114.
    [2] 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
    [3] Arici T, Altunbasak Y. Adaptive sensing for environment monitoring using wireless sensor networks. In: Tachikawa K, Taga T, et al., eds. Proc. of the IEEE Wireless Communications and Networking Conf. (WCNC). New Orleans: IEEE Communications Society, 2003. 2347?2352.
    [4] Mainwaring A, Culler D, Polastre J. Wireless sensor networks for habitat monitoring. In: Raghavendra CS, Sivalingam KM, eds. Proc. of the 1st ACM Int’l Workshop on Wireless Sensor Networks and Application. Atlanta: ACM Press, 2002. 88–97.
    [5] Delin KA, Jackson SP. The sensor Web: A new instrument concept. In: Proc. of the Int’l Society for Optical Engineering Symposium on Integrated Optics. 2001. 1?9.
    [6] Li M, Liu YH. Underground structure monitoring with wireless sensor networks. In: Abdelzaher TF, Guibas LJ, eds. Proc. of the 6th Int’l Conf. on Information in Sensor Networks. Cambridge: ACM Press, 2007. 69?78.
    [7] Schwiebert L, Gupta SKS, Weinmann J. Research challenges in wireless networks of biomedical sensors. In: Rose C, Palazzo S, eds. Proc. of the ACM/IEEE Conf. on Mobile Computing and Networking (MOBICOM). Rome: ACM Press, 2001. 151?165.
    [8] Ren Y, Zhang SD, Zhang HK. 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
    [9] Slijepcevic S, Potkonjak M. Power efficient organization of wireless sensor networks. IEEE Int’l Conf. on Communications, 2001.
    [10] Berman P, Calinescu G, shah C, Zelikovsky A. Power efficient monitoring management in sensor networks. In: Proc. of the Conf. on IEEE Wireless Communication and Networking. Atlanta: IEEE Communications Society, 2004. 2329?2334.
    [11] Ye F, Zhong G, Lu S, Zhang L. PEAS: A robust energy conserving protocol for long-lived sensor networks. In: Almeroth K, Calvert K, eds. Proc. of the IEEE Int’l Conf. on Network Protocols (ICNP). Atlanta: IEEE Computer Society, 2003. 28?37.
    [12] Di T, Nicolas DG. A coverage-preserving node scheduling scheme for large wireless sensor networks. In: Raghavendra CS, Sivalingam KS, eds. Proc. of the 1st ACM Int’l Workshop on Wireless Sensor Networks and Applications. Atlanta: ACM Press, 2002.
    [13] Zhang M, Chan MC, Ananda AL. Coverage protocol for wireless sensor networks using distance estimates. In: Cruz R, Heinzelman W., eds. Proc. of the Mesh and Ad Hoc Communications and Networks (SECON). San Diego: IEEE Communications Society, 2007. 183?192.
    [14] Ting Y, Tian H, John AS. Differentiated surveillance for sensor networks. In: Akyildiz IF, Estrin D, et al., eds. Proc. of the 1st Int’l Conf. on Embedded Networked Sensor Systems. Los Angeles: ACM Press, 2003. 51?62.
    [15] Wang L, Kulkarni SS. Sacrificing a little coverage can substantially increase network lifetime. In: Sivalinga K, Yarvis M, eds. Proc. of the 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks (SECON). Reston: IEEE Communications Society, 2006. 326?335.
    [16] Xu Q, Wang Y. Solving reliable coverage in fault tolerant energy efficient wireless sensor networks. Journal of Software, 2006,17:184?191 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/s184.htm
    [17] Liu M, Cao JN, Zheng Y, Chen LJ, Xie L. Analysis for multi-coverage problem in wireless sensor networks. Journal of Software, 2007,18(3):127?136 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/18/127.htm
    [18] Himanshu G, Samir RD, Quinyi G. Connected sensor cover: Self-Organization of sensor networks for efficient query execution. In: Gerla M, Ephremides A, Srivastava M, eds. Proc. of the 4th ACM Int’l Symp. on Mobile Ad Hoc Networking and Computing. Annapolis: ACM Press, 2003. 189?200.
    [19] 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
    [20] Cardei M, Du DZ. Improving wireless sensor network lifetime through power aware organization. ACM Wireless Networks, 2005, 11:333?340.
    [21] Cardei M, Thai MT, Li Y, Wu W. Energy-Efficient target coverage in wireless sensor networks. In: Znati T, Knightly E, Makki K, eds. Proc. of the IEEE Computer Communications (Infocom). Miami: IEEE Communications Society, 2005. 1976?1984.
    [22] Sen A, Das N, Zhou L, Shen B, Murthy S, Bhattacharya P. Coverage problem for sensors embedded in temperature sensitive environments. Technical Report: TR-06-015, Department of Computer Science and Engineering, Arizona State University, 2006.
    [23] Wang W, Srinivasan V, Chua KC, Wang B. Energy-Efficient coverage for target detection in wireless sensor networks. In: Abdelzaher T, Guibas L, Kaiser B, et al., eds. Proc. of the Int’l Conf. on Information Processing in Sensor Networks (IPSN). Cambridge: IEEE Signal Processing Society, 2007. 313?322.
    [24] Gu Y, Hwang J, He T, Du DH. uSense: A unified asymmetric sensing coverage architecture for wireless sensor networks. In: Shatz SM, Abdelrahman TS, eds. Proc. of the Int’l Conf. on Distributed Computing Systems (ICDCS). Toronto: IEEE Computer Society, 2007. 8?18.
    [25] Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava M. Coverage problems in wireless ad-hoc sensor networks. In: Sengupta B, Kermani P, Lee D, eds. Proc. of the IEEE Computer Communications (Infocom). Anchorage: IEEE Communications Society, 2001. 1380?1387.
    [26] Ma HD, Liu YH. On coverage problems of directional sensor networks. In: Znati T, He YX, eds. Proc. of the Int’l Conf. on Mobile Ad-Hoc and Sensor Networks. LNCS 3794, Springer-Verlag, 2005. 721?731.
    [27] Tao D, Ma HD, Liu L. Coverage-Enhancing algorithm for directional sensor networks. In: Cao J, et al. eds. Proc. of the MSN 2006. LNCS 4325, Berlin: Springer-Verlag, 2006. 256?267.
    [28] Alhussein JA, Abouzeid A. Coverage by directional sensors in randomly deployed wireless sensor networks. Journal of Combinatorial Optimization, 2006,11:21?41.
    [29] Adriaens J, Megerian S, Potkonjak M. Optimal worst-case coverage of directional field-of-view sensor networks. In: Sivalingam K, Yarvis M, Zorzi M, eds. Proc. of the Sensor and Ad Hoc Communications and Networks. Reston: IEEE Communications Society, 2006. 336?345.
    [30] Cai Y, Lou W, Li ML. Target-Oriented scheduling in directional sensor networks. In: Domingo-Pascual J, Smirnow M, eds. Proc. of the IEEE Infocom 2007. Anchorage: IEEE Communications Society, 2007. 1550?1558. 附中文参考文献:
    [2] 任丰原,黄海宁,林闯.无线传感器网络.软件学报,2003,14(7):1282?1291. http://www.jos.org.cn/1000-9825/14/1282.htm
    [8] 任彦,张思东,张宏科.无线传感器网络中覆盖控制理论与算法.软件学报,2006,17(3):422?433. http://www.jos.org.cn/1000-9825/ 17/422.htm
    [16] 徐强,汪芸.容错节能无线传感器网络中可靠覆盖问题的解决方案.软件学报,2006,17:184?191. http://www.jos.org.cn/1000-9825/ 17/s184.htm
    [17] 刘明,曹建农,郑源,陈力军,谢力.无线传感器网络多重覆盖问题分析.软件学报,2007,18(3):127?136. http://www.jos.org.cn/ 1000-9825/18/127.htm
    [19] 蒋杰,方力,张鹤颖,窦文华.无线传感器网络最小连通覆盖集问题求解算法.软件学报,2006,17(2):175?184. http://www.jos.org.cn/ 1000-9825/17/175.htm
    相似文献
    引证文献
引用本文

温俊,蒋杰,窦文华.公平的有向传感器网络方向优化和节点调度算法.软件学报,2009,20(3):644-659

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2007-07-04
  • 最后修改日期:2007-11-05
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19780803位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号