基于窮舉搜索的無(wú)線Mesh網(wǎng)絡(luò)分配信道可行性研究

張繼成+羊秋玲

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

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

中圖分類號(hào)： TN929.5?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

作為一個(gè)非常有前途的無(wú)線寬帶技術(shù)，無(wú)線Mesh網(wǎng)絡(luò)被認(rèn)為是WLAN熱點(diǎn)區(qū)域最好的解決方案之一[1]。事實(shí)上，由于網(wǎng)絡(luò)接口卡相對(duì)比較廉價(jià)，為了提高網(wǎng)絡(luò)的吞吐量，越來(lái)越多的商業(yè)Mesh路由器在多個(gè)信道上配備多個(gè)天線。然而，可以利用的無(wú)線信道數(shù)量相對(duì)有限，因此，在商業(yè)多天線無(wú)線Mesh網(wǎng)絡(luò)的設(shè)計(jì)和部署中，如何分配可利用的有限信道變得非常重要。

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

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

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

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

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

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

1 問(wèn)題描述

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

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

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

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

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

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

此外，假設(shè)在給定的信道分配（CA），在中計(jì)算目標(biāo)函數(shù)的值需要多項(xiàng)式時(shí)間。因此信道分配問(wèn)題的復(fù)雜性由許多不同的信道分配所決定，用來(lái)表示。

2 復(fù)雜度分析

2.1 一般的信道分配問(wèn)題（G?CAP）

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

2.2 實(shí)際的信道分配問(wèn)題（P?CAP）

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

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

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

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

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

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

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

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

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

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

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

其中是鏈路子集的大小。

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

在這里和不同的信道相對(duì)應(yīng)，在形成的個(gè)鏈路子集中沒(méi)有使用。

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

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

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

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

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

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

2.4 復(fù)雜度比較

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

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

3 理論運(yùn)行時(shí)間

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

3.1 理論估計(jì)

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

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

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

3.2 評(píng)估結(jié)果

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

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

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

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

4 實(shí)驗(yàn)和可行性討論

4.1 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

4.2 可行性討論

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

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

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

5 結(jié) 語(yǔ)

本文研究了商業(yè)多天線無(wú)線Mesh網(wǎng)絡(luò)中三種類型的信道分配問(wèn)題的復(fù)雜性。根據(jù)分析結(jié)果，通過(guò)窮舉搜索，估計(jì)確定最優(yōu)信道分配的理論運(yùn)行時(shí)間，然后在實(shí)際場(chǎng)景中通過(guò)實(shí)驗(yàn)驗(yàn)證。結(jié)果表明，給定一定的計(jì)算能力，在實(shí)際的小型和中型多天線無(wú)線Mesh網(wǎng)絡(luò)中，優(yōu)化解決信道分配問(wèn)題是可行的，而近似算法在大規(guī)模Mesh網(wǎng)絡(luò)中是不可或缺的。最后，在商業(yè)無(wú)線Mesh網(wǎng)絡(luò)中提出公開(kāi)的基本信道分配問(wèn)題，并為算法設(shè)計(jì)和網(wǎng)絡(luò)規(guī)劃提供指導(dǎo)意義。endprint

參考文獻(xiàn)

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

[2] 夏漢鑄，劉輝元.無(wú)線Mesh網(wǎng)絡(luò)中基于信道狀態(tài)的動(dòng)態(tài)信道分配算法研究[J].重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 樂(lè)光學(xué)，李明明，丁輝，等.無(wú)線 Mesh網(wǎng)絡(luò)中基于演化博弈的抗振蕩信道分配策略[J].電子學(xué)報(bào)，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] 王子凡，劉作學(xué)，代健美.基于干擾感知的多接口無(wú)線Mesh網(wǎng)絡(luò)信道分配算法[J].現(xiàn)代電子技術(shù)，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] 張偉昆，黃煒，張大偉.基于連接低干擾的無(wú)線Mesh網(wǎng)絡(luò)信道分配算法研究[J].電子科技大學(xué)學(xué)報(bào)，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] 張繩武，曾鋒，陳志剛.無(wú)線Mesh網(wǎng)中一種流量感知和干擾優(yōu)化的信道分配機(jī)制[J].計(jì)算機(jī)應(yīng)用研究，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