廖龍龍

摘要：無(wú)線Mesh網(wǎng)絡(luò)是廣播網(wǎng)絡(luò)的一種特殊方式，它結(jié)合了WLAN網(wǎng)絡(luò)和ad hoc網(wǎng)絡(luò)的優(yōu)點(diǎn)，網(wǎng)絡(luò)通過(guò)跳躍通信和相對(duì)降低基礎(chǔ)設(shè)施在電線和硬件方面的成本來(lái)提供與因特網(wǎng)最后一英里的連接。信道分配方案是提高無(wú)線Mesh網(wǎng)絡(luò)容量的主要途徑。隨著用戶數(shù)量的增加，網(wǎng)狀網(wǎng)絡(luò)對(duì)信道資源的公平利用一直是一個(gè)挑戰(zhàn)。合理利用多信道和節(jié)點(diǎn)的多接口，不僅增加了網(wǎng)絡(luò)的總吞吐量和可擴(kuò)展性，而且為信道分配方法帶來(lái)了新的曙光。針對(duì)現(xiàn)有信道分配方案進(jìn)行了詳細(xì)討論。

關(guān)鍵詞：無(wú)線Mesh網(wǎng)絡(luò)；多接口；多信道；信道分配；網(wǎng)絡(luò)容量

中圖分類(lèi)號(hào)：TN915.01 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）27-0024-04

Abstract： The wireless Mesh network is a special way of broadcasting networks that combines the advantages of WLAN networks and ad hoc networks that provide connectivity to the last mile of the Internet by jumping communications and relatively reducing the cost of infrastructure in terms of wire and hardware. Channel allocation scheme is the main way to improve the capacity of wireless Mesh network. With the increase in the number of users， the mesh network on the fair use of channel resources has been a challenge. Reasonable use of multi-channel and multi-interface nodes， not only increased the total network throughput and scalability， but also for the channel allocation method has brought a new shine. The existing channel allocation scheme is discussed in detail.

Key words： wireless mesh networks；multi-radio；multi-Channel；channel allocation；network capacity

1 概述

無(wú)線Mesh網(wǎng)絡(luò)（WMN）是一種重要的技術(shù)，涵蓋了幾乎各行各業(yè)，具有諸如災(zāi)難恢復(fù)服務(wù)，交叉點(diǎn)安全攝像機(jī)，連接多個(gè)熱點(diǎn)，校園網(wǎng)絡(luò)，戰(zhàn)場(chǎng)等孤立的地區(qū)[1-2]。WMN是提供最后一英里連接的經(jīng)典有線骨干網(wǎng)技術(shù)的架構(gòu)轉(zhuǎn)變[3]，它具有易于部署、可靠性、可擴(kuò)展性、可用性、良好吞吐量和低成本的特性。

無(wú)線Mesh網(wǎng)絡(luò)具有多跳、自組織和自我修復(fù)等特性，其中節(jié)點(diǎn)互連形成網(wǎng)格。雖然只有少數(shù)節(jié)點(diǎn)通過(guò)最后一公里網(wǎng)關(guān)連接到互聯(lián)網(wǎng)，但是這種業(yè)務(wù)形式和其他類(lèi)似的業(yè)務(wù)可以擴(kuò)展到整個(gè)網(wǎng)絡(luò)?？梢园哑湔J(rèn)為是融合網(wǎng)絡(luò)的一種類(lèi)型，其結(jié)合了有線和無(wú)線網(wǎng)絡(luò)部署的技術(shù)，是臨時(shí)和基礎(chǔ)設(shè)施模式網(wǎng)絡(luò)。

圖1為典型的無(wú)線Mesh網(wǎng)絡(luò)架構(gòu)，主要由Mesh客戶端、Mesh路由器和網(wǎng)關(guān)組成?？蛻舳耸庆o態(tài)/移動(dòng)節(jié)點(diǎn)，如計(jì)算機(jī)和筆記本電腦，也可以充當(dāng)路由器，將其他客戶端的數(shù)據(jù)傳送到網(wǎng)關(guān)或從網(wǎng)關(guān)傳輸。路由器作為客戶端和網(wǎng)關(guān)之間的中介，網(wǎng)關(guān)具有和外部互聯(lián)網(wǎng)相連的功能。與經(jīng)典路由器相比，網(wǎng)狀路由器只需要較低的傳輸功率，因?yàn)樗鼈冎灰獙?shù)據(jù)包轉(zhuǎn)發(fā)到臨近的路由器即可。

在傳統(tǒng)的單頻單信道無(wú)線Mesh網(wǎng)絡(luò)中，因?yàn)闊o(wú)線信道的傳輸特性，在節(jié)點(diǎn)的干擾范圍內(nèi)同信道的鏈路之間會(huì)相互干擾，不能同時(shí)進(jìn)行數(shù)據(jù)的傳輸，因此會(huì)降低網(wǎng)絡(luò)的容量。然而在多射頻環(huán)境下的WMN，信道分配的目的是確保良好的網(wǎng)絡(luò)連接，同時(shí)有效地提高信道利用率。雖然不同的物理層標(biāo)準(zhǔn)如802.11a/b/g/n提供了多個(gè)正交可用信道，但是網(wǎng)絡(luò)中存在著節(jié)點(diǎn)的接口約束，流量不均衡等各種不確定因素，所以在考慮網(wǎng)絡(luò)場(chǎng)景的同時(shí)，如何為網(wǎng)絡(luò)中的鏈路分配信道從而最大化網(wǎng)絡(luò)容量一直是研究信道分配算法的目標(biāo)。無(wú)線Mesh網(wǎng)絡(luò)信道分配問(wèn)題類(lèi)似于圖著色問(wèn)題，已被證明是一個(gè)NP-hard問(wèn)題[4]。因此，信道分配機(jī)制應(yīng)采用啟發(fā)式算法來(lái)完成信道分配。根據(jù)節(jié)點(diǎn)的射頻接口上信道的切換頻率可以將信道分配方案主要?jiǎng)澐譃?種類(lèi)型[5]：靜態(tài)信道分配（Fixed Channel Assignment）、動(dòng)態(tài)信道分配（Dynamic Channel Assignment）和混合信道分配（Hybird Channel Assignment）。

2 靜態(tài)信道分配

在靜態(tài)信道分配里，每個(gè)Mesh路由器中的每個(gè)接口被長(zhǎng)時(shí)間固定的分配一個(gè)信道。 靜態(tài)信道分配的目標(biāo)是最大化整體網(wǎng)絡(luò)性能。大多數(shù)工作僅在信道分配中考慮正交信道。不同正交信道上的無(wú)線鏈路可以始終在沒(méi)有干擾的情況下同時(shí)工作。

文獻(xiàn)[6]中提出了CCA信道分配方案，該方案將Mesh路由器分列成簇，在CCA中信道分配取決于簇中節(jié)點(diǎn)的數(shù)量，信道的重新分配取決于簇集間的距離。網(wǎng)絡(luò)中至少應(yīng)該存在兩個(gè)簇。C表示網(wǎng)絡(luò)中所有簇的集合：[C={C1，C2，C3，…，Cn}]。

網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)最多的節(jié)點(diǎn)被選為簇頭節(jié)點(diǎn)，它根據(jù)本簇集中的拓?fù)湫畔?lái)執(zhí)行CCA信道分配方案。CCA信道分配主要為三步：

（1） 初始信道的劃分endprint

（2） 鄰居簇集的選擇

（3） 信道的重分配

為了讓兩個(gè)鄰域簇集合獲得不相交的信道集，網(wǎng)絡(luò)中的所有可用信道均勻分布在簇集中，剛開(kāi)始，簇頭節(jié)點(diǎn)為該簇中的所有節(jié)點(diǎn)分配單個(gè)公共信道，而且邊界節(jié)點(diǎn)也采用該信道來(lái)和鄰域簇進(jìn)行通信。然后簇頭節(jié)點(diǎn)再將剩余的信道分配給為分配信道的節(jié)點(diǎn)。

CCA信道分配的主要局限在于信道沒(méi)有充分的被利用，而且該方案沒(méi)有考慮每條鏈路的負(fù)載，這將導(dǎo)致鏈路之間的干擾。

文獻(xiàn)[7]中提出一種針對(duì)網(wǎng)絡(luò)中擁塞和傳輸干擾算法，該算法是基于節(jié)點(diǎn)優(yōu)先級(jí)策略的靜態(tài)信道分配（NPFCA）方案，在該方案中將網(wǎng)絡(luò)中的所有節(jié)點(diǎn)按照距離網(wǎng)關(guān)節(jié)點(diǎn)的跳數(shù)進(jìn)行分級(jí)。根據(jù)節(jié)點(diǎn)優(yōu)先級(jí)和其鄰居節(jié)點(diǎn)數(shù)，通過(guò)計(jì)算鏈路兩端節(jié)點(diǎn)各自鄰居節(jié)點(diǎn)數(shù)與節(jié)點(diǎn)優(yōu)先級(jí)之比的和得到對(duì)應(yīng)鏈路的負(fù)載權(quán)重，然后根據(jù)鏈路的負(fù)載權(quán)重來(lái)給鏈路分配相應(yīng)的信道。由于信道分配問(wèn)題是一個(gè)NP問(wèn)題，所以該方案采用了離散粒子群優(yōu)化算法來(lái)求解。該方案能夠在一定程度上減少網(wǎng)絡(luò)中的干擾，從而有效提高網(wǎng)絡(luò)中的容量。

文獻(xiàn)[8]中提出了一種差異信道分配算法（VCA），此算法給不同節(jié)點(diǎn)的無(wú)線射頻接口分配不同的信道，減少了網(wǎng)絡(luò)中的同信道干擾，因?yàn)樗薪涌诘男诺朗枪潭ǖ?，所以其降低了網(wǎng)絡(luò)的連通性。

文獻(xiàn)[9]給出了一種集中式信道分配算法（C-HYA），該算法認(rèn)為所有網(wǎng)絡(luò)中的流量來(lái)于互聯(lián)網(wǎng)，假設(shè)已知網(wǎng)絡(luò)流量負(fù)載，以此計(jì)算出每條鏈路的流量負(fù)載，按照假設(shè)的節(jié)點(diǎn)優(yōu)先級(jí)從高到低訪問(wèn)節(jié)點(diǎn)，按貪婪的方法給節(jié)點(diǎn)分配信道，也就是說(shuō)具有優(yōu)先級(jí)高的節(jié)點(diǎn)分配性能好的信道。算法以Hyacinth架構(gòu)為基礎(chǔ)，認(rèn)為所有網(wǎng)絡(luò)中的流量都是流向互聯(lián)網(wǎng)或來(lái)自互聯(lián)網(wǎng)，節(jié)點(diǎn)的流量負(fù)載已知，C-HYA算法通過(guò)公式（1）計(jì)算網(wǎng)絡(luò)中每條鏈路的流量負(fù)載之和，估計(jì)每條虛擬鏈路的預(yù)期流量負(fù)載。

其中s表示源節(jié)點(diǎn)，d表示目的節(jié)點(diǎn)，[Ρ（s，d）]表示節(jié)點(diǎn)對(duì)[（s，d）]之間可以進(jìn)行通信的鏈路數(shù)，[Ρι（s，d）]表示節(jié)點(diǎn)對(duì)[（s，d）]之間能夠進(jìn)行通信的路徑中經(jīng)過(guò)鏈路l的路徑數(shù)量，[Β（s，d）]表示節(jié)點(diǎn)對(duì)（s，d）之間的評(píng)估負(fù)載，[Γι]表示鏈路L上的預(yù)期流量負(fù)載。通過(guò)比較鏈路預(yù)估流量負(fù)載為對(duì)應(yīng)的鏈路選取信道，為預(yù)估鏈路流量負(fù)載重的選取帶寬比較大的信道，預(yù)期流量負(fù)載輕的鏈路選取帶寬比較小的信道。C-HYA算法輸入?yún)?shù)是初始預(yù)估鏈路流量的負(fù)載，然后通過(guò)使用多次迭代的方式來(lái)進(jìn)行信道分配方案的計(jì)算，直到分配給網(wǎng)絡(luò)中的所有鏈路帶寬都滿足預(yù)估的流量負(fù)載需求。該信道分配算法雖然降低了網(wǎng)絡(luò)中的鏈路干擾，提升了網(wǎng)絡(luò)的容量，但其易發(fā)生波紋效應(yīng)現(xiàn)象，即當(dāng)網(wǎng)絡(luò)中的某條已分配信道的鏈路發(fā)生改變時(shí)，會(huì)對(duì)其他已分配了信道的鏈路產(chǎn)生影響，導(dǎo)致剩余的鏈路為了保證網(wǎng)絡(luò)的連通也需要跟著改變其所分配的信道來(lái)避免網(wǎng)絡(luò)分割現(xiàn)象。

在文獻(xiàn)[10]中，作者提出了一種線性規(guī)劃的方法，將優(yōu)化網(wǎng)絡(luò)中的鏈路干擾作為最終目標(biāo)，以此來(lái)減少整個(gè)網(wǎng)絡(luò)中的干擾權(quán)重。

從此可以看出，靜態(tài)信道分配方案主要是通過(guò)理論分析和系統(tǒng)建模的方法，給拓?fù)浣Y(jié)構(gòu)穩(wěn)定和固定業(yè)務(wù)模式的WMN提供解決方案。靜態(tài)信道分配方案在WMN部署與業(yè)務(wù)分配等方面有著重要的參考意義。

3 動(dòng)態(tài)信道分配

動(dòng)態(tài)信道分配方案與靜態(tài)信道方案的最大區(qū)別是，節(jié)點(diǎn)的無(wú)線射頻接口可以動(dòng)態(tài)的從一條信道上切換到另外一條信道上，而不是固定的使用一條信道。動(dòng)態(tài)信道分配面臨兩個(gè)挑戰(zhàn)。（1）目前的文獻(xiàn)顯示，一個(gè)信道切換到另一個(gè)信道的切換延遲是不能忽略的。對(duì)于相同頻帶內(nèi)的頻道切換（2.4GHz上的802.11b/g或5GHz上的802.11a），延遲顯示為[11]中的幾毫秒到幾毫秒。對(duì)于不同頻段的信道切換，延遲預(yù)計(jì)會(huì)大得多[12]?，F(xiàn)在主流的基于IEEE802.11的商業(yè)硬件很難滿足這種要求[13]。而且，大多數(shù)動(dòng)態(tài)信道分配方案需要對(duì)MAC層進(jìn)行特定的修改，這對(duì)于IEEE802.11硬件是種巨大的挑戰(zhàn)。（2）接口之間需要協(xié)調(diào)機(jī)制。當(dāng)兩個(gè)接口想要相互通信時(shí)，它們必須切換到同一個(gè)通道。因此，需要一些同步或控制協(xié)議來(lái)使得接口能夠協(xié)商公共信道并同時(shí)切換到信道。

為了充分利用多信道的優(yōu)點(diǎn)，在文獻(xiàn)[14]定義了一種新的MAC協(xié)議MMAC（Multi-channel MAC），但是該方法存在著切換時(shí)間長(zhǎng)、時(shí)間同步比較復(fù)雜，而且其引入了更多的暴露終端。

D-HYA算法[15]是按照網(wǎng)絡(luò)中流量負(fù)載的變化，已實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡、降低網(wǎng)絡(luò)中的干擾鏈路，從而提升網(wǎng)絡(luò)的整體容量的一種分布式動(dòng)態(tài)信道方案。在算法中以網(wǎng)關(guān)節(jié)點(diǎn)作為根節(jié)點(diǎn)構(gòu)建網(wǎng)絡(luò)的樹(shù)形結(jié)構(gòu)，給每個(gè)節(jié)點(diǎn)都劃分優(yōu)先級(jí)，越接近網(wǎng)關(guān)的節(jié)點(diǎn)優(yōu)先級(jí)越高。

DCA算法是一種經(jīng)典的動(dòng)態(tài)信道分配算法[16]，算法通過(guò)給每個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)分配一個(gè)控制信道和多個(gè)數(shù)據(jù)信道，其中所有的信道都具有相同的帶寬?？刂菩诺乐饕鉀Q信道沖突問(wèn)題，數(shù)據(jù)信道用來(lái)進(jìn)行數(shù)據(jù)的傳輸。每個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)都配有半雙工收發(fā)器兩個(gè)，一個(gè)控制收發(fā)器和一個(gè)數(shù)據(jù)收發(fā)器。網(wǎng)絡(luò)中節(jié)點(diǎn)間的信息交互和數(shù)據(jù)信道接入的權(quán)限通過(guò)控制收發(fā)器控制信道來(lái)完成，數(shù)據(jù)的傳輸主要是通過(guò)數(shù)據(jù)收發(fā)器動(dòng)態(tài)切換數(shù)據(jù)信道完成。

在DCA算法中，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都需要維護(hù)CUL表和FCL表的信息。CUL是用來(lái)記錄信道使用信息的表，在表中每條CUL[i]信息記錄了i的鄰居節(jié)點(diǎn)信息與它自己的信息，里面有三個(gè)域，CUL[i].host表示節(jié)點(diǎn)i鄰居節(jié)點(diǎn)的編號(hào)，CUL[i].ch表示域CUL[i].host中節(jié)點(diǎn)使用的信道編號(hào)，CUL[i].rel_time表示域CUL[i].ch中信道釋放的時(shí)間。通過(guò)實(shí)時(shí)動(dòng)態(tài)的更新節(jié)點(diǎn)的CUL表信息，而空閑信道表FCL的信息可以通過(guò)CUL表信息計(jì)算出來(lái)。

DCA算法的主要步驟為：若網(wǎng)絡(luò)中的節(jié)點(diǎn)A想要與另一節(jié)點(diǎn)B進(jìn)行通信，首先節(jié)點(diǎn)A需要向節(jié)點(diǎn)B發(fā)送請(qǐng)求服務(wù)消息，該消息中包含了節(jié)點(diǎn)A的FCL表信息。其次節(jié)點(diǎn)B在收到節(jié)點(diǎn)A請(qǐng)求的信息后，通過(guò)比較自己的FCL表信息和請(qǐng)求信息中的FCL表信息，找到空閑的數(shù)據(jù)信道，最后給節(jié)點(diǎn)A返回響應(yīng)消息，節(jié)點(diǎn)A在收到響應(yīng)信息后，通過(guò)數(shù)據(jù)信道與節(jié)點(diǎn)B進(jìn)行數(shù)據(jù)的傳輸，同時(shí)給其鄰居節(jié)點(diǎn)廣播該信道被占用的消息，禁止鄰居節(jié)點(diǎn)在使用該信道。所有數(shù)據(jù)交互的過(guò)程都是經(jīng)過(guò)控制信道完成的。DCA作為相對(duì)簡(jiǎn)單的一種動(dòng)態(tài)信道分配方案，其提高了數(shù)據(jù)的傳輸速率與網(wǎng)絡(luò)的吞吐量，由于其需要使用專(zhuān)門(mén)的一個(gè)控制信道用以對(duì)數(shù)據(jù)信道的分析和選取，因此其降低了信道的利用率。endprint

文獻(xiàn)[17]中給出了一種將時(shí)間進(jìn)行分片的SSCH（Slotted Seeded Channel Hopping）新協(xié)議，其可以讓無(wú)線射頻接口在空閑信道之間進(jìn)行切換，并可以讓節(jié)點(diǎn)之間達(dá)成偏序同步，用以提升傳輸?shù)乃俾?。但是SSCH只對(duì)單無(wú)線射頻接口支持，而且它對(duì)全網(wǎng)時(shí)鐘同步有一定的要求。

文獻(xiàn)[18]中給出了一種基于網(wǎng)絡(luò)流量與干擾感知的動(dòng)態(tài)信道分配方案，根據(jù)節(jié)點(diǎn)的流量、節(jié)點(diǎn)與網(wǎng)關(guān)的距離和節(jié)點(diǎn)的接口數(shù)量來(lái)計(jì)算節(jié)點(diǎn)的優(yōu)先級(jí)，然后使用時(shí)間貪婪啟發(fā)式算法給節(jié)點(diǎn)進(jìn)行信道分配。

在文獻(xiàn)[19]中，作者通過(guò)考慮拓?fù)淇刂坪托诺婪峙溥@兩個(gè)方面，用拓?fù)淇刂平鉀Q信道獨(dú)立性問(wèn)題，用信道分配解決信道干擾問(wèn)題。

大多數(shù)的動(dòng)態(tài)信道分配方案都要求無(wú)線射頻接口在極短時(shí)間內(nèi)實(shí)現(xiàn)信道之間的切換，因?yàn)橹挥袩o(wú)線射頻接口的信道切換時(shí)延越小，新協(xié)議才能夠充分發(fā)揮性能。目前的無(wú)線射頻接口硬件設(shè)備的信道切換時(shí)延在實(shí)際應(yīng)用中還是比較大的，無(wú)法完美滿足此類(lèi)要求。

4 混合信道分配

混合信道分配方案是靜態(tài)和動(dòng)態(tài)信道分配方案的組成，方案中將節(jié)點(diǎn)的一部分接口使用靜態(tài)信道分配方案，其他的射頻接口則使用動(dòng)態(tài)信道分配方案，能夠依據(jù)實(shí)時(shí)需求動(dòng)態(tài)的切換信道。混合信道分配方案既具有確保網(wǎng)絡(luò)連通性的靜態(tài)信道分配方案優(yōu)勢(shì)，又能夠像動(dòng)態(tài)信道分配方案一樣，根據(jù)網(wǎng)絡(luò)實(shí)時(shí)負(fù)載和鏈路干擾情況，進(jìn)行合理的信道分配，最小化局部干擾鏈路，提高網(wǎng)絡(luò)的整體容量。

混合多信道協(xié)議（Hybrid Multi-Channel Protocol，HMCP）[20-21]是一種主要針對(duì)多射頻接口的鏈路層多信道協(xié)議對(duì)于每個(gè)節(jié)點(diǎn)，一些接口分配固定信道，而其余接口可以頻繁切換通道。每個(gè)節(jié)點(diǎn)通過(guò)在所有信道上向其鄰居廣播消息來(lái)向其鄰居通知其固定信道。假如一個(gè)節(jié)點(diǎn)需要想鄰居發(fā)送數(shù)據(jù)包，首先它通過(guò)一個(gè)可切換的射頻接口切換到與其鄰居固定接口上的一個(gè)信道，之后通過(guò)這個(gè)可切換接口進(jìn)行數(shù)據(jù)包的發(fā)送。圖2為一個(gè)例子，其中每個(gè)節(jié)點(diǎn)都有一個(gè)固定接口和一個(gè)可切換接口。固定接口分配固定信道。A可以通過(guò)將可切換接口切換到信道2來(lái)將數(shù)據(jù)傳輸?shù)紹，B可以通過(guò)將可切換接口切換到信道3來(lái)將數(shù)據(jù)傳輸?shù)紺。盡管這種方法會(huì)導(dǎo)致信道切換開(kāi)銷(xiāo)，并且具有簡(jiǎn)單的控制，延遲數(shù)據(jù)傳輸，因?yàn)槊刻臄?shù)據(jù)傳輸需要信道切換。

文獻(xiàn)[22]中Ding等提出了ADCA協(xié)議。它考慮了混合無(wú)線架構(gòu)，并使用hyacinth架構(gòu)來(lái)支持MC和多接口的仿真。主要針對(duì)網(wǎng)絡(luò)中的吞吐量和延遲問(wèn)題。在混合架構(gòu)中，節(jié)點(diǎn)的一些接口可以進(jìn)行信道切換，其他接口使用靜態(tài)信道分配。使用靜態(tài)信道分配方案的接口有助于最大化從終端用戶到網(wǎng)關(guān)節(jié)點(diǎn)的吞吐量。而使用動(dòng)態(tài)信道方案的接口則增加了網(wǎng)絡(luò)的連接，并可以幫助網(wǎng)絡(luò)適應(yīng)不同的業(yè)務(wù)需求。ADCA將時(shí)間分成固定長(zhǎng)度間隔：[T=Tc+Td]，其中[Tc]和[Td]分別表示控制間隔和數(shù)據(jù)間隔。在控制間隔中，所有節(jié)點(diǎn)使用相同的默認(rèn)信道。數(shù)據(jù)發(fā)送和接收在數(shù)據(jù)間隔期間完成。在數(shù)據(jù)傳輸過(guò)程中，動(dòng)態(tài)接口選取鄰居節(jié)點(diǎn)并進(jìn)行信道的協(xié)商。它維護(hù)鏈路層中的鄰居隊(duì)列長(zhǎng)度，并根據(jù)隊(duì)列長(zhǎng)度和隊(duì)列等待時(shí)間選擇鄰居。該協(xié)議使用隊(duì)列閾值（[QT]）來(lái)確定信道協(xié)商過(guò)程是否應(yīng)該繼續(xù)。隊(duì)列長(zhǎng)度大于閾值會(huì)導(dǎo)致流量負(fù)載飽和。ADCA協(xié)議中的業(yè)務(wù)負(fù)載有閾值。當(dāng)業(yè)務(wù)流量超過(guò)閾值時(shí)，網(wǎng)絡(luò)面臨相當(dāng)大的延遲。

廣度優(yōu)先搜索信道分配算法[23]是一個(gè)集中式的基于干擾避免的信道分配算法，其目的是最小化干擾的影響來(lái)提升WMNs骨干網(wǎng)的容量。通過(guò)對(duì)沖突圖的概念進(jìn)行擴(kuò)展，BFS-CA算法提出了一種多射頻沖突圖（Multi-radio Conflict Graph，MGC）的概念。在MCG中，頂點(diǎn)代表的是節(jié)點(diǎn)每個(gè)接口之間的鏈路，而不再是Mesh節(jié)點(diǎn)之間的鏈路。在算法中給節(jié)點(diǎn)的一個(gè)接口分配默認(rèn)的靜態(tài)信道，節(jié)點(diǎn)的剩余接口分配非默認(rèn)信道。BFS-CA算法按照從多射頻沖突圖中獲取的干擾射頻接口數(shù)量信息來(lái)計(jì)算帶寬與干擾，然而僅僅根據(jù)無(wú)線射頻接口的干擾數(shù)量并不能準(zhǔn)確反映出接口的干擾情況，應(yīng)該同時(shí)考慮到干擾射頻接口的流量大小。在兩個(gè)信道間無(wú)線干擾射頻接口數(shù)量一樣的情況下，若其中一條信道經(jīng)常被使用，而另外一條信道使用頻率較低，則顯然第一條信道的干擾情況更嚴(yán)重。所以每個(gè)節(jié)點(diǎn)都會(huì)給信道劃分兩個(gè)獨(dú)立的等級(jí)，第一級(jí)是依據(jù)干擾射頻接口的數(shù)量給信道分級(jí)，第二級(jí)是通過(guò)信道的利用率給信道分級(jí)，最后通過(guò)將兩種等級(jí)綜合考慮求得最終的信道等級(jí)信息。首先網(wǎng)絡(luò)按照信道等級(jí)信息將默認(rèn)信道分配給節(jié)點(diǎn)，然后按照多射頻沖突圖的信息給節(jié)點(diǎn)分配非默認(rèn)信道。

BFS-CA算法全面考慮了信道帶寬和干擾的問(wèn)題，通過(guò)分配默認(rèn)靜態(tài)信道防止了默認(rèn)的信道切換導(dǎo)致的數(shù)據(jù)流中斷問(wèn)題，由于需要節(jié)點(diǎn)周期性獲得干擾射頻數(shù)量與信道使用狀況信息，從而導(dǎo)致了射頻接口的利用率降低。

文獻(xiàn)[24]中給出了一種結(jié)合靜態(tài)和動(dòng)態(tài)信道分配特點(diǎn)的混合多信道多接口無(wú)線Mesh網(wǎng)絡(luò)架構(gòu)。在這種架構(gòu)中網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的其中一個(gè)接口都能夠頻繁的進(jìn)行信道的切換，而其他接口則在固定的信道上工作。包括網(wǎng)關(guān)的大多數(shù)節(jié)點(diǎn)具有3個(gè)接口，并且?guī)讉€(gè)邊界節(jié)點(diǎn)（c，g，i，f）具有2個(gè)接口。相鄰節(jié)點(diǎn)的靜態(tài)接口如果在相同的固定信道上工作，則構(gòu)建靜態(tài)鏈路（無(wú)信道切換）。靜態(tài)接口的信道分配旨在最大化從終端用戶到網(wǎng)關(guān)的網(wǎng)絡(luò)吞吐量，這通常構(gòu)成網(wǎng)絡(luò)中流量的主要部分。如圖4所示，通過(guò)靜態(tài)接口上的信道分配構(gòu)建了樹(shù)形拓?fù)洌瑥亩畲笙薅鹊靥岣吡俗罱K用戶的吞吐量。動(dòng)態(tài)接口以按需方式工作。在節(jié)點(diǎn)的傳輸范圍內(nèi)的兩個(gè)動(dòng)態(tài)接口能夠在需要傳輸數(shù)據(jù)時(shí)切換到相同的信道進(jìn)行通信。圖3說(shuō)明了所有可能的動(dòng)態(tài)鏈接。所提出的架構(gòu)不僅通過(guò)靜態(tài)鏈路確保高質(zhì)量的路徑，而且還改善了網(wǎng)絡(luò)的連接性和適應(yīng)性，以改變動(dòng)態(tài)鏈路的交換。此外，它還降低了信道的切換開(kāi)銷(xiāo)。

與動(dòng)態(tài)信道分配方法相比，混合信道分配方式降低了信道交換開(kāi)銷(xiāo)，并且與靜態(tài)信道分配方法相比，保持了對(duì)變化的流量的良好適應(yīng)性。當(dāng)節(jié)點(diǎn)上可以使用的無(wú)線射頻接口較少時(shí)，混合信道分配方式會(huì)導(dǎo)致信道資源的浪費(fèi)。因?yàn)槠湟獙閿?shù)不多的可用無(wú)線接口中，分出一部分以維持網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。endprint

5 結(jié)論和未來(lái)研究方向

靜態(tài)信道分配方案通常具有較低的信道切換開(kāi)銷(xiāo)，動(dòng)態(tài)信道分配方案更適應(yīng)于變化的流量，而混合信道分配方案則結(jié)合了這兩種信道分配方案的優(yōu)點(diǎn)。由于信道分配問(wèn)題是一個(gè)NP-hard問(wèn)題，所以絕大部分信道分配方案都是采用啟發(fā)式的方法。

靜態(tài)信道分配方案不需要接口進(jìn)行信道的切換，因此開(kāi)銷(xiāo)較低。然而，它們依賴(lài)于穩(wěn)定的網(wǎng)絡(luò)流量模式。雖然動(dòng)態(tài)信道分配方案具有較高的信道切換開(kāi)銷(xiāo)，但當(dāng)網(wǎng)絡(luò)流量頻繁變化時(shí)，它們更為合適。在靜態(tài)信道分配中，通?？紤]MAC層和路由層之間的跨層問(wèn)題，而在動(dòng)態(tài)信道分配中，關(guān)鍵問(wèn)題是如何協(xié)調(diào)信道同步問(wèn)題和信道切換問(wèn)題。大部分的靜態(tài)信道分配方案都使用集中式的方法，而大部分動(dòng)態(tài)信道分配方案都使用分布式的方法。

由于靜態(tài)和動(dòng)態(tài)信道分配方案的優(yōu)點(diǎn)和缺點(diǎn)，最好考慮混合信道分配方案，其中每個(gè)Mesh路由器都具有靜態(tài)和動(dòng)態(tài)接口。該架構(gòu)可以降低信道切換開(kāi)銷(xiāo)，同時(shí)使信道分配適應(yīng)不斷變化的環(huán)境。 有幾個(gè)難點(diǎn)在這個(gè)領(lǐng)域值得深入的研究，例如如何協(xié)調(diào)靜態(tài)和動(dòng)態(tài)接口的信道分配，以及如何確定每個(gè)流量的負(fù)載，從而達(dá)到信道的最佳性能。

信道分配中面臨的一個(gè)挑戰(zhàn)問(wèn)題是無(wú)線信道沒(méi)有充分的利用，大多數(shù)以前的研究只考慮了不重疊的信道。由于部分重疊信道的干擾模型比正交信道更為復(fù)雜，因此在信道分配算法的設(shè)計(jì)中增加了更多的復(fù)雜性。由于使用多接口多信道能夠極大提升網(wǎng)絡(luò)的容量，所以可以設(shè)想，將來(lái)越來(lái)越多實(shí)時(shí)應(yīng)用，將在無(wú)線Mesh網(wǎng)絡(luò)中流行。如何確保延遲敏感和高比特率流量的服務(wù)質(zhì)量，找出適當(dāng)?shù)穆酚珊托诺婪峙涫且粋€(gè)具有挑戰(zhàn)性的問(wèn)題。

參考文獻(xiàn)：

[1] M. Portmann and A. A. Pirzada.Wireless mesh networks for public safety and crisis management applications[J]. IEEE Internet Computing， 2008，12（1）：18-25.

[2] S. Avallone， I.F. Akyildiz.A Channel Assignment Algorithm for Multi-Radio Wireless Mesh Networks[C]. Proc of 16th Int. Conf. on Computer Communications and Networks，2007： 1034-1039.

[3] K. N. Ramachandran， E. M. Belding， K. C. Almeroth， M. M. Buddhikot.Interference-Aware Channel Assignment in Multi-Radio Wireless Mesh Networks[C]. Proc. of 25th IEEE Int. Conf. on Computer Communications， 2006： 1-12.

[4] Raniwala A， Gopalan K， Chiueh T. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review， 2004， 8（2）：50-65.

[5] Wireless Mesh networking： architectures， protocols and standards[M]. CRC Press， 2006.

[6] S.A. Makram，and M.Gunes.Channel assignment for multi-radio wireless mesh networks using clustering[C].Proceedings of the 2008 International Conference on Telecommunications，IEEE，June 2008：1-6.

[7] 張劼，鐘朗等.基于節(jié)點(diǎn)優(yōu)先級(jí)的無(wú)線Mesh網(wǎng)絡(luò)資源分配[J].電子科技大學(xué)學(xué)報(bào)，2016，01：54-49.

[8] Marina M K， Das S R， Subramanian A P. A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks[J]. Computer Networks， 2010， 54（2）：241-256.

[9] Raniwala A， Gopalan K， Chiuen T. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review， 2004， 8（2）：50-65.

[10] 彭利民，劉浩.多信道無(wú)線Mesh網(wǎng)絡(luò)信道分配算法[J].計(jì)算機(jī)應(yīng)用，2009，29（7）：1849-1851.

[11] R. Chandra， P. Bahl， P. Bahl， Multinet： connecting to multiple ieee 802.11 networks using a single wireless card， in： INFOCOM， 2004.endprint

[12] P. Kyasanur， N. Vaidya， Routing and interface assignment in multi-channel multi-interface wireless networks， in： WCNC， 2005. （下轉(zhuǎn)第43頁(yè)）

（上接第27頁(yè)）

[13] A. Raniwala， T. Chiueh， Architecture and algorithms for an ieee 802.11-based multi-channel wireless mesh network， in： INFOCOM， 2005.

[14] J. So，N.H. Vaiday. Multi-Channel MAC for Ad Hoc Networks： Handling Multi-Channel Hidden Terminals Using A Single Transceiver. Proc. of ACM MobiHoc，2004：222-233.

[15] Raniwala A， Chiueh T.Architecture and algorithms for an IEEE 802.11-based multi-channel wireless Mesh network[C]. INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE. IEEE， 2005， 3： 2223-2234.

[16] Wu S L， Lin C Y， Tseng Y C， etal. A new multi-channel MAC protocol with on-demand channel assignment for multi-hop mobile ad hoc networks[C]. International Symposium on Parallel Architectures，Algorithms and Networks， 2000：232-237.

[17] P. Bahl， R. Chandra， J. Dunagan. SSCH： Slotted seeded channel hopping for capacity improvement in IEEE 802.11 adhoc wireless networks[C]. Proc. Of ACM MobiCom， 2004：216-230.

[18] Subramanian A， Gupta H， Das S R. Minimum interference channel assignment in multi-radio wireless mesh networks[J]. IEEE Transactions on Mobile Computing， 2008， 7（12）：1459-1473.

[19] Rad A H， Wong V W. Logical topology design and interface assignment for multi-channel wireless mesh networks[C]. IEEE Global Telecommunications Conference， 2006：1-6.

[20] Kyasanur P， Vaidya N H. Routing andinterface assignment in multi-channel multi-interface wireless networks[C].Wireless Communications and Networking Conference， 2005 IEEE.IEEE， 2005， 4： 2051-2056.

[21] P Kyasanur P， Vaidya N H. Routing and link-layer protocols for multi-channel multi-interface ad hoc wireless networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review， 2006， 10（1）：31- 43.

[22] Y. Ding， K. Pongaliur， L. Xiao， and S. Member.Channel allocation and routing in hybrid multichannel multiradio wireless mesh networks[J].IEEE Trans. Mobile Compute， 2013， 12： 206-218.

[23] Ramachandran K N， Belding E M， Almeroth K C， et al. Interference-aware channel assignment in multi-radio wireless mesh networks[C].IEEE INFOCOM. 2006， 6： 1-12.

[24] Y. Ding， K. Pongaliur， L. Xiao， Hybrid multi-channel multi-radio wireless mesh networks， in： IWQoS， 2009.endprint