唐 紅 ,安融通,徐 川,韓珍珍,趙國鋒,周繼華
(1.重慶郵電大學(xué) 未來網(wǎng)絡(luò)研究中心,重慶 400065; 2.重慶金美通信有限責任公司,重慶 400065)
當今,隨著智能手機和可穿戴設(shè)備的興起,為了滿足用戶對高帶寬和高可靠性的需求,過去幾年中,移動互聯(lián)網(wǎng)得到了迅猛發(fā)展。無線局域網(wǎng)(wireless local-area network,WLAN)作為一種高速便利的移動網(wǎng)絡(luò)接入解決方案,已經(jīng)在企業(yè)、醫(yī)院、商圈、學(xué)校等區(qū)域密集部署,成為用戶訪問互聯(lián)網(wǎng)的主流接入方式。根據(jù)思科最近的一份報告表明[1],超過51%的移動流量從蜂窩網(wǎng)絡(luò)中卸載到公共接入點和住宅WiFi網(wǎng)絡(luò),到2020年,這一比例將上升到55%。無線接入點數(shù)量將增長到4.325億。但是密集部署的WLAN會造成2個關(guān)鍵問題:能源浪費和嚴重的干擾。根據(jù)文獻[2]實際測量接入點(acess point,AP)空閑時間比可知用戶流量需求高峰很少發(fā)生。實際上,在學(xué)校、公司中只有部分AP在白天能得到有效利用,多數(shù)AP在夜間和周末都處于空閑狀態(tài)。因此,當大量空閑AP始終處于全功率開啟狀態(tài)時,會造成嚴重的能源浪費。其次,因為IEEE802.11中2.4 GHz頻段缺少正交信道,當同頻AP間信號重疊時會對處于重疊范圍內(nèi)的用戶造成嚴重干擾,這已經(jīng)被證明會降低WLAN中用戶的體驗質(zhì)量[3-4]。
在綠色通信研究熱點中,已有大量文獻研究關(guān)于無線網(wǎng)絡(luò)中密集部署AP的能耗問題。文獻[2]中將密集部署的AP根據(jù)AP間的歐式距離進行聚簇分類,每個簇中信道利用率超過預(yù)設(shè)閾值時將開啟簇中輔助AP,并且對簇中AP負載均衡。但其不能根據(jù)實時網(wǎng)絡(luò)狀態(tài)選擇休眠AP以及進行用戶的切換,會導(dǎo)致節(jié)能不徹底問題。文獻[5]通過整數(shù)線性規(guī)劃建立最小化能耗模型,調(diào)節(jié)AP發(fā)射功率來達到節(jié)能的目的。雖然可以調(diào)低發(fā)射功率減小AP的電路能耗來節(jié)能,但是關(guān)聯(lián)此AP下的用戶仍會受到嚴重的干擾。另外研究人員還嘗試采用休眠喚醒及用戶切換策略來關(guān)閉低利用率或空閑的AP,從而有效利用無線資源滿足用戶流量需求[6-7]。文獻[6]基于集中式控制框架,根據(jù)用戶數(shù)量和系統(tǒng)流量的實際網(wǎng)絡(luò)狀況,利用其節(jié)能決策算法選擇AP開關(guān)來減小能耗。類似地,提出了一種全局信息感知功率控制框架和自適應(yīng)算法,根據(jù)各AP下所關(guān)聯(lián)用戶的流量需求動態(tài)地調(diào)整到相應(yīng)的功率模式實現(xiàn)節(jié)能目標[7]。文獻[8]對網(wǎng)關(guān)(gateway,GW)設(shè)定低負載閾值和高負載閾值,當GW負載不滿足閾值期間時將發(fā)起流量卸載請求,喚醒已關(guān)閉的GW或者可承載的GW執(zhí)行卸載任務(wù)?,F(xiàn)有的研究主要集中在關(guān)閉冗余的AP以降低能耗,而AP間因信號重疊所產(chǎn)生的干擾還沒有被深入考慮。
在文獻[10]中,作者提出一種聯(lián)合信道分配與用戶關(guān)聯(lián)控制的貪心算法優(yōu)化網(wǎng)絡(luò)干擾,實驗結(jié)果表明,該算法可以顯著提升用戶吞吐量。但在這工作中,沒有同時考慮干擾與能耗問題,這是無線系統(tǒng)資源調(diào)度與優(yōu)化的基礎(chǔ)[12]。Kimin Lee等[9]提出,干擾不僅影響無線網(wǎng)絡(luò)和用戶的QoE的穩(wěn)定性,而且還增加了無線系統(tǒng)的能耗。因此,考慮網(wǎng)絡(luò)干擾,同時可以有效解決能耗問題。以能耗為優(yōu)化目標,干擾為約束條件,提出了一種在不損失用戶需求的條件下結(jié)合接入點控制模式,信道選擇和用戶接入關(guān)聯(lián)的近似算法,以減少浪費的能量。但其假設(shè)的同一物理AP下,2個虛擬AP處于不同信道不符合實際情況。而且該工作中沒有將能耗干擾同時放在一個目標函數(shù)里進行優(yōu)化,不能更有效地優(yōu)化干擾。文獻[11]指出干擾源于強大的頻譜重用和高功率傳輸,嚴重限制了系統(tǒng)的性能,于是采用非合作博弈方式來優(yōu)化無線通信的干擾減少能耗。因沒有結(jié)合休眠AP,所以會導(dǎo)致節(jié)能抗干擾不徹底。因此,本文解決的關(guān)鍵問題是如何根據(jù)當前網(wǎng)絡(luò)狀態(tài)選擇休眠AP以及如何進行用戶關(guān)聯(lián)切換。
近年來,雙邊拍賣在資源分配[13-16]上得到廣泛的研究。雙邊拍賣市場通過公開喊價進行,買賣雙方可以通過向中間人提交他們愿意買賣的價格,并不斷調(diào)整雙方各自的報價,如果買方和賣方叫出相同的價格,則交易達成。雙邊拍賣市場通常具有大量的買賣雙方,參與者傾向于降低交易成本。文獻[13]研究了利用雙邊拍賣協(xié)調(diào)數(shù)據(jù)代理之間的數(shù)據(jù)交易,對數(shù)據(jù)資源進行分配。無線通信方面[15-16],文獻[15]研究雙邊拍賣對無線資源的分配,基站賣方和AP買方拍賣交易對基站負載進行流量卸載。
由于軟件定義網(wǎng)絡(luò)(software defined network,SDN)架構(gòu)具有集中控制與可編程性的特點,SDN一直以來備受關(guān)注。雖然SDN架構(gòu)的引入會增加一定的系統(tǒng)開銷,但是SDN集中控制與數(shù)據(jù)、控制平面分離的機制能提供統(tǒng)一的網(wǎng)絡(luò)視圖,進行集中控制從而達到網(wǎng)絡(luò)全局優(yōu)化及資源的高效利用。因此,本文將引入SDN架構(gòu)集中控制用戶在AP之間的切換。
針對目前缺乏對能耗和干擾二者聯(lián)合優(yōu)化的研究,本文對密集部署的AP利用雙邊拍賣聯(lián)合能耗和干擾目標同時進行優(yōu)化??紤]AP節(jié)能的成本函數(shù)作為賣方提供服務(wù)的開銷,干擾因素的效益函數(shù)作為買方獲得數(shù)據(jù)速率服務(wù)的收益。對節(jié)能與干擾聯(lián)合優(yōu)化下資源分配進行雙邊拍賣建模,求解社會福利最大化問題。拍賣完成后SDN控制器更新網(wǎng)絡(luò)狀態(tài)關(guān)閉空載AP,并且將拍賣成交的用戶和AP進行關(guān)聯(lián)切換。本文的主要貢獻如下。
1)針對上述關(guān)鍵問題,本文將AP看作為多個用戶提供無線資源服務(wù)的賣方,用戶看作向多個AP提出購買無線資源需求的買方,SDN控制器作為市場中間人。通過雙邊拍賣機制對無線資源進行合理的分配以達到節(jié)能與降低干擾的目的。
2)通過聯(lián)合干擾優(yōu)化的用戶效用函數(shù)與節(jié)能的AP成本函數(shù),得到節(jié)能與干擾聯(lián)合優(yōu)化下的社會福利最大化問題,設(shè)計一個節(jié)能干擾聯(lián)合優(yōu)化下的雙邊拍賣算法來求解該問題。
3)通過拉格朗日乘數(shù)法以及中間人最優(yōu)分配機制獲取拍賣雙方最優(yōu)的出價,然后使用梯度下降法更新拉格朗日乘子,迭代更新拍賣雙方的出價達到雙方數(shù)據(jù)速率供求的均衡解,即為節(jié)能與干擾聯(lián)合優(yōu)化的最優(yōu)解。
4)實驗仿真結(jié)果表明,本文算法能有效關(guān)閉冗余AP減少能源浪費,并且降低AP間對用戶的干擾,提升用戶的信道容量,滿足用戶的吞吐量需求。充分說明了本文算法的有效性。
在學(xué)校和公司等WLAN網(wǎng)絡(luò)中密集部署大量AP為用戶提供網(wǎng)絡(luò)服務(wù),但其中存在著嚴重的能源浪費和干擾問題。因此,將SDN控制器引入WLAN系統(tǒng),利用SDN控制器對網(wǎng)絡(luò)信息進行收集并動態(tài)地進行網(wǎng)絡(luò)資源調(diào)度,能對全網(wǎng)進行全局控制,系統(tǒng)為每個用戶提供一個獨立的虛擬AP,可實時監(jiān)測用戶的移動狀態(tài),當用戶發(fā)生位移時,控制器提前將用戶狀態(tài)在AP之間進行轉(zhuǎn)移,控制用戶在AP間的無縫切換[17-19],為用戶提供良好的移動性支持,其系統(tǒng)模型如圖1所示。
圖1 系統(tǒng)模型Fig.1 System model
針對密集部署場景下能源浪費和干擾嚴重的問題,本文引入了節(jié)能與干擾聯(lián)合優(yōu)化模型,通過設(shè)計雙邊拍賣機制來解決節(jié)能與干擾問題,目標是同時為AP和用戶提供最大社會福利。
通過計算當前干擾環(huán)境下用戶節(jié)點鏈路的信干噪比來描述AP間的干擾累加效應(yīng),這種物理干擾模型考慮了系統(tǒng)中所有對用戶節(jié)點產(chǎn)生干擾的鏈路,以判斷用戶節(jié)點是否滿足需求,克服了協(xié)議干擾模型沒有考慮多條干擾鏈路產(chǎn)生的干擾信號在接收節(jié)點出的累加效應(yīng)的缺點,能夠更加準確地描述真實環(huán)境中的干擾情況。
假設(shè)用戶Useri與APj關(guān)聯(lián),則用戶Useri接收鏈路的信號與干擾加噪聲比(signal to Interference plus noise ratio,SINR)表示為
(1)
(1)式中:No代表系統(tǒng)熱噪聲功率強度;pj表示APj的發(fā)射功率;gji代表APj到用戶Useri的路徑衰減因子,有
(2)
在雙邊拍賣中,買方和賣方都通過效用函數(shù)來表達拍賣交易中的主觀偏好。定義Hi(xi)代表用戶的效用函數(shù),這個效用函數(shù)表示用戶所創(chuàng)造的收入。對于用戶方而言,用戶傾向于得到更高的數(shù)據(jù)速率來獲取更高的收益。定義?Hi(xi)/?xi>0, ?2Hi(xi)/?xi2<0,其中,xi≥0,xi具有連續(xù)的二次微分函數(shù),對于每個用戶所需求數(shù)據(jù)速率xi的效用函數(shù)Hi(xi)是單調(diào)遞增的,嚴格的凹函數(shù)。故定義用戶Useri的效用函數(shù)Hi(xi),i∈φ表示為
Hi(xi)=lb(θ1·αi·xi+1)
(3)
(3)式中:θ1為常數(shù);由于用戶自身想要得到更多的無線帶寬資源更好地滿足網(wǎng)絡(luò)服務(wù)質(zhì)量,故引入影響因子αi表示用戶Useri的信干噪比,將干擾因素考慮到用戶效益函數(shù)中,對用戶受到的干擾進行優(yōu)化。所以,信干噪比值越大則能更好地滿足用戶的數(shù)據(jù)速率需求。當Hi(0)=0表示用戶數(shù)據(jù)需求為0時沒有產(chǎn)生任何效益。
對于每個APj,j∈φ,定義成本函數(shù)Pj(yj)表示APj為用戶的Useri提供服務(wù)所付出的成本。從AP方的角度來看,AP自身希望使用更少的帶寬傳輸數(shù)據(jù)為用戶提供網(wǎng)絡(luò)服務(wù),以獲取更多的效益。但為了使用戶更多地向密集部署中某些AP聚集以便能關(guān)閉更多的空閑AP達到節(jié)能目的,因此,利用指數(shù)函數(shù)設(shè)計AP成本與負載成相反的趨勢。并對APj定義?Pj(yj)/?yji<0,?2Pj(yj)/?yji2>0意味著每個APj為用戶所提供的數(shù)據(jù)速率yji的成本函數(shù)是單調(diào)遞減和嚴格的凸函數(shù),并且yji≥0,yji具有連續(xù)的二次微分函數(shù)。故定義APj的成本函數(shù)Pj(yj)(j∈φ)表示為
(4)
AP與用戶各自獨立決定賣與買多少數(shù)據(jù)速率是無法達到均衡的。因為AP的目標是以最小數(shù)據(jù)速率為用戶提供服務(wù),而用戶的目標是受到干擾最小,并且獲得更高的數(shù)據(jù)速率來滿足自身QoS需求。因此,兩者的目標是沖突的,所以在本文的拍賣中引入中間人SDN控制器促進交易更公平、公正地達成。中間人將要解決社會福利最大化問題,決定拍賣雙方之間的分配數(shù)據(jù)速率。社會福利為干擾優(yōu)化下用戶的效益函數(shù)與能耗優(yōu)化下AP成本函數(shù)的差額。社會福利最大化問題表達式為
(5)
需要滿足的約束條件為
(6)
(6)式中:條件(M1)表示用戶Useri當前所處的無線信道容量需求高于用戶的流量需求;條件(M2)表示APj為其所有關(guān)聯(lián)用戶Useri服務(wù)產(chǎn)生的負載低于此AP的轉(zhuǎn)發(fā)能力上限Ωj,max;條件(M3)表示用戶Useri的流量需求不高于可為其提供流量服務(wù)AP的供給數(shù)據(jù)速率;條件(M4)表示AP與用戶相應(yīng)的供求數(shù)據(jù)速率均不為負值。
本文利用雙邊拍賣機制實現(xiàn)節(jié)能與干擾聯(lián)合優(yōu)化下數(shù)據(jù)速率的最優(yōu)分配。社會福利目標函數(shù)滿足嚴格拉格朗日的凹函數(shù),可以轉(zhuǎn)為拉格朗日函數(shù)求解最大值,使用KKT條件( Karush-Kuhn-Tucker conditions)[21]得到節(jié)能與干擾聯(lián)合優(yōu)化下最佳的資源分配得到社會福利的最大值。利用約束條件(M1),(M2),(M3)構(gòu)建社會福利問題的拉格朗日函數(shù)[22],表示為
(7)
(7)式中:λ?(λi≥0:?i∈φ)是約束條件(M1)對應(yīng)的拉格朗日乘子矢量:μ?(μj≥0:?j∈φ)是約束條件(M2)相應(yīng)的拉格朗日乘子矢量;υ?(υij≥0:?i∈φ,?j∈φ)也是約束條件(M3)所對應(yīng)的拉格朗日乘子矢量。社會福利問題的最優(yōu)原始變量x*,y*和產(chǎn)生最優(yōu)對偶變量λ*,μ*,υ*的KKT條件由以下方程組給出
(8)
(9)
需要滿足相同的約束條件為
(10)
則構(gòu)建拉格朗日函數(shù)的KKT條件為
(11)
市場中間人決定的拍賣雙方最優(yōu)分配為(T1)和(T2),與(K1)(K2)聯(lián)立得拍賣雙方的出價為
(12)
(13)
定義用戶向市場中間人支付提供數(shù)據(jù)服務(wù)費用為Vi(xi),中間人給AP的服務(wù)報酬為Uj(yj),則用戶Useri與APj的利潤為
User_profit: max(Hi(xi)-Vi(xi))
(14)
AP_profit: max(Uj(yj)-Pj(yj))
(15)
可知拍賣雙方最大利潤應(yīng)滿足最優(yōu)條件[23]為
(16)
(17)
結(jié)合拍賣雙方的出價βij,ηji及KKT條件T1與T2可得,拍賣雙方的成本函數(shù)和效用函數(shù)分別為
(18)
(19)
(20)—(22)式中:δλ,δμ,δυ分別為對偶變量λi,μj,υij的迭代步長;-L(λi)表示拉格朗日函數(shù)在λi處的負梯度,類似地,-L(μj)與-L(υij)也表示拉格朗日函數(shù)在μj和υij處的負梯度;()+表示非負象限上投影,保證可行性約束均為非負值。由于社會福利問題目標函數(shù)是嚴格的凹函數(shù),故保證社會福利目標函數(shù)和拉格朗日函數(shù)無約束最大化對偶問題有相同的節(jié)能與干擾聯(lián)合優(yōu)化的最優(yōu)解。具體算法描述如下。
步驟1初始化網(wǎng)絡(luò)拓撲。將xij,yji,λi,μj,υij分別作為拍賣雙方的數(shù)據(jù)速率以及拉格朗日乘子初始值,并按照每個AP的鄰接數(shù)量以升序得到鄰接數(shù)組ap_adjacent,通過鄰接數(shù)組為AP分配正交信道。
步驟2計算數(shù)據(jù)速率。通過(8)—(9)式計算買賣雙方的各自出價βij和ηji并向拍賣中間人提交。中間人根據(jù)雙方出價以及KKT條件(T1)(T2)更新雙方的數(shù)據(jù)速率yji與xij。
步驟4最大社會福利及數(shù)據(jù)速率。通過(5)式得出最大的社會福利值,并輸出最優(yōu)的數(shù)據(jù)速率。
根據(jù)雙邊拍賣算法得到李雅普諾夫函數(shù)(Lyapunov function)為
(23)
(24)
又因為我們考慮的是一個非常小的時隙,因此,假定根據(jù)微分方程更新拉格朗日乘子有。
?i∈φ,?j∈φ
(25)
(26)
(27)
所以,李雅普諾夫函數(shù)ζ進一步得到
(28)
因此,得到李雅普諾夫函數(shù)ζ一階導(dǎo)數(shù)的上界并且根據(jù)(K3)(K4)(K5)對右邊不等式進行增刪優(yōu)化約束條件有
(29)
根據(jù)約束條件(K1),(K2)得到
(30)
由于社會福利問題的目標函數(shù)是嚴格的凹函數(shù),并且上式右邊為非正值。故可推出
(31)
并且結(jié)合ζ(λ,μ,υ)≥0,ζ(λ*,μ*,υ*)=0即得節(jié)能干擾聯(lián)合優(yōu)化下雙邊拍賣算法收斂到最優(yōu)。
假設(shè)參與雙邊拍賣機制中的用戶數(shù)為m,參與的AP數(shù)為n,收斂迭代循環(huán)次數(shù)為k,則本文算法的時間復(fù)雜度為O(mn+kmn),可以看出,當系統(tǒng)用戶規(guī)模很大時具有較高的復(fù)雜度,但將收斂判定Δ合理調(diào)節(jié)則能保證時間復(fù)雜度在可接受的范圍內(nèi)。
本文利用matlab進行仿真,實驗設(shè)備為內(nèi)存32 G,2.2 GHZ Intel Xeon E5-4607 CPU*2的ubuntu14.04系統(tǒng)服務(wù)器。實驗場景部署100個AP,用戶隨機放置在300 m×300 m的區(qū)域。AP的發(fā)射功率初始化為30 dBm,對應(yīng)AP的有效覆蓋半徑設(shè)置為40 m,并參考之前工作實際測量NETGEAR WNDR3800型號AP負載與能耗及丟包率的變化關(guān)系[25],將每個AP的最大有效負載均設(shè)為Ωj,max=70 Mbit/s,每個用戶吞吐量需求為1~4 Mbit/s的隨機值。為了更好地模擬一個真實的無線網(wǎng)絡(luò)環(huán)境,我們將用戶數(shù)從50增加到800,步長為50。AP信道均初始化為同一信道模擬存在干擾的無線環(huán)境。用戶效益函數(shù)系數(shù)θ1設(shè)置為100,AP成本函數(shù)系數(shù)θ2設(shè)置為0.001。在本節(jié)中,通過對比3種算法,分別是聚簇算法[2]、協(xié)作算法[8]和JIT算法[9]來驗證雙邊拍賣算法節(jié)能與干擾優(yōu)化的有效性。具體參數(shù)設(shè)置如表1所示。
表1 參數(shù)列表
不同算法的AP節(jié)能效果對比如圖2所示。
圖2 不同算法的AP節(jié)能效果對比Fig.2 Comparison of energy-saving of different algorithms for access point
由圖2可知,本文算法在用戶數(shù)由50增加到800的仿真場景中都有很好的能效表現(xiàn),其中,節(jié)能百分比表示節(jié)能前后系統(tǒng)能耗差與節(jié)能前系統(tǒng)總能耗的百分比。當用戶數(shù)為50的吞吐量需求時,本文算法與協(xié)作算法和JIT算法都達到一個很高的節(jié)能百分比(75%),比聚簇算法高出接近20%。隨著用戶數(shù)的增加,導(dǎo)致可關(guān)閉的AP越來越少,因此,節(jié)能百分比逐漸降低。由于聚簇算法在少量用戶數(shù)時不能選擇合理的AP開啟關(guān)聯(lián)而是相應(yīng)要開啟各自簇頭然后進行優(yōu)化,因此,不能有效休眠AP節(jié)能,在4種算法對比中聚簇算法節(jié)能效果較差,但當用戶數(shù)增加到800時,接近無線網(wǎng)絡(luò)環(huán)境中關(guān)閉AP的上限,各算法節(jié)能效果均下降至45%左右。
不同算法的干擾效果對比如圖3所示。
圖3 不同算法的干擾優(yōu)化效果對比Fig.3 Comparison of interference optimizationeffects of different algorithms
圖4為4種不同算法下用戶平均信道容量對比圖。從信道容量曲線易看出,本文算法下的用戶平均信道容量高于聚簇算法和協(xié)作算法下的信道容量,并且對于節(jié)能與干擾聯(lián)合考慮的JIT算法,本文算法仍然優(yōu)于其信道容量,因為本文算法保證相鄰AP在不同的1,6,11正交信道。因此,本文算法相對于這3種算法是最好的,并且能大幅提升用戶信道容量。
圖4 不同算法的用戶平均信道容量Fig.4 Comparison of user average channel capacity for different algorithms
綜上可知聚簇算法和協(xié)作算法,兩者都能達到節(jié)能的目的但沒考慮干擾的影響,不能更好地降低干擾,因此,本文算法優(yōu)于聚簇算法和協(xié)作算法。同時,由于本文算法考慮了無線系統(tǒng)中干擾的優(yōu)化,相對前2種算法用戶能有更高的鏈路容量。并且,與同時考慮節(jié)能與干擾的JIT算法相對比,由于本文算法考慮了為AP分配正交信道,避免了AP重疊區(qū)域同信道間的干擾,因此,本文算法雖然在節(jié)能方面與JIT算法保持相同性能,但是降低干擾方面有更好的效果。通過仿真數(shù)據(jù)并結(jié)合上述分析可以看出,本文所提出節(jié)能與干擾聯(lián)合優(yōu)化下的雙邊拍賣算法能有效關(guān)閉無線網(wǎng)絡(luò)中冗余AP并且降低干擾,合理分配用戶數(shù)據(jù)速率資源滿足用戶的需求,充分說明了算法的有效性和實用性。
針對密集WLAN網(wǎng)絡(luò)冗余AP能耗嚴重以及用戶受到AP間干擾影響的問題,本文提出了一種節(jié)能與干擾聯(lián)合優(yōu)化下的雙邊拍賣算法,求解社會福利最大化目標函數(shù),有效解決了能源消耗和干擾嚴重的問題。拍賣交易中AP與用戶不斷更新出價策略,最終達到出價均衡,為用戶分配合理數(shù)據(jù)速率,調(diào)整用戶關(guān)聯(lián)切換以降低系統(tǒng)的能耗和干擾。但本文未考慮對發(fā)射功率等進行優(yōu)化,下一步工作將對這些情況進行完善。