File sharing applications in mobile ad hoc networks (MANETs) have attracted more and more attention in recent years. The efficiency of file querying suffers from the distinctive properties of such networks including node mobility and limited communication range and resource. An intuitive method to alleviate this problem is to create file replicas in the network. However, despite the efforts on file replication, no research has focused on the global optimal replica creation with minimum average querying delay.
Specifically, current file replication protocols in mobile ad hoc networks have two shortcomings. First, they lack a rule to allocate limited resources to different files in order to minimize the average querying delay. Second, they simply consider storage as available resources for replicas, but neglect the fact that the file holders’ frequency of meeting other nodes also plays an important role in determining file availability. Actually, a node that has a higher meeting frequency with others provides higher availability to its files. This becomes even more evident in sparsely distributed MANETs, in which nodes meet disruptively.
In this paper, we introduce a new
concept of resource for file replication, which considers both node storage and
node meeting ability. We theoretically study the influence of resource
allocation on the average querying delay and derive an optimal file replication
rule (OFRR) that allocates resources to each file based on its popularity and
size. We then propose a file replication protocol based on the rule, which
approximates the minimum global querying delay in a fully distributed manner.
Our experiment and simulation results show the superior performance of the
proposed protocol in comparison with other representative replication
protocols.
1.2 INTRODUCTION
With the increasing popularity of mobile devices, e.g., smartphones and laptops, we envision the future of MANETs consisted of these mobile devices. By MANETs, we refer to both normal MANETs and disconnected MANETs, also known as delay tolerant networks (DTNs). The former has a relatively dense node distribution in an area while the latter has sparsely distributed nodes that meet each other opportunistically. On the other side, the emerging of mobile file sharing applications on the peer-to-peer (P2P) file sharing over such MANETs. The local P2P file sharing model provides three advantages. First, it enables file sharing when no base stations are available (e.g., in rural areas). Second, with the P2P architecture, the bottleneck on overloaded servers in current clientserver based file sharing systems can be avoided. Third, it exploits otherwise wasted peer to peer communication opportunities among mobile nodes. As a result, nodes can freely and unobtrusively access and share files in the distributed MANET environment, which can possibly support interesting applications.
For example, mobile nodes can share files based on users’ proximity in the same building or in a local community. Tourists can share their travel experiences or emergency information with other tourists through digital devices directly even when no base station is available in remote areas. Drivers can share road information through the vehicle-to-vehicle communication. However, the distinctive properties of MANETs, i.e., node mobility, limited communication range and resource, have rendered many difficulties in realizing such a P2P file sharing system. For example, file searching turns out to be difficult since nodes in MANETs move around freely and can exchange information only when they are within the communication range. Broadcasting can quickly discover files, but it leads to the broadcast storm problem with high energy consumption.
Probabilistic routing and file discovery protocols avoid broadcasting by forwarding a query to a node with higher probability of meeting the destination. But the opportunistic encountering of nodes in MANETs makes file searching and retrieval non-deterministic. File replication is an effective way to enhance file availability and reduce file querying delay. It creates replicas for a file to improve its probability of being encountered by requests. Unfortunately, it is impractical and inefficient to enable every node to hold the replicas of all files in the system considering limited node resources. Also, file querying delay is always a main concern in a file sharing system. Users often desire to receive their requested files quickly no matter whether the files are popular or not. Thus, a critical issue is raised for further investigation: how to allocate the limited resource in the network to different files for replication so that the overall average file querying delay is minimized? Recently, a number of file replication protocols have been proposed for MANETs. In these protocols, each individual node replicates files it frequently queries or a group of nodes create one replica for each file they frequently query. In the former, redundant replicas are easily created in the system, thereby wasting resources.
In the latter, though redundant replicas
are reduced by group based cooperation, neighboring nodes may separate from
each other due to node mobility, leading to large query delay. There are also
some works addressing content caching in disconnected MANETs/ DTNs for efficient
data retrieval or message routing. They basically cache data that are
frequently queried on places that are visited frequently by mobile nodes. Both
the two categories of replication methods fail to thoroughly consider that a
node’s mobility affects the availability of its files. In spite of efforts,
current file replication protocols lack a rule to allocate limited resources to
files for replica creation in order to achieve the minimum average querying
delay, i.e., global search efficiency optimization under limited resources.
They simply consider storage as the resource for replicas, but neglect that a
node’s frequency to meet other nodes (meeting ability in short) also influences
the availability of its files. Files in a node with a higher meeting ability
have higher availability.
1.3 LITRATURE SURVEY
CONTACT DURATION AWARE DATA REPLICATION IN DELAY TOLERANT NETWORKS
AUTHOR: X. Zhuo, Q. Li, W. Gao, G. Cao, and Y. Dai
PUBLISH: Proc. IEEE 19th Int’l Conf. Network Protocols (ICNP), 2011.
EXPLANATION:
The recent popularization of
hand-held mobile devices, such as smartphones, enables the inter-connectivity
among mobile users without the support of Internet infrastructure. When mobile
users move and contact each other opportunistically, they form a Delay Tolerant
Network (DTN), which can be exploited to share data among them. Data
replication is one of the common techniques for such data sharing. However, the
unstable network topology and limited contact duration in DTNs make it
difficult to directly apply traditional data replication schemes. Although
there are a few existing studies on data replication in DTNs, they generally
ignore the contact duration limits. In this paper, we recognize the deficiency
of existing data replication schemes which treat the complete data item as the
replication unit, and propose to replicate data at the packet level. We
analytically formulate the contact duration aware data replication problem and
give a centralized solution to better utilize the limited storage buffers and
the contact opportunities. We further propose a practical contact Duration
Aware Replication Algorithm (DARA) which operates in a fully distributed manner
and reduces the computational complexity. Extensive simulations on both
synthetic and realistic traces show that our distributed scheme achieves
close-to-optimal performance, and outperforms other existing replication
schemes.
SOCIAL-BASED COOPERATIVE CACHING IN DTNS: A CONTACT DURATION AWARE APPROACH
AUTHOR: X. Zhuo, Q. Li, G. Cao, Y. Dai, B.K. Szymanski, and T.L. Porta,
PUBLISH: Proc. IEEE Eighth Int’l Conf. Mobile Adhoc and Sensor Systems (MASS), 2011.
EXPLANATION:
Data access is an important issue
in Delay Tolerant Networks (DTNs), and a common technique to improve the
performance of data access is cooperative caching. However, due to the
unpredictable node mobility in DTNs, traditional caching schemes cannot be
directly applied. In this paper, we propose DAC, a novel caching protocol
adaptive to the challenging environment of DTNs. Specifically, we exploit the
social community structure to combat the unstable network topology in DTNs. We
propose a new centrality metric to evaluate the caching capability of each node
within a community, and solutions based on this metric are proposed to
determine where to cache. More importantly, we consider the impact of the
contact duration limitation on cooperative caching, which has been ignored by
the existing works. We prove that the marginal caching benefit that a node can
provide diminishes when more data is cached. We derive an adaptive caching
bound for each mobile node according to its specific contact patterns with
others, to limit the amount of data it caches. In this way, both the storage
space and the contact opportunities are better utilized. To mitigate the coupon
collector’s problem, network coding techniques are used to further improve the
caching efficiency. Extensive trace-driven simulations show that our
cooperative caching protocol can significantly improve the performance of data
access in DTNs.
SEDUM: EXPLOITING SOCIAL NETWORKS IN UTILITY-BASED DISTRIBUTED ROUTING FOR DTNS
AUTHOR: Z. Li and H. Shen
PUBLISH: IEEE Trans. Computers, vol. 62, no. 1, pp. 83-97, Jan. 2012.
EXPLANATION:
However, current probabilistic
forwarding methods only consider node contact frequency in calculating the
utility while neglecting the influence of contact duration on the throughput,
though both contact frequency and contact duration reflect the node movement
pattern in a social network. In this paper, we theoretically prove that
considering both factors leads to higher throughput than considering only
contact frequency. To fully exploit a social network for high throughput and
low routing delay, we propose a Social network oriented and duration utility-based
distributed multicopy routing protocol (SEDUM) for DTNs. SEDUM is distinguished
by three features. First, it considers both contact frequency and duration in
node movement patterns of social networks. Second, it uses multicopy routing
and can discover the minimum number of copies of a message to achieve a desired
routing delay. Third, it has an effective buffer management mechanism to
increase throughput and decrease routing delay. Theoretical analysis and
simulation results show that SEDUM provides high throughput and low routing
delay compared to existing routing approaches. The results conform to our
expectation that considering both contact frequency and duration for delivery
utility in routing can achieve higher throughput than considering only contact
frequency, especially in a highly dynamic environment with large routing
messages.
CHAPTER 2
2.0 SYSTEM ANALYSIS
2.1 EXISTING SYSTEM:
This work focuses on Delay Tolerant Networks (DTNs) in a social network environment. DTNs do not have a complete path from a source to a destination most of the time. Previous data routing approaches in DTNs are primarily based on either flooding or single-copy routing. However, these methods incur either high overhead due to excessive transmissions or long delays due to suboptimal choices for relay nodes. Probabilistic forwarding that forwards a message to a node with a higher delivery utility enhances single-copy routing.
Previous file sharing applications in mobile ad hoc networks (MANETs) have attracted more efficiency of file querying suffers from the distinctive properties of MANETs including node mobility and limited communication range and resource. An intuitive method to alleviate this problem is to create file replicas in the network. However, despite the efforts on file replication, no research has focused on the global optimal replica sharing with minimum average querying delay communication links between mobile nodes are transient and network maintenance overhead is a major performance bottleneck for data transmission. Low node density makes it difficult to establish end-to-end connection, thus impeding a continuous end-to-end path between a source and a destination.
DTN networks for
communication in outer space, but is now directly accessible from our pockets both
the characteristics of MANETs and the requirements of P2P file sharing an
application layer overlay network. We port a DTN type solution into an
infrastructure-less environment like MANETs and leverage peer mobility to reach
data in other disconnected networks. This is done by implementing an
asynchronous communication model, store-delegate-and-forward, like DTNs, where
a peer can delegate unaccomplished file download or query tasks to special
peers. To improve data transmission performance while reducing communication
overhead, we select these special peers by the expectation of encountering them
again in future and assign them different download starting point on the file.
2.1.1 DISADVANTAGES:
2.2 PROPOSED SYSTEM:
We propose a distributed file replication protocol that can approximately realize the optimal file replication rule with the two mobility models in a distributed manner in the OFRR in the two mobility models (i.e., Equations (22) and (28)) have the same form, we present the protocol in this section without indicating the specific mobility model. We first introduce the challenges to realize the OFRR and our solutions. We then propose a replication protocol to realize OFRR and analyze the effect of the protocol.
We propose the priority competition and split file replication protocol (PCS). We first introduce how a node retrieves the parameters needed in PCS and then present the detail of PCS. we briefly prove the effectiveness of PCS. We refer to the process in which a node tries to copy a file to its neighbors as one round of replica distribution. Recall that when a replica is created for a file with P, the two copies will replicate files with priority P =2 in the next round. This means that the creation of replicas will not increase the overall P of the file. Also, after each round, the priority value of each file or replica is updated based on the received requests for the file.
Then, though some replicas may be
deleted in the competition, the total amount of requests for the file remains
stable, making the sum of the Ps of all replicas and the original file roughly
equal to the overall priority value of the file. Then, we can regard the
replicas of a file as an entity that competes for available resource in the
system with accumulated priority P in each round. Therefore, in each round of
replica distribution, based on our design of PCS, the overall probability of
creating a replica for an original file
2.2.1 ADVANTAGES:
The community-based mobility model has been used in content dissemination or routing algorithms for disconnected MANETs/DTNs to depict node mobility. In this model, the entire test area is split into different sub-areas, denoted as caves. Each cave holds one community.
RWP model, we can assume that the inter-meeting time among nodes follows exponential distribution. Then, the probability of meeting a node is independent with the previous encountered node. Therefore, we define the meeting ability of a node as the average number of nodes it meets in a unit time and use it to investigate the optimal file replication.
PCS, we used two routing protocols in the
experiments. We first used the Static Wait protocol in the GENI experiment, in
which each query stays on the source node waiting for the destination. We then
used a probabilistic routing protocol (PROPHET) in which a node routes requests
to the neighbor with the highest meeting ability.
2.3.1 HARDWARE REQUIREMENT:
CHAPTER 3
3.0 SYSTEM DESIGN:
Data Flow Diagram / Use Case Diagram / Flow Diagram:
External sources or destinations, which may be people or organizations or other entities
Here the data referenced by a process is stored and retrieved.
People, procedures or devices that produce data’s in the physical component is not identified.
Data moves in a specific direction from an origin to a destination. The data flow is a “packet” of data.
MODELING RULES:
There are several common modeling rules when creating DFDs:
3.1 ARCHITECTURE DIAGRAM
3.2 DATAFLOW DIAGRAM
UML DIAGRAMS:
3.2 USE CASE DIAGRAM:
3.3 CLASS DIAGRAM:
3.4 SEQUENCE DIAGRAM:
3.5
ACTIVITY DIAGRAM:
CHAPTER 4
4.0 IMPLEMENTATION:
OFRR PROTOCOL:
4.1 ALGORITHM
PSEUDO-CODE
FOR PCS ALGORITHM:
4.2 MODULES:
DELAY TOLERANT NETWORKS (DTNS):
P2P FILE SHARING IN MANETS:
MANETS WITH RWP MODEL:
DISTRIBUTED FILE REPLICATION:
EXPERIMENTAL RESULTS:
REPLICA COST:
REPLICA DISTRIBUTAION:
AVERAGE
DELAY:
4.3 MODULE DESCRIPTION:
DELAY TOLERANT NETWORKS (DTNS):
P2P FILE SHARING IN MANETS:
MANETS WITH RWP MODEL:
DISTRIBUTED FILE REPLICATION:
EXPERIMENTAL RESULTS:
REPLICA COST:
REPLICA DISTRIBUTAION:
AVERAGE
DELAY:
CHAPTER 8
8.1 CONCLUSION & FUTURE:
In this paper, we investigated the problem of how to allocate limited resources for file replication for the purpose of global optimal file searching efficiency in MANETs. Unlike previous protocols that only consider storage as resources, we also consider file holder’s ability to meet nodes as available resources since it also affects the availability of files on the node. We first theoretically analyzed the influence of replica distribution on the average querying delay under constrained available resources with two mobility models, and then derived an optimal replication rule that can allocate resources to file replicas with minimal average querying delay.
Finally, we designed the priority
competition and split replication protocol (PCS) that realizes the optimal
replication rule in a fully distributed manner. Extensive experiments on both
GENI testbed, NS-2, and event-driven simulator with real traces and synthesized
mobility confirm both the correctness of our theoretical analysis and the
effectiveness of PCS in MANETs. In this study, we focus on a static set of
files in the network. In our future work, we will theoretically analyze a more
complex environment including file dynamics (file addition and deletion, file
timeout) and dynamic node querying pattern.