王 聰 張鳳荔王瑞錦 李 敏 楊曉翔

(電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 611731)

1 引言

互聯(lián)網(wǎng)環(huán)境下的許多重要應(yīng)用，包括內(nèi)容分發(fā)網(wǎng)絡(luò)(CDN)[1]，電子競技[2,3]，云計(jì)算[4,5]等，其性能都強(qiáng)烈依賴于網(wǎng)絡(luò)時(shí)延矩陣的感知與獲取。點(diǎn)對(duì)點(diǎn)的測(cè)量雖然能夠精確填充時(shí)延矩陣的任一元素，但其測(cè)量復(fù)雜度達(dá)到O(n2)，難以擴(kuò)展到大規(guī)模網(wǎng)絡(luò)應(yīng)用。如何利用有限的測(cè)量數(shù)據(jù)盡可能精確地恢復(fù)時(shí)延矩陣，已引起了廣泛關(guān)注。

早期關(guān)于非測(cè)量方式的時(shí)延矩陣重建研究將節(jié)點(diǎn)嵌入到特定的度量空間，以節(jié)點(diǎn)在度量空間內(nèi)的距離擬合節(jié)點(diǎn)間的真實(shí)時(shí)延，此類研究成果通常被歸為網(wǎng)絡(luò)坐標(biāo)系統(tǒng)(Network Coordinate System,NCS)[6]。雖然 NCS能夠滿足一定程度上的性能需求，也已在工業(yè)環(huán)境下得到部分應(yīng)用，然而互聯(lián)網(wǎng)中廣泛存在的非對(duì)稱路由和非最短路徑路由現(xiàn)象卻違背了度量空間的定義，且NCS涉及的非凸優(yōu)化問題也使其難以避免局部極小化現(xiàn)象。近期研究證明時(shí)延矩陣具備明顯的近似稀疏性，即矩陣僅有少數(shù)的特征值具有較大的模[7]。文獻(xiàn)[8]已就這種稀疏特征及其與 NCS度量空間的維度關(guān)系進(jìn)行了理論上的深入分析與闡述，從而將NCS歸結(jié)為某種意義上的時(shí)延矩陣稀疏逼近模型。根據(jù)Candes等人[9]的研究，盡管時(shí)延矩陣重建是一個(gè)欠定問題，但在附加必要的稀疏性約束之后，該問題可以高概率得到惟一的可行解。這種約束一般為矩陣的零范數(shù)或跡范數(shù)的極小化約束，以限制重建模型的復(fù)雜程度。然而在分布式環(huán)境下，如對(duì)等網(wǎng)絡(luò)或分布式控制系統(tǒng)，抽取一個(gè)全局一致的時(shí)延矩陣映像通常是困難的。一個(gè)折中的方法是定義一個(gè)可能滿足稀疏性約束的時(shí)延矩陣零范數(shù)先驗(yàn)估計(jì)，并將時(shí)延矩陣的左右特征向量分布在全網(wǎng)中共同維護(hù)，使得每個(gè)參與計(jì)算的節(jié)點(diǎn)均持有一個(gè)行向量和列向量，通過向量的點(diǎn)積運(yùn)算，任一節(jié)點(diǎn)都可以補(bǔ)全與其相關(guān)的元素。與基于內(nèi)積運(yùn)算的NCS模型相比，這種方法具備顯著良好的特性：一是容易轉(zhuǎn)化為凸優(yōu)化問題求解；二是容易處理非最短路徑路由引起的三角違例(Triangle Inequality Violations, TIVs)現(xiàn)象；三是不要求重建矩陣嚴(yán)格對(duì)稱，因而容易處理非對(duì)稱路由問題。基于這種思想，文獻(xiàn)[10]首先提出了一種原型算法 IDES，但時(shí)延空間可能存在的多子流形特征[11]，以及先驗(yàn)估計(jì)的不精確性，使得向量維護(hù)和更新過程中難以避免病態(tài)矩陣的求逆運(yùn)算，導(dǎo)致計(jì)算精度難以滿足要求[12]，因而一直未能引起足夠的重視。直到Liao等人[13]通過引入正則化算子實(shí)現(xiàn)了基于最小均方誤差有偏估計(jì)的 DMF算法，重建算法的魯棒性才得到實(shí)質(zhì)性的提升。而Phoenix算法繼承了正則化處理的思路，并通過非負(fù)約束解決了重建矩陣中的負(fù)值元素問題[14]。最近，包括1l損失函數(shù)和Huber損失函數(shù)在內(nèi)的兼顧魯棒性和異常數(shù)據(jù)處理能力的誤差優(yōu)化準(zhǔn)則也開始引起關(guān)注[15,16]。但受限于目標(biāo)函數(shù)的非光滑性和向量的非負(fù)約束，求解此類損失函數(shù)通常僅依賴于梯度下降法，收斂速度并不令人滿意。

本文提出一種支持多種誤差評(píng)價(jià)準(zhǔn)則的時(shí)延矩陣重建ADMC算法。通過引入伸縮因子實(shí)現(xiàn)對(duì)不同誤差評(píng)價(jià)準(zhǔn)則和生命周期不同階段下梯度下降步長的自適應(yīng)搜索，在不損失計(jì)算精度的前提下，以較低的計(jì)算代價(jià)提升模型的泛化能力。

2 時(shí)延矩陣分布式重建的自適應(yīng)迭代算法

時(shí)延矩陣分布式重建的基本思想是，一個(gè)包含P個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)存在PP×的時(shí)延矩陣D，其中的任一元素,ijd 代表節(jié)點(diǎn)i到節(jié)點(diǎn)j的傳輸時(shí)延，受到網(wǎng)絡(luò)規(guī)模和計(jì)算資源的限制，一般情況下D會(huì)因?yàn)椴糠謹(jǐn)?shù)據(jù)的缺失而轉(zhuǎn)變?yōu)椴煌暾仃?'D ，時(shí)延矩陣重建的目的在于利用 'D 提供的有限信息，生成一個(gè)完整矩陣︿D，使之成為D的良好擬合，全局一致的不完整矩陣稀疏逼近已得到深入的研究[17,18]?？紤]到時(shí)延矩陣的近似稀疏性，這種思路顯然是合理的。但在完全去中心化的環(huán)境下，時(shí)延矩陣一致映像的抽取通常是難以完成的。一般而言，節(jié)點(diǎn)容易協(xié)商得到一致的重建矩陣︿D的零范數(shù)先驗(yàn)估計(jì)N，以確保稀疏性。此時(shí)零范數(shù)的極小化約束可松弛為等式約束，即求解如式(1)的約束優(yōu)化問題：

其中Ω是 'D 所有未缺失元素的下標(biāo)子集，PΩ是Ω上的投影算子，即只取在Ω中的對(duì)應(yīng)元素進(jìn)行計(jì)算；是預(yù)定義的誤差損失函數(shù)；計(jì)算矩陣的零范數(shù)，即矩陣的非零特征值個(gè)數(shù)。易知可表示為兩個(gè)PN×的系數(shù)矩陣U和V的乘積：

于是,ijd可用的對(duì)應(yīng)元素,ijd?擬合：

由于U或V行向量之間的不存在交集元素，這使其易分布于全網(wǎng)共同進(jìn)行維護(hù)：令任一節(jié)點(diǎn)i持有U和V中對(duì)應(yīng)的行向量iu和iv，則節(jié)點(diǎn)只需獲得目標(biāo)節(jié)點(diǎn)持有的向量，便可計(jì)算與對(duì)方的近似時(shí)延，從而大大減少了網(wǎng)絡(luò)測(cè)量帶來的資源開銷。對(duì)應(yīng)地，式(1)可分解為如式(4)兩個(gè)耦合子問題的聯(lián)立：

當(dāng)取l1損失函數(shù)作為誤差評(píng)價(jià)準(zhǔn)則時(shí)，有

此時(shí)，有

當(dāng)取l2損失函數(shù)作為誤差評(píng)價(jià)準(zhǔn)則時(shí)，有

此時(shí)，有

當(dāng)取Huber損失函數(shù)作為誤差評(píng)價(jià)準(zhǔn)則時(shí)，有

此時(shí)，有

根據(jù)文獻(xiàn)[19]的定理 2.1.6，當(dāng)損失函數(shù)為凸函數(shù)時(shí)，可保證式(5)為凸優(yōu)化問題，此時(shí)式(5)的優(yōu)化過程與此類同，限于篇幅在此不予討論。接下來討論式(6)的求解。顯然地，系統(tǒng)生命周期的不同階段對(duì)ηu和ηv的要求是不同的：在系統(tǒng)生成初期或網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生突變時(shí)，需要以較大的步長快速收斂到最優(yōu)值附近；而當(dāng)系統(tǒng)進(jìn)入到穩(wěn)定狀態(tài)時(shí)，需要以較小的步長進(jìn)行逐步求精，并能感知和快速適應(yīng)隨時(shí)可能發(fā)生的拓?fù)渫蛔?，如蜂集態(tài)(flash- crowd)等。對(duì)生命周期不同階段需求進(jìn)行折中，DMFSGD算法[16]提出了一種基于折半查找的步長搜索策略，針對(duì)不同的損失函數(shù)的搜索上界maxη，通過實(shí)驗(yàn)給出了不同的定義。但該策略的缺點(diǎn)也顯而易見：當(dāng)較大時(shí)，算法在穩(wěn)定狀態(tài)下須經(jīng)過多輪查找才能得到恰當(dāng)?shù)闹?；而?dāng)maxη較小時(shí)，算法難以在可接受的時(shí)間內(nèi)收斂到穩(wěn)定狀態(tài)。我們注意到，系統(tǒng)生命周期的不同階段存在一定的延續(xù)性，即后一時(shí)刻的系統(tǒng)狀態(tài)與前一時(shí)刻往往不會(huì)有明顯的差異，換言之，相鄰兩個(gè)時(shí)刻的迭代步長通常并不是條件獨(dú)立的。基于這種假設(shè)，ADMC算法利用步長搜索的歷史信息提出了一種基于上界倍增的步長搜索策略，以上一輪迭代成功檢索的步長因子的某個(gè)倍數(shù)為搜索上界，進(jìn)行折半查找，從而達(dá)到降低計(jì)算代價(jià)的目的。整個(gè) ADMC算法的實(shí)現(xiàn)偽代碼如表 1所示。

ADMC算法中，搜索上界的倍增因子定義為2。當(dāng)系統(tǒng)剛剛建立，或發(fā)生拓?fù)渫蛔儠r(shí)，該值足以確保迭代步長呈指數(shù)級(jí)增長，快速適應(yīng)新的網(wǎng)絡(luò)拓?fù)?。?1展現(xiàn)的細(xì)節(jié)顯示，與 DMFSGD算法相同，ADMC算法的計(jì)算復(fù)雜度同樣為，其中n是節(jié)點(diǎn)在構(gòu)造優(yōu)化函數(shù)時(shí)選取的參考節(jié)點(diǎn)數(shù)；m是梯度下降步長搜索的輪數(shù)?？梢夾DMC算法的測(cè)量與計(jì)算代價(jià)與網(wǎng)絡(luò)規(guī)模無關(guān)，同樣適用于海量節(jié)點(diǎn)在線的網(wǎng)絡(luò)應(yīng)用。而相對(duì)于DMFSGD算法，ADMC基于歷史信息的步長搜索策略通常可以得到較小的m，因而其計(jì)算代價(jià)也顯著較低。

表1 ADMC重建算法的偽代碼

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

為了檢驗(yàn)?zāi)Ｐ偷乃俣?、精度與計(jì)算代價(jià)，本文以DMFSGD算法作為基準(zhǔn)算法與ADMC算法進(jìn)行性能對(duì)比。所有的算法均假定鄰居節(jié)點(diǎn)數(shù)為60個(gè)。實(shí)驗(yàn)以Planetlab數(shù)據(jù)集[20]為仿真基礎(chǔ)，該數(shù)據(jù)集測(cè)量了226個(gè)Planetlab節(jié)點(diǎn)之間4h內(nèi)的傳輸時(shí)延。在所有實(shí)驗(yàn)中，均取重建矩陣的零范數(shù)先驗(yàn)估計(jì)N=5，正則化因子λ=1。

首先定義距離計(jì)算相對(duì)誤差(Relative Error,RE)以評(píng)價(jià)系統(tǒng)性能，定義如式(13)：

與之相關(guān)地，引入相對(duì)誤差的 90%分位數(shù)(Ninetieth Percentile Relative Error, NPRE)作為算法整體性能評(píng)價(jià)指標(biāo)[21]。

3.1 l1損失函數(shù)性能分析

當(dāng)基于 l1損失函數(shù)進(jìn)行矩陣重建時(shí)，取推薦值，可得系統(tǒng)性能如圖1所示。其中，圖1(a)是每一輪迭代中步長折半查找的次數(shù)，決定了算法的計(jì)算代價(jià)?？梢钥闯?，在系統(tǒng)的初始階段，DMFSGD算法基本無須折半查找，將搜索上界代入計(jì)算即可生成損失函數(shù)非遞增迭代序列。這表明，由于折中得到的搜索上界并非此時(shí)的最佳步長。這一現(xiàn)象在圖1(b)和圖1(c)中也得到體現(xiàn)。如圖1(b)所示，以ADMC算法搜索得到的步長為對(duì)比，當(dāng)?shù)介L在0.15左右時(shí)，梯度下降算法才能得到相對(duì)令人滿意的收斂速度。圖 1(c)是系統(tǒng)初始階段的NPRE演進(jìn)曲線。得益于步長的自適應(yīng)搜索策略，ADMC的收斂速度顯然較DMFSGD更快。需要指出的是，由于向量的初始化策略和 l1損失函數(shù)必然導(dǎo)致的誤差截?cái)啵沟迷谙到y(tǒng)的起始階段無論ADMC抑或DMFSGD都存在一小段“冰凍”時(shí)期。但顯然ADMC的反應(yīng)更為敏捷，也有較高的收斂速度。由圖 1(a)可以看到：隨著時(shí)延矩陣重建算法逐漸收斂到穩(wěn)定的狀態(tài)，DMFSGD算法的計(jì)算代價(jià)隨之升高。每輪迭代中，DMFSGD平均需要搜索6~7次才能查找到恰當(dāng)?shù)牡介L；反觀本文提出的ADMC算法，每輪迭代中折半查找次數(shù)始終維持在1.95~2.05次之間，計(jì)算代價(jià)較 DMFSGD降低約65%~70%。這一趨勢(shì)在圖1(b)中得到印證：當(dāng)系統(tǒng)趨于穩(wěn)定時(shí)，恰當(dāng)?shù)牡介L穩(wěn)定在左右，恰好是DMFSGD算法進(jìn)行6~7次折半查找得到的值；而完成同樣的工作ADMC通常僅需兩次折半查找即可。雖然ADMC算法的計(jì)算代價(jià)大幅降低，但計(jì)算性能并未隨之產(chǎn)生下降。圖 1(c)中明顯看出，當(dāng)系統(tǒng)收斂時(shí)，ADMC和DMFSGD算法得到極為相似的NPRE演進(jìn)曲線。深入觀察此時(shí)的矩陣填充相對(duì)誤差累積分布如圖1(d)，可見兩種算法的累積分布曲線幾乎完全重合。由于凸優(yōu)化問題僅存在一個(gè)極優(yōu)解暨全局最優(yōu)解，兩種不同的算法收斂到同一個(gè)解是必然的。

3.2 l2損失函數(shù)性能分析

圖1 l1損失函數(shù)算法性能

圖2 l2損失函數(shù)算法性能

當(dāng)以l2損失函數(shù)為評(píng)價(jià)準(zhǔn)則時(shí)，取推薦值，可得系統(tǒng)性能如圖2。不同于l1損失函數(shù)，l2損失函數(shù)的迭代步長選取須考慮重建誤差的模，因此搜索上界較 l1損失函數(shù)更低，受網(wǎng)絡(luò)抖動(dòng)的影響卻大得多。動(dòng)態(tài)環(huán)境下的步長平均搜索次數(shù)如圖2(a)所示?？梢钥闯?，受數(shù)據(jù)集內(nèi)蘊(yùn)的拓?fù)浣Y(jié)構(gòu)突變影響，DMFSGD算法的步長搜索次數(shù)也隨之從4次左右跳變至6~8次；而ADMC的表現(xiàn)則較為魯棒，步長搜索次數(shù)同樣維持在1.95~2.05次之間，與采用l1損失函數(shù)時(shí)幾乎相同，比DMFSGD平均下降 50%~80%。如圖 2(b)所示，無論 DMFSGD還是ADMC在歷輪迭代最終選取的步長極為相似，在兩個(gè)不同的拓?fù)浣Y(jié)構(gòu)下，分別為和，說明ADMC在l2損失函數(shù)被引入時(shí)對(duì)迭代步長的搜索能力也不弱于 DMFSGD。雖然ADMC的計(jì)算代價(jià)明顯低于DMFSGD，重建精度和速度的表現(xiàn)卻不因此而降低：圖2(c)的NPRE演進(jìn)曲線顯示，ADMC可以取得和DMFSGD幾乎相同的收斂速度?？梢钥闯?，由于此時(shí)不存在對(duì)誤差的截?cái)?，盡管搜索上界減小了一個(gè)數(shù)量級(jí)，但相對(duì)于 l1損失函數(shù)，l2損失函數(shù)的引入依然顯著提升了DMFSGD和ADMC的收斂速度。值得注意的是，伴隨著收斂速度的提升，矩陣重建的精度卻不能盡如人意。如圖2(d)中的相對(duì)誤差累積分布曲線所示，l2損失函數(shù)作為評(píng)價(jià)準(zhǔn)則時(shí)，矩陣重建的誤差顯著高于 l1損失函數(shù)評(píng)價(jià)準(zhǔn)則?；谇捌诠ぷ鞯难芯?，可認(rèn)為是由于 l2損失函數(shù)對(duì)于時(shí)延序列中存在的抖動(dòng)現(xiàn)象更加敏感，難以處理隨機(jī)延遲污染所致。

3.3 Huber損失函數(shù)性能分析

Huber損失函數(shù)是l1損失函數(shù)和l2損失函數(shù)的混合。實(shí)驗(yàn)中取。實(shí)驗(yàn)證明， Huber損失函數(shù)的引入能夠兼顧收斂速度和重建精度。如圖3(a)所示，基于 Huber損失函數(shù)作為評(píng)價(jià)準(zhǔn)則，ADMC的計(jì)算代價(jià)同樣遠(yuǎn)遠(yuǎn)低于DMFSGD。從算法運(yùn)行的初始階段開始直到穩(wěn)定階段，ADMC的迭代搜索次數(shù)除最初的數(shù)輪迭代中上升到2.1次左右，一直穩(wěn)定在1.95~2.05次之間，與其它損失函數(shù)被引入時(shí)幾乎沒有差異。相比之下，DMFSGD的平均步長搜索次數(shù)從起初的 1次攀升至穩(wěn)定狀態(tài)時(shí)的6.5~6.8次，計(jì)算量遠(yuǎn)遠(yuǎn)高于ADMC。圖3(b)中可以看出，當(dāng)系統(tǒng)處于穩(wěn)定狀態(tài)時(shí)，雖然ADMC僅進(jìn)行少數(shù)幾次迭代，但搜索得到的迭代步長與DMFSGD仍然十分接近：雖然在起始階段ADMC搜索得到的迭代步長約為DMFSGD的一倍，但隨著算法的收斂最終ADMC和DMFSGD都將梯度下降算法的迭代步長穩(wěn)定在區(qū)間內(nèi)，這表明 ADMC提出的步長搜索策略具備較強(qiáng)的泛化能力，從側(cè)面驗(yàn)證了策略的有效性。圖 3(c)體現(xiàn)了算法的收斂速度?？梢钥闯?，雖然Huber損失函數(shù)同樣進(jìn)行了誤差截?cái)?，但收斂速度卻超過了采用 l1損失函數(shù)時(shí)的收斂速度。由于算法迭代初值位于原點(diǎn)附近，因此絕大部分計(jì)算誤差都落入 l1損失函數(shù)區(qū)間，于是Huber損失函數(shù)的ε參數(shù)在此起到了步長放大的作用，提升了收斂速度；而當(dāng)算法趨于穩(wěn)定時(shí)，相當(dāng)部分的計(jì)算誤差則落入l2損失函數(shù)區(qū)間，此時(shí)Huber損失函數(shù)截?cái)嗔孙@著異常的計(jì)算誤差，從而有效過濾了時(shí)延毛刺所造成的延遲污染，達(dá)到較好的重建精度。而從圖3(d)中可以看出，此時(shí)矩陣重建的誤差與 l1損失函數(shù)不相上下，顯著優(yōu)于 l2損失函數(shù)。由以上實(shí)驗(yàn)可得，Huber損失函數(shù)的引入能夠兼顧收斂速度和異常數(shù)據(jù)處理能力，具備優(yōu)良的特性。

圖3 Huber損失函數(shù)算法性能

4 結(jié)束語

時(shí)延敏感型應(yīng)用的優(yōu)化強(qiáng)烈依賴于時(shí)延矩陣的感知與重建。不同于傳統(tǒng)的分布式時(shí)延矩陣重建算法，本文在關(guān)注矩陣重建精度的同時(shí)，著重考慮了算法的計(jì)算代價(jià)和泛化能力，以確保實(shí)時(shí)性和特殊環(huán)境下的算法性能。由此，本文試圖提出一種支持多種誤差評(píng)價(jià)準(zhǔn)則的時(shí)延矩陣重建算法：通過伸縮因子的引入來實(shí)現(xiàn)步長搜索上界的自適應(yīng)升降，在滿足不同評(píng)價(jià)準(zhǔn)則和生命周期不同階段下，梯度下降步長快速搜索的同時(shí)，以指數(shù)級(jí)的伸縮速率實(shí)現(xiàn)了對(duì)拓?fù)渫蛔兊拿艚葸m應(yīng)。進(jìn)一步地，本文引入了多種誤差損失函數(shù)，在不損失計(jì)算精度的前提下，以較低的計(jì)算代價(jià)提升了模型的泛化能力。

[1] Szymaniak M, Presotto D, Pierre G, et al.. Practical largescale latency estimation[J]. Computer Networks, 2008, 52(7):1343-1364.

[2] Agarwal S and Lorch R. Matchmaking for online games and other latency-sensitive P2P systems[C]. Proceedings of the ACM SIGCOMM 2009, Barcelona, 2009: 315-326.

[3] Armitage G and Heyde A. REED: optimizing first person shooter game server discovery using network coordinates[J].ACM Transactions on Multimedia Computing,Communications, and Applications, 2012, DOI:10.1145/21268996. 2169000.

[4] Agarwal S, Dunagan J, Jain N, et al.. Volley: automated data placement for geo-distributed cloud services[C]. Proceedings of the 7th USENIX Symposium on Networked Systems Design ＆amp; Implementation (NSDI), San Jose, 2010: 1-16.

[5] Ding C, Chen Y, Xu T, et al.. CloudGPS: a scalable and ISP-friendly server selection scheme in cloud computing environments[C]. Proceedings on the 20th International Workshop on Quality of Service (IWQoS), Coimbra, 2012: 5.

[6] 王占豐, 陳鳴, 邢長友, 等. 因特網(wǎng)時(shí)延空間建模的研究[J].通信學(xué)報(bào), 2012, 33(7): 164-176.Wang Zhan-feng, Chen Ming, Xing Chang-you, et al..Research on the modeling of the Internet delay space[J].Journal on Communications, 2012, 33(7): 164-176.

[7] Lee S, Zhang Z L, Sahu S, et al.. On suitability of Euclidean embedding for host-based network coordinate systems[J].IEEE/ACM Transactions on Networking, 2010, 18(1): 27-40.

[8] Candès E J and Plan Y. Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements[J]. IEEE Transactions on Information Theory,2011, 57(4): 2342-2359.

[9] Candès E J and Recht B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics,2009, 9(6): 717-772.

[10] Mao Y, Saul L K, and Smith J M. IDES: an internet distance estimation service for large networks[J]. IEEE Journal on Selected Areas in Communications, 2006, 24(12): 2273-2284.

[11] Wang Z F, Chen M, Xing C, et al.. Multi-manifold model of the Internet delay space[J]. Journal of Network and Computer Applications, 2013, 31(1): 211-218.

[12] Zhang R, Tang C, Hu Y C, et al.. Impact of the inaccuracy of distance prediction algorithms on Internet applications-an analytical and comparative study[C]. Proceedings on 25th IEEE INFOCOM, Barcelona, 2006: 1-12.

[13] Liao Y, Geurts P, and Leduc G. Network distance prediction based on decentralized matrix factorization[C]. Proceedings on the 9th International IFIP TC6 Networking Conference,Chennai, 2010: 15-26.

[14] Chen Y, Wang X, Shi C, et al.. Phoenix: a weight-based network coordinate system using matrix factorization[J].IEEE Transactions on Network and Service Management,2011, 8(4): 334-347.

[15] Tang L, Shen Z, Lin Q, et al.. Towards a robust framework of network coordinate systems[C]. Proceedings on the 9th International IFIP TC6 Networking Conference, Prague,2012: 331-343.

[16] Liao Y, Du W, Geurts P, et al.. DMFSGD: a decentralized matrix factorization algorithm for network distance prediction[J]. IEEE/ACM Transactions on Networking, 2013,21(5): 1511-1524.

[17] 史加榮, 焦李成, 尚凡華. 不完全非負(fù)矩陣分解的加速算法[J].電子學(xué)報(bào), 2011, 39(2): 291-295.Shi Jia-rong, Jiao Li-cheng, and Shang Fan-hua. Accelerated algorithm to incomplete nonnegative matrix dactorization[J].Acta Electronica Sinica, 2011, 39(2): 291-295.

[18] 張振躍, 趙科科. 數(shù)據(jù)缺損矩陣低秩分解的正則化方法[J]. 中國科學(xué): 數(shù)學(xué), 2013, 43(3): 249-271.Zhang Zhen-yue and Zhao Ke-ke. Regularization methods for low-rank factorization of matrices with missing data[J].SCIENTIA SINICA Mathematica, 2013, 43(3): 249-271.

[19] 胡毓達(dá). 凸分析與非光滑分析[M]. 上海: 上?？茖W(xué)技術(shù)出版社, 2000: 52.

[20] PlanetLabDataset[OL]. http://www.eecs.harvard.edu/~syrah /nc/sim/pings.4hr.stamp.gz. 2012.5.

[21] Wu S, Chen Y, Fu X, et al.. NCShield: securing decentralized,matrix factorization-based network coordinate systems[C].Proceedings on the 20th International Workshop on Quality of Service (IWQoS), Coimbra, 2012: 1.