基于遺傳算法的最大化公平性基站主動(dòng)存儲(chǔ)方案*

宋財(cái)華，祝向輝，游菊芬，萬(wàn)建云

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

0 引 言

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

（1）在全球范圍內(nèi)，移動(dòng)數(shù)據(jù)流量在2016年至2021年將增長(zhǎng)7倍。移動(dòng)數(shù)據(jù)流量在2016年至2021年期間以46%的復(fù)合年增長(zhǎng)率增長(zhǎng)，到2021年達(dá)到48.3 EB/月，固定IP流量在2016年至2021年期間以21%的復(fù)合年增長(zhǎng)率增長(zhǎng)。

（2）2016年至2021年，全球移動(dòng)數(shù)據(jù)流量增長(zhǎng)速度是固定IP流量的2倍。2016年全球移動(dòng)數(shù)據(jù)流量占年全部IP流量的7%，而2021年占全部IP流量的17%。

考慮到這些問(wèn)題，研究人員意識(shí)到，可以,利用基站或手機(jī)的資源存儲(chǔ)能力，把熱點(diǎn)數(shù)據(jù)存儲(chǔ)在基站或手機(jī)等邊緣設(shè)備中，減小用戶(hù)與數(shù)據(jù)資源的距離，使得系統(tǒng)具有更好的可用性、更穩(wěn)定的連接性和更小的延遲，這是無(wú)線網(wǎng)絡(luò)邊緣存儲(chǔ)服務(wù)的最初構(gòu)想。研究人員經(jīng)過(guò)大量的研究，證明這個(gè)想法對(duì)于商業(yè)環(huán)境是實(shí)用的[2-3]。邊緣存儲(chǔ)包括基站存儲(chǔ)、移動(dòng)設(shè)備存儲(chǔ)等，本文主要研究基站存儲(chǔ)。所謂基站存儲(chǔ)，就是將數(shù)據(jù)存儲(chǔ)在基站。也就是說(shuō)，基站被假定為具有大的存儲(chǔ)容量來(lái)存儲(chǔ)將被訪問(wèn)的熱數(shù)據(jù)。這些小型基站形成無(wú)線分布式高速緩存網(wǎng)絡(luò)。由于小基站和請(qǐng)求設(shè)備之間的距離很短，緩存文件的傳輸可以非常有效地完成[4]?；局鲃?dòng)存儲(chǔ)作為邊緣存儲(chǔ)的一種存儲(chǔ)方式，具有以下良好性能。

（1）低時(shí)延和高QoS?；局鲃?dòng)存儲(chǔ)是一個(gè)分布式系統(tǒng)，通過(guò)將數(shù)據(jù)存儲(chǔ)在邊緣網(wǎng)絡(luò)的基站中，盡可能將資源內(nèi)容接近用戶(hù)。用戶(hù)通過(guò)本地基站直接獲得所需要的資源，大大減少了網(wǎng)絡(luò)獲取內(nèi)容的時(shí)延，有助于改善用戶(hù)體驗(yàn)。

（2）可擴(kuò)展性?；局鲃?dòng)存儲(chǔ)有很好的擴(kuò)展性。這種擴(kuò)展性是指具有存儲(chǔ)功能的基站能在現(xiàn)有基站設(shè)施的基礎(chǔ)上直接擴(kuò)展，或者當(dāng)出現(xiàn)新的具有存儲(chǔ)功能的基站時(shí)可以與原來(lái)的基站兼容。新的具有存儲(chǔ)功能的基站必須有協(xié)作機(jī)制模塊，負(fù)責(zé)允許新的基站加入全局緩存系統(tǒng)并訪問(wèn)公共資源，以提供靈活性。

（3）減少網(wǎng)絡(luò)帶寬的使用。當(dāng)移動(dòng)用戶(hù)通過(guò)基站連接到移動(dòng)運(yùn)營(yíng)商網(wǎng)絡(luò)時(shí)，應(yīng)用數(shù)據(jù)必須通過(guò)移動(dòng)運(yùn)營(yíng)商的網(wǎng)絡(luò)返回到移動(dòng)網(wǎng)絡(luò)的網(wǎng)關(guān)才能到達(dá)廣域網(wǎng)，網(wǎng)關(guān)連接到Internet回程?；ヂ?lián)網(wǎng)回程的帶寬使用是移動(dòng)網(wǎng)絡(luò)數(shù)據(jù)業(yè)務(wù)的主要成本之一。為了減少帶寬使用，基站主動(dòng)存儲(chǔ)系統(tǒng)將緩存數(shù)據(jù)保存在全局緩存集群內(nèi)部。之后，如果有用戶(hù)發(fā)送相同的請(qǐng)求，將直接從基站獲取資源，而不是從數(shù)據(jù)源或附近的內(nèi)容分發(fā)網(wǎng)絡(luò)（Content Delivery Network，CDN）服務(wù)器請(qǐng)求它，從而大大降低了網(wǎng)絡(luò)帶寬的使用。

因此，基站主動(dòng)存儲(chǔ)為滿(mǎn)足新出現(xiàn)的實(shí)時(shí)、交互式的媒體服務(wù)所要求的服務(wù)質(zhì)量提供了新的思路。在網(wǎng)絡(luò)邊緣使用協(xié)作緩存，使得數(shù)據(jù)本地化，有助于平衡網(wǎng)絡(luò)負(fù)載。利用基站可以在移動(dòng)用戶(hù)接近的網(wǎng)絡(luò)邊緣部署協(xié)作緩存方案，把原數(shù)據(jù)網(wǎng)絡(luò)中下載內(nèi)容的時(shí)間和將內(nèi)容傳遞給移動(dòng)用戶(hù)的時(shí)間分離，節(jié)省了網(wǎng)絡(luò)回程資源，同時(shí)減少了延遲，提高了服務(wù)質(zhì)量。

在基站中進(jìn)行數(shù)據(jù)緩存是一種新興的網(wǎng)絡(luò)技術(shù)，有許多問(wèn)題需要考慮，其中最關(guān)鍵的問(wèn)題是數(shù)據(jù)資源的存儲(chǔ)分配。盡管眾多學(xué)者對(duì)資源分配問(wèn)題進(jìn)行了研究，并考慮從各個(gè)方面提升系統(tǒng)的性能，但是還有許多方面未考慮其中，如公平性?；局鲃?dòng)存儲(chǔ)的資源分配仍然是個(gè)不太成熟的領(lǐng)域，發(fā)展前景十分廣闊，需要進(jìn)一步的研究和探討。本文研究基站主動(dòng)存儲(chǔ)中資源分配的問(wèn)題，在大量總結(jié)國(guó)內(nèi)外已有論文的成果上，重點(diǎn)考慮提升資源分配的用戶(hù)公平性，對(duì)理論和實(shí)際都有一定的意義。

1 系統(tǒng)模型

1.1 基站主動(dòng)存儲(chǔ)網(wǎng)絡(luò)模型

開(kāi)展研究前，需確定基站主動(dòng)存儲(chǔ)系統(tǒng)的構(gòu)架。本文研究將數(shù)據(jù)存儲(chǔ)在小基站（Small Base Station）中，研究的系統(tǒng)構(gòu)架如圖1所示，并假設(shè)如下：

（1）一個(gè)蜂窩通信系統(tǒng)內(nèi)有許多小型基站，服務(wù)大量終端用戶(hù)，這些基站位置固定；

（2）小基站具有存儲(chǔ)能力，能夠主動(dòng)發(fā)現(xiàn)一段時(shí)間內(nèi)流行的數(shù)據(jù)并進(jìn)行主動(dòng)存儲(chǔ)；

（3）小基站之間具有通信能力，能夠互相訪問(wèn)對(duì)方存儲(chǔ)的數(shù)據(jù)。

本文不研究基站應(yīng)該緩存哪些數(shù)據(jù)，而是研究在確定需要緩存數(shù)據(jù)后，這些數(shù)據(jù)如何進(jìn)行緩存。采取合作緩存的方式，本地基站考慮其他基站中的緩存內(nèi)容。因此，當(dāng)有用戶(hù)向基站請(qǐng)求數(shù)據(jù)時(shí)，本地基站先檢查自身的數(shù)據(jù)是否能滿(mǎn)足用戶(hù)。當(dāng)本地基站不能滿(mǎn)足用戶(hù)所需的數(shù)據(jù)時(shí)，本地基站向網(wǎng)絡(luò)中其他基站請(qǐng)求數(shù)據(jù)，然后其他基站的數(shù)據(jù)先傳輸給本地基站，再由本地基站傳輸給用戶(hù)。

圖1 系統(tǒng)模型

為了有效存儲(chǔ)與傳輸，本文采用網(wǎng)絡(luò)編碼技術(shù)將原始數(shù)據(jù)分組進(jìn)行編碼，然后再將數(shù)據(jù)存儲(chǔ)在SBS中。具體方法：如圖1所示，假設(shè)一個(gè)由N個(gè)基站組成的蜂窩網(wǎng)絡(luò)，當(dāng)需要存儲(chǔ)一個(gè)熱點(diǎn)數(shù)據(jù)時(shí)，首先將數(shù)據(jù)分為M個(gè)原始數(shù)據(jù)分組，線性網(wǎng)絡(luò)編碼采用基于M維有限域GF(q)上的隨機(jī)編碼矢量，然后將數(shù)據(jù)存儲(chǔ)在基站中。為了成功解碼原來(lái)的數(shù)據(jù)分組，接收基站需要從K個(gè)編碼數(shù)據(jù)分組中恢復(fù)出M個(gè)線性獨(dú)立數(shù)據(jù)分組[5]。因?yàn)橛邢抻騁F(q)的q非常大，所以可以認(rèn)為接收到的數(shù)據(jù)分組大概率與其他接收數(shù)據(jù)互相獨(dú)立。成功解碼的概率計(jì)算如下：

成功解碼數(shù)據(jù)分組需要的編碼數(shù)據(jù)分組K為[6]：

其中參數(shù)K可以根據(jù)數(shù)據(jù)分組的原始個(gè)數(shù)M和有限域q的大小來(lái)配置，以保證合適的解碼概率。

1.2 數(shù)學(xué)模型

研究公平性前，首先要確定評(píng)判公平性的指標(biāo)，本文采用Jain指標(biāo)函數(shù)作為公平性評(píng)判的標(biāo)準(zhǔn)。

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

其中Jmin為Jain指標(biāo)門(mén)限，J(x)是指標(biāo)函數(shù)，xk為系統(tǒng)分配給第k個(gè)用戶(hù)的資源量，Jain值域在[1/K,1]范圍內(nèi)，兩個(gè)端點(diǎn)分別代表最差和最好情況。當(dāng)所有的個(gè)體分配到相同的資源時(shí)，公平性最大。

確定評(píng)判公平性的指標(biāo)函數(shù)后，還需要選擇評(píng)判公平性的參數(shù)。本文以用戶(hù)的傳輸延遲作為公平性的評(píng)判指標(biāo)，其中傳輸延遲定義為傳輸數(shù)據(jù)分組所需的傳輸時(shí)間，是一個(gè)與距離有關(guān)的參數(shù)。

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

本文采用隨機(jī)線性網(wǎng)絡(luò)編碼，將數(shù)據(jù)進(jìn)行編碼后再以分組的形式存入基站中，且每個(gè)分組的容量相同。假設(shè)每個(gè)數(shù)據(jù)分組從傳輸基站i傳送到接收基站j所需要的傳輸延遲為cij。當(dāng)本地基站的數(shù)據(jù)不夠需要從其他基站接收數(shù)據(jù)才能恢復(fù)原數(shù)據(jù)時(shí)，考慮到不同基站間通信條件不同，附近的幾個(gè)基站傳輸給本地基站的數(shù)據(jù)量應(yīng)該有所不同。于是，本文引入變量αij表示從基站i傳輸?shù)交緅的分組數(shù)占基站i中存儲(chǔ)數(shù)據(jù)的比例。從傳輸基站到接收基站傳輸?shù)臄?shù)據(jù)所需要的總傳輸延遲為：

其中mi是基站i中數(shù)據(jù)存儲(chǔ)的分組數(shù)。將傳輸延遲作為公平性的衡量指標(biāo)帶入Jain公平性指標(biāo)函數(shù)，得到優(yōu)化目標(biāo)函數(shù)為：

同時(shí)，數(shù)據(jù)分配還應(yīng)當(dāng)受到一些限制條件的約束。

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

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

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

其中Kmin為恢復(fù)原始數(shù)據(jù)所需的最小分組數(shù)。

再次，某個(gè)數(shù)據(jù)的數(shù)據(jù)分組在基站中所占的總的存儲(chǔ)容量也應(yīng)該受到限制，因?yàn)榛镜拇鎯?chǔ)容量是有限的，不能為了一味提高公平性指數(shù)而無(wú)限增大總的存儲(chǔ)量。因此，應(yīng)該在限制總存儲(chǔ)量的條件下進(jìn)行公平性?xún)?yōu)化，具體的公式如下：

其中，Mup是數(shù)據(jù)在基站中的存儲(chǔ)容量限制。

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

在上述問(wèn)題中，有兩個(gè)彼此聯(lián)結(jié)的變量αij和mi。此外，式（6）和式（7）是非線性約束，因此這是一個(gè)非凸優(yōu)化問(wèn)題，問(wèn)題的求解較為復(fù)雜。本文計(jì)劃采用遺傳算法求解該問(wèn)題。

2 問(wèn)題求解

2.1 算法流程

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

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

其次，根據(jù)問(wèn)題的優(yōu)化目標(biāo)構(gòu)造相應(yīng)的適應(yīng)度函數(shù)。適應(yīng)度函數(shù)值的大小反映解的優(yōu)劣。適應(yīng)值越大，個(gè)體被選擇的幾率越大，該個(gè)體越容易被后代繼承。

再次，通過(guò)適當(dāng)?shù)慕徊婧妥儺愃惴óa(chǎn)生新的個(gè)體，提高種群的多樣性。

最后，重復(fù)執(zhí)行上述操作至終止條件，通過(guò)多次迭代，種群的最優(yōu)個(gè)體越來(lái)越好，最終輸出搜索過(guò)程中的最優(yōu)結(jié)果。

圖2 算法流程

2.2 矩陣編碼

本文的自變量mi代表第i個(gè)基站存儲(chǔ)的分組數(shù)，是一個(gè)N維的向量；自變量αij代表第i個(gè)基站傳輸數(shù)據(jù)至基站j的分組數(shù)占總的存儲(chǔ)量的比例，是一個(gè)N*N的矩陣。這兩個(gè)變量彼此聯(lián)結(jié)。本文將兩個(gè)變量進(jìn)行編碼后放在一個(gè)矩陣中直接進(jìn)行遺傳優(yōu)化操作，而無(wú)需將這兩個(gè)變量分解為二級(jí)優(yōu)化問(wèn)題。這樣既避免了兩個(gè)聯(lián)結(jié)在一起的變量因?yàn)檫z傳操作而不收斂，又能用遺傳算法優(yōu)化本文的目標(biāo)函數(shù)。

矩陣編碼的形式如下：

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

2.3 懲罰函數(shù)及模擬退火

本文的優(yōu)化問(wèn)題存在許多限制條件，遺傳算法本身不能直接處理帶有不等式約束的優(yōu)化問(wèn)題?？梢酝ㄟ^(guò)將約束條件包含到適應(yīng)度函數(shù)中的方法處理約束條件，其中懲罰函數(shù)就是一種很好的方法。使用懲罰函數(shù)將約束條件以懲罰項(xiàng)的形式加入到目標(biāo)函數(shù)中，由此將有約束優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題[9]。通過(guò)合理選擇這些懲罰函數(shù)的懲罰因子，新的無(wú)約束優(yōu)化問(wèn)題收斂到原問(wèn)題的最優(yōu)點(diǎn)。本文的適應(yīng)度函數(shù)經(jīng)過(guò)轉(zhuǎn)化后的優(yōu)化目標(biāo)函數(shù)為：

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

因此，需要尋找一個(gè)合適的懲罰因子來(lái)平衡目標(biāo)函數(shù)與懲罰項(xiàng)，這也是懲罰函數(shù)法能否成功運(yùn)用的關(guān)鍵。然而，尋找合適的懲罰因子比較困難。假如懲罰因子取得過(guò)小，那么原函數(shù)受到懲罰項(xiàng)的影響較小，相應(yīng)地，不滿(mǎn)足條件的解受到懲罰較小，懲罰項(xiàng)就失去了意義，且會(huì)導(dǎo)致算法收斂于非極值點(diǎn)；而如果懲罰因子取得過(guò)大，那么原函數(shù)將主要取決于懲罰項(xiàng)。所以，本文設(shè)計(jì)了一種動(dòng)態(tài)罰函數(shù)法來(lái)動(dòng)態(tài)調(diào)整懲罰因子。這種動(dòng)態(tài)罰函數(shù)法參考了模擬退火的思想，稱(chēng)之為動(dòng)態(tài)模擬退火罰函數(shù)法。

模擬退火的思想來(lái)源于固體退火原理。退火現(xiàn)象指物體逐漸降溫的物理現(xiàn)象。溫度愈低，物體的能量狀態(tài)會(huì)低；夠低后，液體開(kāi)始冷凝與結(jié)晶；結(jié)晶狀態(tài)時(shí)，系統(tǒng)的能量狀態(tài)最低。大自然在緩慢降溫（亦即，退火）時(shí)，可“找到”最低能量狀態(tài)——結(jié)晶。但是，如果過(guò)程過(guò)急過(guò)快，快速降溫時(shí)會(huì)導(dǎo)致不是最低能態(tài)的非晶形。本文運(yùn)用模擬退火的思想動(dòng)態(tài)調(diào)整懲罰因子，在懲罰因子前面加一個(gè)模擬退火系數(shù)，該系數(shù)是迭代次數(shù)的函數(shù)。模擬退火系數(shù)θ定義為：

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

運(yùn)用模擬退火懲罰因子后的目標(biāo)函數(shù)變?yōu)椋?/p>

3 實(shí)驗(yàn)仿真

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

3.1 實(shí)驗(yàn)設(shè)置

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

3.2 性能對(duì)比分析

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

隨機(jī)取10個(gè)實(shí)驗(yàn)場(chǎng)景（即隨機(jī)生成10種基站分布場(chǎng)景），將10組實(shí)驗(yàn)結(jié)果的Jain公平性指數(shù)取平均，結(jié)果如圖3所示?？梢钥闯?，隨著總存儲(chǔ)上限的增加，每個(gè)基站能夠分配到更多的數(shù)據(jù)分組，因此公平指數(shù)也相應(yīng)增加。同時(shí)，MFSA的公平指數(shù)在這三種情況下都大于LCSA的公平指數(shù)。當(dāng)總存儲(chǔ)上限分別為3 000、4 000和5 000時(shí)，MFSA公平指數(shù)比LCSA分別提高了17.01%、19.10%和18.20%?？梢?jiàn)，在相同的總存儲(chǔ)量上限下，MFSA的Jain公平指數(shù)高于LCSA。

圖3 總存儲(chǔ)量限制不同下平均公平性指數(shù)的對(duì)比

另外，在總的存儲(chǔ)量Mup=4 000限制下，分別用LCSA和MFSA計(jì)算傳輸延遲Cmax限制條件為50、60、70、80的存儲(chǔ)方案，然后比較兩種算法所得的存儲(chǔ)方案的Jain公平性指數(shù)。同樣，計(jì)算10個(gè)實(shí)驗(yàn)場(chǎng)景并取平均，結(jié)果如圖4所示。

圖4 傳輸延遲限制不同下平均公平性指數(shù)對(duì)比

可以看出，不管是LCSA還是MFSA，傳輸延遲限制越小，公平性越好。這是因?yàn)楸疚暮饬抗叫缘膮?shù)是傳輸延遲，傳輸延遲限制越小，最大傳輸延遲和最小傳輸延遲相差越小，公平性越大。同時(shí)，MFSA的公平指數(shù)在這四種情況下都大于LCSA的公平指數(shù)。當(dāng)傳輸延遲限制分別為50、60、70和80時(shí)，MFSA公平指數(shù)比LCSA分別提高了12.51%、15.10%、20.54%和21.20%。因此，在相同的總存儲(chǔ)上限下，MFSA的Jain公平指數(shù)高于LCSA。

此外，為了更詳細(xì)地說(shuō)明MFSA的公平性?xún)?yōu)于LCSA，在一個(gè)特定的實(shí)驗(yàn)場(chǎng)景中比較這兩種算法。圖5展示了此實(shí)驗(yàn)場(chǎng)景的基站分布，圖6展示了在Mup=3 000、Cmax=65條件下的數(shù)據(jù)分布比較。

圖5 基站分布

圖6 基站存儲(chǔ)分布對(duì)比

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

4 結(jié) 語(yǔ)

本文提出了一種最大公平存儲(chǔ)分配方案，以提高用戶(hù)傳輸延遲的公平性。首先，在傳輸延遲和總存儲(chǔ)上限的約束下，將用戶(hù)公平性作為優(yōu)化目標(biāo)，從而將公平指數(shù)最大化。其次，為了解決最優(yōu)問(wèn)題，提出了一種基于矩陣編碼和模擬退火動(dòng)態(tài)罰函數(shù)的遺傳算法。最后，通過(guò)實(shí)驗(yàn)仿真，分析了算法的收斂性，證明了該算法在用戶(hù)公平性方面優(yōu)于對(duì)比算法的存儲(chǔ)方案。