基于四叉樹多層次數據融合的無線傳感網絡路由協議研究*

聶云峰,汪 濤,鄢化鵬,吳文波

(南昌航空大學信息工程學院,南昌 330063)

在無線傳感網絡WSNs(Wireless Sensor Networks)應用中,為準確獲取監測區域內的感知信息,通常密集部署大量的感知節點[1],節點的密集部署在增加網絡冗余信息的同時加劇了節點的能量消耗。對于大規模無線傳感網絡而言,如何減少冗余信息傳輸、延長網絡的生命周期,是當前研究無線傳感網絡路由協議的重點內容[2-3]。無線傳感網絡路由協議可分為平面路由和層次路由兩類[4],由于分簇路由具有拓撲管理方便、數據融合簡單等優點,逐漸成為當前研究的熱點[5]。分簇路由協議可分為以下兩類:

①非均勻分簇路由協議:整個網絡被劃分為網格大小不均等的簇,每個簇的節點數目和簇半徑不一致。典型的非均勻分簇路由協議有:文獻[6]中提出的UCS模型,首次明確提出采用非均勻分簇的思想來均衡各簇間簇首節點的能量損耗,簇間數據傳輸采用多跳方式,并依據簇首的期望轉發負載來對簇的大小進行調整,從而使得網絡中各簇首節點具有相近的能量損耗,實現了整個網絡的能耗均衡。文獻[7]提出的EEUC有效的將非均勻分簇思想和多跳的路由機制進行結合,依據節點剩余能量和節點位置,在基站附近選舉多個簇頭,利用簇首之間的競爭半徑在基站區域形成多個非均勻的簇群,由于簇頭數目增多,簇群規模必然減少,在保證當選的簇頭能順利完成簇間通信任務的同時,均衡簇頭的能量消耗。文獻[8]提出的ACOUC協議的成簇方式來源于EEUC的非均勻成簇思想,但在簇首選舉方式上,除首輪選舉時,所有節點根據選舉條件隨機且周期性的激活選舉策略外,后續選舉策略采取簇群內部調整的方式進行。文獻[9]提出的CEB-UC采用的分簇方式是給劃分的不同區域分配不同的簇群,各分區通過節點間的局部競爭產生簇頭,簇頭數目根據各分區的能耗相等的原則計算確定,這種方式能有效保證網絡的節點能耗,延長網絡的部署半徑,降低簇頭能耗。

雖然非均勻分簇路由協議通過調整簇群結構,均衡了簇群中節點的能耗,但不均勻的分簇方式加大了成簇的成本、網絡拓撲管理難度。此外,由于分簇的不均勻,導致各個簇群分配的能量不一致,極易引發網絡能量空洞問題的發生[10-12]。

②均勻分簇路由協議:整個網絡被劃分為若干個大小均等的簇,每個簇內的節點數目和簇的半徑近似相等。典型的均勻分簇路由協議如:文獻[13]提出的EADEEG協議是一種基于簇的完全分布式算法和節能的WSNs數據收集協議,它采用計時廣播的方式來產生簇頭,降低了簇首選舉過程中的通信消耗,同時為減少與基站直接通信簇頭的數量以降低網絡的整體能耗,EADEEG協議采用多跳的傳輸方式在簇頭集合間構建路由。文獻[14]提出的PSO-C是一種具有能量感知能力的分簇協議,通過PSO算法選擇分簇方式,并采用輪回成簇機制形成簇群,簇的形成由基站采用集中控制策略,將分簇信息廣播至所有節點,簇內和簇間通信采用單跳的方式。文獻[15]提出的CDAT也是一種按輪運行的分簇協議,其簇頭的選舉是基于一種期望值,而這種期望值是由節點的剩余能量結合網絡覆蓋率所需要的最優簇頭數決定的。

對比非均勻分簇路由協議,均勻分簇路由協議具有成簇方便、簇群結構穩定、拓撲管理方便等優點。此外,在大規模無線傳感網絡中,減少節點冗余信息的傳輸,對于延長網絡的生命周期至關重要。雖然分簇路由協議均具有數據融合[16-17]的能力,相比非均勻分簇,均勻分簇更加有利于路由協議的時空查詢和網絡信息的融合?；诖?提出一種基于四叉樹均勻分簇的無線傳感網絡路由協議——(Quad-tree Uniform Clustering Routing Protocol),并對QUCRP的冗余信息傳輸、網絡生命周期進行仿真分析。

1 GeoGrid及其改進協議

GeoGrid[18-19]協議是一種經典的均勻分簇路由協議,將整個監測區域劃分成若干個大小相等的網格,單個網格構成一個簇,選取距離網格中心最近的節點作為簇首,具有成簇簡單,網絡拓撲清晰等優點。但GeoGrid簇群間的通信完全由簇首節點負責,這種做法極易引發能量空洞,縮短網絡的生命周期。

針對上述問題,文獻[20]提出的QuadGrid從成簇方式、簇首選舉、網絡拓撲層次構建及路由策略等方面對GeoGrid進行改進。首先依據四叉樹層次遞歸分解原理,將監測區域迭代進行四等份分割,并采用二進制Morton碼對網格進行編碼;然后在簇首選舉時,綜合考慮節點的剩余能量、節點與其所在網格中心距離以及節點與周圍簇首的通信距離等因素;最后綜合節點的剩余能量和傳輸距離兩方面因素,作為節點在下一跳路由時的選擇依據。

對比GeoGrid,QuadGrid降低了節點的能量消耗,減少了洪范路由的損耗,一定程度上減少了冗余信息的傳輸。但QuadGrid也存在一些不足:①如圖1中的QuadGrid路由過程所示,QuadGrid在四叉樹相應的層次上增設父節點,父節點間的數據轉發采取逐網格的傳輸方式而未遵循四叉樹結構,喪失了四叉樹結構在數據融合方面的優勢;②在簇首選舉時,需獲取相鄰8個簇首的位置信息,計算量較大。

圖1 QuadGrid路由過程

圖2 監測區域擴張

2 QUCRP路由協議

本文針對QuadGrid存在的問題,從3個方面對QuadGrid協議進行改進:①在簇首節點選取時,綜合考慮候選節點選舉時的能量、候選節點與路由層中心(網格中心)的距離、以及候選節點的通信功率等三方面因素;②在四叉樹相應層次上增設路由中間節點,路由中間節點由上一級簇首節點擔任,相鄰路由層間的數據轉發完全由路由中間節點負責;③為減少冗余信息的傳輸量,采用多層次多途徑的融合策略對數據進行融合。

2.1 簇的劃分和編碼

2.1.1 劃分監測區域和節點通信半徑

如圖2所示,為構建四叉樹層次結構,QUCRP路由協議首先以Sink節點為中心,將監測區域G(紅色線條圍成的區域)擴展成一個正方形區域。

接著Sink節點向網絡發布成簇的命令和劃分層次,并以自身為根節點,采用區域四叉樹遞歸分解原理,對整個監測區域進行四叉樹迭代劃分,劃分層次依據空間分辨率設定,假設劃分層次為4,結果如圖3所示。

圖3 簇的劃分

網格R(圖3中灰色區域所示)為劃分最小簇,設其邊長為l,網絡邊長為L,可計算出:

L=24×l

(1)

根據式(1),可計算出位于網絡第zi層的簇群邊長li與網絡劃分層次z的關系,如式(2)所示:

li=L/2zi,zi∈z

(2)

為保證簇首同成員節點之間能夠進行正常的通信,第zi層感知節點的通信半徑ri與網格的邊長li應滿足式(3):

(3)

2.1.2 網格編碼

依照劃分的層次,對簇群進行二進制編碼,簇群對應的編碼序列長Mz與所在網絡層次z有Mz=2z。簇群編碼采用逐層疊加的方式,低層簇群依據其在上一層簇群的方位(左上、右上、左下、右下4個方位),對應方位編碼分別為00、01、10、11,將方位編碼添加到上一級簇群編碼后面,疊加后的編碼作為自身的簇群編碼。列如網絡劃分層次為4,則最大序列長為8,如圖4簇群對應編碼所示。

網格編碼、補位碼、分隔碼以及簇內節點id共同組成節點標識號。節點標識號共占用32比特,網格編碼占用2Z比特,補位碼占用16-2Z比特,分隔碼占用4比特,節點id占用12比特,節點標識號組成如圖5所示。

圖4 簇群對應編碼

圖5 節點標識號組成

簇群編碼采用疊加方式,便于建立四叉樹的層次結構。當簇首向上還是向下路由時,只選擇與其簇群編碼高位序列相同的簇群;通過節點標識號,更好的定位感知節點所在的層次,簇頭在融合數據時,只融合與其簇群編碼一致或高位序列相同節點轉發來的數據,在保證路由過程嚴格遵循四叉樹層次結構的同時,也便于利用四叉樹在數據融合/壓縮方面的優勢。

2.2 簇首選舉算法

為保障簇首選舉的合理性,QUCRP路由協議從感知節點選舉時的能量、感知節點與網格中心的距離大小、以及節點通信功率等三方面出發,作為簇首節點選舉的依據。為簡化表達,簇首的選舉閾值用字母ch表示,將選舉閾值最小的節點作為簇首節點,其計算公式如下:

(4)

式中:α,β,γ為平衡系數,α+β+γ=1且α>0,β>0,γ>0;ecurrent為候選簇首節點當前剩余能量;einitial為該感知節點的初始能量;dzi為感知節點與柵格中心的距離,k為簇群內節點的個數,pi為節點的通信功率,zi為網絡對應的層次。

QUCRP路由協議采用輪換方式對簇首節點進行更替,并將具有最小ch的感知節點作為新的簇首節點。每經過一輪簇首選舉,能量消耗過大的簇首節點會被新的節點所取代。因而QUCRP路由協議可以有效的均衡簇內節點的能量損耗,延長整個網絡的壽命。

2.3 路由過程

QUCRP路由協議路由過程嚴格遵循四叉樹層次結構,除葉子簇群外,其余層次的簇首節點均只需管理著4個子簇首,QUCRP拓撲結構如圖6所示。

圖6 QUCRP拓撲結構

QUCRP針對上述網絡拓撲結構,在四叉樹對應層次上添加路由中間節點,路由中間節點由轉發節點對應的上一級簇首節點擔任,路由中間節點與簇首對應關系如圖7所示。

圖7 路由中間節點與簇首對應關系

圖8 數據轉發

相鄰路由層間的數據轉發完全交由路由中間節點負責,QUCRP數據轉發如圖8所示。簇群中的所有普通節點將所收集到的數據交付給本群簇首,簇首節點收到數據后,對數據進行初步融合處理,將融合后的結果發送給對應的路由中間節點,路由中間節點收到其子簇首轉發來的數據信息后,對接收到的數據進行再融合處理,得到融合精度更高的數據,接著向上一級路由中間節點轉發,直至Sink節點。

由圖8路由過程可知,簇首節點融合數據的能力決定著路由過程中冗余信息的傳輸量。

2.4 數據融合策略

QUCRP針對其網絡拓撲結構和路由中間節點與簇首的對應關系,對數據融合也分兩部分:葉子簇群融合和路由中間節點融合。

(1)葉子簇群融合:由式(2)和式(3)可知,當網絡層次加深時,葉子簇群所在網格邊長變小,簇群內節點通信范圍的覆蓋程度增大,節點采集到的數據冗余度增加。文獻[21]采用置信距離測度來表示兩個節點數據間的偏差大小,置信距離測度的值越小則測量值越接近,置信距離測度值與設定的閥值進行判斷,獲取節點間的支持度,構建橢圓矩陣表示節點間的關系矩陣。

葉子簇群內的簇首節點采用文獻[21]的融合策略對數據進行初步融合,獲取節點支持度高的數據,減少簇群內部數據的冗余。

(2)路由中間節點融合:由圖8中QUCRP路由協議拓撲結構可知,路由中間節點只需融合其4個子簇首轉發過來的數據,數據量相對減少但重要程度變大,為減少SInk節點接收到的網絡數據失真概率,路由中間節點需對其子簇首轉發來的數據進行詳細的分析,文獻[22]提出一種基于相關性函數和模糊綜合函數的數據融合策略,先由相關性函數得到傳感器節點的相互支持度,然后由隸屬函數得到每個傳感器提供信息的可信度,最后用模糊綜合函數得到融合結果。

路由中間節點采用文獻[22]的融合策略,各級路由中間節點對其下4個子簇首數據先進行相關性的判斷,接著由隸屬函數獲取各簇首數據的可信度,最后采用模糊綜合函數對子簇首數據進行融合。

QUCRP路由過程中,數據轉發嚴格遵循四叉樹的層次結構,數據逐級轉發,邊轉發邊融合,融合策略依據簇頭所在的路由層次,進行多層次多方式的融合,降低接地冗余信息傳輸。

3 仿真分析

3.1 仿真環境和評價標準

采用MATLAB仿真,設監測區域被擴張成一大小為128 m×128 m的正方形區域,傳感器個數為800,Sink節點位于網絡正中心。初始數據包大小為2 kbit,數據包頭長度為50 bit;節點初始能量為0.5 J;簇首每10輪重新選舉,仿真結果取每100輪的平均值。

定義數據融合比例ρ,為路由協議數據融合的評價標準,計算方法如式(5)所示:

(5)

L為網絡邊長、z為網絡劃分層次、n為葉子簇群內節點個數,ki為節點i采集到的數據量。

對任意節點i,設E0為節點初始能量,Er為第r輪節點消耗的總能量;其生命周期LTi滿足式(6):

(6)

3.2 仿真結果與分析

由圖9可知,QUCRP相比GeoGrid平均融合比例增加幅度為1%～43.1%,與QuadGrid相比平均融合比例增加幅度為1%～7.1%。QUCRP對監測區域采用四叉樹的迭代分簇方式,將網絡依層次均勻劃分為若干個簇群,各級路由層增設路由中間節點,路由中間節點選擇比路由節點高一級簇群的簇首節點擔任,保證了路由過程嚴格遵循四叉樹的層次結構。節點采集的初始數據經所在簇群的簇首節點初步融合->路由中間節點再融合(網絡劃分層次越大,再融合次數相應增加)->Sink節點,多層次的融合策略大幅度減少了路由節點的數據冗余,大大降低了冗余信息傳輸比例。

由圖10可知,QUCRP對比其他兩個協議,網絡生命周期有著一定的延長。QUCRP仿真輪數為(1 226 輪),相比QuadGrid(1 161輪)延長了5.6%,與GeoGrid(923輪)相比則延長了32.8%。

節點間的通信是無線傳感網絡能量消耗最大的部分。相比GeoGrid和QuadGrid,QUCRP通過對數據采用多層次的融合策略,減少網絡中冗余信息的傳輸,降低節點的額外通信消耗,延長了網絡的生命周期。

圖9 平均融合比例對比

圖10 網絡節點存活情況

4 結論

本文提出一種基于四叉樹多層次數據融合的均勻分簇路由協議QUCRP,從簇首選舉、路由過程、數據融合等方面對QuadGrid進行了改進。首先在簇首節點選舉時綜合考慮節點的剩余能量、節點與網格的中心距離以及節點的通信功率等因素,使網絡具有更好的負載均衡度。接著,在各級路由層上增設路由中間節點,相鄰路由層間的數據轉發完全交由路由中間節點負責,保證路由過程嚴格遵循四叉樹結構。最后,采用數據的相關性和綜合支持度等融合策略,對數據邊轉發邊融合,實現數據的多層次融合。仿真結果表明,QUCRP路由協議,有效降低了冗余信息的傳輸,延長了網絡的生命周期。下一步工作,將把QUCRP路由協議運用于現實的系統上進行驗證,并在冗余精度和節點能耗效率等方面做進一步研究。