WSNs中滿足時(shí)延要求的空洞抑制路由

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

（1.長沙民政職業(yè)技術(shù)學(xué)院 軟件學(xué)院，長沙 410004；2.河南省電子政務(wù)內(nèi)網(wǎng)管理中心，鄭州 450003；3.湖南軟件職業(yè)學(xué)院 軟件與信息工程學(xué)院，湖南 湘潭 411100）

0 引言

目前，無線傳感網(wǎng)絡(luò)（wireless sensor networks,WSNs）[1-2]已在環(huán)境監(jiān)測、健康醫(yī)療、災(zāi)場救援等場景中得到了廣泛應(yīng)用。這些應(yīng)用要求傳感節(jié)點(diǎn)感測數(shù)據(jù)，將數(shù)據(jù)傳輸至控制中心。這些應(yīng)用對傳輸時(shí)延具有一定要求，而路由協(xié)議對數(shù)據(jù)傳輸時(shí)延有直接影響。

地理位置路由由于操作簡單、開銷低[3]，已經(jīng)廣泛地應(yīng)用到WSNs中。地理位置路由只是利用鄰居節(jié)點(diǎn)的位置信息決策路由，降低網(wǎng)絡(luò)開銷，例如，服務(wù)質(zhì)量（quality of service, QoS）感知的地理機(jī)會路由（QoS aware geographic opportunistic routing, QAGOR）[4]就是一個(gè)例示。

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

1 約束條件及定義

假定網(wǎng)絡(luò)內(nèi)各個(gè)節(jié)點(diǎn)知道自己的位置，數(shù)據(jù)包的目的節(jié)點(diǎn)的位置亦為網(wǎng)絡(luò)已知參數(shù)。

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

式中：di,i+1為Si與Si+1間距離；di,i+2為Si與Si+2間距離；n為傳感節(jié)點(diǎn)數(shù)。

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

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

圖1 視角和最短繞徑示例

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

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

5）空洞-最短繞徑（hole-bypassing shortest path,HBSP）。對于任意兩個(gè)空洞區(qū)域外的節(jié)點(diǎn)，沿著空洞區(qū)域存在順時(shí)針、逆時(shí)針方向的最短繞徑。而空洞-最短繞徑是指兩個(gè)最短繞徑中更短的最短繞徑。

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

2 DGGR路由

提出 DGGR路由的目的在于抑制路由空洞，即在滿足傳輸時(shí)延要求的條件下，避開空洞。DGGR路由主要由檢測空洞、收集空洞信息、擴(kuò)展轉(zhuǎn)發(fā)區(qū)和轉(zhuǎn)發(fā)數(shù)據(jù)等階段構(gòu)成。

2.1 檢測空洞

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

2.2 收集空洞信息

通過收集空洞信息，完成對空洞凸包H信息的收集，即收集空洞邊界節(jié)點(diǎn)的所有位置信息。為了控制網(wǎng)絡(luò)開銷，限定凸包H信息的傳輸范圍。設(shè)定二值參數(shù)αmin，由αmin控制傳輸范圍。如果αmin=π，凸包H信息的傳輸范圍限定于凸包H區(qū)域。反之，若αmin=0，則可將凸包H信息的傳輸至整個(gè)網(wǎng)絡(luò)。

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

2.3 擴(kuò)展轉(zhuǎn)發(fā)區(qū)及擴(kuò)展因子

2.3.1 擴(kuò)展轉(zhuǎn)發(fā)區(qū)

擴(kuò)展轉(zhuǎn)發(fā)區(qū)的目的在于，在滿足數(shù)據(jù)傳輸時(shí)延要求的前提下，增加數(shù)據(jù)轉(zhuǎn)發(fā)區(qū)域，即提供更多的數(shù)據(jù)轉(zhuǎn)發(fā)路徑。

依據(jù)上述分析可知，當(dāng)節(jié)點(diǎn)遭遇路由空洞時(shí)，若都沿著HBSP傳輸數(shù)據(jù)，能夠降低傳輸時(shí)延，并緩解路由空洞問題。然而，若所有節(jié)點(diǎn)都沿著HBSP傳輸數(shù)據(jù)，則會形成邊界網(wǎng)絡(luò)擁塞[8]。為此，通過定義擴(kuò)展轉(zhuǎn)發(fā)區(qū)，使得數(shù)據(jù)包避開邊界，緩解邊界擁塞?？紤]到數(shù)據(jù)傳輸時(shí)延，依據(jù)數(shù)據(jù)傳輸時(shí)延定義數(shù)據(jù)包的擴(kuò)展轉(zhuǎn)發(fā)區(qū)。擴(kuò)展轉(zhuǎn)發(fā)區(qū)的尺寸與數(shù)據(jù)傳輸時(shí)延成正比。

以圖2為例，源節(jié)點(diǎn)s需要向目的節(jié)點(diǎn)t傳輸數(shù)據(jù)包，并且該數(shù)據(jù)包的時(shí)延不能大于15 s，必須在15 s內(nèi)完成數(shù)據(jù)包的傳輸。假定該數(shù)據(jù)包沿著HBSP路徑傳輸只需要10 s。

圖2 擴(kuò)展轉(zhuǎn)發(fā)區(qū)示例

為了減少邊界負(fù)載，可選擇更長的路徑傳輸數(shù)據(jù)包，只要傳輸時(shí)延不超過15 s。在這種情況下，可以擴(kuò)展轉(zhuǎn)發(fā)區(qū)。這樣可將圖2的擴(kuò)展成

據(jù)此，將空洞凸包H進(jìn)行擴(kuò)展，形成擴(kuò)展區(qū)域，必須滿足時(shí)延要求。為此，定義擴(kuò)展因子，使其控制擴(kuò)展區(qū)域的尺寸。

假定ξ為擴(kuò)展因子。將凸包H依據(jù)ξ的比例進(jìn)行擴(kuò)展，形成轉(zhuǎn)發(fā)擴(kuò)展區(qū)F,并滿足

式中：pH為凸包H的邊；LF(s,t)為沿著擴(kuò)展區(qū)域從源節(jié)點(diǎn)s至目的節(jié)點(diǎn)t的路徑長度；LH(s,t)為沿著凸包H從源節(jié)點(diǎn)s至目的節(jié)點(diǎn)t的路徑長度。

2.3.2 擴(kuò)展因子

本文依據(jù)數(shù)據(jù)包的傳輸時(shí)延定義擴(kuò)展因子。假定源節(jié)點(diǎn)si需向目的節(jié)點(diǎn)t轉(zhuǎn)發(fā)數(shù)據(jù)包，它的HBSP路徑為LH(si,t)。該數(shù)據(jù)包的擴(kuò)展因子為

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

式中：Ni為si的鄰居節(jié)點(diǎn)集；為從節(jié)點(diǎn)si到節(jié)點(diǎn)sj的 AHHD時(shí)延，通過文獻(xiàn)[10]所提出的時(shí)延估計(jì)算法估計(jì)出值。

2.4 數(shù)據(jù)包的傳輸

當(dāng)節(jié)點(diǎn)未遭遇路由空洞時(shí)，就采用貪婪轉(zhuǎn)發(fā)策略傳輸數(shù)據(jù)包。若遭遇路由空洞，就采用空洞繞開策略轉(zhuǎn)發(fā)數(shù)據(jù)包。

2.4.1 選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)

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

由于存在貪婪轉(zhuǎn)發(fā)和空洞繞開轉(zhuǎn)發(fā)兩種模式，需分別從這兩種模式下計(jì)算HTHS。若數(shù)據(jù)包采用貪婪轉(zhuǎn)發(fā)，就不必計(jì)算擴(kuò)展區(qū)，這時(shí)就直接計(jì)算從節(jié)點(diǎn)si到節(jié)點(diǎn)sj的HTHS值為

式中：si為數(shù)據(jù)包攜帶節(jié)點(diǎn)；sj為si的鄰居節(jié)點(diǎn)；為si至目的節(jié)點(diǎn)t的距離；為sj至目的節(jié)點(diǎn)t的距離。

若數(shù)據(jù)包遭遇路由空洞，則需沿著擴(kuò)展區(qū)域F轉(zhuǎn)發(fā)數(shù)據(jù)包。與式（5）類似，在空洞繞開轉(zhuǎn)發(fā)模式下，從節(jié)點(diǎn)si到節(jié)點(diǎn)sj的HTHS值為

在貪婪轉(zhuǎn)發(fā)模式下，HTHSth的閾值為

若采用空洞繞開轉(zhuǎn)發(fā)，則 H THSth的閾值為

將節(jié)點(diǎn)si將鄰居節(jié)點(diǎn)集Ni內(nèi)所節(jié)點(diǎn)的 HTHS值與 H THSth進(jìn)行比較。如果HTHS＞ H THSth，說明能夠滿足數(shù)據(jù)包傳輸時(shí)延要求，將此節(jié)點(diǎn)納入候選轉(zhuǎn)發(fā)集ψi，即

一旦形成候選轉(zhuǎn)發(fā)集iψ，就從中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。這時(shí)iψ內(nèi)每個(gè)節(jié)點(diǎn)都滿足時(shí)延要求。

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

假定節(jié)點(diǎn)si需要向目的節(jié)點(diǎn)t傳輸數(shù)據(jù)包，源節(jié)點(diǎn)就傳輸數(shù)據(jù)包，其格式如圖3所示。

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

圖3中：第1個(gè)字段為轉(zhuǎn)發(fā)模式，占1個(gè)比特位。當(dāng)ForwardingModel=0，表示貪婪轉(zhuǎn)發(fā)；反之，F(xiàn)orwardingModel=1，則表示空洞繞開轉(zhuǎn)發(fā)；第 2字段為擴(kuò)展轉(zhuǎn)發(fā)區(qū)的中心位置，其占1個(gè)字節(jié)；第3字段為擴(kuò)展因子，占1個(gè)字節(jié)；第4字段為該數(shù)據(jù)包的傳輸時(shí)延[13]，即在此傳輸時(shí)延要求內(nèi)，完成數(shù)據(jù)包的傳輸。第4字段為數(shù)據(jù)包的目的節(jié)點(diǎn)；最后1個(gè)字段為真正要傳輸?shù)臄?shù)據(jù)包。

一旦接收了數(shù)據(jù)包，首先判斷自己是否為目的節(jié)點(diǎn)，若是，則直接傳輸。否則，就判斷自己是否遭遇路由空洞，若不是，則采用貪婪轉(zhuǎn)發(fā)，否則就采用空洞繞開轉(zhuǎn)發(fā)模式。圖4描述了數(shù)據(jù)傳輸?shù)牧鞒獭?/p>

圖4 DGGR路由流程

3 性能仿真

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

通過 NS2.35[14]網(wǎng)絡(luò)仿真軟件建立仿真平臺，分析DGGR路由處理路由空洞的能力。為此在1 200 m×1 200 m的仿真區(qū)域內(nèi)，部署18個(gè)空洞，空洞尺寸逐步增加。圖5顯示了 3個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的示例，白色區(qū)域表示空洞尺寸。

圖5 網(wǎng)絡(luò)拓?fù)涫纠?/p>

200個(gè)節(jié)點(diǎn)隨機(jī)分布在1 200 m×1 200 m的范圍內(nèi)。50個(gè)源節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)包率為0.1，且數(shù)據(jù)包大小為50字節(jié)。每個(gè)數(shù)據(jù)包的傳輸時(shí)延要求D從{0.2,0.5,0.8}中隨機(jī)選擇。仿真時(shí)間為500 s。

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

式中：N為節(jié)點(diǎn)數(shù)，這里取N=200；pi為傳感節(jié)點(diǎn)si傳輸?shù)臄?shù)據(jù)包數(shù)。依式（10）可知，BI表征了傳感節(jié)點(diǎn)間的流量負(fù)載的均衡性。

由于 DGGR路由旨在抑制路由空洞，在仿真過程中，選擇網(wǎng)絡(luò)中的空洞數(shù)作為參數(shù)變量，空洞數(shù)的數(shù)量從1個(gè)逐步增加至18個(gè)。

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

本次實(shí)驗(yàn)分析數(shù)據(jù)包傳遞率的影響，實(shí)驗(yàn)數(shù)據(jù)如圖6所示。

從圖6可知，不論D取何值，相比于姆姆斯勒（MMSR）和QAGR協(xié)議，提出的DGGR協(xié)議的數(shù)據(jù)包傳遞率最高。空洞拓?fù)鋽?shù)的增加，降低了MMSR和QAGR協(xié)議的數(shù)據(jù)包傳遞率，但DGGR協(xié)議的數(shù)據(jù)包并沒有隨空洞拓?fù)鋽?shù)變化而波動，保持穩(wěn)定的數(shù)據(jù)包傳遞率。

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

從圖6（a）可知，當(dāng)D=0.2 s，DGGR路由的數(shù)據(jù)包傳遞率達(dá)到75%，而當(dāng)D增加至0.5 s和0.8 s時(shí)，DGGR路由的數(shù)據(jù)包傳遞率仍達(dá)到95%。圖6（b）、圖6（c）具有類似的結(jié)果。DGGR路由之所以保持穩(wěn)定的數(shù)據(jù)包傳遞率，原因在于DGGR采用邊界轉(zhuǎn)發(fā)，并構(gòu)建了擴(kuò)展轉(zhuǎn)發(fā)區(qū)，在滿足時(shí)延要求的前提下，提高了數(shù)據(jù)包傳輸?shù)某晒β省?/p>

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

3.3 均衡性能

接下來分析 3個(gè)路由的均衡性能。取D=0.8s，取節(jié)點(diǎn)數(shù)為200，實(shí)驗(yàn)數(shù)據(jù)如圖7所示。

圖7 均衡性能

從圖7可知，相比于QAGR和MMSR路由，提出的 DGGR路由的 BI性能最高，這也說明DGGR路由有效地平衡流量負(fù)載。這歸功于DGGR路由通過設(shè)定擴(kuò)展轉(zhuǎn)發(fā)區(qū)，均衡了邊界轉(zhuǎn)發(fā)流量。

盡管QAGR路由的數(shù)據(jù)包傳遞率低于MMSR路由，但是它的BI性能優(yōu)于MMSR路由，但仍低于DGGR路由。

4 結(jié)束語

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