ABSTRACT

Mobile Ad-hoc network (MANET) is an infrastructure-less and dynamic network. Routing in such a network is a challenge due to the mobility of its nodes. Multipath routing protocols try to improve the performance by finding more than one path towards the destination which could be kept as alternatives should the main path breaks. Stability-based Partially Disjoint AOMDV (SPDA) protocol has been proposed to tackle problems resulted from the very dynamic topology of MANETs. SPDA finds partially disjoint paths that are more stable than the maximally disjoint ones in order to increase paths lifetime as well as the availability of such multipaths. When choosing partially disjoint paths, SPDA does not take into consideration the number of hops of each path. Moreover, SPDA transmits packets over the shortest path until it becomes invalid before it tries to utilize other alternative paths. In this paper we improve SPDA by adding the number of nodes each path passes through to the selection criteria. In the Improved SPDA (ISPDA), the available alternative paths have been utilized to transmit packets in parallel. We compare the SPDA and ISPDA regarding the throughput and delay. Results show the superiority of ISPDA over the original one.

1. Introduction

A Wireless network could operate using an ad hoc mode of operation called Mobile Ad hoc NET work (MANET) in which no infrastructure or fixed access points do exist. The mobility of the wireless nodes renders MANET topology to be very dynamic. This limits the performance of such a network regarding its bandwidth, security, availability, and reliability [1,2]. Due to its dynamic topology, MANET needs special routing protocols that deal with its distinguished characteristics [3]. Most of the routing protocols designed for MANET are reactive in the sense that they invoke the routing procedure on demand and just when that route is currently needed. Finding the required path on demand reduces routing updates overhead when compared with other proactive routing protocols [4].

Ad-hoc On-demand Distance Vector (AODV) is an example of an on-demand routing protocol designed to serve MANET. If no routing entry for the required destination does exist in the routing table, then a Route REQuest message (RREQ) is broadcasted. After receiving the RREQ packet a node saves a reverse path towards the sending node as the next hop on the way back to the source [5]. The neighboring node generates a Route REPly (RREP) when it finds a valid route to the destination; otherwise a new RREQ is flooded. After receiving a RREQ, the destination node generates a RREP which is routed back to the source through the reverse path. A Route ERRor message (RERR) is sent back to the source node by the upstream node that discovered a link breakage. An alternative valid route towards the destination is selected if it exists; otherwise the source could initiate a new route discovery process [5,6].

AODV discovers single route between source and destination which has the lowest number of hops. AODV keeps the alternative discovered routes in reserve to recover the transmission process in case the primary route breaks. Other protocols try to better utilize the network resources by sending the data to be transmitted over the set of discovered routes in parallel [7]. Multipath routing protocol could be based on maximally disjoint paths in which a route does not have shared links or nodes with other routes. Alternatively, multipath could be based on partially disjoint paths that have shared links or nodes.

Maximally disjoint paths are desirable since a link breakage in one of them results in discarding only the broken path [7-9].

One of the maximally disjoint routing protocols is Ad Hoc on demand Multipath distance vector routing protocol (AOMDV). The destination in AOMDV selects many routes that do not have any shared links or nodes. The first RReq received by the destination is considered as a primary route through which the RRep is sent to the source. Other selected routes are kept as secondary paths. If the primary route breaks, the source can use a seconddary route with no need to re-discover new routes to the destination [4,10].

Stability Based Partially Disjoint AOMDV (SPDA) is a protocol that sends data through paths that are partially disjoint. It selects paths that are more stable than others even if these paths are not maximally disjoint. The idea of SPDA is to rely on stable nodes to be shared in multiple paths in order to reduce the number of link breaks that affect the selected alternative paths. This, in turn, decreases the delay and increases the network overall throughput [11]. SPDA selects the required number of paths using very simple first come first selected criteria.

In this paper we present ISPDA protocol which is an improved version of SPDA. The improvement comes in two ways. Firstly, by adding the number of nodes; each path passes through, to the selection criteria so that the shortest paths are chosen. Secondly, in the Improved SPDA (ISPDA), the available alternative shortest paths are utilized to transmit packets in parallel. This is in contrast to SPDA way of utilizing the available multipaths in that it starts by sending packets through the primary path until it gets invalid before other paths are considered for packets transmission [11].

The rest of this paper is organized as follows. The related work is presented in Section 2. Section 3 explains the proposed idea in more details. In Section 4 we walk through the simulation environment. We compare the SPDA and ISPDA regarding the throughput and delay in Section 5. We conclude the paper with Section 6.

2. Other Related Works

Asis Nasipuri et al. in [12] have studied the efficiency of routing protocols designs in Ad Hoc networks, according. Since Multipath routing protocols select many paths in single route discovery process, there is no need to start a new route discovery process whenever any link breakage happened to the primary path. This reduces the discovery overhead and gives better results than single path in end to end delay and throughput specially when sending the data through several paths.

Path disjointness has been studied and evaluated in many papers such as [4,12,13]. M. Marina et al. [4] have classified the Path disjointness into node-disjoint and link-disjoin paths which ensure that any link breakage in any path could not affect on the other paths. Node-disjoint paths have no intermediate nodes in common between the multiple paths. That makes them efficient in dense networks with high nodes mobility. Link-disjoint paths do not share any links while they can have shared nodes. Link disjoint paths approach is preferable in sparse environments, since it allows for shared nodes. This reduces constrains over the selected paths and as a result increases the number of alternative paths [4].

Disjoint multipath routing protocols has been classified into maximally disjoint multipath and partially disjoint multipath protocols. S. Lee et al. in [7] have proposed a maximally disjoint multipath routing protocol called Split Multipath Routing (SMR) protocol. SMR is an on-demand multipath source routing protocol which selects maximally disjoint paths. The destination in SMR selects out the maximally disjoint routes and discards the other routes. After selecting the routes, source in SMR sends the data to the destination through all the selected routes by using a per-packet allocation scheme. This mechanism reduces the traffic in the networks by making load balancing in sending data.

Many papers have discussed the partially disjoint multipath routing protocols and showed that the shared nodes or links between the partially disjoint paths are selected based on stability. Stability of the routes in MANET can be measured based on node stability or link stability [14]. Ye and Hua in [15], have analyzed these protocols and compared between the link stability and node stability by considering the lifetime of the nodes or links.

In [16], a multipath routing scheme has been proposed in order to improve scalability and provides efficient multipath routing. The proposed protocol called Multipath On-demand Routing (MORT), and tries mainly to minimize the route break recovery overhead by providing multiple routes on the source node and intermediate nodes which exist along the primary path to destination. This avoids overhead of additional future route discovery attempts, and reduces the route error messages transmitted during the recovery of route breaks. The paper concludes that finding multiple paths in a single route discovery has the effect of reducing the routing overhead incurred in maintaining ongoing connections.

3. The Idea of ISPDA

In this paper we introduce an Improved SPDA (ISPDA) by which we propose some modifications over SPDA in order to improve its performance over MANET. Similar to SPDA, ISPDA is concerned with partially disjoint multipath with shared links or nodes. The destination selects partially disjoint routes based on nodes stability.

Using ISPDA, the destination receives the first flooded RReq via a route that will be considered as a primary route and through which a RRep is sent back to the source node. In contrast with SPDA, the receiver in ISPDA deals with the other received RReqs differently in that it will firstly check the number of hop counts the newly received RReqs has passed through. If this new path is shorter or equal to the primary route, then the destination reviews the stability of each node in this path as explained by the flow chart shown in Figure 1(a).

As a result, ISPDA tries to choose the shortest paths with more stable links in order to increase the availability of the selected paths by decreasing the probability of link breakages. The selected alternative paths will be used in parallel to transmit the data be the sender node in order to increase the utilization of available bandwidth. This is in contrast to SPDA protocol which does not take path hops count into consideration when accepting new alternative paths. SPDA also keeps available alternative paths in reserve so that they could be used in case of a primary link failure.

Stability of a node in ISPDA is estimated based on the number of RReqs that passed through the node contained in the list of nodes carried by received RReqs. Each destination has a history of the nodes traversed through different routes, how many times each node has been seen in different route lists, and the last time when that node has been seen in any path. If the destination received a route list that has a common link with other received route lists, nodes of these common links would have greater opportunity to be considered as stable nodes. Any intermediate node is considered stable based on two conditions as explained in Figure 1(b). Firstly, the number of times that node has been traversed in various paths is greater than specific threshold. Secondly, the time of the last occurrence, when that node has been encountered in a path, is less than specific period of time.

4. Simulation Environment

In order to study the performance of ISPDA and to compare it with that of SPDA routing protocol we have developed and implemented ISPDA model based on GloMoSim simulator [17]. We used the Distributed Coordination Function (DCF) of IEEE 802.11 for wireless LANs as the MAC layer protocol. We assumed that each node moves independently according to the random way point mobility model with specified average mobility speed and pause time. All nodes had the same transmission range of 250 meters. The simulated traffic is a Constant Bit Rate (CBR). In the last two experiments the number of node varies from 25, 50, 75, and up to 100 mobile nodes. In the other set of the conducted experiments, a fixed number of 100 mobile nodes have been assumed. Parameters that have been adopted in the simulated experiments are as shown in Table 1.

Each experiment has been repeated at least 20 times using different seeds, and an average value of these runs has been computed to represent the final resulted value of the measured performance metric. The average end-toend delay, the throughput, and the average number of selected routes are the considered performance metrics. The chosen performance parameters are the density of nodes, specified via changing the terrain size in square meters, the maximum number of partially selected multiple paths, and the total number of nodes.

5. Results and Analysis

In this section we present the results and their analyses of the proposed ISPDA regarding the considered performance metric while varying the selected performance parameters. A set of experiments that show the relative merit of the two compared protocols, i.e. ISPDA and SPDA, regarding the average end-to-end delay, throughput and the average discovery overhead have been conducted.

In all the conducted experiments we set the maximum number of routes that a node can maintain to a certain destination to ten. In the next set of experiments, we measure the adopted performance metrics while increasing number of Partially Disjoint Paths (PDP) versus the number of maximally disjoint ones. In the figures, the number of routes expressed on the X axis represents the number of partially disjoint paths out of the ten allowed paths. This means that the rest of the paths are maximally disjoint ones.

The result of the first experiment is shown in Figure 2. We compare the end-to-end delay of the SPDA and the ISPDA protocols, while changing the number of partially disjoint routes vs. number of maximally disjoint routes. The superiority of ISPDA over SPDA is clear almost regardless of the number of partially disjoint paths. This is because in contrast with SPDA, ISPDA chooses the most stable paths with the minimum number of hops in the path. This increases the lifetime of the selected paths and so reduces the opportunity of future path breaks, which in turn reduces packet transmission delay.

The second reason of the big difference between ISPDA and SPDA with regards to the end to end delay has to do with the way ISPDA transmits packets. ISPDA transmits packets in parallel over all the discovered paths. It starts the transmission with the first discovered path and then distributes the transmission of the packet in an even way over the other path as they get discovered via receiving route replies form the destination. This parallel transmission of packets over all the PDP available greatly reduce the time needed to send the packets intended to be

transmitted.

In Figure 3, we show the average of discovery overhead of ISPDA and SPDA protocols as we increasing number of partially disjoint paths. One can notice that for both protocols the discovery overhead drops down as the number of partially disjoint paths increases. This is true and especially for the ISPDA protocol which drops more clearly until it converges with SPDA protocol with nine PDP. Although the two protocols select PDP the discovery overhead of ISPDA is higher than that of SPDA. This because ISPDA uses PDPs which pass through routes that are shorter than the primary path.

To compare between the behavior of SPDA and ISPDA with different node speeds, we have conducted an experiment in which the throughput is evaluated as the number of PDP increases and the results are shown in Figures 4-6. We notice firstly, that in almost all results the throughput of both protocols increases as the number of partially disjoint paths increases. The reason behind this is the fact that as the number of more stable PDPs increases the life time of the selected routes increases which allows the senders to send more data.

When we compare ISPDA with SPDA in the three figures we can see that as the nodes speed increases the throughput of ISPDA increases and the difference in performance between the two protocols increases. To explain this behavior firstly we should note that generally, as the nodes speed increases the probability of link break gets higher and consequently the throughput would decrease. ISPDA overcomes this draw back since it chooses

shortest stable paths which have less opportunity to break compared with SPDA which selects longer paths. This will lessen the effect of higher speeds on the throughput as the number of links that could break will be less than the case when using SPDA. Furthermore ISPDA distribute the burden of packet transmission on parallel over all

the discovered paths and this in turn enhance the achieved throughput substantially, this is in contrast to SPDA which transmit packets over one path until it gets invalid before trying to use the next one.

In the next two experiments we have fixed the number of PDP to seven, the speed to 10 m/s, and varied the number of nodes from 25, 50, 75, up to 100. The objective of these experiments is to compare the behavior of the two protocols as the network density, expressed by the number of nodes in the limited terrain, changes.

Figure 7 shows the way SPDA and ISPDA behave regarding the end to end delay as the number of nodes varies. We can see that both protocols react the same way as the number of nodes increases as the end to end delay generally gets lower, and specially with what seems to be the best number of nodes, that is 50 nodes, regarding the specified terrain size. ISPDA seems to perform better that SPDA in all cases and especially with a very sparse network as the case when the number of nodes equals 25. This is because ISPDA finds the shortest most stable paths available even when the number of available paths is limited in the case of 25 nodes in a relatively large terrain size.

The last experiment shows the performance of ISPDA and SPDA regarding the average throughput while changing the number of nodes. Figure 8 illustrates that as the number of nodes increases the throughput achieved by both protocols increases since the number of stable paths available increases. The superiority of ISPDA over SPDA protocol can be easily noticed and become clearer as the number of nodes get higher. The reason behind that is the fact that as the number of nodes increases ISPDA becomes more capable of finding shorter stable paths compared with SPDA which is interested mainly in finding stable paths only.

6. Conclusions

This paper aims to improve the performance of SPDA protocol in MANets. ISPDA is proposed which, as SPDA, tries to select partially disjoint paths that prove to be stable in addition to being be shortest available paths. Se-

lected stable shortest routes that are partially disjoint improve the network performance especially when used in parallel to transmit packets belonging to the same session.

The throughput, average end to end delay, and discovery overhead performance metrics have been measured for ISPDA and SPDA. Results show that ISPDA out performs SPDA regarding the performance metrics while varying the density of the mobile nodes, represented by changing the number of nodes in the same terrain size, and varying the number of partially disjoint paths. As the density of the mobile nodes decreases the superiority of ISPDA becomes clearer. The speed of mobile nodes plays also a clear role in the superiority of ISPDA over SPDA especially as the speed increases.

REFERENCES