Mobile ad hoc network consists of wireless nodes, and is insfrastructureless network. Because of the limited radio transmission range, a packet from source to the destination may need multiple hops. Every node in the network can be a router. Because nodes are free to move randomly,  the link in the route may be broken. The existing routing protocols mostly continue use a route until a link breaks. Then the source will rebuild a new route. It causes some problems: first it will take time to determine the link is broken, second, when node builds a new route, the packet will be dropped.

When we started this thesis last year, there is basically no related work. Some papers proposed use the mobility information to reduce the bad links. For example, in FORP, every packet contains the link expiration time, so the destination can predict the topology change and decide if the route needs hand off. The ABR and SSA favor the longer-live routes to reduce route maintenance. One paper published this month in MobiCom 2001, uses reception signal power strength, and sends warning to the source if the route is likely to be broken. But this paper uses different metrics like preemptive zone and packet latency. Also, implemented this preemptive routing in DSR caused at least twice increased overhead.

Our solution is divided into two parts: first use the reception signal power strength which from neighboring node to predict the link breakage time, we call it prediction algorithm. Second, in the routing protocol, when one link is going to break based on the prediction, a message is sent to the source, source node can rebuild a new route before the route breaks, then the packet won’t be dropped. In prediction algorithm, a node only monitors unicast packets from neighboring nodes. Because nodes are not move totally randomly. In our simulation model, a node will move to a randomly selected destination at a constant speed which is also randomly picked. After arrive the destination, it will stop for a pause time, then move to another randomly selected destination. In the graph, node A and B are neighboring nodes in an active route. V is the relative speed. We can assume that node A is still relative to B,and node B move at speed of vector v.

According to the two-ray ground model, the signal power strength p at the receiver has the relation with the distance between the sender and receiver: d to the 4. P1 to p3 is the power strength that receiver received at different time. Ps is the signal  strength threshold at the receiver. So the t is the link breakage time for node A and B. From above equation, we can calculate the t. When node B is receiving unicast packets from A, it uses sliding window to calculate the link breakage time, and only calculate the decreased signal power strength. And during the time we make prediction and link breaks, we assume two nodes will maintain their speed and direction. So if one of them changes movement pattern, the prediction will not be accurate unless receiving another three packets.

All the simulation works are done in ns2: the network simulator. We chose ns2 because it is free and open source, we can download from internet and modify the source code. We can use the trace file to search every packet at every hop. Most important, the AODV and DSR routing protocol have been implemented. first is dropped packets, one is packets dropped because of no route, this is one we mostly focus on because it caused by link breakage. The other is total packet dropped, there is other reasons cause packet dropped, for example the interface queue is full. Second is the control message increase: for control message, each hop is counted as one. This is the overhead metric. Third is the hop count ratio: the ratio between actual total hop count with the total optimal hop count. 50 mobile nodes in a 1500x300 meters area, 4 packet per second, 900 second simulation time.

We implemented the prediction algorithm is ns2 to validate. We did not modify the routing protocol yet at this step. When the node calculated a link breakage time, it record in the trace file. Then we can compare it with the real packet dropped time which is always later than link breakage  time. If they match, we say the algorithm prediction is correct. The critical time is a parameter that the time needed for source node to receive the prediction Route Error message and build a new route. It is different for different network size and routes with different hops. Here we use a static value. We ran the simulation for different mobility scenarios. The result shows nodes with active link have above 90% prediction accuracy. The active link is the link that has unicast communication over it in one second. So the prediction algorithm may have enough packets to calculate. Also, if nodes change their movement patterns during this time, for example, they are moving closer, then it will cause false prediction. It only account for less than 5%.

We picked DSR as our implementation protocol. Because according to the comparison results of some ad hoc routing protocols, DSR has good performance in packet delivery ratio, less control message. Also it is still has space to improve. If a node S wants to send a packet to destination D, it will check its route cache see if there is a route to D. if not, it will initiate a Route Discovery, broadcast a Route Request message. If a node receives a Route Request, it will check if there is a route to D in its route cache, if there is one, it will append the route into source route and reply it to S, otherwise it will broadcast again. DSR use source route, every data packet contain the route information. For example, when E receive a packet from S, it check the source route in the packet and know next hop is F, so it will send packet to F. If E-F link is broken, E will try to find a alternative route to D in its route cache, for example, there is a route E-C-G-K-D, it will send the packet and also send a error message to S. This is called salvaging the packet. If it can not find one, this packet will be dropped.

When we implement pro-active route maintenance in DSR, every  node maintains a table containing its active source node, previous hop node and the packet reception time, so it will not repeat sending Route Error message. When a node receives a unicast packet from its neighbor, it will check if the prediction time is less than critical time. If it is, it will send a Route Error message and put the node address and reception time in the table. Because the salvage mechanism in DSR, a node is allowed to send 3 error messages for the same bad link (and the same source) so the source node can be informed. When the source receive the error message and can not find an alternative route in its route cache, it will initiate a Route Request. When the node receives a Route Request from a bad link, it just ignore it and does not reply. Otherwise the bad link may be on the new route route again. Finally, because the two nodes over the bad link may move closer some time later, a timout is used to remove the entry in the table. So they may become neighbor in a new route again.

The first number (20,30) is the data source number, the second is the pause time, and the third is maximum node move speed. So the 30-020 has the highest data sending rate and mobility.

The number shown here is based on the 95% confidence interval.