ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.doczj.com/doc/0518857805.html,
Journal of Software, Vol.21, No.8, August 2010, pp.1795?1809 https://www.doczj.com/doc/0518857805.html, doi: 10.3724/SP.J.1001.2010.03669 Tel/Fax: +86-10-62562563
? by Institute of Software, the Chinese Academy of Sciences. All rights reserved.
?
基于Agent和蚁群算法的分布式服务发现
郑啸1,2+, 罗军舟1, 宋爱波1
1(东南大学计算机科学与工程学院,江苏南京 210096)
2(安徽工业大学计算机学院,安徽马鞍山 243002)
Distributed Service Discovery Based on Agent and Ant Colony Algorithm
ZHENG Xiao1,2+, LUO Jun-Zhou1, SONG Ai-Bo1
1(School of Computer Science and Engineering, Southeast University, Nanjing 210096, China)
2(School of Computer, Anhui University of Technology, Maanshan 243002, China)
+ Corresponding author: E-mail: xzheng@https://www.doczj.com/doc/0518857805.html,
Zheng X, Luo JZ, Song AB. Distributed service discovery based on agent and ant colony algorithm. Journal
of Software, 2010,21(8):1795?1809. https://www.doczj.com/doc/0518857805.html,/1000-9825/3669.htm
Abstract: This paper suggests an ant-like agent service discovery mechanism. There are two types of agents
cooperating to search target services: Search Agent and Guide Agent. Search Agent simulates the behavior of an ant
that searches for services on the network. Guide Agent is responsible to manage a service route table that consists of
pheromone and hop count, instructing Search Agent’s routing. Volatile pheromones make Search Agent sense the
change of topology and service resource, and hop count makes them know the distance. Semantic similarity is also
introduced in routing selection as a heuristic factor, which improves the recall. The life-span control policy makes
query traffic controllable. With system size increasing, the query traffic would increase slightly and has an upper
bound. The result of simulation shows that the suggested mechanism is scalable and adaptable enough to be suitable
for large-scale dynamic computing environments.
Key words: service discovery; peer to peer network; agent; ant colony algorithm; routing mechanism
摘要: 提出一种类似蚂蚁觅食活动的Agent服务发现机制.有两类Agent 合作寻找目标服务:Search Agent和
Guide Agent.前者模拟蚂蚁的行为在网络上发现目标服务,后者管理一个由信息素和跳数组成的服务路由表,用以
指导Search Agent的行进路线.动态变化的信息素可以让Search Agent感知到网络拓扑和服务资源的变化,而跳数可
以让它们了解距离.路由选择中还使用语义相似度作为启发因子,用于提高召回率.Search Agent生命周期控制机制
?Supported by the National Natural Science Foundation of China under Grant Nos.60773103, 60903161, 60903162, 90912002 (国家
自然科学基金); the National Basic Research Program of China under Grant No.2010CB328104 (国家重点基础研究发展计划(973)); the
Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.200802860031 (高等学校博士学科点
专项科研基金); the Jiangsu Provincial Natural Science Foundation of China under Grant Nos.BK2007708, BK2008030 (江苏省自然科
学基金); the Jiangsu Provincial Key Laboratory of Network and Information Security of China under Grant No.BM2003201 (江苏省网络
与信息安全重点实验室); the Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of
Education of China under Grant No.93K-9 (东南大学计算机网络和信息集成教育部重点实验室)
Received 2008-09-22; Revised 2008-12-18; Accepted 2009-06-01
1796 Journal of Software软件学报 V ol.21, No.8, August 2010
使查询流量负载成为可控的,并具有确定的上界.实验结果表明,该方法在大规模的分布式计算环境下具有良好的可扩展性和动态环境下的适应性.
关键词: 服务发现;peer-to-peer网络;agent;蚁群算法;路由机制
中图法分类号: TP311文献标识码: A
在服务计算环境下,服务是组成分布式异构系统的基本元素.为了使服务请求者可以迅速而有效地发现并定位服务,服务提供者要将自己提供的服务发布到一个服务注册库中.这个注册库记录了服务的功能、接口、参数和提供者等信息.服务请求者只要到注册库中即可寻找满足功能需要的服务.注册库是服务请求者和服务提供者之间的桥梁,服务查找和发现性能的好坏是影响整个面向服务应用系统性能的关键.
国内外的研究已经相继提出了多种基于P2P(peer-to-peer)网络的分布式服务注册和发现模式[1?5].这些模式将注册系统划分为若干个相对独立的注册节点.注册节点之间以P2P方式互连,并可以共享数据.分布式的服务发现通常包括两个问题[1]:一是如何迅速而有效地找到目标服务所在的注册节点;二是在注册节点上查找目标服务.后面一个问题可以用集中式服务发现的研究成果加以解决,本文只研究前面一个问题.对于此问题,以往的研究只关心召回率、响应时间等基本性能.解决方法一般是根据服务的内容,将服务按照一定的规则或映射关系存储在注册节点中,服务的内容和存储位置有一定的内在关系.在查询服务时,可以按照事先约定的规则或映射关系定位服务所在的注册节点.这种方法的组织结构复杂,发现机制简单,可以达到较短的响应时间和较高的召回率.但是在动态性较强的开放的服务计算环境下,具有一定自主性的注册节点的加入和退出会变得频繁和不确定.过分强调系统组织结构的这类方法,将导致结构的重新组织,计算开销大,可扩展性弱,适应性差.然而,系统的可扩展性和适应性是在大规模的、动态的分布式计算环境中必须解决的挑战性问题.
本文提出一种面向大规模、动态、开放的服务计算环境下的分布式服务发现机制.该机制可以保障用户有效发现服务并具有可扩展性和适应性.首先,提出一个基于非结构化P2P网络的服务注册系统模型.注册系统中的每个注册节点都独自按照服务行业划分和管理服务,为了消除歧义,行业按照一个共同的服务行业分类本体命名.其次,提出了基于Agent的服务发现技术,并用蚁群算法的思想指导Agent的行为.具体来说,就是在P2P注册系统上派出多个自主执行查找任务的Agent.在每一个注册节点,Agent根据所要查找的目标服务所属行业、相应路径上的信息素(pheromone)浓度以及距离目标服务行业的跳数来选择路径.这是一种非直接的协作方式,不需要Agent之间直接通信或传递关于路径的消息,不但可以避免盲目寻找服务,而且可以减少网络负载,节省网络带宽,有利于系统扩展.路径上的信息素由先前经过的Agent留下并积累,它可以指导后来的Agent去搜索服务.当有新的节点或资源加入到系统中时,也要向邻居节点扩散信息素.信息素具有挥发机制,那些长时间没有得到增加的信息素最终会挥发完.依靠信息素更新机制和动态变化的信息素浓度,Agent可以自主适应系统拓扑结构和注册中心服务资源的变化.需要说明的是,本文提出的机制和相关算法并不适用于结构化P2P网络.
本文第1节介绍相关研究工作.第2节介绍分布式服务注册系统体系结构,给出服务注册节点的组织方式.第3节介绍基于Agent的服务发现机制,给出Agent的行为以及基于蚁群算法的Agent路由与服务发现机制.第4节对本文提出的算法进行仿真实验和性能分析.第5节总结全文并给出下一阶段的工作.
1 相关工作
在分布式服务注册与发现的研究中,目前广泛采用P2P结构作为服务注册系统内部的组织方式,但在具体的服务发现机制和研究侧重点上有所不同.
METEOR-S[1]是一个支持语义Web服务发布与发现的基于P2P的分布式UDDI(universal description, discovery and integration).它使用一个共享的注册本体对各个UDDI服务器按照服务领域进行分类,每个UDDI 服务器必须映射到注册本体上的1个或多个结点上.UDDI服务器和注册本体之间的映射关系用于组织P2P网络的拓扑结构.在这种机制下,UDDI服务器的内容和系统拓扑结构紧耦合,存在注册本体和服务注册信息同步的问题,自适应的能力较差.而且,由于注册本体的维护是另外一套语义维护体系,增加了大规模环境下的实现
郑啸等:基于Agent和蚁群算法的分布式服务发现1797
和使用的难度.文献[3]提出了基于传统单层P2P网络的分布式服务发现机制.它使用DNS服务来登记和管理对等结点的信息,并设计了一个称为P2P Registry的Agent作为P2P网络和DNS之间的中间件.在Agent的帮助下,每个对等节点能够通过DNS注册和发现目标服务.文中提出了用Agent实现服务自动注册和发现,但是没有充分发挥Agent自主性和自适应性的特点,还要依靠一个集中式的DNS来定位目标.这个DNS类似于混合P2P 结构中的超级节点.文献[4]提出基于本体社区的双层P2P结构的服务发现模型.本体社区是注册中心的集合,这些注册中心的内容是有限制的,要根据模块化本体中的每一个模块设立注册中心,多个社区之间再通过相同的本体建立连接.因此,这种模型的结构是与本体模型结构相关的.服务发现时,先在社区内采用洪泛式的消息传递,然后在社区之间进行一步转发的消息转发方式,以实现跨社区的服务发现.该模型的特点是根据本体概念之间的关系建立分层的P2P网络,可以适应多本体共存的环境.遗憾的是,实验中注册中心和服务的数量都比较少,不能体现出所提出的模型和相关算法在较大规模分布式环境下的效率如何.与以上的研究不同的是,本文的工作面向大规模的分布式服务发现环境,更加强调系统的可扩展性和适应性.
为了减少服务发现的响应时间,已有一些研究建议对注册库中的服务按类别进行组织和管理.这样可以直接在与服务相关的领域或行业中搜索,缩小了搜索范围.UDDI提供了服务分类机制[6],包括北美行业分类系统、通用标准产品和服务分类法等,但这些分类标准并不统一而且较为粗糙,大都依靠服务的领域或地域进行划分,没有用本体方法统一分类中的概念,不支持语义发现.文献[7]提出按照GICS全球行业分类标准建立adUDDI.一个adUDDI中可以注册多个行业的服务,所有adUDDI的信息注册在一个根注册中心.具有相同行业的adUDDI相互连接,组织成一个虚拟的区域.与本文的方法相比,这种方法没有考虑行业分类中的概念之间的层次关系,即子行业和父行业之间的关系.没有建立本体库,因此并不支持语义查询.此外,GICS是投资型分类标准,只考虑了以赢利为目的的经营活动单位,行政事业单位、社会团体、各种组织协会等是不属于其分类对象范围的.因此,为了获得更全面的划分,本文采用管理型的分类标准,如中国的国民经济行业分类标准.另外,本文建立了行业分类本体,可以在语义上比较行业之间的相似度,提高了召回率.
本文运用蚁群算法的思想指导Agent的服务发现行为.蚁群算法已经成功地应用在网络路由选择[8]、负载均衡[9]、分布式QoS路由[10]、移动Agent迁移[11]等问题中.文献[12]通过在动态的、不可靠的和大规模的网络环境中模拟生物系统的一些特性,如免疫机制(immunity)、药物趋化现象(chemotaxis)等,来设计自适应、鲁棒的分布式算法,并总结了在非结构化P2P网络中的文件查找、移动自组织网络的路由、负载平衡等方面的应用. Anthill[13]是一个用于构建P2P应用的开发环境和工具.它借用多Agent和进化计算技术,利用称为蚂蚁的移动Agent在网络上漫游并执行任务.由于Anthill仅仅是一个开发环境,因此并没有提出具体的蚂蚁的路由算法.
2 服务注册系统体系结构
图1显示了本文提出的基于非结构化P2P的服务注册系统的体系结构.图中每个注册节点都是服务注册系统中的对等节点.它们以随机方式互连,组成一个松散耦合的覆盖网络(overlay).每个注册节点的逻辑结构由3个模块组成,即通信模块、服务路由管理模块和服务注册模块.通信模块实现注册节点之间按照非结构化P2P 方式互连和通信,注册节点的加入和退出遵循非结构化P2P网络的算法.这部分利用已有的研究成果实现,本文不再讨论.服务路由管理模块维护一个服务路由表,表中记录了从本地到目标服务行业的路由信息.这个服务路由表由一个称为Guide Agent的Agent来维护.服务注册模块的主体是注册库,它包含注册Web服务的元数据信息文件.为了在分布式的注册系统上发现目标服务,设计了一个可以在系统中自主漫游的移动Agent(mobile agent),这个Agent称为Search Agent.Search Agent具有生命周期,它接受查询任务,负责在服务注册系统中查找目标服务.
在服务计算环境下,服务是面向某个具体服务行业领域的.例如,租车服务属于交通运输业,而酒店预订服务属于旅游业.因此,服务注册节点可以对注册的服务按照所属行业领域进行划分、归类和管理.为了统一并确定共同认可的服务行业分类的概念和术语,有必要建立服务行业分类本体.每个注册节点都根据共同的服务行业分类本体来管理和聚集服务.本文按照国民经济行业分类标准(GB/T 4754-2002)[14]建立服务行业分类本体.
1798 Journal of Software 软件学报 V ol.21, No.8, August 2010
由于本体构建是一个复杂的工程问题,本文不再讨论如何建立一个行业分类本体.图2给出了一个服务行业分
类本体的片段.根据行业分类标准的特点,该本体是一个由概念组成的树型层次结构,概念之间的层次关系是
subClassOf 关系,表示父类和子类的继承关系.值得注意的是,对于按照其他行业分类标准建立的本体,本文的模
型和算法也同样适用. Communication
Search agent Search agent
Search agent Fig.1 Architecture of a distributed services registry system
图1 分布式服务注册系统体系结构
一个用服务行业分类本体进行语义标注的Web 服务可以表示为WS (I ),I 为服务归属的行业集合(这里忽略
了Web 服务的输入、输出等).图3是一个服务注册模块的组织结构,它包括一个行业分类本体实例和服务池.
行业分类本体实例是一个树状目录结构,表示了当前注册节点中Web 服务的行业分类情况.服务池中存储了
Web 服务的元信息.一个Web 服务可以属于1个或多个行业.如,WS 1(si i ,si j )表示该服务可以属于si i 和si j 两个行
业.为了加快查询速度,可以利用索引技术.索引技术可以参考信息检索中的成熟算法,本文不再深入研究.
Transport Education Accommodation
Hotel Higher education subClassOf subClassOf subClassOf
Elementary education subClassOf
subClassOf
subClassOf Industry classification
subClassOf Accommodation and catering WS n ( si i )......WS 1(si i ,si j )WS n (si j )Classification ontology Web services pools ...WS 2(si j )...si i si j Fig.2 Sample service industry classification ontology 图2 服务行业分类本体例子 Fig.3 Organization of service registry module 图3 服务注册模块组织结构
3 基于蚁群算法的Agent 服务发现
基于真实蚂蚁行为而提出的蚁群算法起初被用于求解TSP 问题(traveling salesman problem)[15].在该算法
中,多个人工蚂蚁被放置在图的多个顶点上.它们模仿真实蚂蚁的行为去寻找最短周游路径.蚁群算法的精髓是
利用在路径上保留的信息素来在蚂蚁之间传递关于路径的信息,而这些信息素又是以前蚂蚁走过后散布下的,
代表了一定的先验知识.在算法中,信息素全局更新的正反馈机制缩小了搜索范围,其隐含的负反馈机制又保持
了搜索范围.受到一些分布式系统中生物群体智能研究[8?12]的启发,本文运用蚁群算法解决分布式服务注册系
统中的服务发现问题.对于实际应用中的每一次Web 服务查询请求,系统产生n 个Search Agent 模拟蚂蚁的行
为去执行查询任务.分布式的服务注册系统中,一般会有不同组织注册的多个功能相同而QoS 不同的服务,服务
请求者需要尽可能地得到所有这些服务的信息,以便选择QoS 最适合的服务.Search Agent 的目标就是在一定
郑啸等:基于Agent和蚁群算法的分布式服务发现1799
的约束条件下尽可能多地找到QoS不同的目标服务信息,并提交给请求者.
3.1 Agent的行为
Search Agent在注册系统P2P网络上漫游并查找目标服务.它包含了目标服务(target service)、生命值(time to live,简称TTL)、跳数(hop count)、禁忌表(tabu)等属性变量.生命值表示Agent可以存活的时间,跳数记录了最近一次发现目标服务后,该Agent经过的注册节点(以下简称节点)数,禁忌表中记录了它经过的节点,防止节点重复访问,也记录它的访问线路.Search Agent具有以下行为(涉及到的算法将在下一节加以介绍):
(1) 漫游.为了在网络上查询到请求的目标服务,Search Agent必须按照一定的路由机制在节点之间移动.网络中的每个节点都维护了一个服务路由表.Search Agent根据服务路由表的信息选择一个邻居节点作为下一跳节点.如图4所示,服务路由表记录了从本地到目标服务行业的信息,它包括目标服务行业Industry、下一跳节点地址Next hop、到Industry的跳数Hop count以及信息素浓度Pheromone这4个字段.例如,图4的路由表中的第1条记录表示如果目标服务属于行业si i,就可以选择h i作为下一个路由节点,从本地到si i所在节点的距离(跳数)为hc i,这条出口上的信息素浓度为ph i.同时,它将经过的节点都登记到自己的禁忌表中,然后更新自己的跳数属性.
(2) 查询服务.它在到达的每一个节点上查询目标服务.节点有关于注册服务的语义描述和QoS属性,所以可以采用语义匹配技术来查询.
(3) 发送信息素更新消息.消息包括服务行业字段和跳数字段.在两种情况下发送更新消息.如果查询成功,就向所有邻居节点的Guide Agent群发更新消息,报告在此节点上可以找到一个目标服务,跳数为1.无论查询成功与否,如果自己的跳数不为0,则都要将跳数封装到一个更新消息中,并发送给当前节点上的Guide Agent.
(4) 生命周期控制.Agent具有生命周期,当它被创建时,就被赋予一个初始生命值,此后在漫游时,生命值根据一定的规则更新.这样就可以控制在网络上传播的Agent的数量,并确保查询请求结束后不会再有其产生的Agent还在网络上不停地漫游.此外,通过调节生命值的初始值,可以增加或减少搜索半径.由于Search Agent在生命周期结束时会自行销毁,这种机制实现了生命周期的自管理,系统不必管理它的整个生命周期.
Industry Next hop Hop count Pheromone
si i h i hc i ph i
si i h j hc j ph j
si j h k hc k ph k
Fig.4 Example of service routing table
图4 服务路由表
Guide Agent主要维护服务路由表,它具有以下行为:
(1) 监听并接收Search Agent的消息.Guide Agent一直监听是否有来自Search Agent或邻居节点上Guide Agent的信息素更新消息.
(2) 服务路由表管理.分析接收到的更新消息,如果路由表中存在此类服务行业,就增加相应表项的信息素浓度,更新相应表项的跳数;如果不存在此类服务行业,则增加一个新的表项.Guide Agent根据收到的信息素更新消息中包含的跳数来替代当前表项中的跳数值.由于注册库中的服务有可能发生变化,路由表需要定时更新并减少信息素.那些长时间没有得到增加的信息素最终会挥发完,表示其相应的路径上可能已经不存在相应的服务注册信息,或者没有查找此类服务的需求.如果某个表项的信息素浓度为0,就删除该表项.
(3) 扩散信息素更新消息.当所在的节点加入注册系统后,或者有新的服务注册成功后,向所有邻居节点扩散信息素更新消息.消息中的跳数设置为1.
3.2 Agent服务发现机制
下面从Search Agent的路由机制、信息素的产生和更新以及Search Agent的跳数更新、生命周期控制这
1800 Journal of Software 软件学报 V ol.21, No.8, August 2010
4个方面进行讨论.不失一般性,假设Search Agent 要查询的目标服务只属于1个服务行业.
3.2.1 Search Agent 的路由机制
Search Agent 查询当前节点的服务路由表.首先,根据服务行业分类本体确定目标服务的行业都和表中的
哪些行业语义相似;然后再根据匹配的结果,从多个符合语义相似条件的路由中选择出适当的路由.
(1) 服务行业的语义匹配
本体概念间的语义相似度计算是服务行业语义匹配的基础.目前提出了很多种概念间语义相似度计算方
法,但本文中的服务行业分类本体是一个树型结构,所以采用基于树的计算方法.这类方法利用两个概念在概念
树中的最短路径、概念在概念树中的层高以及所在层高的节点密度等作为度量指标.文献[16]提出的两个概念
C 1,C 2间语义相似度的计算公式为 12e e (,)e e e h h
al h h
Sim C C ββββ????=?+ (1) 其中,l 表示两个概念间的最短路径的长度,h 表示两个概念在树中最近的相同父辈概念在树中的高度,参数α,
β≥0是调节因子.本文采用该计算方法作为两个行业本体概念间语义相似度的计算方法.给定一个语义相似度
阈值ξ∈(0,1),在当前节点i 上的服务路由表RT i 中的集合I 就是筛选出的与目标服务行业si k 语义相似的行业集
合.I 可以表示为
{|(,)()}k Industry i I si Sim si si si RT ξπ=>∧∈ (2) 其中,πIndustry (RT i )表示RT i 在Industry 上的投影.
(2) 路由选择
在服务路由表中选择路由时,会出现两种情况:一是要查询的目标服务所属行业在语义上不与当前服务路
由表中任何一个目标服务行业匹配,这时Search Agent 就在所有邻居节点中随机选择一个;二是找到1个或多个
目标服务行业可以匹配,这时Search Agent 要根据语义相似度以及表项中相应的信息素值和跳数来确定选择哪
一个邻居.下面讨论第2种情况下的路由选择机制.
信息素是用蚁群算法思想求解问题的核心因素,它代表了一定的先验知识,其大小代表了在相应的路径上
查找成功次数的多少.本文算法还引入两个启发因子,即语义相似度和跳数.语义相似度表示了路由表中的目标
服务行业与Search Agent 的目标服务所属行业的相似程度,跳数代表了与目标服务行业的距离.Search Agent 漫
游到语义相似度大的行业上查询的准确率可能会提高,漫游到信息素大的邻居节点后的查找成功率可能要高
一些,而选择跳数小的可能响应时间较短.因此,要综合考虑这3个参数.
假设当前节点为i ,Search Agent k 在第2种情况下以如下概率(公式(3))选择邻居节点j :
(,)(1/(,))(,),(,)(1/(,))(,)(,)0,k j k u k u N ph i j hops i j Sim si I j N ph i u hops i u Sim si I p i j j N λλ∈?∈??=?????∑ (3) ,{|(,)()}().Industry Nexthop i N n si n RT si I Tabu k π=∈∧∈?
其中,ph (i ,j )表示节点i 到节点j 上的信息素值;hops (i ,j )表示以节点j 为下一跳时,到达目标服务行业的跳数;λ>0
是调节因子,调节信息素和跳数在路由选择中的比重;RT i 表示节点i 上的服务路由表;I x 表示RT i 中下一跳节点x
所对应的行业;si k 表示Search Agent k 要查询的目标服务的行业;Sim (si k ,I x )为语义相似度(可用公式(1)计算).
πIndustry ,Nexthop (RT i )表示RT i 在(Industry ,Nexthop )上的投影,I 的定义如公式(2).Tabu (k )是Search Agent k 的禁忌表.
在服务路由表中,可能会出现多个不同行业对应同一个下一跳节点的情况.因此,为了确保在集合N 中不会
删除重复的节点,可以首先对其进行预处理.方法是对于m 个重复的节点n ,用m 个不同的记号n 1,n 2,…,n m 标记.
3.2.2 信息素的产生和更新
信息素在Search Agent 发现服务的过程中发挥了重要的作用,它引导Search Agent 的路由方向.因此,如何
产生和更新信息素是影响本文算法性能好坏的关键.在以下几种情况下会产生或更新信息素:
郑啸 等:基于Agent 和蚁群算法的分布式服务发现
1801
(1) 已经找到目标服务的Search Agent 在所经过的路径上会留下信息素.它产生的新的信息素会累加到原
来该路径已有的信息素上.设Search Agent 从节点n 进入本地节点i ,ph (i ,n )表示从i 到邻居节点n 的路
径上的信息素值,则有
ph (i ,n )=α?ph (i ,n )+(1?α)Δp 1 (4)
其中,α∈(0,1),Δp 1为常数. (2) 当在节点n 上找到目标服务时,它还会向节点n 的所有邻居节点扩散信息素.邻居节点上的Guide Agent
在收到信息素更新消息后,会在自己服务路由表的相应表项上更新信息素.即
ph (m ,n )=β?ph (m ,n )+(1?β)Δp 2,m ∈J (n ) (5)
其中,β∈(0,1),Δp 2为常数,J (n )是节点n 的邻居集合.
(3) 对于服务路由表上的每一项,都会定期作如下更新:
ph (i ,n )=ρ?ph (i ,n ) (6)
其中,ρ∈(0,1)是挥发系数.这样,如果某个邻居长时间始终没有被访问,则它的信息素将会接近为0.这样
的节点上可能注册的服务较少,或者已经退出了网络. (4) 当有新的节点加入网络后,它会向其所有邻居发送信息素更新消息.按照公式(5)的规则来更新邻居的
服务路由表.
(5) 当某个节点上有新的服务注册时,它会向其所有邻居发送信息素更新消息.按照公式(5)的规则来更新
邻居的服务路由表.
3.2.3 Search Agent 跳数的更新
Search Agent 跳数值初始为0,表示目前还没有发现目标服务.如果第1次发现,就将跳数设置为1.此后,如果
在沿途节点上继续发现目标服务,就重置为1;否则就做加1操作.因此,Search Agent 在查找服务的同时,还可以
记录最近一次发现到的服务距离当前位置的跳数,这个跳数将被包含在信息素更新消息中,用于更新服务路由
表.Search Agent k 在节点i 上时,其跳数HC k 的更新规则为
0, 0()1, ()
1, 0()k k k k k
k k HC si C i HC si C i HC HC si C i =∧???=∈??+>∧?? (7) 其中,si k 表示Search Agent k 要查找的服务所属的行业,C (i )表示节点i 上的服务集合.
3.2.4 生命周期控制
本算法使用TTL 控制Search Agent 的生命周期.在Search Agent 产生时,它的TTL 会被设置一个初值.在经
过的每个节点,TTL 值都会被更新.如果在当前节点上没有找到目标服务,TTL 会减少;如果找到了,则不对TTL
值处理.这样可以使这个Agent 再去查找更多的节点.如果当前节点的所有邻居节点都在Agent 的禁忌表中,则
它的TTL 值被强制为0.TTL 值为0的Agent 就不再漫游,并被销毁.Search Agent k 在节点i 上时,其生命值TTL k
的更新规则为
1, (), ()
0, ()()k k k k k TTL si C i TTL TTL si C i J i Tabu k ????=∈????
(8) 其中,si k 和C (i )同公式(7),J (i )是节点i 的邻居集合.
基于以上的讨论,下面分别给出服务路由表更新算法和路由选择算法的伪代码.
算法1. 服务路由表更新.Guide Agent 在收到信息素更新消息后,在上面提到的情况(2)、情况(4)、情况(5)
这3种情况下运用本算法.情况(1)、情况(3)这两种情况下的服务路由表更新算法与此类似.
1: Input : A service routing table n 1.SrvRoutingTab of a local node n 1, a neighbor node n 2,
a pheromone update message msg , a pheromone increment ph , a const beta ;
2: IF (msg .Industry ,n 2) in n 1.SrvRoutingTab THEN
1802 Journal of Software软件学报 V ol.21, No.8, August 2010
3: n1.SrvRoutingTab[(msg.Industry,n2)].ph=beta×n1.SrvRoutingTab[(msg.Industry,n2)].ph+(1?beta)×ph;
4: n1.SrvRoutingTab[(msg.Industry,n2)].hc=msg.hc;
5: ELSE
6: Add (msg.Industry,n2,msg.hc,ph) to n1.SrvRoutingTab;
算法2.路由选择算法.Search Agent在每个节点执行此算法,执行查询任务和选择下一个访问节点的任务.
1: Input: A Seach Agent SA, a target service WS, a local node node, pheromone increments ph1 and ph2;
2: SendUpdatePheromoneMessage to node with SA.HopCount and ph1;
3: SA.UpdateHopCount;
4: SA.Tabu.Add(node);
5: IF Agents having the same task had arrived THEN
6: SA.TTL??;
7: ELSE
8: SA.Query(WS);
9: IF (NoFound) THEN
10: SA.TTL??;
11: ELSE
12: FOREACH node i IN node.neighbour
13: SendUpdatePheromoneMessage to node i with msg.hc=1 and ph2;
14: IF All node.neighbour in SA.Tabu THEN
15: SA.TTL=0;
16: ELSE
17: SA.Nexthop=SelectingRoute(node);
4 实验分析
下面用仿真实验来评估算法的性能.假设在注册节点上可以准确地找到所有目标服务,实验仅重点考察算法在系统中查找到目标服务所在注册节点的性能.
4.1 实验环境
仿真实验工具为Repast 3(recursive porous agent simulation toolkit)[17].这是一个可以模拟大规模系统的开源的多Agent仿真平台.仿真程序用C#开发,运行的机器为Pentium 4 3.0GHz CPU,2G内存.仿真软件模拟了网络结构符合Power-law规则[18]的非结构化P2P服务注册系统,每个注册节点可以有最多20种类型的服务行业,每个行业最多有50种类型的服务,每个注册中心随机产生200个注册服务,服务路由表的长度为256.基于蚁群算法的机制都包含大量的调节参数.然而到目前为止,这些参数的取值还没有科学的严格的理论指导[19,20],需要经过多次实验确定优化的参数.根据文献[16,20]中的建议和反复的实验,公式(1)的参数设置为α=0.2,β=0.6.本文算法的参数设置为α=0.9,β=0.85,ρ=0.95,Δp1=0.25,Δp2=0.35,ξ=0.5.λ参数决定了信息素和跳数哪一个对路由选择的影响大一些.在拓扑结构和注册服务信息基本不变的静态环境下,跳数可以比较真实地反映服务信息的注册位置;而在动态环境下,信息素的更新机制发挥了适应环境变化的作用,所以在静态实验环境下设置λ=0.5,放大跳数值的影响,动态实验环境下设置λ=2,缩小其值.仿真实验基于离散时间模型,所有事件在确定的离散时间步上执行.这样的时间步称为一个Tick.以所有Search Agent产生直到它们生命全部终止为一个查找轮次(round).
为了分析算法的性能,我们分别做了3组实验.第1组实验评估本文算法的性能以及可扩展性和适应性,第2组实验将本文算法与另两种经典的P2P资源发现算法进行比较,第3组实验讨论本文算法的参数对性能的影响.本文定义并使用下列度量指标:
郑啸 等:基于Agent 和蚁群算法的分布式服务发现
1803
图较15索慢i 如果Search Agent 在某个节点上找到一个目标服务,它的TTL i 不变化,这等于生命值增加了.因此,设ΔTTL i 是第i 个Search Agent 的生命增量,则有
11(Δ)Δ.n n
q i i i i L InitialTTL TTL n InitialTTL TTL ===+=×+∑∑
生命增量ΔTTL i 是在查询过程中动态变化的,与Search Agent i 的查找过程及生命周期控制策略(公式(8))有
如上所述,在网络规模增大时,为了达到一定的召回率,必须增加Search Agent 的数量和初始生命值.根据定理1,这势必增加查询流量负载.图8表明在不同系统规模下,为了达到80%的召回率,查询流量负载随系统规模的增加呈线性增加的趋势.通过理论分析和仿真实验可知,L q 的大小是可控的,可以根据定理1计算其最大值,而且为了达到一定的召回率,L q 必须增加,但其大小是随网络的规模线性增加.
2200
2000
1800
10 15 20 25 30 35 40 45 50 55 Number of SAs R e c a l l (%706560555045403530Initial TTL of SA =20 Initial TTL of SA =25 Initial TTL of SA =30 Initial TTL of SA =35 1000 3000 5000 7000 9000
Number of registry peers R e c a l l (%60
50
40
30
20
10
0Fig.6 Recall vs. the number of registry peers 图6 不同数量注册节点时的召回率 Fig.7 Recall vs. the number of SAs 图7 不同数量Search Agent 时的召回率
郑啸 等:基于Agent 和蚁群算法的分布式服务发现 1805 服务数、Search Agent 数量的变化情况,图9(b)显示此过程中召回率的变化.可见,注册节点增加后,第7轮查找的召回率立刻下降到85%.这是因为注册节点增加后,不但可能会增加目标服务数量,而且网络拓扑结构也会有 Fig.9 Experiments in a dynamic environment
图9 动态环境下的实验
4.3 与经典算法的比较
Gnutella [21]和Random Walks [22]是非结构化P2P 网络中两种经典的资源发现算法,也常被用于P2P 服务发现机制.我们在提出的服务注册系统中实现了这两种算法指导的Search Agent 服务查找机制,以便与本文算法作对比.图10是在不同系统规模下,3种算法查询流量负载的比较.图11是3种算法查找性价比的比较.由于Gnutella 和Random Walks 在每个节点都要生成新的Search Agent,Gnutella 以类似泛洪(flooding)的方式产生, k -Random Walks 在每个注册中心都产生k ?1个新的Search Agent,所以在大规模的环境下,为了达到较高的召回率会产生大量的Search Agent,因而算法产生的查询流量就很高,而查找性价比就很低.而本文算法在整个查找0 200 400 600 800 1000 1200
Time (tick)
N 40
20
00 200 400 600 800 1000 1200Time (tick) 40200(a) Process of multi-round search
(a) 多轮查找过程 (b) Trend of recall (b) 召回率变化趋势
1806 Journal of Software软件学报 V ol.21, No.8, August 2010
0 0.2 0.4 0.6 0.8 1.0
Visited-Total registries ratio
Fig.12 Comparison between three algorithms in recall
图12 3种算法召回率的比较
4.4 算法参数对性能的影响
这组实验考察本文算法的参数设置对其性能的影响.在本文算法中,语义相似度阈值ξ、调节因子λ和挥发系数ρ对于算法的召回率、查找时间的影响较大.因此,本节重点讨论这3个参数.
图13是语义相似度阈值ξ和召回率之间的关系,不同系统规模下的召回率曲线总体趋势相似(图例中的n 表示注册节点数).当ξ=0.5时,召回率达到最高;当ξ<0.5时,召回率有所下降,但还是比较高;但是当ξ>0.5时,召回率呈下降趋势.这是因为当ξ的值减小时,集合I(见公式(2))中的元素增多,即服务路由表中可以与目标服务行业语义匹配的服务行业增多.这会扩大Search Agent的搜索范围,一些实际上与目标服务行业语义相似度很小的服务行业也有机会被选择到.但同时,由于公式(3)中语义相似度因子的作用,相似度较小的服务行业被选择的概率也较小,召回率的减小变化并不十分明显,还维持在较高水平.当ξ较大时,可供选择的服务行业较少,可能会筛选掉一些与目标服务行业语义相似的服务行业,因此会减少召回率.实验结果表明,当ξ≈0.5时会达到较好的
郑啸 等:基于Agent 和蚁群算法的分布式服务发现
1807
Fig.14 Relation between λ and search time
图14 λ和查找时间之间的关系
0 0.5 1.0 1.5 2.0λ T i m e (t i c k ) 120
110
100
90
80
70
60
50
40n =3000 0 0.5 1.0 1.5 2.0 λ T i m e (t i c k ) 210180150120906030
n =2000 n =3000 (a) In a static environment
(a) 静态环境下 (b) In a dynamic environment (b) 动态环境下
e c a l l (%) 80
6040
100
ρ=0.90ρ=0.95
1808 Journal of Software软件学报 V ol.21, No.8, August 2010
References:
[1] Verma K, Sivashanmugam K, Sheth A, Patil A, Oundhakar S, Miller J. METEOR-S WSDI: A scalable P2P infrastructure of
registries for semantic publication and discovery of Web services. Journal of Information Technology and Management, 2005,6(1): 17?39. [doi: 10.1007/s10799-004-7773-4]
[2] Chen DW, Xu B, Cai YR, Li JZ. A P2P based web service discovery mechanism with bounding deployment and publication.
Chinese Journal of Computers, 2005,28(4):615?626 (in Chinese with English abstract).
[3] Chen CW, Gan PS, Yang CH. A service discovery mechanism with load balance issue in decentralized peer-to-peer network. In:
Barolli L, ed. Proc. of the 11th Int’l Conf. on Parallel and Distributed Systems (ICPADS 2005). Washington: IEEE Computer Society Press, 2005. 592?598.
[4] Liu ZZ, Wang HM, Zhou B. A two layered P2P model for semantic service discovery. Journal of Software, 2007,18(8):1922?1932
(in Chinese with English abstract). https://www.doczj.com/doc/0518857805.html,/1000-9825/18/1922.htm [doi:10.1360/jos181922]
[5] Guo DK, Ren Y, Chen HH, Xue QW, Luo XS. A QoS-guaranteed and distributed model for Web service discovery. Journal of
Software, 2006,17(11):2324?2334 (in Chinese with English abstract). https://www.doczj.com/doc/0518857805.html,/1000-9825/17/2324.htm [doi:10.1360/ jos172324]
[6] Clement L, Hately A, Riegen CV, Rogers T. Universal description discovery & integration (UDDI) 3.0.2. 2004.
https://www.doczj.com/doc/0518857805.html,/pubs/uddi_v3.htm
[7] Du ZX, Huai JP. Research and implementation of an active distributed Web service registry. Journal of Software, 2006,17(3):
454?462 (in Chinese with English abstract). https://www.doczj.com/doc/0518857805.html,/1000-9825/17/454.htm [doi:10.1360/jos170454]
[8] Di Caro G, Dorigo M. Antnet: Distributed stigmergetic control for communications networks. Journal of Artificial Intelligence
Research, 1998,9:317?365.
[9] Liu JM, Jin XL, Wang YS. Agent-Based load balancing on homogenous minigrids: Macroscopic modeling and characterization.
IEEE Trans. on Parallel and Distributed Systems, 2005,16(7):586?598. [doi: 10.1109/TPDS.2005.76]
[10] Xu H, Wu SQ. A distributed QoS routing based on ant algorithm for LEO satellite network. Chinese Journal of Computers, 2007,
30(3):361?367 (in Chinese with English abstract).
[11] Du RH, Yao G, Wu QY. Application of an ant colony algorithm in migration of mobile agent. Journal of Computer Research and
Development, 2007,22(2):282?287 (in Chinese with English abstract).
[12] Babaoglu O, Canright G, Deutsch A, Di Caro GA, Ducatelle F, Gambardella LM, Ganguly N, Jelasity M, Montemanni R,
Montresor A, Urnes T. Design patterns from biology for distributed computing. ACM Trans. on Autonomous and Adaptive Systems, 2006,1(1):26?66. [doi: 10.1145/1152934.1152937]
[13] Babao?lu ?, Meling H, Montresor A. Anthill: A framework for the development of agent-based peer-to-peer systems. In:
Rodrigues L, Raynal M, Chen W, eds. Proc. of the 22nd Int’l Conf. on Distributed Computing Systems (ICDCS 2002). Washington: IEEE Computer Society Press, 2002. 15?22.
[14] General Administration of Quality Supervision, Inspection and Quarantine of P.R.C. Industrial Classification for National
Economic Activities. GB/T 4754-2002, Beijing: Standards Press of China, 2007 (in Chinese).
[15] Dorigo M, Gambardella LM. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans.
on Evolutionary Computation, 1997,1(1):53?66. [doi: 10.1109/4235.585892]
[16] Li YH, Bandar ZA, McLean D. An approach for measuring semantic similarity between words using multiple information sources.
IEEE Trans. on Knowledge and Data Engineering, 2003,15(4):871?882. [doi: 10.1109/TKDE.2003.1209005]
[17] North MJ, Collier NT, Vos JR. Experiences creating three implementations of the repast agent modeling toolkit. ACM Trans. on
Modeling and Computer Simulation, 2006,16(1):1?25. [doi: 10.1145/1122012.1122013]
[18] Adamic LA, Lukose RM, Puniyani AR, Huberman BA. Search in power law networks. Physical Review E, 2001,64(4):
46135?46143.
[19] Ridge E, Curry E. A roadmap of nature-inspired systems research and development. Multiagent and Grid Systems, 2007,3(1):3?8.
[20] Parunak HVD, Brueckner SA, Matthews R, Sauter J. Pheromone learning for self-organizing agents. IEEE Trans. on Systems, Man,
and Cybernetics—Part A: Systems and Humans, 2005,35(3):316?326. [doi: 10.1109/TSMCA.2005.846408]
[21] Clip 2. The Gnutella protocol specification. v0.4. 2000. https://www.doczj.com/doc/0518857805.html,/GnutellaProtocol04.pdf
郑啸等:基于Agent和蚁群算法的分布式服务发现1809
[22] Lü Q, Cao P, Cohen E, Li K, Shenker S. Search and replication in unstructured peer-to-peer networks. In: Gupta M, ed. Proc. of the
16th ACM Int’l Conf. on Supercomputing (ICS 2002). New York: ACM Press, 2002. 84?95.
附中文参考文献:
[2] 陈德伟,许斌,蔡月茹,李涓子.服务部署与发布绑定的基于P2P网络的Web服务发现机制.计算机学报,2005,28(4):615?626.
[4] 刘志忠,王怀民,周斌.一种双层P2P结构的语义服务发现模型.软件学报,2007,18(8):1922?1932. https://www.doczj.com/doc/0518857805.html,/1000-
9825/18/1922.htm [doi:10.1360/jos181922]
[5] 郭得科,任彦,陈洪辉,薛群威,罗雪山.一种QoS有保障的Web服务分布式发现模型.软件学报,2006,17(11):2324?2334.
https://www.doczj.com/doc/0518857805.html,/1000-9825/17/2324.htm [doi:10.1360/jos172324]
[7] 杜宗霞,怀进鹏.主动分布式Web服务注册机制研究与实现.软件学报,2006,17(3):454?462. https://www.doczj.com/doc/0518857805.html,/1000-9825/17/
454.htm [doi:10.1360/jos170454]
[10] 许辉,吴诗其.LEO卫星网络中基于蚂蚁算法的分布式QoS路由.计算机学报,2007,30(3):361?367.
[11] 杜荣华,姚刚,吴泉源.蚁群算法在移动Agent迁移中的应用研究.计算机研究与发展,2007,44(2):282?287.
[14] 中华人民共和国国家质量监督检验检疫总局.国民经济行业分类.GB/T 4754-2002,北京:中国标准出版社,2007.
郑啸(1975－),男,福建莆田人,博士生,副教授,CCF会员,主要研究领域为网络与分布式系统,服务计算.
宋爱波(1970－),男,博士,副教授,CCF会员,主要研究领域为网格计算,海量数据处理,Petri网理论与应用
.
罗军舟(1960－),男,博士,教授,博士生导
师,CCF高级会员,主要研究领域为下一代
网络体系结构,协议工程,网络安全与管
理,网格计算.
分布式设计与开发（二）------几种必须了解的分布式算法 分布式设计与开发中有些疑难问题必须借助一些算法才能解决，比如分布式环境一致性问题，感觉以下分布式算法是必须了解的（随着学习深入有待添加）： ?Paxos算法 ?一致性Hash算法 Paxos算法 1）问题描述 分布式中有这么一个疑难问题，客户端向一个分布式集群的服务端发出一系列更新数据的消息，由于分布式集群中的各个服务端节点是互为同步数据的，所以运行完客户端这系列消息指令后各服务端节点的数据应该是一致的，但由于网络或其他原因，各个服务端节点接收到消息的序列可能不一致，最后导致各节点的数据不一致。举一个实例来说明这个问题，下面是客户端与服务端的结构图： 当client1、client2、client3分别发出消息指令A、B、C时，Server1~4由于网络问题，接收到的消息序列就可能各不相同，这样就可能由于消息序列的不同导致Server1~4上的数据不一致。对于这么一个问题，在分布式环境中很难通过像单机里处理同步问题那么简单，而Paxos算法就是一种处理类似于以上数据不一致问题的方案。 2）算法本身 算法本身我就不进行完整的描述和推导，网上有大量的资料做了这个事情，但我学习以后感觉莱斯利·兰伯特（Leslie Lamport，paxos算法的奠基人，此人现在在微软研究院）的Paxos Made Simple是学习paxos 最好的文档，它并没有像大多数算法文档那样搞一堆公式和数学符号在那里吓唬人，而是用人类语言让你搞清楚Paxos要解决什么问题，是如何解决的。这里也借机抨击一下那些学院派的研究者，要想让别人认可你的成果，首先要学会怎样让大多数人乐于阅读你的成果，而这个描述Paxos算法的文档就是我们学习的榜样。 言归正传，透过Paxos算法的各个步骤和约束，其实它就是一个分布式的选举算法，其目的就是要在一堆消息中通过选举，使得消息的接收者或者执行者能达成一致，按照一致的消息顺序来执行。其实，以最简单的想法来看，为了达到大伙执行相同序列的指令，完全可以通过串行来做，比如在分布式环境前加上一个FIFO 队列来接收所有指令，然后所有服务节点按照队列里的顺序来执行。这个方法当然可以解决一致性问题，但
计算几何基础知识整理 一、序言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、本基础目录 本文整理的计算几何基本概念和常用算法包括如下内容： 1. 矢量的概念 2. 矢量加减法 3. 矢量叉积 4. 折线段的拐向判断 5. 判断点是否在线段上 6. 判断两线段是否相交 7. 判断线段和直线是否相交 8. 判断矩形是否包含点 9. 判断线段、折线、多边形是否在矩形中 10. 判断矩形是否在矩形中 11. 判断圆是否在矩形中 12. 判断点是否在多边形中 13. 判断线段是否在多边形内 14. 判断折线是否在多边形内 15. 判断多边形是否在多边形内 16. 判断矩形是否在多边形内 17. 判断圆是否在多边形内 18. 判断点是否在圆内 19. 判断线段、折线、矩形、多边形是否在圆内 20. 判断圆是否在圆内 21. 计算点到线段的最近点 22. 计算点到折线、矩形、多边形的最近点 23. 计算点到圆的最近距离及交点坐标 24. 计算两条共线的线段的交点 25. 计算线段或直线与线段的交点 26. 求线段或直线与折线、矩形、多边形的交点 27. 求线段或直线与圆的交点 28. 凸包的概念 29. 凸包的求法 三、算法介绍 1.矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed
小 型 微 型 计 算 机 系 统 Journal of Chinese Computer Systems
2008 年 月 第 期 Vol.28 No. 2008
?
图论在网络拓扑发现算法中的应用
路连兵 1+，胡吉明 2，姜 岩 1
1，2
，2
(河海大学 计算机及信息工程学院,江苏 南京
210098)
E-mail ：famioo@https://www.doczj.com/doc/0518857805.html,
摘
要：网络拓扑发现技术已经广泛地应用在各种项目软件中。然而，随着网络结构复杂度升级，这给拓扑发现带来了
挑战。所以我们越来越需要一种高效，准确的网络拓扑算法自动发现网络拓扑结构。目前的拓扑算法主要集中在：(1)路 由层的发现。这个层面的发现算法在技术上比较简单，只需要寻找路由与路由之间，或路由端口与子网之间的连接关系， 利用路由器的自身特性，很容易实现。(2)链路层的发现。直到目前为止，已有的厂商工具很难准确发现网络拓扑，已发 表的理论文献知识也只是理论上阐述，实际应用难度比较大。本论文，提出一种基于图论的骨架树数据存储结构算法，可 以高效推断网络的拓扑关系。 关键词：骨架树;子网;地址转发表;图论；信任节点
Topology Discovery in Networks Based on Graph Theory*
LU Lian-Bing1+, HU Ji-Ming2，Jiang Yan1,2
1,2
(School of Computer Science and Information, Hohai University, Nanjing Jiangsu 210098, China)
Abstract: Topology discovery systems are starting to be introduced in the form of easily and widely deployed software. However, Today's IP network is complex and dynamic. Keeping track of topology information efficiently is a difficult task. So, we need effective algorithms for automatically discovering physical network topology. Earlier work has typically focused on: (1) Layer-3 (network layer) topology, which can only router-to-router interconnections and router interface-to-subnet relationships. This work is relatively easy and has lots of systems can do it. (2)Layer-2(link layer), till now, no tools can discovery the network topology exactly because of bad algorithm. In this paper, Skeleton-tree based on Graph theory is proposed to infer the connections between network nodes. Key words: Skeleton-tree; subnets; Address Forwarding Table; Graph Theory；Trust Node
作者简介: 路连兵(1979－),男,江苏泗洪人,硕士。 主要研究网络自拓扑,软件项目管理,Perl 研究;胡吉明(1967－),男,硕导,副教授,主要研究 领域为计算机应用技术,网络安全,数据挖掘，Z 语言; 姜岩(1979-),男,硕士研究生,主要研究方向,网络应用,中间件
２００７年第２４卷第１０期微电子学与计算机 １引言 分布式数据库系统在系统结构上的真正含义是指物理上分布、逻辑上集中的分布式数据库结构。数据在物理上分布后，由系统统一管理，用户看到的似乎不是一个分布式数据库，而是一个数据模式为全局数据模式的集中式数据库［１￣５］。 分布式数据库系统包括两个重要组成部分：分布式数据库和分布式数据库管理系统。分布式数据库系统具有位置透明性和复制透明性，使用户看到的系统如同一个集中式系统。分布式数据库系统分为三类：同构同质型ＤＤＢＳ、同构异质型ＤＤＢＳ和异构ＤＤＢＳ。同构同质型ＤＤＢＳ是指各个场地都采用同一类型的数据模型，并且是同一型号数据库管理系统；同构异质型ＤＤＢＳ是指各个场地都采用同一类型的数据模型，但是数据库管理系统是不同型号的；异构型ＤＤＢＳ是指各个场地的数据模型是不同的类型。 分布式结构是相对于集中式结构而言的。从数据处理的角度来说，典型的集中式结构是数据集中存放和处理，用户通过远程终端或通过网络连接来共享集中存放的数据。分布式结构则是将数据及其处理分散在不同场地，各场地各自管理一部分数据，同时又通过网络系统相互连接。各场地的用户除可以访问和处理本地数据外，也可以访问和处理别的场地的数据。分布式数据库是典型的分布式结构。它包括对数据的分布存储和对事务的分布处理。设计一个分布式数据库系统会遇到许多集中式数据库设计中所没有的问题，一致性是其中必须认真对待和解决的主要问题。 ２ＤＤＢＳ的体系结构 ２．１综合型体系结构 综合型体系结构是指在综合权衡用户需求之后，设计出分布的数据库，然后再设计出一个完整的ＤＢＭＳ，把ＤＢＭＳ的功能按照一定的决策分散配置在一个分布的环境中。每个结点的ＤＢＭＳ均熟知整个网络的情况，也了解其它结点的情况。从整体上，各结点组成一个完整的系统，它们之间是靠进程通讯的手段来维持互访连接，如图１所示。２．２联合型体系结构 联合型体系结构是指每个结点上先有ＤＢＭＳ，以此为基础，再建立分布式环境以实现互访连接。若各个结点的局部ＤＢＭＳ支持同一种数据模式和 分布式数据库系统及其一致性方法研究 刘萍芬，马瑞芳，王军 （西安交通大学电信学院，陕西西安７１００４９） 摘要：分布式数据库系统是数据库领域中的一个主要研究方向，数据一致性维护是分布式数据库系统中的一个非常关键的技术问题。在分析分布式数据库系统体系结构的基础上，讨论了两种一致性方法：两阶段提交和复制服务器，并提出一种具有复制服务器的分布式数据库系统的结构框架，它具有有效性和实用性。 关键词：分布式数据库系统；一致性；两阶段提交；复制服务器 中图分类号：ＴＰ３１文献标识码：Ａ文章编号：１０００－７１８０（２００７）１０－０１３７－０３ ＲｅｓｅａｒｃｈｏｆＤｉｓｔｒｉｂｕｔｅｄＤａｔａｂａｓｅＳｙｓｔｅｍａｎｄＤａｔａＣｏｎｓｉｓｔｅｎｃｙ ＬＩＵＰｉｎｇ－ｆｅｎ，ＭＡＲｕｉ－ｆａｎｇ，ＷＡＮＧＪｕｎ （ＣｏｌｌｅｇｅｏｆＥｌｅｃｔｒｏｎｉｃｓａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｔｉｎｇ，Ｘｉ′ａｎＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｘｉ′ａｎ７１００４９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍｉｓａｍａｉｎｒｅｓｅａｒｃｈｄｉｒｅｃｔｉｏｎｉｎｔｈｅｄａｔａｂａｓｅｆｉｅｌｄ．Ｍａｉｎｔａｉｎｉｎｇｔｈｅｄａｔａｃｏｎｓｉｓ－ｔｅｎｃｙｉｓａｃｒｉｔｉｃａｌｔｅｃｈｎｉｃａｌｐｒｏｂｌｅｍｉｎｔｈｅｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍ．Ｔｈｉｓｐａｐｅｒｄｉｓｃｕｓｓｅｓｔｗｏｍｅｔｈｏｄｓｏｆｍａｉｎｔａｉｎｉｎｇｄａｔａｃｏｎｓｉｓｔｅｎｃｙｂａｓｅｄｏｎａｎａｌｙｚｉｎｇｔｈｅｓｔｒｕｃｔｕｒｅｏｆｔｈｅｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍ，ｗｈｉｃｈａｒｅ２ＰＣａｎｄｒｅｐｌｉｃａｔｉｏｎｓｅｒｖ－ｅｒ．Ｔｈｅｎｔｈｅｐａｐｅｒｐｕｔｓｆｏｒｗａｒｄａｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｆｒａｍｅｗｏｒｋｗｈｉｃｈｈａｖｅｒｅｐｌｉｃａｔｉｏｎｓｅｒｖｅｒｓｔｒｕｃｔｕｒｅ．Ａｎｄｉｔｉｓｅｆｆｅｃ－ｔｉｖｅａｎｄａｐｐｌｉｅｄ． Ｋｅｙｗｏｒｄｓ：ｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍ；ｄａｔａｃｏｎｓｉｓｔｅｎｃｙ；２ＰＣ；ｒｅｐｌｉｃａｔｉｏｎｓｅｒｖｅｒ 收稿日期：２００６－１０－２７ １３７
第1章分布式计算概述 一、选择题 1，CD 2，ABC 3，ABCD 4，ACD 二、简答题 1，参考1.1.1和节 2，参考1.1.2节 3，分布式计算的核心技术是进程间通信，参考1.3.2节 4，单播和组播 5，超时和多线程 三、实验题 1.进程A在进程B发送receive前发起send操作 进程A进程B 发出非阻塞send操 作，进程A继续运行 发出阻塞receive操 作，进程B被阻塞进程B在进程A发起send前发出receive操作
发出非阻塞send 操作，进程A 继续运行 发出阻塞receive 操作，进程B 被阻塞 收到进程A 发送的数据，进程B 被唤醒 2. 进程A 在进程B 发送receive 前发起send 操作 进程A 进程B 发出阻塞send 操作， 进程A 被阻塞 发出阻塞receive 操作，进程B 被阻塞 进程B 在进程A 发起send 前发出receive 操作
发出阻塞send操作，进程A被阻塞 发出阻塞receive操作，进程B 被阻塞 收到进程A发送的数据，进程B 被唤醒 收到进程B返回的数 据，进程A被唤醒 3.1).在提供阻塞send操作和阻塞receive操作的通信系统中在提供非阻塞send操作和阻塞receive操作的通信系统中2)．P1，P2，P3进程间通信的顺序状态图 m1 m1 m2 m2 第2章分布式计算范型概述 1.消息传递，客户-服务器，P2P，分布式对象，网络服务，移动代理等 2.分布式应用最广泛最流行的范型是客户-服务器范型，参考节
3.分布式应用最基本的范型是消息传递模型，参考节 4.参考节，P2P应用有很多，例如Napster，迅雷，PPS网络电视等 5.参考节 6.参考节 7.略 8.消息传递模式是最基本的分布式计算范型，适用于大多数应用；客户-服务器范型是最 流行的分布式计算范型，应用最为广泛；P2P范型又称为对等结构范型，使得网络以最有效率的方式运行，适用于各参与者地位平等的网络；分布式对象范型，是抽象化的远程调用，适用于复杂的分布式计算应用等。 9.略 10.中间件又称为代理，中间件为参与对象提供内容抽象，隐藏对象引用，起到中介作用。 11.略 第3章 Socket编程与客户服务器应用开发 一、填空题 1.数据包socket，流式socket 2.无连接方式，面向连接方式 3.数据层，业务层，应用层 4.迭代服务器和并发服务器 5.有状态服务器和无状态服务器 二、简答题 1.API：Application Programming Interface,应用程序编程接口，是一些预先定义 的函数，目的是提供应用程序与开发人员基于某软件或硬件得以访问一组例程的能 力，而又无需访问源码，或理解内部工作机制的细节 Socket API：套接字应用程序编程接口，适用于进程间通信的套接字应用程序编程 接口
POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学:
多Agent系统理论概述 摘要：Agent在AI(AI:Artificial Intelligence)研究领域已经成为热点，Agent 技术提供了一种新的计算和问题求解规范。本文简要的讨论Agent、多Agent系统。 关键词：多Agent系统概述 1Agent概述 1.1Agent的基本概念 Agent的概念最早出现在20世纪70年代的人工智能中，80年代后期，被译为“代”理，“智能体”或“智能主体”。这些概念在许多领域被引用，不同的研究领域和内容，给出了许多不尽相同的定义。目前为止还没有一个对Agent统一的定义，但多数研究者接受wooldridge和Jelinings所提出的Agent定义，即Agent 是一个具有自治性、社会能力和反应特性的计算机软、硬件系统，它具有自治性、社会能力、反应性和主动性。 1.2Agent具有的特性 根据wooldridge的定义，对于Agent所应具有以下特征： 1.自治性(Autonomy)：Agent一般都具有自己的资源和局部于自身的控制机制，能够在没有外界直接操控下，根据自身的内部状态以及感知的外部环境信息，决定和控制自身的行为。 2.社会能力(Social Ability)：Agent之间并不是孤立的。和人一样，Agent具有通信能力，能够通过某种Agent通信语言与其他Agent进行各种各样的交互，也能和其他各类Agent一起有效地完成各种层次的协同工作。 3.反应性(Reactivity)：Agent能够及时地感知其所在外部环境的变化，并能够针对一些特定的时间做出相应的反应。 4.主动性(activity)：Agent能够遵循其承诺采取主动行动，表现出面向目标的行为。它要求Agent保持比较稳定的目标，它的动作都是以此目标为依据的，从而产生一种叫做目标指引的行为(Goal Directed Behavior)。 1.3Agent分类 从不同的角度，Agent有下面几种分类方法： 1.根据Agent的存在形式：分为有形Agent和无形Agent。有形Agent以是智能控制器、机器人，甚至是操作人员。无形Agent一般指软件Agent，可能有
1、硬币面值组合 描述 使用1角、2角、5角硬币组成n 角钱。 设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。 输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。 输入 一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。 输出 输出有若干行，每行的形式为： i a b c 第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。
源代码： #include
} 2、比赛排名 描述 5名运动员参加100米赛跑，各自对比赛结果进行了预测： A说：E是第1名。 B说：我是第2名。 C说：A肯定垫底。 D说：C肯定拿不了第1名。 E说：D应该是第1名。 比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。 请编程判断5位选手各是第几名。 输入 无 输出 输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次， 第3行是C的名次，第4行是D的名次，第5行是E的名次。 样例输入
基础架构事业群-数据库技术-数据库内核 何登成 Paxos/Raft 分布式一致性算法原理剖析及其在实战中的应用
目录Contents Consensus Problem Basic Paxos Multi-Paxos and Raft 实战分析 参考资料
定义：The consensus problem requires agreement among a number of processes (or agents) for a single data value.
?理解Consensus 问题的关键 ?绝对公平，相互独立：所有参与 者均可提案，均可参与提案的决 策 ?针对某一件事达成完全一致：一 件事，一个结论 ?已经达成一致的结论，不可被推 翻 ?在整个决策的过程中，没有参与 者说谎 ?晚饭吃什么？ 炉鱼食堂同乐会 炉鱼炉鱼 炉鱼 Consensus Algorithm
Consensus Algorithm：Basic Paxos ?Basic Paxos ?一个或多个Servers可以发起提案（Proposers） ?系统必须针对所有提案中的某一个提案，达成一致 ?何谓达成一致？系统中的多数派同时认可该提案?最多只能针对一个确定的提案达成一致 ?Liveness (只要系统中的多数派存活，并且可以相互通信)?整个系统一定能够达成一致状态，选择一个确定的提案
Basic Paxos：Components ?Proposers ?Active：提案发起者（value） ?处理用户发起的请求 ?Acceptors ?Passive：参与决策，回应 Proposers的提案 ?存储accept的提案（value）， 存储决议处理的状态 ?Learners ?Passive：不参与决策，从 Proposers/Acceptors学习最新 达成一致的提案（value）?本文接下来的部分，一个Server同时具有Proposer和Acceptor两种角色，Learner角色逻辑简单，暂时不讨论
计箨机应用研究２０００车 多Ａｇｅｎｔ系统及其组织结构 赵龙交１３候义斌‘ （１西安霆逯走擎工程与耪攀研究琏骛资７ｌｏｏ毒９）＜２鸯癌棱技拳磺究辑西安露００２蛰 摘要组织结构为Ａｇ∞ｔ成员提供一个相置也闻交互的框架，谛每个Ａ鲫诚员挺僻一个多Ａｇ酬群体 求解问题的商层观点和相关捕息。诗论了Ａｇｅｎｔ的概念和姑构。井根据多Ａｇ廿ｌｔ系纨的特点和目标，络出和分析了多删系统的蔓艮成和三种组织蛄构。 关键词Ａ彗材哇盎制体奏觚ｓ虹织结构 ｌＡｇ∞ｔ的概念 Ａｇｅｎｔ是一个运行于动态环境的具有较高自制能力的实体（即自制体可以是系统、机器等：软件Ａ斟ｎｔ是一个计算机软件程序），其根本鞋标是接受另外一个实薛（繇主搭霹壤是嚣ｌ产、幸｝舞壤疆亭、系统戢梳嚣等）的委托弊为之提供帮助和搬务，能够在该秘标的驱动下主动采取包括社交、学弼肄手段在内的各种必要的行为以赙知、适应并对动卷环境的变化进杼适当的反应，它与其服务主体之翘典岿较为松散和相对独立戆关系。 趣咖不是自期和提供帮勘两种属性静簿革结台，而是二者有机的统一体。为燕体提供帮助和服务尾Ａｇｅｎｔ的目标和本质．自制是戴属性和实现其目标所应该采取的簪段。Ａｇ酬的所群岛割｛亍为均是以般嘉教遣势用户提撰黎助为基静瓣，Ａｇ畦技零瓣零震箍是研究如旃搜一个或多个实体嚣可髓地不打搅用户、依靠其自身的能力、采甩各种可能的方法和技术完成用户所委托的艟为复杂或烦瑚的任务．因此，一个Ａｇｅｎｔ应该尽Ｗ能准确地理解用户的真实意图，戗括帮助用户方裁、准确缝播述釉寝达任务意强，浆敬各种鑫蓦标鞋韵瓣、糨摄主韵辩搿为。摇社交、学溜、推理、合作普：蒋知并适应复杂的和不断变化的动；嚣环境；有效地利用环境中的各种埘能利用的数据、知识、信息和计算摄源．为用户提供迅捷、准确和满意齄帮助。 ２矗零贰鹁蒸奉鳍掬帮氧弧Ｓ≤醚Ｈ珏ｌ－Ａ￡描ｌＳｙｓｔｅＩｎ） Ａｇｃｎｔ的基本结构如图ｌ所示．由环境感知模块、执行模块、通讯模块、信息处理摸抉、决策与智能控濑ｌ模块跌及知识麾和任务表组成。邸境感知模块、执学筷块窝逶谖模块受责专幕统球缓帮其它Ａ辞珏ｔ避褥交互，任务袭为该Ａｇｅｎｔ所要完成舶功程和任务。镄息处理模块负赏对感知和接收到的信息进行初步地加工、处理和存储．决策与智能控制模块是赋予＾ｇ蝴ｔ姆能的关键部件。它运用蛔识库巾脾知识对信息嫩蠼 牧稿日期：２０。。年１胃２１日模块处理所得到的井部环境信息和其它Ａｇｅｎｔ的通讯信息进行谶一步的分析、推理，为进一步的通讯或从 任务表中选择适当的任务供执行模块执行作出台理的决燕。程燃ｓ中，各Ａｇ瞅怒蠢制斡。各Ａｇ粼乏间只能透过逶谶跬爱对拜麓黯敬囊镬互影噙，各Ａ鬈ｃ珏ｔ鑫身的行为最终是由其自己决策的。甾＼阻罄港 图１＾倒的蒜潜鸿｝构 Ａｇ器谴投术靛两个主要发展方寅是捣筑嬉德复杂、鲡镑率富帮殛耗强文秘募Ａｇａｔ系统和虫多个结构和性熊较为简单的Ａｇ锄ｔ缀成一个ＭＡｓ。遄垃多个 Ａｇｃｎｔ之问的协作，使整个累娩具有丰富的知识和强大的功能。所谓ＭＡｓ是指出雾个蛳ｔ组成的一个较为松散蛇多Ａｇｅｎｔ联邦，这烂Ａｇｅｎｔ成员之间相互协嚣，招蔓瓣务，共嚣完袋一个任务。砻敏聪娥晏静括动是自制和独立的，其自街的目标和行为布蹙其它Ａ嚣ｎｔ成崩的限制，它通过巍争或磋商等手段协调和解决各成员Ａｇｅｎｔ的目标和行为之间的矛盾和冲突。ＭＡｓ卣奇数描和资源是分散的，每个Ａｇｅｎｔ对予所要完纛羲｛王势绷骞不全器瓣信感残髓力，摹存在垒嚣魏控制系统，任务昭执行和计算怒异步柏。Ａ弘ｓ主簧研究整个Ｍ＾ｓ精动中各Ａｇ龃ｔ之间的相互作用如何产生、每个Ａ蹦ｌｔ成员的推理和行为决莆如何考虑蔗婉或环境中其它Ａ龄ｎｔ的存在、Ａｇｅｎｔ成员蛉日标和行为之间霹藐翦｛中突捡涮釉协调跌疑强务靼赍添瓣划分、努配帮管理等。 ３ＭＡｓ社会及其组织结构 ＭＡ８的姐织结构为Ａ萨ｎｔ成员提供一十棚强之间交互的框槊，为每个Ａ鲫ｔ成员提供一个多＾嚣耐群体求簿闯露的离屡鼹点和相蓑攘塞，鞋便合理地势聚任务著蓬这簸Ａｇ％嘧漫戆镑嚣姆琏貉蠢工捧。糍好藏、 万方数据
常用计算公式 1、投资率，又称资本形成率，通常指一定时期内资本形成总额（总投资）占国内生产总值的比重，一般按现行价格计算。目前，国际上通行的计算方法为： 2、消费率，又称最终消费率，通常指一定时期内最终消费（总消费）占国内生产总值的比率，一般按现行价格计算。用公式可表示为： 其中，最终消费包括居民消费和政府消费。 社会上也有人用社会消费品零售总额代替最终消费，用生产法GDP 代替支出法GDP计算消费率，但这种方法大大低估了消费率。原因是，社会消费品零售总额与最终消费存在较大差异，它仅与最终消费中的商品性货物消费相对应，服务性消费以及实物性消费、自产自用消费和其他虚拟消费都不包括在内，不能全面反映生产活动最终成果中用于最终消费的总量。 反映三大需求对经济增长拉动的指标 3、投资拉动率，又称投资对GDP增长的拉动率，通常指在经济增长率中投资需求拉动所占的份额，也称投资对GDP增长的贡献率。计算方法为： 同时，还可以计算投资拉动GDP增长的百分点。计算方法为： 投资拉动GDP增长（百分点）＝投资拉动率×GDP增长率 其中的GDP增长率一般为不变价生产法GDP增长率（下同）。 4、消费拉动率，又称消费对GDP增长的拉动率，通常指在经济增长率中消费需求拉动所占的份额，也称消费对GDP增长的贡献率。计算方法为：
同时，还可以计算消费拉动GDP增长的百分点。计算方法为： 消费拉动GDP增长（百分点）＝消费拉动率×GDP增长率 5、“贡献率”？它是怎样计算的？ 在统计分析中经常使用“贡献率”，那么“贡献率”是什么含义？它是怎样计算的？ （产业贡献率：指各产业增加值增量与GDP增量之比 产业拉动率：指GDP增长速度与各产业贡献率之乘积。） 贡献率是分析经济效益的一个指标。它是指有效或有用成果数量与资源消耗及占用量之比，即产出量与投入量之比，或所得量与所费量之比。计算公式： 贡献率（%）=贡献量（产出量，所得量）/投入量（消耗量，占用量）×100% 贡献率也用于分析经济增长中各因素作用大小的程度。 计算方法是： 贡献率（%）=某因素贡献量（增量或增长程度）/总贡献量（总增量或增长程度）×100% 上式实际上是指某因素的增长量（程度）占总增长量（程度）的比重。 举例说明如下： 总资产贡献率（%）=（利润总额+税金总额+利息支出）/平均资产总额×100% （1）总资产贡献率：反映企业资金占用的经济效益，说明企业运用全部资产的收益能力。 （2）社会贡献率：是衡量企业运用全部资产为社会创造或支付价值的能力。 社会贡献率（%）= 社会贡献总额/平均资产总额×100% 社会贡献总额包括工资、劳保退休统筹及其他社会福利支出、利息支出净额、应交增值税、产品销售税金及附加、应交所得税及其他税、净利润等。为了反映企业对国家所作贡献的程度，可按上述原则计算贡献率。
分布计算环境作业 一．通过生成进程来构建并发服务器与使用多线程来构建并发服务器相比有优点也有缺点，请分析这两种方式的优缺点。你认为基于CORBA实现的并发服务器是基于生成进程的方法，还是基于多线程的方法？为什么？ 并发服务器需要同时处理多个请求。 采用多进程： 优点：1）处理各个请求的进程之间隔离性好。 缺点：1）创建/撤销处理各个请求的进程的代价大；2）分发器（主进程……）将请求发送到另一个进程的代价大（如果能说明为什么代价大更好）；3）如果各个子进程间需要通信，代价大。 采用线程： 优点：1）创建/撤销处理各个请求的线程的代价小；2）分发器（主线程……）将请求发送到另一个线程的代价小（如果能够说明为什么代价小更好）；3）如果各个线程间需要通信，代价小。 缺点：1）一个线程出问题，可能会影响其他线程。 CORBA：使用多线程技术实现并发服务器。因为如果采用多进程实现，有以下问题：1）服务器端要同时维护多个可被用户访问的CORBA对象，这些对象的数量常常会比较大，为每个服务对象起一个进程，进程数会比较大，系统开销过大；2）对于远程方法调用来说，请求的参数比较复杂，主进程将请求再发送给子进程，开销比较大；3）主进程、子进程都需要ORB的Runtime，进程启动/撤销的代价大；所以如果采用多进程的话实现并发CORBA服务器很困难。 主要问题： (一)针对性不够： a)直接罗列进程和线程的优缺点 (二)理由不够充分： a)为支持高并发及高可用，所以多线程或多进程 b)为支持稳定性和健壮性，所以多线程或多进程 c)ORB拿到请求后要决定哪一个对象实例完成这个请求，送过去，这种工作过程类似于线程
二、常用相关分析方法及其计算 在教育与心理研究实践中，常用的相关分析方法有积差相关法、等级相关法、质量相关法，分述如下。 （一）积差相关系数 1. 积差相关系数又称积矩相关系数，是英国统计学家皮尔逊（Pearson ）提出的一种计算相关系数的方法，故也称皮尔逊相关。这是一种求直线相关的基本方法。 积差相关系数记作XY r ，其计算公式为 ∑∑∑===----= n i i n i i n i i i XY Y y X x Y y X x r 1 2 1 2 1 ) ()() )(( (2-20) 式中i x 、i y 、X 、Y 、n 的意义均同前所述。 若记X x x i -=,Y y y i -=，则（2-20）式成为 Y X XY S nS xy r ∑= (2-21) 式中n xy ∑称为协方差，n xy ∑的绝对值大小直观地反映了两列变量的一致性程 度。然而，由于X 变量与Y 变量具有不同测量单位，不能直接用它们的协方差 n xy ∑来表示两列变量的一致性，所以将各变量的离均差分别用各自的标准差 除，使之成为没有实际单位的标准分数，然后再求其协方差。即： ∑∑?= = )()(1Y X Y X XY S y S x n S nS xy r
Y X Z Z n ∑?= 1 (2-22) 这样，两列具有不同测两单位的变量的一致性就可以测量计算。 计算积差相关系数要求变量符合以下条件：（1）两列变量都是等距的或等比的测量数据；（2）两列变量所来自的总体必须是正态的或近似正态的对称单峰分布；（3）两列变量必须具备一一对应关系。 2. 积差相关系数的计算 利用公式 (2-20)计算相关系数，应先求两列变量各自的平均数与标准差，再求离中差的乘积之和。在统计实践中，为方便使用数据库的数据格式，并利于计算机计算，一般会将(2-20)式改写为利用原始数据直接计算XY r 的公式。即： ∑∑∑∑∑∑∑---= 2 22 2 ) () (i i i i i i i i XY y y n x x n y x y x n r (2-23) （二）等级相关 在教育与心理研究实践中，只要条件许可，人们都乐于使用积差相关系数来度量两列变量之间的相关程度，但有时我们得到的数据不能满足积差相关系数的计算条件，此时就应使用其他相关系数。 等级相关也是一种相关分析方法。当测量得到的数据不是等距或等比数据，而是具有等级顺序的测量数据，或者得到的数据是等距或等比的测量数据，但其所来自的总体分布不是正态的，出现上述两种情况中的任何一种，都不能计算积差相关系数。这时要求两列变量或多列变量的相关，就要用等级相关的方法。 1. 斯皮尔曼(Spearman)等级相关 斯皮尔曼等级相关系数用R r 表示，它适用于两列具有等级顺序的测量数据，或总体为非正态的等距、等比数据。
车联网（VANET）是移动自组织网络在道路上的应用，其具有移动自组织网络（MANET）的各种特点，故此，我们先介绍MANET的环境下的服务协同研究，可发现一些具有实用价值的思想和方案对V ANET环境下的研究具有积极的借鉴意义。 由于MANET通信环境恶劣，移动性强的特点，传统的服务组合方法多是面向有线网络，集中式体系结构，不适用于目前自主移动网络，而目前MANET环境下典型的服务组合系统有以下三种。 1）基于代理的分布式服务组合，BDSCP 该系统框架分为四层：网络层、服务发现层、网络组合与管理层以及应用层。其系统框架分层图如下图1所示。其基本工作流程如图2所示。 图1.BDSCP系统框分层图 图2.系统服务组合基本工作流程图 BDSCP协议作为一个专门面向MANET环境的服务组合框架，采用分布式的动态服务管理者选择机制，避免的了单点失效，并设计了一种基于服务分组的服务发现方法，有效提高服务发现效率；同时还为发现的服务提供了基于分组的服务路由机制，但是也存在一定的问题 （1）代理寻找过程和频繁的发现过程不仅浪费大量的宽带资源还延长了协议响应时间。（2）提出的GSD服务发现协议需要节点周期的向邻居节点广播服务信息，容易造成广播包冗余；同时重复的服务查询包和单播方式的转发引起的服务查询包冗余现象也比较突出。（3）BDSCP没有涉及出现多个候选服务的时候如何进行选择。 （4）没有对网络中服务的QoS进行考虑，尤其是当出现多个候选服务的时候。 2）失败容忍的上下文感知服务组合协议，FTCASCP 该设计以设计出具有分布式的、容错性、上下文感知的服务组合系统为出发点，其采用在一个服务会话中寻找组合服务的所有原子服务的策略来提高服务组合的效率，其体系结构如图3所示，工作的主要流程阶段如图4所示。
度。下图是个例子：
四、实验结果与分析（源程序及相关说明） 1)#include
IP网络拓扑自动发现 自从20世纪90年代以来，越来越多的企业及个人在加入Internet网，使网络规模持续扩大。为了适应越来越多的流量，新节点、新链路不断的被引进到网络上，从而使手工维护很难跟上网络的变化，给网络管理带来困难。 网络由一起工作的大量实体构成，向用户提供某种服务。这些实体功能由硬件和软件执行，一些出现在真实网络中实体的例子有路由器、服务器、普通主机、链路等，所有这些都影响着网络运行的方式及提供给最终用户的服务质量。例如，如果一个应用服务器（Web Server）出现宕机而从网络上剥离下来，那么用户将得不到他们所期望的服务（浏览网页）。提到拓扑发现，一般是指发现完成最终用户服务所涉及到的所有实体，不仅要发现实体，而且要发现实体在网络中所起的作用及实体间互相连接的方式。 网络拓扑对网络管理、网络规划非常有用。例如，网络故障、流量瓶颈等重要信息能直接显示在网络拓扑上，这样网络管理员对当前的网络状况就有一个清楚的认识，对哪里发生了故障一目了然。如果网络拓扑上显示一条链路总处于满负荷传输状态，那么扩大该条链路的容量对提高网络性能将有很大帮助。此外，网络拓扑对网络仿真也十分重要，要仿真能否在现有网络上新开放一种应用，必须首先有正确的网络拓扑。 获得网络拓扑的最简单的方法莫过于让管理员根据实际网络手工绘出其拓扑，但现在网络越来越复杂，越来越庞大，并一直在膨胀，而且实体在网络中担负的功能也越来越复杂，要跟踪这样一个网络需要花费很多时间或精力，而且网络一旦有所改变所有工作必须重做。网络拓扑自动发现正是基于这个原因发展起来的，本文对能用于拓扑发现的一些常用的工具和技术作了简要的介绍，并基于笔者的实践提供了一个简单的算法实现，该算法主要针对同一个管理机构下的IP网络的拓扑自动发现，更复杂的拓扑发现算法可在此基础上进一步扩展。 一、用于拓扑发现的工具 1. Ping