International Journal of Networks and Communications

2012;  2(2): 1-6

doi: 10.5923/j.ijnc.20120202.01

Enhancing Performance of MAODV Routing Protocol for Wireless Mesh Network using Integrated Multiple Metrics Technique (IMMT)

Farhat Anwar 1, Aisha Hassan Abdalla 1, S. M. Sadakatul Bari 1, Md. Akhtaruzzaman 2, Mosharrof Hussain Masud 1, Jannatul Naeem 1, Md. Saiful Azad 1, Md. Arafatur Rahman 1

1Department of Electrical and Computer Engineering (ECE), Kulliyyah of Engineering, International Islamic University Malaysia (IIUM), 53100 Kuala Lumpur, Malaysia

2Department of Mechatronics Engineering (MCT), Kulliyyah of Engineering, International Islamic University Malaysia (IIUM), 53100 Kuala Lumpur, Malaysia

Correspondence to: Md. Akhtaruzzaman , Department of Mechatronics Engineering (MCT), Kulliyyah of Engineering, International Islamic University Malaysia (IIUM), 53100 Kuala Lumpur, Malaysia.

Email:

Copyright © 2012 Scientific & Academic Publishing. All Rights Reserved.

Abstract

Customarily, the design of an efficient routing protocol for Wireless Mesh Networks (WMNs) demands sufficient consideration of the pertinent features. This is due to the fact that WMNs can be permanent or semi-permanent networks. Moreover, a reliable path from the source to the destination can be maintained using an improved and better performance metrics. Currently, the most widely used performance metric is the minimum hop-count which is based on the assumption that communication links are either working well or not working at all. This assumption is true for wired networks however this is impractical for wireless networks where numerous links suffer from intermediate loss ratios, low throughput, interference and other inherent limitations. Consequently, researchers have proposed a number of performance metrics for WMNs. It has also been shown that integrating multiple performance metrics into a routing protocol is effective for attaining optimal performance since it is highly probable that a single performance metric will not be able to satisfy the comprehensive requirements of WMNs. This paper presents a technique of integrating multiple routing metrics in order to optimize the performance of a routing protocol. The proposed technique is implemented on Multicast Ad-hoc On-Demand Distance Vector (MAODV) routing protocol. Simulation results show a statistically significant performance improvement over standard MAODV for WMNs.

Keywords: Wireless Mesh Networks, MAODV, Performance Metrics, Routing Protocol, IMMT, WMN

1. Introduction

Wireless Mesh Networks (WMNs) is gaining more attention from researchers and industrialists as an emerging technology with a plethora of applications. WMNs are dynamic networks with the ability to self-organize and self-configure of the nodes in such a way that an ad-hoc network is automatically established and mesh connectivity is maintained [1]. The constituents of WMNs are mesh clients and mesh routers which form the backbone of the network due to their limited mobility capability. In addition to this, mesh routers provide network access to both mesh and conventional clients. On the other hand, mesh clients can be stationary or mobile and they also have the ability to form a client mesh network [1, 2].
WMNs employ broadcast mechanism which is useful and applicable in applications where one-to-many and many-to- many communications are required. Route discovery among nodes can be achieved by using multicast routing protocols which help to facilitate communication between nodes. Multicasting is highly essential since it mitigates the overheads associated with unicast routing protocol. Furthermore, multicasting offers considerable improvement in terms of network capacity by utilizing links that are shared by multiple users to receive the same data which is transmitted once [2,3].
Distance Vector Multicast Routing Protocol (DVMRP) is the first protocol designed for multicasting in Layer 3 of TCP/IP protocol stack. After this, a number of protocols were designed such as Multicast Open Shorted Path First (MOSPF), Core Based Trees (CBT) and protocol-independent multicast routing protocol for sparse and dense networks [4-9].
As a result of dynamic topological changes, routing is comparatively more challenging in ad-hoc networks than typical wired networks. This is because routing must address a wide range of issues like energy consumption, bandwidth limitation and other constraints. In order to support multicasting in this scenario, researchers have proposed a number of protocols such as Multicast Ad-hoc On-Demand Distance Vector (MAODV) [3] protocol, Ad-hoc Multicast Routing Protocol (AMRoute) [10], On-Demand Multicast Routing Protocol (ODMRP) [11] and Core-Assisted Mesh Protocol (CAMP) [12].
Multicast routing protocols can be classified into two categories, namely; proactive and reactive multicast routing protocols. Proactive protocols establish routes to nodes in multicast group and also to nodes which are not in any multicast group [2]. Another name for proactive techniques is table-driven methods. Examples of proactive multicast routing protocol are DVMRP, MOSPF, PIM, etc. On the other hand, reactive techniques focus on data transmission. Routes between hosts are ascertained only when they are needed for forwarding data packets. Reactive techniques are also known as on-demand methods. Examples of reactive techniques are ODMRP, MAODV and other pertinent protocols. There is another classification known as hybrid techniques which are combination of proactive and reactive methods [2,3,11].
The rest of the paper is organized as follows: Section 2 reviews the related work pertaining to this research work. Section 3 describes the proposed Integrated Multiple Metrics. Section 4 discusses the simulation work and section 5 presents the results together with discussions of the results. Section 6 concludes this paper.

2. Preliminaries

MAODV protocol is the multicast adaptation of AODV [3]. The protocol is based on creating group trees which are shared by sources and sinks for a given multicast group. The multicast group sequence number is maintained by the root of each group tree which is also chosen as the group leader. A broadcast route discovery mechanism is employed by MAODV to discover multiple routes. Whenever a mobile node wants to join a multicast group, a route request message is broadcasted. Afterwards, a multicast member node or group leader will respond to this request message with a route reply message. Route is determined based on the latest sequence number if source node receives multiple reply messages whereas route is decided based on the least hop count if the sequence numbers are identical. Afterwards, the multicast state between the newly joined receiver and shared tree is set up by the source node through a multicast activation (MACT) message. Hello packets are broadcasted to maintain link connectivity. Link repair mechanism is maintained by the downstream node [3].
Hop Count: Hop count is utilized to select minimum path by most of the traditional routing protocols developed for wired and wireless networks [13,14,15]. This technique is simply implemented by counting the number of hops along the path to the specified destination. One of the advantages of this metric is the simplicity in implementing it. However, it has been found that hop count finds route with considerably less throughput for wireless networks [16].
MAODV and other routing protocols designed for WMNs implement quality-aware performance metrics in order to optimize the performance of the entire network. Performance metrics which are widely accepted and widely used for research in communication networks are discussed in the following subsections:

2.1. Expected Transmission Count (ETX)

This metric was proposed with the aim of achieving high throughput for multi-hop wireless networks by considering link quality [16]. This metric is measured by the expected number of transmissions taken for a single packet to be transmitted over a given communication link. ETX is calculated using the following equation:
(1)
Where df and dr are the forward packet delivery ratio and reverse packet delivery ratio respectively. To measure delivery ratio, each node broadcasts link probes of a fixed size, at a fixed interval. ETX improves the throughput and efficiency of the network for homogeneous single-radio environments but not perform well for multi-radio and heterogeneous network.

2.2. Expected Transmission Time (ETT)

ETT is the modified version of ETX in which expected numbers of transmission as well as packet size and link bandwidth are considered [17]. The ETT of a link is calculated using the following equation:
(2)
Where S denotes the size of the packet and B denotes bandwidth of the link .However, ETT may select noisy path because it does not consider intra-flow or inter-flow interference.

2.3. Weighted Cumulative Expected Transmission Time (WCETT)

To minimize the intra-flow [17] proposed another metric WCETT which reduce the number of nodes on the path of a flow that transmit on the same channel. For a path P, WCETT is defined as,
(3)
Where α is the tuneable parameter (0 ≤ α ≤ 1), Tj is the number of times channel j is used along path P. However, it does not capture inter-flow interference .Moreover, WCETT is not isotonic.

2.4. Round Trip Time (RTT)

In [18] RTT metric is proposed which is calculated based on the round trip delay seen by unicast probes between neighboring nodes. A node sends a probe packet carrying a timestamp to each of its neighbors every 500 milliseconds. After receiving a probe packet, each neighbor immediately responds to the probe with a probe acknowledgement, echoing the timestamp. This enables the sending node to measure RTT to each of its neighbors.
In wireless mesh networks, a single-hop or multi-hop path needs to be selected to forward data from a source node to a destination node. This path/route selection is performed based on a metric. Since each individual routing metric consider some minimum and related features and it is difficult to satisfy comprehensive requirements of WMNs by using a single metric, therefore, we proposes an incorporated multiple metrics technique in this paper. Three performance metrics have been considered, that includes Expected Transmission Count (ETX), Round Trip Time (RTT) and traditional Hop Count, which guarantees a minimum hop count with loop free routing and avoids highly loaded and lossy links. ETX is used to avoid lossy link, whereas RTT is used to avoid highly loaded links.

3. Incorporating Multiple Metrics Value (IMMV)

A modified version of ETX is implemented, where only loss probability in reverse direction, Pr is considered to simplify the calculation and to keep the routing overhead analogous to the implemented protocol. Therefore, probability that the packet transmission of a link is not successful can be defined from Equation (4):
(4)
Where, P denotes the probability that the packet transmission from x to y is not successful. Finally, the expected number of transmissions required to successfully deliver a packet from x to y is denoted by ETX:
(5)
The ETX path metric is the sum of the ETX values for each link in that path.
To calculate RTT, a node unicast one probe packet after certain fixed period, carrying a random timestamp to each of its neighbors. This enables the receiving node to calculate round trip time to each of its neighbors. The RTT value for any node is calculated using Equation (6):
(6)
Where Pkt→RTT is the value of the packet carry and PrevHop→RTT is the delay time for the neighbor node.
If only one path exists between source and destination, that path is the default choice for the source who initiated route discovery. However, if there exist two or more paths, an incorporated multiple metrics value (IMMV) is calculated to select the best path among them. The IMMV for a route can be calculated using Equation (7):
(7)
Where, IMMVi and IMMVj are calculated for routes i and j. Among these two paths, the path which has lower IMMV value will be selected.
To incorporate the new integrated multiple metrics technique on MAODV, we modified MAODV as follows. ETX is calculated using the HELLO packets transferred between neighbors. In MAODV, one HELLO packet is broadcasted in every 1000 milliseconds or one second. After receiving one HELLO packet, a node counts the number of HELLO packets received from that neighbor in the previous 10 seconds. Based on these probes packets, the loss rate of probes on the links is calculated. For example, consider two nodes x and y. Assume that node x has received 9 probe packets from y in the previous 10 seconds. Thus, the loss rate from y to x is 0.1. Hence, the expected number of transmissions before the packet is successfully delivered is 1/(1-0.1) = 1.11. This is the value of the ETX metric for the link from x to y.
RTT value is calculated using Equation (6) where Pkt→RTT is the value of RREQ or RREP packet carry and PrevHop→RTT is the delay time for the neighbor node. Here we consider only one way delay between source and destination, not the traditional two ways RTT. Therefore, we can avoid the extra overhead which is generated by sending packet from source to destination to calculate traditional RTT. By using this three routing metrics we can get a reliable path which grantees a minimum hop count with loop free routing that avoids highly loaded and lossy links.
The core functionalities of the proposed enhanced protocol remain analogous to its predecessor MAODV protocol. It differs from MAODV in such a way that multiple metrics are considered for selecting the reliable path in route discovery process. Alike MAODV, the proposed enhanced protocol also uses the Route Request (RREQ) and Route Reply (RREP) packets for the route discovery and route maintenance processes, except that the RREQ and RREP packet format is modified to carry additional information essential to support multi-metrics implementation.
Every node running MAODV maintain two routing table. We added two fields named ‘ETX to Destination’, and ‘RTT to Destination’ in route table. Moreover, we also made changed in Neighbor Table to records the costs of the links from its neighbors to itself. In the modified MAODV, each node looks up the neighboring table for the cost of the link from which it receives the route reply packet and using this link cost, it updates the cost in the reply packet before redirecting to the source node. Since all the neighbors of a node are one hop away, Hop Count field is not necessary in the neighboring table. Hence, in the Neighbor Table, address of all the neighbors and their respective ETX and RTT values are stored.

4. Route Discovery Process

Two fields are added to the Route Request and Route Reply packet format. The Route Error packet format is left unchanged. Similar to traditional MAODV protocol, sequence numbers are used to ensure the freshness of the routes avoiding routing loops in the network.
a) Route Requests: When a node wishes to join a multicast group or to find a route to a group of which it is a member, it generates one Route Request (RREQ) packet and broadcasts. When a node receives the RREQ, it creates or updates a reverse route which is needed in case the node receives an eventual RREP back to the node which originated the RREQ (identified by the Source IP Address). In addition, it also creates a next hop entry for the multicast group in its multicast route table. The activation flag for the next hop is left unset and the direction for this next hop entry is DOWNSTREAM. If it does not fulfil the criteria of generating Route Reply (RREP) packet, it updates necessary information in RREQ packet and broadcasts the request to its neighbors. In the modified RREQ packet, ETX and RTT fields are included and all other fields remain similar to MAODV. In Fig. 1, necessary portion of RREQ partial packet format is given.
Figure 1. RREQ packet format (Partial)
b) Route Replies: When a node (intermediate node or destination) determines that it can respond to the RREQ, it creates a RREP and unicasts the RREP to the source node. In Fig. 2, modified RREP packet (partial) format is depicted. Since this RREQ is a join RREQ, only a node that is a member of the multicast tree may respond to the RREQ. As RREP is generated by the multicast member, it will initialize the Hop Count, ETX and RTT fields of the RREP to zero. These fields are incremented each time the RREP is forwarded, so that when the source node receives the RREP, it indicates the source’s distance from the multicast tree.
Figure 2. RREP packet format (Partial)
If a node receives a RREP in response to a RREQ that it has transmitted, it creates a multicast group next hop entry for the node from which it received the RREP and direction is set to UPSTREAM. The Activated flag is left unset. If the node receives another RREP packet after it forwards the first RREP towards the source of the RREQ, it will forward the later RREP only if it has a greater sequence number or has lower IMMV (if sequence number is equal) than the one in routing table. Fig. 3 shows the pseudo code of the selection procedure.
Once all the necessary updates are completed, intermediate node forwards the RREP to the source. After transmitting the RREQ, the subscribing node waits until the discovery period is finished before selecting a route. During this period, it keeps track of the best route (greatest sequence number and/or lower IMMV if sequence number is equal). At the end of discovery period, the subscribing node selects its next hop and activates that hop.
Figure 3. Pseudo code of the route selection.

5. Simulation Environments

QualNet version 4.5 simulator [19] is used to perform the simulation. In this simulation, we consider a network of 30 nodes that are placed randomly within a (1000m * 1000m) area and operating over 100sec. As mesh networks are permanent or semi-permanent networks, all the nodes are considered stationary in this simulation. Multiple runs with different seed numbers are conducted for each scenario and collected data is averaged over those runs.
A two-ray propagation path loss model is used in our experiments with lognormal shadowing model. The transmission power of the routers is set constant at 20 dBm and the transmission range of the routers is 200 meters. The data transmission rate is 2Mbits/s. At the physical layer 802.11b and at MAC layer MAC 802.11 is used. Table 1 represents the summary of a simulation environment to test the proposed technique.
Table 1. Summary of simulation environments
ParametersValue
Network size30 nodes over 1000m x 1000m area
Path loss modelTwo-ray propagation model
Transmission rate at PHY2 Mbps
Physical layer protocolPHY802.11b
Data link layer protocolMAC802.11
Queue size at router50KB
Queuing policy at routerFirst-in-First-out
Multicast group size{10, 30} nodes
Traffic model of SourcesMulticast Constant Bit Rate (MCBR)
Number of MCBR source1
Multicast Traffic Flow{10, 20, 30, 40, 50, 60} packets/sec
Duration of Each Experiment100 sec
Data Transmission Start10 sec
Data Transmission Stop90 sec
Number of Runs Per Data Point10
Multicast Routing ProtocolMAODV, MAODV-IM
The traffic source is implemented using Multicast Constant Bit Rate (MCBR). The packet size without header is 512 bytes. The length of the queue at every node is 50 Kbytes where all the packets are scheduled on a first-in-first-out (FIFO) basis. The senders and receivers are chosen randomly among multicast members. A member joins the multicast session at the random time and remains as a member throughout the simulation. In our simulation, multicast source starts sending data after 10sec. Once joining the multicast group, we let the source to transmit data for 90s simulation time and remaining 10s is set to allow the last packets to be processed and routed to the destination. Fig. 4 shows an example scenario of the test environment.
To evaluate the performance of enhanced MAODV protocol, three different quantitative metrics are used, they are: multicast packet delivery ratio (PDR), average end-to-end delay and throughput [1]. The performance differentials in this simulation are investigated using varying traffic load for 10 receivers. Traffic load is varied from 10 packets/sec to 60 packets/sec, where it is increased by 10 packets/sec.
Figure 4. Scenario design of the simulation

6. Results and Discussions

The proposed MAODV enhancement is named as MAODV-IM for this result discussion section. In Fig. 5 (a), multicast packet delivery ratio obtained for MAODV and MAODV-IM is shown. At the beginning, when traffic load was low i.e. 10 packets/sec, both protocols display almost same delivery ratio. However, MAODV-IM starts performing better than its counterpart while the traffic load is increased, since proposed protocol selects reliable path and avoid highly loaded and lossy links which original MAODV do not support. For instance, when multicast traffic load is 60 packets/sec, PDR of MAODV-IM is 11.49% higher than traditional MAODV. Therefore, MAODV-IM outperforms MAODV with respect to multicast PDR.
Fig. 5(b) demonstrates the average end-to-end delays from the source to the destination’s application layer. It can be observed that end-to-end delay of MAODV-IM is better than MAODV. For example, when multicast traffic load is 60 packets/sec, Average end-to-end delay of MAODV-IM is 15.2% less than traditional MAODV. Since MAODV-IM avoids highly loaded and lossy links in case of higher traffic load, its end-to-end delay is comparatively less than MAODV. Fig. 5(c) shows the average throughput comparison for MAODV and MAODV-IM. The simulation result shows that both protocol performance similar when low traffic load. But in high traffic load, the average throughput of MAODV-IM is higher than MAODV. For example, when multicast traffic load is 60 packets/sec, Average throughput of MAODV-IM is 7.64% higher than traditional MAODV. This is because MAODV-IM avoids the loaded and lossy links.
Figure 5. Performance of MAODV and MAODV-IM with respect to traffic load.

7. Conclusions

Designing an efficient multicast routing protocol for Wireless Mesh Network is a challenging task due to its wireless characteristics and routing metric selection is one of the core issues that still being investigated. Traditional hop count method for selecting minimum best path is not always optimal. This paper proposed an integrated multiple metrics which could be use to improve the performance of MAODV Routing Protocol for Wireless Mesh Networks. Simulation results show that performance of MAODV-IM is better than MAODV in terms of Packet Delivery Ratio (PDR), Throughput and Average end-to-end delay.

ACKNOWLEDGEMENTS

The authors would like to thank their honorable parents. They also would like to express their gratitude to the Malaysian Institute of Microelectronic Systems (MIMOS) and Ministry of Higher Education (MOHE) Malaysia.

References

[1]  I. F. Akyildiz and X. Wang, Wireless Mesh Networks: Advanced Texts in Communications and Networking, John Wiley & Sons Ltd, First Edition, 2009.
[2]  Y. Zhang, J. Luo and H. Hu, Wireless Mesh Networking: Architectures, Protocols and Standards, Auerbach Publications, 2007.
[3]  E. M. Royer, C. E. Perkins, Multicast ad-hoc on-demand distance vector (MAODV) Routing, IETF Internet Draft, draft-ietf-manet-maodv-00.txt.
[4]  T. Pusateri, Distance Vector Multicast Routing Protocol, IETF Internet draft (draft- ietf-idmr-dvmrp-v3-10), 2000.
[5]  J. Moy, Multicast Routing Extensions for OSPF, Communications of the ACM, vol. 37, no. 8, 1994, pp. 61-66.
[6]  T. Ballardie, P. Francis, and J. Crowcroft, Core Based Trees (CBT) – An Architecture for Scalable Inter-Domain Multicast Routing, In Proceedings of ACM SIGCOMM'93, San Francisco, CA, 1993, pp. 85-95.
[7]  A. Adams, J. Nicholas, and W. Siadak, Protocol Independent Multicast - Dense Mode (PIM-DM): Protocol Specification (Revised), RFC 3973, NextHop Technologies, January, 2005.
[8]  D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, C. Liu, P. Sharma, and L. Wei, Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification, RFC 2362, June, 1998.
[9]  B. Fenner, M. Handley, H. Holbrook and I. Kouvelas, Protocol Independent Multicast—Sparse Mode (PIM-SM): Protocol Specification (revised), IETF Internet draft, daft-ietf-pim-sm-v2-new-05.txt, March, 2006.
[10]  J. Xie, R. R. Talpade, A. Mcauley, and M. Liu, AMRoute: Ad Hoc Multicast Routing Protocol, ACM/Kluwer Mobile Networks and Applications, ACM Press, vol. 1, no. 6, 2002, pp. 429-439.
[11]  S. J. Lee, C. Chiang and M. Gerla, On-Demand Multicast Routing Protocol, In Proceedings of IEEE WCNC‘99, New Orleans, LA, September, 1999, pp. 1298-1304.
[12]  L. A. Garcia and E. L. Madruga, The Core-Assisted Mesh Protocol, IEEE J. S. A. C., vol. 17, no. 8, 2001, pp.1380-1394.
[13]  E. M. Royer and C. E. Perkins, ”Multicast operation of the ad-hoc on-demand distance vector routing protocol”, In Proceedings of ACM/IEEE Intl. Conference on Mobile Computing and Networking (MOBICOM), August, 1999, pp.207-218.
[14]  P. Jacquet, P. Minet, L. Viennot, T. Clausen and C. Adjih, Multicast Optimized Link State Routing:draft-ietf-manet-olsr-molsr-01.txt, IETF MANET Working Group, INRIA Rocquencourt, France, 2001, November.
[15]  D. B. Johnson and D. A. Maltz, Dynamic Source Routing in Ad hoc Wireless Networks, Mobile Computing, Kluwer Academic Publishers, vol. 353, pp. 153-181, 1996.
[16]  S. J. Douglas, D. Couto, D. A. Yo, J. Bicket and R. Morris, A High-Throughput Path Metric for Multi-Hop Wireless Routing, Wireless Networks, vol. 11, pp. 419–434, 2005.
[17]  R. Draves, J. Padhye and B. Zill, Routing in Multi-Radio, Multi-Hop Wireless Networks,” In MobiCom’04, pp. 114–128, Philadekphia, USA, 2004, September.
[18]  A. Adya, P. Bahl, J. Padhye, A. Wolman and L. Zhou, A multi-radio unification protocol for IEEE 802.11 wireless networks, In BroadNets, 2004.
[19]  QualNet Network Simulator, Available:http://www.scalable-networks.com.
[20]  M. Akhtaruzzaman. Unicode Searching Algorithm Using Multilevel Binary Tree Applied on Bangla Unicode. T. Sobh (ed.), Innovations and Advanced Techniques in Computer and Information Sciences and Engineering, Springer Link 2007. pp. 321-326.