基于扇形分簇的無線傳感器網絡路由算法

孔國利　蘇玉

摘 要： 無線傳感網絡中低功耗自適應聚類分簇（LEACH）路由算法等概率選取簇首節點，容易導致整個網絡節點能量損耗出現極端化，減少網絡生存時間。為此，提出一種針對簇首節點選取和分簇的改進LEACH算法。該算法把整個網絡區域分為四個扇形區域，在每個區域內獨立進行分簇路由；然后基站根據節點剩余能量和與基站的距離進行簇首節點選擇，節點根據簇首節點和基站接收信號強度選擇路由方式，以均衡網絡能量消耗。仿真結果表明，改進LEACH算法的網絡壽命是原有LEACH算法的150%，數據吞吐量提升了3倍。

關鍵詞： 無線傳感器網絡； 能量均衡； 扇形分簇； 簇首； 路由算法

中圖分類號： TN915?34； TP393.2 文獻標識碼： A 文章編號： 1004?373X（2017）05?0014?05

Abstract： The low energy adaptive clustering hierarchy （LEACH） routing algorithm for wireless sensor network selects the cluster head node by means of equal probability， which is easy to result in the extreme energy loss of the whole network nodes， and reduce the network lifetime. Therefore， an improved LEACH algorithm for the selection and clustering of the cluster head node is proposed. The whole network area is divided into four fan?shaped subareas with the algorithm to perform the clustering routing in each subarea independently. The cluster head node of the base station is selected according to the node residual energy and distance to the base station. The routing mode of the node is selected according to the cluster head node and the received signal strength of the base station to balance the network energy consumption. The simulation results show that the network lifetime of the improved LEACH algorithm is 150% of the original LEACH algorithm， and its data throughout is increased by three times.

Keywords： wireless sensor network； energy balance； fan?shaped clustering； cluster head； routing algorithm

0 引 言

無線傳感網絡是由分布式部署的微型傳感器節點組成的自組織網絡，其節點數量巨大，部署區域和環境復雜，被廣泛應用于實時車輛監控、智能家居、森林防火防災等方面。其中，傳感器節點體積微小，配置的電池能量、計算能力和存儲能力有限，因此，如何均衡網絡能耗，提升網絡生存時間是合理有效設計無線傳感網絡的重要課題[1?2]。一般來說，無線傳感器網絡的路由算法應該具有能量優先，基于局部的拓撲結構，以數據為中心的特點。現在國內外已經提出了很多經典的無線傳感器網絡路由算法，有以數據中心為主的[3]，有以數據傳輸質量為主的[4]，有以節點地理位置信息為主的[5]等，其中以網絡構成的結構劃分的，分為平面路由算法和分層路由算法。分層路由最經典的算法為LEACH（Low Energy Adaptive Clustering Hierarchy）算法。LEACH算法在數據匯聚、拓撲適應和能量效率方面具有明顯的優勢。

現有大量文獻對LEACH算法進行改進，以提升其性能。文獻[5]提出并對比了三種通過把節點自身的位置坐標和當前能量狀況匯報給基站，基站根據這些因素選取簇首的方法，但對于地理位置的獲取會消耗很大能量，同時沒有考慮到鏈首個數占整體節點總數的比例，導致不均衡。文獻[6]提出了簇首多跳算法，使得簇首之間形成一個多跳的最優路徑，減少簇首的能量消耗，但是延長了路徑，從而使數據傳輸過程加長，時效性變弱。文獻[7]提出引入簇成員數門限和合并極小簇的方法，首先估計簇首能量消耗的情況，然后人為的控制節點休眠的狀況來配合簇首消息的傳送，雖然能量消耗方面得到改善，但是在時效性方面沒有充分考慮。文獻[8]考慮節點剩余能量和通信半徑，選擇簇首節點以減少整個傳感網絡中簇首節點的數目，延長網絡整體壽命。

本文考慮到能量消耗均衡性，網絡壽命長短因素，提出基于扇形分簇的路由算法，縮小分簇范圍進行通信。然后，根據剩余能量、通信距離選取簇首節點，均衡能量消耗，延長網絡壽命。

1 系統模型

LEACH示意圖如圖1所示，假定其覆蓋一定區域的無線傳感網絡，并且有以下假設[9]：

假設1：基站與整個網絡的位置保持不變，基站與整個網絡中的節點距離較遠。

假設2：每個節點有著同樣性質、有限的能量、與基站直接通信的特性。

假設3：節點計算能力較強，支持TDMA。

假設4：WSN節點發送信息的功率可以變化、調整。

節點間的數據通信采用一階無線電模型（First Order Radio Model），通信模型如圖2所示。

這種通信模式有比較成熟的能量消耗計算體系。該模型假設WSN節點有著相同的計算能力，有限的能量；電信號在不同方向上的路徑損耗一樣。當傳輸長為m bit的信息經過距離[d]的過程中，節點的能量消耗如下：

數據發送：

[ETx（m，d）=Eelec?m+εfs?m?d2， d

數據接收：

[ERx=Eelec] （2）

數據融合：

[EGx=Eg?m] （3）

式中：[εfs]是信號放大器的放大倍數；[Eelec]是發送和接收信息時對應的數據處理模塊消耗的能量。由于傳感器節點間距離不同，傳播環境迥異，因此，傳播相同數據量的能量消耗不同。式（1）中不同的能量消耗表征不同傳播距離和傳播環境對能量消耗的影響。其中，[d]是數據通信的距離；[d0]是節點的通信半徑；[εmp]是信道傳輸能量衰減系數，通信傳輸距離越短，能量消耗越少。

2 LEACH算法流程

LEACH算法將傳感器節點分為若干個簇，每個簇內節點的信息匯聚至簇首節點后，由簇首節點轉發至基站。匯聚轉發的工作方式能夠提升LEACH算法的能量效率。此外，由于簇首節點的能量消耗較大，各個節點根據剩余能量狀況輪流擔任簇首節點，提升網絡整體壽命[10]。

LEACH算法以循環也就是“輪（round）”的方式執行簇的構造過程。每輪都由兩階段組成：初始化簇的建立階段和數據傳輸階段，具體時序示意圖如圖3所示。

2.1 初始化簇階段

初始化簇階段分為簇首選取和成簇過程兩個步驟。

Step1：簇首選取。網絡中所有的節點會隨機產生一個在0～1之間的數，網絡會設定一個門限值[T（n）]如式（4）所示，基站會把節點產生的隨機數與設定的門限[T（n）]進行比較，會選擇小于[T（n）]的節點作為簇首。

[T（n）=Q1-Q?（lmod1Q） ， n∈G0， otherwise] （4）

式中：[Q]為每輪簇首節點與[n]個節點的比率；[l]為第[l]輪；[G]為在之前的幾輪中沒有被選為簇首節點的總和。

Step2：成簇過程。節點被選為簇首后會向其他所有節點廣播自己被選為簇首的消息。其他節點在接收到消息之后，根據最小能量的原則通過比較，判斷發送這些消息的節點的功率大小來選擇加入到相應的簇。一般節點會選擇接收到的功率越大的簇首節點形成的簇；然后發送自己要加入相應簇的消息給相應的簇首節點。簇首節點收到消息后會給節點一個回應，并將該節點加入自己的路由表中。

2.2 數據發送和接收

當所有傳感器節點都形成簇之后，節點間采用TDMA方式發送數據。各個節點的數據在簇頭節點處融合，然后由簇頭節點轉發給基站。一個簇分配方案維持數據通信一段時間后，重新進行下一輪的簇分配，以避免對簇首節點的能量過度消耗，提升網絡整體壽命。

3 改進LEACH算法原理

從LEACH算法中可知，以輪的方式等概率的選取簇首，并沒有考慮剩余能量的因素。對于剩余能量不同的節點當選簇首的幾率是一樣的。如果剩余能量偏低的節點被選為簇首，很容易耗盡能量，降低整個網絡的壽命。此外，在LEACH算法中，節點根據接收信號的強度來選擇簇首。若該節點距離簇首節點較遠，路徑損耗較高[11]，因此，節點能量會過早消耗而死亡，導致網絡的通信出現黑洞。

針對這些缺點，綜合考慮節點的能量和整個網絡信息傳輸的及時性，本文在基于LEACH算法的基礎上提出了改進LEACH算法。該算法把整個網絡劃分為四個扇形分區；基站在每個扇形分區中通過比較每個節點產生的隨機數和節點的剩余能量選擇簇首，接著基站公布簇首的消息，節點根據接收到的該區域的消息強度、與簇首和基站的距離比較選擇加入簇還是選擇直接與基站進行通信。

3.1 扇形結構模型

由于覆蓋區域為圓形時，傳感器節點間的最大距離比覆蓋區域為其他形狀時要小，本文假定圓形覆蓋區域，基站位于圓形覆蓋區域中心。同時，為了進一步縮小節點間的最大距離，同時減少由于網絡中節點死亡而重新分簇帶來的通信開銷，改進LEACH算法將圓形覆蓋區域分為4個扇區，如圖4所示。在每個扇區內，分別進行LEACH算法路由。選定某個參考點后，4個扇區分別記為扇區編號num={1，2，3，4}，圓心角[θ=π2。]

3.2 扇區編號確定

劃分好區域后，所有傳感器節點進行分簇時需要確定每個節點所在的扇區編號及在扇區的具體位置，方法如下：

（1） 計算節點的極坐標角度。所有的節點需要將自己的位置信息與ID信息發送給基站，基站根據正切函數特征進行計算。把圓放到直角坐標系中，圓心[O]的坐標為（0，0），設任意一個點[i]的坐標為[（x（i），y（i）），]如圖5所示。

（2） 確定節點所在區域。將節點[i]對應的角度[α]與圓心角[θ]相除，得到整數[k（i），]比較[k（i）]與已經劃分好區域的編號[num（n），]獲得節點[i]所在的區域編號[k（i），]即：

所有節點的極坐標角度和扇區編號構成一個矩陣，記為Loc，其中，[Loc=（i）={a（i），k（i）}。]

3.3 簇首選取

改進LEACH算法同時考慮通信距離和節點剩余能量來選擇簇首節點，并且在每一輪都會進行選取，流程圖如圖6所示。

簇首節點選擇過程分為兩步：

Step1：先按照LEACH算法機制，比較每個節點產生的隨機數與網絡給定的閾值[T（n），]在低于閾值的節點中選擇簇首節點。

Step2：在第一步選擇的節點中，綜合考慮節點的能量和與基站的距離，進行簇首節點選擇。具體選擇的準則為：

[Q=Edis] （9）

式中：[E]為節點的剩余能量；dis為節點與基站之間的距離。由式（1）可以看出，距離dis也與[Q]成反比，距離基站越遠的節點消耗的能量更大，因此該點被選為簇頭的幾率也比較小。

綜上所述，剩余能量越多，離基站距離越近的節點成為最終簇首節點的概率越大。

3.4 分簇通信過程

當簇首節點選定以后，基站會向各個扇區廣播相應區域簇首節點的消息。各個扇區內對應的節點知道自己為簇首后，就會在自己的覆蓋區域內發布自己是簇首的消息。各個扇區的普通節點會根據自己接收到的來自簇首的信息和接收到來自基站的信息強度和相應的距離判斷是選擇加入簇還是直接與基站進行通信。當選擇加入簇后，會給相應的簇首發送消息，同時簇首也會相應的給回應。對于不加入簇中的節點，就只會把測量的消息直接發送給基站，流程圖如圖7所示。

在每輪傳輸數據時，各個區域簇內的節點會把測量到的信息數據發送到相應的簇首，簇首節點傳送到基站，而簇外的節點會把消息直接傳輸給基站。當節點為普通節點或者是簇外節點時，能量消耗只包括節點將數據發送的能量；當節點為簇首節點時，能量消耗為節點接收、融合以及發送數據的能量總和。

4 仿真結果分析

為了評估改進LEACH算法的性能，使用Matlab進行仿真，重點分析經過一定輪數網絡節點的死亡個數和網絡傳輸數據的情況[12]。假定基站固定且位于監測區域的最中心，遠離傳感器節點；所有的節點計算能力和能量容量一樣；節點具有與其他節點和基站進行通信的能力；節點的位置固定不動。同時對比了原有的兩種改進算法LEACH1，LEACH2。其中，LEACH1是由文獻[13]提出的只針對簇首選取改進的算法，采用粒子群算法進行分區，分別在各個區域通過節點剩余能量選取簇首的方法。LEACH2是文獻[14]提出的結合LEACH與PEGASIS的改進算法，通過對節點分區分簇，把不同簇的簇首連成鏈進行通信的方法。

仿真中假定基站坐標為（0，0），數據包的長度為3 000 b，控制包的長度較小，可以忽略不計，其他的實驗參數設置如表1所示。

首先對兩種原有算法和LEACH算法在不同輪數死亡節點總數的統計進行比較，具體顯示結果如圖8所示。

從圖8可以看出，當運行到500輪左右時，四種算法都出現了節點開始死亡的現象。LEACH和LEACH2算法的節點死亡速度比較快。經過1 500輪左右，使用這兩種算法的無線傳感網絡節點死亡率達到最大限度。到將近2 000輪左右時，兩種算法的節點死亡速度接近平緩，并將近全部死亡。這是由于這兩種算法沒有考慮節點剩余能量的影響，導致部分節點過早死亡。而改進LEACH算法和LEACH1算法的節點死亡狀況在一開始比較平緩，到1 300輪左右時速度變快，但都沒有LEACH快，并且在LEACH接近死亡時，改進算法中還存活將近20個節點。可以看出，改進算法比原有算法更好地延長了網絡壽命，并且比LEACH算法在節點存活概率方面提升了20%，節約了能量的消耗，延長了網絡的生命周期。

幾種算法數據傳輸性能的比較如圖9所示。

由圖9可知，隨著輪數的增大，四種算法數據傳輸的量都在增加，并且改進LEACH算法與原有算法的數據傳輸差距也隨之增大，當到1 000輪左右時，改進算法的數據傳輸量是LEACH算法的3倍。LEACH算法和改進算法LEACH2在1 500輪左右時，數據傳輸量的增加趨于穩定，而改進算法和另外一種算法LEACH1的數據傳輸量一直在快速增加，當到2 000輪左右時，LEACH和LEACH2算法已經達到了最大數據傳輸量，而改進算法的數據傳輸量還在增加，并且將要達到LEACH算法的4倍，明顯提高了數據傳輸效率。因此，本文提出的改進算法通過合理使用節點能量，能夠提高網絡有效數據的傳輸量。

5 結 語

本文綜合考慮了扇形分區和節點剩余能量，對LEACH算法進行改進。仿真結果表明，改進LEACH算法能夠提升約150%的網絡壽命，同時能夠傳輸4倍于對比算法的數據量；該算法在均衡了能量消耗的同時還增強了網絡接收數據信息的及時性，提高了網絡的利用率，增加了網絡生存時間。

參考文獻

[1] 蘇儉華，劉宇紅，徐躍州.一種基于LEACH的無線傳感器網絡路由算法及仿真[J].通信技術，2014，47（1）：60?63.

[2] MAMUN Q. A qualitative comparison of different logical topologies for wireless sensor networks [J]. Sensors， 2012， 12（11）： 14887?14913.

[3] 任克強，余建華，謝斌.基于改進LEACH的多簇頭分簇路由算法[J].電視技術，2015，39（13）：69?71.

[4] MCBRIDE D， CROFT T N， CROSS M， et al. Optimization of a CFD： heap leach model and sensitivity analysis of process operation [J]. Minerals engineering， 2014， 63（8）： 57?64.

[5] 周萌，陳躍東，陳孟元.能耗最優的LEACH協議改進[J].計算機工程與應用，2014，50（23）：82?86.

[6] GOETZ E R， RIEFLER R G. Performance of steel slag leach beds in acid mine drainage treatment [J]. Chemical engineering journal， 2014， 240（6）： 579?588.

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

[8] HU Songhua， HAN Jianghong， WEI Xing， et al. A multi?hop heterogeneous cluster?based optimization algorithm for wireless sensor networks [J]. Wireless networks， 2015， 21（1）： 57?65.

[9] 王夢瑩，王鑫，蔣華.基于簇首成鏈的低能耗層次路由協議[J].計算機科學，2015，42（11）：144?148.

[10] 蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網絡非均勻分簇路由協議[J].軟件學報，2012，23（5）：1222?1232.

[11] 吉正洵，江冰，李麗芳，等.采用改進算法對無線網絡節能優化仿真研究[J].計算機仿真，2015，32（6）：266?270.

[12] 張巖.非變換簇的WSN分簇路由算法[J].現代電子技術，2015，38（18）：26?29.

[13] YANG Y， WANG X， WANG M， et al. Recovery of iron from red mud by selective leach with oxalic acid [J]. Hydrometallurgy， 2015， 157： 239?245.

[14] 王鑫，王夢瑩，蔣華.一種基于簇首成鏈的分層分簇路由協議[J].微電子學與計算機，2014（10）：9?12.