崔智軍

(1.安康學(xué)院 電子與信息工程學(xué)院，陜西 安康 725000；2.西北工業(yè)大學(xué) 電子信息學(xué)院，陜西 西安 710129)

無(wú)線網(wǎng)狀網(wǎng)絡(luò)的多路徑路由與調(diào)度算法*

崔智軍1，2

(1.安康學(xué)院電子與信息工程學(xué)院，陜西安康725000；2.西北工業(yè)大學(xué)電子信息學(xué)院，陜西西安710129)

提出了一種保障服務(wù)質(zhì)量的多路徑路由算法，數(shù)據(jù)分組可通過(guò)多條不同的路徑進(jìn)行傳輸，以提升網(wǎng)絡(luò)總吞吐量性能。進(jìn)一步提出了一種多路徑調(diào)度策略。通過(guò)使用調(diào)度策略，基于當(dāng)前可用帶寬信息和路徑所引入的時(shí)延信息，數(shù)據(jù)分組在傳輸前可被分成多段并通過(guò)不同的路徑發(fā)送，根據(jù)路徑時(shí)延調(diào)整優(yōu)化調(diào)度策略，從而使得數(shù)據(jù)可通過(guò)在不同的路徑上進(jìn)行更高效地傳輸。仿真實(shí)驗(yàn)進(jìn)一步驗(yàn)證了本文提出的路由機(jī)制和調(diào)度策略在不同網(wǎng)絡(luò)負(fù)載下的優(yōu)越性。

無(wú)線網(wǎng)狀網(wǎng)絡(luò)； 多路徑； 負(fù)載均衡

0 引 言

無(wú)線網(wǎng)狀網(wǎng)絡(luò)(wireless mesh networks，WMNs)是一種呈網(wǎng)狀拓?fù)浣Y(jié)構(gòu)且節(jié)點(diǎn)資源有限的無(wú)線自組織網(wǎng)絡(luò)，通常由網(wǎng)關(guān)、Mesh節(jié)點(diǎn)和路由器組成[1～3]。WMNs是一種高效且魯棒的可擴(kuò)展無(wú)線通信系統(tǒng)，且隨著各種路由及調(diào)度方法的出現(xiàn)，使得音視頻流的服務(wù)在WMNs上可行[4,5]，因而適用于實(shí)時(shí)應(yīng)急通信方案。由于無(wú)線鏈路之間的干擾和傳輸信號(hào)的衰落容易造成鏈路流量下降，會(huì)導(dǎo)致WMNs中的數(shù)據(jù)傳輸過(guò)程存在巨大的挑戰(zhàn)[6]。針對(duì)該問(wèn)題，有研究提出了利用多路徑傳輸視頻，一般根據(jù)路由跳數(shù)及時(shí)延對(duì)路由進(jìn)行評(píng)估，通過(guò)最小化路由的跳數(shù)或時(shí)延獲得最優(yōu)路徑[6，7]。而在WMNs中，采用多路徑路由協(xié)議可以節(jié)省帶寬，提高安全性和可靠性，也可以避免路由頻繁更新，提高數(shù)據(jù)的傳輸，增加帶寬。盡管目前基于WMNs已開(kāi)發(fā)了一些多路徑路由協(xié)議與算法，例如AOMDV,TORA,SMR協(xié)議與EECA算法[8～12]等，但多路徑負(fù)載平衡仍然是路由協(xié)議中難以解決的關(guān)鍵問(wèn)題。一方面，源節(jié)點(diǎn)的數(shù)據(jù)包分發(fā)策略可能導(dǎo)致速率分配不公平的問(wèn)題；另一方面，由于無(wú)線通信自身內(nèi)在的屬性可能會(huì)導(dǎo)致無(wú)線網(wǎng)狀網(wǎng)中的多路徑負(fù)載平衡的優(yōu)勢(shì)不太明顯?？梢钥闯?，高效的多路徑路由協(xié)議有助于延長(zhǎng)WMNs的生命周期。因此，在多路徑路由協(xié)議中，一方面，制定更有效的擁塞控制和速率調(diào)整策略亦變得尤為重要；另一方面，針對(duì)多路徑路由協(xié)議制定合適的路徑質(zhì)量評(píng)價(jià)指標(biāo)，對(duì)評(píng)估負(fù)載平衡和擁塞控制計(jì)劃同樣至關(guān)重要。

1 數(shù)學(xué)定義及描述

假設(shè)用圖G(V,E)描述一個(gè)包含N個(gè)節(jié)點(diǎn)的WMNs，其中,V為網(wǎng)絡(luò)節(jié)點(diǎn)的集合，E為集合V中節(jié)點(diǎn)組成的連接集合。每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)v∈V，其傳輸范圍為Rt(v)，載波感知范圍為Rc(v)。令eij表示連接節(jié)點(diǎn)vi到vj的邊，其中vi,vj∈E，且1≤i,j≤N。當(dāng)節(jié)點(diǎn)ni處于nj的傳輸范圍之內(nèi)，同時(shí)nj也在ni之內(nèi)時(shí)，則有eij∈E。

定義1：在連接e=(u,v)∈E上的負(fù)載LL(e)∈R表示在連接上L(u,v)的傳輸，其為通過(guò)該鏈路所有不同路徑流量負(fù)載之和。對(duì)于一個(gè)連接e∈E(e為兩個(gè)相臨節(jié)點(diǎn)u和v之間的連接)，令fm為鏈路e上的流量，e在路徑pm上，如果有M條路徑通過(guò)e，則e上的負(fù)載可表示為

(1)

類似地，pm上的負(fù)載為

(2)

定義2：鏈路上的傳輸延時(shí)d(e)∈R，由兩部分組成，隊(duì)列延時(shí)與傳輸延時(shí)。一般，不同鏈路間的延時(shí)互相獨(dú)立。

定義3：路徑上pm的延時(shí)d(pm)。對(duì)于從源節(jié)點(diǎn)i到目標(biāo)節(jié)點(diǎn)j的每條路徑，路徑pm由一組節(jié)點(diǎn)表示，ni,ni+1,… ,nj,且?k,i≤k≤j,(ni,ni+1)∈E，并且所有節(jié)點(diǎn)僅出現(xiàn)一次，如式(3)

(3)

定義4：路徑pm上的可得帶寬b(pm)，由路徑上最低鏈路的帶寬決定，如式(4)

b(pm)=min{b(nk,nk+1)},i≤k≤j

(4)

定義5：端到端的丟包率。鏈路上的丟包率相互獨(dú)立，令dr(nk,nk+1)為路徑(i,j)上的鏈路(nk,nk+1)的丟包率，則路徑(i,j)上的丟包率可由式(5)近似表示

(5)

此外，從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的多條路徑可以定義為P={p1,p2,...,pM}，其中,M為路徑的數(shù)量?？偟腗條路徑的帶寬B可表示為

(6)

本文多路徑路由問(wèn)題可以拆分為最小化端到端時(shí)延和擁塞檢測(cè)兩個(gè)子問(wèn)題進(jìn)行研究:

1)最小化端到端時(shí)延

數(shù)據(jù)分組被分發(fā)到M條路徑上，當(dāng)多路徑路由啟動(dòng)后，接收端節(jié)點(diǎn)為了能夠合并數(shù)據(jù)分組，需要從最長(zhǎng)的路徑發(fā)送的數(shù)據(jù)到達(dá)以后開(kāi)始解碼，因此，所產(chǎn)生的時(shí)延為

D(P)=max{D(pm)},m∈{1,…,M}

(7)

2)擁塞檢測(cè)

在多徑路由中的關(guān)鍵問(wèn)題之一是根據(jù)當(dāng)前的流量檢測(cè)即將來(lái)臨的超載，從而進(jìn)行流量控制。對(duì)于M條路的多路徑路由，源節(jié)點(diǎn)S需要通過(guò)多路徑發(fā)送或轉(zhuǎn)發(fā)。當(dāng)一個(gè)新的視頻流f以基本比特率rf進(jìn)入，并希望通過(guò)多路徑集合P輸出，S檢查是否f的傳輸會(huì)造成過(guò)載?；赟的傳入率檢測(cè)結(jié)果，數(shù)據(jù)分組被傳遞到多路徑?？梢钥闯觯绻窂絧的帶寬B(p)滿足條件B(p)≥rf，則S認(rèn)為多路徑集合P為能夠承載f；否則，如果B(p)

2 多徑路由與調(diào)度算法

2.1 路由發(fā)現(xiàn)機(jī)制

對(duì)具有N個(gè)節(jié)點(diǎn)的無(wú)線網(wǎng)狀網(wǎng)絡(luò)中，節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合記為N(i)，則Sij∈N(i)表示到達(dá)目標(biāo)節(jié)點(diǎn)j的子節(jié)點(diǎn)集合，令Sij(k)表示以i為源節(jié)點(diǎn)，以j為目標(biāo)節(jié)點(diǎn)數(shù)據(jù)流路徑上的節(jié)點(diǎn)k的下一跳節(jié)點(diǎn)集。

在網(wǎng)絡(luò)設(shè)置初始階段，所有節(jié)點(diǎn)均可以找到多個(gè)路徑到網(wǎng)關(guān)χ，網(wǎng)關(guān)χ廣播HELLO消息至其鄰節(jié)點(diǎn)。在收到HELLO消息后，在N(χ)的鄰近節(jié)點(diǎn)將啟動(dòng)“路徑發(fā)現(xiàn)”以尋找到所有網(wǎng)關(guān)的路徑并以可得帶寬升序進(jìn)行排列。這些節(jié)點(diǎn)進(jìn)一步廣播HELLO與鏈路的信息。其中，HELLO消息包含所有到χ的路徑及其序列。其他收到HELLO消息的節(jié)點(diǎn)可能會(huì)收到由同一χ發(fā)出的來(lái)自不同的路徑HELLO消息，進(jìn)而節(jié)點(diǎn)決定每條路徑上的父(parent)節(jié)點(diǎn)并增加到路由表中。之后，該節(jié)點(diǎn)單播一個(gè)Parent消息到選定的Parent節(jié)點(diǎn)。Parent消息包含了其已經(jīng)由HELLO消息選擇的所有路徑。至此，通過(guò)Parent消息將所用來(lái)傳輸?shù)穆窂礁嬷銹arent節(jié)點(diǎn)，從而Parent節(jié)點(diǎn)在路由表中記錄其子(child)節(jié)點(diǎn)并更新相應(yīng)的路徑。之后，Parent節(jié)點(diǎn)單播一個(gè)Child消息，通知所有路徑上的相應(yīng)節(jié)點(diǎn)，包括關(guān)于Child節(jié)點(diǎn)的網(wǎng)關(guān)χ和關(guān)于Child節(jié)點(diǎn)的可達(dá)路徑。在收到Child信息時(shí)，每個(gè)Parent節(jié)點(diǎn)在各自的路由表中注冊(cè)其Child節(jié)點(diǎn)，并按照類似的步驟注冊(cè)該Child節(jié)點(diǎn)可到達(dá)的多條路徑。通過(guò)這種方式，在從網(wǎng)關(guān)到Child節(jié)點(diǎn)的路徑中，包括網(wǎng)關(guān)的每個(gè)中間節(jié)點(diǎn)均有一個(gè)或多個(gè)路徑到響應(yīng)的Child節(jié)點(diǎn)。

2.2 路由維護(hù)機(jī)制

在WMNs中，當(dāng)添加新節(jié)點(diǎn)或一些現(xiàn)有的節(jié)點(diǎn)退出網(wǎng)絡(luò)之后，路由協(xié)議必須進(jìn)行更新維護(hù)。在尋找新的路徑或新的節(jié)點(diǎn)時(shí)，一個(gè)節(jié)點(diǎn)將更新其路由表，并將該信息通知鄰居節(jié)點(diǎn)。受影響的節(jié)點(diǎn)將及時(shí)通過(guò)該信息更新其路由表，并進(jìn)一步廣播。一個(gè)節(jié)點(diǎn)僅在得到網(wǎng)關(guān)χ準(zhǔn)入后，才可以被添加到該Mesh網(wǎng)絡(luò)中。入網(wǎng)后，每一個(gè)新的節(jié)點(diǎn)將發(fā)送一個(gè)Find信息，并找到網(wǎng)關(guān)的路由，進(jìn)而由網(wǎng)關(guān)來(lái)回復(fù)準(zhǔn)入或否決信息。

2.3 多徑調(diào)度算法

本文將數(shù)據(jù)流分割成多個(gè)片段，片段被傳遞到多路徑。為了克服流量擁塞的局限性，本文基于多路徑負(fù)載感知提出了一種新的自適應(yīng)調(diào)度傳輸方案。首先通過(guò)過(guò)載檢測(cè)提高多路徑傳輸?shù)聂敯粜?。?duì)于一個(gè)有M條路徑的無(wú)線網(wǎng)狀網(wǎng)路，起初能夠找到一種多路徑集。假設(shè)路徑pk具有最大d(pk)，則目標(biāo)節(jié)點(diǎn)將所有來(lái)自延時(shí)小于pk的路徑上的數(shù)據(jù)包緩存。本文針對(duì)每個(gè)節(jié)點(diǎn)上數(shù)據(jù)流的分發(fā)，提出了一種多路徑調(diào)度算法(multipath scheduling algorithm,MSA)，如圖1所示。

圖1 視頻流的多路徑調(diào)度

由圖1可以看出，給定M條路徑，P={p1,p2,…,pM}，則相應(yīng)的延遲分別為{d(p1),d(p2),…,d(pM)}。一個(gè)數(shù)據(jù)源在時(shí)間上分成t1,t2,…,tk個(gè)片段，其中，k為路徑數(shù)，各個(gè)路徑上的延遲有d(p1)<…

(8)

式中B為M條路徑的總帶寬；b(pi)為路徑pl上的帶寬;d(pi)為路徑pi上的延時(shí)。為了避免一個(gè)鏈路的負(fù)荷超載，流量根據(jù)瓶頸的剩余容量按比例分配。當(dāng)多路徑中的路徑彼此獨(dú)立時(shí)，負(fù)載均衡能夠有效抑制擁塞并獲得較高的數(shù)據(jù)傳輸率。因此，通過(guò)采用MSA，當(dāng)不同的路徑上的負(fù)載不同時(shí)，沿不同的路徑傳送相同數(shù)據(jù)段，將在同一時(shí)間到達(dá)目標(biāo),從而保證數(shù)據(jù)流的連續(xù)性。

3 仿真分析

3.1 衡量指標(biāo)

1)平均時(shí)延：所有傳輸成功的數(shù)據(jù)分組時(shí)延之和與所成功傳輸?shù)臄?shù)據(jù)分組個(gè)數(shù)之比

(9)

式中Di為第i個(gè)數(shù)據(jù)分組的端到端時(shí)延，主要包括MAC排隊(duì)時(shí)延、分組傳輸時(shí)延以及幀間間隔等時(shí)長(zhǎng)；N為傳輸成功的數(shù)據(jù)分組個(gè)數(shù)。

2)時(shí)延抖動(dòng):連續(xù)的數(shù)據(jù)分組延遲之間的差。例如，節(jié)點(diǎn)j在路徑m上的時(shí)延抖動(dòng)可表示為

(10)

(11)

r在m條路徑上的平均時(shí)延抖動(dòng)可表示為

(12)

3)丟包率：由于干擾或沖突導(dǎo)致丟失的分組個(gè)數(shù)Numlost與發(fā)送分組的總數(shù)Numtotal之比

η=Numlost/Numtotal

(13)

3.2 仿真設(shè)置

仿真基于NS—2網(wǎng)絡(luò)仿真軟件所搭建，使用的軟件版本為NS—2.35。網(wǎng)絡(luò)拓?fù)淙鐖D2所示，所有節(jié)點(diǎn)處于一個(gè)1 km×1 km的正方形區(qū)域內(nèi)。數(shù)據(jù)源的輸入為CBR視頻流業(yè)務(wù)，速率為128 kbps，視頻流輸入到WMNs并通過(guò)多條路徑傳輸?shù)侥繕?biāo)節(jié)點(diǎn)，而目標(biāo)節(jié)點(diǎn)再將接收到的數(shù)據(jù)流進(jìn)行解調(diào)與恢復(fù)。該WMNs有6個(gè)節(jié)點(diǎn)，其中有一個(gè)源節(jié)點(diǎn)S和一個(gè)目標(biāo)節(jié)點(diǎn)R。信道帶寬設(shè)置為2 Mbps，主要仿真參數(shù)遵循IEEE 802.11b協(xié)議[13]。

圖2 網(wǎng)絡(luò)仿真拓?fù)?/p>

3.3 仿真結(jié)果

圖3為平均分組時(shí)延曲線，其中每個(gè)點(diǎn)為50輪仿真均值?？梢钥闯觯寒?dāng)網(wǎng)絡(luò)流量負(fù)載大于600 kbps時(shí)，采用本文所提出的MSA可明顯降低數(shù)據(jù)包的傳輸時(shí)延。隨著網(wǎng)絡(luò)流量的持續(xù)增加，MSA可大幅度提升網(wǎng)絡(luò)性能。

圖3 平均分組時(shí)延

圖4為仿真中的平均時(shí)延抖動(dòng)性能?？梢钥闯觯寒?dāng)網(wǎng)絡(luò)業(yè)務(wù)量大于400 kbps時(shí)，采用MSA可以顯著降低網(wǎng)絡(luò)的分組時(shí)延抖動(dòng)，平均降幅約為30 %。需要注意的是，當(dāng)業(yè)務(wù)量大于1 400 kbps時(shí)，不采用MSA，時(shí)延抖動(dòng)急劇上升。表明MSA可以獲得高效的負(fù)載平衡性能。

圖4 平均時(shí)延抖動(dòng)

圖5為丟包率與網(wǎng)絡(luò)流量負(fù)載的關(guān)系?？梢钥闯觯S著網(wǎng)絡(luò)流量負(fù)載的增加，丟包率呈現(xiàn)出逐漸增加的趨勢(shì)。對(duì)于無(wú)MSA而言，當(dāng)網(wǎng)絡(luò)流量負(fù)載提高到600 kbps，其丟包率增加了約3.4 %左右。當(dāng)網(wǎng)絡(luò)流量負(fù)載逐漸增加時(shí)，無(wú)MSA算法與采用MSA算法之間的丟包率差距越來(lái)越大。表明MSA算法能自適應(yīng)地將數(shù)據(jù)分組分流到不同的路徑上。

圖5 丟包率

4 結(jié)束語(yǔ)

提出了一種基于Mesh網(wǎng)絡(luò)中多路徑路由與調(diào)度算法。根據(jù)不同路徑的帶寬和延遲，數(shù)據(jù)分組被分割為大小不同的數(shù)據(jù)流并分發(fā)到相應(yīng)的路徑上，數(shù)據(jù)流通過(guò)多條路徑到達(dá)目標(biāo)，從而提高M(jìn)esh網(wǎng)絡(luò)總吞吐量。該多路徑路由與調(diào)度算法可應(yīng)用于密集部署的網(wǎng)絡(luò)環(huán)境，如5G等網(wǎng)絡(luò)。

[1] Birlik Firat,Ercetin O,Gurbuz O.Prioritized video streaming in wireless mesh networks[J].Journal of Medical Genetics,2007,47(3):1-3.

[2] Chen Jiancong,Chan S,Li V.Multipath routing for video delivery over bandwidth limited networks [J].IEEE Journal on Selected Areas in Communications,2004,22(10):1920-1932.

[3] Li Shancang,Wang Xinheng,Zhao Shanshan.Multipath routing for video streaming in wireless mesh networks[J].Ad Hoc & Sensor Wireless Networks,2011,11(1):73-92.

[4] Mao Shiwen,Hou Y,Sherali H,et al.Multimedia-centric routing for multiple description video in wireless mesh networks[J].IEEE Network,2008,22(1):19-24.

[5] Wang Xinheng,Iqbal M,Zhou X.Design and implementation of a dual-radio wireless mesh network testbed for healthcare[C]∥Proceedings of the 5th International Conference on Information Technology and Application in Biomedicine,Shenzhen,China,2008:300-304.

[6] Wang Tao,Cui Xunxue,Liu Ping.A novel video monitoring system based on wireless mesh network[C]∥International Colloquium on Computing,Communication,Control,and Management,2008:542-546.

[7] Alariki H D E,Swamy M N S.A survey and analysis of multipath routing protocols in wireless multimedia sensor networks[J].Wireless Networks,2017,23(6):1823-1835.

[8] Zhu Yingnan,Zeng Wenjun,Liu Hang,et al.Supporting video streaming services in infrastructure wireless mesh networks:Architecture and protocols[C]∥IEEE International Conference on Communications,2009:1850-1855.

[9] Zhu Xiaoqing,Girod Bernd.Media-aware multi-user rate allocation over wireless mesh network[C]∥The 1st Workshop on Operator-Assisted Community Networks,Berlin,German,2006:1-8.

[10] Shui Guojun,Shen Shuchun.Video streaming transmission over multi-channel multi-path wireless mesh networks[C]∥The 4th International Conference on Wireless Communications,Networking and Mobile Computing,Dalian,China,2008:1-4.

[11] 楊海波.一種能量高效的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法[J].傳感器與微系統(tǒng),2008,27(7):50-52.

[12] 王世強(qiáng)，邢建春，李決龍,等.面向無(wú)線傳感器網(wǎng)絡(luò)的無(wú)線攜能通信研究[J].傳感器與微系統(tǒng),2015,34(8):46-53.

[13] ANSI/IEEE.802.11:Wireless LAN medium access control (MAC) and physical layer (PHY) specifications[S].IEEE 802.11 Std.2012:380-437.

Multipathroutingandschedulingalgorithmforwirelessmeshnetworks*

CUI Zhi-jun1,2

(1.CollegeofElectronicsandInformationEngineering,AnkangUniversity,Ankang725000,China;2.CollegeofElectronicsandInformation,NorthwesternPolytechnicalUniversity,Xi’an710129,China)

A novel multipath routing algorithm with QoS provision is presented,in which traffic takes multipath to reach the destination,thereby increasing the aggregated throughput.Based on proposed multipath routing algorithm,a scheduling strategy is further proposed,by which the traffic is divided into multiple segments before transmitted according to the path available bandwidth and path delay.The scheduling strategy can be adjusted according to the path delay,therefore data packets can be transmitted on multipath with more high efficiency.The routing scheme and the multipath scheduling strategy are verified by network simulations performed with different network load.

wireless mesh networks; multipath; load-balancing

10.13873/J.1000—9787(2017)12—0137—04

TN 925

A

1000—9787(2017)12—0137—04

2017—10—16

國(guó)家自然科學(xué)基金資助項(xiàng)目(61461025)；陜西省教育廳科學(xué)研究計(jì)劃資助項(xiàng)目(17JK0018)；國(guó)家級(jí)大學(xué)生創(chuàng)新訓(xùn)練項(xiàng)目(G201711397005)；安康學(xué)院校級(jí)青年基金資助項(xiàng)目(2017AYQN08)

崔智軍(1978-)，男，博士研究生，講師，主要從事微型磁通門(mén)傳感器研究工作。