黨小超，邵晨光，郝占軍

(1.西北師范大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，蘭州 730070； 2.甘肅省物聯(lián)網(wǎng)研究中心，蘭州 730070)

0 引言

無線傳感器網(wǎng)絡(luò)是部署在特定監(jiān)測區(qū)域由大量的微型傳感器節(jié)點所組成的一個多跳的自組織網(wǎng)絡(luò)系統(tǒng)[1]。無線傳感器節(jié)點間相互通信，采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中所需要監(jiān)測對象的信息，并發(fā)送給監(jiān)測者。其中節(jié)點的覆蓋性能的優(yōu)劣反映無線傳感器網(wǎng)絡(luò)性能的一個基本問題[2]。無線傳感器網(wǎng)絡(luò)的覆蓋問題研究最開始主要集中在二維平面內(nèi)，由于現(xiàn)實環(huán)境的復(fù)雜性，三維環(huán)境的覆蓋研究很少。隨著對無線傳感器網(wǎng)絡(luò)技術(shù)的研究不斷成熟，以往傳統(tǒng)的二維平面模型和圓盤感知的節(jié)點覆蓋模型已不適用于現(xiàn)實的復(fù)雜環(huán)境[3-4]。

目前，針對三維覆蓋中如何保證網(wǎng)絡(luò)覆蓋效率最大化，在減少覆蓋盲區(qū)的同時增大節(jié)點的利用率和降低節(jié)點的能耗延長網(wǎng)絡(luò)壽命，是當(dāng)前覆蓋相關(guān)研究的熱點。早期，一些國外學(xué)者提出基于虛擬力的部署算法，但直接利用虛擬力下的作用移動傳感器節(jié)點實現(xiàn)最大化覆蓋并減少覆蓋冗余的方法較為單一，同時會有部分節(jié)點因為移動能耗過大而死亡。文獻(xiàn)[5]中提出三維復(fù)雜地形定向傳感器網(wǎng)絡(luò)的表面覆蓋算法，該算法基于節(jié)點的三維定向感知模型，采用網(wǎng)格劃分、模擬退火和局部最優(yōu)思想，通過優(yōu)化節(jié)點的位置坐標(biāo)和偏差角度來提高覆蓋率，但是針對定向傳感器部署優(yōu)化，研究對象仍為節(jié)點感知半徑相同的同構(gòu)節(jié)點，而感知半徑可調(diào)的異構(gòu)節(jié)點研究更符合實際應(yīng)用。文獻(xiàn)[6]中提出在三維水下環(huán)境中的傳感器節(jié)點確定性部署策略，利用布谷鳥搜索算法以找到節(jié)點的最佳位置，減少網(wǎng)絡(luò)能耗并與隨機(jī)算法進(jìn)行對比；雖然有效地提高了覆蓋率，但對網(wǎng)絡(luò)能耗卻沒有進(jìn)一步分析且算法不適用于異構(gòu)網(wǎng)絡(luò)。王昌征等[7]針對三維的有向異構(gòu)的傳感器網(wǎng)絡(luò)隨機(jī)部署中出現(xiàn)的覆蓋盲區(qū)等問題，提出了一種基于粒子群優(yōu)化算法并引入三維質(zhì)心進(jìn)行優(yōu)化，改變了節(jié)點的感知方向以提高覆蓋率，但該算法復(fù)雜度較高且覆蓋率提高得不明顯，最后網(wǎng)絡(luò)能耗較大。文獻(xiàn)[8]中提出基于虛擬力的三維移動無線傳感器網(wǎng)絡(luò)的重新部署，對感興趣的區(qū)域?qū)崿F(xiàn)網(wǎng)絡(luò)的全覆蓋以及保證網(wǎng)絡(luò)連通，但僅僅對虛擬力算法進(jìn)行改進(jìn)，并沒有理論分析其覆蓋率和網(wǎng)絡(luò)能耗。吳帥等[9]提出一種面向三維無線傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)的節(jié)能算法，該算法通過優(yōu)化節(jié)點位置信息使傳感器節(jié)點能相對均勻地分布在所感興趣的監(jiān)測區(qū)域中，并使用集合覆蓋模型算法計算出網(wǎng)絡(luò)中的冗余節(jié)點，最后使冗余節(jié)點移動到覆蓋空洞區(qū)域，提高了監(jiān)測區(qū)域的覆蓋程度。雖然移動冗余節(jié)點提高了覆蓋率，但未對冗余節(jié)點進(jìn)行剩余能量判斷以及如何降低移動不必要的節(jié)點能耗進(jìn)行分析，可能會導(dǎo)致整個傳感器絡(luò)的能耗過大。文獻(xiàn)[10]中研究了三維網(wǎng)絡(luò)的覆蓋和連通問題，為實現(xiàn)全覆蓋對冗余的傳感器節(jié)點的每個子集動態(tài)選擇保持活躍狀態(tài)，同時利用截頂八面體細(xì)分單元減少節(jié)點數(shù)量實現(xiàn)k-覆蓋，但此方法在三維部署中效率較低且節(jié)點的能耗大。杜曉玉等[11]針對異構(gòu)的傳感器網(wǎng)絡(luò)節(jié)點在初始部署時產(chǎn)生的覆蓋盲區(qū)問題，提出一種適用于感知半徑異構(gòu)的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法使得平面覆蓋得到優(yōu)化。秦寧寧等[12]針對節(jié)點感知半徑不相同的移動傳感器網(wǎng)絡(luò)節(jié)點的部署問題，提出一種基于VL(Voronoi Laguerre)圖分割的節(jié)點自主部署算法(Autonomous Deployment Algorithm, ADA)；該算法首先對目標(biāo)區(qū)域作VL圖劃分，將目標(biāo)區(qū)域的覆蓋任務(wù)分配給每個傳感器節(jié)點，再通過構(gòu)造VL受控多邊形來確定下一輪的候選目標(biāo)位置，傳感器節(jié)點通過逐輪更新自身位置信息，從而提高網(wǎng)絡(luò)覆蓋程度。以上兩種算法都是對基于二維平面進(jìn)行覆蓋優(yōu)化并都能提高網(wǎng)絡(luò)的覆蓋率，但不能直接用于三維現(xiàn)實環(huán)境的覆蓋且算法的復(fù)雜度較高。譚勵等[13]針對三維空間中無線傳感器網(wǎng)絡(luò)的節(jié)點部署中出現(xiàn)的覆蓋空洞，提出了基于虛擬力補(bǔ)償?shù)娜S空間自主部署的覆蓋算法，同時建立了節(jié)點模型和覆蓋目標(biāo)，將虛擬力算法由二維應(yīng)用到三維，使節(jié)點能夠根據(jù)被監(jiān)測目標(biāo)的信息實現(xiàn)均勻覆蓋。最后對算法在現(xiàn)實環(huán)境中進(jìn)行實驗，提高了算法的可靠性。作者主要對覆蓋空洞進(jìn)行了分析研究，較好地避免節(jié)點因高度問題而出現(xiàn)的覆蓋空洞，但未能分析算法實驗的能耗及覆蓋度來進(jìn)一步說明實驗的有效性。

本文主要研究基于半徑可調(diào)的無線傳感器網(wǎng)絡(luò)的覆蓋問題，其傳感器節(jié)點的感知半徑異構(gòu)并且每個節(jié)點的初始功率不同。在之前提出的三維環(huán)境覆蓋相關(guān)研究中，利用虛擬力算法VFA-3D(Virtual Force Algorithm in Three-Dimensional)[14]使得隨機(jī)部署在監(jiān)測環(huán)境中的節(jié)點借助虛擬場勢力進(jìn)行重新部署，但VFA-3D并不適用于覆蓋程度不同的環(huán)境和傳感器節(jié)點半徑異構(gòu)的無線傳感器網(wǎng)絡(luò)，因此出現(xiàn)節(jié)點的利用率不高和網(wǎng)絡(luò)能量消耗過快的問題。本文主要依據(jù)感知半徑可調(diào)的傳感器網(wǎng)絡(luò)異構(gòu)節(jié)點在感興趣的區(qū)域中對要檢測的目標(biāo)點覆蓋問題提出了一種半徑可調(diào)的無線傳感器網(wǎng)絡(luò)三維覆蓋算法(Three-Dimensional Coverage Algorithm based on Adjustable Radius in wireless sensor network, 3D-CAAR)。該算法借助虛擬力的作用使得傳感器節(jié)點初始均勻分布，同時結(jié)合節(jié)點半徑可調(diào)特性以及節(jié)點能耗判斷與目標(biāo)點的距離，提高節(jié)點的利用率和網(wǎng)絡(luò)生存時間。最后將本文算法與經(jīng)典的基于人工勢場的三維部署算法(Artificial Potential Field Algorithm in Three-Dimensional space, APFA3D)和基于與目標(biāo)精確覆蓋的三維覆蓋算法(Exact Covering Algorithm in Three-Dimensional space, ECA3D)進(jìn)行比較。這兩種對比算法雖然都能使節(jié)點在三維環(huán)境中較好地分布在目標(biāo)區(qū)域中同時覆蓋率較高，但存在沒有考慮不同程度覆蓋區(qū)域的覆蓋要求不一致的缺點。例如在實際監(jiān)測過程中對于目標(biāo)區(qū)域中所要檢測目標(biāo)事件密集的地方需進(jìn)行更多的覆蓋，而對目標(biāo)事件較少的區(qū)域則不必過多覆蓋。本文提出了3D-CAAR來彌補(bǔ)這兩種算法的缺陷。

1 三維感知模型與相關(guān)定義

1.1 感知半徑可調(diào)的節(jié)點感知模型

實際應(yīng)用中，每個無線傳感器節(jié)點自身的初始能量都存在差異，導(dǎo)致傳感器節(jié)點的感知半徑隨發(fā)射功率的不同而變化。本文研究的是基于半徑可調(diào)的無線傳感器網(wǎng)絡(luò)在三維環(huán)境中的目標(biāo)覆蓋算法，其半徑為傳感器節(jié)點的感知半徑且感知半徑可以改變，具體感知半徑調(diào)整的范圍步驟由第3章中的算法詳細(xì)給出。在此，先假設(shè)無線傳感器網(wǎng)絡(luò)節(jié)點感知半徑可調(diào)，其節(jié)點感知模型為節(jié)點為圓心、感知半徑可調(diào)的球形區(qū)域，如圖1所示。假設(shè)圖1的(a)中黑色的圓球為節(jié)點初始的感知范圍，灰色的大球為感知半徑增大后的感知范圍。圖1(b)為球感知模型的俯視圖，假設(shè)R1為傳感器節(jié)點的初始感知半徑，R2為節(jié)點感知半徑減小后的半徑。

傳感器節(jié)點初始時隨機(jī)撒布在目標(biāo)點區(qū)域，這樣可能導(dǎo)致傳感器節(jié)點分布不均勻、節(jié)點能量消耗過大以及部分目標(biāo)點重復(fù)覆蓋，降低了傳感器節(jié)點的利用率；同時，部分目標(biāo)點可能出現(xiàn)未被覆蓋，存在遺漏問題。其中，傳感器的節(jié)點的感知半徑可以利用算法調(diào)整，具體調(diào)整步驟由下文隨后給出。如圖2目標(biāo)點覆蓋模型所示，節(jié)點覆蓋出現(xiàn)了多余覆蓋，為了節(jié)省節(jié)點能耗，節(jié)點根據(jù)算法與被覆蓋目標(biāo)之間的距離調(diào)整感知半徑以降低傳感器網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生存時間。

圖1 球感知模型的正視圖和俯視圖

圖2 目標(biāo)點覆蓋模型

1.2 相關(guān)問題的分析和定義

傳統(tǒng)的節(jié)點覆蓋模型是以節(jié)點為圓心、感知距離為半徑的球形區(qū)域且每個節(jié)點的初始能量都相同；然而在實際應(yīng)用中，傳感器網(wǎng)絡(luò)中的各個傳感器節(jié)點由于生產(chǎn)工藝、自身能量的消耗不同等導(dǎo)致其初始能量Ei都不相同，從而其感知半徑隨著發(fā)射功率的大小而改變。本文中半徑可調(diào)的傳感器節(jié)點的感知區(qū)域是節(jié)點感知半徑可調(diào)的覆蓋模型。為了減少傳感器節(jié)點在覆蓋過程中多余的能耗，同時提高傳感器節(jié)點的利用率，使用較少的節(jié)點覆蓋較多被監(jiān)測的目標(biāo)點事件；如圖2所示中間的小球表示該節(jié)點通過算法判斷出與被覆蓋到的目標(biāo)點之間的最大距離Rmax小于自身的初始感知半徑rS，減小rS到合適的覆蓋距離。所以，本文主要研究如何在部分節(jié)點根據(jù)自身情況調(diào)整覆蓋半徑下，使該節(jié)點的能耗降低、生命周期增長，同時使得對所監(jiān)測目標(biāo)事件的網(wǎng)絡(luò)生存時間增加。

本文在基于半徑可調(diào)的無線傳感器網(wǎng)絡(luò)三維覆蓋算法研究之前，首先作出以下假設(shè)：

1)傳感器節(jié)點的半徑異構(gòu)，即節(jié)點的感知半徑可調(diào)，但半徑異構(gòu)的傳感器網(wǎng)絡(luò)節(jié)點的初始半徑相同。

2)半徑異構(gòu)的傳感器網(wǎng)絡(luò)節(jié)點初始時隨機(jī)部署節(jié)點，并且傳感器節(jié)點可以移動。

3)傳感器節(jié)點可以獲知各自的位置坐標(biāo)和目標(biāo)點之間的距離。

相關(guān)定義如下。

定義1 三維感知模型。假設(shè)傳感器節(jié)點si位于坐標(biāo)為(x,y,z)三維目標(biāo)區(qū)域R3中，并且其感知半徑為rS，那么si的感知區(qū)域是一個以rS為感知半徑，球心為(x,y,z)的圓球，則將其稱為si的感知圓球Sa(si)，該感知圓球滿足：Sa(si)={p|p∈R3,d(si,p)≤rS|}，其中p為空間中的點。

定義2 鄰居節(jié)點?？臻g中傳感器節(jié)點ni的通信范圍是以rC為通信半徑的感知圓球。規(guī)定，當(dāng)空間中兩個傳感器節(jié)點間的歐氏距離小于或等于節(jié)點自身的通信半徑rC時，則稱這兩個節(jié)點互為鄰居節(jié)點[15]。這兩個節(jié)點間感知范圍的球域會相切或者相交。

定義3 覆蓋率。傳感器節(jié)點在工作一段時間后，會出現(xiàn)能量消耗或者部分節(jié)點失效，使得空間中目標(biāo)點的覆蓋率下降。本文算法采用利用節(jié)點半徑可調(diào)的特點結(jié)合虛擬力算法優(yōu)化，使節(jié)點均勻分布提高整體覆蓋率。覆蓋率定義為：

(1)

其中：S(p)為傳感器網(wǎng)絡(luò)的整體覆蓋率；p為區(qū)域中的任意一個監(jiān)測點；n為待測點數(shù)。

(2)

其中：i為正常工作的節(jié)點個數(shù)，si(p)表示節(jié)點對待測點p的覆蓋率。

(3)

其中d(si,p)表示點p到節(jié)點si的距離。由式(4)可計算表示為：

(4)

2 虛擬力相關(guān)模型

為了進(jìn)一步直觀理解無線傳感器網(wǎng)絡(luò)中虛擬力的作用，設(shè)計出圖3所示的虛擬力下的節(jié)點覆蓋模型。圖3(a)表示傳感器節(jié)點初始狀態(tài)下隨機(jī)分布在監(jiān)測點的周圍，此時節(jié)點未能理想地覆蓋所需要監(jiān)測的目標(biāo)事件集[16]。圖3(b)中表示節(jié)點受到各事件之間的相互作用力開始移動。圖3(c)顯示傳感器節(jié)點在力的作用下移動到所要覆蓋的目標(biāo)事件中。

圖3 節(jié)點覆蓋模型

本文中改進(jìn)后的虛擬力算法假設(shè)三維區(qū)域中受到3個作用力。在無線傳感器網(wǎng)絡(luò)算法優(yōu)化的過程中，每個傳感器節(jié)點隨著其受到總的合力大小進(jìn)行移動，進(jìn)而達(dá)到節(jié)點受力平衡而對目標(biāo)區(qū)域均勻覆蓋。假設(shè)在監(jiān)測區(qū)域中傳感器節(jié)點受到的虛擬力合力為Fi；節(jié)點間的相互作用力為Fij；目標(biāo)區(qū)域?qū)鞲衅鞴?jié)點的吸引力為Fa以及障礙物與節(jié)點之間的作用力為Fr[17]，可得出：

(5)

節(jié)點之間的相互作用力Fij表示各個節(jié)點之間的相互引力以及相互斥力。為了進(jìn)一步約束傳統(tǒng)虛擬力下因為移動距離過大而導(dǎo)致節(jié)點死亡情況的出現(xiàn)，引入節(jié)點之間的距離閾值，并通過規(guī)定各個節(jié)點間的距離范圍去分別表示節(jié)點的受力情況以及在力的作用下的移動情況。Fij的計算公式為：

(6)

其中:k1、k2、a1、a2表示增益系數(shù)；mi、mj表示節(jié)點質(zhì)量因子(通常取單位1)；dij表示節(jié)點和節(jié)點之間的歐氏距離；rmin表示節(jié)點間的最小安全距離，rb表示傳感器節(jié)點之間的平衡距離即所受合力為零的位置。當(dāng)節(jié)點之間的距離在rmin和rb之間時，節(jié)點之間相互排斥；當(dāng)節(jié)點之間的距離等于平衡距離rb時，則節(jié)點不受到作用力；當(dāng)節(jié)點之間的距離在rb與rC之間時，節(jié)點相互吸引；當(dāng)節(jié)點之間的距離大于rC時，節(jié)點間的作用力將會消失。

3 3D-CAAR描述

在三維空間區(qū)域中部署傳感器節(jié)點，本文算法中節(jié)點首先判斷此時自身的位置信息和能量狀態(tài)，同時計算出與鄰居節(jié)點的位置關(guān)系，進(jìn)而判斷傳感器節(jié)點是否需要根據(jù)當(dāng)前的位置信息進(jìn)行調(diào)整。此時該節(jié)點在虛擬力合力的作用下，移動自身位置重新部署最后達(dá)到理想的覆蓋。通過上述的分析和說明，本文提出一種半徑可調(diào)的無線傳感器網(wǎng)絡(luò)算法(3D-CAAR)。首先進(jìn)行算法的假設(shè)：

1)傳感器節(jié)點的感知模型是其初始感知半徑rS都相同的球體；

2)n個傳感器節(jié)點具有感知、通信以及可移動能力；

3)為了保證節(jié)點間的相互連通性，其通信半徑為2倍的感知半徑且通信半徑隨感知半徑變換而變化，rC=2rS；

4)節(jié)點的最大感知半徑范圍為[Rmax,Rmin]；

5)節(jié)點的最大移動步長為dirmax；

6)每個節(jié)點初始能量Ei都不相同，其最大有效時間剩余能量為Ei,max。

本文創(chuàng)新性地將傳感器節(jié)點半徑可調(diào)的特性與改進(jìn)后的虛擬力算法結(jié)合起來。為了更加有效地提高算法的有效性，規(guī)定變化后的節(jié)點感知半徑的最大距離為Rmax，增大節(jié)點的初始感知半徑rS范圍為Rm,則Rm=rS+Rk, 其中Rk為實際增大距離，所以節(jié)點增大后的范圍rS

其次根據(jù)以上提出的虛擬力相關(guān)模型和理論分析以及上述算法的假設(shè)，主要實現(xiàn)傳感器節(jié)點在感知半徑可調(diào)的特性下提高節(jié)點的利用率和降低節(jié)點在覆蓋過程中節(jié)點的移動能耗。本文提出的3D-CAAR算法的設(shè)計流程和步驟如下：

步驟1 在需要監(jiān)測的區(qū)域D中隨機(jī)部署n個傳感器節(jié)點，每個節(jié)點判斷各自的位置和初始能量并在虛擬力合力的作用下移動。

步驟2 針對傳統(tǒng)VFA可能出現(xiàn)的覆蓋問題，將其分為兩種情況：第一種情況，覆蓋過程中存在目標(biāo)點遺漏以及目標(biāo)點位于節(jié)點的感知邊界;第二種情況，不存在目標(biāo)點位于邊界上且節(jié)點覆蓋到多個目標(biāo)點。

步驟3 傳感器節(jié)點根據(jù)被覆蓋的目標(biāo)點到節(jié)點中心的距離ri=rS判斷是否存在邊界目標(biāo)點：是，執(zhí)行步驟4；否則執(zhí)行步驟6。

步驟4 判斷此刻節(jié)點能量Ei是否小于Ei,max:如果否，不作變化;如果是，增大該節(jié)點i的初始感知半徑rS為Rmax。執(zhí)行步驟5。

步驟5 判斷是否覆蓋到漏洞節(jié)點：是，維持此刻狀態(tài)；否，減小Rmax至rS。

步驟6 計算傳感器節(jié)點Cijmax，將該節(jié)點半徑降低到Cijmax-k，其中k可調(diào)。

步驟7 如節(jié)點沒有覆蓋到任何目標(biāo)點，則關(guān)閉節(jié)點使其睡眠。

步驟8 根據(jù)合力重新部署節(jié)點。

4 算法分析

4.1 覆蓋度分析

目標(biāo)點集p被節(jié)點si所覆蓋的概率由下式求得：

(7)

其中：λ是節(jié)點的物理特性，表示時間的感知衰減因子；rS表示傳感器節(jié)點的初始感知半徑；Rmax為節(jié)點的最大確定的感知范圍。事件集P的覆蓋度由下式計算得到：

(8)

假設(shè)在三維無線傳感器網(wǎng)絡(luò)中事件si(Xi,Yi,Zi) 與被監(jiān)測區(qū)域中任意一個傳感器節(jié)點j(Xj,Yj,Zj) 的歐氏距離是不受虛擬力時的距離，其計算公式為：

(9)

但節(jié)點在虛擬力的作用下，節(jié)點受到合力的大小和方向開始移動，從而導(dǎo)致目標(biāo)事件與節(jié)點的歐氏距離和之前的距離存在一定差值，則改變后的距離可由下式計算：

d′(si,j)=d(si,j)+dirj

(10)

由式(10)減去式(9)得到：

(11)

4.2 能耗分析

本文中在虛擬力下的無線傳感器中的節(jié)點的能耗主要有三個方面：單個節(jié)點在任意方向移動單位距離的能耗eim，節(jié)點根據(jù)自身信息調(diào)整發(fā)射功率能耗er，單個節(jié)點的通信能耗eC；因此，整個網(wǎng)絡(luò)節(jié)點的移動能耗、節(jié)點調(diào)整感知半徑總能耗及節(jié)點間的總通信能耗分別為Eim、Er、EC，則本文算法中網(wǎng)絡(luò)的總能耗E為：

(12)

假設(shè)網(wǎng)絡(luò)中總的傳感器節(jié)點數(shù)P(A)不變，基于虛擬力的三維覆蓋算法不采用本文的節(jié)點調(diào)度算法，工作中的總節(jié)點數(shù)仍為N即節(jié)點對目標(biāo)點的覆蓋總數(shù)不變，傳感器節(jié)點的初始能量也相同，則其原有的總的能耗E′計算應(yīng)為：

(13)

將本文算法下傳感器網(wǎng)絡(luò)的總能耗E和原有直接在VFA-3D下的網(wǎng)絡(luò)節(jié)點能耗相比較，用式(12)減去式(13)可以得出：

(14)

5 仿真實驗與算法分析

5.1 仿真實驗

本文采用Matlab(2015b)環(huán)境進(jìn)行仿真實驗。為了驗證本文算法的實驗結(jié)果和性能，利用Matlab將本文算法與經(jīng)典的APFA3D[14]以及ECA3D[14]進(jìn)行仿真比較。假設(shè)無線傳感器網(wǎng)絡(luò)部署在100 m×100 m×100 m的立方體監(jiān)測空間中，在此區(qū)域中對隨機(jī)部署的目標(biāo)點進(jìn)行監(jiān)測實驗。仿真參數(shù)如表1所示。

表1 參數(shù)設(shè)置

在實驗中，選取23個所需要監(jiān)測目標(biāo)點呈線性部署在100 m3空間區(qū)域中，同時將7個傳感器節(jié)點隨機(jī)撒布在上述目標(biāo)區(qū)域中。為了驗證本文算法的準(zhǔn)確性和有效性同時較為明顯地分析對比，三種算法的仿真實驗結(jié)果如圖4所示。

在圖4(a)中可以看出：APFA3D在虛擬力的作用下，雖然對目標(biāo)點區(qū)域分布密集的地方進(jìn)行了覆蓋，但仍有部分區(qū)域中被監(jiān)測的目標(biāo)點沒有被覆蓋，存在部分覆蓋漏洞，導(dǎo)致出現(xiàn)了節(jié)點的浪費，網(wǎng)絡(luò)節(jié)點的整體利用率不高。圖4(b)中的ECA3D較APFA3D的覆蓋程度有所提高，傳感器節(jié)點覆蓋所要檢測的目標(biāo)點事件的分布得較為均勻，但是仍沒有對目標(biāo)點密集的地方進(jìn)行均勻覆蓋且節(jié)點的利用率不高，移動距離較大。本文3D-CAAR算法仿真實驗結(jié)果如圖4(c)(d)所示，由圖4(d)可以得出3D-CAAR算法下節(jié)點有更高的覆蓋率，圖中有兩個傳感器節(jié)點感知范圍大于其余的節(jié)點是因為，它們在3D-CAAR算法下依據(jù)自身的位置信息和對邊界節(jié)點的判斷機(jī)制，從而使得整個網(wǎng)絡(luò)的節(jié)點利用率較高，避免了節(jié)點的多余無效移動的能量消耗。如圖4(d)所示，對于多余的無效覆蓋的傳感器節(jié)點，在本文算法判斷后進(jìn)行關(guān)閉睡眠，降低節(jié)點的浪費。

由上述理論分析和仿真驗證可以得出，本文提出的半徑可調(diào)3D-CAAR算法在虛擬力的作用傳感器使得節(jié)點均勻分布，同時利用算法根據(jù)每個節(jié)點的當(dāng)前能量屬性計算出出節(jié)點和目標(biāo)點之間的位置關(guān)系調(diào)節(jié)節(jié)點半徑，減小了移動能耗，提高了節(jié)點利用率。因此本文算法有更高的覆蓋率，并能使傳感器節(jié)點和監(jiān)測點的分布密度相匹配。

圖4 不同算法仿真圖

5.2 算法分析

本文用參考文獻(xiàn)[16]中提出的事件覆蓋效能η(p)進(jìn)行3D-CAAR算法的性能評價，如圖5所示。在節(jié)點隨機(jī)分布在監(jiān)測區(qū)域部署實驗中對比三種算法實驗仿真的覆蓋效能，本文算法在迭代次數(shù)23代以前較ECA3D有較優(yōu)的覆蓋效能收斂速度有較為明顯的提高。在迭代23次以前，APFA3D比本文算法和ECA3D的收斂速度快，但從第24次迭代后3D-CAAR算法的覆蓋效能超過ECA3D和APFA3D，表現(xiàn)出較為明顯的優(yōu)勢。同時，在之前的覆蓋效能的理論分析中可知因為改變后的移動距離相比未移動之前的距離減少，說明在本文算法下的作用傳感器節(jié)點的覆蓋效能會降低，而在實驗圖中也可以得出3D-CAAR算法在24代后的優(yōu)勢更加明顯。因此，可以得出本文算法相比ECA3D和APFA3D有較快的收斂速度和較高的目標(biāo)事件集的η(P)。

如圖6所示，為了驗證網(wǎng)絡(luò)中傳感器節(jié)點總的剩余能量與運行時間的變化，將本文算法與APFA3D和ECA3D作對比。仿真實驗表明，在剛開始的16 s之前，三種算法的網(wǎng)絡(luò)能耗明顯下降，APFA3D下的傳感器節(jié)點移動距離較大，所以網(wǎng)絡(luò)需要更長的運行時間才能達(dá)到較為穩(wěn)定的狀態(tài)；因此，APFA3D相比ECA3D的移動能耗較大，網(wǎng)絡(luò)剩余能量較小。而本文3D-CAAR算法相比其他兩種算法節(jié)點的無效移動更小，網(wǎng)絡(luò)能耗降低，所以傳感器網(wǎng)絡(luò)的生存時間也明顯提高。

圖5 算法性能仿真對比

同時，為進(jìn)一步驗證網(wǎng)絡(luò)中被監(jiān)測的目標(biāo)點事件和節(jié)點能耗的關(guān)系，本文對3D-CAAR算法與APFA3D、ECA3D作出如圖7的實驗比對。由圖7可以直觀看出，三種算法下的監(jiān)測區(qū)域中的目標(biāo)點覆蓋率都隨著節(jié)點的能耗增加而增大，但本文3D-CAAR算法在覆蓋率相同的情況下節(jié)點消耗的能量更低且使用較少的能耗達(dá)到了較高的覆蓋率。因此，本文算法相比其他兩種算法有著能耗較低、覆蓋率較高的優(yōu)勢。

圖6 網(wǎng)絡(luò)剩余能量與運行時間關(guān)系

圖7 目標(biāo)事件覆蓋率與節(jié)點能耗的關(guān)系

深入分析可知，由于3D-CAAR算法根據(jù)傳感器半徑可調(diào)的覆蓋特性引入覆蓋范圍的判別機(jī)制同時算法根據(jù)網(wǎng)絡(luò)剩余能量對節(jié)點進(jìn)行分類，將剩余能量較少且未覆蓋到目標(biāo)事件的節(jié)點進(jìn)行關(guān)閉，理論上整個網(wǎng)絡(luò)的覆蓋率和網(wǎng)絡(luò)生存時間都會進(jìn)一步地提高和延長。因此，首先對算法進(jìn)行理論分析證明其有效性和優(yōu)劣性，得出3D-CAAR算法在覆蓋率和能耗上都優(yōu)于傳統(tǒng)的虛擬力的算法作用。最后，通過實驗仿真再次驗證了本文算法的可行性，進(jìn)一步說明實驗結(jié)果和理論的對比和相差之處。

為進(jìn)一步分析本文算法的時間開銷，如圖8所示。

圖8 算法運行時間比較

從圖中可以看出，本文提出的算法相比其他兩種算法，在達(dá)到相同覆蓋率的情況下算法所運行的時間明顯減少。如三種算法在圖中覆蓋率達(dá)到80%的同時，APFA3D和ECA3D的時間開銷都超過200 s。主要原因是本文算法在部署過程中有效地避免在虛擬力的作用下節(jié)點的無效和過大移動，使節(jié)點能快速達(dá)到穩(wěn)定狀態(tài)同時提高節(jié)點的覆蓋程度。

從上述實驗的算法分析和比較得出，本文3D-CAAR算法較APFA3D、ECA3D在后期相同迭代次數(shù)下的網(wǎng)絡(luò)覆蓋效能有較明顯的提高；在相同時間下的傳感器剩余能量以及同一能耗下目標(biāo)事件的覆蓋率有著較大的提升。因此，從理論和仿真實驗同時證明了本文3D-CAAR算法的準(zhǔn)確性和可靠性。

6 結(jié)語

本文研究了無線傳感器網(wǎng)絡(luò)中的目標(biāo)事件覆蓋問題，針對三維環(huán)境中節(jié)點的隨機(jī)覆蓋需求，提出3D-CAAR算法并應(yīng)用在半徑可調(diào)的無線傳感器網(wǎng)絡(luò)中實現(xiàn)三維覆蓋優(yōu)化。本文首先對無線傳感器網(wǎng)絡(luò)節(jié)點進(jìn)行受力分析，根據(jù)現(xiàn)實環(huán)境中節(jié)點的異構(gòu)特性，提出改進(jìn)后的虛擬力算法，提高了網(wǎng)絡(luò)的整體覆蓋率和傳感器節(jié)點的利用率；同時將本文算法和經(jīng)典的APFA3D和ECA3D進(jìn)行分析比較，驗證了本文算法的可行性和較高的覆蓋性能。作為下一步工作，將研究本文算法的復(fù)雜度和能量消耗問題并在實際環(huán)境中進(jìn)行相應(yīng)測試。

[9] 吳帥,孫力娟,肖甫,等.面向三維的無線傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J]. 計算機(jī)研究與發(fā)展,2011,48(Suppl):106-110.(WU S, SUN L J, XIAO F, et al. A coverage-enhancing algorithm for the three-dimensional wireless sensor networks [J]. Journal of Computer Research and Development, 2011, 48(Suppl): 106-110.)

[10] NAZRUL ALAM S M, HAAS Z J. Coverage and connectivity in three-dimensional networks with random node deployment [J]. Ad Hoc Networks, 2015, 34(C): 157-169.

[11] 杜曉玉,孫力娟,郭劍,等.異構(gòu)無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].電子與信息學(xué)報,2014,36(3):696-702.(DU X Y, SUN L J, GUO J, et al. Coverage optimization algorithm for heterogeneous WSNs [J]. Journal of Electronics and Information Technology, 2014, 36(3): 696-702.)

[12] 秦寧寧,余穎華,吳德恩.移動混合傳感網(wǎng)中的節(jié)點自主部署算法[J].電子與信息學(xué)報,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.)

[13] 譚勵,王云會,楊明華,等.一種基于虛擬力補(bǔ)償?shù)娜S空間自主部署算法[J].儀器儀表學(xué)報,2015,36(11):2570-2578.(TAN L, WANG Y H, YANG M H, et al. Three-dimensional space self-deployment algorithm based on virtual force compensation [J]. Chinese Journal of Scientific Instrument, 2015, 36(11): 2570-2578.)

[14] 李享.基于空中傳感網(wǎng)的三維部署研究[D]. 太原:中北大學(xué), 2013:5-54.(LI X. Three-dimensional disposition algorithm in aerial sensor network research [D]. Taiyuan: North University of China, 2013: 5-54.)

[15] 周浦城,崔遜學(xué),王書敏,等.基于虛擬力的無線傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].系統(tǒng)仿真學(xué)報, 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.)

[16] 夏娜,王長生,鄭榕,等.魚群啟發(fā)的水下傳感器節(jié)點布置[J].自動化學(xué)報,2012, 38(2) :295-302.(XIA N, WANG C S, ZHENG R, et al. Fish swarm inspired underwater senor deployment [J]. Acta Automatica Sinica, 2012, 38(2): 295-302.)

[17] 魏連鎖,蔡紹濱,潘實.基于加權(quán)虛擬力模型的錨節(jié)點移動策略的研究[J].通信學(xué)報,2017,38(6):97-107.(WEI L S, CAI S B, PAN S. Research on mobile strategy of anchor node based on weighted virtual force model [J]. Journal on Communications, 2017, 38(6) :97-107.)

[18] 劉慧,柴志杰,杜軍朝,等.基于組合虛擬力的傳感器網(wǎng)絡(luò)三維空間重部署算法研究[J].自動化學(xué)報，2011，37(6): 713-723.(LIU H, CHAI Z J, DU J Z, et al. Sensor redeployment algorithm based on combined virtual forces in three dimensional space [J]. Acta Automatica Sinica, 2011, 37(6): 713-723.