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

%
\subsection{EASM Architecture and Protocol Interactions}
\label{sec:easm_arch}

Figure~\ref{fig:easm_arch} illustrates the architecture of the sensing
space and the application of the EASM protocol for data
dissemination. EASM divides the sensing space into a virtual grid.
This is done to identify the {\em grid center} location for a sink 
originating a data request. Grid center is the center of the cell from
which sink makes a request, as shown in Figure~\ref{fig:easm_arch}.
Grid center location is used in {\em directed response} which is
explained in the Data Response section later.

\begin{enumerate}
  \item {\bf Grid} -- is the entire sensor network, which we assume to
  have been partitioned into a grid.
  \item {\bf Sink node} -- is a node, which may be mobile,
  that is interested in receiving notifications of particular event
  types it is interested in.
  \item {\bf Source node} -- is a node, which we assume to be
  stationary, that senses the phenomenon of interest and is capable of
  storing the sensed data, which ultimately must be disseminated to
  sink nodes interested in the data.  We also assume that the source
  node has aggregate data for a given event type.  Thus, we do not
  address the issue of data aggregation in this paper.
  \item {\bf Rendezvous node} -- is a node, also assumed to be
  stationary, that acts a mediator responsible for relaying the event
  subscription by the sink to the source.
  \item {\bf Interceptor node} -- is a node, which is stationary, in
  the vicinity of the rendezvous node.  Interceptors are used to
  improve the fault tolerance and scalability of the EASM protocol as
  described in Section~\ref{sec:ft}.
  \item {\bf Forwarder node} -- is a node, which is stationary, and
  has been elected as a forwarder to relay information between source
  and sink nodes.
  \item {\bf Home cell} -- Virtual grid divides sensing space into
  cells, home cell for a sink is the cell from which it originated
  a request.
  \item {\bf Grid/cell center node} -- is a centrally located sensor
  node in each cell area to which a sink node belongs. Source nodes
  use these grid centers as the destination to directly route data
  information. Grid centers subsequently relay this information to the
  sink node.
\end{enumerate}

\begin{figure*}[hbt]
\begin{center}
\includegraphics[width=5.3in]{eps/easm_arch.eps}
\bfcaption{EASM Architecture}
\label{fig:easm_arch}
\end{center}
\end{figure*}

Rendezvous point in EASM denotes a point or a location within 
sensing space.  Thus, each event type has a corresponding location in
the sensing space called the rendezvous 
point.  Note that rendezvous point receives the sink requests and
forwards them to the source node.  A node at the rendezvous point
called rendezvous node is used for carrying out the above 
functionality.  Often times a node may not be present at the exact
location.  However, since GPSR delivers a packet to a node 
geographically closest to the destination location~\cite{GPSR:00}
(if a node is not present at the destination location) we may
use a node which is geographically closest to the rendezvous
point.  For the rest of the paper, we use the terms rendezvous point
and rendezvous node interchangeably.  Similarly, a grid center is a
location as well as a node responsible for delivering response to the
respective sinks.

For every event type that a sink node is interested in, EASM uses a
hash function for determining a rendezvous point.  Use of hash table
for data location has been successfully demonstrated in Geographic
Hash Table (GHT)~\cite{GHT:02}, Ring-Based Index~\cite{RB:03} and
peer-to-peer systems~\cite{Druschel:01}.

In EASM, when an event to be tracked is first
detected by a sensor node in the geographical terrain, the node elects
itself as the source node for that event.  If the initial sensing node
does not have sufficient residual energy, it may elect a neighbor as
the source node.  This is essential since the source has to respond to
data requests from, possibly several, sink nodes.  The source node
registers its location information with its rendezvous point.  The
source node thus acts as the {\em end-point} for all queries for the
event it is sensing. 

Once the event discovery and source node registration with the
rendezvous point is done, the sink nodes interested in an event can
send queries towards the rendezvous point location.  The rendezvous
point, which acts as the mediator, forwards the data queries to
appropriate source nodes.  On receving data queries, the source node
sends the data response directly toward the sink node querying for data. 

We use Greedy Perimeter Stateless Routing (GPSR)~\cite{GPSR:00} as the
underlying routing protocol for our scheme.  GPSR essentially consists
of two basic methods for forwarding packets: (a) Greedy Forwarding,
where each forwarding node greedily sends a packet to that neighbor,
which is closest to the final destination.  Thus with each hop the
packet moves successively closer to destination node, and (b)
Perimeter Forwarding, which is used when greedy forwarding fails i.e.,
when the current forwarding node does not have a neighbor closer to
the destination than itself~\cite{GPSR:00}.  In this case, the packet
is forwarded using {\em right-hand rule} to its neighbor (which in
this case is farther from the destination than itself).  The same
forwarding scheme is followed till a node can again forward packets
using greedy forwarding. 

{\em Locations} of rendezvous points, which are geographic cartesian
coordinates, are used to send packets.  This eliminates the need for
network-level broadcast for propogation of interest (data request) and
availability (data response).  Further source nodes respond to data
queries using a {\em directed response} approach to ensure that sinks
receive a response even if they have moved from their query location.
We explain the EASM approach in detail in the remainder of this
section. 

\paragraph*{\bf Data Requests} We assume that the rendezvous points are 
populated with source node location information before any sink
makes a data request in the sensor network.  In EASM a sink fills in a
{\em grid center} field in all the requests it sends, which is the
center of the cell from where the request originates.  The sensing space can be 
assumed to be divided into cells as shown in Figure 1, where
the dimension of the cell is a configuration parameter.  The grid
center is an indication of the query location and is used as a hint
when source node responds to the query.  Depending on the event type,
a data request is routed to appropriate rendezvous points.

\paragraph*{\bf Data Response} Sinks are mobile and may move after making a 
request, thus sink location can not be used to send data response.
EASM uses grid center field contained in the query as a hint to the 
query location to generate a response to the query. We call this 
approach {\em directed response}, since the response is sent in the 
direction of the cell from where sink originated request as shown 
in Figure~\ref{fig:easm_arch}. 

In EASM the responsibility of eventually delivering a data response
to sink nodes is delegated to grid centers.  Grid center works similar
to rendezvous nodes in that it is aware of the instantaneous location
of sink nodes.  Thus on receiving a data response it can be routed by the
grid center to appropriate sink.

\paragraph*{\bf Data Delivery} A sink node is given an expected {\em
turn-around} time for every data query it generates, after which it
polls its grid center for data availability.  The polling message is
used by sink node to indicate its instantaneous location to grid
center for data delivery.  Alternately, it may send a location update
message each time it moves.  Initially all the data responses are
stored locally with the grid center since the instantaneous sink
location may not be known.  On receiving a polling message from a
sink, grid center sends the response to sink if the data is available
locally.  Here we assume that sink node does not update its one hop
neighbors after it sends a poll message to its grid center such that
data packets are delivered to sink nodes sucessfully. 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "sensys05"
%%% End: 
