面向社交網絡基于協作度協商的聯盟形成機制

胡 軍，張振興，鄒 立

(1.湖南大學 信息科學與工程學院, 湖南 長沙 410082；2. 桂林電子科技大學 廣西可信軟件重點實驗室,廣西 桂林 541004；3.南京大學 計算機軟件新技術國家重點實驗室, 江蘇 南京 210093；4.湖南大學 嵌入式與網絡計算湖南省重點實驗室，湖南 長沙 410082)

面向社交網絡基于協作度協商的聯盟形成機制

胡 軍1,4?，張振興1,2，鄒 立1,3

(1.湖南大學 信息科學與工程學院, 湖南 長沙 410082；2. 桂林電子科技大學 廣西可信軟件重點實驗室,廣西 桂林 541004；3.南京大學 計算機軟件新技術國家重點實驗室, 江蘇 南京 210093；4.湖南大學 嵌入式與網絡計算湖南省重點實驗室，湖南 長沙 410082)

分布式多Agent構成的社交網絡通常表現出不同的特征，針對不同的社交網絡和多Agent本身的異質性，提出了一種面向社交網絡的基于協作度協商聯盟形成機制.該機制依托多Agent構成的社交網絡環境，建立面向分布式環境的分布式協商協議，并設計一種考慮到社交網絡特征和Agent異質性的基于協作度的協商策略，采用分布式自動協商方式形成聯盟.通過對全連通網絡、層次網路和小世界網絡的仿真實驗結果表明，該機制能夠有效地實現分布式環境下的聯盟形成，并且在反應大多數實際應用環境的小世界社交網絡中表現出相對較好的性能.

多Agent系統；聯盟形成；分布式自動協商；社交網絡；協作度

形成聯盟是多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連通性比較差，葉子節點只有一個直接鄰居.

(a)

(b)

(c)

圖2 隨機樹社交網絡

1.2.3 小世界網絡

小世界網絡一類特殊的復雜網絡結構，在這種網絡中大部份的節點彼此并不相連，但絕大部份節點之間經過少數幾步就可到達.這反映的是現實世界中陌生人可以通過彼此共同認識的人而連接的現象.

小世界網絡的判定準則有兩個，分別是特征路徑長度和高集聚系數.網絡的特征路徑長度是指在它的圖表示中，兩個節點的路徑長度的平均值(這里路徑長度指兩節點間最短路徑的長度).許多復雜網絡盡管節點數目巨大，但節點之間的特征路徑長度則非常小[11].集聚系數則是用來描述“抱團”現象的，也就是“你朋友之間相互認識的程度”.從數學的角度上來說，一個節點的集聚系數等于與它相連的節點中相互連接的點對數與總點對數的比值.高集聚系數實際上保證了較小的特征路徑長度[12].圖3是由100個Agent形成的小世界網絡，其中最大度數為10，平均度數為5.8.由圖可以看出，小世界網絡有明顯的“抱團”現象，并且有邊將這些“團”連接起來.

圖3 小世界型社交網絡

2 分布式協商模型

本文是使用分布式協商的方法形成聯盟，所以首先介紹分布式協商的形式化模型基礎；接下來敘述分布式協商要素；最后給出分布式協商協議.

設Agenti擁有一個特定的資源ri，ri描述的是這個Agent執行任務時可以利用的資源；把Agenti的直接鄰居所擁有的資源稱為Agenti的備用資源.當Agenti無法單獨完成某些特定的任務時，Agenti可以使用自己的備用資源，通過與其直接鄰居形成聯盟來完成.Agent集合中的各個Agent可能形成的聯盟是C1,C2,…,Cn∈2I，Ci中每個成員Agenti擁有ri所描述的資源，這樣聯盟Ci擁有的資源描述為rC∈∏i∈Cri.形成聯盟Ci后可以得到一個整體的效用V(rC)∈Z+，這個效用代表的是聯盟在系統中產生的效用值；通過協商，每一個成員Agent可以在這個效用值中劃分到一份效用值vi∈Z+，易見∑i∈C=vi=V(rC).并且整體效用可用式(2)計算：

V(rC)=|C|∑i∈Cri

(2)

可見，形成的聯盟越大，獲得的聯盟效用越大.

2.1 協商要素

分布式協商中的協商要素包括協商提議、協商區間和協商決策函數，這些都是構建分布式協商的前提.

2.1.1 協商提議

Agenti可以通過發送提議的方式向I(i)合適的Agentj發出聯盟邀請，協商提議定義為式(3)所示：

(3)

2.1.2 協商區間

所謂協商區間就是協商雙方的協商的效用分配的波動區間，即最小效用和最大效用.假如Agenti已經收到了Agentk∈Ι(i)∪{i},k≠j的提議(rC,vi)，如式(4)所示的等式表示對是Agentj加入該聯盟后增加的效用：

δV(rC,rj)=V(rC,rj)-V(rC)

(4)

因此Agenti能夠得到的最大效用如式(5)所示，其中vi是Agentj加入聯盟之前Agenti所獲得的效用分配，δV(rC,rj) 由式(4)求得，即Agenti很自私的全部占有Agentj加入增加的效用.

(5)

要衡量Agenti的最小效用就要計算當前Agenti的最好的效用值，Agenti將到目前為止可以加入的最優聯盟的提議定義為o*=maxo∈commitsetiv(o)，其中，commitseti表示Agenti當前可以加入的聯盟提議集合.因此Agenti的最小效用如式(6)所示，即協商區間的最小值不能小于Agenti到目前為止取得的最大效用：

vmin(rC,rj)=max (0,vi(o*))

(6)

2.1.3 協商決策函數

協商決策函數是Agent在收到協商提議后的按照最大化自身利益的原則決策自身行為的過程.

(7)

綜上，Agent的決策函數定義如式(8)所示，即：

(8)

可見一個Agent進行協商決策的過程就是產生不同類型的提議，有：接收提議、反提議、新建提議等.

因此，Agenti可以執行的決策有：

根據協商策略就當前收到的提議產生反提議；

發送一個提議給當前可加入的最優聯盟的邀請者Agent，加入該聯盟；

2.2 分布式協商協議

協商協議通過對分布式協商通信過程的規定和Agent協商狀態的定義，來實現協商過程的收斂性和避免死鎖.

協商中的Agentj的狀態定義為：sj={DONE,WAIT(i),SLEEP}.其中，DONE狀態表示Agentj已接受某個協商提議，該Agent的協商已完成.WAIT(i)狀態表示Agentj已向Agenti發送了協商提議，等待i的回復.SLEEP狀態表示Agentj的初始狀態，等待其他Agent發送提議過來.

具體協議流程如圖4所示，開始形成聯盟前，所有的Agent都處于SLEEP狀態，當Agentj發送提議給Agenti∈I(j)后，邀請者Agentj將sj設置為WAIT(i)狀態，此時I(j)/{i}中所有的Agent不能再發送新的提議給Agentj，避免死鎖發生.此時唯一能和Agentj通信的只有Agenti，Agenti將發送給Agentj反提議、接受Agenti或者拒絕提議.如果Agenti接受了Agentj，Agenti將si設置為DONE.此時，Agenti將其自身的狀態通知給正在等待它回應的主體.如果該提議包含該鄰居，它發送接受提議消息給該鄰居，如Agentj，對其他主體發送拒絕消息，之后Agenti將不能再收到任何提議.同時Agentj將Agenti加入保證可以加入的聯盟集commitsetj中，Agentj將sj設置為SLEEP，表示現在Agentj可以接收新的提議；如果Agenti發送反提議給Agentj，Agentj將sj設置為SLEEP，Agenti自己將si設置為WAIT(i)；如果Agenti發送拒絕提議給Agentj，則Agentj將sj設置為SLEEP.本協議是通過避免產生提議環和避免提議沖突，來實現協商過程的不死鎖性的.具體來說，通過下列通信的規則來實現：

圖4 分布式協商協議中Agent狀態遷移圖

3 基于協作度的協商策略

3.1 協商策略函數

本文提出基于協作度的協商策略CBNT(CooperationDegree-BasedNegotiationTactic)，協商策略函數如式(9)所示指數函數族來逐步產生讓步后的新提議.

(9)

3.2 協作度

本文引入了協作度的概念，來描述Agent的協作資源和歷史協作狀況的不同，從而體現在不同社交網絡結構的差異性，進而通過協作度對協商態度值產生影響，來實現不同策略的協商過程.

定義1Agentj相對Agenti的歷史協作度：

(10)

其中，分母是Agenti和Agentj所有歷史交互提議的次數，分子是Agenti和Agentj所有歷史交互協商成功的次數.反應歷史協商過程中Agentj接受Agenti提議的幾率，稱為Agentj相對Agenti的歷史協作度，反應的是Agent的協作態度.

定義2 Agentj相對Agenti的現在協作度：

(11)

分子是Agenti的鄰居Agentj擁有的備用資源數量，分母是Agenti所有的鄰居擁有的備用資源總和，當Agentj相對Agenti的其他鄰居而言擁有更多的備用資源時，我們認為Agentj相對Agenti的現在協作度較高，反應的是Agent的協作資源.

定義3 Agentj相對Agenti的協作度：

cij=a×cij-past+b×cij-now∈[0,1]

(12)

Agentj相對Agenti的協作度是綜合考慮定義1和定義2中的歷史協作度和現在協作度的，式中a+b=1恒成立.a和b的選擇反應的是聯盟形成中更注重歷史表現還是現在的資源占有情況.

基于上述協作度的定義，Agenti對Agentj的協商態度值采用式(13)計算：

(13)

4 SOCNCF機制

SOCNCF機制在分布式協商模型的基礎上使用基于協作度的協商策略進行聯盟形成，分布式協商模型保證算法的收斂性，基于協作度的協商策略保證算法的高效性.SOCNCF機制實現算法如算法1所示.算法開始階段會產生模擬分布式環境的不同類型的社交網絡，同時對Agent的協作度初始化；每一次聯盟形成過程開始前會利用前一次聯盟形成計算出的協作度cooperationTemp作為本輪的初始協作度；然后開始多輪協商進行聯盟形成，在遵循社交網絡和分布式協商協議的前提下得到協商決策函數Decision；根據得到的不同Decision對用來計算Agent之間協作度的相關參數進行計算和對Agent的狀態進行更新，一遍聯盟形成后根據Agent之間協作度的相關參數計算協作度并保存至cooperationTemp.然后開始下一次聯盟形成過程，直至MAXHISTORYTIMES次后算法結束.

算法1 SOCNCFAlgorithm()

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社交網絡環境下聯盟形成效果對比

表2 第2種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,etal. Anytime coalition structure generation in multi-agent systems with positive or negative externalities[J]. Artificial Intelligence, 2012, 186: 95-122.

[2] 李少芳, 胡山立, 石純一. 一種基于勢結構分組思想的任一時間聯盟結構生成[J]. 計算機研究與發展, 2012, 48(11): 2047-2054.

LI Shao-fang, HU Shan-li, SHI Chun-yi. 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 Jing-lei, ZHANG Wei, TONG Xiang-rong,etal. 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 Multi-Agent 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 Systems-Volume 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 Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems．New York:ACM, 2012: 365-374.

[7] SOH L，TSATSOULIS C. Allocation algorithms in dynamic negotiation-based 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.Negotiation-based coalition formation model for agents with incomplete information and time constraints[R]. Lincoln, USA:Department of Computer Science and Engineering, University of Nebraska-Lincoln, 2002.

[9] 胡軍, 鄧磊, 宋穎輝. 面向議題關聯的雙邊多議題協商模型研究[J]. 湖南大學學報:自然科學版, 2011, 38(12)：66-71.

HU Jun, DENG Lei, SONG Ying-hui. Research on interdependence-oriented bilateral multi-issue 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,etal.Practical distributed coalition formation via heuristic negotiation in social networks[C]//Fifth International Workshop on Optimisation in Multi-agent Systems(OPTMAS).Valencia ES,2012:205.

[11]汪小帆, 李翔, 陳關榮. 復雜網絡理論及其應用[M]. 北京:清華大學出版社, 2006:5-22.

WANG Xiao-fan, LI Xiang, CHEN Guan-rong. 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.

Social Networks Oriented Collaboration Degree Based Negotiation Coalition Formation Mechanism

HU Jun1,4?, ZHANG Zhen-xing1,2, ZOU Li1,3

(1.College of Computer Science and Electronic Engineering, Hunan Univ, Changsha, Hunan 410082,China；2. Guangxi Key Laboratory of Trusted Software, Guilin Univ of Electronic Technology, Guilin, Guangxi 541004,China；3.State Key Laboratory for Novel Software Technology, Nanjing Univ, Nanjing, Jiangsu 210093,China；4. Key Laboratory for Embedded and Network Computing of Hunan Province,Huna Univ, Changsha, Hunan 410082,China)

The social networks formed by distributed multi-Agent always show different characteristics. This paper proposed a social networks oriented collaboration degree based negotiation coalition formation mechanism aiming at the heterogeneity of different social networks and multi-Agent. This mechanism established a distributed negotiation protocol and designed a collaboration degree based negotiation tactic, which considered the characteristics of the social networks and the heterogeneity of the Agent. The experiment results in fully-connected network, hierarchical network and small world network have shown that this mechanism can form coalition in distributed environment effectively and show a better performance than other social networks in responding to small world networks in practical environment.

multi Agent systems; coalition formation; distributed auto-negotiation; social networking; collaboration degree

1674-2974(2015)02-0100-09

2014-01-16

國家自然科學基金資助項目(60773208),National Natural Science Foundation of China(60773208); 湖南省自然科學基金資助項目(11JJ3065); 廣西可信軟件重點實驗室研究資助項目(kx201333);計算機軟件新技術國家重點實驗室研究資助項目( KFKT2013B14)

胡 軍(1971-)，男，湖南長沙人，湖南大學副教授，博士?通訊聯系人，E-mail:hujun_111@hnu.edu.cn

TP311

A