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

doi:10.3778/j.issn.1673-9418.2009043

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (3): 565-573.DOI: 10.3778/j.issn.1673-9418.2009043

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

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

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

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

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)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP393

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

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.

图/表 5

参考文献 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

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 17

相关文章 15

编辑推荐

Metrics

[1]	孙泽宇, 李传锋, 邢萧飞, 来纯晓. 传感网中带有可控阈值的优化协同覆盖算法[J]. 计算机科学与探索, 2021, 15(5): 893-906.
[2]	曾祥伟, 邓玉辉. 利用页面重构与数据温度识别的闪存缓存算法[J]. 计算机科学与探索, 2021, 15(1): 84-95.
[3]	严远亭，朱原玮，吴增宝，张以文，张燕平. 构造性覆盖算法的SMOTE过采样方法[J]. 计算机科学与探索, 2020, 14(6): 975-984.
[4]	巩轶凡，刘红岩，何军，岳永姣，杜小勇. 带有覆盖率机制的文本摘要模型研究[J]. 计算机科学与探索, 2019, 13(2): 205-213.
[5]	李伟东，李陈筠然，李建平. l_p范数下具有等级约束的负载均衡问题[J]. 计算机科学与探索, 2016, 10(8): 1184-1190.
[6]	孙焕良，富珊珊，刘俊岭，于戈，许鸿斐. 社会网络中弱关系团队形成问题研究[J]. 计算机科学与探索, 2016, 10(6): 773-785.
[7]	吴鲁辉，李凡长. 多李群核覆盖学习算法在图像分类上的应用[J]. 计算机科学与探索, 2016, 10(12): 1737-1743.
[8]	段雨晴，李世峰，丁琳琳. 基于平面图覆盖的大规模图可达查询处理[J]. 计算机科学与探索, 2015, 9(11): 1326-1334.
[9]	严晨，李凡长，邹鹏. 多连通李群覆盖学习算法在图像分类上的应用[J]. 计算机科学与探索, 2014, 8(9): 1101-1112.
[10]	江联，黄海亮，周晓聪，王欣明，李文军. 基于变量感染分析的软件错误定位技术[J]. 计算机科学与探索, 2014, 8(8): 966-977.
[11]	张燕平，邹慧锦，邢航，赵姝. CCA三支决策模型的边界域样本处理[J]. 计算机科学与探索, 2014, 8(5): 593-600.
[12]	王丽娟，杨习贝，吴陈. 多覆盖近似空间中的粗糙集模型[J]. 计算机科学与探索, 2014, 8(5): 601-607.
[13]	秦克云，张小红. CD格上的近似算子[J]. 计算机科学与探索, 2013, 7(1): 92-96.
[14]	王石平, 祝峰, 闵帆, 汤建国. 横贯拟阵与覆盖粗糙集[J]. 计算机科学与探索, 2012, 6(3): 281-286.
[15]	韩蒙1, 李建中1,2, 邹兆年2. 从不确定图中发现K紧密子图[J]. 计算机科学与探索, 2011, 5(9): 791-803.