（计算机软件与理论专业论文）用户自私行为对网络性能影响的研究.pdf

摘要 摘要 计算机网络是互连的计算机及其它相关设备构成的整体，它使众多的计算机可 以互相通信，从而共享资源和信息。一方面，网络性能决定了用户的行为，比如， 用户可以根据网络性能决定否加入该网络；另一方面，随着计算机技术和网络技术 的进一步发展，用户的行为也对网络性能产生了越来越重要的影响。本文研究了无 线网络和p 2 p 网络中用户的自私行为及其对网络性能的影响，主要研究成果如下： 1 无线局域网中的自私功率控制问题：本文研究了在满足吞吐量要求的前提 下，节点自私的功率控制行为及其对无线局域网性能的影响。针对非相干频移键控 ( n o n c o h e r e n tf r e q u e n c ys 1 1 i rk e y i n g ，n f s k ) 调制方式，本文证明了在给定信道 状况的前提下，单一链路存在最优的发送功率以及相应的最优传输策略。假定每个 单位时间有且仅有一个链路可以调整传输策略，且该链路始终选择对自己最有利的， 本文提出了一个重复的动态博弈。由于链路会将发送功率从干扰较高的时间段移到 干扰较低的时间段，该博弈在某些情况下无法收敛，因此本文引入惩罚函数以确保 收敛，并研究了不同惩罚函数的性能。模拟实验结果表明，惩罚函数越大，博弈收 敛越快，但是博弈收敛的速度与稳定状态时能量消耗的大小没有直接联系。 2 无线多跳网络中的自私速率调整问题：本文研究了在满足吞吐量要求的前 提下，节点自私的速率调整行为及其对无线多跳网络性能的影响。针对i e e e8 0 2 1 1 无线多跳网络，本文证明了在给定信道状况的前提下，单一链路存在最优的传输策 略。假定每个单位时间有且仅有一个链路可以调整传输策略，且该链路始终选择对 自己最有利的，本文提出了一个重复的动态博弈。由于自私的速率调整行为的存在， 链路调度顺序会影响吞吐量要求的可行性以及总功率消耗，因此本文引入定价函数， 促使链路公平有效地分享信道。模拟试验结果表明，采用定价函数后不仅导致了更 多的可行解，同时也降低了总功率消耗。 3 b i t t o r r e n t 系统的建模：在b i t t o 仃e n t 系统中，p e e r 的到达和离丌导致了 p e e r 的动态性；此外，p e e r 通过乐观疏通( o p t 面i s t i cu n c h o k i n g ) 机制和针锋相对 ( t i t f 孤t a t ) 原则选择邻居，由此导致了连接的动态性。本文研究了p e e r 的动态性 和连接的动态性，发现具有不同连接数的p e e r 在选择邻居时有不同的行为。因此本 摘要 文定义了p e e r 状态，以及由系统中所有p e e r 的状态决定的系统状态，并计算出动态 因素发生时，系统在不同状态间的跳转率，由此得到一个基于马尔可夫链的随机模 型。基于此模型，本文研究了系统在稳定状态时的性能。模拟实验验证了模型的精 确性，并发现系统稳定时，文件大小对p e e r 实际使用的平均连接数有重要影响。 关键词： 博弈论，无线网络，自私行为，b i t t o r r e n t ，随机模型 j i a b s t r a c t a b s t r a c t a c o m p u t e rn e t 、v o r ki sac o l l e c t i o no fc o m p u t e r s 砒l do t h e rr e l a t e dd e v i c e sw h i c ha r e c o n n e c t e dt oe a c ho t h e r t h en e t 、v o r ka 1 1 0 w sc o m p u t e r st oc o m m u m c a t e 、衍t he a c ho t h e r a n ds h a r er e s o u r c e sa 1 1 dm f o m a t i o n o nm eo n eh a n d ，t h ep e r f b m l a n c eo fn e “，o r k sc a n d e t e n n i n et 1 1 eu s e rb e h a v i o r s f o re x a m p l e ，u s e r s 、v i l ld e c i d ew h e t h e rt oj o 缸an e r k a c c o r d j n gt on l en e t 、v o r kp e r f o 珊a n c e ；o nm eo m e rh a n d ，d u et od e v e l o p m e m so f c o m p u t e rt e c l m o l o g i e sa n d n e t 、v o r kt e c h n o l o g i e s ，t 1 1 eu s e r b e h a v i o r sh a v em o r ea n dm o r e s i g m f i c a n ti 1 1 1 p a c t so nt h ep e r f o m l a n c eo fn e t v ，o f k s t k sm e s i ss t u d i e st h eu b e rb e h a v i o r s i nb o m 、i r e l e s sn e i k sa n dp e e 卜t o p e e r ( p 2 p ) n e 咖r k s ，a n dt h e i rh p a c t so nt h e n e 帆l r kp e 面m a n c e t h em a i nr e s u l t so f m et h e s i sa r ea l sf o l l o w s ： 1 s e l f i s hp o w e rc o n t r o ii nw i r e i e s sl o c a la r e an e t w o r l s ：t h j st 1 1 e s i ss t u d i e st h e s e l f i s hp o w e rc o n c r o lb e h a v i o ra n di t si m p a c to nt h ep e r f b m l a n c eo faw i l e l e s s1 0 c a la r e a n e 咖r k ( w l 触d ，w h e r ee a c hl i l l l ( i su 1 1 d e ra 衄o u g h p u tr e q u i r e m e n t e m p l o y i n gt 1 1 e m o d u l a t i o ns c h e m en o n - c o h e r e n tf r e q u e n c ys m r k e y i n g ( n f s k ) ，i ti sp r o v e dm a tt h e r e i sa no p t i m a l t r a n s m i s s i o np o w e ra r l da c o r r e s p o n d i n go p t i m a l 破m s m i s s i o ns t r a t e g yf o ra l i n k 谢mf - e dc h 珊e lc o n d i t i o n ar e p e a t e dd y n a m i cg 锄ei sp r o p o s e d ，a s s m i n g 也a t m e r ei so m yo n el i n kw h j c hc a na d j u s ti t st r a n s m i s s i o ns 仃a t e g ) ，i ne a c hu n i tt 血ea 1 1 dt h e 1 i n ka l w a 【y s a d o p t sm es e l f o p t i m a ls 仃a t e g ) r s 沁el i l l l ( s a r em o t i v a t e dt om o v e 倾n s m i s s i o np o w e rf b mh i 曲i n t e r 危r e n c ed u r a t i o n st o1 0 wi n t e r f 色r e n c eo n e s ，t k sg a m e c a nn o tc o n v e 玛ei 1 1s o m ec a s e s 。ap e m l t y 如n c t i o ni si i 灯o d u c e dt oe n s u r ec o n v e 唱e n c e a n dm ep e r f o 肌a n c eo fv a r i o u sp e n a l t ) ，劬c t i o l l si si 1 1 v e s t i g a t e d s i m u l a t i o nr e s u l t ss h o w t h a th e a v i e rp e n a l t ) ，l e a d st of a s t e rc o n v e r g e n c e ，b u th a sn od i r e c te 虢c to nt h ee n e r g y c o l l s u m p t i o no fm es t e a d ys t a t e 2 s e i s hr a t ea d a p t a t i o ni nw i r e i e s sm u l t i - h o pn e m o r l s ：1 1 1 i sn l e s i ss m d i e st 1 1 e s e l f i s hr a t ea d a p t a t i o nb e h a v i o ra n di t sh p a c to nm ep e r f o m a j l c eo fa 、诎。e l e s sm u l t i - h o p n e t 、o r k ，w 】托r ee a c hl i n l ( i su n d e rat h r o u 曲p u tr e q u i r e m 锄t h 1a ni e e e8 0 2 11 、v i r e i e s s m u l t i - h o pn e m o r k ，i ti sp r o v e dt h a tt h e r ei sa 1 1o p t h a lt r a n s m i s s i o ns n - a t e g yf o ral 破 a b s t r a c t 、v i t hf i x e dc h a n n e lc o n d i t i o n ar 印e a t e dd y n a m i cg 锄ei sp r o p o s e d ，a s s u m i n gt l a tt h e r e i s0 1 1 1 yo n el i n kw m c hc a na d j u s ti t s 缸孤s m i s s i o ns t r a t e g yi ne a c hu m tt i m ea n dt 1 1 el i n l ( a l 、v a y sa d o p t st h es e l f o p t h l l a ls t r a t e g y d u et ot h es e l f i s hr a t ea d a p t a t i o nb e h a v i o r ，m e l i n ks c h e d u l i n go r d e r 析e c t st h ef e a s i b i l i t ) ，o ft h et h r o u 曲p u tr e q u i i - e m e n ta s 、e n2 l st h e t o t a lp o w e rc o n s u m p t i o n ap r i c i l l gf 岫c t i o ni si n t r o d u c e dt om o t i v a t el i n k st os h a r em e c h 锄e lf a i r l ya n de m c i e m l y s i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e da p p r o a c hl e a d st o n o to i l l ym o r e 佗a s i b l es o l u t i o n s ，b u ta l s ol e s st o t a lp o w e rc o n s u m p t i o n 3 as t o c h a s “cm o d e lf o rb i t l l o r r e n ts y s t e m s ：i nb i t l b r r e ms y s t e m s ，t h ea m v a l a n dd e p a 】嚏u r eo fp e e r s1 e a dt op e e rd y n 甜n i c s ；p e e r sc h o o s en e i g h b o r sa c c o r d i n gt om e m e c h a n j s m0 p t h i l i s t i cu n c h o k i l l ga n dt h ep m c i p l et i t - f o 卜t a t ，h i c hk u r sc o n n e c t i o n d y n 锄i c s n i s 也e s i ss t u d i e st h ep e e rd y m m i c sa n dt 1 1 ec o 】1 n e c t i o nd y i l 锄i c s ，a n di ti s o b s e e dt h a tp e e r s 州t hc 衄宅r e n tc o n n e c t i o nn u m b e r sb e h a v ed i r e n t l yw h i l ec h o o s m g n e i g h b o r s s o 、v ed e f i n ep e e rs t a t e ，a r l ds y s t e ms t a t ew m c hi sc o m p o s e do f t h ep e e rs t a t e s f o ra l lt h ep e e r si nt h es y s t e m w ec o m p u t et h e 订a n s i t i o nr a t e sb e t w e e nd i f r e r e n ts y s t e m s t a t e sw h e nd y n a m i c sh a p p e n ，a n dt h e ng e tas t o c h a s t i cm o d e lb a s e do nm a r k o vc h a i n u s i n gt h i sm o d e l ，t h es y s t e mp e 哟衄a n c ea tm es t e a d ys t a t ei ss 伽i e d t h ea c c u r a c yo f t h em o d e ii sv e r i f i e db ys i r l l u l a t i o n ，a n di t i ss h o w nt h a tt h ef i l es i z eh 2 l s s i 鲥f i c a n t i n n u e n c eo nt h ea v e r a g e 眦m b e ro fc o 衄e c t i o i l sp e rp e e ra tm es t e a d ys t a t e k c y w o r d s ： g a m et h e o 吼w i r e l c s sn c t 、) ，o r l s ，s e m s hb e h a v i o r s ，b i t t o r r c n t ， s t o c h a s t i cm o d e l i v 中国科学技术大学学位论文原刨性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过 的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说 明。 作者签名：堑签字日期：型垡：笸：至 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有 学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文 的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电 子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 口保密( 年) 作者签名：勉导师签名： 签字日期：捌：至 签字日期：芝塑拿! ! l 第一章绪论 绪论 本章摘要：随着计算机技术和网络技术的发展，一方面，网络 生 能决定了用户的行为，另一方面，用户行为也对网络性能产生了 越来越重要的影响。本文主要研究了后一方面的内容。本章首先 概述了计算机网络，其中包括无线网络与p 2 p 网络，然后简单介 绍了无线网络与p 2 p 网络中网络性能与用户行为之间的相互影 响，最后介绍了本文的研究内容和成果。 1 1 计算机网络简介 计算机网络( 以下简称网络) ，就是把分布在不同地理区域的计算机与专门的 外部设备，通过通信线路互连成一个规模大、功能强的系统，从而使众多的计算机 可以方便地互相传递信息，共享信息资源。一般来说，网络可以提供以下主要功能： 资源共享：网络的出现使资源共享变得简单，交流的双方可以跨越时空的障碍， 随时随地传递信息。 信息传输与集中处理：数据可以通过网络传递到服务器，由服务器集中处理后 再回送到终端。 负载均衡与分布处理：比如，一个大型h n e m e t 内容提供商( i m e m e tc o m e n t p r o v i d e r ) 为了支持更多的用户访问他的网站，他可以在全世界多个地方放置内 容相同的w w w ( w b r l dw i d ew r e b ) 服务器，并通过一定的技术使不同地域的 用户看到相同的页面，这样就实现了服务器的负荷均衡，同时也节省了用户的 第一章绪论 路由代价。 综合信息服务：网络的一大发展趋势是多样化，即在一套系统上提供集成的信 息服务，包括来自政治、经济等各方面的资源，甚至还提供多媒体信息，如图 象、语音、动画等。在多样化发展的趋势下，许多新的网络应用不断涌现，如 电子邮件、网上交易、视频点播、联机会议等。 根据不同的标准，网络可以分为不同的类型。比如，按照覆盖范围，网络可分 为局域网、城域网、广域网等；按照拓扑结构，网络可分为总线型、星型、环型、 树型、网状型等：按照交换技术，网络可分为电路交换网、报文交换网、分组交换 网等；按照传输介质，网络可分为有线网、无线网等；按照网络模型，网络可分为 对等网( 即p 2 p 网络) 、c s ( c l i e 州s e e r ) 模式、b s ( b r o 、v e r s e e r ) 模式等。 本文主要研究了无线网络和p 2 p 网络，希望通过对这些网络的建模及性能分析， 研究用户自私行为对网络性能的影响，从而提出相应的方案来优化网络性能。以下 是无线网络和p 2 p 网络的简介。 1 1 1无线网络 随着信息技术的不断发展，人们对移动通信的实时性、灵活性以及便捷性的需 求也越来越高。近年来，移动通信无论是技术还是应用上都得到了飞速发展和普及， 各种新技术和新产品层出不穷。蜂窝移动通信系统的发展历程就是最有力的证明， 在短短十几年时间里，它就完成了从第一代到第二代、二代半的跨越，现在正向第 三代系统演进。与此同时，无线局域网( w n l e s sl o c a l 觚an e 咖r k s ， w l a n s 【1 】【2 】1 3 】【4 】【5 】吲和h i p e r l a n 【7 】) 、蓝牙技术( b l u e t o o n l ) 【8 】、家庭无线网( h o m e r f ) 【明等多种移动通信新技术也纷纷涌现。这些技术使得人与人之间的通信更加方便快 捷，同时也丰富和改变着人们的生活方式。 1 1 1 1 无线局域网 无线局域网是采用无线传输介质的计算机局域网，是一个使用无线多址信道的 分组交换网络，其特点是成本低，灵活性、移动性强，吞吐量高，通信可靠。高速 与移动性是目前局域网发展的两个主要方向。 2 第一章绪论 无线局域网是移动性发展的主要内容。随着互联网络的迅猛发展，无线技术是 未来的热门技术之一，同时，作为基础物理接口的无线局域网技术也是实现移动计 算网络与“个人通信服务”( p e r s o n a lc o m m u m c a t i o n ss e r v i c e ，p c s ) 的关键技术之 一。第一台应用无线通信的计算机是8 0 年代初在市场上出现的，随后的无线计算机 网络主要采用窄带技术；9 0 年代以来，随着微蜂窝结构的无线网络技术、扩频技术 的采用，特别是相关标准的制定与颁布，无线局域网技术迅速发展，目前己经到了 发展的关键时期。 传统上，无线局域网是有线局域网的一种补充，是在有线网基础上发展起来的， 它的大部分应用也是有线局域网的扩展和替换，比如，网络共享处理能力和文件服 务。它的出现正是基于有线局域网发展中固有的缺陷，一是布线繁琐，改线工程量 大，线路易损坏，不易连接远程站点，有时还无法实现方便的线路连接等；二是无 法支持移动设备对网络的访问要求，其站点不可移动。无线局域网的灵活与方便正 好能够克服这些缺点。无线局域网不仅解决了有线局域网大量有关组网与接入更大 范围网络的难题，也方便地拓展了网络信息服务的能力，特别是近年来客户终端的 便携化倾向产生了对移动通信的巨大需求，无线局域网使用户在需要的时候方便地 获取所需信息。 1 1 1 2 无线多跳网络 无线多跳网络( w i r e l e s sm u l t i h o pn e t 、v o r k s ) 是一种无基础设施( i n 丘a s t m c t u r e 1 e s s ) 的无线网络，网络中的某些或全部节点为可移动节点。某些应用场景，通信基 础设施的部署无法快速完成，或非常昂贵，或完全不可能，在这种情况下，无线多 跳网络无基础设施的特点使这些场景中的网络应用有重要意义。 无线多跳网络为典型的分布式系统，其中的无线节点自身具有互连能力，收发 双方可利用其它节点转发数据包，以完成单一节点收发半径外的通信。无线多跳网 络既可独立自动组织成网络，也可以通过网络中特定节点与有线网络通信，作为有 线网络的扩展和延伸。由于其低成本、自组织以及良好的鲁棒性，无线多跳网络已 得到学术界和产业界的广泛关注，研究成果和产品层出不穷，并逐渐在人们的日常 第一章绪论 生活中得到应用。从近些年的观察发现，无线多跳网络代表了未来移动通信领域的 发展方向之一，必将吸引人们更多的关注。 1 1 2p 2 p 网络 p 2 p ( p e e r - t o p e e r ) 技术，即对等网络技术，是一种在不同p c ( p e r s o n a lc o m p u c e r ) 用户之间，不经过中间设备( 如服务器) 而直接交换信息的技术，它实质上是一种 新的网络结构思想。目前网络中占据主导地位的是基于客户端服务器( c l i e 州 s e r v e r ) 的网络结构，p 2 p 与其本质区别是整个网络结构中不存在中心结点( 或中心 服务器) 。p 2 p 节点之间的关系是平等的、直接联系的。p 2 p 节点具有处理信息和提 供信息等功能，即每台p c 可以直接连接到其它p c ，并进行文件交换，而不需要连 接到服务器上再进行浏览和下载。p 2 p 技术弱化了服务器的作用，甚至取消了服务 器，任意两台p c 互为服务器，同时又是客户机。p 2 p 利用个人电脑的能量和资源， 而不是强大的中央服务器，分享的资源通过大量的用户保证高可用性。p 2 p 是互联 网研究的重要领域，它对i t 产业也是非常重要的，因为围绕着p 2 p 网络新型的商 业模型已经在逐步建立中。 p 2 p 的发展可以被划分为三代：第一代是以n a p s t e r l l 0 】为代表的，还在使用中央 服务器管理的p 2 p ，这一代的p 2 p 生命力十分脆弱，只要关闭服务器，网络就死了， 后来因为版权法被封了；第二代分布式p 2 p 没有中央服务器，但是速度太慢，其代 表是m u t e l i a f l l 】：而第三代为混合型，采用分布式服务器。目前我国流行的 b i f r o r r e m 【5 i 】，电驴【5 卯，讯雷( 5 3 j 就是属于这类。 p 2 p 网络已经被越来越多的用户所使用，并且成为了一种标准的文件发布模式， 因为它的结构使得网络具有很好的可扩放性，相对于普通网络有更高的效率和更好 的性能。p 2 p 网络是无中心、自组织、动态的网络，并且为传统的服务器客户端模 式提供了另外一种选择。在“纯粹”的p 2 p 系统中，每个节点都扮演服务器和客户 端的角色，他们在没有任何集中控制的情况下分享资源，但事实上，大部分p 2 p 应 用都有某种程度上的集中控制，它们至少会集中用户列表，b i t t o r r e n t 系统就是其中 的一种。 在b i t t o r r e n t 系统中，至少需要一个1 h c k e r 服务器和一个种子节点( s e e d ) 。 t r a c k e r 服务器帮助客户端( p e e r ) 之间相互建立连接。而种子，通常是第一个向 4 第一章绪论 t r a c k e r 服务器注册的客户端，注册后它就开始进入循环，等待为别人提供文件，也 就是说，第一个种子只负责上传文件。一旦有一个种子向t r a c k e r 服务器注册后， 其它p e e r 就可以取得种子的信息，从而与种子建立连接，并从种子处下载文件。由 于原始的文件只有种子拥有，所以说，种子至少要上传原始文件的一份完整拷贝。 如果又有一个种子加入进来，那么它也可以和p e e r 建立连接，然后p e e r 从这两处获 取文件。 p 2 p 下载解决了单点下载难以突破的服务器带宽瓶颈，从而使下载速度空前提 高，充分利用了闲置的个人p c 网络带宽和存储空间，使得媒体资源文件的获取变 得更加快捷。 1 2 网络性能与用户行为 随着计算机技术和网络技术的发展，网络性能与用户行为之间相互影响，由此 产生了非常密切的关系。一方面，网络性能决定了用户的行为，比如，用户可以根 据网络性能决定否加入该网络；另一方面，随着个人计算机性能的增强以及网络中 用户数量的增加，用户行为对网络性能产生了越来越重要的影响。 1 2 1无线网络中网络性能与用户行为 ( 1 ) 网络性能决定用户行为 众所周知，目前我国的移动运营商为中国移动、中国联通、中国电信三家。3 g 发牌以后，各家运营商开始投入到轰轰烈烈的3 g 网络、设备、内容和服务建设大 潮中。其中，中国移动计划2 0 0 9 年投资5 8 8 亿元，新建t d s c d m 基站约六万个， 年底将在2 3 8 个地级城市提供3 g 服务，占全国地级城市数量的百分之七十以上， 其中东部省( 市) 的地市将实现全覆盖；中国联通2 0 0 9 年首期投资3 0 0 亿元左右， 计划今年上半年在5 5 个省会城市及经济比较发达的大中城市提供3 g 试商用服务， 年底将服务范围扩大到2 8 2 个城市；中国电信正在对c 网进行网络升级和优化，2 0 0 9 年首期投资约3 0 0 亿元，计划3 月底将在共1 0 0 个大中城市提供3 g 服务。各家运 营商之所以加大投入，是因为各大中城市的用户预期将在2 0 0 9 年下半年逐渐转移成 3 g 网络的用户，因此，各家运营商希望通过提高自己的网络性能，利用优质的服务 第一章绪论 及相对低廉的价格赢得用户。 ( 2 ) 用户行为影响网络性能 由于无线网络中的终端( 即节点) 共用无线信道，如果距离较近的节点同时发 送数据，那么在接收节点处会产生干扰，最终导致数据包的丢失。特别在无线多跳 网络中，由于节点的通信覆盖范围有限，两个无法直接通信的节点需要借助其他节 点的分组转发进行数据通信，因而无线多跳网络中节点的协作程度决定了网络的性 能。 由于移动终端一般由电池供电，因此人们一般都希望移动终端在不充电的情况 下能够连续工作尽量长的时间。然而在目前的技术条件下，电池容量平均每十年只 能提高2 0 左右，受制于这种限制，单位重量的电池容量很难在短期内有大幅度的 提高。与此同时，随着移动终端性能的提升和功能的加强，对电能的需求也在不断 上升。因此，在无线网络中，节点会通过功率控制和速率调整达到减少能量消耗和 提高吞吐量的目的。一般来说，发送速率越高，所需的发送功率就越大，因而发送 节点产生的干扰范围也越大，因此会降低附近链路的性能( 比如吞吐量) ，所以，当 每个发送节点都采用最高的发送速率时，网络中的总吞吐量可能并不是最大的。 在无线网络中，很有应用都有吞吐量要求，比如v o i c eo np ( v o p ) ，实时流媒 体等。对于这些应用，如果实际的接收速率小于吞吐量要求，应用的质量会受到严 重影响；反之，如果接收速率大于吞吐量要求，多余的带宽会被浪费。一般来说， 接收速率和能量消耗是矛盾的，更大的接收速率意味着更多的能量消耗，因此节点 会通过功率控制和速率调整，使接收速率刚好达到吞吐量要求，以此降低能量消耗。 喜 邕2 奄i 卜 霎t 辎 时间( s ) 圣 邕2 褂 霎t 鲻 图1 1 两种传输策略 6 时间( s ) 第一章绪论 考虑如下问题：假如某链路的吞吐量要求为1 m b p s ，它有两种传输策略可供选 择( 见图1 1 ) ： 1 ) 采用接收速率1m b p s ，并一直占用信道； 2 ) 采用接收速率2m b p s ，并占用一半的信道时间。 这两种策略都能满足链路的吞吐量要求，但是我们有如下疑问： 哪一种策略消耗的能量更少? 如果所有链路都采用对自己最有利的传输策略，这种行为会对网络性能产生什 么样的影响? 本文回答了上面提到的问题，本文分别在无线局域网和无线多跳网络中研究了 在满足吞吐量要求的前提下，节点自私的功率控制行为和速率调整行为，及其对网 络性能的影响。 1 2 2p 2 p 网络中的网络性能与用户行为 ( 1 ) 网络性能决定用户行为 在p 2 p 网络方面，目前流行的p 2 p 软件有b i t t o 玎e n t 【5 、比特精灵( b i t s p i r i t ) 【5 2 】、迅雷【5 3 】、电驴( e m u l e 【5 4 1 或e d o n l ( e y 【5 5 】) 、m a z e 【5 6 1 、p p l i v e 【5 7 1 、p p s 仃e 锄例等。 当人们需要下载某个文件时，会根据自己的网络状况，以及各p 2 p 软件提供的内容 及服务质量进行选择，因此在p 2 p 网络中，网络性能决定了用户的归属。 ( 2 ) 用户行为影响网络性能 在p 2 p 网络中，由于私有性和保密性的关系，网络中大部分p e e r 都是匿名存在 的，因而难免会存在一些恶意p e e r ，它们会欺骗或攻击网络中其它p e e r ：同时，也 存在一些自私p e e f ，它们只下载网上的共享资源，而不共享和上传本地资源。有数 据表明，8 0 的e d o n l ( e y 用户不共享任何资源，大概6 0 的m a z e 用户不上传资源， 有的用户则把热门的资源移出共享区而只保留非热门资源，以达到减少自身负载的 目的。 在b i t t o 玎e n t 系统中，p e e r 通过乐观疏通( o p t i m i s t i cu n c h o k i n g ) 机制和针锋相 对( t i t - f o r - 1 a t ) 原则选择邻居。每个p e e r 一直与固定数量( 一般是4 个) 的其它 第一章绪论 p e e r 保持疏通( u n c h o k e ) 。每个p e e r 会给若干个其它p e e r 提供上传服务，这些p e e r 是曾经给此p e e r 提供最大下载速率的p e e r ，也就是说，p e e r 严格地根据当前的下载 速率来决定应该与哪些p e e r 保持疏通，应该拒绝给哪些p e e r 提供上传服务。 如果只是按照t i t - f o r 1 、a t 原则为提供最好下载速率的p e e r 提供上传，那么会存 在如下两个问题： p e e r 没有办法来发现那些空闲的连接是否比当前正使用的连接更好； 刚加入系统的p e e r 由于自身没有任何资源可以上传给别的p e e r ，因此这些p e e r 也无法从别的p e e r 下载到它想要的资源。 为了解决上述问题，在任何时候，p e e r 还会保持一个o p t i m i s t i cu n c h o k m g 连接，即 p e e r 会随机选择一个请求下载的p e e r 进行上传，并不考虑这个p e e r 过去的上传速率。 由此可知，p e e r 会根据其它p e e r 的上传带宽建立或断开连接，由此导致了连接的动 态性。 另一方面，p e e r 的到达和离开导致了p e e r 的动态性。本文研究了p e e r 的动态性 和连接的动态性，发现具有不同连接数的p e e r 在选择邻居时有不同的行为。因此本 文通过研究这些动态因素，得到一个基于马尔可夫链的随机模型，并基于此模型研 究系统在稳定状态时的性能。 1 3 本文的主要研究内容和贡献 本文分别研究了无线网络和p 2 p 网络中用户行为及其对网络性能的影响，其主 要研究内容和贡献如下： ( 1 ) 无线局域网中的自私功率控制问题 在无线网络中，节点可以通过功率控制达到减少能量消耗和提高吞吐量的目的。 一般来说，发送功率越大，吞吐量越大，然而产生的干扰也越大，因而会降低附近 链路的性能( 比如吞吐量) 。针对该问题，本文研究了在满足吞吐量要求的前提下， 节点自私的功率控制行为及其对无线局域网性能的影响。 针对非相干频移键控( n o n - c o h e r e n tf r e q u e n c ys m rk e y i n g ，卜盯s k ) 调制方式， 本文证明了在给定信道状况的前提下，单一链路存在最优的发送功率以及相应的最 优传输策略。假定每个单位时间有且仅有一个链路可以调整传输策略，且该链路始 第一章绪论 终选择对自己最有利的，本文提出了一个重复的动态博弈。由于链路会将发送功率 从干扰较高的时间段移到干扰较低的时间段，该博弈在某些情况下无法收敛，因此 本文引入惩罚函数以确保收敛，并研究了不同惩罚函数的性能。模拟实验结果表明， 惩罚函数越大，博弈收敛越快，但是博弈收敛的速度与稳定状态时能量消耗的大小 没有直接联系。 ( 2 ) 无线多跳网络中的自私速率调整问题 在i e e e8 0 2 1 1 无线网络中，物理层支持多速率，节点可以通过功率控制和速率 调整来降低能量消耗。一般来说，发送速率越高，所需的发送功率就越大，因而发 送节点产生的干扰范围也越大，因此会降低附近链路的性能。针对该问题，本文研 究了在满足吞吐量要求的前提下，节点自私的速率调整行为及其对无线多跳网络性 能的影响。 针对正e e8 0 2 1 1 无线多跳网络，本文证明了在给定信道状况的前提下，单一链 路存在最优的传输策略。假定每个单位时间有且仅有一个链路可以调整传输策略， 且该链路始终选择对自己最有利的，本文提出了一个重复的动态博弈。由于自私的 速率调整行为的存在，链路调度顺序会影响吞吐量要求的可行性以及总功率消耗， 因此本文引入定价函数，促使链路公平有效地分享信道。模拟试验结果表明，采用 定价函数后不仅导致了更多的可行解，同时也降低了总功率消耗。 ( 3 ) b i t t 0 玎e m 系统的建模 在b i t t o r r e m 系统中，p e e r 的到达和离开导致了p e e r 的动态性；此外，p e e r 通 过乐观疏通( o p t i m i s t i cu n c h o b n g ) 机制和针锋相对( t i t - f o r - 1 a t ) 原则选择邻居， 由此导致了连接的动态性。 本文研究了p e e r 的动态性和连接的动态性，发现具有不同连接数的p e e r 在选择 邻居时有不同的行为。因此本文定义了p e e r 状态，以及由系统中所有p e e r 的状态决 定的系统状态，并计算出动态因素发生时，系统在不同状态间的跳转率，由此得到 一个基于马尔可夫链的随机模型。基于此模型，本文研究了系统在稳定状态时的性 能。模拟实验验证了模型的精确性，并发现系统稳定时，文件大小对p e e r 实际使用 的平均连接数有重要影响。 9 第一章绪论 1 4 本文的组织 本文的剩余部分是这样组织的： 第二章简单介绍了相关的数学分析工具；第三章研究了无线局域网中的自私功 率控制问题；第四章研究了匝e e8 0 2 1 1 无线多跳网络中的自私速率调整问题；第 五章研究了b i t t o r r e n t 系统的建模；第六章为全文的总结，并提出了些未来的研 究方向。 l o 第二章数学分析工具 2 数学分析工具 本章摘要：本文利用博弈论及马尔可夫链的知识来分析网络中的 用户行为，本章简单介绍了博弈论和马尔可夫链的一些基本概 念。 2 1 数学分析工具简介 本文利用博弈论及马尔可夫链的知识来分析网络中的用户行为。下面简单介绍 一下博弈论和马尔可夫链的相关知识。 2 1 1 博弈论简介 博弈论( g a m et h e o 秽) 【12 1 ，有时也称为对策论，或者赛局理论，它是现代数学 的一个新分支，也是运筹学的一个重要组成内容。按照2 0 0 5 年因对博弈论的贡献而 获得诺贝尔经济学奖的r o b e r ta u m a n n 教授的说法，博弈论就是研究互动决策的理 论。所谓互动决策，即各行动方( 即局中人) 的决策是相互影响的，每个人在决策 的时候必须将他人的决策纳入自己的决策考虑之中，当然也需要把别人对于自己的 考虑也要纳入考虑之中在如此迭代考虑情形进行决策，选择最有利于自己的策 略。 2 1 1 1 博弈要素 一般说来，博弈的要素包括以下几个方面： 1 1 第二章数学分析工具 局中人( p l a y e r ) ：在一场竞赛或博弈中，每一个有决策权的参与者成为一个局 中人。只有两个局中人的博弈称为“双人博弈”，而多于两个局中人的博弈称为 “多人博弈”。 策略( s t r a t e g y ) ：一局博弈中，每个局中人都有可选择的实际可行的完整的行动 方案，即方案不是某阶段的行动方案，而是指导整个行动的一个方案。一个局 中人的一个可行的自始至终全局筹划的行动方案，称为这个局中人的一个策略。 如果在一个博弈中，局中人有有限个策略，则称为“有限博弈”，否则称为“无 限博弈 。 支付( p a y o 毋：一局博弈结局时的结果称为支付。每个局中人在一局博弈结束时 的支付，不仅与该局中人自身所选择的策略有关，而且与全局中人所取定的一 组策略有关。所以，一局博弈结束时每个局中人的“支付是全体局中人所取 定的一组策略的函数，通常称为支付函数。 次序( o r d e r ) ：各博弈方的决策有先后之分，且一个博弈方要做不止一次的决 策选择，就出现了次序问题。其它要素相同但次序不同，博弈就不同。 均衡( e q u i l i b r i u m ) ：均衡是平衡的意思，在经济学中，均衡意即相关量处于稳 定值。在供求关系中，某一商品市场如果在某一价格下，想以此价格买此商品 的人均能买到，而想卖的人均能卖出，此时我们就说，该商品的供求达到了均 衡。所谓纳什均衡，它是一稳定的博弈结果。 2 1 1 2 纳什均衡 纳什均衡( n a s he q u i l i 嘶u m ) 是指，在一策略组合中，所有的参与者面临这样 一种情况，当其他人不改变策略时，他此时的策略是最好的。也就是说，此时如果 他改变策略，他的支付将会降低。在纳什均衡点上，每一个理性的参与者都不会有 单独改变策略的冲动。 纳什均衡点存在性证明的前提是“博弈均衡偶”概念的提出。比如，在双人博 弈中，当局中人a 采取其最优策略a ，局中人b 也采取其最优策略6 ，如果局中 人仍采取6 ，而局中人a 却采取另一种策略口，那么局中人a 的支付不会超过他采 取原来的策略口的支付，这一结果对局中人b 亦是如此。双人博弈中的“均衡偶” 的定义为：一对策略策略，( 属于局中人a 的策略集) 和策略6 ( 属于局中人b 的策略集) 称之为均衡偶，对任一策略口( 属于局中人a 的策略集) 和策略6 ( 属 1 2 第二章数学分析工具 于局中人b 的策略集) ，总有：对于局中人a ，偶对( 口，6 ) 获得的支付小于偶对( 口，6 + ) ； 对于局中人b ，偶对f ，6 ) 获得的支付小于偶对 ，6 + ) 。在双人博弈中，这一均衡偶 就称为纳什均衡点。 2 1 1 3 囚徒困境 在博弈论中，一个著名的例子是“囚徒困境 ( p r i s o n e r s d i l e m m a ) 博弈模型， 该模型用一种特别的方式为我们讲述了一个警察与小偷的故事。 假设有两个小偷a 和b 联