陶雯，沈艷，管昕潔，萬(wàn)夕里

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

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

陶雯1，沈艷2，管昕潔2，萬(wàn)夕里2

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

無(wú)線接入點(diǎn)關(guān)聯(lián)是 Wi-Fi系統(tǒng)中的一個(gè)基礎(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)的無(wú)線接入點(diǎn)關(guān)聯(lián)優(yōu)化問題。與已有研究方法不同，通過(guò)圖轉(zhuǎn)換技術(shù)，并將問題轉(zhuǎn)化為流圖上的優(yōu)化問題，提出基于網(wǎng)絡(luò)流的優(yōu)化求解算法，并從理論上證明算法的最優(yōu)性。最后，通過(guò)對(duì)比實(shí)驗(yàn)進(jìn)一步證明了算法的優(yōu)越性。

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

1 引言

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

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

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

2 相關(guān)工作

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

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

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

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

3.2 問題描述

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

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

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

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

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

值得注意的是，本文中的最大AP關(guān)聯(lián)問題不能采用經(jīng)典的二分匹配算法來(lái)求解，因?yàn)閷?duì)于每一個(gè)AP節(jié)點(diǎn)（即二分圖中U中的節(jié)點(diǎn)）是可以關(guān)聯(lián)多于一個(gè)的移動(dòng)設(shè)備（即二分圖中V中的一個(gè)節(jié)點(diǎn)），而二分匹配問題中 U有且僅能與 V中一個(gè)節(jié)點(diǎn)匹配。未解決此問題，本文提出一種圖轉(zhuǎn)換方法，將最大AP關(guān)聯(lián)優(yōu)化問題轉(zhuǎn)化為對(duì)應(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)建一個(gè)二分圖，對(duì)每個(gè)APi節(jié)點(diǎn)和移動(dòng)設(shè)備dj，分別在U和D中創(chuàng)建一個(gè)節(jié)點(diǎn)i和j。如果移動(dòng)設(shè)備j在APi的覆蓋范圍內(nèi)，也就是APi是移動(dòng)設(shè)備dj的候選節(jié)點(diǎn)，則在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，移動(dòng)設(shè)備集合U，每個(gè)移動(dòng)設(shè)備的候選AP集合。

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

步驟2在G的基礎(chǔ)上建立流圖G'（如圖2所示），在上額外添加一個(gè)虛擬源點(diǎn)S和終點(diǎn)T，對(duì)U中的每個(gè)頂點(diǎn)i，連接源點(diǎn)S與頂點(diǎn)i形成有向邊(S, i)，設(shè)置該邊的權(quán)重為Ci；對(duì)V中頂點(diǎn)j，連接j與終點(diǎn)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，即將移動(dòng)設(shè)備dj關(guān)聯(lián)到APi。

4.2 算法分析

引理1在圖2中，若所求得的從源點(diǎn)S到終點(diǎn)T 的最大流經(jīng)過(guò)邊則該邊對(duì)應(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)過(guò)一定是整數(shù)。又因?yàn)?ui, dj)邊的權(quán)重均為 1，所以(ui, dj） 若有最大流經(jīng)過(guò)，其最大流必定為1，即

引理2對(duì)于任何dj∈D節(jié)點(diǎn)，若一個(gè)從源點(diǎn) S到終點(diǎn) T 的流經(jīng)過(guò)該節(jié)點(diǎn)，則

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

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

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

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

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

證明：定理1揭示了單個(gè)AP關(guān)聯(lián)問題的可行解與流圖G'上的單源單匯流一一對(duì)應(yīng)關(guān)系，并且可行解的值對(duì)應(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ù)目）對(duì)應(yīng)于流圖G'上的所有的單源單匯流值之和，也就是對(duì)應(yīng)于流圖G'上的從源點(diǎn)S出發(fā)到終點(diǎn)T的網(wǎng)絡(luò)流。因此，最大AP關(guān)聯(lián)問題解的最大值對(duì)應(yīng)流圖G'上的最大網(wǎng)絡(luò)流。定理3最大AP關(guān)聯(lián)問題可以在時(shí)間內(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é)點(diǎn)的個(gè)數(shù)。因此算法1的復(fù)雜度為

4.3 示例

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

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

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

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

為了更全面地突出本文算法的有效性，從以下幾個(gè)方面進(jìn)行了仿真實(shí)驗(yàn)。

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

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

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

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

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

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

5.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

本文提出了在混合型架構(gòu)下的一種面向最大連接數(shù)的AP關(guān)聯(lián)算法。與已有AP關(guān)聯(lián)方法不同，本文應(yīng)用圖優(yōu)化方法來(lái)設(shè)計(jì) AP關(guān)聯(lián)算法，提出圖轉(zhuǎn)換技術(shù)，設(shè)計(jì)流圖，將該 AP關(guān)聯(lián)優(yōu)化問題轉(zhuǎn)化為流圖上網(wǎng)絡(luò)流優(yōu)化問題，并從理論上證明了兩個(gè)問題的等價(jià)性。在此基礎(chǔ)上，應(yīng)用網(wǎng)絡(luò)流算法，提出基于網(wǎng)絡(luò)流算法的最優(yōu)AP關(guān)聯(lián)算法。通過(guò)仿真實(shí)驗(yàn)，驗(yà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] 李克, 王換招, 張鵬, 等.一種用戶需求感知的無(wú)線接入點(diǎn)關(guān)聯(lián)策略[J]. 軟件學(xué)報(bào), 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接入點(diǎn)（access point，AP）的信號(hào)強(qiáng)度，并選擇信號(hào)強(qiáng)度最強(qiáng)的AP與之關(guān)聯(lián)。這種方法不能合理分配用戶到不同的AP上，容易造成部分AP過(guò)載，而其他AP關(guān)聯(lián)的用戶偏少，從而造成系統(tǒng)資源不能被充分利用，降低了系統(tǒng)整體關(guān)聯(lián)的用戶數(shù)目。此外，這種方法只是以信號(hào)強(qiáng)度來(lái)關(guān)聯(lián)用戶和AP，而沒有考慮到每個(gè) AP的容量是有限的，即所能容納的用戶數(shù)是一定的。因此，如何在 AP容量有限的前提下，合理調(diào)度分配系統(tǒng)資源，從而提升系統(tǒng)整體可接入用戶數(shù)量是 AP關(guān)聯(lián)領(lǐng)域的一個(gè)重要問題[1]。

TP301

A

10.11959/j.issn.1000?0801.2017310

2017?08?05；

2017?09?19

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

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

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

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

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