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...
Main Authors: | , , |
---|---|
Format: | Journal article |
Language: | English |
Published: |
IOP Publishing
2021
|
_version_ | 1797070406095470592 |
---|---|
author | Badiu, MA Saad, D Coon, JP |
author_facet | Badiu, MA Saad, D Coon, JP |
author_sort | Badiu, MA |
collection | OXFORD |
description | 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. |
first_indexed | 2024-03-06T22:38:21Z |
format | Journal article |
id | oxford-uuid:5ab1fb50-9cd0-4ebd-a155-1d4e7297bdeb |
institution | University of Oxford |
language | English |
last_indexed | 2024-03-06T22:38:21Z |
publishDate | 2021 |
publisher | IOP Publishing |
record_format | dspace |
spelling | oxford-uuid:5ab1fb50-9cd0-4ebd-a155-1d4e7297bdeb2022-03-26T17:17:26ZSelf-organization scheme for balanced routing in large-scale multi-hop networksJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:5ab1fb50-9cd0-4ebd-a155-1d4e7297bdebEnglishSymplectic ElementsIOP Publishing2021Badiu, MASaad, DCoon, JPWe 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. |
spellingShingle | Badiu, MA Saad, D Coon, JP Self-organization scheme for balanced routing in large-scale multi-hop networks |
title | Self-organization scheme for balanced routing in large-scale multi-hop networks |
title_full | Self-organization scheme for balanced routing in large-scale multi-hop networks |
title_fullStr | Self-organization scheme for balanced routing in large-scale multi-hop networks |
title_full_unstemmed | Self-organization scheme for balanced routing in large-scale multi-hop networks |
title_short | Self-organization scheme for balanced routing in large-scale multi-hop networks |
title_sort | self organization scheme for balanced routing in large scale multi hop networks |
work_keys_str_mv | AT badiuma selforganizationschemeforbalancedroutinginlargescalemultihopnetworks AT saadd selforganizationschemeforbalancedroutinginlargescalemultihopnetworks AT coonjp selforganizationschemeforbalancedroutinginlargescalemultihopnetworks |