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

Journal article

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.

Authors: Badiu, MA; Saad, D; Coon, JP

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: IOP Publishing
• Journal: Journal of Physics A: Mathematical and Theoretical
• Volume: 54
• Issue: 4
• Article number: 045001
• Publication date: 2021-01-06
• Acceptance date: 2020-12-14
• DOI: 10.1088/1751-8121/abd34b
• EISSN: 1751-8121
• ISSN: 1751-8113
• Language: English
• Keywords: distributed optimization; self-organization; belief propagation; load balancing; routing; FFR