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

黃 祎

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

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

然而,由于WSNs網絡的固有特性,如能量供應受限、傳感節點存儲容量和計算能力有限以及無線鏈路的不可靠性,滿足數據傳輸的端到端時延要求是不易的。

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

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

傳統的HTHS值正比于離目的節點距離。據以這個觀點,幾乎所有數據包均是沿著源節點至目的節點的連線路徑傳輸。這種路由策略適合于高密度節點區域,然而,當出現路由空洞時,這種路由策略會產生兩個問題:①路由空洞(局部最小問題),如圖1(a)所示,在連通目的節點方向上沒有鄰居節點,在這種情況下,數據包可能無法快速地傳輸至目的節點,甚至會導致數據包丟失。

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

圖1 地理位置路由的兩個問題

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

具體而言,對于每個數據包,先依據空洞區域定義“雷區”FAR(Forbidden Area),進而使得數據包能避開FAR,進而抑制空洞路由。而FAR的尺寸和位置隨數據包時延要求不同而變化,從而平衡網絡流量。為了保證數據包能及時到達目的節點,DG-SHGR路由利用端到端時延要求調整FAR尺寸。實驗數據表明,提出的DG-SHGR路由有效地提高了數據包傳遞率,并平衡網絡負載。

1 系統模型及定義

DG-SHGR路由假定每個節點知道自己的位置和一跳鄰居節點位置。此外,源節點知道目的節點的位置。

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

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

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

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

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

圖2 VLV定義示例

2 DG-SHGR路由

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

2.1 空洞檢測

引用文獻[9]的TENT規則,節點檢測自己是否在空洞邊上。如果在空洞邊上,節點(稱為邊界節點)就產生邊界坐標決策BCD(Boundary Coordinates Determination)消息,再利用文獻[9]引用的右手規則,沿著空洞邊界轉發BCD消息,進而收集信息。

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

2.2 空洞信息傳輸

所謂空洞信息傳輸就是將空洞凸包H的信息傳輸至圍繞著空洞的節點。傳輸半徑是由預定參數αmin控制,且0≤αmin≤π。若αmin=0,則表示將凸包H的信息傳輸至整個網絡;若αmin=π,則傳輸區域限制于凸包H。

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

當節點Ν離空洞越遠,它的視圖控制角θ就越小。當節點Ν離空洞足夠遠時,視圖控制角θ就趨近于零。因此,當αmin=0時,凸包H的信息傳輸區域是整個網絡。本文將信息傳輸區域內的節點稱為空洞感知節點HAN(Hole Aware Nodes),其他節點稱為盲節點BN(Blind Nodes)。

2.3 數據包傳輸

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

2.3.1 雷區FAR的定義

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

設計DG-SHGR路由的目的就是依據數據包的時延要求,盡可能選擇最短路徑傳輸數據包。為此,針對每個數據包,定義雷區FAR。雷區 FAR的尺寸正比于數據包傳輸的時延要求。

以圖3為例。源節點s需向目的節點t傳輸一個數據包,且傳輸時延要求為15 s。即在15 s內完成數據包的傳輸。圖3中的藍線表示從源節點s至目的節點t的HBSP路徑。假定這個路徑長度為100 m。

圖3 雷區FAR定義示例

因此,若沿著HBSP傳輸的話,則只需10 s。為了減少邊界傳輸的負載,并滿足數據包傳輸時延要求,數據包可沿著更長的路徑傳輸,只要路徑長度不超過150 m。為此,在傳輸時延的允許條件下,可適當增加傳輸路徑,為此,定義雷區FAR。

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

雷區 FAR:基于比例因子,對凸包H進行相似轉換所形成的區域為雷區FAR F。如果s和t是凸包H外的兩個任意節點,且滿足式(1):

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

(1)

式中:pH表示凸包H的邊。而LF表示雷區F的長度,相應地,LH表示凸包H的長度。

2.3.2 下一跳節點的選擇

DG-SHGR路由引用特定的數據包格式,如圖4所示,其中轉發模式有GSF和HBF。scaleCenter表示雷區FAR的中心位置,存儲了中心位置的坐標。scaleFactor為比例因子。傳輸時延D表示傳輸數據包所限定的時延。速度門限SpeedThreshold表示滿足傳輸時延D的最小HTHS。最后,數據Data為要傳輸的數據包。

圖4 數據包格式

①Hop-to-Hop 速度HTHS的計算

分別在GSF和HBF兩種轉發模式下,計算HTHS。

(2)

(3)

②速度門限SpeedThreshold的計算

當轉發模式為GSF時,SpeedThreshold的定義如式(4)所示:

(4)

式中:D表示預定的數據包傳輸時延要求,即必須在時延D內將數據包傳輸至目的節點t。而elapsedtime表示數據包到達節點si已消耗的時間。因此,D-elapsedtime表示剩余時間remainingtime。

當轉發模式為HBF時,SpeedThreshold的定義如式(5)所示:

(5)

③雷區中心位置以及比例因子的計算

當轉發模式為GSF時,雷區中心位置和比例因子均為空。當轉發模式為GSF時,需利用雷區轉發數據包,進而平衡網絡負載。因此,對凸包H進行相似變換,且從凸包H內隨機選擇中心位置,而比例因子ξ的定義如式(6)所示:

(6)

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

(7)

式中:B表示節點si的鄰居節點集。

最后,依據節點的HTHS速度,構建下一跳轉發節點的候選集C。如果節點的HTHS速度大于SpeedThreshold,則將此節點加入候選集C,如式(8)所示:

(8)

然后再從C內隨機選擇一個節點作為下一跳轉發節點,整個流程如圖5所示。

圖5 傳輸數據包的基本流程

3 性能仿真

3.1 仿真參數及性能指標

依據NS2.35[12]建立仿真平臺。仿真區域為1 200×1 200 m2,200個源節點隨機分布在仿真區域內,且基站位于區域頂部。建立仿真的目的就是分析DG-SHGR路由處理路由空洞的能力。為此,在 1200 m×1 200 m區域內分別產生18個空洞,分別標注為Topology1、Topology2,…,Topology18,且空洞尺寸逐步增大。圖6顯示了3個空洞示例。

圖6 Topology1、Topology2和Topology3示例

此外,源節點每10 s產生一個數據包,數據包大小為50 byte。且每個數據包的傳輸時延要求從0.2 s、0.5 s和0.8 s中隨機選取,即D={0.2,0.5,0.8}。整個仿真時間為500 s。

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

(10)

3.2 數據包傳遞率

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

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

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

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

圖7 數據包傳遞率

3.3 平衡性能

本次實驗分析QAGOR、MMSPEED路由和DG-SHGR路由的BI性能,實驗數據如圖8所示。

圖8 BI性能

從圖8可知,DG-SHGR路由獲取高的BI的性能,這說明DG-SHGR路由利用動態的雷區機制,有效地平衡負載。相比于QAGOR和MMSPEED相比,DG-SHGR路由的BI得到有效地提高。例如,在Topology 4時,MMSPEED路由獲取最高的BI,但DG-SHGR路由的BI是MMSPEED路由的2倍。

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

4 總結

本文強調地理位置路由的路由空洞問題,并著力解決局部最小問題和邊界擁塞問題,提出基于時延要求的抑制路由空洞的地理位置路由。該路由以滿足數據包的傳輸時延要求為基礎,即依據這個時延要求計算每個數據包的雷區,進而避開路由空洞,也緩解邊界擁塞問題。實驗數據表明,與同類路由相比,提出的DG-SHGR路由提高了數據包傳遞率,平衡了負載。

后期,將進一步優化路由,并擴展路由協議,使其滿足更多的路由指標,如可靠、吞吐量。這是后期研究工作的重點。