An Analysis upon Various Clustering Schemes and Its Effects on the Performances of Mobile Ad Hoc Networks

A Mobile Ad hoc Network (MANET) consists of a group of mobile nodes that self-configure to form a temporary network without the aid of a preset infrastructure or centralized management. Such networks are characterized by: dynamic topologies, existence of bandwidth constrained, variable capacity links, and energy con-strained operations and highly prone to security threats. Due to all these features routing is a major issue in mo-bile ad hoc networks. Routing in a network is the process of selecting paths to send network traffic. Routing can take place either in a flat structure or in a hierarchical structure. In a flat structure, all nodes in the network are in the same hierarchy level and thus have the same role. Although this approach is efficient for small networks, it does not allow the scalability when the number of nodes in the network increases. In large networks, the flat routing structure produces excessive information flow which can saturate the network. Hierarchical routing protocols have been proposed to solve this problem among others. This approach consists of dividing the network into groups called clusters. This results in a network with hierarchical structure. Different routing schemes are used between clusters (inter-cluster) and within clusters (intra- cluster). Each node maintains complete knowledge of locale information (within its cluster) but only partial knowledge about the other clusters. Hierarchical routing is a solution for handling scalability in a network where only selected nodes take the responsibility of data routing. However, hierarchical approaches undergo continual topology changes. Thus, topology management plays a vital role prior to the actual routing in MANET. Cluster based structure (hierarchical structure) in net-work topology has been used to improve the routing efficiency in a dynamic network. Structuring a network is an important step to simplify the routing operation in MANETs. Several algorithms based on clustering techniques have been proposed in the literature. The clustering consists of dividing the

the network functions. In particular, it allows the routing protocol to operate more efficiently by reducing the control traffic in the network and simplifying the data routing. Several clustering schemes have been proposed. These schemes have different characteristics and are de-signed to meet certain goals depending on the context in which the clustering is used (routing, security, energy conservation, etc.). Clustering protocols in the MIANET are classified based on their objectives. According to this criterion, clustering schemes for MANET can be grouped into six categories, as shown in Table 1. Dominating-Set-based (DS-based) clustering tries to find a DS for a MANET so that the number of mobile nodes that participate in route search or routing table maintenance can be reduced. This is because only mobile nodes in the DS are required to do so. Low-maintenance clustering schemes aim at providing stable cluster architecture for upper-layer protocols with little cluster maintenance cost .By limiting reclustering situations or minimizing explicit control messages for clustering, the cluster structure can be maintained well without excessive consumption of network resources for cluster maintenance. Mobility-aware clustering takes the mobility behavior of mobile nodes into consideration. This is because the mobile nodes' movement is the main cause of changes to the network topology .By grouping mobile nodes with similar speed into the same cluster, the intra cluster links can be greatly tightened and the cluster structure can be or respondingly stabilized in the face of moving mobile nodes. Energy-efficient clustering manages to use the battery energy of mobile nodes more wisely in a MANET. By eliminating unnecessary energy consumption of mobile nodes or by balancing energy consumption among different mobile nodes, the network lifetime can be remarkably prolonged. Load balancing clustering schemes attempt to limit the number of mobile nodes in each cluster to a specified range so that clusters are of similar size. Thus, the network loads can be more evenly distributed in each cluster. Combined-metrics based clustering usually considers multiple metrics, such as node degree, cluster size, mobility speed, and battery energy, in cluster configuration, especially in cluster head (CH) decisions. With the consideration of more parameters, CHs can be more properly chosen without giving bias to mobile nodes with specific attributes. Also, the weighting factor for each parameter can be adaptively adjusted in response to different application scenarios. Based on the neighborhood graph introduced by the NRP, We have developed a clustering protocol named "On- Demand Group Mobility-Based Clustering with Ability Definition guest node" (ODGM/GN). As a result, ODGM/GN maps varying physical node groups onto Clustering in the MANET is discussed. The proposed approach is introduced in the third section. In the fourth section, the evaluation results are presented. Finally, the conclusion will be discussed.

Wireless ad-hoc networks have some properties such as the dynamic network topology, limited bandwidth and energy constraint in the network as described by Kumar et al. Mobile ad hoc network (MANET) is useful for different purposes e.g. military operation to provide communication between squads, collaborative and distributed computing, wireless mesh control, wireless sensor networks, hybrid network, medical control etc. Kumar et al said ―routing protocol plays very important part in implementation of mobile ad hoc networks. The following are the main protocols used in routing: Proactive or table driven routing protocols and Reactive or on-demand routing protocols. DSR (Dynamic Source Routing) requires no periodic packets of any kind at any level within the network as stated by Johnson et al. DSR does not use any periodic routing advertisement, link status sensing, or neighbour detection packets, and does not rely on these functions from any underlying protocols in the network. This entirely on-demand behaviour and lack of periodic activity allows the number of overhead packets caused by DSR to scale all the way down to zero, when all nodes are approximately stationary with respect to each other and all routes needed for current communication have already been discovered also as stated by Johnson et al. As nodes begin to move more or as communication patterns change, the routing packet overhead of DSR automatically scales to only that needed to track the routes currently in use. In response to a single Route Discovery (as well as through routing information from other packets overheard), a node may learn and cache multiple routes to any destination. This allows the

since a node with multiple routes to a destination can try another cached route if the one it has been using should fail. This caching of multiple routes also avoids the overhead of needing to perform a new Route Discovery each time a route in use breaks. The operation of Route Discovery and Route Maintenance in DSR are designed to allow unidirectional links and asymmetric routes to be easily supported. In wireless networks, it is possible that a link between two nodes may not work equally well in both directions, due to differing antenna or propagation patterns or sources of interference as described by Johnson et al. DSR allows such unidirectional links to be used when necessary, improving overall performance and network connectivity in the system. DSR also supports internetworking between different types of wireless networks allowing a source route to be composed of hops over a combination of any types of networks available by Johnson et al. For example, some nodes in the ad hoc network may have only short-range radios, while other nodes have both short-range and long-range radios; the combination of these nodes together can be considered by DSR as a single ad hoc network. DSR is an on-demand routing protocol and cannot perform well in a large MANET and the reason is that it has scalability issues when the size of the network increases, mostly when there is node mobility simultaneously. Proactive routing requires control overhead for building and updating this table, having information about the state of the network. For on-demand routing protocols, routes are found when required; however this causes it to suffer significant route setup delay which becomes intolerable in the presence of both a large number of nodes movement. The fundamental idea of on-demand routing protocols is that, an initial node sends a route request and makes a decision based on the reply received, which may be sent by an intermediate mobile node. However, on demand routing algorithms have the disadvantage of increasing per-packet overhead. This per packet overhead reduces the available bandwidth for information transmission in the network. Due to the routine of dissemination of path requests (flooding), it is difficult to reduce the dissemination of packets unnecessarily. Management of large number of nodes is one of the essential issues ad-hoc network faces. The nodes of a wireless ad-hoc network are divided into numerous fragmented or intersecting clusters. Each cluster elects one node as the so-called cluster head and these distinct nodes are accountable for the routing process. Neighbours of cluster heads cannot be cluster heads as well. But cluster heads are able to communicate with each other by using gateway cluster heads as its neighbours or— when the clusters are disjoint—at least one cluster head and another gateway node.

The process that divides the network into interconnected substructures, called clusters. Each cluster has a particular node elected as cluster head (CH) based on a specific metric or a combination of metrics such as identity, degree, mobility, weight, density, etc. The cluster head plays the role of coordinator within its substructure. Each CH acts as a temporary base station within its cluster and communicates with other CHs. A cluster is there-fore composed of a cluster head, gateways and members node. Cluster Head (CH): it is the coordinator of the cluster. Gateway: is a common node between two or more clusters. Member Node (Ordinary nodes): is a node that is neither a CH nor gateway node. Each node belongs exclusively to a cluster independently of its neighbors that might reside in a different cluster. There are several algorithms in the literature for cluster heads election in mobile ad hoc networks: Lowest-ID, Highest-Degree, Distributed Clustering Algorithm, Weighted Clustering Algorithm (WCA) and Distributed Weighted Clustering Algorithm (DWCA). Clustering Concepts and Classification Definition Clustering is the process of dividing the network into interconnected substructures, named clusters. In a clustered network, nodes are divided into distinct logic groups (clusters), which are allocated geographically adjacent to each other. A typical cluster structure is shown in Figure 1.

As depicted, nodes are divided into logic groups (within the dotted lines) according to the rules of the clustering scheme. Nodes may be assigned a different role or function, such as cluster head, gateway or cluster

management functions and data-forwarding. A gateway is a node with inter-cluster links, which can forward information between clusters. There are clustering schemes that support cluster overlapping. In other words, two distinct clusters may share nodes. In this case, gateway nodes may be assigned to more than one cluster. Finally, cluster members, also referred as ordinary nodes, do not possess special cluster maintenance functions; they simply belong to a cluster.

A clustered topology in large MANETs enables efficient performance. The cluster structure provides several benefits, some of which mentioned bellow. Reduced Topology Information Due to the number of nodes inside of a cluster being lower than the number of nodes of the entire network, the clustering process eases the aggregation of topology information. Therefore, each node is only required to store a reduced portion of the entire network routing information. Routing Efficiency In a at architecture every node bears equal responsibility to act as a router for forwarding packets. The great amount of message flooding inherent to path discovery reduces the routing efficiency. A clustered structure improves routing efficiency and makes the path discovery easier. Efficiency and Stability In the perspective of a mobile node, the network appears smaller. Thus, when a mobile node disconnects or switches to another cluster, only the nodes residing in the corresponding clusters are required to modify their data structures. There are further advantages that are transversal to the mentioned benefits. As a product of clustering, the communication bandwidth, energy consumption, throughput and scalability are improved.

Clustering schemes can be classified according to different criteria. For example, depending on whether special nodes are required, such as cluster heads, clustering schemes can be classified as cluster head-based and non-cluster head-based. Or, taking into account the distance between node pairs within a cluster, schemes may be divided into 1-hop clustering and multi-hop clustering. Given the broad types and purposes of existing clustering solutions, this study performs a classification according to their main objectives. Following this criterion, the analysed clustering schemes for MANETs are grouped into five categories, as described in Table 2. In ID-Neighbour based clustering schemes, a unique ID is assigned to each node, and therefore each node in the network knowns the ID of its neighbours. The cluster head is selected based on criteria involving these IDs, such as the lowest ID or highest ID. The Connectivity-based The degree of node connectivity is usually a criterion from which clustering decisions are made. The Mobility-aware clustering takes the mobility behaviour of mobile nodes into consideration. The mobility of nodes is the main cause of changes in the network topology. Thus, by grouping nodes with similar movement speed and pattern into the same cluster, the intracluster connectivity can be better stabilized. Energy-efficient clustering is particularly.

focused in the energy of mobile nodes. By eliminating or balancing the energy consumption among different nodes, the network lifetime can be prolonged. Combined-weight clustering usually combines multiple parameters of the previous categories. A key advantage of this category is the configuration of the individual weight factors, which can be adaptively adjusted in response to different scenarios.

They are many clustering schemes for MANETs avail-able in the literature. To evaluate these schemes, we have to decide about the metrics to use for the evaluation. Based on our review and the work presented in, we summarize the comparison in Table 3. We can ob-serve in Table 3, the total overheads increase when clusters number is high and CHs change frequently. The weight based clustering scheme performs better than ID-Neighbor based, topology based, mobility based and energy based clustering. The weight based clustering scheme is the most used technique for CH election that uses combined weight metrics such the node degree, remaining battery power, transmission power, and node mobility etc. It achieves several goals of clustering: minimizing the number of clusters, maximizing lifespan of mobile nodes in the network, decreasing the total overhead, minimizing the CHs change, decreasing the number of re-affiliation, improving the stability of the cluster structure and ensuring a good resources management (minimize the band-width consumption) .

The protocol needs to generate non-overlapping clusters, i.e. each node is member of at most one cluster at the same lime. Otherwise, His routing and addressing mechanisms would liave to deal with the situation of multi-homed nodes. This is not the primary goal, as it leads to increased complexity. The clusters should be the basis for hierarchical routing. By using an auto-configuration mechanism, address prefixes are assigned to the clusters. The address prefix for a cluster is maintained by the CH. Each node in a cluster lias to know its address prefix. From this requirement, it follows that only the cluster members need to know their current CH, but not vice versa. We assume that each cluster can be identified network-wide by some unique value assigned to it. Tliis unique value could for example be the cluster head's MAC address. Consequently, a node can be in four different states: It can either be no member of any cluster (un-clustered), member of exactly one cluster (clustered), the CH of exactly one cluster (CH) or have another role (guest node). As a result of the nodes‘ movements, there are several possible events in the life cycle of a cluster (see Figure 2). Two nodes may meet and form a cluster, one of them declaring itself to be CH (event create). Nodes can be added to an existing cluster (event join). Or two clusters may be collapsed to one (event merge). If a cluster is split in two with one of the remaining parts haring no CH, the cluster has to be ―repaired‖ accordingly. Nodes may depart horn their clusters (event leave), and a cluster disappears when all members leave it. ODGM/GN is that it lias to be reactive. Most of the clustering protocols previously proposed hi the literature try to (pro-) actively discover a node‘s neighborhood by periodically broadcasting ―hello-beacons‖. By counting the hello‘s received from various nodes over longer time spans, it is possible to draw conclusions about the physical proximity of nodes .ODGM/GN aims to demonstrate that passive (reactive) monitoring of die data traffic is sufficient to detect node neighborhoods.

A lot of research had been conducted within the wireless mobile ad hoc network environments these recent years using numerous protocols. Mobile Ad hoc network has a brighter future and more prospects to deliver. A lot of computing devices are being developed day in day out with very high processing speeds at a faster rate. However, not much have been said or done for clustering systems in mobile ad hoc networks using AODV protocol. This paper presents on such kind. The study conducted in this paper reveals that the AODV protocol does not maintain any routing tables in the nodes but rather stores information about the network in a form of pointers for easy referencing which results in less overhead and more bandwidth availability. The AODV routing protocol also consumes less bandwidth, decreases overhead and able to support very large number of mobile nodes in a congested and clustered network. As a result, it enhanced mobile nodes life time and performance in clustering systems within MANETs. In this survey, we first presented fundamental concepts about clustering, including the definition of clustering, design goals and objectives of clustering schemes, advantages and disadvantages of clustering, and cost of network clustering. Then we classified clustering schemes into five categories based on their distinguishing features and their objectives as: Identifier Neighbor based clustering, Topology based clustering,

clustering schemes which help organize MANETs in a hierarchical manner and presented some of their main characteristics, objective, mechanism, and performance.

Abolhasan, Mehran; Wysocki, Tadeusz; and Dutkiewicz, Eryk. (2004). ―A Review Of Routing Protocols For Mobile Ad Hoc Networks,‖ Elsevier‘s Ad Hoc Networks, Vol. 2, Issue 1, January 2004, pp. 1-22. B. A. Correa, R.C. Hincapie and Laura Ospina (2007). ―Survey on Clustering Techniques for Mobile Ad Hoc Networks,‖ Revista Facultad de Ingenierí，No. 41. B. Maqbool, M. A. Peer (2010). ―Classification of Current Rout-ing Protocols for Ad Hoc Networks,‖ IJCA. C. Konstantopoulos, D. Gavalas and G.Pantziou (2008). ―Clus-tering in Mobile Ad Hoc Networks through Neighbor-hood Stability-based Mobility Prediction,‖. Cook, Jason L. and Ramirez-Marquez, Jose E. (2006). Mobility and reliability modeling for a mobile ad-hoc network. (In Press, IIE Transactions). Ghosh, R.K., Garg, Vijay, Meiti, M.S, Raman, S., Kumar, A., and Tewari, N. (2006). ―Dense cluster gateway based routing protocol for multi-hop mobile ad hoc networks,‖ Ad Hoc Networks, Volume 4, pp. 168-185. J.Y. Yu and P.H.J. Chong, "3hBAC (3-hop between Adjacent CHs): a Novel Non-overlapping Clustering Algorithm for Mobile Ad Hoc Networks", in Proc. IEEE Pacrim'03, vol. 1, Aug. 2003, pp. 318-21. Kevin Fall and Kannan Varadhan (2001), Editors, ―Ns notes and documentation‖, The VINT Project, UC Berkeley, LBL, USC/ISI, and Xerox PARC, Viewed on March 04, 2013 http://www.isi.edu/nsnam/ns Luo, Jun; Eugster, Patrick Th.; and Hubaux, Jean-Pierre. (2004). ―Probabilistic Reliable Multicast In Ad Hoc Networks,‖ Ad Hoc Networks, Vol. 2, Issue 4, pp. 369-386. M. Chatterjee, S. K. Das, and D. Turgut (2000). "An On-Demand Weighted Clustering Algorithm (WCA) for Ad hoc Networks", in Proc. IEEE Globecom'00, pp. 1697-701. Cluster Based Routing Protocol for Manets,‖ World Academy of Science, Engi-neering and Technology 75, pp. 1167-1171. O. Flauzac, B. S. Haggar and F. Nolot (2009). ―Self-stabilizing Clustering Algorithm for Ad Hoc Networks,‖ ICWMC, No. 24-29. P. Basu, N. Khan, and T. D. C. Little (2001). "A Mobility Based Metric for Clustering in Mobile Ad Hoc Networks", in Proc. IEEE ICDCSW' 01, Apr. 2001, pp. 413-18. S. A. Ade and P. A. Tijare (2010). ―Performance Comparison of AODV, DSDV, OLSR and DSR Routing Protocols in Mobile Ad Hoc Networks,‖ International Journal of In-formation Technology and Knowledge Management, Vol. 2, pp. 545-548. X. Cheng, X. Huang, and D.Z. Du. (2013). Ad Hoc Wireless Networking. Network Theory and Applications. Springer US, ISBN 9781461302230. URL https://books.google.pt/books?id=q5HbBwAAQBAJ. 30 Y.Y. Su, S.F. Hwang, and C.R. Dow (2008). ―An EfficientClus-ter-Based Routing Algorithm in Ad Hoc Networks with Unidirectional Links,‖ Journal of Information Science and Engineering 24, pp. 1409 1428. Y.Z.P. Chen and A. L. Liestman (2002). "Approximating Minimum Size Weakly- Connected Dominating Sets for Clustering Mobile Ad Hoc Networks", in Proc. 3rd ACM Int'l. Symp. Mobile Ad hoc Net & Comp, pp. 165- 72. Yuh-Ming Cheng (2009). Using zigbee and room-based location technology to constructing an indoor location-based service platform. In Intelligent Information Hiding and Multimedia Signal Processing, 2009. IIH-MSP '09. Fifth International Conference on, pages 803 {806, sept. 2009. doi: 10.1109/IIH-MSP.2009.106. 61

Associate Professor, Department of Computer Engineering, SSAIET, Kanpur