有輔助基站的LEACH改進路由算法

摘要：LEACH算法是經典的無線傳感器網絡層次路由算法。但算法存在分簇大小變化劇烈、節點能耗不均勻的缺點。為解決上述問題，本文提出了一種增加中轉基站的LEACH改進路由算法。該算法通過一定的中轉節點部署策略，來提升網絡的吞吐量和生命周期。通過仿真實驗生命，該算法能有效地提高網絡各方面的表現。

關鍵詞：無線傳感器網絡；路由算法；輔助基站

1.無線傳感器網絡及路由算法簡介

無線傳感器網絡（WSNs）是由一定數量的傳感器節點，隨機自組織地分布在一起[1]，通過單個節點的感知和存儲能量，加之節點之間的通信來完成一定任務的網絡結構。目前，WSNs已經被廣泛應用于諸如軍事探測、農業應用、環境監測及輔助醫療等眾多領域，發揮著十分重要的作用。

傳感器節點通常由傳感器單元、處理器單元、存儲單元和無線收發單元組成，這些單元都需要采用體積較小的電池作為能量來源。而在大多數的應用場景下，無線傳感器一旦被部署之后，就基本不再進行修改，同時在某些特殊場景下對其進行修改也是不現實的，例如在某些環境監測的應用中，網絡一旦部署就會長期工作在環境惡劣的地帶[2]，不方便被修改。因此，網絡節點的能耗是傳感器網絡路由算法要解決的首要問題。

目前已有的無線傳感器網絡路由算法主要分為兩大類：平面路由算法和層次路由算法。而目前公認的最有效的路由算法都屬于層次路由算法。層次路由算法是通過一定的方式將網絡中的節點分成簇，每個節點都從屬于一個簇，簇內節點將采集的數據首先發送給簇頭節點，再由簇頭節點發送給基站節點。由Heinzelman W等提出的LEACH算法就是最經典的層次路由算法。

2.LEACH算法簡介

LEACH算法是周期性運行的，每一輪次都進行一次簇首選舉、選擇入簇和信息傳輸。

2.1簇首選舉

每一輪次開始時，每個節點會產生一個[0，1]上的隨機數，并計算一個屬于自己當前輪次的閾值T（i），并當t

2.2簇的建立

當一輪內簇首節點選擇完畢之后，當選為簇首的節點向其周圍的節點廣播自己成為簇首的消息，該消息包含節點的編號和所在位置，其他沒有成為簇首的節點在接收到簇首發來的通知消息時，根據自己與所有簇首節點之間的距離來選擇最近的簇首加入，成為該簇首的成員。

2.3數據傳輸階段

當所有的簇已經建立完成后，網絡進入穩定傳輸階段，各個節點發送消息到自己的簇首節點，并通過無線發送模塊發送給基站。普通節點會按照簇首節點頒發的TDMA時隙表發送數據，即在時隙表中查詢到自己的時隙并在相應的時隙之內發送數據。

由于簇首節點要擔任收發數據和融合數據的工作，因此會產生更大量的能耗，LEACH算法通過隨機機制，保證了各個節點在一定程度上公平地成為簇首，平均了網絡能耗。但LEACH算法只考慮了在節點擔任簇首次數上的公平性，忽略了節點地理位置造成的不公平性。某些節點始終距離基站節點較遠，當這些節點當選為簇首時其發送消息到基站的能耗會指數增加，這也導致LEACH算法下的網絡那些距離基站較遠的節點經常會過早死亡，進而影響整個網絡的表現。

3.基站輔助的LEACH改進算法

針對第2小節提出的LEACH算法的不足，本文提出了一種增加輔助基站的方法來延長網絡生命周期的改進LEACH算法。輔助基站是一種功率更大，能量更充足，甚至可以進行能量補充的節點，消息通過這樣的節點進行轉發可以大大減少傳感器節點的能耗。該算法主要由3個階段的工作：LEACH算法運行階段，統計成簇情況并設置輔助基站階段，輔助基站介入的運行階段。

3.1 LEACH算法的運行階段。

算法的第一階段和經典LEACH算法相同，首先網絡在前輪運行經典LEACH算法，但在每一輪結束時，由網絡中的基站節點記錄該輪次有哪些節點當選為簇首，并保留成簇的情況。

3.3輔助基站介入的運行階段

算法繼續采用LEACH算法運行，所不同的是在數據傳輸階段，各個簇首節點在接收了簇內節點的數據后，轉發給距離自己最近的輔助基站，輔助基站將數據進行融合之后再發送給網絡基站，從而完成了數據采集的工作。

算法共運行2000輪次，其中前500輪次是LEACH算法運行階段。

首先，通過實驗來驗證了兩種算法在節點生命周期方面的表現，由于本文的算法加入了可以補充能量的輔助基站，在一定程度上減輕了傳感器節點的工作負擔，在500輪次的LEACH算法運行之后，本文的算法推遲了第一個死亡節點出現的輪次，LEACH算法在第600輪次左右出現了第一個死亡節點，而本文的算法在700輪次左右才出現第一個死亡節點。同時可以看出，本文算法下節點的死亡速率明顯低于LEACH算法，如果網絡以40%的節點存活數作為網絡正常運行的標準，則本文算法下網絡的正常工作比LEACH算法下的正常工作多200輪次左右。即，當存活節點數為40的時候，LEACH算法運行到1200輪次，而本文算法則持續運行到1400輪次。

其次，我們做了網絡剩余能量方面的對比，在500輪次之前，由于兩種算法都采用了LEACH的運行策略，其能耗速度基本一致，曲線重合。而當500輪次之后，由于本文加入了基站輔助策略，使用基站的可補充能量來代替節點的不可補充能量進行消耗，有效地保護了傳感器節點的能量，所以本文算法下的能耗速率明顯低于LEACH算法。LEACH算法在1300輪次時，總能量基本降為0，而本文算法的能量一直持續到1900輪次。

最后，我們對比了兩種算法下每一個節點的剩余能量，LEACH算法在第1500輪次時還有一些存活節點，但其剩余能量值相差較多，多的節點可以達到0.42焦耳，而少的節點只有0.0013，其剩余能量少的節點是距離基站較遠的節點，而本文算法下存活節點的剩余能量值基本平衡在0.13～0.15焦耳之間。這是由于輔助基站的介入，可以減輕偏遠節點的數據收發能耗，避免了其能耗速度過快的情況，從而達到了節點之間能耗均衡的目的。

5.總結

本文設計了一種無線傳感器網絡路由算法，該算法針對經典LEACH算法在能耗速度和均衡方面的不足做出了一定的改進，通過引入輔助基站的方式，減輕了網絡中傳感器節點，尤其是偏遠節點的能耗壓力，平衡了節點的能耗表現。最后，通過仿真實驗的方式驗證了本文算法的有效性。

參考文獻

[1]葉繼華，王文，江愛文.一種基于LEACH的異構WSN能量均衡成簇協議[J].傳感器技術學報，2015，28（12）：1853-1860.

[2]康琳，董增壽. 基于簇頭分級的改進非均勻分簇算法[J].傳感技術學報，2015，28（12）：1841-1844.

劉永超，張月霞，繆旻. 基于能量和距離的分區域選擇簇首 WSNs 路由算法[J]. 傳感器與微系統，2015，34（1）：124-127.