張繼成+羊秋玲

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

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

中圖分類號： 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網(wǎng)絡被認為是WLAN熱點區(qū)域最好的解決方案之一[1]。事實上，由于網(wǎng)絡接口卡相對比較廉價，為了提高網(wǎng)絡的吞吐量，越來越多的商業(yè)Mesh路由器在多個信道上配備多個天線。然而，可以利用的無線信道數(shù)量相對有限，因此，在商業(yè)多天線無線Mesh網(wǎng)絡的設計和部署中，如何分配可利用的有限信道變得非常重要。

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

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

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

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

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

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

1 問題描述

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

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

小規(guī)模的多天線無線Mesh網(wǎng)絡：

中等規(guī)模的多天線無線Mesh網(wǎng)絡：

大規(guī)模的多天線無線Mesh網(wǎng)絡：。

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

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

2 復雜度分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中是鏈路子集的大小。

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

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

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

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

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

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

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

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

2.4 復雜度比較

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

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

3 理論運行時間

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

3.1 理論估計

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

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

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

3.2 評估結(jié)果

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

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

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

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

4 實驗和可行性討論

4.1 實驗驗證

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

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

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

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

4.2 可行性討論

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

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

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

5 結(jié) 語

本文研究了商業(yè)多天線無線Mesh網(wǎng)絡中三種類型的信道分配問題的復雜性。根據(jù)分析結(jié)果，通過窮舉搜索，估計確定最優(yōu)信道分配的理論運行時間，然后在實際場景中通過實驗驗證。結(jié)果表明，給定一定的計算能力，在實際的小型和中型多天線無線Mesh網(wǎng)絡中，優(yōu)化解決信道分配問題是可行的，而近似算法在大規(guī)模Mesh網(wǎng)絡中是不可或缺的。最后，在商業(yè)無線Mesh網(wǎng)絡中提出公開的基本信道分配問題，并為算法設計和網(wǎng)絡規(guī)劃提供指導意義。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網(wǎng)絡中基于信道狀態(tài)的動態(tài)信道分配算法研究[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網(wǎng)絡中基于演化博弈的抗振蕩信道分配策略[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網(wǎng)絡信道分配算法[J].現(xiàn)代電子技術，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網(wǎng)絡信道分配算法研究[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網(wǎng)中一種流量感知和干擾優(yōu)化的信道分配機制[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