Abstract

Communication over wireless links identifies significant challenges for routing protocols operating. This paper proposes a Cross-layer design based Multipath Routing Protocol (CMRP) for mobile ad hoc networks, by means of the node energy signal from the physical layer. The purpose is to optimize routing decision and path quality. The nodes’ mobility behavior is predicted using a notion of “Signal Fading Degree, SFD”. Especially, in combination of the IEEE 802.11e standard at the MAC layer, we determine that the IEEE 802.11e makes a significant contribution to performance improvement of CMRP. Performance evaluation of AODV in legacy 802.11 and CMRP in IEEE 802.11e shows that, as a function of speed of node mobility, a tremendous reduction achieved, in metrics such as the average end-to-end delay, route overhead, route discovery frequency, normalized routing load – almost more than 80%, 40%, 40%, and 40%. In the case of varying number of sessions, the reduction for route discovery frequency and normalized routing load are up to 70% and 80%.

1. Introduction

Technologies such as IEEE 802.11 wireless LANs (WLANs) have revolutionalized the way people think about networks, by offering users freedom from the constraints of physical wires. Mobile users are interested in exploiting the full functionality of the technology at their fingertips, as wireless networks bring closer the “anything, anytime, anywhere” promise of mobile networking [1,2].

Routing in wireless mobile ad hoc networks (MANETs) has been an active area of research for many years [3, 4]. A MANET is an autonomous network that can be formed without (necessarily) using a pre-existing infrastructure. The characteristics such as self-organizing make MANETs be prevalent today and be continued growth in popularity. Without centralized administration, individual nodes in MANETs are responsible for dynamically discovering which other nodes they can directly communicate with. A key assumption is that not all nodes can directly communicate with each other, so mobile nodes forward packets for each other, that is, multi-hop, allowing communication among nodes outside wireless transmission range. The node mobility, dynamic topology and the fundamentally limited capacity of the wireless medium, together with wireless transmission effects such as attenuation, multipath propagation and interference, combine to create significant challenges for routing protocols operating.

Firstly, recent research shows, that the single routing protocol reflects some limitations in case of highly dynamic network topology and strictly limited resources. One observation of single routing AODV [5] is that, though the source actually discovers multiple paths during the route discovery process, it chooses only the shortest delay route and discards the rest. Also, frequent route breaks cause the intermediate nodes to drop packets because no alternate path to the destination is available. Therefore, multipath routing algorithms have drawn researchers’ attention. The multipath routing allows building multiple paths between a source-destination pair. It can provide benefits such as fault tolerance, load balancing, bandwidth aggregation, and improvement in QoS metrics such as delay [7–25].

Another key issue is cross-layer optimization. For MANETs protocol design, the physical layer must adapt to rapid changes in link characteristics, the MAC layer needs to minimize collisions and allow fair access, the network layer needs to make a routing decision for effective data delivery to the destination, and so on.  The cross-layer design is desirable for improving performance in MANETs, since the methodology of layered protocol design does not necessarily lead to an optimum solution for dynamic environment. Under the layered protocol design, MANET routing protocols are unable to retrieve energy and location information from the underlying data link layer and physical layer and, thus, unable to calculate routes based on such information. In this work, we use cross-layer design to refer to protocol design and optimization, that is, make use of the node energy signal from the physical layer to optimize routing decision.

Finally, the IEEE 802.11e standard was developed to offer QoS capabilities to WLANs (e.g. MANETs), offering significant improvements to multimedia traffic [26]. MANETs will also benefit from this new technology since the most widely deployed and used wireless interfaces are IEEE 802.11 based. Currently, relatively little research work has focused on interaction between IEEE 802.11e and multipath routing protocols. In this work, the performance of CMRP gain obtained from IEEE 802.11e is demonstrated, by means of a series of simulation experiments.

Based on cross-layer design, we propose a multipath routing protocol (CMRP), in consideration of IEEE 802.11e technology, to improve dynamic multi-hop routing performance for MANETs. CMRP uses signal strength information to optimize routing decision and path quality. The purpose of this work is to ensure wireless multi-hop network performance improvement. Our simulation results demonstrate that, in combination of the IEEE 802.11e standard at the MAC layer, CMRP provides significant performance improvement in terms of average end-to-end delay, route overhead, route discovery frequency and packet loss as well.

The remainder of this paper is organized as follows. Section 2 discusses related work on current MANETs routing protocols. Section 3 proposes the cross-layer optimized multipath routing protocol and presents the details of its implementation. Section 4 discusses that the performance improvement of CMRP using IEEE 802.11e standard. Section 5 involves thorough analyses and evaluation of the CMRP performance in simulation methodology. Finally, Section 6 concludes the paper.

2.  Related Work

Most proposed wireless mobile ad hoc routing protocols are unipath protocols, which only use a single path to send packets to the destination. The main idea with multipath routing, which has been originally studied in wired networks, has existed for some time. Recently, many different multipath routing protocols based on AODV or DSR [6] for wireless multi-hop network have been proposed in literature.

As an extension to AODV, M. K. Marina et al. proposed a multipath routing algorithm, i.e. AOMDV [7]. The protocol computes multiple loop-free and link-disjoint paths. Loop freedom is guaranteed by using a notion of “advertised hopcount”. Link-disjointness of multiple paths is achieved by using a particular property of flooding. In details of CMRP, we modify both routing selection and routing maintenance based on AODV, in a manner similar to AOMDV. Z. Ye et al. proposed AODVM [8], which achieves a framework for reliably routing information. Duplicate RREQ messages are not discarded by intermediate nodes. Instead, all received RREQ packets are recorded in an RREQ table at the intermediate nodes. Caching and Multipath (CHAMP) Routing Protocol reported in [9] uses cooperative packet caching and shortest multipath routing to reduce packet loss due to frequent route breakdowns. X. Li et al. propose NDMR [10], which modify and extend AODV to include the path accumulation feature of DSR in route control packets, so that much lower overhead is employed to discover multiple node-disjoint paths.

Derived from DSR, SMR [11] focuses on building and maintaining maximally disjoint paths in order to prevent certain links from becoming congested and to efficiently utilize the available network resources. W. Wei et al. propose RMPSR [12], which distributes video packets over two primary routes of two route sets, to support Multiple Description Coding (MDC) application over MANETs. A. Nasipuri et al. developed a multipath protocol [13], in consideration of the situation where the destination replies to a selected set of RREQs. Recently there has been increased interest in protocols for wireless networks that rely on cross-layer [14–16]. M. Li et al. present a cross-layer multipath routing protocol (EMRP) [17]. By sharing the information among the physical layer, the MAC sublayer and the network layer, EMRP is able to utilize the network resources efficiently. H. Sun et al. propose an adaptive QoS routing scheme supported by cross-layer cooperation [18], considering the impacts of node mobility and lower-layer link performance. The multiple QoS requirements are satisfied by adaptively using forward error correction and multipath routing mechanisms, based on the current network status.

Routing protocols for NANETs have traditionally focused on finding paths with minimum hopcount in the last few years. In [3], R. Draves et al. find that minimal hopcount paths may provide poor performance because they tend to include wireless links between distant nodes and these long wireless links can be slow or loss, leading to poor throughput. Therefore, the routing algorithm can select better paths by explicitly taking into account the quality of wireless links. We design the schemes for path storage and selection in consideration of  this idea.

For interaction between IEEE 802.11e and routing protocols, in [26] Carlos T. Calafate et al. exposed results related to the interaction of AODV/DSR and the IEEE 802.11e technology in terms of throughput and normalized routing load in order to assess the improvements resulting from the IEEE 802.11e. In this work, we use IEEE 802.11e as the protocol of MAC sublayer to improve the performance of CMRP.

To the best of our knowledge, currently, relatively little research work has focused on interaction between IEEE 802.11e and multipath routing protocols. This paper is, based on cross-layer design, aimed at a multipath routing protocol for IEEE 802.11e MANETs. We refer to our work as an enhanced version of AODV, focusing on the performance improvement of overall network.

3.  A Cross-Layer based Multipath Routing

The main idea in CMRP is to compute multiple poweraware paths during route discovery. It is designed primarily for highly dynamic ad hoc networks where link failures occur frequently. CMRP stores and selects the paths according to signal strength. That is, it stores multiple SDFs of path on receiving routing message from the same source node, and selects a path also with largest SDF when transmitting data (see Subsection 3.1 for details). As a result, data packets are able to travel along the stable path. Especially, we deduce that the path with the largest SDF is also an energy-efficient path, since it can reduce signal attenuation for packets sending.

We describe the CMRP from the following two aspects. At first, a policy to predict the node mobility behavior is suggested. Then, the process of CMRP routing establishment and maintenance are presented on the basis of mobility prediction. At the same time, we discuss the power-saving characteristic based on routing mechanism as mentioned above.

3.1.  Node Mobility Prediction

It is well known that the radio signal gets weaker as it propagates. In a simulation environment, the node energy signal strength is able to indicate the distance between the sending node and the receiving node, as well as the quality and stability of the link to certain extent. In a realistic environment, however, an estimation of distance using signal strength may introduce errors, but we still can deduce node mobility behavior and the relative distance between a node and its neighbor via measuring signal fading. For example, we can deduce if the moving nodes lead to the link interruption in a short time. The hopcount in traditional routing protocols does not reflect the nodes’ relative location exactly. In a link with weak signal strength, a few hopcounts may lead to numerous packets loss. Therefore, using multipath routing will be not worth the candle if the paths are not chosen appropriately. We store and choose the paths according to the signal strength from the physical layer.

The severe signal fading is one of the characteristics in wireless communication. We use “Signal Fading Degree, SFD” to predict the node mobility, i.e., the distance between the sending node and the receiving node. The smaller the SDF is (the weaker the signal is) and the further the distance is, and the higher the probability of link interruption is. Formula (1) defines SDF of the node, which is transmitted by routing message (see Section 3.2 for details). This Formula gives a measure of the relative stability between two serial nodes in the entire path.

(1)

where RP denotes the remaining node energy. TP represents a fixed energy consumption of every efficient data packet sending. The accumulation of each node SDF hop by hop is the SDF of the whole path. SDF is used for measuring path reliability, i.e. a larger SDF indicates a more reliable link, whereas, a smaller SDF indicates a less reliable link. There are two ways to represent the SDF of the whole path, i.e. This Formula gives a measure of the relative stability of the path.

(2)

(3)

Table 1 shows the structure of the route table entries for CMRP. We add the SDF in path list.

Formula (2, 3) gives a measure of the relative stability of the path. We indicate the node on the path, and Formula (3) is a measuring standard for the signal fading degree of the whole path. As shown in Figure 1, there are two paths from the source node S to the destination node D, with the value on the arrow denoting SDF. SDF results of the two paths (path_1 and path_2) calculated by Formula (2) are 0.6 and 0.65 respectively.  However, the distance between node B and node E is longer and the interruption probability of path_2 is higher than that of path_1, so the result calculated by Formula (2) is wrong. While the SDF result of the two paths calculated by Formula (3) are 0.008 and 0.004 respectively, which can reflect the actual condition more exactly. Therefore, Formula (3) is chosen to calculate.

3.2.  Routing Establishment and Maintenance

The multipath routing protocol seeks multiple disjoint

routes between source and destination nodes, which refer to node-disjoint or link-disjoint. We use link-disjoint in the design of CMRP since it can establish more paths than node disjoint, with higher stability. Figure 2, 3 and 4 describe the CMRP routing establishment and maintenance procedure.

As shown in Figure 2, nodes A, B and C receive RREQ from S, and then Node E receives RREQs from A and B, one after another. It forwards only the RREQ from B and discards the one from A. Since the SDF of path E-B-S is higher than SDF of path E-A-S, it is selected as the primary path. The other one becomes the alternate path. Destination D receives RREQs from nodes F, G and H. Note the route table of node E and node D.

The numbers in parenthesis indicates the SDF carried by the sending node, the numbers on the right indicates the SDF of the link. The updating process is described by formula (1, 2): for example, SDF of S-B is 0.3, which multiplied by SDF initial value 1 is 0.3. The result 0.3 is sent out as SDF of node B by RREQ. 0.3 multiplied by the SDF of path B-E is 0.09 as SDF of node E, which is sent out by RREQ. In a similar calculation way, the SDF of the entire path is calculated finally. The path with the largest SDF is the primary path.

Figure 3 shows the process of route reply and path store. Destination D replies to nodes F, G and H. Node E forwards the RREP from node F to node B and from node G to node B. Source S thus obtains three routes to D. S selects the path S-B-E-F-D as its primary route since it has higher SDF than the other paths (see route table).

Source node S receives several RREP one after the other (see Figure 4). According to the SDF in route table,

S selects the path_1 as the primary route for sending data packet. Path_2 and path_3 shown are used as alternative transmission paths.

We present the main process of routing computer as Formula (5)～Formula (9):

(4)

(5)

(6)

(7)

(8)

(9)

The main process of loop-freedom is illustrated by Formula (10)～Formula (15):

(10)

(11)

(12)

(13)

(14)

(15)

This is used whenever a node i receives a route message to a destination d from a neighbor j. rq, and rp stand for route requests and route replies. SDF and tpr respectively denote remaining node energy when packet is received and fixed transmission power for two-ray ground. The variables seq_num and ad_hopc represent the sequence number and advertised hopcount.

Thus, CMRP stores and selects the paths according to signal strength, stores multiple SDFs of path when receiving routing message from the same source node, and selects paths with strongest signal strength when transmitting data to enhance transmission reliability.

The transmission power is peculiar to wireless ad hoc networks, and is important because typically the nodes involved have a limited power supply, and radio communication consumes a large fraction of this supply [4]. Based on power-aware routing mechanism of CMRP, we deduce that the path with the largest SDF is not only a reliable path but also an energy-efficient path, since it can reduce signal attenuation for packets sending.

4.  IEEE 802.11e QoS Enhanced WLAN

In this section, we briefly explain the IEEE 802.11e Enhanced Distributed Channel Access (EDCA) since we focus on ad hoc mode, and then discuss the significant contribution of IEEE 802.11e provided for enhanced performance of CMRP in MANETs.

4.1.  Enhanced Distributed Channel Access

The most widely deployed and used wireless interfaces for IEEE 802.11e are IEEE 802.11 based. As a matter of fact, the IEEE 802.11e standard was developed to offer QoS capabilities to WLAN, offering significative improvements to multimedia traffic. In this work, we determine that the IEEE 802.11e makes a significant contribution to performance improvement of CMRP by means of a series of simulation experiments.

The IEEE 802.11e standard introduces the hybrid coordination function (HCF) which defines two new medium

access mechanisms to replace legacy PCF and DCF. These are the HCF controlled channel access (HCCA) and the enhanced distributed channel access (EDCA). The HCCA is used in both periods, while the EDCA is used only during the CP. This new characteristic of HCF obviates the need for a contention-free period (CFP) since it no longer depends on it to provide QoS guarantees. With IEEE 802.11e, the point coordinator is replaced by a hybrid coordinator (HC) which also resides in an AP. A Basic Service Set (BSS) including a HC is referred to as a QBSS. In this paper we focus on ad hoc networks and, therefore, we are only interested in 802.11e stations implementing EDCA.

EDCA is designed to provide prioritized QoS by enhancing the contention-based DCF. Before entering the MAC layer, each data packet received from the higher layer is assigned a specific user priority value. How to tag a priority value for each packet is an implementation issue. At the MAC layer, EDCA introduces four different first-in first-out (FIFO) queues, called access categories (ACs). Each data packet from the higher layer along with a specific user priority value should be mapped into a corresponding AC according to the Table 2. Different kinds of applications (e.g., background traffic, best effort traffic, video traffic, and voice traffic) can be directed into different ACs. In Table 3 we can see each AC behaves as a single DCF contending entity with its own contention parameters (CW_min, CW_max, AIFSN and TXOP_Limit), which are announced by the QAP periodically in beacon frames. Basically, the smaller the values of CW_min[AC], CW_max[AC], and AIFS[AC], the shorter the channel access delay for the corresponding AC and the higher the priority for access to the medium.

A new type of IFS is introduced In EDCA, the arbitrary IFS (AIFS), in place of DIFS in DCF. Each AIFS is an IFS interval with arbitrary length as follows:

AIFS [AC] = SIFS + AIFSN [AC] × slot time, where AIFSN [AC] is called the arbitration IFS number. After sensing the medium idle for a time interval of AIFS [AC], each AC calculates its own random backoff time (CW_min[AC] backoff time CW_max[AC]). The purpose of using different contention parameters for different queues is to give a low priority class a longer waiting time than a high-priority class, so the high-priority class is likely to access the medium earlier than the low-priority class. Note that the backoff times of different ACs in one QSTA are randomly generated and may reach zero simultaneously. This can cause an internal collision. In such a case, a virtual scheduler inside every QSTA allows only the highest-priority AC to transmit frames.

4.2.  Contribution of IEEE 802.11e

IEEE 802.11e has a great potential to improve CMRP performance in wireless networks. Firstly, IEEE 802.11e allows wireless nodes to occupy channel for a long period of time during Transmission Opportunity (TXOP). This characteristic is able to dramatically decrease channel overheads caused by interception, Inter-frame, backoff and competition; from our perspective, CMRP performance will benefit from the improved path quality together with the extended occupation period of the channel. Secondly, Block ACK mechanism, i.e. it only replies one ack_frame to multiple data packet to decrease the overheads; finally, CFB enables an EDCA to transmit multiple frames once the medium or TXOP is acquired, without contending for the medium for every frame.

We consider that these characteristic mentioned above of MANETs stations to IEEE 802.11e are very important not only for multimedia traffic support, but also to improve the efficiency of the routing mechanism. This deduction will be verified by means of a series simulation experiments later.

5.  Performance Evaluation

In this work, we use NS-2 [27] with TKN 802.11e module [28] to evaluate the performance of CMRP, comparing it with AODV in the same MAC sublayer protocol and conventional layered protocol stack, which use Legacy 802.11 in the MAC sublayer. Two simulation experiments are conducted, where the rate of the node motility and the number of sessions are varied in order to analyze and compare the performances of CMRP and AODV in Legacy 802.11 and IEEE 802.11e. The detailed simulation parameter setting is illustrated in Table 4.

The following key metrics are used in different scenarios to evaluate CMRP performance.

•  Average End-to-End Delay: It includes all delays caused by buffering during route discovery, queuing at the interface, retransmission at the MAC, propagation and transfer times.

•  Total Packets Loss: This includes all possible packets loss such as data packet loss and control packet loss.

•  Route Overhead: The total number of control packets transmitted by any node.

•  Normalized Routing Load: The total number of control packets divided by the total number of CBR packets received by destination node.

•  Route Discovery Frequency: The total number of route discoveries initiated per second.

•  Average Hopcounts: Average hopcounts of routes for data sending.

5.1.  Performance with Varying Mobility

Figure 5 shows the six performance metrics as a function of mobility in experiment I. The max speed of node mobility is varied from 5m/s to 40 m/s. The number of CBR sessions is 10.

Figure 5(a) shows comparison of average end-to-end delay between the two routing protocols. CMRP with IEEE 802.11e has the shortest delay. Next is AODV with IEEE 802.11e, followed by CMRP with Legacy 802.11 and AODV with Legacy 802.11 respectively. The simulation results demonstrate that a tremendous reduction is achieved, in the average end-to-end delay with both CMPR and AODV in IEEE 802.11e, but that of CMPR decreases much more pronounced, as shown: 80% decreases against AODV in Legacy 802.11, 60% against AODV in IEEE 802.11e. On the other hand, the delay variation of CMRP tends to be much smoother comparing to AODV. CMRP builds multiple link-disjoint routes in the route request process and triggers a new route request process when all the routes are broken. These steps help CMRP maintain multiple routes longer than that of AODV. In traditional multipath routing, the primary path selected may not be always optimal in some cases. Moreover, the reliability of alternative paths often become poor, even broken when needed. By improving primary and alternative path qualities, CMRP is able to suspend link failures. Another important aspect is that IEEE 802.11e provides significant contribution for CMRP performance

improvement. IEEE 802.11e allows wireless nodes to occupy channel for a long period of time during Transmission Opportunity (TXOP). It dramatically decrease channel overheads caused by interception, Inter-frame, backoff and competition. These approaches are important for enhanced performance of delay.

The number of packets loss is shown in Figure 5(b). Using CMRP, the simulation result shows that total packet loss decrease much more pronounced in comparison with AODV. CMRP with legacy 802.11 has the least amount of packet loss. Next is CMRP with IEEE 802.11e, followed by AODV with Legacy 802.11 and AODV with IEEE 802.11e respectively. It indicates that CMRP can not only extend path lifetime, but also improve path reliability. However, this performance tendency of two routing protocol is different from the tendency of average end-to-end delay; note that CMRP with legacy 802.11 has the least amount of packet loss.  The IEEE 802.11 standard defines two Medium Access Control (MAC) protocols, namely Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA), and Request-To-Send/Clear-To-Send (RTS/CTS). The RTS/CTS mechanism, which is included in the legacy 802.11 model, has never been used in the TKN802.11e model of our simulation experiments. Without the four ways handshake mechanism (RTS/CTS/DATA/ACK), the average end-to-end delay achieve improvement to some extent since the channel overhead of RTS/CTS will increases data packet delay. However, without RTS/CTS mechanism, the probability of packet loss has increased in IEEE 802.11e.

The battery power of nodes in MANETs limited, so the route overhead is an important metric for extending overall network lifetime. As shown in Figure 5(c), basically, the number of control packets increases with the node mobility level for both AODV and CMRP. CMRP with IEEE 802.11e has the least amount of route overhead. Next is AODV with IEEE 802.11e, followed by CMRP with Legacy 802.11 and AODV with Legacy 802.11 respectively. Two routing protocol produces a slight difference at a low speed. However, CMRP achieves a remarkable reduction in route overhead at medium and high speed. By constructing multiple paths in one route query round, CMRP increases the average time between RREQ processes, thus effectively reducing the amount of broadcasting messages. Using CMRP, the source node will receive multiple reply messages in one route query round. Although this is a disadvantage for CMRP, the route overhead still descends as a whole.

Figure 5(d) presents the performance of normalized routing load. This metric has a similar tendency with route overhead. CMRP in IEEE 802.11e improves this performance shown at around 50% comparing to AODV in Legacy 802.11. Using CMRP, the route overhead has achieved reduction as possible. This is important for improvement of normalized routing load. On the other hand, the availability of alternate routes reduces the data packets loss and retransmission. This contribution also enhances the performance of normalized routing load. As a whole, CMRP with IEEE 802.11e has the least normalized routing load. Next is AODV with IEEE 802.11e, followed by CMRP with Legacy 802.11 and AODV with Legacy 802.11 respectively.