三維無線移動(dòng)傳感器網(wǎng)絡(luò)k－覆蓋研究
加入技術(shù)交流群
為保持網(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所示。
移動(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)中額外的傳感器；
(5)根據(jù)弧(iout，jin)上的流將傳感器移動(dòng)到小立方體j。
其中，push-relabel(v)算法步驟為：
在算法中，節(jié)點(diǎn)只需要知道相距為D的鄰居節(jié)點(diǎn)信息(比如高度)，以此來執(zhí)行push-relabel算法。算法分為兩個(gè)步驟，在第一步中，節(jié)點(diǎn)將多余的流推入相鄰的鄰居節(jié)點(diǎn)，如果需要重標(biāo)記，則在第二步中，節(jié)點(diǎn)重新標(biāo)記自己，并通知相鄰的鄰居節(jié)點(diǎn)。在同一個(gè)小立方體i中iin和iout之間的推進(jìn)跟不同小立方體之間的推進(jìn)除了沒有信息傳送，其他都是一樣的。要注意的是推進(jìn)和重標(biāo)記過程只是發(fā)送信息，傳感器是沒有移動(dòng)的，只有在算法結(jié)束后，傳感器才根據(jù)弧上的流進(jìn)行移動(dòng)。
因?yàn)榫W(wǎng)絡(luò)圖
含有O(2L)個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)iout至多有O(D3)=O(logL)條出度弧，而每個(gè)iin只有一條出度弧(iin，iout)，因此圖
至多有O(Llog L+L)條弧。根據(jù)Goldberg A給出的同步分布式push-relabel算法，時(shí)間復(fù)雜度為O(|V|2)(V為節(jié)點(diǎn)個(gè)數(shù))，至多有O(|V|2ε)(ε為弧的數(shù)量)的信息交換量，又因?yàn)閕in和iout之間沒有信息交換，所以算法的時(shí)間復(fù)雜度為O(4L2)，信息交換量為O(L3log L)。4 仿真與分析
為了檢驗(yàn)理論的正確性，對(duì)移動(dòng)傳感器網(wǎng)絡(luò)k-覆蓋仿真。將網(wǎng)絡(luò)劃分為邊長
(r為傳感器半徑，k為覆蓋因子)的小立方體，將M=ΛL個(gè)移動(dòng)傳感器均勻于網(wǎng)絡(luò)中，其中Λ=O(k)。(具體的M值根據(jù)網(wǎng)絡(luò)中立方體的空缺總額來選定，只要超過空缺總額即可)。仿真結(jié)果如圖2所示。 
圖2表示對(duì)固定的k值(k=3)，隨著移動(dòng)距離的變化，不同規(guī)模網(wǎng)絡(luò)存在k覆蓋的概率(其中距離被dh規(guī)范化)。
評(píng)論