2.1　通信網(wǎng)絡(luò)

2.1.1　基本概念

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

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

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

圖2-1　有向通信拓?fù)?/p>

在圖2-1中，箭頭指向的個體表示可以從箭頭出發(fā)方向的個體得到信息，該有向圖有兩個有向衍生樹，根節(jié)點(diǎn)分別為2和3，該有向圖不是強(qiáng)連通圖，因?yàn)閺墓?jié)點(diǎn)1，4、5或6出發(fā)無有向路徑與其他節(jié)點(diǎn)連通。