认知无线电算法分析的博弈模型外文翻译.doc

GAME MODELS FOR COGNITIVE RADIO ALGORITHM ANALYSIS

认知无线电算法分析的博弈模型外文翻译
- 11 - / 12
摘 要
博弈论用于分析相互影响的自适应和认知无线电是一种很有前途的方法。本文分析了认知循环的组成部分如何映入标准形式的博弈模型，以及标准的博弈论所要解决的四个重要问题，它们是稳定状态的存在，稳定状态的求解、收敛以及稳定状态的最优性。然后，本文描述了三种博弈模型，这有助于人们分析问题和用新的方法得出结论，博弈模型的使用促进了自适应和认知无线电的分析和发展。　　
1 绪 论
认知无线电通常作为一个实现动态分布式无线资源管理算法的平台。在设想的情景中，无线设备将对网络状态的情况做出反应，并根据一些目标驱动算法改变他们的行为。然而，无线电适应也改变了网络状态，同时出现了一个互动的决策过程。
在这个互动的决策过程中，设计分布式算法，以确定以下属性：稳定状态的存在性和特性，稳态效率，算法的收敛性。这些属性可以通过确立大量的仿真和现场测试，或者通过分析博弈论模型来确立。
几位作者曾评论分析网络互动的决策过程方面的博弈论的适用性。博弈理论已被用于确立稳定状态的存在，描述的稳定状态，预测稳态效率，和确立收敛性。然而，这些结果在ad-hoc的基础上成立，因此它们的博弈理论分析的结果不容易扩展到和此不同的网络和算法中。所以，每次分析必须重新开始，大大延长了需要确立新的结果的时间，减少分析和仿真方面提供许多的优势。
为了不对每个新的网络和算法重复分析，本文提出了对认知无线电算法分析的博弈模型。采用基于模型的分析方法，可以更有效地得出博弈模型和博弈模型的识别标准的结论。本文列出几个特殊的博弈模型，尤其是潜在的博弈，超模博弈和重复博弈。这些模型涉及了稳定状态的存在性，特性，效率和收敛性的属性描述，并给出了模型的识别方法。作为这次讨论的一部分，本文确定并描述适用于这些模型更广泛的博弈论的概念，这些模型对确立分布式算法的适用性很重要。
2 认知无线电和博弈论
本节简要回顾认知无线电博弈论和基于博弈论的认知无线电的应用方面的内容。2.1 认知无线电
认知无线电具有对自己的能力、外界环境、计划的策略的自适应性，并能够认知得到新的波形，新的模型，新的决策方案。对认知无线电的操作的设想，常用图1所示的认知循环表示。
在认知循环中，无线电通过直接观察或通过信令接收有关其操作环境（外界）的信息。然后评估此信息（定位），以确定其重要性。基于此评估，无线电决定了它的备用方案（计划），并选择替代的方案（决策），预测提高估值。假设一个波形的变化是很必要的，而后无线电通过调整其资源和执行适当的信令实施备用策略（执行）。这些变化反映了外界的认知无线电干扰轮廓。整个过程中，无线电使用这些观察和决策，以提高对无线电的操作（学习），通过建立新的模型状态，产生新的备用策略，或创建新的估值。在很大程度上，认知无线电和自适应无线电之间的主要区别是认知无线电的学习能力。
新状态

学习

判决
原始状态

外部环境
执行

制定计划

观察环境

自身定位

图1 认知循环

然而认知无线电的实现需要大量的研究，本文特别关注的是在外部环境下决策的相互作用。每当一个认知无线电轻易改变其干扰轮廓时，网络中其他的认知无线电也可能会改变它们的干扰。这种互动式的决策问题是博弈论需要处理的问题。
2.2博弈论
博弈论是一组用于分析交互决策过程的数学工具。博弈论的基本组成部分体现了博弈的概念。正常的形式下，一个博弈用公式＜；；{}＞来表示，它有以下三个主要组成部分：
1. 一组有限​​的参和者（决策者）通常表示为。
2. 一个由所有参和者的策略集合组成的策略空间，用笛卡尔积表示。
3. 一个效用函数集合：，体现出决策者对可能的利益的偏好关系。而利益是由在博弈中决策者的特殊策略和所有其他的决策者的策略决定的。
在博弈中，策略者被认为是在为它们的自身利益行事，也就是说，每个决策者以一种增加其效用函数返回的数量值的方式来选择行动。其他的博弈可能包括不同的元素，如提供给每个决策者的信息和通信机制。
2.3博弈论的认知无线电中的应用
如图1所示的认知循环，它可以很容易地看到认知（或自适应）无线电网络之间的相互作用是如何应用到博弈中的。
网络中的每个节点都是一个博弈中的决策者，它完成了决策步骤（决策者）的认知循环周期。各种备用策略作用于一个节点形成的节点动作集，从无线电的备用策略的笛卡尔积形成的操作空间。认知无线电的观察和定向的步骤结合起来，形成一个决策者的效用函数。观察步骤大致提供了决策者评估的效用函数的参数，而定向步骤决定了效用函数的估值。
值得注意的是，我们忽略了认知周期的学习步骤。这不是疏忽，也不是一个博弈论的局限性的描述。然而，博弈模型的正常的形式适合于任何自适应无线电算法或不需要学习的任何自适应认知无线电中，这是不适合于学习的分析算法。在这种情况下，应该使用更先进的博弈模型，结合学习过程，如贝叶斯博弈。还应当指出的是，博弈论是不适合行动和目标在认知无线电超时学习的可能的情况下定义的博弈。
3 认知无线电分析
博弈论分析自适应算法时，应回答的问题有4个：
1. 该算法是否有一个稳定的状态？
2. 什么是稳定状态？
3. 该算法是理想的稳定状态吗？
4. 什么限制决定更新算法，以确保收敛？
大多数博弈应用理论分析的重点在前3个问题上，很少解决第4个问题。然而，这4个问题应在执行任何认知无线电算法之前得到回答。
3.1 证明算法具有稳定状态
对于大多数博弈模型来说，关于分布式算法的稳定状态的博弈理论称为纳什均衡理论。假设一个动作矢量（或备用矢量）满足纳什均衡，用下式（1）表示。

(1)

重申一下，纳什均衡是一个行为矢量，当它自身行为时，没有决策者能提高其效益。一次博弈，不需要使用较复杂的模型，使用相关的定点理论存在的纳什均衡就可以将它展现出来。然而，这些定点理论对一个没有经验的分析者来讲可能会显得较为复杂，最常见的应用可以归结为满足以下条件：
1. 策略者集合是有限的；
2. 行动集合是封闭有界的，而且是凸的。间隔和间隔的笛卡尔积满足这个条件；
3. 效用函数在行动空间内是连续的，准凹的。值得注意的是，证明该效用函数是凹函数的方法是二阶导数测试法，此方法足以证明其准凹性。
实际上，有很多的算法满足这些条件，所以证明纳什均衡存在性并不是最优的，因为对认知无线电算法的稳定状态可能会假设错误，或者在一个单一的博弈中可能会有多个纳什均衡。然而，并不是所有博弈方法和所有的算法都能将满足这些条件，所以研究具有稳定性的算法仍有一些价值。
如果允许无线电台混合使用其战略，即，如果一台无线电台在行动策略a和b之间允许存在随机备用策略，然后移除条件（3），并可以放宽条件（2）的凸度要求。有限行动空间将满足这个放宽的条件。这些宽松的条件被称为纳什定点定理。
3.2 识别稳定状态
对其自身而言，证明一个博弈具有稳定状态不是很有用，因为它没有提供洞察该算法的预期行为。这就是稳态需要识别的原因。但是，没有引入更先进的博弈模型，如潜在博弈模型，正常的博弈模型不能提供识别纳什均衡任何工具。
事实上,用来识别行动向量（纳什均衡点），分析者必须应用式(1),确认所有可能源于的单边偏差，也不能改善损害决策者的利益——一个多项式时间的问题。然后找出在一次博弈中所有可能的稳定状态, 对这次博弈中所有可能的行动向量组，必须重复这个过程,使纳什均衡问题的化。
事实上,当试图识别在一次博弈里所有纳什均衡点,分析师们借助仿真来实现——我们专注于最小化的步骤。例如,联合功率自适应系统建模的GPRS网络有4个纳什均衡点, 尽管建模系统[5]中只有7个决策者，依靠着一个详尽的仿真也要花费数天才能完成。
3.3 确定稳定状态可取性
虽然识别一个行动向量是否具有一个“好”的稳态有很多不同的方式，但我们遇到最典型的技术是证明这个行动向量是帕雷托最优，就像文献提到的那样。一个行动向量,假如不存在其他的行动向量，则它是帕雷托最优的,用数学表达式表示为则。
虽然证明稳态是帕雷托最优的，这看上去似乎是一个不错的结果,但事实上,帕雷托最优是一个很弱的概念，分析者从中仅能得到稳态可取性的很少信息。这一点可通过两个简洁的分析来说明,一个是分布式功率控制的例子和另一个是检查呼叫接纳的问题。
3.3.1 信息干扰噪声比（SINR）最大化的功率控制
考虑一个中心接收机的单一群DS-SS网络，中心接收机外的所有节点正调整其发射功率标准以试图最大限度地测量接收信号干扰加噪声比（SINR）。在这里，我们的决策者集合是群中的节点（除中心接收机以外）；行动集合是可用的功率标准（大概是数量有限的功率标准）;而所有决策者的效用函数由式（2）表示

（2）

其中为i节点的发射功率，k是扩频因子的统计估计，是从节点接收增益（大概不到1），σ是接收机的噪声功率。
这次博弈的唯一的纳什均衡是所有节点以最大功率传输的功率矢量。显然，这是一个非理想的结果为：
1. 由于远近效应的问题（除非节点是在距接收机相同的半径），能力大大减弱；
2. 产生SINR是不公平的分配（最接近的节点的SINR远远优于最远的节点）；
3. 电池寿命将大大缩短。
然而，这一结果将是帕雷托最优的，由于任何更公平的功率分配将减少最接近的节点的效用，任何不太公平分配将减少弱势节点的效用。在这种情况下，帕雷托最优实际上误导分析者关于这方面的结果是可取性。
3.3.2 呼叫接入
现在，假设节点要求的是来自一个网络而来的数据带宽，而这个网络是在先到先得基础上分配网络带宽的。在这里，我们决策者群是请求节点的带宽;行动是每个节点可以请求的量化带宽;我们可以假设效用函数是接受数据带宽的单调函数（带宽越宽越好）。我们由此将引入另一个博弈模型，这个模型并不能同时满足所有的要求。这次，虽然对该模型复杂性的了解已对该结果得帕雷托最优含义的理解病不是那么不重要，但所依赖的场景仍是以广泛形式博弈模型的最佳建模。
在稳定状态中，每个先到达的节点将获得尽可能多的带宽，并阻碍网络中后到达节点占用该带宽。一般情况下，阻止潜在的大量节点并不是一个很好的结果。然而，由于其他带宽分配会降低先到达节点的效用，所以这是帕雷托最优的。一个更好的证明稳态可取性的技术是评估所确定的稳定状态如何设计其网络的目标函数。例如，在3.3.1节中的SINR的情况，可以通过衡量容量或总体系统的目标函数更好地评估可能由预期的电池寿命的措施增加的系统总吞吐量。并不像评估帕雷托最优那样，第3.3.2节中的呼叫接入方案的稳定状态是可以得到更好地评估的。
3.4 确立收敛性条件
确立稳态可取性和识别稳定状态同等重要，它是指在什么条件下，该算法能达到稳定状态。可以由展示在表1中的博弈数据说明两个抽象的认知无线电交互关系。

表1 弱FIP博弈模型的博弈表

A
B
C
a
1,-1
-1,1
0,2
b
-1,1
1,-1
1,2
c
20
2,1
2,2

这个博弈表塑造一个有两个认知无线电网络，其中一个认知无线电有备用策略a、b和c,和另一个有备用策略A,B和C。每个认知电选择的实现由不同的外界认知环境决定，例如,(A,c)或(B,a)是无线电无线电要观察和评估的数据。第一个无线电分配给一个结果的值由那个表的各个元素的第一个入口给出 ,第二个无线电分配给一个结果的值是由第二个入口给出。
这个博弈模型有一个唯一的纳什均衡点(c、C),它也是帕雷托最优点，更是网络策略者的目标函数(我们假设的所有无线电效用的总和)的个人看法的错所有可能性。然而,如果无线电采取尽可能小的步骤调整自己的决定,提高适应无线电的代价,然后博弈过程可以继续循环。然而,如果在任何时刻,无线电允许采取最大的步骤,然后博弈模型将收敛于唯一的纳什均衡点。
但是,正常形式博弈模型没有提供对收敛性标准的洞悉,因此，假如分析的话(没有考虑收敛)，收敛性必须分别分析,或通过仿真分析。下章节将会讨论更有效的博弈模型。
4 相关博弈模型
本节回顾了重复博弈模型、超模博弈模型和潜在的博弈模型，并探讨这些博弈模型如何解决在第3章节所提出的第1、第2和第4个问题。对于所有模型，为解决第三个问题，需要用网络目标函数替代预测网络的稳定状态来分析。
4.1 重复博弈
重复博弈是一连串的“阶段博弈”，其中每个阶段的博弈均是相同的正常形式的博弈。根据它们的博弈过程——过去的行为，目前的观测，对未来的期望，决策者选择策略——在每一个阶段的行动选择。这些策略可以固定，视其他决策者的行动或适应性而定。此外，这些策略可以惩罚行为不一致的决策者。处罚时，决策者选择它们的行为使犯规决策者的收益最小。
纳什均衡存在性：在一般情况下，如果阶段博弈中有一个纳什均衡，那么重复博弈也一定有一个纳什均衡。但是，如果允许决策者相互“惩罚”，然后收敛于任何动作向量，以确保设计的“惩罚”的方案的可能性。
纳什均衡规定：如果博弈允许惩罚的话，纳什均衡识别将完全依赖于阶段博弈的性质。但是，假设博弈允许惩罚，则设计的博弈模型有一个所需的纳什均衡。
收敛：假若惩罚策略是设计得当，保证收敛。
例子：重复博弈应用于分布式功率控制问题和资源共享问题。
4.2 潜在博弈模型
潜在博弈是一个特殊的正常形式的博弈，它有一个对应的函数，V：，这样，当一个单方面发生偏差时，V的变化量ΔV反映了在值域单方面偏离决策者值的变化。模型识别：如果行动空间紧凑，效用函数满足

（3）

可以称这个博弈是一个精确的潜在博弈。
除了应用那个定义外，没有明确的条件验证一个博弈是一个序列潜在的博弈。然而,如果一连串效用函数的序列转换导致一个确切的潜在博弈,那么最初的博弈是一个序列潜在博弈。
纳什均衡的存在性：潜在的博弈总是至少有一个纳什均衡。
纳什均衡识别：所有V的最大值是纳什均衡点。值得注意的是，这并不是说每个博弈都有纳什均衡点，但博弈中稳定的纳什均衡点一定是V的最大值。
收敛：潜在博弈有改善路径（FIP）的局限性质，所以当节点以一个自私的手段运作时，决策收敛于纳什均衡点。
例如，潜在博弈应用到自适应干扰回避问题的分析，潜在博弈应用到分布式功率控制。
4.3 超模博弈模型
如果行动的空间形成了一个超模格和效用函数是超模的，则该博弈称为是超模的。部分有序集X称为一个超模格，对所有，其中。一个函数，：，其中X是一个格，如果所有， 则称其为超模。 (+
模型识别虽然定义看上去很复杂，但是如果所有决策者的效用函数满足式（4）的关系和行动空间紧凑，则一个博弈可以称为超模博弈。

（4）

纳什均衡存在性：通过Topkis的不动点理论，所有超模博弈至少有一个纳什均衡点。
纳什均衡识别：一个博弈的所有纳什均衡可以形成一个格。虽然这并不能帮助分析从每对纳什均衡点初步确定纳什均衡的过程，但是另外的纳什均衡点可以评估和来确定。
收敛：超模博弈有弱的FIP，即从初始行动矢量中，存在若干个纳什均衡的自私适应系统。超模博弈的最佳响应序列会收敛于一个纳什均衡点。此外，如果无线电造成了有限量的错误或无线电替换了衡量从最近的过去观察的平均值的一个最佳响应，决策将趋于收敛。这些相同的收敛结果视为潜在博弈的FIP（即薄弱的FIP）。
例如，由Altman，Yates研究的分布式功率控制场景是以超模博弈为蓝本建模的。
5 结 论
前文我们已经说明了认知循环图是如何映射到正常形式的博弈模型上的，同时确定了博弈论在认知或自适应无线电的应用中应解决的四个问题： 稳定状态存在、 稳定状态识别、 稳态最优性和收敛。我们已证明帕雷托最优是不足以证明稳定状态的可取性和网络目标函数的评价是偏向于确定稳态可取性。然后，我们描述了三种可以用来解决剩余的三个问题德博弈模型。
但是，使用博弈模型的评估超出此有限的讨论。在分析中，潜在博弈似乎是更不容易引入噪声， 因此稳定状态被显示出来。
博弈模型可以提供深入了解认知无线电的设计和实现。例如，假定一个设计师欲实现网络函数最大化的算法。然后决策者的效用函数（观察和定位步骤的认知循环），可以表示为，而是一个“虚拟”函数，它取决于其他无线电的行动。另外，如果现​​有的算法可以被证明是一个潜在博弈且不同网络的稳定状态是理想的，那么这可能是通过引入了一个代价函数。博弈模型也可以用来估计算法的复杂性。认知无线电的最佳模型可以用来作为算法复杂性的一个指标。实现认知无线电时，一个关键的研究任务是本体发展表达了无线电有关其自身、波形和网络所需要的信息。包含博弈模型机制的本体将提供了一个紧凑的方式来表示预期的行为信息网络，完善一个认知无线电的预测能力，并且规划其性能。
鉴于这么多的优势，利用博弈模型的分析方法分析适应性和认知无线电的算法是可取的。