WSNs中滿足時延要求的空洞抑制路由

劉 立，朱 弘，蘇秀芝，謝英輝

（1.長沙民政職業技術學院 軟件學院，長沙 410004；2.河南省電子政務內網管理中心，鄭州 450003；3.湖南軟件職業學院 軟件與信息工程學院，湖南 湘潭 411100）

0 引言

目前，無線傳感網絡（wireless sensor networks,WSNs）[1-2]已在環境監測、健康醫療、災場救援等場景中得到了廣泛應用。這些應用要求傳感節點感測數據，將數據傳輸至控制中心。這些應用對傳輸時延具有一定要求，而路由協議對數據傳輸時延有直接影響。

地理位置路由由于操作簡單、開銷低[3]，已經廣泛地應用到WSNs中。地理位置路由只是利用鄰居節點的位置信息決策路由，降低網絡開銷，例如，服務質量（quality of service, QoS）感知的地理機會路由（QoS aware geographic opportunistic routing, QAGOR）[4]就是一個例示。

地理位置路由常遭遇路由空洞[5-6]問題，尤其在低密度節點網絡環境下更是如此。一旦遭遇路由空洞，常采用邊界轉發模式傳輸數據包。若路由空洞邊界上節點都沿著邊界轉發，也可能會造成邊界擁塞?？紤]到空洞路由問題和時延要求，本文提出基于時延要求的地理位置路由（delay-guaranteed-based geographic routing, DGGR）。DGGR路由先檢測路由空洞并解決路由空洞問題，在滿足時延要求的條件下，合理地選擇數據傳輸路徑，平衡各路徑的流量，進而避免邊界擁塞。仿真數據表明，提出的DGGR路由能有效地平衡網絡負載，提高數據包傳遞率。

1 約束條件及定義

假定網絡內各個節點知道自己的位置，數據包的目的節點的位置亦為網絡已知參數。

1）路由空洞（hole）。假定用連線依次連接傳感節點S1,…,Sn，其構成多邊形Θ。當滿足以下兩個條件，就形成路由空洞：①多邊形區域內不含任意任何傳感節點；②S1,…,Sn內相鄰節點的連線距離小于傳感節點的通信半徑r，且相隔一個節點的連線距離大于通信半徑r，其表達式為

式中：di,i+1為Si與Si+1間距離；di,i+2為Si與Si+2間距離；n為傳感節點數。

2）凸包（convex hull）。對于任意一個多邊形Θ，若某一個凸多邊形能覆蓋多邊形Θ，且具有相同的頂點，則該凸多邊形稱為該多邊形Θ的Θ凸包。

3）視點。若Q1，Q2,…,Qn為多邊形Θ的頂點，節點I是多邊形Θ外的一個節點。如果Qi與I連線與Θ不相交，則頂點Qi稱為I的視點，如圖1所示。

圖1 視角和最短繞徑示例

視點Qi、Qj與I連線的夾角，稱為視角。由如圖1（a）可以看出，節點I離空洞越遠，視角越小。若足夠遠，則視角就趨于零。

4）最短繞徑。從源節點至目的節點的最短繞徑是指沿著凸包的最短折線。如圖1（b）所示，源節點s至目的節點t的最短繞徑為LΘ(s,t)。

5）空洞-最短繞徑（hole-bypassing shortest path,HBSP）。對于任意兩個空洞區域外的節點，沿著空洞區域存在順時針、逆時針方向的最短繞徑。而空洞-最短繞徑是指兩個最短繞徑中更短的最短繞徑。

以圖1（b）為例，s、t為空洞區域凸包H的兩個節點。而Hs1、Hs2為節點s的視點，而Ht1、Ht2為t的視點。從源節點s至目的節點t的最短繞徑為：而空洞最短繞徑為這者間最小值，即HBSP =min {L+Θ(s,t),L-Θ(s,t)}。

2 DGGR路由

提出 DGGR路由的目的在于抑制路由空洞，即在滿足傳輸時延要求的條件下，避開空洞。DGGR路由主要由檢測空洞、收集空洞信息、擴展轉發區和轉發數據等階段構成。

2.1 檢測空洞

先利用文獻[7]的滕特（TENT）規則判斷節點是否為空洞節點。若自己遭遇空洞，則自己為空洞節點。一旦成為空洞節點，就形成邊界坐標決策信息（boundary coordinates determination, BCD），然后采用右手規則[7]，沿著邊界傳輸 BCD信息。通過BCD信息的傳輸，收集空洞信息。假定傳感節點Sj接收了傳感節點Si發送的BCD信息（BCDi）。首先檢測Xj是否小于Xi。如果Xj＜Xi，則利用右手規則轉發BCDi，否則就丟失。依據這種策略限定了只有一條BCD消息沿著邊界轉發，而且此條BCD消息是由橫坐標最大的空洞節點產生的，此節點也稱為BCD的啟發節點（BCD-H）。

2.2 收集空洞信息

通過收集空洞信息，完成對空洞凸包H信息的收集，即收集空洞邊界節點的所有位置信息。為了控制網絡開銷，限定凸包H信息的傳輸范圍。設定二值參數αmin，由αmin控制傳輸范圍。如果αmin=π，凸包H信息的傳輸范圍限定于凸包H區域。反之，若αmin=0，則可將凸包H信息的傳輸至整個網絡。

一旦BCD-H獲取了凸包H信息，就由BCD-H觸發空洞核心信息（hole core information, HCI）的傳輸，HCI包含了凸包H信息。隨后，BCD-H節點就向邊界節點傳輸HCI信息。一旦接收了HCI信息，節點就計算視角θ，并與αmin進行比較。若θ＞αmin，節點就存儲凸包H信息，并繼續向鄰居節點轉發HCI信息。若不滿足，就直接丟掉HCI信息。

2.3 擴展轉發區及擴展因子

2.3.1 擴展轉發區

擴展轉發區的目的在于，在滿足數據傳輸時延要求的前提下，增加數據轉發區域，即提供更多的數據轉發路徑。

依據上述分析可知，當節點遭遇路由空洞時，若都沿著HBSP傳輸數據，能夠降低傳輸時延，并緩解路由空洞問題。然而，若所有節點都沿著HBSP傳輸數據，則會形成邊界網絡擁塞[8]。為此，通過定義擴展轉發區，使得數據包避開邊界，緩解邊界擁塞?？紤]到數據傳輸時延，依據數據傳輸時延定義數據包的擴展轉發區。擴展轉發區的尺寸與數據傳輸時延成正比。

以圖2為例，源節點s需要向目的節點t傳輸數據包，并且該數據包的時延不能大于15 s，必須在15 s內完成數據包的傳輸。假定該數據包沿著HBSP路徑傳輸只需要10 s。

圖2 擴展轉發區示例

為了減少邊界負載，可選擇更長的路徑傳輸數據包，只要傳輸時延不超過15 s。在這種情況下，可以擴展轉發區。這樣可將圖2的擴展成

據此，將空洞凸包H進行擴展，形成擴展區域，必須滿足時延要求。為此，定義擴展因子，使其控制擴展區域的尺寸。

假定ξ為擴展因子。將凸包H依據ξ的比例進行擴展，形成轉發擴展區F,并滿足

式中：pH為凸包H的邊；LF(s,t)為沿著擴展區域從源節點s至目的節點t的路徑長度；LH(s,t)為沿著凸包H從源節點s至目的節點t的路徑長度。

2.3.2 擴展因子

本文依據數據包的傳輸時延定義擴展因子。假定源節點si需向目的節點t轉發數據包，它的HBSP路徑為LH(si,t)。該數據包的擴展因子為

式中：D為對該數據包的傳輸時延要求；Dr為已消耗的時間[9]；（r D-D）為剩余時間；dm為節點si的所有-跳鄰居節點中，具有最大平均跳-跳時延（average hop-to-hop delay, AHHD）的節點，其定義為

式中：Ni為si的鄰居節點集；為從節點si到節點sj的 AHHD時延，通過文獻[10]所提出的時延估計算法估計出值。

2.4 數據包的傳輸

當節點未遭遇路由空洞時，就采用貪婪轉發策略傳輸數據包。若遭遇路由空洞，就采用空洞繞開策略轉發數據包。

2.4.1 選擇轉發節點

現存的協議常通過跳速（hop-to-hop speed,HTHS）決策路由，并滿足數據傳輸時延要求。一條路由的 HTHS的值等于這條路由的距離與所需數據包的時延比值[11-12]。DGGR路由也延用HTHS概率，并依據HTHS值選擇轉發節點。

由于存在貪婪轉發和空洞繞開轉發兩種模式，需分別從這兩種模式下計算HTHS。若數據包采用貪婪轉發，就不必計算擴展區，這時就直接計算從節點si到節點sj的HTHS值為

式中：si為數據包攜帶節點；sj為si的鄰居節點；為si至目的節點t的距離；為sj至目的節點t的距離。

若數據包遭遇路由空洞，則需沿著擴展區域F轉發數據包。與式（5）類似，在空洞繞開轉發模式下，從節點si到節點sj的HTHS值為

在貪婪轉發模式下，HTHSth的閾值為

若采用空洞繞開轉發，則 H THSth的閾值為

將節點si將鄰居節點集Ni內所節點的 HTHS值與 H THSth進行比較。如果HTHS＞ H THSth，說明能夠滿足數據包傳輸時延要求，將此節點納入候選轉發集ψi，即

一旦形成候選轉發集iψ，就從中隨機選擇一個節點作為下一跳轉發節點。這時iψ內每個節點都滿足時延要求。

2.5 數據包傳輸

假定節點si需要向目的節點t傳輸數據包，源節點就傳輸數據包，其格式如圖3所示。

圖3 數據包格式

圖3中：第1個字段為轉發模式，占1個比特位。當ForwardingModel=0，表示貪婪轉發；反之，ForwardingModel=1，則表示空洞繞開轉發；第 2字段為擴展轉發區的中心位置，其占1個字節；第3字段為擴展因子，占1個字節；第4字段為該數據包的傳輸時延[13]，即在此傳輸時延要求內，完成數據包的傳輸。第4字段為數據包的目的節點；最后1個字段為真正要傳輸的數據包。

一旦接收了數據包，首先判斷自己是否為目的節點，若是，則直接傳輸。否則，就判斷自己是否遭遇路由空洞，若不是，則采用貪婪轉發，否則就采用空洞繞開轉發模式。圖4描述了數據傳輸的流程。

圖4 DGGR路由流程

3 性能仿真

3.1 仿真參數及性能指標

通過 NS2.35[14]網絡仿真軟件建立仿真平臺，分析DGGR路由處理路由空洞的能力。為此在1 200 m×1 200 m的仿真區域內，部署18個空洞，空洞尺寸逐步增加。圖5顯示了 3個網絡拓撲結構的示例，白色區域表示空洞尺寸。

圖5 網絡拓撲示例

200個節點隨機分布在1 200 m×1 200 m的范圍內。50個源節點產生數據包率為0.1，且數據包大小為50字節。每個數據包的傳輸時延要求D從{0.2,0.5,0.8}中隨機選擇。仿真時間為500 s。

為了充分地分析 DGGR路由性能，選擇文獻[6]提出的多徑多速度路由（multipath multispeed routing, MMSR） 和文獻[4]提出的蓋格勒（QAGR）進行同步仿真，并分析數據包傳遞率和均衡性能（balance index, BI）[15]，BI的定義為

式中：N為節點數，這里取N=200；pi為傳感節點si傳輸的數據包數。依式（10）可知，BI表征了傳感節點間的流量負載的均衡性。

由于 DGGR路由旨在抑制路由空洞，在仿真過程中，選擇網絡中的空洞數作為參數變量，空洞數的數量從1個逐步增加至18個。

3.2 數據包傳遞率

本次實驗分析數據包傳遞率的影響，實驗數據如圖6所示。

從圖6可知，不論D取何值，相比于姆姆斯勒（MMSR）和QAGR協議，提出的DGGR協議的數據包傳遞率最高?？斩赐負鋽档脑黾?，降低了MMSR和QAGR協議的數據包傳遞率，但DGGR協議的數據包并沒有隨空洞拓撲數變化而波動，保持穩定的數據包傳遞率。

圖6 數據包傳遞率

從圖6（a）可知，當D=0.2 s，DGGR路由的數據包傳遞率達到75%，而當D增加至0.5 s和0.8 s時，DGGR路由的數據包傳遞率仍達到95%。圖6（b）、圖6（c）具有類似的結果。DGGR路由之所以保持穩定的數據包傳遞率，原因在于DGGR采用邊界轉發，并構建了擴展轉發區，在滿足時延要求的前提下，提高了數據包傳輸的成功率。

相比于DGGR和MMSR路由，QAGR路由的數據包傳遞率最低。這說明 QAGR路由處理路由空洞能力極差。而MMSR路由引用回壓機制處理路由空洞，具有一定的應對路由空洞的能力。但相比于DGGR路由，MMSR路由的數據包傳輸率仍較低。

3.3 均衡性能

接下來分析 3個路由的均衡性能。取D=0.8s，取節點數為200，實驗數據如圖7所示。

圖7 均衡性能

從圖7可知，相比于QAGR和MMSR路由，提出的 DGGR路由的 BI性能最高，這也說明DGGR路由有效地平衡流量負載。這歸功于DGGR路由通過設定擴展轉發區，均衡了邊界轉發流量。

盡管QAGR路由的數據包傳遞率低于MMSR路由，但是它的BI性能優于MMSR路由，但仍低于DGGR路由。

4 結束語

針對 WSNs的路由問題，提出基于時延要求的地理位置路由 DGGR。DGGR路由在滿足數據包傳輸時延要求下，解決路由空洞問題。通過檢測路由空洞，然后給遭受路由空洞的數據包定義擴展轉發區，使得數據包沿著擴展轉發區傳輸，避開路由空洞，并緩解邊界轉發的擁塞問題。仿真數據表明，提出的 DGGR路由能有效地提高數據包傳遞率，并平衡了邊界節點的負載。