基于博弈论的无线电频谱分配

#图3-1认知系统网络拓扑图示例

基于图论的模型中规定了空闲矩阵，效益矩阵，干扰矩阵和分配矩阵四个基本矩阵。空闲频谱矩阵L=^lIle{0,l}},N为用户数(下标从0到N-1),M为总频n,mn,mnxM带数(下标从0到M-l),l=1表示频带m对于用户n是可用的，l=0表示不可用。n,mn,m效益矩阵B={b},b表征用户n使用频带m所带来的效益权重，如频谱利n,mNxMn,m用率等。将矩阵L与矩阵B相结合，可得出有效频谱的效益L={•b}。Bn,mn,mNxM干扰矩阵集合C={cIc€{0,l}},c=1表示用户n和用户k在同n,k,mn,k,mNxNxMn,k,m时使用频带m时会产生干扰，当n=k时，c=1-1，仅由空闲频谱矩阵L决定。n,k,mn,m无干扰的频谱分配矩阵A={aIae{0,1}},a=1表示频带m被分配给n,mn,mNxMn,m用户n。A必须满足无干扰条件：a•a=0fc=l,Vn,k<N,m<M(3-1)n,mk,mn,k,m把上述频谱分配抽象为一个图G(U,E,L)的着色。U是图G的顶点集，表示共享频cB谱的用户，L表示顶点可选颜色集合和权重，E是表集，由于扰约束集合C决定，当且仅Bc当c=1时，两个不同的顶点(用户)u,veU之间有一条颜色为m(频带m)的边。于n,k,m满足式(3-1)条件的有效频谱分配对应的着色条件可以描述为：当两个不同顶点间存在m色边的时候这两个顶点不能同时着m色。这样，我们便可以根据图论着色理论原则对认知无线电用户进行频谱分配。基于定价拍卖的频谱分配模型利用微观经济学中定价拍卖原理而制定的无线电资源分配机制在近年来得到广泛的研究,而且已经被证明是认知无线电网络的频谱分配问题的有效解决方法。在这种基于定价拍卖的频谱分配模型根据不同的网络效用需要来确定自身的目标函数，即确定赢家胜出的规则。例如采用最大化系统吞吐量原则将某段频谱分配给在其上吞吐量投标值最大的用户，利用效用公平原则和时间公平原则保证投标者在竞争频谱资源过程中的效用公平和时间公平等等。由于在频谱分配过程中引入了定价拍卖原理，认知无线电用户即投标者原则上都是“自私的”、“理性的”，这使得基于定价拍卖的频谱分配模型具有如下一些特点：（1）非合作的用户行为。由于投标者是“自私的”、“理性的”，每个投标者都会根据系统效用需要对可用频谱进行定价，将评估的价格传送给拍卖人，而无需知道其他用户的信息和策略。（2）分配算法需要合理的执行时间和合理的计算开销。基于定价拍卖的频谱分配算法中大量的运算集中在投标者和拍卖人身上，例如投标者需要对每个可用频谱单元进行评估，拍卖人需要收集全部投标者定价并进行赢家判断等。（3）信令开销小。虽然对频谱单元的定价为投标者增加了较大的运算负担，但由于用户之间非合作的关系以及投标者和拍卖人之间信息传递的完备性，使得基于定价拍卖的频谱分配算法拥有较小的信令开销的优点。从以上的加上中我们可以看出，基于图论的频谱分配模型和基于定价拍卖的频谱分配模型充分利用了经典数学和微观经济学理论，为认知无线电中频谱分配提出了解决问题的框架，基于此两类模型的具体算法也得到了广泛的研究。然而，为了推动认知无线电频谱分配技术的不断发展，提出新的频谱分配问题模型成为了普遍的迫切需要。然而基于图论模型的拼配分配完成时间与空闲信道数的多少以及网络的动态变化，基于定价拍卖的模型适合于主、次用户间为租用关系的认知无线电系统，应用范围也具有局限性。为了推动认知无线电频谱分配技术的进一步发展，提出新的频谱分配问题模型已成为普遍需要，于是诞生了基于博弈论的研究方法。基于博弈论反应实时认知用户交互过程的认知周期映射为一个博弈模型，对分布式动态频谱分配算法进行分析。她使用严谨的数学模型解决认知网络中不透光用户间的厉害冲突，在决策选择问题上能够起到关键知道作用。1.一种认知无线电系统中一种基于图论的频谱分配方法，其特征在于该方法包括以下步骤：a.根据信道空闲矩阵L={ln,m|ln,me{0,1}}N*M和干扰矩阵C={ci,j|ci,jg{0,1}}N*N，计算节点可用的频段数目frenum（频段度目）和节点的邻居节点的数目linknum（连接度数），其中N为网络中总的认知用户数目，M为系统中总的信道数目，ln,m=l表示信道m对于认知用户n可用，ln,m=0表示信道m对于认知用户n不可用，ci,j=1表示认知用户i和认知用户j同时使用同一信道会产生干扰，而ci,j=0表示认知用户i和认知用户j同时使用同一信道不会产生干扰；b.计算各节点的优先级其中ConnetFailRate表示区域呼损率，选择具有最大优先级的节点进行分配，若节点具有相同的优先级，选择频段度数较小的节点进行分配，若频段数仍然相同，则随机选择；c.确定分配节点后，在它的频段列表中，找出与其邻居具有最小干扰的频段进行分配；d.分配此频段后，将与其具有此相同频段的邻居节点中删除此频段，更新拓扑图；e.重新更新其他节点的信道空闲矩阵L和干扰矩阵C,返回第一步重新计算优先级，直到所有节点均分配完毕，此时第一轮分配结束；f.当第一轮分配结束后，在每个节点中去除已经分配给自己的信道以及邻居节点已经使用的干扰信道，连接干扰关系仍然保持不变；g.按照相同法则继续进行第二轮、第三轮的分配，直到在每个节点中去除已经分配给自己的信道以及邻居节点已经使用掉的干扰信道后，所有节点都不存在可用信道为止。本发明的目的是提供一种认知无线电系统中一种基于图论的频谱分配方法，该方法在计算分配优先级时，将信道可用度和信道连接度综合考虑，同时引入了区域呼损率参数，降低了呼损率，提高了频谱利用率。具体步骤如下：首先计算各节点的频段度数和连接度数，然后根据频段度数、信道连接度和区域呼损率参数计算出各节点的优先级，选择具有最大优先级的节点进行分配；若节点具有相同的优先级，选择频段度数较小的节点进行分配；确定分配节点后，在它的频段列表中，找出与其邻居节点具有最小干扰的频段进行分配；分配此频段后，将与其具有此相同频段的邻居节点中删除此频段，更新拓扑图；返回第一步重新计算优先级，直到所有节点均分配完毕。博弈论基本概念博弈论，英文名gametheory，是研究决策主体的行为发生直接相互作用时候的决策以及这种决策的均衡问题的理论。也就是说，博弈论研究当一个主体，譬如说一个人或一个企业的选择受到其他人（其他企业）的选择的影响，而且反过来影响到其他人（其他企业）选择时的决策问题和均衡问题。所以在这个意义上说，博弈论又称为“对策论”。博弈论的定义：在一个n人博弈的标准式表述中，参与者的战略空房为s...s,收益函1n数为u...u，我们用G=｛错误！未找到弓|用源。s...s；u...u错误！未找到引用源。｝表示1n1n1n此博弈。博弈的标准时包括：（1）博弈的参与者；（2）每一参与者可供选择的战略集s；（3）真对所有参与者可能选择的战略组合，每一参与者获得的收益u.博弈论与常规的优化决策理论的不同之处在于：博弈论中参与者在利益上有冲突；参与者要各自做出优化决策，并企图使个人的利益最大化；每个人的决策和他人之间有相互作用，即他人的决策会影响某个人，而某个人的决策也会影响他人；在博弈论中一般假定参与决策的个体均为“理智的”，从而进行理性的逻辑思维。博弈论是一种使用严谨数学模型来解决现实中利害冲突的理论，由于冲突、合作、竞争等行为是现实中常见的现象，因此很多领域都能应用博弈论，如军事领域、经济领域、政治外交等。纳什均衡就是博弈中每个博弈方各策略构成的策略组合，其中每个博弈方的策略都是针对所有其他博弈方的策略构成来制定的策略组合的最佳反应。“最佳反应”指的是该策略带给采用它的博弈方的利益或期望利益，大于或至少不小于其它任何策略能带来的利益。博弈论的产生及发展18世纪以前，博弈问题的研究便在学术界展开了，而现在博弈理论中的一些经典博弈模型，如关于产量决策的Cournot模型和关于价格决策的Bertrand模型(分别于1838年，1883年提出)，但博弈论的真正发展则是在20世纪。20世纪初期是博弈论的萌芽阶段。其研究对象主要是从竞赛与游戏中引申出来的严格竞争博弈，即二人零和博弈。在此阶段提出了博弈扩展性策略、混合策略等重要概念。这一阶段最重要的成果就是诺伊曼的最小最大定理(1928)，他为二人零和博弈提供了解法，同时对博弈论的发展产生了重大影响。30年代前后是博弈论学科的建立时期。冯•诺伊曼和摩根斯坦恩于1944年出版的《博弈论与经济行为》汇集了博弈论的研究成果，将其框架首次完整而清晰地表达出来，使之成为一门科学。该书还详尽地讨论了二人零和博弈，并对合作博弈作了探讨，开辟了一些新的研究领域，并在经济学上广泛应用。50年代是博弈论的成长期。纳什为非合作博弈的一般理论奠定了基础，他提出了博弈论中最重要的概念——纳什均衡，开辟了博弈研究的一个全新领域。他规定了非合作博弈的形式，定义了著名的“纳什均衡点”。此后四十余年里，大量学者致力于研究博弈的结构，发展“纳什均衡点”理论，探讨其实际应用的可能性。与此同时，合作博弈理论在这个阶段也得到发展。由于二战硝烟散去不久，以及美苏的对立，博弈论的重要应用领域是军事问题及冷战策略。此后，经济学成为博弈论最重要的应用领域。60年代是博弈论的成熟期。不完全信息的扩充使博弈理论变得更具广泛应用性，基本概念也得到了系统阐述与澄清，博弈论成了完整而系统的体系，并在经济理论的“逻辑范畴”与相应的“博弈重要解”之间找到了对应关系。特别是博弈论与数理经济理论间建立了内在的牢固的关系。海萨尼与塞尔腾正是在这一时期开始他们的工作，海萨尼提出了不完全信息理论，开始均衡选择问题的研究。70年代至今是博弈论的进一步丰富和发展时期。博弈论本身在若干领域获得重大突破，博弈论开始对其他学科的研究产生强有力的影响。计算机技术的飞速发展使得研究复杂与涉及大规模计算的博弈模型发展起来。经济模型有了更深入的研究，特别是非合作博弈理论被应用到若干特殊的经济模型中，使一些复杂的经济问题得到博弈解。博弈论还应用到生物学、计算机科学、哲学等领域。博弈论逐渐成为人们分析、认识、解决许多领域的决策问题的工具。正是由于博弈论特有的思想方法、精确程度和诱人的应用前景，吸引了许多经济学家、数学家投身于这一研究领域。有人认为，如果说20世纪50年代是“一般均衡理论”的时代，60年代是“增长理论”的时代，70年代是“信息经济学”的时代的话，那么80年代则是“博弈论”引起经济理论“革命的时代”，由此反映出人们对博弈论在现代经济学中的重要地位和作用的积极评价。博弈论的分类现实中各种博弈可以按照不同的办法进行分类。根据参与人的多少，可以将博弈分为两人博弈和多人博弈；根据参与人是否合作，可以将博弈分为合作博弈和非合作博弈；根据博弈结果的不同，又可以将博弈分为零和博弈、常和博弈和变和博弈。合作方式：合作博弈非合作博弈博弈结果：零和博弈常和博弈变和博弈参与人：两人博弈多人博弈在非合作博弈中，现在最流行也最有用的分类方法是从博弈参与人的行动次序和在博弈中所获信息的差异角度来分，具体为：从行动的先后次序来分，博弈可以分为静态博弈和动态博弈。从参与人和其他参与人的各种特征信息的获得差异来分，博弈可以分为完全信息博弈和不完全信息博弈。约束力的协议，如果有，就是合作博弈，如果没有就是非合作博弈。(2)静态博弈和动态博弈：从行为的时间序列性，博弈论可以分为静态博弈和动态博弈。静态博弈指的是在博弈中。参与人同时选择行动或非同时选择但是后者并不知道先行动者采取了什么具体的行动；动态博弈是指在博弈中，参与人的行动有先后顺序，并且后行动者能够观察到先行动者所选择的行动。完全信息博弈和不完全信息博弈：按照参与人对其他参与人的了解程度可将博弈论分为完全信息博弈和不完全信息博弈。完全信息博弈是指在博弈的过程中，每一位参与人对其他参与人的特征、策略空间及收益函数有准确的信息。如果参与人对其他参与人的特征、策略空间及收益函数没有准确的信息，在这种情况下进行的就是不完全信息博弈。利用博弈论分析认知无线电前文中我们介绍了博弈论的理论基础，它是帮助分析决策选择问题的有效工具。认知无线电，作为能够检测可用频谱空间，改变自身通信参数以适应无线电环境进行通信的新一代无线电，在其很多关键技术当中都涉及到策略的选择问题。因此，利用博弈论对认知无线电进行分析必然是可行的有效方法。认知无线电中有关策略选择的关键问题，例如频谱分配问题、功率控制问题、呼叫允许问题等，研究的核心都是相关自适应算法的设计和分析。我们可以利用博弈论对这些自适应算法进行分析，在分析的过程中，主要需要确定四个方面的问题：(1)算法具有稳定状态吗？(2)这些稳定状态是什么？这些稳定状态是我们所需要的吗？算法收敛到稳定状态还需要什么约束条件？由此，我们制定了认知无线电的博弈论分析方案，如图3-1所示，图中可以看出，对认知无线电中相关算法进行博弈论分析，主要按分析方案完成4个主要步骤即可。

I1I-flJIJ磚井论找出达态？”川已理论Uliij；i£!|i分析”犬除彳;需蚩的均衡点I1I-flJIJ磚井论找出达态？”川已理论Uliij；i£!|i分析”犬除彳;需蚩的均衡点虫否能判疋第i詹，法的稳定状鑫\是否所需？上r：mf.「只能用廨弈论进行511件分析r卅论分祈站束1、徙川內井论时廉\去进柠分折认知无线电博弈论分析方案绝大多数博弈论的应用研究都致力于前三个问题的解决，而对第四个问题关心较少。其实，在利用博弈论研究认知无线电中的自适应算法时，所有的四个问题都相当重要。下面我们将针对以上四个方面的问题，对如何利用博弈论分析认知无线电进行阐述。论证一个算法具有稳定状态在大多数博弈论模型里，分布式算法的稳定状态都是纳什均衡。一个行动向量a被称为纳什均衡，则必须满足以下式子：u(a)>u(b,a)VigN,bgAiii-iii也就是说，在参与者集合里，如果没有一个参与者能够靠自身行动的改变来提高自身收益时，整个参与者集合对应的行动向量就称为纳什均衡。在不使用较复杂的博弈论模型时，我们可以利用相关的不动点定理判断纳什均衡的存在，但是这样的不动点定理对经验较浅的分析者而言也比较困难。最普通的能定性判断纳什均衡存在的办法是看博弈过程是否满足以下条件：(1)参与者集合是有限的。(2)行动集合是封闭的，有界的凸集。(3)效用函数是在行动空间上的连续的、拟凹函数。所谓拟凹函数，就是相对坐标横轴，图像里没有下凸现象的曲线。亦即对任意两点X、y属于定义域，f(ax+(l-a)y)三min[f(x),f(y)]。实际上，绝大多数的算法都满足这些条件,所以论证纳什均衡的存在并没有太多的实际意义，很多认知无线电中的算法都默认假设存在一个稳定状态，甚至有些单个的博弈过程中存在多个纳什均衡点。但是，也并不是所有的博弈过程和所有的算法都满足以上条件，所以证明一个算法稳定状态的存在还是具有一定价值的。如果无线电被允许混合他们的策略，也就是说允许无线电设备在行动a和b中随机的改变，那么条件(3)就不需要了，并且条件(2)中行动集必须为凸集的要求也不存在，只需要满足有限的行动空间要求就可以，这就是所谓的纳什不动点定理。判定这些稳定状态不管从自身还是相关的角度来说，验证一个博弈过程具有稳定状态并没有太多的实际作用，因为它并没有对期望研究的算法的具体表现进行判定。这就是为什么我们需要对稳定状态进行判定。但是，在没有引用更高级的博弈模型例如潜在博弈模型的前提下，一般的博弈论模型没有办法提供相关的工具来定量的判定纳什均衡。实际上，要判别一个行为向量a是一个纳什均衡，分析者不得不应用式(3-1)并检验所有可能的参与者单方面的策略更改都不能提高此参与者的收益。接下来就是判定出一个博弈过程中所有的稳定状态，这个过程要遍历一个博弈过程中所有可能的行动向量，反复不断的操作。实际上要试图判定出一个博弈过程中所有的纳什均衡点，分析者不得不进行仿真实验。例如，要显示一个在通用分组无线业务(GeneralPacketRadioService,GPRS)网络中建模的联合比特－功率自适应算法拥有4个纳什均衡点，虽然建模系统只假设了7个参与者，但相关的具体仿真工作就要花掉很多天。决定稳定状态是否是所需的有很多种不同的方法可以判断一个行为向量是否是一个“好”的稳定状态，不过其中最典型的方法是证明一个行为向量是帕累托(Pareto)最优，正如中所做的。对于一个向量a*，找不到其他行为向量a^A,使得《(a)-《(a*)ViG“成立，则称此向量a为Pareto最优。证明一个稳定状态是Pareto最优似乎是个好方法，实际上，Pareto最优是个很弱的概念，只告诉了分析者一点点关于稳定状态是否所需的信息。这一点将通过两个简短的分析来说明，一个是有关最大化信干噪比(SignaltoInterferenceplusNoiseRatio,SINR)分布式功率控制的例子，另一个是有关呼叫允许的问题。最大化SINR功率控制考虑一个具有中心接收机的单一簇DS-SS网络，除了中心接收机外，网络中的所有节点调整它们的发射功率，使得信号与加性干扰噪声比达到最大。这里我们的参与者集合是簇中除了中心接收机外的节点；行动集合是所有可能的功率等级(假设可选的功率等级有限)；而所有参与者的效用函数由式(3-2)给出，其中Pi是节点i的传输功率，K是传播系数的统计估计，Hi是从节点到接收机的增益(假设小于1),a是接收机处的噪声。u(p)>hp..[(1k)Yhp]iii：kkkeN我们直觉可以预见，这个博弈过程的唯一的纳什均衡就是所有节点都以最大功率传输时的功率向量。很显然，这并不是我们需要的。第一，由于远近问题，系统容量将会大大减少，除非所有的节点都在接收机的相同覆盖范围内；第二，这样将导致SINR不平等分布，最近的节点比最远的节点会有更大的SINR；第三，电池寿命会大大减少。然而，这样的输出结果却是Pareto最优，因为任何更公平的功率分配将会减少最近的节点效用，而任何更不公平的功率分配会减少弱势节点的效用。这个场景中，Pareto最优实际上会误导分析者对输出的可用性的分析。呼叫允许现在假设一组节点正在从一个网络里申请数据带宽，而网络根据先申请先分配的原则分配带宽。这里我们的参与者集合是申请带宽的节点；行动集合是每个节点可申请的带宽数量；我们假设效用函数是关于接收到数据带宽的单调函数(带宽越大越好)。在这个博弈过程中，我们加入一点其它的假设，即不是所有的带宽请求都同时到达。在稳定状态里，每一个早来的节点会申请到它能处理的尽可能多的带宽，假设这些带宽被合理地覆盖利用，则网络中迟来的节点将被阻挡。一般来说，阻挡大量节点并不认为是好的结果。然而，这样的结果却是Pareto最优，因为任何其它的带宽分配方案都会减少早先到来的节点的效用。更进一步说，传统的为呼叫阻塞保留少量带宽的呼叫允许方案不是Pareto最优，因为效用函数由接收到的数据带宽为条件进行表示，所以把这些保留带宽直接分给用户会增加某些参与者的效用而不会减少其它任何参与者的效用。一个更好的论证一个稳定状态是否满足需要的方法是根据某个网络目标函数来评估一个确定的稳定状态的表现，SINR场景可以利用一个目标函数得到改善，该目标函数测量系统容量或者总的系统吞吐量，也可对电池寿命进行测量。呼叫允许场景如果不考虑Pareto最优，也可以以ErlangB或者ErlangC水平为条件对稳定状态进行更好的评估。Pareto最优是个很弱的概念，因为它并没有太多涉及到一个稳定状态是否是所需的，而且也没有考虑网络设计者的目标是否被最大化。所以评估一个确定的稳定状态更好的方法是使用一个能反映算法设计者需求的网络目标函数。确定收敛条件有一件事情与判定稳定状态以及确定稳定状态是否满足需要一样重要，就是确定在何种条件下算法能够实际达到稳定状态。接下来我们研究一下如表3-1所示模拟了两个认知无线电的交互作用的博弈过程。表3-1具有弱FIP性质的博弈过程表ABCa1,-1-1,1bJI1,-1c三0Ml这个博弈表格模拟了由两个认知无线电用户组成的一个网络，其中一个用户有策略a,b,c可选，而另一个可以选择策略A,B,C。每个用户选择的组合构成了不同的外部实现,例如(a,C)或者(b,A)，每个用户可以对这种实现进行观察和评估。表格数据单元中前半部分表示第一个用户对这个输出的评价赋值，后半部分则是第二个用户的评价赋值。可以注意到这个博弈过程具有唯一一个纳什均衡点(c,C),而且也是Pareto最优，并且若网络规划者按所有用户的效用和构建系统目标函数，这个纳什均衡点(c,C)也是最满足要求的。但是，如果认知无线电用户都分别以最小化步长的方式来改变策略以提高自身效用，这样整个过程就会进入一个循环，即(a,A),(a,B),(b,B),(b,A)。相反，在表中任何点上，如果允许认知无线电用户采用最大步长方式，这样就可以收敛到唯一的纳什均衡点。这种特殊的博弈过程具有弱有限改进路径(FiniteImprovementPath,FIP)特性，是超模博弈模型的属性之一。认知无线电用户在某点上必须采取最大步长方式，如果这一必要条件不被执行，那么整个网络就不会收敛，而所了解的稳定状态信息也就没有意义了。不幸的是，通常形式的博弈模型并没有对收敛条件的规定，所以对收敛的研究不得不个别进行或者通过仿真实现。但幸运的是，为建立收敛特性而存

在着更多功能强大的博弈模型，下面的部分就对其中一些进行讨论。3.3一些特殊的博弈模型这一部分将主要介绍重复博弈模型、超模博弈模型以及潜在博弈模型，并研究每一个模型如何解决.重复博弈模型重复博弈就是一系列的“阶段博弈”，每一阶段的博弈都是相同的一般形式博弈。参与者基于对博弈过程的认知，例如对过去行为的了解，对未来的预期和对当前情况的观察，在每一个阶段的博弈中选择自身的策略。这些策略可以是固定的，也可以随其它参与者行动的改变而变化，甚至可以是自适应的。再者，这些策略能够被设计成惩罚那些违反既定协议行为的参与者。当惩罚发生时，博弈者们选择各自的行为来使得违规者的收益最小化。纳什均衡的存在：一般来说，只有在阶段博弈中存在纳什均衡时，重复博弈才能保证存在纳什均衡。然而，如果参与者被允许相互惩罚，那么适当的设计惩罚规则就能够保证博弈收敛到任何实际的行动向量上。纳什均衡的判定：如果博弈中不允许惩罚，那么纳什均衡就单独的根据阶段博弈的特点来判定。然而，假设博弈过程允许惩罚，那么博弈过程就可被设计得到我们所需的纳什均衡。收敛性：假设惩罚策略设计地很合理，则收敛性可以得到充分保证。潜在博弈模型潜在博弈是一般形式博弈中的一种特殊类型，存在函数v:Af，当单方面的背离发生时，V的变化AV将被反映到单方面背离博弈者的效用上。如果对于所有单方背离，W=Aui则这一博弈称为确定潜在博弈；否则，如果sgn(AV)二sgn(Aui)这一博弈则被称为顺序潜在博弈。模型判定：如果行为空间是紧集合并且效用函数满足式(3-3)，则一个博弈过程就能被视为确定潜在博弈d2d2u(a)idadaijd2u(a)jdadaji但是，除了应用定义，目前还没有明确条件来判断一个博弈过程是顺序潜在博弈。纳什均衡的存在：潜在博弈最少存在一个纳什均衡点纳什均衡的判定：所有的V最大值点都是纳什均衡点。注意这并没有包括一个博弈过程中的所有纳什均衡点，而仅仅指在博弈过程中V最大值的稳定的纳什均衡。收敛性：潜在博弈具有FIP属性，所以当节点采取“自私”的策略选择方式时，就一定收敛于一个纳什均衡。超模博弈模型如果一个博弈过程的行动空间构成一个格，并且效用函数是超模的，则称这个博弈过程为超模博弈。一个偏序集X，如果对于所有a,b£X,都有aAbeX和aVbeX成立，其中aVb=sup{a,b},aAb=inf{a,b}，则称这个偏序集为一个格。一个函数f:X-R，其中X为一个格，若对于所有a,beX都存在f(a)+f(b)Wf(aAb)+f(aVb)，则称这个函数是超模的。模型判定：尽管定义看起来很复杂，但如果所有参与者的效用函数都满足式(3-4)的关系，并且行动空间是紧集合，则一个博弈过程就是一个超模博弈。巴凹＞。巧丰ieNQaQaij(3-4)错误！未找到引用源。纳什均衡的存在：由Topkis不动点定理可知，所有超模博弈至少存在一个纳什均衡点。纳什均衡的判定：文献［40］中提到，一个超模博弈过程中所有的纳什均衡点构成一个格。虽然这并没有对纳什均衡的初始判定有什么帮助，但若知道了一对纳什均衡点，例如a*和b，我们就可以通过计算aAb和a*Vb找到另外的纳什均衡点。收敛性：文献［41］中提到，超模博弈具有弱FIP性质，例如，从一初始行动向量开始，存在一系列的“自私”的策略改变方式使得博弈收敛到纳什均衡。特别的，在超模博弈中一个最佳响应序列也能使博弈过程收敛到纳什均衡。更进一步，如果无线电只产生有限的错误，或者无线电按自身对过去行为观察的平均权重做最佳响应，则整个过程都会收敛［41］［42］。这些相同的收敛结果对潜在博弈同样论分析，则是频谱分配问题模型的关键任务，论证效用函数纳什均衡的存在，讨论这样的纳什均衡是否满足需要，确定收敛的条件等等，这样，我们就可以对相应的算法预计其收敛性，论证均衡状态的最优性等等。一旦算法的效用函数确定，接下来要做的就是针对效用函数的数学形式设计相关的信令协议，并搭建仿真平台进行仿真实验，验证仿真结果与算法的博弈论分析的一致性。从问题的描述、分析到问题的解决、验证，整个基于博弈论的频谱分配问题模型搭建而成，后面的章节里我们会利用此问题模型研究一种基于博弈论的分布式认知无线电频谱分配算法。常见博弈模型介绍1、古诺(Cournot)博弈模型古诺博弈模型是完全信息静态博弈的基本模型，博弈的参与人都以产量作为决策变量。2、伯川德(Bertrand)博弈模型伯川德博弈模型属于完全信息静态博弈模型，博弈的参与人都以价格作为决策变量。伯川德模型假定多个企业生产通类的产品，企业有相同的边际成本，且边际成本是连续函数，企业只通过价格来竞争，并同时决定各自的价格来补给市场需求，企业的行为都是有战略考虑的。3、斯坦克尔(Stacklberg)博弈模型，假定企业1先行动，企业2根据企业1的战略决定自己的行动，企业1知道自己的策略会被企业2知晓。企业的策略可以是价格也可以是产量，如果企业的策略变量是价格，则后行动的企业的利润大于先行动的企业的利润，即“后动优势”，相反如果企业的策略变量是产品，则得到“先动优势”。4、重复博弈重复博弈是指同样的结构的博弈重复多次，其中每次博弈称为“阶段博弈“。因为其他参与人的历史策略是观测得到的，参与人可以通过观察其他参与人的历史策略来做出当前阶段博弈的策略。因此，参与人在重复博弈中的战略空间远远大于、且复杂与每个阶段博弈中的战略空间。这一点意味着，重复博弈可能带来一些额外的均衡结果，这些均衡结果在一次博弈中从来不会出现，这正是分析重复博弈的意义所在。影响重复博弈均衡结果的主要因素是信息的完备和博弈重复的次数。信息完备性，简单的说，当一个参与人的采取的博弈策略特征不为其他参与人所知时，该参与人可能有积极性建立一个“好”声誉以换取长远利益。重复次数的重要性来自于参与人在短期利益和长期利益之间的权衡。当博弈只进行一次时，每个参与人参与人只关心当次博弈的策略，但如果博弈重复多次，参与人可能会为了长远利益而牺牲眼前利益，从而选择不同的均衡策略。基于博弈论的认知无线电频谱分配模型系统模型本文研究的认知无线电频谱分配系统包括三部分：主用户系统、次用户系统，频谱管理机构。本文只研究用户系统之间的博弈过程，将所有次用户当做一个整体考虑。主用户系统由一个位于小区中心的基站和多个用户驻地设备构成。用户驻地设备为位置固定的认知无线电用户设备，使用基站的空闲频谱。频谱管理机构是指完成特定区域或者位置内可用频谱的集中分配，调节通信设备之间频谱共享的过程，并监控相关频谱的服务器主用户系统的频谱既可以用于次用户和主用户系统接入点之间的通信，也可以用于次用户的自组织网络，如网络内的通信。次用户检测到某个区域内有空闲频谱，则频谱管理机构联系，申请租借空闲频谱并将其需求函数等信息传给频谱管理机构；频谱管理机构调用频谱分配算法为次用户选择合适的主用户系统，并将主用户系统信息告知次用户；次用户向选择好的主用户系统租借频谱。一旦次用户建立了通信连接，则整个通信期间，频谱分配都有效，本文建设次用户通信的持续时间相等，因此，公式中不包括时间参数。同时假定频谱分配用户通信的持续时间相等，因此，公式中不包括时间参数。同时假定频谱分配系统中不存在干扰，频谱分配在整个频谱分配区域内有效，没有两个通信过程占用相同的频带，也就是说，某一时刻，一个频点上最多只有一个次用户或者主用户系统正在进行通信。基本方法本文研究的认知无线电频谱分配博弈，是指次用户首先检测到区域内存在空闲频谱，向频谱管理机构请求租用频谱。频谱管理机构收到用户次用户的请求，将频谱租借请求信息广发给各主用户系统。拥有空闲频谱的主用户系统为了获得频谱出租收益决定出租频谱，频谱管理机构规定各个主用户系统为了获取频谱出租收益决定出租频谱，频谱管理机构规定规定各个主用户系统出租的频谱价格相同，数量可不同。不同的主用户系统为了获得最大的频谱出租收益，同时又要考虑自身的出租成本，采取适当的频谱出租策略即决定出租多少频谱，从而形成了多个主用户竞争的博弈过程。通过博弈，主用户系统得到额外的效用，次用户也可以利用主用户系统的频谱传输信息，实现了频谱共享，提高了主用户的频谱利用率。不同主用户系统出租频谱数量可相同也可不相同，出租频谱的价格随着出租频谱总量的变化而变化，市场上出租的频谱数量越多，频谱的价格越低，反之出租的频谱数量越少，频谱价格越高。本文利用效用函数确定次用户是否愿意以频谱管理机构给出的价格购买主用户系统的频谱，该效用函数与频带利用率、频谱数量和频谱价格有关。主用户系统的效用定义为租借频谱得到的货币收入与共享频谱导致的成本之差，其中共享成本与主用户系统的信息传输速率有关。主用户系统相互竞争的目的是通过频谱出租获得最大效用。本文利用非合作博弈解释主用户系统之间的竞争，提出以主用户系统、频谱管理机构、次用户组成的系统模型为基础的静态博弈和动态博弈算法。并求解主用户系统博弈的纳什均衡解，分析不同算法下主用户系统的出租频谱情况。次用户进入频谱分配系统后，首先与频谱管理机构建立连接，将自己的详细信息，如位置、效用函数等传递给频谱管理机构。然后频谱管理机构调用主用户系统的频谱分配博弈算法，确定为次用户提供频谱的主用户系统。在博弈过程中，每个主用户系统每次博弈时都根据各主用户系统的历史策略调整它的当次策略出租频谱数量。以期获得最大的效用。在博弈最终达到稳定平衡状态时，如果次用户接受出租频谱价格，根据次用户的请求，在通信期间，多个主用户系统为次用户分配需要大小的频谱，该博弈完全反应了认知无线电系统中频谱分配过程。系统模型的流程图次用户检测到空闲频谱后，进入频谱分配系统，频谱管理机构收到次用户的租借请求信息请求信息和详细参数信息，调用主用户系统的博弈算法。该方案以频谱管理机构为频谱分配中心更具有实际意义，它有利于频谱管理，也有利于频谱租借市场的规范化。该频谱分配方案由以下步骤完成：（1）次用户检测到空闲频谱，与频谱管理机构建立连接，将它的详细信息，如效用函数等信息传送给频谱管理机构，请求租借频谱。（2）频谱管理机构将频谱频谱租借请求信息进行公示，规定各主用户系统出租的频谱出租价格相同，但随市场供需情况变化。（3不同的主用户系统出租一定数量的频谱，并观察市场供需情况，随时调整自己出租频谱的数量，以获得最大的效益。（4）频谱管理机构判断主用户系统博弈是否达到稳定状态，即市场上出租的频谱总量和各用户出租的频谱的数量是否稳定不变。如果没有达到稳定状态，则继续等待博弈结束，若达到稳定状态，则进行公示，并选定主用户系统出租频谱。（5）主用户系统观察到博弈结束，则与次用户建立通信连接，将稳定状态时自己决定出租的频谱数量的频谱以市场稳定时的频谱价格出租给次用户。（6）次用户使用主用户系统的频谱，在结束通信之后将频谱归还给主用户系统。在第四步中，频谱管理机构通过观察连续三次的博弈结果是否相同来判断博弈是否达到稳定状态。若三次博弈结果均相同说明博弈已处于稳定平衡，各主用户系统不需要再进行决策博弈。本文研究频谱分配中主用户系统间的博弈算法，将该问题抽象为博弈论中的寡头竞争模式，分别设计静态博弈算法古诺模型算法和动态博弈算法基于产量决策的斯坦科尔伯格模型算法，最终目的是提高主用户系统出租频谱总量，同时提高了主用户系统的频谱利用率。博弈稳定后主用户系统效用最大化，从而出租频谱的积极性提高，次用户使用主系统的频谱进行通信，改善了主用户系统的频谱利用率，实现认知无线电技术的应用价值。

静态博弈算法：古诺模型分配算法经典的古诺模型及纳什均衡解为了更好的描述本文提出的古诺模型算法，下面先阐述经济学中的古诺双寡头垄断模型。令错误！未找到引用源。、错误！未找到引用源。分别表述企业1、2生产的同质产品产量。市场中该产品的总供给错误！未找到引用源。，令P(Q)=a-Q表示市场出售的价格，a是一个大于零的常数。设企业i生产q.错误！未找到引用源。的总成本为C(q)二cq,即企业不存在固定成本，且生产每单位产品的边际成本为常数c,这里我们假定cva。根据古诺的假定，两个企业同时进行产量决策。为求出古诺博弈中的纳什均衡，首先将其化为标准式的博弈。前面已讲过，博弈的标准式表述包含下列要素：(1)博弈的参与者；(2)每一参与者可供选择的战略(3)真对所有参与者可能选择的战略组合，每一参与者获得的收益.双寡头垄断模型中当然只有两个参与人，即模型中的两个垄断企业。在古诺模型中，每一个企业可以选择的战略是其产品产量，假定产品是连续可分割的。由于产出不可能为负，每一企业的战略空间就可以表示为Si=[0,-],即包含所有非负实数，其中一个代表性战略Si就是企业选定的产量，q.三0。由于Q三a时，P(Q)=0,任一企业都不会有qi>a的产出。要全面的表述这一博弈并求其均衡解，还需要把企业i的收益表示为它自己和另一企业所选择战略的函数。我们假定企业的收益就是其利润额，这样在一般的两个参与者标准式博弈中，参与者i的收益就可以写为：错误！未找到引用源。兀(q,q)二q[p(q+q)-c]二q[a-(q+q)-c]iijiijiij在一个标准式的两人博弈中，一对战略错误！未找到引用源。)如果是纳什均衡，则对于每个参与者i，错误！未找到引用源。应该满足：u(s*,s*)>u(s,s*)iijiij上式对Si中每一个可选战略错误！未找到引用源。都成立，这一条件等价于：每个参与者i，错误！未找到引用源。必须是下面最优化问题的解：错误！未找到引用源。maxu(s,错误！未找到引用源。maxu(s,s*)iijsesij在古诺的双头垄断模型中，上面的条件可具体的表示为：一对产出组合(q*,q*)错误！未12找到引用源。若为纳什均衡，则对每一个企业i,错误！未找到引用源。错误！未找到引用源。q*应为下面的最大化解：imax兀(q,q*)二maxq[a—(q,q*)—c]0<q.争11j0<q.Ms11j设q*错误！未找到引用源。<a-c(下面将证明该假设成立)，则上面的式子的最优解为：jq=1(a—q*—c).2j那么，如果产量组合(q*,q*)要成为纳什均衡，两个企业的产量选择必须满足：12q*=[(a—q*—c)且q*=^(a—q*—c)错误！未找到引用源。1222211解这一对方程组得：q*=q*=3(a—c)123均衡解的确小于a-c，满足上面的假设。古诺模型算法算法思想：各主用户系统出租品质相同的频谱，价格相同并随市场需求波动。主用户系统的行为自私不合作，相互之间以出租的频谱数量进行博弈。各主用户同时采取出租策略(决定出租的频谱数量)，且能熟悉其他主用户系统之前采用的策略。主用户系统根据历史策略判断当次最适合自己的策略，经过多次博弈后，各主用户系统出租的频谱数量达到均衡稳定值。算法的最终目的是使得主用户系统出租的频谱数量最大化，但求解目标是使主用户系统的效用最大化，主用户系统的效用表示为：u(b错误！未找到引用源。)=p错误！未找到引用源。b-C(错误！未找到引用源。b)错误！未找到引用源。其中匕表示主用户系统i出租的频谱数量，p表示出租的价格，C(b.)表示主用户系统i的出租成本。该效用函数反映了主用户系统出租频谱的积极性，效用大，主用户系统通过频谱出租得到的收益多，从而主用户系统出租频谱的积极性就高，反之，效用低则出租频谱的积极性就越小。古诺模型算法的纳什均衡求解即是求当主用户系统效用最大时出租频谱的数量。从公

式可以看出，出租频谱价格和主用户系统出租频谱的成本均未知。下面分别说明频谱价格和

出租成本的求解方法。由上节的论述可知：可出租的频谱数量越多，频谱的价格就越低；反之可出租的频谱数量越少，频谱价格越高。可以通过次用户的效用函数得到频谱价格和频谱数量的准确关系次用户的效用函数的选择不是唯一的，本文要保证频谱分配算法能够达到均衡收敛

根据文献给出的二次效用函数做出适当的修改如下：u（b）=迓bk（s）-丄（迓b2+2工bb）一迓pbpii2iijii=1i=1i=ji=1其中错误！未找到引用源）是次用户所租借频谱的频带利用率，bi错误！未找到引用源。表示主用户i出租的频谱的数量，p表示出租的频谱价格。采用公示的二次效用函数原因如下：（1）根据博弈论中纳什均衡存在性定理，要求效用函数必须连续且是拟凹的，公示中的效用函数满足该条件。（2）对该二次函数微分可以得到线性的频谱价格函数，从而使得采用经典的博弈论模型构建认知无线电频谱分配模型变得容易。如果公式是一个二次拟凹函数，则必然有一个最大值。通过将该效用函数对频谱数量求导即可得到效用最大值，同时得到频谱价格与频谱数量的关系：iii=1du(biii=1sdbi得到频谱价格函数：p=号）一bi=1从上面公式可以看出，频谱价格与频谱数量成线性关系，为了获得两者之间的准确关系，还必须要求知道错误！未找到引用源。叮），必须了解本文认知无线电的无线传输模型,描述如下：次用户系统采用自适应调制技术，传输速率可以根据信道质量动态的调整。采用正交幅度调制方式MQAM（采用矩形星座图，如4-QAM,16-QAM），单输入单输出高斯信道的比特错误概率（BER）可近似表示为：BER沁0.2exp（-1.5/（2k-1））其中，丫表示接收机信噪比，K是所用调制方式的频带利用率即公式中的k（s），设定比特错i误概率门限值为BERtar，则频带利用率为：log?。+対)其中K=k其中K=k=1.5ln(0.2BER)tar结合公式可得到频谱价格与频谱数量的关系：—(lOg2—(lOg2(l+)bii=1Yln(0.2BER)tar接下来再求主用户系统的出租成本。如果主系统将当前空闲的频谱租借给次用户使用，那么次用户没有结束通信之前，该频谱分配有效，即使是主用户系统也不能使用该频谱，因此主用户系统可以使用的带宽减少，导致主用户系统的服务质量下降，这就是主系统与次用户共享频谱的成本。在古诺模型和后面要阐述的斯坦科尔伯格模型算法中假设边际成本不变，设为C,即成本函数为c错误！未找到引用源。，这个模型适用于主系统带宽无限，可以无限满足次用户需求的情况，但实际上频谱是稀缺资源，主用户系统带宽有限，主用户系统租借给次用户使用的频谱占其可用频谱的比例越大，对主用户系统的QOS影响越大，因此边际成本不变的成本函数在认知无线电系统中不适用，这里采用二次成本函数，如下式所示：c(b)=oM(Breq—K(P)—i卜)2iiiiMi其中®代表成本函数的权重，根据经典的古诺模型和斯坦科尔伯格模型k($)。Breq错ii误！未找到引用源。是一个主系统本地连接实际使用的频谱宽度，W和M错误！未找到ii引用源。分别指主系统i的频谱宽度和本地连接数目，k(p)错误！未找到引用源。表示主系i统的频谱利用效率，k(p)=Breq/(W/M)。iiii1.5Bre1.5Brebqii-)2iMiup(b)=p—叫)=(1o®1n).2BER)Y)仝呐tari=1动态博弈算法：斯坦科尔伯格模型算法经典的斯坦科尔伯格模型及纳什均衡斯坦科尔伯格在1934年提出一个双寡头垄断的动态模型，其中一个支配企业首先行动，然后从属企业。模型中的企业选择产量，这一点和古诺模型是一致的，不同的古诺模型中企业是同时行动的，不同于智力的序贯行动。博弈的时间顺序如下：(1)企业1选择产量q＞错误！未找到弓I用源。0；⑵企业2观察到错误！未找到引用源。％,然后选择产量q＞错误！未找到引用源。0；(3)企业i的收益由下面的利润函数给出：2兀(q,q)=q(p(Q))—ciiji

这里p(Q)=a-Q,是市场上的总产品Q=错误！未找到引用源。qi+错误！未找到引用源。q?时的市场出售价格，a为大于零的常数，c是生产的边际成本，为一常数(固定成本为0)。为求出这一博弈的逆向归纳解,首先计算企业2对企业1任意产量的最优反应,R(q)错误！未找到引用源。应满足：21max兀q210q2)max兀q210q2)二q乂212由上式可得：a-q-c已知qi＜错误！未找到引用源。a-c，在古诺模型中得到的晌)错误！未找到引用源。和上式完全一致，两者的不同之处在于这里的R2(qi)是企业2对企业1已观察到的产量的真实反应，而在古诺的分析中，且企业1的产量选择是和企业2同时做出的。由于企业1也能够像企业2一样解出企业2的最优反应，因此企业1就可以预测到当他选择错误！未找到引用源。时企业2根据错误！未找到引用源。尺2(%)选择产量。那么,a—q—a—q—cmax1q1>02max兀(q,R(q))=maxq[a一q一R(q)一c]=qi^01121qi刃2121a—c/、a—c由上式可得错误！未找到引用源。q：=〒及R(q)=-4这就是斯坦科尔伯格双寡头垄断博弈的逆向归归纳解。斯坦科尔伯格模型算法算法思想：各主用户系统出租品质相同的频谱，价格相同并随市场需求波动。主用户系统的行为自私不合作，相互之间以出租的频谱数量进行博弈。由于某种原