服务网络QoE测试节点鲁棒选址问题研究  

Robust Facility Location Problem of Test Points in Service Networks for Measuring QoE

作　　者：宁颖丹 杨文国[1,2] 高随祥[1,2] 

机构地区：[1]中国科学院大学数学科学学院,北京100049 [2]中国科学院大数据挖掘与知识管理重点实验室,北京100190

出　　处：《网络新媒体技术》2015年第6期1-6,共6页Network New Media Technology

基　　金：国家重点基础研究发展计划(973)项目(2011CB706900);国家高技术研究发展计划(863)项目(2011AA01A102);国家自然科学基金(11331012;71171189);中国科学院战略性先导科技专项(XDA06010302);中国科学院大数据挖掘与知识管理重点实验室开放课题资助;华为技术有限公司的资助

摘　　要：QoE测量网选点问题是指在服务网络中部署少量点模拟用户来测试不同网站的服务效果,选择尽可能少的点代表用户,同时又能准确反映网络中用户获取不同服务的质量情况。选址问题通常是NP难问题,影响覆盖的不确定因素大大增加了QoE测量网选点的难度。建立了QoE测量网选点问题的鲁棒选址集覆盖模型,设计了以最小化选取测试点为目标,求解鲁棒集覆盖问题的贪婪算法。算法对备选点集的元素进行处理,再应用贪婪步骤求解。仿真案例的测试结果表明:所提出的鲁棒选址集覆盖模型和贪婪算法对解决QoE测量网选点问题的可行性和有效性。Test points selecting in service networks for measuring QoE is to select as few points as possible to test the QoE of different websites and reflect the qualities of all users＇ different services under different scenarios. This is a special kind of location problem,which belongs to NP hard. And the uncertainty factors in Test points selecting in service networks for measuring QoE increase the difficulty dramatically. To solve this problem,a robust set covering facility location model is established based on different coverage scenarios. The minimum number of test points to cover all users could be obtained by a heuristic algorithm based on the greedy procedure.The main idea of the algorithm is that process the elements in the sets of points before applying greedy procedure and remove unnecessary sets in last step. Experimental results demonstrate that both robust set covering facility location model and the algorithm proposed in this paper are efficient for solving the problem.

关 键 词：设施选址 集覆盖 鲁棒优化 贪婪算法 

分 类 号：TP393.09[自动化与计算机技术—计算机应用技术]