（通信与信息系统专业论文）对策论框架下无线传感器网络中的功率控制.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导 下，独立进行研究所取得的成果。除文中已经注明引用的内容 外，本论文不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究作出重要贡献的人和集体，均已在文中以明 确方式标明。本声明的法律责任由本人个人承担。 论文作者签名： 王状 日期： 嗣，- ；f 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：垫趑导师签名；工茎三鲨互 山东大学硕士学位论文 摘要 无线传感器网络是由部署在监测区域内大量的廉价微型传感器节点通过无线 通信方式形成的一个多跳的自组织的网络系统，其目的是协作的感知、采集和处 理网络覆盖区域中感知对象的信息，并发送给观察者。传感器节点电源能量有限 的特点决定了如何在网络使用过程中节约能量，延长网络使用寿命是无线传感器 网络所面临的核心问题。 本文根据t d m a 机制和c d m a 机制相结合的分簇结构无线传感器网络的基本特 点，以网络中的簇为单位，阐述了基于纳什均衡理论的t d m a - c d m a 改进机制，提 出了在s t a c k e l b e r g 激励策略( 非合作理论) 和谈判理论( 合作理论) 下基于完 全信息的功率控制的研究框架以及基于不完全信息的功率控制算法，促使传感器 节点通过控制发射功率来优化其收益函数，提高节点的能源有效性，并且改进了 现有的节点收益函数，延长了网络寿命，最后讨论了不完全信息框架下的功率控 制问题，并和完全信息做了比较。 本文以对策论的相关理论为基础，从不同角度进行了深入的理论分析和探 讨，同时结合仿真试验得到了一些有积极意义的研究成果。 首先，本文阐述了t d m a 机制和c d m a 机制相结合的分簇结构无线传感器网络 的基本特点，在此基础上将纳什均衡理论用于t d m a c d 姒机制的实现。 其次，总结了现有的无线传感器网络中的功率控制算法，针对其不足，重点 运用对策论中的s t a c k e l b e r g 策略，提出了基于t d m a - c d m a 机制的分簇结构无线 传感器网络( w s n ) 的反向链路功率控制的新算法，并且改进了现有的收益函数。 同时，在m a t l a b 软件环境下设计完成了相应的仿真试验，仿真结果表明 s t a c k e l b e r g 策略确实能起到控制功率及激励网络优化的作用，结果还表明改进 后的收益函数使网络寿命得以延长 接着，本文将双人谈判理论用于无线传感器网络的功率控制算法中，建立了 一个簇内节点通过谈判确定各个节点的发射功率以达到帕累托改进的数学模型。 山东大学硕士学位论文 仿真结果表明谈判解确实是纳什均衡解的帕累托改进，因此谈判理论为谈判双方 提供了双赢策略。 本文在前面完全信息框架的基础上，提出了不完全信息框架下的功率控制问 题，并且将不完全信息和完全信息两个框架下的纳什均衡信噪比和纳什均衡收益 做了比较，并分析了原因。 最后，对全文的工作进行了总结，指出了值得进一步探讨的相关问题和研究方 向。 2 关键字：对策论；s a c k e l b e r g 策略；谈判理论；无线传感器网络；功率控制 山东大学硕士学位论文 a b s t r a c t w i r e l e s ss e n s o rn e t w o r kc o n s i s t so fal a r g en u m b e ro fd i s t r i b u t e d $ e n s o rn o d e s e q u i p p e d w i t l lr a d i od e v i c e st h a to r g a n i z et h e m s e l v e si n t o 鱼m u l t i - h o pw i r e l e s s n e t w o r k s ，w h i c hc a nb r e a km o n i t o ra n dt r a n s m i s s i o nl i m i t a t i o n so fs i n g l es e n s o ra n d i m p r o v et h ep r e c i s i o na n dr a n g eo f m o n i t o r i n gs i g n i f i c a n t l y d u et oc o n s t r a i n t si m p o s e d o ne n e r g yi nw i r e l e s ss e n s o rn e t w o r k ( w s n ) ，e n e r g y - e f f i c i e n c ya n dl i f e t i m eo fn e t w o r k a r eu n d o u b t e d l yb e i n gp u tt h ef i r s tp l a c e w ed e v e l o pap o w e rc o n t r o la l g o r i t h mo nt h er e v e r s el i n ko fc l u s t e r i n gw i r e l e s s s e n s o rn e t w o r k ( w s n ) o fc o m p l e t ei n f o r m a t i o nb a s e do nt d m a c d m aw i n l s t a c k e l b e r gs t r a t e g ya n db a r g a i nt h e o r y t h e n t h ei s s u ea r i s i n gf r o mi n c o m p l e t e i n f o r m a t i o ni si n v e s t i g a t e da n dn u m e f i c a lr e s u l t sa r ep r o v i d e d b a s e do nt h et h e o r yo f n a s he q u i l i b r i u m ，s t a c k e t b e r gp r i c i n ga n db a r g a i ng a m e ，w ec a nd r a ws o m eu s e f u l c o n c l u s i o nb yt h ea i do f t h e o r e t i c a la n a l y s i sa n dn e t w o r ks i m u l a t i o n ， f i r s t l y ，w ef o r m u l a t eam o d e lo f t d m a - c d m ab a s e do nn u s he q u i l i b r i u m ，g i v i n ga c h a r a c t e r i z a t i o no f c l u s t e r i n gw i r e l e s ss e n s o rn e t w o r k s e c o n d l y ，w ee x p o u n dt h ep o w e rc o n t r o lm o d e l ，p u t t i n gt h ee m p h a s i so na p p l y i n g s t a c k e l b e r gt h e o r ya n di m p r o v i n gt h eu t i l i t yf u n c t i o n f o u n d e do na b o v ea n a l y s i s ， s i m u l a t i o nu n d e rm a t l a be n v i r o n m e n ti sc o n s t r u c t e dt oe v a l u a t ep e r f o r m a n c e so ft h e p o w e rc o n t r o lm o d e l t h i r d l y ，w ec a r r yo u tt w o p e r s o nb a r g a i n i n gt h e o r yi np o w e rc o n t r o lm o d e li nw h i c h c l u s t e r i n gn o d e sf i n d sp a r e t oi m p r o v i n gp o w e rs o l u t i o nb yb a r g a i n i n g mn u m e r i c a l r e s u l t ss h o wt h a tt h eb a r g a i n i n gt h e o r yp r o v i d e st w on o d e sag o o dm e t h o dw h i c h b e n e f i t se a c ho t h e r m o s tr e s e a r c hw o r ki nt h i sf i e l di sb a s e do nc o m p l e t ei n f o r m a t i o n f o rt h ef i r s tt i m e ， w ea n a l y s i st h ep o w e rc o n t r o lp r o b l e mb a s e do i li n c o m p l e t ei n f o r m a t i o n a l s ow e c o m p a r et h et w oc a s e sa b o u tt h en a s he q u i l i b r i u ms i n ra n dn a s he q u i l i b r i u mu t i l i t y a t1 a s t w er e v i e wt h ee n t i r ew o r ka n ds u g g e s tt h ed i r e c t i o nf o rf u t u r er e s e a r c h k e y w o r d s ：g a m et h e o r y ；s t a c k e l b e r gt h e o r y ；b a r g a i n i n gt h e o r y ；w i r e l e s ss e n s o r n e t w o r k ；p o w e rc o n t r o l 3 山东大学硕士学位论文 a t m c d m a m a c s i n r t d m a w n s t r a m a 符号说明 a s y n c h r o n o u st r a n s f e rm o d e c o d ed i v i s i o nm u l t i p l ea c c e s s m e d i u ma c c e s sc o n t r o l s i g n a l - t o i n t e r f e r e n c e - a n d - n o i s e - r a t i o t i m ed i v i s i o nm u l t i p l ea c c e s s w i r e l e s ss e n s o rn e t w o r k t r a f f i ca d a p t i v em e d i u ma c c e s s s m a cs e n s o rm e d i u ma c c e s sc o n t r o l t m a ct i m e - o u tm e d i u ma c c e s sc o n t r o l l o c a lm e a no f n e i g h b o r sa l g o r i t h m d r n gd i r e c t i v er e l a t i v en e i g h b o r h o o dg r a p h d l s sd i r e c t e dl o c a ls p a n n i n gs u b g r a p h 4 异步传输模式 码分复用 介质访问控制 信噪比 时分复用 无线传感器网络 流量自适应介质 接入协议 传感器介质接入 控制 超时介质接入控 制 本地邻居平均 算法 相关邻居图预测 算法 间接本地子图算 法 山东大学硕士学位论文 第一章绪论 1 1 无线传感器网络概述 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ，简称w s n ) t 1 1 是计算机、通信和传 感器这三项技术相结合的产物，随着微处理器和无线通信技术的发展，其重要性 越来越突出。它可应用于布线和电源供给困难的区域，人员不能到达的区域( 如 受到污染、环境不能被破坏或敌对区域) 和一些临时场合( 如发生自然灾害时， 固定通信网络被破坏) 等。它不需要固定网络支持，具有快速展开，抗毁性强等 特点，可广泛应用于军事、工业、交通、环保等领域，被认为是2 1 世纪最重要 的技术之一，它将会对人类未来的生活方式产生深远影响。 无线传感器网络典型工作方式如下：使用飞行器将大量传感器节点( 数量从 几百个到几千个) 抛撤到感兴趣区域，节点通过自组织快速形成一个无线网络。 节点既是信息的采集和发出者，也充当信息的路由者，采集的数据通过多跳路由 到达网关，再由网关与外部通信。 1 1 1 无线传感器网络结构 无线传感器网络典型的体系结构如图1 1 所示 2 1 ，节点具有传感、信号处理 和无线通信功能，它们既是信息包的发起者，也是信息包的转发者。通过网络自 组织和多条路由，将数据向网关发送。网关( 也称为s i n kn o d e ) 是一个特殊的节 点，它可以使用多种方式与外部网络通信，如i n t e r n e t 、卫星或移动通信网络等 等，大规模的应用可能使用多个网关，也可以利用无人机飞越网络上空，通过网 关采集数据。节点由于受到体积、价格和电源供给等因素的限制，通信距离较 短。只能与自己通信范围内的邻居交换数据，要访问通信范围以外的节点，必须 使用多跳路由。为了保证网络内大多数节点都可以与网关建立无线链路，节点的 分布要相当的密集。 山东大学硕士学位论文 用户 图1 1 无线传感器网络体系结构图 1 1 2 无线传感器网络的特点 无线传感器网络具有很多鲜明的特点 3 1 ： ( 1 ) 通信能力有限，通信覆盖范围较窄。 ( 2 ) 电源能量有限。电源能量约束是阻碍传感器网络应用的严重问题，在 传感器网络设计过程中，任何技术和协议的使用都要以节能为前提，最大化网络 的生命周期。 ( 3 ) 无中心。无线传感器网络中所有节点地位平等，是对等式网络，节点 可以随时加入或离开网络，任何节点的故障不会影响整个网络的运行，具有很强 的抗毁性。 ( 4 ) 自组织。网络的布设和展开无需依赖于任何预设的网络设施，节点通 过分层协议和分布式算法协调各自的行为，节点开机后就可以快速、自动地组成 一个独立地网络。 ( 5 ) 硬件资源有限。节点计算能力、程序空间和内存空间普遍的比计算机 功能要弱很多，因此在节点操作系统设计中，协议层次不能太复杂。 ( 6 ) 节点数量众多，分布密集。为了对一个区域执行监测任务，往往有成 千上万传感器节点空投到该区域，传感器节点分布非常密集，利用节点之间高度 连接来保证系统的容错性和抗毁性。 6 山东大学硕士学位论文 ( 7 ) 相邻节点的感知数据具有相似性 1 1 3 无线传感器网络协议栈与功能模块 随着传感器网络的深入研究，研究人员提出了多个传感器节点上的协议栈。 早期的协议栈 1 】包括物理层、数据链路层、网络层、传输层和应用层，与互联网 协议栈的五层协议相对应，如图1 2 所示。另外，协议栈还包括能量管理平 台、移动管理平台和任务管理平台。这些管理平台使得传感器节点能够按照能源 高效的方式协同工作，在节点移动的传感器网络中转发数据，并支持多任务和资 源共享。各层协议和平台的功能如下： 物理层提供简单但健壮的信号调制和无线收发技术； 数据链路层负责数据成帧、帧检测、媒体访问和差错控制； 网络层主要负责路由生成与路由选择； 传输层负责数据流的传输控制，是保证通信服务质量的重要部分； 应用层包括一系列基于监测任务的应用层软件； 能量管理平台管理传感器节点如何使用能源，在各个协议层都需要考虑节省 能量； 移动管理平台检测并注册传感器节点的移动，维护到汇聚节点的路由，使得 传感器节点能够动态跟踪其邻居的位置； 任务管理平台在一个给定的区域内平衡和调度检测任务。 图i 一2 无线传感器网络协议栈 传感器节点由传感器模块、处理器模块、无线通信模块和能量供应模块四部 分组成，如图1 3 所示。传感器模块负责醢测区域内信息的采集和数据转换： ， 8 山东大学硕士学位论文 处理器模块负责控制整个传感器节点的操作，存储和处理本身采集的数据以及其 他节点发来的数据；无线通信模块负责与其他节点进行无线通信，交换控制消息 和收发采集数据；能量供应模块为传感器节点提供运行所需的能量，通常采用微 型电池。前三个模块为传感器节点的能量消耗模块，各模块能量消耗情况如图i 一4 所示，可见处理器和传感器模块的功耗很低，绝大部分能量消耗在无线通信 模块上。无线通信模块分为四种状态：发送，接收，空闲和睡眠，发送状态消耗 的能量最多，接收和空闲状态次之，而在睡眠状态则关闭通信模块。所以为使网 络高效使用能量，可以考虑使节点减少不必要的转发和接收，不需要通信时尽快 进入睡眠状态。为使网络通信不会中断，协调好节点相互问的转发、接收的工作 时间是很重要的。 嵌入式软件 上 厅甄藕习 t 传感器h a d 转换器h -一徽处理器卜 j 无线收发器 上 i 数据采集模块i i 其它外设l i 无线通信模块j i 数据处m 模块! 电源 图i 一3 传感器节点体系结构 图1 4 传感器节点能量消耗情况 山东大学硕士学位论文 1 1 4 无线传感器网络的性能评价 无线传感器网络的性能直接影响其可用性，至关重要，如何评价一个传感器 网络的性能【3 】是一个需要深入研究的问题。下面是几个评价传感器网络性能的标 准这些标准还没有达到实用的程度，需要进一步的模型化和量化。 ( 1 ) 能源有效性。传感器网络的能源有效性是指该网络在有限的能源条件 下能够处理的请求数量，能源有效性是传感器网络的重要性能指标。到目前为 止，传感器网络的能源有效性还没有被模型化和量化，还不具有普遍接受的标 准。需要进行深入研究。 ( 2 ) 生命周期。传感器网络的生命周期是指从网络启动到不能为观察者提 供需要的信息为止所持续的时问。影响传感器网络生命周期的因素很多，既包括 硬件因素也包括软件因素，需要进行深入研究。在设计传感器网络的软、硬件 时，必须充分考虑能源有效性，最大化网络的生命周期。 - ( 3 ) 时间延迟。传感器网络的延迟时间是指从观察者发出请求到其收到回 答信息所需的时间。影响传感器网络时间延迟的因素也有很多。时问延迟与应用 密切相关，直接影响传感器网络的可用性和应用范围。目前的相关研究还很少， 需要进行深入研究。 ( 4 ) 感知精度。传感器网络的感知精度是指观察者接受到的感知信息的精 度。传感器的精度、信息处理方法、网络通信协议等都对感知精度有所影响。感 知精度、时间延迟和能量消耗之阋具有密切的关系，在传感器网络设计中，需要 权衡三者的得失，使系统在最小能源开销条件下最大限度地提高感知精度、降低 时间延迟。 ( 5 ) 可扩展性。传感器网络的可扩展性表现在传感器数量、网络覆盖区 域、生命周期、时间延迟、感知精度等方面的可扩展极限。目前不存在可扩展性 的精确描述和标准，还需要进一步的深入研究。 ( 6 ) 容错性。传感器网络中的传感器经常会由于周围环境或电源耗尽等原 因而失效。由于环境或其他原因，物理的维护或替换失效传感器常常是十分困难 或不可能的。这样，传感器网络的软、硬件必须具有很强的容错性，以保证系统 具有高强壮性，当网络的软、硬件出现故障时，系统能够通过自动调整或自动重 9 山东大学硕士学位论文 构纠正错误，保证网络正常工作。传感器网络容错性需要进一步地模型化和定量 化，容错性和能源有效性之间存在着密切关系。 总的说来，在传感器网络通信协议地设计中要综合考虑以上性能指标，并根 据实际要求有所侧重。在无线传感器网络中，节点通常是使用电池供电的，节能 问题对传感器网络来说是一个关键的闯题。终端设备只能装备上有限能量的电 池，而且电池的充电或更换常常是不便甚至是不可能的，故传感器网络中我们需 对节点的各个功能模块进行优化，以减少能量的消耗，延长电池的使用时间。由 于无线传感器网络通常由大量密集的传感器节点构成，网络中节点的能量资源、 计算能力和带宽都非常有限，这就决定了无线传感器网络协议栈各层协议的设计 都必须以能源有效性为首要的设计要素，如何在网络使用过程中节约能量，延长 网络使用寿命就成为了一个贯穿众多问题的最重要和基础的问题，是无线传感器 网络所面临的核心问题。 节能问题属于传感器网络研究中的跨层次问题，对它们的研究需要从网络的 各个协议层综合来考虑。在物理层需要低功耗的系统设计；在m a c 层尽量减少 碰撞的发生，同时当节点处于空闲状态时尽量关闭无线接口，设计低功耗m a c 协议等；而在路由层的主要设计目标是能源有效性路径的建立，可靠数据转发机 制的形成，尽量最小化一次路由通信所消耗的总能量同时选择能够最大化整个网 络生命周期的路径；在应用和中间件层，节能措施通常与具体应用相关。 从传感器节点各模块的能量消耗情况可知，节约能量应从无线通信模块着 手，m a c 层协议正是解决这个问题的。所以本文的研究框架定位在m a c 层上， 其中m a c 协议中的t d m a 机n t 4 1 能够为每个节点分配时隙，对所有节点的工作 与休眠时间进行合理的安排，但是由于传统的t d m a 机制在每一时隙只能安排一 个节点接收或转发，这对于节点数目十分庞大的无线传感器网络来说效率是很低 的，所以本文考虑在一个时隙安排多个节点发送数据，但是这会造成节点间的干 扰，这就需要使用c d m a 机制控制这些节点的发射功率以减少干扰，所以本文 考虑使用t d m a 和c d m a 相结合的机制f 5 】。又因为由传感器节点消耗能量的特 点可知，节点发送状态的能量消耗最多，所以高效使用网络能量需要从降低节点 的发送功率入手。 l o 山东大学硕士学位论文 基于以上两点，本文重点讨论基于t d m a c d m a 机制的节点反向链路功率 控制问题。 1 2 现行无线传感器网络的功率控制机制 在不同的通信系统中，由于系统的应用目的不相同。功率控制技术所起的作 用也不尽相同。例如在c d m a 蜂窝移动通信系统中【6 l ，功率控制由基站集中控 制，能够克服远近效应问题，消除干扰，提高信道的空间复用度，提高系统的容 量 传感器网络是个相对静止的网络 7 1 ，节点的移动性并不强，但是节点剩余电 量下降等原因将会导致网络拓扑的变化。在无线传感器网络中采用功率控制技 术，主要目的是通过调整发送节点的信号发射功率来提高信道的空间复用度，降 低发送节点能耗，同时降低对邻近节点的干扰，提高整个网络的容量。如果一个 节点的功率过高，通信距离就越远，覆盖节点多，那么无线信道将会变得更加拥 挤，信号碰撞的概率将增大，信道有效利用率降低，如果把功率调低就减小了碰 撞对邻近节点的干扰，减少了不必要的能量损耗，同时提高了信道的空间复用 度，延长了网络的寿命，提高了整个网络的容量。 现行无线传感器网络功率控制方法主要分为基于邻居节点拓扑结构的、基于 延长网络寿命的和基于提高能量效率和减小数据延时的。其中基于节点拓扑结构 的大体分为两类： ( 1 ) 文献 8 】提出本地邻居平均算法l m n ( 1 0 c a lm e a no fn e i g h b o r s a l g o r i t h m ) 。它通过用相同的发射功率发送和应答消息来确定自己的邻居数，然 后再将邻居数与节点度的上限和下限需求比较来确定发射功率。这种算法的收敛 性和网络的连通性是可以保证的，但是需要进一步研究合理的邻居节点判断条 件。 ( 2 ) 文献 9 ，l o 提出基于邻近图的功率控制算法：所有节点都使用最大功率发 射时形成的拓扑图为图g ，按照一定的规则q 求出该图的邻近图g ，最后g 中 每个节点以自己所邻接的最远通信节点来确定发射功率。这是一种解决功率分配 问题的近似解法。在传感器网络中，基于邻近图的算法的作用是使节点确定自己 山东大学硕士学位论文 的邻居集合，调整适当的发射功率，从而在建立起一个连通网络的同时，达到节 省能量的目的。 目前基于邻近图的算法还有d r n g ( d i r e c t i v er e l a t i v en e i g h b o r h o o dg r a p h ) 【】算 法和d l s s ( d i r e c t e dl o c a ls p a n n i n gs u b g r a p h ) “j 。 很多文献中无线传感器网络中的功率控制算法是通过结合m a c 协议来实现 的，比如文献 1 3 】提出的节能防碰撞m a c 协议，它要求每个节点通过了解最远一 跳邻居的信息来决定传输信息的功率，所以整个网络中没有统一的发射功率。文 献【1 4 】提出的功率控制传感器m a c 协议，它对r t s ，c t s ，d a t a , a c k 消息都进 行了功率控制，而不是象其他m a c 协议那样只对d a t a 进行功率控制。但究其 本质，这些功率控制算法仍基于网络拓扑结构。文献 1 5 】提出基于延长网络寿命 的功率控制算法，它通过将二分法应用到功率控制算法中来降低网络流量的不均 匀度，达到延长网络寿命的目的。文献【1 6 】采用排队模型对数据包到达特性及通 信过程做了建模分析，同时利用功率模式管理以降低传感器节点的功率消耗，提 高能量效率，减小数据延时。 由以上阐述可以看出，现行的功率控制算法还存在以下两个问题：( 1 ) 没 有充分考虑节点发射功率之间的干扰。在某一时刻可能会有多个节点同时传送数 据，那么这些节点的发射功率相互问会有干扰，使得节点的信噪比或其他性能例 如能量有效性降低。现行的功率控制算法并没有考虑节点间的相互干扰，在决定 发射功率时没有考虑邻居节点的发射功率。( 2 ) 算法缺乏强制性和正确激励。虽然 网络管理者根据以上算法求解出每个节点的功率，并分配给相应节点，但是如果 有些节点对管理者的分配不予理睬，那么算法同样是无效的。所以我们将对策论 引入功率控制算法中来弥补以上不足。 1 3 对策论在功率控制算法中的应用 在无线传感器网络中，发射功率是一种资源，功率控制过程其实就是根据某 个目标对功率资源进行配置的过程。这恰恰是对策论所适合解决的闯题，因此我 们将利用对策论对功率资源进行合理配置。 1 2 山东大学硕士学位论文 1 3 1 对策论的发展历史和应用领域 最早的对策思想【l 可以追溯到几千年前中国古代的“田忌赛马”和古巴比伦 法典中的“婚姻合同”。而近代对策论的发端则以齐默罗和波雷尔的“象棋博 弈”为代表。但真正形成对策论的理论体系则起始于1 9 4 4 年由冯诺伊曼( v o n n e u m a n n ) 和摩根斯坦( m o r g e n s t e m ) 合著的对策论与经济行为f f h et h e o r yo f g a m e sa n de c o n o m i cb e h a v i o r ) 书。他们引进了对策论的扩展型和正规型表示， 定义了最小最大解，提出了稳定集解概念，构建了对策论的基本框架。 对策论的第一个研究高潮【1 8 】出现在上世纪5 0 年代初，纳什( n a s h ) 在1 9 5 0 年将对策论跨展到非零和对策，提出了纳什均衡的概念和纳什均衡存在性定理， 而a w t u c k e r 则在他人实验的基础上定义了著名的“囚徒困境”( p r i s o n e r s d i l e m m a ) ，从而共同奠定了非合作对策的理论基础，1 9 5 2 - - 1 9 5 3 年，l s s h a p l e y 与d b g i l l i e s 提出“核”( c o r e ) 的概念，还给出了合作对策的“s h a p e l y 值”。古 典经济学家泽森首先认识到古典谈判理论的局限性，他指出需要建立一种可以得 到谈判的唯一理性结局( 谈判解) 的强谈判理论。不过完整的强谈判理论是由纳 什运用博弈论的思想提出的，所以现在经济学中称其为纳什一泽森谈判理论。 从5 0 年代后期到7 0 年代，对策论的发展进入第二个产生重要理论成果的阶 段。泽尔腾( s c i o n ) f 9 6 5 年提出用子博弈精炼纳什均衡对纳什均衡作完美化精炼的 思想，并在1 9 7 5 年阐述了“颤抖手均衡”( t r e m b l i n gh a n dp e r f e c te q u i l i b r i u m ) 的概 念。海撒尼( h a r s a n y i ) 贝d j 在1 9 6 7 - - 1 9 6 8 年的三篇论文中提出了不完全信息对策问 题的标准方法和贝叶斯纳什均衡的概念，建立了这一时期里程碑式的成果。在7 0 年代引起广泛关注的还有“共同知识”( c o m m o nk n o w l e d g e ) ，进化对策论 ( e v o l u t i o n a r yg a m et h e o r y ) 等。 8 0 、9 0 年代是对策论走向成熟的时期，这个时期对策论的理论框架及与其他 学科之间的关系也逐渐完整和清晰。重要的成果包括d a v i dm 融印s 和r o b e r t w i l s o n l 9 8 2 年提出了“序列均衡”( s e q u e n t i a le q u i l i b r i a ) ，海撒尼和泽尔腾1 9 8 8 年 提出了合作与非合作对策中均衡选择的一般理论及标准，1 9 9 1 年d f u d e n b e r g 和 z t i r o l e 定义了精炼贝叶斯均衡的概念等。1 9 9 4 年，诺贝尔经济学奖首次颁给三 位对策论专家：n a s h 、h a r s a n y i 和s e l t e n ，以表彰他们对非合作对策理论的产生 山东大学硕士学位论文 及发展所作出的巨大贡献；在随后的1 9 9 6 年，j a m e sa m i r r l e e s 与w i l l i a m v i c k r e y 因为在不对称信息条件下激励机制方面的基础性研究又获诺贝尔经济学 奖，对策论的地位和作用得到了最具权威性的肯定：2 0 0 5 年诺贝尔经济学奖授予 有以色列和美国双重国籍的罗伯特奥曼和美国人托马斯谢林，以表彰他们通过博 弈理论分析增加了世人对合作与冲突的理解。 对策论在经济学方面应用最广泛、理论也最成熟，但本质上，对策论不属于 经济学，它是一种方法，国际关系、军事、社会生活、工程管理还有犯罪学，都 和它密切相关。这些领域不断提出新的对策论应用课题，也不断有新的应用对策 模型产生。同样近些年来，网络通信领域也不断运用对策论解决流量控制、带宽 资源分配和功率控制等问题，甚至一些学者认为网络通信相比于经济学更适合运 用对策论，因为对策论所需的理性局中人这一条件网络通信更易满足。 1 3 2 对策论概述 对策论( g a m et h e o r y ) ，又译作博弈论，属于运筹学的一个分支，被认为是本 世纪应用数学最重要的理论成果之一，它是研究不同的主体在“策略相互依存” 情形下相互作用的科学，被公认为是研究不同主体决策互相影响、行为交互的最 佳数学工具1 1 9 1 。它与常规的优化决策理论的不同之处在于：( 1 ) 对策论中参与 者在利益上有冲突；( 2 ) 参与者要各自做优化决策，并企图使个人的利益最大 化；( 3 ) 每个主体的收益不仅取决于它自身的行为，而且也取决于他人的行 为，即个人所采取的最优策略取决于他对其他人所采取的策略的预期；( 4 ) 在 对策论中一般假定参与决策的个体均为“理性的个体”( r a t i o n a li n d i v i d u a l s ) 2 0 1 。 对策论就是系统研究各对策方具有理性能力的条件下，合理选择策略时博弈 的结果及分析这些结果的效率和意义的理论与方法。它包含三个基本要素1 2 l j ： ( 1 ) 局中人( p l a y e r ) ：即对策中选择行为或策略以最大化自己效用的决策主 体。局中人为两个的称为二人对策。局中人为两个以上的称为n 人对策或多人 对策。 1 4 山东大学硕士学位论文 ( 2 ) 策略( s t r a t e g i e s ) 或行为( a c t i o n s ) ：在同一对策( 博弈) 中，不同局中人 的可选策略或行为内容和数量也常不同，有时是有限的一种或几种，有时可能是 无限多种。有限对策和无限对策的分析方法及均衡解的存在性有非常大的区别。 ( 3 ) 得益( p a y o f f s ，也称作支付) ：得益是各个局中人从对策中所获得的利 益，是局中人追求的根本目标，它与局中人的策略密切相关，是分析对策模型的 标准和基础。不同对策的得益有不同的特征，而不同的特征和得益的差异也会影 响局中人的行为方式，从而反过来影响对策的结果和各方的得益。得益可以是正 的。也可以是负的，如果所有局中人的得益总和始终为零或者某一非零常数，则 对应的对策成为零和对策( z e r o - s 啪g a m e s ) ，或常和对策( c o n s t a n t - s u mg a m e s ) ，除 此之外的则称为变和对策( v a r i a b l e s u mg a m e s ) ，它是最一般的对策类型。 对策论可以划分为合作对策( c o o p e r a t i v eg a m e ) 和非合作对策( n o n - e o o p e r a l i v e g a m e ) 2 2 。二者之间的区别主要在于局中人的行为相互作用时，能否达成一个具 有约束力的协议( b i n d i n ga g r e e m e n 0 ，如果有，就是合作对策；反之，则是非合作 对策。合作对策强调的是集体理性，效率、公正和公平，例如谈判理论；非合作 对策强调个人理性和个人最优决策，其结果可能是有效率的，也可能是无效率 的，例如s t a c k e l b e r g 策略。这两个策略将在后续章节中结合具体问题详细讨论。 对策的划分还可以从另外两个重要角度进行。第一是局中人行为的先后顺 序，从这个角度可分为静态对策( s t a t i cg a m e ) 和动态对策( d y n a m i cg a m e ) 。静态对 策指的是局中人同时选择行动或虽非同时但后行动者并不知道先行动者的具体行 动；动态对策指的是局中人的行动有先后顺序，且后行动者能够观察到先行动者 的选择和行为。划分对策的第二个角度是局中人对其他人的特征、策略空间和得 益函数有准确的知识，则是完全信息( c o m p l e t ei n f o r m a t i o n ) 对策：否则，就是不完 全信息( i n c o m p l e t ei n f o r m a t i o n ) 对策。将上述两个角度结合起来我们得到四种不同 类型的对策：完全信息静态对策，完全信息动态对策，不完全信息静态，不完全 信息动态对策。与之对应的是四个均衡概念：纳什均衡( n a s he q u i l i b r i u m ) 子博 弈精炼纳什均衡( s u b g a m ep e r f e c t n a s he q u i l i b r i u m ) ，贝叶斯纳什均衡( b a y e s i a n n a s he q u i l i b r i u m ) ，精炼贝叶斯纳什均衡( p e r f e c tb a y e s i a nn a s he q u i l i b r i u m ) 除了 上述分类之外，动态对策又分为完美信息( p e r f e c ti n f o r m a t i o n ) 和不完美信息 f i m l ：l e f f e c ti n f o r m a t i o n ) 的动态对策。在非合作对策范围内，又可分为完全理性( f u n 1 5 山东大学硕士学位论文 m d o n m i t y ) 和有限理性( b o u n d e dr a t i o n a l i t y ) 两种。事实上，对策结构每个方面的特 征都可以作为对策分类的依据，对策结构在这些方面的差异对对策结果和对策分 析都有重要的影响。随着对策理论的发展，其分类方法也将随之发展变化。 本文将在第三章和第四章重点讨论完全信息下的合作对策和非合作对策的功 率控制，第五章讨论不完全信息下功率控制。 i 3 3 对策论在功率控制中的应用现状及本文研究内容 现行的功率控制算法着重考虑保证网络连通性即网络拓扑、延长网络寿命， 但忽视了节点发射功率之间的相互干扰，对策论的引入不但重点解决了节点发射 功率之间的相互干扰问题，而且考虑了系统收益的最大化。 目前对策论一般应用于无线数据网络【2 3 ，矧、蜂窝网络、a dh o e 网络口坷的功率 控制。文献【2 6 】，【2 7 将对策论应用于蜂窝网络中，提出了用户的收益函数，它的 物理意义是每焦耳能量所能传输的数据比特数，并给予了证明，但是它并未考虑 系统的整体利益。文献【2 8 】在无线数据网络中将用户的收益和系统的吞吐量结合 起来，提出两个收益函数：用户层收益函数，系统层收益函数。用户通过这两个 收益函数相互间分别进行用户层博弈和系统层博弈以使最后的纳什均衡结果保证 系统吞吐量最大；文献【2 9 】采用重复对策理论对用户进行功率控制，以使节点最 终达到的纳什均衡为系统最优。 上述功率控制算法既有中心化控制方式也有非中心化控制方式，但最终均能 达到系统最优，缺点是算法实现比较复杂，所以本文致力于利用对策论实现简单 的算法。 虽然对策论目前很少被应用于无线传感器网络，但是由于分簇结构无线传感 器网络【1 的“簇头一成员”结构与蜂窝网中c d m a 的“基站一移动台”结构相 似，而且c d m a 的功率控制机制已比较成熟，所以本文考虑将这些网络中的功 率控制算法借鉴到无线传感器网络中。 本文首先在第三章讨论基于s t a c k e l b e r g 策略d o 】的功率控制，它采用中心化控 制方式( c e n t r a l i z c dc o n t r 0 1 ) ，即网络管理者以某种先验目标( 例如使系统收益最大 化) 确定各个节点的功率，然后通过激励机制确保各个节点遵守这个功率。这种 山东大学硕士学位论文 方式在分簇结构传感器网络中很适用，它将网络中的节点分为若干簇，每个簇内 的节点与簇头都是邻居。簇头可作为网络管理者，它以整个簇的能量有效性( 即 每焦耳能量传输的比特数) 为先验目标来确定各个节点的功率，通过激励策略 ( 例如s t a c k e l b e r g 策略) 来保证各个节点实现分配的功率。 本文还将在第四章讨论基于谈判理论口1 ，3 2 , 3 3 】的功率控制算法，它采用非中 心化控制方式( d e c e n t r a l i z e dc o n t r 0 1 ) ，即网络中的管理者，并不参与节点之间的资 源竞争，而只是制定竞争或合作规则，竞争或合作过程均由节点自行完成。谈判 理论属于合作理论，网络管理者为节点设定谈判规则，节点为了最优化自身利益 而相互间进行协商，最后达成共识。非中心化控制方式为功率控制提供了分布式 处理的可能，减少了网络管理者的运算任务。 对策论模型为功率控制提供了一个具体的分析框架。它假定节点间存在发射 功率分配的竞争，这种竞争相当于经济学中的利益冲突，功率控制的目的是进行 节点间的利益协调，从而使功率控制达到某一特定的对策均衡解。通过研究均衡 解在工程上的含义，可以对网络的整体利益例如能量有效性作出评价，也为在不 同网络利益要求下如何进行功率控制提供了一种新的评价准则。事实上，对策论 数学模型的提出已有近6 0 年的历史，从最初的二人零和对策 3 4 1 到目前已发展完 备的非合作对策，对策论思想应用于经济和市场决策领域已经取得广泛的成功， 而簇内节点也可以被视为单个的经济实体，其追求利益最大化行为的决策过程， 系统在局中人的作用下是否存在某种均衡解或稳定解 3 5 1 ，以及局中人采取竞争与 合作等不同策略对系统均衡解的影响，都是对策论的关注点。首先，对策论分析 方法假定节点可以独立优化其关于功率控制的收益函数，而且节点具有某种“自 私”性，它只考虑自己的收益而不考虑其他节点。其次，对策论方法关心的是， 在用户独立优化其收益函数时，网络管理者制定何种竞争机制使最后的竞争结果 达到系统最优。 对策论在经济学领域的应用非常广泛已十分成熟，而市场机制固有的分布性 与w s n 功率资源的分布性也是相适应的，而且，相对于经济学中的局中人来 说，网络用户更适合“对策( 博弈) 的参与者是理性的”这一对策论的基础性假 设。因此完全可以运用经济学里的对策论理论来研究网络工程，把节点看作购买 商品的顾客，把网络资源看作商品，通过合理的激励机制调节供求关系，一方面 】7 山东大学硕士学位论文 为网络优化提供依据；另一方面能够简化功率控制功能，实现有效的分布式资源 控制和管理，这也是网络资源管理的发展方向。 在优化网络利益和功率控制中引入对策论的理