Distributed Mechanism for Detecting Average Consensus with Maximum-Degree Weights in Bipartite Regular Graphs

Martin Kenyeres and Jozef Kenyeres
Additional contact information
Martin Kenyeres: Institute of Informatics, Slovak Academy of Sciences, Dúbravská Cesta 9, 845 07 Bratislava, Slovakia
Jozef Kenyeres: Frequentis AG, Innovationsstraße 1, 1100 Vienna, Austria

Mathematics, 2021, vol. 9, issue 23, 1-31

Abstract: In recent decades, distributed consensus-based algorithms for data aggregation have been gaining in importance in wireless sensor networks since their implementation as a complementary mechanism can ensure sensor-measured values with high reliability and optimized energy consumption in spite of imprecise sensor readings. In the presented article, we address the average consensus algorithm over bipartite regular graphs, where the application of the maximum-degree weights causes the divergence of the algorithm. We provide a spectral analysis of the algorithm, propose a distributed mechanism to detect whether a graph is bipartite regular, and identify how to reconfigure the algorithm so that the convergence of the average consensus algorithm is guaranteed over bipartite regular graphs. More specifically, we identify in the article that only the largest and the smallest eigenvalues of the weight matrix are located on the unit circle; the sum of all the inner states is preserved at each iteration despite the algorithm divergence; and the inner states oscillate between two values close to the arithmetic means determined by the initial inner states from each disjoint subset. The proposed mechanism utilizes the first-order forward and backward finite-difference of the inner states (more specifically, five conditions are proposed) to detect whether a graph is bipartite regular or not. Subsequently, the mixing parameter of the algorithm can be reconfigured the way it is identified in this study whereby the convergence of the algorithm is ensured in bipartite regular graphs. In the experimental part, we tested our mechanism over randomly generated bipartite regular graphs, random graphs, and random geometric graphs with various parameters, thereby identifying its very high detection rate and proving that the algorithm can estimate the arithmetic mean with high precision (like in error-free scenarios) after the suggested reconfiguration.

Keywords: average consensus; bipartite regular graphs; distributed detection; maximum-degree weights; wireless sensor networks (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/23/3020/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/23/3020/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:23:p:3020-:d:687759

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().