GRID[16]路由協(xié)議是一種典型的基 L4931ABD33于地理柵格的分層網(wǎng)絡路由協(xié)議，其開始是為移動自組織網(wǎng)絡而設計的路由協(xié)議，根據(jù)地理柵格構建分層網(wǎng)絡并實現(xiàn)路由。其基本思想是將整個網(wǎng)絡劃分成一個個正方形的小區(qū)域，在同一個區(qū)域內(nèi)，所有節(jié)點的標號都是用柵格號來標識。如圖3-14所示，有一個4x5的柵格域，每個柵格的邊長都相同且為r。則節(jié)點通過每個柵格內(nèi)的簇頭節(jié)點構成整個網(wǎng)絡的骨干網(wǎng)絡完成數(shù)據(jù)通信。每個柵格都有自己的編號，如(1，2)、(2，4)等，柵格中的所有節(jié)點都共享這個柵格編號，柵格內(nèi)的簇頭節(jié)點負責柵格中的分組轉發(fā)。GRID路由協(xié)議主要包括3個階段：柵格劃分、路由建立與路由維護。
    柵格劃分階段主要包括了兩個部分，即節(jié)點屬于哪個柵格與簇頭的選取。柵格的大小，即邊長r的選取對于路由的性能影響較大。若柵格邊長，．選取較大，則可能導致各個柵格的簇頭芾點之間相距較遠而導致無法通信；若，較小，則可能在某一個柵格內(nèi)，導致沒有節(jié)點存在，使得路由無法選取。通常情況下，，的選取值為幺旁，其中d為兩節(jié)點之間的通信距離，那么為什么選取這個值呢？如圖3-15所示，任意兩個相鄰的柵格之間，若要使得在兩柵格中任意地理位置的兩簇頭都能夠正常通信，則邊長r與通信半徑d滿足如下關系：(2r)² +r²= d²，因此解得R的值。

    每個柵格內(nèi)選取簇頭的原則是按照停留在柵格內(nèi)時間最長的節(jié)點作為簇頭節(jié)點，一旦某節(jié)點擔當了簇頭節(jié)點，只有其離開該柵格時才會進行新一輪簇頭的選舉。節(jié)點以自己和歸屬柵格中心點的距離設定定時器，定時器到時，選舉自己成為簇頭，每周期性地發(fā)送通告消息，其他節(jié)點接收到消息后，則加入該柵格。如果同時有多個節(jié)點競爭簇頭，在收到其他簇頭的通告消息后，距離柵格中心較遠的簇頭放棄簇頭地位，保證柵格中的簇頭個數(shù)不超過一個。