




已阅读5页,还剩40页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
:暂科文搴 面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 摘要 第三代数字通信( 3 g ) 标准的提出使得在移动设备之间实现p 2 p 资源共享将成为可能。 资源搜索与发现是p 2 p 应用所面临的最核心的问题之一。然而,在移动设备上实现p 2 p 资 源搜索受到显示终端和存储能力的限制,而且移动设备不能进行频繁的消息广播,发布到移 动设备的搜索结果也需要具备较高的针对性和准确率。 目前,关于p 2 p 系统与移动网络环境的整合已经做了大量研究工作,并试图实现面向 移动p 2 p 网络的资源搜索与定位的系统。本文即是针对移动平台的特定应用环境,提出了 一个面向移动p 2 p 网络的资源搜索与定位系统方案并予以实现。该系统方案可以大大减小 搜索过程中的消息量,节省网络带宽,系统的查全率和查准率也能较好地满足移动网络和移 动设备的应用需求。 此系统由资源注册、资源索引、资源检索三个模块构成。资源注册模块为用户提供共享 资源的注册服务,主要采用移动用户主动发布的方式集中共享资源到中央服务器,并使用 x m l 语言来保存资源的原始信息;资源索引模块负责对资源的元数据构建索引及更新。为 了提高系统的搜索准确率,本文提出了一种全新的支持高效实时更新的e r t u ( e f f i c i e n t r e a l t i m eu p d a t e ) 倒排索引结构:e r t u 倒排索引由主倒排索引、临时倒排索引和删除文 件列表三部分构成;在执行实时更新时,根据索引中l o n gp 0 s t i n gl i s t s 和s h o r tp o s t i n gl i s t s 大 小分布和增长速度的不同,本文提出了一种混合索引更新模式,即对l o n gp o s t i n gl i s t 采取 i n - p l a c e 更新模式,而对s h o r tp o s t i n gl i s t 采取m e r g e - b a s e d 更新模式,以提高索引更新的性 能和效率;资源检索模块响应移动终端用户对网内资源的查询请求。 最后,我们设计了一个仿真移动网络环境来进行系统测试。仿真实验结果表明:所设计 系统的各项功能均能满足研发初期所提出的构想,系统运行良好、稳定。 关键词:移动p 2 p :资源搜索策略;倒排索引;索引更新 :椎甜虫孽 面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 a b s t r a c t 3 gs t a n d a r d si nm o b i l en e t w o r km a k ei tp o s s i b l et os h a r ep 2 pr e s o u r c e si nm o b i l ed e v i c e s a n do n eo f t h ee s s e n t i a lp r o b l e m si np 2 pi st h es t r a t e g yf o rr e s o u r c ed i s c o v e r y h o w e v e r , r e s o u r c e d i s c o v e r yi sad i f f i c u l tt a s ki nm o b i l ed e v i c e sb yt h el i m i t e dc o m p u t a t i o nc a p a b i l i t ya n dd i s p l a y a r e a i na d d i t i o n , m o b i l ed e v i c ei s n ta b l et ob r o a d c a s tn e w sf r e q u e n t l y , a n ds e a r c hr e s u l t sr e t u r n e d t om o b i l ed e v i c e sm u s th a v ea g r e a ta c c u r a c y m a n yr e s e a r c hf o ri n t e g r a t i o no fp 2 ps y s t e m si n t om o b i l ee n v i r o n m e n th a sb e e nd o n e a c c o r d i n gt oa p p l i c a t i o nr e q u i r e m e n t so fm o b i l ep 2 p , ar e a lr e s o u r c ed i s c o v e r ys y s t e mi s p r o p o s e di nt h i sp a p e r , w h i c hh a ss m a l l e rq u a n t i t yo fq u e r ym e s s a g e sa n dv e r yl o wb a n d w i d t h c o n s u m p t i o n , a d d i t i o n a l l y , i si m p r o v e di np r e c i s i o na n dr e c a l l ,c o m p a r e dt os t a t i ca n dl a n d m a r k i n d e xu p d a t es t r a t e g y t h i ss y s t e mc o n t a i n st h r e em o d u l e sw h i c ha r er e s o u r c e sr e g i s t e r , r e s o u r c e si n d e xa n d r e s o u r c e sq u e r y t h er e s o u r c e sr e g i s t e rm o d u l ep r o v i d e sr e s o u r c e sr e g i s t e rs e r v i c e sf o rm o b i l e p e e r sw h os h a r er e s o u r c e si ni n d e xs e r v e ro nt h e i ro w ni n i t i a t i v e ,a n dm e t a - i n f o r m a t i o no f s h a r e d r e s o l ei sk e p ti ni n d e xs e r v e ra sx m lf o r m a t ;r e s o u r c ei n d e xm o d u l ei m p l e m e n t sf u n c t i o no f i n v e r t e di n d e xc o n s t r u c ta n du p d a t e f o rt h ep u r p o s eo fa c c u r a t es e a r c h , an e wi n v e r t e di n d e x s u p p o r t i n gt oe f f i c i e n tr e a l - t i m eu p d a t e ( e r t u ) i sp r e s e n t e di np a p e r , w h i c hc o n t a i n st h r e e s t r u c t u r e s :d o m i n a n ti n v e r t e di n d e x , t e m p o r a r yi n v e r t e di n d e x , d e l e t e df i l e sl i s t i nt h ep r o c e s so f u p d a t ee r t ui n d e x , an e wf a m i l yo f h y 晡di n d e xu p d a t es t r a t e g i e si sp r e s e n t e d o u rn e wm e t h o d d i s t i n g u i s h e sb e t w e e ns h o r ta n dl o n gp o s t i n g sl i s t :w h i l es h o r tp o s t i n g sl i s t sa r eu p d a t e du s i n g m e r g e - b a s e ds t r a t e g y , l o n gp o s t i n g sl i s t sa r ek e p ts e p a r a t ea n du p d a t e di n - p l a c e t h i sw a y , c o s t l y r e l o c a t i o n so fl o n gp o s t i n g sl i s t sa r ea v o i d e d r e s o u r c eq u e r ym o d u l er e t u r n sq u e r yr e s u l t st o m o b i l ep e e r s i m u l a t i o n ss h o wt h a tt h i s s y s t e mi sp r a c t i c a la n df e a s i b l e i nm o b i l ep 2 pf i l e s h a r i n g s e r v i c e s k e y w o r d s :m o b i l ep 2 p ;r e s o u r c ed i s c o v e r ys t r a t e g y ;i n v e r t e di n d e x ;i n d e xu p d a t e h 原创性声明 本人郑重声明:本人所呈交的学位论文,是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发 表的成果、数据、观点等,均已明确注明出处。除文中已经注明 引用的内容外,不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体,均已在文中以 明确方式标明。 本声明的法律责任由本人承担。 论文作者签名: 日 关于学位论文使用授权的声明 本入在导师指导下所完成的论文及相关的职务作品,知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定, 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版, 允许论文被查阅和借阅;本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索,可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时,第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 敝储躲蕴j 新躲险日期:坠“ 蔫孵幺霉 面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 1 1研究工作背景 第一章绪论 随着手机、p d a 等个人计算设备的普及和移动计算技术的快速发展,处于网络边缘的 移动终端结点上的资源越来越丰富,且分布越来越弥散。如何利用这些动态资源,是移动计 算面临的新挑战。p 2 p 作为一种脱离中央服务器的束缚点对点的通信方式,能实现动态网络 环境中资源的高度共享,毫无疑问已成为移动计算环境下一种新的计算范型。 在p 2 p ( p e e rt op e e r ) 应用方式下,每个对等结点( p e e r ) 既是服务的提供者,又是服务 的享用者。对等结点为系统提供有限的计算或存储资源,结点之间的协作为其他结点提供服 务,实现将服务器的负载分散到每个对等结点上。加入系统的结点越多,结点为系统贡献的 资源也就越多,整个系统总的服务能力也就越强,从而有效地减轻了服务器的负载,极大地 提高了系统的可扩展性。 随着越来越多的数据存储到p 2 p 系统中,上层应用就需要底层架构来提供关键的数据 定位和搜索能力,所以如何发现拥有资源的对等点是p 2 p 系统中的一种非常关键的技术, 而资源搜索效率也成为了衡量p 2 p 网络性能的关键。p 2 p 资源搜索技术涉及到p 2 p 系统的 很多方面,例如资源定位所需要的时间,消耗的带宽等等。另外,在移动网络中实现p 2 p 资 源搜索还受到显示终端和存储能力的限制,而且移动设备不能进行频繁的消息广播,并且发 布到移动设备的搜索结果需要具备较高的针对性和准确率。 因此,研究并设计适用于移动平台特定应用环境的p 2 p 资源搜索与定位系统是一个颇 受瞩目的研究方向。 本论文来源于广州商机网络科技有限公司的委托项目移动p 2 p 文件共享服务系统, 此项目的设计开发及仿真测试工作在兰州大学数据挖掘实验室和p 2 p 实验室完成。移动p 2 p 文件共享服务系统实现移动网络环境和p 2 p 共享系统的高效整合,主要目标是实现3 g 环境 下移动终端用户信息资源的对等共享,建立基于p 2 p 的混合式共享体系结构。本文提出的 面向移动p 2 p 网络的资源搜索系统是移动p 2 p 文件共享服务系统的子系统之一,此子系统 的提出是为了解决移动p 2 p 网络中的资源发现与定位问题。 蔺辨大寥面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 1 2本文研究的内容和创新之处 鉴于此,针对移动网络和移动终端设备的特定应用环境,本文提出了一个面向移动p 2 p 网络的资源搜索与定位系统方案,并加以设计和实现。 本文研究的主要内容和创新之处包含以下几个方面: l 、提出一个适用于移动p 2 p 网络的资源搜索与定位系统方案。此系统由资源注册、资 源索引、资源检索三个模块构成。其中资源注册模块为用户提供共享注册服务,主要采用移 动用户主动发布的方式集中共享资源到中央服务器中,以减小搜索过程中产生的消息量和对 网络产生的负荷;资源索引模块负责对资源的元数据构建倒排索引,并实现对加入、删除、 更新资源的增量实时更新;资源检索模块响应移动终端用户对网内资源的查询请求; 因为在移动设备上实现p 2 p 资源搜索与定位时,发布到移动设备的搜索结果需要具备 较高的针对性和准确率。针对此问题,本文对现有的倒排索引结构进行了改进,提出了一种 支持高效实时更新的倒排索引结构e r t ij 。 2 、首先对倒排索引的存储结构进行了改进,e r t u 倒排索引由主倒排索引、临时倒排 索引和删除文件列表三个部分组成,其中新加入网络文档的索引信息累积在内存中的临时倒 排索引中,删除文件列表保存已被删除文档的标号,以此方式来支持索引的增量实时更新; 3 、观察到倒排索引中l o n gp o s t i n g sl i s t 和s h o r tp o s t i n g sl i s t 大小分布和增长速度的不 同,所以在倒排索引更新时,提出了一种混合索引更新策略:对l o n gp o s t i n g sl i s t 采取i n - p l a c e 更新模式,而s h o r tp o s t i n gl i s t 采取m e r g e - b a s e d 更新模式,以提高索引更新的性能和效率。 2 蔺孵矢掌面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 第二章相关技术综述 2 1p 2 p 文件共享及资源搜索 文件共享是目前p 2 p 技术的一个主要应用方向,目前国内外比较著名的p 2 p 文件共享 软件主要有b i t t o r r e n t 、n a p s t e r 、g n u t e l l a 、k a z a 以及m a z e 等,本文主要介绍在这些应用中 两个较为典型的应用:b i t t o r r e n t 和m a z e 。 2 1 1m a z e m a z e 是由北京大学网络与分布式系统实验室开发,主要采用混合型的p 2 p 系统,m a z e 系统采用了天网文件搜索的现成的检索技术来提供检索服务,采用心跳服务器来管理各个节 点的在线状态他1 。系统中的每个p e e r 就相当于一个传统f t p 服务器和f t p 客户端的结合体。 整个系统除了多个p e e r 外,还包括集中式的用户、目录、检索、心跳还有种子服务器。用 户管理服务器实现用户注册与身份认证。目录收集服务器负责收集每个p e e r 的共享的目录 列表到集中的数据库。检索服务器读取目录数据库为所有p e e r 的文件目录建立索引并提供 x m l 接口的检索服务,它兼容天网搜索的文件检索儿接口。心跳服务器负责维护在线用户 的列表。每个在线的p e e r 每隔几秒就通知心跳服务器“我还在线”,这也就是心跳的意义。 同时每个p e e r 每隔一段时间就把自己的目录信息在m a z e 的目录收集服务器上更新。检索服 务器定期重新建立索引,并由心跳服务器提供的在线状态只显示在线用户的文件检索结果。 种子服务器是为模仿b i t t o r r e n t 机制建立的m a z e 种子提供保存与更新的服务器。m a z e 系 统的整体结构如图2 1 所示。 2 1 2b i t n r r e n t b i t t o r r e n t ( 简称b t ) 是一个多点下载、源码公开的p 2 p 软件,使用非常方便,就像一 个浏览器插件,很适合新发布的热门下载【3 1 0b i t t o r r e n t 是当前比较流行的下载软件,它的思 想简单地说就是记录一个文件块可能的所有镜像下载地址,当下载者请求这个文件块时,下 载者可以从镜像地址中挑选下载,同时,下载者已下载的文件块也作为镜像为其他用户提供 服务【4 】。b i t t o r r e n t 在实现过程中采用w 曲服务器收集和管理种子文件,用户可以通过w e b 3 :篱稍,幺掌 面向移动p 2 p 网络的资源搜索系统研究与设计兰卅i 大学硕士学位论文 服务器发布和检索、下载种子文件;同时采用t r a c k 服务器收集各个节点的在线状态,当用 户需要下载时,则由t r a c k 服务器提供在线节点列表,下载者根据在线节点列表,通过b t 协议在网络中去主动尝试连接各个节点【5 】ob i t t o r r e n t 的系统结构如图2 2 所示: 一 文什l 录服务器_ i 【。似7 舯“求一? 一、”蚶。”采禽篆“国一圄 址f 誊ol # 旧l i ,i j 厂一 p 盯2 槲驴o n “k u 少 、。亨,7、c i 二 - t t f i ,“t ,rz c t 、。d 墓离星敏型皑- - - - + , t 一! 。百瓣西吾、 型 i ;i 、一 1 耵茜予嚷蕞一 一衍1 南莳最南一e = = 了 li辩 蹬鬻攀墅望墼!- h 用户管理服务器卜舞幽錾墼篓墼p w t 、。j 一一 f 丽可一l 石f 1 、| | :- 刊一一,i t j r + l , r i 。- _ o 、- 曲 b i t t o r r e n t 采用分片机制来实现对资源的分片和多点下载,目前b i t t o r r e n t 规定每2 5 6 k b 大小的文件为一个片断( p i e c e ) ,每个片断又分为大小的不同予片断( s l i c e ) 。但除此以外, b t 协议本身还通过p i e c e 选择机制优化了下载:由于数据以s l i c e 的形式分块下载,一般一 个s l i c e 只有3 2 k b ,即使所有p e e r 的上传速率都很慢,但每个s l i c e 极小,以至于从一个很 慢的p e e r 处获得一个s l i c e 所需时间也极少,b t 客户端只需合理安排对s l i c e 的请求,通过 节点选择算法和片断选择算法,在较活跃的p e e r 和下载较慢的s l i c e 中作出相应的调整和搭 配,即可获得较高的下载速率。 2 1 3p 2 p 系统中资源搜索与定位技术 p 2 p 资源发现是指网络主动的去发现资源并对这些资源进行注册和管理的过程【6 j 即: p 2 p 网络中请求的节点在主动发现目标节点的过程中所采用的策略。目前的研究和应用系统 主要采用两种策略来解决p 2 p 资源发现:集中目录式和泛洪请求式7 1 ,以及由这两种策略所 衍生出来的一些变化策略。 1 、集中目录式( c e n 仃a li n d e xs e r v e r ) : 集中目录式通常又称为混合型p 2 p ,在这种结构中有一个类似于服务器的节点集中提供 资源索引信息。当用户共享资源时,需将资源的 向索引服务器进行资源注册,索引 服务器中保存着系统中所有资源的标识符和指针列表。当用户需要查找资源时,首先通过资 源标识符查询索引服务器,服务器返回该资源的指针,用户通过该指针定位。当定位到资源 4 :骘鲥虫雩 面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 的存储位置后,资源的下载在节点之间直接进行,与索引服务器没有关系。 集中目录式的优点是:简单、易实现。大多数的分布式系统采用的都是这种方法,例如: 三种分布式对象计算环境( c o r b a ,d c o m ,j a 、,ar m i ) 提供的分布对象名字服务、大量的 通用目录服务( 如x 5 0 0 、l d a p 和n i s ) 和一些实用分布式系统( 如n a p s t e r ) 的资源定位 方法等。缺点是:基于c s 模式,缺乏可扩展性以及存在单点故障问题。集中目录式的p 2 p 资源发现策略如图2 3 所示。 2 、泛洪请求式( f l o o d i n gr e q u e s t ) 泛洪请求式通常又称为纯p 2 p 引,设计思想主要来源于一个经典的社会心理学原理:六 度分隔理论( s i xd e g r e e so fs e p a r a t i o n ) 1 9 】1 1 0 1 。美国著名社会心理学家米尔格伦( s t a n i e y m i l g r a m ) 于2 0 世纪6 0 年代最先提出:“你和任何一个陌生人之间所间隔的人不会超过六个, 也就是说,最多通过六个人你就能够认识任何一个陌生人。” 在p 2 p 结构中,泛洪请求式在资源发现的过程中主要采用的策略就是向邻居节点广播 信息,在这种结构中没有中央目录服务器,用户的请求通过所有连接的节点传递,这些节点 或者响应该请求,或者在不能满足请求时,将该请求向与自己相连的其他节点广播,直到请 求得到响应为止( 泛洪) 。为了减少广播带来的网络带宽浪费,一般将广播传递限制在7 - 8 跳以内,即如果请求在经过有限的循环广播之后,仍不能得到响应,则发送请求的节点将得 到一个错误信剧1 1 1 【12 1 。 泛洪请求式由于通过广播方式进行查找和定位,因此一般扩展性差,但在小范围内效率 高,可靠性好。此外如果在系统中存在一些所谓的超级节点( 即该节点拥有大量的资源信息) , 则可以显著减少带宽的浪费。泛洪请求式的p 2 p 资源发现策略如图2 4 所示。 _ i 一 。 s e a l 。t h - l 蛔聃n i 峭砌 图2 - 3 集中目录式p 2 p 资源发现策略图2 4 泛洪请求式p 2 p 资源发现策略 5 p 、 :骘村虫掌 面向移动p 2 p 网络的资源搜索系统研究与设计 兰州大学硕士学位论文 2 2p 2 p 文件共享系统与移动网络环境的整合 到目前为止,只有少数的几个方法实现了p 2 p 系统和移动网络环境的整合。文献1 3 1 分 析了在移动网络的资源调停过程中c h o r d 环【1 4 1 的性能状况。文献【1 5 】【1 6 1 介绍了一种面向移动 网络中的文件共享应用系统的通用分布式搜索系统。可是,它的架构主要是适用于m a n e t 网络状况;本文中讨论的方法主要是基于c e l l u l a r 移动网络。文献【1 7 】和1 1 8 1 探究了面向移动网 络的e d o n k e y 文件共享服务的可行性和性能,文献【1 7 1 是基于g p r s 业务,而文献【1 8 1 基于 u m t s 业务。文献1 9 魄出了一种基于j x t a 开发文件共享应用系统的方法,但它只是研究了 在3 g 网络环境下j x t a 这种系统和协议架构的适用性,对于它的性能优劣没有深究。文献 2 0 1 2 1 1 介绍了一种内容分发p 2 p 系统架构。它研究了不同的p 2 p 网络拓扑结构的性能差别, 但并没实现一个类似b i t t o r r e n t 或e d o n k e y 这样真正意义上的p 2 p 应用系统。由此可见,以 前的工作主要是针对资源调停机制的改进和网络拓扑结构的调整,以减少移动终端的通信流 量和资源消耗。 2 3中文自动分词技术 迄今为止人们已经提出了许多种基于字典的计算机自动分词算法,这些算法大致可分 为两类:机械匹配方法、理解式切分方法。 ( 1 ) 机械匹配方法 机械匹配方法主要是基于字符串匹配的原理进行的,即它以“足够”大的词表为依据, 采用一定的处理策略将汉语文本中的字串与词表中的词逐一匹配,若成功,便认定该字串为 词。 ( 2 ) 理解式切分方法 针对机械匹配法的不足,人们提出了理解式切分方法。这样的分词系统由三部分组成: 词库、知识库、推理机。词库中存放词条;知识库中存放已形式化的各种语法规则语法知识, 以及语言学专家在分词过程中进行推理判断的经验知识:推理机利用词库和知识库提供的大 量数据与知识,模拟语言学专家的逻辑思维过程,实现自动分词。这实际上就是一个自动分 词专家系统。从理论上讲,它较匹配算法无疑是一个进步,同时也似乎更易为人们所接受。 但其有效性和可行性尚待进一步验证。因为现代汉语毕竟缺乏标志,缺乏通用的分词规则。 语言界中现有的词法( 构词法,构形法) 、句法及组合规则仍然是十分笼统与复杂的,要想使 6 :氅_ 虫寥 面向移动p 2 p 网络的资源搜索系统研究与设计 兰州大学硕士学位论文 其有效的、系统的转换成可为机器采用的形式,还有待进一步的研究,因此,这种方法在现 阶段是难以付诸于实践的。 综上所述,不论采用哪一种分词方法,建立分词词库( 或称机器词典) 都是汉语自动分词 系统的基础,并且词库的优劣直接影响分词的正确率和分词速度。 2 4倒排索引更新策略研究 已有很多倒排索引方面的研究,并提出了各种实现方法。 t z i c k e rc h i u e h 和l a nh u a n g 提出了一种实时更新索引的实现,并运用在c o d i r 系统 中,他比较了即时更新( e a g e r l y u p d a t e ) 、背负式更新( p i g g y b a c k u p d a t e ) 以及批量更新( b a t c h a p p r o a c h ) 三种更新策科2 2 1 ,得出的结论认为,背负式和批量式都大大地优于i l p 时更新,而 在背负式与批量式的比较中,前者略好一些。 m o f f a t 做了有关压缩和快速索引方面的工作,他描述了对于倒排索引和数据的压缩技 术,并指出压缩质量不会因文档集合的大小而受影响,并且响应时间也可以在一个可以接受 的较好的范围内【2 引。但它是在假设文档集合为静态的基础上进行哈夫曼压缩。 g o o g l e 是一个被广泛运用于超链数据环境下的优秀的搜索引掣2 4 1 ,它用了多种数据结 构来支持有效的检索,每个文档有唯一的标识,文档的信息被保存在一个固定宽度的i s a m 中,称为文档索引。g o o g l e 在内存中存有一个完全的字典。g o o g l e 最关键的技术是运用了 p a g e r a n k 算法来进行结果排序,使搜索引擎的性能大大提高,成为目前最成功的商业搜索 引擎之一。 b r o w n 提出了一种建立在m n e m ep e r s i s t e n t 对象基础上的增量索引机制f 2 习f 2 6 】f 2 7 j 。他们观 察索引大小的分布,发现9 0 词的l i s t 都小于i k ,而这些只占到总索引量的1 0 。将近一 半的l i s t 都小于1 6 字节,这意味着有很多l i s t 自从创建以后,就从来不更新。9 9 的表的大 小都小于或等于8 k b ,仅l 是大于8 k b 的长表,但它们的大小却占了总索引大小的9 0 以上。这部分长表还会不断、并迅速地增长,在查询时用到的机会也更多。考虑到这种特性, 把短表存在固定大小的对象中,对象所占空间可以是从1 6 到8 1 9 2 比特,按2 的幂递增( 如: 1 6 ,3 2 ,6 4 ,) ,当一个新表创建时,分配一个可以容纳此表的最小的对象,把表装入这 个对象中。而长表,则存入一个由8 k b 的对象组成的链表中。当短表增长时,在其对象后 的空余中加入增长的内容,当其大小超过这个对象的容量时,就会分配一个比这个对象大一 倍的对象,把原对象中的内容拷贝过去,并把原来的对象释放掉,当其大小超过8 k 时,就 7 :骘辫幺掌 面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 会变成一个长表。长表增长时可以通过对尾部对象的更新而完成,当尾节点满时,就会在其 尾部加入一个新对象。他们用m n e m ep e r s i s t e n t 对象来实现这种结构,取得了良好的效果。 t o m a s i c 描述了用一种双结构来实现倒排索引【2 8 p f l 。同b r o w n 一样,他们也观察到了 索引大小的分布,因此在他们的方案中有两种结构,他们把短的l i s t 放入磁盘上一个固定大 小的区域,其中含有多个l i s t ,这个区域称为b u c k e t s ,开始时所有的l i s t 都装入b u c k e t s 中, 当b u c k e t s 装满时,其中最长的一个l i s t 被认为是一个长l i s t ,他们把长的倒排表( 也是经常 出现的词所对应的索引) 放到一个变长连续的区域中,每个长l i s t 的块中只含一个词的l i s t 。 当内存中的词w 的l i s tl 要被写入磁盘时,首先检查w 是否有一个l o n gl i s t 在磁盘上,如果 有,把这个l 加入到后面。如果没有,把l 插入到h ( w ) 对应的b u c k e t 中,如果b u c k e t 中已 经有w 的l i s t ,把l 加入,否则新建一个l i s t 。此时如果b u c k e t 溢出,找出其中最长的l i s t , 称为m ,从b u c k e t 中删除m ,并为其建立一个长l i s t 。用这种方法,可以自动地划分长l i s t 和短l i s t 以达到优化处理的效果。 基于文件的倒排索引技术是建立在操作系统所提供的文件系统之上,k n i g h t 和h a m i l t o n 描述了一种基于u n i x 文件系统的实现1 3 0 l 。 8 皙埘矢乎面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 第三章移动p 2 p 文件共享服务系统架构 3 1系统目标与功能 移动p 2 p 文件共享服务系统实现移动网络环境和p 2 p 共享系统的高效整合,主要目标是实 现3 g 环境下移动终端( 智能手机、p d a 、笔记本等) 用户信息资源( m p 3 、图片、铃声、电 影、游戏等) 的对等共享。系统的主要功能包括: 移动终端设备用户之间的信息共享; 移动终端设备用户共享3 g 数据网内部的信息资源; 移动终端设备用户共享来自互联网的信息资源; 有效的用户组管理机制; 信息资源的查询; 实现信息资源的高效下载。 为了共享资源,p 2 p 程序必须支持两个基本功能:1 ) 资源调停功能,即在p 2 p 网络中 定位每个被共享资源的位置;2 ) 资源控制功能,即在对等点下载资源时进行时间和优先顺 序等方面的控制。纯p 2 p 系统架构是基于完全分布式机制,在这种架构下以上两种功能均 由对等点个体实现,如g n u t e l l a ;而混合p 2 p 系统架构是利用一个中央实体( 即所谓的中央 索引服务器,例如b i t t o r r e n t 中的t r a c k e r 服务器) 收集和分发网络中所有共享资源的位置信 息,来完成资源调停功能。 不同于现在应用的有线网络,在2 5 g 3 g 移动网络中两个移动设备进行直接的数据传递 通信代价非常昂贵;另一方面是由于移动终端的局限性,移动终端固然具有携带方便、灵巧 等优点,但也存在其固有的缺陷,如能源受限、内存较小、c p u 处理能力较低和成本较高 等,从而给设计开发和应用推广带来一定难度,同时显示屏等外设的功能和尺寸受限,不利 于开展功能较复杂的业务。考虑到成本和易于携带,移动节点不能配备太多数量的发送接收 器,并且节点一般依靠电池供电。所以基于移动设备在处理器速度、存储容量、特别是电池 性能上的限制,纯粹的p 2 p 系统架构并不能使它在2 5 g 3 g 移动网络环境中性能得到最优 化。像现有的大多数移动p 2 p 架构一样,这篇文章采用的也是混合p 2 p 系统架构。在混合 p 2 p 架构中,有一台或多台中央服务器给所有在共享区域的p e e r 提供服务,每个p e e r 都能 9 麓埘虫害面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 够通过中央服务器来搜索和定位这个移动网络中其他任一p e e r 所共享的任何资源。 3 2系统架构 此项目的移动p 2 p 文件共享系统是一个扩充的混合p 2 p 架构,因为我们在其中设计了 一个实时状态服务器以实现对移动网络中的在线对等点的实时管理。这篇文章中的移动p 2 p 系统由以下四个组件组成:爬虫服务器、中央索引服务器、缓冲索引服务器和实时状态管理 服务器。如图3 1 所示。 |圃 i ;固圜i : 扑 j r 图3 - 1移动p 2 p 文件共享系统体系架构 爬虫服务器在基于中央服务器的移动p 2 p 搜索系统中,中央索引服务器必须知道这个p 2 p 社区中任何一个资源的位置信息。爬虫服务器即支撑这一功能,它定期收集网络中任一个未 知资源的位置信息,报告给中央所有服务器。以此方式,也减少了移动设备在端对端搜索时 的通信量。 中央索引服务器( i s )每个对等点都依靠索引服务器来发现和定位其它对等点上的共享资 源,主要由以下三个步骤完成:共享文件的注册、关键词方式搜索资源、结果的返回。索引 服务器总是知道任何一个共享文件的位置信息和任何一个对等点的在线及离线状态。网络中 的移动设备必须而且只能连接到此索引服务器,提交它所共享的资源的信息( 包括资源名称 和其它描述信息) 。当接收到对等点的搜索请求时,索引服务器即在倒排索引中查取相匹配 的结果列表返回给用户。由于版权问题,索引服务器并不存储共享文件的物理内容,只保留 文件的描述信息。此外,索引服务器还统计每一个共享文件被请求次数,以支持热点资源的 快速查询。 1 0 蔺辫虫雩 面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 缓冲索引服务器( c p ) 缓冲索引服务器上存储热点资源列表。当一个文件单位时间内的访问 次数到达设定的阈值,中央索引服务器即把此文件的信息发送给缓冲索引服务器。这时,缓 冲服务器中将以前的热点资源列表和新产生的热点资源进行对照,加入新产生的热点资源并 删除已过时的资源。存储在缓冲服务器上的文件被单独索引,这些文件的倒排索引被存储在 内存中,以支持热点资源的高效搜索。 实时状态管理服务器( e s )实时状态管理过程包括1 ) 移动终端实时状态的收集,即收集各 个移动终端的在线或离线情况、片断拥有状况、可利用带宽等状态信息,以得到网络中的全 局情况;2 ) 下载过程的控制,即移动设备在下载过程中每下载完一个片段,即向状态服务器 提交继续下载的请求,状态服务器采用改进的b i t t o r r e n t 片断选择算法来指导对等点的片断 选择和地址选择。 ;篱舛幺掌面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 第四章移动p 2 p 资源搜索系统设计与研究 4 1概述 目前p 2 p 技术已在文件交换、分布式计算、搜索、信息共享、协同工作、即时通信、 网络游戏等方面得到了广泛的应用p 4 1 。但是,无论是通信、p 2 p 协作、分布式搜索引擎还 是共享计算和交互式游戏等功能的实现,都是以能很好地解决网内资源的迅速准确定位问题 为前提的。所以,p 2 p 网络中资源发现与搜索是极其重要的。相对于传统的c s 模式网络, 对等网络在容错性、资源共享的可扩展性、自我组织、负载平衡、匿名等方面具有很大的优 势。然而,一些在c s 模式下可以轻而易举完成的工作,在p 2 p 网络中变得并不容易,资 源搜索就是其中之一。在c s 模式中,主机之间通过服务器共享资源,当客户端需要搜索某 种资源时,只需向服务器发出请求,服务器做出回应。p 2 p 网络中,对等点之间通过彼此之 间的联系来共享资源,因此如何发现拥有资源的对等点就成为p 2 p 网络中资源搜索的关键 问题。 从2 2 节,我们可以看到有很多研究机构已经做了关于p 2 p 系统与移动网络环境的整合 方面的工作,但到现在为止并没有实现一个真正意义上的面向移动p 2 p 网络的资源搜索与 定位的成型系统。 针对移动平台的特定应用环境,我们提出了一个基于移动p 2 p 环境的资源搜索与定位 系统方案。这个资源搜索与定位,说到底是一个应用软件系统;从移动p e e r 的角度来看, 它根据移动设备用户在终端上提交的类自然语言查询词或者短语,返回一系列p 2 p 网络中 很可能与该查询相关的资源信息,供用户进一步判断和选取。为了有效地做到这一点,它大 致上被分为三个功能模块,或者三个子系统,即资源注册模块、资源索引模块、资源检索模 块。其中资源注册模块为用户提供共享注册服务,与现有的大部分p 2 p 查询服务类似,主 要采用移动用户主动发布的方式集中共享资源到中央服务器中;资源索引模块在中央服务器 上对收集来的资源信息进行整理、存储,并对资源的元数据构建倒排索引,并实现对加入、 删除、更新资源的增量实时更新;资源检索模块响应移动终端对网内资源的查询请求【3 5 】, 通过这些索引文件进行具体资源信息的检索,从而向用户提供查询服务。整个系统的实现方 案如图4 1 所示。 1 2 :鹭,虫害面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 用户 图4 1 移动p 2 p 资源搜索系统方案图 4 2资源注册模块设计与研究 4 2 1 资源元数据的表现形式 收集资源信息的目的就是要使中央服务器能够统一管理系统中所有的资源,以向用户提 供检索、下载功能,方便用户对所请求资源的定位。在某个共享资源能够在p 2 p 网络中分 发之前,我们必须解决这个资源在网络的标识问题。能够针对资源的唯一性要求,b i t t o r r c n t 和m a z e 分别采用m d 5 和h a s h 算法在资源的发布端根据资源的原始内容计算m d 5 或 h a s h 值,计算出来的值就是相应的资源在整个p 2 p 系统中的唯一标识。然而,考虑到移 动设备计算能力有限,本系统采用计算过程相对简单的算法来生成针对每个共享资源的全局 唯一标识,此标识值在服务器端生成,具体计算过程如公式4 - l : 1 3 :鹭埘虫警 面向移动p 2 p 网络的资源搜索系统研究与设计 兰州大学硕士学位论文 p i d = 服务器端接收到资源的时、分、秒+ 当前进程生成的随机数( 公式4 - 1 ) 如2 0 0 7 年1 月1 7 日1 3 时4 0 分5 6 秒新做种( 发布资源) 的资源,所产生的随机变量 为7 4 8 8 ,则此共享资源的标识值为:2 0 0 7 0 1 1 7 1 3 4 0 5 6 7 4 8 8 。这个标识号是全局唯一的,在 这个资源分发的过程中,这个编号会一直跟随资源,这样就能保证同一个标识号的文件为同 一个资源,在多点p 2 p 下载的过程中可以提供多点下载。 移动设备在发布资源的过程中需要向服务器传递:资源名称、资源类型、大小、资源所 在i s p 类型、e s 服务器地址、资源描述信息等相关内容,以字符串形式传送;结合中央服 务器所产生的资源唯一标识符( p i d ) 和收集来的种子数、用户数、下载者数等信息,就构 成了此数据的元数据。对于移动设备共享资源的元数据,我们采用x m l 语言来描述。在 x m l 语言中,我们定义一套有一定语义内涵的标签体系,用于对数据源的结构化描述。通 过对x m l 元数据进行预处理,可以得到一个元数据库。对元数据库的查询检索很大程度上 是一种类似数据库的结构化检索。不同的是,数据库检索的最终结果只是记录的集合,而元 数据检索的最终结果是符合条件的元数据所描述的原始信息内容。将这些具体信息表示出来 后,我们在进行搜索的时候,可以根据相应的字段进行精确查找,这可以大大提高查找的准 确率和效率;并且按照这种形式来保存资源信息,容错性好,即使有数据损坏,也是局部性 的,不会导致扩散或其他数据无法存取。此格式的示例如图4 - 2 所示: 图4 2 资源原始信息保存格式示例 1 4 :萄村虫害 面向移动p 2 p 网络的资源搜索系统研究与设计兰州大学硕士学位论文 4 2 2 资源注册过程 在本系统中由于服务器与移动终端的通信类型较多、移动终端的存储能力有限,在设计 的过程中,为节约通信负荷、减少通信过程中传递的字符数,通信过程中主要采用传送字符 串的策略来解决这些问题。在中央服务器端通过设置服务器端s o c k e t ,鉴听客户端发来的做 种或查询请求。通过线程连接池,即:每来一个客户端s o c k e t 连接请求,便用一个线程来 处理服务器端s o c k e t ,接收来自客户端s o c k e t 发来的字符串。 每一种通
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年仓储货物仓储合同
- Peptide-HV2-生命科学试剂-MCE
- 2025年船舶租赁合同(GF-9-0405)货运管理服务条款协议书
- 2025年建材批发合作协议书
- 2025年滁州职业技术学院公开招聘工作人员56人考前自测高频考点模拟试题及完整答案详解
- Obtusichromoneside-A-生命科学试剂-MCE
- 中式性格测试题及答案
- 2025年好汉查理面试真题及答案
- 面试试题及考察要点答案
- 2025年初中政治分析试卷及答案
- 2025年四川省情省况考试复习题库题库(含答案)
- 科学教育:未来启航
- GB/T 46134-2025天然酯在电气设备中的维护和使用导则
- 金太阳九年级数学月考试卷及答案
- 地质技能竞赛试题及答案
- 现代农业装备与应用课件
- 土工压实度试验规程课件
- 2025年安徽省标准化专业技术资格考试(标准化基础知识)历年参考题库含答案详解(5卷)
- 售电招聘试题及答案
- 原平市屯瓦昌兴选矿厂铁矿资源开发利用、地质环境保护与土地复垦方案
- 河南省工业项目建设用地控制指标
评论
0/150
提交评论