一種適用于多基站環境的WSN分簇路由協議

潘琢金 陳天毅 王傳云 楊 華

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

0 引 言

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

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

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

1 網絡模型

1.1 網絡拓撲

1.2 能耗模型

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

圖1 一階無線電模型

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

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

(1)

ERx(k)=Eelec×k

(2)

EC(k)=Ecomp×k

(3)

1.3 實驗假設

該協議的仿真運行需滿足以下假設:

1) 所有節點需周期性地采集并匯報數據;

2) 節點最大通信半徑為正方形區域對角線長;

3) 節點最大通信半徑內至少有一個基站;

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

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

6) 未入簇的節點需直接向基站發送數據消息。

2 算 法

數據傳輸的路由過程按輪進行,一輪分為兩個階段:成簇階段和傳輸階段。為減少通信次數,算法由時間驅動,所有節點會按照事先制定好的時間表完成相應的任務,無須與其他節點或基站協商。每一輪的時長固定,該時長的選取需確保所有節點均能完成一輪內的數據傳輸任務。

2.1 成簇階段

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

(4)

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

(5)

3) 中轉節點選擇。選擇中轉節點的過程依然由原簇頭完成。若新簇頭將消息發送給中轉節點,再由中轉節點轉發至基站預期產生的總能耗小于簇頭直接發送給基站所需的能耗,則應選擇中轉節點。即:

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

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

(6)

式(6)可化簡為:

εampd1d2-Eelec>0

(7)

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

SCORE=εampd1d2-Eelec

(8)

2.2 傳輸階段

節點按TDMA發送數據給簇頭。簇內若存在中轉節點,則簇頭將消息發送給中轉節點,否則,簇頭、中轉節點和孤立節點按TDMA將數據消息發送給離自己最近的基站。

2.3 運行流程

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

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

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

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

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

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

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

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

8) 簇頭收齊DATA消息后做數據融合,有中轉節點的簇頭發消息給中轉節點。

9) 所有中轉消息到達中轉節點后,沒有中轉節點的簇頭、中轉節點、孤立節點開始按TDMA發送消息到基站。

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

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

表1 協議運行需要的消息類型

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

3 仿真實驗

3.1 仿真參數

表2 仿真參數

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

圖3 簇頭所占比例與能耗的關系

3.2 仿真結果

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

圖4 不同協議每輪選出的簇頭數

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

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

表3 節點失效所經歷的輪數

圖5 剩余節點數與運行輪數的關系

4 結 語

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