Distributed Algorithm for Real-Time Energy Optimal Routing Based on Dual Decomposition of Linear Programming

Jiří TrdliÄ Ka and ZdenÄ›k Hanzálek

International Journal of Distributed Sensor Networks, 2011, vol. 8, issue 1, 346163

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

Date: 2011
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1155/2012/346163 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:intdis:v:8:y:2011:i:1:p:346163

DOI: 10.1155/2012/346163

Access Statistics for this article

More articles in International Journal of Distributed Sensor Networks
Bibliographic data for series maintained by SAGE Publications ().