陶雯，沈艷，管昕潔，萬夕里

（1．江蘇第二師范學(xué)院數(shù)學(xué)與信息技術(shù)學(xué)院，江蘇 南京 210013；2．南京工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，江蘇 南京 211816）

基于圖轉(zhuǎn)換的無線接入點關(guān)聯(lián)優(yōu)化算法

陶雯1，沈艷2，管昕潔2，萬夕里2

（1．江蘇第二師范學(xué)院數(shù)學(xué)與信息技術(shù)學(xué)院，江蘇 南京 210013；2．南京工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，江蘇 南京 211816）

無線接入點關(guān)聯(lián)是 Wi-Fi系統(tǒng)中的一個基礎(chǔ)問題。已有的研究主要集中在考慮帶寬容量約束條件下的各種AP關(guān)聯(lián)問題。這些研究沒有從用戶的角度考慮帶寬需求，從用戶的帶寬需求出發(fā)，以最多帶寬分配的AP關(guān)聯(lián)為優(yōu)化目標(biāo)，考慮混合型網(wǎng)絡(luò)架構(gòu)下的Wi-Fi系統(tǒng)的無線接入點關(guān)聯(lián)優(yōu)化問題。與已有研究方法不同，通過圖轉(zhuǎn)換技術(shù)，并將問題轉(zhuǎn)化為流圖上的優(yōu)化問題，提出基于網(wǎng)絡(luò)流的優(yōu)化求解算法，并從理論上證明算法的最優(yōu)性。最后，通過對比實驗進一步證明了算法的優(yōu)越性。

無線接入；圖轉(zhuǎn)換；接入點關(guān)聯(lián)

1 引言

IEEE 802.11技術(shù)（通常稱為Wi-Fi）因其具有高帶寬、低成本等優(yōu)勢，隨著社會的發(fā)展，基于IEEE 802.11協(xié)議系列的無線局域網(wǎng)已在校園、工廠等各種場景下不斷得到部署。智能設(shè)備的普及更進一步推動了 Wi-Fi的普及，并深入人們的生活和工作的各個方面。在企業(yè)層面，面向不同應(yīng)用的 Wi-Fi應(yīng)用系統(tǒng)不斷被推出。盡管 Wi-Fi技術(shù)有著很多優(yōu)點，隨著其大規(guī)模的應(yīng)用，其本身也面臨很多技術(shù)上的挑戰(zhàn)，如帶寬優(yōu)化、接入點的最優(yōu)放置等問題。在這些挑戰(zhàn)中，如何在給定 Wi-Fi系統(tǒng)資源的前提下，使得系統(tǒng)能夠服務(wù)更多用戶是實際應(yīng)用中經(jīng)?？紤]的一個重要問題。對該問題的深入研究，可以進一步提高Wi-Fi系統(tǒng)在實際應(yīng)用的利用效率。

近年來，隨著Wi-Fi的不斷普及，Wi-Fi在企業(yè)級別也有了廣泛的應(yīng)用。如在機場、校園校區(qū)、商場等規(guī)模較大的公共區(qū)域，Wi-Fi基本實現(xiàn)全覆蓋。在這類型的Wi-Fi系統(tǒng)中，多個AP通過高速有線網(wǎng)絡(luò)連接到中央控制節(jié)點，這種混合型結(jié)構(gòu)一般被稱為半集中式結(jié)構(gòu)[1]。在這種混合型結(jié)構(gòu)下，多個 AP之間可以通過骨干有線網(wǎng)絡(luò)來分享接入設(shè)備相關(guān)信息，這使得系統(tǒng)可以及時集中收集當(dāng)前在各個 AP信號范圍內(nèi)的用戶信息，使得中央控制節(jié)點擁有全局視圖，為設(shè)計 Wi-Fi資源分配提供有利條件。

本文將研究在這一混合型架構(gòu)下的 Wi-Fi中最大帶寬分配的AP關(guān)聯(lián)問題。已有一些研究[1-3]探討了該AP關(guān)聯(lián)問題。這些研究主要研究在帶寬容量約束條件下，如何尋求帶寬分配最多的一種AP關(guān)聯(lián)方案。但這些研究并沒有考慮到用戶的帶寬需求，隨著移動互聯(lián)網(wǎng)的發(fā)展，為了獲得更好的用戶網(wǎng)絡(luò)體驗，如上網(wǎng)、打游戲以及看視頻等，用戶對所分配到的帶寬有著一定的要求?；诖耍疚目紤]從用戶帶寬需求出發(fā)，研究該需求下的最大帶寬分配的AP關(guān)聯(lián)優(yōu)化問題。參考文獻[1]首先考慮了該問題，研究了單元帶寬需求下的最大帶寬分配的 AP關(guān)聯(lián)優(yōu)化，給出一個貪婪啟發(fā)式算法來求解該問題，但該算法并不能求得該問題的最優(yōu)解。已有的關(guān)于帶寬分配的 AP關(guān)聯(lián)問題基本都是 NP難問題，而且主要是應(yīng)用線性、非線性規(guī)劃等相關(guān)方法來設(shè)計啟發(fā)式算法或者近似算法。與已有研究的方法不同，本文提出用圖的優(yōu)化理論來解決此類問題，并探討在某些條件下存在最優(yōu)解的可能性。本文給出了在每個設(shè)備需求是單元帶寬的假設(shè)下，在基于圖的最優(yōu)化網(wǎng)絡(luò)流理論基礎(chǔ)上，發(fā)現(xiàn)最大帶寬分配的 AP關(guān)聯(lián)優(yōu)化存在最優(yōu)解，理論證明和實驗結(jié)果也進一步驗證了該算法的正確性。

2 相關(guān)工作

隨著當(dāng)前接入 Wi-Fi用戶數(shù)目大量增長以及多層次結(jié)構(gòu)的 Wi-Fi系統(tǒng)的部署，提升系統(tǒng)利用效率和接納更多用戶請求的問題越發(fā)具有挑戰(zhàn)性。為解決此問題，學(xué)術(shù)界提出了各種場景下，面向不同優(yōu)化目標(biāo)的資源調(diào)度和分配關(guān)聯(lián)算法。參考文獻[1]提出了面向帶寬分配的 AP關(guān)聯(lián)分配算法。參考文獻[2]建模 AP關(guān)聯(lián)問題，并考慮負(fù)載均衡因素，通過松弛和取整的方法，設(shè)計了一個具有常數(shù)倍逼近度的分配算法。參考文獻[4]提出了基于最少負(fù)載優(yōu)先設(shè)備關(guān)聯(lián)的啟發(fā)式算法，也就是設(shè)備優(yōu)先選擇負(fù)載最小的 AP接入。參考文獻[5]考慮了 AP可以再關(guān)聯(lián)的優(yōu)化問題，提出了在遷徙約束條件下的面向最大吞吐量的優(yōu)化算法。參考文獻[6]提出了基于可用容量的負(fù)載均衡的AP關(guān)聯(lián)算法。

其他學(xué)者從均衡用戶分配的資源的思路出發(fā)，提出了多種關(guān)聯(lián)算法。參考文獻[3]研究了多種異構(gòu)客戶場景（IEEE 802.11a/b/g/n）下，通過二維馬爾可夫模型預(yù)測設(shè)備的上下行吞吐量，在此基礎(chǔ)上，以提高 MAC效率為目標(biāo)，考慮平衡帶寬和速率，建模在線 AP關(guān)聯(lián)問題并提出一種在線 AP關(guān)聯(lián)方法。參考文獻[7]考慮了單個設(shè)備可關(guān)聯(lián)多個 AP的情況，并提出最優(yōu)的面向多個AP傳輸速率策略，并從理論上證明該算法的逼近度為4+∈。參考文獻[8]提出了度量驅(qū)動的WLAN設(shè)計原則，并以此為指導(dǎo)優(yōu)化信道分配、AP關(guān)聯(lián)和AP功率控制等。參考文獻[9, 10]研究了在軟件定義的WLAN框架下的AP關(guān)聯(lián)問題，考慮了幀延遲、數(shù)據(jù)分組丟失等多種因素，提出面向服務(wù)質(zhì)量保證的AP關(guān)聯(lián)方法。參考文獻[11]提出集中式的AP關(guān)聯(lián)策略模型，并應(yīng)用蟻群算法求解AP關(guān)聯(lián)解。

3 網(wǎng)絡(luò)模型與問題描述

3.1 網(wǎng)絡(luò)模型與定義

圖1 3個AP和4個移動設(shè)備

假設(shè) APi的帶寬容量為 Ci，并且任何移動設(shè)備只需要 AP能滿足其最小的帶寬即可關(guān)聯(lián)該AP。定義Li為第i個AP的負(fù)載。為了方便，與已有研究一樣[1]，本文假設(shè)每個移動設(shè)備只需要候選AP滿足1個單元的帶寬要求，即可關(guān)聯(lián)該AP。因此，第APi的負(fù)載Li為該AP關(guān)聯(lián)的移動設(shè)備的數(shù)目，而每個 APi的容量 Ci則為該APi能關(guān)聯(lián)的移動設(shè)備最大數(shù)目。因此，在此假設(shè)下，最終所有關(guān)聯(lián)上的設(shè)備所獲得的總帶寬與設(shè)備總的連接數(shù)等價。

如果設(shè)備dj關(guān)聯(lián)到APi，定義aij=1，否則aij=0。此外，本文也用 〈uj,vi〉 配對來表示設(shè)備j關(guān)聯(lián)到APi。

3.2 問題描述

定義1（最大AP關(guān)聯(lián)問題）給定一個混合型Wi-Fi網(wǎng)絡(luò)，該網(wǎng)絡(luò)有n個AP節(jié)點和m個移動設(shè)備節(jié)點。假設(shè)每個移動設(shè)備候選的AP節(jié)點是已知的，最大AP關(guān)聯(lián)問題就是求解一種AP關(guān)聯(lián)算法使得最終網(wǎng)絡(luò)中AP所關(guān)聯(lián)的設(shè)備數(shù)目最多。

圖2 圖1對應(yīng)的流圖G′

定義3如果一個AP關(guān)聯(lián)方案滿足式（2）、式（3），則稱該關(guān)聯(lián)方案為最大 AP關(guān)聯(lián)問題的可行解。

4 算法設(shè)計與分析

本節(jié)給出求解最大關(guān)聯(lián)問題的最優(yōu)算法以及相關(guān)最優(yōu)性的證明和分析。該算法的思路是將該AP關(guān)聯(lián)問題轉(zhuǎn)化為圖上的優(yōu)化問題，從而應(yīng)用圖的優(yōu)化理論來求解最優(yōu)解。首先將最大 AP關(guān)聯(lián)問題轉(zhuǎn)化為二分圖上的優(yōu)化問題，然后給出優(yōu)化算法來求解該優(yōu)化問題。

值得注意的是，本文中的最大AP關(guān)聯(lián)問題不能采用經(jīng)典的二分匹配算法來求解，因為對于每一個AP節(jié)點（即二分圖中U中的節(jié)點）是可以關(guān)聯(lián)多于一個的移動設(shè)備（即二分圖中V中的一個節(jié)點），而二分匹配問題中 U有且僅能與 V中一個節(jié)點匹配。未解決此問題，本文提出一種圖轉(zhuǎn)換方法，將最大AP關(guān)聯(lián)優(yōu)化問題轉(zhuǎn)化為對應(yīng)的圖優(yōu)化問題，從而可以應(yīng)用網(wǎng)絡(luò)流優(yōu)化算法取得最優(yōu)解。

4.1 基于網(wǎng)絡(luò)流的AP關(guān)聯(lián)算法

首先本文給出如何構(gòu)造最大 AP關(guān)聯(lián)問題二分圖：創(chuàng)建一個二分圖，對每個APi節(jié)點和移動設(shè)備dj，分別在U和D中創(chuàng)建一個節(jié)點i和j。如果移動設(shè)備j在APi的覆蓋范圍內(nèi)，也就是APi是移動設(shè)備dj的候選節(jié)點，則在E中創(chuàng)建一條從i 到j(luò)的有向邊(i, j)，并設(shè)置(i, j)的權(quán)重為

下面給出基于網(wǎng)絡(luò)流的最大AP關(guān)聯(lián)算法。

算法1 基于網(wǎng)絡(luò)流的AP關(guān)聯(lián)算法

輸入：AP集合U，移動設(shè)備集合U，每個移動設(shè)備的候選AP集合。

輸出：一組移動設(shè)備關(guān)聯(lián)AP的解＜aij＞。

步驟2在G的基礎(chǔ)上建立流圖G'（如圖2所示），在上額外添加一個虛擬源點S和終點T，對U中的每個頂點i，連接源點S與頂點i形成有向邊(S, i)，設(shè)置該邊的權(quán)重為Ci；對V中頂點j，連接j與終點T形成有向邊 (j,T) ，并設(shè)置該邊的權(quán)重為W(j,T)=1。

步驟 3應(yīng)用經(jīng)典最大網(wǎng)絡(luò)流 Push-Relabel算法[14,15]在新構(gòu)造的流圖G'上，求解出G'上的最大流 f'。用表示最大流解f'在邊(i, j)最大流。

步驟4如果則賦值aij=1，即將移動設(shè)備dj關(guān)聯(lián)到APi。

4.2 算法分析

引理1在圖2中，若所求得的從源點S到終點T 的最大流經(jīng)過邊則該邊對應(yīng)的最大流必定為1，即

證明：根據(jù)網(wǎng)絡(luò)流整數(shù)流性質(zhì)[12]，如果網(wǎng)絡(luò)中所有邊的權(quán)重（或者容量）為整數(shù)，則該網(wǎng)絡(luò)的最大流一定為整數(shù)流。算法1中所構(gòu)造的流圖G'的邊的權(quán)重均為整數(shù)，因此最大流經(jīng)過一定是整數(shù)。又因為(ui, dj)邊的權(quán)重均為 1，所以(ui, dj） 若有最大流經(jīng)過，其最大流必定為1，即

引理2對于任何dj∈D節(jié)點，若一個從源點 S到終點 T 的流經(jīng)過該節(jié)點，則

證明：對于任何dj∈D 節(jié)點, 因為 (dj,T)的權(quán)重為 1，根據(jù)網(wǎng)絡(luò)流平衡性質(zhì)[13]，任何流入 dj的流的總和一定為1，因此引理得證。

定理1如果有一個可行性解Γ中，有k個移動設(shè)備與APi節(jié)點關(guān)聯(lián)，則對應(yīng)流圖G'上存在一個從源點S到終點t的流，且該流值為k。反之亦成立。

證明：一個可行解Γ中有k個移動設(shè)備與APi關(guān)聯(lián)，則在流圖G'上可以存在k條邊的流值為1。因為源點S與每個ui相連，并且每個dj與終點T相連，根據(jù)網(wǎng)絡(luò)流平衡性質(zhì)[13]，必定存在從源點S到終點T的流f，且f通過這k條邊，且該流值為f( s, t)。又因為可行解Γ滿足式（2），也就是可行解滿足每個 AP的容量約束條件，而邊上的權(quán)重則對應(yīng)AP 的容量，因此，該流f一定滿足流圖G'上的權(quán)重限制條件。

反之，對于一個流值為k的從源點S到終點T的流值f( s, t)，結(jié)合引理1和引理2，可知對于任何dj∈D節(jié)點，只有一條從ui∈D出發(fā)的邊的流經(jīng)過 dj，且 f( ui, dj)=1。因為 f(s,t)=k，根據(jù)流平衡性質(zhì)，則必定有k條(ui, dj)邊的流值為1。也就是有k條 f( ui, dj) =1，對應(yīng)于k個移動設(shè)備與AP節(jié)點關(guān)聯(lián)的方案，并且該方案滿足式（3）。又因為(s, ui)邊的權(quán)重對應(yīng)于AP的容量約束，所以該關(guān)聯(lián)方案滿足式（2），因此該關(guān)聯(lián)方案是一個有k個移動設(shè)備被關(guān)聯(lián)的可行解。

定理 2最大 AP關(guān)聯(lián)問題可以轉(zhuǎn)化為流圖G'上的最大網(wǎng)絡(luò)流問題。

證明：定理1揭示了單個AP關(guān)聯(lián)問題的可行解與流圖G'上的單源單匯流一一對應(yīng)關(guān)系，并且可行解的值對應(yīng)于圖G'的流值。值得注意的是，最大AP關(guān)聯(lián)問題的解是由一系列可行解構(gòu)成，且最大帶寬AP關(guān)聯(lián)問題的設(shè)備連接數(shù)值是這些可行解相應(yīng)的設(shè)備連接數(shù)值之和。從而，最大AP關(guān)聯(lián)問題的解值（設(shè)備連接數(shù)目）對應(yīng)于流圖G'上的所有的單源單匯流值之和，也就是對應(yīng)于流圖G'上的從源點S出發(fā)到終點T的網(wǎng)絡(luò)流。因此，最大AP關(guān)聯(lián)問題解的最大值對應(yīng)流圖G'上的最大網(wǎng)絡(luò)流。定理3最大AP關(guān)聯(lián)問題可以在時間內(nèi)求的最優(yōu)解。

證明：算法1的復(fù)雜度是由最大網(wǎng)絡(luò)流算法主導(dǎo)，因此網(wǎng)絡(luò)流算法的復(fù)雜度決定了算法1的復(fù)雜度。如果采用經(jīng)典的Push-Relabel算法[14,15]，則算法1復(fù)雜度為中，r為流圖G'中節(jié)點的個數(shù)。因此算法1的復(fù)雜度為

4.3 示例

本節(jié)給出一個示例來演示算法 1。針對圖 1中的部署場景，假定每個AP的容量為2，也就是根據(jù)算法步驟1和步驟2，可以得到圖2中的流圖G'。在圖2中，分別對應(yīng)于3個AP，則對應(yīng)于4個移動設(shè)備。G'中依附在邊上的數(shù)值對應(yīng)于邊的權(quán)重，其中對每個其他邊的權(quán)重均為1。

應(yīng)用最大網(wǎng)絡(luò)流算法，可求得該流圖G'的最大流f =4，如圖3所示，加粗的邊為網(wǎng)絡(luò)最大流經(jīng)過的邊，依附在邊上加粗的數(shù)字則表示最大流經(jīng)過該邊的流值，如邊(s, u1)的流的值為2，也就是根據(jù)算法1的步驟4，任何邊上流的值為1，則關(guān)聯(lián)APi和移動設(shè)備dj。因此，從最大流流經(jīng)邊的結(jié)果可以得到：AP1與移動設(shè)備d1和d2關(guān)聯(lián)，AP2和移動設(shè)備d3關(guān)聯(lián)， AP3和移動設(shè)備d4關(guān)聯(lián)。

圖3 圖2對應(yīng)的流圖G′的最大網(wǎng)絡(luò)流

5 實驗與分析

5.1 實驗參數(shù)設(shè)置

為進一步驗證本文所提算法的性能，通過實驗與參考文獻[1]中提出的貪婪算法對比，通過對AP的關(guān)聯(lián)設(shè)備數(shù)目、AP關(guān)聯(lián)數(shù)目的分布以及AP的利用率對比，對算法性能進行實驗分析和評估。

實驗中有n個AP節(jié)點，m個移動設(shè)備。每個AP節(jié)點的容量是C，實驗中假設(shè)每個AP節(jié)點的帶寬容量相同。本實驗通過 AP關(guān)聯(lián)移動設(shè)備數(shù)目來判斷本文所提出的算法的有效性和合理性。

為了更全面地突出本文算法的有效性，從以下幾個方面進行了仿真實驗。

（1）固定AP節(jié)點的數(shù)量為5，且每個AP節(jié)點的帶寬容量為5，設(shè)置不同的移動設(shè)備數(shù)量，分別為10、15、20，隨機運行10次，比較本文算法與貪婪算法的實驗結(jié)果。

（2）固定移動設(shè)備數(shù)為10，每個AP節(jié)點的帶寬容量為5，設(shè)置不同的AP節(jié)點數(shù)，分別為5、6、7，隨機運行10次，將本文提出的算法與貪婪算法進行比較。

（3）固定AP節(jié)點數(shù)量為5，且每個AP節(jié)點的帶寬容量為5，改變移動設(shè)備的數(shù)量，分別為5、10、15、20、25、30、35、40、45、50，比較這兩個算法的結(jié)果。

（4）固定AP節(jié)點數(shù)為6，設(shè)置不同的AP節(jié)點的帶寬容量，分別為5、6、7，隨著移動設(shè)備逐次增加的情況下（移動設(shè)備數(shù)量分別為5、10、15、20、25、30、35、40、45、50），比較本文提出的算法與貪婪算法的實驗結(jié)果。

（5）比較兩算法在3種不同的 AP節(jié)點數(shù)和移動設(shè)備數(shù)的條件下，AP節(jié)點與移動設(shè)備連接分布情況。

（6）在AP節(jié)點數(shù)為5，容量為5的條件下，隨著移動設(shè)備數(shù)量逐次增加，對兩個算法中 AP節(jié)點的利用率進行了比較。

5.2 實驗結(jié)果

根據(jù)要求設(shè)置參數(shù)，進行仿真實驗。在實驗中將本文的優(yōu)化算法與已有的貪婪算法進行比較。針對本文求最大AP聯(lián)結(jié)數(shù)的問題，使用貪婪算法將其分成每個AP節(jié)點盡可能多地連接移動設(shè)備的子問題。在給定的一個部署場景中，將每個AP節(jié)點與移動設(shè)備連接的數(shù)量按降序排列，在確保每個移動設(shè)備只連接一個AP節(jié)點的條件下，按之前排列的順序依次留下原部署場景中的AP節(jié)點與移動設(shè)備的連接狀態(tài)，最后計算得到AP聯(lián)結(jié)數(shù)。

本文首先設(shè)置AP節(jié)點的數(shù)量為5，每個AP節(jié)點的容量為5。然后，設(shè)置不同的移動設(shè)備數(shù)量，分別運行基于網(wǎng)絡(luò)流的AP關(guān)聯(lián)算法和貪婪算法。運行10次，并且將每次這兩個算法生成的AP關(guān)聯(lián)設(shè)備的數(shù)目進行比較。圖4給出了當(dāng)移動設(shè)備數(shù)量為10、15、20時的比較結(jié)果，可以看出，使用基于網(wǎng)絡(luò)流AP關(guān)聯(lián)算法得到的AP關(guān)聯(lián)數(shù)普遍高于貪婪算法。

圖4 AP節(jié)點數(shù)為5，不同移動設(shè)備數(shù)量下運行10次的AP關(guān)聯(lián)數(shù)

接下來，設(shè)置移動設(shè)備數(shù)量為10，每一個AP節(jié)點的容量為5，對不同數(shù)量的AP節(jié)點分別運行基于網(wǎng)絡(luò)流 AP關(guān)聯(lián)算法和貪婪算法，每一組實驗運行10次，對兩個算法生成的AP關(guān)聯(lián)設(shè)備的數(shù)目進行比較。圖5給出了AP節(jié)點數(shù)為5、6、7時的比較結(jié)果。從圖5可以看出，基于網(wǎng)絡(luò)流AP關(guān)聯(lián)算法生成的 AP關(guān)聯(lián)設(shè)備的數(shù)目總是大于貪婪算法的，且大多數(shù)時候是遠(yuǎn)大于貪婪算法的。這個結(jié)果與本文算法結(jié)論一致，有效驗證了本文算法的性能高于貪婪算法性能。

圖5 移動設(shè)備數(shù)為10、AP節(jié)點數(shù)不同時運行10次的AP關(guān)聯(lián)數(shù)

為了更進一步驗證本文算法的有效性，還進行了如下實驗，設(shè)置AP節(jié)點數(shù)為5，且每個AP節(jié)點的容量為 5，移動設(shè)備數(shù)量依次為 5、10、15、20、25、30、35、40、45、50，分別觀察兩種算法運行下生成的 AP關(guān)聯(lián)設(shè)備的數(shù)目，結(jié)果如圖6所示?？梢钥吹?，在相同的AP數(shù)量和移動設(shè)備數(shù)量下，基于網(wǎng)絡(luò)流 AP關(guān)聯(lián)算法得到的AP關(guān)聯(lián)數(shù)始終大于貪婪算法得到的AP關(guān)聯(lián)數(shù)，如此進一步驗證了所提算法更為有效性。

另外，還改變 AP節(jié)點的容量值進行兩個算法的對比實驗。實驗中設(shè)置AP節(jié)點的數(shù)量為6。然后設(shè)置不同的 AP節(jié)點容量，分別運行基于網(wǎng)絡(luò)流AP關(guān)聯(lián)算法和貪婪算法，在移動設(shè)備數(shù)量逐次增加的情況下比較兩種算法生成的 AP關(guān)聯(lián)設(shè)備的數(shù)目。圖7給出了當(dāng)AP節(jié)點容量為5、6、7時的比較結(jié)果。可以看到，在 AP節(jié)點數(shù)為6，且移動設(shè)備數(shù)量相同的時候，基于網(wǎng)絡(luò)流AP關(guān)聯(lián)算法得到的AP聯(lián)結(jié)數(shù)大多數(shù)時候大于貪婪算法得到的AP聯(lián)結(jié)數(shù)。另外還可以發(fā)現(xiàn)，在同一場景部署下，當(dāng)該環(huán)境中的AP節(jié)點容量增大時，本文所提出的算法的性能明顯優(yōu)于貪婪算法。

圖6 AP節(jié)點數(shù)為5，隨著移動設(shè)備數(shù)量增加生成的AP關(guān)聯(lián)數(shù)

圖7 AP節(jié)點數(shù)量為6時，不同容量下隨著移動設(shè)備數(shù)量增加生成的AP關(guān)聯(lián)數(shù)

接下來，分別運行基于網(wǎng)絡(luò)流AP關(guān)聯(lián)算法和貪婪算法，比較3種不同的AP節(jié)點數(shù)和移動設(shè)備數(shù)的條件下 AP節(jié)點與移動設(shè)備連接分布情況。圖8給出了AP節(jié)點數(shù)為5，且每個AP節(jié)點的容量為5，移動設(shè)備數(shù)為10的情況下，AP連接數(shù)的分布情況。從圖8中可以看出，在基于網(wǎng)絡(luò)流AP關(guān)聯(lián)算法中每個AP節(jié)點都連接著相應(yīng)數(shù)量的移動設(shè)備，而貪婪算法下第 3個AP節(jié)點、第4個AP節(jié)點和第5個AP節(jié)點都沒有與移動設(shè)備相連接。所以很明顯地得出本文提出的算法更為有效。另外，本文還分別進行了AP節(jié)點數(shù)為6，且每個AP節(jié)點的容量為5，移動設(shè)備數(shù)為15和AP節(jié)點數(shù)為7，且每個AP節(jié)點的容量為5，移動設(shè)備數(shù)為20的實驗。結(jié)果分別顯示在圖9和圖10中。結(jié)果與上述結(jié)論保持一致。

圖8 AP節(jié)點數(shù)為5，移動設(shè)備數(shù)為10的AP連接數(shù)分布

圖9 AP節(jié)點數(shù)為6，移動設(shè)備數(shù)為15的AP連接數(shù)分布

此外，本文還對兩個算法中AP節(jié)點的利用率進行了比較。圖11給出了AP節(jié)點為5，且每個 AP節(jié)點的容量為5，移動設(shè)備數(shù)量逐量遞增的條件下兩算法中AP 節(jié)點的利用率情況。可以看出，基于網(wǎng)絡(luò)流的AP關(guān)聯(lián)算法下所得到的AP利用率一直高于貪婪算法，而且大部分情況下，AP利用率為100%。由此可以看出，本文提出的算法在AP利用情況上比貪婪算法更為高效。

圖10 AP節(jié)點數(shù)為7，移動設(shè)備數(shù)為20的AP連接數(shù)分布

圖11 AP節(jié)點數(shù)量為5，容量為5時隨著移動設(shè)備數(shù)量增加生成的AP利用率

6 結(jié)束語

本文提出了在混合型架構(gòu)下的一種面向最大連接數(shù)的AP關(guān)聯(lián)算法。與已有AP關(guān)聯(lián)方法不同，本文應(yīng)用圖優(yōu)化方法來設(shè)計 AP關(guān)聯(lián)算法，提出圖轉(zhuǎn)換技術(shù)，設(shè)計流圖，將該 AP關(guān)聯(lián)優(yōu)化問題轉(zhuǎn)化為流圖上網(wǎng)絡(luò)流優(yōu)化問題，并從理論上證明了兩個問題的等價性。在此基礎(chǔ)上，應(yīng)用網(wǎng)絡(luò)流算法，提出基于網(wǎng)絡(luò)流算法的最優(yōu)AP關(guān)聯(lián)算法。通過仿真實驗，驗證了該算法的有效性。

[1] DANDAPAT S K, MITRA B, CHOUDHURY R R, et al. Smart association control in wireless mobile environment using max-flow[J]. IEEE Transactions on Network and Service Man-agement, 2012, 9(1): 73-86.

[2] BEJERANO S J Y, HAN S J，LI L E. Fairness and load balancing in wireless LAN using association control[M]. New Jersey: IEEE Press, 2007: 560-573.

[3] GONG D, YANG Y. On-line AP association algorithms for 802.11n WLANs with heterogeneous clients [J]. IEEE Transactions on Computers, 2014, 63(11): 2772-2786.

[4] GONG H, KIM J. Dynamic load balancing through association control of mobile users in Wi-Fi networks[J]. IEEE Transactions on Consumer Electronics, 2008, 54(2): 342-348.

[5] WONG W. THAKUR A, CHAN S H G. An approximation algorithm for AP association under user migration cost constraint[C]//The 35th Annual IEEE International Conference on Computer Communications, April 10-15, 2016, San Francisco,USA. New Jersey: IEEE Press, 2016: 56-62.

[6] MURTY R , PADHYE J, CHANDRA R, et al. Designing high performance enterprise Wi-Fi networks[C]//The 5th USENIX Symposium on Networked Systems Design and Implementation,Alaska, USA, 2008: 342-349.

[7] ABUSUBAIH M, WOLISZ A. An optimal station association policy for multi-rate IEEE 802.11 wireless Lans [C]//The 10th ACM Symposium on Modeling, Analysis, and Simulation of Wireless and Mobile Systems, October 22-26, 2007, Chania,Crete Island, Greece. New York: ACM Press, 2007: 34-40.

[8] BROUSTIS I, PAPAGIANNAKI K, KRISHNAMURTHY S,et al. Measurement-driven guidelines for 802.11 WLAN design[J]. IEEE/ACM Transactions on Networking, 2010,18(3): 722-735.

[9] SOOD K, LIU S, YU S, et al. Dynamic access point association using software defined networking[C]//2015 International Telecommunication Networks and Applications Conference, Nov 18-20, 2015, Sydney, Australia. New Jersey: IEEE Press, 2015:230-238.

[10] CHEN J, LIU B, ZHOU H, et al. QoS-driven efficient client association in high-density software defined WLAN [J]. IEEE Transactions on Vehicular Technology, 2017, PP(99): 1-2.

[11] 李克, 王換招, 張鵬, 等.一種用戶需求感知的無線接入點關(guān)聯(lián)策略[J]. 軟件學(xué)報, 2015, 26(2): 100-110.LI K, WANG H Z, ZHANG P, et al. User-demand-aware wireless access point association strategy[J]. Journal of Software,2015, 26(2): 100-110.

[12] PAPADIMITRIOU C H, STEIGLITZ K. Combinatorial optimization: algorithms and complexity[M]. New Jersey: Prentice-Hall, 1998.

[13] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithms: 3rd edition[M]. Cambridge: MIT Press,2009: 60-73.

[14] WAN X, WU J, SHEN X. Maximal lifetime scheduling for roadside sensor networks with survivability k[J]. IEEE Transactions on Vehicular Technology, 2015, 64(11): 5300-5313.

[15] CHERKASSKY B V, GOLDBERG A V. On implementing push-relabel method for the maximum flow problem[J]. Integer Programming and Combinatorial Optimization, 1995, 35(10):157-163.

An association optimization algorithm for wireless access points based on graph transformation

TAO Wen1, SHEN Yan2, GUAN Xinjie2, WAN Xili2
1.College of Mathematics and Information Technology, Jiangsu Second Normal University, Nanjing 210013, China 2. College of Computer Science and Technology, Nanjing Tech University, Nanjing 211816, China

Wireless access point association problem is one of the fundamental problems for Wi-Fi systems. Existing studies focus on the AP association problems under the bandwidth capacity constrain, without considering bandwidth demand for users. Considering the user bandwidth demands, the access point association problem for a Wi-Fi system under hybrid network architecture was studied, with the objective of maximum bandwidth allocation. Different from existing studies, by utilizing graph transformation techniques, this optimization problem was transformed to a network flow optimization problem on a flow graph. Then, an algorithm was proposed based on the maximum network flow problem. Theoretic proof for the optimality of the algorithm was presented and simulations results further validated the superiority of the proposed algorithm.

wireless access, graph transformation, AP association

s: The National Natural Science Foundation of China (No.61602235), The National Natural Science Foundation of Jiangsu Province of China (No.BK20161007)

signal strength indication，RSSI）判斷Wi-Fi接入點（access point，AP）的信號強度，并選擇信號強度最強的AP與之關(guān)聯(lián)。這種方法不能合理分配用戶到不同的AP上，容易造成部分AP過載，而其他AP關(guān)聯(lián)的用戶偏少，從而造成系統(tǒng)資源不能被充分利用，降低了系統(tǒng)整體關(guān)聯(lián)的用戶數(shù)目。此外，這種方法只是以信號強度來關(guān)聯(lián)用戶和AP，而沒有考慮到每個 AP的容量是有限的，即所能容納的用戶數(shù)是一定的。因此，如何在 AP容量有限的前提下，合理調(diào)度分配系統(tǒng)資源，從而提升系統(tǒng)整體可接入用戶數(shù)量是 AP關(guān)聯(lián)領(lǐng)域的一個重要問題[1]。

TP301

A

10.11959/j.issn.1000?0801.2017310

2017?08?05；

2017?09?19

國家自然科學(xué)基金資助項目（No.61602235）；江蘇省自然科學(xué)基金資助項目（No.BK20161007）

陶雯（1979?），女，江蘇第二師范學(xué)院數(shù)學(xué)與信息技術(shù)學(xué)院講師、CCF會員，主要研究方向為無線網(wǎng)絡(luò)協(xié)議。

沈艷（1984?），女，南京工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院碩士生，主要研究方向為網(wǎng)絡(luò)優(yōu)化。

管昕潔（1984?），女，博士，南京工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院講師，主要研究方向為云計算和軟件定義網(wǎng)絡(luò)。

萬夕里（1982?），男，博士，南京工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院講師，主要研究方向為網(wǎng)絡(luò)優(yōu)化和算法設(shè)計。