基于同構(gòu)傳感器網(wǎng)絡(luò)的能量空洞避免策略*

龍勝春，盧定乾，池凱凱（浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023）

?

基于同構(gòu)傳感器網(wǎng)絡(luò)的能量空洞避免策略*

龍勝春*，盧定乾，池凱凱
（浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023）

摘要：針對無線傳感器網(wǎng)絡(luò)中網(wǎng)絡(luò)能量損耗不均勻的問題，提出了基于同構(gòu)傳感器網(wǎng)絡(luò)的能量空洞避免策略。首先對原有的LEACH路由算法進(jìn)行改進(jìn)，得到均衡簇規(guī)模的BCS-L分簇算法；然后聯(lián)合應(yīng)用BCS-L算法與分環(huán)網(wǎng)絡(luò)結(jié)構(gòu)，以節(jié)點(diǎn)能耗均衡為目標(biāo)，將能量空洞避免問題轉(zhuǎn)化為求相鄰環(huán)帶的外半徑的多項(xiàng)式問題，并通過最小化最內(nèi)層環(huán)帶節(jié)點(diǎn)的能量消耗得到最內(nèi)層環(huán)帶的半徑，最后得到符合實(shí)際網(wǎng)絡(luò)分布的局部最優(yōu)解，即除最外層環(huán)帶的其余環(huán)帶節(jié)點(diǎn)能耗均衡。理論分析和實(shí)驗(yàn)結(jié)果表明，所提出的策略與傳統(tǒng)分環(huán)網(wǎng)絡(luò)相比，大幅地提高了網(wǎng)絡(luò)壽命，較大地改善了網(wǎng)絡(luò)的性能，是解決能量空洞問題的有效方案。

關(guān)鍵詞：同構(gòu)傳感器網(wǎng)絡(luò)；能耗均衡；BCS-L算法；環(huán)帶

無線傳感器網(wǎng)絡(luò)由部署在檢測區(qū)域內(nèi)的大量微型、廉價(jià)、低功耗的傳感器節(jié)點(diǎn)組成，這些節(jié)點(diǎn)可以是人工布置或用飛行器拋灑，不同的應(yīng)用場景需要不同的散布方式。節(jié)點(diǎn)一旦布置，便通過自組織快速形成一個(gè)無線網(wǎng)絡(luò)。節(jié)點(diǎn)既是信息的采集和發(fā)出者，也充當(dāng)信息的路由者，采集到的數(shù)據(jù)通過多跳路由到達(dá)網(wǎng)關(guān)。網(wǎng)關(guān)（一些文獻(xiàn)也稱為Sink，以下統(tǒng)稱Sink節(jié)點(diǎn)）是一個(gè)特殊節(jié)點(diǎn)，可以通過In?ternet、移動(dòng)通信網(wǎng)絡(luò)、衛(wèi)星等與監(jiān)控中心通信，也可以利用飛行器飛躍網(wǎng)絡(luò)上空通過網(wǎng)關(guān)采集數(shù)據(jù)。

由于無線傳感器網(wǎng)絡(luò)初始部署的隨機(jī)性，導(dǎo)致不同的檢測區(qū)域具有不同的節(jié)點(diǎn)密度。當(dāng)傳感器節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)，由于節(jié)點(diǎn)通信半徑較小，網(wǎng)絡(luò)中的一部分節(jié)點(diǎn)不僅需要發(fā)送自身的感知數(shù)據(jù)，同時(shí)還需要為其鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)［1］。特別的，越靠近Sink的傳感器節(jié)點(diǎn)，所需轉(zhuǎn)發(fā)的數(shù)據(jù)量越大，頻繁的數(shù)據(jù)轉(zhuǎn)發(fā)必然會(huì)引起大量的能量消耗，因此，這類通信負(fù)載較重的傳感器節(jié)點(diǎn)將在極短的時(shí)間內(nèi)耗盡能量。當(dāng)靠近Sink的傳感器節(jié)點(diǎn)因能量耗盡而失效時(shí)，其所在區(qū)域?qū)⒊蔀橐粋€(gè)覆蓋空洞，通常被稱為“能量空洞”［2］現(xiàn)象。一旦發(fā)生“能量空洞”現(xiàn)象，網(wǎng)絡(luò)連通性將遭到嚴(yán)重破壞，其他傳感器節(jié)點(diǎn)采集的數(shù)據(jù)將無法傳遞到Sink節(jié)點(diǎn)［3］，整個(gè)網(wǎng)絡(luò)不得不宣告“死亡”，但是此時(shí)網(wǎng)絡(luò)中其他節(jié)點(diǎn)仍有大量的能量剩余。如何避免這種“能量空洞”現(xiàn)象，使得整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的負(fù)載平衡，從而延長整個(gè)網(wǎng)絡(luò)的生命周期和提高網(wǎng)絡(luò)性能，成為當(dāng)前無線傳感器網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)。

1　相關(guān)工作

當(dāng)前解決能量空洞的方法主要是最大限度地均衡網(wǎng)絡(luò)負(fù)載，大部分的研究［4-6］都集中在環(huán)狀傳感器網(wǎng)絡(luò)，這是因?yàn)椤澳芰靠斩础爆F(xiàn)象中提前“死亡”的節(jié)點(diǎn)圍繞在基站附近近似形成一個(gè)環(huán)形包圍著基站節(jié)點(diǎn)，研究環(huán)狀傳感器網(wǎng)絡(luò)更有利于解決能量空洞問題。

針對環(huán)狀無線傳感器網(wǎng)絡(luò)的研究大致可以分為兩類，一種是基于等環(huán)帶寬度的異構(gòu)傳感器網(wǎng)絡(luò)的研究，一種是基于不等環(huán)帶寬度的同構(gòu)傳感器網(wǎng)絡(luò)的研究。異構(gòu)傳感器網(wǎng)絡(luò)通常是給近基站的環(huán)帶分配更多的傳感器節(jié)點(diǎn)或者給近基站的傳感器節(jié)點(diǎn)分配更多的初始能量，以實(shí)現(xiàn)能量均衡的效果。

文獻(xiàn)［4］提出了一種初始能量不均勻策略。作者假定節(jié)點(diǎn)均勻分布于一個(gè)矩形區(qū)域中，同時(shí)根據(jù)Sink節(jié)點(diǎn)的位置將區(qū)域劃分為幾個(gè)小區(qū)域，根據(jù)網(wǎng)絡(luò)中不能再傳輸數(shù)據(jù)時(shí)節(jié)點(diǎn)的剩余能量來重新分布節(jié)點(diǎn)的初始能量。最終，距離Sink節(jié)點(diǎn)越近的節(jié)點(diǎn)，分配的初始能量越大。

文獻(xiàn)［6］中設(shè)WSN中節(jié)點(diǎn)不均勻分布，從理論上推導(dǎo)出完全避免能量空洞問題的策略是不存在的，但除最外層之外的各個(gè)環(huán)帶（ring）中節(jié)點(diǎn)的能量均衡是可以達(dá)成的，并提出了一種能量均衡的路由算法，可使得無線傳感器網(wǎng)絡(luò)所耗費(fèi)的能量可以降低10%。

這種策略在理論上是可行的，但在布網(wǎng)時(shí)，特別是部署大型傳感器網(wǎng)絡(luò)時(shí)要專門為特定的區(qū)域布置大量的節(jié)點(diǎn)或一些初始能量較高的節(jié)點(diǎn)，這樣就增大了工作難度，特別是在一些極端的環(huán)境下布網(wǎng)更為困難。另外，傳感器節(jié)點(diǎn)的初始能量原本就是制約無線傳感器網(wǎng)絡(luò)發(fā)展的一個(gè)重要因素，因此這種策略在實(shí)際實(shí)施起來非常困難。

而同構(gòu)傳感器網(wǎng)絡(luò)要求節(jié)點(diǎn)密度均勻，節(jié)點(diǎn)自身的參數(shù)都要保持一致，因此在布網(wǎng)時(shí)就比異構(gòu)傳感器網(wǎng)絡(luò)簡單的多，而且更加適用于大型傳感器網(wǎng)絡(luò)。而分簇網(wǎng)絡(luò)由于具有更高的能量效率因而對其進(jìn)行能量空洞避免的研究往往更具有意義。

LEACH算法［7］是最早提出的分簇路由協(xié)議，算法的基本思想是：以循環(huán)的方式隨機(jī)選擇簇頭節(jié)點(diǎn)，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)中，從而達(dá)到降低網(wǎng)絡(luò)能源消耗、提高網(wǎng)絡(luò)整體生存時(shí)間的目的。LEACH算法的每輪循環(huán)大致包括以下幾個(gè)階段：①簇頭的選舉［8］；②簇的建立；③簇的路由。

LEACH算法簇頭的選舉過程是：每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0~1之間的隨機(jī)數(shù)，如果這個(gè)數(shù)小于閾值T （n），則該節(jié)點(diǎn)向周圍節(jié)點(diǎn)廣播它是簇頭的消息。T （n）的計(jì)算公式如下：

其中：p是簇頭節(jié)點(diǎn)的百分比；r為當(dāng)前輪數(shù)；G是最近1/p輪中未當(dāng)選簇頭的節(jié)點(diǎn)集合；mod是求模運(yùn)算。

簇頭節(jié)點(diǎn)選定后，廣播自己成為簇頭的消息，剩余節(jié)點(diǎn)根據(jù)收到消息的強(qiáng)弱決定加入哪個(gè)簇，并告知簇頭，完成簇的建立過程。

本文結(jié)合LEACH算法，考慮到節(jié)點(diǎn)剩余能量，節(jié)點(diǎn)到簇頭節(jié)點(diǎn)的距離等因素提出一種基于LEACH的改進(jìn)型算法（BCS-L算法），并將此算法應(yīng)用進(jìn)環(huán)狀網(wǎng)絡(luò)，提出了一種基于環(huán)形傳感器網(wǎng)絡(luò)的能量空洞避免策略，來平衡整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗，最后通過控制各個(gè)環(huán)帶的寬度，使各個(gè)環(huán)帶中的節(jié)點(diǎn)的能量消耗最終達(dá)到均衡。

2　系統(tǒng)模型

2.1網(wǎng)絡(luò)結(jié)構(gòu)模型

本文對無線傳感器網(wǎng)絡(luò)做出如下假設(shè)：①半徑為R的圓形無線傳感器網(wǎng)絡(luò)，節(jié)點(diǎn)均勻分布，且密度為ρ，Sink節(jié)點(diǎn)位于圓心位置，且具有較強(qiáng)的計(jì)算、存儲(chǔ)能力，且無能量限制。②節(jié)點(diǎn)同構(gòu)，即除Sink節(jié)點(diǎn)外所有的節(jié)點(diǎn)擁有相同的特性，如初始總能量Eini、通信半徑等，節(jié)點(diǎn)可以獲知自身的當(dāng)前能量Er；③每個(gè)節(jié)點(diǎn)有唯一的ID，可獲知自己的坐標(biāo)信息，都能競爭為簇頭或者普通節(jié)點(diǎn)；④節(jié)點(diǎn)通信功率可以調(diào)節(jié)，通過接收信號的強(qiáng)度計(jì)算出節(jié)點(diǎn)之間的距離；⑤在本文中通過增加采集數(shù)據(jù)的冗余度提高數(shù)據(jù)的準(zhǔn)確性［9］，并通過數(shù)據(jù)融合壓縮技術(shù)［10］減少數(shù)據(jù)傳輸任務(wù)。節(jié)點(diǎn)的感知半徑一般不超過70 m（參照美國SG-Link?-LXRS無線節(jié)點(diǎn)），在密度為平均每平方米布置一個(gè)節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)中，當(dāng)節(jié)點(diǎn)采用較大的感知半徑時(shí)會(huì)導(dǎo)致自身的能耗急劇增加。為了簡化計(jì)算，本文采用的節(jié)點(diǎn)的感知半徑為5.7 m，此時(shí)臨近范圍內(nèi)節(jié)點(diǎn)采集到的數(shù)據(jù)重復(fù)率幾近達(dá)到100倍，這樣既能提高數(shù)據(jù)的準(zhǔn)確性，同時(shí)也沒有增大節(jié)點(diǎn)的自身能耗。

2.2能量消耗模型

本文采用典型能量消耗模型［11-12］，不計(jì)節(jié)點(diǎn)在計(jì)算、存儲(chǔ)過程中的能量消耗，僅計(jì)算通信能耗。在傳輸l bit信息經(jīng)過距離d的過程中，發(fā)送端能量消耗為：

接收端的能量消耗為：

其中，Eelec是指發(fā)送或接收每比特?cái)?shù)據(jù)消耗的能量，后文中簡寫成Ee；Efsd2和Empd4是發(fā)送每比特?cái)?shù)據(jù)放大器的能量消耗，d0為一閾值，本文定義為87.7 m，若發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)的距離小于d0，發(fā)送方的放大器能量消耗與距離的平方成正比，否則成4次方正比。由于一般布網(wǎng)是節(jié)點(diǎn)之間距離不會(huì)超過87.7 m，因此本文采用Efsd2作為發(fā)送每比特?cái)?shù)據(jù)的放大器的能量消耗。在本文中，以上參數(shù)的具體設(shè)置參照文獻(xiàn)［12］，見表1。

表1　仿真參數(shù)表

3　基于同構(gòu)網(wǎng)絡(luò)的能量空洞避免策略

本文定義在密度為ρ的圓形網(wǎng)絡(luò)中，網(wǎng)絡(luò)可以被分成n個(gè)同心環(huán)帶，定義M1，M2，…，Mn為從內(nèi)到外n層相鄰?fù)膱A環(huán)，環(huán)帶Mk中節(jié)點(diǎn)的總數(shù)為Nk（k=1，2，3，…，n），環(huán)帶外半徑為rk（k=1，2，3，…，n），即rn=R。為方便計(jì)算令r0=0，表示Sink節(jié)點(diǎn)。

設(shè)環(huán)帶Mk中的節(jié)點(diǎn)進(jìn)行平均分簇，簇頭節(jié)點(diǎn)的覆蓋半徑為（rk-rk-1）/2，每個(gè)簇頭節(jié)點(diǎn)覆蓋的面積為π［（rk-rk-1）/2］2，那么此圓環(huán)中應(yīng)該部署的簇頭節(jié)點(diǎn)個(gè)數(shù)Ck為：

此環(huán)中平均每個(gè)簇中的節(jié)點(diǎn)總數(shù)Ak（包括簇頭節(jié)點(diǎn)）為：

因?yàn)樵谕画h(huán)帶內(nèi)相鄰節(jié)點(diǎn)之間所采集的數(shù)據(jù)具有很大的相關(guān)性，因此在每個(gè)簇中，簇頭對接收到的簇內(nèi)數(shù)據(jù)進(jìn)行融合壓縮，減少網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量，達(dá)到節(jié)約網(wǎng)絡(luò)能量的目的。本文假設(shè)每個(gè)節(jié)點(diǎn)采集到l bit的數(shù)據(jù)，簇頭的壓縮率為α，即簇頭接收到的Ak×l bit的數(shù)據(jù)，壓縮為Ak×l×α bit數(shù)據(jù)，且壓縮單位比特?cái)?shù)據(jù)的能量消耗為EDA，根據(jù)以上能量消耗模型，可以得知第k環(huán)中的單個(gè)簇中的簇頭接收簇內(nèi)數(shù)據(jù)并壓縮的能耗ECHK，見式（6）：

簇中非簇頭節(jié)點(diǎn)的能耗ENCHK為：

其中dtoC表示普通節(jié)點(diǎn)到簇頭節(jié)點(diǎn)的平均傳輸距離，本文取做簇頭節(jié)點(diǎn)的覆蓋半徑。

3.1BCS-L算法

BCS-L（Balanced Cluster Scale-LEACH）算法是針對LEACH協(xié)議每輪循環(huán)的第一階段和第二階段進(jìn)行改進(jìn)。

在簇頭的選舉之前，環(huán)帶中節(jié)點(diǎn)先判斷自己的當(dāng)前能量Er是否能滿足作為簇頭節(jié)點(diǎn)的能耗，即：當(dāng)Er>ECHK時(shí)，該節(jié)點(diǎn)參加簇頭的選舉，否則不參加簇頭節(jié)點(diǎn)的競爭。

在選擇簇頭時(shí)，將節(jié)點(diǎn)的剩余能量考慮進(jìn)去，調(diào)整后的簇頭閾值計(jì)算方法：

其中：T（n）k為環(huán)帶Mk中的簇頭閾值計(jì)算方法；p是簇頭節(jié)點(diǎn)的百分比，在環(huán)帶Mk中p=1/Ak；r為當(dāng)前輪數(shù)；G是最近1/p輪中未當(dāng)選簇頭的節(jié)點(diǎn)集合；Er為節(jié)點(diǎn)自身的當(dāng)前能量；Eini為節(jié)點(diǎn)的初始總能量。

改進(jìn)后的閾值計(jì)算方法降低了當(dāng)前能量較低的節(jié)點(diǎn)當(dāng)選為簇頭節(jié)點(diǎn)的幾率，使得環(huán)帶中節(jié)點(diǎn)的能量消耗更加均衡。

在環(huán)帶Mk內(nèi)，定義CHk為當(dāng)選為簇頭節(jié)點(diǎn)的個(gè)數(shù)，式（4）中Ck為應(yīng)該部署的簇頭節(jié)點(diǎn)個(gè)數(shù)，當(dāng)CHkCk時(shí)，不做任何處理。

簇頭節(jié)點(diǎn)選定后，簇的循環(huán)進(jìn)入第二階段：簇的建立。定義Thdis為簇中節(jié)點(diǎn)到簇頭節(jié)點(diǎn)的距離閾值，且Thdis=rk-rk-1；Thcluster為平均每個(gè)簇中的節(jié)點(diǎn)個(gè)數(shù)的閾值且Thcluster=Ak，從而有如下算法：

算法：輸入：簇頭節(jié)點(diǎn)的個(gè)數(shù)（CHk）；節(jié)點(diǎn)i到簇頭j的距離（DIST［i，j］），簇j中當(dāng)前節(jié)點(diǎn)的個(gè)數(shù)（CLUSTER［j］）輸出：選擇簇頭節(jié)點(diǎn)j加入①節(jié)點(diǎn)i向距離DIST［i，j］小于閾值Thdis的簇頭節(jié)點(diǎn)j發(fā)送申請加入的信息；②簇頭節(jié)點(diǎn)收到消息后判斷此時(shí)自己簇中的節(jié)點(diǎn)個(gè)數(shù)（CLUSTER［j］）是否小于閾值Thcluster，若小于，則向節(jié)點(diǎn)j回復(fù)“YES”；否則回復(fù)“NO”；③節(jié)點(diǎn)i根據(jù)收到的信息，向回復(fù)了“YES”的簇頭中離得最近的那個(gè)簇頭發(fā)送“確認(rèn)加入”的信息；至此節(jié)點(diǎn)i加入簇j中。

簇頭節(jié)點(diǎn)廣播自己成為簇頭的消息，普通節(jié)點(diǎn)收到消息后，根據(jù)上述算法選擇加入哪個(gè)簇，并告知相應(yīng)的簇頭，完成簇的建立過程。上述算法保證了簇中節(jié)點(diǎn)的個(gè)數(shù)不會(huì)超過Thcluster，有效避免了個(gè)別簇中節(jié)點(diǎn)數(shù)量過多導(dǎo)致的能量消耗不均衡的問題。

3.2基于同構(gòu)網(wǎng)絡(luò)的分環(huán)策略

下面計(jì)算環(huán)帶Mk中的簇頭節(jié)點(diǎn)處理外層簇頭節(jié)點(diǎn)發(fā)送的消息的能量消耗ET，由于簇頭與簇頭之間進(jìn)行數(shù)據(jù)傳輸時(shí)，不對收到的數(shù)據(jù)進(jìn)行壓縮，收到外層簇頭的消息直接轉(zhuǎn)發(fā)至下一跳（內(nèi)層簇頭節(jié)點(diǎn)），定義環(huán)帶Mk中簇頭接收到的總數(shù)據(jù)量為Rk（k=1，2，3，…，n-1）：

所需轉(zhuǎn)發(fā)的總數(shù)據(jù)量為Tk（k=1，2，3，…，n）：

式（10）中Ck×Ak表示環(huán)帶Mk中的節(jié)點(diǎn)總數(shù)。最外層的簇頭節(jié)點(diǎn)只有發(fā)送數(shù)據(jù)，沒有接收數(shù)據(jù)，故Rn=0，最外層簇頭節(jié)點(diǎn)只需要將自己簇內(nèi)的數(shù)據(jù)壓縮后傳遞給環(huán)帶Mk-1中的簇頭節(jié)點(diǎn)，故Tn=Nnla，由式（9）和式（10）推導(dǎo)出：

其中Ni表示當(dāng)i=k時(shí)環(huán)帶Mk中的節(jié)點(diǎn)總數(shù)。

定義環(huán)帶Mk內(nèi)的平均每個(gè)簇頭節(jié)點(diǎn)需要接收的外層數(shù)據(jù)為Rk（k=1，2，…，n-1），則：

所需發(fā)送的平均數(shù)據(jù)為Tk（1，2，…，n）：

為了簡化模型，假設(shè)在環(huán)帶Mk內(nèi)的簇頭節(jié)點(diǎn)到下一跳的傳輸距離等于環(huán)帶的寬度dk，即：dk=rk

rk-1。定義Ek（l，dk）表示環(huán)帶Mk內(nèi)單個(gè)簇頭節(jié)點(diǎn)在單位時(shí)間內(nèi)平均消耗的能量，得到：

展開式（15），得到：

由于最外層環(huán)內(nèi)的簇頭節(jié)點(diǎn)只處理簇內(nèi)數(shù)據(jù)，沒有外層環(huán)的數(shù)據(jù)需要轉(zhuǎn)發(fā)，因此環(huán)帶Cn內(nèi)簇頭節(jié)點(diǎn)在單位時(shí)間內(nèi)的平均能耗為：

由于大規(guī)模無線傳感器網(wǎng)絡(luò)自身的局限性，靠近基站的節(jié)點(diǎn)承擔(dān)了更多的通信負(fù)載，消耗了更多的能量，在節(jié)點(diǎn)初始能量都相同的情況下，最內(nèi)層的節(jié)點(diǎn)往往最快耗盡能量，并最終導(dǎo)致整個(gè)網(wǎng)絡(luò)的死亡。因此最內(nèi)層環(huán)帶節(jié)點(diǎn)的生命周期決定了整個(gè)網(wǎng)絡(luò)的生存周期，提高整個(gè)網(wǎng)絡(luò)的生存時(shí)間的關(guān)鍵就是降低最內(nèi)層環(huán)帶M1內(nèi)節(jié)點(diǎn)在單位時(shí)間的平均能耗。

環(huán)帶M1中，無線通信半徑為d1=r1，簇中普通節(jié)點(diǎn)的通信半徑dtoC=r1/2，r0=0，由式（16）得到：

對式（18）求導(dǎo)得：

最后能夠求出使得E1=（l，d1）最小的半徑r1為：

結(jié)果顯示，最內(nèi)層環(huán)帶M1的環(huán)帶寬度不僅與網(wǎng)絡(luò)半徑R有關(guān)，還與網(wǎng)絡(luò)中的節(jié)點(diǎn)密度ρ、數(shù)據(jù)壓縮率α和Ee、Efs相關(guān)。由求得的r1代入式（18）可求出最內(nèi)層環(huán)帶M1內(nèi)的單個(gè)節(jié)點(diǎn)在單位時(shí)間內(nèi)的平均消耗的能量E1（l，d1）。

當(dāng)簇頭節(jié)點(diǎn)的能量消耗均衡時(shí)，其能量效率最高，因此有下式成立：

4　計(jì)算與實(shí)驗(yàn)結(jié)果

本文采用的傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)密度為平均每平方米1個(gè)節(jié)點(diǎn)，在節(jié)點(diǎn)的平均感知半徑為5.7 m的網(wǎng)絡(luò)中，同一數(shù)據(jù)能同時(shí)被一百多個(gè)節(jié)點(diǎn)感知到，為減少這種重復(fù)率，定義平均每個(gè)節(jié)點(diǎn)所采集數(shù)據(jù)的1%為有效數(shù)據(jù)，然后對有效數(shù)據(jù)進(jìn)行壓縮，最后融合壓縮率［9］為α=0.001，根據(jù)式（20）、式（21）和表1中各參數(shù)，可以推導(dǎo)出當(dāng)無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)半徑為R取不同的值時(shí)，各個(gè)環(huán)帶的環(huán)帶寬度，如圖1所示。

圖1　各層環(huán)帶寬度

如圖1所示，當(dāng)圓形網(wǎng)絡(luò)的半徑R固定時(shí)，假設(shè)節(jié)點(diǎn)單位時(shí)間產(chǎn)生的數(shù)據(jù)量為4 000 bit［8］，為使得各層環(huán)帶的節(jié)點(diǎn)平均能耗均衡，環(huán)帶的寬度由內(nèi)到外是逐漸增大的，環(huán)帶M1與環(huán)帶M2的寬度相差較大，環(huán)帶M2以上的環(huán)帶寬度相差不大。圖中每條折線的最后一個(gè)點(diǎn)都比較低是因?yàn)樵趯W(wǎng)絡(luò)進(jìn)行分環(huán)時(shí)，環(huán)帶的外半徑不能大于網(wǎng)絡(luò)半徑R。當(dāng)網(wǎng)絡(luò)半徑R越來越大時(shí)，在能耗均衡的條件下各層環(huán)帶的寬度普遍增大，整體變化趨勢相似。

從圖2可以看出，同一個(gè)網(wǎng)絡(luò)中，不同環(huán)帶內(nèi)節(jié)點(diǎn)在單位時(shí)間內(nèi)的節(jié)點(diǎn)平均能耗基本相同，最外層環(huán)帶的節(jié)點(diǎn)平均能耗均比內(nèi)層的能耗低，因此本文算法能夠?qū)崿F(xiàn)局部最優(yōu)。

圖2　環(huán)帶內(nèi)節(jié)點(diǎn)單位時(shí)間平均能耗

本文算法采用MATLAB 8.3仿真軟件進(jìn)行建模仿真，仿真的網(wǎng)絡(luò)半徑R=100 m。參考一節(jié)普通AA電池至少有1 000 J的能量，當(dāng)采用電池給節(jié)點(diǎn)供電時(shí)，理論上節(jié)點(diǎn)的初始能量Eini=1 000 J。

圖3　最內(nèi)層環(huán)帶網(wǎng)絡(luò)壽命

圖3顯示本文算法所得到的分環(huán)網(wǎng)絡(luò)和簡單分環(huán)網(wǎng)絡(luò)的網(wǎng)絡(luò)壽命。簡單分環(huán)網(wǎng)絡(luò)工作方式如下：傳感器節(jié)點(diǎn)在各個(gè)環(huán)帶的密度按照從外環(huán)到內(nèi)環(huán)呈幾何級數(shù)遞增的方式部署，即越靠近基站的環(huán)帶布置的節(jié)點(diǎn)密度越大，通過增加內(nèi)層環(huán)帶節(jié)點(diǎn)的密度來降低靠近基站的節(jié)點(diǎn)的平均能量消耗。各個(gè)環(huán)帶中的節(jié)點(diǎn)既要采集數(shù)據(jù)，又要接收相鄰?fù)鈱迎h(huán)帶轉(zhuǎn)發(fā)的數(shù)據(jù)，然后將所有數(shù)據(jù)通過最短路徑路由算法轉(zhuǎn)發(fā)給相鄰內(nèi)層環(huán)帶，最終將數(shù)據(jù)匯聚到Sink節(jié)點(diǎn)。采用本文均衡網(wǎng)絡(luò)算法時(shí)，最內(nèi)層環(huán)帶的節(jié)點(diǎn)耗盡所有能量大致需要平均2 133個(gè)單位時(shí)間；文獻(xiàn)［6］中提出的基于環(huán)的能量均衡策略在一定程度上能將無線傳感器網(wǎng)絡(luò)的能耗降低10%左右，但是在本文的仿真中，最內(nèi)層環(huán)帶的節(jié)點(diǎn)在1 006個(gè)單位時(shí)間時(shí)就幾乎耗盡能量，因此本文算法在壽命上幾乎比單純的分環(huán)網(wǎng)絡(luò)提高接近一倍多。這是因?yàn)樵诒疚牡姆汁h(huán)網(wǎng)絡(luò)中，采用分簇算法，簇內(nèi)數(shù)據(jù)壓縮率為α=0.001，相比于沒有分簇的網(wǎng)絡(luò)，環(huán)帶與環(huán)帶之間傳遞的數(shù)據(jù)量僅占沒有分簇網(wǎng)絡(luò)的α倍，在很大程度上降低了網(wǎng)絡(luò)中流通的數(shù)據(jù)量。

5　總結(jié)

無線傳感器網(wǎng)絡(luò)是近幾年來興起的研究熱點(diǎn)，其中，無線傳感器的能源效率和壽命問題成為人們最為關(guān)心的問題之一。

本文提出的基于同構(gòu)傳感器網(wǎng)絡(luò)的能量空洞避免策略就是將分簇算法融入進(jìn)環(huán)狀網(wǎng)絡(luò)，大量降低了網(wǎng)絡(luò)中的數(shù)據(jù)流。本文算法能夠根據(jù)網(wǎng)絡(luò)半徑和節(jié)點(diǎn)密度等參數(shù)實(shí)現(xiàn)除最外層的其余環(huán)帶中節(jié)點(diǎn)能耗均衡的優(yōu)化后的分環(huán)策略。經(jīng)過理論分析和實(shí)驗(yàn)，結(jié)果表明了該策略的有效性。對比以往的研究，本文的創(chuàng)新點(diǎn)在于從網(wǎng)絡(luò)效率均衡的角度出發(fā)，從而得出更適合實(shí)際的大型無線傳感器網(wǎng)絡(luò)的應(yīng)用。進(jìn)一步工作可以從節(jié)點(diǎn)自供能等方面研究解決網(wǎng)絡(luò)能量空洞問題的策略和機(jī)制。

參考文獻(xiàn)：

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al. Wireless Sen?sor Networks：A Survey［J］. Computer Networks，2002，38（4）：393-422.

［2］吳小兵，陳貴海.無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)非均勻分布的能量空洞問題［J］.計(jì)算機(jī)學(xué)報(bào)，2008，31（2）：253-261.

［3］王亮，鐘先信，石軍鋒.無線傳感器網(wǎng)絡(luò)能耗平衡策略的研究［J］.傳感器世界，2007（3）：32-36.

［4］Lian J，Chen L，Naik K，et al. Modeling and Enbancing the Data Capacity of Wireless Sensor Networks［C］// Phoha S，La Porta T F，Griffin C，et al. IEEE Monograph on Sensor Network Opera? tions. IEEE Press，2004：91-138.

［5］Li J，Mohapatra P. An Analytical Model for the Energy Hole Prob?lem in Many-to-One Sensor Networks［C］//Proceedings of IEEE Vehicular Technology Conference Dallas，TX，2005：2721-2725.

［6］Wu X B，Chen G H，Das S K. Avoiding Energy Holes in Wireless Sensor Networks with Non-Uniform Node Distribution［J］// IEEE Transactions on Parallel and Distributed Systems，2008，19（5）：710-720.

［7］陳曉娟，王卓，吳潔.一種基于LEACH的改進(jìn)WSN路由算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26（1）：116-121.

［8］Raju Pal，Ajay K Sharma. FSEP-E：Enhanced Stable Election Pro?tocol Based on Fuzzy Logic for Cluster Head Selection in WSNs ［C］//6th International Conference on Contemporary Computing （IC3），2013：427-432.

［9］Diane I，Kacimi R，Mammeri Z，et al. Energy Optimization Based on the Redundancy in WSNs［C］//Wireless and Mobile Network?ing Conference（WMNC），2013：1-7.

［10］張美燕，蔡文郁.基于K均值分簇MST路由的無線傳感網(wǎng)壓縮采樣技術(shù)［J］.傳感技術(shù)學(xué)報(bào)，2015，28（9）：1402-1407.

［11］Ali D，Majid G，Carey W. On the Optimal Randomized Clustering in Distributed Sensor Networks［J］. Computer Networks，2014 （59）：17-32.

［12］Bo- Chao Cheng，His- Hsun Yeh，Ping- Hai Hsu. Schedulability Analysis for Hard Network Lifetime Wireless Sensor Networks with High Energy First Clustering［J］. IEEE Transactions on Reli?ability，2011，60（3）：675-688.

龍勝春（1970-），女，副教授，碩士生導(dǎo)師，主要研究方向是無線傳感器網(wǎng)絡(luò)、醫(yī)學(xué)圖像處理等，longsc@zjut.edu.cn；

盧定乾（1990-），男，碩士研究生，主要研究方向是無線傳感器網(wǎng)絡(luò)。

Detection of Coverage Hole in WSN Based on Three-Dimensional Terrain Correction*

SHEN Xianhao*，LI Jun，NAI He
（College of Information Science and Engineering，Guilin University of Technology，Guilin Guangxi 541004，China）

Abstract：Due to the characteristic of undulating terrain，it will produce the coverage holes after randomly deploy?ing sensor nodes under the three-dimensional terrain. In order to effectively detect the coverage holes，in this paper，we propose a detection method of coverage holes in wireless sensor networks（WSN）based on three-dimensional ter?rain correction. Through establishing the unit ball perception model，randomly deploying the sensor nodes，Delau?nay triangulation the sensor nodes. Calculating the circumcircle of the triangle，obtaining coverage holes boundaries based on boundary detection algorithm and eliminating false boundary node，then we obtain the improved boundary. We calculate the information of slope and aspect of sensor nodes. According to the principles of the terrain correc?tion，calculate the actual detection radius；Ultimately obtain a minimum boundary of coverage holes. Simulation re?sults show that the detection method can effectively detect coverage holes under the three-dimensional terrain. For the undulating obviously terrain，it also has some adaptability.

Key words：coverage holes；three-dimensional terrain correction；slope and aspect；Delaunay triangulation；circum?circle

doi：EEACC：6150P10.3969/j.issn.1004-1699.2016.01.019

收稿日期：2015-07-29修改日期：2015-10-26

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：A

文章編號：1004-1699（2016）01-0103-06

項(xiàng)目來源：國家自然科學(xué)基金項(xiàng)目（61472367）