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

摘要

This work proposes a novel in-network distributedalgorithm for real-time energy optimal routing in ad hocand sensor networks for systems with linear cost functionsand constant communication delays. The routing problem isdescribed as a minimum-cost multicommodity network flowproblem by linear programming and modified by networkreplication to a real-time aware form. Based on the convexprogramming theory we use dual decomposition to derivethe distributed algorithm. Thanks to the exact mathematicalderivation, the algorithm computes the energy optimal real-timerouting. It uses only peer-to-peer communication betweenneighboring nodes and does not need any central node orknowledge about the whole network structure. Each nodeknows only the produced and collected data flow and thecosts of its outgoing communication links. According to ourknowledge, this work is the first, which solves the real-timerouting problem with linear cost functions and constantcommunication delays, using the dual decomposition.