A Novel Ad hoc Routing Protocol Based on Mobility Prediction

INTRODUCTION

Mobile Ad hoc Network (MANET) (Giordano and Lu, 2001; Scaglione et al., 2006; Kim and Toh, 2006) comes from the Defense Advanced Research Projects Agency (DARPA), which is a network that each node processes packet routing without infrastructure. The fast equipping and mobile self-organization characters push MANET the hot point in wireless communication, especially the route protocol, e.g., now Internet Engineering Task Force (IETF)’s MANET working Group is searching for the comments (Mnaouer et al., 2007; Perkins et al., 2003).

Today routing protocol is approximately divided into table-driven routing protocol and On-Demand routing protocol (Lee et al., 1999; Kim et al., 2006) according to its trigger mechanism. Table-driven routing protocol is based upon the established routing tables, thus owns small delay. Its virtue is to not wait for establishing route while information are transmitted and delay is small. Meanwhile, on-demand routing protocol looks for routing when demanded, where the node usually needn’t maintain routing technically. Hence it is suitable for MANET and is widely researched recently.

On-demand routing is usually made up of two processes named routing set up and routing maintain. When nodes need transmit information, they broadcast route set up packets and search the optimal path without storage of the routing information, resulting in effective bandwidth and memory save. But it is apparently at the cost of delay due to the set up procedure. Accordingly, this style represents in Ad hoc On-Demand Vector (AODV) (Perkins et al., 2003).

This study presents a novel AODV routing protocol based on mobility prediction (MAODV). It can control node route by keeping and switching route through estimating the neighbor node’s distance and predicting the neighbor node’s mobility to fit fast changed network topology. This mechanism reduces the end-to-end delay effectively and enhances the real-time character, which is very important to the voice communication and the video communication.

MOBILITY PREDICTION ALGORITHM

Figure 1 shows a sketch map on mobility prediction. Node D moves to node D’ in Velocity V. The radial distance varies from d to d’ relative to node S and the radial velocity act as V_r and V’_r. Thus the movement difference is the Δd = d–d’.

Fig. 1:	Sketch map on mobility prediction

After calculating the received power P_r, d is determined by formula 1:

(1)

Here, we suppose that all nodes have the same transmission power p_t. The neighbor node’s velocity is calculated by formula 2:

(2)

where, Δt is spacing time for twice measurement. By the positive or negative of value, we may determine movement direction parameter of neighbor nodes that are outward node S or inward node S for instance (3).

(3)

By estimating space distance d, neighbor’s movement velocity v and neighbor’s movement direction, we may predict effective communication area whether node leaves off one another. If node’s movement direction is outward and d is already close to effective communication radius and v is relatively large, we may in advance start up routing detection and establish a new route before current path breaks off. In the suitable time path switching will be finished. So we may decrease delivery delay duo to suddenly route breaking off by prediction technique effectively.

According to analysis above mentioned, we provide one formula 4 for estimating effective communication area that neighbor node will outward.

there d denotes neighbor node’s distance at some time, D_comm denotes effective communication distance, V_r is the radial velocity and T_min denotes a new routing detective time estimated. When neighbor node’s distance d satisfied with formula 5, a new routing detection is stated up. Before primary routing path breaks off, a new routing will set up.

MAODV PROTOCOL SIMULATIONS

This study uses Network Simulator 2 (NS2) (Cavin et al., 2002). In NS2, we choose propagation model based on 802.11 and apply lucent’s WaveLAN. Under these simulation conditions, the wireless node is configured as:

Fig. 2:	End-to-end packet delay vs node’s maximum velocity

In simulations, we use Constant Bit Rate (CBR) and choose effective communication area of 250 m. Moreover, the mobility scene adopts CMU’s generator. Then in the 1500x300 m scenes, 50 nodes and 20 CBR, of which the length of date packet chooses 64 and 1024, respectively. The node’s maximum mobility is 1, 5, 10, 15 and 20 m sec^-1.

From Fig. 2 , we may obtain end-to-end packet delay in the MAODV protocol superior to in the AODV protocol. The decrease of delay is mainly introduced by route updating predicted. Because route updating is predicted, the delay by route breaking off will Greatly reduce. So average delay character in the MAODV will be improvement.

Figure 3 shows the relationship of the packet delivery ratio vs node’s mobility velocity, where packet delivery ratio is the ratio of received packets vs transmitted packets. As the maximum mobility velocity increases, packet delivery ratio in AODV and MAODV all decrease. But decreased value is not dramatically. Simultaneously the MAODV follows on-demand routing character and its packet delivery ratio will slightly inferior to AODV. After setting up prediction path, the MAODV don’t process further for network topology. The prediction algorithm that is finds out is the temporal excellent path. By memory, the path may be do not the most stable path. Meanwhile the error between the prediction algorithm and the actual status will bring some packet loosen ratio.

Fig. 3:	Packet delivery ratio vs node’s maximum velocity

Fig. 4:	Control overhead vs node’s maximum velocity

Therefore under the complex network circumstances, the MAODV will decrease packet delivery ratio because the action of MAODV protocol reply network topology.

From Fig. 4, control overhead will increase with the increases of node’s mobile velocity. This is because route switching varies business with the increases of node’s mobile velocity. Thus the routing overhead rises and control overhead increase. The control overhead of the MAODV will slightly outgo to AODV, which is bring because of additional consume of the path prediction.

Form Fig. 5, routing average numbers of hops do not dramatically vary with the increases of node’s mobile velocity. Average numbers of hops of the MAODV routing are slightly outgo to AODV. This is because the MAODV adopts the predictive algorithm. The selected predict paths do not always the best path of the route switching. Nevertheless the AODV adopts the routing strategy that set up route searching process after routing is break off. So the AODV routing is not corresponding delay than the MAODV.

Fig. 5:	Average number of hops vs node’s maximum velocity

Sometimes the selected AODV path is more get well than the MAODV. This is because the average numbers of hops of the AODV is small than the MAODV. What is a cost that the MAODV can decrease end-to-end packet delay adopted predictive algorithm.