Distributed Algorithm for the Network Size Estimation – Control and Dynamic Systems Lab Post

Published in: Conference on Decision and control (CDC) 2018
Authors: Donggil Lee, Seungjoon Lee, Taekyoo Kim, and Hyungbo Shim
Abstract: This paper presents a distributed algorithm for the network size estimation problem. The problem is to find the total number of nodes in the network. The proposed algorithm utilizes the continuous-time dynamics for achieving synchronization, which provides a way to assign each element of the equilibrium point of the dynamics close to the network size. The algorithm guarantees that each node directly estimates the total number of nodes in the network. Moreover, the network size can be estimated regardless of initial condition. We also derive the stopping criteria of the algorithm and extend the result to the case where the network varies intermittently with time.

What is the problem?

In large-scale systems, the algorithms for achieving synchronization or making certain formation are often designed in a distributed manner. As it can be inferred from the nomenclature of ‘distributed’ itself, distributed algorithms use only local knowledge for each agent. However, many algorithms are designed assuming that every agent in the network knows some global information of the network. In particular, the total number of nodes in a network (here we define it as Network Size or $N$ ) is important to design some distributed algorithms.

In fact, it is not trivial to estimate network size in a distributed way. Consider the situation shown Fig. 1. In a distributed network, each node can see only its neighbor. What information is to be exchanged between nodes and how to process that information?

The “tagging” method could solve our problems somewhat simply. In the method, each node has a predefined ID and all nodes store tables containing these IDs in which the nodes exchange their list with neighbors and update it. This method, however, has the disadvantage of being given a table in advance, as well as the large amount of information that must be exchanged at each moment.

Another method is introduced in [1] to estimate network size, which is mainly based on average consensus protocol. Initializing one node to value 1 while all others to 0, each node asymptotically obtains $1/N$ . This approach is preferably simpler than the previous ones, but higher accuracy is required as $N$ increases due to the inverse operation.

Proposed algorithm [2]

From now on, we introduce a new method to estimate network size $N$ which overcomes the aforementioned drawbacks.

In our algorithm, every node runs the following a scalar dynamics. It should be noted that there exists one special node, labeled as $i=1$ , which runs slightly different dynamics from other nodes.

$$ \qquad \quad \dot{x}_1 = -x_1+1+k\sum_{j\in\mathcal{N}_1}(x_j-x_1)\\ \dot{x}_i = 1 +k\sum_{j\in\mathcal{N}_i}(x_j-x_1) $$

where $k>0$ is the coupling gain, $x_i$ is state of $i$ -th nodes.

The equilibrium of above dynamics could be obtained exactly, but our goal is just to estimate $N$ . So, we just focus on the distance between $x_i^*$ and $N$ , where $x_i^*$ is equilibrium of $x_i^*$ . When the graph is connected, then we obtain the followings.

$$ |x_i^*-N|<\frac{\bar{N}^3}{2k},\quad \forall i$$

where $\bar{N}$ is upper bound of network size. Note that the equilibrium of each state may not be equal to $N$ , but the distance between $x_i^*$ and $N$ can be set to arbitrarily small value by increasing the gain $k$ .

How can we obtain $N$ exactly?

Remind that what we want to obtain is the total number of nodes in the network, that is integer. It is enough to set the value $|x_i^*-N|$ less than 1/2. Therefore, each node eventually obtains $N$ by rounding its state.

Then, how long should nodes wait before they obtain $N$ ?

Although it takes an infinite time for a state to reach its equilibrium point, it is possible to reach the interval $(N-0.5,N+0.5)$ within a finite time. See Fig. 2.

The problem is to find the finite value $T$ such that

$$\text{round}\big(x_i(t)\big)=N,\quad \forall t>T.$$

When initial values of all state are bounded, then we could find the time $T$ . Thus, the following assumption is added.

$$x_i(0)\in[0,\bar{N}],\quad\forall i$$

Consequently, we have the following result.

What are the advantages of our algorithms?

Our algorithm is very simple. Every node runs just scalar system, and only one piece of information is exchanged for the surrounding nodes at each time. But in fact, the algorithm based on average consensus also has these advantages. In fact, the most distinguishing advantages is that the proposed algorithm can be applied to the switching network where nodes can join or leave the network.

Let us focus on why the average consensus is not applicable to switching network. The algorithm utilize initialization method(initializing one node to value 1 while all others to 0). Actually, in the algorithm, the sum of all states is maintained to 1 while it is divided equally to all nodes. Thus, every node eventually gets the value $1/N$ . However, when some nodes leave the network, then the sum of states are no longer maintained.

On the other hand, in the proposed algorithm, the equilibrium is only related to individual vector field regardless of the initial value. That is the main reason the proposed algorithm can be applicable to switching network. The following is simulation result of proposed algorithm.

How can we come up with the proposed algorithm?

In fact, our algorithms are intentionally designed based on blended dynamics approach. Let us consider that every node in a given network runs the following scalar dynamics.

$$ \dot{x}_i=f_i(x_i)+k\sum_{j\in\mathcal{N}_i}(x_j-x_i)$$

It was shown in [3] that with sufficiently high coupling gain $k$ , the trajectories of nodes achieve practical synchronization. In addition, trajectories (practically) converge to the solution of the blended dynamics which is defined as

$$\dot{s} = \frac{1}{N} \sum_{i=1}^N f_i(s)$$

under appropriate assumptions. Let us check the blended dynamics of proposed algorithm.

$$\dot{s} = \frac{1}{N} \sum_{i=1}^N f_i(s)= \frac{1}{N}(-s+N)=-\frac{1}{N}s+1$$

It is trivial that $s$ converges to $N$ . Consequently, $x_i$ practically converges to $N$ .

Cdc18 dg lee from whatthehellisit

[1] “Distributed Network Size Estimation and Average Degree Estimation and Control in Networks Isomorphic to Directed Graphs”
Iman Shames, Themistoklis Charalambous, Christoforos N. Hadjicostis and Mikael Johansson
50th Annual Allerton Conference, 2012
http://dx.doi.org/10.1109/Allerton.2012.6483452
[2] “Distributed Algorithm for the Network Size Estimation: Blended Dynamics Approach ”
Donggil Lee, Seungjoon Lee, Taekyoo Kim, Hyungbo Shim
57th Conference on Decision and Control, 2018
http://dx.doi.org/10.1109/CDC.2018.8619676
[3] “Robustness of Synchronization of Heterogeneous Agents by Strong Coupling and a Large Number of Agents”
Jaeyong Kim, Jongwook Yang, Hyungbo Shim, Jung-Su Kim, Jin Heon Seo
IEEE Transactions on Automatic Control, 2016
http://dx.doi.org/10.1109/TAC.2015.2498138