Abstract: Stable node-disjoint multipath route for quality communication is needed for the present state of mobile ad hoc networks. In on-demand routing protocol, data transmission was between source and destination through a single path. When node moves with high mobility and low signal strength, the single path broke and results in loss of data. To address the above problems, a Boundary level based Stable Node-disjoint Multipath QoS routing protocol (BLBMQR) is proposed for Mobile ad hoc networks. In this protocol the source node establishes multiple routes in a single route discovery process based on received signal strength. The proposed protocol considers only two node-disjoint routes. One was the active path (primary path) another one is the reserve active path (secondary path). These stability routes meet the QoS (Quality of Service) requirements such as packet delivery ratio, end-to-end delay and route life time. When the active path fails due to instability, a reserve active path will be utilized. A threshold limit for boundary level based on signal strength is fixed for stability purpose. When active path crosses the boundary level, the route automatically switch over to reserve active path. Simulation studies were carried out with different parameters such as node mobility speed and number of nodes and then compared with Ad hoc On-demand Multipath Distance Vector Routing (AOMDV) routing protocol in terms of packet delivery ratio, end-to-end delay and route life time. The simulation results have shown that performance of BLBMQR much better than that of AOMDV.
INTRODUCTION
A mobile ad hoc network is a group of mobile devices that can be dynamically connected by radio waves. The data transmissions between the nodes are without the need of central base stations. The source node can communicate directly with other nodes, if such a link exists within the radio transmission range. If the distance between source and destination pair is too long, then the data must be sent through the intermediate nodes (Murthy and Manoj, 2004). Recently, the wireless ad hoc networks have been found to be more supported to multimedia application, such as data, video and voice applications (Van der Schaar and Sai Shankar, 2005).
QoS provisioning is challenging task due to unexpected node mobility and less signal strength. The Mobile ad hoc networks offer guaranteed Quality of Service (QoS), such as end-to-end delay, packet delivery ratio and route life time (Chen and Heinzelman, 2007; Reddy et al., 2006). In on-demand routing algorithms such as AODV (Perkins and Royer, 1999) the source node that needs to discover a route to a particular destination node, broadcasts a route request control packet (RREQ) to its immediate neighbors. Each neighboring node blindly rebroadcasts the received RREQ packet until destination node is reached. When an active route breaks due to unexpected mobility and low signal strength, the broken route drops the packets because alternate route is not available. Ad hoc On-Demand Multipath Distance Vector (AOMDV) routing protocol is an extension of single path AODV routing protocol. This protocol computes multiple loop-free and link-disjoint paths during route discovery (Marina and Das, 2001). This protocol achieves faster and efficient recovery from route failures in highly dynamic ad hoc networks. Cross-layered multipath AODV (CM-AODV) (Park et al., 2008) which selects multiple routes on demand based on the signal-to-interference plus noise ratio (SINR) measured at the physical layer. CM-AODV assigns the construction of multiple paths to the destination node and results in improved performance of packet delivery ratio. AODV-BR (Lee and Gerla, 2000) provides multiple alternate routes and is constructed without yielding any extra overhead. Alternate routes are utilized only when data packets cannot be delivered through the primary route. But this scheme does not perform well under heavy traffic networks. Zhen et al. (2010) proposed a novel segment-based adaptive multi-path routing mechanism is proposed, in which the Adaptive multi-path can be established based on current network topology. Parallel forwarding mechanism based on the established multi-path is introduced. Duplicated packets are sent along the multi-path to enhance the reliability of the end-to-end path. Sarma and Nandi (2011) proposed SMQR to provide QoS assurance to applications in MANETs. The use of simple route stability model and route maintenance method in the proposed multipath routing significantly reduces the number of route recoveries required during QoS data transmission. The detection of potential route failures and switching to an available stable route before actual route will break analyzed. Neighbor supported reliable multipath multicast protocol is discussed by Biradar and Manvi (2012). This protocol proposed scheme for multipath multicast routing in MANETs that used reliable neighbor node selection mechanisms. Neighbor nodes are selected that satisfy certain threshold of reliability pair factor to find non-pruned neighbor. Dual paths node-disjoint routing for data salvation (DPNR) proposed a routing protocol that maintains the only two shortest backup paths in the source and destination node. The DPNR (Jiang et al., 2012) scheme can alleviate the redundancy-frames over-head during the process of data salvation by the neighboring intermediate nodes. Above referred works are proposed to improve the stability using link stability and path stability. But none of them addressed combination of stability and boundary level. The node dB level based stable QoS routing protocol (Gnanasekaran and Rangaswamy, 2012) alleviate route breaking by using boundary level with signal strength but this protocol does not consider the node-disjoint path.
In this study, a Boundary Level Based Stable Node-disjoint Multipath QoS Routing Protocol for Mobile ad hoc Networks (BLBMQR) is proposed, to find a stable node-disjoint multipath route between source and destination pairs. The proposed system is to interact with the cross layer. The proposed scheme signal strength measurement is obtained at the physical layer. Based on these signal strength measurements, measured value is passed to the MAC layer. This value is used by the Network Layer for searching the new multiple route. The proposed scheme selects a routing path based on the three main factors: (1) Signal strength estimation, (2) Computing the node-disjoint path and (3) Boundary level fixing.
BOUNDARY LEVEL BASED STABLE NODE-DISJOINT MULTIPATH QOS ROUTING PROTOCOL
The Boundary Level Based Stable Node-disjoint Multipath QoS Routing Protocol (BLBMQR) is to find a stable multiple node-disjoint routes (longer lived) between source and destination pairs. The BLBMQR computes the route stability based on signal strength and added few extra fields in route request and route reply of AODV protocol. BLBMQR finds a maximum of two node-disjoint QoS paths. After stable multiple node-disjoint routes were found from source to destination, then source node set maximum route stability as the active path otherwise reserve active path. The stable multiple node-disjoint routes meet the QoS parameters such as minimum end-to-end delay, maximum packet delivery ratio and maximum route life time. The following are the key components of the proposed Boundary Level Based Stable Node-disjoint Multipath QoS Routing Protocol (BLBMQR):
| • | Signal strength estimation |
| • | Computation of node-disjoint multipath |
| • | Boundary level fixing based on signal strength to avoid route breaking |
The proposed method uses one of the most popular routing protocol AODV characters in mobile ad hoc networks.
Signal strength estimation: It is difficult to predict the stability due to node mobility but it is possible to estimate the stability based on received signal strengths using two-ray ground reflection model. Each node keeps a record of the received signal strengths of neighboring nodes. When a node receives a packet from a neighbor, it measures the received signal strength Pr.
The implementation of the network simulator ns-2 (http:/www.isi.edu/nsnam/ns/) is used in the received signal strength Pr to compute the distance to the transmitter of the packet. ns-2 uses the two-ray ground reflection model described in (Fall and Varadhan, 2000). The distance d is computed by using the two-ray ground reflection model given in Eq. 1:
| (1) |
where, Pt is the transmitted signal power and Pr is the received signal power, Gt and Gr are the antenna gains of the transmitter and the receiver, respectively, ht and hr are the heights of the transmit and receive antennas, respectively.
Each node sends out hello packet to its neighbors at a constant time quantum. When a node receives the hello packet, the MAC protocol keeps a record of the distances to neighboring nodes and node related information in a Route Stability Stable (RST). The RST (Table 1) maintains the following parameters: distance di,j, Pt, Pr, Gt, Gr, ht and hr.
| Table 1: | Route stability table |
| Pt: Transmitted signal power, Pr: Received signal power, Gt: Antenna gains of the transmitter, Gr: Antenna gains of the receiver, ht: Heights of the transmitter, hr: Heights of the receiver | |
| Fig. 1: | An examples of node-disjoint multipath |
Computation of node-disjoint multipath: Multiple paths established in single route discovery are called multipath. The Node-disjoint multipath does not have any node in common, except the source and destination. The BLBMQR finds out the maximum of two node-disjoint stability routes. The maximum route stability is the active path and the other is a reserve active path. Figure 1 shows the node-disjoint path between source and destination. In BLBMQR, when the active path breaks due to low signal strength or node mobility, the source automatically switches over to reserve active path. The periodic maintenance is available for alternate path in BLBMQR.
For example, in Fig. 1, from source node S to node D there are four paths: (S, A, B, C, E, D), (S, F, G, H, D), (S, I, G, H, D), (S, J, K, L, M, D). However, not all the paths that arrive in destination are node-disjoint. In BLBMQR, the destination is responsible for selecting and recording multiple node-disjoint paths. The destination node searches only three node-disjoint paths are: (S, A, B, C, E, D), (S, J, K, L, M, D), (S, F, G, H, D) or (S, I, G, H, D). The following algorithms explain the node-disjoint multipath:
| Step 1: | Receiving an RREQ packet at node x |
| Step 2: | Initialize received RREQ packet count n = 1 in each node routing table |
| Step 3: | If the RREQ (nx) packet is received for the first time |
| Step 4: | If nx = n |
| Step 5: | Node x is rebroadcast the received RREQ packet |
| Step 6: | Else |
| Step 7: | Node x is drop the RREQ packet and discard it |
| Step 8: | End IF |
In Fig. 1, S starts the multipath discovery for D and the QoS-RREQ (QoS Route Request) packet from S the following the path (S, F, G) reaches node G before the QoS-RREQ packet which follows the path (S, I, G). Using this proposed algorithm, node G will drop the QoS-RREQ packet received from I.
Boundary level fixing based on signal strength: The route stability model computes the route stability based on received signal strengths. This protocol finds out two node-disjoint stability routes selected by destination node based on received signal strength. Here, the route with maximum stability is considered as active path, otherwise it is a reserve active path. It is assumed that each node has a transmission range up to 9.5081e- 11. In our protocol, fixing the threshold value (sthresh) is 1.7615e-10. All route request messages are received by the destination. After receiving the all RREQ message, the destination node will compute the stability and boundary level. The following steps are defined the boundary level.
| Fig. 2: | Boundary level fixing, Sthresh. Signal threshold |
| Fig. 3: | Route request format |
This algorithm periodically maintains and validates the active path and reserve active path. If the stability value of the reserve active path is higher than the active path, then it automatically switches over to reserve active path:
| Step 1: | If Pr = sthresh, then the active path is assumed to be stable |
| Step 2: | Set RS = 1 |
| Step 3: | If Pr>sthresh, then the active path is assumed to be unstable then source automatically selects reserve active path |
| Step 4: | Set RS = 0 |
In Fig. 2 the high stability of s-f-g-h-d is an active path. The next high stability of s-a-b-c-e-d is a reserve active path. If active path stability crosses the 1.7615e-10, then it automatically changes over to reserve active path.
Route discovery process: Whenever, a source node, S, wishes to communicate with a destination node D and there is no route to the destination, the source node S initiates a broadcast route discovery procedure by broadcasting a QoS Route Request (QoS-RREQ). The transmitted QoS-RREQ is heard by all neighbors who are in the transmission range of the source. The route discovery process is mainly used to find a stable node-disjoint multipath from source to destination. To compute a QoS node-disjoint multipath to a destination, source generates a QoS-RREQ packet with the information given Fig. 3.
An intermediate is neither the source nor the destination. An intermediate maintains a RREQ Cache stores information about the QoS-RREQ forwarded earlier. If two or more QoS-RREQ has the same Source Address, Destination Address, then it discards the QoS-RREQ. Otherwise, node appends to RREQ Cache.
Route selection process: When a QoS-RREQ reaches node D, it stores the QoS-RREQ in RREQ Cache. The destination D after receiving first copy of QoS-RREQ with sufficient signal strength and wait up to route expiry time for collecting all feasible path.
| Fig. 4: | Route reply format |
Node D collects all copies of QoS-RREQ and gets saved in RREQ Cache, before the expiry of a timeout. Upon expiry of the timeout, destination D reads all QoS-RREQ in its RREQ Cache and sorts the QoS-RREQ packet in ascending order of their stability values and selects a maximum of two node-disjoint paths from the sorted order. Node D then sends multiple route replies QoS-RREP to source. It also stores the QoS-RREP in its RREP Cache. The QoS-RREP consists of the format shown in Fig. 4.
Upon receiving QoS-RREP, an intermediate node updates its routing table and unicast the QoS-RREP to the source node along the node-disjoint path. When node S receives QoS-RREP, it stores the path to node D in its Route cache. The source selects the route with the highest stability values as the active path; otherwise as the reserve active path. After receiving the QoS-RREP from destination, then the source starts the data transmission to destination. The algorithm for the route selection process is as follows:
| Step 1: | If (address == RREQ packet.Source address and (RREQ packet.duplicate) then |
| Step 2: | Drop RREQ packet |
| Step 3: | Rebroadcast RREQ to neighbor |
| Step 4: | Else if (addresses == RREQ packet. Destination address) |
| Step 5: | Store RREQ information in RREQ cache |
| Step 6: | Compute node dis-joint path after timed out |
| Step 7: | Compute stability after timed out |
| Step 8: | Check boundary level after timed out |
| Step 9: | Send RREP with node dis-joint to source |
| Step 10: | If (active path) then |
| Step 11: | Forward data packet |
| Step 12: | If (signal strength cross the threshold) |
| Step 13: | Forward data packet through reserve active path |
| Step 14: | Endif |
| Step 15: | Endif |
| Step 16: | Endif |
SIMULATION RESULTS
The free space propagation model (Promwong et al., 2004) and the two-ray ground reflection model (Rappaport, 1995) are the best models for simulation. The free space propagation model assumes the ideal propagation condition that there is only one clear line-of-sight path between the transmitter and receiver. The free space model basically represents the communication range as a circle around the transmitter. If a receiver is within the circle, it receives all of the packets; if not, it loses all of the packets. The two-ray ground reflection model (Rappaport, 1995) which is the more widely accepted of the two propagation models, considers both the direct path and the ground reflection path.
| Fig. 5: | Packet delivery ratio under different mobility speeds |
It has been shown that this model gives more accurate predictions at a long distance than the free space model. The two-ray ground reflection model is used for simulation purpose.
The proposed simulations were conducted in the ns-2 simulator (Fall and Varadhan, 2000). Our simulation modeled a network terrain area is 1000x1000 m containing 100 mobile nodes. This network is a homogeneous network. A random waypoint model was used in the simulation. The radio transmission range per node is 350 m assumed and is same for all nodes in the network. The data transmission rate is 2 Mb sec-1, each run has been executed for 900 sec of simulation time. Traffic source is based on Constant Bit Rate (CBR). The packet sending rate is 4 data packet per second. The packet size is 512 bytes long. The pause time is zero seconds and the maximum speed of the mobile node is set to 10, 20, 30, 40, 50, 60, 70, 80, 90 and 100 m sec-1 for different simulation runs.
We used the following metrics to quantify the performance:
| • | Packet delivery ratio: The ratio between the number of packets originated by source and the number of packets received by the destination |
| • | End-to-end delay: The average time between sending the packets at the source and receiving the packet at destination |
| • | Route life time: It is the period of time taken during which the route remain connected |
Analysis of packet delivery ratio (PDR): Figure 5 illustrates the performance of the packet delivery ratio under various mobility speeds. The mobility speed varied from 10-100. It is observed that the BLBMQR improves the packet delivery ratio of BLBMQR by about 15% when compared to that of AOMDV. With the high mobility speed, there is a better chance that the related links will break. Our protocol had better packet delivery ratio at various mobility speeds. The response shows that the higher the mobility, the lower the packet delivery ratio.
Figure 6 shows the performance of packet delivery ratio against the number of nodes. In this experiment, the number of nodes varied from 10-100. It is observed that the BLBMQR improve the packet delivery ratio of BLBQR by about 10% when compared that of AOMDV. It could be seen that the change rate curve line increased faster than AOMDV.
Analysis of average end-to-end delay: Figure 7 shows the average end-to-end delay of data packets vs. mobility speed (m sec-1). If mobility of nodes increases, the end-to-end delay of data packets also increases.
| Fig. 6: | Number of nodes effect on packet delivery ratio |
| Fig. 7: | Effect of mobility speed on average end-to-end delay |
| Fig. 8: | Effect of number of nodes on average end-to-end delay |
This is because the paths frequently move between source and destination. Comparing the result shown in this Fig. 7, it can be seen that BLBMQR has shortest end-to-end delay than AOMDV. The BLBMQR is better than AOMDV for average end-to-end delay.
Figure 8 shows the average end-to-end delay of data packets vs. Number of Nodes. In this experiment, the number of nodes in network varies from 10-100. We observe that with the growing number of nodes, the performance of BLBMQR is better, because the feasible routes will increase number of nodes between source and destination pairs. By fixing boundary level and stable route selection, the BLBMQR achieves better performance.
Analysis of route life time: Figure 9 compares the route life time with BLBMQR and AOMDV. The percentage of BLBMQR route life time is higher than the AOMDV.
| Table 2: | Comparative analysis of BLBMQR with AOMDV |
| Fig. 9: | Relationship between route life time and mobility speed |
| Fig. 10: | Relationship between route life time and number of nodes |
Figure 10 shows the relationship between the number of nodes and route life time. The BLBMQR route life time is better than AOMDV. The BLBMQR always selects most stable path under the boundary level. When the active path breaks, then reserve active path will takeover. So packet life time is very rare in BLBMQR. The performance of the BLBMQR is compared with AOMDV and is presented in Table 2.
CONCLUSION
In this study, a Boundary Level Based Stable Multipath QoS Routing Protocol (BLBMQR) for MANETs is presented. Using this approach, high stability route is found from source node to a destination node. This routing protocol satisfies End-to-End delay, Packet Delivery Ratio and Route Life Time constraints based on signal stability. It is observed that the BLBMQR algorithm achieves high performance with high Packet delivery ratio, End-to-End delay and Route Life Time compared to the AOMDV. Percentage improvement in QoS parameters reveals the superiority of the present work.