draft-ietf-manet-cbrp-spec-01.txt

在ns2中实现了cbrp协议

   Each entry in the Neighbor Table is associated with a timer. A table
   entry will be removed if a HELLO message from the entry's node is not
   received for a period of (HELLO_LOSS+1)*HELLO_INTERVAL, allowing
   HELLO_LOSS consecutive HELLO messages to be lost from that node.

   When a node's neighborhood topology stabilizes, the Neighbor Table of
   a node will have complete information of all the nodes that have a



Jiang, Li, Tay                                                  [Page 7]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   bi-directional or uni-directional link to it within a bounded time.
   However, a node would not know to whom it has a uni-directional link.
   For example in Figure 1, the Neighbor Table of node 7 will show that
   4 has a uni-directional link to it, however node 4 would not know of
   the existence of such a link.


             8       5
           //         \\      ====    bi-directional link
          //           \\
         (1)===3==6====(2)      (1), (2) cluster heads
          \\           //
           \\         //      --->    uni-directional link
             4------>7

               Fig. 1


   Note that the 2nd and 3rd column of the neighbor table and the status
   field of the hello message need not be used for the purpose of link
   sensing; they are there mainly for cluster formation and adjacent
   cluster discovery, which will be discussed in Section 6.

   In addition to maintaining the Neighbor Table at each node, the peri-
   odic broadcasting of HELLO messages also enables each node to gain
   complete information about all bi-directional links within two-hops.
   Such information is kept in a data structure we call the two-hop-
   topology database.  By checking its 2-hop-topology database, a node
   can tell who are its 2-hop bi-directionally linked neighbors and
   through which intermediate nodes can they be reached.  The format of
   this 2-hop-topology database is implementation dependent.

6. Protocol Operation

   The operations of CBRP are entirely distributed.  The major compo-
   nents are: Cluster Formation, Adjacent Cluster Discovery and Routing.

6.1 Cluster Formation

   The goal of Cluster Formation is to impose some kind of structure or
   hierarchy in the otherwise completely disorganized ad hoc network.
   The algorithm is a variation of the simple "lowest ID" clustering
   algorithm in which the node with a lowest ID among its neighbors is
   elected as the Cluster Head [11].

   Apart from the states of C_MEMBER and C_HEAD, we define a transi-
   tional state called C_UNDECIDED for smoother operation of cluster
   formation. "Undecided" means that a node is still in search of its



Jiang, Li, Tay                                                  [Page 8]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   host cluster. All nodes wake up in the Undecided state. We will refer
   to a node in the undecided state as an undecided node hereafter.

   A node uses the information obtained from the HELLO messages for
   Cluster Formation. An Undecided node schedules a u_timer to go off in
   UNDECIDED_PD seconds and broadcast a HELLO message whenever it enters
   the C_UNDECIDED state.  When a cluster head receives a HELLO message
   from an Undecided Node, it will send out a triggered HELLO message
   immediately.  If an undecided node receives a HELLO message from a
   Cluster Head indicating a bi-directional link in between, it aborts
   its u_timer and sets its own status to C_MEMBER. When the u_timer
   times out, if the node's Neighbor Table contains no bi-directional
   neighbors, then it re-enters the Undecided state; otherwise it elects
   itself as a Cluster Head. The new Cluster Head will change the first
   field in its subsequently broadcast HELLO messages from C_UNDECIDED
   to C_HEAD thereafter.

   A cluster head regards all the neighbors that it has bi-directional
   links to as its member nodes. A node regards itself as a member node
   for a particular cluster if it has a bi-directional link to the cor-
   responding cluster head.  Note that a member node may hear from sev-
   eral cluster heads and therefore have several host clusters; its host
   cluster heads are implicitly listed in the HELLO messages it broad-
   casts.

   As clusters are identified by their respective cluster heads, we
   would like to have the cluster heads change as infrequently as possi-
   ble.  We use the following rules for changing cluster head, as
   described in [10].

     1. A non-cluster head never challenges the status of an existing
        cluster head, i.e. if X is a non-cluster head node with a
        bi-directional link to cluster head Y, X does not become
        a cluster head even if it has an ID lower than Y's.
     2. When two cluster heads move next to each other (i.e. there
        is a bi-directional link between them) over an extended period
        of time (for CONTENTION_PERIOD seconds), then only will one of
        them lose its role of cluster head.

   As a result, whenever a cluster head hears HELLO messages from
   another cluster head indicating a bi-directional link, it sets
   c_timer to expire in CONTENTION_PERIOD seconds.  When c_timer
   expires, it will check if it is still in contention with the other
   cluster head, by checking if the other cluster head is still in its
   neighbor table.  If so, it compares its own ID with that of the other
   cluster head's.  The one with a smaller ID will continue to act as
   cluster head.  The one with a bigger ID gives up its role as cluster
   head and changes from C_HEAD to C_MEMBER in its subsequent HELLO



Jiang, Li, Tay                                                  [Page 9]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   messages. This might trigger reorganization of other clusters.

   Whenever a member node's last cluster head entry times out, this node
   checks among its bi-directionally linked neighbors if it has the low-
   est ID, if so it changes its state to C_HEAD and sends out a trig-
   gered HELLO, otherwise it goes to C_UNDECIDED state.

   A simplified state transition diagram without considering unidirec-
   tional links for Cluster Formation is shown in Appendix A.


6.2 Adjacent Cluster Discovery

   Cluster X and cluster Y are said to be bi-directionally linked, if
   any node in cluster X is bi-directionally linked to another node in
   cluster Y, or if there is a pair of opposite uni-directional links
   between any 2 nodes in cluster X and cluster Y respectively.  For
   example in Figure 2, cluster 1 and cluster 2 are bi-directionally
   linked by the pair of links 3->4 and 5->6.

   Cluster X is said to be uni-directionally linked to cluster Y if they
   are not bi-directionally linked and if there exists some node in
   cluster X that is uni-directionally linked to some node in cluster Y.
   X is called Y's upstream uni-directionally linked adjacent cluster,
   and vice versa.  For example, in Figure 1, cluster 1 is cluster 2's
   upstream uni-directionally linked adjacent cluster.

   The goal of Adjacent Cluster Discovery is for a cluster to discover
   all its bi-directionally linked adjacent clusters. For this purpose,
   each node keeps a Cluster Adjacency Table (CAT) that records informa-
   tion about all its neighboring cluster heads.

   Note that for member nodes, neighboring cluster heads are always two
   hops away and can be discovered by checking received HELLO messages.
   For a cluster head, its neighboring cluster heads could be 2 or 3
   hops away (see Figure 2).  Using the HELLO messages alone, a cluster
   head is able to discover the cluster heads 2 hops away.  However, it
   has to rely on its member nodes' Cluster Adjacency Table to discover
   those neighboring cluster heads that are 3 hops away.

   The format of CAT at each node is as follows:










Jiang, Li, Tay                                                 [Page 10]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


     +--------------+  +--------+-----------+  +--------+-----------+
     |Adj. Cluster1 |->|gateway1|link status|->|gateway2|link status|
     +--------------+  +--------+-----------+  +--------+-----------+
     |Adj. Cluster2 |->|gateway1|link status|->|gateway2|link status|
     +--------------+  +--------+-----------+  +--------+-----------+
     |...
     +------------------------------------------------------------+


   Gateway field contains the ID of the gateway node through which the
   neighboring cluster head could be reached.  Gateway node is the mem-
   ber node of the adjacent cluster and hence always has a bi-direc-
   tional link to the neighboring cluster head.  The link status refers
   to the status of the link between a node's gateway node and itself.
   The possible values are LINK_BIDIRECTIONAL, LINK_FROM, LINK_TO where
   LINK_FROM means there is a uni-directional link from gateway node to
   itself and LINK_TO means there is a uni-directional link from itself
   to the gateway.  Note that there may be several gateway nodes leading
   towards a particular adjacent cluster.

   This table is updated by the periodic HELLO messages a node hears.  A
   member node finds out cluster heads that are exactly 2 hops away and
   records them in its CAT.  In particular, whenever a node A receives a
   HELLO message from B, it scans through the message's list of entries.
   If there is a cluster head C and the link status of the entry is
   LINK_BIDIRECTIONAL (i.e.  B is a member node of cluster C) and, fur-
   thermore, C is not already A's host cluster, A adds an entry in CAT
   for adjacent cluster C with gateway node B and link status specifying
   status of link between A and B.

   In order for cluster heads to gain information on their adjacent
   clusters that are 3 hops away, each member node broadcasts its summa-
   rized CAT as a Cluster Adjacency Extension to the HELLO message.
   (Only member node will send out this information, this is not the
   case with cluster heads.) The rules for summarizing is as follows:

     - If there is at least one gateway with whom the node has a
       bi-directional link, it advertise the neighboring cluster as
       bi-directionally reachable.

     - If there are only uni-directional links (LINK_FROM), the
       neighboring cluster will be advertised as LINK_FROM.
       (Note that, by HELLO messages alone, a node is not able to
       detect any LINK_TO link to the gateway.)

   The format of the Cluster Adjacency Extension to HELLO message is
   shown below:




Jiang, Li, Tay                                                 [Page 11]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


      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
                                                     +-+-+-+-+-+-+-+-+
                                                     |    Length     |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|L|
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |             Adj. Cluster Head1  IP address                    |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |             Adj. Cluster Head2  IP address                    |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                ....
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+



        Length       The number of clusterheads listed in the Extension.

        L            Link Status of the corresponding Adjacent Cluster
                     head. If there is at least one gateway node having
                     bi-directional link to the Adjacent Cluster head,
                     the Link status is specified as LINK_BIDIRECTIONAL.
                     Otherwise, it is LINK_FROM.

                     0 --- LINK_BIDIRECTIONAL
                     1 --- LINK_FROM


   In addition to using HELLO messages to construct its CAT consisting
   of 2-hop away neighboring cluster heads, a cluster head could check
   its members' Cluster Adjacency Extension to find out its 3-hop away
   neighboring cluster heads in its CAT.  In particular, suppose cluster
   head A receives B's HELLO message.  After updating its CAT with the
   Neighbor Table entries in HELLO, A proceeds to check B's Cluster
   Adjacency Extension in HELLO, if it finds adjacent cluster head C
   that is not already reachable within 2 hops, it creates a new entry
   in CAT for it with the gateway node as B and link status as specified
   in the extension.

   If a cluster head finds that some adjacent clusters are reachable
   only through a LINK_FROM uni-directional link, it will flood its
   neighborhood with a message of TTL 3 in search for a "to" link that
   corresponds to this "from" link.  This message will contain the cor-
   responding entry for the adjacent cluster.  When a cluster head
   receives such a message searching for it, it will check if it con-
   tains a corresponding LINK_FROM entry to the source cluster head.  If
   so, it will send out a reply with the corresponding CAT entry and
   update its CAT with the new LINK_TO entry as specified in the



Jiang, Li, Tay                                                 [Page 12]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


   message.  As a result, cluster heads will have complete knowledge of
   all its bi-directionally linked adjacent clusters even if there is no
   actual bi-directional links in between. For example, in Figure 2,
   Cluster 1 knows that 2 can reach cluster 1 through 5, but 1 does not
   know that cluster 2 can be reached through node 3. In CBRP, cluster
   head 1 and 2 will discover this scenario and disseminate the informa-
   tion to node 3 and 5 respectively.


              3-->4
            //     \\              1 and 2 are heads of their respective
           //       \\             clusters, 3,4,5,6 are members.
          (1)       (2)
           \\       //
            \\     //
              6<--5

              Fig. 2


6.3  Routing Considerations


   Routing in CBRP is based on source routing. It can be viewed as con-
   sisting of 2 phases: route discovery and the actual packets routing.

   Cluster structure is exploited to minimize the flooding traffic dur-
   ing route discovery phase. Furthermore, certain uni-directional links
   are discovered and used, thus increasing the network connectivity.


6.3.1 Route Discovery


   Route Discovery is the mechanism whereby a node S wishing to send a
   packet to a destination D obtains a source route to D. Similar to
   other MANET protocols [4] [1], the way S finds a route(or multiple
   routes) to D is also done by flooding, however, because of the clus-
   tering approach the number of times nodes are disturbed are much less
   in general.

   Essentially, in Route Discovery, only cluster heads are flooded with
   Route Request Packets (RREQ) in search for a source route.  The for-
   mat of such a packet is shown below:







Jiang, Li, Tay                                                 [Page 13]





INTERNET-DRAFT        CBRP Functional Specification            July 1999


         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
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |1 0| Num1      |  Num2         |         Identification        |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                         Target Address                        |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |               Gateway Node Address[1]                         |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |               Neighboring Cluster Head[1]                     |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |.....                                                          |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |               Gateway Node Address[Num1]                      |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |               Neighboring Cluster Head[Num1]                  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Cluster Address[1]                         |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                               ...                             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Cluster Address[Num2]                      |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


        10                     type of CBRP packet (Route Request)