无线传感器网络延迟约束的MDC分布式轨道规划算法

作者：刘文军; 王喜; 林政宽

来源：传感技术学报, 2018, 31(08): 1270-1276.

• 无线传感器网络
• k跳支配集
• 数据收集
• 移动数据收集器

针对引入移动元素后无线传感器网络数据面临的收集延时问题,提出了一种分布式的移动数据收集器(MDC)轨道规划算法。首先给出基于k跳支配集的MDC最小时延规划问题定义,并证明它是NP-hard。在基于集结的数据收集模式汇总,k跳支配节点作为集结点缓存传感节点收集的数据并在MDC到达时上传。然后,提出了一种高效的基于k跳支配集的MDC轨迹构建算法。算法通过分布式的k-跳支配集算法找出网络中的支配节点,进而通过Prim算法和Christofides近似算法对MDC的移动轨道进行规划。算法的正确性、k-跳支配集的界、时间复杂性和消息交换复杂性通过理论进行分析。最后,通过仿真实验验证了算法的有效性。仿真结论表明,与同类算法相比,所提出算法能够显著缩短MDC的移动轨迹,因而可以降低网络延迟。

• 单位
  苏州大学; 苏州工业职业技术学院