田 祎，劉愛(ài)軍，顏 軍，樊景博

（1.商洛學(xué)院經(jīng)濟(jì)管理學(xué)院，陜西商洛 726000；2.商洛市智慧農(nóng)業(yè)技術(shù)與應(yīng)用研究中心，陜西商洛 726000；3.商洛學(xué)院 數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛 726000）

蜂窩網(wǎng)絡(luò)的流量分布隨著時(shí)間和空間發(fā)生波動(dòng)[1-7]，人們提出了多種基站關(guān)閉技術(shù)來(lái)關(guān)閉利用率較低的基站，進(jìn)而節(jié)約能源。文獻(xiàn)[8]提出了一種啟發(fā)式算法。該算法從負(fù)載最低的基站開始，只要出現(xiàn)一個(gè)基站，將其關(guān)閉后，其相鄰基站就無(wú)法為其所有用戶提供服務(wù)，那么該基站便不能關(guān)閉，同時(shí)算法終止。文獻(xiàn)[9]提出該算法的改進(jìn)版本，使算法在決定關(guān)閉哪些基站時(shí)檢查網(wǎng)絡(luò)中的所有基站，避免算法提前終止。文獻(xiàn)[10]提出了一種greedy-add 算法，在滿足所有需求的前提下使開啟的基站數(shù)量最小化。人們還借鑒其他領(lǐng)域的算法來(lái)研究基站的關(guān)閉技術(shù)，比如文獻(xiàn)[11]中基于效用的算法和文獻(xiàn)[12]中的通用算法。然而，關(guān)閉基站不僅取決于基站的自身負(fù)載，還取決于相鄰基站負(fù)載及其關(guān)閉次序等因素。

該文研究了3 種不同的基站排序準(zhǔn)則。仿真結(jié)果表明，與基于當(dāng)前負(fù)載的基站關(guān)閉策略相比，根據(jù)基站服務(wù)的用戶數(shù)量進(jìn)行基站排序可以關(guān)閉更多的基站。且當(dāng)每個(gè)基站的用戶數(shù)量為10 個(gè)或更多時(shí)，該文算法的性能優(yōu)于文獻(xiàn)[9]中的基準(zhǔn)算法。

1 問(wèn)題描述

基站關(guān)閉技術(shù)的目的是在滿足用戶的數(shù)據(jù)速率要求時(shí)關(guān)閉盡可能多的基站。該文通過(guò)使用集合覆蓋理論可以滿足上述目的。

集合覆蓋可以表示為(U,S,C)，其中，U表示n個(gè)元素的全域，S={S1,S2,…,Sm}表示U中m個(gè)子集組成的集合，C={c1,c2,…,cm}表示每個(gè)子集Sk∈S的成本集合。集合覆蓋是指確定S中一組子集使得U中所有元素均包含于至少一個(gè)子集中。集合覆蓋的目的是尋找出一種集合覆蓋S*?S，使成本最小。如果所有子集的成本相同，則問(wèn)題變?yōu)槲醇訖?quán)問(wèn)題(U,S,1)。未加權(quán)集合覆蓋問(wèn)題的目的是在子集{S1,S2,…,Sm}中尋找可以覆蓋U中所有元素的一種最小組合。

無(wú)線傳感器網(wǎng)絡(luò)的集合覆蓋在一定程度上與基站關(guān)閉技術(shù)類似。二者目的均是以最少集合覆蓋相同點(diǎn)。然而，將基站關(guān)閉問(wèn)題部署為集合覆蓋問(wèn)題后，其步驟不同于無(wú)線傳感器網(wǎng)絡(luò)。首先，在基站關(guān)閉問(wèn)題中，基站容量是重要約束條件，但是在無(wú)線傳感器網(wǎng)絡(luò)中數(shù)據(jù)傳輸速率較低，因此不存在基站容量約束。其次是覆蓋模式。將無(wú)線傳感器網(wǎng)絡(luò)的覆蓋區(qū)域假設(shè)為圓形區(qū)域[13]，但是在基站關(guān)閉問(wèn)題中，由于障礙物、反射和衍射等因素導(dǎo)致遮蔽效應(yīng)，因此其覆蓋區(qū)域不是圓形區(qū)域。最后是對(duì)節(jié)能機(jī)制的需求。無(wú)線傳感器網(wǎng)絡(luò)由于能量稀少，因此必須進(jìn)行節(jié)能，而蜂窩網(wǎng)絡(luò)是可以進(jìn)行節(jié)能的。

CSO 問(wèn)題可被建模為一種（U,S,1）集合覆蓋問(wèn)題并將其表述為最小化活躍基站數(shù)量，如式（1）所示。（U,S,1）中，U表示網(wǎng)絡(luò)中的用戶設(shè)備集合，S表示隸屬于同一基站的用戶設(shè)備子集，1 表示該問(wèn)題為未加權(quán)集合覆蓋問(wèn)題。

約束條件為：

式（2）是容量約束，它表示被基站j覆蓋的UE子集包含于其服務(wù)集合Sj中，以便需求之和不會(huì)超過(guò)總帶寬Wj；式（3）表示需求分割的概率。在基站關(guān)閉方法中，單個(gè)基站必須滿足所有用戶設(shè)備的需求，這稱為不可分割需求。式（4）表示需求的類型。對(duì)于容量受限集合覆蓋，用戶設(shè)備i要求所有基站的需求bi相同。然而，在蜂窩網(wǎng)絡(luò)中，用戶設(shè)備i的需求即帶寬需求，隨著提供服務(wù)的基站不同而不同，將其稱為差異化需求。因此，需要使用標(biāo)記法bij來(lái)區(qū)別每個(gè)基站j的不同帶寬需求。雖然有多種算法可以求解容量受限的集合覆蓋問(wèn)題[14]，但是這些算法的針對(duì)性太強(qiáng)，不適用于差異化需求場(chǎng)景，因此無(wú)法采用這些算法。

2 該文算法

該文提出一種雙階段集中式算法。第一階段主要負(fù)責(zé)確定實(shí)施約束式（2）的服務(wù)集合。為了確定基站j的服務(wù)集合Sj，首先需要將Mj的用戶設(shè)備加入Sj，然后從需求量bi×j最低的用戶設(shè)備i*開始，從Nj中添加新的用戶設(shè)備，進(jìn)而隨機(jī)填滿基站帶寬Wj。獲得服務(wù)集合S={S1,S2,…,Sm}后算法終止，其中，m表示網(wǎng)絡(luò)中的基站數(shù)量。

在第二階段，根據(jù)第一階段求得的服務(wù)集S，在開始時(shí)假設(shè)所有基站均被關(guān)閉，且所有用戶設(shè)備沒(méi)有相連。在每次迭代時(shí)，選擇將被開啟的基站j*?；颈贿x擇的次序（基站排序）對(duì)將來(lái)的基站關(guān)閉決策具有重大影響。常見(jiàn)的做法是根據(jù)其當(dāng)前負(fù)載選擇一個(gè)基站。然而，關(guān)閉基站不僅取決于基站的自身負(fù)載，還取決于相鄰基站的可用帶寬及用戶設(shè)備與其他基站間的信道質(zhì)量等因素。因此，文中研究了3 種不同的基站排序準(zhǔn)則，分析了它們對(duì)最終關(guān)閉基站數(shù)量的影響。3 種基站排序準(zhǔn)則內(nèi)容如下：

1）最大負(fù)載：在該情況下，選擇的下一基站是負(fù)載最高的基站。根據(jù)它們的負(fù)載來(lái)選擇基站是文獻(xiàn)中的常見(jiàn)做法。

2）最多用戶：此時(shí)，選擇的下一基站是接收其服務(wù)的未連接用戶設(shè)備數(shù)量最大的基站。

3）最多中心：此時(shí)，選擇的下一基站是中心用戶設(shè)備數(shù)量最多的基站。這一準(zhǔn)則強(qiáng)調(diào)選擇含有信道質(zhì)量較優(yōu)的、用戶設(shè)備數(shù)量最大的基站。如果基站的信道二元性較優(yōu)，則表明該信道不如其他基站，因此，需要相對(duì)較多的資源滿足其要求。如果wij≥wth,則對(duì)基站j來(lái)說(shuō)，用戶設(shè)備i為中心用戶設(shè)備，其中，wth表示中心用戶設(shè)備的頻譜效率，且假設(shè)為10 bps/Hz。

選擇開啟基站j*后，將其服務(wù)集中的所有用戶設(shè)備{S}j*加入集合V，并相應(yīng)更新分配矩陣X。每次迭代時(shí)，根據(jù)更新后的V和X調(diào)用第一階段算法來(lái)更新服務(wù)集。當(dāng)所有用戶設(shè)備連接后終止算法。最后，集合L中的基站將保持活躍狀態(tài)，而所有其他基站將被關(guān)閉。

3 實(shí)驗(yàn)評(píng)估

對(duì)采取全向天線方向圖且含有100 個(gè)基站的蜂窩網(wǎng)絡(luò)進(jìn)行下行鏈路分析。根據(jù)文獻(xiàn)[15]中的評(píng)估準(zhǔn)則，通過(guò)模擬城市小型基站場(chǎng)景來(lái)表示小型基站環(huán)境。在城市小型基站場(chǎng)景中由于存在建筑物，所以視線信號(hào)不是該環(huán)境下的常用路徑。根據(jù)兩種路徑損失模型（視線模型和非視線模型）及各種模型的概率來(lái)計(jì)算路徑損失。頻率復(fù)用為1，也就是說(shuō)，每個(gè)基站使用整個(gè)頻譜。表1 給出了必要的仿真參數(shù)。站點(diǎn)間的距離（基站規(guī)模）和傳輸功率對(duì)應(yīng)于小型基站的值。設(shè)置每個(gè)基站的用戶設(shè)備數(shù)量及其速率要求，以使網(wǎng)絡(luò)的負(fù)載較低，這也是基站關(guān)閉技術(shù)的典型場(chǎng)景。

表1 仿真參數(shù)

在仿真時(shí)，假設(shè)每個(gè)基站的覆蓋集合包括區(qū)域內(nèi)的所有用戶設(shè)備。因?yàn)槭袇^(qū)微小區(qū)場(chǎng)景下基站部署較密，因此這一假設(shè)是合理的。為了降低問(wèn)題難度，假設(shè)通過(guò)干擾管理技術(shù)來(lái)管理基站之間的干擾。如果考慮基站之間的干擾，則算法的拓展也很簡(jiǎn)單，算法結(jié)果從本質(zhì)上講與圖1 和圖2 非常類似。因此，根據(jù)用戶設(shè)備i和基站j間的信噪比SNRij計(jì)算頻譜效率wij，如式（5）：

圖1 該文算法和文獻(xiàn)[9]基準(zhǔn)算法的節(jié)能性能比較

圖2 不同基站排序準(zhǔn)則時(shí)的節(jié)能效果

該文算法屬于集中式算法，此時(shí)所有基站與一個(gè)中央實(shí)體（云）相連，且該實(shí)體含有所有用戶設(shè)備和所有基站間的SINR 全局信息。仿真運(yùn)行100 次，每次運(yùn)行時(shí)區(qū)域內(nèi)的用戶設(shè)備被隨機(jī)丟棄。被關(guān)閉的基站平均數(shù)量取100 次仿真的均值。節(jié)能效果與被關(guān)閉的基站數(shù)量呈線性比例關(guān)系。這是因?yàn)榛炯词箾](méi)有傳輸數(shù)據(jù)也會(huì)消耗大量能量，所以用于傳輸數(shù)據(jù)的能量可能被忽略。在部署的100 個(gè)基站中，節(jié)能比等于被關(guān)閉的基站，也就是說(shuō)，關(guān)閉30 個(gè)基站對(duì)應(yīng)于30%的節(jié)能效果。

將該文算法與文獻(xiàn)[9]中的greedy-drop 基準(zhǔn)算法進(jìn)行比較，結(jié)果如圖1 所示。該圖X軸表示每個(gè)基站的用戶設(shè)備數(shù)量，Y軸表示節(jié)能效果。為了比較的公平性，使用相同的最大負(fù)載基站排序準(zhǔn)則，根據(jù)基站負(fù)載來(lái)運(yùn)行兩種算法。當(dāng)每個(gè)基站的用戶設(shè)備數(shù)量較少，只有5 個(gè)用戶設(shè)備時(shí)，基準(zhǔn)算法的性能略優(yōu)于該文算法。然而，當(dāng)每個(gè)基站的用戶設(shè)備數(shù)量增加到10 個(gè)甚至更多時(shí)，該文算法的性能優(yōu)于基準(zhǔn)算法，當(dāng)基站的用戶設(shè)備數(shù)量為25 個(gè)時(shí)，該文算法的節(jié)能效果高出20%，之所以取得這樣的性能提升，是因?yàn)間reedy-add 策略相對(duì)于greedy-drop 具有性能優(yōu)勢(shì)。對(duì)于greedy-drop 算法，在將基站關(guān)閉前，其用戶設(shè)備需被移交。這可能導(dǎo)致其他基站的帶寬無(wú)法獲得100%的應(yīng)用。因此，此時(shí)的重點(diǎn)是清除基站負(fù)載而不是試圖使部分基站中的負(fù)載最大化。另一方面，greedy-add 方法在將基站打開前，盡力使基站負(fù)載最大，以便將所有基站的負(fù)載集中起來(lái)。在使用該文greedy-add 算法時(shí)，這種基站負(fù)載最大化做法可提高被關(guān)閉基站的數(shù)量。

圖2 給出了使用3 種基站排序準(zhǔn)則時(shí)的節(jié)能效果。從圖中可見(jiàn)，選擇何種排序準(zhǔn)則對(duì)實(shí)現(xiàn)的節(jié)能效果具有重大影響。無(wú)論每個(gè)基站的用戶設(shè)備數(shù)量如何，最大負(fù)載和最多中心準(zhǔn)則的性能均比較接近。然而，最多用戶準(zhǔn)則在節(jié)能方面的性能要優(yōu)于其他兩種準(zhǔn)則。無(wú)論每個(gè)基站的用戶設(shè)備數(shù)量如何，性能差異始終維持在5%左右。這一性能差異的原因如下：在最多用戶準(zhǔn)則中，根據(jù)基站可能服務(wù)的用戶設(shè)備數(shù)量來(lái)確定下一個(gè)將被開啟的基站。因此，選擇過(guò)程考慮了該基站在將來(lái)為未連接用戶設(shè)備提供服務(wù)時(shí)做出的貢獻(xiàn)。然而，對(duì)最大負(fù)載策略，選擇過(guò)程基于基站的當(dāng)前負(fù)載，沒(méi)有考慮基站對(duì)未連接用戶設(shè)備做出了多少貢獻(xiàn)。在后一種情況中，被選擇的基站可能不是最優(yōu)基站，因?yàn)樗鼪](méi)有為未連接用戶設(shè)備做出較多貢獻(xiàn)。

4 結(jié)束語(yǔ)

基站關(guān)閉方法通過(guò)關(guān)閉部分基站可有效節(jié)約蜂窩網(wǎng)絡(luò)的能量。當(dāng)前大多數(shù)基站關(guān)閉部署算法根據(jù)基站的當(dāng)前負(fù)載來(lái)關(guān)閉基站。然而，關(guān)閉步驟會(huì)受到基站關(guān)閉次序（基站排序）的影響。因此，在文中研究了3 種不同的基站排序準(zhǔn)則，比較了它們對(duì)總體節(jié)能效果的影響。仿真結(jié)果表明，根據(jù)基站能夠服務(wù)的用戶設(shè)備數(shù)量來(lái)關(guān)閉基站，這一準(zhǔn)則的性能要優(yōu)于其他基站排序準(zhǔn)則。此外，將基站關(guān)閉方法表述為集合覆蓋問(wèn)題?；谶@一表述，提出了基站關(guān)閉方法的一種greedy-add 算法。經(jīng)證明，當(dāng)每個(gè)基站的用戶設(shè)備數(shù)量較多時(shí)，該算法性能優(yōu)于改進(jìn)型Cell-Zooming 基準(zhǔn)算法。