毛凌楚，趙海濤

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

移動傳感網(wǎng)分布式連通按需覆蓋部署方法

毛凌楚*，趙海濤

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

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

移動傳感網(wǎng)；按需覆蓋；虛擬力；引力線

0 引言

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

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

1 問題描述

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

2 按需部署算法

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

2.1 虛擬力設(shè)置

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

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

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

圖1 一種虛擬力示例

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

2.1.1 目標(biāo)引力

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

1)對于引力的方向，顯然目標(biāo)產(chǎn)生的引力方向在監(jiān)測區(qū)域內(nèi)任何一點(diǎn)都應(yīng)該是指向目標(biāo)的。

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

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

X方向：

Fax=Ka×(Δxa/d2)

(1)

Y方向：

Fay=Ka×(Δya/d2)

(2)

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

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

2.1.2 節(jié)點(diǎn)斥力

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

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

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

Fr=Kr/dij2

(3)

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

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

圖2 無縫覆蓋的三種方案

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

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

X方向：

Frx=Kr×Δxr/dij2

(4)

Y方向：

Fry=Kr×Δyr/dij2

(5)

其產(chǎn)生作用的距離為：

(6)

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

2.1.3 引力線

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

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

X方向：

Flx=Kl×Δxl/dl2

(7)

Y方向：

Fly=Kl×Δyl/dl2

(8)

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

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

圖3 引力線示意圖

2.2 算法步驟

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

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

X方向：

(9)

Y方向：

(10)

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

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

(11)

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

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

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

算法的步驟如下：

1)

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

2)

Whilen

3)

Forn

4)

Forsi∈S

5)

計(jì)算節(jié)點(diǎn)距離最近的引力線

6)

計(jì)算節(jié)點(diǎn)受到引力線的引力

7)

Forck∈C

8)

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

9)

End for

10)

Forsj∈S≠si

11)

12)

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

13)

Else

14)

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

15)

End if

16)

End for

17)

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

18)

計(jì)算節(jié)點(diǎn)si的移動距離和方向

19)

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

20)

End for

21)

End for

22)

End while

2.3 收斂性分析

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

3 仿真實(shí)驗(yàn)

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

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

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

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

3.1 單目標(biāo)覆蓋

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

圖4 單中心覆蓋結(jié)果示意圖

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

(12)

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

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

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

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

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

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

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

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

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

3.3 多目標(biāo)連通按需覆蓋

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

圖8 三目標(biāo)連通按需覆蓋部署示意

圖9 四目標(biāo)連通按需覆蓋部署示意

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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] 黃帥,程良倫.一種基于虛擬力的有向傳感器網(wǎng)絡(luò)低冗余覆蓋增強(qiáng)算法[J].傳感技術(shù)學(xué)報(bào),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] 秦寧寧,余穎華,吳德恩.移動混合傳感網(wǎng)中節(jié)點(diǎn)自主部署算法[J].電子與信息學(xué)報(bào),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] 田一鳴,陸陽,魏臻,等.無線傳感器網(wǎng)絡(luò)虛擬力覆蓋控制及節(jié)能優(yōu)化研究[J].電子測量與儀器學(xué)報(bào),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] 陶丹,馬華東,劉亮.基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].軟件學(xué)報(bào),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] 周浦城,崔遜學(xué),王書敏,等.基于虛擬力的無線傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].系統(tǒng)仿真學(xué)報(bào),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。

國家自然科學(xué)基金資助項(xiàng)目(61471376)。

毛凌楚(1993—)，男，湖南長沙人，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)、多智能體網(wǎng)絡(luò)； 趙海濤(1981—)，男，山東昌樂人，副教授，博士，主要研究方向：認(rèn)知無線網(wǎng)絡(luò)、智能組網(wǎng)、交叉層協(xié)議設(shè)計(jì)與優(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.