TopDisc算法是早期成簇算法中的經典算法之一。
TopDisc算法是由Deb等人提出的一種基於圖論中最小支配集問題的經典算法, 利用顏色來描述節點狀態, 解決骨幹網拓撲結構的形成問題。它由網路中一個節點啟動並傳送查詢訊息, 查詢訊息攜帶狀態信息, 隨著訊息的傳播,TopDisc算法依次為每個節點標記顏色, 最後按顏色區分出簇頭節點黑色節點, 並反向尋找查詢訊息, 在簇頭節點之間建立通信鏈路, 簇頭節點管理自己簇內的節點。
基本介紹
- 中文名：成簇算法
- 外文名：topdisc
- 運用：利用顏色來描述節點狀態
- 現實算法：三色算法、四色算法
- 缺點：這種算法建成的網路靈活性不強
算法實現,三色算法,四色算法,算法不足,
算法實現
三色算法
三色算法是分簇算法的具體實現，節點可以處於三種狀態，分別用白、黑和灰三種顏色表示。白色表示未被發現的節點;黑色節點代表簇頭節點;灰色節點表示三色算法所確定的普通節點，即簇成員節點。在骨幹網路形成之前，所有節點都被標記為白色，由一個初始節點發起三色算法。由初始節點啟動傳送用於發現鄰居節點的查詢訊息。查詢訊息攜帶傳送節點的狀態信息。隨著查詢訊息在網路中傳播，三色算法依次為每個節點標記顏色。最後，按照節點顏色區分簇頭和成員節點，簇頭負責管轄自己簇內的節點。算法執行完畢後所有節點都將被標記為黑色或者灰色。
三色算法的具體過程如下:
(1)初始節點將自己標記為黑色，並廣播查詢訊息。
(2)白色節點收到黑色節點的查詢訊息時變為灰色，灰色節點等待一段時間再廣播查詢訊息，等待時間的長度與黑色節點之間的距離成反比。
(3)當白色節點收到一個灰色節點的查詢訊息時，先等待一段時間，等待時間的長度與白色節點到該灰色節點的距離成反比。如果在等待時間內，收到來自黑色節點的查詢訊息，節點立即變成灰色節點，否則節點變為黑色節點。
(4)當節點變為黑色或者灰色後，它將忽略其他節點的查詢訊息。
(5)通過反向查找查詢訊息的傳播路徑形成骨幹網，黑色節點成為簇頭，灰色節點為簇內節點。
註：三色算法需要知道傳送節點和接收節點之間的距離信息，在無線感測器網路中，節點的具體位置信息很難獲得，可以利用接收信號強度值RSSI(Received Signal Strength Indicator)來映射節點之間的
距離。
四色算法
四色算法和三色算法有兩個相同的特點：①利用顏色標記理論找到簇首節點②利用與傳輸距離成反比的延時，確定簇首節點。四色算法主要在三色算法的基礎上加以改進，避免形成的簇重疊，所以根據具體網路的不同，最終的拓撲結構有不同程度的差異。
四色算法主要增加了一個顏色—深灰色。深灰色節點表示該節點至少某一黑色節點的距離為兩級跳，它可能成為黑色節點，但要滿足在等待時間裡沒有收到黑色節點的查詢訊息（既此節點離最近的簇首的距離都較遠，可以成為簇首）。
四色算法的構建過程如下:
1、初始節點將自己標記為黑色，並廣播查詢訊息。
2、白色節點收到黑色節點的查詢訊息時變成灰色，灰色節點等待一段時間再廣播查詢訊息，等待時間的長度與它到黑色節點的距離成反比。
3、當白色節點收集到來自灰色節點的查詢訊息時變為深灰色，然後繼續廣播這個訊息，同時等待一段時間，等待時間的長度與它到灰色節點的距離成反比。深灰色節點在這段時間內沒有收到黑色節點的查詢訊息，它自己成為黑色節點，否則它將成為灰色節點。
4、當白色節點收到來自深灰色節點的查詢訊息時，等待一段時間，等待時間的長度與它到傳送此查詢訊息的深灰色節點的距離成反比。如果在這段時間內又收到來自黑色節點的查詢訊息，節點變成灰色節點，否則節點變成黑色節點。該節點變色後將立即廣播查詢訊息。
5、變為黑色或者灰色的節點不再回響其他節點的查詢訊息。
6、通過反向查找查詢訊息的傳播路徑形成骨幹網，黑色節點成為簇首，
灰色節點成為簇內節點。
算法不足
但是由於這種算法建成的網路靈活性不強，一旦某些節點出現失效，網路必須重新拓撲。尤其特別是無線感測網路固有的能量有限性決定僅僅從距離的角度不能很好選擇出當前的節點做簇頭是最合適的，另外執行算法時，要求各個節點發出信息，並接受其他節點的信息，而且計算兩節點間的距離，所以重複執行算法的開銷過大，因為算法中能量消耗極度不均，會導致算法頻繁重行。另外算法中也沒有考慮節點的剩餘能量問題，使得網路中部分節點因能量消耗過快而功能失效，系統中能量消耗不均衡勢必影響整個系統正常運行，當失效節點數目達到一定時，雖然其他的節點能量還充足，但網路已將無法構成體系，不能完成應有任務，也就是網路生命周期結束。
