基于博弈论的无线Mesh网络信任评估模型

宋佳佳,孙彦武

(嘉兴学院,a.数理与信息工程学院;b.外国语学院,浙江嘉兴314000)

基于博弈论的无线Mesh网络信任评估模型

宋佳佳a,孙彦武b

(嘉兴学院,a.数理与信息工程学院;b.外国语学院,浙江嘉兴314000)

无线Mesh网络中的节点具有动态性和异构性,为解决节点的自私性问题,引入了节点的能量属性,提出了基于博弈论的无线Mesh网络信任评估模型,节点的信任评估值由信任博弈分量与节点信任直接观察分量结合的方式,使节点选择理性策略以获取最优行为结果,达到网络数据包转发负载均衡,有效评价了节点的交互行为并抑制了自私节点.

无线Mesh;博弈论;节点能量;信任评价;激励

随着多网融合技术的不断发展,无线Mesh网络作为一种基于多跳路由(multi-hop)、对等网络技术的新型网络结构,即在有限的发射功率下,采用多跳技术实现流量融合,解决了无线接入“最后一公里”的瓶颈问题.[1]无线Mesh网络结合了Ad Hoc网和传统无线网络的优势,有部署快速、组网灵活、网络覆盖率高、非视距传输(NLOS)强的优点,尤其是在移动性、可靠性和自组织性等方面更灵活便捷,并可以用来提高无线网状网的容量和信道的利用率.因此,无线Mesh网络广泛运用于政府、企业、社区、校园网建设和临时应急指挥网络等场所.如图1所示,无线Mesh网络提供了一种层次结构,其中网状路由器节点组成了无线Mesh的骨干网,它们一起为无线Mesh网和其他接入节点提供网络的无线接入.

随着手机等各类智能终端用户的快速增加和无线Mesh网络运用范围的不断扩大,[2]对无线Mesh网络的稳定性、适用性和安全性提出了更高的要求.但由于泛在结构和无线传输信道的开放性,无线Mesh网络也面临多种安全威胁,包括窃听、截获、伪装及拒绝服务等.[3]网络中许多服务和功能都必须依靠节点之间的相互协作来完成.但当实际的网络节点分别属于不同组织时,网络节点会出于自身处理能力、带宽资源、存储空间等方面的考虑,有一定的自私性,即不愿意消耗自身的能量和计算资源去协助其他节点转发数据,这样会影响无线网络正常的路由和数据转发功能.

图1 无线Mesh网络拓扑结构

如何激励网络中的自私节点进行合作以提高网络整体性能是无线网络研究领域面临的重要挑战之一.针对节点自私问题,目前主要采用两类机制来处理:基于信任度的信任机制和基于非合作博弈的激励机制.[4]前者通过对网络节点交互行为的记录和审计来综合评定节点的合作行为,对不合作的节点进行惩罚.而后者是借鉴了经济学和博弈论的相关理论,对提供服务的合作节点进行相应的有偿激励.

文献[5]提出了基于历史效应和未来效应的信誉系统,历史行为会对节点当前交互行为产生影响,但信誉值的更新速度比较滞后.看门狗和选路人算法用来监控和防止节点的异常行为,但这种算法的问题是没有区分节点拒绝转发数据是恶意还是物理原因,并对恶意节点没有惩罚措施.[6]为了激励节点转发数据而增设的计数器机制,在一定程度上激励了自私节点的转发数据包,但增加了网络开销.[7]解决中间节点是否转发数据包的Spirte机制,是通过对节点支付转发开销而使节点收益,虽然有效激励了链路上的各节点转发数据包,但没有实现预算平衡.[8]

在通信节点信任评价的基础上,利用博弈论对高信誉度节点即信任节点动态博弈,产生优良节点的策略结合,达到节点间信道分配算法最优和网络资源的协同管理.而面对竞争环境中资源共享和分配问题,博弈论作为一种理想的基础工具成为研究和分析动态频谱共享技术的重要方法.还有人提出了基于议价(pricing)或仲裁(referee)博弈方法的信道资源分配方法,或使用了不完全信息贝叶斯博弈解决了无线网络中普通节点和恶意节点的识别和共存问题.[9-10]而将博弈论运用到云终端客户的行为中,用不完全信息动态博弈对云端客户的类型、可信等级进行不同的访问控制,根据博弈结果动态地调整用户的信任等级,从而有效降低了恶意云端客户的访问请求,提高了云服务端的服务质量.[11]

在上述基础上,可建立基于博弈论的无线Mesh网络信任管理机制,如图2所示,通过对节点不同行为策略的分析以获取节点的最好行为结果,而节点的信任博弈分量和直接观察分量直接决定了节点的信任评估值,信任度的高低与节点是否可以为邻居转发数据包相关联,无线Mesh网络中节点的交易风险会有所控制并达到网络的最佳效用.

图2 基于博弈论的信任机制

1 信任管理机制模型

在基于博弈论的信任模型中,对参与网络交互节点的属性进行如下定义:

参与者:无线Mesh网络中的节点类型θ,包括普通节点和自私节点;

行动集:参与者的行动依赖于它的类型,普通节点的行动集Ai＝{a1,a2}＝{提供服务,转发数据包},自私节点的行动集合Ai＝{a3,a4}＝{享受服务,不转发数据包};

支付:节点因可信提供服务转发数据包的开销,即能量消耗为Ei;节点因可信成功转发数据包的收益为Ui;节点发出请求服务的开销为Ci;节点拒绝服务不转发数据包时所获得的惩罚为Pi;

效用函数:节点提供服务所获取的收益λi(a,θ);节点在该策略下所需付出的成本为μi(a,θ);节点类型为θ的节点vi的效用函数为:

只有当a≠0,且μi(a,θ)≥0时,节点vi才有动机参与博弈.

在网络中的每个节点在某t时刻的属性集为Θ＝{θi(t),Ri(t),Hi(t),|Ni|(t)},其中θi(t)为节点能量利用率,Ri(t)为节点信誉度,Hi(t)为节点交互历史记录,|Ni|(t)为当前节点的邻居节点数.暂时不考虑时间因素的影响,节点vi的的属性集合为ΘI＝{θi,Ri,Hi,|Ni|},即为节点vi的私人信息.Hij(t)＝{fji,Dij}为t时刻vi和vj的数据转发记录,其中fji为t时刻vj为vi转发的数据包数量,Dij为vi要求vj转发的数据包总数.

2 基于博弈论的信任关系的建立

由于没有历史交易记录,当有新节点加入无线Mesh网络时,需要在网的节点对新加入节点进行信任评估.本模型利用新加入节点在一跳范围内广播发送Hello包来发现邻居节点,再加入邻居节点的邻居表,通过节点之间的博弈形成对新节点的可信度评估,从而形成对新邻居节点的初始信任值.

2.1 无线Mesh网络节点间的相互交互产生信任度

定义无线Mesh网络节点间的相互交互产生信任度如下:

其中α为权重因子,表示对节点的博弈分量和直接信任分量的偏好程度,若对新节点没有历史记录,则α＝0;随着节点交互行为次数的增多,α会逐渐增大.Tgij为节点交互的博弈分量,即节点vi根据当前网络环境和节点属性集对节点vj的信任评估值.Twij为节点的直接信任分量,即通过节点直接观察得出的信任评估值.

2.2 节点的博弈分量

定义节点的博弈分量为:

对无线网络中的所有节点来说,每个节点都有机会与其邻居节点合作产生交互,节点之间相互策略的选择产生交互信任收益,设节点vi在某一时刻与其邻居节点进行的博弈收益为ui(Ni),μi(Ni| {vj}为节点vi和除去节点vj后的其他邻居节点进行博弈产生的收益,故Δμij＝μi(Ni)-μi(Ni| {vj})表示节点vj对节点vi收益所起的作用,若Δμij}0,则表示节点vj的加入使得节点vi增加了收益,反之则表示收益降低,由此可视节点vj不可信任或信任度较低.

2.3 直接信任分量

定义直接信任分量为:节点的直接信任分量是节点直接交互而获得的观察值,第t次的信任评估值使用第t-1次节点交互行为的记录值来计算.

其中,fji(t)和Dij(t)是第t-1次信任评估后节点vi和vj相互交易的累积记录信息.η为惩罚因子,表示对节点自私行为的惩罚力度.

将节点vi和vj历史上多次的交互结果的总数聚合为当前节点的最新信任评估值,假设观察时间窗口值为κτ,其中κ≥1是观察周期,则第m次的直接信任分量为:

式中κ作为信任评估的两个节点的历史交互次数,当m＝κ时,可以把历史上两个节点的所有交互结果的聚合作为最终的信任评价.

2.4 新加入节点信任关系初始化步骤

Step1:加入新节点,更新邻居集Ni

a)节点vi在当前网络一跳范围内广播发送请求hello包,令TTL＝1;

b)收到hello包的节点vj发送回执reply(j)给节点vi,并将vi加入自己的邻居表里;

c)在一个生存周期内,节点vi根据收到的reply(j)构建自己的邻居集;

Step2:更新信任值Tji

a)节点vi与节点vj进行博弈并计算和;

b)从邻居表读取节点vi的历史记录,并统计节点vi为vj实际转发的分组数量fij和Dji;

c)根据公式计算Tji.

Step3:更新各节点的信息表和属性表.

上述步骤能够实时更新节点的信任评估并更新节点属性表,根据节点对邻居节点的信任度变化情况,反映出当前网络拓扑变化及用户行为的变化情况,使得网络中个点之间保持最新的信任关系,在节点vi的邻居范围内,信任关系收敛的速度比较快.

3 实验效果分析

具体的实验环境如下:2.00 GHz Intel Pentium双核处理器,2GB内存,320G硬盘,Windows 7操作系统,实验软件为Matlab R2009a搭建的仿真平台.Matlab是用于算法开发、数据可视化及数据分析、计算的功能强大的交互式程序设计及建模环境,在本实验中,主要用于模拟环境中节点的仿真以及节点之间信任信息的计算分析.

通过设置不同的值来验证博弈过程中的信任管理机制,假设规定每个节点转发数据包所消耗的能量资源为0.005单位,在每一个评价周期τ内,节点vi向所有的邻居节点总共发送50个数据包,每个邻居节点获得的分组数与其当前的信任评估值有关,信任评估值高的节点可以获得更多转发数据包的机会.当节点vi加入网络先进入就近节点vj,vk的邻居表进行信任评估,设定观察时间窗口值为0,1τ,2τ,3τ,…,20τ,即m＝0,1,2,3,…20时的信任值Tij、Tik的变化情况.节点vi的属性为Θ＝{0.8,0.5,0,|50|(t)},表示节点vi的能量利用率为0.8,初始信誉值为0.5,新进节点的交易历史为0.

权重因子α反映了节点对信任分量的偏好程度,若没有直接观察分量,α＝0,节点的信任评估值由节点博弈分量决定;若节点只有一个邻居,则α＝1,即完全依赖邻居节点;随着节点直接观察分量的不断获取,信任评估值会由节点博弈分量和直接观察分量共同决定,α不断增大.η为惩罚因子反应对消极节点的惩罚情况,取值为1.

图3反映了节点vi随着时间窗口信任度的变化情况,在初始时由于vi是新加入节点没有历史交互记录所以信任度比较低,随着时间窗口的增加,节点vi的信任度呈现逐步增加的态势,节点对邻居节点的选择偏向于丢包率小的节点,而直接交互记录是节点信任评估最重要的依据.

图3 节点i的信任度变化

但随着交互次数的不断增多,Tij有所减小,而Tik有所增加,这是因为转发数据包量的增加过多了消耗了节点vj的能量,而节点vk的能量优势在博弈分量中得以加强,如图4所示.结果证明,过多的转发数据包会消耗节点自身能量.

图4 新加入节点博弈分量的变化

在实验中,如图5所示,假设节点vk在时间窗口m＝15时降低了自己的丢包率,可以看出Tik的值逐渐增大,同时Tij的值逐渐减小,这是由于节点vk分担了节点vj的转发数据包,减轻了vj的转发负载,vk帮助vj转发了更多的数据包,获得了更多的信任,那么相应的博弈分量随着vk转发数据的增多而相应减少.

图5 丢包率减少后节点信任度变化

4 结论

实验结果表明,当有新节点加入网络时,在线节点需要更新自己的邻居并重新评估其邻居的信任度.当邻居节点的数量增加时,意味着对一个节点会有更多的邻居节点为其转发数据包,自私节点会更少的为节点服务,当邻居数量减少时,节点对剩下邻居的转发依赖也会有所增加.节点的能量属性会随着时间窗口值的增大和节点与邻居节点交互行为的变化而不断发生变化,节点在选择交互对象的时候会依据能量属性和信任度来进行选择,自私节点不能因为自身能量消耗少来获得数据转发权利,自身的信任度也不随之增强.

基于博弈论的无线Mesh网络信任管理机制利用节点的能量属性进行博弈,在节点信任关系建立之后,就可以根据节点邻居表中信誉评估值即信任的博弈分量和节点的直接观察分量进行节点信任度的比较,从而获得良好的策略结合以产生最优的行为结果,使得网络可以获得最大的效用并降低节点间的交易风险.

[1]SGORA A,VERGADOS D,CHATZIMISIOS P.IEEE 802.11s Wireless Mesh Networks:Challenges and Perspectives[J]. MOBILIGHT,LNICST,2009,13(1):263-271.

[2]中国互联网络信息中心.第33次中国互联网络发展状况统计报告[R].北京:中国互联网络信息中心,2014:5-80.

[3]仵国锋.认知无线Mesh网络若干关键技术研究[D].郑州:解放军信息工程大学,2011.12:20-75.

[4]JOSANG A,ISMAIL R,BOYD C.A survey of trust and reputation systems for online service provision[J].Decision Support Systems,2007,43(2):618-644

[5]郭彩丽,冯春燕,曾志民.认知无线电网络技术及应用[M].北京:电子工业出版社,2010:12-91.

[6]MARTI S,GIULI T J,LAI K,et al.Mitigating routing misbehavior in mobile ad hoc networks[M]//Proc.of the ACM MobiCom 2000.New York:ACM Press,2000:255-265.

[7]BUTTYAN L,HUBAUX J.Stimulating cooperation in self-organizing mobile ad hoc networks[J].ACM/Kluwer Mobile Networks and Applications,2003,8(5):579-582.

[8]Zhong S,Chen J,Yang YR.Sprite:A simple cheat-proof credit-based system for mobile ad hoc network[M]//Proc.of the IEEE INFOCOM 2003,Vol3.Washington:IEEE Computer Society,2003,1987-1997.

[9]姬文江,马建锋,田有亮.无线Mesh网中一种基于博弈论的公平性路由协议[J].通讯学报,2012,33(11):17-23.

[10]Wenjing Wang,M.Chatterjee,K.Kwiat.Coexistence with malicious nodes:A game theoretic approach[M]//Proc.International Conference on Game Theory for Networks(GameNets’09).Istanbul:IEEE Press,2009:277-286.

[11]陈亚睿,田立勤,杨扬.云计算环境下基于动态博弈论的用户行为模型与分析[J].电子学报,2011,39(8):1818 -1823.

(责任编辑 刘伟侠)

Trust Evaluation Model Based on Game Theory in Wireless Mesh Networks

Song Jiajia,Sun Yanwu
(a.College of Mathematics Physics and Information Engineering; b.College of Foreign Studies,Jiaxing University,Jiaxing,Zhejiang 314000)

Nodes in wireless Mesh network has dynamic and heterogeneous attributes,in order to solve the problem of selfishness,energy attribute of nodes and the game theory are introduced into the paper,it proposed the trust evaluation model based on game theory wireless Mesh network.The value of the node’s trust evaluation is divided into two parts,trust game component and direct observation component,so the nodes can choose the rational strategy to obtain the optimal behavior results,then achieve load balancing of the network in data packet forwarding.Finally,the model evaluated the convergence behavior of node and inhibited the selfish nodes effectively.

wireless Mesh;game theory;node energy;trust evaluation;incentive

TP393.08

A.

1671-3079(2014)03-0082-06

10.3969 /i.issn.1671-3079.2014.03.015

2014-03-12

宋佳佳(1986- ),女,嘉兴学院数理与信息工程学院教师,硕士,主要研究方向为计算机网络技术与网络安全.

时间:2014-04-10 14:06 网络出版地址:http://www.cnki.net/kcms/detail/33.1273.Z.20140519.1650.008.html