2.1　通信網絡

2.1.1　基本概念

如果一個MAS系統中各個體通過通信網絡或者傳感網絡來進行信息交互，則可用有向圖或者無向圖來對信息交換媒介進行描述。假設組成MAS系統的個體數量為n，用圖（ν，ε）表示通信拓撲，其頂點集ν={v_i}，i∈={1，…，n}為非空集合，代表各Agent，邊集ε?ν×ν是由有序頂點對組成的集合，代表各個體之間的鏈接關系。每條邊由兩個不同的頂點（v_i，v_j）所確定，其中v_i稱父節點，v_j稱為子節點。如果（v_i，v_j）∈ε?（v_j，v_i）∈ε，則稱通信圖為無向圖；反之，如果邊（v_i，v_j）為有序的，即（v_i，v_j）∈ε而（v_j，v_i）?ε，則稱之為有向圖。如果（v_i，v_j）∈ε，則稱點v_j為點v_i的一個鄰居，點v_i的所有鄰居的集合用_i來表示。

對于有向圖，有向路徑（directed path）是指邊集按照（v₁，v₂），（v₂，v₃）， …這種有向的形式組成的集合，無向圖中的無向路徑（undirected path）定義與此類似。對于有向圖，如果有向路徑的起始點和終點為同一點，則稱該圖為環形圖。如果有向圖中的每個節點都可以通過有向路徑與其他任意節點連通，則稱為強連通圖。對于無向圖，如果一個無向路徑將所有個體連通，則可稱該無向圖是連通的。根節點是指無父節點而通過有向路徑對其他所有個體具有可達性的節點。如果一個有向路徑除了根節點以外，其他所有節點都只有一個父節點，則稱該有向路徑為有向樹。注意，有向樹不含有環形圖，因為所有個體都以單向的方式與根節點相連。

如果νs?ν，εs?ε∩（νs×νs），則稱圖s（νs，εs）為圖（ν，ε）的附屬圖，如果附屬圖s（νs，εs）為有向樹并且νs=ν，則稱s（ν，εs）為有向圖（ν，ε）的有向衍生樹。如果一個有向衍生樹為圖（ν，ε）的附屬圖，則稱圖（ν，ε）含有一個有向衍生樹，即當且僅當圖（ν，ε）至少有一個節點通過有向衍生樹可以與其他所有節點相連，則稱（ν，ε）含有一個有向衍生樹。下面以圖2-1為例，說明以上概念的具體含義。

圖2-1　有向通信拓撲

在圖2-1中，箭頭指向的個體表示可以從箭頭出發方向的個體得到信息，該有向圖有兩個有向衍生樹，根節點分別為2和3，該有向圖不是強連通圖，因為從節點1，4、5或6出發無有向路徑與其他節點連通。