基于两类服务台批量服务、异步休假排队的P2P网络性能分析

Performance Analysis of P2P Networks Based on Two Types of Servers Bulk Service and Asynchronous Vacation Queueing Model

摘要: 为了对P2P网络性能进行分析，解决P2P网络系统能耗过大的问题，本文将P2P网络中发出资源请求的节点抽象成顾客，提供服务的节点抽象成服务台，在经典排队模型的基础上引入两类服务台批量服务、异步休假策略建立服务台数变化的M/Md/c+k(0≤k≤d)排队模型。利用矩阵几何解方法求解出系统的稳态分布，进而推导出系统平均队长、平均等待时间等性能指标，并分析了系统不同状态下的能耗问题，提出纳什均衡和社会最优策略，为改善P2P网络能耗大的问题寻找合适参数。

Abstract: In order to analyze the performance of P2P networks and solve the problem of excessive energy consumption of P2P network system. In this paper, the peers that resource requests in a P2P net-work are abstracted into customers and the peers that provide services are abstracted into servers. Based on the classical queueing model, two types of servers bulk service and asynchronous vacation strategies are introduced to establish the M/Md/c+k(0≤k≤d) queueing model. The steady-state distribution of the system is solved by using the matrix-geometric solution method, and then the performance indicators such as the average queue length and the average waiting time of the system are derived. This paper also focuses on the energy consumption of the system in different periods, and puts forward the Nash equilibrium and the social optimal strategy to find appropriate parameters to improve the problem of high energy consumption in P2P networks.

1. 引言

P2P网络和传统C/S结构不同，P2P网络不需要中间的服务器，网络提供节点间实时的数据传输，每个节点的地位是相等的。在P2P结构中，每个节点都同时具有信息消费者，信息提供者等方面的功能，同时相比于传统模式中单服务器故障或者使用率偏高导致的系统瘫痪问题，P2P网络更加可靠。随着P2P网络的广泛使用，其能耗问题成为了热点问题，因此本文对改善P2P网络的性能，降低其能耗方面进行了研究。Qin等 [1] 提出了一种移动边缘辅助计算，以提高移动P2P通信中未压缩数据的吞吐量，定义了能耗和延迟时间之间的费用函数，通过最小化实际约束条件下的费用函数得到了一个闭式解。张修如等 [2] 设计了基于P2P网络和C/S的混合流媒体系统三层结构，给出了一个具有最小缓冲延迟的动态数据分配算法。Hales [3] 提出了一种基于测量的分布式方法来降低非结构化P2P网络中的搭便车行为，提出的方案要求每个对等点监控其相邻对等点，或采取明确的激励机制抑制节点的自私行为。Guo [4] 针对P2P网络中的虚假服务和搭便车问题，围绕社会网络的信任模型提出了一个基于矢量空间的分布式信任模型。模型使用了时间敏感因素来检测节点行为的敏感性，并基于向量空间模型的推荐信任来防止节点之间串通和恶意诽谤。

在排队论中休假排队系统是一个重要的研究热点，各种休假策略的引入使得排队模型的应用更加方便。Jain等 [5] 考虑了多服务台机器修复问题的异步休假策略，该问题包括服务台故障和两种类型的备件。采用矩阵几何解方法得到队列大小分布，确定了各种性能指标，如空闲服务台、繁忙服务台和休假服务台的预期数量。Wang等 [6] 针对完全可观察、几乎可观察、几乎不可观察、完全不可观察的排队，加入了异步休假和同步休假策略。从社会福利的角度分析了顾客的均衡策略，得出了交通密度低时，异步休假的均衡社会福利要高于同步休假均衡社会福利的结论。

批量服务排队在现实中有着广泛的实际意义，为了分析这一复杂的排队问题，在经典排队模型的基础上引入了批量服务策略。张宏波等 [7] 对一类批量服务工作休假排队进行了分析，讨论了批量服务的M/M/1多重或单重工作休假排队，对该排队模型用GI/M/1型Markov过程建模，通过求解该过程的联合平稳分布，得到了排队系统服务台平稳状态的详细刻画以及平稳队长分布的随机分解结果。Lee [8] 讨论了服务可变的离散时间批量到达、批量服务的排队模型，利用补充变量法和生成函数，获得了服务完成时的队列分布。Banerjee等 [9] 对具有一般批量服务的单服务器的排队模型进行了分析，根据嵌入式马尔可夫链的方法研究了模型的稳态分布，获得了排队顾客数、服务数和到达过程的联合分布，并通过数值例子对所研究的排队模型进行了定性分析。Germs等 [10] 提出了一个统一的方法来研究一类有限缓冲区且状态相关的批量排队系统的性能，推导出了计算队长极限概率分布的数值平稳步骤，提出了评价批量服务性能的度量指标。

为了更好的研究P2P网络的性能，已有部分研究者将排队论理论应用到P2P网络。Ghimire等 [11] 基于不同结构化的P2P覆盖网络，提供了一个分析模型。将系统建立为排队模型，获得了会话设置延迟和容量的封闭表达式，并通过数值仿真验证了分析方法的可靠性，找到了最小会话设置的最佳超级节点数。Ferragut等 [12] 从排队论的角度分析了P2P网络文件交换群的动态，将P2P网络抽象为M/G/1和M/G/∞的排队模型，得到了下载配置文件的中心极限定理的结果，最后将固定种子数扩展到了种子数量缓慢变化的情况。Gray等 [13] 将排队论的基本理论知识与P2P网络模型相结合，得到了固定队长的期望值和忙周期分布的表达式，确定了等待时间平稳分布的显式表达式。

据了解没有文献通过建立多服务台批量服务、异步休假的排队模型对P2P网络系统能耗问题进行分析。本文将服务器进行更新、维修、保养等不进行资源传输过程或多路复用程序不进行此特定资源输出，转为对其它数据进行处理等情况看作休假机制。将混合P2P网络一个簇中请求节点到达过程抽象成顾客到达，服务节点的资源信息传输过程抽象成服务过程，节点结束文件下载抽象成顾客服务完成，建立两类服务台、异步单重休假、批量服务策略下的M/M^d/ $c+k$ ( $0\le k\le d$ )排队系统，利用矩阵几何解方法和GI/M/1型结构矩阵研究系统的稳态分布并分析混合P2P网络中的排队问题，得到系统的重要性能指标。通过数值分析研究系统能耗随系统参数的变化趋势，并寻找系统的最优参数。

2. 混合P2P网络与建模

混合P2P网络由不同的簇组成，每个簇相当于一个对等点，每个簇中包含一个超级节点和多个普通节点，构成一个星型结构。P2P网络中节点既可以作为“消费者”向其它节点提出资源传输请求，也可以作为“服务者”为其它节点提供服务。将混合P2P系统一个簇建模为两类服务台批量服务和异步单重休假的排队模型，将资源请求的节点看作需要接受服务的顾客，将簇中原有的c个普通节点看作c个I类服务台，将服务结束返回簇为其他节点提供服务的请求节点看作II类服务台。请求节点的到达间隔、两类服务节点的服务时间、II类节点的休假时间分别是独立的指数分布随机变量，假设等待空间是无穷大的。假定该模型为等待制排队，请求节点进入系统后排队等待，服务节点以先到先服务的规则进行服务。P2P网络运行机制如图1。

Figure 1. P2P network operation mechanism diagram

图1. P2P网络运行机制图

1) 假设请求节点的到达间隔服从参数为 $\lambda$ 的指数分布，两类服务节点均可批量服务，I类服务节点的服务时间服从参数为 ${\mu }_1$ 的指数分布，II类服务节点的服务时间服从参数为 ${\mu }_2$ 的指数分布。I类服务节点可进行休假，II类服务节点不休假。当d (d是大于1的固定常数)个请求节点进入系统接受服务时，如果系统中既有空闲的I类服务节点又有空闲的II类服务节点，I类服务节点优先为请求节点服务。

2) 本模型主要是以数量触发的批量服务，即排队等待的请求节点数中至少达到d个才可进行服务，一个服务节点可一次服务d个请求节点，其中d个请求节点同时接受服务，同时被服务完毕。当等待的请求节点达到d个时，簇中原有的I类服务节点为d个请求节点服务。服务结束后，每个请求节点以概率 $\gamma$ 返回簇，作为II类服务节点为其他请求节点服务，或以概率 $\bar{\gamma }=\left(1-\gamma \right)$ 离开系统，一个簇中最多可容纳d个请求节点返回系统作为II类服务节点。

3) 每个I类服务台可单独的开始和结束休假状态，且只能进行一次休假，最大限度的利用空闲服务台提高经济效益，即异步单重休假策略。当d个请求节点服务结束后，如果是I类服务节点提供的服务，若排队等待的节点数大于等于d，则该节点继续为队首的d个请求节点服务，若排队等待的请求节点数小于d时，则该服务节点进入随机长度为V休假期，休假长度服从参数为 $\theta \left(\theta \ge 0\right)$ 的指数分布。I类服务节点休假结束后，若排队等待的请求节点数大于等于d，该I类服务节点立即为队首的d个请求节点服务，若排队等待的节点数小于d，则该服务节点进入空闲期，直到等待的请求节点数达到d个，该服务节点结束闲期进入工作期立即为这d个请求节点服务，重复上面的过程。因此每个I类服务节点在一个忙循环内可处工作、空闲和休假三种状态之一。

3. 模型分析

3.1. 状态转移率矩阵

假设 $L\left(t\right)$ 表示时刻 t 系统中请求节点的数量， $J\left(t\right)$ 表示时刻 t 系统中处于工作期和闲期的I类服务节点数， $H\left(t\right)$ 表示时刻 t系统中II类服务节点数。则 $\left\{\left(L\left(t\right),J\left(t\right),H\left(t\right)\right),t\ge 0\right\}$ 是以 $\Omega$ 为状态空间的三维Markov过程，其中状态空间 $\Omega$ 为

$\Omega =\left\{\left(i,j,h\right),i\ge 0,0\le j\le c,0\le h\le d\right\}$

其中， $\left(i,0,0\right),\left(i,0,1\right),\cdots ,\left(i,0,d\right),\cdots ,\left(i,c,0\right),\left(i,c,1\right),\cdots ,\left(i,c,d\right)$ ，表示水平i， $i\ge 0$ 。同时，每个状态所表示的含义如下：

$J\left(t\right)=0$ 表示有0个I类服务节点处于工作期或闲期，即所有的I类服务节点都处于休假期。

$J\left(t\right)=j$ ( $1\le j\le c$ )表示有j个I类服务节点处于工作期或闲期，即 $\left(c-j\right)$ 个I类服务节点处于休假期。

当 $i\ge 0$ ， $j=0$ ， $0\le h\le d$ 时，状态 $\left(i,0,h\right)$ 表示系统中请求节点的个数为i，I类服务节点全部处于休假期，接受完服务返回系统成为II类服务节点的个数为h。

当 $0\le i\le jd$ ， $0<j\le c$ ， $0\le h\le d$ 时，状态 $\left(i,j,h\right)$ 表示系统中请求节点的个数为i，有 $\left[i/d\right]$ (其中 $[·]$ 符号表示取整)个I类服务节点处于工作期， $\left(j-\left[i/d\right]\right)$ 个I类服务节点处于闲期， $\left(c-j\right)$ 个I类服务节点

处于休假期，接受完服务返回系统成为II类服务节点的个数为h。

当 $i>jd$ ， $0<j\le c$ ， $0\le h\le d$ 时，状态 $\left(i,j,h\right)$ 表示系统中请求节点数为i，j个I类服务节点处于工作期，0个I类服务节点处于闲期， $\left(c-j\right)$ 个I类服务节点处于休假期，接受完服务返回系统成为II

类服务节点的个数为h。

将状态按字典序进行排列，系统的状态转移率矩阵表示如下

$Q=\left[\begin{array}{cccccccccccccccc}{A}_0& C& & & & & & & & & & & & & & \\ ⋮& \ddots & \ddots & & & & & & & & & & & & & \\ 0& \cdots & A_0& C& & & & & & & & & & & & \\ B_1& 0& \cdots & A_1& C& & & & & & & & & & & \\ & \ddots & \ddots & & \ddots & \ddots & & & & & & & & & & \\ & & B_1& 0& \cdots & A_1& C& & & & & & & & & \\ & & & B_2& 0& \cdots & A_2& C& & & & & & & & \\ & & & & \ddots & \ddots & & \ddots & \ddots & & & & & & & \\ & & & & & B_2& 0& \cdots & A_2& C& & & & & & \\ & & & & & & \ddots & \ddots & & \ddots & \ddots & & & & & \\ & & & & & & & B_{d+c}& 0& \cdots & A_{d+c}& C& & & & \\ & & & & & & & & \ddots & \ddots & & \ddots & \ddots & & & \\ & & & & & & & & & B_{d+c}& 0& \cdots & A_{d+c}& C& & \\ & & & & & & & & & & B& 0& \cdots & A& C& \\ & & & & & & & & & & & \ddots & \ddots & \cdots & \ddots & \ddots \end{array}\right]$

其中， $B_1,B_2,\cdots ,B_{d+c},B$ ， $A_0,A_1,A_2,\cdots ,A_{d+c},A$ ， $C$ 分别表示水平间的状态转移率矩阵，且均为 $\left(c+1\right)\left(d+1\right)$ 维方阵。定义 $f_i=\left(\begin{array}{l}d\\ i\end{array}\right){\gamma }^i\cdot {\left(1-\gamma \right)}^{d-i}$ ， $1\le i\le d$ ， $I$ 为 $d+1$ 维单位矩阵，矩阵 $Q$ 的分块矩阵具体表示如下

(1)

$B_k=\left[\begin{array}{cccc}{b}_1^{\left(k\right)}& & & \\ B_1^{\left(k\right)}& b_2^{\left(k\right)}& & \\ & \ddots & \ddots & \\ & & B_c^{\left(k\right)}& b_{c+1}^{\left(k\right)}\end{array}\right]$ , $1\le k\le d+c$ ,

其中

a)

$b_1^{\left(k\right)}=\left[\begin{array}{ccccc}0& 0& \cdots & 0& 0\\ & {\alpha }_1^{\left(k\right)}{\bar{\gamma }}^d& {\alpha }_1^{\left(k\right)}{f}_1& \cdots & {\alpha }_1^{\left(k\right)}{f}_{d-1}\\ & & \ddots & \ddots & ⋮\\ & & & {\alpha }_{d-1}^{\left(k\right)}{\bar{\gamma }}^d& {\alpha }_{d-1}^{\left(k\right)}{f}_1\\ & & & & {\alpha }_d^{\left(k\right)}{\bar{\gamma }}^d\end{array}\right]$ , $1\le k\le d+c$ ,

${\alpha }_i^{(k)}=\{\begin{array}{ccc}i{\mu }_2,& 1\le k\le d,& 1\le i\le k,\\ k{\mu }_2,& 1\le k\le d,& k<i\le d,\\ i{\mu }_2,& d<k\le d+c,& 1\le i\le d.\end{array}$

(i) 当 $1\le k\le c+1$ ，

$b_y^{\left(k\right)}=\left[\begin{array}{ccccc}{\beta }_{y,0}^{\left(k\right)}{\bar{\gamma }}^d& {\beta }_{y,0}^{\left(k\right)}{f}_1& {\beta }_{y,0}^{\left(k\right)}{f}_2& \cdots & {\beta }_{y,0}^{\left(k\right)}{f}_d\\ & {\beta }_{y,1}^{\left(k\right)}{\bar{\gamma }}^d& {\beta }_{y,1}^{\left(k\right)}{f}_1& \cdots & {\beta }_{y,1}^{\left(k\right)}{f}_{d-1}\\ & & \ddots & \ddots & ⋮\\ & & & {\beta }_{y,d-1}^{\left(k\right)}{\bar{\gamma }}^d& {\beta }_{y,d-1}^{\left(k\right)}{f}_1\\ & & & & {\beta }_{y,d}^{\left(k\right)}{\bar{\gamma }}^d\end{array}\right]$ , $2\le y\le k$ ,

$b_y^{\left(k\right)}=0$ , $k<y\le c+1$ ,

${\beta }_{y,i}^{\left(k\right)}=\{\begin{array}{ll}\left(y-1\right){\mu }_1+i{\mu }_2,\hfill & 0\le i\le k-y,\hfill \\ \left(k+1-y\right){\mu }_2,\hfill & k-y<i\le d.\hfill \end{array}$

(ii) 当 $c+2\le k\le c+d$ 时，

$b_y^{\left(k\right)}=\left[\begin{array}{ccccc}{\delta }_{y,0}^{\left(k\right)}{\bar{\gamma }}^d& {\delta }_{y,0}^{\left(k\right)}{f}_1& {\delta }_{y,0}^{\left(k\right)}{f}_2& \cdots & {\delta }_{y,0}^{\left(k\right)}{f}_d\\ & {\delta }_{y,1}^{\left(k\right)}{\bar{\gamma }}^d& {\delta }_{y,1}^{\left(k\right)}{f}_1& \cdots & {\delta }_{y,1}^{\left(k\right)}{f}_{d-1}\\ & & \ddots & \ddots & ⋮\\ & & & {\delta }_{y,d-1}^{\left(k\right)}{\bar{\gamma }}^d& {\delta }_{y,d-1}^{\left(k\right)}{f}_1\\ & & & & {\delta }_{y,d}^{\left(k\right)}{\bar{\gamma }}^d\end{array}\right]$ ,

${\delta }_{y,i}^{\left(k\right)}=\{\begin{array}{ccc}\left(y-1\right){\mu }_1+i{\mu }_2,& 2\le y\le k-d,& 0\le i\le d,\\ \left(y-1\right){\mu }_1+i{\mu }_2,& k-d<y\le c+1,& 0\le i\le k-y,\\ \left(k+1-y\right){\mu }_2,& k-d<y\le c+1,& k-y<i\le d.\end{array}$

b)

$B_y^{\left(1\right)}=\left[\begin{array}{ccccc}{\mu }_1{\bar{\gamma }}^d& f_1{\mu }_1& f_2{\mu }_1& \cdots & f_d{\mu }_1\\ & {\mu }_1{\bar{\gamma }}^d& f_1{\mu }_1& \cdots & f_{d-1}{\mu }_1\\ & & \ddots & \ddots & ⋮\\ & & & {\mu }_1{\bar{\gamma }}^d& f_1{\mu }_1\\ & & & & {\mu }_1{\bar{\gamma }}^d\end{array}\right]$ , $1\le y\le c$ ,

(i) 当 $2\le k\le d+1$ 时，

$B_y^{\left(k\right)}=\left[\begin{array}{ccccc}{\eta }_{y,0}^{\left(k\right)}{\bar{\gamma }}^d& f_1{\eta }_{y,0}^{\left(k\right)}& f_2{\eta }_{y,0}^{\left(k\right)}& \cdots & f_d{\eta }_{y,0}^{\left(k\right)}\\ & {\eta }_{y,1}^{\left(k\right)}{\bar{\gamma }}^d& f_1{\eta }_{y,1}^{\left(k\right)}& \cdots & f_{d-1}{\eta }_{y,1}^{\left(k\right)}\\ & & \ddots & \ddots & ⋮\\ & & & {\eta }_{y,d-1}^{\left(k\right)}{\bar{\gamma }}^d& f_1{\eta }_{y,d-1}^{\left(k\right)}\\ & & & & {\eta }_{y,d}^{\left(k\right)}{\bar{\gamma }}^d\end{array}\right]$ ,

${\eta }_{y,i}^{\left(k\right)}=\{\begin{array}{ccc}0,& 1\le y<k,& 0\le i<k-y,\\ y{\mu }_1,& 1\le y<k,& k-y\le i\le d,\\ k{\mu }_1,& k\le y\le c,& 0\le i\le d.\end{array}$

(ii)当 $d+2\le k\le d+c$ 时，

$\begin{array}{l}k=d+2,B_1^{\left(d+2\right)}=0,\\ k=d+3,B_1^{\left(d+3\right)}=0,B_2^{\left(d+3\right)}=0,\\ ⋮\\ k=d+c,B_1^{\left(d+c\right)}=0,B_2^{\left(d+c\right)}=0,\cdots ,B_{c-1}^{\left(d+c\right)}=0.\end{array}$

$B_y^{\left(d+j\right)}=\left[\begin{array}{ccccc}{\eta }_{y,0}^{\left(d+j\right)}{\bar{\gamma }}^d& f_1{\eta }_{y,0}^{\left(d+j\right)}& f_2{\eta }_{y,0}^{\left(d+j\right)}& \cdots & f_d{\eta }_{y,0}^{\left(d+j\right)}\\ & {\eta }_{y,1}^{\left(d+j\right)}{\bar{\gamma }}^d& f_1{\eta }_{y,1}^{\left(d+j\right)}& \cdots & f_{d-1}{\eta }_{y,1}^{\left(d+j\right)}\\ & & \ddots & \ddots & ⋮\\ & & & {\eta }_{y,d-1}^{\left(d+j\right)}{\bar{\gamma }}^d& f_1{\eta }_{y,d-1}^{\left(d+j\right)}\\ & & & & {\eta }_{y,d}^{\left(d+j\right)}{\bar{\gamma }}^d\end{array}\right]$ , $2\le j\le c$ , $j\le y\le c$ ,

${\eta }_{y,i}^{\left(d+j\right)}=\{\begin{array}{l}0,j\le y<d+j,0\le i<d+j-y,\\ y{\mu }_1,j\le y<d+j,d+j-y\le i\le d,\\ \left(d+j\right){\mu }_1,d+j\le y\le c,0\le i\le d.\end{array}$

$B=\left[\begin{array}{cccc}{b^{\prime }}_1& & & \\ & {b^{\prime }}_2& & \\ & & \ddots & \\ & & & {b^{\prime }}_{c+1}\end{array}\right]$ ,

其中

${b^{\prime }}_1=\left[\begin{array}{ccccc}0& 0& \cdots & 0& 0\\ & {\mu }_2{\bar{\gamma }}^d& {\mu }_2{f}_1& \cdots & {\mu }_2{f}_{d-1}\\ & & \ddots & \ddots & ⋮\\ & & & \left(d-1\right){\mu }_2{\bar{\gamma }}^d& \left(d-1\right){\mu }_2{f}_1\\ & & & & d{\mu }_2{\bar{\gamma }}^d\end{array}\right]$ ,

${b^{\prime }}_y=\left[\begin{array}{ccccc}{\omega }_{y,0}{\bar{\gamma }}^d& {\omega }_{y,0}{f}_1& {\omega }_{y,0}{f}_2& \cdots & {\omega }_{y,0}{f}_d\\ & {\omega }_{y,1}{\bar{\gamma }}^d& {\omega }_{y,1}{f}_1& \cdots & {\omega }_{y,1}{f}_{d-1}\\ & & \ddots & \ddots & ⋮\\ & & & {\omega }_{y,d-1}{\bar{\gamma }}^d& {\omega }_{y,d-1}{f}_1\\ & & & & {\omega }_{y,d}{\bar{\gamma }}^d\end{array}\right]$ , $2\le y\le c+1$ .

${\omega }_{y,i}=\left(y-1\right){\mu }_1+i{\mu }_2$ , $0\le i\le d$ .

(2)

$A_0=\left[\begin{array}{ccccc}-\left(\lambda I+c\theta I\right)& c\theta I& & & \\ & -\left(\lambda I+\left(c-1\right)\theta I\right)& \left(c-1\right)\theta I& & \\ & & \ddots & \ddots & \\ & & & -\left(\lambda I+\theta I\right)& \theta I\\ & & & & -\left(\lambda I\right)\end{array}\right]$ ,

$A_k=\left[\begin{array}{ccccc}{A}_1^{\left(k\right)}& c\theta I& & & \\ & A_2^{\left(k\right)}& \left(c-1\right)\theta I& & \\ & & \ddots & \ddots & \\ & & & A_c^{\left(k\right)}& \theta I\\ & & & & A_{c+1}^{\left(k\right)}\end{array}\right]$ , $1\le k\le d+c$ ,

其中

$A_y^{\left(k\right)}=\left[\begin{array}{ccccc}{\phi }_{y,0}^{\left(k\right)}& & & & \\ & {\phi }_{y,1}^{\left(k\right)}& & & \\ & & \ddots & & \\ & & & {\phi }_{y,d-1}^{\left(k\right)}& \\ & & & & {\phi }_{y,d}^{\left(k\right)}\end{array}\right]$ , $1\le k\le d+c$ ,

(i) 当 $y=1$ 时，

${\phi }_{1,0}^{\left(k\right)}=-\left(c\theta +\lambda \right)$ , ${\phi }_{1,d}^{\left(k\right)}=-\left({\alpha }_d^{\left(k\right)}{\bar{\gamma }}^d+c\theta +\lambda \right)$ ,

${\phi }_{1,j}^{\left(k\right)}=-\left({\alpha }_j^{\left(k\right)}{\bar{\gamma }}^d+{\displaystyle \underset{i=1}{\overset{d-j}{\sum }}{\alpha }_j^{\left(k\right)}{f}_i+c\theta +\lambda }\right)$ , $1\le j\le d-1$ .

(ii) 当 $2\le y\le c+1$ 时，

${\phi }_{y,j}^{\left(k\right)}=\{\begin{array}{lll}-\left({\mu }_1{\bar{\gamma }}^d+{\displaystyle \underset{i=1}{\overset{d-j}{\sum }}{\mu }_1{f}_j+\left(c+1-y\right)\theta +\lambda }\right),\hfill & k=1,\hfill & 1\le j\le d-1,\hfill \\ -\left({\eta }_{y-i,j}^{\left(k\right)}{\bar{\gamma }}^d+{\displaystyle \underset{i=1}{\overset{d-j}{\sum }}{\eta }_{y-i,j}^{\left(k\right)}{f}_i+{\beta }_{y+1,j}^{\left(k\right)}{\bar{\gamma }}^d}+{\displaystyle \underset{i=1}{\overset{d-j}{\sum }}{\beta }_{y,j}^{\left(k\right)}{f}_i+\left(c+1-y\right)\theta +\lambda }\right),\hfill & 2\le k\le d+c,\hfill & 1\le j\le d-1.\hfill \end{array}$

$A=\left[\begin{array}{ccccc}{A^{\prime }}_1& c\theta I& & & \\ & {A^{\prime }}_2& \left(c-1\right)\theta I& & \\ & & \ddots & \ddots & \\ & & & {A^{\prime }}_c& \theta I\\ & & & & {A^{\prime }}_{c+1}\end{array}\right]$ ,

其中

${A^{\prime }}_y=\left[\begin{array}{cccc}{\xi }_{y,0}& & & \\ & {\xi }_{y,1}& & \\ & & \ddots & \\ & & & {\xi }_{y,d}\end{array}\right]$ , $1\le y\le c+1$ .

${\xi }_{y,i}=-\left({\omega }_{y,i}{\bar{\gamma }}^d+\left(c+1-y\right)\theta +\lambda \right)$ , $0\le i\le d$ .

(3)

$C=\left[\begin{array}{cccc}\lambda I& & & \\ & \lambda I& & \\ & & \ddots & \\ & & & \lambda I\end{array}\right]$ .

3.2. 系统稳态分析

由矩阵 $Q$ 的结构可知，Markov过程 $\left\{\left(L\left(t\right),J\left(t\right),H\left(t\right)\right),t\ge 0\right\}$ 是一个GI/M/1型排队系统，当Markov过程 $\left\{\left(L\left(t\right),J\left(t\right),H\left(t\right)\right),t\ge 0\right\}$ 正常返，其稳态分布定义为

${\pi }_{i,j,h}=\underset{t\to \infty }{\lim }P\left\{L\left(t\right)=i,J\left(t\right)=j,H\left(t\right)=h\right\}$ , $\left(i,j,h\right)\in \Omega$ ,

${\pi }_i=\left({\pi }_{i,0,0},\cdots ,{\pi }_{i,0,d},\cdots ,{\pi }_{i,1,0},\cdots ,{\pi }_{i,1,d},\cdots ,{\pi }_{i,c,0},\cdots ,{\pi }_{i,c,d}\right)$ , $i\ge 0$ ,

$\Pi =\left({\pi }_0,{\pi }_1,{\pi }_2,\cdots \right)$ .

Markov过程 $\left\{\left(L\left(t\right),J\left(t\right),H\left(t\right)\right),t\ge 0\right\}$ 正常返的充分必要条件是 $d+1$ 次矩阵方程

$R^{d+1}B+RA+C=0$

存在一个最小非负解 $R$ ，且谱半径 $SP\left(R\right)<1$ ， $\left(c+1\right)\left(d+1\right)\left(c+d+1\right)d$ 维随机矩阵

$B\left[R\right]=\left(\begin{array}{ccccccccccccccc}{A}_0& C& & & & & & & & & & & & & \\ 0& A_0& C& & & & & & & & & & & & \\ ⋮& & \ddots & \ddots & & & & & & & & & & & \\ 0& \cdots & 0& A_0& C& & & & & & & & & & \\ B_1& 0& \cdots & 0& A_1& C& & & & & & & & & \\ & \ddots & \ddots & & \ddots & \ddots & \ddots & & & & & & & & \\ & & B_1& 0& \cdots & 0& A_1& C& & & & & & & \\ & & & B_2& 0& \cdots & 0& A_2& C& & & & & & \\ & & & & \ddots & \ddots & & \ddots & \ddots & \ddots & & & & & \\ & & & & & B_2& 0& \cdots & 0& A_2& C& & & & \\ & & & & & & \ddots & \ddots & & \ddots & \ddots & \ddots & & & \\ & & & & & & & B_{c+d}& 0& \cdots & 0& A_{c+d}& C& & \\ & & & & & & & & \ddots & \ddots & & \ddots & \ddots & \ddots & \\ & & & & & & & & & B_{c+d}& 0& \cdots & 0& A_{c+d}& C\\ & & & & & & & & & & B& RB& R^{2}B& \cdots & R^{d}B+A\end{array}\right)$

存在左零向量。Markov过程 $\left\{\left(L\left(t\right),J\left(t\right),H\left(t\right)\right),t\ge 0\right\}$ 正常返时，稳态分布满足如下方程组

$\{\begin{array}{l}\left({\pi }_0,{\pi }_1,\cdots ,{\pi }_{\left(c+d+1\right)d}\right)B\left[R\right]=0,\\ {\displaystyle \underset{i=0}{\overset{\left(c+d+1\right)d-1}{\sum }}{\pi }_{i}e+{\pi }_{\left(c+d+1\right)d}{\left(I_0-R\right)}^{-1}e=1,}\\ {\pi }_i={\pi }_{\left(c+d+1\right)d}{R}^{i-\left(c+d+1\right)d},i\ge \left(c+d+1\right)d.\end{array}$

其中， $e$ 是 $\left(c+1\right)\left(d+1\right)$ 维且所有元素均为1的列向量， $I_0$ 为 $\left(c+1\right)\left(d+1\right)$ 维单位矩阵。

上述结论的证明主要利用矩阵几何解方法。由于矩阵方程 $R^{d+1}B+RA+C=0$ 中的系数矩阵维数比较大且非常复杂，很难求得 $R$ 的显式表达式，因此利用Gauss-Seidel迭代方法来解决这个问题，迭代算法的步骤如表1所示。

Table 1. Iterative algorithm of rate matrix R

表1. 率阵 $R$ 的迭代算法

3.3. 系统性能指标

根据排队模型的稳态分布，推导出混合P2P网络性能指标表达式，进而研究系统性能指标随参数变化的情况。假设I类服务节点在休假期的平均能耗为 $y_1$ ，闲期内的平均能耗为 $y_2$ ，工作期的平均能耗为 $y_3$ ，且 $y_1<y_2<y_3$ 。

1) 请求节点的平均队长 $E\left(L\right)$ 为

$E\left(L\right)={\displaystyle \underset{i=0}{\overset{\infty }{\sum }}iP\left(L=i\right)}={\displaystyle \underset{i=1}{\overset{\infty }{\sum }}i\left({\displaystyle \underset{j=0}{\overset{c}{\sum }}{\displaystyle \underset{h=0}{\overset{d}{\sum }}{\pi }_{i,j,h}}}\right)}$ .

2) 请求节点的平均等待时间 $E\left(W\right)$ 为

$E\left(W\right)=\frac{1}{\lambda }E\left(L\right)=\frac{1}{\lambda }{\displaystyle \underset{i=1}{\overset{\infty }{\sum }}i\left({\displaystyle \underset{j=0}{\overset{c}{\sum }}{\displaystyle \underset{h=0}{\overset{d}{\sum }}{\pi }_{i,j,h}}}\right)}$ .

3) 系统休假期的平均能耗 $G_1$ 为

$G_1=y_1\left({\displaystyle \underset{i=0}{\overset{\infty }{\sum }}{\displaystyle \underset{h=0}{\overset{d}{\sum }}{\displaystyle \underset{j=0}{\overset{c-1}{\sum }}\left(c-j\right){\pi }_{i,j,h}}}}\right)$ .

4) 系统闲期的平均能耗 $G_2$ 为

$G_2=y_2\left({\displaystyle \underset{h=0}{\overset{d}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\displaystyle \underset{i=0}{\overset{\left(j+h-1\right)d}{\sum }}\left(j-\left[\frac{i}{d}\right]+h\right){\pi }_{i,j,h}}}}\right)$ .

5) 系统工作期的平均能耗 $G_3$ 为

$G_3=y_3\left({\displaystyle \underset{h=0}{\overset{d}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\displaystyle \underset{i=0}{\overset{\left(j+h\right)d}{\sum }}\left(\left[\frac{i}{d}\right]-h\right){\pi }_{i,j,h}+{\displaystyle \underset{h=0}{\overset{d}{\sum }}{\displaystyle \underset{j=1}{\overset{c}{\sum }}{\displaystyle \underset{i=\left(j+h\right)d+1}{\overset{\infty }{\sum }}j{\pi }_{i,j,h}}}}}}}\right)$ .

6) 系统的总能耗 G为

$G=G_1+G_2+G_3$ .

4. 数值实验

系统中大量的节点发出资源请求，排队等待的节点数过多容易使系统负载过大造成系统瘫痪，为更好的选取合适的参数降低系统的能耗，本文利用软件编程进行数值分析，得到系统能耗随参数变化的图像，进而分析参数变化对不同时期能耗的影响选取合适的参数。分析所涉及到的系统参数表示含义见表2。

Table 2. Meaning of system parameters

表2. 系统参数的含义

4.1. 参数变化对P2P网络系统能耗的影响

根据实际情况设定I类服务节点在休假期的平均能耗 $y_1=0.4$ ，闲期的平均能耗 $y_2=0.5$ ，工作期的平均能耗 $y_3=0.8$ 。

图2表示当 $c=6$ ， $d=2$ ， ${\mu }_2=2.5$ ， $\gamma =0.6$ 时，系统休假期的能耗 $G_1$ 随参数 $\lambda$ ， ${\mu }_1$ 和 $\theta$ 变化的情况。在 $\lambda$ 和 ${\mu }_1$ 固定的情况下，随着 $\theta$ 的增大， $G_1$ 呈下降趋势。 $G_1$ 下降的主要原因是当休假参数增大，I类服务节点的平均休假时间减少，越多的I类服务节点转为闲期或者工作期，因此系统休假期的能耗降低；在 $\lambda$ 和 $\theta$ 固定的情况下，随着 ${\mu }_1$ 的增大， $G_1$ 呈上升趋势。主要是因为当I类服务节点的服务率增大，服务的效率变高，排队等待的请求节点越快地进入系统接受服务然后离开系统，从而使得等待的节点数减少，越多的处于工作期的I类服务节点从工作期转为休假期，从而休假期的能耗变大；在 ${\mu }_1$ 和 $\theta$ 固定的情况下，随着 $\lambda$ 的增大， $G_1$ 也有上升趋势。当请求节点到达的数量越多，意味着越容易满足批量服务的启动数量d进入系统，节点资源传输结束后离开系统，排队等待的请求节点数逐渐减少到小于d，I类服务节点从工作期转为休假期，休假期的能耗增加。

Figure 2. Effect of $\lambda$ , ${\mu }_1$ and $\theta$ on the energy consumption $G_1$ during the vacation period

图2. $\lambda$ 、 ${\mu }_1$ 和 $\theta$ 对休假期能耗 $G_1$ 的影响

图3反映了当 $c=6$ ， $d=2$ ， ${\mu }_2=2.5$ ， $\gamma =0.35$ ， $\theta =1$ 时，系统闲期能耗 $G_2$ 和工作期能耗 $G_3$ 随参数 $\lambda$ 和 ${\mu }_1$ 的变化情况。当 ${\mu }_1$ 固定不变时，随着 $\lambda$ 的增大， $G_2$ 呈下降趋势， $G_3$ 呈上升趋势。主要是因为随着到达率的增大，资源请求的节点增多，容易满足批量服务条件，同时为提供服务部分I类服务节点从闲期转换为工作期，因此闲期能耗降低，工作期能耗增加；当 $\lambda$ 固定不变时，随着 ${\mu }_1$ 的增大， $G_2$ 呈上升趋势， $G_3$ 呈下降趋势。主要是因为当I类服务节点的服务率增加，节点的服务效率增大，越多的请求节点完成服务离开系统，系统中的请求节点数减少，部分I类服务节点从工作期进入闲期，所以闲期的能耗增加，工作期的能耗降低。由此可知，为了降低闲期不必要的能耗，可以增加请求节点的到达率，适当减少I类服务节点的服务率，使得更多的I类服务节点能处于工作期。

Figure 3. Effect of $\lambda$ , ${\mu }_1$ on the energy consumption G₂ during the idle period and G₃ during the working period

图3. $\lambda$ 和 ${\mu }_1$ 对闲期能耗G₂和工作期能耗G₃的影响

图4表示当 $c=6$ ， $d=2$ ， ${\mu }_2=2.5$ 时，系统总能耗G随参数 $\lambda$ ， $\theta$ ， ${\mu }_1$ 和 $\gamma$ 的变化。当 $\theta$ ， ${\mu }_1$ 和 $\gamma$ 固定不变时，随着 $\lambda$ 的增大，G呈上升趋势。主要是因为当请求节点数增多，需要更多的节点提供服务，使得处于工作期的I类服务节点数增多，又根据假设条件 $y_1<y_2<y_3$ 设定工作期的能耗最大，因此总能耗增加；当 $\lambda$ ， ${\mu }_1$ 和 $\gamma$ 固定不变时，随着 $\theta$ 的增大，G也呈上升趋势。主要因为当I类服务节点的休假参数变大，其休假时间减少，越多的节点从休假期转为工作期或闲期，工作期和闲期的能耗要大于休假期，因此总能耗增大；当 $\lambda$ ， $\theta$ 和 $\gamma$ 固定不变时，随着 ${\mu }_1$ 的增大，G呈下降趋势。I类服务节点的服务率增大，服务效率变高，更多的请求节点被服务完毕，系统中排队等待的请求节点数减少，因此处于工作期的I类服务节点数减少，总能耗降低；当 $\lambda$ ， $\theta$ 和 ${\mu }_1$ 固定不变时，随着 $\gamma$ 的增大，G呈下降趋势。当服务结束的请求节点返回系统的概率增大，相当于II类服务节点的数量增多，可提供服务的节点变多，完成服务离开系统的请求节点数增多，处于工作期的I类服务节点减少影响总能耗降低。

Figure 4. Effect of $\lambda$ , $\theta$ , ${\mu }_1$ and $\gamma$ on the total system energy consumption G

图4. $\lambda$ 、 $\theta$ 、 ${\mu }_1$ 和 $\gamma$ 对总能耗G的影响

4.2. 纳什均衡策略

现实生活中，大部分是不可观察排队，请求节点在进入系统前不知道系统中的节点数量，请求节点往往追求自身利益最大化而做出自己的行为选择，会对系统的运行产生很大的影响，同时他们的策略选择也会受到其他请求节点或服务节点的影响，在长期多方合作的非博弈过程中，就会形成纳什均衡。我们通常假设节点是风险中立的，节点获得服务后会得到回报，而在等待中需要支付费用，并假设其既不能在排队中中途退出，也不能止步后重新到达。

由于顾客的追求自身利益最大化行为往往背离整个社会的整体利益偏好，因此，本文针对P2P网络的优化问题，为了抑制节点的自私行为建立一种收费方案，使得顾客的行为和社会最优决策行为尽量保持一致，提出如下假设：

(1) 请求节点接受完一次资源传输，可获得的回报为r；

(2) 请求节点进入系统，开始资源传输的激活费用为 $f_1$ ；

(3) 请求节点在系统中逗留等待的成本为 $f_2$ 。

单个请求节点的净收益为

$U=r-f_1-f_{2}E\left(W\right)$ .

图5反映了当 $c=6$ ， $d=2$ ， ${\mu }_2=2.5$ ， $\theta =1$ ， $r=7.2$ ， $f_1=2.5$ ， $f_2=4.5$ 时，请求节点的个人净收益U随着参数 $\lambda$ ， ${\mu }_1$ 和 $\gamma$ 的变化情况。由图可知，当 ${\mu }_1$ 和 $\gamma$ 固定不变时，随着 $\lambda$ 的增大，U先呈上升趋势然后有下降趋势。主要是因为随着请求节点的到达率增大，请求节点容易达到批量服务数量进入系统接受服务，队列中的请求节点等待时间减小，当没有空闲的服务节点时，随着到达的请求节点数增多，请求节点的等待时间增加，而个人效益和请求节点的平均等待时间成反比，所以个人效益先增大后减小；当 $\lambda$ 和 $\gamma$ 固定不变时，随着 ${\mu }_1$ 的增加，U呈上升趋势。主要是因为当I类服务节点的服务率增加，越多的请求节点接受完服务离开系统，请求节点等待的时间减少等待的费用减少，从而个人效益增加；当 $\lambda$ 和 ${\mu }_1$ 固定不变时，随着 $\gamma$ 的增加，U呈上升趋势。随着请求节点返回系统提供服务的概率增加，可提供服务的节点增加，等待的请求节点减少，影响个人效益增加。由图5可看出，随着到达率的增加，个人净收益存在负值和正值，中间存在个人净收益等于0的点，即纳什均衡点，此时的到达率为纳什均衡到达率。

Figure 5. Effect of $\lambda$ , ${\mu }_1$ and $\gamma$ on the net benefit U of individual requesting nodes

图5. $\lambda$ 、 ${\mu }_1$ 和 $\gamma$ 对个人收益U的影响

4.3. 社会最优策略

针对P2P网络社会最优策略分析，考虑每个时刻系统中节点的平均净收益，社会最优的目的是为了最大化全部节点的总收益。

假设平均社会净收益函数

$U_s=\lambda \left(r-f_1-f_{2}E\left(W\right)\right)$ .

图6反映了当 $c=6$ ， $d=2$ ， ${\mu }_2=2.5$ ， $\gamma =0.35$ ， $\theta =1$ ， $r=8$ ， $f_1=2$ ， $f_2=4.5$ 时，平均社会净收益 $U_s$ 随参数 $\lambda$ 和 ${\mu }_1$ 的变化情况。当 $\lambda$ 固定不变时，随着 ${\mu }_1$ 的增大， $U_s$ 呈上升趋势。主要是因为随着I类服务节点的服务率增加，服务效率变快，平均社会收益与单个节点的个人净收益成正比，个人净收益增加，从而平均社会收益增加；当 ${\mu }_1$ 固定不变时，随着 $\lambda$ 的增大， $U_s$ 也呈上升趋势。因为当请求节点的到达率增大，越多的请求节点进入系统接受服务，平均社会收益越大。该条件下最大平均社会净收益为 $U_s=10.4527$ ，此时的最优到达率为 $\lambda =3.5$ ，最优服务率为 ${\mu }_1=4.5$ 。

Figure 6. Effect of $\lambda$ and ${\mu }_1$ on the average social net benefit $U_s$

图6. $\lambda$ 和 ${\mu }_1$ 对平均社会净收益 $U_s$ 的影响

5. 结论

本文针对混合P2P网络，利用排队论的知识对系统进行建模分析，在经典排队模型的基础上引入异步单重休假、批量服务且接受完服务的请求节点可返回系统提供服务等策略，建立两类服务台且服务台数变化的M/M^d/ $c+k$ ，( $0\le k\le d$ )排队模型。利用矩阵几何解方法和GI/M/1型结构矩阵，分析系统的稳态分布，进一步得到了系统各项性能指标的表达式，并结合混合P2P网络主要研究了系统不同时期的能耗随参数的变化情况。最后为了更好的研究如何提升P2P网络的性能，分析了请求节点到达率和收益之间的纳什均衡以及社会收益最优策略。通过数据分析结果可知，适当增加请求节点的到达率，提高I类节点的休假参数可以有效减少休假期以及闲期的不必要能耗，增加I类服务节点的服务率可以同时提高个人收益和社会收益。