基于能量優(yōu)化的三維無線傳感器網(wǎng)絡(luò)覆蓋算法*

孫愛晶，朱鑫鑫，王 磊

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

0 引 言

節(jié)點(diǎn)部署在無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)中是十分重要的一環(huán)，擁有不可替代的作用，而對于WSNs中的能量問題,路徑尋優(yōu)問題以及定位問題等均有重要的影響。如何能在保證網(wǎng)絡(luò)的覆蓋以及提高網(wǎng)絡(luò)的連通容錯(cuò)率的同時(shí)延長網(wǎng)絡(luò)的使用壽命在現(xiàn)階段受到了很多研究者的關(guān)注[1]。文獻(xiàn)[2]從WSNs算法的部署方式，監(jiān)測目標(biāo)以及節(jié)點(diǎn)是否移動(dòng)等方面進(jìn)行分析對比，并給出了WSNs算法的應(yīng)用關(guān)鍵點(diǎn)以及未來發(fā)展趨勢。文獻(xiàn)[3]通過對比適于空間鑲嵌的幾種凸多面體，得出截角八面體在一定條件下的覆蓋效果最優(yōu)。文獻(xiàn)[4]提出了一種基于空間鑲嵌的三維WSNs覆蓋機(jī)制，并在覆蓋的基礎(chǔ)上考慮了漏洞檢測與修復(fù)的問題。文獻(xiàn)[5]對三維曲面進(jìn)行網(wǎng)格劃分后在引入差分進(jìn)化算法來對傳感器節(jié)點(diǎn)的位置坐標(biāo)進(jìn)行優(yōu)化。文獻(xiàn)[6]提出了利用傳感器節(jié)點(diǎn)半徑可調(diào)的機(jī)制來完成三維空間的覆蓋。文獻(xiàn)[7]提出了基于方向梯度的三維表面覆蓋連通方法。由于前提環(huán)境的設(shè)置，只針對三維環(huán)境下的表面進(jìn)行了覆蓋。文獻(xiàn)[8]提出了基于網(wǎng)格的分布式能量有效k覆蓋多連通部署算法。該算法考慮了節(jié)點(diǎn)在分布式部署情況下的通信半徑問題，但并未應(yīng)用在三維場景下，在實(shí)際應(yīng)用中仍然存在一定的局限。

針對以上問題，本文提出了一種基于能量優(yōu)化的三維空間鑲嵌WSNs覆蓋算法。以截八面體為子單元填充三維空間，將傳感器節(jié)點(diǎn)部署在子單元的頂點(diǎn)上，并在節(jié)點(diǎn)部署時(shí)采用休眠與喚醒策略來減小節(jié)點(diǎn)的能量消耗，且在休眠與喚醒策略中加入了改進(jìn)后的人工蜂群算法以改善休眠與喚醒算法中節(jié)點(diǎn)的選取問題。

1 問題模型分析

本文以水下WSNs和地下WSNs為研究背景，假設(shè)網(wǎng)絡(luò)在部署時(shí)：所有傳感器節(jié)點(diǎn)在初始階段的參數(shù)一致，擁有相同的特性。目標(biāo)空間為水下立方體。

1.1 節(jié)點(diǎn)感知模型

在二維WSNs網(wǎng)絡(luò)的覆蓋模型中，節(jié)點(diǎn)感知模型常使用布爾感知模型。在三維WSNs中，理想狀態(tài)下希望節(jié)點(diǎn)的感知范圍可以呈現(xiàn)截角八面體的形狀，由于現(xiàn)實(shí)因素，在此假設(shè)傳感器節(jié)點(diǎn)的感知模型為球體模型[9]。

定義k覆蓋：在水下目標(biāo)區(qū)域中，假定任意某點(diǎn)同時(shí)被k個(gè)傳感器監(jiān)測到，則表示該區(qū)域中任意某點(diǎn)達(dá)到k覆蓋，可稱該區(qū)域被k覆蓋。

1.2 問題描述

在三維目標(biāo)空間中進(jìn)行截角八面體的空間鑲嵌，如何在保證目標(biāo)空間的k覆蓋，并在保證k覆蓋的條件下，如何對工作中的傳感器節(jié)點(diǎn)進(jìn)行協(xié)調(diào)以減少節(jié)點(diǎn)的能量消耗。

2 節(jié)點(diǎn)部署

2.1 填充子單元的選取

利用空間鑲嵌理論來完成三維WSNs的k覆蓋，首先要考慮的就是選取哪一種凸多面體作為填充子單元。在三維目標(biāo)空間的覆蓋中，空間鑲嵌方法中存在一種多面體的鑲嵌以及多種多面體的混合鑲嵌，而多種多面體的混合鑲嵌中，不僅多面體的范圍難以確定，并且混合多面體的組合十分復(fù)雜，會(huì)造成計(jì)算資源的浪費(fèi)。由此在本文中研究單一的多面體鑲嵌問題。

目前在使用空間鑲嵌方法進(jìn)行空間填充的方向上，當(dāng)傳感器節(jié)點(diǎn)部署在凸多面體的形心位置時(shí)，截角八面體能夠以最少的節(jié)點(diǎn)完成網(wǎng)絡(luò)的全覆蓋[10]。

2.2 節(jié)點(diǎn)的部署策略

本文中針對三維目標(biāo)空間采用分層分布式節(jié)點(diǎn)部署，如圖1。

圖1 分布式結(jié)構(gòu)

在目標(biāo)空間的鑲嵌中，采用截角八面體作為填充多面體，將節(jié)點(diǎn)部署在填充單元的各個(gè)頂點(diǎn)處，由此會(huì)產(chǎn)生共用節(jié)點(diǎn)。共用節(jié)點(diǎn)由外而內(nèi)按照目標(biāo)空間鑲嵌的維數(shù)進(jìn)行各不相同的標(biāo)記。內(nèi)層的節(jié)點(diǎn)因感知范圍而覆蓋到外層節(jié)點(diǎn)，所以，對節(jié)點(diǎn)進(jìn)行休眠與喚醒策略以減小能量的消耗。其中，第一層的共用系數(shù)標(biāo)記為1,2,3；第二層標(biāo)記為3，4；第三層以后標(biāo)記為4。

本文節(jié)點(diǎn)部署的基本思路是：首先根據(jù)目標(biāo)區(qū)域計(jì)算所需鑲嵌子單元個(gè)數(shù),如式(1)，將目標(biāo)空間劃分為k層，對每一層的節(jié)點(diǎn)進(jìn)行部署，遍歷每一層，直至完成部署

(1)

(2)

文獻(xiàn)[11]首先將目標(biāo)區(qū)域網(wǎng)格化，再部署傳感器，不僅可以估算覆蓋率還可以定位傳感器。本文在節(jié)點(diǎn)部署時(shí)，對此網(wǎng)格化思維進(jìn)行擴(kuò)展，將其用于三維空間中，對目標(biāo)空間進(jìn)行k覆蓋的檢測。將目標(biāo)空間網(wǎng)格化，以節(jié)點(diǎn)感知半徑為半徑進(jìn)行網(wǎng)格點(diǎn)k覆蓋的判斷，從而達(dá)到目標(biāo)空間的k覆蓋。如果依靠頂點(diǎn)上部署的節(jié)點(diǎn)未能達(dá)到k覆蓋，則在填充子單元內(nèi)部均勻部署L個(gè)節(jié)點(diǎn)，以滿足k覆蓋的要求。如果節(jié)點(diǎn)部署大于k值。則首先進(jìn)行休眠，其次在節(jié)點(diǎn)之后的工作中進(jìn)行有目標(biāo)的喚醒，以延長目標(biāo)網(wǎng)絡(luò)的工作時(shí)長。

2.3 節(jié)點(diǎn)部署位置

在實(shí)現(xiàn)網(wǎng)絡(luò)全覆蓋的情況下，以截八面體作為子單元進(jìn)行空間填充，并將節(jié)點(diǎn)部署在子單元形心位置時(shí)，節(jié)點(diǎn)能夠以最少的數(shù)目完成目標(biāo)空間的覆蓋。

當(dāng)要求網(wǎng)絡(luò)的覆蓋度達(dá)到k時(shí)，節(jié)點(diǎn)如果在形心位置，則需要在子單元內(nèi)部重新部署k-1只傳感器，導(dǎo)致節(jié)點(diǎn)個(gè)數(shù)較多。在保證k覆蓋的前提下，本文選擇將節(jié)點(diǎn)部署在填充單元的頂點(diǎn)上，并將節(jié)點(diǎn)采用確定性部署的放置方法來保證節(jié)點(diǎn)在能量耗盡前達(dá)到全覆蓋以及k覆蓋。

3 基于人工蜂群的改進(jìn)休眠與喚醒算法

3.1 改進(jìn)后的休眠算法

文獻(xiàn)[12]提出了一種冗余節(jié)點(diǎn)休眠算法(sleeping schedule for redundant sensors，SSRS)。算法根據(jù)傳感器節(jié)點(diǎn)s的鄰居節(jié)點(diǎn)對s覆蓋范圍內(nèi)的任意子單元頂點(diǎn)之外節(jié)點(diǎn)進(jìn)行決定參數(shù)的判斷。本文中針對目標(biāo)區(qū)域的k覆蓋要求對冗余節(jié)點(diǎn)的判斷進(jìn)行了改進(jìn)。

定義1感知強(qiáng)度(SI): 表示某傳感器節(jié)點(diǎn)對于感知范圍內(nèi)的不同位置的點(diǎn)產(chǎn)生的感知大小，感知大小由近而外遞減，對此設(shè)定SIsen為感知閾值。當(dāng)感知強(qiáng)度大于感知閾值時(shí)能夠被感知到，感知強(qiáng)度小于感知閾值時(shí)不能夠被感知。

定義2合作感知強(qiáng)度(CSI):假設(shè)對于A點(diǎn)有M只傳感器可以感知到，感知強(qiáng)度各不相同，對于A點(diǎn)所擁有的感知強(qiáng)度為所有感知強(qiáng)度之和，即為合作感知強(qiáng)度。

定義3感知貢獻(xiàn)(SC)：在A點(diǎn)周圍的M只傳感器中，H點(diǎn)對于A點(diǎn)在所有點(diǎn)中的感知比例即為感知貢獻(xiàn)。

定義4決定參數(shù)(DP)：假定A點(diǎn)有M只傳感器覆蓋到，如果M只傳感器中的一個(gè)節(jié)點(diǎn)L點(diǎn)去掉，A點(diǎn)所擁有的合作感知強(qiáng)度CSI>k×SIsen，則L點(diǎn)可以處于休眠狀態(tài)，將DP值置為1，否則置為0。

節(jié)點(diǎn)的休眠思路描述如下：1)首先將所需部署的目標(biāo)空間分為k層，每一層設(shè)定局域估計(jì)器，用來接收每層的數(shù)據(jù)傳輸。2)計(jì)算首層節(jié)點(diǎn)的感知貢獻(xiàn)，按照感知貢獻(xiàn)對除去子單元頂點(diǎn)位置的節(jié)點(diǎn)排序進(jìn)行節(jié)點(diǎn)休眠。當(dāng)節(jié)點(diǎn)的感知貢獻(xiàn)排序較低且去掉該節(jié)點(diǎn)時(shí)對整體的覆蓋度不產(chǎn)生影響，則對該節(jié)點(diǎn)進(jìn)行休眠。3)更新工作節(jié)點(diǎn)的DP值，并進(jìn)行下一層的節(jié)點(diǎn)休眠。4)判斷層級是否遍歷完成，如果未完成重復(fù)步驟(2)至步驟(3)。

3.2 基于改進(jìn)人工蜂群的喚醒算法

3.2.1 喚醒算法

傳感器節(jié)點(diǎn)在工作過程中，為了減小能量的消耗，選取合適的傳感器節(jié)點(diǎn)進(jìn)行休眠，會(huì)造成某些位置無法達(dá)到k覆蓋，此時(shí)采用喚醒算法將合適的節(jié)點(diǎn)進(jìn)行喚醒以達(dá)到網(wǎng)絡(luò)的k覆蓋。

為了均衡傳感器節(jié)點(diǎn)的使用壽命，對傳感器節(jié)點(diǎn)的能量進(jìn)行等間隔分段，這種分階段的算法稱為分階段喚醒策略(phased waking-up strategy，PWS)。假設(shè)將節(jié)點(diǎn)壽命分為相等的N個(gè)階段，則每段工作時(shí)間為T/N。

節(jié)點(diǎn)的喚醒策略描述如下：1)將傳感器節(jié)點(diǎn)的能量值分為N個(gè)階段，當(dāng)每一次被喚醒時(shí)，對應(yīng)的能量值減1，當(dāng)N為0時(shí)能量耗盡。2)在出現(xiàn)節(jié)點(diǎn)的能量消耗需要休眠的時(shí)候，此時(shí)不能滿足k覆蓋，隨機(jī)選擇節(jié)點(diǎn)喚醒，如果該節(jié)點(diǎn)在當(dāng)前工作階段未工作，喚醒此節(jié)點(diǎn)，否則重新選擇節(jié)點(diǎn)。3)循環(huán)執(zhí)行步驟(2),直至傳感器節(jié)點(diǎn)的能量耗盡。

3.2.2 改進(jìn)后的人工蜂群算法

人工蜂群(ABC)算法不僅在數(shù)值優(yōu)化問題的收斂效果相比較其他幾種智能算法效果更好，并且該算法便于理解，過程簡單，具有較強(qiáng)的穩(wěn)健性。但此類算法易陷入局部最優(yōu)。所以，本文中對該算法將搜索方法以及蜜源更新公式與最壞蜜源解進(jìn)行改進(jìn)[13]。

改進(jìn)1：將輪盤賭方法進(jìn)行調(diào)整

鑒于輪盤賭方法在選擇方面會(huì)導(dǎo)致種群的多樣性降低，從而使收斂過快。借鑒于蟻群算法中的信息素概念。在此處加入靈敏度與信息素。將某個(gè)蜜源位置的靈敏度與信息素進(jìn)行比較，若靈敏度小于信息素，則更新新的蜜源，當(dāng)靈敏度大于信息素時(shí)，保持原有蜜源位置。

改進(jìn)2：蜜源更新公式的改進(jìn)

在蜂群算法中，為了減小跟隨蜂的搜索區(qū)域，避免陷入局部最優(yōu)，在跟隨蜂與引領(lǐng)蜂之間引入相互引力概念。

對于第i只引領(lǐng)蜂與第k只引領(lǐng)蜂之間的相互引力為

(3)

式中G為萬有引力常數(shù)，F(xiàn)(xi)為第i只引領(lǐng)蜂的適應(yīng)度值,F(xk)為第k只引領(lǐng)蜂的適應(yīng)度值。

跟隨蜂蜜源的更新公式變?yōu)?/p>

(4)

式中N為蜜源總數(shù),J為第i只引領(lǐng)蜂或第k只引領(lǐng)蜂的分量。

改進(jìn)3：最差蜜源的替換

在算法的工作過程中，會(huì)有最差蜜源產(chǎn)生，這會(huì)降低算法的收斂速度，針對最差蜜源，進(jìn)行蜜源更新，選取更好的蜜源位置，以提升收斂速率。更新蜜源公式為

x′ij=xijL+xijU

(5)

(6)

3.3 融合后的算法

PWS算法雖然通過對傳感器節(jié)點(diǎn)的能量進(jìn)行劃分以合理分配節(jié)點(diǎn)的生命周期，并且分階段喚醒中會(huì)對除共用節(jié)點(diǎn)之外的節(jié)點(diǎn)進(jìn)行隨機(jī)選取，這容易使網(wǎng)絡(luò)陷入局部最優(yōu)的問題，故本文中加入改進(jìn)后的人工蜂群(IABC)算法對PWS進(jìn)行優(yōu)化，即IABCPWS算法,針對喚醒過程中的節(jié)點(diǎn)選取進(jìn)行有目標(biāo)的選擇，能夠使在喚醒節(jié)點(diǎn)時(shí)得到全局最優(yōu)解。

改進(jìn)后的步驟如下：1)針對水下三維目標(biāo)空間，將其劃分為k層，并對傳感器節(jié)點(diǎn)的使用壽命進(jìn)行同等劃分。定義一個(gè)能量閾值E，作為節(jié)點(diǎn)喚醒的標(biāo)準(zhǔn)。2)比較當(dāng)前階段能量閾值與傳感器節(jié)點(diǎn)的能量，如果小于閾值節(jié)點(diǎn)休眠。3)使用改進(jìn)后的人工蜂群算法在喚醒節(jié)點(diǎn)的選取上，選取更優(yōu)的節(jié)點(diǎn)位置以達(dá)到k覆蓋。4)重復(fù)執(zhí)行步驟(3)，直到節(jié)點(diǎn)的能量耗盡。

4 仿真實(shí)驗(yàn)與性能評價(jià)

4.1 仿真參數(shù)設(shè)置

假設(shè)在300 m×300 m×300 m的立方體區(qū)域內(nèi)部鑲嵌截角八面體，并部署傳感器節(jié)點(diǎn)。仿真參數(shù)如表1。

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

4.2 仿真結(jié)果分析

圖2比較了本文算法中引入人工蜂群算法與原始PWS算法傳感器的覆蓋率變化。其中橫坐標(biāo)代表了傳感器網(wǎng)絡(luò)工作的階段，縱坐標(biāo)代表網(wǎng)絡(luò)的覆蓋率。在初始化階段，PWS算法由于隨機(jī)喚醒節(jié)點(diǎn)，不考慮所喚醒節(jié)點(diǎn)產(chǎn)生多少作用，雖然覆蓋率很高，但同時(shí)造成節(jié)點(diǎn)能量損耗嚴(yán)重。而本文算法在喚醒節(jié)點(diǎn)時(shí)采用人工蜂群算法進(jìn)行選擇，雖然在初始階段覆蓋率會(huì)有不足，但延長了整個(gè)網(wǎng)絡(luò)的工作時(shí)長。

圖2 覆蓋率變化

圖3比較了本文算法與原始PWS算法在節(jié)點(diǎn)工作的能量變化。其中橫坐標(biāo)代表了傳感器網(wǎng)絡(luò)的工作階段，縱坐標(biāo)代表了節(jié)點(diǎn)剩余能量。PWS算法的能量呈線性下降，能量消耗極快，對于延長節(jié)點(diǎn)的生命周期效果并不好。在引入人工蜂群算法有序的挑選喚醒節(jié)點(diǎn)后，可以看到節(jié)點(diǎn)的能量下降趨勢有明顯緩解，并延長了節(jié)點(diǎn)以及網(wǎng)絡(luò)的生命周期。

圖3 節(jié)點(diǎn)能量變化

5 結(jié) 論

本文提出了一種改進(jìn)的節(jié)點(diǎn)休眠與喚醒算法，并將其實(shí)現(xiàn)在三維目標(biāo)空間中，經(jīng)過比較，延長了三維空間中WSNs的生命周期以及保證了目標(biāo)空間的k重覆蓋。下一步工作將引入WSNs的連通性問題，針對本文模型的連通性算法進(jìn)行研究。