Systems and methods for consensus-based distributed graph spectral radius estimation
A system estimates spectral radius and leverages local updates from neighboring nodes in a wireless network to iteratively update state values of each node in the network and estimate a spectral radius of the network with guaranteed convergence. A method associated with the system method is a distributed method that efficiently converges to an invertible function of the spectral radius based only on local communications of the network for digital communication models in the presence and/or absence of packet loss, as opposed to conventional centralized methods.
1. A system, comprising:
a wireless sensor network including:
a plurality of nodes, wherein each node of the plurality of nodes is operable for communication with one or more neighboring nodes of the plurality of nodes across a respective communication link and wherein each node of the plurality of nodes includes a respective computing device, the computing device including a processor in communication with a memory, the memory including instructions which, when executed, cause the processor to:
(a) initialize a stored state value of the node to zero;
(b) receive a state value for a previous time iteration from one or more neighboring nodes of the plurality of nodes;
(c) update the stored state value for a current time iteration using the state values received from the one or more neighboring nodes of the plurality of nodes for the previous time iteration;
(d) broadcast the updated stored state value for the current time iteration to the one or more neighboring nodes of the plurality of nodes; and
(e) divide the updated stored state value by a total number of iterations to yield a consensus output value;
wherein the consensus output value is indicative of a spectral radius of the wireless sensor network.
2. The system of claim 1 , wherein the processor iteratively repeats steps (b)-(d) for t max iterations.
3. The system of claim 1 , wherein the stored state value is updated according to:
x i ( t )=log(Σ j=1 N a ij exp( x j ( t− 1)))
where i refers to a node, x i (t) is a given state value for the node at time iteration t, x j (t−1) is the state value received from a neighboring node j of the plurality of nodes for the previous time iteration t−1, a ij is a value denoting a relationship between the node and the neighboring node j, and N is a value denoting a quantity of the plurality of nodes in the wireless sensor network.
4. The system of claim 3 , wherein the value of a ij is a 1 if node j is a neighbor of the node and wherein the value of a ij is a 0 if node j is not a neighbor of the node.
5. The system of claim 1 , wherein each node of the plurality of nodes broadcasts a respective updated stored state value for the current time iteration to the one or more neighboring nodes of the plurality of nodes in a synchronized fashion.
6. The system of claim 1 , wherein the stored state value is updated according to:
x
i
(
t
+
1
)
=
log
(
exp
(
x
i
(
t
)
+
∑
j
=
1
N
a
i
j
b
ij
(
t
)
exp
(
x
j
(
t
)
)
)
where i refers to a node, x i (t) is a given state value for the node at time iteration t, a ij is a value denoting a relationship between the node and the neighboring node j, b ij (t) is an time-dependent independent Bernoulli random variable, and N is a value denoting a quantity of the plurality of nodes in the wireless sensor network.
7. The system of claim 6 , wherein the value of a a ij is a 1 if node j is a neighbor of the node and wherein the value of a a ij is a 0 if node j is not a neighbor of the node.
8. The system of claim 1 , wherein the consensus output value is determined according to:
y
i
(
t
)
=
1
t
x
i
(
t
)
where j refers to a node, where x i (t) is a given state value for the node at time iteration t, t=t max and where t max is the final time iteration.
9. The system of claim 8 , wherein the consensus output value is an approximation of log(p), wherein p is a spectral radius value.
10. A method for determining a spectral radius of a wireless sensor network, comprising:
(a) providing a wireless sensor network including a plurality of nodes, wherein each node of the plurality of nodes is operable for communication with one or more neighboring nodes of the plurality of nodes across a respective communication link and wherein each node of the plurality of nodes includes a respective computing device;
(b) initialize a stored state value of the node to zero at the respective computing device of the node;
(c) receive a state value for a previous time iteration from one or more neighboring nodes of the plurality of nodes;
(d) update the stored state value for a current time iteration using the state values received from the one or more neighboring nodes of the plurality of nodes for the previous time iteration;
(e) broadcast the updated stored state value for the current time iteration to the one or more neighboring nodes of the plurality of nodes; and
(f) divide the updated stored state value by a total number of iterations after a final time iteration to yield a consensus output value;
wherein the consensus output value is indicative of a spectral radius of the wireless sensor network.
11. The method of claim 10 , wherein steps (c)-(e) are iteratively repeated until the final time iteration is reached.
12. The method of claim 10 , further comprising:
increment a time iteration after the stored state value is updated.
13. The method of claim 10 , wherein the stored state value is updated according to:
x i ( t )=log(Σ j=1 N a ij exp( x j ( t− 1)))
where i refers to a node, x i (t) is a given state value for the node at time iteration t, x j (t−1) is the state value received from a neighboring node j of the plurality of nodes for the previous time iteration t−1, a ij is a value denoting a relationship between the node and the neighboring node j, and N is a value denoting a quantity of the plurality of nodes in the wireless sensor network.
14. The method of claim 13 , wherein the value of a ij is a 1 if node j is a neighbor of the node and wherein the value of a a ij is a 0 if node j is not a neighbor of the node.
15. The method of claim 10 , wherein each node of the plurality of nodes broadcasts a respective updated stored state value for the current time iteration to the one or more neighboring nodes of the plurality of nodes in a synchronized fashion.
16. The method of claim 10 , wherein the stored state value is updated according to:
x
i
(
t
+
1
)
=
log
(
exp
(
x
i
(
t
)
+
∑
j
=
1
N
a
ij
b
ij
(
t
)
exp
(
x
j
(
t
)
)
)
where i refers to a node, x i (t) is a given state value for the node at time iteration t, x j (t−1) is the state value received from a neighboring node j of the plurality of nodes for the previous time iteration t−1, a a ij is a value denoting a relationship between the node and the neighboring node j, b ij (t) is an time-dependent independent Bernoulli random variable, and N is a value denoting a quantity of the plurality of nodes in the wireless sensor network.
17. The method of claim 16 , wherein the value of a ij is a 1 if node j is a neighbor of the node and wherein the value of a a ij is a 0 if node j is not a neighbor of the node.
18. The method of claim 10 , wherein the consensus output value is determined according to:
y
i
(
t
)
=
1
t
x
i
(
t
)
where i refers to a node, where x i (t) is a given state value for the node at time iteration t, t=t max and where t max is the final time iteration.
19. The method of claim 18 , wherein the consensus output value is an approximation of log(p), wherein p is a spectral radius value.
20. The method of claim 10 , further comprising:
receive as input N, A, and t max , where N is an integer denoting a total number of nodes in the wireless sensor network, A is an adjacency matrix denoting a relationship between each respective node of the plurality of nodes, and where t max is a maximum quantity of time iterations.