尹鳳杰，關(guān)博文

(遼寧大學(xué) 信息學(xué)院，遼寧 沈陽 110036)

0 引言

無線Mesh網(wǎng)絡(luò)(WMN)作為一種關(guān)鍵技術(shù)越來越受到研究人員的關(guān)注，已經(jīng)成為寬帶家庭網(wǎng)絡(luò)、社區(qū)網(wǎng)絡(luò)和企業(yè)網(wǎng)絡(luò)等許多應(yīng)用的關(guān)鍵技術(shù).無線Mesh網(wǎng)絡(luò)是自組織和自配置網(wǎng)絡(luò)，其中參與節(jié)點能夠自動建立和維護連接，還能快速部署，具有易于維護、成本低并且可伸縮性高的特點.路由協(xié)議作為推動無線網(wǎng)絡(luò)發(fā)展的關(guān)鍵技術(shù)，是當(dāng)前國內(nèi)外研究人員較為注重的研究熱點.現(xiàn)有的無線Mesh網(wǎng)絡(luò)的路由協(xié)議大多是沿用了已有的Ad hoc網(wǎng)絡(luò)路由協(xié)議.移動無線網(wǎng)絡(luò)因其高移動性，所用路由協(xié)議多為被動路由協(xié)議.而無線Mesh網(wǎng)絡(luò)與典型的Ad hoc網(wǎng)絡(luò)如移動自組網(wǎng)(MANET)[1]、無線傳感器網(wǎng)絡(luò)(WSNs)[2]、車載自組網(wǎng)(VANETs)[3]等不同，無線Mesh網(wǎng)絡(luò)骨干的中繼Mesh路由器是靜態(tài)網(wǎng)格路由器，因此，混合路由協(xié)議更加適合無線Mesh網(wǎng)絡(luò).

已有的無線Mesh網(wǎng)絡(luò)混合路由協(xié)議中，人們更多地關(guān)注網(wǎng)絡(luò)的QoS(Quality of Service)指標，如文獻[4]提出一種針對無線Mesh局域網(wǎng)的解決方案，無線Mesh路由(WMR)在最小帶寬和最大端到端延遲方面提供了QoS保證.文獻[5]提出一種基于QoS的混合路由協(xié)議，該協(xié)議是在由基于IEEE802.16j的基礎(chǔ)設(shè)施和不同的基于IEEE802.11s的客戶端組成的混合的無線網(wǎng)絡(luò)體系結(jié)構(gòu)的基礎(chǔ)上提出的，文中所提出的HQMR(High Quality Mesh Router)路由協(xié)議在無線Mesh網(wǎng)絡(luò)中提供了QoS保證，并且為了降低網(wǎng)絡(luò)負載，提出了一種面向IEEE802.16j全局無線網(wǎng)絡(luò)體系結(jié)構(gòu)的聚類算法.HQMR協(xié)議有效地保證了無線Mesh網(wǎng)絡(luò)QoS指標，在平均吞吐量、平均端到端延遲和平均抖動方面有很好的表現(xiàn).但是QoS更多體現(xiàn)網(wǎng)絡(luò)技術(shù)層面的性能，當(dāng)今的網(wǎng)絡(luò)評價標準更多地應(yīng)該體現(xiàn)在用戶體驗方面，即QoE(Quality of Experience)指標.與QoS相比，QoE更能體現(xiàn)用戶主觀體驗，并且所涵蓋的物理指標也更為廣泛.所以，以QoE這一能夠體現(xiàn)用戶主觀感受的指標來評價網(wǎng)絡(luò)的性能是更令人信服的.文獻[6]提出一種OLSR(Optimized Link State Routing)路由協(xié)議，它基于度量的動態(tài)選擇，并在模糊鏈路成本中確定多媒體數(shù)據(jù)包的最佳路由，同時實現(xiàn)了多媒體應(yīng)用的QoS和QoE要求，但是因為模糊規(guī)則的收斂性較差，所以最終的效果有限.文獻[7]針對視頻流、音頻流、普通文件數(shù)據(jù)流3種網(wǎng)絡(luò)場景設(shè)計了完整的路由協(xié)議，在3種網(wǎng)絡(luò)場景中QoE指標有明顯的優(yōu)化效果，同時具有較低的控制報文開銷.研究使用基于雙向強化學(xué)習(xí)的路由算法，對不同服務(wù)的QoE進行預(yù)測，這可能會導(dǎo)致預(yù)估結(jié)果與實際結(jié)果相差較大，降低QoE的指標.

上述文獻主要是面向3種數(shù)據(jù)流通用的優(yōu)化路由協(xié)議，而現(xiàn)在的網(wǎng)絡(luò)更受用戶青睞的是視頻數(shù)據(jù)，也就是視頻流傳輸，本文以視頻流媒體為背景，從簇內(nèi)路由方面入手，加入網(wǎng)絡(luò)編碼，將傳統(tǒng)的MORE(MAC-independent Opportunistic Routing & Encoding)協(xié)議進行改進，使其能夠降低網(wǎng)絡(luò)傳輸?shù)难舆t，提高視頻的用戶體驗質(zhì)量.

1 基于QoE的分簇路由協(xié)議

為了使用本文的路由協(xié)議，實驗先將路由器分簇.為了實現(xiàn)分簇，網(wǎng)絡(luò)中所有的Mesh路由器會將自身的信息以Hello數(shù)據(jù)包的形式周期性地廣播給鄰居，以此讓網(wǎng)絡(luò)中的路由器完成鄰居Mesh路由器列表的建立，Hello數(shù)據(jù)包的格式如圖1所示.鄰居路由器在收到Hello數(shù)據(jù)包后會根據(jù)數(shù)據(jù)包的內(nèi)容更新鄰居表的內(nèi)容，這一列表在簇頭以及簇成員選擇的過程中有著很大的作用.鄰居表的格式如圖2所示.

圖1 Hello數(shù)據(jù)包的格式

圖2 鄰居表的格式

對于滿足QoE約束的路由器，鄰居路由器將會繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)包，關(guān)于Hello數(shù)據(jù)包的發(fā)送過程將一直持續(xù)，直到它滿足距離約束以及期望傳輸約束，式(1)和式(2)給出關(guān)于距離約束以及期望傳輸約束的條件.

(1)

(2)

其中，d(MRi，MRi+1)表示2個Mesh路由之間的距離，d(GW，MRi)表示網(wǎng)關(guān)到路由器的距離，dmax表示最大距離，EXT(MRi，MRi+1)表示2個Mesh路由之間的所需的期望傳輸數(shù)，EXT(GW，MRi)表示網(wǎng)關(guān)到路由器的所需的期望傳輸數(shù)，EXTmax表示最大的期望傳輸數(shù)，滿足式(1)以及式(2)中給出的約束的會被劃分為簇內(nèi)成員，分簇之后，同一簇內(nèi)的路由器需要選擇權(quán)重最大的簇成員作為簇頭，Mesh路由器的權(quán)重計算由式(3)表示，其中，W(v)表示路由器的權(quán)重，D(v)表示Mesh路由器的鄰居數(shù)量，B(v)表示Mesh路由器的可用帶寬，α、β是縮放因子.

W(v)=α×D(v)+β×B(v)

(3)

簇間路由協(xié)議為Mesh網(wǎng)絡(luò)簇間路由協(xié)議(ICMR)，該協(xié)議主要是在簇間建立通信，當(dāng)接收到數(shù)據(jù)請求，如果目標路由器不在同一簇內(nèi)，則使用反應(yīng)式路由協(xié)議建立通信，簇頭將請求轉(zhuǎn)發(fā)到Mesh網(wǎng)關(guān)，Mesh網(wǎng)關(guān)將會把包含Mesh路由器以及目的路由器所在的簇的簇頭地址回復(fù)給發(fā)出請求的簇頭，隨后簇頭會啟動請求程序，在源Mesh路由器以及目的Mesh路由器之間，尋找滿足丟包率以及視頻編碼比特率等QoE約束的最佳路徑.

2 基于改進的MORE協(xié)議的簇內(nèi)路由協(xié)議

本文的路由協(xié)議是針對簇內(nèi)通信提出的，當(dāng)簇頭接收到簇成員發(fā)來的數(shù)據(jù)傳輸請求時，簇頭會首先檢查自己的路由表，如果在路由表中找到目的地址，目的地址處于簇內(nèi)，那么就可以使用簇內(nèi)路由協(xié)議直接將數(shù)據(jù)轉(zhuǎn)發(fā)至目的地址，避免了向網(wǎng)關(guān)發(fā)送路由請求.在以視頻傳輸為主要傳輸目標的網(wǎng)絡(luò)中，傳統(tǒng)的“儲存—轉(zhuǎn)發(fā)”的數(shù)據(jù)處理方式會在一定程度上影響網(wǎng)絡(luò)的延遲，從而影響用戶的服務(wù)體驗，因此，本文采取在節(jié)點處加入網(wǎng)絡(luò)編碼的方式來降低網(wǎng)絡(luò)延遲，即在數(shù)據(jù)傳輸時采用“儲存—編碼—轉(zhuǎn)發(fā)”機制.

網(wǎng)絡(luò)編碼的原理[8]如圖3所示.圖中有3個節(jié)點，節(jié)點S需要將分組信息包p1傳輸至節(jié)點D，與此同時，節(jié)點D也要將分組信息包p2傳輸至節(jié)點S，因為2個節(jié)點受傳輸距離的限制，無法直接將信息包傳輸至目的節(jié)點，因此需要通過中間節(jié)點R進行數(shù)據(jù)的轉(zhuǎn)發(fā)，以此來完成本次傳輸.按照圖3(a)中傳統(tǒng)的儲存轉(zhuǎn)發(fā)式結(jié)構(gòu)進行本次的數(shù)據(jù)傳輸，在沒有數(shù)據(jù)包丟失的情況下，實驗共需要4次傳輸才能夠完成本次的信息交換.而使用加入了網(wǎng)絡(luò)編碼的結(jié)構(gòu)之后，如圖3(b)所示，當(dāng)節(jié)點S和節(jié)點D分別將信息包p1和p2傳輸至節(jié)點R之后，節(jié)點R偵察到有編碼的機會，便會將2個信息包進行編碼操作，將編碼后的數(shù)據(jù)包以廣播的形式傳輸給節(jié)點S和節(jié)點D，2個節(jié)點分別解碼后就可以得到期望的信息包.這種方式可以有效地節(jié)省一次傳輸.在網(wǎng)絡(luò)中，編碼的機會越多，那么通過網(wǎng)絡(luò)編碼獲得的收益也就越大，因此在視頻傳輸中，選擇網(wǎng)絡(luò)編碼的數(shù)據(jù)傳輸方式就可以在很大程度上降低網(wǎng)絡(luò)的延遲.

圖3 儲存轉(zhuǎn)發(fā)結(jié)構(gòu)與網(wǎng)絡(luò)編碼結(jié)構(gòu)

MORE協(xié)議是一種改進的機會路由協(xié)議[9]，它使用了隨機線性編碼，在數(shù)據(jù)包轉(zhuǎn)發(fā)之前會隨機選擇系數(shù)將數(shù)據(jù)包線性組合，生成的數(shù)據(jù)包會將各自使用的系數(shù)封裝在一個特殊的報頭之中，一般將其稱為MORE報頭，目的節(jié)點收到適當(dāng)數(shù)量的數(shù)據(jù)包后，就會通過逆函數(shù)執(zhí)行解碼過程，以得到需要接收的數(shù)據(jù)包.MORE協(xié)議的傳輸調(diào)度依賴于CSMA/CA，就吞吐量性能而言優(yōu)于ExOR等機會路由協(xié)議，具有一定的研究意義.此外，為了保證傳輸?shù)馁|(zhì)量，MORE協(xié)議有自己的確認機制，在源和中繼節(jié)點完成數(shù)據(jù)包的發(fā)送及轉(zhuǎn)發(fā)之后，源和中繼節(jié)點會持續(xù)地發(fā)送和重傳數(shù)據(jù)包，這一過程會一直持續(xù)到目的節(jié)點發(fā)送回確認信息為止.這會很大程度上保證數(shù)據(jù)包的傳輸成功率，但是對時延也會有不小的影響，而在視頻傳輸過程中按時傳輸往往比可靠更為重要.因此本文對MORE協(xié)議作了如下改進：1)將隨機線性編碼改變?yōu)檠舆t最小化網(wǎng)絡(luò)編碼；2)增加拒絕確認機制.

圖4 延遲最小化網(wǎng)絡(luò)編碼算法流程

2.1 延遲最小化網(wǎng)絡(luò)編碼

延遲最小化網(wǎng)絡(luò)編碼是最小化系統(tǒng)的總體接入時間，也就是從網(wǎng)絡(luò)中的所有用戶出發(fā)考慮最小的時延.對于單個用戶而言，假設(shè)該用戶所需的數(shù)據(jù)包數(shù)量為m，那么如果服務(wù)器在前m次廣播中，每一次都能夠得到自己所需要的新數(shù)據(jù)包，那么該用戶就可以得到理論上的最小接入時間，即m個單位數(shù)據(jù)包的傳輸時間m.也就可以理解為，單個用戶所需的接入時間取決于該用戶所需數(shù)據(jù)包在整個服務(wù)器的廣播序列中所占的位置，當(dāng)所需數(shù)據(jù)包發(fā)送出得越早，用戶的時延也就可相應(yīng)降低，用戶的服務(wù)體驗質(zhì)量就會越好.但是在日常中，整個系統(tǒng)往往不止1個用戶，如果系統(tǒng)每次的廣播都只針對某一用戶的數(shù)據(jù)請求，該用戶就可以以最短的時間獲得數(shù)據(jù)包，但是系統(tǒng)中的其他用戶就將遲遲無法得到自己所請求的數(shù)據(jù)包，對整個系統(tǒng)而言，數(shù)據(jù)的傳輸效率就會降低，整體時延將會上升，整體用戶的服務(wù)體驗質(zhì)量極有可能變得不可接受.因此，在數(shù)據(jù)包傳輸時需要考慮整體系統(tǒng)，以全局的時延優(yōu)化作為目標.那么，問題就變成了在每次傳輸中，如何將數(shù)據(jù)包編碼能夠滿足所有的用戶請求數(shù)據(jù).

延遲最小化網(wǎng)絡(luò)編碼的算法流程如圖4所示.M表示編碼組合能夠定位到的用戶數(shù)量，N表示用戶總數(shù).該算法流程將接收到的第1個請求數(shù)據(jù)包作為搜索條件，計算該數(shù)據(jù)包能夠定位到的用戶數(shù)量，如果所定位的用戶數(shù)量等于用戶的總數(shù)，那么該數(shù)據(jù)包就是本次傳輸?shù)淖顑?yōu)選擇，算法隨即將該數(shù)據(jù)包廣播，并且更新用戶的數(shù)據(jù)包接收以及請求信息，如果所定位的用戶數(shù)量不等于用戶總數(shù)，那么將編碼組合的大小增加至2，重新計算這2個數(shù)據(jù)包所能定位的用戶數(shù)量，如果等于用戶總數(shù)，就將這一編碼組合廣播給用戶，并更新接收和請求數(shù)據(jù)，如果不等于用戶總數(shù)，就將編碼組合大小增加至3，并繼續(xù)重復(fù)上述過程.算法的搜索會一直持續(xù)，直至找到能夠定位到所有的用戶的編碼組合，并將其廣播給用戶，發(fā)送完成后隨即更新用戶接收到的數(shù)據(jù)包以及請求數(shù)據(jù)包的信息.上述整個算法過程會不斷重復(fù)，直到所有用戶接收到所請求的數(shù)據(jù)包.

下面以一個實例來說明時延最小化網(wǎng)絡(luò)編碼傳輸方式.假設(shè)系統(tǒng)中共有4個用戶u1、u2、u3、u4，他們已經(jīng)接收到的數(shù)據(jù)包和正在請求的數(shù)據(jù)包如表1所示：

表1 系統(tǒng)中用戶已接收到的數(shù)據(jù)包與請求數(shù)據(jù)包

首先生成編碼數(shù)據(jù)集S={a1、a2、a3、a5、a6、a7、b2、b3、b4、b6、c2、c4、c7}，然后定位數(shù)據(jù)包a1所請求的用戶，只有用戶u2請求，顯然不滿足條件中定位所有的用戶，然后加入數(shù)據(jù)包a2，同樣還是只有用戶u2請求此數(shù)據(jù)包，加入數(shù)據(jù)包a3，此時有用戶u1、u3請求此數(shù)據(jù)包，這時定位用戶數(shù)為3，但是還未滿足條件，可以發(fā)現(xiàn)直到搜索至數(shù)據(jù)包a7時，編碼包{a1、a2、a3、a5、a6、a7}滿足定位到全部用戶這一條件，因此將這一編碼包作為本輪的最優(yōu)編碼包廣播給用戶，第1輪廣播后，用戶已收到的數(shù)據(jù)包與請求的數(shù)據(jù)包如表2所示.以此類推經(jīng)過4輪廣播后能夠滿足所有用戶的請求.

表2 第1輪廣播后用戶已收到數(shù)據(jù)包與請求數(shù)據(jù)包

2.2 增加拒絕確認機制

在原本的MORE協(xié)議中，源會持續(xù)發(fā)送同一批數(shù)據(jù)包直到接收到目的節(jié)點發(fā)回的確認通知，再開始下一批數(shù)據(jù)包的轉(zhuǎn)發(fā).很顯然，這種機制很難滿足時間的要求，因此，在改進的MORE協(xié)議中，通過強制源節(jié)點和中繼節(jié)點廣播有限的時間來克服這一問題，在這一協(xié)議中，源節(jié)點不會等待目的節(jié)點的確認信息，在源節(jié)點將數(shù)據(jù)包廣播之后，它會啟動1個倒計時器，所啟動的倒計時器為1個特定的時間間隔定義為τ，它以視頻流施加的時間約束來估計τ，假定傳輸1組幀速率為f，大小為g的圖片的視頻流，該視頻流必須在小于或等于g/f的時間段內(nèi)轉(zhuǎn)發(fā).如果該組圖片在平均l個大小為b的包中使用封裝，那么每一批數(shù)據(jù)包轉(zhuǎn)發(fā)需要等待τ，如式(4)所示.在倒計時時間歸零之后，立即啟動下一批數(shù)據(jù)包的廣播，而不管上一批是否交付成功.

τ=(g/f)/(l/k)=gk/fl

(4)

拒絕確認機制可以很好地控制轉(zhuǎn)發(fā)所需時間，這是一個極好的特性，因為對于源和中繼節(jié)點來說，持續(xù)發(fā)送已經(jīng)過時的數(shù)據(jù)包是十分浪費能量和時間的.因此在不需要考慮數(shù)據(jù)轉(zhuǎn)發(fā)是否可靠的情況下，增加拒絕確認機制能夠最大程度上降低時延.

3 仿真與分析

本實驗采用MATLAB仿真軟件進行實驗結(jié)果測量及分析.通過文獻[10]可以得知，對于網(wǎng)絡(luò)時延的影響主要有3個方面，用戶平均儲存數(shù)據(jù)的長度、用戶平均請求的數(shù)據(jù)長度以及用戶數(shù)，因此，本實驗以這3點為變量進行比較.實驗將加入了基于改進MORE協(xié)議的簇內(nèi)路由的分簇協(xié)議(IMIC)與加入基于原始MORE協(xié)議的簇內(nèi)路由的分簇協(xié)議(MIC)以及基于排序蟻群算法的分簇路由協(xié)議(SACR)在時延方面進行比較.

1)首先對比當(dāng)用戶平均儲存數(shù)據(jù)長度不同時，基于改進的MORE協(xié)議的簇內(nèi)路由協(xié)議的性能.本次實驗?zāi)M1個用戶數(shù)為4的場景，仿真時給每個用戶隨機生成大小為10的請求數(shù)據(jù)包，同時生成1個大小在4到14之間變化的已儲存數(shù)據(jù)包.進行1 000次隨機實驗并求出實驗的平均值.

圖5 用戶平均儲存長度不同時的時延

仿真結(jié)果如圖5所示，可以看出基于改進的MORE協(xié)議的簇內(nèi)路由協(xié)議當(dāng)用戶平均儲存數(shù)據(jù)長度較低時，原始的MORE協(xié)議有著更好的表現(xiàn)，但是當(dāng)用戶平均儲存數(shù)據(jù)長度增加時，改進的MORE協(xié)議性能逐漸改進，并且優(yōu)于其余2個路由協(xié)議.這是因為時延最小化網(wǎng)絡(luò)編碼，對于時延的優(yōu)化很大程度上取決于用戶所請求的數(shù)據(jù)包與用戶已儲存的數(shù)據(jù)包之間的重合度，當(dāng)用戶本身儲存的數(shù)據(jù)包較少時，時延最小化網(wǎng)絡(luò)編碼能夠搜尋到的最優(yōu)編碼機會也相應(yīng)減少，因此相對應(yīng)的時延就會較長，而隨著用戶儲存的數(shù)據(jù)包逐漸增多，延遲最小化網(wǎng)絡(luò)編碼能夠搜索到最優(yōu)編碼包的概率也將增加，時延相應(yīng)也會降低.而在實際應(yīng)用中，用戶所儲存的數(shù)據(jù)包與請求的數(shù)據(jù)包重合度會遠大于實驗所示.由此來看，基于改進MORE協(xié)議的簇內(nèi)路由協(xié)議在時延方面有著一定的提升.

圖6 用戶平均請求長度不同時的時延

2)本次實驗分析用戶平均請求數(shù)據(jù)長度對時延的影響，同樣模擬1個用戶數(shù)為4的仿真場景，仿真時隨機分配給每個用戶大小為10的數(shù)據(jù)儲存包，大小在1到10之間的數(shù)據(jù)請求包.進行1 000次隨機實驗并取平均值.

圖6顯示實驗結(jié)果，可以看出基于改進MORE協(xié)議的簇內(nèi)路由協(xié)議在所有不同的數(shù)據(jù)請求長度下，時延均低于基于原始MORE協(xié)議的簇內(nèi)路由協(xié)議和基于排序蟻群算法的分簇路由協(xié)議.正如在上一個實驗中所討論的，用戶的平均儲存數(shù)據(jù)足夠大，每個用戶的儲存數(shù)據(jù)與請求數(shù)據(jù)的重合度大概率也會增大，時延最小化網(wǎng)絡(luò)編碼能夠?qū)ふ业阶顑?yōu)編碼包的機會同時增加.從圖6的趨勢可以看出，當(dāng)用戶平均儲存數(shù)據(jù)長度一定時，請求數(shù)據(jù)長度越大，系統(tǒng)時延相應(yīng)也會增加.

圖7 用戶數(shù)不同時的時延

3)本次實驗需要驗證用戶數(shù)對系統(tǒng)時延的影響，因此分別選擇了用戶數(shù)為4、6、8、10的情況，仿真時，隨機向每個用戶分配大小相同的用戶儲存數(shù)據(jù)包以及請求數(shù)據(jù)包.實驗結(jié)果如圖7所示，可以發(fā)現(xiàn)，在不同用戶數(shù)情況下，基于改進的MORE協(xié)議的簇內(nèi)路由優(yōu)化效果并無明顯變化，說明所提出的路由協(xié)議的優(yōu)化能力并不受用戶數(shù)量的影響.

4 結(jié)論

本文提出了一種基于改進的MORE協(xié)議的簇內(nèi)路由協(xié)議，該協(xié)議以MORE協(xié)議為基礎(chǔ)，將MORE協(xié)議中所使用的隨機線性編碼改進為時延最小化網(wǎng)絡(luò)編碼，并且加入了拒絕確認機制，有效地降低了簇內(nèi)路由在數(shù)據(jù)包傳輸過程中的時延.實驗表明，基于改進MORE協(xié)議的簇內(nèi)路由能夠有效地提升用戶體驗質(zhì)量在時間方面的要求，使得無線Mesh網(wǎng)絡(luò)在QoE方面的性能進一步提高.