Quorum-Based Energy Conserving Mechanism in Wireless Mesh Networks

     The Wireless Mesh Network (WMN)[1] has attracted great attention as a new wireless network solution. The energy conservation of WMN nodes, particularly Mesh clients, is thus becoming a very important issue. With Mesh clients’ support for mobile Ad hoc networking, the WMN is actually a super set of Mobile Ad hoc Networks (MANETs). The energy conserving mechanisms for MANET can not only be applied in WMN directly, but also be valuable in designing WMN’s energy conserving algorithms. There has already been lots of research on energy conservation of WMNs/MANETs. The existing energy conservation methods are generally divided into three categories: power control, power-aware routing and power mode management. The mechanism introduced in this paper belongs to the power mode management.

     The authors of Reference [2] first applied the Quorum concept in power saving. The Quorum has been widely used in distributed systems, and its application in asynchronous power saving presents us with a new perspective of research. After several years’ development, the Quorum-based energy conserving algorithms have achieved good results in MANETs.

1 Basics Principles

1.1 Power Saving Mode in IEEE 802.11
Current research on power saving of MANETs is mainly based on IEEE 802.11. The Quorum mechanisms herein were first applied to IEEE 802.11-based networks, too. IEEE 802.11 supports two power modes: active mode and Power Saving Mode (PSM), assuming perfect clock synchronization of all hosts is available with the Timing Synchronization Function (TSF). Figure 1 illustrates a frame structure and data transmission in PSM. In this figure, the time axis is divided into equal-length Beacon Intervals (BIs), each of which starts with an Ad hoc Traffic Indication Map (ATIM) window. The ATIM window begins with a Beacon Window (BW), followed by a  Data Window (DW).

     Each host remains active periodically in the ATIM window. The ATIM window often accounts for 20% of a BI. In the BW, each host contends to send the beacon frame. To avoid collisions, each host will wait for a random number of slots between 0 and 2 (CWmin-1) before sending out the beacon. After the beacon is sent, all hosts will contend to send ATIM frames if there are data in the buffer to be sent. The host receiving ATIM frames must reply with an ACK to complete a handshake process and after the ATIM window finishes, it still remains active in order to send or receive data frames. If the handshake process does not finish in the ATIM window, the hosts will enter power saving mode and wait for next BI.

1.2 Definition and Characteristic Parameters of Quorum System
Mathematically, the Quorum system is defined as follows:

     Many quorum systems have been developed for distributed applications, including grid, cyclic, byzantine and probabilistic quorum systems. Among them, Grid Quorum system[3] is the easiest to understand.
The mathematical definition of Grid Quorum system is:

     Arrange the elements of the set U = {1,…,N } (N = n 2) into an n ×n grid. Then arbitrarily select one row and one column of elements to form a new set Qi , which is a Quorum. All Qi  sets make a Grid Quorum system.

     Figure 2 illustrates a 4× 4 Grid Quorum system, where
Q1 = {1, 2, 3, 4, 5, 9, 13}, Q2 = {3, 7, 9, 10, 11, 12, 15}, Q1∩Q2 = {3, 9}

     The characteristic parameters of a quorum system vary in different applications. The parameters discussed in this paper include quorum size, the number of quorum elements, ratio of quorum size to universal set size (QSR), the minimal intersection size (denoted by m) of any two Quorums.
For example, in an n ×n Grid Quorum system, the Quorum size is 2n -1, QSR is (2n -1)/n 2 = (2  N -1)/N and the minimal intersection size of any two Quorums is 2.

2 Quorum Energy Conserving Mechanism

2.1 Basic Idea
Having the distribution feature, Quorum is initially applied in WMN’s mobility management, such as location management[4].

     The nature of power saving requires each host to go to sleep after collision-free data transmission or reception, and wake up when there are data to be transmitted or received.

     The traditional power-saving mechanisms are a kind of global schedule: All hosts synchronize and wake up at the same time to send or receive data. The core idea of Quorum energy conserving mechanisms is to adopt a distributed approach, allowing the active intervals of all hosts to be distributed in such a specific way that the intervals of hosts are somewhat overlapped and the ratio of active intervals to the total time is the least.

2.2 Work Modes
In the Quorum systems herein, the Quorum element refers to an interval (e.g. BI), and the set of active intervals is the Quorum of the host.

     Depending on whether the intervals start at the same time
(i.e. synchronization), the Quorum energy conserving mechanisms fall into two work modes: synchronous and asynchronous.

     In the asynchronous mode, the hosts do not need to synchronize their clocks but work in an asynchronous way. It is the Quorum mechanism that guarantees the intervals of different hosts to be overlapped. In the large-scale, high-dense, mobile and multi-hop network environment, clock synchronization is often a difficult job and the overhead involved is considerably large, but the asynchronous Quorum energy conserving mechanism can perform perfectly well.

     In the network environment where clock synchronization is easy to achieve, the synchronous Quorum mechanism can further optimize the energy efficiency.

3 Asynchronous Quorum Energy Conserving

3.1 Principle of Asynchronous Quorum System
Being a basic unit, several BIs make a Quorum Interval (QI). The BIs that are Quorum elements are called Quorum Beacon Intervals (QBIs), while others are Non-Quorum BIs (NQBIs). An NQBI starts with an Awake Window (AW), which is similar to ATIM window. In the AW, the host is active and it will go to sleep if there is no data to be transmitted. A QBI starts with a BW (BW ≤ AW), and the rest part of QBI is Data Window (DW). The host remains active in the entire QBI. Figure 3 illustrates the frame structure of a Quorum system.

     From Figure 3, it can be easily seen that the more intervals of two Quorums are overlapped, the earlier the handshake may be completed. Meanwhile, as the host always remains active in QBIs, extra power will be consumed. Therefore, it is necessary to reduce QSR without disrupting the handshake process.
Among others, two design goals of asynchronous Quorum systems are:

• Two asynchronous hosts can shake hands within one QI.
• The ratio of active intervals to Quorum Interval (i.e. QSR) should be the minimal.
  

     For the first goal, Reference [5] proves, on the assumption there is not any collision or transmission error, any Quorum system that satisfies the rotation closure property can ensure that the BI of one Quorum overlaps with the active interval of another Quorum within one QI. As a result, the handshake between the two Quorums can be completed.

     In mathematical terms, the rotation closure property can be defined as:
A Quorum system Q under
U = {1,…,N } is said to have the rotation closure property if
?坌Qi , Qj∈Q, k∈{1…n } : Qi  ∩ rotate (Qj , k ) ≠ Ф, where
rotate (Qj , k ) = {(j +k ) mod n |j∈H }

     In other words, the rotation closure property can be mathematically translated to the non-empty intersection property of Quorums in asynchronous condition. Many Quorum systems (e.g. Grid Quorum system) satisfy this property. Figure 4 illustrates the handshake process of two asynchronous Quorums. The beacons at intervals 1 and 5 of host A can be received by Host B, and the beacons at intervals 7 and 12 of Host B can be received by Host A.

     For the second goal, References [5] and [6] prove: for the asynchronous Quorum system with a Quorum size N and a minimal intersection size m, the lower bound of its QSR is: QSR ≥  m /N. If m = 1, QSR ≥1/  N.
Constructed from the difference sets, the cyclic Quorum system[8] meets the above optimal requirement of QSR.

     The mathematical definition of difference set is:
     A subset D = {d1, d2 ,…,dk } of Zn is called a difference set under Zn if for ?坌е ≠ 0 (mod n), there exists di , dj ∈D, and di -dj =е (mod n ).

     Mathematically, the cyclic Quorum system is defined as follows:
Given any difference set D = {d1, d2 … dk } under Zn , Q = {Q1 … Qn } is a cyclic Quorum system, where Qi = {d1 +i, d 2+i  …dk+i } (mod n ), i = 0…n -1.
For example, if D = {1, 2, 4}, U = Z7.

3.2 Adaptive Quorum System
In the abovementioned Quorum systems, the Quorums are of the same size, and their QSRs are the same, too. These Quorum systems are called symmetric Quorum systems. In WMN/MANET applications, the traffic of a host may be burst, requiring the system to make adaptive adjustment based on the traffic. Besides, the power supply of each host and the remaining charge of the batteries are different, which also requires adaptive power-saving policies. Therefore, the Quorum systems with different sizes and different QSRs, i.e. asymmetric Quorum systems, have to be designed. This is the third goal.

     Obviously, the Grid Quorums of different sizes can make an asymmetric Quorum system. Figure 5 illustrates two Quorums whose sizes are 32 and 42 respectively. They can form a grid Quorum system, which still satisfies the rotation closure property.

     Reference [5] proposes an adaptive Extended Torus Quorum system. Reference [6] also addresses the adaptive issue, but argues that constructing the best asymmetric Quorum may be a Non- Deterministic Polynomial Time - Complete (NPC) problem, the most complex class of problems. This is actually a misunderstanding because the third goal only requires a Quorum table that satisfies asynchronism, not dynamical calculation of Quorums. The complexity involved in selecting Quorum system against the table is linear. Based on Cyclic Quorum system and table lookup method in Reference [8], Reference [7] proposes an optimal adaptive Quorum protocol called Adaptive Asynchronous Power Management (AAPM). This protocol can dynamically adjust the Quorum size and QSR and meet the requirements of the second design goal.

3.3 Performance Comparison of AQEC systems
The performance comparison of Asynchronous Quorum Energy Conserving (AQEC) systems can be made in three ways: comparing an AQEC system with old synchronous system, comparing an Optimal Asynchronous Quorum Energy Conserving (OAQEC) system with a non-optimal AQEC system, and comparing the performances of an AQEC system under different application environments. Simulation experiments are conducted in References [5-7], and the simulation environments are multi-hop Ad hoc networks: the simulation areas are 1,500 × 300 m2 and 1,000 × 100 m2 respectively; the hosts are connected into an IEEE 802.11 Ad hoc networks; the transmission distance between hosts is 250 m and the number of hosts is 50.

     (1) PSM vs. non-PSM
     Simulation results in Reference [6] show that an AQEC system cannot work properly in a mobile multi-hop Ad hoc environment once its packet loss rate in PSM mode exceeds 50%. OAQEC can save more than 80% of energy compared with the systems without any power saving mechanism. In Reference [5], in the mobility test of 50 distributed hosts, no host in the system without any power saving mechanism survives at 120 s, while the survival ratio of hosts in OAQEC system reaches 80% even at 360 s.

     (2) OAQEC vs. common AQEC
     OAQEC system is theoretically the most energy-efficient, which has been proved with simulations in References [5] and [7].

     (3) Comparison of performances of QAEC system in various network environments
     Simulation results in References [5-6] show that the performance of an AQEC system decreases linearly with the growth of network scale and host density. But when a host moves at a speed of about 10 m/s, the decrease of system performance is insignificant. This proves that AQEC systems can be applied in the WMN environment.

     Reference [6] simulates the OAQEC performance in wireless sensor networks, and the results show the performance of OAQEC has a considerable increase over the typical Sensor-Medium Access Control (S-MAC)[9] system. For example, when the S-MAC’s packet loss ratio exceeds 50%, the packet loss ratio of OAQEC remains within 5%.

     In the case of network traffic change, the adaptive AQEC (AAQEC) performs excellently. The simulations in Reference [7] show AAQEC can save 20% more energy than AQEC.

4 Synchronous Quorum Energy Conservation Mechanism

4.1 Synchronous Quorum Energy Conservation System
As shown in Figure 4, the host in AQEC has an active interval at each BI, which is similar to the case of PSM mode. As a result, when clock synchronization is available, more energy can be saved if the synchronous mode is adopted.

     The biggest difference between the fuzzy control-based Synchronous Quorum Energy Conserving (SQEC) system and AQEC system lies in their frame structures. Figure 6 illustrates the frame structure of a synchronous Quorum system. In the synchronous system, the host is only required to be active in BWs of QBIs and it can doze in the rest of Quorum intervals. In this way, more energy is saved. In terms of Mathematics, synchronous Quorums can be regarded as synchronous application of Quorum systems. Therefore, both can use the same Quorum system.

     The study on SQEC focuses on adaptive adjustment. In practice, the adaptive policies can be also used in the asynchronous mode.

     In the Adaptive Synchronous Quorum Energy Conserving (ASQEC) protocol proposed in Reference [10], a host first determines its optimal Quorum sizes for different traffics based on simulation results; and during data transmission, it measures the network traffic and adjusts the Quorum size accordingly.

     However, the protocols in Reference [10] use fixed thresholds to adjust the size of Quorum, so their application is limited. Reference [11] proposes the Fuzzy Control-based Synchronous Quorum Energy Conserving (FSQEC) protocol. Adopting the fuzzy control approach, this protocol uses the experienced latency of historical packets and the length of the packet queuing for transmission as input parameters, and makes adjustment policies according to the theory of fuzzy control.

     To reduce the latency, the protocols in Reference [10] allow the host to remain active in BWs of all Quorum intervals from the time when it receives packets to the completion of packet transmission. This is basically dynamic adjustment, where elements are temporarily added in the Quorum system.

4.2  Performance Comparison of SQEC Systems
As a SQEC system works in a synchronous mode, its performance is mainly compared with other synchronous power saving systems, e.g. PSM, Dynamic Power Saving Mechanism (DPSM)[12]. In Reference [10] and [11], simulations are made respectively to compare ASQEC with PSM/DPSM and to compare FSQEC with
ASQEC/DPSM/PSM. In both references, similar simulation environments are used: Both use the Grid Quorum system; the simulations are conducted in an area of 200 m2; the hosts are immobile and connected into IEEE 802.11 Ad hoc network and the communication distance between hosts is 300 m. The only difference is their host densities, which are 50 and 30 respectively. They are single-hop Ad hoc network environments.

     Simulation results show even in the single-hop Ad hoc network environment with perfect clock synchronization, ASQEC and FAQEC can save more energy than PSM and DPSM, while their latencies are almost equivalent. In the case when the data source is at fixed rate and 20% hosts can survive, the hosts in FSQEC can survive 50%, 20% and 15% respectively longer than those in DPSM, PSM and non power saving mode. In the case of burst data source, these percentages are 100%, 40% and 10% respectively.

     Obviously, in the case of burst data source, the performance difference between SQEC and DPSM is trivial, but FSQEC has a clear performance edge over DPSM. This is because FSQEC makes use of both historical information and the data information that has to
be sent.

5 Conclusions
The Quorum-based energy conserving mechanisms in References [2, 5-7,10-11] suggest a new energy conserving policy. Working in synchronous mode, this energy conserving policy can perform better than the existing ones (e.g. PSM and DPSM); while working in asynchronous mode even in the multi-hop, mobile, large-scale and high-dense network, it can save more than 80% energy. Combining with the adaptive adjustment policy, this energy conserving policy can achieve excellent performance for data sources of various kinds.

     The essence of Quorum energy conserving mechanisms is to reduce unnecessary data synchronization but ensure synchronization in specific periods and spatial areas. Therefore, what they adopt is actually a
time-domain distributed method. Due to the distribution property of WMNs, the Quorum mechanisms are of great potential to be applied in WMNs.

     The existing Quorum mechanisms are mainly designed for the MANET environment. They are applied in one of the two work modes: synchronous and asynchronous, depending on the difficulty of clock synchronization. In WMNs, the MANET subnets may migrate in or out of the coverage of Mesh routers. As a result, how to make use of the characteristic of Mesh routers, i.e. power saving is not needed, to switch across the two work modes for various environments is still a challenge.

     Current research on Quorum energy conserving systems primarily focuses on energy efficiency optimization and adaptation. In the situations where QoS guarantee is required, it is worthy trying the cross-layer design approach that combines the Quorum-based power saving system with power control and MAC routing technologies.

References
[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 multi-hop 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.

[Abstract] Energy conservation is an important issue for wireless Mesh network. The Quorum energy conserving mechanism, discussed in this article, is quite suitable to wireless Mesh networks because it is insensitive to network scale, host 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, according to the difficulty of clock synchronization. Currently, the research on Quorum energy conserving systems focuses on energy efficiency optimization and adaptive system. As for 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 MAC routing, there is much research to do.