一种基于博弈理论的无线传感器网络自私节点惩罚机制

王艳华　孙成启　高洋等

摘要 针对无线传感器网络中的搭便车现象，基于博弈理论建立自私节点惩罚机制。将传感器的可信度分为多个等级，对其进行多策略博弈，使其更加符合无线传感器网络的复杂性特点，从而激励节点对可信合作策略的选取。结果表明，基于博弈理论的无线传感器网络中自私节点惩罚机制可以有效地解决网络中的搭便车问题，从而验证了该惩罚机制的有效性。

关键词 无线传感器网络；搭便车；博弈；惩罚机制

中图分类号 S126 文献标识码

无线传感器网络（Wireless Sensor Network，WSN）是由大量的传感器节点构成的，其构成的方式多为自组织形式和多跳形式，这些传感器节点可以协作地感知和处理被感知对象的相关信息，并且将所感知的信息发送给网络的所有者[1-2]。WSN具有典型的复杂网络特点，其应用也变得日趋复杂，因此，WSN的安全性成为一个亟待解决的问题。传统的解决WSN的方法主要为基于密码学的安全机制，该方法主要用来抵抗外部攻击，然而基于密码学的安全机制不能很好地抑制WSN内部传感器节点的自私行为。

随着WSN研究领域的逐渐成熟，其信任管理的研究也成为WSN领域的研究热点。在WSN中，由于资源的有限性，传感器节点为了获取更多的资源而产生节点的自私行为，从而产生了WSN中的节点搭便车（Freeriding）问题。然而节点的这种自私行为严重影响了WSN的网络性能以及正常运行。

因此，笔者针对无线传感器网络中的搭便车现象，基于博弈理论建立自私节点惩罚机制，将传感器的可信度分为多个等级，对其进行多策略博弈，使其更加符合无线传感器网络的复杂性特点，从而制定更加有效的激励惩罚机制，激励节点对可信合作策略的选取。

1 激励惩罚机制概述

为了解决WSN中的搭便车问题，需要引入信任管理来对传感器节点的行为进行度量与管理，从而制定相应的激励惩罚机制来抑制传感器节点自私行为的产生。

调查显示，在WSN、社会网络以及P2P网络中，几乎70%的节点在交互过程中不分享任何的网络资源，并且这些自私节点对分享信息的用户进行搭便车。在网络中，有很少的节点愿意分享信息或为其他节点提供服务。几乎50%的文件查找响应是来自信息分享节点顶部的1%的文件。目前，有关激励惩罚机制的研究已日趋成熟。激励机制算法的基本流程如图1所示。

图1 激励机制算法基本流程

目前，将已提出的激励惩罚机制分为基于节点行为的激励方法[3-4]、基于博弈论的方法[5-6]以及采用社会网络或经济模型的控制策略[5，7-9]3大类。

1.1 基于节点行为的激励方法 最早有关Freeriding问题的抑制方法是基于节点行为的激励方法，该方法得到了广泛的应用。有关基于节点行为的激励方法中的一些相关问题，如如何计算节点信誉度等，已经成为WSN等网络的研究热点。有关效用函数的定义、度量以及选择等问题，是不同的基于节点行为激励方法之间的差异[10]。该方法可以有效地防止自私节点的欺骗行为，并激励节点遵守网络中的相关协议。

然而，在实际应用中，由于分布式的测量和监视机制，節点之间相互监视而产生大量的开销；并且网络的高密度，使产生节点由于监视邻接节点而增加其负担等问题。

1.2 基于博弈论的方法 由于WSN的复杂性，因此可以将节点的行为建模为长期的博弈过程。节点有多个策略进行选择，如为系统做贡献，只接收信息不发送信息以及贡献收益平衡等，从而使得自身获得最大的收益。基于博弈论的方法是对节点策略的选择进行分析，对网络中节点的不同策略进行博弈，从而分析出它们之间的关系[11]。

然而在实际的WSN、社会网络以及P2P等复杂网络的激励机制研究中，基于博弈论的方法存在以下两大主要问题：①目前的基于博弈论的激励机制，大多针对的是两策略进行博弈，即完全合作和完全不合作，然而在真实的复杂网络中，网络中节点的策略存在复杂性，因此两策略博弈不能满足真实网络中策略的复杂性特点；②现有的基于博弈论的激励机制中，所提出的假设太严格，与真实的复杂网络环境存在较大的差异，因此，所得到的纳什均衡的准确性较低。

1.3 基于社会网络或经济模型的控制策略 在WSN、社会网络以及P2P网络等复杂网络中，节点的自私行为是用户个人心理因素的一种延伸，因此可以采用社会网络或者经济模型来研究个人在社会行为中的自私行为。

然而采用社会网络或经济模型的控制策略大多需要有一个集中式的第三方来对节点的可信行为进行审计。因此，该方法的可扩展性较差，从而制约了WSN、社会网络以及P2P网络等复杂网络的发展，并且在可信度的计算方面很难得到网络中所有节点的认同。因此，由于复杂网络的动态性和复杂性特点，这种需要第三方来审计的方法难以实现。

针对以上激励惩罚机制的不足，基于WSN的特点，该研究基于博弈理论研究WSN的自私节点惩罚机制，将传感器的可信度分为多个等级，对其进行多策略博弈，使其更加符合WSN的复杂性特点，从而制定更加有效的激励惩罚机制，激励节点对可信合作策略的选取。

2 基于博弈理论的惩罚机制

传统的基于博弈理论的激励惩罚机制大多针对的是两策略博弈理论，即将节点的行为分为两类策略：自私策略和可信合作策略。则对称博弈收益矩阵如表1所示，且满足D>T>S>C，2T>C+D。也就是说，博弈双方都选择可信合作策略能够获得总体的最高收益。那么，不论对手采取哪种策略，选择自私策略都是最佳选择，也就是理性的个体最终会选择自私的策略。这种自私的状态就是系统的纳什均衡状态。

在WSN中，当自私节点与可信合作节点进行博弈时，自私节点通过损害可信合作节点的利益而使自己获得利益，其行为违背了公平规范。因此，为了抑制WSN中传感器自私节点的产生，该研究提出基于博弈理论的自私节点惩罚机制，从而提高可信合作策略的节点收益，降低自私节点的收益，激励节点对可信合作策略的选择。则自私节点的惩罚机制满足下面3个特点：

①鼓励传感器节点分享信息和提供服务；

②为传感器节点提供公平的差异化服务；

③最大化WSN的总体收益。

因此，如果博弈个体受到公平规范的影响，那么自私节点的效用收益就会因为破坏公平造成的“内疚”而降低，而可信合作节点的效用收益则会因为非信任个体违反公平造成额外的“不满”而增加。

针对该惩罚机制的特点，基于表1中两策略博弈的收益矩阵中的各个策略的收益值，该研究给出加入惩罚机制后的收益计算方法，如式（1）所示。其中，T*、C*、D*以及S

由于WSN具有复杂网络特性，因此需要将传感器的行为分为多个等级，需要在两策略博弈的基础上进行多策略博弈。该研究将传感器节点的行为分为4个等级，假设当两个节点进行博弈时，两个传感器节点的行为等级分别为i和j，且i，j∈（1，2，3，4）相应的收益分别为xi和xj，则加入惩罚机制的多策略收益值计算方法如式（2）所示，假设i

3 模拟试验与结果分析

該研究通过模拟试验来验证该信息传播模型的有效性。硬件试验环境为Intel Core（TM） i5-3230M CPU @2.60GHz，12.0 GB内存，采用Windows 8操作系统，用Matlab 7.0编程平台。

该研究模拟WSN中的1 000个不同策略的传感器节点数量变化的演化趋势，来验证所提惩罚机制的有效性。图2所示为没有加入惩罚机制的多策略博弈演化结果。从图2可以看出，在没有加入惩罚机制时，自私节点主导了整个网络的演化方向，也就是产生了搭便车现象。

加入该研究提出的惩罚机制后，模拟试验结果如图3所示。从图3可以看出，加入基于博弈理论的无线传感器网络中自私节点的惩罚机制后，选择可信合作策略的传感器节点最终主导整个WSN的演化方向；并且选择自私策略的传感器节点在网络中将最终消失。由此可见，该研究提出的惩罚机制可以有效地解决WSN中的搭便车问题，从而验证了该惩罚机制的有效性。

4 结语

该研究针对WSN中的搭便车现象，基于博弈理论建立自私节点惩罚机制，将传感器的可信度分为多个等级，对其进行多策略博弈，使其更加符合无线传感器网络的复杂性特点，从而制定更加有效的激励惩罚机制，激励节点对可信合

作策略的选取。试验结果表明，基于博弈理论的WSN中自

私节点惩罚机制可以有效地解决网络中的搭便车问题，从而

验证了该惩罚机制的有效性。

在未来的工作中，将进一步研究WSN的复杂特征，建立更加有效的激励惩罚机制来激励节点对可信合作策略的选择，从而提高WSN的整体性能。

参考文献

[1]

YICK J，MUKHERJEE B，GHOSAL D.Wireless sensor networks survey[J].Computer Networks，2008，52：2292-2330.

[2] HAN G J，JIANG J F，SHU L，et al.Management and applications of trust in Wireless Sensor Networks：A survey[J].Journal of Computer and System Sciences，2014，80（3）：602-617.

[3] ZGHAIBEH M，ANAGNOSTAKIS K G.On The impact of P2P incentive mechanisms on user behavior[R].NetEcon + IBC，2007：1-6.

[4] 谢晓兰，刘亮，赵鹏.面向云计算基于双层激励和欺骗检查的信任模型[J].电子与信息学报.2012，34（4）：812-817.

[5] MA R T B，LEE S C M，LUI J C S，et al.Incentive and service differentiation in P2P Networks：A game theoretic approach [J].IEEE/ACM Tranon Networking.2006：978-991.

[6] 张煜，林莉，怀进鹏，等.网格环境中信任-激励相容的资源分配机制[J].软件学报，2006，17（11）：2245-2254.

[7]WANG Y，VASSILEVA J.Super-agent based reputation management with a practical reward mechanism in decentralized systems[C]//4th IFIP WG11.11 International Conference on Trust Management.Iwate，Japan，2010：33-40.

[8]WANG Y，ZHANG J，VASSILEVA J.Effective web service selection via communities formed by superagents[C]// Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence.WI，Toronto，Canada，2010：444-451.

[9] GHAFFARINEJAD A，AKBARI M K.An incentive compatible and distributed reputation mechanism based on context similarity for service oriented systems[J].Future Generation Computer Systems，2013，29（3）：863-875.

[10] 胡建理，周斌，吴泉源.P2P网络中具有激励机制的信任管理研究[J].通信学报，2011，32（5）：22-32.

[11] 张娓娓，陈绥阳，余洋.基于博弈论的P2P激励机制[J].计算机工程，2011，37（15）：89-102.