Self-organization scheme for balanced routing in large-scale multi-hop networks. (6th January 2021)

• Record Type: Journal Article
• Authors: Badiu, Mihai-Alin; Saad, David; Coon, Justin P
• Is Part Of: Journal of physics. Volume 54:Number 4(2021)
• Publication Date: 2021-01-06
• Subjects: distributed optimization -- routing -- load balancing -- belief propagation -- self-organization; Mathematical physics -- Periodicals; Statistical physics -- Periodicals; Quantum theory -- Periodicals; Matter -- Properties -- Periodicals; 530.105
• DOI: 10.1088/1751-8121/abd34b
• Languages: English
• ISSNs: 1751-8113

Abstract

Abstract: 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.