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

Modeling and Solving of Sensor Network Lifetime Problem with Coverage Model

作　　者：赵海军[1,2] 贺春林 蒲斌[1,2] 陈毅红 ZHAO Haijun;HE Chunlin;PU Bin;CHEN Yihong(School of Computer,China West Normal University,Nanchong,Sichuan 637009,China;Nanchong Key Laboratory of Internet of Things Perception and Big Data Analysis,Nanchong,Sichuan 637009,China)

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

出　　处：《计算机科学与探索》2022年第3期565-573,共9页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金(61871330);西华师范大学基本科研业务费专项资金(14C002)。

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]