CGSR

基本介紹

• 中文名：群首網關交換路由
• 外文名：ClusterheadGateway Switch Routing
• 外語縮寫：CGSR
• 類型：路由協定

基本思想

在CGSR使用的網路模型中，網路被劃分為重疊的群，在每個群中選出一個群首，管理群中的其他成員，控制對信道的訪問，進行路由及頻寬分配等。所有在群首通信範圍一跳內的節點都屬於該群，在兩個以上群首通信範圍一跳內的節點稱為網關節點，兩個群首不能直接通信，必須通過網關節點。這樣，一個群中就有3類節點：一個群首、一個或多個網關節點及零個或多個普通節點。CGSR路由協定與DSDV協定的不同之處在於：只有群首和網關節點才轉發分組，減少了路由中涉及的節點個數

關鍵技術問題

為了形成CGSR協定的分群結構，最重要的是解決群首的選擇問題。

1、 兩種分散式群首選舉算法：最小ID算法和最高連線度算法

兩種算法都同時允許集中式和分散式兩種實現方法。當使用集中式的實現方法時，具有最大或者最小的標識號的節點或者是鄰接節點數量最多的節點會被選為群首，以此建立的群包括該節點和距離它只有一跳的鄰接節點。已經被處理過的節點不再被考慮，而這個選擇群首和形成群的過程會不斷重複下去，直到網路中所有的節點都被包含在某個群中為止。

使用分散式的實現時，如果節點與它的鄰接節點相比具有最小或者最大的標識號時，就選擇自己作為群首。否則，就選擇與自己具有直接連通關係的節點中具有最小或者最大標識號的節點作為群首，重複這個過程直到節點的標識號已經在鄰接節點中具有最大或者最小的標識號為止。若使用基於連通性的分群算法的分散式實現，在所有未覆蓋的節點中連線有最多節點的那個節點就會被選作群首，而所有尚未選擇自己的群首的節點都被視為未覆蓋的節點。一旦某個節點已經選擇了自己的群首，那么它自己將不能再被選作群首。

2、 CGSR的群首選舉算法最少分群改變算法（LCC，Least Cluster Change）

分群算法最重要的一個衡量條件是群首的穩定性，如果群首交替十分頻繁，會引起依賴於它的調度和分配算法性能大大下降。CGSR的群首選舉算法LCC在群首的穩定性方面有很大提高，只在以下兩種情況下才修改群首：一是當兩個群首進入兩者的共同傳輸範圍，需要進行群的合併；二是當一個節點與所有的群都失去聯繫時，需要生成新的群。在這兩種情況下，都需要選舉新的群首。

CGSR的群首選舉算法如下：

（1） 開始使用最小ID算法或最高連線度算法，建立初始的群。

（2） 當群i中的一個非群首節點進入群j，群i和群j的群首都不變（只有群成員改變）。

（3） 當一個非群首節點移除其所在的群並且沒有進入已有的任何群時，它成為一個新的群首，形成一個新的群。

（4） 當群首C(i)從群i移入群j，便需要從群j的群首C(j)和C(i)中，根據最小ID算法、最高連線度算法或其他好的優先算法，決定哪個群首放棄群首的地位。

（5） 所有與群首分離的節點將重新根據最小ID算法或最高連線度算法，選擇新的群首。

路由協定描述

CGSR路由協定的形成經歷了一個發展過程：首先，對基本的DSDV協定進行修改形成了DSCR協定，利用群首來實現節點間的路由。在該方式下，每個節點都有一張群成員表和一張路由表，前者存儲網路中每個節點對應的群首信息，後者給出到達目的節點群首的下一跳地址。如果源節點需要向目的節點傳送數據，它首先根據自己存儲的群成員表獲得目的節點的群首，然後將數據分組以最短路徑轉發至目的節點的群首，再由目的節點群首將數據分組路由至目的節點。之後，CGSR協定在DSCR協定的基礎上又進行了改進，它僅使用群首-網關進行路由。在該方式下，如果源節點需要向目的節點傳送數據，又包括以下兩種情況：目的節點與源節點不在統一個群內；目的節點與源節點處於同一個群內。對於第一種情況，源節點首先將數據分組送給自己的群首，然後再按照群首-網關-群首的方式路由至目的節點的群首，最後由目的節點的群首將數據分組路由給目的節點。

在CGSR協定下，數據分組的轉發方式為：群首-網關-群首-網關………-網關-群首。圖1-1顯示的為節點1傳送一個分組至節點12的過程：分組首先被路由至1所在的群的群首2，節點2把分組路由至網關4,4再把分組路由至鄰接群的群首5，如此下去，直至到達目的節點所在的群首11，由11最後把分組路由至目的節點12。
　　

圖1-1從節點1到節點11的CGSR路由實例

總結

CGSR協定是對基本DSDV路由協定的擴展，是一種基於分群的層次路由。它使用LCC群首選舉算法來維護分群結構的穩定性，通過交替使用群首-網關序列來高效地傳遞數據分組，是一種可擴展的先應式自組網路由協定。由於限定分組的傳輸必須經過群首網關序列，可能產生非最優路徑。