Benjie Chen等人提出的Span也是一種在保證網路正常運行的條件下，儘量將節點關機的節能算法。在這種節能方法中，只有部分節點處於通信狀態，相當於組成一個通信骨幹網，網路上所有的數據流都從這些骨幹節點通過。因此，與全體節點都處於通信狀態情況相比，可能導致時延增大，頻寬資源下降，甚至有些節點不可達。
基本介紹
- 中文名：Span算法
- 用途：用於自組網中進行節能
基本思想,關鍵技術問題,總結,
基本思想
一個令人滿意的關機節能算法應當具有以下幾個特點：
1、在大多數時間內儘可能地讓更多的節點關閉無線接收機；
2、能夠保證網路的連通性與不使用這種節能措施時相同；
3、使用這種方法與不使用這種方法相比，增加的時延要儘可能小、可利用的頻寬資源下降不大。
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訊息實現的。
為了避免一個協調者的退出和一個新協調者上任之間的時間空白，引起網路連通性的暫時失效，節點在發出它的退出通告後仍然要作為協調者提供一段短時間的服務，在這段短時間內允許路由協定繼續使用以前的協調者直到選舉出一個新的協調者。
4、與MAC和路由的互操作
如圖1-1所示，Span既不屬於路由協定，也不屬於MAC協定；而是處於兩者之間的一個中間層。Span通過只允許在協調者集合中尋找和維護路由的方式，可以考慮支持多種路由協定。Span協定的實現與MAC層的節能模式有關。Span協定是在IEEE802.11的節能模式上採用基於地理位置的路由協定實現的。
圖1-1 Span與MAC和路由的分層關係
圖1-1 Span與MAC和路由的分層關係總結
Span能在不明顯降低網路容量和連通性的條件下降低能量的消耗。Span分散式地從所有節點中推選協調者，並不時地輪流更替協調者。協調者處於喚醒狀態並完成多跳分組數據的路由，而非協調者處於休眠節省能量的模式，非協調者周期性喚醒檢查它是否應當成為一個協調者。
仿真結果表明，Span不僅能夠保持網路的連通性，也能保持網路的容量，降低了時延，有效地節省了能量，而且在某些場合下，網路壽命可以延長兩倍。
