IOSR Journal of Computer Engineering (IOSRJCE) ISSN: 2278-0661 Volume 5, Issue 1 (Sep-Oct. 2012), PP 21-27 www.iosrjournals.

org

ODRS: Optimal Data Replication Scheme for Time Efficiency In MANETs

1
1 2

M.siva Lakshmi,2R.Raja Sekhar

(M.tech,Department of CSE,JNTU College of Engineering,Anantapur(A.P),INDIA) (R. Raja Sekhar, Assistance professor, Department of CSE , JNTUA , Anantapur (A.P),INDIA)

Abstract: In mobile ad hoc networks (MANETs), mobile nodes move freely from one place to another place
and link/node failures are common. Due to link/node failures leads to frequent network partitions. When network a network partition occurs, mobile nodes in one partition are not able to access data contained in other partition. For this reason the performance of the data access significantly decreased. To avoid such problems data replication scheme proposed to improve the performance of the data access, and hence data availability and query traffic increased and query delay should decrease,also, query rate query delay decreased and hit ratio increased. Keywords- MANETs, Data Replication, Query delay, Data availability, ODRS, combined access frequency, caching.

I.

Introduction

Mobile ad hoc networks (MANETs) have evolved as one of the hot research topic in the wireless communication. There has been a greater change in the wireless technologies, hence the gradual development of mobile devices such as cellular phones, laptops etc.There are two different types of approaches for providing the wireless communication between two mobile nodes. One approach is the centralized administration maintenance or fixed infrastructure and the other one is without fixed infrastructure or infrastructure less communication. An Ad hoc network contains the group of nodes participating in the data communication without fixed infrastructure. Each node in the network act as not only router but also host. A mobile ad hoc network (MANET) is a collection of autonomous wireless nodes that may move unpredictably, forming a temporary network without any fixed backbone infrastructure [1]. In which each node act as end system as well as a router that forwards the data items to desired destination nodes. These nodes are capable of single communication and multi-hop communication. In a mobile ad hoc network (MANET), data caching is essential as it increases the data availability and improves system performance. The major issue that faces cache management is the maintenance of data consistency .In a MANET, all messages sent between the server and the cache are subject to network delays, so cache consistency algorithms are developed to increase the probability of using data items from the cache. In this each node contains some data items, which is owner of that data items, and stored in a server. Hence data availability should be decreased and nodes query delay, query rate query delay should be increase. Due to the node mobility there is a frequent topology change in the network, thus routing becomes more challenging. A routing protocol is needed to route the data items or files to the destination through intermediate nodes without packet loss. In MANETs assumed end to end path between source and destination, But in the real world scenario this case is not valid means that routing protocol must handle intermediate nodes connectivity due to absence of end-to-end path. In mobile ad hoc networks (MANETs), nodes move freely from one place to another place, hence link/node failures are common and frequent network partitions occur. When network partition occurs, mobile nodes in one partition are not able to access data contained by nodes in other partitions, and hence decrease the performance of data access. In this paper, we propose new data replication scheme that provides solutions to data availability, nodes query delay, query rate query delay and hit ratio. As these metrics are important for mobile nodes to improve performance of the system that is data availability decrease, query delay decrease and hit ratio increase.Simulatrion results show that the proposed scheme can achieve these metrics and provide satisfying system performance. II. Related Work Data replication has been studied in the Web environment and distributed systems [6]-[8]. Data replication in web environment, where the goal is to place some replicas of the web servers among a number of possible locations, so that the query delay is reduced. Data replication in distributed database systems, where nodes contain the database are more reliable and less likely to fail/disconnect compared to those in MANETs. www.iosrjournals.org 21 | Page

ODRS: Optimal Data Replication Scheme For Time Efficiency In MANETS

Therefore, a small number of replicas can be used to provide high availability. In [3] et al. identified several research issues in data replication in MANET and attempted to classify data replication techniques. Hara [4], [5] proposed data replication schemes for ad hoc networks. Some other researchers address data access issues in MANETs considering network partitions. In [2] researchers introduced several localized algorithms to detect critical nodes and links for connectivity in MANETs. In [15] addressed the problem of replica allocation in a MANET by exploring group mobility. In [16] proposed schemes to deal with network partitions due to node movement by replicating services in the network, can provide guaranteed service with minimum number of replicated services. Hara [17] proposed several metrics to evaluate the impact of mobility on data availability. In [18] studied solutions for replicating location dependent data in MANETs to handle unreliable network connections. In [19] presented a middleware service that allows collaborative data sharing among ad hoc groups that are dynamically formed according to the network connectivity. In [10-12] to improve data availability and reduce the query delay by data replication along with caching. We have proposed a cooperative cache based data access framework, which provides the sharing and coordination of cached data among multiple mobile nodes [13]. In this framework, after a node sends a data request to the data owner, the data owner sends the data back. Since the data before reaching the requester, it may go through multi-hops. So that intermediate nodes may cache the data or the path to the data. Later, if some other nodes request for the same data and the intermediate nodes can give the data or the path to the data. Because the number of hops is reduced, also the query delay is reduced. In [14] implementation issues of cooperative cache are further studied, where the query delay can reduce by the proposed solution, there is a limitation on how much they can achieve. Generally, these schemes are passive approaches, because the data is only cached after some nodes start to use it. Further to increase the data availability and reduce the query delay, proactive data replication technique used where nodes actively replicate data. Issues related to data replication: Issues related to data replication in MANET are as follows (i) Power Consumption All mobile devices in the MANET are battery powered. If a node with less power is replicated with many frequently accessed data items, it soon gets drained and it cannot provide services any more. Thus replication algorithm should replicate data in the nodes that has sufficient power by periodically checking the remaining power of each node. (ii) Node mobility Nodes in the MANET are mobile which leads to dynamic topology. Thus replication algorithm has to support mobility prediction such that if a node is likely to move away from the network, its replicas will be replaced in some other nodes which is expected to remain in the network for a particular period of time. (iii) Resource availability In MANETs memory capacity is limited only and portable devices are participating .Before sending a replica to the node, the algorithm has to check whether a node has sufficient memory capacity to hold the data or not. (iv) Response Time Time is the crucial factor for many of the applications like rescue operations and military operations. Therefore data is accessed from the nearby replicated nodes than from the owner to improve the response time. (v) Network Partition If a node is in one partition it cannot provide services to other nodes in different partition. Therefore shared data has to be replicated in all the partitions. (vi) Replica relocation This topic addresses issues related to when, where, who and how replicas are allocated. Due to dynamic topology, static allocation of replicas is not possible. So that for data availability improvement replicas should be relocated dynamically improve data availability. (vii) Consistency Management If the data shared is read only, performance can be improved .By fully replicating the data in all the nodes, the performance can be improved at that time data shared is read only. Other replicas are invalid when a replica is updated frequently. So cache management mechanism is needed for manage the data consistency in the network. Our scheme enhances data accessibility by addressing the various issues. Scheme is composed of four main parts are following. What data is to replicate? Where to replicate data? www.iosrjournals.org 22 | Page

ODRS: Optimal Data Replication Scheme For Time Efficiency In MANETS

How to access data? How to synchronize data?

III. Optimal Data Replication Scheme In this section explains new data replication scheme to provide increased data availability, reduced query delay and increased hit ratio. 3.1. Basic idea of Optimal Data Replication Basic idea of optimal data replication as follows. In MENETs mobile nodes share data from multiple nodes collaboratively. Each node creates replicas of the data item and maintains replicas in its memory space. During data replication, to determine the allocation of replicas there is no central server and the data allocation in a distributed manner determine by the mobile nodes. Its decision to replicate data items is taken not only at the time of detecting network partitioning, but also during the time when the wireless connections become bad in terms of reliability, bandwidth and delay. The MANETs topology can be represented as an undirected graph G (V, E) where V is the set of vertices, which represents the mobile nodes in the network, and E is the set of edges in the graph, which represents the physical or logical links between the mobile nodes. When two nodes are connected by an edge in the graph, then they can communicate directly with each other. Let assume N denotes a network which contains m mobile nodes, N1, N2,..,Nm and let D denote a collection of n data items, d1,d2..., dn distributed in the network. For each pair of mobile nodes Ni and Nj, let tdij denotes the time delay for transmitting a data item of unit-size between each pair of nodes. Let flij represented link failure probability between node Ni and node Nj, which is equal to flij represents symmetric link. The network partitions occur when node/link failed. If any queries generated during network partition may fail because the requested data items are not available in the partition to which the requester belongs. Each node maintains some amount of data locally such node is called the original owner of the data. There is only one original owner for each data item. To improve the data availability, these data items may be replicated to other nodes. Each node has limited memory size, so that each node can contain (Cm <n) replicas only along with its original data items. 3.2.Notations used in Optimal Data Replication In optimal data replication following notations are used. N : indicates the set of mobile nodes in the network. Nm : indicates the total number of mobile nodes. D : represents the set of data items presented in the network. Dn : the total number of data items. Si : data item di size Cm : the memory size of each mobile node for containing data replicas. td : indicates the time delay taken for transmitting a data item of unit size between node Ni and Nj . fl : indicates between node Ni and Nj link failure probability daf : which denotes data access frequency between node Ni to data item dj 3.3.Optimal Data Rplication using Combined Access Frequency Function

Fig 1: Optimal data replication The above figure shows optimal data replication where Green color nodes indicates data items of that node is in cache. www.iosrjournals.org 23 | Page

ODRS: Optimal Data Replication Scheme For Time Efficiency In MANETS

Node with orange color indicates node sending query (data items) to server. Here server used for maintaining data items information. Blue color nodes represent data replicated nodes Node with purple color indicates forwarding data items to appropriate requester through single hop or multihops. Node with yellow color indicates data item not in the cache memory In this scheme, each mobile node cooperates with at most one neighbor only to decide which data to replicate. If two nodes Ni and Nj are neighboring nodes. Node Ni calculates the combined access frequency to data item dk of node Ni and node Nj at node Ni denoted as Caf , by using the function as follows Cafi j= (dafik + dafjk (1 flij)) / Si (1) In the same manner node N calculates combined access frequency of it and to data item d using the function as follows Cafji = (dafjk + dafi (1 flij)) / Si (2) Based on Caf value data availability considered between neighboring nodes. If the node Ni neighboring node is Nj ,which contain already replicated the data , so that no need to replicate the data. If the link failure probability between node Ni and node Nj is low, then node Ni is less likely to replicate this data item, because from node Nj it can always get the data item. If the link failure probability is high, and hence node Ni may like to replicate the data locally, Therefore, we define a priority value for node Ni to replicate data dk , it given its neighboring node Nj. The priority value denoted as Pkij by using the function as follows Pkij =Cafkij Wkij (3) k Where W ij indicates the impact on data availability by the neighboring node and the link failure probability. The Wkij value is computed as follows: Wkij =fl if data dk is replicated at Ni ; (4) if data dk is not replicated at Nj ; =1 Each node sorts the data according to the priority value P and takes data items with the highest P to replicate in its memory until no more data items can be replicated. The P value function is designed based on the following considerations To improve data availability it considers the access frequency from a neighboring node; It considers the data size, the data item with smaller size is given higher priority for replicating because this can improve the performance while reducing memory space; It gives high priority to local data access, and hence the interested data should be replicated locally to improve data availability and reduce query delay; It also considers link quality like link is stable or not and from the neighboring node the impact of data availability. Thus, if the link between two neighboring nodes is stable, they can have more cooperation in data replication. According to Optimal data replication scheme, it is possible. Due to the network partitions, node Ni is separated from nodes and it host data item dj. In this case, selects the next best data item according to the replication scheme. 3.4.Optimmal Data replication Scheme 1) for store the sorted values, initiate an array sort; 2) call the sorting procedure, if sort=Sort (); ( i.e start data replication} 3) mark all the nodes as black; 4) for ( i=1 to Nm ) do 5) id1= current node id; 6) if Nid1 is blue then 7) do nothing and continue to the next node; 8) end if 9) find out the smallest id (id2>id1) among all the black neighbors of Nid1; 10) If id2 exists then 11) calculate all the P values separately for Nid1 and; 12) these 2 sets of P values sort and store them in two arrays A1 and A2; 13) get data from array A1 from maximum to minimum and fill them into Nid1s memory until full; www.iosrjournals.org 24 | Page

ODRS: Optimal Data Replication Scheme For Time Efficiency In MANETS

14) get data from array A2 from maximum to minimum and fill them into Nid2s memory until full; 15) mark Nid1 and Nid2 as blue; 16) else 17) do nothing and continue to the next node; 18) end if 19) end for { process remaining nodes i.e nodes which cant find a black neighbor} 20) while black nodes exist do 21) allocate its own most interested data from sort to its memory; 22) end while At the beginning All nodes are marked as Black , which means that no one has done the allocation process . These nodes broadcast their ids and their access frequency for each data item. Among the Black nodes, the node which has the smallest id among its neighboring Black nodes starts the following process. It sends an invitation to the neighboring Black node with which it has the lowest link failure probability. If the neighbor only receives one such invitation, these two neighboring nodes calculate the P values and each node allocates data items with the highest P values until it cannot accommodate more data items. Then both nodes are marked as black and no longer participate the replication process until the next allocation period. Two or more nodes may start the process at the same time. As long as they do not pick the same node as the most reliable neighbor, they can allocate their replicas at the same time. Otherwise, the node picked by more than one neighbor only accepts the invitation from the node with the lowest id. All other inviting nodes have to select another neighbor again. If all neighbors of a Black node are black nodes, which mean that this Black node cannot find any neighbor to cooperate in the allocation process, it only allocates its own most interested data items to its memory. Node Ni should host dj but Ni is separated from nodes that have dj because of network partitions. In this situation, Ni selects the next data item according to the replication scheme.

IV.

Performance Evaluation

In this section, we evaluate the performance of the proposed scheme through simulations. It has been implemented in ns-2 simulator [20] using Random way point mobility model. Basic simulation parameters are summarized in table 1. TABLE 1:Basic simulation parameters Parameter Ns-2 value range Reconnaissance area 20002000m Number of nodes Nm 80 100,300,500 Memory size C 20 Radio range R 100m 50m-300m 0.8 0.7-1.0

4.1. Simulation setup Beginnings of the simulation 80 nodes are placed in 2000m 2000m area randomly. The radio range is set to be 100 and memory size set to 200.Two nodes communicated with each other when two nodes node Ni and node Nj are within the radio range ( i.e. ( i ,j ) <100). So that the communication link between those nodes may be fail, and hence the link failure probability l is defined as follows . flij = ((i,j) /D) 2 (5) is used to adjust flij to a more reasonable value.. The proposed scheme does not depend on the failure model in Equation (5) and they are able to work as long as the failure probability between neighboring nodes can be estimated. The number of data items Nm is set to be the number of mobile nodes Nm [9]. Data item di is original owner is for all i [1, Nm]. The data item size is uniformly distributed n Smin and Smax . Memory size of each node is C.

www.iosrjournals.org

25 | Page

ODRS: Optimal Data Replication Scheme For Time Efficiency In MANETS

Two patterns of access are used in the simulation.. All nodes follow the Zipf -like access pattern, but different nodes have different hot data items. By selecting an offset value randomly for each node Ni offset, which is between 1 and 1, this can be done. In this access pattern the most frequently accessed data item is moved to be off instead of 1; the second frequently data accessed data item is offset i+1 instead of 2 , and so on All nodes have the same access pattern and they have the same access probability to the same data item. In order to avoid routing cycles on the query path, a maximal hop count is used to limit the number of hops for each query. The performance metrics used in the simulation are mainly data availability, query delay and hit ratio. The amount of query traffic is also evaluated to show the protocol overhead. Here, the amount of query traffic can also be used as a metric of system power consumption. This is because in wireless communication, data transmission is the key factor affecting the system power consumption compared to other factors such as disk or CPU operations [9]. Therefore, if there is more query traffic, more energy consumption is expected. If one replication scheme generates less traffic, it is more power efficient. When a query for data item dk is generated by node Ni, if dk can found locally, or at that node that is reachable through single hop or multi-hops. So that this access is considered successful..The query delay is the number of hops taken from node Ni to the nearest node that has data item dk multiplied by the data size , and hence the query traffic is defined as all messages involved processing the query. If data item dk is in the Nk local memory , and hence both the query delay and query traffic are zero (0). 4.2.Simulation results Effects of number of nodes in the networks: The number of nodes in the network indicates the node density of the network. When the number of nodes increases, the density of the network increases and it becomes better connected and the data availability increases. As the number of nodes increases, nodes have more opportunities to get the data from their neighboring nodes, and proposed scheme has performance improvements in terms of data availability as expected. Figure 2(b) and 2(c) shows the effects of number of nodes with query delay and hit ratio. Effects of query rate: When the number of nodes increase, the data availability increased and the query rate is expected to increased.Figures.2 (a) shows that Query delay decrease as query rate decreases. When the query rate increased, the query delay also be increases. Effects of query delay: We evaluate the system performance when the query delays changes. As query delay decreases, data can be contained by a node and the data availability increases. Similarly, more data can be found locally, hence the query delay and query traffic decrease. Figure 2(a) shows the effects of query delay with query rate. Effects of hit ratio: When the number of nodes increases, Due to data replication more nodes contains data and the hit ratio should be decreased. Figure 2(b) shows the effects of the hit ratio, when the number of nodes increased.

Fig.2(a) query rate with query delay

Fig.2(b) nodes with hit ratio

www.iosrjournals.org

26 | Page

ODRS: Optimal Data Replication Scheme For Time Efficiency In MANETS

Fig.2(c) nodes with query delay V. Conclusion and Future Work In MANETs, data replication done to improve data availability, reduce query delay and increase hit ratio. Due to link failure, network partitions occur, as data saved at other nodes may not accessible. So data replication used to improve data availability and hit ratio and reduced query delay. In this paper, we proposed optimized data replication that efficiently improved data availability, reduced the query delay and increased hit ratio. In this scheme, each mobile node only cooperates with at most one neighbor to decide which data to replicate. In future work, we also include the relationship among different data items; the data update issue, and the data discovery issue. Data semantics can be used to improve performance of query and hence we can apply semantic based technique to further improve the performance to extend the proposed scheme to handle data update, data consistency or data discovery issues.

References
[1]. [2]. [3]. [4]. [5]. [6]. [7]. [8]. [9]. [10]. [11]. [12]. [13]. [14]. [15]. [16]. [17]. [18]. [19]. [20]. Fife, L., Grunewald, L.: Research issues for data communication in mobile ad hoc network database systems. ACM SIGMOD RECORD, pp. 4247 (2003) M. Jorgic, I. Stojmenovic, M. Hauspie, and D. Simplot-Ryl, Localized algorithms for detection of critical nodes and links for connectivity in ad hoc P. Padmanabhan, L. Grunewald, A. Vallur, and M. Atiquzza- man, A survey of data replication techniques for mobile ad hoc network databases, The VLDB Journal, vol. 17, pp. 1143 1164, 2008. T. Hara, Effective replica allocation in ad hoc networks for improving data accessibility, IEEE INFOCOM, 2001. T. Hara and S. K. Madria, Data replication for improving data accessibility in ad hoc networks, IEEE Transactions on Mobile Computing, vol. 5, no. 11, pp. 15151532, 2006 L. Qiu, V. N. Padmanabhan, and G. M. Voelker, On the placement of web server replicas, IEEE INFOCOM, 2001. H. Yu and A. Vahdat, Minimal replication cost for availability, ACM Symposium on Principles of Distributed Computing (PODC), 2002. L. Gao, M. Dahlin, A. Nayate, J. Zheng, A. Iyengar, Consistency and replication: application specific data replication for edge services, International Conference on World Wide Web,2003. R. Kravets and P. Krishnan, Power management techniques for mobile communication, ACM MOBICOM, pp. 157168,1998 G. Cao, L. Yin, and C. Das, A cooperative cache based data ccess framework for ad hoc networks, IEEE Computer, Feb.2004. M. Fiore, F. Mininni, C. Casetti, and C. Chiasserini, To cache or not to cache? IEEE INFOCOM, 2009. Y. Du, S. Gupta, and G. Varsamopoulos, Improving on-demand data access efficiency in magnets with cooperative caching, Ad Hoc Networks, vol. 7, pp. 579598, May 2009. L. Yin and G. Cao, Supporting cooperative caching in ad hoc networks, IEEE Transaction on Mobile Computing, vol. 5, no. 1, January 2006. J. Zhao, P. Zhang, G. Cao, and C. R. Das, Cooperative caching in wireless p2p networks: design, implementation, and evaluation, vol. 21, no. 2, pp. 229241, February 2010. J.-L. Huang and M.-S. Chen, On the effect of group mobility to data replication in ad hoc networks, IEEE Transactions on Mobile Computing, vol. 5, no. 5, pp. 492507, 2006 K. Wang and B. Li, Efficient and guaranteed service coverage in partitionable mobile ad-hoc networks, IEEE INFOCOM,2002. T. Hara, Quantifying impact of mobility on data availability in mobile ad hoc networks, IEEE Transactions on Mobile Computing, vol. 9, pp. 241258, 2010. Ramany and P. Bertok, Replication of location-dependent data in mobile ad hoc networks, ACM MobiDE, pp. 3946, 2008. M. Boulkenafed and V. Issarny, A middle ware service for mobile ad hoc data sharing, enhancing data availability, ACM Middleware, 2003.1998. http://www.isi.edu/nsnam/ns - The network simulator-2 (NS-2).

www.iosrjournals.org

27 | Page