孫愛晶， 王 磊， 朱鑫鑫

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)是一種具有自組織性、可靠性、可移動性、節(jié)點(diǎn)間可以通信的無線覆蓋網(wǎng)絡(luò)[1,2]。隨著對WSNs在不同應(yīng)用場景的研究，如安防部署問題、森林火災(zāi)檢測、水下動態(tài)檢測等三維的環(huán)境下，需對二維模型進(jìn)行擴(kuò)展從而構(gòu)建合適的三維模型。文獻(xiàn)[3]針對節(jié)點(diǎn)冗余、覆蓋率等問題，利用改進(jìn)的人工魚群算法(artificial fish-swarm algorithm,AFSA)減少尋優(yōu)時間獲得最優(yōu)部署方案。文獻(xiàn)[4]基于虛擬力算法(virtual force algorithm,VFA)考慮多方面受力完善合力解決三維覆蓋重部署問題。文獻(xiàn)[5]利用傳感器節(jié)點(diǎn)半徑可調(diào)性結(jié)合VFA有效地實(shí)現(xiàn)三維覆蓋。文獻(xiàn)[6]針對覆蓋空洞，基于AFSA提出采用自適應(yīng)的視野和步長完成空洞修補(bǔ)。文獻(xiàn)[7]基于VFA提出一種可變步長的策略優(yōu)化WSNs節(jié)點(diǎn)部署問題。上述研究均有效解決了覆蓋問題，但仍在能耗時間、覆蓋復(fù)雜度等方面存在不足。

本文針對三維WSNs節(jié)點(diǎn)部署問題，建立三維覆蓋模型，提出一種基于VFA與AFSA的融合算法獲得最優(yōu)部署模型，并有效提升網(wǎng)絡(luò)覆蓋率。通過VFA獲得步長因子，再將步長因子添加至AFSA中各行為策略中，起到約束與規(guī)范作用，最終實(shí)現(xiàn)最優(yōu)部署模型。

1 三維網(wǎng)絡(luò)模型與問題模型

1.1 三維網(wǎng)絡(luò)模型

本文采用二元感知模型[8]，在某個三維傳感器場中，將位于(x,y,z)的S點(diǎn)和位于(i,j,k)的P點(diǎn)之間的歐氏距離dij(x,y,z)與傳感器監(jiān)測半徑R進(jìn)行比較。若dij(x,y,z)>R，則格點(diǎn)未被覆蓋，表示為0；否則被覆蓋，表示為1。

根據(jù)覆蓋問題，在檢測范圍中的目標(biāo)點(diǎn)可被采集信息，而超出覆蓋范圍將丟失目標(biāo)點(diǎn)的信息。因此，本文將基于區(qū)域覆蓋實(shí)際問題的統(tǒng)計(jì)模型進(jìn)一步研究AFSA和VFA覆蓋算法，提高網(wǎng)絡(luò)覆蓋率。針對三維覆蓋問題，將采用以節(jié)點(diǎn)位置為圓心、監(jiān)測半徑R的球域覆蓋目標(biāo)區(qū)域，并計(jì)算出當(dāng)前的網(wǎng)絡(luò)覆蓋率。

1.2 三維空間覆蓋問題描述

在實(shí)際應(yīng)用環(huán)境中，對目標(biāo)區(qū)域有效覆蓋是實(shí)現(xiàn)網(wǎng)絡(luò)各種功能的前提。針對三維目標(biāo)區(qū)域覆蓋問題，由于傳感器節(jié)點(diǎn)初始部署時會造成節(jié)點(diǎn)分布不均，引起覆蓋空洞導(dǎo)致通信受阻，難以達(dá)到預(yù)期的覆蓋率。為了達(dá)到覆蓋要求，需要對傳感器網(wǎng)絡(luò)中存在的覆蓋空洞進(jìn)行修復(fù)，即是利用算法進(jìn)行一次重覆蓋的過程，提高網(wǎng)絡(luò)覆蓋率，實(shí)現(xiàn)對三維目標(biāo)區(qū)域的有效監(jiān)測。受到二維平面覆蓋網(wǎng)格劃分啟發(fā)，本文將對三維空間監(jiān)測區(qū)域進(jìn)行離散化處理，使監(jiān)測區(qū)域由若干網(wǎng)格組成，將目標(biāo)點(diǎn)抽象為網(wǎng)格點(diǎn)，由此將區(qū)域覆蓋巧妙地轉(zhuǎn)化為網(wǎng)格點(diǎn)覆蓋，可視為點(diǎn)覆蓋問題來處理，方便了進(jìn)一步研究。

定義網(wǎng)絡(luò)覆蓋率：在三維目標(biāo)監(jiān)測區(qū)域中，所有被工作節(jié)點(diǎn)覆蓋格點(diǎn)數(shù)占整個監(jiān)測區(qū)域總格點(diǎn)數(shù)的比例視為網(wǎng)絡(luò)的覆蓋率，用Q來表示。

設(shè)定一個100 m×100 m×100 m的三維目標(biāo)區(qū)域M，對其進(jìn)行立方體網(wǎng)格劃分，如圖1所示。

圖1 立方體網(wǎng)格化

1.3 基于三維覆蓋模型的假設(shè)

給出本文研究三維空間覆蓋問題的相關(guān)條件設(shè)定，具體如下：

1)所有傳感器節(jié)點(diǎn)為采用二元感知模型的同構(gòu)節(jié)點(diǎn)，均保證相同的感知半徑和通信半徑，且節(jié)點(diǎn)的通信半徑為感知半徑的2倍。

2)每個傳感器節(jié)點(diǎn)均可獲得自身坐標(biāo)信息，可實(shí)現(xiàn)空間全方位探測，其探測范圍是一個以R為半徑的球體，且移動節(jié)點(diǎn)能量足夠支持移動。

3)這里只研究傳感器網(wǎng)絡(luò)應(yīng)用層的問題，涉及底層的如數(shù)據(jù)融合、路由通信等均不討論。

2 基于VFA與AFSA的融合算法描述

2.1 基于三維空間的VFA

VFA是將監(jiān)測區(qū)域中的節(jié)點(diǎn)通過引力、斥力作用進(jìn)行重部署，使得二次部署的節(jié)點(diǎn)均勻排布[9]。若兩節(jié)點(diǎn)之間距離大于某一閾值，通過虛擬引力使兩節(jié)點(diǎn)靠近；反之，便會產(chǎn)生虛擬斥力使兩節(jié)點(diǎn)遠(yuǎn)離，有效提高網(wǎng)絡(luò)覆蓋率[10]。

一般地，VFA多用于二維空間中節(jié)點(diǎn)部署，但在實(shí)際三維應(yīng)用場景均勻部署更加迫切，3D-VFA的提出可以有效根據(jù)目標(biāo)區(qū)域的不同形態(tài)重新部署從而提高區(qū)域覆蓋率。設(shè)用FpA代表優(yōu)先覆蓋區(qū)域?qū)σ粋€傳感器節(jié)點(diǎn)產(chǎn)生的總吸力，用FpR代表障礙物對一個傳感器節(jié)點(diǎn)產(chǎn)生的總斥力，用Fpq代表傳感器節(jié)點(diǎn)之間總引力或總斥力，則一個傳感節(jié)點(diǎn)受到的總合力可以表示為

2.2 基于三維空間的AFSA

每條人工魚都攜帶自身數(shù)據(jù)和擁有執(zhí)行系列行為的能力，且對外界的感知是依靠視覺來實(shí)現(xiàn)的。根據(jù)實(shí)際環(huán)境做出相應(yīng)決策，如覓食、聚群、追尾等行為，獲得最優(yōu)解[11]。當(dāng)前人工魚在下一時刻的行為取決于自身狀態(tài)和環(huán)境狀態(tài)，并且還通過自身活動來影響環(huán)境，進(jìn)而影響其他人工魚活動。一般地，以當(dāng)前網(wǎng)絡(luò)覆蓋率Q的大小作為評價(jià)函數(shù)對行為評價(jià)。1)覓食行為：是魚尋找食物并移動至目標(biāo)位置的一種活動，行動的方向通過視覺或味覺來感知水中的食物量或食物濃度來選擇行動的方向[12]。2)聚群行為：主要模擬應(yīng)自然環(huán)境生存法則，魚自然地聚集成群的一種反應(yīng)行為。在聚群時需遵守一定規(guī)則，即向中心位置靠近、避免擁擠、方向一致[12]。3)追尾行為：是指向視野中最佳位置，在尋優(yōu)算法中可以理解為是向附近的最優(yōu)伙伴前進(jìn)的過程，其中，最優(yōu)是指該人工魚自身解空間是當(dāng)前最優(yōu)部署方案[12]。4)隨機(jī)行為：是指自由移動擴(kuò)大范圍地尋找食物或其他人工魚。

在三維空間網(wǎng)絡(luò)應(yīng)用中，自身數(shù)據(jù)即是一組解空間，通過算法的實(shí)現(xiàn)尋取最優(yōu)魚，即尋求最優(yōu)覆蓋方案。3D-AFSA的實(shí)現(xiàn)是通過循環(huán)執(zhí)行這四種行為，并對行為進(jìn)行評價(jià)，最終尋得最優(yōu)解，即最優(yōu)部署方案。

2.3 基于三維空間的融合算法

根據(jù)2.1節(jié)與2.2節(jié)對兩個算法進(jìn)行描述，本文將利用兩算法各自特點(diǎn)進(jìn)行融合，解決三維空間覆蓋問題。3D-VFA局部優(yōu)化效果佳、收斂速度快和使節(jié)點(diǎn)均勻分布。3D-AFSA雖有著較強(qiáng)的全局優(yōu)化效果和魯棒性，但其搜索時間長、受步長影響較大和易出現(xiàn)不精確最優(yōu)情況位置的缺陷。因此，本文將結(jié)合兩種算法，形成優(yōu)勢互補(bǔ)，在3D-AFSA中引入步長因子、權(quán)重因子和全局最優(yōu)信息形成3D融合算法，以獲取最優(yōu)部署方案。

2.3.1 計(jì)算步長因子

由式(1)可知，三維目標(biāo)監(jiān)測區(qū)域中每個節(jié)點(diǎn)的受力情況。從X軸、Y軸、Z軸三個方向考慮均會受到這些力，接下來從三個方向?qū)αM(jìn)行分解：

設(shè)節(jié)點(diǎn)P的鄰居節(jié)點(diǎn)集合為Si，集合中的傳感器節(jié)點(diǎn)用si來表示；虛擬力作用下節(jié)點(diǎn)可移動最大步長為Maxstep；所受合力方向與X軸夾角為α，所受合力方向與Y軸夾角為β，所受合力方向與Z軸夾角為θ。則傳感器節(jié)點(diǎn)P所受的合力Fp表示如下

Fp=∑si∈SiFpi

(2)

則可計(jì)算節(jié)點(diǎn)沿X，Y，Z坐標(biāo)軸方向的分力大小，以X方向?yàn)槔?/p>

FpX=∑si∈Si(|Fpi|×cosα)

(3)

可計(jì)算出節(jié)點(diǎn)P在三個坐標(biāo)軸方向上的移動步長，以X方向?yàn)槔?/p>

通過虛擬力計(jì)算后，可獲得所有傳感器節(jié)點(diǎn)的移動步長向量集合，即是步長因子F，表達(dá)式如下

F={(π1X,π1Y,π1Z),(π2X,π2Y,π2Z),…,

(πnX,πnY,πnZ)}

(5)

2.3.2 融合步長因子

1)3D融合算法步長改進(jìn)

算法中步長參數(shù)設(shè)置影響仿真結(jié)果的精確度，對算法的收斂性造成影響。那么具體改進(jìn)如下

step=Minstep+(Maxstep-Minstep)/Maxstep

(6)

2)3D融合算法行為改進(jìn)

3D-AFSA應(yīng)用全局最優(yōu)解不佳，結(jié)合3D-VFA獲得步長因子添加至行為移動準(zhǔn)則中，并配上權(quán)重因子，其中w2為步長因子權(quán)重，具體改進(jìn)如下。

針對隨機(jī)行為移動準(zhǔn)則改進(jìn)有

針對聚群行為移動準(zhǔn)則改進(jìn)有

w2×F

(8)

針對追尾行為移動準(zhǔn)則改進(jìn)有

w2×F

(9)

2.3.3 3D融合算法流程描述

Step1 魚群初始化設(shè)置。設(shè)置人工魚數(shù)量K、傳感器節(jié)點(diǎn)數(shù)N和步長等參數(shù)。初始化每條魚，隨機(jī)產(chǎn)生人工魚自身的解空間。

Step2 公告牌設(shè)定。計(jì)算當(dāng)前每個個體的自適應(yīng)度，即網(wǎng)絡(luò)覆蓋率，并將最優(yōu)覆蓋率記錄在公告板上。

Step3 根據(jù)虛擬力算法計(jì)算虛擬力步長因子F，式(5)。

Step4 覓食行為。若目標(biāo)位置優(yōu)于當(dāng)前位置，直接向位置進(jìn)行移動，否則按式(7)隨機(jī)移動。

Step5 聚群行為。滿足該行為執(zhí)行需求，按式(8)執(zhí)行，那么向目標(biāo)中心位置靠攏；否則返回Step4。

Step6 追尾行為。滿足該行為執(zhí)行需求，按式(9)執(zhí)行，那么向目標(biāo)局部最優(yōu)位置方向移動；否則返回Step4。

Step7 分別計(jì)算覓食、聚群和追尾行為網(wǎng)絡(luò)覆蓋率函數(shù)值，使用評價(jià)函數(shù)評比，獲得當(dāng)前狀態(tài)下的最優(yōu)魚位置。

Step8 更新公告牌。本次迭代的網(wǎng)絡(luò)覆蓋率與公告牌的值進(jìn)行對比、更新。

Step9 終止條件判斷。若滿足則輸出全局最優(yōu)解，否則返回Step3。

Step10 算法終止，輸出最優(yōu)結(jié)果。

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 仿真環(huán)境設(shè)置

本文利用MATLAB仿真環(huán)境下，模擬三維傳感器網(wǎng)絡(luò)的部署優(yōu)化過程，驗(yàn)證本文所提出的融合算法的優(yōu)化性能。通過仿真實(shí)驗(yàn)若單純采用隨機(jī)拋灑方式，則約需要500個傳感器節(jié)點(diǎn)才能達(dá)到98 %的覆蓋率。假設(shè)在100×100×100的正方體的目標(biāo)監(jiān)測區(qū)域內(nèi)隨機(jī)拋灑60個可移動傳感器節(jié)點(diǎn)進(jìn)行部署優(yōu)化，其中傳感器節(jié)點(diǎn)半徑R為15 m，之間有效的通信距離為2R，分別使用三種算法進(jìn)行仿真實(shí)驗(yàn)。

具體仿真主要參數(shù)設(shè)置如表1。

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

3.2 仿真結(jié)果與分析

在固定的實(shí)驗(yàn)環(huán)境下，分別使用3D-VFA、3D-AFSA和3D融合算法對三維目標(biāo)監(jiān)測區(qū)域進(jìn)行仿真，其結(jié)果如圖2所示。由圖2和圖3仿真覆蓋結(jié)果圖來看，3D-VFA、3D-AFSA和融合算法仿真相比初始覆蓋率均有效的提升了網(wǎng)絡(luò)覆蓋率。而融合算法的使用，使得節(jié)點(diǎn)排布均勻，結(jié)合了虛擬力使節(jié)點(diǎn)快速均勻分布的優(yōu)勢和魚群算法全局優(yōu)化效果佳的優(yōu)點(diǎn)。從覆蓋率數(shù)值變化來看，融合算法使得網(wǎng)絡(luò)覆蓋率提高更加明顯。

圖2 仿真結(jié)果

圖3 不同算法評估對比

由圖3(b)所示，從移動總能量損耗方面對3D融合算法進(jìn)行評估，3D融合算法能耗相比于其他兩個算法位于中間位置，多次試驗(yàn)之后能耗基本在一定內(nèi)區(qū)間內(nèi)趨于穩(wěn)定，表明本文3D融合算法穩(wěn)定性和均衡較好，適用于三維空間覆蓋環(huán)境。

綜合以上多方面分析與對比，本文提出的3D融合算法可以有效提高網(wǎng)絡(luò)覆蓋率，適用于三維空間覆蓋優(yōu)化問題。

4 結(jié) 論

本文提出了一種3D融合算法，建立三維覆蓋模型，有效提升了三維空間的覆蓋率，并且使得最終的傳感器節(jié)點(diǎn)排布均勻，進(jìn)一步的提高了網(wǎng)絡(luò)服務(wù)。在今后的工作中，將從節(jié)點(diǎn)使用數(shù)量和混合網(wǎng)絡(luò)結(jié)構(gòu)方面考慮問題，把固定節(jié)點(diǎn)與可移動節(jié)點(diǎn)之間的比例作為一個重要的參考因素，繼

續(xù)對本文算法及應(yīng)用模型進(jìn)一步研究和優(yōu)化。