文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.2015.07.023
中文引用格式： 鐘朗，李廣軍，楊學(xué)敏，等. 無(wú)線Mesh網(wǎng)絡(luò)中一種分布式路由方案[J].電子技術(shù)應(yīng)用，2015，41(7)：81-84.
英文引用格式： Zhong Lang，Li Guangjun，Yang Xuemin，et al. A distributed routing scheme in wireless Mesh networks[J].Application of Electronic Technique，2015，41(7)：81-84.
0 引言
在無(wú)線Mesh網(wǎng)絡(luò)中，信道分配和路由協(xié)議是較為關(guān)鍵的問(wèn)題，且二者聯(lián)系緊密。如何協(xié)調(diào)其關(guān)系以更好地利用網(wǎng)絡(luò)資源、提升網(wǎng)絡(luò)性能是當(dāng)前研究熱點(diǎn)之一。對(duì)于信道分配的分類，按照網(wǎng)絡(luò)中Mesh節(jié)點(diǎn)（Mesh Point，MP）射頻接口數(shù)量的不同，可分為單射頻信道分配和多射頻信道分配。由于后者能帶來(lái)更大的網(wǎng)絡(luò)吞吐量，因此應(yīng)用更為廣泛[1]。此外，若根據(jù)信道更新頻繁程度，又可分為靜態(tài)信道分配、動(dòng)態(tài)信道分配和混合信道分配[2]。而對(duì)于路由選擇，按照路由建立和業(yè)務(wù)請(qǐng)求之間的關(guān)系，可以分為先驗(yàn)式路由協(xié)議[3]、反應(yīng)式路由協(xié)議[4]和混合式路由協(xié)議[5]。
傳統(tǒng)的無(wú)線Mesh網(wǎng)絡(luò)中，信道分配和路由選擇是分開(kāi)進(jìn)行的，一般先進(jìn)行信道分配，再執(zhí)行路由選擇。當(dāng)網(wǎng)絡(luò)拓?fù)湟约皹I(yè)務(wù)流量相對(duì)穩(wěn)定時(shí)，該方式可以充分地利用網(wǎng)絡(luò)資源。然而一旦網(wǎng)絡(luò)拓?fù)浠蜴溌坟?fù)載發(fā)生變動(dòng)，以上方法無(wú)法根據(jù)實(shí)時(shí)信息調(diào)整資源配置，致使資源利用率大幅降低，甚至出現(xiàn)節(jié)點(diǎn)孤立，影響正常的數(shù)據(jù)傳輸。
針對(duì)上述問(wèn)題，近年來(lái)出現(xiàn)了諸多關(guān)于融合信道分配和路由選擇的研究，大致可分為集中式[6]和分布式[7]兩類，其中分布式路由算法不需要中央處理節(jié)點(diǎn)，且可避免因單個(gè)節(jié)點(diǎn)失效導(dǎo)致整個(gè)網(wǎng)絡(luò)崩潰的危險(xiǎn)，因此得到更為廣泛的研究和應(yīng)用。本文主要針對(duì)多射頻多信道(Multi-Radio Multi-Channel，MRMC)無(wú)線Mesh網(wǎng)絡(luò)中網(wǎng)絡(luò)負(fù)載及節(jié)點(diǎn)位置實(shí)時(shí)變化等實(shí)際場(chǎng)景，在混合無(wú)線網(wǎng)狀路由協(xié)議（Hybrid Wireless Mesh Routing Protocol，HWMP）反應(yīng)式路由基礎(chǔ)上，設(shè)計(jì)了一種新的混合信道分配的分布式路由算法（Routing based on Hybrid Channel Assignment，RHCA）。
1 信道分配方案
由于本文提出的RHCA方案基于動(dòng)態(tài)網(wǎng)絡(luò)設(shè)計(jì)，因此信道分配策略應(yīng)采用動(dòng)態(tài)分配或混合分配。考慮到混合分配方案具有更好的網(wǎng)絡(luò)連通性，故選擇后者。
1.1 系統(tǒng)模型
本文無(wú)線Mesh網(wǎng)絡(luò)模型如圖1所示，采用網(wǎng)格型網(wǎng)絡(luò)拓?fù)洌苍O(shè)置32個(gè)節(jié)點(diǎn)，相鄰節(jié)點(diǎn)間距170 m。且本文的信道分配過(guò)程只考慮如何減小鏈路干擾，達(dá)到以數(shù)據(jù)流為單位的鏈路干擾最小化信道分配。其余諸如網(wǎng)絡(luò)負(fù)載等因素的影響則在路由選擇時(shí)考慮。干擾模型方面采用文獻(xiàn)[8]中的協(xié)議干擾模型，如圖2所示，當(dāng)鏈路ei、ej節(jié)點(diǎn)間跳數(shù)不少于兩跳時(shí)，才認(rèn)為二者無(wú)相互干擾。雖然該模型是一個(gè)NP問(wèn)題，但其信道分配模型融合于路由算法中，具體分配方式將在后文中詳述。
1.2 接口分配策略和通信協(xié)調(diào)機(jī)制
在接口分配上，所有節(jié)點(diǎn)均固定使用一個(gè)無(wú)線射頻接口搭配標(biāo)號(hào)為1的信道作為固定接口，用于傳遞網(wǎng)絡(luò)管理消息，當(dāng)網(wǎng)絡(luò)負(fù)載較重時(shí)亦可傳送數(shù)據(jù)。其余接口全部用于數(shù)據(jù)傳輸，稱為動(dòng)態(tài)接口(Dynamic Radio Interface，DRI)，其分配信道在傳輸過(guò)程中可實(shí)時(shí)切換。
另外，本文的通信協(xié)調(diào)機(jī)制主要通過(guò)分析網(wǎng)絡(luò)中的相鄰節(jié)點(diǎn)DRI信道分配、路徑請(qǐng)求（Path Request，PREQ）消息幀前兩跳DRI信息以及各個(gè)節(jié)點(diǎn)Metric信息等，得到與下一跳鏈路干擾最小的信道。該機(jī)制在路由過(guò)程中實(shí)施。當(dāng)源節(jié)點(diǎn)發(fā)送PREQ，尋得最優(yōu)路徑之后，目的節(jié)點(diǎn)在回復(fù)路徑響應(yīng)（Path Reply，PREP）消息過(guò)程中逐一節(jié)點(diǎn)綁定通信接口，并分配信道。
1.3 接口釋放機(jī)制
本文對(duì)源節(jié)點(diǎn)的接口釋放機(jī)制進(jìn)行了如下設(shè)計(jì)。在開(kāi)始發(fā)起數(shù)據(jù)業(yè)務(wù)后，數(shù)據(jù)流監(jiān)聽(tīng)模塊隨即啟動(dòng)，并設(shè)置監(jiān)聽(tīng)標(biāo)志位tags為1，表示監(jiān)聽(tīng)有效。當(dāng)收到路徑錯(cuò)誤消息報(bào)文（Path Error，PERR）時(shí)，需要重新尋路，于是釋放現(xiàn)有路徑上節(jié)點(diǎn)所用接口。若沒(méi)有收到PERR則將每次監(jiān)聽(tīng)時(shí)刻同當(dāng)前源節(jié)點(diǎn)最新發(fā)送數(shù)據(jù)時(shí)刻做差值，如果該差值小于設(shè)定閾值，表示源節(jié)點(diǎn)仍在發(fā)送數(shù)據(jù)，否則認(rèn)為發(fā)送完畢，tags置零，監(jiān)聽(tīng)停止，并發(fā)送CHCLR，同時(shí)等待CLRACK。若源節(jié)點(diǎn)收到CLRACK，則執(zhí)行接口釋放操作，否則重發(fā)CHCLR報(bào)文；若超過(guò)規(guī)定重發(fā)次數(shù)后仍未收到CLRACK，則直接執(zhí)行接口釋放操作。
2 RHCA路由算法設(shè)計(jì)
本文提出的RHCA路由算法主要針對(duì)網(wǎng)絡(luò)拓?fù)洳还潭ê蜆I(yè)務(wù)負(fù)載多變的場(chǎng)景。算法采用分布式信道分配，且通信協(xié)調(diào)在路由響應(yīng)階段完成。由于該方案基于IEEE 802.11s中混合無(wú)線網(wǎng)狀路由協(xié)議HWMP的反應(yīng)式路由算法改進(jìn)而來(lái)，所以在管理消息幀格式、路由判據(jù)、PREP和PREQ等管理信息的廣播和接口釋放機(jī)制方面，基本沿用自HWMP算法。
2.1 路由建立過(guò)程
在提出的RHCA路由方案中，當(dāng)發(fā)起一項(xiàng)業(yè)務(wù)時(shí)，源節(jié)點(diǎn)先判斷是否存在到達(dá)目的節(jié)點(diǎn)的路由信息，若已存在則只需要按照路由表向目的節(jié)點(diǎn)單播PREQ；若沒(méi)有則發(fā)起到目的節(jié)點(diǎn)的PREQ廣播請(qǐng)求，各節(jié)點(diǎn)收到請(qǐng)求后，判斷自身是否為目的節(jié)點(diǎn)，如果不是則按中間節(jié)點(diǎn)處理方式處理PREQ信息，直到目的節(jié)點(diǎn)收到請(qǐng)求，進(jìn)入響應(yīng)階段。此后目的節(jié)點(diǎn)首先判斷收到的消息是否為新的PREQ，若不是則直接丟棄；如果是則按PREQ所尋路徑開(kāi)始單播回復(fù)PREP。回復(fù)過(guò)程中逐跳進(jìn)行接口綁定和信道分配。當(dāng)PREP返回至源節(jié)點(diǎn)后，鏈路的雙向路徑建立完畢，開(kāi)始數(shù)據(jù)傳輸。
2.2 路由維護(hù)過(guò)程
RHCA算法的路由維護(hù)在HWMP基礎(chǔ)上，加入了對(duì)故障因素的考慮，增加了如下相關(guān)操作。
當(dāng)發(fā)現(xiàn)故障時(shí)，處于故障上游的節(jié)點(diǎn)向源節(jié)點(diǎn)單播PERR，源節(jié)點(diǎn)接收到PERR后，執(zhí)行路徑上各節(jié)點(diǎn)接口釋放操作，當(dāng)上游各節(jié)點(diǎn)收到CLRACK后開(kāi)始廣播到目的節(jié)點(diǎn)的PREQ重新尋路；而故障下游節(jié)點(diǎn)在未收到CHCLR的情況下，若等待超時(shí)，則判定為上游節(jié)點(diǎn)故障，遂開(kāi)始執(zhí)行鏈路后續(xù)節(jié)點(diǎn)的接口釋放操作。此方案既保證了路由得到修復(fù)，又完成了故障節(jié)點(diǎn)下游的接口釋放，避免了故障鏈路占用信道資源。
3 性能仿真分析
為了模擬網(wǎng)絡(luò)多變性，仿真分別在不同的網(wǎng)絡(luò)負(fù)載和網(wǎng)絡(luò)拓?fù)湎逻M(jìn)行，以便考察提出的RHCA方案的平均吞吐量和時(shí)延。同時(shí)為了便于比較，加入了HWMP路由分別搭配集中式信道分配(Centralized Hyacinth Channel Assignment，C-HYA)和MRMC HWMP(MMHWMP)路由算法結(jié)合節(jié)點(diǎn)優(yōu)先級(jí)靜態(tài)信道分配(Nodes Priority Fixed Channel Allocation，NPFCA)兩種方案進(jìn)行對(duì)比。仿真系統(tǒng)參數(shù)設(shè)置如表1所示。所有結(jié)果均為采用20個(gè)隨機(jī)種子進(jìn)行仿真所得平均值，基本符合網(wǎng)絡(luò)數(shù)據(jù)統(tǒng)計(jì)特性。
3.1 不同網(wǎng)絡(luò)負(fù)載下性能分析
本次仿真采用網(wǎng)絡(luò)拓?fù)淙鐖D1所示，并設(shè)12號(hào)節(jié)點(diǎn)為根節(jié)點(diǎn)。
仿真隨機(jī)選取5對(duì)節(jié)點(diǎn)建立固定碼率(Constant Bit Rate，CBR)數(shù)據(jù)傳輸業(yè)務(wù)，CBR流速率為600 kb/s到2 Mb/s不等，每組節(jié)點(diǎn)在仿真時(shí)間內(nèi)隨機(jī)選擇時(shí)間發(fā)起業(yè)務(wù)，并持續(xù)50 s，如果從發(fā)起業(yè)務(wù)到仿真結(jié)束不足50 s，則以仿真結(jié)束時(shí)間為準(zhǔn)。全網(wǎng)可用正交信道數(shù)為6，仿真結(jié)果如圖3所示。
從圖3(a)可以看出，隨著CBR流速率的增加，三種算法總吞吐量都呈現(xiàn)遞增趨勢(shì)，而提出的RHCA路由算法所得網(wǎng)絡(luò)總吞吐量明顯高于前兩者，尤其在CBR速率為1.6 Mb/s時(shí)，其吞吐量較HWMP和MMHWMP分別高約17.7%和13.5%。
由圖3(b)可知，隨著CBR流速率的增加，三種算法的端到端平均時(shí)延也逐步增加，MMHWMP與HWMP方案在CBR流速率為<1.6 Mb/s時(shí)平均時(shí)延差距不大，當(dāng)速率大于1.6 Mb/s時(shí)差距逐漸拉大； RHCA方案的網(wǎng)絡(luò)時(shí)延顯著優(yōu)于前兩者，尤其在CBR流速率為1.8 Mb/s時(shí)，分別較MMHWMP和HWMP有約0.06 s和0.12 s的優(yōu)勢(shì)。
3.2 動(dòng)態(tài)拓?fù)浼柏?fù)載場(chǎng)景下性能分析
初始網(wǎng)絡(luò)如圖1所示。設(shè)置節(jié)點(diǎn)移動(dòng)模型為“Random Way point Mobility Model”[9]，各節(jié)點(diǎn)速率是在0 m/s～2 m/s中均勻分布的隨機(jī)變量，移動(dòng)范圍限制在圖中二維空間內(nèi)。網(wǎng)絡(luò)中運(yùn)行兩組CBR數(shù)據(jù)任務(wù)，第一組隨機(jī)選取5對(duì)節(jié)點(diǎn)建立CBR數(shù)據(jù)業(yè)務(wù)，流速率為500 kb/s，仿真運(yùn)行5 s后開(kāi)始發(fā)送數(shù)據(jù)直至結(jié)束；仿真運(yùn)行100 s后，再?gòu)挠嘞碌墓?jié)點(diǎn)中隨機(jī)選取5對(duì)節(jié)點(diǎn)建立第二組CBR數(shù)據(jù)業(yè)務(wù)，流速率仍為500 kb/s，同樣持續(xù)至仿真結(jié)束。仿真時(shí)間總共200 s。全網(wǎng)可用正交信道數(shù)為6，當(dāng)仿真開(kāi)始20 s后，開(kāi)啟移動(dòng)模型。同時(shí)還增加了較為靈活的HWMP路由+公共信道分配（Common channel assignment，CCA）組合，以供參考。仿真結(jié)果如圖4所示。
從圖中可以看出，在仿真前20 s范圍內(nèi)，四種方案都處于穩(wěn)態(tài)，此時(shí)本文提出的RHCA方案性能最優(yōu)；當(dāng)仿真開(kāi)始20 s后，移動(dòng)模型開(kāi)啟，網(wǎng)絡(luò)拓?fù)溟_(kāi)始變化，部分鏈路通信中斷，使得在40 s～60 s期間，所有方案的吞吐量均有較大幅度下降；而在60 s～100 s之間，隨著網(wǎng)絡(luò)拓?fù)涑掷m(xù)變化，部分節(jié)點(diǎn)重新建立連接，使得四種方案吞吐量有不同程度回升，其中以RHCA回升最為明顯，最高時(shí)甚至超過(guò)HWMP+CCA方案近一倍；仿真100 s后，由于引入了5條新數(shù)據(jù)流，網(wǎng)絡(luò)整體吞吐量有所上升，同樣以RHCA方案升幅最大，其性能領(lǐng)先HWMP-R+CCA約70%。
4 結(jié)論
本文主要針對(duì)MRMC無(wú)線Mesh網(wǎng)絡(luò)中，網(wǎng)絡(luò)負(fù)載可變以及網(wǎng)絡(luò)節(jié)點(diǎn)可移動(dòng)的動(dòng)態(tài)場(chǎng)景，在HWMP反應(yīng)式路由算法基礎(chǔ)上，提出了一種融合信道分配和路由選擇的RHCA算法。仿真結(jié)果表明，此算法無(wú)論在網(wǎng)絡(luò)吞吐量還是端到端平均時(shí)延方面均有顯著優(yōu)勢(shì)。同時(shí)仿真結(jié)果還驗(yàn)證了在節(jié)點(diǎn)可移動(dòng)的無(wú)線Mesh網(wǎng)絡(luò)中，RHCA較其他三種方案能獲得更高的吞吐量，同時(shí)具有更好的穩(wěn)健性。
參考文獻(xià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.