林 勇

(重慶電子工程職業(yè)學(xué)院通信工程學(xué)院,重慶 401331)

目前,無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)在各領(lǐng)域廣泛使用[1]。WSNs內(nèi)傳感節(jié)點實時地感測數(shù)據(jù),然后,將數(shù)據(jù)傳輸至基站,再由基站將數(shù)據(jù)傳輸至控制中心,進(jìn)而實現(xiàn)對數(shù)據(jù)的監(jiān)測。因此,數(shù)據(jù)收集成為WSNs的關(guān)鍵。在WSNs的所有應(yīng)用場景中,數(shù)據(jù)流量服從匯聚格局,即所有節(jié)點均向基站傳輸數(shù)據(jù)[2]。

網(wǎng)絡(luò)內(nèi)的節(jié)點扮演了兩個角色:①向基站傳輸感測數(shù)據(jù);②協(xié)助其他節(jié)點,向基站轉(zhuǎn)發(fā)數(shù)據(jù)。因此,在基站鄰近區(qū)域就很容易形成流量瓶頸現(xiàn)象。即基站附近的節(jié)點,相比于其他節(jié)點,承擔(dān)了更多的轉(zhuǎn)發(fā)數(shù)據(jù)任務(wù)(高負(fù)載)[3]。然而,由于傳感節(jié)點能量、存儲容量有限,在高負(fù)載流量環(huán)境下,形成流量擁塞問題,傳感節(jié)點的隊列存儲區(qū)不能滿足增長的流量要求,這就容易形成隊列溢出,最終導(dǎo)致數(shù)據(jù)包丟失。

通常,采用負(fù)載平衡路由協(xié)議處理流量擁塞問題。這些協(xié)議常采用鏈路質(zhì)量、接入時延等動態(tài)路由指標(biāo),并利用這些路由指標(biāo)平衡網(wǎng)絡(luò)流量。為此,本文提出基于鏈路質(zhì)量和隊列時延的混合路由QDLQR。QDLQR路由引用動態(tài)的路由指標(biāo)平衡網(wǎng)絡(luò)流量。

1 QDLQR路由

本節(jié)利用數(shù)據(jù)包隊列時延和期望傳輸次數(shù)建立混合路由指標(biāo),再依據(jù)此指標(biāo)構(gòu)建通往基站的路由。

1.1 數(shù)據(jù)包隊列時延

對于每個出隊列的數(shù)據(jù)包,節(jié)點就計算它的停留時間。為了能夠?qū)崟r地統(tǒng)計數(shù)據(jù)包隊列時延[5],節(jié)點統(tǒng)計最近10個數(shù)據(jù)包的停留時間,并將其的平均值作為數(shù)據(jù)包隊列時延PQD(Packet Queueing Delay),如式(1)所示。

(1)

式中:Di表示節(jié)點Si的數(shù)據(jù)包隊列時延PQD。而m表示最近出隊列的數(shù)據(jù)包數(shù),且m≤10。當(dāng)節(jié)點在出隊的數(shù)據(jù)包少于10時,m<10,如圖1所示[6]。隊列緩沖區(qū)具有10個單元,且最多可容納10個數(shù)據(jù)包。當(dāng)信道空閑時,數(shù)據(jù)包就出列,傳輸至信道上。

圖1 數(shù)據(jù)包隊列示意圖

1.2 鏈路質(zhì)量

由于無線媒介的共享特性,無線鏈路存在不可靠性,這也就導(dǎo)致數(shù)據(jù)包傳輸?shù)呐鲎埠透蓴_。因此,在大多數(shù)情況下,節(jié)點需要多次重傳傳輸才能完成數(shù)據(jù)包的傳輸。傳輸次數(shù)越多,表明鏈路質(zhì)量越差。通常,引用期望傳輸次數(shù)ETX(Expected Transmission Count)估計鏈路質(zhì)量。

作為路由指標(biāo),ETX等于節(jié)點成功傳輸一個數(shù)據(jù)包所需的重傳次數(shù)。依據(jù)IEEE 802.15.4的無碰撞的多載波監(jiān)聽CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)協(xié)議,每個數(shù)據(jù)包允許重傳的最大次數(shù)為4。一旦超過4次,仍未成功傳輸,則直接將數(shù)據(jù)包丟棄。

QDLQR協(xié)議也引用ETX指標(biāo)估計鏈路質(zhì)量。每條鏈路的ETX等于每傳輸一個數(shù)據(jù)包所需的傳輸次數(shù)[7]。由于傳輸方向是雙向的,每條路由的ETX等于每條鏈路(正、反向鏈路)的ETX總和。例如,若一個由2跳構(gòu)成的路由,如果它的數(shù)據(jù)包傳輸成功率為100%,則其ETX值為3。若它的數(shù)據(jù)包傳輸成功率降低至50%,則其ETX值為6。

因此,可將鏈路的ETX定義為:

(2)

式中:df表示數(shù)據(jù)發(fā)送傳輸成功率,dr表示數(shù)據(jù)接收率。如圖2所示,節(jié)點A、B構(gòu)成一條鏈路linkA,B。其中df表示從節(jié)點A傳輸至節(jié)點B的傳輸成功率,相應(yīng)地,dr表示節(jié)點A接收來自節(jié)點B的成功率。

圖2 節(jié)點A與節(jié)點B間的鏈路

為了計算df和dr,節(jié)點周期地廣播探測包。每個探測包內(nèi)嵌入了自己和鄰居節(jié)點所所接收的探測包數(shù)。依據(jù)所發(fā)送的探測包數(shù)以及鄰居節(jié)點所成功接收的探測包數(shù),便可計算單向數(shù)據(jù)傳輸成功率r(t):

(3)

式中:x表示鄰居節(jié)點實際接收的數(shù)據(jù)包數(shù),而count(A)表示節(jié)點A傳輸?shù)臄?shù)據(jù)包數(shù)。

接下來,以圖2為例分析節(jié)點A如何計算df和dr。假定A在一段時間內(nèi)發(fā)送的探測包數(shù)為count(A)。節(jié)點B周期地廣播探測包,其包含它從各鄰居節(jié)點所接收的探測包Packetprobe。當(dāng)節(jié)點接收了來自節(jié)點B廣播的Packetprobe,則就知道節(jié)點B接收幾個由自己發(fā)送的探測包,即x值。最后,就可依據(jù)式(3)計算df。類似地,由于各節(jié)點都是周期地廣播探測包,節(jié)點A也能夠知道在一定時間內(nèi)應(yīng)從節(jié)點B所接收的探測包數(shù)。再依據(jù)從節(jié)點B實際接收的探測包數(shù),便可計算dr。最終,可依據(jù)式(2)計算鏈路linkA,B的ETX。

1.3 混合路由指標(biāo)

為了更好地選擇下一跳轉(zhuǎn)發(fā)節(jié)點,QDLQR路由將隊列時延和鏈路質(zhì)量進(jìn)行融合,構(gòu)成新的路由指標(biāo)。隊列時延反映了節(jié)點自身的流量負(fù)載問題。隊列時延越大,表明節(jié)點負(fù)載越嚴(yán)重。而ETX反映了鏈路質(zhì)量。ETX越大,鏈路質(zhì)量越差。為此,引用混合路由指標(biāo)Com_rout,其定義如式(4)所示:

Com_rout=αD+βETX

(4)

式中:α、β分別表示隊列時延、ETX的權(quán)重系數(shù)。從式(4)可知,對于任意一個節(jié)點,它的混合路由指標(biāo)越大,由它構(gòu)建的鏈路質(zhì)量就越差。

1.4 下一跳轉(zhuǎn)發(fā)節(jié)點的選擇

當(dāng)節(jié)點(假定節(jié)點i)需要傳輸數(shù)據(jù)包時,它就計算一跳鄰居節(jié)點內(nèi)每個節(jié)點的混合路由指標(biāo)。假定節(jié)點i的一跳鄰居節(jié)點集為Ni。節(jié)點i從Ni中選擇具有最小的Com_rout、且大于1的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點,如式(5)所示:

(5)

式中:Com_rout(i)表示節(jié)點i的混合路由指標(biāo)。而|Ni|表示鄰居節(jié)點集Ni的節(jié)點數(shù)。通過式(5)選擇具有最小的混合路由指標(biāo)的節(jié)點(假定為節(jié)點k)作為下一跳轉(zhuǎn)發(fā)節(jié)點。

1.5 路由方案

每個數(shù)據(jù)包源節(jié)點依據(jù)式(5)選擇下一跳轉(zhuǎn)發(fā)節(jié)點,進(jìn)而構(gòu)成數(shù)據(jù)傳輸路由。如圖3所示,各節(jié)點先周期地交互探測包,就能得到每個節(jié)點的混合路由指標(biāo),例如節(jié)點B的Com_rout(B)=3,而節(jié)點C的混合路由指標(biāo)為4。

圖3 數(shù)據(jù)傳輸示意圖

如圖3所示,數(shù)據(jù)包攜帶節(jié)點A只有一個鄰居節(jié)點,因此,只能選擇節(jié)點B作為下一跳轉(zhuǎn)發(fā)節(jié)點,然后,節(jié)點B從它的鄰居集NB={C,D}中選擇具有最低混合路由指標(biāo)的節(jié)點作為下一數(shù)據(jù)包轉(zhuǎn)發(fā)節(jié)點,因此,節(jié)點C成為下一跳。以此類推,最終便形成{A,B,C,E,F}路由。

2 性能分析

為了更好地分析QDLQR協(xié)議,利用Cooja仿真器[8]建立仿真平臺[9]。引用IEEE 802.15.4協(xié)議作為物理層協(xié)議,并依據(jù)CSMA/CA策略接入媒介[10-11]。

選擇引用ETX指標(biāo)的RPL協(xié)議和基于最小跳數(shù)[12]的HopCount路由作為參照,并分析它們的數(shù)據(jù)包傳遞率、隊列溢出和端到端傳輸時延性能。同時考查式(4)的α、β值對QDLQR性能的影響,考慮三種情況:①α=0.75,β=0.25;②α=0.5,β=0.5;③α=0.25,β=0.75。這三種情況分別標(biāo)記為QDLQR_0.75、QDLQR_0.5、QDLQR_0.25。每次實驗獨立重復(fù)20次,取平均值作為最終的實驗數(shù)據(jù)。

2.1 數(shù)據(jù)包傳遞率

數(shù)據(jù)包傳遞率是指由基站所接收的數(shù)據(jù)包數(shù)與網(wǎng)絡(luò)內(nèi)總體產(chǎn)生的數(shù)據(jù)包數(shù)之比。本次實驗分析QDLQR、RPL和HopCount協(xié)議的數(shù)據(jù)包傳遞率,同時考慮低流量、高流量兩類場景。前者為每個節(jié)點每秒產(chǎn)生1個數(shù)據(jù)包(1 packet/second/node),后者指每個節(jié)點每秒產(chǎn)生10個數(shù)據(jù)包(10 packet/second/node)。

圖4顯示了各協(xié)議在低流量、高流量場景下的數(shù)據(jù)包傳遞率,且節(jié)點數(shù)從10、20、40和60變化。從圖4(a)可知,在低流量環(huán)境下,所有協(xié)議的數(shù)據(jù)包傳遞率相近,而QDLQR協(xié)議的數(shù)據(jù)包傳遞率并不明顯。原因在于:在低流量環(huán)境下,無線媒介的多數(shù)時間是空閑的,負(fù)載平衡路由對數(shù)據(jù)包傳遞率的影響甚少。

圖4 數(shù)據(jù)包傳遞率

然而,當(dāng)流量增加后,相比于RPL和HopCount協(xié)議,QDLQR協(xié)議的數(shù)據(jù)包傳遞率得到有效地提升。而RPL協(xié)議的數(shù)據(jù)包傳遞率優(yōu)于HopCount協(xié)議,原因在于HopCount協(xié)議采用靜態(tài)的路由指標(biāo),這就無法平衡節(jié)點間負(fù)載,使得部分節(jié)點遭遇擁塞、隊列溢出,最終降低了數(shù)據(jù)包丟失。而RPL協(xié)議引用動態(tài)的路由指標(biāo),但它也不足以平衡負(fù)載,難以避免因隊列溢出而丟失數(shù)據(jù)包的現(xiàn)象。

此外,相比QDLQR_0.5和QDLQR_0.25,QDLQR_0.75協(xié)議獲取最高的數(shù)據(jù)包傳遞率。原因在于:當(dāng)α=0.75,意味著隊列時延在混合路由指標(biāo)中的比重更大,這有利于避免擁塞路徑,提高了數(shù)據(jù)傳輸?shù)挠行浴?/p>

2.2 隊列溢出

網(wǎng)絡(luò)擁塞的一個負(fù)面影響就是隊列溢出,這增加大了數(shù)據(jù)包丟失率。為此,分析QDLQR協(xié)議在隊列溢出方面的性能。由于只可能在高流量環(huán)境下,才可能出現(xiàn)隊列溢出的現(xiàn)象。

因此,本次實現(xiàn)分析了每個節(jié)點每秒產(chǎn)生10個數(shù)據(jù)包(10 packet/second/node)、每個節(jié)點每秒產(chǎn)生5個數(shù)據(jù)包(5 packet/second/node)兩種高流量的環(huán)境,因隊列溢出導(dǎo)致數(shù)據(jù)包丟失的比例(以下簡稱溢出-丟失率),實驗數(shù)據(jù)如圖5所示。

圖5 隊列溢出對數(shù)據(jù)包丟失的影響

從圖5可知,相比于其他協(xié)議,QDLQR協(xié)議的溢出-丟失率很小。在最糟糕的情況,QDLQR協(xié)議的溢出-丟失率也只有1%。原因在于:QDLQR協(xié)議能夠有效地平衡各跳路由間的流量負(fù)載,避免部分節(jié)點承擔(dān)高負(fù)載的情況。而HopCount協(xié)議的溢出-丟失率很高,這主要是因為它采用了靜態(tài)路由指標(biāo)。

2.3 端到端傳輸時延

最后分析QDLQR協(xié)議的端到端傳輸時延,其等于數(shù)據(jù)包從源節(jié)點傳輸至基站的時間。為此,本次實驗環(huán)境的參數(shù)如下:節(jié)點數(shù)為40,流量分別為1 packet/second/node和10 packet/second/node,實驗數(shù)據(jù)如圖6所示。

圖6 端到端傳輸時延

從圖6可知,各協(xié)議的時延在不同跳數(shù)環(huán)境下的相近,HopCount協(xié)議的時延略低于其他協(xié)議。相比于,RPL和HopCount協(xié)議的時延低于QDLQR協(xié)議,原因在于:RPL和HopCount協(xié)議因隊列溢出而丟失了較多數(shù)據(jù)包,這就降低了那些未丟失數(shù)據(jù)包的傳輸時延。

3 總結(jié)

針對無線傳感網(wǎng)絡(luò)的數(shù)據(jù)收集問題,提出基于隊列時延和鏈路質(zhì)量的WSNs路由QDLQR。QDLQR協(xié)議充分考慮了數(shù)據(jù)包隊列時延,并依據(jù)ETX評估鏈路質(zhì)量,再通過融合隊列時延和鏈路質(zhì)量,構(gòu)建新的路由指標(biāo)。最后,通過此路由指標(biāo)構(gòu)建路由。仿真數(shù)據(jù)表明,提出的QDLQR路由有效地降低數(shù)據(jù)包丟失率。