博弈论在频谱共享中的应用

《博弈论在频谱共享中的应用》由会员分享，可在线阅读，更多相关《博弈论在频谱共享中的应用（8页珍藏版）》请在金锄头文库上搜索。

1、 - 1 - 博弈论在频谱共享中的应用博弈论在频谱共享中的应用 胡玉佩，曾令康 北京邮电大学电子信息工程学院，北京 (100876) 摘摘 要：要：博弈论（Game Theory）是专门用于研究若干个体之间竞争有限资源的数学理论。 博弈论已被成功用于研究无线网络资源分配最优化和提高效率的问题。 本文首先简单介绍了 博弈论的基本概念；然后按照不同的分类准则，考虑无线网络资源分配的实际情况，描述了 两种常用的博弈论类型： 非合作型博弈论和合作型博弈论， 并对这两种博弈论在无线网络资 源分配中的应用列举了若干实例。 关键词：关键词：博弈论；非合作型博弈论；合作型博弈论；纳什均衡；帕累托最优 1. 引

2、言引言 在目前的无线网络系统中， 为了避免或是减轻不同无线技术之间的干扰， 广泛采用固定 的频谱分配政策， 即由国家政府机关进行频谱分配， 将一部分频谱分别划分给指定的机构进 行特定的服务， 如无线电视、 蜂窝系统、 WLAN 等， 被指定分配的频谱称为授权频谱 （licensed band），未被指定分配的频谱称为未授权频谱（unlicensed band），由国家机关授权使用某 授权频谱的机构则被称为该授权频谱的授权用户（licensed user），反之则被称为未授权用 户（unlicensed user）。大多数情况下，在无线网络中出现的科技创新都是基于未授权频谱 的。近年来，随着无线

3、技术的快速发展，新业务层出不穷，使原本就已非常有限的未授权频 谱变得越来越拥挤，加剧了频谱资源有限性引起的频谱资源匮乏问题。 但是，频谱的匮乏是相对的，而不是绝对的，这种匮乏是由当前频谱资源管理上存在着 的供新业务使用的频谱匮乏和已授权频谱使用效率不高这两个问题共同引起的。 从美国联邦 通信管理委员会（Federal Communications Commission）提供的测量数据来看，授权频谱远 远没有得到充分的利用，其利用率随着时间的变化和地理环境的不同，一般在 15%85%之 间1。因此 FCC 考虑用实时动态的方法代替已有的固定分配方法进行频谱分配，以解决上 述资源匮乏问题。按照实时

4、动态分配频谱的思想，FCC 提出一项新的政策2，将认知无线电 （Cognitive Radio）技术应用于无线网络系统中。在此类系统中，授权用户划出部分或是全 部授权频谱资源，按照一定的准则，使认知用户即未授权用户可以使用该频谱。为了保证授 权用户的绝对传输质量， 未授权用户的发射功率和工作频谱都要受到严格限制， 因此需要未 授权用户合理有效地分配资源，提高系统效益。在现有的知识体系中，博弈论是专门用于研 究多个利益共同体之间竞争有限资源的数学工具， 并且近年来理论体系不断完善， 日趋成熟。 实际上，博弈论已经在不同领域得到了广泛的利用，如经济学，政治学，生物学等3。同样， 博弈论在无线网络中

5、的应用已经引起了越来越多的重视， 并且对于无线系统的分析起到巨大 的推进作用。为了紧跟技术前沿，本文将对博弈论在资源分配中的应用进行简单的介绍。 2. 博弈论博弈论 博弈论(Game Theory)，有时也称为对策论，或者赛局理论，是应用数学的一个分支, 目 前在生物学，经济学，国际关系，计算机科学, 政治学，军事战略和其他很多学科都有广泛 的应用。博弈论主要研究公式化的激励结构（游戏或者博弈）间的相互作用，是研究具有斗 争或竞争性质现象的数学理论和方法，同时它也是运筹学的一个重要学科3。 在实际生活中， 博弈论经常被用作分析两个及两个以上决策者之间相互作用。 一次完整 - 2 - 的博弈包括

6、三个部分4：局中人，在一场竞赛或博弈中，每一个有决策权的参与者成为一个 局中人；策略，一局博弈中，每个局中人都有选择实际可行的完整的行动方案，此方案不是 某阶段的行动方案， 而是指导整个行动的一个方案， 一个局中人的一个可行的自始至终全局 筹划的一个行动方案， 称为这个局中人的一个策略； 得失， 一局博弈结局时的结果称为得失。 每个局中人在一局博弈结束时的得失， 不仅与该局中人自身所选择的策略有关， 而且与全局 中人所取定的一组策略有关。所以，一局博弈结束时每个局中人的“得失”是全体局中人所取 定的一组策略的函数，通常称为效益函数。 一般认为， 博弈主要可以分为合作博弈和非合作博弈。 它们的区

7、别在于相互发生作用的 当事人之间有没有一个具有约束力的协议，如果有，就是合作博弈，如果没有，就是非合作 博弈。 2.1 非合作型博弈论（非合作型博弈论（Non-cooperative game theory） 在非合作型博弈论中， 每个局中人与其他局中人之间没有共同协议的束缚， 根据自己的 当前状况， 独立采取自己的最优策略而不经过协商， 但是每个局中人的策略又会影响其他局 中人的策略的选择。在非合作型博弈论下得出的结果或者可以称之为均衡点，即纳什均衡 (Nash Equilibrium) 4，其物理含义是所有局中人采用的策略的集合，且是任何局中人都不想 背离的策略集合。 系统达到纳什均衡时，

8、 任何局中人都无法在其他局中人的策略不变的情况 下提高自己的效益，也就是说在纳什均衡状态下，每个局中人所选策略是最优的。纳什均衡 是一种稳定的状态，在这种状态下，任何局中人都没有改变自己策略的要求。 为说明非合作型博弈论的特点，特以著名的囚徒困境为例3。此例中，两个共同犯罪的 囚徒就是两个局中人，他们被安置在两个独立的房间中且需要做出选择，认罪或是否认。每 个囚徒都被提前告知惩罚措施：如果两个人都认罪，那么每个人将会分别被判刑入狱两年； 如果都否认，两个人都将会被判刑入狱一年；如果一个认罪，一个否认，那么认罪的人将会 得到释放，而否认的人将受到严厉的惩罚，被判入狱四年。此问题可总结为图 1 所

9、示。 认罪 否认 认罪 -1,-1 0,-2 否认 -2,0 -2,-2 图 1 囚徒困境 由于两个罪犯是被分别放置于两个独立的房间， 没有办法互相商量对策， 只能从自己的 利益出发， 那么对于两个罪犯来说最有益于自身的策略是认罪， 两个人都认罪的结果就是此 次博弈的唯一的纳什均衡解。 但是显然这并不是此次博弈的最优解， 因为两个人都否认时二 人所获得的利益才最大。 由此可以看出在非合作型博弈论模式下， 纳什均衡解并不一定是最 优解， 即不是帕累托最优解 （Pareto Optimality） 4。 帕累托最优是资源分配的一种理想状态， 是指在没有使任何人境况变坏的前提下， 任何一个人都没有办

10、法取得更大效益的状态。 而帕 累托改进是指一种变化，在没有使任何人境况变坏的前提下，使得至少一个人变得更好。一 方面，帕累托最优是指没有进行帕累托改进的余地的状态；另一方面，帕累托改进是达到帕 累托最优的路径和方法。 非合作博弈强调的是个人理性、个人最优决策，其结果可能是有效率的，也可能是没有 - 3 - 效率的， 个人利益和全局利益存在着明显的冲突矛盾。 普遍认为低效的产出情况是需要避免 的， 因此在用非合作型博弈论解决问题时效益函数的建立以及每个局中人针对不同效益函数 所采用的策略要注意尽可能实现系统性能的帕累托最优化。 2.2 合作型博弈论（合作型博弈论（Cooperative game

11、 theory） 在合作型博弈论中， 每个局中人在博弈开始之前， 从自己的利益出发与其他局中人谈判 或是讨价还价，尽力形成联盟，尝试相互合作并达成共识，如果不能达成共识的话，局中人 就会以非合作型博弈的方式采取措施。 局中人达成的共识是有一定的限制条件的， 而且每个 局中人都不得私自背离。 在形成的联盟中， 每个局中人可选择与所有其他局中人讨价还价以 获得最大效益， 其结果对联盟各方均有利。 通常在局中人合作情况下获得的效益要比局中人 之间相互独立的进行资源分配所获得的效益要大，大多数情况下是帕累托最优的。 合作博弈强调的是团体的理性，强调的是效率、公正、公平，建立效益函数时要把提高 效率和保

12、证公平作为博弈问题的重点。 3. 博弈论在资源分配中的应用博弈论在资源分配中的应用 当前无线网络中的资源分配问题就是如何将有限的授权频谱分配给多个未授权用户， 使 无线网络资源能够得到尽可能大的利用， 改善目前所存在的未授权频谱匮乏和授权频谱利用 率低的现状，实现无线网络的高速和高效传输，满足日益壮大的无线用户的各种需求。无线 网络中未授权用户之间对有限频谱资源的竞争可以看作是一次博弈， 无线网络的资源共享和 分配即可建立博弈模型，每个未授权用户终端可作为一个局中人，相互竞争使用网络资源， 如频谱、能量等。 在无线网络中， 根据是否有中心控制节点， 或者说各个未授权用户终端是否需要交互信 息，

13、以非合作型博弈论和合作型博弈论为基础建立模型。 3.1 非合作型博弈论应用实例非合作型博弈论应用实例 在受到强烈信道间干扰（CCI，Cochannel Interference）和信道时变性较强的无线网络中 实现有限无线资源的高效共享是一个重大挑战。资源分配5，如功率控制和自适应调制等是 抵抗这些有害影响的重要手段， 并且可以在干扰受限的无线网络中提高频谱效率。 由于用户 之间相互并不了解情况，无法进行协作，因此可以建立非合作型博弈模型6 7 8 9，每个用 户独立的自私的分配资源，目的是使自身的效益最大化。 用博弈论来分析无线网络资源分配， 可以从不同角度入手建立模型解决问题。 无线网络 系

14、统可以按照频谱的传输特性，将整个网络分成多个小区，把问题细化，再进一步进行资源 分配。Kwon 等人提出一种应用于多小区系统的分布式资源分配方案10，用这种方法获得的 效益比采用平均分配功率的方法获得的效益要大的多。类似于未来 802.22 网络的感知无线 电系统，可以将整个无线网络系统分成两级：从服务提供商（SP）和终端用户，此处终端 用户特指未授权用户， 未授权用户在不干扰授权用户使用和其他未授权用户的情况下， 共享 授权用户的频带11。在此系统中，某一地理区域的某一频段通过 SP 分配给未授权用户，每 个未授权用户以传输速率为自变量建立效用函数， 系统的最终目的就是在功率的限制下使未 授

15、权用户的效用函数之和获得最大值，同时通过频谱权重来实现各 SP 之间的简单协作。每 一次的资源分配所需的频谱权重由上一次分配结果决定，影响本次分配时各 SP 所能使用的 频段。 - 4 - 无线通信系统中的用户一般通过空气介质进行传输， 而空气对于所有的信号来说都是一 个比较普遍的传输媒质， 因而每个用户的信号都会对其他用户的信号造成干扰， 对于授权用 户 和 未 授 权 用 户 都 是 如 此 。 此 时 通 常 都 会 根 据 未 授 权 用 户 的 信 干 比 （ SIR ， Signal-to-interference Ratio)来衡量系统的性能。另外，由于未授权用户一般都是移动用户

16、， 电池能量一般而言都是有限的， 希望在比较高效的传输信号时消耗的电池尽量少， 因此传输 功率的控制是资源分配的一个重要部分。近年来人们开始用博弈论来解决功率控制问题12 13 14，在建立博弈论模型时采用非合作型博弈论，用 SIR 衡量系统效益并建立效益函数， 每个未授权用户都努力使自己的效益最大化， 达到纳什均衡。 但是由于用户都是根据自己的 情况独立的进行资源分配， 因此从社会的角度来看达到纳什均衡时所获得的系统效益并不一 定是最佳结果，针对这一问题 Shah 和 Saraydar 分别提出在模型中引入一种线性价格政策函 数（Pricing Policy Function）来提高系统效益15 16。使用价格政策的非合作型博弈论模型， 可以通过引入简单的合作来提高系统性能，同时也保持了各未授权用户分配功率的独立性， 并且可以达到纳什均衡。 但是由于价格政策函数是线性的， 并且所有用户都使用同一个价格 因子，此模型依然无法达到社会利益最优即帕累托最优。如果系统想要达到帕累托最优，那 么每个从用