By exploit clustering techniques, several
applications and protocols are proved to have increased scalability, reduced
delays and prolonged lifetime. Examples include [13], [10] and [14], etc. Most
clustering schemes in the literature fall into the following three categories:
1. identifier-based clustering
2. topology-based clustering
3. energy-based clustering
In the following, we will explore the common features of each category of
clustering scheme, and provide some insightful observations on their performance
aspects.
2.1 Identifier-based Heuristic
Baker and Ephremides [15] devised one of the earliest clustering algorithms for
ad hoc networks, the Linked Cluster Algorithm, which originated the identifierbased
heuristic. This heuristic assigns a unique logic ID to each node and
chooses the node with the minimum/maximum id as a clusterhead. Thus, the
IDs of the neighbors of the clusterhead will be higher/lower than that of the
clusterhead. The Max-Min D-Cluster [2] scheme belongs to this category, in
which clusters are formed by di?®using node identities along wireless links.
A logic ID-based clustering heuristic provides a simple means to form
clusters. However, this clustering scheme is biased towards certain nodes on
their identifiers, which results in non-uniform load distribution and leads to
the battery drainage of certain nodes [11]. One might think that this problem
could be fixed by renumbering the node IDs from time to time, which is
however non-trivial [12].
Pages:
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560