idnits 2.17.1 draft-yi-manet-pc-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. == There are 10 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (14 November 2001) is 8198 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 935 looks like a reference -- Missing reference section? '2' on line 147 looks like a reference -- Missing reference section? '3' on line 127 looks like a reference -- Missing reference section? '7' on line 891 looks like a reference -- Missing reference section? '4' on line 891 looks like a reference -- Missing reference section? '5' on line 935 looks like a reference -- Missing reference section? '6' on line 891 looks like a reference -- Missing reference section? 'B' on line 884 looks like a reference -- Missing reference section? 'C' on line 884 looks like a reference Summary: 5 errors (**), 0 flaws (~~), 2 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force Yunjung Yi 3 INTERNET DRAFT UCLA 4 Expires May 14, 2002 Taek Jin Kwon 5 draft-yi-manet-pc-00.txt Telcordia 6 Mario Gerla 7 UCLA 8 14 November 2001 10 Passive Clustering in Ad Hoc Networks 11 (PC) 13 Status of the Memo 15 This document is an Internet-Draft and is subject to all provisions 16 of Section 10 of RFC2026. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference mate- 26 rial or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 Comments should be sent to the author at yjyi@cs.ucla.edu. 36 This draft expires on May 14, 2002. 38 Copyright Notice 40 Copyright (C) The Internet Society (1999-2001). All rights reserved. 42 Abstract 44 This document describes Passive Clustering (PC) protocol that is a 45 cluster formation mechanism designed for mobile ad hoc networks where 46 the resources (e.g., bandwidth, power) are limited and the topology 47 changes dynamically. This protocol, PC, provides an energy-efficient 48 way of partitioning a homogeneous ad hoc network into clusters in a 49 passive way. In other words, PC constructs and maintains clusters 51 I-D PC 14 November 2001 53 using on-going data packets instead of extra explicit control mes- 54 sages. The resulting clusters have only one CLUSTER HEAD (a represen- 55 tative node - CH) on the center of each cluster and the transmission 56 range of each CH defines the area of the cluster. 58 With reasonable on-going traffic, PC effectively constructs a cluster 59 architecture that changes adaptively to the node mobility and pro- 60 vides a platform for efficient flooding. 62 Table of Contents 64 Abstract ..................................................... 1 66 1. Introduction .............................................. 3 68 2. Terminology ............................................... 5 70 3. The Assumptions and Requirements .......................... 7 72 4. Basic Description and Conceptual Data Structures........... 7 73 4.1. The States of Each Node .............................. 8 74 4.2. The Data Structures .................................. 10 75 4.3. The Format of PC Header in IP Option Field ........... 12 77 5. The Detailed Algorithm ................................... 13 78 5.1. Packet Processing .................................... 13 79 5.1.1. Incoming Packet Processing ....................... 14 80 5.1.2. Outgoing Packet Processing ....................... 15 81 5.1.2.1. First Declaration Wins Rule ................ 15 82 5.2. Management ........................................... 16 83 5.3. The Functions ........................................ 16 84 5.3.1. Add ClusterHead ................................. 16 85 5.3.2. Add Gateway ..................................... 17 86 5.3.3. Add Initial ..................................... 17 87 5.3.4. Add Neighbor .................................... 17 88 5.3.5. Check ClusterHead ............................... 18 89 5.3.6. Check Gateway ................................... 18 90 5.3.7. Check Initial ................................... 18 91 5.3.8. Check Neighbor .................................. 18 92 5.4. Gateway Selection Heuristic .......................... 18 93 5.4.1. One Gateway Node per Each Pair of CHs ........... 19 94 5.4.2. The Distributed Gateway Selection Mechanism ..... 20 95 5.4.3. The Procedure ................................... 20 96 5.4.3.1. The Processing of Outgoing Packets Member Node 20 97 5.4.3.2. ReCalculate Member State ................... 23 98 5.5. The Lowest ID Competition ............................ 24 99 5.5.1. The CH Give-Up Message .......................... 25 101 I-D PC 14 November 2001 103 5.6. The Timeout Scheme ................................... 25 104 5.7. The "HELLO" message .................................. 25 106 6. The Applicability ......................................... 25 107 6.1. The Applicability to On-demand Routing Protocol ...... 25 108 6.2. Protocol Characteristics ............................. 26 110 7. Suggested Parameters ...................................... 27 112 8. The Discussion and Implementation Consideration ........... 27 114 8.1. Problems with a Critical Path Loss ................... 27 115 8.2. The Possible Solutions ............................... 28 116 8.3. Some Comments ........................................ 29 118 9. Author's Addresses ........................................ 29 120 References ................................................... 30 122 1. Introduction 124 Passive Clustering (PC) dynamically partitions the network in clus- 125 ters interconnected by gateway nodes. This protocol keeps the bene- 126 fits of the cluster architecture. It, however, improves previous 127 cluster formation schemes [1, 2, 3] and removes control overhead of 128 background cluster formation and maintenance using the concept of 129 "passive" construction. 131 PC is an "on demand" protocol. It constructs and maintains the clus- 132 ter architecture only when there are on-going data packets that pig- 133 gyback "cluster-related information" such as the state of a node in a 134 cluster and an IP address of a node. Each node collects neighbor 135 information through promiscuous packet receptions. Thus, PC does not 136 necessitate background overhead of clustering. 138 Active clustering, instead, uses explicit control packets to build 139 and maintain clusters and is working in the background all the time. 141 PC has two innovative mechanisms for the cluster formation: the 142 "First Declaration Wins" rule (chapter 5.1.2.1) and "Gateway Selec- 143 tion Heuristic" (chapter 5.4). With the "First Declaration Wins" 144 rule, a node that first claims to be a CLUSTER HEAD 'rules' the rest 145 of nodes in its clustered area (radio coverage). There is no waiting 146 period (to make sure all the neighbors have been checked) unlike that 147 in all the weight-driven clustering mechanisms [2, 7]. Also, 148 "Gateway Selection Heuristic (chapter 5.4)" provides a procedure to 150 I-D PC 14 November 2001 152 elect the minimal number of gateways required to maintain connectiv- 153 ity (including distributed gateway nodes) in a distributed manner. 155 Passive Clustering (PC) contributes several innovative features as 156 compared with "active" clustering schemes. Namely: (1) PC requires 157 only tiny extra control overhead to resolve concurrent claims by com- 158 peting CLUSTER HEADs. (2) PC builds up clusters instantaneously once 159 data packets are generated and start flowing; (3) PC uses a novel, 160 efficient gateway selection heuristic to choose the minimum number of 161 forwarding nodes; (4) PC reduces node power consumption by eliminat- 162 ing the background cluster forming overhead. 164 Exploiting the above-mentioned features, PC can be applied to execute 165 efficient flooding, which is one of the key procedures in ad hoc net- 166 works. 167 Many ad hoc network protocols (e.g., routing, service discovery, 168 etc.) use flooding as the basic mechanism to propagate control mes- 169 sages. In flooding, each node transmits the same message until that 170 packet has been propagated to the entire network. Typically, only a 171 subset of the neighbors is required to forward the message in order 172 to guarantee complete flooding to the entire network. 173 If the node geographic density (the degree of neighbors) is too high, 174 the flooding is very inefficient due to redundant, "superfluous" for- 175 warding. In fact, excessive flooding packets increase link overhead 176 and wireless medium congestion, and degrade the network performance. 177 To improve the scalability of the flooding, an efficient flooding, in 178 which only selected dominant nodes participate in flooding, is neces- 179 sary. More importantly, it is required to choose such dominant nodes 180 with very low overhead. 181 PC leads to efficient flooding in that it provides an energy- 182 efficient clustering (low overhead) and is independent to the number 183 of neighbors (scalable). PC works most effectively in geographically 184 dense and dimensionally large networks. In contrast, other schemes 185 merely proposed for efficient flooding [4, 5] are suffering from 186 huge control message overhead under high mobility situation or den- 187 sity situation. 189 Note that, with reasonable on-going data traffic, PC constructs 190 impromptu "soft-state" clusters, in which nodes do not begin cluster- 191 ing unless they have outgoing or incoming packets generated by some 192 application. They do build up clusters instantly, without any 193 "deployment" latency, however, when data packets start flowing. 195 2. Terminology 196 I-D PC 14 November 2001 198 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 199 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 200 document are to be interpreted as described in RFC2119 [6] 202 The following terms are also used to describe PC: 204 node 206 A MANET router that implements passive clustering, identified 207 by a unique node ID. 209 cluster 211 A cluster consists of a group of nodes within the transmission 212 range of one of them elected as a CLUSTER HEAD. 214 Cluster Member 216 All nodes within a cluster except for the CLUSTER HEAD are 217 called members. A member is considered to "belong to cluster 218 {CH1} " when it has received (overheard) packets from the 219 CLUSTER HEAD "CH1 "of the cluster {CH1}. 221 CLUSTER HEAD (CH) 223 A CLUSTER HEAD (CH) of a cluster is a central node that can be 224 directly reached from each member node of the cluster. Each 225 cluster should have only one CLUSTER HEAD. 226 Chapter 5.1.2.1 explains how to elect a CH. The basic idea of 227 election is that one of candidate CHs claims (declares) as a 228 CH when that node has an outgoing packet. A node can be a can- 229 didate CH only when this node is neither isolated nor a member 230 to any cluster. If two nodes declare as CHs at the same time, 231 then a node with the lower node ID wins the other. Unless a 232 packet sent from another CH comes in, a CH keeps its role as a 233 CH. For the purpose of load-balancing, however, a CH can 234 intentionally give up its role. Note that the traffic tends to 235 be concentrated on CHs and gateway nodes. 237 PC results very stable cluster architecture compared with 238 other clustering mechanisms even with the mobility. The reason 239 why PC is a stable is that PC does not occur cascading effects 240 because member nodes cannot override existing CHs. 242 Topology 1. 244 - : link between two nodes 246 I-D PC 14 November 2001 248 (1) (3)-4-(5)-6-(7)-8 (1), (3), (5), (7): CHs 249 4, 6, 8: Members 251 Topology 2. 253 (1)-3-(4)-5-(6)-7-(8) (1), (4), (6), (8): CHs 254 3, 5, 7: Members 256 Topology 3. 258 (1)-3-4-(5)-6-(7)-8 (1), (5), (7): CHs 259 3, 4, 6, 8: Members 261 Figure 1. An Example of Cascading Effect 263 For instance in Figure 1, let's assume that the "Lowest ID" 264 clustering algorithm [7] is used and node "1" moves toward 265 node "3" and becomes a neighbor node of node "3". Then, node 266 "3" should give up the role of CH since node "1" has the lower 267 node ID than node "3". If node "3" gives up the role of CH, 268 then cascading changes will occur. Eventually, the final 269 result will be Topology 2 in Figure 1. 271 In contrast, PC will stop the state change of node "4" since 272 node "4" already knows the existence of CH "5". Instead of 273 changing of the role, node "3" and "4" become distributed 274 gateway (DIST_GW) nodes. Therefore, PC results Topology 3 in 275 Figure 1. 277 gateway node 279 A gateway node of a cluster is one of members and a CH uses 280 this node to communicate with adjacent CHs. Finding enough but 281 minimal number of gateways in a distributed manner is a well- 282 known NP problem. This problem can be induced to the question 283 how a node (CH) chooses optimal dominant set of nodes that 284 cover all nodes that are within two-hops away from the node. 285 Many literatures [4, 5] have provided heuristics for that 286 problem. Those solutions, however, require periodic exchanges 287 of neighbor list. And the control overhead is tightly coupled 288 with the degree of neighbors. Passive Clustering, on the other 289 hand, suggests another heuristic that does not need periodic 290 neighbor exchanges in Chapter 5.4. 292 ORDINARY node 294 I-D PC 14 November 2001 296 A member that is not a gateway node is an ORDINARY node. 298 node 'A' is known to node 'B' 300 A node 'A' is known to node 'B' if node 'B' has directly (not 301 through multi-hop nodes) overheard packets from 'A'. 303 3. The Assumptions and Requirements 305 This section lists the assumptions and requirements of the underlying 306 networks of Passive Clustering. 308 Each MANET node that runs PC is equipped with one wireless media. 310 Each MANET node uses the omni-directional antenna. Each packet that a 311 node sends is broadcast into the region of its radio coverage. 313 Passive Clustering (PC) requires overhearing, intercepting, and 314 manipulating every IP packet. Furthermore, if there is a link between 315 two nodes, then the link is assumed to be "bi-directional". And the 316 maximum radio range of each node is required to be "homogeneous". 318 4. Basic Description and Conceptual Data Structures 320 The key idea of PC is to exploit on-going data packets and piggyback 321 "cluster-related" information such as the state of a node in a clus- 322 ter and an IP address of a node. Each node participates in clustering 323 by overhearing messages from neighbor nodes and piggybacking own 324 cluster information to outgoing packets. To attach cluster informa- 325 tion, PC adds only 8 or 16 bytes (based on IP V4) to each packet 326 using IP option field. 328 A node does not initiate clustering unless it has outgoing or incom- 329 ing packets. A node before joining a cluster is called the INITIAL 330 node. With incoming or outgoing packets, a node can participate in 331 clusters as a member or a CH based on the states of neighbor nodes. 333 When a node has a packet to send, this node can declare as a CH or a 334 gateway node by stamping its state to the packet. After a successful 335 transmission of that claim packet, every node in this sender's radio 336 coverage can learn the presence of the CH or the gateway node through 337 overhearing that packet. Neighbor nodes of the CH cannot declare as a 338 CH since only one CH is allowed in one cluster, but neighbor nodes of 339 a gateway node may declare as another gateway node based on "Gateway 340 Selection Heuristic" (chapter 5.4). 342 I-D PC 14 November 2001 344 To prevent isolated clusters, which consist of only one node, and 345 improve the connectivity of clusters, a node can pronounce as a CH 346 only after it has overheard packets from other nodes. In other words, 347 an INITIAL node cannot declare as the CH without receiving packets 348 from others. A node is called a "candidate CH" (CH_READY node) if it 349 knows more than one neighbor node that is not a CH. 351 Upon promiscuous reception of each packet from a neighbor node, every 352 neighbor node of the sender adjusts its state. 353 An INITIAL node can be a candidate CH if the sender is the non-CH 354 node. Otherwise, this node becomes a member of the new cluster that 355 the CH (sender of the packet) creates. 357 If a CH has heard from another CH, then they compete each other based 358 on the "Lowest ID Competition" (chapter 5.5). When a node fails to 359 keep the role of CH, it sends out a "CH Give-Up Message" (chapter 360 5.5.1) to notify neighbors of the role change. 361 A member node can be a gateway node or ORDINARY node based on "Gate- 362 way Selection Heuristic" (chapter 5.4). This heuristic reduces the 363 number of gateway nodes in an efficient way and supports distributed 364 gateway scheme. In brief, only one gateway node is allowed for each 365 pair of CHs and a CH should have more than two gateway nodes. Chapter 366 5.4.1 describes how to decide the role of each member. 368 PC maintains clusters using implicit timeout scheme. Without exchang- 369 ing neighbor information, a node 'A' assumes that another node 'B' is 370 out of its locality if 'B' did not send out any message longer than 371 timeout duration (CLUSTER_TIME_OUT). If a member node detects no live 372 CH (does not belong to any cluster), then it becomes the INITIAL node 373 and starts clustering from the beginning. The implicit timeout mecha- 374 nism, with reasonable offered load, works efficiently to detect 375 dynamic topology changes. 377 4.1. The States of Each Node 379 There are 2 internal and 5 external states: CH_READY and GW_READY are 380 internal states, and INITIAL_NODE, CLUSTER_HEAD, GW_NODE, DIST_GW, 381 and ORDINARY_NODE are external states. Note that a node uses the 382 internal states to represent the tentative role (candidate CH or can- 383 didate gateway node) of nodes. The internal states should be changed 384 to one of external states at sending a packet, so the internal state 385 of a node is not exposed to neighbor nodes. The description of each 386 state is as follows. 388 1. INITIAL_NODE 390 When a node is initialized (wakes up), the state of a node is 392 I-D PC 14 November 2001 394 set to the INITIAL_NODE. The state of a node that does not 395 belong to any cluster (no CH has not send out messages for CLUS- 396 TER_TIME_OUT) must be the INITIAL_NODE. A node is called an INI- 397 TIAL node if the state of this node is the INITIAL_NODE. 399 2. CLUSTER_HEAD 401 The state of a node is the CLUSTER_HEAD when a node is the CLUS- 402 TER HEAD. 404 3. FULL_GW 406 The state of a node is the FULL_GW when a node is the FULL_GW 407 node. A FULL_GW node should be a member of more than two clus- 408 ters at the same time so that this node can be an intermediate 409 node between two cluster heads. When a FULL_GW node sends out a 410 packet, it determines two CHs that this node connects and 411 announces the node IDs of two CHs. 413 4. ORDINARY_NODE 415 The state of an ORDINARY node. 417 5. GW_READY 419 The GW_READY is the internal state of a potential gateway 420 (FULL_GW or DIST_GW) node before this node sends out a packet. 421 To guarantee that a node who has declared earlier wins, a poten- 422 tial gateway keeps internal state until it actually pronounces 423 the role. This node is called GW_READY node hereafter. A 424 GW_READY node can change its state to ORDINARY_NODE if it has 425 known (overheard packets from) enough neighbor gateway nodes. 426 When a DIST_GW node sends out a packet, it announces the node ID 427 of primary CH and remote CH to which it knows a path through 428 another gateway. 430 6. CH_READY 432 The internal state of a potential CLUSTER HEAD before this node 433 has an outgoing packet. To guarantee that a node who has 434 declared earlier wins, a potential gateway keeps internal state 435 until it actually pronounces the role. This node is called 436 CH_READY node hereafter. A CH_READY node cannot declare as a CH 437 if it has received a packet from another CH. 439 7. DIST_GW 441 The state of a distributed gateway node is DIST_GW. A DIST_GW 443 I-D PC 14 November 2001 445 node is a gateway node that connects two clusters. It, however, 446 may not be directly reachable from one of two cluster heads of 447 two clusters (there are two intermediate gateway nodes between 448 two cluster heads). 450 A GW_READY node determines its final state just before it sends out a 451 packet. This node could be an ORDINARY, FULL_GW, or DIST_GW node 452 (chapter 5.4.3.2). Each internal state should be determined to any 453 external state at sending a packet and the external state is stamped 454 at the packet. Besides, each member may change its state upon receiv- 455 ing a packet from another node (chapter 5.1.1). 457 4.2. The Data Structures 459 Every node maintains 4 different lists: the list of CH (CLUSTER 460 HEAD), GW (Gateway (GW or DIST_GW) node), INITIAL (INITIAL node) and 461 NEIGHBOR (ORDINARY node). Each list is updated whenever a node has 462 received a packet from another node. 464 1. A list of CH 466 Whenever a node has received a packet from CLUSTER HEAD, it 467 updates or adds up information of that node to the list of CH. 468 The entry contains: 470 - NODE_ID: the node ID of the CH 472 - LAST_RECV_TIME: the current time when this node 473 has received a packet from the CH 475 The global variable no_of_CH represents the number of valid 476 ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries 477 of the list of CH. 479 2. A list of GW 481 This is a list of gateway nodes from which this node has heard. 482 The entry contains: 484 - NODE_ID: the node ID of the gateway node 486 - LAST_RECV_TIME: the current time when this node 487 has received this packet from the gateway node 489 - STATE: the cluster state of the gateway node 491 I-D PC 14 November 2001 493 (DIST_GW or FULL_GW) 495 - CH_ID_1: the node ID of first CH among the pair of CHs that 496 the gateway node has announced 498 - CH_ID_2: the node ID of second CH among the pair of CHs that 499 the gateway node has announced 501 The global variable no_of_GW represents the number of valid 502 ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries 503 of the list of GW. 505 3. A list of INITIAL 507 Whenever a node has received a packet from an INITIAL node, it 508 updates or adds up information of that node to the list of INI- 509 TIAL. The entry contains: 511 - NODE_ID: the node ID of the INITIAL node 513 - LAST_RECV_TIME: the current time when this node 514 has received a packet from the INITIAL node 516 The global variable no_of_IN represents the number of valid 517 ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries 518 of the list of INITIAL. 520 4. A list of NEIGHBOR 522 This is a list of ORDINARY nodes. The entry contains: 524 - NODE_ID: the node ID of the ORDINARY node 526 - LAST_RECV_TIME: the current time when this node 527 has received a packet from the ORDINARY node 529 - PRI_CH_ID: the node ID of primary CH. This field is 530 optionally used (e.g., when an ORDINARY node sends "HELLO" 531 messages, the scout message, etc.) 533 The global variable no_of_ON represents the number of valid 534 ((current time - LAST_RECV_TIME) < CLUSTER_TIME_OUT) entries 535 of the list of NEIGHBOR. 537 Note that PC uses the "implicit" timeout mechanism, where no explicit 539 I-D PC 14 November 2001 541 "timer" expires. Whenever a packet comes in, all out-of-date (current 542 time - LAST_RECV_TIME > CLUSTER_TIME_OUT) entries must be removed 543 from lists. 545 4.3. The Format of PC Header in IP Option Field 547 PC uses the IP option field to piggyback the information of clusters. 548 The basic format of IP option of PC is as follows: 550 0 1 2 3 551 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 552 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 553 | STA |G|H| RESERVED | 554 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 555 | Node ID | 556 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 557 | Options | 558 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 559 | ... | 560 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 562 STA 564 The field is used to specify the state of each node. 566 G 568 CH give-up field. 570 This field is used when a CH gives up its role and sends a "CH 571 Give-Up Message" (chapter 5.5.1) to inform neighbors of the 572 change. A node set this field as "TRUE" with "CH Give-Up Message. 573 Otherwise, the default value is "FALSE". 575 H 577 If this message is a "HELLO" message, the sender set this field 578 as "TRUE". Otherwise, the default value is "FALSE". 580 RESERVED 582 Reserved area. Must be set to "0"(zero). 584 I-D PC 14 November 2001 586 Node ID 588 The IP address of the sender node. This may be different to the 589 source address in the IP header. (based on IP V4) 591 Options 593 This field is used for a gateway node to announce two CHs. Also, 594 when a node sends "HELLO" message, this option field may contain 595 the node ID of primary CH of the sender node. If the sender 596 belongs to only one cluster, let's say the node ID of CH of that 597 cluster is "CH1", then the primary CH is CH1. Otherwise, the 598 sender can choose randomly one primary CH among all CHs that are 599 known to the sender. 601 The format of options used by a "FULL_GW" or "DIST_GW" node is as 602 follows: 604 0 1 2 3 605 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 606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 607 | CH_ID_1 | 608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 609 | CH_ID_2 | 610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 612 CH_ID_1 614 The IP address of first CLUSTER HEAD 616 CH_ID_2 618 The IP address of second CLUSTER HEAD 620 If this node is a FULL_GW node, then the order of "CH_ID_1" and 621 "CH_ID_2" can be reversed. If this node is a DIST_GW node, then 622 "CH_ID_1" should be the node ID of the primary CH of this node 623 and "CH_ID_2" should be the node ID of remote CH to which this 624 node relays messages from the primary CH. 626 5. The Detailed Algorithm 628 This section describes the detail algorithm of PC. 630 5.1. Packet Processing 631 I-D PC 14 November 2001 633 All functions related to clustering are called only when a packet 634 comes in or out. 636 5.1.1. Incoming packet Processing 638 PC requires "promiscuous" packet reception. Upon receiving a packet, 639 PC extracts IP option field that is used for PC protocol. If there is 640 no IP option in the packet, then PC just bypass that packet to the 641 proper application. 643 A node with INITIAL_NODE state changes its state to CH_READY only 644 when it has received a packet from the non-CH node. 646 A cluster member decides the state following "Gateway Selection 647 Heuristic" (chapter 5.4). 649 A CH competes with the other CH when a packet has arrived from 650 another CH based on "The Lowest ID Competition" rule (chapter 5.5). 652 A state transition by incoming packet (RECV_MSG) is as follows: 654 1. If RECV_MSG.STA == CLUSTER_HEAD then 656 If my state == CLUSTER_HEAD and my node ID > RECV_MSG.ID then 658 send CH Give-Up Message to member nodes (chapter 5.5.1) 660 Else If my state == CLUSTER_HEAD and my node ID < RECV_MSG.ID 661 then 663 RETURN // Do nothing 665 Add ClusterHead (chapter 5.3.1) 666 // Add this information to the list of CH and adjust its state 667 //as a member of the cluster 669 2. Else If RECV_MSG.STA == FULL_GW or RECV_MSG.STA == DIST_GW then 671 Add Gateway (chapter 5.3.2) 672 // Add the information to the list of GW and adjust its state 673 // if enough gateway nodes found, then this node can be an 674 // ORDINARY node 676 3. Else If RECV_MSG.STA == INITIAL_NODE then 678 Add Initial (chapter 5.3.3) 680 I-D PC 14 November 2001 682 // Add the information to the list of INITIAL 683 // and adjust its state 685 4. Else If RECV_MSG.STA == ORDINARY_NODE then 687 Add Neighbor (chapter 5.3.4) 688 // Add the information to the list of NEIGHBOR 689 // and adjust its state 691 If my state == INITIAL_NODE and RECV_MSG.STA != CLUSTER_HEAD then 693 change my state to CH_READY 695 5.1.2. Outgoing Packet Processing 697 When a packet is sent from the "Network" layer to the "MAC" layer, PC 698 changes all internal states (CH_READY or GW_READY) to external states 699 and adds IP option before it enqueues a packet to the data queue. PC 700 fills up IP option with the state of clusters (STA) and all other 701 field in IP option of PC as follows: 703 STA: my state (after changing the internal state to the 704 external state) 705 G: FALSE (TRUE when a node sends out "CH Give-Up Message") 706 H: FALSE (TRUE when a node sends out "HELLO" messages) 707 Node ID: my node ID 709 If this node is a gateway node (FULL_GW or DIST_GW node) 711 CH_ID_1: my_CH_ID_1 (the node ID of first CH for this node) 712 CH_ID_2: my_CH_ID_2 (the node ID of second CH for this node) 713 or my_REMOTE_CH (the node ID of remote CH for DIST_GW) 715 5.1.2.1. First Declaration Wins Rule 717 How stable and quick the clustering mechanism converges is a very 718 important feature that a clustering algorithm has to provide. "First 719 Declaration Wins" rule improves, compared with other mechanisms, the 720 clustering stability, speeds up converging time, and avoids the sta- 721 tionary requirement for neighbor learning and clustering phase. The 722 working mechanism of this rule is as follows: 723 When a candidate CH (CH_READY node) has packets to send, it change 724 its state to CLUSTER_HEAD and stamps cluster information to the out- 725 going packets that claims the role of CH. After a successful 726 transmission of that claim packet, every node in the sender's radio 728 I-D PC 14 November 2001 730 coverage can learn the presence of the CH through overhearing that 731 packet. 733 A declaration of the role as a gateway node follows the same rule, 734 "First Declaration Wins", but there is no explicit role give-up mes- 735 sage. 737 1. CLUSTER HEAD 739 A node whose state is CH_READY should change its state to CLUS- 740 TER_HEAD. 742 2. gateway (FULL_GW or DIST_GW) node 744 A node whose state is GW_READY should change its state to 745 FULL_GW, DIST_GW or ORDINARY_NODE (chapter 5.4.3.1). 747 5.2. Management 749 Each node changes its state if necessary only when it has outgoing 750 packets or incoming packets. 752 5.3. The Functions 754 5.3.1. Add ClusterHead 756 Add information of CLUSTER HEAD to a list of CH and delete old 757 entries from the list of CH (old entries: (current time - 758 LAST_RECV_TIME > CLUSTER_TIME_OUT)). 760 A DIST_GW node changes its state to GW_READY if the no_of_CH is 761 increased 763 Check Gateway (chapter 5.3.6) 764 // Check the number of gateway nodes and adjust state based on 765 // gateway selection heuristic 767 An INITIAL node changes its state to GW_READY or ORDINARY_NODE in 768 "ReCalculate Member State" (chapter 5.4.3.2) called by Check Gate- 769 way function 771 Check Initial (chapter 5.3.7) 772 // Check the number of INITIAL nodes 774 Check Neighbor (chapter 5.3.8) 776 I-D PC 14 November 2001 778 // Check the number of ORDINARY nodes 780 5.3.2. Add Gateway 782 Add FULL_GW or DIST_GW node's information to a list of GW and delete 783 old entries from the list of GW. 785 A FULL_GW node may change its state to GW_READY or ORDINARY_NODE, if 786 new gateway has announced the same pair of CHs and the node ID of new 787 gateway is less than own node ID. If this node found another pair of 788 CHs that is not announced by another FULL_GW node, then it simply 789 changes the pair of CHs (change my_CH_ID_1 && my_CH_ID_2 -- contains 790 two node IDs of announced CH pair). Otherwise it changes its state to 791 GW_READY. 793 Check ClusterHead (chapter 5.3.5) 794 // Check the number of CHs and adjust its state 795 // if no neighbor CH (no_of_CH == 0) , then becomes INITIAL node. 797 Check Initial (chapter 5.3.7) 799 Check Neighbor (chapter 5.3.8) 801 ReCalculate Member State (chapter 5.4.3.2) 802 // Adjust its state based on Gateway Selection Heuristic 803 // An ORINDARY node may change its state to GW_READY 804 // An GW_READY node may change its state to ORINARY_NODE 806 5.3.3. Add Initial 808 Add INITIAL node's information to a list of INITIAL node and delete 809 old entries from the list of INITIAL. 811 Check ClusterHead (chapter 5.3.5) 813 Check Gateway (chapter 5.3.6) 815 Check Neighbor (chapter 5.3.8) 817 5.3.4. Add Neighbor 819 Add ORDINARY node's information to a list of NEIGHBOR and delete old 820 entries from the list of NEIGHBOR. 822 Check ClusterHead (chapter 5.3.5) 824 I-D PC 14 November 2001 826 Check Gateway (chapter 5.3.6) 828 Check Initial (chapter 5.3.7) 830 5.3.5. Check ClusterHead 832 Delete old entries (OLD_CH) from the list of CH (old entries: (cur- 833 rent time - LAST_RECV_TIME > CLUSTER_TIME_OUT)). 835 Any member node changes its state to INITIAL_NODE if no_of_CH becomes 836 "0" (zero) 838 A gateway node changes its state to GW_READY if OLD_CH.NODE_ID equals 839 to my_CH_ID_1 or my_CH_ID_2. 841 5.3.6. Check Gateway 843 Delete old entries from the list of GW (old entries: (current time - 844 LAST_RECV_TIME > CLUSTER_TIME_OUT)). 846 ReCalculate Member State (chapter 5.4.3.2) 848 5.3.7. Check Initial 850 Delete old entries from the list of INITIAL (old entries: (current 851 time - LAST_RECV_TIME > CLUSTER_TIME_OUT)). 853 5.3.8. Check Neighbor 855 Delete old entries from the list of NEIGHBOR (old entries: (current 856 time - LAST_RECV_TIME > CLUSTER_TIME_OUT)). 858 5.4. Gateway Selection Heuristic 860 A gateway node is a bridge node between two clusters. A node that is 861 reachable from two CHs may declare its role as a FULL_GW node only if 862 this node has not heard from another FULL_GW node that had announced 863 the same pair of CHs. A node is a member of only one cluster can 864 declare as a DIST_GW node to improve the connectivity of the network. 866 This scheme guarantees that one cluster always has at least two 867 gateway nodes. 869 I-D PC 14 November 2001 871 The state of a node is re-calculated and updated whenever this node 872 overhears an incoming packet. 874 5.4.1. One Gateway Node per Each Pair of CLUSTER HEADs (CHs) 876 This scheme eventually allows only one FULL_GW node for each pair of 877 CHs. If two nodes declare concurrently as FULL_GW nodes with announc- 878 ing the same pair of CHs, then a node that has the higher ID may give 879 up FULL_GW role or change its pair of CHs. 881 A FULL_GW announces two IDs of CLUSTER HEAD when it has an outgoing 882 packet. 883 For example in Figure 2, (A) means that the node ID of that node is 884 "A" and [B,C] means that the node ID of two CHs that a FULL_GW node 885 has announced are "B" and "C". The connectivity matrix between two 886 nodes is on the right of figure. 888 GW: a FULL_GW node, NODE: a GW_READY node 890 1 2 3 4 5 6 7 891 GW (1)[4,7] CH (4) GW(3)[4,6] 1 1 1 0 1 1 0 1 892 NODE (5) 2 1 1 1 1 1 1 1 893 CH (7) NODE (2) CH (6) 3 0 1 1 1 1 1 0 894 4 1 1 1 1 1 0 0 895 5 1 1 1 1 1 1 1 896 6 0 1 1 0 1 1 0 897 7 1 1 0 0 1 0 1 899 Figure 2. An Example of FULL_GW Node 901 In this case, when NODE (5) has an outgoing packet, NODE (5) can 902 declare as FULL_GW for the pair of (CH (7), CH (6)) since there is no 903 FULL_GW for ((CH (7), CH (6)). 905 If NODE (2) and NODE (5) declare as FULL_GW nodes at the same time, 906 then NODE (5) will give up the FULL_GW role and become an ORDINARY 907 NODE after it has received a packet from NODE (2) because it has 908 larger ID than NODE (2) and there is no remained pair that is not 909 pronounced by another FULL_GW node. 910 If there is no GW (1), then NODE (5) can change the pair of CHs to 911 (CH (7), CH (4)) instead of (CH (7), CH (6)) when it has heard from 912 NODE (2). 914 A member node that has heard from CHs changes its state to 915 ORDINARY_NODE when this node can hear from more than two CHs at the 917 I-D PC 14 November 2001 919 same time and there is no left pair of CHs that is not announced by 920 other FULL_GW nodes. 922 5.4.2. The Distributed Gateway Selection Mechanism 924 We employ a heuristic to provide the distributed selection mechanism. 925 If a node has heard from only one CH and more than three gateway 926 nodes, then this node can be an ORDINARY node. And if a node that is 927 a member of only one cluster "C1" and it has overheard from more than 928 two DIST_GW nodes that are also the member of the same cluster C1, 929 then this node can be an ORDINARY node. Otherwise, this node changes 930 its state to GW_READY to declare as the DIST_GW node. 932 (=== : bi-directional link) 934 CH 1 ===\\ 935 // \\ GW 4 [1,5] === CH 5 936 // \\ // 937 DIST_GW 2 === NODE 3 939 Figure 3. An Example of a DIST_GW Node 941 Figure 3 shows an example of a DIST_GW node. The state of node "3" 942 should be GW_READY since only two gateway nodes (GW 4 and DIST_GW 2) 943 and one CH (CH 1) are known to this node. At sending a packet, node 944 "3" will be a DIST_GW node. 946 If a DIST_GW node has received a packet from another DIST_GW that has 947 announced the same pair of primary CH and remote CH, then the node 948 with lower ID wins. The node with higher ID changes its state to 949 GW_READY. 951 If an ORDINARY node receives a packet from DIST_GW node whose primary 952 CH is unknown to this node, then this node may change its state to 953 GW_READY (chapter 5.4.3.2). 955 5.4.3. The Procedure 957 5.4.3.1. The Processing of Outgoing Packets for a Member Node 959 At sending a packet "MSG", a node "P" with the state GW_READY changes 960 its state to ORDINARY_NODE, FULL_GW or DIST_GW as follows: 961 (1) no_of_CH >= 2 963 I-D PC 14 November 2001 965 If this node finds a pair of CHs that has not announced, then this 966 node becomes a FULL_GW node. If there is no gateway node that con- 967 nects one of clusters to which this node belongs to another cluster 968 that a DIST_GW has announced, then this node becomes the DIST_GW 969 node. Otherwise, it becomes the ORDINARY node. 971 The pseudo code is as follows: 973 For each pair of CHs known to P (ch1, ch2) 975 For each FULL_GW node "G" known to P 977 If G has announced the same pair of CH 978 break; 980 Else go to next FULL_GW node 982 If no FOUND G then 983 P changes its state to FULL_GW and 984 MSG.CH_ID_1 = ch1 & MSG.CH_ID_2 = ch2 985 my_CH_ID_1 = ch1 & my_CH_ID_2 = ch2 986 RETURN 988 Else go to next pair 990 If all pairs are announced then 992 For each DIST_GW node "DG" known to P 994 If DG.CH_ID_1 is equal to one of CHs known to P then 995 go to next DIST_GW node 997 Else 999 For each gateway node "G" except for DG 1001 If G.STATE == DIST_GW && G.CH_ID_2 == DG.CH_ID_2 then 1002 //there is a DIST_GW node that reaches remote CH 1003 break; 1005 Else If G.STATE == FULL_GW && 1006 G.CH_ID_1 (or 2) == DG.CH_ID_1 then 1007 break; 1009 Else go to next gateway node 1011 I-D PC 14 November 2001 1013 If no FOUND G then 1014 P changes its state to DIST_GW and 1015 MSG.CH_ID_1 = the node ID of primary CH 1016 MSG.CH_ID_2 = DG.CH_ID_1 1017 my_CH_ID_1 = the node ID of primary CH 1018 my_REMOTE_CH = DG.CH_ID_1 1019 RETURN 1021 Else go to next DIST_GW node 1023 If the state ID of P is GW_READY then 1024 P changes its state to ORDINARY_NODE 1026 (2) no_of_CH == 1 and the primary CH "CH1" (the cluster {CH1}) 1028 If there is no gateway node that connects CH1 to another CH (CH2) 1029 that a DIST_GW has announced, then this node becomes a DIST_GW 1030 node. If there is no known DIST_GW node in the same cluster {CH1}, 1031 then it becomes DIST_GW node. Otherwise, it becomes an ORDINARY 1032 node. 1034 The pseudo code is as follows: 1036 For each DIST_GW node "DG" 1038 If DG.CH_ID_1 == CH1 1039 then go to next DIST_GW node 1041 Else 1043 For each gateway node "G" 1045 If G.STATE== DIST_GW && G.CH_ID_1 == CH1 && 1046 G.CH_ID_2 == DG.CH_ID_1 then 1047 go to next DIST_GW node 1049 Else If G.STATE== FULL_GW && the pair of CHs of G 1050 is the same pair to (CH1, DG.CH_ID_1) then 1051 go to next DIST_GW node 1053 If no FOUND gateway node then 1054 P changes its state to DIST_GW and 1055 MSG.CH_ID_1 = CH1 1056 MSG.CH_ID_2 = DG.CH_ID_1 1057 my_CH_ID_1 = CH1 1058 my_REMOTE_CH = DG.CH_ID_1 1059 RETURN 1060 If the state of P is GW_READY then 1062 I-D PC 14 November 2001 1064 For each DIST_GW node "DG" known to P 1066 If DG.CH_ID_1 == CH1 then 1067 P changes its state to ORDINARY_NODE 1068 RETURN 1070 Else go to next DIST_GW node 1072 If the state of P is GW_READY then 1073 P changes its state to DIST_GW and 1074 MSG.CH_ID_1 = CH1 1075 MSG.CH_ID_2 = UNKNOWN 1076 my_CH_ID_1 = CH1 1077 my_REMOTE_CH = UNKNOWN 1079 Note that an ORDINARY node changes its state to GW_READY when it 1080 receives a packet from another node and detects the shortage of 1081 gateway nodes (chapter 5.4.3.2). Therefore, a CH always has more 1082 than two relay nodes. 1084 5.4.3.2. ReCalculate Member State 1086 An ORDINARY node may change its state to GW_READY if it detects the 1087 shortage of gateway nodes. 1088 A node with GW_READY state may change its state to ORDINARY_NODE if 1089 it detects the enough gateway nodes if there are more than two mem- 1090 bers. 1092 A member "P" changes its state as follows: 1094 If the state of P is neither FULL_GW nor DIST_GW then 1096 For each DIST_GW node "DG" 1098 For each gateway node "G" except for DG 1100 If G.STATE == DIST_GW && G.CH_ID_2 == DG.CH_ID_1 then 1101 //there is a DIST_GW node that reaches remote CH 1102 break; 1104 Else If G.STATE == FULL_GW && 1105 G.CH_ID_1 (or 2) == DG.CH_ID_1 then 1106 break; 1108 Else go to next gateway node 1110 If no FOUND G then 1112 I-D PC 14 November 2001 1114 P changes its state to GW_READY and RETURN 1116 If no_of_CH >= 2 1118 For each pair of CHs known to P (ch1, ch2) 1120 For each FULL_GW node "G" known to P 1122 If G has announced the same pair of CH 1123 break; 1125 Else go to next FULL_GW node 1127 If no FOUND G then 1128 P changes its state to GW_READY and RETURN 1130 Else If no_of_CH == 1 ("CH1": the node ID of this CH) then 1132 If no_of_GW >= 3 then 1133 P changes its state to ORDINARY_NODE and RETURN 1135 Else if no_of_GW == 2 then 1137 For each gateway node "G" 1139 If G.STATE != DIST_GW || G.CH_ID_1 != CH1 then 1140 P changes its state to GW_READY and RETURN 1142 Else go to next gateway node 1144 P changes its state to ORDINARY_NODE and RETURN 1146 Else P changes its state to GW_READY and RETURN 1148 5.5. The Lowest ID Competition 1150 The conflict of declarations of CLUSTER HEAD can happen due to the 1151 dynamic change of topology and packet delay. To resolve those con- 1152 flicts, a node that has the lowest ID among conflicted CHs kills 1153 other declaration. If a CLUSTER_HEAD has received a packet from the 1154 CH that has the lower ID than this node, then it gives up its role, 1155 changes its state following the Gateway Selection Heuristic (chapter 1156 5.4), and sends out a "CH Give-Up Message". 1158 If two gateway nodes have announced the same pair of CHs, then the 1159 node with higher node ID should yield to the other. 1161 I-D PC 14 November 2001 1163 5.5.1. The CH Give-Up Message 1165 After one CH gives up the CLUSTER HEAD role and has no outgoing 1166 packet, then it send extra "CH Give-Up Message" which set "G" as 1167 "TRUE" in the IP option. 1169 5.6. The Timeout Scheme 1171 Except "HELLO" message (chapter 5.7), there is no explicit timeout 1172 scheme. But every list is maintained by CLUSTER_TIME_OUT value. An 1173 entry that has not been updated for CLUSTER_TIME_OUT must be removed 1174 from a list. 1176 5.7. The "HELLO" message 1178 Each node may optionally send "HELLO" message at each CLUS- 1179 TER_TIME_OUT interval. Because our algorithm constructs the clusters 1180 in a passive way, the outcome of clusters depends on the traffic pat- 1181 tern. Therefore, it does not guarantee fully connected clusters at 1182 some cases. Even though the probability to lose the partial connec- 1183 tivity is very low, the make-up mechanism to guarantee the full con- 1184 nectivity is necessary at certain points. The "HELLO" scheme could be 1185 optionally used to support full connectivity (chapter 8.2 (1)). 1187 6. The Applicability 1189 PC can be used for an efficient flooding mechanism with allowing only 1190 non-ORDINARY nodes (CH, gateway nodes and INITIAL nodes) to be for- 1191 warding nodes. Since the ratio of ORDINARY nodes increases as the 1192 density of networks raises, PC works the more effectively as the net- 1193 work becomes denser. 1195 Many schemes such as routing protocols, service discovery or multi- 1196 cast can get benefits by employing PC because they use a flooding as 1197 the basic communication mechanism. This document, however, especially 1198 goes over the applicability to reactive routing protocols. 1200 6.1. The Applicability to On-demand Routing Protocols 1202 On-demand routing protocols have two phases (the route request and 1203 route reply phase) to setup a path. The incremental flooding and uni- 1204 cast are used for the route query and route reply phase respectively. 1205 The cluster architecture by PC can support a platform of efficient in 1207 I-D PC 14 November 2001 1209 the route request phase. Only non-ORDINARY nodes participate in 1210 flooding of route request phase and, as a result, are intermediate 1211 nodes of any path. Note that, in the complete cluster architecture, 1212 two nodes can be reached each other through CHs and gateway nodes. 1214 For example in Figure 4, node "E", "F", "B" and "G" will stop for- 1215 warding route queries since they are ORDINARY nodes. Eventually, the 1216 route reply will go through only non-ORDINARY nodes. 1218 (E) (F) 1219 +-+ + +-+ <- : route reply 1220 src <-- |A| <-- /C\ <--|D| <--dest A, D : CHs 1221 +-+ +-+ +-+ C : gateway nodes 1222 (B) (G) B, E, F, G: ORDINARY nodes 1224 Figure 4. An Example of the Efficient Flooding 1226 6.2. Protocol Characteristics 1228 * Does this protocol provide support for unidirectional links? (if 1229 so, how?) 1231 No. Bi-directional links are required. 1233 * Does the protocol require the use of tunneling? (if so, how?) 1235 No. 1237 * Does the protocol require using some form of source routing? (if 1238 so, how?) 1240 No. However, source routing could be used as a basic routing pro- 1241 tocol with passive clustering. 1243 * Does this protocol require the use of periodic messaging? (if so, 1244 how?) 1246 No. However, periodic HELLO messages could be used optionally to 1247 guarantee a fully-connected cluster architecture. 1249 * Does this protocol require the use of reliable or sequenced packet 1250 delivery? (if so, how?) 1252 No. However, the FIFO queue is required. 1254 I-D PC 14 November 2001 1256 * Does the protocol require link or neighbor sensing (if so, how?) 1258 No. However, neighbor sensing helps the clustering connectivity. 1260 * Does the protocol have dependence on a central entity? (if so, 1261 how?) 1263 No. All the functions are achieved in a distributed manner. 1265 * Does the protocol function reactively? (if so, how?) 1267 Yes. The formation of clusters is deferred until there is on-going 1268 data traffic. 1270 * Does the protocol function proactively? (if so, how?) 1272 No. 1274 * Does the protocol provide loop-free functions? (if so, how?) 1276 Yes. Passive clustering does not generate any packets that possi- 1277 bly occur a loop. 1279 * Does the protocol provide for sleep period operation? (if so, 1280 how?) 1282 No. In current version, no sleep mode is supported. 1284 * Does the protocol provide some form of security? (if so, how?) 1286 No. 1288 7. Suggested Parameters 1290 CLUSTER_TIME_OUT 2 seconds 1292 8. The Discussion and Implementation Consideration 1294 8.1. Problems with a Critical Path Loss 1296 This section discusses some of the problems that we have encountered 1297 during the design of PC. In particular, they are related to the issue 1298 of the network connectivity. 1300 * The Connectivity Problem 1302 I-D PC 14 November 2001 1304 Because PC constructs the cluster architecture in a passive way, it 1305 is possible to lose some critical paths. Figure 5 shows an example. 1307 (=== : bi-directional link) 1309 DIST_GW 1 ====== CH 2 ======= DIST_GW 3 \\ 1310 // \\ || GW 7 == CH 8 1311 // \\ || // 1312 DIST_GW 4 ===== ORDINARY 6 1313 \\ 1314 \\ 1315 NODE 5 1317 Figure 5. An Example of a Critical Path Loss 1319 In Figure 5, an ORDINARY node "6" has a critical path to node "5" 1320 and node "5" doesn't have outgoing packets. In this case, node "6" 1321 has no chance to get the knowledge from node "5", so node "6" will 1322 not forward flooding packets to node "5". As a result, node "5" 1323 can't hear a message from the cluster with CH "2". 1325 8.2. The Possible Solutions 1327 There are several possible solutions as follows: 1329 (1) The "HELLO" messages 1331 The periodic "HELLO" messages solve this problem. If node "6" sends 1332 "HELLO" message, then node "5" changes its state to CH_READY and 1333 declares as a CH when node "5" sends out a "HELLO" message. 1334 Finally, node "6" becomes a FULL_GW node which connects CH "2" and 1335 "5". 1337 All ORDINARY nodes announce the node ID of primary CH. Node "6" 1338 announces CH "2" when this node sends out "HELLO" messages. Let's 1339 assume that NODE "5" is the ORDINARY node and the primary CH of 1340 node "5" is node "9". After exchanges of the "HELLO" messages, node 1341 "5" and "6" detect that there is no gateway node that connects CH 1342 "2" and "9" (chapter 5.4.3.2). Therefore, node "5" and "6" change 1343 their states to GW_READY to become DIST_GW nodes. 1345 The periodic "HELLO" message avoids the connectivity problem, but 1346 it occurs extra overhead for exchanging packets. 1348 I-D PC 14 November 2001 1350 (2) An ORDINARY node should send at least one outgoing packet 1351 with active declaration of CH. 1353 An ORDINARY node should send out at least one packet after being 1354 the ORDINARY node. When an ORDINARY node sends out a packet, it 1355 stamps the node ID of primary CH to the packet. And if an INITIAL 1356 node has heard from another ORDINARY node, then it claims as a CH 1357 in an active way (sends explicit packet to declare) instead of a 1358 passive way. 1360 In the Figure 5, if node "5" has heard from node "6", then node "5" 1361 will declare actively as a CH. Then, node "6" changes its state to 1362 FULL_GW after it has received a declaration packet from CH "5". 1364 Suppose, node "5" is an ORDINARY node and has heard from node "6", 1365 then node "5" becomes DIST_GW node since there is no gateway node 1366 to connect two clusters. 1368 This solution, however, has a problem with the node mobility and 1369 new incoming nodes. For example, if node "5" wakes up after node 1370 "6" finally becomes the ORDINARY node, then the critical path from 1371 node "5" to "6" is still lost. 1373 (3) The scout messages 1375 An ORDINARY node sets the BIRTH_TIME to the current time when it 1376 changes its state to the ORDINARY_NODE. And, it sends out a "scout" 1377 packet to catch un-covered neighbors after T seconds from the 1378 BIRTH_TIME. A node that has received the scout packet reacts the 1379 same way to (2). 1381 Still, this solution has the same problem to (2). But, ORDINARY 1382 nodes can send out "scout" messages periodically to prevent men- 1383 tioned problems. 1385 8.3. Some Comments 1387 The problem of necessary gateway selection can be induced to the 1388 well-known set cover problem where a minimal set of gateway nodes 1389 that cover all two hops away neighbors. This problem is a NP complete 1390 problem with depending upon the quasi-stationary assumption to get 1391 the solution. 1393 Based on the quasi-stationary assumption, a set of necessary gateway 1394 nodes can be elected through the exchanges of neighbor lists or pre- 1395 known topology. 1396 However, the dynamic topology of the ad hoc networks challenges the 1398 I-D PC 14 November 2001 1400 basic assumption. In other words, without Oracle, the election algo- 1401 rithm to choose the set of necessary gateway nodes should be per- 1402 formed whenever the topology changes. This may cost huge overhead 1403 such as periodic exchanges of neighbor list, extra control packets to 1404 elect nodes, or extensive "HELLO" messages. 1406 Passive clustering, on the other hand, provides fully distributed, 1407 practical and very cheap in the sense of line overhead gateway selec- 1408 tion mechanism. 1410 In spite of possible cases (e.g., Figure 5) that lose critical paths, 1411 the extensive simulation studies show that the probability of such 1412 cases is extremely low in the fairly dense and loaded networks. 1414 Therefore, PC can be used as a practical clustering mechanism that 1415 provides well-partitioned groups regardless of the size, density, 1416 mobility, and the load status of the network. 1418 9. Authors' Addresses 1420 Yunjung Yi 1422 UCLA 1423 3771 Boelter Hall 1424 Los Angeles, CA 90095 1426 EMail: yjyi@cs.ucla.edu 1428 Taek Jin Kwon 1430 Telcordia Technologies, Applied Research 1431 NVC3X-317 1432 331 Newman Springs Rd. 1433 Red Bank, NJ 07701 1435 EMail: tkwon@research.telcordia.com 1437 Mario Gerla 1439 UCLA Computer Science Department 1440 3564 Boelter Hall 1441 Los Angeles, CA 90095 1443 EMail: gerla@cs.ucla.edu 1445 I-D PC 14 November 2001 1447 References 1449 1. T.J. Kwon and M. Gerla, Clustering with Power Control, Atlantic 1450 City, NJ (Nov. 1999). Proceedings of IEEE MILCOM'99. 1452 2. C.R. Lin and M. Gerla, Adaptive Clustering for Mobile Wireless Net- 1453 works (Sep. 1997). IEEE Journal on Selected Areas in Communica- 1454 tions, Vol. 15, No. 7, pp. 1265-1275. 1456 3. J.T. Tsai and M. Gerla, Multicluster, Mobile, Multimedia Radio Net- 1457 work (1995). ACM/Kluwer Journal of Wireless Networks, Vol.1, No.3, 1458 pp.255-65. 1460 4. Amir Qayyum, Laurent Viennot, Anis Laouiti, "Multipoint relaying: 1461 An efficient technique for flooding in mobile wireless networks," 1462 INRIA report (March, 2000). 1464 5. H.Lim and C. Kim,, "Flooding in wireless ad hoc networks," IEEE 1465 computer communications (2000). 1467 6. Scott Bradner, "Key words for use in RFCs to indicate requirement 1468 levels," IETF RFC 2119 (March , 1997). 1470 7. M. Gerla and J. Tsai, "Multicluster, mobile, multimedia radio net- 1471 works," ACM Baltzer Journal of Wireless Networks, Vol. 1. No. 3. 1472 (1995).