地域自適應保真算法GAF（Geographical Adaptive Fidelity）是自組網中一種能量有效的路由算法。GAF是通過讓節點儘量處於關機狀態來節省能量的方法。同時，GAF還考慮了所有節點能量消耗的均衡性。
基本介紹
- 中文名：地域自適應保真算法
- 外文名：Geographical Adaptive Fidelity
- 外語縮寫：GAF
- 類型：節能策略
- 用途：用於節省自組網中的能量消耗
基本思想,關鍵技術問題,總結,
基本思想
自組網中，節點不僅在傳送和接收分組時要消耗能量，而且當節點處於空閒狀態進行幀聽時也要消耗能量（必須處理接收信息）。許多研究指出空閒時的能量消耗與傳送和接收時的能量消耗相比是不能忽略的。Stemm和Katz曾指出，通過測量，空閒、接收與傳送的功率消耗之比為1:1.05:1.4，最近的研究又表明其比率為1:2:2.5或1:1.2:1.7在以上任何一種情況下，空閒狀態下的能量消耗都不能忽略。
因此，能量使用的最最佳化不僅要減少傳送與接收的功率大小，而且應當考慮在不影響參與組網的前提下，適時地關閉部分節點的無線收發信機。
從路由上考慮，自組網中一般存在冗餘節點，這使得節點之間存在多條路由。因此，在維持節點連通性的前提下，可以關閉一些中繼節點以節能。
GAF中將路由保真度定義為保持正在通信的節點間的連通性。GAF節能是利用節點的位置信息（利用GPS得到），組成虛擬網路，格線中的節點對於中繼轉發而言是等價的，這些節點通過分散式協商確定哪個節點激活，激活多長時間，然後關閉的節點周期性地喚醒，變換角色以平衡能量消耗。利用這種方式，GAF延長了節點和網路的壽命。
關鍵技術問題
GAF算法需要解決：等價節點的確定、狀態轉移、與現有路由協定結合等關鍵技術問題。
1、等價節點的確定
這裡所謂兩個節點等價是指：對中繼轉發而言，一個節點可以代替另一個節點中繼轉發。根據這個定義，節點的等價性與通信的源節點和目的節點是誰有關。為了讓等價節點與通信的源節點和目的節點無關，GAF假設每個節點知道自身相對於其他節點的精確位置（利用GPS），並且將節點分布的整個區域劃分成小的“虛擬格線”。虛擬格線採用這樣的定義：對於兩個相鄰的格線A和B，所有A中的節點都可以與B中的節點通信，反之亦然。因此在每個格線中的所有節點對於所有的路由來說是等價的。
圖1-1構造了三個虛擬格線A，B，C。根據虛擬格線的定義，節點1可以到達節點2、3、4中的任何一個，而節點2、3和4都可以到達5。因此節點2、3和4是等價的，其中任意兩個可以關機。
圖1-1 GAF中虛擬格線的例子
圖1-1 GAF中虛擬格線的例子設虛擬格線為一個邊長是r的正方形，無線通信的有效傳播距離為R：則為了滿足虛擬格線的定義，任意兩個相鄰格線中的兩個相隔最遠的節點間的距離不能超過R。在圖1-1中，格線B中的節點2和格線C中的節點5分別處於連線兩個格線的對角線的兩端，兩者距離為最長。因此，可以得到r^2+(2r)^2≦R^2，即r≦R/√5。
2、GAF的狀態轉移
在GAF中，節點始終處於以下三種狀態中的一種：休眠狀態，發現狀態和激活狀態。圖1-2給出了GAF的狀態轉移。只有處於激活狀態的節點才參與數據轉發。
圖1-2 GAF中的狀態轉移
圖1-2 GAF中的狀態轉移節點起始於發現狀態，這時一個節點打開收發信機並通過交換髮現報文以發現相同格線內的其他節點。發現報文的內容包括：節點ID，格線ID，估計的節點激活時間（Estimated Node Active Time,ENAT）和節點的狀態。節點利用它的位置信息以及格線大小確格線ID。
當節點進入發現狀態是，為其設定一個長度為Td的定時器，當定時器到時，節點廣播其發現報文，然後轉入激活狀態。定時器計時可以被其他節點的發現報文暫停。定時器的設定降低了發現報文相互衝突的可能性。
當節點進入激活狀態時，接設定另一個長度為Ta的定時器定義節點處於激活狀態的時間。Ta時間到後，節點將返回發現狀態。處於激活狀態時，節點每隔Td時間重新廣播其發現報文。
當處於發現或激活狀態的節點找到處理路由的等價節點時，它自身會轉入休眠狀態。節點通過一種分級機制來決定哪個節點處理當前路由：處於激活狀態的節點要比處於發現狀態的節點的級別高：對於處於相同狀態的節點，GAF規定擁有更長預期生存時間的節點有更高的級別。
當節點轉入休眠狀態時，就關閉收發信機。處於休眠狀態的節點在休眠一段時間Ts之後喚醒，同時重新轉入發現狀態。
Td、Ta、Ts都是由節點按照一定規則獨自分散式確定。Td選為一個均勻分布隨機變數的取值，這樣可以避免多個發現報文的衝突。這個隨機變數取值範圍受節點分級的影響：儘量使高級節點能夠壓制低級節點，促使它們儘快進入休眠。Ta可以設成節點的估計激活時間。節點休眠時間（Ts）可以設成處於0和當前激活節點的enat值之間的一個隨機時間。當前處於激活狀態的節點將ENAT的值設定成小於耗盡所有剩餘能量所需時間的值（ENLT,Expected Node Lifetime），例如將ENAT的值設成ENLT/2，這樣在角色切換到其鄰近節點時，此節點只花費了其能量的一半。
3、對節點移動性的自適應
GAF儘量調節參與自組網路由的節點數，以使參與路由數據的節點數保持在一個相對穩定的水平上。理想的情況是：在任何時間每一個格線中都有一個處於激活狀態的節點。然而，隨著節點的移動，處於激活狀態的節點可能會移出其所在的格線。這樣就會使其先前所在的格線中沒有一個處於激活狀態的節點，從而減小了路由保真度。在高移動性的情況下，這個問題會大大增加丟包率。
GAF通過使用預測並報告節點移動性的方式，解決節點移動帶來的路由保真度被破壞的問題。具體而言，讓每個節點預測其離開所在格線的時間ENGT（Estimated Node Grid Time）並且將此信息寫入發現信息中；當其他節點進入休眠狀態時，它們休眠的時間長度取ENAT和ENGT中較短的一個，這樣就可以適應節點移動性的變化。這種修改沒有改變節點的分級規則，但是節點的休眠時間可能變短了。
節點可以利用它的當前移動速度s和格線的大小來估計ENGT（速度值可以通過大多數GPS接收機獲得或估計），例如：EGNT=r/s。
4、GAF與自組網路由的相互關係
GAF是獨立於自組網路路由協定的，準確地說它本身不是一個路由協定，只是一個輔助路由協定節能的算法。因此，GAF要和現有的路由協定結合。這樣也就帶來一個問題：當一個節點被關閉時，如果它正處於路由數據包的激活狀態時，GAF只好依靠自組網路由協定本身的機制進行重路由，這會引起丟包。
總結
嚴格的講，GAF算法不屬於路由協定，而是一種節能策略。這種策略希望在節點密集分布區域，只維持少數節點處於激活狀態，參與路由的中繼轉發，讓大多數節點休眠。同時，這種策略一定要保證網路的連續性。GAF通過劃分地理格線，讓格線內儘量只有一個節點激活實現了這種節能策略。仿真表明GAF要比一個未改進的自組網網路協定節省40%~60%的能量。而且，對GAF的仿真表明網路的生存時間與節點的密度成正比。
