%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  New template code for TAMU Theses and Dissertations starting Fall 2012.  
%  For more info about this template or the 
%  TAMU LaTeX User's Group, see http://www.howdy.me/.
%
%  Author: Wendy Lynn Turner 
%	 Version 1.0 
%  Last updated 8/5/2012
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                           SECTION III
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\chapter{\uppercase {Neighbor Knowledge of Mobile Nodes in a Road Network}}
\label{chap:nk}

In this section, we provide a solution for nodes to maintain neighbor knowledge where nodes communicate via wireless broadcast and are restricted to move on a two-dimensional road network; a road network is roughly a collection of lines that may intersect each other (see Section \ref{sec:nk:sysmodel} for details). We can view vehicular ad hoc networks as nodes (vehicles) with wireless communication capabilities moving on a road network.  Our solution is an extension of the one-dimensional case in \cite{ESW06} and \cite{S06} to two-dimensional space. \blfootnote{Part of this section is reprinted from the following paper:  \copyright 2012 IEEE. Reprinted, with permission, from Hyun Chul Chung, Saira Viqar, and Jennifer L. Welch, ``Neighbor knowledge of mobile nodes in a road network,'' In proceedings of the 32nd IEEE International Conference on Distributed Computing Systems (ICDCS), June 2012, pages 486-495.}  
 %The requirement of ``maintaining neighbor knowledge'' would be, at all times, every node knowing the identity of every other node that is within a certain distance of itself.  

Our solution provides \emph{deterministic} guarantees for maintaining neighbor knowledge.  Our algorithm divides each line of the road network into segments and utilizes time division multiplexing to avoid wireless broadcast interference and collisions.  Assuming that nodes are sufficiently close together, know their future trajectory, and have initial neighbor knowledge, certain nodes (called leader nodes) are periodically identified for each segment.  Leader nodes are the only nodes that broadcast neighbor information; restricting wireless broadcasts to be performed only by leader nodes eliminates the risk of collisions within each segment.  For a given time unit, leader nodes broadcast neighbor information (including trajectories) following a deterministic collision-free broadcast schedule.  This broadcast schedule ensures that simultaneous broadcasts performed by two different leader nodes do not interfere with each other.  All nodes update their neighbor knowledge for the next time unit based on the information received from leader nodes. Other applications may utilize the neighbor information provided by our solution to perform their own tasks.  We also provide a correctness proof for our solution.   

In addition to maintaining neighbor knowledge, we show how fast a message can travel in the network using our broadcast schedule.  We first consider message propagation on a single line and then extend the result to the road network.  Specifically, given any two points $A$ and $B$ on the road network, we provide a lower bound on the speed of a message initially broadcast at point $A$ in reaching point $B$.   

We also consider grouping nodes on the same line into clusters where a node density requirement only holds within each cluster. Under certain conditions, we show that neighbor knowledge is maintained within a cluster that is formed by merging two clusters on the same line. Furthermore, we show that neighbor knowledge is maintained within a cluster even after a single node merges into that cluster through an intersection.

Our solution relies on nodes having initial neighbor knowledge.  We address the issue of obtaining initial neighbor knowledge based on a gossiping algorithm in \cite{GPPR07}. We also discuss how to relax the assumption that every node knows its entire future trajectory and provide practical values for the parameters used in this section. 

\section{Contributions}
We present a deterministic solution for maintaining neighbor knowledge which guarantees that each node in a two dimensional road network knows its neighboring nodes at all times.  This solution can serve as a black box which provides neighbor information to other applications.

Considering the deterministic collision-free broadcast schedule presented as part of our solution in maintaining neighbor knowledge, we determine how fast a message can propagate on a two-dimensional road network by providing a lower bound on the speed of message propagation.

Finally, we consider dynamic clusters of nodes moving on a road network and show, under certain conditions, how neighbor knowledge can be maintained even when clusters merge with each other.  
\begin{comment}
\begin{itemize}
\item We present a deterministic solution for maintaining neighbor knowledge where each node in a two dimensional road network is guaranteed to know its neighboring nodes at all times.  This solution can serve as a black box which provides neighbor information to other applications.
\item Considering the deterministic collision-free broadcast schedule presented for our solution in maintaining neighbor knowledge, we have determined how fast a message can propagate on a two-dimensional road network by providing a lower bound on the speed of message propagation.
\item Finally, we have considered dynamic clusters of nodes and showed, under certain conditions, how neighbor knowledge can be maintained even when clusters merge with each other.    
\end{itemize}
\end{comment}

\section{Related Work}
\label{sec:nk:related}

Our algorithm is a generalization of the algorithm of Ellen et al. \cite{ESW06} and Subramanian \cite{S06}. Their algorithm applies to nodes that are moving along a one-dimensional line (for example vehicles moving along a single highway).  They assume that this one-dimensional line is divided into segments of equal size. These segments are in turn partitioned into a finite number of colors. Segments of the same color are spaced sufficiently apart so that nodes which occupy two different segments of the same color can transmit simultaneously without message collisions.  With the help of this coloring of segments a collision-free schedule is designed, which allows nodes to transmit messages, depending on their current location.  However, their algorithm cannot be applied to two-dimensional VANETs, with multiple adjacent lanes, or intersecting roads. A natural, and non-trivial extension of their work is to deal with the case of nodes approaching each other on intersections. We provide an algorithm for nodes moving on a road network in which lines may intersect at any angle.  In addition to this, we provide an analysis of clusters of nodes gaining knowledge of each other while merging.

In \cite{Viqar2013}, the authors consider nodes moving on a two-dimensional plane. They show how their communication schedule can provide neighborhood knowledge. They do have some discussion about how different types of schedules may help in the dissemination of information along a path of connected nodes on the plane. In their work, they do not provide a characterization of the speed of message propagation achieved by the schedule between two points on the plane. There is also no analysis of clusters of nodes merging on the plane.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In \cite{Cornejo2012}, a reliable neighbor discovery layer for mobile ad hoc networks
is defined. Two distributed algorithms are presented which implement this layer with
varying progress guarantees. However, these algorithms 
are implemented on top of a Medium Access Control (MAC) Layer
which is specified in \cite{Kuhn2011}. This MAC Layer provides upper bounds on the time 
for message delivery thereby abstracting away the lower level details of collision detection,
contention and scheduling. We adopt a more integrated approach. 
Our algorithm handles contention and message collisions
by means of a deterministic collision-free broadcast schedule.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In \cite{M09} and \cite{Mi09}, the authors show lower bounds for gossip in the case of static nodes on a one-dimensional line. Different classes of algorithms are defined: singleton algorithms in which only one node can transmit during one time-step, collision free algorithms in which multiple nodes can transmit simultaneously as long as it does not result in a message collision, and unrestricted algorithms in which no restrictions are placed on the nodes. The authors show different lower bounds for the three cases, in terms of the worst-case number of transmission slots required for all-to-all communication (or gossip).  Also, in \cite{Mi09}, a gossiping algorithm is presented for mobile ad hoc radio networks which uses the schedule defined in \cite{ESW06}. Bounds on the speed of information propagation are presented in a setting where nodes move on a one-dimensional line.  In contrast to this, we analyze the worst case time required for a message broadcast by a node $p$ located at point $A$ to reach point $B$ on a two-dimensional road network using our broadcast schedule.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%In \cite{Mi09}, a gossiping algorithm is presented for mobile ad hoc radio networks which uses the schedule defined in \cite{ESW06}.
%Bounds are presented on the speed of information propagation through the network. However, this algorithm only deals with 
%nodes moving on a one-dimensional line.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{System Model}
\label{sec:nk:sysmodel}

\begin{figure}[ht]
\centering
\includegraphics[scale=0.5]{figures/gridtype.pdf}
\caption{A road network.  Notice that the angle between two intersecting lines need not be a right angle.}
\label{fig:nk:gridtype}
\end{figure}

We define a \emph{road} network as a collection of one-dimensional lines that may intersect each other where, for any two lines, there is no restriction on the intersecting angle; see Figure \ref{fig:nk:gridtype}. We consider a fixed road network in two-dimensional Euclidean space where nodes move along the lines of the road network with a speed of at most $\sigma$. We assume that nodes have unique ids and do not crash.

Nodes communicate via wireless broadcast.  We consider a common communication radius $R$ and a common interference radius $R'$ ($\geq R$): node $p$ correctly receives node $q$'s broadcast message if (1) $q$ was within distance $R$ of $p$ during the entire broadcast, and (2) there was no other node broadcasting a message within distance $R'$ of $p$ at any time while $q$ was broadcasting its message.  

Each one-dimensional line on the road network is divided into segments of size $G$. The segmentation of each individual line is independent from each other; there are no restrictions such as intersection points should correspond to segment boundaries, etc.  Consecutive segments on a line are numbered in increasing order and colored with $m$ colors $0,1,...,m-1$: segment $s$ has a color of $s \mbox{ mod } m$.

Nodes have synchronized clocks which allows nodes to utilize time division multiplexing.  Time is divided into \emph{rounds} where each round is further divided into $u$ unit length \emph{time slots}.  Broadcasts occur at the beginning of a time slot and the duration of a time slot is long enough for a node to broadcast a message by the end of the time slot.  Similar to segments on a line, consecutive rounds are numbered in increasing order and colored with $m$ colors $0,1,...,m-1$: round $r$ has a color of $r \mbox{ mod } m$.  We assume that three or more colors are used to color segments and rounds; $m \geq 3$.

We assume that nodes initially know their future trajectory; each node $p$ knows its trajectory function $f_p(t)$ where, given a time $t$, it returns the exact location of $p$ on the road network.  The trajectory function of a node may be exchanged among nodes.

Throughout Section \ref{chap:nk}, we use the term \emph{Manhattan distance} as follows: Manhattan distance from point $A$ to point $B$ on a road network as the length of the shortest path from $A$ to $B$ \emph{along} the road network.  If we just say ``distance'', then it refers to Euclidean distance.  For two points $A$ and $B$ on the road network, we denote $dist_{E}(A,B)$ and $dist_{M}(A,B)$ as the Euclidean and Manhattan distance between point $A$ and $B$ on the road network, respectively.  Also, for a given time instant and for two nodes $p$ and $q$, we denote $dist_E(p,q)$ and $dist_M(p,q)$ as the Euclidean and Manhattan distance between $p$ and $q$ on the road network, respectively.


\section{A Deterministic Broadcast Schedule}
\label{sec:nk:schedule}

Our broadcast schedule is a small modification of that presented in \cite{ESW06} and \cite{S06}.  Each $m$ consecutive rounds, starting from round $0$, makes up a \emph{phase}\footnote{In \cite{ESW06} and \cite{S06}, not all segments get a chance to broadcast in a phase since a phase consists of $m-1$ rounds.  This causes difficulties in the analysis since the case of a node not being able to broadcast in a phase has to be considered.   In our schedule, every segment broadcasts in a phase which eases the analysis.}.  Each line $\ell$ is assigned only a single time slot during each round for nodes on $\ell$ to broadcast messages. We say that two lines $\ell_1$ and $\ell_2$ are \emph{nearby} if there exists two points $x_1$ and $x_2$ on $\ell_1$ and $\ell_2$, respectively, such that the Euclidean distance between $x_1$ and $x_2$ is less than $R+R'$.  If two lines that are nearby use the same time slot in each round, then broadcasts performed on those lines may interfere with each other.  We assume that a digital map is initially provided to all nodes in the network which allows each node to know which line it is on and which time slot is assigned to that line.  We further assume that the time slot for each line on the digital map is assigned such that any two lines that are nearby use different time slots in each round.  This implies that $u$, the number of time slots per round, is sufficiently large to handle inter-line interference. 

For each phase, exactly those nodes that are in segments of color $c$ at the beginning of the phase are allowed to broadcast during a round that has a color of $c$ within that phase.  Notice that multiple nodes can be located in the same segment at the beginning of a phase and these nodes have a potential of causing broadcast interference.  To avoid interference, nodes in segment $s$ at the beginning of a phase elect a leader node which is the only node that can broadcast on behalf of segment $s$ in that phase.  Leader election at the beginning of a phase can be done by local computation under a condition that every node in a segment at the beginning of a phase know the trajectory function of one another in that segment (e.g. by selecting the node with the lowest ID in a segment as the leader).   

\begin{figure}[tp]
  \centering
  \subfloat[When $m=5$.]{\label{fig:nk:m5}\includegraphics[scale=0.7]{figures/Schedm5.pdf}}\\
  \subfloat[When $m=6$.]{\label{fig:nk:m6}\includegraphics[scale=0.7]{figures/Schedm6.pdf}}
  \caption{Broadcast schedule examples.}
  \label{fig:nk:Sched}
\end{figure}

Our broadcast schedule is illustrated in Figure \ref{fig:nk:Sched} (the figure shows two cases: when $m=5$ and when $m=6$).  Each row represents a round and each column represents a segment. A ``$<$'' (named \emph{leftward} broadcast) indicates a broadcast that is in favor of propagating a message towards segments of decreasing order, a ``$>$'' (named \emph{rightward} broadcast) indicates a broadcast that is in favor of message propagation towards segments of increasing order, and a broadcast that is favorable to both directions is indicated by ``$<>$''.  In our schedule,  (1) every segment gets a chance to broadcast in every phase, (2) the segment that performed the last broadcast in phase $\pi$ again performs the first broadcast in phase $\pi+1$, (3) the first and last broadcast of each phase are both ``$<>$'', (4) the second broadcast of phase $\pi+1$ is ``$>$'' (resp. ``$<$'') if the second last broadcast of phase $\pi$ was ``$<$'' (resp. ``$>$''), and (5) leftward and rightward broadcasts within a phase are interleaved.  Each one-dimensional line in the road network follows this schedule.  The drawback of our schedule is that there is a delay in message propagation on phase boundaries since the same segment broadcasts in two consecutive rounds.  However, as $m$ increases, phase boundary delays occur less frequently which in turn means that phase boundary delays become less influential in message propagation.

\begin{comment}
Same as in \cite{ESW06} and \cite{S06}, we consider that a leader node is elected for each (non-empty) segment at the beginning of each phase and leader nodes are the only nodes that are allowed to broadcast on behalf of their corresponding segments in each phase.  Note that leader election at the beginning of a phase can be done by local computation under a condition that every node in a segment at the beginning of a phase know the trajectory function of one another in that segment (e.g. by selecting the node with the lowest ID in a segment as the leader).   

If we plan to use only the first time slot of each round for exchanging trajectory functions, then broadcasts performed on two or more nearby\footnote{We say that two lines $\ell_1$ and $\ell_2$ are nearby if there exists two points $x_1$ and $x_2$ on $\ell_1$ and $\ell_2$, respectively, such that the Euclidean distance between $x_1$ and $x_2$ is less than $R+R'$.} lines may interfere with one another.  We assume that two lines that are nearby use different time slots in a round.  This implies that $u$, the number of time slots per round, is sufficiently large to handle inter-line interference.
\end{comment}

\section{Assumptions and Constraints on Parameters}
\label{sec:nk:constraints}

We have handled intra-segment and inter-line interference.  However, the broadcast schedule is still exposed to inter-segment interference on a line; since segments of the same color on the same line broadcast simultaneously, interference might occur if those segments are not sufficiently far apart.  To take care of inter-segment interference, we introduce the first constraint:
\begin{align}
mG-2mu\sigma \geq R+R' \label{nk:constraint1}
\end{align}  
where $mG$ corresponds to the distance between two consecutive segments of the same color and $mu\sigma$ is the maximum distance a node can move during a phase.  Constraint \ref{nk:constraint1} tells us that the broadcasts of two leader nodes, one representing segment $s$ and the other representing segment $s+m$ on the same line, do not interfere with each other even if the two nodes approach each other in maximum speed during a phase.

The following constraint tells us that we only allow nodes to cross at most one segment boundary in a phase: 
\begin{align}
mu\sigma < G \label{nk:constraint2}
\end{align}

We assume a density requirement on the network: on each line, there exists at least one node in every interval of length $L$ at all times.  We consider the following constraint on $L$:
\begin{align}
L \leq (R-3G-8mu\sigma)/2 \label{nk:constraint3}
\end{align}

We assume that the Manhattan distance between any two intersection points is greater than $L+2G+6mu\sigma$.  This assumption enforces a node in between two consecutive intersections $A$ and $B$ to remain in between $A$ and $B$ for a certain number of phases.  

We also assume that for each line on the road network, the distance between an endpoint of the line and its nearest intersection is at least $L+2G+6mu\sigma$. 

In addition, we assume that each node $p$ starts at the beginning of phase $0$ and possesses trajectory functions of other nodes within a distance of $R+2mu\sigma$ from $p$ at the beginning of phase $0$.  We say that node $p$ \emph{knows} node $q$ if $p$ possesses $q$'s trajectory function. 

\section{Maintaining Neighbor Knowledge}
\label{sec:nk:maintainNeighborKnowledge}

For simplicity, we assume that, when a leader node broadcasts, it broadcasts all trajectory functions that it knows.  This assumption may be relaxed, as in \cite{ESW06} and \cite{S06}, by making each node $p$ to only keep trajectory functions of other nodes that are nearby $p$ (if $p$ has the trajectory function of $q$, then $p$ can decide whether or not to dispose $q$'s trajectory function since $p$ can calculate its distance to $q$ at any given time).       
We now show that nodes maintain neighbor knowledge with the broadcast schedule.  More specifically, we show that each node $p$ knows every other node that is within Manhattan distance of $R$ from itself at any given time (Theorem \ref{thm:nk:maintainR}).  To do this, we first show that neighbor knowledge is maintained at the beginning of each phase:

\begin{lemma}
\label{lem:nk:maintainRmu}
For all phases $\pi$, 
\begin{itemize}
\item[(a)] if $\pi>1$, then broadcast collisions do not occur during phase $\pi-1$, and
\item[(b)] for all nodes $p$ and $q$, if $dist_M(p,q) \leq R+2mu\sigma$ at the beginning of phase $\pi$, then $p$ knows $q$ at the beginning of phase $\pi$.
\end{itemize}
\end{lemma}
\begin{proof}
We use induction on $\pi$.  For the basis ($\pi=0$), part (a) is vacuously true and part (b) follows by our initialization assumptions.

For the inductive step, we assume that the lemma holds for phase $\pi$ and we will show that it holds for phase $\pi+1$.

We first show part (a).  Since we have assumed that any two lines that are nearby use different time slots in each round, it is only required to show that collisions do not occur within a single line during phase $\pi$.   
 
The inductive hypothesis implies that for all nodes $p$ and $q$, if $dist_M(p,q) \leq G$ at the beginning of phase $\pi$, then $p$ knows $q$ at the beginning of phase $\pi$ since
\begin{align}
R+2mu\sigma &\geq 2L+3G+8mu\sigma \tag{by Constraint \ref{nk:constraint3}} \\
&>G. \nonumber
\end{align}
Thus, at the beginning of phase $\pi$, nodes in the same segment know each other and a unique leader can be elected for each non-empty segment.  Note that, by assumption, leaders are the only nodes that are allowed to broadcast on behalf of their corresponding segments.  

Due to our broadcast schedule, leaders representing different segments of the same color may broadcast simultaneously during phase $\pi$.  Also, at the beginning of phase $\pi$, the distance between any two leaders that represent different segments of the same color is at least $mG$.  Note that due to the upper bound $\sigma$ on node speed and the fact that a phase lasts $mu$ time, the maximum distance a node can travel during a phase is $mu\sigma$.  Thus, during phase $\pi$, for all pair of leader nodes $\ell_1$ and $\ell_2$ that represent different segments of the same color, we get
\begin{align}
dist_E(\ell_1, \ell_2) &\geq mG-2mu\sigma \nonumber \\
&\geq R+R' \tag{by Constraint \ref{nk:constraint1}}
\end{align}
which proves that broadcasts of $\ell_1$ and $\ell_2$ do not interfere with each other. 

Now, we show part (b).  First note that since the maximum Manhattan distance a node can travel during a phase is $mu\sigma$, for all nodes $p$ and $q$, if $dist_M(p,q) \leq R+2mu\sigma$ at the beginning of phase $\pi+1$, then $dist_M(p,q) \leq R+4mu\sigma$ at the beginning of phase $\pi$.  Thus, it is sufficient to show that, during phase $\pi$, $p$ learns about every node $q$ such that $dist_M(p,q)\leq R+4mu\sigma$ at the beginning of phase $\pi$ (if it does not already know $q$).

If $dist_M(p,q) \leq R+2mu\sigma$ at the beginning of phase $\pi$, then by the inductive hypothesis, $p$ knows $q$ at the beginning of phase $\pi$; thus $p$ knows $q$ at the beginning of phase $\pi+1$.  Now, assume that $dist_M(p,q)>R+2mu\sigma$ at the beginning of phase $\pi$.  We will show that there must exist a node $\ell$ such that 

\begin{itemize}
\item[(i)] $\ell$ is the leader of a segment during phase $\pi$,
\item[(ii)] $dist_M(p,\ell)\leq R-2mu\sigma$ at the beginning of phase $\pi$, i.e., $\ell$ is within broadcast range of $p$ throughout phase $\pi$, and
\item[(iii)] $dist_M(\ell,q)\leq R+2mu\sigma$ at the beginning of phase $\pi$, i.e., $\ell$ knows $q$ at the beginning of phase $\pi$, by the inductive hypothesis.
\end{itemize}
Thus, $p$ learns about $q$ during phase $\pi$ (if it does not already know $q$) and $p$ knows $q$ at the beginning of phase $\pi+1$.\\
--(\emph{Case} 1) The path from $p$ to $q$ (along the lines of the road network) either consists of a single line or the first line change occurs at distance at least $L/2+G+2mu\sigma$:  Consider the interval $I_{leader}$ of length $L+2G$ that resides on the same line as $p$ lies on at the beginning of phase $\pi$ where (1) one endpoint is at distance $2mu\sigma$ and the other endpoint is at distance $L+2G+2mu\sigma$ from $p$, and (2) there exists a subinterval of length at least $L/2+G$ that overlaps with the path from $p$ to $q$ (see Figures \ref{fig:nk:maintain1a} and \ref{fig:nk:maintain1b}).

\begin{itemize}
\item[(i)] By the density assumption, the subinterval of length $L$ centered inside $I_{leader}$ contains at least one node $r$.  Either $r$ or another node in the same segment as $r$ is a leader for phase $\pi$.  Since the segment length is $G$, somewhere in $I_{leader}$ there is a leader node $\ell$.
\item[(ii)] To show $dist_M(p,\ell)\leq R-2mu\sigma$ at the beginning of phase $\pi$, first note that $dist_M(p,\ell) \leq L+2G+2mu\sigma$ by the definition of $I_{leader}$.  Then,
\begin{align}
&R-2mu\sigma \nonumber \\
\geq~ &2L+3G+8mu\sigma-2mu\sigma \tag{by Constraint \ref{nk:constraint3}} \\
\geq~ &L+2G+2mu\sigma \nonumber \\
\geq~ &dist_M(p,\ell) \tag{by note above}
\end{align}

\begin{figure*}[tp]
  \centering
  \subfloat[Case 1: no line changes occur.]{\label{fig:nk:maintain1a}\includegraphics[scale=0.95]{figures/maintain1a.pdf}}\\~\\
  \subfloat[Case 1: a line change occurs.]{\label{fig:nk:maintain1b}\includegraphics[scale=0.95]{figures/maintain1b.pdf}}
  %\subfloat[Case 2.]{\label{fig:nk:maintain2}\includegraphics[width=0.20\textwidth]{figures/maintain2.jpg}}~~
  %\subfloat[Case 3.]{\label{fig:nk:maintain3}\includegraphics[width=0.15\textwidth]{figures/maintain3.jpg}}
\caption{Proof of Lemma \ref{lem:nk:maintainRmu} (Case 1).}
\label{fig:nk:maintain1}
\end{figure*}

\item[(iii)] To show $dist_M(\ell,q)\leq R+2mu\sigma$ at the beginning of phase $\pi$, we further divide into two cases depending on the location of $\ell$ with respect to the intersection where the first line change occurs:\\
---(\emph{Case} 1a) A line change does not occur from $p$ to $q$ (see Figure \ref{fig:nk:maintain1a}) or $\ell$ is on the same side of the intersection as $p$ (between point $A$ and the intersection in Figure \ref{fig:nk:maintain1b}) at the beginning of phase $\pi$:  In this case, $\ell$ is located within the path from $p$ to $q$.  Thus,
\begin{align}
&dist_M(\ell,q) \nonumber \\
=~ &dist_M(p,q) - dist_M(p,\ell) \nonumber \\
\leq~ &R+4mu\sigma - dist_M(p,\ell) \tag{by assumption} \\
\leq~ &R+4mu\sigma - 2mu\sigma \tag{by def. of $I_{leader}$} \\
=~& R+2mu\sigma \nonumber
\end{align}
---(\emph{Case} 1b) $\ell$ is on the other side of the intersection as $p$ (between point $B$ and the intersection in Figure \ref{fig:nk:maintain1b}) at the beginning of phase $\pi$:  Since at least half of $I_{leader}$ is on the same side of the intersection as $p$, we get
\begin{align}
&dist_M(\ell,q) \nonumber \\
\leq~ &dist_M(p,q) - 2mu\sigma \nonumber \\
\leq~ &R+4mu\sigma - 2mu\sigma \tag{by assumption} \\
=~ &R+2mu\sigma \nonumber
\end{align}
\end{itemize}
--(\emph{Case} 2) The distance between $p$ and the first intersection point on the path to $q$ is at least $2mu\sigma$ but less than $L/2+G+2mu\sigma$ (see Figure \ref{fig:nk:maintain2}): Consider the interval $I_{leader}$ of length $L+2G$ that resides on the intersecting line where (1) one endpoint is on the intersection point, and (2) overlaps with the path from $p$ to $q$.  Note that, since the distance between any two intersection points is at least $L+2G+6mu\sigma$, no line intersects $I_{leader}$.  The Manhattan distance between $p$ and any point in $I_{leader}$ is at most $3L/2+3G+2mu\sigma$. By Constraint \ref{nk:constraint3}, it follows that $3L/2+3G+2mu\sigma \leq R$.  Thus, $I_{leader}$ is entirely between $p$ and $q$.

\begin{figure}[tp]
  \centering
  \subfloat[Case 2.]{\label{fig:nk:maintain2}\includegraphics[scale=0.95]{figures/maintain2.pdf}}\qquad\qquad
  \subfloat[Case 3.]{\label{fig:nk:maintain3}\includegraphics[scale=0.95]{figures/maintain3.pdf}}
  \caption{Proof of Lemma \ref{lem:nk:maintainRmu} (Cases 2 and 3).}
  \label{fig:nk:maintainCase23}
\end{figure}

\begin{itemize}
\item[(i)] Same as in (Case 1), there exists a leader node $\ell$ in $I_{leader}$ at the beginning of phase $\pi$.
\item[(ii)] To show $dist_M(p,\ell)\leq R-2mu\sigma$ at the beginning of phase $\pi$, note that
\begin{align}
&dist_M(p,\ell) \nonumber \\ 
\leq~ &3L/2+3G+2mu\sigma \tag{$\ell$ is in $I_{leader}$}\\
\leq~ &R-L/2-6mu\sigma \tag{by Constraint \ref{nk:constraint3}}\\
<~ &R-2mu\sigma \nonumber
\end{align}
\item[(iii)] To show $dist_M(\ell,q)\leq R+2mu\sigma$ at the beginning of phase $\pi$, first note that $dist_M(p,\ell) \geq 2mu\sigma$ since the distance between $p$ and intersection is at least $2mu\sigma$.  Thus,
\begin{align}
&dist_M(\ell,q) \nonumber \\
=~ &dist_M(p,q) - dist_M(p,\ell) \nonumber \\
\leq~ &R+4mu\sigma - dist_M(p,\ell) \tag{by assumption}\\
\leq~ &R+4mu\sigma - 2mu\sigma \tag{by note above}\\
=~ &R+2mu\sigma \nonumber
\end{align} 
\end{itemize}
--(\emph{Case} 3) The distance between $p$ and the first intersection point on the path to $q$ is less than $2mu\sigma$ (see Figure \ref{fig:nk:maintain3}):  Consider the interval $I_{leader}$ of length $L+2G$ that (1) resides on the intersecting line where one endpoint is at Manhattan distance $2mu\sigma$ and the other endpoint is at Manhattan distance $L+2G+2mu\sigma$ from $p$, and (2) overlaps with the path from $p$ to $q$. Note that one endpoint of $I_{leader}$ is at most at distance $2mu\sigma$ from the intersection.  Since any two intersections are at least a distance $L+2G+6mu\sigma$ apart,  no line intersects $I_{leader}$. The Manhattan distance between $p$ and a point in $I_{leader}$ is at most $L+2G+2mu\sigma$. By Constraint \ref{nk:constraint3}, it follows that $L+2G+2mu\sigma \leq R$.  Thus, $I_{leader}$ is entirely on the path from $p$ to $q$. For the rest of the proof, part (i) and (ii) is similar to (Case 1), and part (iii) is similar to (Case 1a).
\end{proof}

Using Lemma \ref{lem:nk:maintainRmu}, we can show that, for any given node, knowledge about other nodes within Manhattan distance of $R$ can be maintained at all times: 

\begin{theorem}
\label{thm:nk:maintainR}
Every node knows every other node that is within a Manhattan distance of $R$ from itself at all times.
\end{theorem}
\begin{proof}
Since the time duration of each phase is $mu$ and the maximum node speed is bounded by $\sigma$, two nodes $p$ and $q$ that are separated by a Manhattan distance of at most $R$ during phase $\pi$ can be separated by a Manhattan distance of at most $R+2mu\sigma$ at the beginning of phase $\pi$.  Hence, by Lemma \ref{lem:nk:maintainRmu}, $p$ and $q$ already knew each other at the beginning of phase $\pi$.   
\end{proof}


\section{Speed of Message Propagation}
\label{sec:nk:speed}

For this section, we introduce the following constraint which says that the communication radius is strictly less than the half of the distance between two consecutive segments of the same color on a same line:
\begin{align}
R < \lfloor m/2 \rfloor G \label{nk:constraint4}.
\end{align}
Note that the above constraint does not violate Constraints \ref{nk:constraint1} to \ref{nk:constraint3}.

We analyze how fast messages can travel on the road network using our broadcast schedule.  To do so, we first analyze the speed of message propagation on a single line.  Specifically, we show that, considering message propagation from left to right (message propagation from right to left will be analogous) on a single line, if a leader node $p$ representing segment $s$ does a broadcast of ``$>$'' or ``$<>$'' at round $r$, then there exists a constant $c>0$ and a leader node $q$ that represents a segment $s+\Delta$ for some integer $\Delta \geq 0$ such that $q$ performs a broadcast of ``$>$'' or ``$<>$'' by round $r+c\Delta$; this will show that the speed of information propagation on a single line is at least one segment per $c$ rounds.

Using the speed of message propagation on a single line, we analyze the speed of information propagation on any given path in the road network.  Specifically, given points $A$ and $B$ on the road network where $A$ is the location where some node $p$ broadcasts a message, we will analyze the worst case time required for the message broadcast by $p$ to reach $B$.  The speed of message propagation can be easily calculated by dividing the $dist_M(A,B)$ with the total time required for a message to reach $B$ from $A$.  The basic idea of our analysis is as follows: We calculate the worst case time $\delta_1$ required to reach point $B$ from point $A$ pretending that $A$ and $B$ lies on a single line.  Then, we calculate the worst case time delay $\delta_2$ caused by changing from one line to another along the path from $A$ to $B$ by comparing it to the case when that line change has not occurred.  If a number of $k$ line changes occurred along the path from $A$ to $B$, then the worst case total time of message propagation from $A$ to $B$ would be at most $\delta_1+k\delta_2$.

Before we delve into the analysis of the speed of information propagation, we first make several observations on our schedule that are useful for our analysis.  All observations consider message propagation on a single line.

\begin{observation}
\label{obs:nk:2timeslots}
Suppose segment $s$ is \emph{not} scheduled to broadcast at the last round of phase $\pi$.  Then,
\begin{enumerate}
\item[(a)] if $s$ did a broadcast of ``$<>$'' in round $r$ of $\pi$, then segment $s-1$ (resp. $s+1$) does a leftward (resp. rightward) broadcast in round $r+1$ or $r+2$,
\item[(b)] if $s$ did a leftward broadcast (``$<$'') in round $r$ of $\pi$, then segment $s-1$ does a broadcast of ``$<>$'' or ``$<$'' in round $r+1$ or $r+2$, and
\item[(c)]  if $s$ did a rightward broadcast (``$<$'') in round $r$ of $\pi$, then segment $s+1$ does a broadcast of ``$<>$'' or ``$>$'' in round $r+1$ or $r+2$
\end{enumerate} 
\end{observation}

Observation \ref{obs:nk:2timeslots} basically tells us that, \emph{within a phase}, the difference of broadcast rounds of two adjacent segments is at most 2 assuming a single direction of message propagation.

\begin{observation}
\label{obs:nk:3timeslots}
Suppose segment $s$ is scheduled to broadcast at the last round $r$ of phase $\pi$.  Then, segment $s-1$ (resp. $s+1$) broadcasts in round $r+2$ or $r+3$.
\end{observation}

Observation \ref{obs:nk:3timeslots}, along with Observation \ref{obs:nk:2timeslots}, shows that the difference of broadcast rounds of two adjacent segments is at most 3 assuming a single direction of message propagation.

\begin{observation}
\label{obs:nk:only}
Suppose segment $s$ is scheduled to do a broadcast of ``$<$'' (resp. ``$>$'') in phase $\pi$.  Then, in phase $\pi+1$, segment $s-1$ is scheduled to do a broadcast of ``$>$'' (resp. ``$<$'') or ``$<>$'', segment $s$ is scheduled to do a broadcast of ``$>$'' (resp. ``$<$''), and segment $s+1$ is scheduled to do a broadcast of ``$>$'' (resp. ``$<$'') or ``$<>$''.
\end{observation}

Observation \ref{obs:nk:only} says that for any three consecutive segments $s-1$, $s$, and $s+1$ where $s$ does a leftward (resp. rightward) broadcast in phase $\pi$, all three segments do a broadcast in favor of propagating the message towards segments of increasing (resp. decreasing) order in phase $\pi+1$.   

Using the above observations, Lemma \ref{lem:nk:1dspeed} provides the speed of message propagation on a single line.  We use a similar approach as in \cite{ESW06} and \cite{S06}, however, our analysis turns out to be simpler since, in our case, every segment broadcasts in every phase. 

\begin{lemma}
\label{lem:nk:1dspeed}
The speed of message propagation on a single line is at least one segment per three rounds.
\end{lemma}
\begin{proof}
We prove with the assistance of Figure \ref{fig:nk:1dspeed}.  Suppose node $p$, which is the leader node of segment $s$ at phase $\pi$, broadcasts a message $m$ during phase $\pi$.  We only consider message propagation from left to right where node $p$ performs a broadcast of either ``$>$'' or ``$<>$'' during phase $\pi$ (considering ``$<$'' will be analogous).  Let $s'$ be the nearest segment on the left of $s$ where it is scheduled to broadcast in the first round of phase $\pi$. Also, let $s''$ be the nearest segment on the right of $s$ where it is scheduled to broadcast in the first round of phase $\pi+1$ (See Figure \ref{fig:nk:1dspeedconst}).  Note that segment $s$ itself can be the segment to broadcast in the first round of phase $\pi$ or the segment to broadcast in the last round of phase $\pi$.

\begin{figure}[tp]
  \centering
  \subfloat[The construction.]{\label{fig:nk:1dspeedconst}\includegraphics[scale=0.95]{figures/1dspeedconst.pdf}}\\
  \subfloat[Case 1.]{\label{fig:nk:1dspeedcase1}\includegraphics[scale=0.95]{figures/1dspeedcase1.pdf}}\\
  \subfloat[Case 2.]{\label{fig:nk:1dspeedcase2}\includegraphics[scale=0.95]{figures/1dspeedcase2.pdf}}
  \caption{Proof of Lemma \ref{lem:nk:1dspeed}.}
  \label{fig:nk:1dspeed}
\end{figure}

We divide into two cases depending on the distance between segments $s$ and $s''$:\\
--(\emph{Case} 1) The distance between $s$ and $s''$ is greater than $L$ (Figure \ref{fig:nk:1dspeedcase1}):  In this case, by the density requirement, there exists a leader node $q$ that represents segment $s+i$ at the beginning of phase $\pi$ where $s+i \in [s+1, s''-1]$.  

We show that $q$ receives message $m$ from $p$ during phase $\pi$.  The maximum distance between $p$ and $q$ at the beginning of phase $\pi$ is $L+G$.  Even though $p$ and $q$ move away from each other in maximum speed, the distance between $p$ and $q$ will be at most $L+G+2mu\sigma$ during phase $\pi$.  Hence, at any given time during phase $\pi$,
\begin{align}
dist_E(p,q) &\leq L+G+2mu\sigma \nonumber \\
&\leq R-L-2G-6mu\sigma \tag{by Constraint \ref{nk:constraint3}} \\
&<R \nonumber
\end{align}
which implies that $q$ receives $m$.

Since $s''$ is the nearest segment to the right of $s$ that broadcasts in the first round of phase $\pi+1$, $q$ performs a rightward broadcast in phase $\pi$ after $p$'s broadcast due to the definition of our schedule.  Hence, by Observation \ref{obs:nk:2timeslots}, if $p$ broadcasts at round $r$, then $q$ does a rightward broadcast by round $r+2i$.\\
--(\emph{Case} 2) The distance between $s$ and $s''$ is at most $L$ (Figure \ref{fig:nk:1dspeedcase2}):  In this case, there might not be a node in between segments $s$ and $s''$.  Consider the interval $I_{leader}$ of length $L+G$ from the right endpoint of segment $s''$ towards segment $s'+m$.  First note that, due to the definition of our schedule, the distance between $s''$ and $s'+m$ (also the distance between $s''$ and $s'$) is at least $\lfloor m/2 \rfloor G - G$. We get
\begin{align}
\lfloor m/2 \rfloor G - G &> R-G \tag{by Constraint \ref{nk:constraint4}}\\
&\geq 2L+2G+8mu\sigma \tag{by Constraint \ref{nk:constraint3}}\\
&> L+G \nonumber 
\end{align}
which implies that $I_{leader}$ is entirely in between $s''$ and $s'+m$.

By the density requirement, there exists a node $q'$ in $I_{leader}$ at the beginning of phase $\pi+1$.  Let $s+i$ be the segment where node $q'$ lies on at the beginning of phase $\pi+1$ where $s+i \in [s'', s'+m-1]$ .  Since the leader node of $s+i$ at the beginning of phase $\pi$ can be at most at distance $G$ from $q'$, there exists a leader node $q$ in $I_{leader}$ that represents segment $s+i$ at the beginning of phase $\pi+1$.  

We show that $q$ receives $p$'s broadcast message $m$ in phase $\pi$.  Since $q$ is in $I_{leader}$ at the beginning of phase $\pi+1$, $q$ could be a distance of at most $mu\sigma$ away from the right endpoint of $I_{leader}$ during phase $\pi$.  Node $p$ can be a distance of at most $mu\sigma$ away from the left endpoint of segment $s$.  Hence, nodes $p$ and $q$ can be a distance of at most $2L+3G+2mu\sigma$ away from each other during phase $\pi$.  Thus, at any given time during phase $\pi$,
\begin{align}
dist_E(p,q) &\leq 2L+3G+2mu\sigma \nonumber \\
&\leq R-6mu\sigma \tag{by Constraint \ref{nk:constraint3}}\\
&<R \nonumber
\end{align}
which implies that $q$ receives $p$'s broadcast during phase $\pi$.

By the definition of our schedule, $q$ performs a rightward broadcast during phase $\pi+1$.  Also, since $s''$ is the node that performs the first broadcast of phase $\pi+1$, $s''$ is also the segment that performs the last broadcast of phase $\pi$.  Hence, by Observations \ref{obs:nk:2timeslots} and \ref{obs:nk:3timeslots}, if $p$ broadcast at round $r$, then $q$ does a rightward broadcast by round $r+3i$.

Combining the results of (Case 1) and (Case 2), we obtain that the speed of information propagation is at least one segment per three rounds.
\end{proof}

The following lemma is useful in determining the time delay of changing the direction of message propagation on a single line which in turn plays a key role in determining the speed of message propagation.

\begin{comment}
We now show that if all nodes in an interval $I$ of length $L+2G+6mu\sigma$ on a single line knows a message $m$ during some phase $\pi$, then there will be a node $q_1$ (resp. $q_2$) in $I$ such that $q_1$ knows $m$ and it performs a broadcast of ``$>$'' or ``$<>$'' representing a segment $s_1$ (resp. $s_2$) in $I$ until the end of phase $\pi+2$.
\end{comment}

\begin{figure}[tp]
\centering
\includegraphics[scale=0.95]{figures/trapmessage.pdf}
\caption{Proof of Lemma \ref{lem:nk:trapmessage}.}
\label{fig:nk:trapmessage}
\end{figure}

\begin{lemma}
\label{lem:nk:trapmessage}
Let $I$ be an interval of length $L+2G+6mu\sigma$ on a single line where no other line intersects it and suppose that every node in $I$ knows message $m$ at some time $t$ during phase $\pi$.  Then,
\begin{itemize}
\item[(a)] there exists a leader node that represents a segment in $I$ such that it knows $m$ and performs a broadcast of ``$>$'' or ``$<>$'' by the end of phase $\pi+2$, and
\item[(b)] there exists a leader node that represents a segment in $I$ such that it knows $m$ and performs a broadcast of ``$<$'' or ``$<>$'' by the end of phase $\pi+2$.
\end{itemize} 
\end{lemma}
\begin{proof}
We only prove part (a); part (b) will be analogous.  By the density requirement, during phase $\pi$, there exists a node $p$ in an interval $I_{L}$ of length $L$ that is centered inside $I$; the left (resp. right) end of $I_{L}$ and the left (resp. right) end of $I$ are a distance of $G+3mu\sigma$ apart (see Figure \ref{fig:nk:trapmessage}).  Let $s_p^{\pi}$ be the segment where node $p$ was located at the beginning of phase $\pi$.  At the beginning of phase $\pi$, node $p$ could be at most a distance of $mu\sigma$ from the left and right end of $I_{L}$ (since the maximum distance a node can travel during a phase is bounded by $mu\sigma$) and the leader node $q$ that represents segment $s_{p}^{\pi}$ in phase $\pi$ can be at most $G+mu\sigma$ from the left and right end of $I_{L}$ since $p$ and $q$ have to be in the same segment at the beginning of phase $\pi$.  During phase $\pi$, node $q$ can move at most $G+2mu\sigma$ from the left and right end of $I_{L}$ which implies that $q$ will be in $I$ all times during phase $\pi$.  Thus, $q$ knows $m$ at time $t$.  If node $q$ is scheduled to broadcast after time $t$ within phase $\pi$ and performs a broadcast of ``$>$'' or ``$<>$'', then we are done.  The remaining cases we need to consider are:\\
--(\emph{Case} 1) Node $q$ performed a broadcast of ``$<$'' after time $t$ within $\pi$: Consider phase $\pi+1$.  Let $s_{p}^{\pi+1}$ be the segment where node $p$ is located at the beginning of phase $\pi+1$.  At the beginning of phase $\pi+1$, node $p$ can be at most $mu\sigma$ apart from the left and right end of $I_{L}$ and the leader node $q'$ that represents segment $s_p^{\pi+1}$ in phase $\pi+1$ can be at most $G+mu\sigma$ apart from the left and right end of $I_{L}$.  At all times during phase $\pi$, node $q'$ could have been at most $G+2mu\sigma$ from the the left and right end of $I_{L}$ since the maximum distance a node can travel during a phase is bounded by $mu\sigma$.  Thus, $q'$ was in $I$ at all times during phase $\pi$ which implies that $q'$ knows $m$.  By Constraint \ref{nk:constraint2}, node $p$ can be located in either $s_p^{\pi}-1$, $s_p^{\pi}$, or $s_p^{\pi}+1$ ($s_p^{\pi+1} \in [s_p^{\pi}-1, s_p^{\pi}+1]$).  Hence, by Observation \ref{obs:nk:only}, $q'$ performs a broadcast of ``$>$'' in phase $\pi+1$.\\
--(\emph{Case} 2) Node $q$ was scheduled to broadcast before time $t$ during phase $\pi$:  In this case, node $q$ missed its chance to broadcast $m$ during phase $\pi$.  Consider phase $\pi+1$.  At the beginning of phase $\pi+1$, there exists a node $p'$ in interval $I_{L}$ (by the density requirement).  Let $s_{p'}^{\pi+1}$ be the segment where node $p'$ is located at the beginning of phase $\pi+1$.  The leader node $q_1$ that represents $s_{p'}^{\pi+1}$ in phase $\pi+1$ can be located at most $G$ apart from the left and right end of $I_{L}$.  At all times during phase $\pi$, node $q_1$ could have been at most $G+mu\sigma$ from the left and right end of $I_{L}$ since the maximum distance a node can travel during a phase is bounded by $mu\sigma$.  Thus, $q_1$ was in $I$ at all times during phase $\pi$ which implies that $q_1$ knows $m$.  If $q_1$ performs a broadcast of ``$>$'' or ``$<>$'' in phase $\pi+1$, then we are done.  

The remaining is to consider the case of $q_1$ performing a broadcast of ``$<$'' in phase $\pi+1$.  Now, consider phase $\pi+2$.  Let $s_{p'}^{\pi+2}$ be the segment where node $p'$ is located at the beginning of phase $\pi+2$. Similar to node $p$ and $q'$ in (Case 1), at the beginning of phase $\pi+2$, node $p'$ can be at most $mu\sigma$ apart from the left and right end of $I_{L}$ and the leader node $q_2$ that represents segment $s_p^{\pi+2}$ in phase $\pi+2$ can be at most $G+mu\sigma$ apart from the left and right end of $I_{L}$.  At all times during phase $\pi$, node $q_2$ could have been at most $G+3mu\sigma$ from the the left and right end of $I_{L}$ since the maximum distance a node can travel during two phases is bounded by $2mu\sigma$ (note that $q_2$ is a leader node at the beginning of phase $\pi+2$).  Thus, $q_2$ was in $I$ at all times during phase $\pi$ which implies that $q_2$ knows $m$.  The rest of the proof is similar to (Case 1).
\end{proof}

The following simple lemma tells us that in an interval of length $L+2G+2mu\sigma$ on a single line, there always exists a leader node:

\begin{lemma}
\label{lem:nk:alwaysleader}
Let $I$ be an interval of length $L+2G+2mu\sigma$ on a single line where no other line intersects.  Then, during each phase $\pi$, there exists a leader node $q$ that remains in $I$ at all times during $\pi$. 
\end{lemma}
\begin{proof}
Suppose, in contradiction, that no such leader node exists. By the density requirement, at the beginning phase $\pi$, there exists a node $p$ in an interval $I_{L}$ of length $L$ that is centered inside $I$; the left (resp. right) end of $I_{L}$ and the left (resp. right) end of $I$ are a distance of $G+mu\sigma$ apart.  Let $s_p$ be the segment where $p$ is located at the beginning of phase $\pi$.  The leader node $q$ representing segment $s_p$ during phase $\pi$ can be at most $G$ apart from the left and right end of $I_{L}$ at the beginning of $\pi$ since $p$ and $q$ has to be in the same segment at the beginning of $\pi$.  Since the distance that a node can move during a phase is bounded by $mu\sigma$, $q$ can be at most $G+mu\sigma$ apart from the left and right end of $I_{L}$ during phase $\pi$.  Hence, $q$ remains within $I$ at all times during phase $\pi$, a contradiction.  
\end{proof}

Considering message propagation from any source location $S$ to any destination point $D$ on the road network where there is exactly one line change occurring along the shortest path from $S$ to $D$, we determine the worst case amount of time message propagation can be delayed due to a line change by comparing it to the case when that line change has not occurred.  Given a node $p$ and a position $D$ on the road network, we say that node $p$, positioned at point $S$ on the road network, performs a \emph{well-directed} broadcast towards position $D$ on the road network if the direction (``$>$'', ``$<$'', or ``$<>$'') of $p$'s broadcast is in favor of the direction of message propagation along the shortest path from $S$ to $D$ on the road network.

\begin{figure}[tp]
  \centering
  \subfloat[Case 1.]{\label{fig:nk:2dspeedcase1}\includegraphics[scale=0.95]{figures/2dspeedcase1.pdf}}
  \subfloat[Case 2.]{\label{fig:nk:2dspeedcase2}\includegraphics[scale=0.95]{figures/2dspeedcase2.pdf}}
  \caption{Proof of Lemma \ref{lem:nk:linechangedelay}.}
  \label{fig:nk:2dspeed}
\end{figure}

\begin{lemma}
\label{lem:nk:linechangedelay}
Let $S$ and $D$ be positions on the road network where exactly one line change occurs along the shortest path from $S$ to $D$ on the road network.  Suppose node $p$ performs a broadcast of message $m$ at point $S$ towards $D$ at time $t$.  Then, message $m$ reaches point $D$ by time $t+3u(\lceil dist_{M}(S,D)/G \rceil+\lceil (L+2G+6mu\sigma)/G \rceil +2) +3u(\lceil (L+5G+6mu\sigma)/G \rceil+1) + 6mu$. 
\end{lemma}
\begin{proof}
We prove with the assistance of Figure \ref{fig:nk:2dspeed}.  Let $\ell_1$ and $\ell_2$ be lines where $S$ and $D$ lies on, respectively.  Also, let $X$ be the point on the road network where $\ell_1$ and $\ell_2$ intersect.  We divide into two cases depending on the angle $\alpha$ between $\ell_1$ and $\ell_2$:\\
--(\emph{Case} 1) $\alpha \leq \pi/2$ (see Figure \ref{fig:nk:2dspeedcase1}): Let $A$ be a point on $\ell_2$ where $dist_E(A,X)=L+2G+6mu\sigma$ and in between $X$ and $D$.  Note that no other line intersects in between $X$ and $A$ since the distance between any two intersection point is greater than $L+2G+6mu\sigma$.  We further divide into two cases depending on the distance between $S$ and $X$:\\
---(\emph{Case} 1a) $dist_E(S,X) \leq L+2G+2mu\sigma$: We first show that when $p$ broadcasts message $m$ at time $t$, every node in between $X$ and $A$ on $\ell_2$ receives $m$.  The requirement would be to show that the Euclidean distance between $S$ and $A$ is at most $R$. $dist_E(S,A)$ becomes maximum when $\alpha = \pi/2$.  We can obtain a relationship between $dist_{E}(S,A)$ and $R$ as the following:
\begin{align}
&(dist_{E}(S,A))^2 \nonumber \\
=~ &(dist_{E}(X,S))^2 + (dist_{E}(X,A))^2 \nonumber \\
=~ &(L+2G+2mu\sigma)^2 + (L+2G+6mu\sigma)^2 \nonumber \\
<~ &(2L+3G+8mu\sigma)^2 \nonumber \\
\leq~ &R^2 \nonumber
\end{align}
Thus, we get $dist_{E}(S,A) \leq R$.

By Lemma \ref{lem:nk:trapmessage}, at most three phases ($3mu$ time) are needed for a leader node $q$ in between point $X$ and point $A$ that possesses $m$ to perform a rightward broadcast towards point $D$.  

Let $s_p$ be the segment on line $\ell_1$ where $p$ is located at time $t$ and let $E$ indicate the location of the endpoint of $s_p$ that is closer to $S$.  Now, suppose $S$ and $D$ were on the same single line.  In order to directly apply Lemma \ref{lem:nk:1dspeed}, the segment $s_q$ on $\ell_2$ that $q$ represents should be a segment that is entirely on the path from $S$ to $D$ and at least a Manhattan distance of $G$ from $E$.  However, $s_q$ might not satisfy these conditions since the segmentation of $\ell_1$ and $\ell_2$ are independent from each other. Consider an interval $I_G$ of length $3G$ on $\ell_2$ that is entirely on the path from $S$ to $D$ where the left endpoint resides on $X$.  Since there is always a segment that is entirely in an interval of length $2G$, there exists a segment $s'$ of $\ell_2$ in $I_G$ that is entirely on the path from $S$ to $D$ and at least a Manhattan distance of $G$ from $E$.  Thus, if $s_q$ is a segment that is located on the left of $s'$, we can apply Lemma \ref{lem:nk:1dspeed} on the single line by considering a time delay of which $s'$ being scheduled to perform a rightward broadcast after $q$ performing a rightward broadcast.  This time delay can be at most $3u(\lceil 3G/G \rceil+1) = 12u$ since the speed of message propagation on a single line is one segment per 3 rounds (by Lemma \ref{lem:nk:1dspeed}) and there is at most $\lceil 3G/G \rceil+1$ segments of $\ell_2$ that overlap with $I_G$.  

If $S$ and $D$ were on the same line, then, by Lemma \ref{lem:nk:1dspeed}, the amount of time required for message $m$ to reach $D$ from $S$ is at most $3u(\lceil dist_M(S,D)/G \rceil+1)$ since the speed of message propagation on a single line is one segment per 3 rounds (by Lemma \ref{lem:nk:1dspeed}) and there can be at most $\lceil dist_M(S,D)/G \rceil+1$ segments that overlap with with the path from $S$ to $D$.  Hence, the amount of time required for message $m$ to reach $D$ from $S$ on the road network is at most $3u(\lceil dist_M(S,D)/G \rceil+1)+3mu+12u$.\\
%And, if $S$ and $D$ were on the same line, then, by Lemma \ref{lem:nk:1dspeed}, the amount of time required for $m$ to reach $D$ from $S$ would be at most $3\lceil dist_{M}(S,D)/G \rceil u$ (message $m$ moves at least one segment per 3 rounds on a single line).  Hence, the amount of time required for message $m$ to reach $D$ from $S$ on the road network is at most $3\lceil dist_{M}(S,D)/G \rceil u +3mu$.\\  
---(\emph{Case} 1b) The distance from $S$ to $X$ is greater than $L+2G+2mu\sigma$: In this case, we need to consider an additional delay that can be caused by $p$ performing a broadcast that is \emph{not} well-directed towards $D$.  Let $s_p$ be the segment on line $\ell_1$ where $p$ is located at time $t$ and let $I_p$ be an interval of length $L+2G+6mu\sigma$ on $\ell_1$ such that $p$ is located in $I_p$ at time $t$ and there is no intersection point in $I_p$.  Note that such $I_p$ exists since the distance between any two intersection points is greater than $L+2G+6mu\sigma$.  When $p$ broadcasts $m$ at time $t$, all nodes in $I_p$ receives $m$ since $R>L+2G+6mu\sigma$ by Consttraint \ref{nk:constraint3}.  Now, by applying Lemma \ref{lem:nk:trapmessage}, there exists a leader node $q$ in $I_p$ that performs a well-directed broadcast towards $D$ by time $t+3mu$.  The time delay from $q$ performing a well-directed broadcast to $s_p$ being scheduled to perform a well-directed broadcast is at most $3u(\lceil (L+2G+6mu\sigma)/G \rceil + 1)$  since the speed of message propagation on a single line is one segment per 3 rounds (by Lemma \ref{lem:nk:1dspeed}) and there is at most $\lceil (L+2G+6mu\sigma)/G \rceil + 1$ segments of $\ell_1$ that overlap with $I_p$.

Let $I_{\ell}$ be an interval of length $L+2G+2mu\sigma$ that is in between $X$ and $S$ where one end point lies on $X$.  Message $m$ will make progress of at least one segment per 3 rounds towards the intersection point $X$ (by Lemma \ref{lem:nk:1dspeed}) and $m$ will reach a leader node in $I_{\ell}$ (there exists a leader node in $I_{\ell}$ at all times due to Lemma \ref{lem:nk:alwaysleader}) which will rebroadcast $m$ at some time $t'$ such that all nodes in between $X$ and $A$ receives $m$ at $t'$.  The rest of the proof is similar to (Case 1a).  Hence, the amount of time required for message $m$ to reach $D$ from $S$ on the road network is at most $3u(\lceil dist_M(S,D)/G \rceil+\lceil (L+2G+6mu\sigma)/G \rceil+2)+6mu+12u$.
\\ 
--(\emph{Case} 2) $\alpha > \pi/2$ (see Figure \ref{fig:nk:2dspeedcase2}): Let $I_{\ell}$ be an interval of length $L+2G+2mu\sigma$ such that one end point lies on $X$ and the other end point is at most a distance of $L+2G+2mu\sigma$ apart from $S$.  Let $B$ be a point on $\ell_2$ where $dist_E(B,X)=L+2G+6mu\sigma$ and not in between $X$ and $D$. Similar to (Case 1), all nodes in between point $B$ and $X$ will receive message $m$ by the broadcast performed by a node in $I_{\ell}$ and, by Lemma \ref{lem:nk:trapmessage}, at most $3mu$ time will be needed for a leader node $q$ in between point $X$ and point $A$ to perform a rightward broadcast towards point $D$.   Also, similar to (Case 1b), the additional delay of $3mu+3u(\lceil (L+2G+6mu\sigma)/G \rceil + 1)$ (which can be caused by $p$ performing a broadcast that is not well-directed towards $D$) has to be considered.

Let $I_G$ be an interval of length $3G$ on $\ell_2$ that is entirely on the path from $S$ to $D$ where the left endpoint resides on $X$.  Also, let $s'$ be a segment of $\ell_2$ that is the rightmost segment among all segments that are entirely in $I_G$.  Now, suppose $S$ and $D$ were on the same single line. Similar to (Case 1a), applying Lemma \ref{lem:nk:1dspeed} requires us to consider an additional time delay of which $s'$ being scheduled to perform a rightward broadcast after $q$ performing a rightward broadcast .  This time delay can be at most $3u(\lceil (L+5G+6mu\sigma)/G \rceil+1)$ since the speed of message propagation on a single line is one segment per 3 rounds (by Lemma \ref{lem:nk:1dspeed}) and there are at most $\lceil (L+5G+6mu\sigma)/G \rceil +1$ segments of $\ell_2$ that overlap with the path from $B$ to the right endpoint of $I_G$.  Hence, the amount of time required for message $m$ to reach $D$ from $S$ on the road network is at most $3u(\lceil dist_{M}(S,D)/G \rceil+\lceil (L+2G+6mu\sigma)/G \rceil +2) +3u(\lceil (L+5G+6mu\sigma)/G \rceil+1) + 6mu$.
\end{proof}

Finally, we determine the worst case amount of time required for a message $m$ broadcast at point $S$ to reach point $D$ where multiple line changes occur along the shortest path from $S$ to $D$ on the road network.  In this case, we can consider the shortest path from $S$ to $D$ as a composition of intervals where, in each interval, exactly one line change occurs. Also, we can consider that among all initial broadcasts performed in each such intervals, the only broadcast that cannot be well-formed towards $D$ is the broadcast of $m$ at point $S$.  Hence, we obtain the following theorem:

\begin{theorem}
\label{thm:nk:speedofmessage}
Let $S$ and $D$ be positions on the road network where $k$ line changes occur along the shortest path from $S$ to $D$ on the road network.  Suppose node $p$ performs a broadcast of message $m$ at point $S$ at time $t$.  Then, message $m$ reaches $D$ by time $t+3u(\lceil dist_{M}(S,D)/G \rceil+\lceil (L+2G+6mu\sigma)/G \rceil+2) +3ku(\lceil (L+5G+6mu\sigma)/G \rceil+1) + 3mu(k+1)$.
\end{theorem}

A lower bound on the speed of message propagation from point $S$ to point $D$ on the road network can be easily obtained by dividing $dist_{M}(S,D)$ with the total time required for a message propagated at point $S$ to reach point $D$:

\begin{corollary}
\label{cor:nk:speedofmessage}
Let $S$ and $D$ be positions on the road network where $k$ line changes occur along the shortest path from $S$ to $D$ on the road network.  Suppose node $p$ performs a broadcast of message $m$ at point $S$ towards $D$ at time $t$.  Then, the speed of propagating $m$ from $S$ to $D$ is at least $dist_{M}(S,D)/(3u(\lceil dist_{M}(S,D)/G \rceil+\lceil (L+2G+6mu\sigma)/G \rceil+2) +3ku(\lceil (L+5G+6mu\sigma)/G \rceil+1) + 3mu(k+1))$.
\end{corollary}

\section{Dynamic Clusters}
\label{sec:nk:cluster}

In this section, we do not assume that the density requirement holds for the entire road network.  Instead, we consider grouping nodes into \emph{clusters} on a single line where the density requirement holds within each cluster.  In addition, we assume that nodes move infinitely often and $L \geq G$.

Suppose node $p$ lies on line $\ell$ at time $t$.  We say that node $p$ is an $\ell$-node at $t$ if there exists a time $t' > t$ such that (1) for all times during $[t,t']$, $p$ lies on line $\ell$ and (2) $p$ moves during $[t,t']$.  Since we have assumed that nodes move infinitely often, a node that is located at an intersection point of lines $\ell_1$ and $\ell_2$ at time $t$ is either an $\ell_1$-node or an $\ell_2$-node but not both.     

Similar to \cite{S06}, we define a cluster as a group of nodes in which the density requirement holds:

\begin{definition}[$L$-cluster]
\label{def:nk:Lcluster}
At any given time $t$, an $L$-cluster is a maximal set of $\ell$-nodes that lie on the same one-dimensional line $\ell$ such that if we align the $\ell$-nodes based on their position on line $\ell$, then the distance between any two consecutive $\ell$-nodes is at most $L$.
\end{definition}

Note that each $L$-cluster is defined on a single one-dimensional line.  This means that two nodes that are on different lines cannot be within the same $L$-cluster even though they are at most a Manhattan distance of $L$ apart from each other.

At any given time, we call the nodes that are located at each end of an $L$-cluster $C$ as \emph{boundary nodes} of $C$.
We assume that, for each $L$-cluster, boundary nodes are elected as leaders of their corresponding segment at the beginning of each phase.  Again, this could be done by local computation under a condition that every node in a segment at the beginning of a phase know the trajectory function of one another in that segment.  Also, note that, at the beginning of each phase, two or more boundary nodes of different $L$-clusters cannot be in the same segment since we have assumed that $L \geq G$.  

We are interested in maintaining neighbor knowledge within an $L$-cluster $C$ which is formed as a result of (1) merging two $L$-clusters $C_1$ and $C_2$ on the same line where neighbor knowledge was maintained in both $C_1$ and $C_2$ before the merge happened, or (2) merging an $L$-cluster $C_1$ and a single node $p$ where, before the merge happened, neighbor knowledge was maintained in $C_1$ and node $p$ was located on a line that is different from the line that $C_1$ lies on.     

As in \cite{S06}, we define \emph{knowledgeable} $L$-clusters to formalize the above:

\begin{definition}[Knowledgeable $L$-cluster]
\label{def:nk:knowledgeable}
An $L$-cluster $C$, defined on line $\ell$ is \emph{knowledgeable} during a time interval if (1) it has the same set of $\ell$-nodes at every instant of time during the time interval, and (2) at the beginning of each phase during the time interval, every $\ell$-node in $C$ knows every other $\ell$-node in $C$ that is a distance of at most $R+2mu\sigma$ from itself.  
\end{definition}
Roughly speaking, a knowledgeable $L$-cluster is a cluster in which the density requirement holds and neighbor knowledge is maintained.  

By applying the same proof technique as in (Case 1) of Lemma \ref{lem:nk:maintainRmu}, we obtain the following simple lemma:

\begin{lemma}
\label{lem:nk:stabletoknowledgeable}
Suppose an $L$-cluster $C$, defined on line $\ell$, has the same set of $\ell$-nodes in every instant of time in $[t,t'']$ and there exists a phase beginning at time $t' \in [t,t'']$ where every $\ell$-node in $C$ knows every other $\ell$-node in $C$ that is a distance of at most $R+2mu\sigma$ from itself.   Then, $C$ is knowledgeable during $[t',t'']$.
\end{lemma}

%Note that if an $L$-cluster $C$ has the same set of nodes in every instant of time in $[t,t'']$ and there exists a phase beginning at time $t' \in [t,t'']$ where every node in $C$ knows every other nodes in $C$ that is a distance of at most $R+2mu\sigma$ from itself, then applying Lemma \ref{lem:nk:maintainRmu} shows that $C$ becomes knowledgeable during $[t',t'']$.

\subsection{Merging of Two $L$-clusters on the Same Line}
\label{subsec:nk:merge2clusters}

Maintaining neighbor knowledge after merging two $L$-clusters has been already discussed in \cite{S06}.  The analysis given in \cite{S06} concentrates on handling the situation of a boundary leader node not being able to broadcast in a phase (this situation may occur since not all segments are scheduled to broadcast in a phase).  However, it is missing some details on why a node in one cluster gets to learn about other nodes in a different cluster before the two clusters merge.  We provide a rigorous analysis that fills in the missing details.  

The following simple lemma shows that if two nodes on the same line are a distance of $R-3G$ apart, then it takes more than $4mu$ time for those nodes to become a distance of $L$ apart from each other.

\begin{lemma}
\label{lem:nk:R3Gapart}
Let $p$ and $q$ be two nodes that are on the same line $\ell$ at time $t$.  Suppose both $p$ and $q$ only move on $\ell$ and the distance between $p$ and $q$ at time $t$ is $R-3G$.  Then, at time $t+4mu$, the distance between $p$ and $q$ is greater than $L$.
\end{lemma}
\begin{proof}
The time it takes for $p$ and $q$ to become a distance of $L$ apart when both $p$ and $q$ approach each other in maximum speed is (using Constraint \ref{nk:constraint3}):
\begin{align}
&(R-3G-L)/2\sigma \nonumber \\
\geq~ &(2L+3G+8mu\sigma-3G-L)/2\sigma \tag{by Constraint \ref{nk:constraint3}} \\
=~ &(L+8mu\sigma)/2\sigma \nonumber \\
>~ &4mu \nonumber
\end{align}
Hence, the lemma is proven.
\end{proof}

If a $L$-cluster is knowledgeable for a sufficiently long period of time, then each node in the cluster not only maintains neighbor knowledge but also ``gains'' neighbor knowledge within the cluster:

\begin{lemma}
\label{lem:nk:gainknowledge}
Suppose $L$-cluster $C$, defined on line $\ell$, is knowledgeable from the beginning of phase $\pi$ to the beginning of phase $\pi+k$ for some integer $k \geq 0$.  And, let $S$ be the set of $\ell$-nodes in $C$ from the beginning of phase $\pi$ to the beginning of phase $\pi+k$.  Then, 
\begin{itemize}
\item[(a)] at the beginning of phase $\pi+i$ where $i=0,1,...,k$, each node $p$ in $S$ knows every other node in $S$ that is at most a distance of $R+i(L+G+2mu\sigma)+2mu\sigma$ from itself, and
\item[(b)] at any time during phase $\pi+i$ where $i=0,1,...,k$, each node $p$ in $S$ knows every other node in $S$ that is at most a distance of $R+i(L+G+2mu\sigma)$ from itself.
\end{itemize}
\end{lemma}
\begin{proof}
We first show that, assuming part (a) holds, part (b) holds.  Assume, at the beginning of phase $\pi+i$, node $p$ in $S$ knows every other node in $S$ that is at most a distance of $R+i(L+G+2mu\sigma)+2mu\sigma$ apart from itself.  Suppose, in contradiction, that there exists a node $q$ in $S$ that is at most a distance of $R+i(L+G+2mu\sigma)$ from $p$ during phase $\pi+i$ but does not know $p$.  Since a node can move at most a distance of $mu\sigma$ in a phase, the distance between $p$ and $q$ at the beginning of phase $\pi+i$ can be at most $R+i(L+G+2mu\sigma)+2mu\sigma$.  Thus, $p$ must have known $q$ at the beginning of phase $\pi+i$, a contradiction.  

\begin{figure}[t]
\centering
\includegraphics[scale=0.95]{figures/gainknowledge.pdf}
\caption{Proof of Lemma \ref{lem:nk:gainknowledge}.}
\label{fig:nk:gainknowledge}
\end{figure}

Now, we prove part (a) by induction on $i$.  The base case ($i=0$) immediately follows from the definition of a knowledgeable $L$-cluster.  For the inductive case, we assume the lemma holds for phase $\pi+i$ and we prove it for phase $\pi+i+1$.  Let $\ell$ be the line where $C$ is defined on.  As illustrated in Figure \ref{fig:nk:gainknowledge}, consider an interval $I_{leader}$ of length $L+2G+2mu\sigma$ to the right of node $p$ at the beginning of phase $\pi+i$ where the right end interval $I_{leader}$ is a distance of $R-mu\sigma$ apart from $p$ (considering $I_{leader}$ to be at the left of $p$ will be analogous).    By Lemma \ref{lem:nk:alwaysleader}, there exists a leader node $q'$ that remains in $I_{leader}$ during phase $\pi+i$.  Note that, during phase $\pi+i$, the distance between $p$ and $q'$ can be at most $R$.  Thus, $p$ receives the broadcast of $q'$during phase $\pi+i$.  

By the inductive hypothesis and by the proof in the previous paragraph, leader node $q'$ knows every node that is at most a distance of $R+(L+G+2mu\sigma)i$ to the right from itself during phase $\pi+i$.  Let $I_{right}$ be an interval at the end of phase $\pi+i$ such that $p$ is located at the left end of $I_{right}$ and $p$ knows every node in $I_{right}$.  We consider the worst case movement of $p$ and $q'$ that minimizes the length of $I_{right}$.  The worst case position of $p$ and $q$ by the end of phase $\pi+i$ would be $p$ being located at a point that is a distance of $mu\sigma$ to the right of $p$'s position at the beginning of phase $\pi+i$ (point $A$ in Figure \ref{fig:nk:gainknowledge}) and $q$ being located at the left end of $I_{leader}$ (point $B$ in Figure \ref{fig:nk:gainknowledge}).  Since $p$ receives the broadcast of $q'$ during phase $\pi+i$ and by Constraint \ref{nk:constraint3}, $p$ will know every node that is at most a distance of 
\begin{align}
%&~(R-mu\sigma)-mu\sigma-(L+2G+2mu\sigma)+R+(L+G+2mu\sigma)i \nonumber \\
&2R+(L+G+2mu\sigma)i-(L+2G+4mu\sigma) \nonumber \\
\geq &~R+(L+G+2mu\sigma)i+(L+G+4mu\sigma) \tag{by Constraint \ref{nk:constraint3}} \\
= &~R+(L+G+2mu\sigma)(i+1)+2mu\sigma \nonumber
\end{align}
to its right at the end of phase $\pi+i$.  
\end{proof}

The following lemma assists in proving the main theorem of this section (Theorem \ref{thm:nk:mergeclusters}).  It is used when there is a need to determine how much information about an $L$-cluster $C_2$ is known by a node $p$ in some other $L$-cluster $C_1$ during a certain phase.  See the proof of Theorem \ref{thm:nk:mergeclusters} for details.

\begin{lemma}
\label{lem:nk:lose2musigma}
Let $C$ be an $L$-cluster defined on line $\ell$.  Suppose node $p$ knows every $\ell$-node in $C$ that is a distance of at most $X$ from the left (resp. right) end of $C$ at the beginning of phase $\pi$ where $X \geq 2mu\sigma$.  And, let $S$ be the set of $\ell$-nodes in $C$ at the beginning of phase $\pi$.  Then, at all times $t$ during phase $\pi$, node $p$ knows every node in $S$ that is a distance of at most $X-2mu\sigma$ from the leftmost (resp. rightmost) node among the nodes in $S$ at time $t$. 
\end{lemma}
\begin{proof}
Suppose, in contradiction, that, during phase $\pi$, there exists a node $q$ that is in $S$ and is within a distance of $X-2mu\sigma$ from the leftmost node among the nodes in $S$ but is not known to $p$.  At the beginning of phase $\pi$, the distance between the left end of $C$ and node $q$ must have been greater than $X$ because otherwise $p$ would have already known $q$.  The distance between the left end of $C$ and $q$ becomes minimal when the left boundary (leader) node $q'$ of $C$ and $q$ approach each other in maximum speed during phase $\pi$.  Even in this case, the distance between the left end of $C$ and $q$ is always greater than $X-2mu\sigma$ during phase $\pi$ since both $q$ and $q'$ can move at most a distance of $mu\sigma$ during a phase, a contradiction. 
\end{proof}

Now, we show the main theorem of this section which tells us that a new $L$-cluster $C_3$, which is formed by merging two knowledgeable $L$-clusters $C_1$ and $C_2$, becomes knowledgeable if $C_1$ and $C_2$ were sufficiently far apart before they merged: 

\begin{theorem}
\label{thm:nk:mergeclusters}
Let $t''$, $t$, and $t'$ be times such that $t'' < t < t'$.  Suppose $C_3$ is a $L$-cluster on line $\ell$ that has the same set of $\ell$-nodes in every instant of time during $[t,t']$.  Also, suppose that the $\ell$-nodes in $C_3$ are partitioned into sets $S_1$ and $S_2$ during $[t'',t)$ such that all nodes in $S_1$ form a $L$-cluster $C_1$ on $\ell$ and all nodes in $S_2$ form a $L$-cluster $C_2$ on $\ell$ during $[t'',t)$. Without loss of generality, let $C_1$ be located to the left of $C_2$ on $\ell$.  If (1) $C_1$ and $C_2$ are both knowledgeable in $[t'',t)$ and (2) the distance between the right end of $C_1$ and the left end of $C_2$  at time $t''$ is at least $R-3G$, then $C_3$ is knowledgeable in $[t,t']$.
\end{theorem}
\begin{proof}
Let $t_{\pi}$ be the most recent time when a phase begins that is strictly less than time $t$, and let $\pi$ be the phase that begins at time $t_{\pi}$.  We only need to show that, at the beginning of phase $\pi+1$, every node in $C_3$ knows every other node in $C_3$ that is at most a distance of $R+2mu\sigma$ from itself; Lemma \ref{lem:nk:stabletoknowledgeable} will take care of the rest of the phase beginnings after phase $\pi+1$. 

Since two clusters $C_1$ and $C_2$ were at least a distance of $R-3G$ apart at time $t''$, applying Lemma \ref{lem:nk:R3Gapart} yields $t-t''>4mu$ which in turn implies that, during $[t'',t]$, there exists at least four phase beginnings.  So, from the beginning of phase $\pi-3$ to the beginning of phase $\pi$, both $C_1$ and $C_2$ were knowledgeable and, by Lemma \ref{lem:nk:gainknowledge}, we obtain that for all $i=0,...,3$, (1) at the beginning of phase $\pi-i$, every node in $C_1$ (resp. $C_2$) knows every other nodes in $C_1$ (resp. $C_2$) that is at most a distance of $R+(L+G+2mu\sigma)(3-i)+2mu\sigma$ from itself, and (2) at any time during phase $\pi-i$, every node in $C_1$ (resp. $C_2$) knows every other nodes in $C_1$ (resp. $C_2$) that is at most a distance of $R+(L+G+2mu\sigma)(3-i)$ from itself.  This shows that at the beginning of phase $\pi+1$, every node that is in $S_1$ (resp. $S_2$) knows every other node that is in $S_1$ (resp. $S_2$) that is at most a distance of $R+3(L+G+2mu\sigma)$ ($>R+2mu\sigma$) from itself.

It remains to show that, at the beginning of phase $\pi+1$, every node that is in $S_1$ (resp. $S_2$) knows every other node that is in $S_2$ (resp. $S_1$) that is at most a distance of $R+2mu\sigma$ from itself.  Let $p$ be a node in $S_1$ (considering the case of $p$ being in $S_2$ will be analogous). We denote the right boundary node of $C_1$ at the beginning of phase $\pi$ as $p_{\pi}$ and the left boundary node of $C_2$ at the beginning of phase $\pi$ as $q_{\pi}$.  Let $X$ be the distance between $p$ and $p_{\pi}$ at the beginning of phase $\pi$. Depending on the value of $X$, we divide into several cases:\\
--(\emph{Case} 1) $X \leq R-L-4mu\sigma$:  We first show that $p$ receives $q_{\pi}$'s broadcast during phase $\pi$.  At the beginning of $\pi$, the distance between $p_{\pi}$ and $q_{\pi}$ can be at most $L+2mu\sigma$.  And, during phase $\pi$, both $p$ and $q_{\pi}$ can move at most a distance of $mu\sigma$ away from each other.  Thus, during phase $\pi$, the distance between $p$ and $q_{\pi}$ can be at most $R$ which implies that $p$ receives $q_{\pi}$'s broadcast.

\begin{figure}[t]
\centering
\includegraphics[scale=0.95]{figures/mergecase1.pdf}
\caption{Proof of Theorem \ref{thm:nk:mergeclusters} (Case 1).}
\label{fig:nk:mergecase1}
\end{figure}

Now, we show that the information contained in $q_{\pi}$'s broadcast message is sufficient enough for $p$ to maintain neighbor knowledge.  We already know that, during phase $\pi$, $q_{\pi}$ knows every node in $S_2$ that is within a distance of $R+3(L+G+2mu\sigma)$ from itself.  Since $p$ receives $q_{\pi}$'s broadcast during phase $\pi$, $p$ will know, at the beginning of phase $\pi+1$, every node in $S_2$ that is within a distance of $R+3(L+G+2mu\sigma)$ from the leftmost node that is in $S_2$.  In worst case, $q_{\pi}$ itself, at the beginning of phase $\pi+1$, can still be the leftmost node in $S_2$ by moving a distance of $mu\sigma$ to the left during phase $\pi$, and node $p$ could move a distance of $mu\sigma$ to the right causing $q_{\pi}$ to be located on the left of $p$ and the distance between $q_{\pi}$ and $p$ to be at most $2mu\sigma$.  Even in this worst case, $p$ will know every node in $S_2$ that is within a distance of $R+3(L+G+2mu\sigma)-2mu\sigma$ ($>R+2mu\sigma$) to its right at the beginning of phase $\pi+1$ (see Figure \ref{fig:nk:mergecase1}).  Hence, the lemma holds for (Case 1).
\\
--(\emph{Case} 2) $R-L-4mu\sigma < X \leq R-2mu\sigma$ : We first show that $p_{\pi}$ receives $q_{\pi-1}$'s broadcast during phase $\pi-1$.  At the beginning of phase $\pi-1$, the distance between $p_{\pi}$ and $p_{\pi-1}$ can be at most $2mu\sigma$ because otherwise $p_{\pi-1}$ will be located to the right of $p_{\pi}$ at the beginning of phase $\pi$.  Also, at the beginning of phase $\pi-1$, the distance between $p_{\pi-1}$ and $q_{\pi-1}$ can be at most $L+4mu\sigma$ since a node in $C_1$ and a node in $C_2$ becomes within a distance of $L$ from each other for the first time during phase $\pi$ (the two nodes that first became within a distance of $L$ from each other during phase $\pi$ can both move at most a distance of $2mu\sigma$ away from each other in two phases).  Since both $p_{\pi}$ and $q_{\pi-1}$ can move at most a distance of $mu\sigma$ away from each other during phase $\pi-1$, the distance between $p_{\pi}$ and $q_{\pi-1}$ can be at most $L+8mu\sigma$ which is less than $R$ by Constraint \ref{nk:constraint3}.  Hence, $p_{\pi}$ receives $q_{\pi-1}$'s broadcast during phase $\pi-1$.  Note that, by Lemma \ref{lem:nk:gainknowledge}, $q_{\pi-1}$ knows every node in $S_2$ that is within a distance of $R+2(L+G+2mu\sigma)$ from the left end of $C_2$ at all times during phase $\pi-1$ and as a result $p_{\pi}$ knows every node in $C_2$ that is within a distance of $R+2(L+G+2mu\sigma)$ from the left end of $C_2$ at the beginning of phase $\pi$.    

%Next, we show that $p$ receives $p_{\pi}$'s broadcast during phase $\pi$.  
The maximum distance between $p$ and $p_{\pi}$ is $R-2mu\sigma$ at the beginning of phase $\pi$.  Both $p$ and $p_{\pi}$ can move at most a distance of $mu\sigma$ away from each other during phase $\pi$.  Thus, the distance between $p$ and $p_{\pi}$ can be at most a distance of $R$ apart from each other during phase $\pi$ which implies that $p$ receives $p_{\pi}$'s broadcast during phase $\pi$.  This means that $p$ can receive $q_{\pi-1}$'s broadcast message indirectly through $p_{\pi}$.  Since $p_{\pi}$ knows every node in $C_2$ that is within a distance of $R+2(L+G+2mu\sigma)$ from the left end of $C_2$ at the beginning of phase $\pi$, Lemma \ref{lem:nk:lose2musigma} tells us that, at all times $t$ during phases $\pi$, $p_{\pi}$ knows every node in $S_2$ that is a distance of at most $R+2(L+G+2mu\sigma)-2mu\sigma$ from the leftmost node in $S$ at time $t$.  Hence, $p$ will know every node in $S_2$ that is within a distance of $R+2(L+G+2mu\sigma)-2mu\sigma$ from the leftmost node in $S_2$ at the beginning of phase $\pi+1$ since $p$ receives $p_{\pi}$'s broadcast during phase $\pi$.

\begin{figure}[tp]
  \centering
  \subfloat[The worst case movement of node $p$ during phase $\pi$.]{\label{fig:nk:mergecase2a}\includegraphics[scale=0.95]{figures/mergecase2a.pdf}}\\
  \subfloat[The worst case movement of nodes $p_{\pi}$ and $q_\pi$ during phase $\pi$.]{\label{fig:nk:mergecase2b}\includegraphics[scale=0.95]{figures/mergecase2b.pdf}}
  \caption{Proof of Theorem \ref{thm:nk:mergeclusters} (Case 2).}
\label{fig:nk:mergecase2}
\end{figure}

In worst case, node $p$ can move at most a distance of $mu\sigma$ to its right during phase $\pi$.  Also, in worst case, $p_{\pi}$ can still be the rightmost node in $S_1$ and move a distance of at most $mu\sigma$ to its right, and similarly $q_{\pi}$ can still be the leftmost node in $S_2$ and move a distance of at most $mu\sigma$ during phase $\pi$. This may cause $q_{\pi}$ to be located on the left of $p_{\pi}$ and the distance between $q_{\pi}$ and $p_{\pi}$ to be at most $2mu\sigma$ in worst case.  So, at the beginning of phase $\pi+1$, node $p$ is located on the left of the leftmost node in $S_2$ (which is $q_{\pi}$ in this case) and the distance between $p$ and the leftmost node in $S_2$ is at least $R-L-7mu\sigma > 0$ (See Figure \ref{fig:nk:mergecase2}).  Since node $p$ knows every node in $S_2$ that is at most a distance of $R+2(L+G+2mu\sigma)-2mu\sigma$ ($>R+2mu\sigma$) from the left most node in $S_2$ at the beginning of phase $\pi+1$ and $p$ is located strictly left to the leftmost node in $S_2$, the lemma holds for (Case 2).\\
--(\emph{Case} 3)  $R-2mu\sigma < X \leq R+4mu\sigma$ :  By a similar argument as in (Case 2), the distance between node between $p_{\pi-1}$ and $q_{\pi-2}$ is at most $L+10mu\sigma$.  By Constraints \ref{nk:constraint2} and \ref{nk:constraint3}, we get $L+10mu\sigma < R$.  Hence, $p_{\pi-1}$ receives $q_{\pi-2}$'s broadcast message during phase $\pi-2$.  Since, by Lemma \ref{lem:nk:gainknowledge}, $q_{\pi-2}$ knows every node in $S_2$ that is within a distance of $R+L+G+2mu\sigma$ from from the left end of $C_2$ at all times during phase $\pi-1$, node $p_{\pi-1}$ knows every node in $S_2$ that is within a distance of $R+L+G+2mu\sigma$ from the left end of $C_2$ at the beginning of phase $\pi$.

At the beginning of phase $\pi$, consider an interval $I_{leader}$ of length $L+2G$ where the left end point of $I_{leader}$ is a distance of $R-2mu\sigma$ to the left of $p_{\pi}$ (see Figure \ref{fig:nk:mergecase3}).  Since the density requirement holds for $C_1$, there exists a leader node $p'$ in $I_{leader}$ at the beginning of phase $\pi$.  We show that $p'$ receives $p_{\pi-1}$'s broadcast message during phase $\pi-1$.  Since $p_{\pi}$ is the right boundary node of $C_1$ at the beginning of phase $\pi$, either $p_{\pi-1} = p_{\pi}$ or $p_{\pi-1}$ is located on the left of $p_{\pi}$ at the beginning of phase $\pi$.  Also, the distance between $p_{\pi}$ and $p_{\pi-1}$ should be at most $2mu\sigma$ at the beginning of phase $\pi$ because otherwise $p_{\pi-1}$ could not have been positioned on the right of $p_{\pi}$ at the beginning of phase $\pi-1$.  So, the distance between $p'$ and $p_{\pi-1}$ can be at most $R$ during phase $\pi-1$ since the distance between $p'$ and $p_{\pi-1}$ is at most $R-2mu\sigma$ at the beginning of phase $\pi$ and both $p'$ and $p_{\pi-1}$ can move at most a distance of $mu\sigma$ in a phase.  Hence, $p'$ receives $p_{\pi-1}$'s broadcast during phase $\pi-1$.  This implies that $p'$ receives $q_{\pi-2}$'s broadcast message indirectly through $p_{\pi-1}$.   

\begin{figure}[tp]
\centering
\includegraphics[scale=0.95]{figures/mergecase3.pdf}
\caption{Proof of Theorem \ref{thm:nk:mergeclusters} (Case 3).}
\label{fig:nk:mergecase3}
\end{figure}

The distance between $p$ and $p'$ can be at most $L+2G+6mu\sigma$ at the beginning of phase $\pi$.  Since both $p$ and $p'$ can move at most a distance of $mu\sigma$, the distance between $p$ and $p'$ during phase $\pi$ can be at most $L+2G+8mu\sigma$.  By Constraint \ref{nk:constraint3}, we get $L+2G+8mu\sigma < R$.  Hence, $p$ receives the broadcast message of $p'$ during phase $\pi$.  This implies that $p$ receives $q_{\pi-2}$'s broadcast message indirectly through $p_{\pi-1}$ and $p'$.  By inductively applying Lemma \ref{lem:nk:lose2musigma}, we obtain that node $p_{\pi-1}$ knows every node in $S_2$ that is within a distance of $R+L+G-2mu\sigma$ (=$R+L+G+2mu\sigma-4mu\sigma$) from the leftmost node in $S_2$ at the beginning of phase $\pi+1$.

Similar to (Case 2), node $p$ can move at most a distance of $mu\sigma$ to its right during phase $\pi$ in worst case.  Also, in worst case, $p_{\pi}$ can still be the rightmost node in $S_1$ and move a distance of at most $mu\sigma$ to its right, and similarly $q_{\pi}$ can still be the leftmost node in $S_2$ and move a distance of at most $mu\sigma$ during phase $\pi$. This may cause $q_{\pi}$ to be located on the left of $p_{\pi}$ and the distance between $q_{\pi}$ and $p_{\pi}$ to be at most $2mu\sigma$ in worst case.  So, at the beginning of phase $\pi+1$, node $p$ is located on the left of the left most in $S_2$ and the distance between $p$ and the leftmost node in $S_2$ is at least $R-5mu\sigma>0$.  It is required for $p$ to only know every node in $S_2$ that is at most a distance of $7mu\sigma$ $(= R+2mu\sigma-(R-5mu\sigma))$ from the leftmost node in $S_2$ at the beginning of phase $\pi+1$.  By Constraints \ref{nk:constraint2} and \ref{nk:constraint3}, we get $7mu\sigma < R+L+G-2mu\sigma$.  Hence, the lemma holds for (Case 3).\\
--(\emph{Case} 4) $X > R+4mu\sigma$ : In this case, the distance between node $p$ and the leftmost node in $S_2$ at the beginning of phase $\pi+1$ is greater than $R+2mu\sigma$ since nodes can only move at most a distance of $mu\sigma$ during a phase.  Hence, during phase $\pi$, there is no need for $p$ to learn nodes in $S_2$.
\end{proof}

\subsection{Merging of an $L$-cluster and a Single Node on a Different Line}

Since we consider a two-dimensional road network, nodes on line $\ell_1$ can merge into an $L$-cluster on line $\ell_2$ through the intersection of $\ell_1$ and $\ell_2$.  In this section, we show how an $L$-cluster maintains neighbor knowledge even after a single node merges into it through an intersection:

\begin{theorem}
\label{thm:nk:mergeclusternode}
Let $t''$, $t$, and $t'$ be times such that $t'' < t < t'$.  Suppose $C_3$ is a $L$-cluster on line $\ell_1$ that has the same set of $\ell_1$-nodes in every instant of time during $[t,t']$.  Also, suppose that the $\ell_1$-nodes in $C_3$ are partitioned into a set $S_1$ and a single node $p$ during $[t'',t)$ such that all nodes in $S_1$ form a $L$-cluster $C_1$ on $\ell_1$ during $[t'',t)$ and node $p$ is an $\ell_2$-node in a $L$-cluster $C_2$ on line $\ell_2$ during $[t'',t)$ where $\ell_1 \neq \ell_2$.  If (1) $C_1$ and $C_2$ are knowledgeable in $[t'',t)$ and (2) the Manhattan distance between node $p$ and the intersection of $\ell_1$ and $\ell_2$ at time $t''$ is at least $R-3G-5mu\sigma$, then $C_3$ is knowledgeable in $[t,t']$.
\end{theorem}
\begin{proof}
Let $t_{\pi}$ be the most recent time when a phase begins that is strictly less than time $t$, and let $\pi$ be the phase that begins at time $t_{\pi}$.  Same as in the proof of Theorem \ref{thm:nk:mergeclusters}, we only need to show that, at the beginning of phase $\pi+1$, every node in $C_2$ knows every other node in $C_2$ that is at most a distance of $R+2mu\sigma$ apart from itself (applying Lemma \ref{lem:nk:stabletoknowledgeable} afterwards proves the theorem).

Since node $p$ was at least a Manhattan distance of $R-3G-5mu\sigma$ apart from the intersection point of lines $\ell_1$ and $\ell_2$ at time $t''$, the difference between $t$ and $t''$ is:
\begin{align}
&(R-3G-5mu\sigma)/\sigma \nonumber \\ 
\geq~ &(2L+3G+8mu\sigma-3G-4mu\sigma)/\sigma \tag{by Constraint \ref{nk:constraint3}} \\
>~ &3mu\sigma. \nonumber
\end{align}
Thus, there are at least three phase beginnings during $[t'',t)$.

By the definition of a $L$-cluster, at time $t$, there exists a node $q$ in $S_1$ where the distance between $p$ and $q$ is at most $L$.  Let $q_{\pi}$ and $q_{\pi-1}$ be leader nodes of the segment where $q$ was in at the beginning of phase $\pi$ and $\pi-1$, respectively.  

We first show that $p$ knows every node in $S_1$ that is at most a distance of $R+2mu\sigma$ from itself at the beginning of phase $\pi+1$.  At the beginning of phase $\pi$, the distance between node $q$ and $q_{\pi}$ can be at most $G$ since they must be in the same segment.  During phase $\pi$, both $q$ and $q_{\pi}$ can move at most a distance of $mu\sigma$.  So, the distance between $q$ and $q_{\pi}$ can be at most $G+2mu\sigma$ during phase $\pi$.  Since the distance between $p$ and $q$ is at most $L$ at some time (time $t$) during phase $\pi$, the Manhattan distance between $p$ and $q$ during phase $\pi$ can be at most $L+2mu\sigma$.  
%Note that the movement of node $q$ contributes in calculating upperbounds on both $dist_{M}(p,q)$ and $dist_{E}(q,q_{\pi})$, however, the direction of node $q$'s movement in one case is opposite to the other.  
Hence, the Manhattan distance between $p$ and $q_{\pi}$ during phase $\pi$ can be at most $L+G+4mu\sigma$ which implies that $p$ receives $q_{\pi}$'s broadcast message during phase $\pi$ (since $L+G+4mu\sigma < R$ by Constraint \ref{nk:constraint3}).  By Lemma \ref{lem:nk:gainknowledge}, node $q_{\pi}$ knows every node in $S_1$ that is at most a distance of $R+2(L+G+2mu\sigma)+2mu\sigma$ from itself at the beginning of phase $\pi$ and, since $p$ receives $q_{\pi}'s$ broadcast message during phase $\pi$, $p$ will know every node in $S_1$ that is at most a distance of $R+2(L+G+2mu\sigma)$ from node $q_{\pi}$ at all times during phase $\pi$. Hence, $p$ will know every node within a distance of $R+2mu\sigma$ at the beginning of phase $\pi+1$ since $R+2(L+G+2mu\sigma)-(L+G+4mu\sigma) > R+2mu\sigma$ (by Constraint \ref{nk:constraint2} and the assumption of $L \geq G$).

The remaining is to show that, at the beginning of phase $\pi+1$, every node $q'$ in $S_1$ that is at most a distance of $R+2mu\sigma$ from node $p$ knows $p$. Let $p_{\pi-2}$ be the leader node of the segment where node $p$ was in at the beginning of phase $\pi-2$.  Since $L$-cluster $C_2$ is knowledgeable at the beginning of phase $\pi-2$ and $L\geq G$, node $p_{\pi-2}$ knows $p$ at the beginning of phase $\pi-2$.  We show that $q_{\pi-1}$ receives $p_{\pi-2}$'s broadcast message during phase $\pi-2$.  Since the Manhattan distance between nodes $p$ and $q$ becomes at most $L$ at some time (time $t$) during phase $\pi$,  the Manhattan distance between $p$ and $q$ can be at most $L+6mu\sigma$ during phase $\pi-2$ (a node can move at most a distance of $3mu\sigma$ during three phases).  The distance between nodes $p$ and $p_{\pi-2}$ can be at most $G+2mu\sigma$ during phase $\pi-2$ since $p$ and $p_{\pi-2}$ is in the same segment at the beginning of phase $\pi-2$.  The distance between nodes $q$ and $q_{\pi-1}$ can be at most $G+2mu\sigma$ during phase $\pi-2$ since $q$ and $q_{\pi-1}$ is in the same segment at the beginning of phase $\pi-1$.  Hence, during phase $\pi-2$, the Manhattan distance between $p_{\pi-2}$ and $q_{\pi-1}$ can be at most $L+2G+10mu\sigma < R$ (by Constraint \ref{nk:constraint2}, Constraint \ref{nk:constraint3}, and the assumption of $L \geq G$) which implies that $q_{\pi-1}$ receives $p_{\pi-2}$'s broadcast message and gets to know $p$ during phase $\pi-2$.

Since nodes $q$ and $q_{\pi-1}$ are in the same segment at the beginning of phase $\pi-1$, the distance between $q$ and $q_{\pi-1}$ can be at most $G+2mu\sigma$ during phase $\pi-1$.  Node $q_{\pi-1}$ is a leader node which broadcasts during phase $\pi-1$.  Hence, at the beginning of phase $\pi$, every node that is at most a distance of $R-G-2mu\sigma$ apart from node $q$ will know $p$ by receiving $q_{\pi-1}$'s broadcast message.

Consider an interval $I_{leader}$ of length $L+2G$ on line $\ell_1$ at the beginning of phase $\pi$ where (1) it is located on the right of node $q$ (considering the case of $I_{leader}$ being located on the left of $q$ will be analogous) and (2) the distance between $q$ and the right end of $I_{leader}$ is $R-G-2mu\sigma$ (See Figure \ref{fig:nk:mergenodea}).  Suppose, at the beginning of phase $\pi$, the distance between $q$ and the rightmost node in $S_1$ is greater than $R-G-2mu\sigma$ (otherwise, every node in $S_1$ that is located on the right of $q$ at the beginning of phase $\pi$ already knows $p$).  Then, since the density requirement holds in $C_1$ at the beginning of phase $\pi$, there exists a leader node $q'$ in $I_{leader}$ at the beginning of phase $\pi$.  Also, node $q'$ knows $p$ since it is at most a distance of $R-G-2mu\sigma$ apart from $q$ at the beginning of phase $\pi$.  We consider the worst case movement of $q$ and $q'$ during phase $\pi$ such that the least number of nodes located on the right of $q$ learns about $p$.  The worst case movement will be node $q$ moving a distance of $mu\sigma$ to its right and node $q'$, which is located at the right end of $I_{leader}$ at the beginning of phase $\pi$, moving a distance of $mu\sigma$ to its left during phase $\pi$.  Note that $q'$ broadcasts during phase $\pi$ since it is a leader node (See Figure \ref{fig:nk:mergenodeb}).  Hence, at the beginning of phase $\pi+1$, every node that is at most a distance of 
\begin{align}
&R-G-2mu\sigma -(L+2G+2mu\sigma) + R \nonumber \\
=~ &2R-L-3G-4mu\sigma \nonumber \\
\geq~ &R-L-3G-4mu\sigma + (2L+3G+8mu\sigma) \tag{by Constraint \ref{nk:constraint3}} \\
=~ &R+L+4mu\sigma \nonumber
\end{align}
from $q$ knows $p$.

\begin{figure}[tp]
  \centering
  \subfloat[Interval $I_{leader}$ (beginning of phase $\pi$).]{\label{fig:nk:mergenodea}\includegraphics[scale=0.95]{figures/mergenodea.pdf}}\\
  \subfloat[The worst case movement of nodes $q$ and $q'$ during phase $\pi$.]{\label{fig:nk:mergenodeb}\includegraphics[scale=0.95]{figures/mergenodeb.pdf}}
  \caption{Proof of Theorem \ref{thm:nk:mergeclusternode}.}
\label{fig:nk:mergenode}
\end{figure}

We already know that the distance between node $p$ and $q$ at the beginning of phase $\pi+1$ can be at most $L+2mu\sigma$.  Since $(R+L+4mu\sigma)-(L+2mu\sigma) = R+2mu\sigma$, every node in $S_1$ that is at most a distance of $R+2mu\sigma$ from $p$ at the beginning of phase $\pi+1$ knows $p$.  Hence, the Theorem is proven. 
\end{proof}

\section{Discussion}
\label{sec:nk:discuss}
In this section, we address the issue of obtaining initial neighbor knowledge, 
and discuss how to relax the assumption that every node knows its entire 
future trajectory. We also discuss practical values for the parameters. 

Up till now we have focused on \emph{maintaining} neighbor knowledge as nodes move 
in and out of each other's broadcast range. If nodes possess some amount of 
neighbor knowledge initially, then our solution allows nodes to keep this 
knowledge up-to-date. Specifically, we have assumed that when nodes wake 
up initially, they already possess knowledge about other nodes that are 
within a Manhattan distance of $R+2mu\sigma$.  
In this section we address a special case of this problem of gaining 
initial knowledge. 
We use the gossiping (all-to-all communication) 
algorithm in \cite{GPPR07} as a black box.

For simplicity, we consider the case of the one-dimensional 
line. We assume that nodes start up at the same time and 
remain within their original segment for some period of time 
which we call the initialization phase. We also assume that 
there is an upper bound $v$ on the number of nodes present 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
within one segment during the initialization phase 
and this upper bound is known to all nodes.
This is because the algorithm given in \cite{GPPR07}
requires that all nodes know the linear upper bound on the number of 
nodes participating in the algorithm.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Note that $v$ may be much smaller than the total number of nodes 
in the entire network, which is $n$ ($v<<n$). 
Note also that the nodes within one segment form 
a clique, since they are all within each other's broadcast range.

The initialization phase is divided into two parts. 
The first part is further divided into a total of $m$ periods.
During period $i$, we run an initialization protocol in segments of color $i$,
while nodes in other segments listen.   
This initialization protocol is based on the algorithm for gossip in undirected graphs with unknown
topology presented in \cite{GPPR07}. This algorithm requires 
$O(v \log^2 v \log^2 n)$ time slots. Hence, each of the $m$ 
periods in the first part of the initialization phase has $O(v \log^2 v \log^2 n)$ time slots.  
This algorithm performs gossiping in graphs with arbitrary 
topologies. 
Therefore, it may be used for a clique, which is the topology formed by nodes in one segment.
Nodes also do not require collision detection capabilities 
or any previous knowledge of the neighborhood in order to run this algorithm. 
Furthermore, it is assumed in \cite{GPPR07} that node ids come from a
domain of size $n$ and the actual number of nodes participating in 
the algorithm may be smaller than $n$. 
This assumption fits in with our model since there can be at most $v$ nodes in one segment 
participating in one period and $v<<n$.

In period $i$ of part one of the initialization phase, nodes in segments of color $i$ run this gossiping algorithm from \cite{GPPR07} and collect each other's ids and trajectories.  Note that while the nodes of a certain segment (say $s$) run the algorithm, nodes in neighboring segments which are contained within distance $R-G$ of $s$ successfully receive the transmissions by the nodes in segment $s$.  Hence, after $m$ periods, all nodes have received the ids and trajectories of nodes in segments contained within distance $R-G$ of their own segment.  However, we require knowledge about nodes within a distance of $R+2mu\sigma$.  This can be easily achieved in the second part of the initialization phase.
This part of the initialization phase is divided into two cycles. Each cycle consists of $m$ time slots.  During time slot $i$ of both cycles, a leader node from each segment of color $i$ simply transmits its entire id and trajectory list.  The leader node is the node with the smallest id in the segment.

In order to see why this achieves the desired initial knowledge consider the following.  The exact number of segments entirely contained within distance $R-G$ of a segment is given by $\lfloor(R-G)/G\rfloor$. Consider a segment $s$ as shown in Figure \ref{fig:nk:initpart2}. After part one all nodes in $s$ know the ids and trajectories of all other nodes in segments within distance $(\lfloor(R-G)/G\rfloor)G$.  Consider an interval $I_{leader}$ of length $L+2G$ that is located on the right side of $s$ (analogous arguments hold for the left side of $s$) where the distance between the left end of $s$ and the right end of $I_{leader}$ is $R$. Due to the density assumption, during the initialization phase it is guaranteed that there is at least one leader node present in $I_{leader}$. In the worst case this leader node may remain at the left end of $I_{leader}$ for the entire duration of the initialization phase.  When this leader node broadcasts in its time slot during cycle one of part two, it will broadcast the ids and trajectories of all nodes within distance $(\lfloor(R-G)/G\rfloor)G$ of its segment, which it has collected during part one.  All nodes in segment $s$ will receive the leader node's broadcast successfully since the leader node is within distance $R$ of all nodes in $s$. Therefore, by the end of cycle one of part two all nodes in $s$ will know the ids and trajectories of all other nodes within distance $D_{cycle1}=R-G-(L+2G)+(\lfloor(R-G)/G\rfloor)G$.

\begin{figure}[tp]
\centering
\includegraphics[scale=0.95]{figures/initpart2.pdf}
\caption{Part two of the initialization phase.}
\label{fig:nk:initpart2}
\end{figure}

Now, in cycle two the same leader node (which stays in its original segment during the entire initialization phase) transmits the ids and trajectories of nodes within $D_{cycle1}$ of itself, which it has learnt during cycle one.  Therefore, by the end of cycle two of part two all nodes in $s$ will know the ids and trajectories of all other nodes within distance $R-L-3G+D_{cycle1}$. Assume that $L \geq G$ as in Section \ref{sec:nk:cluster}. Then we have the following:
\begin{align}
&R-L-3G+D_{cycle1} \nonumber \\
=~&R-L-3G+(R-L-3G+(\lfloor(R-G)/G\rfloor)G) \nonumber \\
\geq ~&2R-2L-6G+((R-G)/G-1)G \nonumber \\
=~&3R-2L-8G \nonumber \\
\geq~&R-2L-8G+2(2L+3G+8mu\sigma) \tag{by Constraint \ref{nk:constraint3}} \\
%=~&R+2L-2G+16mu\sigma \nonumber \\
>~&R+2mu\sigma. \tag{since $L\geq G$}
\end{align}
Hence, by the end of part two of the initialization phase all nodes in $s$ will know the ids and trajectories of all other nodes within distance $R+2mu\sigma$.


The challenging part of gaining initial knowledge is that 
the total number of unique ids present in the entire network may be very large, and only a few of these ids 
belong to nodes in one segment (recall that $v<<n$). Learning about which of these ids 
belong to neighbors deterministically, without collision detection, may take a long time.    
However, the above protocol is deterministic and efficient, since it is subquadratic in the maximum number of nodes
in one segment and only polylogarithmic in the total number of unique ids that may be present in the entire network.  

Another important assumption that we have made is that nodes initially know their entire future trajectory. 
Instead of having such a strong assumption, in each round, the time slots that are not being 
used by our solution may be used for an intra-segment communication protocol, so that nodes may 
transmit their trajectory information to the current leader of the segment periodically. 
Hence, it may be sufficient for nodes to know their trajectories for only a short 
interval of time in the future.  Such an intra-segment communication protocol may require an upper 
bound on the number of nodes that can occupy a segment at a particular instant of time. This is because
only a limited number of time slots will be available in each round.

It is not hard to find practical values for the parameters that satisfy all constraints:  We let $R$ and $R'$ to be 250 meters and 550 meters, respectively, which are typical values for IEEE 802.11 (\cite{FZLLZG03,NHJ05}).  Let one time slot duration be 600 microseconds which is slightly greater than the GSM (Global System for Mobile Communications) time slot duration 577 microseconds \cite{3GPP0502}.  Also, let $G=40$ meters, $m=30$ colors, and $u=6$ milliseconds which corresponds to 10 time slots.  Then, we can allow the upper bound on the node speed to be $\sigma < 108$ kilometers/hour and the density parameter to be $L=40$ meters. 

%Text goes here.

%\section{New Section}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{figure}[H]
%\centering
%\includegraphics[scale=.50]{figures/Penguins.jpg}
%\caption{TAMU figure - This is an example of a long figure title.  Figure titles need to be single-spaced within and double spaced between in the list of figures.}
%\label{fig:nk:landscapepenguins}
%\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsection{Subsection}
%\begin{table}[H]
%\centering
%\caption{This is a table template - This is an example of a long table title.  Table titles need to be single-spaced within and double spaced between in the list of tables.}
%\begin{tabular}{|l|c|c|c|c|c|}
%\hline
%Product & 1 & 2 & 3 & 4 & 5\\
%\hline
%Price & 124.- & 136.- & 85.- & 156.- & 23.-\\
%Guarantee [years] & 1 & 2 & - & 3 & 1\\
%Rating & 89\% & 84\% & 51\% & & 45\%\\
%\hline
%\hline
%Recommended & yes & yes & no & no & no\\
%\hline
%\end{tabular}
%\label{tab:template1}
%\end{table}


%\subsection{Subsection}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{figure}[H]
%\centering
%\includegraphics[scale=.50]{figures/Sunset.jpg}
%\caption{Sunset figure}
%\label{fig:nk:sunset-fig2}
%\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsubsection{This is a subsubsection}
%\begin{table}[H]
%\centering
%\caption{This is a table template - This is an example of a long table title.  Table titles need to be single-spaced within and double spaced between in the list of tables.}
%\begin{tabular}{|l|c|c|c|c|c|}
%\hline
%Product & 1 & 2 & 3 & 4 & 5\\
%\hline
%Price & 124.- & 136.- & 85.- & 156.- & 23.-\\
%Guarantee [years] & 1 & 2 & - & 3 & 1\\
%Rating & 89\% & 84\% & 51\% & & 45\%\\
%\hline
%\hline
%Recommended & yes & yes & no & no & no\\
%\hline
%\end{tabular}
%\label{tab:template1-2}
%\end{table}
%\section{Another Section}
