供应链环境下一种分布式RFID发现服务

　　1引言

　　RFID(Radio Frequency Identification)技术是一种非接触、多目标、移动目标识别的自动识别技术，近年来成为自动识别领域的研究热点.该技术可以广泛应用于物流供应链、食品安全、防伪、身份识别、军事等方面.针对大型开环的RFID应用，特别是供应链环境下的应用，需要建立跨地区、跨行业的RFID公共服务基础设施和信息共享机制，作为核心公共服务之一的RFID发现服务，负责收集物品在生命周期内的过程信息，即将分布的物品信息按时问序列整合成完整的物品信息链。

　　EPCglobal网络是一种网络基础设施，负责收集、共享和访问每个以EPC(Electronic Product Code)标记的物品在供应链中移动的相关动态信息.EPCglobal网络所提供的核心服务主要包括：(1)EPCIS(EPC Information Service)：根据预定义的ECSpec(Event Cycle speeitlcation)识别或检验与EPC相关的业务事件的发生，然后存储这些业务事件作为EPCIS事件，并为本地和远程的上层应用提供查询接口.对EPCIS事件的访问权限是由每个EPCIS本地控制的，因而每个企业单独决定其EPCIS的访问控制策略.(2)ONS(Object Naming Service)：负责将一个EPC解析为对应的EPCIS或者其他服务的地址，ONS由EPC的拥有者(通常是物品的生产商)管理和维护.(3)EPCIS Discovery：ONS只是用来获取EPC的拥有者(通常为生产商)所维护的EPCIS服务地址，但是在供应链中，其它企业的EPCIS也可能捕获了与该EPC相关的物品动态信息，而通过ONS不能获取这些EPCIS服务的地址.这种服务由EPCIS Discovery提供.在多个参与方组成的供应链中，某参与方通过EPCIS Discovery可以查询到某一物品的组成部分/成分，这些组成部分/成分来自于何处，以及该物品如何交付给最终用户。

　　一般来说，供应链连接着很多企业，从原材料的生产商开始，到使用物品的最终客户结束.此外，一个企业也可能存在于多个供应链中.供应链中的企业通常会有如下三种基本查询请求：(1)Pedigree查询，追溯物品的完全历史信息，包括在何处加工或发生变化，以及原材料来自于何处等.(2)Recall查询，查明一批物品的当前位置.(3)Bill-of-Material(BOM)查询，识别物品所有组成部分或原材料的生命周期信息，这种追溯式查询需要对物品进行递归的组装或分解过程。

　　目前对RFID发现服务的研究存在三个问题：(1)在大型开环的RFID应用(特别是供应链环境)中，物品数量及物品信息链的数据量十分庞大，因而服务器过载问题严重;(2)面对高强度的查询压力，发现服务器容易失效，所以在单点失效情况下应能继续提供有效的服务;(3)企业的EPCIS信息属于私有信息，需要有效地对允许共享的信息和绝对保密的信息进行控制.为了解决这些问题，同时保持较高的查询响应效率，本文从大规模实际应用的需求出发，在企业对其EPCIS进行完全的访问控制的基础上，选择了一种切实可行的模式，即“跟踪供应链”模式，以该模式为基础，提出一种新的具有分布式结构的RFID发现服务;重新为EPCIS事件进行建模，使之能够表达供应链活动中的绝大多数事件;结合分布式和并行处理技术来改进查询路由并缩减跳步数。

　　2相关研究工作

　　目前，国内外对RFID发现服务解决方案的研究可以分为以下三种：

　　(1)集中式仓库型

　　这种模式中有一个中央的全局数据仓库，物品在供应链中移动时所产生的EPCIS事件的详细信息不仅存储在企业本地，还要上传到全局数据仓库.尽管这种模式容易实现，但对于海量数据的存储以及提供有效的查询响应是相当困难的;此外，这种模式缺乏对私密性的保护。

　　(2)集中式索引型

　　它是EPCglobal提出的一种改进的模式，这种模式有一个全局的中央DS(Discovery Server).当物品在供应链中移动时，供应链各环节产生的EPCIS事件的详细信息存储在企业本地，而本地企业仅将轻量级的事件索引推送给中央Ds.这种模式在一定程度上保护了企业的隐私，并显著降低了中央DS存储的信息量，也降低了数据库的查询代价.但这种模式提供的用户接口较为复杂。

　　(3)跟踪供应链型

　　这种模式采用分布式结构来代替上述两种模式中的中央服务器.IBM和Microsoft公司目前正在从事该模式的研究，研究一种叫做“Theseos”的查询引擎.这种查询引擎绑定在每一个EPCIS上，接收来自本地用户的查询请求后，首先根据本地的数据和私密性策略对查询请求进行处理，然后根据本地查到的物品移动信息修改原查询请求和识别出相关参与方，并将修改后的查询请求转发给供应链上的相关参与方.上述查询过程叫做“Process and Forward”，该过程沿着供应链中每个相关的EPCIS递归的重复执行.每个相关的参与方将本地的查询结果和从其它参与方返回的查询结果进行整合，并将整合的查询结果转发给向它发出查询的参与方，最终所有关于该物品的查询结果就会返回给发出初始查询的客户端.这种模式取消中央Ds，但是查询响应时间较第二种模式长，这是因为一个初始查询会衍生出多个新查询，而且这些查询的结果也需要经过多次转发才能返回到初始客户端。

　　通过对上述三种模式的分析，第二种模式是建立在企业愿意共享EPCIS数据(如：事件的索引)的假设之上，一旦这个假设在以后的实际应用中不成立，我们就会发现第三种模式更具可行性.因此，本文以第三种模式为研究重点，研究如何在这种模式的基础上改进查询路由策略，以及减少查询结果返回的转发次数。

　　3一种分布式RFID发现服务系统

　　本节给出了RFID发现服务的一种分布式结构，该结构改进了“跟踪供应链”模式(或者说“Theseos”方法).第一，客户端的查询请求不仅提交给本地的EPCIS，还可以提交给被查询物品的所有生产商的EPCIS，而这些EPCIS可以根据被查询物品的EPC编码来查询ONS得到.这样处理以后，一个查询就可以分解为多个并行的查询流，从而可以提高查询处理的效率.第二，通过本地缓存机制来处理并行查询流之间的“查询碰撞”.“查询碰撞”是指由于多条查询流并行，同一节点可能先后接收到其直接上下游节点发来的相同查询.为了避免重复查询，后来的查询应该被忽略.第三，供应链中的每个节点将其本地查询结果直接返回给发出初始查询的节点，从而避免查询结果沿着查询转发过来的路径的反方向经多次转发回到客户端。

　　3.1基本假设

　　本文提出的方法基于三个假设：(1)在同一个供应链中，各参与方彼此共享它们的EPCIS数据.调查表明，为了降低成本、加强重点业务和关键环节、寻找增加收入的新机会，业务伙伴之间是乐于共享业务信息的.(2)“one step back.one step forward”原则.ISO/DIS 22005提出了该原则，并详细说明了可追溯性的要求，即每一个交易至少能够确定它的直接上游(供应方)和直接下游(接收方).(3)利用ONS.由于ONS系统已经建立起来并投入了实际应用，我们可以利用ONS来获得物品的生产商的EPCIS地址。

　　3.2分布式结构概述

　　RFID发现服务系统由安装在各个EPCIS节点上的Ds引擎构成，每个DS引擎仅为其所在的供应链伙伴节点提供访问内部EPCIS信息的接口，每个Ds引擎只知道其直接上游和直接下游的节点的访问接口地址.系统的总体结构和查询处理流程如图1所示。

图1 RFID发现服务系统的分布式结构和查询处理流程

　　这种分布式结构下的查询处理流程可分为4个阶段，其中这种结构的特点体现在(1)，(3)和(4)。

　　(1)发起查询：首先，客户端生成一个具有唯一标识querylD的初始查询，查询参数是一组EPC编码.然后，客户端查询现有的ONS服务，将所有Epc编码一一交给ONS解析(步骤①).ONS返回EPC编码对应的生产商节点的EPCIs(或DS引擎)地址(步骤②).接着，客户端分别向每个已知的EllIS并行发起对相应EPc编码的查询，同时客户端也将初始查询交给本地DS引擎处理(步骤③显示了2条并行查询流)。

　　(2)处理并转发：每个节点的DS引擎接收到查询请求后首先查询其本地EPCIS的相关动态信息，然后根据本地查询结果生成与其直接上游和直接下游相关的若干新查询请求.然后，每个DS引擎并发地向其直接上游或直接下游发送对应的新查询请求(步骤④，⑥)，并且每个Ds引擎并发的将其本地查询结果直接返回给发起查询的客户端(步骤⑤，⑦).这个过程沿着供应链上相关的EPCIS递归地进行，直到每条查询流达到供应链边界节点或与另一条查询流“碰撞”.图1用白色“云朵”代表这些过程。

　　(3)解决“查询碰撞”：DS引擎会把它已经处理过的查询忽略掉，例如，对图1中的灰色矩形来说，若来自左侧的查询早于来自右侧的查询，并且两个查询具有相同的EPC编码作为参数，则来自右侧的查询将被忽略.处理这种“查询碰撞”既能避免重复查询，又可避免在局部节点之间形成死锁。

　　(4)合并所有查询结果：客户端将在预定的等待时间内把从不同节点接收到的查询结果整合、排序，得到最终查询结果.因各节点是并发地返回结果，那么客户端需分辨哪些结果属于同一个初始查询，为此，需要保证所有转发的查询的queryID与初始查询保持一致。

　　3.3EPCIS模型

　　图1 RFID发现服务系统的分布式结构和查询处理流程为了增加供应链中物品的可跟踪/追溯性，同时更加全面地描述供应链活动中产生的各种事件，尤其是对那些涉及到将原料加工制成新产品的业务事件，本节对图1中每个EPCIS中的数据重新进行建模.基于EPCglobal EPCIS Spedfieation Ratified Standard中定义的事件类型，我们给出了五种事件类型，其中包括一个基类事件和四个派生类事件，如图2所示.它们可以表达在各个行业的供应链活动中产生的事件.根据假设(2)，我们在EPCIS的数据模型中加入了属性“receiveFrom”和“sendTo”，分别表示某节点的直接上游(供应方)和直接下游(接收方)。

图2 EPCIS的数据模型

　　(1)EPCISEvent是所有事件类型的基类，它描述了EPCIS所捕获事件的一般特征，包括事件的发生时间，发生地点以及基本的业务背景.eventTime是事件的发生时间;recordTime是事件的记录时间，是一个可选的属性：bizStep 是一个BusinessStepID，它记录了事件所属的业务步骤，通过该属性可以实现业务步骤的跟踪;org记录了事件在哪个企业发生;bizLocation记录了事件发生时所处的位置，例如，“warehouse #1”;readPoint记录了事件在哪个物理位置发生，通常由物理读写器所标识，例如，“dock door #12”。

　　(2)ObservationEvent 描述了“物品仅被观察到但没被处理”这样一类事件.epcList是一个EPC编码;receiveFrom记录了物品的直接上游(供应方)，它以GeneralManagerNumber的形式唯一标识一个企业;sendTo记录了物品的直接下游(接受方)。在ObservationEvent中，receiveFrom和sendTo两个属性只能有一个有值。

　　(3)AggregationEvent表达了物品的包装/组装与解包装/拆卸的发生，例如。“一些零件被装入箱子中”。parentID标识了包装物品的容器，或是由多个部件组装成的新物品;childEPCs是一个EPC编码列表，它记录了事件所涉及的所有被组装的部件;action描述了事件中所发生的动作，例如，“ADD”表示包装/组装。而“DELETE”表示解包装/拆卸。

　　(4)QuantityEvent描述的事件只关注同一类物品的数量，而不关注具体的单品。epcClass描述了物品的种类;quantity记录了该类物品的数量。

　　(5)TransfromEvent刻画了多个物品经过加工处理以后生成新物品的事件，例如，“一块猪肉和一袋面粉加工成一些香肠”。materials是一个EPC编码列表，记录了所有的原材料;products也是一个EPC编码列表，记录了利用原材料加工成的所有物品。

　　上述四个派生类事件都通过一个“bizStep”属性关联了一个“业务处理步骤类”(BizStep)，它刻画了事件发生时所处的业务背景。

　　3.4 查询处理过程和算法

　　下面针对3.2节的每个阶段给出具体算法，详细讨论查询处理过程。首先定义算法中必要的数据结构。

　　(1)发起查询

　　这是本文对“跟踪供应链”模式的一点重要改进，利用ONS的作用尽可能找到多个查询入口，这样在发起查询时就可以并发执行多个查询流，下面用算法“startQuery”描述该过程。

　　(2)处理并转发

　　该过程用算法“processAndRoute”描述，包括5个步骤：第一，检查是否有“查询碰撞”发生;第二，在本地EPCIS中执行查询(详见3.5节queryLocal);第三，根据本次查询和本地查询的结果，重新生成若干与直接上下游节点相关的查询(详见3.5节rewriteQuery);第四，并行地将每个新查询转发给相应的上下游节点;最后，将本地查询结果直接返回给初始客户端。其中，后四步仅在未发生“查询碰撞”时才执行。

　　(3)解决“查询碰撞”

　　采用本地结果缓存机制来解决“查询碰撞”问题，将偶对(本地收到的查询，对应的本地查询结果)利用某种机制(如Least Recently Used(LRU)，Time to Live(TTL))缓存起来.DS引擎在处理一个收到的查询之前，先通过本地结果缓存检查该查询是否已被处理过，判断条件是：该查询与缓存中的某查询具有同一queryID并且前者的epcList是后者epcList的子集.该过程用算法“cheekIfQueriesCollision”描述如下.

　　(4)合并所有查询结果

　　既然每个DS引擎各自将其本地的查询结果直接返回给初始客户端，那么，经过一段预定义的等待时间后，客户端首先从返回的结果集合中选择与初始查询具有相同querylD的结果，得到一个结果子集，然后根据eventTime对该子集中所有EPCISEvents排序，形成最终应答结果.该过程用算法“combineResults”描述如下.

　　3.5 processAndRoute相关细节

　　本节讨论算法“processAndRoute”中两个关键过程“queryLocal”和“rewriteQuery”.“queryLocal”负责对本地EPCIS执行查询：首先检查本地结果缓存是否缓存了该查询的结果.如果没有缓存结果，则需要查询本地EPCIs.因为AggregationEvent和TransformEvent记录了与查询的EPC编码具有“包装/组装”、“解包装/拆卸”或“加工变化”关系的其它EPC编码，所以先查询这两类事件中与查询的EPC编码相关的事件，并找到与这些事件关联的其他EPC编码.然后将新发现的EPC编码与原查询的EPC编码合并成一个集合，并在ObservationEventQuantityEvent这两类事件中查询与该合集中的任何一个EPC编码关联的所有事件.最后将本地查询结果添加到本地结果缓存，并返回给初始客户端.具体算法描述如下。

　　根据本地的查询结果，“rewriteQuery”负责将查询重写成与其直接上、下游节点相关的新查询请求.因为ObservationEvent和QuantityEvent记录了本地节点与其直接上、下游节点之间的物品收发(from-to)关系，所以需要对这两类事件进行分析：若某个事件具有receiveFrom属性，则可生成向直接上游节点转发的新查询;若某个事件具有sendTo属性，则可生成向直接下游节点转发的新查询.最后对所得的所有新查询，将具有相同routeTo的查询的epcList合并，这样多个查询合并为一个查询以减少新查询的数量.具体算法描述如下

　　表1 RFID发现服务查询结果的一个实例

　　3.6 RFID发现服务的查询结果

　　采用3.2-3.5节给出的RFID发现服务，能够查询到与给定物品(及其零件、原料)相关的、发生在供应链不同节点的所有EPCISEvent集合.下面通过一个典型实例来描述RFID发现服务查询结果的结构：一件产品D由10个零件C组装而成，每2个零件C由3件原料A和5件原料曰加工制成.D的制造商，从原料A的供应商采购3000件原料A，从原料曰的两个供应商sal，sB2分别采购3000件和2000件原料B，用原料A，B加工制成一批零件C，然后把每10个零件C组装成一件产品D，最后将100件D发给D的分销商DD，DD又将50件D发给一个零售商%.表1列出了与产品Dl相关的查询结果。

　　4算法性能分析

　　4.1效率实验分析

　　为了检验本文提出的分布式发现服务的性能，我们实现了一个原型系统(DDs)，还实现了“Theseos”与DDS进行对比.这两个系统都是以webservice方式实现的，采用Java 1.5和JAX.WS 2.1技术.节点间的所有通讯都以webservice调用方式进行.ONS系统基于Berkeley Internet Name Domain(B帅)实现.每个服务单独运行于一台计算机上，每台计算机配置了Pentium(R)Dual-Core2.5GI-Iz处理器、3GB RAM和相同的Windows、Microsoft SQL Server.实验的测试数据是人工生成的，在特定的供应链网络布局下，给出一定数量的不同物品以及产生这些物品的起始节点集合，然后采用以下数据生成规则：一个物品产生后，有四种可能发生的动作(运送到邻居节点、同另一物品组装起来或从一个物品中分离出来、被加工制成新的物品、不再被移动)，动作的选择是随机进行的，并且选择“运送到邻居节点”的概率随着该物品路径长度的增加而减小.为了检验上述两个系统在查询响应时间上的效果，我们生成的测试数据包含一个最大长度为20的供应链、0.5-1万个物品和2.5-3万条EPCIS事件。

　　我们测试了Recall查询的总体运行时间与物品在供应链中移动的最大长度之间的关系.图3给出了对100个查询的平均运行时间，每个查询都是从供应链的一个前端开始寻找10个不同物品的所有Observation和Quantity事件.实验结果与预期的结果一致，由于查询转发次数和查询结果逆向转发次数的增加，Theseos方法的响应时间随着路径长度的增加而增长，而DDS方法受此影响较小.在物品移动路径的长度≤6时，采用Theseos方法的查询效率高于DDS方法，这是因为DDS在将初始查询分解为多个并行查询流之前，需要查询ONS服务，相比之下，Theseos方法直接发出一个查询流，没有访问ONS的代价，所以在一定程度上(路径长度≤6)响应时间反而更短一些.但是随着路径的增长，DDS的优势(多个并行查询流、直接返回查询结果)越来越明显，所以其响应时间的增长率低于Theseos.图4给出了相同实验配置下对BOM查询的测试结果.在这个实验中，物品之间具有2—3层的包含关系，并且每个查询都是寻找与物品相关的所有Observation，Quantity，Aggregation和Transform事件，因此响应时间总体上大于Recall查询.Theseos和DIY3在响应时间上的对比情况同第一个实验类似，造成的原因相同。

图3 Recall查询的平均执行时间

图4 BOM查询的平均执行时间

　　上述两组实验表明在物品移动路径较长(>6)时，DDS比Theseos方法具有较短的响应时间.因而DDS更加适合较大规模的供应链应用，随着生产和物流规模的扩大，供应链将涉及越来越多的属于不同地区、国家甚至大洲的企业，最大路径长度将很少在6以内。

　　4.2网络消息开销分析

　　DDS和Theseos两种方法在网络消息开销方面，采用量化分析.设尚待发现的供应链实例∞：(n，e>，其中n为供应链拓扑结构图的节点数目，且所有节点均正常工作，e为节点之间的边数;i为DDS中初始查询首次分解成的并行查询数目;X为供应链中单次消息转发的网络开销，y为DDS中单次查询ONS的网络开销.因为Theseos中递归的查询转发过程和结果返回过程相当于2次遍历阳的所有边，故网络消息开销为cr=2Xe.因为DDS中解决了“查询碰撞”，避免了重复查询，所以多个并行查询流的转发过程当于遍历sc的所有边，而结果返回过程是各节点直接返回给发起初始查询的节点，再加上查询ONS和首次发出并行查询流的网络开销，总计

　　但由于X，Y，是常数，i通常较小。故开销相差不会很大;(2)随着e变大，必然使co

　　4.3可用性分析

　　在可用性方面，若DDS和Theseos均不采用额外措施，则在某节点故障时，当前查询均失败，但由于DDS中多个并行查询流的存在，其它查询流还可以访问到更多的节点，从而获得比Theseos更丰富的查询结果，尚可满足一定的用户需求.当目标节点故障时，源节点可将该查询转发到其所知的某个(些)邻居节点，但不能保证查询能从这个(些)邻居节点延续下去.由于节点之间没有信息冗余备份机制(这是由EPCIS的私密性决定的)，解决节点故障的策略尚需进一步研究.但可以说，在同等条件下，DDS比Theseos更具有可用性。

　　5结论

　　本文针对大规模的RFID应用，提出了一种新的具有分布式结构的RFID发现服务，用来在完全分布式的EPCIS节点中发现物品在供应链中发生的业务事件.首先，本文扩展的EPCIS事件模型适用于对供应链中物品的跟踪和追溯，并且新增加的事件类型“TransformEvent”进一步满足了实际应用需求，用来对那些涉及到将原料加工制成新产品的业务事件建模.本文提出的分布式RFID发现服务(DDs)，综合了分布式技术和并行处理技术，给出了基于ONS的并行查询模式，改进了查询的转发机制并且减少了查询结果返回的路由跳数.通过与Theseos方法的对比实验表明，供应链的规模越大(如最大路径越长)，DDS方法比Theseos方法具有更高的查询效率.

　　DDS系统目前已应用于酒类防伪，跟踪产品在生产商、批发商、零售商等供应链环节的移动细节，追溯产品来源以达到防伪目的;还应用于志愿者卡管理，将REID编码嵌入志愿卡证，可实时监控志愿者所在岗位，以及追溯志愿者从事志愿活动的历史记录，方便对志愿活动的组织和管理.下一步，我们需要进一步研究DDS的服务质量(QoS)模型和控制方法，使发现服务的服务质量得以量化和评估.另外，RFID发现服务的最终目的是让供应链上的各企业充分利用发现的数据集，从而改进自己的关键业务环节甚至供应链结构，因此将来还要研究针对发现服务查询结果的分析方法。