# RLT Code Based Handshake-Free Reliable MAC Protocol for Underwater Sensor Networks

Authors: Xiujuan Du; Keqin Li; Xiuxiu Liu; Yishan Su
Journal: Journal of Sensors
 (2016)

---

## Abstract

The characteristics of underwater acoustic channels such as long propagation delay and low bit rate cause the medium access control (MAC) protocols designed for radio channels to either be inapplicable or have low efficiency for underwater sensor networks (UWSNs). Meanwhile, due to high bit error, conventional end-to-end reliable transfer solutions bring about too many retransmissions and are inefficient in UWSN. In this paper, we present a recursive LT (RLT) code. With small degree distribution and recursive encoding, RLT achieves reliable transmission hop-by-hop while reducing the complexity of encoding and decoding in UWSN. We further propose an RLT code based handshake-free (RCHF) reliable MAC protocol. In RCHF protocol, each node maintains a neighbor table including the field of state, and packages are forwarded according to the state of a receiver, which can avoid collisions of sending-receiving and overhearing. The transmission-avoidance time in RCHF decreases data-ACK collision dramatically. Without RTS/CTS handshaking, the RCHF protocol improves channel utilization while achieving reliable transmission. Simulation results show that, compared with the existing reliable data transport approaches for underwater networks, RCHF can improve network throughput while decreasing end-to-end overhead.


---

## Body

## 1. Introduction

Recently, research on underwater sensor networks (UWSNs) has attracted significant attention [1–6] due to its potential application in environmental monitoring, resource investigation, disaster prevention, and so on. UWSN adopts acoustic communication, and acoustic channel is characterized by high bit error with the order of magnitude of 10−3–10−7, long propagation delay of a few seconds, and narrow bandwidth of kbps, resulting in terrestrial-based communication protocols being either inapplicable or inefficient for UWSN. Compared with conventional modems, acoustic modems in UWSN are more energy-consuming. However, nodes are battery-powered and harder to recharge and replace in harsh underwater environments. Furthermore, underwater nodes are usually deployed more sparsely; most nodes can move passively with water currents or other underwater activities, and some nodes will fail as energy depletion or hardware fault, so the network topology of UWSN usually changes dynamically, which brings about significant challenges to protocol design for UWSN.The characteristics of acoustic communication discussed above make terrestrial protocols inapplicable in UWSN, regardless of MAC mechanism or reliable data transmission. MAC protocols have great impact on network system and are especially important for low quality channel. MAC protocols are usually divided roughly into two categories: contention based protocols and contention-free protocols. Contention based protocols are further divided into two subcategories: random access and collision-avoidance. In random access mechanism, a sender transmits packets without any coordination, which could lead to collision. In collision-avoidance protocols, RTS/CTS handshake is used widely to manage contention at both sides of sender and receiver, which can solve the hidden terminal problem and avoid collision between data packets to some extent. So collision-avoidance protocols outperform random access approaches in networks with heavy traffic. However, considering the characteristics of long propagation delay and low bandwidth of underwater acoustic channel, RTS/CTS handshake decreases the utilization of channel and is inefficient in UWSN.Contention-free protocols are divided into three categories: TDMA, FDMA, and CDMA, in which channels are separated by time, frequency, or code domain, respectively. FDMA is unsuitable for UWSN because of the narrow available frequency range in underwater acoustic channels. TDMA requires time synchronization which is very challenging due to the variable delay in UWSN, and TDMA shows limited bandwidth efficiency because of the long time guards required in acoustic channel. CDMA separates signals by spreading codes and supports concurrent transmissions, which is resilient to multipath and Doppler’s effects prevalent in underwater environments. Nevertheless, CDMA system requires additional hardware.The characteristics of acoustic communication make conventional reliable transport mechanism inapplicable as well for UWSN, which is analyzed as follows.(1)
High bit error rate of acoustic channel leads to high erasure probability of packet and low success probability of transferring hop-by-hop. So, traditional end-to-end reliable transport mechanism may incur in too many retransmissions and collisions and reduce channel utilization.
(2)
Low propagation speed of acoustic signals leads to long end-to-end delay, which brings about some issues for two end-nodes to control transmission timely.
(3)
ARQ (Automatic Repeat Request) mechanism requires ACKs (acknowledgements) for the packets received successfully and retransmits the lost packets. It is well known that the channel utilization of simple stop-and-wait ARQ protocol is very low in UWSN with long propagation delay and low bit rate. In addition, acoustic modems adopt half-duplex communication, which limits the choice of efficient pipelined ARQ protocols. Even worse, if ACKs are lost, the packets received successfully will be retransmitted by the sender, and more bandwidth and energy will be consumed.
(4)
Some reliable data transport protocols resort to FEC (Forward-Error-Correcting) to overcome the problems caused by ACKs. FEC adopts erasure codes and the amount of redundancy is fixed prior to transmission. Before transmitting, the sender encodes a set ofn original packets into a set of N
N
≥
n encoded packets. Let m
=
N
-
n, so m redundant packets are generated. In order to reconstruct n original packets, the receiver has to receive a certain number (larger than n) of encoded packets. The stretch factor is defined as N
/
n, which is a constant that depends on erasure probability. However, the error probability of channel in UWSN is dynamic, and overestimated error probability will incur in additional overhead, whereas low-estimated error probability will lead to transmission failure.The main contributions of this paper are summarized as follows.(1)
Underwater acoustic channels are characterized by high bit error and temporal and spatial variation. Based on digital fountain code, we propose a recursive LT (RLT) code with small degree distribution and introduce the erasure probability of channelp
p into RLT code for the first time, which improve the probability of decoding at the receiving node. RLT is applicable to dynamic UWSN with limit transmission time between two nodes. RLT reduces the overhead of encoding and decoding and improves the efficiency of decoding process substantially.
(2)
Based on RLT, we provide a reliable and handshake-free MAC protocol which is called RCHF MAC protocol. In RCHF protocol, a sender transmits packets according to the state of the receiver, which can avoid collisions caused by transmitting to a node in sending state as well as transmitting to the same node by different senders at the same time. A minimum time intervalT
a is set between two successive transmission phases of a node, and T
a is also called transmission-avoidance time, which could decrease collision between data packets and ACK packets. So, without RTS/CTS handshake, RCHF improves channel utilization and realizes reliable transmission hop-by-hop.
(3)
To the best of our knowledge, SDRT [7] proposed by Xie et al. and CCRDT [8] proposed by Mo et al. are two reliable data transport protocols for UWSN up to date. We conduct a large number of simulation experiments to evaluate the performance of RCHF protocol and compare it with SDRT and CCRDT in aspects of throughput, overhead, end-to-end delay, delivery ratio, and energy-consumption. Simulation results show that RCHF has noticeable performance improvement.The remainder of the paper is organized as follows. Section2 briefly discusses related work. In Section 3, we describe RLT (recursive LT) code. Section 4 presents state based and handshake-free MAC protocol which achieves reliable data transmission hop-by-hop. Section 5 evaluates the performance of RCHF protocol through simulations. Finally, Section 6 concludes the paper and discusses some future work.


## 2. Related Work

### 2.1. Reliable Transmission Mechanism

Reliable data transmission over network has been the subject of much research. TCP ensures reliable delivery essentially through retransmitting the packets which have not been acknowledged by receivers, having poor performance in underwater acoustic channel impaired heavily. So, reliable transmission solutions based on coding were proposed [9, 10].Reed and Solomon proposed Reed-Solomon code based on some practical erasure codes [11]. Reed-Solomon code is efficient for small values of n and m. However, the algorithms of encoding and decoding require field operations and result in too high computation overhead. Due to the limited computation capability of nodes, Reed-Solomon code is unsuitable for UWSN. Luby et al. studied a practical Tornado code [12]. Tornado code only involves XOR operations, and the algorithms of encoding and decoding are faster than Reed-Solomon code. However, Tornado code uses multilayer bipartite graph to encode and decode packets, resulting in high computation and communication overhead. Xie et al. presented SDRT reliable transport protocol. SDRT adopts SVT code to improve encoding/decoding efficiency. Nevertheless, after pumping the packets within the window quickly into the channel, the sender sends the packets outside the window at a very slow rate until receiving a positive feedback from the receiver, which reduces channel utilization. Mo et al. investigated a multihop coordinated protocol for UWSN based on GF(256) random-linear code to guarantee reliability and efficiency [8]. However, the encoding vectors are generated randomly, so the success probability of recovering K data packets from K encoded packets could not be guaranteed, and its decoding complexity is higher than other sparse codes. Furthermore, the multihop coordination mechanism requires time synchronization and is restricted in a string topology where there is a single sender and a single receiver.Digital fountain codes are sparse codes on bipartite graphs with high performance [13, 14], which are rateless; that is, the amount of redundancy is not fixed prior to transmission and can be decided on the fly as the error recovery algorithm evolves. These codes are known to be asymptotically near-optimal for every erasure channel and allow for lightweight implementation of encoder and decoder. Luby put forward LT code, in which the decoder is capable of recovering the original symbols with high probability from any set of output symbols whose size is close to the origins [15]. However, LT code is designed for large number of data packets, which is not the case in UWSN, especially for mobile networks where transmission time between two nodes is very limited because of node mobility. Furthermore, the degree distribution used in LT code results in the large degree of nodes in the graph, which brings about large overhead for each packet.


### 2.2. MAC Protocol for UWSN

There are still many open issues in building underwater acoustic networks, and most of research work focused on the design of MAC protocols [16]. For example, Zhou et al. dealt with the design and performance evaluation of random access scheme in UWSN [17] and focused on tradeoffs arisen in clustered topology and proposed a protocol which is partly deterministic and partly random in [18]. Du et al. presented CDMA based MAC protocols for UWSN [19]. CDMA system requires additional hardware, and the narrow available frequency range in underwater acoustic channels has a negative impact on the application of CDMA based MAC protocols.Most of the collision-avoidance MAC protocols in UWSN so far adopted RTS/CTS frames to coordinate transmission and ACK frames to acknowledge the data frames received successfully. However, RTS/CTS-based protocols are helpless in exposed terminal problem, and the channel utilization of handshake-based protocols is very low, especially in UWSN with long propagation delay and low bit rate. In addition, multiple handshakes considerably prolong end-to-end delay. So, RTS/CTS-based protocols are inefficient in impaired UWSN channel.In this paper, a recursive LT (RLT) code with small degree distribution is proposed, which reduces the complexity of encoding and decoding. Integrated with RLT code, a reliable RCHF MAC protocol is presented. With high energy efficiency and channel utilization, RCHF MAC protocol achieves reliable transmission hop-by-hop for UWSN.


## 2.1. Reliable Transmission Mechanism

Reliable data transmission over network has been the subject of much research. TCP ensures reliable delivery essentially through retransmitting the packets which have not been acknowledged by receivers, having poor performance in underwater acoustic channel impaired heavily. So, reliable transmission solutions based on coding were proposed [9, 10].Reed and Solomon proposed Reed-Solomon code based on some practical erasure codes [11]. Reed-Solomon code is efficient for small values of n and m. However, the algorithms of encoding and decoding require field operations and result in too high computation overhead. Due to the limited computation capability of nodes, Reed-Solomon code is unsuitable for UWSN. Luby et al. studied a practical Tornado code [12]. Tornado code only involves XOR operations, and the algorithms of encoding and decoding are faster than Reed-Solomon code. However, Tornado code uses multilayer bipartite graph to encode and decode packets, resulting in high computation and communication overhead. Xie et al. presented SDRT reliable transport protocol. SDRT adopts SVT code to improve encoding/decoding efficiency. Nevertheless, after pumping the packets within the window quickly into the channel, the sender sends the packets outside the window at a very slow rate until receiving a positive feedback from the receiver, which reduces channel utilization. Mo et al. investigated a multihop coordinated protocol for UWSN based on GF(256) random-linear code to guarantee reliability and efficiency [8]. However, the encoding vectors are generated randomly, so the success probability of recovering K data packets from K encoded packets could not be guaranteed, and its decoding complexity is higher than other sparse codes. Furthermore, the multihop coordination mechanism requires time synchronization and is restricted in a string topology where there is a single sender and a single receiver.Digital fountain codes are sparse codes on bipartite graphs with high performance [13, 14], which are rateless; that is, the amount of redundancy is not fixed prior to transmission and can be decided on the fly as the error recovery algorithm evolves. These codes are known to be asymptotically near-optimal for every erasure channel and allow for lightweight implementation of encoder and decoder. Luby put forward LT code, in which the decoder is capable of recovering the original symbols with high probability from any set of output symbols whose size is close to the origins [15]. However, LT code is designed for large number of data packets, which is not the case in UWSN, especially for mobile networks where transmission time between two nodes is very limited because of node mobility. Furthermore, the degree distribution used in LT code results in the large degree of nodes in the graph, which brings about large overhead for each packet.


## 2.2. MAC Protocol for UWSN

There are still many open issues in building underwater acoustic networks, and most of research work focused on the design of MAC protocols [16]. For example, Zhou et al. dealt with the design and performance evaluation of random access scheme in UWSN [17] and focused on tradeoffs arisen in clustered topology and proposed a protocol which is partly deterministic and partly random in [18]. Du et al. presented CDMA based MAC protocols for UWSN [19]. CDMA system requires additional hardware, and the narrow available frequency range in underwater acoustic channels has a negative impact on the application of CDMA based MAC protocols.Most of the collision-avoidance MAC protocols in UWSN so far adopted RTS/CTS frames to coordinate transmission and ACK frames to acknowledge the data frames received successfully. However, RTS/CTS-based protocols are helpless in exposed terminal problem, and the channel utilization of handshake-based protocols is very low, especially in UWSN with long propagation delay and low bit rate. In addition, multiple handshakes considerably prolong end-to-end delay. So, RTS/CTS-based protocols are inefficient in impaired UWSN channel.In this paper, a recursive LT (RLT) code with small degree distribution is proposed, which reduces the complexity of encoding and decoding. Integrated with RLT code, a reliable RCHF MAC protocol is presented. With high energy efficiency and channel utilization, RCHF MAC protocol achieves reliable transmission hop-by-hop for UWSN.


## 3. The RLT Code

RLT code is a variant of the LT code. Prior to RLT, the encoding and decoding of LT code are explained in this section.


### 3.1. The LT Code

#### 3.1.1. Encoding

Consider a set ofk input (original) packets, with each having the same length of l bits [20, 21]. The LT encoder takes k input packets and generates a potentially infinite sequence of encoded packets. Each encoded packet is computed independent of others. More precisely, given k input packets x
1
,
x
2
,
…
,
x
k and a suitable probability distribution Ω
d, where d is the degree of encoded packets, the number of input packets used to generate the encoded packets, d
∈
1
,
2
,
…
,
k, a sequence of encoded packets y
1
,
y
2
,
…
,
y
j
,
…
,
y
n, n
≥
k, are generated as follows.(1)
Select randomly a degreed according to the distribution Ω
d.
(2)
Selectd input packets uniformly at random and set y
j equal to the bitwise sum modulo 2 of the d input packets. This can be implemented by successively XORing the d packets. y
j is an encoded packet with an index field used to indicate the IDs of the XORed input packets.The relationship between the input and the encoded packets can be described by the graph in Figure1 in which n encoded packets are generated from k input packets, where n
=
8, k
=
6, and the degree of y
1 is equal to three.Figure 1
Encoding graph of LT code.


#### 3.1.2. Decoding

The LT decoder tries to recover the original input packets from received encoded packets. The decoding process is as follows.(1)
Find an encoded packety
j which is connected to only one input packet x
i and go to step (2). If the receiving node fails to find such encoded packet, stop decoding.
(2)
Setx
i
=
y
j.
(3)
Sety
m
=
y
m
⊕
x
i for each encoded packet which is connected to x
i, denoted by y
m. Here, ⊕ indicates XOR operation.
(4)
Remove all edges connected tox
i.
(5)
Go to step (1).


#### 3.1.3. Soliton Distribution

For LT codes, the ideal degree distributionΩ
d is the soliton distribution given by the following equation:(1)
Ω
d
=
1
k
,
d
=
1
;
1
d
d
-
1
,
d
=
2,3
,
…
,
k
,where ∑
d
Ω
d
=
1.LT code is designed for the blocks including large number of data packets. However, it is not the case in mobile UWSN, where transmission time between two nodes is very limited due to node mobility. The degree distribution used in LT code incurs in large degree of nodes in the graph and brings about much overhead for encoding and decoding. The ideal soliton distribution of LT code shows perfect behavior in terms of the expected number of encoded packets needed to recover input packets. Unfortunately, like most ideal things, this distribution is quite fragile, in fact so much, so that it is useless in practice.


### 3.2. Recursive LT (RLT) Code

Coding scheme has great impact on system performance. In this section, we present recursive LT (RLT) code, achieving quickly encoding and decoding. For RLT code, we have assumptions that packet losses are independent. We use a bipartite graphG
=
(
V
,
E
) with two levels to represent RLT code, where E is the set of edges and V is the set of nodes in the graph; V
=
D
∪
C, where D is the set of input packets and C is the set of encoded packets. The edges connect the nodes in D and C.


#### 3.2.1. Encoding

Givenk input packets x
1
,
x
2
,
…
,
x
k
∈
D and degree distribution Ω
d, Let n
=
(
k
+
ξ
)
/
(
1
-
p
p
), where n is the expected number of encoded packets received successfully, p
p is erasure probability of underwater acoustic channel, that is, the packet error rate (PER), and ξ
(
ξ
>
0
) corresponds to the expected number of redundant encoded packets received. ξ redundant packets are used to decrease the probability that the receivers cannot restore the original k input packets through one transmission phase. The sequence of encoded packets is y
1
,
y
2
,
…
,
y
j
,
…
,
y
n
∈
C. The encoding procedure of RLT is as follows.(1)
FromD, set input packets, successively XOR, the k packets to generate one encoded packet with degree k, and then duplicate the packet to get 1
/
(
1
-
p
p
) copies.
(2)
From setD, select m
/
(
1
-
p
p
) distinct packets randomly to constitute a seed set S
1 and generate m
/
(
1
-
p
p
) encoded packets with degree one. Here, m is the expected number of encoded packets received successfully with degree one. In reality, we can set 1
≤
m
≤
m
a
x
k
/
4
,
1.
(3)
LetS
2
=
D
-
S
1. From the set S
2, select uniformly k
/
2
(
1
-
p
p
) input packets at random, do XOR operation, respectively, with one packet in the set S
1selected randomly to generate k
/
2
(
1
-
p
p
) encoded packets with degree two.
(4)
LetS
3
=
D
-
S
1
-
S
2. If S
3 is not null, select k
/
6
(
1
-
p
p
) input packets at random from the set S
3; otherwise, from the set D, do XOR operation, respectively, with one packet from S
2 and another from S
1 to generate k
/
6
(
1
-
p
p
) encoded packets with degree three.
(5)
LetS
4
=
D
-
S
1
-
S
2
-
S
3. If S
4 is not null, select randomly ξ
+
k
/
3
-
m
-
1
/
(
1
-
p
p
) input packets from the set S
4; otherwise, from the set D, do XOR operation, respectively, with three packets from S
1
,
S
2
,
S
3, respectively, to generate ξ
+
k
/
3
-
m
-
1
/
(
1
-
p
p
) encoded packets with degree four.


#### 3.2.2. Decoding

When an encoded packet is transmitted over an erasure channel, it is either received correctly or lost. The RLT decoder tries to recover the original input packets from the encoded packets received. The decoding process of RLT is as follows.(1)
Find an encoded packety
j which is connected to only one input packet x
i. If the receiving node fails to find such encoded packet, stop decoding.
(2)
Setx
i
=
y
j.
(3)
Sety
m
=
y
m
⊕
x
i for each encoded packet which is connected to x
i, denoted by y
m. Here, ⊕ indicates XOR operation.
(4)
Remove all edges connected tox
i.
(5)
Go to step (1).


#### 3.2.3. Degree Distribution

The limited delivering time between two nodes caused by node mobility leads to the fact that digital fountain codes are constrained to work with smallk in UWSN communication. In order to reconstruct the input packets, the degree distribution of encoded packets received should have the following properties for RLT.(1)
The encoded packets received should involve all the input packets.
(2)
The process of encoding and decoding should not involve too many XOR operations.
(3)
At least one encoded packet with degree one should be received correctly by the receiver.Given the high bit error, denoted byp
b, with the order of magnitude of 10−3–10−7, the PER p
p is given by the following equation:(2)
p
p
=
1
-
1
-
p
b
l
,where l is the packet size. Reference [22] gave the optimal packet size based on MICRO ANP protocol architecture, which is greater than one hundred bytes. So, given the optimal packet size, p
p is nontrivial. Considering k input packets, in order to address the aforementioned properties of degree distribution, the degree distribution of encoded packets in sending nodes is given by the following equation:(3)
Ω
d
=
m
ξ
+
k
,
d
=
1
;
k
d
d
-
1
ξ
+
k
,
d
=
2,3
;
ξ
+
1
/
3
k
-
m
+
1
ξ
+
k
,
d
=
4
;
1
ξ
+
k
,
d
=
k
,where ∑
d
Ω
(
d
)
=
1.Lemma 1.
The average degree of encoded packetsλ
≈
3.7
.Proof.
From the degree distribution given by (3), we get(4)
λ
=
E
d
=
∑
d
=
1
4
d
×
Ω
d
=
1
×
m
ξ
+
k
+
2
×
k
2
×
1
×
ξ
+
k
+
3
×
k
3
×
2
×
ξ
+
k
+
4
×
ξ
+
1
/
3
k
-
m
+
1
ξ
+
k
+
k
ξ
+
k
=
3
2
3
+
ξ
/
3
-
3
m
-
4
ξ
+
k
.Usually, ξ
/
3
-
3
m
-
4
≪
ξ
+
k, so λ
≈
3
2
/
3
≈
3.7.From Lemma1, we can get that the decoding complexity of RLT is about 3.7 which is independent of the number of input packets. The comparison of encoding/decoding complexity is shown in Table 1.Table 1
Decoding complexity comparison.
Codes
Encoding/decoding complexity
GF(256) in [8]
O
(
k
3
)
LT
k
l
n
e
k
SDRT in [7]
k
⋅
ln
⁡
(
1
/
ε
)
RS
k
(
N
-
k
)
l
o
g
2
N
RLT
3.7


### 3.3. Statistics Analysis of RLT Code

Now, we define functionψ
k
(
n
) as the probability of decoding successfully when n encoded packets have been collected by the receiver. Note that ψ
k
n
=
0 for n
<
k. For completely random digital fountain code, ψ
k
n can be computed exactly as the probability of full rank of a k
×
n
(
n
≥
k
) random binary matrix (i.e., a matrix with elements in G
F
2), which can be expressed as in the following equation:(5)
ψ
k
n
=
∏
i
=
0
k
-
1
1
-
2
i
-
n
.Considering the erase probabilityp
p of channels, let B
N
;
n
,
1
-
p
p denote the probability of n packets received successfully, where N is the number of encoded packets transmitted by a sender, N, n
∈
Z, n
≤
N, 0
≤
p
p
≤
1, 0
≤
B
N
;
n
,
1
-
p
p
≤
1. B
N
;
n
,
1
-
p
p is the probability mass function (PMF) of binominal distribution and is given by the following equation:(6)
B
N
;
n
,
p
=
n
N
p
n
1
-
p
N
-
n
.So, according to random LT code, whenN packets are transmitted at a sender, the decoding probability φ
N
,
k
(
p
p
) at the receiver is given by the following equation:(7)
φ
N
,
k
p
p
=
∑
n
=
k
N
B
N
;
n
,
1
-
p
p
∏
i
=
0
k
1
-
2
i
-
n
.However, according to the RLT with recursive encoding/decoding, the schematic of binary matrix of encoded packets received is as follows:(8)
D
e
g
r
e
e
:
k
1
2
3
4
P
a
c
k
e
t
n
u
m
b
e
r
:
1
m
k
/
2
k
/
6
ξ
-
m
-
1
+
k
/
3
x
1
x
2
x
3
x
4
x
5
,
⋮
,
x
k
1
0
0
⋯
0
︷
1
0
1
⋯
0
1
1
0
⋯
0
1
0
0
⋯
1
1
0
0
⋯
0
,
,
,
⋯
,
⋮
⋮
⋮
⋯
⋮
,
,
,
⋯
,
1
0
0
⋯
0
0
0
⋯
0
︷
0
1
⋯
0
1
0
⋯
0
0
0
⋯
1
0
0
⋯
0
,
,
⋯
,
⋮
⋮
⋯
⋮
,
,
⋯
,
0
0
⋯
0
1
0
⋯
0
︷
0
0
⋯
1
0
1
⋯
1
0
0
⋯
0
1
1
⋯
0
,
,
⋯
,
⋮
⋮
⋯
⋮
,
,
⋯
,
0
0
⋯
0
1
0
⋯
1
︷
1
1
⋯
0
0
1
⋯
1
1
0
⋯
1
0
1
⋯
0
,
,
⋯
,
⋮
⋮
⋯
⋮
,
,
⋯
,
0
0
⋯
0
1
0
⋯
1
︷
1
1
⋯
1
0
1
⋯
1
1
1
⋯
1
1
1
⋯
0
,
,
⋯
,
⋮
⋮
⋯
⋮
,
,
⋯
,
0
0
⋯
0
y
1
y
2
y
3
⋯
,
,
,
⋯
y
j
,
,
⋯
,
,
,
y
ξ
+
k
,In the binary matrix, the expected number of encoded packets received with degreek is “1”; the number with degree “1” is m; the number with degree “2” is k
/
2, and those packets are encoded fully recursively. In the encoding of RLT, S
3 and S
4 may overlap with the set of D, which results in the fact that the decoding probability at the receiver is less than “1”. After k
+
ξ encoded packets have been collected, the probability ψ
k
n of decoding successfully is as follows:(9)
ψ
k
n
=
ψ
k
k
+
ξ
>
∏
i
=
0
ξ
-
m
-
1
+
k
/
2
1
-
2
i
-
k
-
ξ
.We define functionφ
k
,
ξ
(
p
p
) as the probability of recovering k input packets at the receiver after ξ
+
k
/
1
-
p
p packets are transmitted at a sender. This probability can be given by the following equation:(10)
φ
k
,
ξ
p
p
=
∑
ξ
=
0
ξ
B
ξ
+
k
1
-
p
p
;
k
+
ξ
,
1
-
p
p
ψ
k
k
+
ξ
>
∏
i
=
0
ξ
-
m
-
1
+
k
/
2
1
-
2
i
-
k
-
ξ
.


## 3.1. The LT Code

### 3.1.1. Encoding

Consider a set ofk input (original) packets, with each having the same length of l bits [20, 21]. The LT encoder takes k input packets and generates a potentially infinite sequence of encoded packets. Each encoded packet is computed independent of others. More precisely, given k input packets x
1
,
x
2
,
…
,
x
k and a suitable probability distribution Ω
d, where d is the degree of encoded packets, the number of input packets used to generate the encoded packets, d
∈
1
,
2
,
…
,
k, a sequence of encoded packets y
1
,
y
2
,
…
,
y
j
,
…
,
y
n, n
≥
k, are generated as follows.(1)
Select randomly a degreed according to the distribution Ω
d.
(2)
Selectd input packets uniformly at random and set y
j equal to the bitwise sum modulo 2 of the d input packets. This can be implemented by successively XORing the d packets. y
j is an encoded packet with an index field used to indicate the IDs of the XORed input packets.The relationship between the input and the encoded packets can be described by the graph in Figure1 in which n encoded packets are generated from k input packets, where n
=
8, k
=
6, and the degree of y
1 is equal to three.Figure 1
Encoding graph of LT code.


### 3.1.2. Decoding

The LT decoder tries to recover the original input packets from received encoded packets. The decoding process is as follows.(1)
Find an encoded packety
j which is connected to only one input packet x
i and go to step (2). If the receiving node fails to find such encoded packet, stop decoding.
(2)
Setx
i
=
y
j.
(3)
Sety
m
=
y
m
⊕
x
i for each encoded packet which is connected to x
i, denoted by y
m. Here, ⊕ indicates XOR operation.
(4)
Remove all edges connected tox
i.
(5)
Go to step (1).


### 3.1.3. Soliton Distribution

For LT codes, the ideal degree distributionΩ
d is the soliton distribution given by the following equation:(1)
Ω
d
=
1
k
,
d
=
1
;
1
d
d
-
1
,
d
=
2,3
,
…
,
k
,where ∑
d
Ω
d
=
1.LT code is designed for the blocks including large number of data packets. However, it is not the case in mobile UWSN, where transmission time between two nodes is very limited due to node mobility. The degree distribution used in LT code incurs in large degree of nodes in the graph and brings about much overhead for encoding and decoding. The ideal soliton distribution of LT code shows perfect behavior in terms of the expected number of encoded packets needed to recover input packets. Unfortunately, like most ideal things, this distribution is quite fragile, in fact so much, so that it is useless in practice.


## 3.1.1. Encoding

Consider a set ofk input (original) packets, with each having the same length of l bits [20, 21]. The LT encoder takes k input packets and generates a potentially infinite sequence of encoded packets. Each encoded packet is computed independent of others. More precisely, given k input packets x
1
,
x
2
,
…
,
x
k and a suitable probability distribution Ω
d, where d is the degree of encoded packets, the number of input packets used to generate the encoded packets, d
∈
1
,
2
,
…
,
k, a sequence of encoded packets y
1
,
y
2
,
…
,
y
j
,
…
,
y
n, n
≥
k, are generated as follows.(1)
Select randomly a degreed according to the distribution Ω
d.
(2)
Selectd input packets uniformly at random and set y
j equal to the bitwise sum modulo 2 of the d input packets. This can be implemented by successively XORing the d packets. y
j is an encoded packet with an index field used to indicate the IDs of the XORed input packets.The relationship between the input and the encoded packets can be described by the graph in Figure1 in which n encoded packets are generated from k input packets, where n
=
8, k
=
6, and the degree of y
1 is equal to three.Figure 1
Encoding graph of LT code.


## 3.1.2. Decoding

The LT decoder tries to recover the original input packets from received encoded packets. The decoding process is as follows.(1)
Find an encoded packety
j which is connected to only one input packet x
i and go to step (2). If the receiving node fails to find such encoded packet, stop decoding.
(2)
Setx
i
=
y
j.
(3)
Sety
m
=
y
m
⊕
x
i for each encoded packet which is connected to x
i, denoted by y
m. Here, ⊕ indicates XOR operation.
(4)
Remove all edges connected tox
i.
(5)
Go to step (1).


## 3.1.3. Soliton Distribution

For LT codes, the ideal degree distributionΩ
d is the soliton distribution given by the following equation:(1)
Ω
d
=
1
k
,
d
=
1
;
1
d
d
-
1
,
d
=
2,3
,
…
,
k
,where ∑
d
Ω
d
=
1.LT code is designed for the blocks including large number of data packets. However, it is not the case in mobile UWSN, where transmission time between two nodes is very limited due to node mobility. The degree distribution used in LT code incurs in large degree of nodes in the graph and brings about much overhead for encoding and decoding. The ideal soliton distribution of LT code shows perfect behavior in terms of the expected number of encoded packets needed to recover input packets. Unfortunately, like most ideal things, this distribution is quite fragile, in fact so much, so that it is useless in practice.


## 3.2. Recursive LT (RLT) Code

Coding scheme has great impact on system performance. In this section, we present recursive LT (RLT) code, achieving quickly encoding and decoding. For RLT code, we have assumptions that packet losses are independent. We use a bipartite graphG
=
(
V
,
E
) with two levels to represent RLT code, where E is the set of edges and V is the set of nodes in the graph; V
=
D
∪
C, where D is the set of input packets and C is the set of encoded packets. The edges connect the nodes in D and C.


### 3.2.1. Encoding

Givenk input packets x
1
,
x
2
,
…
,
x
k
∈
D and degree distribution Ω
d, Let n
=
(
k
+
ξ
)
/
(
1
-
p
p
), where n is the expected number of encoded packets received successfully, p
p is erasure probability of underwater acoustic channel, that is, the packet error rate (PER), and ξ
(
ξ
>
0
) corresponds to the expected number of redundant encoded packets received. ξ redundant packets are used to decrease the probability that the receivers cannot restore the original k input packets through one transmission phase. The sequence of encoded packets is y
1
,
y
2
,
…
,
y
j
,
…
,
y
n
∈
C. The encoding procedure of RLT is as follows.(1)
FromD, set input packets, successively XOR, the k packets to generate one encoded packet with degree k, and then duplicate the packet to get 1
/
(
1
-
p
p
) copies.
(2)
From setD, select m
/
(
1
-
p
p
) distinct packets randomly to constitute a seed set S
1 and generate m
/
(
1
-
p
p
) encoded packets with degree one. Here, m is the expected number of encoded packets received successfully with degree one. In reality, we can set 1
≤
m
≤
m
a
x
k
/
4
,
1.
(3)
LetS
2
=
D
-
S
1. From the set S
2, select uniformly k
/
2
(
1
-
p
p
) input packets at random, do XOR operation, respectively, with one packet in the set S
1selected randomly to generate k
/
2
(
1
-
p
p
) encoded packets with degree two.
(4)
LetS
3
=
D
-
S
1
-
S
2. If S
3 is not null, select k
/
6
(
1
-
p
p
) input packets at random from the set S
3; otherwise, from the set D, do XOR operation, respectively, with one packet from S
2 and another from S
1 to generate k
/
6
(
1
-
p
p
) encoded packets with degree three.
(5)
LetS
4
=
D
-
S
1
-
S
2
-
S
3. If S
4 is not null, select randomly ξ
+
k
/
3
-
m
-
1
/
(
1
-
p
p
) input packets from the set S
4; otherwise, from the set D, do XOR operation, respectively, with three packets from S
1
,
S
2
,
S
3, respectively, to generate ξ
+
k
/
3
-
m
-
1
/
(
1
-
p
p
) encoded packets with degree four.


### 3.2.2. Decoding

When an encoded packet is transmitted over an erasure channel, it is either received correctly or lost. The RLT decoder tries to recover the original input packets from the encoded packets received. The decoding process of RLT is as follows.(1)
Find an encoded packety
j which is connected to only one input packet x
i. If the receiving node fails to find such encoded packet, stop decoding.
(2)
Setx
i
=
y
j.
(3)
Sety
m
=
y
m
⊕
x
i for each encoded packet which is connected to x
i, denoted by y
m. Here, ⊕ indicates XOR operation.
(4)
Remove all edges connected tox
i.
(5)
Go to step (1).


### 3.2.3. Degree Distribution

The limited delivering time between two nodes caused by node mobility leads to the fact that digital fountain codes are constrained to work with smallk in UWSN communication. In order to reconstruct the input packets, the degree distribution of encoded packets received should have the following properties for RLT.(1)
The encoded packets received should involve all the input packets.
(2)
The process of encoding and decoding should not involve too many XOR operations.
(3)
At least one encoded packet with degree one should be received correctly by the receiver.Given the high bit error, denoted byp
b, with the order of magnitude of 10−3–10−7, the PER p
p is given by the following equation:(2)
p
p
=
1
-
1
-
p
b
l
,where l is the packet size. Reference [22] gave the optimal packet size based on MICRO ANP protocol architecture, which is greater than one hundred bytes. So, given the optimal packet size, p
p is nontrivial. Considering k input packets, in order to address the aforementioned properties of degree distribution, the degree distribution of encoded packets in sending nodes is given by the following equation:(3)
Ω
d
=
m
ξ
+
k
,
d
=
1
;
k
d
d
-
1
ξ
+
k
,
d
=
2,3
;
ξ
+
1
/
3
k
-
m
+
1
ξ
+
k
,
d
=
4
;
1
ξ
+
k
,
d
=
k
,where ∑
d
Ω
(
d
)
=
1.Lemma 1.
The average degree of encoded packetsλ
≈
3.7
.Proof.
From the degree distribution given by (3), we get(4)
λ
=
E
d
=
∑
d
=
1
4
d
×
Ω
d
=
1
×
m
ξ
+
k
+
2
×
k
2
×
1
×
ξ
+
k
+
3
×
k
3
×
2
×
ξ
+
k
+
4
×
ξ
+
1
/
3
k
-
m
+
1
ξ
+
k
+
k
ξ
+
k
=
3
2
3
+
ξ
/
3
-
3
m
-
4
ξ
+
k
.Usually, ξ
/
3
-
3
m
-
4
≪
ξ
+
k, so λ
≈
3
2
/
3
≈
3.7.From Lemma1, we can get that the decoding complexity of RLT is about 3.7 which is independent of the number of input packets. The comparison of encoding/decoding complexity is shown in Table 1.Table 1
Decoding complexity comparison.
Codes
Encoding/decoding complexity
GF(256) in [8]
O
(
k
3
)
LT
k
l
n
e
k
SDRT in [7]
k
⋅
ln
⁡
(
1
/
ε
)
RS
k
(
N
-
k
)
l
o
g
2
N
RLT
3.7


## 3.2.1. Encoding

Givenk input packets x
1
,
x
2
,
…
,
x
k
∈
D and degree distribution Ω
d, Let n
=
(
k
+
ξ
)
/
(
1
-
p
p
), where n is the expected number of encoded packets received successfully, p
p is erasure probability of underwater acoustic channel, that is, the packet error rate (PER), and ξ
(
ξ
>
0
) corresponds to the expected number of redundant encoded packets received. ξ redundant packets are used to decrease the probability that the receivers cannot restore the original k input packets through one transmission phase. The sequence of encoded packets is y
1
,
y
2
,
…
,
y
j
,
…
,
y
n
∈
C. The encoding procedure of RLT is as follows.(1)
FromD, set input packets, successively XOR, the k packets to generate one encoded packet with degree k, and then duplicate the packet to get 1
/
(
1
-
p
p
) copies.
(2)
From setD, select m
/
(
1
-
p
p
) distinct packets randomly to constitute a seed set S
1 and generate m
/
(
1
-
p
p
) encoded packets with degree one. Here, m is the expected number of encoded packets received successfully with degree one. In reality, we can set 1
≤
m
≤
m
a
x
k
/
4
,
1.
(3)
LetS
2
=
D
-
S
1. From the set S
2, select uniformly k
/
2
(
1
-
p
p
) input packets at random, do XOR operation, respectively, with one packet in the set S
1selected randomly to generate k
/
2
(
1
-
p
p
) encoded packets with degree two.
(4)
LetS
3
=
D
-
S
1
-
S
2. If S
3 is not null, select k
/
6
(
1
-
p
p
) input packets at random from the set S
3; otherwise, from the set D, do XOR operation, respectively, with one packet from S
2 and another from S
1 to generate k
/
6
(
1
-
p
p
) encoded packets with degree three.
(5)
LetS
4
=
D
-
S
1
-
S
2
-
S
3. If S
4 is not null, select randomly ξ
+
k
/
3
-
m
-
1
/
(
1
-
p
p
) input packets from the set S
4; otherwise, from the set D, do XOR operation, respectively, with three packets from S
1
,
S
2
,
S
3, respectively, to generate ξ
+
k
/
3
-
m
-
1
/
(
1
-
p
p
) encoded packets with degree four.


## 3.2.2. Decoding

When an encoded packet is transmitted over an erasure channel, it is either received correctly or lost. The RLT decoder tries to recover the original input packets from the encoded packets received. The decoding process of RLT is as follows.(1)
Find an encoded packety
j which is connected to only one input packet x
i. If the receiving node fails to find such encoded packet, stop decoding.
(2)
Setx
i
=
y
j.
(3)
Sety
m
=
y
m
⊕
x
i for each encoded packet which is connected to x
i, denoted by y
m. Here, ⊕ indicates XOR operation.
(4)
Remove all edges connected tox
i.
(5)
Go to step (1).


## 3.2.3. Degree Distribution

The limited delivering time between two nodes caused by node mobility leads to the fact that digital fountain codes are constrained to work with smallk in UWSN communication. In order to reconstruct the input packets, the degree distribution of encoded packets received should have the following properties for RLT.(1)
The encoded packets received should involve all the input packets.
(2)
The process of encoding and decoding should not involve too many XOR operations.
(3)
At least one encoded packet with degree one should be received correctly by the receiver.Given the high bit error, denoted byp
b, with the order of magnitude of 10−3–10−7, the PER p
p is given by the following equation:(2)
p
p
=
1
-
1
-
p
b
l
,where l is the packet size. Reference [22] gave the optimal packet size based on MICRO ANP protocol architecture, which is greater than one hundred bytes. So, given the optimal packet size, p
p is nontrivial. Considering k input packets, in order to address the aforementioned properties of degree distribution, the degree distribution of encoded packets in sending nodes is given by the following equation:(3)
Ω
d
=
m
ξ
+
k
,
d
=
1
;
k
d
d
-
1
ξ
+
k
,
d
=
2,3
;
ξ
+
1
/
3
k
-
m
+
1
ξ
+
k
,
d
=
4
;
1
ξ
+
k
,
d
=
k
,where ∑
d
Ω
(
d
)
=
1.Lemma 1.
The average degree of encoded packetsλ
≈
3.7
.Proof.
From the degree distribution given by (3), we get(4)
λ
=
E
d
=
∑
d
=
1
4
d
×
Ω
d
=
1
×
m
ξ
+
k
+
2
×
k
2
×
1
×
ξ
+
k
+
3
×
k
3
×
2
×
ξ
+
k
+
4
×
ξ
+
1
/
3
k
-
m
+
1
ξ
+
k
+
k
ξ
+
k
=
3
2
3
+
ξ
/
3
-
3
m
-
4
ξ
+
k
.Usually, ξ
/
3
-
3
m
-
4
≪
ξ
+
k, so λ
≈
3
2
/
3
≈
3.7.From Lemma1, we can get that the decoding complexity of RLT is about 3.7 which is independent of the number of input packets. The comparison of encoding/decoding complexity is shown in Table 1.Table 1
Decoding complexity comparison.
Codes
Encoding/decoding complexity
GF(256) in [8]
O
(
k
3
)
LT
k
l
n
e
k
SDRT in [7]
k
⋅
ln
⁡
(
1
/
ε
)
RS
k
(
N
-
k
)
l
o
g
2
N
RLT
3.7


## 3.3. Statistics Analysis of RLT Code

Now, we define functionψ
k
(
n
) as the probability of decoding successfully when n encoded packets have been collected by the receiver. Note that ψ
k
n
=
0 for n
<
k. For completely random digital fountain code, ψ
k
n can be computed exactly as the probability of full rank of a k
×
n
(
n
≥
k
) random binary matrix (i.e., a matrix with elements in G
F
2), which can be expressed as in the following equation:(5)
ψ
k
n
=
∏
i
=
0
k
-
1
1
-
2
i
-
n
.Considering the erase probabilityp
p of channels, let B
N
;
n
,
1
-
p
p denote the probability of n packets received successfully, where N is the number of encoded packets transmitted by a sender, N, n
∈
Z, n
≤
N, 0
≤
p
p
≤
1, 0
≤
B
N
;
n
,
1
-
p
p
≤
1. B
N
;
n
,
1
-
p
p is the probability mass function (PMF) of binominal distribution and is given by the following equation:(6)
B
N
;
n
,
p
=
n
N
p
n
1
-
p
N
-
n
.So, according to random LT code, whenN packets are transmitted at a sender, the decoding probability φ
N
,
k
(
p
p
) at the receiver is given by the following equation:(7)
φ
N
,
k
p
p
=
∑
n
=
k
N
B
N
;
n
,
1
-
p
p
∏
i
=
0
k
1
-
2
i
-
n
.However, according to the RLT with recursive encoding/decoding, the schematic of binary matrix of encoded packets received is as follows:(8)
D
e
g
r
e
e
:
k
1
2
3
4
P
a
c
k
e
t
n
u
m
b
e
r
:
1
m
k
/
2
k
/
6
ξ
-
m
-
1
+
k
/
3
x
1
x
2
x
3
x
4
x
5
,
⋮
,
x
k
1
0
0
⋯
0
︷
1
0
1
⋯
0
1
1
0
⋯
0
1
0
0
⋯
1
1
0
0
⋯
0
,
,
,
⋯
,
⋮
⋮
⋮
⋯
⋮
,
,
,
⋯
,
1
0
0
⋯
0
0
0
⋯
0
︷
0
1
⋯
0
1
0
⋯
0
0
0
⋯
1
0
0
⋯
0
,
,
⋯
,
⋮
⋮
⋯
⋮
,
,
⋯
,
0
0
⋯
0
1
0
⋯
0
︷
0
0
⋯
1
0
1
⋯
1
0
0
⋯
0
1
1
⋯
0
,
,
⋯
,
⋮
⋮
⋯
⋮
,
,
⋯
,
0
0
⋯
0
1
0
⋯
1
︷
1
1
⋯
0
0
1
⋯
1
1
0
⋯
1
0
1
⋯
0
,
,
⋯
,
⋮
⋮
⋯
⋮
,
,
⋯
,
0
0
⋯
0
1
0
⋯
1
︷
1
1
⋯
1
0
1
⋯
1
1
1
⋯
1
1
1
⋯
0
,
,
⋯
,
⋮
⋮
⋯
⋮
,
,
⋯
,
0
0
⋯
0
y
1
y
2
y
3
⋯
,
,
,
⋯
y
j
,
,
⋯
,
,
,
y
ξ
+
k
,In the binary matrix, the expected number of encoded packets received with degreek is “1”; the number with degree “1” is m; the number with degree “2” is k
/
2, and those packets are encoded fully recursively. In the encoding of RLT, S
3 and S
4 may overlap with the set of D, which results in the fact that the decoding probability at the receiver is less than “1”. After k
+
ξ encoded packets have been collected, the probability ψ
k
n of decoding successfully is as follows:(9)
ψ
k
n
=
ψ
k
k
+
ξ
>
∏
i
=
0
ξ
-
m
-
1
+
k
/
2
1
-
2
i
-
k
-
ξ
.We define functionφ
k
,
ξ
(
p
p
) as the probability of recovering k input packets at the receiver after ξ
+
k
/
1
-
p
p packets are transmitted at a sender. This probability can be given by the following equation:(10)
φ
k
,
ξ
p
p
=
∑
ξ
=
0
ξ
B
ξ
+
k
1
-
p
p
;
k
+
ξ
,
1
-
p
p
ψ
k
k
+
ξ
>
∏
i
=
0
ξ
-
m
-
1
+
k
/
2
1
-
2
i
-
k
-
ξ
.


## 4. RLT Code Based Handshake-Free Reliable MAC Protocol

Once the problems of degree distribution, encoding, and decoding of RLT code are solved in advance, a reliable RLT-based media access control protocol is needed for nodes to communicate in real time. Wireless transceivers often work in half-duplex mode, and a sending node equipped with a single channel cannot receive packets at the same time [20], so RCHF solution should be able to avoid interference caused by transmitting to a node in sending state. So far, in MAC solutions of wireless multihop packet networks, RTS/CTS handshake is usually used to determine dynamically if the intended receiver is ready to receive a frame. For underwater sensors, the generating rate of data bits is about 1–5 bps and the optimal packet-load for UWSN is about one hundred of bytes [22]; whereas the length of RTS is a few dozen bytes. So, RTS/CTS frames are not too small compared with data frames, and the benefits from RTS/CTS handshake are unremarkable. On the contrary, considering the characteristics of acoustic communication such as low bandwidth, long propagation delay, RTS/CTS handshake decreases channel utilization and network throughput dramatically while prolonging end-to-end delay. So, coupled closely with RLT code, we put forward a state based, handshake-avoidance reliable MAC solution for UWSN which is detailed in this section.


### 4.1. Reliable Transmission Mechanism

In RCHF MAC solution, a source node first groups input packets into blocks of sizek; that is, there are k input packets in the block. Then, the source node encodes the k packets and sends the encoded packets into network. A block size of 50 requires that the minimum time interval for the communication between a sender and a receiver is about 60 s [7], which meets the limited transmission time between the two nodes in UWSN. By setting the block size k appropriately, RCHF can control the transmission time and allow the receiver to be able to receive enough encoded packets in order to reconstruct the original block even when the nodes are moving. The encoded packets are forwarded from the source to the destination block by block and each block is forwarded hop-by-hop.In RCHF protocol, the nodes which are sending packets are thought to be in transmission phase. In order to avoid the collision of transmission synchronization between data and ACK, reduce the overhead from overredundancy and compromise between transmission efficiency and fairness, two transmission constraints are defined as follows.(1)
The maximum number of data frames allowed to transmit in one transmission phase isN
m
a
x.
(2)
The minimum time interval between two transmission phases of the same node isT
a. The node waiting for T
a expiration is considered to be in transmission-avoidance phase. Present underwater acoustic modems are half-duplex, the delay of state transition between sending and receiving usually ranges from hundreds of milliseconds to several seconds, which is close to the magnitude of the maximum round-trip time (RTT) [18]. To facilitate to the receiver to switch to sending state to transmit the ACK, we set T
a
=
2
×
R
T
T.After transmittingN, N
≤
N
m
a
x encoded packets, the sender switches to the receiving state, waiting for the ACK from the receiver. In order to reconstruct the original k input packets with high probability at the receiver, the number of encoded packets received successfully should be larger than k, which is k
+
ξ. Considering the high packet error rate p
p, we set N
=
k
+
ξ
/
1
-
p
p. The parameter ξ, (
ξ
>
0
) is fixed and corresponds to the expected number of redundant encoded packets received by the receiver. ξ redundant packets are used to decrease the probability that the receiver fails to restore the original k input packets through one transmission phase and the factor 1
/
1
-
p
p is used to compensate for some channel errors.In ACK, the number of frames received at the receiver are included, which can be used to update the packet error ratep
p on this hop on the fly, as well as the indices of input packets unrecovered. If the receiver can reconstruct the whole block, it sends back an ACK with “null” in the index field.Givenk
1 input packets unrecovered after the previous transmission phase, the sender encodes and transmits N
1 encoded packets, N
1
=
k
1
+
ξ
/
1
-
p
p, with the degree distribute given by (3) in RLT code, in which k is replaced by k
1 in the next transmission phase, and then collects feedback from the receiver repeatedly until receiving the ACK with “null” in the index field.


### 4.2. State Based Handshake-Free Media Access Control

After network initialization, each node maintains one neighbor table dynamically as in Table2, which includes a state field recording the real-time state of neighbor nodes. In Table 2, state “0” indicates that the neighbor node is in sending state, state “1” indicates that the neighbor node is receiving frames from other nodes, “2” means unknown state, and “3” means the neighbor node is in send-avoidance phase. The format of frames in our protocol is in Table 3. The frame sequence number is used to identify the frame of one frame chain in one transmission phase, the field of original packet ID is used to indicate the IDs of packets which are XORed, and the immediate ACK field is used to inform whether the receiver should return a ACK immediately or not, in which “1” is for yes and “0” is for no.Table 2
The state table of neighbor nodes.
Value
State
0
Sending state
1
Receiving frame from other nodes
2
Unknown state
3
Send-avoidanceTable 3
The format of data frame.
Bits: 8
8
8
2
6
1
23
Variable
16
Previous node layer
Previous node ID
Next node ID
Type00: data01: ACK
Frame sequence number
Immediate ACK
The IDs of Original packets
data
FCS
Head
load
tailAs a node has packets to send, it searches the neighbor table for the state field of the intended receiver. If the state is “0” or “1,” it will put off delivery till the state is greater than one; otherwise, the sender will turn into transmission phase and start to deliver frames. The pseudocodes for sending data are described in Algorithm1. In lines (4)–(9), we give the pseudocodes of encoding a block and encapsulating. In lines (11)–(13), we give the pseudocodes of waiting for delivery when the receiver is determined to be busy. In lines (14)–(41), we give the pseudocodes of delivering a block when the state of the receiver is unknown or send-avoidance. From lines (17)–(21), we can see that, only after the first frame is acknowledged by the receiver, the sender will transmit subsequently the other frames in the block.Algorithm 1:Encoding and transmitting.
(1)    INPUT: data block
(2)    OUTPUT: encoded packets delivery
(3)    Upon  receiving a data block of size  k  do
(4)      encodes k packets to generate N encoded packets;
(5)      set the frame sequence number of the first encoded packet to N;
(6)      // used to notice the overhearing nodes that the sender will transmit N
-
1 frames subsequently
(7)      set the frame sequence number of the second packet to N
-
1, and so on till last to “1”;
(8)      // also used to notice the overhearing nodes the frame number transmitted subsequently
(9)      set the “immediate ACK” field of the first frame as well as the last to “1”, others to “0”;
(10)   find the next hop (receiver) in routing table;
(11)   while  (the state of the receiver ≤1)  then
(12)   put off delivery;
(13)   endwhile
(14)     if  (the state of the receiver >1) & (backoff_timer is timeout)  then
(15)   switch to sending state and transmit the first frame; // start one transmission stage
(16)   switch to receiving state; // waiting for the ACK
(17)
if  (receive the ACK for the first frame with “0” in the index field)  then
(18)    switch to sending state and send the other frames subsequently;
(19)    set  backoff_time = T
a;
(20)    switch to receiving state; // waiting for ACK for the block
(21)    // the first transmission stage for the block is over.
(2
2)    if  (receive the ACK for the block)  then
(2
3)    if  (k
1 frames of the block are unrecovered successfully, (
k
1
≤
k
))  then
(24)     set k
=
k
1;
(25)     goto  line (4);
(26)    endif
(27)
else  (not receive the ACK for the block)
(28)     if  (the state of the receiver >1) & (backoff_timer is timeout)  then
(29)      switch to sending state and send the last frames again;
(30)      switch to receiving state; // waiting for ACK for the block again;
(31)     else
(32)      goto  line (28);
(33)     endif
(34)      goto  line (22);
(35)
endif
(36)
else  (not receive the ACK for the first frame)
(37)
set  backoff_time = T
a;
(38)
goto  line (11);
(39)
endif
(40)     endif
(41) enduponThe pseudocodes for collecting the state information of neighbor node are described in Algorithm2.Algorithm 2:Collecting the state information of neighbor node.
(1)    INPUT: overhear a frame from a neighbor
(2)    OUTPUT: refresh the state of the neighbor’s in neighbor table
(3)    Upon  overhearing a frame  do
(4)        if  (not an ACK) & (the sequence number >1)  then
(5)       set the state of the neighbor to “0”;
(6)       else if  (not an ACK) & (the sequence number = 1)  then
(7)       set the state of the neighbor to “3”; // indicates the unknown state
(8)       else if  (is an ACK with null index)  then
(9)       set the state of the neighbor to “2”; // indicates the unknown state
(10)    else if  (is an ACK) & (the value of index field is “0”)  then
(11)     set the state of the neighbor to “1”; // ready to receive frames from other nodes
(12)    endif
(13) endupon


## 4.1. Reliable Transmission Mechanism

In RCHF MAC solution, a source node first groups input packets into blocks of sizek; that is, there are k input packets in the block. Then, the source node encodes the k packets and sends the encoded packets into network. A block size of 50 requires that the minimum time interval for the communication between a sender and a receiver is about 60 s [7], which meets the limited transmission time between the two nodes in UWSN. By setting the block size k appropriately, RCHF can control the transmission time and allow the receiver to be able to receive enough encoded packets in order to reconstruct the original block even when the nodes are moving. The encoded packets are forwarded from the source to the destination block by block and each block is forwarded hop-by-hop.In RCHF protocol, the nodes which are sending packets are thought to be in transmission phase. In order to avoid the collision of transmission synchronization between data and ACK, reduce the overhead from overredundancy and compromise between transmission efficiency and fairness, two transmission constraints are defined as follows.(1)
The maximum number of data frames allowed to transmit in one transmission phase isN
m
a
x.
(2)
The minimum time interval between two transmission phases of the same node isT
a. The node waiting for T
a expiration is considered to be in transmission-avoidance phase. Present underwater acoustic modems are half-duplex, the delay of state transition between sending and receiving usually ranges from hundreds of milliseconds to several seconds, which is close to the magnitude of the maximum round-trip time (RTT) [18]. To facilitate to the receiver to switch to sending state to transmit the ACK, we set T
a
=
2
×
R
T
T.After transmittingN, N
≤
N
m
a
x encoded packets, the sender switches to the receiving state, waiting for the ACK from the receiver. In order to reconstruct the original k input packets with high probability at the receiver, the number of encoded packets received successfully should be larger than k, which is k
+
ξ. Considering the high packet error rate p
p, we set N
=
k
+
ξ
/
1
-
p
p. The parameter ξ, (
ξ
>
0
) is fixed and corresponds to the expected number of redundant encoded packets received by the receiver. ξ redundant packets are used to decrease the probability that the receiver fails to restore the original k input packets through one transmission phase and the factor 1
/
1
-
p
p is used to compensate for some channel errors.In ACK, the number of frames received at the receiver are included, which can be used to update the packet error ratep
p on this hop on the fly, as well as the indices of input packets unrecovered. If the receiver can reconstruct the whole block, it sends back an ACK with “null” in the index field.Givenk
1 input packets unrecovered after the previous transmission phase, the sender encodes and transmits N
1 encoded packets, N
1
=
k
1
+
ξ
/
1
-
p
p, with the degree distribute given by (3) in RLT code, in which k is replaced by k
1 in the next transmission phase, and then collects feedback from the receiver repeatedly until receiving the ACK with “null” in the index field.


## 4.2. State Based Handshake-Free Media Access Control

After network initialization, each node maintains one neighbor table dynamically as in Table2, which includes a state field recording the real-time state of neighbor nodes. In Table 2, state “0” indicates that the neighbor node is in sending state, state “1” indicates that the neighbor node is receiving frames from other nodes, “2” means unknown state, and “3” means the neighbor node is in send-avoidance phase. The format of frames in our protocol is in Table 3. The frame sequence number is used to identify the frame of one frame chain in one transmission phase, the field of original packet ID is used to indicate the IDs of packets which are XORed, and the immediate ACK field is used to inform whether the receiver should return a ACK immediately or not, in which “1” is for yes and “0” is for no.Table 2
The state table of neighbor nodes.
Value
State
0
Sending state
1
Receiving frame from other nodes
2
Unknown state
3
Send-avoidanceTable 3
The format of data frame.
Bits: 8
8
8
2
6
1
23
Variable
16
Previous node layer
Previous node ID
Next node ID
Type00: data01: ACK
Frame sequence number
Immediate ACK
The IDs of Original packets
data
FCS
Head
load
tailAs a node has packets to send, it searches the neighbor table for the state field of the intended receiver. If the state is “0” or “1,” it will put off delivery till the state is greater than one; otherwise, the sender will turn into transmission phase and start to deliver frames. The pseudocodes for sending data are described in Algorithm1. In lines (4)–(9), we give the pseudocodes of encoding a block and encapsulating. In lines (11)–(13), we give the pseudocodes of waiting for delivery when the receiver is determined to be busy. In lines (14)–(41), we give the pseudocodes of delivering a block when the state of the receiver is unknown or send-avoidance. From lines (17)–(21), we can see that, only after the first frame is acknowledged by the receiver, the sender will transmit subsequently the other frames in the block.Algorithm 1:Encoding and transmitting.
(1)    INPUT: data block
(2)    OUTPUT: encoded packets delivery
(3)    Upon  receiving a data block of size  k  do
(4)      encodes k packets to generate N encoded packets;
(5)      set the frame sequence number of the first encoded packet to N;
(6)      // used to notice the overhearing nodes that the sender will transmit N
-
1 frames subsequently
(7)      set the frame sequence number of the second packet to N
-
1, and so on till last to “1”;
(8)      // also used to notice the overhearing nodes the frame number transmitted subsequently
(9)      set the “immediate ACK” field of the first frame as well as the last to “1”, others to “0”;
(10)   find the next hop (receiver) in routing table;
(11)   while  (the state of the receiver ≤1)  then
(12)   put off delivery;
(13)   endwhile
(14)     if  (the state of the receiver >1) & (backoff_timer is timeout)  then
(15)   switch to sending state and transmit the first frame; // start one transmission stage
(16)   switch to receiving state; // waiting for the ACK
(17)
if  (receive the ACK for the first frame with “0” in the index field)  then
(18)    switch to sending state and send the other frames subsequently;
(19)    set  backoff_time = T
a;
(20)    switch to receiving state; // waiting for ACK for the block
(21)    // the first transmission stage for the block is over.
(2
2)    if  (receive the ACK for the block)  then
(2
3)    if  (k
1 frames of the block are unrecovered successfully, (
k
1
≤
k
))  then
(24)     set k
=
k
1;
(25)     goto  line (4);
(26)    endif
(27)
else  (not receive the ACK for the block)
(28)     if  (the state of the receiver >1) & (backoff_timer is timeout)  then
(29)      switch to sending state and send the last frames again;
(30)      switch to receiving state; // waiting for ACK for the block again;
(31)     else
(32)      goto  line (28);
(33)     endif
(34)      goto  line (22);
(35)
endif
(36)
else  (not receive the ACK for the first frame)
(37)
set  backoff_time = T
a;
(38)
goto  line (11);
(39)
endif
(40)     endif
(41) enduponThe pseudocodes for collecting the state information of neighbor node are described in Algorithm2.Algorithm 2:Collecting the state information of neighbor node.
(1)    INPUT: overhear a frame from a neighbor
(2)    OUTPUT: refresh the state of the neighbor’s in neighbor table
(3)    Upon  overhearing a frame  do
(4)        if  (not an ACK) & (the sequence number >1)  then
(5)       set the state of the neighbor to “0”;
(6)       else if  (not an ACK) & (the sequence number = 1)  then
(7)       set the state of the neighbor to “3”; // indicates the unknown state
(8)       else if  (is an ACK with null index)  then
(9)       set the state of the neighbor to “2”; // indicates the unknown state
(10)    else if  (is an ACK) & (the value of index field is “0”)  then
(11)     set the state of the neighbor to “1”; // ready to receive frames from other nodes
(12)    endif
(13) endupon


## 5. Performance Evaluation

### 5.1. Simulation Result of RCHF MAC Protocol

In this section, we evaluate the performance of RCHF MAC protocol by simulation experiments. All simulations are performed using NS2 (Network Simulator 2) with an underwater sensor network simulation package extension (Aqua-Sim). Our simulation scenario is similar to the reality, and one hundred nodes are distributed randomly in an area of 7000 m × 7000 m× 2000 m. Simulation parameters are shown in Table 4.Table 4
Simulation parameters.
Parameter
Value
Block sizek
50
Packet lengthl
160 bytes
Bandwidth
10 kbps
Routing protocol
static
Traffic
CBR
Transmission range
1500 m
MAC protocol
802.11The protocol is evaluated in terms of average end-to-end delay, end-to-end delivery ratio, energy-consumption as in Figure2, and throughput as in Figure 3. We define the delivery ratio and throughput of RCHF protocol as follows.(1)
The end-to-end delivery ratio is defined as the following equation:(11)
e
n
d
-
t
o
-
e
n
d
d
e
l
i
v
e
r
y
r
a
t
i
o
=
#
o
f
p
a
c
k
e
t
s
r
e
c
e
i
v
e
d
s
u
c
c
e
s
s
f
u
l
l
y
a
t
s
i
n
k
#
o
f
p
a
c
k
e
t
s
g
e
n
e
r
a
t
e
d
a
t
s
o
u
r
c
e
s
.
(2)
The throughput is defined as the number of bits delivered to the sink node per second (bps).Figure 2
Performance versus hop count of RCHF.Figure 3
Network throughput versus packets interval of RCHF.From Figure2, we can observe that the end-to-end delivery ratio of RCHF protocol is close to “1” when the hop count is “1” and decreases slightly with the increase of hop count, which is considered to be good performance for UWSN in the aspect of delivery ratio. Figure 2 also shows that the end-to-end delay and total energy-consumption rise with hop count, which is easily understood. Notice that the real value of end-to-end delivery ratio is the value of ordinate axis divided by 10.As shown in Figure3, the network throughput of RCHF decreases with the interval time between two successive packets generated by the source node. The reason is that the longer the interval time, the less the packets generated and the less the network load.


### 5.2. Performance Comparison

To the best of our knowledge, SDRT [7] and CCRDT [8] are two reliable data transport protocols for UWSN up to date. In this section, we conduct a large number of simulation experiments and compare the performance of RCHF with SDRT and CCRDT in the aspects of throughput and overhead. To facilitate comparing, the network parameters in this section are set as SDRT and CCRDT. The nodes are in a 4-hop string topology; the block size k is 5; the packet length l is between 50 and 200 bytes; the max bit rate is 800 bps. We use Poisson traffic generator to generate packets with time interval following a Poisson distribution. The overhead is defined as the ratio between the number of extra frames transmitted over multiple hops in the network and the number of original input packets.The impact of packet length on the throughput of three protocols is shown in Figure4(a). We can see that with different packet lengths from 50 to 200 bytes, RCHF achieves better end-to-end throughput than SDRT and CCRDT. Also, we observe that end-to-end throughput of three protocols goes up with the length of packets. However, the throughput of RCHF and CCRDT rise faster than SDRT with the growth of packet length. One of the reason is that RCHF and CCRDT adapt to the increasing PERs better than SDRT due to the PERs estimation, and RCHF can get more exact estimation of PERs by including the information of frames which are damaged or lost in a transmission phase in the ACK of RCHF.Figure 4
Performance comparison.
(a)
Throughput versus packet length
(b)
Throughput versus bit rate
(c)
Throughput versus hop count
(d)
Overhead versus hop countThe impact of bit rate on end-to-end throughput is shown in Figure4(b), where packet length is 200 bytes. Again RCHF outperforms SDRT and CCRDT. The reason is that RLT code in RCHF adopts recursive encoding with higher efficiency than fully random encoding, so it reduces the amount of encoded frames necessary received to reconstruct the block.The impact of hop count on end-to-end throughput is shown in Figure4(c). We can see that RCHF achieves the highest throughput among the three protocols. As the hop count rises, the throughput of all three protocols decreases, and the throughput of SDRT degrades faster than the other two protocols. That is because the packages in RCHF are forwarded according to the state of the receiver and can avoid the sending-receiving collisions and overhearing collisions; further, the time interval of transmission-avoidance in RCHF decreases dramatically the data-ACK collision, whereas SDRT has a larger chance to suffer from collisions with more hops. So, from Figure 4(c), we can see that RCHF MAC protocol improves channel utilization remarkably.The impact of hop count on overhead is shown in Figure4(d). As aforementioned, overhead is defined as the ratio between the number of extra frames transmitted over multiple hops in the network and the number of original input packets, where the number of extra frames is denoted by ∑
i
=
1
m
N
i
-
k
i, and i denotes the ith transmission phase. We can see that the overhead of RCHF and CCRDT stays mostly unchanged for different hop counts primarily because the PERs estimation of RCHF and CCRDT minimizes the amount of unnecessary encoded packets. Also, we can see that RCHF achieves a smaller overhead than the other two protocols for its efficient recursive encoding.


## 5.1. Simulation Result of RCHF MAC Protocol

In this section, we evaluate the performance of RCHF MAC protocol by simulation experiments. All simulations are performed using NS2 (Network Simulator 2) with an underwater sensor network simulation package extension (Aqua-Sim). Our simulation scenario is similar to the reality, and one hundred nodes are distributed randomly in an area of 7000 m × 7000 m× 2000 m. Simulation parameters are shown in Table 4.Table 4
Simulation parameters.
Parameter
Value
Block sizek
50
Packet lengthl
160 bytes
Bandwidth
10 kbps
Routing protocol
static
Traffic
CBR
Transmission range
1500 m
MAC protocol
802.11The protocol is evaluated in terms of average end-to-end delay, end-to-end delivery ratio, energy-consumption as in Figure2, and throughput as in Figure 3. We define the delivery ratio and throughput of RCHF protocol as follows.(1)
The end-to-end delivery ratio is defined as the following equation:(11)
e
n
d
-
t
o
-
e
n
d
d
e
l
i
v
e
r
y
r
a
t
i
o
=
#
o
f
p
a
c
k
e
t
s
r
e
c
e
i
v
e
d
s
u
c
c
e
s
s
f
u
l
l
y
a
t
s
i
n
k
#
o
f
p
a
c
k
e
t
s
g
e
n
e
r
a
t
e
d
a
t
s
o
u
r
c
e
s
.
(2)
The throughput is defined as the number of bits delivered to the sink node per second (bps).Figure 2
Performance versus hop count of RCHF.Figure 3
Network throughput versus packets interval of RCHF.From Figure2, we can observe that the end-to-end delivery ratio of RCHF protocol is close to “1” when the hop count is “1” and decreases slightly with the increase of hop count, which is considered to be good performance for UWSN in the aspect of delivery ratio. Figure 2 also shows that the end-to-end delay and total energy-consumption rise with hop count, which is easily understood. Notice that the real value of end-to-end delivery ratio is the value of ordinate axis divided by 10.As shown in Figure3, the network throughput of RCHF decreases with the interval time between two successive packets generated by the source node. The reason is that the longer the interval time, the less the packets generated and the less the network load.


## 5.2. Performance Comparison

To the best of our knowledge, SDRT [7] and CCRDT [8] are two reliable data transport protocols for UWSN up to date. In this section, we conduct a large number of simulation experiments and compare the performance of RCHF with SDRT and CCRDT in the aspects of throughput and overhead. To facilitate comparing, the network parameters in this section are set as SDRT and CCRDT. The nodes are in a 4-hop string topology; the block size k is 5; the packet length l is between 50 and 200 bytes; the max bit rate is 800 bps. We use Poisson traffic generator to generate packets with time interval following a Poisson distribution. The overhead is defined as the ratio between the number of extra frames transmitted over multiple hops in the network and the number of original input packets.The impact of packet length on the throughput of three protocols is shown in Figure4(a). We can see that with different packet lengths from 50 to 200 bytes, RCHF achieves better end-to-end throughput than SDRT and CCRDT. Also, we observe that end-to-end throughput of three protocols goes up with the length of packets. However, the throughput of RCHF and CCRDT rise faster than SDRT with the growth of packet length. One of the reason is that RCHF and CCRDT adapt to the increasing PERs better than SDRT due to the PERs estimation, and RCHF can get more exact estimation of PERs by including the information of frames which are damaged or lost in a transmission phase in the ACK of RCHF.Figure 4
Performance comparison.
(a)
Throughput versus packet length
(b)
Throughput versus bit rate
(c)
Throughput versus hop count
(d)
Overhead versus hop countThe impact of bit rate on end-to-end throughput is shown in Figure4(b), where packet length is 200 bytes. Again RCHF outperforms SDRT and CCRDT. The reason is that RLT code in RCHF adopts recursive encoding with higher efficiency than fully random encoding, so it reduces the amount of encoded frames necessary received to reconstruct the block.The impact of hop count on end-to-end throughput is shown in Figure4(c). We can see that RCHF achieves the highest throughput among the three protocols. As the hop count rises, the throughput of all three protocols decreases, and the throughput of SDRT degrades faster than the other two protocols. That is because the packages in RCHF are forwarded according to the state of the receiver and can avoid the sending-receiving collisions and overhearing collisions; further, the time interval of transmission-avoidance in RCHF decreases dramatically the data-ACK collision, whereas SDRT has a larger chance to suffer from collisions with more hops. So, from Figure 4(c), we can see that RCHF MAC protocol improves channel utilization remarkably.The impact of hop count on overhead is shown in Figure4(d). As aforementioned, overhead is defined as the ratio between the number of extra frames transmitted over multiple hops in the network and the number of original input packets, where the number of extra frames is denoted by ∑
i
=
1
m
N
i
-
k
i, and i denotes the ith transmission phase. We can see that the overhead of RCHF and CCRDT stays mostly unchanged for different hop counts primarily because the PERs estimation of RCHF and CCRDT minimizes the amount of unnecessary encoded packets. Also, we can see that RCHF achieves a smaller overhead than the other two protocols for its efficient recursive encoding.


## 6. Conclusions

In this paper, we propose a kind of digital fountain code, called recursive LT code (RLT). With small degree distribution and recursive encoding, RLT achieves reliable transmission for UWSN hop-by-hop while reducing the complexity of encoding and decoding. Integrated with reliable transmission mechanism based on RLT code, we present RCHF MAC protocol. In RCHF protocol, frames are forwarded according to the state of the receiver which can avoid the sending-receiving collisions and overhearing collisions. In order to reduce the overhead from overredundancy and compromise between transmission efficiency and fairness, two transmission constraints are defined. The time interval of transmission-avoidance in RCHF decreases dramatically the data-ACK collision. Simulations show that RCHF protocol can provide higher delivery ratio and throughput and lower end-to-end delay and resource consumption.As future work, we plan to implement RCHF protocol on real UWSN nodes and conduct extensive experimental tests using real UWSN nodes in order to evaluate the performance and improve the design of RCHF protocol.



---

*Source: 3184642-2016-02-25.xml*