International Journal of Distributed Sensor Networks
of safe nodes is represented as a set
𝑠
and the set of
malicious nodes is represented as a set
𝑚
,where=
𝑠
∪
𝑚
.
Each node only knows about its direct neighboring nodes
and communicates with them when necessary without any
advanced knowledge about whether they are safe nodes or
malicious nodes. All sensor nodes are assumed to be static,
or they have low mobility with respect to signal propagation
speed. Every sensor node has the same transmission range
and is able to communicate with other sensor nodes within its
range. We also assume that each node is assigned with a triplet
of coordinate (,,), where each coordinate represents
the hop distance of the node from one anchor. All sensor
nodeshavethesamecommunicationrangeof,whichis
represented as a sphere volume of radius in a UWSN.
Denition 1. e function (,V) denes the distance
between two nodes
𝑢
and
V
in a D Euclidean space as
:×→Γ:
(
,V
)
,
(
,V
)
=
𝑥
−V
𝑥
2
+
𝑦
−V
𝑦
2
+
𝑧
−V
𝑧
2
.
()
Two nodes
𝑢
and
V
are neighbors and connected by a
link if (,V)<and the link between
𝑢
and
V
is denoted by
(,V).enodedegreeof
𝑢
is the number of links incident
to
𝑢
, which is denoted by
𝑢
.Weconstructthenetwork
topology with RNG (Relative Neighborhood Graph) [], and
then two nodes become neighbor nodes if and only if for
any arbitrary node
𝑝
, (,V)≤max{(,),(,V)}.For
a three-dimensional Euler space embedded, if the arcuate
area formed by the intersection of two spheres centered at
𝑢
and
V
(with radius (,V ))isempty,then
𝑢
and
V
are adjacent nodes. RNG algorithm is simple and is easily
built in a distributed way. ere is no crossing edges in
aRNGbecauseatleastoneedgeinanypairofcrossing
edges must be removed according to their denitions and
the time complexity is (
3
). While constructing from a
Delaunay Triangulation Graph structure, its complexity of
lower bound is (log())[]. In addition, a computational
method with the complexity of (
2
) for the RNG in a
three-dimensional space is given in []. As underwater
sensors oat with currents, their movements are constrained
in dierent horizontal planes and they are likely to maintain
a steady position relative to each other. e construction
of RNG does not require that the exact positions of nodes
and their neighbors are known. For each node, only the
corresponding mutual distances to its neighbors are required.
erefore, RNG is expected to be more suitable in modeling
UWSN, which achieves more accurate results and behaves
more consistently than other models. In fact, we model a
UWSN with a RNG, not form a RNG overlay on top of a
random geometric graph. e deployment of a UWSN is
deemed to be sparser than that of a terrestrial sensor network
duetothecostinvolvedandtothechallengesassociatedtothe
deployment itself in the underwater environment. erefore,
modeling a UWSN with a random geometric graph is not
suitable for selection in view of the connectivity especially
when sensor nodes are not evenly distributed.
Beacon
000
011
110
001
101
111
100
010
F:etopologyofaUWSNwithsensornodes.
CLUSS is a CLUster-based Secure Synchronization pro-
tocol. Given a UWSN, the whole network is composed of
three types of nodes: beacons, cluster heads, and ordinary
nodes. Beacons have unlimited energy resources and perfect
timing information. For example, they can synchronize to
UTC (Universal Time Coordinated) time constantly using
GPS services without recalibrating their atomic clocks or
performing any synchronization algorithms. In this regard,
they provide the time reference for the sensors positioned
underwater. If there are two or more beacons, they can
communicate with each other through radio frequency (RF)
links. Beacons communicate with cluster heads and ordinary
nodes through acoustic links. Each cluster has and only has
one cluster head. All ordinary nodes connect to their cluster
head via single hop. e cluster heads of dierent clusters
connect to a beacon through multiple hops. Figure shows
the topology of a UWSN with sensor nodes and one beacon.
e beacon is placed on the water surface and is equipped
withGPStoobtainUTCtime.Eachsensornodeisassigneda
unique identier (ID). e sensor nodes make autonomous
decision about cluster formation without any centralized
control.
Denition 2. Suppose that the cluster for node
𝑢
is denoted
as
𝑢
;thenforeachnode,
V
∈
𝑢
;if
V
=
𝑢
,thencluster
consistency is satised; else if there exists a node
𝑤
∈
𝑢
such
that
𝑤
=
𝑢
,thenitiscalledcluster inconsistency.
Denition gives the meanings of cluster consistency and
cluster inconsistency. According to Denition , each sensor
node belongs to one and only one cluster. Dierent clusters
cannot share any common sensor nodes. It is important for
sensor nodes to perform cluster consistency checking during
the process of cluster formation.
e process of cluster formation for a UWSN is described
as in the following step-by-step instructions.
Step 1. All sensor nodes with -hop distance to a beacon are
set to cluster heads.
Step 2. Each cluster head will try to add its neighboring nodes
as ordinary nodes that belong to its cluster in order of their