%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\input{dir}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\typeout{======================================================================}
\typeout{tex    directory is : \texdir}
\typeout{figure directory is : \figdir}
\typeout{======================================================================}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,twoside]{article}

\def\iotabsize{\scriptsize}       % iotab fontsize
\def\resetcounterwithin{section}  % resetting env counters
\input{\texdir macros}
\input{\texdir thesisiocode}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% SETTING THE PAGE LAYOUT

\setpagelayout{0.5in}{1.0in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% COMMANDS TO HELP WITH DRAFT 

% these help to typeset lines including long math hboxes...
\global\tolerance 1000
\global\pretolerance 500
\global\emergencystretch = .15\hsize
%\setlength{\emergencystretch}{5em}

%\def\writeupdraft{}
\ifx\writeupdraft\undefined\else
\typeout{*****************************************************************************}
\typeout{******************************** DRAFT STYLE ********************************}
\typeout{*****************************************************************************}

% Use myheadings pagestyle
\pagestyle{myheadings}

% From siamltex.cls
% generates a rule of width \overfullrule at end of lines that are too
% long... set to 0pt for no such rules or omit...
\setlength\overfullrule{5pt}

% Redefine the reflist command to introduce gray shading in references
\makeatletter
\def\reflist#1#2{%
  \colorbox[gray]{0.9}{%
    \listcount = 0%
    \tmpcount  = 0%
    \xdef\no@sp@reflist{\@ignsp#2 \! }%
    \@for \reflistitem:=\no@sp@reflist\do {\advance\listcount by 1}%
    \ifx#1\empty\else\ifnum\listcount>1 #1s~\else #1~\fi\fi%
    \@for \reflistitem:=\no@sp@reflist\do {%
      \advance\tmpcount by 1\relax%
      \ifnum\tmpcount<\listcount%
      {\ref{\reflistitem}\ifnum\listcount>2{,}\fi{ }}%
      \else%
      {\ifnum\listcount>1{and~}\fi\ref{\reflistitem}}%
      \fi%
    }%
  }% this corresponds to the gray box
}
\makeatother

% remove the change bars... they seem to be generating invalid postscript...
\renewcommand{\cbstart}{}
\renewcommand{\cbend}{}

% show the labels of the various environments...
\usepackage[inline]{showlabels}

\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\includeproofs}[1]{#1}

% use the multicolumn environment
\usepackage{multicol}
% removing the extra vertical spacing before/after multicol environments
\multicolsep = 0pt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setlength{\floatsep}{0.5\baselineskip}
\setlength{\textfloatsep}{\floatsep}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\titletext{A Reliable Broadcast Scheme for Sensor Networks}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\includepaperref{}
\ifx\includepaperref\undefined\else
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Box including the reference...
\newsavebox{\paperref}
\savebox{\paperref}{\fbox{%
    \begin{minipage}{0.5\linewidth}
      \scriptsize
      {\sc Livadas, C. and Lynch, N.~A.}
      \newblock {\titletext}.
      \newblock {Technical Report} {MIT/CSAIL/TR-915}, {Computer Science
      and Artificial Intelligence Lab., MIT}, {Cambridge, MA}, Aug. 2003.
    \end{minipage}%
  }%
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Redefining the pagestyle 'myheadings'
\makeatletter%
\def\ps@myheadings{\let\@mkboth\markboth%
    \def\@oddfoot{\hfil \thepage \hfil}%
    \def\@evenfoot{\hfil \thepage \hfil}%
    \def\@evenhead{\usebox{\draft} \hfil}%
    \def\@oddhead{\hfil \usebox{\paperref}}%
}%                                              
\makeatother%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\fi

\begin{document}

\title{\titletext}
\author{Carolos Livadas \hspace{5ex} Nancy A. Lynch \\
Computer Science and Artificial Intelligence Laboratory\\
\MIT}
\date{August 11, 2003\\%
  Revised April 10, 2006\\%
  Revised February 5, 2007}

\maketitle
\ifx\writeupdraft\undefined\else
\thispagestyle{myheadings}
\fi
\ifx\includepaperref\undefined\else
\thispagestyle{myheadings}
\fi

\begin{abstract}
  In this short technical report, we present a simple yet effective
  reliable broadcast protocol for sensor networks.  This protocol
  disseminates packets throughout the sensor network by flooding and
  recovers from losses resulting from collisions by having hosts retransmit
  packets whenever they notice that their neighbors have fallen behind.
  Such retransmissions serve to flood the appropriate packets throughout
  the regions of the sensor network that did not receive the given packets
  as a result of prior flooding attempts.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Overview}
\label{sec:overview}

In this short technical report, we present a simple reliable broadcast
scheme for sensor networks~\cite{BarYehudaGI92, KushilevitzM03,
  LiuM03, KowalskiP04, LevisPCS04}.  We presume that the sensor
network consists of a set of hosts that are scattered in space and are
stationary.  Moreover, we presume that the hosts are capable of
communicating wirelessly with their neighbors (within a certain
radius) and that the hosts and their wireless connections form a
connected graph.  For simplicity, we presume that there is only one
transmission source $s$ and that our broadcasting scheme is used to
broadcast a sequence of packets from $s$ to all other hosts.

Our reliable broadcasting scheme consists of two mechanisms: packets
are disseminated throughout the sensor network by flooding and losses
are recovered by having hosts retransmit packets whenever they notice
that their neighbors have fallen behind.  The first mechanism floods a
packet $p$ to all the hosts reachable from $s$ by having each host
retransmit $p$ whenever it first receives it.  Since the wireless
connectivity of all hosts forms a connected graph, when no losses
occur $p$ is flooded to all hosts in the sensor network.

The second mechanism is responsible for recovering from losses
resulting from the collision (overlap) of the wireless transmissions
of neighboring hosts.  Each host $h$ periodically transmits its
\emph{frontier} sequence number; that is, the sequence number of the
most recent packet $p$ sent by $s$ such that $h$ has received all
packets up to and including $p$.  Upon receiving this information, if
a neighbor $h'$ of $h$ has a larger frontier sequence number than the
frontier sequence number advertised by $h$, then $h'$ transmits all
the packets that it has received and whose sequence numbers are
greater than the frontier sequence number advertised by $h$.  Thus,
the given packets are forwarded to $h$ and, subsequently, flooded to
the region of the graph of hosts that have, potentially, not received
the given packets.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Formal Model}
\label{sec:formalmodel}

We abstractly model the physical system involving a set of hosts that
communicate wirelessly with their neighbors as the interaction of a set of
host automata (one for each host) and a single environment automaton that
encapsulates the behavior of the hosts' environment.  We let $H$ denote the
set of all hosts in the sensor network and $P$ denote the set of all
packets that could ever be broadcast by any of the hosts.
\reffig{fig:defs} presents the operations supported by the packets in $P$.

We model each host $h \in H$ by the automaton $\aut{host}_h$, the
environment by the automaton $\aut{env}$, and the complete sensor network
as the composition $\aut{env} \times \prod_{h \in H} \aut{host}_h$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}
  \begin{iotab}
    $P = $ Set of packets such that for all $p \in P$: \+\\ 
    $\ms{type}(p) \in \set{\val{DATA}, \val{UPDT}}$ \\
    \ioif $\ms{type}(p) = \val{DATA}$ \iothen \\
      \> $\ms{source}(p) \in H$ \\
      \> $\ms{seqno}(p) \in \setN$ \\
      \> $\ms{data}(p) \in \set{0, 1}^*$ 
    \ioend \\
    \ioif $\ms{type}(p) = \val{UPDT}$ \iothen \\
      \> $\ms{source}(p) \in H$ \\
      \> $\ms{frontier}(p) \in \setN$
    \ioend
  \end{iotab}  
  \caption{Definition of Packet Operations}
  \label{fig:defs}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{The $\aut{host}_h$ Automaton}

\reffig{fig:host-sig, fig:host-aut} specify the signature, the variables,
and the discrete transitions of the $\aut{host}_h$ automaton.  The
parameter $h \in H$ identifies the host whose behavior the automaton
$\aut{host}_h$ models.  In order to provide the appropriate context, the
description of the parameters $\param{SOURCE}$ and $\param{UPDT-PERIOD}$ is
deferred to appropriate places within the description of its variables and
actions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\begin{iotab}
  \headerbox{\textbf{Parameters:}} \+\\
  $h \in H, \param{SOURCE} \in H, \param{UPDT-PERIOD} \in \posR$ 
  \-\\
  \headerbox{\textbf{Actions:}}
\end{iotab}\\
\begin{multicols}{2}
  \begin{iotab}
    \ioin \+\\
    $\act{brecv}_h(p)$, for $p \in P$
  \end{iotab}

  \begin{iotab}
    \ioout \+\\
    $\act{bsend}_h(p)$, for $p \in P$ \\
  \end{iotab}

  \begin{iotab}
    \ioint \+\\
    $\act{bcast}_h$ \\
    $\act{updt}_h$
  \end{iotab}

  \begin{iotab}
    \iotime \+\\
    $\nu(t)$, for $t \in \nnR$ 
  \end{iotab}
\end{multicols}
  \caption{The $\aut{host}_h$ Automaton~---~Signature}
  \label{fig:host-sig}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The variable $\ms{now} \in \nnR$ denotes the time that has elapsed since
the beginning of an execution of $\aut{host}_h$.  The variable
$\ms{received}$ is the set of packets that the host $h$ has received.  The
variable $\ms{bqueue}$ is the set of packets whose transmission is pending
at the host $h$.  The variable $\ms{updt-time}$ is the time at which the
next update packet of host $h$ is scheduled for transmission.  The variable
$\ms{seqno}$ is the sequence number of the next packet to be broadcast by
the host $h$.  The derived variable $\ms{frontier}$ is the frontier
sequence number of the host $h$.

The input action $\act{brecv}_h(p)$ models the reception of a packet $p$ by
the host $h$.  If $p$ is a $\param{DATA}$ packet that the host $h$ has not
yet received, then the $\act{brecv}_h(p)$ action archives $p$ and adds it
to the broadcast queue $\ms{bqueue}$ so that it may subsequently be
forwarded to the neighbors of $h$.  Notice that $p$ is forwarded by $h$
only if $h$ has not previously received it.  If $p$ is an $\param{UPDT}$
packet and the frontier sequence number of $h$ is greater than the frontier
sequence number advertised by $p$, then $\act{brecv}_h(p)$ adds to the
broadcast queue $\ms{bqueue}$ all the packets that it has received whose
sequence number is greater than the frontier sequence number advertised by
$p$.

The internal action $\act{updt}_h$ models the scheduling of the
transmission of an update packet that announces $h$'s current frontier
sequence number to its neighbors.  The $\act{updt}_h$ action is enabled
when the current time $\ms{now}$ is equal to the update packet transmission
deadline $\ms{updt-time}$.  The $\act{updt}_h$ action composes the update
packet from the current state of the automaton $\aut{host}_h$, adds it to
the broadcast queue $\ms{bqueue}$, and resets the update packet
transmission deadline $\ms{updt-time}$ to $\param{UPDT-PERIOD}$ time units
in the future.  The operation $\ms{comp-updt-pkt}()$ returns an update
packet that is consistent with the current state of $\aut{host}_h$.

The internal action $\act{bcast}_h$ models the generation of a new packet
to be transmitted by the source of the transmission.  The $\act{bcast}_h$
action is enabled when the host $h$ is the transmission source
$\param{SOURCE}$.  Its effects are to compose a data packet, to add it to
the broadcast queue $\ms{bqueue}$, and to increment the sequence number
$\ms{seqno}$ of the next packet to be transmitted.  The operation
$\ms{comp-data-pkt}()$ returns the next data packet in the sequence of data
packets to be transmitted by $h$; that is, a data packet whose sequence
number is equal to $\ms{seqno}$.

The output action $\act{bsend}_h(p)$ models the transmission of the packet
$p$ by the host $h$.  This action is enabled when the packet $p$ is in the
broadcast queue $\ms{bqueue}$.  Its effects are to remove $p$ from the
broadcast queue $\ms{bqueue}$.

The time-passage action $\nu(t)$ models the passage of $t$ time units.  The
$\nu(t)$ action is enabled when $h$'s deadline for transmitting an update
packet does not precede the point in time $\ms{now} + t$.  Its effects are
to increment the variable $\ms{now}$ by $t$ time units.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\begin{iotab}
\headerbox{\textbf{Variables:}}  \+\\
$\ms{now} \in \nnR$, initially $\ms{now} = 0$ \\
$\ms{received} \subseteq P$, initially $\ms{received} = \emptyset$ \\
$\ms{bqueue} \subseteq P$, initially $\ms{bqueue} = \emptyset$ \\
$\ms{updt-time} \in \nnr$, initially $\ms{updt-time} \in [0, \param{UPDT-PERIOD}]$ \\
$\ms{seqno} \in \setN$, initially $\ms{seqno} = 0$
\-\\
\headerbox{\textbf{Derived Variables:}} \+\\
$\ms{frontier} = \max(\set{i \in \setN \st \exists p \in \ms{received},
  \ms{seqno}(p) = i \And \forall i' \setN, i' < i, \exists p' \in
  \ms{received}, \ms{seqno}(p') = i'})$
\-\\
\headerbox{\textbf{Discrete Transitions:}}
\end{iotab}%
\begin{multicols}{2}
  \prcef{\ioout $\act{bsend}_h(p)$}
  { % Precondition:
    $p \in \ms{bqueue}$
  }%
  { % Effect:
    $\ms{bqueue} \minusassign \set{p}$
  }%

  \prcef{\ioint $\act{updt}_h$}
  { % Precondition:
    $\ms{now} = \ms{updt-time}$
  }%
  { % Effect:
    $\ms{bqueue} \unionassign \set{\ms{comp-updt-pkt}()}$ \\
    $\ms{updt-time} := \ms{now} + \param{UPDT-PERIOD}$ 
  }%

  \prcef{\ioint $\act{bcast}_h$}
  { % Precondition:
    $h = \param{SOURCE}$
  }%
  { % Effect:
    $\ms{bqueue} \unionassign \set{\ms{comp-data-pkt}()}$ \\
    $\ms{seqno} := \ms{seqno} + 1$
  }%

  \ef[{\iowhere $\ms{type}(p) = \val{DATA}$}]{\ioin $\act{brecv}_h(p)$}
  { % Effect
    \ioif $p \not\in \ms{received}$ \iothen \\
    $\ms{bqueue} \unionassign \set{p}$ \\
    $\ms{received} \unionassign \set{p}$ 
    \ioend%
  }%
  
  \ef[{\iowhere $\ms{type}(p) = \val{UPDT}$}]{\ioin $\act{brecv}_h(p)$}
  { % Effect
    \ioif $\ms{frontier}(p) < \ms{frontier}$ \iothen \\
      \ioforeach $p' \in \ms{received} : \ms{frontier}(p) < \ms{seqno}(p')$ \iodo\\
        $\ms{bqueue} \unionassign \set{p'}$
    \ioend%
  }%
  
  \prcef{\iotime $\nu(t)$}
  { % Precondition
    $\ms{now} + t \leq \ms{updt-time} \And \ms{bqueue} = \emptyset$
  }%
  { % Effect
    $\ms{now} := \ms{now} + t$
  }%
\end{multicols}
\caption{The $\aut{host}_h$ Automaton~---~Variables and Discrete Transitions}
\label{fig:host-aut}
\end{figure}

\subsection{The $\aut{env}$ Automaton}

\reffig{fig:env-sig, fig:env-aut} specify the signature, the
variables, and the discrete transitions of the $\aut{env}$ automaton.
This automaton models the environment of the sensor network.  The
$\aut{env}$ automaton also maintains the sensor network topology.
This topology is presumed to be fixed.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{iotab}
  \headerbox{\textbf{Actions:}}
\end{iotab}
\begin{multicols}{2}
  \begin{iotab}
    \ioin \+\\
    $\act{bsend}_h(p)$, for $h \in H$, $p \in P$
  \end{iotab}

  \begin{iotab}
    \ioout \+\\
    $\act{brecv}_h(p)$, for $h \in H$, $p \in P$ \\
    $\act{bdrop}_h(p)$, for $h \in H$, $p \in P$
  \end{iotab}

  \begin{iotab}
    \iotime \+\\
    $\nu(t)$, for $t \in \nnR$ 
  \end{iotab}
\end{multicols}
  \caption{The $\aut{env}$ Automaton~---~Signature}
  \label{fig:env-sig}
\end{figure}

The variable $\ms{now} \in \nnR$ denotes the time that has elapsed since
the beginning of an execution of $\aut{env}$.  The variables
$\ms{dqueue}(h)$, for $h \in H$, are the delivery queues for each host $h$;
that is, for any packet $p \in \ms{dqueue}(h)$, it is the case that the
delivery of $p$ to $h$ is pending.  Each set $\ms{neighbors}(h)$, for $h
\in H$, indicates the neighboring hosts of $h$ in the sensor network; that
is, the set of hosts that are reachable through $h$'s wireless
transmissions.  The sets $\ms{neighbors}(h)$, for $h \in H$, dictate the
topology of the sensor network.

The input action $\act{bsend}_h(p)$, which models the wireless transmission
of the packet $p$ by $h$, adds the packet $p$ to the delivery queues of all
the neighbors of $h$.  Thus, we model the omni-directional wireless
transmission of $p$ by $h$ as a parallel point-to-point transmission from
$h$ to all of its neighbors.

The output action $\act{brecv}_h(p)$ models the delivery of the packet $p$
to $h$.  The $\act{brecv}_h(p)$ is enabled when $p$ is in the delivery
queue $\ms{dqueue}(h)$ of $h$.  Its effects are to remove $p$ from the
delivery queue $\ms{dqueue}(h)$ of $h$.

The output action $\act{bdrop}_h(p)$ models the loss of the packet $p$
while being delivered to $h$.  By modeling the omni-directional wireless
transmission of packets as multiple point-to-point transmissions, we
consider the transmission failure to any single neighbor as a distinct
loss.  We presume that losses are due solely to collisions, \ie when
neighboring hosts attempt to transmit concurrently.  More complicated
models of the system and its behavior may model power failures, crashes,
and, potentially, sensor/host mobility.

The time-passage action $\nu(t)$ models the passage of $t$ time units.  The
$\nu(t)$ action is enabled at any point in time and its effects are to
increment the variable $\ms{now}$ by $t$ time units.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\begin{iotab}
\headerbox{\textbf{Variables:}}  \+\\
$\ms{now} \in \nnR$, initially $\ms{now} = 0$ \\
$\ms{dqueue}(h) \subseteq P$, for $h \in H$, 
  initially $\ms{dqueue}(h) = \emptyset$, for all $h \in H$ \\
$\ms{neighbors}(h) \subseteq H$, for $h \in H$, 
  initially $\ms{neighbors}(h) \subseteq H$, for all $h \in H$, \\
  \>such that $H$ and $\ms{neighbors}(h)$, for $h \in H$, form a connected
  graph  
\-\\
\headerbox{\textbf{Discrete Transitions:}}
\end{iotab}%
\begin{multicols}{2}
  \ef{\ioin $\act{bsend}_h(p)$}
  { % Effect
    \ioforeach $h' \in \ms{neighbors}(h)$ \iodo\\
      $\ms{dqueue}(h') \unionassign \set{p}$
    \ioend%
  }%

  \prcef{\ioout $\act{brecv}_h(p)$}
  { % Precondition:
    $p \in \ms{dqueue}(h)$
  }%
  { % Effect:
    $\ms{dqueue}(h) \minusassign \set{p}$
  }%

  \prcef{\ioout $\act{bdrop}_h(p)$}
  { % Precondition:
    $p \in \ms{dqueue}(h)$
  }%
  { % Effect:
    $\ms{dqueue}(h) \minusassign \set{p}$
  }%

  \prcef{\iotime $\nu(t)$}
  { % Precondition
    None.
  }%
  { % Effect
    $\ms{now} := \ms{now} + t$
  }%
\end{multicols}
\caption{The $\aut{env}$ Automaton~---~Variables and Discrete Transitions}
\label{fig:env-aut}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Informal Performance Analysis}
\label{sec:performance}

In this section, we informally analyze the performance of our reliable
broadcast scheme for sensor networks.  Let $D$ denote the diameter of the
sensor network in terms of hop-counts; that is, any sensor is at most $D$
hops away from any other sensor in the network.  Moreover, let $\obar{d}$
be an upper bound on the amount of time it takes for a host to wirelessly
transmit a packet.  Finally, let $f \in \setN$ be a bound on the total
number of losses suffered during any particular execution of the system.

Now, consider the effect that a packet drop has on the dissemination of a
packet throughout the sensor network.  Let $h$ and $h'$ be any two
neighbors in the sensor network and suppose that $h'$ is reachable from the
transmission source $s$ only through $h'$.  Now, consider the scenario in
which a data packet $p$ is dropped while being transmitted from $h$ to
$h'$.  Since $h$ may only transmit a packet a second time as a response to
an update packet, $h'$ may only recover the packet after successfully
transmitting an update packet that instigates the retransmission of $p$ by
$h$.

First, consider the case where this update packet indeed instigates the
retransmission of $p$ by $h$.  In such a case, the additional delay in
forwarding $p$ that is incurred by the loss of the original transmission of
$p$ from $h$ to $h'$ is equal to $\param{UPDT-PERIOD} + \obar{d}$; this
corresponds to the latest point in time that $h$ may receive the next
update packet of $h'$.  Once this update packet is received, $h$
retransmits $p$ and, presuming no additional packets are dropped, $p$ is
subsequently flooded throughout the region of the sensor network reachable
through $h'$.  The dissemination of $p$ from $h$ to $h'$ may further be
delayed either if the update packet from $h'$ to $h$ or the retransmission
of $p$ from $h$ to $h'$ is dropped.  Each such drop would delay the
dissemination of $p$ from $h$ to $h'$ by $\param{UPDT-PERIOD}$ additional
time units.  It follows that each packet drop may delay a packet's recovery
by at most $\param{UPDT-PERIOD} + \obar{d}$ time units.

In our example of the packet $p$ being dropped while being transmitted from
$h$ to $h'$, it is possible for an update packet from $h'$ not to instigate
the retransmission of $p$ by $h$.  This may occur when both $h$ and $h'$
share the loss of a packet $p'$ that was transmitted by $s$ earlier than
$p$.  In such a case, the recovery of $p$ may rely on the recovery of $p'$,
which may itself be delayed due to packet losses.  Once $p'$ is recovered
however, the recovery of $p$ proceeds as described above.  In fact, a
cascade of packet recoveries may need to be carried out before $p$ may be
recovered.  Once again, however, each such recovery is delayed by at most
$\param{UPDT-PERIOD} + \obar{d}$ per loss.

Presuming that the sensor network suffers at most $f \in \setN$ packet
losses, the worst-case delay incurred during the recovery of $p$ would be
$f (\param{UPDT-PERIOD} + \obar{d})$.  Thus, the worst-case delay in
broadcasting $p$ would be $D \obar{d} + f (\param{UPDT-PERIOD} +
\obar{d})$, where $D \obar{d}$ is the worst-case propagation delay of $p$
throughout the sensor network and $f (\param{UPDT-PERIOD} + \obar{d})$ is
the delay incurred due to the $f$ possible losses.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Discussion and Conclusions}
\label{sec:discussion}

The reliable broadcast scheme presented in this report is a very simple yet
effective scheme that guarantees the delivery of packets from a single
source to the other hosts in a sensor network.  Our scheme is particularly
effective for low bandwidth sensor network transmissions, which is the type
of application for which it was designed.

Although simple and effective, our reliable broadcast scheme has some
limitations.  The hosts are required to archive all the packets they
receive.  This may not be feasible in an actual sensor network.  Moreover,
the straightforward extension to the case where there are multiple sources
the size of the update packets is proportional to the number of sources.
This may make the transmission of update packets prohibitively expensive
and fault-prone.  Finally, the protocol may not be well suited to high
bandwidth transmissions.  The combination of high bandwidth transmissions
and the fact that wireless communication is highly lossy may induce
frequent frontier sequence number discrepancies and result in frequent
retransmission bursts.  These are limitations that are worth thinking about
and resolving.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Acknowledgments

\section*{Acknowledgments}

We would like to thank Deborah Estrin and David Cuttler for suggesting
the problem of reliable broadcast for sensor networks.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% References

% theoretical refs 
%\nocite{KushilevitzM03,KowalskiP04,BarYehudaGI92}
% applied refs
%\nocite{}
% miscellaneous refs
%\nocite{Estrin03}

%\begin{small}
%\bibliography{paper}
%\bibliography{\texdir refs}
%\bibliographystyle{splncs} 
%\bibliographystyle{ieee}
\bibliographystyle{acm}
\bibliography{\bibdir tr915}

%\end{small}

\end{document}

\endinput
