基于博弈论的无线自组网动态接入激励机制*

王 宏**,2，李建华，崔 琼

(1.空军工程大学 信息与导航学院，西安 710077；2.国防科技大学 信息通信学院，西安 710106)

基于博弈论的无线自组网动态接入激励机制*

王 宏**1,2，李建华1，崔 琼1

(1.空军工程大学 信息与导航学院，西安 710077；2.国防科技大学 信息通信学院，西安 710106)

无线自组网节点的能量有限导致网内节点往往拒绝承担新节点入网所带来的认证负荷。为激励无线自组网节点参与新节点的入网认证，引入博弈论的公共物品供给博弈理论和维克里-克拉克-格罗夫斯(VCG)机制理论，构建了无线自组网的动态接入激励机制。提出了认证节点选举办法，给出了新节点认证付酬和认证节点收益函数，分析了认证能量消耗。理论证明了激励机制具有策略防伪、个体理性和预算平衡3个特性。实例分析了不同参数设置情况下网内节点就新节点接入认证、个体与集体的合作博弈过程，结果表明该机制能有效地激励节点，为了自身的最大利益积极选择参与新节点的入网认证。

无线自组网；接入认证；博弈论；激励机制

1 引 言

无线自组网是在没有固定的网络基础设施的前提下，移动节点之间通过无线信道连接构成的动态拓扑结构的网络。无线信道的大众开放性、移动节点的分布式控制等特征使得无线自组网较传统网络面临更多安全威胁。采取安全高效的认证机制可以有效阻止非法节点的入侵和攻击，是提升无线自组网安全性能的关键。然而，在无线自组网中各移动节点大多都是依赖电池等有限源提供能量，处理能力和计算能力有限，已完成组网的、理性的网内节点往往不肯承担后入网节点接入带来的任务负荷，拒绝耗费自身的能量为他人提供接入认证服务，致使接入访问呈现整体不合作的“消极”状态[1-2]。设计一种科学合理的接入激励机制，有效促进无线自组网节点的积极协作，实现无线自组网的动态随遇接入，已经成为无线自组网发展亟待解决的现实问题。

机制设计是博弈论在社会选择方面的运用，它将参与者的行为描述为博弈策略，同时按照社会选择理论对各种情形设定相应的社会目标，研究构造什么样的博弈形式能使这个博弈的均衡最接近既设的社会目标。假设参与者总会采取使自己获得最大效用(收益和损失之差)的策略，接入激励机制设计就是考虑构造什么样的博弈形式使得参与者既考虑自身能量消耗，也不得不兼顾承担新节点的入网认证事务，从而激励节点积极参与网络事务的责任分担。文献[3-4]将节点个体与集体的博弈过程假设为多阶段博弈，并引入演化博弈理论，提出了一种针对不愿承担转发分组任务节点的惩罚机制，使节点采取合作时的收益永远大于不合作的收益，从而保证无线自组网的连通性和可用性。文献[5-9]引入拍卖博弈机制解决带宽、频谱等网络资源的分配问题，调动资源申请者的参与资源竞争的积极性，从而达到网络资源分配的公平公开。文献[10]以多Agent系统为平台，基于动态无限博弈提出多Agent分工合作机制的模型，促进各个自治系统的相互合作。归纳起来，针对激励机制设计的研究，一方面主要集中在节点分组转发激励机制方面，鲜有安全认证机制方面的研究；另一方面，机制设计大多侧重于长期使用的无线自组网或无线Mesh网络，而对于短期或一次性的自组网的机制设计研究较少，这样的网络节点更加关注眼前的既得利益，较长期网络的节点表现出更差的合作耐性。因此，有必要针对无线自组网节点在安全入网认证方面特性，进一步研究接入认证激励机制。

本文借鉴公共物品供给博弈机制[11](典型代表为“三个和尚没水喝”“雪堆”博弈)，将惩罚措施引入维克里-克拉克-格罗夫斯(VCG)机制[10]中，用于节点自由度更大、自主协同要求更高的无线自组网新节点入网认证激励机制设计，调动网内节点承担新节点入网认证的积极性。

2 基于VCG的动态接入激励机制

VCG机制是在公共物品有效供给和分配过程中，为激励具有拟线性偏好[12]的参与者真实地表现对于公共物品的偏好程度而设计的一种机制。为激励无线自组网内节点积极响应外来节点的入网请求，促使节点真实报告自己的能源、功耗等具体信息。本文将量化的惩罚措施引入VCG机制。首先为每一个节点分配一个信誉值，信誉值会根据节点的表现行为动态变化，当节点的信誉值低于阈值的时候，邻居便会拒绝为其提供诸如转发数据包等服务，导致其被整个网络边缘化。节点独立理性地决定其与网络的合作程度，合作则可以获得付酬，但提供认证等服务必定有一定的能量消耗，节点试图平衡其信誉和能量。

假设某无线自组网中现存(B1,B2,…,Bn)共n个节点，每个Bi(i=1,2,…,n)有ki种类型，当前有一个等待加入网络的节点BNew，本文研究如何调动(B1,B2,…,Bn)积极响应BNew认证申请的激励机制，首先给出假设条件。

假设1：无线自组网中的节点除了具有自主性、对等性等特征，还具有趋利避害的理性特征。

假设2：节点i的剩余能量报告是秘密信息，在其余节点看来它服从分布函数为Fi(x)，且Fi(x)≥0，概率分布为pi(xi),(i=1,2,…,ki)。

假设3：网内节点相互独立，不存在合谋抵制新节点加入的情况。当新节点发出认证请求时，响应节点的能量消耗报告相互独立，若节点i的策略集为Bi，则除i外的其他节点策略集记为B-i。

假设4：响应节点的能量消耗报告相同是小概率事件，在文中环境下不可能发生。

无线自组网动态接入激励机制可记为

VCG:{A,C,R}。

文中符合及其表达意义见表1。

表1 文中符号表达意义Tab.1 Letters and symbols

2.1节点选举办法

动态接入认证节点选择模型为

(1)

2.2新节点付酬

为了激励网内节点参与认证，机制为参与认证的节点提供付酬，参与节点i的付酬函数定义为

(2)

2.3认证节点收益

当参与者具有拟线性偏好特性时，可以使用转移支付调节参与者的收益，达到帕累托均衡。下面通过收益函数的设计，使得参与者具有拟线性偏好，从而使用VCG机制激励节点积极参与入网节点的认证。

如果真实能量消耗为ci的节点i最终被选定，令它的收益函数为

(3)

2.4认证能量消耗

除了认证节点的付酬、收益函数外，认证节点i的能量消耗函数ci也是动态接入激励机制的重要组成部分。函数ci与自身能量剩余、信誉度有关，按照文献[8]定义的节点分类方法，首先引进一套分类标准P={ρ1，ρ2,…,ρl-1}，每个节点的能量Ei(i=1,2,…,n)与一个级别cli对应：

(4)

3 激励机制的性能分析

有效的博弈机制必须满足策略防伪(strategy-proof)、个人理性(individual rational)和预算平衡(budget-balanced)[13]。下面证明当网内节点能量消耗为秘密信息，节点之间仅知道其他参与节点的类型分布概率时，上文机制满足以上3个条件。

3.1策略防伪

定理1：式(1)～(3)表示的激励机制满足策略性防伪或最优策略激励兼容性，确保每个认证参与者如实地报告自己的能量消耗，即“说真话”是最优策略。

3.2个体理性

定理2：对于每一个参与者，式(1)～(3)表示的激励机制是个体理性的。

证明：个体理性，即机制中网络节点若能成功参与外来节点的接入认证，则一定能得到相应的付酬，且收益函数非负；如果没有参与，则相应的付酬为零，能量消耗亦为零。

分两种情况讨论：

3.3预算平衡

定理3：式(1)～(3)表示的激励机制是预算平衡的。

4 激励机制的纳什均衡求解

从认证的过程来看，新节点广播认证请求[14]，网内节点收到请求，并根据自己的信誉度及真实能量给出自己的能量消耗报告予以响应，只有能量报告最少的一个响应节点i取得认证资格，随后完成新节点的认证。从参与认证的节点i的角度来看，它取得付酬，增加自己的信誉度；从网络整体来看，扩展了网络，网中的节点成员增多带来路由选择的多样化，全体网络成员共同受益。下面通过分析认证参与节点的能量消耗报告，绘制参与方的反应曲线，从而确定参与方能量报告决策的纳什均衡。

为讨论方便，假设无线自组网中只有2个现存节点，它们参与认证的能量消耗分别为c1与c2，剩余能量分别为ω1与ω2，则留给自己的私人消耗为x1=ω1-c1与x2=ω2-c2。根据“包含型”服务认证分析，无线自组网吸收新节点后的公共收益为C=max{c1,c2}。在拟线性效用函数的前提下每一个参与者的收益为Scorei(ci)=Ui(C)+xi，i={1,2}，每个节点的决策问题可表示为

则Scorei(ci)=Ui(C)+xi=Ui(max{c1,c2})+ωi-ci。

(4)

(5)

(6)

同理，节点2的能量报告策略为

(7)

分3种情况分析纳什均衡求解。

图1 1>2>2>1时节点的反应曲线Fig.1 Reaction curve when 1>2>2>1

图2 1>2>2>1时节点的反应曲线Fig.2 Reaction curve when 1>2>2>1

图3 1>2>1>2时节点的反应曲线Fig.3 Reaction curve when 1>2>1>2

上述分析表明，3种情形下文中的激励机制总能在兼容个体节点与网络中所有节点利益的情况下，选举出能量保持最优的节点作为入网认证节点。在组队参加抢答竞赛中存在类似的情境，为了获得抢答最高分，最好的办法是小组内成员都积极暴露自己的实力，然后选择一个尖子成员独立积极参加抢答，其他成员打打下手就可以。

5 结束语

基于公共物品供给博弈与VCG机制的无线自组网入网认证付酬激励模型，对促使无线自组网中现存节点积极参与新节点认证具有较大的作用。实例中纳什均衡分析得出的解也与实践经验相符，即当个体理性与集体理性兼容时，为了使个体利益达到最大，节点从自身收益出发选择积极响应入网节点认证请求，而后从所有响应节点中选择能量最优的节点作为认证节点。然而，在实际应用中不乏出现一些不响应认证请求或不履行认证付酬的“恶意”节点。下一步还需要就恶意节点淘汰后无线自组网的抗毁顽存性进行深入研究。

[1] 黄后彪，罗长远，宋玉龙. 航空自组网漫游接入认证方案[J].计算机应用研究，2013，30(2)：500-502.

HUANG Houbiao，LUO Changyuan，SONG Yulong. Authentication scheme for roaming in aeronautical ad hoc networks[J]. Application Research of Computers, 2013，30(2)：500-502. (in Chinese)

[2] 祝世雄，罗长远，安红章，等.无线通信网络安全技术[M].北京：国防工业出版社，2014:170-190.

[3] 郭晶晶，马建峰，李琦，等. 基于博弈论的移动自组织网络的信任管理方法[J].通信学报，2014,35(11)：50-58.

GUO Jingjing, MA Jianfeng, LI Qi, et al. Game theory based trust management method for mobile ad hoc networks[J]. Journal on Communications, 2014,35(11)：50-58. (in Chinese)

[4] 闻英友，赵博，赵宏. 基于博弈理论的移动自组网激励机制研究[J].通信学报，2014，35(4)：49-52.

WEN Yingyou, ZHAO Bo, ZHAO Hong. Study on game-based incentive mechanism of mobile ad hoc network[J]. Journal on Communications,2014，35(4)：49-52.(in Chinese)

[5] 刘志新，申妍燕，关新平.一种基于VCG 拍卖的分布式网络资源分配机制[J].电子学报，2010，38(8)：1929-1932.

LIU Zhixin, SHEN Yanyan, GUAN Xinping. A VCG auction based distributed mechanism for network resource allocation[J]. Acta Electronica Sinica, 2010，38(8)：1929-1932. (in Chinese)

[6] 黄河.网上采购组合拍卖研究[D].北京：清华大学，2006.

HUANG He. Study on online procurement combinatorial auctions[D]. Beijing: Tsinghua University, 2006.(in Chinese)

[7] 刘岩，张国印，何金洲，等. 基于贝叶斯博弈的MP2P高性能安全资源节点选择策略[J].通信学报，2016,37(1)：100-105.

LIU Yan, ZHANG Guoyin, HE Jinzhou, et al. MP2P high capacity and security resource node selection strategy based on Bayesian game[J]. Journal on Communications, 2016,37(1)：100-105. (in Chinese)

[8] 许力，陈志德，黄川.博弈理论在无线网络中的应用[M].北京：科学出版社，2012：85.

[9] 高丽，赵海峰，穆晓敏. 改进的基于合作博弈的资源分配和接入控制策略[J].电讯技术，2012，52(7)：1183-1188.

GAO Li , ZHAO Haifeng, MU Xiaomin. Improved resource allocation based on cooperative game and access control policy[J].Telecommunication Engineering, 2012，52(7)：1183-1188. (in Chinese)

[10] 范思遐，周奇才，熊肖磊，等. 一种动态博弈的多agent合作机制模型[J].东北大学学报(自然科学版)，2015,36(1)：114-118.

FAN Sixia，ZHOU Qicai，XIONG Xiaolei，et al. Multi-agent cooperation mechanism model based on dynamic game[J].Journal of Northeastern University(Natural Science),2015,36(1)：114-118. (in Chinese)

[11] TADELIS S.博弈论导论[M]. 李井奎,译.北京：中国人民大学出版社:2015：282-291.

[12] FUDENBERG D, TIROLE J.博弈论[M]. 黄涛，郭凯，龚鹏,等译.北京：中国人民大学出版社，2010：220-226.

[13] 丁丁，罗四维，艾丽华. 基于双向拍卖的适应性云计算资源分配机制[J].通信学报，2012,33(Z1)：136-138.

DING Ding, LUO Siwei, AI Lihua. Adaptive double auction mechanism for cloud resource allocation[J].Journal on Communications, 2012,33(Z1)：136-138. (in Chinese)

[14] 王辛果.一种高效的无线自组网全网可靠广播协议[J].电讯技术，2015，55 (7)：769-772．

WANG Xinguo．An efficient network wide reliable broadcast protocol for wireless Ad Hoc networks[J]．Telecommunication Engineering，2015，55(7)：769-772．(in Chinese)

GameTheoryBasedDynamicAccessIncentiveMechanismofWirelessAdHocNetworks

WANG Hong1,2,LI Jianhua1,CUI Qiong1
(1.Information and Navigation College，Air Force Engineering University,Xi′an 710077,China;2.Information and Communication College,National University of Defense Technology,Xi′an 710106,China)

The nodes′ limited energy in wireless ad hoc network makes the nodes in the network not respond a recruit node′s access request vigorously. In order to motivate nodes to participate in the authentication,the Vickrey-Clarke-Groves(VCG) mechanism is combined with the public-goods supplying theory,and the access incentive mechanism for wireless ad hoc network is proposed. Furthermore,how to find the authentication’s node is given and how much income/pay the authentication node gets/needs is presented with the study of energy consumption. It is proved theoretically that the mechanism possesses strategy-proof,individual rational and budget-balanced. Meanwhile,game between individual and collectivity is analyzed according to different parameter configuration in the example of this paper,which verifies that the equilibrium can effectively motivate all nodes′ cooperation,and all nodes should participate in a recruit node′s authentication vigorously for its own profit.

wireless ad hoc network;access authentication;game theory;incentive mechanism

date:2016-12-30；Revised date：2017-06-20

国家自然科学基金资助项目(61401499, 61174162)

**通信作者：whongger2006@sina.com Corresponding author：whongger2006@sina.com

TN918；O225

A

1001-893X(2017)10-1177-07

王宏(1979—)，男，陕西澄城人，博士研究生，讲师，主要研究方向为无线自组网的信任管理；

Email：whongger2006@sina.com

李建华(1965—)，男，陕西白水人，博士，教授、博士生导师，主要研究方向为空天信息网络作战运用；

崔琼(1990—)，女，河南林州人，博士研究生，主要研究方向为信息系统网络复杂性分析技术。

10.3969/j.issn.1001-893x.2017.10.013

王宏，李建华，崔琼.基于博弈论的无线自组网动态接入激励机制[J].电讯技术，2017,57(10):1177-1183.[WANG Hong,LI Jianhua,CUI Qiong.Game theory based dynamic access incentive mechanism of wireless ad hoc networks[J].Telecommunication Engineering,2017,57(10):1177-1183.]

2016-12-30；

2017-06-20