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

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

最近几年，有学者提出使用移动性来解决上述问题。提出的策略可分为两类。第一类方法使用一个或数个移动基站在网络中随机行走并收集数据。这类方法进行一次数据收集所耗费的时间是无法预期的。另一类方法试图将移动性和路由结合。基站被指定移动轨迹和速度，从而使其位置可以被预测，同时依然通过多跳路由方式收集数据。这类机制减少了数据延迟，但由于其较复杂，因而难以在实际应用。此外，这些方法大多基于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支配集的分布式构造算法

分布式算法不需要中心化的管理，并且当问题规模变得很大时集中式算法的代价也难以接受。为了分布式地实现前文所描述的启发式算法规则，我们使用不同的角色来标志节点当前在支配集构造过程中的状态。定义节点角色可能的取值如下：

·NULL：表示初始化状态，节点还没被赋予任何角色；

·DOMINATOR：表示是支配集中的节点；

·DOMINATEE：表示是被支配集中某个节点支配的节点；

·2-NEIGHBOR：表示是支配集中某个节点的第二跳邻居，即某个被支配节点的邻居；

·CANDIDATE：表示是支配集中节点的候选节点。

算法开始时，任意选择网络中的一个节点，将其角色设置为DOMINATOR，并将该角色状态以广播的方式告知其邻居节点。这些邻居节点收到该广播消息后，将自己的角色设置为烈删TEE，并将新的角色进行广播。每个节点收到不同类型的角色消息后按不同方式处理，并用广播发送自己的角色信息。依此扩展开去，最终引起全网范围内所有节点至少广播一次。当所有节点的角色都是DOMINATOR或DOMINATEE时，节点不会再改变角色，也不会再广播新的消息，算法终止。此时，所有角色为DOMINATOR的节点就构成一个支配集。

各个角色之间的转换关系如图2所示。其中，收到角色状态消息后的状态变化遵循第一条规则。为了实现第二条规则，当节点角色变为CANDIDATE后，将会建立一个定时器，在一段时间延迟后触发。若在定时器触发之前，该节点收到DOMINATOR状态消息，则将自己的角色设置为DOMINATEE并取消定时器。若定时器被触发，则将节点角色设置为DOMINATOR。令节点秒上定时器时间延迟的长度为t(v)=C／|N(v)|，其中C为正的常数。这样，在两个相邻的CANDIDATE节点同时建立定时器后，拥有更高度数的节点将先触发定时器并成为DOMINATOR，另一节点在收到广播消息后则会成为烈)肘刀vATEE。但仅按上文描述的方式进行角色转换，并不能保证在所有节点广播一次后全网节点的状态都是DOMINATOR或DOMINATEE，还可能存在角色为2-NEIGHBOR。这些节点都正好处于规则l中所述某条从最初选择的DOMINATOR节点出发的最短路径的末端，但这些节点的相邻关系无法判定。因此，每个节点需要记录每个邻居是否广播过消息，如果是，则建立一个时长随机的定时器。定时器触发后则将该节点角色设置为DOMINATOR并

图2 各个角色之间的转换关系

下面以图3为例来说明算法构造支配集的过程。图3(a)中是一个简单的网络，我们选择节点1作为起始节点，将其角色设置为DOMINATOR，然后广播消息；节点2和3收到后，其角色变为DOMINATEE，然后分别广播消息；按照前文所述规则，节点4—9的角色都将转换为2一NEICHBOR，并各自广播消息。图3(b)中，节点10和11分别收到节点6和7的广播消息后，角色变为CANDIDATE，并根据节点的度建立定时器；同时，节点4、5和9发现所有邻居节点都已发送过消息，也各自建立定时器；节点5的定时器先触发(或节点4的定时器先触发)，则将其角色转换为DOMINATOR，并广播消息，节点4收到后将角色转换为DOMINATEE；而节点9在定时器触发后也将角色转换为DOMINATOR。图3(e)中，节点11的定时器先触发，随后节点10成为DOMINATEE，并广播消息。在图3(d)中，节点6收到节点10的消息后，发现所有邻居都已广播过消息，建立定时器。并最终也成为DOMINATOR。此时，节点6发送广播消息已经不会再触发新的广播消息，支配集生成完毕。