基于遺傳算法的最大化公平性基站主動存儲方案*

宋財華，祝向輝，游菊芬，萬建云

（三川智慧科技股份有限公司，江西 鷹潭 335000）

0 引 言

近年來，移動設備用戶的迅速增長和云服務的興起，對移動運營商網絡中的高效資源訪問提出了巨大挑戰。隨著各種移動智能終端的普及和迅速發展，用戶對移動通信網絡的需求除了傳統所需的語音業務外，視頻、圖片、實時通信等各個媒體業務也成為了移動通信的主流。全球范圍內思科可視化網絡指數（VNI）統計[1]，到2021年，Wi-Fi和移動設備的流量將占總IP流量的63%以上，其中移動設備占17%，Wi-Fi占46%，智能手機流量將超過PC流量。以下是思科公司做出的統計[1]。

（1）在全球范圍內，移動數據流量在2016年至2021年將增長7倍。移動數據流量在2016年至2021年期間以46%的復合年增長率增長，到2021年達到48.3 EB/月，固定IP流量在2016年至2021年期間以21%的復合年增長率增長。

（2）2016年至2021年，全球移動數據流量增長速度是固定IP流量的2倍。2016年全球移動數據流量占年全部IP流量的7%，而2021年占全部IP流量的17%。

考慮到這些問題，研究人員意識到，可以,利用基站或手機的資源存儲能力，把熱點數據存儲在基站或手機等邊緣設備中，減小用戶與數據資源的距離，使得系統具有更好的可用性、更穩定的連接性和更小的延遲，這是無線網絡邊緣存儲服務的最初構想。研究人員經過大量的研究，證明這個想法對于商業環境是實用的[2-3]。邊緣存儲包括基站存儲、移動設備存儲等，本文主要研究基站存儲。所謂基站存儲，就是將數據存儲在基站。也就是說，基站被假定為具有大的存儲容量來存儲將被訪問的熱數據。這些小型基站形成無線分布式高速緩存網絡。由于小基站和請求設備之間的距離很短，緩存文件的傳輸可以非常有效地完成[4]。基站主動存儲作為邊緣存儲的一種存儲方式，具有以下良好性能。

（1）低時延和高QoS。基站主動存儲是一個分布式系統，通過將數據存儲在邊緣網絡的基站中，盡可能將資源內容接近用戶。用戶通過本地基站直接獲得所需要的資源，大大減少了網絡獲取內容的時延，有助于改善用戶體驗。

（2）可擴展性。基站主動存儲有很好的擴展性。這種擴展性是指具有存儲功能的基站能在現有基站設施的基礎上直接擴展，或者當出現新的具有存儲功能的基站時可以與原來的基站兼容。新的具有存儲功能的基站必須有協作機制模塊，負責允許新的基站加入全局緩存系統并訪問公共資源，以提供靈活性。

（3）減少網絡帶寬的使用。當移動用戶通過基站連接到移動運營商網絡時，應用數據必須通過移動運營商的網絡返回到移動網絡的網關才能到達廣域網，網關連接到Internet回程。互聯網回程的帶寬使用是移動網絡數據業務的主要成本之一。為了減少帶寬使用，基站主動存儲系統將緩存數據保存在全局緩存集群內部。之后，如果有用戶發送相同的請求，將直接從基站獲取資源，而不是從數據源或附近的內容分發網絡（Content Delivery Network，CDN）服務器請求它，從而大大降低了網絡帶寬的使用。

因此，基站主動存儲為滿足新出現的實時、交互式的媒體服務所要求的服務質量提供了新的思路。在網絡邊緣使用協作緩存，使得數據本地化，有助于平衡網絡負載。利用基站可以在移動用戶接近的網絡邊緣部署協作緩存方案，把原數據網絡中下載內容的時間和將內容傳遞給移動用戶的時間分離，節省了網絡回程資源，同時減少了延遲，提高了服務質量。

在基站中進行數據緩存是一種新興的網絡技術，有許多問題需要考慮，其中最關鍵的問題是數據資源的存儲分配。盡管眾多學者對資源分配問題進行了研究，并考慮從各個方面提升系統的性能，但是還有許多方面未考慮其中，如公平性。基站主動存儲的資源分配仍然是個不太成熟的領域，發展前景十分廣闊，需要進一步的研究和探討。本文研究基站主動存儲中資源分配的問題，在大量總結國內外已有論文的成果上，重點考慮提升資源分配的用戶公平性，對理論和實際都有一定的意義。

1 系統模型

1.1 基站主動存儲網絡模型

開展研究前，需確定基站主動存儲系統的構架。本文研究將數據存儲在小基站（Small Base Station）中，研究的系統構架如圖1所示，并假設如下：

（1）一個蜂窩通信系統內有許多小型基站，服務大量終端用戶，這些基站位置固定；

（2）小基站具有存儲能力，能夠主動發現一段時間內流行的數據并進行主動存儲；

（3）小基站之間具有通信能力，能夠互相訪問對方存儲的數據。

本文不研究基站應該緩存哪些數據，而是研究在確定需要緩存數據后，這些數據如何進行緩存。采取合作緩存的方式，本地基站考慮其他基站中的緩存內容。因此，當有用戶向基站請求數據時，本地基站先檢查自身的數據是否能滿足用戶。當本地基站不能滿足用戶所需的數據時，本地基站向網絡中其他基站請求數據，然后其他基站的數據先傳輸給本地基站，再由本地基站傳輸給用戶。

圖1 系統模型

為了有效存儲與傳輸，本文采用網絡編碼技術將原始數據分組進行編碼，然后再將數據存儲在SBS中。具體方法：如圖1所示，假設一個由N個基站組成的蜂窩網絡，當需要存儲一個熱點數據時，首先將數據分為M個原始數據分組，線性網絡編碼采用基于M維有限域GF(q)上的隨機編碼矢量，然后將數據存儲在基站中。為了成功解碼原來的數據分組，接收基站需要從K個編碼數據分組中恢復出M個線性獨立數據分組[5]。因為有限域GF(q)的q非常大，所以可以認為接收到的數據分組大概率與其他接收數據互相獨立。成功解碼的概率計算如下：

成功解碼數據分組需要的編碼數據分組K為[6]：

其中參數K可以根據數據分組的原始個數M和有限域q的大小來配置，以保證合適的解碼概率。

1.2 數學模型

研究公平性前，首先要確定評判公平性的指標，本文采用Jain指標函數作為公平性評判的標準。

Jain指標函數的定義如下：當J(x)＞Jmin，性能參數向量x是公平的；反之，不是Jain公平的。定義為[7]：

其中Jmin為Jain指標門限，J(x)是指標函數，xk為系統分配給第k個用戶的資源量，Jain值域在[1/K,1]范圍內，兩個端點分別代表最差和最好情況。當所有的個體分配到相同的資源時，公平性最大。

確定評判公平性的指標函數后，還需要選擇評判公平性的參數。本文以用戶的傳輸延遲作為公平性的評判指標，其中傳輸延遲定義為傳輸數據分組所需的傳輸時間，是一個與距離有關的參數。

用戶傳輸延遲包括兩部分，一部分是用戶服務小基站得到全部數據分組的傳輸延遲，即用戶服務小基站從其他小基站得到全部數據分組的傳輸時間；另一部分是用戶服務小基站將全部數據分組傳輸給用戶手機的傳輸延遲。本文在考慮用戶公平性時，只考慮用戶服務小基站得到全部數據分組的傳輸時延。一方面未來的蜂窩系統，基站系統是由密集分布的小基站組成，用戶服務的小基站距離用戶較近；另一方面，小基站系統已經考慮其服務用戶之間的公平性，如通過功率控制、碼率控制和調度等技術，使得其提供給每個用戶的傳輸性能基本公平。

本文采用隨機線性網絡編碼，將數據進行編碼后再以分組的形式存入基站中，且每個分組的容量相同。假設每個數據分組從傳輸基站i傳送到接收基站j所需要的傳輸延遲為cij。當本地基站的數據不夠需要從其他基站接收數據才能恢復原數據時，考慮到不同基站間通信條件不同，附近的幾個基站傳輸給本地基站的數據量應該有所不同。于是，本文引入變量αij表示從基站i傳輸到基站j的分組數占基站i中存儲數據的比例。從傳輸基站到接收基站傳輸的數據所需要的總傳輸延遲為：

其中mi是基站i中數據存儲的分組數。將傳輸延遲作為公平性的衡量指標帶入Jain公平性指標函數，得到優化目標函數為：

同時，數據分配還應當受到一些限制條件的約束。

首先，數據分配時，為了保證請求基站及時得到資源，本地基站從其他基站接收數據的傳輸延遲應當受到一個上限限制，以免某個基站接收數據的傳輸延遲特別大而影響整個系統的性能。因此，需要限制每個基站恢復數據所需要的總傳輸延遲。具體公式如下：

其中Cmax是接收基站得到K個分組所允許的最大傳輸延遲。

其次，本文采用線性分組網絡編碼方式，接收基站需要從接收到的編碼數據分組中恢復原數據，接收的編碼數據分組也受到某個最小值的限制，即需要接收一定的數據分組才能恢復原數據，具體公式如下：

其中Kmin為恢復原始數據所需的最小分組數。

再次，某個數據的數據分組在基站中所占的總的存儲容量也應該受到限制，因為基站的存儲容量是有限的，不能為了一味提高公平性指數而無限增大總的存儲量。因此，應該在限制總存儲量的條件下進行公平性優化，具體的公式如下：

其中，Mup是數據在基站中的存儲容量限制。

最后，由于基站的容量有限，數據在每個基站中的存儲容量mi也是有限制的，且傳輸系數αij應該是一個0-1的比例系數。因此，自變量mi和αij受到以下條件限制：

在上述問題中，有兩個彼此聯結的變量αij和mi。此外，式（6）和式（7）是非線性約束，因此這是一個非凸優化問題，問題的求解較為復雜。本文計劃采用遺傳算法求解該問題。

2 問題求解

2.1 算法流程

本文采用遺傳算法[8]求解問題，并改進算法使其更適合問題的求解，流程如圖2所示。

首先，生成一個有效的初始種群，這個種群要盡量具有多樣性。算法以這個初始種群作為初始搜索空間進行搜索。

其次，根據問題的優化目標構造相應的適應度函數。適應度函數值的大小反映解的優劣。適應值越大，個體被選擇的幾率越大，該個體越容易被后代繼承。

再次，通過適當的交叉和變異算法產生新的個體，提高種群的多樣性。

最后，重復執行上述操作至終止條件，通過多次迭代，種群的最優個體越來越好，最終輸出搜索過程中的最優結果。

圖2 算法流程

2.2 矩陣編碼

本文的自變量mi代表第i個基站存儲的分組數，是一個N維的向量；自變量αij代表第i個基站傳輸數據至基站j的分組數占總的存儲量的比例，是一個N*N的矩陣。這兩個變量彼此聯結。本文將兩個變量進行編碼后放在一個矩陣中直接進行遺傳優化操作，而無需將這兩個變量分解為二級優化問題。這樣既避免了兩個聯結在一起的變量因為遺傳操作而不收斂，又能用遺傳算法優化本文的目標函數。

矩陣編碼的形式如下：

其中Gk是遺傳種群中的第K個個體；mi代表存儲在第i個基站的數據分組數，αij代表基站i傳輸數據至基站j的分組數占存儲在基站i中總分組數的比例。

2.3 懲罰函數及模擬退火

本文的優化問題存在許多限制條件，遺傳算法本身不能直接處理帶有不等式約束的優化問題。可以通過將約束條件包含到適應度函數中的方法處理約束條件，其中懲罰函數就是一種很好的方法。使用懲罰函數將約束條件以懲罰項的形式加入到目標函數中，由此將有約束優化問題轉化為無約束問題[9]。通過合理選擇這些懲罰函數的懲罰因子，新的無約束優化問題收斂到原問題的最優點。本文的適應度函數經過轉化后的優化目標函數為：

其中α、β、γ是懲罰因子。

因此，需要尋找一個合適的懲罰因子來平衡目標函數與懲罰項，這也是懲罰函數法能否成功運用的關鍵。然而，尋找合適的懲罰因子比較困難。假如懲罰因子取得過小，那么原函數受到懲罰項的影響較小，相應地，不滿足條件的解受到懲罰較小，懲罰項就失去了意義，且會導致算法收斂于非極值點；而如果懲罰因子取得過大，那么原函數將主要取決于懲罰項。所以，本文設計了一種動態罰函數法來動態調整懲罰因子。這種動態罰函數法參考了模擬退火的思想，稱之為動態模擬退火罰函數法。

模擬退火的思想來源于固體退火原理。退火現象指物體逐漸降溫的物理現象。溫度愈低，物體的能量狀態會低；夠低后，液體開始冷凝與結晶；結晶狀態時，系統的能量狀態最低。大自然在緩慢降溫（亦即，退火）時，可“找到”最低能量狀態——結晶。但是，如果過程過急過快，快速降溫時會導致不是最低能態的非晶形。本文運用模擬退火的思想動態調整懲罰因子，在懲罰因子前面加一個模擬退火系數，該系數是迭代次數的函數。模擬退火系數θ定義為：

式中，L為迭代次數；Ti是第i代的動態溫度；ρ是取值范圍在（0，1）的系數。θ隨著T的逐漸減小而逐漸增加，且其增長率受參數ρ的控制。隨著演化的進行，θ逐漸增大，懲罰函數的比重逐漸增大，不滿足限制條件解的適應值所受影響越來越大，種群逐漸趨于可行解[10]。

運用模擬退火懲罰因子后的目標函數變為：

3 實驗仿真

本節分析本文提出的最大公平存儲分配方案（Maximum Fairness Storage Allocation Scheme，MFSA）的性能，并將Jain公平指數結果與文獻[8]中的基于最小總存儲容量的低復雜度存儲分配法（Low Complexity Storage Allocation，LCSA）的公平指數進行比較。

3.1 實驗設置

為了對比，本文的仿真設置與文獻[11]中的相同。假設蜂窩網絡部署在邊長10 km的正方形區域。基站的位置隨機均勻分布，基站數量N=20。鏈路的傳輸延遲假設為發送基站和接收基站之間的距離。數據解碼所需的數據分組數為Kmin=1 000。遺傳算法中，種群大小G=1 000。迭代收斂條件設置為：迭代次數達到上限1 000，或連續100輪算法前后兩次迭代結果變化大小不超過0.02。交叉概率Pc為0.65，變異概率Pm為0.05，參數α、β、γ將懲罰函數取值歸一化，使懲罰函數取值在同一量級上。

3.2 性能對比分析

分析在傳輸延遲Cmax=60的限制下，用LCSA和MFSA分別計算在總存儲容量Mup限制為3 000、4 000和50 00的存儲分配方案，然后比較LCSA和MFSA存儲方案的Jain公平性指數。

隨機取10個實驗場景（即隨機生成10種基站分布場景），將10組實驗結果的Jain公平性指數取平均，結果如圖3所示。可以看出，隨著總存儲上限的增加，每個基站能夠分配到更多的數據分組，因此公平指數也相應增加。同時，MFSA的公平指數在這三種情況下都大于LCSA的公平指數。當總存儲上限分別為3 000、4 000和5 000時，MFSA公平指數比LCSA分別提高了17.01%、19.10%和18.20%。可見，在相同的總存儲量上限下，MFSA的Jain公平指數高于LCSA。

圖3 總存儲量限制不同下平均公平性指數的對比

另外，在總的存儲量Mup=4 000限制下，分別用LCSA和MFSA計算傳輸延遲Cmax限制條件為50、60、70、80的存儲方案，然后比較兩種算法所得的存儲方案的Jain公平性指數。同樣，計算10個實驗場景并取平均，結果如圖4所示。

圖4 傳輸延遲限制不同下平均公平性指數對比

可以看出，不管是LCSA還是MFSA，傳輸延遲限制越小，公平性越好。這是因為本文衡量公平性的參數是傳輸延遲，傳輸延遲限制越小，最大傳輸延遲和最小傳輸延遲相差越小，公平性越大。同時，MFSA的公平指數在這四種情況下都大于LCSA的公平指數。當傳輸延遲限制分別為50、60、70和80時，MFSA公平指數比LCSA分別提高了12.51%、15.10%、20.54%和21.20%。因此，在相同的總存儲上限下，MFSA的Jain公平指數高于LCSA。

此外，為了更詳細地說明MFSA的公平性優于LCSA，在一個特定的實驗場景中比較這兩種算法。圖5展示了此實驗場景的基站分布，圖6展示了在Mup=3 000、Cmax=65條件下的數據分布比較。

圖5 基站分布

圖6 基站存儲分布對比

從圖5可以看到，基站 3、6、8、10、15、16、19以及20在網絡的邊緣，并且離其他基站距離較遠。從圖6可以看到，用LCSA算法會將更多的數據存儲在網絡中心。比如，大部分數據都集中存儲在2、5、14，而處于網絡邊緣的基站如10、16、19和20存儲的數據非常少。用本文提出的算法MFSA，不僅會考慮處于網絡邊緣的基站如10、16和19，而且不會將大部分數據都存儲在中心網絡。因此，MFSA的Jain公平性要好于LCSA。具體來說，MFSA和LCSA的Jain公平指數分別為0.918 1和0.793 7，公平性提高了15.6%。

4 結 語

本文提出了一種最大公平存儲分配方案，以提高用戶傳輸延遲的公平性。首先，在傳輸延遲和總存儲上限的約束下，將用戶公平性作為優化目標，從而將公平指數最大化。其次，為了解決最優問題，提出了一種基于矩陣編碼和模擬退火動態罰函數的遺傳算法。最后，通過實驗仿真，分析了算法的收斂性，證明了該算法在用戶公平性方面優于對比算法的存儲方案。