三維無線移動傳感器網絡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.104case.com/article/160780.htm
移動算法步驟如下：
(1)對每個小立方體i進行分布式移動算法；
(2)收集每個小立方體的信息vi和mi；
(3)令h(iin)=0，h(iout)=0：e(iin)=0，e(iout)=mi-vi，其中h和e分別表示節點的高度和節點中額外的傳感器；
評論