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

毛凌楚，趙海濤

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

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

毛凌楚*，趙海濤

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

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

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

0 引言

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

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

1 問題描述

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

2 按需部署算法

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

2.1 虛擬力設置

對于處在虛擬力場中的節(jié)點而言，如果只受到單一的虛擬力是難以趨于穩(wěn)定的。所以在這個虛擬力場中，應該有多種虛擬力共同作用來使節(jié)點部署到預期的狀態(tài)。虛擬力通?？梢苑譃閮深悾阂统饬?。引力可以使節(jié)點聚集，將節(jié)點引向需要其部署的位置。節(jié)點間的斥力可以使得節(jié)點的分布分散開來，減少過多的重復覆蓋，提高覆蓋率。應該明確的是，虛擬力都是矢量，要考慮大小和方向。

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

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

圖1 一種虛擬力示例

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

2.1.1 目標引力

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

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

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

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

X方向：

Fax=Ka×(Δxa/d2)

(1)

Y方向：

Fay=Ka×(Δya/d2)

(2)

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

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

2.1.2 節(jié)點斥力

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

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

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

Fr=Kr/dij2

(3)

其中：Kr為斥力系數(shù)，dij為兩節(jié)點si和sj間的距離。

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

圖2 無縫覆蓋的三種方案

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

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

X方向：

Frx=Kr×Δxr/dij2

(4)

Y方向：

Fry=Kr×Δyr/dij2

(5)

其產生作用的距離為：

(6)

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

2.1.3 引力線

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

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

X方向：

Flx=Kl×Δxl/dl2

(7)

Y方向：

Fly=Kl×Δyl/dl2

(8)

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

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

圖3 引力線示意圖

2.2 算法步驟

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

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

X方向：

(9)

Y方向：

(10)

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

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

(11)

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

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

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

算法的步驟如下：

1)

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

2)

Whilen

3)

Forn

4)

Forsi∈S

5)

計算節(jié)點距離最近的引力線

6)

計算節(jié)點受到引力線的引力

7)

Forck∈C

8)

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

9)

End for

10)

Forsj∈S≠si

11)

12)

節(jié)點間斥力Fr=0

13)

Else

14)

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

15)

End if

16)

End for

17)

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

18)

計算節(jié)點si的移動距離和方向

19)

移動并更新節(jié)點si的位置

20)

End for

21)

End for

22)

End while

2.3 收斂性分析

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

3 仿真實驗

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

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

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

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

3.1 單目標覆蓋

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

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

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

(12)

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

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

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

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

圖6 兩種算法節(jié)點移動公平性比較

3.2 兩目標動態(tài)按需覆蓋

此處在不引入引力線的情況下演示兩個目標的動態(tài)按需覆蓋過程，其中當?shù)螖?shù)達到100后將調整目標的引力系數(shù)以模擬覆蓋需求變化的情況。

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

圖7 兩目標動態(tài)按需覆蓋過程

3.3 多目標連通按需覆蓋

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

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

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

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

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

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

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

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

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

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

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

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

4 結語

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

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] 秦寧寧,余穎華,吳德恩.移動混合傳感網中節(jié)點自主部署算法[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] 田一鳴,陸陽,魏臻,等.無線傳感器網絡虛擬力覆蓋控制及節(jié)能優(yōu)化研究[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].系統(tǒng)仿真學報,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—)，男，山東昌樂人，副教授，博士，主要研究方向：認知無線網絡、智能組網、交叉層協(xié)議設計與優(yōu)化。

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.