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

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

    图3 构建支配集的分布式算法简单示例

    2．3路径优化

    确定支配集后，基站还需要获取各个节点的位置信息，选择经过这些节点的一条较短的路径。在支配集构建时，可以将基站置于网络中任一节点处，并从该节点开始分布式算法，发送角色消息的同时在消息内包括从开始节点计算的跳数，从而可以不付出额外的通信代价建立起任意节点到开始节点的最短路径路由。各个DOMINATOR节点可以在确定自己的角色后通过多跳路由将位置信息传递回基站。此时，就可以将路径优化问题转换成旅行商问题，寻找一条最短的圈且经过每个点仅一次。然而，旅行商问题也被证明为NPhard问题。本文中使用kahng等提出的一种近似算法。该算法使用两次连续的匹配来选择完全图中的一部分边来将所有必须访问的位置连接起来。第一次匹配选择具有最小权重(本文中使用欧氏距离作为权重)的边，是每个位置仅与一条边相关联。在将这些边从图中清除后再进行第二次匹配。两次匹配所选择的边构成多个圈。然后。再将这些圈连接成一个大圈，即为算法的结果。在下一节中，我们将给出基于上述算法的仿真结果。

3 仿真评估

    本节中，我们提供了支配集构建和路径优化的仿真结果，并将本文的方法和基于树形结构的收集方法的负载分布也通过仿真进行了比较。在仿真设置中，选择了500×500单位长度的正方形区域作为传感器网络的部署区域。假定传感器的传输范围是圆形区域，通信半径为r=50。

    使用支配集的势和所需使用的消息总数作为指标，首先将2．2节中的算法与Wan等提出的算法进行了比较。在基本场景中，我们使用1000个随机分布的节点。通过改变节点数量使其从500变化到2000，模拟节点密度的变化。在每个场景下，我们进行10次仿真并取平均值作为实验结果。实验结果如图4所示。在图4(a)中，我们提出的算法所生成支配集的势比较稳定，而Wan等所提出算法的结果则随着节点数目的增加而略有增加。我们的结果具有更小的势，仅为Wan等结果的50％～60％。在图4(b)中，两种算法的通信消耗都随着节点数的增加而线性增长。我们的算法仅需要约占Wan等提出算法的50％的代价。我们的算法在支配集的势和通信消耗两个方面都优于Wan等提出的算法。随后，分别基于上文中两种算法的结果，使用kahng等提出的算法生成移动路径。同样改变节点数量从500到2000。在每个场景下，进行1O次仿真，并使用平均值进行比较。仿真结果如图5所示。两条曲线都随着节点数的变化而波动，其原因是拓扑结构是随机生成的，各个拓扑可能有不同的性质。但使用我们算法的结果要优于使用Wan等所提出算法的结果，即减少支配集的势确实有助于缩短移动路径的长度。

    图4支配集的势和通信代价比较

    图5 移动路径的长度

    我们分别对本文的方法与使用树形结构且静态基站位于网络中心的方法进行了仿真。仿真使用了具有2500个节点的网格拓扑。两种方案都需要构建最短路径树作为路由。此处我们忽略了构建最短路径树的通信消耗，而只考虑数据收集过程中的消耗。图6显示了我们提出的方案和基于树形结构收集方案在一次性收集所有节点上数据时的负载分布。其中X、y分别表示二维平面的坐标轴，使用基于树形结构的收集方法时，基站位于网络的中心位置。很容易看出我们的方案仅有极低的通信消耗且具有更均衡的负载分布。在图6(a)中，所有节点所需发送的消息数都不超过5，而在图6(b)中相当一部分节点需要发送超过100个消息。在图6(b)靠近中心位置处，有的节点需要发送的消息个数远远超出其他节点。正是这些节点的寿命限制了网络寿命。仿真结果显示我们的方案具有很好的可行性。与基于树形结构的收集方法相比，它具有低通信消耗和更平衡的负载分布。我们的方案不需要转发别的节点生成的数据，因此明显比其他联合使用移动基站和多跳路由方法更高效。

    图6 本文提出的方法和基于树形结构收集的负载分布

4 小结

    我们提出了一种基于移动基站而不使用多跳路由的数据收集方法。该方法结合了支配集相逢算法和旅行商问题的近似算法。仿真结果显示，所提出的支配集构造算法具有更低的通信消耗和更低势的支配集结果，并能生成更短的移动路径。所提出的数据收集方法还具有负载均衡分布的特性。此外，该方法不使用UDG等理想状态模型。从而具有很好的实用性。