21 世纪, 人类已经进入了信息化的时代, P2P 网络的应用已经遍布在社会活动和生产生活的各个领域当中. 王学龙和张璟^[1]对 P2P 网络中各类关键技术进行分析研究, 如网络中的安全问题、资源搜索等技术, 分析了各类技术的研究现状等. 贺文华等^[2]分析了 P2P 网络的特点及主要应用, 与传统网络节点在资源分散、拓扑结构等方面进行了比较, 最后分析了 P2P 网络的安全问题及面临的挑战. 穆筝等^[3]对高速网络下 P2P 网络的流量进行了识别和研究, 主要研究了 P2P 流量的二元分类法, 其可以准确高效的对网络中的流量进行识别. 由于离散时间排队有着非常广泛的应用背景, 许多学者对其进行研究并取得了大量的成果. Tian 等^[4]研究了多重工作休假的离散时间 Geom/Geom/1 排队, 利用拟生灭链和矩阵几何解的方法, 给出了系统队长、顾客等待时间的分布及其随机分解结构, 得到附加队长和附加延迟的分布. Wang 和 Zhang^[5] 考虑了一个离散时间单服务台重试排队, 服务台可能出现故障和进行维修, 分析该排队系统的嵌入 Markov 链, 得到其遍历条件, 推导出重试轨道和系统内顾客数的概率母函数, 以及服务台空闲、繁忙或故障时轨道队长的边际分布. 陈佩树等^[6]研究了有 Bernoulli 休假和可选服务的 Geo/G/1 重试排队.

在一些排队系统中, 如果到达的顾客不能立即得到服务, 顾客就会离开服务区, 进入重试轨道等待接受服务, 这就是排队中的重试现象. 重试排队已经被广泛应用于模拟计算机系统和电信网络中的许多实际问题. 在排队系统中经常会遇到服务台休假的问题, 在排队系统中引入各种休假策略可以更好的模拟现实生活中遇到的问题. Li 等^[7]考虑了一个有工作休假和休假中断的 Geo/Geo/1 重试排队, 推导出了模型的稳定条件, 使用矩阵分析方法得到了稳态概率分布和系统的一些性能指标. Yang 等^[8]考虑了一个有固定重试率和 J 可选休假的单服务台重试排队, 使用补充变量法得到系统队长分布的概率母函数, 得到一系列系统性能指标和两个可靠性指标. Arivudainambi 等^[9]研究了一个有工作休假的单服务台重试排队系统, 得到了服务台状态的稳态分布和一些性能指标. 薛红和唐应辉^[10]利用补充变量法和母函数法分析了有 Bernoulli 休假和负顾客到达的 Geo/G/1 重试排队并通过数值实例讨论不同参数对系统性能的影响. Manoharan 和 Sankarasasi^[11] 考虑了一个带二次可选服务和二次可选休假的 M/G/1 违约排队模型并给出了该模型的几种特殊情况. 蔡梨等^[12]考虑了一个有二次可选休假和一般重试时间的 Geo/G/1 离散时间重试排队模型.

在我们的实际生活当中, 具有优先权、不耐烦顾客的排队现象普遍存在. Wu 等^[13]考虑了一个 Geo/G/1 重试排队, 给出了它的遍历条件, 得到系统的稳态分布和系统队长. Drekic 和 Woolford ^[14] 研究了一个有两类顾客的单服务台抢占优先权排队模型, 考虑了两种特定形式下的不耐烦行为, 通过广义特征值的方法推导系统中两种优先级顾客数的稳态联合分布. Rajadurai ^[15] 对有 Bernoulli 工作休假的单服务台优先权重试排队进行了稳态分析. Manoharan 和 Jeeva ^[16] 研究了有等待服务台和启动时间的 M/M/1 工作休假排队中的不耐烦顾客, 运用母函数法, 得到了稳态下系统的一系列关键性能指标. Lan 和 Tang ^[17] 研究了有优先权和不耐烦顾客的不可靠 Geo/G/1 重试排队系统, 利用补充变量法和母函数法, 推导出重试轨道和系统中顾客数的母函数以及稳态下系统的一些关键性能指标.

现已有较多文献将 P2P 网络与各种排队模型相结合. 闫苗等^[18]根据 P2P 网络系统, 结合 N 抢占优先权、不耐烦和延迟启动策略, 构建了一个服务台数量可变的 M/M/c 排队. 根据非结构化 P2P 网络建立排队模型来分析具体资源提供的搜索、传输服务能力等. Wang 等^[19]将服务节点引入工作休眠机制, 以及负顾客和反馈策略, 建立了一个工作休假和故障可修的排队模型, 来模拟 P2P 的文件传输过程. Si 等^[20]将带有服务器动态变化、客户不耐烦、故障可修的 M/M/c 排队模型与 P2P 网络结合进行分析, 达到提高系统性能和避免拥塞的目的.

关于二次可选休假排队的研究较少, 本文将 P2P 网络中节点的动态变化抽象为排队模型, 将 P2P 网络中的请求节点和服务节点分别比作排队模型中的顾客和服务器, 把二次可选休假策略、优先权和不耐烦请求节点引入到离散时间 Geo/G/1 重试排队系统中, 建立排队模型. 利用嵌入 Markov 链的方法, 构造相应维数的 Markov 链, 利用补充变量法推导系统演化的平衡方程组, 求解得到该系统的一系列性能指标, 最后通过具体的数值例子讨论参数的变化对系统性能指标的影响.

本文将 P2P 网络与排队论进行结合分析, 将 P2P 网络中请求节点比作排队论中的顾客, 将服务节点比作服务台, 将 P2P 网络的动态变化比作排队模型中的服务过程. 此外, 本文考虑一个单服务节点的早到系统, 假设时间轴被分割为等长的时隙, 被标记为 $0,1,2\cdots$. 假设请求节点到达、服务节点休假开始和请求节点重试都发生在时隙 $(m,{{m}^{+}})$ 处, 请求节点离开和服务节点休假结束都发生在时隙 $({{m}^{-}},m)$ 处. $m=1,2,\cdots$. 模型的具体假设如下

(1) 请求节点的到达间隔服从参数为 $p(0<p<1,\bar{p}=1-p)$ 的几何分布, 服务节点前没有等待位置, 因此, (a) 若请求节点到达系统时发现服务节点空闲则立即接受服务, (b) 若请求节点到达系统时发现服务节点休假, 那么请求节点以概率 $q(0\le q\le 1)$ 进入重试轨道等待再次接受服务, 假设只允许重试轨道队首的请求节点进行重试, 重试时间服从一般分布, 分布列为 $\left\{ {{a}_{i}},i\ge 0 \right\}$, 其母函数为 $A(z)=\sum\limits_{i=0}^{\infty }{{{a}_{i}}}{{z}^{i}}$; 或者以概率 $\bar{q}\text{=}1-q$ 离开系统. (c) 若请求节点到达系统时发现服务节点处于工作状态, 那么请求节点以概率 $q(0\le q\le 1)$ 进入系统, 同时进入系统的请求节点或以概率 $\alpha (0\le \alpha \le 1)$ 抢占服务, 或以概率 $\bar{\alpha }=1-\alpha$ 进入重试轨道, 由于抢占终止服务的请求节点则需要返回重试轨道等待重新接受服务; 或者以概率 $\bar{q}\text{=}1-q$ 离开系统.

(2) 服务节点的服务时间独立同分布, 服从一般分布, 分布列为 $\left\{ {{s}_{i}},i\ge 1 \right\}$, 其母函数为 $S(z)=\sum\limits_{i=1}^{\infty }{{{s}_{i}}{{z}^{i}}}$. 当服务节点完成一次服务之后, 系统中若无请求节点, 服务节点就会进行第一次休假. 当第一次休假结束之后, 服务节点将以概率 $\eta (0\le \eta \le 1)$ 进行第二次休假, 或者以概率 $\bar{\eta }\text{=}1-\eta$ 处于等待服务状态, 有请求节点等待就开始为其服务, 没有请求节点等待就处于空闲状态. 当第二次休假结束之后, 服务节点就处于等待服务状态. 两次休假时间都服从一般分布, 其分布列分别为 $\left\{ {{v}_{1,i}},i\ge 1 \right\}$, $\left\{ {{v}_{2,i}},i\ge 1 \right\}$, 其母函数分别为 ${{V}_{1}}(z)=\sum\limits_{i=1}^{\infty }{{{v}_{1,i}}}{{z}^{i}}$, ${{V}_{2}}(z)=\sum\limits_{i=1}^{\infty }{{{v}_{2,i}}}{{z}^{i}}$, 其 $n$ 阶矩分别为 ${{V}_{1,n}}$, ${{V}_{2,n}}$, $n\ge 1$.

(3) 假设到达过程、服务过程、重试过程和两次休假过程都是相互独立的, 且按先到先服务顺序.

在时刻 ${{m}^{+}}$ 处, 系统的状态可由 Markov 过程 $\{({{C}_{m}},{{\xi }_{m}},{{N}_{m}}),m\ge 1\}$ 来表示, ${{C}_{m}}$ 表示服务节点的状态, ${{C}_{m}}$ 取 0、1、2、3 分别表示服务节点处于空闲、工作、第一次休假和第二次休假状态, ${{N}_{m}}$ 表示服务完成时重试轨道中的请求节点数 $({{N}_{m}}\ge 0)$, ${{\xi }_{m}}$ 表示服务完成时某个随机剩余寿命 $({{\xi }_{m}}\ge 0)$. 具体地, 若 ${{C}_{m}}=0$, ${{N}_{m}}>0$, ${{\xi }_{m}}$ 表示剩余重试时间; 若 ${{C}_{m}}=1$, ${{N}_{m}}\ge 0$, ${{\xi }_{m}}$ 表示剩余服务时间; 若 ${{C}_{m}}=2$, ${{N}_{m}}\ge 0$, ${{\xi }_{m}}$ 表示剩余第一次休假时间; 若 ${{C}_{m}}=3$, ${{N}_{m}}\ge 0$, ${{\xi }_{m}}$ 表示剩余第二次休假时间. 过程 $\{({{C}_{m}},{{\xi }_{m}},{{N}_{m}}),m\ge 1\}$ 是嵌入 Markov 链, 其状态空间为

假设 Markov 链 $\{({{C}_{m}},{{\xi }_{m}},{{N}_{m}}),m\ge 1\}$ 的平稳分布如下

令 ${{P}_{\left( h,f,g \right)\left( i,j,k \right)}}=P\left\{ {{N}_{m+1}}=i,{{\xi }_{m+1}}=j,{{C}_{m+1}}=k|{{N}_{m}}=h,{{\xi }_{m}}=f,{{C}_{m}}=g \right\}$ 表示 Markov 链的一步转移概率, 则具体表达式如下

如: 当 $i=0,\quad j=0,\quad k=0$ 时

以此类推 ${{P}_{\left( h,f,g \right)\left( i,j,k \right)}}$ 都有其对应的一步转移概率.

根据平稳分布条件 ${\pi }{P}={\pi }$, 其平稳状态下的 Kolmogorov 方程组为

其中 ${{\delta }_{0,k}}$ 是 Kronecker 记号 (即 ${{\delta }_{0,0}}=1$; 当 $k\neq0$ 时, ${{\delta }_{0,k}}$=0), 并且归一化条件为

为求解方程 (3.1)-(3.5) 式, 引入部分母函数

${{\varphi }_{0,i}}(z)=\sum\limits_{k=1}^{\infty }{{{\pi }_{0,i,k}}}{{z}^{k}},i\ge 1,$${{\varphi }_{j,i}}(z)=\sum\limits_{k=0}^{\infty }{{{\pi }_{j,i,k}}}{{z}^{k}},i\ge 1,j=1,2,3,$

${{\varphi }_{0}}(x,z)=\sum\limits_{i=1}^{\infty }{\sum\limits_{k=1}^{\infty }{{{\pi }_{0,i,k}}}{{x}^{i}}}{{z}^{k}},$${{\varphi }_{j}}(x,z)=\sum\limits_{i=1}^{\infty }{\sum\limits_{k=0}^{\infty }{{{\pi }_{j,i,k}}}{{x}^{i}}}{{z}^{k}},j=1,2,3.$

通过求解以上方程组, 系统稳态分布的概率母函数被推导出来, 具体的解析表达式由以下的定理给出.

定理3.1 若 $1-pq\alpha <(\alpha \bar{p}A(\bar{p})+1)S(1-pq\alpha )$, 则 Markov 链 $\{({{C}_{m}},{{\xi }_{m}},{{N}_{m}}),m\ge 1\}$ 存在稳态分布, 其母函数为

其中

证 将 (3.4)-(3.5) 式两边同乘 ${{z}^{k}}{{x}^{i}}$, 然后对 $k$, $i$ 求和, 结合 (3.1) 式, 并代换得

对 ${{\varphi }_{2}}\left( x,z \right)$, ${{\varphi }_{3}}\left( x,z \right)$ 中的变量 $x$ 求偏导, 令 $x=0$, $z=0$, 结合 (3.1) 式, 可得

将 (3.2) 式两边同乘 ${{z}^{k}}{{x}^{i}}$, 然后对 $k$, $i$ 求和, 可得

在 (3.9) 式中令 $x=1$, 将 (3.3) 式两边同乘 ${{z}^{k}}{{x}^{i}}$, 对 $k$, $i$ 求和, 可得

在 (3.9) 式中令 $x=\bar{p}$, (3.10) 式中令 $x=1-pq+pq\bar{\alpha }z$, 可得

将 (3.11)-(3.12) 式代入 (3.9)-(3.10) 式中, 将 (3.8) 式代入 (3.6)-(3.7) 式中, 再利用归一化条件确定常数 ${{\pi }_{0,0,0}}$, 从而定理得证.

基于以上定理, 可以得到下面的结论

(1) 当服务节点空闲时, 重试轨道中请求节点数的概率母函数为

(2) 当服务节点工作时, 重试轨道中请求节点数的概率母函数为

(3) 当服务节点休假时, 重试轨道中请求节点数的概率母函数为

(4) 重试轨道中请求节点数 (用随机变量 ${{L}_{O}}$ 表示) 的概率母函数为

(5) 系统中请求节点数 (用随机变量 ${{L}_{S}}$ 表示) 的概率母函数为

其中, $H(z)=(1-z)\bar{p}(1-pq+pqz)B(0)W(z)$.

(1) 服务节点空闲且重试轨道无请求节点的概率为

(2) 服务节点工作的概率为

(3) 服务节点第一次休假的概率为

(4) 服务节点第二次休假的概率为

(5) 顾客在系统中的平均逗留时间为

其中

在这一部分, 用一些数值实例来说明不同的参数对一些系统性能指标的影响. 假设服务时间服从参数为 0.7 的几何分布, 即 $S(z)=\frac{7z}{10-3z}$, 第一次休假时间和第二次休假时间分别服从参数为 0.4 和 0.6 的几何分布, 即 ${{V}_{1}}(z)\text{=}\frac{2z}{5-3z}$, ${{V}_{2}}(z)\text{=}\frac{3z}{5-2z}$, 重试时间服从几何分布, 其母函数为 $A(z)=\frac{{{a}_{0}}}{1-(1-{{a}_{0}})z}$, 系统性能指标随参数变化趋势图见图 1-4.

图 1 描述的是当 $q=0.3$, ${{a}_{0}}=0.1$, $\alpha =0.1$ 时, 服务节点空闲且重试轨道无请求节点的概率 ${{\pi }_{0,0,0}}$ 与二次可选休假概率 $\eta$ 和请求节点的到达参数 $p$ 之间的关系. 从图形可以发现, 当 $p$ 固定时, ${{\pi }_{0,0,0}}$ 随着 $\eta$ 的增大而减小, 随着 $\eta$ 的增大, 服务节点以更大的概率进行第二次休假, 同时重试轨道上的请求节点会逐渐增多, 这会导致 ${{\pi }_{0,0,0}}$ 减小. 当 $\eta$ 固定时, ${{\pi }_{0,0,0}}$ 随着 $p$ 的增大而减小, 随着 $p$ 的增大, 到达系统的请求节点逐渐增多, 所以 ${{\pi }_{0,0,0}}$ 逐渐减小.

图 2 描述的是当 $p=0.1$, $q=0.3$, $\eta =0.3$ 时, 服务节点空闲且重试轨道无请求节点的概率 ${{\pi }_{0,0,0}}$ 与优先权概率 $\alpha$ 和重试参数 ${{a}_{0}}$ 之间的关系. 从图形可以发现, 当 ${{a}_{0}}$ 固定时, ${{\pi }_{0,0,0}}$ 不受优先权概率 $\alpha$ 变化的影响, 随着 $\alpha$ 的不断增大, 曲线并没有什么变化趋势, 即优先权概率 $\alpha$ 不影响 ${{\pi }_{0,0,0}}$. 当 $\alpha$ 固定时, ${{\pi }_{0,0,0}}$ 随着 ${{a}_{0}}$ 的增大而增大, 当 ${{a}_{0}}$ 增大时, 请求节点重试的概率会增加, 所以重试轨道中的请求节点会变少, 所以 ${{\pi }_{0,0,0}}$ 增大.

图 3 描述的是当 $\alpha =0.1$, ${{a}_{0}}=0.1$, $\eta \text{=}0.3$ 时, 服务节点工作的概率 ${{\varphi }_{1}}(1,1)$ 与不耐烦概率 $q$ 和到达参数 $p$ 之间的关系. 从图形可以发现, 当 $p$ 固定时, ${{\varphi }_{1}}(1,1)$ 随着 $q$ 的增大而增大, 随着 $q$ 的增大, 到达系统的请求节点发现服务节点不可用时进入系统的概率增大, 所以 ${{\varphi }_{1}}(1,1)$ 增大. 当 $q$ 固定时, ${{\varphi }_{1}}(1,1)$ 随着 $p$ 的增大而增大, 随着 $p$ 的增大, 到达系统的请求节点增多, 所以 ${{\varphi }_{1}}(1,1)$ 增大.

图 4 描述的是当 $p=0.1$, $q=0.3$, $\eta =0.3$ 时, 服务节点第一次休假的概率 ${{\varphi }_{2}}(1,1)$ 与优先权概率 $\alpha$ 和重试参数 ${{a}_{0}}$ 之间的关系. 从图形可以发现, 当 ${{a}_{0}}$ 固定时, ${{\varphi }_{2}}(1,1)$ 不随 $\alpha$ 的变化而变化, 也就是说, ${{\varphi }_{2}}(1,1)$ 与优先权概率 $\alpha$ 没有关系. 当 $\alpha$ 固定时, ${{\varphi }_{2}}(1,1)$ 随着 ${{a}_{0}}$ 的增大而增大, 当 ${{a}_{0}}$ 增大时, 请求节点重试的概率增大, 重试轨道中的请求节点变少, 系统中没有请求节点的概率变大, 由于当服务节点完成一次服务之后, 系统中如果没有请求节点, 服务节点会进行第一次休假, 所以, ${{\varphi }_{2}}(1,1)$ 会增大.

假设请求节点完成服务获取收益为 ${{f}_{1}}$, 请求节点在系统内平均逗留时间的单位等待费用为 ${{G}_{1}}$, 每个进入系统的节点需要支付的费用为 ${{f}_{2}}$. 则请求节点的个人收益函数为

假设服务时间服从参数为 0.7 的几何分布, 第一次休假时间和第二次休假时间分别服从参数为 0.4 和 0.6 的几何分布, 重试时间服从几何分布, 其母函数为 $A(z)=\frac{{{a}_{0}}}{1-(1-{{a}_{0}})z}$. 图 5 描述的是当 $q=0.3$, ${{a}_{0}}=0.1$, $\alpha =0.1$, ${{f}_{1}}=9$, ${{f}_{2}}=2$, ${{G}_{1}}=1$ 时, 请求节点的个人收益 ${{U }_{L}}$ 与二次可选休假概率 $\eta$ 和到达参数 $p$ 之间的关系. 从图形可以发现, 当 $p$ 固定时, ${{U }_{L}}$ 随着 $\eta$ 的增大而减小, 随着 $\eta$ 的增大, 服务节点以更大的概率进行第二次休假, 同时会有更多的请求节点进入轨道中等待接受服务, 请求节点在系统中的平均逗留时间变长, 所以 ${{U }_{L}}$ 会减小. 当 $\eta$ 固定时, ${{U }_{L}}$ 随着 $p$ 的增大而减小, 随着 $p$ 的增大, 系统中请求节点的平均逗留时间变大, 所以 ${{U }_{L}}$ 减小.

为分析 P2P 网络中请求节点的不同到达过程及服务节点的服务情况, 本文将 P2P 网络和排队论进行结合分析, 建立了基于 Geo/G/1 排队模型, 研究带二次可选休假、优先权和不耐烦请求节点的 Geo/G/1 重试排队模型. 利用嵌入 Markov 链的方法, 构造相应维数的 Markov 链, 再利用补充变量法求解得到该模型重试轨道和系统中请求节点数的概率母函数, 进而得到该系统的一系列性能指标如服务台处于各个状态的概率等, 通过分析一些具体的数值例子, 进一步研究不同的参数变化对系统性能指标的影响.