基于节点信任度和博弈论的Ad hoc网络路由算法

刘　欣，李校林,3，夏小霞

(1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.重庆邮电大学 通信新技术应用研究中心，重庆 400065；3.重庆信科设计有限公司，重庆 400065)



基于节点信任度和博弈论的Ad hoc网络路由算法

刘欣1,2，李校林1,2,3，夏小霞1

(1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.重庆邮电大学 通信新技术应用研究中心，重庆 400065；3.重庆信科设计有限公司，重庆 400065)

摘要：节点能耗和路径可靠性是移动自组织网络路由需要考虑的关键因素。为了提高能量利用率以及实现网络收益的最大化，在节点理性、自私的前提下，运用博弈论方法建立了转发节点选择的重复博弈模型，设计了节点信任度评价函数，并采用惩戒机制来威慑自私节点，迫使其自愿采取协同合作的策略。仿真结果表明，提出的路由算法能够均衡网络的能量消耗，提高分组投递率，延长网络的生存时间。

关键词：Ad hoc网络；重复博弈；信任度评价；惩戒机制；路由

0引言

移动自组织网络(mobile ad hoc networks, MANET)[1]是一种由无固定基础设施支持的移动节点组成的无线网络，具有开展迅速、无控制中心、灵活组网等优点。由于网络的高度动态性、时变性以及丢失性容易导致链路质量较差，这对Ad hoc网络的传输可靠性造成了影响。另外，节点能量受限以及移动性也为新的路由算法的设计与优化带来了难度。

传统的Ad hoc网络路由协议大致分为2类：一类为按表驱动路由协议，如目的序列距离矢量路由(destination sequenced distance vector routing, DSDV)算法[2]；另一类为按需驱动路由协议，如动态源路由(dynamic source routing, DSR) 算法[3]和按需距离矢量路由(Ad hoc on-demand distance vector, AODV)算法[4]等，这些协议并未考虑节点能量、链路可靠等因素，多采用最小跳数优先策略。但是，基于最小跳数原则设计的路由算法在传输数据时，容易使得部分节点过多地被选为转发节点，造成这些节点能量过快消耗，致使网络生存时间严重缩短。另外，由于节点能量、带宽等资源受限，节点不可避免地会产生自私性。基于理性偏好的考虑，自私节点都希望从其他节点获取收益而不消耗资源。所以，在这种利己性的驱使下，节点的自私性行为对网络性能造成了严重的影响：网络吞吐量下降以及资源浪费。

近年来，不少研究者将博弈理论(game theory)引入路由协议。博弈理论描述了参与者在游戏中的行为，参与者根据所处环境选择对应的策略来获取自身最大收益。在网络中，路由路径的选择过程与博弈类似，数据转发节点同样是根据所处的网络环境来选择相应策略，并实现最大化收益。文献[5]为了解决网络能耗不均衡的问题，引入马尔可夫博弈理论，在能量均衡路由分析的基础上提出了一种马尔科夫博弈的能量均衡路由算法，该算法实现了节点能量的均衡消耗，延长了网络的生命周期。针对节点的自私性与理性偏好，文献[6]采用博弈理论建立了一个基于节点理性偏好的路由博弈模型，并对网络均衡问题进行了分析。但以上算法没有考虑节点间链路可靠性对数据转发造成的影响，也没有对节点存在的自私性问题进行解决。

针对网络中节点的自私性行为，一些激励节点协同合作的方法被提出，如虚拟货币机制、奖励机制、惩戒机制等。文献[7]提出了一种不完全信息的数据包合作机制，利用集中仲裁方式，对节点进行“惩罚”和“奖励”，采用自信概率来影响节点的决策行为。但是此算法依赖于集中控制，不适合分布式自治下的环境。文献[8]将博弈理论运用于无线自组网，提出一种采用虚拟流通方法或者协作信誉制度激励节点间合作的机制。另外，一些研究学者也提出了其他的博弈算法来增强节点间的合作，如文献[9]采用支付价格的方式来补偿节点转发数据所消耗能量和时延，并建立了一种基于价格机制的博弈模型来促进节点之间的合作，文献[10]以博弈理论中的循环囚徒困境模型为基础，提出节点间亲密度的概念，并以此为因子激励节点的合作，有效地改善网络性能。以上算法很好地解决了节点自私行为对网络造成的影响，但未考虑到节点的能量受限性，因此，所提出来的博弈模型并不适合Ad hoc网络能量有限的特点。

在路由选择过程中，节点之间数据的多次传递是重复进行的，并且可以看作是发送方节点与潜在接收节点之间的博弈过程，所以本文在重复博弈模型的基础上综合考虑节点的能量有限性与链路可靠性，提出了一种基于节点信任度和重复博弈的路由选择算法。将路由问题建模为节点之间的博弈问题，由每个节点根据相邻节点的信任度来选择合适的下一跳，逐跳之后形成一条通向目的节点的路径。另外，为了降低自私节点背叛的可能性，算法采用惩戒机制来促使自私节点倾向于选择协同合作策略。通过仿真实验证明，本文提出来的算法能够均衡网络能量消耗，提高网络分组投递率，以及延长网络的生存时间。

1网络系统架构

1.1网络模型及假定

在分析路由问题时将网络拓扑模型采用无向图G=(V,E)表示，V表示拓扑G中的移动节点集合，E表示节点间可双向通信的链路集，其中vi∈V为网络中的一个节点，eij=(vi,vj)∈E为节点vi与vj之间的连接边。s∈V为源节点，d∈{V-{s} }为目的节点。

本文假设网络模型如下。

1) 网络是对称的，且节点随机分布。

2) 网络中的节点具有相同有限的能量，并定义初始能量为Einitial。

3) 网络中的节点具有理性自私性。

4) 网络采用离散的时间模型，每个时隙节点均有一个数据包发送。

5) 网络中节点的最大通信距离为R。

1.2包转发概率模型

由于Ad hoc网络的动态拓扑以及传输多跳性和信道的不可靠性，往往存在数据包因转发失败而重新转发的现象，这会影响网络的分组投递率。定义节点i转发包的数量为Pis(t)，接收包的数量为Pir(t)，则该节点在t时刻的包成功转发概率为

Pi(t)=Pis(t)/Pir(t)

(1)

1.3能耗模型

假设网络中，接收节点收到信号所需能量为Emin，则发射节点发出信号所消耗的能量为

Et(d)=kdnEmin

(2)

(2)式中：k为常系数；d为发射节点与接收节点之间的距离(d≤R)；n为2-4之间的整数值。本文中取n=2，k=1。Et(d)为发射节点传输单位数据需要消耗的能量，如果需要发送m个数据包，则消耗的总能量Etx(m,d)如(3)式所示，接收m个数据包所需消耗的能量如式(4)所示。

Etx(m,d)=m(Eelec+Emind2)

(3)

Erx(m,d)=mEelec

(4)

(3)式中，Eelec为节点在发送与接收数据过程中内部电路所消耗的能量。

所以，对于中继节点而言，传输m个数据包所需消耗的能量为

Ecost(m,d)=Etx(m,d)+Erx(m,d)=

2mEelec+md2Emin

(5)

对于单个节点，在接收与转发数据过程中，其剩余能量为

Eremain(m,d)=Einitial-Ecost(m,d)

(6)

(6)式中：Einitial为节点的初始能量；Ecost(m,d)为转发m个数据包所需消耗的能量，可通过(5)式得到。

2基于信任度的重复转发博弈

2.1一次博弈模型

节点数据包的一次转发可以看作一次博弈过程。假设T取值为1表示节点i发送自己的数据包，取值为0表示放弃发送自己的数据包；Z取值为1表示节点i的邻居节点转发其数据包，取值为0表示其邻居节点放弃为其转发数据包；F取值为1表示节点i愿意转发其他节点的数据包，取值为0表示放弃转发其他节点的数据包；R取值为1表示节点i成功发送自己的数据包，取值为0表示自己的数据包发送失败，且存在如下关系式

(7)

由(7)式可以看出，只有当节点发送数据，且其数据被邻居节点转发时，该节点才算成功发送自身数据(R=1)。

不妨假设当邻居节点合作时，节点成功发送一个包的收益为b，接收一个包的收益为0，则节点i在时隙tj中的收益模型为

ui(R,T,F)=R·b-T·c-F·c·mi

(8)

其中mi为节点i在时隙tj中转发数据包的数目，c为发送一个包的所需消耗的能量。

定义节点i的策略S为(R,T,F) 三元组的取值形式，并规定所有节点都是同时决策。由(9)式可以看出，当节点拒绝转发数据包时，即当F=0，T=1时，无论其邻居节点是否为其转发数据，节点获得的收益总要大于其为别的节点转发数据包获得的收益。因此策略(*, 1 ,0)为整个博弈的优超策略，当全部节点采用该策略时，博弈G将达到纳什均衡[11]，且当策略为(1, 1, 0)时，博弈G达到帕累托最优策略，但该状态下所有节点不转发其他节点数据会导致整个网络的性能下降，显然不是我们期望的。

2.2信任度函数

在数据包转发的过程中，自私节点的决策具有如下特点：①自私节点更加倾向于选择剩余能量较高、包转发成功率较高的相邻节点作为转发节点。②邻居节点在做转发决策时，若其获得的收益越大，其转发的可能性也就越大。因此，为了合理地选择下一跳节点，本文依据节点的包转发概率模型、能耗模型以及收益模型来设计节点信任度评估函数，如(9)式所示。

(9)

(9)式中：Eremain为节点t时刻的剩余能量；Einitial为节点的初始能量；ui为本轮博弈中转发数据包所能获得的收益；Pi(t)为节点在t时刻的包成功转发概率。设计可信度函数是从节点自身角度出发，用于评价邻居节点转发自己数据包的一种度量标准。

2.3惩戒机制

造成节点之间的协作困境是由于节点不会考虑自私行为对将来收益造成影响。若不采用惩罚手段，自私节点不会自愿消耗能量去转发其他节点的数据。因此，本文提出了对于不合作的节点采取惩戒的策略，当节点在上一轮发送数据过程中存在作弊行为，整个网络会立马得知，那么在下一轮博弈的时候，该节点在发送自身数据时会被邻居节点拒绝转发，且节点自身在转发其他节点的数据时得不到任何收益。当后继惩罚损害了其利益，并超过作弊时的短期利益，将会对自私节点产生威慑，迫使该节点采取协同合作的态度。节点在惩罚结束后将继续参与下一轮的路由博弈，其作弊历史会被遗忘。

2.4基于信任度的重复博弈

在Ad hoc网络中，节点的能量是有限的，当节点的剩余能量不足以发送或者转发一个数据包时，我们认为该节点死亡。本文定义上述的重复博弈过程为有限次数的博弈，当网络中死亡节点数目的百分比超过90%时，博弈结束。

根据重复博弈论中的收益评估方式，节点i在时隙tj中k次博弈的总收益Ui是各阶段收益总和的一个折现值，用式(10)表述为

(10)

(10)式中，0<δ<1，该系数越大，节点将来的行为对收益的影响也就越大。

根据ui的定义，可以得出节点在博弈选择的策略以及相应收益，如表1所示。

从表1可以看出，策略DF没有被采用，因为对于理性且自私的节点而言，不发送自身数据而转发其他节点的数据，不仅得不到收益而且还要消耗自身的能量，这种行为显然是不会被采用的。所以本文网络中的节点只有3种可选策略，即S=(FF,FD,DD)。

表1　路由博弈收益矩阵

2.5基于信任度的博弈路由选择算法

本文路由算法通过数据发送节点与潜在接收方节点之间的两两博弈，自组织地建立路由路径。其算法的基本流程描述如下。

步骤1初始化网络参数。

步骤2数据发送方节点向周围的邻居节点发起路由请求，并按式(9)评估所有邻居节点的可信任度。

步骤3比较所有邻居节点的可信任度，选择可信任度值最大的节点作为下一跳为其转发数据。

步骤4如果该节点决定为其转发数据，就会回复路由确定消息并跳到步骤7。若该节点放弃为其转发数据，转入步骤5。

步骤5判断该节点是否为存在自私行为。如果存在，则根据本文设定的惩戒机制对其采取惩罚。否则转入步骤6。

步骤6发送方节点根据信任度值向次优的邻居节点发送路由请求，并转到步骤4。

步骤7重复步骤2-6，直到所有数据发送至目的节点，算法结束。

这种路由方式不仅可以保证数据在转发出去的情况下，尽可能地会去选择剩余能量较高、转发成功率较高的节点作为跳转节点，而且符合节点的理性偏好特性。

3性能评估

本文采用NS2进行仿真实验，将基于IEEE802.11协议中分布式协调机制作为MAC层协议，数据传输率为2 Mbit/s。网络中节点均匀随机分布，且以Random Waypoint Model 方式随机移动，每个节点的通信范围为250 m，节点速度在0-30 m/s之间均匀变化。规定当网络中90%节点死亡时，网络失效。其他仿真参数如表2所示。

为了验证算法性能，将本文算法与文献[10]提出的循环囚徒困境博弈算法进行实验对比。将网络的生命周期、网络能量总耗、分组投递率及网络吞吐量作为评价标准。

图1给出了2种算法的网络生命周期。从图1中可以看出，随着博弈轮数的增加，本文提出的路由算法的节点死亡数要低于循环囚徒困境算法，这是因为循环囚徒困境算法并没有考虑节点能量有限问题，在路由通信中，能量消耗不均衡缩短了网络的生命周期。而本文算法考虑了节点的剩余能量，将其作为下一跳节点选择的评价指标之一，剩余能量较大的节点更有可能被选为转发节点，这样较低剩余能量的节点被保护。因此，网络的生命周期要优于循环囚徒困境算法。

表2　仿真参数

图1　网络生命周期图Fig.1　Network lifecycle diagram

图2描述了网络的总体能耗。可以看到，本文算法的网络整体能耗增加比较平缓，与循环囚徒困境算法相比，网络整体能耗要低。因为在路由选择时，发送数据方节点倾向于选择更节能的通信方式，有效地降低和均衡了网络的能量消耗。此外，本文算法考虑了节点的包转发概率，成功率较高的节点在路由过程中倾向于被选择，这在一定程度上避免了因数据转发失败而重传造成的能量浪费。总而言之，本文算法在能耗均衡方面表现出较好的效果。

图3给出了节点在不同移动速度下的分组投递率，随着节点平均移动速度增加，本文算法的分组投递率下降趋势要比循环囚徒困境算法缓慢。循环囚徒困境算法根据节点间的亲密度以及自身收益来决定采取合作或背叛策略，在一定程度上激励了节点间的合作，但该算法没有对选择背叛的自私节点进行惩戒，也没有考虑链路的可靠性，分组仍然存在重传、丢失现象。而本文算法不仅考虑了节点的包转发成功率，同时也针对节点背叛行为建立惩戒机制，有效地提高了分组的成功投递率，保证了链路的可靠性。

图2　网络总能耗图Fig.2　Network total energy diagram

图3　分组投递率图Fig.3　Rate of delivering packet diagram

网络吞吐率是网络性能的一个重要指标，为了考察2种算法对网络吞吐率的影响，本文进行了实验对比，如图4所示。由于网络存在自私节点，循环囚徒算法并没有对节点的自私行为进行威慑，且该算法没有考虑能量均衡消耗，部分节点消耗过快，吞吐率在生存后期迅速下降。而本文算法采用惩戒机制，允许自私节点在受到惩罚后重新恢复合作，同时，算法保持了能耗均衡状态，所以吞吐率保持较长时间的高位。

4总结

本文提出了一种基于节点信任度和博弈理论的Ad hoc网络路由选择算法。在考虑节点的理性偏好条件下，设计了与节点剩余能量、包成功转发率及路由博弈收益相关的可信任函数。发送数据方通过评估邻居节点的可信任度来合理选择下一跳。为了防止节点的自私性行为，又采用惩戒机制来迫使节点协同合作。实验结果表明，该算法能够均衡网络的能量消耗，提高分组投递率、网络吞吐量，以及延长网络的生存时间。

图4　网络吞吐率图Fig.4　Network throughput rate diagram

参考文献：

[1]王博，陈训逊. ad hoc网络中一种基于信任模型的机会路由算法[J]. 通信学报，2013，34(9)：92-104.

WANG Bo, CHEN Xunxun. Opportunistic routing algorithm based on trust model for ad hoc network[J]. Journal on Communication，2013，34(9): 92-104.

[2]PERKINS C E, BHAGWAT P. Highly dynamic destination-sequenced distance-vector routing (DSDV) for Mobile Computer[C]// Proc ACM SIGCOMM’94. UK: Computer Communications Review, 1994: 234-244.

[3]JOHNSON D B, MALTZ D A, BROCH Josh. DSR: The dynamic source routing protocol for multihop wireless ad hoc networks[C]// ACM/IEEE. Ad Hoc Networking.USA:Addison Wesley Longman Publishing Co,2001:139-172.

[4]PERKINS C E, ROYER E M. Ad hoc on-demand distance vector routing[C]//IEEE WORKSHOP. Proc of the 2nd IEEE Workshop on Mobile Computer Systems and Applications. USA: IEEE Computer Society, 1990: 90.

[5]董荣胜，马争先，郭云川，等.一种基于马尔科夫博弈的能量均衡路由算发[J]. 计算机学报，2013，36(7):1500-1508.

DONG Rongsheng，MA Zhengxian，GUO Yunchuan,et al. A Markov Game Theory-Based Energy Balance Routing Algorithm[J]. Chinese Journal of Computers，2013，36(7): 1500-1508.

[6]李慧芳，姜胜明，韦岗.无线传感器网络中基于博弈论的路由建模[J].传感技术学报.2007，20(9):2075-2079.

LI Huifang，HIANG Shengming，WEI Gang. Game-Theoretic Modeling on Routing in Wireless Sensor Networks[J]. Chinese Journal of Sensors and Actuators. 2007，20(9)：2075-2079.

[7]ZENG Jia，MU Chundi. Game theory-based energy balance routing with incomplete information in wireless sensor networks[J]. Acta Automatica Sinica，2008，34(3): 317-322.

[8]ZHONG S，CHEN J，YANG Y R. A Simple，Cheat-Proof, Credit-Based System for Mobile Ad hoc Networks[C]// Proceeding of IEEE IOFOCOM. San Francisco，CA，USA：IEEE Press，2003: 1987-1997.

[9]SHASTRY N, ADVE R S. Stimulating Cooperative diversity in wireless ad hoc networks through pricing[C]// In Proc. IEEE intl Conf Commun. Istanbul: IEEE, 2006: 3747-3752.

[10] 何涛，王锁萍. 无线Mesh 网络中基于循环囚徒困境的路由算法[J]. 南京大学学报：自然科学版， 2010，46(5):561-566.

HE Tao, WANG Suoping. A routing algorithm for wireless mesh network based on alternating prisoner’s dilemma[J]. Journal of Nanjing University：Natural Sciences Edition, 2010，46(5)：561-566.

[11] 陆音，石进，谢立. 基于重复博弈的无线自组织网络协作增强模型[J].软件学报，2008，19(3)：755-768.

LU Yin，SHI Jin，XIE Li. Repeated-Game Modeling of Cooperation Enforcement in Wireless Ad Hoc Network[J].Journal of Software，2008，19(3):755-768.

Trust and game theory based routing algorithm for Ad hoc networks

LIU Xin1,2, LI Xiaolin1,2,3, XIA Xiaoxia1

(1.School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications,Chongqing 400065,P.R.China;2. Research Centre for Application of New Communication Technologies,Chongqing University of Posts and Telecommunications,Chongqing 400065,P.R.China;3.Chongqing Information Technology Designing CO.LTD，Chongqing 400065，P.R.China)

Abstract:Energy consumption and path reliability are the key issues in mobile Ad hoc networks. In order to improve energy efficiency and maximize networks payoff, a repeated-game theoretic model is proposed for selecting forwarding nodes under the conditions of selfish and rational nodes, a trust evaluation function is designed, and punishment mechanism is used to deter the selfish nodes and force them to take cooperation strategy. Simulation indicates that the proposed routing algorithm can keep the balance of energy consumption and improve the packet delivery ratio and prolong network lifetime.

Keywords：Ad hoc network；repeated game；trust evaluation；punishment mechanism；routing

DOI：10.3979/j.issn.1673-825X.2016.01.018

收稿日期：2014-04-16

修订日期：2015-03-07通讯作者：刘欣1063657058@qq.com

中图分类号：TP393

文献标志码：A

文章编号：1673-825X(2016)01-0120-05

作者简介：

刘欣(1990-)，男，湖南衡阳，硕士生，主要研究方向为通信新技术、数字图像处理。E-mail：1063657058@qq.com。

李校林(1968-)，男，硕士生导师，正高级

工程师，主要研究方向为新一代移动通信技术、物联网与视频监控技术、天线与电波传播。

夏小霞(1990-)，女，湖南益阳人，硕士生，主要研究方向为移动通信、自组织网络路由算法。E-mail：fighting_xxx@163.com。

(编辑：张诚)