三維無(wú)線(xiàn)移動(dòng)傳感器網(wǎng)絡(luò )k-覆蓋研究

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

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

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

2 移動(dòng)模型
為了實(shí)現三維傳感器網(wǎng)絡(luò )k-覆蓋，提出傳感器移動(dòng)策略問(wèn)題如下：假設每個(gè)小立方體i含有mi個(gè)移動(dòng)傳感器，每個(gè)立方體i將有vi=k個(gè)空缺。將傳感器移動(dòng)問(wèn)題轉化為網(wǎng)絡(luò )流問(wèn)題，其中小立方體中多余的移動(dòng)傳感器(網(wǎng)絡(luò )流)“流入”網(wǎng)絡(luò )圖中存在的空缺。
構造一個(gè)以每個(gè)小立方體為頂點(diǎn)的圖G(V，E)，當小立方體i和小立方體j中心間距小于D=O((log L)1／3)時(shí)，就在頂點(diǎn)i和j之間連接一條邊。將從i到j(luò )移動(dòng)的傳感器數目記為xij，則移動(dòng)策略問(wèn)題可以表示為：

式中：cij表示移動(dòng)花費，簡(jiǎn)單情況下表示所移動(dòng)的距離。在這個(gè)優(yōu)化模型里，式(2)表示流守恒條件，即傳感器移出小立方體i的數目減去移進(jìn)小立方體i的數目要小于或等于小立方體i額外的傳感器數目，這保證了移動(dòng)后每個(gè)小立方體移動(dòng)傳感器大于小立方體的空缺，即達到所要求的k覆蓋。式(3)則表示移出小立方體i的移動(dòng)傳感器數目的總和要小于或等于它所擁有的移動(dòng)傳感器的數目。
用同樣構造圖的方法，模型同樣適應于不規則形狀的網(wǎng)絡(luò )。