GAT算法

GAT 算法是一種依據節點的地理位置進行分簇，並對簇內的節點選擇性地進行休眠的路由算法。其核心思想是：在各數據源到數據目的地之間存在有效通路的前提下，儘量減少參與數據傳輸的節點數，從而減少用於數據包偵聽和校收的能量開銷。它將無線感測器網路劃分成若干個單元格(簇)，各單元格內任意一個節點都可以被選為代表，代替本單元格內所有其他節點完成數據包向相鄰單元格的轉發。被選中的節點成為本單元格的簇頭節點其他節點都進行休眠，不傳送、接收和偵聽數據包。

基本介紹

• 中文名：GAT算法
• 定義：依據節點的地理位置進行分簇，並對簇內的節點選擇性地進行休眠的路由算法

GAT算法通常分為兩個階段：

第一階段為虛擬單元格的劃分。節點根據其位置信息和通信半徑將網路區域劃分為若干個虛擬單元格，並保證相鄰單元格中的任意兩個節點都可以直接通信，假設節點已知整個監測區域的位置信息和本身的位置信息，節點可以通過計算得知自己屬於哪個單元格。

第二階段為虛擬單元格中的簇頭節點的選擇。節點周期性地進入休眠和工作狀態。從休眠狀態喚醒後與本單元內其他節點進行信息交換，以此確定自己是否需要成為簇頭節點，每個節點處於發現、活動以及休眠三種狀態。在網路初始化時，所有節點均處於發現狀態，每個節點通過傳送廣播訊息通告自己的位置和ID等信息，然後每個節點將自身的定時器設定為某個區聞內的隨機值T_d，一旦定時器逾時，節點傳送訊息聲明其進入活動狀態，成為簇頭。節點如果在定時器逾時前收到來自同一單元格內其他節點成為簇頭的聲明，則說明自己在這次簇頭競爭中失敗，從而進入休眠狀態。成為簇頭的節點設定定時器T_a來設定自己處於活動狀態的時間。在T_a逾時前，簇頭節點定期廣播自己處於活動狀態的信息，以抑制其他處於發現狀態的節點進入活動狀態：當T_a逾時後，簇頭節點重新回到發現狀態，處於活動狀態的節點如果發現本單元格出現了更適合成為簇頭的節點，會自動進入休眠狀態。

由於節點處於偵聽狀態時也會消耗很多熱量，所以讓節點處於休眠狀態成為感測器拓撲控制算法中常見的方法，GAT算法的優點是在節點密集型分布的網路中使部分節點處於休眠狀態，節省了網路總能耗。但GAT算法沒有考慮移動節點的存在。實際套用環境中，簇頭節點很容易從一個單元格移動到另一個單元格，從而造成某些單元格內沒有節點轉發數據包，最終造成大量丟失的數據包和重複轉發的數據包，導致了總能耗的增加。