A Clustering Routing Algorithm Based on Improved Ant Colony Optimization Algorithms for Underwater Wireless Sensor Networks

Abstract

Because of the complicated underwater environment, the efficiency of data transmission from underwater sensor nodes to a sink node (SN) is faced with great challenges. Aiming at the problem of energy consumption in underwater wireless sensor networks (UWSNs), this paper proposes an energy-efficient clustering routing algorithm based on an improved ant colony optimization (ACO) algorithm. In clustering routing algorithms, the network is divided into many clusters, and each cluster consists of one cluster head node (CHN) and several cluster member nodes (CMNs). This paper optimizes the CHN selection based on the residual energy of nodes and the distance factor. The selected CHN gathers data sent by the CMNs and transmits them to the sink node by multiple hops. Optimal multi-hop paths from the CHNs to the SN are found by an improved ACO algorithm. This paper presents the ACO algorithm through the improvement of the heuristic information, the evaporation parameter for the pheromone update mechanism, and the ant searching scope. Simulation results indicate the high effectiveness and efficiency of the proposed algorithm in reducing the energy consumption, prolonging the network lifetime, and decreasing the packet loss ratio.

1. Introduction

Nowadays, underwater wireless sensor networks (UWSNs) have aroused widespread interest with the exploration and utilization of marine resources [1,2]. UWSNs are composed of numerous underwater acoustic sensor nodes deployed in underwater monitoring areas, which perform functions such as navigation, surveillance, resource exploration, intrusion detection, and data collection [3]. However, the underwater sensor nodes are small devices with limited energy and they are difficult to replace, which makes energy efficiency a major concern [4,5]. Moreover, UWSNs have disadvantages such as high propagation delay, low bandwidth, and high error rate [6]. Therefore, designing an energy-efficient routing algorithm for data transmission in a complex underwater environment is extremely important for UWSNs [7]. There exist many conventional routing algorithms in terrestrial wireless sensor networks (TWSNs), but they are usually infeasible in UWSNs [8]. The reasons are as follows. Firstly, TWSNs employ radio signals to transmit data, but UWSNs use acoustic signals for data transmission because radio signals attenuate quickly underwater [9]. Secondly, TWSNs usually employ a 2D network model, whereas UWSNs adopt a 3D network model, which is a great challenge to researchers. Thirdly, the replacement of sensor nodes is more difficult in UWSNs than in TWSNs.

In conserving energy, multi-hop data transmission in long-distance communication for UWSNs is more effective than single-hop transmission [10]. Additionally, to alleviate the problems of data collision and traffic load balance, it is important to design a reliable network topology [11]. Many studies have shown that the clustering routing algorithm is capable of saving energy, avoiding collisions, and balancing traffic load because it employs the clustering topology and uses a multi-hop mechanism during the inter-cluster data transmission [12,13]. In clustering routing algorithms, the network is divided into many clusters and each cluster consists of one cluster head node (CHN) and several cluster member nodes (CMNs) [14]. When clusters are formed, the CHNs allocate channel resources for CMNs and the CMNs transmit data according to the allocation, which can decrease collisions [15]. After receiving the data from the CMNs in the same cluster, the CHN is responsible for aggregating the data, which can reduce data redundancy and decrease the number of data packets to be sent to the sink node (SN), thereby conserving energy [16]. Meanwhile, the decreased number of data packets helps reduce collisions when the CHNs transmit them to the SN. Additionally, the multi-hop mechanism is used when CHNs send data to the SN, which can save energy compared to the single-hop mechanism. Moreover, the clustering routing algorithm usually employs a CHN rotation mechanism, which avoids the excessive energy consumption of CHNs, balances the energy dissipation, and prolongs the network lifetime [17].

Many studies indicate that clustering routing algorithms are superior in controlling data traffic and reducing data transmission, and are thus capable of saving energy, extending network lifespan, and decreasing the packet loss ratio [18,19,20,21,22,23,24,25,26,27,28]. The low-energy adaptive clustering hierarchy (LEACH) algorithm, the earliest clustering routing algorithm, employs a probabilistic method to select CHNs and does not consider the residual energy of nodes, which causes some low-energy nodes to become CHNs [18]. This goes against the energy balance and the energy efficiency, for these inefficient CHNs may die prematurely. Therefore, researchers proposed improved clustering routing algorithms. Domingo et al. proposed a distributed underwater clustering scheme (DUCS), which considers the residual energy of candidate nodes when selecting CHNs [19]. However, the distance between the candidate CHN and the SN is not considered in the DUCS algorithm. Xu et al. came up with a clustering routing algorithm where the CHN selection is optimized by considering the remaining energy and the positions and the density of nodes [20]. Additionally, the mechanism of data transmission from the CHN to the SN is improved, thereby minimizing the energy consumption and maximizing the network lifetime. Wang et al. presented a clustering routing protocol based on hybrid multiple hops, where the CHN selection based on the remaining energy of nodes is self-organized and the path from CHN to the destination node is obtained by the establishment of a minimum spanning tree [21]. This algorithm can reduce energy consumption and extend the network expectancy, but is designed for TWSNs instead of UWSNs. Wan et al. designed an adaptive clustering underwater network (ACUN) algorithm, which considers the residual energy of nodes and the energy loss of paths to select CHNs [22]. It also considers the node energy condition to select paths with high energy efficiency. However, the distance factor has not been considered in this literature. Bhattacharjya et al. proposed a cluster-based underwater wireless sensor network (CUWSN) algorithm, which selects CHNs based on the residual energy of nodes and adopts multi-hop transmission to forward data packets to the destination node [23]. The CUWSN can reduce energy consumption and improve the performance of the network, but the distance factor has not been taken into account and the multi-hop paths have not been optimized. In [24], Ayaz et al. did a survey on routing algorithms in UWSNs, which aimed to solve problems such as data transmitting and node deployment, as well as localization. In the survey, the authors analyzed and compared several clustering routing algorithms such as the DUCS [19], the distributed minimum cost clustering protocol (MCCP) [25], temporary cluster-based routing (TCBR) [26], the location-based clustering algorithm for data gathering (LCAD) [27], and the multipath virtual sink architecture [28]. The MCCP was proposed by Pu et al. in [25], which addresses the hotspots near the SN and balances the traffic load. In addition, the MCCP determines the number of CMNs according to the locations of the CHNs and the SN. However, the multi-hop method is not supported in the MCCP and the period of re-clustering is too long. TCBR was presented by Ayaz et al. in [26], where multiple SNs are placed on the water’s surface in order to solve the problem that nodes near the SN consume more energy and die prematurely. TCBR can balance the energy dissipation, but it cannot achieve high efficiency in time-critical applications. The LCAD was given by Anupama et al. in [27], where horizontal acoustic communication is employed when CMNs transmit data to CHNs, and autonomous underwater vehicles (AUVs) are used when CHNs send data to the SN. The LCAD can solve the energy hole problem and reduce energy dissipation. However, it relies on the network structure and its effectiveness is affected if the node mobility is considered. The multipath virtual sink architecture was proposed by Seah and Tan in [28], where the aggregation nodes aggregate the data from other nodes in the same cluster, and then transmit the aggregated data to the SNs. The authors assume that these SNs can achieve high-speed communications so that they form a virtual SN. This method can guarantee high reliability, but the duplicate data packets result in redundant transmission, which increases the resource consumption. A pressure routing algorithm for UWSNs was presented by Uichin et al. in [29], which employs anycast routing to send data to the SN according to the pressure levels. Pressure routing can achieve high delivery ratios and low end-to-end delay, but it consumes more energy because of the use of opportunistic routing and the repeated transmission of the copies of same packets. The cluster sleep–wake scheduling algorithm in UWSNs was proposed by Zhang et al. in [30], which shows the rotating temporary control nodes that control the sleep–wake scheduling, thus minimizing the energy dissipation. The energy optimization clustering algorithm (EOCA) was put forward by Yu et al. in [11], where the number of neighboring nodes, the remaining energy of nodes, the motion of nodes, and the distance factor are taken into account. Additionally, the EOCA provides a maximum effective communication range based on the remaining energy of nodes, thereby controlling the energy dissipation for packet delivery. However, the EOCA does not optimize the multi-hop paths for data transmission to the SN.

Greedy algorithms have shown great strength in addressing combinational optimization problems, which make local optimal choices at every step [31,32]. They are effective in finding global optimal solutions in specific circumstances [33], and we take Dijkstra’s algorithm and Prim’s algorithm as examples [34,35]. Dijkstra’s algorithm, which was proposed by Edsger Wybe Dijkstra in 1959, has been widely used to look for the shortest paths between network nodes. It can thus be employed in routing algorithms to find the shortest path to the destination node [36]. Prim’s algorithm constructs minimum spanning trees and can usually find the best solutions [37]. Nevertheless, the greedy algorithms are considered short-sighted because they only make the best choice at every step and do not consider the overall condition. That is the reason why they cannot obtain the optimal solution sometimes. Hence, researchers proposed many metaheuristics extending greedy algorithms, which can be applied to a wide range of different problems [38,39,40,41]. The greedy randomized adaptive search procedure (GRASP) was presented by Feo et al. in [38], where the present problem can be solved in every iteration. Each iteration has two stages: stage one provides the initial solution and stage two aims to find the improved solution by applying the local search procedure to the solution provided by stage one. The fixed set search (FSS) was proposed by Jovanovic et al. in [39], which adds the learning method to the GRASP and is thus more effective than the GRASP in the solution quality as well as the computational cost. In the work of Arnaout in [40], the worm optimization (WO), on the basis of the worm behaviors, was proposed to solve unrelated parallel machine schedule problems, which can find the optimal solution as well as reduce the makespan. In [41], the particle swarm optimization (PSO) and the fuzzy algorithm are used in a clustering scheme for UWSNs, which can find the optimal number of clusters and select the optimal CHNs, thereby reducing the energy dissipation and prolonging the lifespan of UWSNs.

The ant colony optimization (ACO) algorithm is also a population-based metaheuristic that extends the greedy algorithm, which has been widely used to optimize routing paths [42,43,44]. The ACO can find optimal paths from source nodes to destination nodes so that the energy consumption can be reduced and the network lifetime can be prolonged. ACO algorithms simulate ant behavior, as ants could usually find the optimal paths to foods [45]. Ants release pheromones on the path that they make. Other ants are more likely to choose the path with higher pheromone concentration, and the following ants will also release pheromones on the path, which increases the pheromone concentration [46]. The higher pheromone concentration will attract more ants, which forms a positive feedback loop. After a period of time, the ant colony will find the shortest path to the food source.

So far, many researchers have applied ACO algorithms to routing algorithms. Agarwal et al. combined ACO algorithms with the LEACH algorithm for prolonging the lifetime of TWSNs, and they validated the effectiveness of the algorithm by simulation experiments [47]. Okdem et al. applied ACO algorithms to routing algorithms by taking into account the hop count and the residual energy of neighbor nodes, which can reduce the energy consumption to a certain extent, but the algorithm can only balance the local energy consumption [48]. Camilo et al. improved the pheromone update process of ACO algorithms when designing routing algorithms, and took into account the total energy of all nodes, thereby improving the energy efficiency of the entire network [49]. Shan proposed a threat cost calculation for submarine path planning based on ACO algorithms [50]. He presented a new cost function that took into account the path length and distance factor, and adopted a coalescing differential evolution mechanism when updating the pheromone so as to settle the local optimum problem. Zhang et al. proposed a clustering algorithm on the basis of the ACO algorithm, which was designed for TWSNs instead of UWSNs. When selecting CHNs, they considered the residual energy of candidate nodes and the distance factor. When looking for routing paths, the authors took into account the path length as well as the node energy, which can balance the network energy consumption [51]. Sun et al. presented a routing protocol based on ACO algorithms for TWSNs, where the remaining energy of nodes, the transmission direction, and the distance between nodes were considered in order to look for ideal routing paths and reduce the energy consumption of the network [52]. Liu proposed an effective transmission strategy using ACO algorithms, which can improve the energy efficiency and prolong the network lifetime. Additionally, the improved ACO algorithm was unlike the traditional one: no heuristic information and just one step for every ant in its whole trip [53]. The literature mentioned above indicate that ACO algorithms could be employed to look for the optimal routing paths in networks. Nevertheless, the problem of clustering routing algorithms in UWSNs has not been resolved, so we need to make some improvements to the existing ACO algorithms and apply them to UWSNs.

To our knowledge, few studies have applied ACO algorithms in UWSNs when designing clustering routing algorithms. It is of great significance to design an energy-efficient routing algorithm that can minimize the energy consumption and ultimately maximize the network lifetime. Therefore, this paper presents a clustering routing algorithm based on an improved ACO algorithm for UWSNs. Firstly, we describe the network model and the energy consumption model that can be used to quantify energy consumption and evaluate the energy efficiency of the proposed algorithm. Secondly, we present an improved ACO algorithm through the improvement of the heuristic information, the evaporation parameter for the pheromone update mechanism, and the ant searching scope. To improve the heuristic information of the traditional ACO algorithm, we consider not only the residual energy but also the distance factor in the proposed heuristic information. Additionally, the proposed adaptive strategy of the evaporation parameter for the pheromone update mechanism helps improve the global search ability and the convergence rate of the algorithm. Thirdly, we design the clustering routing algorithm, which has two main phases in one round: CHN selection phase and data transmission phase. In the first phase, we optimize CHN selection by considering the residual energy of nodes, the distance from the node to the SN and the average distance between the node and the other nodes in the cube. In the second phase, the single-hop method is adopted for the data transmission from CMNs to CHNs, and the multi-hop method is employed when CHNs transmit data to the SN, and the optimal multi-hop paths are found by the improved ACO algorithm. Finally, simulation results show that compared to five other algorithms, the proposed algorithm can effectively reduce the energy consumption of the network, prolong the network lifetime, and decrease the packet loss ratio.

The remainder of the rest of the paper is as follows. The network model and energy consumption model are presented in Section 2. Section 3 proposes the improved ACO algorithm. The proposed clustering routing algorithm is given in Section 4. Simulation results and analyses are provided in Section 5. Section 6 draws the conclusion.

2. Model Assumptions

2.1. Network Model

This paper presents a large-scale 3D network model for UWSNs where the underwater sensor nodes are randomly deployed in an underwater monitoring area. Figure 1 illustrates the network model and the description is as follows:

• The 3D underwater network is evenly divided into small cubes and each cube is regarded as a cluster.
• Two types of nodes are considered in the network: the ordinary underwater acoustic sensor nodes and the SN. The underwater acoustic sensor nodes are static after random deployment.
• The single SN is always the destination node and is located at the center of the surface of the monitoring area, which has a continuous energy supply. However, the energy of the ordinary sensor nodes is restrained and they do not have an energy supply.
• All nodes (except the SN) have the same initial energy and every node has a unique ID.
• The locations of the SN and sensor nodes after placement can be obtained by localization algorithms [54], and the distance between two nodes can be calculated.
• The sending power can be controlled by nodes according to different distances to the receiving nodes.
• In every small cube, sensor nodes run for CHN. One of them will become the CHN and the others become CMNs. CMNs collect data and send them to the CHN by a single hop. After receiving the data from the CMNs, the CHN processes the data and then transmits them to the SN in one data packet by multiple hops. The relay nodes on multi-hop paths are other CHNs. If some CHNs are near the SN, they can directly forward data to the SN by a single hop.

2.2. Energy Consumption Model

To quantify the energy consumption, this paper refers to the underwater acoustic energy consumption model given in [55]. We assume that the minimum power for one node to receive a data packet is P₀. Then the minimum transmission power needs to be P₀A(l). A(l) is the attenuation function, which is presented by:

$$A(l)=l^k{a}^l$$

(1)

where l is the distance between transmitter node and receiver node and k is the energy spreading factor (1 for cylindrical, 2 for spherical, 1.5 in general), and

$$a={10}^{\alpha (f)/10}$$

(2)

is decided by the absorption coefficient, which is presented by:

$$\alpha (f)=0.11\frac{f^2}{1+f^2}+44\frac{f^2}{4100+f^2}+2.75\times {10}^{-4}{f}^2+0.003$$

(3)

where f is carrier frequency in kHz. Then we can define the energy consumption for sending and receiving:

$$E_t(l)=T_t{P}_{0}A(l)$$

(4)

$$E_r=T_r{P}_0$$

(5)

where E_t (l) and E_r are energy consumption for transmitting and receiving, respectively. T_t and T_r are the time duration for a node to transmit and receive one data packet, respectively. The time duration can be calculated by the data packet length and the data transmission rate.

3. The Improved Strategy of the ACO Algorithm

3.1. Overview of ACO

The ACO algorithm is widely used to find an optimal path between a source node and a destination node. When searching for the destination node, artificial ants deposit a chemical substance called a pheromone on the path that they pass [56]. The pheromone is the medium that ants used to communicate and it guides other ants. Ants are more likely to follow a path with a higher pheromone concentration, and the following ants also release pheromones on the path, which increases the pheromone concentration. The increased pheromone concentration attracts more ants, which forms a positive feedback loop [57]. The pheromone matrix is a two-dimensional matrix used to record the pheromone values on every partial path. We use ${\tau }_{ij}(t)$ to denote the pheromone concentration between node i and node j at time t. Additionally, t is the iteration counter. Moreover, the pheromone volatilizes with time. After all ants have completed a path search, the pheromone matrix should be updated. The global pheromone update rule is presented as follows:

$${\tau }_{ij}(t+1)=(1-\rho ){\tau }_{ij}(t)+\Delta {\tau }_{ij}(t)$$

(6)

$$\Delta {\tau }_{ij}(t)={\displaystyle \sum _{k=1}^q\Delta }{\tau }_{ij}^k(t)$$

(7)

$$\Delta {\tau }_{ij}^k(t)=\{\begin{array}{ll}Q/L_k& ,(i,j)\in \mathrm{tour}\mathrm{by}\mathrm{ant}k\\ 0& ,\mathrm{otherwise}\end{array}$$

(8)

where ρ (0 < ρ < 1) is the evaporation parameter, q is the total number of ants, Q is the total amount of pheromone, and L_k is the total length of the path that the kth ant passes during this time. Nevertheless, a too high pheromone concentration may cause a local optimum of the algorithm and a too low pheromone concentration may not attract other ants. Thus, we employ the method introduced in the max–min ant system (MMAS) to limit the pheromone value [58], which is presented as follows:

$${\tau }_{ij}(t+1)=\left\{\begin{array}{c}{\tau }_{\max },{\tau }_{ij}(t+1)>{\tau }_{\max }\\ (1-\rho ){\tau }_{ij}(t)+\Delta {\tau }_{ij}(t),\mathrm{otherwise}\\ {\tau }_{\min },{\tau }_{ij}(t+1)<{\tau }_{\min }\end{array}\right.$$

(9)

where ${\tau }_{\max }$ and ${\tau }_{\min }$ represent the maximum and the minimum of the pheromone values, respectively. The limitation of the pheromone values could avoid the stagnation of the searching process and improve the global convergence of the algorithm.

In ACO, the transition probability from node i to node j for the kth ant can be given by:

$$p_{ij}^k=\left\{\begin{array}{c}\frac{{({\tau }_{ij}^{}(t))}^{\alpha }{({\eta }_{ij}^{})}^{\beta }}{{\displaystyle \sum _{m\in U_k}{({\tau }_{im}^{}(t))}^{\alpha }{({\eta }_{im}^{})}^{\beta }}},j\in U_k\\ 0,\mathrm{otherwize}\end{array}\right.$$

(10)

where U_k represents the set of next hop nodes available to the ants, ${\eta }_{ij}^{}$ is the heuristic information, α is the pheromone parameter, and β denotes the heuristic information parameter.

Ants transfer to the next hop node according to (10) until they arrive at the destination node. After all q ants have reached the destination node, the pheromone matrix is updated. It is decreased by evaporation, and ρ ranging from 0 to 1 is the evaporation parameter. The evaporation process contributes to avoiding unrestrained accumulation of the pheromone concentration. If one partial path is not selected by ants, its pheromone concentration decreases gradually, which makes ants not choose this bad path over time. The pheromone value is increased if the ants deposit pheromone on the path. The better paths receive more pheromone released by ants, which are more likely to be selected in future. Every pheromone value in the pheromone matrix is updated according to (7), (8), and (9). After the pheromone matrix is updated, the next iteration begins.

3.2. The Improved Evaporation Parameter

Researchers have proposed many methods to update the pheromone values. For example, Jovanovic and Tuba put forward a very efficient pheromone correction procedure based on the concept of suspicion, which avoids the local convergence of the ACO and enhances the overall performance of the ACO [59]. In this paper, we aim at the evaporation parameter ρ and propose an adaptive strategy to influence the update of the pheromone values. The evaporation parameter ρ is important to the ACO algorithm. In the most ACO algorithms, ρ is a fixed value. When the value of ρ is unreasonable, the convergence rate of the algorithm is affected. If the value is too small, the pheromone evaporation speed is too slow, making ants just follow the path with a high pheromone concentration and do not try to look for other potential paths. That means the algorithm can easily fall into the local optimum. If the value is too large, the pheromone volatilizes too fast, which causes the ACO to converge slowly. The adaptive strategy for evaporation parameter ρ is given by:

$$\rho (x)=\frac{X}{X+x}\times e^{-bx}$$

(11)

where X denotes the total number of iterations, x is the current number of iterations, and b is a constant. At the beginning, the pheromone volatilizes faster, and the pheromone concentration has a weaker guiding effect on the ants, which is helpful for the ants to find other potential paths. As the iterations increase, the value of ρ(x) gradually decreases, and the pheromone evaporation slows down. The positive feedback increases, which makes the ants tend to choose the path with a higher pheromone concentration. At this time, the ants have searched for feasible paths for a long time and the path with a higher pheromone concentration is the better choice. So, the proposed strategy is capable of improving the global search ability and the convergence rate of the algorithm.

3.3. The Heuristic Information

The heuristic information ${\eta }_{ij}^{}$ is only related to the distance to the next hop node, which can be calculated by:

$${\eta }_{ij}^{}=\frac{1}{d_{ij}}$$

(12)

where d_ij denotes the distance between node i and the next hop node j. Nevertheless, in UWSNs, the distance from node j to the SN also has an influence on the network energy consumption. If the next hop node j is closer to the SN, it tends to consume less energy to forward data. In addition, the energy of the next hop node also affects the balance of the energy consumption, which helps to prevent the node with low energy becoming the next hop node. Hence, this paper defines an improved strategy for heuristic information:

$${\eta }_{ij}=\frac{1}{\sigma d_{ij}+(1-\sigma )d_{js}}\times \frac{E_{jres}}{E_{ini}}$$

(13)

where σ is a constant ranging from 0 to 1, E_jres denotes the residual energy of the next hop node j, E_ini indicates the initial energy of node j, and d_js represents the distance from node j to the SN. From (13), we can see that the heuristic information is positively related to the residual energy of the next hop node j, and is negatively correlated with the distance between node i and node j and the distance from node j to the SN. It is more likely for node j to become the next hop node if the value of the heuristic information is larger.

3.4. The Proposal of Ant Searching Scope

The searching scope is crucial to the algorithm. Too small a scope may result in a failure to find the next hop node and too large a scope could lead to the slow convergence of the algorithm. To alleviate this problem, this paper presents the searching scope, as shown in Figure 2. R presents the transmission radius of nodes and θ denotes the searching scope. The density of nodes in the network and the transmission radius of nodes are two important factors to the searching scope. A high density of nodes and a large transmission radius only require a small scope. Clearly, if the value of θ is smaller, the transmission direction is closer to the SN. Theoretically, when the value of θ is zero, it is the best transmission direction from node i to the SN. However, in fact, there may not be enough nodes existing in that best transmission direction. If an ant cannot find an appropriate next hop node, the searching scope should be enlarged and θ should be smaller than 90 degrees.

4. Clustering Routing Algorithm Design

The clustering routing algorithm has two main phases: CHN selection phase and data transmission phase. In the algorithm, the network is divided into cubes, and each cube is seen as a cluster. In every cluster, nodes run for CHN. One of them will be selected as the CHN and the others become CMNs. CMNs collect data and send them to the CHN by a single hop. After receiving the data from the CMNs, the CHN processes the data and then transmits them to the SN in one data packet by multiple hops. The relay nodes on multi-hop paths are other CHNs and the optimal path to the SN is found by using the improved ACO algorithm.

4.1. Cluster Head Selection Phase

CHNs play a very important role in data transmission. The CHNs are responsible for processing the data received from their CMNs, and then forwarding the processed data to the SN. Many algorithms, such as the LEACH algorithm, generate CHNs in a random selection without considering the residual energy of the nodes. If the residual energy of the selected CHNs is too low, the nodes will die too early, which is bad for energy balance and network efficiency. Therefore, when selecting CHNs, the residual energy of the nodes should be considered. If the residual energy of one node is less than the average energy of the nodes in its cluster, it will not be qualified for the selection. In this paper, we consider not only the residual energy of nodes but also the distance factor to select CHNs. Hence, we propose an index for CHN selection as follows:

$$I_i=\frac{\lambda E_{ires}}{d_{is}{d}_{avg}}$$

(14)

$$d_{avg}=\frac{1}{N-1}{\displaystyle \sum _{n=1}^{N-1}{d}_{in}}$$

(15)

where λ is a constant, E_ires is the residual energy of node i, d_is is the distance between node i and the SN, d_avg is the average distance between node i and the other nodes in the cube, N is the total number of nodes in the cube, and d_in is the distance between node i and node n in the cube. It can be seen from (14) that it is more likely for a node to become a CHN if it has more residual energy, a shorter distance to the SN, and a shorter average distance to the other nodes in the cube.

In each cube, every qualified node calculates its value of I_i and broadcasts the message with its ID and I_i value to other nodes in the cube. Through comparisons, the node with the largest value of I_i will become a CHN. Then the CHN broadcasts the CHN message to the other nodes in the cube. After receiving the CHN message, the nodes reply to the CHN with an acknowledgement message and become CMNs. In addition, all the selected CHNs send message packets to the SN and the packets carry information such as the ID, the location, and the residual energy.

4.2. Data Transmission Phase

The data transmission phase includes intra-cluster data transmission and inter-cluster data transmission. In the intra-cluster data transmission, the CHNs allocate time slots by a time division multiple access (TDMA) scheme for the CMNs to send data packets to their own CHNs by a single hop. After the CMNs transmit the data packets for this round, they turn to sleep mode in order to reduce energy consumption. After receiving the data packets from all the CMNs in the cluster, the CHNs process the data and then transmit them to the SN by using a carrier sense multiple access with collision detection (CSMA/CD) mechanism through multiple hops and the optimal multi-hop paths are found by the improved ACO algorithm. If some CHNs are near the SN, they can directly transmit the data to the SN by a single hop. The process of the improved ACO algorithm is shown in Figure 3 and the steps are given as follows:

Step 1: To ensure the initial search ability of ants, the initial energy and the initial pheromone concentration of each node are set to be equal. Each node has a unique ID.

Step 2: The source node generates a forward ant at regular intervals. The format of the routing table carried by the forward ant is shown in

Table 1. The format of the routing table.

Source Node ID

SN ID

Hop Count

Taboo List

Packet Length

Packet Type

. The taboo list indicates the nodes that the ant has visited and these nodes cannot be accessed in future searches.

Step 3: The transfer probability to the next hop node is calculated by (10). The ant transfers to the next CHN according to this probability. Then this next hop node is added to the taboo list, and the hop count is increased by one.

Step 4: Step 3 is repeated until the ant reaches the SN. At the same time, the forward ant dies, and the corresponding backward ant is generated. The backward ant carries the routing information of the forward ant and returns to the source node by the path that the forward ant made. The routing information no longer changes as the backward ant returns. When the backward ant reaches the source node, a routing path is established.

Step 5: Steps 2, 3, and 4 are repeated until all ants have completed a path search. By this time, the present iteration ends. Then the search paths of the ants are noted, the taboo list is cleared, and the pheromone is updated according to (9).

Step 6: Steps 2 to 5 are repeated until the preset number of iterations is reached, and the optimal path output is shown.

It is noted that only one CHN finds its optimal path to the SN after Step 6, and the number of CHNs is equal to the number of small cubes in the network. Hence, by changing the IDs of the source nodes and repeating the whole process of the ACO algorithm, the paths from the other CHNs to the SN can be determined. In this paper, the destination node is always the SN and the CHNs that need to send data packets become the source nodes. The relay nodes on multi-hop paths are other CHNs. Furthermore, the search process for the optimal multi-hop routing paths is accomplished in the SN because it has a continuous energy supply. After the CHNs are selected, they send the SN messages with information such as IDs, locations, and residual energy so that the SN can figure out the optimal paths by using the improved ACO and then transmit the routing information to the CHNs.

By the time all the CHNs have sent the data to the SN, one round is over. At this time, if in one cube the residual energy of the CHN is more than half of the average energy of other nodes, the CHN of the next round stays the same, which can save energy and time. Otherwise, a new CHN is selected in the next round. The new selected CHN transmits its information to the SN so that the SN can restart the process of the ACO algorithm and find the optimal path for the new CHN.

5. Simulation Results and Analyses

For the convenience of comparison, the proposed algorithm in this paper is called ant colony optimization clustering routing (ACOCR). Five existing popular algorithms: LEACH [18], DUCS [19], LEACH-ANT [47], CUWSN [23], and EOCA [11] were chosen as the references to validate the proposed algorithm according to the number of surviving nodes, the energy consumption of the network, and the packet loss ratio. MATLAB was used to carry out the simulation where sensor nodes were randomly placed in a 3D area of 5000 m × 5000 m × 1000 m and the coordinate of the SN was (2500, 2500, 0). The network was divided into 64 cubes. The number of sensor nodes ranged from 300 to 500 for different scenarios. The data packet was 1024 bits in length and the data transmission rate was 2048 bps, by which the time duration for a node to transmit and receive data packets could be calculated. The broadcast and other message packets were 64 bits in length. The sound speed was 1500 m/s. As for the energy consumption parameters, the receiving power P₀ was set to 50 μW and the initial energy for every node was 120 J. The frequency f was 10 kHz.

5.1. Comparison and Analysis of the Number of Surviving Nodes

Figure 4 shows the number of surviving nodes versus the number of rounds for the proposed algorithm and reference algorithms when 400 nodes were considered in the network, from which we can see that the number of surviving nodes decreases with the increase in the network rounds no matter which algorithm is used. However, by using the proposed ACOCR, the network always has the largest number of surviving nodes.

In order to further assess the network lifetime, this paper brings in some metrics, such as first node dead (FND), half of the nodes dead (HND), and last node dead (LND). Figure 5 illustrates the number of rounds when FND, HND, and LND arise for the six algorithms, from which we can see that the first node of the ACOCR, EOCA, CUWSN, LEACH-ANT, DUCS, and LEACH dies in about the 806th, 686th, 632th, 569th, 481th, and 423th round, respectively. That indicates that with respect to the FND metric, the efficiency of the proposed ACOCR is 17.5%, 27.5%, 41.7%, 67.6%, and 90.5% higher than that of EOCA, CUWSN, LEACH-ANT, DUCS, and LEACH, respectively. As for the HND and LND, the proposed ACOCR outperforms LEACH by 63.2% and 65.2%, respectively. In conclusion, the proposed ACOCR algorithm has the best performance in prolonging the network lifetime because it adopts the improved CHN selection scheme by comprehensively considering the residual energy of the nodes, the distance between the node and the SN, and the average distance between the node and the other nodes in the cube. The CHN selection is capable of distributing the network load equally and preventing the nodes with low energy from becoming CHNs so as to prevent the premature death of nodes. Additionally, the ACOCR employs the improved ACO to find the optimal paths between CHNs and the SN in order to reduce the energy consumption. The LEACH has the worst performance, as it randomly selects CHNs without considering the residual energy of the nodes, which makes some nodes with insufficient residual energy be selected as CHNs and thus die too early. In addition, it does not consider the multi-hop paths when the CHNs send data packets to the SN. The LEACH-ANT algorithm and the DUCS algorithm outperform the LEACH algorithm. This is because the LEACH-ANT algorithm employs ACO algorithms to look for the next hop node, and the DUCS algorithm selects the CHN according to the residual energy of the node. However, the LEACH-ANT algorithm does not optimize the CHN selection or improve the ACO algorithm, and the DUCS algorithm does not consider the optimal paths from CHNs to the SN. Hence, they are inferior to the proposed ACOCR algorithm.

5.2. Comparison and Analysis of the Energy Consumption of the Network

Figure 6 illustrates the total energy consumption versus the number of rounds for the six algorithms when 400 nodes were considered in the network, from which we can see that the total energy consumption rises with the increase in the network rounds regardless of which algorithm is used. However, the proposed ACOCR algorithm is the most efficient one in reducing the energy consumption. For example, in round 600, the total consumed energy of the ACOCR, EOCA, CUWSN, LEACH-ANT, DUCS, and LEACH accounts for 32.5%, 41.1%, 50.6%, 58.2%, 65.4%, and 83.8% of the initial energy of the network, respectively. As for the network energy that is completely consumed, the energy efficiency of the ACOCR is improved by 14.7%, 18.3%, 29.3%, 45.3%, and 65.2% compared to that of the EOCA, CUWSN, LEACH-ANT, DUCS, and LEACH, respectively. This is because the proposed ACOCR optimizes CHN selection and employs the optimal paths found by the improved ACO algorithm to transmit the data packets, thereby minimizing the energy consumption. The EOCA and the CUWSN outperform the LEACH, DUCS, and LEACH-ANT. However, both of them are inferior to the ACOCR, which is because neither of them optimizes the multi-hop paths for data transmission.

Figure 7 demonstrates the number of rounds when the network energy is exhausted versus the different number of nodes in the network for the six algorithms, which validates the effect of the different number of network nodes on energy consumption. As the number of nodes increases, the number of rounds when the network energy is exhausted also increases. This is because more nodes in the network lead to a better balance of energy consumption. The proposed ACOCR outperforms the other five algorithms in all situations. For example, when there are 450 nodes in the network, the ACOCR algorithm is 10.1%, 15.6%, 19.2%, 43.4%, and 52.9% more efficient than the EOCA algorithm, the CUWSN algorithm, the LEACH-ANT algorithm, the DUCS algorithm, and the LEACH algorithm, respectively.

5.3. Comparison and Analysis of the Packet Loss Ratio

Table 2. The packet loss ratio for the six algorithms.

Algorithms	Packet Loss Ratio
ant colony optimization clustering routing (ACOCR)	12.8%
energy optimization clustering algorithm (EOCA)	14.9%
cluster-based underwater wireless sensor network (CUWSN)	15.8%
low-energy adaptive clustering hierarchy based on ant colony (LEACH-ANT)	17.1%
distributed underwater clustering scheme (DUCS)	18.8%
low-energy adaptive clustering hierarchy (LEACH)	20.7%

provides the packet loss ratio after round 1200 for the six algorithms when 400 nodes were considered in the network. The packet loss ratio is defined in this paper as the ratio of the number of data packets that the CHNs send to the number of data packets that the SN receives during the whole simulation process. As we can see from the table, the packet loss ratio of the proposed ACOCR is the lowest. The LEACH, which performs the worst, has about a 1.62 times higher packet loss ratio than the proposed ACOCR does. This is because the ACOCR adopts the improved ACO algorithm to find the optimal routing paths, which can reduce the risk of packet loss.

Figure 8 demonstrates the received packets by the SN versus the number of rounds for the six algorithms when 400 nodes were considered in the network. The more packets the SN receives, the more efficient the algorithm is. Apparently, the ACOCR algorithm has the best performance, the efficiency of which is 18.6%, 27.4%, 44.1%, 60.9%, and 84.1% higher than that of the EOCA, CUWSN, LEACH-ANT, DUCS, and LEACH, respectively, in round 1200.

6. Conclusions

To alleviate the problem of energy consumption in UWSNs, this paper presented an energy-efficient clustering routing algorithm based on the improved ACO algorithm. The contributions of the paper were as follows. Firstly, the improvement of the heuristic information was proposed in the paper based on the consideration of the residual energy of nodes and the distance factor. Secondly, this paper provided the improved adaptive strategy of the evaporation parameter for the pheromone update mechanism, which can be of help to the global search ability and the convergence rate of the algorithm. Thirdly, this paper proposed the ant searching scope. Fourthly, we optimized the CHN selection by considering the residual energy of nodes, the distance from the node to the SN, and the average distance between the node and the other nodes in the cube. Finally, simulation results demonstrated that the proposed ACOCR algorithm outperforms the LEACH, the DUCS, the LEACH-ANT, the CUWSN, and the EOCA in terms of the network lifetime, the energy consumption, and the packet loss ratio. The limitation of the paper is that the multipath effect of underwater channels was not considered. Therefore, we plan to study the multipath effect on the data packet transmission and design cross-layer protocols in the future. Moreover, in this paper, we employed a random method to generate the network node. In order to make the network model closer to the practical situation, we plan to use NS-3 to simulate our algorithm and call the function to generate the nodes as well as set attributes for them.