覃琪 譚松鶴

摘? 要：文章在研究LEACH協(xié)議的基礎(chǔ)上，提出了一種改進(jìn)的層次型路由協(xié)議LEACH-Improved，改進(jìn)的路由協(xié)議主要針對原有LEACH路由協(xié)議的不足，主要改進(jìn)在兩個方面：一是在簇頭節(jié)點(diǎn)的選擇上依據(jù)節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)與區(qū)域中心的距離，作為主要考慮因素，減少簇頭分布的不合理情況，能有效地平衡節(jié)點(diǎn)的能量消耗;二是簇頭節(jié)點(diǎn)采用多跳路由的方式向基站傳輸數(shù)據(jù)，也減少了部分簇頭節(jié)點(diǎn)與基站的遠(yuǎn)距離的通信。最后通過OMNeT++仿真工具進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果顯示該算法相比原有的LEACH路由協(xié)議能有效地延長網(wǎng)絡(luò)生命周期，降低網(wǎng)絡(luò)能耗，實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載平衡。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);LEACH;層次型路由協(xié)議;網(wǎng)絡(luò)生命周期

中圖分類號：TP212.9? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號：2095-2945（2019）08-0011-04

Abstract： Based on the study of LEACH protocol， an improved hierarchical routing protocol， LEACH-Improved， is proposed in this paper. The improved routing protocol mainly aims at the shortcomings of the original LEACH routing protocol. The main improvement is in two aspects： First， according to the residual energy of the node and the distance between the node and the regional center， as the main consideration factor， the unreasonable distribution of the cluster head can be reduced in the selection of the cluster head node， which can effectively balance the energy consumption of the nodes. Second， the cluster head nodes use multi-hop routing to transmit data to the base station， thereby can reduce the long-distance communication between some cluster head nodes and the base station. Finally， the simulation experiments are carried out by OMNeT++ simulation tool. The experimental results show that the algorithm can effectively prolong the network life cycle， reduce network energy consumption and achieve network load balancing， compared with the original LEACH routing protocol.

Keywords： wireless sensor networks （WSN）; LEACH; hierarchical routing protocol; network life cycle

引言

無線傳感器網(wǎng)絡(luò)作為一種新型網(wǎng)絡(luò)體系，具有移動性、無線布線、多跳路由等多種特點(diǎn)，在遠(yuǎn)程監(jiān)測、信息采集以及交通控制等多個領(lǐng)域都有廣泛應(yīng)用[1-2]。無線傳感器網(wǎng)絡(luò)通過傳感器節(jié)點(diǎn)采集與處理覆蓋域內(nèi)監(jiān)測到的信息，在軍事、消防以及工業(yè)領(lǐng)域均有著廣泛的應(yīng)用[3]。在實(shí)際網(wǎng)絡(luò)應(yīng)用中，傳感器節(jié)點(diǎn)分布不均，使得某些簇頭與距離較遠(yuǎn)的基站進(jìn)行通信時，發(fā)射功率較大，增加了網(wǎng)絡(luò)通信能耗，縮短了網(wǎng)絡(luò)生命周期[4]。在這種情況下，如何有效地進(jìn)行降低網(wǎng)絡(luò)通信能耗，成為了該領(lǐng)域亟待解決的主要問題。而低能耗多跳路由協(xié)議中的簇頭選取策略，通過綜合考慮網(wǎng)絡(luò)候選傳感器節(jié)點(diǎn)的剩余能量以及自身位置信息等參數(shù)優(yōu)化簇頭選取，避免剩余能量較少和位置不佳的傳感器節(jié)點(diǎn)被推選成簇首，減少能量消耗，是解決上述弊端的有效手段，引起了該領(lǐng)域相關(guān)專家學(xué)者的高度關(guān)注[5]。

1 LEACH路由協(xié)議研究

LEACH協(xié)議是為無線傳感器網(wǎng)絡(luò)WSN設(shè)計的一種低功耗自適應(yīng)分簇層次型路由協(xié)議。LEACH協(xié)議算法以一定概率隨機(jī)選取某個節(jié)點(diǎn)擔(dān)任簇頭并與相鄰節(jié)點(diǎn)動態(tài)形成簇，算法使得網(wǎng)絡(luò)中的節(jié)點(diǎn)輪流擔(dān)任簇頭而平均的分?jǐn)偼ㄐ拍芰肯?，最終達(dá)到實(shí)現(xiàn)節(jié)點(diǎn)能量的負(fù)載均衡、延長網(wǎng)絡(luò)壽命的目標(biāo)[7]。LEACH協(xié)議工作過程是分成很多“輪”（round）進(jìn)行的，每一輪包含簇建立（setup_up）階段和穩(wěn)定運(yùn)行（steady-state）階段。

簇建立（setup_up）階段，每一輪開始都會為每個節(jié)點(diǎn)n隨機(jī)選取一個在0到1之間的實(shí)數(shù)，成為標(biāo)記值或者節(jié)點(diǎn)的記號。如果n的這個標(biāo)記值小于一個門限值T（n）的話，節(jié)點(diǎn)n就當(dāng)選為本輪的簇頭節(jié)點(diǎn)。門限值T（n）通過公式（1）計算得出。各簇頭節(jié)點(diǎn)廣播建簇信號，其他相鄰節(jié)點(diǎn)選擇信號最強(qiáng)的簇頭加入形成簇[7]。

P是網(wǎng)絡(luò)中每輪期望選出的簇頭節(jié)點(diǎn)所占總節(jié)點(diǎn)數(shù)目的百分比（根據(jù)不同應(yīng)用場景選值在4%-5%之間）;r為當(dāng)前的輪數(shù)，G是前l(fā)/P輪中沒有充當(dāng)過簇頭節(jié)點(diǎn)的節(jié)點(diǎn)的集合[8]，mod符號是求模運(yùn)算符。通過這樣的計算公式，可以保證每個節(jié)點(diǎn)會在1/P輪內(nèi)都充當(dāng)一次簇頭節(jié)點(diǎn)，從而實(shí)現(xiàn)節(jié)點(diǎn)能量的負(fù)載均衡。

目前針對LEACH協(xié)議的研究很多，MIT學(xué)者Heinzelman等人在LEACH協(xié)議的基礎(chǔ)上又提出了LEACH-C協(xié)議，它解決了LEACH協(xié)議中“無法確定每輪簇頭的數(shù)量和位置”以及“根據(jù)隨機(jī)數(shù)決定節(jié)點(diǎn)是否當(dāng)選為簇頭”等方面的問題，大大提高了簇的生成質(zhì)量。此外，該算法直接由基站選擇簇頭，健壯性較好，但由于所有節(jié)點(diǎn)都必須向基站周期性地發(fā)送它們的位置和能量等信息，成簇開銷較大，并且會增加網(wǎng)絡(luò)流量、信號干擾以及時間延遲的概率。

另有研究者文獻(xiàn)[6]提出一種基于節(jié)點(diǎn)區(qū)域中心的改進(jìn)算法LEACH_CS，該算法針對簇頭選舉算法中簇頭節(jié)點(diǎn)個數(shù)偏離最優(yōu)值范圍，導(dǎo)致全網(wǎng)能耗過快，以及簇頭位置分布不均勻，造成的簇頭節(jié)點(diǎn)負(fù)載的不均衡問題，通過考慮簇頭節(jié)點(diǎn)的最優(yōu)分布區(qū)域，使簇頭節(jié)點(diǎn)盡可能的均勻分布在網(wǎng)絡(luò)中，形成簇的規(guī)模也近似相等，還設(shè)定了簇首節(jié)點(diǎn)“棄權(quán)”機(jī)制，以限制簇首個數(shù)超出最優(yōu)值的范圍。

2 基于LEACH路由協(xié)議的改進(jìn)算法

本文提出一種基于LEACH路由協(xié)議的改進(jìn)路由協(xié)議LEACH-Improved后面簡稱LEACH-I。改進(jìn)算法的主要思想是：首先，根據(jù)節(jié)點(diǎn)的剩余能量作為主要依據(jù)選擇簇頭，并在簇頭和基站之間通信引入改進(jìn)的多跳路由算法，簇內(nèi)節(jié)點(diǎn)和簇頭節(jié)點(diǎn)之間還是采用直接通信的方式。LEACH-I協(xié)議的運(yùn)行過程類似于LEACH協(xié)議分為多“輪”進(jìn)行，每一輪分為兩個階段，簇建立階段和簇穩(wěn)定運(yùn)行階段，如圖1所示。

2.1 簇建立階段

Step1每一輪開始時，每個節(jié)點(diǎn)先根據(jù)自己的剩余能量生成一個定時時間，剩余能量越大的節(jié)點(diǎn)生成的定時時間越短。

Step2 定時時間到的節(jié)點(diǎn)生成一個隨機(jī)數(shù)Rnd，計算過程見公式（2），即剩余能量越大的節(jié)點(diǎn)越容易產(chǎn)生較小的數(shù)值，也就越容易當(dāng)選簇頭節(jié)點(diǎn)。

其中? ? ? 為該節(jié)點(diǎn)的剩余能量，? ? 為節(jié)點(diǎn)的初始能量。

Step3 節(jié)點(diǎn)生成的隨機(jī)數(shù)Rnd如果小于文獻(xiàn)[6]給出的門限值Tnew（n）則被選為簇頭，并向網(wǎng)絡(luò)中發(fā)送廣播建簇信息。隨機(jī)數(shù)不小于閥值Tnew（n）的節(jié)點(diǎn)返回Step2生成新的隨機(jī)數(shù)，再確定能否當(dāng)選為簇頭節(jié)點(diǎn)。

其中，P是一個0-1間的實(shí)數(shù)，表示網(wǎng)絡(luò)中每輪成為簇頭的節(jié)點(diǎn)占所有節(jié)點(diǎn)的比例;r表示當(dāng)前輪數(shù);G表示在前的r-1輪內(nèi)未充當(dāng)簇頭的節(jié)點(diǎn)集合，mod符號表示求模運(yùn)算符，di表示節(jié)點(diǎn)i到分布區(qū)域中心的距離，dj表示本輪中參與選舉的節(jié)點(diǎn)到分布區(qū)域中心的距離，n代表參加選舉的節(jié)點(diǎn)個數(shù)，R代表中心圓周的半徑。

由公式（2）和（3）可知，優(yōu)化后簇頭節(jié)點(diǎn)的選擇除了要考慮未選舉成功過的節(jié)點(diǎn)數(shù)目和網(wǎng)絡(luò)所需要的簇頭節(jié)點(diǎn)的比例，還要考慮節(jié)點(diǎn)到中心圓周的距離和所有未當(dāng)選簇頭的節(jié)點(diǎn)到中心圓周的平均距離，以及節(jié)點(diǎn)的剩余能量。優(yōu)化選舉產(chǎn)生的簇頭節(jié)點(diǎn)將大致以中心圓周為基準(zhǔn)進(jìn)行分布，確保了簇頭節(jié)點(diǎn)之間的通信間距比較短，同時能有效減少簇頭節(jié)點(diǎn)集中在某一局部區(qū)域的最差情況發(fā)生。

2.2 簇穩(wěn)定運(yùn)行階段

在簇穩(wěn)定運(yùn)行階段，簇內(nèi)節(jié)點(diǎn)根據(jù)簇頭分配的TDMA時隙號通過單跳方式向簇頭傳輸數(shù)據(jù)，簇頭節(jié)點(diǎn)將收到的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合后采用多跳路由的方式發(fā)送給區(qū)域外的基站。網(wǎng)絡(luò)穩(wěn)定運(yùn)行一段時間后，在下一個時間周期開始新一輪的簇頭選舉過程。簇頭到基站之間通信的多跳路由算法描述如下：

分簇完成后，簇頭節(jié)點(diǎn)在區(qū)域內(nèi)廣播其自身權(quán)重（WEIGHT）消息，該消息包含權(quán)值W（由公式（4）計算得出）和節(jié)點(diǎn)自己的ID。各簇頭節(jié)點(diǎn)收到WEIGHT消息后，將自身的權(quán)值和消息中包含的權(quán)值和進(jìn)行比較，選擇權(quán)值較大的節(jié)點(diǎn)作為自己的父節(jié)點(diǎn)，并發(fā)出加入隊(duì)列的消息，另外在所有簇頭節(jié)點(diǎn)中選出權(quán)值最大的節(jié)點(diǎn)作為多跳樹的根節(jié)點(diǎn)，從而形成了簇頭節(jié)點(diǎn)間多跳通信的路徑。簇頭節(jié)點(diǎn)沿著多跳樹路徑將融合計算后的數(shù)據(jù)傳送給父節(jié)點(diǎn)，再一級一級傳遞到根節(jié)點(diǎn)，最后由根節(jié)點(diǎn)直接和基站通信傳遞數(shù)據(jù)。當(dāng)出現(xiàn)簇類的分布較為稀疏或節(jié)點(diǎn)已絕大部分死亡時的情況時，簇頭節(jié)點(diǎn)不會收到任何WEIGHT消息，則簇頭直接與基站通信傳遞數(shù)據(jù)。

其中，E為節(jié)點(diǎn)剩余能量、Emax為節(jié)點(diǎn)初始最大能量、D為節(jié)點(diǎn)到基站的距離，Dmax為傳感器節(jié)點(diǎn)范圍內(nèi)離基站最遠(yuǎn)的距離。

算法能夠確保那些距離基站較近并且剩余能量較多的簇頭節(jié)點(diǎn)能優(yōu)先成為多條樹的根節(jié)點(diǎn)。當(dāng)出現(xiàn)權(quán)值相等的情形時，則根據(jù)節(jié)點(diǎn)的ID大小來選擇父節(jié)點(diǎn)，ID大的節(jié)點(diǎn)當(dāng)選為父節(jié)點(diǎn)。該算法通過選擇最小的MTE路由來減少距離基站較遠(yuǎn)的節(jié)點(diǎn)的能量消耗;同時又能防止距離基站較近的簇頭節(jié)點(diǎn)因?yàn)轭l繁轉(zhuǎn)發(fā)其他簇頭節(jié)點(diǎn)的數(shù)據(jù)而導(dǎo)致死亡的情況發(fā)生，保證了該算法的能量低耗性，可以有效的延長整個網(wǎng)絡(luò)的生存周期。

3 實(shí)驗(yàn)結(jié)果與分析

通過仿真實(shí)驗(yàn)驗(yàn)證改進(jìn)算法的有效性，實(shí)驗(yàn)采用OMNet++仿真平臺，實(shí)驗(yàn)仿真環(huán)境是在100m×100m范圍內(nèi)隨機(jī)布置100個無線傳感器節(jié)點(diǎn)。鑒于目前針對網(wǎng)絡(luò)節(jié)點(diǎn)壽命的定義尚未形成統(tǒng)一的標(biāo)準(zhǔn)，為了滿足不同應(yīng)用場合的需要，本文將節(jié)點(diǎn)壽命評價指標(biāo)定義為三種形式：第一個節(jié)點(diǎn)死亡（FisrtNodeDied）、一半節(jié)點(diǎn)死亡（HalfNodeDied）和全部節(jié)點(diǎn)死亡（LastNodeDied）。下面從兩個方面分別與LEACH協(xié)議和LEACH_CS協(xié)議進(jìn)行仿真實(shí)驗(yàn)對比。

4 結(jié)論

本文在研究LEACH協(xié)議的基礎(chǔ)上，提出了一種改進(jìn)的層次型路由協(xié)議LEACH-Improved，改進(jìn)的路由協(xié)議主要針對原有LEACH路由協(xié)議的不足，最后通過OMNeT++仿真工具進(jìn)行仿真實(shí)驗(yàn)，仿真結(jié)果表明，LEACH-I協(xié)議在網(wǎng)絡(luò)生存周期、減少能量消耗兩個方面相對于LEACH協(xié)議都有明顯的提高。

參考文獻(xiàn)：

[1]焦克瑩，郭強(qiáng).面向異構(gòu)WSNs的基于能量感知的簇路由算法[J].傳感技術(shù)學(xué)報，2017，30（9）：1427-1432.

[2]陳志剛，沈小建，劉立.無線mesh網(wǎng)中最小編碼代價低時延多播路由[J].通信學(xué)報，2016，37（1）：10-16.

[3]肖軍弼，劉戰(zhàn)軍.AntNet算法在AdHoc網(wǎng)絡(luò)QoS組播路由中的研究[J].計算機(jī)系統(tǒng)應(yīng)用，2014，23（11）：127-131.

[4]周欣欣，余鎮(zhèn)危.基于情景感知的移動AdHoc網(wǎng)絡(luò)自適應(yīng)路由協(xié)議[J].計算機(jī)工程與設(shè)計，2014，35（11）：3799-3903.

[5]劉迪，等.基于NDN的多層衛(wèi)星網(wǎng)絡(luò)分布式動態(tài)路由方法[J].電子學(xué)報，2017，45（11）：2769-2778.

[6]騰英政.基于LEACH的無線傳感網(wǎng)絡(luò)路由協(xié)議研究[D].大連理工大學(xué)，2008.

[7]陳晨，楊紅麗.無線傳感器網(wǎng)絡(luò)LEACH協(xié)議能耗改進(jìn)[J].計算機(jī)系統(tǒng)應(yīng)用，2017，26（11）：205-212.