Distributed Minimum-Cost Clustering Protocol
for UnderWater Sensor Networks (UWSNs)
Pu Wang and Cheng Li
Electrical and Computer Engineering
Faculty of Engineering and Applied Science
Memorial University of Newfoundland
St. John’s, Newfoundland,
A1B 3X5, Canada
Email: {pwang, licheng}@engr.mun.ca
Jun Zheng
School of Information Technology and Engineering
University of Ottawa
800 King Edward Street
Ottawa, Ontario K1N 6N5, Canada
Email: junzheng@site.uottawa.ca
Abstract—In this paper, we study the node clustering problem
in UnderWater Sensor Networks (UWSNs). We formulate the
problem into a cluster-centric cost-based optimization problem
with an objective to improve the energy efficiency and prolong
the lifetime of the network. For this purpose, a cost metric is
defined for a potential cluster, which takes into account three
important parameters that are relevant to the energy status of
the cluster, including (1) the total energy consumption of the
cluster members for sending data to the cluster head; (2) the
residual energy of the cluster head and its cluster members;
and (3) the relative location between the cluster head and the
underwater sink (uw-sink)
. To solve the formulated problem, a
novel distributed clustering protocol called minimum-cost
clustering protocol (MCCP) is proposed, which selects a set of
non-overlapping clusters from all potential clusters based on
the cost metric assigned to each potential cluster and attempts
to minimize the overall cost of the selected clusters. MCCP can
adapt geographical cluster head distribution to the traffic
pattern in the network and thus avoid the formation of hot
spots around the uw-sink. It can also balance the traffic load
between cluster heads and cluster members through periodical
re-clustering the sensor nodes in the network. Simulation
results show that MCCP significantly improves the energy
efficiency and the lifetime of a UWSN as compared with the
well-known HEED protocol.
I. I
NTRODUCTION
UnderWater Sensor Network (UWSN) is an emerging
networking paradigm that promises a wide range of potential
applications in both civilian and military areas [1-2].
Compared with traditional underwater monitoring or
surveillance technologies, a UWSN has a number of
advantages, such as unmanned underwater exploration,
localized and precise information acquisition, large-scale
underwater monitoring, reduced implementation cost, and
more frequent operation [2]. However, the lifetime of a
UWSN is largely restricted by the energy constraint in
sensor nodes and the harsh conditions of underwater
acoustic transmission channels.
Node clustering is an effective technique for improving
the energy efficiency and prolonging the network lifetime of
a WSN [3] and has been widely studied in terrestrial WSNs.
Due to the unique characteristics of UWSNs, however, the
clustering algorithms proposed for terrestrial WSNs cannot
be applied to UWSNs directly without modification. In this
paper, we study the node clustering probl
1
em in UWSNs.
We formulate the problem into a cluster-centric cost-based
This work is supported in part by the Natural Sciences and Engineering
Research Council (NSERC) of Canada
optimization problem with an objective to improve the
energy efficiency and prolong the lifetime of the network. In
the formulated problem, every node in the network is a
cluster head candidate, which can potentially form a cluster
together with some combination of its neighbors. The
generation of a set of clusters is based on a cost metric
(called cluster cost) defined for a potential cluster, which
takes into account three important parameters that are
relevant to the energy status of the cluster, including
(1) the
total energy consumption of the cluster members for sending
data to the cluster head; (2) the residual energy of the cluster
head and its cluster members; and (3) the relative location
between the cluster head and the uw-sink. To solve the
formulated problem, we first propose a centralized
minimum-cost clustering algorithm (MCCA) and then
present a minimum-cost clustering protocol (MCCP) that
implements MCCA in a distributed manner. Unlike most
existing clustering algorithms, MCCA and MCCP select
clusters, rather than cluster heads, based on the cost metric
assigned to each potential cluster and attempts to minimize
the overall cost of the selected clusters. Simulation results
show that the proposed MCCP significantly improves the
energy efficiency and prolong the network lifetime of a
UWSN. To the best of our knowledge, this is the first time
that the node clustering problem is considered as a
cluster-centric cost-based optimization problem.
The rest of this paper is organized as follow. In Section II,
we describe the network architecture, formulate the
clustering problem, define the cost metric, and review
related work. In section III, we present the proposed MCCA
and MCCP. In section IV, we show simulation results to
evaluate the performance of MCCP. In Section V, we
conclude this paper with a brief discussion of future work.
II. P
ROBLEM STATEMENT AND RELATED WORK
2.1. Network Architecture
A UWSN typically consists of several uw-sinks located at
the centers of different monitored areas, a number of ocean
bottom sensor nodes surrounding each uw-sink, and a
surface station providing a link to an on-shore control center,
as shown in Figure 1. A uw-sink has a sufficient power
supply and is capable of handling multiple parallel
communications with the sensor nodes. All sensor nodes are
homogenous and quasi-stationary. Each of them can adjust
its transmission range with transmission power control.
Unlike terrestrial sensor network, a UWSN has some unique
characteristics, such as highly limited bandwidth, long
1-4244-0353-7/07/$25.00 ©2007 IEEE
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2007 proceedings.