一種改進LEACH的無線傳感器路由協議仿真

覃琪 譚松鶴

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

關鍵詞：無線傳感器網絡;LEACH;層次型路由協議;網絡生命周期

中圖分類號：TP212.9? ? ? ? 文獻標志碼：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

引言

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

1 LEACH路由協議研究

LEACH協議是為無線傳感器網絡WSN設計的一種低功耗自適應分簇層次型路由協議。LEACH協議算法以一定概率隨機選取某個節點擔任簇頭并與相鄰節點動態形成簇，算法使得網絡中的節點輪流擔任簇頭而平均的分攤通信能量消耗，最終達到實現節點能量的負載均衡、延長網絡壽命的目標[7]。LEACH協議工作過程是分成很多“輪”（round）進行的，每一輪包含簇建立（setup_up）階段和穩定運行（steady-state）階段。

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

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

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

另有研究者文獻[6]提出一種基于節點區域中心的改進算法LEACH_CS，該算法針對簇頭選舉算法中簇頭節點個數偏離最優值范圍，導致全網能耗過快，以及簇頭位置分布不均勻，造成的簇頭節點負載的不均衡問題，通過考慮簇頭節點的最優分布區域，使簇頭節點盡可能的均勻分布在網絡中，形成簇的規模也近似相等，還設定了簇首節點“棄權”機制，以限制簇首個數超出最優值的范圍。

2 基于LEACH路由協議的改進算法

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

2.1 簇建立階段

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

Step2 定時時間到的節點生成一個隨機數Rnd，計算過程見公式（2），即剩余能量越大的節點越容易產生較小的數值，也就越容易當選簇頭節點。

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

Step3 節點生成的隨機數Rnd如果小于文獻[6]給出的門限值Tnew（n）則被選為簇頭，并向網絡中發送廣播建簇信息。隨機數不小于閥值Tnew（n）的節點返回Step2生成新的隨機數，再確定能否當選為簇頭節點。

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

由公式（2）和（3）可知，優化后簇頭節點的選擇除了要考慮未選舉成功過的節點數目和網絡所需要的簇頭節點的比例，還要考慮節點到中心圓周的距離和所有未當選簇頭的節點到中心圓周的平均距離，以及節點的剩余能量。優化選舉產生的簇頭節點將大致以中心圓周為基準進行分布，確保了簇頭節點之間的通信間距比較短，同時能有效減少簇頭節點集中在某一局部區域的最差情況發生。

2.2 簇穩定運行階段

在簇穩定運行階段，簇內節點根據簇頭分配的TDMA時隙號通過單跳方式向簇頭傳輸數據，簇頭節點將收到的數據進行數據融合后采用多跳路由的方式發送給區域外的基站。網絡穩定運行一段時間后，在下一個時間周期開始新一輪的簇頭選舉過程。簇頭到基站之間通信的多跳路由算法描述如下：

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

其中，E為節點剩余能量、Emax為節點初始最大能量、D為節點到基站的距離，Dmax為傳感器節點范圍內離基站最遠的距離。

算法能夠確保那些距離基站較近并且剩余能量較多的簇頭節點能優先成為多條樹的根節點。當出現權值相等的情形時，則根據節點的ID大小來選擇父節點，ID大的節點當選為父節點。該算法通過選擇最小的MTE路由來減少距離基站較遠的節點的能量消耗;同時又能防止距離基站較近的簇頭節點因為頻繁轉發其他簇頭節點的數據而導致死亡的情況發生，保證了該算法的能量低耗性，可以有效的延長整個網絡的生存周期。

3 實驗結果與分析

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

4 結論

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

參考文獻：

[1]焦克瑩，郭強.面向異構WSNs的基于能量感知的簇路由算法[J].傳感技術學報，2017，30（9）：1427-1432.

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

[3]肖軍弼，劉戰軍.AntNet算法在AdHoc網絡QoS組播路由中的研究[J].計算機系統應用，2014，23（11）：127-131.

[4]周欣欣，余鎮危.基于情景感知的移動AdHoc網絡自適應路由協議[J].計算機工程與設計，2014，35（11）：3799-3903.

[5]劉迪，等.基于NDN的多層衛星網絡分布式動態路由方法[J].電子學報，2017，45（11）：2769-2778.

[6]騰英政.基于LEACH的無線傳感網絡路由協議研究[D].大連理工大學，2008.

[7]陳晨，楊紅麗.無線傳感器網絡LEACH協議能耗改進[J].計算機系統應用，2017，26（11）：205-212.