11-12-2012, 12:45 PM
Handling Selfishness in Replica Allocation over a Mobile Ad Hoc Network
1Handling Selfishness.pdf (Size: 2.1 MB / Downloads: 51)
Abstract
In a mobile ad hoc network, the mobility and resource constraints of mobile nodes may lead to network partitioning or
performance degradation. Several data replication techniques have been proposed to minimize performance degradation. Most of
them assume that all mobile nodes collaborate fully in terms of sharing their memory space. In reality, however, some nodes may
selfishly decide only to cooperate partially, or not at all, with other nodes. These selfish nodes could then reduce the overall data
accessibility in the network. In this paper, we examine the impact of selfish nodes in a mobile ad hoc network from the perspective of
replica allocation. We term this selfish replica allocation. In particular, we develop a selfish node detection algorithm that considers
partial selfishness and novel replica allocation techniques to properly cope with selfish replica allocation. The conducted simulations
demonstrate the proposed approach outperforms traditional cooperative replica allocation techniques in terms of data accessibility,
communication cost, and average query delay.
INTRODUCTION
MOBILE ad hoc networks (MANETs) have attracted a lot
of attention due to the popularity of mobile devices
and the advances in wireless communication technologies
[13], [14], [31]. A MANET is a peer-to-peer multihop mobile
wireless network that has neither a fixed infrastructure nor
a central server. Each node in a MANET acts as a router,
and communicates with each other. A large variety of
MANET applications have been developed [27]. For
example, a MANET can be used in special situations,
where installing infrastructure may be difficult, or even
infeasible, such as a battlefield or a disaster area. A mobile
peer-to-peer file sharing system is another interesting
MANET application [9], [19].
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 [12].
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
[12] [13] [32].
PROPOSED STRATEGY
Overview
Our strategy consists of three parts: 1) detecting selfish
nodes, 2) building the SCF-tree, and 3) allocating replica. At
a specific period, or relocation period [12], each node
executes the following procedures:
. Each node detects the selfish nodes based on credit
risk scores.
. Each node makes its own (partial) topology graph and
builds its own SCF-tree by excluding selfish nodes.
. Based on SCF-tree, each node allocates replica in a
fully distributed manner.
The CR score is updated accordingly during the query
processing phase. We borrow the notion of credit risk from
economics to effectively measure the “degree of selfishness.”
In economics, credit risk is the measured risk of loss
due to a debtor’s nonpayment of a loan. A bank examines
the credit risk of an applicant prior to approving the loan.
The measured credit risk of the applicant indicates if he/she
is creditworthy. We take a similar approach. A node wants
to know if another node is believable, in the sense that a
replica can be paid back, or served upon request to share a
memory space in a MANET.
Building SCF-Tree
The SCF-tree based replica allocation techniques are
inspired by human friendship management in the real
world, where each person makes his/her own friends
forming a web and manages friendship by himself/herself.
He/she does not have to discuss these with others to
maintain the friendship. The decision is solely at his/her
discretion. The main objective of our novel replica allocation
techniques is to reduce traffic overhead, while
achieving high data accessibility. If the novel replica
allocation techniques can allocate replica without discussion
with other nodes, as in a human friendship management,
traffic overhead will decrease.
Allocating Replica
After building the SCF-tree, a node allocates replica at every
relocation period. Each node asks nonselfish nodes within
its SCF-tree to hold replica when it cannot hold replica in its
local memory space. Since the SCF-tree based replica
allocation is performed in a fully distributed manner, each
node determines replica allocation individually without any
communication with other nodes.
Since every node has its own SCF-tree, it can perform
replica allocation at its discretion. For example, in Fig. 3,
after building the SCF-tree in Fig. 3b, N1 may ask N2 to hold
some replicas. Note that the decision, whether to accept the
replica allocation request or not, will be made at N2’s
discretion (if N2 is selfish, it may not accept the replica
allocation request). Afterward, node N1 may issue a query
for the replicas. At this time, N1 is likely to recognize
whether the expected N2 serves the query (i.e., nonselfish) or
not (i.e., selfish).
Parameter Setting in Our Strategy
Several parameters are used in our strategy. For the
selfishness detection algorithm, we use the threshold .
For the selfishness features update algorithm, we use the
predefined wait time ! and need to initialize the selfishness
alarm Pk
i . In building the SCF-tree, we use the depth d. We
select data accessibility as the most important criterion to
determine the values of parameters.
We set ! to 50 units of simulation time, since we observe
that one round of request-response exchanges in the entire
network takes less than 50 units of simulation time in our
simulation setting. A similar reasoning is made in a prior
simulation environment [14]. We choose to use 2 as the
default depth of the (e)SCF-tree experimentally after
inspecting our simulation results. We observe that average
query delay, data accessibility, and communication cost are
insensitive to the depth of the SCF-tree. More specifically,
both average query delay and data accessibility are almost
the same with varying depths of SCF-tree, while communication
cost increases marginally as the depth increases.
CONCLUSION
In contrast to the network viewpoint, we have addressed
the problem of selfish nodes from the replica allocation
perspective. We term this problem selfish replica allocation.
Our work was motivated by the fact that a selfish replica
allocation could lead to overall poor data accessibility in a
MANET. We have proposed a selfish node detection
method and novel replica allocation techniques to handle
the selfish replica allocation appropriately. The proposed
strategies are inspired by the real-world observations in
economics in terms of credit risk and in human friendship
management in terms of choosing one’s friends completely
at one’s own discretion. We applied the notion of credit risk
from economics to detect selfish nodes. Every node in a
MANET calculates credit risk information on other connected
nodes individually to measure the degree of
selfishness. Since traditional replica allocation techniques
failed to consider selfish nodes, we also proposed novel
replica allocation techniques. Extensive simulation shows
that the proposed strategies outperform existing representative
cooperative replica allocation techniques in terms of
data accessibility, communication cost, and query delay. We
are currently working on the impact of different mobility
patterns. We plan to identify and handle false alarms in
selfish replica allocation.