三维无线移动传感器网络k－覆盖研究

为保持网络的连通性，假设传感器的通信半径大于传感器半径r的2倍。在算法执行前，假设每个静止或移动传感器知道它的位置和位于哪个小立方体里。随机部署岳，考虑传输信息消牦能量的影响，每个单元周期性地选择一个传感器作为代表，收集算法执行前需要的信息，信息形式如下：



其中：ID代表传感器的标志；cube表明传感器在哪个小立方体里；x，y，z表示传感器位于哪个位置信息，代表元会负责与图G中的邻居互传信息。因为随机部署会产生某些单元没有任何传感器，为保持网络的连通性，在算法执行前将距离最近的传感器移动到空单元。

Push-relabel算法的基本思想是循环地选择多余的流推进到高度比它低的邻居，若没有则重新标记高度，一直到所有的节点没有多余的流。在算法中，把移动传感器从比k个传感器多的小立方体中推向比k要小的小立方体中，并按如下方法来处理图G(V，E)，将其转换为有向图：

将每个节点j∈V分裂成两个节点iin和iout，并增加一条单向边(iin，iout)，其移动花费为0，且容量约束为mi；iout是每一轮中的源节点，其出边与邻居节点j以单向边(iout，jin)相连，移动花费为cij，容量约束为无穷大，如图1所示。



移动算法步骤如下：

(1)对每个小立方体i进行分布式移动算法；

(2)收集每个小立方体的信息vi和mi；

(3)令h(iin)=0，h(iout)=0：e(iin)=0，e(iout)=mi-vi，其中h和e分别表示节点的高度和节点中额外的传感器；



(5)根据弧(iout，jin)上的流将传感器移动到小立方体j。

其中，push-relabel(v)算法步骤为：



在算法中，节点只需要知道相距为D的邻居节点信息(比如高度)，以此来执行push-relabel算法。算法分为两个步骤，在第一步中，节点将多余的流推入相邻的邻居节点，如果需要重标记，则在第二步中，节点重新标记自己，并通知相邻的邻居节点。在同一个小立方体i中iin和iout之间的推进跟不同小立方体之间的推进除了没有信息传送，其他都是一样的。要注意的是推进和重标记过程只是发送信息，传感器是没有移动的，只有在算法结束后，传感器才根据弧上的流进行移动。

因为网络图含有O(2L)个节点，每个节点iout至多有O(D3)=O(logL)条出度弧，而每个iin只有一条出度弧(iin，iout)，因此图至多有O(Llog L+L)条弧。根据Goldberg A给出的同步分布式push-relabel算法，时间复杂度为O(|V|2)(V为节点个数)，至多有O(|V|2ε)(ε为弧的数量)的信息交换量，又因为iin和iout之间没有信息交换，所以算法的时间复杂度为O(4L2)，信息交换量为O(L3log L)。

4 仿真与分析

为了检验理论的正确性，对移动传感器网络k-覆盖仿真。将网络划分为边长(r为传感器半径，k为覆盖因子)的小立方体，将M=ΛL个移动传感器均匀于网络中，其中Λ=O(k)。(具体的M值根据网络中立方体的空缺总额来选定，只要超过空缺总额即可)。仿真结果如图2所示。



图2表示对固定的k值(k=3)，随着移动距离的变化，不同规模网络存在k覆盖的概率(其中距离被dh规范化)。