0 引言

    在無線Mesh網(wǎng)絡中,，信道分配和路由協(xié)議是較為關鍵的問題，且二者聯(lián)系緊密,。如何協(xié)調(diào)其關系以更好地利用網(wǎng)絡資源,、提升網(wǎng)絡性能是當前研究熱點之一,。對于信道分配的分類，按照網(wǎng)絡中Mesh節(jié)點（Mesh Point,，MP）射頻接口數(shù)量的不同,，可分為單射頻信道分配和多射頻信道分配,。由于后者能帶來更大的網(wǎng)絡吞吐量，因此應用更為廣泛^[1],。此外,，若根據(jù)信道更新頻繁程度，又可分為靜態(tài)信道分配,、動態(tài)信道分配和混合信道分配^[2],。而對于路由選擇，按照路由建立和業(yè)務請求之間的關系,，可以分為先驗式路由協(xié)議^[3],、反應式路由協(xié)議^[4]和混合式路由協(xié)議^[5]。

    傳統(tǒng)的無線Mesh網(wǎng)絡中,，信道分配和路由選擇是分開進行的,，一般先進行信道分配，再執(zhí)行路由選擇,。當網(wǎng)絡拓撲以及業(yè)務流量相對穩(wěn)定時,，該方式可以充分地利用網(wǎng)絡資源。然而一旦網(wǎng)絡拓撲或鏈路負載發(fā)生變動,，以上方法無法根據(jù)實時信息調(diào)整資源配置,，致使資源利用率大幅降低，甚至出現(xiàn)節(jié)點孤立,，影響正常的數(shù)據(jù)傳輸,。

    針對上述問題，近年來出現(xiàn)了諸多關于融合信道分配和路由選擇的研究,，大致可分為集中式^[6]和分布式^[7]兩類,，其中分布式路由算法不需要中央處理節(jié)點，且可避免因單個節(jié)點失效導致整個網(wǎng)絡崩潰的危險,，因此得到更為廣泛的研究和應用,。本文主要針對多射頻多信道(Multi-Radio Multi-Channel，MRMC)無線Mesh網(wǎng)絡中網(wǎng)絡負載及節(jié)點位置實時變化等實際場景,，在混合無線網(wǎng)狀路由協(xié)議（Hybrid Wireless Mesh Routing Protocol,，HWMP）反應式路由基礎上，設計了一種新的混合信道分配的分布式路由算法（Routing based on Hybrid Channel Assignment,，RHCA）,。

1 信道分配方案

    由于本文提出的RHCA方案基于動態(tài)網(wǎng)絡設計，因此信道分配策略應采用動態(tài)分配或混合分配,?？紤]到混合分配方案具有更好的網(wǎng)絡連通性，故選擇后者。

1.1 系統(tǒng)模型

    本文無線Mesh網(wǎng)絡模型如圖1所示,，采用網(wǎng)格型網(wǎng)絡拓撲,，共設置32個節(jié)點，相鄰節(jié)點間距170 m,。且本文的信道分配過程只考慮如何減小鏈路干擾,，達到以數(shù)據(jù)流為單位的鏈路干擾最小化信道分配。其余諸如網(wǎng)絡負載等因素的影響則在路由選擇時考慮,。干擾模型方面采用文獻[8]中的協(xié)議干擾模型,，如圖2所示，當鏈路e_i,、e_j節(jié)點間跳數(shù)不少于兩跳時,，才認為二者無相互干擾。雖然該模型是一個NP問題,，但其信道分配模型融合于路由算法中,，具體分配方式將在后文中詳述。

1.2 接口分配策略和通信協(xié)調(diào)機制

    在接口分配上,，所有節(jié)點均固定使用一個無線射頻接口搭配標號為1的信道作為固定接口,，用于傳遞網(wǎng)絡管理消息，當網(wǎng)絡負載較重時亦可傳送數(shù)據(jù),。其余接口全部用于數(shù)據(jù)傳輸,，稱為動態(tài)接口(Dynamic Radio Interface，DRI),，其分配信道在傳輸過程中可實時切換,。

    另外，本文的通信協(xié)調(diào)機制主要通過分析網(wǎng)絡中的相鄰節(jié)點DRI信道分配,、路徑請求（Path Request,，PREQ）消息幀前兩跳DRI信息以及各個節(jié)點Metric信息等,，得到與下一跳鏈路干擾最小的信道,。該機制在路由過程中實施。當源節(jié)點發(fā)送PREQ,，尋得最優(yōu)路徑之后,，目的節(jié)點在回復路徑響應（Path Reply，PREP）消息過程中逐一節(jié)點綁定通信接口,，并分配信道,。

1.3 接口釋放機制

    本文對源節(jié)點的接口釋放機制進行了如下設計。在開始發(fā)起數(shù)據(jù)業(yè)務后,，數(shù)據(jù)流監(jiān)聽模塊隨即啟動,，并設置監(jiān)聽標志位tags為1，表示監(jiān)聽有效。當收到路徑錯誤消息報文（Path Error,，PERR）時,，需要重新尋路，于是釋放現(xiàn)有路徑上節(jié)點所用接口,。若沒有收到PERR則將每次監(jiān)聽時刻同當前源節(jié)點最新發(fā)送數(shù)據(jù)時刻做差值,，如果該差值小于設定閾值，表示源節(jié)點仍在發(fā)送數(shù)據(jù),，否則認為發(fā)送完畢,，tags置零，監(jiān)聽停止,，并發(fā)送CHCLR,，同時等待CLRACK。若源節(jié)點收到CLRACK,，則執(zhí)行接口釋放操作,，否則重發(fā)CHCLR報文；若超過規(guī)定重發(fā)次數(shù)后仍未收到CLRACK,，則直接執(zhí)行接口釋放操作,。

2 RHCA路由算法設計

    本文提出的RHCA路由算法主要針對網(wǎng)絡拓撲不固定和業(yè)務負載多變的場景。算法采用分布式信道分配,，且通信協(xié)調(diào)在路由響應階段完成,。由于該方案基于IEEE 802.11s中混合無線網(wǎng)狀路由協(xié)議HWMP的反應式路由算法改進而來，所以在管理消息幀格式,、路由判據(jù),、PREP和PREQ等管理信息的廣播和接口釋放機制方面，基本沿用自HWMP算法,。

2.1 路由建立過程

    在提出的RHCA路由方案中,，當發(fā)起一項業(yè)務時，源節(jié)點先判斷是否存在到達目的節(jié)點的路由信息,，若已存在則只需要按照路由表向目的節(jié)點單播PREQ,；若沒有則發(fā)起到目的節(jié)點的PREQ廣播請求，各節(jié)點收到請求后,，判斷自身是否為目的節(jié)點,，如果不是則按中間節(jié)點處理方式處理PREQ信息，直到目的節(jié)點收到請求,，進入響應階段,。此后目的節(jié)點首先判斷收到的消息是否為新的PREQ，若不是則直接丟棄,；如果是則按PREQ所尋路徑開始單播回復PREP,?；貜瓦^程中逐跳進行接口綁定和信道分配。當PREP返回至源節(jié)點后,，鏈路的雙向路徑建立完畢,，開始數(shù)據(jù)傳輸。

2.2 路由維護過程

    RHCA算法的路由維護在HWMP基礎上,，加入了對故障因素的考慮,，增加了如下相關操作。

    當發(fā)現(xiàn)故障時,，處于故障上游的節(jié)點向源節(jié)點單播PERR,，源節(jié)點接收到PERR后，執(zhí)行路徑上各節(jié)點接口釋放操作,，當上游各節(jié)點收到CLRACK后開始廣播到目的節(jié)點的PREQ重新尋路,；而故障下游節(jié)點在未收到CHCLR的情況下，若等待超時,，則判定為上游節(jié)點故障,，遂開始執(zhí)行鏈路后續(xù)節(jié)點的接口釋放操作。此方案既保證了路由得到修復,，又完成了故障節(jié)點下游的接口釋放,，避免了故障鏈路占用信道資源。

3 性能仿真分析

    為了模擬網(wǎng)絡多變性,，仿真分別在不同的網(wǎng)絡負載和網(wǎng)絡拓撲下進行,，以便考察提出的RHCA方案的平均吞吐量和時延。同時為了便于比較,，加入了HWMP路由分別搭配集中式信道分配(Centralized Hyacinth Channel Assignment,，C-HYA)和MRMC HWMP(MMHWMP)路由算法結(jié)合節(jié)點優(yōu)先級靜態(tài)信道分配(Nodes Priority Fixed Channel Allocation，NPFCA)兩種方案進行對比,。仿真系統(tǒng)參數(shù)設置如表1所示,。所有結(jié)果均為采用20個隨機種子進行仿真所得平均值，基本符合網(wǎng)絡數(shù)據(jù)統(tǒng)計特性,。

3.1 不同網(wǎng)絡負載下性能分析

    本次仿真采用網(wǎng)絡拓撲如圖1所示,，并設12號節(jié)點為根節(jié)點。

    仿真隨機選取5對節(jié)點建立固定碼率(Constant Bit Rate,，CBR)數(shù)據(jù)傳輸業(yè)務,，CBR流速率為600 kb/s到2 Mb/s不等，每組節(jié)點在仿真時間內(nèi)隨機選擇時間發(fā)起業(yè)務,，并持續(xù)50 s，如果從發(fā)起業(yè)務到仿真結(jié)束不足50 s,，則以仿真結(jié)束時間為準,。全網(wǎng)可用正交信道數(shù)為6，仿真結(jié)果如圖3所示。

    從圖3(a)可以看出,，隨著CBR流速率的增加,，三種算法總吞吐量都呈現(xiàn)遞增趨勢，而提出的RHCA路由算法所得網(wǎng)絡總吞吐量明顯高于前兩者,，尤其在CBR速率為1.6 Mb/s時,，其吞吐量較HWMP和MMHWMP分別高約17.7%和13.5%。

    由圖3(b)可知,，隨著CBR流速率的增加,，三種算法的端到端平均時延也逐步增加，MMHWMP與HWMP方案在CBR流速率為<1.6 Mb/s時平均時延差距不大,，當速率大于1.6 Mb/s時差距逐漸拉大,； RHCA方案的網(wǎng)絡時延顯著優(yōu)于前兩者，尤其在CBR流速率為1.8 Mb/s時,，分別較MMHWMP和HWMP有約0.06 s和0.12 s的優(yōu)勢,。

3.2 動態(tài)拓撲及負載場景下性能分析

    初始網(wǎng)絡如圖1所示。設置節(jié)點移動模型為“Random Way point Mobility Model”^[9],，各節(jié)點速率是在0 m/s～2 m/s中均勻分布的隨機變量,，移動范圍限制在圖中二維空間內(nèi)。網(wǎng)絡中運行兩組CBR數(shù)據(jù)任務,，第一組隨機選取5對節(jié)點建立CBR數(shù)據(jù)業(yè)務,，流速率為500 kb/s，仿真運行5 s后開始發(fā)送數(shù)據(jù)直至結(jié)束,；仿真運行100 s后,，再從余下的節(jié)點中隨機選取5對節(jié)點建立第二組CBR數(shù)據(jù)業(yè)務，流速率仍為500 kb/s,，同樣持續(xù)至仿真結(jié)束,。仿真時間總共200 s。全網(wǎng)可用正交信道數(shù)為6,，當仿真開始20 s后,，開啟移動模型。同時還增加了較為靈活的HWMP路由+公共信道分配（Common channel assignment,，CCA）組合,，以供參考。仿真結(jié)果如圖4所示,。

    從圖中可以看出,，在仿真前20 s范圍內(nèi)，四種方案都處于穩(wěn)態(tài),，此時本文提出的RHCA方案性能最優(yōu),；當仿真開始20 s后,，移動模型開啟，網(wǎng)絡拓撲開始變化,，部分鏈路通信中斷,，使得在40 s～60 s期間，所有方案的吞吐量均有較大幅度下降,；而在60 s～100 s之間,，隨著網(wǎng)絡拓撲持續(xù)變化，部分節(jié)點重新建立連接,，使得四種方案吞吐量有不同程度回升,，其中以RHCA回升最為明顯，最高時甚至超過HWMP+CCA方案近一倍,；仿真100 s后,，由于引入了5條新數(shù)據(jù)流，網(wǎng)絡整體吞吐量有所上升,，同樣以RHCA方案升幅最大,，其性能領先HWMP-R+CCA約70%。

4 結(jié)論

    本文主要針對MRMC無線Mesh網(wǎng)絡中,，網(wǎng)絡負載可變以及網(wǎng)絡節(jié)點可移動的動態(tài)場景,，在HWMP反應式路由算法基礎上，提出了一種融合信道分配和路由選擇的RHCA算法,。仿真結(jié)果表明,，此算法無論在網(wǎng)絡吞吐量還是端到端平均時延方面均有顯著優(yōu)勢。同時仿真結(jié)果還驗證了在節(jié)點可移動的無線Mesh網(wǎng)絡中,，RHCA較其他三種方案能獲得更高的吞吐量,，同時具有更好的穩(wěn)健性。

參考文獻

[1] PENG Y,，YU Y,，GUO L，et al.An efficient joint channel assignment and QoS routing protocol for IEEE 802.11 multi-radio multi-channel wireless Mesh networks[J].Journal of Network and Computer Applications,，2013,，36(2)：843-857.

[2] Zhang Yang，Luo Jijun,，Hu Honglin.Wireless Mesh networking：architectures,，protocols and standards[M].New York：Auerbach Publications，2006.

[3] PERKINS C E,，WATSON T J.Highly dynamic destination sequenced distance vector routing(DSDV) for mobile computers[C].ACM SIGCOMM’94 Conference on Communications Architectures,，1994：234-244.

[4] PERKINS C E，ROYER E M.Ad hoc on demand distance vector(AODV) routing[C].IEEE Workshop on Mobile Computing Systems and Applications,，WMCSA(2),，1999：90-100.

[5] RADHAKRISHNAN S,，RAO N S,，RACHERLA G,，et al.DST-A routing protocol for ad hoc networks using distributed spanning trees[C].IEEE Wireless Communications and Networking Conference，WCNC,，1999：1543-1547.

[6] AVALLONE S,，AKYILDIZ I F，VENTRE G.A channel and rate assignment algorithm and a layer-2.5 forwarding paradigm for multi-radio wireless Mesh networks[J].IEEE/ACM Transactions on Networking,，2009,，17(1)：267-280.

[7] RANIWALA A，CHIUEH T.Architecture and algorithms for an IEEE 802.11-based multi-channel wireless Mesh network[C].Annual Joint Conference of the IEEE Computer and Communications Societies,，INFOCOM(24),，2005：2223-2234.

[8] XU K X，GERLA M,，BAE S.How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks[C].Global Telecommunications Conference,，2002(1)：72-76.

[9] VINOTHINI M，GANDHIMATHI K.Comparison of L-PEDAP routing protocol with random way point mobility model in mobile sensor networks[C].IEEE-International Conference On Advances In Engineering,，Science And Management,，ICAESM(1)，2012：735-740.