雷宇飛，簡必建

(泉州信息工程學院，福建泉州 362000)

無線傳感器網(wǎng)絡(luò)(WSN)是由大量廉價的、低成本的感知設(shè)備組成的網(wǎng)絡(luò)。具有實時性、低能耗、低成本、低速率、自適應(yīng)等特點，由于能量由一次性微型電池供應(yīng)，因此能量有限成為了WSN的最大限制，而通信部分消耗的能耗最大[1]，所以如何設(shè)計能量高效的路由協(xié)議是無線傳感器網(wǎng)絡(luò)的關(guān)鍵問題之一。

無線傳感器網(wǎng)絡(luò)路由協(xié)議是面向應(yīng)用的，不同的應(yīng)用場合有著不同的路由協(xié)議，隨著無線傳感器網(wǎng)的發(fā)展，近年來國內(nèi)外學者提出了大量的路由協(xié)議。根據(jù)網(wǎng)絡(luò)拓撲結(jié)構(gòu)的不同，路由協(xié)議分為平面路由協(xié)議和分簇路由協(xié)議。研究表明，無線傳感器網(wǎng)絡(luò)采用分簇的路由協(xié)議以及簇間通過多跳轉(zhuǎn)發(fā)發(fā)送數(shù)據(jù)能夠明顯地降低網(wǎng)絡(luò)能耗[2-3]。因此，近年來學者們提出了許多能量高效的分簇路由協(xié)議。分簇算法根據(jù)成簇階段簇的形成方式的不同，分為均勻分簇算法和非均勻分簇算法，主要的均勻分簇算法有LEACH算法、LEACH-C和HEED協(xié)議[4]等，該類協(xié)議將目標區(qū)域劃分為大小相同的小區(qū)域，每個區(qū)域中有且只有一個簇頭節(jié)點，普通節(jié)點只能和所在區(qū)域的簇頭進行數(shù)據(jù)傳輸，最后由簇頭節(jié)點將數(shù)據(jù)發(fā)送至網(wǎng)關(guān)節(jié)點。其中，LEACH算法是典型的低功耗自適應(yīng)的分簇算法，能有效地提高節(jié)點的能量效率，是一種高效的路由協(xié)議。主要的非均勻分簇算法有UCS協(xié)議[5]、EEUC協(xié)議[6]等，此類協(xié)議的基本思想是將網(wǎng)絡(luò)的區(qū)域根據(jù)節(jié)點距離網(wǎng)關(guān)節(jié)點的遠近不同，劃分為大小不一的簇，遠離網(wǎng)關(guān)節(jié)點的簇的規(guī)模較大，更多地承擔收集采樣數(shù)據(jù)的功能，靠近網(wǎng)關(guān)節(jié)點的簇則更多地擔任數(shù)據(jù)轉(zhuǎn)發(fā)的任務(wù)，通過多跳的方式將數(shù)據(jù)傳輸至網(wǎng)關(guān)節(jié)點，從而實現(xiàn)全局范圍內(nèi)簇頭節(jié)點能耗的均衡。

1 LEACH算法與問題分析

1.1 LEACH協(xié)議

LEACH[7](Low Energy Adaptive Clustering Hierarchy)是MIT研究人員A.Chandrakasan等為無線傳感器網(wǎng)絡(luò)設(shè)計的低功耗的自適應(yīng)分簇路由協(xié)議。它打破了原有成簇算法中固定簇頭的思想，采用本地簇頭隨機輪流當選簇頭的機制將能量負載均勻分布到網(wǎng)絡(luò)中的所有節(jié)點，提高了網(wǎng)絡(luò)壽命。LEACH路由協(xié)議網(wǎng)絡(luò)模型如圖1所示。

圖1 LEACH路由協(xié)議網(wǎng)絡(luò)模型

LEACH協(xié)議執(zhí)行過程是周期性的，稱為“輪”(Rounds)，每個周期分為簇的建立階段和穩(wěn)定狀態(tài)階段。簇的建立階段又可以分為簇頭選舉階段和成簇階段，一般規(guī)定簇的建立階段比穩(wěn)定階段的時間短，算法流程圖如圖2所示。

圖2 LEACH算法流程圖

簇的建立階段，網(wǎng)絡(luò)中的每個節(jié)點都產(chǎn)生一個0到1之間的隨機數(shù)用于與閾值T(si)比較，如果節(jié)點產(chǎn)生的隨機數(shù)小于閾值則成為本輪簇首，閾值T(si)的計算公式為：

(1)

其中，p是一個預(yù)先設(shè)定的常量，表示期望簇頭節(jié)點占所有節(jié)點的比例；r為當前輪數(shù)；si表示傳感器節(jié)點標識；G表示在過去rmod(1/p)中簇頭競選失敗的節(jié)點。由公式(1)可以看出，每1/p輪網(wǎng)絡(luò)所有節(jié)點均依照一定概率當選過一次簇頭，直到所有節(jié)點都當選過簇頭后才重新獲得競選簇頭的權(quán)利。簇頭節(jié)點競選成功之后，則向全網(wǎng)發(fā)布一條消息宣布自己成為簇頭。未成為簇頭的節(jié)點根據(jù)接收到信號強度加入到離自己最近的簇頭，并發(fā)送申請加入請求消息，簇頭根據(jù)成員數(shù)量建立一個TDMA調(diào)度，并將這個調(diào)度發(fā)送給所有成員，防止節(jié)點數(shù)據(jù)傳輸發(fā)生沖突，節(jié)點收到調(diào)度之后整個網(wǎng)絡(luò)就進入穩(wěn)定狀態(tài)階段。

在穩(wěn)定狀態(tài)階段，普通節(jié)點只能在簇內(nèi)指定的持續(xù)時間內(nèi)(時隙)發(fā)送自己感知的數(shù)據(jù)給簇頭節(jié)點。普通節(jié)點在沒有發(fā)送數(shù)據(jù)時，將進入休眠狀態(tài)以節(jié)省能量，而簇頭則保持工作狀態(tài)以接收數(shù)據(jù)。簇頭節(jié)點接收數(shù)據(jù)后經(jīng)融合處理后，最后由單跳發(fā)送至Sink節(jié)點。

1.2 LEACH協(xié)議的問題分析

LEACH算法采用隨機選舉簇首的機制，在新一輪競選的過程中，最近幾輪為當選過簇首的節(jié)點隨機產(chǎn)生(0,1)的隨機數(shù)，然后與閾值T(si)比較，如果節(jié)點產(chǎn)生的隨機數(shù)小于閾值則成為本輪簇首。由于競選過程中未考慮節(jié)點的位置，導(dǎo)致產(chǎn)生的簇頭節(jié)點會出現(xiàn)位置集中的情況，同時會出現(xiàn)簇頭節(jié)點位置不理想導(dǎo)致節(jié)點間的通信能耗浪費的情況，如圖3所示。

圖3 LEACH算法分簇結(jié)果圖

在LEACH算法中，在簇頭選舉階段若只考慮節(jié)點的當選簇首的頻率，未考慮簇頭節(jié)點能量因素，會導(dǎo)致某些節(jié)點因距離網(wǎng)關(guān)節(jié)點遠近差異或者由于簇成員數(shù)目不一致而導(dǎo)致能量消耗不均衡的問題。

2 LEACH-M算法

基于對現(xiàn)有路由算法的研究與分析，本文提出了基于能量均衡的均勻分簇路由算法(LEACH-M)。采用二次競選的方法來產(chǎn)生最終簇首，綜合考慮節(jié)點的能量因素，通過輪換的機制首先產(chǎn)生候選簇首，然后根據(jù)節(jié)點的通信半徑，綜合考慮節(jié)點的能耗產(chǎn)生最終簇首。

2.1 網(wǎng)絡(luò)模型與通信模型

考慮一個由N個傳感器節(jié)點隨機均勻分布的方形監(jiān)測區(qū)域，檢測數(shù)據(jù)被周期性地收集，定義周期為輪，由Sink節(jié)點根據(jù)實際應(yīng)用背景在初始化時設(shè)置并廣播，每輪包括分簇階段和數(shù)據(jù)傳輸階段，在數(shù)據(jù)傳輸階段普通節(jié)點將采集數(shù)據(jù)直接傳輸給簇頭，簇頭對收集到的數(shù)據(jù)進行數(shù)據(jù)融合處理,然后通過多跳方式發(fā)送給匯聚節(jié)點。對于網(wǎng)絡(luò)模型有以下假設(shè)：

(1)Sink節(jié)點位于監(jiān)測區(qū)域外，且Sink節(jié)點和傳感器節(jié)點在部署后處于靜止狀態(tài)，位置不再變化。

(2)傳感器節(jié)點si,i=1,2,…,N的初始能量相同，功能、結(jié)構(gòu)也相同，每個節(jié)點均有唯一的標識(ID)。

(3)傳感器節(jié)點的地理位置可知，通過接收信號強度來估計二者之間的距離。

(4)傳感器節(jié)點可以根據(jù)接收方的距離來自主調(diào)節(jié)發(fā)送功率。

LEACH-M協(xié)議采用典型的無線通信能耗模型[8]傳輸k比特的數(shù)據(jù)包通過距離d的能耗為：

(2)

其中，Etx為傳輸電路能耗；Eamp為放大電路的能耗；β是一個路徑損耗常數(shù)，依賴于傳輸環(huán)境。當d≤d0和d>d0時，功率放大損耗分別采用“自由空間模型”和“多路徑衰減模型”，d0的取值如式(3)所示。

(3)

接收k比特數(shù)據(jù)能耗的計算公式：

Erx(k,d)=kErx.

(4)

其中，Erx表示接收電路能耗；融合k比特數(shù)據(jù)包的能耗Eag(k)=kEag。

2.2 簇的建立階段

2.2.1 簇首選舉策略

簇首選舉流程如圖4所示。

圖4 LEACH-M算法分簇流程圖

假設(shè)監(jiān)測區(qū)域中有N個節(jié)點，監(jiān)測區(qū)域的面積為S，假設(shè)簇的通信半徑為Rc，規(guī)定小區(qū)域的簇內(nèi)有且只有一個節(jié)點成為簇頭節(jié)點，監(jiān)測區(qū)域內(nèi)最多有個ceil(S/(πRc_min2))簇頭節(jié)點，進而可以得到期望簇首與節(jié)點的比例：

(5)

每經(jīng)過1/pt輪后所有節(jié)點同時獲得競選簇首的權(quán)利，因此可通過輪流競選簇首方式來產(chǎn)生最終簇首。在新一輪中，節(jié)點si,i=1,2,…,N是否成為候選簇首由動態(tài)閾值T(si)決定，T(si)的計算公式：

(6)

其中，p表示期望候選簇首占所有節(jié)點的百分比；rm=rmod(1/pt)表示輪換周期的臨界值；pt表示期望最終簇首占所有節(jié)點的最大百分比；G表示在前(r-1)mod(rm)未當選為最終簇首的集合；si表示節(jié)點標識。

由式(6)首先隨機產(chǎn)生候選簇首節(jié)點，通過輪換的機制，保證所有節(jié)點在一定周期內(nèi)當選簇首的頻率是相同的，從而在時間分布上消除節(jié)點因當選簇首頻率差異導(dǎo)致過早失效的情況。如果僅考慮節(jié)點當選簇首的頻率而不考慮節(jié)點位置以及能量因素會導(dǎo)致節(jié)點間能耗不均衡的情況。因此首先引入通信半徑Rc來構(gòu)造鄰居簇首集合SCH，候選簇首sj的鄰簇首集sj·SCH為：

sj·SCH={sm|sm∈tentativeCHs,d(sj,sm)≤Rc}.

(7)

如果候選簇首sj一旦發(fā)現(xiàn)自身在鄰簇首集合中自身的剩余能量最大，則競選成功并廣播獲勝消息給其鄰居候選簇首，成為最終簇首。如果在鄰居簇首集中自身的剩余能量不是最大，則需等待鄰居簇首集中剩余能量大的節(jié)點先做出決策：若收到剩余能量比自己大的鄰簇首sk競選成功的消息，則候選簇首sj立即宣布退出競選，成為普通節(jié)點；若候選簇首sj收到剩余能量比自己大的鄰簇首sm退出競選的消息，則將sm在鄰簇首集合sj·SCH中刪除。由此整個簇首選舉過程結(jié)束。

2.2.2 分簇階段

簇首產(chǎn)生之后，未參與競選的節(jié)點被重新喚醒，然后簇首向全網(wǎng)廣播自身成為簇首的消息，普通節(jié)點選擇加入信號強度強的簇，成為該簇的成員節(jié)點，并向?qū)?yīng)的簇首發(fā)送加入消息。

簇頭節(jié)點根據(jù)簇成員數(shù)目，全網(wǎng)廣播的形式向所有簇成員節(jié)點發(fā)送一個TDMA調(diào)度表，保證所有節(jié)點不沖突地發(fā)送數(shù)據(jù)給簇頭。

2.3 數(shù)據(jù)傳輸階段

2.3.1 簇內(nèi)數(shù)據(jù)傳輸

為了便于實現(xiàn)，簇內(nèi)數(shù)據(jù)通信采用與EEUC協(xié)議相同的通信方式——單跳通信，具體過程不再贅述。

2.3.2 簇間數(shù)據(jù)傳輸

為了驗證LEACH-M算法的有效性，簇間采用單跳通信，即簇頭節(jié)點直接和網(wǎng)關(guān)節(jié)點通信。

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

通過MATLAB進行實驗仿真，分析LEACH-M協(xié)議的能量效率和網(wǎng)絡(luò)的能量分布情況,并和LEACH協(xié)議進行比較。為了便于分析，假設(shè)采用理想的MAC協(xié)議，忽略無線通信發(fā)生丟包情況。仿真過程中應(yīng)考慮路由建立過程中所有的通信能耗，包括廣播包、數(shù)據(jù)包的能耗及數(shù)據(jù)融合的能耗，為了保證數(shù)據(jù)的精度，只融合本簇內(nèi)數(shù)據(jù)。具體仿真數(shù)據(jù)如表1所示。

表1 仿真參數(shù)

3.1 網(wǎng)絡(luò)拓撲分析

圖5顯示了LEACH-M協(xié)議的網(wǎng)絡(luò)拓撲。可以看出，LEACH-M協(xié)議在分簇階段采用了競選的機制,綜合考慮了位置和能量，保證了簇首的均勻分布，避免了簇首扎堆的情況，有利于均衡簇首間的能耗。

圖5 LEACH-M協(xié)議網(wǎng)絡(luò)拓撲

圖6 兩種算法網(wǎng)絡(luò)生存時間曲線圖

3.2 網(wǎng)絡(luò)的能量效率

由圖6可以看出，LEACH算法的第一個節(jié)點死亡時間為202，LEACH-M算法的第一個節(jié)點死亡時間為668,結(jié)果表明LEACH-M算法能夠有效延長網(wǎng)絡(luò)的生存時間。圖7是網(wǎng)絡(luò)總能量隨工作時間變化的曲線圖，可以看出LEACH-M算法每輪能耗相對均衡，能量總量值與工作時間成反比關(guān)系，而LEACH算法網(wǎng)絡(luò)總能耗隨工作時間變化關(guān)系不是曲線關(guān)系，輪與輪之間能耗不均衡。圖8為每輪網(wǎng)絡(luò)能耗隨工作時間變化曲線圖?？梢钥闯鯨EACH-M算法的節(jié)點能耗相對于LEACH算法更均衡、更穩(wěn)定。

圖7 網(wǎng)絡(luò)剩余總能量變化曲線圖

圖8 平均能耗使用曲線

4 結(jié)語

本文在現(xiàn)有均勻分簇算法研究與分析基礎(chǔ)上，提出了一種基于能耗均衡的均勻分簇算法(LEACH-M)。首先以輪換的機制先產(chǎn)生候選簇首，然后綜合考慮候選簇首的位置和能量因素，競爭產(chǎn)生最終簇首。仿真結(jié)果表明，LEACH-M算法能夠有效地延長網(wǎng)絡(luò)的生存時間，而且均衡整個網(wǎng)絡(luò)的能耗，提高網(wǎng)絡(luò)的性能。

[參考文獻]

[1]Tashtarian,E Haghighat,A T Honary,et al.A new energy-efficient cluster algorithm for wireless sensor networks[C].Sofiware,Telecommunications and Computer Networks,15th Intemational Conferenee on,2007.

[2]孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學出版社,2005.

[3]Mhatre V,Rosenberg C.Design guidelines for wireless sensor networks:communication,clustering and aggregation[J]. Ad Hoc Networks,2004(1):45-63.

[4]Younis O,Fahmy S.HEED:A Hybrid,Energy-efficient,distributed clustering approach for Ad Hoc sensor networks[J]. IEEE Transactions on Mobile Computing,2004(4):366-379.

[5]Akyildiz LF, Su W,Sankara subramaniam Y.Wireless sensor network[J].A survey Computer Networks,2002(4):22-34.

[6]Zhiyuan S,Liu F,Hou B,et al.Energy-efficient uneven clustering routing protocol for wireless sensor networks[J].Transducer & Microsystem Technology,2013(12):67-60.

[7]Holger K,Andreas W.Protocols and architectures for wireless sensor networks[M].Beijing: Publishing House of Electronics Industy,2007.

[8]Zheng L,Gao L,Yu T.An Energy-balanced clustering algorithm for wireless sensor networks based on distance and distribution[C].Proceedings of the 6th International Asia Conference on Industrial Engineering and Management Innovation,Atlantis Press,2016:229-240.