% $Id: impediments.tex 20822 2010-01-03 14:28:25Z gokhale $
\section{Impediments to Real-time and Reliable Information Dissemination}
\label{sec:impediments}

Section~\ref{sec:relwork} outlined how prior work has studied
individual issues, such as the challenges stemming from the MAC layer
of 802.11p, in isolation.  
% Andy, rather than saying ``our goal'' can you please phrase this
% stuff in terms of what this section covers?
%DONE
This section describes experiments conducted to better understand
known challenges and uncover hitherto unknown challenges from an
integrated perspective of the physical and cyber artifacts of ITS for
the following reasons: 

\noindent\textbf{1. Physics of the system.} Since vehicles are mobile,
the vehicular networks they create among themselves and/or with the
infrastructure elements are \emph{ad hoc}.  The temporal (\emph{i.e.},
lifespan of the network) and spatial (\emph{i.e.}, size and topology)
properties of such network are determined by multiple factors
including the speed, direction, and density of the vehicles, as well
as the wireless radio transceiver power, frequency, and
signal-to-noise ratio.  These factors impact timeliness and
reliability in information dissemination.

\noindent\textbf{2. Vagaries of the cyber infrastructure.}  Protocols
at the different layers of the network stack (\emph{e.g.}, the five
layer TCP/IP stack) significantly impact the timeliness and
reliability of information dissemination.  For example, the MAC layer
requires address resolutions using ARP; the network layer requires
addressing and routing to work despite handoffs.  Likewise, transport
layer protocols (such as TCP) involve sophisticated mechanisms for
retransmissions, flow control, and congestion control.

It is important to obtain an integrated perspective of the physical
and cyber-imposed challenges so that practical solutions that will
realize the vision of ITS can be conceived.  To obtain such a
perspective we conducted a number of simulations emulating a traffic
system.  Lack of open ITS testbeds motivated us to choose simulation
as an alternative to conduct our study.

\subsection{Simulation Framework}
\label{sec:sim_engine}
\vspace{-.05in}

The experiments in this paper use OMNeT++ (\url{www.omnetpp.org}),
which is an extensible, modular, component-based, C++ simulation
library and framework, with an Eclipse-based IDE and a graphical as
well as command-line runtime environment.  Domain-specific
functionality (\emph{e.g.}, support for simulation of communication
networks, queuing networks, performance evaluation) is provided by
model frameworks, developed as independent projects.

OMNeT++ provides a component architecture for models.  Basic
components (called simple modules) are declared in a high level
language called the network definition (NED) and its logic is
programmed in C++.  Individual components can be assembled into larger
components and models by declaring them as compound modules in the NED
file.  Modules can communicate with each other via messages.

OMNeT++ has extensive GUI support, and due to its modular
architecture, the simulation kernel (and models) can be embedded
easily into applications.  Due to its generic architecture OMNeT++ can
be used in various problem domains, such as modeling of wired and
wireless communication networks, protocol modeling, modeling of
multiprocessors and other distributed hardware systems, validating of
hardware architectures, evaluating performance aspects of complex
software systems, and any other domain where a discrete event
simulation approach is suitable.

For the evaluations in this paper, we leverage the INETMANET framework
also available from the OMNeT++ web portal.  The INETMANET framework
contains support for both wired and wireless networks including IPv4,
IPv6, TCP, UDP protocol implementations, and several application
models.  The framework includes an MPLS model with RSVP-TE and LDP
signalling.  Link-layer support includes PPP, Ethernet and various
flavors of 802.11. Static routing can be set up using network
autoconfigurators, or one can use routing protocol implementations.

Mobile ad hoc networking protocols, such as AODV, are also available
in addition to many different kinds of mobility models including
linear, random, mass and circular mobility.

\subsection{Experiment Setup}
\label{sec:setup}
\vspace{-.1in}

To simulate a scenario in OMNeT++, developers must describe the
modules in a NED file.  Configurations that never change can be
specified inside the NED files.  Any configuration parameters whose
values can vary must be specified at initialization-time of the
simulation through initialization files.

For experiments that involve mobility, the INETMANET framework's
ChannelControl module requires the size of the region (called
playground) to be specified.  We used a playground of size $5,000
meters X 1,000 meters$ for our experiments.  Since vehicles do not
move in random directions but follow the road, we limited our
simulations to scenarios comprising straight roads, such as those
found on highways. This was obtained using the LinearMobility module
from INETMANET.

The INETMANET framework does not provide an implementation of the IEEE
802.11p protocol since the latter is still not a standard.  To mimic
802.11p as closely as possible, we chose the standard 802.11a
implementation with a 5.9 GHz frequency range and a channel bit rate of
6 Mbps.  The radio transceiver's sensitivity was set to -85 dBm while
the thermal noise threshold was kept at -110 dBm.  These parameters
help the simulator to distinguish a valid packet reception from noise.
The signal to noise ratio threshold was set to 4 dB.

In INETMANET the computation of the distance for wireless signal
propagation and power of received signal is based on the Friis
transmission equation~\cite{Friis_Xmit:46}.  Since this technique
works in idealized conditions, the simulation results may deviate
somewhat from reality.  Since we are interested in understanding the
general trends and challenges, however, this limitation is acceptable
for our work.

We narrowed the scope of our simulations to V2I communications where
infrastructure elements, such as road side units (RSUs), mediate
communication between vehicles or vehicles to internet-based services.
Our motivation to restrict the study stems from the fact that the ITS
problem space is very large, which argues for narrowing the scope of
the integrated cyber- and physics-imposed challenges.

To understand the combined impact of both the cyber- and
physics-imposed challenges, we developed a series of simulation
scenarios that help to elicit these challenges.  All our simulations
assume straight roads without any obstacles, such as buildings, hills
and trees.

\subsection{Impediments Due to Road Side Unit Association}
\label{sec:RSU_chal}

\noindent\textbf{Context.} In 802.11 networks a node acquires network
connectivity only when it gets associated with an access point (AP).
In ITS, vehicles involved in V2I communications must be associated
with a RSU, which serves as the AP.  Association with an AP in 802.11
networks involves complex activities.  At the physical layer, the
radio transceiver on the mobile node (in our case the vehicle), which
operates in the 802.11 STA mode (\emph{i.e.}, station mode), can
choose to actively scan the radio channel to discover an AP.  At the
same time, any 802.11 device acting in the AP mode (\emph{i.e.},
access point) periodically broadcasts a beacon frame which can be
received by any node in the radio range that is tuned to the same
channel.

Whenever either the mobile node or the AP discovers the other entity,
complex MAC layer signaling takes place that involves first an
authentication request (AUTH) by the node to the AP followed by an
acknowledgment from the AP, only if the security credentials are
acceptable.  This is followed by an association request (ASSOC) by the
node and a grant message by the AP.  Once the node is associated with
the AP, the node stores the AP's MAC address for any subsequent V2I
communications.

\noindent\textbf{Objective.}  Since the node is mobile, with passage
of time the received power at the node's radio transceiver will
eventually fall below the sensitivity value at which point the RSU is
considered out-of-range.  Our goal is to identify the impact of
vehicular speed, density of vehicles, and the power of the wireless
radio -- all physical factors -- on the time it takes to discover the
RSU, associate with it, and ultimately lose contact with it.
Determining these times are important since they determine the window
of opportunity for the middleware and application layer -- all cyber
artifacts -- to schedule data communication operations, which are key
to realize the different kinds of ITS applications.

\subsubsection{Scenario 1: Impact of Vehicle Speed on RSU Association} 
\label{sec:speed_impact_rsu_assoc}

\noindent\textbf{Experiment - Varying the speed of a single vehicle.}
The first experiment comprises a single vehicle whose speed can be
configured per iteration of the experiment.  This special case of a
single vehicle is used to understand the impact of speed without the
impact of collisions arising from multiple vehicles contending for the
shared channel.

Figure~\ref{fig:Scan4AP} shows our simulation setup.  A RSU
(\emph{i.e.}, AP) is placed on the playground at coordinates $(500,
100)$.  A single vehicle moves east (\emph{i.e.}, from left to right)
starting from coordinates $(200,105)$.  The speed of the vehicle is
varied between 15 MPH (miles per hour) and 75 MPH.  The higher speeds
represent typical speed limits on interstates in USA.  The lower
speeds represent speeds during rush hour traffic or speeds on entry
and exit ramps.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.55\columnwidth]{Scan4AP_Run}
  \bfcaption{Discovering the Road Side Unit}
  \label{fig:Scan4AP}
\end{figure}

Two iterations of the experiment were conducted for each speed
value: once using active scanning by the vehicle for a RSU and once
relying solely on beaconing from the RSU.  The wireless radio
transceiver power for both the RSU and vehicle is set to 5 mW.

%%%% Reduced due to lack of space
\iffalse
\noindent\textbf{Observations:}

Figures~\ref{fig:Speed_1_Veh_wActScan_STATE}
and~\ref{fig:Speed_1_Veh_NoActScan_STATE} show for the active scanning
and beaconing only mechanisms, respectively, the times it takes for
the vehicle from its starting point to discover the RSU, authenticate
with it, associate with it, and ultimately lose contact with it.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.7\columnwidth]{Speed_1_Veh_wActScan_STATE}
  \bfcaption{RSU Relationship for Single Vehicle with Varying Speed
    and Active Scanning}
  \label{fig:Speed_1_Veh_wActScan_STATE}
\end{figure}

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.7\columnwidth]{Speed_1_Veh_NoActScan_STATE}
  \bfcaption{RSU Relationship for Single Vehicle with Varying Speed
    and Beaconing Only}
  \label{fig:Speed_1_Veh_NoActScan_STATE}
\end{figure}

The figures confirm our intution that higher speeds will
result in faster discovery of the RSU but also a rapid disconnection
from the RSU.  The figures also reveal negligible difference between
the two mechanisms for RSU association as shown in
Figure~\ref{fig:ActScan_Beacon_Diff}.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.7\columnwidth]{AssocTimeComparison}
  \bfcaption{Performance Difference between Active Scanning and Beaconing}
  \label{fig:ActScan_Beacon_Diff}
\end{figure}
\fi

\noindent\textbf{Observations.}
Figure~\ref{fig:Speed_1_Veh_wActScan_STATE} shows the time taken for
the vehicle from its starting point to discover the RSU, authenticate
with it, associate with it, and ultimately lose contact with it for
the active scanning mechanisms.  This figure confirms our intution
that higher speeds will result in faster discovery of the RSU but also
a rapid disconnection from the RSU.  The beacon-only approach reveals
negligible difference in performance compared to the active scan
approach.  The results are not shown due to lack of space.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.7\columnwidth]{Speed_1_Veh_wActScan_STATE}
  \bfcaption{RSU Relationship for Single Vehicle with Varying Speed
    and Active Scanning}
  \label{fig:Speed_1_Veh_wActScan_STATE}
\end{figure}

We argue that with increasing number of vehicles on the road, the
bandwidth of the channel will have to be shared between both the
scan requests (which each vehicle transmits) and beacons
(which are broadcasted by the RSU).  Hence, in the rest of the
experiments we use only the beaconing approach.\footnote{The 802.11p
  standard proposes to drop the association process altogether but
  instead relies on wildcard AP addresses.  This approach will require
  active scanning by the node but no beaconing by the AP.}

\subsubsection{Scenario 2: Impact of Radio Power on RSU Association} 
\label{sec:power_impact_rsu_assoc}

\noindent\textbf{Experiment - Varying the radio transceiver power.}
The second experiment maintains a constant speed of 60 MPH for the
vehicle but varies the power level of the wireless radio transceivers
on the vehicle and the RSU.  Our aim is to determine the impact of
power levels on the time window available for data communication via
the RSU.  The power level used in each iteration was varied between 5
mW and 50 mW.  The starting coordinates of the vehicle was the same as
before, however, the RSU is now placed at coordinates $(1500, 100)$ to
ensure that the vehicle is out of range of the RSU at the start of the
simulation even for the higher power levels.

\noindent\textbf{Observations.}
Figure~\ref{fig:Power_1_Veh_NoActScan_STATE} depicts the impact of
different power levels on the time it takes to discover the RSU,
authenticate with it, associate with it, and ultimately lose
connection with it.  The results are in tune with our intuition that
the higher the power level, the earlier is the RSU discovered and
later is the connection lost.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.7\columnwidth]{Power_1_Veh_NoActScan_STATE}
  \bfcaption{RSU Relationship for Single Vehicle with Varying Radio Power}
  \label{fig:Power_1_Veh_NoActScan_STATE}
\end{figure}

These results are important since they provide insights into how
higher layer cyber solutions can make runtime adaptations to the radio
power to improve reliability and timeliness of information
dissemination. 

\subsubsection{Scenario 3: Impact of Vehicular Density on RSU Association} 
\label{sec:density_impact_rsu_assoc}

\noindent\textbf{Experiment - Varying the number of vehicles.}  In the
third experiment we created a scenario representing two-way traffic.
The highway comprises two lanes each in both directions.  The RSU is
assumed to be placed on the median. We varied the number of vehicles
heading east-to-west and west-to-east so that platoons of vehicles are
formed in both directions.  The platoon size was varied from one
vehicle in each platoon to 16 vehicles in each platoon for a total of
32 vehicles.

Figure~\ref{fig:Platoon} shows our experimental setup with one vehicle
each on either side.  The speeds of all vehicles are maintained at 60
MPH.  Although it is unrealistic to expect all vehicles in a platoon
to travel at exactly the same speeds, we chose this scenario since it
reflects a worst case scenario where due to the same speed, each
vehicle will demonstrate the same pattern for association with the
RSU.  We surmise that this situation will result in higher number of
collisions in the authentication and association messages (and data
messages) leading to unpredictability in the association time (and
application-level data throughput).

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.55\columnwidth]{TwowayTraffic_Run}
  \bfcaption{Twoway Traffic with Platoons}
  \label{fig:Platoon}
\end{figure}

Two vehicles in neighboring lanes are separated by 5 meters.  Thus,
the lead vehicle moving east in the inner lane starts at coordinates
$(200, 105)$ while the one in the outer lane starts at $(200, 110)$.
Each following vehicle is separated from the vehicles in the front
also by 5 meters.  An exactly symmetric arrangement exists for the
westward moving traffic.

\noindent\textbf{Observations.}
Figure~\ref{fig:Speed_N_Veh_NoActScan_STATE} shows the variation in
the time it takes for the lead vehicle moving east to discover the
RSU, authenticate with it, associate with it, and then disconnect from
it as the size of the platoon increases from 2 to 32 (1 to 16 in each
direction).  The jitter in the times are the result of contention for
the shared channel and resulting collisions.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.7\columnwidth]{Speed_N_Veh_NoActScan_STATE}
  \bfcaption{RSU Relationship for a Platoon with Varying Radio Power}
  \label{fig:Speed_N_Veh_NoActScan_STATE}
\end{figure}


\subsection{Impediments due to Higher Layer Protocols}
\label{sec:protocol_impact}

\noindent\textbf{Context.}  To realize any useful application in ITS,
simply discovering a RSU is not enough.  Data must be communicated
between vehicles and other network-based services.  For example,
real-time traffic updates need to flow from servers based in the wired
Internet to the vehicles.  On the other hand, applications, such as
periodic transmission of health status of a vehicle, must send data
from a vehicle to a network-based server.  All such communication is
mediated through the RSUs.

The ITS applications and their QoS will require leveraging traditional
cyber infrastructure including middleware; network protocols, such as
TCP and UDP for transport-level end-to-end properties; IP for
addressing and routing; and 802.11 MAC for transmitting the physical
frames over the wireless channel.   

\noindent\textbf{Objective.}  The physics of the system (\emph{e.g.},
speed, density, radio power) impact the performance of traditional
cyber technologies, such as TCP, IP and 802.11 MAC.  For example, a
disconnection from a RSU due to mobility creates multiple problems at
every higher layer protocol of the cyber infrastructure.  TCP will
experience packet loss and resort to retransmissions.  It is
imperative to study the effects of such retransmissions on
application-level throughput and message latencies, particularly, when
the density of vehicles in a region increases.

At the IP level, addressing and routing are key issues that must be
handled when a vehicle is handed over from one RSU to the other.
Handoffs may impact the timeliness and reliability of information
dissemination.  It is necessary to understand the impact of handoffs
and determine how promising techniques, such as routing in delay
tolerant networks~\cite{Jain_DTN:04}, may need to be enhanced for ITS.

\subsubsection{Scenario 1: Impact of Speed and Time Window on
  Application Data Communication}  
\label{sec:window_impact_app_comm}

\noindent\textbf{Experiment - Request-response between vehicle and
server.}  Figure~\ref{fig:Scan4APwTCP} shows our experiment setup.  A
wired network-based server is shown directly attached to the RSU's
LAN-based interface.  The RSU simply relays packets between the
wireless and wired network.  The server is directly attached to the
RSU to eliminate additional impact in our measurements due to routing
and switching.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.55\columnwidth]{Scan4APwTCP_Run}
  \bfcaption{Data Communication Mediated by a RSU}
  \label{fig:Scan4APwTCP}
\end{figure}

In the experiment, the vehicle opens up a TCP connection with the
server.  Every request is 1 Kbytes while the response is 5 Kbytes.  A
request will fit in a single MAC-layer (whose maximum transfer
unit is approximately 1,500 bytes) frame while multiple frames will be
needed for the response.  Trying to open up a connection to the server
even before associating with a RSU is useless.  Hence, using the
timings we measured in our earlier experiment (see
Section~\ref{sec:speed_impact_rsu_assoc}) we ensured that the
application opens a connection to the server right after the RSU is
associated.

\noindent\textbf{Observations.}  We observed that the SYN TCP
connection establishment packet triggers an ARP request as shown in
Figure~\ref{fig:SYN_n_ARP}.  Even with a UDP communication, an ARP
request must be made.  ARP is needed by the vehicle because it needs
to determine the destination MAC address to which it must relay the
message in order to reach the network-based server.  Naturally, the
ARP overhead further reduces the time window of communication with RSU
available to a vehicle. 

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.7\columnwidth]{SYN_n_ARP}
  \bfcaption{Address Resolutions Initiated by TCP Packet}
  \label{fig:SYN_n_ARP}
\end{figure}

Figure~\ref{fig:speed_vs_packets} shows the number of packets received
successfully at the application level by the vehicle for different
speeds.  Since it is already known that higher speeds will have a
smaller window of time, the number of packets received will also be
smaller.  Note that these measurements include TCP-level effects, such
as congestion control and retransmissions, if any.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.6\columnwidth]{Speed_vs_Packets}
  \bfcaption{Packets Delivered for Different Speeds}
  \label{fig:speed_vs_packets}
\end{figure}

These results are important since higher level cyber artifacts, such
as middleware and application level protocols, as well as tools for
real-time scheduling can determine how best to schedule data
transmissions and what message sizes are appropriate to ensure
retrieval of information in the available time window.

\subsubsection{Scenario 2: Impact of Density on Application Data Communication}
\label{sec:desnity_impact_app_comm}

\noindent\textbf{Experiment - Varying the platoon size.}  We extended
the experimental setup shown in Figure~\ref{fig:Scan4APwTCP} by
including the two-way traffic and platoon of vehicles described in
Section~\ref{sec:density_impact_rsu_assoc}.  The goal is to estimate
the impact of collisions on application-level data throughput.  For
this experiment we kept the speed of all vehicles constant at 60 MPH.

\noindent\textbf{Observations.}  Figure~\ref{fig:packets_vs_platoon}
shows the minimum, average, and maximum number of packets received by
any vehicle in the platoon.  With increasing density of vehicles, the
number of packets received starts decreasing.  After about 16 vehicles
overall in the platoon (8 on each side), some vehicles do not even
receive any packet.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.6\columnwidth]{Packets_vs_PlatoonSize}
  \bfcaption{Packets Delivered with increasing Platoon Size}
  \label{fig:packets_vs_platoon}
\end{figure}

The behavior in Figure~\ref{fig:packets_vs_platoon} can be attributed
to increasing number of MAC layer collisions and resulting
retransmissions by TCP, as shown in
Figure~\ref{fig:collisions_vs_platoon}.  The figure shows that the
data throughput is acceptable until about 14 vehicles in the platoon
since the number of collisions and jitter remains low.
\begin{figure}[htb]
  \centering
  \includegraphics[width=0.6\columnwidth]{Collisions_vs_PlatoonSize}
  \bfcaption{MAC-level Collisions with increasing Platoon Size}
  \label{fig:collisions_vs_platoon}
\end{figure}

\subsubsection{Scenario 3: Impact of Handoffs between RSUs on
  Application Data Communication}
\label{sec:handoff_impact_app_comm}

\noindent\textbf{Experiment - Single vehicle handoff.}  In our final
experiment we introduced multiple RSUs so that the vehicle can be
handed over from one RSU to other as the vehicle moves out of range of
one RSU and into that of the other.
Figure~\ref{fig:Scan4AP_Data_Handoff} shows the experimental setup.
In this experiment we moved the server deep inside the network so that
it can be reached to the vehicle through a router, an ethernet switch
and a RSU.  This arrangement enables us to determine the impact of
routing in addition to all the earlier studied impediments.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.65\columnwidth]{Scan4APwTCP_Handoff_Run}
  \bfcaption{RSU Handoff}
  \label{fig:Scan4AP_Data_Handoff}
\end{figure}

\noindent\textbf{Observations.}  In addition to all the other
impediments uncovered earlier, in this experiment we faced an
additional challenge that adversely impacts the timeliness and
reliability of information dissemination.  The router that routes
packets from the server to the vehicle consults its routing table
entries.  When the vehicle is associated with RSU A (shown as ap\_A),
the router forwards the packet on the interface towards the Ethernet
switch 1.  When the vehicle moves into the range of ap\_C, the routing
table entry is no longer valid.  Similar issues are faced at the
ethernet switches, whose tables also become stale as the vehicle moves
out of range.

Traditional approaches based on Dijkstra or Bellman-Ford algorithms
used in the Internet to update routing tables at routers are based on
the assumption that routing updates are infrequent.  In ITS, vehicles
move at high speeds making it infeasible to rely on traditional
algorithms.  Solutions relying on an RSU assigning an IP address using
DHCP will incur network address translations at the RSU imposing
additional overhead.  Moreover, it does not address the routing table
problem since the router must still route a packet to a different RSU
when handoffs occur.

Solutions relying on Mobile IP~\cite{Perkins_MobileIP:97}, though
promising, are not directly applicable since Mobile IP relies on a home
agent and a foreign agent.  Every vehicle will need to maintain a home
agent with some RSU, which may be hard and impose an extra overhead.
Moreover, due to high speeds, the foreign agents will change
frequently requiring significant overhead of maintaining the mapping
from home agent to foreign agent, and redirecting requests.

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