基于頻譜資源共享的動(dòng)態(tài)分配算法

陳書恒，張朝陽(yáng)，吳廣富

(1.海軍研究院，上海 200436；2.重慶郵電大學(xué) 移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

0 引 言

無(wú)線物理網(wǎng)絡(luò)(wireless physical network, WPN)擁有功率、時(shí)隙、頻譜等物理資源。虛擬網(wǎng)絡(luò)(virtual network, VN)從WPN處租賃物理資源，構(gòu)建不同服務(wù)網(wǎng)絡(luò)，并為用戶提供服務(wù)。實(shí)際場(chǎng)景中用戶行為具有隨機(jī)變化的特性，使得VN實(shí)際需求的資源量具有時(shí)變性，而VN向WPN申請(qǐng)資源時(shí)，往往按照用戶峰值需求的資源量進(jìn)行申請(qǐng)，從而導(dǎo)致大部分時(shí)間內(nèi)VN的資源未被完全使用。這樣不僅提高了服務(wù)商租賃資源的成本，而且降低了WPN接受率。因此，VN資源請(qǐng)求的時(shí)變性是無(wú)線網(wǎng)絡(luò)虛擬化資源分配中需要考慮的重要問(wèn)題。

當(dāng)前部分學(xué)者對(duì)無(wú)線網(wǎng)絡(luò)虛擬化中資源分配問(wèn)題做了大量研究。文獻(xiàn)[1-2]將物理資源以及虛擬網(wǎng)絡(luò)抽象成時(shí)域和頻域組成的矩形圖，提出了一種近似卡諾圖的資源分配算法。其中，文獻(xiàn)[1]介紹了一種在線分配算法，考慮了虛擬網(wǎng)絡(luò)(virtual network, VN)動(dòng)態(tài)地到達(dá)和離開特性，有效解決了資源分配過(guò)程中的在線虛擬網(wǎng)絡(luò)請(qǐng)求和映射問(wèn)題，但并沒有考慮當(dāng)物理資源出現(xiàn)碎片化后動(dòng)態(tài)調(diào)整的問(wèn)題；文獻(xiàn)[2]在文獻(xiàn)[1]的基礎(chǔ)上提出了一種動(dòng)態(tài)資源分配方案，并提出了資源重分配的思想。文獻(xiàn)[3-5]研究了正交頻分多址(orthogonal frequency division multiple access, OFDMA)系統(tǒng)中基于價(jià)格理論的能效優(yōu)化問(wèn)題，并利用非合作博弈理論求得納什均衡解來(lái)進(jìn)行資源分配。文獻(xiàn)[6-9]提出了針對(duì)節(jié)點(diǎn)和鏈路的資源分配算法，但均未考慮動(dòng)態(tài)性。其中，文獻(xiàn)[6]和文獻(xiàn)[8]在靜態(tài)多跳網(wǎng)絡(luò)中，利用最短路徑算法為虛擬網(wǎng)絡(luò)分配資源，使得干擾最??；文獻(xiàn)[7]利用了網(wǎng)絡(luò)鏈路可靠性為虛擬網(wǎng)絡(luò)分配資源，但允許同一虛擬網(wǎng)絡(luò)的不同節(jié)點(diǎn)映射到相同的物理節(jié)點(diǎn)上，使得鏈路間的干擾太大；文獻(xiàn)[9]利用動(dòng)態(tài)資源分配，使得重新分配的結(jié)果避免了和原分配方案相同，實(shí)現(xiàn)了資源的均衡利用。針對(duì)資源請(qǐng)求的時(shí)變性，文獻(xiàn)[10-11]提出了基于頻譜資源機(jī)會(huì)性共享的分配算法，但該算法沒有考慮VN請(qǐng)求到達(dá)與離開的動(dòng)態(tài)性。

為解決VN資源請(qǐng)求時(shí)變性和物理資源碎片問(wèn)題，本文提出了基于頻譜資源共享的動(dòng)態(tài)分配算法(dynamic allocation algorithm based on spectrum resource sharing, DAA-SRS)。該算法結(jié)合虛擬請(qǐng)求的生命周期，進(jìn)行子信道分配和重分配。針對(duì)無(wú)線虛擬網(wǎng)絡(luò)資源請(qǐng)求接受率、物理網(wǎng)絡(luò)收益等性能指標(biāo)進(jìn)行仿真分析，驗(yàn)證了DAA-SRS算法的可行性和有效性。

1 系統(tǒng)模型

1.1 資源映射

無(wú)線物理網(wǎng)絡(luò)(wireless physical network, WPN)擁有功率、時(shí)隙、頻譜等物理資源。虛擬網(wǎng)絡(luò)(virtual network, VN)從WPN處租賃物理資源，構(gòu)建不同服務(wù)網(wǎng)絡(luò)，并為用戶提供服務(wù)。本文主要考慮單個(gè)訪問(wèn)節(jié)點(diǎn)(access point, AP)的頻譜資源分配問(wèn)題，通過(guò)OFDMA技術(shù)將其劃分為正交的子信道，如圖1所示。因此，任意一個(gè)VN請(qǐng)求頻譜資源，可以表示為請(qǐng)求一定數(shù)量的子信道?？紤]到實(shí)際場(chǎng)景中用戶行為具有隨機(jī)變化的特性，使得VN實(shí)際需求的資源量具有時(shí)變性，而VN向WPN申請(qǐng)資源時(shí)，往往按照用戶峰值需求的資源量進(jìn)行申請(qǐng)，導(dǎo)致大部分時(shí)間內(nèi)VN的資源未被完全使用。這樣不僅提高了服務(wù)商租賃資源的成本，而且降低了WPN接受率。因此，VN資源請(qǐng)求的時(shí)變性是無(wú)線網(wǎng)絡(luò)虛擬化資源分配中十分重要問(wèn)題。文獻(xiàn)[11]中將VN的請(qǐng)求分為2個(gè)部分：基本資源請(qǐng)求(basic resource request, BRR)和可變資源請(qǐng)求(varied resource request, VRR)。BRR是在其對(duì)應(yīng)VN整個(gè)生命周期內(nèi)為滿足用戶的基本需求所壟斷的物理頻譜資源，即WPN為其分配相應(yīng)數(shù)量的物理子信道；VRR是依概率發(fā)生的，并且多個(gè)VNs的VRR共享物理子信道?；跈C(jī)會(huì)共享機(jī)制，VNs使物理子信道數(shù)量減少，從而降低租賃物理資源成本，同時(shí)也能夠?yàn)閃PN提供更多VNs的接受機(jī)會(huì)。

圖1 無(wú)線資源映射Fig.1 Wireless resource mapping

1.2 機(jī)會(huì)共享機(jī)制

機(jī)會(huì)性地共享相同頻譜會(huì)引發(fā)碰撞，即多個(gè)VNs的VRR同時(shí)共享于同一個(gè)物理信道。碰撞發(fā)生時(shí)，會(huì)使網(wǎng)絡(luò)服務(wù)質(zhì)量(quality of service, QoS)和用戶體驗(yàn)質(zhì)量(quality of experience，QoE)惡化。為避免這種情況的發(fā)生，文獻(xiàn)[10-11]設(shè)置了一個(gè)碰撞概率的閾值pth。規(guī)定當(dāng)多個(gè)VNs在某一物理信道上的碰撞概率不大于pth，就允許VNs共享該物理信道；調(diào)節(jié)pth的大小會(huì)直接影響到頻譜利用率，進(jìn)而會(huì)影響QoS和QoE。因此，根據(jù)實(shí)時(shí)要求和系統(tǒng)狀態(tài)動(dòng)態(tài)地調(diào)整并合理地設(shè)置pth是至關(guān)重要的。假設(shè)碰撞閾值為pth=0.1，VN1和VN2的VRR的發(fā)生概率分別為0.2，0.3，則VN1和VN2的碰撞概率為0.2×0.3=0.06<0.1，這樣VN1和VN2的VRR虛擬信道就可以共享同一物理信道；若VN1，VN2的VRR發(fā)生概率分別為0.4，0.3，就不能共享同一信道，因?yàn)?.4×0.3=0.12>0.1。

1.3 虛擬網(wǎng)絡(luò)請(qǐng)求資源

在真實(shí)場(chǎng)景中，VN請(qǐng)求是動(dòng)態(tài)地到達(dá)與離開，即VN請(qǐng)求并不是長(zhǎng)期占有物理資源，而是其在生命周期內(nèi)占用資源，在生命周期結(jié)束后釋放所占用的物理資源。因此，某個(gè)時(shí)間內(nèi)VN請(qǐng)求并未被成功分配資源，則會(huì)被放入緩存區(qū)等待下一時(shí)隙。

VN請(qǐng)求資源可以表示為(b,v,p,Lt,D)，其中,b表示基本資源請(qǐng)求BRR；v表示可變資源請(qǐng)求VRR；p表示可變請(qǐng)求發(fā)生的概率；Lt表示VN的生命周期；D表示VN可忍受的最大時(shí)延。

1.4 資源分配問(wèn)題

ei=bi+pivi

(1)

因此，其為WPN帶來(lái)的收益為

Rj(ei)=Rj(bi,vi,pi)=alog(1+bi+pivi)

(2)

則時(shí)隙資源j分配成功的VN請(qǐng)求所帶來(lái)的收益為

s.t.

(3)

優(yōu)化目標(biāo)函數(shù)為

(4)

并使其滿足

(5)

2 算法設(shè)計(jì)

根據(jù)上述問(wèn)題的定義，所要優(yōu)化的目標(biāo)函數(shù)是一個(gè)NP難問(wèn)題。對(duì)于解決NP難問(wèn)題，已有很多學(xué)者提出了啟發(fā)式或者貪婪算法去求優(yōu)化解。文獻(xiàn)[11]提出了一種啟發(fā)式算法，但是并沒有考慮到VN請(qǐng)求的到達(dá)與離去的動(dòng)態(tài)性；同時(shí)也沒有考慮由于動(dòng)態(tài)性而導(dǎo)致的資源碎片化問(wèn)題。為解決上述問(wèn)題，本文提出了基于頻譜資源共享的動(dòng)態(tài)分配算法，其流程圖如圖2所示。

設(shè)計(jì)一個(gè)包含有2種類型的VN請(qǐng)求的緩存區(qū)：①前面時(shí)隙未被成功分配且在時(shí)延忍受范圍內(nèi)的VN；②當(dāng)前時(shí)隙新到達(dá)的VN請(qǐng)求。在無(wú)線資源分配過(guò)程中，首先，將前面時(shí)隙的VN按照剩余生命時(shí)長(zhǎng)大小排序，并優(yōu)先分配剩余時(shí)長(zhǎng)小的VN；其次是分配新到達(dá)的VN。為體現(xiàn)分配優(yōu)先級(jí)，定義參數(shù)ε為

(6)

即在無(wú)線資源分配時(shí)，應(yīng)優(yōu)先考慮：①資源請(qǐng)求大的VN；②生命周期較短的VN。

針對(duì)以上2種類型的VN，分別按照相應(yīng)優(yōu)先準(zhǔn)則進(jìn)行排序。排序完成后，再將依序完成對(duì)VN的資源分配工作。對(duì)于任意VNi，首先為BRR分配資源，滿足的話則進(jìn)行VRR的分配，不滿足就放入緩存區(qū)，在生命周期內(nèi)都無(wú)法滿足VN的請(qǐng)求資源，則拒絕該請(qǐng)求；VN分配結(jié)束后，再進(jìn)行當(dāng)前VRR的重分配過(guò)程。

圖2 DAA-SRS算法流程圖Fig.2 Algorithm flow chart for DAA-SRS

BRR資源分配的具體過(guò)程如下。

算法1BRR資源分配算法。

步驟1依據(jù)資源分配優(yōu)先準(zhǔn)則對(duì)緩存區(qū)中的虛擬網(wǎng)絡(luò)進(jìn)行排序；

步驟2判斷當(dāng)前時(shí)隙是否存在VN因生命周期到期而離開的現(xiàn)象。如果存在，則調(diào)用算法3；否則，進(jìn)行步驟3；

步驟3從緩存區(qū)中取出待分配的VNi，并判斷可用的頻譜資源Rrem是否滿足其BRR的請(qǐng)求；

步驟4若不滿足，判斷是否在其時(shí)延忍受范圍內(nèi)。是，則放入緩存區(qū)，否則拒絕該請(qǐng)求；

步驟5若滿足，則調(diào)用算法2進(jìn)行資源分配并判斷是否滿足VRR請(qǐng)求；滿足則分配完成，不滿足則進(jìn)行步驟4。

3 VRR資源分配

BRR請(qǐng)求生命周期內(nèi)必須壟斷頻譜資源，是無(wú)線網(wǎng)絡(luò)虛擬資源分配必須滿足的。下面著重介紹VRR請(qǐng)求的分配以及重分配過(guò)程，主要包括碰撞概率、子信道分配以及子信道的重分配。

3.1 計(jì)算碰撞概率

(7)

(8)

(7)—(8)式中：Sm表示第m條共享子信道；Prno(Sm),Prone(Sm)分別表示第m條共享物理信道沒有信道共享和只有一條信道共享時(shí)的概率。

當(dāng)有新的VN到來(lái)，且其VRR的發(fā)生概率為pi，則該VN的碰撞概率計(jì)算公式為

(9)

實(shí)際使用過(guò)程中，不需要重復(fù)上面的計(jì)算過(guò)程，只需要保存每條共享物理信道上的Prno,Prone即可。當(dāng)有新的VN時(shí)，更新碰撞概率為

(10)

(11)

然后根據(jù) (9) 式計(jì)算出碰撞概率大小并和閾值pth進(jìn)行比較。

3.2 子信道分配

通過(guò)計(jì)算當(dāng)前VN與各條共享物理子信道的碰撞概率，統(tǒng)計(jì)碰撞概率小于pth的信道作為VRR的候選子信道集合BCH。

(12)

先統(tǒng)計(jì)候選子信道的數(shù)量nBCH，然后為當(dāng)前VN的VRR分配子信道，分配情況有如下幾種。

1)nBCH≥vi表示VRR請(qǐng)求的頻譜資源量小于當(dāng)前滿足條件的共享子信道數(shù)量；

此時(shí)，應(yīng)優(yōu)選出剩余資源量大的vi條共享子信道進(jìn)行分配。定義crem表示共享子信道的剩余資源量。假設(shè)新到VN的VRR發(fā)生概率為pnew，則單條子信道剩余資源量可以用該VN的碰撞概率恰好等于閾值pth來(lái)進(jìn)行。

(13)

可以解出

(14)

進(jìn)而得出

crem=pnew

(15)

再根據(jù)crem將候選信道按降序排列，取出最大的vi條共享子信道進(jìn)行分配。

2)nBCH

3)nBCHRrem-bi，表示共享子信道和剩余空閑子信道均無(wú)法滿足VRR請(qǐng)求量，無(wú)線物理網(wǎng)絡(luò)無(wú)法滿足VNi，則將其放入緩存區(qū)。

3.3 VRR資源分配算法

結(jié)合碰撞概率和子信道分配2個(gè)方面，提出一種VRR資源分配算法，該算法主要是根據(jù)碰撞概率選出能夠分配資源的子信道，再將子信道分配給VN，并更新子信道的碰撞概率，其具體的算法流程如算法2所示。

算法2VRR資源分配算法。

步驟1根據(jù)所要分配VRR的發(fā)生概率pi，并依次與當(dāng)前所有的共享子信道計(jì)算其碰撞概率；

步驟2統(tǒng)計(jì)步驟1中碰撞概率不大于閾值pth的共享子信道集合BCH；

步驟3根據(jù)步驟2中BCH得出滿足的子信道數(shù)量并與VRR請(qǐng)求量進(jìn)行比較，完成分配；

步驟4根據(jù)步驟3中的分配結(jié)果，更新對(duì)應(yīng)共享子信道的碰撞概率Prno(Sm),Prone(Sm)。

3.4 VRR重分配算法

由于VN請(qǐng)求到達(dá)和離開的動(dòng)態(tài)性，造成頻譜資源出現(xiàn)碎片化，使得頻譜資源沒有得到充分利用。針對(duì)這種情況，提出VRR請(qǐng)求的重分配思想并給出具體步驟。

另外由于生命周期的存在，同一時(shí)隙有新的VN到達(dá)，也有VN離開，導(dǎo)致共享子信道內(nèi)出現(xiàn)資源空閑，不同的VN占用不同的子信道，新的VN可能因?yàn)榕鲎哺怕蚀笥陂撝?，?dǎo)致VRR資源得不到滿足而遭到拒絕，為了避免這種情況，提出VRR重分配算法，當(dāng)VN離開物理網(wǎng)絡(luò)時(shí)，在滿足碰撞概率的前提下，將分散在多個(gè)子信道的VN請(qǐng)求融合在同一個(gè)子信道內(nèi)，這樣就能空余更多的子信道供新的VN請(qǐng)求占用。VRR重分配算法如下。

算法3VRR重分配算法。

接到分手電話的時(shí)候，我正窩在家里上淘寶。小健說(shuō)，他們家是地道的本地人，本來(lái)就不同意我們?cè)谝黄稹，F(xiàn)在我沒有工作又不上進(jìn)，他很難再堅(jiān)持。大家都是成年人，應(yīng)該考慮現(xiàn)實(shí)問(wèn)題，所以，分開比較好。

步驟1根據(jù)當(dāng)前共享子信道的情況，統(tǒng)計(jì)其數(shù)量并按照生成順序編號(hào)為1,2,…,N;

步驟2按照編號(hào)從大到小遍歷共享子信道，并對(duì)所遍歷的子信道優(yōu)先選擇其上發(fā)生概率最大的VRR進(jìn)行重分配；

步驟3將步驟2中選擇出的VRR與其所在子信道編號(hào)之前的子信道依次計(jì)算碰撞概率；

步驟4判斷是否存在滿足碰撞概率不大于閾值pth的共享子信道。若有，進(jìn)入步驟5;若無(wú)，進(jìn)入步驟2遍歷下一個(gè)共享子信道；

步驟5在所滿足碰撞閾值pth的共享子信道集合中，找出使得碰撞概率最小的子信道做為VRR重分配后的共享子信道；

步驟6判斷是否遍歷完所有的共享子信道。是，則停止重分配；否則進(jìn)行步驟2。

4 仿真及分析

4.1 場(chǎng)景設(shè)置

利用MATLAB工具驗(yàn)證所提算法的有效性。分別從以下方面進(jìn)行分析：①一般分配算法(即無(wú)頻譜共享機(jī)制)與頻譜共享算法在占用信道數(shù)量方面的對(duì)比，驗(yàn)證頻譜共享的有效性；②不同碰撞閾值對(duì)所占信道數(shù)量的對(duì)比，判斷設(shè)置閾值的合理性；③在考慮VN請(qǐng)求動(dòng)態(tài)性的條件下，分析其接受率性能。

4.2 仿真結(jié)果及性能分析

由于VN的BRR部分是壟斷物理資源，因此該實(shí)驗(yàn)過(guò)程僅考慮VN的VRR部分的分配。在仿真過(guò)程中[11]，一般假設(shè)物理網(wǎng)絡(luò)的總信道數(shù)C=600，碰撞閾值pth=0.1，單個(gè)VN的可變資源請(qǐng)求VRR服從(5,Vmax)的均勻分布，VN所能允許的最大分配時(shí)延D=2，VN的到達(dá)過(guò)程建模為一個(gè)服從參數(shù)為λ的泊松分布過(guò)程，VN的生命周期服從參數(shù)為μ的指數(shù)分布，且λ=5,μ=10。本實(shí)驗(yàn)取了200次運(yùn)行結(jié)果的算術(shù)平均值。

4.2.1 頻譜共享算法有效性

圖3分析不同VN的數(shù)量與平均占用信道數(shù)量(即消耗的頻譜資源)之間關(guān)系。其中VRR發(fā)生概率服從(0.1,0.2)的均勻分布，Vmax=10?？梢园l(fā)現(xiàn)，隨著VN的數(shù)量增多，其相應(yīng)占用的物理信道數(shù)量均呈線性增長(zhǎng)。一般分配算法在不同VN數(shù)量請(qǐng)求下，其占用的信道數(shù)量遠(yuǎn)高于具有共享機(jī)制的算法，這是因?yàn)闆]有共享機(jī)制，每個(gè)VN的VRR請(qǐng)求就會(huì)壟斷頻譜資源，即請(qǐng)求多少就分配多少，不管其是否真實(shí)使用；而共享機(jī)制允許不同VNs的VRR機(jī)會(huì)性地共享相同的物理信道，這樣同樣情況下其真實(shí)占用的物理信道數(shù)量會(huì)顯著減少。

圖3 pi∈(0.1,0.2)時(shí)，平均占用信道數(shù)vs虛擬網(wǎng)絡(luò)數(shù)量Fig.3 Average occupied channel number vs number of virtual networks with pi∈(0.1,0.2)

為了驗(yàn)證VRR發(fā)生概率的不同對(duì)占用信道數(shù)量的影響，圖4仿真了VRR發(fā)生概率服從(0.2,0.3)的均勻分布，Vmax=10時(shí)，不同VN的數(shù)量與平均占用信道數(shù)量(即消耗的頻譜資源)之間關(guān)系。從圖4可以看出，所述頻譜共享算法占用的信道數(shù)量同樣比一般算法低。對(duì)比圖3和圖4，可以發(fā)現(xiàn)同樣數(shù)量的VN，VRR發(fā)生概率大則占用的信道數(shù)量會(huì)高于概率小的，這是因?yàn)樵诟怕瘦^小時(shí)，在碰撞閾值的約束下，單條物理信道允許共享的VN數(shù)量將會(huì)增多，相應(yīng)同樣數(shù)量的VNs占用的物理信道的數(shù)量會(huì)更少。但是無(wú)論發(fā)生概率大或者小，采用頻譜共享算法后，頻譜共享機(jī)制都會(huì)降低VN占用的物理信道量，從而提高其網(wǎng)絡(luò)收益。

4.2.2 閾值設(shè)置的合理性

圖5仿真了單個(gè)VN的VRR的最大值Vmax的變化與占用信道數(shù)量的情況。其中，VRR發(fā)生概率服從(0.1,0.2)的均勻分布，VNNumber=50。由圖5可以看到，隨著Vmax的增大，VNs對(duì)應(yīng)占用物理信道的數(shù)量隨之增長(zhǎng)。一般分配算法在Vmax≥25就不會(huì)隨著Vmax的增大而變化，這是因?yàn)榇藭r(shí)的物理信道已經(jīng)被占用完，其占用的物理信道數(shù)量穩(wěn)定在600，即信道總數(shù)；而頻譜共享算法，其占用物理信道的數(shù)量呈線性增長(zhǎng)，表明相同的Vmax下其占用的數(shù)量要少于一般分配算法，并且能接受更大Vmax的VN，從而會(huì)為WPN帶來(lái)更高的網(wǎng)絡(luò)收益。

圖4 pi∈(0.2,0.3)時(shí)，平均占用信道數(shù)量vs虛擬網(wǎng)絡(luò)數(shù)量Fig.4 Average occupied channel quantity vs number of virtual networks with pi∈(0.2,0.3)

圖5 pi∈(0.1,0.2)時(shí)，平均占用信道數(shù)vs VRR的VmaxFig.5 While pi∈(0.1,0.2) average occupied channel quantity vs Vmax of VRR

圖6仿真了VRR發(fā)生概率服從(0.2,0.3)的均勻分布時(shí)，Vmax的變化與平均占用信道數(shù)量的關(guān)系。從圖6中可以看出，隨著Vmax的增大，占用信道的數(shù)量也在增加，最終當(dāng)Vmax=50時(shí)，占用了600的信道數(shù)量，這是因?yàn)閂RR發(fā)生的概率增大后，相同數(shù)量的VN占用信道數(shù)量就更多，所以與VRR發(fā)生概率小的時(shí)候比起來(lái)，則占用的信道就變多。但是在整個(gè)仿真過(guò)程，占用的信道數(shù)都是低于一般分配算法，說(shuō)明當(dāng)VRR發(fā)生概率較大時(shí)，頻譜共享算法依然能夠在Vmax不夠大時(shí)占用更少的信道數(shù)。

4.2.3 VN請(qǐng)求動(dòng)態(tài)性時(shí)的接受率

下面仿真中，DAA-SRS算法基本假設(shè)和前提：VN的到達(dá)過(guò)程服從參數(shù)為λ的泊松分布過(guò)程，VN的生命周期服從參數(shù)為μ的指數(shù)分布，且λ=5,μ=10。VNs允許的最大映射時(shí)延D=2，物理網(wǎng)絡(luò)的總信道數(shù)C=600，碰撞閾值pth=0.1，收益系數(shù)a=1?；举Y源請(qǐng)求BRR和可變資源請(qǐng)求VRR均服從(5,15)的均勻分布，可變資源請(qǐng)求發(fā)生概率服從(0.1,0.3)的均勻分布。

圖6 pi∈(0.2,0.3)時(shí)，平均占用信道數(shù)vs VRR的VmaxFig.6 While pi∈(0.2,0.3) average occupied channel quantity vs Vmax of VRR

圖7是DAA-SRS算法與文獻(xiàn)[11]中Heuristic算法和一般分配算法在虛擬網(wǎng)絡(luò)接受率上的比較。從圖7可以發(fā)現(xiàn)，分配初期頻譜資源較為充足，因此接受率相差不大。隨著時(shí)間的推移，頻譜資源被逐漸占用，接受率隨之下降，并趨于穩(wěn)定?；陬l譜資源共享機(jī)制的2種算法在接受率上要高于一般分配算法，而DAA-SRS算法又明顯高于Heuristic算法。這是因?yàn)榛陬l譜資源共享的機(jī)制，使得相同數(shù)量的VNs占用更少的物理信道，有更多的物理資源可以接受后續(xù)VNs。而DAA-SRS算法在VNs生命周期的結(jié)束而離去時(shí)，進(jìn)行有效的資源重分配，使得占用的信道數(shù)量相比于文獻(xiàn)[11]的算法更少。

圖7 VN接受率的變化Fig.7 Change in VN acceptance rate

圖8給出了3種算法在網(wǎng)絡(luò)收益方面的比較。所述網(wǎng)絡(luò)收益是該時(shí)隙內(nèi)物理網(wǎng)絡(luò)中正在接受服務(wù)的所有虛擬網(wǎng)絡(luò)帶來(lái)的收益?？梢钥吹?，DAA-SRS算法在網(wǎng)絡(luò)收益方面要優(yōu)于其他2種算法。結(jié)合圖7和圖8可以看出，較高的虛擬網(wǎng)絡(luò)接受率與較高的網(wǎng)絡(luò)收益趨勢(shì)一致。DAA-SRS算法在接受率和收益方面均是最優(yōu)的。

圖9給出了不同到達(dá)率對(duì)接受率的影響，由圖9可知，虛擬網(wǎng)絡(luò)的接受率隨著λ的增大而降低。DAA-SRS算法的接受率相較于其他2種算法有顯著提高。可以預(yù)見，在針對(duì)較大規(guī)模數(shù)量的VN時(shí)，DAA-SRS算法仍然會(huì)獲得比較高的接受率，這得益于該算法模型充分考慮了動(dòng)態(tài)性、時(shí)變性和重分配的機(jī)制。DAA-SRS算法不僅能夠充分利用物理網(wǎng)絡(luò)資源，而且使得無(wú)線網(wǎng)絡(luò)負(fù)載更加均衡。

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

本文針對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求的動(dòng)態(tài)性以及時(shí)變性，在考慮了網(wǎng)絡(luò)動(dòng)態(tài)性導(dǎo)致物理資源出現(xiàn)碎片化或負(fù)載不均的情況下，提出了一種基于頻譜資源共享的動(dòng)態(tài)分配算法DAA-SRS。對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求的時(shí)變性進(jìn)行了分析，并建立了請(qǐng)求資源的模型；并根據(jù)虛擬網(wǎng)絡(luò)請(qǐng)求和物理資源的限制條件，建立了最大化網(wǎng)絡(luò)收益的目標(biāo)函數(shù)；最后，針對(duì)頻譜資源共享機(jī)制中存在的碰撞問(wèn)題進(jìn)行了較為詳細(xì)的討論，給出了可行的更新方式，即根據(jù)虛擬請(qǐng)求的動(dòng)態(tài)性，實(shí)時(shí)調(diào)整VRR資源映射。仿真結(jié)果表明，DAA-SRS算法在虛擬網(wǎng)絡(luò)接受率和物理網(wǎng)絡(luò)收益方面具有較優(yōu)性能。

參考文獻(xiàn)：

[1] YANG M, LI Y, ZENG L, et al. Karnaugh-map like online embeddingalgorithm of wireless virtualization[C]∥International Symposium on Wireless Personal Multimedia Communications. [S.l.]: IEEE Press, 2012:594-598.

[2] BELT Van de J, AHMADI H, DOYLE L E. A Dynamic Embedding Algorithm for Wireless Network Virtualization[C]∥Vehicular Technology Conference. Vancouver, BC, Canada: IEEE Press, 2015:1-6.

[3] FU F, KOZAT U C. Stochastic game for wireless network virtualization[J]. IEEE/ACM Transactions on Networking, 2013, 21(1):84-97.

[4] PARSAEEFARD S, JUMBA V, DERAKHSHANI M, et al. Joint resource provisioning and admission control in wireless virtualized networks[C]∥Wireless Communications and NETWORKING Conference. New Orleans, LA, USA: IEEE Press, 2015:2020-2025.

[5] ZHU Q, ZHANG X. Bayesian-game based power and spectrum virtualization for maximizing spectrum efficiency over mobile cloud-computing wireless networks[C]∥Computer Communications Workshops. [S.l.]: IEEE Press, 2015:1-6.

[6] YUN D, YI Y. Virtual network embedding in wireless multihop networks[C]∥International Conference on Future Internet Technologies. New York, NY, USA： ACM, 2011:30-33.

[7] 劉川川. 無(wú)線網(wǎng)絡(luò)虛擬化中資源分配算法研究[D]. 長(zhǎng)沙：湖南大學(xué), 2013.

LIUChuanchuan. Research in Resource Allocation Algorithm in Wireless Network Virtualization[D]. Changsha, China: Hunan University, 2013.

[8] YUN D, OK J, SHIN B, et al. Embedding of Virtual Network Requests over Static Wireless Multihop Networks[J]. Computer Networks, 2013, 57(5):1139-1152.

[9] ABDELWAHAB S, HAMDAOUI B, GUIZANI M, et al. Efficient Virtual Network Embedding With Backtrack Avoidance for Dynamic Wireless Networks[J]. IEEE Transactions on Wireless Communications, 2016, 15(4):2669-2683.

[10] YANG M, LI Y, LIU J, et al. Opportunistic spectrum sharing for wireless virtualization[C]∥Wireless Communications and Networking Conference. Istanbul, Turkey: IEEE Press, 2014:1803-1808.

[11] YANG M, LI Y, JIN D, et al. Opportunistic Spectrum Sharing Based Resource Allocation for Wireless Virtualization[C]∥International Conference on Innovative Mobile & Internet Services in Ubiquitous Computing. Taichung, Taiwan, China: IEEE Press, 2013:51-58.