考慮節點失效的QoE測量點魯棒選址問題研究

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

(1.中國科學院大學數學科學學院，北京 100049; 2.中國科學院大數據挖掘與知識管理重點實驗室,北京 100049;3.山東工業職業學院,山東 淄博 256414;　4.中國科學院聲學研究所,北京 100190)

?

考慮節點失效的QoE測量點魯棒選址問題研究

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

(1.中國科學院大學數學科學學院，北京 100049; 2.中國科學院大數據挖掘與知識管理重點實驗室,北京 100049;3.山東工業職業學院,山東 淄博 256414;4.中國科學院聲學研究所,北京 100190)

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

關鍵詞：設施選址；魯棒優化；節點失效；QoE

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

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

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

為使測量點失效時QoE測量結果仍較為穩定、精確，即各用戶的服務效果仍可以一定的概率被測量到，本文以最小化選取的測量點數為目標，首先研究各測量點的失效概率已知時的QoE測量點選址問題，其次借鑒Bertsimas等[12]、Degel等[13]及Liu等[14]的思想用魯棒區間描述失效概率的不確定性，分別建立了相應的規劃模型，并通過數學方法將其轉化為混合0-1整數規劃進行求解。

1　失效概率已知的QoE測量點選址模型

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

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

隨機失效QoE測試節點選址模型可用如下的規劃來描述：

(1)

(2)

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

(3)

式中，xj為0-1決策變量，xj=0表示備選點Sj未被選中，當xj=1表示選取備選點Sj，目標函數表示所求備選測量點個數最少，約束條件表示用戶ei能被測試到的概率不小于αi，即測量效果不低于αi。

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

從而上述模型可改寫為

(4)

(5)

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

(6)

故失效概率已知的QoE測量點選址問題轉化為一般的線性規劃問題，可用現有的數學軟件求解。

2　失效概率未知的QoE測量點選址模型

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

用如下規劃來描述魯棒隨機失效選址模型

(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　α取不同值時所選取的備選位置點及個數

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

表2　α取不同值時所選取的備選位置點及個數

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

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

表3　α及Γi取不同值時選取的備選位置點

表3中第二列Γi取0為不考慮失效概率的不確定性選取的備選位置點，當考慮失效概率不確定性時，隨著Γi的增加，選取的備選位置點不會減少，并且與不考慮備選位置點失效選擇的備選位置點不盡相同，如固定測量效果，隨著Γi的增加選取的位置點個數不會減少。當測量效果α較高時，選點的個數對于Γi的變化十分敏感，如測量效果α為0.8時，不考慮備選位置點失效的選點個數與考慮Γi的選點個數有差異。

5　結語

QoE測量網選點問題考慮選擇盡可能少的測量點來準確反映網絡中用戶獲取不同服務質量的實際情況，考慮到網絡中備選位置點可能發生故障而不能夠正常測量到用戶接受服務的效果，本文采用魯棒優化的方法，分別考慮了各測試點失效概率已知的QoE測量點選址問題，以及失效概率不確定的魯棒失效選址問題，用魯棒區間描述失效概率的不確定性，建立了相應的數學模型并用數學方法將其轉化為確定性的0-1混合整數規劃問題。仿真案例結果表明,在QoE測量網選點問題中考慮備選位置的失效對測量點的部署方案效果有很大的影響。考慮測量點失效的QoE測量網選點問題在布置測量點時，需在服務效果和選點個數之間作出權衡。然而，測試點失效大大增加了QoE測量網選點問題的難度，如何設計大規模的QoE測量網選點問題的高效求解算法是今后的研究方向。

參考文獻：

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

[2]紅葉. 基于移動互聯網業務的QoE建模與分析[D].北京：北京郵電大學, 2013.

[3]趙飛龍, 梅杓春,余輪. 移動通信網的QoE測量及其量化方法[J]. 電子測量與儀器學報, 2010, 24(3):230-236.

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

[5]寧穎丹, 楊文國,高隨祥. 服務網絡QoE測試節點魯棒選址問題研究[J]. 網絡新媒體技術,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

基金項目：國家重點基礎研究發展計劃(973計劃)(2011CB706900)；國家高技術研究發展計劃(863計劃)(2011AA01A102)；國家自然科學基金(11571015，11331012)；中國科學院戰略性先導科技專項(XDA06010302)；中國科學院大數據挖掘與知識管理重點實驗室開放課題及華為技術有限公司資助

作者簡介：寧穎丹(1993-)，女，碩士研究生，研究方向為魯棒優化。 *通信作者，楊文國。Email:yangwg@ucas.ac.cn

中圖分類號：O221

文獻標識碼：A

文章編號：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