无线传感器网络由很多的微型传感器节点组成，已在多种监测运用中起到重要作用。在这些运用中，传感器节点通过多跳通讯将感知数据传输到基站。基站往往是一个停止节点，运用最短途径路由或其他路由办法收取数据。因而接近基站的节点需求比远离基站的点转发更多的数据，然后导致更快地耗尽能量并导致网络不再连通。这些节点一般被叫做“热门”。“热门”问题是传统的数据搜集协议所无法处理的问题。
最近几年，有学者提出运用移动性来处理上述问题。提出的战略可分为两类。第一类办法运用一个或数个移动基站在网络中随机行走并搜集数据。这类办法进行一次数据搜集所耗费的时刻是无法预期的。另一类办法企图将移动性和路由结合。基站被指定移动轨道和速度，然后使其方位能够被猜测，一起仍然通过多跳路由办法搜集数据。这类机制削减了数据推迟，但因为其较杂乱，因而难以在实践运用。此外，这些办法大多依据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一NE%&&&&&%HBOR，并各自播送音讯。图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发送播送音讯现已不会再触发新的播送音讯，分配集生成结束。
