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

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

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

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

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

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

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

0　引 言

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

無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不是一成不變的，并且網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的能量也是受限的且通常非常少，所以在無(wú)線傳感器網(wǎng)絡(luò)的諸多研究中，能夠連接所有傳感器節(jié)點(diǎn)且可以降低能耗的路由協(xié)議是其最關(guān)鍵的技術(shù)之一。結(jié)構(gòu)上，WSN路由協(xié)議可分為平面協(xié)議和層次性協(xié)議。平面協(xié)議工作時(shí)需要維持較大的路由表，并不適合應(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é)點(diǎn)輪流擔(dān)任簇頭而達(dá)到能量盡可能均勻消耗的目的。但是，該協(xié)議也存在簇頭的分布不合理、能耗不均、單跳選擇等缺陷。W-LEACH[2]、T-LEACH、LEACHRA和LEACH-C等改進(jìn)協(xié)議，對(duì)原LEACH協(xié)議在不同角度進(jìn)行了不同改進(jìn)[3]，但大部分算法選簇時(shí)仍沿用LEACH的分布式方法。

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

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

1.1LEACH協(xié)議概述

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

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

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

圖2　LEACH運(yùn)行過(guò)程

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

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

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

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

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

2　對(duì)LEACH協(xié)議的綜合改進(jìn)

2.1基本思想

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

2.2一階無(wú)線電模型

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

同樣條件下，接收信息無(wú)線電擴(kuò)展為：

圖3　一階無(wú)線電模型

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

2.3簇頭的選擇

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

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

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

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

圖4　簇頭選擇流程

2.4簇間多跳通信

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

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

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

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

表1　仿真參數(shù)

圖5　LEACH和LEACH-Improvement的死亡節(jié)點(diǎn)隨時(shí)間變化對(duì)比

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

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

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

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

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

4　結(jié) 語(yǔ)

無(wú)線傳感器網(wǎng)絡(luò)分簇算法采用輪換的節(jié)點(diǎn)作為簇頭方式來(lái)平衡整個(gè)傳感器網(wǎng)絡(luò)的負(fù)載和能量，但隨機(jī)選擇簇頭的方式和單跳的簇間路由有時(shí)會(huì)造成能源的大量浪費(fèi)。針對(duì)這些問(wèn)題，本文逐一進(jìn)行逐改進(jìn)。在簇頭選擇上，參考更多的節(jié)點(diǎn)客觀參數(shù)。仿真發(fā)現(xiàn)，在100個(gè)節(jié)點(diǎn)上，改進(jìn)算法在生存期、能耗、效率上，均有一定的提高。但同時(shí)發(fā)現(xiàn)，本改進(jìn)算法在更大規(guī)模網(wǎng)絡(luò)上（如300枚節(jié)點(diǎn)）的應(yīng)用效果并不理想，因?yàn)閷?duì)網(wǎng)絡(luò)進(jìn)行的一些細(xì)節(jié)改進(jìn)使得自適應(yīng)性被削弱；BS在確定簇頭時(shí)會(huì)產(chǎn)生更多簇間路由。鑒于此，下一步在解決以上問(wèn)題的同時(shí)，會(huì)在選舉函數(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ìn)算法[J].電子學(xué)報(bào),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é)議改進(jìn)的簇間多跳路由協(xié)議[J].傳感技術(shù)學(xué)報(bào),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ú)線傳感器網(wǎng)絡(luò)中自然能收集分簇路由算法研究[J].計(jì)算機(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] 馬建樂(lè),楊軍.基于位置和剩余能量的局部集中式LEACH算法研究[J].傳感技術(shù)學(xué)報(bào),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的改進(jìn)WSN路由算法[J].傳感技術(shù)學(xué)報(bào),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—），男，碩士研究生，主要研究方向?yàn)槲锫?lián)網(wǎng)通信、無(wú)線傳感器網(wǎng)絡(luò)仿真等；

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

婁 陽(yáng)（1990—），男，碩士研究生，主要研究方向?yàn)長(zhǎng)DPC碼混沌加密技術(shù)；

劉寶軍（1991—），男，碩士研究生，主要研究方向?yàn)長(zhǎng)DPC碼和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ā)展計(jì)劃項(xiàng)目（No.2012J0030009）