# Joint Network Lifetime Maximization and Relay Selection Design in Underwater
Acoustic Sensor Networks

Z. Mohammadi, M. Soleimanpour-Moghadam, S. Talebi, H. Ahmadi Z. Mohammadi is
with the Department of Electrical Engineering, Shahid Bahonar University of
Kerman, Kerman, Iran (e-mail: zahramohammadi@eng.uk.ac.ir). M. Soleimanpour-
moghadam is with the Texas Biomedical Research Institute, Texas, US (e-mail:
msoleimanpour@txbiomed.org). S. Talebi is with the Department of Electrical
Engineering, Shahid Bahonar University of Kerman, Kerman, Iran and the
Advanced Communications Research Institute, Sharif University, Tehran, Iran
(e-mail: siamak.talebi@uk.ac.ir). H. Ahmadi is with the Department of
Electrical Engineering, University of York, York, UK (e-mail:
Hamed.ahmadi@york.ac.uk).
Corresponding author: Mohadeseh Soleimanpour-Moghadam

###### Abstract

The paper proposes a new approach to minimize the number of relays while
maximizing the lifetime of underwater acoustic sensor networks (UASNs). This
involves formulating the relay node placement (RNP) problem as a multi-
objective optimization problem and employing the multi-objective lexicographic
method (MOLM) to solve it. To achieve the optimal solution, the MOLM consists
of two steps. First, the problem of lifetime maximization is tackled to find
RNP solutions. This transforms the RNP into a non-convex optimization problem
which is then converted into a convex programming equivalent. The proposed
method has the same computational complexity as previous relay-node adjustment
(RA) and difference convex algorithm (DCA) methods. The second step introduces
a novel relay node selection to reach the optimal number of relays. Simulation
results demonstrate that it has superior network lifetime and efficiency
compared to RA and DCA.

###### Index Terms:

Underwater sensor node, relay node, critical node, network lifetime, convex
optimization, energy hole.

##  I Introduction

Underwater acoustic sensor networks (UASNs) have attracted a great deal of
attention for various applications including off-shore oil and gas extraction,
oil spills, and natural calamities like tsunami and hurricane forecasts [1].
These networks are composed of multiple nodes that use acoustic transceivers,
which are more suitable for underwater environments than electromagnetic ones
as acoustic signals experience less attenuation in the water. Each node
collects data from its surroundings and transmits it to a surface buoy (SB).
Unfortunately, because of the sparse deployment of UASNs, energy consumption
is high, particularly for the nodes closest to the SB that send a large amount
of data. This can lead to an energy hole, where the nodes closest to the SB
die before the other nodes, making it impossible to forward the remaining data
to the SB [2]. To prolong the lifetime of the network and avoid the energy
hole, much research has been conducted to reduce energy consumption in recent
years.

###  I-A Literature review

The work in [3] studied the cluster-based data forwarding to deal with the
energy efficacy in UASNs. Based on this approach, the sensor nodes are
classified into some clusters, and the cluster heads (CHs) are responsible for
gathering data. Also, the residual energy and location of sensor nodes are
taken into account to select the optimal CHs to prevent the energy hole
problem. Using an autonomous underwater vehicle (AUV) to collect data from
sensor nodes is an another solution to reduce energy consumption in UASNs. For
instance, [4], [5] demonstrate that by employing an AUV, data can be collected
from gateways and gateways can be rotated over time to balance energy
consumption. However, the transmission delays caused by the AUV are very long,
making it difficult to use in time-sensitive applications such as temperature
and salinity evaluations for red tide forecasts [6]. Power control schemes can
also be used to adjust the power level of sensors during communication
depending on the channel status and network conditions [7, 8]. Additionally,
sleeping schemes can be implemented for sensor nodes [9, 10] to help save
energy by keeping them in the sleeping mode for as long as possible. However,
these techniques pose new challenges when dealing with new technologies such
as energy harvesting. To this end, [11, 12] present methods for optimizing
time to foster energy harvesting and prolong the lifetime of the network. But
energy harvesting-based networks struggle with the unpredictability of the
harvested energy. There has been research on designing an optimal routing
protocol. For example, routing protocols can balance energy consumption among
nodes by assigning more energy to nodes that have higher traffic loads [13],
using residual energy as the routing criteria [14], and splitting the
transmission range into different power levels [15].

The high costs and intricate characteristics of underwater networks often
result in their sparse deployment, leading to increased energy consumption. To
overcome this limitation and extend the network’s lifetime, some authors
propose the utilization of micro-relay nodes. These relay nodes possess
identical size and power supply as the sensor nodes. One area of focus to
enhance the network’s lifetime is the strategic placement of these relay
nodes, which is known as relay node placement (RNP). This aspect has garnered
significant attention among researchers. For example, the study by Das et al.
[16] proposed the utilization of relay nodes that dynamically move between
communicating nodes, acting as intermediaries. This strategy aims to decrease
the communication distance between nodes, thereby improving overall energy
efficiency. The authors in [17] proposed a heuristic relay-node adjustment
(RA) scheme for positioning relay nodes in 3-dimensional UASN. This scheme
consists of two steps: initially randomizing the relay nodes on the water
surface and then adjusting their depth. However, the heuristic approach
employed in [17] may yield suboptimal solutions due to its reliance on
simplified rules and assumptions. In contrast, our mathematical solution, as
presented in [18, 19], effectively overcomes these limitations, resulting in
improved accuracy and efficiency. Specifically, [18] introduced the concept of
a line-segment relay node placement (LSRNP), which entailed positioning a
relay node between a critical node and its farthest neighbor. However, it was
demonstrated that LSRNP posed challenges as a complex, non-convex problem,
making practical implementation difficult. Building upon this concept, [19]
explored joint deployment of relay and sensor nodes, employing a difference
convex algorithm (DCA) to derive a low-complexity solution. In contrast to
previous relay node placement schemes, which often employed simplified
restrictions on the feasible space of relay nodes (i.e., a line between
critical node and its farthest neighbor), our approach seeks to overcome this
limitation by seeking the optimal position for relay nodes, ensuring the best
possible arrangement.

TABLE I: Comparisons between related studies on energy management in UASNs Ref. |  Methods Adoption |  Problem Description |  Performance Metrics
---|---|---|---
[3] |  Cluster-based data gathering |  CH selection |  Network lifetime
[4], [5] |  AUV-based data gathering |  Path optimization of AUV |  Collection delay
[7, 8] |  Adjusting the power level of sensors |  Power allocation |  Achievable throughput
[9, 10] |  Changing the network topology |  Link scheduling optimization |  Energy consumption
[11, 12] |  Energy harvesting |  Optimizing time to harvest energy |  Network lifetime
[14] |  Designing routing protocol |  Optimizing the routing criteria |  Balanced energy consumption
[18, 19] |  Line-segment RNP |  Optimizing the position of relay nodes |  Network lifetime
This work |  Multi-objective RNP |  Network lifetime maximization and the number of relay nodes minimization |  Network lifetime and number of relay nodes

###  I-B Contribution

The above mentioned RNP solutions contribute to extending the network lifetime
but still fail to optimize the network lifetime. In this paper we introduce a
framework that addresses the inherent shortcomings of the LSRNP. By exploring
a broader range of potential relay node positions and leveraging advanced
optimization techniques, we aim to significantly improve the accuracy and
optimality of RNP. Additionally, the number of relay nodes deployed in the RNP
is an important factor to consider which is not considered in all previous
works. In which the research in [20] has investigated the effect of the number
of relay nodes on the LSRNP and found that redundant relay nodes do not
increase the network lifetime, but too many can lead to a decrease in network
performance due to the extra time and energy spent in packet forwarding and
receiving data. Motivated by these, we propose a framework that can solve the
RNP efficiently without placing redundant relay nodes in the network. To the
authors’s best knowledge, while RNP is becoming a crucial topic in UASNs, this
is one of the first times that network lifetime maximization is combined with
number of relay nodes minimization. Overall, the paper’s core contributions
are described in the following.

  1. 1.

We formulate the joint problem of maximizing network lifetime and minimizing
the number of relay nodes (NLMA-RNMI) in relay-assisted UASNs as a multi-
objective optimization problem (MOOP). We employ the multi-objective
lexicographic method (MOLM) to achieve Pareto optimality for the given NLMA-
RNMI MOOP. Based on the MOLM, the objectives are prioritized in order of
importance, with network lifetime given the highest priority. Thus, our first
aim is to maximize the network lifetime and subsequently minimize the number
of relay nodes to prevent resource wastage.

  2. 2.

To ensure that the network lifetime is maximized, we propose the Optimal Relay
Node Setting (ORNS) algorithm, which models RNP as a mathematical optimization
problem. This problem considers two criteria in the maximization process:
balancing the energy consumption between sensor nodes and preventing the relay
nodes positioned in outlier positions. We have taken this into account in our
problem formulation, leading to a MOOP RNP. To perform the proposed MOOP RNP,
we use the $\epsilon$-constraint approach. By employing this approach, we
prioritize the network lifetime of the critical node as the objective function
to address the energy hole in the network. Additionally, we incorporate the
relay node’s lifetime as a constraint to ensure an improvement in the overall
network lifetime. We demonstrate that the resulting RNP is non-convex and
introduce a transformation to convert it into a convex optimization problem.

  3. 3.

We then formulate a mixed-integer convex programming model to obtain the
optimal number of relay nodes. To ensure a strong coupling relationship
between network lifetime and the number of relay nodes, we consider the
optimal value of network lifetime as a constraint in the problem of minimizing
relay nodes. This ensures direct communication without the assistance of
intermediate relay nodes when the energy consumption is low. Therefore, this
approach is referred to as the relay selection design.

To better highlight the contribution of this paper, Table I presents a
comparison of this work with different works in the literature. We evaluate
the time complexity of our RNP method, as well as the DCA and RA approaches.
The results indicate that these approaches exhibit the same order of
complexity. Additionally, we conduct several comprehensive simulations assess
their performance. Through these simulations, we compare the effectiveness of
our RNP approach with the others. The outcomes demonstrate that our approach
outperforms the alternative methods in terms of network lifetime.

The rest of the paper is organized as follows: In section ii@, the model of
the system and problem definition are illustrated and described. Some basics
and preliminaries on the MOOP, MOLM, convex optimization problems, difference
convex functions, and other basics —that are used in this work—are described
in section<EMAIL_ADDRESS>The proposed method to RNP and its equivalent convex
programming scheme as well as the relay node selection scheme are presented in
detail in section<EMAIL_ADDRESS>In section v@, the complexity of the proposed RNP is
evaluated. Simulation and comparison results are provided in section vi@ and
finally, the paper concludes in section vii@, recapping its contribution.
Lightface letters denotes scalars. Boldface lowercase letters are employed to
denote vectors and boldface uppercase letters to denote matrices. The
operations $\rm{E(.)},(.)^{T}$ and $\|.\|_{p}$ denote the expectation
operator, transpose, and p-norm respectively. The $[{\mathbf{A}}]_{n*}$ and
${\mathbf{a}}[n]$ stands for $n$-th row and $n$-th column of matrix
$\mathbf{A}$ respectively, and to denote the $(m,n)$ entry of matrix
$\mathbf{A}$ we use $[{\mathbf{A}}]_{mn}$. The $\mathbf{1}$ refers to a vector
with all elements equal to one while $\mathbf{e}_{i}$ denotes a unit vector
with element $i$ equals one and zeros everywhere else. We also denote the
size, i.e., cardinality, of set $S$ by $|S|$. $\rm{dom}$ is an abbreviation of
domain where $\rm{dom}(g)$ describes all the values that go into the function
$g$.

##  II System model and problem formulation

Consider a 3-dimensional multi-hop UASN, as depicted in Fig 1, which consists
of $\rm N$ sensor nodes and $\rm M$ relay nodes deployed in a designated
search field to gather data about the environment. The sensor nodes are
constrained by limited battery power and their positions are randomly
determined. The relay nodes, on the other hand, are strategically placed to
maximize the network lifetime, but are not capable of sensing information from
the environment. Additionally, the SB is situated on the ocean surface to
communicate with a satellite that forwards the data gathered by the sensor
nodes to the onshore sink. The SB is responsible for making RNP decisions in
the field and all the sensor nodes are required to communicate with it in
order to forward parameters. This scheme is effective in maximizing the
network lifetime, while minimizing the number of relay nodes.

Figure 1: Network model with 3-dimensional Cartesian coordinates

It should be noted that the origin of the Cartesian coordinates system is
located on SB. In the proposed scheme, all nodes have the communication range
$C_{R}$, so any two nodes out of this range will not be able to communicate
together. The rate array $\mathbf{R}$ is given as

$\mathbf{R}=\left[\mathbf{R}_{1*}^{T},\ldots,\mathbf{R}_{i*}^{T},\ldots,\mathbf{R}_{|\mathcal{N}|*}^{T}\right]^{T},$
(1)

where $\mathcal{N}$ is the set of all nodes, including sensor nodes
($\mathcal{S}$), relay nodes ($\mathcal{R}$), and the SB, and
$\mathbf{R}_{i*}\in\mathbb{Z}_{+}^{|\mathcal{N}|\times 1}$ is the outgoing
flow vector from node $i$ to other nodes. Additionally,
$\mathbf{r}\left[i\right]\in\mathbb{Z}_{+}^{|\mathcal{N}|\times 1}$ is the
incoming flow vector from other nodes to node $n$ for
$i=1,\ldots,|\mathcal{N}|$. In order to ensure that the flow rate array meets
certain specifications, there are several conditions that must be taken into
account.

  1. 1.

At each sensor node $k$, the sum of outgoing flow rates must be equal to the
sum of incoming flow rates and the generation rate, given as

$\mathbf{R}_{k*}\mathbf{1}=\mathbf{1}^{T}\mathbf{r}\left[k\right]+g_{k},$ (2)

where $g_{k}$ is the generation rate of sensor node $k$. Additionally, at each
relay node, the sum of outgoing flow rates should be equal to the sum of
incoming flow rates,

$\mathbf{R}_{i*}\mathbf{1}=\mathbf{1}^{T}\mathbf{r}\left[i\right].$ (3)

  2. 2.

Underwater acoustic communication faces challenges such as limited bandwidth,
long propagation delays, multipath fading, and high signal attenuation. These
factors affect the achievable data rate and overall link capacity in
underwater acoustic sensor networks. In the context of UASNs, the node’s link
capacity ($L_{c}$) refers to the maximum data rate or throughput that can be
achieved over a communication link between two nodes in the network [21].
Therefore, the sum of outgoing flow rates of each node must be less than the
node’s link capacity ($L_{c}$),

$\mathbf{R}_{n*}\mathbf{1}\leq L_{c},$ (4)

for each node $n\in\mathcal{R}\cup S$.

###  II-A Energy consumption model

Based on the Urick model [22], the energy consumption of sending one bit of
data from one node, $i$, to another node, $j$ is expressed as [23], [17]

$p_{ij}=\begin{cases}p_{s}+\epsilon_{fs}{d^{2}_{ij}}&d_{ij}<d_{t}\\\
p_{s}+\epsilon_{mp}{d^{4}_{ij}}&d_{ij}\geq d_{t}\end{cases},$ (5)

where $d_{ij}$ is the 3-dimensional Euclidean distance between nodes $i$ and
$j$ given by $\left\lVert\mathbf{l}_{i}-\mathbf{l}_{j}\right\rVert$, with
$\mathbf{l}_{i}$ being the position vector of node $i$. Additionaly, $d_{t}$
is a threshold distance to transmit data; $p_{s}$ is the the power consumption
for processing in sending data; $\epsilon_{fs}$ and $\epsilon_{mp}$ represent
transmit amplifier coefficient of free space and multipath model,
respectively. If $d_{ij}<d_{t}$, the amplifier coefficient of free space model
$\epsilon_{fs}$ is adopted. Otherwise, the amplifier coefficient of free
multipath model $\epsilon_{mp}$ is adopted. In UASNs, no matter the free space
module or multipath model, the amplifier coefficient is defined as
$\alpha(f)^{d_{ij}}$ [23], [17], where $\alpha(f)$ is the absorption
coefficient which is derived from Throp’s formula [24] as $10{\rm
log}\alpha(f)=0.1\frac{f^{2}}{1+f^{2}}+\frac{40f^{2}}{4100+f^{2}}+2.75\times
10^{-4}f^{2}+0.003$ for frequencies of the acoustic signal above a few hundred
Hertz and $f$ is the frequency of acoustic signal. Therefore, the expression
(5) is rewritten as:

$p_{ij}=\begin{cases}p_{s}+\alpha(f)^{d_{ij}}{d^{2}_{ij}}&d_{ij}<d_{t}\\\
p_{s}+\alpha(f)^{d_{ij}}{d^{4}_{ij}}&d_{ij}\geq d_{t}\end{cases},$ (6)

The lifetime of an underwater acoustic sensor network (UASN) is defined as the
duration until the death of the first node, as effective communication is only
possible until then [25], [26]. The lifetime of a node, $i$, is expressed as
the ratio of its residual energy, $\epsilon_{i}$, to its total energy
consumption [17]:

$\tau_{i}=\frac{\epsilon_{i}}{\sum_{j\in\mathcal{N}}^{i\neq
j}p_{ij}[\mathbf{R}]_{ij}+p_{r}\sum_{k\in\mathcal{S}\cup\mathcal{R}}^{k\neq
i}[\mathbf{R}]_{ki}},$ (7)

where $p_{r}$ is the energy consumption for receiving one bit, and
$[\mathbf{R}]_{ij}$ is the outgoing flow from node $i$ to node $j$, and
$[\mathbf{R}]_{ki}$ is the incoming flow from node $k$ to node $i$.

The following assumptions are made in the investigation: (1) All sensor and
relay nodes have the same communication range; (2) the movement of sensors is
predictable, and the position of the nodes is known through the localization
process; (3) Link capacity (${L}_{c}$) is considered constant and equal for
all sensor and relay nodes [17]; and (4) Before placing relay nodes, the
network is connected, meaning each sensor node has a route to the SB.

###  II-B Problem formulation

Our goal is to maximize the UASN lifetime while jointly minimizing the number
of required relay nodes. The multi-objective optimization problem is
formulated as below:

$\displaystyle\\{\min{\rm
M},\max\\{\min_{i\in\mathcal{S}\cup\mathcal{R}}\tau_{i}\\}\\},$ (8a) s.t.
$\displaystyle\tau_{i}=\frac{\epsilon_{i}}{\sum_{j\in\mathcal{N}}^{i\neq
j}p_{ij}[\mathbf{R}]_{ij}+p_{r}\sum_{k\in\mathcal{S}\cup\mathcal{R}}^{k\neq
i}[\mathbf{R}]_{ki}},i\in\mathcal{S}\cup\mathcal{R}$ (8b)
$\displaystyle|\mathcal{R}|={\rm M}$ (8c) $\displaystyle
p_{ij}=\begin{cases}p_{s}+\alpha^{d_{ij}}{d^{2}_{ij}}&d_{ij}<d_{t}\\\
p_{s}+\alpha^{d_{ij}}{d^{4}_{ij}}&d_{ij}\geq d_{t}\end{cases},$ (8d)
$\displaystyle
d_{ij}^{2}=\left\lVert\mathbf{l}_{i}-\mathbf{l}_{j}\right\rVert^{2},\forall
i,j\in\mathcal{N},$ (8e) $\displaystyle\mathbf{l}_{r_{i}}\in X_{c},\forall
r_{i}\in\mathcal{R}.$ (8f)

Constraint (8c) sets the number of relay nodes to $\rm M$. Constraint (8d) and
(8e) calculate the energy consumption between node $i$ and $j$ based on the
3-dimensional Euclidean distance between them. Lastly, constraint (8f)
requires that relay nodes must be positioned within the cylindrical area of
the surveillance field with radius $R_{s}$ and depth $H_{s}$.

##  III Preliminaries

In this section, we introduce preliminaries that we will use in the rest of
our study.

######  Definition 1.

We consider a general MOOP as

$\displaystyle\min\\{f_{1}(\mathbf{x}),...,f_{K}(\mathbf{x})\\}$ (9a) s.t
$\displaystyle\mathbf{x}\in\mathcal{X}$ (9b)

with $K$ objectives and a feasible set $\mathcal{X}$. Using MOLM, the
objectives are ranked in order of importance from best to worst. The problem
then begins with the most important objective and continues with the
objectives in the order of their importance. Specifically, in step $i$,
$f_{i}^{*}$ is obtained by sequentially minimizing the objective $f_{i}$. It
is worth noting that, the computed optimal value of each objective is added as
a constraint for the subsequent optimization steps.

######  Definition 2.

In a convex optimization problem, we minimize a convex objective function over
a convex set. This problem is of the form

$\displaystyle\min f_{0}(\mathbf{x})$ (10a) s.t. $\displaystyle
f_{i}(\mathbf{x})\leq 0,i=1,\ldots,m$ (10b) $\displaystyle
h_{i}(\mathbf{x})=0,i=1,\ldots,p$ (10c)

where $\mathbf{x}\in\mathbb{R}^{n}$ and
$f_{0},\dots,f_{m}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ are convex functions
and $h_{i}(\mathbf{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}$ are affine
functions [27]. The important property of this problem is that any locally
optimal solution is also globally optimal.

######  Definition 3.

Let $\Omega$ be a convex set in $\mathbb{R}^{n}$. We say that a function is a
difference convex (DC) if it can be expressed as the difference of two convex
functions on $\Omega$, i.e. if $f(x)=f_{1}(\mathbf{x})-f_{2}(\mathbf{x})$,
where $f_{1}$ and $f_{2}$ are convex functions on $\Omega$ [28]. The function
$f(x)$ is convex when $f_{1}(\mathbf{x})$ and $f_{2}(\mathbf{x})$ are convex
and affine functions, respectively. In general, each convex function is a DC
function, but its reverse is not true.

######  Lemma 1.

The inverse of the function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ will reach
its minimum point at $\mathbf{x}_{0}\in\mathbb{R}^{n}$ if $\mathbf{x}_{0}$ is
the maximum point of $f$. Additionally, this result also holds for the
converse.

###### Proof.

See the theorem 1. 46 in [29]. ∎

##  IV Proposed method

Using the lexicographic optimization algorithm, the lifetime of a network and
the number of relay nodes are optimized in a hierarchical manner. This process
involves two steps to arrive at the optimal solution.

###  IV-A Step 1 - Network lifetime maximization: ORNS scheme

In this case, the problem can be defined as

$\displaystyle\max\\{\min_{i\in\mathcal{S}\cup\mathcal{R}}\tau_{i}\\}$ (11a)
s.t. $\displaystyle\tau_{i}=\frac{\epsilon_{i}}{\sum_{j\in\mathcal{N}}^{i\neq
j}p_{ij}[\mathbf{R}]_{ij}+p_{r}\sum_{k\in\mathcal{S}\cup\mathcal{R}}^{k\neq
i}[\mathbf{R}]_{ki}},i\in\mathcal{S}\cup\mathcal{R},$ (11b)
$\displaystyle|\mathcal{M}|={\rm{M_{0}}}$ (11c) $\displaystyle
p_{ij}=\begin{cases}p_{s}+\alpha^{d_{ij}}{d^{2}_{ij}}&d_{ij}<d_{t}\\\
p_{s}+\alpha^{d_{ij}}{d^{4}_{ij}}&d_{ij}\geq d_{t}\end{cases},$ (11d)
$\displaystyle
d_{ij}^{2}=\left\lVert\mathbf{l}_{i}-\mathbf{l}_{j}\right\rVert^{2},\forall
i,j\in\mathcal{N},$ (11e) $\displaystyle\mathbf{l}_{r_{i}}\in X_{c},\forall
r_{i}\in\mathcal{R}.$ (11f)

The problem at hand is a challenging, non-convex NP-hard problem, which we
have attempted to address through the use of ORNS. This method is designed to
determine the ideal location of a single relay node ($r_{i}$) and can be
extended to identify the best coordinates of all the relay nodes. Furthermore,
ORNS calculates which nodes ($N_{c_{i}}^{u}$) receive data from the most
critical node ($c_{i}$) of the network. This set can be expressed as:

$N_{c_{i}}^{u}=\\{j;[\mathbf{R}]_{{c_{i}}j}>0\\},$ (12)

where $j$ is the nodes that is connected to $c_{i}$. With the optimal
coordinates of $r_{i}$ determined, it can then act as a router to facilitate
the connection between $c_{i}$ and the elements of $N_{c_{i}}^{u}$. In other
words, after placing $r_{i}$ in the network the following equations can be
written:

$[\mathbf{R}]_{c_{i}r_{i}}=\sum_{j\in N_{c_{i}}^{u}}[\mathbf{R}]_{c_{i}j},$
(13) $[\mathbf{R}]_{r_{i}j}=[\mathbf{R}]_{c_{i}j},\forall j\in N_{c_{i}}^{u}.$
(14)

According to the above equations, $r_{i}$ acts as an intermediate node to
forward the information of node $c_{i}$ and thus:

$[\mathbf{R}]_{c_{i}j}=0,\forall j\in N_{c_{i}}^{u}.$ (15)

From the network lifetime perspective, mathematically, two remarks must be
made in regard to the RNP:

######  Remark 1.

In a valid RNP, less energy should be consumed than in a direct transmission,
and the network lifetime is maximized when the $c_{i}$ lifetime is maximized,
which can be expressed as

$\mathbf{l}_{{r}_{{i}}}=\mathrm{argmax}\left({\tau}_{{c}_{{i}}}\right).$ (16)

######  Remark 2.

By defining the residual energy factor of $c_{i}$ as
$\rm{RF}_{i}\triangleq\frac{\epsilon_{c_{i}}}{\epsilon_{p}},$ where
$\epsilon_{p}$ is the primary energy of $c_{i}$, the efficient RNP (ERNP) will
take into account the lifetime of relays especially when the $\rm{RF}_{i}$ is
high, which can be expressed as:

$\mathbf{l}_{{r}_{{i}}}=\mathrm{argmax}\left(\tau_{{r}_{i}}\right)\ \ {s.t.\
}p_{r_{i}j}<p_{c_{i}j}$ (17)

To further illustrate this concept, an example of an RNP in two system
scenarios is given in Fig. 2 where the ERNP considers the case when the relay
node is located within the convex hull of $c_{i}$ and its upper neighbors
$\left(N_{c_{i}}^{u}\right)$, mathematically expressed as follows:

$\mathbf{l}_{r_{i}}\in{\mathrm{conv}}\left\\{\mathbf{l}_{j},\ j\in
N_{c_{i}}^{u}\cup c_{i}\right\\}\triangleq\mathbf{\mathrm{conv}}_{{i}},$ (18)

where $\mathrm{conv}_{i}$ is a convex combination of these
$\left|N_{c_{i}}^{u}\right|+1$ vectors. This system is true if and only if
there is a solution to the following system:

$\mathbf{l}_{r_{i}}=\Big{\\{}\sum_{j\in N_{c_{i}}^{u}\cup
c_{i}}{\theta_{j}\mathbf{l}_{j}}|\theta_{j}\geq 0,\sum_{j\in N_{c_{i}}^{u}\cup
c_{i}}\theta_{j}=1\Big{\\}}.$ (19)

Figure 2: Routing traffic by the two RNPs when $|N_{c_{i}}^{u}|=3$, (a)
$p_{r_{i}j}>p_{c_{i}j}$, (b) $p_{r_{i}j}<p_{c_{i}j}$ (ERNP) Figure 3:
Construction of the feasible space to locate $r_{i}$ using convex hull when
$|N_{c_{i}}^{u}|=3$

The feasible space created by (19) for $r_{i}$ is shown in Fig. 3.

In summary, to meet all the above conditions, the problem of network lifetime
maximization can be given as

$\displaystyle\mathbf{y}_{i}=\arg\left(\max\tau_{c_{i}},\max\tau_{r_{i}}\right),$
(20a) $\displaystyle s.t.$
$\displaystyle\tau_{c_{i}}=\frac{\epsilon_{c_{i}}}{p_{c_{i}r_{i}}[\mathbf{R}]_{{c_{i}}{r_{i}}}+p_{\text{r}}\sum_{k\in\mathcal{S}\cup\mathcal{R}}[\mathbf{R}]_{k{c_{i}}}},$
(20b) $\displaystyle\tau_{r_{i}}=\frac{\epsilon_{r_{i}}}{\sum_{j\in
N_{c_{i}}^{u}}{p_{r_{i}j}[\mathbf{R}]_{{r_{i}}j}}+p_{{r}}[\mathbf{R}]_{{c_{i}}{r_{i}}}},$
(20c) $\displaystyle
p_{c_{i}r_{i}}=\begin{cases}p_{s}+\alpha\left(f\right)^{d_{c_{i}r_{i}}}d_{c_{i}r_{i}}^{2}\
,d_{c_{i}r_{i}}<d_{t}\\\
p_{s}+\alpha\left(f\right)^{d_{c_{i}r_{i}}}d_{c_{i}r_{i}}^{4},\
d_{c_{i}r_{i}}\geq d_{t}\end{cases},$ (20d) $\displaystyle
d_{c_{i}r_{i}}^{2}=\left\|\mathbf{l}_{r_{i}}-\mathbf{l}_{c_{i}}\right\|^{2},$
(20e) $\displaystyle
p_{r_{i}j}=\begin{cases}p_{s}+\alpha\left(f\right)^{d_{r_{i}j}}d_{r_{i}j}^{2}\
,d_{r_{i}j}<d_{t}\\\ p_{s}+\alpha\left(f\right)^{d_{r_{i}j}}d_{r_{i}j}^{4},\
d_{r_{i}j}\geq d_{t}\end{cases},\forall j\in N_{c_{i}}^{u},$ (20f)
$\displaystyle
d_{r_{i}j}^{2}=\left\|\mathbf{l}_{r_{i}}-\mathbf{l}_{j}\right\|^{2},\ \forall
j\in N_{c_{i}}^{u},$ (20g)
$\displaystyle\mathbf{l}_{r_{i}}\in\mathbf{\rm{conv}}_{{i}},$ (20h)
$\displaystyle\left\\{p_{r_{i}j},d_{r_{i}j},p_{c_{i}r_{i}},d_{c_{i}r_{i}}\right\\}\in\mathbb{R}_{+}^{\
},\ \forall j,$ (20i)

that $\mathbf{y}_{{i}}$ denotes the decision variable where
$\mathbf{y}_{{i}}\triangleq\left[\mathbf{p}_{r_{i}},\mathbf{d}_{r_{i}},p_{c_{i}r_{i}},d_{c_{i}r_{i}},\mathbf{l}_{r_{i}},\mathbf{\Theta}\right]\in\mathbb{R}^{3\left|N_{c_{i}}^{u}\right|+6},$
$\mathbf{\Theta}=\left[\theta_{1},\ldots,\theta_{\left|N_{c_{i}}^{u}\right|+1}\right]^{T},$
$\mathbf{p}_{r_{i}}=\left[p_{r_{i}1},\ldots,p_{r_{i}\left|N_{c_{i}}^{u}\right|}\right]^{T},$
and
$\mathbf{d}_{r_{i}}=\left[d_{r_{i}1},\ldots,d_{r_{i}\left|N_{c_{i}}^{u}\right|}\right]^{T}.$

It is important to note that solely maximizing the lifetime of the critical
node can solve the problem of energy hole among sensors and does not guarantee
improving the entire network lifetime. Therefore, our proposed method takes
into account the maximization of both relay nodes and critical nodes
simultaneously. To achieve this, we employ multi-objective optimization
techniques to identify optimal values by exploring trade-offs and finding
desirable solutions across multiple objectives. In the following, we utilize
the $\epsilon$-constraint 111Based on the $\epsilon$-constraint method, a main
and a secondary objective functions are selected, and the purpose is to
optimize the main objective function and limit the secondary function by some
allowable amount.  method to solve the problem (20). Based on this approach,
the lifetime of critical nodes serves as the main objective function, and the
lifetime of the relay node is the secondary objective. The relay node’s
lifetime, as the secondary objective, must be greater than that of the
critical node and is added as a constraint in the optimization problem.
Indeed, we incorporate relay node’s lifetime as a constraint in the
optimization problem to ensure that the entire the network lifetime is
improved. By employing this method, we guarantee the resolving the energy hole
by maximization the lifetime of critical nodes while preserving the lifetime
of relay nodes and avoiding their placement in outlying positions. This
approach effectively resolves the energy hole problem caused between sensor
nodes and enhances the overall network lifetime. To sum up, the RNP is given
as

$\displaystyle\mathbf{x}_{{i}}=\arg\max\tau_{c_{i}},$ (21a) $\displaystyle
s.t.$
$\displaystyle\tau_{c_{i}}=\frac{\epsilon_{c_{i}}}{p_{c_{i}r_{i}}[\mathbf{R}]_{{c_{i}}{r_{i}}}+p_{\text{r}}\sum_{k\in\mathcal{S}\cup\mathcal{R}}[\mathbf{R}]_{k{c_{i}}}},$
(21b) $\displaystyle\tau_{r_{i}}\geq\tau_{c_{i}},$ (21c) $\displaystyle
p_{c_{i}r_{i}}=\begin{cases}p_{s}+\alpha\left(f\right)^{d_{c_{i}r_{i}}}d_{c_{i}r_{i}}^{2}\
,d_{c_{i}r_{i}}<d_{t}\\\
p_{s}+\alpha\left(f\right)^{d_{c_{i}r_{i}}}d_{c_{i}r_{i}}^{4},\
d_{c_{i}r_{i}}\geq d_{t}\end{cases},$ (21d) $\displaystyle
d_{c_{i}r_{i}}^{2}=\left\|\mathbf{l}_{r_{i}}-\mathbf{l}_{c_{i}}\right\|^{2},$
(21e) $\displaystyle\mathbf{l}_{r_{i}}=\sum_{j\in N_{c_{i}}^{u}\cup
c_{i}}{\theta_{j}\mathbf{l}_{j}},$ (21f)
$\displaystyle\mathbf{\Theta}\succcurlyeq\mathbf{0},$ (21g)
$\displaystyle\mathbf{1}^{T}\mathbf{\Theta}=1,$ (21h)
$\displaystyle\mathbf{p}_{r_{i}}\succcurlyeq\mathbf{0},$ (21i)
$\displaystyle\mathbf{d}_{r_{i}}\succcurlyeq\mathbf{0}.$ (21j)

where the decision variable is updated as
$\mathbf{x}_{{i}}\triangleq\left[\mathbf{p}_{r_{i}},p_{c_{i}r_{i}},d_{c_{i}r_{i}},\mathbf{l}_{r_{i}},\mathbf{\Theta}\right]\in\mathbb{R}^{2\left|N_{c_{i}}^{u}\right|+6}.$
It can be shown that the (21c) is rewritten as a linear constraint

$\mathbf{1}^{T}\mathbf{D}\mathbf{x}_{{i}}\leq\gamma_{0},$ (22)

where

$\gamma_{0}=\left(p_{{r}}\sum_{k\in\mathcal{S}\cup\mathcal{R}}[\mathbf{R}]_{k{c_{i}}}\right)\left(\frac{\epsilon_{r_{i}}}{\epsilon_{c_{i}}}\right)-p_{\text{r}}[\mathbf{R}]_{{c_{i}}{r_{i}}},$
(23) $\mathbf{D}=\mathrm{diag}\
\left(a_{1},\ldots,a_{2\left|N_{c_{i}}^{u}\right|+6}\right),$ (24)

and

$a_{j}=\begin{cases}[\mathbf{R}]_{{r_{i}}j},\
j\in\\{1,\ldots,\left|N_{c_{i}}^{u}\right|\\}\\\
-\left(\frac{\epsilon_{r_{i}}}{\epsilon_{c_{i}}}\right)[\mathbf{R}]_{{c_{i}}{r_{i}}},\
j=\left|N_{c_{i}}^{u}\right|+1\\\ 0,\ o.w\\\ \end{cases}.$ (25)

Problem (21) is a non-convex problem that includes the convex objective
function with convex (and/or linear) and DC constraints. Considering that the
constraint (21e) is DC and non-convex, this leads to the non-convexity of the
proposed RNP. However, we explore a novel convex programming model equivalent
to this problem. To do so, we apply a novel transformation to these problems
whose detailed expressions are developed in Appendix A. Based on the proposed
transformation, lemma 1, and definition of variable $t$, the proposed problem
to place $r_{i}$ in the network is the form of

$\displaystyle[\mathbf{x}_{{i}},t]=\arg\min p_{c_{i}r_{i}}$ (26a)
$\displaystyle s.t.$ $\displaystyle
p_{c_{i}r_{i}}=\begin{cases}&p_{s}+\alpha\left(f\right)^{d_{c_{i}r_{i}}}d_{c_{i}r_{i}}^{2}\
,d_{c_{i}r_{i}}<d_{t}\\\
&p_{s}+\alpha\left(f\right)^{d_{c_{i}r_{i}}}d_{c_{i}r_{i}}^{4},\
d_{c_{i}r_{i}}\geq d_{t}\\\ \end{cases}$ (26b)
$\displaystyle\mathbf{1}^{T}\mathbf{D}\mathbf{x}_{{i}}\leq\gamma_{0},$ (26c)
$\displaystyle\left\|\mathbf{l}_{r_{i}}-\mathbf{l}_{c_{i}}\right\|^{2}-t=0,$
(26d) $\displaystyle d_{c_{i}r_{i}}^{2}-t=0$ (26e)
$\displaystyle\mathbf{l}_{r_{i}}=\sum_{j\in N_{c_{i}}^{u}\cup
c_{i}}{\theta_{j}\mathbf{l}_{j}},$ (26f)
$\displaystyle\mathbf{\Theta}\succcurlyeq\mathbf{0},$ (26g)
$\displaystyle\mathbf{1}^{T}\mathbf{\Theta}=1,$ (26h)
$\displaystyle\mathbf{p}_{r_{i}}\succcurlyeq\mathbf{0},$ (26i)
$\displaystyle\mathbf{d}_{r_{i}}\succcurlyeq\mathbf{0}.$ (26j)

which is known as the epigraph form of the problem:

$\displaystyle[\mathbf{x}_{{i}},t]=\arg\min\begin{cases}&p_{s}+\alpha\left(f\right)^{d_{c_{i}r_{i}}}d_{c_{i}r_{i}}^{2}\
,d_{c_{i}r_{i}}<d_{t}\\\
&p_{s}+\alpha\left(f\right)^{d_{c_{i}r_{i}}}d_{c_{i}r_{i}}^{4},\
d_{c_{i}r_{i}}\geq d_{t}\\\ \end{cases}$ (27a) $\displaystyle s.t.$
$\displaystyle\mathbf{1}^{T}\mathbf{D}\mathbf{x}_{{i}}\leq\gamma_{0},$ (27b)
$\displaystyle\left\|\mathbf{l}_{r_{i}}-\mathbf{l}_{c_{i}}\right\|^{2}-t\leq
0,$ (27c) $\displaystyle d_{c_{i}r_{i}}^{2}-t\leq 0$ (27d)
$\displaystyle\mathbf{l}_{r_{i}}=\sum_{j\in N_{c_{i}}^{u}\cup
c_{i}}{\theta_{j}\mathbf{l}_{j}},$ (27e)
$\displaystyle\mathbf{\Theta}\succcurlyeq\mathbf{0},$ (27f)
$\displaystyle\mathbf{1}^{T}\mathbf{\Theta}=1,$ (27g)
$\displaystyle\mathbf{p}_{r_{i}}\succcurlyeq\mathbf{0},$ (27h)
$\displaystyle\mathbf{d}_{r_{i}}\succcurlyeq\mathbf{0}.$ (27i)

Our proposed RNP belongs to non-differentiable convex optimization problems.
The advantage of convex problems over non-convex counterparts is that, in
general, a global optimum can be computed with good precision and within a
reasonable time, independent of initialization [30]. To obtain the optimal
position of the relay node we resort to off-the-shelf convex solver CVX which
is a Matlab-based modeling system for convex optimization. CVX can solve much
more complex convex optimization problems, including non-differentiable
functions. It was developed using interior point methods and gives numerical
solutions for the convex optimization problem. By solving it, a set of optimal
solutions $(\mathbf{l}_{r_{1}},...,\mathbf{l}_{r_{M_{0}}})$ and
$\mathbf{p}_{r}^{*}=[\mathbf{1}^{T}\mathbf{p}_{r_{1}},...,\mathbf{1}^{T}\mathbf{p}_{r_{M_{0}}}]^{T}$
showing the vector position of relay nodes and overall transmitting energy
consumption of them is obtained, respectively. This optimal solution shows the
optimal value $\tau^{*}$. The pseudo-code of the proposed network lifetime is
given in algorithm 1.

Data: The set of sensor nodes ($\mathcal{S}$)

Result: Position of relay nodes, rate array

1: for each relay node $r_{i}$ do

2: for each node $n\in\mathcal{S}\cup R$ do

3: Compute $\tau_{n}$ using (7)

4: end for

5: $c_{i}=\arg\min\tau_{n}$

6: Construct the set $N_{c_{i}}^{u}$ using (12)

7: Define the convex hull system as given in (19)

8: Define the multi-objective problem (20)

9: Apply the $\epsilon$-constraint approach to convert the multi-objective
problem (20) into the single-objective problem (21)

10: Apply the transformation (35) and Lemma 1 to form problem (26)

11: Define the convex-based RNP (27) by using the epigraph form of (26)

12: Solve problem (27) using CVX tool to obtain ${\mathbf{l}}_{r_{i}}$

13: Update $\mathbf{R}$ based on Eqs. (13)-(15)

14: end for

15: return $\mathbf{R},{\mathbf{l}}_{r_{i}},i=1,\ldots,\rm M$

Algorithm 1 Summary of proposed ORNS approach TABLE II: Computations of
proposed ORNS method

Operation |  Computations of formulating (27) |  Computations of solving (27) |  Total computations
---|---|---|---
Linear search |  $3$ |  $\rm{iter_{1}}$ |  $3({\rm N}+{\rm M}-1)+\rm iter_{1}({\rm N}+{\rm M}-1)$
Assignment |  $3$ |  — |  $3$
Addition |  $({\rm N}+{\rm M}-1)({\rm N}+{\rm M})$ |  $({\rm N}+{\rm M}+13)\ \rm{iter_{1}}$ |  $({\rm N}+{\rm M})({\rm N}+{\rm M}-1)+({\rm N}+{\rm M}+13)\ \rm{iter_{1}}$
Division |  ${\rm N}+{\rm M}-1$ |  $\rm{iter}_{1}$ |  $({\rm N}+{\rm M}-1)\ \rm{iter_{1}}$
Multiplication |  $({\rm N}+{\rm M}-1)^{2}$ |  $({\rm N}+{\rm M}+12)\ \rm{iter_{1}}$ |  $({\rm N}+{\rm M}-1)^{2}+({\rm N}+{\rm M}+12)\ \rm{iter_{1}}$

TABLE III: Computations of previous RNP schemes

Operation |  Computations of DCA[19] | Computations of RA [17]
---|---|---
Computations of initializing the position of relay nodes on the surface of the water |  Computations of adjusting the depth |  Total computations
Linear search |  $2({\rm N+M}-1)$ |  — |  ${\rm N+2M-2}$ |  ${\rm N+2M-2}$
Assignment |  $4$ |  $2{\rm M}+4\alpha$ |  $\beta$ |  $2{\rm M}+4\alpha+\beta$
Addition |  $({\rm N+M})({\rm N+M}-1)+({\rm N+M}+17)\ {{\rm iter_{2}}}$ |  ${\rm N}({\rm 2N-4}+\alpha)+\alpha+\alpha^{2}$ |  $2{\rm(N+M)(M+N-2)}+5\beta+{\rm 13\ iter_{3}}$ |  $2{\rm(N+M)(M+N-2)}+{\rm N}({\rm 2N-4}+\alpha)+\alpha+\alpha^{2}+5\beta+{\rm 13\ iter_{3}}$
Division |  $({\rm N+M}-1)+5\ {\rm iter_{2}}$ |  ${\rm N+}3\alpha$ |  $\rm N+M$ |  ${\rm 2N+M}+3\alpha$
Multiplication |  $({\rm N+M})({\rm N+M}-1)+({\rm N+M}+23)\ {\rm iter_{2}}$ |  ${\rm N}^{2}+4\alpha$ |  $({\rm N+M})^{2}+4\beta+14\ \rm iter_{3}$ |  $({\rm N+M})^{2}+{\rm N}^{2}+4\alpha+4\beta+14\ \rm iter_{3}$

###  IV-B Step 2 - Relay nodes minimization: RNMI scheme

By definition, $\rm M$ is an indication of the selected relay nodes which are
in an acceptable network lifetime extension and we have $\rm M\leq M_{0}$.
Moreover, let $\mathbf{p}_{c}$ includes the total transmitting energy
consumption of nodes $c_{i},i=1,\ldots,\rm M_{0}$ before placing relays.
Considering the effectiveness of relay nodes in the extension of network
lifetime, a relay should be introduced if necessary in terms of the network
lifetime. Toward this, we cast to the zero-norm and one-norm principles to
define the relay node selection problem as:

$\displaystyle\gamma=\arg\\{\min\left\lVert\mathbf{p}_{r}\right\rVert_{0},\max\left\lVert{\mathbf{p}_{r}-\mathbf{p}_{c}}\right\rVert_{1}\\},$
(28a) $\displaystyle s.t.$
$\displaystyle\min\tau_{i}=\tau^{*},i\in\mathcal{N},$ (28b)
$\displaystyle{[\mathbf{p}_{r}]_{i}}\in\\{\mathbf{0},{[\mathbf{p}_{r}^{*}]_{i}}\\},$
(28c)
$\displaystyle[\mathbf{p}_{c}]_{i}=\begin{cases}p_{c_{i}r_{i}}\times\sum_{j\in
N_{c_{i}}^{u}}[\mathbf{R}]_{{c_{i}}j}&[\mathbf{p}_{r}]_{i}=[\mathbf{p}_{r}^{*}]_{i}\\\
\sum_{j\in
N_{c_{i}}^{u}}{p_{c_{i}j}}[\mathbf{R}]_{{c_{i}}j}&[\mathbf{p}_{r}]_{i}=0\end{cases},i=1,\ldots,\rm
M_{0}.$ (28d)

where zero-norm as the cardinality function returns the non-zero entry in the
$\mathbf{p}_{r}$. In addition, $\tau^{*}$ is the answer from the first
optimization step added as the constraint. By employing the scalarization
method to mix the zero-norm and one-norm functions, the problem can be given
as:

$\displaystyle\gamma=\arg\\{\min\omega_{1}\left\lVert\mathbf{p}_{r}\right\rVert_{0}-\omega_{2}\left\lVert{\mathbf{p}_{r}-\mathbf{p}_{c}}\right\rVert_{1}\\},$
(29a) $\displaystyle s.t.$
$\displaystyle\min\tau_{i}=\tau^{*},i\in\mathcal{N},$ (29b)
$\displaystyle{[\mathbf{p}_{r}]_{i}}\in\\{\mathbf{0},{[\mathbf{p}_{r}^{*}]_{i}}\\},$
(29c)
$\displaystyle[\mathbf{p}_{c}]_{i}=\begin{cases}p_{c_{i}r_{i}}\times\sum_{j\in
N_{c_{i}}^{u}}[\mathbf{R}]_{{c_{i}}j}&[\mathbf{p}_{r}]_{i}=[\mathbf{p}_{r}^{*}]_{i}\\\
\sum_{j\in
N_{c_{i}}^{u}}{p_{c_{i}j}}[\mathbf{R}]_{{c_{i}}j}&[\mathbf{p}_{r}]_{i}=0\end{cases},i=1,\ldots,\rm
M_{0}.$ (29d)

where the weights for each function $\omega_{1}$ and $\omega_{2}$ can be
chosen according to the kind of tradeoffs we are willing to make and
$\omega_{1}+\omega_{2}=1$. Recall step function $s(x)$ with
$s(x):\mathbb{R}\rightarrow\mathbb{R}^{+}$ that $s(x)=1$ for $x>0$ and
$s(x)=0$ for $x\leq 0$, the zero-norm can be written as the sum of
discontinuous step function as:

$\left\lVert\mathbf{p}_{r}\right\rVert_{0}=\sum_{i=1}^{\rm
M_{0}}s([\mathbf{p}_{r}]_{i})$ (30)

Here, by applying the nonnegative feature of $[\mathbf{p}_{r}]_{i}$, we use
the following continuously differentiable concave approximation of the step
function for nonnegative variable [31]:

$s([\mathbf{p}_{r}]_{i})=1-\exp(-\eta[\mathbf{p}_{r}]_{i})$ (31)

that $\eta>0$. Therefore the problem (29) is equivalently presented as:

$\displaystyle\gamma=\arg\min\\{\omega_{1}\sum_{i=1}^{M_{0}}\left({1-\exp(-\eta[\mathbf{p}_{r}]_{i})}\right)-\omega_{2}\left\lVert\mathbf{p}_{r}-\mathbf{p}_{c}\right\rVert_{1}\\},$
(32a) $\displaystyle s.t.$
$\displaystyle\tau_{i}\geq\tau^{*},i\in\mathcal{N},$ (32b)
$\displaystyle{[\mathbf{p}_{r}]_{i}}\in\\{\mathbf{0},{[\mathbf{p}_{r}^{*}]_{i}}\\},$
(32c)
$\displaystyle[\mathbf{p}_{c}]_{i}=\begin{cases}p_{c_{i}r_{i}}\times\sum_{j\in
N_{c_{i}}^{u}}[\mathbf{R}]_{{c_{i}}j}&[\mathbf{p}_{r}]_{i}=[\mathbf{p}_{r}^{*}]_{i}\\\
\sum_{j\in
N_{c_{i}}^{u}}{p_{c_{i}j}}[\mathbf{R}]_{{c_{i}}j}&[\mathbf{p}_{r}]_{i}=0\end{cases},i=1,\ldots,\rm
M_{0}.$ (32d)

The obtained model is a mixed-integer convex programming model. Models with
integer and binary variables must still obey all of the same disciplined
convex programming rules that CVX enforces for continuous models. The above
approximation model is a smooth optimization problem with tolerable complexity
and show that each relay node should not be deployed if the transmit power
consumption by the cooperation of the relay node is more than the direct
transmit power consumption and should be otherwise. Let us now evaluate our
approach against the RA [17] and DCA [19] schemes in terms of complexity and
network lifetime

##  V Complexity analysis

In this section, we compute the time complexity of our proposed RNP, DCA and
RA methods. We do this by calculating the number of computations as shown in
Tables II and III. One can notice that ${\rm iter}_{i},i\in\\{1,2,3\\}$
represents the number of iterations required for each RNP scheme to converge,
which is significantly lower than $({\rm N}+{\rm M})$ in practical scenarios.
Additionally, $\alpha$ and $\beta$ are small constant values. Consequently,
Table II demonstrates that the worst-case time complexity of our proposed
method is limited to ${\mathcal{O}}({\rm N}+{\rm M})^{2}$. Furthermore, based
on table III, it can be concluded that the time complexity of DCA and RA is
also bounded by ${\mathcal{O}}({\rm N+M})^{2}$. Subsequently, we will assess
the performance of the proposed ORNS method through simulations.

TABLE IV: List of parameters

Notation | Definition | Value
---|---|---
$H_{s}$ | Depth of the water | 2000 m
$C_{R}$ | Communication range | 500 m
$f$ | Frequency of acoustic signal | 1 kHz
$p_{s}$ | The power consumption for processing in sending data | 1 mw/bit
$p_{r}$ | The power consumption for processing in receiving data | 1 mw/bit
$d_{t}$ | Distance threshold | 87 m
$L_{c}$ | Link capacity | 10 kb/sec
$\epsilon_{p}$ | Primary energy of typical node $i$ |  $4\times 10^{5}$ J
${g}_{i}$ | Generation rate of sensor node $i$ |  $10\thicksim 200$ bit/sec

##  VI Algorithm evaluation results

In this section, we evaluate and compare the proposed RNP with the heuristic
RA method [17] and DCA approach [19] using multiple simulation scenarios. The
experiments are performed by MatLab 2017b. The simulation parameters and their
notations are provided in Table IV. The depth of water was taken as $2000\ \rm
m$, the generation rate of each sensor node is set randomly between $10$ and
$200\ \rm bit/Sec$, and the primary energy of nodes was set to $4\times
10^{5}\rm J$ [32]. The frequency of the acoustic signal was set to $1\rm kHz$.
Similar to [17], [19], we design the deployment of 3-D underwater sensor
networks in the cylindrical sensing field where they sense the environment.
The gathered data is then transmitted to the SB, which is positioned at the
origin. Additionally, Table V outlines the different RNP cases, using
$\gamma_{r}=\frac{|\mathcal{R}|}{|\mathcal{S}|}$ to denote the percentage of
employed relays and $\rm{RF}=\frac{\epsilon_{c_{1}}}{\epsilon_{p}},$ as the
residual energy factor of the most critical node in the sensor network.

The Imbalanced Factor of Energy Consumption (IEC) was calculated as

$\mathrm{IEC}=\frac{\frac{1}{\rm
N}\sum_{i\in\mathcal{S}}{\left(\mathrm{E}\left(\epsilon_{i}\right)-\mathrm{E}\left(\bar{\epsilon}\right)\right)^{2}}}{\sigma_{0}^{2}}$
(33)

where $\bar{\epsilon}=\frac{1}{{\rm N}}\sum_{i\in\mathcal{S}}{\epsilon_{i}},$
and $\sigma_{0}^{2}$ is the normalization factor. In the following we present
a three-fold approach to evaluate the effectiveness of our relay node
placement method. Firstly, we investigate regulation of the positions of relay
nodes within the network at different scales. Secondly, we conduct a
comprehensive performance evaluation of our proposed method by comparing it
with existing approaches. Thirdly, we delve into the details of our relay node
selection design, which aims to minimize resource wastage in UASNs.

TABLE V: Considered RNP characteristics

Case |  A |  B |  C |  D
---|---|---|---|---
$\rm{RF}$ |  0.25 |  0.75 |  0.25 |  0.25
$\gamma_{r}$ |  0.3 |  0.3 |  0.6 |  0.9
|  |  |  |

(a) RA method (first deployment)

(b) DCA approach (first deployment)

(c) Proposed approach (first deployment)

(d) RA method (second deployment)

(e) DCA approach (second deployment)

(f) Proposed approach (second deployment)

Figure 4: Position of relay nodes in the network when $|\mathcal{S}|=20$,
$\gamma_{r}=0.3$, and $\rm{RF}=0.25$ in different deployments

(a) RA method (first deployment)

(b) DCA approach (first deployment)

(c) Proposed approach (first deployment)

(d) RA method (second deployment)

(e) DCA approach (second deployment)

(f) Proposed approach (second deployment)

Figure 5: Position of relay nodes in the network when $|\mathcal{S}|=40$,
$\gamma_{r}=0.3$, and $\rm{RF}=0.25$ in different deployments

(a) RA method

(b) DCA approach

(c) Proposed approach

Figure 6: Residual energy of sensor nodes when $|\mathcal{S}|=40$,
$\gamma_{r}=0.3$, and $\rm{RF}=0.25$ Figure 7: Imbalanced factor of energy
consumption for different $\mathrm{RF}$s

(a) $\gamma_{r}=0.3,\mathrm{RF}=0.25$

(b) $\gamma_{r}=0.3,\mathrm{RF}=0.75$

Figure 8: Investigation of the performance in different network scales

###  VI-A Regulation of relay nodes

In this section, we examine the regulation of relay nodes in the network. To
do so, we consider Case A with $\rm RF=0.25$ and $\gamma_{r}=0.3$. We consider
two network scales in this example, each with a different number of sensor
nodes. For each scale, we present the results for two network deployments, as
shown in Figs. 4 and 5. In Fig. 4, we assume that there are 20 sensor nodes,
while in Fig. 5, we assume that there are 40 sensor nodes.
We observe that in a multi-hop UASN, a higher percentage of relay nodes are
positioned near the SB due to the larger amount of data collected by nodes in
that area. Comparing Fig. 4 with Fig. 5, as the number of sensor nodes
increases, the percentage of relay nodes near the SB also increases. This
observation can be attributed to the fact that an increase in the number of
sensors leads to a larger amount of information being gathered by nodes near
the SB. In the previous RA method, most relay nodes are not adjusted in depth
because of their random location on the water’s surface. Furthermore, previous
line-segment relay node placement (LSRNP) approaches, such as RA and DCA,
resulted in relay nodes being positioned too closely together or even directly
on top of sensor nodes, as seen in Fig. 5(a) and Fig. 5(d). In contrast, our
proposed approach suggests a more sensible placement for relay nodes by
considering a feasible search for the convex hull.

###  VI-B Performance evaluation

Figure 9: Effect of increasing the number of relay nodes on the performance

In this part, we evaluate the performance of proposed RNP method and compare
with RA and DCA approaches in terms of balanced energy consumption and network
lifetime. To do so, we design some simulation cases and obtain all the
numerical results from 50 deployments. The first case assumes 40 sensor nodes,
$\gamma_{r}=0.3$, and $\mathrm{RF}=0.25$, as shown in Case A in Table V. Figs.
6(a), 6(b) and 6(c) show the distribution of residual energy among sensor
nodes when applying the RA, DCA, and ORNS methods, respectively, along with a
scenario without relay nodes for comparison. It is observed that imbalanced
energy consumption creates an energy hole in the network that limits the
performance of UASNs. This, in turn, prevents the collected data from being
forwarded to the SB. Employing relay nodes improves the energy hole issue in
the network. Furthermore, the proposed ORNS method highlights the advantages
of obtaining a more balanced energy distribution among nodes through optimal
positioning of the relay nodes in addressing the energy hole issue. To
illustrate further, Fig. 7 depicts the IEC factor for different RF values. It
can be seen that the proposed method outperforms previous schemes in terms of
energy balance, as evidenced by the smaller IEC values.

We present the network lifetime as a function of the number of sensor nodes in
the second case, with the parameters set according to cases A and B in Table
V. The results for these cases are shown in Fig. 8(a) and 8(b), respectively.
Several important observations can be made based on these results. Firstly, it
can be seen that the network lifetime decreases as the number of sensor nodes
increases. This is due to the increased amount of data that needs to be
relayed, leading to higher energy consumption. Secondly, the proposed RNP
method outperforms RA and DCA by utilizing convex programming to determine the
optimal location of the relay nodes. Lastly, without relay nodes, the
transmission distance between the sensor nodes becomes long, resulting in a
shorter network lifetime.

###  VI-C Relay node selection design

So far, we have assumed a fixed number of relay nodes in our scenario.
However, in this section, we want to highlight the importance of selecting
relay nodes in our proposed approach. To address this concern, we conducted a
thorough analysis by comparing the network lifetime with varying numbers of
sensor nodes and relay nodes. The results, shown in Fig.9 for cases C and D
(where $\gamma_{r}=0.6$ and $\gamma_{r}=0.9$), clearly demonstrate that when
the network has a high number of nodes, especially when the communication
distance between sensor nodes is small, the need for additional relay nodes
decreases. This is because the close proximity of sensor nodes allows for
direct communication without relying intermediate relay nodes. In such cases,
the presence or absence of extra relay nodes does not significantly affect the
network lifetime.

To gain further insight, consider Fig. 10 where we assume there are 80 sensor
nodes and plot the positions of relay nodes in the network. It can be observed
that the relay nodes are placed very closely together (DCA) or have specific
positions beyond a certain number (proposed approach). In this situation, our
relay node selection design, which strategically places five relay nodes,
proves effective in achieving optimal network performance while minimizing the
overall number of required relay nodes. On the other hand, when relay node
selection is not considered, there are no criteria to limit the placement of
relay nodes. In conclusion, by carefully selecting these relay nodes based on
our proposed criteria, we were able to achieve significant improvements in
both maximizing network lifetime and minimizing the number of required relay
nodes.

Figure 10: Distribution of relay nodes when $|\mathcal{S}|=80$ and
$\mathrm{RF}=0.25$

##  VII Conclusion

This paper aimed to address the joint optimization of maximizing network
lifetime and minimizing relay node deployment in relay-assisted UASNs. To
achieve a Pareto optimal solution, a multi-objective lexicographic method was
employed in which the primary goal was to optimize the network lifetime in the
RNP followed by the reduction of the active relay nodes. To accomplish this, a
two-step process was employed. First, the ORNS algorithm was utilized to
formulate the position of each relay node as a non-convex programming problem.
This was then converted into an equivalent convex programming problem using a
novel transformation and epigraph form scheme. Subsequently, a relay selection
procedure utilizing a mixed-integer convex programming model was applied to
minimize the number of active relay nodes. The proposed approach proved to be
more efficient in terms of network lifetime than the existing models (RA and
DCA).

##  Appendix A Equivalent convex form of the (21)

Here, we present a transformation of a non-convex optimization problem with a
convex objective function and convex (and/or linear) and DC constraints into
an equivalent convex optimization problem. The non-convex problem can be
expressed as

$\displaystyle\mathbf{x}={\rm arg\min}f_{0}(\mathbf{x})$ (34a) s.t.
$\displaystyle f_{i}(\mathbf{x})\leq 0,\quad\quad i=1,2,\ldots,I,$ (34b)
$\displaystyle h_{p}(\mathbf{x})=0,\quad\quad p=1,2,\ldots,P,$ (34c)

where $\mathbf{x}\in\mathbb{R}^{n}$ ,
$f_{0},...,f_{I}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ are convex functions and
$h_{1},\ldots,h_{M}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ are DC functions. We
take advantage of the property of DC constraints which can be expressed as the
difference of convex functions, and introduce a new variable
$\mathbb{t}=[t_{1},t_{2},\ldots,t_{M}]^{T}\in\mathbb{R}^{M}$. This yields a
convex optimization problem,

$\displaystyle(\mathbf{x},\mathbb{t})=\rm arg\min f_{0}(\mathbf{x})$ (35a)
s.t. $\displaystyle f_{i}(\mathbf{x})\leq 0,\quad\quad i=1,2,\ldots,I,$ (35b)
$\displaystyle\psi_{m}(\mathbf{x})-t_{m}=0,\quad\quad m=1,2,\ldots,M,$ (35c)
$\displaystyle\phi_{m}(\mathbf{x})-t_{m}=0,\quad\quad m=1,2,\ldots,M.$ (35d)

Since (35c) and (35d) are both convex, this problem is the desired convex
programming equivalent of the non-convex one.

## References

  * [1] S. Fattah _et al._ , “A survey on underwater wireless sensor networks: Requirements, taxonomy, recent advances, and open research challenges,” _Sensors_ , vol. 20, no. 18, p. 5393, 2020.
  * [2] A. Wadaa _et al._ , “Training a wireless sensor network,” _Mobile Networks and Applications_ , vol. 10, no. 1-2, pp. 151–168, 2005.
  * [3] K. Wang _et al._ , “An energy-efficient reliable data transmission scheme for complex environmental monitoring in underwater acoustic sensor networks,” _IEEE Sensors Journal_ , vol. 16, no. 11, pp. 4051–4062, 2015.
  * [4] X. Zhuo _et al._ , “Auv-aided energy-efficient data collection in underwater acoustic sensor networks,” _IEEE Internet of Things Journal_ , 2020.
  * [5] J. Yan _et al._ , “Energy-efficient data collection over auv-assisted underwater acoustic sensor network,” _IEEE Systems Journal_ , vol. 12, no. 4, pp. 3519–3530, 2018.
  * [6] N. Javaid _et al._ , “An efficient data-gathering routing protocol for underwater wireless sensor networks,” _Sensors_ , vol. 15, no. 11, pp. 29 149–29 181, 2015.
  * [7] H. U. Yildiz, V. C. Gungor, and B. Tavli, “Packet size optimization for lifetime maximization in underwater acoustic sensor networks,” _IEEE Transactions on Industrial Informatics_ , vol. 15, no. 2, pp. 719–729, 2018.
  * [8] P. Anjangi and M. Chitre, “Scheduling algorithm with transmission power control for random underwater acoustic networks,” in _OCEANS 2015-Genova_. IEEE, 2015, pp. 1–8.
  * [9] A. Roy and N. Sarma, “Rpcp-mac: Receiver preambling with channel polling mac protocol for underwater wireless sensor networks,” _International Journal of Communication Systems_ , vol. 33, no. 9, p. e4383, 2020.
  * [10] H. Wang _et al._ , “An effective scheduling algorithm for coverage control in underwater acoustic sensor network,” _Sensors_ , vol. 18, no. 8, p. 2512, 2018.
  * [11] H. E. Erdem, H. U. Yildiz, and V. C. Gungor, “On the lifetime of compressive sensing based energy harvesting in underwater sensor networks,” _IEEE Sensors Journal_ , vol. 19, no. 12, pp. 4680–4687, 2019.
  * [12] L. Jing _et al._ , “Energy management and power allocation for underwater acoustic sensor network,” _IEEE Sensors Journal_ , vol. 17, no. 19, pp. 6451–6462, 2017.
  * [13] T. Ahmed _et al._ , “Optimized depth-based routing protocol for underwater wireless sensor networks,” in _Open Source Systems & Technologies (ICOSST), 2016 International Conference on_. IEEE, 2016, pp. 147–150.
  * [14] Z. Wadud _et al._ , “An energy balanced efficient and reliable routing protocol for underwater wireless sensor networks,” _IEEE Access_ , vol. 7, pp. 175 980–175 999, 2019.
  * [15] E. Felemban _et al._ , “Underwater sensor network applications: A comprehensive survey,” _International Journal of Distributed Sensor Networks_ , vol. 11, no. 11, p. 896832, 2015.
  * [16] B. Das, E. S. Mishra, and S. K. Sethi, “Enhancement of lifetime of acoustic sensor using pegasis algorithm in uasn,” _International Journal of Electronics, Electrical and Computational System (Mc Graw Hill Publication)_ , vol. 6, no. 9, pp. 534–545, 2017.
  * [17] L. Liu _et al._ , “Optimal relay node placement and flow allocation in underwater acoustic sensor networks,” _IEEE Transactions on Communications_ , vol. 65, no. 5, pp. 2141–2152, 2017.
  * [18] Z. Mohammadi _et al._ , “A new optimization algorithm for relay node setting in underwater acoustic sensor networks,” in _2018 3rd Conference on Swarm Intelligence and Evolutionary Computation (CSIEC)_. IEEE, 2018, pp. 1–5.
  * [19] ——, “Increasing the lifetime of underwater acoustic sensor networks: Difference convex approach,” _IEEE Systems Journal_ , 2020.
  * [20] Z. Mohammadi, “Modified relay node placement in dense 3d underwater acoustic sensor networks,” in _2022 9th Iranian Joint Congress on Fuzzy and Intelligent Systems (CFIS)_. IEEE, 2022, pp. 1–4.
  * [21] I. F. Akyildiz, D. Pompili, and T. Melodia, “Underwater acoustic sensor networks: research challenges,” _Ad hoc networks_ , vol. 3, no. 3, pp. 257–279, 2005.
  * [22] R. J. Urick, “Principles of underwater sound-2,” 1975.
  * [23] K. Wang _et al._ , “An energy-efficient reliable data transmission scheme for complex environmental monitoring in underwater acoustic sensor networks,” _IEEE Sensors Journal_ , vol. 16, no. 11, pp. 4051–4062, 2016.
  * [24] W. H. Thorp, “Analytic description of the low-frequency attenuation coefficient,” _The Journal of the Acoustical Society of America_ , vol. 42, no. 1, pp. 270–270, 1967.
  * [25] J. Cao, J. Dou, and S. Dong, “Balance transmission mechanism in underwater acoustic sensor networks,” _International Journal of Distributed Sensor Networks_ , vol. 11, no. 3, p. 429340, 2015.
  * [26] M. Akbar _et al._ , “Efficient data gathering in 3d linear underwater wireless sensor networks using sink mobility,” _Sensors_ , vol. 16, no. 3, p. 404, 2016.
  * [27] S. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [28] H. Tuy _et al._ , _Convex analysis and global optimization_. Springer, 1998.
  * [29] R. A. Silverman, _Essential calculus with applications_. Courier Corporation, 1989, vol. 75.
  * [30] M. Soleimanpour-moghadam _et al._ , “Low complexity green cooperative cognitive radio network with superior performance,” _IEEE Systems Journal_ , no. 99, pp. 1–12, 2018.
  * [31] F. Rinaldi, F. Schoen, and M. Sciandrone, “Concave programming for minimizing the zero-norm over polyhedral sets,” _Computational Optimization and Applications_ , vol. 46, no. 3, pp. 467–486, 2010.
  * [32] W. Alsalih, H. Hassanein, and S. Akl, “Placement of multiple mobile data collectors in wireless sensor networks,” _Ad Hoc Networks_ , vol. 8, no. 4, pp. 378–390, 2010.