小世界網絡拓撲下的多Ａｇｅｎｔ網絡傳輸有效性和限定性滿足問題研究

摘 要：首先探討了小世界拓撲下的多Agent網絡的有效性、可靠性，相比于規則Agent網絡和完全隨機Agent網絡，小世界網絡拓撲具有更高的有效性和可靠性；其次，對于Agent網絡的限定滿足問題的解決，規則Agent網絡比小世界Agent網絡和完全隨機Agent網絡更優。

關鍵詞：小世界網絡； Agent網絡； 傳輸有效性； 限定性滿足問題

中圖法分類號：TP393文獻標識碼：A

文章編號：1001—3695(2007)02—0066—03

Agent網絡是以網絡節點為Agent、邊為Agent之間的相互關系所構成的一個網絡圖。許多研究人員是通過分布式人工智能(DAI)來研究自治Agent系統的協作性和有效性，從網絡拓撲方面研究多Agent系統特性還不多見。近年來出現的小世界(Small World)網絡拓撲[1，2，6，7，9]，對于保持系統的高可靠性和低網絡組織代價，提高系統性能有重要作用。另一方面，隨機連接拓撲要提高系統性能，就必須付出高的網絡代價和低的傳輸可靠性；規則網絡拓撲則必須付出低系統性能、低網絡組織代價和高可靠性。然而，對于近年來出現的網絡限定性滿足問題，規則網絡拓撲優于小世界網絡拓撲和隨機網絡拓撲。

1 單Agent動態

在多Agent網絡中的單個Agent均能處理、傳輸網絡信息。描述一個Agent可以用它的信息感知、活動、信任Agent節點、信息傳送目標等，在這里不涉及Agent內部的物理結構。假設網絡是由具有不同特性的n個自治Agent的相互通信組成的，每一個Agent的形式動態可表示為[8]

2 網絡拓撲

網絡拓撲是反映Agent網絡連通性的一種幾何屬性，隨著Watts和Strogatz于1998年提出的一種小世界網絡，盡管網絡規模很大，但在網絡任意兩節點之間的平均最短路徑長度小得驚人(相對于網絡規模大小n，一般與log n同階)，產生了小世界現象。人們逐漸發現小世界效應現象可以出現在通信網絡、生物的神經網絡、冪率網絡、科技工作者的合作關系網絡，從而可以用小世界模型來分析這些網絡，對于Agent網絡也不例外。小世界網絡是基于規則的網格和節點的重連概率p，每一節點以概率p和不同的目標節點重連而逐步演化生成。若p=0，則初始的網格是不變的；隨著p的增大，網絡隨機性增大，網絡變得無序，直至p=1時為隨機重連網絡；在0＜p＜1的很大一個范圍內，所得到的網絡就是小世界網絡。小世界網絡具有較小的平均網絡節點距離和較大的分簇系數，它是介于規則網絡和隨機網絡之間，可看成是兩者的綜合，那么網絡拓撲性質就與規則網絡和隨機網絡既有區別又有聯系。小世界網絡的節點度分布類似于隨機網絡，其峰值出現在網絡的平均節點度值處以及按指數率衰減等。

通常意義上講，網絡拓撲主要包含兩個元素：系統節點元素和連接節點的邊；結構參數包含網絡節點的平均距離、分簇聚類系數、節點度分布及其分布指數、度相關指數等。

3 多Agent網絡傳輸有效性、可靠性和限定性滿足問題

假定在具有n個Agent的網絡Ω中，每一個Agent都能和與之直接連接的Agent產生相互作用，每一對相連接的Agent之間的信息傳輸存在傳輸可靠性問題。傳輸可靠性反映了數據丟包率的問題。假定在一對相連接的Agent鏈路之間發生的信息傳輸概率為p_i，_i，Agent鏈路之間連接時間越長，則p_i， _j越小，令

其中τ為[0，1]上的隨機變量。

對于不同的網絡拓撲，其網絡組織代價O(Ω，p)是不同的，并依賴于邊的隨機重連概率。對于規則網絡，由于所有存在鏈路的Agent對之間情況都是相同的，那么網絡組織代價就可以通過計算這些鏈路上的信息傳輸代價而得到，由規則網絡通過邊的隨機重連而過渡到隨機網絡的過程中，網絡組織代價也在隨之變化。另外，在Agent間的信息傳輸中的全局傳輸可靠性定義為

其中Tmax表示的是信息流傳導至Ω中的其他Agent處所花費的最大時間，則G(p)綜合考慮了Agent網絡組織代價和傳輸有效性。圖2顯示了G(p)與重連概率p的關系。

在1 000個Agent的網絡中，基于隨機重連概率p的平均路徑長度L(p)和分簇系數C(p)分別與L(0)和C(0)的比值，其中L(0)和C(0)分別是規則網絡的情形如圖1所示。在1 000個Agent的網絡中，基于隨機重連概率p時的G(p)如圖2所示。

在小世界網絡拓撲下具有較大的Eg和El，所以也有研究者將具有較大的Eg和El的網絡稱為小世界網絡。文獻[3，4]的研究表明，在所有的網絡拓撲中，小世界網絡的信息傳輸最有效，但限定性滿足問題的有效性例外。然而在多Agent網絡下解決限定性滿足問題，對于一個給定的限定性滿足問題，每一個Agent代表該限定性問題中的一個子句(Clause)，并且要使得該子句為True，那么基于這種Agent子句表示，結果顯示多Agent網絡呈現出小世界拓撲特征。

一般來說，在多Agent網絡下解決限定性滿足問題，Agents之間都有限定性問題，那么問題的解決就是Agents的相互協作和折中過程。如果在一定的Agents狀態下，所有的限定性問題都被滿足，我們就認為在多Agent網絡下限定性滿足問題得到了解決。

4 多Agent網絡限定性問題的生成及其在小世界拓撲下的有效性

圖3為限定性滿足問題的示例。Agents a1，a2，a3，a4分別代表四個變量A，B，C，D，且有四個限定性問題如圖中線段旁邊所示。①與Agents相對應的四個變量被隨機地賦值A=0，B=0，C=1，D=1，多Agent系統尋求滿足限定性問題的Agents狀態。首先發現兩個限定性條件未被滿足，即Bv—C和Av—D，這種情況下，Agents通過改變其自身的值來尋求滿足要求，從而在Agents相互協作的機制下，Agent a2所對應的變量B由1變為0，從而進入下一步。②Agent a1發現限定性條件Av—D未滿足，并使變量A從0變為1并進入下一步。③Agents間的所有限定性條件都得到滿足，這時限定性滿足問題得到了解決。

驗證限定性問題的有效性和可靠性，通過算法的三個步驟完成：

(1)從一個規則Agent網絡開始，基于不同的隨機重連概率p，產生一組小世界拓撲的Agent網絡Ωi(i=1，2，…)。

(2)基于每一個小世界拓撲的Agent網絡，利用上面提到的方法生成若干個限定性滿足問題。

(3)對于每一個限定性滿足問題，運行GLS(Greedy Local Search)算法[3]，并按下列方法記錄和計算Agent節點ik及與其相對應的隨機變量值vik。隨機變量值的改變導致限定性條件數目的增長，取增長數目最大的隨機變量值所對應的Agent節點；若不存在這樣的Agent節點，則隨機挑選一個Agent節點，并令一個[0，1]上和原值不同的隨機變量與之重新對應。

5 仿真驗證

首先通過GLS算法，看看已滿足的限制性條件和總的限制性條件的比率μ的變化情況。圖4為已滿足的限制性條件和總的限制性條件的比率μ隨重連概率p變化情況的比較(四組網絡)。其中N為網絡Agent節點數、k為平均Agent節點度；Ωi為算法步驟（1）中產生的一組Agent網絡，分別有340，240，140，100個。從圖4可以看出，隨著隨機重連概率p的增大，比率是遞減的，特別是當p進入具有小世界拓撲特征區域時，比率遞減加速。這說明在具有小世界拓撲的Agent網絡下，使得在GLS算法下限制性條件的滿足將變得更加困難。

其次，對于每一個限定性滿足問題和不同的隨機重連概率p，運行GLS算法直至85%的限定性條件得到滿足為止。計算算法運行的步數Γ(p)，Γ(0)為完全規則網絡下的算法運行步數。Γ(p)/Γ(0)的結果如圖5所示。

從圖5中可以看出，當隨機重連概率p從0增加到 0.5時，滿足一定數量的限定性條件的算法步數幾乎是單調增加的，這意味著小世界拓撲特征越明顯的Agent網絡，所產生的限定性滿足問題就越難得到解決。當p＞0.5時，解決問題的困難程度就變得不可預測。

圖5運行GLS算法直至85%的限定性條件得到滿足為止的算法運行步數Γ(p)與完全規則網絡下的算法運行步數Γ(0)的比值和隨機重連概率p的關系。

6 結論

小世界拓撲特征近年來得到研究人員的極大關注，對于多Agent網絡，在小世界拓撲下的信息傳輸有效性比在規則網絡或隨機網絡拓撲下更高。但小世界拓撲也有它的缺點，即限定性滿足問題的有效解決，不如規則網絡拓撲高；從仿真和驗證結果來看，當隨機重連概率p∈(0，0.01)時，對于限定性滿足問題的有效解決，小世界拓撲也不如完全隨機網絡拓撲；當p∈(0.1，0.5)時，則優于完全隨機網絡；當p＞0.5時，結果不可預測。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。