（计算机软件与理论专业论文）网络资源分配算法研究.pdf

华东师范大学硕士学位论文 摘要 随着i n t e m e t 的发展，网络资源作为一种新兴的资源正快速增长。网络资源广义 上可包括电子文档、电子视频、网络信息、应用程序、网络服务等，对于部分可复 制的网络资源，如电子文档和视频，人们可以轻易地从网上下载得，然而，对于部 分具有稀缺性的网络资源而言，如网络空间分配、网络服务分配等，如何合理分配 这类稀缺的网络资源，优化系统的整体效益，已成为一个重要的研究课题，这亦是 本文将主要关注解决的问题。网络资源的分配是指根据一定的分配算法，将稀缺的 网络资源有效分配给需要资源的消费者，使资源分配系统达到高收益，使资源供应 者和消费者均达到高收益。传统的资源分配算法多关注如何提高分配效率，但对资 源的属性关注甚少，也因此缺少有针对性、合理的分配算法来进一步提高稀缺的网 络资源分配的效率。本文将稀缺的网络资源分为两类一可定价网络资源和不可定价 网络资源，针对这两种网络资源的特点，进行建模分析，并且引入算法博弈论中的 基于网络流的计算均衡定价的算法和的组合拍卖机制来分别解决这两种网络资源的 分配问题。 本文的主要贡献有如下几点： 首先，将网络资源分为可定价与不可定价两种，并分别进行建模分析； 其次，针对可定价的网络资源，结合实际的网络教学平台空间分配问题，基于 网络流模型，引入算法博弈论中的计算均衡定价的算法，设计了完整的针对空问资 源分配的方法：可灵活计算的空间资源总量及基于均衡定价的空间资源分配算法； 本文用j a v a 实现了该分配算法，得到计算均衡价格的可视化工具，可灵活调整相 关参数，得到最优的资源分配结果。 最后，针对不可定价的网络资源，结合实际的网络教学平台课程资源分配问题， 设计了用户福利函数，引入算法博弈论中的组合拍卖方法，提出了基于组合拍卖的 资源分配算法，将资源有效分配，并获得高社会福利。用j a v a 和c p l e x 结合实现 了该算法，并经过多次实验，得到实验数据，与常用的基于排名或信誉的分配算法 对比，分析得知该算法针对不可定价的网络稀缺资源的分配更为有效，并能获得高 社会福利，兼顾考虑了资源分配的效率性与公平性。 本文引入和提出的网络资源分配算法具有扩展性。基于网络流的资源分配算法 华东师范大学硕士学位论文 在可定价网络资源分配，如网络带宽分配、云计算空间分配与预留等具有较大的应 用空间；基于组合拍卖的不可定价网络资源分配对于公益资源、公用资源的分配等 亦有参考意义。本文开发的可视化工具，简洁易用，可适用于一些需要计算可定价 资源总量及进行有效分配的场合。 关键词：网络资源分配，网络服务，组合拍卖，网络流，定价机制 i i 华东师范大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e m e t ，n e t w o r kr e s o u r c e sa san e wk i n do fr e s o u r c ea r e g r o w i n gr a p i d l y n e t w o r kr e s o u r c e sm a yi n c l u d ee l e c t r o n i cd o c u m e n t s ( e d o c u m e n t ) ， d i g i t a lv i d e o ，n e t w o r ki n f o r m a t i o n ，w e ba p p l i c a t i o n ，w e bs e r v i c ea n d s oo ni nb r o a ds e n s e f o rt h o s en e t w o r kr e s o u r c e sw h i c hc a nb ec o p i e d ，s u c ha se l e c t r o n i cd o c u m e n t sa n d v i d e o ，p e o p l ec a nd o w n l o a df r o mt h ei n t e r n e te a s i l y h o w e v e r ，f o rt h o s es c a r c en e t w o r k r e s o u r c e s ，s u c ha sn e t w o r ks p a c ea l l o c a t i o n ，w e bs e r v i c e ，h o wt of i n dt h er e a s o n a b l e a l l o c a t i o na l g o r i t h mo ft h e s es c a r c en e t w o r kr e s o u r c e s ，o p t i m i z i n gt h eo v e r a l lw e l f a r eo f t h es y s t e mh a sb e c o m ea ni m p o r t a n tr e s e a r c ht o p i c ，a n di sa l s ot h em a i ni s s u eo ft h i s p 印e r n e t w o r kr e s o u r c ea l l o c a t i o ni sd e f i n e da st h ee f f i c i e n ta l l o c a t i o no fs c a r c en e t w o r k r e s o u r c e st ot h ec o n s u m e r so w n i n gt h en e e du n d e rac e r t a i na l g o r i t h mt oa c h i e v eh i g h s o c i a lw e l f a r e ，t h a ti st h er e s o u r c ep r o v i d e r sa n dc o n s u m e r sb o t ha c h i e v eh i g hw e l f a r e t h et r a d i t i o n a lr e s o u r c ea l l o c a t i o na l g o r i t h mp a ym o r ea t t e n t i o nt oh o wt oi m p r o v et h e a l l o c a t i o ne f f i c i e n c y ，b u tl i t t l ea t t e n t i o nt ot h ep r o p e r t i e so fr e s o u r c e s ，a n dt h u st h e r ei s l a c ko fat a r g e t e d ，r e a s o n a b l ea l l o c a t i o na l g o r i t h mt oi m p r o v et h ea l l o c a t i o no fs c a r c e n e t w o r kr e s o u r c ee f f i c i e n c yf u r t h e r t h i sp a p e rd i v i d e st h es c a r c en e t w o r kr e s o u r c e si n t ot w oc a t e g o r i e s p r i c i n gb a s e d a n dn o n - p r i c i n gb a s e dn e t w o r kr e s o u r c e s a n da c c o r d i n gw i mt h ec h a r a c t e r i s t i c so ft h e s e t w ok i n d so fr e s o u r c e s ，w eu s em o d e l i n ga n a l y s i sa n di n t r o d u c et h en e t w o r kf l o wb a s e d m a r k e tc l e a r i n gp r i c e sa l g o r i t h ma n dc o m b i n a t o r i a la u c t i o nm e c h a n i s mo fa l g o r i t h m g a m et h e o r yt os o l v et h ep r o b l e m so ft h e s et w ok i n d so fn e t w o r kr e s o u r c ea l l o c a t i o n t h em a i nc o n t r i b u t i o n so ft h i sp a p e ra r et h ef o l l o w i n g ： f i r s t ，n e t w o r kr e s o u r c e sc a nb ed i v i d e di n t op r i c i n ga n dn o n p r i c i n g ，a n da n a l y z e db y m o d e l i n gs e p a r a t e l y ； s e c o n d ，r e g a r d i n gt h ep r i c i n go fn e t w o r kr e s o u r c e sc a nb ec o m b i n e dw i t ht h ea c t u a l s p a c ea l l o c a t i o no fn e t w o r kt e a c h i n gp l a t f o r m ，u s i n gt h en e t w o r kf l o wm o d e la n dt h e a l g o r i t h mo fc o m p u t em a r k e tc l e a rp r i c e ，w ed e s i g n e dar e s o u r c ea l l o c a t i o nm e t h o d ： f l e x i b l er e s o u r c e sq u a n t i t yc o m p u t i n gf u n c t i o n ，a n dn e t w o r kf l o wm o d e lb a s e dr e s o u r c e i i i 华东师范大学硕士学位论文 a l l o c a t i o na l g o r i t h m ；t h e nw eu s i n gj a v at oi m p l e m e n tt h ea l g o r i t h ma n do b t a i nav i s u a l t o o lw h i c hc a nc o m p u t et h ee q u i l i b r i u mp r i c e sa n df l e x i b l ya d j u s t e dr e s o u r c e r e l a t e d p a r a m e t e r s ，a n dg e tt h eo p t i m a lr e s u l to fr e s o u r c ea l l o c a t i o n f i n a l l y , f o rt h en o n - p r i c i n gn e t w o r kr e s o u r c e s ，r e g a r d i n gt h en o n p r i c i n go fn e t w o r k r e s o u r c e sc a nb ec o m b i n e dw i t ht h ea c t u a lc o u r s ea l l o c a t i o no fn e t w o r kt e a c h i n gp l a t f o r m ， w ed e s i g n e dt h eu s e rw e l f a r ef u n c t i o n ，i n t r o d u c e dt h ec o m b i n a t o r i a la u c t i o nb a s e d r e s o u r c ea l l o c a t i o na l g o r i t h m ，a n dg a i n e dt h ee f f i c i e n ta l l o c a t i o no fr e s o u r c e sw i t hh i g h s o c i a lw e l f a r e c p l e xw i t hj a v ac o m b i n a t i o ni su s e dt oi m p l e m e n tt h ea l g o r i t h m ，a n d a f t e rr e p e a t e de x p e r i m e n t s ，t h ee x p e r i m e n t a ld a t ai s o b t a i n e d c o m p a r i n gw i t l lt h e c o m m o n l yu s e dr a n k i n g b a s e do rr e p u t a t i o n b a s e da l l o c a t i o na l g o r i t h m ，t h ea n a l y s i so f t h ee x p e r i m e n t a ld a t ai n d i c a t e dt h a tt h ea l l o c a t i o no f n o n - p r i c i n gs c a r en e t w o r kr e s o u r c e w a sm o r ee f f i c i e n t l ya n dc o u l dg a i n h i g h e rs o c i a lw e l f a r ea n dt o o ki n t oa c c o u n t e f f i c i e n c ya n df a i r n e s sf o rt h er e s o u r c e sa l l o c a t i o n t h en e t w o r kr e s o u r c ea l l o c a t i o na l g o r i t h m si nt h i sp a p e rh a v ee x p a n s i b i l i t y n e t w o r k f l o wm o d e lb a s e dp r i c i n gn e t w o r kr e s o u r c ea l l o c a t i o nc o u l db eu s ef o rn e t w o r k b a n d w i d t ha l l o c a t i o n ，s p a c ea l l o c a t i o na n dr e s e r v a t i o ni nc l o u dc o m p u t i n g ；c o m b i n a t o r i a l a u c t i o n b a s e dn o n - p r i c i n gn e t w o r kr e s o u r c ea l l o c a t i o na l s os u i t a b l ef o rt h ed i s t r i b u t i o no f p u b l i cr e s o u r c e s t h ev i s u a lt o o li se a s yt ou s ea n dc o u l db ea p p l i e di nt h ef i e l do fo t h e r p r i c i n gr e s o u r c ea l l o c a t i o n k e yw o r d s ：n e t w o r kr e s o u r c ea l l o c a t i o n ，w e bs e r v i c e ，c o m b i n a t o r i a l a u c t i o n s ，n e t w o r kf l o w , p r i c i n gm e c h a n i s m i v 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取 得的研究成果据我所知，除文中已经注明引用的内容外，本论文不包 含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献 的个人和集体，均已在文中作了明确说明并表示谢意 作者签名：蛰亟日期：型2 ：! 竺：! 竺 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版。有权将学位论文用于非赢利目的的少量复制并允许论文进入 学校图书馆被查阅有权将学位论文的内容编入有关数据库进行检索 有权将学位论文的标题和摘要汇编出版保密的学位论文在解密后适用 本规定 学位论文作者签名： 日期： 蠲面 导师签名： 川垆 彩蝴 日期：1 0 , i q 华东师范大学硕士学位论文 1 1 研究背景 第一章引言 随着2 1 世纪i n t e m e t 的高速发展，人们已经越来越离不开计算机和网络了。网 络上分布式地存放了各种各样人们需要的资源，人们可以通过网络观看电视节目， 点击网页查看新闻，在家通过电子商务网站购物、销售，通过网络教学平台轻松学 习课程。尽管网络存储和带宽仍在不断增加，资源的增加速度越来越快，除了一些 可复制或重用的网络资源，如电子文档和视频点播等可以满足人们的需要，但一些 总量有限的稀缺网络资源始终与人们的需要存在一定的距离，如网络带宽、网络服 务( 如网络空间分配、网络课堂名额等等) 。因此如何针对稀缺的网络资源的特性 进行有效的分配，使资源分配系统获得高效益，亦即使资源提供者和消费者均获得 高收益，己成为当前的研究热点。 1 1 1 资源分配问题 n o r m a nr n i e l s e n 在1 9 7 0 年时即提出计算机资源是种稀缺资源，“尽管在过去 的2 0 年里，计算机的数量和容量都有了巨大的提升，但是对计算能力的需求仍是 超过了计算机可提供的范围”【1 】。也许有人希望获得更多的缓存，有人希望获得更 多的进程，人们希望得到自己所请求的一切资源，以帮助自己又快又好的完成工作。 因此，人们面临着计算机资源的分配问题。 如今，计算机硬件技术的飞速发展，单个计算机资源的分配问题已经逐步得到 解决，人们不再为硬盘空间不足而烦恼，但是在今天的w e b2 0 时代，更多的网络 资源分配问题需要解决。狭义上讲，网络资源是指指通过现代计算机和通讯技术相 结合构筑起来的以超链接方式将文字、图像、语言和视频信息链接为超文本和超媒 体系统。它具有信息来源广、量大、传播速度快、内容庞杂不一形式多样及时等特 点【2 】。网络资源共享网站的兴起很大程度上解决了电子文档和视频这类网络资源的 分配问题。通过上豆丁网( w w w d o c i n c o m ) 或土豆网( w w w t u d o u t o m ) ，人们可 以方便的寻找到需要的电子文档或视频，从而满足了人们对此类资源的需要。但是， 广义上讲，网络资源亦包括网络服务，网络带宽分配及网络空间等有限的网络资源， 华东师范大学硕：l 学位论文 例如，在网络空间盛行的今天，人们开始在网上存放自己的照片、文档、视频 等等，网络服务和云计算的讨论日益火热，网络带宽和网络空间亦成为人们争相申 请的网络资源。网络资源分配即是将现有的稀缺的网络资源，根据一定的分配算法， 将资源有效分配给需要资源的用户，使资源提供者和使用者均达到较高收益。如何 为人们分配合适的稀缺网络资源，让有限的网络资源有效利用和公平分配，是目前 的研究热点之一。为此，人们提出了许多优秀的资源分配算法，对资源分配的影响 因素、效率等进行了深入的讨论。在一些顶级的会议和期刊上，不断涌现了许多讨 论资源分配的文章，如基于组合拍卖、用户信誉、竞价博弈，网络流均衡模型的分 配算法等等。据c n k i 的统计，研究网络资源的文献呈逐年增长趋势【3 】。 下文简述了网络资源的定价问题，本文正是以网络资源是否可定价的特性，将 其分为可定价网络资源和不可定价网络资源，分别建立通用模型，引入网络流模型 和组合拍卖方法，提出有效的资源分配算法，解决资源分配问题。 1 1 2 资源定价问题 早在1 9 6 8 年，s i n g e r ，k a n t e r 和m o o r e 就讨论了是否对资源定价的需要，并且 对三种分配方法进行了有效性的比较【4 】。 网络资源是一个稀缺资源，要实现具有服务质量保证的网络服务，必须处理好资 源的优化性、分布性、差异性和替代性等问题【5 】。传统的网络资源分配方法包括优 先级调度、逐个流资源预约等【6 】，尽管解决了部分资源分配问题，但这些方法不能 很好的考虑网络资源的特性，从而实现更有效率的分配。 因此，为了网络资源的合理和优化分配，需考虑引入市场机制，即把定价因素 引入网络资源分配。 现有的定价因素解决网络资源最优分配问题的典型方法包括巴黎地铁定价策略 ( p a d sm e t r op r i c i n g ，p m p ) ，o d l y z k o 借助巴黎地铁通过价格杠杆调节车厢拥挤的思 想，提出将网络从逻辑上分为若干个子网络，根据不同的网络服务，收取不同的费 用，用户可以根据自己的偏好及资金选择合适的网络，得到不同的网络服务【7 】。该 算法实现了将网络服务定价进行分配，然而p 机制与优先级队列机制相比不能 够有效利用网络资源，经济效率上来讲比优先级队列机制要低 8 】。此外，优化q o s 2 华东师范大学硕十学位论文 降级法【9 】、k e l l y 市场模型【l o 】和s r a 方法【1 l 】也提出了基于定价的网络资源分 配问题。k e l l y 通过对交通流控制和动态定价策略关系的研究，提出比例公平定价 策略( p f p ：p r o p o r t i o n a lf a i r n e s sp r i c i n g ) 。k e l l y 认为系统的资源分配受用户的支付 能力影响，当用户单位时间内愿意为消费资源付出的费用确定时，网络资源供应者 将此费用作为权值，根据比例公平原则分配资源。当用户的费用权值和网络资源分 配达到均衡时，分配系统达到最优化，总效用最大。然而随着网络规模的扩大，每 个用户的单位费用计算开销将变得更为复杂，算法时间开销较大。 引入资源定价机制，主要是为了引导用户合理的使用网络资源，但是，上述的 算法主要考虑可定价网络资源的分配，对于一些不可定价的网络资源的分配考虑甚 少，如带有公益性质的教育资源或公共资源的分配，显然不能简单的定价收费来实 现有效分配。为此，本文针对网络资源的特性，将资源分为可定价网络资源和不可 定价网络资源，从而设计不同的分配算法，进行更有效的分配。 1 1 3 算法博弈论简述 博弈( g a m e ) 的本质是存在利益冲突的参与者均希望自身获得的利益能够最大 化，使得参与博弈的各方所采取的策略具有相互依存性( s t r a t e g i ci n t e r d e p e n d e n c e ) 。 博弈论( g a m et h e o r y ) 针对上述依存性探索各种博弈模型中的可能出现的均衡，并 对各种均衡进行规律总结【1 2 】【1 3 】。 在博弈论模型中，每个主体的收益取决于2 个方面，一是其自身的行为，二是 其他人的行为。也就是说，单个个体所采取的最优策略，取决于其自身预期其他人 所可能采取的策略。 博弈论被公认为研究不同主体决策互相影响，行为交互的最佳数学工具。 从发展来看，博弈论的研究大致经历了以下三个发展阶段： l 、 合作博弈( c o o p e r a t i v eg a m e ) 阶段 美国数学家冯诺依曼和摩根斯特恩于1 9 4 4 年出版了博弈论与经济行为一 书【1 4 】，该书中提及“策略型”和“扩展型”等基本博弈模型，并首次定义了最小最大 解决概念( m i n m a xs o l u t i o n ) 。该书构建了博弈论的基本框架。 2 、 非合作博弈( n o n c o o p e r a t i v eg a m e ) 阶段 华东师范大学硕士学位论文 数学家n a s h 于1 9 5 0 年提出了著名的纳什均衡( n a s he q u i l i b r i u m ) 的概念【1 5 】。 假设有n 个局中人参与博弈，给定其他人策略的条件下，每个局中人选择自己的最 优策略( 个人最优策略可能依赖于也可能不依赖于他人的战略) ，从而使自己利益 最大化。所有局中人策略构成一个策略组合( s t r a t e g yp r o f i l e ) 。纳什均衡指的是这 样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的 情况下，没有人有足够理由打破这种均衡。纳什均衡，从实质上说，是一种非合作 博弈状态 1 6 1 。 同年，t u c k e r 定义了“囚徒困境”( p f i s o n e r s d i l e m m a ) ，这两个概念的提出奠定 了现代非合作博弈论的基础。 3 、 经济学及多领域应用阶段 上世纪7 0 年代以来，博弈论开始受到经济学家的重视，到8 0 年代已成为主流 经济学的一部分。1 9 9 4 - - 2 0 0 1 年先后有6 a 因博弈论相关研究获得诺贝尔经济学奖。 上世纪9 0 年代以后，博弈论的应用范围日益外延，已成为网络资源分配，自 动控制，人工智能等多个领域中广泛应用的工具。 在i n t e m e t 迅速发展的今天，博弈论与算法原本作为两个独立的领域，现如今 结合得越来越紧密，在网络研究中逐渐占有一席之地，为解释网络的奇妙做出了许 多努力，也渐渐形成了新的研究领域一算法博弈论。s c o t ts h e n k e r 曾说过，“网络就 是一种均衡，我们只是在鉴定这个博弈。” 1 2 国内外研究现状 在资源分配算法研究中，古今中外的学者提出了许多优秀的算法和工具。m i c h a l f e l d m a n 等使用价格预测方案建立了一个固定预算资源分配博弈，同时考虑了效率 和公平性以评价基于分布式的基于市场的资源分配系统的性能【1 7 】。y e o u f a n g w a n g 等讲述了支持n a s a 地面资源分配和规划的w e b2 0 分析工具g f 认p e ( g r o u n dr e s o u r c ea l l o c a t i o na n dp l a n n i n ge n v i r o n m e n t ) ，该工具能将分析、监控和 搜索功能集成在一个已有的社区环境- w e b 网站中，使用户能在这个集成了w i k i s ， 博客，电子图书馆、日历、讨论组等的w e b 网站中实现通讯、合作和分析协作【1 8 】。 在p 2 p 系统中，已有人量关于资源分配的研究。a n n as a t s i o u 【1 9 等研究了基于 4 华东师范大学硕士学位论文 信誉的资源分配机制以鼓励理性的参与者给与p 2 p 系统更多的贡献。参与者下载的 能力取决于其上传自身资源时获得的信誉，因此参与者会积极理性的进行共享，以 获得在整个p 2 p 系统中的稳定操作。yy a n 2 0 等设计了一个在p 2 p 系统中基于排名 的资源分配机制，其根据是设计了包含参与者共享和消费参数的排名函数，因此， 资源提供者可以给不同的消费者提供不同的服务。在p 2 p 网络中，许多工作主要关 注于如何激发用户共享资源，例如基于信誉的机制【2 0 】，基于定价的方案 2 1 1 ，及博 弈理论方法 2 2 1 。 g e o f f r e ym a i n l a n d 等讨论在传感网络中的资源配置问题【2 3 】。他们提出了自组 织资源分配( s e r f - o r g a n i z i n g r e s o u r c e a l l o c a t i o n ，s o r a ) 以在传感网络中进行资源 的分配。k e v i n 等设计并实现了基于分享拍卖的调度算法t y c o o n 2 4 。他们指出 如果对那些讲真话的用户提供激励，t y c o o n 可以达到高透明性和高公平性。 在网络流方面，早在1 9 5 5 年t e 哈里斯在研究铁路最大通量时就提出在一个 给定的网络上寻求两点问最大运输量的问题，这是学术界第一次提出了网络流相关 的问题。1 9 5 6 年，l r 福特和d r 富尔克森等人给出了解决这类问题的算法，从而 建立了网络流理论”。到目前为止，网络流问题已有5 0 多年的研究历史，人们在建 立较为完善的网络流问题理论的同时也开发了大量的算法。近年来，随着网络和计 算机科学的飞速发展，网络流问题得到了更深入的研究。历年来重要的国际理论计 算机科学会议如s t o c ，s a c 等都有网络流问题最新研究成果的报告。最大流问题 是网络流理论的重要组成部分，在实际中有许多应用，如电力系统的电力分配，交 通流控制及生态系统的食物链控制等等。 在计算市场均衡方面，1 8 9 1 年，i r v i n gf i s h e r 就提出了市场清算价格的问题一 包含买家和商品的市场，如何求出市场清算价格，以达到市场均衡【2 5 】。w a l r a s 也 同期提出了此问题 2 6 】。在a r r o w 和d e b r e u 使用k a k u t a n i 的不动点理论来证明均 衡价格的存在后，市场均衡价格的研究逐渐成为热点 2 7 】。f i s h e r ，a r r o w 和d e b r e u 的市场均衡模型被认为是数理经济学中的最经典的两个模型。后者被认为是前者的 通用模型。v i j a yv v a z i r a n i 撰写了多篇关于计算市场均衡的论文，提出了在多项式 时间内计算市场清算价格的算法 2 8 】。 组合拍卖是指在拍卖过程中，竞拍者可以对物品的组合进行竞拍，而不仅仅针 对单个物品的一种拍卖方式。近些年来，组合拍卖方法在房地产拍卖，货物运输， 华东师范大学硕士学位论文 公交线路，工业采购以及无线通信频谱分配方面也获得了人们越来越多的关注。如 x i ns u i 2 9 1 等提出了一种新的可调整的拍卖策略，允许拍卖者为了最大化预期效用 而频繁调整边际利润，特别是该调整是基于拍卖者自己在多轮组合拍卖中产生的拍 卖历史。组合拍卖一个非常著名的应用是一f c c 将组合拍卖机制引入频谱分配【3 0 1 。 1 3 解决方案 本文分析了网络资源的分配问题，并对资源的定价机制进行分析，将网络资源 分为可定价与不可定价两种。在此基础上，本文根据网络资源的特性，并结合实际 问题建立了通用的分配模型。 在可定价网络资源分配模型中，设计了资源计算方法，将资源分配转化网络流 模型，引入n i k h i l 等人提出的p r i m a l d u a l 算法来计算均衡价格，提出了可定价网 络资源的分配算法，使分配系统达到均衡，分配系统的参与者一资源提供者和消费 者均达到高收益。 对于不可定价的网络资源分配模型，本文引入了福利函数概念，设计了用户福 利函数，在此基础上引入算法博弈论中的组合拍卖方法，提出了基于组合拍卖的资 源分配算法，使分配系统达到高的全局社会福利，兼顾考虑了资源分配的有效性和 公平性。 1 4 本文的主要贡献 首先，分析网络资源特性，将其分为可定价和不可定价两类，并分别进行建模 分析； 其次，针对可定价的网络资源，结合实际的网络教学平台空间分配问题，引入 算法博弈论中基于网络流的均衡定价计算算法，设计了完整的资源分配方法：可灵 活计算的资源总量及基于网络流模型的资源分配算法；用j a 、，a 实现了该分配算法， 并开发了计算均衡价格的可视化工具，可以灵活调整资源相关参数，输出最优的资 源分配结果。 最后，针对不可定价的网络资源，结合实际的网络教学课程资源分配问题，设 计了用户福利函数，引入算法博弈论中的组合拍卖方法，提出了基于组合拍卖的资 6 华东师范大学硕士学位论文 源分配方法，将资源有效分配，并获得高社会福利。用j a v a 和c p l e x 结合实现 了该算法，并经过多次实验，得到实验数据，与常用的基于排名或信誉的分配算法 对比，分析得知该算法针对不可定价的网络稀缺资源的分配更为有效，并能获得高 社会福利，兼顾考虑了资源分配的效率与公平。 本文提出的网络资源分配算法思想具有扩展性。基于网络流模型的可定价网络 资源分配对_ 丁网络带宽分配、云计算空间分配与预留等具有应用空间；基于组合拍 卖的不可定价网络资源分配对于公益资源、公用资源的分配等亦有参考意义。 1 5 本文的组织结构 本文将网络资源分为可定价与不可定价两类，全文的组织结构如下： 第一章引言介绍选题的提出和研究背景，详细介绍了为何需要解决资源分配问 题，及为何引入资源定价，并结合国内外研究现状进行了深入阐述。同时介绍了本 文针对资源分配问题的解决方案及本文的主要贡献、组织结构。 第二、三章分别就可定价网络资源和不可定价网络资源的分配提出了相应算法， 其中第二章基于网络流模型的可定价资源分配算法研究，首先根据实际问题一网络 教学平台的空间资源分配问题，抽象出通用的可定价网络资源分配模型，并经过分 析演绎，将其转换为网络流模型，提出了可灵活调整参数的资源总空问计算公式， 并根据用户的影响参数计算出用户权值，引入n i k h i l 等提出的基于p r i m a l d u a l 算 法来计算资源的均衡价格，从而实现可定价网络资源系统完整的资源计算及分配。 本文采用j a 、，a 编程实现了计算均衡价格的可视化界面，可灵活设置影响资源计算、 分配的各个参数，从而实现可定价网络资源的有效分配。 第三章提出了基于组合拍卖的不可定价资源分配算法，首先根据实际问题一网 络教学平台的课程资源分配问题，分析了不可定价资源的特性，接着引入了社会福 利函数，讨论了资源分配的公平性问题。其次，介绍了算法博弈论与组合拍卖的基 本概念。接着，本文对不可定价资源进行了建模分析，设计了用户福利函数，引入 组合拍卖解决资源分配问题。最后，本文通过计算机模拟，生成一系列随机数据， 将基于组合拍卖的资源分配算法，与常用的优先级分配( 基于时间或信誉等) 算法 进行比较，得出本文提出的算法在稀缺的不可定价网络资源分配中，性能最佳。 最后，本文在第四章中进行了总结，并提出了进一步研究的工作。 7 华东师范大学硕士学位论文 第二章基于网络流模型的可定价资源分配算法 2 1 研究背景 可定价的网络资源是指能通过一定的定价机制，计算出资源的均衡价格，在分 配系统中合理分配给资源消费者，达到系统均衡。本章主要针对这类可定价的网络 资源，结合实际的网络教学平台空间分配问题，搭建了一个通用的网络空间分配模 型，利用网络流模型，引入算法博弈论中计算均衡价格的算法，探讨了网络空间容 量计算和分配的问题。在网络空间分配的同时，通过一定的激励机制，促进教学资 源的丰富与共享。 本章的组织结构如下：首先2 1 1 节提出了一个实际问题一网络教学平台的空间 资源分配问题，并在2 1 2 节中介绍了网络流模型的相关基础知识。结合网络教学 平台的空间分配问题，在2 2 节抽象出通用的可定价网络资源分配模型，并经过分 析演绎，将其转换为网络流模型，在2 3 1 节提出了可灵活调整参数的资源总空间 计算公式，在2 3 2 节根据用户的影响参数计算出用户的权值，引入n i k h i l 等提出 的基于p r i m a l d u a l 算法来计算资源的均衡价格，在2 3 3 节描述了可定价网络资源 系统完整的资源分配算法。在2 4 节中，采用j a v a 编程实现了可视化界面，可灵 活设置影响资源计算、分配的各个参数，从而实现可定价网络资源的有效分配。 2 1 1网络教学平台的空间资源分配问题 教育资源是指“那些可以提供给学习者使用，能帮助和促进他们学习的信息、技 术和环境。”【3 1 】根据我国教育资源建设技术规范，资源主要包括：媒体素材、 课件与网络课件、案例、文献资料等几类。 目前，人们多关注教学资源平台的建设开发，女h b l a c k b o a r d 、m o o d l e 已经颇为成 熟，最近g o o g l e 又引进m o o d l e 来加强g o o g l e 应用教育版套件。在教育资源的共享上， 2 0 0 1 年m i t 启动开放课程项目，通过o c w ( o p e n c o u r s e w a r e ) 网站 3 2 】，逐步把其所 开设的从本科到研究生教育各层次的课程资源放在网络上，供全世界的求知者和教 育者无偿享用，迄今为止m i t 已在网上免费开放课程1 9 0 0 f 3 。近年来，在开放教育 8 华东师范大学硕士学位论文 资源( o p e ne d u c a t i o n a lr e s o u r c e ) 运动的促进下，许多美国大学开始采取院校合作 和开放源代码的方式来共同开发所需要的一些应用系统，女l u p o r t a l ( 开放的大学校 园门户系统) ，c a s ( 校园网单点登录系统) ，s a k a i ( 开源的课程管理系统) ，d s p a c e ( 共享的大学知识库系统) ，o s p ( 学生电子档案袋系统) 。在我国，清华大学图 书馆从2 0 0 4 年开始进行了基于d s p a c e 的若干应用探索，主要包括：读者教育门户平 台的设计和开发，机构知识库的建设，外购电子资源长期保存的试验【3 3 】。在厦门 大学，厦大图书馆运用d s p a c e 系统来构建厦门大学机构存储系统，为厦门大学的教 学科研提供存储服务，并为厦门大学的教师和学生进行校内校外学习交流共享和利 用资源提供平台【3 4 。由北京航空航天大学计算机系、m 实验室、多家博物馆和图 书馆合作的中国数字博物馆项目( t h ec h i n ad i g i t a lm u s e u mp r o j e c o ，基于d s p a c e 系 统探讨数字资源的长期保存问题，并利用网格技术实现各大学数字博物馆的互联互 通和资源共享 3 5 1 。 人们为存储教学资源搭建了各种教学平台，也积极推动了资源的共享，促进了 师生教学相长。如上海财经大学自2 0 0 6 年引入b l a c k b o a r d 教学平台后，有9 4 的 教师使用教学平台上课，从而成为华东地区首先在本科课程教学中，全面应用数字 化教学平台的高校。截至2 0 0 8 年1 0 月，教学平台使用课程数和用户数有：课程5 6 8 4 门次，教师7 4 9 人，学生9 8 7 7 余人，平均日访问量9 4 1 7 次，最高日访问量2 2 0 4 7 次。 教师们反映上课再也不必带u 盘，所有的教学资源都在教学平台上，在教室直接连 接网络就可以使用课程资源，学生提交作业、教师检查、批改作业、测验都可在 b l a c k b o a r d 平台上进行；学院和教务处可随时统计抽查【3 6 】。清华大学网络学堂为 每位学生提供了虚拟个人网络空间，就是在网络上为用户提供一个存储空间及相关 服务，使用户在此空间里，可以根据自己的喜好来构筑有自己特色的工作环境，实 现方便快捷地访问常用的网络资源。并且在任意一台联网的机器上，用户都可以访 问到自己的虚拟网络空间，就像访问自己独占的一台机器上的空间一样。用户拥有 这样一个个性化空间，就可以实现移动学习一不论是在教室、实验室还是宿舍，都 可以进入自己的网上学屋自由学习【3 7 】。 但是在实际工作中，我们发现如何鼓励教师多上传高质量的教学资源，如何推 动教学资源的共享，及如何合理配置每位教师或课程的存储空间成了一大难题。例 如下面从一些常用的教学平台中截取的图所示，教学资源的存储空间大小该如何确 9 # 东帅m l n i 定，空间又该如何有效分配给一线的教师和学生呢? i i 二ei i ，i q i ! f j c 两4 姓目黼也竺墅l 矗鹾；i i 溢“+ 荆咧缒日蛳 口i m 龃蜘m * 。国再e 拄间容量睦塑旦：! ! jh i * 柚触目# 蛳。， 一 u 存储空间无# b 制 ；戢* 8 t e 舟h _ _k b ；口# 4 十t # z * i 十* $ dk b 。 o 挺交 * t 敞i * 。j r * * 。 辫耐i 2 1 目 遇 o 存储空间霉量巨五垂口m o 存储蜘无限制 0 薮认空问限额 为这些文件夫设置默认空间限额。输儿“1 表示无限眼额。 默认空问服顿i j 1 m b 国2 1教学平台空m 设置组闰 尽管计算机存储技术迅猛发胜，存储价格不断r 降，但对于有几千名教师和几 万名学t 的大学而言，采购足够的存储空间仍是一笔币小的丌支。在立令的海量数 据前，存储已是高校信息化的主要开支之一了，并且随着计算机存储技术的发展， 最新的存储技术和设备层出不穷，因此购买合理大小的存储空间将为高校节约开支， 有效利用教育经费。在购买丁存储设备后，如何让存储有效利用亦足一个值得讨论 的问题。为每位老师或每门课程平均分配一个单位空间，看似台理，其空凼为每位 老师或母门课程的学科性质和个人信息修养不h ，对空问大小的要求是不同的，对 分配到的空间的利片