

% $Id: easm_replication.tex,v 1.3 2005/04/08 21:21:45 gokhale Exp $

\subsection{Analytical Results}
\label{sec:analytical}

In this section we give an analytical study for our scheme, and compare
and contrast our scheme with the Adaptive Ring-based Index (ARI). We
compare the schemes, specifically the fault-tolerence behavior against 
two dimensions, instantaneous node failure and node mobility. We specify
the performance of each scheme in terms of query and response messages lost.

1. Query Messages. Both schemes are randezvous-based, that is a randezvous 
point is appointed which knows instantaneous storage node location that 
contains the sensed data. The total cost associated with node failure of
each {\em node type} is calculated in order to compare EASM and ARI. Node 
type could be 1. routing node, GPSR routes the packets from sink to 
source using routing nodes. 2. replicated rendezvous node, which have the 
forwarding information for all source nodes. 3. interceptor node, which 
intercept a query and forward it to appropriate rendezvous node.
We argue that since both schemes use GPSR system, the cost of a 
routing node failure is same. Further, cost of interceptor node failure is
negligible since it is a stateless node meant for local routing of
packets to corresponding rendezvous node. We calculate the cost of a 
replicated rendezvous node failure next for both schemes.
Let $r_{t}$ be the rate of querying for target $e/t$ and $s_{r}$ be the size of
query message. Then over time $e/T$ number of queries generated
\begin{equation}
                \sum queries = $r_{t}$*T*$s_{r}$
\end{equation}
Assuming a uniform distribution of sinks throughout the sensing space,
\begin{equation}
Load on a single rendezvous node = \sum queries/$n_{t}$
                                 = $r_{t}$*T*$s_{r}$/$n_{t}$
\end{equation}
where $n_{t}$ be the number of replicated rendezvous nodes for target $e/t$.
In ARI the failure of a rendezvous node causes packets destined to the
failed node to be diverted to the next clockwise neighbor of the failed node.
Again assuming uniform sink distribution,
\begin{equation}
Load on next clockwise neighbor = $r_{t}$*T*$s_{r}$*2/$n_{t}$
Load on other rendezvous nodes  = $r_{t}$*T*$s_{r}$*$n_{t}$ - 2}/$n_{t}$
\end{equation}

As against ARI EASM divides the load evenly when failure occurs making
it more robust to failures.

2. Response messages. EASM has a mechanism similar for response messages 
delivery to sinks. Note that ARI can not handle sink movements beyond
their own grid, here we establish an upper bound on the number of responses 
lost in ARI owing to such sink movement. 
Consider a sensing square area A with $e/r$ units on a side. Let the nominal
radio range be R. Thus we have \begin{equation} m = A/r^2} \end{equation} 
grids and \frac{n}{m} sinks per grid,
where $e/n$ is the total number of sinks. Assume uniform distribution of sinks
in the sensing space. Let $e/P$ be the probability that a sink moves out
of its grid after making a query, i.e. before $e/RTT$ has elapsed.
\begin{equation}
Probability that $e/x$ sinks move = P^x*(1-P)^(\frac {n}{m}-x)
Aggregate response messages lost = P^x*(1-P)^(frac {n}{m}-x)*t/RTT
\end equation}

