非連通通信網(wǎng)絡(luò)中的分布式優(yōu)化算法

王靖瑤 郭景華

0 引言

隨著手機、電腦等電子產(chǎn)品的不斷普及,IP視頻流在現(xiàn)代網(wǎng)絡(luò)中占據(jù)了越來越重的份額．思科公司年度視覺網(wǎng)絡(luò)指數(shù)預(yù)測報告[1]指出,到2021年,IP視頻流量在整個網(wǎng)絡(luò)流量中的比重將會增長到82%,這遠(yuǎn)高于2016年的73%．此外,該報告還調(diào)研了用戶對于視頻發(fā)送服務(wù)的喜好,發(fā)現(xiàn)用戶對服務(wù)的體驗滿意程度決定著用戶對于服務(wù)商的選擇傾向．因此,整個視頻服務(wù)系統(tǒng)的成功運營不僅由它能否滿足用戶對視頻服務(wù)不斷增長的需求決定,還由它能否為用戶提供滿意的服務(wù)體驗決定．然而,現(xiàn)存的網(wǎng)絡(luò)資源分配協(xié)議卻不能為視頻服務(wù)系統(tǒng)的發(fā)展提供有力的支撐．這主要是因為:一方面,由于“大象流”的存在,現(xiàn)存的網(wǎng)絡(luò)中網(wǎng)絡(luò)資源分配不均現(xiàn)象頻發(fā);另一方面,用戶對服務(wù)的滿意程度函數(shù)作為數(shù)據(jù)率的函數(shù),是非凹的.

自Kelly等[2]引入網(wǎng)絡(luò)效用函數(shù)最大化問題以來,該問題框架已經(jīng)被多次應(yīng)用于網(wǎng)絡(luò)資源分配協(xié)議及網(wǎng)絡(luò)堵塞控制協(xié)議的研究．基于此問題框架的研究成果中,例如文獻(xiàn)[3-5],大部分考慮的是由FTP和HTTP等應(yīng)用產(chǎn)生的網(wǎng)絡(luò)流,而這些網(wǎng)絡(luò)流被認(rèn)為是彈性流,其對應(yīng)的網(wǎng)絡(luò)效用函數(shù)是嚴(yán)格的凹函數(shù)．考慮彈性流的好處在于,所得到的最大化網(wǎng)絡(luò)效用函數(shù)是容易求解的．但是,僅考慮彈性流卻影響了上述研究成果在實際中的應(yīng)用．這是因為,視頻流和音頻流被認(rèn)為是非彈性的,并且被建模為非凹函數(shù)．例如,手機用戶對視頻服務(wù)的滿意程度是一個關(guān)于數(shù)據(jù)率非減的并且階梯狀的函數(shù)[6].

視頻和音頻的這種非彈性特性逐漸被重視起來,文獻(xiàn)[7]提出了一種中心式算法來逼近最優(yōu)解,然而這種方法僅適用于優(yōu)化可以轉(zhuǎn)化成多項式形式的效用函數(shù)．文獻(xiàn)[8-14]則提出了分布式算法．文獻(xiàn)[8]針對效用函數(shù)為反曲函數(shù)的優(yōu)化問題提出了求解次優(yōu)解的啟發(fā)式算法；文獻(xiàn)[9]給出了在分布式梯度算法下收斂到全局最優(yōu)解的條件；文獻(xiàn)[10-11]針對連通通信模式下的互聯(lián)網(wǎng)網(wǎng)絡(luò)設(shè)計了分布式的流量分配方法,并通過仿真驗證了算法對于鏈路斷開的魯棒性；文獻(xiàn)[12-14]針對非連通通信模式下的互聯(lián)網(wǎng)網(wǎng)絡(luò)提出了分布式優(yōu)化算法,該算法通過以流量目的地分類流量的方法更新數(shù)據(jù)率來減少計算量,但是由于算法運行需要傳遞較多信息,執(zhí)行該算法仍需要較大的通信代價和計算代價.

本文針對非連通通信模式下的互聯(lián)網(wǎng)網(wǎng)絡(luò),考慮了最大化效用函數(shù)的問題,將用戶對服務(wù)的滿意程度建模為非凹的函數(shù)．因而,本文要解決的是非凸的優(yōu)化問題．本文的主要貢獻(xiàn)有兩方面:一方面,本文設(shè)計了一種分布式的流量分配算法來最大化網(wǎng)絡(luò)資源利用率,并且避免了鏈路堵塞事件的發(fā)生;另一方面,本文設(shè)計的協(xié)議使得每個節(jié)點根據(jù)局部信息來決定自身發(fā)送數(shù)據(jù)率,需要的非局部信息僅僅是路徑有沒有堵塞的信息,而這個信息僅占一個字節(jié)(1 B).

1 預(yù)備知識

2 分布式流量分配算法

2.1 問題描述

本文將效用函數(shù)最大化問題建模為

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

上述優(yōu)化問題的限制條件是超空間和超平面的交集,該問題很顯然是非凹的最大化問題．非凹的最大化問題是很難求解和分析的.

2.2 主要結(jié)果

注意到優(yōu)化問題(10)是非凸的,這意味著該問題很難分析和求解．為了解決該問題,本文將用一類如下式的類多項式函數(shù)逼近效用函數(shù):

(15)

基于上述逼近結(jié)果,有

(16)

(17)

(18)

(19)

(20)

類似于文獻(xiàn)[10],將上述問題轉(zhuǎn)化為下述等價問題:

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

(29)

yi,maxM(1,l-1,mi)-M(2,l,mi)0,

(30)

(31)

(32)

(33)

(34)

(35)

對于類型為i的流量,pi=[pi,α]α∈{1,…,n}和mi=[mi,α]α∈{1,…,n}是矩構(gòu)成的向量．yi,max是第i個數(shù)據(jù)率的已知上界．矩陣M(k,k+2h,mi)是如下式的漢克兒矩陣:

(36)

為了保持優(yōu)化問題(27)的緊性,本文引入下述記號.

yi,maxM(1,l-1,mi)-M(2,l,mi)0,

(37)

(38)

優(yōu)化問題(27)可以寫為

(39)

(40)

(41)

(42)

定理1優(yōu)化問題(39)的解可以逼近問題(16)的解.

證明該定理的證明可由文獻(xiàn)[10]中定理的證明得到.

接下來將求解凸優(yōu)化問題(39).

(43)

(44)

這里,fi(mi,ri)是矩限制和上下限限制的指示函數(shù),即:

(45)

g(x)同樣是指示函數(shù),即:

(46)

帶有二次約束的拉格朗日函數(shù)為

(47)

基于ADMM的算法如下:

算法1 ADMM算法1)更新m和r:對于類型為i的流量,(mi,ri)更新:(mi,ri)k+1=argmax(mi,ri)∈ ipTimi-vi(ri-Tixki)-ρ2(ri-Tixki+uki)2 ,i∈ .(48)2)更新x:Txk+1=Π (rk+1+uk),(49)其中Π (·)代表了向集合 的歐幾里得投影算子.3)更新u:對每個i∈ ,更新ui:uk+1i=uki+rk+1i-Tixki.(50)

注意到算法1中,x的更新步驟中需要全局信息,這就阻礙了將此算法應(yīng)用于分布式場景．為解決上述問題,注意到投影意味著解決下述二次規(guī)劃問題:

(51)

(52)

(53)

(54)

上述二次規(guī)劃問題的等價問題為

(55)

算法2 迭代算法 更新xi,1:對每個i∈ ,x(kg+1)i,1=x(kg)i,1-α(kg)(2(x(kg)i,1-(rk+1i+uki))+λ1βli+λ2γbi).(56)

(57)

(58)

(59)

令數(shù)據(jù)率xi,j是由節(jié)點b經(jīng)邊l發(fā)出．βli代表了鏈路l的擁堵信息,即:

(60)

(61)

分布式算法如下:

算法3 分布式算法 1)給定初始值x0,u0,k=0,1,…,N.2)每個發(fā)送流量的節(jié)點通過求解一個凸的半正定規(guī)劃問題更新它的數(shù)據(jù)率:(mi,ri)k+1=arg max(mi,ri)∈ ipTimi-vi(ri-Tixki)-ρ2(ri-Tixki+uki)2 ,i∈ .(62)3)給定初始值xkg,0←xk.4)kg=0,1,…,Ng,i=1,…,| |.5)每個節(jié)點b∈ i 查看它自身的流量守恒信息并且將γbi 發(fā)送它的最近的鄰居.6)每條鏈路l∈ b 將它的擁堵信息βli 發(fā)給它相連的邊節(jié)點, x(kg+1)i,1=x(kg)i,1-α(kg)(2(x(kg)i,1-(rk+1i+uki))+λ1βli+λ2γbi),(63) x(kg+1)i,j=x(kg)i,j-α(kg)(λ1βli+λ2γbi),j∈{2,…,| i|,(64) xk+1←xk,kg.(65)7)每個發(fā)送流量的節(jié)點更新它的對偶變量 uk+1i=uki+rk+1i-zki,i∈ .(66)

定理2算法3生成的序列{(mi,xi,ri,zi,ρui)}收斂到優(yōu)化問題的一個KKT點.

證明該定理的結(jié)果可通過文獻(xiàn)[15]中的結(jié)果得到.

3 仿真結(jié)果

考慮通信網(wǎng)絡(luò)圖2．網(wǎng)絡(luò)中流量類型集合為S={1,…,8},并且多項式目標(biāo)函數(shù)的階數(shù)為n=6．算法參數(shù)為ρ=0.7,α(kg)=1/kg和λ1=λ2=8．圖3比較了Ng=103時算法3和基因算法求解結(jié)果．從圖3可以發(fā)現(xiàn):雖然算法3是分布式的求解方法,但是該方法得到的目標(biāo)函數(shù)值會收斂到基因算法這種中心式算法得到的全局最優(yōu)解．這充分說明了算法3的有效性.

4 結(jié)束語

本文針對非連通通信模式下的互聯(lián)網(wǎng)網(wǎng)絡(luò)提出了一種分布式的流量分配方法．該方法可以有效地最大化網(wǎng)絡(luò)效用函數(shù),提高用戶對服務(wù)的體驗滿意程度,并且避免網(wǎng)絡(luò)中鏈路堵塞和流量丟失等現(xiàn)象的發(fā)生．仿真結(jié)果表明,雖然本文提出的方法是分布式的,但是該方法得到的結(jié)果可以收斂到原問題的最優(yōu)解.