mobility.tex

对IEEE 802.11e里的分布式信道接入算法EDCA进行改进

        \}

        # ============================================================

        $self addif $netif
\}
\end{program} %$

The plumbing in the above method creates the network stack we see in
Figure~\ref{fig:mobilenode-dsdv}.

Each component is briefly described here. Hopefully more detailed
docuentation from CMU shall be available in the future. 
\begin{description}
\item[{\bf Link Layer}] The \code{LL} used by mobilenode is same as
  described in Chapter~\ref{chap:lan}. The only difference being the
  link layer for mobilenode, has an ARP module connected to it which
  resolves all IP to hardware (Mac) address conversions. Normally for
  all outgoing (into the channel) packets, the packets are handed down
  to the \code{LL} by the Routing Agent. The \code{LL} hands down
  packets to the interface queue. For all incoming packets (out of the
  channel), the mac layer hands up packets to the \code{LL} which is
  then handed off at the \code{node_entry_} point. The
  \clsref{LL}{../ns-2/ll.h} is implemented in \nsf{ll.\{cc,h\}} and
  \nsf{tcl/lan/ns-ll.tcl}.

\item [{\bf ARP}] The Address Resolution Protocol (implemented in BSD
  style) module receives queries from Link layer. If ARP has the
  hardware address for destination, it writes it into the mac header
  of the packet. Otherwise it broadcasts an ARP query, and caches the
  packet temporarily. For each unknown destination hardware address,
  there is a buffer for a single packet. Incase additional packets to
  the same destination is sent to ARP, the earlier buffered packet is
  dropped. Once the hardware address of a
  packet"s next hop is known, the packet is inserted into the
  interface queue. The \clsref{ARPTable}{../ns-2/arp.h} is implemented
  in \nsf{arp.\{cc,h\}} and \nsf{tcl/lib/ns-mobilenode.tcl}.

\item[{\bf Interface Queue}] The \clsref{PriQueue}{../ns-2/priqueue.h}
  is implemented as a priority queue which gives priority to routing  
  rotocol packets, inserting them at the head of the queue. It supports
  running a filter over all packets in the queue and removes those with
  a specified destination address. See \nsf{priqueue.\{cc,h\}} for 
  interface queue implementation.

\item[{\bf Mac Layer}] The IEEE 802.11 distributed coordination 
  function (DCF) Mac protocol has been implemented by CMU. It uses a 
  RTS/CTS/DATA/ACK pattern for all unicast packets and simply sends out
  DATA for all broadcast packets. The implementation uses both 
  physical and virtual carrier sense. The
  \clsref{Mac802\_11}{../ns-2/mac-802\_11.h} is implemented in
  \nsf{mac-802\_11.\{cc,h\}}.
  
\item[{\bf Tap Agents}] \code{Agents} that subclass themselves as
  \clsref{Tap}{../ns-2/mac.h} defined in mac.h can register themselves
  with the mac object using method installTap(). If the particular Mac
  protocol permits it, the tap will promiscuously be 
  given all packets received by the mac layer, before address filtering
  is done. See \nsf{mac.\{cc,h\}} for \clsref{Tap} implementation. 

\item[{\bf Network Interfaces}] The Network Interphase layer serves as
  a hardware interface which is used by mobilenode to access the
  channel. The wireless shared media interface is implemented as
  \clsref{Phy/WirelessPhy}{../ns-2/wireless-phy.h}. This interface
  subject to collisions and the radio propagation model receives
  packets transmitted by other node interfaces to the channel. The
  interface stamps each transmitted packet with the meta-data related
  to the transmitting interface like the transmission power,
  wavelength etc. This meta-data in pkt header is used by the
  propagation model in receiving network interface to determine if the
  packet has minimum power to be received and/or captured and/or
  detected (carrier sense) by the receiving node. The model
  approximates the DSSS radio interface (Lucent WaveLan
  direct-sequence spread-spectrum). See \nsf{phy.\{cc.h\}} and
  \nsf{wireless-phy.\{cc,h\}} for network interface implementations.

\item[{\bf Radio Propagation Model}]  It uses Friss-space attenuation
  ($1/r^2$) at near distances and an approximation to Two ray Ground
  ($1/r^4$) at far distances. The approximation assumes specular
  reflection off a flat ground plane. See \nsf{tworayground.\{cc,h\}}
  for implementation.

\item[{\bf Antenna}] An omni-directional antenna having unity gain is 
  used by mobilenodes. See \nsf{antenna.\{cc,h\}} for implementation
  details. 
\end{description}

\subsection{Different types of Routing Agents in mobile networking}
\label{sec:mobilenode-routing}

The four different ad-hoc routing protocols currently implemented
for mobile networking in \ns are dsdv, dsr, aodv and tora. In this section
we shall briefly discuss each of them.

\subsubsection{DSDV}
\label{sec:dsdv}

In this routing protocol routing messages are exchanged between
neighbouring mobilenodes (i.e mobilenodes that are within range of one
another). Routing updates may be triggered or routine. Updates are
triggered in case a routing information from one of t   
he neighbours forces a change in the routing table.
A packet for which the route to its destination is not known is cached
while routing queries are sent out. The pkts are cached until
route-replies are received from the destination. There is a maximum buffer
size for caching the pkts waiting for routing information beyond which
pkts are dropped. 

All packets destined for the mobilenode are routed directly by the address
dmux to its port dmux. The port dmux hands the packets to the respective
destination agents. A port number of 255 is used to attach routing agent
in mobilenodes. The mobilenodes al
so use a default-target in their classifier (or address demux). In the
event a target is not found for the destination in the classifier (which
happens when the destination of the packet is not the mobilenode itself),
the pkts are handed to the default-ta   
rget which is the routing agent. The routing agent assigns the next hop
for the packet and sends it down to the link layer. 

The routing protocol is mainly implemented in C++. See \nsf{dsdv}
directory and \nsf{tcl/mobility/dsdv.tc}l for all procedures related to
DSDV protocol implementation.  

\subsubsection{DSR}
\label{sec:dsr}

This section briefly describes the functionality of the dynamic source
routing protocol. As mentioned earlier the \code{SRNode} is different from
the \code{MobileNode}.  The \code{SRNode}'s \code{entry\_} points to the
DSR routing agent, thus forcing all    
packets received by the node to be handed down to the routing agent. This
model is required for future implementation of piggy-backed routing
information on data packets which otherwise would not flow through the
routing agent.   

The DSR agent checks every data packet for source-route information. It
forwards the packet as per the routing information. Incase it doesnot find
routing information in the packet, it provides the source route, if route
is known, or caches the packet and   
sends out route queries if route to destination is not known. Routing
queries, always triggered by a data packet with no route to its
destination, are initially broadcast to all neighbours. Route-replies are
send back either by intermediate nodes or the 
destination node, to the source, if it can find routing info for the
destination in the route-query.  It hands over all packets destined to
itself to the port dmux.  
In \code{SRNode} the port number 255 points to a null agent since the
packet has already been processed by the routing agent. 

See \nsf{dsr} directory and \nsf{tcl/mobility/dsr.tcl} for implementation
of DSR protocol. 

\subsubsection{TORA}
\label{sec:tora}

Tora is a distributed routing protocol based on "link reversal" algorithm. 
At every node a separate copy of TORA is run for every destination. When a
node needs a route to a given destination it broadcasts a QUERY message
containing the address of the destination for which it requires  a route.
This packet travels through the network until it reaches the destination
or an intermediate node that has a route to the destination node.
This recepient node node then broadcasts an UPDATE packet listing its
height wrt the destination. As this node propagates through the network
each node updates its height to a value greater than the height of the
neighbour from which it receives the UPDATE. This results in a series of
directed links from the node that originated the QUERY to the destination
node. If a node discovers a particular destination to be unreachable it
sets a local maximum value of height for that destination. Incase the node
cannot find any neighbour having finite height wrt this destination it
attempts to find a new route. In case of network partition, the node
broadcasts a CLEAR message that resets all routing states and removes
invalid routes from the network.

TORA operates on top of IMEP (Internet MANET Encapsulation Protocol) that
provides reliable delivery of route-messages and informs the routing
protocol of any changes of the links to its neighbours. IMEP tries to
aggregate IMEP and TORA messages into a single packet (called block) in
order to reduce overhead. For link-status sensing and maintaining a list
of neighbour nodes, IMEP sends out periodic BEACON messages which is
answered by each node that hears it by a HELLO reply message.
See \ns/tora directory and \ns/tcl/mobility/tora.tcl for implementation of
tora in \ns.

\subsubsection{AODV}
\label{sec:AODV}

AODV is a combination of both DSR and DSDV protocols. It has the basic
route-discovery and route-maintenance of DSR and uses the hop-by-hop
routing, sequence numbers and beacons of DSDV. The node that wants to know
a route to a given destination generates a ROUTE REQUEST. The route
request is forwarded by intermediate nodes that also creates a reverse
route for itself from the destination. When the request reaches a node
with route to destination it generates a ROUTE REPLY containing the number
of hops requires to reach destination. All nodes that participates in
forwarding this reply to the source node creates a forward route to
destination. This state created from each node from source to destination
is a hop-by-hop state and not the entire route as is done in source
routing.
See \ns/aodv and \ns/tcl/lib/ns-lib.tcl for implementational details
of aodv.


\subsection{Trace Support}
\label{sec:mobile-trace}

The trace support for wireless simulations currently use cmu-trace
objects. In the future this shall be extended to merge with trace and
monitoring support available in ns, which would also include nam support
for wireless modules. For now we will explain briefly with cmu-trace
objects and how they may be used to trace packets for wireless scenarios. 

The cmu-trace objects are of three types - \code{CMUTrace/Drop},
\code{CMUTrace/Recv} and \code{CMUTrace/Send}. These are used for tracing
packets that are dropped, received and sent by agents, routers, mac layers
or interface queues in \ns. The methods and procedures used for
implementing wireless trace support can be found under
\nsf{trace.\{cc,h\}} and \nsf{tcl/lib/ns-cmutrace.tcl}.

A cmu-trace object may be created by the following API:
\begin{program}
set sndT [cmu-trace Send "RTR" $self]
\end{program} %$
which creates a trace object, sndT, of the type \code{CMUTrace/Send}
for tracing all packets that are sent out in a router. The trace
objects may be used to trace packets in MAC, agents (routing or
others), routers or any other NsObject. 

The cmu-trace object \code{CMUTrace} is derived from the base class
\code{Trace}. See Chapter~\ref{chap:trace} for details on class
\code{Trace}. The class \code{CMUTrace} is defined as the following:

\begin{program}
class CMUTrace : public Trace \{
public:
        CMUTrace(const char *s, char t);
        void    recv(Packet *p, Handler *h);
        void    recv(Packet *p, const char* why);

private:
        int off_arp_;
        int off_mac_;
        int off_sr_;

        char    tracename[MAX_ID_LEN + 1];
        int     tracetype;
        MobileNode *node_;

        int initialized() \{ return node_ && 1; \}

        int     command(int argc, const char*const* argv);
        void    format(Packet *p, const char *why);

        void    format_mac(Packet *p, const char *why, int offset);
        void    format_ip(Packet *p, int offset);

        void    format_arp(Packet *p, int offset);
        void    format_dsr(Packet *p, int offset);
        void    format_msg(Packet *p, int offset);
        void    format_tcp(Packet *p, int offset);
        void    format_rtp(Packet *p, int offset);
\};
\end{program}

The type field (described in \code{Trace} class definition) is used to
differentiate among different types of traces. For cmu-trace this can be
{\bf s} for sending, {\bf r} for receiving or {\bf D} for dropping a
packet. A fourth type {\bf f} is used to denote forwarding of a packet
(When the node is not the originator of the packet). 
Similar to the method Trace::format(), the CMUTrace::format() defines and
dictates the trace file format. The method is shown below: 
\begin{program}
void CMUTrace::format(Packet* p, const char *why)
\{
        hdr_cmn *ch = HDR_CMN(p);
        int offset = 0;

        /*
         * Log the MAC Header
         */
        format_mac(p, why, offset);
        offset = strlen(wrk_);

        switch(ch->ptype()) \{

        case PT_MAC:
                break;

        case PT_ARP:
                format_arp(p, offset);
                break;

        default:
                format_ip(p, offset);
                offset = strlen(wrk_);

                switch(ch->ptype()) \{

                case PT_DSR:
                        format_dsr(p, offset);
                        break;

                case PT_MESSAGE:
                case PT_UDP:
                        format_msg(p, offset);
                        break;
                        
                case PT_TCP:
                case PT_ACK:
                        format_tcp(p, offset);
                        break;
                        
                case PT_CBR:
                        format_rtp(p, offset);
                        break;
                ..........

                \}
        \}
\}
\end{program}