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

(1.上海交通大學(xué)微納電子學(xué)系，上海 200240； 2.近地面感知與探測(cè)重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫 214000)

0 引言

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

1 LEACH協(xié)議描述

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) 在判斷是否為簇頭的過(guò)程中，加入節(jié)點(diǎn)當(dāng)前能量這個(gè)考量因素，提出

(2)

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

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

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

條件1滿足

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

(3)

式中，d(i,CH)

條件2在滿足條件1的情況下，進(jìn)行如下運(yùn)算

(4)

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

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

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

(5)

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

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

(6)

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

(7)

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

當(dāng)m=3時(shí)

(8)

而

(9)

兩式相減,即

(10)

總結(jié)整個(gè)算法過(guò)程的要點(diǎn)有：

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

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

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

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

3 仿真與分析

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

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

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

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

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

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

4 總結(jié)

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