（信号与信息处理专业论文）基于博弈论的节点协作机制研究.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 移动自组网是一种特殊的对等式网络，具有自治性、无基础设施、快速组网的特点， 移动自组网中节点间的通信通过无线信道、由多个节点转发来共同完成，因此，节点合作 与否是实现通信的关键。协同安全机制是解决网络内部恶意节点和自私性节点不合作行为 的有效方法。 将博弈论引入到a dh o c 的节点协作性研究成为目前国际上一种很流行的思路。本文 首先集中介绍了现有的几种将博弈论引入节点协作的方法，在分析借鉴了基于博弈论的惩 罚策略后提出了对于恶意不合作节点的动态阻塞惩罚策略。接着在兼顾节点生存期与效益 的前提下提出了节点能量模型的概念，即根据网络中节点的平均能量限制来划分节点等 级。接着本文提出了一种衡量节点效益的指标：节点自身数据包被转发概率。并引入博弈 论分析在这种模型下，整体网络效益最大时的节点所遵从的转发策略，即本文提出的“针 锋相对策略。接着在现有a o d v 协议基础上加入该“针锋相对 策略，提出了改进的 “针锋相对 a o d v 协议。最后利用n s 2 仿真软件比较了针锋相对路由协议与原a o d v 协议的路由性能，通过比较可以发现，在能量有限情况下，针锋相对路由协议在网络整体 吞吐量等指标上优于传统a o d v 路由协议。除此之外，本文还对节点的恶意不合作行为 进行了仿真，并将前面提出的动态阻塞策略应用到针锋相对路由协议上，进一步解决了协 议的安全问题。 关键字：a dh o c ：博弈论；能量模型；针锋相对协议；动态阻塞策略 南京邮电人学硕士研究生学位论文 a b s t r a c t a b s t r a c t a dh o cn e t w o r ki sam u l t i h o pt e m p o r a r ya u t o n o m o u ss y s t e mo fm o b i l en o d e sw i t h w i r e l e s st r a n s m i t t e r sa n dr e c e i v e r sw i t h o u tt h ea i do fn e t w o r ki n f i - a s t m e t u r e i na dh o en e t w o r k ， n o d e sc o o p e r a t eb yf o r w a r d i n gp a c k e t sf o re a c ho t h e rt oa l l o wt h e mt oc o m m u n i c a t eb e y o n d d i r e c tw i r e l e s st r a n s m i s s i o nr a n g e t h e r e f o r e ，t h ec o o p e r a t i o no fn o d e si sak e yi s s u et o c o m m u n i c a t i o n t h ec o o p e r a t i v es e c u r i t ys c h e m e so f f e rt h er e a s o n a b l ee f f e c t i v es o l u t i o nt o r e s o l v et h eu n c o o p r a t i v eb e h a v i o rw h i c hl a u n c h e db yt h em a l i c i o u sa n ds e l f i s hn o d e si nt h e m o b i l ea dh o cn e t w o r k i th a sb e e np o p u l a rt ou s et h eg a m et h e o r yt om o d e lt h ea dh o en e t w o r kc o o p e r a t i v e p r o b l e mi nr e c e n ty e a r s t h i sp a p e rf i r s ta n a l y s e ss o m em a i nc u r r e n ta p p r o a c h sw h i c hu s et h e g a m et h e o r yt os e t t l et h ec o o p e r a t i v ep r o b l e m ，t h e nb r i n g sf o r t han e wp u n i s h i n gm e a s u r ef o r m a l i c i o u sn o d e sw h i c hd on o tc o o p e r a t eb a s eo nt h ea n a l y s i so fs o m et r a d i t i o n a lp u n i s h i n g m e a s u r e s ，s p e c i a l l yf o rb l o c k i n gw a y a n da s s i g nn a m et oi ta s d y n a m i cb l o c k i n gs t r a t e g y f o r s e e i n gb o t l ls i d e so fn o d e sl i v i n gt i m ea n db e n e f i t , w ei n t r o d u c et h ec o n c e p t i o no ft h ee n e r g y m o d e lo fm o b i l en o d e s ，w h i c hu s e st h ea v e r a g ee n e r g yc o n s t r a i n tt os e g m e n tm o b i l en o d e st o d i f f e r e n td e g r e e s t h ep a c ts u g g e s t san e wi n d e xt om e a s u r et h ee f f e c to fan o d e ：t h en o r m a l i z e d a c c e p t a n c er a t ef n a r ) ，u s e st h eg a m et h e o r yt oa n a l y s et h em o s te f f e c t i v es t r a t e g yw h i c hn o d e o b s e r v et og a i nt h em a xb e n e f i ti nt h ew h o l en e t w o r ki nt h ee n e r g ym o d e la b o v e w ea s s i g n n a m et ot h es t r a t e g y 勰 t i t - f o r - t a t t h e nt h i sp a p e rp r e s e n t st h et i t - f o r - t a tr o u t i n gp r o t o c o l b a s eo nt h et r a d i t i o n a la o d v p r o t o c o l ，l a s t l yd i s c u s s e st h es e c u r i t yi s s u ea b o u tt h en e wr o u t i n g p r o t o c 0 1 w es u g g e s tt h ea b o v ed y n a m i cb l o c k i n gs t r a t e g yt os o l v et h i sp r o b l e m t h i sp a p e ru s e st h en e t w o r k - s i m u l a t i o ns o f t w a r et oa n a l y s et h ep e r f o r m a n c eo ft h e t i t - f o r - t a tr o u t i n gp r o t o c o l ，t h e nc o m p a r e sb e t w e e nt h et i t f o r - t a tr o u t i n gp r o t o c o la n da o d v p r o t o c 0 1 r e s u l t ss h o w st h a tu n d e rt h ec o n d i t i o no fe n e r g yc o n s t r a i n t , t h et i t - f o r - t a tr o u t i n g p r o t o c o l sp e r f o r m a n c ec a nb eb e t t e r l a s t l yt h i sp a p e ra s s o c i a t e st h ed y n a m i cb l o c k i n gs t r a t e g y a b o v et ot h et i t - f o r t a tr o u t i n gp r o t o c o l ，a n di ns o m ed e g r e e ，i ts l o v et h es e c u r i t yi s s u e s k e yw o r d s ：a dh o c ；g a m et h e o r y ；e n e r g ym o d e l ；t i t - f o r - t a tp r o t o c o l ；d y n a m i cb l o c k i n g s t r a t e g y i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 ，7 研究生签名：弋。心j 日期沙。，州 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所 送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保 存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保 密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内 容。论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：吣已、 导师签名： 日期： i ? 乓 丢4 己 厶 歹泸7 ，t 1 i l 星些鱼查兰壁i ：竺墨竺兰丝堡苎墨= 璺堕兰 i ia d h o e 网络简介 第一章绪论 a dh o c i l 网络是指一组带有无线收发装置的移动终端组成的一个多跳自组织系统。移 动终端具有路由功能，可以通过无线连接构成任意的网络拓扑，这种网络可以独立工作。 a dv o c 网络中，每个移动终端兼备路由器和主机的两种功能：作为主机，终端需要运行面 向用户的应用程序：作为路由器终端需要运行相应的路由协议，根据路由策略和路由表 参与分组转发和路由维护工作。a d h o c 网络的拓扑结构是动态变化的，其内部节点可以以 任何方式动态地和其他节点联系，但是由于终端的无线传输范围有限，两个无法直接通信 的终端节点往往通过多个中间节点的转发实现通信，所以它又被称为多跳无线网、自组织 网络、无固定设施的网络或者对等网络。这种无中心又不依赖固有基础设施的结构使得它 的组网十分方便快捷。因此特别适用于某些特殊紧急场合，如：灾难现场营救、战时出现 重要线路故障需要进行临时无线联络等。 j i劳萨萨。搿萨劳 图l1 a d h o c 网络结构 a dh o c 网络与传统的移动网络一个最显著的区别是：a dh o c 网络中没有基站，也没 有移动交换中心。如果两个移动节点在无线通讯范围内，它们可以直接通过无线信道建立 连接，否则则需要利用这两个通信节点以外的邻居节点来转发报文，以实现通信。a d h o c 网络中的节点不依赖于任何的网络结构，所有节点都同时具有主机和路由器两种功能，节 点通过分层的网络协议和分布式算法进行沟通和协调，实现网络的自组织化。因此，a dh o c 网络比传统的网络更加灵活、健壮，适台于些特定的场合。 与其它传统通信网络相比，a d h o c 网络具有以下显著特点： 南京邮【乜大学硕上研究生学位论文第一章绪论 动态变化的网络拓扑：a dh o e 网络中，移动终端能够以任意速度和任意方式在网中移 动，并可以随时关闭电台，加上无线发送装置的天线类型多种多样、发送功率的变化、无 线信道间的互相干扰、地形和天气等综合因素的影响，移动终端间通过无线信道形成的网 络拓扑随时可能发生变化，而且变化的方式和速度都难以预测。 无中心和自组织性：a dh o c 网络中没有绝对的控制中心，所有节点的地位平等，即是 一个对等网络。在a dh o e 网络中，节点通过分层的网络协议和分布式算法来协调彼此的 行为，节点可以随时地加入或者离开该网络，任何节点的故障不会影响整个网络的正常运 行，具有很强的抗毁性。 受限的无线传输带宽：a dh o e 网络采用无线传输技术作为底层通信手段，由于无线信 道本身的物理特性，它所能提供的网络带宽相对有线信道要低得多。此外，考虑到竞争共 享无线信道产生的冲突、信号衰减、噪音和信道之间干扰等多种因素，移动终端得到的实 际带宽远远小于理论上的最大带宽。 移动终端的便携性及能量受限：在a dh o e 网络中，用户终端多为笔记本，手持设备 或者是车载设备，这样的移动终端便携性固然好，但能量受限，并且其高度的便携性限制 了这些移动设备开展复杂工作的能力。因此，如何高效地使用节点的电能和延长工作时间 ， 是一个突出的问题。 多跳路由：a dh o e 网络中移动节点的有限能量限制了节点的发射功率。当一个节点要 和该节点通信范围以外的节点进行通信时，就需要中间节点的转发，即需要多跳。 安全性较差。a dh o e 网络是一种特殊的无线移动网络，由于采用无线信道、有限电源、 分布式控制等技术，再加上“多跳 的机制，即可能多个节点都参与到一个消息的转发中， 使得它更加容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡眠 等网络攻击。信道加 密、抗干扰、用户认证和其它安全措施都需要特别考虑。 1 2 无线网络协作的特点 随着a dh o e 网络日益成熟，网络本身能提供一种不受限制的连接。为了将一个数据 包从源节点发送到目的节点，中间需要好几个节点进行多跳传输。但是由于a dh o e 手持 设备普遍存在的供电特点，即主要由电池供电，以往的路由协议普遍基于一个假设：任何 一个节点都会毫无保留的路由非其节点产生的数据包。在能量有限情况下这种假设可能不 是随时成立。 请看下面一种典型情况：假设一个小组在野外使用若干台笔记本电脑，需要在保持数 2 南京邮电大学硕l 研究生学位论文第一章绪论 据连接的前提下工作一整天。如果每台电脑都毫无保留的接受其他终端的请求转发每一个 数据包，很可能造成每台电脑的电池容量在工作日结束前耗尽。反之，如果每台电脑都拒 绝转发数据包，将能量只用于传递自己产生的数据包，则整个网络将陷于瘫痪。因此任何 一台终端在延长自己工作时间与服务其他终端中找到平衡。 节点的协同工作问题近几年很受关注。在文献嘲至【1 4 】中就节点的协同工作问题进行 论述。在文献【6 】与嗍中，讨论了行为不端节点的种种表现及其带来的问题，在【刀、【9 】与【1 4 j 中，引入市场机制来激励节点协作，在文酬9 】中，提出了两种算法，节点是否路由数据包 根据每一次节点“会议协商的结果。在文献【1 2 】中，作者分析了在协作管理与激励机制下 自私节点的不对称行为。 目前关于a dh o c 节点的协作问题有两大思路：第一就是引入第三方现金管理系统， 对每个节点的行为进行记录，根据节点的行为派发现金，节点每次发送自己的数据包都必 须消耗一定额度的现金。节点需要得到现金就必须去转发其他节点的数据包。第二种就是 整个网络系统靠其他节点，一般指邻居节点，来评判本节点每次行为，当发现此节点为不 合作的节点时，采用通知孤立的方法，即联合所有节点将其从网络中孤立出来，不发送其 任何数据包。任何一种思路都是在节点发送自身数据包与转发其他节点数据包中找到平 衡，每个节点都达到平衡状态时，整个网路进入一个稳态。这个平衡在博弈论中称为纳什 均衡。本文介绍的方法就是在达到均衡后实现网络效益最大化。 1 3 本文主要工作与章节安排 本论文主要包括以下两部分工作： 第一部分首先简要介绍博弈论在网络领域的研究进展，介绍近年来使用博弈论进行无 线自组织网络协作研究的方法思路，特别是建立不同的数学模型，并指出其中方法的优点 与局限，并且从已有的协作方式中总结出一种新型的协作方式。 第二部分接着将利用博弈论对实际场景进行建模，用于探讨能量限制的前提下无线自 组织网络中用户节点的自私行为以及提出本文的策略，达到网络效益最大化。接下来介绍 本文剩余章节的主要内容。 第二章首先介绍博弈论的基本概念，接着将讨论博弈论在网络中的现有应用，主要包 括路由算法、流量控制、拥塞控制和网络安全等方面的应用。这些应用表明，博弈论是分 析网络资源合理分配问题中的一个强大工具。 第三章对a dh o c 网络的协作特点进行了研究，对节点的协同工作方法进行总结，分 南京邮电大学硕上研究生学位论文第一章绪论 析了目前几种主流的将博弈论引入节点协作的方法，指出几种方法存在的不足与局限性， 并在借鉴之前方法的基础上提出一种新的基于动态阻塞的惩罚机制。 第四章首先简要介绍a o d v 路由协议，主要研究了在单个节点能量限制基础上，构建 所有节点的能量模型，提出“针锋相对 的概念，即每个节点收到数据包后根据以往其他 节点的行为进行判断，作出是否转发的决策。接着提出单纯实施针锋相对策略存在的安全 问题。再将传统a o d v 路由协议与“针锋相对 相结合，提出路由算法。最后将第三章的 动态阻塞与a o d v 路由协议相结合，一定程度上解决了之前提出的安全问题。 第五章是对传统a o d v 路由协议与本章中创新的“针锋相对”结合的路由协议以及动 态阻塞策略进行仿真，比较得出加入“针锋相对一后加大了整个网络的吞吐量。 第六章对前五章工作进行了总结，并对今后的工作开展加以展望。 4 南京邮电大学硕i = 研究生学位论文 第二章博弈论及其在网络中的应用 第二章博弈论及其在网络中的应用 本章首先简要介绍了博弈论的一些基本概念，接着对博弈论在网络中的应用和研究进 展进行了讨论，这些应用主要包括路由算法、流量控制、拥塞控制和网络安全等方面。 2 1 博弈论简介 博弈论又称为对策论，属于应用数学领域的一个重要分支，是一种研究两个或两个以 上有利益冲突的个体在有相互作用的情况下如何进行各自最优决策的理论。 对博弈论的研究始于0 2 世纪初，以策墨洛( z c m r e l o ) 、波雷尔( b o e r l ) 和冯诺伊曼( v o a n c u m a n n ) 等人的工作为代表，他们利用数学理论研究竞争性现象的各方是否存在最合理的 行动方案，以及如何找到这个合理的行动方案。1 9 4 4 年，冯诺伊曼和奥斯卡摩根斯坦 ( m o r g e n s m ) 合著的“t h et h e o r yo f o a m es a n de c o n o m i cb e h a v i o r ”一书总结了博弈论的研 究成果，是博弈论发展史上的重要里程碑。随后，纳什m a s h ) 分别在1 9 5 0 生g 和1 9 5 1 年发表 了两篇关于非合作博弈论的重要论文，证明了非合作博弈存在平衡解，即著名的纳什平衡 0 n a s he q u i l i b r i u m ) ，从而揭示了博弈均衡与经济均衡的内在联系，彻底改变了人们对竞争 和市场的看法。纳什的工作基本上奠定了现代非合作博弈论的基石，而他本人也在1 9 9 4 年 与另外两位科学家共同获得了诺贝尔经济学奖。 由于博弈论从一个独特的视角帮助人们更加深刻地理解和把握竞争现象，因此被广泛 的应用于经济学、军事学、生态学、管理科学和社会科学等领域。随着认识的不断深入， 在计算机科学界也有人开始尝试使用博弈论作为分析的工具。在本节，我们通过著名的“囚 徒困境”的例子来介绍博弈论的一些基本概念。关于博弈论的详细介绍可以参考文献【1 7 l 和【嘲。 2 1 1 囚徒困境 有两名嫌犯甲和乙联手作案，被警方逮捕但未获得证据。警方将两人分别置于两间房 间分开审讯。量刑的标准是如果两人中有一人招供但另外一人未招，则招供者将被立即释 ， 放，而未招供者将被判入狱1 0 年；若两人同时招供，则两人分别判刑5 年：若两人都未招供 则因为警方缺少证据而将两名罪犯分别判刑1 年。 显然，对于每个嫌犯而言，他们都有两种选择：招供或不招供。这种对局形势可以 南京邮电大学硕士研究生学位论文第二章博弈论及其在网络中的应用 用表2 一l 来说明： 不招供招供 不招供 ( 一1 ，一1 )( - 1 0 ，0 ) 招供( 0 ，- 1 0 )( - 5 ，一5 ) 表2 1 囚徒问题 上表可以看出，囚徒困境问题由以下三个部分组成： 局中人：( p l a y e r ) 在一个对局中，有权决定自己行动方案的参与者称为局中人。在囚 徒困境问题中，嫌犯甲和嫌犯乙都是局中人，两个人都可以独立选择自己的对策。 策略集：( s t r a t e g ys e t ) 在对局中，可供局中人选择的一个实际可行的行动方案称为一个 策略( s t r a t e g y ) 。对于每个局中人而言，他们所有可以选择的策略的全体组成了一个策略集。 如果从每个局中人的策略集中取出一个策略组成策略组的话，则该策略组称为一个局势。 在本问题中，对于两个嫌犯而言，每个人的策略集是一样的，即 招供，不招供 ，而本问 题共包含四个局势，即：( 甲招供，乙招供) ，( 甲招供，乙不招供) ，( 甲不招供，乙招供) 和( 甲不招供，乙不招供) 。 支付：( p a yo 国对策的结果由局势唯一确定，而对策的结果又决定了每个局中人的得 与失，这种得失称为局中人的支付。在本问题中，对于嫌犯甲而言，他所期望的对局结果 从好到坏依次为：被释放( 甲招供，乙不招供) 被判刑1 年( 甲不招供，乙不招供) 被判刑 5 年( 甲招供，乙招供) 被判刑1 0 年( 甲不招供，乙招供) 。类似地，从表中也可以得知嫌 犯乙所期望的对局结果。 2 1 2 基本假设和定义 定义2 1 ： 策略型博弈( s t r a t e g yg a m e ) 。一个策略型博弈由以下三个基本要素组成： 一组局中人。 对于每个局中人，都有一个策略集。 一对于每个局中人而言，任意一个对局形势都会给他们带来利益得失，或者称为支付。 在囚徒困境问题中，通过对四个局势( 表2 1 ) 的分析，可以发现( 甲招供，乙招供) 对于 两个嫌犯而言都是最好的选择。这个结论可以通过纳什平衡理论推导出。在推导之前，我 们首先给出纳什平衡的基本概念。 纳什平衡的概念是建立在参与决策的个体均为“理智的 个体的前提下。 定义2 2 ：理智的选择( r a t i o n a lc h o i c e ) ，即局中人选择的策略所带来的收益( 支付) 至少不 6 南京邮电人学硕士研究生学位论文 第二章博弈论及其在网络中的应用 会少于其它可以选择的策略所带来的收益。 定义2 3 ：纳什平衡局势口是策略型博弈的一个纳什平衡点，如果对于每一个局中人i 以 及局中人i 的每一个策略矿，局势口为l 所带来的支付至少不比局势( 西，口二。) 所带来的支付 要差。这里，口二，表示除了i 之外的其余局中人的最优策略( 符号i 表示除了局中人i 之外的 所有其余局中人) 。 等价的，上述定义可以表述为对于每一个局中人i ， 坼( 口) u i ( a 。，a 。) 对于局中人i 的每一个策略q 都成立。 ( 2 一1 ) 其中，表示局中人i 的支付，a 表示纳什平衡点。 从定义2 3 以及公式( 2 1 ) 可以看出，当达到纳什平衡时，任意一个用户都无法通过单 方面改变自己的策略来获得更多的收益。纳什平衡的意义即在于当博弈的局中人只关心自 己利益的时候，在局中人之间能够达成一种妥协( 即所谓的平衡) ，并保证在这个平衡点上 各自的收益达到最大。 现在利用纳什均衡理论来分析囚徒困境问题。 显然，局势( 甲招供，乙招供) 是这个问题的平衡点。考虑嫌犯乙选择招供，则( 招 供，招供) 一5 一1 0 = ( 不招供，招供) ，这说明嫌犯甲应该选择招供；同样的，考虑嫌犯 甲选择招供，那么u 2 ( 招供，招供) 一5 一1 0 = 心( 招供，不招供) ，因此嫌犯乙也应该选择 招供。 2 2 分类 根据不同的划分标准，博弈可以分为不同的类型。 1 合作博弈与非合作博弈 按照对局人之间是否达成具有约束力的协议，博弈可以划分为合作博弈( c o o p e r a t i v e g a m e ) 与非合作博弈( n o n - c o o p e r a t i v eg a m e ) 。在一个博弈中，如果局中人之间互不合作，对 于策略的选择不允许事先有任何交换、传递信息的行为不允许订立任何强制性约定，则称 该博弈为非合作博弈。而合作博弈则是指局中人可以事先商量、互通信息并协调行动，因 而导致一些局中人进行合作而结成一个联盟。 2 策略型博弈与展开型博弈 7 南京邮电大学硕士研究生学位论文第二章博弈论及其在网络中的应用 以表现形式来划分，可以分为策略型博弈( 定义2 1 ) 与展开型博弈( e x t e n s i v eg a m e ) 。在 一个博弈中，如果局中人必须在博弈的一开始就确定策略，而无法在对局过程中根据当前 的局势选择下一步对策，则该对局称为策略型博弈。展开型博弈则是指对局开始时无法预 先确定局中人的完整的行动方案，每个局中人的下一步都是依据其他局中人的前一步来选 择的。 3 有限博弈和无限博弈 以对局进行的次数或者持续长短可以分为有限博弈( f i n i t eg a m e ) 和无限博弈( i n f i n i t e g a m e ) 如果每个局中人的策略集都是有限的，则称之为有限博弈，否则称之为无限博弈。 此外，博弈论还可以分为零和博弈、常和博弈等。本文将在后续章节对a dh o c 网络中的具 体场景建立模型，并使用非合作策略型博弈理论对模型进行分析。 2 3 在网络中的应用 博弈论在网络的许多研究领域内都有应用，本节将给出一些实际应用，这些应用涵盖 了网络的各个方面，主要包括路由算法、流量控制、拥塞控制和网络安全等。 2 3 1 路由协议 文献【1 9 】使用非合作博弈理论对两节点之间的多路径路由作了建模，每个用户的效用函 数被定义为他们在多条路径上的网络流量的总和，用户的目标就是如何分配每条路径上的 流量，使得各自的效用函数达到最大。文献【1 9 】还讨论了用户效用函数对纳什平衡点的存在 性和唯一性的影响。但是o r d a 等人的讨论仅限于两个节点之间流量的分配，当网络较为复 杂时，该模型难以扩展。l a 等人则在文献【2 l 】的基础上对多路径路由作了进一步的讨论。将 用户行为建模为扩展型博弈模型，并讨论了多个节点情形下的路由问题。作者指出，当使 用扩展型博奔论模型时，原来问题的纳什平衡解恰恰是整个系统的最优解，即整个网络的 效益也达到最大。e i t a n 舢衄觚等人研究了在多个用户同时竞争共享链路的情形下，各自可 以使用的最大带宽。文中定义了一类多项式路由成本，并证明了在该定义下系统的纳什平 衡点存在且唯一，并且该平衡点正好就是网络的全局最优点。文中所提出的路由策略适用 于源路由类型。 8 南京邮电大学硕士研究生学位论文 第二章博弈论及其在网络中的应用 2 3 2 流量控制 文献【2 2 1 和【2 3 】给出了流量控制的一个排队论模型，并使用非合作博弈理论对模型的平衡 点进行了分析。两篇文献都将用户的效用函数定义为平均吞吐量和平均传输时延的比值， 并且通过数学分析的方法给出了系统的平衡点。不同的是，前者的平衡点在整个系统中是 唯一的，而后者在某些特定情况下无法保证网络一定收敛于唯一的平衡点。与前两篇文献 将场景建模为非合作博弈模型相比，文献【2 4 l 则使用了合作博弈理论来分析流量控制问题。 用户不仅仅关心自己的收益是否实现最大化，同时还关注网络中的资源分配是否合理，因 此所有用户处于一种合作的环境中。作者最后证明了该模型可以达到平衡。在文献【2 5 】中， a l t m a n 等人将路由和用户的流量控制结合起来，对大规模网络( 即用户数量很多的网络) 的多路径路由进行建模，建立了非合作博弈理论下的模型框架。用户的效用函数被定义为 用户所占用带宽的多项式函数，在这种前提下，作者证明了模型的纳什平衡点存在且唯一。 2 3 3 拥塞控制 拥塞控制一直是计算机网络领域内的一个研究热点。随着因特网规模的不断扩大，以 往那种期望网络中的所有用户都遵从公共的网络协议并且相互协作的假设已经受到挑战。 事实上，并非所有的用户都会在网络发生拥塞的时候主动减少数据发送。此外，在资源受 限、带宽共享的竞争型网络( 如a dh o c 网络) 中，如何进行资源的合理分配以保证公平性已 经成为大家越来越关注的一个问题。文献【2 7 】在非合作博奔论的框架下提出了一种“奖惩机 制 。当网络发生拥塞的时候，对于那些仍然不减少数据发送量的用户将给予“惩罚 ， 即减少其可以使用的带宽；而那些愿意“合作 的用户则可以从对自私用户的惩罚中得到 “奖赏一，适当的增加自己的数据传输速率。该机制是通过最大最小公平准则 ( m a x m i n f a i m e s c r i t e r i a ) 来实现的。文献【2 8 j 给出了具有一般拓扑结构的网络拥塞控制的博弈 论模型。作者首先将用户的数据传输行为建模为非合作的竞争行为，接着将用户的净收益 定义为数据传输的成本与数据传输的效用之差。文献不仅证明了这类模型的纳什平衡点存 在且唯一，而且还给出了一种快速达到平衡点的方法。 2 3 4 网络安全 在a dh o c 网络中，由于缺少且还集中式的管理，网络安全受到两种具有非正当行为 ( m i s b e h a v e d ) 的节点的挑战：一类是自私节点，这类节点使用网络资源但又不愿意参与到网 9 南京邮电大学硕士研究生学位论文第二章博弈论及其在网络中的应用 络的合作中：另一类则是恶意节点，这类节点以破坏网络的整体性能为目的而不吝惜自己 所付出的成本。在文献【2 9 】中，m i c h i a r d i 和m o l v a 对a dh o e 网络中的用户节点之间的交互行 为进行了建模。文献中，用户的效用函数不仅与其绝对支付有关，而与相对支付有着密切 联系。所谓相对支付，就是该用户的实际收益与网络的总收益的比值。作者证明了在该机 制下，即使网络中存在自私用户，但大部分用户仍然会以合作的方式参与到网络中来。文 献【3 0 】从另一个角度对a dh o e 网络的用户行为进行建模。在该文献中，博弈的局中人被定义 为本节点以及除本节点之外的其它所有节点。作者分析了在何种条件下自私节点将会主动 参与到网络中，与其它节点进行合作。分析结果还表明，如果网络对节点提出的要求过于 苛刻，那么即使是“诚实 的节点也将会选择退出网络。 2 4 本章小结 通过上述介绍，可以发现博弈论能够将网络中各个用户的竞争行为以效用函数的形式 表现出来。博弈论强调个体的收益，这符合网络用户的初衷，使得可以从数学分析的角度 去探索激励机制对网络用户行为的影响，允许建立适当的模型去促使用户积极的参与到网 络的合作中。此外，在网络资源较为有限的场合下，博弈论还对如何公平合理的分配网络 资源起到指导作用。在研究博弈论模型时，一些基本特性往往受到人们的格外关注，譬如 模型是否可以达到动态平衡( 即是否存在纳什平衡) 、纳什平衡是否唯一以及收敛到纳什平 衡的速度等等。在后续章节中，将对a dh o e 网络的节点协作问题进行建模，并使用博弈论 这一强大工具进行分析。 1 0 南京邮电大学硕上研究生学位论文第三章基于博弈论的一种新型阻塞的协作策略 第三章基于博弈论的一种新型阻塞的协作策略 本文前两部分介绍了a dh o c 网络和博弈论的概念，第三部分将着重介绍a dh o e 网络 中节点协作的特点，存在的一般问题以及处理机制，重点介绍将博弈论引入节点间协作的 思路方法，在比较了几个主流博弈模型后，将推出本章由传统阻塞博弈模型得出的新型动 态阻塞博弈模型。 3 1 节点协作总体概述 移动a dh o e 网络不像固定网络，有专门的路由器和交换机来实现网络通信功能，它 的每一个节点既是主机又是路由器，既作为一个网络终端用户，又作为一个网络交换节点。 因此，每一个节点要承担起网络路由和包交换的功能。但是在移动a dh o e 网络中每个节 点拥有的资源有限，在多个管理域的情况下，有些节点为了节省自己的资源，不参与网络 交换，这就是移动a dh o e 网络节点中的自私行为。这种自私行为对网络性能的影响不可 低估。在文献【3 1 l 中研究了在d s r 协议环境下，自私行为对整个网络吞吐量和传输延迟的 影响程度，模拟试验结果显示，即使整个网络节点中只有小部分节点产生自私行为，也造 成网络性能下降。自私行为和攻击者的蓄意破坏行为虽然在出发点上有所不同，前者是为 了保存和节省资源，后者是为了破坏网络的正常功能，但是它们造成的后果相同，都会严 重影响网络性能，所以如何对付自私行为，增强网络节点的协作通信也是异构无线网络安 全体系不可或缺的一个重要部分。 在对付自私行为，增强协作方面的论文主要分两类，第一类是基于激励的机制，其基 本原理为节点转发报文后，即可得到筹码或者虚拟货币用于自己报文的传送。第二类是基 于惩罚的机制，邻居相互监视，发现不良行为的节点则被排除出网络。下面先介绍这两种 算法，然后进行分析比较。 1 基于激励的机制 l e v e n t eb u t t y a n 和j e a n p i e r r eh u b a u x 在文献【3 2 1 中，提出为了增强合作，网络中的节 点必须被鼓励转发报文，但是又不能滥发报文增加网络负载。为此，设计两种虚拟货币的 解决方案：一种解决方案是钱包方式，需要发送报文的节点估计报文所经过的节点与所需 要的花费，将计算所得的虚拟货币数放入钱包。钱包随报文一起发送，途径中间的每一个 转发节点从报文的钱包中取出一定量的货币作为转发该报文的费用，然后转发该报文，直 南京邮电大学硕士研究生学位论文第三章基于博弈论的一种新型阻塞的协作策略 至到达目的节点。这样每一个节点只有尽力转发其他节点的报文才能获得足够的货币以发 送自己的报文，从而起到一种激励合作的作用。该方式的优点在于可以防止节点滥发报文 增加网络负载，缺点主要有两个：其是源节点需要能够精确计算报文转发的费用，如果 放入钱包的费用小于实际费用，报文就会被中途抛弃。在拓扑频繁变化的移动a dh o c 网 络中估计报文所经过的节点和费用不是一件容易的事情。其而是每个报文都携带货币，用 于中途付给转发节点，增加了报文的长度。另一种解决方案是购买方式，每一个节点转发 报文时，从上游节点买下该报文，加上本节点的转发费用后，又把报文卖给下游节点，依 此转发直至目标节点。该方式的优点在于无需事先估计转发费用，全部费用由收方支付， 缺点为由于发方无需支付发送费用，攻击者可滥发报文，造成网络负载过重直至崩溃。 l c v e n t cb u t t y a n 和j e a n p i e r r eh u b a u x 在文酬3 3 j 中，提出一种基于筹码思想的解决 方案。该方案要求每个节点都安装安全卡，这是一个防止用户修改的硬件。安全卡内有筹 码累加器，每当节点转发一个报文时，该计数器就增加一个筹码值。当节点需要发送自己 的报文时候，就要将卡内筹码累加器减去n 个筹码，n 代表报文要经过n 个节点转发才能 到达目的节点。如果卡内筹码数小于n ，则节点不能发送该报文。这意味着节点要发送自 己的报文，必须转发其他的报文，以积累足够的筹码。该方案并不是用于阻止节点的不良 行为，它只是鼓励节点转发报文，确保节点不能从不良行为中获益。如果节点不转发报文， 它就没有筹码用于发送自己的报文。其优点是算法简单，只需要一个筹码累加器即可。主 要缺点有两点，其一需要硬件支持，其二不论报文长短，转发均增加一个筹码。 s h e n gz h o n g 等人认为在每个节点安装额外的硬件是不现实的，他们提出了一个不需 要在节点上安装硬件的类似方案s p r i t e 。首先设立一个集中的结算中心来存储每个节点的筹 码数，当节点发送一个报文时，所有中间转发节点和目的节点都记下这个报文的收据，然 后与结算中心联系，上传该收据。结算中心根据报文转发情况付给参与转发节点相应的筹 码数，同时扣去发送节点总计筹码数。结算时，按照博弈理论来计算支付方案，促使节点 能够尽力诚实履行网络功能。该方案的优点在于用统一的结算中心取代了各节点的硬件累 加器，无需在每个网络节点安装硬件卡。缺点也在集中的结算中心，若由网内节点承担则 会造成过重的通信负载和单点失败。该算法提出使用网外设备，将结算中心放在网外，通 过移动通信中的g p r s 来实现结算中心的联系。这种算法就非常适合a dh o c 与蜂窝融合 的异构无线网络。 上述基于激励机制的解决方案有三个特点，其一使用虚拟货币或者筹码作为转发 的回报。其二使用硬件设备来存储筹码值，以防用户修改。其三采用博弈理论来促使节点 合作。 1 2 南京邮电大学硕士研究生学位论文第三章基于博弈论的一种新型阻塞的协作策略 2 基于惩罚的机制 s e r g i om a r t i 等人提出通过w a t c h d o g 和p a t h r a t e r 两种技术来对付恶意节点的方案【3 4 】。 w a t c h d o g 和p a t h r a t e r 运行在每个节点上。w a t c h d o g 负责监视邻居节点行为，发现恶意行为 的节点。p a t h r a t e r 负责选择避开恶意节点的路径。该方案只是实现如何发现并避开恶意节 点，并不孤立和惩罚恶意节点。恶意节点仍然能够正常收发报文，反而为其免除了正常的 转发流量，客观上奖赏了恶意节点。 s o n j ab u e h e g g e r 和j e a n - y v e sl eb o u d e c 在文献1 3 5 】【3 6 1 a e 提出了一种利用邻居监视来 发现并排除恶意节点的算法c o n f i d 肘盯。它依靠运行于每个节点上的四个程序：邻 居监视器、信任管理、名誉系统、路径管理来实现其功能。邻居监视器的作用在于发现不 履行正常网络功能的邻居节点；信任管理用来发送、接收、管理其他节点的报警信息；名 誉系统是标记并管理其他节点的名誉值；路径管理在于选择路径时避开并孤立恶意节点。 每个节点监视其邻居的行为。如果发现恶意行为则提交给名誉系统并发送警报信息给其他 节点。名誉系统为每个节点设立一个名誉值，当有恶意行为报告时，减少其名誉分值。当 某个节点的名誉值低于标准时候，则提交路径管理。路径管理将删除与不良节点有关的路 径存储信息，并拒绝其路由申请。该方案的优点是不仅能发现恶意节点，而且用孤立方法 来惩罚它们，以促使它们履行正常网络功能。 p i e t r om i c h i a r d i 和r e f i km o l v a 也提出一种通过监视技术和名誉机制来激励合作的 算法c o r e p 6 。网络中每一个节点监视其邻居行为，观察其是否履行正常网络功能，如转 发报文、处理路由请求等。如果观察结果与预期的一致，则增加该节点的名誉分值，否则 减去一定分值。节点通过一个综合公式来计算某个节点总名誉的分值，公式的参数有直接 观察结果、其他节点的报告等等，还考虑到通信线路状况和以前的名誉分值。当某个节点 出现自私行为或者其他恶意行为的时候，其名誉分值就会逐渐下降，直至低于某个阀值的 时候，其他节点会拒绝为其提供服务，那样就将自私节点排除出网络。 该类方案有三个特点，其一采用本地监视技术来发现不良节点。其二通过名誉值来评 价节点。其三通过惩罚不良节点来促使节点合作。 为了实现共同的目标，限制节点的自私行为，增强节点合作，提高网络性能，上述两 种算法采用了完全不同的方法，种是激励的方法一种是惩罚的方法。 上述算法有以下特点： ( 1 ) 基于激励机制的算法存在的主要问题是需要额外的硬件支持其协议的执行。前两种 方案需要在每一个节点安装安全卡来存储信息。这些设备的使用会限制网络的扩展性和应 用范围。例如多个管理域的网络用户若不统一安装安全卡，则不能运行该协议。 1 3 南京邮电大学硕士研究生学位论文第三章基于博弈论的一种新型阻塞的协作策略 算法分类基于激励的机制基于惩罚的机制 理论基础博弈论 算法特点虚拟货币 邻居监视 主要思想以虚拟货币作为节点合作的奖赏，以被排出网络作为不合作的惩 孤立转发报文罚，鞭策节点参与网络功能 基本原理节点转发报文后，即可获得筹码或邻居节点相互监视，发现不良行 者虚拟货币用于自己报文的传送为的节点，则将被排除出网络 优点算法简单纯软件实现，无需硬件支持 缺点需要硬件支持邻居监视并不完全有效 表3 - l 基于激励机制的算法和基于惩罚机制的算法比较 ( 2 ) 基于惩罚机制的算法中存在邻居节点监视的有效性问题。基于惩罚机制主要使用本 地邻居监视的方法来发现恶意不良行为。但移动a dh o c 网络具有多交的拓扑和不稳定的 无线通信的特征，这使得有效检测自私节点变得十分困难。节点可能由于线路和电源等故 障无法转发报文，而被认定是自私节点。 ( 3 ) 标识的有效性问