基于能量的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)分簇路由算法

（蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院， 蘭州 730050）



摘 要：

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)存在嚴(yán)重的能量約束問(wèn)題，網(wǎng)絡(luò)協(xié)議的首要設(shè)計(jì)目標(biāo)就是要高效地使用傳感器節(jié)點(diǎn)的能量，延長(zhǎng)網(wǎng)絡(luò)的存活時(shí)間。在分析經(jīng)典的分簇路由協(xié)議LEACH的基礎(chǔ)上，針對(duì)其不足提出了基于能量的改進(jìn)算法和分簇規(guī)模約束機(jī)制平衡節(jié)點(diǎn)能量消耗。仿真實(shí)驗(yàn)表明，改進(jìn)算法有效地延長(zhǎng)了網(wǎng)絡(luò)生存周期。

關(guān)鍵詞：無(wú)線(xiàn)傳感器網(wǎng)絡(luò)； 路由算法；能量有效

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)02-0674-03



Clustered routing agorithm based on energy for wireless sensor networks



ZHANG Qiu-yu ， PENG Duo， LIU Hong-guo

(School of Computer Communication， Lanzhou University of Technology， Lanzhou 730050， China)



Abstract:On the basis of understanding of routing protocol——low energy adaptive clustering hierarchy (LEACH)， this paper analyzed it’s shortcoming and improvement. The new algorithm balancedenergy depletionof node by two methods. One was considering the energy of nodes when selecting cluster heads another was limited number of nodes in each cluster. Simulation results show that the effectiveness of the improved algorithm and prove the improved algorithm is much better than LEACH in energy consumption and lifetimeof network.

Key words：wireless sensor network(WSN); routing algorithm ; energy efficient



0 引言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSN)是一種由大量微小的集成(包括傳感器件、數(shù)據(jù)處理單元和無(wú)線(xiàn)通信模塊)的節(jié)點(diǎn)組成的以數(shù)據(jù)為中心的無(wú)線(xiàn)自組織網(wǎng)絡(luò)。WSN在社會(huì)生活各個(gè)領(lǐng)域具有十分重要的科研價(jià)值和巨大的實(shí)用價(jià)值。2001年1月，《MIT技術(shù)評(píng)論》將WSN列于十種改變未來(lái)世界新興技術(shù)之首[1，2]。在我國(guó)，2006年初發(fā)布的《國(guó)家中長(zhǎng)期科學(xué)與技術(shù)發(fā)展規(guī)劃綱要》為信息技術(shù)確定了三個(gè)前沿方向，其中兩個(gè)與WSN的研究直接相關(guān)，即智能感知技術(shù)和自組織網(wǎng)絡(luò)技術(shù)。

作為一種典型的普適計(jì)算(pervasive computing)應(yīng)用，WSN通過(guò)大量部署在監(jiān)測(cè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)，采集監(jiān)測(cè)者所關(guān)注的信息，通過(guò)無(wú)線(xiàn)方式，將收集并簡(jiǎn)單處理后的信息發(fā)送到目標(biāo)用戶(hù)。由于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)通常部署在人無(wú)法接近或者高危險(xiǎn)區(qū)域且數(shù)量眾多，這使得隨時(shí)更換節(jié)點(diǎn)能源變得非常困難。節(jié)點(diǎn)通常攜帶一次性電池供電，因此傳感器網(wǎng)絡(luò)存在嚴(yán)重的能量約束問(wèn)題。所以，傳感器網(wǎng)絡(luò)協(xié)議的首要設(shè)計(jì)目標(biāo)就是要高效地使用傳感器節(jié)點(diǎn)的能量，延長(zhǎng)整個(gè)網(wǎng)絡(luò)的存活時(shí)間。

本文首先介紹無(wú)線(xiàn)傳感器網(wǎng)絡(luò)路由協(xié)議及其分類(lèi)，在分析經(jīng)典的分簇路由協(xié)議LEACH的基礎(chǔ)上，針對(duì)其不足提出改進(jìn)算法，并通過(guò)仿真證明本文提出的改進(jìn)算法的有效性，最后是全文總結(jié)。

1 路由協(xié)議及其分類(lèi)

從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的角度可以把無(wú)線(xiàn)傳感器網(wǎng)絡(luò)路由協(xié)議分為平面路由協(xié)議和分簇(clustering) 路由協(xié)議兩類(lèi)。在平面路由協(xié)議中，所有網(wǎng)絡(luò)節(jié)點(diǎn)的地位是平等的，不存在等級(jí)和層次差異，通過(guò)相互之間的局部操作和信息反饋來(lái)生成路由。典型的平面路由算法有定向擴(kuò)散(directed diffusion)協(xié)議[3]、SAR(sequential assignment routing)[4]、SPIN(sensor protocols for information via negotiation)[5]、Romor Routing[6]等。平面路由的最大缺點(diǎn)在于：網(wǎng)絡(luò)中無(wú)管理節(jié)點(diǎn)；缺乏對(duì)通信資源的優(yōu)化管理；自組織協(xié)同工作算法復(fù)雜；對(duì)網(wǎng)絡(luò)動(dòng)態(tài)變化的反應(yīng)速度較慢等[7]。

將傳感器節(jié)點(diǎn)組織成簇的形式可以有效地減少網(wǎng)絡(luò)的能量消耗。在分簇的拓?fù)涔芾頇C(jī)制下，網(wǎng)絡(luò)中的節(jié)點(diǎn)可以劃分為簇頭節(jié)點(diǎn)(cluster head)和成員節(jié)點(diǎn)兩類(lèi)。在每個(gè)簇內(nèi)，根據(jù)一定的機(jī)制算法選取某個(gè)節(jié)點(diǎn)作為簇頭，用于管理或控制整個(gè)簇內(nèi)成員節(jié)點(diǎn)，協(xié)調(diào)成員節(jié)點(diǎn)之間的工作，負(fù)責(zé)簇內(nèi)信息的收集和數(shù)據(jù)的融合處理以及簇間轉(zhuǎn)發(fā)[8]。

LEACH(low-energy adaptive clustering hierarchy)[9]是WSN中最早提出的分簇路由協(xié)議。其成簇思想貫穿于之后提出的很多分簇路由協(xié)議中。LEACH采用所有節(jié)點(diǎn)輪流擔(dān)任簇頭節(jié)點(diǎn)的方法來(lái)達(dá)到使所有節(jié)點(diǎn)均勻消耗能量的目的，它也是第一個(gè)提出數(shù)據(jù)聚合的分簇路由協(xié)議。

2 LEACH協(xié)議及其存在的問(wèn)題

2. 1 LEACH協(xié)議分析

LEACH是按照循環(huán)方式構(gòu)建的。每一循環(huán)稱(chēng)之為一輪（round）。每一輪被進(jìn)一步劃分為建立階段和穩(wěn)態(tài)階段。建立階段（setup phase）開(kāi)始于節(jié)點(diǎn)自選舉為簇頭的過(guò)程，各節(jié)點(diǎn)獨(dú)立地按照一定概率決定自己是否做簇頭。選舉方法是：每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0～1的隨機(jī)數(shù)，如果這個(gè)數(shù)小于閾值T(n)，則該節(jié)點(diǎn)向周?chē)?jié)點(diǎn)廣播它是簇頭的消息。T(n)的計(jì)算公式為

T(n)=p/{1-p×[r mod(1/p)]} n=G

0other(1)

其中:P是簇頭占所有節(jié)點(diǎn)的百分比，即節(jié)點(diǎn)當(dāng)選簇頭的概率；r是目前循環(huán)進(jìn)行的輪數(shù)；G是最近1/P 輪中還未當(dāng)選過(guò)簇頭的節(jié)點(diǎn)集合。從T(n)可以看出，當(dāng)選過(guò)簇頭的節(jié)點(diǎn)在接下來(lái)的1/P 輪循環(huán)中將不能成為簇頭，剩余節(jié)點(diǎn)當(dāng)選簇頭的閾值T(n)增大，節(jié)點(diǎn)產(chǎn)生小于T(n)的隨機(jī)數(shù)的概率隨之增大，所以節(jié)點(diǎn)當(dāng)選簇頭的概率增大。

在后續(xù)的廣告階段（advertisement phase），簇頭用一個(gè)廣告消息發(fā)送給鄰居節(jié)點(diǎn)。簇頭使用CSMA協(xié)議與隱終端爭(zhēng)用媒體。在分簇建立階段，節(jié)點(diǎn)通過(guò)檢測(cè)收到信號(hào)的強(qiáng)弱來(lái)決定加入哪個(gè)分簇，之后簇頭了解成員的數(shù)量及其標(biāo)志，并建立一個(gè)TDMA時(shí)間表，隨機(jī)地拾取一個(gè)CDMA碼，并將該信息在廣播時(shí)間表的子階段進(jìn)行廣播，每個(gè)節(jié)點(diǎn)只在自己的時(shí)間片內(nèi)進(jìn)行數(shù)據(jù)傳輸。簇建立之后， TDMA穩(wěn)態(tài)階段開(kāi)始，簇頭將節(jié)點(diǎn)收集的信息傳送到收集點(diǎn)（sink）節(jié)點(diǎn)，直到本輪結(jié)束。其組織結(jié)構(gòu)如圖1所示。

2. 2 LEACH協(xié)議存在的問(wèn)題

LEACH協(xié)議中，簇頭是周期性按輪隨機(jī)選舉的，這保證了網(wǎng)絡(luò)各節(jié)點(diǎn)有平等的機(jī)會(huì)成為簇頭，平衡了節(jié)點(diǎn)的能耗。但這是一個(gè)理想化的結(jié)果，必須滿(mǎn)足兩個(gè)前提條件: a)每個(gè)節(jié)點(diǎn)初始能量均等;b)每個(gè)節(jié)點(diǎn)在擔(dān)任簇頭期間耗費(fèi)的能量均等。實(shí)際上，由于每個(gè)簇的大小以及簇頭到基站的距離都不一樣，條件b)很難達(dá)到，這就使得有些節(jié)點(diǎn)的能量消耗較快，有些節(jié)點(diǎn)的能量消耗較慢，經(jīng)過(guò)一段時(shí)間后，有些節(jié)點(diǎn)能量較少但卻被選舉為簇頭，

這就加速了節(jié)點(diǎn)的死亡，大大減少了網(wǎng)絡(luò)生存周期。其次，在LEACH協(xié)議中，由于簇首選舉的隨機(jī)性使得網(wǎng)絡(luò)的簇首需要負(fù)擔(dān)的節(jié)點(diǎn)數(shù)不同，加重了個(gè)別簇首節(jié)點(diǎn)的負(fù)擔(dān)，使得簇間負(fù)載不均衡，整個(gè)網(wǎng)絡(luò)的負(fù)載平衡程度下降，而在網(wǎng)絡(luò)規(guī)模較大時(shí)簇頭之間必須采用多跳方式將數(shù)據(jù)傳送到sink節(jié)點(diǎn)，這就使得靠近sink節(jié)點(diǎn)的簇頭因?yàn)槌袚?dān)了更多的轉(zhuǎn)發(fā)任務(wù)，能量消耗較快，影響了網(wǎng)絡(luò)的生存周期。

3 改進(jìn)后的路由協(xié)議

基于LEACH協(xié)議中存在的問(wèn)題，本文在兩個(gè)方面對(duì)它進(jìn)行了改進(jìn)。改進(jìn)算法仍使用LEACH協(xié)議的網(wǎng)絡(luò)模型。

首先，在簇頭選舉階段，對(duì)候選簇頭增加考慮能量因素，改進(jìn)了T(n)的計(jì)算方法。 

T(n)=p/{1-p×[r mod(1/p)]}×Ecurrent/E0n=G

0other(2)

其中：Ecurrent 表示節(jié)點(diǎn)的當(dāng)前能量；E0 表示節(jié)點(diǎn)的初始能量。式(2)的改進(jìn)使能量消耗比較低的節(jié)點(diǎn)比能量消耗高的節(jié)點(diǎn)優(yōu)先當(dāng)選簇頭，平衡了節(jié)點(diǎn)間的能量消耗，從而可以延長(zhǎng)網(wǎng)絡(luò)的生存周期。此改進(jìn)還考慮到能量因素對(duì)T(n)的影響程度，使得節(jié)點(diǎn)能量都較多時(shí)，能量因素的影響相對(duì)較大；當(dāng)節(jié)點(diǎn)能量普遍較少時(shí)，能量因素的影響相對(duì)較小。改善了當(dāng)網(wǎng)絡(luò)運(yùn)行較長(zhǎng)時(shí)間后，所有節(jié)點(diǎn)的當(dāng)前能量Ecurrent都變得很低，使得閾值T(n)變小，所有節(jié)點(diǎn)成為簇頭的概率都降低，每輪當(dāng)選的簇頭數(shù)量減少，最終導(dǎo)致網(wǎng)絡(luò)能量耗費(fèi)不均衡的問(wèn)題。

其次，基于協(xié)議中存在的簇間負(fù)載不均衡的問(wèn)題，提出了一種分簇規(guī)模約束機(jī)制，即在簇的形成過(guò)程中，設(shè)置簇內(nèi)節(jié)點(diǎn)數(shù)目的最大值Nmax和最小值Nmin，控制簇的規(guī)模，保持簇間負(fù)載均衡。

具體過(guò)程為：在網(wǎng)絡(luò)初始階段，匯聚點(diǎn)需要用一個(gè)較大的發(fā)送功率向所有節(jié)點(diǎn)廣播一個(gè)信號(hào)。 每個(gè)傳感器節(jié)點(diǎn)在收到此信號(hào)后，根據(jù)接收信號(hào)的強(qiáng)度計(jì)算它到匯聚點(diǎn)的近似距離（RSSI)，記這個(gè)距離為D(i)-sink。一旦第i個(gè)節(jié)點(diǎn)當(dāng)選為簇頭節(jié)點(diǎn)，其簇內(nèi)節(jié)點(diǎn)的數(shù)目為

N=[q+（D(i)-sink-Dmin）/（Dmax-Dmin)](1/p-1)(3)

其中：Dmax和Dmin分別代表網(wǎng)絡(luò)中的節(jié)點(diǎn)到sink節(jié)點(diǎn)距離的最大值和最小值；D(i)-sink 代表節(jié)點(diǎn)i到匯聚點(diǎn)的距離；q是一個(gè)加權(quán)因子。簇內(nèi)節(jié)點(diǎn)數(shù)目的最大值Nmax和最小值Nmin由q決定，本文取q= 1/2，此時(shí): 

Nmax=3/2(1/p-1)(4)

Nmin=1/2(1/p-1)(5)

從式（3）可以看出，簇內(nèi)節(jié)點(diǎn)數(shù)目與節(jié)點(diǎn)到sink點(diǎn)的距離呈線(xiàn)性遞減關(guān)系。簇頭按照信號(hào)強(qiáng)度決定接受哪些節(jié)點(diǎn)為其成員節(jié)點(diǎn)。當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)目超過(guò)規(guī)定值后，簇頭就不再接納新節(jié)點(diǎn)。這就使得靠近匯聚點(diǎn)的簇規(guī)模小，數(shù)量多，遠(yuǎn)離匯聚點(diǎn)的簇規(guī)模大，數(shù)量少，達(dá)到控制簇的規(guī)模，保持簇間負(fù)載均衡的目的。改進(jìn)的算法流程如圖2所示。

4 仿真及其分析

4. 1 能量模型及仿真環(huán)境

本文用NS2軟件對(duì)改進(jìn)算法與LEACH算法進(jìn)行了仿真比較。主要從簇頭節(jié)點(diǎn)的能耗和網(wǎng)絡(luò)生存時(shí)間兩個(gè)方面進(jìn)行了比較，以此來(lái)評(píng)價(jià)改進(jìn)后的性能。為了加以區(qū)別，將改進(jìn)后的算法記為L(zhǎng)EACH_E。在這里將網(wǎng)絡(luò)生命周期定義為出現(xiàn)第一個(gè)因能量耗盡而失效的節(jié)點(diǎn)所需的時(shí)間（first node dies， FND）。節(jié)點(diǎn)采用與文獻(xiàn)[10]相同的無(wú)線(xiàn)通信能量消耗模型，節(jié)點(diǎn)發(fā)射1 bit的數(shù)據(jù)消耗的能量主要分為發(fā)射電路損耗和功率放大損耗兩部分，即

ETx(1，d)=lEelec+lεfsd2，d＜d0

lEelec+lεmpd4，d≥d0(6) 

其中:Eelec表示發(fā)射電路損耗的能量；εfs 、εmp 分別為這兩種模型中功率放大所需的能量；d為兩節(jié)點(diǎn)間距離 。當(dāng)傳輸距離小于閾值do ，功率放大損耗采用自由空間模型，能量消耗與d 2成正比；當(dāng)傳輸距離大于等于閾值do 時(shí)， 采用多路徑衰減模型，能量消耗與d 4成正比。節(jié)點(diǎn)接收1 bit的數(shù)據(jù)消耗能量為

ERx(l)=lEelec (7)

這里假設(shè)簇頭節(jié)點(diǎn)有理想的數(shù)據(jù)融合，即分別接收n個(gè)簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)l，融合后為1 bit。簇頭節(jié)點(diǎn)在作為中繼節(jié)點(diǎn)時(shí)，首先接收數(shù)據(jù)然后再轉(zhuǎn)發(fā)出去。能耗就由兩部分組成：

Ehead(d)=lERx+lETx+lEelecn+lεmpd2=

(n+1)lEelec+2lεmpd2(8) 

在仿真中使用了以下參數(shù)。網(wǎng)絡(luò)大小為150 m×150 m，隨機(jī)生成100個(gè)傳感器節(jié)點(diǎn)，如圖3所示，sink節(jié)點(diǎn)位于坐標(biāo)(150 ，0)處。Eelec為50 nJ/bit ，εfs為10 pJ/bit/m2，εmp為0.001 3 pJ/bit/m4， l為4 000 bit ，do為75 m。

4. 2 仿真結(jié)果

分別比較節(jié)點(diǎn)初始能量為0.25、0.5、1 J的情況下，改進(jìn)算法與LEACH 協(xié)議的網(wǎng)絡(luò)生命周期，如圖4所示。從圖中可以看出，改進(jìn)算法比LEACH算法在不同初始能量下，網(wǎng)絡(luò)運(yùn)行的輪數(shù)分別延長(zhǎng)26%、24%、32%，明顯延長(zhǎng)了網(wǎng)絡(luò)生命周期。圖5顯示某一相同規(guī)模簇的簇頭節(jié)點(diǎn)的能耗。從圖中可以看出，改進(jìn)算法的簇頭能耗相對(duì)較低，也就是說(shuō)，采用分簇規(guī)模約束機(jī)制和簇間轉(zhuǎn)發(fā)方式可有效地節(jié)約簇頭能量，平衡簇間負(fù)載。 

5 結(jié)束語(yǔ)

本文在分析經(jīng)典的分簇路由協(xié)議LEACH的基礎(chǔ)上，針對(duì)其不足提出在簇頭選舉中增加考慮節(jié)點(diǎn)當(dāng)前能量的因素來(lái)解決部分能量少的節(jié)點(diǎn)當(dāng)選簇頭的問(wèn)題，使得能量大的節(jié)點(diǎn)成為簇頭的概率相對(duì)更大，有效地延長(zhǎng)了節(jié)點(diǎn)存活時(shí)間。同時(shí)采用分簇規(guī)模約束機(jī)制改善了簇頭之間的負(fù)載不均衡問(wèn)題。仿真實(shí)驗(yàn)表明，以上措施有效地平衡了節(jié)點(diǎn)能量消耗，延長(zhǎng)了網(wǎng)絡(luò)生存周期。

參考文獻(xiàn)：

[1]AKYILDIZI F， SUWei-lian， SANKARASUBRAMANIAMY， et al. A survey on sensor network[J]. IEEE Communications Magazine， 2002，40(8):102-114.

[2]RENFeng-yuan， HUANGHai-ning， LINChuang. Wireless sensor networks[J]. Journal of Software， 2003， 4(7):1282-1291.

[3]INTANAGONWIWATC， GOVINDANR， ESTRIND. Directed diffusion: a scalable and robust communication paradigm for sensor networks[C]//Proc of the 6th Annual ACM/IEEE International Confe-rence on MobiCom’00. Boston，MA:[s.n.]，2000.

[4]SHAH R C， RABAEY J. Energy aware routing for low energy Ad hoc sensor networks[C]//Proc of IEEE Wireless Communications and Networking Conference. 2002.

[5]KULIK J， HEINZELMAN W R， BALAKRISHNAN H. Negotiation based protocols for disseminating information in wireless sensor networks[J]. Wireless Networks， 2002，8(2-3):169-185.

[6]BRAGINSKY D， ESTRIN D. Rumor routing algorithm for sensor networks[C]//Proc of the 1st Workshop on Sensor Networks and Applications. 2002. 

[7]SHEN Bo， ZHANG Shi-yong， ZHONG Yi-ping. Cluster-based routing protocols for wireless sensor networks[J]. Journal of Software， 2006，17(7):1588-1600.

[8]孫利民，李建中，陳渝，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社， 2005.

[9]HEINZELMAN W，CHANDRAKASAN A， BALAKRISHNANH.Energy-efficient communication protocol for wireless microsensornetworks[C]//Proc of the 33rd Annual Hawaii Int’l Conf on System Sciences. Maui: IEEE Computer Society， 2000:3005-3014.

[10]HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communications ，2002，1(4):660-670.