（计算机应用技术专业论文）基于博弈论的认知无线电频谱访问研究.pdf

摘要 摘要 认知无线电是近年新提出的一种无线通信的技术，它利用未授权通信用户 的频谱感知能力，动态的自适应的使用空闲频谱资源，从而提高整个频谱的利用 率。认知无线电用户可以感知外部环境，从环境中学习，并且根据环境的变化动 态地调整其内部参数，比如工作频率、发射功率、调制方式等，以便在授权用户 空闲时利用其频谱，并且在授权用户需要频谱时，及时的让出以避免对授权用户 的干扰。 认知无线电的关键问题之一就是频谱访问技术。它是未授权用户在频谱感 知得到的信息的基础上，智能的选择频段访问，并且在合适的时候进行通信。频 谱访问技术是改善认知无线电频谱利用率的最关键的因素。 博弈论是应用数学的一个分支，它是研究市场竞争中，个体之间为了最大化 自己的收益而进行相互竞争与合作的理论。在通信领域，由于广泛的存在着通信 用户之间对有限的通信资源的竞争，因此可以有效的利用博弈论的模型和理论 来解决这些问题。尤其是分布式的自主通信系统，其通信行为可以很好的用博弈 论来建模和分析。 本文旨在讨论具有广泛应用背景的分布式认知无线电系统，在这种分布式 的环境下，运用博弈论的来解决自主的认知无线电用户的频谱访问问题。具体而 言，本文的主要工作有： 1 本文研究分析了分布式的通信系统模型，并用博弈论对其进行建模。我们 将通信中的用户看成是自主的a g e n t ，它们可以自主的完成频谱感知、频谱 分配、行为决策、信号发送等通信任务，多个智能化的a g e n t 构成了竞争使 用无线频谱资源的网络，并且在博弈论的框架下完成一系列的通信任务。 博弈的结果就是各个用户合理有效的分配到频谱资源。 2 我们将通信的重要性能指标一时间也做为频谱资源的一部分，从而将频谱 的概念扩展到二维空间。基于这个二维空间下的博弈模型，我们提出了分 布式l e a m i n g b a 略a i n i n g 博弈学习算法。各个用户在二维空间中根据该算法 自主的决定通信的频谱和时间。对每个用户而言，它们的行为从时间和频 谱的角度都是自己的效用尽量最大化；而对整个系统而言，所有用户的行 为构成一个高效有序的通信过程。这种分布式的算法可以灵活应用到多种 环境下，而不用增加一个中心控制器，此外，通过时间复杂度的分析，我们 进一步证明了分布式博弈算法相对与集中式算法性能上的优越。 l 表格 3 1 3 2 3 3 3 4 3 5 3 6 4 1 4 2 4 3 4 4 4 5 4 6 表格 几个典型的时间效用函数3 3 不同算法的频谱效率对比4 2 不同算法的平均通信延迟时间对比 不同算法的最大通信延迟时间对比 4 4 14 5 不同时间效用函数的平均通信延迟时间对比4 6 不同时间效用函数的最大通信延迟时间对比4 7 已分配用户和未分配用户之间的异类博弈5 3 未分配用户之间的同类博弈5 3 协作方法下的相关概率6 0 n a s h 均衡和相关均衡收益的比较6 3 不同算法的信道利用效率的统计结果6 5 不同算法的用户通信时间统计结果6 6 i x 表格 3 1 3 2 3 3 3 4 3 5 3 6 4 1 4 2 4 3 4 4 4 5 4 6 表格 几个典型的时间效用函数3 3 不同算法的频谱效率对比4 2 不同算法的平均通信延迟时间对比 不同算法的最大通信延迟时间对比 4 4 14 5 不同时间效用函数的平均通信延迟时间对比4 6 不同时间效用函数的最大通信延迟时间对比4 7 已分配用户和未分配用户之间的异类博弈5 3 未分配用户之间的同类博弈5 3 协作方法下的相关概率6 0 n a s h 均衡和相关均衡收益的比较6 3 不同算法的信道利用效率的统计结果6 5 不同算法的用户通信时间统计结果6 6 i x 第l 章绪论 l 垒鳘錾蔓量景基囊薹薹誊篡篡篡誊誊老曩釜誊髻鏊薹鍪 筹饕毯萎兰窒垒蔫笔爱耋警鍪孽莩三荤g 一一一一一一一一一。一一一一一一一。一一一p - p - 一“hhn “ h ” 塑 ； 雾 嚣霞i 蘸 黎 纂 i l j ； 辑 ，￥l 蓁 ：融 鏖 荤姜 女接眷零黪 l ，0 ， ； 】 ： 黧 ? 翳 霞 娄 羹 薰 雾f 乏 i ： to ji ； 。i l 羹 基 l 一、一- 。； 窖 豳冒豳 匹善io ； 兰 豁露疆 = 生 鬻 j - i ； 毒 奎 l露霆 辔 警 |：| t暨 善 震 鍪 黼l壤霾l黧l 隔麟翰 霪瑷 萤黼黼 目嘲黼 _ 4q ，二二 瞄 臻强 露 强目融黜z 一 e i覃 f， 譬髻 j ，j? g ；镕 年? 黧 _ 一隧 一 g 嚣灞 爨黼翰 缀隧麓弱麓瑷 戮黧 墨 j 三， 黧震 鞫 i 叠蠡。葫端舞彰g ；s 孽蠡籀謦i。j * u二= 基 ： 薯 r r掣 ：。 v 0 i蛋受 a 霭 鬟 鍪耋蓁 聱薯 羹 冀攘 l 霪錾 羹 萋 爹 藕 囊 警 i爹 ； 巍 ；喜 笺 一 l 蠢藿 雾嚣 h |爹 l爹 霾譬 皋 叠 绷 t 鹱 2 麝c 釜孽雩曼 j ! i 豳 i i l 毒 霹嚣黑 童黛 一 事i 黯女 li g j瑟 茹 图1 1 已授权的无线频谱图 限制了频谱的使用效率。因此，需要寻求一种更有效的频谱管理方式，以充分利 用时间、空间上的空闲频段，来缓解不断增长的频谱资源的需求矛盾。 窭 一。 露 儿“_ | l j 止 f r 窜q t 堰 n e yf g h z j 图1 2 不平衡的无线频谱使用情况 1 9 9 9 年，瑞典皇家技术学院的j m i t o l a 博士在软件无线电的基础上提出了认 知无线电的概念。这种新的无线电技术能够灵活有效的管理频谱资源，极大的提 高了频谱利用率。关于认知无线电，各个研究组都有不同的定义，但是在整体的 架构上都包括了感知、理解和适应这几个部分，这里我们引入了对认知无线电概 括较为简洁而又准确的s h a y l ( i n 给出的定义 h a y l 【i n ，2 0 0 5 】： 定义1 1 ( 认知无线电) 认知无线电是一种智能通信系统，它可以感知周围环 境( 即外部世界) ，采用基于理解、认知的方法实时地从环境中学习并且通过改变 特定的通信参数来调整其内部状态以适应无线环境的统计变化。它主要有两个 目标：( 1 ) 保证在各种环境下高可靠性的通信需求；( 2 ) 保证高效率的利用无线 频谱。 这样，认知无线电系统中的用户就可以如下分类【王国强，2 0 0 7 ： ， 第1 章绪论 一级用户( 埘m a r yu s e r ，简称p u ) ：拥有授权频谱的用户，也称授权用 户( 1 i c e n s e du s e r s ) 。在传统的静态频谱管理方式下，大部分通信用户都 是一级用户，他们独占某些频段。 二级用户( s e c o n d a r yu s e r 简称s u ) ：不拥有任何频段，而利用空闲频谱进行 通信的用户也称未授权用户( u n l i c e n s e du s e r s ) 。二级用户的设备必须是认知 无线电。 1 1 2 认知无线电的认知循环 认知无线电需要和外部的射频环境实时交互，以发现空闲频谱，并决定合适 的传输参数。为此，认知无线电需要完成多个任务，这些任务及它们之间的关系 被称为“认知循环 ( c o g n i t i v ec y c l e ) m i t o l ai i i ，19 9 9 。 j m i t o l a 博士提出的认知无线电的认知循环如图1 3 所示： 定向 确立优先级 图1 3j m i t o l a 提出的认知循环 其中，认知循环的步骤如下： 1 观察( o b s e r v e ) ：分析外部射频环境，并推断通信内容。例如，如果发现一个 用户通过电话预定了出租车，则可推断出此用户将乘坐出租车出行。 2 定向( 0 n e n t ) ：确定通信的优先级。优先级分为三种：立即( i m m e d i a t e ) ，紧 急( u r g e n t ) 和正常( n o 姗a 1 ) 。 3 计划( p 1 a n ) ：产生并评估解决方案，包括把解决方案发送给网络中的其他认 知无线电以获取反馈意见。 3 第l 章绪论 1 1 3 3 功率控制 功率控制( p o w e rc o n 的1 ) 是指射频发射端为了保证自身的通信质量和避免对 其他通信系统的干扰而对自身的发射功率进行的控制。在认知无线电中，由于需 要动态的访问频谱，p u 和s u 之间不能相互产生干扰，因此功率控制将尤为重要。 在多用户传输的c r 系统中，发送功率控制受到给定的干扰温度和可用频谱空洞 数量的限制，目前解决功率控制这一难题的主要技术是博弈论( g a m et h e o r y ) 和信 息论( i n f o 珊a t i o nm e o r y ) 【h a y l ( i n ，2 0 0 5 】。 1 1 4 认知无线电的应用 做为一项新的无线通信技术，认识无线电有着非常广阔的应用前景。目前， 虽然认知无线电的很多问题尚处于理论探索阶段，但是已经在部分领域已经开 展了直接面向应用的研究。 1 1 4 1 军事 认知无线电在军事上应用有着非常重要的意义。它不需要如商用系统中的 基础设施就可以实现和其它设备的通信，并且能够根据环境变化自我调整参 数以保证通信质量，能够和不同无线电标准的设备进行通信，能够检测出敌方 的传输等。美国国防部最近几年已经投入了大量人力物力进行这方面的研究， 如：s p e a k e a s yr a d i os y s t e m ，j o i n tt a c t i c a lr a d i os y s t e m ( j i r s ) ，n e x tg e n e r a t i o n ( x g ) 等项目。 1 1 4 2 公共安全 当紧急事件发生时，分配给公共安全的频谱通常很快会被突发的各种通信 阻塞，并且各个应急部门之间由于所拥有的频谱不同很难互相进行通信。有了认 知无线电技术后，当紧急事件发生时就可以利用空闲频谱维持通信，不会因为负 载过大而阻塞，而且还可以实现不同应急部门之间的通信。美国这方面的研究项 目有s a f e c o m 等。 1 1 4 3i e e e8 0 2 2 2 工作组 2 0 0 4 年1 0 月，i e e e 正式成立i e e e8 0 2 2 2 工作组，又称为无线区域网络( w i r e l e s s r e g i o n a la f e an e t w 0 1 k ，简称w r a n ) ，目的就是使用认知无线电技术将分配给电 视广播的v h f 厂u h f 频带( 北美为5 4 8 6 2 m h z ) 用作宽带访问线路。i e e e8 0 2 2 2 制 定的是无线通信的物理层与m a c 层规范，其数据通信速率为数m b i t 秒至数 十m b i t 秒，它是第一个引入认知无线电概念的i e e e 技术标准化活动，目前的标 准化工作已经基本完成【i e e e8 0 2 ，2 0 0 7 】。 气 第l 章绪论 1 。2 认知无线电中的频谱访问问题 1 2 1 频谱访问模型 在前面的c r 认知循环和关键技术中，很大一部分都涉及到了动态频谱访 问的技术。做为认知无线电中的关键技术之一，动态频谱访问技术在近几年的研 究中产生了几种不同的模型。如图1 4 所示，动态频谱访问策略可以分为如下三 种模型 z h a oa n ds a d l e r ，2 0 0 7 ；z h a oa n ds w a i i l i ，2 0 0 7 b 】： 图1 4 动态频谱访问分类 1 2 1 1 动态独占式模型 动态独占式模型( d y n a m i ce x c l u s i v eu s em o d e l ) 保持了当前频谱使用策略的基 本结构：频段授权给用户独占使用。它通过引入了一定的灵活性来改善频谱效 率，主要有频谱使用权和动态分配两种方式。 1 频谱使用权( s p e c t m mp r o p e r t yn g h t s ) 允许被授权用户在其不使用频谱时出 租频段。在这种方式中，授权用户希望通过其他未授权用户共享有限的频 谱资源来最大化自己的利益。 2 动态分配频谱( d y n a m i cs p e c t r u ma l l o c a t i o n ) 有别于我们前面提到的广义上的 动态频谱分配，它通过探寻不同用户在通信时时间和空间上的频谱空洞动 态的指派频谱资源改善频谱效率。 基于动态独占式的d s a 模型在一定程度上提高了频谱效率，但是它依然没 有摆脱原先静态频谱分配固定划分授权频段的缺点，因此无法消除有突发式无 线通信引起的白色频谱空洞。 6 第1 章绪论 1 2 。1 2 开放式共享频谱模型 开放式共享频谱( o p e ns h 撕n gm o d e l ) 也叫频谱公有( s p e c t m mc o m m o n s ) ，这 种模型在对等的用户之间使用开放式共享技术。这种方式有集中式和分布式两 种实现手段。 1 - 2 1 3 等级式访问模型 等级式的访问模型( h i e r a r c h i c a la c c e s sm o d e l ) 将用户按照等级划分，即前 面所说的一级和二级用户。基本思想是将p u 的授权频谱开放给s u 使用，同时 避免或限制s u 对p u 的干扰以保证p u 的正常通信。这种方法可以分为频谱铺 垫( s p e c t m mu n d e r l a y ) 和频谱交叠( s p e c t m mo v e d a y ) 两种方式。 1 s p e c 仰mu n d e r l a y 的方法对s u 的发射功率进行了严格的限制以使s u 可以 在p u 的噪声门限( n o i s ef l o o r ) 以下工作而不会对p u 产生干扰。u n d e r l a y 的方 式可以和超宽带( u l t r aw i d eb a n d ) 技术结合起来，并且不用依赖于频谱空洞 的检测。但是这种方法要求硬件具有前端干扰抑制、低功率高速率的电路 设计以及对信道延迟的估计能力，因此主要的挑战来自于硬件实现方面。 2 s p e c t l l j mo v e r l a y 的方法即机会式频谱分配( o p p o r t u n i s t i cs p e c t r u ma 1 1 0 c a t i o n ， 简称o s a ) ，它是由j m i t o l a 的“频谱池( s p e c t m mp o o l i n g ) ”的概念演变而 来 m i t o l ai i i ，1 9 9 9 】。s u 探索时间和空间上的未被p u 使用的频谱空洞，利用 这种频谱机会进行通信，并且在p u 重新需要使用这一部分频谱的时候再让 出这一部分频谱。使用s p e c t m mo v e r l a y 的c r 系统没有对s u 的传输功率的 严格限制，但是需要在频谱感知的基础上侦别出时间或者空间上的频谱机 会。 相对于动态独占式模型和开放式共享频谱模型，等级式访问模型是和 当前无线通信系统的频谱管理策略更兼容，并且灵活有效的频谱访问方 法。u n d e r l a y 和o v e r l a y 可以同时进行更深入的研究以改善频谱效率。本文主要关 注了o v e r l a v 的机会式频谱访问方法。 1 - 2 2 频谱访问的关键问题 机会式频谱访问是认知无线电中非常重要的研究方向，这其中有一些关键问 题需要解决。它包括了频谱机会的确认( s p e c t r u mo p p o n u n i t yi d e n t i f j c a t i o n ) 、频谱 机会的利用( s p e c t m mo p p o r t u n i t ye x p l o i t a t i o n ) 、多二级用户的频谱分配( s p e c t m m a l l o c a t i o nf o rm u l t i p l es e c o n d a l r yu s e r s ) 以及一些跨层的协议设计和规范化的策 畔子( c r o s s - l a y e rp r o t o c 0 1a n dr e g u l a t o r yp o l i c y ) 。 7 第l 章 绪论 当多个可用的频谱机会存在时，如何选择信道是c r 中新出现的问题。在选 择信道上，必须考虑信道被p u 重新使用的可能性，当多个频谱机会存在时，s u 应 当尽量选择这种概率较小的信道。因为，s u 总是希望在自己的服务时间内可以 持续的使用某一段频谱，如果这段频谱再次被p u 占用，s u 将被迫中断或者切换 到其他频段。这种中断如果频繁的发生，那么将严重的影响到s u 的通信质量。这 一部分也可以和上一节感知信道的选择结合起来考虑。 此外，通信的调制方式和传输功率也是一个值得讨论的问题。一个合适的调 制方式可以最大程度的保证通信质量并且抑制干扰，目前，利用正交频分服用技 术o f d m ( o n h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g ) 设计机会式频谱访问的通信 系统是一个很好的选择【b e n h 0 1 da n dj o n d r a l ，2 0 0 5 。传输功率的控制是o s a 网络 中的重要步骤，当考虑到干扰、衰减和阴影效应是，我们需要构建一种概率模型 来处理o s a 中功率控制问题。 1 2 2 3 多个二级用户的频谱分配 在无线通信中往往并不仅仅存在着一个s u ，当有很多s u 存在时，如何利用 频谱以避免和其他s u 造成冲突，同时使整个系统的通信效率最高是个必须面对 的问题。 s u 之间共享频谱机会可以从时间、频谱、空间、功率等几个方面去考虑。时 间上的共享是指在特定的空间里，一段频谱从时间上进行划分，并且分配给多 个s u 使用。频谱上的共享是指在一定时间一定空间内，将一段可用频谱划分成 多份，分配个多个用户使用。空间上的共享是指在某一时间段内，认为频谱情况 是不变的，这时在不同的区域内可以让多个s u 使用同一段频谱而相互之间不发 生冲突。功率上的共享就是通过功率控制技术、滤波技术和信号处理技术，将不 同功率的信号进行叠加发射出去，在接收段将有用的信号分离出来，而将其他信 号当做噪声滤除。 多个s u 存在的情况下，c r 的复杂度要远远高于单个s u 的情况，因为此时不 仅要考虑s u 与p u 之间的关系，还需要考虑s u 之间的关系。多个s u 频谱分配的目 标就是在不影响p u 通信的前提下，是各个s u 都能够尽快的获得自己需要的频谱 资源，同时它们之间的干扰尽量少，这就要求我们不仅要考虑通信系统的效率， 还要考虑整体的公平性和复杂度。如何处理好s u 之间的竞争与合作是一个很有 挑战性的问题。 对于分布式系统，由于不存在一个中心控制器，各个s u 在资源有限的情况 下对频谱的使用过程可以看作是一个竞争过程，这种竞争包括了通信时间上先 后的竞争和通信频率上的竞争。每个s u 都在使用频谱时，都希望能够最大程度 的满足自己的通信需求，而这样对于整个系统来说，无序的竞争反而可能导致 q 第1 章绪论 整体性能的低下。所以，要提高多个s u 的频谱分配效率就必须让各个s u 按照 定的规则或者算法进行频谱使用。由于博弈论的思想和模型可以很好的满足多 个s u 竞争频谱资源的情景，因此，用博弈论研究多用户间的频谱分配问题得到 了越来越多的关注。本文的主要工作就是沿着这一问题展开的。 1 2 2 4 协议与规范 规范化的策略对c r 来说非常重要，因此c r ，尤其是o s a 系统，就是建立 在p u 与s u 、以及s u 之间的协作与共同使用频谱资源的基础上的。由于频谱访问 的策略涉及到感知、决策、信息交互等多个过程，因此合适的协议必然是一个覆 盖了物理层和链路层的跨层协议。物理层的协议主要负责频谱感知、信道估计和 数据的传输，而链路层则要保证p u 与s u 之间、s u 相互之间的通信和链路管理。 此外，由于涉及到s u 的公平性和优先级的问题，协议还可能涉及到更高的网络 层等的设计。 1 3 基于博弈论的频谱访问研究 1 3 1 频谱访问问题的研究现状 目前，认知无线电技术还处于研究的初级阶段，对于频谱访问的研究，国内 外各个研究组的工作还处于对局部问题的探索阶段。但是，随着学术界和工业界 对认知无线电越来越多的关注，认知无线电的频谱访问研究也取得了飞快的进 展。 1 3 1 。1 b e r k e i e y 研究组 u n i v e r s i 哆o fc a l i f o m i ab e r k e l y 的认知无线电研究组提出了使用虚拟非授权 频谱的c o r v u s 框架【e a b r i 已f 口z ，2 0 0 5 】。c o r v u s 系统也工作在频谱池上，频谱 池进一步被分为n 个大小相同的“子信道”。每个一级用户的频段可能占有多个子 信道。一对二级用户需要通信时，选择一组空闲的子信道形成一个二级用户链 接( s u l ) ，这个二级用户链接的子信道可能分布到多个一级用户的频段中。二级 用户形成二级用户组( s u g ) 来协作它们的通信，不允许不同二级用户组的二级 用户之间直接的点对点通信。二级用户使用专门的逻辑信道以交换控制和感知 信息，有两个不同的逻辑控制信道，一个全局控制信道和一个组控制信道。全局 控制信道是全局唯一的，被所有二级用户所知，全局控制信道的主要目的是通告 存在的组并授予相关的传输参数，以使新来的二级用户加入到一个二级用户组； 每个组的组控制信道的主要目的是进行组控制和感知信息的交换。文献 m i s h r a p f 口z ，2 0 0 5 】提出了一个c o r v u s 测试平台，以评估物理层、链路 1 0 第1 章绪论 拥塞控制、路由、功率控制、拓扑控制、信任管理以及其他的有线或者无线通信 系统。博弈论做为一个分析无线网络的工具有着明显的优势：通过对相互依赖的 决策者的建模，博弈论可以让我们构建出一个不需要拥有网络全局信息的中心 实体的场景。 1 3 3 博弈论在频谱访问中的应用 认知无线电中采用的是动态频谱分配的方式，二级用户可以根据频谱环境 决定自己使用哪些频谱。由于这种频谱资源是有限的，所以，各个用户在使用的 时候必须合理有效的协调好各自的行为，既要充分利用资源不造成浪费，又要避 免过度使用资源造成相互之间的负面影响。因此，我们很自然的想到可以用博弈 论来研究这种有限资源下，各个用户之间的竞争与合作。目前，已经有很多研究 组利用博弈论进行这方面的研究。通常是考虑分布式的自适应用户的通信模型， 各个用户之间相互博弈，自主的决定通信参数。比如，在功率分配时，各个用户 为了提高通信效果，通常希望增加自己的发射功率，但是较高的发射功率又会给 其他用户造成干扰，因此，用户之间就可以通过博弈最终达到一个能够满足通信 效果，又不致于造成过多干扰的功率水平。 在认知无线电的频谱访问研究上，可以用博弈论来描述自主用户对频谱资 源的竞争。通常将每个用户的选择的频谱或者信道做为用户博弈的行为，而将受 到的干扰做为评价博弈效果的收益函数。各个用户在博弈中形成的均衡状态，就 是每个用户都不能单方面通过仅仅改变自己的行为( 改变频谱或信道) 而提高收 益( 降低受到的干扰) 。 用博弈论研究多个用户频谱访问问题时，不同的具体问题需要不同的方法。 当全面考虑时间、频谱等多个方面的频谱共享时，由于维数的增加，博弈就变的 较为复杂，并且计算量也大大增加。这时就需要建立合理的博弈模型，并且运用 高效的算法来达到较优的结果。另外，博弈并不仅仅存在与未分配到频谱的用户 之间，在已经使用频谱的s u 与尚未分配到频谱的s u 之间同样存在着博弈。这也 需要不同的博弈模型进行描述和分析。 博弈论有着严格的数学定义和丰富的理论基础，因此用博弈论进行通信方 面的研究，有助于我们建立性质良好的模型和进行深入的分析。博弈论本身也正 处于发展之中，越来越多的新的概念和思想为它的应用提供了更多的研究方法 和理论。本文是基于博弈论的频谱访问的研究，其中涉及到博弈学习理论、均衡 理论、合作理论等，我们将在后面的章节里对这些理论和应用做详细的介绍。 1 4 第1 苹绪论 1 4 本文的主要研究内容和创新之处 认知无线电是一种新兴的通信技术，它的研究成果将极大的改善无线通信 频谱紧张的现状。认知无线电的研究刚刚开始兴起，本文主要关注了认知无线电 当中非常重要的频谱访问的研究。目前频谱访问的研究已经出现了各种不同的 思路和方法，我们的工作主要研究了多个二级用户之间访问频谱、竞争频谱资源 的情况。我们先是将频谱访问问题提取主要特征进行数学建模，在数学模型的基 础上提出一些关键性的频谱访问算法提高单个通信用户的通信效率以及整个通 信网络的频谱利用率。本文用博弈论描述自主通信系统之间竞争频谱资源的过 程，建立了针对不同问题的具体博弈模型，并基于博弈提出相应的分布式博弈算 法，最终的目的是达到个体和整体高效的频谱利用率。 本文的创新之处在于： 1 本文着重研究了分布式的通信系统模型，并用博弈论对其进行建模。我们 将通信中的用户看成是自主的a g e n t ，每个通信个体根据外部环境进行博弈 从而获得资源。这种分布式的博弈模型体现了频谱资源有限情况下，各个 通信a g e n t 之间的竞争与合作，具有自适应、自学习的特点，可以方便灵活 的应用的各种通信环境中。 2 扩展了频谱资源的概念，建立了二维空间中的博弈模型，并提出了相应 的分布式l e a r n i n g b a r g a i l l i n g 博弈学习算法。二维空间的博弈模型既考虑 了通常意义下的频谱利用率，又关注了通信用户的时间效率，它是从频 率时间的二维空间中描述博弈过程。此外我们将分布式博弈中的n o r e g r e t l e a n l i n g 算法和n a s hb a r g a i n i n g 过程结合起来进行求解。通过时间复杂度的 分析，我们进一步证明了分布式博弈算法相对与集中式算法性能上的优 越。 3 基于c h a i n s t o r e 博弈建立动态场景下频谱竞争模型，并引入共有信号来使 通信用户的行为达到比n a s h 均衡性能更优的相关均衡。我们将新到达用户 和已有用户的竞争行为描述成市场竞争中新兴企业与垄断企业之间的连锁 店博弈，这种博弈非常吻合认知无线电系统的特点。此外，为了提高整体 的频谱使用效率，我们通过一种共有信号来协调各个通信用户之间的行为， 从而使整个博弈最终达到稳定而又高效的相关均衡。 1 5 本文的组织结构和章节安排 本文共五章，各部分内容的组织结构如图1 5 所示： 下面简要介绍一下各章节的内容： 1 5 第2 章认知无线电频谱访问的博弈模型 第2 章认知无线电频谱访问的博弈模型 2 1 博弈论基本概念与模型 博弈论是研究分布式网络中的通信实体之间交互的非常有力的数学工具， 它研究的是智能的理性决策者之间交互影响的决策问题。本章将介绍博弈论的 基本定义和相关的解的概念，同时将阐述如何运用博弈论为认知无线电的频谱 访问问题进行建模。有关博弈论的更多的探讨可以参见【f u d e m b e r ga n dt i r o l e ， 1 9 9 1 ；f u d e m b e r g ，d p f 以正，2 0 0 2 ；0 s b o m ea n dr u b i n s t e i n ，1 9 9 4 】 2 1 1 博弈的基本要素 最基本的博弈由三种元素组成g = ：参与者( p l a y e r ) 集合他 、每个参与者的行动空间( a c t i o ns p a c e ) a 、收益函数( p a y o f f f u n c t i o n ) 或者效 用函数( u t i l i t yf u n c t i o n ) 。 参与者是做出理性决策的个体，各个参与者构成了整个博弈的参与者集合。 动作n ：是参与者钆所做出的决策。参与者的动作集合a 。= n n ) 是该参与者可以 做出的所有的动作集合。一个动作组合( a c t i o np r o i i l e ) q = o n ) 。是博弈中所有 参与者所做出的动作的序列向量，每个元素都由相应的参与者做出。 参与者仡的收益乱。( n ) 是动作组合n 的函数，它描述了参与者如何从每个可能 的动作组合中获得收益。通常，我们认为博弈中的个体都是理性的( r a t i o n a l ) ， 也就是每个参与者的目的就是通过自己的动作决策最大化自己的收益。 博弈论可以分为非合作博弈和合作博弈两大类。它们的区别在于相互发生 作用的当事人之间有没有个具有约束力的协议，如果有，就是合作博弈，如果 没有，就是非合作博弈。由于合作博弈论比非合作博弈论复杂，在理论上的成熟 度远远不如非合作博弈论。 从行为发生的时间性看，博弈论进一步分为两类：静态博弈( s t a t i s t i c g a m e ) 是指在博弈中，参与人同时选择或虽非同时选择但后行动者并不知道先 行动者采取了什么具体行动；动态博弈( d y n a m i cg a m e ) 是指在博弈中，参与人 的行动有先后顺序。且后行动者能够观察到先行动者所选择的行动。静态博弈中 最著名的例子就是“囚徒困境( 州s o n e r sd i l e m m a ) ” f u d e m b e r ga n dt i r o i e ，1 9 9 1 ； f u d e m b e r g ，d p f 口7 ，2 0 0 2 ；0 s b o r n ea n dr u b i n s t e i n ，1 9 9 4 】；而棋牌类游戏等决策或 行动有先后次序的，属于动态博弈。 博弈中一个非常重要的概念就是参与者的信息( i n f o m l a t i o n ) 。按照参与人 对其他参与人的了解程度分为完全信息博弈和不完全信息博弈。完全博弈是指 2 1 第2 章 认知无线电频谱访问的博弈模型 在博弈过程中，每一位参与人对其他参与人的特征、策略空间及收益函数有准确 的信息。如果参与人对其他参与人的特征、策略空间及收益函数信息了解的不够 准确、或者不是对所有参与人的特征、策略空间及收益函数都有准确的准确信 息，在这种情况下进行的博弈就是不完全信息博弈。不论何种信息的博弈，为了 最大化自己的收益，参与者都要设计出策略( s t r a t e g y ) ，它实际上就是从每个参 与者的信息集合映射到其动作的函数。策略可以是纯策略( p u r es t r a t e g y ) ，它只 包括了每个信息集合所对应的确定性的动作；或者是混合策略( m i x e ds t r a t e g y ) ， 它表示了根据概率向量所选择的动作集合中的动作。 2 1 2n a s h 均衡 n a s h 均衡是因数学家j o h nn a s h 教授而命名的，n a s h 在1 9 5 9 年运用角谷静夫 不动点定理( k a k u t a t l j6 x e dp o i n tt h e o r e m ) 证明了非合作博弈中n a s h 均衡的存在 性【n a s h ，1 9 5 1 。n a s h 均衡是一种策略组合，使得每个参与者的策略是对其他参 与者策略的最优反应。 定义2 1 ( n a s h 均衡) 策略组合盯+ 是一种n a s h 均衡，如果对于所有参与者i 有： 让i ( 口；，盯二t ) u l ( o i ，盯二t ) ，v o i 西 这里我们用矿一。和。一。表示除了参与者i 之外的所有其他的参与者的行动组 合。已经证明混合策略的n a s h 均衡( 有可能退化为纯策略n a s h 均衡) 在任意的完 美信息博弈中都存在，而纯策略n a s h 均衡有可能不存在【n a s h ，1 9 5 1 ；f u d e m b e r g a n dt i r o l e ，1 9 9 1 ；f u d e m b e r g ，d e f 以，2 0 0 2 】。 n a s h 均衡是对关于博弈将会如何进行的“一致”的理性的预测，处于n a s h 均 衡下的所有的参与者都没有改变自己行为的意图，因为这是在其他参与者不改 变他们行为的情况下的最优结果。事实上，n a s h 均衡具有这样良好的性质：博弈 中的参与者可以预测它，也可以预测到其他的参与者也会预测到它的发生，如此 继续。因此，如果所有的参与者都预测到某个n a s h 均衡会发生，那么没有一个参 与者会有兴趣去故意违背。 很多博弈往往具有不止一个n a s h 均衡。n a s h 均衡本身并没有告诉我们 当多个n a s h 均衡存在时，到底哪一个才是博弈最合理的预测。此时，要么 在博弈的规则中添加更多的细节，比如聚点( f o c a lp o i n t s ) 、风险占优( 一s k d o m i n a n c e ) 、p a r e t o 最优( p a r e t oo p t i m a l ) 均衡等等；要么就诉诸于均衡精 练( e q u i l i b r i u mr e f j n e m e n t ) 的办法。 2 1 3 博弈学习理论 传统的博弈论的研究集中在均衡问题上，一般认为均衡是在博弈的规则、 2 2 第2 章认知无线电频谱访问的博弈模型 参与者的理性以及参与者的收益函数都是共同知识的情况下，由参与者的分析 和自省所得出的结果。然而，n a s h 最初关于的均衡不动点解的证明是非构造性 的( n 6 n c o n s t m c t i v e ) ，就是说n a s h 用角谷静夫不动点定理证明了平衡不动点解 是存在的，但却不能指出以什么构造算法如何去达到这个平衡不动点解。这种非 构造性的发现对现实生活里的博弈的作用是有限的，即使知道平衡不动点解存 在，在很多情况下达不到并不能解决问题。 对于均衡的另一种解释是：均衡是有限理性的参与者随着时间的推移寻 求最优化这一过程的长期结果 f u d e n b e 曜a n dl e v i n e ，1 9 9 8 ；f u d e n b e 曜，d p f 日z ， 2 0 0 4 】。这实际上就是参与者根据过去的信息不断进行学习的过程。学习模型能 够为评价和改进传统的均衡概念提供有用的方法，也会产生n a s h 均衡的精练解。 在传统的博弈论中，要求参与者具有完美理性( p e r f e c tr a t i o n a l i t y ) ，也就是 说如果参与者知道我们所知道的关于该博弈的所有事情，那么它就可以做出我 们所能做出的任意的推论。这就好比参与者就是一台超级计算机，它根据已知 可以计算出未来的任意步的结果。在现实世界中，这一条件往往是很难满足的。 而博弈学习理论抛弃了传统博弈论中基本要求的完美理性假设，参与者往往是 根据历史信息做出判断，选择对前一阶段历史统计结果的最优反应。它们的动 作可能并不是对未来很多步进行预测的结果，而可能是短期内的短视的最优反 应( m y o p i cb e s tr e s p o n s e ) 的结果。这种有限理性( b o u n d e dr a t i o n a l i t y ) 的参与者 经过很多轮的单步博弈之后，常常可以收敛到博弈的均衡状态。当然，学习过程 不一定收敛( c o n v e r g e n c e ) ，而且即使它们收敛，在某些情况下也需要很长的时 间。这方面问题的解决往往取决于具体博弈学习模型的特性以及实际应用背景 的要求。 本文第三章主要是基于博弈学习理论，同时结合n a s h 的b a 唱a i n i n g n a s h ， 1 9 5 0 】过程来解决分布式频谱访问中各个用户自主选择频谱的问题。 2 1 4 相关均衡 n a s h 均衡的是博弈论中具有及其重要的意义与价值的概念，它的前提是 在参与者独立的选择自己的策略。事实上，在许多博弈中，参与者的策略的 选择是相关的，比如他们可以进行事先的讨论，或者通过某种“信号设备”来沟 通。a u m 柚n 的相关均衡( c o r r e l a t e de q u i l i b r i u m ) 概念讨论了通过任意这种信号可 以达成的结果【a u m a n n ，1 9 7 4 ，1 9 8 7 。 通过相关机制，博弈中的参与者可以达成对策略的某种共识，在这种共识 下的参与者的策略可以使自己的效益最大化。共识相当与基于相关性的某种“建 议”，相关均衡就是没有参与者有兴趣偏离这种建议，因为在其他参与者服从建 议的情况下，该参与者的当前收益是最大的，也就是说，如果其他参与者服从给 2 3 第2 章认知无线电频谱访问的博弈模型 他的建议，那么参与者j 不能通过不服从建议而获益。相关均衡的数学描述如下： 定义2 2 ( 相关均衡) 相关均衡是纯策略& s ，上的任意概率分布p ( ) ，使 得对于每个参与者i 和从s 到& 的任意函数幺( ) 有： ：p ( s ) ( s i ，s i ) ：p ( s ) u ( 觑( 鳓，s i ) s ss s 事实上，纯策略n a s h 均衡是分布p ( ) 退化的相关均衡。混合策略n a s h 均衡也 是这样一种相关均衡：仅仅需要取p ( ) 为均衡策略时导致的联合分布，这样对于 每个参与者的建议就没有传达关于其对手行动的任何信息。从另一角度看，相关 均衡实际上相当与在适当设置巧妙的信号装置下博弈的“条件”n a s h 均衡。 由于n a s h 均衡在有限博弈中存在，相关均衡也相应存在。实际上，相关均衡 的的存在性比n a s h 均衡更加简单，因为相关均衡集是用线性不等式组定义，因此 是凸的。相关均衡的求解将比n a s h 均衡更简单，它可以通过线性规划的方法解 出，而且对于非n a s h 均衡的相关均衡可能达到比n a s h 均衡更高的收益。 本文第四章具体讨论了在连锁店博弈( c h a i ns t o r eg a l n e ) 的模型中引入相关 均衡来解决频谱访问问题。 2 2 频谱访问问题的博弈模型框架 2 - 2 1分布式的认知无线电模型 认知无线电二级用户通过感知周围环境，白适应的选择一级用户( 授权用 户) 暂时不使用的频谱进行通信，而在一级用户需要频谱时再出让频谱资源重新 寻找新的频谱通信，通过这种充分利用频谱的方式从而提高频谱利用率，缓解频 谱资源紧张的状况。因此，认知无线电中一个关键问题就是二级用户的频谱分配 问题。我们考虑多个二级用户存在时，当一级用户的频谱空闲时，这些二级用户 将共同竞争使用这些频谱，并在一级用户要求频谱时自动让出。 如何使二级用户有效的调配使用这些频谱资源是频谱访问的核心问题。通 常有两种解决方法：集中式和分布式。集中式的方法就是在一定区域内架设一个 具有中心控制器的中心节点，中心节点收集到环境中的频谱信息和用户信息，然 后由中心控制器计算得出一个合理有效的分配方案，再统一的为各个二级用户 分配频谱资源。这种方式减轻了用户节点的计算开销，同时可以从全局考虑调配 资源，往往可以得到一个比较理想的分配效果。但是，它的缺点也是很明显的， 架设中心节点的花费较大，收集外部信息需要耗费较多的通信资源，另外集中式 方法缺乏灵活性，对于无线网络结构变化较快的场景适应性不够。 另外一种方式是分布式的方式，它可以基于a d - h o c 等无线网络，在一定区域 中不设中心控制器，每个二级用户独立具有感知、分配的功能，它们通过自身的 2 4 参考文献 n a s h ，j ，1 9 5 0 ，“t h eb a 唱a i n i n gp r o b l e m ”，e c o n o m e t r i c a1 8 ，1 5 5 n a s h ，j ，1 9 5 1 ，“n o n c o o p e r a t i v eg a m e s ”，t h ea n n a l so f m a t h e m a t i c s5 4 ( 2 ) ，2 8 6 o s b o m e ，m ，a n da r u b i n s t e i n ，l9 9 4 ，ac d “瑙已加g a m 已刀l 已d 删( m i tp r e s s ) 第3 章二维频谱空间博弈学习模型及算法 第3 章二维频谱空间博弈学习模型及算法 在频谱资源有限的无线网络中，部分节点由于无法分配到频谱而需要延迟， 因此在对系统进行频率分配的同时还要对它们的通信时间次序进行安排。本章 构建了新的频率一时间的频谱模型，在这个二维的频谱空间中进行频谱一时间的联 合分配。各个节点利用l e a m i n g b a r g a i n i n g 算法进行博弈学习并且通过谈判提高