（通信与信息系统专业论文）基于经济理论的互联网资源管理研究.pdf

北京邮电大学博士论文 中文摘要 中文摘要 随着i n t e r n e t 和无线网络技术的逐渐融合，将经济学模型和博弈理论应用到网 络资源分配是研究的一个热点。具体而言，使用微观经济学的概念研究的问题包 括：流量拥塞控制、路由、接纳控制、调度、网络设计和资源计费等。现在，大 量的具有异构需求的用户访问计算机系统，因此有效的服务提供和优化的资源分 配，是非常复杂且具有挑战性的任务。而基于经济学的一些方法能够针对不同的 消费群体为分配问题提供分布式的解决方案。这些方法非常适合处理通信网络中 复杂的问题。而在互联网中，这方面的研究还较少。本文主要采用相关的经济模 型和博弈理论对互联网的资源管理进行了研究，并取得了以下成果： ( 1 ) 详细讨论了采用效用函数来建模用户的行为，在效用函数的设计中，主要 考虑了两方面的因素：支付意愿和弹性因子。提出了基于n a s h 交易框架的资源分 配的公平性机制，并给出了这种机制的分布式实现模型。然后针对w c d m a 网络 中，用户数目较少和发送速率受限的情况，提出了基于非对称n a s h 交易框架的公 平资源分配方案，最后在统一的协作博弈理论的框架下，论证了效率的两种不同 形式f 社会福利最大化和收益最大化) 之间的关系。 f 2 1 以w c d m a 网络为背景，提出了考虑用户“自利的”行为的价格期望机制。 在这种价格期望机制中，用户预先估计自己的行为对网络的影响，并据此作出响 应。本文论证了这种价格期望机制的均衡性，并说明了价格期望机制与价格接受 机制( 用户仅仅作为价格的接受者，而没有考虑自己的行为对网络的影响) 之间的关 系。然后，从博弈理论的角度，基于m n l 模型( 多项罗吉特模型) ，提出了综合考 虑服务质量指标和价格因素的i n t e m e tq o s 评估机制。 ( 3 ) 将巴黎地铁计费方案( 即用户基于资源的使用情况作出自己业务类的选择， 而网络基于用户选择的业务类进行计费) 应用到无线接入网络中。研究了在这种模 型下网络收益和服务质量区分的问题，获得了如下的结论：p m p 方案并没有提高 网络的收益，只能实现服务区分。我们所得到的结论纠正了某些文献中不适当的 观点；然后，基于s t a c k e l b e r g 博弈提出了网络收益最大化模型，并确定了最大的 网络收益与网络应接纳的用户数之间的定量关系。 北京邮电大学博士论文中文摘耍 ( 4 ) 将v i c k r e y 拍卖机制用于a dh o c 网络中，使“自利的”节点能够相互协 作，提出了基于v i c k r e y 拍卖的路由机制，并证明了这种机制具有诱导用户以真实 意图竞标的特性，从而实现了费用有效性。 【关键词】互联网资源管理服务质量博弈理论a d h o c 网络 i l 一墅塑_ 丈竺堡圭笙苎一垒! 竺! ! ! a b s t r a c t w i t ht h ei n t e g r a t i o no fi n t e m e ta n dw i r e l e s sn e t w o r k s ，t h er e s e a r c ho nt h en e t w o r k r e s o u r c em a n a g e m e n tb a s e do ne c o n o m i c a lm o d e l sa n dg a m e t h e o r y ，h a se x p e r i e n c e da r e m a r k a b l e d e v e l o p m e n t t h e p r o b l e m s t h a tc a nb e i n v e s t i g a t e d b a s e d o n m i c r o e c o n o m i cm o d e l si n c l u d ef l o wa n dc o n g e s t i o nc o n t r o l ，r o u t i n g ，a c c e s s c o n t r o l ， s c h e d u l i n g ，n e t w o r kd e s i g na n d r e s o u r c ep r i c i n g ，e t c a tp r e s e n t ，c o m p u t e r s y s t e m sa r e u s e db ya n i n c r e a s i n g l yg r o w i n ga n dh e t e r o g e n e o u s s e to fu s e r s m a n yk i n d so f a p p l i c a t i o n s a r cb a s e do naw i d e r a n g e o fp e r f o r m a n c ec r i t e r i a i n t h i s c o n t e x t ， p r o v i s i o n i n gs e r v i c ee f f i c i e n t l ya n da l l o c a t i n gr e s o u r c eo p t i m a l l ya r ec h a l l e n g i n gt a s k s a p p r o a c h e s b a s e do ne c o n o m yc a n p r o v i d ed i s t r i b u t e ds o l u t i o nf o rd i f f e r e n tc u s t o m e r s ， s ot h e ya r ev e r ya p p r o p r i a t et od e a lw i t ht h ec o m p l i c a t e dp r o b l e m si nc o m n n m i c a t i o n s n e t w o r k st h ed i s s e r t a t i o ns t u d i e st h ei n t e r n e tr e s o u r c e m a n a g e m e n t b a s e do i lc c o t i o m i c m o d e l sa n dg a m e t h e o r y , a n dr e s u l t si nt h ef o l l o w i n g a c h i e v e m e n t ： ( 1 ) t h i sd i s s e r t a t i o n u s e s u t i l i t y f u n c t i o nt om o d e lu s e r s p r e f e r e n c e ss e v e r a l i m p o r t a n tf a c t o r s ( s u c ha s “w i l l i n g n e s s t o p a y a n de l a s t i c i t y ) i nc o n s t r u c t i n gu t i l i t y f u n c t i o na r ed e s c r i b e di nd e t m l ，a n dr e s o u r c ea d a p t a t i o nb a s e do nu t i l i t yi ss t u d i e di n t h i sd i s s e r t a t i o n f o rt h ec a s eo fl i m i t e dn u m b e ro fu s e r sa n dt r a n s i m i s s i o nr a t ei n w c d m a ，t h ef a i r n e s sf r a m e u ，o r kb a s e do na s y m m e t r i cn b s i si n v e s t i g a t e d i nt h e u n i f i e df r a m e w o r ko fc o o p e r a t i o ng a m e ，t h ep r o b l e ma b o u tf a i r n e s sa n de f f i c i e n c yi s e x a m i n e df o rs p e c i f i ce n v i r o n m e n t ( 2 ) t h i s d i s s e r t a t i o ne x p l i c i t l yc o n s i d e r st h es e l f i s h n e s so fu s e r s ，e x a m i n e st h ep r i c e p a r t i c i p a t i o nm e c h a n i s m i nw c d m an e t w o r k s ，i nw h i c hu s e r sa c ta sp r i c ea n t i c i p a t o r s b yp r i c ea n t i c i p a t o rw e m e a nu s e r sa n t i c i p a t et h ee f f e c to ft h e i rb e h a v i o r so nt h er e s u l t o fn e t w o r kr e s o u r c ea l l o c a t i o n ，a n dt a k ea c t i o n sa c c o r d i n gt ot h e i ra n t i c i p a t i o n t h i s d i s s e r t a t i o n i n v e s t i g a t e s t h ep r o b l e m so ft h ee q u i l i b r i u mo fr e s o u r c ea l l o c a t i o na n d r e v e n u em a x i m i z a t i o no fi nw c d m an e t w o r k s i n t e r a c tq o s e v a l u a t i o ni sa m u l t i d i s c i p l i n ep r o b l e m t h e nf r o m t h e p o i n to fv i e w o fg a m et h e o r y , b a s e do n 1 1 1 - 北京邮电大学博士论文 m u l t i n o m i a ll e g i tm o d e l ，t h i sp a p e re x a m i n e st h eq o se v a l u a t i o nt h r o u g hi n t e g r a t i n g q o s i n d e xw i t h p r i c ef a c t o r t h e n ，b a s e do ng a m et h e o r y , t h i sd i s s e r t a t i o ne x a m i n e st h e q o s e v a l u a t i o nm e t h o d t h r o u g hi n t e g r a t i n gq o si n d e xw i t hp r i c ef a c t o r ( 3 ) t h ed i s s e r t a t i o na p p l i e sp m p ( p a r i sm e t r op r c i n g ) s c h e m et ow i r e l e s sn e t w o r k ， a n dd e t a i l e d l ys t u d i e st h es e r v i c ed i f f e r e n t i a t i o n ，a n dd r a wt h ec o n c l u t i o nt h a ta l t h o u g h p m pd o e s n ti n c r e a s et h en e t w o r k r e v e n u e ，i ti n d e e di m p r o v e st h eq o s t h ec o n c l u s i o n r e c t i f i e st h ei n a p p r o p r i a t er e s u l ti ns o m e p a e r s t h e nf o rt h en e t w o r ko f f e r i n ge l a s t i c s e r v i c e ，t h ed i s s e r t a t i o np u tf o r w a r d st h et h em o d e lo fn e t w o r kr e v e n u e m a x i m i z a t i o n b a s e do n s t a c k e l b e r gg a m e ，a n d e x a m i n e st h e r e l a t i o n s h i p b e t w e e nn e t w o r k r e v e n u e - m a x i m i z a t i o na n di n c e n t i v ef o rn e t w o r kt oe n f o r c ec o n g e s t i o nc o n t r 0 1 ( 4 ) f o ri n c e n t i v em e c h a n i s mt os t i m u l a t ec o o p e r a t i o na m o n gm o b i l et e r m i n a l si n a dh o cn e t w o r k s ，t h ed i s s e r t a t i o nd i s c u s s e st h e r o u t i n gs c h e m eb a s e do nv i c k x e y a u c t i o n ，a n da n a l y t i c a l l yd e m o n s t r a t e st h a tt h es c h e m eg i v e st e r m i n a l si n v e n t i v e n e s st o “t e l lt r o t h ”i nb i d ，a n dc a na c h i e v ec o s te f f i c i e n c y k e y w o r d s ：r e s o u r c em a n a g e m e n t ，q o s ，g a m e t h e o r y , a d h o cn e t w o r k s 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本人承担一切相关责任。 日期 粤呜红珥幽迪 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制 手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密沦 文注释：本学位 本人签名： 导师签名： 适用本授权书。 日期：尘咝缉丝留 日期 印f f g 2 r 北京邮电大学博士论文第一章绪论 第一章绪论 基于经济模型与博弈理论的移动互联网资源管理和服务提供是目前研究的热 点。本章首先论述了本论文选题的可行性和必要性，然后对于目前国内外相关领 域的研究现状进行了总结和归纳，最后简要介绍了本论文的研究内容和结构安排。 1 1 引言 随着人们对信息移动性的迫切需求，高度的开放性、全球的移动性、承载业 务的多样性将成为新一代互联网的重要特征。业界和公众都在期待i n t e r n e t 和无线 通信的真正融合，但在这两个领域存在基本的技术上和商业模式上的不兼容。这 对于基于统一框架的网络资源管理的研究工作提出了挑战。而现有的网络资源管 理的方案存在如下的问题： 大规模网络中分布式的管理问题：应当建立在如何评价q o s 以及网络中的拥 塞。现在n t e m e t 互联了许多异构的系统以提供计算和通信资源的集合，而且 这些系统由不断增加的需求各异的用户使用。因此使系统的复杂性大大的增 加。 区分服务中内在的激励问题：如果没有内在激励结构，所有的服务都会成为“尽 力而为f b e ) ”的服务：如果在优先级类之间没有价格区别，所有的用户将选 择高优先级类。当然，用户的行为受合约和管制的的控制，但是这将导致复 杂的监控和管制系统。另外，网络可能无法( 或很困难) 获得单个用户的q o s 需 求和业务模式，经济有效的影响用户行为的方式是给用户提供适当的经济激 励。 自组织( a dh o c ) n 络中节点的协作问题：在a dh o e 网络从军用转向商用时， 这是需要解决的问题；自治的设备自主地决定是否协作，每个参与者都趋向于 通过不协作的行为来最大化自己的资源效用。因此需要促进协作的激励机制。 自治设备的网络强烈的与经济学中的协作与激励相关。 人类社会的基本问题是生存与发展。生存与发展就是不断的用物质产品( 以及 1 北京邮电大学博士论文 第一章绪论 劳务) 来满足人们日益增长的需求。需求来自于人类的欲望，欲望的特点在于无 限性，相对人们无限的欲望而言，资源量总是有限的和不足的。这就是经济学家 所说的“稀缺性”。稀缺性是人类社会面临的永恒问题。稀缺性决定了每一个社会 和个人必须做出选择。欲望有轻重缓急之分，同一种资源可以满足不同的欲望。 选择就是用有限的资源去满足什么欲望的策略。选择要决定用既定的资源生产什 么、如何生产和为谁生产这三个基本问题。这三个基本问题被经济学家称为资源 配置问题。经济学要研究的正是选择问题或者说资源配置问题。正是在这一意义 一h ，经济学被称为“选择的科学”。经济学研究选择问题或资源配置并不是醺它可 以直接告诉人们如何去做，而是向人们提供一套解决这个问题的工具和方法，告 诉人们解决这个问题可供选择的思路 2 2 1 。因而出于下面几方面的原因，本文选择 了从经济学领域来看待网络问题。 资源相对于人的无限的欲望是稀缺的，而经济学是研究理性选择的科学 ( s c i e n c eo f r a t i o n a lc h o i c e ) ； 博弈理论在通信网络环境下是适宜的工具，原因是博弈理论主要处理分布式的 优化一单个“自利的( s e l f - i n t e r e s t ) ”用户自主作出决策，而不是由中心的机构 控制。在通信系统中需要解决的复杂问题大部分是n p h a r d 问题。因此，中心 化的解决这些问题在计算上不可行的，尤其是当网络规模增加时。博弈理论集 中于系统问题分布式的解，因此在系统中考虑博弈作为解决方案是高度可扩展 的； 经济模型对于资源共享算法提供了许多有意义的帮助。首先，提供一组工具用 于分散资源控制以限制复杂性；第二，对于资源共享问题产生新的理解。 因此，应用博弈理论模型研究网络的资源分配最近获得了较大的关注。具体 而言，使用微观经济学的概念研究的问题包括：流量拥塞控制、路由、接纳控制、 调度、网络设计和资源计费等。现在的计算机系统由不断增长的用户访问，而且 多种应用基于范围广泛的性能标准，在这种场景下，有效的服务提供和优化的资 源分配，是非常复杂且具有挑战性的任务。而基于市场的方法能够针对不同的消 费群体为分配问题提供分布式的解决方案。这些方法非常适合处理通信网络中复 杂的问题。在某些场合下，博弈理论比解决经济问题更加适合于解决通信问题。 北京邮电大学博士论文第一章绪论 博弈理论典型的假设是：所有的参与者以一种充分理性的方式寻求最大化自己的 效用。在经济问题中，参与者很少是充分理性的，但是在通信中却可以如此假设( 在 终端上可以通过编程使其具有充分的理性1 。因此强的理性假设似乎更适合于机器 而不是人。 从微观经济学的角度寻找网络问题的解决方案分为两个步骤：第一步是，很 好的定义问题，并标识与处理问题相关的优化参数；对于定义好的网络问题，下 面关键是从网络的角度、消费者的角度或同时从两者出发考虑构造表示资源分配 问题的效用模型。具体而言，将博弈理论应用到通信网络的研究中，通常第一步 包括建模效用函数，它将用户消耗的资源或收到的服务映射到感受到的满意级别， 并定义网络或系统目标，然后建立有效的操作点。由于通常自私的个体的集合不 可能达到最优社会福平l j ( s o c i a lw e l f a r e ) 或网络收益最大的操作点，因此下一步就是 构造一种定价( p r i c i n g ) 方案，使之对个体产生刺激以便个体能够以增加整体网络性 能以及用户满意度的方式发展。定价由网络供应商基于个体使用网络资源的社会 费用( s o c i a lc o s t ) 来确定。这些方案的基本目标是，通过对资源计费来控制用户的行 为以便获得预期的结果，例如，较高的整体网络利用率和较好的用户的公平性。 基于经济模式的资源分配方式有下面的特点： 通过不同的效用函数定义应用。新应用不必适应到已存在的业务类中，效用规 范也不需要详细的业务流特征，而且可以容纳范围广泛的业务。由于每个业务 通过效用函数独立说明，增加新业务到系统不会引入太多的复杂性。 显式地考虑了每个用户的效用和相对优先级。即每个用户根据价格和自己的 q o s 需求来购买资源。 可以通过改变价格实现动态的资源管理。当负荷变化时，网络可以调节价格使 资源在用户之间实现最优的分配。 为用户良好的行为和有效地使用资源提供了激励因素，因为用户必须为资源付 费，所有用户不会请求超过需要的资源。 可以减轻接纳控制的需求。由于价格增加时，每个用户需求的资源减少。当系 统的负荷较大时，网络可以设置很高的费用使总的资源需求不超过资源容限。 只有那些具有较高效用的应用被接纳，而具有较低效用的用户将被阻塞。 北京邮电大学博士论文 1 2 国内外发展动态 1 2 1 基于效用的资源分配机制、公平与效率的问题 随着移动多媒体业务的增长，下一代的无线网络需要承载多媒体业务，包括 话音、视频、图像或数据以及它们的结合。多媒体应用能够容忍并适应某种范围 的q o s 的暂时变化，这种适应可以通过使用可调节速率的编解码器和采用分级的 声音或视频流编码技术来获得。因此受控制的服务降级是网络服务管理的一个重 要的组成部分。它反映了从硬的q o s 保证模式到软的、自适应的0 0 s 保证模式的 转变。移动应用根据网络条件自适应地调整资源的使用，同时保证一定的业务质 量的能力是非常重要的。现有的移动网络( 如m o b i l e i p 和3 g 蜂窝系统等) 缺少架构 的灵活性，不能容纳在时变的环境下应用的适配需求。因此需要设计有效的网络 适配机制来支持受控的服务降级，允许应用得体地适应于暂时的带宽变化，而不 会或很少产生整体质量的下降。 r a y m o n dr u i f e n gl i a o 在其博士论文 6 中提出了应用和服务敏感的资源分配 框架。形式化带宽效用函数的研究工作可以分成两种不同的阵营：一个是信号处 理技术阵营，另一个是网络研究阵营。来自信号处理的工作主要集中在效用度量 和基于效用的端到端的速率控制。而来自网络研究的工作集中于采用效用幽数研 究t c p 建模以及基于效用的带宽分配算法。统一的效用函数模式闭合了网络和基 于应用的适配之间的控制环路。应用的敏感性可以由多媒体内容生成的效用函数 来建模，而服务区分可以通过对网络业务类按比例缩放效用函数来获得。 由于i n t e r n e t 和无线网络的逐渐融合以及在无线网络中提供数据业务的需求日 益增加，有效地利用和控制有限的无线网络资源目益重要，除了简单性和实现的 有效性外，资源控制的过程还应当有坚实的经济理论的基础，在经济模型基础上 考虑移动用户的实际需求，才可能有效的利用网络资源。因此需要研究基于经济 理论模型的方案。在相关的文献 4 】 5 8 1 6 1 8 1 9 】中采用基于价格因素的非协作 功率控制博弈对功率进行有效的控制。通常第一步包括建模效用函数，将用户消 耗的资源或收到的服务映射到经历的满意级别，采用每单位能量传输的有效比特 数目作为效用函数。然后定义非协作的功率博弈问题，论证了非协作功率博弈存 北京邮电大学博士论文 第一章绪论 在n a s h 均衡，但此n a s h 均衡不是p a r e t o 最优的。然后证明了含有计费因素的非 协作功率博弈问题可以获得p a r e t o 改进( p a r e t oi m p r o v e m e n t ) ，即存在一个计费价 格，使分布式的功率博弈与没有价格因素时的博弈结果相比，能够达到p a r e t o 改 进，这种改进不一定是p a r e t o 最优的，但是通过动态的价格因素可以达到摄优的 社会福利。在未来的支持具有高带宽需求的多媒体业务的3 g 网络中，无线资源也 是非常有限的。因此，除了电池功率的费用，综合考虑无线资源拥塞控制( 信号质 量和速率) 也是非常重要的。 在无线互联网中弹性业务的业务量控制和资源管理的目标是从用户和网络的 视角，以有效和公平的方式分配资源。有效性和公平性的概念并不是简单明了的， 其高度依赖于所研究问题的环境。例如效率可能指最大化网络收益或将拥塞保持 在可管理的水平。 资源分配的基本的问题是： 如何以公平或公正的方式分配资源，而同时考虑不同用户类的不同特征? 有没有适宜的标准完成这种分配? 何为效率? 这样一些问题，过去已经做过一些研究。一个通常的思路是试图实现和分析 已知的一些方案，如最大一最小公平性或优化福利函数的方案。但目前没有统一 的框架对这些问题进行说明。c a t h e r i n er o s e n b e r g 等提出了基于博弈理论的系统的 资源分配的框架，研究了基于对称( 非对称) n a s h 交易框架的公平性问题【7 。通过 对现有一些方案的考察，可以看出它们存在博弈理论的解释，因此可能比较各种 不同的解决方案。而且从这个视角概括化以包括用户性能需求和用户的预算是可 能的。 1 2 2 基于市场方式的资源分配 经济模式不仅考虑了分布式的实现，而且提供了调整用户行为的机制。因此基 于经济模型的最优网络分配方案在最近几年出现了大量的研究成果。大体而言， 这些研究可以分为两类：1 ) 基于市场的方式。在这种方式中，效用函数用来刻画 单个用户的服务需求。在这种方式中假设单个用户的效用函数对网络是不可知的， 北京邮电大学博士论文 第一章绪论 但用户知道自己的效用函数。网络的目标是分配资源来最大化与刚户效用函数自 关的网络总体目标函数。例如，网络可能通过分配资源来实现所有用户的效用和f 称 为社会福利) 最大化。为了实现整体的目标，网络使用费用来( 隐含地) 获得有关优 化效用函数的信息，并据此分配资源；2 ) 基于控制的方式。在这种方式中，网络 将效用函数分配给用户( 应用) 以刻画它们的业务需求，并将效用函数看作是一个控 制变量，通过它来实现期望的资源分配目标。在这种方式中，也可以使用费用作 为分布式决定用户传输速率( 或其它资源) 的手段。通过适当的选择效用函数，网络 可以实现各神资源共享目标( 如按比例的或最大最小公平性1 。 基于市场的方式正在成为控制大规模分布式系统的模式。这种方式之所以重 要不仅因为它是许多传统商品交换的机制，而且因为它已成为了在复杂系统中管 理和分配资源的一种新模式。市场的重要特性之一是货i = f i ( c u r r e n c y ) 的建立，市场 通过货币对异构的资源进行统一的评价，这使得管理者或用户能够说明各自喜好 或建立优先级。市场机制适宜于分散式系统的原因是，一旦货币兑换协议建立， 协商可以在不同的用户之间同时进行，而不需要中心化的权威机构。可扩展性是 市场方式的另一个优点，由于新资源或使用新资源的用户通过收取或支出货币可 以方便的加入系统( 网络) ，而价格可以作为低级别的信号来控制资源的使用。 通常而言，每个用户享受到的服务性能受访问相同网络资源的其它用户行为 的影响，因此所有用户获得的服务级别将是用户之间协商以满足各自效用后所获 得的均衡，而协商的目标是在竞争的主体之间寻找稳定的操作点，这正是博弈理 论所分析的内容。 在研究领域，出现了许多拥塞计费( c o n g e s t i o np r i c i n g ) 的模型。这些模型对于 异构韵资源需求问题提出了传统的经济学解决方案：将网络资源集合作为市场对 待，并相应的对使用资源计费。fp k e l l y 提出了一种市场方式 1 0 【1 1 】，其中每个 用户单位时间向网络提交一个“标价( b i d ) ”或“支付意愿”，网络接受这些竞标并 确定每条网络链路的价格。每个用户分配到的资源与其标价成正比，与链路价格 成反比。f 只k e l l v 说明了这种方案使效用之和最大化( 社会福利) ，但是在他的模型 中，一个基本的假设是每个用户作为价格的接受n ( p r i c e t a k e r ) ，也就是说，用户没 有预期他们的行动对于链路价格的影响。 北京邮电大学博士论文第一章绪论 v a s i r i s 研究了w c d m a 网络中上行和下行链路基于经济模型的资源使用情 况，并提出和分析了一种服务区分机n ! j 1 2 。他设计了一种新的加权参数“支付意 愿”来反映资源的分配情况。同f pk e l l y 设计的机制类似，但是这种方案中没有 考虑用户对于价格的期望，而是仅仅将用户作为价格的接受者，而且也没有研究 基于博弈理论的资源的分配的均衡性。 网络用户、服务提供商和研究人员所面临的核。f l , 的问题是没有任何人能够控 制的持续变化的网络行为，而这种网络行为依赖于网络中汇聚的业务量，而汇聚 的业务量是许多用户独自决策如何使用网络的结果。这些决策受用户所面l 临的刺 激因素的影响，因此需要将价格作为网络控制的信号引入网络工程设计中，描述 提供q o s 的工程技术问题和对网络服务计费的经济问题。 1 2 3 基于价格的区分服务 随着i n t e m e t 应用的增多，随之而来的是对多种q o s 级别的需求。将来能够提 供区分的带宽服务模型、机制和策略受复杂的技术和非技术因素的驱动。对用户 进行区别对待有以下两神方式： 区分的服务：即通过技术机制来提供更好的服务，如优先级等； 区分的价格：即通过减少使用网络的人数来提供较好的服务。即更贵的网络 价格一较少的使用者一较好的服务。 由于服务需求的异构性有必要对不同q o s 需求的业务采用不同的方式处理。 但是没有适当的计费机制，任何优先级方案都是无用的。如果在优先级类之间没 有价格区别，所有的用户将选择高优先级类，也就是说，各种不同的优先级类的 价格应当激励用户加入适当的优先级类。 p e t e r m a r b a c h 研究了利用优先级提供区分服务质量的网络中的计费方案 1 4 。 考虑用户自由的选择业务优先级，并据此付费。将这种情况建模为非协作的博弈， 即用户以自利的方式来选择分组的优先级以优化自己的净利益。文献 1 4 】论证了在 这种博弈中存在均衡，并且说明了价格对于均衡的影响。本文得到的结果是，对 于平滑的业务( 在每个时隙中，需求通过确定性模型给出) ，在这种计费方案下的均 衡分配中，最多只使用两个业务优先级，而且能够通过计费方案保证绝对的q o s ； 北京邮电大学博士论文第一章绪论 但对于突发的业务，将使用低于某个i o 的所有优先级，而且低于优先级j o 的业务 的传输概率不仅依赖于定价，还依赖于优先级i o 的传输概率。但是计费仍然可以 用于设置不同优先级之间传输概率的比率，从而提供相对的q o s 保证。 最近在i n t e m e t 计费的研究中提出了p m p ( p a r i sm e t r op r i c i n g ) 计费策略n 5 1 。 p m p 使用价格作为实现网络资源分配的工具以便提供q o s 保障。p m p 是简单的、 自我调节的，而且不需要大量的通信或带宽开销。p m p 类似于d i f f - s e r v ，它并不 提供“硬”的q o s 保障，而仅仅提供期望的服务级别，但是与d i f f - s e r v 不同，p m p 在业务量管理中集成了经济和计费的概念，是多学科领域的研究问题。 1 2 3a dh o c 网络中节点协作的激励机制 在a d h o e 网络中，设备之间需要协作以补偿基础设施的缺乏。但是自治的设 备自主地决定是否协作。因此激励是必不可少的。在集体( c o l l e c t i v e ) 网络( 如军事网 络) 中，成员之间有充分的动机协作。但是当a d h o c 网络从军用转向民用，由于无 线和移动设备资源的苛刻限制，每个参与者都趋向于通过不协作的行为来最大化 自己的资源效用，因此需要促进协作的激励机制。自治设备构成的网络与经济学 中的协作与激励密切相关。自治设备和经济实体试图最大化他们资源的效用，而 协作又与实体的目标冲突，因此需要通过激励机制来刺激。 p h i l i p p 对激励模式进行了定义，并详细描述了激励机制的分类 2 6 。激励模式 ( i n c e n t i v ep a t t e r n ) 是刺激协作的模式，包括激励方案可以使用的抽象机制的集合。 如果每种激励模式的特征已知，则可以通过考虑特定的应用环境并将其与适当的 激励模式相匹配来改进系统的构造激励方案。 y i n gq i u 将价格作为在a dh o c 网络中刺激协作的手段，用户对为其它节点转 发的分组收费，并提出了迭代的价格和速率适配算法，并论证了这种算法收敛到 社会最优的带宽分配 2 7 】。文献 3 1 3 2 基于经济模式设计了节点之间协作的激励 机制，但这些方案没有显式地考虑节点转发分组的能量费用。文献 3 3 中采用机制 设计( m e c h a n i s md e s i g n ) 思想，设计了a dh o e v c g 的路由方案，并从博弈理论角 度分析了这种方案具有激励用户显示真实的转发费用，并基于v c g 机制对转发节 点进行额外的补偿( 即补偿的数量大于转发分组的实际的费用) 。 北京邮电大学博士论文第一章绪论 1 3 本文主要贡献 本文按照经济理论( 微观经济学、博奔理论等) 对无线互联网中资源管理机制进 行研究，主要的贡献是： 随着i n t e m e t 和无线网络技术的逐渐融合，将经济学模型和博弈理论应用到网 络资源分配是研究的一个热点。具体而言，使用微观经济学的概念研究的问题包 括：流量拥塞控制、路由、接纳控制、调度、网络设计和资源计费等。现在，大 量的具有异构需求的用户访问计算机系统，因此有效的服务提供和优化的资源分 配，是非常复杂且具有挑战性的任务。而基于经济学的一些方法能够针对不同的 消费群体为分配问题提供分布式的解决方案。这些方法非常适合处理通信网络中 复杂的问题。而在互联网中，这方面的研究还较少。本文主要采用相关的经济模 型和博弈理论对互联网的资源管理进行了研究，并取得了以下成果： ( 1 ) 详细讨论了采用效用函数来建模用户的行为，在效用函数的设计中，主要 考虑了两方面的因素：支付意愿和弹性因子。提出了基于n a s h 交易框架的资源分 配的公平性机制，并给出了这种机制的分布式实现模型。然后针对w c d m a 网络 中，用户数目较少和发送速率受限的情况，提出了基于非对称n a s h 交易框架的公 平资源分配方案，最后在统一的协作博弈理论的框架下，论证了效率的两种不同 形式( 社会福利最大化和收益最大化) 之间的关系。 f 2 ) 以w c d m a 网络为背景，提出了考虑用户“自利的”行为的价格期望机制。 在这种价格期望机制中，用户预先估计自己的行为对网络的影响，并据此作出响 应。本文论证了这种价格期望机制的均衡性，并说明了价格期望机制与价格接受 机制( 用户仅仅作为价格的接受者，而没有考虑自己的行为对网络的影响) 之间的关 系。然后，从博弈理论的角度，基于m n l 模型( 多项罗吉特模型) ，提出了综合考 虑服务质量指标和价格因素的i n t e m e tq o s 评估机制。 ( 3 ) 将巴黎地铁计费方案( 即用户基于资源的使用情况作出自己业务类的选择， 而网络基于用户选择的业务类进行计费) 应用到无线接入网络中，研究了在这种模 型下网络收益和服务质量区分的问题，获得了如下的结论：p m p 方案并没有提高 网络的收益，只能实现服务区分。我们所得到的结论纠正了某些文献中不适当的 观点：然后，基于s t a c k e l b e r g 博弈提出了网络收益最大化模型，并确定了网络收 北京邮电大学博士论文 第一章绪论 益最大化与网络应接纳的用户数之问的定量关系。 ( 4 ) 将v i c k r e y 拍卖y l s j j 用于a dh o c 网络中，使“自利的”节点能够相互协 作，并提出了基于v i c k r e y 拍卖的路由机制，并证明了这种机制具有诱导用户以真 实意图竞标的特性，从而实现了费用有效性。 1 4 本文的结构和安排 在第二章中考虑了基于支付意愿和弹性因素的效用函数的构造，并研究了基 于效用的资源适配机制以及在统一的协作博弈框架下，公平与效率的一些相关的 问题。 之后的第三章，以w c d m a 网络为背景，研究了考虑用户“自利的”行为的 网络均衡机制，在这种机制中移动节点不仅仅是价格的接受者，而且预期自己的 行为对网络资源分配的影响，讨论了在这种场景下的均衡问题。然后，基于博弈 理论探讨了i n t e m e tq o s 评估的问题，在评估中考虑了q o s 参数与价格的均衡问题。 第四章分成两个方面讨论了价格区分的服务质量的提供问题，首先研究p m p 方案在无线接入网络中的应用，即用户基于网络的使用情况选择业务类，而网络 根据对业务类的接入而收费，研究了网络收益与服务质量改善的问题。然后钏+ 列 于弹性业务的情况，基于s t a c k e l b e r g 博弈研究了网络收益最大化的问题，以及网 络实施接纳控制的动机。 第五章的主要目的是研究a dh o c 网络中，节点之间协作激励机制的问题。提 出了基于v i c k r e y 拍卖的付费方案，这种方案具有诱导用户以真实的意愿竞标的特 点，并能够实现全局的费用有效性，然后对这种机制进行了定性的分析。 最后是结束语，对全文进行了总结，指出了目前在研究中还存在的一些问题 和不足，并给出了了下一步的研究课题和相应的一些设想。 1 5 本章参考文献 1 】d f e r g u s o n ，c n i k o l a o u ，j s a i m m e s h ，a n dy y e m i n i ，“e c o n o m i c m o d e l sf o ra l l o c a t i n g r e s o u r c e si nc o m p u t e rs y s t e m s ，”1 i ls c o t tc l e a r w a t e r ，e d i t o r , m a r k e t - b a s e dc o n t r o l ：ap a r a d i g mf o r d i s t r i b u t e d r e s o u r c e a l l o c a t i o n ，s c o t t c l e a r w a t e r w o r l d s c i e n t i f i c ，h o n g k o n g ，1 9 9 6 1 0 北京邮电大学博士论文第一章绪论 f 2 o a f i a b ，“e c o n o m i c m e o h a m s mf o re f f i c i e n tw i r e l e s sc o e x i s t e n c e , a v a i l a b l eo n l i n e ， h t t p ：i t c m i t e d u i t e l s t u d e n t s p a p e r s a f t a b _ l c sp d f 3 j a l t m a r m ，hd a a n e n ，h o l i v e re ta 1 ，“h o wt om a r k e t m a n a g eaq o sn e t w o r k ，”i np r o e o f i e e ei n f o c o m2 0 0 3 4 4 z h o u c h i ，“u t i l i t y - b a s e dm u l t i - c e l lc d m a r e s o u r c ea l l o c a t i o nf o rw i r e l e s sv o i c ea n dd a