APU - Mobility Prediction Scheme for Routing Protocols in MANET

Abstract

In Manet, each node periodically broadcast its location information to its neighbor nodes which is known as beacon packet. These updates are costly. APU Adaptive Position Update scheme tries to reduce update cost and increase the performances in term of routing decision. Based on two principles, 1) A node transmits its next beacon if it has a deviation in its predicted value more than the acceptable range. 2) When a node hear a data packet transmission it transmit beacon. Greedy Perimeter Stateless Routing (GRPS) Protocol with greedy techniques for geographic routing. When greedy fails in selecting the next node nearest to destination we use perimeter rule which search over the perimeter for the destination. In this paper we predict the mobility of node to estimate the link time between the nodes known as link expiration time, which is used for selecting next hop for forwarding. Also we analyses LOOP problem which is created by mobility of destination node.

Keywords

beacons, DMP, geographic routing, GPSR, link expiration, LOOP problem.

INTRODUCTION

In MANET there is no fixed communication infrastructure. Each node is free to move in an arbitrary manner. Hence it’s necessary for nodes to maintain updated position information with the immediate neighbor. Also there will be frequent changes in the topology of the mobile nodes. In geographic routing, the destination node and the node in the forwarding path can be mobile. In such case it is necessary to reduce the effects caused by the changing topology, which is a difficult task in geographic routing to reconstruct the network topology in presences of changing topology. Various routing schemes have been proposed which uses the location information such as LAR.

To obtain the location of node’s neighbor, each node exchanges its location information (Using GPS) with its neighbor by periodic broadcast of beacons. This periodic beaconing is not fair in terms of update cost and for the possible for collision. To overcome this drawback, in this paper we propose an efficient beacon scheme, which dynamically adjust the frequency for beacon update based on nodes mobility. Also we enhance the location information to estimate the expiration time of the link between two nodes.

II. LITERATURE SURVEY

Greedy Perimeter Stateless Routing (GPSR) [2] uses the neighbor list of node and destination location for forwarding decision. In Greedy forwarding strategy the next hop is selected based on the optimal path that is it always selects a node which is closest to the destination. Nodes broadcast beacon to immediate neighbors periodically for maintaining local topology.

In [4] showed that the inaccuracy of location information has a significant impact on the performance of geographic routing protocols. They applied a mobility prediction scheme as [3] to GPSR and studied its impact of on the performance. However, they only use the prediction scheme to compute current position of neighbors and still employed periodic beacon updates.

Heissenbuttel et al[5]. has shown that periodic beaconing can cause the inaccurate local topologies in highly mobile ad-hoc networks, which leads to performances degradation. They proposed several simple optimizations that adapt beacon interval to node mobility or traffic load, including distance-based beaconing (DB), speed-based beaconing.

In the distance-based beaconing, a node transmits a beacon when it has moved a given distance d. The node removes an outdated neighbor if the node does not hear any beacons from the neighbor after a maximum time out. However, this approach has two problems. First, a slow node may have many outdated neighbors in its neighbor list since the neighbor time-out interval at the slow node is longer. Second, when a fast moved node passes by a slow node, the fast node may not detect the slow node due the infrequent beaconing of the slow node, which reduces the perceived network connectivity.

In the speed-based beaconing, the beacon interval is dependent on the node speed. A node determines its beacon interval which is inversely proportional to its speed. Nodes piggyback their neighbor time-out interval in the beacons. A receiving node compares the piggybacked time-out interval with its own time-out interval, and selects the smaller one as the time-out interval for this neighbor. In this way, a slow node can have short time-out interval, which eliminate first problem. But it still suffer from the second problem i.e. a fast node may not detect the slow node existences.

GLS [6] is a new distributed location service which tracks mobile node locations. GLS combined with geographic forwarding allows the construction of ad hoc mobile networks that scale to a larger number of nodes than possible with previous work. GLS is decentralized and runs on the mobile nodes themselves, requiring no fixed infrastructure. Each mobile node periodically updates a small set of other nodes (its location servers) with its current location. A node sends its position updates to its location servers without knowing their actual identities, assisted by a predefined ordering of node identifiers and a predefined geographic hierarchy. Queries for a mobile node's location also use the predefined identifier ordering and spatial hierarchy to find a location server for that node. Experiments using the ns simulator for up to 600 mobile nodes show that the storage and bandwidth requirements of GLS grow slowly with the size of the network. Furthermore, GLS tolerates node failures well: each failure has only a limited effect and query performance degrades gracefully as nodes fail and restart. The query performance of GLS is also relatively insensitive to node speeds. Simple geographic forwarding combined with GLS compares favorably with Dynamic Source Routing (DSR): in larger networks (over 200 nodes) our approach delivers more packets, but consumes fewer network resources.

III. EXISTING METHODS AND DRAWBACKS

ADAPTIVE POSITION UPDATE (APU)

Each node broadcasts its location information and its velocity in beacon packets to the nodes in its communication range. Following this each node periodically broadcasts its current location information. Each node stores this location information of beacons to maintain its neighbor lists. This location update is taken place continuously in periodically. Based on this information the node is selected for data forwarding.

Nodes which are outside the nodes communication range are not considered for data forwarding. Hence beacon is very important in building the local topology.

MOBILITY PREDICTION (MP) RULE

Periodic beacon update scheme have many outdated entries in its neighbor list. Because nodes that are highly mobile need to frequently update their neighbors since their locations are changing dynamically. On the contrary, nodes which move slowly do not need to send frequent updates. Also a small update interval will be wasteful for slow nodes, whereas a larger update interval will lead to inaccurate position information for the highly mobile nodes.

In our scheme, upon receiving a beacon update from a node i, each of its neighbors, denoted by the set N(i), records its current position and velocity and continues to track node i’s location using a simple prediction scheme. Based on this position estimate the neighbors N(i), check whether node i is still within their transmission range and update their neighbor list accordingly. The goal of the MP rule is to send the next beacon update from i when the error between the predicted location in N(i) and i’s actual location is greater than an acceptable value. To achieve this, node i, must track its own predicted location in its neighbors, N(i). Let (xa, ya), denote the actual location of node i, obtained via GPS or other localization techniques. (xp, yp) denotes the predicated position of the node I at current time. Node i then computes the deviation Di devi as follows:

If the deviation (Obtained in Eqn(1)) is greater than a certain threshold, known as the Acceptable Error Range (AER), it acts as a trigger for node i to broadcast its current location and velocity as a new beacon. The AER threshold is an important parameter that can affect the performance of the APU scheme. A large value of AER will minimize the beacon updates but will result in a larger error in the estimated location of the node at its neighbors. On the contrary, a smaller value guarantees accuracy of location information amongst the neighbors but increases the beacon overheads.

ON-DEMAND LEARNING (ODL) RULE

The MP rule solely may not be sufficient for maintaining an accurate local topology. Consider when a fast moving node passes through the communication range of slow nodes. Also the fast moving node has send its beacons before its mobility and AER value is greater so that MP rule is never triggered. If these nodes were transmitting data packets, then their local topology will not be updated and they will exclude each other while selecting the next hop node

Hence, we need another mechanism to maintain a more accurate local topology in those regions of the network where significant data forwarding activities are on-going. This is precisely what the On-Demand Learning (ODL) rule aims to achieve. As the name suggests, a node broadcasts beacons on-demand, i.e. in response to data forwarding activities of that node. According to this rule, whenever a node overhears a data transmission from a new neighbor, it broadcasts a beacon as a response. The ODL rule allows active nodes that are involved in data forwarding to enrich their local topology beyond this basic set. Thus the rich list is maintained only at the active nodes and is built reactively in response to the network traffic. All inactive nodes simply maintain the basic neighbor list.

Fig. 1(a) illustrates the network topology before node S starts sending data to node D. The solid lines in the figure denote that both ends of the link are aware of each other. The initial possible routing path from S to D is S-2-D. Now, when source S send a data packet to node 2, both 1 and 3 receive the data packet from S. As S is a new neighbor of 1 and 3, according to the ODL rule, both 1 and 3 will send back beacons to S. As a result, the links S-1 and S-3 will be discovered. Further, based on the location of the destination and their current locations, 1 and 3 discover that the destination D is within their one-hop neighborhood. Similarly when 2 forward the data packet to D, the links 2-1 and 2-3 are discovered. Fig. 1(b) reflects the enriched topology along the routing path from S to D.

DRAWBACKS

The MP rule, tries to maximize the effective duration of each beacon, by broadcasting a beacon only when the position information in the previous beacon becomes inaccurate. This extends the effective duration of the beacon for nodes with low mobility, thus reducing the number of beacons. Further, highly mobile nodes can broadcast frequent beacons to ensure that their neighbors are aware of the rapidly changing topology.

Since the network is highly mobility there is frequent changes in the local topology. The selected node make also move from the communication range and the link between the nodes may get lost which result in packet loss. This reduces the performances of the network.

LOOP PROBLEM

With GPSR, a packet is forwarded towards the coordinate of the destination stored in the packet header, and identification of a node is meaningless until the packet reaches the destination node in greedy forwarding. Consider the case when a destination node moves away from its original location and another becomes a node located closest to the original coordinate of the destination. This situation is misunderstood as a local maximum by GPSR protocol, and the perimeter mode forwarding is used to resolve this problem.

However, in this situation, packets normally get dropped unless the destination node comes back to near the original location and becomes the closest node to the destination location of the packet again. Perimeter forwarding generates wasteful loops in this situation, and we label these situations as LOOP problems.

IV. PROPOSED METHOD

In [1], they used the Adaptive Position Update Scheme for dynamically adjust the frequency for beacon update by using GPSR protocol for geographic routing. However in GPSR, the selected next node for forwarding the packet may get lost in the forwarding path due to the mobility of node out of the range, which decreases the performances of routing protocols. In this paper we propose our work by using the dynamic adjustment of the frequency for beacon update interval and estimation of the expiration time of the link between the mobile nodes. Based on the link expiration time the next hop is selected for forwarding the packets.

ESTIMATION OF LINK EXPIRATION TIME

We assume a free space propagation model, where the received signal strength solely depends on its distance to the transmitter. We also assume that all nodes in the network have their clock synchronized. Therefore, if the motion parameters of two neighbors (e.g., speed, direction, radio propagation range, etc.) are known, we can determine the duration of time these two nodes will remain connected. Assume two nodes i and j are within the transmission range r of each other. The predicted time is the link expiration time (LET) between the two nodes. Let (Xi,Yi)be the coordinate of mobile host i and (Xj,Yj) be that of mobile host j. Also Let Vi and Vj be the speeds, and θi and θj be the moving directions of nodes i and j respectively. Then, the amount of time two mobile hosts will stay connected, Dt is predicted by:

Using Eqn(2), the routing protocol always selects routes with the largest LET for data forwarding.

DESTINATION MOBILITY PREDICTION (DMP)

The second part of our mobility prediction scheme is a solution to the LOOP problem, which turns out to be the most serious problem for greedy forwarding. A great number of packets get dropped even when those are delivered to a neighbor node of the destination node. Packet drop after forwarding it to a neighbor of a destination node is the most undesirable thing to do with packet routing because it means more wastage of energy and bandwidth in the network.

To avoid this kind of problem and to increase the chance of packet delivery for the case when the destination node is moved out of its original location, a destination location prediction (DMP) scheme is proposed as a second part of MP. With DMP, each node searches its neighbor list for the destination node before it makes a packet forwarding decision based on the location information of the destination.

If the destination node exists in the neighbor list and located within the transmission range of the packet holder, the packet is forwarded directly to the destination node without further calculation for finding a closest neighbor to the destination. LOOP problems can be overcome by utilizing the identification information of nodes as well as location information. Significant amount of lost packets and wasted network resources can be saved by avoiding misjudgment on the local maximum situation. With DMP, the destination node movement towards the nodes in the delivery path and within the transmission ranges of that packet forwarder does not cause negative effects on geographic routing or even can be utilized in a positive way.

ADVANTAGE

Using this mobility prediction scheme we can dynamically update the frequency of beacon update and by using the LET value a node can select its next hop for transmission with largest value to reduce the packet loss and improve the performance in terms of packet delivery ratio. And also reduced the LOOP problems and packets drop.

V. RESULTS AND DISCUSSION

The Simulation based on the evaluation of APU Scheme was developed using Java SWANS simulator. The performances of the APU Scheme were compared with the Periodic beaconing Scheme. The figure shows the results of the Network with APU Scheme implementation. The Packet routing information and beacon broadcast information along with the acceptable error range of the nodes are shown in the information panel.

Figure: 3 show that the beacon overhead of APU increases linearly as a function of the average speed. The beacon overhead tends to saturate as the average speed increases. This is because of the polynomial relationship that exists between the beacon update period and the node speed. In contrast, observe that periodic beaconing results in very high beacon overhead, which does not vary significantly with the node speed. This is because in periodic beaconing, the beacon broadcasts are independent of the node mobility.

VI. CONCLUSIONS

In this paper, we proposed the Adaptive beaconing scheme and the mobility prediction rule to estimate the link expiration time of the nodes to increase the performances of geographic routing protocol. With DMP, unnecessary packet drops near the destination can be avoided, and the positive side of node mobility is exploited while the negative effect is mitigated. Future work includes the analysis of various geographic routing protocols using the above prediction scheme for beaconing and routing in Mobile Ad hoc Networks.

References

1. Q. Chen, S.S. Kanhere, and M. Hassan, “Adaptive Position Update for Geographic Routing in Mobile Ad Hoc Networks,” IEEE Transactions on Mobile Computing, vol. 12, no. 3, pp- 489-501, March 2013.
2. B. Karp and H. T. Kung,”GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” in Proceedings of MOBICOM 2000, Boston, MA, USA, 2000, pp. 243-254.
3. W.Su, S.J. Lee, and M. Gerla, ”Mobility prediction and routing in ad hoc wireless networks”, International Journal of Network Management, 2001.
4. D.Son, A.Helmy, B.Krishnamachari. ”The Effect of Mobility-Induced Location Errors on Geographic Routing in Mobile Ad Hoc and Sensor Networks: Analysis and Improvement Using Mobility Prediction”, in IEEE Transactions on Mobile Computing, vol. 3, pp. 233-245, July 2004.
5. M. Heissenbuttel, T. Braun, M. Walchli, and T. Bernoulli, “Evaluating of the Limitations and Alternatives in Beaconing,” Ad Hoc Networks, vol. 5, no. 5, pp. 558-578, 2007.
6. J.Li, J.Jannotti, D.S.J.D.Couto, D.R.Karger and R.Morris, “A Scalable Location Service for Geographic Ad Hoc Routing”, Proc. ACM MobiCom, pp. 120-130, Aug.2000.