移動傳感網分布式連通按需覆蓋部署方法

毛凌楚，趙海濤

(國防科學技術大學 電子科學與工程學院，長沙 410073)(*通信作者電子郵箱maolc@126.com)

移動傳感網分布式連通按需覆蓋部署方法

毛凌楚*，趙海濤

(國防科學技術大學 電子科學與工程學院，長沙 410073)(*通信作者電子郵箱maolc@126.com)

針對移動傳感器網絡監測區域中目標覆蓋所需傳感器數不同且各目標之間沒有形成通路的問題，提出了通過虛擬力方法實現對不同目標的按需覆蓋方法。根據不同目標的覆蓋需求設置對傳感器節點的基于萬有引力的吸引力、節點之間基于庫侖力的斥力以及目標之間的引力線，節點在虛擬合力的引導下覆蓋目標或連接成通路。仿真結果顯示所提方法與已有代表性算法相比收斂時間短，節點移動公平性高達99%，且GPS誤差的影響能夠控制在1%以下，可實現稀疏或密集初始條件下按需覆蓋的分布式快速部署。

移動傳感網；按需覆蓋；虛擬力；引力線

0 引言

移動傳感器網絡在現代信息技術中是必不可少的一部分。通常人為部署傳感器時會以對區域的均勻覆蓋為目標，但是在移動傳感網的現實應用中，對于一片區域的覆蓋需求通常不是均勻的。這就是說，在監測區域中存在部分目標由于需求較高需要更多的節點對其進行重點覆蓋，而另一些目標則可以部署相對較少的節點。那么，根據實際的覆蓋需求調整節點的部署就可以實現對監測區域的按需覆蓋，這樣的覆蓋方案更符合實際應用。在實際的應用中，傳感器網絡對于信息傳遞的通暢有一定的要求，需要各傳感器節點能夠連通起來，在整個網絡的各個目標之間保持通信鏈路，這在網絡的部署中也是要考慮的一個重要的問題。例如在無網絡覆蓋的地方或因大型集會等突發狀況需要臨時提供網絡服務時，根據任務需求按需部署網絡并保證網絡的連通是值得注意的一個應用場景；或者在現代信息化戰場上的無人機集群等多節點的戰場環境感知，這些都是潛在的應用場景。

在這方面前人做了許多的研究工作。文獻[1]提出了一種基于Voronoi多邊形[2-3]形心的部署策略，將對區域的覆蓋轉換為各節點對其所劃分的Voronoi多邊形的覆蓋進行處理，但其對于質心[1]和區域劃分的計算較復雜。文獻[4]采用MW-Voronoi(Multiplicatively Weighted Voronoi)圖分割目標區域，各節點在所受的虛擬力[5]的作用下運動，但由于子區間包含曲線邊界，所以算法復雜度較大。文獻[6]提出了一種基于VL(Voronoi Laguerre)圖[7]分割的節點自主部署算法(Autonomous Deployment Algorithm, ADA)，該算法需要將節點分為兩類采用不同的方法進行處理，且需要全局信息支持。在采用虛擬力的方法上，Howard等[8]將運動機器人路徑規劃的虛擬勢場[9-10]方法引入傳感器節點的部署中，在移動節點的再部署中收獲了較好的效果，但是其必須在所有節點始終保持聯系的情況下執行。Zou[11]提出一種虛擬力算法，解決了節點初始隨機部署后的自動完善網絡覆蓋性能的問題，可以均勻網絡覆蓋提高覆蓋率，但是需要簇頭節點控制，不能分布式部署[12]。文獻[13]提出了一種基于虛擬力的傳感器節點移動算法，該算法模擬自然界中的引力和斥力來指導節點的移動，適用于密集初始條件或稀疏初始條件，但收斂速度較慢，且最終形成的部署結構在各節點之間存在覆蓋空洞。前人的研究針對不同的場景作了相應的優化，但是算法結構較復雜，且不能實現無縫覆蓋。文獻[14]提出結合傳統的兩種控制方法的半聚群控制方法，既能對目標進行集中覆蓋，同時又保留一部分游離的節點去探索區域，使得覆蓋更加合理。但是，該方法沒有考慮到各目標之間的傳感器節點的通信，整個網絡沒有連接成一個整體，增加了信息的收集和傳遞的成本。本文在文獻[13]和[14]的基礎上提出基于虛擬力場的移動傳感器網絡分布式連通按需覆蓋部署方案，按覆蓋需求設置目標對節點的引力和節點間的斥力，引入目標之間的引力線，通過節點的分布式計算和移動，實現對不同需求區域的動態按需覆蓋和節點之間的通信連通，同時在無縫覆蓋區域的前提下覆蓋面積最大，且節點移動公平性較高，全球定位系統(Global Positioning System, GPS)誤差容忍性較好。

1 問題描述

在一個二維矩形L×W平面監測區域Ω?R2內部署N個移動傳感器節點S={s1,s2,…,si,…,sN}。對該平面區域，以矩形左下角的頂點為坐標原點，水平向右為X軸正方向，豎直向上為Y軸正方向建立笛卡爾坐標系。對S中任意節點si，其位置坐標為(xi,yi)，感知范圍為以節點位置為圓心，感知半徑R為半徑的圓，其通信范圍為半徑2R的圓。區域中需要節點覆蓋的M個目標記為C={c1,c2,…,ck,…,cM}(此處的目標既可以是單個個體，也可以是一片熱點區域的幾何或業務中心)，這是節點僅需要知道的全局信息(在節點散播前預置，或通過接收廣播獲得)，其他的信息全部通過分布式交互獲得(例如節點通過廣播帶有其位置信息的HELLO包給鄰居節點，通信范圍內的鄰居節點返回帶有本身位置信息的ACK使得節點之間可以共享位置信息。而HELLO包在許多通信協議中都有廣泛應用，這也不會增加網絡的額外負載。因此，整個系統不需要中心控制，節點的位置信息通過節點之間的交互傳遞，是完全分布式的)。初始時將若干節點或集中或分散地隨機拋撒入區域中，之后節點根據分布式計算逐漸調整部署，使得所有節點根據目標的覆蓋需求大小對其進行相應的覆蓋，對覆蓋需求高的部署更多節點，反之則部署較少節點。部署完成時，要求節點覆蓋的范圍盡可能大，節點之間不能出現覆蓋空洞，且各目標之間的節點應保持通信連接。

2 按需部署算法

對于移動傳感網中節點自主按需覆蓋部署，本文借鑒了虛擬力體系的思想，但是本文的設計思路和應對場景與之前的研究有所不同：1)不同于以往均勻的覆蓋，本文針對的場景是目標的動態按需覆蓋，更符合實際應用場景；2)本文的方法可以保持各個目標之間節點的通信連接；3)傳統方法所借鑒的虛擬力不適用于動態按需覆蓋場景，本文重新進行了設計，且本文的虛擬力設置思路不是通常的受力平衡，而是用虛擬力指導節點運動，最后利用幾何方法確定節點間的距離；4)本文的部署方法同時適用于初始時節點是集中的和隨機分散的情況。

2.1 虛擬力設置

對于處在虛擬力場中的節點而言，如果只受到單一的虛擬力是難以趨于穩定的。所以在這個虛擬力場中，應該有多種虛擬力共同作用來使節點部署到預期的狀態。虛擬力通常可以分為兩類：引力和斥力。引力可以使節點聚集，將節點引向需要其部署的位置。節點間的斥力可以使得節點的分布分散開來，減少過多的重復覆蓋，提高覆蓋率。應該明確的是，虛擬力都是矢量，要考慮大小和方向。

關于虛擬力整體的設計思路是：由目標產生范圍較大但是大小較小的引力，將區域中的節點吸引到目標附近；在節點間距離較近時，各節點兩兩之間產生相互的斥力，斥力的值較大，但作用范圍較小，通過控制斥力的作用范圍來調整節點之間的分散程度；另外，引入連接兩個目標的虛擬引力線，節點受到引力線的引力向引力線運動，并在引力線上連成一條線，像一條電話線將兩個目標周圍的節點連接起來。

如圖1為一種可能的節點受力情況示意。

圖1 一種虛擬力示例

圖1中所示s1、s2、s3、s4為四個節點，s1和s2之間由于距離過近產生了斥力F12，s1和s4之間由于距離過遠產生了引力F14，而節點s1和s3之間的虛擬力F13為零，故s1所受合力如圖中F1所示。

2.1.1 目標引力

需要覆蓋的目標產生在監測區域內指向目標的引力場，在它的影響下，監測區域內所有的節點都會受到指向目標的引力，將節點“拉”向目標運動，從而使這些節點聚集在目標的附近。

1)對于引力的方向，顯然目標產生的引力方向在監測區域內任何一點都應該是指向目標的。

2)對于引力的大小，借鑒萬有引力定律，可以設置為與到目標的距離的平方成反比，比例系數則反映覆蓋需求。這就意味著，距離目標越遠，節點所受的引力越小。特別是這樣的設置在按需覆蓋中應用更合理，因為在按需覆蓋中有多個目標待考察，以兩個目標為例，若節點所受的引力大小與其和目標的距離呈線性關系的話，就會導致節點不聚集在目標附近，而是聚集在兩個目標連線之間的某一點上。而采用上述設置方法時，節點會向引力較大的目標方向移動，在移動過程中，其所受到的目標方向的引力逐漸變大，而來自其他目標的引力迅速減小，可以聚集在產生引力的目標附近，避免了節點停留在目標之間某處。

由于在平面坐標系中研究虛擬力場，所以對于虛擬力矢量來說，表示成沿坐標軸的分量更加清晰明了，也便于計算。那么，目標產生的虛擬引力就可以表示為：

X方向：

Fax=Ka×(Δxa/d2)

(1)

Y方向：

Fay=Ka×(Δya/d2)

(2)

其中：Ka為引力系數，d為目標到基站的距離，Δxa和Δya分別表示由節點指向中心的單位方向矢量的X和Y方向的分量。

式(1)、(2)中的引力系數Ka可以根據不同的目標設置不同的值，甚至可以利用相關參數建模成量化的通信或感知等需求。當需求變化時，節點受力隨之變化，從而動態調整。這一引力的設置方法可以同時適用于初始情況下節點分布較集中的密集初始條件或節點分布較分散的稀疏初始條件，有利于網絡的連通性。

2.1.2 節點斥力

僅有引力的作用會導致節點重疊在一起，為了解決這一問題，引入節點間的相互斥力使節點彼此分散開以提高覆蓋率。與引力不同，斥力的產生作用的范圍較小，只有在兩節點距離較近時才產生作用。以下將以一對鄰居節點si和sj為例，分別對斥力的方向、大小和作用范圍進行討論。

1)對于節點間斥力方向的設置，是沿兩節點連線指向外側，對于節點si來說，它受到的來自鄰居節點sj的斥力的方向就是從sj指向si的。

2)對于節點間斥力的大小，借鑒庫侖力思想，將其大小設置為與兩節點間的距離平方成反比，比例系數設置為遠大于目標引力的值。這樣設計節點間的斥力要比目標產生的引力大得多，以至于可以將節點視為剛體，經過引力吸引到一起之后被斥力嚴格控制距離，那么只要調整斥力的作用距離就可以設置各節點的分散程度，從而控制節點的覆蓋率。如此，節點間斥力的大小可以表示為：

Fr=Kr/dij2

(3)

其中：Kr為斥力系數，dij為兩節點si和sj間的距離。

3)對于節點間斥力作用范圍的設置，在此方案的設計中決定了它們的重疊面積從而影響了整體覆蓋率。通常認為的最佳的覆蓋方式是無縫覆蓋的同時重疊覆蓋的面積盡可能小。那么根據幾何學的有關知識，多個相同的圓實現無縫覆蓋平面區域主要有如圖2所示的幾種設置方法。

圖2 無縫覆蓋的三種方案

由圖2可見，在無縫覆蓋的幾種方式中圖2(a)所示的是最佳的方案，這種設置方法在實現無縫覆蓋的同時，重疊的面積最小，也就是說其覆蓋的范圍最大，故以此方案為參考設置基站間產生斥力的距離。

綜上所述，節點間的斥力可以表示為：

X方向：

Frx=Kr×Δxr/dij2

(4)

Y方向：

Fry=Kr×Δyr/dij2

(5)

其產生作用的距離為：

(6)

其中，Kr為斥力系數，Δxr和Δyr分別為節點sj指向si單位距離矢量的X方向分量和Y方向分量，dij為其距離標量，R為節點覆蓋半徑。

2.1.3 引力線

上述虛擬力的設置只能實現目標的按需覆蓋，為了將各目標間的傳感器節點通信連接起來，引入引力線的方法。

將某兩個目標所確定的直線或線段稱為引力線，引力線實際上并不存在，只是用來指導節點的運動。一定范圍內的節點會受到垂直指向引力線的虛擬引力作用而靠近引力線。當節點運動到引力線附近時，可能出現節點在引力線附近振蕩的情況，所以在引力線上設置較窄寬度的“真空帶”，當節點運動到“真空帶”內則不受引力線的虛擬力。需要注意的是，當目標數增多時，引力線也會隨之增加，可能導致局部受力情況過于復雜。為了避免這一現象出現，每個節點可以在初始狀態時先判斷距離自己最近的引力線，在之后的調整中則只受到該引力線的作用，這樣可以簡化節點的受力情況，但同時并不影響部署效果。引力線產生的引力的大小與目標引力的設置相同，與節點到引力線的距離的平方成反比，如下：

X方向：

Flx=Kl×Δxl/dl2

(7)

Y方向：

Fly=Kl×Δyl/dl2

(8)

其中：Kl為引力線引力系數，dl為節點到引力線的距離，Δxl和Δyl分別表示由節點垂直指向引力線的單位方向矢量的X和Y方向的分量。

如圖3所示，c1、c2為兩個目標，L為過兩目標的引力線，節點s1受到其引力Fl的作用垂直向引力線運動，當節點運動到“真空帶”，即外側的兩條虛線之間的時候，則不再受到引力線的引力，可能受到其他節點的斥力而沿著引力線運動，使得各節點沿引力線排列開來，從而連接兩個目標之間的其他節點。

圖3 引力線示意圖

2.2 算法步驟

初始情況是，在某一L×W的平面監測區域內，分布著若干或集中或分散的節點，以及待覆蓋的若干目標。這時所有節點在當前所處的情況計算一次在監測區域內受到的虛擬力的合作用力，根據所受的合力進行一定量的移動，然后節點再根據新的位置進行同樣的計算，如此重復迭代計算直到部署完成。

上文介紹了整個監測區域中虛擬力場主要由目標產生的引力、引力線的引力和節點間的相互斥力構成，那么節點所受的合力就是它們的矢量和，具體對于某節點si，其所受的合力可以表示為：

X方向：

(9)

Y方向：

(10)

其中:第一項表示節點i受到來自目標ck的引力的分量之和，第二項表示節點i受到來自鄰居節點j的斥力的分量之和，第三項表示節點受到引力線的引力。

由于上述合力是矢量和，所以通過計算合力可以得到節點需要移動的方向和距離，但是由于節點間斥力較大，節點所受的合力的值可能較大，故其所受合力的標量不能直接作為其移動的距離值，還需要對其移動距離和合力的關系進行合理的設置，控制其上限。考慮到反正切函數存在上界的情況，此處將節點所受合力的標量值作為反正切函數的自變量進行處理，即如下所示：

(11)

其中：li為節點si單次移動的距離[15]，Fix和Fiy分別為節點si所受的合力的X方向和Y方向分量，b為節點移動步進。上式可以將節點的移動距離上界限制在b。

此外，由于節點分布的隨機性，在部署接近完成時，可能出現節點位置振蕩而難以趨于穩定的情況。針對這一情況，可以采用節點移動步進b來控制算法的收斂，實際應用時應根據具體環境設置b的值，例如隨迭代次數增加而衰減或與實際節點移動的速度有關。此外還應設置節點移動停止門限δ，當節點計算得到移動的距離小于δ時認為達到穩定狀態，節點停止移動[16]，這也可以較好地避免節點振蕩的情況。

節點移動的方向即其所受合力的方向，那么根據計算的節點移動距離和方向在節點原坐標的基礎上進行更新即可得到移動后的新的位置坐標。

算法的步驟如下：

1)

初始化設置：監測區域范圍L×W，目標位置C，區域內節點集S，節點初始位置，節點覆蓋半徑R，初始迭代次數n=0，最大迭代次數nmax，節點移動步進b，移動停止門限δ。

2)

Whilen

3)

Forn

4)

Forsi∈S

5)

計算節點距離最近的引力線

6)

計算節點受到引力線的引力

7)

Forck∈C

8)

分別計算ck對節點的X方向和Y方向引力

9)

End for

10)

Forsj∈S≠si

11)

12)

節點間斥力Fr=0

13)

Else

14)

分別計算節點sj對si的斥力的X方向分量和Y方向分量

15)

End if

16)

End for

17)

計算節點si所受的合力的X和Y方向分量

18)

計算節點si的移動距離和方向

19)

移動并更新節點si的位置

20)

End for

21)

End for

22)

End while

2.3 收斂性分析

節點在初始分布時，受到較大的斥力(密集初始條件)或引力(稀疏初始條件)，對應的每次移動的距離也較大。之后所受合力可能逐漸減小，當趨于穩定時，節點所受的合力趨于零，移動的距離也趨于零。對于這種情況，由于節點單次移動的距離是反正切函數，故當合力趨于零時，節點的移動距離也隨之趨于零，則必然?δ0>l，此時可認為算法收斂。對于另外一種情況，若節點所受合力不趨于零，而是出現振蕩(這主要是由于節點所受斥力較大，計算得到的移動距離較大，但移動后又脫離了斥力的范圍而受到引力吸引，從而使得節點在最佳距離附近振蕩)，則由步進值b可以控制減小其移動距離，當節點與其所接近的目標距離小于一定的值時，利用步進值b減小其移動的距離，可以使節點穩定于最佳位置附近。綜上兩種情況，算法最終可以收斂，使得節點部署趨于穩定。

3 仿真實驗

首先對本文仿真實驗所設置的參數進行說明，需要注意的是，本文所研究的應用背景具有較強的特異性，不同的環境應用時差異較大，將會導致參數設置上的差別，實際中應根據當時的應用環境相應地調試有關參數，以達到理想的效果。此外，文中各量均作無量綱處理，重點關注它們之間的比例關系和便于理解。

引力和斥力系數的設定與區域大小和節點覆蓋半徑有關，本文參考文獻[13]將引力系數設置為與區域邊長同量級，斥力系數為引力系數10倍。力的系數太小或太大均會影響部署效果和收斂時間。

對于最大迭代次數nmax，本文設置了一個較大的值500來限制程序運行可能出現的假死或無限循環的異常情況，通常程序運行達不到這一上限即可收斂。

對于移動停止門限δ，是用來判斷算法是否收斂的條件，本文算法中，節點所受合力應逐漸減小至0，但是實際中合力可能無法完美達到零，或是會經過極多甚至無窮次迭代，所以引入節點移動停止門限是十分必要的。通常節點的移動距離維持在一個較小的值時可以認為其已經在最佳位置附近小幅振蕩，設置一個停止門限可以避免節點無止境的振蕩。考慮到節點感知半徑為500，停止門限應遠小于這一值，例如相差一個量級以上，故本文結合仿真實驗經驗將其設置為20。

3.1 單目標覆蓋

圖4中叉號代表目標位置，圓圈表示節點的覆蓋范圍，節點位置位于圓心(坐標軸刻度為對平面區域如第1節所述建立坐標系時的位置刻度，圖4中坐標軸X、Y方向無量綱，單位為1，下同)。由圖可見節點圍繞目標部署，且目標周圍的節點之間實現無縫覆蓋。

圖4 單中心覆蓋結果示意圖

將本文算法應用于單目標時的性能與文獻[13]中的SMCA(Simple Movement Control Algorithm)進行比較，主要考察了算法的收斂時間和節點移動的公平性。其中：收斂時間指從初始位置開始到完成部署所用的時間；節點移動公平性采用了Jain氏公平性指數：

(12)

在本文中，n即節點數，xi即節點i移動的總距離，計算結果f(x)即為公平性指數。該數值無量綱且處在0～1，越接近1說明越公平，反之說明公平性差。為便于閱讀，本文將該數值表示為百分數形式。

圖5可見本文算法的收斂時間較SMCA方法稍短，尤其在節點數相對多時，且考慮到實際應用中算法分別由各節點分布式計算，執行效率應更高。

圖5 兩種算法收斂時間比較

圖6顯示了本文算法的節點移動公平性明顯好于SMCA算法，且本文的該項指標較穩定，基本不隨節點數而變化。

圖6 兩種算法節點移動公平性比較

3.2 兩目標動態按需覆蓋

此處在不引入引力線的情況下演示兩個目標的動態按需覆蓋過程，其中當迭代次數達到100后將調整目標的引力系數以模擬覆蓋需求變化的情況。

由圖7可見(圖中坐標軸X、Y方向無量綱，單位為1，叉號代表目標位置，圓圈表示節點的覆蓋范圍，節點位置位于圓心)，在迭代100次之前節點按照左側目標覆蓋需求小而右側大的設定進行部署，當迭代100次后目標需求發生了變化，原來需求小的左側目標需求變大，節點也根據新的需求調整部署，一部分節點從右側移動到了左側，說明本文算法可以適應目標需求的變化。

圖7 兩目標動態按需覆蓋過程

3.3 多目標連通按需覆蓋

圖8、9中叉號處為各目標位置，圓點為節點位置，圓點之間的連線表示節點之間處于可以通信的范圍(圖中坐標軸X、Y方向無量綱，單位為1)。顯然，圖中各目標周圍根據不同的需求情況覆蓋了一定的節點，同時各目標之間還有若干節點將節點集群連接起來，保證了所有節點間的通信連接，達到了本算法的設計目的。

圖8 三目標連通按需覆蓋部署示意

圖9 四目標連通按需覆蓋部署示意

在性能分析中考察了在目標數為2個，節點數分別為20、30、40、50、60時的收斂時間和節點移動公平性；以及在節點數為50個，目標數分別為2、3、4時的相應性能。考慮到實際應用中通常采用GPS進行定位，其精度直接影響了結果，故同時考察了GPS誤差[17]對性能的影響。GPS誤差的引入方法為：在計算出節點下一次將要移動的位置后，在該坐標的基礎上加上一個隨機方向的GPS定位誤差值，以模擬定位與實際位置產生一定偏差時的情況。

圖10對目標數分別為2、3、4，節點數為50時的收斂時間進行了考察。當目標數增加時收斂時間相應增加，符合實際情況。在引入GPS誤差后，收斂時間相應增加，這是因為此時節點移動的位置并不是預期的精確計算結果，那么經過多次迭代積累下來可能導致較大偏差使得收斂時間大幅增加。但本文算法中收斂時間增加并不明顯，大約在1%左右，最大也不超過5%，在通常的工程應用中處在可以接受的范圍，說明本文算法對GPS誤差容忍性較好，也就是說即使存在GPS誤差，本算法也可以實現預期的部署效果。

圖11對節點數為50，目標數分別為2、3、4時的節點移動公平性進行了分析。該指標都在99%左右，已達到很高水平，但在引入GPS誤差前后不同目標的該項指標無明顯規律，這主要是由于該項指標與目標數目和它們之間的相對位置有較大關系，由具體環境決定。部分節點在沒有誤差時可能率先到達停止條件，而引入GPS誤差后這些節點相比沒有誤差時增加了移動量，與其他節點的移動總量差縮小，從而整體節點移動公平性更優。但是GPS誤差的影響已經小于0.3%，可以忽略，認為沒有影響。

圖10 不同目標數收斂時間及GPS誤差分析(50節點)

圖11 不同目標數節點移動公平性及GPS誤差分析(50節點)

圖12是在2目標情況下分析不同節點數的收斂時間，當節點增加時，收斂時間增加，符合一般常識。GPS誤差對此影響較小，這是因為每個節點都存在隨機GPS誤差，從整個系統來看，各節點之間的誤差影響相互抵消了相當一部分，這也可以理解為整個系統分布式并行計算結構的魯棒性。從量級上看，GPS誤差引入前后收斂時間的變化不大于5%，在實際應用中可以接受。

圖12 不同節點數收斂時間及GPS誤差分析(2目標)

圖13反映了2目標不同節點數的節點移動公平性，可見本文算法節點移動公平性十分接近1，效果好。引入GPS誤差后性能相近或略好主要是因為潛在提高了節點間的交互性，和對圖11分析相同，增加了移動量較少節點的總移動量，減小了各節點移動量分布的方差。實際上由于GPS誤差對該指標影響小于1%，故可認為在一般系統誤差范圍內無影響。

圖13 不同節點數節點移動公平性及GPS誤差分析(2目標)

4 結語

本文提出了一種基于虛擬力的移動傳感器網絡節點連通按需覆蓋的部署方法。該方法針對傳感器監測區域中存在覆蓋需求不同的目標的情況，通過設置目標產生引力吸引節點向目標區域移動，節點之間產生斥力使之避免重疊，引入引力線使得各目標之間節點相互連通，通過節點分布式逐輪計算后移動，從而實現了對監測區域中需求高的目標部署較多節點，對需求低的區域部署較少節點，各目標之間節點保持通信連接，目標周圍節點之間實現無縫覆蓋的按需覆蓋。該算法部署效果佳，收斂時間短，節點移動公平性高，GPS誤差并未明顯降低本算法性能，實際應用的價值高。后續的工作可以考慮優化節點的移動效率，以及改進算法用于更廣泛的異構網絡中。

References)

[1] LEE H J, KIM Y H, HAN Y H, et al. Centroid-based movement assisted sensor deployment schemes in wireless sensor networks [C]// Proceedings of the 2009 IEEE 70th Vehicular Technology Conference Fall. Piscataway, NJ: IEEE, 2009: 1-5.

[2] CORTéS J, BULLO F. Coordination and geometric optimization via distributed dynamical systems [J]. SIAM Journal on Control and Optimization, 2005, 44(5): 1543-1574.

[3] BARTOLINI N, BONGIOVANNI G, PORTA T L, et al. Voronoi-based deployment of mobile sensors in the face of adversaries [C]// Proceedings of the 2014 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2014: 532-537.

[4] MAHBOUBI H, AGHDAM A G. Distributed deployment strategies to increase coverage in a network of wireless mobile sensors [C]// Proceedings of the 2013 American Control Conference. Piscataway, NJ: IEEE, 2013: 5887-5892.

[5] 黃帥,程良倫.一種基于虛擬力的有向傳感器網絡低冗余覆蓋增強算法[J].傳感技術學報,2011,24(3):418-422.(HUANG S, CHENG L L. A low redundancy coverage-enhancing algorithm for directional sensor network based on fictitious force[J]. Chinese Journal of Sensors and Actuators, 2011, 24(3): 418-422.)

[6] 秦寧寧,余穎華,吳德恩.移動混合傳感網中節點自主部署算法[J].電子與信息學報,2016,38(7):1838-1842.(QIN N N, YU Y H, WU D E. Autonomous deployment algorithm in mobile heterogeneous networks [J]. Journal of Electronics and Information Technology, 2016, 38(7): 1838-1842.)

[7] IMAI H, IRI M, MUROTA K. Voronoi diagram in the Laguerre geometry and its applications [J]. SIAM Journal on Computing, 1985, 14(1): 93-105.

[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]// Proceedings of International Symposium on Distributed Autonomous Robotic Systems 5. Berlin: Springer, 2002: 299-308.

[9] 田一鳴,陸陽,魏臻,等.無線傳感器網絡虛擬力覆蓋控制及節能優化研究[J].電子測量與儀器學報,2009,23(11):65-71.(TIAN Y M, LU Y, WEI Z, et al. Research on energy-efficient optimization for coverage control in wireless sensor networks [J]. Journal of Electronic Measurement and Instrument, 2009, 23(11): 65-71.)

[10] 陶丹,馬華東,劉亮.基于虛擬勢場的有向傳感器網絡覆蓋增強算法[J].軟件學報,2007,18(5):1152-1163.(TAO D, MA H D, LIU L. A virtual potential field based coverage-enhancing algorithm for directional sensor networks [J]. Journal of Software, 2007, 18(5): 1152-1163.)

[11] ZOU Y. Coverage-driven sensor deployment and energy-efficient information processing in wireless sensor networks [D]. Durham, North Carolina: Duke University, 2004.

[12] GAGE D W. Command control for many—robot systems [EB/OL]. [2016- 12- 12]. https://www.researchgate.net/publication/243636092_Command_control_for_many-robot_systems.

[13] LIU H, CHU X, LEUNG Y W, et al. Simple movement control algorithm for bi-connectivity in robotic sensor networks [J]. IEEE Journal on Selected Areas in Communications, 2010, 28(7): 994-1005.

[14] SEMNANI S H, BASIR O A. Semi-flocking algorithm for motion control of mobile sensors in large-scale surveillance systems [J]. IEEE Transactions on Cybernetics, 2015, 45(1): 129-137.

[15] LI S, XU C, PAN W, et al. Sensor deployment optimization for detecting maneuvering targets [C]// Proceedings of the 2005 8th International Conference on Information Fusion. Piscataway, NJ: IEEE, 2005,2: 1629-1635.

[16] 周浦城,崔遜學,王書敏,等.基于虛擬力的無線傳感器網絡覆蓋增強算法[J].系統仿真學報,2009,21(5):1416-1419.(ZHOU P C, CUI X X, WANG S M, et al. Virtual force-based wireless sensor network coverage-enhancing algorithm [J]. Journal of System Simulation, 2009, 21(5): 1416-1419.)

[17] National Coordination Office for Space-based Positioning, Navigation, and Timing. GPS accuracy [EB/OL]. [2017- 03- 20]. http://www.gps.gov/systems/gps/performance/accuracy/.

Distributeddeploymentalgorithmforconnectedon-demandcoverageinmobilesensornetwork

MAO Lingchu*, ZHAO Haitao

(CollegeofElectronicScienceandEngineering,NationalUniversityofDefenseTechnology,ChangshaHunan410073,China)

Aiming at the problem that the number of sensors needed in the monitoring area of the mobile sensor network is different and no path is formed between the targets, a method of on-demand coverage for different targets was proposed by virtual force method. The attractive force between targets and sensor nodes based on the gravitational attraction, the repulsive force based on the Coulomb force between nodes and the gravitational lines between targets were set according to the coverage requirements of different targets. The nodes covered the targets or formed the paths under the guidance of its resultant force. The simulation results show that the proposed method has a shorter convergence time compared with the existing representative algorithm, and the moving fairness index is as high as 99%, and the influence of GPS error can be controlled below 1%, which can be distributed under sparse or dense initial conditions.

mobile sensor network; on-demand coverage; virtual force; gravitational line

2017- 03- 27;

2017- 05- 05。

國家自然科學基金資助項目(61471376)。

毛凌楚(1993—)，男，湖南長沙人，碩士研究生，主要研究方向：無線傳感器網絡、多智能體網絡； 趙海濤(1981—)，男，山東昌樂人，副教授，博士，主要研究方向：認知無線網絡、智能組網、交叉層協議設計與優化。

1001- 9081(2017)09- 2463- 07

10.11772/j.issn.1001- 9081.2017.09.2463

TP393.02

A

This work is partially supported by the National Natural Science Foundation of China (61471376).

MAOLingchu, born in 1993, M. S. candidate. His research interests include wireless sensor network and multi-agent network.

ZHAOHaitao, born in 1981, Ph. D., associate professor. His research interests include wireless cognitive network, intelligent networking, network protocol design and optimization.