论文部分内容阅读
用户体验质量(Quality of Experience,QoE)测量网选址问题是指在服务网络中部署少量点模拟用户来测量不同网站的服务效果,要求选择尽可能少的点代表用户,同时又能准确反映网络中用户获取不同服务的质量情况。选址问题通常是NP难问题,影响测量网选址的不确定因素大大增加了QoE测量网选址的难度。鲁棒优化是近二十年来发展的处理不确定问题的方法,应用鲁棒优化方法建模求解实际问题由于考虑了不确定性的影响,所得的最优方案通常具有良好的稳健性。本文用鲁棒优化方法来研究考虑不确定性因素的QoE测量网选址问题,提出了分别考虑测量范围不确定、节点失效以及费用未知的QoE测量网鲁棒选址模型,设计相应求解算法并给出算例分析和模拟结果。 首先,提出了QoE测量网选址问题。用离散情景刻画各测量点测量范围的不确定性,建立了离散鲁棒选址模型,设计了以最小化选取测量点为目标的贪心算法。算法首先对备选点集的元素进行处理,再应用贪心步骤求解。仿真案例的测试结果表明所提离散鲁棒选址模型和贪心算法对解决QoE测量网选址问题的可行性和有效性。 其次,研究了节点失效的QoE测量网鲁棒选址问题。在实际监测过程中测量点可能发生故障而影响正常测量,由于失效概率不能准确给出,大大增加了获取服务质量情况的难度;在建立基于失效概率已知的QoE测量网选址模型的基础上,用区间描述失效概率的不确定性,建立了失效概率未知的QoE测量网鲁棒选址模型,利用Degel-Lutter方法将其转化为混合整数线性规划进行求解。测试结果表明了鲁棒选址模型对考虑节点失效的QoE测量网选址问题的有效性,并分析了测量效果和失效个数对选址方案的影响。 最后,研究了费用未知的QoE测量网选址问题。各测量点的选取需要一定的费用,用随机变量表示选址费用,在精确分布信息未知的条件下,利用低阶矩信息来刻画费用的不确定性,建立了QoE测量网选址问题最小最大准则下的分布式鲁棒模型,应用锥对偶理论,提出了把分布式鲁棒模型转化为半定规划的求解方法;并给出了仿真结果。