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

Latency Constrained Distributed Trajectory Planning in WSNs with Mobile Data Collector

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

To minimize the latency in mobility-enabled WSNs,an efficient trajectory planning algorithm of Mobile Data Collector（MDC） is proposed. First,the definition of minimum latency planning of MDC based on k-hop Dominating Sets（k-DSs） is given. k-DSs serve as rendezvous nodes to cache data from sensing nodes and upload the data to MDC when it arrives. Then,in order to locate the dominating nodes,an efficient distributed algorithm is provided.Based on k-DSs,the moving trajectory of MDC is constructed applying Prim algorithm for Minimum Spanning Tree and Christofides approximation algorithm for Traveling Salesman Problem. The algorithm correctness,the bound of kDSs,the time and message exchange complexity is analyzed,respectively. Finally,the simulation shows that compared with the existing algorithms,the proposed algorithm can effectively decrease trajectory length of MDC,and thus shorten the network latency.