LEACH協(xié)議簇頭選擇算法的改進(jìn)與研究

章春華，陳宏偉

（湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢430068）

無(wú)線傳感器網(wǎng)絡(luò)（WSN），在一個(gè)區(qū)域內(nèi)布置無(wú)限個(gè)能量有限的傳感器節(jié)點(diǎn)，形成一個(gè)無(wú)線網(wǎng)絡(luò)且每個(gè)節(jié)點(diǎn)能夠自行采集區(qū)域中的信息，發(fā)送站基站節(jié)點(diǎn)對(duì)信息進(jìn)行處理.

由于無(wú)線傳感器自身的局限性［1］，如：1）節(jié)點(diǎn)的分布廣泛并且數(shù)目很多，每個(gè)節(jié)點(diǎn)想要維護(hù)整個(gè)網(wǎng)絡(luò)的信息是不可能的；2）節(jié)點(diǎn)基本上采用電池供電，能量有限且存儲(chǔ)空間有限；3）網(wǎng)絡(luò)節(jié)點(diǎn)如果消耗能量過(guò)大，則容易造成無(wú)效節(jié)點(diǎn)，從而導(dǎo)致網(wǎng)絡(luò)的部分癱瘓，無(wú)法有效傳遞信息.因此，傳統(tǒng)的有限網(wǎng)絡(luò)中的一些路由算法以及Ad Hoc網(wǎng)絡(luò)中常用的DSDV、AODV等路由算法由于沒(méi)有考慮到無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的局限性，并不適合自身局限性過(guò)多的傳感器網(wǎng)絡(luò).設(shè)計(jì)新的無(wú)線傳感器路由協(xié)議勢(shì)在必行.

隨著科技的不斷發(fā)展，大量新的路由協(xié)議被提出，平面路由協(xié)議和層次路由協(xié)議是現(xiàn)有的比較流行的兩類傳感器路由協(xié)議.

典型的平面路由協(xié)議［2］有：DD、SAR、SPIN 等，其優(yōu)點(diǎn)在于協(xié)議簡(jiǎn)單，所有節(jié)點(diǎn)的地位平等，具有良好的健壯性.平面路由的最大缺點(diǎn)是網(wǎng)絡(luò)中沒(méi)有管理節(jié)點(diǎn)，難以對(duì)通信的資源進(jìn)行優(yōu)化管理，同時(shí)節(jié)點(diǎn)協(xié)同工作的算法復(fù)雜，不利于網(wǎng)絡(luò)的動(dòng)態(tài)拓?fù)?

層次路由協(xié)議［3］，將傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)按照某種算法分成一些小的集合，每一個(gè)集合都有一個(gè)領(lǐng)導(dǎo)節(jié)點(diǎn)和多個(gè)非領(lǐng)導(dǎo)節(jié)點(diǎn)，領(lǐng)導(dǎo)節(jié)點(diǎn)不斷地收集非領(lǐng)導(dǎo)節(jié)點(diǎn)傳遞過(guò)來(lái)的信息并將信息傳遞給上一級(jí)的節(jié)點(diǎn)，層次路由協(xié)議也有很多不足，需要不斷改進(jìn)，使路由機(jī)制達(dá)到最大的利用率.

本文提出對(duì)經(jīng)典層次路由協(xié)議LEACH進(jìn)行進(jìn)一步的優(yōu)化，重點(diǎn)在對(duì)LEACH簇頭選擇算法的改進(jìn)，從而改進(jìn)整個(gè)無(wú)線網(wǎng)絡(luò)，提高網(wǎng)絡(luò)的生命周期和數(shù)據(jù)傳輸成功率.

1 Leach算法概述

LEACH （Low Energy Adaptive Cl ustering Hierarchy）是典型的分層分簇路由協(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在運(yùn)行的過(guò)程中不斷地循環(huán)執(zhí)行簇的重構(gòu)過(guò)程，每個(gè)簇重構(gòu)的過(guò)程可以用“輪”的概念來(lái)描述.每個(gè)輪可以分為兩個(gè)階段：簇的建立階段和傳輸數(shù)據(jù)的穩(wěn)定階段.簇的建立過(guò)程又分為4個(gè)階段：簇首節(jié)點(diǎn)的選擇、簇首節(jié)點(diǎn)的廣播、簇的建立和調(diào)度機(jī)制的生成［4］.

簇首節(jié)點(diǎn)具體的選擇辦法是：傳感器網(wǎng)絡(luò)會(huì)根據(jù)某些因素計(jì)算出一個(gè)閾值，那么當(dāng)每一輪選舉簇首節(jié)點(diǎn)的時(shí)候，每個(gè)傳感器節(jié)點(diǎn)會(huì)隨機(jī)在0～1之間選擇一個(gè)值，如果傳感器節(jié)點(diǎn)選擇的值小于閾值

那么這個(gè)節(jié)點(diǎn)會(huì)被選為簇首節(jié)點(diǎn).式（1）中，p是網(wǎng)絡(luò)中簇頭數(shù)和總節(jié)點(diǎn)數(shù)的百分比；r是當(dāng)前的選舉輪數(shù)；G是最近1／p不是簇頭的節(jié)點(diǎn)集.

選定簇首節(jié)點(diǎn)后，將簇首節(jié)點(diǎn)的信息廣播到整個(gè)網(wǎng)絡(luò).網(wǎng)絡(luò)中的其他節(jié)點(diǎn)根據(jù)接收信號(hào)強(qiáng)度來(lái)決定加入哪個(gè)簇，并通知相應(yīng)的簇首節(jié)點(diǎn)，完成了簇的建立.最后，簇首節(jié)點(diǎn)采用TDMA方式為簇中的每個(gè)節(jié)點(diǎn)分配向其傳輸數(shù)據(jù)的時(shí)間片.

數(shù)據(jù)的傳送是在穩(wěn)定階段開(kāi)始的.傳感器節(jié)點(diǎn)將數(shù)據(jù)傳送到簇首節(jié)點(diǎn)后，簇首節(jié)點(diǎn)對(duì)簇中所有節(jié)點(diǎn)所采集的數(shù)據(jù)進(jìn)行信息的融合，然后傳送給BS（基站）.

2 簇頭選擇算法的改進(jìn)

2.1 算法的提出

研究表明，簇頭節(jié)點(diǎn)的個(gè)數(shù)對(duì)網(wǎng)絡(luò)的生存周期和網(wǎng)絡(luò)的總體能耗有很大影響.原有的LEACH協(xié)議簇頭選擇算法依賴于傳感器節(jié)點(diǎn)所產(chǎn)生的隨機(jī)數(shù)，隨機(jī)數(shù)的不穩(wěn)定性導(dǎo)致傳感器節(jié)點(diǎn)數(shù)量和分布的區(qū)域位置都呈現(xiàn)極不穩(wěn)定的狀態(tài).計(jì)算出來(lái)的最優(yōu)簇頭數(shù)目Kopt是一個(gè)期望值，在現(xiàn)實(shí)的傳感器網(wǎng)絡(luò)環(huán)境中，簇頭的個(gè)數(shù)可能會(huì)遠(yuǎn)遠(yuǎn)偏離期望值Kopt，選出的簇頭個(gè)數(shù)過(guò)少時(shí)，分層分簇的概念就沒(méi)有了，簇首節(jié)點(diǎn)也會(huì)因?yàn)槟芎膯?wèn)題提前死亡，無(wú)法平衡整個(gè)網(wǎng)絡(luò)的能耗；反之，簇首數(shù)目過(guò)多，因?yàn)榇厥坠?jié)點(diǎn)要和基站進(jìn)行數(shù)據(jù)的傳輸，增大了網(wǎng)絡(luò)的節(jié)點(diǎn)的功耗.

從上面的分析可知：如何得到最優(yōu)的簇首數(shù)是協(xié)議的關(guān)鍵，其思想是在選擇最優(yōu)簇首的同時(shí)保證節(jié)點(diǎn)的能耗最小，并且，整個(gè)網(wǎng)絡(luò)的能量損耗均勻地分布在所有節(jié)點(diǎn)上.

本文將簇建立階段產(chǎn)生的能耗考慮到整個(gè)網(wǎng)絡(luò)的能耗中去，提出了一個(gè)新的最優(yōu)簇頭數(shù)目選擇算法KoptG.

2.2 算法的詳細(xì)描述

2.2.1 最優(yōu)簇頭數(shù)推導(dǎo) 有N個(gè)節(jié)點(diǎn)分布在M×M的區(qū)域內(nèi)，假設(shè)最優(yōu)的簇頭數(shù)目為K，代表傳感器節(jié)點(diǎn)被劃為K個(gè)簇，每個(gè)簇內(nèi)有N／K個(gè)節(jié)點(diǎn)，其中，N／K－1個(gè)非簇首節(jié)點(diǎn)，一個(gè)簇頭節(jié)點(diǎn)，傳感器網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都有相同的處理能力和通信能力，且每個(gè)節(jié)點(diǎn)的發(fā)射功率是可控制的，節(jié)點(diǎn)每次傳送1 bit的數(shù)據(jù).

在筆者提出的最優(yōu)簇首數(shù)目算法中，整個(gè)網(wǎng)絡(luò)的能耗分為兩個(gè)部分.

第一部分：選擇階段的能耗

簇頭節(jié)點(diǎn)的能耗

式（2）中，第一個(gè)大括號(hào)表示簇頭節(jié)點(diǎn)傳送廣播信息的能耗；第二部分是同一個(gè)簇內(nèi)節(jié)點(diǎn)接收數(shù)據(jù)的能耗；第三部分是簇首節(jié)點(diǎn)告知非簇首節(jié)點(diǎn)TDMA和CDMA消息的能耗.

非簇首節(jié)點(diǎn)的能耗式（3）中，第一部分是接收簇首廣播信息消耗的能耗；第二部分是相應(yīng)的簇首節(jié)點(diǎn)，傳輸消息的能耗；第三部分是接收簇首節(jié)點(diǎn)確認(rèn)消息的能耗.

第二部分：數(shù)據(jù)的傳送階段.

在數(shù)據(jù)的傳輸階段，一個(gè)簇頭節(jié)點(diǎn)的能耗

非簇首節(jié)點(diǎn)將數(shù)據(jù)傳送到簇首節(jié)點(diǎn)的能耗

因此，在一個(gè)簇內(nèi)消耗的能耗

式中，第一部分是簇頭選擇消耗的能耗；第二部分是數(shù)據(jù)傳送消耗的能耗.

那么，K個(gè)簇消耗的總能耗為：將式（5）代入式（6）中，并對(duì) K求導(dǎo)，即得最優(yōu)簇頭數(shù)目

2.2.2 LEACHG算法思想 通過(guò)以上的推導(dǎo)，得到最優(yōu)的簇頭數(shù)，下一步提出新的簇首選擇算法LEACHG.思想是：利用距離關(guān)系將所有節(jié)點(diǎn)群組化，使得群組的數(shù)量和算法中期望的簇頭個(gè)數(shù)相同，這樣導(dǎo)致簇頭的實(shí)際個(gè)數(shù)與期望的簇頭個(gè)數(shù)相同.

無(wú)線傳感器網(wǎng)絡(luò)區(qū)域內(nèi)的節(jié)點(diǎn)按下面的步驟被分為組，且成組的個(gè)數(shù)與最優(yōu)簇頭的個(gè)數(shù)相同，具體的實(shí)現(xiàn)方法（圖1）如下：

圖1 成組算法流程圖

1）根據(jù)最優(yōu)簇頭個(gè)數(shù)Kopt，決定成組的個(gè)數(shù)k；

2）基站（BS）廣播一條很短的信息包；

3）網(wǎng)絡(luò)中的節(jié)點(diǎn)一旦接受到基站發(fā)送來(lái)的信息，就將自己的當(dāng)前信息，如位置和節(jié)點(diǎn)的ID號(hào)，回送給基站；

4）根據(jù)節(jié)點(diǎn)信息回送給基站的時(shí)間片，基站選擇一個(gè)信息返回時(shí)間最長(zhǎng)的節(jié)點(diǎn)作為組頭（Group Head），然后基站將組頭的ID號(hào)，組內(nèi)的成員個(gè)數(shù)發(fā)送給網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)；

5）組頭節(jié)點(diǎn)再發(fā)送一個(gè)短信息包給WSN；

6）當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)收到短信息后，反饋?zhàn)约旱墓?jié)點(diǎn)信息；

7）組頭節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)反饋信息時(shí)間片的長(zhǎng)短，選取時(shí)間片最快的－1個(gè)節(jié)點(diǎn)作為自己的組內(nèi)成員，同時(shí)組節(jié)點(diǎn)再發(fā)送一個(gè)信息包括組ID以及組內(nèi)節(jié)點(diǎn)的ID號(hào)給WSN，一旦一個(gè)節(jié)點(diǎn)加入到組內(nèi)，這個(gè)節(jié)點(diǎn)就不能再加入別的組內(nèi)；

8）組頭（GH）節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)反饋的信息，選擇一個(gè)反饋時(shí)間片最長(zhǎng)的節(jié)點(diǎn)作為下一個(gè)組頭節(jié)點(diǎn)，同樣發(fā)送組頭ID和組ID號(hào)給WSN.

重復(fù)5－8階段，直到組的個(gè)數(shù)與Kopt相等.

當(dāng)達(dá)到與Kopt相等的組的個(gè)數(shù)后，各個(gè)組內(nèi)的成員就根據(jù)相應(yīng)的簇頭選擇算法選出簇頭，然后進(jìn)入數(shù)據(jù)的傳輸穩(wěn)定階段.

3 仿真結(jié)果與分析

本文的仿真基于NS2仿真平臺(tái).首先，設(shè)置相關(guān)的實(shí)驗(yàn)環(huán)境進(jìn)行仿真，得到有用的leach.energy和leach.alive文件，leach.alive和leach.ener gy文件詳細(xì)記錄了仿真的過(guò)程以及每一節(jié)點(diǎn)的死亡、存活，節(jié)點(diǎn)能耗；然后，用提供的awk語(yǔ)言編寫(xiě)提取leach.alive和leach.energy文件信息數(shù)據(jù)的腳本文件；最后，利用NS自帶的畫(huà)圖軟件gnuplot生成圖表，對(duì)生成的圖表進(jìn)行分析，比較改進(jìn)后的LEACH協(xié)議.

仿真的過(guò)程中，為了更準(zhǔn)確地比較提出算法的優(yōu)劣，采用完全相同的參數(shù)和節(jié)點(diǎn)分布文件同時(shí)模擬LEACH、LEACHG協(xié)議，本仿真采用的網(wǎng)絡(luò)模型是一個(gè)在100 m×100 m的區(qū)域內(nèi)隨機(jī)地分布100個(gè)WSN節(jié)點(diǎn)，其部分實(shí)驗(yàn)參數(shù)設(shè)置：節(jié)點(diǎn)數(shù)，100；節(jié)點(diǎn)初始能量，2 J；仿真區(qū)域，100 m×100 m；信道帶寬，1 Mb／s；發(fā)送／接收1bit能耗，50 nJ／bit；傳輸放大器能耗，10 pj／bit／m2；數(shù)據(jù)融合能耗，50 nJbit／signal；數(shù)據(jù)包大小，100 bytes.

圖2 網(wǎng)絡(luò)生存周期

圖2顯示了兩種協(xié)議的網(wǎng)絡(luò)生存周期.從圖中的數(shù)據(jù)可以看出，第一個(gè)節(jié)點(diǎn)死亡時(shí)間LEACHG要晚于LEACH協(xié)議，當(dāng)全部節(jié)點(diǎn)死亡時(shí)，LEACHG比LEACH多運(yùn)行了幾輪.新的LEACHG協(xié)議將簇首階段的能耗考慮進(jìn)去，并通過(guò)成組算法得出了最優(yōu)的簇首數(shù)，導(dǎo)致傳感器節(jié)點(diǎn)的能耗能更加均勻地分布到所有的節(jié)點(diǎn)中去，避免了單個(gè)節(jié)點(diǎn)因?yàn)槟芰康南倪^(guò)大而過(guò)早地死亡，從而影響了網(wǎng)絡(luò)的生存周期.本實(shí)驗(yàn)只設(shè)置了100個(gè)節(jié)點(diǎn)，當(dāng)傳感器節(jié)點(diǎn)更多，WSN的規(guī)模更大時(shí)，LEACHG的效果會(huì)更佳.

4 結(jié)論

本文將簇首選舉階段的能耗計(jì)算到整個(gè)網(wǎng)絡(luò)的能耗中去，得出了最優(yōu)簇首個(gè)數(shù)的計(jì)算公式，而后提出了成組的簇首選擇算法LEACHG，并在NS2仿真工具上進(jìn)行了仿真.分析的結(jié)果表明，相比于原來(lái)的LEACH協(xié)議，LEACHG能夠有效地平衡網(wǎng)絡(luò)中的能耗，提高整個(gè)網(wǎng)絡(luò)的生存周期.

［1］Al Karaki J N，Kamal A E.Routing techniques in wireless sensor networks［J］.IEEE Wireless Communications，2004，11（6）：6－28.

［2］Mhatre V，Rosenber g C.Design guidelines for wireless sensor networks：communication，clustering and aggregation［J］.Ad Hoe：Networ ks，2004，2（1）：45－63.

［3］Heinzel man W R，Chandrakasan A，Balakrishnan H.An applicationspecific protocol for wireless microsensor networks［J］.IEEE Transactions on Wireless Communication，2002，1（4）：660－670.

［4］Wendi B，Heinzel man W R，Balakrishnan H.An application specificpr otocol architecture for wireless micr osensor networ ks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660－670.

［5］Jan F，Akyildiz，Weilian S，etal.Asuivey on r outing protocols for wireless sensor networks［J］.IEEE Communicaitons Magazine，2004，40（8）：102－114.

［6］Li Qing，Zhu Qingxin，Wang Mingwen.Design of distribute denergy efficient clustering algorithm for wirelesssensor networ ks［J］.Co mputer communication，2006（29）：2 230－2 237.