06-02-2013, 02:51 PM
A Survey of Clustering Schemes for Mobile Ad-Hoc Network (MANET)
1A Survey of Clustering.pdf (Size: 328.51 KB / Downloads: 78)
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.
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.
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.
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.
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.
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.