潘琢金 陳天毅 王傳云 楊 華

(沈陽航空航天大學計算機學院 遼寧 沈陽 110136)

0 引 言

由于構(gòu)成無線傳感器網(wǎng)絡(luò)(WSN)的節(jié)點通常由電池供電,能量有限,因此節(jié)能是路由算法設(shè)計中的一個關(guān)鍵點。大部分有關(guān)無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究設(shè)定的應(yīng)用場景都是單基站環(huán)境。事實上,有很多的應(yīng)用場景如森林火災(zāi)檢測,需要多基站確保網(wǎng)絡(luò)的連通,出于保護基站的目的或由于基站不易部署等原因,基站需要放在待檢測區(qū)域的外圍。

針對單基站部署于網(wǎng)絡(luò)外的場景,文獻[1]提出讓靠近基站的簇更小,從而為這些簇頭留出更多的能量用于簇間轉(zhuǎn)發(fā),很好地平衡了節(jié)點的能量消耗,但該協(xié)議不適用于多基站環(huán)境。針對多基站部署于網(wǎng)絡(luò)內(nèi)的場景,文獻[2]采用相遇蟻群算法獲得了更快的路由收斂速度,但其網(wǎng)絡(luò)拓撲是平面網(wǎng)狀的結(jié)構(gòu),一是難以避免熱點問題,二是路由的尋找與維護依然十分復(fù)雜。文獻[3]利用Q學習算法一定程度上避免了使用剩余能量少的節(jié)點做轉(zhuǎn)發(fā)。文獻[4]針對基站隨機部署的場景進行研究,通過動態(tài)調(diào)整簇半徑優(yōu)化能耗。針對多基站部署在網(wǎng)絡(luò)外的場景,文獻[5]設(shè)計了考慮QoS的路由協(xié)議MSO-ETSSEP并仿真證實了多基站比單基站在延長網(wǎng)絡(luò)壽命方面更有優(yōu)勢,但其網(wǎng)絡(luò)模型中需要包含具有更高能量的節(jié)點。文獻[6]的協(xié)議使用考慮路徑能耗、路徑最小剩余能量以及節(jié)點到基站跳數(shù)的簇間多跳轉(zhuǎn)發(fā)來節(jié)省能量,延長了網(wǎng)絡(luò)的使用壽命,但需要節(jié)點能夠記錄所有其他節(jié)點的位置和能量以便尋找路徑和維護路由表,增加了協(xié)議的復(fù)雜度,且在每輪開始前所有節(jié)點向基站傳輸剩余能量會消耗較多的能量。文獻[7]在節(jié)點上使用三扇區(qū)天線,僅利用節(jié)點的大概位置選擇路由,避免了與查找定位信息相關(guān)的復(fù)雜計算,且算法可用于移動的WSN網(wǎng)絡(luò)。分簇路由協(xié)議由于其節(jié)點能耗均衡且可擴展性好被廣泛使用[8]。盡管LEACH協(xié)議[9]最初是為單基站部署于網(wǎng)絡(luò)中心的應(yīng)用場景設(shè)計的,但其思路依然可以用在多基站部署于檢測區(qū)域外的場景下。文獻[10]在考慮節(jié)點剩余能量的同時優(yōu)化簇頭數(shù)量,與LEACH算法相比降低了節(jié)點功耗。文獻[11]基于改進Bayes估計的數(shù)據(jù)融合節(jié)點選取方法一定程度上實現(xiàn)了節(jié)點能耗均衡,提高了數(shù)據(jù)傳輸正確率。文獻[12]提出了一種基于能量質(zhì)心的分簇路由協(xié)議EECRP,當基站位于網(wǎng)絡(luò)中時,其效果優(yōu)于LEACH、LEACH-C[13]和GEEC[14]。大部分LEACH協(xié)議的改進版本都對閾值函數(shù)進行修改,目的是在選簇頭時考慮到節(jié)點的位置和剩余能量,從而讓簇頭選擇結(jié)果更加合理,但這些協(xié)議仍然基于節(jié)點每輪生成一個隨機數(shù)與閾值函數(shù)進行比較的方法讓節(jié)點自選舉出簇頭,這種方法每輪選出的簇頭數(shù)量波動較大。

針對以上問題,結(jié)合多基站部署于網(wǎng)絡(luò)外圍的場景特征,本文提出一種適用于多基站環(huán)境的帶有中轉(zhuǎn)節(jié)點的分簇路由協(xié)議MSCRR(Multi-Sink Clustering Routing Protocol with Relay Nodes),使用一種新的簇頭自選舉方法來保證一輪中簇頭個數(shù)的穩(wěn)定,通過優(yōu)先選擇簇內(nèi)質(zhì)心位置剩余能量高的節(jié)點做簇頭,并讓網(wǎng)絡(luò)邊緣節(jié)點協(xié)助簇頭轉(zhuǎn)發(fā)消息至基站,以此來平衡節(jié)點的能耗,減輕簇頭的負擔,降低網(wǎng)絡(luò)的總能耗,延長網(wǎng)絡(luò)的使用壽命。

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

1.1 網(wǎng)絡(luò)拓撲

1.2 能耗模型

對于實驗中節(jié)點能耗的計算,使用文獻[9]中提到的如圖1所示的一階無線電模型。所有節(jié)點初始能量相同且同時開始工作。Eelec是發(fā)射機和接收機所需的能量,εamp是發(fā)射放大器所需的能量,Ecomp是數(shù)據(jù)融合需要的能量。

圖1 一階無線電模型

向距離d的位置發(fā)送k比特數(shù)據(jù)消耗的能量見式(1),接收k比特數(shù)據(jù)消耗的能量見式(2),對k比特消息做數(shù)據(jù)融合消耗的能量見式(3)。

ETx(k,d)=Eelec×k+εamp×k×d2

(1)

ERx(k)=Eelec×k

(2)

EC(k)=Ecomp×k

(3)

1.3 實驗假設(shè)

該協(xié)議的仿真運行需滿足以下假設(shè):

1) 所有節(jié)點需周期性地采集并匯報數(shù)據(jù);

2) 節(jié)點最大通信半徑為正方形區(qū)域?qū)蔷€長;

3) 節(jié)點最大通信半徑內(nèi)至少有一個基站;

4) 所有節(jié)點以及基站的時間都是同步的;

5) 節(jié)點已知自己的精確位置,且位置不變;

6) 未入簇的節(jié)點需直接向基站發(fā)送數(shù)據(jù)消息。

2 算 法

數(shù)據(jù)傳輸?shù)穆酚蛇^程按輪進行,一輪分為兩個階段:成簇階段和傳輸階段。為減少通信次數(shù),算法由時間驅(qū)動,所有節(jié)點會按照事先制定好的時間表完成相應(yīng)的任務(wù),無須與其他節(jié)點或基站協(xié)商。每一輪的時長固定,該時長的選取需確保所有節(jié)點均能完成一輪內(nèi)的數(shù)據(jù)傳輸任務(wù)。

2.1 成簇階段

1) 簇頭自選舉。n是節(jié)點編號,N是網(wǎng)絡(luò)中的節(jié)點個數(shù),P是網(wǎng)絡(luò)內(nèi)所有節(jié)點中簇頭的比例,r是當前輪數(shù),其中n和r從0開始。當以上參數(shù)滿足式(4)時,該節(jié)點自選舉為簇頭。

(4)

2) 簇頭選擇優(yōu)化。由于自選舉得到的簇頭未必合理,需要進行優(yōu)化,優(yōu)化的思路是優(yōu)先選擇簇內(nèi)靠近質(zhì)心且剩余能量更高的節(jié)點。原簇頭將每個節(jié)點與簇內(nèi)其他節(jié)點的距離平方的和Sdist以及該節(jié)點的已消耗能量Eu組成pair〈Sdist,Eu〉,其中Sdist按照式(5)計算,Nc為簇內(nèi)節(jié)點個數(shù),節(jié)點自己的坐標為(X,Y),簇內(nèi)其他節(jié)點的坐標為(Xi,Yi)。根據(jù)Sdist和Eu的值對pair〈Sdist,Eu〉按從小到大排序,規(guī)定若x1

(5)

3) 中轉(zhuǎn)節(jié)點選擇。選擇中轉(zhuǎn)節(jié)點的過程依然由原簇頭完成。若新簇頭將消息發(fā)送給中轉(zhuǎn)節(jié)點,再由中轉(zhuǎn)節(jié)點轉(zhuǎn)發(fā)至基站預(yù)期產(chǎn)生的總能耗小于簇頭直接發(fā)送給基站所需的能耗,則應(yīng)選擇中轉(zhuǎn)節(jié)點。即:

[Eelec+εamp×(d1+d2)2]>

[3Eelec+εamp×(d12+d22)]

(6)

式(6)可化簡為:

εampd1d2-Eelec>0

(7)

式中:d1是新簇頭到候選中轉(zhuǎn)節(jié)點的距離,d2是候選中轉(zhuǎn)節(jié)點到基站的距離。若存在多個候選中轉(zhuǎn)節(jié)點,由式(7),可為每個中轉(zhuǎn)節(jié)點設(shè)定如式(8)的評分函數(shù),選取分數(shù)最高的節(jié)點作為本輪的中轉(zhuǎn)節(jié)點。為防止與基站接近的節(jié)點因總是成為中轉(zhuǎn)節(jié)點而過快失效,剩余能量低于20%的節(jié)點不參與中轉(zhuǎn)節(jié)點競選。

SCORE=εampd1d2-Eelec

(8)

2.2 傳輸階段

節(jié)點按TDMA發(fā)送數(shù)據(jù)給簇頭。簇內(nèi)若存在中轉(zhuǎn)節(jié)點,則簇頭將消息發(fā)送給中轉(zhuǎn)節(jié)點,否則,簇頭、中轉(zhuǎn)節(jié)點和孤立節(jié)點按TDMA將數(shù)據(jù)消息發(fā)送給離自己最近的基站。

2.3 運行流程

使用MSCRR路由算法進行一輪數(shù)據(jù)收集的具體步驟如下:

1) 所有節(jié)點根據(jù)式(4)完成自選舉,選為簇頭的節(jié)點廣播公告消息ADV_CH,告知鄰居節(jié)點它們是簇頭。

2) 當所有ADV_CH消息都到達目標節(jié)點時,非簇頭節(jié)點根據(jù)ADV_CH消息選最近的簇頭,發(fā)送JOIN_CH消息,需包含自己的位置信息和剩余能量。若節(jié)點未收到ADV_CH消息,則成為孤立節(jié)點,本輪不入簇,直接與基站通信。

3) 當所有JOIN_CH消息到達目標簇頭時,簇頭收到入簇申請并暫時保存;基站廣播公告信息,告知所有節(jié)點它們的編號和位置。

4) 所有ADV_BS消息到達后,簇頭根據(jù)JOIN_CH消息按照2.1節(jié)(2)中的方法尋找簇內(nèi)是否有更適合成為簇頭的節(jié)點,若有則尋找最適合的一個令其在本輪擔任新簇頭,將其編號附加進SCHED_CH消息;簇頭接著按照2.1節(jié)(3)中的方法尋找簇內(nèi)是否有適合為簇頭做中轉(zhuǎn)的節(jié)點,若有則尋找最合適的一個,并將其編號附加進SCHED_CH;簇頭廣播SCHED_CH給簇內(nèi)節(jié)點。

5) 當簇內(nèi)所有節(jié)點收到SCHED_CH消息后,節(jié)點檢查自己是否為新簇頭或中轉(zhuǎn)節(jié)點。如果是新簇頭則準備接收來自簇內(nèi)的數(shù)據(jù)消息,如果是中轉(zhuǎn)節(jié)點則準備接收來自簇頭的數(shù)據(jù)消息。沒有中轉(zhuǎn)節(jié)點的簇頭、中轉(zhuǎn)節(jié)點、孤立節(jié)點將直連基站。需要直連基站的節(jié)點選擇最近的基站發(fā)送JOIN_BS。

6) 所有JOIN_BS消息到達基站時,基站發(fā)出SCHED_BS。

7) 所有SCHED_BS消息到達節(jié)點時,普通節(jié)點開始按TDMA向簇頭發(fā)送DATA。

8) 簇頭收齊DATA消息后做數(shù)據(jù)融合,有中轉(zhuǎn)節(jié)點的簇頭發(fā)消息給中轉(zhuǎn)節(jié)點。

9) 所有中轉(zhuǎn)消息到達中轉(zhuǎn)節(jié)點后,沒有中轉(zhuǎn)節(jié)點的簇頭、中轉(zhuǎn)節(jié)點、孤立節(jié)點開始按TDMA發(fā)送消息到基站。

10) 若一輪只發(fā)一次數(shù)據(jù),則該輪結(jié)束,否則,繼續(xù)傳輸數(shù)據(jù)直到一輪的時間結(jié)束。接著,重復(fù)以上步驟,直到所有節(jié)點失效。

協(xié)議運行需要的消息類型如表1所示。

表1 協(xié)議運行需要的消息類型

圖2是MSCRR路由協(xié)議運行效果的示意圖。

3 仿真實驗

3.1 仿真參數(shù)

表2 仿真參數(shù)

大部分與LEACH相似的路由算法使用的簇頭占總節(jié)點數(shù)的比例P的值是0.05,因為通過實驗證明單基站條件下P為0.05時網(wǎng)絡(luò)的總能耗最小。但在基站的位置改變、基站數(shù)量增加,以及簇頭廣播覆蓋范圍改變后,P的值需要重新確定。通過仿真實驗發(fā)現(xiàn),三種算法無論哪一種,前200輪內(nèi)都不會出現(xiàn)節(jié)點失效的情況,因此每種算法通過100次隨機實驗,每次節(jié)點都隨機且均勻地布撒在正方形區(qū)域內(nèi),測試前200輪所有節(jié)點的總能量消耗的平均值,結(jié)果如圖3所示?？梢?當P值選取為0.15時,總能耗最低。

圖3 簇頭所占比例與能耗的關(guān)系

3.2 仿真結(jié)果

圖4顯示了其中一次實驗中LEACH協(xié)議經(jīng)典的簇頭自選舉方法與本文中的簇頭自選舉算法每輪選出的簇頭數(shù)的對比。LEACH每輪選出的簇頭數(shù)不同,波動較大,當簇頭比例較小時甚至會出現(xiàn)無法選出簇頭的情況,有節(jié)點失效后,未選出簇頭的概率會增加。若一輪中選不出簇頭,則所有節(jié)點需要直接與基站通信,這會導(dǎo)致大量的能量浪費。選出過多的簇頭則會導(dǎo)致部分簇頭建立的簇沒有節(jié)點加入,該簇頭仍需直接與基站通信,造成不必要的能量浪費。本文算法可保證有節(jié)點失效前,選出的簇頭個數(shù)固定為NP,有節(jié)點失效后,選不出簇頭的次數(shù)也較少。

圖4 不同協(xié)議每輪選出的簇頭數(shù)

為消除單次實驗的偶然性,以下所有實驗的結(jié)果均來自100次隨機實驗的平均值,每次實驗節(jié)點隨機且均勻地布撒在指定的正方形區(qū)域中,每一輪只收集一次數(shù)據(jù)。

圖5顯示了100次實驗每輪結(jié)束后網(wǎng)絡(luò)中剩余節(jié)點數(shù)的均值與運行輪數(shù)的關(guān)系。表3顯示了網(wǎng)絡(luò)中1%、25%、50%、75%的節(jié)點失效在100次實驗中最早出現(xiàn)的輪數(shù),當更多的節(jié)點失效時,大面積的區(qū)域?qū)o法被檢測,此時網(wǎng)絡(luò)變得幾乎不可用,故不再討論,此時應(yīng)該向網(wǎng)絡(luò)中補充新的節(jié)點。從實驗結(jié)果可以看出,EECRP和MSCRR算法都有效地增加了1%、25%、50%、75%節(jié)點失效時的輪數(shù),有效地延長了網(wǎng)絡(luò)壽命,本文算法MSCRR表現(xiàn)更優(yōu)。由于EECRP協(xié)議存在保護機制,即當一輪中某簇頭與目標基站距離大于一定值時,該簇頭將暫存數(shù)據(jù)不發(fā),直到加入其他簇,該機制雖然能夠節(jié)省能量但會引發(fā)暫時的丟包,尤其是在網(wǎng)絡(luò)中剩余節(jié)點較少的情況下,而本文算法要求數(shù)據(jù)消息必須發(fā)送至基站,非節(jié)點或基站失效等特殊情況下,不存在丟包現(xiàn)象。

表3 節(jié)點失效所經(jīng)歷的輪數(shù)

圖5 剩余節(jié)點數(shù)與運行輪數(shù)的關(guān)系

4 結(jié) 語

本文算法使用優(yōu)先選擇靠近簇內(nèi)質(zhì)心位置的高能量節(jié)點做簇頭的方法以及中轉(zhuǎn)節(jié)點機制,相比傳統(tǒng)算法有效地降低了網(wǎng)絡(luò)中的平均通信距離,進而降低了由通信產(chǎn)生的能耗;使用周期性輪換的簇頭自選舉方法有效地控制了網(wǎng)絡(luò)中的簇頭數(shù)量,避免了由于簇頭過多或過少造成額外的能量浪費,且無須基站進行集中調(diào)度,減少了因集中調(diào)度產(chǎn)生的能量開銷。同時,多基站的部署以及中轉(zhuǎn)節(jié)點的機制也可讓網(wǎng)絡(luò)的覆蓋面積更大,并可應(yīng)對部分基站失效的情況,使網(wǎng)絡(luò)的魯棒性更好。本文算法采用節(jié)點自選舉的方式產(chǎn)生簇頭,成簇階段不依賴基站,該方法可改為由基站集中控制的算法。集中控制的算法會在節(jié)點發(fā)送給基站自身的位置和能量等附加信息以及接收來自基站的控制報文上消耗更多的能量,但基站可以從全局考慮做出更合理的分簇方案,并為節(jié)點提前規(guī)劃合適的路由,這是未來進一步研究的方向之一。