（电路与系统专业论文）基于重复博弈的跨洋航空网频谱分配算法研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 近年来，我国民用航空业飞速发展，航空通信业务量剧增，a t m 系统通信容 量已经趋于饱和。另外，随着国外航空宽带移动通信的开放，我国航空移动通信 的解禁也指日可待，届时航空通信频谱资源将更加紧张，传统频谱分配利用率低 的弊端将日益显现，因此研究适用于航空通信网络的频谱共享方法已经刻不容缓。 未来的航空移动宽带通信网络是一个空天地一体化系统，飞机不仅可以与地 基基站和中继卫星直接通信的基础上，也可通过由飞机自组织建立的航空白组网 与地基基站通信，实现低成本的快速宽带数据传输。航空白组网中包含有多架飞 机组成主干网和游离的飞机节点。主干网的链路结构稳定，拥有频谱使用权，而 游离的飞机节点则需要通过与主干网链接才能完成通信需求，本文着重讨论了这 种背景下的频谱接入问题。 基于认知无线电的频谱分配是当前频谱共享理论的研究热点。本文针对航空 自组网的特点，通过将博弈论和认知无线电有机结合，提出了一种基于重复博弈 的频谱共享策略。在基于重复博弈模型下的频谱共享算法中，针对航空自组网的 频谱分配问题，首先，本文用单次博弈对单个时隙中的频谱竞争问题进行建模， 分析了单次博弈下的纳什均衡策略；其次，用重复博弈对用户在多个时隙下的频 谱竞争行为建模，提出了基于最大吞吐量准则和比例公平准则的频谱分配策略； 同时，本文给出了基于不同惩罚策略的防欺骗手段，通过这些防欺骗的措施使得 参与用户约束自己的行为以合作方式共享频谱、实现频谱分配，保证合作竞争的 诚实性。最后，从仿真结果可以看出防欺骗方式能很好的约束博弈双方保持合作， 本文提出的频谱共享策略能够很好的降低用户间的干扰，提高系统的频谱利用率。 关键词：频谱共享；纳什均衡；重复博弈；惩罚；防欺骗 重庆大学硕士学位论文英文摘要 a b s t r a c t i nr e c e n t y e a r s ，w i t h t h e r a p i dd e v e l o p m e n t o fc h i n a sc i v i l a v i a t i o n ， c o m m u n i c a t i o nb u s i n e s sh a sg r e a t l yi n c r e a s e d t h ea t m ( a i rt r a f f i cm a n a g e m e n t ) s y s t e mh a sa p p r o x i m a t e di t sm a x i m u mc o m m u n i c a t i o nc a p a c i t y i na d d i t i o n ，a st h e c o m m e r c i a lo p e r a t i o no fa v i a t i o nb r o a d b a n dm o b i l ec o m m u n i c a t i o na r o u n dt h ew o r l d ， s o o nw i l lc h i n a a n dt h e nt h ew i r e l e s sf r e q u e n c yr e s o u r c e sb e c o m em o r ep r e c i o u s t h e e x c l u s i v es p e c t r u ma l l o c a t i o nm o d eh a sn o tf u l l yu s e dt h ef r e q u e n c y , r e s u l t i n gi nt h e t e n s i o no ft h es p e c t r u mr e s o u r c e s t h e r e f o r et h es t u d yo fs p e c t r u ms h a r i n gs t r a t e g y , w h i c hi ss u i t a b l ef o ra v i a t i o nc o m m u n i c a t i o nn e t w o r k ，i so fp r i m ei m p o r t a n t t h ea v i a t i o nm o b i l ec o m m u n i c a t i o nn e t w o r ko ft h ef u t u r ei sai n t e g r a t e ds y s t e mo f a i ra n dl a n dc o m m u n i c a t i o ns y s t e m ，w h i c hi st h ec o m b i n a t i o no fs a t e l l i t e - b a s e dn e t w o r k ， t h el a n d b a s e dn e t w o r ka n dt h e s p a c e b a s e d n e t w o r k a i r c r a f tc a nc o m p l e t e c o m m u n i c a t i o nb a s e do nt h el a n d b a s e dn e t w o r ko rs a t e l l i t en e t w o r k a n da l s ot h r o u g h t h eo r g a n i z a t i o na v i a t i o na dh o cn e t w o r ka n dt h el a n d b a s e dn e t w o r k ，r e a l i z ed a t a t r a n s m i s s i o nw i t hal o w e rc o s ta n df a s t e rr a t e a v i a t i o na dh o cn e t w o r ki sf o r m e db y t h eb a c k b o n el i n k s ，w h i c ha r ef o r m e db ya i r c r a f t s 、) l ，i 廿1c l o s es p e e d so rs a m ed i r e c t i o n s ， a n ds o m ef r e ea i r c r a f tn o d e s t h eb a c k b o n el i n k sa r es t a b l e ，a n dh a v et h es p e c t r u m u s i n gp r i o r i t y , w h i l et h ef r e ea i r c r a f tn o d e s n e e dt h r o u g ht h eb a c k b o n el i n k st oc o m p l e t e c o m m u n i c a t i o nd e m a n d a n dt h es p e c t r u ms h a r i n gp r o b l e m sd i s c u s s e di nt h i sp a p e ri s w i t h i nt h i ss c o p e c o g n i t i v er a d i ob a s e ds p e c t r u ma l l o c a t i o ni s t h eh o ts p o to fc u r r e n ts p e c t r u m s h a r i n gt h e o r yr e s e a r c h e s c o n s i d e r i n gt h ec h a r a c t e r i s t i c so fa v i a t i o na d h o cn e t w o r k ， i n t r o d u c i n gt h et h e o r yo fg a m et h e o r yi n t o c rt e c h n o l o g y ，t h i sp a p e rp r o p o s e sa r e p e a t e dg a m eb a s e ds p e c t r u ms h a r i n gs t r a t e g y r e f e r r i n gt ot h em o d e lo fr e p e a t e dg a m e t h e o r yf o rs p e c t r u ms h a r i n ga n dt a k i n gi n t oa c c o u n to fo na i r l i n ea dh o cn e t w o r ko f s p e c t r u ma l l o c a t i o np r o b l e m ，i nt h i sp a p e r , f i r s tu s eas i n g l e t i m eg a m et om o d e lt h e s p e c t r u mc o m p e t i t i o np r o b l e m si no n et i m es l o ta n dt h e na n a l y z et h en a s he q u i l i b r i u m s t r a t e g yo ft h es i n g l e t i m eg a m e a st h es p e c t r u mc o m p e t i t i o nw i l ll a s tf o ral o n gp e r i o d a n dr e p e a ti ne v e r yt i m es l o t ，u s ear e p e a t e dg a m em o d e lt od i s c u s st h es p e c t r u m s h a r i n gp r o b l e m s i nt h er e p e a t e dg a m em o d e l ，t h e r ep u tf o r w a r ds p e c t r u ma l l o c a t i o n s t r a t e g yb a s e do nm a x i m u mt o t a lt h r o u g h p u tc r i t e r i o na n dp r o p o r t i o n a lf a i r n e s s c r i t e r i o n t oa v o i dt h eu s e r s c h e a ta c t i o n s o m ec h e a t p r o o fm e t h o d si sd i s c u s s e dt o i i r e s t r a i nt h e i rb e h a v i o r si no r d e rt os h a r et h es p e c t r u mi nac o o p e r a t i v ew a y b a s e do i lt h e c h e a t p r o o fm e c h a n i s m t h es i m u l a t i o nr e s u l t ss h o wt h a tt h em e t h o dp r o p o s e dc a n r e d u c em u t u a li n t e r f e r e n c ea n dt h ec h e a t p r o o fm e t h o dc a nr e d u c et h ei n t e r f e r e n c e b e t w e e nu s e r s ，i m p r o v et h es p e c t r u mo fu t i l i z a t i o n ，a n dc a nk e e pp l a y e r si nc o o p e r a t i o n e f f i c i e m l y k e y w o r d s ：s p e c t r u ms h a r i n g ；n a s he q u i l i b r i u m ；r e p e a t e dg a m e ；p u n i s h ；c h e a t 。p r o o f i i i 重庆大学硕士学位论文1 绪论 1绪论 1 1 课题研究背景 1 1 1 迅速发展的航空业 航空业是经济全球化的主要载体之一，也是全球发展最快的产业之一。2 0 世 纪5 0 年代以来，民用航空的服务范围不断扩大，民用航空已然成为一个国家的重 要经济部门。我国地域广阔、资源富裕，适合发展便利、灵活、快捷的航空运输 业。伴随着现代经济的快速增长，我国的外交活动变得更加频繁和活跃，旅游、 贸易等也有了较快的发展，对航空运输产生了更大的需求。 作为一种新兴的现代经济发展服务模式，航空业带动的经济发展正在成为未 来主要城市经济发展的重点。从发达国家及经济发达地区的发展经验上可以看出， 以机场、空港为依托，大力发展航空枢纽经济及航空制造经济对有效增大就业机 会、促进区域经济的发展有着重要的指导意义。但同时空中交通流量的飞速增长 对各种飞行保障系统提出了越来越高的要求，在航空通信和信息的快速、准确、 可靠性以及各种信息的自动化处理方面的要求越来越高，给现有的航空无线通信 系统带来了巨大的压力。 民用航空是一种先进的交通运输方式，也是我国国民经济和社会发展的重要 行业，新中国建国以来伴随着国民经济和社会经济的发展，中国的民用航空业获 得了极大的发展，取得了很大进步。改革开放近三十年来，我国民航的运输量始 终保持着快速的增长趋势，航线网络的规模不断地扩大，机队规模、运输能力得 到了显著提升，航行的安全水平得到了明显提高，航空相关基础设施的建设正逐 步完善，管理体制的革新及对外开放进展迅速，航空运输作为先进的交通运输方 式已成为了现代社会经济发展的重要支柱之一，在我国改革开放和中国特色的社 会主义现代化建设中发挥着不可估量的重要作用【l j 。 在中国国民经济强劲增长的背景下，中国的航空业已进入了快速发展时期， 目前中国航空业的发展是全球主要航空市场中增长最快的一个，中国的航空运输 总周转量和旅客周转量在国际民航组织缔约国中占据着举足轻重的位置。 美国波音公司预测，今后2 0 年世界航空运输业将以年均5 2 的速度高速增 长。其中亚太地区将是增长最快的地区之一，未来2 5 的世界航空运输量将集中 在亚洲。中国将是世界各主要市场中增长最快的国家，预计其年增速将达到7 6 ， 照此计算，剑2 0 2 0 年中国航空市场将成为仅次于美国的世界第二大航空市场【n j 。 ( c h i n ad a i l y ) ) 报道称，为满足国内强劲的空运需求，预计到2 0 1 5 年中国民 用客机的数量将增长一倍，最多达到5 0 0 0 架。中国民用航空局( c i v i la v i a t i o n 重庆大学硕士学位论文1 绪论 a d m i n i s t r a t i o no fc h i n a ，简称“民航局”) 局长李家祥表示，到2 0 15 年中国民航客 机总数预计将翻一番3 ，4 1 。 下图表明了2 0 0 6 至2 0 1 0 年间我国民航运输总周转量。 霸吨慧黑 图12 0 0 f r 2 ) 0 = 1 0 年民航运输总周转量 2 0 i - 1 62 0 口12 口 1 82 口o 2 01 口 图1 12 0 0 6 2 0 1 0 年民航运输总周转量 f i g1 1t o t a lt r a n s p o r t a t i o nt u r n o v e ro f c i v i la v i a t i o ni n2 0 0 6 - 2 0 1 0 如图1 1 所示，可以看出，肇“十二五”期间我国民航总运输周转量呈明显的 上升趋势，作为一种先进的交通运输方式，航空运输业已经成为了我国现代社会 经济发展的重要支柱之一，对我国的发展有着不可或缺的重要作用。 1 1 2 未来航空移动通信网络 伴随着航空业的飞速发展，空中通信的需求也愈来愈清晰。现代的航空通信 系统已经不仅限于用于满足空中交通管制方面的要求，而是在航空飞行过程中有 了更加细腻、人性化的通信需求。于是，未来航空移动通信网络这一概念便被提 出。 未来航空移动通信网是由以飞机、卫星、飞行器等作为空中节点的空地 通信系统。简单地说，上文所指的“空”是指以卫星( 飞机、飞行器等) 为中心 的天基【5 】系统，“地”是指以陆地( 岛屿等地面设施) 固定通信设备为中心的地基 系统，而未来航空移动通信网就是指由天基系统和地基系统所构成的“天地一体 化”系统，该系统是为了空管和各类航空用户提供高速宽带、安全可靠的通信服 务。 2 蝣 加 嘶 如 圬 5 0 重庆大学硕士学位论文1 绪论 图1 2 天地一体化系统 f i g1 2i n t e g r a t e ds y s t e mo f t e r r e s t r i a ln e t w o r ka n da e r o n a u t i c a la dh o en e t w o r k 航空移动通信指的是航空飞行中信息的交换和传输，其主要由两部分组成空 中交通管理( a i rt r a f f i cm a n a g e m e n t ，a t m ) 和民航旅客通信【6 j ( a i rp a s s a n g e r s c o m m u n i c a t i o n a p c ) 。 航空移动通信由飞机、飞艇等其他飞行物作为空中节点组成，与天基网和地 基网互联互通，目的是为空管及各类航空用户提供高速宽带和安全可靠的通信服 务。现代航空移动通信系统不仅要为a t m 系统提供服务，更主要的是为了满足航 空旅客的a p c 服务。 未来航空移动通信网是由飞机、飞艇等空中节点组成的空基系统，与天基系 统和地基系统构成的空天地体化系统【6 ，7 1 ，为空管和各类航空用户提供高速宽带 安全可靠的通信服务。在陆地上沿飞机航线建设覆盖半径为2 0 0 千米的地基基站， 形成地基接入网，当飞机在该陆地上空飞行时，直接与覆盖该航线的地基基站通 信。飞机在跨洋飞行时，如能连接到地基网，则直接连接，如不能，则飞机与飞 机之间白组织构成一个空基网。在空基网中有飞机能接入地基网，就直接接入地 基网，否则，就通过卫星构成的天基网中继接入地基网。图1 3 直观阐述了这一概 念。 重庆大学硕士学位论文1 绪论 滋。歹天基蕊 ， 髓1 一 滋”，7k 穴量剿 ， ， ， ， ， ， ，。篱一一一篓翁獬 ik 瀛71 氟黼。瓤一 、。盘。净，。飞一二。 陆地基站和 陆基网 海洋 图1 3 未来航空移动通信网 f i g1 3f u t u r en e t w o r ko fa v i a t i o nm o b i l ec o m m u n i c a t i o n 陆地基站 和陆基网 航空白组网是依靠民航飞机之间的相互通信构成的移动自组织网路，它通过 与地面站最靠近的民航飞机与地基网相连接，实现低成本的快速宽带数据传输。 在这方面，我国c 9 1 9 大型客机空天地一体化导航、监视与通信系统还处在研究阶 段，受到国家科研生产等多个部门的重视，且国外的相关研究工作也正在积极开 展 8 ，9 1 。 1 1 3 频谱资源的分配 为满足空中通信的需求，首先需要解决的就是如何解决有限频谱资源的竞争 使用问题，其中最主要的就是如何提高频谱利用率的问题。频谱在无线通信中是 稀缺的资源，随着新的无线电设备的涌现频谱资源日益紧张，如何有效使用有限 的频谱资源是研究频谱分配问题的关键【l 例。传统的频谱划分方式是一种基于静态 的静态频谱共享方式【1 1 1 ，其划分频谱效果并不理想，在很多时候频谱并没有被完 全、有效的利用，频谱利用率很低。 认知无线电技术是当今频谱共享的热门研究课题之一，作为一种智能无线通 信技术，认知无线电能够感知周围通信环境的变换进而做出处理，因此被广泛应 用到频谱共享中。目前国内外的研究人员已经提出了基于认知无线电的频谱分配 模型，并给出了相关的算法。实验证明，基于认知无线电频谱共享技术能根据频 谱需求做出调整，能有效地提高频谱的利用率，缓解频谱资源紧张问题【l2 | 。认知 无线电技术为如何在有限的频谱资源下提高频谱利用率开辟了新的思路和途径， 成为当今研究无线频谱分配的热点之一。 博弈论是在经济学中被广泛应用的理论，博弈的思想已经渗透到了现代生活 的各个方面，其中涉及到的纳什均衡的思想已经成为博弈方进行决策、寻找最优 4 叁 # 一鞠 ， 。fk 重庆大学硕士学位论文1 绪论 解的的理论依据，因此将博弈论的知识与认知无线电技术相结合来进行无线频谱 分配的方法为探索无线频谱共享问题提供了一种新的思维，对认识无线电技术的 发展及提高无线频谱利用率的研究有着推动作用。 1 2 课题研究的意义及来源 1 2 1 课题的意义 未来航空移动通信网是一种“空天地一体化”系统，目的是为空管及各类航 空用户提供高速、安全、可靠的通信服务。然而空中无线频谱资源是有限的，伴 随着无线电设备的增多，频谱资源更加显得稀少和珍贵。 航空旅客通信的目的是为飞行中的旅客提供电话、i n t e r n e t 等信息服务，按照 信号的传输方式可以大致分为两类。一种是地对空的直接覆盖，如a i r c e l l 宽带系 统，这种方法具有高带宽，低成本的优势，但却不支持跨洋飞行。另外一种是卫 星链路传送，如a e r o m o b i l e 和松下通过国际海事卫星组织( i n m a r s a t ) 提供的 s w i f t b r o a d b a n d 业务或s w i f t 6 4 业务实现飞行中电话和i n t e m e t 接入服务。卫星链 路的通信质量好、切换次数少，但是其时延相对较大、成本也相当高，此外卫星 信道资源是有限的，当面对较大的用户量时，必然会面临带宽不足的情况【l3 | 。因 此有限频谱的分配问题的研究就变得非常有现实意义! 认知无线电技术又被称为“新一代无线电技术”，它能够主动监测当前可用的 频谱资源，进而充分利用无线频谱资源。能否有效使用频谱资源、提高频谱使用 率的关键就是选取的频谱分配规则是否有效，到目前为止，国内外的研究人员已 经提出了很多基于认知无线电理论的频谱分配的模型，并给出了具体算法，但基 于其他理论的模型和算法仍然是十分具有学术价值的。 博弈论是在微观经济学中被广泛使用的理论，博弈的思想已经广泛应用到社 会生活中。博弈中的纳什均衡的存在，使得寻找最优解成为了可能，因此博弈论 为不同生活场景中的决策分析和决策选择提供了强有力的数学理论依据。针对无 线频谱分配这一问题，同样的，可以使用博弈论的方法对其进行数学分析，寻找 出占优的频谱分配策略。因此，可以考虑将博弈论的知识运用到频谱分配的方法 中，用博弈的方法对基于认知无线电的无线频谱分配方式进行建模、分析，探索 “占优”的频谱分配策略是具有重要意义的。 本文所涉及的研究课题主要依托以下两个科研课题：一是2 0 1 0 年民用飞机关 键技术预先研究课题民航客机移动通信宏蜂窝网络中继通信链路技术研究 ( 工信部装 2 0 1 0 3 0 7 号) ；二是国家自然科学基金项目“跨洋民用航空宽带移动通 信组网及关键技术研究”( 6 1 1 7 1 0 8 9 f 0 1 0 2 0 1 ) 项目。 重庆大学硕士学位论文1 绪论 1 2 2 国内外研究现状 伴随着信息全球化的发展，无线通信的业务量也是突飞猛增，其对无线频谱 的需求也是飞速增长，于此同时无线频谱资源却是有限且不可增的，因而频谱资 源显得更加的匮乏和稀缺。如何最大化这些有限的频谱资源的利用率是重要的研 究课题。传统的频谱分配方式是基于授权机制的静态分配方式，频谱仅由授权用 户使用，因而频谱利用率低下。而基于认识无线电的频谱分配方式是一种动态的 频谱分配方式，它能够在不影响授权用户使用的前提下智能地利用空闲频谱，实 现随时随地的高可靠性的通信，从而有效地提高频谱使用率，有力地缓解频谱资 源紧张的问题。 博弈论是经济学中应用最为广泛的理论之一，博弈中的纳什均衡思想及均衡 求解的过程被广泛应用到了各个领域。在通信领域，针对无线频谱资源分配这一 问题用博弈论的思想能很好地体现出来。基于博弈思想的频谱分配方式为提高无 线频谱的利用率提供了一种新的思路，基于博弈论的认识无线电技术在无线频谱 共享算法中得到了广泛的应用【1 4 , 1 5 j 。国内外的研究人员已经提出了很多基于博弈 论的认识无线电无线频谱分配模型，并给出了相应的算法。 基于认知无线电频谱共享技术能根据频谱需求做出调整，能有效地提高频谱 的利用率，缓解频谱资源紧张问题。由于博弈论研究就是研究竞争中的策略优化 问题，因此在多用户竞争频谱的分析中，基于博弈论的无线频谱分配方式是研究 热点。目前国内外的研究人员已经提出了基于博弈论的认知无线电频谱分配模型， 并给出了相关的算法。下面对基于博弈论的频谱分配算法研究的国内外研究现状 做一个简要的介绍。 为避免小区内或小区问的十扰，运用本地议价算法，在图论中的着色理论的 基础上c h e n 等人提出“预分配和本地议价”的动态频谱分配模型。该模型减小了 系统的复杂性，而且能够保证用户间的公平性、满足用户对频谱带宽的需求 1 6 1 。 运用博弈论中的拍卖知识，k l o e c k 等人提出了一种新的频谱分配模型，该模型综 合考虑了频谱定价、分配及计费体制，将三者合为一体，根据不同的网络需求分 别确定各自的目标函数，从而跟踪反应用户的动态特性，解决频谱共享问题【l 。 e t k i n 等人对博弈论中的非合作博弈模型做了深入研究，针对未授权频道分别 建立了一次博弈模型和重复博弈模型，对两种模型的效用进行比较，发现在重复 博弈中运用惩罚策略能够获得公平性和高效性【18 1 。c l e m e n s 等人用两人重复博弈来 对无线电用户之前的频谱竞争行为进行建模，通过遗传算法求得参与人的策略， 该模型运用分布式动态频谱共享算法，具有很好的系统性能【l9 | 。针对有多个次级 用户有频谱接入需求而仅有一个授权用户可提供频谱时，次级用户之间存在竞争， d u s i tn i y a t o 等人提出了基于c o u r n o t 博弈的频谱共享模型，给出了基于该模型的 6 重庆大学硕士学位论文1 绪论 静态博弈算法和动态博弈算法，实验仿真也表明该算法在公平性和稳定性方面有 着不错的效果。当存在多个授权用广而只有。个次级用户有频谱接入需求时，授 权用户之间出现竞争情况，d u s i t n i y a t o 等人综合考虑了多个授权用户问的差异性， 提出了基于于伯特兰德( b e r t r a n d ) 博弈的竞价模型，详细推导了该模型的均衡， 给出了它的动态分布式算法。同时针对竞争博弈中的低效率问题，文中还提出了 通过合作博弈来实现高效率的频谱共享【2 0 1 。 在国内，对基于博弈论的认知无线电频谱分配算法的研究也取得了一定的成 果。借助图论着色理论p e n g 和z h e n g 等人对认知无线电频谱共享问题进行建模， 提出了一种分布式的频谱分配算法，实验仿真结果表明该分布式的算法具有和集 中式算法相同的性能，且分布式算法在降低系统复杂性方面有一定优势【2 i ，2 2 1 。w a n g 和l i u 在图论着色模型的基础上提出了分布式贪婪算法、分布式公平算法及分布式 随机算法等三种频谱共享算法，实验表明这三种算法在提高频谱利用率、公平性 、降低系统复杂性和开销方面获得了较好的效剽2 3 1 。g u o 等人在w a n g 和l i u 算法 的基础上提出了快速信道调整算法，在保证系统吞吐量和公平性的前提下明显降 低了系统开销 2 4 , 2 5 】。 针对有多个次级用户具有频谱接入需求，却仅有一个授权用户可提供频谱的 情况，t i a n 等人提出了加权比例公平算法模型，实现了频谱共享的高效性和公平 性【2 6 , 2 7 。q i n 等人则考虑了频谱的差异性，提出了改进的b e r t r a n d 模型，给出了静 态博弈和动态博弈的算法，有效的改善了频谱利用率【2 8 1 。针对有多个次级用户有 频谱接入需求而仅有一个授权用户可提供频谱的情况，考虑到授权用户的收益收 到次级用户所请求宽带的影响，同时每个次级用户的收益也受到其他次级用户的 宽带请求的影响，综合考虑以上方面黄丽亚等人提出了改进的c o u r n o t 博弈的频谱 共享模型，该模型综合考虑了博弈双方之间的影响，获得了较好的系统效能【2 9 1 。 1 3 论文的主要工作及成果 在基于用户竞争的频谱共享算法中，基于博弈论的频谱共享方法是研究的热 点。传统的单次博弈的纳什均衡解不能很好的保证用户获得较高的收益，本论文 在首先对单时隙内用户的竞争行为作了分析，给出了单次博弈下的纳什均衡策略， 并证明在单次博弈下用户的支付收益并不能很好的得到保证。在这个分析基础上， 将n 个时隙中用户反复竞争频谱的情况用重复博弈模型建模，提出了基于最大吞 吐量准则和比例公平准则的频谱分配规则。为了避免在竞争频谱的过程中，用户 为了得到更多的接入机会而采用欺骗手段，文中对常用的触发惩罚策略和针锋相 对惩罚策略结合该博弈模型做了详细的探讨和分析，提出了只针对用户在欺骗时 刻进行严厉惩罚的策略，并给出了性能仿真。 重庆大学硕士学位论文1 绪论 1 4 论文章节安排 第一章主要是对论文的研究背景、课题的研究意义及相关技术的研究现状做 了介绍，并给出了本论文的结构安排。 第二章主要是对博弈论的知识做了详细的介绍。首先，详细地阐述了对博弈 论的概念及其标准表达式，之后介绍了博弈的分类、纳什均衡等其他基本概念。 最后，在本章结束时简要介绍了认知无线电的有关知识，并阐述了基于博弈论的 认知无线电的知识。 第三章着重介绍本次论文中使用的重复博弈的知识。本章首先给出了重复博 弈的概念，分别介绍了有限次重复博弈和无限次重复博弈，之后详细地讨论了重 复博弈中的信用问题，并针对重复博弈的信用机制介绍了相应的惩罚机制。 第四章详细阐述了基于重复博弈的频谱共享算法。针对n 个时隙用户反复竞 争频谱的情况运用重复博弈对其建模，给出其目标函数，分析何种策略选择能够 获得最大的收益，并基于此提出了相应的频谱分配规则。同时，为了抑制在重复 博弈中经常会出现的欺骗手段，提出了基于惩罚的约束机制对用户的诚实竞争进 行了保护。本章最后给出了模型的性能仿真结果。 第五章对本论文作了总结，并对博弈论应用在基于认知无线电技术的频谱共 享技术的未来研究方向进行了展望。 重庆大学硕士学位论文 2 博弈论的基本知识 2 博弈论的基本知识 本章针对博弈论的相关基本知识做了较全面的介绍，给出了博弈论的基本概 念，阐述了博弈论的生产和发展过程、博弈论的分类和标准表达式等。在本章中 给出了博弈论中各种均衡的分析和求解，介绍了几个博弈论的主要模型，旨在对 博弈论有个宏观上的认识，为本论文中用到的分析方法做好介绍、铺垫工作。 2 1 博弈论的基本概念 古语有云：世事如棋。观察对弈的情景，棋手在下棋时相互揣摩、相互牵制、 步步为营，下出的棋局可谓是精彩纷呈、变化多端。博弈论就是古老的象棋、围 棋等棋牌类游戏衍变而来的，其最初就是研究棋手在出棋时做出的策略选择中的 理性和逻辑分析过程。数学家从这些具体问题中抽象出策略分析过程，并建立完 备的逻辑框架、体系对其变化规律做研究。 博弈论一般是研究各博弈方面对某种局面时的对策选择或者相互之问的策略 竞争、对抗，因此在我国博弈论又被称为“对策论”，对应的博弈问题也被称为“对 策问题”。其实对策更多是指具体的应对方案，而博弈论所涉及的决策问题是指开 始至最终作出决策的整个对策选择过程p 。 2 1 1 博弈的产生及发展 博弈的思想很早就已经存在了，最早见于我国古代的孙子兵法一书，该 书可以说是最早的一部博弈论专著。其研究的象棋、桥牌、赌博涉及到的胜负问 题是博弈思想的雏形，只是当时对博弈局势的把握只停留在了经验上，并没有进 行横向的理论化发展。一般认为，2 0 世纪初期博弈论才正式作为一门学科进行发 展。 2 0 世纪2 0 年代博弈论还处于萌芽阶段，此时博弈论的研究对象主要是从古代 竞赛游戏中抽象出来的严格的“二人零和博弈”，在这段时间提出了博弈的扩展性 策略和博弈的混合策略的概念1 3 1 i 。1 9 2 8 年，冯诺依曼( v o nn e u m a n n ) 证明了博 弈论的基本原理，对博弈论的发展产成了重大影响。 2 0 世纪3 0 年代初步建立了博弈论这门学科。1 9 4 4 年，冯诺依曼和摩根斯坦 恩( m o r g e n s t e r n ) 合作出版了博弈论和经济行为( t h et h e o r yo fg a m e sa n d e c o n o m i cb e h a v i o r ) 一书，书中两人将二人博弈推广到n 人博弈，并将博弈论应 用于经济领域，首次展示了博弈论的研究成果及其框架，从而奠定了这一学科的 理论基础。冯诺依曼和摩根斯坦恩的这部巨著的出版标志着现代系统博弈理论的 初步形成。 9 重庆大学硕士学位论文2 博弈论的基本知识 2 0 世纪5 0 年代是博弈论的研究发展到了鼎盛阶段。纳什( n a s h ，1 9 5 0 ) 和夏 普里( s h a r p l y , 1 9 5 3 ) 分别提出了的“讨价还价”模型，g i l l i e s 和夏普里( 1 9 5 3 ) 提出了合作博弈中的“核”( c o r e ) 的概念等研究成果标志着合作博弈发展到了鼎 盛时期。同时，非合作博弈论也在这个时期开始创立。纳什在1 9 5 0 和1 9 5 1 年分 别发表了两篇关于非合作博弈的论文n 人博弈中的均衡点和非合作博弈， 首次提m 了“均衡”这一概念( 即后来的纳什均衡) ，证明了非合作博弈中均衡的 存在，改变了人们对市场竞争的认识。t u c k e r 于1 9 5 0 年定义了“囚徒困境( p r i s o n e r s d i l e m m a ) ”，它与纳什提出的均衡的研究一起为现代非合作博弈论奠定了基础，之 后的博弈论发展一般都是以纳什均衡作为主线进行研究的。 2 0 世纪6 0 年代博弈论的理论发展研究已经进入了比较成熟的阶段。1 9 6 5 年 泽尔腾( s e l t e n ) 在纳什均衡的概念上引申了动态分析，提出了“精炼纳什均衡” 的概念，定义了完全信息动态博弈的“子博弈完备纳什均衡”和不完全信息动态 博弈的“完备贝叶斯纳什均衡”。1 9 6 7 至1 9 6 8 年海萨尼( h a r s a n y i ) 将不完全信息 引入博弈论，提出了不完全信息静态博弈的“贝叶斯纳什均衡”【3 2 1 。这两位的研 究将纳什均衡进一步动态化，加入了不完全信息条件更加接近了实际情况。 在过去的几十年中博弈论已经发展成为一门较完善的学科，对其他学科的研 究也产生了很人影响【3 3 j 。在政治学、军事学及外交领域，选举策略、竞争问题、 战争起因、立法议程安排等重大事宜均采用博弈论进行分析。在经济学领域，博 弈论已是主流分析学科，已经被经济学家作为分析工具分析诸如公共经济、国际 贸易、工业管理等各类经济问题【34 | 。当人们的收益与其他人的行为具有相关性、 受他人的行为影响时，博弈论提供了这样一种方法帮助人们选择能够使自身收益 最大化的策略。这种方法的效果在有许多因素共存且彼此之间并不独立，决策的 结果之间均是相互影响、关联时会更加有价值。 2 1 2 博弈论的定义 博弈论，英文为g a m et h e o r y ，是研究决策主体的行为发生直接相互作用时候 的决策以及这种决策的均衡问题【35 | 。具体来讲，博弈是指某些个人或集体面对某 种情况时，在一定的约束条件下，根据自身所掌握的信息选择某种行为( 策略) 使得各自从中获得收益的过程。这种策略行为的选择可以是同时的，也可以是有 先后顺序的，可以是只进行一次的也可以是重复多次进行的。博弈论研究一个主 体( 一个人或企业) 的决策受到其他主体的选择的影响，并且反过来影响其他主 体的行为决策的过程，以及整个过程中的均衡问题。 由上述定义可知，对博弈过程进行研究的话应该包括参与人、行动、信息空 间、战略( 策略) 、支付( 收益) 、结果和均衡等几个方面。而其中参与人、战略 和支付又是一个博弈过程所需要具备的基本要素。其中参与人、行动( 空问) 、结 1 0 重庆大学硕士学位论文2 博弈论的基本知识 果是一个博弈进行的博弈规则，博弈的分析过程就是运用这些博弈规则对均衡进 行预测。下面给出这些概念的具体解释。 参与人( p l a y e r s ) 是博弈的参与方，又被称为局中人。参与人是一个博弈 过程中独立做出决策的主体，他通过选择不同的策略获得不同的收益，当然他的 目的是为了使自身获得最大的收益。参与人可以是真实存在的个人，也可以是某 个集体的代表。一般来讲用f = 1 ，2 ，n 来表示参与人。 行动( a c t i o n s ) 是指参与人在博弈中的决策行为，一般来讲用a i 表示第f 个 参与人的一个特定行动，用4 = a i 表示f 可选择的所有行动的集合。参与人的行 动可以是离散的行为或连续的行为。 信息( i n f o r m a t i o n ) 是指参与人在参与博弈的过程中所有与博弈有关的知 识。它包括参与人自身和其他参与人的特征及行动集合，以及其他相关的所有知 识。信息集是博弈论中描述参与人信息的集合，包含了一个参与人以及其他参与 人之前的行动的信息，是博弈论中的一个基本概念。 战略( s t r a t e g i e s ) 又称策略，是指博弈过程中参与人可以选择的全部行为 的集合。它规定了参与人在什么时候选择什么行动，它规定了参与人在进行决策 时如何对其他参与人的动作做出反应以及其可以选择的方法和做法等。一般用j 表 示参与人i 的战略，用s = s i 表示参与人f 所有可能选择的战略集合。用n 维向量 s = ( s ，s ，s 。) 表示一个战略组合，表示门个参与人选择的战略集合，其中s ：是 参与人i 所选择的战略。 支付( p a y o f f ) 又称之为收益( u t i l i t y ) ，是指在特定的战略组合下参与人 得到的效用水平或期望效用水平【3 5 】，是每个参与人真正关心的东西。一般地，用甜i 表示参与人i 的支付，则u = ( u ，“，u ) 为个参与人的支付组合。在博弈中，n n 某个参与人获得的收益不仅与自身所选择的策略有关系，其他参与人的策略选择 也会对该参与人的支付收益产生影响。用数学的语言来表达的话就是说，博弈中 某个参与人的支付收益是所有参与人策略选择的函数，“，的数学表达式可以用 u ，= “j ( s l ，s ，) 表示。 结果( o u t c o m e ) 是博弈分析时要考虑的所有的要素的集合。它包括博弈 分析时常涉及的均衡策略组合、均衡行动组合及均衡支付组合等。 均衡( e q u i l i b r i u m ) 是所有参与人的最优战略组合，也就是说该均衡策略 以外的任意战略组合都不能使得其支付收益大于该战略组合下的收益。一般地， 用s ：表示参与人i 在均衡情况下的最优战略，则记j ：= ( i ，一? ，一：) 为i 所有可能 的战略中使得u ，或e u ，】最大化的战略组合。一般用s 一，= ( s 1 ，叫s 书s 川，s n ) 表示参 与人f 之外的所有参与人的战略组合的集合向量。最优战略意味着 u 。( s ：，s 。) u ，( s ：，s 一，) ，v s ：s ：，均衡是指上式对所有的扛1 ，2 ，n 同时成立。 重庆大学硕士学位论文2 博弈论的基本知识 2 1 3 博弈论的标准表达式 任何一个博弈过程都可以用g = ( n ，a ， u 。) ) 来表示，其中g 表示某种特定的博 弈，包含参与人、策略和支付三个基本要素： n = 1 ，2 ，船j 表示每个具有决策权的参与人； a i 表示参与人i 在博弈中采取的策略，4 表示参与人i 的可选策略集合，用 a = a 1 a 2 4 表示所有参与人的战略空间； u ，= ( ，“，u 。) 表示一局博弈结束后参与人f 获得的收益。博弈中的收益 不仅与参与人自身选择的策略a i 有关，同时也受到其他参与人的策略选择a i 的影 响。一局博弈后，某参与人i 的支付函数并不是独立的，而是一个关于所有参与人 的策略选择的函数。 2 2 博弈论的分类 从不同的方向作为出发点，博弈可以划分为不同的类别。 1 ) 按照参与人采取行动的先后次序进行分类，博弈可划分为两大类：静态博 弈和动态博弈。静态博弈是指在博弈过程中参与人同时进行策略选择或采取行动， 或者参与人分别先后采取行动，但是后行动的参与人并不知道先行动的参与人的 行为或策略。动态博弈是指在博弈过程中，参与人的策略选择有先后顺序，而且 后采取行动的参与人能够观察到之前采取行动的参与人的行为。 2 ) 按照参与人对其他参与人的信息等公共知识的掌握程度进行分类，博弈可 以划分为完全信息博弈和不完全信息博弈，以及完美信息博弈和不完美信息博弈。 信息在博弈论中有着举足轻重的地位。在博弈过程中如果每位参与人对其他 参与人的特征、策略空间、支付函数等“公共知识”有着准确的信息，那么就称 之为完全信息博弈。如果只了解一部分信息则称为不完全信息博弈。 在动态博弈中，如参与人在决策时清楚之前所有参与人的决策信息或者说完 全了解之前博弈过程中自己的行为策略则称该参与人具有完美信息。如