TopDisc（Topology Discovery）算法是基於最小支配集理論的經典算法。它首先由初始節點發出拓撲發現請求，通過廣播該訊息來確定網路中的骨幹節點(distinguished nodes)，並結合這些骨幹節點的鄰居節點的信息形成網路拓撲的近似拓撲。在這個近似拓撲形成之後，為了減少算法本身引起的網路通信量，只有骨幹節點才對初始節點的拓撲發現請求作出相應的反應。
基本介紹
- 中文名：TopDisc算法
- 外文名：Topology Discovery算法
為了確定網路中的骨幹節點，TopDisc算法採用的是貪贊算法。具體地講，TopDisc提出了兩種類似的方法：三色法和四色法。
在三色法中，節點可以處於三種不同的狀態。在TopDisc 算法中，分別用白色、黑色、灰色表示三種節點：(1) 白色表示尚未被發現的節點，或者說是沒有接收到任何拓撲發現請求的節點； (2) 黑色表示骨幹節點(簇頭節點)，負責相應地拓撲發現請求；(3) 灰色表示普通節點，至少被一個標記為黑色的節點覆蓋，即黑色節點的鄰居節點。
在初始階段，所有節點都被標記為白色，算法由一個初始節點發起，算法結束後所有節點都將被標記為黑色或者灰色(前提假設整個網路拓撲是連通的)。
TopDisc 採用兩種啟發方法來使得每個新的黑色節點都儘可能多地覆蓋還沒有被覆蓋的節點：一種是節點顏色標記方法； 另一種是節點轉發拓撲發現請求時，將會故意延時一段時間，好時間的長度反比於該節點與傳送拓外發現請求到該節點的節點之間的距高。
