1.   Introduction

Mobile sensor networks (MSNs) have attracted increasing research attention and found various applications in the past decade [1], [2]. For a practical MSN, energy limitation is always one of the most important and challenging issues. The reason lies in the batteries powering the MSNs, which are limited in capacity and inconvenient for replacement. Besides, a typical MSN consists of a mass of energy-demanding nodes capable of sensing, computing, communicating and moving. As such, energy efficient algorithms are of utmost importance for MSN applications, hence, are the focus of many research works. To name a few, by modeling power consumption as the distance traveled by the sensors, [3]-[5] investigated the power-constrained deployment and coverage control issues of MSNs. In [6], an energy aware control protocol was proposed to achieve rendezvous without depleting the energy of the nodes. Based on the energy forecast, [7] designed a clustering-tree topology control algorithm to save energy and maximize the network lifetime for heterogeneous wireless sensor networks with considering packet loss rate and the link quality.

In most cases, the cost saving problem is complicated, since it is often realized at the cost of a certain degree of performance loss. Therefore, the intention of most papers comes down to finding a trade-off of energy usage and system performance, which refers to quality of performance (QoP) for control and estimation problems, and to quality of service (QoS) for communication problems. For instance, [8] investigated the compromise of communication cost and the convergence rate (a QoP indicator), and [9] studied the trade-off between energy expenditure and communication delay (a QoS parameter).

Here we aim at the issue of consensus seeking of MSNs subject to limited cost supply. Of course, it is not the first time that this problem is being addressed. There have been some results reported in the literature. For instance, [10] considered the energy-constrained consensus estimation issue by activating a subset of sensors at each instant. In [11], an optimal consensus controller design method was given to minimize the power cost of sensors deployed in smart home systems. Reference [12] proposed an LQR consensus algorithm for multi-vehicle control. In [13], a sub-optimal consensus control algorithm for MSNs was presented by modeling the energy expenditure for mobility and communication independently. Most of these results assume static communication topologies in the MSNs. In practice, however, the network topology may vary with link failures, packet dropouts or environmental disturbances. As these factors are random by nature, the switching of topologies is essentially a random event modeled as a stochastic process, in particular, a Markov chain [14]. In fact, a number of papers have studied MSNs with Markov switching topologies under different frameworks with various concerns, see, e.g., in [15]-[21]. However, it should be noted that several important factors have not been considered in the existing results. Firstly, most of these works concern ergodic Markov chains, while a more general Markov chain is more interesting, since when a system goes through an unsteady environment to a settled one, it will reasonably experience switching from variable topology to a certain fixed one. Secondly, almost all the existing results are applied to situations with completely known transition probabilities. In reality, however, all or part of the transition probabilities are unavailable [22]-[25], and only the estimated values of transition rates are accessible. Moreover, estimation errors, referred to as probability uncertainties of switching topology, may also result in instability or at least degrade performance of MSNs. Thus, it is of great importance to consider partially unavailable transition rates, which do not need any knowledge of the unavailable elements. Thirdly, existing works do not consider cost limitations.

In this paper, we study the guaranteed cost consensus seeking problem for MSNs with switching communication topologies governed by a Markov chain whose initial and transition probabilities are partially unknown. A team of mobile sensors cooperate with each other and form a network whose topologies are switching within a topology set according to a Markov chain. Each directed graph in the graph set is assumed to have a spanning tree. A novel function of team cost which penalizes the state and control input errors between communicating sensors is defined in a linear quadratic form, in which cost consumption for information receiving and sending is involved. The elements of the transition probability matrix are divided into the known and unknown parts. Then, using model transformation and graph theory, the issue of guaranteed cost consensus is transformed to the stability problem of a reduced order Markov jump systems with partially unknown initial and transition probabilities. Using stochastic Lyapunov functional method, a sufficient mean square stability condition is obtained for the reduced order jumping system, which guarantees global exponential consensus of the original MSN in the mean square sense. Then, a computational algorithm is given, by which the sub-optimal controller gains and a sub-minimal upper cost bound of the MSN can be calculated, concurrently. The validity of the controller design method is illustrated by example results.

The remaining sections are organized as follows. Section 2 provides some preliminaries of graph theory, Markov switching topology and the problem formulation. The main results on sufficient consensus condition are presented in Section 3. Then, a controller design algorithm of sensor networks is derived. In Section 4, numerical examples are given to validate the performance of the proposed method. Section 5 draws a conclusion.

Notations: $\mathbb{R}^{n }$ and $\mathbb{R}^{n\times m}$ denotes $n$ dimensional Euclidean space and the family of dimensional real matrices, respectively. $I_{n}$ stands for $n$ dimensional identity matrix. For a given matrix $X$ , $\| X \|$ denotes its Euclidean norm, $X^{T}$ denotes its transpose, and $X^{-1}$ denotes its inverse matrix (if square matrix $X$ is nonsingular). And ${\rm diag}\{\cdot\} $ denotes a block-diagonal matrix. The sign $\otimes $ represents Kronecker product of matrix. 0 denotes a column vector whose entries equal to zero. The similar notation is adopted for 1. ${\rm Pro}(y)$ and ${E}(y)$ denote the probability and mathematical expectation of stochastic variable $y$ . $\mathbb{N}^+$ denotes the non-negative integers. ∅ denotes an empty set which implies that there are no elements in the set according to some rules.

2.   Preliminaries and Problem Statement

2.1   Graph Theory Notations

Consider a mobile sensor network consisting of $N$ identical sensors. A directed graph (digraph) is used to model the interactions among sensors, where $\upsilon \in \{\upsilon _1$ $\ldots$ $\upsilon _N \}$ is the set of $N$ nodes, $\varepsilon \subseteq \upsilon \times \upsilon $ is the set of edges, $\Lambda =[a_{ij}]$ is the adjacency matrix with its elements associated with the edges, i.e., if , $a_{ij}$ $=$ $1$ , otherwise $(\upsilon _i, \upsilon _j)\notin \varepsilon $ , $a_{ij}=0$ . Edge $(\upsilon _i, \upsilon _j)\in \varepsilon $ means that node $\upsilon _i $ can receive information transmitted from node $\upsilon _j $ . A sequence of edges $(\upsilon _i, \upsilon _k)$ , $(\upsilon _k, \upsilon _l)$ , $\ldots $ , is called a directed path from node $\upsilon _j $ to node $\upsilon _i $ . A digraph is said to have a spanning tree, if there is a directed path from the root to any other nodes in the graph. The set of in-neighbors of node $\upsilon _i $ at time $k$ is denoted by . Similarly, the set of out-neighbors of node $\upsilon _i $ is adopted as $N_i^{\rm out} (k)$ $=$ . The in-degree of node $\upsilon _i $ is defined as $d_i =\sum\nolimits_{j=1}^N {a_{ij} } $ , moreover, in-degree matrix $\Delta ={\rm diag}\{d_1, \ldots, d_N \}$ . The Laplacian matrix of the directed graph $G$ is defined as $L=\Delta -\Lambda $ . Accordingly, the out-degree of node $\upsilon _i $ is defined as $d_i ^o=\sum\nolimits_{j=1}^N {a_{ji} } $ and the out-degree matrix $\Delta ^o={\rm diag}\{d_1 ^o, \ldots, d_N ^o\}$ . The column Laplacian matrix of graph $G$ is defined as .

2.2   Markov Switching Topology With Partially Unknown Switching Probabilities

At each instant $k$ , the interconnection of these mobile sensors can be regarded as a directed graph with a spanning tree. The communication topology is not fixed but switching according to a certain random event. It is assumed that the topology is switching within a given set of graphs $G( {\theta (k)})\in\bar {G}(k)$ , , where $k$ $\in$ $\mathbb{N}^+\}$ is the switching signal. Here, $\{\theta (k), k\in \mathbb{N}^+\}$ is assumed to be a Markov chain taking values in a finite set, $\theta (k)$ $\in$ , with transition probability defined as

where ${\rm Pro}\{\theta(0)=l\}=\pi_{0 l} $ , $\pi _{0l} $ is the initial probability of $G_{l}$ , $\forall l\in S$ , is the initial probability distribution, $\pi _{lv} $ is the single step transition probability from mode $l$ to mode $v$ , $\sum_{v=1}^q {\pi _{lv} =1} $ , , $\pi =[\pi _{lv}]_{q\times q} $ is called transition probability matrix.

The transition probabilities of the Markov chain are assumed to be partly available, e.g., some elements in transition probability matrix $\pi $ are unknown. For example, when $q$ $=$ $4, $ the transition probability matrix $\pi $ may be

where ? represents the unavailable element. Define $S=$ $\cup$ $S_{u\kappa }^l $ , where $S_\kappa ^l ={\{}v, $ if is known}, $S_{u\kappa }^l ={\{}v, $ if $\pi _{lv} $ is unknown} for any $l\in S$ . The former is equivalently described as $S_\kappa ^l =\{\kappa _1^l, \ldots, \kappa _r^l \}$ , , where $\kappa _r^l$ $\in$ $\mathbb{N}^+$ represents the $r$ {th} known element in the $l$ {th} row of matrix $\pi $ . In the forthcoming discussions, notation $\pi _\kappa ^l=$ will be adopted. Furthermore, the initial probability distribution is also assumed partially unknown, i.e., $\Pi _0$ $ =$ , we denote $\Omega _\kappa = \{v$ , if is known}, $\Omega _{u\kappa } =\{v$ , if $\pi _{0v} $ is unknown}, $1\le v\le q$ . Also, we denote throughout the paper.

2.3   Problem Statement and the Control Objective

The dynamics of each sensor in the MSN is presented as:

where $x_i (k)\in \mathbb{R}^n$ and $u_i (k)\in \mathbb{R}^m$ are the state and control input of sensor $i$ , and $B\in \mathbb{R}^{n\times m}$ are constant matrices, $x_i (0)$ is the initial state.

As in many other references [26], it is assumed that a number of mobile base stations are deployed to detect the topology information of the MSN and broadcast the information of the communication topology to the sensors in the systems, which implies it is a practical way that each sensor can know the present topology. Therefore, we use the mode-dependent consensus control protocol for sensor as follows.

where $K(\theta (k))$ is the controller gain matrix to be designed later.

The cost consumption for information receiving, sending and control of the MSN (1), respectively, can be defined as below

where , , $R\in \mathbb{R}^{m\times m}>0$ and $Q_1, $ are constant matrices.

Remark 1: In many wireless sensor network applications, data transmitting and receiving are two different procedures with different power requirement. This paper gives independent considerations of the energy costs for information receiving and sending. To cope with them more accurately, we use the to describe sensors from which sensor i receives information at each sampling instant, and $j$ $\in$ $N_i^{\rm out} (k)$ to denote sensors to which senor $i$ transmits information. We also introduce weight matrices $Q_1$ and $Q_2$ in the cost function to make independent penalties on the two cost consumption procedures. Therefore, the method proposed in this paper is very flexible for use in different scenarios.

The objective of this paper is to design a set of controllers (2) for MSN (1) to achieve consensus in the sense defined below.

Definition 1: MSN (1) is said to achieve mean-square consensus (MS-consensus) with consensus protocol (2) under Markov switching topologies $G( {\theta (k)} )$ , , $\theta (k)$ $\in$ $S=\{1, \ldots, q\}$ , if for any initial $x_i (0)$ , the following

holds true for any $i, $ $j=1, {\ldots}, N.$ Furthermore, the consensus protocols should guarantee a limited cost consumption:

Specifically, we aim at designing controllers (2) such that MSNs achieve consensus seeking for $C\le \tilde {C}$ , where is a given cost budget.

3.   Main Results

In this section, firstly, the sufficient MS-consensus conditions for MSN (1) with partially unknown switching probabilities will be derived. Then, using this condition, a controller design algorithm will be given to simultaneously calculate controller gains and sub-minimal cost upper bound.

Let $I_k =\{x\left( t \right), \theta (t), t=0, 1, 2, \ldots, k\}$ be the admissible information set. Then, under the consensus protocol (2), the dynamics of MSN (1) can be rewritten as

where $X(k)=[x_1^T (k), x_2^T (k), \ldots, x_N^T (k)]^T$ , Laplacian matrix $L_\theta$ $=$ $L(\theta (k))$ and the controller gain $K_\theta =K(\theta (k))$ .

By the definition of , $Y(k)=[y_1^T (k), y_2^T (k), \ldots, y_N^T (k)]^T$ , we can obtain $Z(k)=(L_\theta \otimes I_N)X(k)$ , , where $L_\theta ^o =L^o(\theta (k))$ . The global cost of the MSN (1) can be rewritten as

Now, introduce the following state transformation [21]:

And partition $\tilde {X}(k)\in \mathbb{R}^{nN}$ into two parts as $\tilde {X}(k)=[\tilde {X}_1^T (k), $ $\tilde {X}_2^T (k)]^T$ , where $\tilde {X}_1 (k)\in \mathbb{R}^n$ is a vector consisting of the first $n$ elements of $\tilde {X}(k)$ . Then, the dynamics of system (7) can be written as

where $\Theta _\theta =\frac{1}{\sqrt N }1^TL_\theta T_o $ , . According to [21], the MS-consensus of MSN (1) will be achieved if system (11) is mean square stable. Also, the cost consumption (8) can be rewritten as follows

where ${\Phi} _\theta ^o =T_o ^TL_\theta ^o T_o $ .

With the above discussion, the consensus seeking issue of system (7) is transformed to the stability problem of the reduced order system (11) with performance index (12).

We are now in the position to establish a sufficient mean square stability condition for system (11) with a guaranteed energy cost $\tilde {C}$ .

Theorem 1: Under the consensus protocol (2), MSN (1) can achieve guaranteed cost MS-consensus with Markov switching topologies set $\bar {G}(k)$ , if there exist matrices $P_l >0$ , $P_l$ $\in$ $R_{(N-1)n\times (N-1)n} $ , $l\in S$ , such that the following conditions

hold true, where , ${\Phi} _l =T_o ^TL_l T_o $ , $L_l$ $=L(\theta (k)=l)$ , , , ${\Phi}_l^o $ $=T_o ^TL_l^o T_o $ , , and $T_o $ is the orthogonal basis for the null space of 1. Furthermore, the guaranteed cost is

Proof: Firstly, the stability of system (11) will be proved. The following stochastic Lyapunov functional is defined as

Let $\theta (k)=l$ , $\theta (k+1)=v$ , $l, v\in S$ , the backward difference of (16) is derived as

Since , (17) can be written as

If (13) and (14) hold, we can have

Employing (18) and (19), the difference satisfies

where . Based on (18) and (20), we can obtain that

If inequalities (13) and (14) hold, it is clear that $<$ $\lambda _{\max } (P_l)$ , $0<\zeta <1$ . Along the same lines, the following formulation can be obtained

According to smooth characteristics of conditional mean [27], by (22), we can have

By recursion like (21), (22) and (23), the exponentially mean square stable condition can be derived as

from which it is straightforward that

where , $0<\zeta <1$ . Therefore, the stability of the reduced order system (11) can be achieved exponentially in a mean square sense. Moreover, under Markov switching topologies, the MSN (1) with controller (2) can achieve MS-consensus

Next, the proof of the guaranteed cost will be given. Summing both sides of inequality (17) from $k=0$ to $\infty$ yields

Since $\pi _{ov} \le 1-\pi _\kappa ^0 $ , , the energy cost upper bound in (26) can be written as

Remark 2: If $S_{u\kappa }^l =∅$ , $\forall l\in S$ , the problem reduces to the case where the initial and transition probabilities of the Markov chain are completely known [28]. In this case, the conditions in (13) and (14) are simplified as , $l\in S$ . On the other hand, if $S_\kappa ^l = ∅$ , $\forall l\in S$ , then the problem reduces to the case with arbitrary switching topologies [29] and conditions (13) and (14) become as $Q_l$ $+$ , $l\in S$ .

Before closing this section, a design algorithm for the controllers (2) will be proposed. To derive the algorithm, the following sufficient conditions on the existence of the controller gains are needed.

Theorem 2: For MSN (1) under Markovian switching topologies $G(\theta (k))$ , the consensus protocols (2) can drive the MSN to reach guaranteed cost consensus, if there exist $P_l $ , $M_l \in \mathbb{R}^{(N-1)n\times (N-1)n}$ , , $M_l >0$ , such that the following conditions

hold for all $l\in S$ , with the constraint and , $v\in S_{u\kappa }^l $ .

Proof: By using Theorem 1 and Schur complement lemma, Theorem 2 can be easily proved, so we omit it.

As for the cost budget of the MSNs, a feasible one has been derived in Theorem 1. Since the capacity of batteries for the MSNs is restricted, a minimal cost bound is more appropriate. Namely, we intend to seek the infimum of $\tilde {C}$ in (15) over the feasibility set $\Delta =(P_l, M_l, K_l)$ $(l\in S)$ determined by Theorem 2 as

The minimization problem can be presented as

By Schur complement, equivalently, it can be written as

where

and

The conditions in (33), (28) and (29) contain some constraints of matrix inversion, which are equivalent to the rank constrained LMIs

Therefore, the above minimization problem can be reduced to

To concurrently determine the controller gain matrix (2) and the sub-minimal cost upper bound (6), Algorithm 1 is proposed as follows.

Algorithm 1.
Step 1: Set the initial state $x_i (0)$ $(i=1, {\ldots}, N)$ , weight matrices $Q1, Q2$ , $R$ and the computational accuracy $\varepsilon $ . Let $e=0$ .
Step 2: Find a feasible solution $\bar {\delta }$ of $\delta $ by solving (38), set $f=\bar {\delta }$ .
Step 3: Let g=(e+f)/2, $\delta =g$ . Solving (38), if there exist feasible the solutions $K_l $ ( $l\in S)$ , set $f=g$ . Otherwise, $e=g$ .
Step 4: If $\left| {e-f} \right|<\varepsilon $ , output $\delta $ and $K_l $ . Otherwise, go to Step 3.

下载: 导出CSV 

| 显示表格

Remark 3: Since the guaranteed consensus issue is transformed to the stability of Markov jumping system (11) with performance index (12), the Lyapunov-Krasovskii functional method is used to derive the conditions on the existence of controller gains in terms of LMIs. It indicates that the results obtained in this paper depend to a great extent on the solvability of the LMIs, which may cause more complex computation as the number of sensors and their dimensions are increasing. Thus, for a large size network of sensors with high dimensions, the results obtained in this paper may not be appropriate. As for, how to amicably reduce such computational complexity, is still a tough problem, which is worth to be further studied in our future research.

4.   Numerical Examples

Some numerical examples are presented to illustrate the validity of the presented method in this section. Consider a collection of six identical sensors, whose dynamics described as

where $x_{i}(k)$ and $u_{i}(k)$ denote the position and input of the sensor $i$ , respectively. Choose $Q_{1}=0.2 {\rm J/m}^2$ , $Q_{2}=3 {\rm J/m}^2$ , $R$ $=$ $1$ kg and the initial positions $x_{1}(0)=9.3$ m, $x_{2}(0)$ $=$ $0$ m, $x_{3}(0)=5.7$ m, $x_{4}(0)=2.1$ m, $x_{5}(0)=1.3$ m and $ x_{6}(0)$ $=$ $10$ m.

A group of four directed graphs is shown in Fig. 1, which describes all the possible interactions among sensors.

图 1  The set of switching graphs $\bar{G}(k)=\{G_1, G_2, G_3, G_4 \}$ .

Fig. 1  The set of switching graphs $\bar{G}(k)=\{G_1, G_2, G_3, G_4 \}$ .

下载: 全尺寸图片 幻灯片

In the simulation, it is assumed that the topology of the MSN is switching according to a Markov chain with the following transition probability matrix

and the initial distribution of the Markov chain is . The Markov switching sequences of topologies are given in Fig. 2, where each mode in the ordinate denotes the corresponding topology.

图 2  Markov switching sequences of topologies.

Fig. 2  Markov switching sequences of topologies.

下载: 全尺寸图片 幻灯片

Using the proposed design Algorithm 1, we calculate the following controller gains $K_1 =-0.4053$ , $K_2 =-0.3226$ , $K_3$ $=$ $-0.3869$ and $K_4 =-0.0496$ . The mean cost consumption in (6) is obtained as $C=1565.9$ J, while the sub-minimal cost upper bound $C$ * is 6024.1 J. The simulation results of the six sensors with the designed controller gains are given in Fig. 3. It can be clearly seen that the six sensors' positions asymptotically converge to the same value, which implies the proposed controller design method in this paper is effective.

图 3  Positions of the nodes in the MSN with Algorithm 1.

Fig. 3  Positions of the nodes in the MSN with Algorithm 1.

下载: 全尺寸图片 幻灯片

As a comparison, the simulation result of the method in [30] is also presented to show the superiority of Algorithm 1 proposed in this paper. The same systems in (40), the communication topology set in Fig. 1 and the same transition probability matrix of Markov chain in (39) are considered in this comparison. Using the controller design algorithm in [30], we have the controller gains , $K_2^c$ $=$ $-0.2339$ , $K_3^c =-0.2225$ and . Mean cost in (6) and the cost upper bound are $Cc=3128.8$ and $\tilde {C}_c$ $=$ $12 980$ , respectively. The simulation result with the six sensors is illustrated in Fig. 4. By comparison, it is easily seen that $C<C_{c}$ and , which implies the proposed controller design method in this paper can guarantee the MSN to reach consensus with less cost consumption under partially unknown switching probabilities.

图 4  Positions of the nodes in the MSN with controller design method in [30].

Fig. 4  Positions of the nodes in the MSN with controller design method in [30].

下载: 全尺寸图片 幻灯片

5.   Conclusion

We have investigated the consensus issue of MSNs with Markov switching communication topologies under a sub-minimal guaranteed cost, in which both initial and transition probabilities of the Markov chain are assumed to be partially unavailable. The stability criterions for Markov jumping systems have been derived by state transformation, which ensure MSNs reach globally exponential mean square consensus. According to these conditions, the sub-optimal controller gains and sub-minimal cost bound have been derived synchronously by our proposed controller design method. Numerical examples have been given to validate the performance of the proposed method. In our further work, the cost-optimal consensus issue for MSNs with Markov switching topologies will be studied.