基于局部信息的移動感知網覆蓋方法

摘 要：移動感知網是一個由許多帶有傳感器的自主移動機器人組成的分布式傳感器網絡。為了更好地部署這些移動機器人節點，形成最大化覆蓋感知區域，提出了一種基于機器人局部信息的分布式感知網覆蓋方法。每個節點利用與鄰居節點之間的虛擬人工勢場產生的虛擬作用力來控制移動節點的運動和節點間的避碰，使移動節點能夠在允許的時間內，以較少的能量消耗移動到各自理想的位置。采用李亞普諾夫函數進行了感知網節點勢場梯度的理論分析，用計算機仿真實驗驗證了該方法的有效性，并與模擬退火算法進行了性能比較。

關鍵詞：移動感知網；覆蓋；虛擬力；多機器人；避碰

中圖分類號：TP242．6 文獻標志碼：A

文章編號：1001-3695(2008)07-2016-04



Coverage of mobile sensor networks based on local information

ZHOU Tong1，3， HONG Bingrong1， PIAO Songhao1， ZHOU Hongyu2

(1.School of Computer Science Technology， Harbin Institute of Technology， Harbin 150001， China；2.School of Mechanical Power Engineering， Harbin University of Science Technology， Harbin 150080， China；3.Heilongjiang Institute of Metrology， Harbin 150036， China)Abstract:Mobile sensor network is a distributed sensor networks which is composed of many autonomous mobile robots with sensors.Presented a new distributed coverage method of mobile robot nodes based local information in order to deploy these nodes for forming maximum coverage of sensing area. Utilised the forces resulted from virtual potential fields between these nodes to control the movement of mobile nodes and collision avoidance. By this way mobile nodes moved to each perfect position using a little energy consume in allowable time.Made theoretic analysis of mobile sensor networks potential gradient was made by Lyapunov function. Numeric simulation verified the valid of the method and compared the performance with simulated anneal algorithm. 

Key words:mobile sensor networks; coverage; virtual force; multirobot; collision avoidance

0 引言

感知網的首要任務就是感知環境，傳送感知數據，并進行進一步的處理^[1]。傳感器部署的好壞直接影響感知網的感知區域覆蓋性能。覆蓋問題是指區域覆蓋^[2]，它可被看做是系統服務質量的一個測量標準，當覆蓋率下降到一定閾值，感知網將不能正常發揮作用^[3]。 在大多數感知網的研究中，感知網使用的只是靜態節點^[4]，這種節點沒有移動功能，對感知網的魯棒性、容錯等有很大的限制。移動感知網是一個動態系統，能夠協作地實時監測、感知和采集各種環境或監測對象的信息，并對其進行處理，傳送這些信息到用戶。在部署移動傳感器節點方面已有許多研究，但它們大多數是基于集中式控制方法^[5，6]，然而在許多傳感器部署環境中，由于網絡分割很難組織成傳感器集群，使用一個中心服務器進行控制是不可行的，而且容易由于單個節點的失效而失敗，使用移動傳感器來幫助部署節點可以避免這個問題^[7]。在本文中，給作為節點的移動機器人裝備一些傳感器，組成一種移動感知網的形式，既考慮了感知網節點的重構，具有自適應功能，又能提高感知網的覆蓋性能。這種節點覆蓋方法是一種分布式方法，也是一種啟發式方法，無須集中控制，而且算法簡單、易操作，理論分析和仿真實驗均驗證了其可行性和高效性。 

1 問題描述

在一個面積為L×L柵格的二維正方形無障礙感知區域內，隨機地分布著n個可移動的傳感器（自主移動機器人），它們共同組成一個移動傳感器網絡，由于部署時的隨機性，使網絡的覆蓋率沒有達到預期的要求，這時n個移動節點將進行重新部署。本文的目的就是尋找一種快速可行的多移動機器人協調運動控制算法，使整個網絡的覆蓋率最大，同時移動機器人不能躍出所給定的邊界，并且移動節點所消耗的能量最低，用的時間最短。

假定移動機器人在二維平面U內運動，U={(x，y)T|x，y∈R}。其中：點q=(x，y)T為列向量形式；R代表全體實數集，U表示U的邊界。qi=(xi，yi)表示第i個移動機器人的坐標位置，i=0，1，2，…，n，qi∈R2。第i個機器人的驅動控制力用ui∈R2表示，i=0，1，2，…，n。

q¨i=ui(1)

由于機器人的傳感器和通信裝置的功能局限性，它的感知和通信范圍是有限的，每個機器人的感知半徑為sr，通信半徑為cr。

定義1 如果兩個機器人i， j，且i≠j，兩節點間的歐幾里得距離小于等于cr，

qij=‖qi-qj‖≤cr(2)

則這兩個節點為鄰居節點。

一個移動感知網的性能可以用感知區域的覆蓋率、節點分布的均勻性、節點覆蓋所需時間和節點移動的總距離來評價。

定義2 覆蓋率是所有機器人能夠感知的區域之和與待感知區域之比，可以用下式計算:

coverage=(∪i=1，…，nSi)/S(3)

其中：Si是節點i覆蓋的區域面積；S是感知區域總面積；n是總節點數。

定義3 節點分布均勻性用下式計算:

其中：n是節點數；ki是第i個節點的鄰居節點數；Di=(ki+1)/(π(cr)2)是第i個節點的局部密度；Da=n/L2是節點的平均密度。Uniformity越小越好，也就表示節點的分布更均勻。

定義4 運行時間time是感知網節點部署后達到穩定狀態時所耗費的總時間，此時間應盡量短。在用計算機仿真時，就是程序所運行的迭代步數。

定義5 移動距離distance是所有移動節點移動的總距離。由于節點是由移動機器人組成，由電池供電的機器人應該移動最短距離達到預定位置，這也是一個評價感知網標準的重要指標。所有移動節點運行的總距離可以用下式計算:

distance=tmaxt=1ni=1di(t)(5)

其中：tmax是感知網運行的總迭代步數；di是每個移動節點在每次運動中的移動距離。

2 節點覆蓋方法

2．1 虛擬力

人工勢場法被廣泛用于移動機器人的局部導航、避障、隊形控制和感知網的節點覆蓋^[8~10]。在本文中，把人工勢場法用于移動節點的覆蓋問題，這種方法模擬了電子勢場的概念，如果假設感知網中的每個節點都攜帶一個正電荷，就可以定義一個可量測的勢場，每個節點受到感知網中其他節點的排斥，這種排斥力使整個網絡中的所有移動節點向感知網中的其他地域擴散，最終達到平衡狀態，也就是達到了感知區域的最大覆蓋狀態。

在此引入兩種虛擬勢場力， 第i個機器人與它的有鄰居節點關系機器人之間的作用力為

其中：mi是第i個機器人的鄰居機器人總數；kR>0，是一個增益系數。D∈U，if dmin(qi-D)



其中：kB>0，是一個增益系數。qi受到qj的排斥力是它所處勢場的負梯度：

qi受到qj的排斥力與qj受到qi的排斥力是作用力與反作用力的關系，即

且有

其中：kd>0，是一個阻尼項。

使用李亞普諾夫函數作為系統內所有動能和勢能之和：

系統在沒有外力的作用下，保證系統最終穩定的條件是所有機器人所受的合力為0，即

2．2 節點勢場梯度分析

在多機器人網絡中，每個機器人可以在它的通信范圍內收到其他機器人的位置信息，也可以在感知范圍內感知到障礙物的位置信息。通過這些節點和障礙物的位置信息構成了此機器人的勢場，所有機器人的勢場之和就構成了感知網的勢場分布。

對于一個單獨的機器人，q¨i=ui，同時定義控制規則為

其中：T:R2→R為梯度勢場；kd＞0；η是一個常量控制參數。如果機器人在勢場的原點則梯度勢場T(qi)存在極小值。使用下面形式的李亞普諾夫函數容易證明在原點的漸近穩定性：

V(qi，i)=i×i/2+ηT(qi)(16)

其中η＞0。如果原點是惟一的，并且全局極小，那么全局漸近穩定性是存在的。

如果對一組機器人中的每個機器人使用同樣的控制規則，并且加入機器人之間的相互作用力，可得到下面的運動學方程:

q¨i=-kdi-ηΔT(qi)-mij=0FR(qij)(17)

其中：mi是第i個機器人在通信半徑范圍內所有鄰居機器人數目之和。因為由n個機器人組成的系統沒有受到外力作用，可以用李亞普諾夫函數作為表示系統的動能和勢能之和，而且在勢能中還包括勢場T的勢能:

微分方程為

把式(17)代入(19)得到

命題1 如果T是一個勢場函數，并且考慮一組機器人具有式(17)規定的控制規則，那么機器人系統將會達到一個穩定的平衡狀態。

證明 基于控制動力學的對稱性，應用LaSalle的不變性原理可以得出非孤立的平衡狀態集合具有收斂性，所有機器人相互間作用的勢場與環境勢場之和的極小值可以通過解式(17)來得到，此時q¨i=i=0，則式(17)為

由FR(qij)=-FR(qij)得到ni=1ΔT(qi)=0。因此只要所有機器人所受的環境勢場梯度之和為0，系統就能達到穩定狀態。 證畢。

命題2 假設T是一個徑向對稱梯度勢場，T=T(‖q‖)，在q=0有嚴格的全局極小值，T(‖q‖)是嚴格增加。例如對于所有的‖q‖＞0，T(‖q‖)/‖q‖＞0，那么對于具有式(17)能夠形成具有穩定凸形外殼隊形的n個機器人，所形成的勢場極小值在q=0處。

證明 對于一個給定的勢場T，穩定條件ni=1ΔT(qi)=0是指ni=1ai(‖qi‖)qi=0，且對于‖q‖＞0，ai＞0。如果對于某些i，qi=0，那么在機器人位置形成的凸形外殼中q=0是平凡解，所以考慮在i，qi≠0的情況。讓a=a1+…+an＞0，且bi=ai/a，那么b1+…+bn=1，所以ni=1bi(‖qi‖)qi=0，極小值在穩定狀態的凸形外殼內。證畢。

2．3 移動感知網覆蓋算法

移動感知網的覆蓋主要是移動節點的部署。因為節點通常是隨機部署的，通過節點的再部署可以達到節點分布的均勻性。因此，每個移動節點的運動只受當前位置的影響，每個移動節點都能適應環境的變化以自主移動的方式變化位置，以便能最大化感知網的覆蓋率和節點的均勻性。

每個移動節點都執行相同的算法，并且節點的移動是并行同步進行的。在每一次移動過程中，首先移動節點發送自己的位置坐標，并要求收到信息的所有節點回答自己的當前位置坐標，接收到這些信息后，按照相對位置計算所受的作用力，同時移動節點進行邊界的感知，也按照和邊界的相對位置計算所受的作用力，這樣就可以得到每個移動節點所受的合力。根據運動學方程，移動節點運動到新位置，重復這個過程直到循環結束。

移動感知網覆蓋算法（mobile sensornetwork coverage algorithm，MSCA）描述如下:

a)Initialize

input qi0;讀入第i個移動節點的初始位置坐標;

set sr;設置移動節點感知半徑;

set cr;設置移動節點通信半徑;

set t＝0;設置循環變量;

set tmax;設置最大循環次數;

while(t

b)Calculate virtual forces

移動節點所受虛擬力計算send(request，qi(t));在通信半徑cr范圍內對其他所有節點發送（回答請求，qi(t)）;

receive (reponse，qj);接收在cr范圍內的所有移動節點的（回應，qj）;

根據式(6)計算FRi;

detection;在感知半徑sr范圍內探測邊界障礙;

根據式(7)計算FBi;

計算Fi=FRi+FBi

c)Node move按照所受虛擬力進行移動

根據式(10)計算移動節點移動到qi(t＋1)位置，如果新位置在感知區域外，則停留在最近的邊界線上;

d)t=t+1;}

程序結束。

節點受到排斥力進行移動時，它不僅受運動學方程的限制，同時受到動力學方程的約束限制，在每個時間步長，即使受到的力很大，也只能按照動力學方程允許的最大移動距離移動。在仿真中，假設如果移動節點運動每次距離小于0.5 m，節點就不進行移動，以節約能量。

2．4 算法的計算復雜性分析

由上述算法可知，算法的基本運算為算法的步驟b)c）。步驟b)的時間復雜性為O(n(n-1))；步驟c)的時間復雜性為O(n2)。在有限次循環內完成節點部署后，總的時間復雜性為O(t(n(n-1)+n2))=O(n2)。

3 仿真實驗及分析

3．1 仿真實驗的建立

本文使用圖形化編程語言LabVIEW開發平臺編制了移動感知網節點部署的仿真程序。參數設置為L=100 m，cr=20 m，sr=10 m，tmax＝20，kR=kB=0.2，m=1，kd=1。選擇了不同節點數進行仿真：a）n=20;b)n=35;c)n=50。n代表移動節點數。

圖1所示是第n=35的節點運動軌跡仿真結果。在圖1中，網格狀區域表示待感知區域，小空心圓代表移動節點的初始位置，小實心圓表示經過20次迭代運算后，移動節點最終到達的位置。從圖1中可以看到，移動節點從傳感器密集區域運動到空曠的區域，從而使節點分布更均勻、節點的覆蓋范圍更大，并且可以看到機器人沒有發生任何碰撞。

3．2 感知網的性能分析

圖2是三種不同數目節點隨迭代次數變化的節點覆蓋率變化。在這三種情況下，移動節點不同，都是隨機分布在中心區域。從圖2的數據可以看出，在三種情況下覆蓋率都有提高，在n=50，由50個移動節點組成感知網，覆蓋率由12．6%提高到96.4%，并且在第14次迭代后感知網已達到穩定狀態，覆蓋率不再變化。其他兩種形式的感知網的覆蓋率也都有所提高，并且在20次迭代后基本達到了穩定狀態。從覆蓋率的變化可以發現，完全由移動節點組成的感知網覆蓋率提高得最大。

圖3所示是感知網節點均勻性隨迭代次數變化的曲線圖。根據感知網節點均勻性的定義， 三種不同數目節點形式都不同程度地提高了感知網的節點均勻性，每個節點都進行拓撲變化，從而達到最好的節點均勻分布狀態。圖4 所示是不同數目節點形式情況下每次迭代后，感知網移動節點運行的總距離，也可以近似代表移動節點的能量消耗。從圖4中可以看出，網絡覆蓋率的提高是以犧牲能量為代價的。

由移動節點組成的感知網可以達到最高的覆蓋率和分布均勻性，但在實際應用中，完全由移動節點組成感知網在成本上會遠遠高于完全由靜態節點組成的感知網，但靜態感知網最大的弱點是它不能進行再部署。在實際應用中，會由于節點失效或部署時的非均勻性造成網絡的傳輸分割，以至于不能工作，所以使用移動感知網可以極大提高網絡節點的再部署，從而使感知網的生命得以延長。

3．3 MSCA與模擬退火算法的性能比較

為了驗證所提出的MSCA性能的高效性，本文將MSCA與模擬退火算法(simulated annealing algorithm，SA)進行了性能比較。

SA中的主要參數與MSCA中的參數基本一致。在SA中，如果本次循環的移動節點運行總距離Dn小于上次循環的總距離Do，則接受本次節點運行過程，并作為新的運行方案；否則，以概率p=exp(-(Dn-Do)/T)接受本次運行方案。其中T是當前溫度。圖5是不同移動節點數時，最終達到覆蓋率的比較。雖然移動節點數不同，但從圖5中可以看出，MSCA在覆蓋率上略好于SA。

圖6是移動節點運行總距離的比較。從圖6可以看出，MSCA明顯好于SA，使用MSCA的節點部署運行的總距離要遠遠小于使用SA運行的總距離，相差一個數量級。這是因為MSCA是一種啟發式的算法，也是一種分布式算法；而SA中，每個移動節點作為一個粒子首先進行的是一種無序運動，而在退火階段才逐步達到有序運動，所以運行的距離要長，同時消耗了大量的能量。雖然使用SA也可以達到部署優化，但在實際應用中，這種方式是難以進行的。從實際應用的角度， MSCA是可取的。

4 結束語

本文基于機器人的局部信息和人工勢場法提出了一種移動感知節點的覆蓋方法，在理論上分析了它的可行性。在感知網中，移動節點具有移動的特性，對感知網節點的部署和重構具有很大的靈活性，在感知網絡的區域覆蓋上，比單純由靜態傳感器組成的感知網具有魯棒性。雖然人工勢場法存在局部極小的缺陷，但是通過仿真實驗可以看出，采用這種算法可以快速對感知區域進行節點覆蓋，也是一種分布式控制方法，對移動感知網的覆蓋率、均勻性都有很大的提高。這種覆蓋方法不需要預先知道環境地圖，無須進行集中控制，能夠實現動態網絡節點的調整，對于戰場或污染地區的偵察監控等實際應用領域有一定的現實意義。 

參考文獻：

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks:a survey[J].Computer Networks，2002，38(4): 393-422.

[2]MEGUERDICHIAN S，KOUSHANFAR F，POTKONJAK M，et al.Coverage problems in wireless Ad hoc sensor network[C]//Proc of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies.Anchorage:IEEE Press，2001:13801387.

[3]WATTENHOFER R，LI L，BAHL P，et al.Distributed topology control for wireless multihop Ad hoc networks[C]//Proc of the 20th Annual Joint Conference of the IEEE Computer and Commpunications Societies.Anchorage:IEEE Press，2001:13881397.

[4]LI Xiangyang，WAN Penjun，FRIEDER O.Coverage in wireless Ad hoc sensor networks[J].IEEE Trans on Computer，2003，52(6): 753763.

[5]HOWARD A，MATARIC M J，SUKHATME G S.An incremental selfdeployment algorithm for mobile sensor networks[J].Autonomous Robots，2002，13(2): 113126.

[6]ZOU Yi，CHAKRABARTY K.Sensor deployment and target localization based on virtual forces[C]//Proc of the 22nd Annual Joint Conference of the IEEE Computer and Commpunications Societies.San Francisco：IEEE Press，2003:12931303.

[7]WANG Guilin，CAO Guohong，La PORTAL T.Movementassisted sensor deployment[J].

IEEE Trans on Mobile Computing，2006，5(6):640-652.

[8]HOWARD A，MATARIC M J，SUKHATME G S.Mobile sensor network deployment using potential fields:a distributed，scalable solution to the area coverage problem[C]//Proc of the 6th International Symposium on Distributed Autonomous Robotics Systems.London:SpringerVerlag，2002:299-308.

[9]CORTES J，MARTINEZ S，KARATAS T，et al.Coverage control for mobile sensing networks[J].IEEE Trans on Robotics and Automation，2004，20(2): 243-255.

[10]HEO N，VARSHNEY P K.An intelligent deployment and clustering algorithm for a distributed mobile sensor network[C]//Proc of IEEE International Conference on Systems，Man and Cybernetics.Piscataway:IEEE Press，2003:4576-4581.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”