树状网络上代理服务器逆优化问题

树状网络上代理服务器逆优化问 对象存储 摘 要 通常的代理服务器选址问题是在一给定的网络上，如何合理地放置代理服务器，使得整个网络的最大时延最小或总花费最小。其实在实际中会很自然地碰到它的一类逆优化问题，就是当代理服务器已在给定的网络上放置好且不能移动时，如何改进网络(如增加网络带宽，提高服务器的负载能力、处理速度等)，使得改进后的网络运行更有效。本文研究在一个已放置了P个代理服务器的树状网络上，在预算可以变动的情况下，为了保证每个用户的利益，即到代理服务器的距离不超过某个正数 ，讨论带时延约束的最小费用逆优化问题，给出了一个多项式时间算法。 关键词 树状网络 代理服务器 逆优化 最小费用 0引言 随着互联网的迅速发展，许多用户受到访问响应缓慢的困扰。 在网络中有效地放置代理服务器可以达到减少用户访问延迟、均衡服务负载、降低网络带宽消耗的目的。 网络上代理服务器的放置问题是一类特殊的选址问题，与传统的选址问题不同，该问题具有方向性。在一般的网络图中代理服务器的最优放置问题是NP-难问题，但对于一些特殊的网络结构如线性结构和树状结构，该问题已有多项式时间算法。这些研究都是考虑在给定的网络上，如何合理地放置代理服务器，使得整个网络的最大时延最小或总花费最小。但在实际中可能碰到相逆的一类问题，就是当设施已经在给定的网络 上放置好且不能移动时，如何改进网络(如增加网络带宽，提高服务器的负载能力、处理速度等)，使得改进后的网络这些设施运行更有效。这类问题被称为逆优化问题。 本文研究在一个已放置了P个代理服务器的树状网络上，在预算可以改变的情况下，为了保证每个用户的利益，即到代理服务器的距离不超过某个正数，讨论带时延约束的最小费用问题。 1模型建立 令Ts=(V，E，P，1，w， )是一棵根节点为s的树，其中V为节点集合，|V|=n;E为边集合;P示代理服务器所在位置的节点的集合 (P V，|P|=p，);pv表示用户节点v 到根节点s(源服务器)的路径上遇到的第一个代理服务器(pv?P?{s});对于任意边e=(i，j)?E， 1ij表示每条边当前的长度(时延);wij表示减少每单位边长的费用; 表示长度(时延约束)。问题:如何减少边的长度(时延)，使得总花费最小，并且保证在改进后的网络中各用户节点到代理服务器的最大距离不超过 。这里的所谓减少边长在实际中可以用很多方式实现，如增加网络带宽，提高服务器的负载能力、处理速度等。这个代理服务器逆优化问题可用线性描述如下: (P)min?(i，j)?Ewijxij s.t. 0?xij?ij，(i，j)?E， (1) d(v，pv)? ， v?V 其中xij表示边e=(i，j)?E减少的长度;d(v，pv)表示在修改后的网络中用户节点v到离它最近的代理服务器的距离(时延)。 2模型求解 定理1:问题(P)在O(n2logn)多项式时间内可解。 证明:(1)我们首先把Ts=(V，E)分解成p棵以各代理服务器所在的节点为根的互不相交的子树T，v?P(可以只 有一个节点)。那么问题(P)就等价的转化为p个子问题(P')的和(P*)。 (P') minwijxij s.t. 0?xij?ij，(i，j)?Tv， (2) d(u，v)? ，u?TV，v?P (P') minwijxij s.t. 0?xij?ij，(i，j)?Tv，v?P， (3) d(u，v)? ，u?TV，v?P 如果每个子问题(P')有最优解，那么问题(P*)的解就是问题(P)的最优解。因为每一部分都是最小的那么和自然也是最小的。 (2)其实问题(P')就是树图上RLP的变形问题(Q1)。问题(Q1)有一强多项式时间算法，其复杂度为O(n2longn)。 在最好情况下，每棵子树Tv，v?P的规模相当，不妨令|Tv| =n/p，则问题(P*)在p?(n/p)2?log(n/p)=n2/p(longn logp)=O(n2logn)时间内可解。 在最坏情况下，算法的复杂度显然为O(n2logn)。 所以问题(P)在O(n2logn)多项式时间内可解。 Algorithm (p) Step1:把TS分解成p棵子树Tv，v?P; Step2:在每棵子树Tv上解问题(Q1); Step3:给出(P*)的解。 3 结语 本文讨论的是在预算可变的情况下，使用户到代理服务器的最大距离不超过某个正数的最小费用问题。现今网络中代理服务器逆优化问题会有很大的研究空间和实际应用。 对象存储