無線傳感器網(wǎng)絡(luò)LEACH分簇路由協(xié)議研究*

張 珉，王中訓(xùn)，婁 陽，劉寶軍

（煙臺大學(xué) 光電信息科學(xué)技術(shù)學(xué)院，山東 煙臺 264005）

無線傳感器網(wǎng)絡(luò)LEACH分簇路由協(xié)議研究*

張 珉，王中訓(xùn)，婁 陽，劉寶軍

（煙臺大學(xué) 光電信息科學(xué)技術(shù)學(xué)院，山東 煙臺 264005）

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

無線傳感器網(wǎng)絡(luò)；分簇；路由協(xié)議；仿真

0　引 言

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

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

圖1　無線傳感器網(wǎng)絡(luò)分簇

1　LEACH協(xié)議分析研究

1.1LEACH協(xié)議概述

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

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

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

圖2　LEACH運行過程

1.2LEACH協(xié)議的主要問題

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

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

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

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

2　對LEACH協(xié)議的綜合改進

2.1基本思想

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

2.2一階無線電模型

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

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

圖3　一階無線電模型

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

2.3簇頭的選擇

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

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

式中，fe、fd和fc分別用來考查剩余節(jié)點能量情況、與BS的遠近程度以及相鄰節(jié)點數(shù)。在提出的協(xié)議中，用上輪同簇節(jié)點數(shù)目來近似鄰居節(jié)點數(shù)。we、wd和wc是所考察指標的權(quán)重指數(shù)，具體取值可以根據(jù)網(wǎng)絡(luò)規(guī)模和應(yīng)用情況來調(diào)整[9]。

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

圖4　簇頭選擇流程

2.4簇間多跳通信

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

3　改進協(xié)議的MATLAB仿真

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

設(shè)置網(wǎng)絡(luò)運行3 000輪，100個節(jié)點具有相同的初始能量，分別對兩種協(xié)議進行仿真，死亡節(jié)點隨時間變化對比圖如圖5所示。

表1　仿真參數(shù)

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

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

如圖6所示，在網(wǎng)絡(luò)吞吐量上，原協(xié)議BS首輪接收6單位數(shù)據(jù)，此后隨著輪數(shù)的增加，接收數(shù)據(jù)緩慢增加，直至所有節(jié)點死亡，BS接收到9 925單位數(shù)據(jù)；而LEACH-Improvement的BS首輪接收18單位數(shù)據(jù)，其后快速增長，直至節(jié)點全部死亡共接收到25 454單位數(shù)據(jù)，整個生命周期始終保持比原協(xié)議高的數(shù)據(jù)量?？梢姡倪M后的協(xié)議在時間上的效率相對原協(xié)議高。

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

圖6　LEACH和LEACH-Improvement的數(shù)據(jù)傳輸對比

圖7　LEACH和LEACH-Improvement的網(wǎng)絡(luò)消耗對比

4　結(jié) 語

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

[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協(xié)議的改進算法[J].電子學(xué)報,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協(xié)議改進的簇間多跳路由協(xié)議[J].傳感技術(shù)學(xué)報,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] 陳慧杰,韓江洪,劉磊.無線傳感器網(wǎng)絡(luò)中自然能收集分簇路由算法研究[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].傳感技術(shù)學(xué)報,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].傳感技術(shù)學(xué)報,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—），男，碩士研究生，主要研究方向為物聯(lián)網(wǎng)通信、無線傳感器網(wǎng)絡(luò)仿真等；

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

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

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

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

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