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

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.

Automated summary

The proposed self-organization scheme for routing in multi-hop networks balances route costs and node loads by penalizing high loads and applying belief propagation. Through numerical demonstration, the framework's efficacy in balancing node loads is shown, and the trade-off between load reduction and total cost minimization is studied.