American Journal of Scientific Research ISSN 1450-223X Issue 20(2011), pp.135-151 © EuroJournals Publishing, Inc. 2011 http://www.eurojournals.com/ajsr.htm

A Survey of Clustering Schemes for Mobile Ad-Hoc Network (MANET)
Ismail Ghazi Shayeb Albalqa Applied Univesity, Amman, Jordan E-mail: ismail@bau.edu.jo AbdelRahman Hamza Hussein Jearsh University, Jearsh, Jordan E-mail: Abed_90@yahoo.com Ayman Bassam Nasoura Jearsh University, Jearsh, Jordan E-mail: nassuora@yahoo.com Abstract Clustering has been found to be an effective means of resource management for MANETs regarding network performance, routing protocol design, Quality of Service (QoS) and network modeling though it has yet to be refined to satisfy all the issues that might be faced by choosing this approach. Scalability is of particular interest to ad hoc network designers and users and is an issue with critical influence on capability and capacity. Where topologies include large numbers of nodes, routing packets will demand a large percentage of the limited wireless bandwidth and this is exaggerated and exacerbated by the mobility feature often resulting in a high frequency of failure regarding wireless links. In this paper we present acomprehensive survey and classification of recently published clustering algorithm, which we classify based on their objectives. We survey different clustering algoirthm for MANET's; highlighting the defining clustering, the design goals of clustering algorithms, advantages of clustering for ad hoc networks, challenges facing clustering including cost issues and classifying clustering algorithms as well as discussion on the objectives and features of various clustering schemes presented in a comprehensive survey of the related literature.

1. Introduction
Without using any existing infrastructure or centralised administration a Mobile Ad-hoc Network (MANET) consists of wireless mobile nodes that dynamically form a temporary communication network resulting in a rapidly changing network topology subject to swift changes to which it must react in order to continue effectively. This dynamic topology, varied/limited mobile node capability and limitations of link bandwidth for MANET pose scalability problems that are not just a challenge but a threat to the success of widespread use of MANETs. The scalability issue of MANET is ordinarily addressed through a hierarchical approach that sections the network into clusters. This way it is easier to follow the smaller, rationally separate, clusters and their content nodes’ movements, mergers, departures and capabilities as well as the overall cluster topology.

A Survey of Clustering Schemes for Mobile Ad-Hoc Network (MANET)

136

Scalability is of particular interest to ad hoc network designers and users and is an issue with critical influence on capability and capacity. Where topologies include large numbers of nodes, routing packets will demand a large percentage of the limited wireless bandwidth and this is exaggerated and exacerbated by the mobility feature often resulting in a high frequency of failure regarding wireless links. To overcome such barriers to success and address the issues of scalability and maintenance of MANETs it is essential, “to build hierarchies among the nodes, such that the network topology can be abstracted. This process is commonly referred to as clustering and the substructures that are collapsed in higher levels are called clusters.” (Yuanzhu et al., 2004). Increasing network capacity and reducing the routing overhead through clustering brings more efficiency and effectiveness to scalability in relation to node numbers and the necessity for high mobility. The manager node- CH (Clusterhead) - in clustering has responsibility for many functions such as cluster maintenance, routing table updates, and the discovery of new routes. However, the recurrent changes faced by the clusterhead can lead to losing stored routing information, route changes between node pairs and ultimately impacts on the overall performance of the routing protocol because of cluster structure instability. For these reasons this research will focus on how to elect a clusterhead to keep the stability of network topology. This paper will address the following: defining clustering, the design goals of clustering algorithms, advantages of clustering for ad hoc networks, challenges facing clustering including cost issues and classifying clustering algorithms as well as discussion on the objectives and features of various clustering schemes presented in a comprehensive survey of the related literature. Attention will be given to low maintenance clustering, mobility aware clustering, energy efficient clustering, load balancing clustering and combined metrics based clustering.

2. Clustering Defined
In mobile ad hoc network references, clustering can be defined as a notional arrangement of the dynamic nodes into various groups. These virtual collections of nodes are grouped together regarding their relative transmission range proximity to each other that allows them to establish a bidirectional link. The diameter size of the clusters determines the control architectures as single-hop clustering and multi-hop (K-hop) clustering. In single-hop clustering every member node is never more than 1-hop from a central coordinator - the clusterhead. Thus all the member nodes remain at most two hops distance away from each other within a logical cluster. In multi-hop clustering, the limitation or restriction of an immediate proximity to member nodes from the head is removed, allowing them to be present in serial k-hop distance to form a cluster (Angione et al., 2007). A typical mobile ad hoc network is illustrated in Figure 1 with flat and cluster structure. The small circles in the Figure 1 represent the individual wireless nodes in the network and the lines joining the circles show the sequential single hops of the wireless link among the wireless nodes. Each node is identified with an ID number (i.e.1–16) and Figure 1(a) illustrates each node bearing equal responsibility in its role as a router for forwarding packets to every other node in a flat architecture MANET.

137

Ismail Ghazi Shayeb, AbdelRahman Hamza Hussein and Ayman Bassam Nasoura
Figure 1: Nodes in flat and cluster structure. (a) Flat structure. (b) Cluster structure

This type of arrangement is prone to an inundation of information known as message flooding which offers better routing efficiency but significantly diminishes the Medium Access Control (MAC) layer efficacy (Perkins, 2008). Using clustering schemes, improved spatial reuse, scalability, throughput and energy efficiency are achievable from better protocol performance of the MAC layer. At the network layer, clustering helps improve routing through reduction of the routing table size and a decrease in transmission overhead (resultant of routing table updates) following topological changes. The condensing and the ability of each node to store only fractional amounts of data (of the total network routing information) achieved through clustering helps aggregate topology information. (Inn & Winston, 2004). Clustering schemes generally utilize three types of nodes which are chosen to assume different roles according to specific criteria briefly outlined below: Clusterhead nodes: for any efficient cluster (subsets of nodes in a network satisfying a particular property) operation there must be a support or backbone to sustain all essential control functions such as channel access, routing, calculation of the routes for longer-distance messages, bandwidth allocation, forwarding inter-cluster packets, power control and virtual-circuit support (Ohta et. al, 2003). This support or backbone takes the form of connected clusterheads, in managerial role; linked either directly or via gateway nodes and they will have the subordinate nodes of that cluster linked to them. Another function of clusterheads is internal node communication, to forward intercluster messages. To send a packet an ordinary node must first direct it to its ‘superior’ its directly connected clusterhead. Should the receiver share the same cluster location, clusterhead will direct the packet to it. However, should the receiver be in a different cluster location, clusterhead will route it to another clusterhead (directly) connected to the receiver and the new clusterhead then directs it to the final destination (Chen & Liestman, 2003). Cluster Gateway Nodes: Is a node that works as the common or distributed access point for two clusterheads. When a node remains within the transmission range of two clusterheads as the node 2 in Figure 1(b) it is called as the ordinary gateway for two corresponding clusters. And a node having one clusterhead as an immediate neighbor in addition to which it can reach a second clusterhead in two hops as node 5 or 6 is a distributed gateway that is linked to another distributed gateway of other cluster. Both of the distributed gateways provide the path for the inter-cluster communication (Purtoosi et al., 2004). Ordinary nodes (cluster member): As the name suggests, ordinary nodes do not perform any other function beyond a normal node role. They are members of an exclusive cluster independent of neighbors residing in a different cluster.

A Survey of Clustering Schemes for Mobile Ad-Hoc Network (MANET)

138

3. Design Goals of Clustering Algorithm
Implementing MANETs presents an immense challenge that cannot be met solely by the design goals of traditional or conventional networking applications (Amis et al., 2000). Clustering algorithms are crucial to the design if the aim to create an invisible global infrastructure is ever to be realized where mobile devices can communicate with each other effectively, efficiently, reliably and wirelessly without loss of connectivity, data or huge amounts of energy. 3.1. Cost of Clustering Clustering is recognized as a vital element in ad hoc network topology design but there are often essential communication and processing tasks required that demand resources to augment the creation and facilitation of clustering topology that incur costs beyond data transmission or processing tasks. Communication demands increase with the network size and as it grows bigger so the amount of bandwidth consumed by it is more. The payoff for scalability from clustering is at the expense of the amount of available bandwidth for the transmission of data. 3.2. Load Balancing Where CHs perform data processing or significant intra-cluster administration tasks an even node distribution among the clusters is often desirable in order for the CHs to have a balanced the load so that expected performance goals are not compromised. Load balancing is a particular issue for MANETs and the establishment of equally sized clusters offers energy savings and thus prolongs the network lifetime rather than employing a subset of high rate CHs that could expire too early. Even node distribution can also influence data delay (Gayathri et al., 2007). 3.3. Clustering Formation The clustering concept offers amazing potential for MANETs but their formation needs careful consideration as the variety of applications using clustering may require different priorities in the node arrangements, their size and ideal parameters for the style of configuration (Yang & Zhang, 2007). 3.4. Real-Time Operation Data lifespan is another consideration that may, or may not, be pertinent to a particular application. For some, receipt of data only is adequate for analysis and delay is not a significant issue whereas it is absolutely imperative that military tracking or emergency services applications receive real-time data (Chlamtac et al., 2003). In tailoring a clustering algorithm, delay created by the clustering scheme itself and the time required for cluster recovery mechanisms must also be taken into consideration for the particular application. 3.5. Maximising Network Longevity The energy constraints of nodes affecting the network’s lifetime is of particular importance to MANET applications in hostile environments. Where CHs are resource-rich compared to other nodes, it becomes essential to reduce the energy requirements of intra-cluster communication (Al-Karaki et al., 2004) by placing CHs close to most of the nodes in its cluster where possible or through load balancing, as mentioned earlier. Also worthy of consideration is combined clustering and route setup to maximize a network’s lifetime or adaptive clustering to attain network longevity (Younis et al., 2005). 3.6. Maintenance Mechanisms There are several situations that might provoke link failure in MANETs – the physical mobility and nomadic nature of some devices, node death and interference. Clustering schemes need to have link

139

Ismail Ghazi Shayeb, AbdelRahman Hamza Hussein and Ayman Bassam Nasoura

recovery mechanisms in place in order to restore dependability of function and reliability of data communication. 3.7. Connectivity and Reduced Delay Outside of satellite links for very long-haul communication capabilities inter-CH connectivity is vital in many applications especially when CHs are selected from the nodes population. The connectivity goal for better message broadcasting, say, might be achieved through the provision of a path simply CH-CH ensuring the availability or it might be more limiting through a determination of path length boundaries (Dai & Wu, 2005). In setups where some of the nodes adopt the CH role, “…vertices of a connected dominating set induce a connected sub-graph that can be used as a virtual backbone so that broadcast redundancy is reduced significantly.” the connectivity objective makes network clustering one of the many variants of the connected dominating set problem in unit disk graphs (UDGs) and when data latency is a concern and packets have tight arrival deadlines, intra-cluster connectivity requires greater attention. Delay is typically factored in by putting a ceiling limit on the number of hops ‘‘K’’ permitted on data paths. K-hop clustering is K-dominating set problem (Garcia et al., 2003). 3.8. Quality of Service (QoS) There has to be an overview of QoS to determine the efficacy of MANET requirements regarding communication overhead. Node mobility can, in hierarchical structures, cause topology changes (link/cluster additions/deletions) to spread up to any level. Research has revealed (Liu et al., 2002) that MANETs respond better to a ‘virtual backbone’ (VB) made up of a small set of dynamically selected nodes among which all control messages for service discovery are transferred. The effect is to create a partitioning that produces virtual domains with each possessing its own home VB and resultant in cost savings. “This is because the queries involve only message exchanges among the VB nodes and the QoS (path latency) information is shared by the nodes in the same virtual domain; for denser node distributions, more nodes could be accommodated in one cluster and the average cost per query is thus reduced.” (Liu et al., 2002) Implementations can of course have great variations in their requirements and application in terms of the metrics so the design process should be given careful consideration to these elements.

4. Advantages of Clustering Structure
The cluster architecture in MANET with a large number of mobile terminals ensures efficient performance. The cluster structure provides a certain amount of benefits, some of which are mentioned below: 4.1. Aggregation of Topology Information Due to of the fact that the number of nodes of a cluster is lower than the number of nodes of the whole network, this way the clustering process assists in aggregating topology information. Thus, with this system in place now each node is only required to store a small portion of the entire network routing information (Chinara & Rath, 2009). 4.2. Efficiency and Stability The significant quality of a cluster structure is that it causes a MANET to seem smaller and more stable in the aspect of each mobile terminal. So, now in this system, when a mobile node switches its attaching cluster, only mobile nodes residing in the corresponding clusters are required to modify their data structures (Mai et al., 2009; El-Bazzal et al., 2006).

A Survey of Clustering Schemes for Mobile Ad-Hoc Network (MANET) 4.3. Communication Coordination

140

The process of clustering limits the reach of inter-cluster interactions to clusterheads and also averts unnecessary exchange of messages amongst the mobile nodes and thus can also conserve communication bandwidth. 4.4. Routing Efficiency In flat architecture of MANET every node bears equal responsibility to act as a router for routing the packets to every other node so a great amount of message flooding takes place in order to obtain better routing efficiency. In return, such message flooding reduces the MAC layer efficiency to a certain extent. Cluster structure can be one possible solution to improve such MAC layer efficiency and makes the routing process easier (Sucec & Marsic, 2004). 4.5. Spatial Reuse of Resources A cluster increases the system capacity; by the way that the information is stored once on the clusterhead, which facilitates the spatial reuse of resources. Two clusters can distribute a similar frequency or code set if they are not adjoining clusters, this can be facilitated with the non-overlapping multi-cluster structure. Likewise, there can be a better coordination by a clusterhead of its transmission with the assistance of a specialized mobile node residing in it. This change in the existing system can save much of the resources, which are used for retransmission resulting from decreased transmission collision (Tolba et al., 2007).

5. What is the Cost of Clustering?
Costs in clustering, in terms of expenditure rather than energy usage and bandwidth absorption, can escalate when attempts to improve scalability are factored in. The advantages of extra node numbers and increased mobility capability can be outweighed by the construction and maintenance costs (which grow exponentially) when compared to the expense of a flat based MANET. The costs incurred have to be justified against the efficacy of a clustering approach. The pros and cons of cluster-based MANET can be extracted from quantitative and qualitative evaluation of diverse aspects of clustering schemes explained below (Jane & Peter, 2005; Chinara & Rath, 2009): • The dynamic nature of cluster structures often requiring explicitly commanded control message exchanging between pairs of mobile nodes demands considerable maintenance. Such information transfer, vis-à-vis clustering, will increase significantly and constitute hasty alterations involving excessive numbers of mobile nodes in the underlying topology that ultimately results in greedy consumption both of bandwidth and mobile node energy. This ‘greed’ can make the implementation of upper-layer applications difficult because of the subsequent scarcity of existing resources or the lack of support available from associated mobile nodes (Chen & Liestman, 2002; Wang & Olariu, 2005). • On occasion, total reconstruction of a cluster structure over a whole network may have to take place when some local events occur, e.g. the movement or ‘death’ of a mobile node that necessarily results in a quantity of clusterhead re-election (re-clustering) (Yu & Chong, 2003; Kwon et al., 2003). When the behavior or action of one element impacts on another to initiate neighboring radial consequence a ripple effect is created and this occurs when re-clustering arouses clusterhead re-election over the network (Inn & Winston, 2004) potentially affecting optimal performance of upper-layer protocols. • As most schemes divide clustering into two phases, formation and maintenance, there is an assumption that mobile nodes remain static while cluster formation is in progress (Angione et al., 2007). During initial cluster formation a mobile node has options to decide to become a clusterhead following specific information exchange with its neighbors and assess its

141

Ismail Ghazi Shayeb, AbdelRahman Hamza Hussein and Ayman Bassam Nasoura

possession of some particular attribute in that neighborhood. The assumption therefore is that there must be a period of stasis wherein each mobile node may accrue accurate information from neighboring nodes, thence allowing the initial cluster structure to be formed with some explicit characteristics. However, this scenario may not be applicable in real terms where mobile nodes might always be randomly in movement (El-Bazzal et al, 2006). • Another metric is the computation round – how often (or how many ‘rounds’ or ‘rotations’) it takes for a cluster formation procedure to complete. This is an important metric for those schemes that rely on a period of stasis assumption as the more rounds required for cluster formation, it follows logically, the longer is the required stasis period for mobile nodes. Many clustering schemes might be able to perform their cluster formation procedure in parallel with the whole network, resulting in fast time convergence for cluster formation. However, MANET topology undergoes recurrent changes with the movement of mobile nodes. Not all mobile nodes can necessarily determine their status simultaneously in only one round and may require a differing number of subsequent rounds (depending on their role and decision) to complete the initial cluster construction. The algorithms for these schemes cannot be bound by specific timings and there may be great disparity between various network topologies. This, the requisite explicit control message exchange, the re-clustering ripple effect, and the period of stasis assumption regarding cluster formation make up the chief costs of cluster-based MANETs compared to flat structure MANETs. The costs of clustering elements are summarized in Figure 2.

6. Categorisation of Clustering Structure
The clustering structure of MANETs may be classified according to various criteria such as clusterhead-based clustering/non clusterhead-based clustering (Hou & Tsai, 2001) with specific interest in the role of special function nodes (CHs), single-hop clustering/multi-hop clustering (Chinara & Rath, 2009) with focus on the distance between node pair hop distance; clustering protocols have different classifications also dependent on different criteria such as objectives that identify them characteristically into various categories (Angione et al., 2007; Yu & Chong, 2003). Classifying the clustering protocols based on their objectives, the proposed MANET clustering schemes may be categorised into eight distinctive groups (Chinara & Rath, 2009; Jane & Peter, 2005). Dominating-Set-based (DS-based) clustering endeavors to determine the DS for a MANET where the number of mobile nodes participant in route search or routing table maintenance can be reduced as their function becomes ‘familiar’ and only DS mobile nodes are required to perform them (Cokuslu & Erciyes, 2007; Wu & Li, 1999). Flooding-based clustering addresses MANETs’ characterised by scant bandwidth, radio interference issues and no fixed infrastructure, circumventing the need for more efficient (specified) techniques required of complex protocols. Flooding, as the term suggest, is the dissemination of information (overall and without explicit direction) that covers all the nodes in the network regardless. Each node redistributes the all of the information to all of its neighbours until there is inundation of the entire network without any computation requirements or maintenance of routing tables, thus avoiding network delay. For some, the ‘flooding’ may be based on specific, tailored criteria where it is perhaps limited to only a set of nodes instead of blanket network coverage (Amis et al., 2000). Channel-based clustering segregates control channels and data channels for MANETs (that have no centralised control) as separate out-of-band signaling is preferential for these types of networks. The control channel exchanges instructions and the data channel transmits information and by creating a bi-channel structure the mobile node can more efficiently schedule transmissions and reduce collisions overhead (Cai et al., 2003). Low-maintenance clustering schemes aim to reduce cluster maintenance cost and ‘greedy’ resources consumption through the provision of stable cluster architecture for upper-layer protocols. This is achieved through prevention of re-clustering requirements and/or minimisation of explicit control messages for clustering (Baker & Ephremides, 1981; Chatterjee et al., 2002; Gerla & Tsai, 1995). Mobility-aware clustering will group like mobile

A Survey of Clustering Schemes for Mobile Ad-Hoc Network (MANET)

142

nodes together according to their speed of movement – the chief reason for network topology changes. Similarly paced nodes are gathered into the same cluster allowing a tightening of intra-cluster links with corresponding stability realised in the presence of mobile nodes in motion (Basu et al., 2001; Inn & Winston, 2004). Energy-efficient clustering manages battery energy of mobile nodes more sensitively in a MANET. Fine calibration of energy requirements through elimination of redundant energy consumption by mobile nodes or balance among different mobile nodes can greatly impact on the projected network lifetime (Younis & Fahmy, 2004; Sheu & Wang, 2006). Load-balancing clustering schemes attempt an even distribution of mobile nodes to each cluster to create similarly sized clusters thus sharing the load on the network by this arrangement (Aim & Prakash, 2000; Li et al., 2004). Combined-metrics based clustering considers the multiple metrics in a cluster configuration with particular regard to clusterhead decisions, weighting the parameters according to their attributes pertinent to a particular application requirement, allowing an adaptive response as justified by the needs. With the consideration of more parameters that might include mobility speed, node degree, cluster size or battery energy, clusterheads can be better selected without bias given to mobile nodes with specific attributes (Chatterjee et al., 2002; Dhurandher & Singh, 2005; El-Bazzal et al., 2006).
Figure 1: Description of cost terms for clustering structure

Based on this classification, studying the common criteria shared by each category, and the similarities and differences between their schemes, the best application scenario for each clustering category can be determined.

143

Ismail Ghazi Shayeb, AbdelRahman Hamza Hussein and Ayman Bassam Nasoura

7. Clustering Algorithm in MANET
There have been numerous proposals and surveys of clustering algorithms (Jane & Peter, 2005; Chinara & Rath, 2009). Newly published approaches and others already reviewed will be given consideration (Chinara & Rath, 2009; Agarwal & Mahesh, 2009). The survey presented concentrates on five of the eight classifications outlined previously that relate directly to this paper 7.1. Low-Maintenance Clustering Clustered networks are chiefly criticised for the need of mobile nodes to have extra explicit message exchange between them in order to maintain cluster structure. When network topologies face recurrent changes, resulting in frequent cluster topology updates, the control overheads required for cluster maintenance face equivalent severe increases. The result of responsive clustering behavior may thereby consume a huge amount of network bandwidth, cause rapid energy drain (of mobile nodes) and (ironically and paradoxically) make ineffective any intended enhancement to network performance and scalability. Greater emphasis will be given to re-clustering due to its negative impact on issues regarding communication overhead, route invalidation and ripple effect. Re-affiliation, a lesser problem, refers to a non-clusterhead being reassigned after a link sever or compromise that seeks reestablishment within a different clusterhead that is within range without affecting the corresponding clusterhead(s). Accordingly, therefore, cluster-related control overhead can be reduced by limiting reaffiliation (usually requiring reaffiliation procedures) and re-clustering events. However, the proposed algorithm strives to actually eliminate this element completely by constructing, and maintaining, cluster architecture data traffic forwarding. The following protocols can be categorised under Low-Maintenance clustering approach: • The Lowest-Identifier (LID), or ‘identifier-based clustering’, was an original proposal of Baker and Ephremides (1981) and the Lowest-ID algorithm has proven one of the most favored clustering schemes cited in the old (Chatterjee et al., 2002) as well as recent (Chiang et al., 1998) ad hoc networks literature and has been a foundation for many undergraduate studies, still being given mention in such prestigious events as ICYCS 2008 [The 9th International Conference for Young Computer Scientists]. This popular heuristic allocates each node a unique ID number and designates the node with the lowest ID as clusterhead. Thus, the IDs of clusterhead’s neighbours will be higher than that of itself. However, the clusterhead is capable of delegating its responsibility to a node with the next minimum ID in its cluster. When a node lies directly between two or more clusterheads transmission lines it becomes a ‘gateway’ and is commonly used for routing between clusters. If a node lies between clusterheads and the clusters overlap the node may become part of a ‘distributed gateway’ if another node (from another cluster) within transmission range joins it as a pair to behave in this manner. (See Figure 1(b) in the first section.) Only gateway nodes (not regular cluster members) can listen to the different nodes of the overlapping clusters outside of which they lie. The concept of distributed gateway (DG) is also used for inter-cluster communication only when the clusters do not overlie. The chief benefit of distributed gateways is assuming the delegated role of responsibility whereby it can maintain connectivity in situations where any clustering algorithm might fail to provide connectivity. Although system performance is better with LID than Highest-Degree (see next algorithm) in terms of throughput that is sacrificed by this algorithm in terms of its inherent bias towards nodes with smaller IDs possibly leading to the battery drainage of certain nodes without any attempt at a uniform balance of load across all the nodes. • The Highest-Degree, or ‘connectivity-based clustering’, was an original proposal of Gerla and Parekh (1995) in which the degree of a node is calculated on the basis of its relative proximity to other nodes. Each node transmits its ID to others within its transmission range. A node x is considered to be a neighbour of another node y if x lies within the

A Survey of Clustering Schemes for Mobile Ad-Hoc Network (MANET)

144

transmission range of y. The node having the greatest number of neighbours (i.e., most/highest degree of direct transmission links) is chosen as clusterhead and any tie is broken with the unique node IDs. The neighbours of a clusterhead become absorbed as members of that cluster (or specific neighbourhood) and cannot participate any further in the election process now they have a declared ‘home’. The neighbourliness process thus prevents any direct link between clusterheads; only one clusterhead will reside in each cluster. As the clusterhead is linked directly to each of its neighbours in the cluster, any two nodes in a cluster are never more than two-hops apart. Experiments have shown the system demonstrates a low clusterhead rate of change however; there is a low throughput under the Highest-Degree heuristic. Each cluster is typically assigned resources that are shared in turn between those cluster members [nodes]. Any increase to the number of nodes in a cluster causes an eventual drop in throughput with a general effect of gradual degradation in the system performance. Node reaffiliation rates are high due to node movement (for new tasks, migrating to clusters with sufficient resources and responding to events) often resulting in the highest-degree node’s (the current clusterhead) failure at re-election because the loss of a neighbour can skew the dominance of a node’s previous connections in this arrangement. The subsequent re-elections that occur because of the lack of a ceiling limit on node occupancy of a cluster can drain the system. • LCC (Least Cluster Change) — LCC (Chiang, 1998) is believed to be an adaptation that marries the best features of Lowest ID Clustering (LID) with Highest Connectivity Clustering (HC). Prior to the proposal of LCC, most protocols sporadically executed the clustering procedure and to satisfy a particular clusterhead attribute, occasionally reclustered. In HC, the clustering procedure is periodically carried out to confirm a clusterhead’s “local highest node degree” attributes and on discovery of a higher degree member node, the current clusterhead under assessment must surrender its clusterhead role. As such, frequent re-clustering occurs when using this particular mechanism. LCC uses two steps to take best advantage of the clustering algorithm: cluster formation that is established through LID to choose clusterheads from mobile nodes with the lowest neighbourhood ID and cluster maintenance. Re-clustering in this case is reduced as it is event-driven and summoned in only two scenarios: • When two clusterheads come into proximity range one surrenders its clusterhead role. • When a mobile node is unable contact any clusterhead, the cluster structure for the network is rebuilt according to LID. LCC thus appreciably improves the stability of a cluster by abandoning the requirement for a clusterhead to always carry specified attributes in its local area. However, signified in the second reclustering scenario in LCC, a single node’s movement could still call upon a complete cluster structure re-computation involving an unavoidable expensive communication overhead for clustering. 7.2. Mobility-Aware Clustering Mobility is probably the most highly recognised attribute of MANETs, and is the major dynamic that affects topology change and route invalidation (Basu et al., 2001). Drawing upon the mobility behavior of mobile nodes to determine cluster architecture the idea is that by grouping similarly-paced mobile terminals into the same cluster, the intra-cluster links can become more tightly connected which will naturally decrease the reaffiliation and re-clustering rates. The protocols that follow may be categorised under ‘Mobility Aware’ clustering approach: • Mobility Based Metric for Clustering — MOBIC was the original proposal of Basu, Khan and Little (2001) suggesting that cluster formation, particularly the election of clusterheads which has been observed to be an exclusively local activity requiring only the involvement of the immediate neighbours and itself, needs to consider mobility as a pertinent issue. MOBIC proposes an aggregate local mobility metric for the cluster

145

Ismail Ghazi Shayeb, AbdelRahman Hamza Hussein and Ayman Bassam Nasoura formation process such that relatively low speed neighbouring mobile nodes have opportunity to become clusterheads. In MOBIC, a calculation of the variance of neighbouring mobile nodes’ relative speed will generate an estimated aggregate local speed. By calculating the variance of the relative mobility values of a mobile node with respect to each neighbour it is revealed that a low variance value indicates less mobility (and by implication, better stability) to neighbours so mobile nodes with low variance values in their neighbourhoods assume clusterhead responsibility. This outlook of MOBIC is a practicable and reasonable expectation of MANETs with common group mobility behavior, as in highway traffic where a selected clusterhead can normally promise a low mobility in relation to its member nodes. However, random movement and intermittent or frequent speed changes of mobile nodes can readily degrade the integrity of the MOBIC performance ability. MOBIC does have its disadvantages; it requires considerable cluster setup time and the high reaffiliation rate makes computation and communication overhead costly, as well as possibly increasing routing delay due to the increased number of clusterheads. Mobility-Based d-hop Clustering Algorithm (Inn & Winston, 2004) partitions an ad hoc network into d-hop clusters, intended to increase the flexibility of the cluster diameter, based on mobility metric. It assumes each node is capable of measuring its received signal strength, thereby estimating its distance from its neighbours - the stronger the received signal the closer the neighbouring node. This algorithm needs to factor five terms for its calculation: an estimation of the distance between nodes, the relative mobility between nodes, the variation of estimated distance over time, the local stability, and an estimation of mean distance. Relative mobility corresponds to the difference of the estimated distance of one node with respect to another, at two successive time moments. This parameter indicates if two nodes move away from each other or if they become closer. The variation of estimated distances between two nodes is computed instead of calculated by physical distance between two nodes because physical distance does not necessarily reveal ‘closeness’ in terms of functional ability. For example, a node low on energy will transmit packets at low power thus behaving as a distanced node from its physically close neighbour. The variation of estimated distance and the relative mobility between nodes are used to calculate the local stability, returning a low value for the most stable node in a neighbourhood which may indicate the most ideal candidate for selection as clusterhead.

•

7.3. Energy-Efficient Clustering Mobile nodes in a MANET dependent on battery power supply during operation pose challenges regarding energy limitation or conservation for optimal network performance. A MANET should make every effort to reduce any greedy energy consumption to prolong the lifespan of a network. Clusterheads are essential to several administrative tasks and inter cluster communication over and above the regular function of an ordinary node and are subject therefore, to earlier ‘death’ because of excessive energy consumption. Any resultant lack of mobile nodes (each essential in its role) due to energy depletion can make the network liable to partition and potential communication interruption. The protocols that following can be categorised under an ‘Energy-Efficient’ clustering approach: • Power-aware connected dominant set (Wu et al., 2001) is an energy-efficient clustering scheme that can decrease the size of a dominating set (DS) without any functional impairment. Unnecessary mobile nodes are identified and excluded from the dominating set and with the energy saving made from their exclusion, the higher energy-demanding clusterheads have more resources made available to them. Mobile nodes inside a DS bear extra tasks such as data packet relay and routing information updates and consume more battery energy than those outside a DS. The DS then is more power greedy than other sets

A Survey of Clustering Schemes for Mobile Ad-Hoc Network (MANET)

146

•

•

so it is vital to find a means of reduction to its energy consumption. In this scheme energy level is ascribed to a node to determine its suitability as a clusterhead rather than ID or node degree as described in other schemes. A mobile node can be removed from the DS when it has less residual energy than dominating neighbours in its close neighbour set. However, this scheme is unable to balance the rate of energy consumption between dominating nodes (clusterheads) and non-dominating nodes (ordinary nodes) because it endeavors only to minimise the DS rather than to actually balance the energy consumption of each and every mobile node. Thus, despite achieving some level of energy consumption reduction by decreasing the number of nodes in the DS, much faster rates of energy depletion probably occur overall. In (Younis & Fahmy, 2004), the authors offered an energy-efficient distributed clustering approach, called Hybrid Energy-Efficient Distributed clustering (HEED), for the ad hoc sensor networks. HEED operates in quasi-stationary networks and based on the residual energy of clusterheads a random selection is made of them to reduce the cost of communication. In HEED, each node executes a constant number of iterations with no assumption about node dispersion. An implementation of HEED in TinyOS (the operating system for Berkeley motes) successfully demonstrated that the HEED approach can prolong network lifetime and supports data aggregation. In Sheu’s Stable Cluster Algorithm (SCA) (Sheu & Wang, 2006) a battery power level threshold is established that defines nodes with battery level beneath the threshold as bottlenecks, counts the number of neighbours that are bottlenecks for each node, and elects nodes with the largest number of bottlenecks as clusterheads. This detour in the election of clusterheads prevents nodes with the least battery power assuming the role even as an election candidate thus, the clusters become more stable. Unfortunately, failing to address and include node mobility means the possibility of numerous re-clustering occurrences may still eventuate when elected clusterheads have high movement levels.

7.4. Load-Balancing Clustering Load-balancing clustering algorithms are based on the belief that a cluster is best served by an optimum number of active mobile nodes, especially in a clusterhead-based MANET. An over large cluster will demand too much of the clusterheads, causing them to become the bottleneck of a MANET with subsequent system throughput reductions. An inadequately small cluster, however, will requires many more of the smaller cluster units to achieve performance capability but the increased number of clusters will inevitably increase the length of hierarchical routes with resultant longer end-to-end delay. This research satisfies the demands of load balancing by establishing calculated upper (Max value) and lower (Min value) limits on the number of mobile nodes that a cluster can deal with for optimal performance regarding stability and energy requirements. The Max Value represents the upper limit to the amount of nodes a clusterhead can support simultaneously. Since mobile nodes have limited resources they are incapable of handling large numbers of nodes. This value is determined regarding the remainder of the clusterhead’s resources. Should a cluster size exceed its predefined limit, reclustering procedures are invoked to make appropriate adjustment to the number of mobile nodes contained therein. The Min Value represents the lower limit to the amount of nodes contained in a given cluster before it becomes necessary to proceed to extension or merging mechanisms when a drop below this calculated lower limit would impair efficiency. This is a global value that runs through the entire network. The Min Value can help avoid the complexities that result from having to manage great numbers of clusters that might otherwise occur without a load balancing strategy in place. The protocols that follow can be categorized under ‘Load-Balancing’ clustering approach: • DLBC (Degree-Load-Balancing Clustering) — DLBC (Aim & Prakash, 2000) periodically reviews the clustering scheme to maintain the number of mobile nodes in each cluster around a designated system parameter, ED, that indicates the ideal for a

147

Ismail Ghazi Shayeb, AbdelRahman Hamza Hussein and Ayman Bassam Nasoura clusterhead. Where the difference between ED and the number of mobile nodes that it currently serves exceeds some value, Max Delta, a clusterhead will be devalued and degrade to an ordinary member node. The endeavor of this mechanism is to make all clusterheads (where possible) serve the same and optimal number of member nodes. Adaptive Cluster Load Balance Method (Li et al., 2004) In HCC (Hierarchical Cluster Counting) (Gerla & Tsai, 1995) clustering scheme, a clusterhead may become exhausted through service to an excessive number of mobile hosts, an undesirable situation that results in the clusterhead becoming a bottleneck. Li, et. al (2004) suggested an alternative approach. In hello message format, there is an "Option" item. If a sender node is a clusterhead, it will assume an "Option" value by setting the number of its dominated member nodes and when it is not a clusterhead or it is undecided (CH or non-CH), "Option" item will be reset to 0, or no value. When a CH's Hello message reveals the dominated nodes' number is in excess of a threshold (the maximum number a single CH can manage), no further nodes will join this cluster. By limiting the number of nodes in a cluster (and the responsibility and work rate of the clusterhead) the bottleneck phenomenon can be eliminated and the cluster structure optimised. This algorithm can achieve load balance between various clusters, balancing resource consumption and information transmission through distribution to all rather than a few clusters.

•

7.5. Combined-Metrics-Based Clustering Combined-metrics-based clustering considers a number of metrics for cluster configuration. It aims to elect the most suitable (rather than desirable) clusterhead in a local area by ignoring any bias of specific node attributes, permitting it to flexibly adjust the weighting factors for each metric in adaptation to a variety of scenarios. For example, in systems that are particularly concerned with battery energy, the associated weighting factor can be set at higher level (Chatterjee et al., 2002). However, certain parameters may sometimes be unavailable or lack accuracy and understandably affect clustering performance. A novel weight algorithm that can be employed for selecting suitable clusterheads based on a number of metrics will be discussed in detail in future chapters. The protocols that follow can be categorised under ‘Combined-Metrics-Based’ clustering approach: • Weighted Clustering Algorithm (WCA) (Chatterjee et al., 2002) selects a clusterhead (Wv) based on a collection of certain attributes – loosely, the ideal number of nodes it can support (∆v), mobility (Mv), transmission power (Dv) and battery power (Pv). Avoiding communications overhead, the WCA is in-built but the clusterhead election procedure will only be invoked based on node mobility and when the current DS is incapable of covering all nodes. To prevent an overload to clusterheads a pre-defined threshold is used to indicate the ideal number of nodes a clusterhead can successfully accommodate. WCA selects the clusterheads according to the weight value of each node. The weight associated to a node v is defined as: Wv = W1 ∆v + W2 Dv +W3 Mv +W4 Pv The node with the minimum weight is selected as a clusterhead. The weighting factors are chosen so that w1 + w2 + w3 + w4 = 1. Mv is the measure of mobility, taken by computing the running average speed of every node during a specified time T. ∆v is the degree difference. ∆v is obtained by first calculating the number of neighbours of each node. The result of this calculation is defined as the degree of a node v, dv. To ensure load balancing the degree difference ∆v is calculated as |dv - δ | for every node v, where δ is a pre-defined threshold. The parameter Dv is defined as the sum of distances from a given node to all its neighbours. This factor is related to energy consumption since more power is needed for larger distance communications. The parameter Pv is the cumulative time of a node being a clusterhead. Pv is a measure of how much battery power has been consumed. With a clusterhead’s extra responsibilities it consumes more battery than an ordinary node. The clusterhead election

A Survey of Clustering Schemes for Mobile Ad-Hoc Network (MANET)

148

algorithm finishes once all the nodes are designated appropriate roles as either member nodes or clusterheads which is further decided by their proximity to one another where the distance between members must be less or equal to their transmission range and no two clusterheads can be immediate neighbours. Yet again, there are disadvantages even with this weighted algorithm particularly the network’s global minima weight values and the time expenditure for the computation of battery power. The effort required to distribute the algorithm is impractical as there is an inordinate amount of information that must be stored and exchanged among the nodes to find the smallest weight that becomes greater and more problematical as network size increases. So much information has to be computed for each node to reach a weight calculation for cluster setup that the freezing time of mobility of nodes is also high. Computation costs are increased with each reelection as the combined weight of every node needs to be calculated. • Entropy-Based Weighted Clustering Algorithm (Wang & Bao, 2007) Entropy based clustering overcomes the drawback of WCA’s high reaffiliation rates that contribute to higher communication overhead (Chatterjee et al., 2002) and forms a more stable network. It uses an entropy based model (originally founded in thermodynamics Second law) whereby measurement of “…the level of disorder in a closed but changing system in which energy can only be transferred from an ordered state to a disordered state shows that the higher the entropy, the higher the disorder and the lower the availability of the system’s energy to do useful work.” (Definition: BusinessDictionary.com, 2010) evaluates route stability in ad hoc networks and the election of a clusterhead. By evaluating this dynamic a better indication of the stability and mobility of the ad hoc network can be achieved. • Weight Based Clustering Algorithm (WBCA) proposed by Yang and Zhang (2007) modifies the WCA algorithm by considering the mean connectivity degree and battery power in calculation of the weight of nodes. The mean connectivity degree of a node is calculated as
Cv

∑N N + N = N +1 v i =1

vi

v

v

where N vi is the degree of connectivity of i-th neighbour of node v, and connectivity of node v. The consumed energy of a node is calculated as q N

v

is the degree of

E v = ∑ N vi ∗ e i =1

where q is the time of period during which a node v acts as cluster head at i-th times. Finally the combined weight is calculated as

W where v

= W 1 ∗ Dv + W 2 ∗ E v

is the degree difference and is defined as N v − C v for every node v. The values of W1 and W2 are the weighing factors that depend on the system requirements and W1 + W2 = 1. WBCA, unlike LID and HC algorithms, uniformly distributes the time for which the nodes act as cluster head reducing the cluster setup computation cost through calculation of only two values Dv and E v to determine the combined weight. However, in calculation of the mean connectivity degree of a single node the degree of connectivity of all its neighbour nodes is also required information. This is an atypical situation in a dynamic network as node mobility regularly changes its degree of connectivity. Like WCA, this algorithm requires substantial node freezing time prior to the actual cluster setup. Its main disadvantage is the arrangement of the global minima in a distributed fashion necessarily creates increased amounts of message exchanges between the nodes, channel bandwidth consumption becomes greater and computation cost is higher as calculation of mean connectivity degree of a node requires the degree of connectivity of neighbour nodes delaying cluster setup.

149

Ismail Ghazi Shayeb, AbdelRahman Hamza Hussein and Ayman Bassam Nasoura

8. Conclusion
Clustering can provide a large scale MANET with hierarchical network structures to overcome the difficulties of critical scalability and message flooding that impair the function of flat structure of MANETs. It brings attention to significant elements regarding routing operations, network management, mobility management, quality of service support etc. This chapter, provided fundamental concepts and definitions about clustering, design objectives of clustering algorithms, the necessity to cluster in a large dynamic MANET and the contra-indications and network cost of clustering. Associated clustering algorithms were classified into categories based on their distinguishing features subsequently discussed in terms of objective, mechanism, performance, and application scenarios. So far, it has been demonstrated that a cluster-based MANET has numerous important issues to examine including the stability of cluster structure, the control overhead of cluster construction and maintenance, the energy consumption of mobile nodes with different cluster-related status, the traffic load distribution in clusters, and the fairness of serving as clusterheads for a mobile node. Additionally, differing varieties of clustering schemes may have alternative focus and objectives. Regardless of the scheme or its specific objectives, clustering cost remains a major consideration in the performance evaluation and scalability improvement.

9. Future Work
This paper has briefly presented a wide range of concepts and systems relating to the research problem in this paper. All of these topics will somehow influence, or have a bearing, to a lesser or greater extent, the research outcome, affecting the design and development of a new efficient clustering algorithm that will address and seek to overcome the different clustering problems faced by MANETs.

References
[1] [2] Agarwal, R., & Mahesh, M. (2009). Survey of Clustering Algorithms for MANET. International Journal on Computer Science and Engineering, Vol.1 (2), 2009, (pp. 98-104). Al-Karaki, J., Kamal, A., & Ul-Mustafa, R. (2004). On the Optimal Clustering In Mobile Adhoc Network., First IEEE Consumer Communications and Networking Conference (CCNC), (pp. 71-76.). Amis, A., Prakash, R., Vuong, T., & Huynh, D. (2000). Max-Min D-Cluster Formation in Wireless Ad Hoc Networks. INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE , (pp. 32-41). Angione, G., Bellavista, P., Corradi, A., & Magistretti, E. (2007). A k-hop Clustering Protocol for Dense Mobile Ad-Hoc Networks. 26th IEEE International Conference on Distributed Computing Systems Workshops (ICDCSW'06). Lisboa, Portugal, (pp.10). Baker, D., & Ephremides, A. (1981). The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm. IEEE Transactions on Communications COM, (pp. 1694–1701). Basu, P., Khan, N. & Little, T. (2001). A Mobility Based Metric for Clustering In Mobile AdHoc Networks, In Proceedings of Distributed Computing Systems Workshop, IEEE ICDCSW’, (pp. 413-418). Cai, Z., Lu, M., & Wang, X. (2003). Channel Access-Based Self-Organized Clustering in Ad Hoc Networks. IEEE Trans. Mobile Comput, Vol. 2, No 2, (pp. 102-113). Chatterjee, M., Das, S., & Turgut, D. (2002). WCA: A Weighted Clustering Algorithm (WCA) for mobile ad hoc networks. Cluster Computing (pp. 193-204). Kluwer Academic. Chen, Y. & Liestman, A. (2003) A Zonal Algorithm For Clustering Ad-Hoc Networks. International Journal of Foundations of Computer Science ; Vol. 14(2), (pp. 305–322).

[3]

[4]

[5]

[6]

[7] [8] [9]

A Survey of Clustering Schemes for Mobile Ad-Hoc Network (MANET) [10]

150

[11]

[12] [13] [14]

[15]

[16] [17]

[18]

[19] [20]

[21] [22] [23]

[24] [25]

[26]

[27] [28]

Chiang, C., Gerla, M., & Zhang, L. (1998). Forwarding Group Multicast Protocol (FGMP) for Multihop, Mobile Wireless Networks. Cluster computing ACM/Baltzer J., Special Issue on Mobile Computing, Vol.1, No.2., (pp. 1187-96). Chinara, S., & Rath, K. (2009). TACA: A Topology Adaptive Clustering Algorithm For Mobile Ad Hoc Network. The 2009 World Congress in Computer Science Computer Engineering and Applied Computing. Las Vegas, USA. Chinara, S., & Rath, S. (2009). A Survey on One-Hop Clustering Algorithms in Mobile Ad Hoc Networks. Journal of Network and Systems Management , 17, (pp. 183 – 207) . Chlamtac, I., Conti, M., & Liu, J. (2003). Mobile Ad Hoc Networking: Imperatives and Challenges. Elsevier Ad Hoc Networks Journal , Vol. 1, (pp. 13-64). Cokuslu, D., & Erciyes, K. (2007). A Hierarchical Connected Dominating Set Based Clustering Algorithm for Mobile Ad Hoc Networks. 15th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems. Istanbul, Turkey, (pp. 60-66). Dai, F., & Wu, J. (2005). On Constructing K-Connected K-Dominating Set in Wireless Networks. Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05). Denver, Colorado, (pp. 81a). Dhurandher, S., & Singh, V. (2005). Weight Based Adaptive Clustering In Wireless Ad Hoc Networks. Personal Wireless Communications, 2005. ICPWC 2005, (pp. 95 - 100). El-Bazzal, Z., Kadoch, M., Agba, B., Gagnon, F., & Bennani, M. (2006). A Flexible Weight Based Clustering Algorithm in Mobile Ad hoc Networks. International Conference on Systems and Networks Communication (ICSNC'06), (pp. 50-56) . El-Bazzal, Z., Kadoch, M., Agba, L., Gagnon, F., & Bennani, M. (2006). An Efficient Management Algorithm for Clustering In Mobile Ad Hoc Network. International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems. Terromolinos, Spain: ACM, (pp. 25-31). Garcia, F., Solano, J., & Stojmenovic, I. (2003). Connectivity Based K-Hop Clustering in Wireless Networks. Telecommunication Systems 22, (pp. 205–220). Gayathri, V., Sabu, E., & Srikanthan, T. (2007). Size Restricted Cluster Formation and Cluster Maintenance Technique for Mobile Ad Hoc Networks. International Journal of Network Management , Vol. 17, (pp. 171–194). Gerla, M., & Tsai, J. (1995). Multi-cluster Mobile Multimedia Radio Network. ACM/Baltzer Wireless Networks Journal 95, (pp. 255-265). Hou, T., & Tsai, T. (2001). An Access-Based Clustering Protocol For Multihop Wireless Ad Hoc Networks. IEEE J. Select. Areas Comm, Vol.19 No.7, (pp. 1201-1210). Inn, E., & Winston, S. (2004). Mobility-Based D-Hop Clustering Algorithm for Mobile Ad Hoc Networks. IEEE Wireless Communications and Networking Conference, Vol. 4. Atlanta, GA, USA, Georgia, (pp. 2359-2364). Jane, Y., & Peter, J. (2005). A Survey of Clustering Schemes for Mobile Ad Hoc Networks. IEEE Communications Surveys and Tutorials, Vol. 7, ( pp. 32-40). Kwon, T., Gerla, M., Varma, K., & Barton, M. (2003). Efficient Flooding with Passive Clustering an Overhead-Free Selective Forward Mechanism for Ad Hoc/Sensor Networks. Proceedings of the IEEE, vol. 91, (pp. 1210 – 1220). Liu, J., Sailhan, F., Sacchetti, D., & Issarny, V. (2005). Group Management for Mobile Ad Hoc Networks: Design, Implementation and Experiment. Proceedings of the 6th international conference on Mobile Data Management, Ayia Napa, Cyprus, (pp. 192-199). Mai, K., Shin, D., & Choo, H. (2009). Toward Stable Clustering In Mobile Ad Hoc Networks. Information Networking, 2009. ICOIN 2009. International Conference on, (pp. 308-310). Ohta, T., Inoue, S., & Kakuda, Y. (2003). An Adaptive Multi-Hop Clustering Scheme For Highly Mobile Ad Hoc Networks. Proceedings of Sixth International Symposium on Autonomous Decentralized Systems(ISADS’03). Italy, (pp. 293).

151 [29] [30]

Ismail Ghazi Shayeb, AbdelRahman Hamza Hussein and Ayman Bassam Nasoura Perkins, C. (2008). Ad Hoc Networking, Addison-Wesley Professional. Purtoosi, R., Taheri, H., Mohammadi, A., & Foroozan, F. (2004). A Light-Weight ContentionBased Clustering Algorithm for Wireless Ad Hoc Networks. Computer and Information Technology (CIT ’04), (pp. 627-632). Sheu, P., & Wang, C. (2006). A Stable Clustering Algorithm Based on Battery Power for Mobile Ad Hoc Networks. Tamkang Journal of Science and Engineering , (pp. 233-242). Sucec, J., & Marsic, I. (2004). Hierarchical Routing Overhead in Mobile Ad Hoc Networks. IEEE Transactions on Mobile Computing , Volume: 3 Issue: 1, (pp. 46 – 56). Tolba, F., Magoni, D., & Lorenz, P. (2007). A Stable Clustering Algorithm for Highly Mobile Ad Hoc Networks. Second International Conference on Systems and Networks Communications (ICSNC 2007). Cap Esterel, France, (pp. 11-16). Tolba, F., Magoni, D., & Lorenz, P. (2007). Connectivity, energy & mobility driven Weighted clustering algorithm. in proceedings of IEEE GLOBECOM 2007, (pp. 2786 – 2790). Wang, L., & Olariu, S. (2005). Cluster Maintenance in Mobile Ad-hoc Networks. Cluster Computing, (pp. 111 - 118). Wang, X., & Bao, F. (2007). An Entropy-Based Weighted Clustering Algorithm and Its Optimization for Ad Hoc Networks. Third IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob 2007), (pp. 56-70). Wu, J., & Li, H. (1999). On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks. Proc.3rd Int’l. Wksp. Discrete Algorithms and Methods for Mobile Comp. and Commun., (pp. 7–14.). Wu, J., Gao, M., & Stojmenovic, I. (2001). On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks. Proceedings of the 2001 International Conference on Parallel Processing, (pp. 346 - 356). Yang, W., & Zhang, Z. (2007). A Weight- Based Clustering Algorithm for Mobile Ad Hoc Network. Proceedings of 3rd International Conference on Wireless and Mobile Communications (ICWMC‘07), (pp. 3-8). Younis, O., & Fahmy, S. (2004). HEED: A Hybrid Energy-Efficient Distributed Clustering Approach for Ad Hoc Sensor Networks. IEEE Transactions on Mobile Computing, Volume: 3 Issue: 4 . USA, (pp 366-371). Yu, J. & Chong, P. (2005). A Survey of Clustering Schemes for Mobile Ad Hoc Networks. IEEE Commun. Survey Tutor. 7(1), (pp. 32–47). Yuanzhu, P. C., Liestman, A. L., & Liu, J. (2004). Clustering Algorithms for Ad Hoc Wireless Networks. In Ad Hoc and Sensor Networks. Ad Hoc and Sensor Networks. Nova Science Publishers, (pp. 1-16).

[31] [32] [33]

[34] [35] [36]

[37]

[38]

[39]

[40]

[41] [42]