Scalability Technologies for Wireless Mesh Networks

This work was funded by Special Standardization Foundation of the Science and Technology Commission of Shanghai Municipality under Grant 07DZ05018, and the Natural Science Foundation of Shanghai Municipality under Grant 07ZR14104.

     The global mobile voice services have been a great success along with the wide use of mobile networks such as the Global System for Mobile communication (GSM) in the past 20 years. Nowadays along with the development of technologies, the mobile communications demands obviously speed up the provisioning of new data services besides voice services. These data services have a more urgent requirement of a high transmission rate, broad coverage and good end-to-end Quality of Service (QoS). Technologies for Wireless Mesh Network (WMN) develop rapidly based on traditional cellular communications and Ad hoc technologies, and have attracted more and more attentions from industry and academe[1-2].

1 Wireless Mesh Network Overview
Figure 1 illustrates a WMN, an Ad hoc network and a cellular network. This figure shows that most of the features of the WMN are similar to those of the Ad hoc network, such as self-organizing, self-roaming and self-recovery, so it has an open Mesh network architecture. However, not all of the nodes in the WMN are equal as they are in the Ad hoc network, and they are classified into Mesh Base Stations (BSs) and Mesh Mobile Stations (MSs). The Mesh BS has much more functions than the Mesh MS, and performs more network management and maintenance and data relay transmission tasks than Mesh MS. In other words, the wireless Mesh BS is the fixed cluster head in the WMN, whereas the cluster head in Ad hoc network is temporary[3]. So, viewed from this point, the WMN can be regarded as a communications network between the cellular network and wireless Ad hoc network. It integrates the centralized management features of the traditional cellular networks while retaining the flexibility of the Ad hoc network. Table 1 lists the features of the three wireless networks.

     A key factor that affects the rapid development of WMN is spectrum. A large number of multimedia services require data transmission at a higher rate along with the development of wireless communication services, so a greater bandwidth is required. Although new transmission technologies, such as Multiple-Input and Multiple-Output (MIMO), Adaptive Modulation and Coding (AMC) and the dynamic spectrum sharing technology, can improve the spectrum efficiency to an extent and thus meet the requirement for spectrum temporarily, however, it is still a problem in the future.

     The spectrum allocation in the last World Radiocommunication Conference showed an increasing density of
low-end spectrum used, so if radio communication systems require larger continuous or symmetric spectrum in the future, it will have to support transmission at higher frequencies[4].

     Wireless signals are attenuated faster at high frequencies, so the coverage of each BS is smaller with the same transmission power. In addition, it is also unpractical to increase the BS transmission power only because of its effect on the human life besides technical and cost factors.

     In this situation, the multi-hop transmission, which is a feature and an advantage of WMN, plays its role. Especially in a city with a dense population and lots of tall buildings, where signals cannot cover all of the areas due to building blocking, a WMN can be used to ease the problem.

     The WMN has an open network architecture and, theoretically, high scalability. However, in actual systems, the WMN faces many practical problems. Even the existing wireless Mesh related standards, such as IEEE 802.11 (Wi-Fi), IEEE 802.15 (Bluetooth and ZigBee) and IEEE 802.16 (WiMAX), cannot provide any specific, practical networking solutions[5]. One of the important reasons is that the network capacity decreases as the number of nodes increases in wireless Ad hoc networks. Reference [6] shows that the average capacity of each node in an Ad hoc multi-hop network is proportionate to O (1/  n logn ), in which n indicates the number of nodes. But in WMN, the average capacity of each node is proportionate to O (1/n ) due to the restriction of the central gateway[7]. Therefore, it is hard to establish large-scale WMNs, which require more powerful hardware facilities and more efficient protocol support.

     This paper focuses on the technologies related to the WMN scalability for the purpose of increasing its adaptive networking capability.

2 Scalability Technologies for Wireless Mesh Networks
In WMN, increasing network capacity is incompatible with improving the coverage due to the factors such as
multi-hop transmission. So the goal of the scalability technologies study for WMNs is to extend the coverage while maintaining the capacity. To achieve this objective, the scalability of both Mesh BS and Mesh Ms should be studied. There are more researches on the Mesh MS scalability, which is similar to the scalability in the Ad hoc network, but the Mesh BS scalability is more important because Mesh BS is the backbone node in the Mesh network.

2.1 Mesh BS Scalability
According to the characteristics of wireless Mesh BSs, scalability technologies mainly include channel allocation, intelligent routing, and multi-antenna technologies.

     (1) Channel Allocation

     Nodes in WMNs support single-channel and multi-channel transmission. However, single-channel transmission may cause complex co-channel interference problems and worsen the problems of hidden and exposed terminals in wireless Ad hocnetworks. It is obvious that in Ad hoc networks, nodes requiring a large gateway hop count have a low access rate because the averagely allocated bandwidth is small. Although the problem can be eased through frequency reuse when the hop count is very high, the bandwidth distributed to the nodes in the case of single-channel transmission can only reach a value between 1/2m and 1m (m denotes the hop count), with additional severe access unfairness. The wireless Mesh BS plays a role of the backbone node, so multi-channel transmission is almost absolutely necessary. In actual systems, wireless Mesh BSs are generally designed in a multi-mode configuration, that is, they support transmission in multiple air interfaces (such as IEEE 802.11a/b/g), thus meeting the actual requirement.

     In the case of multimode, channel allocation is now regarded as the key technology, which is practical and effective for WMNs. However, channel allocation must consider both Mesh BS and Mesh MS. Generally, the
IEEE 802.11a interface is used for the transmission between Mesh BSs, and IEEE 802.11b/g interfaces are used for the communication between Mesh BSs and the Mesh MSs they cover. Therefore, reasonable frequency coordination and planning are required for adjacent Mesh BSs. On the IEEE 802.11a interface, eight non-overlapping channels can be used in the ranges of 5.25—5.35 GHz and 5.725—5.825 GHz, so transmission between adjacent Mesh BSs can be allowed through different channels. Reference [8] concludes channel allocation problems in WMNs in details and points out the problems and challenges in the channel allocation.
With consideration of Mesh BS scalability, when a new Mesh BS attempts to access an existing Mesh network, a reasonable channel allocation solution is also very important besides a highly effective access technology. A practical method is to obtain channels through Carrier Sense Multiple Access (CSMA). In addition, the nearer a Mesh BS is to the gateway, the more data it requires to relay, therefore, it should have a higher channel access priority. A reasonable channel allocation can reduce the probability of conflict, lower interference and decrease time delay, and thus improve the scalability of wireless Mesh BSs.

     (2) Intelligent Routing
     Intelligent routing is the core technology for the wireless multi-hop network, in which routing algorithm directly affects the performance of the entire WMN. The largest difference between WMN and Wireless Local Area Network (WLAN) is the routing function. Researches on the routing protocols for the Ad hoc network have made many achievements after years of efforts. Many typical routing algorithms are developed, including proactive routing, reactive routing, and hybrid routing protocols. The overhead of routing protocols must be minimized because of network capacity restriction, but since the node mobility causes network topology changes, frequent signaling transmissions are required for fast route update. The routing function in the WMN is provided by Mesh BSs, so routes in the WMN are relatively fixed, however, the flexibility of routing is restricted.

     Since Mesh BSs provide most of the routing function in the WMN, intelligent routing protocols must be designed with consideration of this factor. In addition, intelligent routing protocols must consider the service bearer on each Mesh BS, which is helpful for load balance to some extent. Load balance is actually an important index to measure network fairness. Moreover, Mesh BSs must consider forwarding information from remote nodes at a higher priority upon data transmission to ensure the fairness of the transmission delay between remote nodes and near-end nodes during multi-hop relay.

     (3) Multi-Antenna
     Multi-antenna technologies have been developed rapidly in the mobile communications field in the past ten years, and have been widely used in WMNs. Multi-antenna technologies provide the following functions:

• Increasing the WMN capacity;
• Improving network routing performance;
• Optimizing network energy consumption;
• Assisting node positioning;
• Improving the capability to provide QoS assurance for users.
  

     In addition, multi-antenna technologies can increase capacity and coverage and thus greatly improve the scalability of the WMN.

     A Mesh BS may have multiple antennas and Radio Frequency (RF) modules, so it can use beamforming and Space Division Multiple Access (SDMA) technologies. Reference[9] shows that the beamforming technology used on the transmitting or receiving end can get a capacity gain of   2πα or   2πβ, respectively, in which α  and β are the antenna beam width on the transmitting and receiving ends respectively. When both the transmitting and receiving ends use a beamforming technology, a capacity gain of   2παβ can be achieved. Beamforming technologies can also improve the Mesh BS coverage, which reduces the hop count in routing and improves network scalability. In addition, SDMA technologies divide transmission channels by space, thus providing more available channels and improving the Mesh BS access rate.

2.2 Scalability Technologies for Mesh MS
The Mesh MS scalability refers to the coverage extension with capacity assurance in an area where a Mesh BS is the core. Main technologies involved include channel allocation, node classification, QoS differentiation, and cooperative transmission.

     (1) Channel Allocationaaaaaaaaaaaaaaaa
To improve the performance of multi-hop networks, MSs in the future WMNs can be multimode, for example, configured with IEEE 802.11b/g. IEEE 802.11b/g has three non-overlapping channels at 2.4 —2.4835 GHz. This allows Mesh MSs to use different air interfaces or run on different channels for the interconnection and interworking between Mesh BSs. A practical channel allocation scheme is to divide the coverage of a Mesh BS, which is located at the center, into multiple circles, and use different air interfaces between each circle. When a new Mesh MS accesses the network, a suitable transmission channel is determined according to its position. The key point of the scheme is to consider the number of circles that a Mesh BS can serve and the reasonable distance between each circle. In addition, similar to the situation of Mesh BS, since the nearer a Mesh MS is to the Mesh BS, the more data it requires to relay, generally it should have a higher channel access priority. Moreover, Mesh MSs must consider forwarding information from remote Mesh MSs at a higher priority upon data transmission to ensure the fairness of the transmission delay between remote nodes and
near-end nodes.

     (2) Node Classification and QoS Differentiation
     WMNs must work properly in both of the two cases: low and high density of nodes. However, as mentioned before, transmission delay increases in the case of high-density nodes. To solve the problem of Mesh MS scalability, Reference [10] addresses a dynamic adaptive algorithm to reduce the conflicts between nodes. The subject of the algorithm is node classification. Different nodes are configured with different access priority coefficients. This controls the access conflicts between nodes effectively, which ensures more effective transmission, lowers transmission time delay, and effectively improves the scalability of WMNs with a high density of nodes.

     Reference [11] addresses a QoS differentiation to improve WMN scalability. It abstracts the next accessible time length and the required waiting time of Mesh node in the IEEE 802.16 protocol, and associates them with the transmission service QoS. That is, different next-accessible time length and required waiting time are set for services requiring different QoS. The scalability of Mesh networks with a high density of nodes can be improved through QoS differentiation and conflict indication setting.

     (3) Cooperative Transmission
     Generally, unlike on Mesh BSs, it is very difficult to configure multiple antennas on Mesh MSs. Even if two antennas are configured on a Mesh MS, they use the same RF module. The Mesh MS gets limited space diversity gain by selecting a transmitting antenna. However, multiple Mesh MSs can use a cooperative transmission technology to get greater diversity gain[12]. For example, multiple Mesh MSs can support transmission by forming a virtual multi-antenna system, which is called virtual MIMO technology. In addition, multiple Mesh MSs can also support transmission through cooperative coding, which can also provide certain diversity gain. With the open architecture of WMN, cooperative transmission technologies can increase the transmission rate and transmission range of Mesh MSs, which is important especially for the Mesh MSs far away from Mesh BSs. So cooperative transmission improves the scalability of Mesh MSs. Suitable user pairing is vital in cooperative transmission. It is necessary to maximize the throughput of cooperative users while maintaining the fairness between users[13].

3 Conclusion
The scalability of WMNs is an extraordinary problem due to the inherent weak points of the Ad hoc network. This paper discusses the key technologies for the scalability of Mesh BSs and Mesh MSs, including channel allocation, intelligent routing and multi-antenna technologies for Mesh BSs, and channel allocation, node classification, QoS differentiation and cooperative transmission technologies for Mesh MSs. However, the implementation of the abovementioned key technologies still faces many challenges. Especially, the implementation of many physical-layer technologies requires the assistance of relevant media access control layer protocols, for example, the beamforming and SDMA technologies for the Mesh BS. So the across-layer optimization of the Mesh network requires further research.

References
[1] AKYILDIZ I F, WANG Xudong, WANG Weilin. Wireless Mesh networks: a survey [J]. Elsevier Computer Networks, 2005, 47 (4): 445-487.
[2] ZHANG Yan, LUO Jijun, HU Honglin. Wireless Mesh networking: architectures, protocols and standards [M], New York, NY, USA: Auerbach Publications, Taylor and Francis Group, 2006.
[3] 郑少仁, 王海涛, 赵志峰. Ad Hoc网络技术 [M]. 北京: 人民邮电出版社, 2005.
[4] World Radiocommunication Conference 2007
(WRC-07) [EB/OL]. http://www.itu.int/ITU-R/ index.asp? category=conferences&link=wrc-07.
[5] IEEE 802 LAN/MAN Standards Committee [EB/OL]. http://www.ieee802.org.
[6] GUPTA P, KUMAR P R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory, 2000, 46 (2): 388-404.
[7] JUN J, SICHITIU M L. The nominal capacity of wireless Mesh networks [J]. IEEE Wireless Communications, 2003, 10 (5): 8-14.
[8] SKALLI H, GHOSH S, DAS S K, et al. Channel assignment strategies for multiradio wireless Mesh networks: Issues and solutions [J]. IEEE Communications Magazine, 2007, 45 (11): 86-95.
[9] YI S, PEI Y, KALYANARAMAN S. On the capacity improvement of Ad hoc wireless networks using directional antennas [C]// Proceedings of 4th ACM International Symposium on Mobile Ad hoc Networking and Computing (MOBIHOC’2003), Jun 1-3, 2003, Annapolis, MD, USA. New York, NY, USA: ACM, 2003: 108-116.
[10] CAO M, MA W, ZHANG Q, et al. Modeling and performance analysis of the distributed scheduler in IEEE 802.16 Mesh mode [C]// Proceedings of 6th ACM International Symposium on Mobile Ad hoc Networking and Computing (MOBIHOC’2005), May 25-28, 2005, Urbana- Champaign, IL, USA. New York, NY, USA: ACM, 2005: 78-89.
[11] HU Honglin, ZHANG Yan, CHEN H H. An effective QoS differentiation scheme for wireless Mesh networks [J]. IEEE Network, 2008, 22 (1): 66-73.
[12] HU Honglin, LUO Jijun, CHEN H H. Radio resource management for cooperative wireless communication systems with organized
beam-hopping techniques [J]. IEEE Wireless Communications, 2008, 15(2):100-109.
[13] CHEN Xia, HU Honglin, WANG Haifeng, et al. Double proportional fair user pairing algorithm for uplink virtual MIMO systems [J]. IEEE Trans. Wireless Communications, Accepted for publication, 2007.

[Abstract] The continuous increase of data transmission density in wireless mobile communications has posed a challenge to the system performance of Wireless Mesh Networks (WMNs). There is a rule for wireless Ad hoc networks that the average node capacity decreases while the number of nodes increases, so it is hard to establish a large-scale wireless Mesh network. Network scalability is very important for enhancing the adaptive networking capability of the wireless Mesh network. This article discusses key scalability technologies for Mesh Base Stations (BSs) and Mesh Mobile Stations (MSs), such as channel allocation, intelligent routing, multi-antenna, node classification, Quality of Service (QoS) differentiation and cooperative transmission.