s2fieldsofstudy:
Computer Science
Environmental Science

text:
A Novel Technique for Rejecting Non-Aircraft Artefacts in Above Horizon Vision-Based Aircraft Detection

Unmanned aerial vehicle (UAV) operations are steadily expanding into many important applications. A key technology for better enabling their commercial use is an onboard sense and avoid (SAA) technology which can detect potential mid-air collision threats in the same manner expected from a human pilot. Ideally, aircraft should be detected as early as possible whilst maintaining a low false alarm rate, however, textured clouds and other unstructured terrain make this trade-off a challenge. In this paper we present a new technique for the modelling and detection of aircraft above the horizon that is able to penalise non-aircraft artefacts (such as textured clouds and other unstructured terrain). We evaluate the performance of our proposed system on flight data of a Cessna 172 on a near collision course encounter with a ScanEagle UAV data collection aircraft. By penalising non-aircraft artefacts we are able to demonstrate, for a zero false alarm rate, a mean detection range of 2445m corresponding to an improvement in detection ranges by 9.8% (218m).

I. INTRODUCTION
The unmanned aerial vehicle (UAV) market worldwide is projected to grow by US $47.8 Billion by 2025, with a compounded growth of 18.8%. This growth is driven by the increasing use of UAVs in various commercial applications, such as monitoring, surveying and mapping, precision agriculture, aerial remote sensing, product delivery and many more [1]- [3]. The consistent increase in the global market has propelled efforts to ensure that routine, standard and flexible UAV operations are integrated into the national airspace such that they do not compromise the existing safety levels [4]. The risk of mid-air collision is an important safety concern that is both faced and posed by UAVs. The capability to avoid mid-air collisions would allow UAVs to more routinely operate in common airspace [5], [6].
In order to reduce the risk of a mid-air collision, the national airspace is strictly regulated with several safety layers [4], [5], [7]. The first few layers involve operational procedures, air traffic management and cooperative collision avoidance systems. The final layer is for potential mid-air collision threats that are not caught by the other layers e.g. aircraft that are not communicating their presence. In these situations non-cooperative collision avoidance is necessary. For a manned aircraft this final safety layer involves a pilot visually seeing and then avoiding a collision threat. For UAVs this final safety layer involves sensing and avoiding Fig. 1. An example of the above horizon conditions and aircraft target size which we are trying to detect. Note the texture in the clouds and the similarities between the aircraft and cloud features potential non-cooperative, mid-air collision threats with a proficiency matching or exceeding that of human pilots. A general guideline for how well human pilots detect potential collision threats is given in [8] where pilots, who were alerted to the presence of potential collision threat, were able to detect them with an 86% success rate at a median range of 2593m.
For sense and avoid (SAA), in small to medium sized UAVs, machine vision has been established as a potential technology as vision sensors have power, cost, size and weight benefits over other sensing approaches [9]. To meet the approximate human guidelines (as well as providing sufficient time for avoidance manoeuvres) it is desirable to detect aircraft as early as possible in an image sequence. At these ranges aircraft appear in vision sensors as a very small number (approx 1-10) of locally dim pixels that poorly contrast with the background (see Figure 1 for an example of aircraft size). In this paper we will focus on the "sense" aspect of SAA, specifically vision-based aircraft detection. There have been a variety of collision avoidance strategies to address the "avoid" aspect suitable for use with vision-based aircraft detection approaches (see [9], [10] and references therein), however that is out of scope for this paper.
The most promising approaches for vision-based aircraft detection that have been presented in the literature exploit the use of a multi-stage detection pipeline [7], [11]- [15]. The first stage typically exploits image pre-processing where spatial and visual aircraft features are highlighted and background clutter is suppressed. Popular approaches that Fig. 2. Overview of our multi-stage detection system. An image sensor captures an image which is then stabilised. Morphology is used for the image pre-processing stage and hidden Markov model (HMM) filtering for the temporal filtering. For the detection logic stage we propose our new system which exploits the visual appearance of aircraft emergence and common false alarms.
have been proposed in the literature to achieve this include morphology [7], [11], [12], and image frame differencing [7], [13]. Various machine learning [16] and deep learning [17], [18] approaches have been investigated to exploit the visual appearance of aircraft. Recently [15] used a deep CNN fused with morphological processing in the image preprocessing stage to detect aircraft above the horizon with a mean detection range of 2527m and no false alarms. However there are several drawbacks in using learnt approaches in this application as data is expensive and challenging to collect.
Finally the detection logic stage aims to utilise the information available from the image pre-processing and temporal filtering stages in order to declare whether an aircraft is present or not. Some more simple approaches include looking for a detection in a 5 × 5 neighbourhood in the previous frame [20] and checking if the aircraft is increasing in area [21]. In [14] they proposed a new way of modelling aircraft emergence and were able to obtain a theoretically optimal detection logic. In this paper we aim to build off the theoretically optimal detection logic presented in [14] however we also aim to exploit the visual appearance of aircraft emergence and common false alarms.
The key contributions of this paper are casting the visionbased aircraft detection problem as an optimal stopping problem where we are able to introduce a penalty on detecting non-aircraft artefacts such as cloud features. We are able to establish that the optimal solution occurs on first entry of the change posterior into a stopping region characterised by the union of convex sets. Using these properties we propose a new detection logic stage that is able to improve detection ranges and false alarm rates.
The rest of this paper is structured as follows. In Section II we set up our model of aircraft dynamics and observations, this lets us cast our problem as an optimal stopping problem and propose two candidate rules for aircraft detection. In Section III we evaluate the performance of our proposed rules on flight data of near collision course encounters. We provide concluding remarks in IV.

II. PROPOSED SYSTEM
In this section we describe our proposed vision-based aircraft detection system. Similar to several state of the art approaches we exploit a multi-stage detection pipeline as seen in Figure 2. An image sensor captures an image which is then stabilised (the data we will test on was stabilised by a GPS-INS sensor see [22] for full details). We will now describe the other stages of our proposed detection system.

A. Image Pre-Processing
As noted in the introduction morphological processing is commonly exploited in the image pre-processing stage. For a greyscale image I, the dilation by a morphological structuring element S is denoted by I ⊕ S and erosion is denoted by I S. Similar to several state of the art approaches [12], [14] we use bottom hat [I ⊕ S] S − I morphological processing which emphasises dark targets In [23] they observed that targets are generally darker than the background (supporting the notion that bottom hat filters are appropriate).

B. Proposed Temporal filtering
For our temporal filtering stage we use a HMM approach. Let us consider an aircraft in an image sequence which we are trying to detect as soon as possible. The aircraft emerges over time and is (potentially) first visually apparent in an image frame from a single pixel in size.
For k ≥ 0, we introduce a Markov chain with a state to represent each of an aircraft's possible N pixel locations in an image. Following [14] we also introduce an extra state to denote when the aircraft is not visually apparent anywhere in the image frame (that is, it has not visually emerged yet, or there is no collision threat). Let us denote this Markov chain as X k ∈ {e 1 , e 2 , . . . , e N , e N +1 } where e i ∈ R N +1 are indicator vectors with 1 as the ith element and 0 elsewhere. For i ∈ {1, . . . , N }, e i corresponds to the aircraft being visually apparent at the ith pixel and e N +1 corresponds to the aircraft not being visually apparent. We denote this the out of image state.
The following are the three key parameters of a HMM description of target image motion for 1 ≤ i, j ≤ N + 1 1) State transition probabilities: gives the probability of moving between different states. This can either be from the out of image state to a pixel in the image, or moving between different pixels. An aircraft not current located in the image is able to transition from the out of image state to any pixel in the image allowing for the possibility that an aircraft can visually emerge anywhere as it approaches from a distance. Possible aircraft inter-frame motion can be modelled by a transition patch (see [12] for detailed explanation of patches). In this paper we will use the patch that allows transitions to side and above pixels as seen in Figure 3. 2) Initial probabilities: π i = P (X 0 = e i ) denotes the probability that the target is initially located in state e i . We initialise our filter with an equal probability of specify the probability of obtaining the observed image measurement y k given that the target is actually in pixel location e i . At each time k > 0 we obtain a noise corrupted, greyscale image y k that has been morphologically processed using bottom hat. We denote the measurement of the ith pixel at time k as y i k and following [12], [14] for i, j ∈ {1, . . . , N + 1} our diagonal matrix of (unnormalised) output densities is then given by the approximation . . , N } and b N +1 (y k ) = 1 (see [14] for justification). Essentially, the likelihood of an aircraft is proportional to the strength of the morphology output.
For k > 0 we can now calculateX k ∈ R N +1 via the HMM filter [24], which can be regarded as an indicator of likely target locationŝ With the initial condition π and where N k are scalar normalisation factors defined by Here, · denotes an inner product.

C. Proposed Detection Logic
We now present our proposed detection logic. We first cast our problem as an optimal stopping rule and establish an optimal policy. We then propose a general pragmatic greedy decision rule for use as our detection logic.
1) Problem Formulation: Our desired detection logic can be characterised by the following continuing and stopping costs, . . , N }) denotes the delay penalty (when an aircraft is present but a detection has not been declared), c 2 > 0 denotes the false alarm penalty (where an aircraft is not present but a detection has been declared) andc i ∈ R N +1 for i ∈ {1, . . . , N } denotes a penalty for incorrectly declaring a detection on a non-aircraft artefact. Given the location decision i such that S(X) min i∈{1,...,N } S i (X τ ), we seek to design a stopping time τ ≥ 0 that minimises the following cost criterion Where E · X denotes the expectation operation corresponding to the probability measure where the initial state has distributionX, 2) Optimal Policy: Let us consider a stopping action u k ∈ {1 (continue), 2 (stop)}. Then, there is an optimal policy µ * (X k ) to minimise our cost criterion (5) given by the value function V (X k ) min τ {J(τ,X k )}. This value function can be described by the following recursion (similar to [25, pg. 258 whereX + (X, y) = 1, B(y)AX −1 B(y)AX, and B(y) = diag(b 1 (y), . . . , b N +1 (y)). If we let Q(X) C(X) + E[V (X + (X, y))|X] denote the total cost incurred if continuing, then the optimal policy is given by In general, the value recursion (6) is difficult to compute making it unsuitable for use in the vision-based aircraft detection application. We can however establish some properties of the optimal solution that allow us to propose some practical rules.
3) Structure of the Optimal Policy: We now establish that our optimal stopping problem can be solved by finding N convex stopping sets (rather than solving the dynamic programming recursion equations directly). We define the stopping region for state e i as follows R i S {X : S i (X) ≤ Q(X)}. Theorem 1. Consider the value recursion (6) and let R S ∪ i∈{1,...,N } R i S be the union of the N regions R i S . Then, the optimal stopping time given by τ * inf{k :X k ∈ R S } Furthermore, the regions R i S forming the optimal stopping region R S are convex and contain e i .
Proof. See Appendix for proof. Theorem 1 establishes that the solution to our optimal stopping problem can be solved by finding the N convex stopping sets R i S . Given the parallels with our problem setup and quickest change detection and identification, we expect the stopping region R S to not be a connected region in general [26].

4) A Greedy Decision Rule:
We now propose a practical greedy rule which can be applied in our application and establish some performance bounds.
Let us define R i g {X : S i (X) ≤ C(X)} and the union of sets R g = ∪ i∈{1,...,N } R i g . We also define the probability of a false alarm (PFA) as PFA P (X τ = e N +1 ).
Lemma 1. For i ∈ {1, . . . , N }, we consider the union of sets R i g ⊂ R i S and the value recursion (6). Then, the greedy decision rule given by where the maximum delay constant c m max ic i 1 .

Proof. See Appendix for proof
Lemma 1 suggests that a pragmatic solution to our optimal stopping problem is the greedy (sub-optimal) stopping rule τ g . Moreover, if this rule is used then the cost function parameters can be related to a false alarm performance tradeoff. The lemma also provides some insight into the role of cost parameters and false alarm performance. Now, rather than solving the dynamic programming recursion equations (6) directly or trying to calculate the convex stopping sets R i S (both of which are computationally expensive), we are able to just run the HMM filter (1). We highlight that you do not need to know the value of the costs constantsc 1 , c 2 ,c i to run the filter.

5) Proposed Greedy Detection Logic:
We now present two proposed greedy rules for use in the detection logic stage in our multi stage detection pipeline. Due to Lemma 1 we know that these stopping rules are a greedy (sub-optimal) solution to our cost criterion (5). Greedy Rule 1: We first consider a a simple stopping rule of the form whereX i k is the ith element ofX k . Intuitively, this rule declares a detection when the probability of being in one of the first N states is higher than a threshold.
Greedy Rule 2: We introduce a mapping M(·) which reshapes the pixel elements of the vectorX k to an image matrix and also introduce the inverse mapping M −1 (·). Our second stopping rule is of the form where ζ i (·) is the ith element of ζ(·) and ζ(·) M −1 (M(·) * ω) and * denotes the convolution operation with the kernel Intuitively we know that aircraft emerge in an image at approximately 1 pixel in size and hence only occupy one state. As our aim is to detect this aircraft emergence, we propose a kernel that penalizes the states around the aircraft as a type of penalty. Additionally, we found that this kernel was an effective way to reject cloud artifacts that are generally larger in size (more pixels) than an aircaft emerging in an image sequence.

III. RESULTS
In this section we examine the performance of our two proposed detection logic stages in the vision-based aircraft detection application. As a baseline we compare to the theoretically optimal intermittent signal detection (ISD) rule presented in [14], we denote this the baseline ISD rule.
We compare the performance of our proposed detection systems on 15 near mid-air collision course encounters between two fixed wing aircraft; the data collection aircraft was a ScanEagle UAV and the other aircraft was a Cessna 172. An example of the flight path of a head on near collision course encounter is presented in Figure 5, and Figure 1 is an example of the size of aircraft we are detecting. For full details of the flight experiments see [22].

A. Illustrative Example
For i ∈ {1, . . . , N } Figure 4 shows an illustrative example for Case 10 of the Greedy rule 1 test statistic (max iX i k ) the Greedy rule 2 test statistic (max i ζ i ) and the baseline ISD rule test statistic (1 −X N +1 k ). The aircraft is visually present from image frame k = 680 to k = 800. All 3 test statistics effectively increase at a similar time corresponding to them detecting aircraft presence. Greedy rule 1 and Greedy rule 2 both correctly declare at k = 698 (corresponding to aircraft at range 2542.4m) and the baseline ISD rule correctly declares slightly later at k = 705 (corresponding to aircraft at range 2479.8m).
We highlight the peak in the Greedy rule 1 and ISD rule test statistics just after k = 100. This corresponds to the rules mistaking small cloud features for aircraft. Importantly, Greedy rule 2 effectively rejects this false alarm.
We also note the choice of thresholds for the 3 rules. Greedy rule 1 has a higher threshold than Greedy rule 2 so that it does not declare false alarms. We also note that the scale of the baseline ISD rule corresponds to a significantly higher threshold, and to a higher number of significant figures than the two greedy rules, which can be set between 0 and 1.

B. Detection Range Performance
We now investigate the detection range performance across all 15 cases from our test data. We highlight that the detection range and false alarm rates vary with the choice of the threshold parameters. Hence, to ensure fair comparison, we will compare these rules on the basis of the lowest thresholds  Fig. 6. A comparison of the proposed Greedy rules compared to the baseline ISD rule for all 15 cases presented in [22]. The mean detection distance and standard error was 2295m and 22m for Greedy rule 1, 2445m and 61m for Greedy rule 2 and 2227m and 52m for the baseline ISD rule.
for each rule that achieve zero false alarms (ZFAs) in this data set. In practice, detection thresholds could be adaptively selected on the basis of scene difficulty such as proposed in [27].
The resulting ZFA detection ranges are presented in Figure  6. The mean detection distance and standard error was 2295m and 22m for Greedy rule 1, 2445m and 61m for Greedy rule 2 and 2227m and 52m for the baseline ISD rule. Both our Greedy rules improved performance relative to the baseline ISD rule but importantly Greedy rule 2 improved detection ranges by a mean distance of 218m (9.8%).
Intuitively, the performance benefits from Greedy rule 2 are from penalising the non-aircraft artefacts and as a result more effectively rejecting false alarms. This allows for a lower ZFA threshold to be set and therefore an earlier detection can be declared.

IV. CONCLUSION
In this paper we presented a new technique for the modelling and detection of aircraft above the horizon that is able to penalise non-aircraft artefacts (such as textured clouds and other unstructured terrain). We first posed the vision-based aircraft detection problem in a Bayesian setting and established some optimal properties. We then proposed a practical greedy rule and developed some bounds for characterising its performance. Finally, we investigated the performance of two greedy rules on real flight data where we were able to improve detection ranges by a mean distance of 218m (9.8%) relative to a current state of the art vision-based aircraft detection technique.

APPENDIX
A. Proof of Theorem 1 For i ∈ {1, . . . , N }, we define the cost for the location decision i as and consider the value function V i (X k ) min τ {J i (τ,X k )} for the stopping time recursion described by Noting that the cost is linear here, then according to [25,Theorem 7.4.2], V i (X k ) are concave inX. Moreover, our location decisionS(X) min i∈{1,...,N } S i (X τ ) gives that at eachX k , J(τ,X) = min i J i (τ,X), and hence V (X k ) = min i V i (X k ) (swapping the order of the minimisation operations) implies that V (X k ) is concave inX (concavity is preserved under minimum operations). The V (X k ) concavity gives that R i S are convex sets (see similar proof steps in [25, Theorem 12.2.1]).
We proceed by considering the N location decisions as individual optimal stopping problems. For i ∈ {1, . . . , N } if S i (e i ) = 0 then e i ∈ R i S . WhenX ∈ R i S for any i implies S i (X) ≤ Q(X) and under optimal rule (7) implies that the optimal action is to stop. Contrarily,X / ∈ R i S for any i implies S i (X) > Q(X) and under optimal rule (7) implies the optimal action is to continue. Hence the union of the R i S regions defines the optimal stop region as given in the theorem statement.

B. Proof of Lemma 1
For i ∈ {1, . . . , N }, C(X k ) ≥ S i (X k ) implies that Q(X k ) ≥ S i (X k ) and therefore, according to the optimal policy (7), we should stop whenX k ∈ R i g . Further, if S i (e i ) = 0 then e i ∈ R i g giving our first lemma result. Simple algebra shows that C(X k ) ≥ S i (X k ) implies (c m + c 2 )X N +1 k +c iXk < c m (given that c m (1−X N +1 k ) ≥c 1Xk ). Taking the expectation operation on both sides and using the idempotent property gives our lemma's PFA performance bound result.


extfieldsofstudy:
Mathematics
Computer Science

text:
Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials

Optimization over non-negative polynomials is fundamental for nonlinear systems analysis and control. We investigate the relation between three tractable relaxations for optimizing over sparse non-negative polynomials: sparse sum-of-squares (SSOS) optimization, diagonally dominant sum-of-squares (DSOS) optimization, and scaled diagonally dominant sum-of-squares (SDSOS) optimization. We prove that the set of SSOS polynomials, an inner approximation of the cone of SOS polynomials, strictly contains the spaces of sparse DSOS/SDSOS polynomials. When applicable, therefore, SSOS optimization is less conservative than its DSOS/SDSOS counterparts. Numerical results for large-scale sparse polynomial optimization problems demonstrate this fact, and also that SSOS optimization can be faster than DSOS/SDSOS methods despite requiring the solution of semidefinite programs instead of less expensive linear/second-order cone programs.

I. INTRODUCTION
Optimization over non-negative polynomials plays a fundamental role in analysis and control of systems with polynomial dynamics. For instance, the construction of polynomial Lyapunov or Lyapunov-type functions subject to suitable polynomial inequalities can prove nonlinear stability of equilibrium solutions [1], approximate basins of attraction [2], and provide bounds on infinite-time averages [3]- [5].
Since deciding whether a given polynomial p(x) is nonnegative is NP-hard in general, a popular alternative is to look for a decomposition of p(x) as a sum-of-squares (SOS) of polynomials with lower degree. Checking this sufficient condition for non-negativity is attractive because it amounts to solving a semidefinite program (SDP) [6], [7], a well-known type of convex optimization problem for which polynomial-time algorithms exist. However, the dimension of this SDP typically grows in a combinatorial fashion as the number of variables and the polynomial degree increase [6], and very large SDPs are required to solve even when one employs well-known dimension reduction techniques, such as the Newton polytope [8], diagonal inconsistency [9], and symmetry [10] or facial reduction [11]. Consequently, SOSbased analysis is only practical for polynomial dynamical systems with few states and/or low degree.
In order to improve scalability, it has been proposed by many authors to replace positivity certificates based on SOS representations with other sufficient conditions for nonnegativity, which are stronger but have a lower computational complexity. For correlatively sparse polynomials, characterized by sparse couplings between different independent variables, Waki et al. [12] proposed to look for a decomposition as a sum of SOS polynomials, each involving only small subsets of the independent variables. While being more restrictive, the search for such a sparse sum-of-squares (SSOS) decomposition can be carried out at a fraction of the computational cost required for a standard SOS decomposition, because an SDP with one large matrix variable is replaced with an SDP with multiple much smaller matrix variables. The latter can be solved more efficiently, a fact that also underpins the more recent sparse-BSOS [13] and multi-ordered Lasserre relaxation hierarchies [14] for sparse polynomial optimization. Two other alternatives to SOS optimization, applicable also to polynomials without correlative sparsity, were put forward by Ahmadi and Majumdar [15], who observed that the cones of diagonally dominant sum-ofsquares (DSOS) polynomials and of scaled diagonally dominant sum-of-squares (SDSOS) polynomials are strict subsets of the cone of SOS polynomials. Optimization problems over DSOS and SDSOS polynomials can be recast as linear programs (LPs) and second-order cone programs (SOCP), respectively, and both of these can be solved with algorithms that scale more favourably than those for SDPs [15]. On the other hand, DSOS/SDSOS optimization might be very conservative (although the conservatism may be reduced using iterative methods based on basis pursuit [16] or column generation [17]).
The availability of such a variety of approaches poses a simple but important dilemma: when more than one method can be applied, which one should be used? To answer this question, theoretical results comparing the degree of conservatism and computational complexity for each of the aforementioned approaches would be desirable. In this paper, therefore, we study the relation between DSOS/SDSOS/SSOS positivity certificates for polynomials with correlative sparsity. Specifically, we prove that if a DSOS/SDSOS decomposition exists and the correlative sparsity is chordal (meaning that it can be represented by a chordal graph), then an SSOS decomposition is also available. In other words, the cones of DSOS/SDSOS polynomials with chordal correlative sparsity are strictly contained within the cone of polynomials that admit an SSOS decomposition in the sense of Waki et al. [12]. Thus, for polynomials with chordal correlative sparsity, DSOS/SDSOS optimization is provably more conservative than SSOS optimiza-tion (at least when the iterative improvement techniques for DSOS/SDSOS optimization mentioned above are not utilised). Also, SSOS optimization promises better scalability compared to standard SOS optimization. Therefore, we argue that SSOS optimization is a suitable candidate to bridge the gap between DSOS/SDSOS and SOS optimization.
The rest of this paper is organized as follows. Section II reviews some basic facts about SOS/DSOS/SDSOS polynomials, useful notions from graph theory, and correlatively sparse polynomials. We give a new interpretation of the positivity certificates of Waki et al [12] in Section III, which enables the connection to DSOS/SDSOS conditions for correlatively sparse polynomials in Section IV. In Section V, we extend our analysis to the cones of sparse DSOS/SDSOS/SSOS polynomial matrices. Section VI presents numerical results. Finally, Section VII concludes the paper.

A. SOS, DSOS, and SDSOS polynomials
Given a vector of variables x ∈ R n and a multi-index α ∈ N n , the quantity An n-variate polynomial of degree 2d can be written as p(x) = α∈N n 2d c α x α . We denote the set of polynomials in n variables with real coefficients of degree no more than 2d by R[x] n,2d , and the subset of nonnegative polynomials in R[x] n,2d by PSD n,2d .
Checking if p(x) ∈ PSD n,2d is NP-hard already for polynomials of degree 4, but it is computationally tractable to test membership to the following subsets of PSD n,2d .
(1) SOS polynomials: We denote the set of n-variate SOS polynomials of degree no larger than 2d by SOS n,2d . It is known [6] that p(x) ∈ SOS n,2d if and only if there exists a PSD matrix Q (denoted Q 0), such that where T is the vector of monomials of x of degree d or less. Following [6], we refer to (1) as the Gram matrix representation of the polynomial p(x). Note that the size of the Gram matrix Q is n+d d × n+d d in general.
(2) DSOS polynomials: Recall that a symmetric matrix A ∈ S r is diagonally dominant (DD) if A ii ≥ r j=1 |A ij | for all i = 1, . . . , r, and that DD matrices are positive semidefinite (this directly follows, for example, from Gershgorin's circle theorem). Following [15], we say that polynomial p(x) ∈ R[x] n,2d is a diagonally dominant sum-of-squares (DSOS) if it admits a Gram matrix representation (1) with a DD Gram matrix Q. We denote the set of DSOS polynomials in n variables and degree no larger than 2d by DSOS n,2d . (3) SDSOS polynomials: Recall that a symmetric matrix A ∈ S r is scaled diagonally dominant (SDD) if there exists a positive definite r ×r diagonal matrix D such that DAD is diagonally dominant. Following [15], we say that polynomial p(x) ∈ R[x] n,2d is a scaled diagonally dominant sum-ofsquares (SDSOS) if it admits a Gram matrix representation (1) with an SDD Gram matrix Q. We denote the set of SDSOS polynomials in n variables and degree no larger than 2d by SDSOS n,2d .
Let p 0 , . . . , p t ∈ R[x] n,2d be given polynomials. An SOS optimization problem takes the standard form where u ∈ R t is the decision variable. It is not difficult to see that (1) enables one to recast (2) as an SDP [6]. It has also been proved that if SOS n,2d is replaced with DSOS n,2d in (2) (resp. SDSOS n,2d ), then one obtains an LP (resp. SOCP) [15]. Thus, DSOS/SDSOS optimization are more scalable alternatives to SOS optimization, but are typically more conservative since the strict inclusion DSOS n,2d ⊂ SDSOS n,2d ⊂ SOS n,2d holds.

B. Chordal graphs and sparse matrices
The sparsity of a polynomial p(x) ∈ R[x] n,2d , or of any of its possible Gram matrices, can be conveniently represented by an undirected graph G(V, E), that is, a set of nodes V = {1, 2, . . . , n} and a set of edges E ⊆ V × V such that (i, j) ∈ E implies that (j, i) ∈ E also. For this reason, it is useful to review some essential notions about graphs and their relation to sparse matrices.
A cycle of length k of an undirected graph between nonconsecutive nodes of the cycle, and an undirected graph is called chordal if all its cycles with length ≥ 4 have a chord. Simple examples of chordal graphs are given in Fig. 1. Note that any nonchordal graph G(V, E) can always be extended to a chordal graph G(V,Ê) by adding edges to E [18]. Finally, a clique C ⊆ V is a subset of nodes where (i, j) ∈ E, ∀i, j ∈ C, i = j. If a clique C is not included in any other clique, then it is referred to as a maximal clique. For example, the graph in Fig. 1(c) has maximal cliques {1, 2, 3} and {2, 3, 4}, while that in Fig. 1(b) has maximal cliques {1, i+1}, i = 1, . . . , 4.
Given an undirected graph G(V, E), we consider the extended set of edges E * = E ∪ {(i, i), ∀i ∈ V} and define the space of n × n symmetric matrices with sparsity pattern characterized by G as Similarly the cone of sparse positive semidefinite (PSD) matrices with sparsity pattern described by G is For simplicity, we will slight abuse the terminology and say that S n (E, 0) has sparsity pattern E. Finally, for each maximal clique C k of G we define an index matrix E C k ∈ R |C k |×r as where |C k | denotes the number of nodes in C k , and C k (i) denotes the i-th node in C k , sorted in the natural ordering.
The following key result states that when the graph G is chordal, then X ∈ S r + (E, 0) if and only if it can be written as a sum of "inflated" PSD matrices.

C. Correlatively sparse polynomials
The notion of correlative sparsity was introduced by Waki et al. [12] to describe couplings between the variables x 1 , . . . , x n of a polynomial p(x) = |α|≤2d c α x α . Key to this description is the so-called correlative sparsity matrix For example, we have n,2d is said to have a correlative sparsity pattern characterized by an undirected graph G(V, E) if csp(p) ∈ S n (E, 0). It is then natural to define the vector space of polynomials with the same correlative sparsity as and its subset of sparse SOS polynomials as Throughout this paper, we assume that the correlative sparsity pattern E is chordal, or that a suitable chordal extension has been found.

III. REVISITING SPARSE SOS DECOMPOSITIONS
Suppose we wish to determine whether a correlatively sparse polynomial p(x) ∈ R[x] n,2d (E) is non-negative using an SOS certificate, meaning that we seek a Gram matrix representation of the form Using multi-indices β ∈ N n d and γ ∈ N n d to index the entries of Q, the equality constraints in (6) can be rewritten as It is clear that, even though p(x) is correlatively sparse, its Gram matrix Q need not be sparse: the only requirement is that β+γ=α Q β,γ = 0 if p(x) does not contain the monomial x α . Nonetheless, in order to exploit correlative sparsity and reduce the cost of searching for a suitable PSD Gram matrix, we insist that Q should be sparse by imposing that Q β,γ = 0 if the monomial x β+γ does not appears in any polynomial of R[x] n,2d (E). More precisely, we define Another method to exploit sparsity, proposed by Waki et al. [12], is to search for a sparse SOS (SSOS) decomposition: let C 1 , . . . , C t be the maximal cliques of G(V, E), let E C k be as in (5) for all k = 1, . . . , t, and try to find PSD matrices Q 1 , . . . , Q t such that In other words, one can try to write p as a sum of SOS polynomials , each of which depends only on the corresponding subset of variables E C k x. Our first main result is to show that these two strategies-imposing that Q is sparse according to (7) and looking for the SSOS decomposition (8)-are equivalent.
Proof: To prove the ⇒ part, we show that the Gram matrix Q has a chordal pattern when (7) holds, so the chordal decomposition (Theorem 1) can be applied to recover (8).
The ⇐ part will also follows from this. a) ⇒: If β and γ are such that an entry Q β,γ is not required to vanish due to (7), then (i, j) ∈ E for all i, j such that β i +γ i = 0 or β j +γ j = 0. Consequently, the set C β,γ = {i ∈ V | β i + γ i = 0} is a clique of the graph G(V, E) and is therefore contained in one of its maximal cliques C 1 , . . . , C t .

Fig. 2:
Graph patterns for polynomial (13): (a) the correlative sparsity pattern G(V, E) of (13) is a line graph; (b) the corresponding super-graph In other words, C β,γ ⊆ C k for some k ∈ {1, . . . , t}. Clearly, this also implies that Thus, if β and γ do not satisfy the condition in (7), then there exists a value k ∈ {1, . . . , t} such that At this stage, define a hyper-graph as edges. Since C 1 , . . . , C t are the maximal cliques of the chordal graph G(V, E), it can be shown [21] is also chordal, and that C d 1 , . . . , C d t are its maximal cliques. Moreover, given that condition (10) holds for some k ∈ {1, . . . , t} for each pair (β, γ) such that Q β,γ is not required to vanish by (7), the hyper-graph G d (V d , E d ) characterizes the sparsity pattern of the PSD matrix Q in (6) Thus, according to Theorem 1, Q in (6) can be decomposed as where (10), we then obtain from (6) that which is exactly (8) as claimed. b) ⇐: This follows after rearranging the last set of equalities in a suitable way.
Note that, in fact, we have shown that p(x) ∈ SSOS n,2d if and only if it admits a sparse Gram matrix Q ∈ S N + (E d , 0), so searching for an SSOS decomposition (8) amounts to imposing a sparsity constraint on the Gram matrix.
where csp(p) is a line graph with maximal cliques C 1 = {1, 2} and C 2 = {2, 3}, as shown in Fig. 2. The Gram matrix Q, which is unique in this case, is PSD and has a chordal sparsity pattern corresponding to the graph in Fig. 2(b), and according to Theorem 1 it can be written as Therefore, the 3-variate p(x) can be written as the sum of the two bi-variate SOS polynomials:

IV. RELATING SSOS TO SPARSE DSOS/SDSOS
We have seen that finding an SSOS decomposition of a correlatively sparse polynomial p ∈ R[x] n,2d (E) amounts to constraining the sparsity of its Gram matrix. This fact makes it possible to draw a connection between the space SSOS n,2d (E) of sparse SOS polynomials and those of sparse DSOS/SDSOS polynomials, defined as Specifically, we have the following result.
Proposition 1: For any sparsity pattern E and the first two inclusions are strict. The third inclusion is strict unless E is full or d = 1, in which cases SSOS n,2d (E) ≡ SOS n,2d (E). Proof: We only need to prove that SDSOS n,2d (E) ⊂ SSOS n,2d (E); the rest is true by definition, and the identity SSOS n,2 (E) ≡ SOS n,2 (E) holds because the Gram matrix representation of correlatively sparse quadratic polynomials is unique and must be sparse. Recall that any p ∈ SDSOS n,2d (E) can be represented by an SDD Gram matrix Q, not necessarily sparse. We then construct a sparse Gram matrixQ according tô It is not difficult to see that p(x) = v d (x)Qv d (x), and that Q is also SDD. Indeed, replacing any off-diagonal entries with zeros does not affect the scaled diagonal dominance of a matrix, while if a diagonal entry Q β,β is replaced by zero, then there exists (i, j) / ∈ E such that β i = 0 and β j = 0, and so the entire row Q β,• and column Q •,β are also replaced with zeros. Thus,Q satisfies the condition (7) and p(x) ∈ SSOS n,2d (E). Finally, the inclusion SDSOS n,2d (E) ⊂ SSOS n,2d (E) is strict because there exist SSOS polynomials whose Gram matrix is not SDD.
The implication of Proposition 1 is simple but important: SSOS n,2d (E) is a strictly better inner approximation of SOS n,2d (E), compared to the DSOS/SDSOS counterparts. Consequently, given correlatively sparse polynomials p 0 , . . . , p t ∈ R[x] n,2d (E) and an optimization variable u ∈ R t , the SOS optimization problem Specifically, if we denote the optimization problems arising in each of these cases by P ssos , P sdsos , and P dsos , and let f * ssos , f * sdsos , and f * dsos be their respective optimal values 1 , Proposition 1 implies that Additionally, it should be clear from Theorem 2 that the SSOS optimization problem P ssos can be recast as an SDP with multiple PSD matrix variables whose size is bounded by m+d d , where m is the size of the largest clique of the underlying correlative sparsity graph G(V, E). Therefore, even though problems P dsos and P sdsos can be solved as LPs and SOCPs [15], the added representation power offered by SSOS constraints need not add much computational cost when m ≪ n. Table I summarizes the problem types for SOS, SSOS, SDSOS, and SOS optimization. In fact, as will be demonstrated by the numerical examples in Section VI, SSOS optimization can be much faster than DSOS/SDSOS optimization provided by the package SPOTless [22]. Seen in this light, SSOS optimization bridges the gap between DSOS/SDSOS and SOS optimization for problems with correlatively sparse polynomials.

POLYNOMIALS
The results of the previous sections can be extended to sparse matrix-valued polynomials, which arise naturally in some applications [23], [24]. Let R[x] r×s n,2d be the space of r × s matrices whose entries are polynomials in R[x] n,2d , and S[x] r n,2d be the space of r × r symmetric polynomial matrices. A symmetric polynomial matrix P (x) ∈ S[x] r n,2d is PSD if P (x) 0, ∀ x ∈ R n , and it belongs to the space 1 For an infeasible problem, we denote the optimal cost value as infinity.  [10], [23], [25].
Clearly, SOS matrices are PSD, and it is well-known (see, e.g., [10], [23], [25]) that P (x) ∈ SOS r n,2d if and only if there exists a Gram matrix Q 0 such that where I r is the r × r identity matrix and ⊗ is the usual Kronecker product. Similarly to DSOS/SDSOS polynomials, we can define DSOS/SDSOS matrices as follows. Definition 1: A polynomial matrix P ∈ S[x] r n,2d is • DSOS, denoted P ∈ DSOS r n,2d , if it admits a Gram matrix representation (16) with a DD matrix Q. • SDSOS, denoted P ∈ SDSOS r n,2d , if it admits a Gram matrix representation (16) with an SDD matrix Q. An alternative characterization of SOS/DSOS/SDSOS matrices can be given as follows [10].
Proposition 2: A polynomial matrix P ∈ S[x] r n,2d is SOS (resp., DSOS or SDSOS) if and only if, given y ∈ R r , the polynomial y T P (x)y is SOS (resp. DSOS or SDSOS) in [x; y] ∈ R m+n .
Proof: Using (16), where z(x, y) = y ⊗ v d (x) is a subset of the vector of monomials in x and y. Therefore, P (x) ∈ SSOS r n,2d (resp. P (x) ∈ DSOS r n,2d and P (x) ∈ SDSOS r n,2d ) if and only if Q is PSD (resp., DD and SDD).

A. Sparse SOS, SDSOS, and DSOS matrices
Similar to the spaces of sparse matrices mentioned in Section II, we can define the space of sparse symmetric polynomial matrices whose sparsity pattern is characterized by an undirected graph G(V, E) as We can also introduce the subspaces of sparse SOS/SDSOS/DSOS matrices, The Gram matrix representation (16) of a sparse SOS matrix P ∈ SOS r n,2d (E) can be rewritten as where the (i, j)-th block Q ij ∈ S N of the Gram matrix is to be chosen such that Q 0 and Note that Q ij need not be a zero matrix to satisfy (18), so the Gram matrix Q for a sparse SOS matrix is dense in general and checking that P ∈ SOS r n,2d (E) can be computationally expensive. For this reason, in [26] the authors proposed to impose sparsity in the Gram matrix Q and test if P belongs to the space of polynomial matrices that admit a sparse SOS decomposition, defined as The following proposition shows that this space is larger than both DSOS r n,2d (E) and SDSOS r n,2d (E), and is the matrix-valued analogue of Proposition 1.
Proposition 3: For any pattern E, we have (20) and the first two inclusions are strict. The third inclusion is strict unless E is full in which SSOS r n,2d (E) ≡ SOS r n,2d (E). Proof: We only need to prove that SDSOS r n,2d (E, 0) ⊂ SSOS r n,2d (E, 0), since the other inclusions follow directly from the definition of each space. To this end, note that any P ∈ SDSOS r n,2d (E) admits a Gram matrix representation (16) with an SDD matrix Q. Then, consider the matrix obtained by setting to zero blocks of Q corresponding to zero entries of P . The matrixQ is still SDD, and hence PSD, and satisfies Hence, P (x) ∈ SSOS r n,2d (E) and (21) is true; the inclusion is strict because there clearly exist polynomial matrices in SSOS n,2d (E) whose Gram matrix is not SDD. Finally, the identity SSOS r n,2d (E) ≡ SOS r n,2d (E) holds obviously when E contains all edges.
As in the scalar case, sparse matrix SOS certificates are expected to be less conservative than their DSOS/SDSOS counterparts. Additionally, if the sparsity pattern of a sparse polynomial matrix is chordal, then working with SSOS n,2d (E) can be computationally efficient because-similar to the SSOS decomposition for scalar polynomials-it requires solving SDPs with small PSD cones. This follows from the next theorem, originally proven in [26], which extends Theorem 1 to sparse polynomial matrices.
Theorem 3 ( [26]): Let G(V, E) be a chordal graph with maximal cliques {C 1 , C 2 , . . . , C t }. Then, with P k ∈ SOS |C k | n,2d for each k = 1, . . . , t. Proof: A detailed proof can be found in [26]. Briefly, the "if" part is obvious, while the "only if" part relies on the fact that, when G(V, E) is chordal, the sparse Gram matrix Q of P has a chordal sparsity pattern also, and can be decomposed using Theorem 1 to obtain (22).
Consequently, one can use the cones DSOS r n,2d (E), SDSOS r n,2d (E), and SSOS r n,2d (E) to formulate increasingly better and computationally tractable approximations of largescale matrix-valued SOS optimization problems of the form where P 0 , . . . , P t ∈ S r n,2d (E, 0) are given sparse symmetric polynomial matrices and u ∈ R t is the decision variable. All comments given at the end of Section IV on the relation between scalar SSOS/SDSOS/DSOS optimization are also valid for matrix-valued problems.

B. Reduction to the scalar analysis
Proposition 2 states that a matrix-valued polynomial P (x) is SOS (resp., DSOS or SDSOS) if the associated scalar polynomial p(x, y) = y T P (x)y is so, and it is natural to ask if the same is true for the SSOS condition. Here show that applying Theorem 3 to P ∈ SSOS r n,2d (E) is indeed equivalent to applying Theorem 2 to p(x, y), but only if any correlative sparsity with respect to the variable x is ignored.
Indeed, p(x, y) has correlative sparsity pattern E with respect to y since the monomial y i y j appears if and only if P ij (x) = 0, meaning that (i, j) ∈ E. It is then not difficult to verify that, if any correlative sparsity with respect to the variable x is ignored, Theorem 2 guarantees that p(x, y) can be decomposed as for some SOS polynomials p k , k = 1, . . . , t. In particular, each p k is quadratic in y and has degree d in x, so it admits the Gram matrix representation with Q k 0. But then, upon defining and using the properties of the Kronecker product to rewrite Since p(x, y) = y T P (x)y we conclude that which is exactly the statement of Theorem 3. The argument can easily be reversed to show that Theorem 3 implies the existence of an SSOS decomposition of p(x, y). Remark 1: It is important to note that the equivalence outlined above holds only when any correlative sparsity of the entries of the polynomial matrix P with respect to x is disregarded, because we do not take it into account in our analysis of polynomial matrices. However, it may be possible to exploit correlative sparsity in x when applying Theorem 2 to y T P (x)y. In this case, working at the scalar level will not be equivalent to applying Theorem 3 to P directly, and will instead result in a stronger (but possibly computationally cheaper) constraint. Therefore, our results for matrix-valued polynomials remain of independent interest.

VI. NUMERICAL EXAMPLES
To demonstrate that DSOS/SDSOS constraints are indeed more conservative than sparse SOS conditions in practice, we report the results of numerical experiments on sparse versions of the examples considered in [15]. We implemented sparse SOS conditions in YALMIP [27], adapting the undocumented option sos.csp to exploit correlative sparsity using the chordal extension methods described in [12]. For the DSOS/SDSOS constraints, instead, we used SPOTless [22]. The solver MOSEK [28] was used to solve the LPs, SOCPs, and SDPs arising, respectively, from DSOS, SDSOS and SSOS constraints. All computations were carried out on a PC with a 2.8 GHz Intel Core i7 CPU and 8GB of RAM.

A. Lower bounds on scalar polynomials
Given the Broyden tridiagonal polynomial  consider the best lower bound problem Upon replacing the non-negativity constraint with an SOS/SSOS/SDSOS/DSOS conditions, this problem can be reformulated as an SDP/SDP/SOCP/LP, respectively. The optimal γ obtained in each case for different values of n is reported in Table II, and MOSEK's runtime is reported in Table III. For all values of n the cone of DSOS polynomials is too restrictive and the DSOS constraint is infeasible. Moreover, as expected from Proposition 1, the SDSOS condition is more conservative that the SSOS one 2 . For this example, SSOS conditions appear not to introduce any conservativeness: they yield the same optimal value as the classical SOS relaxation, and at a fraction of the computational cost. Interestingly, solving the SSOS conditions was also faster than solving SDSOS conditions. This is likely due to the fact that the SSOS condition translates to an SDP with n − 1 PSD matrix variables of size 6 × 6 for this particular problem (27), while, the number of second-order cones required for an SDSOS constraint is O(n 2 ). Whether sparsity can be exploited in SPOTless to formulate a smaller SOCP for sparse SDSOS constraints remains an interesting open question for future work.

B. Eigenvalue bounds on matrix polynomials
Let G(V, E) be the 5-node star graph of Fig. 1(b), and let P ∈ S r×r 2,2 (E, 0) be a sparse polynomial matrix whose entries are randomly generated quadratic polynomials in 2 variables. The best lower bound on the smallest eigenvalue of P (x) valid for all x ∈ R 5 is given by the solution of the optimization problem min γ γ subject to P (x) + γI 0 ∀x ∈ R 5 .  We solved this problem for P (x) of increasing size r after replacing the PSD constraint with SOS, SSOS, DSOS and SDSOS conditions. The optimal γ for each case is reported in Table IV, while the CPU time is shown in Table V. As in the previous example, SSOS conditions exhibit the best trade-off between conservativeness and computational cost.

C. Co-positive programming
Our next experiment is an optimization problem over the cone CP n of co-positive n × n matrices, which has recently attracted attention since it can model several combinatorial optimization problems exactly [29]. A symmetric matrix Z ∈ S n is co-positive if y T Zy ≥ 0 for all y ≥ 0, or [6] Z ∈ CP n ⇔ n i,j=1 Replacing the non-negativity constraint with SOS, SSOS, SDSOS and DSOS conditions yields tractable inner approximations of CP n . Here, we solve such approximations for l blocks e e h h Fig. 3: Block-arrow sparsity pattern (dots indicate repeating diagonal blocks). The parameters are: the number of blocks, l; block size, e; the width of the arrow head, h.  optimization problems of the form where Z is a randomly generated symmetric matrix with a block-arrow sparsity pattern with l blocks of size e × e, and arrow head h; see Fig. 3 for an illustration. Such a sparsity pattern is chordal, with l maximal cliques of size e + h.
We fixed the block size e = 3, arrow head size h = 2, and varied the number of blocks l. Table VI shows that the upper bound on the optimal solution of (29) obtained with SSOS constraints is always strictly better than that obtained with SDSOS and DSOS optimization, and gives the same result as the classical SOS relaxation in all cases for which this could be implemented. Again, SSOS constraints are also extremely competitive in terms of CPU time, cf. Table VII.

D. Lyapunov stability analysis
As our final example, we considered randomly generated n-dimensional, degree-3 polynomial dynamical systems of the form           ẋ with a linearly stable equilibrium at the origin. We then searched for quadratic Lyapunov functions of the form that certify the nonlinear local stability of the origin for a subset of initial conditions in the box D = [−0.1, 0.1] n . Specifically, we looked for V (x) that satisfies (where we used ǫ = 10 −6 in the simulation) after replacing the non-negativity conditions with SOS, SSOS, SDSOS, and DSOS constraints in turn.  VII. CONCLUSION In this paper we have demonstrated that, for correlatively sparse polynomials, sparse SOS positivity certificates are more general and typically less conservative than those based on DSOS and SDSOS methods. Key to this result is a new interpretation of the sparse SOS conditions proposed by Waki et al. [12] in terms of a sparsity constraint of the Gram matrix Q used to represent sparse SOS polynomials, to which a well known chordal decomposition theorem can be applied. Numerical examples have confirmed our theoretical findings, and also demonstrated that SSOS conditions can be dramatically more efficient than the DSOS/SDSOS conditions formulated by the dedicated package SPOTless. Thus, although DSOS/SDSOS methods remain one of the few methods to implement non-negativity constraints for dense polynomials with many variables and/or high degree, one should try to utilize SSOS constraints when possible.
In the particular context of systems analysis, our findings motivate the development of robust methods that exploit sparsity in the system's governing equations and result in sparse polynomial non-negativity conditions. In Section VI-D, we have done this by choosing a Lyapunov function with a structure such that the correlative sparsity of the governing equations is inherited by the eventual non-negativity constraints, but this construction was made possible by the simplicity of our example. Identifying a general procedure to formulate sparse SOS conditions will therefore be essential to enable the analysis of complex, large-scale sparse systems.


extfieldsofstudy:
Computer Science
Medicine

text:
CMTN-SP: A Novel Coverage-Control Algorithm for Moving-Target Nodes Based on Sensing Probability Model in Sensor Networks

The non-consecutive coverage problem for the target nodes in Sensor Networks could lead to the coverage blind area and a large amount of redundant data, which causes the bottleneck phenomenon for the communication link. A novel Coverage Control Algorithm for Moving Target Nodes Based on Sensing Probability Model (CMTN-SP) is proposed in this work. Firstly, according to the probability theory, we derive the calculation method for the expectation of the coverage quality with multiple joint nodes, which aims to reduce the coverage blind area and improving network coverage rate. Secondly, we employ the dynamic transferring mechanism of the nodes to re-optimize the deployment of the nodes, which alleviates the rapid exhaustion of the proper network energy. Finally, it is verified via the results of the simulation that the network coverage quality could not only be improved by the proposed algorithm, but the proposed algorithm could also effectively curb the rapid exhaustion of the node energy.

Introduction
The sensor network is a large-scale and self-organized sensing network which could achieve the information world integration and the physical world integration [1][2][3][4][5]. The deployment of this network is achieved by densely and randomly deploying the nodes which are in the monitoring area, while the sensor nodes behavior is mainly characterized by: a certain degree of computation, communication, storage and control ability, which could accomplish the collection, communication, computation, and storage of the information from the physical world [6][7][8][9]. The high-speed visual sensors are adopted by this work. The main characteristics of this sensor are listed below. (1) Data collection unit. The data collection unit is mainly composed by the sensor and the analog/digit converter, where the data collection module is mainly in charge of collecting the mobile data and the analog/digit converter is in charge of converting the collected analog signal into digital signal.
(2) Control unit. The control unit is in charge of the running of the entire sensor node, which is normally composed of the micro-processor and the memory. The function of the micro-processor is to perform the real-time processing on the data collected by the node and received from other nodes. On the other hand, the function of memory is to store the temporary data collected by the node and received from other nodes. (3) Communication unit. The wireless communication unit is in charge of the communication between different sensor nodes, exchanging control messages and transcribing data. (4) Power unit. The power unit is in charge of powering the sensor nodes to guarantee the functioning.
It is crucial to the secure and reliable working of the entire network. The coverage problem is crucial to the study of the Sensor Network and closely related to the other research fields of Sensor Network, e.g., node positioning, target tracking, node deployment, time synchronization, data fusion, and node energy consumption [10][11][12][13][14]. The three heated topics of the coverage problem in Sensor Network are (1) how to increase the coverage rate which is effective on the area of monitoring, (2) how to curb the rapid energy exhaustion of the nodes to prolong the network lifetime, and (3) how to use the minimal nodes number to satisfy the required coverage rate for the users in the area of monitoring.
In the covering process on the node which is the target node, usually the full coverage over the entire monitoring area is employed [15][16][17]. However, we utilize the partial consecutive coverage, focusing on the target node. That is, we only consecutively cover the moving target node which we focus on. The main reasons behind this are that (1) during the whole operation period of this network, putting all the nodes into work would rapidly exhaust the node energy, and (2) the required coverage degrees of different monitoring areas are different when we re-partition the whole monitoring area. Therefore, the network energy would also quickly run out if we put all the nodes in the monitoring area into work. Finally, (3) During the consecutive coverage process over the moving node, the coverage blind area would exist since some nodes are dead or not awakened by some algorithm. We take the moving target node as an example and give the illustration of the consecutive coverage, which is shown in Figure 1. guarantee the functioning. It is crucial to the secure and reliable working of the entire network. The coverage problem is crucial to the study of the Sensor Network and closely related to the other research fields of Sensor Network, e.g., node positioning, target tracking, node deployment, time synchronization, data fusion, and node energy consumption [10][11][12][13][14]. The three heated topics of the coverage problem in Sensor Network are (1) how to increase the coverage rate which is effective on the area of monitoring, (2) how to curb the rapid energy exhaustion of the nodes to prolong the network lifetime, and (3) how to use the minimal nodes number to satisfy the required coverage rate for the users in the area of monitoring.
In the covering process on the node which is the target node, usually the full coverage over the entire monitoring area is employed [15][16][17]. However, we utilize the partial consecutive coverage, focusing on the target node. That is, we only consecutively cover the moving target node which we focus on. The main reasons behind this are that (1) during the whole operation period of this network, putting all the nodes into work would rapidly exhaust the node energy, and (2) the required coverage degrees of different monitoring areas are different when we re-partition the whole monitoring area. Therefore, the network energy would also quickly run out if we put all the nodes in the monitoring area into work. Finally, (3) During the consecutive coverage process over the moving node, the coverage blind area would exist since some nodes are dead or not awakened by some algorithm. We take the moving target node as an example and give the illustration of the consecutive coverage, which is shown in Figure 1. Based on the analysis above, this work mainly focuses on the following four aspects.
(1) We establish the sensing model according to the probability model and utilize the normal distribution feature of multiple nodes to derive the expectation of the coverage quality, aiming to have the coverage rate improved in the area of monitoring.
(2) When a certain coverage rate is satisfied, the result in (1) is employed to derive the calculation method for the minimal nodes number in the area which is monitored, and we further introduce the controllable parameters to achieve the coverage which is effective over the target node that is moving.
(3) According to the curbing of the consumption of the energy, we exploit the dynamic transferring mechanism of the nodes to optimize the deployment and re-partitioning of the nodes. Meanwhile, we perform the resource integration over the nodes which are in the monitoring area to achieve the balance of the energy in the whole network.
(4) Via the simulations, we perform comparisons on the coverage rate of the network, network lifetime, and the quantity of the nodes which are survived, which further verifies the effectiveness of the proposed algorithm. Based on the analysis above, this work mainly focuses on the following four aspects.
(1) We establish the sensing model according to the probability model and utilize the normal distribution feature of multiple nodes to derive the expectation of the coverage quality, aiming to have the coverage rate improved in the area of monitoring.
(2) When a certain coverage rate is satisfied, the result in (1) is employed to derive the calculation method for the minimal nodes number in the area which is monitored, and we further introduce the controllable parameters to achieve the coverage which is effective over the target node that is moving.
(3) According to the curbing of the consumption of the energy, we exploit the dynamic transferring mechanism of the nodes to optimize the deployment and re-partitioning of the nodes. Meanwhile, we perform the resource integration over the nodes which are in the monitoring area to achieve the balance of the energy in the whole network.
(4) Via the simulations, we perform comparisons on the coverage rate of the network, network lifetime, and the quantity of the nodes which are survived, which further verifies the effectiveness of the proposed algorithm.

Materials and Methods
Recently, the network coverage problem has become a heated topic in the study of Sensor Network. Many researchers in the world has conducted some effective research work and got some results. Liu et al. [7] proposed a probabilistic coverage model based on a circle region in 2005. Li et al. [11] proposed deployment entropy to measure the deployment quantitatively. From the results of the deployment entropy, a scheme of activating pre-deployed sensors is provided to meet the goal of waking up sensors as little as possible to obtain a desirable sensing coverage. The work in Reference [18] mainly studied the impacts of the range and maximum of the particle's flying speed on the network coverage optimization process. Furthermore, the range of the varying network coverage rate with different number of nodes is also determined. A Multiround Distributed Lifetime Coverage Optimization Protocol (MuDiLCO) was proposed in Reference [19]. This protocol first divides the target area into several subareas and then distributes the MuDiLCO protocol to all the nodes which are called the sensor nodes in each subarea. This protocol works when the set of sensor nodes are scheduled and remain active in the sensing period. Therefore, it determines the sensing coverage area. An Optimized Coverage Algorithm in Probability Model (OCPM) was proposed in Reference [20], which performs investigation and analysis on the sensing model to find the membership between the nodes and the target node coverage. Then it conducts the theoretical calculation and derivation on the rate of the network coverage and gives the calculation method for the deviation when the node covers multiple target nodes simultaneously. A Complex Alliance Strategy with Multi-objective Optimization of Coverage (CASMOC) was proposed in Reference [21]. This strategy employs the proportional relationship between the energy transferring functions of the working node and the neighboring nodes. This proportional relationship is applied to the scheduling of the low-energy moving nodes to achieve the whole network energy balance, optimize the resources of the network and improve the network coverage rate. The Reuleaux Geometry Triangle was employed in Reference [22] to design a Probabilistic Detection Algorithm (PDA). This algorithm first divides the monitoring area in geometry according to the users' requirement on the coverage rate and then performs the dynamic clustering on the nodes according to the sensing ability of the nodes. The coverage which is effective over the whole area being monitored is achieved via the centralized coverage among different clusters. A Convoy Tree based Fuzzy Target Tracking (CTFTT) algorithm was proposed in Reference [23], which employs the tree-like structure to establish a tree structure focusing on the local node and the neighbor node. It does this by deleting the dead nodes off the tree and adding new nodes to the tree to dynamically update the target tree. Meanwhile, the ambiguity sensing model was exploited to extend, contract, and reconstruct the tree, which accomplishes the effective coverage over the monitoring area. A new Distributed Approach Algorithm Based Trust among Sensor Nodes (DTA) was proposed in Reference [24], which utilizes the sensing ability of the nodes and the remained energy to achieve the effective coverage which is effective over the target nodes. The main idea is to divide the randomly deployed nodes into several clusters while each node in the cluster submits its current state information to the cluster head. Then, the working cluster is determined via the comparison on the cluster energy and the state transferring mechanism of the cluster heads, which achieves the coverage over the target node. Vector of Locally Aggregated Descriptors (VLAD) was proposed in Reference [25]. This algorithm employs the redundancy feature of the nodes to determine the coverage rate and uses the controllability, which is adaptable to the variation of the function, to decline the coverage rate, which is redundant. Therefore, the coverage rate of the network is improved. Deployment entropy was proposed in Reference [26], which is to measure the deployment quantitatively. By the results of the deployment entropy, a scheme of activating pre-deployed sensors is provide to meet the goal of waking up sensors as less as possible to obtain a desirable sensing coverage.
For the entire monitoring area or the target nodes, the algorithms mentioned above could improve the network coverage rate. But there are some deficiencies: (1) some algorithms do not consider the change of the network lifetime when they are performed. (2) The network model is ideal and ignores the boundary effect. (3) The state transferring mechanism and the power allocation mechanism of the nodes are not considered in the coverage process, which causes the rapid exhaustion of the network energy. (4) When the data is relayed, the redundant data problem exists and the routing has to be re-chosen.
Therefore, this work is based on the probability theory and employs the membership between the target node and the node to derive the expectation of the joint coverage with multiple nodes. Based on this, we further give the calculation method for the minimal number of required nodes. In addition, we introduce the controllable parameter to accomplish the coverage which is effective over the whole area which is monitoring. In terms of the energy efficiency, the dynamic clustering algorithm is used to perform the re-integration and scheduling of the nodes within the area which is being monitored to achieve the energy balance of the network.

Assumption and Definition
For further analysis of the algorithm which is proposed to achieve the effective coverage, the proposed algorithm satisfies the following assumption: (1) Then sensor nodes are randomly deployed in the area which is being monitored. The initial energy of all nodes is the same. The sensing area is in the shape of a circle [27]. (2) The monitoring area, which is in the shape of a square, is large enough and the edge length is far larger than the sensing radius. (3) An arbitrary node could acquire its location information via the positioning algorithms, e.g., RSSI and DTOA [28]. (4) The deployments of the nodes are normally distributed and the communication radius is at least twice as large as the sensing radius [29][30][31].

Definition 1. (Coverage Region):
The coverage region is defined as the overall area covered by all the deployed sensor nodes.

Definition 2. (Coverage Quality):
Within the area which is being monitored, the quality of the coverage is defined as the ratio of the union set of all the nodes' coverage area to the monitoring area.
where C q is the coverage quality and area(A) is the size of the monitoring area and s i is the coverage area of node i.

Definition 3. (Coverage Efficiency):
The coverage efficiency is the definition of the ratio of union set of all the nodes' coverage area to the summation of all the nodes' coverage area.
where C e is the coverage efficiency and s i is the coverage area of node i.

Definition 4. (Coverage Evenness):
Normally, the coverage evenness is defined as the standard deviation of the distance from the reference nodes to the nodes which are neighbor nodes. where E v is the coverage evenness and N is the quantity of nodes, NE i is the quantity of neighbor nodes for node i, D(i,j) is the distance between node i and node j and d i is the average distance from all the nodes which intersect with node i.

Definition 5. (Network Lifetime):
The lifetime of the network is defined as the duration of time from the initial time to the time that arbitrary sensor node could not cover an arbitrary target node.

Definition 6. (Coverage Time):
The coverage time is defined as the longest time from the start to the completion of coverage among all the nodes.

Coverage Quality
For the convenience of research, we assume that the monitoring area is square and N sensor nodes are randomly deployed. We take an arbitrary sensor node as the reference node, and its sensing radius R 0 obeys the normal distribution N(R 0 , δ 2 ). The average sensing radius in the monitoring area for the nodes is R a . When the user's required coverage rate and the communication between nodes and their neighboring nodes are guaranteed, we do not achieve the full coverage over the entire monitoring area. Instead, we only perform consecutive coverage over the moving target node and make sure that the coverage rate varies within a reasonable range.

Theorem 1.
Assuming that the area of a monitoring area is A and the number of working nodes is N, then the expectation of the coverage quality in this area is E( Proof. Since we deployed the nodes at a certain monitoring area randomly and the sensing radius R i of an arbitrary node follows the normal distribution, the coverage rate for an arbitrary node a within the monitoring area is: And the probability that an arbitrary node M within the monitoring area is covered by R a is: We consider R 0 the sensing radius for the considered reference node and R a is assumed to be the sensing radius of an arbitrary sensor node within this area, according to the probability density function of the normal distribution, thus we have: and we have: Firstly, we perform the first integration: Calculated by using the step-by-step integration method: Then we perform the second integration method. According to the symmetry of the function: Next, we calculate the third integration: We further calculate Equation (13) and get the following result: Since the working nodes are assumed to be mutually independent, when an arbitrary moving target node M which is in the monitoring area is covered jointly by k nodes at least, according to the Binomial theorem, we can derive the expectation of the coverage quality: It is shown via Equation (15) that when the node which is the target is covered jointly by N nodes at least, the expectation of the coverage quality is: This completes the proof. Corollary 1. The minimal number of the nodes which is required to satisfy the expected coverage quality above Proof. When an arbitrary moving node M which is the target node and is covered by only one sensor node, the expected coverage quality should be no larger than that when the node which is the target is covered by multiple nodes jointly. We assume the average sensing radius is R a and it is derived from Equation (16) that: If we take the logarithmic operation on both sides, it is derived that: This completes the proof.

Redundant Coverage
In order to guarantee the consecutive coverage which is in the monitoring area over the moving target node and reduce the quantity of redundant nodes and redundant data, we analyze the degree of redundant coverage. We assume the monitoring area is a double square where the outer square is not the focusing area for the moving target node, while the inner square is the focusing area for the target node which is moving while the inner square is the focusing area for the target node which is moving. Generally speaking, the existence of other redundant nodes is ignored for investigation convenience. The illustration of the degree of redundant coverage is shown in Figure 2.

Redundant Coverage
In order to guarantee the consecutive coverage which is in the monitoring area over the moving target node and reduce the quantity of redundant nodes and redundant data, we analyze the degree of redundant coverage. We assume the monitoring area is a double square where the outer square is not the focusing area for the moving target node, while the inner square is the focusing area for the target node which is moving while the inner square is the focusing area for the target node which is moving. Generally speaking, the existence of other redundant nodes is ignored for investigation convenience. The illustration of the degree of redundant coverage is shown in Figure 2.

Definition 7. (Redundant Node):
When the threshold is higher than the Euclidean distance between two arbitrary nodes, this node is defined as the redundant node, i.e., d(si, sj) < ε(l).

Definition 8. (Degree of Redundant Coverage):
When node si and its neighboring node are redundant nodes, the degree of redundant coverage is defined as the ratio of its neighbor's coverage area to its own coverage area.
Proof. Now we consider Figure 2 and assume that ∠BCE = α and λ is a controllable parameter, i.e., BC = λRa, λ ∈ (0, 2]. We further assume that the distance l between B and C is a random variable with the following distribution: The size of the overlapped area between these two points is: If we set this distance to be BC = l, we have:

Definition 7. (Redundant Node):
When the threshold is higher than the Euclidean distance between two arbitrary nodes, this node is defined as the redundant node, i.e., d(s i , s j ) < ε(l).

Definition 8. (Degree of Redundant Coverage):
When node s i and its neighboring node are redundant nodes, the degree of redundant coverage is defined as the ratio of its neighbor's coverage area to its own coverage area.
Theorem 2. The degree of redundant coverage for arbitrary n neighbor nodes centering an arbitrary node s i and sharing the same sensing radius R a is derived as follows Proof. Now we consider Figure 2 and assume that ∠BCE = α and λ is a controllable parameter, i.e., BC = λR a , λ ∈ (0, 2]. We further assume that the distance l between B and C is a random variable with the following distribution: The size of the overlapped area between these two points is: If we set this distance to be BC = l, we have: After substituting Equation (21) into the probability density function, we have: We further calculate Equation (22) as: According to the Definition 7 and Definition 8, the degree of redundant coverage for the neighbor node of an arbitrary node s i is: Substituting Equation (23) into Equation (24), we have: The degree of redundant coverage formed by n neighboring nodes centering this redundant node s i with sensing radius R a is as follows: This completes the proof.

Expectation of First Covarage
The expectation of the coverage quality within the monitoring area is presented in Theorem 1 and the degree of redundant coverage is given in Theorem 2. Now we focus on the expectation of first coverage when the sensor nodes firstly covered the path of the target node which is moving. After acquiring this expectation, this node could utilize the awakening mechanism to make the subsequent nodes accomplish the coverage task over the moving target node with the same or approximate expectation value. Therefore, we introduce Theorems 3, 4, and 5. Proof. We assume the random variable X is the number of transferring within unit time and X ∈ [1, 2, . . . , Q]. When X = m, the target node which is moving is not covered for the first Q − 1 times if and only if m < Q − 1, where the probability density function for the distribution of X is: Then we derive the expectation as follows: Multiply q at both sides of the equation and further simplify the equation, we have: Substituting q = 1 − C p into Equation (30), we have: Substituting Equation (31) into Equation (28), we have: This completes the proof.
When one moving target node moves across the monitoring area, we perform data fitting on the path of the moving target node and give the function of the node trajectory. f 1 (x) = δ n x n + δ n−1 x n−1 + δ n−2 x n−2 + · · · + δ 1 x 1 + ξ Set the range of value for δ to be δ ∈ [0, 1]. In order to calculate the size of the shadowed area, we establish the 2-dimension panel and mark the Y-axis and the X-axis. The area which is shadowed and the partial shape between sensor nodes a and b, as well as the node p, which is a sensor node at the lower-left corner, are shown in Figure 3.
Substituting Equation (31) into Equation (28), we have: This completes the proof. □ When one moving target node moves across the monitoring area, we perform data fitting on the path of the moving target node and give the function of the node trajectory.
Set the range of value for δ to be δ ∈[0, 1]. In order to calculate the size of the shadowed area, we establish the 2-dimension panel and mark the Y-axis and the X-axis. The area which is shadowed and the partial shape between sensor nodes a and b, as well as the node p, which is a sensor node at the lower-left corner, are shown in Figure 3. In Figure 3, while the intersection point is the origin, we make Y-axis and X-axis to move through the centers of sensor nodes b and a. Then we connect sensor nodes a and b and assume that the cutting point is c. The trajectory of the target node which is moving and the X-axis intersect at point e. The trajectory of the target node which is moving and the Y-axis intersect at point d. The coordinate of node a is (xa, 0) while that for node b is (0, yb). Since the point c is the cutting point In Figure 3, while the intersection point is the origin, we make Y-axis and X-axis to move through the centers of sensor nodes b and a. Then we connect sensor nodes a and b and assume that the cutting point is c. The trajectory of the target node which is moving and the X-axis intersect at point e. The trajectory of the target node which is moving and the Y-axis intersect at point d. The coordinate of node a is (x a , 0) while that for node b is (0, y b ). Since the point c is the cutting point between node a and node b, the coordinate of node c is (0.5x, 0.5y) while those for node e and node d are (x a + r, 0) and (0, y b + r), respectively. The size of the shadowed area in Figure 3 is equal to the area surrounded by axis-X and axis-Y minus the size of a lower corner and one circle. As for the lower corner size, we can also perform the data fitting to give an equation. Set b∈ [0, 1], the equation for the curve is: And the size of the shadowed area is: Substituting Equations (33) and (34) into (35), we have: Theorem 4. Without the loss of any generality, if a void exists and the g(x) and the void curves f(x) are consecutive and derivable, after that, the difference value between the sizes of the two voids is no smaller than the sum of the sizes of two externally tangent circle sectors. Figure 3, if we move the coordinate of the X-axis and the Y-axis to O', we have new coordinate axes X' and Y'. The sensor node a intersects with Y' at n and m and the angle formed is β. Similarly, sensor node b intersects with the X' axis at point f and g and the angle formed is α. Due to the existence of voids, ∆S = |S 1 − S 2 − S fan | ≥ 0. According to Equations (35) and (36), we have:

Proof. As shown in
And since S fan = 2πr 2 − [r 2 (α + β)/2], we substitute this into Equation (37) and have the following result: (38) Due to the existence of voids, ∆S ≥ 0. Therefore, And the proof is completed.
In theorem 4, we can obtain that when {0 ≤ α ≤ π}∩{0 ≤ β ≤ π}, the area of void that needs to be filled is at least 2πr 2 . If the angles α and β lies between [π, 2π], then the area of void that needs to be filled is at least πr 2 . Proof. ince x ≥ 0 and consecutive and derivable on [0, a], |f 0 (x)| is consecutive on [0, a]. Therefore, |f 0 (x)| has a maximum on [0, a], which is denoted as M. That is, M is the maximum value in the range and it is equal to M = max 0≤x≤a | f 0 (x)|. Since: Since |f 0 (x)| is consecutive on [0, a], |f 0 (x)| has a maximum value M on [0, a]. Therefore: Since Equation (41) is convergent on x ∈ [0, 1], convergent. This proof is completed.

Algorithm Ideas
The Coverage Control Algorithm for Moving Target Nodes based on Sensing Probability (CMTN-SP) algorithm employs the dynamic clustering mechanism to set some nodes as the cluster heads and the cluster heads could form one backbone network with self-processing ability and relaying data. For other non-backbone network nodes, they can switch into sleep state by the node state transferring mechanism to save the energy consumption [32][33][34][35]. The organization forms of clusters are mainly characterized by the fact that each cluster is composed of one cluster head and several cluster members. The cluster members could communicate directly or indirectly with the cluster head. When there is a common member between different clusters, the communication can be accomplished via the gateway node [36][37][38][39]. The cluster head is mainly in charge of transmitting and receiving the data information within the cluster, data fusion and data storage. The data communication among the cluster members or between the cluster member and the cluster head can be performed in a time division duplexing manner, to avoid the collision of data packets and packet losses. On the other hand, the nodes not in the communication are switched to sleep state to save the energy consumption. When the cluster heads receive the response messages from the cluster members, the cluster heads assign the working time slots to the cluster member node, which accomplishes the time synchronization.
The proposed algorithm is carried out mainly in three periods: (1) formation of the clusters, (2) election of the cluster heads, and (3) dynamic changes. Firstly, when the other nodes receive the request frames from the node with higher remaining energy, they calculate the distance to this node according to the location information and perform comparison on distance in the local topology structured list. If this distance is smaller than the threshold, the topology structured list bit is changed to 1. Otherwise, it is changed to 0. After one or more time rounds, the nodes satisfying the conditions are put into a set, which forms the cluster. Secondly, in the cluster head election period, the nodes with more remaining energy are mainly in charge of electing the node with the maximal coverage expectation as the head of the cluster. The cluster head which is elected sends a request frame to the cluster members in a flooding schedule, which contains the ID and location information of this cluster head. This request also serves as a declaration of election. For the convenience of management, this cluster head establish a dynamic link to store the cluster members the remaining energy, the distances among cluster members, the ID of the members and the cluster members sensing radius. Thirdly, since the cluster head is in charge of many tasks, the energy consumption is quick for this node. Furthermore, the energy imbalance among the cluster members leads to the problem that the total energy of this cluster could not sustain the energy consumption after many rounds of tasks. Therefore, in order to guarantee the subsequent work, we need to perform another round of division and integration for the clusters with lower total energy. In the dynamic cluster partition process, we need to consider the node remaining energy in the local topology structured list, expectation of the coverage and the distance among nodes. Then we choose the appropriate node as the cluster head. After that, according to the distance among nodes, we search for the nodes with bit 1 in the local topology structured list and form a cluster with these nodes.
When the time duration of an event is long, the cluster energy would quickly run out if the cluster head is fixed [40][41][42][43]. Therefore, we have to perform the switching of the cluster head and in this switching process, we need to consider the round of data transmission, node HTS (Hop To mobile Sink) value and the remaining energy to choose a cluster head. Therefore, we can balance the responsibility of the cluster head and save the energy consumption of cluster reformation. When the best candidate node does not have enough energy to perform the cluster reformation, the current cluster head sends a PCM (Position Calculation Message, binary tuple <Type, E_ID>) message to the MS (Mobile Sink), which aims to timely urge the MS to perform the quasi-optimal location computation, update the network routing structure, and reduce the event field data loss caused by the absence of cluster heads.

Realization of Algorithm
Step 1: Calculate the expectation of coverage and sensing properties for all the nodes and store in the local topology structured list.
Step 2: Search for the node in the topology structured list satisfying the condition as the cluster head.
Step 3: The cluster heads broadcast the request frame in a flooding schedule that includes this cluster head ID.
Step 4: After the cluster members receive the request frame, they send the response message to the cluster head, containing the cluster member's ID, remaining energy, sensing property, etc. These messages are stored in the local topology structured list of the cluster head.
Step 5: The nodes not in the local topology structured list of the cluster head are switched into sleep mode.
Step 6: After many unit rounds, perform the comparison on the data stored in the local topology structured list of the cluster head. Select the nodes satisfying the condition as the new cluster head and turn to Step 3.
Step 7: When the total energy of this cluster is below the threshold ε, this cluster is dismissed.

Algorithm Complexity
We proposed a distributed algorithm in this work and the complexity of this algorithm includes the time complexity and spatial complexity. The number of nodes transmitting data within the cluster is k, the total quantity of the nodes is N, and k ≤ N. If all the nodes transmitting data share the same node energy and are time synchronized, the complexity of the time of the CMTN-SP algorithm is O(k) at its best. Otherwise, the time complexity is O(klogk). In terms of the spatial complexity, since the number of transmitting-data nodes k is determined in advance, the time complexity is therefore O(k).

System Evaluation
For verifying the stability and the effectiveness of this algorithm, we employ the platform, MATLAB 7.0, to carry out simulations and make comparisons with the PDA [22], DAT [24] and VLAD [25] algorithms in terms of the coverage rate of the network, network lifetime, and the quantity of survived nodes. The performances are listed in Table 1. The network coverage performances versus the number of sensor nodes under different monitoring area are illustrated with δ = 0.3 and δ = 0.8 form Figures 4-6, respectively. It is shown in the figures that the network coverage rate increases for all the four algorithms with the number of sensor nodes. Generally, the proposed algorithm outperforms the other three algorithms in terms of the network coverage rate. It is shown in Figure 4 that when the number of nodes is equal to 200, the coverage rate of the proposed algorithm is 80.2% and 75.4%, while those for the other algorithms are 72.1%, 69.95%, and 68.01%, which is below the performance of the proposed algorithm. It is shown in Figure 5 that when the monitoring area is 400 × 400 m 2 and the number of sensor nodes is 300, the proposed algorithm shows a more prominent increase in network coverage rate than the others. The main reason behind this is that we adopt the controllable parameter λ to adjust the coverage rate within the entire monitoring area, so that we can adjust to the changing coverage rate during the consecutive coverage over the moving target node. The network coverage rate is improved by 16.32% on average. The analysis process in Figures 6 and 7 is similar to that in Figures 4 and 5. The comparison on the network coverage rate with δ = 0.3 and δ = 0.8 is also presented in Figures 8 and 9 for the moving target node. We can see that with an increasing number of moving target node, the network coverage rate decreases for all the four algorithms. But the proposed algorithm shows the least magnitude of decrease, which does not influence the coverage effect over the entire network. The main reason behind this is that the controllable parameter could maintain the network coverage within a certain range, which guarantees the robustness and scalability for the proposed algorithm.               Figures 10-13 give the network lifetime performance versus the number of sensor nodes with δ = 0.3 and δ = 0.8. It is shown from the figures that with an increasing number of sensor nodes, the network lifetime is prolonged for all the four algorithms. In Figure 10, when the number of sensor nodes is 250, the network lifetime of the proposed algorithm is 450 s and 420 s, while those for the other algorithms are 410 s, 305 s and 295 s. In Figure 11, when the number of nodes is 500, the network lifetime of the proposed algorithm is 520 s and 400 s while those for the other algorithms are 380 s, 340 s, and 240 s. The main reason behind this is that the other three algorithms employ the centralized coverage while we employ the distributed coverage. Meanwhile, the other three algorithms do not consider the transformation process among different nodes and they require more energy consumption for the network. The proposed algorithm increases the network lifetime by 13.07% compared with the other three algorithms. The network lifetime versus the number of moving target nodes with δ = 0.3 and δ = 0.8 are shown in Figures 14 and 15. It is shown that with an increasing number of moving target nodes, the network lifetime of all the four algorithms are decreased. We take Figure 14 as an example. When the number of moving target nodes is 6, the magnitude of decrease is larger for the other three algorithms. The main reason behind this is that the other three algorithms employs the centralized coverage scheme, without considering the coordination among different nodes, which leads to the rapid exhaustion of these three algorithms and a shorter network lifetime compared with the proposed algorithm.  Figures 10-13 give the network lifetime performance versus the number of sensor nodes with δ = 0.3 and δ = 0.8. It is shown from the figures that with an increasing number of sensor nodes, the network lifetime is prolonged for all the four algorithms. In Figure 10, when the number of sensor nodes is 250, the network lifetime of the proposed algorithm is 450 s and 420 s, while those for the other algorithms are 410 s, 305 s and 295 s. In Figure 11, when the number of nodes is 500, the network lifetime of the proposed algorithm is 520 s and 400 s while those for the other algorithms are 380 s, 340 s, and 240 s. The main reason behind this is that the other three algorithms employ the centralized coverage while we employ the distributed coverage. Meanwhile, the other three algorithms do not consider the transformation process among different nodes and they require more energy consumption for the network. The proposed algorithm increases the network lifetime by 13.07% compared with the other three algorithms. The network lifetime versus the number of moving target nodes with δ = 0.3 and δ = 0.8 are shown in Figures 14 and 15. It is shown that with an increasing number of moving target nodes, the network lifetime of all the four algorithms are decreased. We take Figure 14 as an example. When the number of moving target nodes is 6, the magnitude of decrease is larger for the other three algorithms. The main reason behind this is that the other three algorithms employs the centralized coverage scheme, without considering the coordination among different nodes, which leads to the rapid exhaustion of these three algorithms and a shorter network lifetime compared with the proposed algorithm. an increasing number of moving target nodes, the network lifetime of all the four algorithms are decreased. We take Figure 14 as an example. When the number of moving target nodes is 6, the magnitude of decrease is larger for the other three algorithms. The main reason behind this is that the other three algorithms employs the centralized coverage scheme, without considering the coordination among different nodes, which leads to the rapid exhaustion of these three algorithms and a shorter network lifetime compared with the proposed algorithm.          Form Figures 16-19 give the number of working nodes versus the total number of nodes with δ = 0.3 and δ = 0.8. It is shown in the figures that with the increase in the total number of nodes, the number of working nodes remain relatively steady for all the four algorithms. However, the required number of working nodes of the proposed CMTN-SP algorithm is smaller than the other algorithms, which is 8.26%. The main reason behind this is that the proposed algorithm performs consecutive coverage over the focused moving target node while the other nodes not participating in the coverage or the redundant nodes are switched into sleep state or overhearing state to prolong the network lifetime. By contrast, the other three algorithms perform the consecutive coverage over  Form Figures 16-19 give the number of working nodes versus the total number of nodes with δ = 0.3 and δ = 0.8. It is shown in the figures that with the increase in the total number of nodes, the number of working nodes remain relatively steady for all the four algorithms. However, the required number of working nodes of the proposed CMTN-SP algorithm is smaller than the other algorithms, which is 8.26%. The main reason behind this is that the proposed algorithm performs consecutive coverage over the focused moving target node while the other nodes not participating in the coverage or the redundant nodes are switched into sleep state or overhearing state to prolong the network lifetime. By contrast, the other three algorithms perform the consecutive coverage over the entire monitoring area and only parts of the nodes are switched into sleep state or overhearing Form Figures 16-19 give the number of working nodes versus the total number of nodes with δ = 0.3 and δ = 0.8. It is shown in the figures that with the increase in the total number of nodes, the number of working nodes remain relatively steady for all the four algorithms. However, the required number of working nodes of the proposed CMTN-SP algorithm is smaller than the other algorithms, which is 8.26%. The main reason behind this is that the proposed algorithm performs consecutive coverage over the focused moving target node while the other nodes not participating in the coverage or the redundant nodes are switched into sleep state or overhearing state to prolong the network lifetime. By contrast, the other three algorithms perform the consecutive coverage over the entire monitoring area and only parts of the nodes are switched into sleep state or overhearing state.

Conclusions
This paper first analyzed and investigated the coverage condition of the moving target node. Based on this, a Coverage Control Algorithm for Moving Target Nodes Based on Sensing Probability Model was proposed. According to the normal distribution function, this proposed algorithm gave the derivation method for the network coverage quality and the minimal number of nodes. Then we analyzed and investigated the generation of the redundant data and further presented the calculation method for the degree of redundant coverage. In terms of the realization of this algorithm, we gave the key ideas and the detailed description of the CMTN-SP algorithm, as well as the complexity of this algorithm. Finally, we verified via simulations the network coverage rate, network lifetime and the number of working nodes for the proposed algorithm, in comparison with the other three algorithms. The simulation results proved the effectiveness and the stability of the proposed algorithm.