一种基于移动基站的无线传感器网络数据收集方法

无线传感器网络由大量的微型传感器节点组成，已在多种监测应用中起到重要作用。在这些应用中，传感器节点通过多跳通信将感知数据传输到基站。基站往往是一个静止节点，使用最短路径路由或其他路由方式收取数据。因此靠近基站的节点需要比远离基站的点转发更多的数据，从而导致更快地耗尽能量并导致网络不再连通。这些节点通常被叫做“热点”。“热点”问题是传统的数据收集协议所无法解决的问题。

最近几年，有学者提出使用移动性来解决上述问题。提出的策略可分为两类。第一类方法使用一个或数个移动基站在网络中随机行走并收集数据。这类方法进行一次数据收集所耗费的时间是无法预期的。另一类方法试图将移动性和路由结合。基站被指定移动轨迹和速度，从而使其位置可以被预测，同时依然通过多跳路由方式收集数据。这类机制减少了数据延迟，但由于其较复杂，因而难以在实际应用。此外，这些方法大多基于UDG(UIlit Disk Graph)模型，即节点仅能与在某个圆形区域内的邻居节点通信。该模型与现实差别较大，影响了这些方法的实用效果。本文提出一种使用移动基站但不使用多跳路由机制的数据收集方法。其目标是克服现有方法在复杂度和实用性上的不足，减少通信代价，并平衡各节点的能量消耗。

1 网络模型与问题描述

连通的，在图G的定义外，存在一个移动基站，用来收集y中所有节点的监测数据。收集过程中不考虑数据聚合，并假定移动基站与静止节点具有相同的通信能力。基站在移动过程中在支配集中各点的位置短暂停留，当且仅当其停留时与周围静止的节点通信并收集数据。本文定义网络寿命为从传感器网络部署成功到第一个传感器节点因能量耗尽而停止工作的时间。传感器消耗能量的活动包括感知、计算、睡眠、等待、接收和发送数据，其中通信消耗的能量是最多的。本文的主要目的是最大化网络寿命，近似等价于尽可能地减少通信代价并平衡负载分布。

2 基于移动基站的数据收集

我们提出一种分布式的支配集构造方法。支配集中节点的位置作为基站的检查点。基站在每个检查点处可以通过单跳通信获取数据。使用旅行商问题的近似算法可以得出一条经过所有检查点的移动路径。基站沿此路径移动并收集网络中的所有节点上的数据。

2．1如何构造支配集

对于给定的图C，其支配集不是唯一的。各个支配集的势也不一定相等。支配集的势|s|越小，基站所必须停留的位置越少，在转化为旅行商问题求解时的约束条件就越少。直观上认为，约束条件较少时可能获得更优的解。因此，我们需要构造一个具有较小势的支配集。已有的研究主要聚焦于连通支配集的构造，而本文仅需非连通的支配集。最小支配集求解问题已被证明是“NP-完全”问题，在传感器网络中实现解决该问题的算法可能带来非常大的能量消耗，甚至可能远远超出其较少的势带来的收益。因此，我们提出一种分布式启发式算法，在构造具有较小势的支配集的同时降低了单个节点的通信消耗，并且使各个节点的通信消耗趋于均衡。该算法主要遵循以下两条规则：

规则1 在任意一条路径上，尽量每隔两个节点选一个节点作为支配点。

在强连通的图中，从任意一点出发，必然有到达任意其他点的最短路径。令n表示路径中所包含点的个数，对于一条足够长的路径(n≥3)，一定包括由三个连续节点组成的单元。只要将处于中间的节点添加进支配集，就能保证每个节点都被中间的节点支配。路径长度n按照nmod3的结果可以分为三类，即

当n=3m时，按照图中的方式选择节点构造支配集；当n=3m-1或n=3m-2时，在路径的前3(m—1)个节点部分采用图1所示方式选择节点，然后再加上路径中的最后一个节点构成支配集。该结论的证明可参考图论中关于环中最小支配集的势的定理相关证明，因篇幅限制，此处略过相关证明。

图1一条路径上的最小支配集

规则2尽可能选择度数高的节点作为支配集中节点。

由于图中含有多条相交的路径，因此仅使用上述规则并不能保证结果最优。当分布式实现上述规则时，尤其是网络中节点密度比较大的前提下，经常出现两个或多个相邻节点同时在不同的路径中被选择作为支配集中节点的情况，从而导致最终生成的支配集中存在多个相邻节点。直观地认为，在多个相邻节点竞争时，应当采用贪婪的方式，选择具有较高度数的节点加入到支配集中。

2．2支配集的分布式构造算法

分布式算法不需要中心化的管理，并且当问题规模变得很大时集中式算法的代价也难以接受。为了分布式地实现前文所描述的启发式算法规则，我们使用不同的角色来