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

崔智軍

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

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

崔智軍1，2

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

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

無線網(wǎng)狀網(wǎng)絡； 多路徑； 負載均衡

0 引 言

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

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

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

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

(1)

類似地，pm上的負載為

(2)

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

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

(3)

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

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

(4)

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

(5)

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

(6)

本文多路徑路由問題可以拆分為最小化端到端時延和擁塞檢測兩個子問題進行研究:

1)最小化端到端時延

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

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

(7)

2)擁塞檢測

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

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

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

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

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

2.2 路由維護機制

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

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

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

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

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

(8)

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

3 仿真分析

3.1 衡量指標

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

(9)

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

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

(10)

(11)

r在m條路徑上的平均時延抖動可表示為

(12)

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

η=Numlost/Numtotal

(13)

3.2 仿真設置

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

圖2 網(wǎng)絡仿真拓撲

3.3 仿真結(jié)果

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

圖3 平均分組時延

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

圖4 平均時延抖動

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

圖5 丟包率

4 結(jié)束語

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

[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ǎng)絡分簇路由算法[J].傳感器與微系統(tǒng),2008,27(7):50-52.

[12] 王世強，邢建春，李決龍,等.面向無線傳感器網(wǎng)絡的無線攜能通信研究[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

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

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