Self-organization scheme for balanced routing in large-scale multi-hop networks

Mihai Alin Badiu, David Saad*, Justin P Coon

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


We propose a self-organization scheme for cost-effective and load-balanced routing in multi-hop networks. To avoid overloading nodes that provide favourable routing conditions, we assign each node with a cost function that penalizes high loads. Thus, finding routes to sink nodes is formulated as an optimization problem in which the global objective function strikes a balance between route costs and node loads. We apply belief propagation (its min-sum version) to solve the network optimization problem and obtain a distributed algorithm whereby the nodes collectively discover globally optimal routes by performing low-complexity computations and exchanging messages with their neighbours. We prove that the proposed method converges to the global optimum after a finite number of local exchanges of messages. Finally, we demonstrate numerically our framework's efficacy in balancing the node loads and study the trade-off between load reduction and total cost minimization.
Original languageEnglish
Article number045001
JournalJournal of Physics A: Mathematical and Theoretical
Issue number4
Early online date14 Dec 2020
Publication statusPublished - 29 Jan 2021

Bibliographical note

Funding: This work was supported by the Independent Research Fund Denmark under
Grant ID DFF–5054-00212, the Leverhulme Trust Grant No. RPG-2018-092, EPSRC
programme grant number EP/R035342/1 TRANSNET (D.S.) and EPSRC grant
number EP/N002350/1 (“Spatially Embedded Networks”)


Dive into the research topics of 'Self-organization scheme for balanced routing in large-scale multi-hop networks'. Together they form a unique fingerprint.

Cite this