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

• 网络与信息安全 • 上一篇    下一篇

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

赵海军1,2,+(), 贺春林1,2, 蒲斌1,2, 陈毅红1,2   

  1. 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 Haijun1,2,+(), HE Chunlin1,2, PU Bin1,2, CHEN Yihong1,2   

  1. 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)

摘要:

针对传感器网络的寿命问题(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

中图分类号: