Distributed Algorithm for Real-Time Energy Optimal Routing Based on Dual Decomposition of Linear Programming
This work proposes a novel in-network distributed algorithm for real-time energy optimal routing in ad hoc and sensor networks for systems with linear cost functions and constant communication delays. The routing problem is described as a minimum-cost multicommodity network flow problem by linear pr...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2011-09-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | https://doi.org/10.1155/2012/346163 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832547790899642368 |
|---|---|
| author | Jiří Trdlička Zdeněk Hanzálek |
| author_facet | Jiří Trdlička Zdeněk Hanzálek |
| author_sort | Jiří Trdlička |
| collection | DOAJ |
| description | This work proposes a novel in-network distributed algorithm for real-time energy optimal routing in ad hoc and sensor networks for systems with linear cost functions and constant communication delays. The routing problem is described as a minimum-cost multicommodity network flow problem by linear programming and modified by network replication to a real-time aware form. Based on the convex programming theory we use dual decomposition to derive the distributed algorithm. Thanks to the exact mathematical derivation, the algorithm computes the energy optimal real-time routing. It uses only peer-to-peer communication between neighboring nodes and does not need any central node or knowledge about the whole network structure. Each node knows only the produced and collected data flow and the costs of its outgoing communication links. According to our knowledge, this work is the first, which solves the real-time routing problem with linear cost functions and constant communication delays, using the dual decomposition. |
| format | Article |
| id | doaj-art-8dd15b8190a74639a099814e08489350 |
| institution | Kabale University |
| issn | 1550-1477 |
| language | English |
| publishDate | 2011-09-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj-art-8dd15b8190a74639a099814e084893502025-02-03T06:43:16ZengWileyInternational Journal of Distributed Sensor Networks1550-14772011-09-01810.1155/2012/346163Distributed Algorithm for Real-Time Energy Optimal Routing Based on Dual Decomposition of Linear ProgrammingJiří Trdlička0Zdeněk Hanzálek1 Department of Control Engineering, Faculty of Electrical Engineering, Czech Technical University, Technická 2, 16627 Prague, Czech Republic Department of Control Engineering, Faculty of Electrical Engineering, Czech Technical University, Technická 2, 16627 Prague, Czech RepublicThis work proposes a novel in-network distributed algorithm for real-time energy optimal routing in ad hoc and sensor networks for systems with linear cost functions and constant communication delays. The routing problem is described as a minimum-cost multicommodity network flow problem by linear programming and modified by network replication to a real-time aware form. Based on the convex programming theory we use dual decomposition to derive the distributed algorithm. Thanks to the exact mathematical derivation, the algorithm computes the energy optimal real-time routing. It uses only peer-to-peer communication between neighboring nodes and does not need any central node or knowledge about the whole network structure. Each node knows only the produced and collected data flow and the costs of its outgoing communication links. According to our knowledge, this work is the first, which solves the real-time routing problem with linear cost functions and constant communication delays, using the dual decomposition.https://doi.org/10.1155/2012/346163 |
| spellingShingle | Jiří Trdlička Zdeněk Hanzálek Distributed Algorithm for Real-Time Energy Optimal Routing Based on Dual Decomposition of Linear Programming International Journal of Distributed Sensor Networks |
| title | Distributed Algorithm for Real-Time Energy Optimal Routing Based on Dual Decomposition of Linear Programming |
| title_full | Distributed Algorithm for Real-Time Energy Optimal Routing Based on Dual Decomposition of Linear Programming |
| title_fullStr | Distributed Algorithm for Real-Time Energy Optimal Routing Based on Dual Decomposition of Linear Programming |
| title_full_unstemmed | Distributed Algorithm for Real-Time Energy Optimal Routing Based on Dual Decomposition of Linear Programming |
| title_short | Distributed Algorithm for Real-Time Energy Optimal Routing Based on Dual Decomposition of Linear Programming |
| title_sort | distributed algorithm for real time energy optimal routing based on dual decomposition of linear programming |
| url | https://doi.org/10.1155/2012/346163 |
| work_keys_str_mv | AT jiritrdlicka distributedalgorithmforrealtimeenergyoptimalroutingbasedondualdecompositionoflinearprogramming AT zdenekhanzalek distributedalgorithmforrealtimeenergyoptimalroutingbasedondualdecompositionoflinearprogramming |