三維無線移動(dòng)傳感器網(wǎng)絡(luò)k-覆蓋研究
加入技術(shù)交流群
3 分布式算法
由上文可知，傳感器移動(dòng)策略就是網(wǎng)絡(luò)最小花費(fèi)流問題，已對(duì)傳感器的最大移動(dòng)距離有了限制，所以，可以通過更簡(jiǎn)單的最大流問題找到可行的移動(dòng)策略來填補(bǔ)每個(gè)小立方體的空缺，而不考慮最小花費(fèi)的問題。關(guān)于網(wǎng)絡(luò)最大流問題有許多有效的算法，本文采取pushrelahcl分布式算法。
為保持網(wǎng)絡(luò)的連通性，假設(shè)傳感器的通信半徑大于傳感器半徑r的2倍。在算法執(zhí)行前，假設(shè)每個(gè)靜止或移動(dòng)傳感器知道它的位置和位于哪個(gè)小立方體里。隨機(jī)部署岳，考慮傳輸信息消牦能量的影響，每個(gè)單元周期性地選擇一個(gè)傳感器作為代表，收集算法執(zhí)行前需要的信息，信息形式如下：
其中：ID代表傳感器的標(biāo)志；cube表明傳感器在哪個(gè)小立方體里；x，y，z表示傳感器位于哪個(gè)位置信息，代表元會(huì)負(fù)責(zé)與圖G中的鄰居互傳信息。因?yàn)殡S機(jī)部署會(huì)產(chǎn)生某些單元沒有任何傳感器，為保持網(wǎng)絡(luò)的連通性，在算法執(zhí)行前將距離最近的傳感器移動(dòng)到空單元。
Push-relabel算法的基本思想是循環(huán)地選擇多余的流推進(jìn)到高度比它低的鄰居，若沒有則重新標(biāo)記高度，一直到所有的節(jié)點(diǎn)沒有多余的流。在算法中，把移動(dòng)傳感器從比k個(gè)傳感器多的小立方體中推向比k要小的小立方體中，并按如下方法來處理圖G(V，E)，將其轉(zhuǎn)換為有向圖
：將每個(gè)節(jié)點(diǎn)j∈V分裂成兩個(gè)節(jié)點(diǎn)iin和iout，并增加一條單向邊(iin，iout)，其移動(dòng)花費(fèi)為0，且容量約束為mi；iout是每一輪中的源節(jié)點(diǎn)，其出邊與鄰居節(jié)點(diǎn)j以單向邊(iout，jin)相連，移動(dòng)花費(fèi)為cij，容量約束為無窮大，如圖1所示。本文引用地址：http://www.ex-cimer.com/article/160780.htm
移動(dòng)算法步驟如下：
(1)對(duì)每個(gè)小立方體i進(jìn)行分布式移動(dòng)算法；
(2)收集每個(gè)小立方體的信息vi和mi；
(3)令h(iin)=0，h(iout)=0：e(iin)=0，e(iout)=mi-vi，其中h和e分別表示節(jié)點(diǎn)的高度和節(jié)點(diǎn)中額外的傳感器；
評(píng)論