覃琪 譚松鶴

摘? 要：文章在研究LEACH協(xié)議的基礎(chǔ)上，提出了一種改進(jìn)的層次型路由協(xié)議LEACH-Improved，改進(jìn)的路由協(xié)議主要針對原有LEACH路由協(xié)議的不足，主要改進(jìn)在兩個方面：一是在簇頭節(jié)點的選擇上依據(jù)節(jié)點的剩余能量和節(jié)點與區(qū)域中心的距離，作為主要考慮因素，減少簇頭分布的不合理情況，能有效地平衡節(jié)點的能量消耗;二是簇頭節(jié)點采用多跳路由的方式向基站傳輸數(shù)據(jù)，也減少了部分簇頭節(jié)點與基站的遠(yuǎn)距離的通信。最后通過OMNeT++仿真工具進(jìn)行仿真實驗，實驗結(jié)果顯示該算法相比原有的LEACH路由協(xié)議能有效地延長網(wǎng)絡(luò)生命周期，降低網(wǎng)絡(luò)能耗，實現(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ò)體系，具有移動性、無線布線、多跳路由等多種特點，在遠(yuǎn)程監(jiān)測、信息采集以及交通控制等多個領(lǐng)域都有廣泛應(yīng)用[1-2]。無線傳感器網(wǎng)絡(luò)通過傳感器節(jié)點采集與處理覆蓋域內(nèi)監(jiān)測到的信息，在軍事、消防以及工業(yè)領(lǐng)域均有著廣泛的應(yīng)用[3]。在實際網(wǎng)絡(luò)應(yīng)用中，傳感器節(jié)點分布不均，使得某些簇頭與距離較遠(yuǎn)的基站進(jìn)行通信時，發(fā)射功率較大，增加了網(wǎng)絡(luò)通信能耗，縮短了網(wǎng)絡(luò)生命周期[4]。在這種情況下，如何有效地進(jìn)行降低網(wǎng)絡(luò)通信能耗，成為了該領(lǐng)域亟待解決的主要問題。而低能耗多跳路由協(xié)議中的簇頭選取策略，通過綜合考慮網(wǎng)絡(luò)候選傳感器節(jié)點的剩余能量以及自身位置信息等參數(shù)優(yōu)化簇頭選取，避免剩余能量較少和位置不佳的傳感器節(jié)點被推選成簇首，減少能量消耗，是解決上述弊端的有效手段，引起了該領(lǐng)域相關(guān)專家學(xué)者的高度關(guān)注[5]。

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

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

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

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

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

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

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

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

2.1 簇建立階段

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

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

4 結(jié)論

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

參考文獻(xiàn)：

[1]焦克瑩，郭強.面向異構(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].計算機系統(tǒng)應(yīng)用，2014，23（11）：127-131.

[4]周欣欣，余鎮(zhèn)危.基于情景感知的移動AdHoc網(wǎng)絡(luò)自適應(yīng)路由協(xié)議[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].計算機系統(tǒng)應(yīng)用，2017，26（11）：205-212.