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出发无有向路径与其他节点连通。