# Finite Time Exact Quantized Average Consensus
with Limited Resources and Transmission Stopping for Energy-Aware Networks

Apostolos I. Rikos<EMAIL_ADDRESS>Christoforos N. Hadjicostis<EMAIL_ADDRESS>Karl H. Johansson<EMAIL_ADDRESS>Division of Decision and Control Systems, KTH
Royal Institute of Technology,
and also affiliated with Digital Futures, SE-100 44 Stockholm, Sweden
Department of Electrical and Computer Engineering, University of Cyprus,
Nicosia, Cyprus

###### Abstract

Composed of spatially distributed sensors and actuators that communicate
through wireless networks, networked control systems are emerging as a
fundamental infrastructure technology in $5$G and IoT technologies, including
diverse applications, such as autonomous vehicles, UAVs, and various sensing
devices. In order to increase flexibility and reduce deployment and
maintenance costs, many such applications consider battery-powered or energy-
harvesting networks, which bring additional limitations on the energy
consumption of the wireless network. Specifically, the operation of battery-
powered or energy-harvesting wireless communication networks needs to
guarantee (i) efficient communication between nodes and (ii) preservation of
available energy. Motivated by these novel requirements, in this paper, we
present and analyze a novel distributed average consensus algorithm, which (i)
operates exclusively on quantized values (in order to guarantee efficient
communication and data storage), and (ii) relies on event-driven updates (in
order to reduce energy consumption, communication bandwidth, network
congestion, and/or processor usage). We characterize the properties of the
proposed algorithm and show that its execution, on any time-invariant and
strongly connected digraph, will allow all nodes to reach, in finite time, a
common consensus value that is equal to the exact average (represented as the
ratio of two quantized values). Furthermore, we show that our algorithm allows
each node to cease transmissions once the exact average of the initial
quantized values has been reached (in order to preserve its battery energy).
Then, we present upper bounds on (i) the number of transmissions and
computations each node has to perform during the execution of the algorithm,
and (ii) the memory and energy requirements of each node in order for the
algorithm to be executed. Finally, we provide examples that demonstrate the
operation, performance, and potential advantages of our proposed algorithm.

###### keywords:

Quantized average consensus, event-triggered, distributed algorithms,
quantization, digraphs, multi-agent systems

###### keywords:

Quantized average consensus, digraphs, event-triggered distributed algorithms,
quantization, multi-agent systems.

††thanks: The results of this paper were not presented at any conference.
Corresponding author Apostolos I. Rikos.

, ,

##  1 INTRODUCTION

In recent years there have been tremendous advances in the area of wireless
networking, sensing, computing, and control. These advances are
revolutionizing the role and importance of wireless control networks in
various areas, such as Cyber-Physical Systems [43] and Internet of Things
(IoT) applications [3]. Wireless control networks consist of various sensor
nodes which sample and transmit data over a wireless channel to controllers,
which are in charge of deciding the necessary actions based on the received
data. Wireless networks play an important role in the rapid expansion of the
areas of embedded computing, advanced control, cloud computing, and emerging
applications in autonomous vehicles [1, 10], coordination of UAVs [4], and
sensor networks [2]. A recent survey which analyzes the importance of wireless
networks in emerging control systems can be found in [31].

By their nature, wireless networks do not have a fixed infrastructure and do
not use centralized methods for organization. This flexibility enables their
use even when a fixed infrastructure is unavailable and makes them attractive
for numerous applications (ranging from military, civil, industrial or
environmental monitoring in hostile environments). The absence of cables for
data communication motivates the removal of the power supply from the nodes in
order to achieve even more flexibility. Therefore, nodes need to rely on (i)
battery storage, and/or (ii) energy harvesting techniques for their operation.
Prolonging the lifetime of nodes and enhancing network flexibility through
efficient battery management and/or energy harvesting techniques has received
a lot of attention in recent years in the area of networked control systems
[32, 33, 21, 23, 2].

Battery-driven operation is of particular importance in cases where wireless
networks are deployed in remote and inaccessible places (with no fixed
infrastructure). However, modern wireless networks may consist of thousands of
nodes and replacing/recharging batteries may be a costly, time-consuming or
even infeasible task. Therefore, researchers have proposed several battery-
driven energy conservation strategies to ensure energy efficient network
operation. In [34] the authors present a power and coding control algorithm
for state estimation with wireless sensors. An online scheduling scheme was
developed in [17] under communication energy constraints for remote state
estimation. In [14] the authors study the control scheme of a linear plant
when state information is being transmitted from a sensor to the controller
over a wireless fading channel. Additionally, the graph routing problem
optimized for maximizing network lifetime is analyzed in [47]. Finally, self-
triggered control determines its next execution time according to the
triggering rule and previously received data [46] allowing for better
allocation of network resources. Note, however, that battery-driven operation
consists of limited energy supply constraints.

Energy constraints are widely regarded as a fundamental limitation of wireless
devices. For this reason, many researchers aimed to develop alternative energy
provision mechanisms by utilizing ambient energy. A sensor network can have
near perpetual operation, by utilizing energy harvesting strategies in order
to harvest ambient energy [23]. However, limitations on energy harvesting
opportunities have led researchers to also work on the direction of efficient
energy management in wireless sensor networks with energy harvesting
capabilities. Specifically, power control policies for maximizing throughput
or minimizing mean delay or transmission completion time were presented in
[42, 44], whereas power control algorithms for maximizing the mutual
information of a wireless link were discussed in [19]. Jointly controlling
data queue and battery buffer in order to maximize the long-term average
sensing rate was presented in [26], while in [27] a sensor with energy
harvesting capabilities that sends its measurements toward a remote estimator
is considered. The design of optimal sensor transmission power control schemes
was presented in [22], and in [12] the distortion minimization problem by
optimizing sleep-wake scheduling and transmit power was considered. In [21],
the authors presented optimal transmission scheduling schemes in the presence
of energy-leaking sensor batteries. The authors of [6] improved throughput
performance by considering circuit power and non-ideal batteries. In [45] an
energy-harvesting scheduler is considered which makes independent observations
and in [29] an optimization framework to minimize the summation of packet
dropping probability is presented. In [40] the authors construct and analyze a
simplified sensor battery model that is used to predict sensor battery
dynamics. However, in practice, the amount of harvested energy may be random
and sometimes insufficient. Thus, energy efficient algorithms for wireless
sensor networks still require further development.

In today’s emerging technologies, the limited battery or harvested energy
associated with wireless networks is a major bottleneck. This bottleneck may
trammel the two main advantages of battery powered or energy harvesting
wireless networks, which are (i) autonomy of the operating nodes, and (ii)
network flexibility. Efficient usage of the limited energy resources is
critically important to support these advantages and prolong the lifetime of
the nodes. For this reason, there is an increasing demand for large scale
network coordination algorithms which operate over battery powered networks or
networks with energy harvesting capabilities, and whose efficient operation
(i) reduces energy consumption, and (ii) achieves a lifetime of several years
using nodes that carry merely hundreds of joules of stored/harvested energy.

In this paper, we focus on distributed control and coordination over wireless
networks nodes that are battery powered or utilize energy harvesting
techniques. We focus on the average consensus problem in which a group of
nodes reaches agreement to a common value that is equal to the average of the
initial states of the nodes [16, 9]. Calculating the average of their initial
states allows nodes to coordinate their actions via a common decision and is
useful in many applications such as load balancing, voting schemes, quantized
privacy protocols (can be used as the basis for various encoding schemes), and
distributed optimization. However, in practical scenarios there exist
constraints on the bandwidth of communication links and the capacity of
physical memories. This means that network links can only allow messages of
limited length (i.e., quantized) to be stored and transmitted between nodes
[8, 7, 38, 39]. Furthermore, the desire to achieve more efficient usage of
network resources has increased the interest in event-triggered algorithms for
distributed coordination and, more generally, distributed control [41, 30,
25]. In most existing applications of wireless networks which consider a
limited source of energy, their operation is not designed to guarantee
efficient communication and energy preservation. Specifically, (i) nodes may
operate in a way that is not “event-based” (i.e., nodes transmit their state
at each iteration, which leads to increased energy consumption), or (ii) nodes
do not have a distributed strategy to determine whether convergence has been
achieved (thus they continue transmitting even after convergence has been
achieved, which leads to increased energy and bandwidth consumption), or (iii)
node operation considers the transmission of real-valued states (thus not
guaranteeing efficient communication). This paper aims to fill this gap by
proposing a distributed coordination algorithm that fulfills all above
requirements. Specifically, we focus on three main strategies for slowing down
the depletion of energy in wireless networks: (i) efficient communication,
(ii) event-triggered operation, and (iii) transmission stopping. To the
authors’ knowledge, only [36] presents an algorithm which allows nodes in a
data center to coordinate and perform task allocation by exchanging quantized
messages and eventually stopping their operation according to a distributed
mechanism. However, the distributed stopping mechanism in [36] requires
knowledge of the digraph diameter which is a global parameter. Thus, the
design of distributed coordination algorithms which (i) operate in an event-
based fashion, (ii) consider efficient (quantized) communication, (iii)
converge to the exact quantized average of the initial states without any
quantization error, and (iv) utilize a distributed stopping mechanism for
ceasing transmissions without knowledge of global network parameters, is still
an open question.

###  1.1 Main Contributions

In this paper, we present a novel distributed average consensus algorithm for
battery powered or energy harvesting wireless networks, that combines the
desirable features mentioned above. More specifically, average consensus is
reached in finite time; processing, storing, and exchange of information
between neighboring nodes is subject to uniform quantization; and the control
actuation at each node is “event-driven”. The main contributions of our paper
are the following.

  * •

We present a novel distributed algorithm that is able to calculate the exact
average of the initial values in the form of a quantized fraction (i.e., as
the ratio of two integer values) introducing no quantization error111Note that
most algorithms in the available literature (see [20, 28, 7]) are able to
converge to the ceiling or the floor of the initial average thus introducing a
quantization error..

  * •

We show that our algorithm converges to the desired result after a finite
number of iterations, and we provide a polynomial upper bound on the number of
time steps needed for convergence222The operation of our algorithm in this
paper is analyzed over static directed graphs. However, it can be extended
also to dynamic networks which is a more suitable scenario for controlling UAV
swarms and autonomous vehicles..

  * •

We show that our algorithm utilizes its distributed stopping capability and
transmissions are ceased for every node once the exact quantized average of
the initial states is calculated.

  * •

We calculate an upper bound on the number of transmissions and computations
each node performs during the operation of our algorithm.

  * •

We analyze the consumption of available resources by calculating an upper
bound on the required memory and the required energy for each node during the
operation of our algorithm.

  * •

We demonstrate the operation of our algorithm via examples while we analyze
its potential advantages and its transmission stopping capabilities.

The operation of the proposed event-triggered algorithm essentially involves
directed transmissions and broadcast transmissions from every node according
to multiple event-triggered conditions. Specifically, every node broadcasts to
every out-neighbor the value of its initial quantized state. This means that
every node learns the maximum initial state in the network. Then, the nodes
which have an initial state less than the maximum value transmit their
quantized initial state directly to one neighboring node. The nodes that
receive multiple directed messages from neighboring nodes sum the values,
update their state and broadcast the updated state according to a set of event
triggered conditions. The operation of the algorithm ensures that every
initial quantized state is summed in a single node in the network. Then this
node broadcasts its updated state (which is equal to the exact average of the
initial quantized states) and every node in the network learns and updates its
own state to be equal to the exact average. Once every node learns the state
that is equal to the exact average convergence has been achieved and
transmissions are ceased.

Following [20, 7] we assume that the node’s states are integer-valued (which
comprises a uniform class of quantization effects). Note that most work
dealing with quantization has concentrated on the scenario where the nodes can
store and process real-valued states but can transmit only quantized values
through limited rate channels (see, [8]). However, by contrast, our assumption
is also suited to the case where the states are stored in digital memories of
finite capacity (as in [28, 20, 7]), as long as the initial values are also
quantized.

###  1.2 Paper Organization

The remainder of this paper is organized as follows. In Section 2, we
introduce the notation used throughout the paper. In Section 3 we formulate
the finite transmission quantized average consensus problem. In Section 4, we
present a deterministic event-triggered distributed algorithm, which (i)
allows the nodes to reach consensus to the exact quantized average of the
initial values after a finite number of steps, and (ii) allows them to cease
transmissions once quantized average consensus is reached. Furthermore, we
analyze the algorithm’s operation via an example, and we calculate a worst
case upper bound on the number of time steps required for convergence. In
Section 5, we present a deterministic upper bound on the number of
transmissions and computations each node performs during the operation of the
algorithm. In Section 6, we analyze the consumption of resources by
calculating an upper bound on the required memory and the required energy of
each node for the execution of the proposed algorithm. In Section 7, we
present simulation results and comparisons. We conclude in Section 8 with a
brief summary and remarks about future work.

##  2 NOTATION AND BACKGROUND

The sets of real, rational, integer and natural numbers are denoted by
$\mathds{R},\mathds{Q},\mathds{Z}$ and $\mathds{N}$, respectively. The symbol
$\mathds{Z}_{+}$ denotes the set of nonnegative integers.

###  2.1 Graph-Theoretic Notions

Consider a network of $n$ ($n\geq 2$) nodes communicating only with their
immediate neighbors. The communication topology can be captured by a directed
graph (digraph), called communication digraph. A digraph is defined as
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{v_{1},v_{2},\dots,v_{n}\\}$ is the set of nodes and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}-\\{(v_{j},v_{j})\ |\
v_{j}\in\mathcal{V}\\}$ is the set of edges (self-edges excluded). A directed
edge from node $v_{i}$ to node $v_{j}$ is denoted by
$m_{ji}\triangleq(v_{j},v_{i})\in\mathcal{E}$, and captures the fact that node
$v_{j}$ can receive information from node $v_{i}$ (but not the other way
around). We assume that the given digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ is strongly connected (i.e., for
each pair of nodes $v_{j},v_{i}\in\mathcal{V}$, $v_{j}\neq v_{i}$, there
exists a directed path333A directed path from $v_{i}$ to $v_{j}$ exists if we
can find a sequence of vertices $v_{i}\equiv
v_{l_{0}},v_{l_{1}},\dots,v_{l_{t}}\equiv v_{j}$ such that
$(v_{l_{\tau+1}},v_{l_{\tau}})\in\mathcal{E}$ for $\tau=0,1,\dots,t-1$. from
$v_{i}$ to $v_{j}$), which is the necessary (and sufficient) requirement for
average consensus to be possible. The subset of nodes that can directly
transmit information to node $v_{j}$ is called the set of in-neighbors of
$v_{j}$ and is represented by
$\mathcal{N}_{j}^{-}=\\{v_{i}\in\mathcal{V}\;|\;(v_{j},v_{i})\in\mathcal{E}\\}$,
while the subset of nodes that can directly receive information from node
$v_{j}$ is called the set of out-neighbors of $v_{j}$ and is represented by
$\mathcal{N}_{j}^{+}=\\{v_{l}\in\mathcal{V}\;|\;(v_{l},v_{j})\in\mathcal{E}\\}$.
The cardinality of $\mathcal{N}_{j}^{-}$ is called the in-degree of $v_{j}$
and is denoted by $\mathcal{D}_{j}^{-}=|\mathcal{N}_{j}^{-}|$, while the
cardinality of $\mathcal{N}_{j}^{+}$ is called the out-degree of $v_{j}$ and
is denoted by $\mathcal{D}_{j}^{+}=|\mathcal{N}_{j}^{+}|$.

###  2.2 Node Operation

With respect to quantization of information flow, we have that at time step
$k\in\mathds{Z}_{+}$ (where $\mathds{Z}_{+}$ is the set of nonnegative
integers), each node $v_{j}\in\mathcal{V}$ maintains the transmission
variables $S\\_br_{j}\in\mathds{N}$ and $M\\_tr_{j}\in\mathds{N}$, the state
variables $y^{s}_{j}[k]\in\mathds{Z}$, $z^{s}_{j}[k]\in\mathds{Z}_{+}$ and
$q_{j}^{s}[k]=\frac{y_{j}^{s}[k]}{z_{j}^{s}[k]}$, and the mass variables
$y_{j}\in\mathds{Z}$ and $z_{j}\in\mathds{Z}_{+}$. Note here that for every
node $v_{j}$ the transmission variables $S\\_br_{j}$, $M\\_tr_{j}$ are used to
decide whether it will broadcast its state variables or transmit its mass
variables, the state variables $y^{s}_{j}[k],z^{s}_{j}[k],q_{j}^{s}[k]$ are
used to store the received messages and calculate the quantized average of the
initial values, and the mass variables $y_{j}[k],z_{j}[k]$ are used to
communicate with other nodes by either transmitting or receiving messages.

Furthermore, we assume that each node is aware of its out-neighbors and can
directly transmit messages to each out-neighbor; however, it cannot
necessarily receive messages (at least not directly) from them. In the
proposed distributed protocol, each node $v_{j}$ assigns a unique order in the
set $\\{0,1,...,\mathcal{D}_{j}^{+}-1\\}$ to each of its outgoing edges
$m_{lj}$, where $v_{l}\in\mathcal{N}^{+}_{j}$. More specifically, the order of
link $(v_{l},v_{j})$ for node $v_{j}$ is denoted by $P_{lj}$ (such that
$\\{P_{lj}\;|\;v_{l}\in\mathcal{N}^{+}_{j}\\}=\\{0,1,...,\mathcal{D}_{j}^{+}-1\\}$).
This unique predetermined order is used during the execution of the proposed
distributed algorithm as a way of allowing node $v_{j}$ to transmit messages
to its out-neighbors in a round-robin444When executing the proposed protocol,
each node $v_{j}$ transmits to its out-neighbors, one at a time, by following
a predetermined order. The next time it transmits to an out-neighbor, it
continues from the outgoing edge it stopped the previous time and cycles
through the edges in a round-robin fashion according to the predetermined
ordering. fashion.

##  3 PROBLEM FORMULATION

Consider a strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$, where each node
$v_{j}\in\mathcal{V}$ has an initial (i.e., for $k=0$) quantized value
$y_{j}[0]$ (for simplicity, we take $y_{j}[0]\in\mathds{Z}$). In this paper,
we develop a distributed algorithm that allows nodes to address the problem
presented below, while processing and transmitting quantized information via
available communication links.

Each node $v_{j}$ obtains, after a finite number of steps, a fraction $q^{s}$
which is equal to the exact average $q$ of the initial values of the nodes
(i.e., there is no quantization error), where

$q=\frac{\sum_{l=1}^{n}{y_{l}[0]}}{n}.$ (1)

Specifically, we argue that there exists $k_{0}$ so that for every $k\geq
k_{0}$ we have

$y^{s}_{j}[k]=\frac{\sum_{l=1}^{n}{y_{l}[0]}}{\alpha}\ \ \text{and}\ \
z^{s}_{j}[k]=\frac{n}{\alpha},$ (2)

where $\alpha\in\mathds{N}$. This means that

$q^{s}_{j}[k]=\frac{(\sum_{l=1}^{n}{y_{l}[0]})/\alpha}{n/\alpha}\coloneqq q,$
(3)

for every $v_{j}\in\mathcal{V}$ (i.e., for $k\geq k_{0}$ every node $v_{j}$
has calculated $q$ as the ratio of two integer values). Furthermore, we have
that every node $v_{j}$ stops performing transmissions towards its out-
neighbors $v_{l}\in\mathcal{N}^{+}_{j}$ once its state variables $y^{s}_{j}$,
$z^{s}_{j}$, $q^{s}_{j}$ fulfill (2) and (3), respectively.

##  4 EVENT-TRIGGERED QUANTIZED AVERAGE CONSENSUS ALGORITHM WITH FINITE
TRANSMISSION CAPABILITIES

In this section we present a distributed algorithm which achieves exact
quantized average consensus in a finite number of time steps. Also, once
average consensus is reached, all transmissions are ceased. The main idea is
to maintain a separate mechanism for broadcasting the state variables and the
mass variables of each node (as long as they satisfy certain event trigger
conditions). This way, nodes learn the average but also have a way to decide
when (or not) to transmit.

###  4.1 Finite Transmission Event-Triggered Algorithm

The details of the distributed algorithm with transmission stopping
capabilities can be seen in Algorithm 1.

Algorithm 1 Finite Transmission Event-Triggered Quantized Average Consensus

Input: A strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ with $n=|\mathcal{V}|$ nodes and
$m=|\mathcal{E}|$ edges. Each node $v_{j}\in\mathcal{V}$ has an initial state
$y_{j}[0]\in\mathds{Z}$.
Initialization: Each node $v_{j}\in\mathcal{V}$ does the following:

  * 1)

Assigns to each outgoing edge $v_{l}\in\mathcal{N}^{+}_{j}$ a unique order
$P_{lj}$ in the set $\\{0,1,...,\mathcal{D}_{j}^{+}-1\\}$.

  * 2)

Sets $z_{j}[0]=1$, $z^{s}_{j}[0]=1$, $y^{s}_{j}[0]=y_{j}[0]$,
$q^{s}_{j}[0]=y^{s}_{j}[0]/z^{s}_{j}[0]$ and $S\\_br_{j}=0$, $M\\_tr_{j}=0$.

  * 3)

Broadcasts $z^{s}_{j}[0]$, $y^{s}_{j}[0]$ to every
$v_{l}\in\mathcal{N}_{j}^{+}$.

Iteration: For $k=0,1,2,\dots$, each node $v_{j}\in\mathcal{V}$ does the
following:

  * 1)

Receives $y^{s}_{i}[k]$, $z^{s}_{i}[k]$ from every
$v_{i}\in\mathcal{N}_{j}^{-}$ (if no message is received it sets
$y^{s}_{i}[k]=0$, $z^{s}_{i}[k]=0$).

  * 2)

Receives $y_{i}[k]$, $z_{i}[k]$ from each $v_{i}\in\mathcal{N}_{j}^{-}$ and
sets

$y_{j}[k+1]=y_{j}[k]+\sum_{v_{i}\in\mathcal{N}_{j}^{-}}w_{ji}[k]y_{i}[k],$
$z_{j}[k+1]=z_{j}[k]+\sum_{v_{i}\in\mathcal{N}_{j}^{-}}w_{ji}[k]z_{i}[k],$

where $w_{ji}[k]=1$ if a message with $y_{i}[k]$, $z_{i}[k]$ is received from
in-neighbor $v_{i}$, otherwise $w_{ji}[k]=0$.

  * 3)

If $w_{ji}[k]\neq 0$ or $z^{s}_{i}[k]\neq 0$ for some
$v_{i}\in\mathcal{N}_{j}^{-}$ then

    * 3a)

Calls Algorithm 1.A.

    * 3b)

If $M\\_tr_{j}=1$ then chooses $v_{l}\in\mathcal{N}_{j}^{+}$ according to
$P_{lj}$ (in a round-robin fashion) and transmits $y_{j}[k]$, $z_{j}[k]$.
Then, sets $y_{j}[k]=0$, $z_{j}[k]=0$, $M\\_tr_{j}=0$.

    * 3c)

If $S\\_br_{j}=1$ then broadcasts $z^{s}_{j}[k+1]$, $y^{s}_{j}[k+1]$ to every
$v_{l}\in\mathcal{N}_{j}^{+}$. Then, sets $S\\_br_{j}=0$.

  * 4)

Repeats (increases $k$ to $k+1$ and goes back to Step $1$).

Output: (3) holds for every $v_{j}\in\mathcal{V}$.

Algorithm 1.A Event-Triggered Conditions for Algorithm 1 (for each node
$v_{j}$)

Input
$y^{s}_{j}[k]$, $z^{s}_{j}[k]$, $q^{s}_{j}[k]$, $y_{j}[k+1]$, $z_{j}[k+1]$,
$S\\_br_{j}$, $M\\_tr_{j}$ and the received $y^{s}_{i}[k]$, $z^{s}_{i}[k]$
from every $v_{i}\in\mathcal{N}_{j}^{-}$.
Execution

  * 1)

Event Trigger Conditions $1$: If
Condition $(i)$: $z^{s}_{i}[k]>z^{s}_{j}[k]$, or
Condition $(ii)$: $z^{s}_{i}[k]=z^{s}_{j}[k]$ and $y^{s}_{i}[k]>y^{s}_{j}[k]$,
then sets

$z^{s}_{j}[k+1]=\max_{v_{i}\in\mathcal{N}_{j}^{-}}z^{s}_{i}[k],\ \ \text{and}$
$y^{s}_{j}[k+1]=\max_{v_{i}\in\\{v_{i^{\prime}}\in\mathcal{N}_{j}^{-}|z^{s}_{i^{\prime}}[k]=z^{s}_{j}[k+1]\\}}y^{s}_{i}[k],$

and sets $q^{s}_{j}[k+1]=\frac{y^{s}_{j}[k+1]}{z^{s}_{j}[k+1]}$, and
$S\\_br_{j}=1$.

  * 2)

Event Trigger Conditions $2$: If
Condition $(i)$: $z_{j}[k+1]>z^{s}_{j}[k+1]$, or
Condition $(ii)$: $z_{j}[k+1]=z^{s}_{j}[k+1]$ and $y_{j}[k+1]>y^{s}_{j}[k+1]$,
then sets $z^{s}_{j}[k+1]=z_{j}[k+1]$, $y^{s}_{j}[k+1]=y_{j}[k+1]$ and sets
$q^{s}_{j}[k+1]=\frac{y^{s}_{j}[k+1]}{z^{s}_{j}[k+1]}$ and $S\\_br_{j}=1$.

  * 3)

Event Trigger Conditions $3$: If
Condition $(i)$: $0<z_{j}[k+1]<z^{s}_{j}[k+1]$ or
Condition $(ii)$: $z_{j}[k+1]=z^{s}_{j}[k+1]$ and $y_{j}[k+1]<y^{s}_{j}[k+1]$,
then sets $M\\_tr_{j}=1$.

Output
$y^{s}_{j}[k]$, $z^{s}_{j}[k]$, $q^{s}_{j}[k]$, $S\\_br_{j}$, $M\\_tr_{j}$.

The intuition behind Algorithm 1 is the following. Let us first consider the
notion of “leading mass”. During time step $k$, the node that holds the pair
of mass variables with the largest $z[k]$ value is referred to as the “leading
mass” (pair). In case there are multiple nodes with pairs of mass variables
that have the largest $z[k]$, then the “leading mass” is the pair (or pairs)
of mass variables that has (or have) the largest $y[k]$ value among the pairs
of mass variables with the largest $z[k]$. Note that a formal definition of
the “leading mass” is presented in Subsection 4.2. During the Initialization
process, each node $v_{j}$ considers its set of stored mass variables to be
the “leading mass”. For this reason, it sets its state variables to be equal
to the stored mass variables, and then broadcasts the values of its state
variables. During the Iteration process, each node $v_{j}$ (i) receives any
(possibly) transmitted set of state variables from its in-neighbors and, (ii)
receives and stores any (possibly) transmitted set of mass variables from its
in-neighbors. If it received a set of state variables and/or a set of mass
variables from its in-neighbors, then it executes Algorithm 1.A. During the
execution of Algorithm 1.A, each node checks (i) Event Trigger Conditions $1$,
(ii) Event Trigger Conditions $2$, and (iii) Event Trigger Conditions $3$. In
Event Trigger Conditions $1$, it checks whether the received set of state
variables is equal to the “leading mass” (in case it receives messages from
multiple in-neighbors it checks which set of state variables is the “leading
mass”). If Event Trigger Conditions $1$ hold, it sets its state variables to
be equal to the received set of state variables which is the “leading mass”
and decides to broadcast its updated state variables (i.e., sets its
transmission variable $S\\_br_{j}=1$). In Event Trigger Conditions $2$, it
checks whether the set of mass variables it stored is the “leading mass”. If
Event Trigger Conditions $2$ hold, it sets its state variables to be equal to
the stored set of mass variables and decides to broadcast its updated state
variables (i.e., sets its transmission variable $S\\_br_{j}=1$). In Event
Trigger Conditions $3$, it checks whether the set of mass variables it stored
is not the “leading mass”. Specifically, it checks whether its state variables
are equal to the “leading mass”. If Event Trigger Conditions $3$ hold, this
means that the mass variables of another node in the network is the “leading
mass” (and the state variables of node $v_{j}$ became equal to the “leading
mass” from Event Trigger Conditions $1$). This means the stored mass variables
is not the “leading mass” and thus $v_{j}$ decides to transmit its stored mass
variables (i.e., sets its transmission variable $M\\_tr_{j}=1$). Once
Algorithm 1.A is executed, $v_{j}$ returns to the Iteration process of
Algorithm 1 and broadcasts its state variables and/or transmits its mass
variables according to its transmission variables. Then, it repeats the
procedure.

######  Remark 1.

Notice here that each node $v_{j}$, during time step $k$, is able to perform
two types of transmissions towards its out-neighbors
$v_{l}\in\mathcal{N}_{j}^{+}$. It can broadcast (to all of its out-neighbors)
its state variables $y^{s}_{j}[k]$ and $z^{s}_{j}[k]$ (if Event Trigger
Conditions $1$ and/or Event Trigger Conditions $2$ hold) and it can transmit
its mass variables $y_{j}[k]$ and $z_{j}[k]$ to a single out-neighbor, chosen
according to the predetermined order $P_{lj}$ (if Event Trigger Conditions $3$
hold). This may seem as a departure from the literature on average consensus
which assumes only a broadcast primitive (see [11, 15, 13] and references
therein) and the literature on quantized average consensus which assumes only
a unicast primitive (i.e., directed transmissions) [20, 7, 38, 37], or a
broadcast primitive [8]. However, with broadcast as sole primitive and without
additional assumptions, achieving the exact average (i.e., avoiding an error
introduced due to quantization) would be impossible (see [18]) while with
unicast as a sole primitive exhibiting distributed stopping capabilities in
order to terminate transmissions also appears difficult (e.g., see [38] where
the number of transmissions at each time step monotonically decreases but it
never becomes equal to zero). For this reason, each node $v_{j}$ is allowed to
perform both types of transmissions (broadcast and unicast) and, as we will
also see later, this achieves both exact average and transmission termination
during the operation of Algorithm 1. This is a direct result of Event Trigger
Conditions $1$, $2$ and $3$ that characterize the operation of our algorithm
and they effectively imply that no transmission is performed if no set of
conditions holds when using Algorithm 1.A to check them.

It is also important to note that Algorithm 1 can be applied to the standard
average consensus problem, where the initial value of each node and the
transmitted messages are real values. In this case, our proposed protocol
allows deterministic convergence to the exact value after a finite number of
time steps. This is an important aspect as most finite time algorithms are
only able to calculate the average of the initial values within an error bound
(e.g., see [24] and references therein) which is a direct consequence of their
asymptotic convergence. $\hfill\blacksquare$

During the operation of Algorithm 1, nodes are able to reach quantized average
consensus after a finite number of steps. Depending on the graph structure and
the initial mass variables of each node, we have the following two possible
scenarios:

  1. A.

Full Mass Summation (i.e., there exists $k^{\prime}_{0}\in\mathds{Z}_{+}$
where we have $y_{j}[k^{\prime}_{0}]=\sum_{l=1}^{n}{y_{l}[0]}\ \ \text{and}\ \
z_{j}[k^{\prime}_{0}]=n$, for some node $v_{j}\in\mathcal{V}$, and
$y_{i}[k^{\prime}_{0}]=0\ \ \text{and}\ \ z_{i}[k^{\prime}_{0}]=0$, for each
$v_{i}\in\mathcal{V}-\\{v_{j}\\}$). In this scenario (2) and (3) hold
(eventually, for some $k_{0}>k_{0}^{\prime}$) for each node $v_{j}$ for the
case where $\alpha=1$.

  2. B.

Partial Mass Summation (i.e., there exists $k^{\prime}_{0}\in\mathds{Z}_{+}$
so that for every $k\geq k^{\prime}_{0}$ there exists a set
$\mathcal{V}^{p}[k]\subseteq\mathcal{V}$ in which we have $y_{j}[k]=y_{i}[k]$
and $z_{j}[k]=z_{i}[k]$, $\forall v_{j},v_{i}\in\mathcal{V}^{p}[k]$ and
$y_{l}[k]=0\ \ \text{and}\ \ z_{l}[k]=0$, for each
$v_{l}\in\mathcal{V}-\mathcal{V}^{p}[k]$). In this scenario, (2) and (3) hold
(eventually, for some $k_{0}>k_{0}^{\prime}$) for each node $v_{j}$ for the
case where $\alpha=|\mathcal{V}^{p}[k]|$.

We now illustrate the event-triggered behavior of the proposed distributed
algorithm via an example where we have “Partial Mass Summation”.

######  Example 1.

Consider a strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$, shown in Fig. 1, with
$\mathcal{V}=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and
$\mathcal{E}=\\{m_{31},m_{41},m_{12},m_{13},m_{43},m_{24}\\}$ where each node
has an initial quantized value $y_{1}[0]=2$, $y_{2}[0]=4$, $y_{3}[0]=7$ and
$y_{4}[0]=9$ respectively. The average of the initial values, is equal to
$q=\frac{22}{4}$.

Figure 1: Example of digraph for partial mass summation when using Algorithm
1.

Each node $v_{j}\in\mathcal{V}$ follows the Initialization steps in Algorithm
1. This means that it assigns to each of its outgoing edges
$v_{l}\in\mathcal{N}^{+}_{j}$ a unique order $P_{lj}$ in the set
$\\{0,1,...,\mathcal{D}_{j}^{+}-1\\}$. Assume that the unique orders assigned
by each node are the following: $v_{1}:P_{41}=0,P_{31}=1;\ v_{2}:P_{12}=0;\
v_{3}:P_{13}=0,P_{43}=1,\ v_{4}:P_{24}=0.$ For example, node $v_{1}$ will
first transmit towards node $v_{4}$ and then transmit towards node $v_{3}$.
Furthermore, according to the Initialization steps, each node $v_{j}$ sets its
transmission variables $S\\_br_{j}=0$, $M\\_tr_{j}=0$ and then it broadcasts
its state variables $z^{s}_{j}[0]$ and $y^{s}_{j}[0]$ to every out-neighbor
$v_{l}\in\mathcal{N}_{j}^{+}$. The initial mass and state variables, at time
step $k=0$, for nodes $v_{1},v_{2},v_{3},v_{4}$ are shown in Table 1.

During the operation of Algorithm 1, at time step $k=0$ each node $v_{j}$ will
receive the state variables $z^{s}_{i}[0]$ and $y^{s}_{i}[0]$ from every in-
neighbor $v_{i}\in\mathcal{N}_{j}^{-}$ (however, it will not receive any set
of mass variables $z_{i}[0]$ and $y_{i}[0]$ from any in-neighbor
$v_{i}\in\mathcal{N}_{j}^{-}$). According to the Event Trigger Conditions $1$,
nodes $v_{1}$ and $v_{2}$ will update their state variables and then set
$S\\_br_{1}=1$, $S\\_br_{2}=1$ (nodes $v_{3}$ and $v_{4}$ will maintain
$S\\_br_{3}=0$ and $S\\_br_{4}=0$ since Event Trigger Conditions $1$ do not
hold for them). Furthermore, Event Trigger Conditions $2$ do not hold for any
node but Event Trigger Conditions $3$ hold for nodes $v_{1}$ and $v_{2}$ who
set $M\\_tr_{1}=1$ and $M\\_tr_{2}=1$ (nodes $v_{3}$ and $v_{4}$ will maintain
$M\\_tr_{3}=0$ and $M\\_tr_{4}=0$ since Event Trigger Conditions $3$ do not
hold for them). Then nodes $v_{1}$ and $v_{2}$ will broadcast their state
variables to every out-neighbor (since $S\\_br_{1}=1$, $S\\_br_{2}=1$) and
then they will transmit their mass variables according to their unique
predetermined order (since $M\\_tr_{1}=1$ and $M\\_tr_{2}=1$). Furthermore,
they will set $S\\_br_{1}=0$, $M\\_tr_{1}=0$ and $S\\_br_{2}=0$,
$M\\_tr_{2}=0$ since they transmitted their state and mass variables. The mass
and state variables, at time step $k=1$, for nodes $v_{1},v_{2},v_{3},v_{4}$
are shown in Table 1.

During time step $k=1$, each node $v_{j}$ will receive the state variables and
the mass variables from every in-neighbor. Specifically, node $v_{1}$ will
receive the mass variables of node $v_{2}$ and node $v_{4}$ will receive the
mass variables of node $v_{1}$. Following Event Trigger Conditions $1$,
$v_{1}$ will update its state variables and set $S\\_br_{1}=1$. Then,
following Event Trigger Conditions $2$, node $v_{4}$ will update its mass
variables and set $S\\_br_{4}=1$. Following Event Trigger Conditions $3$, node
$v_{1}$ will set $M\\_tr_{1}=1$. Nodes $v_{1}$ and $v_{4}$ will broadcast
their state variables to every out-neighbor (since $S\\_br_{1}=1$,
$S\\_br_{4}=1$) and node $v_{1}$ will transmit its mass variables according to
its unique predetermined order towards node $v_{3}$ (since $M\\_tr_{1}=1$).
Then, nodes $v_{1}$, $v_{4}$ will set $S\\_br_{1}=0$, $S\\_br_{4}=0$ and node
$v_{1}$ will set $M\\_tr_{1}=0$. The mass and state variables, at time step
$k=2$, for nodes $v_{1},v_{2},v_{3},v_{4}$ are shown in Table 1.

Repeating the steps above, in Table 1 we can see the mass and state variables,
at time step $k=3$. In Table 1 we can see that for the set
$\mathcal{V}^{p}[3]=\\{v_{3},v_{4}\\}$ we have $y_{3}[3]=y_{4}[3]$ and
$z_{3}[3]=z_{4}[3]$ while, for the set
$\mathcal{V}-\mathcal{V}^{p}[3]=\\{v_{1},v_{2}\\}$ we have
$y_{1}[3]=y_{2}[3]=0$ and $z_{1}[3]=z_{2}[3]=0$. This means that we have a
“Partial Mass Summation” scenario. In this case, we will see that Event
Trigger Conditions $2$ will not hold again for any node for time steps $k>3$
(i.e., no node will transmit again its mass variables).

Table 1: Mass and State Variables for Fig. 1. Node |  Mass and State Variables for $k=0$
---|---
| $y_{j}[0]$ | $z_{j}[0]$ | $y^{s}_{j}[0]$ | $z^{s}_{j}[0]$ | $q^{s}_{j}[0]$
$v_{1}$ | 2 | 1 | 2 | 1 | 2 / 1
$v_{2}$ | 4 | 1 | 4 | 1 | 4 / 1
$v_{3}$ | 7 | 1 | 7 | 1 | 7 / 1
$v_{4}$ | 9 | 1 | 9 | 1 | 9 / 1
Node |  Mass and State Variables for $k=1$
| $y_{j}[1]$ | $z_{j}[1]$ | $y^{s}_{j}[1]$ | $z^{s}_{j}[1]$ | $q^{s}_{j}[1]$
$v_{1}$ | 2 | 1 | 7 | 1 | 7 / 1
$v_{2}$ | 4 | 1 | 9 | 1 | 9 / 1
$v_{3}$ | 7 | 1 | 7 | 1 | 7 / 1
$v_{4}$ | 9 | 1 | 9 | 1 | 9 / 1
Node |  Mass and State Variables for $k=2$
| $y_{j}[2]$ | $z_{j}[2]$ | $y^{s}_{j}[2]$ | $z^{s}_{j}[2]$ | $q^{s}_{j}[2]$
$v_{1}$ | 4 | 1 | 9 | 1 | 9 / 1
$v_{2}$ | 0 | 0 | 9 | 1 | 9 / 1
$v_{3}$ | 7 | 1 | 7 | 1 | 7 / 1
$v_{4}$ | 11 | 2 | 11 | 2 | 11 / 2
Node |  Mass and State Variables for $k=3$
| $y_{j}[3]$ | $z_{j}[3]$ | $y^{s}_{j}[3]$ | $z^{s}_{j}[3]$ | $q^{s}_{j}[3]$
$v_{1}$ | 0 | 0 | 9 | 1 | 9 / 1
$v_{2}$ | 0 | 0 | 11 | 2 | 11 / 2
$v_{3}$ | 11 | 2 | 11 | 2 | 11 / 2
$v_{4}$ | 11 | 2 | 11 | 2 | 11 / 2
Node |  Mass and State Variables for $k=4$
| $y_{j}[4]$ | $z_{j}[4]$ | $y^{s}_{j}[4]$ | $z^{s}_{j}[4]$ | $q^{s}_{j}[4]$
$v_{1}$ | 0 | 0 | 11 | 2 | 11 / 2
$v_{2}$ | 0 | 0 | 11 | 2 | 11 / 2
$v_{3}$ | 11 | 2 | 11 | 2 | 11 / 2
$v_{4}$ | 11 | 2 | 11 | 2 | 11 / 2

During time step $k=4$, each node will receive the state variables and the
mass variables from every in-neighbor. Node $v_{1}$ will update its state
variables and set $S\\_br_{1}=1$ (according to Event Trigger Conditions $1$).
Then, no transmissions of mass variables will be performed since Event Trigger
Conditions $3$ do not hold for any node; thus, for every node $v_{j}$ we have
$M\\_tr_{j}=0$. Node $v_{1}$ will broadcast its state variables to every out-
neighbor (since $S\\_br_{1}=1$) and every node $v_{j}$ will set
$S\\_br_{j}=0$, $M\\_tr_{j}=0$. However, since the state variables of nodes
$v_{3}$, $v_{4}$ are the same as the updated state variables of node $v_{1}$,
we have the mass and state variables of every node at time step $k=5$ remain
the same as time step $k=4$ (shown in Table 1).

In Table 1, we can see that (2) and (3) hold for every node for $\alpha=2$
(i.e., every node has reached quantized average consensus). Notice that no set
of event trigger conditions holds for any node during time step $k=5$. This
means that no node will perform any transmissions of its state or mass
variables for time steps $k\geq 5$. $\square$

######  Remark 2.

It is interesting to consider here the case where node $v_{1}$ sets its
priorities as $P_{31}=0$ and $P_{41}=1$, during the Initialization of
Algorithm 1. In this case, we will notice the scenario of “Full Mass
Summation” for node $v_{4}$ instead of “Partial Mass Summation” (i.e., (2) and
(3) hold for every node for $\alpha=1$). $\hfill\blacksquare$

###  4.2 Deterministic Convergence Analysis

We now analyze the functionality of Algorithm 1 and prove that it allows all
nodes to reach quantized average consensus after a finite number of steps.
Furthermore, we will also show that once quantized average consensus is
reached, transmissions from each node cease. We first consider the following
setup and then state Lemma 1 and Lemma 2 which are necessary for our
subsequent development.

Setup: Consider a strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ with $n=|\mathcal{V}|$ nodes and
$m=|\mathcal{E}|$ edges. During the execution of Algorithm 1, at time step
$k_{0}$, there is at least one node $v_{j^{\prime}}\in\mathcal{V}$, for which

$z_{j^{\prime}}[k_{0}]\geq z_{i}[k_{0}],\ \forall v_{i}\in\mathcal{V}.$ (4)

Then, among the nodes $v_{j^{\prime}}$ for which (4) holds, there is at least
one node $v_{j}$ for which

$y_{j}[k_{0}]\geq y_{l}[k_{0}],\ \text{where}\ \
v_{j},v_{l}\in\\{v_{j^{\prime}}\in\mathcal{V}\ |\ (\ref{great_z_prop1_det})\
\text{holds}\\}.$ (5)

For notational convenience we will call the pair of mass variables of node
$v_{j}$ for which (4) and (5) hold as the “leading mass” (or “leading masses”
if multiple nodes hold such a pair of values) and the pairs of mass variables
of a node $v_{l}$ for which $z_{l}[k_{0}]>0$ but (4) and (5) do not hold as
the “follower mass” (or “follower masses”). Furthermore, if two (or more)
masses reach a node simultaneously then we say that they “merge”, i.e., the
receiving node “merges” the mass variables it receives by summing their
numerators and their denominators (according to Step $2$ of the Iteration of
Algorithm 1). This way a set of mass variables with a greater denominator is
created.

######  Lemma 1.

If, during time step $k_{0}$ of Algorithm 1, the mass variables of node
$v_{j}$ fulfill (4) and (5), then the state variables of every node
$v_{i}\in\mathcal{V}$ satisfy

$\displaystyle z_{i}^{s}[k_{0}]\leq z_{j}[k_{0}],$ (6)

or

$\displaystyle z_{i}^{s}[k_{0}]=z_{j}[k_{0}]\ \ \text{and}\ \
y_{i}^{s}[k_{0}]\leq y_{j}[k_{0}].$ (7)

Let us consider the variable $z^{(m)}[k]=\max_{v_{l}\in\mathcal{V}}z_{l}[k].$
From Iteration Step $2$ of Algorithm 1 we have that $z^{(m)}[k]$ is non-
decreasing (i.e., $z^{(m)}[k+1]\geq z^{(m)}[k]$, for every $k$). Furthermore,
since the mass variables of node $v_{j}$ fulfill (4) and (5), then, during
time step $k$, it holds that $z_{j}[k]=z^{(m)}[k].$ In addition, for every
$k$, during Execution Steps $1$ and $2$ of Algorithm 1.A, for every node
$v_{i}\in\mathcal{V}$, we have that $z_{i}^{s}[k]$ is either less than
$z^{(m)}[k]$ (i.e., $z_{i}^{s}[k]<z^{(m)}[k]$) or equal to $z^{(m)}[k]$ (i.e.,
$z_{i}^{s}[k]=z^{(m)}[k]$). This is a direct result of $z^{(m)}[k]$ being non-
decreasing and Event Trigger Conditions $1$ and $2$ where, at time step $k$,
the state variables $z_{i}^{s}[k]$, $y_{i}^{s}[k]$ of a node $v_{i}$ are
updated to be (i) either equal to $z_{i}[k]$, $y_{i}[k]$ if
$z_{i}^{s}[k]>z_{i}[k]$ or $z_{i}^{s}[k]=z_{i}[k]$, $y_{i}^{s}[k]>y_{i}[k]$ or
(ii) equal to $z_{i^{\prime}}^{s}[k]$, $y_{i^{\prime}}^{s}[k]$,
$v_{i^{\prime}}\in\mathcal{N}_{i}^{-}$ if $z_{i^{\prime}}^{s}[k]>z_{i}^{s}[k]$
or $z_{i^{\prime}}^{s}[k]=z_{i}^{s}[k]$, $y_{i^{\prime}}^{s}[k]>y_{i}^{s}[k]$.
As a result, at time step $k$, the state variables of every node
$v_{i}\in\mathcal{V}$ satisfy $z_{i}^{s}[k]\leq z_{j}[k].$ Finally, from
Execution Steps $1$ and $2$ of Algorithm 1.A, for every $k$, we have that if
$z_{i}^{s}[k]=z_{j}[k]$ holds for some node $v_{i}$, then we have that either
$y_{i}^{s}[k]<y_{j}[k]$ or $y_{i}^{s}[k]=y_{j}[k]$. [Note here that if
$z_{i}^{s}[k]=z_{j}[k]$ and $y_{i}^{s}[k]>y_{j}[k]$, then the mass variables
of $v_{j}$ do not fulfill (4) and (5) which is a contradiction.] As a result
we have that if the mass variables of node $v_{j}$ fulfill (4) and (5), then
the state variables of every node $v_{i}\in\mathcal{V}$ satisfy (6) or (7).
$\square$

######  Lemma 2.

If, during time step $k_{0}$ of Algorithm 1, the mass variables of each node
$v_{j}$ with nonzero mass variables fulfill (4) and (5), then we have only
leading masses and no follower masses. This means that the Event Trigger
Conditions $3$ will never hold again for future time steps $k\geq k_{0}$. As a
result, the transmissions that (may) take place will be only via broadcasting
(from Event Trigger Conditions $1$ and $2$) for at most $n-1$ time steps and
then they will cease.

Let us assume that during time step $k_{0}$ two (or more) mass variables merge
at nodes $v_{j}$, $v_{i}$, so that these two nodes simultaneously become
leading masses (more generally, we could have more than two leading masses)
and all other nodes have zero mass variables. Since the mass variables of
nodes $v_{j}$, $v_{i}$, during time step $k_{0}$, become leading masses then
there exists a set $\mathcal{V}^{p}[k_{0}]\subseteq\mathcal{V}$ in which we
have $y_{j}[k_{0}]=y_{i}[k_{0}]$ and $z_{j}[k_{0}]=z_{i}[k_{0}]$, $\forall
v_{j},v_{i}\in\mathcal{V}^{p}[k_{0}]$ and $y_{l}[k_{0}]=0\ \ \text{and}\ \
z_{l}[k_{0}]=0$, for each $v_{l}\in\mathcal{V}-\mathcal{V}^{p}[k_{0}]$. Once
this merge occurs then we have that, for both $v_{j}$ and $v_{i}$, the Event
Trigger Conditions $1$ and the Event Trigger Conditions $3$ do not hold, but
Event Trigger Conditions $2$ do hold. This means that $v_{j}$ and $v_{i}$ do
not transmit their mass variables but rather they broadcast their new state
variables to their out-neighbors. Then, their out-neighbors, $v_{l_{j}}$ and
$v_{l_{i}}$ respectively, will update their state variables and broadcast
their new state variables towards their out-neighbors. The updating and
broadcasting of state variables will continue, until all nodes obtain state
variables equal to $z^{s}_{j}[k_{0}]$ and $y^{s}_{j}[k_{0}]$. Note that during
this update and broadcasting of state variables, no node transmits its mass
variables. After at most $n-1$ steps, all nodes will be aware of the values
$z^{s}_{j}[k_{0}]$ and $y^{s}_{j}[k_{0}]$, and at that point all transmissions
will seize. $\square$

######  Theorem 1.

The execution of Algorithm 1 allows each node $v_{j}\in\mathcal{V}$ to reach
quantized average consensus after a finite number of steps $k_{0}$ upper
bounded by $n^{2}+(n-1)m^{2}$, where $n$ is the number of nodes and $m$ is the
number of edges in the network. Furthermore, each node stops transmitting
towards its out-neighbors once quantized average consensus is reached.

Before starting the analysis of Algorithm 1, it is important to note that the
leading mass will not fulfill the Event Trigger Conditions $3$ in Execution
Step $3$ of Algorithm 1.A. This means that the corresponding node (say
$v_{j}$) will not transmit its mass variables to its out-neighbors
$v_{l}\in\mathcal{N}_{j}^{+}$ according to its predetermined priority. In this
proof we will show that there exists $k_{0}\in\mathds{Z}_{+}$ for which the
mass variables of every node $v_{j}$ (for which $z_{j}[k]>0$) fulfill (4) and
(5), for every $k\geq k_{0}$. This means that for $k\geq k_{0}$ we have only
leading masses. Furthermore, from Lemma 2, we have that there exists
$k_{1}>k_{0}$, where for every $k\geq k_{1}$ the state variables of every node
$v_{j}\in\mathcal{V}$ fulfill (2) and (3) for $\alpha\in\mathds{Z}_{+}$ (i.e.,
every node has reached quantized consensus) and thus transmissions cease.

During the Initialization steps of Algorithm 1, we have that each node will
broadcast its state variables to every out-neighbor. Then, during Iteration
Step $1$, each node will receive and update its state variables. When checking
Event Trigger Conditions $1$ it will decide to broadcast towards its out-
neighbors the updated values (of the state variables). This means that after
$n$ iterations (assuming, that no other mass variables merged during $n$ time
steps), the state variables of each node $v_{i}\in\mathcal{V}$ satisfy
$z^{s}_{i}[n]=z_{j_{1}}[0]$ and $y^{s}_{i}[n]=y_{j_{1}}[0]$, where the mass
variables of node $v_{j_{1}}$ are the leading mass. As a result, after $n$
iterations, we have that the Event Trigger Conditions $3$ will hold for every
node $v_{i}\in\mathcal{V}-\\{v_{j_{1}}\\}$. Thus, every node (except node
$v_{j_{1}}$ which is the leading mass) will transmit its mass variables toward
its out-neighbors according to its unique priority. Note here that the number
of iterations required for the follower mass to reach every node
$v_{i}\in\mathcal{V}$ is bounded by $m^{2}$, where $m=|\mathcal{E}|$ is the
number of edges of the given digraph $\mathcal{G}_{d}$ (in this case
Proposition $3$ in [35] provides a bound for the follower mass to travel via
each edge in the graph and thus necessarily also reach every other node). Let
us assume now that, after executing Algorithm 1 for additional $m^{2}$ steps,
we have that the mass variables $z_{i_{1}}[0]$, $y_{i_{1}}[0]$ and
$z_{i_{2}}[0]$, $y_{i_{2}}[0]$ of nodes $v_{i_{1}}$ and $v_{i_{2}}$
respectively, meet (and merge) in node $v_{j_{2}}$, and after this merge they
become the leading mass. This means that node $v_{j_{2}}$ will not transmit
its mass variables during time step $n+m^{2}$ (because Event Trigger
Conditions $3$ do not hold) but it will broadcast its state variables to every
out-neighbor (because Event Trigger Conditions $2$ hold). Thus, after
additional $n$ iterations, the state variables of each node
$v_{i}\in\mathcal{V}$ satisfy $z^{s}_{i}[2n+m^{2}]=z_{j_{2}}[n+m^{2}]$ and
$y^{s}_{i}[2n+m^{2}]=y_{j_{2}}[n+m^{2}]$, where the mass variables of node
$v_{j_{2}}$ are now the leading mass. This means that Event Trigger Conditions
$3$ will hold for every node $v_{i}\in\mathcal{V}-\\{v_{j_{2}}\\}$. Thus,
every node (except node $v_{j_{2}}$ which is now the leading mass) will
transmit its mass variables toward its out-neighbors according to its unique
priority. Note here that also node $v_{j_{1}}$ will transmit its mass
variables toward its out-neighbors (since the state variables of $v_{j_{1}}$
are equal to the mass variables of the leading mass $v_{j_{2}}$, this means
that Event Trigger Conditions $3$ will also hold for $v_{j_{1}}$). Let us
assume now that, after executing Algorithm 1 for additional $m^{2}$ steps, the
mass variables $z_{i_{3}}[0]$, $y_{i_{3}}[0]$ and $z_{i_{4}}[0]$,
$y_{i_{4}}[0]$ of nodes $v_{i_{3}}$ and $v_{i_{4}}$ respectively, meet (and
merge) in node $v_{j_{3}}$. After this merge they become the leading mass.
Again, this means that during time step $2n+2m^{2}$, node $v_{j_{3}}$ will not
transmit its mass variables (because Event Trigger Conditions $3$ do not hold)
but it will broadcast its state variables to every out-neighbor (because Event
Trigger Conditions $2$ hold). After additional $n$ iterations, the state
variables of each node $v_{i}\in\mathcal{V}$ satisfy
$z^{s}_{i}[3n+2m^{2}]=z_{j_{3}}[2n+2m^{2}]$ and
$y^{s}_{i}[3n+2m^{2}]=y_{j_{3}}[2n+2m^{2}]$, where the mass variables of node
$v_{j_{3}}$ are now the new leading mass. By continuing this analysis, we can
see that every $n+m^{2}$ time steps at least two follower masses merge and
become the leading mass. Since, during the Initialization steps of Algorithm
1, we have $n$ initial mass variables this means that after $(n-1)(n+m^{2})$
time steps all initial mass variables will merge into one mass (obviously the
mass variables in which every initial mass has merged is the leading mass).
Thus, at time step $(n-1)n+(n-1)m^{2}$ we have only leading masses and no
follower masses. From Lemma 2, we have that after $n$ additional time steps
every node will have state variables equal to the leading mass (i.e.,
$z^{s}_{i}[n^{2}+(n-1)m^{2}]=n$ and
$y^{s}_{i}[n^{2}+(n-1)m^{2}]=\sum_{l=1}^{n}{y_{l}[0]}$, for every
$v_{i}\in\mathcal{V}$). As a result, each node $v_{j}\in\mathcal{V}$ will
reach quantized average consensus after a finite number of steps $k_{0}$ upper
bounded by $n^{2}+(n-1)m^{2}$ and then transmissions will be ceased.

Note that so far we considered the scenario where there is only one leading
mass during every time step $k$ and it merges with only one nonzero mass
variable every $n+m^{2}$ time steps. In other scenarios, we can consider
multiple leading masses (i.e., the nonzero mass variables fulfill (4) and (5)
for more than one node) which will speed up convergence since the follower
masses will merge more frequently. $\square$

The proof of Theorem 1 analyzes the operation of Algorithm 1 over a static and
strongly connected digraph. It shows that the convergence time of the
algorithm is equal to $n^{2}+(n-1)m^{2}$ (where $n$ is the number of nodes and
$m$ is the number of edges in the network). Note that the finite time
deterministic convergence of the algorithm is achievable due to the unique
order $P_{lj}$ that each node $v_{j}$ assigns to its out-neighbors during the
initialization steps. However, in most applications nowadays, such as control
and coordination of autonomous vehicles or UAV swarms, we have that the
structure of the network is time-varying. Analyzing the operation of Algorithm
1 over time-varying digraphs is outside the scope of this paper and an
extension of the unique order transmission strategy over time-varying networks
is currently an open question. An extension of Algorithm 1 over time-varying
digraphs can be done through the analysis in [39]. Specifically, [39] presents
an algorithm in which each node performs randomized transmissions towards its
out-neighbors (i.e., it chooses an out-neighbor to perform a transmission
according to a nonzero probability) and is shown to operate both in static and
time-varying digraphs allowing convergence with high probability. Thus, an
important future research direction is to extend the operation of Algorithm 1
by applying a randomized transmission strategy. This extension will enhance
the algorithm’s convergence speed (see Fig. $3$ and Fig. $4$ in [39]) and will
allow convergence over time-varying digraphs; however, it will eliminate its
deterministic convergence characteristics, allowing instead finite time
convergence with high probability.

##  5 BOUNDING NUMBER OF TRANSMISSIONS AND COMPUTATIONS

In this section we calculate an upper bound on the number of transmissions and
the number of computations each node $v_{j}$ performs during Algorithm 1.

######  Theorem 2.

During the operation of Algorithm 1, each node $v_{j}$ will perform at most
$n+(n-1)m$ transmissions (where $n$ is the number of nodes and $m$ is the
number of edges in the network) before quantized average consensus is reached
and transmissions are ceased.

During the operation of Algorithm 1 every node $v_{j}$ performs (i) broadcast
transmissions and (ii) directed transmissions. We provide an upper bound for
each transmission type separately.

Broadcast Transmissions: It is easy to see that during Algorithm 1 there are
at most $n-1$ updates of the leading mass (see Theorem 1) which trigger
broadcast transmissions. Considering also the broadcast transmission performed
during the initialization procedure, we have that each node $v_{j}$ will
perform at most $n$ broadcastings towards its out-neigbors during Algorithm 1.

Directed Transmissions (or Unicast Transmissions): Our analysis is based on
Proposition $3$ in [35] which provides a bound for the follower mass to travel
via each edge in the digraph and thus necessarily also reach every other node.
Specifically, considering a strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ (with $n=|\mathcal{V}|$ nodes and
$m=|\mathcal{E}|$ edges) we have that the number of iterations required for
the follower mass to reach every node $v_{i}\in\mathcal{V}$ is bounded by
$m^{2}$, where $m=|\mathcal{E}|$ is the number of edges. This result is
derived from the fact that digraph $\mathcal{G}_{d}$ consists of $C_{\beta}$
cycles, where $C_{\beta}\in\\{1,2,...m\\}$ (see Proposition $3$ in [35]), and
each cycle is traversed at most $m$ times by a follower mass until it reaches
the node (say $v_{i}$) whose mass variables are the leading mass. Let us
consider now that each node $v_{j}$ performs one directed transmission every
time one follower mass traverses the cycle $C_{\beta_{0}}$ (to which node
$v_{j}$ belongs to). This means that node $v_{j}$ will perform at most $m$
directed transmissions until this specific follower mass merges with the
leading mass. Furthermore, we have that initially there are at most $n$ mass
variables and during the operation of Algorithm 1 there are at most $n-1$
mergings. As a result, $n-1$ follower masses will traverse the digraph in
order to merge with the leading mass. This means that each node $v_{j}$ will
perform at most $(n-1)m$ directed transmissions during Algorithm 1.

Combining the results for (i) broadcast transmissions and (ii) directed
transmissions, we have that during the operation of Algorithm 1 each node
$v_{j}$ will perform at most $n+(n-1)m$ transmissions before quantized average
consensus is reached and transmissions are ceased. $\square$

######  Theorem 3.

During Algorithm 1, each node $v_{j}$ will perform at most
$1+(n-1)(m+1+\mathcal{D}_{max}^{-})$ computations (where $n$ is the number of
nodes, $m$ is the number of edges and
$\mathcal{D}_{max}^{-}=\max_{v_{j}\in\mathcal{V}}\mathcal{D}_{j}^{-}$) before
quantized average consensus is reached and transmissions are ceased.

During the operation of Algorithm 1, we consider that a node $v_{j}$ performs
computations if it executes (i) the Initialization steps or (ii) any of the
Iteration Steps $1$, $2$, $3$. The Initialization steps are executed only
once. The Iteration steps are executed at time step $k$ only if a node $v_{j}$
receives a set of state variables $z^{s}_{i}[k]$, $y^{s}_{i}[k]$ during
Iteration Step $1$ or a set of mass variables $z_{i}[k]$, $y_{i}[k]$ during
Iteration Step $2$. Thus, the upper bound on computations is calculated
according to the number of messages each node $v_{j}$ receives during
Algorithm 1.

Computations due to Received Mass Variables: We consider the cases of
computations due to received mass variables that (i) fulfill Event-Triggered
Conditions $2$ of Algorithm 1.A and (ii) fulfill Event-Triggered Conditions
$3$ of Algorithm 1.A.
For the first case we have that there are at most $n-1$ mergings of mass
variables (see Theorem 1). This means that the amount of computations due to
received mass variables that fulfill Event-Triggered Conditions $2$ of
Algorithm 1.A, is upper bounded by $n-1$. For the second case we have that
each node $v_{j}$ will perform a directed transmission for $(n-1)m$ times (see
Theorem 2). This directed transmission is the result of receiving a set of
mass variables which fulfills Event-Triggered Conditions $3$ of Algorithm 1.A.
This means that the amount of computations due to received mass variables that
fulfill Event-Triggered Conditions $3$ of Algorithm 1.A, is upper bounded by
$(n-1)m$. As a result, node $v_{j}$ will perform computations for received
mass variables (by checking Event-Triggered Conditions $2$ or Event-Triggered
Conditions $3$) for at most $(n-1)(m+1)$ times.

Computations due to Received State Variables: From Theorem 1 we have that
during Algorithm 1 there are at most $n-1$ updates of the leading mass which
trigger broadcast transmissions among nodes in the network. This means that
node $v_{j}$ will receive a set of state variables $z^{s}_{i}[k]$,
$y^{s}_{i}[k]$ from its in-neighbors for at most $(n-1)\mathcal{D}_{max}^{-}$
times, where
$\mathcal{D}_{max}^{-}=\max_{v_{j}\in\mathcal{V}}\mathcal{D}_{j}^{-}$. As a
result, node $v_{j}$ will perform computations for received state variables
(by checking Event-Triggered Conditions $1$) for at most
$(n-1)\mathcal{D}_{max}^{-}$ times.

We now consider the computations during the Initilization steps and we combine
them with the results of computations for (i) received mass variables and (ii)
received state variables. As a result, we have that during the operation of
Algorithm 1, each node $v_{j}$ will perform at most
$1+(n-1)(m+1+\mathcal{D}_{max}^{-})$ computations (where
$\mathcal{D}_{max}^{-}=\max_{v_{j}\in\mathcal{V}}\mathcal{D}_{j}^{-}$) before
quantized average consensus is reached, and computations along with
transmissions are ceased. $\square$

The result of Theorem 3 depends on the number of incoming messages since, from
the operation of Algorithm 1, each node performs a computation only after a
transmission has been received. Furthermore, if no messages are received
(i.e., no mass or state variables are received) then, during the operation of
Algorithm 1, each node will not execute Iteration Steps $1$, $2$ and $3$ and
thus it will remain in hibernation mode (i.e., awaiting to receive signals
without performing any computations). As a result, since the number of
transmissions that each node performs during the operation of Algorithm 1 is
upper bounded (see Theorem 2) then the number of computations is also upper
bounded and the bound depends on the number of incoming messages.

##  6 MEMORY AND ENERGY REQUIREMENTS FOR ACHIEVING QUANTIZED AVERAGE CONSENSUS

In this section we focus on the consumption of available resources from each
node in the network. Specifically, we calculate an upper bound on the memory
and energy each node $v_{j}$ requires during Algorithm 1.

###  6.1 Required Memory

We first characterize the memory requirements of each node $v_{j}$ during the
operation of Algorithm 1.

######  Proposition 1.

During the operation of Algorithm 1, the memory requirement of each node
$v_{j}$ is (i) $7+4\mathcal{D}_{j}^{-}$ locations for integer values, and (ii)
$2+(3+2\mathcal{D}_{j}^{-})\lceil\log_{2}n\rceil+(3+2\mathcal{D}_{j}^{-})\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil$
bits for binary numbers.

During the operation of Algorithm 1, each node $v_{j}$ needs to store (i) $2$
transmission variables $S\\_br_{j}$, $M\\_tr_{j}$, (ii) $2$ mass variables
$y_{j}[k]$, $z_{j}[k]$, (iii) $3$ state variables $y^{s}_{j}[k]$,
$z^{s}_{j}[k]$, $q^{s}_{j}[k]$, and (iv) $4$ mass and state variables
$y_{i}[k]$, $z_{i}[k]$, $y^{s}_{i}[k]$, $z^{s}_{i}[k]$ for each
$v_{i}\in\mathcal{N}_{j}^{-}$ (i.e., $2$ mass variables and $2$ state
variables that node $v_{j}$ may receive from each in-neighbor respectively).
This means that the memory requirements of node $v_{j}$ is
$7+4\mathcal{D}_{j}^{-}$ locations for integer values (decimal numbers).

In order to calculate the memory requirements for binary numbers we need to
calculate the required bits for each one of the $7+4\mathcal{D}_{j}^{-}$
integer values each node $v_{j}$ stores during the operation of the algorithm.
Specifically, we have that node $v_{j}$ requires (i) $2$ bits for the binary
transmission variables $S\\_br_{j}$, $M\\_tr_{j}$, (ii)
$\lceil\log_{2}n\rceil$ and $\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil$
bits for the mass variables $z_{j}[k]$, $y_{j}[k]$ respectively, (iii)
$\lceil\log_{2}n\rceil$, $\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil$ and
$\lceil\log_{2}n\rceil+\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil$ bits for
the state variables $z^{s}_{j}[k]$, $y^{s}_{j}[k]$, $q^{s}_{j}[k]$
respectively, and (iv) $2(\lceil\log_{2}n\rceil)\mathcal{D}_{j}^{-}$ and
$2(\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil)\mathcal{D}_{j}^{-}$ bits for
the mass and state variables $y_{i}[k]$, $z_{i}[k]$, $y^{s}_{i}[k]$,
$z^{s}_{i}[k]$ for each $v_{i}\in\mathcal{N}_{j}^{-}$. Combining these $4$
cases, we have that the memory requirements of each node $v_{j}$ is
$2+(3+2\mathcal{D}_{j}^{-})\lceil\log_{2}n\rceil+(3+2\mathcal{D}_{j}^{-})\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil$
bits for binary numbers. $\square$

It is important to note here that during the operation of Algorithm 1 the
memory requirements of each node $v_{j}$ are greater than most algorithms in
the current literature (e.g., [8, 7] and references therein). In most
algorithms each node needs to store at most $2+2\mathcal{D}_{j}^{-}$ integer
values (i.e., at most $2$ integer values for the node’s state and at most $2$
integer values for the state of each in-neighbor). However, in Algorithm 1
each node $v_{j}$ needs to store $7+4\mathcal{D}_{j}^{-}$ integer values in
order to establish finite time convergence and transmission stopping.
Specifically, each node $v_{j}$ needs to store (i) $2+2\mathcal{D}_{j}^{-}$
integer values for mass variables, in order to establish finite time
convergence, and (ii) $3+2\mathcal{D}_{j}^{-}$ integer values for state
variables along with $2$ integer values for transmission variables, in order
to establish transmission stopping. This increase in the required memory of
each node leads to preservation of the number of transmissions and the
utilized bandwidth (since each node ceases transmissions once it achieves
convergence to the quantized average). Considering that the energy cost for
performing transmissions is much higher than the energy cost for performing
computations [5], this aspect of Algorithm 1 is of particular importance since
it leads to energy savings during the operation of each node. As a result,
this characteristic makes Algorithm 1 suitable for battery powered networks
(as will be seen in the following section).

###  6.2 Required Energy

We now discuss the energy requirements of each node $v_{j}$ during the
operation of Algorithm 1. Energy is consumed mainly during (i) communication,
(ii) processing, and (iii) sensing. Therefore, before analyzing the operation
of each node, we introduce the energy model from [5] which we will use to
calculate the required energy per operation.

  * 3\. Sensing:

For each node $v_{j}$, the energy required to sense a bit is constant and
equal to $\alpha_{3}$. The sensing power is

$p_{\text{sense}}=\alpha_{3}r,$ (8)

for a sensing rate of $r$ bits/sec. A typical value of $\alpha_{3}$ is $50$
nJ/bit.

  * 2\. Processing:

For each node $v_{j}$, the energy required for aggregating $n_{\text{agg}}$
data streams into one stream is

$p_{\text{comp}}=\alpha_{4}n_{\text{agg}}r,$ (9)

where $r$ is the rate (bits/sec) and $\alpha_{4}$ is a constant (typically $5$
nJ/bit).

  * 1\. Communication:

For each node $v_{j}$, the energy required for transmitting to node $v_{l}$ is

$p_{\text{trans}}=(\alpha_{11}+\alpha_{2}d(v_{j},v_{l})^{n})r,$ (10)

where $r$ is the rate (bits/sec), $d(v_{j},v_{l})$ is the distance between
nodes $v_{j}$, $v_{l}$, $n$ is the path loss index, and $\alpha_{11}$,
$\alpha_{2}$ are constants (typically $45$ nJ/bit and $135$ nJ/bit,
respectively).

For convenience we assume that during the operation of our algorithm, the
above operations occur for $1$ second. We next analyze the required energy for
each of the above operations separately. Then, the energy requirements of each
node $v_{j}$ during the operation of Algorithm 1 is the sum of these three
results.

######  Lemma 6.4.

During Algorithm 1, each node $v_{j}$ requires

$\displaystyle p^{j}_{\text{sense}}=$
$\displaystyle\alpha_{3}(m+1+\mathcal{D}_{max}^{-})(n-1)(\lceil\log_{2}n\rceil+\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil)$
(11)

nJ of energy for its sensing operation (i.e., for receiving values from its
in-neighbors), where $n$ is the number of nodes, $m$ is the number of edges in
the network,
$\mathcal{D}_{max}^{-}=\max_{v_{j}\in\mathcal{V}}\mathcal{D}_{j}^{-}$, and
$\alpha_{3}$ is decided by the specifications of the receiver node $v_{j}$
(typical value of $\alpha_{3}$ is $50$ nJ/bit).

In order to calculate the required energy for each node $v_{j}$, we consider
the analysis of Theorem 3 and Proposition 1. Specifically, we combine (i) the
number of times each node $v_{j}$ received a set of mass and state variables
(see Theorem 3), (ii) the number of bits the received sets of mass and state
variables consist of (see Proposition 1), and (iii) the required energy for
each node $v_{j}$ to sense a bit (shown in (8)).

From Theorem 3, we have that each node $v_{j}$ will receive a set of state
variables $z^{s}_{i}[k]$, $y^{s}_{i}[k]$ from its in-neighbors for at most
$(n-1)\mathcal{D}_{max}^{-}$ times. Furthermore, each node $v_{j}$ will
receive a set of mass variables $z_{i}[k]$, $y_{i}[k]$ from its in-neighbors
for at most $(n-1)(m+1)$ times. From Proposition 1, we have that each set of
mass or state variables consists of at most
$\lceil\log_{2}n\rceil+\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil$ bits.
This means that for each node $v_{j}$, during the operation of Algorithm 1,
the upper bound regarding the number of received bits is equal to
$[(n-1)\mathcal{D}_{max}^{-}+(n-1)(m+1)](\lceil\log_{2}n\rceil+\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil)$.
Combining the upper bound regarding the number of received bits with the
required energy to sense a bit in (8), we have that each node $v_{j}$ requires
$p^{j}_{\text{sense}}$ energy as in (11) for its sensing operation. $\square$

######  Lemma 6.5.

During Algorithm 1, each node $v_{j}$ requires

$\displaystyle p^{j}_{\text{comp}}=$
$\displaystyle\alpha_{4}[1+2(\mathcal{D}_{max}^{-})^{2}](n-1)(\lceil\log_{2}n\rceil+\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil)$
(12)

nJ of energy for its processing operation (i.e., for aggregating multiple
streams into one stream), where where $n$ is the number of nodes, $m$ is the
number of edges in the network,
$\mathcal{D}_{max}^{-}=\max_{v_{j}\in\mathcal{V}}\mathcal{D}_{j}^{-}$, and
$\alpha_{4}$ is decided by the specifications of the processing node $v_{j}$
(typical value of $\alpha_{4}$ is $5$ nJ/bit).

In order to calculate the required energy for each node $v_{j}$, we consider
the analysis of Theorem 3 and Proposition 1 where we combine (i) the number of
times each node $v_{j}$ received a set of mass and state variables, (ii) the
number of bits the received sets of mass and state variables consist of, and
(iii) the required energy for each node $v_{j}$ to aggregate multiple data
streams into one stream (shown in (9)).

From Theorem 3, we have that each node $v_{j}$ will receive a set of state
variables $z^{s}_{i}[k]$, $y^{s}_{i}[k]$ from its in-neighbors for at most
$(n-1)\mathcal{D}_{max}^{-}$ times. This means that node $v_{j}$ will have to
aggregate $2\mathcal{D}_{max}^{-}$ streams into two streams for at most
$(n-1)\mathcal{D}_{max}^{-}$ times. Specifically, $v_{j}$ will have to
aggregate $\mathcal{D}_{max}^{-}$ streams of $z^{s}_{i}[k]$,
$v_{i}\in\mathcal{N}_{j}^{-}$, values into one stream $z^{s}_{j}[k+1]$ and
$\mathcal{D}_{max}^{-}$ streams of $y^{s}_{i}[k]$,
$v_{i}\in\mathcal{N}_{j}^{-}$, values into one stream $y^{s}_{j}[k+1]$. As a
result, the required energy for node $v_{j}$ to process the received state
variables is

$p_{1}^{j}=\alpha_{4}2(\mathcal{D}_{max}^{-})^{2}(n-1)(\lceil\log_{2}n\rceil+\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil)\
\text{nJ}.$ (13)

Furthermore, each node $v_{j}$ will receive a set of mass variables
$z_{i}[k]$, $y_{i}[k]$ from its in-neighbors for at most $(n-1)(m+1)$ times.
However, the maximum number of aggregations of received mass variables
$z_{i}[k]$, $y_{i}[k]$ is upper bounded by $n-1$ (i.e., there are at most
$n-1$ aggregations of mass variables during the operation of Algorithm 1).
This means that the required energy for node $v_{j}$ to process the received
mass variables is

$p_{2}^{j}=\alpha_{4}(n-1)(\lceil\log_{2}n\rceil+\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil)\
\text{nJ}.$ (14)

As a result, combining (13) and (14) we have that each node $v_{j}$ requires
$p^{j}_{\text{comp}}$ energy as in (12) for its processing operation.
$\square$

######  Lemma 6.6.

During Algorithm 1, each node $v_{j}$ requires

$\displaystyle p^{j}_{\text{trans}}=$
$\displaystyle(n-1)(\alpha_{11}+\alpha_{2}d(v_{j})^{n})(m+1)A$ (15)

nJ of energy for its transmission operation (i.e., for performing
transmissions towards its out-neighbors), where

$A=\lceil\log_{2}n\rceil+\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil,$

and $n$ is the number of nodes, $m$ is the number of edges in the network,
$d(v_{j})$ is the distance between node $v_{j}$ and every
$v_{l}\in\mathcal{N}_{j}^{+}$, $n$ is the path loss index, and $\alpha_{11}$,
$\alpha_{2}$ are constants (typically $45$ nJ/bit and $135$ nJ/bit,
respectively). [For notational simplicity, we assume that
$d(v_{j})^{n}=d(v_{j},v_{l})^{n}=d(v_{j},v_{l^{\prime}})^{n}$, for every
$v_{l},v_{l^{\prime}}\in\mathcal{N}_{j}^{+}$.]

In order to calculate the required energy for each node $v_{j}$, we combine
(i) the number of times each node $v_{j}$ performs a transmission of a set of
mass and state variables (see Theorem 2), (ii) the number of bits involved in
the transmitted sets of mass and state variables (see Proposition 1), and
(iii) the required energy for each node $v_{j}$ to perform a transmission
towards its out-neighbors (shown in (10)).

From Theorem 2, we have that each node $v_{j}$ will transmit a set of state
variables $z^{s}_{j}[k]$, $y^{s}_{j}[k]$ to its in-neighbors for at most
$(n-1)$ times. Furthermore, each node $v_{j}$ will transmit a set of mass
variables $z_{j}[k]$, $y_{j}[k]$ towards its in-neighbors for at most $(n-1)m$
times. From Proposition 1, we have that each set of mass or state variables
consists of at most
$\lceil\log_{2}n\rceil+\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil$ bits.
This means that for each node $v_{j}$, during the operation of Algorithm 1,
the upper bound regarding the number of transmitted bits is equal to
$[(n-1)(m+1)](\lceil\log_{2}n\rceil+\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil)$.
Combining the upper bound regarding the number of transmitted bits with the
required energy to transmit a bit in (10), we have that each node $v_{j}$
requires $p^{j}_{\text{trans}}$ energy as in (15) for its transmission
operation. $\square$

As a result, if we combine the above results, we obtain the total energy
requirements of each node $v_{j}$ during the operation of Algorithm 1, which
is equal to

$\displaystyle p^{j}_{\text{total}}=$
$\displaystyle(n-1)(\alpha_{3}(m+1+\mathcal{D}_{max}^{-})+\alpha_{4}[1+2(\mathcal{D}_{max}^{-})^{2}])A\
+$ $\displaystyle(n-1)(\alpha_{11}+\alpha_{2}d(v_{j})^{n})(m+1)A\ \text{nJ},$
(16)

where $A=\lceil\log_{2}n\rceil+\lceil\log_{2}\sum_{j=1}^{n}|y_{j}[0]|\rceil,$
$n$ is the number of nodes, $m$ is the number of edges,
$\mathcal{D}_{max}^{-}=\max_{v_{j}\in\mathcal{V}}\mathcal{D}_{j}^{-}$,
$\alpha_{3}$ is decided by the specifications of the receiver node $v_{j}$
(typical value of $\alpha_{3}$ is $50$ nJ/bit), $\alpha_{4}$ is decided by the
specifications of the processing node $v_{j}$ (typical value of $\alpha_{4}$
is $5$ nJ/bit) and and $\alpha_{11}$, $\alpha_{2}$ are constants (typically
$45$ nJ/bit and $135$ nJ/bit, respectively).

######  Remark 6.7.

Note here that in (16), we calculate the total required power of each node for
the worst case scenario. The results in Section 5 and Section 6 can also be
extended for the cases where we want to (i) calculate the minimum required
energy per node during the operation of Algorithm 1, and (ii) tune Algorithm 1
to perform under an energy budget. In the first case, the analysis can
consider the topology of the network, the distribution of the initial states
of the nodes and the unique order each node assigns to its outgoing edges. In
the second case, by utilizing the analysis of the first case, we can show how
we can tune Algorithm 1 to perform under an energy budget. Calculating the
minimum required energy per node and adjusting the algorithm to perform under
an energy budget are interesting directions for future research (but outside
the scope of this paper). $\hfill\blacksquare$

##  7 SIMULATION RESULTS

In this section, we illustrate the behavior of Algorithm 1 and the advantages
of its event triggered operation. Specifically, for $1000$ randomly generated
digraphs of $20$ nodes with identical (randomly chosen) integer initial values
with average equal to $q=214/20=10.7$, we show in Fig. 2 (i) the average value
of each node state variable at each time step, (ii) the average number of
transmissions accumulated until each time step, and (iii) the average number
of nodes performing transmissions at each time step. In Table 2, we show the
minimum, maximum and average values of the (i) total transmissions, and (ii)
total required number of time steps for convergence, during the execution of
Algorithm 1 over these $1000$ randomly generated digraphs of $20$ nodes.

Figure 2: Execution of Algorithm 1 averaged over $1000$ random digraphs of
$20$ nodes. Top figure: Average values of node state variables plotted against
the number of iterations (averaged over $1000$ random digraphs of $20$ nodes).
Middle Figure: Average accumulated number of transmissions plotted against the
number of iterations (averaged over $1000$ random digraphs of $20$ nodes).
Bottom Figure: Average number of nodes performing transmissions plotted
against the number of iterations (averaged over $1000$ random digraphs of $20$
nodes).

In Fig. 2 it is interesting to notice the drop in the average number of nodes
which perform transmissions at each time step (see bottom figure).
Specifically, at time step $k=1$ we have that $57$ transmissions are performed
because during initialization each node $v_{j}$ transmits its state variables
and then, Event Trigger Conditions $1$, $2$ and $3$ hold for some nodes in the
digraph. However, the average number of transmissions at time step $k=10$
drops to $1.485$ and becomes almost equal to $1$ for time steps $k\geq 20$
which means that only one node performs transmissions after approximately $20$
time steps. Furthermore, we can see that for $k\geq 210$ the average number of
transmissions becomes equal to zero (meaning that no node performs
transmissions any more) since Event Trigger Conditions $1$, $2$ and $3$ do not
hold for any node. This means that every node has reached a common value,
equal to $10.7$, which is equal to the average of the initial values (see top
figure). As a result, from Fig. 2 we have that Algorithm 1, allows the nodes
to reach quantized average consensus after an average number of $210$ time
steps and $240.5$ transmissions.

From Table 2, notice that the minimum number of transmissions is $103$ and the
maximum number of transmissions is $368$ with the average being $240.547$.
Furthermore, it is interesting to note that the minimum number of time steps
for convergence is $5$, the maximum is $209$, with the average being
$103.875$. Both results show that in practical scenarios (implemented over
random directed graphs) the total number of transmissions and the total number
of required time steps for convergence are much lower than the worst case
upper bounds calculated in Section 5 and Section 4.2, respectively.

Table 2: Minimum, Maximum, and Average Number of (i) Total Transmissions and (ii) Time Steps for Convergence, of Algorithm 1 over $1000$ random digraphs of $20$ nodes. |  $\\#$ of Transmissions and Time Steps
---|---
| Min. | Max. | Average
$\\#$ of Transmissions | $103$ | $368$ | $240.547$
$\\#$ of Time Steps | $5$ | $209$ | $103.875$

##  8 CONCLUSIONS

In this work, we analyzed the quantized average consensus problem over
wireless networks with nodes that are battery powered or utilize energy
harvesting techniques. Quantized average consensus plays a key role in a
number of applications, which aim at more efficient usage of network
resources. We solved the quantized average consensus problem using a novel
event-triggered distributed algorithm, which calculates the exact average
(i.e., avoids the error introduced due to quantization) after a finite number
of iterations, which we explicitly bounded. Furthermore, we showed that once
the quantized average is calculated, transmissions are ceased from each node
in the network. Then, we presented upper bounds on the number of transmissions
and computations each node performs during the operation of the algorithm and
used them to bound the memory and energy requirements of each node. Finally,
we concluded with simulations which demonstrated the performance and the
advantages of our algorithm. Note here that to the best of our knowledge, this
is the first deterministic algorithm, which allows convergence to the exact
quantized average of the initial values after a finite number of time steps
without any specific requirements regarding the network that describes the
underlying communication topology (see [8]), while it achieves more efficient
usage of available network resources due to its event-triggering operation and
its transmission stopping capabilities.

In the future, we plan to extend Algorithm 1 to cases where (i) it performs
under an energy budget, (ii) we have time-varying communication topologies,
with bounded or unbounded transmission delays, and (iii) nodes aim to preserve
the privacy of their initial states.

## References

  * [1] A. Alam, B. Besselink, V. Turri, J. Martensson, and K. H. Johansson.  Heavy-duty vehicle platooning for sustainable freight transportation: A cooperative method to enhance safety and efficiency.  IEEE Control Systems Magazine, 35(6):34–56, 2015.
  * [2] A. A. Aziz, Y. A. Sekercioglu, P. Fitzpatrick, and M. Ivanovich.  A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks.  IEEE Communications Surveys & Tutorials, 15(1):121–144, 2013.
  * [3] O. Bello and S. Zeadally.  Intelligent device-to-device communication in the Internet of Things.  IEEE Systems Journal, 10(3):1172–1182, 2016.
  * [4] N. Bezzo, K. Mohta, C. Nowzari, I. Lee, V. Kumar, and G. Pappas.  Online planning for energy-efficient and disturbance-aware UAV operations.  Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5027–5033, 2016.
  * [5] M. Bhardwaj and A. P. Chandrakasan.  Bounding the lifetime of sensor networks via optimal role assignments.  Proceedings of $21^{st}$ Annual Joint Conference of the IEEE Computer and Communications Societies, pages 1587–1596, 2002.
  * [6] R. V. Bhat, M. Motani, and T. J. Lim.  Hybrid NOMA for an energy harvesting MAC with non-ideal batteries and circuit power.  IEEE Transactions on Wireless Communications, 18(8):3961–3973, 2019.
  * [7] K. Cai and H. Ishii.  Quantized consensus and averaging on gossip digraphs.  IEEE Transactions on Automatic Control, 56(9):2087–2100, 2011.
  * [8] M. E. Chamie, J. Liu, and T. Basar.  Design and analysis of distributed averaging with quantized communication.  IEEE Transactions on Automatic Control, 61(12):3870–3884, 2016\.
  * [9] T. Charalambous, Y. Yuan, T. Yang, W. Pan, C. N. Hadjicostis, and M. Johansson.  Decentralised minimum-time average consensus in digraphs.  Proceedings of IEEE Conference on Decision and Control, pages 2617–2622, 2013.
  * [10] U. Demir and S. C. Ergen.  ARIMA-based time variation model for beneath the chassis UWB channel.  EURASIP Journal on Wireless Communications and Networking, 178:1–11, 2016.
  * [11] A. D. Domínguez-García and C. N. Hadjicostis.  Coordination and control of distributed energy resources for provision of ancillary services.  Proceedings of IEEE International Conference on Smart Grid Communications, pages 537–542, 2010.
  * [12] P. Du, Q. Yang, Z. Shen, and K. S. Kwak.  Distortion minimization in wireless sensor networks with energy harvesting.  IEEE Communications Letters, 21(6):1393–1396, 2017.
  * [13] M. Franceschelli, A. Giua, and C. Seatzu.  Distributed averaging in sensor networks based on broadcast gossip algorithms.  IEEE Sensors Journal, 11(3):808–817, 2011.
  * [14] K. Gatsis, A. Ribeiro, and G. J. Pappas.  Optimal power management in wireless control systems.  IEEE Transactions on Automatic Control, 59(6):1495–1510, 2014\.
  * [15] C. N. Hadjicostis and T. Charalambous.  Asynchronous coordination of distributed energy resources for the provisioning of ancillary services.  Proceedings of $47^{th}$ Annual Allerton Conference on Communication, Control, and Computing, pages 1500–1507, 2011.
  * [16] C. N. Hadjicostis, A. D. Domínguez-García, and T. Charalambous.  Distributed averaging and balancing in network systems, with applications to coordination and control.  Foundations and Trends® in Systems and Control, 5(3–4), 2018.
  * [17] D. Han, P. Cheng, J. Chen, and L. Shi.  An online sensor power schedule for remote state estimation with communication energy constraint.  IEEE Transactions on Automatic Control, 59(7):1942–1947, 2014\.
  * [18] J. M. Hendrickx and J. N. Tsitsiklis.  Fundamental limitations for anonymous distributed systems with broadcast communications.  Proceedings of $53^{rd}$ Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 9–16, 2015.
  * [19] C. K. Ho and R. Zhang.  Optimal energy allocation for wireless communications with energy harvesting constraints.  IEEE Transactions on Signal Processing, 60(9):4808–4818, 2012\.
  * [20] A. Kashyap, T. Basar, and R. Srikant.  Quantized consensus.  Automatica, 43(7):1192–1203, 2007.
  * [21] S. Knorn, S. Dey, A. Ahlen, and D. E. Quevedo.  Optimal energy allocation in multisensor estimation over wireless channels using energy harvesting and sharing.  IEEE Transactions on Automatic Control, 64(10):4337–4344, 2019\.
  * [22] Y. Li, F. Zhang, D. E. Quevedo, V. Lau, S. Dey, and L. Shi.  Power control of an energy harvesting sensor for remote state estimation.  IEEE Transactions on Automatic Control, 62(1):277–290, 2017.
  * [23] D. Ma, G. Lan, M. Hassan, W. Hu, and S. K. Das.  Sensing, computing, and communications for energy harvesting IoTs: a survey.  IEEE Communications Surveys & Tutorials, 22(2):1222–1250, 2020\.
  * [24] N. E. Manitara and C. N. Hadjicostis.  Distributed stopping for average consensus in undirected graphs via event-triggered strategies.  Automatica, 70:121–127, 2016.
  * [25] N. E. Manitara and C. N. Hadjicostis.  Distributed stopping for average consensus in digraphs.  IEEE Transactions on Control of Network Systems, 5(3):957–967, 2018\.
  * [26] Z. Mao, C. E. Koksal, and N. B. Shroff.  Near optimal power and rate control of multi-hop sensor networks with energy replenishment: Basic limitations with finite energy and data storage.  IEEE Transactions on Automatic Control, 57(4):815–829, 2012.
  * [27] A. Nayyar, T. Basar, D. Teneketzis, and V. V. Veeravalli.  Optimal strategies for communication and remote estimation with an energy harvesting sensor.  IEEE Transactions on Automatic Control, 58(9):2246–2260, 2013\.
  * [28] A. Nedic, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis.  On distributed averaging algorithms and quantization effects.  IEEE Transactions on Automatic Control, 54(11):2506–2517, 2009\.
  * [29] S. K. Nobar, F. Mansourkiaie, and M. H. Ahmed.  Packet dropping minimization in energy harvesting-based wireless sensor network with linear topology.  IEEE Access, 8:38682–38691, 2020.
  * [30] C. Nowzari and J. Cortés.  Distributed event-triggered coordination for average consensus on weight-balanced digraphs.  Automatica, 68:237–244, 2016.
  * [31] P. Park, S. C. Ergen, C. Fischione, C. Lu, and K. H. Johansson.  Wireless network design for control systems: A survey.  IEEE Communications Surveys & Tutorials, 20(2):978–1013, 2018\.
  * [32] P. Park, C. Fischione, A. Bonivento, K. H. Johansson, and A. L. Sangiovanni-Vincentelli.  Breath: An adaptive protocol for industrial control applications using wireless sensor networks.  IEEE Transactions on Mobile Computing, 10(6):821–838, 2011.
  * [33] J. Ploennigs, V. Vasyutynskyy, and K. Kabitzsch.  Comparative study of energy-efficient sampling approaches for wireless control networks.  IEEE Transactions on Industrial Informatics, 6(3):416–424, 2010\.
  * [34] D. E. Quevedo, A. Ahlen, and J. Ostergaard.  Energy efficient state estimation with wireless sensors through the use of predictive power control and coding.  IEEE Transactions on Signal Processing, 58(9):4811–4823, 2010\.
  * [35] A. I. Rikos, T. Charalambous, and C. N. Hadjicostis.  Distributed weight balancing over digraphs.  IEEE Transactions on Control of Network Systems, 1(2):190–201, June 2014.
  * [36] A. I. Rikos, A. Grammenos, E. Kalyvianaki, C. N. Hadjicostis, T. Charalambous, and K. H. Johansson.  Optimal CPU scheduling in data centers via a finite-time distributed quantized coordination mechanism.  arXiv preprint arXiv:2104.03126, 2021.
  * [37] A. I. Rikos and C. N. Hadjicostis.  Distributed average consensus under quantized communication via event-triggered mass summation.  Proceedings of the IEEE Conference on Decision and Control, pages 894–899, 2018.
  * [38] A. I. Rikos and C. N. Hadjicostis.  Event-triggered quantized average consensus via ratios of accumulated values.  IEEE Transactions on Automatic Control, 66(3):1293–1300, 2020.
  * [39] A. I. Rikos, C. N. Hadjicostis, and K. H. Johansson.  Fast quantized average consensus over static and dynamic directed graphs.  arXiv preprint arXiv:2103.05172, 2021.
  * [40] R. Seifullaev, S. Knorn, and A. Ahlen.  Event-triggered transmission policies for harvesting powered sensors with time-varying models.  IEEE Transactions on Green Communications and Networking, 2021 (Early Access).
  * [41] G. S. Seyboth, D. V. Dimarogonas, and K. H. Johansson.  Event-based broadcasting for multi-agent average consensus.  Automatica, 49(1):245–252, 2013.
  * [42] V. Sharma, U. Mukherji, V. Joseph, and S. Gupta.  Optimal energy management policies for energy harvesting sensor nodes.  IEEE Transactions on Wireless Communications, 4(9):1326–1336, 2010\.
  * [43] J. Sztipanovits, X. Koutsoukos, G. Karsai, N. Kottenstette, P. Antsaklis, V. Gupta, B. Goodwine, J. Baras, and S. Wang.  Toward a science of cyber-physical system integration.  Proceedings of the IEEE, 100(1):29–44, 2012.
  * [44] K. Tutuncuoglu and A. Yener.  Optimum transmission policies for battery limited energy harvesting nodes.  IEEE Transactions on Wireless Communications, 11(3):1180–1189, 2012.
  * [45] M. M. Vasconcelos, M. Gagrani, A. Nayyar, and U. Mitra.  Optimal scheduling strategy for networked estimation with energy harvesting.  IEEE Transactions on Control of Network Systems, 7(4):1723–1735, 2020.
  * [46] X. Wang and M. D. Lemmon.  Self-triggered feedback control systems with finite-gain $L_{2}$ stability.  IEEE Transactions on Automatic Control, 54(3):452–467, 2009.
  * [47] C. Wu, D. Gunatilaka, A. Saifullah, M. Sha, P. B. Tiwari, C. Lu, and Y. Chen.  Maximizing network lifetime of WirelessHART networks under graph routing.  Proceedings of IEEE First International Conference on Internet-of-Things Design and Implementation (IoTDI), pages 176–186, 2016.