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

王飛飛++丁亞飛

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò) 簇首 數(shù)據(jù)傳輸 多跳路由

中圖分類號(hào)：TN929.5 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2016）12（a）-0023-02

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

1 LEACH協(xié)議分析

1.1 傳輸能耗模型

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

1.2 LEACH協(xié)議描述

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

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

1.3 存在問題

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

2 改進(jìn)算法

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

2.1 簇首選舉

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

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

（1）

2.2 簇間多跳路由

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

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

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

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

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

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

3 仿真說明與分析

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

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

4 結(jié)語

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

參考文獻(xiàn)

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

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

[3] 陳曉娟，王卓，吳潔.一種基于LEACH的改進(jìn)WSN路由算法[J].傳感技術(shù)學(xué)報(bào)，2013，26（1）：116-121.

[4] 嚴(yán)斌亨，陳任秋，劉軍.能量?jī)?yōu)化的無線傳感器網(wǎng)絡(luò)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.