Subscribe Now Subscribe Today
Research Article
 

Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol



Naif A. Nasr Al-Sharabi, Li Ren Fa and Mohammad H. Algamali
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

This study is introducing the proactive prediction algorithm into a reactive ad hoc routing protocol, the concept of prediction algorithm using power measurement. Inserting signal power into packets and using it as a metric to determine and predict whether a route needs to be reconstructed is an original concept. The Prediction Algorithm together with Packets Received Time (PRT) method approach enhances the performance of the existing DSR protocol. The new approach is compared with original DSR in CBR and TCP traffics using various scenarios. The simulation results showed that our scheme is more efficient, reliable and improves throughput of the Ad-hoc network.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Naif A. Nasr Al-Sharabi, Li Ren Fa and Mohammad H. Algamali, 2008. Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol. Journal of Applied Sciences, 8: 1035-1041.

DOI: 10.3923/jas.2008.1035.1041

URL: https://scialert.net/abstract/?doi=jas.2008.1035.1041

INTRODUCTION

In most of the current ad-hoc routing protocols like (DSDV, DSR, TORA, DSR etc.) a node will keep using the route until the link is broken. It then has to discover a new route to the destination. During this discovery time the packets are lost and it will cause significant throughput degradation (Macker and Scott, 2000). When the network traffic requires real time delivery (such as voice, or video), dropping data packets at the intermediate nodes can be costly.

In this study, we propose an algorithm that utilizes PRT (Packet`s Received Time) to predict the signal power of the link state and find out if the route is going to be broken or not. Our scheme aims at modifying mobile ad-hoc network (MANET) reactive routing protocol (DSR), to give it a proactive behavior to improve its performance. Under our proposed scheme, route maintenance decisions are based on predicted values of link-breakage times (when the next-hop node will move out of transmission range). If a link is about to break, proactive discovery of new routes to all destinations using the next hop node depends on the history of traffic to that destination.

Several studies have proposed the Probability model for the link availability. GPS and signal strength methods presented in Goff and Abu-Ghazaleh (2001), McDonald and Znati (1999), Jiang et al. (2001) and Perkins (2000) are used physically measured parameters to predict the link status. The node with GPS can know its position directly, but the GPS system currently is not a standard component of mobile devices and the signal is too weak to be received in the metropolitan area and indoors.

This study concentrates on the PRT prediction approach in ad hoc networks to reduce the data packets that would have been dropped because of link failures. As seen above, in most existing protocols, a mobile host will keep using the route until the link is broken. Our proposed scheme will use power measurement of received packets to predict the topological change in order to rebuild a route prior to the link breakage, thus avoiding the data packets being dropping. Generally, a link failure happens when two mobile nodes A and B move out of their radio transmission ranges. Node B monitors the packets coming from A, predicts the link breakage time of link {A→ B} and then sends a warning message to the source node of this active route. The source node can rebuild a new route before the link breaks. The simulation results show that our PRT algorithm can increases the packets delivery ratio and reduces the number of drop`s packets due to link failure.

Many research works have studied the problem of estimation the residual link lifetime. One of the earliest works is Associativity Based Routing (ABR) presented in Toh (1997). ABR measures the lifetime of a link using beacon messages, which are periodically broadcast. Signal Stability Adaptive Routing (SSA) (Dube et al., 1997) classifies its neighbors as strongly/weakly connected on the basis of the signal strength of beacons that are exchanged periodically. Also based on signal strength, Route lifetime Assessment Based Routing (RABR) (Singh et al., 2000) predicts the time when a link would fail by calculating the average change in received signal strength.

The recent related work presented the PRT over the reactive protocol is (Alsharabi et al., 2005) which is applied the predict algorithm on AODV routing protocol.

MATERIALS AND METHODS

Route discovery: The method in DSR by which a node S dynamically obtains a source route to node D that will be used by S to route packets through the network to D. Performing a route discovery involves sending one or more route request packets.

Route maintenance: The process in DSR of monitoring the status of a source route while in uses, so that any link-failures along the source route can be detected and the broken link removed from use. When route maintenance indicates a source route is broken, S can attempt to use some other route on its routing table, or can invoke route discovery again to find a new route. Route maintenance is the mechanism whereby S is able to detect, while using a source route to D, if the network topology has changed such that it can no longer use its route to D because a link along the route no longer works. When route maintenance indicates a source route is broken, S can attempt to use some other route it happens to know to D, or can invoke route discovery again to find a new route.

Route discovery: Route Discovery is the mechanism whereby node S wishing to send a packet to destination D obtains a source route to D. To perform route discovery, the source node S (link-layer) broadcasts a route request packet. Each node that hears the route request packet forwards a copy of the request, if appropriate, by adding its own address to a source route being recorded in the request packet and then re-broadcasting the route request. The forwarding of route requests is constructed so that copies of the request propagate hop-by-hop outward from the node initiating the route discovery, until either the target of the request is found or another node is found that can supply a route to the target.

The basic mechanism of forwarding route requests forwards the request if the node (1) is not the target of the request, (2) is not already listed in the recorded source route in this copy of the Request and (3) has not recently seen another route request packet belonging to this same route discovery. A node can determine if it has recently seen such a route request, since each route request packet contains a unique identifier for this route discovery, generated by the initiator of the discovery. Each node maintains a Least-Recently-Used (LRU) cache of the unique identifier from each recently received route request. By not propagating any copies of a request after the first, the overhead of forwarding additional copies that reach this node along different paths is avoided. In addition, the Time-to-Live field in the IP header of the packet carrying the route request may be used to limit the scope over which the request will propagate, using the normal behavior of Time-to-Live defined by IP showed in Su and Gerla (1999) and Johnson et al. (2001). Additional optimizations on the handling and forwarding of route requests are also used to further reduce the route discovery overhead.

Route request table: The route request table is a collection of records about route request packets that were recently originated or forwarded by this node. The table is indexed by the home address of the target of the route discovery. A record maintained on node S for node D contains the following:

The time that`s last originated a route discovery for D,
The remaining amount of time that S must wait before the next attempt at a rout discovery for D,
The time-to-live (TTL) field in the IP header of last route request originated by S for D,
FIFO cash of the last ID_FIFO_SIZE identification value from route request packets targeted at node D that were forwarded by this node.

PRT route construction: Our algorithm does not require any modification to the DSR`s RREQ (route request) propagation process. When a source needs to initiate a data session to a destination but does not have any route information, it searches a route by flooding a RREQ packet. Each RREQ packet has a unique identifier so that nodes can detect and drop duplicate packets.

An intermediate node upon receiving a non-duplicate RREQ records the previous hop and the source node information in its route table. It then broadcasts the packet or sends back a ROUTE REPLY (RREP) packet to the source if it has a route to the destination. The destination node sends a RREP via the selected route when it receives the first RREQ or subsequent RREQs that traversed a better route (in DSR for instance, fresher or shorter route) than the previously replied route, when the route established the source start send the packet`s to the destination through shorter route.

The PRT structure and L_Prediction are established during RECV (received packet`s procedure) and RREP_ACK phase.

Routing maintenance and L_prediction: Data packets are delivered through the primary route unless there is a route disconnection. When PRT detects a packet`s received time is bigger than the route life time and does not receive hello packets for a certain period of time the L_prediction send RERR to the source to initiate a route rediscovery. The reason for reconstructing a new route is to build a fresh and optimal route that reflects the current network situation and topology. The L_prediction also mark the disconnect route and delete it from the packet header. Data packets therefore can be delivered through fresh routes and are not dropped when route breaks occur. On this case the old route will be deleted from the route header and link layer protocol will refreshment according to the new changes, rather the future route establishing in behalf of RREQ.

Packets receiving and packet`s sequence numbers: The Destination Node (DN) continues receiving packet`s until the link is broken. The DN receives different packet`s type from the Source Node (SN) or upstream node. Each destination (node) maintains a monotonically increasing sequence number, which serves as a logical time at that node. Also every route entry includes a destination sequence number which indicates the time at the destination node when the route was created. The protocol uses sequence numbers to ensure that nodes only update routes with newer ones.

All RREQ messages include the originator`s sequence number and its (latest known) destination sequence number. Nodes receiving the RREQ add/update routes to the originator with the originator sequence number assuming this new number is greater than that of any existing entry. If the node receives an identical RREQ message via another path the originator sequence numbers would be the same, so in this case the node would pick the route with the smaller hop count. If a node receiving the RREQ message has a route to the desired destination then the sequence numbers used to determine whether this route is fresh enough to use as a reply to the route request. RREQ messages, RREP messages also include destination sequence numbers. This is so nodes along the route path can update their routing table entries with the latest destination sequence number.

PRT and prediction algorithm: Two Ray Ground reflection approximations are used as radio propagation model used in (Das et al., 2000). The Two Ray Ground model uses formula (1) to calculate signal strength at the receiver`s end.

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
(1)

where, Pr is the received signal power, Pt is the transmitted signal power, Gt is the transmitter antenna gain, Gr is the receiver antenna gain, ht is the transmitter antenna height, hr is the receiver antenna height, it is assumed that Pt is a constant. Assume that the ground is flat to remove dependence of h and d values on the geography of the simulation area. So equation above can be simplified under the conditions of ad hoc wireless network simulation to:

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
(2)

where, k is constant

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
(3)

This equation shows that the signal power at the receiver node has relation 1/d4 with the distance between the sender node and receiver node.

The magnitude of relative speed of two nodes, average over all neighborhood pairs and all time is:

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
(4)

Where:
RS = Relative speed
V = Velocity and R is radio range

The value of extent of similarity of the velocities of two nodes that are not too far apart, average over all neighborhood pairs and all time is:

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
(5)

As we mentioned earlier, GPS and signal strength methods use physically measured parameters to predict the link status. GPS currently is not a standard component of mobile devices and the signal can be too weak to be received. Supposing the route has already been established and the first packet delivered, our algorithm starts recording packet received times and based on this data, predicting link breakages using the following formula:

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
(6)

where, MSS is the Maximum segment size, b is the Number of packets acknowledged by a received ACK, T0 is the Time-out length, p is the Packet loss probability, h is the Hops number in the route and RTTpt is the Packet`s round trip time. We use tree packets (for minimum) to predict the link state on the future packet by sending the pk-ack-power to the sender and save it in the table to compare it with signal power for the next packet received to predict the link state. In this case we will increment the packet flag p_flg by one and save the packet receive time on the receive table as flowing:

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
(7)

The packet received time average over all neighborhoods and all time is calculated using the following formula:

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
(8)

where, Prt is packet received time average on destination node, Ct is the current time defined on DSR original protocol calculated during transmitting and receiving packets, Llt is link life time, T total time arrives at the destination and N Number of hop.

Substituting (8) into Eq. 2 the received signal power on the distinction node is calculated as follows:

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
(9)

We added PRT procedure to DSR protocol, in this procedure when the destination node received the first packet. PRT start save packet time on the received packet time table, increment the packet flag, calculate packet signal power and wait for the next packet from the upstream and repeat Eq. 7-9 to next packet and compare it with previous packet that is already on the table.

If the current packet`s signal power is greater than the pervious packet`s signal power, that means the nodes are moving closer to each other otherwise if the current packet signal power is equal to the pervious packet signal power that means the nodes are quiescence so the packet flag will be zero and do not need prediction algorithm.

On the other hand if current packet signal power is weaker than the previous packet signal power, prediction algorithm maintenance marks the current route as idle to delete it from the packet header when a new route is established and send RERR upstream to locally maintain the route, or to the source node to establish RREQ to find a fresh and optimal route to the destination that reflects the current network situation and topology.

In the implementation, each destination nodes will keep an array as showed in (7) of signal info objects. Each table holds three packets with information such as signal power strength and reception time for the same neighboring mobile nodes. When node B receives packets from node A, it updates its table array according to:

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
(10)

When two mobile nodes are moving closer, the latest signal power strength will be greater than the previous one. In this case, we set P1 to the latest signal power value and set P2 and P3 to zero, no prediction is necessary.

RESULTS AND DISCUSSION

All simulations were run using the NS-2 simulator (ns-2allonone, 2005) and numerous simulations were chosen to illustrate the performance advantage gained by using DSR_PRT over DSR. The simulation experiments can be classified broadly as CBR (UDP) based simulations and TCP based simulations. The routing protocols were tested using both CBR and TCP traffic to get a more complete picture of their performances. Both the CBR and TCP based simulations were run with two mobility models. The simulations using RW (random waypoint) model were run in a 1500 m by 300 m area with 20 nodes under varying conditions of mobility and load. The communication model consisted of 8 CBR connections, with a packet size of 512 bytes for each set of simulations. All statistics were based up on 10,000 data packets and the rate of sending is 0.25, 0.5, 0.75 and 1 sec. Our simulations were conducted by varying both maximum velocity and pause time.

Maximum velocity varied as 1, 4, 8, 12,16, 20 m sec-1
Pause time varied as 0, 50, 100, 150, 200 sec

Figure 1 show that the End-to-End delay for DSR_PRT has longer delays than DSR. The reason for this is that packets that are dropped by DSR may use alternative, slower routes in DSR_PRT, thus resulting in longer delays, but better packet delivery ratio.

Figure 2 shows that DSR_PRT delivers more packets and those packets that are delivered in DSR_PRT but not in DSR, take alternate and possibly longer routes as we explained before

Figure 3 shows that the DSR_PRT loses fewer packets than DSR, thus increases the packet delivery ratio.

Figure 4 shows that the DSR and DSR_PRT have delivered almost the same amount of packets in low mobility and when the nodes are moving fast DSR_PRT deliverers more packets. DSR_PRT has more amount of control over messages. The hop count obtained with CBR traffic is a true measure of the average hop count of all active routes in the simulation, as the traffic source is independent of the network condition, while the hop count obtained with TCP traffic is not. This is because, in the absence of congestion, the rate of TCP transmissions is very sensitive to the number of hops, because the rate depends on the mean round trip time (rtt) of each connection, which is largely dependant on the number of hops.


Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
Fig. 1: End-to-end delays vs. pause time

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
Fig. 2: Packet delivery ratios

Hence, at lower hop counts, TCP transmits at a very high rate, while the rate rapidly drops at higher hop counts. Thus, the average hop count in TCP tends to be similar for all simulations just as the average hop count across all CBR simulations are comparable. Since TCP operates as a feedback system, TCP has a lower average hop count than the average hop count with CBR traffic for the same mobility scenario (Das et al., 2000; Daehyoung and Rappaport, 2003; Dajing et al., 2000; David et al., 1999).

Figure 5 shows the total data drop ratio for CBR with different pause time and Fig. 6 shows End-to-End delays for DSR_PRT has longer delays than DSR, because the DSR_ PRT detects the link break and discovers a new route to continue sending packets dropped in DSR

Figure 7 shows that DSR_PRT has more control messages than DSR, because DSR_PRT sends more messages to detect link states and discover new routes in order to continue sending packets that would have been dropped in DSR.


Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
Fig. 3: CBR packets lost

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
Fig. 4: TCP packet delivery ratios

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
Fig. 5: Total data dropped with CBR

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
Fig. 6: TCP end-to-end delay

Image for - Applied Packet`s Received Time Prediction to Reactive Ad-hoc Routing Protocol
Fig. 7: Control message on TCP

CONCLUSIONS

Prediction algorithm is one of the best approaches to avoid link breakage; it has been widely used in schemes aimed at improving performance of ad-hoc networks. As reviewed in this study, most of this work depends on node density, radio transmission range and GPS and signal strength. But the GPS and signal strength methods both use physically measured parameters to predict the link status. The performance could be further improved using the received packet signal. This study has given new method to improve the performance of ad-hoc network as the following:

The CBR simulation shows that DSR_PRT delivers more packets and those packets that are delivered in DSR_PRT but not in DSR, take alternate and possibly longer delay more than DSR
The TCP simulation shows that DSR and DSR_PRT have delivered almost the same amount of packets in low mobility and DSR_PRT deliverers more packets than DSR in high mobility
DSR_PRT has more amounts of control messages. The hop count obtained with CBR traffic is a true measure of the average hop count of all active routes in the simulation, as the traffic source is independent of the network condition, while the hop count obtained with TCP traffic is not
Compared with original DSR, our simulation experiments show that our approach with CBR and TCP traffic is more beneficial, delivered more packets, lost and dropped fewer packets
Study in this paper the insertion of a proactive prediction algorithm into a reactive ad hoc routing protocol
The concept of prediction algorithm using power measurement. Inserting signal power into packets and using it as a metric to determine and predict whether a route needs to be reconstructed is an original concept

More remains to be done to improve the performance on ad-hoc network protocols. Reduce overhead, control messages and also implementing our scheme in the real world scenario.

REFERENCES
1:  Alsharabi, N.A., L.Y. Ping and W. Rajeh, 2005. Avoid link breakage in on-demand ad-hoc network using packet's received time prediction. Proceedings of the 19th European Conference on Modeling and Simulation Conference, October 24-26, 2005, Latvia, pp: 802-807.

2:  Hong, D. and S.S. Rappaport, 1986. Traffic model and performance analysis for cellular mobile radio telephone systems with prioritized and non-prioritized handoff procedures. IEEE Trans. Veh. Technol., 35: 77-92.
Direct Link  |  

3:  Dajing, H., J. Shengming and R. Jianqiang, 2000. A link availability prediction model for wireless ad hoc networks. Proceedings of the International Workshop on Wireless Networks and Mobile Computing, Taipei, Taiwan, D7-D11.

4:  Das, S.R., C.E. Perkins and E.M. Royer, 2000. Performance comparison of two on-demand routing protocols for ad hoc networks. Proceedings of the IEEE 19th Annual Joint Conference of the IEEE Computer and Communications Societies, Volume 1, March 26-30, 2000, Tel Aviv, Israel, pp: 3-12.

5:  David, A.M., J. Broch, J. Jetcheva and D.B. Johnson, 1999. The effects of on-demand behavior in routing protocols for multihop wireless ad hoc networks. IEEE. J. Selected Areas in Communications Special Issue on Mobile and Wireless Networks, pp: 1439-1453.

6:  Dube, R., C. Rais, K.Y. Wang and S.K. Tripathi, 1997. Signal stability based adaptive routing for ad hoc mobile networks. IEEE Personal Communications, pp: 36-45.

7:  Goff, T., N.B. Abu-Ghazaleh, D.S. Phatak and R. Kahvecioglu, 2001. Preemptive routing in ad hoc networks. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, July 16-21, 2001, Rome, Italy, pp: 43-52.

8:  Jiang, S.M., D.J. He and J.Q. Rao, 2001. A prediction-based link availability estimation for mobile ad-hoc networks. Proceedings of the 20th Joint Conference on the Computer and Communications SocietiesInfocom, Volume 3, April 22-26, 2001, Anchorage, AK., pp: 1745-1752.

9:  Johnson, D.B., D.A. Maltz and J. Broch, 2001. DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks. In: Ad Hoc Networking, Perkins, C.E. (Ed.). Addison-Wesley, USA., pp: 139-172.

10:  Macker, J. and M. Scott, 2000. Internet Engineering Task Force (IETF) Mobile Ad Hoc Networks (MANET) Working Group Charter, Chaired by Joseph Macker and M. Scott Corson.

11:  McDonald, A.B. and T. Znati, 1999. A path availability model for wireless ad-hoc networks. Proceedings of the Wireless Communications and Networking Conference, Volume 1, September 21-24, 1999, New Orleans, LA., pp: 35-40.

12:  Perkins, C.E., 2000. Ad Hoc Networks. 1st Edn., Addison-Wesley, USA.

13:  Singh, J.P., A. Ahuja and S. Agarwal, 2000. Link connectivity assessment based applications for mobile ad-hoc networks. 42nd Annual Technical Convention of The Institution of Electronics and Telecommunication Engineers. New Delhi, India. http://www.stanford.edu/~jatinder/academic/projects/previous/adhoc_routing/publications/IETE2000.pdf

14:  Su, W. and M. Gerla, 1999. IPV6 flow handoff in ad-hoc wireless networks using mobility prediction. Proceedings of the Global Communications Conference, Volume 1, December 5-9, 1999, Rio de Janeiro, Brazil, pp: 271-275.

15:  Toh, C.K., 1997. Associativity-based routing for ad hoc mobile networks. Wireless Personal Commun., 4: 103-139.
CrossRef  |  Direct Link  |  

©  2021 Science Alert. All Rights Reserved