基于節(jié)點位置和剩余能量的分簇路由改進算法*

陳 曦，羅雪梅，楊 靖，2

（1.貴州大學電氣工程學院，貴陽550025；2.貴州省“互聯(lián)網(wǎng)+”協(xié)同智能制造重點實驗室，貴陽550025）

1 引 言

無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN）是一種由大量傳感器節(jié)點構(gòu)成的自組織網(wǎng)絡，能對目標監(jiān)測信息進行收集，已被廣泛應用于軍事、農(nóng)業(yè)、環(huán)境監(jiān)測、智能家居等領域[1]。傳感器節(jié)點使用電池供電，通常部署在極端惡劣的工作環(huán)境中，而節(jié)點的能量利用率是WSN的關(guān)鍵技術(shù)指標之一[2]，如何平衡節(jié)點的負載和最大限度地延長網(wǎng)絡生命周期是國內(nèi)外學者研究的熱點問題。路由作為影響WSN性能的重要環(huán)節(jié)，關(guān)系到網(wǎng)絡數(shù)據(jù)傳輸?shù)目煽啃耘c實時性，其中能量的均衡高效是路由問題的重要指標，因此，設計一種高效節(jié)能的路由算法尤為重要[3]。為實現(xiàn)無線傳感器網(wǎng)絡的能量均衡高效，文獻[4]首次提出低功耗自適應層次聚類協(xié)議（Low-Energy Adaptive Clustering Hierarchy,LEACH），但該協(xié)議存在局限性，如：簇首分布不合理、能量消耗不均衡等。此后，相繼出現(xiàn)了如LEACH-C、EDDEEC、EELEACH等改進的路由協(xié)議[5-9]。但改進的協(xié)議仍存在一定的缺陷，如：未考慮節(jié)點位置及簇數(shù)的影響，忽略簇間通信能耗等。

針對現(xiàn)有研究的不足，在此嘗試提出一種改進分簇路由協(xié)議LEACH-EPN。

2 LEACH協(xié)議

2.1 協(xié)議概述

LEACH是無線傳感器網(wǎng)絡的基本聚類路由協(xié)議，它使用聚類算法來平衡網(wǎng)絡能耗。該路由協(xié)議以簇的形式來劃分網(wǎng)絡，并進行數(shù)據(jù)包的收集。在進行簇頭選舉時，每個節(jié)點都會生成一個隨機數(shù)值ζ（0<ζ<1），若節(jié)點i產(chǎn)生ζi小于閾值T(n)，則當選簇頭。T(n)的計算方法為：

其中，p表示簇頭在整個網(wǎng)絡中的占比；r表示當前網(wǎng)絡的工作輪次；G表示在本輪循環(huán)之前沒有擔任過簇頭節(jié)點的集合。

簇頭節(jié)點的選舉完成后，會在網(wǎng)絡中對將擔任簇頭的節(jié)點信息進行廣播，普通節(jié)點根據(jù)信號的強弱程度選擇合適的簇頭節(jié)點入簇。

2.2 網(wǎng)絡模型

改進算法基于傳統(tǒng)的LEACH網(wǎng)絡模型，具有如下設定：

1)在目標區(qū)域內(nèi)隨機部署N個節(jié)點，部署完成后，節(jié)點不再移動；

2)目標區(qū)域內(nèi)所有節(jié)點具有相同的初始能量Eo，且計算與通信能力相同；

3)基站位置已知且傳感器節(jié)點可以獨立與基站通信；

4)節(jié)點可根據(jù)信號強度計算自身相對位置，節(jié)點可以計算自身剩余能量并對數(shù)據(jù)進行融合處理。

2.3 能耗模型

鑒于無線傳感器節(jié)點的感知能耗和計算能耗遠低于通信能耗，所以協(xié)議中僅考慮通信能耗。根據(jù)發(fā)送節(jié)點和接收節(jié)點之間的通信距離建立起自由空間模型以及多路徑衰減模型，如圖1所示。

圖1 WSN能耗模型

根據(jù)一階無線電通信能耗模型可知，傳感器節(jié)點發(fā)送Lbit數(shù)據(jù)與能耗的關(guān)系為：

其中，Eelec表示電路損耗的能量。當傳輸距離d＜do時，選擇自由空間模型；當傳輸距離d＞do時，選擇多路徑衰減模型。式中的εfs和εmp分別為自由空間信道模型和多徑衰落信道模型下的傳輸功率放大器能耗參數(shù)。最終，節(jié)點接收Lbit數(shù)據(jù)消耗的能量為：

3 算法改進

對LEACH算法的改進，是綜合考慮節(jié)點剩余能量、節(jié)點位置及密度的WSN分簇路由算法，可稱為LEACH-EPN，其中E、P、N分別用來代表節(jié)點剩余能量、節(jié)點位置及當前網(wǎng)絡的存活節(jié)點數(shù)目。改進主要體現(xiàn)在：①引入能量、距離、密度因子來改進閾值公式，加入最優(yōu)簇數(shù)的約束條件以選擇出合適的簇頭節(jié)點，并通過改變簇的覆蓋范圍來改變成簇機制；②提出節(jié)點入簇偏好度的概念，綜合考慮數(shù)據(jù)傳輸距離以及節(jié)點當前剩余能量這兩個因素，共同確定節(jié)點的入簇機制。

3.1 最優(yōu)簇數(shù)

分簇路由協(xié)議中，簇首數(shù)目直接關(guān)系到網(wǎng)絡的整體性能。根據(jù)文獻[10]所述，最優(yōu)簇數(shù)與網(wǎng)絡中的節(jié)點總數(shù)及節(jié)點的覆蓋面積密切相關(guān)，即最優(yōu)簇數(shù)直接被當前網(wǎng)絡存活節(jié)點數(shù)所影響，當節(jié)點能量耗盡后，最優(yōu)簇數(shù)減少。因此，改進后的最優(yōu)簇數(shù)計算方式為：

式中，Nalive為當前網(wǎng)絡剩余的存活節(jié)點個數(shù)，M表示網(wǎng)絡區(qū)域的邊長，dtoBS表示節(jié)點i到基站的距離。

3.2 簇頭選舉方式改進

3.2.1 簇頭選舉指標

簇頭不僅要對簇內(nèi)數(shù)據(jù)進行采集、處理和發(fā)送，還要收發(fā)其他簇的數(shù)據(jù)并進行數(shù)據(jù)融合處理，因此，其能耗要遠遠大于普通成員節(jié)點。為均衡節(jié)點的能耗，簇頭應在各節(jié)點中輪選。

節(jié)點當前剩余能量Ei是當選簇頭的重要指標，剩余能量越多，當選簇頭的概率越大。節(jié)點i的剩余能量計算如下式：

式中，E0為節(jié)點初始能量；r表示當前輪數(shù)。

簇頭節(jié)點到sink節(jié)點的距離會直接影響到節(jié)點的生存期，距離的大小與數(shù)據(jù)傳輸?shù)哪芎某烧嚓P(guān)，即dtoBS(i)越大，能耗越大，節(jié)點i的存活時間越短。節(jié)點到基站距離的計算如下式：

節(jié)點密度Ni越大，即鄰居節(jié)點越多，簇建立時信息傳輸?shù)目蛇x路徑越多，平均消耗能量也就越少。節(jié)點i的密度計算方法如下：

式中，Nn(i)表示鄰居節(jié)點個數(shù)。

2.2.2 節(jié)點通信半徑

節(jié)點到sink節(jié)點的距離會直接影響到信息傳輸過程中的能耗。距離越大，數(shù)據(jù)傳輸產(chǎn)生的能耗越大，節(jié)點存活時間越短。反之，數(shù)據(jù)傳輸產(chǎn)生的能耗也越少，但距離基站較近的節(jié)點具有較重的路由任務，將會承擔著更多的數(shù)據(jù)轉(zhuǎn)發(fā)與傳輸工作。在選擇簇頭節(jié)點時，為了在距離sink節(jié)點較遠的區(qū)域內(nèi)選舉更多的簇頭節(jié)點，需要調(diào)整節(jié)點的通信半徑Ri，以此均衡各個節(jié)點的能耗，方法為：

式中：max(dtoBS)和min(dtoBS)分別表示簇頭節(jié)點到基站的最大距離和最小距離，R0為預定義的通信半徑，ω0∈(0,1)。

基于上述指標考慮，可對LEACH協(xié)議閾值公式進行改進。在簇頭選舉階段，先根據(jù)改進閾值公式對簇頭進行初選，選出的節(jié)點為備選簇頭。若備選簇頭節(jié)點數(shù)滿足最優(yōu)簇數(shù)的約束，則節(jié)點當選簇頭；否則，根據(jù)各備選簇頭的剩余能量及其到基站的距離來進行二次選擇。

3.3 節(jié)點入簇方式的改進

LEACH協(xié)議中普通節(jié)點的入簇方式是選擇加入距離最近的簇頭。在此基礎上進行改進，先將節(jié)點到所屬簇簇頭的距離與節(jié)點到sink節(jié)點的距離進行比較，若距離sink節(jié)點較近，則該節(jié)點可直接與sink節(jié)點進行通信，以此減少簇頭節(jié)點的數(shù)據(jù)融合能耗及數(shù)據(jù)傳輸能耗；若節(jié)點i同時被兩個或兩個以上的簇頭覆蓋，則優(yōu)先選擇偏好度大的簇頭節(jié)點進行入簇。簇頭節(jié)點j的偏好度計算如下式：

式中，E(i)表示節(jié)點i的剩余能量，E為當前網(wǎng)絡的平均剩余能量，dtoBS(j)表示簇頭節(jié)點j到基站的傳輸距離，k為(0,1)之間的隨機數(shù)。

至此，對閾值公式的改進可由如式各式表示：

式中：表示當前網(wǎng)絡內(nèi)的存活的節(jié)點數(shù)目，ω1、ω2和ω3均為(0,1)區(qū)間的隨機數(shù)。改進算法LEACH-EPN的整體流程圖如圖2所示。

圖2 LEACH-EPN算法流程圖

4 實驗仿真與結(jié)果對比

為驗證改進分簇協(xié)議的性能，采用MATLAB R2018a作為仿真平臺，對LEACH協(xié)議、文獻[9]的算法和LEACH-EPN算法進行對比仿真。在100×100的矩形區(qū)域中隨機部署N個傳感器節(jié)點，基站固定在區(qū)域中心位置，當選簇頭節(jié)點的概率p取值為0.1，k取值0.5。實驗參數(shù)如表1所示。

表1 仿真參數(shù)

節(jié)點總數(shù)N的值分別取100和200，仿真后得出相應網(wǎng)絡存活節(jié)點數(shù)量變化情況，如圖3所示。

圖3 存活節(jié)點數(shù)仿真結(jié)果對比

可見，LEACH-EPN算法相對于LEACH協(xié)議和文獻[9]，網(wǎng)絡生存期得到了較大提升。

不同節(jié)點規(guī)模下三種算法的網(wǎng)絡節(jié)點死亡百分數(shù)仿真結(jié)果如圖4所示?？梢钥吹剑cLEACH協(xié)議和文獻[9]的算法相比，LEACH-EPN算法的第一個節(jié)點、50%的節(jié)點及全部節(jié)點的死亡時間都較晚。當網(wǎng)絡節(jié)點規(guī)模取100時，LEACH-EPN的節(jié)點死亡時間較LEACH協(xié)議分別延長了7.55%、27.17%和61.5%；較文獻[9]的算法分別延長了4.31%、22.43%和57.13%。當節(jié)點規(guī)模為200時，LEACH-EPN算法的節(jié)點死亡時間較LEACH協(xié)議分別延長了21.9%、59.15%和86.89%；較文獻[9]的算法分別延長了14.88%、43.89%和74.48%。由此可見，改進算法LEACH-EPN有效均衡了網(wǎng)絡的能量消耗，從而延長了網(wǎng)絡生存周期。

圖4 網(wǎng)絡節(jié)點死亡百分數(shù)仿真結(jié)果對比

隨著仿真時間的變化，不同節(jié)點規(guī)模下的網(wǎng)絡剩余能量變化圖如圖5所示。

圖5 剩余能量仿真結(jié)果對比

可見，LEACH協(xié)議和文獻[9]算法的剩余能量比LEACH-EPN算法少得多，這表明改進算法LEACH-EPN能夠有效減少網(wǎng)絡能耗，網(wǎng)絡的整體性能更好，同時，具有較好的網(wǎng)絡負載均衡能力。

5 結(jié)束語

分簇路由算法LEACH-EPN作為對LEACH路由協(xié)議的改進，其精華部分在于對簇頭選舉階段對循環(huán)選舉時的閾值公式的改進，以及在入簇階段提出節(jié)點偏好度的概念。依照仿真結(jié)果，改進后的路由協(xié)議使簇首的選舉更加合理，減少了網(wǎng)絡的整體能耗，實現(xiàn)了網(wǎng)內(nèi)節(jié)點的能量負載均衡性，有效地延長了網(wǎng)絡生存時間。通過不同節(jié)點規(guī)模仿真，也證實了LEACH-EPN算法更適用于基站位于區(qū)域中心且節(jié)點規(guī)模較大的網(wǎng)絡。