1. 引言
P2P现已成为大型通讯系统中不可缺少的技术,因其去中心化的理念,满足了用户日益增长的对下载速率和流媒体质量的要求,在分布式计算、多媒体、协同工作等方面有卓越优势,让服务器之间实现自动负载均衡 [1] 。在P2P网络中,每个节点地位对等,兼备服务器和客户端双重身份,既能请求网络服务又能对请求做出响应,使得互联网通信由传统的C/S结构向分布式P2P结构迈进,不同计算机用户之间可以不经过中继设备直接交换数据或服务 [2] [3] [4] 。P2P的流行伴随着较大的能耗问题和服务节点故障问题,导致用户在进行资源文件下载或使用时感到不便,对P2P网络安全产生了不良影响,优化和完善P2P网络系统是现在互联网亟待解决的任务。
近年来,P2P网络因其去中心化、高性能、拓展性强等优点受到广泛关注。李纲等 [5] 将流媒体与P2P技术相结合,讨论了在P2P环境下的流媒体多点分布式调度技术和调度性能分析,以及多点调度下的带宽分配算法,最后给出了一个基于P2P点组的流媒体协作调度模型。Michela M和Fabio M [6] 引入Qos概念,研究了P2P文件共享应用程序节点上的内容管理策略。贺文华等 [7] 指出了P2P网络应用于分布式计算、协同工作、多媒体的强大优势,分析了构建安全对等网络的必要性。Masahiro S [8] 采用线性程序作为工具,分析了任意上传容量分布下基于TFT的P2P文件分发的最小分发时间,揭示了基于TFT的P2P文件分布的基本特征。Yin等 [9] 详细介绍了媒体分发网络系统设计,建立用于描述系统中对等节点相互作用的动态模型,提出了对等体选择策略和带宽分配策略。Huo等 [10] 在认知无线电网络的研究中,提出了一种新的双速率传输节能策略,在收益支出结构的基础上,建立了收益函数,研究了纳什均衡策略和社会最优策略。Lua等 [11] 研究并分析了结构化和非结构化P2P覆盖网络,利用对比调查的方法讨论了各自的应用级网络性能。Lehrieder等 [12] 开发了一个流体模型,动态地捕捉了缓存对P2P网络系统的影响,并表明缓存会根据系统参数对系统动态产生不利影响。
上述大多数文献从P2P网络的排队论模型、性能分析方法和优化控制策略等方面进行研究,排队论和P2P网络可以结合来优化P2P网络系统中的资源利用和数据传输效率。具体而言,在P2P网络中,节点之间通过传输队列共享资源。队列管理可以优化数据传输的顺序和速度,从而提高整个P2P网络的性能。通过排队论的流控制理论,可以限制P2P网络中节点之间的数据传输速率,防止网络拥塞和资源浪费,从而提高数据传输的稳定性和可靠性。排队论的负载均衡理论也可以应用于P2P网络中,通过动态调整节点之间的资源分配,使得整个网络的资源利用更加均衡,从而提高整个网络的效率和性能。通过排队论的优化模型,可以对P2P网络中的节点进行评估和选择,选择最优节点进行数据传输,从而提高传输速度和可靠性。
综上所述,排队论和P2P网络结合可以优化P2P网络的性能,提高数据传输的效率和可靠性。本文为应对P2P网络中任务太繁重而导致节点出现一些故障不能正常工作的问题,有如下三方面贡献:
1) 针对现实混合P2P网络中服务节点会出现故障的问题,引入服务节点故障可修,并且考虑系统中节点非必要的能耗浪费,引入节点同步工作休假策略来降低系统能耗,将服务节点的工作休眠过程抽象成工作休假过程,将资源正常传输过程抽象成正常忙期,将网络中一些恶意节点等不安全因素抽象成负顾客,同时为更加贴合实际引入启动期和关闭期应用于混合P2P网络中,使得模型与混合P2P网络实际情况更加吻合。
2) 建立了带有恶意节点、启动期、关闭期、工作休假的故障可修的M/M/c排队模型,对混合P2P网络进行建模,对服务节点各种状态的能耗进行量化分析,利用拟生灭过程和矩阵几何解法求解排队模型的稳态分布,给出系统能耗等性能指标的表达式,并通过数值实验研究系统性能,以此提高P2P网络中资源请求数据的效率和P2P网络系统的安全性能。
3) 研究请求节点的到达率和收益之间的纳什均衡,以避免过量请求节点向系统发出非必要的服务请求而引起系统能耗的增加。通过社会最优策略,得到社会收益的最优值,为P2P系统提高网络安全性能和降低节点在线能耗提供理论基础和决策评估。
本文的其余部分组织如下。第2节介绍了混合P2P网络的原理图和运行机制。在第3节中,使用三维马尔可夫链推导稳态概率向量。第4节通过数值实验研究了混合P2P网络的性能指标,并通过纳什均衡策略和社会最优策略分析了个人效益和社会效益的优化。结论在第5节。
2. 混合P2P网络与建模
2.1. 混合P2P网络
混合P2P网络(Hybrid Peer-to-Peer Network)是一种结合了中心化P2P网络和去中心化P2P网络的混合网络模型,是在局部上呈现集中式的体系构架,由不同的簇构成,每个簇中包含一个超级节点(Super Node, SN)和若干个具有相同服务资源的普通节点(Ordinary Node, ON),节点分为两类:超级节点和普通节点。超级节点是具有高带宽、高性能的节点,它们充当中心化P2P网络的服务器,负责在本区域内响应资源查找请求和转发资源以及收集普通节点的资源信息,负责维护整个网络的拓扑结构,路由和索引服务,同时超级节点还要维护和更新本区域普通节点的信息以及与其他区域的超级节点建立连接。普通节点则充当去中心化P2P网络的客户端,存储自身节点的资源信息和区域信息,它们连接到超级节点并共享和获取资源,作为服务节点接收请求节点的数据请求,建立对等连接后进行数据传输,具体表现为当P2P网络系统接收到请求节点的请求后,首先通过超级节点在区域内查询,如果搜索区域内存在所需的请求资源,请求节点则在该区域内接收数据传输;如果搜索区域内不存在所需的请求资源,请求节点则进行跨区域查询,通过超级节点的资源转发和查询,查找区域外存在该请求资源的信息,请求节点在查询具有所需请求资源的节点后进入文件传输阶段。
混合P2P网络结合了中心化P2P网络和去中心化P2P网络的优点。与纯去中心化P2P网络相比,混合P2P网络能够更好地控制和管理网络结构,提高网络的可靠性和性能。与纯中心化P2P网络相比,混合P2P网络具有更好的可扩展性和抗攻击性。在混合P2P网络中,超级节点可以动态地添加或删除,从而使网络能够更好地适应不同的网络环境和负载。混合P2P网络在许多应用场景中得到了广泛的应用,例如文件共享、内容分发、视频流媒体等。在一些大规模的视频流媒体应用中,混合P2P网络可以通过超级节点提供高效的流媒体服务,并利用普通节点来共享流媒体内容,从而提高整个网络的性能和可靠性。
2.2. 模型描述
在混合P2P网络中,文件传输过程可以抽象为节点请求服务的排队问题,根据节点的功能可以将节点分为服务节点和请求节点,服务节点接受资源请求节点的数据请求,建立对等连接后进行数据传输。为了减少能耗,建立一个带有恶意节点、启动期和关闭期、故障可修以及工作休假的排队机制,其模型描述及系统参数如下。
1) 在P2P网络中,把需要接受数据传输服务的请求节点看作正顾客,外来的干扰信号或者阻止系统正常工作的不安全因素等恶意节点看作负顾客,请求节点、恶意节点到达均为泊松到达,到达率分别为
和
。在RCE (Removal the Customers at the End)抵消策略下,到达的恶意节点一对一抵消队尾的请求节点(若有,不管该请求节点是在等待还是在被服务),若系统中无请求节点,恶意节点自动消失。
2) 为了降低网络系统的在线能耗,提高网络系统的安全稳定性,在系统中引入同步多重工作休假策略,当服务系统中无资源请求节点时,系统将关闭,关闭时间D服从参数为
的负指数分布。(i) 如果请求节点在关闭期到达,则系统立即进入正规忙期,服务时间服从参数为的负指数分布。(ii) 如果关闭期没有请求节点到达,则服务节点在关闭期结束时开始一个随机长度为V的工作休假,休假时间V服从参数为的负指数分布,在工作休假期内服务节点以较低的服务率对请求节点进行服务,服务时间服从参数为的负指数分布。若一次工作休眠结束后,系统仍无资源请求节点,服务节点则继续一个独立同分布的工作休眠,若一次工作休眠结束后,系统中有资源请求节点,进入启动期,系统有启动延迟,请求节点不能立即用于服务,系统必须经过一个缓冲预热期,定义为启动期。启动时间U服从参数为的负指数分布。服务节点在启动期后进入正规忙期,重复上述过程。
3) 服务节点在工作期间可能发生故障,并且故障可修,所有节点可能因为请求下载的任务太繁重,从而造成拥塞、卡顿等故障,故障过程服从参数为的泊松过程。如果正在工作的节点发生故障,则立即修理,同一节点只能被一个修理工维修,修复时间服从参数为的指数分布,一旦服务节点发生故障,修理工马上修理故障节点,假设修理工的数量是无限的。
4) 服务遵循FCFS (First-Come-First-Served)排队规则,并且假设请求服务节点到达间隔、服务节点故障时间、修理工维修时间、服务节点启动时间、关闭时间、服务节点服务时间和工作休假时间相互独立。混合P2P网络节点服务运行机制如图1所示,服务节点状态切换如图2所示。
Figure 1. Operation mechanism of the node service
图1. 节点服务运行机制图
Figure 2. Status transition of service node
图2. 服务节点状态切换图
3. 带恶意节点的P2P系统模型分析
3.1. 模型假设
图3. 状态转移图
表示时刻t请求节点数,
表示时刻t提供服务的节点故障数,
表示时刻t服务节点的状态,具体如下:
则
是一个以
为状态空间的三维Markov过程,状态空间
如下:
(1)
其中
称
为0水平,
为i水平,当所有服务节点均故障时,服务系统进入故障状态(
)。
排队模型的状态转移如图3所示。
将状态按字典序进行排列,系统的状态转移率矩阵可以写成如下形式:
其中
分别表示对应水平间的状态转移率,并令
。具体矩阵如下:
阶矩阵
为
其中,
阶矩阵
为
阶矩阵
为
阶矩阵
为
当
时,定义符号
则
阶矩阵
为
当
时,定义符号
阶矩阵
为
3.2. 系统稳态分析
由矩阵
的结构可知,Markov过程
是一个拟生灭过程(Quasi-Birth-and-Deathprocess, QBD)。当Markov过程
正常返时,定义稳态分布如下:
QBD
是正常返的充分必要条件是矩阵方程
存在一个最小非负解
,且谱半径
,
维随机阵如下:
有左零向量,当QBD是正常返时,稳态分布满足下列方程组:
其中
是维数为
且所有元素均为1的列向量,
是维数为
且所有元素均为1的列向量,
是维数为
的单位矩阵。
上述结论分析证明过程运用了矩阵几何解法,由于矩阵
相对复杂,求解上述矩阵方程
的最小非负解
很难显式表示,因此通过Gauss-Seidel迭代法来解决上述难题,从而得到
的数值结果,具体算法如表1所示:
Table 1. Iterative algorithm of rate array R
表1. 率阵R的迭代算法
3.3.性能指标
根据上述分析,利用Little’s公式,得到了系统的各项性能指标。
1) 请求服务节点的平均队长为
2) 请求节点的平均延迟为
3) 系统服务节点处于工作休眠状态的概率为
4) 系统服务节点处于启动期或关闭期状态的概率为
5) 系统服务节点处于正规忙期状态的概率为
6) 系统服务节点全部处于故障状态的概率为
7) 系统服务节点的平均故障数为
系统的单位能耗包括工作忙期状态节点和工作休眠期状态节点的能耗以及服务节点处于启动期或关闭期的能耗,假设
是单个服务节点处于工作休眠期状态的能耗,
是单个服务节点处于启动期或关闭期的能耗,
是单个服务节点处于正规忙期状态的能耗,故障的服务节点没有能耗。
8) 服务节点在工作休眠状态的平均能耗
为
9) 服务节点在启动期或关闭期的平均能耗
为
10) 服务节点在工作忙期状态的平均能耗
为
11) 系统的总能耗为
4. P2P系统数值实验
通过Gauss-Seidel迭代法求解得到矩阵二次方程
的最小非负解
,然后利用稳态分布方程组求解得到
的数值结果,进而可以得到P2P系统的各项性能指标。利用计算机软件编程绘图得到P2P系统性能指标随参数变化的关系图像,进而分析参数变化对性能指标的影响,从而为该P2P系统节能策略提供依据。
4.1. 参数变化对P2P系统性能指标的影响
Figure 4. Relationship between
and
图4.
与
的关系
根据上述理论分析得到了系统的性能指标的表达式,利用数值实验分析系统参数对系统性能指标的影响。假设
,图4中反映了请求节点到达率
和服务节点的服务速率
对系统的平均队长
的影响。我们发现,当另一个参数固定不变时,系统的平均队长
随到达率
的增大而增大,随服务率
的增大而减小。主要原因是当到达率
增大时,单位时间内到达系统的请求节点的数量增多,所以平均队长
增大;当服务率
增大时,意味着单位时间的平均下载量增大,所以请求节点的平均队长
越小。综上,为了减少系统平均队长,需要在一定程度上减小到达率
,增大服务率
。
Figure 5. Relationship between
and
图5.
与
的关系
假设
,图5中反映了服务速率
和到达率
对系统的平均延迟
的影响。我们发现,当另一个参数固定不变时,系统的平均延迟
随服务速率
的增大而减小,随到达率
的增大而增大。主要原因是当服务率增大时,单位时间的平均服务量增大,所以请求节点的平均延迟
越小;当到达率
增大时,意味着单位时间内到达系统的请求节点的数量增多,所以单个请求节点的平均延迟
增大。综上,为了减少系统请求节点的平均延迟
,需要在一定程度上减少到达率
,增大服务率
。
Figure 6. Relationship between
and
图6.
与
的关系
假设
,图6描述了系统服务节点平均故障数
与故障率
和维修率
之间的数值结果。当
为定值时,
随
的增大而减小;当为定值时,
随
的增大而增大。主要原因是当故障率
增大时,系统中服务节点更容易发生故障,所以平均故障数增大;当维修率
增大时,系统中发生故障的服务节点被修好的速率增大,所以平均故障数减小。
Figure 7. Relationship between
and
图7.
与
的关系
假设
,图7反映了工作休眠参数
、服务率
和到达率
对工作休眠状态的平均能耗
的影响。在
和
固定的情况下,工作休眠状态的平均能耗
随工作休眠参数
的增大而减小,在
和
固定的情况下,工作休眠状态的平均能耗
随服务率的增大而增大,在
和
固定的情况下,工作休眠状态的平均能耗
随到达率
的增大而减小。这是因为当工作休眠参数增大时,服务节点的平均工作休眠时间减小,从而工作休眠状态的平均能耗减小;当到达率增大时,请求节点数量增多,服务节点处在工作忙期的时间增加,不易进入工作休眠期,从而工作休眠状态的平均能耗降低;当服务率增大时,系统全部完成服务后进入工作休眠期的速度越快,服务节点的平均工作休眠时间增大,所以工作休眠状态的平均能耗增大。由此我们可以得出结论,为了降低系统节点在工作休眠状态的能耗,可以采取增大工作休眠参数和到达率,减小服务率的方法。
Figure 8. Relationship between
and
图8.
与
的关系
假设
,图8反映了服务率
和到达率
对工作休眠状态的能耗
和工作忙期的能耗
的影响。在服务率固定的情况下,工作休眠期的能耗随到达率的增大而减小,工作忙期的能耗随到达率的增大而增大。在到达率固定的情况下,工作休眠期的能耗随服务率的增大而增大,工作忙期的能耗随服务率的增大而减小。这是因为当到达率增大时,系统处于工作休眠期的平均休眠时间减小,处在工作忙期的平均工作时间增大,使得工作休眠期能耗降低而工作忙期能耗增大。当服务率增大时,服务节点在工作忙期服务速率增大,更容易全部服务完进入工作休眠期,所以工作休眠期的能耗增大,工作忙期的能耗减小。由此我们得出,为了降低工作忙期的能耗,需要减小到达率,并且增大服务率。
Figure 9. Relationship between
and
图9.
与
的关系
假设
,图9中反映了到达率
、工作休眠参数
、工作休眠服务速率
和忙期服务速率
对系统的总能耗
的影响。我们发现,当其他三个参数固定不变时,系统的总能耗随忙期服务率的增大而减小,随到达率的增大而增大,随工作休眠参数的增大而增大,随工作休眠服务速率的增大而减小。这是因为服务节点正规忙期的能耗大于工作休眠期的能耗,所以当服务率增大时,系统更容易服务完全部请求节点从而进入工作休眠期,处于正规忙期状态的时间缩短,所以总能耗减小;当工作休眠参数增大时,平均工作休眠时间减小,处于工作忙期状态的时间增大,所以总能耗增大;当到达率增大时,系统内请求节点数量增多,服务节点处于正规忙期状态的时间增加,所以总能耗也会增大;当工作休眠服务速率增大时,系统工作休眠期可以服务更多的请求节点,工作休眠期的能耗小于正规忙期的能耗,所以总能耗减小。综上,为了降低系统总能耗,需要在一定程度上增大忙期服务率,减小工作休眠参数,减小到达率,增大工作休眠期服务速率。
4.2. 纳什均衡策略
在混合P2P网络中,过量的请求节点向系统发出非必要的服务请求会导致资源浪费,而现实情况下,请求节点对系统内提供下载服务的节点状态及是否存在故障服务节点未知,请求节点无法自发改变策略使自身利益最大化,本节研究请求节点的到达率与单个请求节点个人收益之间的博弈行为,即纳什均衡。
假设
表示每个服务完成的请求节点获得的收益,
表示请求节点在系统中的延迟过程产生的单位等待费用,
表示每个进入系统的请求节点需要支付的费用。定义每个请求节点的个人收益函数为
假设到达系统的请求节点面对完全不可视的排队情形,假设
表示请求服务节点的潜在到达率,
表示均衡策略下请求服务节点进入系统响应的概率,则请求服务节点的均衡策略为
其中
是
的解。
假设
,图10描述了单个请求节点的个人收益
与到达率
和工作休眠参数
之间的关系,当
为定值时,
随
的增大而减小;当
为定值时,
随
的增大而增大。这是因为请求节点不受控制的进入导致系统拥塞,从而导致系统的社会效用降低。而工作休眠参数
的增大意味着结束工作休眠期速度的增大,处在正规忙期的时间增大,服务节点在正规忙期的服务速率大于在工作休眠期的服务速率,故请求服务节点的平均延迟会随着工作休眠参数
的增大而减小,获得的个人效用
增大。
Figure 10. Relationship between
and
图10.
与
的关系
由图10可以看出,无论
取什么值,
,
,
,
,说明只有部分请求节点可以获得正的个人收益,其他请求节点由于在缓冲区等待时间过长而获得负的个人收益。当
时,达到纳什均衡状态,最优到达率
。
4.3. 社会最优策略
为了讨论社会最优策略,假设
是请求节点进入系统响应的最优概率,
为社会最优下的请求节点的实际到达率,并且
。则社会收益函数定义为
假设
,图11描述了社会效益
与到达率
和工作休眠参数
的变化情况。当
取定值时,随着
的增大,
呈现先增大再减小的变化趋势;当
取定值时,
随着
的增大而增大。因此,社会最优下的实际到达率和社会最大效益值存在。如
时,社会效益存在
。主要因为工作休眠参数
越大,服务节点工作休眠结束的速率增大,处在忙期的时间增大,平均延迟越小,社会效益
越大;与此同时,在不可视的排队中,随着到达率
的逐渐增大,越来越多的请求节点进入系统,在系统拥塞前,服务节点数量充裕,处于正规工作状态的服务节点的服务率更快,请求节点的逗留时间更短,因此,社会效用趋于上升。随着请求节点到达率不断提升,当到达率
超过社会最优下的实际到达率
时,请求下载服务的节点越来越多,造成系统的拥塞,其在系统中的平均延迟逐渐增大,导致个人效益
呈下降趋势。综上社会收益呈现先增大后减小的趋势,存在最大社会效益值。
Figure 11. Relationship between
and
图11.
与
的关系
5. 结论
本文为解决节点在线行为导致的不必要的资源浪费问题,引入同步多重工作休假策略来降低请求节点的能耗,在此基础上,实际情况下常伴随环境干扰和系统中阻止正常工作的不安全因素,建立了带有负顾客、启动期、关闭期、工作休假且故障可修的排队模型。利用QBD和矩阵几何解法对系统模型进行了稳态分析,得到了节点平均队长、延迟和能耗等关键性能指标。通过数值分析,分析了参数变化对P2P网络系统性能指标的影响,并对服务节点各种状态的能耗进行量化分析。最后,分析了请求节点到达率和工作休眠参数与单个节点个人收益之间的纳什均衡,进而研究了社会收益最优化。通过观察数值分析结果可知,减少故障率以避免系统拥塞,引入工作休眠机制和适当增大工作休眠参数可以减少系统的平均延迟和系统的能耗,并且可以增加个人和社会效益。