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

陳 曦，羅雪梅，楊 靖，2

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

1 引 言

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

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

2 LEACH協(xié)議

2.1 協(xié)議概述

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

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

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

2.2 網(wǎng)絡(luò)模型

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

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

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

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

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

2.3 能耗模型

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

圖1 WSN能耗模型

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

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

3 算法改進(jìn)

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

3.1 最優(yōu)簇?cái)?shù)

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

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

3.2 簇頭選舉方式改進(jìn)

3.2.1 簇頭選舉指標(biāo)

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

節(jié)點(diǎn)當(dāng)前剩余能量Ei是當(dāng)選簇頭的重要指標(biāo)，剩余能量越多，當(dāng)選簇頭的概率越大。節(jié)點(diǎn)i的剩余能量計(jì)算如下式：

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

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

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

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

2.2.2 節(jié)點(diǎn)通信半徑

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

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

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

3.3 節(jié)點(diǎn)入簇方式的改進(jìn)

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

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

至此，對閾值公式的改進(jìn)可由如式各式表示：

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

圖2 LEACH-EPN算法流程圖

4 實(shí)驗(yàn)仿真與結(jié)果對比

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

表1 仿真參數(shù)

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

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

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

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

圖4 網(wǎng)絡(luò)節(jié)點(diǎn)死亡百分?jǐn)?shù)仿真結(jié)果對比

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

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

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

5 結(jié)束語

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