[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
Internet Engineering Task Force                               Yunjung Yi
INTERNET DRAFT                                                      UCLA
Expires May 14, 2002                                       Taek Jin Kwon
draft-yi-manet-pc-00.txt                                       Telcordia
                                                             Mario Gerla
                                                                    UCLA
                                                        14 November 2001

                 Passive Clustering in Ad Hoc Networks
                                  (PC)

Status of the Memo

   This document is an Internet-Draft and is subject to all provisions
   of Section 10 of RFC2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference mate-
   rial or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   Comments should be sent to the author at yjyi@cs.ucla.edu.

   This draft expires on May 14, 2002.

Copyright Notice

   Copyright (C) The Internet Society (1999-2001).  All rights reserved.

Abstract

   This document describes Passive Clustering (PC) protocol that is a
   cluster formation mechanism designed for mobile ad hoc networks where
   the resources (e.g., bandwidth, power) are limited and the topology
   changes dynamically. This protocol, PC, provides an energy-efficient
   way of partitioning a homogeneous ad hoc network into clusters in a
   passive way. In other words, PC constructs and maintains clusters



Yi, Kwon and Gerla        Expires May 14, 2002                  [Page 1]


I-D                                PC                   14 November 2001


   using on-going data packets instead of extra explicit control mes-
   sages. The resulting clusters have only one CLUSTER HEAD (a represen-
   tative node - CH) on the center of each cluster and the transmission
   range of each CH defines the area of the cluster.

   With reasonable on-going traffic, PC effectively constructs a cluster
   architecture that changes adaptively to the node mobility and pro-
   vides a platform for efficient flooding.


                          Table of Contents

   Abstract .....................................................    1

   1. Introduction ..............................................    3

   2. Terminology ...............................................    5

   3. The Assumptions and Requirements ..........................    7

   4. Basic Description and Conceptual Data Structures...........    7
      4.1. The States of Each Node ..............................    8
      4.2. The Data Structures ..................................   10
      4.3. The Format of PC Header in IP Option Field ...........   12

   5. The Detailed Algorithm  ...................................   13
      5.1. Packet Processing ....................................   13
        5.1.1. Incoming Packet Processing .......................   14
        5.1.2. Outgoing Packet Processing .......................   15
           5.1.2.1.  First Declaration Wins Rule ................   15
      5.2. Management ...........................................   16
      5.3. The Functions ........................................   16
         5.3.1. Add ClusterHead .................................   16
         5.3.2. Add Gateway .....................................   17
         5.3.3. Add Initial .....................................   17
         5.3.4. Add Neighbor ....................................   17
         5.3.5. Check ClusterHead ...............................   18
         5.3.6. Check Gateway ...................................   18
         5.3.7. Check Initial ...................................   18
         5.3.8. Check Neighbor ..................................   18
      5.4. Gateway Selection Heuristic ..........................   18
         5.4.1. One Gateway Node per Each Pair of CHs ...........   19
         5.4.2. The Distributed Gateway Selection Mechanism .....   20
         5.4.3. The Procedure ...................................   20
            5.4.3.1. The Processing of Outgoing Packets Member Node 20
            5.4.3.2. ReCalculate Member State ...................   23
      5.5. The Lowest ID Competition ............................   24
         5.5.1. The CH Give-Up Message ..........................   25



Yi, Kwon and Gerla        Expires May 14, 2002                  [Page 2]


I-D                                PC                   14 November 2001


      5.6. The Timeout Scheme ...................................   25
      5.7. The "HELLO" message ..................................   25

   6. The Applicability .........................................   25
      6.1. The Applicability to On-demand Routing Protocol ......   25
      6.2. Protocol Characteristics .............................   26

   7. Suggested Parameters ......................................   27

   8. The Discussion and Implementation Consideration ...........   27

      8.1. Problems with a Critical Path Loss ...................   27
      8.2. The Possible Solutions ...............................   28
      8.3. Some Comments ........................................   29

   9. Author's Addresses ........................................   29

   References ...................................................   30



1. Introduction

   Passive Clustering (PC) dynamically partitions the network in clus-
   ters interconnected by gateway nodes. This protocol keeps the bene-
   fits of the cluster architecture. It, however, improves previous
   cluster formation schemes  [1, 2, 3] and removes control overhead of
   background cluster formation and maintenance using the concept of
   "passive" construction.

   PC is an "on demand" protocol. It constructs and maintains the clus-
   ter architecture only when there are on-going data packets that pig-
   gyback "cluster-related information" such as the state of a node in a
   cluster and an IP address of a node.  Each node collects neighbor
   information through promiscuous packet receptions. Thus, PC does not
   necessitate background overhead of clustering.

   Active clustering, instead, uses explicit control packets to build
   and maintain clusters and is working in the background all the time.

   PC has two innovative mechanisms for the cluster formation: the
   "First Declaration Wins" rule (chapter 5.1.2.1) and "Gateway Selec-
   tion Heuristic" (chapter 5.4). With the "First Declaration Wins"
   rule, a node that first claims to be a CLUSTER HEAD 'rules' the rest
   of nodes in its clustered area (radio coverage).  There is no waiting
   period (to make sure all the neighbors have been checked) unlike that
   in all the weight-driven clustering mechanisms [2, 7].  Also,
   "Gateway Selection Heuristic (chapter 5.4)" provides a procedure to



Yi, Kwon and Gerla        Expires May 14, 2002                  [Page 3]


I-D                                PC                   14 November 2001


   elect the minimal number of gateways required to maintain connectiv-
   ity (including distributed gateway nodes) in a distributed manner.

   Passive Clustering (PC) contributes several innovative features as
   compared with "active" clustering schemes. Namely: (1) PC requires
   only tiny extra control overhead to resolve concurrent claims by com-
   peting CLUSTER HEADs. (2) PC builds up clusters instantaneously once
   data packets are generated and start flowing; (3) PC uses a novel,
   efficient gateway selection heuristic to choose the minimum number of
   forwarding nodes; (4) PC reduces node power consumption by eliminat-
   ing the background cluster forming overhead.

   Exploiting the above-mentioned features, PC can be applied to execute
   efficient flooding, which is one of the key procedures in ad hoc net-
   works.
   Many ad hoc network protocols (e.g., routing, service discovery,
   etc.) use flooding as the basic mechanism to propagate control mes-
   sages. In flooding, each node transmits the same message until that
   packet has been propagated to the entire network. Typically, only a
   subset of the neighbors is required to forward the message in order
   to guarantee complete flooding to the entire network.
   If the node geographic density (the degree of neighbors) is too high,
   the flooding is very inefficient due to redundant, "superfluous" for-
   warding. In fact, excessive flooding packets increase link overhead
   and wireless medium congestion, and degrade the network performance.
   To improve the scalability of the flooding, an efficient flooding, in
   which only selected dominant nodes participate in flooding, is neces-
   sary. More importantly, it is required to choose such dominant nodes
   with very low overhead.
   PC leads to efficient flooding in that it provides an energy-
   efficient clustering (low overhead) and is independent to the number
   of neighbors (scalable). PC works most effectively in geographically
   dense and dimensionally large networks. In contrast, other schemes
   merely proposed for efficient flooding  [4, 5] are suffering from
   huge control message overhead under high mobility situation or den-
   sity situation.

   Note that, with reasonable on-going data traffic, PC constructs
   impromptu "soft-state" clusters, in which nodes do not begin cluster-
   ing unless they have outgoing or incoming packets generated by some
   application. They do build up clusters instantly, without any
   "deployment" latency, however, when data packets start flowing.





2. Terminology



Yi, Kwon and Gerla        Expires May 14, 2002                  [Page 4]


I-D                                PC                   14 November 2001


   The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC2119  [6]

   The following terms are also used to describe PC:

      node

          A MANET router that implements passive clustering, identified
          by a unique node ID.

      cluster

          A cluster consists of a group of nodes within the transmission
          range of one of them elected as a CLUSTER HEAD.

      Cluster Member

          All nodes within a cluster except for the CLUSTER HEAD are
          called members. A member is considered to "belong to cluster
          {CH1} " when it has received (overheard) packets from the
          CLUSTER HEAD "CH1 "of the cluster {CH1}.

      CLUSTER HEAD (CH)

          A CLUSTER HEAD (CH) of a cluster is a central node that can be
          directly reached from each member node of the cluster. Each
          cluster should have only one CLUSTER HEAD.
          Chapter 5.1.2.1 explains how to elect a CH. The basic idea of
          election is that one of candidate CHs claims (declares) as a
          CH when that node has an outgoing packet. A node can be a can-
          didate CH only when this node is neither isolated nor a member
          to any cluster. If two nodes declare as CHs at the same time,
          then a node with the lower node ID wins the other. Unless a
          packet sent from another CH comes in, a CH keeps its role as a
          CH. For the purpose of load-balancing, however, a CH can
          intentionally give up its role. Note that the traffic tends to
          be concentrated on CHs and gateway nodes.

          PC results very stable cluster architecture compared with
          other clustering mechanisms even with the mobility. The reason
          why PC is a stable is that PC does not occur cascading effects
          because member nodes cannot override existing CHs.


          Topology 1.

          - : link between two nodes



Yi, Kwon and Gerla        Expires May 14, 2002                  [Page 5]


I-D                                PC                   14 November 2001


              (1)   (3)-4-(5)-6-(7)-8     (1), (3), (5), (7): CHs
                                             4, 6, 8: Members


          Topology 2.

                  (1)-3-(4)-5-(6)-7-(8)   (1), (4), (6), (8): CHs
                                           3, 5, 7: Members

          Topology 3.

                  (1)-3-4-(5)-6-(7)-8    (1), (5), (7): CHs
                                           3, 4, 6, 8: Members

                   Figure 1. An Example of Cascading Effect


          For instance in Figure 1, let's assume that the "Lowest ID"
          clustering algorithm  [7] is used and node "1" moves toward
          node "3" and becomes a neighbor node of node "3". Then, node
          "3" should give up the role of CH since node "1" has the lower
          node ID than node "3". If node "3" gives up the role of CH,
          then cascading changes will occur. Eventually, the final
          result will be Topology 2 in Figure 1.

          In contrast, PC will stop the state change of node "4" since
          node "4" already knows the existence of CH "5". Instead of
          changing of the role, node "3" and "4" become distributed
          gateway (DIST_GW) nodes. Therefore, PC results Topology 3 in
          Figure 1.

      gateway node

          A gateway node of a cluster is one of members and a CH uses
          this node to communicate with adjacent CHs. Finding enough but
          minimal number of gateways in a distributed manner is a well-
          known NP problem. This problem can be induced to the question
          how a node (CH) chooses optimal dominant set of nodes that
          cover all nodes that are within two-hops away from the node.
          Many literatures  [4, 5] have provided heuristics for that
          problem. Those solutions, however, require periodic exchanges
          of neighbor list. And the control overhead is tightly coupled
          with the degree of neighbors. Passive Clustering, on the other
          hand, suggests another heuristic that does not need periodic
          neighbor exchanges in Chapter 5.4.

      ORDINARY node




Yi, Kwon and Gerla        Expires May 14, 2002                  [Page 6]


I-D                                PC                   14 November 2001


          A member that is not a gateway node is an ORDINARY node.

      node 'A' is known to node 'B'

          A node 'A' is known to node 'B' if node 'B' has directly (not
          through multi-hop nodes) overheard packets from 'A'.


3. The Assumptions and Requirements

   This section lists the assumptions and requirements of the underlying
   networks of Passive Clustering.

   Each MANET node that runs PC is equipped with one wireless media.

   Each MANET node uses the omni-directional antenna. Each packet that a
   node sends is broadcast into the region of its radio coverage.

   Passive Clustering (PC) requires overhearing, intercepting, and
   manipulating every IP packet. Furthermore, if there is a link between
   two nodes, then the link is assumed to be "bi-directional". And the
   maximum radio range of each node is required to be "homogeneous".


4. Basic Description and Conceptual Data Structures

   The key idea of PC is to exploit on-going data packets and piggyback
   "cluster-related" information such as the state of a node in a clus-
   ter and an IP address of a node. Each node participates in clustering
   by overhearing messages from neighbor nodes and piggybacking own
   cluster information to outgoing packets. To attach cluster informa-
   tion, PC adds only 8 or 16 bytes (based on IP V4) to each packet
   using IP option field.

   A node does not initiate clustering unless it has outgoing or incom-
   ing packets. A node before joining a cluster is called the INITIAL
   node. With incoming or outgoing packets, a node can participate in
   clusters as a member or a CH based on the states of neighbor nodes.

   When a node has a packet to send, this node can declare as a CH or a
   gateway node by stamping its state to the packet. After a successful
   transmission of that claim packet, every node in this sender's radio
   coverage can learn the presence of the CH or the gateway node through
   overhearing that packet. Neighbor nodes of the CH cannot declare as a
   CH since only one CH is allowed in one cluster, but neighbor nodes of
   a gateway node may declare as another gateway node based on "Gateway
   Selection Heuristic" (chapter 5.4).




Yi, Kwon and Gerla        Expires May 14, 2002                  [Page 7]


I-D                                PC                   14 November 2001


   To prevent isolated clusters, which consist of only one node, and
   improve the connectivity of clusters, a node can pronounce as a CH
   only after it has overheard packets from other nodes. In other words,
   an INITIAL node cannot declare as the CH without receiving packets
   from others. A node is called a "candidate CH" (CH_READY node) if it
   knows more than one neighbor node that is not a CH.

   Upon promiscuous reception of each packet from a neighbor node, every
   neighbor node of the sender adjusts its state.
   An INITIAL node can be a candidate CH if the sender is the non-CH
   node. Otherwise, this node becomes a member of the new cluster that
   the CH (sender of the packet) creates.

   If a CH has heard from another CH, then they compete each other based
   on the "Lowest ID Competition" (chapter 5.5). When a node fails to
   keep the role of CH, it sends out a "CH Give-Up Message" (chapter
   5.5.1) to notify neighbors of the role change.
   A member node can be a gateway node or ORDINARY node based on "Gate-
   way Selection Heuristic" (chapter 5.4). This heuristic reduces the
   number of gateway nodes in an efficient way and supports distributed
   gateway scheme. In brief, only one gateway node is allowed for each
   pair of CHs and a CH should have more than two gateway nodes. Chapter
   5.4.1 describes how to decide the role of each member.

   PC maintains clusters using implicit timeout scheme. Without exchang-
   ing neighbor information, a node 'A' assumes that another node 'B' is
   out of its locality if 'B' did not send out any message longer than
   timeout duration (CLUSTER_TIME_OUT). If a member node detects no live
   CH (does not belong to any cluster), then it becomes the INITIAL node
   and starts clustering from the beginning. The implicit timeout mecha-
   nism, with reasonable offered load, works efficiently to detect
   dynamic topology changes.


4.1. The States of Each Node

   There are 2 internal and 5 external states: CH_READY and GW_READY are
   internal states, and INITIAL_NODE, CLUSTER_HEAD, GW_NODE, DIST_GW,
   and ORDINARY_NODE are external states. Note that a node uses the
   internal states to represent the tentative role (candidate CH or can-
   didate gateway node) of nodes. The internal states should be changed
   to one of external states at sending a packet, so the internal state
   of a node is not exposed to neighbor nodes. The description of each
   state is as follows.

     1. INITIAL_NODE

        When a node is initialized (wakes up), the state of a node is



Yi, Kwon and Gerla        Expires May 14, 2002                  [Page 8]


I-D                                PC                   14 November 2001


        set to the INITIAL_NODE. The state of a node that does not
        belong to any cluster (no CH has not send out messages for CLUS-
        TER_TIME_OUT) must be the INITIAL_NODE. A node is called an INI-
        TIAL node if the state of this node is the INITIAL_NODE.

     2. CLUSTER_HEAD

        The state of a node is the CLUSTER_HEAD when a node is the CLUS-
        TER HEAD.

     3. FULL_GW

        The state of a node is the FULL_GW when a node is the FULL_GW
        node. A FULL_GW node should be a member of more than two clus-
        ters at the same time so that this node can be an intermediate
        node between two cluster heads. When a FULL_GW node sends out a
        packet, it determines two CHs that this node connects and
        announces the node IDs of two CHs.

     4. ORDINARY_NODE

        The state of an ORDINARY node.

     5. GW_READY

        The GW_READY is the internal state of a potential gateway
        (FULL_GW or DIST_GW) node before this node sends out a packet.
        To guarantee that a node who has declared earlier wins, a poten-
        tial gateway keeps internal state until it actually pronounces
        the role. This node is called GW_READY node hereafter. A
        GW_READY node can change its state to ORDINARY_NODE if it has
        known (overheard packets from) enough neighbor gateway nodes.
        When a DIST_GW node sends out a packet, it announces the node ID
        of primary CH and remote CH to which it knows a path through
        another gateway.

     6. CH_READY

        The internal state of a potential CLUSTER HEAD before this node
        has an outgoing packet. To guarantee that a node who has
        declared earlier wins, a potential gateway keeps internal state
        until it actually pronounces the role. This node is called
        CH_READY node hereafter. A CH_READY node cannot declare as a CH
        if it has received a packet from another CH.

     7. DIST_GW

        The state of a distributed gateway node is DIST_GW. A DIST_GW



Yi, Kwon and Gerla        Expires May 14, 2002                  [Page 9]


I-D                                PC                   14 November 2001


        node is a gateway node that connects two clusters. It, however,
        may not be directly reachable from one of two cluster heads of
        two clusters (there are two intermediate gateway nodes between
        two cluster heads).


   A GW_READY node determines its final state just before it sends out a
   packet. This node could be an ORDINARY, FULL_GW, or DIST_GW node
   (chapter 5.4.3.2). Each internal state should be determined to any
   external state at sending a packet and the external state is stamped
   at the packet. Besides, each member may change its state upon receiv-
   ing a packet from another node (chapter 5.1.1).


4.2. The Data Structures


   Every node maintains 4 different lists: the list of CH (CLUSTER
   HEAD), GW (Gateway (GW or DIST_GW) node), INITIAL (INITIAL node) and
   NEIGHBOR (ORDINARY node). Each list is updated whenever a node has
   received a packet from another node.

     1. A list of CH

        Whenever a node has received a packet from CLUSTER HEAD, it
        updates or adds up information of that node to the list of CH.
        The entry contains:

          - NODE_ID: the node ID of the CH

          - LAST_RECV_TIME: the current time when this node
            has received a packet from the CH

          The global variable no_of_CH represents the number of valid
          ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries
          of the list of CH.

     2. A list of GW

        This is a list of gateway nodes from which this node has heard.
        The entry contains:

          - NODE_ID: the node ID of the gateway node

          - LAST_RECV_TIME: the current time when this node
            has received this packet from the gateway node

          - STATE: the cluster state of the gateway node



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 10]


I-D                                PC                   14 November 2001


            (DIST_GW or FULL_GW)


          - CH_ID_1: the node ID of first CH among the pair of CHs that
            the gateway node has announced

          - CH_ID_2: the node ID of second CH among the pair of CHs that
            the gateway node has announced


          The global variable no_of_GW represents the number of valid
          ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries
          of the list of GW.

     3. A list of INITIAL

        Whenever a node has received a packet from an INITIAL node, it
        updates or adds up information of that node to the list of INI-
        TIAL. The entry contains:

          - NODE_ID: the node ID of the INITIAL node

          - LAST_RECV_TIME: the current time when this node
            has received a packet from the INITIAL node

          The global variable no_of_IN represents the number of valid
          ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries
          of the list of INITIAL.

     4. A list of NEIGHBOR

        This is a list of ORDINARY nodes. The entry contains:

          - NODE_ID: the node ID of the ORDINARY node

          - LAST_RECV_TIME: the current time when this node
            has received a packet from the ORDINARY node

          - PRI_CH_ID: the node ID of primary CH. This field is
            optionally used (e.g., when an ORDINARY node sends "HELLO"
            messages, the scout message, etc.)

          The global variable no_of_ON represents the number of valid
          ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries
          of the list of NEIGHBOR.


   Note that PC uses the "implicit" timeout mechanism, where no explicit



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 11]


I-D                                PC                   14 November 2001


   "timer" expires. Whenever a packet comes in, all out-of-date (current
   time - LAST_RECV_TIME > CLUSTER_TIME_OUT) entries must be removed
   from lists.


4.3. The Format of PC Header in IP Option Field

   PC uses the IP option field to piggyback the information of clusters.
   The basic format of IP option of PC is as follows:



    0               1               2               3
    0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | STA |G|H|                      RESERVED                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            Node ID                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            Options                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                              ...                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+



     STA

       The field is used to specify the state of each node.

     G

       CH give-up field.

       This field is used when a CH gives up its role and sends a "CH
       Give-Up Message" (chapter 5.5.1) to inform neighbors of the
       change. A node set this field as "TRUE" with "CH Give-Up Message.
       Otherwise, the default value is "FALSE".

     H

       If this message is a "HELLO" message, the sender set this field
       as "TRUE". Otherwise, the default value is "FALSE".

     RESERVED

       Reserved area. Must be set to "0"(zero).




Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 12]


I-D                                PC                   14 November 2001


     Node ID

       The IP address of the sender node. This may be different to the
       source address in the IP header. (based on IP V4)

     Options

       This field is used for a gateway node to announce two CHs. Also,
       when a node sends "HELLO" message, this option field may contain
       the node ID of primary CH of the sender node. If the sender
       belongs to only one cluster, let's say the node ID of CH of that
       cluster is "CH1", then the primary CH is CH1. Otherwise, the
       sender can choose randomly one primary CH among all CHs that are
       known to the sender.

       The format of options used by a "FULL_GW" or "DIST_GW" node is as
       follows:

      0               1               2               3
      0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                           CH_ID_1                             |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                           CH_ID_2                             |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


       CH_ID_1

          The IP address of first CLUSTER HEAD

       CH_ID_2

          The IP address of second CLUSTER HEAD

       If this node is a FULL_GW node, then the order of "CH_ID_1" and
       "CH_ID_2" can be reversed. If this node is a DIST_GW node, then
       "CH_ID_1" should be the node ID of the primary CH of this node
       and "CH_ID_2" should be the node ID of remote CH to which this
       node relays messages from the primary CH.


5. The Detailed Algorithm

   This section describes the detail algorithm of PC.


5.1. Packet Processing



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 13]


I-D                                PC                   14 November 2001


   All functions related to clustering are called only when a packet
   comes in or out.


5.1.1. Incoming packet Processing

   PC requires "promiscuous" packet reception. Upon receiving a packet,
   PC extracts IP option field that is used for PC protocol. If there is
   no IP option in the packet, then PC just bypass that packet to the
   proper application.

   A node with INITIAL_NODE state changes its state to CH_READY only
   when it has received a packet from the non-CH node.

   A cluster member decides the state following "Gateway Selection
   Heuristic" (chapter 5.4).

   A CH competes with the other CH when a packet has arrived from
   another CH based on "The Lowest ID Competition" rule (chapter 5.5).

   A state transition by incoming packet (RECV_MSG) is as follows:

     1. If RECV_MSG.STA == CLUSTER_HEAD then


       If my state == CLUSTER_HEAD and my node ID > RECV_MSG.ID then

            send CH Give-Up Message to member nodes (chapter 5.5.1)

       Else If my state == CLUSTER_HEAD and my node ID < RECV_MSG.ID
       then

            RETURN // Do nothing

       Add ClusterHead (chapter 5.3.1)
          // Add this information to the list of CH and adjust its state
          //as a member of the cluster

     2. Else If RECV_MSG.STA == FULL_GW or RECV_MSG.STA == DIST_GW then

       Add Gateway (chapter 5.3.2)
           // Add the information to the list of GW and adjust its state
           // if enough gateway nodes found, then this node can be an
           // ORDINARY node

     3. Else If RECV_MSG.STA == INITIAL_NODE then

       Add Initial (chapter 5.3.3)



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 14]


I-D                                PC                   14 November 2001


          // Add the information to the list of INITIAL
          // and adjust its state

     4. Else If RECV_MSG.STA == ORDINARY_NODE then

       Add Neighbor (chapter 5.3.4)
          // Add the information to the list of NEIGHBOR
          // and adjust its state


     If my state == INITIAL_NODE and RECV_MSG.STA != CLUSTER_HEAD then

       change my state to CH_READY


5.1.2. Outgoing Packet Processing

   When a packet is sent from the "Network" layer to the "MAC" layer, PC
   changes all internal states (CH_READY or GW_READY) to external states
   and adds IP option before it enqueues a packet to the data queue. PC
   fills up IP option with the state of clusters (STA) and all other
   field in IP option of PC as follows:

         STA: my state (after changing the internal state to the
              external state)
         G: FALSE (TRUE when a node sends out "CH Give-Up Message")
         H: FALSE (TRUE when a node sends out "HELLO" messages)
         Node ID: my node ID

   If this node is a gateway node (FULL_GW or DIST_GW node)

         CH_ID_1: my_CH_ID_1 (the node ID of first CH for this node)
         CH_ID_2: my_CH_ID_2 (the node ID of second CH for this node)
             or my_REMOTE_CH (the node ID of remote CH for DIST_GW)


5.1.2.1. First Declaration Wins Rule

   How stable and quick the clustering mechanism converges is a very
   important feature that a clustering algorithm has to provide. "First
   Declaration Wins" rule improves, compared with other mechanisms, the
   clustering stability, speeds up converging time, and avoids the sta-
   tionary requirement for neighbor learning and clustering phase. The
   working mechanism of this rule is as follows:
   When a candidate CH (CH_READY node) has packets to send, it change
   its state to CLUSTER_HEAD and stamps cluster information to the out-
   going packets that claims the role of CH. After a successful
   transmission of that claim packet, every node in the sender's radio



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 15]


I-D                                PC                   14 November 2001


   coverage can learn the presence of the CH through overhearing that
   packet.

   A declaration of the role as a gateway node follows the same rule,
   "First Declaration Wins", but there is no explicit role give-up mes-
   sage.

     1. CLUSTER HEAD

       A node whose state is CH_READY should change its state to CLUS-
       TER_HEAD.

     2. gateway (FULL_GW or DIST_GW) node

       A node whose state is GW_READY should change its state to
       FULL_GW, DIST_GW or ORDINARY_NODE (chapter 5.4.3.1).


5.2. Management

   Each node changes its state if necessary only when it has outgoing
   packets or incoming packets.


5.3. The Functions


5.3.1. Add ClusterHead

   Add information of CLUSTER HEAD to a list of CH and delete old
   entries from the list of CH (old entries: (current time -
   LAST_RECV_TIME > CLUSTER_TIME_OUT)).

   A DIST_GW node changes its state to GW_READY if the no_of_CH is
   increased

   Check Gateway (chapter 5.3.6)
     // Check the number of gateway nodes and adjust state based on
     // gateway selection heuristic

     An INITIAL node changes its state to GW_READY or ORDINARY_NODE in
     "ReCalculate Member State" (chapter 5.4.3.2) called by Check Gate-
     way function

   Check Initial (chapter 5.3.7)
     // Check the number of INITIAL nodes

   Check Neighbor (chapter 5.3.8)



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 16]


I-D                                PC                   14 November 2001


     // Check the number of ORDINARY nodes


5.3.2. Add Gateway

   Add FULL_GW or DIST_GW node's information to a list of GW and delete
   old entries from the list of GW.

   A FULL_GW node may change its state to GW_READY or ORDINARY_NODE, if
   new gateway has announced the same pair of CHs and the node ID of new
   gateway is less than own node ID. If this node found another pair of
   CHs that is not announced by another FULL_GW node, then it simply
   changes the pair of CHs (change my_CH_ID_1 && my_CH_ID_2 -- contains
   two node IDs of announced CH pair). Otherwise it changes its state to
   GW_READY.

   Check ClusterHead (chapter 5.3.5)
     // Check the number of CHs and adjust its state
     // if no neighbor CH (no_of_CH == 0) , then becomes INITIAL node.

   Check Initial (chapter 5.3.7)

   Check Neighbor (chapter 5.3.8)

   ReCalculate Member State (chapter 5.4.3.2)
     // Adjust its state based on Gateway Selection Heuristic
     // An ORINDARY node may change its state to GW_READY
     // An GW_READY node may change its state to ORINARY_NODE


5.3.3. Add Initial

   Add INITIAL node's information to a list of INITIAL node and delete
   old entries from the list of INITIAL.

   Check ClusterHead (chapter 5.3.5)

   Check Gateway (chapter 5.3.6)

   Check Neighbor (chapter 5.3.8)


5.3.4. Add Neighbor

   Add ORDINARY node's information to a list of NEIGHBOR and delete old
   entries from the list of NEIGHBOR.

   Check ClusterHead (chapter 5.3.5)



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 17]


I-D                                PC                   14 November 2001


   Check Gateway (chapter 5.3.6)

   Check Initial (chapter 5.3.7)


5.3.5. Check ClusterHead

   Delete old entries (OLD_CH) from the list of CH (old entries: (cur-
   rent time - LAST_RECV_TIME > CLUSTER_TIME_OUT)).

   Any member node changes its state to INITIAL_NODE if no_of_CH becomes
   "0" (zero)

   A gateway node changes its state to GW_READY if OLD_CH.NODE_ID equals
   to my_CH_ID_1 or my_CH_ID_2.


5.3.6. Check Gateway


   Delete old entries from the list of GW (old entries: (current time -
   LAST_RECV_TIME > CLUSTER_TIME_OUT)).

   ReCalculate Member State (chapter 5.4.3.2)


5.3.7. Check Initial

   Delete old entries from the list of INITIAL (old entries: (current
   time - LAST_RECV_TIME > CLUSTER_TIME_OUT)).


5.3.8. Check Neighbor

   Delete old entries from the list of NEIGHBOR (old entries: (current
   time - LAST_RECV_TIME > CLUSTER_TIME_OUT)).


5.4. Gateway Selection Heuristic

   A gateway node is a bridge node between two clusters. A node that is
   reachable from two CHs may declare its role as a FULL_GW node only if
   this node has not heard from another FULL_GW node that had announced
   the same pair of CHs. A node is a member of only one cluster can
   declare as a DIST_GW node to improve the connectivity of the network.

   This scheme guarantees that one cluster always has at least two
   gateway nodes.



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 18]


I-D                                PC                   14 November 2001


   The state of a node is re-calculated and updated whenever this node
   overhears an incoming packet.


5.4.1. One Gateway Node per Each Pair of CLUSTER HEADs (CHs)

   This scheme eventually allows only one FULL_GW node for each pair of
   CHs. If two nodes declare concurrently as FULL_GW nodes with announc-
   ing the same pair of CHs, then a node that has the higher ID may give
   up FULL_GW role or change its pair of CHs.

   A FULL_GW announces two IDs of CLUSTER HEAD when it has an outgoing
   packet.
   For example in Figure 2, (A) means that the node ID of that node is
   "A" and [B,C] means that the node ID of two CHs that a FULL_GW node
   has announced are "B" and "C". The connectivity matrix between two
   nodes is on the right of figure.


   GW: a FULL_GW node, NODE: a GW_READY node

                                                     1 2 3 4 5 6 7
             GW (1)[4,7]  CH (4)  GW(3)[4,6]       1 1 1 0 1 1 0 1
                         NODE (5)                  2 1 1 1 1 1 1 1
                CH (7)   NODE (2)  CH (6)          3 0 1 1 1 1 1 0
                                                   4 1 1 1 1 1 0 0
                                                   5 1 1 1 1 1 1 1
                                                   6 0 1 1 0 1 1 0
                                                   7 1 1 0 0 1 0 1

              Figure 2. An Example of FULL_GW Node


   In this case, when NODE (5) has an outgoing packet, NODE (5) can
   declare as FULL_GW for the pair of (CH (7), CH (6)) since there is no
   FULL_GW for ((CH (7), CH (6)).

   If NODE (2) and NODE (5) declare as FULL_GW nodes at the same time,
   then NODE (5) will give up the FULL_GW role and become an ORDINARY
   NODE after it has received a packet from NODE (2) because it has
   larger ID than NODE (2) and there is no remained pair that is not
   pronounced by another FULL_GW node.
   If there is no GW (1), then NODE (5) can change the pair of CHs to
   (CH (7), CH (4)) instead of (CH (7), CH (6)) when it has heard from
   NODE (2).

   A member node that has heard from CHs changes its state to
   ORDINARY_NODE when this node can hear from more than two CHs at the



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 19]


I-D                                PC                   14 November 2001


   same time and there is no left pair of CHs that is not announced by
   other FULL_GW nodes.


5.4.2. The Distributed Gateway Selection Mechanism

   We employ a heuristic to provide the distributed selection mechanism.
   If a node has heard from only one CH and more than three gateway
   nodes, then this node can be an ORDINARY node. And if a node that is
   a member of only one cluster "C1" and it has overheard from more than
   two DIST_GW nodes that are also the member of the same cluster C1,
   then this node can be an ORDINARY node. Otherwise, this node changes
   its state to GW_READY to declare as the DIST_GW node.

                (=== : bi-directional link)

                     CH 1  ===\\
                   //  \\     GW 4 [1,5] === CH 5
                  //    \\     //
               DIST_GW 2 === NODE 3


               Figure 3. An Example of a DIST_GW Node


   Figure 3 shows an example of a DIST_GW node. The state of node "3"
   should be GW_READY since only two gateway nodes (GW 4 and DIST_GW 2)
   and one CH (CH 1) are known to this node. At sending a packet, node
   "3" will be a DIST_GW node.

   If a DIST_GW node has received a packet from another DIST_GW that has
   announced the same pair of primary CH and remote CH, then the node
   with lower ID wins. The node with higher ID changes its state to
   GW_READY.

   If an ORDINARY node receives a packet from DIST_GW node whose primary
   CH is unknown to this node, then this node may change its state to
   GW_READY (chapter 5.4.3.2).


5.4.3. The Procedure


5.4.3.1. The Processing of Outgoing Packets for a Member Node

   At sending a packet "MSG", a node "P" with the state GW_READY changes
   its state to ORDINARY_NODE, FULL_GW or DIST_GW as follows:
   (1) no_of_CH >= 2



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 20]


I-D                                PC                   14 November 2001


     If this node finds a pair of CHs that has not announced, then this
     node becomes a FULL_GW node.  If there is no gateway node that con-
     nects one of clusters to which this node belongs to another cluster
     that a DIST_GW has announced, then this node becomes the DIST_GW
     node.  Otherwise, it becomes the ORDINARY node.

     The pseudo code is as follows:


        For each pair of CHs known to P (ch1, ch2)

            For each FULL_GW node "G" known to P

               If G has announced the same pair of CH
                    break;

               Else go to next FULL_GW node

           If no FOUND G then
              P changes its state to FULL_GW and
                MSG.CH_ID_1 = ch1 & MSG.CH_ID_2 = ch2
                my_CH_ID_1 = ch1 & my_CH_ID_2 = ch2
                RETURN

           Else go to next pair

         If all pairs are announced then

          For each DIST_GW node "DG" known to P

           If DG.CH_ID_1 is equal to one of CHs known to P then
              go to next DIST_GW node

           Else

            For each gateway node "G" except for DG

              If G.STATE == DIST_GW && G.CH_ID_2 == DG.CH_ID_2 then
                 //there is a DIST_GW node that reaches remote CH
                 break;

              Else If G.STATE == FULL_GW &&
                G.CH_ID_1 (or 2) == DG.CH_ID_1 then
                break;

              Else go to next gateway node





Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 21]


I-D                                PC                   14 November 2001


            If no FOUND G then
               P changes its state to DIST_GW and
               MSG.CH_ID_1 = the node ID of primary CH
               MSG.CH_ID_2 = DG.CH_ID_1
               my_CH_ID_1 = the node ID of primary CH
               my_REMOTE_CH = DG.CH_ID_1
               RETURN

           Else go to next DIST_GW node

        If the state ID of P is GW_READY then
         P changes its state to ORDINARY_NODE

   (2) no_of_CH == 1 and the primary CH "CH1" (the cluster {CH1})

     If there is no gateway node that connects CH1 to another CH (CH2)
     that a DIST_GW has announced, then this node becomes a DIST_GW
     node.  If there is no known DIST_GW node in the same cluster {CH1},
     then it becomes DIST_GW node. Otherwise, it becomes an ORDINARY
     node.

     The pseudo code is as follows:

       For each DIST_GW node "DG"

          If DG.CH_ID_1 == CH1
              then go to next DIST_GW node

          Else

           For each gateway node "G"

              If G.STATE== DIST_GW && G.CH_ID_1 == CH1 &&
                 G.CH_ID_2 == DG.CH_ID_1 then
                 go to next DIST_GW node

              Else If G.STATE== FULL_GW && the pair of CHs of G
                is the same pair to (CH1, DG.CH_ID_1) then
                 go to next DIST_GW node

           If no FOUND gateway node then
                P changes its state to DIST_GW and
                MSG.CH_ID_1 = CH1
                MSG.CH_ID_2 = DG.CH_ID_1
                my_CH_ID_1 = CH1
                my_REMOTE_CH = DG.CH_ID_1
                RETURN
         If the state of P is GW_READY then



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 22]


I-D                                PC                   14 November 2001


           For each DIST_GW node "DG" known to P

             If DG.CH_ID_1 == CH1 then
                P changes its state to ORDINARY_NODE
                RETURN

             Else go to next DIST_GW node

           If the state of P is GW_READY then
               P changes its state to DIST_GW and
               MSG.CH_ID_1 = CH1
               MSG.CH_ID_2 = UNKNOWN
               my_CH_ID_1 = CH1
               my_REMOTE_CH = UNKNOWN

     Note that an ORDINARY node changes its state to GW_READY when it
     receives a packet from another node and detects the shortage of
     gateway nodes (chapter 5.4.3.2). Therefore, a CH always has more
     than two relay nodes.


5.4.3.2. ReCalculate Member State

   An ORDINARY node may change its state to GW_READY if it detects the
   shortage of gateway nodes.
   A node with GW_READY state may change its state to ORDINARY_NODE if
   it detects the enough gateway nodes if there are more than two mem-
   bers.

   A member "P" changes its state as follows:

    If the state of P is neither FULL_GW nor DIST_GW then

          For each DIST_GW node "DG"

            For each gateway node "G" except for DG

              If G.STATE == DIST_GW && G.CH_ID_2 == DG.CH_ID_1 then
                //there is a DIST_GW node that reaches remote CH
                 break;

              Else If G.STATE == FULL_GW &&
                 G.CH_ID_1 (or 2) == DG.CH_ID_1 then
                break;

              Else go to next gateway node

           If no FOUND G then



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 23]


I-D                                PC                   14 November 2001


             P changes its state to GW_READY and RETURN

          If no_of_CH >= 2

            For each pair of CHs known to P (ch1, ch2)

              For each FULL_GW node "G" known to P

                If G has announced the same pair of CH
                  break;

                Else go to next FULL_GW node

              If no FOUND G then
                 P changes its state to GW_READY and RETURN

          Else If no_of_CH == 1 ("CH1": the node ID of this CH) then

             If no_of_GW >= 3 then
               P changes its state to ORDINARY_NODE and RETURN

             Else if no_of_GW == 2 then

                For each gateway node "G"

                    If G.STATE != DIST_GW || G.CH_ID_1 != CH1 then
                        P changes its state to GW_READY and RETURN

                    Else go to next gateway node

               P changes its state to ORDINARY_NODE and RETURN

             Else  P changes its state to GW_READY and RETURN


5.5. The Lowest ID Competition

   The conflict of declarations of CLUSTER HEAD can happen due to the
   dynamic change of topology and packet delay. To resolve those con-
   flicts, a node that has the lowest ID among conflicted CHs kills
   other declaration. If a CLUSTER_HEAD has received a packet from the
   CH that has the lower ID than this node, then it gives up its role,
   changes its state following the Gateway Selection Heuristic (chapter
   5.4), and sends out a "CH Give-Up Message".

   If two gateway nodes have announced the same pair of CHs, then the
   node with higher node ID should yield to the other.




Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 24]


I-D                                PC                   14 November 2001


5.5.1. The CH Give-Up Message

   After one CH gives up the CLUSTER HEAD role and has no outgoing
   packet, then it send extra "CH Give-Up Message" which set "G" as
   "TRUE" in the IP option.


5.6. The Timeout Scheme

   Except "HELLO" message (chapter 5.7), there is no explicit timeout
   scheme. But every list is maintained by CLUSTER_TIME_OUT value. An
   entry that has not been updated for CLUSTER_TIME_OUT must be removed
   from a list.


5.7. The "HELLO" message

   Each node may optionally send "HELLO" message at each CLUS-
   TER_TIME_OUT interval. Because our algorithm constructs the clusters
   in a passive way, the outcome of clusters depends on the traffic pat-
   tern. Therefore, it does not guarantee fully connected clusters at
   some cases. Even though the probability to lose the partial connec-
   tivity is very low, the make-up mechanism to guarantee the full con-
   nectivity is necessary at certain points. The "HELLO" scheme could be
   optionally used to support full connectivity (chapter 8.2 (1)).



6. The Applicability

   PC can be used for an efficient flooding mechanism with allowing only
   non-ORDINARY nodes (CH, gateway nodes and INITIAL nodes) to be for-
   warding nodes. Since the ratio of ORDINARY nodes increases as the
   density of networks raises, PC works the more effectively as the net-
   work becomes denser.

   Many schemes such as routing protocols, service discovery or multi-
   cast can get benefits by employing PC because they use a flooding as
   the basic communication mechanism. This document, however, especially
   goes over the applicability to reactive routing protocols.


6.1. The Applicability to On-demand Routing Protocols

   On-demand routing protocols have two phases (the route request and
   route reply phase) to setup a path. The incremental flooding and uni-
   cast are used for the route query and route reply phase respectively.
   The cluster architecture by PC can support a platform of efficient in



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 25]


I-D                                PC                   14 November 2001


   the route request phase. Only non-ORDINARY nodes participate in
   flooding of route request phase and, as a result, are intermediate
   nodes of any path. Note that, in the complete cluster architecture,
   two nodes can be reached each other through CHs and gateway nodes.

   For example in Figure 4, node "E", "F", "B" and "G" will stop for-
   warding route queries since they are ORDINARY nodes. Eventually, the
   route reply will go through only non-ORDINARY nodes.



                  (E)   (F)
              +-+      +     +-+                  <- : route reply
      src <-- |A| <-- /C\ <--|D| <--dest               A, D : CHs
              +-+     +-+    +-+                  C : gateway nodes
                 (B)    (G)             B, E, F, G: ORDINARY nodes


         Figure 4. An Example of the Efficient Flooding


6.2. Protocol Characteristics

    * Does this protocol provide support for unidirectional links? (if
    so, how?)

      No. Bi-directional links are required.

    * Does the protocol require the use of tunneling? (if so, how?)

      No.

    * Does the protocol require using some form of source routing? (if
    so, how?)

      No. However, source routing could be used as a basic routing pro-
      tocol with passive clustering.

    * Does this protocol require the use of periodic messaging? (if so,
    how?)

      No. However, periodic HELLO messages could be used optionally to
      guarantee a fully-connected cluster architecture.

    * Does this protocol require the use of reliable or sequenced packet
    delivery? (if so, how?)

      No. However, the FIFO queue is required.



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 26]


I-D                                PC                   14 November 2001


    * Does the protocol require link or neighbor sensing (if so, how?)

      No. However, neighbor sensing helps the clustering connectivity.

    * Does the protocol have dependence on a central entity? (if so,
    how?)

      No. All the functions are achieved in a distributed manner.

    * Does the protocol function reactively? (if so, how?)

      Yes. The formation of clusters is deferred until there is on-going
      data traffic.

    * Does the protocol function proactively? (if so, how?)

      No.

    * Does the protocol provide loop-free functions? (if so, how?)

      Yes. Passive clustering does not generate any packets that possi-
      bly occur a loop.

    * Does the protocol provide for sleep period operation? (if so,
    how?)

      No. In current version, no sleep mode is supported.

    * Does the protocol provide some form of security? (if so, how?)

      No.


7. Suggested Parameters

   CLUSTER_TIME_OUT   2 seconds


8. The Discussion and Implementation Consideration


8.1. Problems with a Critical Path Loss

   This section discusses some of the problems that we have encountered
   during the design of PC. In particular, they are related to the issue
   of the network connectivity.

   * The Connectivity Problem



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 27]


I-D                                PC                   14 November 2001


     Because PC constructs the cluster architecture in a passive way, it
     is possible to lose some critical paths. Figure 5 shows an example.

                  (=== : bi-directional link)

     DIST_GW 1 ====== CH 2 ======= DIST_GW 3 \\
                      //    \\    ||        GW 7 == CH 8
                     //      \\   ||      //
                 DIST_GW 4 ===== ORDINARY 6
                                \\
                                 \\
                                 NODE 5


                 Figure 5. An Example of a Critical Path Loss


     In Figure 5, an ORDINARY node "6" has a critical path to node "5"
     and node "5" doesn't have outgoing packets. In this case, node "6"
     has no chance to get the knowledge from node "5", so node "6" will
     not forward flooding packets to node "5". As a result, node "5"
     can't hear a message from the cluster with CH "2".


8.2. The Possible Solutions


   There are several possible solutions as follows:

   (1) The "HELLO" messages

     The periodic "HELLO" messages solve this problem. If node "6" sends
     "HELLO" message, then node "5" changes its state to CH_READY and
     declares as a CH when node "5" sends out a "HELLO" message.
     Finally, node "6" becomes a FULL_GW node which connects CH "2" and
     "5".

     All ORDINARY nodes announce the node ID of primary CH. Node "6"
     announces CH "2" when this node sends out "HELLO" messages. Let's
     assume that NODE "5" is the ORDINARY node and the primary CH of
     node "5" is node "9". After exchanges of the "HELLO" messages, node
     "5" and "6" detect that there is no gateway node that connects CH
     "2" and "9" (chapter 5.4.3.2). Therefore, node "5" and "6" change
     their states to GW_READY to become DIST_GW nodes.

     The periodic "HELLO" message avoids the connectivity problem, but
     it occurs extra overhead for exchanging packets.




Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 28]


I-D                                PC                   14 November 2001


   (2) An ORDINARY node should send at least one outgoing packet
       with active declaration of CH.

     An ORDINARY node should send out at least one packet after being
     the ORDINARY node. When an ORDINARY node sends out a packet, it
     stamps the node ID of primary CH to the packet. And if an INITIAL
     node has heard from another ORDINARY node, then it claims as a CH
     in an active way (sends explicit packet to declare) instead of a
     passive way.

     In the Figure 5, if node "5" has heard from node "6", then node "5"
     will declare actively as a CH. Then, node "6" changes its state to
     FULL_GW after it has received a declaration packet from CH "5".

     Suppose, node "5" is an ORDINARY node and has heard from node "6",
     then node "5" becomes DIST_GW node since there is no gateway node
     to connect two clusters.

     This solution, however, has a problem with the node mobility and
     new incoming nodes. For example, if node "5" wakes up after node
     "6" finally becomes the ORDINARY node, then the critical path from
     node "5" to "6" is still lost.

   (3) The scout messages

     An ORDINARY node sets the BIRTH_TIME to the current time when it
     changes its state to the ORDINARY_NODE. And, it sends out a "scout"
     packet to catch un-covered neighbors after T seconds from the
     BIRTH_TIME. A node that has received the scout packet reacts the
     same way to (2).

     Still, this solution has the same problem to (2). But, ORDINARY
     nodes can send out "scout" messages periodically to prevent men-
     tioned problems.


8.3. Some Comments

   The problem of necessary gateway selection can be induced to the
   well-known set cover problem where a minimal set of gateway nodes
   that cover all two hops away neighbors. This problem is a NP complete
   problem with depending upon the quasi-stationary assumption to get
   the solution.

   Based on the quasi-stationary assumption, a set of necessary gateway
   nodes can be elected through the exchanges of neighbor lists or pre-
   known topology.
   However, the dynamic topology of the ad hoc networks challenges the



Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 29]


I-D                                PC                   14 November 2001


   basic assumption. In other words, without Oracle, the election algo-
   rithm to choose the set of necessary gateway nodes should be per-
   formed whenever the topology changes. This may cost huge overhead
   such as periodic exchanges of neighbor list, extra control packets to
   elect nodes, or extensive "HELLO" messages.

   Passive clustering, on the other hand, provides fully distributed,
   practical and very cheap in the sense of line overhead gateway selec-
   tion mechanism.

   In spite of possible cases (e.g., Figure 5) that lose critical paths,
   the extensive simulation studies show that the probability of such
   cases is extremely low in the fairly dense and loaded networks.

   Therefore, PC can be used as a practical clustering mechanism that
   provides well-partitioned groups regardless of the size, density,
   mobility, and the load status of the network.


9. Authors' Addresses

   Yunjung Yi

     UCLA
     3771 Boelter Hall
     Los Angeles, CA 90095

     EMail: yjyi@cs.ucla.edu

   Taek Jin Kwon

     Telcordia Technologies, Applied Research
     NVC3X-317
     331 Newman Springs Rd.
     Red Bank, NJ 07701

     EMail: tkwon@research.telcordia.com


   Mario Gerla

     UCLA Computer Science Department
     3564 Boelter Hall
     Los Angeles, CA 90095

     EMail: gerla@cs.ucla.edu





Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 30]


I-D                                PC                   14 November 2001


References

1.   T.J. Kwon and M. Gerla, Clustering with Power Control, Atlantic
     City, NJ (Nov. 1999). Proceedings of IEEE MILCOM'99.

2.   C.R. Lin and M. Gerla, Adaptive Clustering for Mobile Wireless Net-
     works (Sep. 1997). IEEE Journal on Selected Areas in Communica-
     tions, Vol. 15, No. 7, pp. 1265-1275.

3.   J.T. Tsai and M. Gerla, Multicluster, Mobile, Multimedia Radio Net-
     work (1995). ACM/Kluwer Journal of Wireless Networks, Vol.1, No.3,
     pp.255-65.

4.   Amir Qayyum, Laurent Viennot, Anis Laouiti, "Multipoint relaying:
     An efficient technique for flooding in mobile wireless networks,"
     INRIA report (March, 2000).

5.   H.Lim and C. Kim,, "Flooding in wireless ad hoc networks," IEEE
     computer communications (2000).

6.   Scott Bradner, "Key words for use in RFCs to indicate requirement
     levels," IETF RFC 2119 (March , 1997).

7.   M. Gerla and J. Tsai, "Multicluster, mobile, multimedia radio net-
     works," ACM Baltzer Journal of Wireless Networks, Vol. 1. No. 3.
     (1995).

























Yi, Kwon and Gerla        Expires May 14, 2002                 [Page 31]