|Related article at Pubmed, Scholar Google|
Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering
In MANET, the packet forwarding necessitates the location information of the neighbor nodes and the location update information is obtained by transmitting the beacon signals periodically. However in geographic routing, the periodic beacon scheme has two problems: (1) It reduces the packet delivery ratio if a node does not exhibit significant dynamism, (2) The mobility and resource constraints of mobile nodes may lead to network partitioning or performance degradation. We propose a replica allocation pattern over the beacon update to address these problems. The replica allocation deals with the frequent network partitioning based on the data that are replicated at nodes there by increasing the data accessibility. The former case is conquered by making the occurrence of beacon updates in accordance with the mobility of the nodes and the latter case is handled by the replica allocation technique.
|Mobile ad hoc networks, periodic beacons, replica allocation, network partitioning|
|In a mobile ad hoc network (MANETs), there is no fixed infrastructure such as base stations or mobile switching centers. Mobile nodes that are within each other’s radio range communicate directly via wireless links, while those that are far apart rely on other nodes to relay messages as routers. In MANET, nodes move freely and so the topology of the nodes is highly dynamic. For example in Fig.1, nodes A, B, C, D and E constitute an ad hoc network and the circle represents the radio range of node A. The network initially has the topology in Fig.1(a). When node C moves out of the radio range of node A, the network topology changes to the one in Fig.1(b).|
|Node mobility in an ad hoc network causes frequent changes of the network topology. Fig.1 shows such an example: initially, nodes A and C have a direct link between them. When node C moves out of node A’s radio range, the link is broken. However, the network is still connected, because node A can reach node C through node B. The process of routing the data packets to the destination is a challenging task. Due to the mobility of the nodes the topology of the network may change frequently and in unpredictable ways. In order to provide an efficient and reliable data delivery for these MANETs, each node exchanges its location information with its neighbor by periodic broadcast of beacons. This periodic beacon consumes more energy per transmission and reduces the packet delivery ratio. To overcome this drawback we propose a beaconing scheme based on the mobility of the nodes which adapts the occurrence of beacon updates in accordance with the mobility of the nodes.|
|1.1 Replica Allocation Technique|
|Network partitions can occur frequently, since nodes move freely in a MANET, causing some data to be often inaccessible to some of the nodes. Hence, data accessibility is often an important performance metric in a MANET . Data are usually replicated at nodes, other than the original owners, to increase data accessibility to cope with frequent network partitions. A considerable amount of research has recently been proposed for replica allocation in a MANET. In general, replication can simultaneously improve data accessibility and reduce query delay, i.e., query response time, if the mobile nodes in a MANET together have sufficient memory space to hold both all the replicas and the original data. For example, the response time of a query can be substantially reduced, if the query accesses a data item that has a locally stored replica. Thus the replica allocation technique is used to improve the data accessibility.|
|The remainder of the paper is organized as follows: In section II we introduce some related works, in section III we describe about the existing systems and in section IV we propose our replica allocation method along with the beacon update. Finally, in section V, we give the concluding remarks.|
II. LITERATURE SURVEY
|In MANETs, by utilizing wireless networks the mobile nodes can change their locations while retaining network connections. The position update of the nodes are obtained through the location update packets called beacons which consists of the parameters such as signal strength, power supply information, relative address, location, time stamp and available bandwidth resources. In geographic routing (such as GPSR)  – , the neighbor list of nodes and destination location is used for forwarding decision. In Greedy Perimeter Stateless Routing (GPSR) the local topology is maintained by periodically transmitting the beacons.|
|Heissenbuttel et al  have shown that periodic beaconing leads to performance degradation due to the inaccurate topologies in high mobility MANETs. They addressed several adaptive beaconing schemes based on the node mobility or traffic load. In the distance-based beaconing, a node transmits a beacon when it has moved a given distance d. A node is considered to be outdated if the node does not send any beacon to its neighbors even after the maximum time out. However this method can have many outdated neighbors in its neighbor list since the neighbor time-out interval at the slow node is longer. In addition a fast node may not able to detect the slow node due to the infrequent beaconing of the slow node when it passes a slow moved node which leads to the reduction in 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.|
III. EXISTING METHODS
|3.1. Adaptive Position Update (APU)|
|In MANET, at first each node broadcasts a beacon to its neighbors to inform its presences stating its current location and velocity. After initialization each node periodically broadcasts its current location information. Each node continuously updates its neighbor list based on its transmission range, current location and the position updates received from its neighbors and stores them at each node. APU adapts the beacon update intervals to the mobility of the nodes and the amount of data being forwarded in the neighborhood of the nodes. In APU the neighbors which are outside the nodes communication range are not considered for data forwarding and the local topology is maintained by using the beacons. APU uses two principles: (1) nodes that have frequent dynamism updates its position frequently, (2) nodes which are in and closer to forwarding path are updated.|
|3.1.1. Mobility Prediction (MP) Rule|
|This rule adapts the occurrence of beacon generation to the dynamics of mobility of nodes. High dynamic mobility nodes update their neighbors very frequently and vice versa. A periodic beacon update policy cannot satisfy both these requirements simultaneously, since 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 Ni, record its current position and velocity and continue to track node i’s location using a simple prediction scheme (discussed below). Based on this position estimate Ni, the neighbors 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 Ni 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 Ni. We use a simple location prediction scheme based on the physics of motion to track a nodes current location. Note that, in our discussion we assume that the nodes are located in a two-dimensional coordinate system with the location indicated by the x and y coordinates as shown in equation (1) and (2). However, this scheme can be easily extended to a three dimensional system.|
|If the deviation (Obtained in equation (3)) 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. 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.|
|3.1.2. On-Demand Learning (ODL) Rule|
|The MP rule solely may not be sufficient for maintaining an accurate local topology. Consider the example illustrated in Fig. 2, where node N1 moves from P1 to P2 at a constant velocity. Now, assume that node N1 has just sent a beacon while at P1. Since node N1 does not receive this packet, it is unaware of the existence of node N2. Further, assume that the AER is sufficiently large such that the MP rule is never triggered. However, as seen in Fig. 2 node N2 is within the communication range of node N1 for a significant portion of its motion. If either node N2 or node N1 was transmitting data packets, then their local topology will not be updated and they will exclude each other while selecting the next hop node.|
|Hence, it is necessary to devise a mechanism which will 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. By maintaining a rich neighbor list along the forwarding path, ODL ensures that in situations where the nodes involved in data forwarding are highly mobile, alternate routes can be easily established without incurring additional delays. Fig. 3(a) illustrates the network topology before node N1 starts sending data to node N7. The solid lines in the figure denote that both ends of the link are aware of each other.|
|The initial possible routing path from node N1 to node N7 is N1 - N2 - N7. Now, when source node N1 send a data packet to node N2, both nodes N3 and N4 receive the data packet from node N1. As node N1 is a new neighbor of nodes N3 and N4, according to the ODL rule, both nodes N3 and N4 will send back beacons to N1. As a result, the links 1 - 3 and 1 - 4 will be discovered. Further, based on the location of the destination and their current locations, nodes N3 and N4 discover that the destination N7 is within their one-hop neighborhood. Similarly when node N2 forward the data packet to node N7, the links 2 - 3 and 2 - 4 are discovered. Fig. 3(b) reflects the enriched topology along the routing path from node N1 to node N7.|
|In , Chen.Q et al used the Adaptive Position Update Scheme, to adjust the occurrence for beacon update by using GPSR protocol for geographic routing. The beacons are used to locate mobile node’s position and the beacon generation intervals are adapted based on the mobility of nodes as well as the nodes along in the forwarding path. However in geographic routing such as GPSR, a node cannot access the data items of another mobile node if it is migrated to the separate divided network. As a result inaccessibility between the divided networks is increased which leads to the poor routing performance. For example if the entire network in Fig.4(a) is divided into two networks as like in Fig. 4(b) i.e. radio link between two mobile nodes at the central part is disconnected then the mobile nodes in the right -hand side and those in the left-hand side cannot access data items D1 and D2, respectively.|
|In ad hoc networks, it is a very important issue to prevent deterioration of data accessibility at the point of network division. A possible solution is by replicating data items at mobile nodes which are not the owners of the original data as shown in Fig. 4(b). In Fig. 4(a), the replicas of data items D1 and D2 are allocated at one of the mobile nodes in the opposite networks as shown in Fig. 4(b). Hence every mobile node can access both data items after the network division while improving the data accessibility.|
|In this paper, we proposed the data replication technique over an efficient beaconing scheme to avoid the inaccessibility of mobile nodes. The mobility based beacons are proposed to control the frequency of the beacon generation rate where as the high mobility node causes frequent generation of beacons while comparing it to the low mobility nodes. The replica allocation pattern is introduced to increase the data availability and it can be used to reduce the query delay i.e. query response time. Generally it is impossible for mobile nodes to have replicas of all data items in the network. Since most nodes in a MANET have only limited memory space there is a trade-off between data accessibility and query delay. Due to this a node should not hold the same replica that is also held by many other nodes.|
|Future work includes the analysis of eliminating the same replica in many mobile nodes. Further we plan to identify the impact of different mobility patterns along with the replica allocation technique.|
|We are grateful to the management of SNS College of Technology, Coimbatore for providing the facilities in the Department of Electronics and Communication Engineering to carry out the research work. We acknowledge Dr. S Chendur Pandian, Principal, for his constant encouragement and guidance provided in all respects.|
| 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.
 Dr.YogeshChaba and Naresh Kumar Medishetti, “Routing protocols in Mobile Ad hoc Networks-A Simulation Study Final”, JCS Vol1, No.1, August 2005.
 S. Lee, B. Bhattacharjee, and S. Banerjee, “Efficient Geographic Routing in Multihop Wireless Networks,” Proc. ACM MobiHoc, pp. 230-241, May 2005.
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.
 L. Blazevic, S. Giordano, and J.-Y.LeBoudec, “A Location Based Routing Method for Mobile Ad Hoc Networks,” IEEE Trans. Mobile Computing, vol. 4, no. 2, pp. 97-110, Mar. 2005.
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. A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica, “Geographic Routing without Location Information,” Proc. ACMMobiCom, pp. 96- 108, Sept. 2003.
 Takahiro Hara, “Effective Replica Allocation in Ad Hoc Networks for Improving Data Accessibility,” Ad hoc networks, IEEE INFOCOM 2001
. R. Cheng, C. Huang, “Efficient Prediction-Based Location Updating and Destination Searching Mechanisms for Geographic Routing in Mobile Ad Hoc Networks”, Proc. Journal of information science and engineering 28, 115-129 (2012).
O.Wolfson and S. Jajodia, “Distributed algorithms for dynamic replication of data,” Proc. ACM PODS’92, pp.149-163, 1992.
M. Nishizawa, H. Hagino, T. Hara, M. Tsukamoto, and S. Nishio: “A routing method using uni-directional link in ad hoc networks,” Proc. Int’l Conference on Advanced Computing and Communications (ADCOM’99), pp.78-82, 1999.
 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.
 Q. Chen, S.S. Kanhere, and M. Hassan, “Mobility and Traffic Adaptive Position Update for Geographic Routing,” Technical Report UNSW-CSETR- 1002, School of Computer Science and Eng., Univ. of New South Wales, ftp://ftp.cse.unsw.edu.au/pub/ doc/papers/UNSW/1002.pdf, 2010.
 C.E. Perkins, “Ad hoc Networking”, Addison Wesley , 2001.
 C. K. Toh, “Ad hoc Mobile wireless networks: Protocols and Systems”, Prentice Hall, New Jersy, 2002.
 L. Yin and G. Cao, “Balancing the Tradeoffs between Data Accessibility and Query Delay in Ad Hoc Networks,” Proc. IEEE Int’l Symp. Reliable Distributed Systems, pp. 289-298, 2004.
 S.-Y. Wu and Y.-T. Chang, “A User-Centered Approach to Active Replica Management in Mobile Environments,” IEEE Trans. Mobile Computing, vol. 5, no. 11, pp. 1606-1619, Nov. 2006.
 V. Srinivasan, P. Nuggehalli, C. Chiasserini, and R. Rao, “Cooperation in Wireless Ad Hoc Networks,” Proc. IEEE INFOCOM, pp. 808-817, 2003.