黨小超，邵晨光，郝占軍

(1.西北師范大學 計算機科學與工程學院，蘭州 730070； 2.甘肅省物聯網研究中心，蘭州 730070)

0 引言

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

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

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

1 三維感知模型與相關定義

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

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

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

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

圖2 目標點覆蓋模型

1.2 相關問題的分析和定義

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

本文在基于半徑可調的無線傳感器網絡三維覆蓋算法研究之前，首先作出以下假設：

1)傳感器節(jié)點的半徑異構，即節(jié)點的感知半徑可調，但半徑異構的傳感器網絡節(jié)點的初始半徑相同。

2)半徑異構的傳感器網絡節(jié)點初始時隨機部署節(jié)點，并且傳感器節(jié)點可以移動。

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

相關定義如下。

定義1 三維感知模型。假設傳感器節(jié)點si位于坐標為(x,y,z)三維目標區(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ī)定，當空間中兩個傳感器節(jié)點間的歐氏距離小于或等于節(jié)點自身的通信半徑rC時，則稱這兩個節(jié)點互為鄰居節(jié)點[15]。這兩個節(jié)點間感知范圍的球域會相切或者相交。

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

(1)

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

(2)

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

(3)

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

(4)

2 虛擬力相關模型

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

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

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

(5)

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

(6)

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

3 3D-CAAR描述

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

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é)點半徑可調的特性與改進后的虛擬力算法結合起來。為了更加有效地提高算法的有效性，規(guī)定變化后的節(jié)點感知半徑的最大距離為Rmax，增大節(jié)點的初始感知半徑rS范圍為Rm,則Rm=rS+Rk, 其中Rk為實際增大距離，所以節(jié)點增大后的范圍rS

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

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

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

步驟3 傳感器節(jié)點根據被覆蓋的目標點到節(jié)點中心的距離ri=rS判斷是否存在邊界目標點：是，執(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可調。

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

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

4 算法分析

4.1 覆蓋度分析

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

(7)

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

(8)

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

(9)

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

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

(10)

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

(11)

4.2 能耗分析

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

(12)

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

(13)

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

(14)

5 仿真實驗與算法分析

5.1 仿真實驗

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

表1 參數設置

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

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

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

圖4 不同算法仿真圖

5.2 算法分析

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

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

圖5 算法性能仿真對比

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

圖6 網絡剩余能量與運行時間關系

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

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

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

圖8 算法運行時間比較

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

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

6 結語

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

[9] 吳帥,孫力娟,肖甫,等.面向三維的無線傳感器網絡覆蓋增強算法[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] 杜曉玉,孫力娟,郭劍,等.異構無線傳感器網絡覆蓋優(yōu)化算法[J].電子與信息學報,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] 秦寧寧,余穎華,吳德恩.移動混合傳感網中的節(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.)

[13] 譚勵,王云會,楊明華,等.一種基于虛擬力補償的三維空間自主部署算法[J].儀器儀表學報,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] 李享.基于空中傳感網的三維部署研究[D]. 太原:中北大學, 2013:5-54.(LI X. Three-dimensional disposition algorithm in aerial sensor network research [D]. Taiyuan: North University of China, 2013: 5-54.)

[15] 周浦城,崔遜學,王書敏,等.基于虛擬力的無線傳感器網絡覆蓋增強算法[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.)

[16] 夏娜,王長生,鄭榕,等.魚群啟發(fā)的水下傳感器節(jié)點布置[J].自動化學報,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] 魏連鎖,蔡紹濱,潘實.基于加權虛擬力模型的錨節(jié)點移動策略的研究[J].通信學報,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] 劉慧,柴志杰,杜軍朝,等.基于組合虛擬力的傳感器網絡三維空間重部署算法研究[J].自動化學報，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.