  Clustering is a promising approach for building hierarchies and simplifying
the routing process in mobile ad-hoc network environments. The main objective
of clustering is to identify suitable node representatives, i.e. cluster heads
(CHs), to store routing and topology information and maximize clusters
stability. Traditional clustering algorithms suggest CH election exclusively
based on node IDs or location information and involve frequent broadcasting of
control packets, even when network topology remains unchanged. More recent
works take into account additional metrics (such as energy and mobility) and
optimize initial clustering. However, in many situations (e.g. in relatively
static topologies) re-clustering procedure is hardly ever invoked; hence
initially elected CHs soon reach battery exhaustion. Herein, we introduce an
efficient distributed clustering algorithm that uses both mobility and energy
metrics to provide stable cluster formations. CHs are initially elected based
on the time and cost-efficient lowest-ID method. During clustering maintenance
phase though, node IDs are re-assigned according to nodes mobility and energy
status, ensuring that nodes with low-mobility and sufficient energy supply are
assigned low IDs and, hence, are elected as CHs. Our algorithm also reduces
control traffic volume since broadcast period is adjusted according to nodes
mobility pattern: we employ infrequent broadcasting for relative static network
topologies, and increase broadcast frequency for highly mobile network
configurations. Simulation results verify that energy consumption is uniformly
distributed among network nodes and that signaling overhead is significantly
decreased.
