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

?

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

龍勝春*，盧定乾，池凱凱
（浙江工業(yè)大學(xué)計算機(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é)點能耗均衡為目標(biāo)，將能量空洞避免問題轉(zhuǎn)化為求相鄰環(huán)帶的外半徑的多項式問題，并通過最小化最內(nèi)層環(huán)帶節(jié)點的能量消耗得到最內(nèi)層環(huán)帶的半徑，最后得到符合實際網(wǎng)絡(luò)分布的局部最優(yōu)解，即除最外層環(huán)帶的其余環(huán)帶節(jié)點能耗均衡。理論分析和實驗結(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é)點可以是人工布置或用飛行器拋灑，不同的應(yīng)用場景需要不同的散布方式。節(jié)點一旦布置，便通過自組織快速形成一個無線網(wǎng)絡(luò)。節(jié)點既是信息的采集和發(fā)出者，也充當(dāng)信息的路由者，采集到的數(shù)據(jù)通過多跳路由到達(dá)網(wǎng)關(guān)。網(wǎng)關(guān)（一些文獻(xiàn)也稱為Sink，以下統(tǒng)稱Sink節(jié)點）是一個特殊節(jié)點，可以通過In?ternet、移動通信網(wǎng)絡(luò)、衛(wèi)星等與監(jiān)控中心通信，也可以利用飛行器飛躍網(wǎng)絡(luò)上空通過網(wǎng)關(guān)采集數(shù)據(jù)。

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

1　相關(guān)工作

當(dāng)前解決能量空洞的方法主要是最大限度地均衡網(wǎng)絡(luò)負(fù)載，大部分的研究［4-6］都集中在環(huán)狀傳感器網(wǎng)絡(luò)，這是因為“能量空洞”現(xiàn)象中提前“死亡”的節(jié)點圍繞在基站附近近似形成一個環(huán)形包圍著基站節(jié)點，研究環(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é)點或者給近基站的傳感器節(jié)點分配更多的初始能量，以實現(xiàn)能量均衡的效果。

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

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

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

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

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

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

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

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

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

2　系統(tǒng)模型

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

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

2.2能量消耗模型

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

接收端的能量消耗為：

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

表1　仿真參數(shù)表

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

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

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

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

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

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

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

3.1BCS-L算法

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

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

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

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

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

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

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

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

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

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

下面計算環(huán)帶Mk中的簇頭節(jié)點處理外層簇頭節(jié)點發(fā)送的消息的能量消耗ET，由于簇頭與簇頭之間進(jìn)行數(shù)據(jù)傳輸時，不對收到的數(shù)據(jù)進(jìn)行壓縮，收到外層簇頭的消息直接轉(zhuǎn)發(fā)至下一跳（內(nèi)層簇頭節(jié)點），定義環(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é)點總數(shù)。最外層的簇頭節(jié)點只有發(fā)送數(shù)據(jù)，沒有接收數(shù)據(jù)，故Rn=0，最外層簇頭節(jié)點只需要將自己簇內(nèi)的數(shù)據(jù)壓縮后傳遞給環(huán)帶Mk-1中的簇頭節(jié)點，故Tn=Nnla，由式（9）和式（10）推導(dǎo)出：

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

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

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

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

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

展開式（15），得到：

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

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

環(huán)帶M1中，無線通信半徑為d1=r1，簇中普通節(jié)點的通信半徑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é)點密度ρ、數(shù)據(jù)壓縮率α和Ee、Efs相關(guān)。由求得的r1代入式（18）可求出最內(nèi)層環(huán)帶M1內(nèi)的單個節(jié)點在單位時間內(nèi)的平均消耗的能量E1（l，d1）。

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

4　計算與實驗結(jié)果

本文采用的傳感器網(wǎng)絡(luò)的節(jié)點密度為平均每平方米1個節(jié)點，在節(jié)點的平均感知半徑為5.7 m的網(wǎng)絡(luò)中，同一數(shù)據(jù)能同時被一百多個節(jié)點感知到，為減少這種重復(fù)率，定義平均每個節(jié)點所采集數(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取不同的值時，各個環(huán)帶的環(huán)帶寬度，如圖1所示。

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

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

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

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

本文算法采用MATLAB 8.3仿真軟件進(jìn)行建模仿真，仿真的網(wǎng)絡(luò)半徑R=100 m。參考一節(jié)普通AA電池至少有1 000 J的能量，當(dāng)采用電池給節(jié)點供電時，理論上節(jié)點的初始能量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é)點在各個環(huán)帶的密度按照從外環(huán)到內(nèi)環(huán)呈幾何級數(shù)遞增的方式部署，即越靠近基站的環(huán)帶布置的節(jié)點密度越大，通過增加內(nèi)層環(huán)帶節(jié)點的密度來降低靠近基站的節(jié)點的平均能量消耗。各個環(huán)帶中的節(jié)點既要采集數(shù)據(jù)，又要接收相鄰?fù)鈱迎h(huán)帶轉(zhuǎn)發(fā)的數(shù)據(jù)，然后將所有數(shù)據(jù)通過最短路徑路由算法轉(zhuǎn)發(fā)給相鄰內(nèi)層環(huán)帶，最終將數(shù)據(jù)匯聚到Sink節(jié)點。采用本文均衡網(wǎng)絡(luò)算法時，最內(nèi)層環(huán)帶的節(jié)點耗盡所有能量大致需要平均2 133個單位時間；文獻(xiàn)［6］中提出的基于環(huán)的能量均衡策略在一定程度上能將無線傳感器網(wǎng)絡(luò)的能耗降低10%左右，但是在本文的仿真中，最內(nèi)層環(huán)帶的節(jié)點在1 006個單位時間時就幾乎耗盡能量，因此本文算法在壽命上幾乎比單純的分環(huán)網(wǎng)絡(luò)提高接近一倍多。這是因為在本文的分環(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ò)是近幾年來興起的研究熱點，其中，無線傳感器的能源效率和壽命問題成為人們最為關(guān)心的問題之一。

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

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