摘 要：考慮移動傳感器的移動會大量消耗能量且比較昂貴，使用密度為O(k)的移動傳感器來滿足網(wǎng)絡(luò)k-覆蓋的密度需求，并給出了網(wǎng)絡(luò)要達(dá)到k-覆蓋傳感器需移動的最大距離的一個(gè)界O((log L)1/3)；建立了三維網(wǎng)絡(luò)傳感器移動數(shù)學(xué)模型，將傳感器重新部署問題轉(zhuǎn)化為最大網(wǎng)絡(luò)流問題，用分布式重新部署算法仿真證明了其有效性。



關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)； k-覆蓋； 最大移動距離； 最大網(wǎng)絡(luò)流算法

中圖分類號：TN711-34; TP212.9

文獻(xiàn)標(biāo)識碼：A

文章編號：1004-373X(2012)01-0052-03

The K-coverage of three-dimensional wireless mobile sensor network



LIU Chun-mei

(Yangtze University College of Arts and Science， Jingzhou 434020， China)



Abstract：

Considering the mobile sensor is expensive and consumes a lot of energy on moving. A part of mobile sensor with density of O(k) was used to meet the demand of k-coverage of three dimensional network. To achieve k- coverage，it received the maximum moving distance for mobile sensor is O((log L)1/3) in a network with a size of L. At last， it established a mathematical mobility model for mobile sensors， and converted the sensor redeployment for k-coverage into maximum network flow problem. It is verified through experimental simulation by distributed relocation algorithm.



Keywords： wireless sensor network; k-coverage; maximum moving distance; maximum network flow algorithm





收稿日期：2011-09-21

0 引 言

無線移動傳感器網(wǎng)絡(luò)是由能量有限且具有感知、計(jì)算和通信能力的微型移動傳感器節(jié)點(diǎn)通過自組織的方式構(gòu)成的無線網(wǎng)絡(luò)。它不需要固定網(wǎng)絡(luò)支持，具有快速展開，抗毀性強(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è)傳感器覆蓋，則稱此傳感器網(wǎng)絡(luò)達(dá)到k-覆蓋。因?yàn)閭鞲衅魇且苿拥?，所以它們可以調(diào)整自己的位置，以冗余度O(1)達(dá)到k-覆蓋。然而，由于移動消耗大量的能量，為節(jié)省能量，如何確定傳感器的最大移動距離呢？前人對此曾做過大量工作。Wu J等人最小化了每個(gè)傳感器的最大移動距離[1]，但只考慮了二維網(wǎng)絡(luò)。Wang G等人通過級聯(lián)式短距離移動雖然限制了每個(gè)傳感器，但也沒具體給出最大距離的一個(gè)界[2]。因此，本文的研究目標(biāo)是在三維無線傳感器網(wǎng)絡(luò)中，給出傳感器移動的最大距離的一個(gè)界，在此前提下，用分布式重新部署算法實(shí)現(xiàn)網(wǎng)絡(luò)k-覆蓋，證實(shí)其有效性。

1 傳感器的密度和移動距離

假設(shè)移動傳感器獨(dú)立均勻分布于體積為L的立方體區(qū)域中，傳感器的傳感半徑為r，k為網(wǎng)絡(luò)覆蓋因子。將體積為L的立方體分解成邊長為2r33k的小立方體。顯然，其中每個(gè)格點(diǎn)的密度為1/2r33k3=32r3k。當(dāng)傳感器移動到每個(gè)格點(diǎn)上時(shí)，移動傳感器的密度Λ為32r3k，即338r3k，每個(gè)傳感器的感應(yīng)球域?yàn)?3πr3，每個(gè)球域?qū)⒑笑?8226;43πr3=32πk≥k個(gè)傳感器，所以區(qū)域中任何一個(gè)點(diǎn)將至少被k個(gè)傳感器所覆蓋，即網(wǎng)絡(luò)達(dá)到k-覆蓋。當(dāng)傳感器隨機(jī)撒播在立方體區(qū)域中，傳感器移動到每個(gè)格點(diǎn)的最大距離可以由以下定理得出。

根據(jù)Ahuja RK給出的定理[3]，將n個(gè)點(diǎn)均勻分布獨(dú)立撒播在一個(gè)單位立方體中，將單位立方體分解成n個(gè)小立方體，則點(diǎn)和格點(diǎn)之間以最大概率存在完全匹配，且匹配的最大距離為O((log n/n)1/3)。

因這里考慮的是體積為L的立方體，由上述定理可得網(wǎng)絡(luò)格點(diǎn)數(shù)目為L/2r33k3=kL#8226;338r3個(gè)。因此傳感器移動的最大移動距離約為O(log kL/kL)1/3#8226;L1/3=O13k(log kL)1/3。

由此可見，移動傳感器網(wǎng)絡(luò)相對靜態(tài)傳感器網(wǎng)絡(luò)能彌補(bǔ)節(jié)點(diǎn)分布的隨機(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 移動模型

為了實(shí)現(xiàn)三維傳感器網(wǎng)絡(luò)k-覆蓋，提出傳感器移動策略問題如下：假設(shè)每個(gè)小立方體i含有mi個(gè)移動傳感器，每個(gè)立方體i將有vi=k個(gè)空缺。將傳感器移動問題轉(zhuǎn)化為網(wǎng)絡(luò)流問題，其中小立方體中多余的移動傳感器(網(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ò)移動的傳感器數(shù)目記為xij，則移動策略問題可以表示為：

min imize∑i，jcij*xij

(1)

s.t. ∑jxij－∑jxji≤mi－vi i

(2)

∑jxij≤mi i

(3)

xij≥0 i，j

(4)

式中:cij表示移動花費(fèi)，簡單情況下表示所移動的距離。在這個(gè)優(yōu)化模型里，式(2)表示流守恒條件，即傳感器移出小立方體i的數(shù)目減去移進(jìn)小立方體i的數(shù)目要小于或等于小立方體i額外的傳感器數(shù)目，這保證了移動后每個(gè)小立方體移動傳感器大于小立方體的空缺，即達(dá)到所要求的k覆蓋。式(3)則表示移出小立方體i的移動傳感器數(shù)目的總和要小于或等于它所擁有的移動傳感器的數(shù)目。

用同樣構(gòu)造圖的方法，模型同樣適應(yīng)于不規(guī)則形狀的網(wǎng)絡(luò)。

3 分布式算法

由上文可知，傳感器移動策略就是網(wǎng)絡(luò)最小花費(fèi)流問題，已對傳感器的最大移動距離有了限制，所以，可以通過更簡單的最大流問題找到可行的移動策略來填補(bǔ)每個(gè)小立方體的空缺，而不考慮最小花費(fèi)的問題。關(guān)于網(wǎng)絡(luò)最大流問題有許多有效的算法[4]，本文采取push-relabel分布式算法。

為保持網(wǎng)絡(luò)的連通性，假設(shè)傳感器的通信半徑大于傳感器半徑r的2倍。在算法執(zhí)行前，假設(shè)每個(gè)靜止或移動傳感器知道它的位置和位于哪個(gè)小立方體里。隨機(jī)部署后，考慮傳輸信息消耗能量的影響，每個(gè)單元周期性地選擇一個(gè)傳感器作為代表，收集算法執(zhí)行前需要的信息，信息形式如下:

IDcubexyz



其中：ID代表傳感器的標(biāo)志;cube表明傳感器在哪個(gè)小立方體里;x，y，z表示傳感器位于哪個(gè)位置信息，代表元會負(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個(gè)傳感器多的小立方體中推向比k要小的小立方體中，并按如下方法來處理圖G(V，E)，將其轉(zhuǎn)換為有向圖(V′，)：

將每個(gè)節(jié)點(diǎn)i∈V分裂成兩個(gè)節(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所示。

圖1 節(jié)點(diǎn)分裂圖

移動算法步驟如下:

(1) 對每個(gè)小立方體i進(jìn)行分布式移動算法；

(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)中額外的傳感器；

(4) while v∈V′且e(v)>0

push-relabel(iin);

push-relabel(iout);

endwhile

(5) 根據(jù)弧(iout，jin)上的流將傳感器移動到小立方體j。

其中，push-relabel(v)算法步驟為：



if(e(v)>0)

whilearc(v，w)s.t.h(v)=h(w)+1 and cap(v，w)>0，(其中cap表示容量約束)

則將y=min{e(v)，cap(v，w)}個(gè)單位的流從節(jié)點(diǎn)v推進(jìn)到節(jié)點(diǎn)w(注意：這里的推進(jìn)是通過發(fā)送信息給w的鄰居節(jié)點(diǎn)來實(shí)現(xiàn)的)；使得e(v)=e(w)－y;e(w)=e(v)+y；并更新cap(v，w)；否則令h(v)=min{h(w)+1|arc(v，w)∈且cap(v，w)>0}，并把h(v)廣播給相距D的鄰居節(jié)點(diǎn)；

endwhile

endif



在算法中，節(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ā)送信息，傳感器是沒有移動的，只有在算法結(jié)束后，傳感器才根據(jù)弧上的流進(jìn)行移動。

因?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ù)量)的信息交換量[5]，又因?yàn)閕in和iout之間沒有信息交換，所以算法的時(shí)間復(fù)雜度為O(4L2)，信息交換量為O(L3log L)。

4 仿真與分析

為了檢驗(yàn)理論的正確性，對移動傳感器網(wǎng)絡(luò)k-覆蓋仿真。將網(wǎng)絡(luò)劃分為邊長dh=2r33k(r為傳感器半徑，k為覆蓋因子)的小立方體，將M=ΛL個(gè)移動傳感器均勻于網(wǎng)絡(luò)中，其中Λ=O(k)。(具體的M值根據(jù)網(wǎng)絡(luò)中立方體的空缺總額來選定，只要超過空缺總額即可)。仿真結(jié)果如圖2所示。

圖2表示對固定的k值(k=3)，隨著移動距離的變化，不同規(guī)模網(wǎng)絡(luò)存在k覆蓋的概率 (其中距離被dh規(guī)范化)。

由圖2可知，網(wǎng)絡(luò)從8×8×8增長到20×20×20的小立方體時(shí)，網(wǎng)絡(luò)達(dá)到k-覆蓋傳感器需移動的最大距離都為3dh。這說明，隨著網(wǎng)絡(luò)規(guī)模的增大，傳感器移動的最大距離增長微小。



圖2 傳感器移動距離與網(wǎng)絡(luò)存在k-覆蓋的概率關(guān)系

在傳感器網(wǎng)絡(luò)仿真中，其算法性能如圖3所示。

圖3 算法性能

圖3表示當(dāng)k=10，D=4時(shí)，隨著網(wǎng)絡(luò)規(guī)模的增大，push-relabled算法的性能。

在上文中，分析了push-relabel算法的時(shí)間復(fù)雜度為O(4L2)。但從實(shí)驗(yàn)結(jié)果(如圖3(a)所示)可以看出，算法的平均和最大時(shí)間復(fù)雜度與L呈線性關(guān)系，如當(dāng)網(wǎng)絡(luò)大小為8 000時(shí)，平均只需要1 000輪便可得到解。從圖3(b)曲線來看，網(wǎng)絡(luò)中所有節(jié)點(diǎn)發(fā)送信息量的總和隨著網(wǎng)絡(luò)規(guī)模的增大呈O(L2+α)(0<α<1)增長，比上文分析的總的信息交換量O(L3log L)要好。由此可知，通過對算法的改進(jìn)，算法在實(shí)際運(yùn)行中總的性能比push-relabel算法要好一些。

5 結(jié) 語

本文在前人研究的基礎(chǔ)上給出了三維空間移動傳

感器最大移動距離的一個(gè)界，并采用最大網(wǎng)絡(luò)流算法，實(shí)現(xiàn)了傳感器移動策略，減少了每個(gè)傳感器因移動消耗

的能量，提高了網(wǎng)絡(luò)的覆蓋性能。但對于三維網(wǎng)絡(luò)達(dá)到k-覆蓋時(shí)傳感器的具體定位還有待于進(jìn)一步研究。

參 考 文 獻(xiàn)

［1］WU J， YANG S. Smart: A scan-based movement-assisted sensor deployment method in wireless sensor networks [C]// Proc. IEEE INFOCOM. [S.l.]: IEEE， 2005: 2313-2324.



［2］WANG G， CAO G， PORTA T L. Proxy-based sensor deployment for mobile sensor networks [C]. [S.l.]: Proc. First IEEE Int′l Conf. Mobile Ad-Hoc and Sensor System(MASS)， 2004.



［3］AHUJA R K， MAGNANTI T L， ORLIN J B. Network flows: theory， algorithms， and application [M]. [S.l.]: Prentice Hall， 1993.



［4］CORMEN T H， LEISERSON C E， RIVEST R L， et al. Introduction to algorithms [M]. Second ed. [S.l.]: MIT Press and McGraw-Hill， 2001.



［5］GOLDBERG A， TARJAN R. A new approach to the maximum-flow problem [J]. ACM， 1988， 35(4): 921-940.



［6］WANG W， SRINIVASAN V， Chua K C. Coverage in hybrid mobile sensor networks mobile computing [J]. IEEE Transactions， 2008， 7(11): 1374-1387.



［7］RAVELOMANANA V. Extremal properties of three-dimensional sensor networks with application [J]. IEEE Trans. on Mobile Computing， 2004， 3(3): 246-257.



［8］TAREK E S， NIDAL N. Routing in three dimensional wireless sensor networks [C]. [S.l.]: GLOBLECOM， 2008.



［9］HUANG C F， TSENG Y C， LO L C. The coverage problem in three-dimensional wireless sensor networks [C]// IEEE GLOBECOM. [S.l.]: IEEE， 2004: 3182-3186.



［10］SHOR P W， YUKICH J E. Minimax grid matching and empirical measures [J]. The Annals of Probability， 1991， 19(3): 1338-1348.



［11］CHELLAPPAN S， BAI X， MA B， et al. Sensor networks deployment using flip-based sensors [C]. [S.l.]: Proc. Second IEEE Int′l Conf. Mobile Ad-Hoc and Sensor Systems(MASS)， 2005.



作者簡介：

劉春梅 女，1984年出生，湖南漣源人，碩士，教師。主要研究方向?yàn)檫\(yùn)籌學(xué)在信息網(wǎng)絡(luò)中的運(yùn)用、信息管理與信息系統(tǒng)研究等。