ROUTING PROTOCOLS IN WIRELESS MESH NETWORKS -A COMPARISON AND CLASSIFICATION

Key words: Wireless Mesh Networks, routing, WMN, metrics Piotr OWCZAREK* Piotr ZWIERZYKOWSKI* ROUTING PROTOCOLS IN WIRELESS MESH NETWORKS - A COMPARISON AND CLASSIFICATION Wireless Mesh Networks can give an answer for many open issues in the field of wireless networks. For WMN to be effective enough, it is required for a chosen routing protocol based on routing metrics that fits application needs to be used properly. Until now, many different routing protocols have been proposed. All of them have their own characteristics and there is no easy way to make any reliable comparison. The proposed paper presents a review of the current state-of-the-art WMN routing protocols and metrics. The paper also includes an evaluation of properties and proposed classification of WMN routing protocols. Furthermore authors attempted to make a comparison of different features of selected routing metrics and characteristics of selected routing protocols. 1. INTRODUCTION Wireless mesh networks, commonly known as MESH networks, have come a long way over the past years and their popularity is soaring. One of the main contributing factors for their growing popularity is the necessity to provide broadband access to the Internet. This is particularly evident in areas where no appropriate cabling infrastructure is provided, or where costs of building such an infrastructure would exceed potential resulting benefits. A significant part of routing protocols in Wireless Mesh Networks (WMN) has been imported from Ad-Hoc networks (e.g. AODV and DSR protocols). These protocols are based on the simplest metrics, based on the number of hops in feasible paths, that are well-suited for the Ad-Hoc network, but are not particularly effective in MESH networks, because they do not take into account the quality of the link as well as the differences in technologies used in the networks in question. In the face of these differences and limitations, it is necessary to include in the consideration other __________ * Poznan University of Technology, Faculty of Electronics and Telecommunications, Chair of Communications and Computer Networks, Polanka 3, 61-131 Poznań 2 Piotr Owczarek, Piotr Zwierzykowski routing metrics, specific to mesh networks, that would make any development of new routing protocols, or a modification of existing protocols, possible. Such protocols must also satisfy a number of requirements, i.e. scalability, provision of routes without loops, speed of response to possible changes in the topology of the network, security, QoS issues and optimization of energy consumption. The article is divided into four sections. Section II presents a description of the architecture of MESH network and the metrics used in routing protocols in MESH. Section 3 includes a presentation of those selected routing protocols that are then compared in the following section 3. Finally, Section IV provides a summary of the results and the conclusions of the study. 2. WIRELESS MESH NETWORKS 2.1. INTRODUCTION MESH networks guarantee the connectivity through a multihop wireless backbone formed by stationary routers and thus provide connectivity between mobile and stationary (landline) users and are frequently used to provide access to the Internet. Wireless Mesh Networks offer many advantages such as, for example, fast and easy extension of the system, self-configuration ability, self-healing aspect, elasticity, large territorial range, better and easier area coverage (as compared to IEEE 802.11 a/b/g/n), large throughput, reliability (a failure in a single point (node) is not followed by a failure in the whole of the network) and energy conservation. Regrettably, no standard has been worked out yet and hence available solutions are most frequently incompatible with one another. Lack of appropriate routing protocols suitable for mesh networks is still an important problem. Since those metrics that are known from protocols for the Ad-Hoc network cannot be applied to mesh networks, any process of designing new protocols is substantially hindered. Therefore, a development of appropriate metrics has become an important stage in research studies aimed at working out new protocols. 2.2. METRICS USED IN WIRELESS MESH NETWORKS The metrics that have been proposed for mesh networks can be divided as follows [2],[3]:  metrics related to the number of hops (Hop Count),  metrics that determine the quality of a connection (Link Quality Metrics),  metrics that are based on network load rate (Load-Dependant Metrics),  Multi Channel Metrics. The Hop Count Metrics is the oldest type of metric that has been used in the RIP protocol since the inception of the Internet. More attention should be given then to the remaining metrics. One can distinguish seven metrics based on the link quality [4]: Expected Transmission Count (ETX)[5], Minimum Loss (ML) [8], Expected Transmission Time (ETT) [5], Expected Link Routing protocols in wireless mesh networks – a comparison and classification 3 Performance (ELP) [5], Per-Hop Round Trip Time (RTT), Per-Hop Packet Pair Delay (PPD) and Expected Transmission on a Path (ETOP). Load-Dependent Metrics include: Distribution Based Expected Transmission Count (DBEXT) and Bottleneck Aware Routing Metric (BATD). The following multi-channel metrics stand out among other multi-channel metrics: Weighted Cumulative ETT (WCETT), Metric of Interference and Channel-switching (MIC) [6], Modified ETX (mETX) [11] , Effective Number of Transmissions (ENT) [11], iAWARE – [12] and Exclusive Expected Transmission Time (EETT) [13]. Table 1. shows a comparison of selected characteristics of the metrics used in most routing protocols for mesh networks. Results shown in the table are the efects of comparison made by the authors of the article based on the available literature sources. The characteristics are given based on [3] and [7]. Table 1. A comparison of main routing metrics Name of Metric Qualityaware Data Rate Hop   ETX ML ETT ELP RTT PPD ETOP               DBEXT BATD     WCETT MIC mETX ENT iAWARE EETT             Packet Intra-flow Size Interferences Hop Count Metrics   Link-Quality Metrics               Load-Dependent Metrics     Multi-Channel Metrics             Inter-flow Interferences Medium Instability                                 2. ROUTING PROTOCOLS IN WIRELESS MESH NETWORKS Routing protocols in wireless mesh networks can be divided into two categories: proactive and reactive [1]. Proactive protocols involve a situation where network nodes continuously maintain one, or a number, of routing tables that store routes to each of the nodes of a network and, at the same time, recurrently send them along the network to exchange and update information in neighboring nodes. Reactive protocols, in turn, receive information on the route to the destination (node) of a packet only at the moment when data transmission is to be effected (on demand). These pro- 4 Piotr Owczarek, Piotr Zwierzykowski tocols do not generate additional traffic in the network, but the time needed for data to be forwarded is prolonged by the time necessary to effect the exchange of information concerning the available route. Another classification of the protocols that takes into account their particular features is proposed in [9]:  Hop Count Based Routing – protocols based the on metrics of the hop-count type. Though these protocols do not in fact indicate the most effective connection paths, they are still in common use due to their low computational complexity.  Link-Level QoS Routing – this group includes protocols that use the cumulative or the bottleneck value that defines the quality of the connection path (or section thereof).  End-to-End QoS Routing – these protocols are based on the quality parameters, but in a global approach, i.e. for the end-to-end connection path.  Reliability-Aware Routing – protocols based on the assumption of the availability of a number of simultaneous routes. In this group of protocols, depending of available implementation, packets are sent concurrently along a number of routes, or alternative routes are used only as an auxiliary solution.  Stability-Aware Routing – protocols grouped in his category use a special architecture of the system to improve the stability of the operation of a network. These protocols prefer cable connection links in MESH networks or links in which no sections (segments) that are executed via mobile users are included.  Scalable Routing – protocols for large networks where scalability is pivotal. The most typical representatives of this category are the hierarchical and the geographical routing. The classification of routing protocols proposed by the authors of the article is presented further on in the chapter. 2.1 HOP COUNT BASED ROUTING PROTOCOLS  Light Client Management Routing Protocols (LCMR) [9]. In this protocol, the destination routing path from the sender to the receiver between routers in the network is selected in the proactive way, whereas the path between clients and the routers of the network in the reactive way. In order to determine the best route, the hop-count metric is used. In this protocol, the functionality of routing is based exclusively on routers. To achieve that, routers service two routing tables: one for local clients of the network, the other for clients and remote routers. On the basis of the information they store, destination routing paths are selected. The instance of servicing two tables, however, is followed by a significant usage of resources.  Orthogonal Rendezvous Routing Protocols (ORR) [19]. The operation of this protocol is based on the assumption that in the two-dimensional Euclidean space two orthogonal lines have at least two common points with a group of other orthogonal The group of the Hop Count Based Routing protocols includes: Routing protocols in wireless mesh networks – a comparison and classification 5 lines. In the process of finding a route, the source node sends a route discovery packet in the orthogonal directions, while the destination node sends a route dissemination packet. The packets meet in a node called the rendezvous point. In this way, the end-to-end routing path is established in which the segment from the source to the rendezvous point is a reactive route, whereas the other part is a proactive route. This protocol requires a strict description of the directions towards the nodes of a network.  HEAT Protocol [20]. The HEAT protocol uses distribution of temperature. The protocol adopts that each of the nodes of a network is a source of heat. The assumption is that gateways are the warmest, followed by nodes/clients that in the closest vicinity, and that the further from gateways, the temperature becomes lower and lower. Using the temperature distribution, the protocol always sends packets to a neighboring node that has the warmest temperature, thus reaching the destination.  Dynamic Source Routing Algorithm (DSR) [23]. DSR is one of the most commonly used routing protocol in WMN networks and belongs to the group of unicast reactive protocols. The protocol uses source routing, which results in the knowledge of the whole of the destination routing path by any packet. The operation of the protocol occurs in the two consecutive stages: the route discovery phase and the route maintenance phase. The first, initiated by the source node, involves sending broadcast packets that include the destination address, the source address and a unique id to neighboring nodes. If the packet is received by a node that is not a destination node, this node adds its address to the header and then forwards the packet according to the same scheme. Thus, a packet that has reached its destination has in its header information on the end-to-end connection path. On the basis of information carried in the header, intermediate nodes collect information on routing paths. In the second phase, nodes supervise updated information on stored routes by generating error packets (RERR) forwarded towards the source node. When such a packet is received, a given router is removed from the database and further process proceeds in line with the phase one described earlier.  Ad-Hoc On-Demand Distance Vector Routing Algorithm (AODV) [21]. The AODV protocol belongs to the most popular protocols because they employ simple mechanisms of the type “question - reply” to define routing paths. For this purpose, three types of packets are used: Route Request (RREQ), Route Reply (RREP) and Route Error (RERR). The source node sends RREQ packets when a necessity to send packets arises and then intermediate nodes, provided they know the route, send a RREQ packet further on towards the destination node, whereas when intermediate nodes do not know the route, they reply with a RERR packet. This process is then repeated until the packet reaches the destination node (the node sends then a RREP packet). In the case when the node receives RREQ pack- 6 Piotr Owczarek, Piotr Zwierzykowski ets from different routes, then the route along which the packet has reached the node as first is selected. 2.2. LINK LEVEL BASED ROUTING PROTOCOLS  Link Quality Source Routing Protocol (LQSR) [22]. A reactive routing protocol proposed by Microsoft Research Group that is based on the Dynamic Source Routing (DSR) algorithm. To improve the quality of the link, the LQSR protocol employs single link parameters instead of end-to-end path parameters. In the process of setting a connection path, the protocol describes individual links by the quality metric, and then sends back the information to the node that initiates the setting up of the path. Quality parameters may vary depending on the mobility of nodes and metrics used in the process, e.g. for stationary nodes they may include strictly quality parameters such as ETX, while for mobile nodes this can be a hop-count based parameter such as RTT and ETX. Though the protocol has many advantages, it is still necessary to develop more appropriate routing metrics that would take into account the specificity of the WMN network and the features of the LQSR protocol [9].  Multi-Radio LQSR Routing Protocol (MR-LQSR) [22]. A protocol based on LQSR that takes into consideration the use of the multi-radio architecture in WMN networks. This is effected by the application of WCETT metrics that take into account both quality parameters of the link and the minimum number of hops. This protocol makes it possible to achieve the expected equilibrium (balance) between the delay and the throughput by selecting channels of best quality with a diversity of radio channels taken into account. The protocol also allows researchers to effectively compensate load among individual radio channels.  ExOR Routing Protocol [23]. This protocol is based on broadcasts from the source to the receiver without setting up a direct routing path. Forwarding of packets is done in batches from the source node to selected intermediate nodes. Intermediate nodes themselves choose which one of them will be the node that will forward the packet in the next stage of transmission. This decision depends on the cost of the link based on the ETX metric. The ExOR protocol is based on broadcasts and therefore only the parameter related to the probability of reaching the goal by the packet is taken into consideration. The choice of nodes to be involved in particular stages of the process is, in turn, executed on the basis of the packet loss ratio (PLR) between the source node and the nodes involved. In the course of the process, many nodes can receive packets from the source node and hence it is necessary to select such nodes that can become nodes forwarding packets. It is in this group of nodes that a node with the highest priority is selected and it is just this node that will be responsible for packet (batch) forwarding (according to the procedure described above). The process is completed when 90 % of packets in each Link-Level QoS Routing protocols include: Routing protocols in wireless mesh networks – a comparison and classification 7 batch is received by the destination node, while the remaining 10 % of packets is resent again in line with the protocol based on the number of hops.  AODV – Spanning Tree Protocol (AODV-ST) [22]. This protocol has been specially designed for WMN networks that use a multi-radio architecture and is based on the AODV protocol. The special feature of the AODV-ST is hybrid routing, which means that it employs AODV mechanisms for internetwork routing in WMNs and Spannig Tree (ST) between the network and edge routers. In short, AODV-ST makes advantage of proactive routing between nodes of the network and routers, and reactive routing with nodes of the internal WMN network. The AODV-ST protocol uses the ETT metric taking into account the expected time for a given packet traversing the link necessary to reach its destination.  BABEL Routing Protocol [14]. BABEL is a proactive protocol based on the distance-vector routing protocol. During the process of selection of tracks, it takes advantage of some historical information available, including the error statistics for individual links. Within this process, links that have been used earlier and their quality satisfies the assumed criteria are favored in selection. The BABEL protocol performs simultaneously updating of the state of neighboring nodes (in the reactive way) and can make an exchange of routing information (e.g. following a failure of a link) effective.  Better Approach To Mobile Ad Hoc (B.A.T.M.A.N.) [15]. A proactive protocol that shows a different approach to the selection of a connection path. Here, nodes find only the appropriate (adequate) link towards the source without taking into consideration the end-to-end route. Data are forwarded to the next node along the route, while the procedure is repeated according to the same assumption. The process is regarded to be completed when the destination node is reached. Each of nodes recurrently sends broadcasts to let the neighboring nodes about its existence. The neighboring nodes forward this information on until all the nodes in the network receive appropriate information on the other nodes in the network. 2.3. END-TO-END QOS ROUTING  Quality Aware Routing Protocol [22]. This protocol makes it possible to maintain a given loss ratio along the end-to-end connection path through appropriate use of the ETX and ENT metrics. During the selection process of feasible connection routes, the number of retransmissions is checked and then this number is compared with the maximum admissible value in the protocols of the link layer. So long as the ENT value is higher than the admissible value, the link cost is deemed as infinitely high. At the same time, the ETX metric is also used to estimate the cost of individual links and, following that, links that do not satisfy the assumed parameters are eliminated from the connection route. The most important in this protocol End-to-End QoS Routing protocols include the following protocols: 8 Piotr Owczarek, Piotr Zwierzykowski is to determine boundary quality parameters related to packet loss along the endto-end route.  RingMesh Routing Protocol [9]. The protocol is based on the Token Ring protocol for wireless LAN networks. The protocol assumes that many concurrent rings are emerging to maintain a secure service of the WMN network with a large number of hops. Individual rings are implemented in the direction from the gateway to the rest of nodes, similarly as in the case of the Spaning Tree. Another assumption is that neighboring rings use different radio frequencies. The ring that spans the gateway is treated as the root ring, whereas other rings are the so-called child rings. Individual rings always include a common node called the pseudo gateway. Subsequent nodes of the network implement further rings created according to the procedure described above and to the transmission delay criterion opposite the source node. 3. COMPARISION OF ROUTING PROTOCOLS IN WMN An unequivocal comparison of all the routing protocols presented in Chapter II is not possible due to their particular, individual-oriented features, as well as due to their different approach to the issue of routing determination methods (reactive and proactive protocols). Because of this, it is mainly comparisons of protocols representing the same group of protocols, or comparisons of protocols that are based on similar assumptions, that are to be found in the literature. Another approach to making a comparison of protocols involves their evaluation in view of objective features, i.e. delay, packet loss, overhead and throughput. Yet another approach involves a comparison of the protocols with regard to some defined features, for example, scalability, reliability of operation and traffic balancing. In [9], Akyildiz presents a comparison of structural features of groups of protocols included in his study and discusses their main features that indicate potential areas of application of the protocols in relation to required parameters. Table 2. Characteristic features of particular groups of routing protocols [9] Lp 1 Category of routing protocols Hop-count routing 2 Link-quality based routing 3 4 5 6 Interference based routing Load-balanced routing Stability based routing End-toEnd QoS Routing Features Simple in routing metric; easy to be integrated with complicated schemes of routing path selection A certain metric for link quality is used to select routing path Interference or contention is directly considered in routing Congestion or network capacity is explicitly considered Stability has higher priority End-to-end QoS is ensured Routing protocols in wireless mesh networks – a comparison and classification 9 The authors of [16] and [17] attempt, in turn, to systematize the characteristic features for routing protocols and then to compare them element by element. Table 3 shows an attempt of comparison of selected protocols described in Chapter II made by authors on base of literature studies, especially on [16] and [17] . Regrettably, it is not possible to make a viable comparison of all the presented protocols. However, it is worthwhile to mention here that the bulk of available comparative studies is based either on theoretical considerations or simulation models. In contrast, results obtained in real systems are not available and, in fact, it is such results only that would be comprehensive enough to render all features of any natural environment. An interesting approach to the issue of the methodology employed in this kind of a comparison, as well as the resulting conclusions are presented in [18]. The authors present a description of the test environment, procedures employed in the study and conclusions related to a study of four routing protocols: AODV, OSLR, BABEL and B.A.T.M.A.N. The experiments conducted by the authors were aimed at providing essential data for a comparison of the above protocols and for a selection of the best protocol with regard to a given test scenario, which in the end clearly indicates an additional dimension of difficulties for researches in making comparisons of different protocols. Reliability reactive No shortest path Yes No Yes No AODV Reactive Yes fastes & shortest path Yes No Yes No LQSR Reactive Yes Yes No Yes MRLQSR Reactive Yes Hop Mount, RTT, ETX Hop Mount, RTT, ETX Yes No Yes Type Hello Routing metrics Throughput Congestion Control Scalability DSR Protocol Load balancing Loop free Table 3. Comparison of characteristic features of selected routing protocols Yes Decreases as mobility increases Poor for more than 20 mobile nodes Yes No Yes Yes Yes Yes No 4. CONSULSIONS This article presents an overview of a number of selected metrics used in routing protocols, as well as routing protocols for WMN networks. Additionally, a comparison of selected protocols on the basis of available sources in the literature is presented. 10 Piotr Owczarek, Piotr Zwierzykowski The authors introduce a division of metrics into categories with regard to particular features of the metrics. All metrics under consideration have been grouped within the following groups: Hop Count Metrics, Link–Quality Metrics, Load-Dependent Metrics and Multi-Channel Metrics. In addition, the article includes another division of routing protocols grouped within the following categories; Hop Count Based Routing Protocols, Link Level Based Routing Protocols and End-To-End QoS Routing. It is worthwhile to notice that the above three categories are by no means exhaustive and, as a result, only some selected protocols are presented due to the complexity of this many-faceted problem. During the selection process of protocols, the popularity and common use of protocols were decisive in their inclusion. The main authors’ goal was to find features of all described protocols and their metrics that would allow to make objective comparison of selected protocols and metrics. Presented results of that comparison will be a starting point of further research for authors, which expected result is to propose new routing protocol for WMN based either on existing metrics or new designed one. The article presents a comparison of described protocols on the basis of available sources published in the literature and requires further studies which, along with experiments involving simulators, will constitute the next stage in the research agenda of the authors. REFERENCES [1] ROYER E.M., TOH C.K., A review of current routing protocols for ad hoc mobile wireless networks, Personal Communications, IEEE, 1999, 6.2: 46-55. [2] ENTEZAMI F., POLITIS C., Routing protocol metrics for wireless mesh networks, Wireless World Research Forum, 2013. [3] MOGAIBEL H.A., OTHMAN M., Review of Routing Protocols and It's Metrics for Wireless Mesh Networks, Conf. on Computer Science and Inf. Technology-Spring, 2009, 62-70. [4] DE COUTO, Douglas S.J., et al. A high-throughput path metric for multi-hop wireless routing, Wireless Networks, 2005, vol. 11, no. 4, 419-434. [5] DRAVES R., PADHYE J., ZILL B., Routing in multi-radio, multi-hop wireless mesh networks, Annual Int. Conf. on Mobile Computing and Networking, 2004, 114-128. [6] YANG Y., WANG J., KRAVETS R., Designing routing metrics for mesh networks, IEEE Workshop on Wireless Mesh Networks, 2005. [7] CAMPISTA M., Elias M., et al. Routing metrics and protocols for wireless mesh networks. Network, 2008, vol. 22, no.1, 6-12. [8] PASSOS D., at al. Minimum loss multiplicative routing metrics for wireless mesh networks. Journal of Internet Services and Applications, 2011, vol. 1, no. 3, 201-214. [9] AKYILDIZ I., WANG X., Wireless mesh networks. Wiley, 2009. [10] ASHRAF U., ABDELLATIF S., SJUANOLE G., An interference and link-quality aware routing metric for wireless mesh networks, Vehicular Technology Conference (VTC-Fall), 2008, 1-5. [11] KOKSAL C.E., BALAKRISHNAN H., Quality-aware routing metrics for time-varying wireless mesh networks. J. Selected Areas in Communications, 2006, vol. 24, no.11, 1984-1994. [12] SUBRAMANIAN A.P., BUDDHIKOT M.M., MILLER S., Interference aware routing in multiradio wireless mesh networks. In: 2nd Workshop on Wireless Mesh Networks, 2006, 55-63. [13] JIANG W., et al. Optimizing routing metrics for large-scale multi-radio mesh networks, Int. Conf. on Wireless Communications, Networking and Mobile Computing, 2007, 1550-1553. Routing protocols in wireless mesh networks – a comparison and classification 11 [14] CHROBOCZEK J., The Babel routing protocol, RFC 6126 (Experimental). Inter-net Engineering Task Force, Apr. 2011. URL: http://www.ietf.org/rfc/rfc6126.txt. [15] http://www.open-mesh.org/projects/open-mesh/wiki [16] RAO, S. Siva Nageswara; KRISHNA, YK Sundara; RAO, K. Nageswara, A Survey: Routing Protocols for Wireless Mesh Networks, IJRRWSN, 2011 vol. 1, no. 3. [17] SRIKANTH V., JEEVAN A.C., AVINASH B., KIRAN T.S., BABU S.S., A Review of Routing Protocols in Wireless Mesh Networks (WMN), Int. J. of Comp. Applications, vol. 1, no. 11, 2010. [18] FRIGINAL J., et al. Towards benchmarking routing protocols in wireless mesh networks, Ad Hoc Networks, 2011, vol. 9, no. 8, 1374-1388. [19] CHENG, Bow-Nan; YUKSEL, Murat; KALYANARAMAN, Shivkumar. Orthogonal rendezvous routing protocol for wireless mesh networks, IEEE/ACM Transactions on Networking (ToN), 2009, 17(2), 542-555. [20] BAUMANN, Rainer, et al. HEAT: Scalable routing in wireless mesh networks using temperature fields, World of Wireless, Mobile and Multimedia Networks, 2007. WoWMoM 2007. IEEE International Symposium on a. IEEE, 2007, 1-9. [21] PERKINS, Charles E.; ROYER, Elizabeth M. Ad-hoc on-demand distance vector routing, Mobile Computing Systems and Applications, 1999. Proceedings. WMCSA'99. Second IEEE Workshop on. IEEE, 1999, 90-100. [22] CAMPISTA, Miguel Elias M., et al. Routing metrics and protocols for wireless mesh networks, Network, IEEE, 2008, 22(1), 6-12. [23] JOHNSON, David B.; MALTZ, David A. Dynamic source routing in ad hoc wireless networks, Kluwer International Series in Engineering and Computer Science, 1996, 153-179. [23] BISWAS, Sanjit; MORRIS, Robert. ExOR: opportunistic multi-hop routing for wireless networks, ACM SIGCOMM Computer Communication Review. ACM, 2005, 133-144.