Modeling and Solving of Sensor Network Lifetime Problem with Coverage Model

doi:10.3778/j.issn.1673-9418.2009043

Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (3): 565-573.DOI: 10.3778/j.issn.1673-9418.2009043

• Network and Information Security • Previous Articles Next Articles

Modeling and Solving of Sensor Network Lifetime Problem with Coverage Model

ZHAO Haijun¹^,²^,⁺(), HE Chunlin¹^,², PU Bin¹^,², CHEN Yihong¹^,²

1. School of Computer, China West Normal University, Nanchong, Sichuan 637009, China
2. Nanchong Key Laboratory of Internet of Things Perception and Big Data Analysis, Nanchong, Sichuan 637009, China

Received:2020-09-16 Revised:2020-12-16 Online:2022-03-01 Published:2020-12-24
About author:ZHAO Haijun, born in 1966, M.S., professor, M.S. supervisor. His research interests include wire-less communications and wireless sensor networks.
HE Chunlin, born in 1971, M.S., professor, M.S. supervisor. His research interests include computer big data and image processing.
PU Bin, born in 1972, M.S., associate professor. His research interests include data communi-cation and network information security.
CHEN Yihong, born in 1972, Ph.D., professor, M.S. supervisor. His research interests include RFID, Internet of things and big data analysis.
Supported by:
National Natural Science Foundation of China(61871330);Special Fund of Basic Scientific Research Operating Expenses of China West Normal University(14C002)

覆盖模型的传感器网络寿命问题建模及其求解

赵海军¹^,²^,⁺(), 贺春林¹^,², 蒲斌¹^,², 陈毅红¹^,²

1.西华师范大学计算机学院,四川南充 637009
2.物联网感知与大数据分析南充市重点实验室,四川南充 637009

通讯作者: + E-mail: zhaohai_jun@163.com
作者简介:赵海军（1966—）,男,四川广安人,硕士,教授,硕士生导师,主要研究方向为无线通信、无线传感器网络。
贺春林（1971—）,男,四川广安人,硕士,教授,硕士生导师,主要研究方向为计算机大数据、图像处理。
蒲斌（1972—）,男,四川南部人,硕士,副教授,主要研究方向为数据通信、网络信息安全。
陈毅红（1972—）,男,四川营山人,博士,教授,硕士生导师,主要研究方向为RFID、物联网与大数据分析。
基金资助:
国家自然科学基金(61871330);西华师范大学基本科研业务费专项资金(14C002)

Abstract

Abstract:

Aiming at the sensor network lifetime problem (SNLP), a sensor network coverage model and its data structure are proposed, and the problem is equivalent to its dual problem, namely minimum weight sensor coverage problem. Firstly, SNLP is constructed as a package linear programming. After finding different sensor coverage satisfying sensor network constraints, the sensor network life is maximized by allocating time for each sensor coverage. Secondly, for solving SNLP, three centralized solving methods are proposed, which are based on Garg-Konemann algorithm, greedy algorithm considering partial sensor coverage and constant approximation algorithm considering communication cost. At the same time, a distributed solving method based on global reshuffle is pro-posed. The reshuffle is triggered when the initial energy supply of a sensor drops to a certain predefined threshold value H among active, idle and intermediate vulnerable states, thus the sensor network lifetime is improved by using smart self-organizing monitoring schedules. Simulation results show that the proposed SNLP, which is based on sensor network coverage model and data structure, and its solving method can achieve preferable running time, network life and network overhead.

Key words: sensor network lifetime, energy consumption, coverage, packing linear programming, approximation algorithm, distributed protocols

摘要：

针对传感器网络的寿命问题（SNLP）,提出了一种传感器网络覆盖模型及其数据结构,并把该问题等效为它的对偶问题——最小权值传感器覆盖问题。首先,把SNLP构建为一个包装线性规划,在找到满足传感器网络约束的不同传感器覆盖后,通过为每个传感器覆盖分配时间来使传感器网络寿命最大化;其次,对于求解SNLP,提出了基于Garg-Konemann算法、考虑部分传感器覆盖的贪婪算法和考虑通信成本的常数近似算法的三种集中式求解方法;同时还提出了一种基于全局重组的分布式求解方法,使传感器在活跃的、空闲的或中间脆弱的三种状态之间,基于传感器的初始能量供给下降到预先确定的某个阈值H时触发重组,从而通过智能自组织监测调度来提高传感器网络寿命。仿真实验结果表明,提出的基于传感器网络覆盖模型和数据结构的SNLP及其求解方法,能够获得较好的运行时间、网络寿命和网络开销。

关键词: 传感器网络寿命, 能量消耗, 覆盖, 包装线性规划, 近似算法, 分布式协议

CLC Number:

TP393

ZHAO Haijun, HE Chunlin, PU Bin, CHEN Yihong. Modeling and Solving of Sensor Network Lifetime Problem with Coverage Model[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(3): 565-573.

赵海军, 贺春林, 蒲斌, 陈毅红. 覆盖模型的传感器网络寿命问题建模及其求解[J]. 计算机科学与探索, 2022, 16(3): 565-573.

Figures/Tables 5

References 17

[1]	LIU J X, XIONG K, FAN P Y, et al. RF energy harvesting wireless powered sensor networks for smart cities[J]. IEEE Access, 2017, 5(99): 9348-9358. DOI URL
[2]	林晓鹏. 无线传感器网络的能效分析[J]. 智能计算机与应用, 2017, 7(6): 32-34.
	LIN X P. Analysis of energy efficiency in wireless sensor networks[J]. Intelligent Computer and Applications, 2017, 7(6): 32-34.
[3]	王振海. 可持续能量收集无线传感器网络能量建模与优化[D]. 哈尔滨: 哈尔滨工业大学, 2016.
	WANG Z H. Sustainable energy harvesting wireless sensor networks energy modeling and optimization[D]. Harbin: Harbin Institute of Technology, 2016.
[4]	李志华, 连彬, 魏忠诚, 等. 无线传感器网络能效和延时性能分析[J]. 计算机应用研究, 2014, 31(8): 2473-2476.
	LI Z H, LIAN B, WEI Z C, et al. Energy efficiency and delay analysis in wireless sensor network[J]. Application Research of Computers, 2014, 31(8): 2473-2476.
[5]	黄敏, 张伟, 胡立刚, 等. 具有能量收集管理的无线传感器节点设计[J]. 智能计算机与应用, 2017, 7(1): 22-26.
	HUANG M, ZHANG W, HU L G, et al. Design of wireless sensor node with energy harvesting and management[J]. In-telligent Computer and Applications, 2017, 7(1): 22-26.
[6]	SALIM A, OSAMY W, KHEDR A M. Effective scheduling strategy in wireless multimedia sensor networks for cri-tical surveillance applications[J]. Applied Mathematics & Information Sciences, 2018, 12(1): 101-111.
[7]	TAN C K, LIEW S Y, GOH H G, et al. A fast, adaptive, and energy-efficient multi-path-multi-channel data collection protocol for wireless sensor networks[C]// Proceedings of the 2017 International Conference on Recent Advances in Signal Processing, Telecommunications & Computing, Da Nang, Jan 9-11, 2017. Piscataway: IEEE, 2017: 33-38.
[8]	PALAZZI V, GELATI F, VAGLIONI U, et al. Leaf-compatible autonomous RFID-based wireless temperature sensors for precision agriculture[C]// Proceedings of the 2019 IEEE Topical Conference on Wireless Sensors and Sensor Networks, Orlando, Jan 20-23, 2019. Piscataway: IEEE, 2019: 1-4.
[9]	HASAN M Z, Al-RIZZO H, GUNAY M. Lifetime maximiza-tion by partitioning approach in wireless sensor networks[J]. Eurasip Journal on Wireless Communications & Networking, 2017, 15(1): 2-18.
[10]	王宏健, 张雪莲, 吕洪莉. 基于几何覆盖率算法的传感器覆盖优化策略[J]. 计算机应用研究, 2017, 34(8): 2478-2482.
	WANG H J, ZHANG X L, LYU H L. Optimized strategy of sensor coverage based on geometry coverage algorithm[J]. Application Research of Computers, 2017, 34(8): 2478-2482.
[11]	丁旭, 吴晓蓓, 黄成. 基于改进粒子群算法和特征点集的无线传感器网络覆盖问题研究[J]. 电子学报, 2016, 44(4): 967-973. DOI
	DING X, WU X B, HUANG C. Area coverage problem based on improved PSO algorithm and feature point set in wireless sensor networks[J]. Acta Electronica Sinica, 2016, 44(4): 967-973.
[12]	张聚伟, 王宇, 杨挺. 基于数据融合的有向传感器网络全覆盖部署[J]. 传感技术学报, 2017, 30(1): 139-145.
	ZHANG J W, WANG Y, YANG T. Full coverage deploy-ment algorithm of directional sensor network based on data fusion[J]. Chinese Journal of Sensors and Actuators, 2017, 30(1): 139-145.
[13]	PUGHAT A, SHANMA V. Performance analysis of an im-proved dynamic power management model in wireless sen-sor node[J]. Digital Communications & Networks, 2016, 3(1): 19-29.
[14]	MORE P R, SANKPAL S V. Energy aware routing using energy efficient routing protocol in wireless Ad hoc network[C]// Proceedings of the 2016 International Conference on Electrical, Electronics, and Optimization Techniques, Chennai, Mar 3-5, 2016. Piscataway: IEEE, 2016: 1258-1261.
[15]	GURUGANESH G, SANITÀ L, SWAMY C. Improved region-growing and combinatorial algorithms for k-Route cut problems[C]// Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, Jan 4-6, 2015. Philadelphia: SIAM, 2015: 676-695.
[16]	DING S B. Uncertain minimum cost multicommodity flow problem[J]. Soft Computing, 2017, 21(1): 223-231. DOI URL
[17]	BLEY A, LJUBIC I, MAURER O. A node-based ILP formu-lation for the node-weighted dominating Steiner problem[J]. Networks, 2017, 69(1): 33-51. DOI URL

算法类型	节点数目	感知范围/m	面数	运行时间/s
近似Garg-Konemann算法	100~1 000	100~150	861~81 845	5.56~3 755.47
CPLEX解	100~1 000	100~150	861~81 845	9.77~7 887.55
分布式调度算法	100~1 000	100~150	861~81 845	3.56~3 605.46

算法类型	节点数目	感知范围/m	面数	运行时间/s
近似Garg-Konemann算法	100~1 000	100~150	861~81 845	5.56~3 755.47
CPLEX解	100~1 000	100~150	861~81 845	9.77~7 887.55
分布式调度算法	100~1 000	100~150	861~81 845	3.56~3 605.46

传感器节点数	名称（归一化单位时间）	重组触发阈值
传感器节点数	名称（归一化单位时间）	1	2	3	5	10
100	网络寿命	31.3	30.3	29.6	28.6	26.1
100	通信开销	350.2	173.3	119.5	736.4	415.5
200	网络寿命	54.1	53.3	52.6	52.0	51.8
200	通信开销	1 121.1	559.8	380.2	239.8	138.2
300	网络寿命	120.0	105.6	100.3	98.1	93.5
300	通信开销	2 587.2	1 344.1	958.7	688.8	499.7
400	网络寿命	169.5	167.3	164.6	158.9	154.5
400	通信开销	4 675.5	2 346.6	2 055.0	1 438.1	939.4
500	网络寿命	221.2	210.1	206.3	199.6	182.1
500	通信开销	7 365.2	4 211.4	3 258.5	2 257.8	1 304.2

传感器节点数	名称（归一化单位时间）	重组触发阈值
传感器节点数	名称（归一化单位时间）	1	2	3	5	10
100	网络寿命	31.3	30.3	29.6	28.6	26.1
100	通信开销	350.2	173.3	119.5	736.4	415.5
200	网络寿命	54.1	53.3	52.6	52.0	51.8
200	通信开销	1 121.1	559.8	380.2	239.8	138.2
300	网络寿命	120.0	105.6	100.3	98.1	93.5
300	通信开销	2 587.2	1 344.1	958.7	688.8	499.7
400	网络寿命	169.5	167.3	164.6	158.9	154.5
400	通信开销	4 675.5	2 346.6	2 055.0	1 438.1	939.4
500	网络寿命	221.2	210.1	206.3	199.6	182.1
500	通信开销	7 365.2	4 211.4	3 258.5	2 257.8	1 304.2

Modeling and Solving of Sensor Network Lifetime Problem with Coverage Model

覆盖模型的传感器网络寿命问题建模及其求解

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 17

Related Articles 12

Recommended Articles

Metrics

[1]	WEI Guang, QIAN Depei, YANG Hailong, LUAN Zhongzhi. Practice on Program Energy Consumption Optimization by Energy Measurement and Analysis Using FPowerTool [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(6): 1291-1303.
[2]	SUN Zeyu, LI Chuanfeng, XING Xiaofei, LAI Chunxiao. Optimization Cooperative Coverage Algorithm with Controllable Threshold- Parameters in WSNs [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(5): 893-906.
[3]	GONG Yifan, LIU Hongyan, HE Jun, YUE Yongjiao, DU Xiaoyong. Research on Text Summarization Model with Coverage Mechanism [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(2): 205-213.
[4]	ZHANG Yiwen, WANG Cheng. Reliability-Aware Energy Management Scheduling Algorithm for Periodic Task [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(5): 833-841.
[5]	LI Weidong, LICHEN Junran, LI Jianping. Load Balancing Problem with Hierarchical Constraints in l_p Norm [J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(8): 1184-1190.
[6]	TAO Yang, HE Qianjin. Research on Vertical Handoff Mechanism in Heterogeneous Convergence Networks [J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(4): 504-515.
[7]	JIANG Lian, HUANG Hailiang, ZHOU Xiaocong, WANG Xinming, LI Wenjun. Software Fault Localization Technique Based on Variable Infection [J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(8): 966-977.
[8]	HE Yanxiang, CHEN Yong, WU Wei, LI Qing’an, JIANG Nan, XU Chao1. Optimization for Green Compilations: A Survey [J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(8): 673-690.
[9]	HAN Meng1, LI Jianzhong1,2, ZOU Zhaonian2 . Finding K Close Subgraphs in an Uncertain Graph [J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(9): 791-803.
[10]	HU Congxing, CHEN Lin, DING Hui, ZENG Yi. Fault Localization Method of Combining Statement Execution Complement [J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(6): 522-533.
[11]	HAN Meng, LI Jianzhong, ZOU Zhaonian. Finding K Close Subgraphs in an Uncertain Graph [J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(09): 791-803.
[12]	XU Daoyun⁺. PCP theorem and its applications to research on non-approximatable problems [J]. Journal of Frontiers of Computer Science and Technology, 2008, 2(1): 20-31.