劉偉強(qiáng)， 蔣 華， 王 鑫

(桂林電子科技大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，廣西 桂林 541004)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)現(xiàn)代工業(yè)革命的前沿陣地，其中無線傳感器網(wǎng)絡(luò)路由協(xié)議是其中發(fā)展的重點(diǎn)[1]。能源問題是制約無線傳感器網(wǎng)絡(luò)發(fā)展的關(guān)鍵因素，因此，大量低功耗路由協(xié)議被提出，其中，PEGASIS (power-efficient gathering in sensor information systems)協(xié)議是無線傳感器網(wǎng)絡(luò)中經(jīng)典的低功耗路由協(xié)議之一，它是由Stephanie Lmdsey等人在Leach協(xié)議基礎(chǔ)上提出的鏈?zhǔn)絽f(xié)議[2]。該協(xié)議的主要思想是將網(wǎng)絡(luò)中所有節(jié)點(diǎn)連成一條鏈，基站在鏈中選擇一個簇頭，通信時信息從鏈的兩端開始沿鏈將數(shù)據(jù)傳輸給簇頭，再由簇頭發(fā)送給基站。相對于Leach協(xié)議，該協(xié)議在一定程度上提高了網(wǎng)絡(luò)能量利用率，但也產(chǎn)生了通信時延過長，遠(yuǎn)離基站的簇頭節(jié)點(diǎn)容易死亡的缺點(diǎn)[3]。

針對PEGASIS協(xié)議的這些不足，本文提出過一種能解決這些問題的PEGASIS-I協(xié)議[4]，但PEGASIS-I協(xié)議存在根節(jié)點(diǎn)能量負(fù)載過大、容易死亡的缺點(diǎn)。文獻(xiàn)[5]在解決無線傳感器網(wǎng)絡(luò)多跳通信協(xié)議中靠近基站的簇頭節(jié)點(diǎn)容易死亡的缺點(diǎn)時提出了“熱區(qū)”輪轉(zhuǎn)機(jī)制，該機(jī)制的作用是在多跳分簇協(xié)議中，當(dāng)靠近基站的簇因大量轉(zhuǎn)發(fā)其它簇的信息而能量消耗過大時，該機(jī)制可以將靠近基站的簇的轉(zhuǎn)發(fā)任務(wù)轉(zhuǎn)移到其它能量充足的簇身上。文獻(xiàn)[6]提出“休眠/活動節(jié)點(diǎn)對”機(jī)制，該機(jī)制使網(wǎng)絡(luò)中距離最近的兩相鄰節(jié)點(diǎn)組成“休眠/活動點(diǎn)節(jié)對”，發(fā)送信息時，該節(jié)點(diǎn)對中一個節(jié)點(diǎn)處于活動狀態(tài),另一個節(jié)點(diǎn)處于休眠狀態(tài)。針對PEGASIS-I協(xié)議的缺點(diǎn)，且受文獻(xiàn)[5，6]的啟示，在PEGASIS-I協(xié)議的基礎(chǔ)上,本文提出了一個新協(xié)議，該協(xié)議的改進(jìn)之處在于增加了“熱”節(jié)點(diǎn)輪轉(zhuǎn)機(jī)制與“相似”節(jié)點(diǎn)群擇一發(fā)送機(jī)制，很好地解決了PEGASIS-I協(xié)議存在的問題。

1 PEGASIS-I[4]協(xié)議描述

PEGASIS-I協(xié)議是本文作者在改進(jìn)PEGASIS的基礎(chǔ)上提出的一個新協(xié)議，該協(xié)議的具體步驟參看文獻(xiàn)[4]，其主要思路是：該協(xié)議將監(jiān)測區(qū)域看成是以基站為中心的圓形區(qū)域，基站生成參數(shù)θ(0<θ<π/2)并將圓形區(qū)域分成2π/θ個以基站為中心的扇形子區(qū)域，扇形子區(qū)域內(nèi)節(jié)點(diǎn)與節(jié)點(diǎn)形成通信路由樹，數(shù)據(jù)先從樹葉傳輸至樹根，再由樹根發(fā)送至基站，如圖1所示。

圖1 PEGASIS-I協(xié)議通信圖

PEGASIS-I協(xié)議利用樹的特性使節(jié)點(diǎn)與節(jié)點(diǎn)之間避免了長鏈，推遲了第一個節(jié)點(diǎn)的死亡時間,延長了網(wǎng)絡(luò)生存周期；利用扇形分區(qū)的方式將網(wǎng)絡(luò)分成若干個區(qū)域，減小了網(wǎng)絡(luò)通信時延；簡化網(wǎng)絡(luò)維護(hù)方式，降低網(wǎng)絡(luò)維護(hù)消耗。它雖然解決了PEGASIS協(xié)議的缺點(diǎn)，但它本身存在根節(jié)點(diǎn)能量負(fù)載過大的問題，這個問題導(dǎo)致根節(jié)點(diǎn)容易死亡，從而形成監(jiān)測空洞。為了解決該問題,本文提出了第2節(jié)所描述的新協(xié)議。

2 新協(xié)議原理

2.1 新協(xié)議描述

定義1：“熱”節(jié)點(diǎn)是具有如下特點(diǎn)的節(jié)點(diǎn)：它屬于一顆樹的非葉子節(jié)點(diǎn)，且其能量低于網(wǎng)絡(luò)平均能量的50 %。

定義2：“相似”節(jié)點(diǎn)群是一組節(jié)點(diǎn)集合，組內(nèi)節(jié)點(diǎn)之間的距離在閾值D內(nèi)，且感知信息的差別度在閾值T內(nèi)。

定義3：“相似”節(jié)點(diǎn)群擇一發(fā)送是指：每一輪通信時，以一個節(jié)點(diǎn)的感知信息代表整個“相似”節(jié)點(diǎn)群所有節(jié)點(diǎn)的感知信息，即群內(nèi)一個節(jié)點(diǎn)發(fā)送感知信息時其它節(jié)點(diǎn)不發(fā)送自身的感知信息。比如：對于溫度傳感器，在某一小范圍內(nèi)各處的溫度相差不大，可以稱這一小范圍內(nèi)的節(jié)點(diǎn)為“相似”節(jié)點(diǎn)群，群里一個節(jié)點(diǎn)感知的溫度可以代表其它節(jié)點(diǎn)感知的溫度。

針對PEGASIS-I協(xié)議的缺點(diǎn)，本文在PEGASIS-I協(xié)議的基礎(chǔ)上提出一個新的改進(jìn)協(xié)議。新協(xié)議的改進(jìn)主要體現(xiàn)在2個方面:一方面是增加了“熱”節(jié)點(diǎn)輪轉(zhuǎn)機(jī)制，它的作用是當(dāng)出現(xiàn)“熱”節(jié)點(diǎn)時，將“熱”節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)轉(zhuǎn)移到其它能量充足的節(jié)點(diǎn)身上，使自身變成葉子節(jié)點(diǎn)，減輕自身的能量負(fù)載，延長它的生存期；另一方面是實(shí)施“相似”節(jié)點(diǎn)擇一發(fā)送原則。新協(xié)議與PEGASIS-I協(xié)議一樣，也分為3個階段:

第一階段區(qū)域劃分階段:與第二階段路由形成階段與PEGASIS-I協(xié)議完全相同，在此不多贅述。

第三階段，數(shù)據(jù)通信階段:新協(xié)議對PEGASIS-I協(xié)議改進(jìn)之處主要體現(xiàn)在本階段，新協(xié)議數(shù)據(jù)通信階段規(guī)則如下：

1)如果節(jié)點(diǎn)屬于“相似”節(jié)點(diǎn)群，則只有到它的時間序號時它才發(fā)送自身的感知信息。在它所在的“相似”節(jié)點(diǎn)群其它節(jié)點(diǎn)發(fā)送信息時，如果它是葉子節(jié)點(diǎn)，則進(jìn)入休眠狀態(tài);如果它是非葉子節(jié)點(diǎn)，則除了不發(fā)送自身感應(yīng)的信息外，轉(zhuǎn)發(fā)數(shù)據(jù)功能正常執(zhí)行。

2)如果一個節(jié)點(diǎn)有多個子節(jié)點(diǎn)，它必須為每個子節(jié)點(diǎn)分配數(shù)據(jù)發(fā)送時間段，避免數(shù)據(jù)接收沖突，且父節(jié)點(diǎn)收到子節(jié)點(diǎn)發(fā)來的數(shù)據(jù)后須回復(fù)一條接收完畢的信息，當(dāng)父節(jié)點(diǎn)將自己所有子節(jié)點(diǎn)的數(shù)據(jù)收集完后將子節(jié)點(diǎn)的數(shù)據(jù)與自己的數(shù)據(jù)融合，然后將融合后的數(shù)據(jù)發(fā)送給自己的父節(jié)點(diǎn)。如果子節(jié)點(diǎn)發(fā)送完信息后過一段時間沒有收到父節(jié)點(diǎn)的回復(fù)信息，則認(rèn)為父節(jié)點(diǎn)死亡，該子節(jié)點(diǎn)重新按照第二階段中的方法重新為自己確定父節(jié)點(diǎn)。如果父節(jié)點(diǎn)在規(guī)定的時間里沒有接收到相應(yīng)子節(jié)點(diǎn)的信息，則認(rèn)為該子節(jié)點(diǎn)要么是死亡，要么是休眠節(jié)點(diǎn)，不再等待該子節(jié)點(diǎn)的數(shù)據(jù)。

3)如果有新節(jié)點(diǎn)加入網(wǎng)絡(luò)中，新節(jié)點(diǎn)先將自己的位置信息單跳直接發(fā)送給基站，基站收到信息后根據(jù)它所在的位置確定它與基站的距離、它屬于哪個區(qū)域以及它是否屬于某一“相似”節(jié)點(diǎn)群，然后將這些信息廣播給新節(jié)點(diǎn)，新節(jié)點(diǎn)根據(jù)這些信息按照第二階段的方法加入到其所在子區(qū)域的路由樹中。

4)每隔N(本文中設(shè)定N=10)輪通信，所有節(jié)點(diǎn)發(fā)送包含節(jié)點(diǎn)能量的信息(在1到N-1輪中節(jié)點(diǎn)只需發(fā)送自身的感知信息而不需要發(fā)送能量信息)到基站，基站根據(jù)這一輪所有節(jié)點(diǎn)的感知信息重新得出“相似”節(jié)點(diǎn)群，并對所有節(jié)點(diǎn)的能量求平均值Eavg，然后將結(jié)果向所有節(jié)點(diǎn)廣播。網(wǎng)絡(luò)節(jié)點(diǎn)收到新的“相似”節(jié)點(diǎn)群信息后在后續(xù)的信息發(fā)送輪中按新的“相似”節(jié)點(diǎn)群信息中的時間序號發(fā)送數(shù)據(jù)，然后將信息中網(wǎng)絡(luò)節(jié)點(diǎn)平均值Eavg與自己的能量E進(jìn)行對比，執(zhí)行“熱”節(jié)點(diǎn)輪轉(zhuǎn)機(jī)制：

a.如果E

b.如果E

c.如果E≥Eavg/2，可以接受其它節(jié)點(diǎn)成為其子節(jié)點(diǎn)。

與PEGASIS-I協(xié)議對比可以發(fā)現(xiàn)，新協(xié)議的數(shù)據(jù)通信階段增加了第一條與第六條規(guī)則，這兩條規(guī)則中加入了“熱”節(jié)點(diǎn)輪轉(zhuǎn)機(jī)制與“相似”節(jié)點(diǎn)擇一發(fā)送原則。

2.2 “相似”節(jié)點(diǎn)群算法描述

基站計算機(jī)根據(jù)節(jié)點(diǎn)的位置坐標(biāo)與感知信息差別度計算“相似”節(jié)點(diǎn)群。采用的算法描述如下：1)基站根據(jù)節(jié)點(diǎn)坐標(biāo)計算每個節(jié)點(diǎn)到基站的距離與節(jié)點(diǎn)到節(jié)點(diǎn)之間的距離；2)基站選定距離基站最遠(yuǎn)且沒有被賦予“相似”節(jié)點(diǎn)群編號的節(jié)點(diǎn)賦予群編號并選定其作為“基”節(jié)點(diǎn);3)基站再依次遍歷其它沒有被賦予“相似”節(jié)點(diǎn)群編號的節(jié)點(diǎn)，如果被遍歷的節(jié)點(diǎn)與“基”節(jié)點(diǎn)的距離在閾值D內(nèi)且節(jié)點(diǎn)感應(yīng)的信息與“基”節(jié)點(diǎn)感知的信息差度在閾值T內(nèi)則對被遍歷的節(jié)點(diǎn)賦予與“基”節(jié)點(diǎn)相同的“相似”節(jié)點(diǎn)群編號，表明該節(jié)點(diǎn)加入了“基”節(jié)點(diǎn)所屬的“相似”節(jié)點(diǎn)群；4)如果所有節(jié)點(diǎn)全部被賦予“相似”節(jié)點(diǎn)群編號則算法結(jié)束，否則，跳轉(zhuǎn)到第(2)步。

執(zhí)行此算法后網(wǎng)絡(luò)內(nèi)所有擁有相同的“相似”節(jié)點(diǎn)群編號的節(jié)點(diǎn)為一個“相似”節(jié)點(diǎn)群，基站會根據(jù)群成員個數(shù)為群內(nèi)每個節(jié)點(diǎn)安排數(shù)據(jù)發(fā)送序號。

3 協(xié)議仿真與分析

3.1 新協(xié)議分析

與PEGASIS-I協(xié)議相比新協(xié)議增加了兩條改進(jìn)措施，一方面是增加了“熱”節(jié)點(diǎn)輪轉(zhuǎn)機(jī)制，當(dāng)非葉子節(jié)點(diǎn)的能量少于所有節(jié)點(diǎn)平均能量的50 %時，表明該節(jié)點(diǎn)能量負(fù)擔(dān)過重，繼續(xù)作為非葉子節(jié)點(diǎn)會導(dǎo)致其短時間內(nèi)死亡。為了避免該情況出現(xiàn)，協(xié)議運(yùn)用“熱”節(jié)點(diǎn)輪轉(zhuǎn)機(jī)制將非葉子節(jié)點(diǎn)的任務(wù)從該節(jié)點(diǎn)輪轉(zhuǎn)到其能量充足的其它節(jié)點(diǎn)上，保護(hù)能量弱的節(jié)點(diǎn)，達(dá)到延長網(wǎng)絡(luò)生存期的目的。另一方面，采用了“相似”節(jié)點(diǎn)群擇一發(fā)送機(jī)制，該機(jī)制使網(wǎng)絡(luò)中“相似”節(jié)點(diǎn)群里以一個節(jié)點(diǎn)的感知信息替代群里所有節(jié)點(diǎn)的感知信息，即滿足信息準(zhǔn)確度同時也使網(wǎng)絡(luò)通信量大大減少，有效延長了網(wǎng)絡(luò)生存時間。

3.2 協(xié)議仿真與結(jié)果分析

本文用Matlab軟件對2種協(xié)議進(jìn)行仿真，采用文獻(xiàn)[7]中的能量模型，分別從網(wǎng)絡(luò)生存時間與網(wǎng)絡(luò)能量負(fù)載均衡性兩方面來評價這兩種協(xié)議。為了實(shí)驗方便實(shí)驗中沒有設(shè)置信息差別度閾值T，“相似”節(jié)點(diǎn)群的確定僅由距離閾值D決定。實(shí)驗時節(jié)點(diǎn)位置隨機(jī)選取，單次實(shí)驗結(jié)果隨機(jī)因數(shù)大，故下面所有數(shù)據(jù)均為50次實(shí)驗取平均值的結(jié)果。實(shí)驗環(huán)境設(shè)置與文獻(xiàn)[4]相同，只增加了閾值屬性D=5 m的設(shè)置。

3.2.1 參數(shù)θ的確定

在新協(xié)議中參數(shù)θ的確定同PEGASIS-I協(xié)議一樣，也需要通過實(shí)驗來確定。為了實(shí)驗方便，θ值在π/8，π/6，π /4，π /3，π /2之中選取。圖2是當(dāng)θ取上述值時新協(xié)議運(yùn)行的節(jié)點(diǎn)存活數(shù)與輪數(shù)關(guān)系仿真圖。從圖與實(shí)驗數(shù)據(jù)可看出：當(dāng)θ取值為π /2時，網(wǎng)絡(luò)所有節(jié)點(diǎn)存活時間最短，新協(xié)議性能最差，當(dāng)θ取值為π/4時，網(wǎng)絡(luò)節(jié)點(diǎn)存活時間最長，新協(xié)議性能最好，故在該實(shí)驗條件下最合適的參數(shù)值設(shè)置是θ=π /4。

圖2 θ取不同值時網(wǎng)絡(luò)生存時間對比

3.2.2 能量負(fù)載均衡性

PEGASIS-I協(xié)議中根節(jié)點(diǎn)能量負(fù)載大，容易死亡，導(dǎo)致整個網(wǎng)絡(luò)能量消耗不平衡，新協(xié)議采用“熱”節(jié)點(diǎn)輪轉(zhuǎn)機(jī)制有效平衡了網(wǎng)絡(luò)能量負(fù)載。文中用某時刻的能量方差函數(shù)DE(t)來衡量網(wǎng)絡(luò)負(fù)載均衡性,DE(t)越小表示網(wǎng)絡(luò)負(fù)載勻衡性越好[7]。能量方差函數(shù)

(1)

式中Ei(t)為標(biāo)記為i的節(jié)點(diǎn)在t時刻的能量，G(t)為t時刻網(wǎng)絡(luò)平均能量，N為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)。

圖3是兩協(xié)議的能量方差與輪數(shù)關(guān)系圖，從圖中可以看到新協(xié)議的能量方差一直低于PEGASIS-I協(xié)議的方差，表明新協(xié)議的能量均衡性優(yōu)于PEGASIS-I協(xié)議，有利于網(wǎng)絡(luò)生命周期的延長。

圖3 兩協(xié)議的能量方差對比結(jié)果圖

3.2.3 網(wǎng)絡(luò)生存時間

圖4表示在實(shí)驗條件下兩協(xié)議的運(yùn)行情況,最大輪數(shù)為2 000輪。文中以50 %節(jié)點(diǎn)死亡時所經(jīng)過的輪數(shù)作為網(wǎng)絡(luò)生存時間[8]。對第一個節(jié)點(diǎn)開始死亡輪數(shù)、20 %節(jié)點(diǎn)死亡輪數(shù)、50 %節(jié)點(diǎn)死亡輪數(shù)、70 %節(jié)點(diǎn)死亡輪數(shù)、全部節(jié)點(diǎn)死亡輪數(shù)進(jìn)行了比較，結(jié)果如表1所示。

表1 兩種協(xié)議生命期對比結(jié)果

從表1中的結(jié)果可以看出:新協(xié)議比PEGASIS-I協(xié)議的生存周期提高了22.2 %，第一個節(jié)點(diǎn)死亡時間更是大大推遲了140.8 %，20 %,70 %,100 %節(jié)點(diǎn)死亡時間也都得到了很大的改善。

圖4 網(wǎng)絡(luò)生存節(jié)點(diǎn)數(shù)與輪數(shù)關(guān)系圖

新協(xié)議相比于PEGASIS-I協(xié)有如下優(yōu)點(diǎn)：1)根節(jié)點(diǎn)能量負(fù)載較輕，不容易死亡，避免出現(xiàn)監(jiān)測空洞；2)網(wǎng)絡(luò)通信量少，有效延長了網(wǎng)絡(luò)生存時間，同時也減少了節(jié)點(diǎn)訪問無線信道的競爭。

4 結(jié) 論

本文提出的新協(xié)議解決了PEGASIS-I協(xié)議這一缺點(diǎn)，使其更完善。分析和仿真結(jié)果表明：改進(jìn)后的算法在延長網(wǎng)絡(luò)生存時間有更優(yōu)越的性能。但“相似”節(jié)點(diǎn)機(jī)制只適合于節(jié)點(diǎn)密集型網(wǎng)絡(luò)，在此類型網(wǎng)絡(luò)中可以大量減少通信量，在稀疏網(wǎng)絡(luò)中不適合使用，因為此類網(wǎng)絡(luò)中“相似”節(jié)點(diǎn)群少，不能大量減少通信量，反而需要節(jié)點(diǎn)定期接收基站的廣播信息，得不償失，所以，新協(xié)議適合于靜態(tài)節(jié)點(diǎn)密集布署型網(wǎng)絡(luò)。另外，“相似”節(jié)點(diǎn)機(jī)制中的距離參數(shù)D與信息差異度T要根據(jù)具體的應(yīng)用來確定。

參考文獻(xiàn):

[1] 楊 軍,張德運(yùn),張云翼.基于分簇的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)匯聚傳送協(xié)議[J].軟件學(xué)報，2010,21(5): 1127-1137.

[2] Lee Y H,Lee K O,Lee H J,et al.CBERP:Cluster-based energy efficient routing protocol for wireless sensor networks[C]∥Proceedings of 12th International Conference on Networking,VLSI and Signal Processing,Cambridge,2010:24-28.

[3] Stephanie Lmdsey,Cauligi S Raghavendra.PEGASIS:Power-efficient gathering in sensor information systems[J].Proceedings of IEEE Aerospace Conference ,2002,3(3):1125-1130.

[4] 劉偉強(qiáng)，蔣 華，王 鑫.無線傳感器網(wǎng)絡(luò)中PEGASIS協(xié)議的研究與改進(jìn)[J].傳感技術(shù)學(xué)報,2013,26(12):1764-1769.

[5] 朱 康.無線傳感器分布式多跳分層路由協(xié)議研究與設(shè)計[D].成都：電子科技大學(xué)，2013.

[6] 鄧 潔,程良倫.大規(guī)模無線傳感器網(wǎng)絡(luò)多優(yōu)先級自適用分簇路由協(xié)議[J].傳感器與微系統(tǒng)，2010,29(8):78-81.

[7] 蔣暢江,石為人,唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].軟件學(xué)報，2012,23(5):1222-1232.

[8] Sun C, Yin R R, Hao X C, et al. Connected dominating set topology control algorithm of heterogeneous wireless sensor network-s[J].Journal of Software, 2011,22(9):2137-2148.