Span算法

一個令人滿意的關機節能算法應當具有以下幾個特點：

1、在大多數時間內儘可能地讓更多的節點關閉無線接收機；

2、能夠保證網絡的連通性與不使用這種節能措施時相同；

3、使用這種方法與不使用這種方法相比，增加的時延要儘可能小、可利用的帶寬資源下降不大。

4、這樣一種方法最好與具體的路由和MAC協議無關，也就是能夠支持多種路由與MAC協議。

Span是滿足上述要求的一種節能算法。在Span算法中，網絡的每一個節點能夠以分佈式方式獨立週期性地判斷和決定自己應當進入休眠還是保持清醒。保持清醒的節點作為一個協調者，承擔當前骨幹路由上的中繼轉發功能。判斷是否應當清醒成為協調者的原則是：當一個節點發現它的兩個鄰節點之間既不能之間通信又不能通過一個現存的協調者通信時，它就認為自己應當成為協調者。為了均衡能量消耗避免部分節點過早死亡，網絡中的節點應當輪替地成為協調者。同時，為了更好地節能，處於清醒狀態作為協調者的節點越少越好。

Span通過讓每個節點週期性地廣播HELLO消息實現上述基本思想。HELLO消息中包含：節點狀態（節點是或不是協調者），節點當前的協調者、節點當前的鄰居。然後，每一個非協調者節點週期性地喚醒和休眠，喚醒時依據自己獲得的信息，根據上述規則確定它是否應當成為一個協調者。

1、避免協調者競爭

當局部區域內的多個節點同時發現缺少一個協調者時，它們就都認為自己應當成為一個協調者，然後就利用HELLO消息通告周圍節點，這就產生了通告競爭。Span通過讓這些節點採用隨機退避發送HELLO消息來解決這個競爭問題。

這種方法是：當節點判斷自己應當成為協調者時，使用某種機制確定一個隨機退避時間，然後退避；如果在退避時間結束時節點沒有收到從其他相鄰節點發出的HELLO消息，它就發出HELLO消息；否則，它會根據任何收到的HELLO消息來重新判斷它成為協調者的合格性，如果它依然應當成為協調者，這個節點就會利用HELLO消息發出通告。

2、退避時間確定

退避時間短意味着節點成為協調者的優先級高，退避時間長意味着節點成為協調者的優先級低。一個節點是否更應當成為協調者，取決於這個節點的剩餘能量，以及這個節點周圍的局部拓撲結構等因素。

首先考慮：當所有的節點有大概相等的能量的情況，這意味着在決定哪些節點更容易成為協調者時只考慮節點的拓撲結構。設Ni是節點i的鄰節點數目，Ci是節點i成為協調者後通過節點i新增連接的節點對數目。顯然0≦Ci≦

，在Span中將Ci/

稱為節點i的利用率。利用率高的節點表明這個節點成為協調者後，通過它新連接的相對節點對數多。讓利用率高的節點成為協調者，可以減少成為協調者的總節點個數。因此，應當讓Ci值高的節點更易於成為協調者。為了避免協調者競爭，應當引入一定的隨機性。因此，當所有節點的能量大概相等時，一個比較合理的確定退避時間的公式如下：

delay =

R是[0,1]內均勻分佈的隨機變量，T是無線鏈路上的往返傳播時延。

其次考慮節點中的電池能量不相等的情況。原則顯然是：要求剩餘能量高的節點更應該成為協調者。Span中考慮了的節點的不一致性：每個節點的總可用電池量（也就是開始時的總電池能量）是不同的，有的節點類型多，有的節點類型少。在這種情況下，如果用Er來代表一個節點剩餘的總能量（用焦耳表示），用Em表示該節點的總可用能量，一個合理的觀點是保證Er/Em比值比較大的節點比Er/Em比值小的節點更容易成為一個協調者。在Span中，綜合剩餘能量和網絡拓撲因素後，確定退避時間的公式為：

delay =

3、協調者身份撤銷

每個協調者週期性地檢查它是否應當推出協調者行列。撤銷自己作為協調者的原則是：當一個節點的每對鄰居都能直接互相到達或能通過其他協調者到達，這個節點就應當推出協調者行列。但是，為了能量消耗的均衡性，當一個節點當了一段時間的協調者後，如果它的每對鄰節點能通過其他鄰居相互到達，就算那些鄰居目前不是協調者，這個節點也會退出協調者行列。這個規則給了其他鄰居一個成為協調者的機會。協調者退出也是通過發送HELLP消息實現的。

為了避免一個協調者的退出和一個新協調者上任之間的時間空白，引起網絡連通性的暫時失效，節點在發出它的退出通告後仍然要作為協調者提供一段短時間的服務，在這段短時間內允許路由協議繼續使用以前的協調者直到選舉出一個新的協調者。 ^[1] 

4、與MAC和路由的互操作

如圖1-1所示，Span既不屬於路由協議，也不屬於MAC協議；而是處於兩者之間的一箇中間層。Span通過只允許在協調者集合中尋找和維護路由的方式，可以考慮支持多種路由協議。Span協議的實現與MAC層的節能模式有關。Span協議是在IEEE802.11的節能模式上採用基於地理位置的路由協議實現的。

Span能在不明顯降低網絡容量和連通性的條件下降低能量的消耗。Span分佈式地從所有節點中推選協調者，並不時地輪流更替協調者。協調者處於喚醒狀態並完成多跳分組數據的路由，而非協調者處於休眠節省能量的模式，非協調者週期性喚醒檢查它是否應當成為一個協調者。

仿真結果表明，Span不僅能夠保持網絡的連通性，也能保持網絡的容量，降低了時延，有效地節省了能量，而且在某些場合下，網絡壽命可以延長兩倍。