[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Next Article in Journal
RPC-Based Orthorectification for Satellite Images Using FPGA
Next Article in Special Issue
A Data Quality Control Method for Seafloor Observatories: The Application of Observed Time Series Data in the East China Sea
Previous Article in Journal
Three-Dimensional Terahertz Coded-Aperture Imaging Based on Back Projection
Previous Article in Special Issue
A Conformal Driving Class IV Flextensional Transducer
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Sensors
Volume 18
Issue 8
10.3390/s18082512
sensors-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

An Effective Scheduling Algorithm for Coverage Control in Underwater Acoustic Sensor Network

by
Hui Wang
1,2,
Youming Li
1,*,
Tingcheng Chang
2 and
Shengming Chang
1
1
Department of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China
2
Department of Computer Science Engineering, Ningde Normal University, Ningde 352000, China
*
Author to whom correspondence should be addressed.
Sensors 2018, 18(8), 2512; https://doi.org/10.3390/s18082512
Submission received: 25 June 2018 / Revised: 23 July 2018 / Accepted: 28 July 2018 / Published: 1 August 2018
(This article belongs to the Special Issue Underwater Sensing, Communication, Networking and Systems)
Browse Figures
Figure 1
<p>Three-dimensional underwater acoustic sensor network structure.</p> "> Figure 2
<p>Coding rule design.</p> "> Figure 3
<p>Relationship between values of <math display="inline"><semantics> <msup> <mrow> <mi>F</mi> </mrow> <mi>k</mi> </msup> </semantics></math>, <math display="inline"><semantics> <mi>α</mi> </semantics></math> and <math display="inline"><semantics> <mi>β</mi> </semantics></math>.</p> "> Figure 4
<p>Time slot diagram of a TDMA frame period.</p> "> Figure 5
<p>Network reconfiguration mechanism flow chart.</p> "> Figure 6
<p>The change trend of the fitness function when the number of nodes changes and the node sensing radius <math display="inline"><semantics> <msub> <mi>r</mi> <mi>s</mi> </msub> </semantics></math> changes.</p> "> Figure 7
<p>The change trend of the number of nodes in the minimum node set when the number of nodes changes and the node sensing radius changes.</p> "> Figure 8
<p>Relationship between network lifetime and number of nodes.</p> "> Figure 9
<p>Relationship between network lifetime and sensing radius <math display="inline"><semantics> <msub> <mi>r</mi> <mi>s</mi> </msub> </semantics></math>.</p> "> Figure 10
<p>Relationship between network coverage and running rounds.</p> "> Figure 11
<p>Average residual energy of network nodes.</p> ">
Versions Notes

Abstract

:
Coverage maintenance is a bottleneck restricting the development of underwater acoustic sensor networks (UASNs). Since the energy of the nodes is limited, the coverage of UASNs may gradually decrease as the network operates. Thus, energy-saving coverage control is crucial for UASNs. To solve the above problems, this paper proposes a coverage-control strategy (referred to as ESACC) that establishes a sleep–wake scheduling mechanism based on the redundancy of deployment nodes. The strategy has two main parts: (1) Node sleep scheduling based on a memetic algorithm. To ensure network monitoring performance, only some nodes are scheduled to work, with redundant nodes in a low-power hibernation state, reducing energy consumption and prolonging the network lifetime. The goal of node scheduling is to find a minimum set of nodes that can cover the monitoring area, and a memetic algorithm can solve this problem. (2) Wake-up scheme. During network operation, sleeping nodes are woken to cover the dead nodes and maintain high coverage. This scheme not only reduces the network energy consumption but takes into account the monitoring coverage of the network. The experimental data show that ESACC performs better than current algorithms, and can improve the network life cycle while ensuring high coverage.

1. Introduction

With the rise of the marine economy, countries around the world are paying increased attention to maritime rights and interests. Hence, underwater acoustic sensor networks (UASNs) have become a popular research topic [1,2]. They are mainly applied to mid- and long-term marine-resource surveys, disaster warning and forecasting, environmental monitoring, and submarine exploration [3]. Their broad application prospects have gained attention in academic and military circles.
The sensing range of nodes in UASNs is known to be limited. Therefore, the coverage of a monitored area is an important issue that UASNs must consider in topology control [4,5,6,7]; in addition, UASNs are node-sparse networks, so the coverage problem within the scope of monitoring is more difficult to solve, as the failure of any one node may lead to coverage holes. However, underwater nodes are expensive, and their redundancy is costly and difficult to implement. Reasonable planning is required for coverage and redundancy.
To achieve energy optimization, early researchers experimented with many algorithms and strategies for different network structures and application requirements [8,9,10,11,12]. This research has two main aspects.
The first aspect is to achieve energy balance through network topology control, which is mainly achieved by equalizing energy loss within the entire network or optimizing node transmit power. Based on network-topology control, the energy consumption of the entire network is balanced, so that the lifetime of the wireless sensor network is extended, or the node transmit power-control algorithm is optimized. According to the redundancy of the deployment node, optimization and balance are achieved through the sleep–wake rotation of nodes. Based on different characteristics of nodes, the residual energy aware dynamic algorithm [13] dynamically senses the residual energy at nodes, determines the transmit power based on that, and builds a topology relationship. This is aimed at extending the network lifetime by reducing the use of network nodes with low remaining energy for data forwarding. The algorithm uses a centralized control-based topology construction algorithm. It needs to know the topology information of the entire network, and the overhead is too large. A local topology-control algorithm [14] is proposed to avoid the addition of nodes with low residual energy to the forwarding path. This is a distributed topology control algorithm. Fewer algorithms are based on power control and consider the remaining energy of a node. In underwater sensor network topology control, there is still a lack of simple and effective methods.
The second aspect is to implement energy optimization through routing strategies. Energy optimization is mainly implemented by reducing the routing overhead. Methods of reducing routing overhead include minimum transmission energy consumption routing, maximum network lifetime routing, and path energy consumption equalization policies. The low-energy adaptive clustering hierarchy (LEACH) protocol [15] is a typical clustering algorithm. Through the cluster head selection strategy, the topology relationship is rebuilt on each selection. The geographical adaptive fidelity (GAF) algorithm [16] is a clustering algorithm based on the geographic location of nodes. The algorithm divides the monitoring area into several cells, assigns nodes to cells according to geographical locations, and periodically selects a cluster head node in each cell. The GAF algorithm is based on the plane model, and it uses the distance between nodes to judge whether they can communicate with each other. However, in practical applications, it is not possible to consider only the physical location, such as the communication channel. Moreover, the algorithm does not consider the problem of node energy balance.
Each of the above energy-optimization algorithms focuses on different scenarios and application modes, and some algorithms have good results in the context of their design. At present, most of these achievements are for the design of land-surface wireless sensor networks. Underwater sensor networks have some common problems, as summarized below.
(1)
In the research object, the system model does not consider the water environment factors in practical application, and cannot meet the energy-optimization requirements of the underwater sensor network.
(2)
The autonomy of network nodes is insufficient, and there is a lack of intelligence in the process of energy-optimization of nodes.
To solve the above problems, this paper proposes an energy-saving coverage-scheduling scheme to optimize UASNs. We studied the node sleep–wake scheduling mechanism based on a memetic algorithm, closed the redundant nodes in the network after node deployment, and optimized the UASN’s topology. It is worth noting that the coverage area of a redundant node usually overlaps with that of its neighbor nodes. Switching a redundant node to sleep mode can reduce network overhead. Further, an effective node wake-up scheme is also a problem considered in this paper. With the operation of the network, the energy of some nodes is depleted, which can easily cause network cavities. The wake-up scheme will activate one or more nodes in an affected neighborhood to maintain high coverage. The ESACC algorithm achieves maximum coverage and extends the entire network life cycle with a minimum number of active nodes. This study theoretically analyzed and evaluated the performance of the algorithm through experiments. The results show that the algorithm is superior to the CMSS [6] and LEACH-Coverage-U  [11] algorithms in maintaining high coverage and a long lifetime.
The rest of this paper is organized as follows: Section 2 describes the preconditions and models related to the ESACC algorithm. Section 3 provides a detailed description of the issues studied in this paper and the proposed ESACC algorithm. Section 4 describes our experimental results and compares them with different methods. Conclusions are given in Section 5.

2. Preliminaries

2.1. Assumptions

We assume that the monitoring area is a cube denoted by A, and the monitoring objects are randomly distributed events and the number of events is G. Assume that the sink node is stationary after deployment (ignoring small-scale movements), and the nodes are not restricted. The sink node and all other nodes can use the relevant positioning algorithm to know their real-time location in the monitored waters. In addition, assume that all nodes are homogeneous and have the same communication capacity, sensing range, and data-processing capability. The sensing range of a node is a spherical area with sensing radius r s .
The method proposed in this paper accounts for the coverage of a given area. Here, we assume that each event e t will always generate an event signal. As shown in Figure 1, each event e t is surrounded by multiple nodes. If e t is within the perceived range of a given node r s , the node will detect the event signal and transmit the measured data to the receiver through multi-hop mode.

2.2. Sensing Coverage Model

The perceptual coverage model is used to describe the node’s perception of the surrounding waters [17]. Assuming there is a node s i ( x i , y i , z i ) in the three-dimensional space, its Euclidean distance to any spatial event e j ( x j , y j , z j ) is d ( s i , e j ) . The binary detection model determines that the probability that event e j is covered by node s i is
γ j i = 1 d s i , e j = x i - x j 2 + y i - y j 2 + z i - z j 2 < r s 0 o t h e r w i s e
Equation (1) shows that, in monitoring area A, for ∀ e j ∈ A , if the Euclidean distance between the event e i and the node s i is smaller than the sensor radius r s , then it can be covered, and otherwise it is not covered. Assume that there are k nodes s 1 , s 2 , ⋯, s k , and their coverage rates for event e i are γ i 1 , γ i 2 , ⋯, γ i k respectively. Then, the coverage of event e i in the network is
γ A e i = 1 - ∏ n = 1 k 1 - γ i n

2.3. Network Energy-Consumption Model

Much literature has proposed node energy-consumption models for UASNs [18,19]. This paper uses the same energy-consumption model as Zhao and Liang (2006) [19]. The energy consumed by the transmitter to send a package of m bits is
E T X m , d = m E e l e c + m T b C H d e a f d
Similarly, the energy consumption of the receiver is
E R X m , d = m E e l e c
where E e l e c is the energy consumed by the node circuit to process one bit of information. C is the coefficient when the transmitter is at the minimum transmit power derived from the sonar equation in [19], and its value is 2 π × 0 . 67 × 10 - 9 . 5 . H is the average depth of the node, and d is the transmission distance. T b is the duration of one bit, which can be expressed as [20]
T b = M ′ S v
Here, M ′ is the size of the packet to be sent, S v is the data transmission rate, and a ( f ) is the absorption coefficient that depend on frequency [18,21]:
a f = 0 . 11 f 2 1 + f 2 + 44 f 2 4100 + f 2 + 2 . 75 × 10 - 4 f 2 + 0 . 003
where f is the transmission frequency of the signal in kHz and the absorption coefficient a ( f ) has the unit dB/m, and it is the frequency correlation coefficient. The determination of Equation (6) can be done based on Thorp’s model [22].

3. Energy-Efficient Coverage Control Using Memetic Algorithm

3.1. Problem Formulation

Assume that there are G monitoring events in the underwater monitoring area A, which can all be completely covered by the union of the sensing ranges of the N nodes. Then, the problem can be described as follows: after giving a set of nodes S = s 1 , s 2 , ⋯ , s N and an event set E = e 1 , e 2 , ⋯ , e G that can be covered by S, find the smallest subset of sensors S ′ so that E can be completely covered by S ′ . That is, if the perceived range of node s i is expressed as r s , and the smallest subset of nodes found is S ′ = s 1 , s 2 , ⋯ , s m , 1 ≤ m ≤ N , then S ′ must satisfy A ⊆ r 1 ⋃ r 2 ⋃ ⋯ ⋃ r m . This is a set-covering problem (SCP) of NP (Non-deterministic Polynomial) difficulty. In this study, SCP will be applied to node-optimization scheduling to solve the problems of energy efficiency and coverage, which can be described as follows:
M i n i m i z e : ∑ i ∈ N c i · q i
S u b j e c t t o : ∑ i ∈ N γ j i · q i ≥ 1 j ∈ G
where c i i ∈ N is the active cost of the ith node, and q i is a key decision variable, which is the focus of this study ( q i  = 1 indicates the node is active, and q i = 0 means the node is asleep). The objective function in Equation (7) describes the number of least active nodes. We assume that the active costs of each node are the same. For example, c i  = 1. The constraint in Equation (8) indicates that each monitoring event e i is covered by at least one node. When the network is in working condition, the optimization model described by Equations (7) and (8) is important, as it greatly improves the network energy efficiency and prolongs the lifetime of the network while guaranteeing coverage. The swarm intelligence optimization algorithm is a heuristic algorithm formed by simulating the laws of nature or biology [23,24]. Similar to a genetic algorithm, particle swarm algorithm, memetic algorithm (MA), or fish school algorithm [25,26,27], it has the characteristics of self-learning, self-organization, and self-adaptation, and it provides new optimization methods for UASNs. Based on this, we developed a swarm intelligence optimization algorithm that simulates the evolutionary mechanism of organisms through iterative computations and explores the optimal solution in the solution space. To solve the SCP problem, we propose an effective scheduling algorithm of coverage control (ESACC) and apply it to the UASN. ESACC includes two optimization strategies: (1) node sleep scheduling based on a memetic algorithm, which can suppress redundant nodes in UASNs; and (2) a node wake-up scheme to solve energy-saving coverage optimization problems in each round. In UASNs, a round is a basic unit of time. The ESACC is described below.

3.2. Node Sleep-Scheduling Mechanism Based on Memetic Algorithm

The Memetic algorithm was first proposed by Moscato in 1989, which consists of an individual-based local search and a population-based global search to solve large-scale combinatorial optimization problems [27,28]. The initial state of the population is generated randomly or in a specific way. The evolutionary process is operated by genetic algorithms including selection, crossover, and mutation. In ESACC, each individual represents a solution with a corresponding adaptability, which is given by the adaptive function. The adaptive function is used to evaluate the superiority of the solution. After completing the operation of the genetic algorithm, the local search further improves the superiority of the solution. In this way, a new batch of excellent individuals is generated, and the individuals in the new population are closer to the global optimal solution. Below, we describe the redundant node sleep-scheduling algorithm.

3.2.1. Coding Rule Design

The coding is a mapping from the problem space to the solution space. The genetic algorithm cannot directly process the solution data of the solution space. It must map the variables of the solution space into the data structure of the evolutionary space, i.e., the chromosome, before searching. In the coverage of UASNs, each chromosome represents a node-deployment scenario in which each gene describes the state of the node. In this study, the nodes in the UASNs are activated or asleep through proper scheduling to extend the network life cycle. For scheduling, we use binary 0 and 1 to represent the working state of the node (where 0 means sleep and 1 means a node is active).
As shown in Figure 2, there are 11 nodes that monitor 14 events, and some nodes are redundant (marked with solid lines). To achieve energy-saving optimization coverage, the optimal node-scheduling strategy is integrated into the ESACC so that the redundant nodes go to sleep. From the genetic coding point of view, we use the encoding format “10101010000” to represent the chromosome. N represents the length of the chromosome, whose size equals the number of nodes (N is 11). The gene A j represents the state of node s j in chromosome Q. In addition, because diversity during genetic evolution varies with population size, the selection of the population size is critical for ESACC. To simplify this work, based on the opinion of Trivedi et al. [29], the population size of each generation is fixed at 50.

3.2.2. Adaptive Function

An adaptive function is used to evaluate the degree of chromosomes. The goal of ESACC is to use the fewest nodes to achieve the best coverage. Therefore, in this study, the superiority of node scheduling is used as the adaptive function of ESACC. Using the perceptual coverage model described in Section 2.1, suppose the coverage vector of node s i is c o v i = γ i , 1 , γ i , 2 , ⋯ , γ i , G , and the coverage vector of the other node s j is c o v j = γ j , 1 , γ j , 2 , ⋯ , γ j , G , where i ≠ j . To determine whether an event is covered by a node, a Boolean operation is applied to the coverage vector by calculating the composite overlay vector of c o v i and c o v j :
Ψ s i , s j = γ i , 1 ∨ γ j , 1 , γ i , 2 ∨ γ j , 2 , ⋯ , γ i , G ∨ γ j , G
where Ψ represents the composite overlay vector, which is used to determine whether each event is covered by node s i and s j . Therefore, the composite overlay vector of chromosome k can be expressed as
Ψ k = A k 1 · c o v 1 ∨ A k 2 · c o v 2 ∨ ⋯ ∨ A k N · c o v N
Furthermore, the coverage of chromosome k can be expressed as
λ k = Ψ k 2 M
where Ψ k 2 represents the number of events covered by chromosome k. At this point, the utilization of the nodes in the network can be expressed as
η k = ∑ i = 1 N A k , i N
where ∑ i = 1 N A k , i indicates the number of nodes in the active state at the current time. The entire coverage-assessment process can be simplified to binary operations, greatly improving the performance of ESACC. From the aspect of evaluating the coverage of node-deployment algorithms, UASNs require the coverage of events to be as high as possible, and utilization of the nodes to be as low as possible. Therefore, we define an adaptive function F k to evaluate the advantages and disadvantages of chromosome k, and this is expressed as
F k = ξ 1 · λ k α - ξ 2 · η k β
In the equation, 0 ≤ λ k ≤ 1 and 0 ≤ η k ≤ 1 . ξ 1 and ξ 2 are the weight coefficients, whose values depend on the network designer’s comprehensive requirements for network performance indicators. α  and β are exponential factors whose role is to distinguish the size of each chromosome F k . The adaptive function F k is defined by Equation (13). It is a key factor affecting the performance of ESACC, and it includes four parameters: ξ 1 , ξ 2 , α and β . Coverage rate λ k and utilization η k are equally important indicators for evaluating UASNs, so we set ξ 1 = ξ 2 = 1 . α  = 3 and β  = 0.7 is based on our practical experience and repeated experiments. Figure 3 shows the trend of the adaptive function F k when α  = 3 and β  = 0.7. The higher is the coverage rate λ k , the larger is the value of F k , and the lower is the utilization rate of nodes η k , the larger is the value of F k , which accord with the design intention.

3.3. Algorithm Simulation and Analysis

3.3.1. Genetic Evolution

The selection operation selects good individuals from the current group, allowing them to breed the next generation as fathers. According to the above ESACC coding rules, the gene represents the status of the node: 1 indicates active, and 0 indicates sleep. The chromosomes with higher adaptability have better scheduling methods in the UASNs to handle the SCP problems, with a greater probability of being selected through the selection operation. This paper uses the roulette method, by which independent solutions are selected from a circle, and each individual’s probability of selection (reproduction probability) is proportional to its adaptability. The so-called reproduction probability is defined as
P i = f i ∕ ∑ j = 1 K f j
where f i is the adaptability of each individual a i , and k is the population size. Interleaving in genetic algorithms means that new individuals can be created. In ESACC, each gene represents the state of a network node. In the scheduling algorithm of network nodes, the state changes of nodes are unrelated. Therefore, this paper selects the random-point crossover method to reproduce. Mutation applies only to offspring individuals that have been born from two parents. In a genome set composed of all offspring individuals, the genome is selected for mutation with mutation probability P m . Mutation is an important flexible search operator, which can force the algorithm to search for new regions, thereby helping the genetic algorithm avoid premature convergence and resulting in a local optimal solution. In this paper, the mutation probability is the reciprocal of the length of the chromosome, which is theoretically proven to be optimal [27].

3.3.2. Local Search

To further improve the adaptability of the genetic algorithm to calculate the population, we propose a simple local search strategy that makes ESACC converge quickly. For the next generation, this strategy determines whether to keep the modification by modifying the value of each gene in the chromosome (changing the value of a gene from 1 to 0) and comparing it with the adaptability of the original chromosome. This gives us a better node-scheduling scheme than the original node. Population k is expressed as P o p k = u 1 , u 2 , ⋯ , u k , where u k is the kth group of chromosomes, and A i 1 , A i 2 , ⋯ , A i N is the gene sequence of chromosome i , where i ∈ 1 , k . The pseudo code of the local search strategy in ESACC is as follows in Algorithm 1.
Algorithm 1 Local search algorithm.
1: Calculate the adaptability f i t ( A i ) of chromosome u i ;
2: Statistics of index position g where gene A i j equals 1 in chromosome u i , j ∈ 1 , N , g ⊂ 1 , N ;
3: for t = 1 , 2 , ⋯, l e n g t h ( g ) do
4:  if f i t A i ′ > f i t A i then
5:    f i t A i = f i t A i ′ ;
6:   Keep the state of A i t ;
7:  else
8:    A i t = 1;
9:  end if
10: end for
11: Get the improved chromosome u i and repeat to obtain the optimal population P O P k .

3.4. Node Wake-Up Scheme

To achieve energy-saving coverage, we propose a node sleep-scheduling strategy based on a memetic algorithm. However, uncovered events will occur as certain nodes are gradually depleted of energy. Therefore, we propose a wake-up strategy to wake up some sleeping nodes for re-coverage. Assume that the power of the sink node of the network is sufficient to perform ESACC operations and wake-up schemes. Below, we describe the node wake-up scheme.
In UASNs, the node wake-up scheme runs in rounds, each of which includes clustering, scheduling, and data-transmission phases. In the clustering phase, nodes form several clusters through self-organizing and select one node in each cluster as the cluster head. The cluster head is responsible for forwarding messages received by the cluster node to the sink node. Then, it enters the scheduling phase. The UASNs applies a TDMA (Time Division Multiple Access) technique to accomplish communication in between the nodes and also their cluster head. Additionally, the cluster head has the ability to connect with the remote base station directly as well as accountable of forwarding the messages gotten from its cluster nodes to the base station. The head node will set up a TDMA timetable as well as send it to its cluster nodes. The cluster nodes could utilize the TDMA timetable to arrange the time slots for every node. Specifically, a TDMA frame consists of a fixed number of time slots, which equals the number of nodes in the cluster. The first time slot of each frame is reserved for the cluster head. After the inter-cluster communication link is established, it enters the data-transmission phase and the cluster members are designated to send data in their respective time slots. Compared with radio channels, the propagation delay of underwater channels is large. Therefore, the guard interval between slots should be set large enough to ensure that the cluster head has completed the reception of the current slot data before the data of the next slot arrives. In the entire network, the length of each frame period is uniform, which determines the interval between two consecutive transmissions. Since the guard interval may be long, the number of cluster members should not be excessive. Figure 4 shows a slot diagram of a TDMA frame period. After completing the data collection, it will enter the next round, re-elect a cluster head, and re-dispatch.
According to the node sleep-scheduling scheme, some nodes enter the sleep mode, and the rest are responsible for event monitoring. When the sink node receives a signal from a dead node, i.e., the energy of a certain node is about to run out, the wake-up scheme will wake some of the nodes in the next round. Assume that the energy of node n i is about to be exhausted ( E n i < E t h ). If node n i is active, then the original composite coverage vector of all nodes is c n i Δ . If node n i is dead, then the original composite coverage vector of all nodes is c n i ∇ . Then, according to the Boolean operation, the vector c u n c n i that can be obtained by an uncovered event can be expressed as
c u n c n i = c n i Δ ⊕ c n i ∇
where ⊕ denotes an exclusive-OR operation in Boolean operations; if o p t c o m represents an optimal scheduling combination when node n i runs out, then the pseudo code of the node wake-up scheme is described as follows in Algorithm 2.
Algorithm 2 Stud Crossover (SC) Operator
1: if E n i < E t h then
2:  Find the neighbor node of n i , u i
   u i = n j ∈ C d n i , n j < r s , i ≠ j , j ∈ 1 , N ;
3:  Find ρ , which is the number of nonempty subsets Y of the neighbor node u i
   Y = Y p ∀ n * ∈ Y p , ∃ n * ∈ u i , ρ = 2 l e n g t h u i - 1 ;
4:  for j = 1 , 2 , ⋯, ρ do
5:   for k = 1 , 2 ,⋯, length( Y j ) do
6:     c cov Y k = c n Y j k ⋃ c cov Y k ;
7:   end for
8:    V a l u e = c cov Y k   &   c u n c n i ;
9:   if ∑ 1 ∈ V a l u e 1 > o p t v a l then
10:     o p t v a l = Y j ;
11:   end if
12:   end for
    o p t c o m ;
13: end if
The main goal of the wake-up scheme is to generate an optimal scheduling combination to wake a node from sleep state by sending a wake-up signal to the neighbor node of the dead node. At the beginning of the next round, the sink wakes up some nodes according to the wake-up scheme. If a node dies again, then the wake-up scheme will reevaluate the coverage and decide to wake some other nodes to resume uncovered events.

3.5. Network Reconfiguration Mechanism

In actual situations, the events monitored by the sensor network may be relatively static or dynamic. For example, in the investigation of mineral resources on the seabed, events are stationary. Conversely, in marine water-quality monitoring, incidents to be monitored, i.e., pollutants, may drift along with the movement of seawater; in a dynamically changing situation, the sensor network and the events to be monitored are likely to be constantly changing. However, it costs too much for a node to update the event information every moment to perform intelligent processing or tracking. Therefore, it is necessary to reanalyze the node coverage after a certain period. We divide each round into decision-making and operational phases. The decision-making phase reevaluates the monitoring of events. In the operation phase, all nodes follow the ESACC plan according to the evaluation results in the decision-making phase until the end of the round. Figure 5 shows the flowchart of the network-reconfiguration mechanism.

4. Performance Evaluations

We evaluated the performance of the proposed ESACC scheme through extensive simulation tests. Assume a UASN contains preset numbers of nodes and events. Each node is static after a random or scheduled deployment, and the event may be affected by the flow of water. We verified the convergence of ESACC and display the experimental results.

4.1. Convergence of the ESACC

To prove the fast convergence characteristics of ESACC, under the same condition, we assessed the computational time and fitness of ESACC in UASNs of different sizes and compared it with the results of genetic algorithm (GA) [30]. We randomly deployed 64 events in 3D monitoring waters with a length, width and height of 100 m. The number of nodes deployed ranged between 50 and 500. No matter the number of sensor nodes deployed, the node’s perceived radius was 30 m. Every experiment was repeated 30 times.
In general, due to the evolutionary constraints of GA, it requires more generations to generate optimal solutions. However, with the use of additional local search schemes, ESACC is able to generate optimal solutions in fewer generations. Assume that both ESACC and GA use the same criteria to prevent evolution, and when the fitness of the best chromosome is above a predetermined threshold, the evolutionary process is terminated. Based on our previous experimental studies to determine fitness thresholds for different network sizes, we found that, based on experimental results, ESACC is highly adaptable around the second generation. Moreover, we also recorded the timestamp and fitness of the GA. Then, we compared the calculation time of ESACC with the calculation time of GA under different fitness values. The statistic results of experiments are as follows in Table 1.
It is worth noting that the computing platform is Intel (R) Core (TM) i7-3770 CPU @ 3.40 GHz, 8 GB memory. Table 1 plainly shows that the ESACC could offer an optimum schedule for nodes that is much better compared to that of GA. We could see that, with the same fitness, ESACC takes lower computing time to generate solutions with far better fitness compared to that in GA. As the network grows in size, the advantages of ESACC become more apparent. This is because the SCP becomes more complex as the number of nodes and events deployed increases. When it comes to network with 450 nodes, the computing time for the ESACC at a fitness value of 0.86 is 12.10 s, 81.6% faster than GA. In all other cases, the proposed ESACC is also able to achieve higher fitness and use less time. In summary, because the nodes deployed in the UASNs become more dense, the convergence and fitness generated by the ESACC is better than that in GA.
Next, we tested the impact of changes in the number of nodes and sensing radius r s on ESACC performance. Figure 6 and Figure 7 show the effect of the sensing radius r s from 20 m to 70 m and the number of nodes from 50 to 500 on ESACC performance (fitness value and minimum number of node subsets) when nodes are randomly distributed in the 3D water environment monitoring area. It can be seen in Figure 6 that, as the sensing radius r s or the number of nodes increases, the fitness value increases, which is mainly because, as the sensing radius r s or the number of nodes increases, the union of the sensing ranges of nodes in the network increases. As a result, the network coverage is also increased. From another perspective, the number of redundant nodes in the network also increases, and the number of nodes that need to sleep will become more and more, which will reduce the node utilization. This shows that the fitness function proposed in this paper can effectively evaluate network performance.
Figure 7 depicts the change trend of the number of nodes in the minimum set of nodes as the number of nodes changes and the sensing radius r s of the nodes changes. It is easy to be seen that, as the sensing radius r s or the number of nodes increases, the number of nodes in the minimum set of nodes decreases. This is mainly because, as the sensing radius r s or the number of nodes increases, the number of redundant nodes in the network increases, and the number of nodes that need to sleep also increases. In summary, experiments show that ESACC can effectively reduce the number of active nodes and reduce node utilization based on network status.

4.2. Algorithm Simulation and Analysis

We used MATLAB for simulation. To eliminate the randomness of the experiment, the final result was taken as the average of 30 experiments. Assuming that the three-dimensional monitoring water area is 200 m in each dimension, the sink node is located at the center of the water surface, and 64 events are to be monitored. Each node has the same initial energy, and all nodes are assumed to be homogeneous. Table 2 shows the meanings and values of simulation parameters.
We now demonstrate ESACC’s performance evaluation results in extending the life cycle and maintaining coverage of UASNs. ESACC was applied to the sink node. By controlling the sleep or active state of the node, the node energy can be fully utilized while maintaining efficient coverage of the event. Assume that the sink node has enough power to schedule every node in the network. When a node’s energy is below a critical value, the ESACC wake-up scheme can determine which neighbor must be awakened to recover uncovered events.Therefore, the network coverage, average remaining energy of network nodes, and network runtime need to be considered simultaneously.
To compare the performance of the ESACC with those of LEACH-Coverage-U [11] and CMSS algorithm [6] (the CMSS algorithm is a typical algorithm for extending the network lifetime through sleeping scheduling), the network parameter settings mentioned above were used for simulation. It should be noted that all experimental designs here are based on the idea of clustering.
Figure 8 and Figure 9 show the comparison of the network lifetimes of the above three algorithms. Figure 8 is a comparison of the network lifetime of the ESACC algorithm with the CMSS and the LEACH-Coverage-U algorithm when the number of events is fixed at 64, the node sensing radius r s is fixed at 20 m, and the number of nodes varies from 125 to 1000. As can be seen in the figure, in terms of average network lifetime, the ESACC algorithm is 951.8∼2028.9% better than EACH-Coverage-U and 12.2∼57.6% better than CMSS. Figure 9 is a comparison of the network lifetime of the ESACC algorithm with the CMSS and LEACH-Coverage-U algorithm when the number of events is fixed at 64, the number of nodes is fixed at 343 , and the node sensing radius r s varies from 15 to 40. It is easy to find that the proposed ESACC algorithm is 1294.1∼1958.9% better than EACH-Coverage-U, and 24.3∼40.9% better than CMSS. Obviously, the proposed ESACC algorithm shows good performance compared to other existing methods.
Figure 10 is a comparison of the network coverage of the ESACC algorithm and the CMSS and LEACH-Coverage-U algorithms with the change of rounds in the network when the number of nodes is fixed at 512, the node sensing radius r s 20 m, and the event 64. It can be seen that, when the number of running rounds is the same, the network coverage rate of the LEACH-Coverage-U algorithm is significantly lower than that of ESACC and CMSS. Because it does not apply a node scheduling strategy, this leads to a large number of nodes dying prematurely, which in turn leads to an increase in network vulnerabilities. CMSS and ESACC not only consider network coverage, but also consider the sleep and wake-up mechanisms of redundant nodes. Compared to the CMSS, ESACC can maintain 97% high coverage over a long period of time (from the initial time until 1327 rounds) in its lifetime (3269 rounds). This is because the ESACC algorithm improves the efficiency of network scheduling and reduces the energy loss caused by frequent communication between nodes in the network, so that more nodes with sufficient energy participate in network monitoring tasks, thereby improving network service quality.
Figure 11 is a comparison of the average remaining energy of the network nodes of the ESACC algorithm with CMSS and LEACH-Coverage-U with the change of rounds in the network when the number of nodes fixed at 512, the node sensing radius 20 m, and the number of events 64. It can be seen that, when the number of running rounds is the same, compared with the LEACH-Coverage-U algorithm, the network nodes of CMSS and ESACC have a lower energy gradient and a higher energy utilization rate. This is mainly because the CMSS and ESACC algorithms optimize the network structure, close redundant nodes, and reduce the overall energy consumption of the network. At the same time, ESACC shows better energy utilization than CMSS. This is because, when a dead node appears in the network, based on the minimum set of nodes, the ESACC algorithm seeks the optimal combination by waking up the neighbor nodes of the dead node, making up for the lack of node death, and making the energy consumption of the network balanced, thereby extending the network lifetime.

5. Conclusions

A UASN is different from a wireless sensor network on land. It must account for the particularity of the underwater acoustic environment, and it requires greater energy efficiency. Therefore, this paper proposes an energy-saving coverage-scheduling algorithm called ESACC. A memetic algorithm is used to implement the sleep scheduling of redundant nodes, which simplifies the network topology and reduces the network energy consumption. A wake-up scheme is also established. The use of some dormant redundant nodes in the network to replace nodes that are about to die due to energy exhaustion maintains high network coverage. The algorithm uses a sleep–wake strategy to reduce network energy consumption and extend the network life cycle while maintaining high coverage. Simulation results show that, compared with the CMSS and LEACH-Coverage-U algorithms, ESACC can close redundant nodes and maintain UASN operation with the minimum number of active nodes. When a node’s energy is close to critical, it can wake up a sleeping node to maintain high coverage. Next, applying ESACC to energy-saving deployment in UASNs is an important aim of future work.

Author Contributions

H.W. and Y.L. conceived and designed the whole procedure of this paper. T.C. contributed to the Introduction and System Model Sections. S.C. performed the computer simulation and analyzed the results.

Funding

This research was supported by the National Natural Science Foundation of China (61571250), Zhejiang Natural Science Foundation (LY18F010010), Key Laboratory of Mobile Network Application Technology of Zhejiang Province, and K. C. Wong Magna Fund of Ningbo University. Youth Project of Ningde Normal University (2017Q105,JG2018012), School Innovation Team of the Ningde Normal University (2015T011) and project of the Fujian Provincial Natural Science Fund (2017I0016, 2017J01775 ).

Acknowledgments

The authors would like to express their gratitude to Youming Li and Shengming Chang from Ningbo University for their experimental help. At the same time, they would like to thank Joeair Jiang and Chiapang Chen from Taiwan University for their creative ideas. Their professionalism is critical to completing the research.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Pompili, D.; Akyildiz, I.F. Overview of networking protocols for underwater wireless communications. IEEE Commun. Mag. 2009, 7, 97–102. [Google Scholar] [CrossRef]
  2. Zheng, P. Effcient and Robust Underwater Sensor Network Systems: Design, Implementation and Experiments. Ph.D. Dissertation, University of Connecticut, Storrs, CT, USA, 2012. [Google Scholar]
  3. Akyildiz, I.F.; Pompili, D.; Melodia, T. Underwater acoustic sensor networks: Research challenges. Ad Hoc Netw. 2005, 3, 257–279. [Google Scholar] [CrossRef]
  4. Cui, J.H.; Kong, J.; Gerla, M.; Zhou, S. The challenges of building mobile underwater wireless networks for aquatic applications. IEEE Netw. 2006, 20, 12–18. [Google Scholar]
  5. Liu, F.; Tsui, C.Y.; Zhang, Y.J. Joint Routing and Sleep Scheduling for Lifetime Maximization of Wireless Sensor Networks. IEEE Trans. Wirel. Commun. 2010, 9, 2258–2267. [Google Scholar] [CrossRef] [Green Version]
  6. Danratchadakorn, C.; Pornavalai, C. Coverage maximization with sleep scheduling for wireless sensor networks. In Proceedings of the IEEE International Conference on Electrical Engineering/electronics, Computer, Telecommunications and Information Technology, Hua Hin, Thailand, 24–27 June 2015; pp. 1–6. [Google Scholar]
  7. Zhao, Y.; Wu, J.; Li, F.; Lu, S. On Maximizing the Lifetime of Wireless Sensor Networks Using Virtual Backbone Scheduling. IEEE Trans. Parallel Distrib. Syst. 2012, 23, 1528–1535. [Google Scholar] [CrossRef]
  8. Lin, C.C.; Deng, D.J.; Wang, S.B. Extending the Lifetime of Dynamic Underwater Acoustic Sensor Networks Using Multi-Population Harmony Search Algorithm. IEEE Sens. J. 2016, 16, 4034–4042. [Google Scholar] [CrossRef]
  9. Wang, C.; Lin, H.; Jiang, H. CANS: A Congestion-Adaptive WSN-Assisted Emergency Navigation Algorithm with Small Stretch. IEEE Trans. Mob. Comput. 2016, 15, 1077–1089. [Google Scholar] [CrossRef]
  10. Fan, X.; Chen, Q.; Che, Z.; Hao, X. Energy-Efficient Probabilistic Barrier Construction in Directional Sensor Networks. IEEE Sens. J. 2017, 17, 897–908. [Google Scholar] [CrossRef]
  11. Tsai, Y. Coverage-preserving routing protocols for randomly distributed wireless sensor networks. IEEE Trans. Wirel. Commun. 2007, 6, 1240–1245. [Google Scholar] [CrossRef]
  12. Ogundile, O.O.; Alfa, A.S. A Survey on an Energy-Efficient and Energy-Balanced Routing Protocol for Wireless Sensor Networks. Sensors 2017, 17, 1084. [Google Scholar] [CrossRef] [PubMed]
  13. Fariborzi, H.; Moghavvemi, M. EAMTR: Energy aware multi-tree routing for wireless sensor networks. IET Commun. 2009, 3, 733–739. [Google Scholar] [CrossRef]
  14. Zhang, R.; Labrador, M.A. Energy-aware topology control in heterogeneous wireless multi-hop networks. In Proceedings of the International Symposium on Wireless Pervasive Computing, San Juan, PR, USA, 5–7 February 2007. [Google Scholar]
  15. Kar, K.; Kodialam, M.; Lakshman, T.V.; Tassiulas, L. Routing for network capacity maximization in energy-constrained ad hoc networks. In Proceedings of the 22th Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, CA, USA, 30 March–3 April 2003; pp. 1–9. [Google Scholar]
  16. Zhang, B.; Zhao, Z.; Ma, J.; Mouftah, H.T. Efficient Localized Topology Control Algorithm. In Proceedings of the 2007 Workshop on High PERFORMANCE Switching & Routing, Brooklyn, NY, USA, 30 May–1 June 2007; pp. 1–6. [Google Scholar]
  17. Jiang, P.; Liu, J.; Feng, W.; Wang, J.; Xue, A. Node Deployment Algorithm for Underwater Sensor Networks Based on Connected Dominating Set. Sensors 2016, 16, 388. [Google Scholar] [CrossRef] [PubMed]
  18. Sozer, E.M.; Stojanovic, M.; Proakis, J.G. Underwater acoustic networks. IEEE J. Ocean. Eng. 2000, 25, 72–83. [Google Scholar] [CrossRef]
  19. Zhao, L.; Liang, Q. Optimum cluster size for underwater acoustic sensor networks. In Proceedings of the IEEE Conference on Military Communications, Washington, DC, USA, 23–25 October 2006; IEEE Press: Washington, DC, USA, 2006; pp. 1218–1222. [Google Scholar]
  20. Jiang, P.; Liu, J.; Wu, F. Node non-uniform deployment based on clustering algorithm for underwater sensor networks. Sensors 2015, 15, 29997–30010. [Google Scholar] [CrossRef] [PubMed]
  21. Stojanovic, M. On the Relationship Between Capacity and Distance in an Underwater Acoustic Channel. ACM Sigmob. Mob. Comput. Commun. Rev. 2007, 11, 34–43. [Google Scholar] [CrossRef]
  22. Berkhovskikh, L.; Lysanov, Y. Fundamentals of Ocean Acoustics; Springer: New York, NY, USA, 1982. [Google Scholar]
  23. Ganesan, T.; Elamvazuthi, I.; Shaari, K.Z.K.; Vasant, P. Swarm intelligence and gravitational search algorithm for multi-objective optimization of synthesis gas production. Appl. Energy 2013, 103, 368–374. [Google Scholar] [CrossRef]
  24. Ting, C.K.; Liao, C.C. A memetic algorithm for extending wireless sensor network lifetime. Inf. Sci. 2010, 180, 4818–4833. [Google Scholar] [CrossRef]
  25. Neshat, M.; Sepidnam, G.; Sargolzaei, M.; Toosi, A.N. Artificial fish swarm algorithm: A survey of the state-of-the-art, hybridization, combinatorial and indicative applications. Artif. Intell. Rev. 2014, 42, 965–997. [Google Scholar] [CrossRef]
  26. Du, H.; Na, X.; Rong, Z. Particle Swarm Inspired Underwater Sensor Self-Deployment. Sensors 2014, 14, 15262–15281. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  27. Liao, C.C.; Ting, C.K. A Novel Integer-Coded Memetic Algorithm for the Set k-Cover Problem in Wireless Sensor Networks. IEEE Trans. Cybern. 2018, 48, 2245–2258. [Google Scholar] [CrossRef] [PubMed]
  28. Moscato, P. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms; Caltech Concurrent Computation Program, C3P Report 826 (1989); California Institute of Technology: Pasadena, CA, USA, 1989. [Google Scholar]
  29. Trivedi, A.; Srinivasan, D.; Sanyal, K.; Ghosh, A. A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition. IEEE Trans. Evolut. Comput. 2017, 21, 440–462. [Google Scholar] [CrossRef]
  30. Zhang, Y.; Zhou, Z.; Zhao, D.; Sun, Y.; Xue, X. A Genetic Algorithm Based Mechanism for Scheduling Mobile Sensors in Hybrid WSNs Applications. In Wireless Algorithms, Systems, and Applications (WASA 2017); Ma, L., Khreishah, A., Zhang, Y., Yan, M., Eds.; Lecture Notes in Computer Science; Springer: Cham, Germany, 2017; Volume 10251, pp. 220–231. [Google Scholar]
Sensors 18 02512 g001 550
Figure 1. Three-dimensional underwater acoustic sensor network structure.
Figure 1. Three-dimensional underwater acoustic sensor network structure.
Sensors 18 02512 g001
Sensors 18 02512 g002 550
Figure 2. Coding rule design.
Figure 2. Coding rule design.
Sensors 18 02512 g002
Sensors 18 02512 g003 550
Figure 3. Relationship between values of F k , α and β .
Figure 3. Relationship between values of F k , α and β .
Sensors 18 02512 g003
Sensors 18 02512 g004 550
Figure 4. Time slot diagram of a TDMA frame period.
Figure 4. Time slot diagram of a TDMA frame period.
Sensors 18 02512 g004
Sensors 18 02512 g005 550
Figure 5. Network reconfiguration mechanism flow chart.
Figure 5. Network reconfiguration mechanism flow chart.
Sensors 18 02512 g005
Sensors 18 02512 g006 550
Figure 6. The change trend of the fitness function when the number of nodes changes and the node sensing radius r s changes.
Figure 6. The change trend of the fitness function when the number of nodes changes and the node sensing radius r s changes.
Sensors 18 02512 g006
Sensors 18 02512 g007 550
Figure 7. The change trend of the number of nodes in the minimum node set when the number of nodes changes and the node sensing radius changes.
Figure 7. The change trend of the number of nodes in the minimum node set when the number of nodes changes and the node sensing radius changes.
Sensors 18 02512 g007
Sensors 18 02512 g008 550
Figure 8. Relationship between network lifetime and number of nodes.
Figure 8. Relationship between network lifetime and number of nodes.
Sensors 18 02512 g008
Sensors 18 02512 g009 550
Figure 9. Relationship between network lifetime and sensing radius r s .
Figure 9. Relationship between network lifetime and sensing radius r s .
Sensors 18 02512 g009
Sensors 18 02512 g010 550
Figure 10. Relationship between network coverage and running rounds.
Figure 10. Relationship between network coverage and running rounds.
Sensors 18 02512 g010
Sensors 18 02512 g011 550
Figure 11. Average residual energy of network nodes.
Figure 11. Average residual energy of network nodes.
Sensors 18 02512 g011
Table
Table 1. The statistic results of experiments. Each experiment was repeated 30 times to compare the average computation time (seconds) between ESACC and GA at different fitness values.
Table 1. The statistic results of experiments. Each experiment was repeated 30 times to compare the average computation time (seconds) between ESACC and GA at different fitness values.
NumberFitnessESACCStd.GAStd.NumberFitnessESACCStd.GAStd.
500.620.350.080.090.021500.793.030.078.533.54
500.580.260.070.070.021500.751.490.054.282.24
500.370.010.010.010.011500.360.030.010.050.01
2500.824.70.1131.1616.523500.858.910.2152.6425.36
2500.813.910.1118.5610.233500.837.370.2040.5221.23
2500.350.050.010.090.013500.340.070.010.120.02
4500.8716.610.2874.5236.145500.8820.070.21118.1155.21
4500.8612.100.2768.4833.745500.8718.010.30100.1152.62
4500.340.090.010.150.015500.340.120.010.190.02
Table
Table 2. Simulation scenarios and parameters.
Table 2. Simulation scenarios and parameters.
ParameterValueParameterValue
Initial energy of node E O 1000 JNode energy threshold E t h 10 J
Carrier frequency f25 kHzPacket size M ′ 1 kbit
Node sensing radius R s 30 mCircuit energy consumption to process one bit of information E e l e c 50 nJ/bit
Average depth H100 mData transmission rate S v 5 kbps

Share and Cite

MDPI and ACS Style

Wang, H.; Li, Y.; Chang, T.; Chang, S. An Effective Scheduling Algorithm for Coverage Control in Underwater Acoustic Sensor Network. Sensors 2018, 18, 2512. https://doi.org/10.3390/s18082512

AMA Style

Wang H, Li Y, Chang T, Chang S. An Effective Scheduling Algorithm for Coverage Control in Underwater Acoustic Sensor Network. Sensors. 2018; 18(8):2512. https://doi.org/10.3390/s18082512

Chicago/Turabian Style

Wang, Hui, Youming Li, Tingcheng Chang, and Shengming Chang. 2018. "An Effective Scheduling Algorithm for Coverage Control in Underwater Acoustic Sensor Network" Sensors 18, no. 8: 2512. https://doi.org/10.3390/s18082512

APA Style

Wang, H., Li, Y., Chang, T., & Chang, S. (2018). An Effective Scheduling Algorithm for Coverage Control in Underwater Acoustic Sensor Network. Sensors, 18(8), 2512. https://doi.org/10.3390/s18082512

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop