基于非均勻分簇的無線傳感器網(wǎng)絡(luò)多跳路由算法

林 仁，夏方禮，王 扉(湖南城市學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，湖南 益陽 413000)

基于非均勻分簇的無線傳感器網(wǎng)絡(luò)多跳路由算法

林 仁，夏方禮，王 扉
(湖南城市學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，湖南 益陽 413000)

針對(duì)低功耗自適應(yīng)分簇(LEACH)路由協(xié)議中均勻分簇方式和簇頭選擇的不合理以及遠(yuǎn)距離數(shù)據(jù)傳輸過程中能量消耗過多的問題，提出了一種基于非均勻分簇的多跳路由算法LEACH-MRUC．在分簇過程中，該算法充分考慮了節(jié)點(diǎn)的能量及地理位置，同時(shí)采用非均勻分簇方式構(gòu)建規(guī)模不同的簇結(jié)構(gòu)；在數(shù)據(jù)傳輸過程中，簇頭與基站之間采用單跳和多跳相結(jié)合的路由方式來進(jìn)行通信．仿真結(jié)果表明，LEACH-MRUC算法既使得網(wǎng)絡(luò)的能量消耗有效地得到均衡，又使得能量的利用效率得到顯著提高，并且顯著延長(zhǎng)了網(wǎng)絡(luò)的壽命．

負(fù)載均衡；非均勻分簇；無線傳感器網(wǎng)絡(luò)；能量高效

1 概述

無線傳感器網(wǎng)絡(luò)是大量微小傳感器節(jié)點(diǎn)組成的自組織(Ad-hoc)網(wǎng)絡(luò)系統(tǒng)，這些微小傳感器部署在監(jiān)測(cè)區(qū)域內(nèi)，其目的就是協(xié)助感知、采集和處理監(jiān)測(cè)區(qū)域內(nèi)感知對(duì)象的有效信息，并最終將其發(fā)送給觀測(cè)者[1]．無線傳感器網(wǎng)絡(luò)很好的將網(wǎng)絡(luò)世界、客觀的物質(zhì)世界以及人類社會(huì)有機(jī)的結(jié)合在一起，它無需固定網(wǎng)絡(luò)設(shè)施的支持，具有快速展開、抗毀性強(qiáng)等特點(diǎn)，可廣泛應(yīng)用于軍事偵察、環(huán)境監(jiān)測(cè)、醫(yī)療護(hù)理以及空間探索等領(lǐng)域[2-3]．由于傳感器節(jié)點(diǎn)通常被隨機(jī)部署在無人值守的區(qū)域且一般采用電池供電，因此，研究高效、負(fù)載均衡的路由協(xié)議對(duì)無線傳感器網(wǎng)絡(luò)意義重大．

目前，研究者們已提出了各種路由協(xié)議．一般從網(wǎng)絡(luò)的邏輯結(jié)構(gòu)來看，可以分為層次路由協(xié)議和平面路由協(xié)議兩種.所有傳感器節(jié)點(diǎn)在平面路由協(xié)議中地位平等且缺乏中心控制節(jié)點(diǎn)．因此，網(wǎng)絡(luò)的可擴(kuò)展性以及對(duì)資源的優(yōu)化管理能力較弱，對(duì)動(dòng)態(tài)變化網(wǎng)絡(luò)的反應(yīng)速度也相對(duì)較慢；層次路由協(xié)議則通過將網(wǎng)絡(luò)劃分為多個(gè)規(guī)模較小的簇，由簇頭節(jié)點(diǎn)來實(shí)現(xiàn)局部范圍內(nèi)簇內(nèi)成員的管理，從而實(shí)現(xiàn)節(jié)點(diǎn)之間的協(xié)同工作．層次路由協(xié)議的出現(xiàn)在很大程度上解決了平面路由協(xié)議中存在的一些問題，它也是當(dāng)前路由協(xié)議研究的主流[4]．

LEACH[5]協(xié)議是無線傳感器網(wǎng)絡(luò)中最經(jīng)典的層次路由協(xié)議之一，本文研究了LEACH協(xié)議及相關(guān)改進(jìn)協(xié)議，并且針對(duì)其數(shù)據(jù)傳輸以及簇頭選舉等一些方面存在的先天性不足，進(jìn)而提出了一種基于非均勻分簇的多跳路由算法 LEACHMRUC(Mutil-hop Routing Algorithm Based on Uneven Clustering of LEACH)．

2 LEACH協(xié)議

2.1 LEACH協(xié)議介紹

MIT的Heinzelman等人提出的第一個(gè)基于分簇思想的層次路由協(xié)議便是 LEACH，其后許多路由協(xié)議都是在它基礎(chǔ)上發(fā)展而來的．LEACH協(xié)議的主要思想是通過自適應(yīng)分簇的方式將整個(gè)網(wǎng)絡(luò)劃分為多個(gè)不同的簇，并采用輪換的隨機(jī)性簇頭選舉機(jī)制來達(dá)到均衡網(wǎng)絡(luò)負(fù)載、延長(zhǎng)網(wǎng)絡(luò)生命周期的目的．其拓?fù)浣Y(jié)構(gòu)見圖1．

圖1 LEACH協(xié)議的拓?fù)浣Y(jié)構(gòu)圖

LEACH引人了“輪”(round)的概念，每輪循環(huán)由兩個(gè)階段組成，即簇的建立階段和穩(wěn)定傳輸階段，并且其協(xié)議的執(zhí)行過程是周期性的．每個(gè)傳感器節(jié)點(diǎn)在簇的建立階段選擇一個(gè)介于0和1之間的隨機(jī)數(shù)．若該隨機(jī)數(shù)小于閾值T(n)，則此節(jié)點(diǎn)在這一輪中被選舉為簇頭．

其中，p表示在網(wǎng)絡(luò)中簇頭所占節(jié)點(diǎn)的百分比大小；集合G中的元素表示在最近1/p輪中還未當(dāng)選過簇頭的節(jié)點(diǎn)；輪數(shù)r表示當(dāng)前已完成的．

簇頭在節(jié)點(diǎn)選定后通過廣播方式將其成為簇頭的消息告知網(wǎng)絡(luò)，而其他節(jié)點(diǎn)是根據(jù)接收到信息的信號(hào)強(qiáng)弱來決定其所從屬的簇，并向相應(yīng)簇頭發(fā)送請(qǐng)求加入消息，從而完成簇的建立工作．隨后，簇頭節(jié)點(diǎn)采用TDMA方式為簇內(nèi)成員分配傳播數(shù)據(jù)的時(shí)間片，并告知簇內(nèi)成員．

穩(wěn)定傳輸階段，簇內(nèi)成員節(jié)點(diǎn)將在所屬時(shí)間片內(nèi)采集到的數(shù)據(jù)發(fā)送給簇頭，簇頭節(jié)點(diǎn)將接收到的簇內(nèi)成員數(shù)據(jù)進(jìn)行相應(yīng)的融合處理，最后將融合后的數(shù)據(jù)發(fā)往基站，之后又開始新一輪循環(huán)．

2.2 LEACH協(xié)議缺陷

LEACH 協(xié)議在無線傳感器網(wǎng)絡(luò)中意義重大，但也有幾點(diǎn)缺陷：(1)LEACH協(xié)議基于初始能量同構(gòu)前提，在實(shí)際應(yīng)用中存在著局限；(2)LEACH協(xié)議采用隨機(jī)性的簇頭選舉及均勻分簇方式，可能使得某些節(jié)點(diǎn)過多擔(dān)任簇頭而過早耗盡能量，從而產(chǎn)生網(wǎng)絡(luò)監(jiān)測(cè)“盲區(qū)”；(3)由于所有簇頭與基站之間采用單跳路由方式，導(dǎo)致簇頭負(fù)載過重，遠(yuǎn)距離通信能耗開銷較大；(4)LEACH協(xié)議的可擴(kuò)展性差，不適合大規(guī)模的無線傳感器網(wǎng)絡(luò)．

3 LEACH-MRUC協(xié)議

在LEACH-MRUC協(xié)議的簇頭選舉過程中，它充分考慮了節(jié)點(diǎn)的能量及位置因素，確保剩余能量較高的節(jié)點(diǎn)優(yōu)先當(dāng)選為簇頭，并且在能量消耗大致相同的情況下，距離基站較近的節(jié)點(diǎn)成為簇頭的可能性更大；此外，由于距離基站較遠(yuǎn)的簇頭能量消耗速度較快，因此，LEACH-MRUC協(xié)議采用非均勻分簇策略，通過構(gòu)建規(guī)模不同的簇結(jié)構(gòu)來均衡負(fù)載；在數(shù)據(jù)傳輸?shù)倪^程中，采用單跳和多跳相結(jié)合的路由方式來實(shí)現(xiàn)簇頭與基站的數(shù)據(jù)通信，既節(jié)省了簇頭節(jié)點(diǎn)與基站遠(yuǎn)距離通信的開銷，也使得網(wǎng)絡(luò)的可擴(kuò)展性得以加強(qiáng)．

3.1 新的成簇機(jī)制

在進(jìn)行簇頭選舉時(shí)，LEACH-MRUC算法與LEACH具有相似的選舉機(jī)制．不同的是，基站在網(wǎng)絡(luò)部署階段需發(fā)送一個(gè)廣播消息，其功率足夠大，根據(jù)接收到的信號(hào)強(qiáng)度RSSI，需要計(jì)算傳感器節(jié)點(diǎn)與基站的近似距離[7]．考慮到 LEACH協(xié)議不適合節(jié)點(diǎn)初始能量不同的場(chǎng)合，且簇頭選舉算法沒有考慮節(jié)點(diǎn)的實(shí)際情況，本文結(jié)合節(jié)點(diǎn)的能量和距離因子，給出了如下閾值T(n)的計(jì)算公式：其中，Ecurrt：節(jié)點(diǎn)的剩余能量，Einit：節(jié)點(diǎn)的初始能量，n：網(wǎng)絡(luò)預(yù)計(jì)要運(yùn)行的輪數(shù)，d：當(dāng)前節(jié)點(diǎn)到基站的距離，節(jié)點(diǎn)到基站的最大值、最小值，常數(shù)w大于0小于1，隨網(wǎng)絡(luò)規(guī)模和場(chǎng)景的不同進(jìn)行大小設(shè)置．

基于公式(2)的改進(jìn)，當(dāng)選為簇頭往往是剩余能量較高的節(jié)點(diǎn)，而如果能量相當(dāng)，成為簇頭的可能性就處決于距離基站遠(yuǎn)近，從而確保選出的簇頭位置合理且具有較多能量，優(yōu)化所形成簇的結(jié)構(gòu)．

無線傳感器網(wǎng)絡(luò)中，第一順序無線電模型[6]一般被采用，節(jié)點(diǎn)發(fā)送k比特?cái)?shù)據(jù)所消耗的能量：

其中，Eelec：電路消耗的能量，功率放大器的能量損耗系數(shù)，d：傳輸距離，dc：距離閾值．

節(jié)點(diǎn)接收數(shù)據(jù)時(shí)的能耗為

在基于多跳方式的路由協(xié)議中，距離基站較近的節(jié)點(diǎn)需承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)工作，此外，根據(jù)多徑衰減模型可知，節(jié)點(diǎn)與基站進(jìn)行遠(yuǎn)距離傳輸時(shí)能量的消耗與距離的4次方成正比，因此，為了均衡不同地理位置的簇頭節(jié)點(diǎn)的能耗，LEACHMRUC算法中采用非均勻分簇的策略，通過控制各簇頭的廣播范圍來構(gòu)建不均等的簇結(jié)構(gòu)．

定義節(jié)點(diǎn)i的廣播半徑Ri為

由公式(5)可知，節(jié)點(diǎn)的廣播半徑與節(jié)點(diǎn)到基站距離的大小成正比，節(jié)點(diǎn)的廣播范圍始終在R與之間變化，與基站相距越近的節(jié)點(diǎn)其廣播半徑越小，用于管理簇內(nèi)成員所消耗的能量也就越少，從而使其具有更多的能量用于多跳通信時(shí)的數(shù)據(jù)轉(zhuǎn)發(fā)．

3.2 數(shù)據(jù)傳輸策略

LEACH-MRUC協(xié)議中，簇頭與基站進(jìn)行通信時(shí)采用單跳和多跳相結(jié)合的傳輸模式．算法中引入了一個(gè)臨界值TD_MAX，當(dāng)簇頭與基站的距離大于臨界值TD_MAX時(shí)，簇頭以多跳路由的方式與基站進(jìn)行通信，否則與基站直接進(jìn)行通信，最終形成一棵以基站為根節(jié)點(diǎn)的路由樹．

在穩(wěn)定傳輸階段開始前，各個(gè)當(dāng)選為簇頭的節(jié)點(diǎn)以相同的功率向全網(wǎng)廣播一條包含其自身ID、當(dāng)前剩余能量以及它與基站距離的消息，當(dāng)某個(gè)簇頭節(jié)點(diǎn)收到來自其他簇頭節(jié)點(diǎn)的廣播消息后通過計(jì)算獲得它們之間的距離值．在采用多跳路由進(jìn)行通信的過程中，假設(shè)簇頭i的下一跳候選簇頭節(jié)點(diǎn)的集合為MCH，則MCH應(yīng)滿足

假設(shè)簇頭i選擇簇頭j作為其數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳并將數(shù)據(jù)發(fā)往基站，根據(jù)能耗計(jì)算公式，傳輸k比特?cái)?shù)據(jù)所消耗的總能量為

圖2 路由樹模型

4 仿真結(jié)果及分析

本文通過NS2平臺(tái)對(duì)LEACH-MRUC算法仿真，將200個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在300 m*300 m的監(jiān)測(cè)區(qū)域，基站坐標(biāo)為(150,350)，節(jié)點(diǎn)的初始能量為 3 J，發(fā)送和接受數(shù)據(jù)的能量損耗為 50 nJ/bit，ω為0.8，TD_MAX為140 m，λ為0.5，假設(shè)數(shù)據(jù)在轉(zhuǎn)發(fā)過程中無丟失．

本文分別從網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)能量消耗及每輪簇頭所消耗的總能量三方面對(duì) LEACHMRUC、LEACH以及HEED協(xié)議進(jìn)行比較．

4.1 每輪存活節(jié)點(diǎn)數(shù)目比較

圖3 網(wǎng)絡(luò)存活節(jié)點(diǎn)對(duì)比

圖3為網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)的對(duì)比，從圖中可以看出，在210 s及350 s附近，LEACH和HEED協(xié)議開始有節(jié)點(diǎn)出現(xiàn)死亡，到600 s和760 s的時(shí)候網(wǎng)絡(luò)中的節(jié)點(diǎn)已全部死亡，而LEACH-MRUC算法中第一個(gè)死亡節(jié)點(diǎn)出現(xiàn)的時(shí)間為620 s附近，最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間則為970 s左右．

圖3中的曲線顯示，LEACH-MRUC算法的存活節(jié)點(diǎn)數(shù)目隨時(shí)間變化的曲線明顯優(yōu)于LEACH 和HEED，這主要是因?yàn)長(zhǎng)EACH-MRUC算法中節(jié)點(diǎn)的負(fù)載均衡度更好，避免了某些節(jié)點(diǎn)負(fù)載過重而過早死亡的現(xiàn)象．

此外，在無線傳感器網(wǎng)絡(luò)中，第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間跨度可以很好的反映網(wǎng)絡(luò)穩(wěn)定工作的情況，跨度越短說明網(wǎng)絡(luò)的能耗均衡度越好，因而性能也就越穩(wěn)定．表 1顯示LEACH-MRUC既使得網(wǎng)絡(luò)壽命得到有效的延長(zhǎng)，并且由于時(shí)間跨度明顯小于另外兩種協(xié)議，使得網(wǎng)絡(luò)的性能得到顯著提高．

表1 節(jié)點(diǎn)壽命值對(duì)照

4.2 總能量消耗對(duì)比

圖4為網(wǎng)絡(luò)的總損耗隨時(shí)間變化的曲線，圖中顯示LEACH的總能量消耗速度最快，HEED略優(yōu)于LEACH，而LEACH-MRUC算法的曲線斜率大都低于LEACH和HEED，因而其總能量消耗速度相對(duì)而言更為緩慢，這很大程度上得益于LEACH-MRUC算法在簇頭選舉過程中考慮了位置因素和節(jié)點(diǎn)能量，對(duì)所形成簇的結(jié)構(gòu)進(jìn)行了優(yōu)化，同時(shí)改進(jìn)了對(duì)簇間的路由方式，減少了基站與簇頭遠(yuǎn)距離通信的開銷，節(jié)約了能量．

圖4 網(wǎng)絡(luò)總能耗比較

4.3 每輪簇頭消耗能量對(duì)比

在分簇路由協(xié)議中，簇頭節(jié)點(diǎn)所消耗的能量在網(wǎng)絡(luò)的總能量消耗中所占比重非常大，簇頭相對(duì)普通節(jié)點(diǎn)所承擔(dān)的任務(wù)更多，因而也更容易由于負(fù)載過重而導(dǎo)致失效，因此，對(duì)比網(wǎng)絡(luò)中每輪簇頭節(jié)點(diǎn)所消耗的能量也是評(píng)估協(xié)議性能優(yōu)劣的重要手段．圖5為實(shí)驗(yàn)過程中各隨機(jī)選取連續(xù)16輪所統(tǒng)計(jì)的簇頭總能耗對(duì)比．

從圖5可以看出，LEACH-MRUC各輪中簇頭節(jié)點(diǎn)消耗的總能量低于LEACH、HEED，這與該算法中采用非均勻分簇的策略進(jìn)行分簇是密不可分的，非均勻的簇結(jié)構(gòu)很好的均衡了不同地理位置的簇頭的負(fù)載．同時(shí)，LEACH-MRUC在通信過程中采用了單跳與多跳相結(jié)合的通信機(jī)制，減少了與基站直接通信的簇頭的數(shù)目，節(jié)省了簇頭遠(yuǎn)距離通信的能耗代價(jià)．相對(duì)LEACH和HEED而言，圖5中LEACH-MRUC算法所代表的曲線的波動(dòng)性也較小，這也說明LEACH-MRUC算法在穩(wěn)定性及負(fù)載均衡度方面得到了提升．

圖5 各協(xié)議每輪簇頭總能耗比較

5 結(jié)束語

本文對(duì)LEACH協(xié)議進(jìn)行了詳細(xì)的分析，并針對(duì)其問題提出了一種基于非均勻分簇的無線傳感器多跳路由算法(LEACH-MRUC)．在LEACHMRUC算法中，新的成簇機(jī)制確保了選出簇頭的合理性，同時(shí)非均勻分簇的方式也很好的均衡了網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的負(fù)載，此外單跳與多跳相結(jié)合的路由方式避免了所有簇頭與基站遠(yuǎn)距離直接通信時(shí)不必要的能量消耗．仿真實(shí)驗(yàn)表明，該算法在節(jié)點(diǎn)存活情況、網(wǎng)絡(luò)總能耗以及每輪簇頭所消耗能量方面均優(yōu)于LEACH和HEED，既延長(zhǎng)了網(wǎng)絡(luò)的生命周期，又有效提高了能量的利用效率．

[1]黃海寧, 任豐原, 林闖. 無線傳感器網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 2003, 14(7): 1252-1291.

[2]Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[3]Zhonghua Zhao,Wei Huangfu, Linmin Sun.NSSN: A network monitoring and packet sniffing tool for wireless sensor networks[C]//Proceedings of the 8th International Conference on Wireless Communications and Mobile Computing, 2012: 537-542.

[4]Zhang Wenya, Liang Zize, Hou Zengguang,et al. A power efficient routing protocol for wireless sensor network[C]// Proceedings of the IEEE International Conference on Networking Sensing and Control. Washington, DC: IEEE Computer Society, 2007: 20-25.

[5]Heinzelman W, Chandrakasan A, Balakrishnan H. Energyefficient communication protocol for wireless Micro-sensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Maui: IEEE Computer Society, 2000: 3005-3014.

[6]Zhang Jun-guo, LI Wen-bin, CUI Dong-xu,et al. The NS2-based simulation and research on wireless sensor network route protocol[C]//Proceedings of the 5th International Conference on Wireless Communications, Netwarking and Mobile Computing. Piscataway, 2009: 3146-3149.

[7]李成法, 陳貴海, 葉懋, 等. 一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]. 計(jì)算機(jī)學(xué)報(bào), 2007, 30(1): 27-36.

(責(zé)任編校：蔣冬初)

A Mutil-hop Routing Algorithm Based on Uneven Clustering for Wireless Sensor Networks

LIN Ren, XIA Fang-li, WANG Fei
(College of Mathematics & Computer Science, Hunan City University, Yiyang, Hunan 413000, China)

Concerning the deficiencies of Low Energy Adaptive Clustering Hierarchy (LEACH) routing protocol, approximately uniform cluster structure, unreasonable cluster-head nodes selection and also more than one cluster-heads consuming excessive energy in the process of long-distance communications, a mutil-hop routing algorithm based on uneven clustering is proposed. In the set-up phase, the remaining energy and the geographical position of nodes are fully considered, and it uses non-uniform clustering way to build cluster structure of different sizes. In the steady-state phase, a routing method with single-hop and multi-hop is also introduced to the communicate between cluster-heads and Base Station (BS). Simulation results show that the algorithm effectively balances the energy consumption of networks, improves energy efficiency and obvious prolongs the network lifetime.

wireless sensor networks; load balancing; uneven clustering; energy efficient

O646

A

10.3969/j.issn.1672-7304.2017.01.11

1672–7304(2017)01–0049–05

2016-11-10

中央高?；究蒲袠I(yè)務(wù)費(fèi)專題項(xiàng)目(SWJTU12ZT12)；國家教育部人文社會(huì)科學(xué)研究規(guī)劃基金項(xiàng)目(13YJA630144)；益陽市科技計(jì)劃項(xiàng)目(益科字[2016]51號(hào))

林仁(1979-)，男，湖南邵陽人，講師，博士，主要從事項(xiàng)目管理與調(diào)度優(yōu)化、智能優(yōu)化算法研究．E-mail: 232898945@qq.com