寧穎丹，任清元，高隨祥 ，鄧浩江，楊文國(guó)*

(1.中國(guó)科學(xué)院大學(xué)數(shù)學(xué)科學(xué)學(xué)院，北京 100049; 2.中國(guó)科學(xué)院大數(shù)據(jù)挖掘與知識(shí)管理重點(diǎn)實(shí)驗(yàn)室,北京 100049;3.山東工業(yè)職業(yè)學(xué)院,山東 淄博 256414;　4.中國(guó)科學(xué)院聲學(xué)研究所,北京 100190)

?

考慮節(jié)點(diǎn)失效的QoE測(cè)量點(diǎn)魯棒選址問題研究

寧穎丹1,2，任清元3，高隨祥1,2，鄧浩江4，楊文國(guó)1,2*

(1.中國(guó)科學(xué)院大學(xué)數(shù)學(xué)科學(xué)學(xué)院，北京 100049; 2.中國(guó)科學(xué)院大數(shù)據(jù)挖掘與知識(shí)管理重點(diǎn)實(shí)驗(yàn)室,北京 100049;3.山東工業(yè)職業(yè)學(xué)院,山東 淄博 256414;4.中國(guó)科學(xué)院聲學(xué)研究所,北京 100190)

摘要：QoE測(cè)量點(diǎn)選址問題是選擇盡可能少的測(cè)量點(diǎn)來準(zhǔn)確反映網(wǎng)絡(luò)中用戶獲取服務(wù)的情況。本文基于失效概率已知的QoE測(cè)量點(diǎn)選址模型，用區(qū)間描述失效概率的不確定性，建立了QoE測(cè)量點(diǎn)選址的魯棒模型，并將其轉(zhuǎn)化為混合整數(shù)線性規(guī)劃求解。測(cè)試結(jié)果表明了魯棒選址模型對(duì)考慮節(jié)點(diǎn)失效的QoE測(cè)量點(diǎn)選址問題的有效性，算例分析表明覆蓋率和失效個(gè)數(shù)對(duì)選址方案有不同程度的影響。

關(guān)鍵詞：設(shè)施選址；魯棒優(yōu)化；節(jié)點(diǎn)失效；QoE

用戶體驗(yàn)質(zhì)量(quality of experience，QoE)[1]是一種以用戶認(rèn)可程度為標(biāo)準(zhǔn)的服務(wù)的評(píng)價(jià)方法,綜合了服務(wù)層面、用戶層面和環(huán)境層面的影響因素。有關(guān)QoE的研究主要涉及以下幾個(gè)方面：QoE的定義及影響因素、量化方法、評(píng)價(jià)指標(biāo)、評(píng)價(jià)方法與模型以及基于QoE的網(wǎng)絡(luò)優(yōu)化。QoE的測(cè)量[2]是采用合理的監(jiān)測(cè)手段和計(jì)量方法對(duì)可預(yù)設(shè)的指標(biāo)包括終端質(zhì)量(quality of terminal，QoT)與開發(fā)者對(duì)用戶QoE的貢獻(xiàn)(quality of development，QoD)的關(guān)鍵網(wǎng)絡(luò)性能指標(biāo)(key performance indicators，KPI)信息及關(guān)鍵業(yè)務(wù)質(zhì)量指標(biāo)(key quality indicators，KQI)進(jìn)行監(jiān)視和測(cè)量，甚至可以監(jiān)測(cè)和收集用戶的行為習(xí)慣以及一些用戶的注冊(cè)信息等，在網(wǎng)絡(luò)管理系統(tǒng)(network management system，NMS)上實(shí)現(xiàn)，幫助運(yùn)營(yíng)商正確有效地對(duì)QoE進(jìn)行評(píng)估，并且為運(yùn)營(yíng)商面向QoE的運(yùn)維管理體系提供完善的手段與方法。QoE測(cè)量分為計(jì)算機(jī)網(wǎng)絡(luò)測(cè)量和無線通信網(wǎng)絡(luò)測(cè)量[2]，無線通信網(wǎng)絡(luò)QoE測(cè)量用外置探針以主動(dòng)測(cè)量方式來進(jìn)行。外置探針是一種特殊的測(cè)量設(shè)備，可以通過模擬用戶使用網(wǎng)絡(luò)來直接獲取QoE值，如分布式移動(dòng)QoS代理；也可以通過將有關(guān)的測(cè)量軟件安裝在用戶終端,將眾多用戶變成測(cè)試代理，具有樣本可靠度高, 測(cè)量結(jié)果較為穩(wěn)定、精確的特點(diǎn)。

為了解網(wǎng)絡(luò)中用戶接受服務(wù)的效果，需要在備選的測(cè)量集中選取若干點(diǎn)，在測(cè)量點(diǎn)上放置外置探針模擬用戶的各種訪問需求。假設(shè)已經(jīng)知道各測(cè)量點(diǎn)可測(cè)量的用戶范圍，同時(shí)為了節(jié)省成本，測(cè)試點(diǎn)的個(gè)數(shù)越少越好。這就是QoE測(cè)量網(wǎng)選點(diǎn)問題，可以抽象為圖論中的集覆蓋問題[4]。最近，寧穎丹等[5]建立了QoE測(cè)量網(wǎng)選點(diǎn)問題的魯棒選址集覆蓋模型，設(shè)計(jì)了以最小化選取測(cè)試點(diǎn)為目標(biāo)，求解魯棒集覆蓋問題的貪婪算法。然而在實(shí)際情況中，各測(cè)量點(diǎn)的外置探針可能由于某些內(nèi)在的原因，如結(jié)構(gòu)簡(jiǎn)單、能量有限，或者外在的因素，如自然或者人為影響，發(fā)生故障而不能夠正常測(cè)量用戶接受服務(wù)的效果，使得QoE的測(cè)量結(jié)果出現(xiàn)偏差。這種情況的發(fā)生具有突發(fā)性和難以預(yù)測(cè)性，建立測(cè)量點(diǎn)通常成本高、決策期長(zhǎng)，在一個(gè)長(zhǎng)的時(shí)期內(nèi)，很多參數(shù)都會(huì)發(fā)生波動(dòng)，從而造成環(huán)境的不確定性；若在事前建立大量測(cè)量點(diǎn)，則在經(jīng)濟(jì)上難以承受且不具備良好的可操作性。

考慮各測(cè)量點(diǎn)均存在失效的可能，即正常服務(wù)的概率小于1，此時(shí)QoE測(cè)量網(wǎng)選點(diǎn)問題可抽象為設(shè)施失效的選址問題。近年來，不確定選址問題已有很好的理論結(jié)果[6]。Drezner[7]最早對(duì)考慮設(shè)施失效的選址問題進(jìn)行研究, 構(gòu)建了設(shè)施失效情景下的P-中心模型和P-中值模型。Snyder等[8]研究了給定故障概率下，目標(biāo)為設(shè)施失效后運(yùn)輸成本的期望值最小的選址模型。Berman等[9]分析了設(shè)施按照一定概率中斷后，顧客重新再在現(xiàn)存設(shè)施中尋求服務(wù)的選址模型。Cui等[10]放松了各設(shè)施失效概率相同的假設(shè), 以常規(guī)和應(yīng)急狀態(tài)下的運(yùn)輸成本之和最小為目標(biāo), 構(gòu)建了同時(shí)考慮可靠性和經(jīng)濟(jì)性的供應(yīng)網(wǎng)絡(luò)。Peng等[11]用事件可能發(fā)生的情景來描述設(shè)施的中斷概率。

為使測(cè)量點(diǎn)失效時(shí)QoE測(cè)量結(jié)果仍較為穩(wěn)定、精確，即各用戶的服務(wù)效果仍可以一定的概率被測(cè)量到，本文以最小化選取的測(cè)量點(diǎn)數(shù)為目標(biāo)，首先研究各測(cè)量點(diǎn)的失效概率已知時(shí)的QoE測(cè)量點(diǎn)選址問題，其次借鑒Bertsimas等[12]、Degel等[13]及Liu等[14]的思想用魯棒區(qū)間描述失效概率的不確定性，分別建立了相應(yīng)的規(guī)劃模型，并通過數(shù)學(xué)方法將其轉(zhuǎn)化為混合0-1整數(shù)規(guī)劃進(jìn)行求解。

1　失效概率已知的QoE測(cè)量點(diǎn)選址模型

QoE測(cè)量網(wǎng)用戶集E={e1,e2,…,en},ei(i=1,2,…,n)為需要測(cè)量服務(wù)的用戶組成的集合，S={S1,S2,…,Sm}為用來測(cè)試各用戶使用不同網(wǎng)站服務(wù)效果的備選的測(cè)量點(diǎn)集，Sj(j=1,2,…,m)為備選測(cè)量點(diǎn)。0-1測(cè)量矩陣A=(aij)n×m表示備選測(cè)量點(diǎn)對(duì)用戶的測(cè)量情況，若aij=1表示測(cè)量位置點(diǎn)Sj可以有效測(cè)量用戶ei獲得服務(wù)的質(zhì)量情況；反之若aij=0則認(rèn)為備選位置點(diǎn)Sj不能有效測(cè)量用戶ei獲得服務(wù)的質(zhì)量情況。

實(shí)際情況中，各測(cè)量點(diǎn)的外置探針通過模擬用戶使用網(wǎng)絡(luò)主動(dòng)測(cè)量網(wǎng)絡(luò)QoE時(shí)，由于其本身或其他一些外在原因，均存在失效的可能性。假設(shè)測(cè)量點(diǎn)能正常服務(wù)的概率為隨機(jī)變量，定義測(cè)量概率矩陣P=(pij)n×m，pij表示備選測(cè)量點(diǎn)Sj以概率pij能測(cè)試到用戶ei接受網(wǎng)站的服務(wù)效果，即aij以概率pij取值為1，其他為0，由于各備選測(cè)量點(diǎn)均存在失效的可能，pij取值區(qū)間為[0,1)，并且假設(shè)不同的備選點(diǎn)能測(cè)量到同一用戶ei的概率相互獨(dú)立。

隨機(jī)失效QoE測(cè)試節(jié)點(diǎn)選址模型可用如下的規(guī)劃來描述：

(1)

(2)

xj∈{0,1},j={1,2,…,m}，

(3)

式中，xj為0-1決策變量，xj=0表示備選點(diǎn)Sj未被選中，當(dāng)xj=1表示選取備選點(diǎn)Sj，目標(biāo)函數(shù)表示所求備選測(cè)量點(diǎn)個(gè)數(shù)最少，約束條件表示用戶ei能被測(cè)試到的概率不小于αi，即測(cè)量效果不低于αi。

由于xj∈{0,1}，易知(1-pijxj)=(1-pij)xj，于是約束條件可轉(zhuǎn)換為如下的線性約束

從而上述模型可改寫為

(4)

(5)

xj∈{0,1},j={1,2,…,m}。

(6)

故失效概率已知的QoE測(cè)量點(diǎn)選址問題轉(zhuǎn)化為一般的線性規(guī)劃問題，可用現(xiàn)有的數(shù)學(xué)軟件求解。

2　失效概率未知的QoE測(cè)量點(diǎn)選址模型

失效概率未知的QoE測(cè)量點(diǎn)選址模型的目標(biāo)仍是選擇盡可能少的備選測(cè)量點(diǎn)，使得各用戶在接受不同網(wǎng)站的服務(wù)時(shí)，服務(wù)效果能被測(cè)量到的概率即測(cè)量效果不小于αi∈(0,1)。

用如下規(guī)劃來描述魯棒隨機(jī)失效選址模型

(7)

(8)

xj∈{0,1},j={1,2,…,m}。

(9)

(10)

(11)

ξij+ηi≥(w′ij-wij)xj， ?i,?j，

(12)

ξij≥0,ηi≥0 ，i={1,2,…,n}，

(13)

xj∈{0,1},j={1,2,…,m}，

(14)

其中

(15)

(16)

3　模型求解與算例分析

3.1失效概率已知的選址模型

表1　α取不同值時(shí)所選取的備選位置點(diǎn)及個(gè)數(shù)

由表1可知，測(cè)量效果α取值較大時(shí)，即各用戶對(duì)測(cè)量效果要求較高時(shí)，選取的備選位置點(diǎn)相對(duì)于不考慮備選點(diǎn)失效選擇的位置點(diǎn)個(gè)數(shù)較多，如測(cè)量效果α取值0.9時(shí)，選取的備選位置點(diǎn)為S1,S2,S3,S4；而測(cè)量效果α取值0.8時(shí)，選取的備選位置點(diǎn)為S2,S3,S4，與不考慮備選位置點(diǎn)失效選擇的S1相差明顯。隨著測(cè)量效果α的減少，即各用戶對(duì)測(cè)量效果要求逐漸降低時(shí)，選取的備選位置點(diǎn)相對(duì)不考慮備選點(diǎn)失效選擇的位置點(diǎn)個(gè)數(shù)也逐漸減少。當(dāng)測(cè)量效果α取值0.6時(shí)，選取的備選位置點(diǎn)為S1,S3；當(dāng)測(cè)量效果α取值0.5時(shí)，選取的備選位置點(diǎn)為S1,S4；當(dāng)測(cè)量效果α取值0.4時(shí)，選取的備選位置點(diǎn)與不考慮備選點(diǎn)失效時(shí)相同均為S1?？梢缘弥?，考慮備選未知點(diǎn)失效并且測(cè)量效果取值較大時(shí)與不考慮備選位置點(diǎn)失效的選擇差異較大。實(shí)際中QoE測(cè)量網(wǎng)用戶數(shù)較多，為滿足各用戶的QoE測(cè)量效果，可選的備選位置點(diǎn)需要盡量多，考慮將用戶分為不同的類型(如按照居住地分類)，同一類型的用戶視為一個(gè)“用戶組”，使得種類數(shù)與備選位置點(diǎn)數(shù)較為相近。隨機(jī)生成“用戶組”數(shù)與備選位置點(diǎn)數(shù)均為40的網(wǎng)絡(luò)，當(dāng)不考慮測(cè)量點(diǎn)失效時(shí)，經(jīng)典的選址問題選擇測(cè)量點(diǎn){S12,S14,S37}，選取的點(diǎn)個(gè)數(shù)為3，在區(qū)間(0.8,1)上隨機(jī)生成測(cè)量概率矩陣P=(pij)n×m中元素pij。考慮測(cè)量點(diǎn)失效時(shí)，測(cè)量效果α取不同值時(shí)選取備選位置點(diǎn)及個(gè)數(shù)的結(jié)果見表2。

表2　α取不同值時(shí)所選取的備選位置點(diǎn)及個(gè)數(shù)

由表2可知，測(cè)量效果α要求較高(α≥0.90)時(shí)，隨著α增加，選取的位置點(diǎn)個(gè)數(shù)顯著增多；測(cè)量效果α取值0.9時(shí)，選取的備選位置點(diǎn)為S10,S23,S27,S34；而測(cè)量效果α增加至0.95時(shí)，選取的備選位置點(diǎn)為S14,S15,S23,S37；當(dāng)測(cè)量效果α繼續(xù)增加至0.96時(shí)，選取的備選位置點(diǎn)為S8,S10,S23,S25,S31，位置點(diǎn)個(gè)數(shù)增多；當(dāng)測(cè)量效果α為0.99接近1時(shí)，選取的備選位置點(diǎn)個(gè)數(shù)為最多6個(gè)。當(dāng)測(cè)量效果α較低時(shí)，選取的位置點(diǎn)不再變化，如測(cè)量效果α取值0.8時(shí)，選取的備選位置點(diǎn)個(gè)數(shù)為3，已達(dá)到不考慮失效情況時(shí)的最優(yōu)解。這表明隨著測(cè)量效果α的增加，測(cè)量點(diǎn)的選取個(gè)數(shù)對(duì)于測(cè)量點(diǎn)是否失效較為敏感。

3.2失效概率未知的魯棒選址模型

表3　α及Γi取不同值時(shí)選取的備選位置點(diǎn)

表3中第二列Γi取0為不考慮失效概率的不確定性選取的備選位置點(diǎn)，當(dāng)考慮失效概率不確定性時(shí)，隨著Γi的增加，選取的備選位置點(diǎn)不會(huì)減少，并且與不考慮備選位置點(diǎn)失效選擇的備選位置點(diǎn)不盡相同，如固定測(cè)量效果，隨著Γi的增加選取的位置點(diǎn)個(gè)數(shù)不會(huì)減少。當(dāng)測(cè)量效果α較高時(shí)，選點(diǎn)的個(gè)數(shù)對(duì)于Γi的變化十分敏感，如測(cè)量效果α為0.8時(shí)，不考慮備選位置點(diǎn)失效的選點(diǎn)個(gè)數(shù)與考慮Γi的選點(diǎn)個(gè)數(shù)有差異。

5　結(jié)語

QoE測(cè)量網(wǎng)選點(diǎn)問題考慮選擇盡可能少的測(cè)量點(diǎn)來準(zhǔn)確反映網(wǎng)絡(luò)中用戶獲取不同服務(wù)質(zhì)量的實(shí)際情況，考慮到網(wǎng)絡(luò)中備選位置點(diǎn)可能發(fā)生故障而不能夠正常測(cè)量到用戶接受服務(wù)的效果，本文采用魯棒優(yōu)化的方法，分別考慮了各測(cè)試點(diǎn)失效概率已知的QoE測(cè)量點(diǎn)選址問題，以及失效概率不確定的魯棒失效選址問題，用魯棒區(qū)間描述失效概率的不確定性，建立了相應(yīng)的數(shù)學(xué)模型并用數(shù)學(xué)方法將其轉(zhuǎn)化為確定性的0-1混合整數(shù)規(guī)劃問題。仿真案例結(jié)果表明,在QoE測(cè)量網(wǎng)選點(diǎn)問題中考慮備選位置的失效對(duì)測(cè)量點(diǎn)的部署方案效果有很大的影響?？紤]測(cè)量點(diǎn)失效的QoE測(cè)量網(wǎng)選點(diǎn)問題在布置測(cè)量點(diǎn)時(shí)，需在服務(wù)效果和選點(diǎn)個(gè)數(shù)之間作出權(quán)衡。然而，測(cè)試點(diǎn)失效大大增加了QoE測(cè)量網(wǎng)選點(diǎn)問題的難度，如何設(shè)計(jì)大規(guī)模的QoE測(cè)量網(wǎng)選點(diǎn)問題的高效求解算法是今后的研究方向。

參考文獻(xiàn)：

[1]JAINR.Qualityofexperience[J].IEEEMultimedia, 2004, 11(1): 96-97.

[2]紅葉. 基于移動(dòng)互聯(lián)網(wǎng)業(yè)務(wù)的QoE建模與分析[D].北京：北京郵電大學(xué), 2013.

[3]趙飛龍, 梅杓春,余輪. 移動(dòng)通信網(wǎng)的QoE測(cè)量及其量化方法[J]. 電子測(cè)量與儀器學(xué)報(bào), 2010, 24(3):230-236.

[4]王非, 徐渝, 李毅學(xué). 離散設(shè)施選址問題研究綜述[J]. 運(yùn)籌與管理, 2006, 15(5): 64-69.

[5]寧穎丹, 楊文國(guó),高隨祥. 服務(wù)網(wǎng)絡(luò)QoE測(cè)試節(jié)點(diǎn)魯棒選址問題研究[J]. 網(wǎng)絡(luò)新媒體技術(shù),2015, 4(6):1-6.

[6]CAISX,YANGWG,TANGYH.Approximatingsoft-capacitatedfacilitylocationproblemwithuncertainty[J].JournalofCombinatorialOptimization, 2014，28(2): 496-504.

[7]DREZNERZ.Heuristicsolutionmethodsfortwolocationproblemswithunreliablefacilities[J].JournalofOperationsResearchSociety,1987,38(6):509-514.

[8]SNYDERLV,DASKINMS.Reliabilitymodelsforfacilitylocation:Theexpectedfailurecostcase[J].TransportationScience,2005,39(3):400-416.

[9]BERMANO,KRASSD,MENEZESMBC.Facilityreliabilityissuesinnetworkp-medianproblem:Strategiccentralizationandco-locationeffects[J].OperationsResearch, 2007, 55(2): 332-350.

[10]CUITT,OUYANGYF,SHENZJM.Reliablefacilitylocationdesignundertheriskofdisruptions[J].OperationsResearch, 2010, 58(4): 998-1011.

[11]PENGP,SNYDERLV,LIMA,etal.Reliablelogisticsnetworksdesignwithfacilitydisruptions[J].TransportationResearchPartBMethodological, 2011, 45(8): 1190-1211.

[12]BERTSIMASD,SIMM.Thepriceofrobustness[J].OperationsResearch,2004,52(1):35-53.

[13]DEGELD,LUTTERP.ArobustformulationoftheuncertainSetcoveringproblem[EB/OL]. [2016-01-02].http://www.Optimization-online.org/DB_FILE/2013/06/3926.pdf.

[14]LIUPF,YANGWG,GUOTD.Adiscussionontheconservatismofrobustlinearoptimizationproblems[EB/OL].[2016-03-02].http://www.optimization-online.org/DB_FILE/2014/10/4598.pdf.

DOI:10.3976/j.issn.1002-4026.2016.04.016

收稿日期：2016-04-19

基金項(xiàng)目：國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃)(2011CB706900)；國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃)(2011AA01A102)；國(guó)家自然科學(xué)基金(11571015，11331012)；中國(guó)科學(xué)院戰(zhàn)略性先導(dǎo)科技專項(xiàng)(XDA06010302)；中國(guó)科學(xué)院大數(shù)據(jù)挖掘與知識(shí)管理重點(diǎn)實(shí)驗(yàn)室開放課題及華為技術(shù)有限公司資助

作者簡(jiǎn)介：寧穎丹(1993-)，女，碩士研究生，研究方向?yàn)轸敯魞?yōu)化。 *通信作者，楊文國(guó)。Email:yangwg@ucas.ac.cn

中圖分類號(hào)：O221

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1002-4026(2016)04-0080-07

Robust facility location issue of QoE test points with node failure

NING Ying-dan1,2, REN Qing-yuan3, GAO Sui-xiang1,2,DENG Hao-jiang4, YANG Wen-guo1,2*

(1. School of Mathematics, University of Chinese Academy of Sciences, Beijing 100049, China;2.Key Laboratory of Big Data Mining and Knowledge Management,Chinese Academy of Sciences, Beijing 100049, China;3. Shandong Vocational College of Industry, Zibo 256414, China;4. Institute of Acoustics, Chinese Academy of Sciences, Beijing 100190, China)

Abstract∶Facility location issue of QoE test points is to accurately reflect the obtained service of all network users with as less test points as possible. We established a robust model of QoE test points location with an interval to indicate the uncertainty of failure possibility based on QoE test points location model of given failure possibility. We then converted it to a mixed integer linear programming model.Test results show that the model is effective for QoE test points location issue with node failure. Case analysis demonstrates that coverage rate and failure number have different impact on location scheme.

Key words∶facility location;robust optimization;node failure;quality of experience