（信号与信息处理专业论文）异构无线网络负载均衡算法研究.pdf

重庆邮电大学硕士论文 摘要 摘要 当前各种无线异构网络共存，不同无线接入网络在网络覆盖面积、业务能力、 使用成本上有较大的差异，且服务种类、速率等各不相同，这就必须对网络资源 进行优化控制，合理分配网络业务负载。同时，在城市等用户业务比较密集的通 信热点地区很容易造成新呼叫的阻塞概率及切换呼叫的掉线率的提高；相对而言， 非热点小区的资源利用率低，这就造成整个网络环境的资源分配不均匀。因此对 异构无线网络负载均衡的研究是非常必要的。 本文在泛在网络中异构无线网络融合与协同发展背景下，在博弈论和最优化 理论的基础上，主要从以下两个方面展开研究，概括如下： 首先，研究了基于非合作博弈的异构无线网络的负载均衡。将博弈论中的非 合作博弈与最优化理论相结合，考虑网络中所有用户的利益与网络的效用两个部 分，第一部分是用户利益最大化模型，最大化全网络用户利益；第二部分是网络 间带宽资源竞争的非合作博弈模型，通过网络之间的非协作博弈使网络根据接入 的用户数量来提供带宽与价格，运用迭代算法使其达到非合作博弈的稳定状态一 一纳什均衡，从而实现了带宽在网络与用户间的均衡分配。同时，还对纳什均衡 的存在性、唯一性，以及迭代算法的稳定性进行了证明。最终使各个网络中用户 的平均利益达到均衡状态，用户带宽进行合理分配，网络带宽得到充分应用，提 高网络带宽的利用率，异构无线网络达到负载均衡。 第二，研究了基于多目标优化的异构无线网络负载均衡算法。在博弈论的效 用函数的基础上，利用用户带宽进行两个优化目标的建立：一，全网络效用的最 大化；二，网络负载成本的最小化；而两个目标函数之间是相互矛盾的，最大化 全网络效用使用户接入带宽较大的网络，而最小化网络负载则是将用户接入带宽 较小的网络，为了使用户的利益达到优化，根据最优化理论中的多目标优化来建 立联合网络负载与全网络效用的多目标优化模型。文中通过关联矩阵法进行数量 化描述，用关联矩阵来表示网络与用户之间的对应关系，采用优化工具箱t o m l a b 求解0 1 规划问题，得到网络带宽的分配方案以及用户在网络中的接入情况，使带 宽优化分配，网络负载均衡。 关键词：异构无线网络，负载均衡，博弈论，纳什均衡，多目标优化 重庆邮电大学硕士论文a b s t r a c t a b s t r a c t n o w a d a y s ，w i r e l e s sa c c e s sn e t w o r k sa r ed i f f e r e n tf r o me a c ho t h e r i nn e t w o r k c o v e r a g ea r e a , t y p e so fs e r v i c e ，c o s t ，s p e e d ，e t c t h eb l o c k i n gp r o b a b i l i t yo fo r i g i n a t i n g c a l l sa n dt h ef o r c e dt e r m i n a t i o np r o b a b i l i t i e so fh a n d o f fc a l l sc a nb ep r o d u c e di nt h eh o t s p o to ft h ec i t yi nw h i c ht h es e r v i c ei sc o m p a c t ，t h en o n - h o ts p o ti so p p e r s i t e ，t h e nt h e r e s o u r c eu t i l i z a t i o no fe n t i r en e t w o r ke n v i r o n m e n t a lr e d u c e s oi ti sn e c e s s a r yt og e t r e s e a r c ho nl o a de q u i l i b r i u mi nh e t e r o g e n e o u sw i r e l e s sn e t w o r k i nt h eb a c k g r o u n do f i n t e g r a t i o na n dc o - o r d i n a t i o nf o rt h eh e t e r o g e n e o u sw i r e l e s s n e t w o r ko fu b i q u i t o u sn e t w o r k ，w es t a r tt h er e s e a r c hf r o mt h ef o l l o w i n gt w ow a y s b a s e do ng a m et h e o r ya n do p t i m i z a t i o nt h e o r y f i r s t ，i ti sa b o u tl o a db a l a n c i n gb a s e do nn o n c o o p e r a t i v eg a m ei nh e t e r o g e n e o u s w i r e l e s sn e t w o r k s c o m b i n e dn o n - c o o p e r a t i v eg a m eo fg a m et h e o r yw i t ho p t i m i z a t i o n t h e o r y , w er e s e a r c ht h ep r o f i to fu s e r sa n dt h eu t i l i t yo fn e t w o r k t h ef i r s tp a r ti st h e m o d e lo fm a x i m i z i n gt h ep r o f i to fu s e r sw h i c hi st om a x i m i z et h ep r o f i to fu s e r si nt h e w h o l en e t w o r k s ；t h es e c o n dp a r ti st h em o d e lo fn o n c o o p e r a t i v eg a m eb e t w e e n w i r e l e s sn e t w o r k sf o rb a n d w i d t h ，a n di tu s e st h ei t e r a t i v ea l g o r i t h mt oo b t a i nt h en a s h e q u i l i b r i u mw h i c hi st h es o l u t i o no fn o n - c o o p e r a t i v eg a m et od i s t r i b u t et h eb a n d w i t h p r o p e r l y i ta l s op r o v et h a tt h ee x i s t e n c e ，u n i q u e n e s sa n ds t a b i l i t yo fn a s he q u i l i b r i u m b a s e do nt h ea l g o r i t h mf o rl o a db a l a n c i n gw ec o u l dg e tt h el o a db a l a n c eo fn e t w o r k s ， i n c r e a s et h eb a n d w i d t hu t i l i z a t i o n s e c o n d ，i t i sa b o u tr e s e a r c ho fl o a d b a l a n c i n gb a s e d o nm u l t i - o b j e c t i v e o p t i m i z a t i o ni nh e t e r o g e n e o u sw i r e l e s sn e t w o r k b a s e do nt h et h eu t i l i t yf u n c t i o n , w e e s t a b l i s h e dt w oo p t i m i z a t i o no b j e c t i v e 谢t l lt h eb a n d w i d t ho fu s e r s ：f i r s t ，m a x i m i z a t i o n o ft h en e t w o r k - w i d eu t i l i t y ；s e c o n d ，m i n i m i z a t i o no ft h ec o s t ；b u tt h et w oo b j e c t i v e f u n c t i o ni sc o n t r a d i c t o r y , m a x i m i z i n gt h et h en e t w o r k - w i d eu t i l i t yw i l lm a k et h eu s e r g e tah i 曲b a n d w i d t h ，m i n i m i z i n gt h ec o s tw i l lm a k et h eu s e rg e tal o wb a n d w i d t h a n d t h e ni no r d e rt oo p t i m i z et h eg a i no fu s e r s ，w ep r o p o s e da j o i n to p t i m i z a t i o nm o d e lf o r b a n d w i d t ha l l o c a t i o na n dn e t w o r kl o a db a l a n c i n g ，w h i c hi st h em o d e lo f m u l t i o b j e c t i v e o p t i m i z a t i o n o fo p t i m i z a t i o nt h e o r yw h i c hc o n t a i n st h en e t w o r k u t i l i t ya n dc o s t f u n c t i o n s w ec a l c u l a t et h ea l g o r i t h mw i t hr e l a t i v em a t r i x ，w h i c hc o u l ds h o wt h e r e l a t i o n s h i pb e t w e e nu s e ra n dn e t w o r k t h r o u g ht h ea s s o c i a t i o nm a t r i xt h em o d e lc o u l d g e tt h es c h e m eo fb a n d w i d t hm a k i n gh e t e r o g e n e o u sw i r e l e s sn e t w o r k sb a l a n c e d a n d 重庆邮电奎堂堡主笙銮 垒! 坚! - - _ _ _ _ _ - - - _ _ _ _ - _ _ - _ _ - _ _ _ - - - _ _ - _ _ _ _ _ _ _ _ l - - - _ _ _ l i _ _ - _ _ - _ _ _ _ - _ - _ _ - _ 一一 w es o l v et h ei n t e g e rp l a n n i n gp r o b l e mw i t ht o m l a bw h i c hi sat o o l b o xu s e dt o o p t i m i z i n g ，t h er e s u l to f j o i n to p t i m i z a t i o nm o d e li sd i s t r i b u t e da m o n g t h ep r o p o s e dc o s t f u n c t i o n sa n dt h en e t w o r ku t i l i t y ；i tc a no p t i m i z et h ea l l o c a t i o no fb a n d w i d t ht oa c h i e v e l o a db a l a n c i n go fn e t w o r k s k e yw o r d s ：h e t e r o g e n e o u sw i r e l e s sn e t w o r k ；l o a db a l a n c i n g ；g a m e t h e o r y ；n a s h e q u i l i b r i u m ；m u l t i - o b j e c t i v eo p t i m i z a t i o n i i i 重庆邮电大学硕士论文 第一章绪论 1 1引言 第一章绪论 现今，全球信息产业处于重大发展变革时期，以无所不在、无所不能、无所 不包为特征，实现在任何时间( a n y t i m e ) 、任何地点( a n y w h e r e ) 、任何人( a n y o n e ) 、 任何物( a n y t h i n g ) 都能顺畅地通信( 即“4 a 通信) 的泛在网络( u b i q u i t o u sn e t w o r k ) 为目的的发展趋势和策略成为研究热点。而目前在泛在网络架构下，现有的三网 融合正在加速推进，以建立“无所不包”的网络基础。 但是泛在网络并不是一个全新的网络，而是以不断融合新的网络，使其成为 泛在网络的子网，如此源源不断地向泛在网络注入新的业务和应用，这个过程就 是各种异构网络之间的融合与协同的过程。因此，在面向未来丰富的业务扩展过 程之中，网络演变下各种体系架构的融合和协同变得越发重要。并且聂延波在“环 境感知泛在网络未来信息通讯的发展趋势”一文中总结了环境感知泛在网络 的特征：泛在性、异构性、协同性、融合性等。 在异构融合网络的系统中，用户可在多模终端接口的支持下，通过统一综合 的网络平台，进行信息通信，任何人、任何时候、任何地点都可以享受无缝的通 信服务。在这个体系下衍生的网络融合的范畴很广，如广义的“三网融合”指的 是电信网、互联网和广电网的融合，它主要是基于高层业务的融合，表现为网络 层上的互联互通，业务层上的互相渗透，应用层上使用统一的通信协议。而本文 所讨论的异构无线网络的融合指狭义的无线通信网络的融合，所涉及到的典型无 线网络有蜂窝网络( 女1 2 g 、3 g ) 、无线局域n ( w l a n ) 等。 在异构网络的融合与协同中，为了使各个网络的资源实现共享，必须有效的 管理网络的有限资源，提高整体网络无线资源的利用率，扩大系统容量，为用户 提供更多的服务类型以及更好的服务质量，具体原因如下。 首先，在异构网络中，用户基于统一综合的网络平台，通过不同的终端进行 信息通信时，享有网络系统平台提供的高速率、低时延多媒体服务，并可以进行 网络间的无缝切换。但是网络中巨大的业务量及具有不同q o s 要求的业务需求使各 种不同的无线网络与标准相继出现。并且在当前各种异构无线网络共存的环境中， 不同无线接入网络在网络覆盖面积、业务能力、使用成本上有较大的差异，服务 种类、速率等各不相同，这就必须进行优化控制，合理分配网络业务负载。 其次，在城市等用户业务比较密集的地区，容易形成通信热点，小区内部流 重庆邮电大学硕士论文第一章绪论 量大，这就很容易造成小区内新呼叫的阻塞概率以及切换呼叫的掉线概率的提高； 相对而言，非热点小区的流量却又比较少，用户终端资源分配不均匀，这就造成 整个异构系统的资源利用率很低。因此，可以通过引入负载均衡( 1 0 a db a l a n c i n g ) 机 制将较重负载网络中的部分流量转移到其它流量较轻的网络中去，从而达到一种 均衡分布的状态。 异构无线网络所面临的挑战是：高效率的使用各种无线接入网络的资源【l 】，解 决网络拥塞以及性能下降，使网络间资源能够充分的利用，网络之间互通、融合。 利用异构无线网络的负载均衡机制有助于提高异构网络系统无线资源的整体利用 率，增加网络容量，扩展网络覆盖范围和避免业务量过于集中导致的网络超载， 为用户提供多样化服务及更好的服务质量，促进异构网络的融合。 1 2 异构网络融合 在移动通信发展的多年以来，许多种不同的无线传输技术陆续出现，如p h s 、 g s m 、c d m a 2 0 0 0 、w c d m a 、t d s c d m l a 、w i m a x 、8 0 2 1 l a b g 、u w b 、l m d s 、 d v b s t h 、m m d s 、z i g b e e 、i 江d 等，而目前各国又正在不断的研究新的s u p e r 3 g 、 b e y o n d 3 g 和4 g 的传输技术。显然，未来网络的异构性更加充分。其实不仅在无线 接入方面具有这样的趋势，在终端技术、网络技术和业务平台技术方面，异构化【2 j 、 多样化、泛在化【3 1 的趋势也同样引人注目 4 1 。 泛在网络的发展为异构网络的融合与协同提供了重要的基础。2 0 0 8 年底，m m 公司在全球范围内首次提出“智慧地球( s m a r te a r t h ) ”概念，主要体现在3 个i ( 3 i ) ： 更透彻的感知( i n s t r u m e n t e d ) ，更广泛的互联互通( i n t e r c o n n e c t e d ) ，更深入的智能化 ( i n t e l l i g e n t ) 。2 0 0 9 年6 月欧盟的“物联网行动计划”、日本的“u j a p a n ”计划、韩 国的u k o r e a 的核心计划、新加坡的“下一代i h u b 计划、土耳其u n s 计划以及中 国的建立“感知中国 中心。 异构网络( h e t e r o g e n e o u sn e t w o r k ) 是一种类型的网络，它由不同的设备组成， 大部分情况下运行在不同的协议上以支持不同的功能或应用。各种异构网络将经 历从隔离到互通，从互通到协同的演进。而通过网络间的协同，将分离的局部的 优势能力与资源进行有序的整合，从而最终使系统更加智能化。 近年来，就异构网络融合问题当前已做了不少的研究，并且提出了不同的解 决方案。欧盟信息社会技术( i s t ) 从框架结构f p ( f r a m e w o r kp r o j e e t ) 5 开始，逐渐展 开异构网络领域的技术研究，有w i n e 、w i n d f l e x 、t i m s t 、s c o u t 等项目。 在i s t f p 研究阶段，欧盟专注于异构网络体系的完整构建和融合，主要开展的研究 项目有a n ( a m b i e n tn e t w o r k ) ，w i n n e r ( w i r e l e s sw o r l d i n i t i a t i v en e wr a d i o ) 。欧洲 2 重庆邮电大学硕士论文 第一章绪论 的d a i d a l o s 项目对3 g 和w l a n 融合网络的研究为异构无线网络的融合提供了研究 实例，其主要目标是建立一个基于全d 架构的综合网络，实现多种无线技术和3 g 技术的有效融合，建立以用户为中心、综合管理的骨干移动网络。日本的国立项 目m i r a i 是用于各种不同的无线通信系统之间的融合。b r a i n 提出了w l a n 与通 用移动通信系统( u m t s ) 融合的开放体系结构；d r i v e 项目研究了蜂窝网络和广播 网的融合问题；n e g l a s s 则从用户的角度研究了w l a n 与u m t s 的融合；用于异 构网络管理的模块被m o n a s i d r e 首次定义，m o b y d i c k 重点探讨了在i p v 6 网络 体系下的移动网络和w l a n 的融合问题。近来提出的环境感知网络和无线网状网 络m e s h 也为多种异构网络融合的实现提供了更为广阔的研究空间。 1 3异构无线网络联合资源管理 异构网络的融合可极大地提升单个网络的性能，在支持传统业务的同时也为 引入新的服务创造了条件，这种技术已经成为支持异构互连和协同应用的新一代 无线移动网络的热点技术。如3 g 网络和w l a n 的融合、t d s c d m a 和w i m a x 的 融合都是目前无线异构网络融合的研究热点。 当前，国内外对异构网络融合的关键技术研究主要集中在以下几个方面【l j ：异 构网络的互连；异构无线网络的联合资源管理【5 】；异构无线网络的服务质量( q o s ) 研究；异构网络终端的可重配置性；此外，异构无线网络的移动性管理，垂直切 换技术，异构网络的鉴权、计费、认证( 删、安全等问题也是当前的研究热点。 本文主要针对异构无线网络联合资源管理的负载均衡进行研究。由文献【1 6 】 7 【8 】分析，在研究网络间负载均衡技术时，还涉及异构网络垂直切换、网络选择、 带宽分配、接入控制等相关内容。 网络负载均衡。建立在现有网络结构之上的负载均衡机制，提供了一种廉 价有效透明的方法来扩展网络设备和服务器的带宽、增加吞吐量、加强网络数据 处理能力、提高网络的灵活性和可用性。当前网络结构可分为同构网络和异构网 络，异构网络在前面已经提到，而同构网络( h o m o g e n e o u sn e t w o r k ) 指环境中的网 络部件是由同一个供应商供应的或者是兼容设备，它们运行在同一个操作系统或 者是网络操作系统下p j 。 在同构网络系统中，一般的负载均衡算法流程【l 】为：首先周期性对网络各个小 区进行负载测量，若某小区超载，系统给出备选小区的函数值( 这个函数值的参 量包括负载大小、信噪比、q o s 参数等) ，将这些函数值从大到小排列，按照顺序 逐个选择用户和对应的网络，直到网络负载低于特定的门限值，重复执行这些操 作可以使小区间的负载趋于一种平衡状态。此外，k y u l a os o n 提出了一种负载转 3 重庆邮电大学硕士论文 第一章绪论 移的方法，联合优化部分频率重用( p a r t i a lf r e q u e n c yr e u s e ) 和负载均衡来解决小区 内干扰和不均匀分配引起的低吞吐量问趔1 0 】。文献将小区的频带进行划分，使用 户通过在不同的频带以及在不同小区之间的切换来使自己的期望速率达到最大， 以此来调节各个小区的网络负载。 异构网络负载均衡是指多个网络或者多个系统中负载较重的一方将部分负载 转移到另一方中去，达到一种均匀分布的状态。异构无线接入网络中，通过动态 负载管理使网络间负载保持均匀分布，从而提高整体网络无线资源的利用率，扩 大系统容量。针对不同网络用户带宽分配的不同方式，文献 1 1 根据各个网络间负 载的公平性来对不同网络间的负载进行平衡，使不同网络在某种形式上进行了融 合以及互通，网络负载达到均衡。在蜂窝网络和w l a n 中，文献 1 2 】采用一个两 阶段的控制策略来达到负载均衡，其中呼叫分配用于用户进入阶段时提供用户质 量保障；动态垂直切换用于流量服务阶段以最小化用户性能差异，实现对网络资 源进行接入控制以及垂直切换的管理，实现负载均衡。文献 1 3 】将s t a c k d b e r g 博弈 的基本理论和模型应用于多主接入网络的负载均衡问题中，给出了一种基于 s t a c k e l b e r g 博弈理论的多主接入网络带宽分配模型。 异构网络垂直切换。网络间切换技术分为两种：水平切换和垂直切换，移 动台在相同系统的基站( 扇区、信道) 之间的切换称为水平切换，而移动台在不 同系统的基站( 扇区、信道) 之间的切换就称为垂直切换。而垂直切换又分为松 耦合和紧耦合，松耦合与紧耦合之间物理耦合方式、通信方式等有所不同。 在w m a n ，蜂窝网络、w l a n 还有a dh o e 网络组成的异构网络环境中，文 献 1 l 】对两种耦合方式都进行了讨论，为了进一步达到异构无线网络的无缝集成， a dh o c 模式被应用到3 4 g 无线数据网络、v a n e t s ，以及i e e e8 0 2 1 1w l a n s 中， 通过路由选择算法，将数据包传向最恰当的链接连接点以最大化集体电池寿命， 保持负载均衡，最终达到切换的目的。文献 1 4 】是在l t e 和w i m a x 两个异构网络 组成的系统中提出了垂直切换算法- d t f h 算法。文献 8 】在异构网络中提出了 一种基于多因素综合判决的异构无线网络垂直切换算法，综合考虑了异构网络负 载、接收信号强度、移动速度和网络成本多种因素，利用模糊多目标判决方法进 行切换决策的选择。文献 1 5 1 在蜂窝网与无线局域网共存的异构无线网络中，综合 考虑移动用户的电池寿命、花费以及网络负载等因素进行切换判决，为移动用户 选择合适的目标网络进行切换，使整个网络资源得到合理利用。 接入网络选择。在异构网络中，用户如果要接入到网络中去，需要根据当 前自身的需求以及网络的状况，对接入网络进行选择，使用户能够满足q o s 需求。 文献 1 6 】在异构无线网络中提出了一种基于效用函数和博弈论的网络选择方案 u g t 来最大化呼叫数量，最小化切换发生率的目标，完成用户的q o s 需求。在集 4 重庆邮电大学硕士论文 第一章绪论 成网络中，装置了异构网络接e l 的的移动用户可以接入所有可能的网络，在此基 础上文献 1 7 】从系统的角度提出了一个基于成本函数的网络选择策略( c f n s ) ，并同 时考虑用户的需求。文献 1 8 】利用进化博弈理论研究了异构无线网络中网络选择的 动态性。不同服务区的用户组之间为了共享无线接入的网络中的有限带宽数量而 进行竞争，这个竞争就形成了一个动态进化博弈，进化均衡点就是博弈的解决方 法，即网络选择的最佳方案。 异构网络带宽分配。异构网络带宽分配主要指将网络带宽分配给用户而不 中断链接，从而最优化带宽性能的过程。在这个方面，n i y a t o 使用博弈论解决带 宽分配的问题，文献 1 9 提出了基于b a n k r u p t c yg a m e ( 一种n 人协作博弈的特殊 类型) 的带宽分配以及接入控制算法，使各种无线接入网络形成联盟为新的连接 提供带宽。文献 2 0 】是基于合作博弈纳什商定解的带宽分配框架，它不仅可以 向用户提供整个系统帕累托优化的速率值，还可以保持博弈准则的公平。文献 2 1 在w l a n 和w m a n 中，在垂直切换技术的基础上提出一种减少不必要切换的带 宽分配算法，使系统能够获得更高的容量，并且扩大i e e e8 0 2 1 1 网络的覆盖范围。 网络接入控制。网络的接入控制体现的是网络服务质量的过程，针对用户 的不同带宽请求，接入控制用于决定如何分配带宽与时延，因此需要在用户终端 与网络中设计合适的接入控制方案来控制进入网络的通信流量。如果要将消息通 过网络进行安全传输，首先需要请求一个连接，这个连接包括通知网络有关消息 的特征以及q o s 要求，并将信息储存在流量合同中。网络根据自身情况判断当前 是否有足够可用的资源，再决定是否接入这个连接。当大量连接共享一条链路( 如 语音通信) 时，如果连接数量大量增加以致影响当前所有连接，使其崩溃时，接 入控制起着重要作用。文献 2 2 提出一个基于用户优先机制的集成价格与接入控制 的方案，并且为了缓和拥塞，价格可以根据当前网络状况随时调整。文献【6 】利用 非协作博弈得到各种不同接入网络提供给新连接的带宽大小，并利用接入控制来 限制在线连接的数量，使不同类型连接的q o s 性能保持在一定层次上。 上述研究方案针对异构网络资源分配问题取得了不少研究成果，然而，由于 当前各种无线网络共存，无线网络技术并不相同，且不兼容，因此还有许多问题 尚待进一步深入研究，包括： 将经济学中的博弈论引入异构无线网络的资源分配问题，它可以为其提供 一个良好的分析模型，参与博弈的终端和网络通过使用不同的网络策略( 或策略组 合) 优化各自的目标函数，使资源分配达到均衡解。针对当前异构网络的资源利用 率低，可以在利用博弈论解决资源分配问题的基础上，从提高网络带宽利用率的 基础上进行研究。 在异构网络环境蜂窝网络和w l a n 网络中的网络资源分配问题是近 5 重庆邮电大学硕士论文 第一章绪论 几年的热点问题，当前对他们的融合，垂直切换，网络选择，负载均衡等有较深 入的研究。但是目前的研究主要集中在部分用户( 如切换用户、新连接用户等) 的情况，针对网络中用户移动性引起的负载变化情况并没有太多研究。 以上的问题都可以通过数学语言进行描述，即建立数学模型。根据博弈论在 解决网络资源分配问题上的优势，以及优化理论在当前资源分配上的发展，本文 主要采用博弈论和优化理论对异构无线网络负载均衡进行研究。 1 4 主要研究内容和结构 无线通信的形式种类较多并且各具特点，但能够为用户提供一个高带宽、广 覆盖以及综合了语音、数据和各种多媒体业务的综合网络却没有一种单一的无线 通信方式可以实现。因此，未来的通信网络体系必然是一个异构型的结构。本课 题主要以重庆市教委研究项目“基于m u l t i a g e n t 的泛在网络建模研究( k j 0 8 0 5 2 2 ) 为依托，并根据已发表或录用的论文整理而成。 本学位论文共分五章，主要章节安排如下： 第一章介绍了异构无线网络的相关研究背景、异构无线网络融合的研究现状 以及在泛在网络中的重要作用，重点研究了异构无线网络中资源分配的当前发展 情况。 第二章介绍相关的理论原理，博弈论和最优化理论。介绍博弈论的基本内容， 重点介绍了非合作博弈的概念、分类情况，纳什均衡的相关理论；针对最优化理 论，主要介绍了整数规划中的0 1 规划，以及多目标规划的相关理论。这一章作为 基础理论的介绍具有非常重要的作用。 第三章主要根据博弈论中的非合作博弈，考虑网络中所有用户的利益与网络 效用两个部分，建立用户利益最大化模型与网络间带宽资源竞争的非合作博弈模 型，通过网络之间的非协作博弈使网络根据接入用户的数量来提供带宽与价格， 通过运用迭代算法使其达到纳什均衡状态，从而实现了网络负载均衡分配。 第四章在最优化理论的基础上，结合效用函数设计异构无线网络中基于多目 标优化的网络负载均衡的网络带宽分配方案，对全网络效用与负载成本进行联合 优化。并利用关联矩阵来表示网络与用户之间的对应关系，采用优化工具箱 t o m l a b 对整数规划的问题来进行求解。最后通过仿真证明了联合优化算法可以 使带宽优化分配，网络负载均衡。 第五章主要对论文的工作进行了大致的总结，并对后续的研究方向进行探讨。 6 重庆邮电大学硕士论文第二章博弈论与最优化理论基础 2 1引言 第二章博弈论与最优化理论基础 由于当前的无线网络是各种无线接入技术、各种类型业务并存与融合的异构 型混合网络。在这个异构网络环境中，各个网络以及网络间的用户之间为达到负 载均衡，获得更多的网络资源相互合作相互竞争。为了使网络资源在用户间得到 合理、优化分配，本文主要采用博弈论以及最优化理论来设计相关算法进行解决。 博弈论研究主体之间相互行为，关注冲突与合作问题，在政治学、公共政策、 犯罪学、生物学、计算机科学、外交、国际关系、军事、等领域都得到了广泛应 用，并产生了重要影响。它为异构网络中网络与用户间的竞争提供了很好的分析 平台【3 0 1 。最优化方法【删主要运用数学方法研究各种系统的优化途径及方案，它的 目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案， 发挥和提高系统的性能及效益，最终达到系统的最优目标。利用最优化理论解决 资源的分配问题是当今研究的热点，相关理论以及技术的研究比较成熟，在各个 领域发挥着越来越重要的作用。 本章主要对博弈论和最优化理论的基本原理进行简单的介绍，使读者对博弈 论和最优化理论有一个基本的认识，为下文利用博弈论和最优化理论研究异构无 线网络中的负载均衡算法做基础。 2 2 博弈论基础 博弈论来自英文g a m et h e o r y ，又称对策论1 2 3 j 。 博弈论思想古已有之，我国古代的孙子兵法就不仅是一部军事著作，而 且可以算是最早的一部博弈论著作，但博弈论真正作为一种理论研究则始于2 0 世 纪2 0 年代。1 9 2 8 年，冯诺依曼证明了博弈论的基本原理，从而宣告了博弈论的 正式诞生。而1 9 4 4 年出版的由科学家冯诺伊曼和经济学家奥斯卡库根斯坦恩 合著的博弈与经济行为的理论奠定了博弈论的基础。奥斯卡摩根斯坦思和 冯诺伊曼认为经济学所研究的对象更接近于一场游戏中的参与者，相互之间预 期对方的行动；因此，观察、描述研究对象就需要一系列新的数学工具，他们将 这一套新的数学工具命名为博弈论。“博弈论”这个名词虽然提出来了，但却找 不到发展的突破方向。直到1 9 5 1 年纳什提出了“纳什均衡 的概念，博弈论才找 到正确的方向，并取得了长足的发展，为博弈论的一般化奠定了坚实的基础，并 7 重庆邮电大学硕士论文 第二章博弈论与最优化理论基础 开始运用于经济学、政治科学和心理学等其他领域。到了2 0 世纪7 0 年代，博弈 论又被用于生物学和计算机科学，逐渐发展形成一个完整的体系，并在经济学中 渐渐取得主流地位。1 9 9 4 年经济学诺贝尔奖授予了三位对博弈论发展作出贡献的 学者美国伯克利加利福尼亚大学的约翰海萨尼( j n a r s a n y i ) 、普林斯顿大学约 翰纳什( j n a s a ) 和德国波恩大学的赖因哈德泽尔滕( r e i n h a r ds e k e n ) ，这不仅表现 出博弈论在理论和实践中的成就，也揭示了博弈论在未来的理论研究和应用中的 广阔前景，确认了博弈论对人类思想的贡献【2 引。 2 2 1 博弈论概述 按照现代汉语词典的解降，“博弈 就是指丰富多彩的对抗性游戏；而 在英语中，博弈( g a m e ) 最早出现在博弈与经济行为的理论书中；但是他们所 表达的意思都是一样的。但是关于博弈论确切的定义，至今无统一的结论【2 3 1 。 约翰海萨尼( j n a r s a n y i ，1 9 9 4 年诺贝尔奖获得者) 对博弈论的概念论述： 博弈论是关于策略相互作用的理论。即认为它是关于社会局势中理性行为的理论， 每个局中人对自己行动的选择必须以他对其他局中人将如何反应的判断为基础。 罗伯特约翰奥曼( r o b e r tj o h na u m a n n ，2 0 0 5 年诺贝尔奖获得者) 将博 弈论称为“相互有影响的决策论 。 国外著名教材博弈论基础( 罗伯特吉本斯著) 认为：博弈论是研究多 人决策问题的理论。 文献 2 4 】认为博弈是指利益存在冲突的决策主体( 个人、企业、政党、集团、 国家等) 在相互对抗( 或合作) 中，对抗双方( 或多方) 相互依存的一系列策略和行动 的过程集合，其中：首先，博弈中的参与者各自追求的利益具有冲突性；其次， 博弈是一个过程集合；最后，博弈的一个本质特征就是策略的相互依存性。 而国外不少著名教材，如博弈论( f u n d e n b e g 和t i r o l e 合著) ，则未给出博 弈论的定义。可见，要给出博弈论完整准确的定义是困难的。博弈论研究的范畴 是多方面的，因而难以给出一个包罗一切的定义，只能在对博弈论的学习过程中 去体会它。但从上面各种表述，可以将博弈论理解为竞争环境下的多人决策理论， 并从这个角度进行学习和研究。 2 2 2 非合作博弈 根据在博弈过程中参与者之间能否达成一个具有约束力的协议( b i n d i n g a g r c e m e n t ) ，博弈论可以划分为合作博弈( c o o p e r a t i v eg a m e ) 利眙作博弈( n o n e o o p e r a t - i v eg a m e ) ，合作博弈以参与者群的可能联合行动集合为基本元素；非合作博弈以 8 重庆邮电大学硕士论文第二章博弈论与最优化理论基础 单个参与者的可能行动集合为基本元素【2 5 1 。合作博弈与非合作博弈的区别之处在 于：合作博弈集中讨论哪个参与者群而不是哪个单个参与者能做什么，它不考虑 参与者群内部作用的具体细节。目前经济学家所谈的博弈论一般是指非合作博弈， 因为合作博弈论比非合作博弈论复杂，在理论上的成熟度远远不如非合作博弈论， 下面主要对非合作博弈进行大致介绍。 非合作博弈【2 5 1 ，指参加博弈的局中人之间相互不合作，既不允许在博弈过程 中订立攻守同盟、互相传递信息，也不允许相互之间有强制性的约定，还不允许 博弈后对结果进行交换、相互照顾。每个局中人在考虑其他局中人的策略及策略 的可能性后，独立地选择策略，争取对自己最好的结果。非合作博弈是一种参与 者不可能达成具有约束力的协议的博弈类型，这是一种具有互不相容的情形。非 合作博弈主要研究人们在利益相互影响的局势中如何选决策使自己的收益最大， 即策略选择问题。 根据参与者行动的先后顺序和参与者对有关其他参与者的特征、策略空间及 支付函数的了解程度，有学者将非合作博弈划分为4 种基本形式，见表2 1 。 表2 1 非合作博弈的基本划分 完全信息非完全信息 静态完全信息静态博弈非完全信息静态博弈 ( 纳什均衡)( 贝叶斯均衡) 动态完全信息动态博弈非完全信息动态博弈 ( 子博弈精炼均衡)( 序列均衡) 首先，按照参与人对其他参与人的了解程度分为完全信息博弈和不完全信息 博弈。完全信息博弈是指在博弈过程中，每一位参与人对其他参与人的特征、策 略空间及收益函数有准确的信息。不完全信息博弈是指如果参与人对其他参与人 的特征、策略空间及收益函数信息了解的不够准确、或者不是对所有参与人的特 征、策略空间及收益函数都有准确的信息，在这种情况下进行的博弈就是不完全 信息博弈；在非合作博弈中，若每个局中人同时独立地采取自己策略，或行动时 间有先后顺序与同时行动的结果是相同的，并且只进行一次，这样的博弈称为静 态博弈，又称为一次博弈；而动态博弈行动有先后顺序，不同的参与人在不同时 点行动，先行动者的选择影响后行动者的选择空间，后行动者可以观察到先行动 者做了什么选择【23 i 。 2 2 3 非合作博弈构成要素 博弈论的基本构成要素包括：参与者( p l a y 神、行动、信息、策略( s t r a t e g i e s ) 、 9 重庆邮电大学硕士论文第二章博弈论与最优化理论基础 收益( p a y o f f ) 、结果和均衡( e q u i l i b r i u m ) 。但是非合作博弈主要包括以下几个构成要 烈2 5 】： 参与者( p l a y e r ) 。指一个博弈中的决策主体，在一场竞赛或博弈中，每一个 有决策权的参与者成为一个局中人。只有两个局中人的博弈现象称为“两人博弈 ， 而多于两个局中人的博弈称为“多人博弈 。 策略( s t r a t e g i e s ) 。指参与者在给定信息集情况下的行动规则。因为信息集 包含了参与者对其他参与者以前的认知，策略指导该参与者如何对其他参与者的 行动作出反应，因此策略是参与者的“相机行动方案 ( c o n t i n g e n ta c t i o np l a n ) 。 如果一个策略规定参与者在每一个给定的信息情况下只选择一种特定的行动，则 该策略称为纯策略( p u r es t r a t e g i e s ) ；如果一个策略规定参与者在给定信息情况下以 某种概率分布随机选择不同的行动，则该策略称为混合策略( m i x e ds t r a t e g i e s ) 。 用j ，表示第i 个参与者的一个特定策略，墨= s ，) 代表第i 个参与者的所有可选 择的策略集合。n 维向量s = s ，s ，s 。) 成为一个策略组合，其中墨是第i 个参与 者选择的策略。博弈论规定，作为一种行动规则，策略必须是完备的，亦即策略 必须包括参与者在每一种可想象到的情况下的行动选择。 收益( p a y o f f ) ，又叫支付。指在一个特定策略组合下参与者得到的确定效用 水平或期望效用水平。博弈结束时每个局中人的“支付 是全体局中人所取定的 一组策略的函数，通常称为支付( p a y o f f ) 函数，用u ，表示第f 个参与者的支付， u = 伽，“，u 。) 为n 个参与者的支付组合。 均衡( e q u i l i b r i u m ) 。均衡是平衡的意思，在经济学中，均衡意即相关量处 于稳定值。即指所有参与者的最优策略组合，一般记为矿= “ ，s ，s 。木) 。墨 是第f 个参与者在均衡情况下的最优策略，是参与者i 的所有可能策略中使u ；或眈； 最大化的策略。 2 2 4 纳什均衡 纳什均衡( n a s he q u i l i b r i u m ) 是由约翰纳什( j o h nn a s h ) 定义的均衡点 ( e q u i l i b r i u mp o i n t s ) ，纳什均衡概念是约翰纳什( j o h nn a s h ) 于1 9 4 9 年1 1 月，在他 未公开发表的博士学位论文中首先提出的。1 9 5 0 年纳什正式发表了题为 ( e q u i l i b r i u mp o i