基于随机演化博弈的WSNs节点协作演化模型

王丁　曹奇英　许洪云　沈士根

摘 要：为解决无线传感器网络节点协作策略的选择影响协作效果的问题，考虑到节点数量有限及个体随机性，基于模仿突变Wright-Fisher过程的随机演化博弈，提出了WSNs节点协作随机演化模型，并加入了与节点协作程度相关的惩罚机制。该模型弥补了复制子动态不适用于节点数量有限的WSNs节点协作演化建模问题。经过随机动力学分析，推导并证明了达到演化稳定状态的定理。最后通过实验验证定理并分析了选择强度和惩罚力度对WSNs节点协作演化稳定状态的影响。

关键词：无线传感器网络；协作；Wright-Fisher过程；随机演化博弈；模仿突变

中图分类号： TP393 文献标志码： A 文章编号：2095-2163（2016）01-

Abstract： To solve the problem of coordination decisions among WSNs nodes which affects the cooperation between nodes， considering limited numbers of nodes and individual stochastic effect， this paper constructs a stochastic evolutionary trust model of WSNs nodes based on imitated mutation Wright-Fisher process， and introduces a punishment mechanism related to the coordination level of nodes. The model compensated for the shortcoming of replicator dynamics where it was inapplicable to the WSNs having limited numbers of nodes. Theorems of arriving at the evolutionary stable state， through stochastic dynamics analysis， are deduced and proved. Experiments verify the conclusions and analyze the impacts of punishment levels and selection intensities toward the WSNs nodes coordination evolutionary stable state.

Keywords： Wireless Sensor Networks（WSNs）； Coordination； Wright-Fisher Process； Stochastic Evolutionary Game； Imitated Mutation

0 引言

无线传感器网络（Wireless Sensor Networks， WSNs） [1]是由数量众多的传感器节点以自组织和多跳等方式组成的无线网络。WSNs中传感器节点采集的数据需要被多个节点连续转发后才能到达目标节点。如果一个节点与其他节点协作，那么将会帮助其他节点转发数据包，使协作任务的成功率提高，可认为该节点获得收益；但在转发数据包的同时，节点本身需要付出一定的成本，如消耗能量、自身任务延时传输等。由于获得收益和付出成本是一个矛盾，因此若存在较多节点不和其他节点协作的情况，就会导致WSNs节点无法正常协作。因此，节点之间协作与否会直接影响到WSNs的稳定性和协作任务的成功率。

近几年来，已有许多学者使用演化博弈论的方法来分析网络中的一些矛盾问题。文献[2]分析了无限总体演化博弈的演化稳定策略，并与复杂网络博弈的演化稳定策略进行了比较，提出了一种适用于网络演化博弈的演化稳定策略新定义；文献[3]将演化博弈应用于延迟容忍网络的非合作转发控制方面，并分析了交互次数对演化均衡的影响。在WSNs研究领域，文献[4]提出了一种基于演化博弈的资源控制协议，用于缓解WSNs内部资源竞争矛盾。文献[5]将演化博弈与WSNs节点信任决策结合，建立了WSNs节点信任博弈模型，提出并证明了在不同的参数条件下达到演化稳定策略的定理。文献[6]和文献[7]在文献[5]的基础上分别引入了节点的反思机制和模仿机制，并考虑了网络不可靠因素对模型的影响。

上述文献所用的演化博弈模型大都是针对无限总体的对象，而实际情况中的研究对象一般都是有限总体。针对这个问题，学者们将随机过程应用到演化博弈中，形成了以有限总体为研究对象的随机演化博弈。文献[8]研究了服务提供商面对软硬件服务攻击时的安全和可信机制，提出了一种适用于虚拟传感器服务（Virtual Sensor Services）的安全、可信的随机演化联合博弈防御框架。文献[9]针对网构软件中存在的服务问题，将网构软件的服务差异化，并把基于Wright-Fisher过程的两策略博弈拓展到多策略，提出了一种博弈参与者具有多个策略的信任演化博弈模型。文献[10]把Moran过程应用到无线网络的接入选择中，并从多策略的角度改进了局部更新机制。随机演化博弈虽然在其他领域已有较广的应用，但是目前在WSNs中应用还较少。

本文使用基于两策略频率相关、带模仿突变的Wright-Fisher过程随机演化博弈模型来分析无线传感器网络中存在的节点协作问题。数量有限的WSNs节点在选择协作与否时体现出了重复性、有限理性等特征，而对于整个WSNs来说，其目标是在达到总体收益较高状态的同时也能够保持足够的稳健性，这些特征恰好满足随机演化博弈的要求。据此，本文建立了WSNs节点协作演化模型，使节点在无外界干预的情况下动态演化，各个节点根据模仿突变Wright-Fisher机制自行调整下一次博弈的策略，使WSNs逐渐演化到稳定状态。在到达演化稳定状态之后，WSNs中的绝大部分节点将会选择协作策略并保持不变。在信任演化[5]的基础上，通过考虑WSNs中有限节点数量的情况，引入惩罚因子和模仿机制来构造协作博弈模型，并利用带突变的Wright-Fisher过程来分析节点协作演化动态，使WSNs节点协作模型更趋近真实状况，并得出到达演化稳定状态的定理，分析影响到达演化稳定状态的影响因子。

1 基于突变Wright-Fisher过程的随机演化博弈模型

博弈论是分析博弈个体在进行博弈时表现出的行为并研究博弈个体的博弈最优策略的理论。一个标准的博弈由3个要素组成：博弈个体，策略集合和收益函数[11]。博弈个体是参与博弈的主观个体，每个博弈个体分别从策略集合中选取一种策略与另一个博弈个体进行博弈，收益函数是博弈个体依据其策略与对手博弈所获得的收益。收益函数可由收益矩阵的形式给出。经典博弈的博弈个体总是完全理性[11]的，也就是说，博弈个体总是选择收益最大的策略与对手进行博弈。

演化博弈论在经典博弈的基础之上，结合博弈分析理论和生物种群的演化过程，形成了一个新的博弈论分支。在演化博弈论中，博弈个体都是有限理性[12]的，它把所有博弈个体的总体视为一个种群，将种群作为基本的研究对象，研究博弈个体在多次动态博弈中的策略演化状况。

经典的演化博弈的研究对象一般是无限总体，但在实际情况中，研究对象都是总体数量有限的，并且个体的随机性在有限总体的博弈过程中起着非常重要的作用，因此基于随机过程的随机演化博弈成为了研究有限总体演化博弈的重要途径，当中较重要的三种模型是Moran过程[13]、Wright-Fisher过程[14]和随机配对过程[15]。其中Wright-Fisher过程由于能够在一次迭代内进行同步更新，相较于只能异步更新的其他两种过程更具现实意义。

在Wright-Fisher过程中，总体中的个体在进行策略更新时，会依据策略的适应性选择适合自身的策略，之后每一个体都会产生多个后代个体，得到一个总数大于总体数量的后代集合，再从这个集合中随机选出等于总体数量的新个体取代当前个体。

在文献[14]描述的Wright-Fisher过程博弈模型的基础上引入模仿突变概率 ， ， 表示选择 策略的个体在下一次博弈时依然选择 策略的概率， 表示选择 策略的个体在下一次博弈时突变为 策略的概率， 表示选择 策略的个体在下一次博弈时突变为 策略的概率， 表示选择 策略的个体在下一次博弈时依然选择 策略的概率。易知，突变概率 存在如下关系：

， （1）

每个博弈个体在进行策略更新时，策略的选择过程相当于在个体后代的集合中进行 次独立的二项分布试验，因此产生选择 策略个体的过程就是概率为 的 重伯努利试验，所以带突变的Wright-Fisher过程是一个状态空间为 的马尔可夫链，系统从状态 转变到状态 的转移概率为：

（2）

2 WSNs节点协作演化模型

2.1 博弈模型

基于文献[5]的研究，本文在WSNs节点协作博弈时加入了与节点协作程度相关的惩罚机制。在WSNs中，节点可以与邻居节点进行主动式的交互，选择协作策略与对方协作，或选择不协作策略不与对方协作。在本文中并不涉及节点协作程度的计算或量化过程，而是在节点选择不协作策略时给予一定的惩罚。

考虑两个节点在交互时的协作状况，记 表示当前节点数据被协作节点成功转发传输而带来的收益； 表示当前节点选择与其他节点协作，成功转发其他节点数据使任务的成功率提高带来的收益； 表示当前节点因选择协作策略提升了自身在对方节点的信任度收益或因选择不协作策略而降低自身在对方节点的信任度损失； 表示当前节点选择协作策略使路由可靠度提升而带来的收益或因选择不协作策略而使路由可靠度降低所带来的收益损失； 表示因对方节点不协作而导致自身数据传输失败带来的收益损失； 表示因选择不协作策略节省能量从而延长自身的生存周期所获得的收益； 表示当前节点向对方节点发送自身的数据或转发对方数据所产生的传输成本， 表示当前节点因选择了不协作策略而受到的惩罚损耗。

下面对各种可能发生的交互状态分别进行讨论：

1）两个节点在进行交互时均选择了协作策略。双方节点的收益均为 。

2）两个节点在进行交互时有一个节点选择了协作策略，而另一个节点选择了不协作策略。此时选择了协作策略的节点会帮助对方节点转发传输数据，而选择不协作策略的节点则不会帮助对方转发数据，因此选择协作策略的节点收益为 ，选择不协作策略的节点收益为 。

3）两个节点在进行交互时均选择了不协作策略。两个节点的收益均为 。

定义1 无线传感器网络节点协作博弈是一个由四元组 表示的对称博弈。其中参与者 为无线传感器网络中所有节点的集合； 为参与者的总体数量；策略集合为 ， 为协作策略， 为不协作策略； 为无线传感器网络节点在一次两人两策略对称博弈时的收益函数，如表1所示。

2.2 模仿突变因子的确定

本文提出一种基于模仿策略的策略调整机制，使传感器节点在协作博弈时若发现对方策略的收益大于自己的收益，就会模仿其策略或行为。模仿机制体现在博弈过程中具体表现为博弈个体在产生后代的过程中引入模仿突变因子，产生后代的过程中有一定的突变概率，将后代个体的策略调整为博弈对手的策略。

逻辑斯蒂方程（Logistic Equation）是研究生物学、社会学中种群增长的一种模型，在生态学中，一个种群内个体数量的变化动态可以用逻辑斯蒂方程的微分形式表示：

（3）

其中， 为种群的瞬时增长量， 为种群的个体增长率， 为特定时间内种群内的个体数量， 为环境容纳量，也就是该生态环境所能维持的种群内个体最大数量。 为逻辑斯蒂系数。

在演化博弈过程中，突变因子在演化前期由于博弈次数较少或稳定性的可信度不高，因此模仿突变因子具有较大的变化趋势，而随着演化过程的演进，系统稳定性的可信度逐渐增强，因此模仿突变因子在演化后期的变化范围较小，这个特性恰与逻辑斯蒂方程的增长趋势相符，因此本文使用基于逻辑斯蒂方程的变形微分方程来表示模仿突变因子。

令 ，则逻辑斯蒂方程变形为：

（4）

记 表示博弈总体内每个个体可选的博弈策略集，向量 表示总体状况，其中 表示选择策略 的个体比例； 表示选择策略 的个体和选择策略 的个体在博弈时相遇，两个个体在经过博弈后，互相学习，观察对方的策略和收益，对自己当前的策略和收益进行调整，使个体产生的后代有一定概率突变为其他策略，记 表示选择 策略的后代个体突变为 策略的概率，由于模仿突变概率与各策略的收益和选择该策略的个体在总体中的比例有关，引入逻辑斯蒂变形方程可得模仿突变概率为：

（5）

其中， 表示策略 与策略 在博弈过程中期望收益之差。

2.3 引入模仿突变Wright-Fisher过程

由于WSNs的节点数量是有限的，进行博弈的节点可以看作出自一个种群的有限总体，因此在WSNs节点协作博弈中引入模仿突变Wright-Fisher过程，该模型既能体现WSNs节点协作博弈的总体有限性、离散性和随机性等特征，也能体现出节点在博弈时的策略调整过程。

假设在WSNs节点协作博弈中，节点的总数为 ，有数量为 的节点选择协作策略，则有 个节点选择不协作策略。在进行节点协作博弈时，需剔除自己和自己博弈的情况，因此可得：

任选一个节点选择协作策略的期望收益为： （6）

任选一个节点选择不协作策略的期望收益为：

（7）

假设在演化博弈中，收益函数对该策略适应度的影响因子为 ， ，则在WSNs节点协作博弈中，协作策略的适应度为： （8）

不协作策略的适应度为： （9）

由于适应度要求收益函数为非负数，因此对策略的收益函数还应加以修正，使其满足适应度的条件。选择强度参数 的引入，使得Wright-Fisher过程具有了有限理性的特性。

定义2 在不考虑自身博弈情况的无线传感器网络节点协作博弈中，协作策略的适应度为 ，不协作策略的适应度为 ，其中 为选择协作策略的节点数量， 为无线传感器网络节点在博弈时选择协作策略的收益且：

（10）

为无线传感器网络节点在博弈时选择不协作策略的收益且：

（11）

为收益对适应度的选择强度， 为常数使得收益函数为非负数。

定义3 在不考虑自身博弈情况的无线传感器网络节点协作博弈中，个体在每次博弈之后，产生的后代个体中，有一定的突变概率 使个体改变博弈的策略，个体的博弈策略从协作策略突变为不协作策略的概率为：

（12）

则个体的博弈策略依然保持协作策略的概率为 ；个体的博弈策略从不协作策略突变为协作策略的概率为： （13）

则个体的博弈策略依然保持不协作策略的概率为 ，其中 ， ， ， 为常数使得 ， 。

在定义3中， 和 作为策略突变的概率，保证其大小与当前节点的自身收益呈反向变化，与对方的收益呈正向变化。

WSNs的节点在进行下一次博弈之前，会进行以下步骤更新策略：

1）每个节点都会生成相同数量的多个选择相同策略的后代，这些后代中，有一部分后代会以突变概率 突变，选择对手策略，剩下的后代依然完全继承父代个体选择的策略，构成一个数量为 的整数倍个后代的集合；

2）从这个后代集合里选出与总体数量相同的 个新一代后代，由于后代节点只有协作和不协作两种策略，选择每个节点的过程都是一次独立伯努利试验过程，由定义2可得，选出一个信任策略的后代节点的概率为 ，因此新一代博弈后代节点的产生过程就是一个概率为 的 重伯努利试验；

3）新一代后代完全替换上一代，完成节点的一代更新。

由定理1和定理2可知，要使整个无线传感器网络具有良好的稳定性和节点协作性，需促使无线传感器网络的节点在协作博弈时选择协作策略，因此在设计无线传感器网络协作机制时应使其尽量符合定理2的条件。惩罚因子 的引入会使无线传感器网络节点在选择不协作策略时受到一定的惩罚，产生更多的损失，当 逐渐增大，惩罚力度也逐渐变大时，会使无线传感器网络逐渐满足定理2的条件，而逐渐偏离定理1的条件。当 增大到一定程度，使得无线传感器网络节点信任博弈不满足定理1，但是满足定理2的条件时，无线传感器网络将处于比较理想的稳定状态，此时网络内的所有节点在经过有限次博弈之后都会最终选择协作策略。

3 实验分析

3.1 定理验证实验

在图1中，当WSNs节点协作博弈的条件满足定理1时，设定选择协作策略的节点初始比例为0.999 9，经过140次博弈，绝大部分节点都选择不协作策略，达到了 的演化稳定状态；当WSNs节点协作博弈的条件满足定理2时，设定选择协作策略的节点初始比例为0.000 1时，经过78次博弈，绝大部分节点都选择协作策略，达到了 的演化稳定状态。此实验验证了定理1和定理2成立。

3.2 影响因子验证实验

实验中分别使用不同数值的惩罚因子 和选择强度 来观察其对无线传感器网络节点协作博弈的影响，并根据实验结果给出优化无线传感器网络节点协作博弈的对策。本实验共设2组，第1组分析惩罚因子 对定理2的影响，第2组分析选择强度 对定理2的影响。

3.2.1 惩罚因子 的影响

实验设定： ， ， ， ， ， ， ， ， ； 分别设定为16和15。两组数据均满足定理2，实验结果如图2所示。

在图2中，当选择协作策略的节点初始比例为0.000 1时，两组数据均使得WSNs节点经过一定次数的协作博弈达到了 的演化稳定状态。在其他参数相同的情况下， 的一组节点只需78次博弈即可达到演化稳定状态，比 的另一组节点收敛速度更快。由此可知，在满足定理2的条件下，提高惩罚因子 能有效促进WSNs节点在进行协作博弈时更快地达到演化稳定状态。

在图3中，当选择协作策略的节点初始比例为0.0001时，三组数据均使得无线传感器网络节点经过一定次数的协作博弈后达到了 的演化稳定状态。在其他参数相同的情况下， 的一组节点需要212次博弈才能达到稳定状态， 的一组节点需要130次博弈才能达到稳定状态，而 的一组节点只需78次即可达到稳定状态。由此可知，在满足定理2的条件下，提高选择强度 能有效促进无线传感器网络节点在进行协作博弈时更快地达到演化稳定状态。

4 结束语

节点间的协作问题是WSNs稳定运行的重要基础，促进WSNs节点互相协作能够促使整个无线传感器网络达到稳定状态。本文根据无线传感器网络中节点数量有限等特点，引入与节点协作相关的惩罚机制，提出了基于模仿突变Wright-Fisher过程的无线传感器网络节点协作随机演化模型，弥补了复制子动态不适用于节点数量有限的无线传感器网络中的缺陷，使无线传感器网络节点协作博弈模型更符合实际情况。在此基础之上，对随机演化博弈模型进行了动力学分析，得出并证明了WSNs节点协作博弈达到演化稳定状态的定理。经过分析与实验验证了结论：提高节点选择不协作策略的惩罚力度和节点选择协作策略的选择强度均能有效促进WSNs节点的协作程度，实现网络的安全与稳定。本文提出的基于模仿突变Wright-Fisher过程的WSNs节点协作随机演化博弈模型，为无线传感器网络节点协作问题研究提供了理论依据。

参考文献：

[1] YICK J， MUKHERJEE B， GHOSAL D. Wireless sensor network survey[J]. Computer networks， 2008， 52（12）： 2292-2330.

[2] CHENG D， XU T， QI H. Evolutionarily Stable Strategy of Networked Evolutionary Games[J]. IEEE transactions on neural networks and learning systems， 2014， 25（7）： 1335-1345.

[3] EL-AZOUZI R， De PELLEGRINI F， SIDI H B A， et al. Evolutionary forwarding games in delay tolerant networks： Equilibria， mechanism design and stochastic approximation[J]. Computer Networks， 2013， 57（4）： 1003-1018.

[4] FARZANEH N， YAGHMAEE M H. An adaptive competitive resource control protocol for alleviating congestion in Wireless Sensor Networks： An evolutionary Game Theory approach[J]. Wireless Personal Communications， 2015，82（1）： 123-142.

[5] 沈士根， 马绚， 蒋华， 等. 基于演化博弈论的 WSNs 信任决策模型与动力学分析[J]. 控制与决策， 2012， 27（8）： 1133-1138.

[6] 李紫川， 沈士根， 曹奇英. 基于反思机制的 WSNs 节点信任演化模型[J]. 计算机应用研究， 2014， 31（5）： 1528-1531.

[7] LI Yuan-jie， XU Hong-yun， CAO Qi-ying， et al. Evolutionary game-based trust strategy adjustment among nodes in Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks， 2015，2015（818903）：1-12.

[8] LIU J， SHEN S， YUE G， et al. A stochastic evolutionary coalition game model of secure and dependable virtual service in Sensor-Cloud[J]. Applied Soft Computing， 2015， 30： 123-135.

[9] 印桂生， 王莹洁， 董宇欣， 等. 网构软件的 Wright-Fisher 多策略信任演化模型[J]. 软件学报， 2012， 23（8）： 1978-1991.

[10] 冯光升， 王慧强， 周沫， 等. 基于 Moran 过程的无线网络接入选择方法[J]. 北京邮电大学学报， 2014， 37（4）： 10-14.

[11] FUDENBERG D， TIROLE J. 博弈论[M].北京： 中国人民大学出版社，2002.

[12] 乔根 W.威布尔. 演化博弈论[M]. 王永钦，译.上海：上海人民出版社，2006： 40-86.

[13] MORAN P. A. P. The Statistical Processes of Evolutionary Theory[M]. Oxford： Clarendon Press， 1962.

[14] TRAULSEN A， CLAUSSEN J C， HAUERT C. Coevolutionary dynamics： from finite to infinite populations[J]. Physical review letters， 2005， 95（23）： 238701.

[15] TRAULSEN A， PACHECO J M， NOWAK M A. Pairwise comparison and selection temperature in evolutionary game dynamics[J]. Journal of theoretical biology， 2007， 246（3）： 522-529.

[16] OHTSUKI H， PACHECO J M， NOWAK M A. Evolutionary graph theory： breaking the symmetry between interaction and replacement[J]. Journal of Theoretical Biology， 2007， 246（4）： 681-694.