路徑優化的無線傳感器網絡CTP路由算法

王澤業， 陳慧杰， 黎有琦

(北京理工大學 計算機學院，北京 100081)

?

路徑優化的無線傳感器網絡CTP路由算法

王澤業， 陳慧杰， 黎有琦

(北京理工大學 計算機學院，北京 100081)

針對無線傳感器網絡普遍存在因負載不均衡導致的轉發率過高，網絡壽命短的問題，提出了一種基于匯聚樹協議(CTP)的路徑轉發優化協議深度和孩子匯聚樹協議(DC—CTP)。通過研究節點路徑深度和孩子節點個數對當前節點以及對全網絡轉發數據量的影響，對CTP網絡節點的路由算法進行優化。TOSSIM 仿真的結果表明：DC—CTP協議選擇優化后的路徑，將整個網絡的節點的數據轉發量減少了平均10.25 %左右，能夠延長無線傳感器網絡的存活時間。

無線傳感器網絡; 匯聚樹協議； 能量優化； 負載均衡

0 引 言

無線傳感器網絡(wireless sensor networks,WSNs)是由大量具有計算和感知能力的傳感器節點組成，節點間通過多跳自組織方式形成的自組網絡系統[1,2]。無線傳感器網絡在醫療衛生、軍事科技以及安全應用等多個領域具有廣闊的應用前景。無線傳感器網絡的傳感器節點由能量有限的電池供電。因此降低網絡中傳感器節點的能量消耗，增加網絡的生存時間，成為無線傳感器網絡的一個研究熱點。而匯聚路由協議負責將傳感器節點采集的數據逐跳轉發至匯聚節點，匯聚路由協議的效率直接影響到無線傳感器網絡的存活時間。

匯聚樹協議(collection tree protocol，CTP)[3]是一類將傳感器節點采集到的數據采用多播轉發到一個或多個匯聚節點的無線傳感網絡路由協議。協議使用節點間的數據傳輸期望值(expected transmissions，ETX)作為路由選擇度量。傳輸期望值較小的節點會被選作父親節點。目前針對CTP協議的改進主要集中在網絡的負載均衡[4,5]以及網絡整體能量優化方面。文獻[6]針對CTP的數據熱點進行了負載遷移。當網絡中某節點發送的數據量過大時，節點將轉換傳輸數據量較小的父節點的兄弟節點作為該熱點的父節點。該算法優點是避免了熱點能量的快速消耗，對網絡有一定的優化。但缺點也很明顯只是將負載從當前的熱點轉移到另一個節點，隨著時間增加，下一個節點又會變成另一個熱點。文獻[7,8]均是考慮了下一節點的剩余能量對網絡的影響。文獻[7]的算法是在最大能量路徑和最優傳輸期望值路徑之間選擇一條。這樣兼顧了傳輸的成功率和整體網絡的能量均衡。而文獻[8]是進一步將下一跳的剩余能量和最優ETX進行了歸一化。以上對CTP協議的改進均是對路徑上單個節點的能量以及負載均衡，并未綜合研究選擇節點的路徑深度和孩子節點個數對節點能量以及整

個網絡數據轉發量的影響。

本文針對CTP路由協議原理中存在的因負載不均衡導致的能耗問題，通過研究節點路徑深度和孩子節點個數對全網絡轉發數據包數量的影響，提出了一種基于路徑優化協議深度和孩子匯聚樹協議(depth and children collection tree protocol,DC—CTP)。TOSSIM 仿真[9]結果表明：其優化了整個網絡節點的路徑選擇。通過DC—CTP優化后的路徑，減少了節點的數據轉發量，達到了整個網絡的能量優化的效果，能夠延長無線傳感網絡壽命。

1 DC—CTP定義

為了更好闡述DC—CTP協議，給出以下幾個定義：

定義1 路由梯度 DCETX)DCETX等于節點N到其父節點F的鏈路ETX值與其父節點F的DCETX值之和，即

PDCETX(N,Sink)=LETX(N,F)+PDCETX(F,Sink)×

Fchildno×α

(1)

式中Fchildno為父親節點的孩子個數；α為梯度系數。

定義2 路由梯度集)節點N有m個鄰居節點，則N經過所有鄰居節點到達匯聚節點的DCETX組成一個集合，記為X即

X={PDCETX(N,Ni,Sink)|0≤i≤m}

(2)

式中PDCETX(N,Ni,Sink)為N經過鄰居節點Ni的DCETX值。

定義3 (最優路由梯度路徑)最優路徑為當節點N到節點F的鏈路ETX值小于最小傳遞成功閾值T時，路徑深度最小的一組

BP(N,Sink)={Xi|LETX(Ni,F)

Sink)}

(3)

路由引擎中路由算法將根據最優路徑梯度選擇最優路徑。

2 DC—CTP設計實現

DC—CTP協議包含鏈路質量估計引擎、路由引擎和轉發引擎三個部分。其中，鏈路質量估計引擎根據節點間的數據包及鏈路幀傳輸成功率計算節點間的單跳鏈路質量，并將節點間的鏈路信息提供給路由引擎。而路由引擎根據鏈路質量引擎提供的信息構建路由表，并根據優化的算法選擇下一跳的父親節點。轉發引擎維護包發送隊列，根據路由引擎提供的下一跳地址發送包序列。

2.1 鏈路質量估計引擎

鏈路質量估計引擎初期利用廣播(link estimation exchange protocol,LEEP)幀建立鏈路質量表，如圖1所示。鏈路質量用特別期望傳輸(EETX)來表示。后期利用LEEP幀的傳輸成功率和傳輸數據包的成功率兩種方法來計算節點間鏈路質量。

節點間數據包傳輸總量超過固定的窗口值時，則根據數據包傳輸成功率利用式(4)計算新的鏈路質量評估值

EETX={Ntotal_data/Nsuccess_data-1}×10

(4)

為了減少鏈路的抖動，協議采用了取指數加權移動平均值的方法將兩方法結合在一起。計算公式如式(5)。其中新計算的鏈路質量EETXnew占鏈路質量的1-β。算法實現中β取值為90 %。

EETX=EETXnew×(1-β)+EETXold×β

(5)

圖1 鏈路質量表建立過程Fig 1 Process of setting up of link quanlity table

2.2 路由引擎

路由引擎采用定義的DCETX作為路由梯度。根據路由算法更新節點間的DCETX，同時選擇出最優路徑路由梯度。具體算法如下：

1)初始化路由表：初始化Sink節點的孩子個數為0，路徑深度初始化為0；非根節點孩子個數初始化為0，路徑深度初始化為極大值INVALID_VALUE；節點的DCETX值初始化為0。

2)Sink路由信息擴散：Sink節點將路由表中信息廣播至鄰居節點，鄰居節點通過計算PDCETX(N,Sink)選擇最優路徑，算法的具體流程如圖2所示。鄰居節點將更新選擇的父親節點，同時將本節點的路徑深度更新為父節點的路徑深度加1。然后鄰居節點將路由信息廣播至網絡中，其父節點收到路由包后會將鄰居節點加入自己的孩子列表當中。

3)路由全面構建：路由信息通過Sink節點的鄰居節點更新后，進一步向外層擴散，每個節點通過路由信息更新父親節點、孩子個數、路徑深度。

4)網絡拓撲構建結束。

圖2 更新路由表過程Fig 2 Process of updating routing table

2.3 轉發引擎

轉發引擎根據路由引擎選擇的下一跳節點發送數據包。轉發的數據包報頭中包含了節點間的DCETX值，轉發引擎根據此檢測路由的循環，如果檢測到路由環，則通知路由引擎更新路由表。

3 DC—CTP仿真與評估

DC—CTP使用在nesC語言在TinyOS系統平臺上實現。仿真實驗使用的是TinyOS系統中的仿真平臺TOSSIM。實驗假設在一個M×M的正方形網格的區域中，有n(n為正整數的平方)個節點隨機地分布于正方形網格區域，匯聚節點能量充足且只有一個。同時規定每個節點只隨機的發送500個數據包。針對不同節點的個數，對比CTP和DC—CTP路由算法各項性能參數。

1)匯聚樹深度。

由表1可見，20個節點以上時，DC—CTP相比于CTP協議明顯減少了匯聚樹的深度。匯聚樹深度的減少會相應的減少節點間數據包的轉發數量。

表1 匯聚樹深度

2)節點轉發數據量。

無線傳感網絡能量消耗主要在于節點間的收發數據，減少數據的轉發量能有效降低整個網絡的能量消耗。由圖3可見，網絡節點較少時，DC—CTP數據轉發量并沒有明顯的減少，但是當網絡中節點增長到16～49之間時，DC—CTP相對于CTP協議的整體數據轉發量減少了9.5 %～11 %。隨著數據節點的增多，DC—CTP控制轉發數量的提升越明顯。但在圖4中，網絡中49個節點每個節點的數據轉發量時。幾個關鍵的數據轉發節點上的數據，DC—CTP相對于CTP并未有明顯的減少，大體上相當。

圖3 DC—CTP與CTP數據轉發總量Fig 3 Total quantity of data forwarding of DC—CTP and CTP

圖4 49個節點時DC—CTP與CTP節點數據轉發量Fig 4 Forwarding packets’number of DC—CTPand CTP,when node No=49

3)孩子節點個數

如圖5所示，網絡中49個節點時每個節點的孩子節點個數。因為少于49個節點的網絡中DC—CTP與CTP節點孩子個數區別不明顯，所以這里不做展示。由圖5可見，DC—CTP協議的每個節點的孩子個數90 %以上都在2個以下，相對于CTP協議提高了將近10 %左右。

圖5 49個節點時，DC—CTP與CTP節點的孩子個數Fig 5 Child node number of DC—CTP and CTP,when node No=49

4)數據傳遞成功率

圖6中，5個節點時CTP傳遞成功率明顯低于DC—CTP，這是因為節點較少時，CTP構建網絡出現了環造成了部分節點的傳遞不成功。而在有16～49節點的傳遞成功率上DC—CTP均高出CTP協議1 %左右。其原因可能是DC—CTP路由建立時間相對較短，初期數據傳遞成功率比CTP高。

4 結束語

圖6 DC—CTP與CTP傳輸成功率
Fig 6 Delivery ratio of DC—CTP and CTP

比CTP協議均有減少；同時整體網絡的數據轉發量平均下降了10.25 %左右，有效改善了CTP數據傳輸負載不均衡的問題，減少了整個網絡的能量消耗。

[1] Akyildiz I F,Su W,Sankarasubramaniam Y,et al.Wireless sensor networks:A survey[J].Computer Networks,2002,38(4):393-422.

[2] Yick J,Mukherjee B,Ghosal D.Wireless sensor networks sur-vey[J].Computer Networks,2008,52(12):2292-2330.

[3] Gnawali O,Fonseca R,Jamieson K,et al.Collection tree proto-col[C]∥Proc of the 7th ACM Conference on Embedded Networked Sensor Systems,New York:ACM,2009:1-14.

[4] 趙晨旭,吳怡之,韓漢光.基于WSNs均衡匯聚樹的CTP路由算法改進[J].計算機工程,2012,38(14):62-65.

[5] 吳怡之,駱彥凌,許紅安,等.基于Markov模型的WSNs匯聚樹路由協議[J].計算機工程,2011,37(18):62-64.

[6] Zhao Jing,Wang Lei,Yue Wenlong,et al.Load migrating for the hot spots in wireless sensor networks using CTP[C]∥Proc of the 7th International Conference on Mobile Ad-Hoc and Sensor Networks,Washington DC:IEEE Computer Society,2011:167-173．

[7] Sivagami A,Pavai K,Sridharan D,et al.Energy and link quality-based routing for data gathering tree in wireless sensor networks under TinyOS—2.X[J].International Journal of Wireless & Mobile Networks,2010,2(2):47-60.

[8] 吳三柱,吳三斌,李成博,等.基于能量感知的無線傳感器網絡CTP路由算法[J].計算機應用研究,2014,31(11):3045-3048.

[9] Levis P,Lee N,Welsh M,et al.TOSSIM:Accurate and scalable simulation of entire TinyOS applications[C]∥Proceedings of the 1st International Conference on Embedded Networked Sensor Systems,ACM,2003:126-137.

CTP routing algorithm for wireless sensor networks based on path optimization

WANG Ze-ye， CHEN Hui-jie， LI You-qi

(College of Computer Science and Technology，Beijing Institute of Technology，Beijing 100081，China)

To address load unbalance problem which can led to high forwarding rate and short lifetime of network in wireless sensor networks(WSNs).An optimal path-based protocol based on collection tree protocol(CTP),is proposed，which is called depth and children CTP(DC—CTP).Considering the path depth and the number of child node influence the forwarding data number in the whole network，DC—CTP optimized the path choice for every node in the network.TOSSIM simulation results show that the path which is selected by DC—CTP，can reduce the forwarding packet number of nodes about 10.25 %，and the DC—CTP can prolong network lifetime.

wireless sensor networks(WSNs); collection tree protocol(CTP); energy-optimization; load balance

10.13873/J.1000—9787(2016)12—0122—03

2016—01—11

TP 393; TP 301

A

1000—9787(2016)12—0122—03

王澤業(1988-)，男，河北衡水人，碩士研究生,研究方向為無線傳感網、物聯網等。