多等级通信半径的无源传感器网络中的覆盖问题
作者:
作者简介:

石拓(1992-),男,博士,CCF专业会员,无源传感器网络,边缘计算.
高宏(1966-),女,博士,教授,博士生导师,CCF杰出会员,主要研究领域为图数据管理,大数据管理,传感器网络.
李建中(1950-),男,教授,博士生导师,CCF会士,主要研究领域为大数据管理,传感器网络.

通讯作者:

石拓,E-mail:shituo@hit.edu.cn

中图分类号:

TP393

基金项目:

国家自然科学基金(61832003,61632010);国家重点研发计划(2019YFB2101902)


Coverage Problem in Battery-free Sensor Networks with Multi-level Communication Radius
Author:
Fund Project:

National Natural Science Foundation of China (61832003, 61632010); National Key Research and Development Program of China (2019YFB2101902)

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [33]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    无源传感器网络是近年来兴起的一种新型的网络结构,可用于解决传统无线传感器网络能量有限、寿命受限的问题.在无源传感器网络中,每个无源传感器节点配备有能量收集模块,可以从周围环境中获取能量.由于周围环境中的能量是无限的,这样,从能量的角度来讲,无源传感器网络的网络寿命是无限的.这样就解决了传统无线传感器网络寿命受限的问题.然而,由于周围环境中的能量源具有能量低、分布不均匀等特点,导致无源传感器网络中的覆盖问题比传统的无线传感器网络中的覆盖问题更加复杂.为了解决无源传感器网络中的覆盖问题,同时也为了让无源节点更有效地利用环境中的能量,考虑了一种具有多等级通信半径的无源节点,并提出了基于多等级通信半径的无源传感器网络中的覆盖问题.证明了这个问题是NP-Hard问题.提出一种基于贪心策略的近似算法,解决了这个问题,并证明了该算法的近似比.同时,采用模拟实验的方式验证了该算法的性能.根据实验结果,该算法是有效且可靠的.

    Abstract:

    The battery-free sensor network is an emerging IoT network architecture. The battery-free sensor network aims to address the energy and lifetime limitations in traditional wireless sensor networks. In the battery-free sensor network, battery-free nodes can harvest energy from the ambient environment by specific energy harvesting component. Since the energy in the ambient environment is infinite, the lifetime of the battery-free sensor networks is unlimited in terms of energy. Thus, the lifetime limitation of the wireless sensor network can be addressed. However, since the ambient energy is usually very weak and it distributes unevenly, the coverage problem in battery-free sensor networks is very complex than that in traditional wireless sensory networks. In order to solve the coverage problem in battery-free sensor networks and more reasonably use the harvested energy, a battery-free sensor network is considered in which battery-free nodes have multi-level communication radius. Furthermore, a coverage problem is defined in such networks. It is proved that this problem is NP-Hard, and an approximation algorithm is proposed to solve this problem. The approximation ratio of such algorithm is analyzed and the simulations are also carried out to evaluate the performance of the algorithm. The results demonstrate that the algorithm is effective and efficient.

    参考文献
    [1] Zhang H, Hou JC. Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc & Sensor Wireless Networks, 2005,1(1-2):89-124.
    [2] Shi T, Li JZ, Gao H, Cai ZP. Coverage in battery-free wireless sensor networks. In:Proc. of the IEEE Conf. on Computer Communications (IEEE INFOCOM 2018). IEEE, 2018. 108-116.
    [3] Shi T, Li JZ, Gao H, Cai ZP. A novel framework for the coverage problem in battery-free wireless sensor networks. IEEE Trans. on Mobile Computing, 2020.[doi:10.1109/TMC.2020.3019470]
    [4] Shi T, Cheng SY, Li JZ, Cai ZP. Constructing connected dominating sets in battery-free networks. In:Proc. of the IEEE Conf. on Computer Communications (IEEE INFOCOM 2017). IEEE, 2017. 1-9.
    [5] Shi T, Cheng SY, Li JZ, Gao H, Cai ZP. Dominating sets construction in RF-based battery-free sensor networks with full coverage guarantee. ACM Trans. on Sensor Networks (TOSN), 2019,15(4):1-29.
    [6] Liu C, Wu K, Xiao Y, Sun B. Random coverage with guaranteed connectivity:Joint scheduling for wireless sensor networks. IEEE Trans. on Parallel and Distributed Systems, 2006,17(6):562-575.
    [7] He SB, Chen JM, Sun YX. Coverage and connectivity in duty-cycled wireless sensor networks for event monitoring. IEEE Trans. on Parallel and Distributed Systems, 2012,23(3):475-482.
    [8] Han K, Xiang L, Luo J, Liu Y. Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features. In:Proc. of the MobiHoc 2012. ACM, 2012. 85-94.
    [9] Liu H, Wan PJ, Yi CW, Jia XH, Makki S, Pissinou N. Maximal lifetime scheduling in sensor surveillance networks. In:Proc. of the INFOCOM 2005, Vol.4. IEEE, 2005. 2482-2491.
    [10] Li Y, Thai MT, Wang F, Yi CW, Wan PJ, Du DZ. On greedy construction of connected dominating sets in wireless networks. Wireless Communications and Mobile Computing, 2005,5(8):927-932.
    [11] Yu JG, Wang NN, Wang GG. Constructing minimum extended weakly-connected dominating sets for clustering in ad hoc networks. Journal of Parallel and Distributed Computing, 2012,72(1):35-47.
    [12] Wu J, Li HL. On calculating connected dominating set for efficient routing in ad hoc wireless networks. In:Proc. of the 3rd Int'l Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. ACM, 1999. 7-14.
    [13] Liu BY, Dousse O, Wang J, Saipulla A. Strong barrier coverage of wireless sensor networks. In:Proc. of the MobiHoc 2008. ACM, 2008. 411-420.
    [14] Li XY, Wan PJ, Frieder O. Coverage in wireless ad hoc sensor networks. IEEE Trans. on Computers, 2003,52(6):753-763.
    [15] Mao X, Liu Y, Tang S, Liu H, Han J, Li XY. Finding best and worst k-coverage paths in multihop wireless sensor networks. IEEE Trans. on Parallel and Distributed Systems, 2013,24(12):2396-2406.
    [16] Shi T, Cheng SY, Cai ZP, Li JZ. Adaptive connected dominating set discovering algorithm in energy-harvest sensor networks. In:Proc. of the 35th Annual IEEE Int'l Conf. on Computer Communications (IEEE INFOCOM 2016). IEEE, 2016. 1-9.
    [17] Shi T, Cheng SY, Cai ZP, Li YS, Li JZ. Exploring connected dominating sets in energy harvest networks. IEEE/ACM Trans. on Networking, 2017,25(3):1803-1817.
    [18] Ren XJ, Liang WF, Xu WZ. Quality-Aware target coverage in energy harvesting sensor networks. IEEE Trans. on Emerging Topics in Computing, 2014,3(1):8-21.
    [19] Sample AP, Yeager DJ, Powledge PS, Mamishev AV, Smith JR. Design of an RFID-based battery-free programmable sensing platform. IEEE Trans. on Instrumentation and Measurement, 2008,57(11):2608-2615.
    [20] Smith JR, Sample AP, Powledge PS, Roy S, Mamishev A. A wirelessly-powered platform for sensing and computation. In:Proc. of the Int'l Conf. on Ubiquitous Computing. Springer-Verlag, 2006. 495-506.
    [21] Sample AP, Yeager DJ, Powledge PS, Smith JR. Design of a passively-powered, programmable sensing platform for uhf rfid systems. In:Proc. of the 2007 IEEE Int'l Conf. on RFID. IEEE, 2007. 149-156.
    [22] Alippi C, Galperti C. An adaptive system for optimal solar energy harvesting in wireless sensor network nodes. IEEE Trans. on Circuits and Systems, 2008,55(6):1742-1750.
    [23] Park C, Chou PH. Ambimax:Autonomous energy harvesting platform for multi-supply wireless sensor nodes. In:Proc. of the SECON, Vol.1. IEEE, 2006. 168-177.
    [24] Dai H, Liu Y, Liu AX, Kong L, Chen G, He T. Radiation constrained wireless charger placement. In:Proc. of the 35th Annual IEEE Int'l Conf. on Computer Communications (IEEE INFOCOM 2016). IEEE, 2016. 1-9.
    [25] Dai H, Wang X, Liu AX, Ma H, Chen G, Dou W. Wireless charger placement for directional charging. IEEE/ACM Trans. on Networking (TON), 2018,26(4):1865-1878.
    [26] Shi T, Cai ZP, Li JZ, Gao H. The energy-data dual coverage in battery-free sensor networks. In:Proc. of the 2019 IEEE 39th Int'l Conf. on Distributed Computing Systems (ICDCS). IEEE, 2019. 338-347.
    [27] Zhang Y, Gao H, Cheng SY, Cai ZP, Li JZ. IEA:An intermittent energy aware platform for ultra-low powered energy harvesting WSN. In:Proc. of the Int'l Conf. on Wireless Algorithms, Systems, and Applications. Cham:Springer-Verlag, 2010. 185-197.
    [28] He J, Ji SL, Pan Y, Li YS. Reliable and energy efficient target coverage for wireless sensor networks. Tsinghua Science and Technology, 2011,16(5):464-474.
    [29] Song C, Liu M, Cao JN, Zheng Y, Gong HG, Chen GH. Maximizing network lifetime based on transmission range adjustment in wireless sensor networks. Computer Communications, 2009,32(11):1316-1325.
    [30] Kumar S, Lai TH, Balogh J. On k-coverage in a mostly sleeping sensor network. In:Proc. of the 10th Annual Int'l Conf. on Mobile Computing and Networking. 2004. 144-158.
    [31] Xue YH. Introduction to Internet of Things. Beijing:China Machine Press, 2014(in Chinese).
    附中文参考文献:
    [31] 薛燕红.物联网导论.北京:机械工业出版社,2014.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

石拓,李建中,高宏.多等级通信半径的无源传感器网络中的覆盖问题.软件学报,2021,32(8):2580-2596

复制
相关视频

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

京公网安备 11040202500063号