基于神經網絡和遺傳算法的高密集WLAN公平性保障算法

蔣雨瑾, 楊奇, 楊懋, 李波, 閆中江

(西北工業大學 電子信息學院, 陜西 西安 710072)

為了滿足用戶在各類場景下對無線業務日益增長的要求,無線接入點(access point,AP)的覆蓋越來越密集,頻譜資源愈發緊缺。無線局域網(wireless local area network,WLAN)標準IEEE 802.11中采用的是空閑信道評估機制(clear channel assessment,CCA)通過檢測信號能量大小來判斷信道的忙閑狀態,而高密集WLAN部署環境意味著AP能夠偵聽到更多同一信道的其他AP,使得網絡中的沖突退避更容易發生,造成WLAN吞吐量公平性下降,嚴重影響網絡服務質量(quality of service,QoS)。吞吐量是衡量WLAN性能的關鍵性指標,因此如不加特殊說明,本文的公平性指吞吐量公平性。

為了改善這一問題,學者們在物理層和媒體訪問控制(medium access control,MAC)層中提出了許多基于資源分配算法的方案。在物理層提出的設計大多是基于功率以及速率的方法[1-4]。文獻[1]中,作者根據相鄰節點與吞吐量嚴重下降的AP接收到的信號強度動態調節載波偵聽閾值,該動態調整閾值的算法能夠明顯提高網絡的下行吞吐量。在文獻[2]中,作者提出了基于信號發射功率的算法,該算法是通過AP間合作交換彼此當前時刻的吞吐量和所發送的數據包大小調節信號發送功率。在文獻[3]中,作者提出了一種新的魯棒速率自適應算法,其主要原理是根據短時間的信號路徑損耗調節物理層速率,并使用自適應請求發送幀來維持碰撞發生速率。在文獻[4]中,作者設計了一種局部搜索算法同時改進了傳統AP布局位置和信道分配方案的搜索算法。在MAC層中提出的方案有自適應競爭窗調整、準入控制[5-6]等算法。在文獻[5]中,作者對在CSMA/CA 機制下的競爭窗口進行優化,該算法的原理是在每個干擾節點中設計并實現一個控制器,同時根據本地的2次平均信道狀態值對競爭窗大小進行動態調節,最終使得信道狀態收斂到最佳值。在文獻[6]中,作者對準入控制技術進行了詳細研究和討論,但沒有提出有效的參數優化方案。總而言之,影響WLAN性能的因素眾多,但傳統的基于資源分配方案選取的優化參數較少,對WLAN性能提升有限。已有研究提供了一些提升公平性的有價值思路,但還存在一些不足之處。其中只針對競爭窗口值或發送功率的單一參數調節方案缺少對整網公平性的衡量,并且產生競爭窗口值的機制具有隨機性,而單一功率調整會在一定程度上影響通信范圍和質量,給高密集WLAN帶來新問題。動態的信道分配和切換技術會影響網絡穩定性,同時面臨信道資源緊缺問題,信道分配方法難以滿足高密集部署場景。

無線局域網絡日益復雜多變,采用傳統模型方法對復雜網絡環境建模越來越困難。而神經網絡黑盒優化是一個仍在發展的新興研究領域,現有的結合機器學習的無線局域網參數調優研究大多針對的是AP的發送功率以及信道分配[7-8]。文獻[7]采用了分布式強化學習方案,AP間信息不互通,各自進行強化學習,并求得各自的最優參數配置。文獻[8]采用深度Q-learning強化學習網絡 (DQN) 對無線通信網絡進行優化。但目前采用優化算法與神經網絡結合來對高密集無線局域網調優的研究較少。

針對高密集WLAN中的同頻干擾問題,本文基于神經網絡和遺傳算法提出了一種網絡參數調優方法。神經網絡具有強大的非線性擬合能力和學習能力,遺傳算法可以在解空間內進行全局搜索,因此在處理復雜系統優化問題時,能有效地避免陷入局部最優解。故本文在神經網絡可以構建數值間復雜的映射關系能力的基礎上,結合遺傳算法優秀的全局搜索能力來優化WLAN參數。該方法的核心思想是利用來自精準、一體化的仿真平臺[9-10]的有限次網絡仿真數據結果對神經網絡進行訓練,得到AP個數、發射功率、距離、能量檢測閾值、最小競爭窗口以及帶寬這些參數和網絡公平性之間的映射關系,利用這一具有強大的擬合建模能力的神經網絡模型作為遺傳算法的適應度函數,能夠起到優勢互補作用。通過遺傳算法對發送功率、能量檢測閾值以及最小競爭窗口的最優參數組合配置,保障小區間的公平性。

1 問題分析與研究現狀

1.1 公平性問題分析

IEEE 802.11中的CSMA/CA(carrier sense multiple access/collision avoidance)機制采用空閑信道評估,通過檢測信號能量來判斷信道忙閑狀態,在協議中,CCA主要分成2種方法:載波偵聽(carrier sense)以及能量檢測(energy detection)。

載波偵聽:載波偵聽用作檢測數據包的preamble,即識別數據包的起始邊界。802.11中的preamble部分采用特定的序列所構造,發送方和接收方都已知該序列,監聽節點會不斷對信道信號進行采樣,用其做相關運算,其計算值會與載波偵聽閾值進行比較判斷。若大于該值,則認為檢測到了一個信號,若小于則沒有檢測到。節點在識別到數據包起始部分后,通過解調出數據包內部的相應字段來識別出數據包的終止邊界。

能量檢測:該方法能夠識別數據包中的能量。其直接利用物理層接收到的能量大小來比較判斷是否有信號,若信號強度大于能量檢測閾值,則認為信道是忙,若小于該閾值,則判斷信道為閑。當同一信道有多個AP時,由于發送信號覆蓋范圍的重疊,在CCA機制下會出現一些AP對信道忙閑狀態的錯誤判斷,導致AP傳輸數據包的機會大幅下降,出現不斷進行等待退避或不斷發送數據包但節點無法正確解析發給自己的數據包preamble的情況。

線上線下學習內容高度契合，各有分工：線上完整精講、細講知識點、重概念原理和“廣度”學習，線下教師部分精講，理清脈絡，重案例點評和“深度”學習。

為了確保每個終端都能被服務,企業網或者校園網的AP位置可以根據用戶以及環境的需求進行部署,AP的數量和密度往往較大。即使采用頻率復用技術,但由于WLAN的工作帶寬較大,且工作在非授權頻段,所能配置的互不干擾的頻率有限,因此小區間仍然會出現工作帶寬重疊且相互干擾的問題。如圖1a)所示,A和B、C和B之間互相感知的接收信號強度指示(received signal strength indication,RSSI)在能量檢測閾值與載波偵聽閾值之間,而A和C之間互相感知的RSSI小于載波偵聽閾值。A和C可以同時退避競爭信道并發地發送數據,互不干擾。但由于信道能量檢測閾值較大,會讓A和B、B和C,都認為信道是空閑而不停地發包,導致A發的包、B發的包及B和C發的包會發生重疊,各節點不能正確解析包的preamble,最終造成整網的吞吐量下降。又如圖1b)所示,此場景中,A和B、C和B之間互相感知的RSSI大于能量檢測閾值,A和C間互相感知的RSSI小于載波偵聽閾值。在WLAN的CSMA/CA機制下,A和C可以同時競爭信道,互不干擾,而對于B,一旦A或者C發送數據包時,B就會監聽到信道繁忙,需要等待信道空閑。最終導致A和C將以很大概率占據信道,B難以搶占到信道無法進行數據的發送,從而導致B的吞吐量大幅下降,惡化網絡公平性。

圖1 公平性惡化問題示意圖

可以看出,該機制使部分節點的傳輸機會下降及傳輸失敗次數增加,將直接導致這部分節點和整網吞吐量下降,進而使得網絡中各小區吞吐量差異過大。假設網絡中共有N個AP,Ti為第i個AP的吞吐量,采用最小-最大公平性指標[11]d衡量WLAN中同頻干擾問題的嚴重性,計算公式為

(1)

WLAN中的多種網絡參數與公平性之間存在特定函數關系,在對公平性優化問題中,可以據此關系找到d的極大值點與對應參數配置值,從而實現對WLAN公平性的優化,本文提出一種優化算法,利用神經網絡得到優化參數與吞吐量間的函數關系,并利用遺傳算法來求解該問題。

1.2 采用機器學習優化無線網絡參數的相關研究

無線網絡參數調優問題本質上被視為求最優解問題,WLAN日益復雜,構建相應模型也變得困難。強化學習算法(reinforce learning,RL)是在機器與環境的交互過程中,根據環境返回的收益優化目標。強化學習在無監督的優化問題中證明了其應用價值,現已有較多學者針對蜂窩網絡下的資源分配問題提出了基于強化學習、深度強化學習和神經網絡方面的方法。文獻[12-14]采用深度學習中的Q學習算法(deep Q network,DQN)對功率進行合理分配使得整體速率達到最大值。除了強化學習這類動態規劃方法外,也有學者指出監督學習同樣可以應用于網絡參數調優。文獻[15]同樣采用了深度學習,逼近最小加權均方誤差算法,取代傳統方法中的使用近似迭代來求最優解,該方法是使用多收發器對功率進行控制。

在很多高密集AP場景下,采用機器學習對WLAN參數進行優化的相關方法并不全面。文獻 [16]只適用于狀態空間較少的場景,主要使用了分布式強化學習動態地對無線信道與發送功率進行分配與調節。另外由于無線局域網絡環境復雜,若使用強化學習進行參數優化則需要不斷使得網絡運行狀況發生改變并要求網絡環境即時反饋收益,在算法運行期間可能會影響到網絡環境。同時也面臨著算法復雜度高、運行時間長、難以收斂等挑戰。

現在基于機器學習對網絡參數調優算法主要有監督學習、非監督學習以及強化學習,這些方法技術已經在資源分配算法得以應用。文獻[17]作者把WLAN的容量優化過程分解為發射功率控制、數據鏈路調度以及網絡流量管理等問題。并利用支持向量機(support vector machines,SVM)和深度置信網絡(deep belief network,DBN)得到非線性優化問題的近似解。該算法主要利用SVM來識別每個數據鏈路是需要斷開還是以最大功率支持,然后采用DBN得到最佳功率值。仿真結果表明這一基于機器學習的算法十分有效。另外,文獻[18]提出了由AP獲取信息并分布式執行的發送功率動態分配算法。該算法中AP可從其相鄰AP獲取信道狀態和服務質量信息,來調節其本身的信號發射功率。該方案的目的是使其提出的加權目標函數達到最大值,以實現每個AP的吞吐量呈比例或者整網達到最大吞吐量。在蜂窩網絡應用中,文獻[19]分別將基于策略的蒙特卡羅策略梯度(REINFORCE)、基于行為的深度確定性策略梯度(deep deterministic policy gradient,DDPG)及基于值的深度Q學習(deep Q learning,DQL)算法應用到發送功率調節中。最終結論為相較于基于模型的方法,基于數據驅動的方法在速率方面表現更為優異,而其中DDPG在魯棒性方面的表現最優。但這些只是針對無線網絡中某單一方面或特點的應用,并不是機器學習在WLAN中的研究與應用。

2 基于神經網絡和遺傳算法的公平性保障算法

2.1 基本思想

具有至少一個S型隱含層、線性輸出層以及偏差的3層BP神經網絡能夠以任意精度逼近任何非線性連續函數。本文搭建的神經網絡輸入節點為網絡的一些基本參數配置,輸出節點為網絡中AP最小吞吐量與最大吞吐量的比值d,該值能夠衡量網絡中的公平性。通過大量數據訓練得到該問題的神經網絡模型,并利用測試集進行測試驗證,若誤差足夠小則達到訓練效果,否則需要不斷調整各層參數或數據集的規模直到輸出與期望之間達到誤差要求。

神經網絡可以看作是一個從n維輸入映射到n維輸出的黑盒函數,通過神經網絡建立WLAN參數與其公平性間的非線性擬合關系,即可簡化構建WLAN公平性模型的步驟,并且神經網絡的輸入數據集可以實時改變,故該神經網絡模型也能夠動態地對網絡性能進行有效評估。

2.2 詳細設計

如圖2所示,首先改變AP數量、距離、發送功率,能量檢測門限、最小競爭窗口值以及帶寬參數并基于一體化仿真平臺[9-10]得到有限組數據結果,形成訓練集和測試集。通過不斷修改模型參數和增加數據集訓練得到滿足誤差要求的神經網絡模型,將WLAN基本參數輸入到模型中,即可得到網絡公平性衡量指標d。遺傳算法的關鍵環節之一是適應度函數的設計與計算,由于影響高密集WLAN公平性的因素較多,難以對其進行建模,但神經網絡具有強大的擬合能力,從而可以作為遺傳算法的適應度函數。通過遺傳算法的不斷迭代和評估,可以得到WLAN參數配置結果。

圖2 參數優化流程圖

2.3 神經網絡

目前常使用反向傳播算法(backpropagation,BP)來訓練神經網絡。BP算法包括學習和識別兩部分,學習過程可分為正向傳播和反向傳播兩部分。正向傳播開始時,以任意值作為神經元權值的初值,選取輸入數據集中任意一組作為輸入,傳入隱層處理,最終在輸出層得到對應輸出。若輸出值與期望值存在較大的誤差,需要通過誤差的反向傳遞過程,調整各層神經元權值。

本文在搭建神經網絡模型中選取了6個與輸出公平性特征相關性較大的網絡參數,即6維輸入特征,能夠降低神經網絡的運算復雜度,加快擬合無線局域網絡環境信息的速度,神經網絡的輸出為一維特征d。

最終搭建的神經網絡模型如圖3所示,各層神經元個數以及所選取的激活函數如表1所示。

表1 神經網絡基本參數表

圖3 無線局域網絡多層神經網絡擬合模型

2.4 遺傳算法

遺傳算法是數學領域中通過計算找到最佳解決方法的一種搜索算法,其屬于進化算法。該算法是由生物界的進化規律演變而來的,隨后成為計算機科學領域中被廣泛應用的一種優化和搜索的機制。

本文需要求解的網絡參數配置為AP發送功率、能量檢測門限以及最小競爭窗這3個參數。該算法首先需要基于現有的模型對求解問題進行編碼并形成隨機遺傳種群,再通過基于選擇概率和適應度函數的選擇性復制、交叉、變異對最終解的適應性評估的滿足情況進行驗證。若其最終解經過驗證后滿足迭代收斂條件,則說明該解是最優的。具體流程如圖4所示。

圖4 遺傳算法流程圖

初始化:設定交叉概率Pc和變異概率Pm。假設群體中某個染色體表示為c=(x1,x2,…,xn),其中n表示選取的WLAN參數個數,xi表示第i個參數的取值。

適應度函數計算:這部分利用已經訓練完成并達到誤差需求的多層神經網絡模型進行輸出,即染色體中每一位的對應值作為神經網絡模型的輸入,其輸出則為適應度函數值。

選擇:采用精英保留策略讓上一環節中適應度函數值最大的個體直接進入到下一代進化中。

交叉:所有染色體按照次序并隨機完成配對。若染色體個數為奇數,則適應度函數值最大的染色體將不再進行配對。隨后采用均勻交叉算子,即一對染色體的索引i處的基因會以交換概率Ps進行交換。經驗研究表明,均勻交叉既能保持良好的信息交換特質,又能更優地搜索設計空間。

變異:采用兩點交叉變異算子。首先在所有染色體上設置隨機的2個交叉點,再根據變異概率Pm交換所設定的2個交叉點之間的部分染色體。

不斷重復適應度函數計算、選擇、交叉以及變異這4個環節,直至滿足迭代收斂條件,將遺傳算法最終輸出結果的對應解作為最優參數配置。

3 仿真驗證

3.1 仿真環境及參數設置

本文采用基于NS3的下一代WLAN一體化仿真平臺[9-10],仿真參數如表2所示。

表2 仿真參數表

3.2 仿真結果及分析

神經網絡模型訓練完成后的最小相對誤差值為0.037%,最大相對誤差值為2.1%,從圖5中測試集數值與BP神經網絡預測值對比可以看出該神經網絡的訓練已滿足誤差要求。

圖5 神經網絡模型預測結果 圖6 AP個數為3的吞吐量結果對比圖 圖7 AP個數為6的吞吐量結果對比圖

圖6為AP個數為3的仿真結果對比圖,從圖中可以看出在沒有進行參數優化的802.11ax場景下,AP2的吞吐量遠小于AP1與AP3的吞吐量,采用本文算法得到的參數配置進行仿真后,AP2的吞吐量提高了70.77%,結果表明該參數配置能夠改善小區間公平性問題。基于神經網絡和遺傳算法的方案吞吐量輸出結果與在仿真平臺中單獨使用遺傳算法對網絡參數求最優解的吞吐量輸出結果基本一致。

圖7為AP個數為6的仿真結果圖,從圖中可以看出未進行參數優化的802.11ax場景下,AP2、AP3和AP5的吞吐量遠小于AP1與AP6的吞吐量,采用本文算法優化后的參數進行仿真后,AP2、AP3和AP5的吞吐量分別提升了10.31%,27.53%和64.6%,提高了網絡的公平性。基于神經網絡和遺傳算法與單獨使用遺傳算法的2種方案對吞吐量的輸出結果也基本符合。

圖8展示了3種方案在不同AP個數場景下的整網總吞吐量對比情況,基于神經網絡和遺傳算法與單獨使用遺傳算法的2種方案對整網總吞吐量皆有提升。AP個數為3時,分別提升了16.11%和15.05%,AP個數為6時,分別提升了3.81%和3.25%。因此,公平性問題得到改善的同時,整網總吞吐量也得到了提升。

圖8 不同方案下整網總吞吐量結果對比圖

從仿真結果對比中可以看出,基于神經網絡與算法得到的參數配置使得網絡公平性得到提高,如表3所示,3APs場景下AP最小吞吐量與最大吞吐量比值由40.79%提高到86.40%;6APs場景下AP最小吞吐量與最大吞吐量比值由37.27%提高到了79.11%。本文提出的算法與單獨使用遺傳算法的仿真結果基本符合,表明多層神經網絡訓練效果良好、誤差小,且前者的耗時更短、靈活性更強。盡管神經網絡和遺傳算法需要引入一些計算和存儲開銷,但由于遺傳算法具有并行計算特性,而神經網絡也可以采取離線(或者準離線)學習的方式進行,因此可以降低算法的計算和存儲開銷。

表3 參數優化方案效果對比

4 結 論

為了改善高密集WLAN中的小區間公平性問題,本文提出了一種基于神經網絡和遺傳算法的參數調優方案,通過多組仿真數據對神經網絡進行訓練與驗證,使其充當遺傳算法中的適應度函數,最終得到最優組合參數取值,在對應參數配置下得到的仿真結果表明網絡公平性得到大幅提高。本文方案設計簡單,靈活性強,能夠在下一代WLAN下具有較強的應用價值。