Joint Slot Scheduling and Power Allocation in Clustered Underwater Acoustic Sensor Networks

Dear Editor,

This letter deals with the joint slot scheduling and power allocation in clustered underwater acoustic sensor networks (UASNs), based on the known clustering and routing information, to maximize the network’s energy efficiency (EE). Based on the block coordinated decent (BCD) method, the formulated mixed-integer non-convex problem is alternatively optimized by leveraging the Kuhn-Munkres algorithm, the Dinkelbach’s method and the successive convex approximation (SCA) technique. Numerical results show that the proposed scheme has a better performance in maximizing EE compared to the separate optimization methods.

Recently, the interest in the research and development of underwater medium access control (MAC) protocol is growing due to its potentially large impact on the network throughput. However, the focus of many previous works is at the MAC layer only, which may lead to inefficiency in utilizing the network resources [1]. To obtain a better network performance, the approach of cross-layer design has been considered. In [1], Shi and Fapojuwo proposed a cross-layer optimization scheme to the scheduling problem in clustered UASNs. However, power allocation and slot scheduling were separately designed in [1], which cannot guarantee a global optimum solution. In [2], a power control strategy was introduced to achieve the minimum-frame-length slot scheduling. However, EE, as a non-negligible aspect of network performance, is not being considered in [2].

In this letter, we formulate a joint slot scheduling and power allocation optimization problem to maximize the network’s EE in clustered UASNs. The formulated problem with coupled variables is non-convex and mixed-integer, which is challenging to be solved. We propose an efficient iterative algorithm to solve it. Numerical results demonstrate the effectiveness of our proposed algorithm.

Problem statement: A clustered UASN with N sensor nodes grouped into K clusters is considered in this article, with the sets ${\cal{N}} \triangleq \{1,2,\ldots,N\}$ and ${\cal{K}}\triangleq \{1,2,\ldots,K\}$. Sensor nodes’ operation time in a frame consists of M equal and length-fixed time slots with the index set ${\cal{M}} \triangleq \{ 1,2,\ldots,M\}$. The sensor nodes send carriers at the same frequency. The half-duplex (HD) mode and the decode-and-forward (DF) mode are adopted for data relaying. The data packet length is assumed equal to the length of the time slot. Since packet collisions occur at the receiver but not the sender, we optimize the slot scheduling from the perspective of signal arrival time. As shown in Fig. 1, packets are scheduled to reach the destination at specific time slots. To avoid collisions, the arriving packets cannot overlap with each other as shown in the example of the packets at the sink from CH1, CH2 and CH3 in Fig. 1.

Figure  1.  Receiver-synchronized slot scheduling table.

DownLoad: Full-Size Img PowerPoint

We use the sparse vector ${\bf{z}}_{n} = (M,[t,1]) \in \mathbb{R}^{M \times 1}$ (which means the t-th element is 1 and the rest $M-1$ elements are 0) to represent the scheduling indicator, i.e., the t-th time slot is assigned to node n to deliver data. Then the slot scheduling of the overall network can be expressed by the set ${\cal{Z}} \triangleq \{{\bf{z}}_{1},{\bf{z}}_{2},\ldots,{\bf{z}}_{N}\}$. The allocated transmission power of node n is denoted as $p_{n}$, with the corresponding set of the overall network ${\cal{P}} \triangleq \{p_{1},p_{2},\ldots,p_{N}\}$. By Shannon’s law, the achievable link rate of node n to its receiver can be given by R_n = $B\log_2 \left(1 + \gamma_{n}\right)$, where B is the bandwidth, and $\gamma_{n}$ is the signal-to-interference-and-noise ratio (SINR) at the receiver of node n, which can be written as

where $g_{\overline{n}n}$ is the link’s channel gain from node $\overline{n}$ to the receiver of node n, $N_{0}(f)$ is the power spectral density (p.s.d.) of the ambient noises at the receiver (refer to [3]), and binary variable

is the interference indicator used to characterize the interference relationships between node n and node $\overline{n}$, where $\overline{n} \neq n \in {\cal{N}}$.

We regard the links connecting to the sink (i.e., sea surface buoy node) directly as the bottleneck links, then the EE maximization problem can be formulated as

where ${\cal{L}} \triangleq \{1,2,\ldots,L\}$ is the set of the links connecting to the sink directly, $\dot{{\cal{K}}}$ is the remaining part of ${\cal{K}}$ after removing the cluster containing the sink, ${\cal{Q}}_{k}\triangleq \{1,2,\ldots,Q_{k}\}$ is the set of cluster members (CMs) in k-th cluster, ${\cal{C}}\left({\bf{z}}_{k}\right)$ represents the set of time slots occupied by the cluster head (CH) $k \in \dot{{\cal{K}}}$ to transmit data, $\gamma_{th}$ is the required SINR threshold for each link, $N R_{th}$ is the required threshold of network rate for the entire network, and $T_{p}$ is a constant integer. $C1$ is the transmission power constraint. $C2$ is the SINR constraint to ensure that the signals can be correctly demoduled as shown in the example of CH3 in Fig. 1. $C3$ indicates that the output link rate of CH k is restrained by the rate of its subnetwork, which ensures that the links connecting to the sink directly are the bottleneck links. $C4$ is the integer constraint of M ranging from $M_{{\rm{min}}}$ to $M_{{\rm{max}}}$. $C5$ is the required minimum network rate constraint. $C6$ denotes ${\textit{z}}^{k}_{i,j}$ is a binary variable, which is set as 1 when the j-th time slot is occupied by the i-th CM of the k-th cluster. $C7$ denotes that each time slot accommodates at most one node in a cluster, which is given to avoid packet collisions. $C8$ denotes that each node is assigned one and only one time slot to deliver data in a frame. $C9$ denotes that the HD mode is adopted, thus CHs could not transmit and receive data simultaneously as shown in the example of CH1 in Fig. 1. $C10$ is the constraint for CHs to ensure that frames will not affect each other.

Problem solution: The optimization problem (3) is a non-convex and mixed-integer optimization problem, which cannot be solved directly due to the challenge that the variables M, ${\cal{P}}$ and ${\cal{Z}}$ are always coupled with each other in $C2$, $C3$, $C5$ and the objective function. To tackle the coupled variables, firstly, the exhaustive search method is adopted to solve the variable M, then a BCD-based alternating optimization method is utilized to decouple ${\cal{P}}$ and ${\cal{Z}}$.

Given the ${\cal{P}}$, ${\cal{Z}}$ and M, sensors’ optimal slot scheduling solution ${\cal{Z}}^{\ast}$ can be optimized by solving the following problem:

where $N R$ is the network rate of clustered UASNs. Considering that each node is assigned one and only one slot to deliver data and each slot accommodates at most one node in a cluster, the slot scheduling problem in a cluster can be modeled as a weighted matching problem for a bipartite graph, in which the CMs in the k-th cluster and the M time slots can be partitioned into two independent and disjoint sets ${\cal{Q}}_{k}$ and ${\cal{M}}$ such that every edge connects a node in ${\cal{Q}}_{k}$ to a time slot in ${\cal{M}}$. The weight of the edge is defined as the network rate. Then problem (4) can be solved by the Kuhn-Munkres algorithm proposed in [4]. The process, that optimizing the slot scheduling of a cluster while keeping the other clusters unchangeable, continues until all the clusters are optimized. After a round of optimization, if the network rate is improved, another optimization round will be performed until the network rate no longer increases.

Although any two nodes in the same cluster have no mutual interference, it still should be noted that a node in other clusters may be interfered by multi nodes in the optimization cluster. That means the optimal matching obtained by the Kuhn-Munkres algorithm may unsatisfy $C2$. For solving this problem, Criterion 1 is proposed to search for the eligible slot scheduling scheme.

Criterion 1: Supposing node A is the node unsatisfying the SINR constraint, firstly, we find its interference nodes (called set ${\cal{B}}$) who belong to the optimization cluster. Then, we sort set ${\cal{B}}$ in descending order in terms of the interference intensity to node A to find the node having the largest interference to node A (called node C). If node C has more than one available time slot, the previous assigned slot is forbidden to be assigned to node C. Otherwise, other nodes’ time slot will be checked and forbidden in same fashion unless there are no more time slot that can be forbidden in ${\cal{B}}$.

Given the ${\cal{Z}}$ and ${\cal{P}}$, sensors’ optimal transmission power solution ${\cal{P}}^{\ast}$ can be optimized by solving the following problem:

Problem (5) is nonconvex due to its nonconvex numerator of objective function and the constraints $C3$ and $C5$ with respect to ${\cal{P}}$. To obtain a convex upper bound of the left-hand side (LHS) of $C3$, we note that $R_{k}$, $\forall k \in \dot{{\cal{K}}}$, can be rewritten as $R_{k} = B \log_{2} A_{k} -$ $B \log_2 H_{k}$, where $A_{k} = p_{k} g_{kk} + \sum_{\forall \overline{k} \neq k \in {\cal{N}}} \delta_{k}({\bf{z}}_{\overline{k}})p_{\overline{k}}g_{\overline{k}k} + N_{0}(f)B$, and $H_{k} = \sum_{\forall \overline{k} \neq k \in {\cal{N}}} \delta_{k}({\bf{z}}_{\overline{k}})p_{\overline{k}}g_{\overline{k}k} + N_{0}(f)B$. Making use of the deformation of arithmetic-geometric mean inequality, which states that $\sum_i v_{i} \geq \prod_i ({v_{i}}/{\theta_{i}})^{\theta_{i}}$ with $v_{i} \geq 0$, $\theta_{i} > 0$ and $\sum_i \theta_{i} = 1$ (the equality happens when $\theta_{i} = v_{i} / \sum_i v_{i}$), we can obtain

and the equality happens when

By taking logarithm on both sides of (6), we have

Letting $\hat{R}_{k} = B \log_{2} A_{k} - B\check{f}({\cal{P}})$, we have $R_{k} \leq \hat{R}_{k}, \,\, \forall k \in \dot{{\cal{K}}}$. And the equality happens when (7) holds. Letting $\tilde{p}_{n} = \ln p_{n}$, $\forall p_{n} \in {\cal{P}}$, it is easy to see that

is a convex function with respect to $\widetilde{{\cal{P}}}$ (log-sum-exponent is convex).

To obtain a concave lower bound of the right-hand side (RHS) of $C3$, the logarithmic approximation method used in [5] is adopted. Then we have

Letting $\tilde{p}_{n} = \ln p_{n}$, $\forall p_{n} \in {\cal{P}}$, it is easy to see that

is concave. Likewise, we can obtain the concave lower bound $\check{R}_{l}, \;\forall l \in {\cal{L}},$ of $R_{l}, \;\forall l \in {\cal{L}},$ in the objective function and $C5$. Substituting the undesired terms in (5) with the upper or lower bounds obtained above, and letting $\tilde{p}_{n} = \ln p_{n}$, $\forall p_{n} \in {\cal{P}}$, problem (5) can be reformulated as

where $\tilde{{\cal{P}}} \triangleq \{\tilde{p}_{1},\tilde{p}_{2},\ldots,\tilde{p}_{N}\}$. The objective function in (12) is a fractional function with a concave numerator and a convex denominator in terms of the transmission power $\tilde{{\cal{P}}}$, and the constraints are all convex. Therefore, we can exploit the Dinkelbach’s method [6] to transform it into the equivalent convex problem

The optimal solution of problem (5) can be obtained by solving the equivalent convex problem (13) iteratively, which can be tackled with existing optimization tools like CVX. The pseudocode of the optimization process in terms of sensors’ transmission power ${\cal{P}}$ is shown in Algorithm 1.

The pseudocode of the BCD-based alternating optimization algorithm is shown in Algorithm 2, in which two variable blocks are optimized alteratively corresponding to the two optimization subproblems (i.e., the slot scheduling subproblem and the power allocation subproblem) in each iteration of the alternating optimization process.

Simulation results: We consider a 10 km × 10 km × 200 m area, where N = 30 underwater sensor nodes deployed randomly at different sea depths are divided K clusters. We assume that the sensors are stationary, and the data in each sensor’s buffer is always sufficient. We take the carrier frequency $f = 10$ kHz, $B = 2$ kHz and $P_{{\rm{max}}} =$ 2 W.

For assessing the performance of the proposed alternating-optimization-based joint slot scheduling and power allocation algorithm (denoted as AO), we present three other schemes as contrasts, which include two kinds of separate optimization methods and the power allocation scheme ${\cal{P}}_{0}$ and the slot scheduling scheme ${\cal{Z}}_{0}$ obtained by the proposed CMS-MAC algorithm in [2]. The two separate optimization methods are summarized as follows:

Algorithm 1 Power Control Algorithm Based on the SCA Technique and the Dinkelbach’s Method

1: Set the maximum number of iterations $\tau$ and the maximum tolerance $\varepsilon$. Initialize iteration index $t \longleftarrow 0$ and $\tilde{{\cal{P}}}^{\{t\}} \longleftarrow \{\ln p_{1},\ln p_{2},...,\ln p_{N}\}$, where ${\cal{P}}$ is the input powers;

2: repeat

3:　 Initialize iteration index $h \longleftarrow 0$ and $\tilde{{\cal{P}}}_{{\rm{temp}}}^{\{h\}} \longleftarrow \tilde{{\cal{P}}}^{\{t\}}$;

4:　Compute $\eta^{\{t\}}_{E E}$ with given $\tilde{{\cal{P}}}^{\{t\}}$;

5:　repeat

6:　　Compute $\alpha_{l}=\dfrac{\gamma_{l}\left(\tilde{{\cal{P}}}_{{\rm{temp}}}^{\{h\}}\right)}{1+\gamma_{l}\left(\tilde{{\cal{P}}}_{{\rm{temp}}}^{\{h\}}\right)}$, $\beta_{l}=\ln \left(\dfrac{1 + \gamma_{l}\left(\tilde{{\cal{P}}}_{{\rm{temp}}}^{\{h\}}\right)}{\gamma^{\alpha_{l}}_{l}\left(\tilde{{\cal{P}}}_{{\rm{temp}}}^{\{h\}}\right)}\right)$, $\forall l \in {\cal{L}}$, $\alpha_{q}=$$\dfrac{\gamma_{q}\left(\tilde{{\cal{P}}}_{{\rm{temp}}}^{\{h\}}\right)}{1+\gamma_{q}\left(\tilde{{\cal{P}}}_{{\rm{temp}}}^{\{h\}}\right)}$, $\beta_{q}=\ln \left(\dfrac{1 + \gamma_{q}\left(\tilde{{\cal{P}}}_{{\rm{temp}}}^{\{h\}}\right)}{\gamma^{\alpha_{q}}_{q}\left(\tilde{{\cal{P}}}_{{\rm{temp}}}^{\{h\}}\right)}\right)$, $\forall q \in {\cal{Q}}_{k}$, $\forall k \in \dot{{\cal{K}}}$, and compute $\theta_{\overline{k}}$, $\forall \overline{k} \neq k \in {\cal{N}}$, $\theta_{N}$, $\forall k \in \dot{{\cal{K}}}$ by (7) with given $\tilde{{\cal{P}}}_{{\rm{temp}}}^{\{h\}}$;

7:　　 Solve (13) with the given $\eta^{\{t\}}_{E E}$ and ${\cal{Z}}$, and obtain the optimal $\tilde{{\cal{P}}}_{{\rm{temp}}}^{\{h+1\}}$;

8:　　 Update $h \longleftarrow h+1$;

9:　 until $\tilde{{\cal{P}}}_{{\rm{temp}}}^{h}$ converge to the optimal solution $\tilde{{\cal{P}}}_{{\rm{temp}}}^{*}$;

10:　 $\tilde{{\cal{P}}}^{\{t+1\}} \longleftarrow \tilde{{\cal{P}}}_{temp}^{\ast}$;

11:　Update $t \longleftarrow t+1$;

12: until $\left| {f\left( {\eta _{EE}^{\{ t - 1\} }} \right)} \right| < \varepsilon ,\ {{ or }}\ t \ge \tau$;

13: Obtain the optimal solution ${\cal{P}}^{\ast} = \{e^{\tilde{p}_{1}^{\{t\}}},e^{\tilde{p}_{2}^{\{t\}}},...,e^{\tilde{p}_{N}^{\{t\}}}\}$;

Algorithm 2 Alternating-Optimization-Based Joint Time Slot Scheduling and Power Allocation Algorithm

1: Obtain the low bound $M_{{\rm{min}}}$ and the upper bound $M_{{\rm{max}}}$ of M, and the power allocation solution ${\cal{P}}_{0}$ and the slot scheduling scheme ${\cal{Z}}_{0}$ under $M_{{\rm{min}}}$ by the algorithm proposed in [2];

2: Set the maximum tolerance $\varepsilon$;

3: for $M=M_{{\rm{min}}};M \leq M_{{\rm{max}}};M++$ do

4:　Initialize iteration index $l \leftarrow 0$;

5:　Initialize ${\cal{Z}}^{\{l\}}_{M} \leftarrow {\cal{Z}}_{0}$, and ${\cal{P}}^{\{l\}}_{M} \leftarrow {\cal{P}}_{0}$;

6:　repeat

7:　　Solve (4) with the given ${\cal{P}}^{\{l\}}_{M}$ and ${\cal{Z}}^{\{l\}}_{M}$ by the Kuhn-Munkres algorithm, and obtain the optimal slot scheduling ${\cal{Z}}^{\{l+1\}}_{M}$;

8:　　Solve (5) with the given ${\cal{P}}^{\{l\}}_{M}$ and ${\cal{Z}}^{\{l+1\}}_{M}$ by Algorithm (1), and obtain the optimal power allocation ${\cal{P}}^{\{l+1\}}_{M}$;

9:　　Update $l \longleftarrow l+1$;

10: until the increment of η_EE is smaller than ε;

11: Obtain the optimal network EE $\eta^{\ast}_{M}$, and the optimal solution ${\cal{Z}}^{\{l\}}_{M}$ and ${\cal{P}}^{\{l\}}_{M}$;

12: end

13: Let $\eta^{\ast}_{M^{\ast}} = \text{{{Max}}}\{\eta^{\ast}_{M_{{\rm{min}}}},\eta^{\ast}_{M_{{\rm{min}}+1}},\ldots,\eta^{\ast}_{M_{{\rm{max}}}}\}$;

14: Return the optimal solution $M^{\ast}$, ${\cal{Z}}^{\{l\}}_{M^{\ast}}$ and ${\cal{P}}^{\{l\}}_{M^{\ast}}$;

1) Optimal power allocation with fixed slot scheduling (denoted as OPA_FSS): With the fixed slot scheduling scheme ${\cal{Z}}_{0}$, the transmission powers are optimized by Algorithm 1.

2) Optimal slot scheduling with fixed power allocation (denoted as OSS_FPA): With the fixed power allocation scheme ${\cal{P}}_{0}$, the slot scheduling of all of sensors are optimized by the slot scheduling algorithm proposed above.

The corresponding comparison results are shown in Fig. 2. It can be observed that the proposed AO shows the best performance. The reason is that slot scheduling and power allocation may be influenced by each other, thus it is unreasonable to fix one of them and then solve another. For the proposed AO, slot scheduling and power allocation could be solved in an alternating way, which leads to better solutions. Furthermore, it can be found that AO achieves significant EE gains compared to CMS-MAC algorithm.

Figure  2.  Comparisons of EE. (a) for different clustering numbers with $\gamma_{th}$ = 10 dB; (b) for different SINR constraints with K = 7.

DownLoad: Full-Size Img PowerPoint

Conclusion: In this letter, an EE maximization problem with cross-layer design is considered in clustered UASNs. To tackle the non-convex and mixed-integer optimization problem, a BCD-based iterative algorithm is proposed. Numerical results show that the proposed joint optimization scheme achieves significant EE gains compared to the separate optimization methods.

Acknowledgment: This work was supported by the National Natural Science Foundation of China (62273298, 61873223), the Natural Science Foundation of Hebei Province (F2019203095), and Provincial Key Laboratory Performance Subsidy Project (22567612H).