魏 鑫， 周世杰, 彭 牧, 馮 誠(chéng)

(東北林業(yè)大學(xué) 信息與計(jì)算機(jī)工程學(xué)院， 哈爾濱 150040)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議主要負(fù)責(zé)將數(shù)據(jù)包從源節(jié)點(diǎn)通過(guò)網(wǎng)絡(luò)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)，即在傳感器節(jié)點(diǎn)和sink節(jié)點(diǎn)之間建立路由,從而進(jìn)行可靠的數(shù)據(jù)傳輸[1-3]。分簇路由協(xié)議與其它路由協(xié)議相比具有非常明顯的優(yōu)勢(shì)[4-5]。其中，LEACH算法[6]是Heinzelman等人提出的第一個(gè)無(wú)線傳感器網(wǎng)絡(luò)自適應(yīng)分簇路由算法。由于該算法仍存在很多缺點(diǎn)，研究學(xué)者們對(duì)其進(jìn)行了諸多改進(jìn)[7-10]。Kaur等人[7]考慮到節(jié)點(diǎn)剩余能量這一因素，通過(guò)改進(jìn)閾值從而達(dá)到延長(zhǎng)網(wǎng)絡(luò)生命周期的目的，但仍顯現(xiàn)出一定不足，如并未考慮為了均衡各個(gè)節(jié)點(diǎn)的負(fù)載，需要修改各個(gè)因子的權(quán)重。唐甲東[8]提出將簇頭選舉分為全網(wǎng)選舉和簇內(nèi)選舉兩個(gè)階段，從而更好地平衡各個(gè)節(jié)點(diǎn)的能量，但依然沒(méi)有著重考慮剩余能量。Mankita等人[9]考慮到節(jié)點(diǎn)的剩余能量，通過(guò)修改閾值增大剩余能量較高的節(jié)點(diǎn)成為簇頭的概率。同時(shí)引入副簇頭(vice cluster)的概念，減少每個(gè)簇的能量消耗以延長(zhǎng)生命周期，但并未考慮某些剩余能量較高的節(jié)點(diǎn)能量利用不充分的情況。楊穎輝等人[10]考慮到節(jié)點(diǎn)剩余能量和普通節(jié)點(diǎn)距sink節(jié)點(diǎn)的距離兩種因素，提出了LEACH-O算法降低網(wǎng)絡(luò)能耗，但還需指出，研究中并未關(guān)注到隨著輪數(shù)的增加，各個(gè)因子對(duì)網(wǎng)絡(luò)負(fù)載均衡的影響力不同這一特征。本文針對(duì)LEACH算法的不足，考慮能量因子側(cè)重度對(duì)簇頭選舉閾值進(jìn)行改進(jìn)，提出一種新型的LEACH-OE(LEACH based on energy factors)自適應(yīng)算法。本文擬對(duì)此展開(kāi)研究論述如下。

1 系統(tǒng)建模

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

本文研究的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)地分布在一個(gè)正方形監(jiān)測(cè)區(qū)域內(nèi)[11]，傳感器節(jié)點(diǎn)和sink節(jié)點(diǎn)在部署之后位置固定不變[12]，并且不再進(jìn)行人為干涉；節(jié)點(diǎn)同構(gòu)且能量受限，具有相同初始能量[13]，處理能力和通信能力相等，被選中的概率相同；每個(gè)節(jié)點(diǎn)都具備了數(shù)據(jù)融合功能[14]，能感知自己的剩余能量并且具有全網(wǎng)唯一標(biāo)識(shí)ID[15]；節(jié)點(diǎn)的無(wú)線發(fā)射功率可以自我調(diào)控，可自主選擇發(fā)射功率[16]；sink節(jié)點(diǎn)計(jì)算能力和能量不受限制[17]。

1.2 能耗模型

本文采用的是一階無(wú)線電能量消耗模型(first order radio model)[18]。假設(shè)傳感器節(jié)點(diǎn)在傳輸距離為d時(shí)傳送k比特的數(shù)據(jù)，所消耗的能量為：

(1)

信號(hào)在路徑中的衰減模型分為自由空間信道模型(free space channel model)和多徑衰減信道模型(multi-path fading channel model)兩種[19]。其中，Eelec為發(fā)射電路或接收電路發(fā)送或接收1比特?cái)?shù)據(jù)的耗能；d0為自由空間信道模型與多徑衰減信道模型的切換閾值[20]，d

(2)

節(jié)點(diǎn)接收k比特?cái)?shù)據(jù)消耗的能量為ERX(k) =kEelec；對(duì)k比特?cái)?shù)據(jù)進(jìn)行數(shù)據(jù)融合消耗的能量為Eagg(k) =kEda，其中Eda為傳感器節(jié)點(diǎn)融合1比特?cái)?shù)據(jù)消耗的能量。

2 LEACH-OE算法

2.1 LEACH算法概述

LEACH算法的執(zhí)行過(guò)程是周期性的，因此可以引入“輪”的概念去描述。該算法在每輪的執(zhí)行過(guò)程中不斷地進(jìn)行簇的重構(gòu)過(guò)程，每輪循環(huán)分為簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段，后一階段通常比前一階段時(shí)間復(fù)雜度高[21]。對(duì)此可做闡釋解析如下。

2.1.1 簇的建立階段

簇的建立階段分為4個(gè)過(guò)程[22-23]。各過(guò)程設(shè)計(jì)詳情可見(jiàn)如下。

(1)簇頭節(jié)點(diǎn)的選擇。T(n)為節(jié)點(diǎn)n自身的簇頭選舉閾值，每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)，如果這個(gè)數(shù)小于其自身閾值T(n)，則該節(jié)點(diǎn)成為簇頭。T(n)值的計(jì)算公式如下：

(3)

其中,p為簇頭在所有節(jié)點(diǎn)中所占的百分比；r為當(dāng)前選舉輪數(shù)；mod為取模運(yùn)算符；G為前?1/p」輪中未當(dāng)選過(guò)簇頭的節(jié)點(diǎn)集合。隨著當(dāng)選過(guò)簇頭的節(jié)點(diǎn)數(shù)目增加，剩余節(jié)點(diǎn)的閾值T(n)隨之增加，未當(dāng)選過(guò)簇頭的節(jié)點(diǎn)成為簇頭的概率增大。LEACH算法能夠保證各個(gè)節(jié)點(diǎn)等概率地?fù)?dān)任簇頭，從而使整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)中。

(2)簇頭節(jié)點(diǎn)的廣播。節(jié)點(diǎn)成為簇頭之后，發(fā)出廣播消息通知自己是新簇頭。

(3)簇的形成。節(jié)點(diǎn)成為簇頭之后，普通節(jié)點(diǎn)根據(jù)自身與簇頭之間通信的強(qiáng)弱來(lái)決定加入哪個(gè)簇并告知該簇頭。

(4)調(diào)度機(jī)制的生成。簇頭節(jié)點(diǎn)產(chǎn)生TDMA定時(shí)消息，為簇中每個(gè)普通節(jié)點(diǎn)分配向其傳送數(shù)據(jù)的時(shí)間片。

2.1.2 穩(wěn)定的數(shù)據(jù)通信階段

該階段的主要任務(wù)是進(jìn)行數(shù)據(jù)的傳送。數(shù)據(jù)傳送采用TDMA[24-25]方式，每個(gè)節(jié)點(diǎn)按時(shí)間片將自己感知到的數(shù)據(jù)傳送給相應(yīng)的簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)經(jīng)過(guò)數(shù)據(jù)融合將數(shù)據(jù)傳送給更高級(jí)別的簇頭或者sink節(jié)點(diǎn)。穩(wěn)定階段持續(xù)一定時(shí)間后，傳感器網(wǎng)絡(luò)重新執(zhí)行簇的重構(gòu) ，并以此不斷循環(huán)，直到不滿足網(wǎng)絡(luò)性能要求為止。

2.2 LEACH-OE算法設(shè)計(jì)

由于LEACH算法的簇頭選舉具有隨機(jī)性，因此可能導(dǎo)致剩余能量過(guò)低的節(jié)點(diǎn)當(dāng)選為簇頭節(jié)點(diǎn)。為此，LEACH-OE算法引入能量因子對(duì)LEACH的閾值T(n)表達(dá)式進(jìn)行改進(jìn)。同時(shí)，分析可知每一輪中均會(huì)存在某些剩余能量較高的節(jié)點(diǎn)未參加簇頭選舉，則可通過(guò)自適應(yīng)閾值的方法將這些節(jié)點(diǎn)重新加入未當(dāng)選過(guò)簇頭的集合并參加簇頭選舉，從而充分利用節(jié)點(diǎn)的剩余能量。該算法可以降低條件不佳的節(jié)點(diǎn)成為簇頭的概率，減緩節(jié)點(diǎn)的死亡速度，平衡整個(gè)網(wǎng)絡(luò)的能量負(fù)載，避免部分節(jié)點(diǎn)過(guò)早死亡造成網(wǎng)絡(luò)癱瘓。這里，針對(duì)各研究要點(diǎn)，可給出探討分述如下。

2.2.1 能量因子

網(wǎng)絡(luò)初始階段，各節(jié)點(diǎn)能量相同，均為E0。隨著節(jié)點(diǎn)之間信號(hào)的傳輸，部分節(jié)點(diǎn)當(dāng)選為簇頭，其它節(jié)點(diǎn)成為普通節(jié)點(diǎn)。因?yàn)榇仡^節(jié)點(diǎn)消耗的能量遠(yuǎn)遠(yuǎn)大于普通節(jié)點(diǎn)，若某些節(jié)點(diǎn)頻繁當(dāng)選為簇頭，這些節(jié)點(diǎn)將因電量迅速下降而枯竭死亡，最終導(dǎo)致網(wǎng)絡(luò)部分癱瘓。因此，在進(jìn)行簇頭選舉時(shí)，必須將節(jié)點(diǎn)的剩余能量考慮在內(nèi)。定義節(jié)點(diǎn)的能量因子的數(shù)學(xué)公式如下：

(4)

其中，E(n)表示節(jié)點(diǎn)n的能量因子；Eresidual(n)表示該節(jié)點(diǎn)的剩余能量；Eave表示整個(gè)網(wǎng)絡(luò)所有節(jié)點(diǎn)的平均剩余能量?？梢钥闯觯Ｓ嗄芰吭降偷墓?jié)點(diǎn)其能量因子越小。

2.2.2 閾值的修正

在改進(jìn)算法中，針對(duì)每一輪選舉簇頭時(shí)節(jié)點(diǎn)n是否在前rmodp-1輪中當(dāng)選過(guò)簇頭，閾值T(n)被分為T1(n)和T2(n)兩類。對(duì)此可得剖析論述如下。

(1)若節(jié)點(diǎn)n在前rmodp-1輪中當(dāng)選過(guò)簇頭且滿足：

Eresidual(n)>Eave

(5)

則該節(jié)點(diǎn)再次參與簇頭選舉，相應(yīng)的閾值為：

[αE(n)+ωA]

(6)

其中，參數(shù)n、p、r、G和式(3)中相同，α、ω是小于1的影響因子，并且α+ω=1。通過(guò)仿真實(shí)驗(yàn)發(fā)現(xiàn)，取α= 0.8 -Eresidual(n) /E0，ω=0.2+Eresidual(n)/E0時(shí)效果較好，A= (r-rlast) modp-1，rlast表示節(jié)點(diǎn)n上一次成為簇頭的輪數(shù)，即A表示節(jié)點(diǎn)n從上次成為簇頭之后經(jīng)過(guò)的輪數(shù)。經(jīng)過(guò)的輪數(shù)越多，該節(jié)點(diǎn)成為普通節(jié)點(diǎn)的時(shí)間越長(zhǎng)，下一輪被選中的概率越大。

(2)若節(jié)點(diǎn)n在前rmodp-1輪中未當(dāng)選過(guò)簇頭，相應(yīng)的閾值為：

(7)

其中,參數(shù)n、p、r、G和式(3)中相同。

對(duì)于能量因子的影響因子α，隨著輪數(shù)的增加，節(jié)點(diǎn)的剩余能量越來(lái)越少。為了減緩節(jié)點(diǎn)的枯竭速度，均衡各個(gè)節(jié)點(diǎn)的負(fù)載，需要更加側(cè)重考慮剩余能量這一因素。因此，隨著傳輸輪數(shù)的增加，α逐漸增大，ω相對(duì)減小。各個(gè)因子的影響因子值總滿足和為1。LEACH-OE 算法針對(duì)不同的網(wǎng)絡(luò)負(fù)載情況自適應(yīng)地調(diào)節(jié)參數(shù)α和β的影響因子值，使修正后的閾值達(dá)到最優(yōu)。

2.2.3 算法流程

LEACH-OE算法對(duì)LEACH的簇頭選舉過(guò)程的研發(fā)改進(jìn)主要可歸納為如下2點(diǎn)，即：

(1)引入能量因子來(lái)修正簇頭選舉閾值。

(2)在未當(dāng)選過(guò)簇頭的節(jié)點(diǎn)進(jìn)行簇頭選舉之前，判斷前rmodp-1輪當(dāng)選過(guò)簇頭的節(jié)點(diǎn)能否再次成為簇頭。

其它過(guò)程與LEACH算法相同。這里，r表示當(dāng)前輪數(shù)，Node(n)表示節(jié)點(diǎn)n。LEACH-OE算法成簇階段的偽代碼設(shè)計(jì)表述詳見(jiàn)如下。

輸入：傳感器節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)銰n

輸出：分簇的傳感器節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)銰n′

ifNode(n)?G

ifEresidual(n) >Eavethen

G←Node(n)

由式(6)計(jì)算T1(n)并生成隨機(jī)數(shù)ξ1

ifξ1

Node(n)當(dāng)選為簇頭

end if

else

Node(n)退出簇頭選舉并成為普通簇頭

end else

end if

else

由式(7)計(jì)算T2(n)并生成隨機(jī)數(shù)ξ2

ifξ2

Node(n)當(dāng)選為簇頭

end if

else

Node(n)退出簇頭選舉并成為普通簇頭

end else

end if

3 實(shí)驗(yàn)仿真及分析

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

采用Matlab R2014b作為實(shí)驗(yàn)仿真平臺(tái)，將LEACH和LEACH-OE算法進(jìn)行仿真和性能對(duì)比分析。仿真參數(shù)設(shè)置見(jiàn)表1。

3.2 實(shí)驗(yàn)結(jié)果及分析

節(jié)點(diǎn)的分布情況如圖1所示，可以看出節(jié)點(diǎn)均勻分布在監(jiān)測(cè)區(qū)域內(nèi)。

隨著仿真輪數(shù)的增加，2種算法不同數(shù)量死亡節(jié)點(diǎn)對(duì)應(yīng)的輪數(shù)見(jiàn)表2。若以90%節(jié)點(diǎn)死亡的輪數(shù)作為衡量網(wǎng)絡(luò)性能的標(biāo)準(zhǔn)，LEACH-OE算法的網(wǎng)絡(luò)生命周期較LEACH算法提高了約13.12%。

表1 仿真參數(shù)

圖1 節(jié)點(diǎn)分布

算法種類輪數(shù)第一個(gè)節(jié)點(diǎn)50%節(jié)點(diǎn)90%節(jié)點(diǎn)LEACH347687983LEACH-OE3117461 112

圖2顯示了隨著仿真輪數(shù)的增加，2種算法在網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)的變化情況?？梢钥闯?，采用LEACH算法出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)的輪數(shù)在第347輪，而采用LEACH-OE算法雖然第一個(gè)節(jié)點(diǎn)死亡的時(shí)間比LEACH算法早，在第311輪，但是從LEACH-OE算法出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)的輪數(shù)到第1 200輪，在大部分時(shí)刻LEACH-OE算法存活節(jié)點(diǎn)的數(shù)量要高于原始的LEACH算法。

主要是由于LEACH沒(méi)有充分考慮到節(jié)點(diǎn)剩余能量的因素，有些節(jié)點(diǎn)自身能量過(guò)低，但在下一輪簇頭選舉時(shí)仍被選為簇頭，這樣會(huì)使節(jié)點(diǎn)剩余能量耗盡，加速該節(jié)點(diǎn)的死亡，甚至導(dǎo)致在節(jié)點(diǎn)未完成本輪通信時(shí)就提前死亡，降低網(wǎng)絡(luò)傳輸效率和網(wǎng)絡(luò)魯棒性。同時(shí)，LEACH-OE算法還考慮到某些剩余能量較高的節(jié)點(diǎn)能量未被充分利用的情況，使?jié)M足條件的節(jié)點(diǎn)重新參與簇頭選舉，充分利用了節(jié)點(diǎn)的剩余能量。因此，LEACH-OE算法減少了簇內(nèi)和簇間的網(wǎng)絡(luò)消耗，減緩了節(jié)點(diǎn)的死亡速度，均衡了全網(wǎng)節(jié)點(diǎn)的能量負(fù)載，同時(shí)相較其它算法能耗更低，有效延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生命周期。

圖2 存活節(jié)點(diǎn)數(shù)隨輪數(shù)的變化

4 結(jié)束語(yǔ)

針對(duì)LEACH算法的不足，本文提出一種考慮能量因子的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法。該算法采用新型簇頭選舉機(jī)制來(lái)均衡全網(wǎng)能量負(fù)載，并考慮到應(yīng)盡可能減小剩余能量較低的節(jié)點(diǎn)當(dāng)選簇頭的概率，引入能量因子來(lái)修正簇頭選舉閾值并且在因子前面賦上相應(yīng)系數(shù)，從而避免低能量的節(jié)點(diǎn)成為簇頭。此外，通過(guò)自適應(yīng)閾值的方法使部分剩余能量較高且已當(dāng)選過(guò)簇頭的節(jié)點(diǎn)重新參加簇頭選舉。實(shí)驗(yàn)證明，改進(jìn)算法相較其它算法能耗更低，有效避免了節(jié)點(diǎn)過(guò)早死亡，從而延長(zhǎng)了網(wǎng)絡(luò)的生命周期。下一步，擬將繼續(xù)研究大規(guī)模網(wǎng)絡(luò)下分簇路由算法的優(yōu)化問(wèn)題。