基于全局时延最小化的移动Sink数据收集算法*

常　捷，张　灵，曾　碧

（广东工业大学计算机学院，广州510006）



基于全局时延最小化的移动Sink数据收集算法*

常捷，张灵*，曾碧

（广东工业大学计算机学院，广州510006）

摘要：针对Sink节点移动所带来的时延问题，提出了一种基于最优路径的移动Sink数据收集方案OPDG（Data Gathering Based on Optimal-Path）。首先由MWHA（Minimum Weighted Heuristic Algorithm）算法得到汇聚节点RP（Rendezvous Point）的集合，然后根据这些RP节点求出移动Sink的最佳驻留点集合，最后求出经过驻留点的最短路径。Sink沿着这条路径周期性采集数据。通过NS-2中大量的仿真实验结果表明，与已有算法相比，OPDG算法能最大限度的减小时延，延长网络的生命周期。

关键词：无线传感器网络；时延；移动Sink；汇聚节点

无线传感器网络WSN（Wireless Sensor Net⁃work）由大量微型的且能量受限的传感器节点组成。其中数据收集是WSN的主要应用之一，传感器节点通过逐跳通信的方式将感知的数据传送给Sink或基站。早期的研究工作侧重于静态网络［1］，容易使Sink周围的节点因过多的转发数据而很快死亡，从而造成“网络分割”，产生能量空洞［2］，使网络寿命大大降低。

因此很多研究者引入移动Sink来解决上述问题，相比静态网络，用移动Sink充当数据收集器［3-4］可以有效的解决能量空洞问题，缓解节点负载不均问题，而且，Sink的移动性还能减少节点将数据传输给Sink所需要的跳数，从而减少节点的能耗，延长网络寿命［5-6］。然而移动Sink的路径选择直接影响数据的收集效率以及网络的整体性能。Zhangc⁃hun［7］等采用一种自组织分簇算法选取合适的簇头作为数据收集点，可有效降低网络能耗。文献［8-9］提出时延受限时移动Sink的数据收集算法。……