（通信与信息系统专业论文）基于pubsub系统的rfid网络及其路由研究.pdf

中文摘要 中文摘要 r f i d 网络已成为r f i d 应用的研究热点，研究人员提出了以中间件为基础的 应用框架，并在诸多领域得到了广泛应用，如物流、供应链、零售业、食品以及 铁路车号自动识别系统等。 早期的r f i d 应用，由于应用的简单性，研究人员对应用架构的研究较少，侧 重关注r f i d 数据获取以及制造成本等问题，包括：廉价的标签和阅读器的研究与 设计、标签及阅读器冲突、特定应用环境下的标签、以及数据读取的可靠性等问 题。 传统的r f i d 应用主要是针对特定领域的应用，大都采用基于数据中心的应用 方式，即由阅读设备获取标签对象数据，并集中进行存储和处理。重点关注如何 将r f i d 数据与现有的应用系统相关联，因而，中间件技术被认为是解决r f i d 网 络的关键手段和技术方法。 近年来，随着r f i d 的普及，r f i d 应用正在经历由简单应用向复杂应用的转 变；从简单的数据处理转向面向事件的处理；从局部应用走向全球化应用；从r f i d 与后台单一应用系统相结合，转变为在异构环境下实现数据共享等。这些转变给 r f i d 数据管理和系统架构带来了新的挑战，要求新一代的r f i d 应用架构能处理 具有以下特征的数据事件：r f i d 数据的时态性、动态性和关联性，数据的流特性 和海量数据，冗余和差错，以及在异构网络实现数据共享等特征。 为满足新一代r f i d 网络应用的要求，本文提出了面向复杂事件处理的普适应 用环境下的r f i d 网络体系结构，并对其中的关键理论和方法进行了深入的研究。 本文的主要工作包括： ( 1 ) 将p u b s u b 系统与r f i d 复杂事件处理相结合，提出了l 玎i d 分层网络结 构，给出了r f i d 网络关键描述及定义，包括r f i d 网络的形式化描述、匹配、路 由等，研究并讨论了r f i d 网络中的关键组成部分一代理的结构和主要功能。 ( 2 ) 考虑到海量数据条件下r f i d 网络的负载和可扩展性，基于复杂网络和结 构化p 2 p ，提出了分层r f i d 网络结构和模型。在此基础上，针对著名的基于内容 的c b c b 路由，通过考虑代理邻居间关系，提出了簇首代理网络中的代理遍历路 由算法，实验结果表明：考虑代理邻居间关系的代理遍历算法，可有效地减少簇 首代理网络由于遍历而带来的通信开销。 ( 3 ) 为限制簇首代理网络内部开销，考虑到客户订阅间的相关性，提出了带有 源地址的基于边的覆盖合并精确路由算法，并进步给出了c h o r d 环簇首与簇内 代理的基本算法，算法可以减少传统的c h o r d 环覆盖路由中的订阅重复传播的问 题。同时，为适应c h o r d 环的动态变化，采用数据代理的方法，对c h o r d 环进行 北京交通大学博士学位论文 维护。研究表明：利用上述方法一方面可有效地减少网络内订阅的传播数量，另 一方面也使得c h o r d 维护开销更低。 ( 4 ) 研究并讨论了基于c h o r d 环的簇内和簇间移动性问题，提出了基于c h o r d 环的簇内移动性支持算法以及簇间移动性支持算法，包括订阅路由、订阅取消路 由算法等，并根据弱有效路由准则，证明了算法的正确性。实验表明：在移动情 况下与标准算法和延时优化算法相比，在路由重构开销、网络负载等方面具有较 好的表现。 关键词：路由；复杂事件处理；发布订阅系统；射频身份标签 a b s t r a c t a bs t r a c t w i t hr f i dn e t w o r kb e c o m i n gh o ti nr f l da p p l i c a t i o n s ，r e s e a r c h e r sp r o p o s e dt h e m i d d l e w a r e - b a s e da p p l i c a t i o nf r a m e w o r kw h i c hh a sb e e nw i d e l yu s e di nm a n yf i e l d s ， s u c ha sl o g i s t i c s ，s u p p l yc h a i n ，r e t a i l ，f o o d ，a u t o m a t i ct r a i ni d e n t i f i c a t i o ns y s t e ma n ds o o n d u et ot h es i m p l i c i t yo ft h ee a r l yr f i da p p l i c a t i o n s ，f e wr e s e a r c h e sp a i da t t e n t i o n t ot h es t r u c t u r e , w h i l em o s to ft h ew o r kf o c u s e do nt h er f i dd a t aa c q u i s i t i o na sw e l la s t h em a n u f a c t u r i n gc o s t s ，i n c l u d i n g ：l o w - c o s tt a g s ，r e s e a r c ha n dd e s i g no ft h er e a d e r s ， t h et a gc o l l i s i o n ，t h er e a d e rc o l l i s i o n , t a gi nas p e c i f i ca p p l i c a t i o ne n v i r o n m e n t s ，a n dt h e r e l i a b i l i t yo ft h ed a t ar e a d i n g t r a d i t i o n a lr f i da p p l i c a t i o n sa r e m a i n l yu s e di ns p e r f i cf i e l d s ，a n dt h e a p p l i c a t i o nm o d e sa l em o s t l yb a s e do nt h ed a t ac e n t e r , t h a ti s ，l a b e l e do b j e c td a t a a c q u i s i t i o nt h r o u g hr e a d i n ge q u i p m e n t ，t h e nc e n t r a l i z e ds t o r a g ea n dp r o c e s s i n g h o wt o a s s o c i a t er f i dd a t aw i t ht h ee x i s t i n ga p p l i c a t i o ns y s t e m sw i l lb et h ef o c u sp o i l l t ，t h u s ， t h em i d d l e w a r ei sc o n s i d e r e dt ob eak e ym e t h o da n d t e c h n o l o g yi nt h er f i dn e t w o r k r e c e n t l y , w i t hi t sp o p u l a r i z i n g , r f i di sg o i n gt h r o u g ht h ea p p l i c a t i o nc h a n g e s f r o m s i m p l i c i t y t o c o m p l e x i t y ；f r o ms i m p l ed a t a - p r o c e s s i n gt o e v e n t - o r i e n t e d p r o c e s s i n g ；f r o ml o c a la p p l i c a t i o n st og l o b a la p p l i c a t i o n s ；f r o mt h er f i dc o m b i n e d w i t l lb a c k e n d s i n g l ea p p l i c a t i o ns y s t e m st od a t as h a r i n gi nah e t e r o g e n e o u s e n v i r o n m e n t ，a n ds oo n t h e s ec h a n g e sb r i n gn e wc h a l l e n g e st ot h er f i dd a t a m a n a g e m e n ta n ds y s t e ma r c h i t e c t u r e ， a n dd e m a n dan e wg e n e r a t i o no fr f i d a p p l i c a t i o nf r a m e w o r kw h i c hc a l lp r o c e s sd a t ae v e n t sw i t ht h ef o l l o w i n gc h a r a c t e r i s t i c s ： r f i dd a t at e n s e ，d y n a m i ca n dr e l e v a n t ，t h ed a t af l o wa n dt h em a s sd a t a ，r e d u n d a n c y a n de r r o r , a sw e l la sd a t as h a r i n gi nh e t e r o g e n e o u sn e t w o r k i no r d e rt om e e tt h en e e d so ft h en e w g e n e r a t i o no fr f i dn e t w o r ka p p l i c a t i o n s ， t h i sp a p e rp r e s e n t sac o m p l e xe v e n t o r i e n t e dp r o c e s s i n gr f i dn e t w o r ka r c h i t e c t u r ef o r t h eu n i v e r s a la p p l i c a t i o ne n v i r o n m e n t , a n dm a k e sa l li n t e n s i v ei n v e s t i g a t i o na b o u tt h e k e y t h e o r i e sa n dm e t h o d s t h em a i nw o r ki n c l u d e sa sf o l l o w s ： ( 1 ) p u b s u bs y s t e mi sc o m b i n e dw i t ht h er f i dc o m p l e xe v e n tp r o c e s s i n g , a n da h i e r a r c h i c a lr f i dn e t w o r ks t r u c t u r eb a s e do np u b s u bs y s t e mi sp r o p o s e d ，a sw e l la s s o m ek e yd e s c r i p t i o n sa n dd e f i n i t i o n sa b o u tt h er f i dn e t w o r ka r eg i v e n ，i n c l u d i n gt h e f o r m a ld e s c r i p t i o no ft h er f i dn e t w o r k ，m a t c h i n g ，r o u t i n g , a n ds oo n t h ek e y v 北京交通大学博士学位论文 c o m p o n e n t sa b o u tr f i dn e t w o r k t h e 咖c 1 眦a n dm a i nf u n c t i o no ft h eb r o k e ra r e a l s od i s c u s s e d ( 2 ) c o n s i d e r i n gt h el o a da n ds c a l a b i l i t yo ft h er f i dn e t w o r ki nc o n d i t i o n so f m a s s i v ed a t a , ah i e r a r c h i c a ls t n l c t l l r ea n dm o d e lo ft h er f i dn e t w o r kb a s e do nt h e c o m p l e xn e t w o r ka n dt h es t r u c t u r i n gp 2 pi sp u tf o r w a r d o nt h i sb a s i s ，f o rt h e w e l l k n o w nc o n t e n t - b a s e dr o u t i n gc b c b ，c o n s i d e r i n gt h er e l a t i o n s h i pb e t w e e nt h e b r o k e rn e i g h b o r s ，ab r o k e rt r a v e r s a lr o u t i n ga l g o r i t h mi nan e t w o r ko fc l u s t e r - h e a d b r o k e ri sp r o p o s e d ，a n dr e s u l t ss h o wt h a t ：t h eb r o k e rt r a v e r s a la l g o r i t h mc o n s i d e r i n gt h e r e l a t i o n s h i pb e t w e e nb r o k e rn e i g h b o r sc a ne f f e c t i v e l yr e d u c ec o m m u n i c a t i o no v e r h e a d b r o u g h tb yt h et r a v e r s a li nt h en e t w o r ko fc l u s t e r - h e a db r o k e r ( 3 ) f o rt h er e s t r i c t i o n so fn e t w o r ko v e r h e a do nc l u s t e r - h e a db r o k e rn e t w o r k ， c o n s i d e r i n gt h ed e p e n d e n c yo ft h ec l i e n ts u b s c r i p t i o n ，t h i sp a p e rp r o p o s e sae d g e - b a s e d p r e c i s e l yc o v e rr o u t i n ga l g o r i t h mc o m b i n e dw i t ht h es o b r c ea d d r e s s ，a n df u r t h e rg i v e s t h eb a s i ca l g o r i t h ma b o u tc l u s t e r - h e a db r o k e ra n db r o k e ri nt h ec l u s t e r , w h i c hc a n r e d u c et h er e p e a t e ds p r e a do fs u b s c r i b e r si nt h et r a d i t i o n a lc h o r dr i n gc o v e r a g er o u t e a tt h es a m et i m e ，i no r d e rt oa d a p tt ot h ed y n a m i cc h a n g e so ft h ec h o r dr i n g , ad a t a p r o x ya p p r o a c hi su s e di nc h o r dr i n gm a i n t e n a n c e r e s e a r c hs h o w st h a t ：o no n eh a n d ， t h e s em e t h o d sc a nb ee f f e c t i v ei nr e d u c i n gt h en u m b e ro fs u b s c r i b e r ss p r e a d i n gi nt h e n e t w o r k ；o nt h eo t h e rh a n d ，n l e yc a na l s or e d u c et h ec h o r dr i n gm a i n t e n a n c ec o s t s ( 4 ) t h i sp a p e rs t u d i e sa n dd i s c u s s e sp r o b l e m sa b o u tm o b i l i t yo fi n t r a c l u s t e ra n d i n t e r - c l u s t e rb a s e do nt h ec h o r dr i n g , a n dp r o p o s e sa l g o r i t h m sw h i c hc a ns u p p o r tt h e m o b i l i t yf o rb o t ht h ei n t r a - c l u s t e ra n di n t e r - c l u s t e rb a s e do nt h ec h o r dr i n g , i n c l u d i n g t h es u b s c r i p t i o nr o u t ea l g o r i t h m ，s u b s c r i p t i o nt ot h ea b o l i t i o no ft h er o u t ea l g o r i t h ma n d s oo n t h i sp a p e ra l s op r o v e st h ec o r r e c t n e s so ft h ea l g o r i t h m sb a s e do nw e a ke f f i c i e n t r o u t i n gc r i t e r i a e x p e r i m e n t ss h o wt h a ti nc o m p a r i n gw i t ht h es t a n d a r da n dd e l a y o p t i m i z a t i o na l g o r i t h m si nr o u t er e c o n s t r u c t i n ge x p e n s e s ，a n dn e t w o r kl o a d ，t h e a l g o r i t h m sh a v eb e t t e rp e r f o r m a n c ew h e n i nt h es i t u a t i o no f m o b i l ec l i e n t s k e y w o r d s ：r o u t e ，c o m p l e xe v e n tp r o c e s s i n g , p u b l i s h s u b s c r i b es y s t e m ，r f i d 北京交通大学博士学位论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 、j 学位敝储答名：虿文扣奄答字嗍：加矿年- 堋心日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 薛4 彳 锯彳 签字日期：彻孑年l 月储日 导师签名 签字日飙2 西年1 2 旯碜备 致谢 值此论文完成之际，谨向我尊敬的导师张思东教授表示衷心的感谢! 感谢张 老师四年来的辛勤培养，感谢张老师为我取得的每一点进步所付出的大量心血。 张老师以他渊博的学识、深邃的思想给予我不倦的教诲和悉心的指导，使我的博 士论文得以顺利地完成。 张老师严谨的治学态度、勤勉的工作精神、务实的生活作风和睿智的学者风 范给我留下了深刻的印象；他对科学的热情和对自己信念的执著将对我今后的学 习、工作和生活产生潜移默化的长远影响，令我终身受益。 张老师不仅为我创造了良好的学习和科研环境，同时，在日常生活中给予了 我无微不至的关怀和照顾，从师四年的学习经历使我受益颇多，我将终生难忘。 在本文的研究与撰写过程中，得到了张宏科教授、王小平教授、秦亚娟副教 授、周华春副教授、郜帅老师、苏伟老师等热心的指导和无私的帮助，在此表示 深深的谢意。 在博士学习期间，还得到许多同学的帮助，与各位同学的讨论和交流使我受 益匪浅，使我得到了很多有价值的启示和建议，他们是：任彦、王博、董平、杨 冬、刘颖、杨水根、伍小芹等。他们的真诚合作与帮助使我度过了四年愉快而充 实的学习生活，在此一并向他们表示诚挚的谢意! 在研究过程中得到了我的同事和研究生的帮助，他们是：赵晓群教授、郭爱 煌教授、孙懋珩副教授、尹琴、葛乐、张磊、戴佩华、张凯、梅素平、刘翠平、 李刚、林铌忠、谭韵天等，在此表示深深的谢意。 最后，特别要感谢我的家人，正是他们真诚无私的奉献和持之以恒的支持与 鼓励，才使得我能够没有后顾之忧地专注于学业，没有他们全身心的支持和巨大 的付出，我将难以完成本论文。本论文凝聚了他们的大量心血，再次对他们表示 深深的谢意。 最后，谨以本文献给所有关心、帮助和支持我的老师、亲人和朋友们! 献给 我长眠于地下的我母亲! 第一章绪论 第一章绪论弟一早瑁化 r f i d ( r a d i of r e q u e n c yi d e n t i f i c a t i o n ，射频身份标签) 克服了传统条码技术的易 受污染、视距读取等方面的限制，上世纪末已经受到了学术界和工业界的高度关 注，并已在供应链管理、物流、零售、健康等多个领域实现了成功的应用【卜3 】。 早期的r f i d 应用，由于应用的简单性，研究人员对应用架构的研究较少，侧 重关注r f i d 数据获取以及制造成本等问题，包括廉价的标签和阅读器的研究及设 计、标签及阅读器冲突、特定应用环境下的标签、以及数据读取的可靠性等问题。 近年来，随着r f i d 的普及，r f i d 应用正在经历以下转变：由简单应用向复 杂应用；从简单的数据处理转向面向事件的处理；从局部应用走向全球化应用， 早期的应用如仓库管理等通常是地理范围较小的应用，而现在的供应链管理、集 装箱管理等应用，需要在全球范围内构建r f i d 应用架构；从r f i d 与后台单一应 用系统相结合，转变为在异构环境下实现r f i d 数据共享等。这些转变给r f i d 数 据管理和系统架构带来了新的挑战，要求新一代的r f i d 应用架构能处理具有以下 特征的数据事件【4 j ： ( 1 ) 时态性、动态性和关联性。阅读器动态地阅读标签对象的状态变化，如物 品入、出库等状态。在实际应用中，r f i d 数据非独立存在的，往往与以往的历史 数据间存在关联，包括时态、空间和时空等方面的关联。时态关联表达了事件之 间的时序关系，空间关联表达了事件发展的轨迹，时空关联表达了与对象有关的 事件的变化过程。 ( 2 ) 冗余性和差错性。阅读器以无线方式识读标签对象，一方面，由于识读周 期的原因，会重复获取同一对象的多个冗余数据；另一方面，由于无线通信的固 有特性，会出现阅读错误，如漏读、多读和脏数据等。 ( 3 ) 流特性、批量性和海量性。r f i d 数据是以流的形式快速、自动地产生的， 应用需要积累r f i d 数据以支持跟踪和监控应用。r f i d 数据也呈现出批量特征， 即多个对象成批地阅读，同时大规模r f i d 设备的部署也会产生海量数据。研究表 明：一个中等规模的仓库，每天可产生高达g b 级的数据，因此需要处理的数据量 非常庞大【5 1 。 ( 4 ) 应用异构性。r f i d 数据最根本的目的是能被各种应用有效地利用，但由 于不同的应用架构采用的设计和实现方式，以及数据处理方法的差异性，导致不 同的应用无法共享有意义的r f i d 数据。此外，随着大规模的r f i d 应用，要求在 全球不同位置部署和配置大量的阅读器。由于r f i d 阅读器部署和配置代价较高， 人们也要求不同的应用共享阅读器获取的数据，以减少阅读器的重复配置和部署。 北京交通大学博士学位论文 为满足r f i d 应用的要求，学术界和工业界都意识到构建新一代r f i d 网络的 重要性。但到目前为止，并没有对r f i d 网络进行统一定义和描述。 本文将r f i d 网络定义为面向应用的r f i d 数据获取和事件传送的普适网络， 包括阅读器网络和事件传送网。与传统的网络不同，r f i d 网络侧重于异构环境 中存储、传播和处理r f i d 阅读事件。构建大规模普适环境下的r f i d 应用架构已 成为r f i d 成功应用的关键和核心【6 】。 1 1 研究背景 针对i 强i d 的普适应用，研究人员提出了以数据为中心的应用架构【| 7 】以及以事 件为中心的应用架构【黏l o 】。 最早研究r f i d 的机构是美国m i t ( 麻省理工学院) a u t o i d 中心，该中心提出 了e p c 网络( 电子产品编码网络，也称物联网) 的概念及网络的基本架构【6 】，如图 1 1 所示。 该架构主要包括：s a v a n t ：s a v a n t 负责收集、存储r f i d 阅读器发送的 e p c ( e l e c t r i cp r o d u c tc o d e ，电子产品编码) 信息；物理标记语言( p m l ) ，以x m l 为基础的规范，用以描述物品的标准信息格式；对象名字服务( o b j e c tn a m e s e r v i c e ，o n s ) ：类似于网络环境下的域名服务( d o m a i nn a m es e r v i c e ，d n s ) ，提 供e p c 编码的位置信息，当s a v a n t 需要查询保存某商品信息的服务器网络地址时， o n s 服务器提供e p c 编码与e p c 信息服务器间的映射功能。 s a v a n t 是位于阅读器和企业应用系统之间的中间件，用于处理连续读入的e p c 信息。阅读器所收集的e p c 编码首先传送给s a v a n t ，依据这种信息，s a v a n t 向分 布在各处的o n s 提出查询，由o n s 找到对应e p c 编码的产品资料信息，再回传 给s a v a n t 。 图1 - 1e p c 网络结构 西门子公司率先建立了以数据为中心的r f i d 中间件系统 7 1 。该系统采用传统 2 第一章绪论 的数据库技术，对r f i d 数据进行建模，并将数据保存在数据库中。在 d b m s ( d a t a b a s em a n a g e m e n ts y s t e m ，数据库管理系统) 基础上通过增加动态关系， 以支持r f i d 事件的检测与跟踪。 r f i d 应用一般要求从高速、海量的在线事件中及时发现异常事件并进行主动 报警。以数据为中心的系统由于性能限制，只适合进行历史数据的a d - h o e 查询或 在线监控低速的事件，并不适合对高速、海量的事件进行连续查询【4 】。 面对海量的r f i d 原始数据、数据大量冗余以及时态性和动态性、应用异构性、 数据的流特性等应用要求，以数据为中心的r f i d 网络受到了前所未有的挑战。为 此，研究人员提出了以事件为中心的r f i d 应用架构。 以事件为中心的方法是一种新型的r f i d 事件处理技术。基于数据源而非基于 数据库对事件进行建模，并对事件直接进行处理，以便高效处理更复杂的事件。 r f i d 国际标准化机构e p c g l o b a l 提出了a l e ( a p p l i c a t i o nl e v e le v e n t ，应用层 事件) 规范，a l e 的目的是为了减少原始数据的冗余性，从大量数据中提炼出有效 的业务逻辑，以满足不同的应用需求。基于事件的r f i d 网络能有效地对r f i d 数 据进行管理、处理、传递和存储，大大减少r f i d 网络中的冗余数据及事件。 p u b s u b 事件通信网络具有异步、匿名、多对多通信、松耦合、分布式等特征， 是一种有效的事件处理和传播的方法。将r f i d 事件与p u b s u b 系统相结合的研究 也得到了学术界和工业界的认可，如微软b i z t a l k b 2 】系统基于n e t 技术，以发布 订阅系统为基础，构建面向统一阅读语义的r f i d 网络，提供面向应用的服务，以 达到在异构网络中实现事件的分布式处理、存储和传播的目的。 下面从复杂事件处理、p u b s u b 系统、事件路由以及移动性支持等方面阐述基 于事件的r f i d 网络的研究进展。 1 2 当前研究进展 1 2 1r f i d 事件及处理 简单和复合事件的检测和处理是基于事件的r f i d 网络的关键任务之一。简单 事件是发生在阅读器和物品标签之间的信息交互，通常将r f i d 标签信息的读取 过程看成为一个简单事件。r f i d 读取设备频繁读取标签中的d 及数据，产生大 量的简单事件。 复杂事件则是在高层应用中由简单事件通过时态和非时态算子组合起来的事 件，是一系列简单事件的集合。 主动数据库、p u b s u b 系统中对查询数量和流速的高效支持，以及数据流系统 3 北京交通大学博士学位论文 中的查询语言接口和查询优化方法，为基于事件的r f i d 网络提供了重要的参考。 但由于主动数据库的处理技术【1 3 】没有考虑数据的流特性及复杂语义，并不能直接 适用于r f i d 网络。此外，考虑到r f i d 事件的冗余和时态特征等，现有的p u b s u b 系统并不能完全支持r f i d 复杂事件的检测和处理，需要进一步完善p u b s u b 系统 中的事件检测和处理机制。 针对r f i d 应用，借鉴传统的主动数据库和p u b s u b 系统中复杂事件处理方法， 研究人员提出了基于r f i d 的复杂事件处理方法，典型系统有美国加州大学伯克利 分校开发的原型系统s a s e t l 4 1 、s a s e + t 15 1 、c o m e l l 大学开发的c a y u g a 系统【16 】以及 e s t r e a m 1 7 】系统等。 s a s e 系统提供扩展的事件语言、事件查询处理器和操作优化策略等，实现了 r f i d 设备的数据采集和清理、基本事件生成、复合事件处理、事件归档，以及对 事件的查询。 +。 c a y u g a 系统提出了扩展的查询语言，通过自定义的自动机模型和内部命名方 法来高效地检测复合事件，并讨论了有关系统实现的技术细节。 e s t r e a m 系统在数据流查询器的基础上，集成了连续事件查询器，利用规则检 测数据流上的复合事件，考虑了高效的增量维护算法。 s a s e 和c a y u g a 方法是r f i d 复杂事件处理的主要方法，虽然可以在一定程 度上支持r f i d 复杂事件处理，但在面对r f i d 应用中的事件乱序、非事件以及事 件分布不均匀等问题时，在处理效率、检测正确性等方面存在着困难和挑战。 1 2 2p u b s u b 系统 通常p u b s u b 系统可以大致划分成基于通道【1 8 , 1 9 1 、基于主题【2 0 - 2 2 】以及基于内容 2 3 , 2 4 j _ - - 类，已有的实验原型系统包括e l v i n l 2 5 】、g r y p h o n t 2 们、s i 饥a 【2 7 1 、j e d i 2 8 1 、 h e r m e s 2 9 】和n a r a d ab r o k e r i n g l 3 0 】等。 p u b s u b 系统通常由一系列分布式代t 里( b r o k e r ) 组成，发布者和订阅者之间的 交互由p u b s u b 系统实现，网络可表示为g = v ，e ) ，其中v 表示b r o k e r ，e 表示 b r o k e r 之间的链路。 事件在g 中传播，客户( c l i e n t ) 连接到事件代理( b r o k e r ) 上。客户依据其作用可 以分为两类：发布者( 也称生产者) 和订阅者( 也称消费者) ，客户间一般不直接通信， 而是通过与p u b s u b 系统的交互来实现。发布者发布通告( 如当前的r f i d 事件) ， 消费者订阅( s u b s c r i p t i o n ) 通告。订阅者可以有多个有效的订阅，在客户已经签发订 阅后，通告服务为客户提供所有匹配的通告，直到客户取消订阅。 近年来，p u b s u b 系统受到了研究人员的高度关注。研究热点包括匹配算法 2 3 】、 4 第一章绪论 基于内容的路由算法【2 7 飙3 、安全策略【3 2 - 3 5 、基于p 2 p 网络的p u b s u b 系统解决方 梨2 9 3 删、p u b s u b 系统在普适计算和移动计算环境下的应用【4 1 垌、语义w e b 和本 体论与p u b s u b 系统的结合【4 7 4 讣以及容错策略 5 0 , 5 1 1 和提高p u b s u b 系统可靠性的事 务机制【5 2 ，5 3 】的研究等。 分布式p u b s u b 系统通常有三个层次：o v e r l a y 架构、事件路由和匹配订阅的 事件算法【2 2 1 。p u b s u b 系统通常建立在应用层o v e r l a y 网络上，o v e r l a y 架构是系 统的组成结构。事件路由定义为从发布者向订阅者传播信息的机制，即事件通过 o v e r l a y 架构从发布方到订阅方所要经历的路径。目前常用的o v e r l a y 结构有b r o k e r o v e r l a y 、p 2 p 结构化的o v e r l a y 以及p 2 p 无结构化的o v e r l a y 三种【2 2 1 。 根据系统节点的组织情况，基于p 2 p 网络的p u b s u b 系统可主要划分为非结 构化和结构化两种。 在非结构化p 2 p 网络中，各节点被随机地组织在一起，通常采用泛洪( f l o o d i n g ) 和随机游走( r a n d o mw a l k ) 的方法来转发消息。泛洪方法容易导致网络通信流量急 剧增加，造成网络拥塞；而随机游走无法保证资源一定能被发现。此外，非结构 化p 2 p 网络的节点组织通常要保持在一个较小的半径内，且网络拓扑的可扩展性 差，资源发现的准确率和效率低，并不适用于大规模系统的建构。 结构化的网络拓扑通常采用分布式哈希表作为基础结构，拓扑结构是受控和 确定的，如t i b c or e n d e z v o u s 、s c r i b e 、p a s t r y 、h e r m s 、c a n 、c h o r d 等。结构 化的网络结构使得数据位置信息具有确定性，只要数据在网络中存在，系统总能 够发现它，从而提高了资源发现的准确率。 结构化p 2 p 网络可分为p u r e - p 2 p 网络的p u b s u b 系统和s u p e r - p 2 p 网络的 p u b s u b 系统，前者指p 2 p 网络中的每个节点同时作为事件代理和客户端，如s c r i b e 系统；后者指p 2 p 网络中的每个节点只作为事件代理，每个代理连接若干个客户 端，客户端不在p 2 p 网络中，如h e r m e s 。这两种结构本质上是一致的，s u p e r - p 2 p 结构可以看作一种特殊的p u r e p 2 p 结构，其中每个节点的应用层包含多个应用系 统实例。 1 2 3 基于事件的r f i d 网络的事件路由机制 基于事件的r f i d 网络的事件路由定义为：对于给定的输入事件消息，寻找正 确的、应当接收该事件消息的邻居路由器和本地客户的集合。 事件路由机制传承了传统口路由中的很多思想，每个代理( b r o k e r ) ( 也称事件 路由器) 通过路由算法，建立事件转发路由表。所不同的是，传统的路由机制以目 的地址进行寻址；在事件路由中，则通常基于事件的内容或类别进行寻址；由于 5 北京交通大学博士学位论文 事件通信系统的匿名和异步通信的特征，事件通信系统中，通常采用遍历机制( 如 泛洪或g o s s i p ) 来确定事件的接收者，然后建立事件通信路由，并传递事件。 现有的事件路由算法大致有两类：基于订阅语义和基于通告语义的路由。 基于通告语义的路由通常有3 个阶段：通告广播：在事件代理网络中广播 通告，确定通信对象；订阅传播：如果代理所接收的订阅与通告匹配，则代理 将订阅沿着通告传播的反向路径传送给该通告发布代理；事件传播：代理将接 收到的发布事件沿着订阅的反向路径发送给感兴趣的订阅者。 基于订阅语义的路由通常有2 个阶段：订阅广播；事件传播。这两种 路由机制都假设：匹配位置要么在事件的发布方要么在事件的接收方。两种语义 下的路由尽管在具体阶段上有所不同，本质上却是一致的。 事件代理通过维护通告路由表来转发新增和取消的通告，为订阅构建从订阅 者到发布者的路由路径。订阅路由表用来转发新增和取消的订阅”为事件构建从 发布者到订阅者的路由路径。为减轻p u b s u b 系统的负载，减少不必要的事件或订 阅在网络中的传播，使系统具有更好的扩展性，研究者们提出了许多限制和约束 网络中的事件传递数量的方法，如广告( a d v e r t i s e m e n t ) 、覆盖和合并( m e r g e ) 等。 事件路由机制主要包括泛洪路由、覆盖合并路由、广告路由等。 事件路由的最基本路由方法是泛洪法及匹配优先法m 】。这两种基本路由算法 会带来大的网络负载和节点计算开销，不适用于大规模网络的情形，却是现有成 熟事件路由算法的基础。 覆盖和合并机制【2 7 5 5 聊1 是在过滤的基础上针对订阅而提出的，目的是有效地减 少订阅消息的传播以及组播树建立的数量。利用订阅中过滤条件之间的覆盖关系 来优化订阅消息在网络中的传播数量，这种路由机制可减少路由表中路由实体的 数量，也可以减少必须要转发的控制消息数量，著名的s i e n a 2 7 1 、j e d i 2 8 】和h e 锄e s 【2 9 】 等都采用了支持覆盖关系的路由。 广告的目的是通知事件代理网络发布者将要发布事件的类型，更为合理地引 导订阅的传播。订阅定义感兴趣的事件集合，广告则定义了发布方将要发布的事 件集，通过订阅与广告的相关性，引导并限制订阅在事件代理网络的传播路径。 目前大多数基于内容的通告服务，要么是集中式的( 如l es u b s c r i b e t 5 8 1 ) ，要么 依赖于简单路由( 如g r y p h o n 2 6 ) ，这两种方法在大规模系统中，由于匹配和路由开 销的问题，在不同程度上限制了p u b s u b 的可扩展性。 1 2 4 移动环境下的事件路由机制 由于客户的移动，代理之间的路由关系发生了变化，可能造成订阅或事件丢 6 第一章绪论 失，因此，在客户移动后，需要重构新路由，且支持客户方移动的路由算法应满 足在客户移动过程中重建路由的时间段内，不会引起任何事件或订阅丢失这一约 束。 j e d i 系统首次提出了订阅者移动性支持协议，引入了“m o v e i n ”和“m o v e o u t 操作，使p u b s u b 系统支持断开连接以及重新连接操作【2 8 】，文献 5 9 】中进一步给出 了发布者移动性支持协议，这两个协议统称为移动性支持的标准路由协议。 支持移动的p u b s u b 系统协议涉及组播树重构和发布订阅消息转移两个问题。 标准协议虽然解决了移动性支持的基本问题，但存在高开销、高延时等问题【删。 为此，研究人员提出了很多优化方案，其中，由于发布者移动的主要问题在 于组播重构引起的高延时，其优化方案【4 2 】