张琦琮，朱立谷

(中国传媒大学 理工学部计算机学院，北京)

1 引言

对等网络具有节点自治性较高，扩展灵活，负载均衡等特点，因而得以在流媒体技术、文件分发、存储共享、传感器通讯等领域应用广泛。但由于网络中自私节点的存在，不可避免地出现“搭便车”现象。还有如文献[1]研究无线传感器网络发现，若传感器节点不积极获取数据并及时传输，会导致系统参与者数量不足，节点间合作程度不高，进而无法提供高质量数据，最终难以保证网络系统有效性。为减少和避免这类现象，采用激励机制以促进节点之间合作和互相提供服务[2]。激励机制如何在提升网络节点合作方面有效发挥作用，国内外学者已经在不同领域进行了广泛的研究。激励机制在群智感知、机会网络和延迟容忍网络等研究方向取得进展，并在计算机与信息共享、带宽与频谱资源分配等应用中得以实现[3，4]。在社交网络、无线传感器网络等开放环境中，激励机制用于评估信誉信任管理的效果[5，6]。如何构建和评价激励机制，事关激励作用能否实现。有学者指出，关于社会网络以及多智能体系统，对网络群体行为实行合理建模分析是研究激励机制的有效手段[7]。文献[8]提出，演化博弈适合作为解决网络环境中动态博弈问题的建模基础。还有学者进一步指出，将数学理论与计算机技术相结合，建立模型研究个体间协同演化与相互作用，进而分析群体演化的动力学机制[9]。这些成果都为深入研究提供了较好的基础。

镜像激励机制是一种广泛采用的激励机制[10]。但对于镜像激励机制，不同学者有不同的认识，如有学者认为只有满足一定的条件，初始状态下无私节点和互惠节点数量比例较高，并拥有较高的激励系数，该机制才能够实现有效激励，系统可以保持合作状态；如果初始时自私节点比例较高，即使激励系数较高的情况下，系统也终将走向崩溃[11]。但有的学者认为该机制根本无法实施有效的激励[12]。因而，对镜像激励机制是否能够有效激励的研究分析就具有了重要意义。本文即基于完全图网络围绕镜像激励机制进行建模和实验仿真研究，探讨不同类型节点初始比例、激励系数与系统节点提供服务程度之间的关系。

2 框架设计与策略描述

一般网络系统中，节点类型分为无私者和自私者两种类型。无私者类型节点，采取无条件提供服务的策略，不论请求服务的节点是何种类型。自私者类型节点，采取不提供任何服务的策略，同样不考虑请求服务的节点是何种类型。所谓镜像激励机制，是指在系统原有两种类型节点的基础上引入第三种类型节点，该类型节点不是无条件采用提供服务或拒绝服务的策略，而是采用一种新的有条件为对方提供服务的策略，称为互惠策略，该类型节点称为互惠者。互惠者的做法如同一面镜子，“你对别人怎么样，我就对你怎么样”。因此该激励机制称之为镜像激励机制。

2.1 模型系统的设计

为便于研究，我们构建的网络框架系统基于以下假设条件：(1)该网络系统是具有一定规模的完全图网络，网络中任意两个节点之间直接相连，彼此可以直接实现数据传输存储等相关服务。(2)该网络是一个封闭的系统，当模型运行开始后不允许系统内节点退出，也不允许系统外节点进入，保证网络规模固定不变。(3)该系统基于设定的离散时间时长演化，任务开始与完成都以时间步为基本单位。

根据以上假设，我们来构建本文的模型系统。设网络中有n个节点，共有3种类型，xi表示i类型节点数量占网络中节点总数的比例，gi(j)为i类型节点为j类型节点提供服务的概率，i，j=1，2，3，分别代表无私、互惠、自私节点类型。各种类型节点数量初始比例为x1：x2：x3。归一后有：

网络中三种类型节点数目分别为n×x1，n×x2，n×x3。按照博弈理论，三种类型的节点可以认为是三方博弈的参与者，构成参与者集合：{无私者，互惠者，自私者}。参与策略集合：{按照一定比例gi(j)提供服务}。三方博弈关系：无私者对任何类型节点都采取提供服务的策略，因此，g1(j)=1，无私者对无私者、互惠者、自私者构成的策略选择矩阵为(1 1 1)。自私者对任何类型节点都采取拒绝服务的策略，因此，g3(j)=0，自私者对无私者、互惠者、自私者构成的策略选择矩阵为(0 0 0)。互惠者采取互惠策略，下文进行详细分析。

2.2 策略描述

镜像激励机制下的互惠节点收到另一个节点请求时，是否为其服务的概率等于该请求节点是否为其他节点提供服务的概率。因此易知，互惠节点对无私节点提供服务概率为g2(1)=1，对自私节点提供服务概率为g2(3)=0。互惠节点之间服务概率满足如下等式：

代入g2(1)=1，g2(3)=0，整理后求得，

综合以上三种类型节点策略，构建模型系统策略选择矩阵如下：

(1)

其中，行列参与者顺序依次表示无私者、互惠者、自私者类型节点，Gi，j表示i类型节点向j类型节点提供服务的概率，Gi，j=gi(j)。

显然，为其他节点提供服务得出的消耗矩阵等于策略选择矩阵式(1)，如下：

(2)

而获得其他节点服务的收益矩阵为激励系数与消耗矩阵的转置的乘积，如下：

(3)

由式(2)(3)可以得到单个节点的净收益矩阵，如下：

(4)

根据式(4)，可得两两净收益矩阵，如下：

(5)

对式(5)采用划线法分析可以得到：

由以上分析得到，(0，0)是唯一的纳什均衡解。采用经典博弈理论分析得出，只有节点拒绝提供服务才是最优策略，而且与激励系数α无关。但该结论与实际仿真实验结果不同。

3 结合数学模型的实验分析方法

经典博弈理论以博弈参与者具有完全理性为基础，完全理性意味着博弈参与者一开始就能够找到最优策略。但这与大部分现实状况不符，现实中由于信息不对称等各种因素限制，大部分参与者表现出的是有限理性，因此导致经典博弈理论分析难以逼真地模拟现实。仿真实验允许博弈参与者在博弈过程中，不断试错，不断学习，来寻求更优的策略。因而，在有限理性的前提下模拟现实情形，博弈分析的重点是关注博弈者学习和策略调整过程，以及趋势和稳定性。这里稳定性是指系统中博弈参与者采用特定策略的比例不变，而不是某个博弈方的策略不变。本模型节点数量较多，任意两个节点满足完全图网络性质，可以两两直接相连，相互之间随机提出服务请求。因此采用在上文的数学框架基础上开展演化博弈实验方法分析。

3.1 实验基本流程

(1)系统初始化阶段

首先确定系统规模，生成数量充足、数目固定的节点，并建立两两相连的完全图网络。对网络中每个节点按照初始策略比例赋予相应个体策略属性初值。并假定所有节点都可以满足提供服务的条件和具备学习能力。最后，系统设置完毕相关参数，如演化步数，学习系数，激励系数等。

(2)演化学习阶段

为便于实现并较为真实地反映实际演化过程，该阶段使用当前最大收益学习模型。该模型的核心思想是每个时间步系统得到平均收益最大的策略，采用其他策略的节点按照一定概率改变为该策略。后文作详细介绍。

(3)数据处理阶段

系统运行时记录每次时间步各种策略比值，对趋于稳定的后半部分时间步的策略比值集进行数学处理，以最小二乘法将这部分实验数据拟合为直线。截取该直线在时间步区间上的线段求其函数均值作为策略比例解。全部过程结束。

3.2 最大收益学习模型

当前最大收益学习模型包括3部分内容：

(1)某时刻(即当前时间步)的i类型节点的平均收益，公式如下：

(6)

(7)

(2)策略改变概率，公式如下：

(8)

(3)一个时间步内完整的流程。流程如下：

(a)每个节点(i)从自己相连的节点集合中随机选取一个节点(j)，向其提出请求服务，并提供自身节点类型；

(b)收到服务请求的节点(j)根据节点类型和自身当前策略，做出决定；

(c)每个节点计算本轮自己的收益，将收益值告诉系统；

(d)系统对每类节点的收益值分类求总和，计算平均收益(式6)，得到本轮平均收益最高的策略(式7)，并将该策略类型，与收益值告诉系统中每一个节点；

(e)每个节点将自己策略类型与最高策略比较，相同则保持策略不变，不同则转向6；

(f)节点将自己收益与平均最高收益值比较，自己的高或相同则不变，低则转向7；

(j)根据式(8)，计算概率值，节点按照概率转变策略。

4 实验结果与分析

4.1 实验设定

为了使实验仿真更加接近真实情况，因而必须保证网络系统具有一定规模，以减少误差。本文参考文献[11]中的节点数目，设定网络规模为节点数500。演化步数设定为20000时间步，大于一般文献设定的不高于3000时间步。策略比值集数据截取最后10000时间步。其他相关初始参数参照文献[11]，所有实验都在同一平台上进行仿真实验。具体实验参数设定如下。

实验参数参数值节点数500演化步数20000截取步数10000

续表

设定6组具有代表性的各种初始节点比例，来分析初始节点比例对演化过程和演化结果的影响。比例如下：

组次初始x1x2x3比例第1组(0.05,0.05,0.9)第2组(0.05,0.9,0.05)第3组(0.2,0.55,0.25)第4组(0.35,0.1,0.55)第5组(0.5,0.05,0.45)第6组(0.05,0.05,0.9)

4.2 固定α值实验过程分析

首先固定α值进行6组实验。图1(a)-(f)给出在激励系数α=4条件下，完全图对等网络不同初始类型节点密度条件下，三种类型节点演化20000步的比例变化过程。每个子图中不同曲线分别对应无私者、互惠者和自私者即时比例。

(a)

(b)

(c)

(d)

(e)

(f)图1

由图1可见：(1)不管节点初始比例怎样不同，经过20000步演化后，各组节点比例都趋向稳定。结果都趋向于相同的比例值，且遵循x1>x2>x3。

(2)各组演化至稳定状态所花费的时间不一样。从图1大致看出，节点初始比例与演化稳定比例较为接近的组趋于稳定花费的时间较短，反之较长。

(3)一些组节点比例经历了较大幅度的反复变化，如图1(d)(e)(f)前期都经历过自私者数量快速增长的阶段。如果设定的演化时间较短，实验结果与演化时间较长的结果偏差较大，就容易得出不一样的结论。

(4)图1(a)(b)(f)是特意取值较为极端的3种情形，分别对应初始时自私者、互惠者、无私者几乎独占的状态。但从演化变化情况发现，过程虽然经过较大幅度振荡，结果仍趋向稳定和一致。

图2

进一步对实验数据进行处理，精确求得节点所占比例值，见图2。进而求得数据的算术平均值，并计算三种节点类型的标准差和离散系数。见表1。

节点类型算术平均值标准差离散系数无私者(x1)0.550980.003580.006497互惠者(x2)0.3692580.009880.026755自私者(x3)0.0803520.0065840.081945

观察图2和分析表1可知，各个评价维度显示，6组实验结果非常接近。因而得出，当激励系数α=4时，经过较长时间演化学习后，节点比例趋向于一个稳定值，与初始比例无关。

4.3 不同α值实验结果分析

下面对激励系数α为一般值时的情形进一步进行实验仿真。分别取α=1，2，3，4，5，6，7，8，9，其他参数同前文设置，系统仍然按照6组初始比例运行20000步。图3(a)-(f)为运行后各种节点类型的所占比例。

观察图3(a)-(f)可知：(1)当α=1时，事实上等于没有激励，无私者在演化过程中消失，不同组互惠者与自私者比例虽然有所不同，但其实效果一样。没有了无私者，所谓的互惠者按照镜像激励机制的互惠策略，不再给任何节点提供服务，本质等同于自私者。此时系统已经崩溃，节点彼此之间已不提供服务。

(a)

(b)

(c)

(d)

(e)

(f)图3

(2)当α>1时，可以大体看出，无论节点初值比例如何设定，在α值相同的条件下，演化后的不同组的比例值大体相近。也就意味着一般意义上，不同的初始比例对经过长期演化的节点类型比例值不构成影响。

(3)当α=2时，无私者数量稍有增加，虽然对系统性能改善有一定作用，但效果不明显。自私者比例仍然在70%左右，占据绝对多数，而互惠者比例虽有所提高，但按照镜像激励机制的互惠策略，大部分互惠节点为其他节点提供服务概率很低，整个系统不具有良好的性能。

(4)当α=3时，自私节点已经降到了系统总节点数的1/3以下，无私节点和互惠节点占据了大多数，具有一定优势，但没有形成压倒性态势。

(5)当α=4时，自私节点降到了10%以下，无私节点和互惠节点占据了绝对优势地位，系统形成了稳定的态势。

(6)α>4之后，系统保持优良的稳定性能，但激励系数增加的带来系统的整体效果改善不再像之前明显，自私节点整体上呈现平稳态势下略有下降。

综上分析，可以得到：(1)镜像激励机制并非是一种不成功的激励机制，而是在较高激励系数的条件下，随着长时间演化，可以实现促进系统节点间提供服务的目的。(2)演化稳定状态与激励系数相关，与初始比例无关。(3)即使存在激励机制，但没有提供实质性的激励(当α=1时相当于没有激励)，系统仍然会走向崩溃。(4)既有激励机制，又保证实质性激励(α>1)，激励的效果可以显现。在较小的激励系数变化区间(2≤α≤4)，激励系数增加，能够明显有利于无私者和互惠者数量的增加，自私节点的减少，有效引导系统趋向合作。但并非随着激励系数的增大，性能改善持续保持明显提高。实验结果显示，到达一定值(α=4)后，效果改善不再显著，而是趋于平缓。由此我们可以得到启示：系统需要激励机制，但没有必要无限制地增加激励成本。

5 结论

本文基于完全图网络，构建了旨在提高节点之间服务概率的镜像激励机制框架系统，采用结合数学模型的实验仿真方法求得了系统稳定后各种节点类型所占总节点数的比例。进而发现，在较短的演化时间内，各种节点的初始比例对演化情形影响较大，但随着演化时间的增加，演化比例趋于稳定。本质而言，演化稳定时的节点比例只受激励系数影响，而与初始比例无关。一般而言，激励系数的增大，能够减少自私者在系统中所占的比例，在激励系数较小的区间内这种变化较为明显。随着激励系数增大，这种变化逐渐趋向平缓。本文的局限性在于假设条件较为严格以及采用了结合数学的实验方法，探究其背后的数学机理以及放宽假设条件使之更接近真实系统是下一步的研究方向。