面向社交网络基于协作度协商的联盟形成机制

胡军等

摘要：分布式多Agent构成的社交网络通常表现出不同的特征，针对不同的社交网络和多Agent本身的异质性，提出了一种面向社交网络的基于协作度协商联盟形成机制.该机制依托多Agent构成的社交网络环境，建立面向分布式环境的分布式协商协议，并设计一种考虑到社交网络特征和Agent异质性的基于协作度的协商策略，采用分布式自动协商方式形成联盟.通过对全连通网络、层次网路和小世界网络的仿真实验结果表明，该机制能够有效地实现分布式环境下的联盟形成，并且在反应大多数实际应用环境的小世界社交网络中表现出相对较好的性能.

关键词：多Agent系统；联盟形成；分布式自动协商；社交网络；协作度

中图分类号：TP311 文献标识码：A

形成联盟是多Agents最常用的一种协作方式，高效的构建联盟是多Agent系统中的研究热点之一.目前的联盟形成方法存在着诸多的局限.一是，大多数方法针对多Agent全连通的情况，未考虑实际环境中Agents之间不同的连接结构，适用面较窄；二是，现有研究中大多是针对集中式系统的，不适用于分布式的应用情况，实用性不强；三是，忽略了不同Agent的异质性，没有考虑Agent的协作态度和协作资源的不同，实用性不强.如文献[1-4]中Agent之间都是全连通的，求解联盟的方法是通过搜索联盟结构图获得最优联盟结构.这样联盟形成的过程是一个NP难问题，而实际应用中全连通的Agent情况并不多见.文献[5-6]引入了社交网络和学习型协同图的概念，使得问题的求解简化，但是文中没有考虑不同的网络拓扑结构对联盟形成的影响.集中式环境中，文献[7-9]先通过协商形成候选联盟集，然后通过发起联盟的集中管理者Agent分配效用，确定最终联盟.针对分布式应用环境，文献[10]中建立了一套基于协商的联盟形成机制，Agent在分布式协商协议下形成联盟和确定效用值的划分并且对比了不同网络拓扑结构对联盟形成的影响，但是该机制没有考虑不同Agent的协作资源和协作态度的不同的异质性，使得联盟形成效率相对不高.为了解决现有研究中的局限性，本文试图建立一套在分布式环境下、面向社交网路结构的，异质的多Agent联盟形成机制.本文首先对比分析全连通的、随机树型的、小世界网络社交网络拓扑结构特点；然后针对分布式应用环境，构建一个分布式的协商协议来保障联盟形成；接下来考虑邻居Agent的历史信任度和资源拥有情况下引入了协作度的概念，来体现不同Agent的协作资源和协作态度的差异性，进而表达不同社交网络结构的特点，建立一种基于Agent协作度的协商策略；最后，实现面向社交网络的基于协作度协商联盟形成机制SOCNCF（social networks oriented collaboration degree based negotiation coalition formation mechanism ）.

1社交网络

分布式环境中，多Agent之间的连通关系构建的网络拓扑结构图，可以看成是多Agent之间的社交网络SN（Social Network）.该网络结构构成多Agent通过分布式协商形成联盟的环境基础.

1.1简单的社交网络

设AGENT={Agent1，Agent2，…，Agenti}，表示一个用于联盟形成的Agents集合，Agents连通关系的网络拓扑图G=（A，E）.A表示不同的Agent，E表示连接Agent的边，把可以与Agenti直接通信的其他Agent定义为Agenti的直接邻居，其形式化的定义如式（1）：

I（i）={i'|（i'，i）∈E，i'≠i} （1）

例如，e=（1，2）∈E表示的意思是Agent1和Agent2之间是连通的，他们可以通过协商形成联盟.

传统的联盟形成机制中很少考虑到成员Agent的SN差异性，大多考虑的都是全连通的情况.但是实际应用中Agent是处于不同的SN中的， Agent之间的交互将受到SN的差异性限制.图1是使用本文实验平台产生的3种简单的社交网络，可见，图1（a）中可能形成的联盟是{Agent0}，{Agent1}，{Agent2}，{Agent0，Agent1}，{Agent0，Agent2}，和{Agent0，Agent1，Agent2}.可见联盟{Agent1，Agent2}是不可能形成的，因为Agent1和Agent2没有之间相连，他们之间不能相互交互协商形成联盟.在图1（b）中由于Agent之间的连同关系变了，所以不能形成的联盟是{Agent0，Agent2}，{Agent1，Agent3}.最后，在如图1（c） 的全连通图中，由于每一个Agent之间都是之间相连的，所有{Agent0，Agent1，Agent2，Agent3}的任意子集都可能形成联盟.

1.2几类典型的社交网络

1.2.1全连通网络

全连通网络中Agents之间都是全连通的，其联通关系如图1（c）所示，此时I（i）={i'|i'∈AGENT，i'≠i}.在这种网络中，每个Agent的直接邻居数目是相同的，也就是说每个节点的度数是一样的，各个节点之间就有对称性.

1.2.2树型网络

树型社交网络是具有层次结构的社交网络，是通过随机选择节点的生成方式构建的树形结构.在随机树型的社交网络中，最典型的特点就是不同层次的Agent所具有的邻居数目|I（i）|差异性大.如图2所示，上层的Agent具有更高的连通性，而下层的Agent连通性比较差，叶子节点只有一个直接邻居.

1.2.3小世界网络

小世界网络一类特殊的复杂网络结构，在这种网络中大部份的节点彼此并不相连，但绝大部份节点之间经过少数几步就可到达.这反映的是现实世界中陌生人可以通过彼此共同认识的人而连接的现象.

小世界网络的判定准则有两个，分别是特征路径长度和高集聚系数.网络的特征路径长度是指在它的图表示中，两个节点的路径长度的平均值（这里路径长度指两节点间最短路径的长度）.许多复杂网络尽管节点数目巨大，但节点之间的特征路径长度则非常小[11].集聚系数则是用来描述“抱团”现象的，也就是“你朋友之间相互认识的程度”.从数学的角度上来说，一个节点的集聚系数等于与它相连的节点中相互连接的点对数与总点对数的比值.高集聚系数实际上保证了较小的特征路径长度[12].

2分布式协商模型

本文是使用分布式协商的方法形成联盟，所以首先介绍分布式协商的形式化模型基础；接下来叙述分布式协商要素；最后给出分布式协商协议.

可见，形成的联盟越大，获得的联盟效用越大.

2.1协商要素

分布式协商中的协商要素包括协商提议、协商区间和协商决策函数，这些都是构建分布式协商的前提.

2.1.1协商提议

2.1.2协商区间

所谓协商区间就是协商双方的协商的效用分配的波动区间，即最小效用和最大效用

2.1.3协商决策函数

协商决策函数是Agent在收到协商提议后的按照最大化自身利益的原则决策自身行为的过程.

2.2分布式协商协议

协商协议通过对分布式协商通信过程的规定和Agent协商状态的定义，来实现协商过程的收敛性和避免死锁.

3基于协作度的协商策略

3.1协商策略函数

本文提出基于协作度的协商策略CBNT（Cooperation DegreeBased Negotiation Tactic），协商策略函数如式（9）所示指数函数族来逐步产生让步后的新提议.

3.2协作度

本文引入了协作度的概念，来描述Agent的协作资源和历史协作状况的不同，从而体现在不同社交网络结构的差异性，进而通过协作度对协商态度值产生影响，来实现不同策略的协商过程.

表示的是协商态度值的最小值，协商过程中Agent的协商态度值不能小于这个值.

通过协作度实现对协商态度值的影响，在形成联盟时总是会参考邻居的协商态度值，针对性的降低协作度高的邻居协商态度值和提高协作度低的邻居的协商态度值；并且优先选择让步策略更好的邻居协商，使得让步更加迅速，并将协作度低的邻居Agent逐渐被淘汰，使得协商策略将更加智能高效.

4SOCNCF机制

SOCNCF机制在分布式协商模型的基础上使用基于协作度的协商策略进行联盟形成，分布式协商模型保证算法的收敛性，基于协作度的协商策略保证算法的高效性.SOCNCF机制实现算法如算法1所示.算法开始阶段会产生模拟分布式环境的不同类型的社交网络，同时对Agent的协作度初始化；每一次联盟形成过程开始前会利用前一次联盟形成计算出的协作度cooperationTemp作为本轮的初始协作度；然后开始多轮协商进行联盟形成，在遵循社交网络和分布式协商协议的前提下得到协商决策函数Decision；根据得到的不同Decision对用来计算Agent之间协作度的相关参数进行计算和对Agent的状态进行更新，一遍联盟形成后根据Agent之间协作度的相关参数计算协作度并保存至cooperationTemp.然后开始下一次联盟形成过程，直至MAXHISTORYTIMES次后算法结束.

算法1SOCNCFAlgorithm（）

SOCNCFAlgorithm（）{

graph = graphGen.getGg（）；

//产生Agents的社交网络，初始化当前协作度

cooperation=cooperationInit（）；

//Agent历史协作的初始化

cooperationTemp；//用来保存历史协作度记录

for times：1→MAXHISTORYTIMES

//利用协作度的动态更新进行

MAXHISTORY-TIMES次联盟形成

allAgents=initialiser.createAgents（）；

//Agent集初始化

cooperation=cooperationTemp；

//将上一轮的协作度记录赋给本Agent

for clock：1→MAX_TIME

//进行最大轮数不超过MAX_TIME的协商

for agent：allAgents

//遍历Agent集中所有的agent

if（agent.issleep&&！nonwaiting.isEmpty）

//判断Agent自身和邻居的状态

Decision=agent.getDecision（）；

//根据决策函数进行该Agent协商、决策

updateCooperationParameter（Decision，Parameter）//更新用来计算协作度的参数

updateState（Decision）

//根据得到的决策更新Agent的状态

sortNeiberhour（cooperation）

//根据Agent不同邻居的协作度的大小对邻居进行排序，下轮协商时将优先选择协作度高的Agent

endif

endfor //遍历完所有的Agent

endfor //本轮协商结束

CalculateCooperation（cooperationTemp， Parameter）//根据本次联盟形成的协作度

endfor//基于协作度的多次联盟形成过程结束

}

5实验分析

5.1实验设置

实验使用Eclipse平台仿真多Agent联盟形成过程，试验中模拟的机制有本文的SOCNCF和文献[10]社交网络中的联盟形成机制CFMSN（Coalition Formation Mechanism In Social Network），文献[10]中所述的联盟形成机制是单纯的考虑Agent之间的连通关系—协作资源，忽略了Agent之间在协作态度上的异质性.实验内容包括两部分，第1部分将对比使用不同的社交网络时SOCNCF机制和CFMSN在总共使用的协商轮数上的差异性，由于SOCNCF机制需要历史信息的累计，故进行了10次联盟形成的过程，分别是CFMSN，SOCNCF-2，SOCNCF-3，…，SOCNCF-10，可见第1次联盟形成实际上就是没有使用协作度信息的CFMSN机制；实验的第2部分将在平均协商轮数、协商成功率、平均联盟大小、平均个体效用等4个方面对比分析以上两种方法在不同的社交网络下形成联盟时的性能，由于我们的实际应用中大多的多Agent联盟形成环境都是小世界网络拓扑结构，所以我们期望SOCNCF机制相比CFMSN机制来说在小世界网络中有更好的性能.

为了对比不同网络拓扑结构和不同规模Agent集下SOCNCF机制的性能，Agent社交网络环境设置有两种，为了保证不同网络拓扑结构的可比性，第1种社交网络环境中将网络的最大度数都设定为20；第2种社交网络环境中将网络的最大度数都设定为40.实验中具体相关参数设置如下：

第1种社交网络环境中，全连通网络Agent集为21个，度数为20；小世界网络Agent集为100个，模拟真实的社交环境，最大度数限制为20，平均度数为8.8；随机树网络的Agent集为100个，模拟具有明显层次结构的环境，最大度数为20，平均度数为1.98.第2种社交网络环境中把全连通网络Agent集扩展到41，小世界网络和随机树网络的Agent集扩展为200，并限制最大度数为40.

单个Agent开销是0到1的随机分布；单个Agent的效用是开销的1.5倍到3倍；为了去除试验中随机过程的影响，每一次联通形成过程都将重复100次取置信度为95%的置信区间作为实验结果；为了得到SOCNCF机制那个的协作度信息，将进行10次联盟形成过程；初始协作度可以为15（激进型）、0.001（线性型）、-5（被动型）随机选择；为了既反映出Agent的协作态度，又反映出Agent的协作资源，协作度中取a，b都为0.5；同时为了使协作度对协商策略起到最为恰当的影响并且对邻居Agent协作度有较好的判断，β0设置为5，协商策略阀值Δcth为0.5.

5.2实验结果分析

实验的第1部分是对比使用不同的社交网络时，SOCNCF机制和CFMSN机制在协商轮数上变化的差异性.实验的设置如5.1节描述所示，其中Agent网络环境设置为第1种，初始协作度是5.1节中所示的3种随机选择的.为了验证SOCNCF的有效性，将进行10联盟形成的过程，为了去除试验中随机因素的影响，每次联盟形成过程重复了100次取平均值.最终实验结果如图5所示.

可以看出，全连通社交网络的协商次数在CFMSN机制中最少，但是它随着协作信息的累积没有很明显的减少联盟形成的协商次数；相反，小世界社交网络在CFMSN机制中联盟形成的协商次 数最大，但是由于SOCNCF机制中的协作度很好地反应了小世界社交网络的特性，使得它随着协作度信息的累集有很明显的协商次数改进，以至于到了SOCNCF-10时，它的协商次数最少.这反映了的SOCNCF机制更适合应用于小世界社交网络中，在不同的社交网络中具体的各项性能对比将在实验的第2部分进行.

实验的第2部分是为了对比CFMSN机制和SOCNCF在不同网络拓扑结构中的性能，从而验证SOCNCF机制的有效性.实验中Agent社交网络环境分别取5.1节中所示的两种；Agent的初始协作度是实验1中3种协商策略随机选择的，SOCNCF机制的数据取的是第10次形成联盟时（SOCNCF-10）的数据；每次形成联盟时重复试验100次，取置信度为95%的置信区间作为结果.Agent网络环境为第1种时，实验结果如表1所示；Agent网络环境为第2种时，实验结果如表2所示.其中协商轮数是联盟形成中协商交互提议最多的次数；协商成功率是联盟形成后，Agent集中收敛的Agent占的比分比，联盟大小是形成的所有联盟的平均值；而平均个体效用是所有收敛的Agent获得的效用的平均值.

由表1可以看出，当使用第1种Agent网络环境时，由于SOCNCF机制使用了基于协作度的协商策略，能够动态改变给对手的协商态度值，使得该机制与单纯的基于网络的CFMSN机制相比具有更好的性能；同时虽然使用CFMS机制时小世界社交网络中的效果不是最好，但是由于SOCNCF机制中的协作度是Agent的协作资源和Agent的协作态度的综合反映，而小世界网络的高聚集性正好使得不同Agent之间的协作资源差异性较大，小世界网络的低平均路径使得Agent之间的协商成功率高，从而协商态度较好，所以SOCNCF机制在小世界社交网络中具有比其他两种社交网络更好的性能.

表2中采取的是第2种Agent社交网络环境，这时Agent的规模扩大，节点最大的度数也增加了.实验结果表明，本文机制对网络环境做出了变换时总体的趋势和表1是相同的，即SOCNCF机制性能比CFMSN机制好，同时采取SOCNCF机制形成联盟时小世界社交网络中的性能最好.这说明SOCNCF机制的性能不会因为Agent社交网络环境的变化而失效，适应于不同Agent大小、不同平均度数的Agent社交网络.

综合上面两部分实验可知，在CFMSN机制中，小世界社交网络与其他两种社交网络相比在联盟形成效率上不是最好的.但是SOCNCF机制通过引入协作度的概念，充分反映了小世界网络高聚集、低平均路径的特性，通过对协作度信息的累计后的SOCNCF在小世界网络中具有最好的联盟形成性能.而恰恰我们现实应用中的多Agent系统大多都是小世界社交网络，也就是说我们的SOCNCF机制具有很好的实用性.

6总结

本文提出的SOCNCF机制通过社交网络模拟实际应用中的多Agent环境，制约潜在的提议数；然后结合一系列的协商要素建立分布式协商协议，保证了该机制的收敛性；最后使用基于协作度的协商策略，既能提高联盟形成的效率又能反应不同的社交网络的差异性；最后通过实验分析验证了该机制的可行性和有效性，并且验证SOCNCF机制在小世界网络中的性能更突出，从而验证了SOCNCF的实用性.

参考文献

[1]RAHWAN T， MICHALAK T， WOOLDRIDGE M， et al. Anytime coalition structure generation in multiagent systems with positive or negative externalities[J]. Artificial Intelligence， 2012， 186： 95-122.

[2]李少芳， 胡山立， 石纯一. 一种基于势结构分组思想的任一时间联盟结构生成[J]. 计算机研究与发展， 2012， 48（11）： 2047-2054.

LI Shaofang， HU Shanli， SHI Chunyi. An anytime coalition structure generation based on the grouping idea of cardinality structure[J]. Journal of Computer Research and Development， 2012， 48（11）： 2047-2054. （In Chinese）

[3]刘惊雷， 张伟， 童向荣， 等. 一种O（2.983n）时间复杂度的最优联盟结构生成算法[J]. 软件学报， 2011， 22（5）： 938-950.

LIU Jinglei， ZHANG Wei， TONG Xiangrong， et al. O（2.983n） time complexity algorithm for optimal coalition structure generation [J]. Journal of Software， 2011， 22（5）： 938-950.（In Chinese）

[4]SANDHOLM T. Agents in electronic commerce： Component technologies for automated negotiation and coalition formation[J]. Autonomous Agents and MultiAgent Systems， 2000， 3（1）： 73-96.

[5]VOICE T， RAMCHURN S D， JENNINGS N R. On coalition formation with sparse synergies[C]//Proceedings of the 11th International Conference on Autonomous Agents and Multiagent SystemsVolume 1. International Foundation for Autonomous Agents and Multiagent Systems.New York：ACM，2012： 223-230.

[6]LIEMHETCHARAT S， VELOSO M. Modeling and learning synergy for team formation with heterogeneous agents[C]//Proceedings of the 11th International Conference on Autonomous Agents and Multiagent SystemsVolume 1. International Foundation for Autonomous Agents and Multiagent Systems.New York：ACM， 2012： 365-374.

[7]SOH L，TSATSOULIS C. Allocation algorithms in dynamic negotiationbased coalition formation[C]//Proc of the 1st Int Conf on Autonomous Agents and Multiagent Systems. New York：ACM， 2002：16-23.

[8]SOH L K.Negotiationbased coalition formation model for agents with incomplete information and time constraints[R]. Lincoln， USA：Department of Computer Science and Engineering， University of NebraskaLincoln， 2002.

[9]胡军， 邓磊， 宋颖辉. 面向议题关联的双边多议题协商模型研究[J]. 湖南大学学报：自然科学版， 2011， 38（12）：66-71.

HU Jun， DENG Lei， SONG Yinghui. Research on interdependenceoriented bilateral multiissue negotiation model[J]. Journal of Hunan University ：Natural Sciences， 2011， 38（12）：66-71. （In Chinese）

[10]RAMCHURN Sarvapali D，GERDING Enrico，JENNINGS N R，et al.Practical distributed coalition formation via heuristic negotiation in social networks[C]//Fifth International Workshop on Optimisation in Multiagent Systems（OPTMAS）.Valencia ES，2012：205.

[11]汪小帆， 李翔， 陈关荣. 复杂网络理论及其应用[M]. 北京：清华大学出版社， 2006：5-22.

WANG Xiaofan， LI Xiang， CHEN Guanrong. Theory and application of the complex network[M]. Beijing：Tsinghua Unversity Press， 2006：5-22.（In Chinese）

[12]ABRAHAM A， HASSANIEN A E， SNASEL V. Computational social network analysis： trends， tools and research advances[M].Berlin：Springer Press， 2009：205.