胡玉佩，曾令康
北京邮电大学电子信息工程学院，北京 (100876)
涉水喉E-mail: hypfly73@yahoo
摘要：博弈论（Game Theory）是专门用于研究若干个体之间竞争有限资源的数学理论。博弈论已被成功用于研究无线网络资源分配最优化和提高效率的问题。本文首先简单介绍了博弈论的基本概念；然后按照不同的分类准则，考虑无线网络资源分配的实际情况，描述了两种常用的博弈论类型：非合作型博弈论和合作型博弈论，并对这两种博弈论在无线网络资源分配中的应用列举了若干实例。
关键词：博弈论；非合作型博弈论；合作型博弈论；纳什均衡；帕累托最优
1.引言
在目前的无线网络系统中，为了避免或是减轻不同无线技术之间的干扰，广泛采用固定的频谱分配政 策，即由国家政府机关进行频谱分配，将一部分频谱分别划分给指定的机构进行特定的服务，如无线电视、蜂窝系统、WLAN等，被指定分配的频谱称为授权频谱（licensed band），未被指定分配的频谱称为未授权频谱（unlicensed band），由国家机关授权使用某授权频谱的机构则被称为该授权频谱的授权用户（licensed user），反之则被称为未授权用户（unlicensed user）。大多数情况下，在无线网络中出现的科技创新都是基于未授权频谱的。近年来，随着无线技术的快速发展，新业务层出不穷，使原本就已非常有限的未授权频谱变得越来越拥挤，加剧了频谱资源有限性引起的频谱资源匮乏问题。 但是，频谱的匮乏是相对的，而不是绝对的，这种匮乏是由当前频谱资源管理上存在着的供新业务使用的频谱匮乏和已授权频谱使用效率不高这两个问题共同引起的。从美国联邦通信管理委员会（Federal Communications Commission）提供的测量数据来看，授权频谱远远没有得到充分的利用，其利用率随着时间的变化和地理环境的不同，一般在15%~85%之间[1]。因此FCC考虑用实时动态的方法代替已有的固定分配方法进行频谱分配，以解决上述资源匮乏问题。按照实时动态分配频谱的思想，FCC提出一项新的政策[2]，将认知无线电（Cognitive Radio）技术应用于无线网络系统中。在此类系统中，授权用户划出部分或是全部授权频谱资源，按照一定的准则，使认知用户即未授权用户可以使用该频谱。为了保证授权用户的绝对传输质量，未授权用户的发射功率和工作频谱都要受到严格限制，因此需要未授权用户合理有效地分配资源，提高系统效益。在现有的知识体系中，博弈论
是专门用于研究多个利益共同体之间竞争有限资源的数学工具，并且近年来理论体系不断完善，日趋成熟。实际上，博弈论已经在不同领域得到了广泛的利用，如经济学，政治学，生物学等[3]。同样，博弈论在无线网络中的应用已经引起了越来越多的重视，并且对于无线系统的分析起到巨大的推进作用。为了紧跟技术前沿，本文将对博弈论在资源分配中的应用进行简单的介绍。
2.博弈论
变压器油箱
博弈论(Game Theory)，有时也称为对策论，或者赛局理论，是应用数学的一个分支, 目前在生物学，经济学，国际关系，计算机科学, 政治学，军事战略和其他很多学科都有广泛的应用。博弈论主要研究公式化的激励结构（游戏或者博弈）间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法，同时它也是运筹学的一个重要学科[3]。
在实际生活中，博弈论经常被用作分析两个及两个以上决策者之间相互作用。一次完整
的博弈包括三个部分[4]：局中人，在一场竞赛或博弈中，每一个有决策权的参与者成为一个局中人；策略，一局博弈中，每个局中人都有选择实际可行的完整的行动方案，此方案不是某阶段的行动方案，而是指导整个行动的一个方案，一个局中人的一个可行的自始至终全局筹划的一个行动方案，称
为这个局中人的一个策略；得失，一局博弈结局时的结果称为得失。每个局中人在一局博弈结束时的得失，不仅与该局中人自身所选择的策略有关，而且与全局中人所取定的一组策略有关。所以，一局博弈结束时每个局中人的“得失”是全体局中人所取定的一组策略的函数，通常称为效益函数。
一般认为，博弈主要可以分为合作博弈和非合作博弈。它们的区别在于相互发生作用的当事人之间有没有一个具有约束力的协议，如果有，就是合作博弈，如果没有，就是非合作博弈。
2.1 非合作型博弈论（Non-cooperative game theory）
在非合作型博弈论中，每个局中人与其他局中人之间没有共同协议的束缚，根据自己的当前状况，独立采取自己的最优策略而不经过协商，但是每个局中人的策略又会影响其他局中人的策略的选择。在非合作型博弈论下得出的结果或者可以称之为均衡点，即纳什均衡(Nash Equilibrium) [4]，其物理含义是所有局中人采用的策略的集合，且是任何局中人都不想背离的策略集合。系统达到纳什均衡时，任何局中人都无法在其他局中人的策略不变的情况下提高自己的效益，也就是说在纳什均衡状态下，每个局中人所选策略是最优的。纳什均衡是一种稳定的状态，在这种状态下，任何局中人都没有改变自己策略的要求。
为说明非合作型博弈论的特点，特以著名的囚徒困境为例[3]。此例中，两个共同犯罪的囚徒就是两个局中人，他们被安置在两个独立的房间中且需要做出选择，认罪或是否认。每个囚徒都被提前告知惩
罚措施：如果两个人都认罪，那么每个人将会分别被判刑入狱两年；如果都否认，两个人都将会被判刑入狱一年；如果一个认罪，一个否认，那么认罪的人将会得到释放，而否认的人将受到严厉的惩罚，被判入狱四年。此问题可总结为图1所示。
认罪否认
认罪 -1,-1 0,-2
否认 -2,0 -2,-2
图1 囚徒困境
由于两个罪犯是被分别放置于两个独立的房间，没有办法互相商量对策，只能从自己的利益出发，那么对于两个罪犯来说最有益于自身的策略是认罪，两个人都认罪的结果就是此次博弈的唯一的纳什均衡解。但是显然这并不是此次博弈的最优解，因为两个人都否认时二人所获得的利益才最大。由此可以看出在非合作型博弈论模式下，纳什均衡解并不一定是最优解，即不是帕累托最优解（Pareto Optimality）[4]。帕累托最优是资源分配的一种理想状态，是指在没有使任何人境况变坏的前提下，任何一个人都没有办法取得更大效益的状态。而帕累托改进是指一种变化，在没有使任何人境况变坏的前提下，使得至少一个人变得更好。一方面，帕累托最优是指没有进行帕累托改进的余地的状态；另一方面，帕累托改进是达到帕累托最优的路径和方法。
非合作博弈强调的是个人理性、个人最优决策，其结果可能是有效率的，也可能是没有
效率的，个人利益和全局利益存在着明显的冲突矛盾。普遍认为低效的产出情况是需要避免的，因此在用非合作型博弈论解决问题时效益函数的建立以及每个局中人针对不同效益函数所采用的策略要注意尽可能实现系统性能的帕累托最优化。
2.2 合作型博弈论（Cooperative game theory）
在合作型博弈论中，每个局中人在博弈开始之前，从自己的利益出发与其他局中人谈判或是讨价还价，尽力形成联盟，尝试相互合作并达成共识，如果不能达成共识的话，局中人就会以非合作型博弈的方式采取措施。局中人达成的共识是有一定的限制条件的，而且每个局中人都不得私自背离。在形成的联盟中，每个局中人可选择与所有其他局中人讨价还价以获得最大效益，其结果对联盟各方均有利。通常在局中人合作情况下获得的效益要比局中人之间相互独立的进行资源分配所获得的效益要大，大多数情况下是帕累托最优的。
万次火柴
合作博弈强调的是团体的理性，强调的是效率、公正、公平，建立效益函数时要把提高效率和保证公平作为博弈问题的重点。
3.博弈论在资源分配中的应用
当前无线网络中的资源分配问题就是如何将有限的授权频谱分配给多个未授权用户，使无线网络资源能够得到尽可能大的利用，改善目前所存在的未授权频谱匮乏和授权频谱利用率低的现状，实现无线网络的高速和高效传输，满足日益壮大的无线用户的各种需求。无线网络中未授权用户之间对有限频谱资源的竞争可以看作是一次博弈，无线网络的资源共享和分配即可建立博弈模型，每个未授权用户终端可作为一个局中人，相互竞争使用网络资源，如频谱、能量等。
在无线网络中，根据是否有中心控制节点，或者说各个未授权用户终端是否需要交互信息，以非合作型博弈论和合作型博弈论为基础建立模型。
3.1 非合作型博弈论应用实例
在受到强烈信道间干扰（CCI，Cochannel Interference）和信道时变性较强的无线网络中实现有限无线资源的高效共享是一个重大挑战。资源分配[5]，如功率控制和自适应调制等是抵抗这些有害影响的重要手段，并且可以在干扰受限的无线网络中提高频谱效率。由于用户之间相互并不了解情况，无法进行协作，因此可以建立非合作型博弈模型[6] [7] [8] [9]，每个用户独立的自私的分配资源，目的是使自身的效益最大化。
用博弈论来分析无线网络资源分配，可以从不同角度入手建立模型解决问题。无线网络系统可以按照频谱的传输特性，将整个网络分成多个小区，把问题细化，再进一步进行资源分配。Kwon等人提出一种应用于多小区系统的分布式资源分配方案[10]，用这种方法获得的效益比采用平均分配功率的方法获得的效益要大的多。类似于未来802.22网络的感知无线电系统，可以将整个无线网络系统分成两级：从服务提供商（SP）和终端用户，此处终端用户特指未授权用户，未授权用户在不干扰授权用户使用和其他未授权用户的情况下，共享授权用户的频带[11]。在此系统中，某一地理区域的某一频段通过SP分配给未授权用户，每个未授权用户以传输速率为自变量建立效用函数，系统的最终目的就是在功率的限制下使未授权用户的效用函数之和获得最大值，同时通过频谱权重来实现各SP之间的简单协作。每一次的资源分配所需的频谱权重由上一次分配结果决定，影响本次分配时各SP所能使用的频段。
无线通信系统中的用户一般通过空气介质进行传输，而空气对于所有的信号来说都是一个比较普遍的传输媒质，因而每个用户的信号都会对其他用户的信号造成干扰，对于授权用户和未授权用户都是如此。此时通常都会根据未授权用户的信干比（SIR，Signal-to-interference Ratio)来衡量系统的性能。另外，由于未授权用户一般都是移动用户，电池能量一般而言都是有限的，希望在比较高效的传输信号时消耗的电池尽量少，因此传输功率的控制是资源分配的一个重要部分。近年来人们开始用博弈论
来解决功率控制问题[12] [13] [14]，在建立博弈论模型时采用非合作型博弈论，用SIR衡量系统效益并建立效益函数，每个未授权用户都努力使自己的效益最大化，达到纳什均衡。但是由于用户都是根据自己的情况独立的进行资源分配，因此从社会的角度来看达到纳什均衡时所获得的系统效益并不一定是最佳结果，针对这一问题Shah和Saraydar分别提出在模型中引入一种线性价格政策函数（Pricing Policy Function）来提高系统效益[15] [16]。使用价格政策的非合作型博弈论模型，可以通过引入简单的合作来提高系统性能，同时也保持了各未授权用户分配功率的独立性，并且可以达到纳什均衡。但是由于价格政策函数是线性的，并且所有用户都使用同一个价格因子，此模型依然无法达到社会利益最优即帕累托最优。如果系统想要达到帕累托最优，那么每个从用户采用的价格政策函数要比线性函数复杂的多，而且每个从用户所采用的价格政策函数也不完全相同，这在实际操作中的难度很大，几乎是无法完成的。
无线网络资源分配方案按照其关注角度不同，可以分为以用户为中心的方案和以网络系统为中心的方案。以用户为中心的方案目的是使用户个体利益最大化，而以系统为中心的方案的目的是尽量使系统效益最优。上面提到的功率控制算法就是典型的以用户为中心的方案。而最大化网络信息容量[17] [18]或是最大化系统吞吐量[19]可看作是以系统为中心的方案。这两种方案一个显著的区别是以用户为中心的方案的QoS分布较以系统为中心的方案的分布平坦的多。以系统为中心的方案倾向于将大多数的甚至是全部的系统资源分配给少数信道质量较好的用户，而以用户为中心的方案则没有类似的情况
反光道钉发生。在上面提到的文献中，采用的方法是将用户的功率控制和系统的吞吐量一起建立一个效益函数，但是这样做会出现由于函数的非线性得到的纳什均衡解是局部最优而不是全局最优的不理想情况，如同上文功率控制算法中出现的问题。为避免这种情况，可以将功率控制和自适应速率分配问题结合考虑，在固定的BER（Bit-error Rate）的限制下建立双线性不等式[20]，即当功率固定时吞吐量受到线性限制，而当吞吐量固定时功率受到线性限制。Feng等人首先提出了当系统中只使用一个效益函数并且没有使用自适应调制时，采用同时考虑用户标准和系统标准的一种双重标准的最优化方法的思想[21]。Han等人将以用户为中心的方案和以网络系统为中心的方案结合在一起设计博弈模型[22]，从而实现将功率控制和自适应调制相结合。此种方法得到的系统效益非常接近最优结果，但是，由于建立的两个函数之间相互联系相互影响，因此实际操作时耗费时间很多，实施起来也比较困难。
在采用上述方法的系统中，未授权用户使用的是空白频谱，为了保证授权用户的正常数据传输，需要未授权用户检测频谱是否空闲，因此要求未授权用户对其所处的无线电环境变化具有非常高的敏感度，并且可以灵活切换状态。这对于器件的要求较高，同时在经常变化的环境中，会影响频谱的使用效率，器件的耗损率也比较大。因此FCC提出了干扰温度模型[23]，此模型为授权用户接收方接收到的干扰值提供了度量标准。Huang等人提出了一种包含一个或是多个测量站点的系统模型[24]，在此类模型中要求每个测量站点接收到的总干扰值不超过给定的门限。Jia等人在此模型下，提出了一种资源分配方法[25]，为了保证干扰不超过门限值，测量站点会根据接收的干扰值决定是否需要剔除未授权用户，以及剔除哪个或
是哪几个未授权用户，从而降低对相应频段的干扰值。但是对于如何选择测量站点的位置，及存在若干个测量站点时，各站点如何协作并没有说明。并且，此文中要求测量站点掌握所有未授权用户的精确信道状况，而在实际情况中，这是很难做到的，因此还需要改进。
由此可见，非合作型博弈论应用于无线网络资源分配时最主要的问题是个体利益最优与系统利益最优之间存在的矛盾。采用非合作型博弈论模型的系统中，当系统达到稳定状态，即纳什均衡时，用户个体的利益是最优的，但是系统的利益却不能保证是最优的，有时可能还与系统最优状态相差很远。虽然已经提出了一些方案来解决这一问题，如价格函数的引入和不同算法的结合等，但是这些方法在实际操作中还存在着难度。因此还需要研究既能提高系统效益使其接近社会效益最优，还要有较高的可操作性的算法。
3.2 合作型博弈论应用实例
如同经济学中各商户之间进行协商合作一样，在无线网络系统中，分散分布的未授权用户之间也可以相互协商合作，共同商议无线网络资源的使用，以使每个用户的效益达到最优，用合作型博弈论模型实现资源共享。u盘外壳
在目前的研究当中，人们较多关注的是如何在某些限制下实现高效地最大化未授权用户的总传输速率或是最小化未授权用户的总传输功率。但是这些算法往往对于距离较近的或是有较高功率容量的用户较为有利，而公平性问题则被忽略了。Rhee等人提出的最大最小（max-min）算法[26]，虽然保证了用户之间的公平性，但是此算法无法兼顾到用户对数据传输的不同的需求。此外，最大最小算法假定系统处于最差情况下，对信道条件较好的未授权用户会施以惩罚，从而抑制了这些未授权用户的数据传输，系统的性能会有所降低。同时此算法的复杂度较高，实际操作起来难度也较大。针对以上缺点，考虑到系统中未授权用户之间的公平性，系统的效率以及实施的复杂度，Han等人提出一种基于纳什讨价还价解（Nash Bargaining Solution, NBS）的算法[27]。这种算法在保证NBS公平性的基础上使系统性能达到最优，从而实现了在保证未授权用户之间资源公平分配的同时完成系统的总传输速率的最大化。
在NBS 的基础上，Feng等人考虑了未授权用户的感知性能，引入了权重的概念，提出了非对称型纳什讨价还价解（Asymmetric-Nash-Bargain-Solution, ANBS）算法[28]。采用ANBS 方法时，若权重较高的未授权用户占用了好的信道，两个未授权用户的总传输效率非常接近最佳输出，公平性优于NBS，因此可以极大的改善NBS算法；但若是权重较低的未授权用户占用了好的信道，两个未授权用户的总传输效率比起NBS算法显著下降，公平性也次于NBS算法。上述NBS算法和ANBS算法都是基于两个未授权用户的，可以用匈牙利方法[29]推广到多个用户的情况，但是随着载波数量的增加复杂度也有所提高。
无线网络系统中的信道具有一定的时变性，Jalali等人利用信道的这一特点来进行资源分配[30]。采用这种算法的系统中，需要控制中心实时监测用户每个特定时间间隔内的信息，根据用户当前的信道状况和传输速率决定用户是否可以使用信道进行传输。在此算法中，用以应对用户信道变化情况的参数需要慎重选择，如果取值太小，而用户的信道变化又比较频繁的话，用户就要不停的在传输与不传输之间来回切换，对器件的损耗较大，也不能完成数据的正常传输；反之，如果取值过大，那么就会造成系统对信道变化不够敏感，对用户的正常数据传输也会造成影响。
无线网络的用户一般都是移动用户，某一授权用户出现或是离开某一频段，或是未授权用户的出现或是离开发生的频率都相当高，因此无线系统的环境是经常变化的。这样，未授
权用户的资源分配策略就要作出相应的改变，在满足主用户传输的透明性的同时实现未授权用户资源分配的最优化。
Cao等人提出了一种应用于移动接入网的自适应分布式频谱分配算法[31]。在此算法中，首先假定在某一特定区域中的授权用户和未授权用户的拓扑分布是固定不变的，在此基础上完成未授权用户的资源的最优或是次最优分配。采用这个方法可以降低算法的计算量和复杂度。接着，根据系统中发生的移动事件，从用户自动组成讨价还价小组，共同协商频谱分配。算法对发起讨价还价的未授权用户，以
及讨价还价小组的组员身份和数量都有严格的要求，以实现在较低复杂度的情况下比较高效的完成资源分配。同时，在讨价还价过程中每个用户都必须承诺通力合作实现系统性能最优，即使这样作会降低某些用户自身的性能。为了保证公平性，获得频段较多的用户要分出一部分频段给获得频段较少的用户。但是此算法在实际操作中还是有一定的难度，因为它要求未授权用户是完全无私的，而这在现实生活中是很难实现的。
在无线网络资源分配中使用合作型博弈论，需要各未授权用户之间进行协商和合作，因此使用合作型博弈论可以使系统资源分配达到或是近似达到系统最优，同时还可以保证公平和公正，这是合作型博弈论较之非合作型博弈论的优势所在。但是，由于合作型博弈需要局中人之间的持续的交流互动，实际操作中对无线网络控制中心的设置和用户的要求比较告，并且由用户之间交流信息引起的延迟也比较明显，因此目前在理论研究中和实际使用中受到的关注不如非合作型博弈论，如何加强合作型博弈论的实际操作性还有待开发。
4.总结和展望
随着无线技术的不断创新，新型的无线产品层出不穷，对于无线传输的速度和质量有了更高的要求。目前无线网络资源越来越紧缺，无线频谱越来越拥挤。如何将有限的频谱更加高效地利用起来，是当前无线网络面临的一个重大问题。博弈论由于其独特的数学特性，在无线网络资源分配的研究中已逐
渐受到人们的普遍关注。本文对近几年来将博弈论应用于无线网络资源分配的研究成果进行了大致的介绍。无线网络资源分配中博弈论的使用，虽具有独特的优点，但还远不成熟，还存在一些问题需要进一步研究。我们今后的工作将重点关注以下几个方面：
y在用博弈论进行资源分配的同时，考虑频谱感知性能对于策略选择的影响。
y考虑非合作型博弈论和合作型博弈论在某种程度上的合作，共同完成资源分配。
y打破目前所提出的系统中关于接收方和发送方位置、距离等的限制，使算法更加具有普遍性，更加易于实施。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议