改進(jìn)的網(wǎng)絡(luò)路由協(xié)議低功耗自適應(yīng)分簇算法

劉 軍，李 巖，齊 華

（1.武警工程學(xué)院，陜西 西安 710086；2.西安工業(yè)大學(xué)電子信息工程學(xué)院，陜西 西安 710032）

0 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network）［1］是數(shù)據(jù)采集、處理及通信功能于一體的分布式自組織網(wǎng)絡(luò)，具有分布式式處理帶來的高監(jiān)測(cè)精度、高容錯(cuò)性、大覆蓋區(qū)域、可遠(yuǎn)程監(jiān)控等眾多的優(yōu)點(diǎn)，在軍事、環(huán)境監(jiān)測(cè)、醫(yī)療、智能建筑及其他商業(yè)領(lǐng)域等方面有著廣泛的應(yīng)用。

無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)能量有限，不同于傳統(tǒng)的有限網(wǎng)絡(luò)。無線傳感器網(wǎng)絡(luò)的路由協(xié)議必須時(shí)刻關(guān)注降低能耗、延長(zhǎng)網(wǎng)絡(luò)生命周期這一核心問題［2］。設(shè)計(jì)精良的網(wǎng)絡(luò)協(xié)議就可以降低能耗，延長(zhǎng)網(wǎng)絡(luò)的生命周期。目前，路由協(xié)議的主流是層次路由協(xié)議，該協(xié)議具有代表性的路由算法是低功耗自適應(yīng)分簇（LEACH）算法［3］。LEACH 算法中，簇首形成高一層的網(wǎng)絡(luò)，這樣簇內(nèi)成員的功能就變相對(duì)簡(jiǎn)單，大大減少了路由控制信息的數(shù)量。但該算法也存在著簇首分布不均勻、簇首與基站之間只能采用單跳路徑的問題。針對(duì)以上問題，以降低功耗，實(shí)現(xiàn)能量均衡、延長(zhǎng)網(wǎng)絡(luò)壽命為目的，對(duì)LEACH算法進(jìn)行改進(jìn)。

1 LEACH算法的分析

LEACH 算法（Low Energy Adaptive Clustering Hierarchy）是 MIT的Chandrakasan等人為無線傳感器網(wǎng)絡(luò)設(shè)計(jì)的低功率自適應(yīng)分簇路由算法。它的基本思想是以循環(huán)的方式隨機(jī)選擇簇首節(jié)點(diǎn)，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)中，從而達(dá)到提高網(wǎng)絡(luò)整體生存時(shí)間的目的。

1.1 LEACH算法的工作流程

該算法的建立主要包括三個(gè)階段：

1）簇首的建立階段

簇頭節(jié)點(diǎn)的選取是LEACH算法中的關(guān)鍵，具體的選擇方法是：各節(jié)點(diǎn)產(chǎn)生一個(gè)［0，1］之間的隨機(jī)數(shù)，若該數(shù)小于某一個(gè)閾值T（n），則該節(jié)點(diǎn)成為簇頭。T（n）［4］如公式：

式中，p是網(wǎng)絡(luò)中簇頭數(shù)與總節(jié)點(diǎn)數(shù)的百分比；r是當(dāng)前的選舉輪數(shù)；G是最近1／p輪不是簇頭的節(jié)點(diǎn)集合。

被選為簇首的節(jié)點(diǎn)會(huì)利用CSMA MAC協(xié)議廣播ADV消息，宣布自己成為簇首。非簇首節(jié)點(diǎn)收到來自各簇首的消息，并根據(jù)接收信號(hào)的強(qiáng)度選擇強(qiáng)度最大的簇首發(fā)送加入請(qǐng)求JOIN－REQ，其包含了節(jié)點(diǎn)的ID和要求加入簇首的ID信息。

2）時(shí)隙表建立階段

當(dāng)簇首確定并且簇域劃分工作完成，簇頭將根據(jù)成員節(jié)點(diǎn)的數(shù)目，產(chǎn)生TDMA時(shí)隙表［5］。成員節(jié)點(diǎn)通過接收簇首的廣播獲取該表，并在自己的時(shí)隙到達(dá)時(shí)才開啟發(fā)送裝置向簇首發(fā)送數(shù)據(jù)，其余時(shí)間處于休眠狀態(tài)以節(jié)省寶貴能量。

3）穩(wěn)定階段

相對(duì)于簇的建立階段，這個(gè)階段是相對(duì)較長(zhǎng)的一個(gè)階段，該階段主要是各節(jié)點(diǎn)完成數(shù)據(jù)傳輸?shù)娜蝿?wù)。一旦簇形成，TDMA時(shí)刻表確定，則數(shù)據(jù)傳輸開始。簇首節(jié)點(diǎn)在收到成員節(jié)點(diǎn)傳來的數(shù)據(jù)后對(duì)數(shù)據(jù)進(jìn)行數(shù)據(jù)融合和壓縮，將壓縮處理后的信號(hào)傳輸給基站。

1.2 LEACH算法存在的問題

1）壽命不均：簇首的選舉策略是隨機(jī)的，可能造成簇首分布不均，簇成員個(gè)數(shù)也有較大差異，使得各簇首負(fù)載不均衡，造成個(gè)別簇首較早死亡。

2）距離受限：LEACH協(xié)議只適用于小規(guī)模的無線傳感器網(wǎng)絡(luò)。由于基站與簇首之間采用單跳路徑選擇模式，所以簇首與基站必須布置在通信可達(dá)的范圍內(nèi)。

2 LEACH算法的改進(jìn)

2.1 改進(jìn)算法的設(shè)計(jì)思路

針對(duì)LEACH算法中存在簇首壽命不均、傳輸距離受限的問題，并結(jié)合無線傳感器網(wǎng)絡(luò)自身的特點(diǎn)，本文從以下幾個(gè)方面對(duì)LEACH算法進(jìn)行改進(jìn)。

1）改變簇首產(chǎn)生方式來均衡各各簇首壽命

簇首的產(chǎn)生主要從以下兩個(gè)方面加以改變：

①基于節(jié)點(diǎn)的剩余能量選擇簇首?？紤]到無線傳感器網(wǎng)絡(luò)的能耗問題，選取能量較多節(jié)點(diǎn)作為簇首。將節(jié)點(diǎn)的剩余能量作為選擇簇首的一個(gè)重要衡量標(biāo)準(zhǔn)，保證區(qū)域內(nèi)剩余能量較多的節(jié)點(diǎn)被選為簇首。

②基于節(jié)點(diǎn)與簇首之間的距離選擇簇首?？紤]到簇首地理分布平均的問題，每個(gè)簇首發(fā)射信號(hào)，其他節(jié)點(diǎn)根據(jù)接收到的信號(hào)判斷離簇首的距離，離簇首距離小于設(shè)定值M的節(jié)點(diǎn)不再選為簇首。從而保證所有簇首之間距離不小于M。

2）改變簇首與基站之間的通信方式來增加傳輸距離

LEACH算法中，簇首與基站之間的數(shù)據(jù)發(fā)送過程采用單跳的方式。由于基站距離傳感區(qū)域很遠(yuǎn)，所以簇首將數(shù)據(jù)發(fā)送給基站時(shí)所消耗的能量很多，基于這一點(diǎn)，在簇首向基站發(fā)送數(shù)據(jù)的時(shí)候采用多跳的方式，這樣可以使簇首節(jié)點(diǎn)能量的消耗相對(duì)減少。因此，本論文提出的改進(jìn)算法將會(huì)把簇首組織起來，以多跳的方式向基站發(fā)送融合之后的數(shù)據(jù)。

2.2 改進(jìn)算法的實(shí)現(xiàn)

與傳統(tǒng)的LEACH算法相比，改進(jìn)后的算法在選擇簇首之前，傳感區(qū)域內(nèi)的所有節(jié)點(diǎn)需要將自己的地理位置信息和節(jié)點(diǎn)能量發(fā)送給基站，基站收集到區(qū)域內(nèi)各個(gè)節(jié)點(diǎn)的位置信息后，根據(jù)這些信息將傳感器網(wǎng)絡(luò)按面積平均劃分為k個(gè)區(qū)域（本論文中設(shè)定k＝3，如圖1所示，這就意味著需要將整個(gè)區(qū)域劃分為三部分）。

區(qū)域劃分完成以后，每個(gè)節(jié)點(diǎn)隨機(jī)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)，如果小于閾值T（n），則該節(jié)點(diǎn)當(dāng)選為候補(bǔ)簇首，T（n）的計(jì)算與LEACH算法中相同，然后把選出的候補(bǔ)簇首按能量的大小遞減排列成一個(gè)隊(duì)列，從隊(duì)列中第一個(gè)節(jié)點(diǎn)開始，取消以節(jié)點(diǎn)為圓心，半徑為M的圓內(nèi)的其它候補(bǔ)簇首成為簇首的資格，并將其從列隊(duì)中刪除。依次遍歷其他節(jié)點(diǎn)，重復(fù)上述操作，最后剩下的候補(bǔ)簇首成為最終簇首。

圖1 傳感區(qū)域的劃分Fig.1 The regional division

當(dāng)選為簇首的節(jié)點(diǎn)會(huì)將自己的ID添加到該簇域的全局變量ch＿list＿中去，最終得到的ch＿list＿就是該簇域內(nèi)所有簇首節(jié)點(diǎn)ID的列表。通過簇域的ch＿list＿即可以得到下游簇域內(nèi)的所有節(jié)點(diǎn)的ID列表，所謂下游指的是指向BS方向的下一個(gè)簇域，有了該列表，就相當(dāng)于得到了下一跳的候選列表，如圖2所示，簇首只需從這些候選節(jié)點(diǎn)中隨機(jī)選出一個(gè)節(jié)點(diǎn)作為自己的下一跳節(jié)點(diǎn)，這樣就將各個(gè)簇首的多跳路徑建立起來了。

簇首確定、簇域劃分完成后，各簇域?qū)⒔⒏髯缘臅r(shí)隙表，時(shí)隙表建立后，進(jìn)入到穩(wěn)定傳輸階段。

圖2 簇首多跳路徑示意圖Fig.2 Multi－ hop path

3 算法的仿真及分析

3.1 仿真平臺(tái)的構(gòu)建

本文 采 用 NS2［6］對(duì) LEACH 及 改 進(jìn) 后 的LEACH算法進(jìn)行了仿真。NS2（Network Simulator）是一種內(nèi)核源代碼開放的，針對(duì)網(wǎng)絡(luò)研究的離散事件大型可視化仿真器。它能夠建立目前幾乎所有網(wǎng)絡(luò)對(duì)象的基本模型之間的互連，并且使復(fù)雜的網(wǎng)絡(luò)交通和拓?fù)浣Y(jié)構(gòu)得到高度切合實(shí)際的模擬和仿真。仿真環(huán)境設(shè)定如下：

1）傳感器節(jié)點(diǎn)和虛擬聚類區(qū)域具有全局唯一的ID標(biāo)識(shí)；

2）網(wǎng)絡(luò)內(nèi)所有傳感器節(jié)點(diǎn)均相同，具有相同的初始能量2J，且到BS均可達(dá)；

3）各個(gè)傳感器節(jié)點(diǎn)具備GPS功能，即節(jié)點(diǎn)能定位其位置。

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

1）圖3對(duì)兩種算法在不同時(shí)段仍然存活的節(jié)點(diǎn)個(gè)數(shù)做出了比較。

圖3 網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)量的仿真Fig.3 Simulation of alive node number

從圖3可以得出以下結(jié)論：

①LEACH算法在365s的時(shí)候出現(xiàn)節(jié)點(diǎn)死亡，而改進(jìn)后的算法在375s的時(shí)候開始有節(jié)點(diǎn)出現(xiàn)死亡。從節(jié)點(diǎn)開始死亡的時(shí)間上來說，改進(jìn)后的算法相對(duì)于LEACH算法提高了2.73%。

②LEACH算法在500s左右的時(shí)候結(jié)束了網(wǎng)絡(luò)生命，而改進(jìn)后的算法在580s左右的時(shí)候才結(jié)束網(wǎng)絡(luò)生命，從網(wǎng)絡(luò)存活時(shí)間比較來說，改進(jìn)后的算法比LEACH算法延長(zhǎng)了16%。

2）不同時(shí)段網(wǎng)絡(luò)內(nèi)存活節(jié)點(diǎn)數(shù)目的比較很直觀地說明了兩種算法下網(wǎng)絡(luò)生命周期的不同，下面從能量消耗的角度來進(jìn)一步對(duì)兩種算法進(jìn)行比較。

圖4比較了兩種算法下在不同時(shí)段網(wǎng)絡(luò)消耗總能量的值，可以看出LEACH算法在500s結(jié)束網(wǎng)絡(luò)生命時(shí)的總能耗是450J左右，而改進(jìn)后的算法在580s結(jié)束生命周期時(shí)總能耗是350J。更進(jìn)一步印證了算法較LEACH算法延長(zhǎng)了網(wǎng)絡(luò)生命周期。

圖4 網(wǎng)絡(luò)總能量消耗的仿真Fig.4 Simulation of energy consumption

3）兩種算法的性能比較

New－LEACH算法和LEACH算法相比，性能有所提高。從表1可以看出，如果以節(jié)點(diǎn)開始死亡的時(shí)間為標(biāo)準(zhǔn)，New－LEACH算法相比LEACH算法能有2.73%的提高；若以網(wǎng)絡(luò)生命周期為標(biāo)準(zhǔn)，則有16%的提高；如果以網(wǎng)絡(luò)總能耗為標(biāo)準(zhǔn)，相比LEACH算法，New－LEACH算法獲得了21%的性能提高。

表1 不同路由協(xié)議下網(wǎng)絡(luò)生命周期的比較Tab.1 The comparison of life－cycle under different network routing prorocols

4 結(jié)論

本文針對(duì)無線傳感器網(wǎng)絡(luò)，在理論分析的基礎(chǔ)上提出了一種改進(jìn)的LEACH算法。該算法在選擇簇首方面，充分地考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)的位置和剩余能量，進(jìn)而使簇的大小更為合理；在簇首與基站之間的路徑選擇方面，采取了多跳傳輸?shù)姆绞?。通過NS2的仿真實(shí)驗(yàn)表明：與傳統(tǒng)的LEACH算法相比較，網(wǎng)絡(luò)的能量消耗率降低了將近21%。因此，改進(jìn)后的算法能更有效地降低與均衡網(wǎng)絡(luò)的能量消耗，從而較大幅度的延長(zhǎng)了傳感器網(wǎng)絡(luò)的生命周期。

［1］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，2005.

［2］余勇昌，韋崗.無線傳感器網(wǎng)絡(luò)中基于PEGASIS協(xié)議的改進(jìn)算法［J］.電子學(xué)報(bào)，2008，36（7）：1 309－1 313.YU Yongchang，WEI Gang.An improved pegasis algorithm in wireless sensor network［J］.Acta Electronica Sinica，2008，36（7）：1 309－1 313.

［3］Shah R C，Rabaey J.Energy Aware Routing for Low Energy Ad hoc Sensor Networks［C］／／Orlando：IEEE Wireless Communications and Networking Conferenee（WCNC），2002：350－355.

［4］陶東.基于無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的仿真分析研究［J］.現(xiàn)代電子技術(shù)，2011：24－26.TAO Dong.Analysis and simulation of leach routing protocol in wireless sensor networks［J］.Modern Electronics Technique，2011（11）：24－26.

［5］王盛.基于NS2的無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的改進(jìn)仿真研究［D］.武漢：武漢理工大學(xué)畢業(yè)論文，2010.

［6］徐雷鳴.NS與網(wǎng)絡(luò)模擬［M］.北京：人民郵電出版，2003.