時(shí)延要求感知的空洞抑制WSNs路由的研究*

黃 祎

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

無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)已在多類應(yīng)用中使用,如戰(zhàn)場監(jiān)視、緊急報(bào)警、空難檢測[1]。這些應(yīng)用均要求傳感節(jié)點(diǎn)在預(yù)定時(shí)間限制內(nèi)將感測數(shù)據(jù)傳輸至基站,并且不同的應(yīng)用具有不同的時(shí)間限制。即使在同一應(yīng)用中,不同類型的感測數(shù)據(jù)也具有不同的時(shí)間要求。例如,在火災(zāi)檢測應(yīng)用中,攜帶異常高溫的數(shù)據(jù)應(yīng)盡可能快地傳輸至基站,而對(duì)于攜帶常溫的數(shù)據(jù)[2],可允許一定的時(shí)延。因此,討論不同WSNs內(nèi)數(shù)據(jù)的傳輸時(shí)延是十分必要的。

然而,由于WSNs網(wǎng)絡(luò)的固有特性,如能量供應(yīng)受限、傳感節(jié)點(diǎn)存儲(chǔ)容量和計(jì)算能力有限以及無線鏈路的不可靠性,滿足數(shù)據(jù)傳輸?shù)亩说蕉藭r(shí)延要求是不易的。

基于網(wǎng)絡(luò)局部信息的地理位置路由[3]在WSNs內(nèi)廣泛使用。地理位置路由常假定網(wǎng)絡(luò)內(nèi)每個(gè)節(jié)點(diǎn)知道自己的位置以及鄰居節(jié)點(diǎn)位置,并以貪婪[4]轉(zhuǎn)發(fā)策略傳輸數(shù)據(jù)包,如多徑多速度MMSPEED(Multipath Multispeed)[5]協(xié)議、 服務(wù)質(zhì)量感知的地理機(jī)會(huì)路由QAGOR(Qos Aware Geographic Opportunistic Routing)[6]、多約束的地理路由MCGR(Multi-Constrained Geographic Routing)[7]和基于流量差異的定位路由TDLR(Traffic-differentiation-based Localized Routing)[8]。

這些協(xié)議通常將端到端的服務(wù)質(zhì)量QoS(Quality of Service)限制劃分為Hop-to-Hop限制。在時(shí)間領(lǐng)域內(nèi),現(xiàn)存協(xié)議通過Hop-to-Hop速度HTHS(Hop-to-Hop Speed)決策路由,進(jìn)而保證端到端傳輸時(shí)延。從節(jié)點(diǎn)(假定si)至它的鄰居節(jié)點(diǎn)sj的HTHS等于它們間的歐式距離與從si向sj轉(zhuǎn)發(fā)一個(gè)數(shù)據(jù)包所要求的時(shí)間比值。這些協(xié)議總是將具有更高HTHS的選擇為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

傳統(tǒng)的HTHS值正比于離目的節(jié)點(diǎn)距離。據(jù)以這個(gè)觀點(diǎn),幾乎所有數(shù)據(jù)包均是沿著源節(jié)點(diǎn)至目的節(jié)點(diǎn)的連線路徑傳輸。這種路由策略適合于高密度節(jié)點(diǎn)區(qū)域,然而,當(dāng)出現(xiàn)路由空洞時(shí),這種路由策略會(huì)產(chǎn)生兩個(gè)問題:①路由空洞(局部最小問題),如圖1(a)所示,在連通目的節(jié)點(diǎn)方向上沒有鄰居節(jié)點(diǎn),在這種情況下,數(shù)據(jù)包可能無法快速地傳輸至目的節(jié)點(diǎn),甚至?xí)?dǎo)致數(shù)據(jù)包丟失。

當(dāng)遭遇路由空洞時(shí),常將數(shù)據(jù)包沿著空洞邊界傳輸,這就導(dǎo)致第2個(gè)問題:②空洞邊界擁塞,如圖1(b)所示,這就增加端到端傳輸時(shí)延。

圖1 地理位置路由的兩個(gè)問題

為此,本文考慮了路由空洞問題,并提出基于時(shí)延要求的抑制路由空洞的地理位置路由DG-SHGR(Delay-Guaranteed-based Suppressing Hole Geographic Routing),進(jìn)而解決上述的兩個(gè)問題。DG-SHGR路由的主要目的在于預(yù)先檢測路由空洞,然后再合理地選擇路由。

具體而言,對(duì)于每個(gè)數(shù)據(jù)包,先依據(jù)空洞區(qū)域定義“雷區(qū)”FAR(Forbidden Area),進(jìn)而使得數(shù)據(jù)包能避開FAR,進(jìn)而抑制空洞路由。而FAR的尺寸和位置隨數(shù)據(jù)包時(shí)延要求不同而變化,從而平衡網(wǎng)絡(luò)流量。為了保證數(shù)據(jù)包能及時(shí)到達(dá)目的節(jié)點(diǎn),DG-SHGR路由利用端到端時(shí)延要求調(diào)整FAR尺寸。實(shí)驗(yàn)數(shù)據(jù)表明,提出的DG-SHGR路由有效地提高了數(shù)據(jù)包傳遞率,并平衡網(wǎng)絡(luò)負(fù)載。

1 系統(tǒng)模型及定義

DG-SHGR路由假定每個(gè)節(jié)點(diǎn)知道自己的位置和一跳鄰居節(jié)點(diǎn)位置。此外,源節(jié)點(diǎn)知道目的節(jié)點(diǎn)的位置。

路由空洞:將路由空洞定義為多邊形,且在每個(gè)頂點(diǎn)上的傳感節(jié)點(diǎn)S1,…,Sn滿足3個(gè)條件:①多邊形內(nèi)部區(qū)域不包含任何傳感節(jié)點(diǎn);②節(jié)點(diǎn)Si與Si+1間的歐式距離小于傳輸范圍R,且i∈|1,n|,Sn+1=S1;③節(jié)點(diǎn)Si與Si+2間的歐式距離大于傳輸范圍R,且i∈[1,n],Sn+1=S1,Sn+2=S2。

令Θ為多邊形,頂點(diǎn)表示為Q1,Q2,…,Qn。此外,引用|·|表示歐式距離,例如|AB|表示點(diǎn)A與點(diǎn)B間的歐式距離,||表示線的歐式長度。pΘ表示Θ的邊。令A(yù)、B是Θ邊上的點(diǎn),而分別表示從A至B的逆時(shí)針、順時(shí)針邊。

凸包(convex hull):Θ凸包的定義為能夠覆蓋整個(gè)Θ的凸多邊形,且與Θ具有相同的頂點(diǎn)。

本文引用H表示空洞的凸包。令N表示Θ邊外的任意一個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)N的視圖控制頂點(diǎn)VLV(View Limit Vertex)是Θ內(nèi)的頂點(diǎn),且此頂點(diǎn)與節(jié)點(diǎn)N的連線不與Θ相交,如圖2(a)所示。Qi、Qj是Θ的VLV。從N至Θ的視圖控制角θ定義為NQi與NQj的夾角。

繞開-最短路徑BSEP(Bypassing Short Euclidean Path):從源節(jié)點(diǎn)s至目的節(jié)點(diǎn)t的繞開-最短路徑LΘ(s,t)是沿著Θ的最短折線構(gòu)成,如圖2(b)所示。

圖2 VLV定義示例

2 DG-SHGR路由

提出的DG-SHGR路由主要解決圖1所示的兩個(gè)問題:局部最小問題和空洞邊界擁塞問題。DG-SHGR路由先檢測空洞,然后再選擇能避開空洞的路由傳輸數(shù)據(jù)包。具體而言,DG-SHGR路由主要由空洞檢測、空洞信息傳輸以及數(shù)據(jù)轉(zhuǎn)發(fā)3個(gè)階段構(gòu)成。

2.1 空洞檢測

引用文獻(xiàn)[9]的TENT規(guī)則,節(jié)點(diǎn)檢測自己是否在空洞邊上。如果在空洞邊上,節(jié)點(diǎn)(稱為邊界節(jié)點(diǎn))就產(chǎn)生邊界坐標(biāo)決策BCD(Boundary Coordinates Determination)消息,再利用文獻(xiàn)[9]引用的右手規(guī)則,沿著空洞邊界轉(zhuǎn)發(fā)BCD消息,進(jìn)而收集信息。

當(dāng)收到來自其他節(jié)點(diǎn)發(fā)送的BCD消息,節(jié)點(diǎn)就檢測自己的橫坐標(biāo)是否小于發(fā)送節(jié)點(diǎn)的橫坐標(biāo)。如果小于,則利用右手規(guī)則轉(zhuǎn)發(fā)BCD消息,否則就丟失。通過這種方式,最終只有一條BCD消息沿著邊界轉(zhuǎn)發(fā),并且被轉(zhuǎn)發(fā)的BCD消息是由橫坐標(biāo)最大的邊界節(jié)點(diǎn)產(chǎn)生的。將此節(jié)點(diǎn)稱為BCD的初始節(jié)點(diǎn)(BCD-I)。

2.2 空洞信息傳輸

所謂空洞信息傳輸就是將空洞凸包H的信息傳輸至圍繞著空洞的節(jié)點(diǎn)。傳輸半徑是由預(yù)定參數(shù)αmin控制,且0≤αmin≤π。若αmin=0,則表示將凸包H的信息傳輸至整個(gè)網(wǎng)絡(luò);若αmin=π,則傳輸區(qū)域限制于凸包H。

由于BCD-I節(jié)點(diǎn)獲取了凸包H的信息,BCD-I節(jié)點(diǎn)就利用空洞核心信息HCI(Hole Core Information)消息向鄰居節(jié)點(diǎn)傳輸凸包H信息。一旦接收到HCI消息,節(jié)點(diǎn)就計(jì)算凸包H的視圖控制角θ。如果θ大于αmin,就存儲(chǔ)凸包Ω的信息,再將HCI消息傳輸至它的鄰居節(jié)點(diǎn);否則就丟棄HCI消息。

當(dāng)節(jié)點(diǎn)Ν離空洞越遠(yuǎn),它的視圖控制角θ就越小。當(dāng)節(jié)點(diǎn)Ν離空洞足夠遠(yuǎn)時(shí),視圖控制角θ就趨近于零。因此,當(dāng)αmin=0時(shí),凸包H的信息傳輸區(qū)域是整個(gè)網(wǎng)絡(luò)。本文將信息傳輸區(qū)域內(nèi)的節(jié)點(diǎn)稱為空洞感知節(jié)點(diǎn)HAN(Hole Aware Nodes),其他節(jié)點(diǎn)稱為盲節(jié)點(diǎn)BN(Blind Nodes)。

2.3 數(shù)據(jù)包傳輸

DG-SHGR路由引用兩種轉(zhuǎn)發(fā)模式:直接轉(zhuǎn)發(fā)GSF(Go Straight Forwarding)[10]和空洞繞開轉(zhuǎn)發(fā)HBF(Hole Bypassing Forwarding)。當(dāng)節(jié)點(diǎn)未遭遇路由空洞時(shí),即正常情況,就利用地理位置路由的貪婪轉(zhuǎn)發(fā)模式傳輸數(shù)據(jù)包,將這種方式稱為GSF。這不是本文研究的重點(diǎn)。本文的研究重點(diǎn)是HBF。

2.3.1 雷區(qū)FAR的定義

沿著HBSP傳輸數(shù)據(jù)包能夠減少端到端傳輸時(shí)延,并且防止數(shù)據(jù)包到達(dá)空洞邊界,緩解了局部最小問題。然而,如果所有數(shù)據(jù)包沿著HBSP傳輸,則增加了邊界網(wǎng)絡(luò)區(qū)域的負(fù)載,如圖1(b)所示。

設(shè)計(jì)DG-SHGR路由的目的就是依據(jù)數(shù)據(jù)包的時(shí)延要求,盡可能選擇最短路徑傳輸數(shù)據(jù)包。為此,針對(duì)每個(gè)數(shù)據(jù)包,定義雷區(qū)FAR。雷區(qū) FAR的尺寸正比于數(shù)據(jù)包傳輸?shù)臅r(shí)延要求。

以圖3為例。源節(jié)點(diǎn)s需向目的節(jié)點(diǎn)t傳輸一個(gè)數(shù)據(jù)包,且傳輸時(shí)延要求為15 s。即在15 s內(nèi)完成數(shù)據(jù)包的傳輸。圖3中的藍(lán)線表示從源節(jié)點(diǎn)s至目的節(jié)點(diǎn)t的HBSP路徑。假定這個(gè)路徑長度為100 m。

圖3 雷區(qū)FAR定義示例

因此,若沿著HBSP傳輸?shù)脑?則只需10 s。為了減少邊界傳輸?shù)呢?fù)載,并滿足數(shù)據(jù)包傳輸時(shí)延要求,數(shù)據(jù)包可沿著更長的路徑傳輸,只要路徑長度不超過150 m。為此,在傳輸時(shí)延的允許條件下,可適當(dāng)增加傳輸路徑,為此,定義雷區(qū)FAR。

DG-SHGR路由將雷區(qū)FAR定義為凸包H的擴(kuò)展區(qū)域,區(qū)域中心點(diǎn)位于H內(nèi),再依比例因子(scale factor)擴(kuò)展。

雷區(qū) FAR:基于比例因子,對(duì)凸包H進(jìn)行相似轉(zhuǎn)換所形成的區(qū)域?yàn)槔讌^(qū)FAR F。如果s和t是凸包H外的兩個(gè)任意節(jié)點(diǎn),且滿足式(1):

|LF(s,t)|≤|LH(s,t)|+(ξ-1)pH

(1)

式中:pH表示凸包H的邊。而LF表示雷區(qū)F的長度,相應(yīng)地,LH表示凸包H的長度。

2.3.2 下一跳節(jié)點(diǎn)的選擇

DG-SHGR路由引用特定的數(shù)據(jù)包格式,如圖4所示,其中轉(zhuǎn)發(fā)模式有GSF和HBF。scaleCenter表示雷區(qū)FAR的中心位置,存儲(chǔ)了中心位置的坐標(biāo)。scaleFactor為比例因子。傳輸時(shí)延D表示傳輸數(shù)據(jù)包所限定的時(shí)延。速度門限SpeedThreshold表示滿足傳輸時(shí)延D的最小HTHS。最后,數(shù)據(jù)Data為要傳輸?shù)臄?shù)據(jù)包。

圖4 數(shù)據(jù)包格式

①Hop-to-Hop 速度HTHS的計(jì)算

分別在GSF和HBF兩種轉(zhuǎn)發(fā)模式下,計(jì)算HTHS。

(2)

(3)

②速度門限SpeedThreshold的計(jì)算

當(dāng)轉(zhuǎn)發(fā)模式為GSF時(shí),SpeedThreshold的定義如式(4)所示:

(4)

式中:D表示預(yù)定的數(shù)據(jù)包傳輸時(shí)延要求,即必須在時(shí)延D內(nèi)將數(shù)據(jù)包傳輸至目的節(jié)點(diǎn)t。而elapsedtime表示數(shù)據(jù)包到達(dá)節(jié)點(diǎn)si已消耗的時(shí)間。因此,D-elapsedtime表示剩余時(shí)間remainingtime。

當(dāng)轉(zhuǎn)發(fā)模式為HBF時(shí),SpeedThreshold的定義如式(5)所示:

(5)

③雷區(qū)中心位置以及比例因子的計(jì)算

當(dāng)轉(zhuǎn)發(fā)模式為GSF時(shí),雷區(qū)中心位置和比例因子均為空。當(dāng)轉(zhuǎn)發(fā)模式為GSF時(shí),需利用雷區(qū)轉(zhuǎn)發(fā)數(shù)據(jù)包,進(jìn)而平衡網(wǎng)絡(luò)負(fù)載。因此,對(duì)凸包H進(jìn)行相似變換,且從凸包H內(nèi)隨機(jī)選擇中心位置,而比例因子ξ的定義如式(6)所示:

(6)

式中:R為節(jié)點(diǎn)傳輸范圍。而dm表示節(jié)點(diǎn)si的所有鄰居節(jié)點(diǎn)中的最大HTHD時(shí)延,其定義如式(7)所示:

(7)

式中:B表示節(jié)點(diǎn)si的鄰居節(jié)點(diǎn)集。

最后,依據(jù)節(jié)點(diǎn)的HTHS速度,構(gòu)建下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的候選集C。如果節(jié)點(diǎn)的HTHS速度大于SpeedThreshold,則將此節(jié)點(diǎn)加入候選集C,如式(8)所示:

(8)

然后再從C內(nèi)隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn),整個(gè)流程如圖5所示。

圖5 傳輸數(shù)據(jù)包的基本流程

3 性能仿真

3.1 仿真參數(shù)及性能指標(biāo)

依據(jù)NS2.35[12]建立仿真平臺(tái)。仿真區(qū)域?yàn)? 200×1 200 m2,200個(gè)源節(jié)點(diǎn)隨機(jī)分布在仿真區(qū)域內(nèi),且基站位于區(qū)域頂部。建立仿真的目的就是分析DG-SHGR路由處理路由空洞的能力。為此,在 1200 m×1 200 m區(qū)域內(nèi)分別產(chǎn)生18個(gè)空洞,分別標(biāo)注為Topology1、Topology2,…,Topology18,且空洞尺寸逐步增大。圖6顯示了3個(gè)空洞示例。

圖6 Topology1、Topology2和Topology3示例

此外,源節(jié)點(diǎn)每10 s產(chǎn)生一個(gè)數(shù)據(jù)包,數(shù)據(jù)包大小為50 byte。且每個(gè)數(shù)據(jù)包的傳輸時(shí)延要求從0.2 s、0.5 s和0.8 s中隨機(jī)選取,即D={0.2,0.5,0.8}。整個(gè)仿真時(shí)間為500 s。

為了更好地分析DG-SHGR路由的性能,選擇MMSPEED[5]和QAGOR[6]路由作為參照,并分析它們的數(shù)據(jù)包傳遞率和平衡指標(biāo)BI(Balance Index)[13]的性能。其中數(shù)據(jù)包傳遞率是指基站所接收的數(shù)據(jù)包數(shù)與源節(jié)點(diǎn)所發(fā)送的數(shù)據(jù)數(shù)比值。而BI反映了傳感節(jié)點(diǎn)間的流量負(fù)載的平衡性,其定義如式(10)所示:

(10)

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

圖7顯示了在D=0.2、D=0.5和D=0.8 3種情況下的數(shù)據(jù)包傳遞率。

從圖7可知,DG-SHGR路由所獲取的數(shù)據(jù)包傳遞率高于MMSPEED和QAGOR路由,并且隨著空洞尺寸的增加,優(yōu)勢越發(fā)明顯。

此外,MMSPEED和QAGOR路由隨空洞尺寸增加而數(shù)據(jù)包傳遞率迅速下降,而DG-SHGR路由仍保持穩(wěn)定。原因在于:DG-SHGR路由引用雷區(qū)概念。從圖7可知,即使在D=0.2 s時(shí),DG-SHGR路由仍保持75%的數(shù)據(jù)包傳遞率,而在D=0.5 s和D=0.8 s時(shí),數(shù)據(jù)包傳遞率保持95%以上。相反,在最糟糕的情況下(Topologies 18),MMSPEED路由在D=0.2 s、D=0.5 s和D=0.8 s 3種條件下的數(shù)據(jù)包傳遞率下降至30%、55%和61%。

從圖7可知,QAGOR路由的數(shù)據(jù)包傳遞率最差。例如,在Topology 16-19時(shí),QAGOR路由的數(shù)據(jù)包傳遞率低至1.0%。這也說明,空洞對(duì)QAGOR路由的影響最大。相比QAGOR,MMSPEED路由利用回壓機(jī)制能較好地處理路由空洞。盡管回壓機(jī)制能處理路由空洞,但是相比DG-SHGR路由,MMSPEED路由的數(shù)據(jù)包傳遞率仍較低。

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

3.3 平衡性能

本次實(shí)驗(yàn)分析QAGOR、MMSPEED路由和DG-SHGR路由的BI性能,實(shí)驗(yàn)數(shù)據(jù)如圖8所示。

圖8 BI性能

從圖8可知,DG-SHGR路由獲取高的BI的性能,這說明DG-SHGR路由利用動(dòng)態(tài)的雷區(qū)機(jī)制,有效地平衡負(fù)載。相比于QAGOR和MMSPEED相比,DG-SHGR路由的BI得到有效地提高。例如,在Topology 4時(shí),MMSPEED路由獲取最高的BI,但DG-SHGR路由的BI是MMSPEED路由的2倍。

與MMSPEED路由相比,QAGOR路由的BI得到提高,但是仍低于DG-SHGR路由。在空洞為Topology 6時(shí),DG-SHGR路由的BI是QAGOR路由的1.9倍。

4 總結(jié)

本文強(qiáng)調(diào)地理位置路由的路由空洞問題,并著力解決局部最小問題和邊界擁塞問題,提出基于時(shí)延要求的抑制路由空洞的地理位置路由。該路由以滿足數(shù)據(jù)包的傳輸時(shí)延要求為基礎(chǔ),即依據(jù)這個(gè)時(shí)延要求計(jì)算每個(gè)數(shù)據(jù)包的雷區(qū),進(jìn)而避開路由空洞,也緩解邊界擁塞問題。實(shí)驗(yàn)數(shù)據(jù)表明,與同類路由相比,提出的DG-SHGR路由提高了數(shù)據(jù)包傳遞率,平衡了負(fù)載。

后期,將進(jìn)一步優(yōu)化路由,并擴(kuò)展路由協(xié)議,使其滿足更多的路由指標(biāo),如可靠、吞吐量。這是后期研究工作的重點(diǎn)。