無線Ｍｅｓｈ網中的Ｑｕｏｒｕｍ節能機制

摘要：無線Mesh網絡節能問題十分重要。文章討論的基于Quorum的節能機制對網絡規模、節點密度、移動性和多跳等因素不敏感，非常適合無線Mesh網絡。Quorum節能機制主要基于MANET網絡環境設計。Quorum系統根據時鐘同步的難易程度，可以應用于同步和異步兩種工作模式。目前對Quorum節能系統的研究主要集中在能量效率優化和自適應系統方面。對于異步和同步兩種模式的協同，基于Quorum機制的節能與功率控制、MAC路由結合的跨層設計，是值得嘗試的課題。

關鍵詞：節能；Quorum機制；異步；同步；無線Mesh網

Abstract: Energy conservation is a quite important issue for wireless Mesh networks. The Quorum energy conserving mechanism， discussed in this article， is quite suitable to wireless Mesh networks because it is insensitive to network scale， node density， mobility and multi-hop. Originally designed for the Mobile Ad Hoc Network (MANET) environment， the Quorum mechanism can work in two modes: synchronous and asynchronous， subject to the difficulty of clock synchronization. Currently， the research on Quorum energy conserving systems focuses on energy efficiency optimization and adaptive system. As to other issues， such as the collaboration between synchronous and asynchronous working modes， and the cross-layer design for integrating Quorum mechanism-based energy conservation with power control and Media Access Control (MAC) routing， there is much research to do.

Key words: energy conserving; Quorum mechanism; asynchronous; synchronous; wireless Mesh network

無線Mesh網(WMN)[1]作為一種新型無線網絡解決方案備受關注。WMN中節點的節能，特別是Mesh客戶終端的節能十分重要。由于Mesh客戶終端需要支持移動Ad Hoc方式組網，所以WMN實際上是移動Ad Hoc網(MANET)的一個超集。MANET下的節能機制可直接應用在WMN中，并對設計WMN的節能算法有重要參考價值。關于WMN/MANET的節能，已經有大量相關研究，主要方法分為3類：功率控制、功率感知路由和低功耗模式管理。本文介紹的方法屬于低功耗模式管理。

傳統的基于同步-周期休眠/喚醒的節能機制在WMN/MANET環境下遇到了很多困難，這主要是由于同步困難引起的。在大規模、高密度、多跳、移動性網絡環境下，時鐘同步的開銷很大。一個極端的例子是兩個各自同步的子網絡，如果移動到一起，這兩個網絡會互相異步，造成網絡分化。

文獻[2]的作者首次應用分布式系統中的Quorum概念，開啟了異步節能的新領域，經過幾年的發展，基于Quorum機制的節能算法在MANET下取得了良好的效果。

1 基本原理

1.1 IEEE 802.11的節能模式

目前關于MANET的研究基本都基于IEEE 802.11，本文介紹的Quorum機制也首先應用在IEEE 802.11上。在Ad Hoc工作方式中，IEEE 802.11支持兩種模式：活躍模式和節能模式(PSM)。IEEE 802.11假設所有節點的時鐘通過定時同步功能(TSF)實現了完全同步。PSM的幀結構和一個數據傳輸的例子如圖1所示。時間軸被劃分為等間隔的信標間隔(BI)，BI開始有一個廣播傳輸指示信息(ATIM)窗，ATIM窗的開始階段，有一個Beacon窗(BW)，ATIM窗后為數據窗(DW)。

所有節點都周期性地在ATIM窗內保持活躍狀態。ATIM窗通常占BI的20%。在ATIM開始的BW內，每個節點通過競爭發送信標(Beacon)。為了減少碰撞，每個節點在嘗試發送Beacon前有0～2×(CWmin-1)個時隙的隨機規避時間。發送完Beacon后，如果緩沖區有數據要發送，則通過競爭發送ATIM幀，收到ATIM幀的節點必須回復ATIM應答幀完成握手，并在ATIM窗結束后仍保持活躍，進行數據幀的發送和接收。如果在ATIM窗沒有完成握手，則進入休眠模式，等待下一個BI的到來。

1.2 Quorum系統定義及表征參數

Quorum系統的數學定義為：

2 Quorum節能機制基本思想及應用模式

2.1 Quorum節能機制的基本思想

Quorum具有分布式特征，在WMN中的應用首先是移動性管理，如位置信息管理[4]等。

節能的本質要求是：盡可能無沖突地實現數據收發后休眠，并在需要數據收發時激活。

傳統的節能機制是一種全局的時間調度：所有節點同步起來，在同一時間段醒來進行數據收發。Quorum節能機制的核心思想是采用一種分布式的方法，使節點的激活時隙成一種特定分布，保證互相之間時隙有交疊，且激活時隙占總時間的比例達到最小化。

2.2 Quorum節能機制的同步和異步工作模式

本文用來節能的Quorum系統中，Quorum中的元素是指一個時隙(如BI)；而活躍時隙的集合為該節點對應的Quorum。

根據這些時隙的開頭是否對齊(也就是是否同步)，分為同步和異步工作模式。

Quorum節能的異步工作模式最引人注目。該模式下，節點不進行時鐘同步，而是保持異步工作，由Quorum機制保證批次之間時間上有交疊。在大規模、高密度、移動、多跳的網絡環境下，同步比較困難，開銷很大，而異步的Quorum節能機制能保持良好性能。

在時隙同步較易實現的網絡環境下，同步Quorum節能機制可以進一步優化能量效率。

3 異步模式Quorum節能機制

文獻[2]首先提出了異步工作模式的Quorum節能機制，文獻[5-6]分別對該異步模式下的Quorum節能機制進行了理論證明和仿真分析，文獻[7]則提出了最優自適應調整Quorum大小和占空比的方法。

這些方法的基本思想是保留PSM模式的ATIM窗，同時選取部分時隙進行偵聽，時隙選取方法遵循Quorum的原則。

3.1 異步Quorum系統的原理和能量最優化

以BI為基本時隙單元，多個BI組成Quorum間隔(QI)。屬于Quorum元素中的BI稱為Quorum信標間隔(QBI)，非Quorum的BI稱為非Quorum信標間隔(NQBI)。NQBI由一個覺醒窗(AW)開始，AW類似于ATIM窗，節點處于活躍狀態，如果沒有數據傳輸則進入休眠狀態。QBI由一個BW(BW≤AW)開始，其余時間為DW，整個QBI期間節點都處于活躍狀態。圖3為一個Quorum系統幀結構示意圖。

從圖3可以看出，兩個Quorum重疊的時隙越多，越可能早實現握手；同時QBI時，節點總處于活躍狀態，需要消耗額外的電量，所以在保證前述握手條件下，需要盡可能減少QSR。

異步Quorum系統設計的目標是：

異步的兩個節點能夠在一個QI內實現握手；

處于活躍時期的時間與QI的比值(即占空比)最小。

所謂異步，就是要求兩個節點的時隙可以有任意的偏差。

對于第1個目標，文獻[5]證明了假設不存在碰撞和傳輸錯誤，滿足“旋轉閉合特性”的Quorum系統都可以保證在一個QI內，任意兩個Quorum的BI處于對方的活躍期內，因此可以完成握手。

旋轉閉合性的數學定義為：

3.2 自適應Quorum系統

前面的Quorum系統，每個Quorum的大小是一樣的，每個Quorum的QSR也是一樣的，這樣的Quorum系統稱為對稱的Quorum系統。在WMN/MANET的應用中，節點的業務流量可能是突發的，需要系統能夠根據流量進行自適應調整；不同節點的供電方式和電池剩余電量也不一樣，希望采用的節能策略也可以自適應調整。這就需要設計不同大小和不同QSR的Quorum系統，即非對稱Quorum系統，成為第3個目標。

不同大小的Grid Quorum自然就可以構成非對稱的Quorum系統，如圖5所示，大小分別為：N =32和N =42的2個Quorum，組成的Quorum系統仍滿足“旋轉閉合特性”。

文獻[5]一開始就構造了一類自適應的Extended Torus Quorum系統。文獻[6]也注意到了這個問題，但構造最佳的非對稱Quorum可能是一個非決定性多項式時間-完全(NPC)問題，屬最難解的一類問題。這實際上是一個誤解，因為第3個目標實際上只要求提供滿足異步特性的Quorum表，而不需要動態計算Quorum。而根據查表選擇Quorum系統，復雜度是線性的。文獻[7]就利用文獻[8]的Cyclic Quorum和查表的方法，構造了最優自適應Quorum系統——AAPM，可以動態調整Quorum大小和QSR，并具有第2個目標要求的最優特性。

3.3 異步Quorum節能系統的性能

異步Quorum節能系統(AQEC)的性能比較方式分為：與原有同步系統的比較、能量最優Quorum節能系統(OAQEC)與非最優系統的比較以及各種應用環境下Quorum系統的適應能力的比較。文獻[5-7]對這些進行了仿真，仿真區域分別為：1 500×300 m2和1 000×100 m2的環境，節點采用IEEE 802.11 Ad Hoc方式組網，節點的傳輸距離為250 m，節點數為50，都是多跳的Ad Hoc環境。

(1)不使用節能模式與PSM節能模式的比較

文獻[6]仿真證實了在移動的多跳Ad Hoc環境下，PSM模式下的丟包率在50%以上，根本不能很好地工作。OAQEC比不使用任何節能機制的系統能節省80%以上的能量。如文獻[5]中，在分布50個節點的移動性測試中，無節能的系統在120 s時已無存活節點，而OAQEC在360 s時仍然有80%的存活節點。

(2) OAQEC與普通AQEC系統比較

OAQEC是理論上能量最優的，文獻[5，7]可以證實。

(3) 各種網絡環境下的性能比較

文獻[5-6]的仿真中都顯示：在AQEC節能系統隨著網絡規模、節點密度的增長時，系統性能的下降也是線性的，當節點以10 m/s左右的速度移動時，系統性能變化不明顯。這樣就證實了AQEC可以應用于WMN環境中。

文獻[6]還仿真了無線傳感器網絡下OAQEC的性能，結果表明OAQEC比經典的S-MAC[9]系統性能有很大的提高，比如在S-MAC有50%以上的丟包率時，OAQEC的丟包率仍然保持在5%以內。

對于網絡業務流量的變化，自適應的AQEC(AAQEC)具有很突出的性能，文獻[7]的仿真表明，AAQEC能比AQEC節省20%的能量。

4 同步模式Quorum節能機制

4.1 同步模式Quorum節能系統

由圖4可以看出，AQEC在所有的BI都有活躍期，這點類似于PSM模式。當時隙同步可以實現的時候，應用同步模式可以進一步節約能量。

基于模糊控制同步Quorum節能(SQEC)系統與AQEC的最大區別體現在幀結構上。圖6為同步Quorum系統的幀結構圖，節點只需要在QBI中保持BW活躍，其他時間都可以維持在休眠狀態。這樣就能節省更多的能量。從數學上來看，同步Quorum是Quorum系統的同步應用，因此兩者可以使用同樣的Quorum系統。

關于SQEC的研究主要在自適應調整方面，實際上這些策略也可以用在異步模式下。

在文獻[10]的自適應同步Quorum節能(ASQEC)協議中，首先根據仿真確定了不同流量下最優的Quorum大小，然后在數據傳輸過程中檢測網絡流量，相應調整Quorum的大小。

由于文獻[10]中的方法中采用了固定的閾值調整Quorum的大小，在實際應用中受到限制，文獻[11]提出模糊控制同步Quorum節能(FSQEC)協議，引入模糊控制的方法，將歷史數據包的延遲和排隊等待傳輸數據包長作為輸入參數，根據模糊控制的理論制訂出調整策略。

值得一提的是在文獻[10]中為了減少時延，當節點收到數據包之后的所有的時隙都保持BW活躍，直到數據包傳送完成。這從本質上也是一種動態調整，即臨時增加Quorum系統的元素。

4.2同步Quorum節能系統的性能

由于SQEC工作于同步狀態，性能比較主要是針對與其他同步方式的節能系統：如PSM、DPSM[12]。文獻[10]中對ASQEC與PSM、DPSM[12]，文獻[11]中對FSQEC與ASQEC、DPSM、PSM的性能進行了仿真比較。兩者都采用了一個200 m2的區域，節點采用IEEE 802.11 Ad Hoc方式組網，且不移動，節點通信距離為300 m，節點密度分別為50個和30個，因此是一個單跳的Ad Hoc環境。Quorum系統采用Grid Quorum。

仿真結果表明，即使在時鐘良好同步的單跳Ad Hoc網絡環境下，ASQEC和FSQEC比PSM、DPSM都能節省更多的能量，同時延遲與他們相當。如在恒定速率數據源，20%節點存活條件下，FSQEC的存活時間比DPSM、PSM和無節能模式分別多50%、20%和15%。而在突發數據源時，這一數據分別為：100%、40%和10%。

可以注意到在突發數據源的情形下，SQEC與DPSM的性能差異不明顯，而FSQEC則有明顯的性能優勢。這是因為FSQEC不僅利用了歷史信息，同時還利用了未來要發送的數據信息。

值得指出的是兩者都沒有采用最優Quorum系統，因此性能還有優化的空間。

5 結束語

文獻[2，5-7，10-11]中的Quorum節能機制提供了一種新的節能策略；工作于同步模式下則可以獲得優于已有方式(如PSM、DPSM)的性能；而工作于異步模式下，在多跳、移動、大規模、高密度的網絡中，能節省超過80%的能量。配合自適應調整策略，則可以在各種模式的數據源下，保持良好性能。

Quorum節能機制的本質是減少了不必要的數據同步，同時在局部時間/空間區域內保證必要的同步，本質上是一種“時間域”分布式的方法。由于WMN的分布式特征，Quorum機制在WMN中也有很大的應用潛力。

目前的Quorum節能機制主要基于MANET網絡環境設計，Quorum系統根據時鐘同步的難易程度，可以應用于同步和異步兩種工作模式。而在WMN中，存在MANET子網移入和移出Mesh路由器覆蓋范圍的情形，如何利用Mesh路由器不需要節能的特性，在各種環境下進行模式切換，是一個需要解決的問題。

目前對Quorum節能系統的研究主要集中在能量效率優化和自適應系統方面。而在需要服務質量保證(QoS)的條件下，基于Quorum機制的節能與功率控制、MAC路由結合的跨層設計，是一個值得嘗試的課題。

6 參考文獻

[1] AKYILDIZ I F， WANG Xudong， WANG Weilin. Wireless mesh networks: a survey [J]. Elsevier Computer Networks， 2005， 47(4): 445-487.

[2] TSENG Y C， HSU C S， HSIEH T Y. Power-saving protocols for IEEE 802.11—based multi-hop ad hoc networks [C]// Proceedings of Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM'02):Vol1，Jun 23-27， 2002， New York， NY， USA. Piscataway， NJ，USA:IEEE，2002:200-209.

[3] MAEKAWA M. An algorithm for mutual exclusion in decentralized systems [J]. ACM Transactions on Computer Systems，1985，3(2):145-159.

[4] HAAS Z J， LIANG B. Ad Hoc mobility management with uniform quorum systems [J]. IEEE/ACM Transactions on Networking，1999，7(2):228-240.

[5] JIANG J R， TSENG Y C， HSU C S， et al. Quorum-based asynchronous power-saving protocols for IEEE 802.11 Ad Hoc networks [J]. Mobile Networks and Applications， 2005，10(1):169-181.

[6] ZHENG R， HOU J C， SHA L. Optimal block design for asynchronous wake-Up schedules and its applications in multihop wireless networks [J]. IEEE Transactions on Mobile Computing， 2006，5(9):1228-1241.

[7] CHOU Z T. Optimal adaptive power management protocols for asynchronous wireless Ad Hoc networks [C]// Proceedings of Wireless Communications and Networking Conference(WCNC'07)， Mar 11-15，2007，Kowloon，China. New York，NY，USA:IEEE， 2007:61-65.

[8] LUK W S， WONG T T. Two new quorum based algorithms for distributed mutual exclusion [C]//Proceedings of the 17th International Conference on Distributed Computing System， Mar 27-30，1997，Baltimore，MD，USA.Piscataway，NJ，USA: IEEE，1997: 100-106.

[9] YE W， HEIDEMANN J， ESTRIN D. An energy-efficient MAC protocol for wireless sensor networks [C]//Proceedings of Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM'02):Vol3，Jun 23-27， 2002， New York， NY， USA. Piscataway， NJ，USA:IEEE，2002:1567-1576.

[10] CHAO C M， SHEU J P， CHOU I C. An adaptive quorum-based energy conserving protocol for IEEE 802.11 ad hoc networks [J]. Transactions on Mobile Computing， 2006，5(5):560-570.

[11] CHAO C M， LIN X H. A Fuzzy control quorum-based energy conserving protocol for IEEE 802.11 Ad Hoc networks [C]// Proceedings of Wireless Communications and Networking Conference(WCNC'07)， Mar 11-15，2007，Kowloon，China. New York，NY， USA:IEEE， 2007:2178-2183.

[12] JUNG E S， VAIDYA N H. An energy efficient MAC protocol for wireless LANs [C]// Proceedings of Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM'02):Vol 3，Jun 23-27， 2002， New York， NY， USA. Piscataway， NJ，USA:IEEE，2002: 1756-1764.

收稿日期：2008-01-17

劉天喜，北京大學信息科學技術學院在讀博士研究生，主要研究方向為近距離無線通信系統、無線醫療監護系統和新型生理信號傳感器。

唐孝通，北京大學信息科學技術學院在讀博士研究生，主要研究方向為無線通信、網絡流量自相似特征等。

焦秉立，北京大學信息科學技術學院教授、博士生導師，目前主要研究方向為CDMA、OFDM和B3G/4G無線通信系統。已發表論文30余篇、獲得專利5項。