Date of publication xxxx 00, 0000, date of current version xxxx 00, 0000.
10.1109/ACCESS.2017.DOI

This paper is supported in part by National Natural Science Foundation of
China (NSFC) under grant No.(61602447) and No.(61702487). The authors would
like to thank all the people involved in KW14 and KAM11 sea trials.

Corresponding author: Boyu Diao(e-mail: diaoboyu2012@ict.ac.cn).

# A Channel-Aware Routing Protocol With Nearest Neighbor Regression For
Underwater Sensor Networks

BOYU DIAO1  CHAO LI1, QI WANG1, ZHULIN AN1, AND YONGJUN XU1  Institute of
Computing Technology, Chinese Academy of Sciences, Beijing (e-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The underwater acoustic channel is one of the most challenging communication
channels. Due to periodical tidal and daily climatic variation, underwater
noise is periodically fluctuating, which result in the periodical changing of
acoustic channel quality in long-term. Also, time-variant channel quality
leads to routing failure. Routing protocols with acoustic channel estimation,
namely underwater channel-aware routing protocols are recently proposed to
maintain the routing performance. However, channel estimation algorithms for
these routing protocols are mostly linear and rarely consider periodicity of
acoustic channels. In this paper, we introduce acoustic channel estimation
based on nearest neighbor regression for underwater acoustic networks. We
extend nearest neighbor regression for SNR (Signal-to-Noise Ratio) time series
prediction, providing an outstanding prediction accuracy for intricately
periodical and fluctuating received SNR time series. Moreover, we propose a
quick search algorithm and use statistical storage compression to optimize the
time and space complexity of the algorithm. In contrast with linear methods,
this algorithm significantly improves channel prediction accuracy (over three
times at most) on both simulation and sea trial data sets. With this channel
estimation method, we then propose a Depth-Based Channel-Aware Routing
protocol (DBCAR). Taking advantage of depth-greedy forwarding and channel-
aware reliable communication, DBCAR has an outstanding network performance on
packet delivery ratio, average energy consumption and average transmission
delay which is validated through extensive simulations.

###### Index Terms:

Channel Estimation, Depth, Nearest Neighbor, Routing, Underwater Sensor
Networks.

=-15pt

##  I Introduction

During the past decade, there has been a significant development in underwater
acoustic communication, thus inspiring extensive research on underwater sensor
networks (UWSNs). At the same time, marine applications on underwater sensor
networks, including ocean exploration, submarine tracking, and marine rescue
[1, 2, 3] have gradually matured. Long-term and reliable data transmission is
the primary research object for UWSNs which faces many challenges: long
transmission delay as the propagation speed of acoustic waves in water is
approximately 1500 m/s, which is five orders of magnitude lower than that of
radio frequency[4]; limited-bandwidth as it is difficult for the bit rate of
acoustic channels to exceed 100 kbps in a long-range system [5]; time variable
channel as underwater acoustic channel affected by ambient noise, leading to
severe bit error[1].

Due to periodical tidal and daily climatic variation, underwater noise is
periodically changing, result in acoustic channel quality changing with a
periodical trend in long-term. Since underwater acoustic channels are time
variable, it is useful to estimate channel anterior to data transmission, in
order to explore reliable communication links. Also, time-variant channel
quality leads to routing failure. Routing with acoustic channel estimation,
namely underwater channel-aware routing protocols are recently proposed to
maintain the performance of routing protocols[6, 7, 8, 9]. These protocols are
able to investigate a reliable communication path from sources to sinks hop by
hop. In channel-aware routing protocols, acoustic channel quality estimation
is the core process of the best forwarder selection. With a group of quality
indicators, channel quality estimation can be modeled as a time series
analysis problem. Simple mean statistical analysis, exponential moving average
(EMA) and auto-regression (AR) were adopted for underwater channel quality
series analysis. However, these algorithms are linear and rarely consider
periodicity of acoustic channels. With periodical tidal and daily climatic
variation, underwater noise is changing periodically in long-term[10].
Meanwhile, the fluctuations of SNR values exist intrinsic periodicity in long-
term underwater communication.

In this paper, we consider intrinsic periodicity in long-term underwater
acoustic channels and propose the nearest neighbor regression (NNR) based
channel estimation algorithm. Moreover, we propose a depth-based channel-aware
routing (DBCAR) protocol with NNR channel estimation algorithm. Depth-based
routing protocols[11, 12, 13] are location-free and stateless which have
unstable packet delivery ratios in sparse networks but low transmission delay.
On the contrary, channel-aware routing protocols have better packet delivery
rates but high transmission delay. DBCAR with NNR channel estimation provides
a more powerful solution with excellent packet delivery ratios while keeping a
reasonable transmission delay. In summary, we make two significant
contributions for underwater acoustic channel estimation and channel-aware
routing protocols: 1) We introduce NNR for underwater channel quality
estimation, and extend NNR for time series analysis, thus providing a better
prediction precise for intricately periodical and fluctuating received SNR
time series. In addition, we use hash table and statistical storage
compression to optimize the time and space complexity of NNR quality
estimation algorithm. 2) Based on the NNR quality estimation algorithm, we
propose a depth-based channel-aware routing protocol, DBCAR. Besides residual
energy, we take historical statistical parameters, current SNR gradient, and
depth into consideration to explore the best forwarder hop by hop. The
accuracy of NNR quality estimation algorithm has been evaluated through
simulations on different SNR fluctuation scenarios and sea trials data sets,
including ideal periodic fluctuation, periodic fluctuation with stochastic
noises and random periodic fluctuation, and underwater experiment data, KW14
and KAM11. The performance of DBCAR has been evaluated through extensive
simulations using Bellhop[14] and Aqua-sim[15].

The rest of the paper is organized as follows. Selected works on acoustic
channel estimation methods and channel-aware routing protocols are summarized
in Section II. Proposed channel estimation algorithm and a channel-aware
routing protocol are presented in Section III, including NNR channel quality
estimation algorithm, time and space complexity optimization and DBCAR, a
depth-based channel-aware routing protocol with NNR. Extensive evaluations and
results are analyzed in Section IV. Section V concludes this paper.

##  II Related Work

Acoustic channel quality is time-variant [16] while most underwater network
protocols assumed acoustic channel quality is static [17, 11, 18], leading to
unsatisfying network performance, including low packet delivery ratio, low
throughput, and redundant re-transmissions in real underwater environments.
Channel estimation algorithms considering time variability of acoustic
propagation results in a better channel estimation accuracy. Besides,
considering time-variant channel quality provides a practical performance
evaluation for network protocols[19]. Underwater routing protocols with
channel quality estimation, namely channel-aware routing protocols[6, 7, 8, 9]
can investigate a reliable communication path from sources to sinks hop by
hop, maintaining a remarkable network performance in time-variant underwater
acoustic channel states.

Acoustic channel quality estimation is the core process for channel-aware
routing protocols. Historical and current packet success ratio[6, 7] and
received signal-to-noise ratio [8, 9] were taken into account as the primary
channel quality indicator for estimation and prediction. Packet success ratio
(PSR) is the ratio of successful delivery packets and total transmitted
packets counted hop-by-hop between each node and its neighbors. Received
signal-to-noise ratio (SNR) is computed as Equation 1 where $P$ is the
transmission power, $A(r,f)$ is the attenuation over a distance of r with a
signal of frequency f. $N(f)$ is the noise power spectral density and $\Delta
f$ is the receiver noise bandwidth[20]. Packet success ratio and received
signal-to-noise ratio have an equivalence relation from Equation 2[21].
Besides packet success ratio and received signal-to-noise, hops away from
sinks, residual energy, and other auxiliary parameters were also considered
for channel quality estimation and best forwarder selection.

$SNR=\frac{P/A(r,f)}{N(f)\Delta f}$ (1)

$PSR=1-(1-\frac{1}{2}erfc(\sqrt{SNR}))^{L}$ (2)

Channel quality estimation can be modeled as a time series analysis process.
Simple mean statistical analysis[9], exponential moving average (EMA)[6, 22,
7] and auto-regression (AR)[23] were adopted for underwater channel quality
time series analysis. The EMA for a series $Y$ may be calculated recursively
as Equation 3. For AR, the notation AR(p) indicates an auto-regressive model
of order p defined in Equation 4. However, linear time series analysis methods
are not precise for underwater link quality estimation as SNR intricately
fluctuating with ambient noise. Also, SNR fluctuation exists intrinsic
periodicity in long-term underwater communication[10]. Also, these conclusions
can be drawn from real ocean experiments, including KW14 (Fig.1) and
KAM11(Fig.2). KW14 sea trials took place August 2014 in Keweenaw Waterway near
Michigan Tech. Received SNR time series in decibels are presented in Fig.1,
the receiver is 312m away from the transmitter. Kauai Acomms MURI 2011 (KAM11)
Experiment took place from June to July 2011 in waters around the coast of
Martha’s Vineyard (MA, USA), Pianosa (Italy), and Kauai (HI, USA) islands,
respectively. SNR measurements taken on July 8 were shown in Fig.2 [24, 19].

Figure 1: SNR samples in KW14 sea trial  Figure 2: SNR samples in KAM11 sea
trial

$\displaystyle S_{t}=\begin{cases}Y_{1},&t=1\cr\alpha\cdot
Y_{t}+(1-\alpha)\cdot S_{t-1},&t>1\end{cases}$ (3)

$X_{t}=c+\sum^{p}_{i=1}\phi_{i}X_{t-i}+\epsilon_{t}$ (4)

With acoustic channel quality estimation, some channel-aware routing protocols
were proposed [6, 7, 9, 22, 25]. In [22], a cross-layer routing protocol for
UWSN was proposed which exploited link quality information for cross-layer
relay determination. In addition, simple network topology parameters,
including hop count, were considered to improve routing performance. EMA was
selected as the major channel estimation method. [6, 7] extended ideas in [22]
to sea trials and multi-modal communications. In [9] an energy efficiency
channel-aware and depth-based routing protocol was proposed with autonomous
underwater vehicles. Besides channel quality, this paper considered node
energy, hop count and propagation delay to improve routing performance.
Average peak signal-to-noise vectors (PSNR)[26] were used to estimate channel
quality. In [25], a channel-aware, depth-adaptive routing protocol was
proposed, taking sound speed and underwater noises into account to relief the
rate of transmission error. On relay selection, three factors were taken into
consideration: successful transmission probability, the distance between
candidate nodes and the destination, and the distance between candidate nodes
and the ideal path. The successful transmission probability was computed
between a source node and its neighbors respectively.

Figure 3: Network Architecture

Different from above algorithms and protocols, we introduce NNR for underwater
channel quality estimation in this paper, extending NNR for time series
analysis and providing a better prediction precise for intricately periodical
and fluctuating received SNR time series. However, NNR based channel
estimation algorithm is non-linear, thus increasing time and space complexity
than linear algorithms. Therefore, we use hash table and statistical storage
compression to optimize the time and space complexity of NNR quality
estimation algorithm, getting an approximate linear performance. Based on the
NNR quality estimation algorithm, we proposed a depth-based channel-aware
routing protocol (DBCAR). Besides residual energy, we take historical
statistical arguments, current SNR gradient, and depth into consideration to
explore the best forwarder hop-by-hop. We will present proposed algorithm and
protocol in the next section.

##  III Algorithm and Protocol Description

In this section, we start by describing the network model before defining the
initialization process. Then, we present NNR channel quality estimation
algorithm together with time and space complexity optimization methods.
Finally, we present a depth-based channel-aware routing protocol.

###  III-A Network Model

We constitute the network within a cube area. $N$ underwater sensor nodes are
vertically deployed in the area and slowly moving with water currents. As
shown in Fig.3, sensor nodes are uniformly deployed. Besides, there is one or
multiple sinks on the surface. Each sensor node has a unique identification
number and the same transmission power. Channel attenuation function is
defined in Equation 5.

$A(l,f)=l^{p}a(f)^{l}$ (5)

$10logA(l,f)=p\cdot 10logl+l\cdot 10loga(f)$ (6)

where $l$ is transmission distance, $f$ is carrier frequency. $A(l,f)$ is
acoustic channel attenuation function in units of $dB$ given by Equation 6,
$p\in[1,2]$, $a(f)$ is the absorption coefficient.

Once an underwater node deployed into the water and switched on, it will
broadcast a handshake packet to explore neighbors and initialize a vector of
SNR vectors, notated as $M_{SNR}$ based on ACK packets from neighbors given by
Equation 7, where $X^{ID_{1}}$ is the received SNR vector of neighbor
$ID_{1}$. For the NNR channel quality estimation algorithm, the input vector
is an element of $M_{SNR}$, notated as Equation 8, where $x_{t_{1}}$ notates
SNR values is X from a neighbor with $ID_{i}$ at $t_{1}$ moment.

$M_{SNR}=\left[\begin{matrix}X^{ID_{1}}&X^{ID_{2}}&\cdots&X^{ID_{i}}&\cdots&X^{ID_{n}}\end{matrix}\right]$
(7)

$X^{ID_{i}}=\left(\begin{matrix}x_{t_{1}}&x_{t_{2}}&x_{t_{3}}&\cdots\
&x_{t_{m}}\end{matrix}\right)$ (8)

###  III-B NNR Channel Estimation Algorithm

In this section, we extend NNR to the time series prediction problem. In the
primal NNR algorithm, the training set contains a group of vectors taking
values in $\mathbb{R}^{h}$ and $y$ is the output label of each vector given in
Equation 9.

$\begin{matrix}(x_{1}^{1}&x_{2}^{1}&\cdots&x_{h}^{1})&\sim&y_{1}\\\
(x_{1}^{2}&x_{2}^{2}&\cdots&x_{h}^{2})&\sim&y_{2}\\\
(x_{1}^{3}&x_{2}^{3}&\cdots&x_{h}^{3})&\sim&y_{3}\\\
\vdots&\vdots&\vdots&\vdots\\\
(x_{1}^{n}&x_{2}^{n}&\cdots&x_{h}^{n})&\sim&y_{n}\\\ \end{matrix}$ (9)

We want to predict the output label $y_{n+1}$ of
$(x_{1}^{n+1},x_{2}^{n+1},\cdots,x_{h}^{n+1})$ based on the training set. $k$
nearest neighbor vectors are taken from the training set by distance function
(e.g., Euclidean distance function given by Equation 10).

$D(X^{1},X^{2})=\sum^{n}_{i=1}(x_{i}^{1}-x_{i}^{2})^{2}$ (10)

Then, output label $y$ of the input vector is determined by Equation 11 with
inverse distance weighting of the $k$ nearest neighbors where $q$ is a
negative integer, and $d_{i}$ is the distance. Inverse distance weighing is a
weighted average method that weight decreases as distance increases when
computing weighted average.

$y=\sum^{k}_{i}\omega_{i}y_{i}\qquad\omega_{i}=\frac{d_{i}^{q}}{\sum^{k}_{i}d_{i}^{q}}$
(11)

However, in a time series prediction problem, there is no direct output label
$y$ but a vector of values with the same property and constantly accumulate
with time, like the time series in Expression.12.

$\begin{matrix}x_{t_{1}}&x_{t_{2}}&x_{t_{3}}&\cdots\
&x_{t_{n-m}}&\underbrace{x_{t_{n-m+1}}\quad x_{t_{n-m+2}}\cdots
x_{t_{n}}}_{m}\end{matrix}$ (12)

To predict $y_{t+1}$, we define a time window with a length of $m$. We use the
latest $m$ SNR values as an input vector of NNR, then sliding the time window
from the beginning of the SNR vector, setting $m+1$ SNR value as corresponding
output $y$, thus getting a training set notated in Expression.13 ($m=3$). With
the training set, we can calculate distances step by step, getting $k$ nearest
vectors in $m$ dimension. With $k$ nearest vectors, we get $k$ prediction
values, constituting the prediction vector. For example, we assume
$k=2,m=3,n=10$, and we want to predict $x_{11}$. Therefore, the input vector
of NNR is $(x_{8},x_{9},x_{10})$. Then, we assume the 2 nearest neighbor is
$(x_{1},x_{2},x_{3})$ and $(x_{4},x_{5},x_{6})$ with distances $d_{1}$ and
$d_{4}$ away from the input vector. Thus, we get the prediction vector
$(x_{4},x_{7})$. With inverse distance weighting function given by Equation
11, we get prediction value of time
$x_{11}=\frac{d_{1}^{p}}{d_{1}^{p}+d_{4}^{p}}x_{4}+\frac{d_{4}^{p}}{d_{1}^{p}+d_{4}^{p}}x_{7}$
eventually, where $p$ is generally set to be $2$.

$\begin{matrix}(x_{1}&x_{2}&x_{3})&\sim&x_{4}\\\
(x_{2}&x_{3}&x_{4})&\sim&x_{5}\\\ (x_{3}&x_{4}&x_{5})&\sim&x_{6}\\\
\vdots&\vdots&\vdots&\vdots\\\
(x_{n-3}&x_{n-2}&x_{n-1})&\sim&x_{n}\end{matrix}$ (13)

The time complexity of this algorithm is $O(nm)$ and space complexity is
$O(n)$ where $n$ is the length of an SNR vector, and $m$ is the length of
sliding window. However, it is not an efficient solution so that we will
optimize the time and space complexity of this algorithm in the next section.

###  III-C Algorithm Optimization

Time Complexity Optimization: We adopt a hash table to store SNR records.
Multiplying each SNR by $10^{3}$ and keeping the integral part to form a new
SNR vector. Using an arbitrary hash function to compute an index. We get hash
keys from SNR values and hash values are the corresponding time stamps of SNR
values, then putting SNR values into an array of buckets, from which the time
stamp of an expected SNR value can be directly found. When finding $k$ nearest
neighbors, we shorten searching range after the $min$ values upgraded. In
general, we usually initial the $k$ $min$ values with a big number, e.g.
65535. Therefore, the initial searching interval is the whole SNR vector.
During the calculation, we update the $k$ $min$ values while we get a distance
smaller than the max value of $k$ $min$ values. Once the $k$ $min$ values
updated, we shorten the search range with recently updated $min$ value. The
searching interval is given in Expression 14 where $x_{t_{n-m+1}}$ is defined
in Expression 8.

$\left[\left\lfloor x_{t_{n-m+1}}-\sqrt{min}\right\rfloor,\left\lceil
x_{t_{n-m+1}}+\sqrt{min}\right\rceil\right]$ (14)

Space Complexity Optimization: Length of an SNR vector is continuously
increasing with time, consuming lots of hard disk space. SNR values far from
now have little significance for current prediction. So we employ time inverse
distance weighting like Equation 15 to compress prior SNR values. We set a
storage limit $L$ and a period $T$. When the length of SNR vector reaches $L$
or the sensor node operates for $T$ hours, the compression process will be
triggered. The first $\alpha L$ SNR values will be compressed into an inverse
distance weighting average, then the length of SNR vector is $(1-\alpha)L$,
where factor $\alpha\in[0,0.5]$.

$y=\sum^{\alpha
L}_{i}\omega_{i}x_{i}\qquad\omega_{i}=\frac{d_{i}^{p}}{\sum^{L}_{i}d_{i}^{p}}$
(15)

Then we will prove that the time complexity of the optimized algorithm will be
reduced by orders of magnitude. Underwater channel quality is mainly affected
by marine environmental parameters such as hydro-meteorology. The statistical
law of general meteorological data conforms to the normal distribution.
Therefore, we assume that the channel quality satisfies the discrete normal
distribution in the proof of algorithm complexity[27]. According to the
conclusions of Szablowski[28], while the variance $\sigma^{2}>0.73$, the
probability density of discrete normal distribution can be approximated by
Equation 16 where $\alpha$ is the mean and $\sigma$ is the variance.

$P(X=i)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(i-\alpha)}{2\sigma^{2}}}$ (16)

Setting the channel quality values fluctuate within $r=|v_{max}-v_{min}|$,
keeping the channel quality two decimal before hashing, that is the same with
multiplying all channel quality values by 100 and retain the integer part. And
now the values fluctuate within $100r$, so the total number of keys in the
hash table in Fig. 4 is at least $100r$

Total number of nearest neighbor calculations is related to the length of
timing sequence vectors $n$, the length of the time window for calculating the
nearest neighbor regression $m$ and the value of target channel quality $i$,
denoted as $T(X=i,m,n)$. When there are $n$ keys, the expected length of the
value vector that is randomly selected in the hash table is
$n\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(s-\alpha)}{2\sigma^{2}}}$. According
to proposed optimized algorithm, $T(X=i,m,n)$ is the sum of the $m$ value
vector lengths of all the data in the hash table (Equation 17).

$\displaystyle T(X=i,m,n)$
$\displaystyle=\frac{n}{\sigma\sqrt{2\pi}}(\frac{1}{e^{\frac{i_{1}-\alpha}{2\sigma^{2}}}}+\frac{1}{e^{\frac{i_{2}-\alpha}{2\sigma^{2}}}}+...\frac{1}{e^{\frac{i_{m}-\alpha}{2\sigma^{2}}}})$
(17)
$\displaystyle\leq\frac{nm}{\sigma\sqrt{2\pi}}(\frac{1}{e^{\frac{i-\alpha}{2\sigma^{2}}}})$

When $r\geq 10$, we have $100r\geq 1000$. The distance between randomly
selected key $i$ and the expectation key $\alpha$ is denoted as $E(i-\alpha)$.
Then we have Equation 18.

Figure 4: SNR Hash Table

$\displaystyle E(i-\alpha)$
$\displaystyle\geq\frac{\sum\limits_{i=1}^{500}i}{500}\geq\frac{500(500+1)}{1000}$
(18) $\displaystyle\geq 250$

While $1<\sigma^{2}<12.5$, we have
$\sigma\sqrt{2\pi}e^{\frac{i-\alpha}{2\sigma^{s}}}\geq\sigma\sqrt{2\pi}e^{1}0\geq
e^{11}$. Then Equation 17 can be further organized as Equation 19.

$\displaystyle T(X=i,m,n)$
$\displaystyle=\frac{n}{\sigma\sqrt{2\pi}}(\frac{1}{e^{\frac{i_{1}-\alpha}{2\sigma^{2}}}}+\frac{1}{e^{\frac{i_{2}-\alpha}{2\sigma^{2}}}}+...\frac{1}{\frac{i_{m}-\alpha}{2\sigma^{2}}})$
(19)
$\displaystyle\leq\frac{nm}{\sigma\sqrt{2\pi}}(\frac{1}{e^{\frac{i-\alpha}{2\sigma^{2}}}})$
$\displaystyle\leq\frac{nm}{\sigma\sqrt{2\pi}e^{10}}$
$\displaystyle\leq\frac{nm}{e^{11.5}}\leq O(\frac{nm}{10^{4.8}})$

Finally, we get that, when $r>10,1<\sigma^{2}<12.5$, proposed optimized
algorithm is able to reduce time complexity by approximately 5 orders of
magnitude.

###  III-D DBCAR: a depth-based channel-aware routing protocol

In this section, we apply NNR-based channel estimation algorithm to depth-
based routing protocols, then propose a depth-based channel-aware routing
protocol, DBCAR. Depth-based routing protocols are location-free and stateless
with unstable packet delivery rates in sparse networks but low transmission
delay. On the contrary, channel-aware routing protocols have better packet
delivery rates but high transmission delay. DBCAR with NNR channel estimation
provides a more powerful solution among depth-based routing protocols and
channel-aware routing protocols with outstanding packet delivery rates while
keeping a reasonable transmission delay.

In DBCAR, each underwater node has three operation processes, including the
initialization process, the listening process, and the forwarding process.
Transition relationship between the three processes is described in Fig.5.

Each underwater node starts initialization process once deployed into the
water and switched on. In the initialization process, each node broadcasts a
handshake packet containing node ID and initial energy volume. Every neighbor
node that receives the handshake packet will reply an ACK packet containing
node ID and residual energy volume. With ACK packets and the corresponding
received SNR values, nodes in initialization process construct the list of SNR
vectors described in Section III-A. Besides the list of SNR vectors, we
utilize residual energy which can be obtained in a variety of ways[29][30],
historical SNR means, and variances as auxiliary parameters for best forwarder
selection. After the initialization process, each underwater node has a list
of neighbor nodes information, including received SNR vectors, latest residual
energy and historical SNR means and variances, then changes to the listening
process.

Figure 5: Transition Relationship between Operation Processes

In the listening processes, each node keeps listening and analyzing every
received packets. When parsing received packet, the node obtains received SNR,
residual energy, forwarder ID and other information of the source node. We
assume a node $A$ in the listening process receives a packet from node $B$.
Then node $A$ will update received SNR vectors and other parameters
corresponding to node $B$ in $M_{SNR}$ (defined in Equation 8). If the
forwarder ID is the same with node $A$, this node will change to forwarding
process. Because node $B$ has chosen node $A$ as the best forwarder.
Otherwise, node $A$ maintains in the listening process. To calculating mean
and variance of received SNR values based on time series, we introduce a
recursive algorithm utilizing only the latest arrived value, latest mean and
variance. This algorithm has a time complexity of $O(n)$ in contrary to the
naive calculation of mean and variance using all historical data with the time
complexity of $O(n^{2})$. The mean and variance calculation methods are
expressed in the form of recursion formula as Equations.20, 21 and 22.

${{M}_{i}}=\frac{\text{i}-1}{\text{i}}{{M}_{k-1}}+\frac{1}{\text{i}}{{x}_{\text{i}}}$
(20)

${{S}_{i}}={{S}_{i-1}}+({{x}_{i}}-{{M}_{i}})({{x}_{i}}-{{M}_{i-1}})$ (21)

$V=\frac{{{S}_{i}}}{i-1}$ (22)

where $i$ is the number of total SNR values, $x_{i}$ is the latest arrived SNR
value, $M_{i-1}$ is latest mean and $\frac{S_{i-1}}{i-2}$ is latest variance.
$M_{i}$ and $V$ are updated mean and variance of all historical SNR values.

A brief demonstration of Equation 20 is given in Equation 23,24 and 25. In
addition, a brief demonstration of Equation21 is given in Equation III-D.

${{M}_{i}}=\frac{{{x}_{i}}+{{x}_{i-1}}......+{{x}_{1}}}{i}$ (23)

${{M}_{i\text{-}1}}=\frac{{{x}_{i-1}}......+{{x}_{1}}}{k\text{-}1}$ (24)

$k{{M}_{i}}-(i-1){{M}_{i\text{-}1}}={{x}_{n}}$ (25)

$\displaystyle{{S}_{i}}$
$\displaystyle=\sum\limits_{j=1}^{i}{{{({{x}_{j}}-{{M}_{n}})}^{2}}}$
$\displaystyle=\sum\limits_{j=1}^{i-1}(x_{j}-M_{i-1}-\frac{x_{i}-M_{i-1}}{i})^{2}+(\frac{(i-1)(x_{i}-M_{i-1})}{i})^{2}$
$\displaystyle=\sum\limits_{j=1}^{i-1}{{{({{x}_{j}}-{{M}_{i-1}})}^{2}}+\left[\frac{i-1}{{{i}^{2}}}+\frac{{{(i-1)}^{2}}}{{{i}^{2}}}\right]}{{({{x}_{i}}-{{M}_{i-1}})}^{2}}$
$\displaystyle={{S}_{i-1}}+(\frac{i-1}{i}){{({{x}_{i}}-{{M}_{i-1}})}^{2}}$
$\displaystyle={{S}_{i-1}}+({{x}_{i}}-{{M}_{i-1}})({{x}_{i}}-{{M}_{i}})$

As mentioned in the listening process that once a node receives a packet with
the same ID with its own, it will change to the forwarding process. Nodes in
the forwarding process take responsibility to explore the best forwarder for
the next hop. In DBCAR, nodes in forwarding process (the source node) will
broadcast a handshake packet to determine communicable neighbors. Each
neighbor node receives this handshake packet will reply an ACK packet
containing ID, residual energy, and current depth. Then the source node will
consider current received SNR values, current depth, residual energy and
current SNR fluctuation trends and substitute each value into Equation 28,
thus obtaining the calculating result of each neighbor node. The neighbor node
with the highest calculation result will be chosen as the forwarder for the
next-hop. Node ID of the next-hop forwarder will be encoded into the packet
transmitted by the source node. The primal parameter of Equation 28 is $s$ and
$\Delta d$. We use NNR-based channel estimation algorithm in Section III-B to
compute $s$. We traverse $M_{SNR}$ and put each SNR vector into the channel
estimation algorithm. Then we get a vector of $s$ corresponding to each
neighbor of the source node.

$SNR(s,g)=s+\alpha\cdot sgn(g)s$ (27)

$f(SNR(s,g),\Delta d,m,v,E)=\frac{mE}{v}\Delta d\cdot SNR(s,g)$ (28)

In addition, we add a coefficient considering channel stability, residual
energy and SNR prediction value. $\frac{m}{v}$ indicate channel stability
where $m$ and $v$ are the mean and variance of SNR vectors. The neighbor with
a higher mean and lower variance will improve the final calculation result.
Besides, $E$ is ratio of the residual energy and initial energy
$\frac{E_{r}}{E_{all}}$in percentage. Even a node has a good channel quality
but is running out of energy, the node might not be chosen as the best
forwarder. It is an efficient strategy to balance energy so as to extend
network lifetime. $SNR(s,g)$ is given in Equation 27 where $g$ is the gradient
between $t$ and $t-1$ moments and $sgn$ is the sign function.
$\alpha\in[0,0.3]$ is an impact factor of gradient.

Figure 6: Ideal Period Simulation Samples

Figure 7: Period with Random Noise Simulation Samples

Figure 8: Random Period with Random Noise Simulation Samples

Figure 9: Ideal Period Sample Comparison

Figure 10: Period with Random Noise Sample Comparison

Figure 11: Random Period with Random Noise Sample Comparison

Figure 12: Ideal Period Sample Comparison

Figure 13: Period with Random Noise Sample Comparison

Figure 14: Random Period with Random Noise Sample Comparison

##  IV Performance Evaluations

Performance evaluations consist of three parts: A) Accuracy evaluations of NNR
acoustic channel estimation algorithm; B) Time and space complexity
optimization evaluation of NNR acoustic channel estimation algorithm; C)
Network performance evaluations of DBCAR with NNR.

###  IV-A Accuracy Evaluations of Channel Estimation Algorithms

We use both simulation and sea trial data-sets to evaluate proposed method. We
simulate ideal period SNR samples, fixed period SNR samples with random noises
and random period SNR samples with random noise, receptively. Moreover, we
used KAM11 and KW14 sea trial data-sets. For acoustic channel estimation
methods, we select EMA, AR(2) and AR(5) to compare with the proposed
algorithm. We analyze times of best estimation and prediction errors,
demonstrating NNR had an outstanding accuracy than other linear methods.

Fig.14-14 present data trends of ideal period data, period data with random
noise and random period data with random noise. Fig.14-14 show the times of
best estimation of the four channel estimation algorithms concerning ideal
period data, period data with random noises and random period data with random
noises, respectively. The size of the data sets increases from 1000 to 10000.
Best estimation is the channel estimation with minimum error in contrary to
real SNR values among the four algorithms. In summary, NNR has an average best
estimation rate of $83.9\%$ with ideal period samples while the second best is
EMA with an average best estimation rate of $4.6\%$, demonstrating that NNR
has perfect performance on period samples. However, real received SNR samples
are not ideal periodicity. Concerning period data with random noises and
random period data with random noises, NNR has an average best estimation rate
of $54.2\%$ and $43.4\%$ while the second best is EMA with an average best
estimation rate of $22.2\%$ and $31.5\%$. With the size of data sets
increasing, the best estimation rate of NNR gradually rises. Fig.14-14 show
average channel estimation error of different algorithms on different data-
sets. Also, NNR is the best among these channel estimation algorithms. Fig.1-2
show data trends of sea trials, KAM11 and KW14. From Fig.15-16 together, we
may conclude that NNR has an average best estimation rate of $47.8\%$ with
KW14 and $42.2\%$ with KAM11 while the second best is MA with an average best
estimation rate of $15.8\%$ with KW14 and $15.2\%$ with KAM11. Fig.17-18 show
average channel estimation error of different methods on sea trial data-sets.
We may conclude that NNR is the best among these channel estimation
algorithms.

Figure 15: Optimal Estimation on KW14 sea trial Figure 16: Optimal Estimation
on KAM11 sea trial Figure 17: Average Estimation Error on KW14 sea trial
Figure 18: Average Estimation Error on KAM11 sea trial

###  IV-B Complexity Optimization Evaluations

In this section, we evaluate time and space complexity optimization in Section
III-C

In Fig.19 and Fig.20, we compare time and space efficiency of naive NNR and
optimized-NNR. Without loss of generality, we set $k$ to be 3 and $\alpha$,
then compare the searching time of $k$ nearest neighbors with the sample size
from $10^{2}$ to $10^{8}$. Obviously, searching time of optimized-NNR
algorithm slightly rises in linear trend while naive NNR in an exponential
trend. In addition, we set $L$ to be $10^{4}$ and $\alpha$ to be $0.2$ in
Equation 15. The result is similar to time complexity comparison. Space
consumption of optimized NNR algorithm stopped increasing at $L$ while naive
NNR rises in an exponential trend. Optimized NNR has an approximate linear
complexity in time and space. However, time and space optimization results in
tiny errors. Fortunately, estimation accuracy of optimized NNR is very close
to naive NNR. The estimation error of optimized NNR is less than $1.48\%$
compared with naive NNR in Fig.21.

###  IV-C Network Performance Evaluations

Network simulations are implemented through Aqua-Sim [15], a widely used UWSN
simulation extension package based on NS-2 [31]. Major underwater
communication parameters are based on a real-world acoustic modem UWM1000
[32]: bandwidth was $10$ $kbps$; power consumption of sending is $2$ $watt$,
receiving is $0.1$ $watt$ and idling is $1\times 10^{-2}$ $watt$. Broadcast
MAC protocol is the same as [11]. $\delta$ in delay function is set to be
$\frac{R}{4}$ in the whole simulation. Sensor nodes are randomly deployed in a
$500\times 500\times 500$ $m^{3}$ underwater area. Three sinks are uniformly
deployed on the surface. The sink nodes are fixed once deployed. For
simplicity and without loss of generality, one of the underwater sensor nodes
is set to be the source node. In addition, depth of the source node is set to
be the max depth and moving slightly and randomly on this plane. Maximal
transmission distance $R$ is $150\ m$. Length of data packets is 100 bytes and
20 bytes for handshake packets in DBCAR and CARP. We run the simulation for
$10^{4}$ seconds then statistic major network parameters. The number of nodes
increases from 100 to 200 with an interval of 10. The source has a packet rate
of $0.1\ packet/s$. Bellhop computes time variable distribution of
transmission loss for different locations. Environment data refer to an area
in Dickins Seamount located at
$54^{\circ}30^{\prime}00^{\prime\prime}N,137^{\circ}00^{\prime}00^{\prime\prime}W$.
Sound Speed profiles (SSP) and bathymetry profiles are provided in Acoustic
Toolbox[33].

Figure 19: Time Complexity Optimization Evaluation Figure 20: Space Complexity
Optimization Evaluation Figure 21: Accuracy Evaluation

In network performance evaluation, we concern three performance metrics:
packet delivery ratio, average end-to-end delay, and average energy cost
defined below.

Packet Delivery Ratio : the ratio of the number of different packets received
at the sink to the number of the total packets transmitted by the source node.
This parameter indicates the reliability of a routing protocol.

Average End-to-End Delay : the average transmission duration for each packet
from the source to the sink. We don’t consider lost packets in this work. This
parameter indicates time efficiency of a routing protocol.

Average Energy Consumption : the average total consumption for each packet
received by the sink. Average energy consumption is the ratio of total energy
consumption of the network to the number of packets received by the sink. This
parameter indicates energy efficiency of a routing protocol.

Fig.22 shows packet delivery ratio of DBCAR, CARP, and DBR in terms of
different network density. As DBCAR using NNR-based channel quality estimation
methods which had an outstanding performance than EMA validated in Section
IV-A, DBCAR exceeds DBR without channel quality estimation and CARP with EMA-
based channel quality estimation in terms of packet delivery ratio. In
contrast with DBR, DBCAR increases packet delivery ratio by 18.2% on average
and 39.7% in max. In contrast with CARP, DBCAR increases packet delivery ratio
by 15.5% on average and 20.8% in max.

Figure 22: Packet Delivery Ratio Evaluation Figure 23: Average End-to-End
Delay Evaluation Figure 24: Average Energy Consumption Evaluation

Comparison of average transmission delays of DBCAR, CARP, and DBR is
illustrated in Fig.23. In Fig.23, DBR has a better time efficiency than DBCAR
and CARP because DBR is a depth-greedy routing protocol considering no channel
parameters. It can explore the neighbor with max depth difference, then make
this neighbor as next forwarder without considering channel quality between
senders and receivers. As defined above, we only statistics successfully
delivered packets in average end-to-end delay results. Although DBR has a
lower packet delivery ratio, packets successfully delivered have a shorter
transmission delay. Also, DBCAR exceeds CARP in time efficiency. According to
simulation results, DBCAR reduces average end-to-end transmission delay by
10.3% on average and 11.3% in max in contrast with CARP.

Comparison of Average energy consumption of the three protocols is illustrated
in Fig.24. DBCAR has an outstanding energy efficiency than DBR and CARP. Both
DBCAR and CARP are single-path routing protocols with a centralized handshake
process to select the best forwarder while DBR is a multi-path routing
protocol producing inevitable redundancy energy consumption. However, depth-
greedy routing reduces hop-counts from sources to sinks for DBR. Therefore,
there are little differences in average energy consumption between DBR and
CARP. DBCAR took advantages of depth-greedy routing and channel-aware routing,
leading to a better energy efficiency. In contrast with DBR, DBCAR reduces
average energy consumption by 26.1% on average and 32.1% in max. In comparison
with CARP, DBCAR reduces average energy consumption by 26.2% on average and
34.4% in max.

##  V Conclusions

In this paper, we introduce NNR for underwater channel estimation. We extend
NNR for time series analysis and obtain a better prediction precise for
intricately fluctuating and periodical SNR time series. Also, we use a hash
table and statistical storage compression to optimize the time and space
complexity of NNR quality estimation algorithm. In contrast with linear
methods, this algorithm significantly improves prediction accuracy on both
simulation and sea trial datasets. With this channel estimation algorithm, we
then propose a depth-based channel-aware routing protocol, DBCAR. Taking
advantage of depth-greedy forwarding and channel-aware reliable communication,
DBCAR has an outstanding network performance on packet delivery ratio, average
energy consumption and average transmission delay which is validated through
extensive simulations.

## References

  * [1] J.-H. Cui, J. Kong, M. Gerla, and S. Zhou, “The Challenges of Building Mobile Underwater Wireless Networks for Aquatic Applications,” Network, IEEE, vol. 20, no. 3, pp. 12–18, 2006.
  * [2] J. Partan, J. Kurose, and B. N. Levine, “A Survey of Practical Issues in Underwater Networks,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. 11, no. 4, pp. 23–33, 2007.
  * [3] G. Han, J. Jiang, N. Sun, and L. Shu, “Secure communication for underwater acoustic sensor networks,” IEEE Communications Magazine, vol. 53, pp. 54–60, August 2015.
  * [4] C. Kam, S. Kompella, G. D. Nguyen, A. Ephremides, and Z. Jiang, “Impact of Relay Placement on Energy Efficiency in Underwater Acoustic Networks,” in MILITARY COMMUNICATIONS CONFERENCE, 2011-MILCOM 2011, pp. 424–429, IEEE, 2011.
  * [5] K. Chen, M. Ma, E. Cheng, F. Yuan, and W. Su, “A survey on mac protocols for underwater wireless sensor networks,” IEEE Communications Surveys Tutorials, vol. 16, pp. 1433–1447, Third 2014.
  * [6] S. Basagni, C. Petrioli, R. Petroccia, and D. Spaccini, “Carp: A channel-aware routing protocol for underwater acoustic wireless networks,” Ad Hoc Networks, vol. 34, pp. 92–104, 2015.
  * [7] S. Basagni, V. D. Valerio, P. Gjanci, and C. Petrioli, “Finding MARLIN: exploiting multi-modal communications for reliable and low-latency underwater networking,” in 2017 IEEE Conference on Computer Communications, INFOCOM 2017, Atlanta, GA, USA, May 1-4, 2017, pp. 1–9, 2017.
  * [8] Y. D. Chen, Y. W. Chen, C. Y. Lien, and K. P. Shih, “A channel-aware depth-adaptive routing protocol for underwater acoustic sensor networks,” in OCEANS 2014 - TAIPEI, pp. 1–6, April 2014.
  * [9] M. R. Bharamagoudra, S. K. S. Manvi, and B. Gonen, “Event driven energy depth and channel aware routing for underwater acoustic sensor networks: Agent oriented clustering based approach,” Computers & Electrical Engineering, vol. 58, pp. 1–19, 2017.
  * [10] N. D. Merchant, K. L. Brookes, R. C. Faulkner, A. W. J. Bicknell, B. J. Godley, and M. J. Witt, “Underwater noise levels in uk waters,” Scientific reports, vol. 6, p. 36942, 2016.
  * [11] H. Yan, Z. J. Shi, and J.-H. Cui, “DBR: Depth-Based Routing For Underwater Sensor Networks,” in NETWORKING 2008 Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet, pp. 72–86, Springer, 2008.
  * [12] B. Diao, Y. Xu, Q. Wang, Z. Chen, C. Li, Z. An, and G. Han, “A reliable depth-based routing protocol with network coding for underwater sensor networks,” in IEEE International Conference on Parallel and Distributed Systems, pp. 270–277, 2017.
  * [13] B. Diao, Y. Xu, Z. An, F. Wang, and C. Li, “Improving both energy and time efficiency of depth-based routing for underwater sensor networks,” International Journal of Distributed Sensor Networks,2015,(2015-10-19), vol. 2015, p. 8, 2015.
  * [14] “Description of BELLHOP algorithm.” http://oalib.hlsresearch.com/Rays/, 2014\.  [Online; accessed Oct, 2017].
  * [15] P. Xie, Z. Zhou, Z. Peng, H. Yan, T. Hu, J.-H. Cui, Z. Shi, Y. Fei, and S. Zhou, “Aqua-Sim: An NS-2 Based Simulator for Underwater Sensor Networks,” in OCEANS 2009, MTS/IEEE Biloxi-Marine Technology for Our Future: Global and Local Challenges, pp. 1–7, IEEE, 2009.
  * [16] N. M. Carbone and W. S. Hodgkiss, “Effects of tidally driven temperature fluctuations on shallow-water acoustic communications at 18 khz,” IEEE Journal of Oceanic Engineering, vol. 25, pp. 84–94, Jan 2000.
  * [17] P. Xie, J.-H. Cui, and L. Lao, “VBF: Vector-Based Forwarding Protocol for Underwater Sensor Networks,” in NETWORKING 2006. Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems, pp. 1216–1221, Springer, 2006.
  * [18] G. Han, J. Jiang, N. Bao, and L. Wan, “Routing protocols for underwater wireless sensor networks,” IEEE Communications Magazine, vol. 53, no. 11, pp. 72–78, 2015.
  * [19] B. Tomasi, G. Toso, P. Casari, and M. Zorzi, “Impact of time-varying underwater acoustic channels on the performance of routing protocols,” IEEE Journal of Oceanic Engineering, vol. 38, no. 4, pp. 772–784, 2013.
  * [20] M. Stojanovic, “On the relationship between capacity and distance in an underwater acoustic communication channel,” in Proceedings of the 1st ACM International Workshop on Underwater Networks, WUWNet ’06, (New York, NY, USA), pp. 41–47, ACM, 2006.
  * [21] M. Stojanovic and J. Preisig, “Underwater acoustic communication channels: Propagation models and statistical characterization,” IEEE Communications Magazine, vol. 47, pp. 84–89, January 2009.
  * [22] S. Basagni, C. Petrioli, R. Petroccia, and D. Spaccini, “Channel-aware routing for underwater wireless networks,” in 2012 Oceans - Yeosu, pp. 1–9.
  * [23] W. Sun and Z. Wang, “Modeling and prediction of large-scale temporal variation in underwater acoustic channels,” in OCEANS 2016 - Shanghai, pp. 1–6.
  * [24] B. Tomasi, J. Preisig, and M. Zorzi, “On the predictability of underwater acoustic communications performance: The kam11 data set as a case study,” in Proceedings of the Sixth ACM International Workshop on Underwater Networks, WUWNet ’11, (New York, NY, USA), pp. 1:1–1:7, ACM, 2011.
  * [25] Y. D. Chen, Y. W. Chen, C. Y. Lien, and K. P. Shih, “A channel-aware depth-adaptive routing protocol for underwater acoustic sensor networks,” in OCEANS 2014 - TAIPEI, pp. 1–6.
  * [26] B. P. Bondzulic, B. Z. Pavlovic, V. S. Petrovic, and M. S. Andric, “Performance of peak signal-to-noise ratio quality assessment in video streaming with packet losses,” Electronics Letters, vol. 52, no. 6, pp. 454–456, 2016.
  * [27] A. W. Kemp, “Characterizations of a discrete normal distribution,” Journal of Statistical Planning and Inference, vol. 63, no. 2, pp. 223 – 229, 1997.  In Honor of C.R. Rao.
  * [28] P. J. Szabłowski, “Discrete normal distribution and its relationship with jacobi theta functions,” Statistics & Probability Letters, vol. 52, no. 3, pp. 289 – 299, 2001.
  * [29] J. U. Kim, M. J. Kang, J. M. Yi, and D. K. Noh, “A simple but accurate estimation of residual energy for reliable wsn applications,” International Journal of Distributed Sensor Networks, vol. 11, no. 8, p. 107627, 2015.
  * [30] A. K. Mishra and A. K. Turuk, “Residual energy-based replica detection scheme for mobile wireless sensor networks,” Security and Communication Networks, vol. 8, no. 4, pp. 637–648, 2015.
  * [31] K. Varadhan, “The NS Manual (formerly NS Notes and Documentation),” 2003.
  * [32] “LinkQuest Underwater Acoustic Modems UWM1000 Specifications.” http://www.link-quest.com/html/uwm1000.htm, 2014.  [Online; accessed Oct, 2014].
  * [33] “Acoustic ToolBox.” http://oalib.hlsresearch.com/Modes/AcousticsToolbox/, 2016\.  [Online; accessed Dec, 2017].

|  Boyu Diao received his B.Eng. degree in computer science from Beijing
Institute of Technology, Beijing, China, in 2012 and became He a Ph. D.
candidate of Institute of Computing Technology, Chinese Academy of Sciences,
Beijing, China, in 2015. He is also a Ph. D. candidate of University of
Chinese Academy of Sciences, Beijing, China. His research focuses on
underwater sensor networks, distributed algorithms and multi-sensor data
fusion.
---|---
|  Chao Li received B.Eng. degree from the Southwest University, Chongqing,
China, in 2008, received his M.Eng. degree in computer science from Beijing
Normal of Technology, Beijing, China, in 2011. He received his PHD degree in
2016 from Institute of Computing Technology (ICT), Chinese Academy of
Sciences. His research interest includes the wireless sensor networks, the
underwater sensor networks and distributed algorithms, and new trends in cloud
platform.
---|---
|  Qi Wang is an assistant professor at Institute of Computing Technology,
Chinese Academy of Sciences (ICT/CAS) in Beijing, China. She received the Ph.D
degree in computer science from Chinese Academy of Sciences, Beijing, China in
2015. Her research focuses on performance evaluation and optimization for
wireless ad hoc and sensor networks.
---|---
|  Zhulin An received the B.Eng. and M.Eng. degrees in Computer Science from
School of Computer and Information, Hefei University of Technology, Hefei,
China, in 2003 and 2006, respectively. He received his PHD degree in 2009 from
Institute of Computing Technology (ICT), Chinese Academy of Sciences and
became an associate professor in 2014. His research interests include parallel
and distributed algorithms and time synchronization in wireless sensor
networks.
---|---
|  Yongjun Xu (M’06) received his B.Eng. degree in computer communication from
Xi’an Institute of Posts & Telecoms (China) in 2001, and then entered
Institute of Computing Technology (ICT), Chinese Academy of Sciences as a
graduate student. He received his PHD degree in 2006 and became an associate
professor in 2008. He is now a professor in Institute of Computing Technology,
Chinese Academy of Sciences. His current research interests include cyber-
physical systems, multi-sensor data fusion.
---|---