周衛(wèi)元,陳立建,,徐欣晨,毛科技*
(1.浙江廣播電視大學(xué)蕭山學(xué)院,杭州 311200;2.浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310032)
無(wú)線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Networks)是由傳感器節(jié)點(diǎn)、匯聚節(jié)點(diǎn)(Sink node)和終端等3個(gè)部分組成的一種自組織網(wǎng)絡(luò),由于應(yīng)用場(chǎng)合的特殊性,傳感器節(jié)點(diǎn)一般由電池供電,電池更換比較困難或者花費(fèi)代價(jià)比較高[1-2]。所以直接能從環(huán)境中捕獲能量的WSN被廣泛的進(jìn)行了研究與應(yīng)用,能從環(huán)境中捕獲的能量包括太陽(yáng)能、熱能、射頻能量、振動(dòng)能量、機(jī)械能等等[3-4]。射頻能量捕獲無(wú)線傳感器網(wǎng)絡(luò)RFEHWSN(Radio Frequency Energy Harvesting Wireless Sensor Network)可以通過(guò)不同物理環(huán)境和不同需要條件如時(shí)間、頻率、能量源的發(fā)送能量功率等維度上進(jìn)行充分的控制,穩(wěn)定性較強(qiáng)[5-6]。RFEHWSN 一般由能量源ET(Energy Transmitter)、基站BS(Base Station)和無(wú)線傳感器節(jié)點(diǎn)組成。
目前在RFEHWSN的研究進(jìn)展有,文獻(xiàn)[7]給出了射頻能量捕獲無(wú)線傳感網(wǎng)中占空比最佳的能量源布置方法。文獻(xiàn)[8]描述了射頻能量捕獲異構(gòu)無(wú)線傳感網(wǎng)的能量源最少化布置方法。文獻(xiàn)[9-11]對(duì)無(wú)線傳感網(wǎng)絡(luò)的射頻能量收集器,能量源移動(dòng)路徑約束下時(shí)延最小化供電方案,射頻能量收集芯片等進(jìn)行了研究。文獻(xiàn)[12]的模型也是點(diǎn)對(duì)點(diǎn)的平坦衰落信道下的無(wú)線系統(tǒng),由于時(shí)變同信道信號(hào)干擾的存在,單天線接收方不僅要考慮如何收集發(fā)射機(jī)發(fā)射的干擾信號(hào)或者特定信號(hào)作為節(jié)點(diǎn)的能量供應(yīng),還要考慮如何解碼信息。文獻(xiàn)[13]提出了一種動(dòng)態(tài)功率拆分的分配方案,即接收器接收到的信號(hào)一部分用以電池的供能,一部分用以信息解碼。在RFEHWSN的基站部署方面,文獻(xiàn)[14]研究了 RFEHWSN 中滿足節(jié)點(diǎn)吞吐量需求的基站最少化部署問(wèn)題,提出一種低復(fù)雜度的啟發(fā)式部署算法和一種復(fù)雜度略高的基于遺傳算法的部署算法。文獻(xiàn)[15]以最少化基站和能量源數(shù)目為目標(biāo),研究了基站和能量源的聯(lián)合部署,滿足每個(gè)節(jié)點(diǎn)的平均能量捕獲功率比所需數(shù)據(jù)發(fā)送功率至少高出一個(gè)預(yù)定的閾值作為約束條件。本文考慮在異構(gòu)射頻能量捕獲傳感網(wǎng)中,確定出滿足所有傳感器節(jié)點(diǎn)吞吐量所需求的最少基站個(gè)數(shù),將其作為初始化部署,給定多于初始化部署所需個(gè)數(shù)的基站(如1.5倍的初始化基站個(gè)數(shù)),在不同基站數(shù)目下,部署基站滿足負(fù)載均衡,從而使節(jié)點(diǎn)的傳輸速率和網(wǎng)絡(luò)吞吐量滿足一個(gè)較優(yōu)的水平。
本節(jié)介紹滿足節(jié)點(diǎn)吞吐量需求的負(fù)載均衡基站部署的異構(gòu)RFEHWSN模型。
(1)
(2)
(3)
(4)
式中:λ2為數(shù)據(jù)傳輸信號(hào)波長(zhǎng)。節(jié)點(diǎn)向基站傳輸信息,節(jié)點(diǎn)接入該基站?;镜慕尤肓?也稱負(fù)載量,定義為接入該基站的節(jié)點(diǎn)數(shù)目(基站服務(wù)節(jié)點(diǎn)數(shù))。根據(jù)信噪比公式,基站Bn從節(jié)點(diǎn)Sk處接收的信號(hào)的信噪比為
(5)
式中:no是高斯白噪聲的功率譜密度,W是信號(hào)帶寬。根據(jù)香農(nóng)公式,可以得到節(jié)點(diǎn)Sk的實(shí)際吞吐量Ck為:
Ck=Wlog2(1+SNRk),k=1,2,…,K
(6)
綜上以上公式可得:
(7)
基于以上分析,最優(yōu)基站部署問(wèn)題可建模為優(yōu)化如下問(wèn)題:
目標(biāo):均衡各個(gè)基站的服務(wù)節(jié)點(diǎn)數(shù)量
變量:各個(gè)基站位置
滿足全部節(jié)點(diǎn)的吞吐量需求的負(fù)載均衡基站部署方案為可行基站部署方案。在所有可行基站部署方案中,負(fù)載量最均衡的基站部署方案為最優(yōu)基站部署方案。
由于基站數(shù)N是整數(shù)取值且節(jié)點(diǎn)的吞吐量表達(dá)式不是凸函數(shù),該問(wèn)題實(shí)際上是研究一個(gè)非線形和非凸優(yōu)化問(wèn)題,不能用凸優(yōu)化理論解決。本文提出高效的啟發(fā)式基站部署方案,值得說(shuō)明的是,該問(wèn)題與ETs部署問(wèn)題都屬于拓?fù)鋬?yōu)化問(wèn)題,但是由它們對(duì)應(yīng)的數(shù)學(xué)優(yōu)化問(wèn)題可以知道,ETs部署問(wèn)題中約束函數(shù)涉及的節(jié)點(diǎn)能量捕獲表達(dá)式與基站部署問(wèn)題中約束函數(shù)涉及的節(jié)點(diǎn)吞吐量表達(dá)式有著顯著的不同。在ETs部署問(wèn)題中,每個(gè)ETs位置的改變會(huì)影響所有節(jié)點(diǎn)所捕獲的功率,而在基站部署問(wèn)題中,每個(gè)基站位置的改變只影響其周邊少數(shù)節(jié)點(diǎn)。因此,ETs部署問(wèn)題的已有部署方案不適用于基站部署問(wèn)題。此外,該問(wèn)題與最小化基站問(wèn)題也有著不同,最小化基站問(wèn)題并不考慮每個(gè)基站的負(fù)載量,目的是基站數(shù)目最小。而在負(fù)載均衡基站部署中,需要優(yōu)化的是每個(gè)基站的位置和接入量,基站數(shù)目的多少影響著整個(gè)網(wǎng)絡(luò)的基站負(fù)載量。
本文定義以下幾個(gè)在基站部署方案中涉及的概念和定義。
(8)
由式(7)、式(8)可知,距離基站越近的節(jié)點(diǎn)可以達(dá)到的吞吐量越高。
定理1在可行基站部署方案中,任意一個(gè)節(jié)點(diǎn)的需求圓內(nèi)至少部署一個(gè)基站。
證明:通過(guò)反證法來(lái)證明。對(duì)于某個(gè)可行基站部署方案,假設(shè)一個(gè)節(jié)點(diǎn)的需求圓內(nèi)沒(méi)有基站,那么該節(jié)點(diǎn)到最近基站的距離大于需求半徑,那么該節(jié)點(diǎn)達(dá)不到其吞吐量需求。因此,這與可行基站部署方案的定義相矛盾。證明結(jié)束。
定義2(最糟糕基站) 全網(wǎng)中服務(wù)節(jié)點(diǎn)數(shù)目最多的基站。
定理2存在一個(gè)最優(yōu)部署方案,每個(gè)基站都是在最小覆蓋長(zhǎng)方形內(nèi)。
證明:通過(guò)反證法來(lái)證明。假設(shè)每個(gè)最優(yōu)基站布置方案都有基站部署在最小覆蓋長(zhǎng)方形外。任意挑一個(gè)最優(yōu)基站布置方案,如圖1所示,有個(gè)基站部署在最小覆蓋長(zhǎng)方形ABCD外的E點(diǎn)。現(xiàn)將該基站從E點(diǎn)沿著垂直于AD邊的線路上移動(dòng)直至到達(dá)AD邊上的F點(diǎn)。易知,任一原先接入該基站的節(jié)點(diǎn),到該基站的距離變得更短,因此該新基站部署方案仍為可行方案。證明成立。
圖1 部署示意圖
在給定基站個(gè)數(shù)N和節(jié)點(diǎn)個(gè)數(shù)K時(shí),平均基站服務(wù)節(jié)點(diǎn)數(shù)Bavg為
Bavg=K/N
(9)
每個(gè)基站的服務(wù)節(jié)點(diǎn)數(shù)越接近平均數(shù),則部署方案越優(yōu)。為了使本文的部署方案能更好地反映均衡性,本文采用基站負(fù)載量方差這個(gè)參數(shù)σ2來(lái)衡量。
定義基站負(fù)載量方差為
(10)
Bload是每個(gè)基站的負(fù)載量,方差越小,方案越優(yōu)。
本文在初始化部署中,基站的部署方案要滿足約束條件,使每個(gè)節(jié)點(diǎn)滿足各自的吞吐量需求;在負(fù)載均衡部署中,始終滿足吞吐量約束條件基礎(chǔ)上對(duì)基站進(jìn)行接入量的優(yōu)化。
給定節(jié)點(diǎn)和ETs的位置和個(gè)數(shù)情況下,根據(jù)式(3)計(jì)算出節(jié)點(diǎn)的能量捕獲功率。給定各個(gè)節(jié)點(diǎn)的吞吐量要求下,再根據(jù)式(8)計(jì)算出各個(gè)節(jié)點(diǎn)的需求半徑和需求圓。
初始化部署方案滿足每個(gè)節(jié)點(diǎn)的吞吐量需求,所以我們可以執(zhí)行某個(gè)已有的部署方案,將所需最小基站數(shù)目部署在網(wǎng)絡(luò)中,并將節(jié)點(diǎn)接入相應(yīng)的基站。具體步驟如下:
第2步 由節(jié)點(diǎn)的發(fā)送功率和最低吞吐量需求計(jì)算出各個(gè)節(jié)點(diǎn)的需求半徑rk. 和需求圓。
第3步 執(zhí)行某個(gè)已有的部署方案(本文的方案)來(lái)將Nmin個(gè)基站部署到網(wǎng)絡(luò)中并將節(jié)點(diǎn)接入到這些基站。
第4步 確定剩余基站數(shù)N′=N-Nmin。
本文部署的主要目標(biāo)是讓最糟糕基站達(dá)到負(fù)載均衡的效果,所以基站的接入量是唯一衡量指標(biāo),分別從兩個(gè)維度——節(jié)點(diǎn)和其余基站以均衡糟糕基站。對(duì)于節(jié)點(diǎn)而言,若其需求圓內(nèi)基站個(gè)數(shù)大于1,節(jié)點(diǎn)進(jìn)行信息傳輸基站的選擇就有很多種,為了滿足負(fù)載均衡,節(jié)點(diǎn)可以切換接入負(fù)載量較輕的基站進(jìn)行信息傳輸。對(duì)于基站而言,若它原來(lái)所有的節(jié)點(diǎn)都已經(jīng)切換到其余基站時(shí),該基站可作為一個(gè)待移動(dòng)基站,在性質(zhì)上與未部署基站是一樣的(即此時(shí)接入量為0),該基站可以部署在最糟糕基站位置上,有效降低最糟糕基站的接入量。
因此,優(yōu)化方案可分為4個(gè)部分:給定節(jié)點(diǎn)的切換優(yōu)化、給定基站接入節(jié)點(diǎn)的切換優(yōu)化、單個(gè)待移動(dòng)基站的挑選和全網(wǎng)節(jié)點(diǎn)接入優(yōu)化。
①給定節(jié)點(diǎn)的切換優(yōu)化Node-Switch
當(dāng)節(jié)點(diǎn)的需求圓內(nèi)部署了不止一個(gè)基站時(shí),為了滿足負(fù)載均衡,該節(jié)點(diǎn)就有選擇切換基站進(jìn)行信息傳輸?shù)臋?quán)利。若節(jié)點(diǎn)當(dāng)前傳輸信息的基站接入量相比較其他圓內(nèi)基站更大,則該節(jié)點(diǎn)可以切換至接入量較小的基站上。在該模塊中,執(zhí)行以下步驟:
第1步:對(duì)于給定的節(jié)點(diǎn)Sk,該節(jié)點(diǎn)的需求圓內(nèi)的基站數(shù)目(記為I)大于1,即I>1,則節(jié)點(diǎn)進(jìn)入準(zhǔn)備切換狀態(tài),當(dāng)前接入的基站記為Bnow。
第2步:值得注意的是節(jié)點(diǎn)只會(huì)切換至負(fù)載量小于P的基站。在節(jié)點(diǎn)需求圓內(nèi)找到負(fù)載量最低的基站B1。
第3步:判斷基站B1是否為Bnow。若不是,則節(jié)點(diǎn)切換至B1,否則繼續(xù)執(zhí)行。
第4步:完成該模塊。
②給定基站接入節(jié)點(diǎn)的切換優(yōu)化Nodes-Switch in BS
對(duì)于某個(gè)基站Bn下所有接入的節(jié)點(diǎn),進(jìn)行一個(gè)優(yōu)化接入Node-Switch。具體步驟如下:
第1步 給定某個(gè)基站B,記此時(shí)基站負(fù)載量為P。
第2步 記錄接入該基站B的所有節(jié)點(diǎn)Sp(p=1,2…P)。
第3步 初始化p=1。
第4步 判斷p<=P是否成立,若成立,繼續(xù)向下執(zhí)行,若不是,執(zhí)行第8步。
第5步 對(duì)于節(jié)點(diǎn)Sp,判斷該節(jié)點(diǎn)的需求圓內(nèi)是否有多個(gè)基站。
第6步 若該節(jié)點(diǎn)的需求圓內(nèi)只有一個(gè)基站B,則該節(jié)點(diǎn)只能接入該基站B,執(zhí)行第7步。否則,調(diào)用執(zhí)行模塊Node-Switch。
第7步p=p+1,執(zhí)行第4步。
第8步 完成該模塊。
③單個(gè)待移動(dòng)基站的挑選Single Moving BS Selection
在這一模塊中,由于基站的負(fù)載量越低,其相應(yīng)節(jié)點(diǎn)切換的復(fù)雜度越低,所以依次按照負(fù)載量從低到高的順序,嘗試從所有已經(jīng)部署的基站中挑選出一個(gè)待移動(dòng)的基站。當(dāng)接入某個(gè)基站的節(jié)點(diǎn)可以全部切換到其他基站后,此時(shí)該基站的負(fù)載量為0,那么該基站就是待移動(dòng)的基站,它可以去均衡負(fù)載量更重的基站。具體步驟如下。
第1步:基站負(fù)載量進(jìn)行從低到高排序,記為B1,Bi,…,BI,(1
第2步:判斷i
第3步:給定基站Bi,此時(shí)基站負(fù)載量記為P,記錄接入該基站Bi的所有節(jié)點(diǎn)Sp(p=1,2,…,P)。
第4步:判斷當(dāng)前基站Bi下所有的節(jié)點(diǎn)Sp的需求圓內(nèi)是否都存在至少兩個(gè)基站,只要存在一個(gè)節(jié)點(diǎn)的需求圓內(nèi)只有一個(gè)基站,則Bi不能成為待移動(dòng)基站,執(zhí)行第7步。否則當(dāng)所有的節(jié)點(diǎn)的需求圓內(nèi)是否都存在至少兩個(gè)基站,繼續(xù)執(zhí)行。
第5步:在所有的節(jié)點(diǎn)Sp的需求圓內(nèi)將基站Bi標(biāo)記可懸空。
第6步:節(jié)點(diǎn)Sp接入其需求圓內(nèi)負(fù)載量最小的基站,執(zhí)行第8步。
第7步:i=i+1,執(zhí)行第2步。
第8步:退出。
④全網(wǎng)節(jié)點(diǎn)接入優(yōu)化All Nodes Optimization
在該模塊中,主要目標(biāo)是均衡最糟糕基站的負(fù)載量,使得全網(wǎng)節(jié)點(diǎn)的信息傳輸相對(duì)較均衡。偽代碼如下:
All Nodes Optimization
1. while(true)
2. 挑出當(dāng)前最糟糕基站,執(zhí)行將其一半的接入節(jié)點(diǎn)切換走;
3. if(Nodes-Switch in BS沒(méi)有進(jìn)行任何節(jié)點(diǎn)接入的切換)
4. break;
5. end while
基于以上分析,優(yōu)化部署的總體偽代碼如下:
負(fù)載均衡優(yōu)化部署方案
Output:所需基站物理位置
Main procedures
①初始化部署
2. 將最小覆蓋長(zhǎng)方形區(qū)域分割成p×q個(gè)小網(wǎng)格,并將這些網(wǎng)格標(biāo)上序號(hào),每個(gè)網(wǎng)格的中心記
為基站可能放置的位置。
3. 由節(jié)點(diǎn)的發(fā)送功率和最低吞吐量需求計(jì)算出各個(gè)節(jié)點(diǎn)的需求半徑rk。
4. 執(zhí)行某個(gè)已有的基站部署方案(比如本文前面所提方案)來(lái)將Nmin個(gè)基站部署到網(wǎng)絡(luò)中,將
節(jié)點(diǎn)接入這些基站。
②負(fù)載均衡優(yōu)化部署
1. if(N>Nmin)
2. for(i=1;i<=N-Nmin;i++)
3. 從剩余基站中挑出一個(gè),部署到最糟糕基站上;
4. 執(zhí)行All Nodes Optimization進(jìn)行全網(wǎng)節(jié)點(diǎn)優(yōu)化;
end for
end if
5. while(true)
6. 執(zhí)行Single Moving BS Selection嘗試挑出一個(gè)待移動(dòng)的基站;
7. if(Single Moving BS Selection挑出了基站)
將其放在最糟糕基站邊上;
8. else
return;
9. 執(zhí)行All Nodes Optimization進(jìn)行全網(wǎng)節(jié)點(diǎn)優(yōu)化;
end while
本文仿真實(shí)驗(yàn)的場(chǎng)景是10 m×10 m的區(qū)域內(nèi)隨機(jī)部署了K個(gè)傳感器節(jié)點(diǎn),均勻部署了4個(gè)ETs,每個(gè)ET的發(fā)送功率Pt=0.1 W。能量捕獲模型和信息傳輸模型的相關(guān)參數(shù)如下[16]:η=0.3,Gs=8 dBi,Gr=2 dBi,Lp=3 dB,λ1=0.33 m,λ2=0.66 m,ε=0.2316 m,α=0.8。每種情況下的拓?fù)淠M1 000次。
采用的對(duì)比方案一,隨機(jī)對(duì)比法,即相同初始化部署后,如果還有基站未使用,則將剩余全部基站隨機(jī)放置在節(jié)點(diǎn)需求圓覆蓋范圍內(nèi),接著節(jié)點(diǎn)按照1/2的概率選擇是否進(jìn)行基站切換;如果基站已經(jīng)使用完,那么方案結(jié)束。
對(duì)比方案二,接入一半法,即相同初始化部署后,如果還有基站未使用,則每次將基站放置在全網(wǎng)最糟糕的基站旁,分擔(dān)其一半的接入量,直到所有基站全部部署;如果基站已經(jīng)使用完,那么方案結(jié)束。
圖2 不同節(jié)點(diǎn)數(shù)下3種方案的平均最糟糕基站負(fù)載量(N=1.5Nmin)
圖2給出了當(dāng)給定基站是滿足初始化部署所需基站(即滿足所有節(jié)點(diǎn)吞吐量需求的基站)的1.5倍,即N=1.5Nmin時(shí)候,3種方案在節(jié)點(diǎn)不同情況下,最糟糕基站的負(fù)載量對(duì)比。第2個(gè)圖是在第1個(gè)圖的基礎(chǔ)上,畫(huà)出的最糟糕基站降低量對(duì)比,更能直觀地看出所提算法的優(yōu)勢(shì)。由圖中可以看出,所提方案在最糟糕基站負(fù)載量上均比兩個(gè)方案要優(yōu)。
圖3直觀地反映了所提方案在最糟糕基站負(fù)載量上都比對(duì)比方案分別低,在隨機(jī)部署法對(duì)比中降低率在50%上下,在接入一半法對(duì)比中降低率在10%左右至20%左右,效果十分明顯。
圖3 不同節(jié)點(diǎn)數(shù)下3種方案的平均最糟糕基站負(fù)載降低量(N=1.5Nmin)
原因如下:隨機(jī)部署法存在十分大的偶然性,在初始化部署之后,剩余的基站隨機(jī)放置在節(jié)點(diǎn)需求圓覆蓋的區(qū)域內(nèi),不會(huì)非常準(zhǔn)確地正好落在最糟糕的基站旁邊,所以該方案的最糟糕基站負(fù)載量較大。接入一半法與所提方案在初始化部署和全網(wǎng)節(jié)點(diǎn)接入優(yōu)化All Nodes Optimization前半部分一樣,在滿足節(jié)點(diǎn)吞吐量需求后,將剩余基站輪次放置在最糟糕基站旁邊,分擔(dān)一半的接入節(jié)點(diǎn)。由圖可知,將剩余基站放置在最糟糕的基站旁邊,能有效地降低負(fù)載量。相比較隨機(jī)部署法,接入一半法和所提方案的最糟糕負(fù)載量明顯下降。而在本文所提方案有全網(wǎng)均衡的效果,不僅可以通過(guò)剩余基站降低負(fù)載,也可以通過(guò)已經(jīng)部署好的基站來(lái)分擔(dān)最糟糕基站的負(fù)載量,所以所提方案還要比接入一半法在最糟糕基站負(fù)載量少。
圖4 不同基站數(shù)下接入一半法與所提方案最糟糕基站降低量對(duì)比,K=40
圖4給出了在節(jié)點(diǎn)數(shù)為40,給定不同基站下,即N=aNmin,a∈. {1,1.2,1.4,1.6,1.8,2}的情況下,所提方案與接入一半方案在最糟糕基站下的降低量對(duì)比。降低量先降低后上升再降低,但是始終所提方案的結(jié)果要更優(yōu)。
在a={1,1.2}時(shí),降低量降低,原因如下:在a=1時(shí),接入一半法即為初始化部署,最糟糕的基站位置必然是全網(wǎng)節(jié)點(diǎn)需求圓重疊最高的區(qū)域,且重疊部分的節(jié)點(diǎn)都將接入該基站。而所提方案會(huì)在初始化部署基礎(chǔ)上進(jìn)行優(yōu)化接入,將最糟糕基站的負(fù)載量均衡到其他基站,所以在a=1降低量較高。當(dāng)基站數(shù)目上升時(shí),接入一半法存在剩余基站開(kāi)始均衡最糟糕基站,與所提方案相差減少,所以降低量下降。
在a={1.2,1.4 1.6}時(shí),降低量上升,原因如下:假設(shè)節(jié)點(diǎn)數(shù)40的情況下,最少需要4個(gè)基站,即Nmin=4,初始化部署基站分別接入21、8、8、3,最糟糕基站負(fù)載量為21。在接入一半法下,a=1.2,N=5,將剩余的一個(gè)基站放在最糟糕基站旁邊,均衡一半負(fù)載,此時(shí)所有5個(gè)基站部署結(jié)束,基站負(fù)載量為11、10、8、8、3,最糟糕基站負(fù)載量此時(shí)為11。當(dāng)a=1.4,N=6,基站再增加一個(gè),基站負(fù)載量分別為5、6、10、8、8、3,最糟糕基站負(fù)載量此時(shí)為10。當(dāng)a=1.6,N=7,基站再增加一個(gè),最后結(jié)果為5、6、5、5、8、8、3,最糟糕基站負(fù)載量此時(shí)為8。在所提方案中,初始化部署與接入一半法基站接入相同:21、8、8、3,最糟糕基站負(fù)載量為21。當(dāng)a=1.2,N=5,將剩余的一個(gè)基站放在最糟糕基站旁邊,均衡一半負(fù)載,然后進(jìn)行全網(wǎng)優(yōu)化,基站負(fù)載量為10、10、8、8、4,最糟糕基站負(fù)載量此時(shí)為10。當(dāng)a=1.4,N=6,基站再增加一個(gè),優(yōu)化后基站負(fù)載量分別為9、8、5、6、7、5,最糟糕基站負(fù)載量此時(shí)為9。當(dāng)a=1.6,N=7,基站再增加一個(gè),優(yōu)化后放置最后結(jié)果為7、7、5、5、6、5、5,最糟糕基站負(fù)載量此時(shí)為7。為直觀起見(jiàn)如表1所示。
表1 負(fù)載量比較表
然而隨著基站數(shù)目的不斷增加,新增加的基站幾乎都覆蓋接入了所有接入量較大的基站,所以兩個(gè)方案中每個(gè)基站接入量介于平均,所以降低量減少。
如圖5,在a=1.5,N=1.5Nmin時(shí),即給定的基站是滿足節(jié)點(diǎn)吞吐量需求下基站數(shù)目的1.5倍,可以從圖中清楚地看到,所提方案的方差σ2明顯優(yōu)于兩個(gè)對(duì)比方案,方差越小,說(shuō)明負(fù)載越均衡,且所提方案的方差均能保持在1以下,說(shuō)明每個(gè)基站的負(fù)載量越均衡,也滿足了每個(gè)節(jié)點(diǎn)的吞吐量需求。
隨著節(jié)點(diǎn)數(shù)目的增加,本文的算法與隨機(jī)部署法方差降低量都維持在90%左右,如圖6所示。
圖5 不同節(jié)點(diǎn)數(shù)下3種方案的方差對(duì)比(N=1.5Nmin)
圖6 不同節(jié)點(diǎn)數(shù)下3種方案的方差降低量對(duì)比(N=1.5Nmin)
當(dāng)節(jié)點(diǎn)數(shù)為30,即K=30,給定不同基站數(shù)目,即N=aNmin,a∈{1,1.2,1.4,1.6,1.8,2}下的3種方案方差對(duì)比。一方面,基站越多,所有方差都呈現(xiàn)下降趨勢(shì);另一方面,本文所提方案均能保持一個(gè)較低的方差值,如圖7所示。
圖7 不同基站數(shù)下3種方案的方差對(duì)比(K=30)
圖8 不同基站數(shù)下所提方案與接入一半法的方差降低量對(duì)比(K=30)
圖8是圖7的更直觀表示,更有區(qū)分度地反映了所提方案與接入一半法在這種情況下方差的降低量,即使在給定最小基站數(shù)目?jī)杀兜幕厩闆r下,降低量依然能保持在10%以上。
本文提出了如何在獲得最小化基站個(gè)數(shù)并且滿足每個(gè)節(jié)點(diǎn)的吞吐量需求不少于一個(gè)門(mén)限值條件下,優(yōu)化每個(gè)基站的負(fù)載量的方案,引入最糟糕基站的負(fù)載量和網(wǎng)絡(luò)基站負(fù)載量的方差作為優(yōu)化指標(biāo)。該方案分為兩部分:初始化部署和優(yōu)化部署。初始化部署用最小的基站數(shù)目以滿足節(jié)點(diǎn)的吞吐量需求,優(yōu)化部署的主要目的是達(dá)到負(fù)載均衡。其中,優(yōu)化部署分為4個(gè)模塊,分別為:給定節(jié)點(diǎn)的切換優(yōu)化、給定基站接入節(jié)點(diǎn)的切換優(yōu)化、單個(gè)待移動(dòng)基站的挑選和全網(wǎng)節(jié)點(diǎn)接入優(yōu)化。節(jié)點(diǎn)可以通過(guò)切換需求圓內(nèi)的基站以優(yōu)化每個(gè)基站的接入量,負(fù)載量小的基站可以分擔(dān)負(fù)載量大的基站節(jié)點(diǎn),同時(shí)網(wǎng)絡(luò)中也可以通過(guò)方差來(lái)判斷是否可以挑選出可以移動(dòng)的基站來(lái)均衡全網(wǎng)最糟糕的基站。通過(guò)這些步驟優(yōu)化部署,既要滿足每個(gè)節(jié)點(diǎn)吞吐量限制,也要讓每個(gè)基站負(fù)載量盡可能小。仿真結(jié)果表明,通過(guò)節(jié)點(diǎn)的優(yōu)化接入能夠有效降低網(wǎng)絡(luò)基站負(fù)載量方差,達(dá)到負(fù)載均衡的效果。