基于效用优化的P2P文件共享网络带宽公平分配算法

摘要

一种基于效用优化的P2P文件共享网络带宽公平分配算法，文件提供者为其每个文件请求者初始化下载速率，文件请求者的下载链路和文件提供者的上传链路各自初始化收取的价格；文件请求者根据为其提供文件下载服务的所有提供者分配的带宽计算得到调节因子；文件提供者根据文件请求者在当前时刻获得的下载速率、下载链路收取的价格、文件提供者的上传链路收取的价格，调整下一时刻其为文件请求者分配的下载速率；文件请求者的下载链路更新其下一时刻收取的价格，文件提供者的上传链路更新其下一时刻收取的价格；通过迭代得到近似优化问题的最优点不断逼近原优化问题的最优点。本发明具有带宽分配公平合理、算法准确有效、简单方便等优点。

说明书

技术领域

本发明涉及计算机网络技术领域，尤其涉及一种基于效用优化的P2P文件共享网 络带宽公平分配算法。

背景技术

近几年来，P2P文件共享应用成为P2P技术最广泛和最成功的应用之一，占据了 Internet网络的大部分流量。在传统的基于C/S模式的文件共享系统中，用户需要将分享的 文件先上传到中心服务器，其它需要获取文件的用户与中心服务器建立联系以下载该文 件。这种简单的方式使得互联网用户之间实现了文件共享，但文件资源的集中存储及频繁 的上传下载浪费了大量的服务器资源(带宽资源、计算资源及存储资源)，而且隐藏着单点 失效的可能性，中心服务器一出现问题，整个文件共享系统将不可使用。而在基于P2P技术 的文件共享网络中，用户无需将文件上传至中心服务器，文件存储在位于不同地理位置的 不同用户电脑中，而该用户可直接与其它用户进行分享，从提供文件共享的该用户电脑中 直接获得所需文件资源下载，这样不仅节约了服务器的带宽资源，而且提高了文件共享系 统的可靠性、鲁棒性、可扩展性。

P2P文件共享系统中，用户间通常都会建立多个并发连接同时下载或上传相同文 件的不同分片。这种方式提高了文件共享系统的文件传输效率，也在一定程度上提高了网 络带宽的利用率，但同时也对传统的拥塞控制机制和公平资源分配带来了挑战。传统的拥 塞控制的目标只在于让每个TCP连接友好，认为如果N个会话同时共享瓶颈链路，那么每个 会话应该分得链路传输能力的1/N。而在P2P文件共享系统中，某些自私用户(客户端)为了 加快文件下载速度，通过建立多个TCP连接从而增加连接数来抢占大量的带宽资源，造成了 网络带宽资源在用户之间分配的严重不公平性，也导致其它传统互联网应用的性能和服务 质量下降，同时也极大地增加了底层传输网络的负担。

因此，需要解决文件共享系统和传统互联网应用以及网络运营商之间的矛盾，保 证在不损害双方利益的前提下尽量达到双赢，实现网络带宽资源在用户之间的公平合理分 配，这也是保证网络快速健康发展的重要基础。本发明则从效用优化的角度分析了P2P文件 共享网络资源的最优分配，保障请求文件下载服务的用户获得一定满意度的同时，确保带 宽资源在用户之间公平有效分配，从而保证为用户提供所需同时具有一定质量保证的文件 下载服务。

发明内容

本发明目的在于提供一种以最优化用户满意度为目标、带宽分配公平合理、方法 简单有效的基于效用优化的P2P文件共享网络带宽公平分配算法。

为实现上述目的，采用了以下技术方案：

本发明算法主要包括P2P文件共享网络、文件请求者s以及文件提供者p，在P2P文 件共享网络中，对每个用户的接入链路进行定价，根据链路上的流量情况动态调整链路价 格，而文件提供者p在为文件请求者s提供文件下载服务时，根据文件请求者s当前的下载速 率和接入链路收取的价格，动态调整文件提供者p的上传带宽在文件请求者之间的公平分 配，最终实现所有文件提供者带宽的最优分配。

进一步的，所述带宽公平分配算法的步骤如下：

步骤1，P2P文件共享网络中，在t时刻，文件提供者p为每一个文件请求者s初始化 下载速率x_ps(t)，文件请求者s的下载链路初始化收取的价格λ_s(t)，文件提供者p的上传链 路初始化收取的价格μ_p(t)；

步骤2，如果此时x_ps(t)已经是原优化问题PP的最优点，那么得到文件请求者s的最 优带宽分配，则算法停止；否则向下进入步骤3；

步骤3，文件请求者s根据为其提供文件下载服务的所有提供者P(s)分配的带宽计 算得到调节因子ξ_ps(t)，ξ_ps(t)是使近似优化问题AP逼近原优化问题PP的调节因子；

步骤4，文件提供者p根据文件请求者s在t时刻获得的下载速率x_ps(t)、文件请求者 s的下载链路收取的价格λ_s(t)、文件提供者p的上传链路收取的价格μ_p(t)，调整t+1时刻为 文件请求者s分配的下载速率x_ps(t+1)；

步骤5，文件请求者s的下载链路更新t+1时刻收取的价格λ_s(t+1)；文件提供者p的 上传链路更新t+1时刻收取的价格μ_p(t+1)；

步骤6，若此时t+1时刻的下载速率x_ps(t+1)不是近似优化问题AP的最优点，则进入 步骤4重新计算；若此时t+1时刻的下载速率x_ps(t+1)是近似优化问题AP的最优点，则进入步 骤2，迭代直至得到原优化问题PP的最优点；

步骤7，当有新的文件提供者或文件请求者加入或者原有的文件提供者或文件请 求者退出，则上述迭代过程重新进行以达到新的最优点。

进一步的，在步骤2中，所述原优化问题PP为P2P文件共享网络带宽分配模型：

其中，$U\left(x_s\right)={\mathrm{ϵU}}_s\left(\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{ps}\right)+(1-ϵ)\underset{p:p\in P\left(s\right)}{\Sigma }{U}_s\left(x_{ps}\right),$向量x_s＝(x_1s,x_2s,...,x_ps)， x_ps是文件提供者p为文件请求者s提供的下载速率，U_s(·)是文件请求者s的效用函数，ε∈ [0,1]是耦合因子，是文件请求者s的下载链路带宽，是文件提供者p的上传链路带宽， S是文件请求者集合，P是文件提供者集合，P(s)是为文件请求者s∈S提供下载服务的文件 提供者集合；S(p)是文件提供者p∈P提供下载服务的所有文件请求者集合。

进一步的，在步骤3中，所述近似优化问题AP为P2P文件共享网络带宽分配模型PP 的近似等价模型：

其中$\hat{U}(x_s;{\xi }_s)=\underset{p:p\in P\left(s\right)}{\Sigma }\left({\mathrm{ϵ\xi }}_{ps}{U}_s\right(\frac{x_{ps}}{{\xi }_{ps}}\left)\right)+\left(1-ϵ\right)U_s\left(x_{ps}\right)),$向量x_s＝(x_1s,x_2s,...,x_ps)， x_ps是文件提供者p为文件请求者s提供的下载速率，U_s(·)是文件请求者s的效用函数，ε∈ [0,1]是耦合因子，ξ_ps是调节因子，是文件请求者s的下载链路带宽，是文件提供者p 的上传链路带宽，S是文件请求者集合，P是文件提供者集合，P(s)是为文件请求者s∈S提供 下载服务的文件提供者集合；S(p)是文件提供者p∈P提供下载服务的所有文件请求者集 合。

进一步的，在步骤3中，调节因子ξ_ps(t)的计算式如下：

${\xi }_{ps}\left(t\right)=\frac{x_{ps}\left(t\right)}{\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{ps}\left(t\right)}$

式中，p是文件提供者；s是文件请求者；P(s)是为s提供文件下载服务的所有文件 提供者集合；x_ps(t)是文件提供者p为文件请求者s分配的下载速率；ξ_ps(t)是使近似优化问 题AP逼近原优化问题PP的调节因子。

进一步的，在步骤4中，t+1时刻文件提供者p为文件请求者s分配下载速率x_ps(t+1) 的计算式如下；

$x_{ps}(t+1)=\left(x_{ps}\right(t)+{\mathrm{\kappa x}}_{ps}(t\left)\right(({\mathrm{ϵ\xi }}_{ps}^{\alpha }\left(t\right)+\left(1-ϵ\right))w_s{x}_{ps}^{-\alpha }\left(t\right)-{\lambda }_s\left(t\right)-{\mu }_p\left(t\right)){)}_{x_{ps}\left(t\right)}^{+}$

式中，x_ps(t)是t时刻文件提供者p为文件请求者s分配的下载速率；λ_s(t)是文件请 求者s的下载链路收取的价格；μ_p(t)是文件提供者p的上传链路收取的价格；w_s是文件请求 者s愿意支付的费用；ξ_ps(t)是使近似优化问题AP逼近原优化问题PP的调节因子；ε是效用优 化模型的耦合系数；κ是算法迭代步长，且κ>0；参数α>0是公平性指标，当α＝1时，实现用户 之间资源分配的比例公平性，当α＝2时，实现用户之间资源分配的调和平均公平性，当α→ ∞，则实现用户之间资源分配的最大最小公平性；

$x_{ps}(t+1)={\left(x_{ps}\right(t)+{\mathrm{\kappa x}}_{ps}(t\left)\right(\left({\mathrm{ϵ\xi }}_{ps}^{\alpha }\left(t\right)+\left(1-ϵ\right)\right)w_s{x}_{ps}^{-\alpha }\left(t\right)-{\lambda }_s\left(t\right)-{\mu }_p\left(t\right)\left)\right)}_{x_{ps}\left(t\right)}^{+}$意味着，

若x_ps(t)>0，则$x_{ps}(t+1)=x_{ps}\left(t\right)+{\mathrm{\kappa x}}_{ps}\left(t\right)\left(\right({\mathrm{ϵ\xi }}_{ps}^{\alpha }\left(t\right)+(1-ϵ)\left)w_s{x}_{ps}^{-\alpha }\right(t)-{\lambda }_s(t)-{\mu }_p(t\left)\right);$

若x_ps(t)＝0，则$x_{ps}(t+1)=\max \{0,x_{ps}\left(t\right)+{\mathrm{\kappa x}}_{ps}\left(t\right)\left(\right({\mathrm{\alpha \xi }}_{ps}^{\alpha }\left(t\right)+\left(1-ϵ\right)\left)w_s{x}_{ps}^{-\alpha }\right(t)-{\lambda }_s(t)-{\mu }_p(t\left)\right)\}.$

进一步的，在步骤5中，t+1时刻文件请求者s的下载链路收取的价格λ_s(t+1)利用 如下计算式进行更新：

${\lambda }_s(t+1)={\left({\lambda }_s\right(t)+\gamma \frac{y_s\left(t\right)-C_s^d}{C_s^d})}_{{\lambda }_s\left(t\right)}^{+},y_s\left(t\right)=\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{ps}\left(t\right)$

式中，p是文件提供者；s是文件请求者；P(s)是为s提供文件下载服务的所有文件 提供者集合；x_ps(t)是t时刻文件提供者p为文件请求者s分配的下载速率；λ_s(t)是文件请求 者s的下载链路在t时刻收取的价格；y_s(t)是文件请求者s在t时刻获得的总下载速率；是 文件请求者s的下载链路带宽；γ是算法迭代步长，且γ>0；

${\lambda }_s(t+1)={\left({\lambda }_s\right(t)+\gamma \frac{y_s\left(t\right)-C_s^d}{C_s^d})}_{{\lambda }_s\left(t\right)}^{+}$意味着，

若λ_s(t)>0，则${\lambda }_s(t+1)={\lambda }_s\left(t\right)+\gamma \frac{y_s\left(t\right)-C_s^d}{C_s^d};$

若λ_s(t)＝0，则${\lambda }_s(t+1)=max\{0,{\lambda }_s\left(t\right)+\gamma \frac{y_s\left(t\right)-C_s^d}{C_s^d}\}.$

进一步的，在步骤5中，t+1时刻文件提供者p的上传链路收取的价格μ_p(t+1)利用 如下计算式进行更新；

${\mu }_p(t+1)={\left({\mu }_p\right(t)+\gamma \frac{z_p\left(t\right)-C_p^u}{C_p^u})}_{{\mu }_p\left(t\right)}^{+},z_p\left(t\right)=\underset{s:s\in S\left(p\right)}{\Sigma }{x}_{ps}\left(t\right)$

式中，p是文件提供者；s是文件请求者；S(p)是接受文件提供者p提供文件下载服 务的文件请求者集合；μ_p(t)是t时刻文件提供者p的上传链路收取的价格；x_ps(t)是t时刻文 件提供者p为文件请求者s分配的下载速率；z_p(t)是文件提供者p的上传链路为文件请求者 分配的总上传速率；是文件提供者p的上传链路带宽；γ是算法迭代步长，且γ>0；

${\mu }_p(t+1)={\left({\mu }_p\right(t)+\gamma \frac{z_p\left(t\right)-C_p^u}{C_p^u})}_{{\mu }_p\left(t\right)}^{+}$意味着，

若μ_p(t)>0，则${\mu }_p(t+1)={\mu }_p\left(t\right)+\gamma \frac{z_p\left(t\right)-C_p^u}{C_p^u};$

若μ_p(t)＝0，则${\mu }_p(t+1)=max\{0,{\mu }_p\left(t\right)+\gamma \frac{z_p\left(t\right)-C_p^u}{C_p^u}\}.$

进一步的，算法由两层迭代组成，在步骤4和5构成的内循环中，算法迭代到达的最 优点就是带宽分配模型的近似优化问题AP的最优点；而在步骤2至6构成的外循环中，近似 优化问题AP的最优点不断逼近带宽分配模型的原优化问题PP的全局最优点，即P2P文件共 享网络中文件提供者为文件请求者分配的最优带宽。

与现有相关技术相比，本发明算法具有如下优点：将P2P文件共享网络中的带宽分 配问题归结为网络效用最优化问题，并针对文件请求者是否区分不同提供者分配的带宽， 考虑了两种不同形式的效用优化模型，利用耦合因子将两种形式结合起来，并将其转换为 等价的近似优化问题，提出的分布式带宽分配算法能够有效的收敛到带宽分配问题的最优 点，因此在保障网络中文件请求者满意度的同时，有效实现了网络带宽在文件请求者之间 的合理公平分配。

附图说明

图1是本发明算法的步骤流程图。

图2是本发明算法的5个用户网络拓扑结构图。

图3是图2中算法总共迭代次数与内循环次数的关系图。

图4是图2中文件请求者s1获得的最优带宽分配图。

图5是图2中文件请求者s2获得的最优带宽分配图。

图6是图2中文件请求者s3获得的最优带宽分配图。

图7是图2中各文件请求者的效用值及网络聚合效用值。

附图标号：p1是文件提供者1、p2是文件提供者2、s1是文件请求者1、s2是文件请求 者2、s3是文件请求者3。

具体实施方式

本发明根据对等网络中用户获取文件下载服务时的满意度选取效用函数，针对文 件请求者是否区分来自不同文件提供者的带宽，分别考虑了两种形式的效用优化模型，并 通过耦合因子将两种模型结合起来。本发明设计了一种分布式带宽分配算法，该算法能够 有效地收敛到效用优化模型的最优点，即网络用户的最优带宽分配。

带宽分配问题描述：

P2P文件共享网络中，各个用户通过接入链路连接到互联网，从其他用户处下载共 享文件。目前互联网的骨干部分采用了光纤等通信技术，传输速度较快，一般情况下不容易 发生大规模拥塞现象，此时用户端的接入链路就成了影响用户满意度的瓶颈，也就成为网 络资源分配与管理的关键所在。目前，很多用户接入互联网时采取的是上传链路和下载链 路相分离的情形，如非对称数字用户环路(AsymmetricalDigitalSubscriberLoop，简称 ADSL)，而一个用户在为其他用户提供文件下载服务时，该用户的上传带宽对其他网络用户 来讲就是资源，获得的带宽多少将直接影响到下载用户的满意度。

在P2P文件共享网络中，为了区分文件提供者和请求者，引入文件提供者集合P和 文件请求者集合S。只要一个用户p提供文件下载服务，那么该用户就属于P；只要一个用户s 请求文件下载服务，那么该用户就属于S。假设为文件请求者s∈S提供下载服务的文件提供 者集合为P(s)；同时，文件提供者p∈P提供下载服务的所有文件请求者集合为S(p)。注意到 p∈P(s)当且仅当s∈S(p)。

若文件提供者p为文件请求者s提供的下载速率为x_ps，则由于该用户s可以从多个 文件提供者处下载同一文件，因此文件请求者s获得的总下载速率为y_s＝∑_p:p∈P(s)x_ps，而且 不应超过该用户的下载链路带宽即同时，一个文件提供者p还可以同时为多 个请求者提供文件下载服务，因此该文件提供者p的上传速率为z_p＝∑_s:s∈S(p)x_ps，而且不应 超过该用户的上传链路带宽即$z_p\le C_p^u.$

用户效用函数：

文件请求者s在获得文件下载服务时，其满意度与获得的带宽分配有密切关系，获 得的带宽越大其满意度也就越高。用户在获取网络服务时的满意度可以用效用函数来描 述，为此选择下述效用函数，

其中，w_s是文件请求者s愿意支付的费用，是文件请求者s获得的带宽，而参数α ≥0描述了公平性指标。

若公平性参数α＝0，则网络资源分配问题的目标就是该目标就是最 大化网络吞吐量。

若公平性参数α＝1，则网络资源分配问题的目标就是该目标就 是实现用户之间资源分配的比例公平性。

若公平性参数α＝2，则网络资源分配问题的目标就是或该目标就是实现用户之间资源分配的调和平均公平性，也可以认为是最小化网络文件传输 时延。

若公平性参数α→∞，则网络资源分配问题的目标就是该目标就是实 现用户之间资源分配的最大最小公平性，其中m_s是文件请求者s需满足的最小带宽值。

带宽分配模型：

P2P文件共享网络的带宽分配模型有两种形式，不同之处在于这两种形式中，文件 请求者是否区分来自不同提供者的带宽，即文件请求者获得的满意度可以分别依赖于其每 个文件提供者分配的带宽值，也可以依赖于其从所有提供者处获得的带宽之和。

模型I：文件请求者的满意度依赖于其每个文件提供者分配的带宽，此时带宽分配 模型为

该模型也称为带宽分配的非耦合效用优化模型。

模型II：文件请求者的满意度仅依赖于其获得的带宽之和，此时带宽分配模型为

该模型也称为带宽分配的耦合效用优化模型。

考虑下列的一般效用函数

$U\left(x_s\right)={\mathrm{ϵU}}_s\left(\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{ps}\right)+(1-ϵ)\underset{p:p\in P\left(s\right)}{\Sigma }{U}_s\left(x_{ps}\right)$

其中向量x_s＝(x_1s,x_2s,...,x_ps)。这里，参数ε∈[0,1]称为耦合因子，将上述两种 形式模型联系起来，若ε偏大，则更注重耦合效用优化模型，反之，则更注重非耦合效用优化 模型。

此时，P2P文件共享网络带宽分配模型可以归结为如下优化问题，称为原优化问题 PP

利用非线性规划理论可以得到，该效用优化问题是凸优化问题。当0≤ε<1时，该问 题的目标函数U(x_s)对变量x_ps是严格的凹函数，存在全局最优解也就 是说，每个文件请求者获得的最优带宽分配是唯一的。

建立上述优化问题的拉格朗日函数

$\left(\begin{array}{c}L(x;\lambda ,\mu )=\underset{s:s\in S}{\Sigma }\left({\mathrm{ϵU}}_s\right(\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{ps})+(1-ϵ\left)\underset{p:p\in P\left(s\right)}{\Sigma }{U}_s\right(x_{ps}\left)\right)\\ +\underset{s:s\in S}{\Sigma }{\lambda }_s(C_s^d-\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{ps})+\underset{p:p\in P\left(s\right)}{\Sigma }{\mu }_p(C_p^u-\underset{s:s\in S\left(p\right)}{\Sigma }{x}_{ps})\end{array}\right)$

其中，λ_s≥0是文件请求者s的下载链路收取的单位带宽的价格，μ_p≥0是文件提供 者p的上传链路收取的单位带宽的价格。

为了对资源分配问题进行解耦，从而设计分布式资源分配算法，首先利用Jensen 不等式引入下列结论。

引理，对于任何向量ξ_s＝(ξ_1s,ξ_2s,...,ξ_ps)，其中ξ_ps>0且下列不等式 成立

$U_s\left(\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{ps}\right)\ge \underset{p:p\in P\left(s\right)}{\Sigma }{\xi }_{ps}{U}_s\left(\frac{x_{ps}}{{\xi }_{ps}}\right)$

其中等式当且仅当ξ_ps＝x_ps/∑_p:p∈P(s)x_ps时成立。

由该引理，对一般效用函数U(x_s)进行近似化处理，得到

$\hat{U}(x_s;{\xi }_s)=\underset{p:p\in P\left(s\right)}{\Sigma }\left({\mathrm{ϵ\xi }}_{ps}{U}_s\right(\frac{x_{ps}}{{\xi }_{ps}}\left)\right)+\left(1-ϵ\right)U_s\left(x_{ps}\right))$

此时，P2P文件共享网络中带宽分配模型PP可以近似为如下优化问题，称为近似优 化问题AP

该问题的拉格朗日函数为

$\left(\begin{array}{c}L(x;\lambda ,\mu )=\underset{s:s\in S}{\Sigma }\hat{U}(x_s;{\xi }_s)+\underset{s:s\in S}{\Sigma }{\lambda }_s(C_s^d-\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{ps})+\underset{p:p\in P}{\Sigma }{\mu }_p(C_p^u-\underset{s:s\in S\left(p\right)}{\Sigma }{x}_{ps})\\ =\underset{s:s\in S}{\Sigma }\underset{p:p\in P\left(s\right)}{\Sigma }\left({\mathrm{ϵ\xi }}_{ps}{U}_s\right(\frac{x_{ps}}{{\xi }_{ps}})+(1-ϵ\left)U_s\right(x_{ps})-{\lambda }_s{x}_{ps}-{\mu }_p{x}_{ps})+\underset{s:s\in S}{\Sigma }{\lambda }_s{C}_s^d++\underset{p:p\in P}{\Sigma }{\mu }_p{C}_p^u\end{array}\right)$

此时的拉格朗日函数对变量x_ps是分离的，可以得到针对变量x_ps的子梯度为

$▿L(x;\lambda ,\mu ){|}_{x_{ps}}={\mathrm{ϵ\xi }}_{ps}{U}_s^{\prime }\left(\frac{x_{ps}}{{\xi }_{ps}}\right)+(1-ϵ)U_s^{\prime }\left(x_{ps}\right)-{\lambda }_s-{\mu }_p=({\mathrm{ϵ\xi }}_{ps}^{\alpha }+(1-ϵ\left)\right)w_s{x}_{ps}^{-\alpha }-{\lambda }_s-{\mu }_p$

因此可以应用子梯度方法求解近似优化问题AP。实际上，由于具有参数ξ_s，因此 包含了U(x_s)的多个近似函数。当给定一个初始值ξ_s时，近似优化问题AP的解实际 上是原优化问题PP的一个子优化解。可以通过凸规划方法证明，通过本发明提出的算法不 断迭代ξ_s，近似优化问题AP的解将逐步逼近原优化问题PP的最优解。

本发明算法主要包括P2P文件共享网络、文件请求者s以及文件提供者p，其特征在 于：在P2P文件共享网络中，对每个用户的接入链路进行定价，根据链路上的流量情况动态 调整链路价格，而文件提供者p在为文件请求者s提供文件下载服务时，根据文件请求者s当 前的下载速率和接入链路收取的价格，动态调整文件提供者p的上传带宽在文件请求者之 间的公平分配，最终实现所有文件提供者带宽的最优分配。

其中，所述带宽公平分配算法的步骤如下：

步骤1，P2P文件共享网络中，在t时刻，文件提供者p为每一个文件请求者s初始化 下载速率x_ps(t)，文件请求者s的下载链路初始化收取的价格λ_s(t)，文件提供者p的上传链 路初始化收取的价格μ_p(t)；

步骤2，如果此时x_ps(t)已经是原优化问题PP的最优点，那么得到文件请求者s的最 优带宽分配，则算法停止；否则向下进入步骤3；

原优化问题PP为P2P文件共享网络带宽分配模型：

其中，$U\left(x_s\right)={\mathrm{ϵU}}_s\left(\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{ps}\right)+(1-ϵ)\underset{p:p\in P\left(s\right)}{\Sigma }{U}_s\left(x_{ps}\right),$向量x_s＝(x_1s,x_2s,...,x_ps)， x_ps是文件提供者p为文件请求者s提供的下载速率，U_s(·)是文件请求者s的效用函数，ε∈ [0,1]是耦合因子，是文件请求者s的下载链路带宽，是文件提供者p的上传链路带宽， S是文件请求者集合，P是文件提供者集合，P(s)是为文件请求者s∈S提供下载服务的文件 提供者集合；S(p)是文件提供者p∈P提供下载服务的所有文件请求者集合。

步骤3，文件请求者s根据为其提供文件下载服务的所有提供者P(s)分配的带宽计 算得到调节因子ξ_ps(t)，ξ_ps(t)是使近似优化问题AP逼近原优化问题PP的调节因子；

近似优化问题AP为P2P文件共享网络带宽分配模型PP的近似等价模型：

其中$\hat{U}(x_s;{\xi }_s)=\underset{p:p\in P\left(s\right)}{\Sigma }\left({\mathrm{ϵ\xi }}_{ps}{U}_s\right(\frac{x_{ps}}{{\xi }_{ps}}\left)\right)+\left(1-ϵ\right)U_s\left(x_{ps}\right)),$向量x_s＝(x_1s,x_2s,...,x_ps)， x_ps是文件提供者p为文件请求者s提供的下载速率，U_s(·)是文件请求者s的效用函数，ε∈ [0,1]是耦合因子，ξ_ps是调节因子，是文件请求者s的下载链路带宽，是文件提供者p 的上传链路带宽，S是文件请求者集合，P是文件提供者集合，P(s)是为文件请求者s∈S提供 下载服务的文件提供者集合；S(p)是文件提供者p∈P提供下载服务的所有文件请求者集 合。

调节因子ξ_ps(t)的计算式如下：

${\xi }_{ps}\left(t\right)=\frac{x_{ps}\left(t\right)}{\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{ps}\left(t\right)}$

式中，p是文件提供者；s是文件请求者；P(s)是为s提供文件下载服务的所有文件 提供者集合；x_ps(t)是文件提供者p为文件请求者s分配的下载速率；ξ_ps(t)是使近似优化问 题AP逼近原优化问题PP的调节因子。

步骤4，文件提供者p根据文件请求者s在t时刻获得的下载速率x_ps(t)、文件请求者 s的下载链路收取的价格λ_s(t)、文件提供者p的上传链路收取的价格μ_p(t)，调整t+1时刻为 文件请求者s分配的下载速率x_ps(t+1)；

t+1时刻文件提供者p为文件请求者s分配下载速率x_ps(t+1)的计算式如下；

$x_{ps}(t+1)=\left(x_{ps}\right(t)+{\mathrm{\kappa x}}_{ps}(t\left)\right(({\mathrm{ϵ\xi }}_{ps}^{\alpha }\left(t\right)+\left(1-ϵ\right))w_s{x}_{ps}^{-\alpha }\left(t\right)-{\lambda }_s\left(t\right)-{\mu }_p\left(t\right)){)}_{x_{ps}\left(t\right)}^{+}$

式中，x_ps(t)是t时刻文件提供者p为文件请求者s分配的下载速率；λ_s(t)是文件请 求者s的下载链路收取的价格；μ_p(t)是文件提供者p的上传链路收取的价格；w_s是文件请求 者s愿意支付的费用；ξ_ps(t)是使近似优化问题AP逼近原优化问题PP的调节因子；ε是效用优 化模型的耦合系数；κ是算法迭代步长，且κ>0；参数α>0是公平性指标，当α＝1时，实现用户 之间资源分配的比例公平性，当α＝2时，实现用户之间资源分配的调和平均公平性，当α→ ∞，则实现用户之间资源分配的最大最小公平性；

$x_{ps}(t+1)={\left(x_{ps}\right(t)+{\mathrm{\kappa x}}_{ps}(t\left)\right(\left({\mathrm{ϵ\xi }}_{ps}^{\alpha }\left(t\right)+\left(1-ϵ\right)\right)w_s{x}_{ps}^{-\alpha }\left(t\right)-{\lambda }_s\left(t\right)-{\mu }_p\left(t\right)\left)\right)}_{x_{ps}\left(t\right)}^{+}$意味着，

若x_ps(t)>0，则$x_{ps}(t+1)=x_{ps}\left(t\right)+{\mathrm{\kappa x}}_{ps}\left(t\right)\left(\right({\mathrm{ϵ\xi }}_{ps}^{\alpha }\left(t\right)+(1-ϵ)\left)w_s{x}_{ps}^{-\alpha }\right(t)-{\lambda }_s(t)-{\mu }_p(t\left)\right);$

若x_ps(t)＝0，则$x_{ps}(t+1)=\max \{0,x_{ps}\left(t\right)+{\mathrm{\kappa x}}_{ps}\left(t\right)\left(\right({\mathrm{\alpha \xi }}_{ps}^{\alpha }\left(t\right)+\left(1-ϵ\right)\left)w_s{x}_{ps}^{-\alpha }\right(t)-{\lambda }_s(t)-{\mu }_p(t\left)\right)\}.$

步骤5，文件请求者s的下载链路更新t+1时刻收取的价格λ_s(t+1)；文件提供者p的 上传链路更新t+1时刻收取的价格μ_p(t+1)；

t+1时刻文件请求者s的下载链路收取的价格λ_s(t+1)利用如下计算式进行更新：

${\lambda }_s(t+1)={\left({\lambda }_s\right(t)+\gamma \frac{y_s\left(t\right)-C_s^d}{C_s^d})}_{{\lambda }_s\left(t\right)}^{+},y_s\left(t\right)=\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{ps}\left(t\right)$

式中，p是文件提供者；s是文件请求者；P(s)是为s提供文件下载服务的所有文件 提供者集合；x_ps(t)是t时刻文件提供者p为文件请求者s分配的下载速率；λ_s(t)是文件请求 者s的下载链路在t时刻收取的价格；y_s(t)是文件请求者s在t时刻获得的总下载速率；是 文件请求者s的下载链路带宽；γ是算法迭代步长，且γ>0；

${\lambda }_s(t+1)={\left({\lambda }_s\right(t)+\gamma \frac{y_s\left(t\right)-C_s^d}{C_s^d})}_{{\lambda }_s\left(t\right)}^{+}$意味着，

若λ_s(t)>0，则${\lambda }_s(t+1)={\lambda }_s\left(t\right)+\gamma \frac{y_s\left(t\right)-C_s^d}{C_s^d};$

若λ_s(t)＝0，则${\lambda }_s(t+1)=max\{0,{\lambda }_s\left(t\right)+\gamma \frac{y_s\left(t\right)-C_s^d}{C_s^d}\}.$

t+1时刻文件提供者p的上传链路收取的价格μ_p(t+1)利用如下计算式进行更新；

${\mu }_p(t+1)={\left({\mu }_p\right(t)+\gamma \frac{z_p\left(t\right)-C_p^u}{C_p^u})}_{{\mu }_p\left(t\right)}^{+},z_p\left(t\right)=\underset{s:s\in S\left(p\right)}{\Sigma }{x}_{ps}\left(t\right)$

式中，p是文件提供者；s是文件请求者；S(p)是接受文件提供者p提供文件下载服 务的文件请求者集合；μ_p(t)是t时刻文件提供者p的上传链路收取的价格；x_ps(t)是t时刻文 件提供者p为文件请求者s分配的下载速率；z_p(t)是文件提供者p的上传链路为文件请求者 分配的总上传速率；是文件提供者p的上传链路带宽；γ是算法迭代步长，且γ>0；

${\mu }_p(t+1)={\left({\mu }_p\right(t)+\gamma \frac{z_p\left(t\right)-C_p^u}{C_p^u})}_{{\mu }_p\left(t\right)}^{+}$意味着，

若μ_p(t)>0，则${\mu }_p(t+1)={\mu }_p\left(t\right)+\gamma \frac{z_p\left(t\right)-C_p^u}{C_p^u};$

若μ_p(t)＝0，则${\mu }_p(t+1)=max\{0,{\mu }_p\left(t\right)+\gamma \frac{z_p\left(t\right)-C_p^u}{C_p^u}\}.$

步骤6，若此时t+1时刻的下载速率x_ps(t+1)不是近似优化问题AP的最优点，则进入 步骤4重新计算；若此时t+1时刻的下载速率x_ps(t+1)是近似优化问题AP的最优点，则进入步 骤2，迭代直至得到原优化问题PP的最优点；

步骤7，当有新的文件提供者或文件请求者加入或者原有的文件提供者或文件请 求者退出，则上述迭代过程重新进行以达到新的最优点。

上述算法由两层迭代组成，在步骤4和5构成的内循环中，算法迭代到达的最优点 就是带宽分配模型的近似优化问题AP的最优点；而在步骤2至6构成的外循环中，近似优化 问题AP的最优点不断逼近带宽分配模型的原优化问题PP的全局最优点，即P2P文件共享网 络中文件提供者为文件请求者分配的最优带宽。

收敛性分析：

收敛性是衡量算法性能的重要指标。本发明考虑了2个文件提供者p1和p2，3个文 件请求者s1、s2、s3的情形，如图2所示。其中，文件提供者的上传链路带宽为 文件请求者的下载链路带宽为本发明分析了文件提供者的上传带宽在文件请求者之间的比例公平分配(即α＝1)，各仿真 结果如图3、4、5、6、7所示。该算法实际上由两层迭代过程组成，如图3所示算法收敛的总迭 代次数与内循环迭代次数之间的关系，可以发现总共迭代次数与内循环次数基本上是呈线 性关系。在半耦合情形下(即ε＝0.5)，文件请求者得到的最优带宽分配如图4、5、6所示，其 中文件请求者1从文件提供者处得到的最优带宽分配为如图4所示。此时各个文件请求者得到的效用如图7所示。因此，算法能够在有限的迭代次数 内有效的收敛到效用优化模型的最优点，实现网络带宽在各个用户之间的合理分配。

以上所述的实施例仅仅是对本发明的优选实施方式进行描述，并非对本发明的范 围进行限定，在不脱离本发明设计精神的前提下，本领域普通技术人员对本发明的技术方 案做出的各种变形和改进，均应落入本发明权利要求书确定的保护范围内。