無線傳感網(wǎng)絡(luò)中基于時(shí)延感知的背壓路由?

章萬靜

(1.江蘇省軟件測試工程技術(shù)研究開發(fā)中心，江蘇 淮安 223003；2.江蘇電子信息職業(yè)學(xué)院計(jì)算機(jī)與通信學(xué)院，江蘇 淮安 223003)

無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)已廣泛應(yīng)用于環(huán)境檢測、康復(fù)醫(yī)療等應(yīng)用領(lǐng)域[1－2]。 WSNs 中的節(jié)點(diǎn)具有感測數(shù)據(jù)、傳輸數(shù)據(jù)的能力。 傳感節(jié)點(diǎn)先感測數(shù)據(jù)，然后將數(shù)據(jù)傳輸基站。因此，數(shù)據(jù)傳輸成為WSNs 研究熱點(diǎn)之一。

近期，背壓(Backpressure，BP)路由受到廣泛關(guān)注[3]。 原始的 BP 算法起源于 Tassiulas 和Ephremides 提出的無線數(shù)據(jù)包多跳網(wǎng)絡(luò)[4]。 BP 通過lyapunov drift 理論最大化網(wǎng)絡(luò)效益，優(yōu)化了吞吐量。

BP 路由就是通過節(jié)點(diǎn)間數(shù)據(jù)包隊(duì)列的擁塞剃度處理路由流量。 與其他路由機(jī)制不同，BP 路由并不構(gòu)建從源節(jié)點(diǎn)至目的節(jié)點(diǎn)間的具體路徑，只是構(gòu)建在每個(gè)時(shí)隙時(shí)的隊(duì)列積壓差。 BP 路由就是依據(jù)積壓差決策路由，進(jìn)而傳輸數(shù)據(jù)包。

相比于按需距離矢量路由(Ad hoc On-Demand Vector， ADOV) 和目的序列距離矢量路由(Destination Sequence Distance Vector，DSDV)等路由，BP 路由是通過節(jié)點(diǎn)間的數(shù)據(jù)包隊(duì)列積壓差決策路由，其存在以下優(yōu)勢:①最大化網(wǎng)絡(luò)吞吐量；②對于拓?fù)渥兓木W(wǎng)絡(luò)具有強(qiáng)的魯棒性。 然而，盡管BP路由優(yōu)化吞吐量，但是也存在時(shí)延、路徑冗長問題。BP 路由最初需消耗一定時(shí)間形成隊(duì)列積壓梯度，這增加了數(shù)據(jù)包的傳輸時(shí)延。

文獻(xiàn)[5]提出基于駐留時(shí)間的BP 改進(jìn)路由。利用隊(duì)列長度和數(shù)據(jù)傳輸時(shí)延計(jì)算數(shù)據(jù)包的駐留時(shí)間。 數(shù)據(jù)包在隊(duì)列中駐留時(shí)間越長，數(shù)據(jù)包被優(yōu)先傳輸?shù)母怕试礁摺?即優(yōu)先傳輸駐留時(shí)間長的數(shù)據(jù)包，減少數(shù)據(jù)包在隊(duì)列里的停留時(shí)間，進(jìn)而降低數(shù)據(jù)傳輸時(shí)延。 文獻(xiàn)[6]針對智能化WSNs，提出鏈路反轉(zhuǎn)算法協(xié)助的BP 路由，進(jìn)而降低數(shù)據(jù)包的傳輸時(shí)延。 文獻(xiàn)[7]提出基于虛擬梯度的BP 路由，利用虛擬梯度縮短時(shí)延。 此外，文獻(xiàn)[8]針對大型緊急物聯(lián)網(wǎng)，提出基于最短路徑的BP 改進(jìn)路由，優(yōu)先傳輸緊急數(shù)據(jù)包。

為此，針對BP 路由算法的傳輸時(shí)延問題，提出基于時(shí)延感知的背壓路由 ( Delay-Aware Backpressure Routing，DABR)。 DABR 路由依據(jù)隊(duì)列積壓差計(jì)算鏈路權(quán)值，并優(yōu)先激活權(quán)值大的鏈路，然后再優(yōu)先傳輸駐留時(shí)間長的數(shù)據(jù)包，縮短數(shù)據(jù)傳輸時(shí)延。 仿真結(jié)果表明，提出的DABR 路由縮短數(shù)據(jù)傳輸時(shí)延，并提升了數(shù)據(jù)包傳輸成功率。

1 傳統(tǒng)BP 路由不足及系統(tǒng)模型

1.1 BP 路由不足

圖1 隊(duì)列積壓差示例

然而，只依據(jù)隊(duì)列積壓差決策路由有兩個(gè)弊端:①節(jié)點(diǎn)需消耗較長時(shí)間形成數(shù)據(jù)包隊(duì)列積壓梯度；②若在在長時(shí)間內(nèi)無法形成數(shù)據(jù)包隊(duì)列積壓梯度，節(jié)點(diǎn)就無法傳輸數(shù)據(jù)包。 在決策路由時(shí)，并沒有考慮數(shù)據(jù)包在隊(duì)列內(nèi)駐留時(shí)間。

如圖2 所示，圖中有三個(gè)節(jié)點(diǎn)a，b，c。 在時(shí)隙t＝8 時(shí)，節(jié)點(diǎn)a，b，c 的隊(duì)列內(nèi)已存的數(shù)據(jù)包數(shù)分別為7，5、4。 若需要在鏈路(a，c)和(b，c)間選擇一條鏈路傳輸數(shù)據(jù)包，它們的數(shù)據(jù)包隊(duì)列積壓差分別為2 和1。 依據(jù)傳統(tǒng)的BP 路由，優(yōu)先激活鏈路(a，c)。

圖2 第一個(gè)數(shù)據(jù)包入隊(duì)時(shí)間

這個(gè)過程并沒有考慮到數(shù)據(jù)包在隊(duì)列的駐留時(shí)間。 假定在節(jié)點(diǎn)a 隊(duì)列中第一個(gè)數(shù)據(jù)包入隊(duì)的時(shí)隙thead＝3；在節(jié)點(diǎn)b 隊(duì)列中第一個(gè)數(shù)據(jù)包入隊(duì)的時(shí)隙thead＝1。 顯然，節(jié)點(diǎn)b 隊(duì)列內(nèi)的數(shù)據(jù)包駐留的時(shí)間更長。 但是傳統(tǒng)的BP 路由并沒有考慮到此問題。這就會增加數(shù)據(jù)包傳輸時(shí)延。

1.2 系統(tǒng)模型

將網(wǎng)絡(luò)操作時(shí)間劃分多個(gè)時(shí)隙，即t∈{0，1，2，…}。 在每個(gè)時(shí)隙t，DABR 路由就激活一條鏈路。利用有向圖G＝(N，L)表示無線多跳網(wǎng)絡(luò)，其中N表示節(jié)點(diǎn)集，L表示鏈路集。 位于源節(jié)點(diǎn)的數(shù)據(jù)包需貫穿多條鏈路[10]，并通過多跳通信才能達(dá)到目的節(jié)點(diǎn)。 用(i，j)表示節(jié)點(diǎn)i與節(jié)點(diǎn)j構(gòu)成的鏈路。 流量fc表示流向目的節(jié)點(diǎn)c的流量。 而Qfci表示在節(jié)點(diǎn)i的流量隊(duì)列。

2 DABR 路由

2.1 數(shù)據(jù)包的隊(duì)列積壓差

仍以圖3 為例，節(jié)點(diǎn)i與節(jié)點(diǎn)j間的wi，j(t)＝6。

圖3 無線多跳網(wǎng)絡(luò)(t＝8)

2.2 數(shù)據(jù)包入列的駐留時(shí)間

式中:k表示數(shù)據(jù)包類型。 圖3 給出了節(jié)點(diǎn)i三類數(shù)據(jù)包(1，2，3)的駐留時(shí)間，依據(jù)式(4)可得Qi(2)＝5。

2.3 鏈路權(quán)值

節(jié)點(diǎn)i依據(jù)式(5)計(jì)算一跳鄰居節(jié)點(diǎn)集Ni內(nèi)每個(gè)節(jié)點(diǎn)j∈Ni的鏈路權(quán)值:

式中:wi，j(t)μi，j值越大，鏈路單個(gè)時(shí)隙內(nèi)能夠傳輸?shù)臄?shù)據(jù)包數(shù)越大；μi，j表鏈路(i，j)的速率；選擇具有最大鏈路權(quán)值的節(jié)點(diǎn)作下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，即優(yōu)先激活最大鏈路權(quán)值的鏈路。

鄭州航院乃至河南省的二本高校若要圓滿實(shí)現(xiàn)中外合作辦學(xué)的培養(yǎng)目標(biāo)，培養(yǎng)更多高水平的國際化人才助力中原經(jīng)濟(jì)快速發(fā)展，英語是其無法避開的關(guān)鍵一環(huán)。中外合作辦學(xué)的英語教學(xué)不僅要提高學(xué)生的語言學(xué)習(xí)效率、幫助學(xué)生取得語言通行證，而且還要培養(yǎng)學(xué)生適應(yīng)國際化學(xué)習(xí)的能力、提升其跨文化溝通能力；同時(shí)也要調(diào)動教師的積極性，使項(xiàng)目內(nèi)學(xué)生英語運(yùn)用能力和專業(yè)學(xué)習(xí)能力的培養(yǎng)和發(fā)展得到保證。因此，在課程設(shè)置和課程建設(shè)方面與國際接軌勢在必行。全面學(xué)習(xí)、重點(diǎn)借鑒美國高校針對母語非英語國家留學(xué)生的強(qiáng)化英語課程設(shè)置以及其課程建設(shè)對我省高校中外合作辦學(xué)項(xiàng)目的英語教學(xué)十分有益。

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

依據(jù)式(5)選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)后，就激活此鏈路。 然后，節(jié)點(diǎn)i就依據(jù)式(4)選擇隊(duì)列中最長駐留時(shí)間的數(shù)據(jù)包傳輸。

2.5 傳輸數(shù)據(jù)包的示例

仍以圖3 為例，闡述傳輸數(shù)據(jù)包的過程。 依據(jù)式(2)，可得表1 所示的鏈路的數(shù)據(jù)包隊(duì)列積壓差。假定μi，j＝4 packets/slot，μi，?＝2 packets/slot。 首先選擇活具有最大權(quán)值的鏈路，即鏈路(i，j)被激活，然后傳輸?shù)诙悢?shù)據(jù)包(k＝2)，如圖3 所示。

表1 鏈路權(quán)值及駐留時(shí)間

2.6 基于BP 路由算法的實(shí)現(xiàn)

依據(jù)圖4 所示的模塊實(shí)現(xiàn)基于BP 路由，主要由數(shù)據(jù)包隊(duì)列管理、鄰居節(jié)點(diǎn)管理和下一跳節(jié)點(diǎn)選擇三個(gè)模塊組成。 數(shù)據(jù)包隊(duì)列管理模塊是用于調(diào)度數(shù)據(jù)包，包括入列和出列。

圖4 路由算法的實(shí)現(xiàn)模塊

而鄰居節(jié)點(diǎn)管理是主要由鄰居表的構(gòu)建和Hello 消息的管理兩個(gè)模塊組成。 鄰居表內(nèi)包含節(jié)點(diǎn)的當(dāng)前狀態(tài)信息，如IP 地址和它所的擁有隊(duì)列的長度。 而Hello 消息的管理負(fù)責(zé)Hello 消息的傳輸。

下一跳節(jié)點(diǎn)選擇是依據(jù)節(jié)點(diǎn)擁有數(shù)據(jù)包的緊急程度，決策下一跳的傳輸。 DABR 路由是依據(jù)具有最大權(quán)值的節(jié)點(diǎn)作為下一跳傳輸節(jié)點(diǎn)。

3 性能分析

3.1 仿真環(huán)境

利用NS－3[12]仿真軟件建立平臺。 作為開源的離散事件網(wǎng)絡(luò)仿真工具，NS－3 廣泛應(yīng)用于科學(xué)研究。 在μ＝1 packets/slot 網(wǎng)格內(nèi)部署36 個(gè)節(jié)點(diǎn)，如圖5 所示。 節(jié)點(diǎn)的通信半徑為250 m。 具體的仿真參數(shù)如表2 所示。

圖5 網(wǎng)格拓?fù)浣Y(jié)構(gòu)

表2 仿真參數(shù)

選擇文獻(xiàn)[13]提出的基于最短路徑的背壓路由(Shortest-path-based back-pressure routing，SPPR)和文獻(xiàn)[14]提出的低時(shí)延多播背壓路由(Lowlatency Multicast back-pressure Forwarding，LMPF)作為參照，并對比分析它們的數(shù)據(jù)包傳遞率、吞吐量和傳輸時(shí)延。

此外，通過類圖實(shí)現(xiàn)了路由，如圖6 所示，其主要包括以下四個(gè)類:①Routing Protocol 類:該類用于管理出列和入列的數(shù)據(jù)包，以及內(nèi)部關(guān)聯(lián)的其他類函數(shù)；②Queue 類:該類屬隊(duì)列管理模塊，用于管理數(shù)據(jù)包的出列或入列；③NextHopDecide 類:用于選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)并負(fù)責(zé)對鄰居節(jié)點(diǎn)的管理；④HelloSend 類:用于管理Hello 消息的傳輸以及鄰居節(jié)點(diǎn)的管理。

圖6 路由實(shí)現(xiàn)的類函數(shù)

3.2 吞吐量

首先分析數(shù)據(jù)包到達(dá)率對吞吐量的影響，考慮μ＝1 packets/slot 和μ＝3 packets/slot 兩種情況。 從圖7 可知，吞吐量隨數(shù)據(jù)包到達(dá)率的增加呈上升趨勢。 原因在于:數(shù)據(jù)包到達(dá)率越大，單位時(shí)間內(nèi)擁有的數(shù)據(jù)包數(shù)就越多。 這必然增加了網(wǎng)絡(luò)的提高了吞吐量。 但當(dāng)數(shù)據(jù)包達(dá)到率增加至1 packets/slot 后，吞吐量隨數(shù)據(jù)包到達(dá)率的增加而上升的速度變緩。

圖7 吞吐量

相比于SPPR，DABR 路由有效地提升的吞吐量。 這主要是因?yàn)?SPPR 路由是采用最短路徑?jīng)Q策路由，并沒有依據(jù)鏈路容量決策路由。 此外，DABR 路由與LMPF 路由的吞吐量相近，DABR 路由的優(yōu)勢并不明顯。 原因在于:LMPF 路由采用多播策略。 多播路由有利于提高吞吐量，尤其是在低數(shù)據(jù)包到達(dá)到率時(shí)，其吞吐量高于DABR 路由。 當(dāng)數(shù)據(jù)包到達(dá)率較大時(shí)，LMPF 路由的吞吐量逐漸下降。

此外，對比于圖7(a)與圖7(b)可知，鏈路速率的增加提升了吞吐量。 例如，在數(shù)據(jù)包到達(dá)到率為1.6 packets/slot 時(shí)，μ＝1 packets/slot 時(shí)的DABR 路由的吞吐量為0.6，當(dāng)μ＝3 packets/slot 時(shí)，DABR 路由的吞吐量達(dá)到0.63。 鏈路速率對吞吐量的影響并不大。

3.3 數(shù)據(jù)傳輸時(shí)延

數(shù)據(jù)傳輸時(shí)延是指將數(shù)據(jù)包從發(fā)送節(jié)點(diǎn)傳輸至接收節(jié)點(diǎn)的平均時(shí)間，其是衡量路由性能的重要指標(biāo)。 圖8 給出了μ＝1 packets/slot 和μ＝3 packets/slot 兩種情況下的數(shù)據(jù)包傳輸時(shí)延。

從圖8 可知，數(shù)據(jù)包到達(dá)率的增加，增加了數(shù)據(jù)傳輸時(shí)延。 原因在于:數(shù)據(jù)包到達(dá)率越大，網(wǎng)絡(luò)內(nèi)存儲的數(shù)據(jù)包數(shù)越多，隊(duì)列積壓越嚴(yán)重，這就增加了時(shí)延。 相比于LMPF 和SPPR 路由，DABR 路由有效地控制了數(shù)據(jù)包傳輸時(shí)延。 這歸功于:DABR 路由不僅考慮隊(duì)列積壓差，還考慮了數(shù)據(jù)包駐留時(shí)間，優(yōu)先傳輸駐留時(shí)間長的數(shù)據(jù)包，這就縮短了傳輸時(shí)延。

相比于LMPF 路由，SPPR 路由降低了其數(shù)據(jù)傳輸時(shí)延。 原因在于:SPPR 路由采用最短路徑策略決策路由，其縮短了數(shù)據(jù)傳輸?shù)穆窂健?此外，對比圖8(a)和圖8(b)不難發(fā)現(xiàn)，鏈路速率的增加降低了傳輸時(shí)延。 這符合預(yù)期:鏈路速率越大，單位時(shí)間內(nèi)傳輸?shù)臄?shù)據(jù)包數(shù)越多，隊(duì)列積壓數(shù)就越少，減少了數(shù)據(jù)傳輸時(shí)延。

圖8 數(shù)據(jù)傳輸時(shí)延

3.4 數(shù)據(jù)包傳輸成功率

最后，分析數(shù)據(jù)包到達(dá)率對數(shù)據(jù)包傳輸成功率的影響，如圖9 所示。

圖9 數(shù)據(jù)包傳輸成功率

從圖9 可知，數(shù)據(jù)包到達(dá)率的增加，降低了數(shù)據(jù)包傳輸成功率。 原因在于:數(shù)據(jù)包到達(dá)率的增加，增加了網(wǎng)絡(luò)內(nèi)的數(shù)據(jù)包數(shù)量，這就加大網(wǎng)絡(luò)負(fù)擔(dān)，最終降低了數(shù)據(jù)包傳輸成功率。

相比于LMPF，DABR 路由的數(shù)據(jù)包傳輸成功率較低，尤其是在數(shù)據(jù)包到達(dá)率較低時(shí)。 隨著數(shù)據(jù)包到達(dá)率的增加，DABR 路由與LMPF 路由的數(shù)據(jù)包傳輸成功率的差距逐步縮小。 原因在于:當(dāng)數(shù)據(jù)包到達(dá)率較大時(shí)，多播策略容易導(dǎo)致網(wǎng)絡(luò)擁塞。 一旦擁塞，就會降低數(shù)據(jù)包傳輸?shù)某晒β省?對比圖9(b)和圖9(a)可知，鏈路速率的增加，提升了數(shù)據(jù)包傳輸成功率，但是提升的幅度并不大。

4 總結(jié)

針對背壓路由的時(shí)延問題，提出時(shí)延感知的背壓路由DABR。 DABR 路由在決策路由時(shí)不僅考慮隊(duì)列積壓差，還考慮了數(shù)據(jù)包在隊(duì)列中的駐留時(shí)間，縮短數(shù)據(jù)傳輸時(shí)延。 通過分析DABR 路由的吞吐量、數(shù)據(jù)包傳輸成功率和數(shù)據(jù)傳輸時(shí)延性能，分析結(jié)果表明:DABR 路由在縮短傳輸時(shí)延的同時(shí)，并沒有降低吞吐量的數(shù)據(jù)包傳輸成功率。 后期，將一步分析DABR 路由的復(fù)雜度以及能耗問題，這將是后期的研究工作。