基于窮舉搜索的無線Mesh網絡分配信道可行性研究

張繼成+羊秋玲

摘 要： 信道分配問題在多天線無線Mesh網絡中已被各種文獻證明是NP難問題。分析了一般的信道分配問題的復雜性與某些基本和常見的屬性。結果表明，不同信道分配數量的復雜度和無線鏈路的數量呈指數關系。此外，估計了通過窮舉搜索確定最優信道分配的理論運行時間，并通過實驗驗證。實驗表明，給予一定的計算能力（如一個現成的筆記本電腦），在小規模和中等規模的商業無線Mesh網絡中，對于最優解決信道分配問題是可行的。

關鍵詞： 無線Mesh網絡； 信道分配； 窮舉搜索； 干擾最小化； 復雜度； 無線鏈路

中圖分類號： TN929.5?34 文獻標識碼： A 文章編號： 1004?373X（2018）05?0014?06

Abstract： The channel assignment problem in multi?radio wireless Mesh networks （WMNs） is the NP?hard problem proved by various literatures. The complexity of the general channel assignment problem is analyzed， as well as a certain basic and common properties. The results show that the complexity of different possible channel assignment quantity has exponent relation to the wireless link quantity. Furthermore， the theoretical runtime of optimal channel assignment determined by exhaustive search was estimated， and verified with experiments. The experimental results show that， giving a certain computing power （notebook PC）， it is feasible to solve the optimal channel assignment problem in small?and medium?scale commercial WMNs.

Keywords： wireless Mesh network； channel assignment； exhaustive search； interference minimality； complexity； wireless link

0 引 言

作為一個非常有前途的無線寬帶技術，無線Mesh網絡被認為是WLAN熱點區域最好的解決方案之一[1]。事實上，由于網絡接口卡相對比較廉價，為了提高網絡的吞吐量，越來越多的商業Mesh路由器在多個信道上配備多個天線。然而，可以利用的無線信道數量相對有限，因此，在商業多天線無線Mesh網絡的設計和部署中，如何分配可利用的有限信道變得非常重要。

近年來，研究人員對無線Mesh網絡信道分配問題產生了極大的研究興趣，在文獻中也提出了許多解決的方法，包括動態或者靜態方法。文獻[2]在無線Mesh網絡中提出基于信道狀態的動態信道分配算法。文獻[3]提出基于演化博弈的抗振蕩動態信道分配策略，動態方法需要在非常快的時間內進行信道切換，因此需要節點之間的同步合作。此外，大部分的動態方法還需要專門的MAC協議或者修改的802.11MAC層，因此，它們不適合在現存的硬件上使用。在靜態分配方法中，除非有重大的網絡流量負載或者網絡拓撲結構變化，算法永久的分配信道，同時也不考慮信道切換延遲和流量測量開銷。除了動態、靜態方法，文獻[4?5]提出基于干擾感知的多接口無線Mesh網絡信道分配算法，文獻[6]提出一種流量感知和干擾優化的信道分配機制。

除了以上提供的解決方案，最近提出了許多聯合優化解決方案[7?9]。相關工作提出信道分配和其他因素聯合優化問題，比如和路由、拓撲控制、調度、擁塞控制、媒體訪問控制（MAC）等的聯合。

在本文中，研究在多天線無線Mesh網絡中給鏈路靜態分配不重疊的信道問題，在實際的商業網絡中考慮通用性和可行性。研究基于窮舉搜索最優化信道分配的復雜度，進一步找出在給定規模的商業無線Mesh網絡中，以這種最簡單的方法優化解決這類問題是否可行。

在相關工作中，一些特定的信道分配問題已經被證明是NP難問題。文獻[10]對提出的信道分配問題通過減少多個子集和問題證明其是NP難問題?；谖墨I[10]的證據，文獻[11]通過打破單一碰撞域使之成為更小的沖突域，表明定向信道分配也是NP難問題。

值得注意的是，一方面，所有特定的信道分配問題都被證明是NP難問題，因此，不能證明廣義信道分配問題具有不同的目標或約束。另一方面，信道分配問題的NP難問題意味著在大規模WMNs中很難確定最優信道分配。出于這個原因，大部分研究聚焦在發展高效的近似算法上，而不是最優的，其可以提供質量好的信道分配，運行速度快。然而，在許多現有的小型和中型的商業WMNs中，在合適的時間確定最優的信道分配是可能的。關鍵問題是確定多大的網絡規模是可行的。到目前為止，對于這個問題，相關研究人員已經提出了大量的信道分配方案，本文試圖通過理論分析和仿真實驗找出這個問題的答案，具體如下：

在多天線無線Mesh網絡中，本文研究純粹的信道分配問題的復雜性，而不是聯合優化問題。根據理論分析結果，估計基于窮舉搜索確定最優信道分配的理論運行時間。為優化解決相應的信道分配問題，設計三個窮舉搜索算法并在實驗中加以運行。通過比較理論運行時間和在實際場景中的實驗結果，驗證了理論估計時間。結論表明，給予一定的計算能力（如一個現成的筆記本電腦），在實際小規模和中等規模商業多天線無線Mesh網絡中，決定最優信道分配問題是可行的。endprint

1 問題描述

在商業多天線無線Mesh網絡中，通常路由器被配備多個無線網絡接口，而且每個接口被分配不同的信道。從本質上講，信道分配問題是給每個無線網絡接口分配可用的無線信道，以最大化網絡吞吐量。無線網絡接口和無線鏈路都可以被認為是基本的信道分配單元，在本文分析中，考慮雙向無線鏈路作為基本的信道分配單元。

無線Mesh網絡中有兩種類型的流量：客戶及其相關mesh路由器之間的網絡訪問流量；mesh路由器之間的回程流量。本文只討論回程通信的信道分配問題，因此只考慮回程鏈接。本文中，根據雙向無線鏈路的數量，商業多天線無線Mesh網絡的網絡規模被歸類為以下三種類型（其中用表示無線鏈路）：

小規模的多天線無線Mesh網絡：

中等規模的多天線無線Mesh網絡：

大規模的多天線無線Mesh網絡：。

假設在回程無線Mesh網絡中包含個無線路由器、個雙向無線鏈路和個非重疊的信道。一般的信道分配問題（G?CAP）是為了優化某個目標給個不同的鏈路分配個不同的信道。實際上，在網絡設計和部署的早期階段，無線信道的鏈路質量是不確定或者未知的。因此，實際的信道分配問題（P?CAP）并沒有考慮不同信道的鏈路質量。如果一個P?CAP的優化目標是通過最小化鏈路之間的總干擾來最大化網絡的吞吐量，那么P?CAP被稱為最小化干擾P?CAP（簡稱i?mP?CAP）。事實上，大多數優化目標相關的工作相當于等價轉化為一個最小化總干擾問題。

此外，假設在給定的信道分配（CA），在中計算目標函數的值需要多項式時間。因此信道分配問題的復雜性由許多不同的信道分配所決定，用來表示。

2 復雜度分析

2.1 一般的信道分配問題（G?CAP）

給定個不同的鏈路和個不同的信道，對于第（2，…，）個鏈路，它被分配個信道中的一個。一旦每條鏈路被分配一個信道，則構建了一個不同的信道分配方案CA，這個信道是彼此不同的，對于每個鏈路都有次機會，因此：

2.2 實際的信道分配問題（P?CAP）

如前所述，在P?CAP中，不考慮不同信道鏈路之間的區別，定義相同的信道如下：

定義1：不同頻率的不同信道是相同的，當且僅當這些信道的鏈路質量被認為是相同的。

因此，在P?CAP中，所有可利用的信道是等價的；在G?CAP中，不同的信道分配例子在P?CAP某種情況下能變得相同。表1給出了兩種等價的信道分配方案的例子，給定4個不同的鏈路有3個信道CH1，CH2，CH3。CA1和CA2在P?CAP中是相同的，而在G?CAP中卻是不同的。

給定個不同的鏈路和個等價的信道，不同的信道分配方案數量可以由組合得出。將個不同的鏈路看做一組個元素，將個等價的信道看做是個無法區分的盒子，則P?CAP變成一個區分問題，即如何把個元素放到個盒子里，要求不允許有空盒子。因此，不同的信道分配方案數量就等于區分的數量。

在P?CAP中，不同的信道分配數量可以表示如下：

2.3 干擾最小化信道分配P?CAP（i?mP?CAP）

在i?mP?CAP中，能夠獲得比（Nca）P?CAP更少的不同信道分配數量。詳細的分析和推導如下：

引理1：給定個不同的鏈路和個等價的信道，對于任何一個信道分配CA使用個不同的信道比使用個信道能夠獲得更好的性能。

證明：設是個不同的鏈路，是個等價但不同的信道。對于任何一個信道分配CA，使用個不同的信道記為個鏈路的組成可以記為它可以被分割為個不相交的子集如下：

第鏈路子集相對應于一個不同的信道。換句話說，鏈路在同樣的子集被分配同樣的信道對于任意的根據式（3）中對的定義和引理1中提供的條件，得出：

根據式（7）得，比小，因此，通過鴿巢原理，至少有一個子集擁有至少兩條鏈路。為了不失一般性，定義是這個子集，被描述如下：

其中是鏈路子集的大小。

隨機選擇一個鏈路記為從中形成另外一個鏈路子集（注意改變的記為）。分配一個沒有使用的信道給中的使用個不同的信道構造一個新的信道分配CA記為在中，鏈路集合被分割為個不相交的子集如下：

在這里和不同的信道相對應，在形成的個鏈路子集中沒有使用。

因此，在和中惟一的區別是信道分配給在中，在中，由于引入沒有被使用的信道中減少了中的和中的所有鏈路之間的干擾，而這些鏈路在中共享信道作為中的元素。與此同時，其他鏈路子集的鏈路在中除了仍然保持不變的性能，因此能實現比更好的性能。

關于引理1及其證明，以下兩點值得注意：對于不同的信道，如果考慮不同的鏈路質量，對于能實現比更好的性能是不確定的；當一個新的信道被引入，盡管它可以減少干擾，這個新信道的鏈路質量比原來的更糟糕，在子集和整個網絡中，不能實現更好的總體性能。因此，對于引理1必須具備所有的信道是等價的這個前提。換句話說，雖然它適合i?mP?CAP信道分配，但它對G?CAP是不確定的。

如果優化目標不是等價的，或者不能等價轉化為最小化總的干擾，對于引理1是不確定的。換句話說，雖然它適合i?mP?CAP信道分配，但它對P?CAP也是不確定的。

基于引理1，則有以下定理：

定理1：給定個不同的鏈路和個等價的信道，最優的信道分配CA必須使用個不同的信道。

證明：在式（2）中給出不同的信道分配方案數量對于第（k=1，2，…，）個信道分配CA，個不同的信道被分配給個鏈路。如果認為最優的信道分配CA，記為CAC，它使用個不同的信道，而比小，通過引理1，CA使用個不同的信道能實現更好的性能，因此CAC不是最優的。假設最優的信道分配CA已經使用個不同的信道，通過引理1和式（3）中對的定義，在i?mP?CAP中，不同的信道分配的數量為：endprint

2.4 復雜度比較

不同信道分配的數量復雜度總結如表2所示。其中和由式（4）決定。假設有3個正交信道可供分配，表3中給出了一個算例復雜性。

如表2和表3所示，信道分配方案的復雜度隨著無線鏈路數量的增加而增大，此外，當無線鏈路的數量變得更大時，信道分配的復雜性在P?CAP和i?mP?CAP中的值比G?CAP小得多。

3 理論運行時間

在本節中，首先給出基于窮舉搜索的最優信道分配CA估算公式的理論運行時間。然后在實際場景中提出一個例子，給出特定的評估結果。

3.1 理論估計

在估計最優信道分配CA的運行時間之前制定一個信道分配問題的優化目標是很有必要的。根據對G?CAP和P?CAP的定義，它們在優化目標上都沒有限制，因此采用i?mP?CAP，它認為優化目標是最小化鏈路之間的總干擾。

對應一個給定的信道分配CA，對于個鏈路中的每一個，計算和其他鏈路之間的干擾來確定相關信道分配CA的總干擾。對于每一個鏈路是等價的，為干擾鏈路的上限數量。另一方面，設為計算兩條鏈路之間干擾度的時間，考慮到計算能力，是一個常數，可以由測試得出。因此，在本文中常數反映了給定的計算能力。對于一個信道分配CA，計算目標函數的時間成本由給出，它是一個的二次多項式函數，記為，所以認為一個信道分配CA的運行時間是。

此外，本文發現最優信道分配CA是所有的信道分配中基于窮舉搜索的，因此，通過第2節對的定義（見表2），對于先前提到的信道分配問題，確定最優的信道分配CA的理論運行時間為：

3.2 評估結果

例如，考慮一個實際的場景，在該場景中，在一個現成的惠普筆記本電腦上計算最優的信道分配CA，筆記本的相關系統配置信息如下：處理器：英特爾酷睿雙核T2300E（1.66 GHz，667 MHz FSB 2 MB L2高速緩存）；內存：2×512 Mb DDR2 SDRAM。

是計算兩個鏈路之間干擾的實時時間成本。運行100 000次之后得到的平均值為1.7。與此同時，假設3個正交信道可供分配，的值為3，這種假設是合理的。根據IEEE 802.11標準，在802.11b/g帶寬中有3個正交信道，因此，式（11）可以寫成：

基于式（12），給出理論運行時間和無線鏈路數量的關系如圖1所示。

從圖1中可以看到，一方面，通過窮舉搜索計算最優信道分配CA的運行時間隨著鏈路的增加呈指數型增長。另一方面，對于增加同樣數量的鏈路數，在G?CAP信道分配中運行的時間比在P?CAP和i?mP?CAP中更多一些，而在i?mP?CAP中信道分配運行的時間在同樣數量的鏈路下比P?CAP要更少一些。

4 實驗和可行性討論

4.1 實驗驗證

除了在第3節提到的主要因素盡管核心算法是相同的（比如窮舉搜索），在實際中確定最優信道分配CA的真正運行時間也會受到軟件設計細節的影響。與此同時，理論估計不可能考慮到所有軟件設計的細節。因此，在實際場景中依靠實驗來驗證在第3節提到的理論結果是非常有必要的。

對于多天線多信道無線Mesh網絡，基于信道分配工具CAT，設計了三種窮舉搜索算法來解決三種相應的信道分配問題：G?CAP，P?CAP，i?mP?CAP。最優信道分配CA的最優性能在先前的工作中被CAT驗證，在本節中，關注對以上三種算法使用CAT工具在三種信道分配問題上確定最優信道分配CA的真正運行時間，和實驗時間相比，驗證了理論估計結果。

在這個實驗的實際場景中，和3.2節中的例子一樣，具體來說，在同樣的惠普筆記本上運行軟件CAT，此外，可以利用的正交信道數量也設置為3。對于優化解決先前提到的信道分配問題，運行CAT以后，則記錄了真實的實驗運行時間，實驗運行時間和雙向無線鏈路數量的大小關系如圖2所示。

通過圖1和圖2中理論運行時間和實驗結果的比較，得出以下結論：在以上三種信道分配問題上，理論結果和實驗結果在運行時間的走勢上是相同的，都為單獨考慮每個問題，理論運行時間和實驗結果彼此接近；隨著網絡規模的增長，運行時間的增量趨勢在理論和實驗結果上是一致的。因此，通過在實際場景中的實驗，在信道分配問題上驗證了理論估計運行時間來確定最優信道分配CA 。

4.2 可行性討論

根據上述分析和驗證，顯示當無線鏈路增加時，最優解決G?CAP的運行時間比P?CAP和i?mP?CAP增加得更快一些。對于提到的所有信道分配問題，由于采用了窮舉搜索算法，即使網絡的規模不是很大，在實際中運行時間仍然會很久。因此，在大規模無線Mesh網絡中，近似算法對信道分配問題是不可或缺的。

然而，本文也表明給定一定的計算能力（如現成的筆記本電腦），在商業小規模和中等規模的無線Mesh網絡中，通過窮舉搜索確定最優信道分配CA是可行的。以4.1節中所描述的實驗為例，當無線鏈路的數量小于20時，在P?CAP和i?mP?CAP中的運行時間成本在實踐中是可以接受的。這里的無線鏈路被認為是最基本的信道分配單元，由于信道依賴共享Mesh路由器公共接口的鏈路，而在實際的無線Mesh網絡中，真正的信道分配單元通常包括若干個無線鏈路。真正的信道分配單元要比無線鏈路的數量要少，給定在第3節描述的一個筆記本配置的計算能力，在商業中等規模的無線Mesh網絡中，只要信道分配單元的數量少于20，通過窮舉搜索確定最優信道分配CA是可行的。

對于商業小規模和中等規模的無線Mesh網絡，沒有必要設計近似算法提供給非優化的信道分配CA。給定一定的計算能力和網絡信息，根據文中提出的理論估計方法，能夠提供一個有用的判斷。

5 結 語

本文研究了商業多天線無線Mesh網絡中三種類型的信道分配問題的復雜性。根據分析結果，通過窮舉搜索，估計確定最優信道分配的理論運行時間，然后在實際場景中通過實驗驗證。結果表明，給定一定的計算能力，在實際的小型和中型多天線無線Mesh網絡中，優化解決信道分配問題是可行的，而近似算法在大規模Mesh網絡中是不可或缺的。最后，在商業無線Mesh網絡中提出公開的基本信道分配問題，并為算法設計和網絡規劃提供指導意義。endprint

參考文獻

[1] AKYILDIZ I F， WANG X， WANG W. Wireless mesh networks： a survey [J]. Computer networks & ISDN systems， 2005， 47（3）： 445?487.

[2] 夏漢鑄，劉輝元.無線Mesh網絡中基于信道狀態的動態信道分配算法研究[J].重慶郵電大學學報（自然科學版），2014，26（3）：362?366.

XIA Hanzhu， LIU Huiyuan. Channel?state?based dynamic channel assignment algorithm in multichannel wireless Mesh networks [J]. Journal of Chongqing University of Posts and Telecommunications （natural science edition）， 2014， 26（3）： 362?366.

[3] 樂光學，李明明，丁輝，等.無線 Mesh網絡中基于演化博弈的抗振蕩信道分配策略[J].電子學報，2016，44（1）：176?185.

YUE Guangxue， LI Mingming， DING Hui， et al. The anti?channel oscillation channel assignment scheme based on evolutionary game in wireless Mesh network [J]. Acta electronica sinica， 2016， 44（1）： 176?185.

[4] 王子凡，劉作學，代健美.基于干擾感知的多接口無線Mesh網絡信道分配算法[J].現代電子技術，2014，37（14）：24?27.

WANG Zifan， LIU Zuoxue， DAI Jianmei. Interference?aware based channel assignment algorithm for multi?interface wireless Mesh networks [J]. Modern electronics technique， 2014， 37（14）： 24?27.

[5] 張偉昆，黃煒，張大偉.基于連接低干擾的無線Mesh網絡信道分配算法研究[J].電子科技大學學報，2014，43（6）：817?822.

ZHANG Weikun，HUANG Wei， ZHANG Dawei. A study of wireless Mesh networks based on connected low interference channel assignment algorithm [J]. Journal of University of Electronic Science and Technology of China， 2014， 43（6）： 817?822.

[6] 張繩武，曾鋒，陳志剛.無線Mesh網中一種流量感知和干擾優化的信道分配機制[J].計算機應用研究，2016，33（3）：810?812.

ZHANG Shengwu， ZENG Feng， CHEN Zhigang. Traffic?aware and interference optimized channel assignment mechanism in wireless Mesh network [J]. Application research of computers， 2016， 33（3）： 810?812.

[7] WU Di， YANG S H， BAO Lichun， et al. Joint multi?radio multi?channel assignment， scheduling， and routing in wireless mesh networks [J]. Wireless networks， 2014， 20（1）： 11?24.

[8] ULUCINAR A R， KORPEOGLU I. Distributed joint flow?radio and channel assignment using partially overlapping channels in multi?radio wireless mesh networks [J]. Wireless networks， 2016， 22（1）： 83?104.

[9] CHENG Hongju， XIONG Naixue， CHEN G， et al. Links organization for channel assignment in multi?radio wireless mesh networks [J]. Multimedia tools & applications， 2013， 65（2）： 239?258.

[10] RANIWALA A， GOPALAN K， CHIUEH T. Centralized channel assignment and routing algorithms for multi?channel wireless mesh networks [J]. ACM mobile computing and communications review， 2004， 8（2）： 50?65.

[11] DAS S M， PUCHA H， KOUTSONIKOLAS D， et al. DMesh： incorporating practical directional antennas in multi?channel wireless mesh networks [J]. IEEE journal on selected areas in communications， 2006， 24（11）： 2028?2039.endprint