Key Technologies of Wireless Mesh Network

     The Wireless Mesh Network (WMN) is a multi-hop, self-organizing broadband wireless network. Typically, it is a hierarchical architecture, consisting of Mesh routers and Mesh clients. Mesh routers are responsible for data relay and are interconnected into a multi-hop wireless backbone, which is connected to other networks via gateway nodes; Mesh clients access the backbone via Mesh routers. With WMN, communication between Mesh clients as well as between Mesh clients and other networks is established.

     WMN is characterized as multi-hop, self-forming, self-healing and self-organizing. Although the Ad hoc network also has these features, it is quite different from WMN in many aspects. First, the nodes in Ad hoc network are mobile, so its network topology is dynamically changing; while the Mesh routers in WMN are usually immobile, hence its backbone topology is relatively steady. Second, the mobility of nodes may restrict the power supply of equipment. As a result, in designing networking protocols for Ad hoc network, power consumption must be taken into account. On the contrary, the relay nodes of WMN are often immobile and external power supply can be used, so the restraint on its power consumption is limited. Third, Ad hoc network is designed for peer-to-peer communications between mobile nodes; while WMN aims to provide wireless broadband access for users with various service demands.

     For any wireless network, improving transmission capacity would be the primary goal in its networking protocol design. Like common multi-hop, self-organizing wireless networks, the wireless links of WMN strongly interfere with each other. This greatly challenges the design goal, i.e. improving the network capacity. In order to achieve this goal and guarantee Quality of Service (QoS), the current WMN networking protocol design basically adopts a cross-layer design approach based on the characteristics of WMN. This paper, aiming at achieving the design goal,analyses and summarizes the critical technologies related to current WMN networking protocols from the perspectives of spectrum spatial reuse, multi-channel technology and routing optimization.

1 Spatial Reuse
The WMN is a multi-hop wireless network. Due to the broadcast of wireless channel, the neighboring links in the wireless network interfere with each other, thus the transmission capacity of the network is restricted. On the other hand, the attenuation of wireless channel enables the multi-hop network to potentially have spatial reuse feature. If the spatial reuse is improved, more links can be used for concurrent transmission, and thus the network capacity is increased.

     The WMN should adopt a networking protocol with high spatial reuse. In this chapter, we will discuss Media Access Control (MAC) protocols from two aspects: WMN based on advanced Physical Layer technologies, such as directional antenna and Multiple-Input Multiple-Output (MIMO), and power control in physical layer.

1.1 Directional Antenna-Based WMN
Unlike traditional omni antenna, the directional antenna (intelligent antenna) can concentrate the energies on one direction for transmission, thus giving this direction the largest gain and other directions smaller gains. This beam direction-oriented characteristic of directional antenna can improve spatial reuse of WMN. However, new problems arise with the directional antenna in access to the shared channel, including hidden terminal, deafness and receiving node location.

     The hidden terminal problem occurs when the physically neighboring nodes become invisible to each other because they transmit in different directions. For example, in Figure 1, nodes A and B are neighbors and both of them transmit data to node C. Because they cannot find out, via the carrier, whether the other one is sending data, they are a pair of hidden nodes, and their transmission will collide at node C. Obviously, the hidden terminal problem will not occur in omni antennas. The deafness problem means the transmitting node cannot set up wireless communication with another node because this node is beamformed in or receiving data from another direction. The receiving node location problem means the sending node must determine the location of receiving node before communication so as to decide the direction of its beam.

     To effectively solve these problems, the cross-layer design approach is used in most of directional antenna-based MAC researches. This approach tries to improve WMN capacity by coordinating MAC sublayer and physical layer.

     Directional MAC (D-MAC) protocol is a MAC protocol for directional antenna, based on IEEE 802.11 Distributed Coordinated Function (DCF). This protocol not only reduces the number of exposed terminals and improves spatial reuse by directionally sending Request to Send (RTS), DATA and Acknowledgement (ACK) frames, but also reduces the potential hidden terminals by sending the Clear to Send (CTS) frames in an omni way. This protocol uses Global Positioning System (GPS) to locate neighboring nodes.

     A tone-based directional MAC protocol[1] is proposed to address the problem of deafness. In this protocol, RTS, CTS, DATA and ACK are all transmitted directionally, and when the transmission is complete, both the transmitter and the receiver are tuned to send a tone omni-directionally to notify neighboring nodes of their availability of communication.

     Reference[2] presents a Directional Virtual Carrier Sensing (DVCS) mechanism based on IEEE 802.11 DCF. In the mechanism, a node estimates the Angle of Arrival (AOA) of each signal by measuring the received power of control frame, and then controls the beam direction. In this way, directional transmission is achieved. Besides, the node sets a proper Network Allocation Vector (NAV) for each direction.

1.2 Power Control
In the WMN, the node can dynamically control the transmit power based on the network environment, adjust the threshold of sensing to control the power, or use both of them. However, there are still some technical problems to be solved in power control. For example, how to improve spatial reuse with the network connectivity being retained; how the transmit power and the carrier sensing threshold are related to spatial reuse control; how to determine the node’s transmit power to optimize the network performance. Of these problems, the determination of each node’s transmit power is a tough one. Reducing the node’s transmit power can improve the channel’s spatial reuse, but may decrease the data transmission ratio between nodes and prolong the end-to-end transmission latency of data stream. On the contrary, increasing the power means the communication distance between nodes is extended and the transmission latency of data stream shortens, but it decreases the channel’s spatial reuse and network capacity. In addition, how to achieve a distributed power control in WMN is also a great challenge.

     The early power control research focuses on the graph model-based topology control. In the graph model, if the distance between two nodes is within the transmission range, the two nodes are neighbors and there is a connection between them. The transmission range depends on such factors as transmit power, path loss and receiver sensitivity. In this model, the objective of power control is to reduce the degree of the node while retaining the connectivity. This objective was developed on such a basic viewpoint: smaller node degree means less link interference. But recent research[3-4] shows the graph model cannot fully depict the interference between wireless links, so the Signal to Interference and Noise Ratio (SINR)-based physical models are developed to study the power control. Moreover, because the carrier sensing threshold determines the coverage of the communication node that avoids interference with other transmissions, Reference [5] proposes a power control algorithm that can dynamically adjust the physical carrier sensing threshold to maximize spatial reuse.

2 Multi-Channel Technology
The multi-channel-based WMN networking technology is the most effective means for improving WMN capacity, and has attracted great attention of researchers.

2.1 Multi-Channel MAC Model
The multi-channel MAC models can be divided into three types, as shown in Figure 2.

• Single-radio (network card), multi-channel: In this model, only one transceiver is available and only one channel of each network node is active at a time. As different nodes can simultaneously operate on different channels, the system capacity is improved.
• Single-radio, multi-transceiver, multi-channel: In this model, multiple transceivers are assigned to one radio interface and they share a group of channels. Several physical layer entities coordinate the multi-channel function via a MAC sublayer.
• Multi-radio, multi-channel: In this model, one network node has several radio interfaces with respective MAC sublayers and physical layers. The communications between these radio interfaces are independent. Therefore, a virtual sublayer protocol is required to coordinate communications between all channels on several MAC entities.
  

     In research and practical applications, the single-radio, multi-transceiver, multi-channel model is rarely used. The early research is mainly on the single-radio, multi-channel model, while recent research focuses on the multi-radio, multi-channel model, especially when the number of radio interfaces is less than that of available channels.

2.2 Multi-Channel Assignment
The main objective of channel assignment in multi-radio WMN environment is to maximize channel utility without damaging network connectivity. There are three main channel assignment schemes: fixed, dynamic and hybrid.

     (1) Fixed Channel Assignment Scheme
     In this scheme, one or several channels are assigned to one radio interface permanently or for a quite long time (relative to the handover time of the radio interface), taking no account of the topology or load change after channel assignment. This scheme is suitable for the situations where the network remains relatively stable and small change may occur in its topology and load. It can be further divided into two modes: Common Channel Assignment (CCA) and Variable Channel Assignment (VCA).

     CCA mode is the simplest. In this mode, all nodes are assigned the same group of channels. As shown in
Figure 3(a), each node has two radio interfaces and uses two identical channels. This mode is too simple to efficiently utilize network resources.

     In VCA mode, radio interfaces of different nodes will be assigned with different groups of channels, as shown in Figure 3(b). There are various factors that have impact on channel assignment, which has been taken into consideration. This assignment scheme may lead to changes in network partition or topology. Reference[6] suggests a centralized algorithm, which assigns channels in the order of load size, from the largest to the smallest. This scheme ensures the channels assigned each time are those with the smallest load, meanwhile, network connectivity and bandwidth limit of each link are guaranteed. The Connected Low Interference Channel Assignment (CLICA)[7] is a traffic-independent channel assignment scheme, which first computes the priority for each Mesh node and then assigns the channels according to connectivity graph and conflict graph.

     Reference [8] proposes two algorithms based on graph coloring problem and Max K-cut problem in graph respectively to ensure the least conflict in channel assignment. Reference [9] treats channel assignment and topology control as two independent but related problems, and thus suggests a decentralized channel assignment strategy.

     (2) Dynamic Channel Assignment Scheme
     This scheme is suitable for the situations where the network load changes dramatically. In this scheme, any channel can be assigned to any radio interface. Unlike the fixed scheme, the dynamic scheme allows a radio interface to switch from one channel to another after initial assignment. As a result, a coordination mechanism is required to ensure the nodes that involve in communication to be on the same channel.

     A typical coordination mechanism is like this: all nodes visit a pre-defined channel periodically, and negotiate on this channel the channel usage of next period. The Slotted Seeded Channel Hopping (SSCH) protocol[10] suggests another mechanism, where each node switches across channels based on a pseudo-random number, thus all neighbors can own the same channel periodically. The control channel method is also a common coordination mechanism, where one radio interface is fixedly assigned to a common channel for channel control; while other radios switch across the rest channels for data exchange. Reference [11] proposes an algorithm that dynamically assigns channels based on load change so as to increase the network throughput and get better load balance. In this algorithm, each gateway node is regarded as a root and several spanning trees are created.

     The advantage of dynamic channel assignment scheme is that a radio interface can switch across any channel, enabling few radios to use multiple channels. The main problem with this scheme lies in decision-making: when to switch across the channels and which channel to be switched across.

     (3) Hybrid Channel Assignment Scheme
     The hybrid channel assignment scheme[12] is a combination of fixed and dynamic schemes. In this scheme, some radio interfaces adopt the fixed assignment approach, while others use the dynamic approach. The radio using fixed assignment approach is assigned a special control channel or a hybrid
data/control channel, and other radios dynamically switch across channels.

3 Routing Optimization
As a multi-hop network, the WMN also suffers the capacity limitation because of interference between data streams on different paths or between the neighboring links on the same path.  However, the backbone of WMN is characterized by relatively stable topology, less power consumption restraint, multi-hop relay and convergence of traffic at the gateway, so the wireless link interference can be reduced, and the network capacity can be increased by reasonably optimizing the routing.

3.1 Selection of Routing Metric
The routing metric is the basic for routing selection. The hop-count metric, most commonly used by traditional wireless Ad hoc networks, cannot reflect the interference of multi-hop networks, and supports little for QoS, so it is not suitable for WMN. The WMN should adopt a routing metric mechanism that supports QoS. This mechanism should evaluate the link measurements based on the wireless link status and the upper-layer requirements so as to select an optimal route and effectively increase available bandwidth and capacity.

     The communication quality of wireless channel is largely affected by background noise, obstacles, channel attenuation, and interference from other communications. Often, the link layer protocol performs retransmission operations when the data frames are lost. Based on this characteristic, De Couto et al. present a routing metric “Expected Transmission Count” (ETX)[13]. EXT is the expected number of transmissions required for successful delivery of a data frame on a wireless link by the MAC sublayer of a WNM node. The EXT-based routing algorithm shows that the network throughput is improved with the frame retransmission count being reduced. The sum of EXTs of all links on the optimal path selected by this algorithm is thought to be the least.

     After studies, Koksal et al[14] point out the EXT metric cannot accurately measure the wireless channel quality because the status of the channel is time-varying. To solve this problem, they propose a new routing metric, i.e. modified EXT (mETX)[15], and introduce a parameter that reflects the quick change of channel in this metric.

     In the process of selecting the optimal path, it is also required to adopt a cross-layer coordination mechanism and take into account the requirements of both upper layers and link layer on bit error rate. For example, Transfer Control Protocol (TCP) requires that the number of retransmitting error frames on a link should not exceed pre-defined threshold; otherwise, the retransmission of the transmission layer will be initiated and the slow start mechanism of TCP will be triggered, causing the network performance to degrade. The Effective Number of Transmissions (ENT) solves this problem. Studies show the WMNs using ENT routing approach can achieve a reduction of 50% in the average packet loss rate compared with WMNs using EXT.

3.2 Load-Balancing Routing
In WMNs, lots of traffic converges at the gateway nodes. As a result, the processing capability of the gateway restricts the capacity of the entire WMN. For WMNs with multiple gateways, a key problem is how to allocate the traffic among these gateways to avoid unbalanced load. Particularly, if the gateways are of different types or the access links are with different bandwidths, the impact of these access links’ transmission capacities on the load-balancing allocation scheme should also be considered. The common strategies used in load-balancing allocation among the gateways include Moving Boundary-based Load Balancing (MBLB), Partitioned Host-based Load Balancing (PHLB) and Positional Scan Load Balancing (PSLB). In MBLB and PHLB, each Mesh node uses one gateway for access to other networks; while in PSLB, each Mesh node can simultaneously use several gateways as channels to external networks, thus in theory achieving a full load balance.

     Compared with other nodes, the nodes in the central part of WMN are apt to be overloaded because most routing algorithms are oriented to the shortest path, which often passes through these central nodes. One solution for the overload problem of central nodes is to dynamically distribute the traffic to the nodes with light load by ways of routing. Most load-balancing algorithms take ring-based routing scheme, whose basic ideas are: To divide the entire WMN into several concentric rings and each node is in one of the rings; to avoid the traffic from the source node in Ring i to the destination node in Ring j passing through the nodes in rings other than Ring i and Ring j. Currently, the ring-based load-balancing algorithms include Preferred Outer Ring Routing Scheme (PORS), Preferred Inner Ring Routing Scheme (PIRS), Preferred Destination Ring Routing Scheme (PDRS) and Preferred Source Ring Routing Scheme (PSRS). Among them, PORS and PIRS concentrate the main traffic on outer and inner rings respectively; PSRS and PDRS are integrations of both PORS and PIRS algorithms and they distribute the traffic into inner and outer rings, thus balancing the load further. As shown in Figure 4, compared with traditional shortest path algorithms, the above four algorithms can distribute the traffic in a better way and can effectively reduce the load of the central nodes.

4 Conclusion
The WMN is a special kind of Ad hoc network with a hierarchical network structure. Its backbone transmission network is characterized by multi-hop, stable topology，and less power supply constraint. Meanwhile, being a broadband wireless access network, the WMN connects other kinds of networks via its gateway nodes, leading to relative convergence of traffic at the gateways. How to improve the communication performance of the WMN is still a hot topic in current WMN research, but the critical and basic problem of WMN is to increase its capacity. In addition, some key technology problems have to be solved, including QoS guarantee, distributed network management, control mechanism and security mechanism. In spite of these problems, we still believe the WMN will be one of the main technologies for next-generation wireless networks.

References
[1] CHOUDHURY R R, VAIDYA N H. Deafness: A MAC problem in ad hoc networks when using directional antennas [C]//Proceedings of IEEE 12th International Conference on Network Protocols (ICNP’04), Oct 5-8, 2004. Berlin, Germany. Piscataway, NJ, USA: IEEE, 283-292.
[2] TAKAI M, MARTIN J, REN A, et al. Directional virtual carrier sensing for directional antennas in mobile ad hoc networks [C]// Proceedings of 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’02), Jun 9-11, 2002, Lausanne, Switzerland. New York, NY, USA: ACM, 2002: 83-193.
[3] BURKHART M, RICKENBACH P, WATTENHOFER R, et al. Does topology control reduce interference? [C]// Proceedings of 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’04), May 24-26, 2004, Tokyo, Japan. New York, NY, USA: ACM, 2004: 9-19.
[4] FUEMMELER J A, VAIDYA N H, VEERAVALLI V V. Selecting transmit powers and carrier sense thresholds for CSMA protocols [R].
Urbana-Champaign, IL, USA: Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, 2004.
[5] ZHU J, GUO X, YANG I, et al. Adapting physical carrier sensing to maximize spatial reuse in 802.11 mesh networks [J]. Wireless Communications and Mobile Computing, 2004, 4 (8): 933-946.
[6] RANIWALA A, GOPALAN K, CHIUEH T. Centralized channel assignment and routing algorithms for
multi-channel wireless mesh networks [J]. ACM Mobile Computing and Communications Review, 2004, 8 (2): 50-65.
[7] MARINA M, DAS S R. A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks [C]// Proceedings of the 2nd IEEE International Conference on Broadband Networks: Applications and Services Symposium (BroadNets’05), Oct 3-7, 2005, Boston, MA, USA. Piscataway, NJ, USA: IEEE, 2005: 381-390.
[8] SUBRAMANIAN A, GUPTA H, DAS S R.
Minimum-interference channel assignment in　
multi-radio wireless mesh networks [C]//Proceedings of  4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON’07), Jun 18-21, 2007, San Diego, CA, USA. Piscataway, NJ, USA: IEEE, 2007: 481-490.
[9] RAD A H M, WONG V W S. WSN16-4: Logical topology design and interface assignment for
multi-channel wireless mesh networks [C]// Proceedings of IEEE Global Telecommunications Conference (Globecom’06), Nov 27-Dec 1, 2006, San Francisco, CA, USA. Piscataway, NJ, USA: IEEE, 2006:1-6.
[10] BAHL P, CHANDRA R, DUNAGAN J. SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks [C]// Proceedings of 10th Annual International Conference on Mobile Computing and Networking (MOBICOM’04), Sep 26-Oct 1, 2004, Philadelphia, PA, USA. New York, NY, USA: ACM, 2004: 216-230.
[11] RANIWALA A, CHIUEH T. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network [C]// Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05): Vol. 3, Mar 13-17, 2005, Miami, FL, USA. Piscataway, NJ, SA: IEEE, 2005: 2223-2234.
[12] RAMACHANDRAN K, ALMEROTH K,
BELDINGROYER E, et al. Interference-aware channel assignment in multi-radio wireless mesh networks [C]// Proceedings of 25th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’06): Vol. 3, Apr 23-29, 2006, Barcelona, Spain. Piscataway, NJ, USA: IEEE, 2006: 1-12.
[13] De COUTO D, AGUAYO D, BICKET J, et al. A high throughput path metric for multi-hop wireless routing [C]//Proceedings of 9th Annual International Conference on Mobile Computing and Networking, Sep 14-19, 2003, San Diego, CA, USA. New York, NY, USA: ACM, 2003: 136-146.
[14] KOKSAL C E, JAMIESON K, TELATAR E, et al. Impacts of channel variability on link-level throughput in wireless networks [C]//Proceedings of ACM SIGMETRICS/Performance, June 26-30, 2006, Saint-Malo, France. 2006.
[15] KOKSAL C E, BALAKRISHNAN H. Quality aware routing metrics for time-varying wireless mesh networks [J]. IEEE Journal on Selected Areas in Communications, 2006, 24 (11): 1984-1994.
[16] BHAYA G, MANOJ B S, SIVA C, et al. Ring-based routing schemes for load distribution and throughput improvement in multi hop cellular, Ad hoc, and mesh networks [C]//Proceedings of 2003 International Conference on High Performance Computing (HiPC’03), Dec 17-20, 2003, Hyderabad, India. Berlin, Germany: Springer-Verlag, 2003: 152-161.

[Abstract] The Wireless Mesh Network (WMN) is a special kind of Ad hoc network with a hierarchical network structure. Its backbone transmission network has such characteristics as multi-hop, topology stability, no electricity supply constraints, convergence of flows. Improving the spatial reuse of spectrum is an effective approach to increase network capacity. The linchpin of this approach is to effectively control the interference range between wireless links. The multi-channel networking technology is one of the key technologies of WMN, and its core is the channel allocation through which the channel utilization can be maximized. The mutual interference between multi-hop wireless links should be considered when choosing the routing metrics in WMN. Through the load-balancing routing method, the network capacity and throughput of nodes can be improved.