半徑可調(diào)的無線傳感器網(wǎng)絡(luò)三維覆蓋算法

黨小超，邵晨光，郝占軍

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

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

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

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

(5)

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

(6)

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

3 3D-CAAR描述

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

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

2)n個(gè)傳感器節(jié)點(diǎn)具有感知、通信以及可移動(dòng)能力；

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

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

5)節(jié)點(diǎn)的最大移動(dòng)步長(zhǎng)為dirmax；

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

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

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

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

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

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

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

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

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

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

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

4 算法分析

4.1 覆蓋度分析

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

(7)

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

(8)

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

(9)

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

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

(10)

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

(11)

4.2 能耗分析

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

(12)

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

(13)

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

(14)

5 仿真實(shí)驗(yàn)與算法分析

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

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

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

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

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

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

圖4 不同算法仿真圖

5.2 算法分析

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

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

圖5 算法性能仿真對(duì)比

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

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

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

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

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

圖8 算法運(yùn)行時(shí)間比較

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

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

6 結(jié)語

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

[9] 吳帥,孫力娟,肖甫,等.面向三維的無線傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J]. 計(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é)報(bào),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] 秦寧寧,余穎華,吳德恩.移動(dòng)混合傳感網(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.)

[13] 譚勵(lì),王云會(huì),楊明華,等.一種基于虛擬力補(bǔ)償?shù)娜S空間自主部署算法[J].儀器儀表學(xué)報(bào),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é)報(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.)

[16] 夏娜,王長(zhǎng)生,鄭榕,等.魚群?jiǎn)l(fā)的水下傳感器節(jié)點(diǎn)布置[J].自動(dòng)化學(xué)報(bào),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] 魏連鎖,蔡紹濱,潘實(shí).基于加權(quán)虛擬力模型的錨節(jié)點(diǎn)移動(dòng)策略的研究[J].通信學(xué)報(bào),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].自動(dòng)化學(xué)報(bào)，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.