4.4.3　基于地理位置信息的路由協議

在前面介紹的無線傳感器網絡路由協議中，節點根據自己的邏輯地址，通過相鄰節點之間的通信探測到所有網絡節點之間的路由，這種方式相對來說比較簡單。隨著現代技術的發展，節點的定位技術已經實現，節點能夠很容易地知道自己所處的位置，利用這些位置數據，節點可以確定自己的路由協議，提高網絡的性能。

同時，在很多應用中，無線傳感器節點需要精確地知道自己所處的位置，例如，在森林防火的時候，消防人員可通過無線傳感器節點精確地知道火災發生的位置。基于地理位置的路由協議假設節點已經知道了自身的地理位置信息和自己所要傳送數據的目的節點所在的位置，從而利用這些已知的地理位置信息來選擇自己的路由策略，高效地將數據從遠端發送到指定目標區域，減小路由選擇過程中所需要的時間和成本代價。

基于地理位置的路由協議一般分為兩類，一類是使用地理位置協助改進其余路由算法，以約束網絡中路由搜索的區域，減少網絡不必要的開銷，主要代表協議為GAF路由算法；另一類路由協議直接利用地理位置來實現自己的路由策略，代表協議是GEAR路由協議。

1. GEAR路由協議

GEAR路由協議是一種典型的基于地理位置來實現自己路由策略的協議，它結合了定向擴散路由算法的思想，在路徑選擇時甚至加入了能量的因素。

1）基本思想

GEAR路由協議根據事件所在區域的地理信息，實現從Sink節點到事件所在地區節點的路徑，這樣就能實現Sink節點向某個特定區域發送數據，避免了泛洪似的全網廣播數據，同時借鑒了SPIN中查詢節點剩余能量值的方法，建立從Sink節點到目標區域的最優路徑。

GEAR路由協議通過周期性地泛洪廣播一個Hello消息來通知相鄰節點自己所在的位置和自己的能量消耗情況，保證鏈路的對稱。

2）關鍵技術

GEAR路由協議在已知事件所在位置信息的情況下，每個節點都知道自己的位置信息和剩余能量值，在自己的緩存中也保存了所有相鄰節點所在的位置信息和剩余能量值。GEAR路由協議要求每個節點維護一個預估路徑代價和一個通過相鄰節點到達目的節點的實際路徑代價。預估代價要使用節點的剩余能量值和發送節點到目的節點的距離來進行計算，而實際代價則是對網絡中圍繞在洞（Hole）周圍的路由所需預估代價的改進。所謂“洞”是指某個節點的周圍沒有任何相鄰節點比它到事件區域的路徑所耗費的路徑代價更大。如果洞現象不發生，那么實際代價將會與預估代價一致。當數據包成功到達目標區域之后，該節點的實際代價就要傳播到上一跳節點，用來調整下一次發送時路由的優化。GEAR路由協議需要解決兩個關鍵性的技術問題：向目標區域傳送查詢消息和查詢消息在事件區域內的傳播。

（1）向目標區域傳送查詢消息。從Sink節點到事件區域傳送數據采用的是貪婪算法。節點在自己所有的相鄰節點中選擇到事件區域內代價最小的節點，以此節點作為自己的下一跳節點，并將自己的路徑代價設置為自己到該節點路徑的代價與該節點到目標區域的代價之和。如上所述，如果出現空“洞”現象，如圖4.6所示，節點C是節點S的相鄰節點中到達目的節點T代價最小的節點，節點G、H、I已經失效，不能夠作為節點C的下一跳節點，因此節點C再也找不到比它距離目標區域節點T代價小的節點，即出現了路由空洞。GEAR路由協議采用的方法是：節點C選取相鄰點中代價最小的節點B作為下一跳節點，并將自己的代價值設置為節點C到節點B的一跳代價值和節點B的代價值之和，同時將這個新代價值通知給節點S。當節點S需要再次轉發查詢命令到節點T時，它就會根據這次的預估代價和實際代價來綜合比較，選擇直接通過節點B來轉發查詢消息，而不是節點C。

（2）查詢消息在事件區域內的傳播。當事件區域接收到查詢消息后，如果采用泛洪的方式將此查詢消息傳送給事件區域內的所有節點，則所需要的代價比較大，尤其在節點密度比較大、規模較為龐大時。GEAR路由協議針對這種情況提出了一種區域內迭代地理轉發的算法，如圖4.7所示。我們假設事件所在區域是一個矩形，該區域收到查詢消息后將該區域劃分為若干個子區域，圖4.7中為4個，并向每一個區域中心轉發此查詢消息，在子區域中每個最靠近區域中心的節點接收該查詢消息后，采用同樣的方法將自己的子區域再劃分為若干個子區域，這樣就形成了一級一級的迭代過程，直到節點發現該子區域內除了自己再也沒有其余的節點時，該查詢消息停止轉發。當所有區域內轉發過程全部停止時，整個迭代過程完成。

GEAR路由協議通過維護預估代價和實際代價，優化了數據傳輸的路徑，采用貪婪算法均衡網絡負載，提高了網絡能效。貪婪算法雖然可以算是局部最優算法，但卻會產生路由空洞。GEAR路由協議采用了一種新方法—局部優化算法解決了這個問題，終端節點由于缺乏足夠的拓撲信息，所以只適用于節點移動性不強的應用中，對移動節點網絡的應用還需要進一步提高。

2. GAF路由算法

GAF（Geographical Adaptive Fidelity）路由算法是一類使用地理位置信息來輔助路由選擇的算法，在該算法中，地理位置不但可以幫助優化路由，還可以用來選擇等價節點。

1）基本思想

一般情況下，節點在發送和接收數據的過程中最為消耗能量，節點在空閑時也需要消耗能量，根據最新的測量結果，節點在空閑、接收數據和發送數據時消耗的能量之比為1：1.2：1.7，節點只要處于啟動狀態就一定要消耗能量，GAF路由算法在地理位置信息的幫助下，關閉一定量的節點，以此來節省能量，提高網絡的性能。

GAF路由算法考慮到無線傳感器網絡中節點的冗余性，在保證網絡正常流通的情況下，適當關閉一些節點可降低能量消耗，延長節點的生存時間，從而延長網絡的生命周期。GAF路由算法利用節點的位置信息，組成一個虛擬的網格，網格中的節點對于數據的轉發來說是等價的，無論選擇哪個節點，所耗費的時間和能量也大致相同，因此這些節點可以通過協商輪流地工作，不工作的節點就被關閉，同時確定好激活的時間，通過周期性輪換，就能夠提高節點的能效。

2）主要問題

在GAF路由算法中，節點的關閉需要考慮以下幾個問題：確定等價節點、輪換協商算法，以及移動節點的自適應算法。

（1）確定等價節點。等價節點，通俗來講就是一個節點可以代替另外一個節點，同時兩者消耗的能量和耗費的代價也大致相同。因此，只要能夠完成數據的轉發功能，使用等價節點中的任何一個節點對網絡性能都不會產生明顯的影響，并且等價節點與源節點和目標節點無關。為了達到這個目的，在GAF路由算法中，協議將整個區域分成若干個虛擬網格，虛擬網格中的任意一個節點都可以與相鄰網格內的節點進行通信，因此對于每個網格中的節點來說，都可以實現路由的連通，這些節點可以說是等價節點。

如圖4.8所示，有三個虛擬網格A、B、C，假設每個虛擬網格都為正方形，邊長為r，根據虛擬網格的要求，節點1和節點5可以和節點2、3、4中任意一個節點通信，因此節點2、3、4是等價節點，任意一個節點都可以實現路由的連通。在這種情況下，節點5需要跟中間區域中的任意一個節點進行通信，就必須保證節點5能和節點2進行通信，因為兩個節點距離最遠，可以看成兩個網格的對角線距離，假設節點的通信最遠距離為R，則要求。

（2）輪換協商算法。在GAF路由協議中，節點有三種狀態：發現狀態、激活狀態和睡眠狀態，圖4.9為GAF路由算法中節點狀態轉換圖，只有處于激活狀態的節點才能夠正常進行數據的通信。

在初始化時，節點處于發現狀態，在這個狀態下，節點打開收發信機，通過交換發現報文來發現相同網格內的其他節點。發現報文的內容包括節點的ID、網格ID、節點的預估激活時間和節點的狀態信息。節點利用自己的位置信息和網格的大小來確定網格的ID。

當節點進入發現狀態時，設定了一個長度為TD的定時器，這個定時器就是節點距離激活剩余的時間，當定時器溢出時，節點進入激活狀態，廣播發送自己已經發現的數據。定時器定時期間，如果有需要，其余節點發現的報文可以令定時器暫停，延長節點發現狀態的時間。為了避免多個發現報文發生沖突，TD會選擇一個隨機量，服從[0，常數]之間均勻分布。當一個節點發送了發現報文后，其余的等價節點將會進入睡眠狀態，只有發送發現報文的節點被激活，進入激活狀態。節點進入激活狀態之后，節點會設定一個時間為TA的定時器，定義節點此次將要激活的時間，定時器時間到達后，節點將返回發現狀態。當處于激活狀態時，節點每隔TA時間重新廣播它的發現報文。

根據這種機制，整個網格內只有一個節點處于激活狀態，網格內的數據轉發功能就由此節點來完成。對于處于發現狀態的節點，節點通過接收其余節點的發送報文來感知是否有比自己擁有更長生命周期的節點，即剩余能量值比自身大的節點，如果有，則此節點轉入睡眠狀態，發現狀態中生命周期最長的節點就被預計作為下一個激活的節點。當節點進入睡眠狀態時，關閉收發信機，通過設置一個定時器在TS時間后自動喚醒節點，進入發現狀態。節點的睡眠時間也是采用節點激活時間內均勻分布的一個隨機數。一般情況下，節點的激活時間要比自己的生命周期短得多，以此來多次進行激活完成工作。

（3）移動節點的自適應算法。根據以上協議的規定，GAF路由算法最理想的情況就是每個網格內只有一個處于激活狀態的節點，盡量少的節點處于發現狀態。但是對于移動無線傳感器網絡來說，有些節點可能移動，尤其是對于網格內的激活節點來說，如果激活節點移出網格，那么該網格內的通信路由將被中斷，從而降低路由的可靠性，同時丟包率也會升高。因此，GAF路由算法要能夠調節網格內處于激活狀態的節點數，使參與路由的節點數保持在一個相對平衡的狀態。

對于節點移動的情況，GAF路由算法通過預測和報告節點規律的方法，來解決節點移動帶來的網格內的路由中斷問題。GAF路由算法讓每個節點預測其可能離開網格的時間，并且將此信息加入發現信息中，發送給其余節點。當其余節點進入睡眠狀態后，其睡眠時間會考慮到激活節點的離開時間，使睡眠時間小于節點的離開時間，當此激活節點還未離開時就會有節點處于發現狀態，及時解決激活節點離開所帶來的激活節點缺失的情況。當然這種修改在一定程度上縮短了節點的睡眠時間，這對于靜態的無線傳感器網絡節點的應用來說是沒有必要的。

嚴格來說，GAF路由算法不屬于路由協議，因為它沒有確定整個網絡內的路由，只是針對局部路由進行的一種節省能量的技術，但是這種算法在節點分布比較密集的區域中能夠取得很好的效果，可以說是一種輔助型的路由算法。GAF路由算法通過對網絡進行地理劃分，讓網格內只有一個節點處于激活狀態，來完成網格區域內數據的轉發，節省能量，GAF路由算法的這種思想可以用在許多路由算法中。GAF路由算法還需進一步改進，最好能夠找到一種不需要或者需要比較少的地理位置信息就能夠實現網絡內等價節點互換的辦法，這些辦法最好能夠與具體的路由情況無關，與MAC層獨立存在，同時希望增加的時延盡可能小，能效更高。