DYNAMIC coverage in underwater environment is one of the enabling technologies for the development of future ocean-observation systems. In a spatially-large underwater environment,there exist a number of points of interest which cannot be fully covered by any static configuration of the sensors (possibly due to the small sensing range as compared to the dimension of the environment). The goal is then to plan the motion of the mobile nodes,i.e.,dynamic coverage,in order to minimize uncertainty and maintain an up-to-date knowledge of the state of the points of interest in the environment. Applications of underwater dynamic coverage range from oil industry to aquaculture,and include instrument monitoring,pollution controlling,climate recording, natural disturbances predicting,missions search and survey,and marine life studying reference ^{[1, 2, 3]}.

Due to the sparse property in the underwater environment,most of the underwater dynamic coverage strategies adopt mobile sensor nodes to achieve the coverage task,which has been widely researched. Reference ^[4] proposed a high-speed AUV-based silent localization algorithm for underwater sensor networks. In order to stabilize the dynamic coverage ,a dynamic coverage strategy was presented to adapt the velocity of mobile nodes along a predefined trajectory in ^{[5, 6]}. In addition,Huang et al.^[7] designed a novel direction-steerable three-dimensional directional sensor model,and detailedly analyzed the sensory ability of three-dimensional directional sensor based on probability model. Based on this,Xia et al.^[8] developed a rigidity driven moving strategy for mobile sensors. In these papers given above,a large number of underwater mobile nodes were required to monitor the underwater environment. However,these underwater mobile nodes are very expensive due to the more complex underwater transceivers and to the hardware protection needed in the extreme underwater environment. {% Therefore,how to achieve the dynamic coverage with a small number of mobile nodes becomes a new issue. }On the other hand,the power needed for underwater communications is higher than in terrestrial radio communications due to longer distances and more complex signal processing at the receivers to compensate for the impairments of the channel^[9]. Based on this,how to save the underwater communication energy becomes a new issue. Normally,the so-called neighbor rule is widely used to illustrate the topology relationship of sensor nodes (SNs). Analyzing the network topology with neighbor rule reveals that many interactions between sensors are redundant. The redundancy sometimes makes the communication complex and inefficient. References ^{[10, 11]} introduced rigid graph based topology optimization to reduce the communication energy for wireless sensor network. However,it is still unknown whether it would reduce or not and how the rigid graph based optimization can improve the dynamic coverage performance in the underwater environment. In addition,in most existing sensor and actor networks,the authors mainly designed strategies to enhance the coverage performance while ignoring connectivity. For example,a distributed actor deployment algorithm is designed in ^[12],in which the approach applied repelling forces between neighboring actors and from the sensors that sat on the boundaries in order to spread them in the region. In addition,Zamanifar et al.^[13] put forward a distributed,proactive algorithm to restore actor-to-actor connectivity of wireless sensor and actor networks (WSANs) that minimized time of reconnecting the network and also total required movements of actors. But it cannot be applied to the underwater environment. Reference ^[14] proposed deployment strategies for two-dimensional and three-dimensional communication architectures for underwater acoustic sensor networks. However,the underwater environment has a spare property. Thus,the performance improvement of coverage is also at the expense of connectivity reduction. Therefore,it is required to design a strategy where the performance of coverage and connectivity can both be guaranteed.

Motivated by above consideration,we design a dynamic coverage with WSANs in underwater environment,where both connectivity and coverage are considered. WSANs are composed of a large number of SNs and multiple mobile actor nodes (ANs). The roles of SNs and ANs are to collect data from the environment and perform corresponding actions based on the collected data,respectively. Compared with traditional static wireless sensor networks,WSANs not only have the capacity of monitoring the environment,but also can make decisions based on the observations and perform corresponding actions. On the other hand,only a small number of mobile ANs are used in WSANs,and then it is more economical compared with mobile sensor networks. A min-weighted rigid graph based topology optimization scheme is first provided to reduce the redundancy of communication links in underwater environment,and then a dynamic coverage strategy is proposed for underwater WSAN to achieve the dynamic coverage task. The main contributions of this paper are twofold.

1) To optimize the topology of underwater WSANs,a min-weighted rigid graph is used,such that the number of communication links and energy dissipations can be reduced.

2) Under the optimized topology and fluid motions,a dynamic coverage strategy is proposed for SNs and ANs in underwater environment,such that the coverage rate can be improved.

The organization of the paper is given as follows. In Section II,problem formulation for underwater WSANs is described. Main results are presented in Section III. Section IV presents simulation to validate the proposed approach. Finally,conclusion and future work are presented in Section V.

In this paper,the topology relationship of underwater WSANs is represented by an undirected graph $\mathcal{G=(V},\mathcal{E},\mathcal{A)}$,where $% \mathcal{V=S\cup R}$ and $\mathcal{E}\subseteq \mathcal{V\times V}$. In addition,the SNs and ANs are denoted by $\mathcal{S}=\{ s_{1},s_{2},\ldots ,s_{c}\} $ and $\mathcal{R}=\{ s_{c+1}$, $s_{c+2}$,$\ldots ,s_{n}\} ,$ respectively. The roles of SNs and ANs are to collect data from the environment and perform corresponding actions to the collected data,respectively. A graph is defined to be undirected if edge $(i,j)\in \mathcal{E}$ and edge $(j,i)\in \mathcal{E}$. Adjacency matrix $\mathcal{A=}$ $[a_{ij}] $ ($(i,j)\in \mathcal{E} $,$a_{ii}=a_{jj}=0$,$a_{ij}=a_{ji}$) stands for the corresponding relations between the vertices and edges in the undirected graph. Next,some basic concepts in graph theory are introduced.

A graph is defined to be rigid if the corresponding set of distance constraints is sufficient to maintain the formation shape,i.e.,a graph is rigid provided that all prescribed distance constraints between nodes are satisfied during a continuous rotation. Otherwise,it is called flexible. A minimally rigid graph is a rigid graph where no edge can be removed without losing rigidity.

Given a network framework $\mathcal{G=(V},\mathcal{E},\mathcal{A)}$ with $n$ vertices,positions $h_{i}\in {\bf R} ^{3}$ and $i\in \mathcal{V},$ if $\forall\, (i,j)$ $\in \mathcal{E}$ satisfies $\|h_{i}-h_{j}\|$ $=$ $\Upsilon >0$,and $% (h_{i}-h_{j})^{\rm T}(\dot{h}_{i}-\dot{h}_{j})=0$ at the initial rotation time ($t\geq 0$),we say that $\dot{h}=(\dot{h}_{1},\dot{h}_{2},\ldots,\dot{h}% _{n})$ is an infinitesimal flex. An infinitesimal flex is trivial if it results from a rigid motion of the framework. A framework is said to be infinitesimally rigid if it only has trivial infinitesimal flex. The infinitesimal rigidity of a framework is a sticker condition than rigidity,where all infinitesimally rigid networks are rigid. Specially,the rigidity matrix $\mathcal{M}$ is defined as an $\vert \mathcal{E}\vert \times 3\vert \mathcal{V}\vert $ matrix

The following propositions are used in the design of underwater optimization topology.

Proposition 1 ^{[11, 15, 16]} $\mathcal{M}$ is a rigidity matrix of a general structure with $n$ vertices $\left( n>3\right) $ in three-dimensional environment. Then,this structure is infinitesimal rigid if and only if rank$\left( \mathcal{M}\right) =3n-6$.

Proposition 2^{[11, 15, 16]} An infinitesimal rigid belongs to rigid.

Remark 1. With Propositions 1 and 2,it can be easily obtained that: if an undirected graph in three-dimensional is an infinitesimal rigid and the number of edges it contains is $3n-6$,then the undirected graph is minimally rigid graph.

the coverage problem in underwater environment. Generally,network coverage problems can be categorized into static and dynamic ones. This paper mainly investigates the dynamic coverage problem by considering the complex dynamic environment of water,where nodes (including sensor and actor nodes) can move passively with fluid motions. As we know,the water is a stratified, rotating fluid. For simplicity,similar to $^[17]$,it is assumed that the nodes move passively on horizontal surfaces,while neglecting the vertical movement. Next,we consider the condition of ordinary water circulation.

According to the continuous equation of fluid motion $\frac{\partial \rho}{\partial t}+\bigtriangledown \cdot ( \rho V^{\prime }) =0$, where $\frac{\partial \rho}{\partial t}$ is micelle fluid density and $\rho >0$ is a constant,we can obtain the continuous motion equation of incompressible flow field : $\bigtriangledown \cdot V^{\prime }=0$. The incompressible flow field is a uniform flow, which is defined as a uniform flow when the velocity and other hydrodynamic parameters do not change from point to point in the flow field. In this paper,it is assumed that the given underwater area is an ideally incompressible fluid. Based on this,the flow of water can be described by a Lagrange stream function $\varphi $,and the stream function $\varphi $ contains two different directions of the velocity field $% V^{\prime }\equiv ( u,v) $,wherein $u=\frac{\partial \varphi}{\partial y}$ and $v=-\frac{\partial \varphi}{\partial x}$\ denote\ the east and north velocity fields,respectively. Now,we introduce the stream function $% \varphi $.

When the trajectories of particles are in a steady flow,the stream function $\varphi $ can be used to plot streamlines. Streamlines are perpendicular to equipotential lines. Then the continuity equations in Cartesian coordinates are given by $\frac{\partial v}{\partial y}+\frac{\partial u}{\partial x}=0.$ In order to describe the underwater environment,the following stream function model $% ^[18]$ is used for the basic meandering jet,i.e.,

In this section,we first provide a min-weighted rigid graph to optimize the topology of underwater WSANs. With the optimized topology and fluid motions, a dynamic coverage strategy is proposed for SNs and ANs in underwater environment.

A. Topology Optimization Based on Min-weighted Rigid Graph

The main process of generating the min-weighted rigid graph is divided into two steps: 1) Generate the local min-weighted rigid graph for each vertex; 2) Delete the edges that do not belong to global min-weighted rigid graph. Detailed steps are given in Algorithm 1.

1. Input: the positions of sensor and actor nodes

2. for $i=1$ to $\left\vert \mathcal{S}\right\vert $ do

3.      earch the set of neighbor nodes $\mathcal{N}_{i}$,and calculate the number of neighbor nodes $\left\vert \mathcal{N}_{i}\right\vert $

4.      for $i=1$ to $\left\vert \mathcal{S}\right\vert +\left\vert \mathcal{R}\right\vert $ do

5.             Calculate the length of all the neighbor edges $e_{ij}$

6.             Sequence all the edges in the ascending order

7.             Establish a stiffness matrix and initialize $\mathcal{M}_{i}=\mathcal{M}% _{i}^{\bigtriangleup }\left( 1\right) $

8.      S      S if rank($\mathcal{M}_{i}$) $\leq 3\left( \left\vert \mathcal{N}_{i}\right\vert +1\right) -6$

9.                  S$\mathcal{M}_{i}=\left[ \begin{array}{c} \mathcal{M}_{i} \\ \mathcal{M}_{i}^{\bigtriangleup }\left( j+1\text{,}:\right)% \end{array}% \right] $

10.            else if $\mathcal{M}_{i}$ is full rank then

11.                  SAccording to $\mathcal{M}_{i}$,record the edge $e'_{ij}$

12.            end if

13.      end for

14.      for $j=\left\{ i\text{,}\mathcal{N}_{i}\right\} $

15.            for $k=\left\{ i\text{,}\mathcal{N}_{i}\text{,}k\neq l\right\} $

16.                  if $\left( l\text{,}k\right) \notin e'_{ij}$

17.                         Delete $\left( l\text{,}k\right)$

18.                   end if

19.            end for

20.       end for

21. end for

22. Output: the position of all sensor and actor nodes, meanwhile show the minimum weighted dynamic covering strategy graph

23. Call Algorithm 2.

In the following,we define the length of communication edge as the weighted value. Then,the weighted value in Fig. 1 (a),Fig. 1 (b) and Fig. 1 (c) are $% 10.942$,$9.824$,and $9.528$,respectively. Obviously,it can be obtained that the weighted value in Fig. 1 (c) is smallest,which means,the energy dissipation with the topology as shown in Fig. 1 (c) is the least. Based on this,the following theorem is given.

Fig. 1

	Download: JPG larger image
Fig. 1 Topology relationship of underwater WSANs.

Theorem 1 In underwater environment,if we use the min-weighted rigid graph generated by Algorithm 1 to represent the topology relationship of underwater WSAN,the network coverage area is connected.

Proof In three-dimensional underwater WSANs, according to the rigid definition of min-weighted rigid graph,it is obtained that $% \mathcal{\ }$min-weighted rigid is the minimum rigid network. Through the properties of the minimum rigid,it is known that each vertex can at least be connected with three neighbors and the total number of edges is 3n-6. Obviously,the above conditions meet the necessary and sufficient condition of 3 connected graph,i.e.,there are at least three roads between three different vertices in graph. So this network is 3 connected. Therefore,if remove three arbitrary vertices,the underwater WSANs are still connected.

According to the above algorithm,the optimal topology generated by min-weighted rigid algorithm is unique. The time complexity is an important index used to measure this algorithm. Then we define the time complexity is $% {\rm O}( n^{3}) $. If ${\rm O}( n^{3}) $ is greater,the higher the degree of complexity is,whereas the lower the degree of complexity is.

Based on the min-weighted rigid graph topology,a dynamic coverage strategy is proposed for SNs and ANs in underwater environment. Especially,fraction of coverage is an important measurement for the network quality of service (QOS). It is noticed that the coverage of underwater WSANs plays an important rule on the rationally allocating network space resources,since it achieves better environmental perception and information transmission,and improves the network viability. In order to evaluate the network performance, we give the following definitions:

Definition 1 (fraction of coverage)}{\bf .} Assuming that $V$ is the volume of the underwater WSANs monitoring area and $V_{i}$ is the volume of effective cover for arbitrary sensor (or actor) node. Then,the fraction of coverage is defined as $C=\cup_{i\in V}V_{i}/V$,where $V_{i}=4\pi r_{i}^{3}/3$ and $r_{i}$ is the perception of the sensor (or actor) node radius.

Definition 2(node adjacency coverage) In the node adjacency set $\mathcal{N}_{i}$,node adjacency coverage $\mathcal{K}% \left( s_{i}\right) $ is defined as the ratio of the sum of all the nodes in the coverage of effective volume and the sum of all the nodes could cover the largest volume. Moreover,$\mathcal{K}\left( s_{i}\right) \leq 1$ and

Among them,$\cup V_{ij}$ is defined as the effective cover volume of node $% s_{i}$ and all its adjacent nodes,and $\vert \mathcal{N}% _{i}\vert $ denotes the number of adjacent nodes and $r$ is the node$'$s perception of the radius. Less volume of overlap $s_{i}$ and its adjacent nodes effectively cover,greater the value of $\mathcal{K}( s_{i}) $ is. To obtain $\mathcal{K}( s_{i}) $,it is required to know $\cup V_{ij}$ firstly. However,it is difficult to calculate the overlap volume in three-dimensional space. We use a mathematical method to calculate the volume of a regional overlap, which is shown as Fig. 2.

Fig. 2

	Download: JPG larger image
Fig. 2 The model of the volume of overlap.

In Fig. 2,we assume that $s_{j}$ is a neighbor node of $s_{i}$. $o_{i}$,$% o_{j}$ are positions of the node $s_{i}$ and $s_{j}$ respectively. The distance between these two nodes is denoted by $d_{ij}$ ($0\leq d_{ij}\leq 2r_{s}$). $A$ and $B$ are two intersecting points. $\mathcal{S}_{\mathcal{A}% ^{^{\prime }}\mathcal{OB}^{^{\prime }}\text{ \ }}$is the projection of the overlap in plane $xo_{j}y$. The volume of overlap can be calculated by the following equation:

In analogy to fish movement,the sensor and actor nodes are considered as food and fish,respectively. As fish,actors have two movements: feeding movement and clustering movement. In feeding movement,it is defined that the static sensor with no neighbor nodes is to find the food with the highest concentration and its task is only to collect data under the impact of the flow function. This behavior is a kind of random motion,because the actors need to move more widely for neighbors and food.

At some points,actors begin to forage in current positions. Within its largest range of perception,the concentrations of food are determinated. Furthermore,actors move to the food with the highest concentration. But if actors do not search for the food with the highest concentration,then repeat the actions above. After trying a few times,if actors still do not find the highest concentration,then turn to the next action. In clustering movement,actors in the process of movement can move as far as possible to the center of the neighbor fish and avoid overcrowding. When actors can not find any food,then start to look for companions. Just as the feeding movement,the actors that have larger range of perception to search partners has less neighbor nodes at the initial time. Then actors calculate the approximate center position of the partner. If the center position is not too crowded,actors are required to perform clustering movement.

Our goal is to find an optimal deployment strategy that achieves higher coverage while having full connectivity of all sensor neighbor nodes with minimum transmission loss. See the details in Algorithm 2.

Algorithm 2. Dynamic coverage control

1. Input: record the volume of overlap $\mathcal{V}_{ij}$,the total volume of the corresponding $\mathcal{V}_{i}$

2. $i$ $\epsilon $ $\mathcal{S}$

3.    if (the number of neighbor nodes $\left\vert \mathcal{N}_{i}\right\vert $ is equal to zero)

4.        if the threshold value satisfies $\Delta \varphi >\mathcal{K}\left( s_{i}\right) $

5.            Actors move to assist in covering

6.         end if

7.    else if $\Delta \psi >\sum\nolimits_{i,j\epsilon \left\vert \mathcal{N}% \left( {i}\right) \right\vert }\mathcal{V}_{ij}$ then

8.        Actors move to assist in covering

9.     end if

10.end for

In Algorithm 2,ANs perform the dynamical assist in covering at random position and time. With the date collected by SNs,ANs start to perform feeding movement and clustering movement. When ANs within its maximum sensing range perceive a point which has no neighbor nodes around,ANs move toward it and begin to fine-tune the distance between them until the node adjacency coverage is less than the threshold set in advance. This behavior is feeding movement (line 1~6). On the other hand,when ANs within its maximum sensing range perceive a point which has at least one neighbor node, ANs prepare to perform clustering movement,particularly if the volume of overlap at that point is smaller than $\Delta \varphi $, which is defined as a crowding factor to avoid overcrowding. Repeat operations above until all ANs have proper positions to collaborate SNs coverage.

Autonomous fish swarm algorithm (AFSA) is a novel optimization method proposed in $^[19]$. This algorithm is easy to understand and implement. It achieves optimization by multiple comparison and characteristics of mobile. Nevertheless,this algorithm has some shortcomings,such as,poor robustness,being easy to fall into local optimum,slow convergence speed and the limitations of application environments. So we improve the algorithm and apply it to a new environment. In this paper,we use the node adjacent coverage and the overlapping volume among adjacent nodes to restrict ANs random moving in feeding movement and clustering movement. Moreover,with these restriction,ANs cannot jump out of the local optimum,nor accelerate the convergence speed.

Remark 2. From the analysis above,the action of actors can be easily explained. Actors perform appropriate actions according to all the data collected by SNs. Then they guarantee the connectivity of WSANs. In addition,with a small number of mobile ANs used in WSANs,it is more economical compared with WMSNs.

Remark 3. In Algorithm 1,the global min-weighted rigid graph is generated indirectly from the local min-weighted rigid graph,where local min-weighted rigid graphs are generated and each node only exchanges information with its neighboring nodes. Meanwhile,in Algorithm 2,each node (AN or SN) makes decision using only the received data within its neighboring sensing area. Therefore,the proposed method in this paper is in a distributed way.

In this section,simulation results are given to demonstrate the efficiency of the proposed dynamic coverage algorithm. The underwater WSANs are consist of 12 SNs and 5 ANs,where the initial node deployment is shown in Fig. 3. We assume that the length, width and height of the area is 100 meters,respectively. The parameters are set as follows: $\lambda$ $=$ $1.5$,$A=2\pi /7.5 $, $c=0.15$ and $r_{s}=20$.

Fig. 3

	Download: JPG larger image
Fig. 3 The initial node deployment

Figs. 4 and 5 show the topology relationship of SNs and ANs with the distributed neighbor rule and the min-weighted graph optimization strategy,respectively. A comparison of the number of links between un-optimized and optimized distributed modes is presented in Fig. 6. Obviously,we can see the complexity of the communication topology is reduced by the min-weighted graph optimization strategy. Furthermore,Fig. 7 compares the number of the difference value between links in un-optimized and optimized distributed modes. We can see that the number of the difference value between links in optimized distributed modes is constant. But the number of the difference value between links in un-optimized distributed modes is almost linear to number of sensors.

Fig. 4

	Download: JPG larger image
Fig. 4 Ordinary rigid topology relationships in un-optimized distributed mode.

Fig. 5

	Download: JPG larger image
Fig. 5 Minimum weighted rigid topology relationships in optimized distributed mode.

Fig. 6

	Download: JPG larger image
Fig. 6 The number of links in un-optimized and optimized distributed modes.

Fig. 7

	Download: JPG larger image
Fig. 7 The number of the difference value between links in unoptimized and optimized distributed modes.

Fig. 8 shows that the initial coverage of 12 SNs and 5 ANs. The little red rectangle represents AN,and the little black dots represent SN. From Fig. 8,it is obvious that this network has poor coverage and connectivity,because some nodes are only of 2-connectivity. And in the underwater environment,2-connectivity is not stable. If any link is disconnected,part of the network will be paralyzed. If the network connectivity cannot be guaranteed,the coverage of the network will not be achieved. To solve this problem, a min-weighted dynamic covering strategy is used to deploy the network. SNs can passively move with the underwater fluid motions, and ANs can automatically explore new position to assist in the updated wireless sensor actor network. As shown in Fig. 9,the network connectivity and coverage are both improved. Also,it can be seen that each node has at least three links to other nodes. To show the effectiveness of the algorithm,we perform the deployment of network with two different methods at certain point $t$. Fig. 10 shows the original deployment of nodes,and Fig. 11 is the original rigid deployment using the method in ^[20]. In addition,the min-weighted dynamic cover deployment and connected graph in this paper are shown in Fig. 12 and Fig. 13. Obviously,compared with the results in Fig. 10 and Fig. 11,both of the coverage and the connectivity of the network are improved using our method.

Fig. 8

	Download: JPG larger image
Fig. 8 Ordinary rigid deployment use[20]

Fig. 9

	Download: JPG larger image
Fig. 9 The minimum weighted dynamic cover deployment.

Fig. 10

	Download: JPG larger image
Fig. 10 The original deployment of nodes at certain point t

Fig. 11

	Download: JPG larger image
Fig. 11 The ordinary rigid deployment use [20] at certain point t.

Fig. 12

	Download: JPG larger image
Fig. 12 The min-weighted dynamic cover deployment at certain point t.

Fig. 13

	Download: JPG larger image
Fig. 13 The connected graph of min-weighted dynamic cover deployment at certain point t.

In this paper,we investigate the problem of dynamic coverage with wireless sensor and actor networks (WSANs) in underwater environment. SNs are responsible to collect data from the environment,and ANs perform appropriate actions according to the gathered data. For such a network,a topology optimization strategy based on min-weighted rigid graph is first proposed to optimize the topology of WSANs. With the optimized topology,the amount of communication links and energy dissipations can be reduced. Furthermore,a dynamic coverage strategy is proposed for underwater WSAN. As shown in the simulation results,not only the connectivity is significantly enhanced but also the coverage rate can be increased accordingly. Moreover,it is known that the construction cost of the underwater WSAN can be reduced.

In our future work,the undirected graph will be switched to a directed graph. Also on the basis of the directed graph,we may achieve a full coverage of underwater area under the condition of obstacles.