|
TOPDISC算法是基于最小支配理論的經典算法，它首先由初始節點發出拓撲發現請求，通過廣播該消息來確定網絡中的骨干節點，并結合這些骨干節點的鄰居節點的信息形成網絡拓撲的近似拓撲。在這個近似拓撲形成之后，為了減少算法本身引起的網絡通信量，只有骨干節點才對初始節點的拓撲發現請求作出相應的響應。 為了確定網絡中的骨干節點，光電開關的TOPDISC算法采用的是貪婪算法。具體地，TOPDISC提出了兩種類似的方法：三色法和四色法。 在三色算法中，節點可以處于三種不同狀態，分別用白色、黑色、灰色三種顏色表示： 1、白色，尚未被發現的節點，或者說是沒有接收到任何拓撲發現請求的節點; 2、黑色，骨干節點(簇頭節點)，負責相應拓撲發現請求; 3、灰色，普通節點，至少被一個標記為黑色的節點覆蓋，即黑色節點的鄰居節點。 在初始階段，光電開關傳感器的所有節點都被標記為白色，算法由一個初始節點發起，算法結束后所有節點都將被標記為黑色或者灰色(前提假設整個網絡拓撲是連通的)。光電開關的TOPDISC采用兩種啟發方法來使得每個新的黑色節點都盡可能多地覆蓋還沒有被覆蓋的節點：一種是節點顏色標記方法：另一種是節點轉發拓撲發現請求時將會故意延時一段時間，延時時間的長度反比于該節點與發送拓撲發現請求到該節點的節瞇之間的距離。三色法的詳細過程描述如下： 1、初始節點被標注記為黑色，并向網絡廣播拓撲發現請求; 2、當白色節瞇收到來自黑色節點的拓撲發現請求時，將被標記為灰色，并在延時時間TWB后繼續廣播拓撲發現請求，TWB反比于它與黑色節點之間的距離; 3、當白色節點收到來自灰色節點的拓撲發現請求時，將在等待時間TWC后標記為黑色，但如果在等待周期又收到來自黑色節點的拓撲發現請求則先優先標記為灰色;同樣，等待時間TWG反比于該白色節點與灰色節點之間的距離。不管節點被標記為灰色還是黑色，都將在完成顏色標記后繼續廣播拓撲發現請求; 4、所有已被標記為黑色或者灰色的節點，都將忽略其他節點的拓撲發現請求。 為了使得每個新的黑色節點都盡可能多地覆蓋還沒有被覆蓋的節點，光電開關傳感器的TOPDISC采用了反比于節點之間距離的轉發延時機制。其合理懷簡單解釋為：理想情況下，節點的覆蓋面積和局部的節點部署密度。對于一個正在轉發拓撲發現請求的節點，它所能覆蓋的新的節點(還沒有被任何節點覆蓋的)則正比于它的覆蓋面積與已經覆蓋的面積之差。 |
當前位置：
