三维无线移动传感器网络k-覆盖研究
3 分布式算法
由上文可知，传感器移动策略就是网络最小花费流问题，已对传感器的最大移动距离有了限制，所以，可以通过更简单的最大流问题找到可行的移动策略来填补每个小立方体的空缺，而不考虑最小花费的问题。关于网络最大流问题有许多有效的算法，本文采取pushrelahcl分布式算法。
为保持网络的连通性，假设传感器的通信半径大于传感器半径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所示。本文引用地址：http://www.eepw.com.cn/article/160780.htm
移动算法步骤如下：
(1)对每个小立方体i进行分布式移动算法；
(2)收集每个小立方体的信息vi和mi；
(3)令h(iin)=0，h(iout)=0：e(iin)=0，e(iout)=mi-vi，其中h和e分别表示节点的高度和节点中额外的传感器；
评论