LEACH路由協(xié)議分析 - 基于最小能耗的無線傳感器網(wǎng)絡路由算法

　　最早的分簇路由協(xié)議是由Wendi等三人在2000年提出的LEACH算法，全稱為“低功耗自適應集簇分層型協(xié)議”。LEACH算法的每一輪操作分為兩個運行階段：簇建立階段和簇穩(wěn)定運行階段。由于簇建立階段是屬于額外的通信需求，所以穩(wěn)定運行的持續(xù)時間要遠大于建立階段持續(xù)的時間。

　　在簇建立階段，傳感器節(jié)點隨機生成一個0，1之間的隨機數(shù)，并且與閾值T(n)做比較，如果小于該閾值，則該節(jié)點就會當選為簇首。T(n)按照下面公式計算：

?

　　式中：P為節(jié)點成為簇首節(jié)點的百分數(shù);r為當前輪數(shù);G為在這一輪中未當選簇首的節(jié)點集合。

　　簇首節(jié)點選定后，廣播自己成為簇首的消息，節(jié)點根據(jù)接收到的消息的強度決定加入哪個簇，并告知相應的簇首，完成簇的建立過程。然后，簇首節(jié)點采用TDMA的方式，為簇內(nèi)成員分配傳送數(shù)據(jù)的時隙。以上LEACH算法存在一個很大的缺陷，即協(xié)議沒有說明蔟首節(jié)點的數(shù)目怎么分布才能遍及于整個網(wǎng)絡。因此，很可能出現(xiàn)被選的簇首節(jié)點集中在網(wǎng)絡某一區(qū)域的現(xiàn)象，這樣就會使得一些節(jié)點的周圍沒有任何簇首節(jié)點。同時，由于簇首節(jié)點是隨機選擇的，有可能出現(xiàn)某個節(jié)點剩余能量過低而不能成為簇首節(jié)點，從而導致網(wǎng)絡失效。

　　2 基于最小能耗的無線傳感器網(wǎng)絡路由算法

　　2.1 算法拓撲結(jié)構(gòu)

　　圖3所示為無線傳感器網(wǎng)絡路由算法的拓撲結(jié)構(gòu)。整個網(wǎng)絡的節(jié)點被分為匯聚節(jié)點、簇首節(jié)點和普通節(jié)點。網(wǎng)絡由若干個子區(qū)域組成，子區(qū)域自主產(chǎn)生簇首節(jié)點，區(qū)域內(nèi)的其他節(jié)點和簇首節(jié)點通信并通過簇首節(jié)點將數(shù)據(jù)傳輸給匯聚節(jié)點。

?

　　2.2 算法描述

　　為了改進上述LEACH算法存在的缺點，本文采用了以下方法：網(wǎng)絡開始運行時，首先通過類似文獻中的擴散法將整個網(wǎng)絡劃分為若干個子區(qū)域，然后再在各個子區(qū)域內(nèi)隨機選取簇首節(jié)點，這樣可以保證簇首節(jié)點更加均勻地分布在整個網(wǎng)絡中。同時，設定節(jié)點剩余能量閾值Eth，每次選取簇首節(jié)點之前，對剩余能量低于閾值的節(jié)點采取休眠處理。這樣保證了簇首節(jié)點選取的可用性，有效地提高了網(wǎng)絡的生存時間。圖4為簇首節(jié)點形成流程圖。網(wǎng)絡開始運行時，依然將節(jié)點工作時間按周期劃分為簇首節(jié)點建立階段t1和穩(wěn)定運行時間t2。t1階段網(wǎng)絡首先在各個子區(qū)域內(nèi)隨機產(chǎn)生簇首節(jié)點，新簇首節(jié)點產(chǎn)生后廣播告知整個網(wǎng)絡。此時，普通節(jié)點在接收到信息后開始發(fā)送入簇信息，簇首節(jié)點則為其分配通信時隙。圖5為整個算法的流程圖，在建立新的簇首節(jié)點和傳輸網(wǎng)絡后，簇內(nèi)節(jié)點開始將數(shù)據(jù)信息發(fā)送給簇首節(jié)點，并在其內(nèi)部進行數(shù)據(jù)融合后轉(zhuǎn)發(fā)給匯聚節(jié)點，網(wǎng)絡開始穩(wěn)定運行。經(jīng)過t2后，網(wǎng)絡開始重新選取簇首節(jié)點，此時要注意，每個節(jié)點都將判斷自己的剩余能量，對低于閾值的采取休眠處理并廣播告知其他節(jié)點。

?

　　3 結(jié)語

　　在分析LEACH算法和無線傳感器網(wǎng)絡的能量模型的基礎上，本文提出了一種改進算法。在隨機選取簇首節(jié)點之前，首先把網(wǎng)絡劃分為若干個子區(qū)域，這樣可以將簇首節(jié)點分步得更加均勻，同時設定剩余能量閾值Eth，在每次選取簇首節(jié)點之前對剩余能量低于Eth的節(jié)點進行休眠處理，有效地提升了整個網(wǎng)絡的生命周期。