draft-ietf-manet-aodv-10.txt

OMNET++仿真三色算法的源码,三色算法是无线传感器中一个典型的分簇算法

         For instance, the node initiating a Route Discovery process and
         broadcasting the RREQ message is called the originating node of
         the RREQ message.

      reverse route

         A route set up to forward a reply (RREP) packet back to the
         originator from the destination or from an intermediate node
         having a route to the destination.


4. Message Formats

4.1. Route Request (RREQ) Message Format

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |J|R|G|       Reserved          |   Hop Count   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            RREQ ID                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Destination IP Address                     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                  Destination Sequence Number                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Originator IP Address                     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                  Originator Sequence Number                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The format of the Route Request message is illustrated above, and
   contains the following fields:

      Type           1

      J              Join flag; reserved for multicast.

      R              Repair flag; reserved for multicast.




Perkins, Belding-Royer, Das        Expires 19 July 2002         [Page 4]

Internet Draft                   AODV                    19 January 2002


      G              Gratuitous RREP flag; indicates whether a
                     gratuitous RREP should be unicast to the node
                     specified in the Destination IP Address field (see
                     sections 6.3, 6.6.3)

      Reserved       Sent as 0; ignored on reception.

      Hop Count      The number of hops from the Originator IP Address
                     to the node handling the request.

      RREQ ID        A sequence number uniquely identifying the
                     particular RREQ when taken in conjunction with the
                     originating node's IP address.

      Destination IP Address
                     The IP address of the destination for which a route
                     is desired.

      Destination Sequence Number
                     The greatest sequence number received in the
                     past by the originator for any route towards the
                     destination.

      Originator IP Address
                     The IP address of the node which originated the
                     Route Request.

      Originator Sequence Number
                     The current sequence number to be used for
                     route entries pointing to (and generated by) the
                     originator of the route request.


4.2. Route Reply (RREP) Message Format

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |R|A|    Reserved     |Prefix Sz|   Hop Count   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Destination IP address                    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                  Destination Sequence Number                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Originator IP address                     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           Lifetime                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+




Perkins, Belding-Royer, Das        Expires 19 July 2002         [Page 5]

Internet Draft                   AODV                    19 January 2002


   The format of the Route Reply message is illustrated above, and
   contains the following fields:

      Type          2

      R             Repair flag; used for multicast.

      A             Acknowledgment required; see sections 5 and 6.7.

      Reserved      Sent as 0; ignored on reception.

      Prefix Size   If nonzero, the 5-bit Prefix Size specifies that the
                    indicated next hop may be used for any nodes with
                    the same routing prefix (as defined by the Prefix
                    Size) as the requested destination.

      Hop Count     The number of hops from the Originator IP Address
                    to the Destination IP Address.  For multicast route
                    requests this indicates the number of hops to the
                    multicast tree member sending the RREP.

      Destination IP Address
                    The IP address of the destination for which a route
                    is supplied.

      Destination Sequence Number
                    The destination sequence number associated to the
                    route.

      Originator IP Address
                    The IP address of the node which originated the RREQ
                    for which the route is supplied.

      Lifetime      The time for which nodes receiving the RREP consider
                    the route to be valid.

   Note that the Prefix Size allows a Subnet Leader to supply a route
   for every host in the subnet defined by the routing prefix, which
   is determined by the IP address of the Subnet Leader and the Prefix
   Size.  In order to make use of this feature, the Subnet Leader has to
   guarantee reachability to all the hosts sharing the indicated subnet
   prefix.  The Subnet Leader is also responsible for maintaining the
   Destination Sequence Number for the whole subnet.  See section 7 for
   details.








Perkins, Belding-Royer, Das        Expires 19 July 2002         [Page 6]

Internet Draft                   AODV                    19 January 2002


4.3. Route Error (RERR) Message Format

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |N|          Reserved           |   DestCount   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Unreachable Destination IP Address (1)             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Unreachable Destination Sequence Number (1)           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|
   |  Additional Unreachable Destination IP Addresses (if needed)  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |Additional Unreachable Destination Sequence Numbers (if needed)|
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   The format of the Route Error message is illustrated above, and
   contains the following fields:

      Type        3

      N           No delete flag; set when a node has performed a local
                  repair of a link, and upstream nodes should not delete
                  the route.

      Reserved    Sent as 0; ignored on reception.

      DestCount   The number of unreachable destinations included in the
                  message; MUST be at least 1.

      Unreachable Destination IP Address
                  The IP address of the destination that has become
                  unreachable due to a link break.

      Unreachable Destination Sequence Number
                  The sequence number in the route table entry for
                  the destination listed in the previous Unreachable
                  Destination IP Address field.

   The RERR message is sent whenever a link break causes one or more
   destinations to become unreachable from some of the node's neighbors.
   See section 6.2 for information about how to maintain the appropriate
   records for this determination, and section 6.11 for specification
   about how to create the list of destinations.







Perkins, Belding-Royer, Das        Expires 19 July 2002         [Page 7]

Internet Draft                   AODV                    19 January 2002


5. Route Reply Acknowledgment (RREP-ACK) Message Format

    0                   1
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |   Reserved    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


      Type        4

      Reserved    Sent as 0; ignored on reception.

   The RREP-ACK message may be used to acknowledge receipt of a RREP
   message.  It is used in cases where the link over which the RREP
   message is sent may be unreliable or unidirectional.


6. AODV Operation

   This section describes the scenarios under which nodes generate Route
   Request (RREQ), Route Reply (RREP) and Route Error (RERR) messages
   for unicast communication towards a destination, and how the message
   data are handled.  In order to process the messages correctly,
   certain state information has to be maintained in the route table
   entries for the destinations of interest.

   All AODV messages are sent to port 654 using UDP.


6.1. Maintaining Sequence Numbers

   AODV depends on each node in the network to own and maintain a
   sequence number to guarantee the loop-freedom of all routes towards
   that node.  A node increments its own sequence number in two
   circumstances:

    -  Immediately before a node originates a route discovery, it MUST
       increment its own sequence number.  This prevents problems with
       deleted reverse routes to the originator of a RREQ.
    -  Immediately before a destination node originates a RREP in
       response to a RREQ, it MUST update its own sequence number to
       the maximum of its current sequence number and the destination
       sequence number in the RREQ packet.

   When the destination increments its sequence number, it MUST do so by
   treating the sequence number value as if it were an unsigned number.
   Thus, if the sequence number has already been assigned to be the
   largest possible number representable as a 32-bit unsigned integer



Perkins, Belding-Royer, Das        Expires 19 July 2002         [Page 8]

Internet Draft                   AODV                    19 January 2002


   (i.e., 4294967295), then when it is incremented it will then have a
   value of zero (0).  Similarly, if the sequence number currently has
   the value 2147483647, which is the largest possible positive integer
   when if 2's complement arithmetic is in use, the next value will be
   2147483648, which is the most negative possible integer in the same
   numbering system.  The representation of negative numbers is not
   relevant to the incrementation of AODV sequence numbers.  This is
   in contrast to the manner in which the result of comparing two AODV
   sequence numbers is to be treated (see below).

   Every route table entry at every node MUST include the latest
   information available about the sequence number for the IP address of
   the destination node for which the route table entry is maintained.
   This sequence number is called the "destination sequence number".  It
   is updated whenever a node receives new (i.e., not stale) information
   about the sequence number from RREQ, RREP, or RERR messages that may
   be received related to that destination.  In order to ascertain that
   information about a destination is not stale, the node compares its
   current numerical value for the sequence number with that obtained
   from the incoming AODV message.  This comparison MUST be done using
   signed 32-bit arithmetic.  If the result of subtracting the currently
   stored sequence number from the value of the incoming sequence number