第３４卷第ｌＯ期 ２０１３年ｌＯ月 通信学报 Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ 、，０ｌｌ３４ Ｎｏ．１Ｏ Ｏｃｔｏｂｅｒ ２０１３ ｄｏｉ：１０．３９６９￣．ｉｓｓｎ．１０００—４３６ｘ．２０１３．１０．００５
基于改进蚁群算法的可信服务发现
盛国军 ，一，温涛 ，一，郭权 ，宋晓莹１，２
（１．东北大学软件中心，辽宁沈阳１１０００４：２．大连东软信息学院辽宁省网络安全与计算技术重点实验室，辽宁大连１１６０２３）
摘要：针对非结构化Ｐ２Ｐ网络中的服务发现问题，提出了一种基于改进蚁群算法的可信服务发现方法。该方法 在传统蚁群算法基础上应用若干新的策略控制蚁群的行为，如动态蚁群策略、子蚂蚁策略、服务节点的信誉评估 策略以及蚂蚁的恶意节点惩罚策略等，高信誉服务节点在蚂蚁的推荐下进行邻居更换和自组织。这些策略和方法 为蚁群算法在分布式环境下服务发现的应用研究提供了一种新思路。实验结果表明，本算法在各种常见复杂网络 环境下仍可保证较高的可信服务查准率和更高的综合服务发现效率，通过对实验数据的分析和解释得到了若干有 益的结论，为进一步的研究工作奠定了基础。 关键词：服务发现；自组织网络；可信服务；动态蚁群策略；子蚂蚁策略 中图分类号：ＴＰ３１１ 文献标识码：Ａ 文章编号：１０００．４３６Ｘ（２０１３）１０．００３７，１２
Ｔｒｕｓｔｗｏｒｔｈｙ ｓｅｒｖｉｃｅ ｄｉｓｃｏｖｅｒｙ ｂａｓｅｄ ｏｎ
ａ ｍｏｄｉｆｉｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ
ＳＨＥＮＧ Ｇｕｏ－ｊｕｎ ，ＷＥＮ Ｔａｏ ，ＧＵＯ Ｑｕａｎ ．ＳＯＮＧ Ｘｉａｏ ｙｉｎｇ ，
（１．Ｓｏｆｔｗａｒｅ Ｃｅｎｔｅｒ，Ｎｏｒｔｈｅａｓｔｅｒｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ １１０００４，Ｃｈｉｎａ； ２．Ｌｉａｏｎｉｎｇ Ｋｅｙ Ｌａｂ ｏｆＮｅｔｗｏｒｋ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｃｏｍｐｕｔｍｇ Ｔｅｃｈｎｏｌｏｇｙ，Ｄａｌｉａｎ Ｎｅｕｓｏｆｔ Ｉｎｆｏｒｍａｔｉｏｎ Ｉｎｓｔｉｔｕｔｅ，Ｄａｌｉａｎ １ １６０２３，Ｃｈｍａ）
Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ ａｔ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｓｅｒｖｉｃｅ ｄｉｓｃｏｖｅｒｙ ｉｎ ｕｎｓｔｒｕｃｔｕｒｅｄ Ｐ２Ｐ ｎｅｔｗｏｒｋ，ａ ｔｒｕｓｔｗｏｒｔｈｙ ｓｅｒｖｉｃｅ ｄｉｓｃｏｖｅｒｙ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ａ ｍｏｄｉｆｉｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｗａｓ ｐｒｏｐｏｓｅｄ．Ｓｏｍｅ ｎｏｖｅｌ ｐｏｌｉｃｉｅｓ ｗｅｒｅ ｉｎｔｒｏｄｕｃｅｄ ｔｏ ｃｏｎｔｒｏｌ ｔｈｅ ｂｅ— ｈａｖｉｏｒ ｏｆ ｔｈｅ ａｎｔ ｃｏｌｏｎｙ，ｓｕｃｈ ａｓ ｔｈｅ ｄｙｎａｍｉｃ ａｎｔ ｃｏｌｏｎｙ ｐｏｌｉｃｙ，ｔｈｅ ｓｕｂ－ａｎｔ ｐｏｌｉｃｙ，ｔｈｅ ｒｅｐｕｔａｔｉｏｎ ｅｖａｌｕａｔｉｏｎ ｐｏｌｉｃｙ ｔｏ ｓｅｒｖｉｃｅ ｐｅｅｒｓ，ａｎｄ ｔｈｅ ｐｕｎｉｓｈｍｅｎｔ ｐｏｌｉｃｙ ｔｏ ｍａｌｉｃｉｏｕｓ ｐｅｅｒｓ．Ｓｅｒｖｉｃｅ ｐｅｅｒｓ ｗｉｔｈ ｈｉｇｈ ｒｅｐｕｔａｔｉｏｎ ｃｏｕｌｄ ｃｈａｎｇｅ ｔｈｅｉｒ ｎｅｉｇｈｂｏｒｓ ａｎｄ ｍａｋｅ ｓｅｌｆ－ｏｒｇａｎｉｚａｔｉｏｎ ｕｎｄｅｒ ｔｈｅ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ｏｆ ａｎｔｓ．Ｔｈｅｓｅ ｐｏｌｉｃｉｅｓ ａｎｄ ｍｅｔｈｏｄｓ ｐｒｏｖｉｄｅ ｎｅｗ ｉｄｅａｓ ｆｏｒ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｒｅｓｅａｒｃｈｅｓ ｏｆ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ，ｄｉｓｔｒｉｂｕｔｅｄ ｓｅｒｖｉｃｅ ｄｉｓｃｏｖｅｒｙ．Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｅｘｐｅｒｉ— ｍｅｎｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ Ｃａｎ ｇｕａｒａｎｔｅｅ ｈｉｇｈｅｒ ｔｒｕｓｔｗｏｒｔｈｙ ｓｅｒｖｉｃｅ ｐｒｅｃｉｓｉｏｎ ａｎｄ ｂｅＲｅｒ ｉｎｔｅｇｒａｔｅｄ ｓｅｒｖｉｃｅ ｄｉｓｃｏｖｅｒｙ ｐｅｒｆｏｒｍａｎｃｅ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ ｅｎｖｉｒｏｎｍｅｎｔｓ，ａｎｄ ｓｏｍｅ ｕｓｅｆｕｌ ｃｏｎｃｌｕｓｉｏｎｓ ｗｅｒｅ ｏｂｔａｉｎｅｄ ｔｈｒｏｕｇｈ ｔｈｅ ａｎａｌｙ— ｓｉｓ ａｎｄ ｅｘｐｌａｎａｔｉｏｎ ｏｆｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｄａｔａ，ｌａｙｉｎｇ ａ ｓｏｌｉｄ ｆｏｕｎｄａｔｉｏｎ ｆｏｒ ｆｕｒｔｈｅｒ ｒｅｓｅａｒｃｈｅｓ． Ｋｅｙ ｗｏｒｄｓ：ｓｅｒｖｉｃｅ ｄｉｓｃｏｖｅｒｙ；ｓｅｌｆ－ｏｒｇａｎｉｚｉｎｇ ｎｅｔｗｏｒｋ；ｔｒｕｓｔｗｏｒｔｈｙ ｓｅｒｖｉｃｅ；ｄｙｎａｍｉｃ ａｎｔ ｃｏｌｏｎｙ ｐｏｌｉｃｙ；ｓｕｂ—ａｎｔ ｐｏｌｉｃｙ
１ 引言
Ｐ２Ｐ网络中的各节点是逻辑对等的，各节点自 治又相互合作．可以把ｉｎｔｅｒｎｅｔ看成一个Ｐ２Ｐ系统， 系统中的组件通过互相提供服务进行对等交互。网
络中任何节点都可以发布自己的服务，服务消费者 在面对网络中存在着的大量功能相同或相似、服务 质量不同的服务，由于缺乏交互经验而使其面临着 不确定的交易风险，在正式调用目标服务之前，服 务消费者无法在可行的时间和成本范围内对这些 第三方提供的Ｗｅｂ服务进行完备的测试，从而很难
得知目标服务是否安全可信，这为Ｐ２Ｐ环境下的可 信服务发现提出了更高的要求，即Ｐ２Ｐ系统应具有
一个能使节点间相互帮助和协作来发现高信誉服
务节点的方法。在大规模开放的Ｐ２Ｐ系统中，采用 传统的服务等级协议或第三方中心节点来保证服
收稿日期：２０１３．０１．２８；修回日期：２０１３—０４．２２ 基金项目：国家自然科学基金资助项目（６１１７０１６８，６１１７０１６９） Ｆｏｕｎｄａｔｉｏｎ Ｉｔｅｍ：Ｔｈｅ Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆＣｈｉｎａ（６１ １７０１６８，６１ １７０１６９）
通信学报 第３４卷
务质量的方法耗时耗力，且运行成本很高，而信任 和信誉…机制更加适用于大规模开放Ｐ２Ｐ系统中可
信资源的管理，近年来在学术界和工业界受到极大 关注。ＥｉｇｅｎＴｒｕｓｔ［２］是典型的全局信任模型，该模型
通过节点间信任度的迭代为每个节点计算全局信
任值，网络中节点的全局信誉由与其交互过的其他 节点对该节点的评价聚合而成，该模型还假设Ｐ２Ｐ
网络在创建时就具有全局高信任值的节点存在，其 在整个Ｐ２Ｐ网络范围内的迭代将导致巨大开销，这
是大部分基于Ｐ２Ｐ网络的全局信任模型所具有的共 同问题。泛洪（ｆｌｏｏｄｉｎｇ）是传统非结构化Ｐ２Ｐ网络资
源查找的典型路由算法，其盲目的消息转发方式造 成的通信开销十分巨大对于大规模Ｐ２Ｐ网络，即使 采用ＴＴＬ限制的广播方式也会造成大量网络资源 浪费。而蚁群算法ｌ３ （ＡＣＳ，ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ）由于具
有良好的白适应性和动态自组织性，能较好地解决 大规模Ｐ２Ｐ网络中的路由问题。
本文为解决上述非结构化Ｐ２Ｐ网络中的可信服 务定位问题，将蚁群算法与Ｐ２Ｐ网络中的信誉机制
相结合，提出了一种基于自组织Ｐ２Ｐ网络与改进蚁 群算法的可信服务发现方法。该方法在传统蚁群算 法基础上应用若干新的策略控制蚁群的行为，高信
誉服务节点在蚂蚁的推荐下进行邻居更换和白组 织。实验结果表明，该算法可在各种常见复杂网络
环境下保证较高的可信服务查准率，且可以大幅度 降低蚂蚁网络漫游的总跳数，从而使算法的单跳查
询效率得到大幅提升。
２相关工作
文献［４］提出一种基于Ｐ２Ｐ网络和语义技术的 服务发现方法，该方法将Ｐ２Ｐ网络中语义相似的节 点聚类成语义群，每个服务查询请求按照语义匹配
度被路由到特定的语义群以提高查询效率。文献［５］ 提出一种基于结构化Ｐ２Ｐ网络的服务发现方法，该
方法采用增强的Ｃｈｏｒｄ协议，用分层次的多环取代 传统Ｃｈｏｒｄ协议中的单环，根据打分选择出服务提 供能力强的节点组成超环来管理Ｐ２Ｐ网络。文献［６］ 提出了一种基于多ａｇｅｎｔ系统的分布式服务发现框
架，该系统中的ａｇｅｎｔ可根据自己的服务查询偏好
和效用进行邻居更新和自组织以提高服务查询的 成功率。潘静等１７１提出一种基于声誉的推荐者发现
方法，该方法通过信任的传递计算具有高声誉值的
服务推荐者，其研究重点是发现可信的服务推荐 者。谢晓芹等 ］提出 种基于推荐网络的服务发现
方法，该方法使用推荐有效地提高了服务发现的效
率，引入蚁群算法并使用节点社交度和服务信息度 引导蚂蚁的漫游过程，但该模型没有考虑Ｐ２Ｐ网络 中恶意服务提供者对服务发现结果造成的影响。郑 啸 ９］提出一种基于移动ａｇｅｎｔ的服务发现机制，
该方法中，ＳｅａｒｃｈＡｇｅｎｔ从无结构化Ｐ２Ｐ网络中具
有服务注册功能的中心服务节点出发与ＧｕｉｄｅＡｇｅｎｔ 合作寻找目标服务，该方法仍然缺少对可信服务发 现问题的考虑。ＦＥＬＩＸ Ｇ Ｍ等ＩⅢ 提出了一种Ｐ２Ｐ
网络环境下基于蚁群算法的可信服务发现模型 ＴＡＣＳ，在该模型中，蚂蚁发现的高信誉服务节点对
应路径上的信息素得到增强，恶意服务节点对应路 径上的信息素值将会得到惩罚，该模型的主要问题
在于：在每轮迭代后，服务请求节点要通过对蚂蚁 发现的服务的实际调用结果来评价该节点的信誉类 型，多次迭代将导致大量的服务调用成本，该设计
不合理也不具有实践可操作性；另外ＴＡＣＳ模型对 应实验中的Ｐ２Ｐ网络只有几十个节点以内的数量级，
节点数量太少导致蚂蚁的路由复杂度和难度过于简 单从而缺乏对算法性能的有力支持。 在以上相关研究的基础上，本文提出了一种非
结构化Ｐ２Ｐ网络中的可信服务发现方法，该方法将 蚁群算法与Ｐ２Ｐ网络中的信誉机制相结合，蚂蚁利
用其漫游路径上的服务消费者节点对相关服务的 历史调用信息推导出服务提供者的局部信誉视图，
并将其用于对相关服务提供者的信誉评估中。通过 常见的各种类型大规模Ｐ２Ｐ网络的仿真实验表明， 该方法能获得较高的可信服务查全率和查准率。
３问题描述
定义１信誉：Ｊｏｓａｎｇ将信誉定义¨ｌＩ为“信誉
是群体关于某人或某事的特征或立场的大众观点
和看法。” 定义２服务的局部信誉：Ｐ２Ｐ服务网络中， 所有该服务消费者节点集合中的部分节点对该服 务结果的总体评价和看法。
定义３服务交易日志是一个四元组ＳＴＬ＝（ｓｐ，
ｋｗｓ，ｔｉｍｅ，ｓａｔ），ｓｐ是服务提供者节点标识，ｋｗｓ是被 调用服务的关键字标识，ｔｉｍｅ是服务调用时间， ｓａｔｅ【＿＿１，１】是服务消费者调用完服务后对该服务结
果的满意度，当一个节点调用另一个节点的服务
后，服务请求者节点中的ａｇｅｎｔ就会生成一个新的