路徑優(yōu)化的無線傳感器網(wǎng)絡(luò)CTP路由算法

王澤業(yè)， 陳慧杰， 黎有琦

(北京理工大學(xué) 計算機(jī)學(xué)院，北京 100081)

?

路徑優(yōu)化的無線傳感器網(wǎng)絡(luò)CTP路由算法

王澤業(yè)， 陳慧杰， 黎有琦

(北京理工大學(xué) 計算機(jī)學(xué)院，北京 100081)

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

無線傳感器網(wǎng)絡(luò); 匯聚樹協(xié)議； 能量優(yōu)化； 負(fù)載均衡

0 引 言

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

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

個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)量的影響。

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

1 DC—CTP定義

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

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

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

Fchildno×α

(1)

式中Fchildno為父親節(jié)點(diǎn)的孩子個數(shù)；α為梯度系數(shù)。

定義2 路由梯度集)節(jié)點(diǎn)N有m個鄰居節(jié)點(diǎn)，則N經(jīng)過所有鄰居節(jié)點(diǎn)到達(dá)匯聚節(jié)點(diǎn)的DCETX組成一個集合，記為X即

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

(2)

式中PDCETX(N,Ni,Sink)為N經(jīng)過鄰居節(jié)點(diǎn)Ni的DCETX值。

定義3 (最優(yōu)路由梯度路徑)最優(yōu)路徑為當(dāng)節(jié)點(diǎn)N到節(jié)點(diǎn)F的鏈路ETX值小于最小傳遞成功閾值T時，路徑深度最小的一組

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

Sink)}

(3)

路由引擎中路由算法將根據(jù)最優(yōu)路徑梯度選擇最優(yōu)路徑。

2 DC—CTP設(shè)計實(shí)現(xiàn)

DC—CTP協(xié)議包含鏈路質(zhì)量估計引擎、路由引擎和轉(zhuǎn)發(fā)引擎三個部分。其中，鏈路質(zhì)量估計引擎根據(jù)節(jié)點(diǎn)間的數(shù)據(jù)包及鏈路幀傳輸成功率計算節(jié)點(diǎn)間的單跳鏈路質(zhì)量，并將節(jié)點(diǎn)間的鏈路信息提供給路由引擎。而路由引擎根據(jù)鏈路質(zhì)量引擎提供的信息構(gòu)建路由表，并根據(jù)優(yōu)化的算法選擇下一跳的父親節(jié)點(diǎn)。轉(zhuǎn)發(fā)引擎維護(hù)包發(fā)送隊(duì)列，根據(jù)路由引擎提供的下一跳地址發(fā)送包序列。

2.1 鏈路質(zhì)量估計引擎

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

節(jié)點(diǎn)間數(shù)據(jù)包傳輸總量超過固定的窗口值時，則根據(jù)數(shù)據(jù)包傳輸成功率利用式(4)計算新的鏈路質(zhì)量評估值

EETX={Ntotal_data/Nsuccess_data-1}×10

(4)

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

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

(5)

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

2.2 路由引擎

路由引擎采用定義的DCETX作為路由梯度。根據(jù)路由算法更新節(jié)點(diǎn)間的DCETX，同時選擇出最優(yōu)路徑路由梯度。具體算法如下：

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

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

3)路由全面構(gòu)建：路由信息通過Sink節(jié)點(diǎn)的鄰居節(jié)點(diǎn)更新后，進(jìn)一步向外層擴(kuò)散，每個節(jié)點(diǎn)通過路由信息更新父親節(jié)點(diǎn)、孩子個數(shù)、路徑深度。

4)網(wǎng)絡(luò)拓?fù)錁?gòu)建結(jié)束。

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

2.3 轉(zhuǎn)發(fā)引擎

轉(zhuǎn)發(fā)引擎根據(jù)路由引擎選擇的下一跳節(jié)點(diǎn)發(fā)送數(shù)據(jù)包。轉(zhuǎn)發(fā)的數(shù)據(jù)包報頭中包含了節(jié)點(diǎn)間的DCETX值，轉(zhuǎn)發(fā)引擎根據(jù)此檢測路由的循環(huán)，如果檢測到路由環(huán)，則通知路由引擎更新路由表。

3 DC—CTP仿真與評估

DC—CTP使用在nesC語言在TinyOS系統(tǒng)平臺上實(shí)現(xiàn)。仿真實(shí)驗(yàn)使用的是TinyOS系統(tǒng)中的仿真平臺TOSSIM。實(shí)驗(yàn)假設(shè)在一個M×M的正方形網(wǎng)格的區(qū)域中，有n(n為正整數(shù)的平方)個節(jié)點(diǎn)隨機(jī)地分布于正方形網(wǎng)格區(qū)域，匯聚節(jié)點(diǎn)能量充足且只有一個。同時規(guī)定每個節(jié)點(diǎn)只隨機(jī)的發(fā)送500個數(shù)據(jù)包。針對不同節(jié)點(diǎn)的個數(shù)，對比CTP和DC—CTP路由算法各項(xiàng)性能參數(shù)。

1)匯聚樹深度。

由表1可見，20個節(jié)點(diǎn)以上時，DC—CTP相比于CTP協(xié)議明顯減少了匯聚樹的深度。匯聚樹深度的減少會相應(yīng)的減少節(jié)點(diǎn)間數(shù)據(jù)包的轉(zhuǎn)發(fā)數(shù)量。

表1 匯聚樹深度

2)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)量。

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

圖3 DC—CTP與CTP數(shù)據(jù)轉(zhuǎn)發(fā)總量Fig 3 Total quantity of data forwarding of DC—CTP and CTP

圖4 49個節(jié)點(diǎn)時DC—CTP與CTP節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)量Fig 4 Forwarding packets’number of DC—CTPand CTP,when node No=49

3)孩子節(jié)點(diǎn)個數(shù)

如圖5所示，網(wǎng)絡(luò)中49個節(jié)點(diǎn)時每個節(jié)點(diǎn)的孩子節(jié)點(diǎn)個數(shù)。因?yàn)樯儆?9個節(jié)點(diǎn)的網(wǎng)絡(luò)中DC—CTP與CTP節(jié)點(diǎn)孩子個數(shù)區(qū)別不明顯，所以這里不做展示。由圖5可見，DC—CTP協(xié)議的每個節(jié)點(diǎn)的孩子個數(shù)90 %以上都在2個以下，相對于CTP協(xié)議提高了將近10 %左右。

圖5 49個節(jié)點(diǎn)時，DC—CTP與CTP節(jié)點(diǎn)的孩子個數(shù)Fig 5 Child node number of DC—CTP and CTP,when node No=49

4)數(shù)據(jù)傳遞成功率

圖6中，5個節(jié)點(diǎn)時CTP傳遞成功率明顯低于DC—CTP，這是因?yàn)楣?jié)點(diǎn)較少時，CTP構(gòu)建網(wǎng)絡(luò)出現(xiàn)了環(huán)造成了部分節(jié)點(diǎn)的傳遞不成功。而在有16～49節(jié)點(diǎn)的傳遞成功率上DC—CTP均高出CTP協(xié)議1 %左右。其原因可能是DC—CTP路由建立時間相對較短，初期數(shù)據(jù)傳遞成功率比CTP高。

4 結(jié)束語

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

比CTP協(xié)議均有減少；同時整體網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)量平均下降了10.25 %左右，有效改善了CTP數(shù)據(jù)傳輸負(fù)載不均衡的問題，減少了整個網(wǎng)絡(luò)的能量消耗。

[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ìn)[J].計算機(jī)工程,2012,38(14):62-65.

[5] 吳怡之,駱彥凌,許紅安,等.基于Markov模型的WSNs匯聚樹路由協(xié)議[J].計算機(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] 吳三柱,吳三斌,李成博,等.基于能量感知的無線傳感器網(wǎng)絡(luò)CTP路由算法[J].計算機(jī)應(yīng)用研究,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

王澤業(yè)(1988-)，男，河北衡水人，碩士研究生,研究方向?yàn)闊o線傳感網(wǎng)、物聯(lián)網(wǎng)等。