AP放置和信道分配在無(wú)線局域網(wǎng)的優(yōu)化

1、在無(wú)線局域網(wǎng)中AP的位置和信道分配的優(yōu)化摘要設(shè)計(jì)一個(gè)無(wú)線局域網(wǎng)絡(luò)（WLAN）需要有一個(gè)確定的最優(yōu)配置接入點(diǎn)（AP）和分配給他們的渠道。無(wú)線局域網(wǎng)在室外以及室內(nèi)環(huán)境的服務(wù)都應(yīng)當(dāng)以達(dá)到最大的覆蓋范圍和吞吐量來(lái)設(shè)計(jì)。為了提供無(wú)線局域網(wǎng)服務(wù)領(lǐng)域的最大覆蓋范圍，應(yīng)安裝接入點(diǎn)，使得測(cè)量信號(hào)的總和在每個(gè)傳輸需求點(diǎn)都達(dá)到最大化。然而，當(dāng)用戶(hù)連接一個(gè)無(wú)線AP與其他人共享同一個(gè)信道帶寬時(shí)，應(yīng)當(dāng)仔細(xì)衡量接入點(diǎn)間的負(fù)載平衡，考慮吞吐量的大小并根據(jù)用戶(hù)流量大小來(lái)分配信道帶寬。在本文中，我們提出了一個(gè)AP的放置的優(yōu)化方法，為無(wú)線局域網(wǎng)的信道分配制定一個(gè)最佳整數(shù)線性規(guī)劃（ILP）。該優(yōu)化目的是在WLAN熱點(diǎn)服務(wù)領(lǐng)域中最大限

2、度的降低信道的利用率。模擬結(jié)果表明，該方法找出AP最佳的位置和渠道，最大限度地減少信道的利用率。索引詞-網(wǎng)絡(luò)設(shè)計(jì)，無(wú)線局域網(wǎng)，IEEE 802.11b，負(fù)載平衡，ILP，優(yōu)化。導(dǎo)言盡管無(wú)線局域網(wǎng)1的目的是為不具備傳統(tǒng)的有線局域網(wǎng)服務(wù)的樓宇提供局域網(wǎng)連接，它開(kāi)始支持移動(dòng)電腦在一幢房子或是一校園的連接。一般來(lái)說(shuō)，無(wú)線局域網(wǎng)屬于無(wú)照經(jīng)營(yíng)工業(yè)，科學(xué)，醫(yī)學(xué)（ISM）工作在915HZ，2.4KHZ，5KHZ頻段。無(wú)線局域網(wǎng)的第一個(gè)版本，僅提供高達(dá)2Mbps的速率，它允許在直接序列或跳頻擴(kuò)頻在2.4 GHz的紅外頻率中使用操作或功能。然而，在IEEE 802.11直接序列擴(kuò)頻修改后的版本中，IEEE 802

3、.11b在2.4gHZ頻段中已提供高速率高達(dá)11Mbps WLAN服務(wù)。最近，高速率無(wú)線局域網(wǎng)標(biāo)準(zhǔn)IEEE新版本802.11a在5 GHz的UNII頻帶可以提供高達(dá)54 Mbps的服務(wù)。WLANs由移動(dòng)電腦與網(wǎng)絡(luò)適配器(NAs)和存取點(diǎn)(APs)連接由具有高速有線局域網(wǎng)接連而構(gòu)成。當(dāng)WLANs被用于室內(nèi)環(huán)境,如在一幢建筑里,其使用一直延伸到室外環(huán)境中的因特網(wǎng)接入服務(wù)，如在校園內(nèi)或在街道上。設(shè)計(jì)無(wú)線局域網(wǎng)的服務(wù)，最重要的事情是要確定接入點(diǎn)應(yīng)設(shè)在哪里，促使覆蓋面和服務(wù)范圍的吞吐量達(dá)到最大化。因此，無(wú)線局域網(wǎng)服務(wù)的設(shè)計(jì)過(guò)程將是由以下步驟.1）需求的地區(qū)的地圖估算：無(wú)線服務(wù)區(qū)將用戶(hù)的需求傳達(dá)給互聯(lián)網(wǎng)服

4、務(wù)提供商（ISP）。然后，互聯(lián)網(wǎng)服務(wù)供應(yīng)商應(yīng)該通過(guò)調(diào)查得出的墻壁或障礙的物理空間中的服務(wù)區(qū)的完整地圖。服務(wù)區(qū)地圖將被劃分為更小的需求點(diǎn)，在那里從AP和用戶(hù)數(shù)量或傳輸需求來(lái)估計(jì)信號(hào)的測(cè)量是。例如，需求點(diǎn)可以是一個(gè)1×1平方米的面積。2）選擇候選AP的位置:由于AP的物理位置可能會(huì)受到限制,要受到連接到有線局域網(wǎng)，電源，安裝和管理費(fèi)用方面的影響，互聯(lián)網(wǎng)服務(wù)供應(yīng)商將選擇候選地點(diǎn)接入點(diǎn)（APS）。3）信號(hào)在服務(wù)方面的需求點(diǎn)測(cè)量：為了提供最大的覆蓋范圍和吞吐量，在每一個(gè)需求點(diǎn)信號(hào)測(cè)量或估計(jì)應(yīng)保證閾值大于最小率。例如，在IEEE802.11b中自動(dòng)速率回退（ARF）的功能是將提供諸如根據(jù)接入點(diǎn)和

5、移動(dòng)計(jì)算機(jī)之間的距離設(shè)置為1/2/5.5/11Mbps不同的速率。此外，由于障礙波將改變信號(hào)的功率，即使有兩個(gè)點(diǎn)位于相同距離AP，信號(hào)功率有可能不同。所以為了提供最大的服務(wù)覆蓋范圍，信號(hào)測(cè)量過(guò)程是很重要的。4）無(wú)信道干擾決定AP：在一般情況下，根據(jù)服務(wù)區(qū)和信號(hào)測(cè)量信息的地圖，互聯(lián)網(wǎng)服務(wù)供應(yīng)商將決定AP的最佳位置，以滿(mǎn)足用戶(hù)的傳輸需求和最低成本的性能指標(biāo)。IEEE802.11b中，如果一個(gè)AP把使用的相同的頻道分配給鄰近的AP，信道干擾無(wú)線局域網(wǎng)的性能會(huì)大幅下降。因此，定義鄰近點(diǎn)應(yīng)該使用不同頻道的最小距離的信道，以避免不同頻道的信道干擾。在決定APs時(shí)，,通常情況下提高WLAN服務(wù)范圍的優(yōu)化目標(biāo)

6、是最大化整個(gè)需求點(diǎn)信號(hào)的總和。5）重新配置接入點(diǎn)和帶反饋信息的渠道：接入點(diǎn)安裝后，互聯(lián)網(wǎng)服務(wù)供應(yīng)商將收集APS和運(yùn)用統(tǒng)計(jì)呼入/呼出每個(gè)AP的流量。為了提高無(wú)線局域網(wǎng)服務(wù)新的AP可能被安裝在擁擠的地方，或者閑置的AP可能會(huì)轉(zhuǎn)移到其他地區(qū)；此外,指定頻道可能重新避開(kāi)干擾。研究表明已經(jīng)有許多研究已在蜂窩網(wǎng)絡(luò)的容量規(guī)劃，但AP在安置和信道分配無(wú)線局域網(wǎng)近期才開(kāi)始起步2。傳統(tǒng)的面向無(wú)線局域網(wǎng)的覆蓋面的設(shè)計(jì)方法只解決如何提供的每一個(gè)無(wú)線服務(wù)區(qū)的最大信號(hào)。在3，覆蓋面為導(dǎo)向的WLAN設(shè)計(jì)問(wèn)題已經(jīng)制定了ILP總和最大化在每個(gè)傳輸需求點(diǎn)出現(xiàn)的信號(hào)。ILP問(wèn)題制定了包括無(wú)信道分配問(wèn)題的信道干擾； 4一般WLAN設(shè)

7、計(jì)方法在大規(guī)模無(wú)線局域網(wǎng)的服務(wù)領(lǐng)域的解釋。同時(shí)5提出優(yōu)化算法，以最大限度地提高覆蓋范圍和整體信號(hào)質(zhì)量。然而，當(dāng)接入點(diǎn)安裝在無(wú)線局域網(wǎng)服務(wù)領(lǐng)域支持的移動(dòng)主機(jī)很多時(shí)，不僅需要考慮覆蓋面，而且接入點(diǎn)之間的負(fù)載平衡也應(yīng)予以考慮，因?yàn)榈幕顒?dòng)主機(jī)連接到AP的數(shù)量會(huì)影響WLAN的網(wǎng)絡(luò)性能。例如，當(dāng)每個(gè)WLAN服務(wù)區(qū)有一個(gè)主機(jī)上有不同的人口流動(dòng)，一個(gè)AP到其中一個(gè)連接可能出現(xiàn)擠塞，而其他鄰近的接入點(diǎn)，移動(dòng)主機(jī)的用戶(hù)很多也沒(méi)有空閑?；镜腎EEE802.11媒體訪問(wèn)機(jī)制稱(chēng)為分布式協(xié)調(diào)功能（DCF），并基于CSMA/CD（載波偵聽(tīng)/沖突檢測(cè)）協(xié)議來(lái)避免沖突。因此，信道的利用率代表著一個(gè)AP在WLAN服務(wù)區(qū)的網(wǎng)絡(luò)性

8、能，帶寬提供給每一個(gè)用戶(hù)將減少了用戶(hù)數(shù)量在一樣的媒介競(jìng)爭(zhēng)的AP6。這個(gè)問(wèn)題在移動(dòng)主機(jī)和動(dòng)態(tài)的用戶(hù)在無(wú)線服務(wù)領(lǐng)域可能經(jīng)常發(fā)生，因此，在無(wú)線局域網(wǎng)接入點(diǎn)應(yīng)安裝應(yīng)使網(wǎng)絡(luò)性能最大化，這樣提供的最大吞吐量被分發(fā)到每個(gè)請(qǐng)求接入點(diǎn)的用戶(hù)。本文中，我們提出了一個(gè)接入點(diǎn)放置在無(wú)線局域網(wǎng)和渠道分配的優(yōu)化方法，以最大限度地減少信道的利用率。本文的其余部分組織如下：第二節(jié)是優(yōu)化AP制定安置的問(wèn)題和對(duì)信道無(wú)線局域網(wǎng)分配進(jìn)行了解釋。第三節(jié)對(duì)其結(jié)果通過(guò)仿真性能評(píng)價(jià)進(jìn)行討論。第四節(jié)解釋了AP的重組方法，第五節(jié)總結(jié)本文。二、AP的布置和信道分配問(wèn)題答：假設(shè)為了簡(jiǎn)化問(wèn)題，我們假設(shè)以下條件有關(guān)的傳輸需求，無(wú)線局域網(wǎng)的服務(wù)領(lǐng)域，AP

9、S。.一個(gè)點(diǎn)集的傳輸需求，Nd：求點(diǎn)定義了一個(gè)無(wú)線局域網(wǎng)服務(wù)范圍測(cè)量信號(hào)來(lái)自于AP,或流量需求的估計(jì)或用戶(hù)歡迎程度。例如，1×1m2代表了傳輸需求點(diǎn)。.每個(gè)傳輸平均需求的體積需求點(diǎn)：摘要:在每個(gè)的需求點(diǎn)、傳輸需求,給出實(shí)測(cè)傳輸量或估算主機(jī)。每一個(gè)需求點(diǎn)都將被指定給一個(gè)AP。.一個(gè)AP的候選點(diǎn)集，Na：候選點(diǎn)集將在這里給出安裝接入點(diǎn)。對(duì)于一個(gè)給定的需求點(diǎn)，候選指定AP的位置點(diǎn)。這樣，每一個(gè)需求點(diǎn)連接到至少一個(gè)AP。最大數(shù)量的APS可以安裝在同一地區(qū)（IEEE 802.11b)，每個(gè)三AP使用同一個(gè)非重疊信道。.信號(hào)矩陣，S = （Sij）：信號(hào)噪比（信噪比）值，sij，其需求點(diǎn)從AP的

10、 i點(diǎn)J點(diǎn)給出。假設(shè)我們產(chǎn)生了一個(gè)AP分配圖和一個(gè)指定的信道，其將在使用過(guò)程中形成的ILP。.AP配圖,G=(N ; E).節(jié)點(diǎn)(N)由一套需求點(diǎn),Nd、一組候選集APs、Na。.如果j（sij）大于閾值i，那么i和其中一個(gè)候選集APs連接在一起。.信道分配圖，ga=（Na;Ea）如果一個(gè)接入點(diǎn)連接在接入點(diǎn)之間的信道存在干擾距離，非重疊信道則會(huì)自動(dòng)分配以確保其性能不會(huì)降低。 一種生成G和Ga舉例圖： 1.該需求點(diǎn)和候選點(diǎn)AP的位置如圖1-(a)所示。通過(guò)連接每一個(gè)點(diǎn)的業(yè)務(wù)需求APs的距離內(nèi)信號(hào)接入點(diǎn)，我們產(chǎn)生一個(gè)AP分配圖G（圖1 -（b）。另外，信道分配圖Ga（圖1 (c)），其是通過(guò)連接A

11、Ps與信道干擾間的距離來(lái)創(chuàng)建的。二、問(wèn)題描述 根據(jù)不同的問(wèn)題設(shè)計(jì)WLAN服務(wù)在每個(gè)區(qū)域的用戶(hù)密度是找到最佳位置的APS與非重疊信道可用帶寬，這樣在每個(gè)WLAN服務(wù)領(lǐng)域中達(dá)到覆蓋范圍的最大化。 在本小節(jié)，我們?cè)跐M(mǎn)足業(yè)務(wù)需求下制定最小化問(wèn)題信道的利用率最高的AP。 根據(jù)此前的問(wèn)題制定，定義變量和常量:xij：二進(jìn)制變量，如果點(diǎn)i被分配到AP j為1，否則為0。 cki：二進(jìn)制變量，如果k信道分配到AP i為1，否則為0。 Bj：APj提供的最大帶寬（如在IEEE 802.11b的11 Mbps）。雖然容量在APj的信道將被定義為一個(gè)函數(shù)用戶(hù)和他們的聯(lián)系，但在本文中，該恒定帶寬是由每個(gè)AP的一條信道

12、提供的簡(jiǎn)化問(wèn)題制定方案。aj:二進(jìn)制變量,如果AP j被選中則為1,否則返回0。K:一組可用的信道。最大信道利用率。這個(gè)度量指標(biāo)代表分配到APs的最大的業(yè)務(wù)負(fù)荷,這是實(shí)際衡量無(wú)線局域網(wǎng)網(wǎng)絡(luò)性能,它解釋了定性擁擠網(wǎng)絡(luò)服務(wù)的領(lǐng)域。AP配置的ILP規(guī)劃和信道分配的問(wèn)題應(yīng)考慮業(yè)務(wù)需求：其被定義為擴(kuò)展傳統(tǒng)的拓?fù)湓O(shè)計(jì)問(wèn)題，如下：其目的（1）是盡量減少每個(gè)信道的最大利用。限制（2）狀態(tài)的每個(gè)需求點(diǎn)應(yīng)該被分配到一個(gè)AP。限制（3）條件需求點(diǎn)的總流量的需求應(yīng)比無(wú)線鏈路由AP提供的帶寬小。 限制（4）如果需求點(diǎn)i是與APj的連接則表示APj被選擇。限制（5）表明一個(gè)信道應(yīng)分配給所選的AP。限制（6）描述用最小的非

13、重疊信道條件與信道的距離。 除了盡量減少信道的利用率，優(yōu)化目標(biāo)可能是減少APs的數(shù)量為最低成本( )或APS的總和最大化信號(hào)功率（）。三、績(jī)效評(píng)估 A：運(yùn)行環(huán)境 我們使用CPLEX解決ILP制定的問(wèn)題。 對(duì)于ARF功能，我們假設(shè)有11，5.5，2和1 Mbps的帶寬建立連接， 當(dāng)移動(dòng)主機(jī)和小于160，270，400的AP的距離為550米，該頻道干擾距離設(shè)置為550米每用戶(hù)平均業(yè)務(wù)需求假設(shè)高達(dá)200 Kbps時(shí)，以及每個(gè)需求點(diǎn)的用戶(hù)數(shù)量是隨機(jī)分布在1和10。在業(yè)務(wù)需求需求點(diǎn)為用戶(hù)數(shù)量x平均每個(gè)用戶(hù)的傳輸需求。 B:網(wǎng)絡(luò)的一個(gè)案例 在圖示1中，我們找到了一組選定的APs和他們的信道減少的目標(biāo)信道的

14、利用率最高時(shí)有多少APs。 表一表明，伴隨最小化的目標(biāo)值a，在五個(gè)已選擇APs中最高的信道利用率是1.64。然而，AP的數(shù)量可減少到四個(gè)，盡量減少與使用的APS數(shù)量,增漲目標(biāo)值a(2.36）。如果xij變量是真實(shí)的，即在每個(gè)需求點(diǎn)移動(dòng)主機(jī)可以選擇不同的AP，從而優(yōu)化業(yè)務(wù)需求并分配給APs，使得最高信道利用率（1.36）減小。表I 這個(gè)例子的結(jié)果（其結(jié)果與xij的真值）C 隨機(jī)拓?fù)?由于很難獲得有關(guān)的大規(guī)模營(yíng)銷(xiāo)的WLAN服務(wù)區(qū)域環(huán)境的所有信息，如需求點(diǎn)，用戶(hù)區(qū)域環(huán)境普及，信號(hào)測(cè)量，業(yè)務(wù)需求預(yù)測(cè)，為了核查其方法，我們使用了一種普遍的網(wǎng)絡(luò)拓?fù)?。為了調(diào)查網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的總體性能 ，我們?cè)?00 x200

15、隨機(jī)產(chǎn)生的需求點(diǎn)和AP點(diǎn),其中每個(gè)網(wǎng)格代表10x10平方米面積單位。在圖2中，我們可以看到了由于業(yè)務(wù)需求候選接入點(diǎn)的數(shù)量增加，APs數(shù)量增加，a卻降低了。 而圖3可以看出，信道干擾不能使業(yè)務(wù)需求變高，選取最好的AP的設(shè)置的大小。例如，業(yè)務(wù)要求點(diǎn)明顯高于40APs的需求數(shù)大約為13。因此，其可以節(jié)省安裝和管理，提供互聯(lián)網(wǎng)服務(wù)供應(yīng)商最優(yōu)配置成本的方法。四、重構(gòu)在一般情況下，由于它比有線局域網(wǎng)用戶(hù)的移動(dòng)性，無(wú)線局域網(wǎng)的傳輸需求格局將更具活力，因此，在無(wú)線局域網(wǎng)接入點(diǎn)在整個(gè)服務(wù)區(qū)安裝后，根據(jù)動(dòng)態(tài)變化的傳輸需求重新配置無(wú)線AP這是必要的。在重組過(guò)程中，AP和他們的渠道可能會(huì)改變，這將導(dǎo)致用戶(hù)的傳輸中斷，

16、在本節(jié)中，我們提出了一個(gè)以盡量減少對(duì)傳輸?shù)男枨笾袛鄳?yīng)付新的AP分配到需求點(diǎn)的目標(biāo)AP的重組方法，雖然它比原來(lái)的保持AP配置少。其問(wèn)題的解決過(guò)程如圖4所示。當(dāng)原來(lái)的流量矩陣Ti改為T(mén)j，我們首先解決了新的傳輸需求矩陣Ti得到最優(yōu)值的問(wèn)題。然后，我們找到了新的傳輸需求矩陣解，Ti是AP的設(shè)置和最大限度減少流量的關(guān)聯(lián)點(diǎn)，然而最大的信道利用率小于。圖。 4。重構(gòu)問(wèn)題的解決過(guò)程讓將需求點(diǎn)i處的流量分配到APj。重構(gòu)問(wèn)題函數(shù)給出如下：公式7是為為了減少需求點(diǎn)AP的新任務(wù)的流量，在公式9，設(shè)置為一個(gè)新的傳輸需求固定的最大信道的利用率。公式10描述了新的AP任務(wù)變量與舊的之間的區(qū)別。例如，當(dāng)傳輸需求是隨機(jī)矩陣在100的最大偏差值變化，傳輸需求矩陣的最佳值是0.86。但是，如果用老的AP需求矩陣，變成了1.07。然后，通過(guò)盡量減少改變傳輸流的數(shù)量（=2.9）優(yōu)化步驟，我們發(fā)現(xiàn)AP和需求點(diǎn)的關(guān)聯(lián)度達(dá)到了滿(mǎn)意的0.86。五，結(jié)論在本