（通信与信息系统专业论文）基于博弈论无线多跳网络性能优化研究.pdf

摘要 中文摘要 无线多跳网路作为无线数据传输的通信基础，用于实现发送端到接收端之间 的多跳数据的传输与处理。无线多跳网络易搭建且自身硬件成本低的特点，使它 被广泛地应用于军事、医疗等多个领域。但另一方面，由于无线多跳网络受到能 量、存储等方面的限制，使得节点在数据传输过程中需要权衡多个网络中的影响 因素，才能达到延长网络周期，优化网络性能的目的。 本论文以逐层递进的思路，详细论述了利用博弈论对无线多跳网络进行优化 的研究机制。首先，对无线多跳网络的定义、特征及挑战进行简要的说明，并对 博弈论的相关基础知识进行介绍，通过对已有博弈论与无线多跳网络相结合的典 型机制论述了基于博弈论的网络优化方案的高效性、稳定性等优势。其次，为了 使网络中传输数据的节点能同时兼顾到数据链路的安全与效用，提出了将声誉机 制与价格机制相结合的方案，利用博弈论对节点效用进行分析与推导，从而验证 了该方案能有效提高网络性能，使链路更加可靠。紧接着，对基于博弈的议价机 制进行了进一步分析，结合跨层设计的思想，实现物理层与链路层部分信息共享 的网络架构，通过议价博弈的分析与多重约束的优化模型建立，达到同时提高网 络吞吐量与节点效用的目的。虽然应用跨层思想使无线多跳网络变得更为灵活多 样化，但是信息的共享也使节点自私或恶意等安全问题变得不容忽视。因此，论 文最后利用贝叶斯博弈对节点交互过程中的信息进行策略空间的构建，进一步利 用物理层与链路层信息的共享实现节点之间合作的互监督机制，达到有效控制自 私或恶意节点给网络带来不良影响的目的。 关键词：无线多跳网络，博弈论，网络优化，跨层设计 福建师范大学陈心瑜硕士学位论文 摘要 a b s t r a c t a sac o m m u n i c a t i o ni n f r a s t r u c t u r ef o rw i r e l e s sd a t at r a n s m i s s i o n ，t h ew i r e l e s s m u l t i h o pn e t w o r ki su s e dt oa c h i e v ed a t ap r o c e s s i n ga n dt r a n s m i s s i o nb e t w e e nt h e s e n d i n ge n da n dt h er e c e i v i n ge n d t h ee a s y - t o - b u i l dc h a r a c t e r i s t i c so ft h ew i r e l e s s m u l t i h o pn e t w o r ka n di t sl o wc o s to fh a r d w a r em a k ei tw i d e l yu s e di nm i l i t a r y , m e d i c a la n ds o m eo t h e rf i e l d s o nt h eo t h e rh a n d , t h en o d ei nt h ew i r e l e s sn e t w o r k h a st ob a l a n c et h ei m p a c tf r o md i f f e r e n tn e t sd u r i n gt h ed a t a st r a n s f e r r i n gd u et ot h e e n e r g yo rs t o r a g ec o n s t r a i n t s ，a n dt h u st oe x t e n dt h ec y c l eo ft h ew i r e l e s sn e t w o r ka n d m a k ea o p t i m i z a t i o n i nt h i st h e s i s ，t h i sp a p e rw i l lp r o g r e s s i v e l yd e t a i lt h eo p t i m i z a t i o no fm e c h a n i s m s b a s e do nu s i n gg a m et h e o r yf o rw i r e l e s sm u l t i - h o pn e t w o r ks t e pb ys t e p f i r s t l y , t h i s p a p e rw i l li n t r o d u c ed e f i n i t i o n s ，c h a r a c t e r i s t i c sa n dc h a l l e n g e si nw i r e l e s sm u l t i - h o p n e t w o r k s ，a sw e l la st h eb a s i ck n o w l e d g eo fg a m et h e o r y t h eg a m et h e o r y - b a s e d n e t w o r ko p t i m i z a t i o ns o l u t i o n sf o re 伍c i e n c y , s t a b i l i t ya n do t h e ra d v a n t a g e sw i l lb e s t a t e db yd i s c u s s i n gt h et y p i c a lm e c h a n i s mw h i c hc o m b i n e sb o t ht h eg a m et h e o r ya n d w i r e l e s sm u l t i - h o pn e t w o r k s ，s e c o n d l as c h e m et h a tc a nc o m b i n e sw i t ht h e r e p u t a t i o na n dp r i c i n gm e c h a n i s m sw i l lb ep r e s e n t e dt og u a r a n t e et h el i n kl a y e r s s a f e t ya n de f f e c t i v e n e s si nn e t w o r kd u r i n gt h ed a t at r a n s m i t t i n g a n a l y z i n ga n d d e r i v a t i n gt h eu t i l i t yo ft h en o d e sw i t hg a m et h e o r y , i tw i l lb ep r o v e dt h a tt h es c h e m e i sa b l et og e tt h en e t w o r kp e r f o r m a n c ee f f e c t i v e l yi m p r o v e da n dt h ed a t al i n km o r e r e l i a b l e t h e n , af u r t h e ra n a l y s i so ft h eb a r g a i n i n gm e c h a n i s mb a s e do ng a m et h e o r y , c o m b i n i n gw i t ht h ec r o s s - l a y e rd e s i g ni d e a , w i l lb ec o n d u c t e dt ob u i l dan e t w o r k i n f r a s t r u c t u r et h a ts u p p o r t si n f o r m a t i o ns h a r i n gb e t w e e nt h ep h y s i c a ll a y e ra n dl i n k l a y e r n e t w o r kt h r o u g h p u ta n dt h en o d e s u t i l i t yw i l lb ei m p r o v e db ya n a l y z i n gt h e b a r g a i n i n gg a m ea n dp r o p o s i n gam u l t i c o n s t r a i n e do p t i m i z a t i o ns c h e m e a l t h o u g h w i r e l e s sm u l t i - h o pw i l lb em o r ef l e x i b l eb e c a u s eo ft h ea p p l i c a t i o no fc r o s s 1 a y e r , t h e i n f o r m a t i o ns h a r i n ga l s or e s u l t si ns o m es e c u r i t yi s s u e ss u c ha ss e l f i s ho rm a l i c i o u s n o d e s t h e r e f o r e ，b a y e s i a ng a m et h e o r yw i l lb ea p p l i e dt oc o n s t r u c ti n f o r m a t i o n s p a c e , w h i c hi sf o r m e di nt h ep r o c e s so fi n t e g r a t i n gi n f o r m a t i o n , a n dt h es h a r i n g i n f o r m a t i o nb e t w e e np h y s i c a ll a y e ra n dl i n k1 a y e rw i l lb u i l dm o n i t o t i n gm e c h a n i s m b a s e do nm u t u a lc o o p e r a t i o na n de f f e c t i v ec o n t r o lo fs e l f i s ho rm a l i c i o u sm o d e si nt h e n e t w o r kw i l lb ea c h i e v e d k e y w o r d s ：w i r e l e s sm u l t i - h o pn e t w o r k , g a m et h e o r y , n e t w o r ko p t i m i z a t i o n , c r o s s - l a y e rd e s i g n i i i 福建师范大学陈心瑜硕士学位论文 i v 中文文摘 中文文摘 近年来随着科学技术的发展，网络的广泛应用，用户对网络资源的需求日益 增加。无线多跳网络因其先进的网络技术与新式的网络架构，深刻得影响着现代 科学技术。廉价的设备成本，快速的网络部署，自主的传输管理使无线多跳网络 不仅在军事，民用，商业等场合发挥着强大的通信作用，同时也吸引着学术界的 注意力，成为学者们网络研究的主要对象。 无线多跳网络是一种动态自我组织和自我配置的无线网络，网络中的节点能 动态的建立与维护网络中多跳连接的状态。在数据传输过程中，由于信道资源的 有限使得节点不仅要考虑传输数据的优化问题还需要考虑通信成本代价问题，而 二者矛盾的冲突性需要节点通过正确的判断网络实时状态，构建出合理的权衡策 略才得以解决。博弈论作为一种策略分析的理论已被广泛的应用于商业，政治， 国际关系，计算机等领域。在无线多跳网络中，博弈论作为一种理论分析的方法， 从节点的行为空间中提取出相关的信息，根据节点实时的要求，建立效用函数， 通过对效用函数的指标判定，推导出对节点有利的信息或者行为预测。一种合理 的博弈论分析方法将有助于缓解节点之间的竞争与自私现象，让节点在收益与成 本之间找到合适的权衡方法，微观上使节点个体利益最大化，宏观上使整个网络 的使用周期、性能优化、安全检测都得到进一步提高。 本论文正是应用博弈理论对无线多跳网络进行分析，通过对博弈规则的设 定，引导节点提取相关信息，构建出合理的网络模型，通过对网络模型的分析与 相关理论的推导，达到个体与整体之间利益的权衡与优化。 本论文以层层递进的方式对基于博弈论的无线多跳网络性能展开研究，论文 分为三个部分： 第一部分为绪论，首先简要地说明了无线多跳网络的定义，指明了无线多跳 网络的特点。其次，表述了无线多跳网络所面临的挑战，根据已述的挑战内容说 明应用博弈论解决无线多跳网络优化的可行性与高效性。随后，论文对博弈论的 基本概念与分类进行概述，并从性能指标、跨层与博弈论的结合、节点状态与多 点博弈四个方面论述了基于博弈论的无线多跳网络研究现状。 第二部分，首先在第一章对节点效用的博弈机制进行了研究与分析，提出将 声誉机制与价格机制结合，应用博弈理论设计机制策略，促使发送端同时兼顾所 v 福建师范大学陈心瑜硕士学位论文 预付的通信价格与转发节点的可信度，并通过对节点行为的模型分析，推导出纳 什均衡存在的条件。 第二章，对价格机制进行了拓展延伸分析，提供基于议价博弈的无线多跳网 络模型，以提高网络的吞吐量和节点的效用为目的，将物理层的能量阈值与链路 层的信道容量作为主要约束条件，在无线多跳网络中引入跨层设计和协作优化的 思想，构建多重约束的网络博弈模型，应用议价博弈理论，分析网络中节点的议 价行为，改进网络性能，促进了网络公平性与高效性的提高。 第三章，在跨层的基础上，对网络的安全问题做了进一步分析，指出节点层 次之间信息的共享使网络应用多样化的同时也使网络的安全问题变得更为突出。 为了有效控制自私节点和恶意节点给网络带来的不良影响，通过对物理层与链路 层的跨层建立不完全信息的贝叶斯博弈模型。利用贝叶斯博弈理论对节点的交互 信息构建策略空间并进行推导分析，形成有效激励节点合作的互监督机制。最后， 分别通过案例分析与计算机仿真验证了该网络模型的可行性和公平性。 第三部分即第四章是对本论文的研究成果的总结，并对未来的研究工作展望 做了进一步的论述。 v i 绪论 绪论 第一节无线多跳网络的特征与应用 无线多跳网络概述 2 0 世纪8 0 年代前后，有线网络的应用已得到广泛得发展。随着有线网络应 用领域的不断拓展也随之带来了新的问题，由于有线网络存在维护成本高、可移 动性差、难架设等缺点【1 】，使得有线网络在应用发展的道路上遇到了瓶颈。作 为有线网络的一种改进方式，无线多跳网络突破了有线网络的局限性，为用户提 供了更多优质的服务。 无线多跳网络与有线网络不同之处在于，有线网络主要是以集中式管理为 主，节点任务单一，通信子网与资源之网之间有明确的界定。而无线多跳网络则 不同，网络由多个节点组成，常被应用于无人监管的区域，因此，无线多跳网络 具备动态自我组织和自我配置的无线网络特点。网络中的节点能动态的建立与维 护网络中多跳连接的状态在满足用户需求的同时实现自主管理网络。所以，网络 中的节点不仅具备传输数据的能力还需要承担分布式管理网络的职责。 从发展角度而言，无线多跳网络针对不同用户需求，已由无线多跳网络衍生 出针对不同应用场合的网络，比如以数据为中心的无线传感器网络( w i r e l e s s s e n s o r n e t w o r k ) 2 】；针对“最后一公里 无线接入技术的无线网格网络( w i r e l e s s m e s h n e t w o r k ) 3 】，快速布设提供应急通信的无线自组织网络( a dh o en e t w o r k ) 4 等。无线多跳网络因其应用的普遍性，已被抽象为一种集合多种无线应用网 络特征的一般网络模型，并被众多学者用于研究网络性能优化，节点吐吞量提高， 通信与能耗之间的利益权衡等问题。 二无线多跳网络挑战 无线多跳网络主要面临以下几个挑战： 1 物理条件受限。无线多跳网络的物理条件受限主要体现在资源管理与能 量消耗方面。在网络的初始阶段，为了方便网络节点的布设，节点基本 由轻质配件组成，这种轻质配件主要体现在节点硬件体积小，处理数据 福建师范大学陈心瑜硕士学位论文 的能力不高，存储量较低。在能耗方面，由于节点采用轻质配件组成， 这直接导致节点不具备有较高的蓄电能力，能量的有限性致使节点在传 输数据过程中要考虑到功率、通信成本等问题。 2 多跳传输数据。由于节点之间传输范围的有限，使得节点之间只有通过 多跳的方式才能实现远距离传输。如果网络规模越大，网络就需要布设 越多的节点实现数据传输。大量节点的存在就涉及到安全的维护及传输 的优化问题。 3 干扰性强。节点是以无线电波作为载波的方式进行传输的，在节点传输 范围内会存在多个节点之间的数据并发性，当节点之间同时发出信号时， 如果没有良好的网络架构用于规范节点的行为，可能会产生数据之间的 碰撞，资源共享的冲突，最终导致网络大面积瘫痪。 三基于博弈论的无线多跳网络应用需求 无线多跳网络所面临的挑战决定了网络中的节点需要扮演多重角色，比如节 点既是处理自身数据的发送者，又是转发其它节点数据的转发者，此外还必须是 维护网络稳定性与安全性的管理者等等。多重角色的转换不仅要求节点具备较高 的数据处理能力，处理应急事件的智能性，还应能够通过构建策略方案权衡节点 与节点之间的利益冲突。 博弈论作为应用数学的一个分支，被广泛的应用于分析事物利益冲突的本 源，提出相应的解决方案，力图使博弈结果达到最优。因此，在无线多跳网络中， 将博弈论作为一种机制策略，用于寻求网络模型与博弈模型之间的映射关系，达 到有效解决节点之间的利益冲突问题。在网络中，节点可根据自身配置的不同， 将自身的利益进行层次量化，对节点个体而言利益的量化使得节点有了明确的偏 好，但对于网络全局性而言，利益层次的不同致使网络的状态变得更为复杂。为 了在个体与全局之间做出权衡，节点不仅要了解自身利益的得失还需要更为准确 的把握网络的实时状态。节点可通过基于博弈论的分析，建立一个可行的策略空 间，抉择行为方案。一个基于博弈论正确分析的网络架构可以帮助节点做出正确 的策略选择，而正确的策略选择可以提高节点的效用。作为节点激励的最大动力， 效用的增加不仅可以促进节点处理更多的数据，还可以使网络整体的性能与安全 都得到进一步提高。 2 绪论 博弈论定义 第二节博弈论的基本知识 所谓的博弈【5 】即指在给定的条件下，一些个人、组织或者团队通过所掌握的 知识或者信息，一次或多次，同时或先后，从各自行为策略集合中选择相应的策 略并实施，最终获得相应收益。 博弈是由参与者、策略空间、效用三个主要元素组成 6 】。参与者( p l a y e r ) ： 指博弈中能独立决策并能独立承担后果的主体，主体可是个人或是团体，该主体 以优化集体或者个体利益为目的。策略空间( s t r a t e g i e s ) ：指参与者可选择的行为 或策略的集合，参与者可按需求选择策略空间中的一个策略即纯策略或者多个策 略用于展开博弈。效用( u t i l i t y ) ：又称效益，是指参与者从博弈中做出决策选 择后所得到的利益。因此，一个标准的博弈可描述为：在个有n 个人参与者 的博弈中，参与者都有其各自的策略空间，每个参与者根据各自的策略空间构建 出对应的效用函数，通过效用函数参与者权衡出最佳的策略方案。 在基于博弈理论分析的网络模型中，参与者即是网络中的节点，节点根据实 际的网络状态构建策略空间，并且通过策略空间评测期望收益。协议作为无线多 跳网络自主优化的实体 7 】，将以博弈理论作为基础，实现个体节点与整体网络 的优化，以微观视角诠释宏观网络特性。 二博弈论分类 博弈论的分类主要根据博弈的时序与信息的完整性进行衡量。博弈的时序分 为动态与静态，动态即指参与者根据时间的先后顺序进行博弈，反之参与者若为 同时进行博弈则定义为静态博弈。信息的完整性指双方对对方策略内容是否完整 可知，若参与者完全知道对方策略空间的内容，则定义为信息的完全性，反之若 对方只获知对方的部分策略信息或者不知道对方的策略信息则称为信息的不完 全性。 因此，根据博弈的时序与完整性可以把博弈分为如表0 - 1 所示类型 8 ： 3 福建师范大学陈心瑜硕士学位论文 表o - l 博弈分类 完全信息不完全信息 时序 静态 完全信息静态博弈不完全信息静态博弈 动态完全信息动态博弈不完全信息动态博弈 第三节基于博弈论的无线多跳网络研究现状 在基于博弈理论分析的网络模型中，参与者即是网络中的节点，节点根据实 际的网络状态构建策略空间，并且通过策略空间评测期望收益。节点作为无线多 跳网络自主优化模型的主体【4 ，将以博弈理论作为基础，实现个体节点与整体 网络的优化。 通过“由点及面 的论述方式，首先从网络单层的性能指标入手，从微观角 度论述节点如何通过博弈论优化个体节点的性能；其次，以达到节点提高优化性 能准确度与高效性为目的，从单层的性能优化扩展为跨层之间的信息博弈；再次， 针对个体节点获得的不同信息所表现出的不同状态，进一步论述如何构建合理的 博弈应对机制，达到节点趋于合作的目的；最后，从宏观视角出发，就多个节点 博弈时，网络应如何通过设计一个合理的机制使整体网络趋于一种稳定性与高效 性的兼顾状态进行深入阐述。 一性能指标 以性能指标为最终的评价准则，博弈论时常被应用于解决网络特定的优化问 题，比如功率控制优化，信道共享分配，路由选择决策等等。在文献t 9 ，1 0 ，1 1 ， 作者阐述了功率等级与信干比之间需要权衡的必要性，文献中指出当一个节点提 高功率等级，增大数据发送成功率的同时也使周边节点的信干比值下降。文献通 过基于信干比的博弈模型建立得出纳什均衡结论，指出纳什均衡不仅使各节点的 功率能量具有“公平性 而且还具有“帕累托 特性 1 2 】。在文献 1 3 ，1 4 】中，作 者指出节点竞争信道的解决方案在于应该构建一个具有实时动态的博弈策略，作 者将碰撞的条件概率作为博弈的策略选择空间，从中推导出实时的信道反馈信 息，通过反馈信息构建具有自适性随机访问模型。 4 绪论 在文献 1 5 】中，文章基于合作博弈的基础上讨论了节点路由选择的方法，推 导出当网络所拥有信道状态信息达到一定阈值时，通过网络的信息收集所建立的 策略空间可以有效延长网络运行周期。在文献 1 6 】中作者将网络博弈模型所推导 出的纳什均衡解作为高斯广播信道参数，目的是为了解决节点之间访问信道的 “公平性”问题。而文献【1 7 】指出节点之间的路由选择可以借鉴非合作博弈思想 设计一种有效的激励机制，比如声誉机制，价格机制，拍卖机制 1 8 】，通过节点对 支付与效用之间的权衡，选择出稳定性与有效性兼顾的路由机制。 二跨层与博弈论的结合 节点如何根据网络的实时状态信息构建出一个准确的博弈策略空间，主要由 节点对网络信息数量获取的多与少来确定。分层网络层次之间的独立性成为节点 把握网络信息准确度的最大阻碍。比如文献 3 8 1 q b 指出造成网络拥塞的原因可能 是链路层的链路断开，或者网络层路由的变化，也可能是传输层节点数据缓冲的 异常。因此，打破原有对网络“横向 设计的方法，改为以优化网络的功能模块 化为目的的“纵向 设计是有必要的。如图0 1 所示，让独立层次之间的信息得 到部分或者全部的共享，形成网络“耦合 状态【7 】。网络作为一个优化者，以 实现优化网络的某一功能模块为目的，逆向推导所需的对应层次的服务信息，构 建出符合实际要求的多重复合型策略，使无线多跳网络更能兼顾到多方面的考 虑。 跨层信息交换 分层信息交换 图0 - 1 跨层网络架构 f i g u r e0 1t h ea r c h i t e c t u r eo fc r o s s l a y e rn e t w o r k 5 福建师范大学陈心瑜硕士学位论文 对于一个网络而言，由于被监测节点异常状态的多样性，致使监测节点对网 络信息的获取应该是多个层次的综合考虑。例如文献 3 9 d p ，针对网络出现的信 号衰退，作者提出同时利用物理层与路由层信息构建博弈策略，策略中考虑了丢 包率与单播路由等因素。文献 4 0 】中，作者将传输媒介的波束形成与信干比做了 结合考虑形成二阶的博弈模型，使网络达到无失真具有时序收敛的波束形成并且 由纳什均衡解推测信道分配趋于合作状态的可能性。 网络作为一个优化者，以实现优化网络的某一功能模块为目的，逆向推导所 需的对应层次的服务信息，构建出符合实际要求的多重复合型策略。对于一个网 络而言，由于被监测节点异常状态的多样性，致使监测节点对网络信息的获取应 该是多个层次的综合考虑。例如文献 3 6 】中，针对网络出现的信号衰退，作者提 出同时利用物理层与路由层信息构建博弈策略，策略中包括了丢包率与单播路由 的考虑。文献【3 7 】中，作者将传输媒介的波束形成与信干比做了结合考虑形成二 阶的博弈模型，使网络达到无失真具有时序收敛的波束形成并且由纳什均衡解推 测信道分配趋于合作状态的可能性。 三节点状态 节点智能性的提高使得网络自主管理的能力增强，但与此同时，节点的智能 性也使网络的安全性分析变得更为复杂。尤其是当网络中存在多种配置的节点 时，因为节点所处利益不同使得有些节点表现出自私性。文献 1 5 1 9 对网络中节 点可能出现的异常状态进行了分析，例如节点拒绝转发数据的原因可能是自身能 量的耗尽或者信道状态不稳定，但也可能是节点出于节能的自私考虑等。因此， 对节点拒绝转发数据的原因应该根据节点的实际情况进行分析。应对网络出现自 私节点问题，可给出相应的监督或者惩罚机制，以提高网络的安全性。 如何将博弈机制的内容与网络的实际情况形成一种映射关系，应用博弈理论 激励节点为网络做出贡献，已成为学者们研究的一个热点。在文献 2 0 】中，作者 将议价博弈应用于网络中，提出“接收端驱动，发送端仲裁 的方法，即目的节 点将为源节点每一次的成功发送数据给予一定的报酬，报酬作为网络的激励方 式，鼓励节点之间相互传输数据。而文献1 2 1 ，2 2 】则将声誉机制应用于网络中，一 个节点的历史行为记录将作为一种信誉评价，用于衡量节点的诚实可靠性，发送 端将根据备选节点的可靠性构建策略空间。 在文献 2 3 2 4 中，作者认为节点对弈的信息应具有不对称性，这更符合网络 6 绪论 中的实际情况。应用不完全信息博弈模型对节点双方的期望收益分别进行讨论， 通过节点之间利益的权衡，得出纳什均衡解，这将有助于节点了解网络的实际状 态。对于已发现的自私节点，在许多文献中也给出了相应的惩罚机制。在早期的 文献中，对于自私的节点，网络则是采取孤立机制来惩罚这些自私节点。文献 【2 5 ，2 6 】中，对自私节点的惩罚是将自私节点的信息广播：通过多个合作节点的努 力形成自私节点传输范围内的孤立网络，使自私节点无法发送数据。在文献 2 7 】 中，自私节点都会有一个较低的评价值，节点若要“悔改”就必须努力得发送数 据，使自己的评价值达到合作状态的评价阈值以示“悔改，从而获得更多的服 务权限。 四多点博弈 如何解决网络全局优化始终是一个难点，因为不同的评价准则将会造就基于 不同偏好的博弈模型【2 8 】。针对一个非合作的网络而言，在个体节点与整个网络 架构之间始终存在利益的冲突，个体节点以最大化自身利益为目的，网络架构则 是以网络整体优化为目的，两者之间的矛盾需要通过博弈理论的分析，以网络的 整体优化为主要目的的前提下兼顾到解决节点个体的利益i 口- j 题。在文献 2 9 ，3 0 】 指出当网络中有一半以上的节点处于合作状态时，节点之间在进行多次重复博弈 后，网络就会显示一种大部分节点处于合作的良好状态。而在文献 3 1 】中也指出 当网络中两个节点之间形成“互惠互利的交互状态时，节点也可达成相互合作 的协议。 无线多跳网络无人监管的特性，使节点在博弈机制的作用下形成自主的合作 状态成为了必要性。文献 3 2 】重点讨论了网络中多个节点之间的联盟博弈问题， 论述了节点通过收益与成本权衡的合作策略将有助于形成网络的稳定状态。在文 献 3 3 】中，博弈论作为一种机制策略描述节点的非合作行为，应用博弈论对网络 的动态性进行分析，文中分别推导出完全信息与非完全信息下的纳什均衡解，纳 什均衡的求解不仅有助于网络设计者对网络的走向做出推测，而且还可以协助网 络评测达到即定优化目标的收敛速度。文献【3 4 】应用演化博弈的特点对网络中节 点的理性提出有限性假设，与节点的完全理性不同之处在于有限理性的节点更注 重于效用的对比性与持久性，如果节点进行合作博弈，认为无限次重复博弈所带 来的收益将大于节点自私所带来的短暂收益，那么节点将偏向一种合作偏好。 7 福建师范大学陈心瑜硕士学位论文 第四节课题来源及内容安排 尽管无线多跳网络的应用已得到广阔的发展，但是无线多跳网络中依旧存在 着多个问题有待改进，例如：如何使节点在高效传输数据的同时能兼顾到链路的 安全性；如何构建一个具有稳定性与灵活性的网络优化模型；如何将跨层思想与 无线多跳网络进行有机的结合等等。本论文将结合博弈论，针对无线多跳网络中 网络的性能优化问题展开讨论，并针对现有研究工作的不足进行改进与拓展，使 无线多跳网络更加的高效与安全。 本论文的课题来源于如下基金项目：国家自然科学基金项目( 6 1 0 7 2 0 8 0 ) “跨 层协作的可编程无线m e s h 网络安全关键技术研究、国家自然科学基金( n o 6 0 5 0 2 0 4 7 ) “安全和能量感知的可编程复杂动态自组织网络研究 和福建省教育 厅重点项目( n o j a 0 7 0 3 0 ) “基于可信分簇的无线传感器网络安全关键技术 等。 论文的主要工作和内容安排如下： 绪论介绍了无线多跳网络的定义、特点及其挑战，说明了博弈论与无线多跳 网络相结合的必要性与可行性。阐述了博弈论的基本概念与分类方法，并对博弈 论与无线多跳网络相结合的研究状态做了论述。 第一章针对无线多跳网络中节点资源有限的特点，提出了一种将声誉机制与 价格机制相结合的方案，方案中应用博弈论，在促进了发送端兼顾所预付的通信 价格的同时，提高了转发节点的可信度。用基于博弈理论的分析方法对无线多跳 网络进行了建模，并推导出纳什均衡存在的条件。 第二章以提高网络吞吐量为目的，改进节点把握信息的准确度，在基于议价 博弈的基础上引入跨层设计的思想，将物理层的能量阈值与链路层的信道容量作 为主要约束条件，构建多重约束的优化模型，应用议价博弈理论，分析网络中节 点的议价行为，从而改进了网络的性能。 第三章为了防止自私节点和恶意节点所带来的不良影响，本论文基于物理层 与链路层的跨层信息展开了进一步分析，应用博弈理论知识，构建出适时的不完 全信息贝叶斯模型，通过对博弈规则的创建，节点在通信过程中，逐渐形成互监 督机制，达到改进网络安全性的目的。 第四章对本论文的研究成果进行了总结，并对下一步的研究工作提出了一些 展望。 8 第一章节点效用的博弈机制研究 第一章节点效用的博弈机制研究 无线多跳网络不具备基础设施，需要节点自主管理网络。在构建网络模型时， 由于无线多跳网络自主性与资源有限的特点，节点在优化网络时，应注意效用与 成本之间的权衡。本章将声誉机制与价格机制相结合，应用博弈论对节点传输数 据的效用进行分析，使发送端兼顾到通信价格的同时也提高了传输链路的稳定 性。 第一节无线多跳网络的安全需求 优化无线多跳网络的策略机制主要分为两类，一类以节点传输数据包的频度 作为衡量标准，用于评价节点声誉的高低 4 1 ，4 2 ，若节点中继数据包越多，则节 点拥有的声誉评价就越高，节点就越有可能获取更多节点信赖；另一类，通过节 点之间竞争报价方法，发送端选取候选中继节点中报价最高的节点作为下一跳节 点 3 1 ，从而达到双方互利的目标。不管是何种类型的策略机制，网络最终的 目的都是希望通过机制的规范，使节点处理数据的能力转换成为一种效用，激励 更多的节点参与到网络的数据传输中。但是，仅以节点转发数据的支付能力或者 链路的可靠性这种单方面指标作用参考标准，很难兼顾到数据转发过程中，在保 证转发节点可靠性的同时防止异常节点的价格虚报行为。 因此，在本章中结合声誉机制与报价机制的优势，发送端将同时对转发节点 的声誉值与该节点所报价格做评价。促进发送端对中继节点的稳定性与有效性做 出正确的判断。另一方面，自主性的特点使网络中的节点出于自身能量的节约或 者服务能力的局限性将产生自私或者恶意的异常行为，这种异常行为与整个网络 的良好性能发挥是相悖的，为了权衡单个节点与全局网络之间的利益，本章将以 博弈理论作为基础，分析网络中存在的群体合作与利益权衡的问题，从而使得单 个节点利益得到优化同时，整个网络的性能也能得到相应有效的提高。 9 福建师范大学陈心瑜硕士学位论文 纳什均衡 第二节基本背景介绍 在博弈论【6 】中，“均衡是对参与者策略组合稳定趋势的一种判定。最常见 的均衡是“纳什均衡”( n 砒e q u i l i b r i u m ) 。纳什均衡定义如下： 标准式博弈g = 留l ，”，s 。；材l 一，“。) 中，由每个参与者所选择的一个策略组成 某个策略组合g ：，j ：9 其中每个参与者f 的策略都应对的是其它参与者 策略组合研，也，) 的最佳策略，即如式( 1 1 ) 所示： g ，i ，囊，s d “研，, s d k ( 1 - 1 ) 蝇，墨，2 蝇， () 在式( 1 1 ) 中，对任意吻岛都成立，则称g ，) 为标准式博弈g 的一个 纳什均衡。纳什均衡作为博弈中一种典型的稳定状态，是可预测的，且这种可预 测性具有一致性的特点，即指如果所有参与者预测特定纳什均衡会出现，则所有 参与者将有动力参与到寻求均衡的行动中。 二声誉机制 声誉指在给定的条件下，一个实体对另一个实体行为所表现出可信度的一种 评价，它所体现的是对该实体执行某种特定行为的期望。在无线多跳网络中，节 点传输范围或者路由协议等可以被视为节点的“有形约束 4 3 】；而为了建立节 点的长期效用，还需要“无形约束，比如声誉机制、第三方认证。无线多跳网 络时常工作在恶劣的环境下，不易实现人为的管理，因此无线多跳网络具有无中 心点，自组织，能量有限等特点。正是因为网络需要节点自主管理，致使在无线 多跳网络中构建第三方机构变得不易实现。与第三方认证不同的是，声誉机制不 需要以集中认证方式对恶意行为或欺骗行为进行管理，因此，声誉机制被视为一 种有效激励机制，应用于无线多跳网络，用以惩罚节点的恶意行为或欺骗。基于 声誉机制的博弈，节点的声誉值是群体在多次的通信交互过程中逐渐建立的，因 此，声誉值包含节点的历史行为与特征记录的积累，这种累积直接影响着其它节 点对该节点信任度的评价。当网络中出现恶意或者欺骗行为的可能性比较少时， 所有节点的声誉值就比较持平，每个节点的利用率相对平均，因此声誉值间接体 l o 第一章节点效用的博弈机制研究 现着整个网络的稳定性。在无线多跳网络中，声誉机制在基于节点原有特性的基 础上，为节点增加了可靠度判定的指标，使得声誉机制在无线多跳网络中的可行 性要大于第三方认证机制的可行性。 前提假设 第三节基于博弈的网络模型建立 假设该网络中有( z + 1 ) 个节点，节点之间链路具有对称性 4 4 】。考虑 到节点能耗与存储器的局限性，采用按需驱动的动态源路由协议( d y n a m i cs o u r c e r o u t i n g ，d s r ) 4 5 作为网络层路由选择协议。d s r 主要分为两个阶段：1 、路由 发现阶段；2 、路由维护阶段。在路由发现阶段，发送端s 将数据发送给接收端 d ，但节点s 并不知道到达节点d 的具体路由，这时节点s 将广播包含节点d 信息的r o u t er e q u e s t 数据包给其邻居节点，邻居节点在正确接收到r o u t e r e q u e s t 数据包后，将自身的地址信息附加到r o u t er e q u e s t 数据包中并 进行再次广播，通过这样多次广播直至r o u t er e q u e s t 数据包成功的被节点 d 接收到，节点d 将依据r o u t er e q u e s t 数据包中所包含的节点s 、d 间的 路由信息，以r o u t er e p l y 数据包形式返回给节点s ，以示两个节点之间的路 由已确定，可以开始传输数据。而在路由维护阶段，主要实现的是维护点到点或 者端到端的路由可用性。 二接收端策略空间 在无线多跳网络中，作为博弈参与者的发送端、接收端，在信息交互过程中， 逐步建立各自的策略空间。以下首先对接收端的策略空间进行描述。 在给定的时间内，网络时常所提供的是相同的服务功能，比如在无线传感器 网络中，主要以提供环境数据为主。所以，假设在给定的时间内，网络中的接收 端为发送端所提供的服务类型不变。尽管是同- - j j 砭务，但在无线多跳网络中，节 点由于外在因素，比如拓扑变化，电磁干扰；或者内在因素，比如耗能，声誉评 价等使网络产生多变性，所以即使面对的是同样的服务类型，接收端完成服务的 能力是不同的。用无表示成功完成同一服务名的不同概率f 或称服务的不同等级 福建师范大学陈心瑜硕士学位论文 i ，例如五x j ( i j f ) 表示对于同一服务a ，以f 等级完成服务的概率小于或等于 以j f 等级完成服务的概率。同时，假设服务等级是一个非空有限集合 人= ， ，如，k ，对于不同的服务等级，所反应的是接收端对成本与收益 - 0 ， 的不同考虑。 对接收端而言，节点的理性表现为最大化本节点效用函数。用“( ) 表示节点 相应的效用函数。在仅考虑服务等级时，接收端的支付函数定义为 p ： 缸，k 】j 孵，p ( 五) 表示不同服务等级所产生的不同支付值。设定服务等 级越高，所支付的值越大，且p ( 五) 满足p 7 ( 五) 0 ，p ( 五) 0 。与支付函数相对 应的成本函数将作为接收端权衡所需要考虑的另一方面。成本函数定义为 c ： 缸，k 】兮吼；c ( 旯) 作为对于服务的不同等级所产生不同成本的评价指标。 服务等级越高，接收端提供相应服务等级的成本将越大，即c ( a ) 0 且c ( 五) 0 。 因此，服务等级的效用函数“( ) 可以如下表示： “( 名) = p ( 五) - c ( 2 ) ，五 彳曲，五瞰】 ( 1 - 2 ) 尽管支付函数与成本函数是连续型函数，但是考虑到接收端为了节约能耗， 接收端对于效用函数的观察是不完全的有限个离散值。因此将连续的效用函数近 似表示为： rt - l lc ( 兰铴+ ( 饥一五) + q ( 五一五) f - 1 1 兄【k ，k 】 ( 1 - 3 ) i p ( 旯) 兰f l o + 层( 五“一乃) + 屈一五) 其中a j 为边际成本，它所表示的是随着服务等级的提高，其应付成本的变化 量；同理，屈为边际价格，所表示的是接收端所获支付的变化量，这里假设当i j f 时，a i o j ， p i p j 。 在无线多跳网络中，由纳什均衡的一致性定义【5 】可知，当发送端所提出的服 务请求，总有至少一个接收端能具备处理服务能力时，那么网络中所有节点就都 第一章节点效用的博弈机制研究 能趋于某一纳什均衡点。假设网络中所存在的纳什均衡点具有唯一性，则当网络 达到纳什均衡点时，接收端的最优服务等级记为z ，z 满足下式( 1 - 4 ) z = 一c(名)(1-4)argmax(p(；l，) 力= 一c 【允 此时，边际成本与边际价格应满足吩 “。例如图1 - 1 ，在式 ( 1 4 ) 的约束下，服务等级5 为最优服务等级，即当服务等级为5 时，支付价 格与成本之间差值最大。 3 2 相 藿l 5 划 1 0 e 成本边际效益 + 支付边际效益 ( 7 7 e 一 乡易 匕 ，一一苏 ，一。 、一 ef = 一甲 丫 01234567891 01 1 服务等级 图1 1 边际效用 f i g u r e1 1m 蛐咖a lu t i l i t y 假设接收端的初始声誉值为r 姗z + ，如果接收端在发送端规定的时间内正 确完成了发送端所请求的服务时，接收端能在原有的声誉值上增加相应的反馈声 誉值，。将发送端所期望的等待时间统为等长的服务等待时间，在时刻f 之前所 得到的声誉值记为足，而在经历过一个服务等待时间后，如果接收端成功的完成 了发送端的服务请求，那么接收端所获得的声誉值定义为r = f ( r ，) ，其中 福建师范大学陈心瑜硕士学位论文 c 为本次服务结束时，发送端所能得到的反馈声誉值。 声誉机制的引入，不仅表示为当前节点的可信度，而且还影响到该节点将来 收益。因此在时刻f ，接收端将以自己当前的声誉值冠，剩余能耗4 与发送端的 服务请求等级丑，三者同时作为接收端报价参考因素，向发送端表达接收端所 期望的收益，而与收益相对应的成本则表示为c ( 丑，4 ) 。接收端的效用函数表达 为如式( 1 5 ) 所示： 铭 ，丑，4 ) = 园 ，五，4 ) 一“五，4 ) + 理+ 。阻a ，扎，乱) 】 ( 1 5 ) 其中e l 。1 【( r ，+ ，以+ 。) 】表看, - 亥u t + 1 的声誉值r “的期望；由于 不同时间状态所产生的声誉值具有不对称性，所以用秒表示f + 1 时刻的声誉对当 前效用函数的贴现。在重复博弈中，如果双方将博弈过程中谈判的费用和利息的 损失考虑在内，那么就用贴现因子表示每一回合中双方利益的折扣，取值范围 0