（计算机应用技术专业论文）基于粗糙集的p2p任务调度策略研究.pdf

大连理工大学硕士学位论文 摘要 p 2 p 网络具有很强的自治性和随意性等特点，每个节点既是资源提供者，又是资源 消费者，所有节点可自由加入或退出网络。这样，整个i n t e m e t 网络应用的核心从中央 服务器向网络边缘的终端设备扩散，人们将以更主动的方式参与到网络活动中去， i n t e m e t 重返自由和平等的本质，并极大地提高了信息、带宽等资源的利用率。任务调 度是p 2 p 计算中的一项关键技术，直接影响到整个系统的计算性能。 考虑在p 2 p 环境下，描述一个任务和节点需要多个属性，其中可能存在不相关属性。 本文首先利用粗糙集对描述任务和节点的关键属性进行特征向量提取，然后根据相似度 公式将任务和节点分配到与它相似度最大的类别中，从而确定任务和节点的类型。p 2 p 环境下，为了完成任务调度，必须先选取满足任务调度时间要求的空闲节点集合，但是， 节点在某一时刻的空闲与否并不能作为任务调度的条件，还应该考虑节点的空闲时间区 间。本文通过统计的方法来获取节点的空闲时间区间，为提高资源的利用率，在保证任 务成功执行的基础上，充分利用网络资源，动态调整置信度，选取在时间上适合于任务 调度的节点。 对任务和节点进行划分后，本文定义了排队机制后的任务调度模型，将任务和节点 分别放入不同的队列和集合中，对于同一队列中的任务按动态优先级进行排序。根据任 务调度机制选择空闲节点，一个队列中的任务调度到同一集合中的节点，完成任务调度。 最后，在实验中，把任务执行的平均q o s ( 主要包括任务的执行时间、通信时间、所需 费用) ，作为任务调度的评价指标，结果表明本文的方法提高了任务执行的平均q o s 。 关键词：p 2 p n 络；任务调度；粗糙集；排队机制 基于租糙集的p 2 p 任务调度策略研究 r e s e a r c ho nt a s ks c h e d u l i n gs t r a t e g yb a s e do nr o u g hs e tt h e o r yi n p e e r t o p e e re n v i r o n m e n t a b s t r a c t e a c hn o d eo ft h ep 2 pn e t w o r ki sb o t har e s o u r c e sp r o v i d e ra n dar e s o u r c e sc o n s u m e r a l l o fn o d e si nt h ep 2 pn e t w o r kc a r lf r e e l yio i no rl e a v et h en e t w o r k ，w i t hs t r o n ga u t o n o m ya n d r a n d o m n e s s t h u st h ec o r eo ft h ew h o l ei n t e r n e t sn e t w o r ka p p l i c a t i o nh a st r a n s f e r r e df r o m c e n t r a ls e r v e rt ot e r m i n a ld e v i c eo nn e te d g e p e o p l ec a r lt a k ep a r ti nn e ta c t i v i t i e sm o r e i n i t i a t i v e l y ，w h i c hr e a l i z e st h ef r e e d o ma n de q u a l i t yp r i n c i p l eo ft h ei n t e m e t m e a n w h i l et h e u t i l i z a t i o no fs o u r c e sl i k ei n f o r m a t i o na n db a n dw i d t hi si m p r o v e d t a s ks c h e d u l i n gi sak e y t e c h n o l o g yi np 2 pc o m p u t i n g ，i ti sad i r e c ti m p a c to nt h ec o m p u t i n gp e r f o r m a n c eo ft h ee n t i r e s y s t e m i np 2 pe n v i r o n m e n t i ti sd i f f i c u l tt oo b t a i nc o m p l e t ei n f o r m a t i o no ft a s ka n dn o d e m o r e t h a no n ep r o p e r t yi sn e e d e dt od e s c r i b et h et a s ka n dn o d e ，a n dt h e r em a yb ei r r e l e v a n t a t t r i b u t e se x i s t i nt h i sp a p e rw ef i r s tu s er o u g hs e t st oe x t r a c tf e a t u r ev e c t o r sf r o mt h e a t t r i b u t eo ft h et a s k sa n dn o d e s ，o nt h eb a s i so fw h i c hd e t e r m i n et h et y p ea n da s s i g nt h e i r s c a t e g o r yw h i c hw i t ht h el a r g e s ts i m i l a r i t yw i t hi t ，a c c o r d i n gt ot h es i m i l a r i t yf o r m u l a i nt h e p 2 pe n v i r o n m e n t i ts h o u l df i r s ts e l e c tt h es p a r en o d es e t st h a tm e e tt h er e q u i r e m e n t so ft a s k s c h e d u l i n gt i m eb e f o r et h et a s kb e i n gs c h e d u l e d h o w e v e r ，w h e t h e rt h en o d ei si d l eo rn o ta ta p a r t i c u l a rm o m e n tc a nn o ts e r ea st h ec o n d i t i o nf o rt a s ks c h e d u l i n g t h ei d i et i m ei n t e r v a lo f t h en o d ei sa l s os h o u l db ec o n s i d e r e d i nt h i sp a p e r as t a t i s t i c a lm e t h o di su s e dt oo b t a i nt h e n o d e si d i et i m ei n t e r v a l o nt h eb a s i so fe n s u r i n gt h es u c c e s s f u li m p l e m e n t a t i o no ft h et a s k w h i c hh a sf a c i l i t a t e di m p r o v e ds c h e d u l i n ge f j f i c i e n c y i na d d i t i o n s e l e c tt h en o d e st h a ta r e s u i t a b l ef o rt a s ks c h e d u l i n gd e p e n do nt i m eb ya d ju s t i n gc o n f i d e n c ec o e f f i c i e n td y n a m i c a l l y a f t e rp u tt h ed i v i s i o no ft a s k sa n dn o d e si nd i f f e r e n tq u e u e sa n dc o l l e c t i o n s ，t h i sp a p e r d e f i n e st h et a s ks c h e d u l i n gm o d d eb a s e do nq u e u et h e o r y ，a n ds o r tt h et a s ko ft h es a m e q u e u ea c c o r d i n gt od y n a m i cp r i o r i t y a c c o r d i n gt ot a s ks c h e d u l i n gm e c h a n i s mf o rs e l e c t i n g s p a r en o d e s ，at a s kq u e u ed i s p a t h ct ot h es a m es e to fn o d e s ，s oc o m p l e t e dt a s ks c h e d u l i n g f i n a l l y ，t a k et h ea v e r a g eq o se v a l u a t i o ni n d e xa st a s ks c h e d u l i n g ，w h i c hm a i n l yi n c l u d e st h e t a s ke x e c u t i o nt i m e ，c o m m u n i c a t i o nt i m ea n dc o s t e x p e r i m e n t a lr e s u l t ss h o wt h a tt h et a s kt o i m p r o v et h ea v e r a g eq o si nt h i sp a p e r k e yw o r d s ：p 2 pn e t w o r k ；t a s ks c h e d u l i n g ；r o u g hs e t ；q u e u e i n g m e c h a n i s m i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文 作者签名 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阕。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学硕士学位论文 1绪论 目前，互联网在世界上越来越普及，每天都有数以千计的计算机连入其中。在当今 高速网络时代，计算资源价格在下降，网络带宽在不断提高，网络的整体性能得到大幅 度提升，许多网络终端有了一定的服务能力，个人计算机的应用开始多样化，一部分人 开始依托计算机提供特定形式的服务，常见的有个人f t p 服务、协同计算服务以及文件 共享服务等。这些都给传统的c s 网络结构带来巨大冲击，而c s 网络中的服务器难以 满足越来越大的数据吞吐量，成为提供数据服务的瓶颈，虽然研究者们开发了许多方法 ( 如分布式机群) 来解决这一瓶颈问题，但是代价非常昂贵，而且又引入了新的安全问 题。如果我们能够共享网络中的各计算机终端资源，那么这些资源将是非常庞大的，也 是集中式服务器所无法比拟的。此外，c s 网络的服务器端很容易遭到黑客的攻击，服 务器必须要摆脱这种攻击。在这种背景下，p 2 p 网络结构适时出现了。 n a p s t e r 作为第一款p 2 p 应用软件推出并普及后，各式各样的p 2 p 软件开始不断发 布和流行，如g n u t e l l a 、f r e e n e t 等，它们试图提供全球范围的信息存取、资源共享和协 作。p 2 p 应用显示出了前所未有的威力，并不断有新的发展，它不仅改变了人们的上网 习惯，还改变了人们的生活习惯。 1 1p 2 p 的基本概念 p 2 p 是p e e r t o p e e r 的缩写。p 2 p 可以理解为“伙伴对伙伴”的意思，或者称为对等 网络。p 2 p 各节点既可以充当服务器为其它节点提供服务，又可以是客户机享受其它节 点提供的服务，相互之间可以共享资源。几年前人们已经认识到p 2 p 网络的优点并且从 体系结构角度对p 2 p 进行了研究，但是到目前为止，p 2 p 还没有一个统一的定义。c l a y s h i r k e y 给出了一个简单的但是具有启发意义的p 2 p 定义：p 2 p 是一类应用，它可充分 利用分布于网络边缘的各种资源，如c p u 周期、人力资源及信息等等。文献【l 】认为p 2 p 就是c l i e n t s e r v e r 结构相对的一种体系结构。r u d i g e rs c h o l l m e i e r 认为分布式网络如果 共享一部分他们自己的硬件资源，如处理器资源、网络宽带、打印机等，那么它就可以 称为是p 2 p 网络。有的学者认为p 2 p 是一种对等网络计算技术，它改变了i n t e m e t 现在 以大网站为中心的状态，重返“非中心化且把权力交还给用户【2 】。有的学者认为p 2 p 网络是分布式系统与计算机网络相结合的产物，是采用对等模式构建的计算机网络。归 根结底，p 2 p 网络与传统的集中式的c s ( 客户端j j l 务器) 模式不同，p 2 p 系统是由大 量作用和能力相同的节点构成的分布式计算系统，这些节点可以随时加入或离开，而且 两个节点之间的通信是对称的，可以直接进行信息交换。 基于粗糙集的p 2 p 任务调度策略研究 1 2 p 2 p 网络的拓扑分类 目前，p 2 p 技术的研究着重于p 2 p 拓扑结构的研究。p 2 p 核心技术就是分布式对象 的定位机制，p 2 p 网络的体系结构直接影响着网络的性能。p 2 p 拓扑可分为四类：集中 式拓扑( c e n t r a l i z e dt o p o l o g y ) ，分散式非结构化拓扑( d e c e n t r a l i z e du n s t r u c t u r e d t o p o l o g y ) 、分散式结构化拓扑( d e c e n t r a l i z e ds t r u c t u r e dt o p o l o g y ) 和部分分散式拓扑 ( p a r t i a l l yd e c e n t r a l i z e dt o p o l o g y ) 【3 1 。 ( 1 ) 集中式拓扑 集中式拓扑基于一台或多台中央索引服务器，中央索引服务器的功能是保存共享资 源的目录信息，并负责协调单独注册节点上的资源，提供资源的各个对等节点保存着数 据信息。有时，中央服务器也作为发配者分配任务给合适的节点。在集中式拓扑结构中， 中央服务器的功能得到了弱化，负担也得到了减轻，不必频繁的为各节点提供服务，只 需要提供目录服务，系统的关键功能由分布的各单独节点完成，其存储和计算能力都得 到了充分利用。集中式拓扑的最大优点是维护简单且发现效率高，它的资源发现可以由 中央目录来实现，所以它非常灵活和高效，但是集中式拓扑可能存在单点失效、网络热 点、诉讼等其它问题，一旦中央服务器失效，整个p 2 p 网络即陷入瘫痪。n a p s t e r 是这 种拓扑结构的典型对等网络模型【4 1 ，其模型如图1 1 所示。随着n p a s t e r 的成功，其它的 p 2 p 文件共享系统如f r e e n e t 开始出现，极大的推动了p 2 p 网络的发展。 图1 1 n a p s t e r 的搜索模型 f i g 1 1s e a r c h i n g i nn a p s t e r 大连理工大学硕士学位论文 ( 2 ) 分散式非结构化拓扑 分散式非结构化拓扑采用了随机图的组织方式，不需要中央目录，当一个新的节点 加入到网络中时，它自由地连接到其它节点。网络中的各节点都是对等的，具有相同的 能力，任何一个单独的、任意的终端实体离开网络，都不会给网络中的服务带来大的损 失。由于没有中心节点，所以不存在中心节点失效问题，分散式非结构化网络具有较好 的容错能力和可用性。分散的非结构化拓扑非常适合由高度自治的节点组成的环境，各 个用户之间可以共享资源。非结构化p 2 p 网络适合节点的动态性，也支持复杂查询，但 是由于资源十分丰富，其搜索请求在网络中传播过大，占用大量的带宽，某些搜索可能 会失败，搜索效率也不能保证。g n u t e l l a 、n u r e o g r i d 和f r e e n e t 是非结构化p 2 p 网络的 典型代表。模型如图1 2 所示。 图1 2g u t e l l a 搜索模型 f i g 1 2s e r a c h i n gi ng u t e l l a 一一一下载流 ( 3 ) 分散式结构化拓扑 分散式结构化拓扑也没有中央目录服务器，但为结构化的。目前，分散式结构化拓 扑大多由分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 实现的。这种结构的典型代表 是c h o r d 5 1 ，它将整个对等网络系统抽象为一个环形的结构，发现指定对象只需要维护 0 0 0 9 n ) 长度的路由表，它的目标是提供一个适合于p 2 p 环境的分布式资源发现服务。 d h t 系统已成为许多大规模分布式系统的构建基础，如分布式文件系统、事件通知服 务和应用层组播等。d h t 类结构最大的优点是数据定位搜索十分精确，查询效率高， 基于粗糙集的p 2 p 任务调度策略研究 缺点是d h t 维护机制较为复杂，对节点的不断加入和离开需要频繁地做额外工作，会 加大d h t 维护代价，而且d h t 不能有效地支持内容、语义等多样化查询。分散式结构 化拓扑的典型代表还有c a n 、p a s t r y 和t a p e s t r y 。 ( 4 ) 部分分散式拓扑 部分分散式拓扑吸取了集中式拓扑和分散式拓扑的优点，在设计思想和处理能力上 都得到了优化，它选择性能较高的节点( 如处理能力、存储能力、带宽等性能都比较高) 作为超级节点，每个超级节点作为一部分普通节点的中央资源，担任维持这些普通节点 共享数据的索引的任务。这个模型的关键就是引入了这些超级节点，超级节点之间组成 了纯分散式p 2 p 网络，超级节点处理用户的搜索请求，并从它负责的普通节点中执行搜 索，从而构成了一个层次式结构。部分分散式拓扑结构具有集中式拓扑的效率和分散式 拓扑的可恢复性、可扩展性，因此便于管理，性能较高，但是对超级节点依赖性大，如 果接近项层的少数超级节点失效，会给整个系统带来严重的影响，并且容易受到攻击， 容错性受到影响。部分分散式拓扑网络的典型代表是b r o c a d e 、f a s t t r a c k 和k a z a a 等。 模型如图1 3 所示。 查询流 _ 一一下载流 图1 3 部分分散式p 2 p 网络结构查询流程 f i g 1 3p a r t i a l l yd e c e n t r a l i z e dp 2 pn e t w o r kq u e r yp r o c e s s 大连理工大学硕士学位论文 1 3p 2 p 技术的应用 随着互联网的发展，p 2 p 技术也得到了长足发展，它的发展给网络的发展带来了无 限的发展空间，具有广阔的应用前景。目前，p 2 p 软件的用户使用数量急剧增加，应用 越来越广泛，已经扩展到军事、政治、交通及通信等各个领域。p 2 p 的主要应用可以概 括为以下几个方面。 ( 1 ) p 2 p 文件共享 p 2 p 作为一种新的计算模式，目前已经广泛应用于基于广域网的p 2 p 文件共享系统。 它通过在不同用户间直接进行文件交换达到文件共享的目的，在众多的p 2 p 应用软件中 所提供的功能也是多以此为主。p 2 p 技术可以实现i n t e m e t 上的任意两台计算机之间直 接共享文档、游戏和其它文件。p 2 p 文件共享应用通常用来共享大的音视频文件，客户 端在下载过程中通常会与几十上百个客户端保持连接，网上计算机之间不需要使用任何 一台中央服务器就可以实现交互，客户端越多，文件共享越频繁。与传统c s 模式相比， 能满足更多用户文件的快速共享需求，而且文件资源由各个客户端提供，所以资源丰富， 下载速度较快，客户文件下载体验非常好。在传统的w e b 方式中，必须要有服务器才 能实现文件的交换，通过将文件上传到某个特定的网站，用户再到某个网站搜索需要的 文件，然后下载，给用户带了很大的不便。但是，p 2 p 文件共享存在网络连接数庞大、 普通节点间的交互流量巨大、网络安全存在隐患等缺点。另外，p 2 p 文件共享的集中可 控制性、可管理性较低，大量非授权、盗版文件在普通用户之间传播交互，不能有效保 护知识产权和文化版权。 n a p s t e r 是最早出现的p 2 p 系统之一，满足了人们对m p 3 音乐的需求，从而在短期 内迅速成长起来，也由此引发了网络的p 2 p 技术革命。n a p s t e r 首先实现了文件查询与 文件传输的分离，当需要查询某个文件时，对等机通过不同的查询机制向其它对等机发 送查询请求，和合适的对等机建立连接后，实现文件的传输下载，有效地节省了中央服 务器的带宽消耗，减少了系统的文件传输延时。但是如果该服务器失效，会导致整个系 统的瘫痪。 b i t t o r r e n t 在中国用户之间使用比较广泛，它是一种依赖p 2 p 方式将文件在大量互 联网用户之间进行共享与传输的协议，实现简单、使用方便。 迅雷是被大家所熟知的下载软件，它是综合p 2 p 技术与c s 技术实现的，即基于 p 2 s p 原理建立的。迅雷整合了原本孤立的服务器和其镜像资源以及p 2 p 资源。这样迅 雷就拥有自己的资源服务器的同时共享了各个客户端的资源，另外，迅雷会把各个客户 端所单独拥有的服务器地址搜索出来并共享给别的用户使用。迅雷服务器会储存下载用 户所拥有的资源服务器地址，当有新的用户也下载该文件时，迅雷服务器会将前面所收 基于粗糙集的p 2 p 任务调度策略研究 集的所有资源提供给用户，并将新用户的地址作为新的资源来更新服务器资源列表。这 样，迅雷就具有了稳定快速的下载。 ( 2 ) 对等计算 在本质上，对等计算就是网络上的c p u 资源共享。p 2 p 技术的对等计算，连结起 网络中的众多计算机暂时不用的计算能力，获得的累积计算能力可以执行超级计算机才 能完成的任务。可以用这种“超级计算机 的计算能力处理一些拥有大量数据的业务， 如天气预报、基因的研究等。对等计算是网络环境下多个节点参与的计算模式，它具有 分布与共享、自相似性、自适应性与管理的多重性、动态性与多样性等特点，作为一种 全新的计算模型，它亦可作为网格计算和无线通信的底层支撑技术。 ( 3 )即时通信 即时通信是i n t e m e t 上十分重要的一项网络应用，在短短的几年内，各种即时通信 软件就获得了普及，而各种即时通信产品的相继出现也推动了p 2 p 技术的发展。 当前广泛使用的即时通信软件有m s n 、q q 等，这些著名的通讯软件正在改变传统 的通信方式。即时通信从原来的简单文字信息交流发展到现在两个用户或多个用户的文 件传输、音视频通信等。其工作原理如图1 4 所示。另外一款重要的p 2 p 即时通信软件 是s k y p e ，具有强大的语音通信功能，是全球领先的v o l p ( v o i c eo v e ri n t e m e tp r o t o c 0 1 ) 软件。 图1 4 即时通信软件原理图 f i g 1 4 t h ee l e m e n t a r yd i a g r a mo fi n s t a n tm e s s a g i n gs o f t 大连理工大学硕士学位论文 ( 4 ) 搜索引擎 p 2 p 搜索引擎技术也是现在研究的热点。p 2 p 技术使用户能够深度搜索文档，用户 搜索时不受信息文档格式的限制，不需要通过w e b 服务器，只要通过共享所有硬盘上 的文件、目录乃至整个硬盘，就可以取得很好搜索效果，这是传统目录式搜索引擎器( 只 能搜索到2 0 - - 3 0 的网络资源) 6 1 不能比拟的。可以说，p 2 p 为因特网的信息搜索提供 了全新的解决之道，许多著名公司都着手向p 2 p 方向发展，比如g o o g l e 公司称要在其 搜索引擎上采用p 2 p 技术，美国新兴搜索引擎设计公司1 5d i g i t a l 在几年前推出的商业 性搜索引擎p a n d a n g o ( w w w p a n d a n g o c o r n ) 就是依据对等搜索理念，但是一直没有顺 利发展起来，应用十分有限。 随着i n t e m e t 的迅速发展，网上庞大的数字化信息和人们获取所需信息能力之间的 矛盾日益突出。因为大多数搜索系统的表现与用户的期望值相差太大，诸如数据量高速 增长的视频、音频等多媒体信息的检索，现在仍然是无法突破的难题。将p 2 p 技术应用 到网页的检索中在一定程度上解决了这一问题。 目前p 2 p 搜索技术的研究空间还很大。 ( 5 ) 协同工作 使用传统的w e b 实现协同工作会给服务器带来很大的负担，成本太大。而p 2 p 技 术解决了这一难题，它可以将互联网上任意两台p c 建立实时的联系，从而实现协同工 作，为人们的活动提供了一个安全、共享的虚拟空间。通过p 2 p 可以建立一个安全的企 业级协同工作平台，提供信息链上的互动信息沟通，方便了各用户之间的交流联系等， 或者连接p 2 p 网上的所有p c ，利用其空闲c p u 进行协同计算，完成超级计算机的工作。 基于p 2 p 技术的协同工作受到了极大的重视，目前己经有p 2 p 网络在电子商务中成功应 用的方案，奥奇曾创建l o t u s 公司后就曾获得6 0 0 0 万美元的风险投资，用来开发协同工 作产品g r o o v e 。 ( 6 ) p 2 p 流媒体系统 现在网络流媒体软件发展也是日新月益，如p p l i v e 、p p s t r e a m 等都是常见p 2 p 应 用软件。 传统的c s 模式，流媒体服务器以单播的方式给客户端推送媒体流。由于流媒体业 务的迅速发展，用户数量大大增加，服务器就常常成为了系统瓶颈，不能满足服务的需 求，一方面是由于服务器带宽不够，另外一方面由于服务器处理能力也不可能满足越来 越多的服务需求。通过在网络应用层建立一个重叠网实现应用层的组播功能，并淡化服 务器的地位【7 】，一定程度上解决了服务器的瓶颈问题，通过扩大用户组的规模，更多的 一7 一 基于粗糙集的p 2 p 任务调度策略研究 需求也会带来更丰富的资源。另一方面这种技术依赖于现有的互联网，因此路由器交换 机等网络基础设施不需要改动，易于部署，且成本很低。 p 2 p 流媒体现在主要应用有：在线视频点播( v o d ) 和广播、网络电视( i n t e m e t p r o t o c o lt e l e v i s i o n ，简称i p t v ) 、虚拟现实漫游、无线流媒体、远程教学等。 ( 7 ) 其它应用 p 2 p 技术的应用越来越广泛，分布式存储技术利用数据存储软件，在网络上将文件 分散化存放，而不像现在存放于专用服务器，从而既减轻了服务器负担，又增加了数据 的可靠性和传输速度。 p 2 p 分布式计算能充分利用网络上冗余的计算能力从事规模庞大的并行计算，但是 基于p 2 p 的分布式并行计算技术并不成熟，还需要解决协同机制、信用机制等问题。 随着s u n 公司将其x t a 协议扩展到诸如个人数字助理( p d a ) 和移动电话等手 持终端上，并允许人们屏蔽具体的物理平台进行资料共享和文件交换等，p 2 p 技术在移 动通信和智能领域开始呈现发展势头迅猛的态势。 1 4p 2 p 网络的研究现状 p 2 p 技术在最近几年获得了高速的发展，它的应用也扩展到诸多领域。国外的研究 比国内起步要早，无论是协同办公、分布式计算，还是在资金实力方面都要领先国内许 多，而且国外的许多p 2 p 企业有过比较成功的经验，这些都是国内应当学习和借鉴的。 目前p 2 p 网络的研究主要集中在安全性研究、抖动问题研究、降低查找延迟算法研 究、常量度数的d h t 研究和关键字搜索研究等方面。 1 4 1 国外研究现状 国外学术界对p 2 p 网络的研究大部分是基于对其网络拓扑结构的研究。当前互联网 络中广泛使用的是集中式、层次式等拓扑结构。传统的集中式拓扑结构系统存在存储负 载过量、单点失效、容易受到黑客攻击( 比如d o s ，即拒绝服务，其目的是使计算机或 网络无法提供正常的服务，最常见的d o s 攻击有计算机网络带宽攻击和连通性攻击) 等 问题。而p 2 p 系统则多为分布式结构，有效解决了集中式拓扑结构的瓶颈问题，不过 p 2 p 系统在构造过程中需要解决系统中所包含的大量节点如何命名、组织以及确定节点 的加入或离开方式、出错恢复等问题。 各大企业如m i c r o s o f t 公司、s u n 公司和i n t e l 公司对p 2 p 技术应用的研究都有很大 的投入。m i c r o s o f t 公司成立了p a s t r y 项目组，主要负责p 2 p 计算技术的研究和开发工 作，目前m i c r o s o f t 公司已经发布了基于p a s t r y 的软件包s i m p a s t r y r v i s p a s t r y 。s u n 公司 利用j a v a 技术，开展了j x t a 项目。j x t a 是基于j a v a 的开源p 2 p 平台，吸引了大批 大连理工大学硕士学位论文 p 2 p 研究人员和开发人员，已经发布了许多基于j x t a 的应用软件包。2 0 0 0 年8 月，i n t e l 公司宣布成立p 2 p 工作组，负责开发p 2 p 应用平台。2 0 0 2 年i n t e l 发布了n e t 基础架构 之上的a c c e l e r a t o k i t ( p 2 p 加速工具包) 和p 2 p 安全a p i 软件包，从而使得微软n e t 开发人员能够迅速地建立p 2 p 安全w e b 应用程序。 国外开展p 2 p 研究较为著名的大学和科研机构主要包括u cb e r k e l e y 、m i t 和a t & t 互联网研究中心( a c i ) 。在国外学术界方面，p 2 p 研究的学术团体主要包括负责网 格计算和p 2 p 计算等相关的标准化工作的g g f ( g l o b a lg r i df o r u m ，g g f ，即全球网格 论坛) 以及希望加速p 2 p 计算基础设施的建立和相应的标准化工作的p 2 p w g ( p 2 p 工 作组) 。 1 4 2 国内研究现状 在国内，一方面虽然p 2 p 的相关应用极其广泛，但是p 2 p 行业标准尚未形成；另一 方面p 2 p 技术门槛与经营门槛都相对较低，而进入p 2 p 市场的企业无论是规模还是实力， 都不相上下，竞争十分激烈，并且这种竞争局面将会长期存在。目前，p 2 p 技术在电子 商务等领域有很好的应用前景。 国内对p 2 p 网络的研究主要在一些高等学校的学术团队中进行，目前，国内p 2 p 网络研究项目比较出色的有北京大学网络实验室开发的m a z e 文件共享系统，清华大学 自主开发的g r a n a r y 对等计算服务系统和华中科技大学研发的a n y s e e 视频组播系统。 m a z e 是北京大学网络实验室开发的一个中心控制与对等连接相融合的对等计算的 文件共享系统，是c e r n e t 上最大的非商业性、以科研为目的p 2 p 系统。m a z e 通过一 系列的核心技术( 共享的激励策略、文件共享与传输、防火墙跨越技术、基于关键字的 搜索技术、p e e r 节点的发现) ，确保了文件共享系统提供高效可靠的服务。网络上的每 台计算机都可以安装运行m a z e 的客户端软件，随时可以加入或退出m a z e 系统，系统 中每个节点( 也就是各个客户端) 可以将自己的一个或多个目录下的文件共享给系统的 其他其它成员，同时也可以分享其他其它成员提供的资源。m a z e 在用户管理、信息检 索上采用集中控制，中心索引服务器提供基于关键字的搜索，同时，还可以基于p e e r 之间的好友关系，进行p 2 p 搜索，成为比较成功的p 2 p 应用典型。 g r a n a r y 和a n y s e e 系统都充分利用了p 2 p 的对等计算技术，保证了系统的可扩展 性、高可用性等特点。 对等计算可以共享网络的c p u 资源，没有集中控制点，是一种分布式计算技术， 可避免客户服务器模型的服务瓶颈问题，成为分布式计算技术的研究热点。对等计算技 术及其应用也正晋升为整个信息技术研究领域的热点之一。 基于粗糙集的p 2 p 任务调度策略研究 1 5 研究课题的提出 在分布式环境下，往往有大规模的任务需要完成，而单一计算单元的计算能力是很 难胜任的。目前，人们在分布式计算中一般采用并行技术、分布式技术将多个计算单元 节点联合起来共同完成计算任务，另外，人们一直在研究如何把网络中的计算机的计算 能力充分利用起来，希望能够充分利用网络中的闲散计算能力来完成大规模的计算任 务。p 2 p 计算技术则为研究计算技术的发展提供了新的机遇。 p 2 p 计算技术也可以归结为一种分布式计算技术，但是它具有许多自身的特点，面 临一些需要解决的问题。如何实现调度的目标，怎样解决系统的实时性要求，以及任务 调度的方法都是p 2 p 技术研究的热点和难点。在p 2 p 计算中，各节点具有很大的差异性， 不同计算节点的计算能力和存储能力都可能不同，不同计算节点的活动时间存在巨大差 异，计算节点共享资源的数量也是不同的，所有这些都可能成为p 2 p 网络的瓶颈问题或 者影响系统的总体性能。 作为p 2 p 计算的研究课题之一的任务调度，目前受到人们的极大关注。在p 2 p 环境 下，任务分解、目标节点定位、负载均衡和结果返回等都是任务调度所涉及的问题。本 文主要考虑纯p 2 p 环境下任务与节点的特点，结合粗糙集理论知识，提出任务调度策略。 1 6 论文的主要研究工作 1 6 1 论文的主要工作 论文的主要工作： ( 1 ) 介绍了p 2 p 的基本概念，p 2 p 网络的拓扑分类，p 2 p 技术的主要应用及研究 现状； ( 2 ) 阐述粗糙集理论基础知识，分析了任务调度的特点、目标、算法分类及研究 现状。 ( 3 ) 利用粗糙集理论知识，提取任务和节点的关键属性，根据相似度对任务和节 点进行类型划分；采取统计方法提出空闲时间节点的获取方法，引入代理节点，根据任 务排队机制对任务进行动态优先级排序，将任务的执行时间、通信时间和所需费用三个 目标转化为任务平均q o s ，作为论文的评价指标，与传统的m i n m i n 算法进行分析对比。 1 6 2 论文的组织结构 论文共分四章： 第一章，主要介绍p 2 p 网络的概念，p 2 p 网络结构模式，p 2 p 技术应用及研究现状， 提出研究课题。 大连理工大学硕士学位论文 第二章，介绍粗糙集理论的概念、特点和粗糙集与其他不确定性理论的比较，并分 析p 2 p 环境下任务调度的特点、目标以及p 2 p 网络任务调度的研究现状和任务调度的几 种分类情况。 第三章，提出任务和节点划分问题，主要利用粗糙集理论对任务和节点进行划分类 型。 第四章，在任务和节点划分的基础上，引入排队机制，对p 2 p 任务调度策略进行研 究，最后结合实验进行分析比较，得出结论。 基于粗糙集的p 2 p 任务调度策略研究 2 粗糙集理论和任务调度基础 2 1 粗糙集介绍 2 1 1 粗糙集理论概述 粗糙集( r o u g hs e t ) 理论是波兰科学家z p a w l a k 教授于1 9 8 2 年提出的，用于处理 不精确、不确定、不完整的数据。但是当时并未引起国际学术界的重视，只是东欧各国 对粗糙集有所研究。到上世纪八十年代末，粗糙集理论终于引起国际计算机和数学界的 注意，从此走上迅速发展的道路。由于它在机器学习与知识发现、数据挖掘、决策支持 与分析等方面的成功应用，粗糙集理论成为国际上的研究热点。1 9 9 1 年z p a w l a k 专著 的出版成为粗糙集理论研究趋热的一个标志【8 j 。之后国际粗糙集研讨会陆续召开( 比如 1 9 9 2 年在波兰k i e k r z 召开的第一届国际粗糙集研讨会和1 9 9 3 年在加拿大b a l l f f 召开的 第二届国际粗糙集与知识发现( r s l 9 3 ) 研讨会) ，都积极推动了国际上对粗糙集理 论与应用的研究。现在，r o u g hs e t 理论与其它一些软计算理论，诸如f u z z y 集、粒计 算、神经网络、遗传算法等均已经成为当前计算机及相关专业的研究热点。 在国内，对粗糙集理论研究主要集中在对它的数学性质、有效算法的研究方面，如 粗糙集理论的知识表示、知识约简算法、粗糙逻辑等。自2 0 0 1 年在重庆成功召开第一 届中国r o u g h 集与软计算学术研讨会( c r s s c 2 0 0 1 ) 以来，与粗糙集相关的各类研讨会 也相继召开，很多学者出版了粗糙集的专著或合著，2 0 0 3 年第九届粗糙集、模糊集、数 据挖掘与粒计算国际会议( r s d f g 疋2 0 0 3 ) 和2 0 0 6 年第一届粗糙集与知识技术国际会 议( r s k l 2 0 0 6 ) 在重庆召开。我国每年的c r s s c 系列研讨会在规模和质量上均呈良好 的增长趋势，在相关领域的研究取得了显著成果，2 0 0 3 年成立了中国人工智能学会粗糙 集与软计算专业委员会，r o u g h 集的研究队伍得到了进一步的状大，研究成果在深度和 广度上也取得了快速发展，在知识约简、与信息论的结合、粒度计算、粗糙逻辑和知识 的不确定性方面取得了较大成功，培养出了一批较强的研究型人才。 2 1 2 粗糙集理论的基本概念 粗糙集的定义依赖于等价关系和等价类，粗糙集是建立在分类的机制上的，分类是 在特定空间上的等价关系，而等价关系构成了该空间的划分。下面首先介绍等价关系和 等价类的概念例。 定义2 1( 自反关系) 设r 是集合么到么的二元关系，如果对任意口a ，都有 ( 口，口) r ，则称尺为4 上的自反关系。 一1 2 一 大连理工大学硕士学位论文 定义2 2 ( 对称关系) 设r 是集合4 到彳的二元关系，如果对任意a ，b e a ，有 ( 口，b ) r ，则必有( 6 ，口) r ，称r 是彳上的对称关系。 定义2 3( 传递关系)设r 是集合么到彳的二元关系，如果对任意a ，b ，c 彳， 有( 口，6 ) r 和( 6 ，c ) r ，则必有( 口，c ) r ，称r 是彳上的传递关系。 定义2 4 ( 等价关系) 设犬是集合彳到4 的二元关系，如果他是自反关系、对称 关系、传递关系，则称r 是彳上的等价关系。 定义2 5 ( 等价类) 设尺是么上的一个等价关系，与么中的一个元素a 等价的所 有元素组成的集合叫作a 的一个等价类，记为 口】。，在不致引起混淆时，记作【口】。 根据上面的定义给出粗糙集定义： 定义2 6 设彳u ，r 是u 上的等价关系，么= ( u r ) 是一个近似空间，在彳上， 如果x 是一些尺的等价类的并集，则称x 是尺可定义的；否则称x 是尺不可定义的。r 不可定义集也称为r r o u g h 集，简称r o u g h 集、粗糙集。为将粗糙集精确地表达出来， 引入上近似和下近似的概念。 定义2 7 设x 互u ，r 是u 上的等价关系，x 的下近似集定义为有那些被包含在x 里的r 等价类的并：r ( x ) = 扛ui x 】r x ) ，x 的下近似集也称为x 的尺正域，记作 p o s 。( x ) ，它是由那些根据现有知识r 判断出肯定属于x 的对象所组成的集合。 x 的上近似定义为所有那些与x 交集不为空集的等价类的并： r ( x ) = x ul x 】rnx 0 ，x 的上近似是由根据现有知识r 判断出有可能属于x 的 对象所组成的集合。u r ( x ) 叫做x 的r 负域，记作n e g 尺( x ) ，它是根据现有知识尺 判断出肯定不属于x 的对象所组成的集合。 上近似集和下近似集之间的差叫做x 的的边界集，记作砌。( z ) ，它是由根据现有 知识r 判断出可能属于x 但不能肯定是否一定属于x 的对象所组成的集合。 由集合近似的概念导致了一个新的概念成员关系。因为在我们的方法中，对于 一个集合的定义是与集合的知识相联系的，所以成员关系一定也和知识有