which is computed leveraging the history of successful data
transmissions between neighbouring sensor nodes.
Generally, E-CARP works in two stages: network ini-
tialization and hope count setting and data forwarding.
When the network is initialized, a HELLO control packet:
HELLO ¼ id
src
; HC
hi
ð1Þ
is flooded from SN throughout the whole network region,
where (1) id
src
is the unique identifier of a source node, and
(2) HC is the hop count, which represents the distance in
terms of the hops when transmitting packets, to SN. HC( SN )
is 0. Intuitively, the bigger the HC is, the farther the distance
is between a certain sensor node and SN. When the network
has been initialized, the topology has been established and
each sensor node is aware of its distance in hop count to SN.
During the packet forwarding phase, a packet (denoted
pkt) is routed from a source sensor node uv
x
2 UV to SN in
a hop-by-hop fashion, where each hop is determined
independently. Specifically, when pkt is to be routed, uv
x
will choose a neighbouring sensor node uv
y
2 UV, which is
nearer to SN and acts as the rel ay node, to forward pkt.An
EPING control packet is broadcasted:
EPING ¼ id
uv
x
; id
uv
y
; gðuv
y
Þ; HCðuv
x
Þ; pid; L
pkt
ð2Þ
where id
uv
x
and id
uv
y
represent the identifiers of uv
x
and uv
y
,
respectively. pid is the unique identifier of this EPING
packet. L
pkt
¼fhpkt
id
src
; pkt
id
ig represents a set of packet
identifiers to be forwarded. pkt
id
src
specifies the sensor node
which has gener ated this sensory data packet pkt, and pkt
id
is the unique identifier of pkt. uv
y
ignores this EPING
packet when ðHCðuv
y
ÞHCðuv
x
ÞÞ [ 0. This suggests that
uv
y
is farther to SN than uv
x
. Otherwise, uv
y
replies a
PONG control packet to uv
x
:
PONG ¼ id
uv
y
; id
uv
x
; pid; HCðuv
y
Þ;
queue; energy; lqðuv
y
; uv
x
Þ;
bit
mask
L
pkt
; bit mask
JR
ð3Þ
where id
uv
y
; id
uv
x
, and pid are the same as those in the
EPING packet. queue specifies the available buffer space at
uv
y
, and energy refers to the residen t energy at uv
y
.
lqðuv
y
; uv
x
Þ corresponds to the quality of the link, which is
computed leveraging the quality of the links (1) from uv
y
to
uv
x
, and (2) from uv
y
to uv
z
, where uv
z
is the relay node
when uv
y
forwards packets to SN. bit mask
L
pkt
and
bit
mask
JR
are used for handling link asymmetries and
interference. lqðuv
y
; uv
x
Þ is defined as follows:
lq
t
new
ðuv
y
; uv
x
Þ¼lq
t
y;x
ðuv
y
; uv
x
Þþ
1
distðuv
y
; uv
x
Þ
ð4Þ
where lq
t
y;x
ðuv
y
; uv
x
Þ is the value of link quality computed
by Formula 1 in the article [19]. Note that the impact of the
distance between sensor nodes (denoted distðuv
y
; uv
x
Þ)is
considered when computing the link quality. Generally, the
shorter the distance is, the better the link quality between
sensor nodes is. This is reflected by
1
distðuv
y
;uv
x
Þ
in Formula 4.
Same as what we have argued in [15], sensory data may
not vary significantly when the environment to be monitored
is relatively steady. Besides, certain applications may work
well when the variation of certain sensory data is within a
certain threshold. In this case, an INFORM control packet,
rather than the sensory data packet, should be routed to SN:
INFORM ¼ id
uv
x
; id
uv
y
; HCðuv
x
Þ; pid; L
pkt
ð5Þ
where id
uv
x
; id
uv
y
; HCðuv
x
Þ; pid, and L
pkt
are the same as
those in the EPING control packet.
3 Routing tree construction and maintenance
This sectio n presents the construction of the routing tree
during the network initialization phase, and introduces the
mechanism for the maintenance of the routing tree when
the network topology changes due to the water dynamic s.
3.1 Routing tree construction
As aforementioned, during the network initialization phase,
HELLO control packets are flooded from the sink node SN to
sensor nodes in the whole network region. HC(uv) (where
uv 2 UV) represents the distance in hop count of a sensor node
uv to the sink node. Leveraging the HC(uv) of sensor nodes, a
routing tree Tr
rt
is constructed where SN is the root of this tree.
The tree construction procedure is represented as follows:
As pres ented in Algorithm 1, the routing tree is con-
structed along with the HELLO control packet flooded from
SN. When a sensor node uv
chd
receives a HELLO control
Pers Ubiquit Comput (2015) 19:1075–1086 1077
123