Abstract:
Need for it?
A fundamental goal of researches in WSNs is to reduce the communication operations
and prolong the total lifetime of sensor networks.
Making effective use of the vast amounts of data gathered by large scale sensor networks
will require scalable, self-organizing, and energy-efficient data dissemination
algorithms
Distributed Hash Tables (DHTs) over WSNs is a new routing paradigm promises several
advantages over conventional routing protocols
CONCEPTSHOULD BE CLEAR BEFORE IT?
-
hashing
-distributed hash table
-GPSR
-directed diffusion
-clustering
-data centric storage
-perimeter refresh protocol
ROUTING TECHNIQUES USING DHTS OVER WSNS
1) GHT(Geographic Hash Table)
Assumption:
->large scale sensor network spread out over an area which geographical boundary is known
->nodes know their geographical position this can be achived through GPS.
->sensor network is connected to the outside word by some access point.
->the data dissemination algorithms should seek
to minimize communication in order to extend overall system lifetime.
->GHTuses a novel perimeter refresh protocol to provide both persistence and consistency when nodes fail
or move.
KEYWORDS:
home node:
We define the home node for a GHT packet to be the node geographically nearest the destination
coordinates of the packet. The home node serves as the rendezvous point for Put() and Get() operations on
the same key.
Home perimeter:
the path between home node and node which have detected event is called home perimeter.
Perimeter refreshes protocol:
GHT uses the perimeter refresh protocol (PRP) to accomplish replication of key-value pairs and
their consistent placement at the appropriate home nodes when the network topology changes.
PRPstores a copy of a key-value pair at each node on the home perimeter.
PRP generates refresh packets periodically using a simple timer scheme. Every Th seconds, the
home node for a key generates a refresh packet addressed to the hashed location of that key. The refresh
contains the data stored for that key, and is routed exactly as are Get() and Put() packets in GHT.
Working:
First, Data Dissemination is start with flooding the task to be done by entire sensor network, The
tasks specify which events to detect, how to detect them, and what actions to take upon detection.
When event has been detected there will be three options to store the event information based on
location…
1)external storage
2)local storage
3)data centric storage
future work:
still need investigate
à
Foremost among these is the effect of varying node density.
à
To avoid hashing keys to points outside the sensornet, GHT requires
approximate knowledge of a sensornet’s boundarie An
open research problem is to devise scalable distributed algorithms to map these
(possibly
changing!)
geographic boundaries.
2) CSN (Chord for sensor networks)
Chord
for a sensor network (CSN) that uses the Chord’s DHT over the sensor network.
CSN is used to bound times for data lookup, --- still not clear…
3) CHR (Cell Hash
Routing)
In
CHR we divide the space into equally-sized
cells that have the shape of squares, as the grid depicted in Figure 1.
Division into
cells:
The size of the cells is limited by the communication range
of the nodes, because we require that a node in a cell can always listen to any
other node either in its own cell or in any adjacent cell. This restriction
ensures that in most circumstances, the clustered network stays connected, as
long as the initial network is also connected. If we assume that nodes have a
communication range of R, the resulting
square side is at most R/√8. This can be seen in Figure 1.
Nodes need to be aware of other nodes in the neighboring
cells, mainly for two reasons: i) the routing
scheme requires nodes to know whether or not the adjacent cells are populated
and ii) we do not require nodes to perform
some kind of leader election algorithm;
Assumption:
1)All the nodes know and can reach all the other nodes
in their own and in any of the adjacent cells.
2) A broadcast message inside a cell
is received by all nodes of that cell.
The purpose of Assumption (1) is to ensure that a node has
sufficient knowledge to route messages and to support the DHT in the clustered
hierarchy.
The purpose of Assumption (2) is to ensure a simple means
of communication among nodes of the same cell, to enable operation of the DHT.
Conclusion and
future work:
The results presented here show that CHR is a viable
alternative to build a DHT for ad hoc wireless networks. Therefore we plan to pursuit this work,
by designing a complementary set of mechanisms that address the limitations of
this current implementation. Namely:
• Dynamic Cell
Structure:
when the number of nodes in a cell drops below l, the cell is considered empty.
On the contrary, the cell needs to acquire h nodes before it is considered populated (h >
l). Note that the value h should be fairly small. As a consequence, knowing h does not require much memory, because, in general, a node will
not need to know all the eighbors in its
own cell (i.e., Assumption 2.1 can be relaxed). A cell leaving the network
delivers its keys to its home cell. An entering cell needs to query its home
perimeter to receive its keys. Additionally, it will also receive keys of empty
cells for which it becomes the home cell.
• General non-UDG model:
in more
general models, it is possible for a node not to see some of its neighbors in
its cell or in some adjacent cell. One possible approach to overcome this
problem is to create routing tables to mreach only the invisible nodes inside
the cell or adjacent cells.
• Incorrect
determination of position:
in this paper, we assumed that nodes can always determine
their position exactly, which is actually not the case. The consequence of this
is that a node may consider itself to be in the wrong cell. In a sense, this
resumes to the non-UDG model.
• Cluster induces
disconnection:
occasionally, the clustering mechanism may disconnect the
network. This event should be rare, especially in denser networks, where use of
CHR is
more worthwhile. A straightforward solution consists of creating the necessary
links and then using a geographically-scoped broadcast to remove intersections.
• Fault-tolerance
requirements:
one of the occurrences
that CHR should
try to avoid as much as possible is
the loss of stored (key,value) pairs. We already suggested
the use of thresholds to ensure that keys are sufficiently spread among nodes
of the same cell. This mechanims can be complemented with a technique already
used in wired DHTs, e.g., [18], that consists of using k hash keys to replicate contents in different cells.
4)T-DHT (Topology based
Distributed Hash Table)
Using a virtual coordinate system, we
construct a distributed hash table which is strongly oriented to the underlying
network topology. Thus, adjacent areas in the hash table commonly have a direct
link in the network. Routing in the T-DHT guarantees reachability and
introduces low hopoverhead compared with the shortest path.
Overview of working:
the
proposed algorithm does not rely on position information. Building a TDHT
consists of two steps:
(1)
The construction of a virtual coordinate space which represents the network
topology.
(2)
On top of these coordinates we build a two-dimensional hash table, where each
node maintains the data close to its virtual position.
first step can be achieved
by light weight virtual coordinate system
future work:
The
presented scheme is ongoing work, and many interesting questions still need to
be addressed. Currently,we are evaluating the impact of the positions of the
reference nodes as well as the number of reference nodes. Furthermore, we will
evaluate the improvement in routing performance arising
from
maintaining a two-hop neighborhood.
5)VRR and(Virtual Ring Routing)
6)Scatter Pastry.
COMPARISON:
\
