On the topology design of large wireless sensor networks for distributed consensus with low power consumption

Abstract

Sensor-based structural health monitoring systems are commonly used to provide real-time information and detect damage in complex structures. In particular, wireless structural health monitoring systems are of low cost but, since wireless sensors are powered with batteries, a low power consumption is critical. A common approach for wireless structural health monitoring is to use a distributed computation strategy, which is usually based on consensus algorithms. Power consumption in such wireless consensus networks depends on the number of connections of the network. If sensors are randomly connected, there is no control on the power consumption. In this article, we present a novel strategy to connect a large number of wireless sensors for distributed consensus with low power consumption by combining small networks with basic topologies using the Kronecker product.

Keywords

Low power consumption network design large wireless sensor networks distributed consensus Kronecker product

Introduction

Monitoring complex structures such as aerospace, civil and mechanical infrastructures to provide real-time information and detect damage is referred in the literature as structural health monitoring (SHM). Visual inspection and time-based maintenance procedures are replaced by damage assessment processes using new technological developments such as sensor-based SHM systems. Since large-scale sensor networks are used for SHM, traditional wire-based SHM systems require significant time and cost for cable installation and maintenance. Wireless SHM systems are therefore an alternative solution for low-cost structural monitoring (see previous works).^1,2 Moreover, when monitoring aerospace infrastructures such as plane wings, data cables significantly increase aircraft weight and therefore its fuel consumption. Hence, the use of wireless sensor networks (WSN) is a key factor for the fuel-efficiency of aircrafts. For more details on the current research progress see Noel et al.³ and references therein.

In wireless SHM systems, it is common that each sensor requires a target value that depends on the values measured by other sensors of the WSN. When the WSN has a central entity that computes the target values, sensors have to transmit their measured values to the central entity and this leads to a large energy consumption. Since sensors on a WSN are usually powered with batteries, they have very limited energy resources and hence a reduction in the energy consumption due to transmission (power consumption) increases their life cycle.

The distributed computation strategy is a high-energy efficient strategy, where each sensor computes its target value by interchanging information with its neighbouring sensors.⁴ Many practical applications, where the distributed computation strategy is used, rely on the distributed averaging problem (also known as the distributed average consensus problem), which is the problem of obtaining the average of the values measured in all the sensors of the network in a distributed way.^5,6

A common approach for solving such problem is to use a linear iterative algorithm that is characterized by a matrix called weighting matrix. Its entries depend on the topology of the network considered. In Xiao and Boyd,⁷ the authors showed that a weighting matrix that makes the algorithm the fastest possible (i.e. the algorithm with the lowest convergence time) can be obtained by numerically solving a semidefinite programme, which can also be solved in a distributed way (see Insausti et al.).⁸ Unfortunately, except for certain basic network topologies, a closed-form expression for this optimal weighting matrix is not found in the literature.

In the literature, there are many works (see references)^9–11 whose goal is to minimize the power consumption in wireless consensus networks. Power consumption of the distributed averaging problem depends on the convergence time of the algorithm used for solving the problem and on the number of connections of the network. Thus, under a convergence time restriction, a reduction in the number of connections leads to a reduction of the power consumption.

If sensors are randomly connected, there is no control neither on the convergence time nor on the energy consumption. In this article, we present a strategy to connect a large number of wireless sensors for distributed consensus with low power consumption. In particular, we consider the case in which the large network is built from other smaller networks with basic topologies, which we call basic building blocks, using the Kronecker product. To connect a large number of wireless sensors for distributed consensus with low power consumption under a convergence time restriction, we previously derived a new mathematical result which is the key that gives a closed-form expression of the optimal weighting matrix for a large network built in such way. Moreover, we show that this optimal weighting matrix only depends on the optimal weighting matrices for the employed basic building blocks. Specifically, applying our result, we determine the basic building blocks to be used to minimize the number of connections of the resulting network. Observe that the number of connections of the network directly determines the power consumption of the sensors due to transmission when the convergence time is fixed.

The remainder of this article is organized as follows: The next section states preliminary considerations and the new mathematical result that gives a closed-form expression of the optimal weighting matrix for distributed consensus on any network modelled using the Kronecker product. In section ‘Problem formulation’, we introduce the problem of designing large wireless consensus networks with low power consumption under a convergence time restriction using the Kronecker product. In section ‘Numerical examples’, we numerically solve the considered problem for certain scenarios. Finally, we present our conclusions in section ‘Conclusion’.

Preliminaries

The distributed averaging problem

Consider a network of $n$ nodes. The network can be viewed as an (undirected) graph $G = (V, E)$ , where $V = {v_{1}, v_{2}, \dots, v_{n}}$ is the set of nodes and $E$ is the set of edges. We say that the nodes $v_{i}$ and $v_{j}$ are connected if ${v_{i}, v_{j}} \in E$ .

Each node of the network needs to obtain the average (arithmetic mean) of the initial values stored in all the nodes of the network in a distributed way. A common approach for solving this problem is to use a linear iterative algorithm of the form

x (t + 1) = W x (t) t \in {0, 1, \dots}

(1)

where $[x (0)]_{i, 1}$ is the initial value stored in the node $v_{i}$ and $W$ is a real $n \times n$ symmetric matrix, called the weighting matrix, with $[W]_{i, j} = 0$ whenever the nodes $v_{i}$ and $v_{j}$ are not connected and $i \neq j$ . The weighting matrix $W$ needs to be set so that

lim_{t \to \infty} [x (t)]_{i, 1} = lim_{t \to \infty} [W^{t} x (0)]_{i, 1} = x_{ave} \forall i \in {1, \dots, n}

(2)

where $x_{ave}$ is the sought average, that is

x_{ave} : = \frac{1}{n} \sum_{i = 1}^{n} [x (0)]_{i, 1}

Let $W (G)$ be

W (G) : = {W \in R^{n \times n}, W^{T} = W, W 1_{n} = 1_{n}

[W]_{i, j} = 0 if i \neq j and {v_{i}, v_{j}} \notin E}

where $R^{n \times n}$ is the set of all $n \times n$ real matrices, T denotes transpose, and $1_{n}$ is the $n \times 1$ matrix of ones. From Xiao and Boyd⁷ Theorem 1, if $W \in W (G)$ and $‖ W - P_{n} ‖_{2} < 1$ then, equation (2) holds, where $| | \cdot ‖_{2}$ is the spectral norm (see Bernstein¹²) and $P_{n} : = (1 / n) 1_{n} 1_{n}^{T}$ . We assume that $G$ is a connected graph (see Bollobás¹³) to guarantee the existence of such a $W \in W (G)$ with $‖ W - P_{n} ‖_{2} < 1$ .

The convergence time of an algorithm of the form equation (1) only depends on the weighting matrix $W$ and was defined in Xiao and Boyd⁷ as

τ (W) : = \frac{- 1}{\log ‖ W - P_{n} ‖_{2}}

(3)

whenever $W \in W (G)$ and $‖ W - P_{n} ‖_{2} < 1$ .

An algorithm of the form equation (1) that minimizes the convergence time is known as the fastest symmetric distributed linear averaging (FSDLA) algorithm, that is, its (optimal) weighting matrix $W_{opt}$ satisfies

‖ W_{opt} - P_{n} ‖_{2} \leq ‖ W - P_{n} ‖_{2} \forall W \in W (G)

We denote as $τ_{opt} (G)$ the convergence time of the FSDLA algorithm on that graph, that is

τ_{opt} (G) : = τ (W_{opt})

Building networks using the Kronecker product

We recall that the adjacency matrix of a graph $G = (V, E)$ with $n$ nodes (see Bollobás¹³ (Section 8.2)) is the $n \times n$ real symmetric matrix $A$ given by

[A]_{i, j} : = {\begin{matrix} 1 & if {i, j} \in E, \\ 0 & otherwise, \end{matrix} i, j \in {1, \dots, n}

In this article, we use the Kronecker product as a tool for modelling a large network. Let $G_{1}$ and $G_{2}$ be two graphs with $n_{1}$ and $n_{2}$ nodes, respectively. Using the Kronecker product, we build a larger graph $H = (V_{H}, E_{H})$ with $n_{1} n_{2}$ nodes, whose adjacency matrix $A_{H}$ is given by

A_{H} = (A_{1} + I_{n_{1}}) \otimes (A_{2} + I_{n_{2}}) - I_{n_{1} n_{2}}

(4)

where $A_{1}$ and $A_{2}$ are the adjacency matrices of $G_{1}$ and $G_{2}$ , respectively, $I_{n}$ is the $n \times n$ identity matrix, and ⊗ denotes the Kronecker product. For convenience, we denote the nodes of $H$ as

V_{H} = {(k, l) : k \in {1, \dots, n_{1}}, l \in {1, \dots, n_{2}}}

If $q_{1}$ is the number of edges of $G_{1}$ and $q_{2}$ is the number of edges of $G_{2}$ then, the number of edges of $H$ is given by

q_{H} = \frac{(2 q_{1} + n_{1}) (2 q_{2} + n_{2}) - n_{1} n_{2}}{2}

(5)

A very interesting example of graphs built this way are the grids, which are built using two paths.

A new mathematical result

In this subsection, we give a new mathematical result regarding the FSDLA algorithm on networks built using the Kronecker product. This new mathematical result is key to design large wireless consensus networks with low power consumption. More precisely, we consider a graph $H$ built using the Kronecker product of another two graphs $G_{1}$ and $G_{2}$ as explained in subsection ‘Building networks using the Kronecker product’. Without loss of generality, we assume that $τ_{opt} (G_{1}) \geq τ_{opt} (G_{2})$ . Let $W_{1}$ be the weighting matrix of the FSDLA algorithm on $G_{1}$ and let $W_{2}$ be any weighting matrix in $W (G_{2})$ satisfying $τ (W_{2}) \leq τ (W_{1}) = τ_{opt} (G_{1})$ . Theorem 1 shows that

The convergence time of the FSDLA algorithm on $H$ is equal to the convergence time of the FSDLA algorithm on $G_{1}$ .

$W_{1} \otimes W_{2}$ is the weighting matrix of the FSDLA algorithm on $H$ .

Theorem 1

Let $G_{1}$ and $G_{2}$ be two connected graphs with $n_{1}$ and $n_{2}$ nodes, respectively, satisfying $τ_{opt} (G_{1}) \geq τ_{opt} (G_{2})$ . Consider $W_{1} \in W (G_{1})$ such that $τ (W_{1}) = τ_{opt} (G_{1})$ and let $W_{2} \in W (G_{2})$ with $τ (W_{2}) \leq τ (W_{1})$ . Then, $W_{1} \otimes W_{2} \in W (H)$ , and

$τ_{opt} (G_{1}) = τ (W_{1} \otimes W_{2}) = τ_{opt} (H)$

where $H$ is the graph whose adjacency matrix $A_{H}$ is defined as in equation (4).

Proof

We divide the proof into three steps.

Step 1: We show that $W_{1} \otimes W_{2} \in W (H)$ . Observe that $W_{1} \otimes W_{2} \in R^{n_{1} n_{2} \times n_{1} n_{2}}$

{(W_{1} \otimes W_{2})}^{T} = W_{1}^{T} \otimes W_{2}^{T} = W_{1} \otimes W_{2}

and

\begin{matrix} (W_{1} \otimes W_{2}) 1_{n_{1} n_{2}} & = (W_{1} \otimes W_{2}) (1_{n_{1}} \otimes 1_{n_{2}}) \\ = (W_{1} 1_{n_{1}}) \otimes (W_{2} 1_{n_{2}}) = 1_{n_{1}} \otimes 1_{n_{2}} \\ = 1_{n_{1} n_{2}} \end{matrix}

Moreover

\begin{matrix} {[W_{1} \otimes W_{2}]}_{n_{2} (i - 1) + k, n_{2} (j - 1) + l} \\ = {[W_{1}]}_{i, j} {[W_{2}]}_{k, l} \\ = {[A_{1} + I_{n_{1}}]}_{i, j} {[W_{1}]}_{i, j} {[A_{2} + I_{n_{2}}]}_{k, l} {[W_{2}]}_{k, l} \\ = {[(A_{1} + I_{n_{1}}) \otimes (A_{2} + I_{n_{2}})]}_{n_{2} (i - 1) + k, n_{2} (j - 1) + l} \\ \times {[W_{1} \otimes W_{2}]}_{n_{2} (i - 1) + k, n_{2} (j - 1) + l} \\ = {[A_{H} + I_{n_{1} n_{2}}]}_{n_{2} (i - 1) + k, n_{2} (j - 1) + l} \\ \times {[W_{1} \otimes W_{2}]}_{n_{2} (i - 1) + k, n_{2} (j - 1) + l} \end{matrix}

for all $i, j \in {1, \dots, n_{1}}$ and $k, l \in {1, \dots, n_{2}}$ .

Step 2: We prove that $τ (W_{1} \otimes W_{2}) = τ (W_{1})$ . If $W \in R^{n \times n}$ is symmetric, we denote its eigenvalues by $λ_{k} (W)$ , $k \in {1, \dots, n}$ , with $| λ_{1} (W) | \geq \dots \geq | λ_{n} (W) |$ . Since $τ (W_{2}) \leq τ (W_{1})$ , we have $‖ W_{2} - P_{n_{2}} ‖_{2} \leq ‖ W_{1} - P_{n_{1}} ‖_{2} < 1$ . Hence, from Insausti et al.⁸ (Lemma 1) we have $‖ W_{2} - P_{n_{2}} ‖_{2} = | λ_{2} (W_{2}) |$ and $‖ W_{1} - P_{n_{1}} ‖_{2} = | λ_{2} (W_{1}) |$ . Consequently, as

\begin{matrix} | λ_{2} (W_{1} \otimes W_{2}) | \\ = max (| λ_{1} (W_{1}) λ_{2} (W_{2}) |, | λ_{1} (W_{2}) λ_{2} (W_{1}) |) \\ = max (| λ_{2} (W_{2}) |, | λ_{2} (W_{1}) |) \\ = | λ_{2} (W_{1}) | = ‖ W_{1} - P_{n_{1}} ‖_{2} < 1 \end{matrix}

we obtain that

‖ W_{1} \otimes W_{2} - P_{n_{1} n_{2}} ‖_{2} = ‖ W_{1} - P_{n_{1}} ‖_{2}

Step 3: We prove that $τ (W_{1} \otimes W_{2}) = τ_{opt} (H)$ . Let $G$ be a connected graph with $n$ nodes and $q$ edges, and let $B : R^{q} \to W (G)$ be the bijection defined in Insausti et al.⁸(equation (8)). Consider the function $f_{G} : R^{q} \to [0, \infty)$ defined as $f_{G} (w_{1}, \dots, w_{q}) : = ‖ B (w_{1}, \dots, w_{q}) - P_{n} ‖_{2}$ .

Observe that proving $τ (W_{1} \otimes W_{2}) = τ_{opt} (H)$ is equivalent to prove

‖ W_{1} \otimes W_{2} - P_{n_{1} n_{2}} ‖_{2} \leq ‖ B (w_{1}, \dots, w_{q_{H}}) - P_{n_{1} n_{2}} ‖_{2}

(6)

for all w_{1}, \dots, w_{q_{H}} \in R .

Let $u \in R^{n_{1} \times 1}$ be such that $‖ u ‖_{2} = 1$ and $W_{1} u = (- 1)^{s} | λ_{2} (W_{1}) | u$ for some $s \in {1, 2}$ . Since, $W_{2}$ satisfies $W_{2} 1_{n_{2}} = 1_{n_{2}}$ , then $(1 / \sqrt{n_{2}}) 1_{n_{2}}$ is the unit eigenvector of $W_{2}$ associated to $λ_{1} (W_{2}) = 1$ , and therefore $u \otimes (1 / \sqrt{n_{2}}) 1_{n_{2}}$ is a unit eigenvector of $W_{1} \otimes W_{2}$ associated to the eigenvalue $(- 1)^{s} | λ_{2} (W_{1} \otimes W_{2}) | = (- 1)^{s} | λ_{2} (W_{1}) |$ .

Applying Insausti et al.⁸(Theorem 1), we get a subgradient of $f_{H}$ associated to the eigenvector $u \otimes (1 / \sqrt{n_{2}}) 1_{n_{2}}$

g_{H} (u) = \frac{{(- 1)}^{s + 1}}{n_{2}} (\begin{matrix} {({[u]}_{k_{1}, 1} - {[u]}_{p_{1}, 1})}^{2} \\ ⋮ \\ {({[u]}_{k_{q_{H}}, 1} - {[u]}_{p_{q_{H}}, 1})}^{2} \end{matrix})

where ${(k_{m}, l_{m}), (p_{m}, r_{m})} \in E_{H}$ for $m \in {1, \dots, q_{H}}$ . Observe that from equation (4), ${(k_{m}, l_{m}), (p_{m}, r_{m})} \in E_{H}$ if and only if

{\begin{matrix} {k_{m}, p_{m}} \in E_{1} and {l_{m}, r_{m}} \in E_{2}, or \\ k_{m} = p_{m} and {l_{m}, r_{m}} \in E_{2}, or \\ {k_{m}, p_{m}} \in E_{1} and l_{m} = r_{m} \end{matrix}

where $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ .

Fix $m \in {1, \dots, q_{H}}$ . If $k_{m} = p_{m}$ , then

{[g_{H} (u)]}_{m, 1} = \frac{{(- 1)}^{s + 1}}{n_{2}} {({[u]}_{k_{m}, 1} - {[u]}_{p_{m}, 1})}^{2} = 0

(7)

If ${k_{m}, p_{m}} \in E_{1}$ , then there exists $d \in {1, \dots, q_{1}}$ such that

{[g_{G_{1}} (u)]}_{d, 1} = (- 1)^{s + 1} {({[u]}_{k_{m}, 1} - {[u]}_{p_{m}, 1})}^{2}

where $g_{G_{1}} (u)$ is a subgradient of $f_{G_{1}}$ associated to the eigenvector $u$ . Therefore

\begin{matrix} {[g_{H} (u)]}_{m, 1} & = \frac{{(- 1)}^{s + 1}}{n_{2}} {({[u]}_{k_{m}, 1} - {[u]}_{p_{m}, 1})}^{2} \\ = \frac{1}{n_{2}} {[g_{G_{1}} (u)]}_{d, 1} \end{matrix}

(8)

As $W_{1}$ is the weighting matrix of the FSDLA algorithm on $G_{1}$ , $‖ W_{1} - P_{n_{1}} ‖_{2} \leq f_{G_{1}} (w_{1}, \dots, w_{q_{1}})$ for all $w_{1}, \dots, w_{q_{1}} \in R$ , and therefore from Insausti et al.¹⁴ $0_{q_{1}}$ is a subgradient of $f_{G_{1}}$ , where $0_{q_{1}}$ denotes the $q_{1} \times 1$ matrix of zeros. Since the set of all the subgradients of $f_{G_{1}}$ is the convex hull of the set

{g_{G_{1}} (u) : W_{1} u \in {\pm λ_{2} (W_{1}) u}, ‖ u ‖_{2} = 1}

there exist unit eigenvectors $u_{1}, \dots, u_{L}$ and non-negative scalars $α_{1}, \dots, α_{L}$ with $\sum_{j = 1}^{L} α_{j} = 1$ satisfying

0_{q_{1}} = \sum_{j = 1}^{L} α_{j} g_{G_{1}} (u_{j})

Consequently, from equations (7) and (8) we get that

\sum_{j = 1}^{L} α_{j} g_{H} (u_{j}) = 0_{q_{H}}

and since a convex combination of subgradients is also a subgradient, from Shor¹⁴ equation (6) holds.

Observe that, according to Theorem 1, for obtaining the closed-form expression of the weighting matrix of the FSDLA algorithm on $H$ , there is no need to know the weighting matrix of the FSDLA algorithm on $G_{2}$ .

Problem formulation

In this section, we introduce the problem of designing large wireless consensus networks with low power consumption.

The power consumption (energy consumption of the sensors of the network due to transmission) of the distributed averaging problem depends on the convergence time of the algorithm used for solving the problem and on the number of edges of the network. Hence, under a convergence time restriction, a reduction in the number of edges leads to a reduction of the power consumption.

We aim to connect a large number of sensors (nodes) so that the distributed averaging problem is solved under a convergence time restriction. We build this large network using the Kronecker product of basic building blocks. We study the problem of combining these basic building blocks (allowing repetitions) to minimize the number of edges of the resulting network.

In particular, let ${G_{1}, \dots, G_{k}}$ be the basic building blocks to be combined. We want to use the Kronecker product for building a graph $H$ that connects at least $n$ nodes under a convergence time restriction $τ_{max}$ . We denote with $n_{i}$ the number of nodes of $G_{i}$ , and with $r_{i}$ the number of times that the basic building block $G_{i}$ is used to build $H$ ( $r_{i}$ can be zero). The goal is to obtain the values of $n_{i}$ and $r_{i}$ for $i \in {1, \dots, k}$ such that the number of edges $q$ of the resulting graph $H$ is minimized. Let $n_{i_{max}}$ be the maximum number of nodes of $G_{i}$ such that $τ_{opt} (G_{i}) \leq τ_{max}$ for all $i \in {1, \dots, k}$ . Observe that from Theorem 1, regardless of the combination of basic building blocks employed, any graph $H$ built in this way satisfies

τ_{opt} (H) = max_{i \in {1, \dots, k}} τ_{opt} (G_{i}) \leq τ_{max}

Therefore, to connect the $n$ nodes under a convergence time restriction $τ_{max}$ and with a minimum number of edges, we need to solve the following minimization problem

\begin{matrix} minimize & q \\ subject to & Π_{i = 1}^{k} n_{i}^{r_{i}} \geq n \\ n_{i} \leq n_{i_{max}}, i \in {1, \dots, k} \end{matrix}

(9)

Observe that $q$ can be obtained by applying equation (5) recursively. By solving equation (9), we obtain the values of $n_{i}$ and $r_{i}$ . Hence, from Theorem 1, the problem of designing the topology of a large consensus WSN under a convergence time restriction becomes into the minimization problem given in equation (9). Moreover, Theorem 1 provides the weighting matrix of the FSDLA algorithm on $H$ , that is, from Theorem 1, there does not exist another weighting matrix that solves the distributed averaging problem faster on $H$ .

For the reader’s convenience, we end this section with an algorithm that summarizes the implementation of the solution of the considered problem (see Algorithm I).

Algorithm 1 for the design of large wireless consensus networks from basic building blocks under a convergence time restriction.
1. Select $k$ basic building blocks $G_{1}, \dots, G_{k}$ . 2. Set $τ_{max}$ . 3. for $i = 1 : k$ do 4. Compute $n_{i_{max}}$ such that $τ_{opt} (G_{i}) \leq τ_{max}$ 5. end for 6. Solve equation (9) 7. Compute the adjacency matrix of $H$ by applying equation (4) recursively

Numerical examples

Here, we solve the problem introduced in section ‘Problem formulation’ for two different scenarios.

Scenario 1: cycles and paths as basic building blocks

We consider two building blocks with basic topologies ${G_{1}, G_{2}}$ . In particular, $G_{1}$ is a cycle with $n_{1}$ nodes ( $n_{1} \geq 3$ ) and $G_{2}$ is a path with $n_{2}$ nodes ( $n_{2} \geq 2$ ). We want to connect at least $n$ nodes under a convergence time restriction $τ_{max}$ and with a minimum number of edges by using $r_{1}$ cycles of $n_{1}$ nodes and $r_{2}$ paths of $n_{2}$ nodes. From Insausti et al.¹⁵(Section 2.1.1) we obtain $n_{1_{max}}$ , which is the maximum number of nodes of $G_{1}$ such that $τ_{opt} (G_{1}) \leq τ_{max}$ . Similarly, from Insausti et al.¹⁵(Section 2.1.3) we obtain $n_{2_{max}}$ , which is the maximum number of nodes of $G_{2}$ such that $τ_{opt} (G_{2}) \leq τ_{max}$ .

In this scenario, it is possible to obtain an explicit expression of $q$ , and therefore the minimization problem in equation (9) can be rewritten as follows

\begin{matrix} minimize & q = \frac{{(3 n_{1})}^{r_{1}} {(3 n_{2} - 2)}^{r_{2}} - n_{1}^{r_{1}} n_{2}^{r_{2}}}{2} \\ subject to & n_{1}^{r_{1}} n_{2}^{r_{2}} \geq n \\ 3 \leq n_{1} \leq n_{1_{max}} \\ 2 \leq n_{2} \leq n_{2_{max}} \end{matrix}

(10)

where the function to be minimized has been obtained by applying equation (5) recursively.

Table 1 shows the numerical resolution of equation (10) when at least $10, 000$ nodes need to be connected under different convergence time restrictions.

Table 1.

Numerical resolution of equation (10) for at least $n = 10, 000$ nodes.

$τ_{max}$	$1$	$5$	$10$	$50$	$100$	$500$
$n_{1}$	4	9	12	29	41	71
$r_{1}$	7	2	3	2	2	2
$n_{2}$	–	5	6	12	6	2
$r_{2}$	0	3	1	1	1	1
$τ_{opt} (H)$	0.91	4.72	7.45	42.65	85.20	255.42

Figure 1(a) and (b) shows the minimum number of edges obtained by solving equation (10) when different number of nodes need to be connected under different convergence time restrictions.

Figure 1.

Minimum number of edges for connecting at least $n$ nodes under a convergence time restriction $τ_{max}$ . (a) Variation of the minimum number of edges required for building graphs that connect 100, 1000 and 10,000 nodes when $τ_{max} \in$ (1; 1000). (b) Variation of the minimum number of edges required for building graphs under a convergence time restriction of 1, 10 and 100 when the number of nodes to connect $n \in$ (2⁸; 2¹⁴).

Figure 2 shows the graphs resulting from solving equation (10) when $n = 36$ and for different convergence time restrictions.

Figure 2.

Graph $H$ with 36 nodes built using the Kronecker product of cycles and paths. (a) $τ_{max} = 5$ : this graph is built using one cycle of nine nodes and one path of four nodes. It has 117 edges. (b) $τ_{max} = 10$ : this graph is built using one cycle of 12 nodes and one path of 3 nodes. It has 108 edges. (c) $τ_{max} = 50$ : this graph is built using one cycle of 18 nodes and one path of 2 nodes. It has 90 edges.

Scenario 2: stars and paths as basic building blocks

In this subsection, we study the same scenario considered in subsection ‘Scenario 2: cycles and paths as basic building blocks’, but $G_{1}$ is now a star with $n_{1}$ nodes $(n_{1} \geq 4)$ . Since a closed-form expression of $τ_{opt} (G_{1})$ is not found in the literature, we numerically compute it from Xiao and Boyd⁷ equation (4) to obtain $n_{1_{max}}$ , which is the maximum number of nodes of $G_{1}$ such that $τ_{opt} (G_{1}) \leq τ_{max}$ .

In this scenario, the minimization problem in equation (9) can be rewritten as follows

\begin{matrix} minimize & q = \frac{{(3 n_{1} - 2)}^{r_{1}} {(3 n_{2} - 2)}^{r_{2}} - n_{1}^{r_{1}} n_{2}^{r_{2}}}{2} \\ subject to & n_{1}^{r_{1}} n_{2}^{r_{2}} \geq n \\ 4 \leq n_{1} \leq n_{1_{max}} \\ 2 \leq n_{2} \leq n_{2_{max}} \end{matrix}

(11)

Table 2 shows the numerical resolution of equation (11) when at least $10, 000$ nodes need to be connected under different convergence time restrictions.

Table 2.

Numerical resolution of equation (11) for at least $n = 10, 000$ nodes.

$τ_{max}$	$1$	$5$	$10$	$50$	$100$	$500$
$n_{1}$	–	10	15	100	100	1000
$r_{1}$	0	4	3	2	2	1
$n_{2}$	2	–	3	–	–	10
$r_{2}$	14	0	1	0	0	1
$τ_{opt} (H)$	0	4.98	7.49	50.00	50.00	500.00

Figure 3 shows the graphs resulting from solving equation (11) when $n = 36$ and for different convergence time restrictions.

Figure 3.

Graph $H$ with 36 nodes built using the Kronecker product of stars and paths. (a) $τ_{max} = 5$ : this graph is built using one star of nine nodes and one path of four nodes. It has 107 edges. (b) $τ_{max} = 10$ : this graph is built using one star of 18 nodes and one path of 2 nodes. It has 86 edges. (c) $τ_{max} = 50$ : this graph is built using a single star of 18 nodes. It has 35 edges.

Conclusion

In this article, we have proposed a method for building large wireless consensus networks with low power consumption under a convergence time restriction. These large networks are built from other smaller networks with basic topologies using the Kronecker product. We observe that the advantage of building a large network this way is that it inherits the symmetries of its corresponding basic building blocks. Hence, the shape of the structure to be monitored determines the suitability of the basic building blocks to be used.

Footnotes

Handling Editor: Mihael Mohorcic

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the Basque Government through the CODISAVA project (KK-2018/00082) and by the Spanish Ministry of Economy and Competitiveness through the CARMEN project (TEC2016-75067-C4-3-R).

ORCID iD

Xabier Insausti

References

Federici

Graziosi

Faccio

, et al. An integrated approach to the design of wireless sensor networks for structural health monitoring. Int J Distrib Sens Netw 2012; 8(3): 594842.

Wang

Yan

Tian

, et al. Investigation of wireless sensor networks for structural health monitoring. J Sens 2012; 2012: 156329.

Noel

Abdaoui

Elfouly

, et al. Structural health monitoring using wireless sensor networks: a comprehensive survey. IEEE Commun Surv Tut 2017; 19(3): 1403–1423.

Dimakis

Kar

Moura

JMF

, et al. Gossip algorithms for distributed signal processing. Proc IEEE 2010; 98(11): 1847–1864.

Hendrickx

Olshevsky

Tsitsiklis

JN.

Distributed anonymous discrete function computation. IEEE T Automat Contr 2011; 56(10): 2276–2289.

Dai

Toulouse

Lower-bound study for function computation in distributed networks via vertex-eccentricity. SN Comput Sci 2019; 1(1): 10.

Xiao

Boyd

Fast linear iterations for distributed averaging. Syst Control Lett 2004; 53: 65–78.

Insausti

Gutiérrez-Gutiérrez

Zárraga-Rodríguez

, et al. In-network computation of the optimal weighting matrix for distributed consensus on wireless sensor networks. Sensors 2017; 17(8): 1702.

Insausti

Camaró

Crespo

, et al. Distributed pseudo-gossip algorithm and finite-length computational codes for efficient in-network subspace projection. IEEE J Sel Top Signa 2013; 7(2): 163–174.

10.

Asensio-Marco

Beferull-Lozano

Energy efficient consensus over complex networks. IEEE J Sel Top Signa 2015; 9(2): 292–303.

11.

Sardellitti

Barbarossa

Swami

Optimal topology control and power allocation for minimum energy consumption in consensus networks. IEEE T Signal Pr 2012; 60(1): 383–399.

12.

Bernstein

DS.

Matrix mathematics. Princeton, NJ: Princeton University Press, 2009, pp.350, 603.

13.

Bollobás

Modern graph theory (Graduate texts in mathematics). New York: Springer, 1998, p.6.

14.

Shor

NZ.

Minimization methods for non-differentiable functions. New York: Springer, 1985, p.12.

15.

Gutiérrez-Gutiérrez

Zárraga-Rodríguez

Insausti

Analysis of known linear distributed average consensus algorithms on cycles and paths. Sensors 2018; 18(4): 968.