Page 298 - 《软件学报》2021年第8期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(8):2580−2596 [doi: 10.13328/j.cnki.jos.006216] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
多等级通信半径的无源传感器网络中的覆盖问题

石 拓, 李建中, 高 宏

(哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001)
通讯作者: 石拓, E-mail: shituo@hit.edu.cn

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

中文引用格式: 石拓,李建中,高宏.多等级通信半径的无源传感器网络中的覆盖问题.软件学报,2021,32(8):2580−2596. http://
www.jos.org.cn/1000-9825/6216.htm
英文引用格式: Shi T, Li JZ, Gao H. Coverage problem in battery-free sensor networks with multi-level communication radius.
Ruan Jian Xue Bao/Journal of Software, 2021,32(8):2580−2596 (in Chinese). http://www.jos.org.cn/1000-9825/6216.htm

Coverage Problem in Battery-free Sensor Networks with Multi-level Communication Radius
SHI Tuo, LI Jian-Zhong, GAO Hong

(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)
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.
Key words: battery-free sensor network; sensor network; coverage

∗ 基金项目: 国家自然科学基金(61832003, 61632010); 国家重点研发计划(2019YFB2101902)
Foundation item: National Natural Science Foundation of China (61832003, 61632010); National Key Research and Development
Program of China (2019YFB2101902)
收稿时间: 2020-05-12; 修改时间: 2020-08-07; 采用时间: 2020-11-30; jos 在线出版时间: 2021-01-15