一種基于LEACH協(xié)議的改進路由算法

王飛飛++丁亞飛

摘 要：針對無線傳感器網絡中LEACH協(xié)議的簇首選擇與簇間數(shù)據(jù)傳輸存在的問題，提出了一種改進的路由算法，該算法在簇首選舉時以節(jié)點剩余能量作為依據(jù)，采用了新的閾值公式，在數(shù)據(jù)傳輸時建立臨時路由表、構建簇間多跳路由。仿真結果表明：改進后的算法可有效地延長網絡內節(jié)點的存活時間，從而延長網絡的生存周期。

關鍵詞：無線傳感器網絡 簇首 數(shù)據(jù)傳輸 多跳路由

中圖分類號：TN929.5 文獻標識碼：A 文章編號：1672-3791（2016）12（a）-0023-02

無線傳感器網絡（WSNs）是由部署在監(jiān)測區(qū)域內的大量傳感器節(jié)點構成的自組織系統(tǒng)，綜合了傳感器技術、分布式信息處理技術和無線通信技術，主要通過各節(jié)點實時地監(jiān)測與采集覆蓋區(qū)域內的各種數(shù)據(jù)信息，然后進行處理和傳輸[1]。WSNs最先應用于軍事與國防領域，隨著技術的發(fā)展與普及，逐漸應用于自然災害、智能家居、生物醫(yī)療與智慧居家養(yǎng)老等領域，市場發(fā)展前景較好。但是因傳感器節(jié)點一般采取電池供電，在能量方面具有一定的局限性。而節(jié)點的能耗主要產生于數(shù)據(jù)采集與傳輸，由平面路由到分簇路由，許多研究者對數(shù)據(jù)傳輸采用的路由協(xié)議在不斷地進行研究與改進[2-4]。該文在對經典路由協(xié)議LEACH[5]分析研究基礎上，針對其簇首節(jié)點選舉時未考慮剩余能量與簇首和基站通信采用的單跳路由問題，提出了基于能量和簇間多跳路由的改進算法，有效地均衡了節(jié)點能耗，延長了網絡生存周期。

1 LEACH協(xié)議分析

1.1 傳輸能耗模型

設定傳感器網絡數(shù)據(jù)傳輸時采用文獻[5]中的無線通信模型，節(jié)點發(fā)送與接收kbit數(shù)據(jù)所消耗的能量計算公式中，d是信號傳輸?shù)木嚯x，根據(jù)d值的大小決定信息傳輸時采用自由空間信道模型還是多徑衰減模型，當d值超過臨界值86.2時，能耗消耗比較大，因此在分簇路由協(xié)議中，在成簇與構建簇間路由時，盡量控制可通信節(jié)點之間的距離。

1.2 LEACH協(xié)議描述

LEACH協(xié)議是最具有代表性的分簇路由協(xié)議，后期許多路由協(xié)議都是在對它研究基礎上所產生的，如LEACH-C、LEACH-F。LEACH協(xié)議主要由簇首選舉、簇的產生、數(shù)據(jù)融合、數(shù)據(jù)傳輸?shù)冉M成，并在其中引入了輪的概念，每輪包括簇的建立和數(shù)據(jù)傳輸兩個階段。

在LEACH協(xié)議中，簇首的選擇具有隨機性，具體步驟如下：監(jiān)測區(qū)域中的傳感器節(jié)點，產生一個介于0、1之間的隨機數(shù)，如果該隨機數(shù)小于此輪所設定的閾值T（n），該節(jié)點就被選定為該輪的簇首，閾值越大，節(jié)點當選為簇首的概率越大，節(jié)點被選為簇首后，發(fā)送簇首廣播信息，非簇首節(jié)可能收到多個廣播信息，其根據(jù)信號強弱決定要加入的簇，并向該簇首發(fā)送請求，簇首收到請求后產生TDMA定時消息并通知簇內各節(jié)點，成簇后，簇首接收該簇內各節(jié)點發(fā)送的信息并進行數(shù)據(jù)融合后直接發(fā)送至基站。

1.3 存在問題

LEACH協(xié)議中，簇首選擇時沒有充分考慮到節(jié)點的剩余能量，其閾值產生公式雖然一定程度上保證了各節(jié)點成為簇首的概率相同，但是并不能保證成為簇首節(jié)點的當前能量。另外，各簇首節(jié)點與基站直接通信，如果簇首距離基站在通信范圍內，會采用自由空間通信模式，否則將采用多路徑衰減模式，導致該部分簇首節(jié)點能量消耗過快。因此，為了解決上述問題，該文在LEACH協(xié)議基礎上提出了新的改進算法，著重解決其在簇首選擇時的能量與簇首數(shù)據(jù)傳輸問題。

2 改進算法

該算法主要在簇首選舉與數(shù)據(jù)傳輸兩個方面進行了研究與改進，具體如下。

2.1 簇首選舉

每輪工作時，節(jié)點向簇首傳遞數(shù)據(jù)時攜帶節(jié)點當前剩余能量，當所有數(shù)據(jù)發(fā)送至基站后，由基站計算當前網絡的平均剩余能量Eave，并以廣播的形式發(fā)送給每個節(jié)點，在簇首選舉時，節(jié)點首先將自己的當前能量Eleft與Eave進行比較，如果大于等于Eave，則根據(jù)新的閾值計算公式判斷是否當選為簇首，如果Eleft小于Eave，則退出競爭。

同時，在產生閾值時引入網絡中的最優(yōu)簇首個數(shù)，該數(shù)確定采用文獻[5]中的簇首計算公式，將此數(shù)應用到LEACH協(xié)議閾值計算公式中，可得到新的計算公式（1）。

（1）

2.2 簇間多跳路由

無線傳感器網絡中簇建立后，簇內節(jié)點將采集的數(shù)據(jù)傳輸給簇首，簇首經過數(shù)據(jù)融合后將數(shù)據(jù)發(fā)送至基站，在LEACH協(xié)議中無論距離遠近，簇首均直接與基站相連，導致部分節(jié)點能量消耗過快，因此簇間路由的創(chuàng)建至關重要。該算法采用簇首多跳路由傳輸?shù)姆椒?，即簇首選擇自己周圍合適的簇首作為中轉節(jié)點，從而減少能量的損耗，具體如下。

在成簇階段，簇首發(fā)送廣播信息，信息中攜帶自己當前剩余能量以及自己的坐標位置，非簇首節(jié)點根據(jù)此信息選擇合適的簇加入，而簇首節(jié)點則根據(jù)信息，選擇合適的簇首加入臨時路由表，路由表建立方法如下：

假設Si節(jié)點的坐標為（x1，y1），Sj節(jié)點的坐標為（x2，y2），基站BS的坐標為（x，y），數(shù)據(jù)由Si經Sj發(fā)送至BS，由式（1）可知，能耗與數(shù)據(jù)傳輸距離相關，即當

d=d2（Si，Sj）+ d2（Sj，BS） （2）

的值較小時，才能達到節(jié)能的目的，式（2）中，d2（Si，Sj）為Si到Sj的距離的平方。

同時考慮到節(jié)點進行數(shù)據(jù)傳輸時所需要的能量較多，在選擇下一跳節(jié)點時除了相互間距離還需將節(jié)點的當前能量作為參考因素，因此在路由表中添加4個滿足條件的節(jié)點，進行數(shù)據(jù)傳輸時選擇Eleft/d值最大的節(jié)點作為中轉節(jié)點。

3 仿真說明與分析

為了將改進后的算法與已有算法進行比較，該文利用OMNET++進行仿真模擬，對網絡內同一時間的節(jié)點存活個數(shù)進行比較，驗證改進算法的性能。仿真環(huán)境：設定在一個200 m×200 m的區(qū)域內，有400個傳感器節(jié)點，節(jié)點在監(jiān)測區(qū)域內隨機分布，基站BS的坐標預先設置（x=50，y=250）；節(jié)點初始能量相同，均為0.5J，數(shù)據(jù)包大小為4 000 bit。

改進后的算法在某一時間點節(jié)點存活數(shù)較多，且整體存活時間較長，原因在于節(jié)點在成簇時選擇距離較近的簇首加入，減少了非簇首節(jié)點的能耗，而在簇首選擇中轉節(jié)點時，綜合考慮了能量與距離因素，也減少了簇首節(jié)點的能耗，從而延長了整個網絡的生命周期。

4 結語

在無線傳感器網絡中，分簇路由協(xié)議占據(jù)著重要的地位，它的性能直接影響到整個網絡的工作效率與生存周期，因此，該文在對經典LEACH路由協(xié)議分析研究的基礎上，針對其能量與數(shù)據(jù)傳輸方面存在的問題，通過新的閾值公式改變原有的簇首選舉方法，結合節(jié)點當前剩余能量建立臨時路由表，構建簇首間數(shù)據(jù)傳輸?shù)亩嗵酚桑倪M后的算法使簇首選舉更合理，數(shù)據(jù)傳輸更加有效。分析顯示，經過改進的算法在均衡網絡節(jié)點能耗與延長生命周期方面有了明顯的提高。

參考文獻

[1] 孫利民，李建中，陳渝，等.無線傳感器網絡[M].清華大學出版社，2005.

[2] 李芳芳，王靖.一種基于LEACH協(xié)議的無線傳感器網絡路由算法[J].傳感技術學報，2012，25（10）：1445-1451.

[3] 陳曉娟，王卓，吳潔.一種基于LEACH的改進WSN路由算法[J].傳感技術學報，2013，26（1）：116-121.

[4] 嚴斌亨，陳任秋，劉軍.能量優(yōu)化的無線傳感器網絡LEACH算法[J].傳感器與微系統(tǒng)，2016，35（7）：120-122.

[5] Heinzelman WB，Chandrakasan AP，Balakrishnan H.An Application Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communications，2002，1（4）：660-670.