三維無線移動傳感器網(wǎng)絡(luò)k－覆蓋研究
加入技術(shù)交流群
無線移動傳感器網(wǎng)絡(luò)是由能量有限且具有感知、計算和通信能力的微型移動傳感器節(jié)點通過自組織的方式構(gòu)成的無線網(wǎng)絡(luò)。它不需要固定網(wǎng)絡(luò)支持，具有快速展開，抗毀性強(qiáng)等特點，可廣泛應(yīng)用于軍事、工業(yè)、交通、環(huán)保等領(lǐng)域。然而，由于傳感器網(wǎng)絡(luò)通常工作在復(fù)雜的環(huán)境下，而且網(wǎng)絡(luò)中傳感器節(jié)點眾多，所以大都采用隨機(jī)部署方式。而這種方式很難一次性將數(shù)日眾多的傳感器節(jié)點放置在適合的位置，極容易造成傳感器網(wǎng)絡(luò)覆蓋的不合理。所以，在傳感器網(wǎng)絡(luò)部署初始，需要采用覆蓋控制策略的重新部署，以獲得理想的網(wǎng)絡(luò)覆蓋性能。其中滿足k-覆蓋是很多應(yīng)用中需要重點考慮的。
通常認(rèn)為如果給定一個區(qū)域，若其中的任何一個點至少被k個傳感器覆蓋，則稱此傳感器網(wǎng)絡(luò)達(dá)到k-覆蓋。因為傳感器是移動的，所以它們可以調(diào)整自己的位置，以冗余度O(1)達(dá)到k-覆蓋。然而，由于移動消耗大量的能量，為節(jié)省能量，如何確定傳感器的最大移動距離呢?前人對此曾做過大量工作。Wu J等人最小化了每個傳感器的最大移動距離，但只號慮了二維網(wǎng)絡(luò)。wang G等人通過級聯(lián)式短距離移動雖然限制了每個傳感器，但也沒具體給出最大距離的一個界。因此，本文的研究目標(biāo)是在三維無線傳感器網(wǎng)絡(luò)中，給出傳感器移動的最大距離的一個界，在此前提下，用分布式重新部署算法實現(xiàn)網(wǎng)絡(luò)k-覆蓋，證實其有效性。
1 傳感器的密度和移動距離
假設(shè)移動傳感器獨立均勻分布于體積為L的立方體區(qū)域中，傳感器的傳感半徑為r，k為網(wǎng)絡(luò)覆蓋因子。將體積為L的立方體分解成邊長為
的小立方體。顯然，其中每個格點的密度為
。當(dāng)傳感器移動到每個格點上時，移動傳感器的密度Λ為
，每個傳感器的感應(yīng)球域為
，每個球域?qū)⒑?img onload="if(this.width>620)this.width=620;" onclick="window.open(this.src)" style="cursor:pointer" height=31 alt=e.jpg src="http://editerupload.eepw.com.cn/fetch/20140414/238009_1_4.jpg" width=150 border=0>個傳感器，所以區(qū)域中仟何一個點將至少被k個傳感器所覆蓋，即網(wǎng)絡(luò)達(dá)到k-覆蓋。當(dāng)傳感器隨機(jī)撒播在立方體區(qū)域中，傳感器移動到每個格點的最大距離可以由以下定理得出。根據(jù)Ahuja RK給出的定理，將n個點均勻分布獨立撒播在一個單位立方體中，將單位立方體分解成n個小立方體，則點和格點之間以最大概率存在完全匹配，且匹配的最大距離為O((log，n／n)1／3)。
因這里考慮的是體積為L的立方體，由上述定理可得網(wǎng)絡(luò)格點數(shù)目為
個。因此傳感器移動的最大移動距離約為 
。由此可見，移動傳感器網(wǎng)絡(luò)相對靜態(tài)傳感器網(wǎng)絡(luò)能彌補節(jié)點分布的隨機(jī)性。在覆蓋過程中如果傳感器全部是移動的，那么它可以通過移動一小段距離達(dá)到k-覆蓋。相對靜態(tài)傳感器網(wǎng)絡(luò)，隨著出現(xiàn)網(wǎng)絡(luò)規(guī)模的擴(kuò)大，傳感器的密度也會隨著增大的傾向，而移動傳感器網(wǎng)絡(luò)的傳感器密度卻仍能保持不變，只需隨著網(wǎng)絡(luò)的增大，移動距離改變?yōu)镺((log L)1／3)即可。2 移動模型
為了實現(xiàn)三維傳感器網(wǎng)絡(luò)k-覆蓋，提出傳感器移動策略問題如下：假設(shè)每個小立方體i含有mi個移動傳感器，每個立方體i將有vi=k個空缺。將傳感器移動問題轉(zhuǎn)化為網(wǎng)絡(luò)流問題，其中小立方體中多余的移動傳感器(網(wǎng)絡(luò)流)“流入”網(wǎng)絡(luò)圖中存在的空缺。
構(gòu)造一個以每個小立方體為頂點的圖G(V，E)，當(dāng)小立方體i和小立方體j中心間距小于D=O((log L)1／3)時，就在頂點i和j之間連接一條邊。將從i到j(luò)移動的傳感器數(shù)目記為xij，則移動策略問題可以表示為：
式中：cij表示移動花費，簡單情況下表示所移動的距離。在這個優(yōu)化模型里，式(2)表示流守恒條件，即傳感器移出小立方體i的數(shù)目減去移進(jìn)小立方體i的數(shù)目要小于或等于小立方體i額外的傳感器數(shù)目，這保證了移動后每個小立方體移動傳感器大于小立方體的空缺，即達(dá)到所要求的k覆蓋。式(3)則表示移出小立方體i的移動傳感器數(shù)目的總和要小于或等于它所擁有的移動傳感器的數(shù)目。
用同樣構(gòu)造圖的方法，模型同樣適應(yīng)于不規(guī)則形狀的網(wǎng)絡(luò)。
3 分布式算法
由上文可知，傳感器移動策略就是網(wǎng)絡(luò)最小花費流問題，已對傳感器的最大移動距離有了限制，所以，可以通過更簡單的最大流問題找到可行的移動策略來填補每個小立方體的空缺，而不考慮最小花費的問題。關(guān)于網(wǎng)絡(luò)最大流問題有許多有效的算法，本文采取pushrelahcl分布式算法。
評論