基于最佳候選的蜂窩網(wǎng)絡(luò)低能耗基站部署算法

，

(湖北大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，武漢 430064)

0 引言

在過去的二十年里，隨著智能手機(jī)和移動(dòng)應(yīng)用的不斷普及，無線移動(dòng)蜂窩網(wǎng)絡(luò)的需求已經(jīng)增加到意想不到的水平。為了滿足這樣的增加需求，網(wǎng)絡(luò)運(yùn)營(yíng)商采用了多種解決方案，比如擴(kuò)展頻譜，增加單位面積的節(jié)點(diǎn)密度以及增加部署[1]。由于區(qū)間干擾的原因，蜂窩網(wǎng)絡(luò)中宏基站過多增加會(huì)顯著降低增益。更多基站的部署會(huì)增加網(wǎng)絡(luò)能量消耗，這也是導(dǎo)致溫室氣體排放增加的一個(gè)非常重要的原因。最終，綠色環(huán)保蜂窩通信吸引了大家的注意[2-3]。綠色環(huán)保蜂窩通信的主要目的是在滿足用戶需求的同時(shí)也盡可能地降低能量消耗。降低能量消耗也會(huì)降低維護(hù)費(fèi)用以及增加了移動(dòng)用戶的電池使用壽命[4]。

針對(duì)異構(gòu)無線蜂窩網(wǎng)絡(luò)的研究大都集中在能量控制和資源分配[5-6]。然而，很少有文獻(xiàn)涉及微基站部署和能量效率問題。文獻(xiàn)[7]提出通過增加低功率基站部署以便將網(wǎng)絡(luò)中斷頻率降至最低，該方法首先是對(duì)網(wǎng)絡(luò)區(qū)域部署一定數(shù)量的微基站，并反復(fù)改變這些基站的位置?；谙到y(tǒng)的特點(diǎn)，其路徑損耗是嚴(yán)格依賴于基站的位置。盡管該算法對(duì)于測(cè)試案例有效，但是在實(shí)際基站結(jié)構(gòu)中每次迭代均需要獲取這些參數(shù)，這是很難做到的。文獻(xiàn)[8]研究了關(guān)于微基站部署頻譜效率問題，提出在一個(gè)宏基站覆蓋的區(qū)域內(nèi)部署微基站以增加網(wǎng)絡(luò)區(qū)域頻譜效率(area spectral efficiency，ASE)。該方法通過選擇網(wǎng)格邊界來進(jìn)行基站候選位置選擇，然后提出用貪婪算法來選擇微基站。該算法重復(fù)執(zhí)行，一直到達(dá)到系統(tǒng)AES需求。然而，如果將網(wǎng)絡(luò)的能量效率列入考慮范圍的話，網(wǎng)格邊界也是并不是最好的候選點(diǎn)。此外，用戶的分布會(huì)影響網(wǎng)絡(luò)的能量效率，而文獻(xiàn)[8]提出的算法如果在集群用戶分布情況下，效果會(huì)很差。

為了解決以上這個(gè)局限性，本文提出了一種基于最佳候選的低能耗基站部署算法。該方法不會(huì)受到用戶分布的影響，可以在群集網(wǎng)絡(luò)或者分散網(wǎng)絡(luò)執(zhí)行。此外，該算法考慮到了候選點(diǎn)的可行性，同時(shí)也將環(huán)境影響降至最低。而且，該算法可以應(yīng)用于六角網(wǎng)格或是實(shí)際基站結(jié)構(gòu)，在滿足網(wǎng)絡(luò)容量增加需求的同時(shí)也可以將網(wǎng)絡(luò)能量效率最大化。最后通過大量的實(shí)驗(yàn)驗(yàn)證得出，本文提出的算法在滿足網(wǎng)絡(luò)容量的同時(shí)不僅增加了能量效率還增加了網(wǎng)絡(luò)總流量，中負(fù)載能量效率具有較大的提高。

1 系統(tǒng)模型

假設(shè)無線網(wǎng)絡(luò)所有移動(dòng)用戶都由宏基站和微基站提供服務(wù)，分別由BM和Bm表示。M代表宏基站,m代表微基站。B代表基站，也就是說B=BM∪Bm。移動(dòng)用戶與基站聯(lián)系在一起，基站在用戶位置為其提供最高信號(hào)強(qiáng)度。如果在用戶所處位置有多個(gè)基站提供的相同強(qiáng)度的信號(hào)，用戶隨意選擇其中一個(gè)基站。我們假設(shè)移動(dòng)用戶時(shí)常有數(shù)據(jù)需要發(fā)送，從而他們需要一個(gè)帶寬分配。宏蜂窩聯(lián)系用戶k的信號(hào)噪聲干擾比(signal-to-interference-plus-noise ratio，SINR)可以用以下公式表示：

(1)

(2)

(3)

傳統(tǒng)宏基站可以提供更好的覆蓋率和數(shù)據(jù)率，然而與微基站相比它們明顯消耗更高的能量。此外，在密集部署網(wǎng)絡(luò)中，由于區(qū)間干擾增益大幅度降低。另外一方面，微基站傳輸功率明顯不如宏基站，所以其覆蓋更小的范圍。然而，與宏基站相比微基站消耗更少的能量而且也不會(huì)與其他傳輸相互干擾。所以與宏基站相比，微基站更加高效節(jié)能，尤其是對(duì)于密集部署網(wǎng)絡(luò)。因此，在本文研究中，我們將微基站部署作為宏基站的支撐，以最大化網(wǎng)絡(luò)能量效率來滿足流量需求。

基站能量消耗由兩個(gè)部分組成：第一部分是沒有傳輸時(shí)候的靜態(tài)功耗；第二部分功耗取決于基站傳輸功耗?，F(xiàn)有文獻(xiàn)中有許多功耗模型[10-11]。本文中，我們采用中提及的功耗模式，如下所示：

PM=P0,M+ΔMPtx

Pm=P0,m+ΔmPtx

(4)

以上公式中，PM，Pm，Ptx分別代表每個(gè)宏基站的平均消耗功率，每個(gè)微基站的平均消耗功率和平均傳輸耗能。ΔM和Δm是由負(fù)載決定的傳輸功率參數(shù)。P0,M和P0,m分別表示宏基站和微基站靜態(tài)功耗。

如上所述，我們假設(shè)數(shù)據(jù)總是以全緩沖傳輸。此外，不用任何能量控制算法。所以，基站將完全被利用，ΔM和Δm為恒定，那么，網(wǎng)絡(luò)能量效率可以通過以下公式表示：

(5)

公式中，NB和Nb分別代表的是宏基站和微基站的數(shù)量。

2 問題描述

網(wǎng)絡(luò)運(yùn)營(yíng)商想要通過額外增加基站以達(dá)到改善網(wǎng)絡(luò)容量的目的來滿足增加的流量需求。為了將網(wǎng)絡(luò)能量效率最大化以及限制資本支出和運(yùn)營(yíng)支出，網(wǎng)絡(luò)運(yùn)營(yíng)商將微基站部署于最佳位置。在現(xiàn)實(shí)生活中，用戶是移動(dòng)的，而且用戶分布存在很多不同的可能性。在高峰期的幾個(gè)小時(shí)，用戶活躍，網(wǎng)絡(luò)總?cè)萘窟_(dá)到最大值。但是，絕大部分時(shí)間里基站并未得到充分利用。然而，即便大多數(shù)時(shí)間中網(wǎng)絡(luò)流量需求低，仍然需要部署額外的基站以滿足高峰期時(shí)候流量需求。對(duì)于非高峰期來說，現(xiàn)存的基站已經(jīng)足夠，額外增加基站是為高峰期時(shí)候?qū)α髁康男枨?。所以，運(yùn)營(yíng)商部署應(yīng)該考慮高峰期時(shí)候用戶的分布問題。下面，我們將部署問題公式化：

maxπrηEE(B)

(6)

式中，Cr代表當(dāng)場(chǎng)景r只部署宏基站時(shí)的網(wǎng)絡(luò)容量；乘數(shù)λ≥1為期望容量；πr為場(chǎng)景r出現(xiàn)的幾率；R和Kr分別表示場(chǎng)景的集合和場(chǎng)景r下用戶的集合。

研究出基站最佳數(shù)量以及基站最佳位置是極為復(fù)雜的問題。能量效率基站部署與設(shè)施選址問題之間的關(guān)系很明確。簡(jiǎn)化這個(gè)問題的方法為在網(wǎng)絡(luò)區(qū)域選擇一組基站候選點(diǎn)。我們應(yīng)該合理地選擇這些候選點(diǎn)以改善算法的性能。選定這些候選點(diǎn)以后，第二步將是在這些候選點(diǎn)中選擇最佳基站點(diǎn)。當(dāng)場(chǎng)景和候選點(diǎn)較復(fù)雜時(shí)，問題變得很困難。所以，提出了貪婪算法，將在下一部分中闡述。

3 提出的最佳候選和貪婪算法

在這部分，我們首先介紹候選點(diǎn)選擇和貪婪部署算法，然后討論其性能。

3.1 候選點(diǎn)選擇策略

如上節(jié)所述，文獻(xiàn)[8]提出方法并未考慮到用戶的分布，效果會(huì)很差，尤其是當(dāng)用戶聚集于宏基站附近時(shí)候。此外，由于地形和結(jié)構(gòu)的限制，這些位置也許并不能作為基站部署使用。另外一種方法是選擇全部可行位置作為候選點(diǎn)。然而，取決于網(wǎng)絡(luò)規(guī)模，這樣的位置可能數(shù)不清，即使執(zhí)行啟發(fā)式算法都不切實(shí)際。所以，所以明智的做法是淘汰一些可行的位置以改進(jìn)算法的性能。為了克服這些問題，我們將網(wǎng)絡(luò)區(qū)域劃分為平等的網(wǎng)格，然后在每個(gè)網(wǎng)格里選擇候選點(diǎn)。不管對(duì)于集群或是分散網(wǎng)路，這個(gè)方法都可以有效執(zhí)行。但是，這也不能保證每個(gè)網(wǎng)格都存在可行位置。此外，如果一個(gè)網(wǎng)格中存在不止一個(gè)可行位置，從中選擇候選址又成為了另外一個(gè)問題，需要解決。所以，我們提出了以下方法。以6個(gè)網(wǎng)格區(qū)域?yàn)槔?，如果中心網(wǎng)格的所有相鄰網(wǎng)格存在至少一個(gè)可行位置，那么選擇中心網(wǎng)格作為選取區(qū)域，最接近于選取區(qū)域中心的那一個(gè)位置作為候選點(diǎn)。假如有些相鄰網(wǎng)格不存在可行位置，那么中心網(wǎng)格與和無可行位置的相鄰網(wǎng)格組成一個(gè)選取區(qū)域，距離選取區(qū)域中心最近的可行位置被選擇作為候選點(diǎn)。圖1顯示了一個(gè)場(chǎng)景案例。

如圖1所示，可行位置，候選點(diǎn)，區(qū)域中心分別由空三角形，實(shí)三角形，X表示。在圖1(a)的第一種情況中，所有相鄰的網(wǎng)格都有至少一個(gè)可行位置。所以，我們選擇最接近選取區(qū)域中心的作為候選點(diǎn)。在圖1(b)的第二種情況中，有三個(gè)相鄰網(wǎng)格沒有可行位置。所以，我們選擇最接近選取區(qū)域中心的可行位置作為候選點(diǎn)。這種方法限制了用戶分布對(duì)于本文提出方法性能的影響。

圖1 候選點(diǎn)選擇案例

3.2 貪婪部署算法

我們提出的貪婪算法在每次迭代中選擇一個(gè)微基站去部署。該算法選擇能夠在所有場(chǎng)景中實(shí)現(xiàn)能量效率最大化的候選微基站作為下一個(gè)微基站。這個(gè)過程一直持續(xù)到所有需要容量得到滿足。在每次迭代中，該算法假設(shè)之前選定的微基站已經(jīng)部署，然后計(jì)算出能量效率。這個(gè)辦法明顯降低了算法的復(fù)雜性。最優(yōu)解復(fù)雜度增加。|R|和|BC|，其中|BC|代表基站候點(diǎn)集合。提出算法適用于許多不同類型的基站部署問題，比如微微基站和家庭基站。提出算法步驟如下：

1：初始化Bm=φ以及ηEE(B) =ηEE(BM)

3：B=BM∪Bm

5：Bm←Bm∪b

6：BC←BC

7：end while

提出算法為貪婪啟發(fā)式算法。所以，這不能保證得到的為最佳解。但是如果貪婪算法滿足1)ηEE(φ)=0；2)ηEE不減少；3)ηEE為子模，那么該算法比最優(yōu)解優(yōu)秀(e-1)/e倍。能量效率函數(shù)不符合條件2。 然而，在文獻(xiàn)[8]中，顯示ASE滿足這三個(gè)特性。所以，如果我們假設(shè)滿足約束的微基站部署數(shù)量與最優(yōu)解相等，那么ηEE比最優(yōu)解好(e-1)/e倍。

4 仿真實(shí)驗(yàn)結(jié)果

首先研究網(wǎng)格數(shù)量和活躍用戶數(shù)量對(duì)該算法效果的影響。然后將該算法與文獻(xiàn)[8]和文獻(xiàn)[11]做對(duì)比。圖2顯示了一個(gè)宏基站部署示例場(chǎng)景，包括一組微基站候選點(diǎn)和用戶分布。10個(gè)宏基站部署于10×10 km2仿真區(qū)域。為了避免邊緣效應(yīng)，如文獻(xiàn)[8]一樣，我們收集中心5×5 km2數(shù)據(jù)。為簡(jiǎn)單起見，我們假設(shè)存在15種不同的場(chǎng)景，幾率均等。為了觀察活躍用戶對(duì)于該算法性能的影響，我們創(chuàng)造3種不同場(chǎng)景：低負(fù)載，中負(fù)載和高負(fù)載。5個(gè)場(chǎng)景為低載，其中30個(gè)活躍用戶；5個(gè)場(chǎng)景為中負(fù)載，其中100個(gè)活躍用戶；5個(gè)場(chǎng)景為負(fù)載，其中200個(gè)活躍用戶。所有這些場(chǎng)景中，用戶分布均勻。仿真模式和參數(shù)如表1所示。我們假設(shè)宏基站采用扇形天線，而微基站采用全向天線。本文不研究多頻天線傳輸。宏基站和微基站的傳輸與操作功率如表2所示。

在圖3中，我們研究網(wǎng)格數(shù)量對(duì)于提出算法性能的影響。首先我們使用4個(gè)網(wǎng)格，直到增加到65536。當(dāng)網(wǎng)格數(shù)量達(dá)到1024時(shí)候，該算法的性能明顯得到改善。網(wǎng)格數(shù)量從1024增加到65536，算法能量效率改善了1%。然而由于增加了候選點(diǎn)，算法的復(fù)雜度也相應(yīng)增加了。在一定數(shù)量網(wǎng)格以后，再增加網(wǎng)格的數(shù)量并不能改善算法的性能，反而需要更長(zhǎng)的時(shí)間。

表1 仿真參數(shù)

圖2 仿真示例場(chǎng)景

基站類型PM/WPm/W宏基站20W865-微基站1W-38

圖3 隨著網(wǎng)格尺寸增加時(shí)平均能量效率的變化

在圖4中，我們將三種用戶情形類型進(jìn)行了比較，網(wǎng)格數(shù)量為1024。當(dāng)網(wǎng)絡(luò)活躍用戶增加，需要更多微基站部署以將能量效率最大化。當(dāng)微基站數(shù)量分別為8,20和28，而部署情形分別為低負(fù)載，中負(fù)載和高負(fù)載時(shí)候，網(wǎng)絡(luò)能量效率達(dá)到最大化。預(yù)計(jì)在高峰期間網(wǎng)絡(luò)活躍用戶數(shù)量將增加。所以，可以增加更多微基站部署。此外，更多活躍用戶使用網(wǎng)絡(luò)也更加高效節(jié)能。

圖4 隨著活躍用戶數(shù)量增加時(shí)能量效率的變化

圖5和圖6顯示了提出算法與文獻(xiàn)[8]、文獻(xiàn)[11]中算法的性能比較結(jié)果，具體對(duì)比了能量效率和網(wǎng)絡(luò)總?cè)萘扛纳菩Ч?。三種算法最初都不含微基站，每次迭代中部署一個(gè)基站。這個(gè)仿真中，我們考慮中負(fù)載情形。網(wǎng)格選擇1024。隨著微基站數(shù)量的增加，網(wǎng)絡(luò)總流量直線上升。另一方面，能量效率上升到一定點(diǎn)然后開始下降。圖5中當(dāng)λ=1.5，提出算法需要10個(gè)微基站，三個(gè)算法都達(dá)到最大值時(shí)候，相比其他兩種算法，本文提出算法總?cè)萘糠謩e提高了24%和34%。同樣，在圖6中，本文提出算法能量效率也分別提高了約26%和36%。

圖5 網(wǎng)絡(luò)總?cè)萘?/p>

圖6 系統(tǒng)能量效率

5 結(jié)論

提出了一種基于最佳候選和貪婪算法的低能耗基站部署算法，以改善網(wǎng)絡(luò)能量效率。提出算法首選合理策略選擇一組可行的微基站位置，然后通過貪婪算部署基站直到網(wǎng)絡(luò)總?cè)萘啃枨蟮玫綕M足。由于該算法為啟發(fā)算法，算法復(fù)雜度較低。仿真試驗(yàn)證明該提議算法在滿足網(wǎng)絡(luò)容量的同時(shí)不僅增加了能量效率還增加了網(wǎng)絡(luò)總流量。

參考文獻(xiàn)：

[1] Feng D, Jiang C, Lim G, et al. A survey of energy-efficient wireless communications[J]. IEEE Communications Surveys & Tutorials, 2013, 15(1):167-178.

[2] Bianzino A P, Chaudet C, Rossi D, et al. A survey of green networking research[J]. IEEE Communications Surveys & Tutorials, 2012, 14(1):3-20.

[3] Mastronarde N, Mihaela V D S. Fast reinforcement learning for energy-efficient wireless communication[J]. IEEE Transactions on Signal Processing, 2013, 59(59):6262-6266.

[4] Nan G F, Chen Z N. Deployment algorithm of mobile sensing nodes based on evolutionary optimization[J]. Tien Tzu Hsueh Pao/acta Electronica Sinica, 2012, 40(5):1017-1022.

[5] 李俊伶, 蘇寒松, 朱世兵,等. LTE家庭基站部署中的下行功率控制[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015, 51(20):86-90.

[6] 李偉平. 4G小型化基站部署策略與工程應(yīng)用分析[J]. 電信科學(xué), 2015(S1):1-4.

[7] Son K, Oh E, Krishnamachari B. Energy-efficient design of heterogeneous cellular networks from deployment to operation[J]. Computer Networks, 2015, 78:95-106.

[8] Son K, Oh E, Krishnamachari B. Energy-aware hierarchical cell configuration: From deployment to operation[A]. Computer Communications Workshops[C]. 2011:289-294.

[9] Hossain M F, Munasinghe K S, Jamalipour A. Distributed Inter-BS Cooperation Aided Energy Efficient Load Balancing for Cellular Networks[J]. IEEE Transactions on Wireless Communications, 2013, 12(11):5929-5939.

[10] Hossain M F, Munasinghe K S, Jamalipour A. Traffic-aware two-dimensional dynamic network provisioning for energy-efficient cellular systems[J]. Transactions on Emerging Telecommunications Technologies, 2014, 27(3):357-372.

[11] Oh E, Son K, Krishnamachari B. Dynamic Base Station Switching-On/Off Strategies for Green Cellular Networks [J]. IEEE Transactions on Wireless Communications, 2013, 12(5):2126-2136.