基于功率控制和信道分配的網絡優化算法

劉 悅，郭曉磊，張 迅

（1.開封大學信息工程學院 開封475004；2.武漢大學電子信息學院 武漢430079）

1 引言

WLAN由于其移動性、靈活性、低成本及易布設等優勢，在世界各地被大量布設[1]。但是高密度的無線局域網也暴露出了各種問題，如網絡性能下降、資源分配不均勻，網絡優化方法的研究一直是無線局域網研究領域的一個熱點[2]。目前的優化方法主要有3種手段：無線信號AP（access point，接入點）的工作信道分配；AP的發射功率控制；負載均衡。本文綜合考慮3種手段的優點，對算法進行了重新設計，提出了一種基于功率調整和信道分配的綜合優化方案，并進行了仿真實驗，驗證了本文提出的方法可以大幅改善網絡性能、負載的均衡性和網絡資源分配的有效性。

本文的研究目的在于：在不修改現有IEEE 802.11協議的情況下，采用功率控制及信道分配的方法對特定范圍內的無線局域網進行優化，盡量最大化無線局域網的有效帶寬，同時保證網絡的負載均衡。功率調整的方法不僅可以改變每個鏈路傳輸的速率以提高頻帶資源的利用率，還會改變用戶關聯關系及網絡結構，這方面的改變可以被有效地利用來提高網絡的帶寬和改善網絡負載不均衡的情況。同時，工作信道的選擇可以避免個別信道的負載過大導致的網絡性能下降以及信道資源浪費。信道選擇方法不僅可以改善網絡的性能和公平性，還可以更加有效地為網絡資源的分配提供建議。本文同時采用以上兩種方法對無線局域網進行優化，提供一套網絡優化方法，為網絡性能的提高、用戶公平性保證以及網絡資源分配提供解決方案。

目前在功率調整和信道選擇方面的主要工作如下。

[3]提出了一種功率調整的方法，采用跨層設計的方法調整AP的發射功率及載波感知門限，為繁忙的AP分配更大的發射功率，提高網絡整體的吞吐量。這種調整方法具有一定的局限性，因為一般來說AP都有自己的發射功率上限。

參考文獻[4]提出了一種信道選擇的方法，采用“最空閑信道搜索”分配AP的信道，AP的信道選擇是篩選出可用信道中最空閑的信道，并選用該信道。這種方法雖然在一定程度上提高了信道的利用率，但是卻不能降低由信道帶來的干擾。

參考文獻[5]提出了一種改變用戶關聯關系的方法，通過修改STA（station，工作站）與AP的驅動，讓STA與AP間交換各自的負載信息，并通過修改后的驅動使得STA關聯到空閑AP。這種方法需要修改硬件的驅動信息，比較復雜，限制了其應用范圍。

2 背景知識

WLAN主要包含STA[6]及AP等網絡組件，其中AP負責網絡所有的通信，包括同一服務區域中所有STA之間的通信。WLAN中，STA必須先與AP建立關聯才能取得網絡服務。對STA而言，關聯必須是唯一的，即每個STA在某個時間段內只能與一個AP相連。一般情況下，STA選擇信號強度最高的AP進行關聯，即通常與距離較近的AP進行關聯。然而，AP的發射功率是固定的，而STA的分布并不均勻，從而導致STA密集地帶的AP關聯的STA數量較多，相反，其他AP關聯的STA數量較少甚至不存在。這種關聯的不均衡性最終會導致網絡資源的浪費、網絡有效帶寬的下降。WLAN中主要的物理層協議為IEEE 802.11a/b/g/n。其中工作在2.4 GHz頻段的IEEE 802.11b/g/n協議擁有3個完全正交的信道（1、6、11），而工作在5 GHz頻段的IEEE 802.11a協議，在美國所使用的標準和30 MHz的防護頻帶的情況下，擁有12個正交信道。STA與AP之間的傳輸速率由接收幀的信號噪聲干擾比（SINR）決定，不同的傳輸速率與不同SINR的關系[7]見表1。

表1 傳輸速率與SINR的關系

3 優化方案闡述

3.1 網絡模型

假設高密度的無線局域網中含有N個AP和M個STA。如果整個區域被這N個AP完全覆蓋[8]，即沒有盲區存在，區域中的所有STA都關聯一個AP。STA的關聯采用目前最基本的基于信號強度的方式，即STA會選擇信號強度最大的AP進行連接。如果用γij表示STAi連接到APj時的SINR，則：

其 中，gij為APj到STAi的 信 號 傳 播 增 益，pj為APj的發射功率，N0為高斯白噪聲，Ai為能量覆蓋到STAi的AP的集合，si為能量覆蓋到STAi的STA的集合。cjk為頻率選擇函數，當APj（或STAj）與APk（或STAk）為同一信道時，cjk=1，否則cjk=0。可以從式（1）看出，同時考慮了與STAi處于同一頻段的AP與STA的能量干擾。

根據表1，IEEE 802.11網絡中存在8個傳輸速率的級別。每個傳輸速率的級別由一系列的SINR決定。

其中，vij表示STAi與APj之間的傳輸速率。如果bi表示分配給STAi的有效帶寬，則：

其中，δij表示關聯函數，當STAi與APj關聯時，δij=1，否則δij=0。tij表示在一個時間單元內STAi與APj之間的有效傳輸時間，則：

其中，wi代表STAi的權重系數。整個網絡的總體效用函數為：

3.2 功率調整

功率調整會引起兩個方面的改變：一個是會引起網絡的負載均衡狀況的變化[9]，另一個方面是可以引起整個網絡狀況的變化，因此在調整的過程中要同時注意這兩個方面。在實際的調整過程中首先調整AP的功率，改善網絡的負載情況，然后在不使網絡負載情況惡化的前提下，再對AP的功率進一步調整，改善整體網絡狀況。

3.2.1 網絡負載均衡

在一個具體的網絡中，STA指整個網絡中接入的用戶。網絡往往會存在負載不均衡的情況，某些AP關聯的用戶較多，其他AP關聯的用戶較少，這將會導致整體網絡的狀況惡化。因此網絡的負載均衡對整個網絡的狀況起著重要的作用。

首先構造待調整的AP信息矩陣M，主要包括AP的坐標和功率（AP的功率初始化到功率的上限），并設定一個已調整過功率的AP信息矩陣N，矩陣N初始時為空；另外還需要設定好AP功率調整的下限，這個過程的步驟如下。

（1）如果矩陣M和N中AP的數目不相等，說明還有待調整的AP，則繼續下面的步驟，否則計算此時的關聯用戶數的方差DX，以方便下一個步驟使用，退出循環。

（2）計算用戶的歸屬關系，根據其計算AP關聯用戶數的方差DX1。

（3）從未調整過功率的AP信息矩陣中（矩陣M除去矩陣N為未調整的矩陣）選擇關聯用戶數最多的AP為目標AP，如果其功率未達到設置的功率下限，則減小矩陣M中目標AP的功率，并計算當前的關聯用戶數的方差DX2；否則把目標AP存入矩陣N，再回到步驟（1）。

（4）比較步驟DX1和DX2的大小，如果DX2的值不大于DX1，則保存功率的調整，把目標AP存入矩陣N，再回到步驟（1）；否則矩陣M中目標AP功率恢復到未調整前的時刻，并把目標AP信息存入矩陣N，然后返回步驟（1）。

3.2.2 最大化網絡效用函數

引入AP效用[10]的概念，指關聯在它上面的用戶的加權帶寬積，APj的效用用UjA表示：

其中，Cj表示與APj關聯的用戶集合。

重寫網絡的效用函數并且進行如下變換：

由均值定理可知，幾何平均數不大于算數平均數，如下：

因此：

當每個AP的效用相等時，式（10）取得最大值，因此如果想最大化網絡的效用，只需要最大化Ua，且使每個AP的效用Ua接近即可。

算法開始時,初始化階段的AP信息矩陣X等于網絡負載均衡完成后的矩陣N，設定一個已調整過功率的AP信息矩陣Y，初始值為空。具體實現過程如下。

（1）如果X和Y兩個矩陣中AP的數目不相等，說明還有待調整的AP，則繼續下面的步驟，否則退出循環。

（2）計算每個AP的效用及平均效用U1a，并且確定AP的歸屬關系。

（3）從待調整的AP信息矩陣（矩陣X除去矩陣Y為未調整的矩陣）中找出擁有最大網絡效用的AP作為待調整的目標AP，如果其功率未達到設置的下限，則調整矩陣X中AP的功率，計算當前關聯用戶數的方差DX′，同網絡負載均衡過程中保留下來的DX進行比較，如果其不大于DX′，則進一步計算此時的平均效用U2a；否則，則把目標AP存入矩陣Y，并且回到步驟（1）。

（4）比較U1a和U2a的大小，如果U2a>U1a，則保存功率的調整，并把目標AP存入矩陣Y，且回到步驟（1）；否則矩陣X中目標AP功率恢復到未調整前的時刻，并把目標AP信息存入矩陣Y，然后返回步驟（1）。

3.3 信道分配

遺傳算法[11]是一種通過模擬自然進化過程進行最優解搜索的方法。本文設計的優化算法主要是通過最大化網絡的效用函數達到提升網絡性能的目的，而信道分配也會影響網絡的效用，因此可以用遺傳算法進行信道的分配[12]，使整體網絡的效用達到最大化。由式（5）可知其中wi是用戶的權重，在本文的實驗中假設各個用戶的權重是一樣的，都設為1，如果要使式（5）達到最大化，只要使達到最大化即可，因此這里可以確定其為目標函數。

在信道分配的遺傳算法中創建一個個體數目為10的種群，每個個體的染色體由對應AP序號的AP信道組成。AP信道經過編碼（1信道編碼為0、6信道編碼為1、11信道編碼為2）形成編碼后的染色體，參與后續的遺傳演變。特別地，原始信道分配會放在初始種群的一個個體中。算法流程如圖1所示，具體實現過程如下：

（1）若迭代次數達到最大迭代限制，算法退出，否則繼續；

（2）計算本代種群中每個個體的目標函數值，并根據其計算個體適應度；

（3）選擇需要進行交叉的個體；

（4）選擇個體的染色體重組；

（5）子代個體的基因突變；

（6）子代個體目標函數值的計算；

（7）根據子代、父代的個體染色體編碼及其對應的目標函數值進行重新插入，并獲取重插入的每個個體目標函數值；

（8）最優解保存；

圖1 遺傳算法流程

（9）迭代計數器加1，返回步驟（1）。

4 仿真實驗

本文通過對某地移動大樓二層進行測試，獲得測試數據，進行了優化算法的對比驗證。場景為辦公場所，大小為40 m×25 m，有11個待優化的目標AP和30個用戶（上文中的工作點），AP和用戶的工作信道為1、6和11中的一個。分別用單一化的優化手段以及本文中的方法進行了優化，然后把優化數據用網絡仿真軟件OPNET進行了仿真。

首先用OPNET進行場景的建模，建模的時候可以選擇辦公場景，根據建筑物的長寬設置場景的長寬。根據AP和工作點的實際位置建模，如圖2所示。

根據優化后的信息設置AP和工作點的信道、速率關聯信息等。OPNET的仿真時間設置為0.5 h，仿真結果如圖3和圖4所示。

圖2 網絡仿真建模

只調整功率與未調整前以及多手段優化算法的對比結果如圖3所示。

圖3 只調整功率與多優化手段及未調整前的仿真結果對比

只調整信道與未調整前以及多手段優化算法的對比結果如圖4所示。

圖4 只調整信道與多優化手段及未調整前的仿真結果對比

通過圖3、圖4的分析可以得出，單一化的優化手段一定程度上增大了網絡的吞吐量，起到了改善網絡性能的目的。當采用多優化手段的方法進行優化時，其吞吐量比單一手段的吞吐量均有明顯改善，這是因為本文提出的優化算法考慮了影響網絡性能的幾個指標（即功率、負載均衡和信道），并且重新設計了各個指標的評價函數。AP功率的高低會影響網絡的效用，從而會對網絡性能產生一定的影響；AP負載不均衡也會極大地降低網絡的性能；AP的信道分配出現問題，不僅會影響網絡的效用，也會影響網絡的干擾，這些都會影響網絡的性能。

5 結束語

無線局域網在布設的過程中由于缺乏一定的指導，其布設過程可能存在很多問題，如功率過大或者過小、信道的分配不合理等，造成網絡性能普遍下降。因此對無線網絡進行優化是一個迫在眉睫的問題，對于布設AP的運營商來說所起的作用更為重要。以往的優化手段往往比較單一，雖然能起到一定的作用，但是并不能使網絡性能達到最優。采用多優化的手段對AP的功率和信道進行調整，通過仿真結果的驗證表明，相比單一化的優化手段能取得更好的結果。

參考文獻

1 周慧峰,羅自強.高校場景下的WLAN網絡優化方案研究.移動通信,2013(6):23～25 Zhou H F,Luo Z Q.WLAN network optimization research programs university scenarios.Mobile Communications,2013(6):23～25

2 邵佩,吳迎笑,溫熙華.無線城市建設中WLAN熱點的部署及優化.電信技術,2011(11):33～34 Shao P,Wu Y X,Wen X H.Construction WLAN hotspot deployment and optimization of wireless city.Telecommunications Technology,2011(11):33～34

3 Wang S,Liu M,Cheng X,et al.Coverage adjustment for load-balancing with an AP service availability guarantee in WLANs.Wireless Networks,2014(20):475～491

4 Mishra A,Shrivastava V,Agarwal D,et al.Distributed channel management in uncoordinated wireless environments.Proceedings of ACM MobiCom,California,USA,2009:1～12

5 Broustis I,Papagiannaki K.Measurement-driven guidelines for 802.11 WLAN design.IEEE/ACM Transactions,2010,18(3):722～735

6 孫佑明.無線局域網WLAN設計與實現.計算機安全,2012(7):76～77 Sun Y M.Design and implementation of wireless local area network WLAN.Computer Security,2012(7):76～77

7 The Institute of Electrical and Electronics Engine.High-speed Physical Layer in the 5 GHz Band,1999

8 Zhai H,Chen X,Fang Y.How well can the IEEE 802.11 wireless LAN support quality of service.IEEE Transaction on Wireless Communications,2005(6):3084～3094

9 丁曉樂,李風華.基于功率控制和位置信息的無線局域網動態負載均衡機制.廈門大學學報，2007(42):150～152 Ding X L,Li F H.Dynamic load balancing mechanism in WLAN based on power control and location information.Journal of Xiamen University(Natural Science),2007(42):150～152

10 Kotz D,Essien K.Characterizing Usage of a Campus-wide Wireless Network,2002

11曾瑛.遺傳算法在優化求解中的應用.科技創業月刊,2012(10):193～194 Zeng Y.A summary for genetic algorithm and its application in optimization problems.Pioneering with Science & Technology Monthly,2012(10):193～194

12 Mochaourab R,Jorswieck E A.Optimal beamforming in interference networks with perfect local channel information.Signal Processing,2011(3):1128～1140