無線傳感器網絡LEACH分簇路由協議研究*

張 珉，王中訓，婁 陽，劉寶軍

（煙臺大學 光電信息科學技術學院，山東 煙臺 264005）

無線傳感器網絡LEACH分簇路由協議研究*

張 珉，王中訓，婁 陽，劉寶軍

（煙臺大學 光電信息科學技術學院，山東 煙臺 264005）

無線傳感器網絡是物聯網的重要支撐基礎技術之一，在國防民用各個方面有著廣泛應用。無線傳感器網絡由很多具有無線射頻功能的傳感器節點組成，是一種靈活、自適應性強的網絡。研究無線傳感器網絡中的分簇路由協議，分析LEACH協議的優缺點，指出問題所在，設計和改進的首要目的是延長網絡的生命周期，提高能量的利用率。因此，針對原LEACH協議存在的不足，在簇頭的選舉、特殊節點的處理以及簇間路由傳輸問題上分別進行改進，并利用MATLAB進行仿真，對比分析其與原協議在存活點個數、耗能、傳輸數據效率的性能，具有一定的實用價值。

無線傳感器網絡；分簇；路由協議；仿真

0　引 言

無線傳感器網絡（Wireless Sensor Networks，WSNs）是近年來炙手可熱的研究方向。因為該項技術在惡劣環境、無人值守、資源受限制等的特殊環境中具有十分卓越的表現性能，能夠客觀及時有效地獲得人們想要的物理信息，所以廣泛應用于譬如搶險救災、防空反恐、危險區域遠程控制、生物醫療、智能家居、城市管理、工農業控制、軍事國防等諸多領域。

無線傳感器網絡的拓撲結構不是一成不變的，并且網絡中每個節點的能量也是受限的且通常非常少，所以在無線傳感器網絡的諸多研究中，能夠連接所有傳感器節點且可以降低能耗的路由協議是其最關鍵的技術之一。結構上，WSN路由協議可分為平面協議和層次性協議。平面協議工作時需要維持較大的路由表，并不適合應用于大規模網絡；層次性協議又稱分布式協議或分簇性協議，如圖1所示，其較為經典的協議即本文將要討論的低功耗自適應集簇分層型協議[1]（Low Energy Adaptive Clustering Hierarchy，LEACH）。該協議是由MIT的Heinzelman等人與2000年提出的，由節點輪流擔任簇頭而達到能量盡可能均勻消耗的目的。但是，該協議也存在簇頭的分布不合理、能耗不均、單跳選擇等缺陷。W-LEACH[2]、T-LEACH、LEACHRA和LEACH-C等改進協議，對原LEACH協議在不同角度進行了不同改進[3]，但大部分算法選簇時仍沿用LEACH的分布式方法。

圖1　無線傳感器網絡分簇

1　LEACH協議分析研究

1.1LEACH協議概述

LEACH協議的核心是確定簇頭節點，為此提出“輪”（Round）的概念。每一個Round由簇的建立態和穩定態兩個狀態組成。每一輪開始都要重新確定簇頭的位置，然后簇頭廣播自己的位置和信息。普通節點接收到離自己最近的簇頭節點信息后加入。所有的簇頭和普通節點都已經確定時（實際應用時，并不是所有的頭都有下屬的普通節點，也不是所有的普通節點都能加入某一個簇頭），網絡開始進入穩定狀態，后再進入選舉狀態，依此周期性進行，直至系統所有能量都耗盡，系統死亡。

確定簇頭節點時，每個節點隨機生成一個[0,1]之間的數。若小于式（1）中的T(n)，則該節點就被選為簇頭節點，其余點則為普通節點。式（1）中，p是該網絡中簇頭節點與總節點的比例，r是當前選舉的輪數，G是在剩余1/p輪中普通節點的集合。

選定簇頭節點后，簇頭節點廣播告知整個網絡。網絡中的其他普通節點根據信號的強度決定自己從屬哪個簇頭節點，并告知簇頭節點，至此完成簇的建立。然后，簇頭用TDMA方式分配給每個下屬普通節點傳遞數據的時間點（發送時隙）。在穩定階段，簇頭對接收到的各個普通節點的數據進行融合，然后轉發至基站（Base Station，BS），整個過程如圖2所示。

圖2　LEACH運行過程

1.2LEACH協議的主要問題

LEACH協議提出時，相對整個物聯網和無線傳感器網絡的發展進度，非常具有前瞻性和創新性。LEACH協議相對其他平面節點，可以減少15%以上的能耗[1]。其后人們開始研究對LEACH協議的改進，提出了很多實用的改進方向。本文主要針對LEACH的以下問題進行研究和改進。

第一，實際應用中簇的劃分及其不平衡，有的簇過于龐大，有的反而只有一個節點，造成節點能量大量的浪費。文獻[4]指出，極小簇節點能耗相比極大簇節點高出20%左右，同時原協議對加入簇失敗的節點處置不夠合理。

第二，簇節點與基站通信是單路徑點對點傳輸，此時若簇頭與基站距離太遠，則需很大的發送功率[5]。同時，穩定階段若某簇頭因意外情況猝死，原LEACH協議是沒有備用簇頭節點的，則該簇內的普通節點仍會按照原先分配的時間進行通信，直至本輪結束，從而造成大量能量浪費。

第三，文獻[6]指出，簇頭節點與普通節點比例以1/19為佳，即5%比重時，系統效率最高。事實上，該比例是基于初始節點數目確定簇頭節點數目的，實際運行中經常有新節點加入或者已有節點死亡而引起的拓撲結構的變化。

2　對LEACH協議的綜合改進

2.1基本思想

基于原協議存在的問題，本文主要在以下方面進行改進：要對各個簇劃分規模，控制簇成員，控制最小簇或者等待時間超過限制直接與基站通信；首輪過后，要由基站節點選出下一輪簇頭，依據剩余能量、與基站位置距離、已當選次數和鄰居節點數目等，綜合選舉下一輪簇頭節點；特殊節點的處理更加科學；意外情況發生時，本文程序會自動啟用備用簇頭節點；最后，設置更科學合理的多跳簇間路由[7]等。

2.2一階無線電模型

圖3為一階無線電模型。本文工作中，假設一個簡單的模型的發送和接收信號，分別耗能Eelec=50 nJ/bit，發送放大器放大倍數為εamp=100 pJ/bit/m2，以得到可以接受的值。同時，假設在信道傳輸中有r2的能量損耗。因此，無線電模型在距離d發送k bit信息時，無線電擴展為：

同樣條件下，接收信息無線電擴展為：

圖3　一階無線電模型

由以上可知，接收信息功耗是不低的。因此，本文的路由協議應該不僅降低發送功率，還要去降低接收功率[1]。

2.3簇頭的選擇

首輪選舉，主要采用原協議的方法，并且引入ts等待時間、Tr每輪持續時間。當特殊節點等待時間ts＞Tr/2時，此節點直接與BS通信，以減少不必要的能量浪費[8]。通過首輪選舉，BS已經收集掌握了各個節點的當前信息，從第二輪開始，簇頭節點由BS分配，具體流程如圖4所示。

記Ecurrent(ni)為節點ni目前的剩余能量，dtoBS(ni)表示節點ni到基站的距離，N(ni)表示此節點上一輪同簇節點總數。同時，記節點ni在屬于簇ci時，被選為下輪簇頭的評估函數f(ni,ci)，則：

式中，fe、fd和fc分別用來考查剩余節點能量情況、與BS的遠近程度以及相鄰節點數。在提出的協議中，用上輪同簇節點數目來近似鄰居節點數。we、wd和wc是所考察指標的權重指數，具體取值可以根據網絡規模和應用情況來調整[9]。

同時，所提協議規定，簇頭選舉程序會選出一個備用簇頭節點。這樣當簇頭節點猝死時，備用簇頭節點還可以繼續代替它進行工作，不會讓簇內成員能量無謂損耗。

圖4　簇頭選擇流程

2.4簇間多跳通信

眾所周知，簇頭負責與BS之間的通信。然而，當簇頭離BS距離較遠時，簇頭會消耗很大的發送功率，從而造成簇頭節點能量過快消耗光。于是，提出解決方法：當簇頭離BS較遠時，采用多跳的路由，選擇最小的路徑，把數據傳輸給BS；而當距離很近時，簇頭直接與BS通信。目前，有很多最小能量路由協議，基本上在選擇路由的時候只考慮發送功耗，而忽略接收功耗。這里進行綜合考量，中間路由轉發節點必須使總能量消耗盡可能小，所以不僅要減少轉發距離，還要降低轉發次數[5]。

3　改進協議的MATLAB仿真

MATLAB是美國MathWorks公司出品的商業數學軟件，用于算法開發、數據可視化、數據分析以及數值計算的高級技術計算語言和交互式環境，在工程領域應用非常廣泛。本文將使用MATLAB 7.1仿真工具，對提出的改進協議進行仿真。設置仿真參數如表1所示[10]。

設置網絡運行3 000輪，100個節點具有相同的初始能量，分別對兩種協議進行仿真，死亡節點隨時間變化對比圖如圖5所示。

表1　仿真參數

圖5　LEACH和LEACH-Improvement的死亡節點隨時間變化對比

分析數據發現，原協議在第1～731輪都沒有出現死亡節點，所有的節點都是存活的，直至第732輪，出現了第一個死亡節點，其后死亡節點急劇增加，至第1 220輪所有節點都死亡，整個網絡死亡；而LEACH-Improvement在第1～783輪都沒有死亡節點，所有的節點都是存活的，直至第784輪出現了第一個死亡節點，其后死亡節點同樣急劇增加，但存活節點數始終大于原協議，死亡節點數一直少于原協議，至第1 560輪所有節點死亡，整個網絡死亡。通過曲線對比可以很直觀地發現，LEACH-Improvement在存活上的表現比原協議好。

如圖6所示，在網絡吞吐量上，原協議BS首輪接收6單位數據，此后隨著輪數的增加，接收數據緩慢增加，直至所有節點死亡，BS接收到9 925單位數據；而LEACH-Improvement的BS首輪接收18單位數據，其后快速增長，直至節點全部死亡共接收到25 454單位數據，整個生命周期始終保持比原協議高的數據量。可見，改進后的協議在時間上的效率相對原協議高。

在網絡消耗上，如圖7所示。在前500輪，兩個協議的消耗大體無異。500輪之后，原協議的網絡消耗急劇增加，至所有節點死亡，共消耗50.14 J能量；而LEACH-Improvement協議在500輪之后耗能增加，至所有節點死亡，共耗能50.07 J。在能耗方面，原協議比改進協議耗能更快，改進協議比原協議更加節能，能量消耗速度更緩慢。

圖6　LEACH和LEACH-Improvement的數據傳輸對比

圖7　LEACH和LEACH-Improvement的網絡消耗對比

4　結 語

無線傳感器網絡分簇算法采用輪換的節點作為簇頭方式來平衡整個傳感器網絡的負載和能量，但隨機選擇簇頭的方式和單跳的簇間路由有時會造成能源的大量浪費。針對這些問題，本文逐一進行逐改進。在簇頭選擇上，參考更多的節點客觀參數。仿真發現，在100個節點上，改進算法在生存期、能耗、效率上，均有一定的提高。但同時發現，本改進算法在更大規模網絡上（如300枚節點）的應用效果并不理想，因為對網絡進行的一些細節改進使得自適應性被削弱；BS在確定簇頭時會產生更多簇間路由。鑒于此，下一步在解決以上問題的同時，會在選舉函數參數上做更多的研究。

[1] Heinzelman W R,Chandrakasan A,Balakrishnan H．Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C].Proceedings of the 33rd Annual Hawaii International Conference on System Sciences:Piscataway,2000:175-187．

[2] Sharma I,Singh R,Khurana M.Comparative Study of LEACH,LEACH-C and PEGASIS Routing Protocols for Wireless Sensor Network[C].IEEE Computer Engineering and Applications,2015:1-15.

[3] Sony C T,Sangeetha C P,Suriyakala C D.Multi-hop LEACH Protocol with Modified Cluster Head Selection and TDMA Schedule for Wireless Sensor Networks[C].IEEE Communication Technologies(GCCT),2015:539-543.

[4] 呂濤,朱清新,張路橋.一種基于LEACH協議的改進算法[J].電子學報,2011,39(06):1405-1409. LV Tao,ZHU Qing-xin,ZHANG Lu-qiao.An Improved Algorithm based on LEACH Protocol[J].Journal of Electr onics,2011,39(06):1405-1409.

[5] Omari M,Fateh W H.Enhancing Multihop Routing Protocols in Wireless Sensor Networks Using LEACH-1R[C].Web Applications and Networking(WSWAN),2015 2nd World Symposium on IEEE,2015:1-6.

[6] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An Application-specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communications,2002,1(04):660-670.

[7] 陳炳才,么華卓,楊明川等.一種基于LEACH協議改進的簇間多跳路由協議[J].傳感技術學報,2014(03):373-377. CHEN Bing-cai,YAO Hua-zhuo,YANG Ming-chuan,et al.An Improved Inter Cluster Multi Hop Routing Protocol based on LEACH Protocol[J].Journal of Sensing Technology,2014(03):373-377.

[8] 陳慧杰,韓江洪,劉磊.無線傳感器網絡中自然能收集分簇路由算法研究[J].計算機工程,2016,42(03):143-147. CHEN Hui-jie,HAN Jiang-hong,LIU Lei.Research on Clustering Routing Algorithm in Wireless Sensor Networks[J].Computer Engineering,2016,42(03):143-147.

[9] 馬建樂,楊軍.基于位置和剩余能量的局部集中式LEACH算法研究[J].傳感技術學報,2013(08):1147-1151. MA Jian-le,YANG Jun.Local Centralized LEACH Algorithm based on Position and Residual Energy[J].Journal of Sensing Technology,2013(08):1147-1151.

[10] 陳曉娟,王卓,吳潔.一種基于LEACH的改進WSN路由算法[J].傳感技術學報,2013,26(01):116-121. CHEN Xiao-juan,WANG Zhuo,WU Jie.An Improved WSN Routing Algorithm based on LEACH[J].Journal of Sensing Technology,2013,26(01):116-121.

張 珉（1991—），男，碩士研究生，主要研究方向為物聯網通信、無線傳感器網絡仿真等；

王中訓（1965—），男，博士，教授，碩士研究生導師，主要研究方向為LDPC編碼以及水下通信；

婁 陽（1990—），男，碩士研究生，主要研究方向為LDPC碼混沌加密技術；

劉寶軍（1991—），男，碩士研究生，主要研究方向為LDPC碼和FPGA仿真技術。

LEACH Clustering Routing Protocol for Wireless Sensor Networks

ZHANG Min, WANG Zhong-xun, LOU Yang, LIU Bao-jun
(Institute of Science and Technology for Opto-Electronics Information, Yantai University, Yantai Shandong 264005, China)

Wireless sensor network ,as one of the important supporting technologies for IOT (Internet of things), is now widely used in the defense and civilian fields. Wireless sensor network,composed of many sensor nodes with wireless radio frequency function, is also a very flexible and adaptive network, and its routing protocol is extremely important. The cluster routing protocol in wireless sensor network is discussed, the advantage and disadvantage of LEACH protocol analyzed, and the problem pointed out. The primary purpose of design and modification lies in extending life cycle of the network, improving the utilization rate of energy. Aiming at the problems existing in the original LEACH protocol, the selection of cluster head, the processing of special node and the routing of between the clusters are improved.Simulation with MATLAB and comparison with the original LEACH in the number of survival points, the energy consumption and the efficiency of data transmission indicate that this modification is feasible and of certain practical value.

wireless sensor network; clustering; LEACH; simulation

Science and Technology Development Project of Shandong Province（No.2012J0030009）

TN212

A

1002-0802(2016)-08-01023-06

10.3969/j.issn.1002-0802.2016.08.013

2016-04-21;

2016-07-21

date:2016-04-21;Revised date:2016-07-21

山東省科技發展計劃項目（No.2012J0030009）