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