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

标志节点当前在支配集构造过程中的状态。定义节点角色可能的取值如下：

·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发送广播消息已经不会再触发新的广播消息，支配集生成完毕。

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

2．3路径优化

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

3 仿真评估

本节中，我们提供了支配集构建和路径优化的仿真结果，并将本文的方法和基于树形结构的收集方法的负载分布也通过仿真进行了比较。在仿真设置中，选择了500&ti