蜂窩網(wǎng)絡(luò)中基于集合覆蓋的基站節(jié)能技術(shù)研究

田 祎，劉愛軍，顏 軍，樊景博

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

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

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

1 問題描述

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

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

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

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

約束條件為：

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

2 該文算法

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

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

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

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

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

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

3 實驗評估

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

表1 仿真參數(shù)

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

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

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

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

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

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

4 結(jié)束語

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