一種基于多跳與按數(shù)據(jù)量-距離分發(fā)的LEACH協(xié)議優(yōu)化

潘 華， 陳佳品， 丁 凱， 林鳳德

(1.上海交通大學微納電子學系，上海 200240； 2.近地面感知與探測重點實驗室，江蘇 無錫 214000)

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)[1]是由多個節(jié)點組成的自組織網(wǎng)絡(luò)。在軍事、航天等領(lǐng)域有極為廣泛的應(yīng)用，本文的背景是基于一個智能雷場項目的雷場節(jié)點壽命研究。智能雷場是通過對一片雷場區(qū)域內(nèi)的地雷上安裝傳感器節(jié)點，達到實時收集戰(zhàn)場態(tài)勢信息以及使地雷之間能夠相互通信，最終能夠產(chǎn)生一種選擇性智能爆炸的效果。而雷場節(jié)點指的就是安裝了具有無線通信功能的傳感器節(jié)點的地雷。由于在軍事領(lǐng)域，傳感器節(jié)點一般都是一次性部署而不進行維護，其壽命通常由電池能量決定，然而，WSN自身的特點決定了一旦某個節(jié)點由于能量耗盡而死亡，將會導致網(wǎng)絡(luò)拓撲結(jié)構(gòu)的變化，甚至可能導致通信中斷等不可靠行為發(fā)生。如何最大限度地降低雷場節(jié)點的能量消耗，對延長整個雷場網(wǎng)絡(luò)的壽命至關(guān)重要。在這種情況下，國外研究者提出了低能量自適應(yīng)聚類路由(LEACH)協(xié)議[2-3]——一種最早的分簇路由協(xié)議。本文在深入理解LEACH協(xié)議的基礎(chǔ)上，結(jié)合以上幾點因素，對LEACH協(xié)議進行改進，目的是得到一種更加節(jié)能的路由協(xié)議。

1 LEACH協(xié)議描述

LEACH協(xié)議定義了“輪”的概念[4]，協(xié)議以輪為周期執(zhí)行，每一輪的過程包括分簇和穩(wěn)定兩個階段。在分簇階段，WSN各個節(jié)點隨機生成一個0～1之間的數(shù)字，然后將該數(shù)字與一個設(shè)定的閾值公式得出的值進行比較，若該隨機數(shù)小于閾值，并且該節(jié)點在前1/p(p為當前輪中節(jié)點成為簇頭的比例)輪內(nèi)未當選為簇頭節(jié)點，則該節(jié)點被選為本輪的簇頭節(jié)點。其中，閾值的算式為[5]

(1)

式中：p為成為簇頭的期望百分比；r為當前輪數(shù)；mod為取模符號；G為在最后1/p輪中還未成為簇頭的節(jié)點集合。

當簇頭選取完畢后，簇頭向周圍節(jié)點廣播自身的簇頭狀態(tài)、ID等信息，節(jié)點根據(jù)接收到的消息強度決定加入哪個簇，并告知相應(yīng)的簇頭，完成簇頭的建立過程。然后，簇頭節(jié)點采用TDMA的方式[6]，為簇內(nèi)成員分配傳送數(shù)據(jù)的時隙。

在穩(wěn)定階段，傳感器節(jié)點價格采集的數(shù)據(jù)傳送到簇頭節(jié)點。簇頭節(jié)點對采集的數(shù)據(jù)進行數(shù)據(jù)融合后再將信息以單跳方式傳送到匯聚節(jié)點，按照不同的CDMA代碼直接發(fā)送給基站。

但是，LEACH協(xié)議存在以下問題[7]：

1) LEACH協(xié)議算法中，簇頭的選取是隨機的,而沒有考慮到節(jié)點當前的能量，有可能剩余能量很小的節(jié)點仍然被選為簇頭，導致該節(jié)點過早死亡，引發(fā)再組網(wǎng)等一系列問題，降低網(wǎng)絡(luò)生存周期;

2) 簇頭與基站之間直接單跳通信，當距離較遠時，能量消耗成指數(shù)增長，造成簇頭節(jié)點過早死亡，進而降低網(wǎng)絡(luò)生命周期;

3) 簇頭的選取無法保證節(jié)點在空間上均勻分布，在某些可能的情況下，形成的簇頭節(jié)點可能聚集在某一個小范圍內(nèi)，導致某些節(jié)點無法加入任何簇。

2 改進后的LEACH協(xié)議

改進后的LEACH協(xié)議(IMP-LEACH)與LEACH算法有如下相同的網(wǎng)絡(luò)模型[8]。

1) 傳感器節(jié)點隨機分布在某一片方形區(qū)域，基站唯一;

2) 部署之后所有節(jié)點(包括基站)的位置不變;

3) 各個傳感器節(jié)點的初始能量相同，且已知節(jié)點任何時刻的剩余能量，基站能量不受限。

在上面的模型中，文獻[9]給出了幾個定義：鄰居節(jié)點、前鄰節(jié)點、前簇頭節(jié)點。

針對LEACH協(xié)議的諸多缺點，本文根據(jù)協(xié)議的幾個過程，對每一個過程提出以下改進，整體算法步驟如下所述。

1) 在判斷是否為簇頭的過程中，加入節(jié)點當前能量這個考量因素，提出

(2)

式中：Eicurrent為節(jié)點i當前能量；Eavg為系統(tǒng)節(jié)點當前平均能量;α定義為能量距離因子，取值為2或4，取決于節(jié)點間距離d。

2) 在簇頭選取的過程中，不同簇頭節(jié)點能量的不同會導致其通信距離的不同，同時，不同能量的簇頭節(jié)點，其所能容納的節(jié)點數(shù)也不同，在節(jié)點選擇加入簇頭的過程中，綜合考慮以上兩點，給出如下定義。

對于一個特定的節(jié)點i，其所能加入的簇頭節(jié)點集合CH需滿足以下兩個條件。

條件1滿足

N(CH)={CHCH∈V,d(i,CH)

(3)

式中，d(i,CH)

條件2在滿足條件1的情況下，進行如下運算

(4)

式中:{CHiCHi∈CH};Emin為使節(jié)點存活所需要的最小能量;ECHi為簇頭節(jié)點i當前剩余能量;n為當前加入簇頭節(jié)點i的節(jié)點個數(shù);E(i,n)為當有n個節(jié)點加入簇頭節(jié)點i時，每個節(jié)點所能分配的能量。通過計算可以得到一系列的E(i,n)值，則當E(i,n)取最大值時節(jié)點選擇加入，至此，節(jié)點i的簇頭選取過程結(jié)束。

3) 在數(shù)據(jù)傳輸階段，有如下能量消耗模型[10]：傳感器節(jié)點能耗模型主要包括：感知消費、通信消費和數(shù)據(jù)處理消費，其中，通信能耗占主要部分，也是研究的對象。根據(jù)已知文獻資料，簇頭節(jié)點i發(fā)送l比特數(shù)據(jù)到距離d處的基站所需要消耗的能量為[11]

ETx(l,d)=l·Eelec+l·εamp·dα

(5)

式中:Eelec為發(fā)射和接收電路的單位能量消耗；εamp為傳輸放大電路的能量消耗；α為多路徑損失指數(shù)，當傳輸距離小于某一個閾值時，使用自由空間模型的功率放大損耗，α取值為2；當傳輸距離大于或等于閾值時，其值為4，使用多徑衰減模型進行功率放大損耗。

顯然，當傳輸距離大于某一個閾值時，會導致能量消耗成指數(shù)增長，因此，本文在數(shù)據(jù)傳輸階段的突破點即為此，參考文獻[9]，并在其基礎(chǔ)上進一步優(yōu)化了數(shù)據(jù)分發(fā)規(guī)則，其基本思想是：利用簇頭節(jié)點的鄰接信息表，選擇一個CH作為另一個CH的中繼節(jié)點來傳輸數(shù)據(jù)。根據(jù)上面的能量公式，很容易證明采用轉(zhuǎn)發(fā)中繼模型能夠取得更優(yōu)的能量耗散效果，如文獻[9]所采用的模型，基本思想為找到簇頭CH0的前鄰簇頭節(jié)點，將數(shù)據(jù)按照下式進行轉(zhuǎn)發(fā)

(6)

在此，本文認為：距離簇頭節(jié)點越遠的節(jié)點承擔越少的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)是一種更加優(yōu)化的選擇。證明如下：首先，通過基站存儲的節(jié)點位置信息，對d1,d2,…,di,…,dm進行排序，并假設(shè)距離由小到大排序結(jié)果為：d1,d2,…,di,…,dm，在此條件下，提出改進后的數(shù)據(jù)分發(fā)公式為

(7)

容易證明m的取值不會影響最終的結(jié)果，為簡化證明，僅以m=3來代表證明，過程如下。

當m=3時

(8)

而

(9)

兩式相減,即

(10)

總結(jié)整個算法過程的要點有：

1) 考慮節(jié)點能量和距離因素，重新定義閾值公式;

2) 通過新閾值公式初步查找符合條件的簇頭節(jié)點;

3) 簇頭節(jié)點和普通節(jié)點之間雙向選擇過程，綜合考慮節(jié)點通信范圍和簇頭節(jié)點當前能量;

4) 根據(jù)新的數(shù)據(jù)分發(fā)思想進行多跳數(shù)據(jù)傳輸。

3 仿真與分析

實驗采用Matlab模擬運行改進后的算法，同時將仿真結(jié)果與經(jīng)典LEACH算法進行比較。實驗中用到的參數(shù)如表1所示。

表1 模型相關(guān)初始參數(shù)

存活節(jié)點個數(shù)比較與死亡節(jié)點比例比較分別如圖1、圖2所示。

圖1 存活節(jié)點個數(shù)與循環(huán)次數(shù)關(guān)系Fig.1 Number of alive node vs number of cycles

圖2 死亡節(jié)點比例與循環(huán)次數(shù)關(guān)系圖Fig.2 Proportion of dead nodes vs number of cycles

從仿真結(jié)果可以得知，改進后的LEACH協(xié)議(IMP-LEACH)在相同循環(huán)次數(shù)下存活節(jié)點個數(shù)明顯比改進之前的多，并且從橫軸可以得知，原LEACH協(xié)議在大約1239次循環(huán)之后就再無存活節(jié)點了，而改進后這一數(shù)值提高到了1768，說明改進后的協(xié)議能極大地延緩節(jié)點死亡時間；通過仿真結(jié)果導出的數(shù)據(jù)所制作的節(jié)點死亡比例與循環(huán)次數(shù)的關(guān)系圖同樣可以看出，改進后的協(xié)議在延長節(jié)點壽命方面有重大提升，尤其是進入傳感器網(wǎng)絡(luò)運行后期階段，這種差異更加明顯。

4 總結(jié)

本文在已有的相關(guān)LEACH協(xié)議基礎(chǔ)上做了深入改進，在簇頭選取的過程中增加考慮簇頭節(jié)點當前能量及其簇內(nèi)節(jié)點個數(shù)，綜合考慮簇頭與節(jié)點之間的選擇，在數(shù)據(jù)傳輸階段，采用新的多跳數(shù)據(jù)傳輸方式，并從數(shù)學角度證明了新的數(shù)據(jù)傳輸方式更加節(jié)能。最后，通過對協(xié)議算法的仿真研究，得出了與預(yù)期一致的實驗觀點，證明了改進后的協(xié)議在延長WSN網(wǎng)絡(luò)壽命方面確實有重大提升。