三維無線移動傳感器網(wǎng)絡k-覆蓋研究

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

0 引言
    無線移動傳感器網(wǎng)絡是由能量有限且具有感知、計算和通信能力的微型移動傳感器節(jié)點通過自組織的方式構(gòu)成的無線網(wǎng)絡。它不需要固定網(wǎng)絡支持，具有快速展開，抗毀性強等特點，可廣泛應用于軍事、工業(yè)、交通、環(huán)保等領域。然而，由于傳感器網(wǎng)絡通常工作在復雜的環(huán)境下，而且網(wǎng)絡中傳感器節(jié)點眾多，所以大都采用隨機部署方式。而這種方式很難一次性將數(shù)日眾多的傳感器節(jié)點放置在適合的位置，極容易造成傳感器網(wǎng)絡覆蓋的不合理。所以，在傳感器網(wǎng)絡部署初始，需要采用覆蓋控制策略的重新部署，以獲得理想的網(wǎng)絡覆蓋性能。其中滿足k-覆蓋是很多應用中需要重點考慮的。
    通常認為如果給定一個區(qū)域，若其中的任何一個點至少被k個傳感器覆蓋，則稱此傳感器網(wǎng)絡達到k-覆蓋。因為傳感器是移動的，所以它們可以調(diào)整自己的位置，以冗余度O(1)達到k-覆蓋。然而，由于移動消耗大量的能量，為節(jié)省能量，如何確定傳感器的最大移動距離呢?前人對此曾做過大量工作。Wu J等人最小化了每個傳感器的最大移動距離，但只號慮了二維網(wǎng)絡。wang G等人通過級聯(lián)式短距離移動雖然限制了每個傳感器，但也沒具體給出最大距離的一個界。因此，本文的研究目標是在三維無線傳感器網(wǎng)絡中，給出傳感器移動的最大距離的一個界，在此前提下，用分布式重新部署算法實現(xiàn)網(wǎng)絡k-覆蓋，證實其有效性。

1 傳感器的密度和移動距離
    假設移動傳感器獨立均勻分布于體積為L的立方體區(qū)域中，傳感器的傳感半徑為r，k為網(wǎng)絡覆蓋因子。將體積為L的立方體分解成邊長為的小立方體。顯然，其中每個格點的密度為。當傳感器移動到每個格點上時，移動傳感器的密度Λ為，每個傳感器的感應球域為，每個球域?qū)⒑袀€傳感器，所以區(qū)域中仟何一個點將至少被k個傳感器所覆蓋，即網(wǎng)絡達到k-覆蓋。當傳感器隨機撒播在立方體區(qū)域中，傳感器移動到每個格點的最大距離可以由以下定理得出。
    根據(jù)Ahuja RK給出的定理，將n個點均勻分布獨立撒播在一個單位立方體中，將單位立方體分解成n個小立方體，則點和格點之間以最大概率存在完全匹配，且匹配的最大距離為O((log，n／n)1／3)。
    因這里考慮的是體積為L的立方體，由上述定理可得網(wǎng)絡格點數(shù)目為 個。因此傳感器移動的最大移動距離約為 。由此可見，移動傳感器網(wǎng)絡相對靜態(tài)傳感器網(wǎng)絡能彌補節(jié)點分布的隨機性。在覆蓋過程中如果傳感器全部是移動的，那么它可以通過移動一小段距離達到k-覆蓋。相對靜態(tài)傳感器網(wǎng)絡，隨著出現(xiàn)網(wǎng)絡規(guī)模的擴大，傳感器的密度也會隨著增大的傾向，而移動傳感器網(wǎng)絡的傳感器密度卻仍能保持不變，只需隨著網(wǎng)絡的增大，移動距離改變?yōu)镺((log L)1／3)即可。

2 移動模型
    為了實現(xiàn)三維傳感器網(wǎng)絡k-覆蓋，提出傳感器移動策略問題如下：假設每個小立方體i含有mi個移動傳感器，每個立方體i將有vi=k個空缺。將傳感器移動問題轉(zhuǎn)化為網(wǎng)絡流問題，其中小立方體中多余的移動傳感器(網(wǎng)絡流)“流入”網(wǎng)絡圖中存在的空缺。
    構(gòu)造一個以每個小立方體為頂點的圖G(V，E)，當小立方體i和小立方體j中心間距小于D=O((log L)1／3)時，就在頂點i和j之間連接一條邊。將從i到j移動的傳感器數(shù)目記為xij，則移動策略問題可以表示為：
   
    式中：cij表示移動花費，簡單情況下表示所移動的距離。在這個優(yōu)化模型里，式(2)表示流守恒條件，即傳感器移出小立方體i的數(shù)目減去移進小立方體i的數(shù)目要小于或等于小立方體i額外的傳感器數(shù)目，這保證了移動后每個小立方體移動傳感器大于小立方體的空缺，即達到所要求的k覆蓋。式(3)則表示移出小立方體i的移動傳感器數(shù)目的總和要小于或等于它所擁有的移動傳感器的數(shù)目。
    用同樣構(gòu)造圖的方法，模型同樣適應于不規(guī)則形狀的網(wǎng)絡。[!--empirenews.page--]

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

    移動算法步驟如下：
    (1)對每個小立方體i進行分布式移動算法；
    (2)收集每個小立方體的信息vi和mi；
    (3)令h(iin)=0，h(iout)=0：e(iin)=0，e(iout)=mi-vi，其中h和e分別表示節(jié)點的高度和節(jié)點中額外的傳感器；
    [!--empirenews.page--]
    (5)根據(jù)弧(iout，jin)上的流將傳感器移動到小立方體j。
    其中，push-relabel(v)算法步驟為：

    在算法中，節(jié)點只需要知道相距為D的鄰居節(jié)點信息(比如高度)，以此來執(zhí)行push-relabel算法。算法分為兩個步驟，在第一步中，節(jié)點將多余的流推入相鄰的鄰居節(jié)點，如果需要重標記，則在第二步中，節(jié)點重新標記自己，并通知相鄰的鄰居節(jié)點。在同一個小立方體i中iin和iout之間的推進跟不同小立方體之間的推進除了沒有信息傳送，其他都是一樣的。要注意的是推進和重標記過程只是發(fā)送信息，傳感器是沒有移動的，只有在算法結(jié)束后，傳感器才根據(jù)弧上的流進行移動。
    因為網(wǎng)絡圖含有O(2L)個節(jié)點，每個節(jié)點iout至多有O(D3)=O(logL)條出度弧，而每個iin只有一條出度弧(iin，iout)，因此圖至多有O(Llog L+L)條弧。根據(jù)Goldberg A給出的同步分布式push-relabel算法，時間復雜度為O(|V|2)(V為節(jié)點個數(shù))，至多有O(|V|2ε)(ε為弧的數(shù)量)的信息交換量，又因為iin和iout之間沒有信息交換，所以算法的時間復雜度為O(4L2)，信息交換量為O(L3log L)。

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

    圖2表示對固定的k值(k=3)，隨著移動距離的變化，不同規(guī)模網(wǎng)絡存在k覆蓋的概率(其中距離被dh規(guī)范化)。
    由圖2可知，網(wǎng)絡從8×8×8增長到20×20×20的小立方體時，網(wǎng)絡達到k-覆蓋傳感器需移動的最大距離都為3dh。這說明，隨著網(wǎng)絡規(guī)模的增大，傳感器移動的最大距離增長微小。[!--empirenews.page--]
    在傳感器網(wǎng)絡仿真中，其算法性能如圖3所示。

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

5 結(jié)語
    本文在前人研究的基礎上給出了三維空間移動傳感器最大移動距離的一個界，并采用最大網(wǎng)絡流算法，實現(xiàn)了傳感器移動策略，減少了每個傳感器因移動消耗的能量，提高了網(wǎng)絡的覆蓋性能。但對于三維網(wǎng)絡達到k-覆蓋時傳感器的具體定位還有待于進一步研究。