基于鏈接成本反饋的WiMedia分布式路由協議

何榮毅,王小群,陳楷豐

(山東大學(威海)網絡與信息管理中心,山東 威海 264209)

0 概述

近年來,無線通信技術和消費電子的發展,使得在消費電子中的建設網絡成為可能,并加速了物聯網(Internet of Things,IoT)的快速增長[1-2]。IoT的主要目標是將現實世界中的現有對象或事物與因特網集成,以創建所有對象和機器自動交互的新方法。為向物聯網提供更多不同的應用,無線設備須支持比傳統無線技術更高的傳輸速率。超寬帶(Ultra Wide Band,UWB)技術是一種應用于高速無線數據傳輸和長距離定位的無線技術,由于其吞吐量優于Wi-Fi,因此適合于多媒體應用,UWB是市場上出現的較新的無線網絡技術,具有高數據速率和低功耗的客觀要求,其效率比Wi-Fi高80%～90%[3]。

WiMedia聯盟已經為高速WPAN指定了基于UWB的PHY/MAC標準。WPAN的傳統標準支持集中式MAC方法并形成微網。在物聯網應用中可同時操作微網(SOP),而移動性支持和為同步流提供服務質量(QoS)是核心需求[4-5]。例如,文獻[6]為提高WiMedia網絡資源的利用率,滿足服務速率和服務間隔的要求,提出一種資源分配算法,文獻[7]考慮了WiMedia標準中視頻流的流量規格和QoS要求,在對最大比特率進行預測的基礎上,提出一種估計CBR流和VBR流傳輸所需資源量的算法,并據此分配資源,文獻[8]提出一種考慮信道估計環境的資源預留方案,通過預留大量資源來提高網絡性能,文獻[9]使用包丟失、吞吐量、平均端到端延遲、平均抖動和路由開銷等各種性能指標來評估WiMedia網絡路由協議性能。上述算法都是集中式體系結構路由算法,但存在以下問題,首先協調器管理整個微微網,若協調器消失,網絡中的設備重新選擇新的PNC,浪費了大量的時間和精力,且在協調器的重新選擇過程中不能保證QoS,其次當2個或更多微微網彼此重疊時,IEEE 802.15.3協議的效率顯著降低(即SOP問題),最后是移動性支持不佳以及擴展WPAN覆蓋范圍的困難。為解決上述問題,WiMedia MAC協議支持分布式MAC方法,使所有設備具有相同的功能,并提供分布式時間同步方案。此外,WiMedia MAC協議采用分布式體系結構,可消除SOP問題。

近年來,人們針對應用于WiMedia標準的路由協議進行了大量的研究。然而,由于較少考慮信道條件,因此不能為實時應用程序提供完整的QoS。本文設計鏈接反饋信息元素(IE)結構形式,利用媒體接入時隙的數量和跳數來決定源設備和目的地設備之間的最佳路由。

1 研究背景

1.1 WiMedia標準

WiMedia標準使得所有設備具有相同的功能,并以分布式方式向設備提供諸如信道分配、數據傳輸和時間同步等功能[10]。WiMedia標準的超幀由信標周期(BP)和數據傳輸周期(DTP)組成,圖1為WiMedia標準的超幀結構。

圖1 WiMedia超幀結構

超幀具有固定的時間長度,并且被分成多個時間窗口,稱為媒體接入時隙(MAS)。超幀中的MAS數量為256,超幀的長度為65.536 ms。在BP算法中,每個設備選擇不與其他設備重疊的信標時隙,并在所選擇的信標時隙中廣播其信標。因此,為了在沒有沖突的情況下廣播其信標,所有設備都應該搜索沒有被其他設備占用的免費信標時隙。根據多個信息元素,設備可以共享用于網絡管理、移動性支持等的各種信息。超幀的起點是信標周期的開始時間,稱為信標周期開始時間(BPST)。超幀的其余部分用于傳輸數據,并且被分成2種類型的MAS塊。基于競爭的協議在一個MAS塊期間工作,而基于預留的協議在另一個MAS塊期間工作。基于競爭的協議稱為PCA,對于多個優先級排序的類類似于IEEE 802.11e標準。PCA是基于CSMA/CA的媒體接入,分為4個接入類別(AC),具有不同的優先級,用于異步業務傳輸。在PCA塊中,設備發送屬于相應AC的數據幀。

1.2 問題描述

圖2給出AODV路由協議的路由選擇示例。在圖2中,設備A和F超出了通信范圍,因此設備A不能直接向設備F發送數據包。然而,由于設備A使用路由協議發現從設備A到設備F的路由路徑,因此它可以通過設備B和E向設備F發送數據分組。

圖2 AODV協議的路由發現示例

傳統AODV路由協議通常能夠發現具有最小跳數的路由。因此,它可以選擇在源設備和目的地設備之間具有最短路徑的路由[11-12]。然而,傳統的AODV路由協議不適合基于預約的信道接入方案,并且不考慮用于通信的可用資源和每個鏈路支持的數據速率。因此,如果所選路由上的中間節點中有低效的可用資源,則整個網絡的性能降低。文獻[13]為WiMedia標準的DRP提出了新的路由協議,由于它們不考慮鏈路支持的數據速率,低數據速率的鏈路會降低網絡性能,因此傳統的路由協議不能充分利用較高速率的優點。為此,本文提出一個增強的路由協議,通過考慮WiMedia網絡中的信道條件來建立有效的路由。

2 鏈接反饋結構路由協議

本文路由協議可以找到數據速率最高的路由路徑,并提出了新的路由發現請求(R-REQ)IE和路由發現響應(R-REP)IE。R-REQ IE包括中間設備的地址、RREQ IE已經通過的鏈路的成本等。本節在設計鏈接反饋結構路由協議過程中采用預約機制,提出鏈接反饋IE結構形式,所有設備都可以獲得關于相鄰設備使用的鏈路數據速率的信息,利用源和目的地之間的中間設備計算路由成本以確定最佳路由,并利用媒體接入時隙的數量和跳數來決定源設備和目的地設備之間的最佳路由。

2.1 鏈路成本和所需資源計算

本文路由協議能夠找到由從源到目的地的中間鏈路支持的具有最高數據速率的路由。源和目的地之間的中間設備通過計算路由成本以確定最佳路由,并且目的地設備選擇具有最小鏈路成本的路由[14-15]。當路由上的設備數量為n時,所選擇的路由P表示為P(D1,D2,…,Dn),其中,Dk是路由上的節點。WiMedia標準提供鏈路反饋IE,其通告關于相鄰節點的數據速率和傳輸功率水平的信息。圖3所示為鏈接反饋IE結構形式。

圖3 鏈接反饋IE結構形式

在圖3中,DevAddr字段表示提供反饋的設備的地址。發送功率電平改變字段指示接收方向源設備推薦的發送功率電平的改變,而數據速率字段指示接收方設備向源設備推薦的數據速率。本文提出的路由協議通過考慮鏈路成本和傳輸數據包所需的資源來確定路由。設TDRP是發送數據包所需的DRP預留的持續時間,因此得到[16-17]:

(1)

其中,η是鏈路Li,j的MAC效率,即有效載荷傳輸的時間比例,PPERij是鏈路Li,j的相應分組錯誤率。根據式(2),通過鏈路Li,j傳輸數據包所需的MAS數量為[18-19]:

(2)

其中,TMAS是MAS的長度,為256 μs。根據式(3),端到端路由上的所有設備都可以計算所需的端到端數據流時隙數,則MAC效率η可計算如下[20]:

(3)

通過考慮確認(ACK)策略來估計MAC效率η。WiMedia標準提供了無確認(NoACK)、立即確認(Imm-ACK)和塊確認(B-ACK)3種ACK策略。No-ACK方案容易受到分組丟失的影響,在Imm-ACK中,每幀在短幀間空間(SIFS)持續時間之后被確認為一個ACK幀,可以提供可靠性。然而,Imm-ACK機制導致確認諸如多媒體流之類的接收業務突發的開銷量,在WiMedia標準和IEEE 802.11e標準中已經提出了B-ACK方案,以減輕這種開銷。

B-ACK機制允許源設備發送多個幀,并從接收方接收單個確認幀,該確認幀指示接收了哪些幀以及哪些幀需要重傳。由于在預留的傳輸持續時間中僅對所有幀使用一個ACK,因此開銷大大降低。因此,可將B-ACK策略應用于本文協議。圖4所示為DRP預約塊中B-ACK方案的幀事務。

圖4 B-ACK策略幀事務示例

總傳輸時間受鏈路支持的數據速率的影響,其計算公式如下:

(Nframe-1)×TMISF+2TSIFS+TB-ACK

(4)

其中,Nframe為數據幀號,WHeader和WPSDU分別為WiMedia標準的MAC報頭和有效負載的大小,Rmin為WiMedia標準支持的最小數據速率,WPre_S為標準前導碼的大小,WPre_B是突發前導碼的大小,TMISF和TSIFS是幀間間隔的持續時間,TB-ACK是B-ACK幀的傳輸時間。TB-ACK可計算為:

TB-ACK=TPre-S+THeader+

(5)

WiMedia標準的數據幀由前導、報頭和物理層服務數據單元(PSDU)組成。基于式(4)、式(5),TOverhead和TPSDU可計算為:

TMISF+2TsIFS+TB-ACK

(6)

(7)

鏈路Li,j的平均PER可計算為:

PPER=1-(1-BBER)8WPSDU

(8)

上述等式意味著路由上的中間設備可以計算傳輸數據分組所需的MAS數量,計算鏈路成本以確定最佳路線。總鏈路成本C是針對路由中的鏈路計算的數據速率的倒數和,計算公式為:

(9)

其中,n是路徑上的鏈接總數。路由上的所有設備計算鏈路成本,并在BP中廣播包括計算鏈路成本的RREQ IE。

2.2 路由發現過程

源設備廣播包括BP中的RREQ IE的信標幀,以將數據幀發送到超出范圍的另一設備。圖5給出建議的RREQ IE的格式。在圖5中,用戶DevAddr字段表示發送RREQ IE的設備的ID。

圖5 RREQ IE格式

如果源設備首先廣播包括所提RREQ IE的信標幀,則所有者DevAddr字段被設置為源DevAddr字段的值;源DevAddr字段指示首先廣播所提RREQ IE設備的地址,Dest DevAddr字段指示目的地設備的地址。服務數據長度字段指示提供服務所需的數據幀長度。

Hop Count字段指示源設備和目的地設備之間的跳數,并且當RREQ IE通過中間節點時,Hop Count字段的值增加1。鏈接成本文件包含使用式(9)計算的鏈接成本,DRP分配字段包含關于為多跳通信保留的資源的信息、區域位圖和MAS位圖的信息。為了便于資源分配,WiMedia標準提出二維超幀結構,將超幀劃分為16個區域。每個區域由16個MAS組成,并且對應于16×16超幀矩陣的每個列。圖6所示為接收RREQ IE的設備流程。

圖6 接收RREQ IE的設備流程

在圖6中,首先接收設備接收源設備廣播的包括RREQ IE的信標幀,基于接收到的RREQ IE信標幀確定路由目標的DevAddr字段。然后對當前字段的地址與目標DevAddr字段的地址進行對比,如果字段地址不符合,則丟棄該字段RREQ IE信標幀。如果滿足字段要求,再判斷是否在可用MASs范圍內,如果不在范圍內則丟棄該字段RREQ IE信標幀。如果滿足可用范圍條件,則繼續執行算法,更新鏈路消耗,如果目的地設備接收到RREQ IE,則它廣播包括所提RREP IE的信標幀。

圖7給出所提RREP IE的設備流程。在圖7中,源DevAddr字段指示源設備的地址,目標DevAddr字段包含目標設備的地址。用戶DevAddr字段指示廣播RREP IE的設備地址,而Target DevAddr字段指示已被選擇為中繼設備的地址。鏈路Cost字段指示由目的地設備計算的端到端路徑的總鏈路成本。Hop Count字段指示源設備和目標設備之間的跳數。DRP可用位圖字段指示關于可用資源的信息,如果相應的MAS可用,則字段中的每個位設置為“1”。如果請求預約的MAS已經被其他設備預約,則字段中的對應位被設置為“0”。如果沒有預約沖突,則設備不會更改DRP可用性位圖字段的值。

圖7 接收RREP IE的設備流程

在圖7中,接收RREP IE的設備首先確定目標DevAddr字段。如果目標DevAddr字段的值等于設備的地址,則檢查DRP可用位圖字段。如果請求資源與設備資源重疊,則創建DRP可用位圖字段,否則,設備將用戶 DevAddr字段設置為其地址,并選擇具有最小鏈接成本的目標設備,將目標DevAddr字段設置為要向其發送RREP IE的設備的地址。然后,設備廣播包括RREP IE的信標幀。如果目標DevAddr字段不等于其地址,則丟棄RREP IE。如果源設備接收到RREP IE,則構建Rconf IE。圖8給出了本文Rconf IE格式。

圖8 Rconf IE格式

接收RREP IE的源設備將關于保留資源的信息存儲到DRP Allocation字段。此外,在將Target DevAddr字段設置為位于路由路徑上的下一個設備的地址之后,它將Route Sequence字段設置為1,并廣播包括Rconf IE的信標幀,接收Rconf IE的設備確定目標DevAddr字段。如果目標DevAddr字段等于其地址,則將用戶DevAddr字段設置為其地址,并將目標DevAddr字段設置為沿路由路徑的下一個設備的地址。此外,將DRP分配字段設置為保留資源的信息,并廣播包括Rconf IE的信標幀。如果目標DevAddr字段不等于設備的地址,則丟棄接收到的Rconf IE。在廣播Rconf IE之后,設備在保留的資源中發送數據幀。

2.3 實例分析

圖9為本文路由協議的示例。為簡單起見,本文不考慮鏈路的分組錯誤率和MAC效率。此外,假設提供服務所需的數據長度是27 KB。

圖9 路由協議示例

在圖9中,圖9(a)顯示每個鏈接支持的數據速率和可用MAS的數量,在圖9(b)中,源設備A將包括RREQ IE的信標幀廣播到相鄰設備B和C,相鄰設備B和C在接收到RREQ IE時計算鏈路成本,設備B計算的鏈路成本是1/160,設備C計算的鏈路成本是1/200。圖9(c)為設備B和C廣播包括新鏈路成本的RREQ IE(參),設備B接收設備C發送的RREQ IE,并重新計算所接收的RREQ IE的鏈路成本,即(1/200+1/106.7),由設備B計算的新鏈路成本大于先前計算的鏈路成本(1/160)。因此,設備B丟棄從設備C接收的RREQ IE。設備C接收設備B發送的RREQ IE,并重新計算接收的RREQ IE的鏈路成本,即(1/160+1/106.7),由設備B計算的新鏈路成本大于先前計算的鏈路成本(1/200)。因此,設備C也丟棄從設備B接收的RREQ IE。設備E從設備B接收RREQ IE,而設備D從設備B和C接收RREQ IE。設備E在從設備B接收到RREQ IE時計算的鏈路成本是(1/160+1/106.7),并且由設備D在從設備B接收到RREQ IE時計算的鏈路成本是(1/160+1/53.3)。

由于設備C的鏈路成本小于設備B,因此設備D選擇設備C作為候選中繼設備。在圖9(d)中,設備D和E廣播RREQ IE。設備E從設備D接收RREQ IE并重新計算鏈路成本,即(1/200+1/480+1/320)。因為新鏈路成本小于先前計算的鏈路成本,所以設備E重新廣播包括新鏈路成本的RREQ IE(見圖9(e))。在圖9(d)中,設備G從設備E接收RREQ IE,但是它幾乎沒有足夠的資源來傳輸數據幀,因此,丟棄從設備E接收的RREQ IE。目的地設備F接收具有路由(A、B、E、F)和鏈路成本(1/160+1/106.7+1/400)、路由的RREQ IE(A、C、D、F)和鏈路成本(1/200+1/480+1/106.7)、具有路由的RREQ IE(A、C、D、E、F)和鏈路成本(1/200+1/480+1/320+1/400)。目的地設備F比較所有鏈路成本并選擇具有最小路由的路由,即路由(A、C、D、E、F)。隨后,目的地設備F將RREP IE與選擇的路由一起發送回源設備A(見圖9(f))。源設備A更新其路由表,因此建立從設備A到F的路由(見圖9(g))。源設備A廣播Rconf IE,包括已建立的路由的信息,當選擇的中間設備接收到Rconf IE時,為路由建立預留的資源信息(見圖9(h))。之后,路由上的所有設備在保留的MAS中發送數據幀。本文方案發現的路由可以提供比現有路由協議更好的吞吐量。

3 實驗結果與分析

3.1 實驗設置

使用openWNS模擬器[15]來評估本文方案的性能。openWNS是一個動態事件驅動的仿真平臺,包括WiMedia標準的實現。在仿真中,源設備總是向目標設備發送數據幀。WiMedia設備發送的分組有效負載大小為1 024 Byte,源對和目標對之間的業務負載是通過改變每秒的分組數量來生成的。此外,隨機地選擇源-目的地對作為網絡中業務負載,信標幀和ACK幀以53.3 Mb/s的強制速率傳輸。模擬中使用的參數如表1所示。

表1 仿真參數

此外,考慮具有無線IPTV和個人錄像機(PVR)記錄相同節目的多媒體應用。在某個時候,用戶使用遙控器,命令機頂盒(STB)啟動IPTV節目。機頂盒中的PVR同時開始在位于客廳旁邊壁櫥的無線連接的外部硬盤驅動器上記錄相同的程序。設服務提供者的視頻源使用實時傳輸協議(RTP)作為傳輸生成MPEG-4流,表2顯示了業務流的令牌桶TSPEC。

表2 業務流的令牌桶TSPEC特性

在該模擬中,假設所有設備隨機分布在100 m×100 m的正方形區域。給定網絡拓撲,隨機選擇源-目標對。將節點的通信半徑設為10 m,在仿真中評估了不同信道編碼參數對算法性能的影響,包括業務負載、節點數目和信噪比。在本文仿真中,將本文方案與WiMedia標準以及WiMedia網絡中的QoS路由協議進行了比較。

3.2 不同業務負載的實驗

在不同業務負載下,每50 s添加新的業務流,并且業務流的數量隨時間單調地增加。經過一定時間后,計算在整個網絡中傳輸的業務流的數量,并將其總和除以整個網絡飽和的業務流的數量,得到的數字被當作網絡的平均負載,設備的數量固定在40個。圖10為WiMedia標準、QoS路由和本文方案的吞吐量仿真結果。

圖10 3種協議的吞吐量仿真結果比較

在輕量業務下(發送的分組數較小情況下),本文算法的端到端吞吐量實驗結果非常接近選取的WiMedia標準和QoS路由2種協議。當流量增加時,WiMedia標準的DRP協議的缺點較為明顯,其端到端的吞吐量指標下降較多,主要原因是算法的效率低,導致數據傳輸過程中存在較為嚴重的數據擁堵問題。而QoS路由協議因為將數據傳輸服務質量(QoS)作為主要的評價指標,端到端的吞吐量作為QoS路由協議的主要考量指標,其具有相對較優的性能表現。本文協議相對于QoS路由協議的優勢在于,本文協議采用了預約機制的鏈接反饋IE結構形式,這種協議結構的優點在于其可有效避免無效數據的處理,從而節省了網絡資源和帶寬資源,具有相對較好的數據傳輸性能表現。因此,所提出的路由協議優于2個傳統協議。

圖11通過比較WiMedia標準、QoS路由和在各種業務負載下提出的路由協議,顯示了平均端到端延遲的仿真結果。在輕流量下,文獻[15]提出的QoS路由協議所經歷的分組端到端延遲結果與WiMedia標準的結果類似。隨著網絡流量的增加,本文路由協議逐漸優于WiMedia標準,因為網絡中的每個鏈路變得負載過重,所以WiMedia標準會出現網絡擁堵的情形,導致分組延遲情形的增加。而QoS路由協議是一種帶寬感知路由,它能夠確保在該路徑上保留足夠的帶寬。另外,由于QoS路由協議允許路由路徑上的所有設備使用預留的資源無爭用地發送數據幀,因此QoS路由協議可以減少擁塞。然而,QoS路由協議只考慮可用資源,選擇最短路徑,因此它不能獲得速率自適應調整,反映在實驗結果中就是本文算法在端到端延遲指標上的性能表現要顯著優于QoS路由協議。由于本文路由協議考慮了鏈路質量和每個鏈路支持的數據速率,因此可以選擇數據速率最高的路由路徑。因此,本文提出的路由協議優于2個傳統協議的端到端延遲性能。

圖11 3種協議的端到端延遲仿真結果比較

3.3 能源消耗實驗

圖12為每個協議中最小剩余能量的比較。本文協議和QoS路由的生命期比WiMedia標準要長,因為它們可以無競爭地發送數據幀。使用WiMedia標準的設備必須與相鄰設備進行數據傳輸。隨著網絡流量的增加,傳輸數據幀的爭用變得更加激烈,并且增加了沖突造成的數據丟失。因此,在WiMedia標準中,通過爭用和沖突進行重傳會增加能耗。然而,由于所提出的路由協議和QoS路由協議可以無競爭地發送數據幀,因此它們的性能優于WiMedia標準。然而,QoS路由協議只考慮可用資源,只選擇最短路徑,無法選擇最優的路由路徑。本文提出的路由協議考慮了每個鏈路所支持的數據速率,從而可以選擇數據速率最高的路由路徑。因此,本文路由協議比傳統的2種協議具有更好的節能性能。

圖12 最小剩余能量比較

4 結束語

本文提出一種考慮WiMedia網絡信道條件的多跳路由協議。該協議通過可用資源與每個鏈路的數據速率配置多跳通信的最佳路由路徑,是一種完全分布式的協議,其不依賴于網絡中設備之間的全局時間同步。在網絡棧的操作中,MAC層由路由層決定,不需要額外的控制分組建立路由,并提供路由協議來保證實時業務的QoS。仿真結果表明,與傳統WiMedia協議相比,本文路由協議可提高分組的傳輸率,明顯改善平均的端到端分組延遲。