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