基于N-策略两阶段服务异步休假排队的P2P网络性能分析

Performance Analysis of a Two-Stage Queuing System Based on N-Policy and Asynchronous Vacation in the P2P Network

摘要: 随着互联网的发展，P2P作为一种新兴的网络技术，凭借着去中心化、可扩展性等独特的优势，已经被广泛应用于各个领域。本文针对P2P网络中的能耗问题，引入部分节点异步多重休假策略来降低系统能耗，建立了一个带有不耐烦顾客、N-策略和异步休假的两阶段M/M/c排队模型。利用拟生灭过程和矩阵几何解方法得到系统稳态下的概率分布向量，推导出节点平均队长和系统能耗等性能指标的表达式，构造系统的社会效用函数，得到相应的最优到达率和最优服务率。

Abstract: With the development of the Internet, P2P, as an emerging network technology, has been widely used in various fields by means of its unique advantages such as decentralization and scalability. To address the issue of energy consumption in the P2P network, the asynchronous multiple vacation strategy is introduced and a two-stage M/M/c queuing model with impatient customers, N-policy and asynchronous vacation is built. The probability distribution vectors in the steady state are obtained by using the quasi-birth-and-death process and matrix-geometric solution method. And the expressions for the performance indicators are deduced, such as the energy consumption of the system. The optimal arrival rate and optimal service rate are obtained by constructing the social utility function.

1. 引言

近年来，对等网络(Peer-to-Peer network，简称P2P网络)逐渐走入大众的视野，并且得到迅猛的发展[1]，它不同于传统的网络技术，是一种用户之间直接进行资源共享的新型的网络技术，具有高扩展性、节点对等性、资源利用率高等优势，这些独特的优势使得P2P网络在互联网中占据主导地位。

P2P网络是大规模、自组织、无中心依赖性的覆盖网络，构建在底层物理网络之上，其拓扑结构是研究P2P系统应用的重要课题。非结构化对等网络基本是通过随机选择邻居节点的方式构建拓扑结构，节点不断加入、离开，具有较好的容错能力，利于进行网络的全局部署。Kwong和Tsang [2]提出了一种用于构建异构环境下非结构化网络拓扑的随机行走协议，利用Metropolis-Hastings算法给出了数学模型，证明了不同的节点容量分布会导致不同的拓扑结构，为在异构环境下从不同方面优化P2P网络提供了指导。结构化对等网络拥有严格的拓扑结构，主要采用分布式哈希表(DHT) [3]技术存储、查询数据，数据的存放位置、查询算法具有精确的描述，解决了数据定位的问题，具有可扩展性、鲁棒性等特点。

随着信息技术的不断发展，由经典排队理论延伸出一些更为复杂的排队策略，如服务台休假、两阶段服务、N-策略等，这些策略使得排队论更好地应用于实际生活。Ma等[4]提出了一种同步休假、异步休假相结合的VM调度策略，并且引入休假唤醒阈值，提高了系统的利用率，降低了云数据中心的能耗。刘洺辛等[5]兼顾系统服务质量和资源利用率两方面，研究了部分服务台异步N-策略多重休假的M/M/c排队模型，给出了系统平均等待时间等指标。

已有学者将排队理论应用于分析P2P网络系统中由于大量节点在线产生的能耗问题，进而优化P2P网络性能。Liu等[6]建立了具有同步工作休假的两阶段服务排队模型，使得闲期节点可适当离线，通过数值实验表明部分节点休假能有效减少P2P网络系统产生的能耗。Zhang和Yin [7]建立了M/M/1/N模型来分析P2P网络系统的性能，给出了平均等待时间等表达式，最后通过数值实例验证了计算结果。

2. 混合多层P2P网络与建模

2.1. 混合多层P2P网络

P2P网络各个节点间不同的逻辑连接形式构成了不同的拓扑结构，目前移动P2P网络广泛使用中心化、全分布式非结构化、全分布式结构化和半分布式四种拓扑结构。非结构化P2P网络具有良好的稳定性和容错能力，但由于各节点间采用泛洪方式查询，可能导致查询效率低，造成网络拥塞。基于DHT的结构化P2P网络具有良好的扩展性和负载均衡性，但网络中节点频繁加入、退出会影响其稳定性。为了解决系统资源查询效率低、网络负载大等问题，结合非结构化P2P网络与结构化P2P网络的优势，构建了一个混合多层P2P网络[8]结构。

该网络系统中资源请求的具体流程是当系统收到请求节点的资源请求信息后，首先在该节点群内进行查询、搜索是否存在所需的资源，如果存在，则该请求节点在节点群内接收数据进行传输，服务完成后离开系统，如果节点群内资源结构不完整则需要跨区域在其他节点群内进行查询，通过超级节点的资源转发和查询，将拥有该资源的节点与请求节点建立连接进行数据传输。因此可以把整个资源请求过程抽象为两阶段服务排队模型。

2.2. 模型描述

本文将排队模型应用于分析混合多层P2P网络(简称为P2P网络)中请求节点向网络系统请求资源以及完成资源传输的过程，将请求节点请求资源传输抽象为顾客到达过程，将服务节点进行资源传输抽象为服务过程，将服务节点完成资源传输过程抽象为顾客完成服务，建立一个部分节点异步多重休假的两阶段服务的排队模型，具体的模型假设及系统参数如下。

1) 该系统由两阶段服务节点串联组成，假设第一阶段的服务节点由节点群内的c $\left(c\ge 1\right)$ 个普通节点构成，第二阶段的服务节点由该节点群内的超级节点和与之相连的其他节点群抽象为一个服务台构成。假设第一阶段服务系统存在一个可容纳无限个请求节点的缓冲区，第二阶段缓冲区的容量为K，当第二阶段缓冲区请求节点数达到K时，在第一阶段服务完成的节点直接离开系统，遵循消失制原则。

2) 假设系统中请求节点的到达过程为泊松过程，到达率为λ $\left(\lambda >0\right)$ 。请求节点到达系统后首先在第一阶段接受服务，服务完成后以概率p $\left(0\le p\le 1\right)$ 进入第二阶段继续接受服务，或者以概率$1-p$ 离开系统。假设两阶段节点的服务时间分别服从参数为${\mu }_1$ $\left({\mu }_1>0\right)$ 、${\mu }_2$ $\left({\mu }_2>0\right)$ 的指数分布。

3) 为了兼顾系统的服务质量与减少节点持续在线产生的能耗，在第一阶段服务系统中引入部分节点异步多重休假策略，且d为最大休假节点数，即当系统中处于休假的服务节点数小于d，且缓冲区没有等待的请求节点时，该服务节点服务完成后开始一次长度为V的休假，且假定其服从参数为θ的指数分布，当一次休假结束缓冲区仍没有请求节点到达时，则开始另一次休假；当休假结束缓冲区有请求节点到达时，则该节点由休假状态转换为工作状态；当处于休假的服务节点数等于d时，若缓冲区为空则服务完成后进入一般的空闲状态，等待请求节点到达继续服务；若缓冲区有请求节点等待时则继续服务。

4) 为了避免节点多次重新启动，系统引入N-策略，即第一阶段的服务节点在完成一次休假后，如果缓冲区的请求节点数小于阈值N $\left(0<d<c<N\right)$ ，则开始另一次休假，直到某次休假结束时，缓冲区的请求节点数大于等于N，该服务节点返回系统转换为工作状态。

5) 假设第二阶段的服务节点一直在线不休假。由于第二阶段只有一个服务节点，缓冲区内的请求节点可能会因长时间排队变得不耐烦，假设其在系统内耐心等待的时间服从参数为ξ的指数分布。

3. 模型分析

3.1. 状态转移率矩阵

令$L_1\left(t\right)=i$ 和$L_2\left(t\right)=j$ 分别表示时刻t系统中第一阶段和第二阶段的请求节点数为$i\left(i\ge 0\right)$ 和$j\left(0\le j\le K\right)$ ，$J\left(t\right)=m$ 表示时刻t系统中第一阶段的服务节点休假数为$m\left(0\le m\le d\right)$ ，$J\left(t\right)$ 的具体定义如下：

$J\left(t\right)=\{\begin{array}{c}0,时刻t系统中有0个服务节点休假，\\ 1,时刻t系统中有1个服务节点休假，\\ \cdots \\ d,时刻t系统中有d个服务节点休假。\end{array}$

因此由上述假设可得$\{\left(L_1\left(t\right),L_2\left(t\right),J\left(t\right)\right),t\ge 0\}$ 是一个三维Markov过程，状态空间表示为

$\Omega ={\Omega }_1\cup {\Omega }_2\cup {\Omega }_3$

其中

${\Omega }_1=\left\{\left(i,j,d\right),0\le i\le c-d,0\le j\le K\right\}$ ,

${\Omega }_2=\left\{\left(i,j,m\right),c-d<i<c,0\le j\le K,c-i\le m\le d\right\}$ ,

${\Omega }_3=\left\{\left(i,j,m\right),i\ge c,0\le j\le K,0\le m\le d\right\}$ .

按照字典序对系统的各状态进行排列，三维Markov过程状态转移率矩阵可写成以下分块矩阵形式，表示为

$Q=\left[\begin{array}{ccccccccccccccc}{A}_0& C_0& & & & & & & & & & & & & \\ B_1& A_1& C_1& & & & & & & & & & & & \\ & B_2& A_2& C_2& & & & & & & & & & & \\ & & \ddots & \ddots & \ddots & & & & & & & & & & \\ & & & B_{c-d}& A_{c-d}& C_{c-d}& & & & & & & & & \\ & & & & B_{c-d+1}& A_{c-d+1}& C_{c-d+1}& & & & & & & & \\ & & & & & \ddots & \ddots & \ddots & & & & & & & \\ & & & & & & B_{c-1}& A_{c-1}& C_{c-1}& & & & & & \\ & & & & & & & B_c& A_c& C& & & & & \\ & & & & & & & & B& A_{c+1}& C& & & & \\ & & & & & & & & & \ddots & \ddots & \ddots & & & \\ & & & & & & & & & & B& A_{N-1}& C& & \\ & & & & & & & & & & & B& A& C& \\ & & & & & & & & & & & & \ddots & \ddots & \ddots \end{array}\right]$

其中$A_0,C_0,A_i\left(1\le i\le N-1\right),B_i\left(1\le i\le c\right),C_i\left(1\le i\le c-1\right)$ 及$\left(K+1\right)\left(d+1\right)$ 维方阵$A,{\rm B},C$ 分别表示对应水平间的状态转移率矩阵。为了更简便的表示以上子块矩阵，定义如下的符号。

当$0\le k\le K-1$ 时，

$a_{3,k}=-\lambda -{\mu }_2-k\xi -\left(c-d+l\right){\mu }_1$ .

构建$K+1$ 维方阵$D_1$ 、$D_{2,k}\left(0\le k\le d-c+i\right)$ 、$D_{3,l}\left(0\le l\le d-c+i\right)$ 、$D_{4,l}\left(1\le l\le d\right)$ 、$G_k\left(0\le k\le d-1\right)$ 。

$D_1=\text{diag}\left(\lambda ,\lambda ,\cdots ,\lambda \right)$ ，$D_{4,l}=\text{diag}\left(l\theta ,l\theta ,\cdots ,l\theta \right)$ ，$G_k=D_{3,k}-D_{4,d-k}$ ，

$D_{2,k}=\left[\begin{array}{cccc}\left(c-d+k\right){\mu }_1\overline{p}& \left(c-d+k\right){\mu }_{1}p& & \\ & \ddots \text{}& \ddots & \\ & & \left(c-d+k\right){\mu }_1\overline{p}& \left(c-d+k\right){\mu }_{1}p\\ & & & \left(c-d+k\right){\mu }_1\end{array}\right]$，

$D_{3,l}=\left[\begin{array}{ccccc}-\lambda -\left(c-d+l\right){\mu }_1& & & & \\ {\mu }_2& a_{3,0}& & & \\ & {\mu }_2+\xi & a_{3,1}& & \\ & & \ddots & \ddots & \\ & & & {\mu }_2+\left(K-1\right)\xi & a_{3,K-1}\end{array}\right]$ .

因此Q矩阵的子块矩阵表示如下：

当$0\le i<c-d$ 时，$K+1$ 维方阵$C_i$ 为

$C_i=\text{diag}\left(\lambda ,\lambda ,\cdots ,\lambda \right)$ .

当$c-d\le i\le c-1$ 时，$\left(K+1\right)\left(d-c+i+1\right)\times \left(K+1\right)\left(d-c+i+2\right)$ 维矩阵$C_i$ 为

$C_i=\left[\begin{array}{ccccc}{D}_1& & & & \\ & D_1& & & \\ & & \ddots & & \\ & & & D_1& O\end{array}\right]$ .

当$1\le i\le c-d$ 时，$K+1$ 维方阵$B_i$ 为

$B_i=\left[\begin{array}{ccccc}i{\mu }_1\overline{p}& i{\mu }_{1}p& & & \\ & i{\mu }_1\overline{p}& i{\mu }_{1}p& & \\ & & \ddots & \ddots & \\ & & & i{\mu }_1\overline{p}& i{\mu }_{1}p\\ & & & & i{\mu }_1\end{array}\right]$ .

当$c-d+1\le i\le c$ 时，$\left(K+1\right)\left(d-c+i+1\right)\times \left(K+1\right)\left(d-c+i\right)$ 维矩阵$B_i$ 为

$B_i=\left[\begin{array}{cccc}{D}_{2,0}& & & \\ & D_{2,1}& & \\ & & \ddots & \\ \begin{array}{c}\\ \end{array}& \begin{array}{c}\\ \end{array}& \begin{array}{c}\\ \end{array}& \begin{array}{c}{D}_{2,d-c+i-1}\\ D_{2,d-c+i}\end{array}\end{array}\right]$ .

当$1\le i\le c-d$ 时，$K+1$ 维方阵$A_i$ 为

$A_i=\left[\begin{array}{ccccc}-\lambda -i{\mu }_1& & & & \\ {\mu }_2& -\lambda -i{\mu }_1-{\mu }_2& & & \\ & {\mu }_2+\xi & -\lambda -i{\mu }_1-{\mu }_2-\xi & & \\ & & \ddots & \ddots & \\ & & & {\mu }_2+\left(K-1\right)\xi & -\lambda -i{\mu }_1-{\mu }_2-\left(K-1\right)\xi \end{array}\right]$

当$c-d+1\le i\le c$ 时，$\left(K+1\right)\left(d-c+i+1\right)$ 维方阵$A_i$ 为

$A_i=\left[\begin{array}{ccccc}{D}_{3,0}& & & & \\ & D_{3,1}& & & \\ & & \ddots & & \\ & & & D_{3,d-c+i+1}& \\ & & & & D_{3,d-c+i}\end{array}\right]$ .

当$c+1\le i\le N-1$ 时，$\left(K+1\right)\left(d+1\right)$ 维方阵$A_i$ 为

$A_i=\left[\begin{array}{ccccc}{D}_{3,0}& & & & \\ & D_{3,1}& & & \\ & & \ddots & & \\ & & & D_{3,d-1}& \\ & & & & D_{3,d}\end{array}\right]$ .

$K+1$ 维方阵$A_0$ 为

$A_0=\left[\begin{array}{ccccc}-\lambda & & & & \\ {\mu }_2& -\lambda -{\mu }_2& & & \\ & {\mu }_2+\xi & -\lambda -{\mu }_2-\xi & & \\ & & \ddots & \ddots & \\ & & & {\mu }_2+\left(K-1\right)\xi & -\lambda -{\mu }_2-\left(K-1\right)\xi \end{array}\right]$ .

$A=\left[\begin{array}{ccccc}{G}_0& D_{4,d}& & & \\ & G_1& D_{4,d-1}& & \\ & & \ddots & \ddots & \\ & & & G_{d-1}& D_{4,1}\\ & & & & D_{3,d}\end{array}\right]$ , $B=\left[\begin{array}{ccccc}{D}_{2,0}& & & & \\ & D_{2,1}& & & \\ & & \ddots & & \\ & & & D_{2,d-1}& \\ & & & & D_{2,d}\end{array}\right]$ ,

$C=\text{diag}\left(\lambda ,\lambda ,\cdots ,\lambda \right)$ .

3.2. 系统稳态分析

由矩阵Q三对角形式的结构可知，Markov过程$\{\left(L_1\left(t\right),L_2\left(t\right),J\left(t\right)\right),t\ge 0\}$ 是一个拟生灭过程，当该Markov过程正常返时，满足的稳态分布如下

${\pi }_{i,j,m}=\underset{t\to \infty }{\lim }P\left\{L_1\left(t\right)=i,L_2\left(t\right)=j,J\left(t\right)=m\right\}=P\left\{L_1=i,L_2=j,J=m\right\},\left(i,j,m\right)\in \Omega$ ，

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

其中

${\pi }_i=\left({\pi }_{i,0,d},{\pi }_{i,1,d},\cdots ,{\pi }_{i,K,d}\right),0\le i\le c-d$ ，

${\pi }_i=\left({\pi }_{i,0,d},{\pi }_{i,1,d},\cdots ,{\pi }_{i,K,d},{\pi }_{i,0,d-1},\cdots ,{\pi }_{i,K,d-1},{\pi }_{i,0,c-i},{\pi }_{i,1,c-i},\cdots ,{\pi }_{i,K,c-i}\right),c-d<i<c$ ，

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

该过程$\{\left(L_1\left(t\right),L_2\left(t\right),J\left(t\right)\right),t\ge 0\}$ 正常返的充分必要条件是矩阵方程

$R^{2}B+RA+C=0$

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

$B\left[R\right]=\left[\begin{array}{ccccccccccccc}{A}_0& C_0& & & & & & & & & & & \\ B_1& A_1& C_1& & & & & & & & & & \\ & B_2& A_2& C_2& & & & & & & & & \\ & & \ddots & \ddots & \ddots & & & & & & & & \\ & & & B_{c-d}& A_{c-d}& C_{c-d}& & & & & & & \\ & & & & B_{c-d+1}& A_{c-d+1}& C_{c-d+1}& & & & & & \\ & & & & & \ddots & \ddots & \ddots & & & & & \\ & & & & & & B_{c-1}& A_{c-1}& C_{c-1}& & & & \\ & & & & & & & B_c& A_c& C& & & \\ & & & & & & & & B& A_{c+1}& C& & \\ & & & & & & & & & \ddots & \ddots & \ddots & \\ & & & & & & & & & & B& A_{N-1}& C\\ & & & & & & & & & & & B& RB+A\end{array}\right]$

存在左零向量。当该三维连续Markov过程正常返时，根据平衡方程和正规化条件可知，稳态分布满足下列方程组

$\{\begin{array}{l}\left({\pi }_{\text{0}},{\pi }_{\text{1}},\cdots ,{\pi }_N\right)B\left[R\right]=0\\ {\displaystyle \sum _{i=\text{0}}^{c-d}{\pi }_i{e}_{\text{0}}}+{\displaystyle \sum _{i=c-d+\text{1}}^{N-\text{1}}{\pi }_{i}e}+{\pi }_N{\left(I-R\right)}^{-\text{1}}e=\text{1}\\ {\pi }_i={\pi }_N{R}^{i-N},i\ge N\end{array}$

其中，$e_0$ 是$K+1$ 维列向量且各元素都是1，e是适当维数且各元素都是1的列向量，I是$\left(K+1\right)\left(d+1\right)$ 维单位矩阵。

由于矩阵$A,{\rm B},C$ 维数较大相对复杂，可以通过迭代方法近似求解率阵R，Gauss-Seidel迭代算法收敛速度快、运行时间短，是求解线性方程组的经典算法。因此本文运用Gauss-Seidel迭代法通过迭代条件$R=-\left(R^{2}B+C\right)A^{-1}$ 最终得到${\pi }_{i,j,m}$ 的数值。

3.3. 性能指标

利用上述方法得到系统稳态概率分布向量π，通过分析给出系统的性能指标。

1) 系统中第一二阶段请求节点的平均队长为

$E\left(L_1\right)={\displaystyle \sum _{i=1}^{c-d}i\left({\displaystyle \sum _{j=0}^K{\pi }_{i,j,d}}\right)}+{\displaystyle \sum _{i=c-d+1}^{c-1}i\left({\displaystyle \sum _{j=0}^K{\displaystyle \sum _{m=c-i}^d{\pi }_{i,j,m}}}\right)}+{\displaystyle \sum _{i=c}^{\infty }i\left({\displaystyle \sum _{j=0}^K{\displaystyle \sum _{m=0}^d{\pi }_{i,j,m}}}\right)}$ ，

$E\left(L_2\right)={\displaystyle \sum _{j=1}^{K}j\left({\displaystyle \sum _{i=0}^{c-d}{\pi }_{i,j,d}}\right)}+{\displaystyle \sum _{j=1}^{K}j\left({\displaystyle \sum _{i=c-d+1}^{c-1}{\displaystyle \sum _{m=c-i}^d{\pi }_{i,j,m}}}\right)}+{\displaystyle \sum _{j=1}^{K}j\left({\displaystyle \sum _{i=c}^{\infty }{\displaystyle \sum _{m=0}^d{\pi }_{i,j,m}}}\right)}$ .

2) 系统中两阶段处于服务状态的服务节点数为

$E\left(Q_1\right)={\displaystyle \sum _{i=1}^{c-d}{\displaystyle \sum _{j=0}^{K}i{\pi }_{i,j,d}}}+{\displaystyle \sum _{i=c-d+1}^{c-1}{\displaystyle \sum _{j=0}^K{\displaystyle \sum _{m=c-i}^d\left(c-m\right){\pi }_{i,j,m}}}}+{\displaystyle \sum _{i=c}^{\infty }{\displaystyle \sum _{j=0}^K{\displaystyle \sum _{m=0}^d\left(c-m\right){\pi }_{i,j,m}}}}$ ，

$E\left(Q_2\right)={\displaystyle \sum _{j=1}^K{\displaystyle \sum _{i=0}^{c-d}{\pi }_{i,j,d}}}+{\displaystyle \sum _{j=1}^K{\displaystyle \sum _{i=c-d+1}^{c-1}{\displaystyle \sum _{m=c-i}^d{\pi }_{i,j,m}}}}+{\displaystyle \sum _{j=1}^K{\displaystyle \sum _{i=c}^{\infty }{\displaystyle \sum _{m=0}^d{\pi }_{i,j,m}}}}$ .

3) 假设$y_1,y_2,y_3$ 分别是第一阶段单个服务节点在休假期、闲期、工作期的平均能耗，其中$y_3>y_2>y_1>0$ ，则第一阶段服务系统在休假期、闲期、工作期的平均能耗为

$G_1=y_1\left({\displaystyle \sum _{i=0}^{c-d}{\displaystyle \sum _{j=0}^{K}d{\pi }_{i,j,d}}}+{\displaystyle \sum _{i=c-d+1}^{c-1}{\displaystyle \sum _{j=0}^K{\displaystyle \sum _{m=c-i}^{d}m{\pi }_{i,j,m}}}}+{\displaystyle \sum _{i=c}^{\infty }{\displaystyle \sum _{j=0}^K{\displaystyle \sum _{m=0}^{d}m{\pi }_{i,j,m}}}}\right)$ ，

$G_2=y_2\left[{\displaystyle \sum _{i=0}^{c-d}{\displaystyle \sum _{j=0}^K\left(c-d-i\right){\pi }_{i,j,d}}}\right]$ ，

$G_3=y_{3}E\left(Q_1\right)$ .

4) 假设$y_4$ 为第二阶段单个请求节点在工作状态的平均能耗，则第二阶段服务节点的平均能耗为

$G_4=y_{4}E\left(Q_2\right)$ .

5) 系统的总能耗为

$G=G_1+G_2+G_3+G_4$ .

4. 数值实验

基于上述研究得到系统稳态下性能指标的表达式，根据P2P网络的实际情况及Markov过程的稳态条件选取适当的参数，利用MATLAB编程绘制图像，分析其参数变化对各性能指标的影响，为优化P2P网络系统性能提供依据。

4.1. 参数变化对P2P系统性能指标的影响

假设$c=7,K=12,{\mu }_1=2,\xi =1.5,p=0.7,\theta =1.5,{\mu }_2=3$ ，图1展示了请求节点到达率λ、最大休假节点数d与阈值N对第一阶段请求节点平均队长$E\left(L_1\right)$ 的影响情况。从图像变化趋势来看，固定d，N和λ中的两个参数，$E\left(L_1\right)$ 会随第三个参数的变化而变化，具体地，$E\left(L_1\right)$ 随着λ的增大而增大，随d的增大而增大，随N的增大而增大，主要是因为第一阶段缓冲区容量为无穷，且服务节点的服务速率不变，到达系统的资源请求节点数越多，平均队长越大；当d增大时，处于工作状态的节点数会相对减少，则完成服务的请求节点数减少，平均队长增加；N增大意味着缓冲区等待的请求节点数大于等于N时，休假的节点才能返回系统开始工作，则处于工作状态的服务节点数较少，平均队长增加。因此可以通过减少最大休假节点数和降低阈值来减少平均队长，缓解系统的拥塞现象。

Figure 1. Relationship between $\lambda ,d,N$ and $E\left(L_1\right)$

图1. $E\left(L_1\right)$ 与$\lambda ,d$ 和N的关系

Figure 2. Relationship between $\lambda ,d,{\mu }_1$ and G

图2. G与$\lambda ,d$ 和${\mu }_1$ 的关系

假设${\mu }_2=5,y_1=1,y_2=2,y_4=2$ ，图2描述了系统总能耗G与请求节点到达率λ、最大休假节点数d和第一阶段节点服务率${\mu }_1$ 之间的关系。固定$\lambda ,d$ 和${\mu }_1$ 中的两个参数不变时，G会随第三个参数的变化而变化，具体地，G随着λ的增大而增大，随d的增大而减小，随${\mu }_1$ 的增大而减小，主要是因为当λ增大时，系统中请求节点数增多，服务节点转变为工作状态，工作状态的平均能耗较大，所以G增大；当d增大时，系统中处于空闲状态的服务节点减少，且节点空闲状态的平均能耗大于休假状态的能耗，所以G减小；当${\mu }_1$ 增大时，系统中请求节点更快地完成资源传输，服务节点处于工作状态的时间缩短，更容易进入空闲状态或休假状态，且节点工作状态的能耗较大，所以G降低。因此可以采用提高节点服务率或适当增加最大休假节点数的方法来减少系统的总能耗。

4.2. 个人最优和社会最优策略

在完全不可见排队系统中，请求节点不清楚缓冲区内的队列长度，也不清楚服务节点休假的个数，则请求节点在决定是否进入系统过程中存在一种博弈行为，因此可以通过研究请求节点的到达率与个人效益之间的纳什均衡来为节点是否进入系统提供依据，避免系统产生不必要的能耗。假设单个请求节点进入系统接受服务所需的接入成本为h，在服务过程中单位延迟时间产生的成本为f，服务完成后获得的回报为r，因此定义请求节点的个人效益函数为

$U_1=r-fE\left(W\right)-h$

令$c=8,K=12,\xi =1.5,p=0.7,r=15,f=12,h=5,{\mu }_1=4,{\mu }_2=5,N=12,d=6$ ，图3展示了当第一阶段服务节点休假参数θ取值不同时，请求节点的个人效益$U_1$ 随到达率λ的变化趋势。由图像可知，当θ不变时，$U_1$ 随λ的增大先减小又增大再减小，这种现象主要是因为当λ增大但缓冲区节点数没达到阈值N时，系统中请求节点可能因为服务节点在线数少而产生平均延迟，所以$U_1$ 减小；当λ继续增大，系统中休假的节点返回系统进入工作状态，节点在系统中平均延迟减小，所以$U_1$ 呈短暂上升趋势；当λ继续增大且服务节点完全处于工作状态，随着系统中请求节点数增多，导致平均延迟增大，最终$U_1$ 呈下降趋势。当λ不变时，$U_1$ 随θ的增大而增大，主要是因为当θ增大时，节点处于休假状态的平均时间减小，更容易进入工作状态，由此造成的平均延迟减小，所以个人效益增加。

Figure 3. Relationship between $\lambda ,\theta$ and $U_1$

图3. $\lambda ,\theta$ 与$U_1$ 的关系

为了研究社会最优策略，假设所有请求节点的个人效益函数都是相同可加的，并且请求节点的接入成本只是在节点之间转移，并不影响系统的社会效用，假设系统内单位能耗带来的损失为$f_1$ ，因此在不考虑其他费用的情况下，定义系统的社会效用函数为

$U_2=\lambda \left(r-fE\left(W\right)\right)-f_{1}G$ .

假设$d=4,{\mu }_2=4,N=9,\theta =1.5,f_1=3$ ，图4反映了系统的社会效用$U_2$ 随到达率λ和第一阶段节点服务率${\mu }_1$ 的变化趋势。当λ不变时，随着${\mu }_1$ 的增加，系统单位时间内完成服务的节点数增加，由此造成的平均延迟减少，且社会效用是到达率的单调增函数，是平均延迟的单调减函数，所以$U_2$ 增加；当${\mu }_1$ 不变时，随着λ的增加，社会效用曲线呈上升趋势，主要是因为到达率整体水平较低时，到达系统的节点数越多，则获得回报的节点数越多，产生的社会效用增加。在上述条件下，社会效用取最大$U_2=27.9288$ 时，第一阶段最优到达率和最优服务率分别是$\lambda =6,{\mu }_1=4$ 。

Figure 4. Relationship between$\lambda ,{\mu }_1$ and$U_2$

图4. $U_2$ 与$\lambda ,{\mu }_1$ 的关系

5. 结论

本文针对P2P网络中节点频繁启动以及不必要在线产生的能耗问题，利用排队理论对混合多层P2P网络进行建模，根据实际网络运行机制将资源请求过程抽象为两阶段服务模型，并且引入部分节点异步多重休假策略，建立了具有不耐烦顾客和N-策略的两阶段M/M/c排队模型，利用拟生灭过程和矩阵几何解方法对构造的完全不可视排队模型进行稳态分析，给出了节点平均队长和系统总能耗等性能指标的表达式，最后构造节点的个人效益函数，并利用最优化理论给出社会最优策略，得到相应的最优到达率和最优服务率。实验结果表明，提高节点服务率或适当增加最大休假节点数可减少系统的总能耗，从而保障社会效用。