云制造资源服务的组织与发现机制*

张倩 齐德昱

(华南理工大学计算机系统研究所，广东广州510006)

云制造的目标之一是实现制造资源的全面共享，其中制造资源服务的组织与发现是获得共享制造资源的关键．制造资源服务的分布性、自治性和动态性等特点，以及云制造资源服务用户请求的异构性和复杂性，使得云制造模式下的资源服务组织与发现面临着挑战．

已有的资源服务发现系统大多采用集中式、层次式、对等式(P2P)以及混合式等机制对资源服务进行组织，并设计相应的资源服务发现算法．但这些算法主要研究网格模式下计算资源、文件资源、制造资源的发现机制，因此只能起到一定的借鉴作用，不能完全照搬迁移到云制造资源服务的组织与发现中．至今已有许多学者针对云制造模式下制造资源服务的组织与发现机制进行了研究．文献［1］中提出了一种基于分布式哈希表(DHT)的自组织云制造资源聚集方法，并设计了基于四叉树的多维属性区间搜索方法;文献［2］中提出了基于语义Web和本体知识的制造资源发现框架，该框架构建在集中式的统一描述、发现和集成协议(UDDI)注册中心之上;文献［3］中提出了一种智能化的云制造服务搜索与匹配方法，通过分级匹配策略来实现云制造服务的高效精确匹配;文献［4］中提出了基于资源云服务(RVCS)的云制造资源封装、发布和发现模型;文献［5］中提出了云制造服务语义匹配模型，通过参数匹配、属性匹配、综合匹配和量化匹配程度来实现云制造服务的智能匹配;文献［6］中将云制造资源服务匹配看作是一个复杂的多属性决策优化过程，提出了基于模糊积分的云制造资源服务匹配方法．然而，这些研究大多从服务发现角度进行研究，较少考虑到制造资源服务的组织方式;除文献［1］外，其他研究不支持制造资源服务属性值的范围查询．

考虑到云制造资源服务的分布性、自治性和动态性等特点，基于P2P的资源服务组织与发现机制是一种较为理想的解决方案．作为一种实现P2P的结构，DHT技术得到了广泛的研究与应用．但目前基于DHT的资源服务发现中，基于关键字的精确匹配的研究居多，而云制造需要基于制造资源服务的属性值进行查找．为有效地组织云制造资源服务和支持复杂的用户搜索，文中从制造资源服务的注册与部署角度出发，提出了基于DHT和分层的资源服务组织模型，并设计了支持5种查询方式的云制造资源服务发现算法．

1 基于DHT和分层的资源服务组织模型

1．1 相关定义

定义1 制造资源服务(MRS)是指已经虚拟化封装为服务，并注册和发布到云制造服务平台的逻辑制造资源．根据部署方式的不同，制造资源服务可分为托管型和本地型两类．

定义2 托管型制造资源服务(T-MRS)是指资源提供方发布的资源将部署到云制造服务平台管理的服务器中，并提供服务器IP地址和一定的带宽给资源提供方，资源提供方只需采用远程管理方式对制造资源服务进行维护．

定义3 本地型制造资源服务(L-MRS)是指制造资源服务仍部署在资源提供方本地的服务器中，云制造服务平台只需建立该资源服务的索引．

定义4 服务部署节点(SDN)是指T-MRS的宿主节点．

定义5 服务注册节点(SRN)是指制造资源发布和查询的入口，主要职能包括:管理多个SDN、实现MRS的注册和检索、与其他SRN进行通信．

定义6 自治域(AD)是指由一个SRN和多个SDN构成的自治管理的制造资源服务域．

1．2 云制造资源服务组织模型

图1 基于DHT和分层的云制造资源服务组织模型Fig．1 Organization model of cloud manufacture resource services based on DHT and layered structure

如图1所示，文中提出的分布式云制造资源服务组织模型采用分层的管理方式，逻辑上分为3层．下层是资源服务层，由各种T-MRS组成．中间层由若干AD组成，L-MRS只需在SRN中登记其索引信息．每个自治域可根据处理能力和可用性指标选出SRN，同时选出备份节点，随时监控SRN并保存其运行日志，一旦SRN失效，便切换到备份节点并依次运行日志来同步数据，同时选出新的备份节点．上层为由负责MRS注册的SRN组成的基于DHT的覆盖网，可采用比较成熟的 Chord［7］、Pastry［8］、CAN［9］或Tapestry［10］等DHT协议，文中采用Chord协议．

1．3 云制造资源服务的组织结构形成机制

为便于进行范围查询和多属性查询，需要一个自治域中能尽量存储属性相似的资源服务．利用基于局部性敏感的哈希(LSH)函数［11-12］能将相似的资源服务映射到标识相同或相近的节点上．如图2所示，节点和资源服务均被映射到一个大小为2l的环状标识空间(文中取l=160)，利用哈希函数(如SHA-1［13］)将SRN的IP地址和端口号映射到标识空间，这样，每个SRN将管理与他相邻的前一个节点之间的区间．MRS的关键属性(将在1．3．2节中详细介绍)经过LSH函数(如Simhash［12］)映射到同一标识空间．根据LSH的特性，相似的MRS将以高概率映射到相同的SRN中．文中采用Chord协议来实现这种映射关系，资源服务标识i将被映射到沿Chord环顺时针方向所找到的第一个节点，即节点标识大于等于i的第一个节点上．

图2 DHT的结构Fig．2 Structure of DHT

1．3．1 节点的加入和离开

基于DHT的覆盖网的建立和维护是一个动态的过程，节点可以随时加入和退出．节点的加入包括SRN的加入和SDN的加入．其中，SRN的加入算法可利用Chord协议中的节点加入算法，这里不再阐述．当SDN加入时，可向与之最近的SRN发送加入其自治域的申请信息，SRN确认接收后，与之建立连接，并更新其SDN管理表．

SDN的离开分为正常退出和异常退出两种情况:①当SDN正常退出时，只需更新其域内SRN中的SDN管理表和MRS索引表，并将其内部署的资源服务进行重新注册．此过程不会影响域内SRN的路由表中的信息，可有效降低节点频繁离开覆盖网所引起的波动．②当SDN异常退出时，SRN通过周期的SDN状态监测进程可截获此异常，从而进行信息更新．

每个自治域的SRN起着极其重要的作用，既要负责覆盖网的拓扑维护和各种信息的路由，又要负责SDN的管理，以及资源服务的注册和查找工作．同样，SRN的离开也分为正常退出和异常退出两种情况．当SRN正常退出时，将SRN管理的自治域内的SDN及其内部署的资源服务一起迁移到SRN的后继节点中，更新后继节点的SDN管理表和MRS索引表，并调用Chord协议中的节点退出算法修改SRN的前驱和后继节点中的信息．SRN的备份节点实时监控SRN并保存其运行日志，一旦检测到SRN失效，便可切换到备份节点并依次运行日志来同步数据，同时选出新的备份节点，这样可将SRN的失效影响限制在本AD内，同时维持覆盖网的拓扑结构．

1．3．2 资源服务的维护

文中采用基于属性的方法对MRS进行描述，每个属性用一组〈属性名称，属性值〉来描述．以模具加工外协服务为例［1］，该服务可描述为属性集合C:{Service Name=模具加工，Service Quality=98%，Dimensional Precision=1T6，Surface Roughness=Ra 0．2μm，Service Duration=3 个月，… }．如果将资源服务的每个属性分别进行注册，当属性的数量较多时，资源服务的索引维护开销将很大．制造资源服务一般具有多个属性，而用户往往只对其中的一小部分属性感兴趣，文中将用户感兴趣且最能代表制造资源服务能力的属性作为关键属性．如可选择资源服务的名称、服务质量、尺寸精度和表面粗糙度作为模具加工外协资源服务的关键属性．实际中制造资源服务的关键属性及其个数m可以根据资源服务类型灵活定义．任何制造资源服务均可以动态地加入和退出，故其维护包括资源服务的注册和退出过程．

(1)资源服务的注册．根据资源服务部署方式的不同，资源服务注册可分为T-MRS注册和L-MRS注册．假设选定的资源服务关键属性为 key［］={key1，key2，…，keym}，文中分别给出这两种情况下的资源服务注册算法．T-MRS注册算法描述如下:

资源服务注册算法的主要思想为:①每个资源服务将被注册到m个目标SRN中，即在m个SRN中建立该资源服务的索引;②资源服务实际上至多被部署到K个SDN中，且该SDN有足够的能力(部署和运行T-MRS所需的CPU、内存、带宽等)接受新资源服务的部署．

T-MRS注册算法描述了当资源服务在节点n发起注册请求时，资源服务部署和建立索引的过程．L-MRS的注册无需部署，只需在对应的SRN中建立索引信息．基于T-MRS算法易得到支持L-MRS的注册算法，这里不再赘述．

(2)资源服务的退出．当T-MRS正常退出时，向其所在的SRN发送退出请求，SRN收到资源服务退出请求后，删除此资源服务的索引信息及SDN中的部署信息，并通知其他存有此资源服务索引的SRN以及部署此资源服务的SDN进行相应地删除．由于T-MRS被部署到k个不同的SDN中，因此，只有在副本均失效的情况下，资源服务才会变得不可用．

当L-MRS正常退出时，只需删除各关键属性对应SRN中的该资源服务的索引信息．若m个资源服务的索引均失效，则将无法访问该资源服务．

2 云制造资源服务发现算法与分析

2．1 资源服务发现算法

从查询请求中属性的个数和查询条件的范围来看，资源服务发现可分为5类:①单属性单值查询(s1)，如“Service Name=模具加工”;②多属性单值查询(s2)，如“Service Name=模具加工and Service Quality=98%”;③单属性范围查询(s3)，如“Service Quality＞98%”;④多属性范围查询(s4)，如“Service Quality＞98%and Surface Roughness ＜Ra 0．2μm”;⑤Top-k查询(s5)，如“满足Service Name=模具加工and Surface Roughness＜Ra 0．2μm的k个资源”．

文中仅给出s4查询算法，其他4种查询算法可根据s4查询算法修改得到，此处不再赘述．s4查询

算法描述如下:

在s4查询算法中，搜索范围被划分为多个连续整数值，对每个单值进行基于DHT的查找定位，多个单值查询结果的汇总即为满足范围查询条件的资源服务．Top-k查询算法只需在查询节点按照某种优化选择算法对汇集的查询结果进行排序，进而获得最优的前k个资源服务．此外，每个SRN维护一个缓存以保存由此节点产生的查询结果，可提高检索效率．缓存的容量有限，其内运行LRU替换算法．资源服务的动态性可能导致缓存内容与实际的资源服务索引信息不一致，为避免向用户提供不可用的资源服务，需要周期性地检测缓存中的内容是否可用，当资源服务退出时，应及时删除缓存中对应的项．

2．2 算法分析

文中采用搜索延迟和消息开销两个指标对资源服务发现算法的性能进行分析．搜索延迟是指查询消息从发起节点到达目标节点需要经历的跳数;消息开销是指一个资源服务发现请求在覆盖网中产生的搜索消息总数．

定理1 在N个SRN节点组成的覆盖网中，资源服务发现算法的搜索延迟为O(log2N)．

证明 (1)s1算法的搜索延迟为DHT搜索延迟O(log2N)．

(2)文中多属性单值搜索的思路是:若查询q个关键属性，则对每个关键属性分别使用单值查询算法进行并行查找，最后将结果汇总．可见，s2算法的搜索延迟是q个单属性单值搜索延迟中的最大值，为O(log2N)．

(3)在s3算法中，查询范围被划分为t个连续整数值，可看成是t个单属性单值的并行查询．因此，s3算法的搜索延迟是t个单属性单值搜索延迟中的最大值，即O(log2N)．

(4)s4算法是在多个单属性中进行单值范围查询，故s4算法的搜索延迟仍为O(log2N)．

(5)s5算法是在上述算法的基础上再利用某种优化算法进行选取，因此其搜索延迟亦为O(log2N)．

综上可得，文中提出的资源服务发现算法的搜索延迟为O(log2N)．证毕．

定理2 在N个SRN组成的覆盖网中，资源服务发现算法s3的消息开销下界为 O(log2N)，上界为O(tlog2N)，其中t为搜索范围的划分粒度．

证明 根据定理1中的分析，s1算法的消息开销为DHT消息开销O(log2N)．s2算法的消息开销为q个单属性单值查询消息开销的总和，即O(qlog2N)．

在s3算法中，搜索范围被划分为t个连续整数值，根据局部哈希函数的性质，这t个连续整数值将以高概率映射到同一个SRN节点上．在最好情况下，即t个连续整数值映射到同一个SRN节点上，则只需发送1条查询请求即可检索到该范围内的所有资源服务，等同于单属性单值搜索，因此s3算法的消息开销下界为O(log2N);在最坏情况下，即t个连续整数值映射到t个不同的SRN节点上，则需发送t条不同的查询请求才能检索出所有满足条件的资源服务，因此s3算法的消息开销上界为O(tlog2N)．证毕．

由定理1中的分析可知，s4算法是在多个单属性中进行单值范围查询，结合定理2，可得到s4算法的消息开销下界为O(qlog2N)，上界为O(qtlog2N)．

从以上分析可以看出，随着q、t取值的增大，系统的存储负担和查询消息开销有所增加．但在文中提出的云制造资源服务组织模型中，大部分发布的数据都是资源服务的索引，每个数据的信息只有几千字节，因此不会给系统增加太多负担．同时，虽然资源服务部署的信息较大，但资源服务副本的增多保证了资源服务的可用性和健壮性．在实际应用中，可根据需要合理地设置q和t的取值．

文中提出的资源服务发现算法可以看成是由两步完成:①定位到可能含有资源服务的SRN节点;②基于关键词的匹配．某个资源服务是否属于集合M是在关键词匹配时确定的．可见，第1步的定位机制对服务平台查准率不造成影响，第2步采用基于关键词的精确匹配方法，因此，文中算法的查准率为基于关键词匹配的查准率．

设搜索范围的划分粒度为t时，返回的制造资源服务集为M;搜索范围的划分粒度为t'(t'＞t)时，返回的制造资源服务集为M'．当搜索范围的划分粒度为t时，对应的关键词较少，由查准率分析可知，集合M也较小;当搜索范围的划分粒度为t'时，划分粒度细，关键词较多，则增加了资源服务加入到集合M的概率，即增加了M'＞M的概率．由此可见，提高搜索范围的划分粒度，在一定程度上可提高资源服务发现算法的查全率．

3 仿真实验

仿真实验采用开源 P2P模拟器 Peersim［14］，使用Chord协议构建覆盖网的拓扑结构，并以事件驱动方式对文中提出的模型和算法进行模拟实现及性能分析．为了简化问题和便于仿真实现，文中忽略在一次资源服务搜索过程中SRN拓扑结构以及资源服务的变化．资源服务发现请求由系统随机选择一个SRN发起，实验结果为独立重复1000次实验的平均测试结果．

3．1 搜索延迟分析

首先评估不同网络规模下各种资源服务发现算法的搜索延迟．实验中SRN节点数N从1000增加到10000，每次增加1000个节点;资源服务关键属性个数q分别取值为1、2、10;搜索范围为任意两个相邻节点之间的间隔，划分粒度t=10．实验结果如图3所示．

图3 搜索延迟与SRN节点数的关系Fig．3 Search delay versus number of SRN

由图3可以看出，平均搜索延迟随着SRN节点数的增加大致呈对数级速度增长．当q=1时，平均搜索延迟小于，该结果与Chord算法的精确匹配查询结果一致［7］．图3表明，在多属性查询情况下，随着资源服务的关键属性个数的增多，算法的平均搜索延迟也在增加．这主要是因为多属性查询的搜索延迟是q个单属性搜索延迟中的最大值，增加了高搜索延迟取值的概率，因此降低了算法的搜索效率．在关键属性个数相同的查询情况下，虽然单属性范围查询的搜索延迟是t个单属性单值搜索延迟中的最大值，但这t个单属性单值搜索将以高概率映射到标识相同或相近的SRN节点上，因此，关键属性个数相同的单值查询的平均搜索延迟与范围查询的平均搜索延迟大致相同(见图3)．

接下来考察搜索延迟与搜索范围的关系．实验中SRN节点数N=10000，假设所有节点标识均匀分布在Chord环中，搜索范围取任意两个相邻节点之间的间隔，其大小从50倍间隔变化到400倍;搜索范围划分粒度 t分别取值为 10、50、100、150、200．在不同的搜索范围大小下，s3算法的平均搜索延迟见图4．实验表明:①在搜索范围一定的情况下，算法的平均搜索延迟随t的增大而增加，直到t等于搜索范围的大小时趋向平稳．这主要是因为t较小时，随着t的增大，搜索请求映射到标识不同SRN节点上的概率增加，即增加了高搜索延迟取值的概率;但当t大于搜索范围的大小时，搜索请求映射到标识相同SRN节点上的概率增加，因此搜索延迟趋向平稳．②在t一定的情况下，算法的平均搜索延迟随搜索范围的增大而增加，直到搜索范围的大小等于t时趋向平稳．这是因为t值一定、搜索范围较小时，搜索请求映射到标识相同的SRN节点上的概率较大;但随着搜索范围的增大，搜索请求映射到标识不同的SRN节点上的概率增加，因而增加了高搜索延迟取值的概率;在最坏情况下，搜索请求会映射到t个标识不同的SRN节点上．因此，当搜索范围的大小大于t时，不会增加高搜索延迟取值的概率．

图4 搜索延迟与搜索范围的关系Fig．4 Search delay versus search range

3．2 消息开销分析

实验条件与3．1节中考察搜索延迟与搜索范围关系的实验条件相同．单属性范围查询s3算法的平均消息开销如图5所示．由实验结果可以看出，当搜索范围一定时，算法的平均消息开销随t的增大而增加，直到t等于搜索范围的大小时趋向平稳;当t一定时，算法的平均消息开销随搜索范围的增大而增加，直到搜索范围的大小等于t时趋向平稳．产生上述结果的原因分析与3．1节中搜索延迟与搜索范围关系的实验分析类似，这里不再赘述．由于多属性范围查询算法是在多个单属性中进行单值范围查询的，因而其消息开销与单属性范围查询算法的消息开销成正比，文中没有对多属性范围查询进行比较．

图5 消息开销与搜索范围的关系Fig．5 Search message overhead versus search range

4 结语

云制造资源服务的组织与发现是实现制造资源共享的前提，具有重要的研究意义．文中提出了基于DHT和分层的云制造资源服务组织与发现机制，该机制将基于DHT的覆盖网作为基本的拓扑结构，提供了一定的容错机制，支持常见的5种查询:单属性单值查询、多属性单值查询、单属性范围查询、多属性范围查询和Top-k查询，有效地解决了分布式云制造资源服务的组织和搜索问题．下一步将在公共云制造服务平台系统的开发中具体实现文中提出的算法，并逐步解决实际开发中遇到的各种问题，进一步完善云制造资源服务组织与发现机制．

［1］刘士军，曲本科，武蕾，等．自组织云制造资源聚集框架与多维属性区间搜索方法研究［J］．计算机辅助设计与图形学学报，2012，24(3):299-307．Liu Shi-jun，Qu Ben-ke，Wu Lei，et al．Self-organizing resource integration framework and multi-dimensional range search of cloud manufacturing ［J］．Journal of Computer-Aided Design ＆ Computer Graphics，2012，24(3):299-307．

［2］Wang Weixing，Liu Fei．The research of cloud manufacturing resource discovery mechanism［C］∥Proceedings of the 7th International Conference on Computer Science＆ Education．Melbourne:IEEE，2012:188-191．

［3］李慧芳，董训，宋长刚．制造云服务智能搜索与匹配方法［J］．计算机集成制造系统，2012，18(7):1485-1493．Li Hui-fang，Dong Xun，Song Chang-gang．Intelligent searching and matching approach for cloud manufacturing service［J］．Computer Integrated Manufacturing Systems，2012，18(7):1485-1493．

［4］朱李楠，赵燕伟，王万良．基于RVCS的云制造资源封装、发布和发现模型［J］．计算机集成制造系统，2012，18(8):1829-1838．Zhu Li-nan，Zhao Yan-wei，Wang Wan-liang．Model of resource package，publication and discovery based on RVCS in cloud manufacturing ［J］．Computer Integrated Manufacturing Systems，2012，18(8):1829-1838．

［5］尹超，夏卿，黎振武．基于OWL-S的云制造服务语义匹配方法［J］．计算机集成制造系统，2012，18(7):1494-1502．Yin Chao，Xia Qing，Li Zhen-wu．Semantic matching technique of cloud manufacturing service based on OWL-S［J］．Computer Integrated Manufacturing Systems，2012，18(7):1494-1502．

［6］高一聪，冯毅雄，谭建荣，等．制造资源耦合映射与模糊匹配技术研究［J］．计算机辅助设计与图形学学报，2012，24(3):290-298．Gao Yi-cong，Feng Yi-xiong，Tan Jian-rong，et al．Research on coupled mapping and service matching technology of cloud manufacturing based on fuzzy integral［J］．Journal of Computer-Aided Design ＆ Computer Graphics，2012，24(3):290-298．

［7］Stoica I，Morris R，Karger D，et al．Chord:a scalable peerto-peer lookup service for Internet applications［C］∥Proceeding of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications．New York:ACM，2001:149-160．

［8］Ratnasamy S，Francis P，Handley M，et al．A scalable content-addressable network［C］∥Proceedings of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications．New York:ACM，2001:161-172．

［9］Rowstron A I T，Druschel P．Pastry:scalable，decentralized object location，and routing for large-scale peer-topeer systems［C］∥Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms．London:Springer，2001:329-350．

［10］Zhao B Y，Huang L，Stribling J，et al．Tapestry:a resilient global-scale overlay for service deployment［J］．IEEE Journal on Selected Areas in Communications，2004，22(1):41-53．

［11］Indyk P，Motwani R．Approximate nearest neighbor:towards removing the curse of dimensionality［C］∥Proceedings of the 30th Annual ACM Symposium on Theory of Computing．New York:ACM，1998:604-613．

［12］Charikar M S．Similarity estimation techniques from rounding algorithms ［C］∥Proceedingsofthe 34th Annual ACM Symposium on Theory of Computing．New York:ACM，2002:380-388．

［13］Federal Information Processing Standards Publication 180-1，Secure hash standard ［S］．

［14］Jelasity M，Montresor A，Jesi G P，et al．The peersim simulator［CP/OL］．(2011-07-23)［2013-01-07］．http:∥peersim．sf．net．