MANET Working Group Sanghyun Ahn Internet Draft University of Seoul Expires: November 4, 2013 Hyogon Kim Korea University May 13, 2013 Architecture for MANET Clustering draft-ahn-manet-clustering-architecture-01.txt Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. This document may not be modified, and derivative works of it may not be created, except to format it for publication as an RFC or to translate it into languages other than English. 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 material 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. This Internet-Draft will expire on November 2, 2013. Copyright Notice Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Ahn Expires November 4, 2013 [Page 1] Internet-Draft Architecture for MANET Clustering May 2013 Abstract This document describes the architecture for clustering in the MANET which can be an efficient communication structure for the case when MANET nodes have the tendency of forming groups. In this type of MANET, each group of nodes forms a cluster which is represented by a cluster head. In this draft, we define the terminology for the MANET clustering and the related communication procedure. Table of Contents 1. Requirements notation . . . . . . . . . . . . . . . . . . . . 3 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 4. Cluster Formation Procedure . . . . . . . . . . . . . . . . . 4 5. Data Exchange Procedure . . . . . . . . . . . . . . . . . . . 5 6. Cluster Reformation Procedure . . . . . . . . . . . . . . . . 5 7. Other Considerations . . . . . . . . . . . . . . . . . . . . . 6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 6 Ahn Expires November 4, 2013 [Page 2] Internet-Draft Architecture for MANET Clustering May 2013 1. Requirements notation The key words "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]. 2. Introduction A MANET is a wireless multihop network with a number of mobile nodes. Especially in a military or office MANET, nodes tend to form groups. In this type of MANETs, the traditional flat communication structure does not perform efficiently. Instead, the clustering architecture is a better communication structure since it fits well to the physical network topology of this type of MANETs [1]. We call the MANET employing the clustering architecture the MANET clustering. In a MANET with clustering, there can be a number of MANET clusters and a node called a cluster head (CH) represents each MANET cluster. A MANET cluster consists of a CH and a number of cluster members which are within the range of the cluster size of the CH. All CHs have the same fixed cluster size (in the number of hops). A node can be a member of only one cluster. That is, if a node is within the range of the cluster size of more than one CHs, it has to choose only one CH as its cluster head. In this draft, we define the terminology and the communication architecture for the MANET clustering. 3. Terminology Cluster Head The representative node of a cluster; the cluster head receives data from its cluster members and forwards the data to the cluster head of the cluster to which the destination belongs, and vice versa. Cluster Member The node belonging to a cluster Cluster Size The maximum number of hops from a cluster head to any one of its cluster members; in this draft, we assume that the cluster size is fixed to k Cluster Formation Procedure The procedure that cluster heads and cluster members are determined; composed of the cluster announcement phase and the cluster join phase Ahn Expires November 4, 2013 [Page 3] Internet-Draft Architecture for MANET Clustering May 2013 Cluster Announcement Phase The cluster head sends the Cluster Announcement message to its k-hop neighbors to indicate its willingness of forwarding data from its cluster members Cluster Join Phase The node wishing to act as a cluster member sends out a Cluster Join message to the cluster head upon receiving a Cluster Announcement message from the cluster head Data Exchange Procedure The procedure that a node sends data to another node via their cluster heads; data exchange between two nodes in different clusters must be forwarded by their cluster heads Cluster Reformation Procedure The procedure that a cluster head gives up its role and its members change clusters to belong 4. Cluster Formation Procedure For the MANET clustering to work, MANET nodes have to form clusters by following the cluster formation procedure which is composed of the cluster announcement phase and the cluster join phase. The cluster formation procedure is carried out either periodically or when a prespecified event occurs (e.g., when a CH gives up its role). After the cluster formation procedure, two nodes in different clusters can communicate via their CHs. The algorithm for a node to determine itself to be a CH is out of the scope of this draft. Once a node decides to beomce a CH, it sends out a Cluster Announcement message to its k-hop neighbors, where k is the cluster size. We call this phase the cluster announcement phase. Once a node receives a Cluster Announcement message, it replies back to the corresponding CH (i.e., the originator of the Cluster Announcement message) with a Cluster Join message, if it wishes to join the cluster announced by the Cluster Announcement message. If a node receives more than one Cluster Announcement messages, it has to reply back to only one CH by sending a Cluster Join message only to the chosen CH. We call this phase the cluster join phase. Steps (1) and (2) of figure 1 shows the message exchange scenario of the cluster formation procedure initiated by cluster heads n2 and n4 In this scenario, node n3 receives Cluster Announcement messages from both n2 and n4, and replies back only to n4. Ahn Expires November 4, 2013 [Page 4] Internet-Draft Architecture for MANET Clustering May 2013 n1 n2(CH) n3 n4(CH) (1) Cluster Announcement <-----------+-----------><-----------+ Phase (2) Cluster Join +-----------> +-----------> Phase (3) Data +===========> From n1 To n3 +========================> <===========+ Figure 1. A message exchange scenario of MANET cluster formation 5. Data Exchange Procedure Once cluster formation procedure is completed, the data sent from nodes in different clusters must be forwarded by their cluster heads. Step (3) of Figure 1 shows the message exchange scenario for data delivery from n1 to n3 via cluster heads n2 and n4. First, n1 sends a data packet to its CH n2 and n2 forwards it to the destination CH n4 and, finally, n4 forwards it to the destination node n3. In order for this data delivery to work, a source CH is required to know the destination CH. How to determine the destination CH will be defined later. If source and destination nodes are in the same cluster and reachable via 1-hop, then those nodes can directly communicate without the help of the cluster head. However, if they are more than 1-hop away, they must communicate via their cluster head even though they are in the same cluster. 6. Cluster Reformation Procedure The cluster reformation procedure can be initiated by either (i) a periodic CLAN message or (ii) a Cluster Giveup (CLGU) message. The cluster reformation procedure of the case (i) is the same as the cluster formation procedure in section 4. The cluster reformation procedure of the case (ii) is started when a CH broadcasts a CLGU message to its members. A CLGU message is generated by a CH when it faces some circumstances that it can not continue its role as a CH such as the energy depletion or some other events prespecified by a cluster management mechanism. Ahn Expires November 4, 2013 [Page 5] Internet-Draft Architecture for MANET Clustering May 2013 When a member receives a CLGU message from its CH, it decides whether it will become a CH or send a CLJN message to another CH. If it decides to become a CH, it has to go through the cluster formation procedure described in section 4. Otherwise, it sends a CLJN message to one of the CHs from which it has received CLAN messages recently. 7. Other Considerations TBD. References [1] I. G. Shayeb and et. al., "A Survey of Clustering Schemes for Mobile Ad-Hoc Network (MANET)," Americal Journal of Scientific Research, pp. 135-151, 2011. Authors' Addresses Sanghyun Ahn University of Seoul 90, Cheonnong-dong, Tongdaemun-gu Seoul 130-743 Korea Email: ahn@uos.ac.kr Hyogon Kim Korea University 145, Anam-ro, Seongbuk-gu Seoul 136-701 Korea Email: hyogon@gmail.com Ahn Expires November 4, 2013 [Page 6]