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