Distributed Multi-Commodity Network Flow Algorithm for Energy Optimal Routing in Wireless Sensor Networks

被引:0
作者
Trdlicka, Jiri [1 ]
Hanzalek, Zdenek [1 ]
机构
[1] Czech Tech Univ, Fac Elect Engg, Dept Control Engg, Prague 16627 6, Czech Republic
关键词
Routing; In-network distributed algorithms; Multi-commodity network flow; Dual decomposition; CROSS-LAYER OPTIMIZATION; DECOMPOSITION;
D O I
暂无
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
This work proposes a distributed algorithm for energy optimal routing in a wireless sensor network. The routing problem is described as a mathematical problem by the minimum-cost multi-commodity network flow problem. Due to the separability of the problem, we use the duality theorem to derive the distributed algorithm. The algorithm computes the energy optimal routing in the network without any central node or knowledge of the whole network structure. Each node only needs to know the flow which is supposed to send or receive and the costs and capacities of the neighboring links. An evaluation of the presented algorithm on benchmarks for the energy optimal data flow routing in sensor networks with up to 100 nodes is presented.
引用
收藏
页码:579 / 588
页数:10
相关论文
共 18 条
[11]   A survey of algorithms for convex multicommodity flow problems [J].
Ouorou, A ;
Mahey, P ;
Vial, JP .
MANAGEMENT SCIENCE, 2000, 46 (01) :126-147
[12]   Lautum information [J].
Palomar, Daniel P. ;
Verdtu, Sergio .
2006 IEEE INFORMATION THEORY WORKSHOP, 2006, :1-+
[13]   A tutorial on decomposition methods for network utility maximization [J].
Palomar, Daniel P. ;
Chiang, Mung .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2006, 24 (08) :1439-1451
[14]  
Pioro M., 2004, Routing, Flow, and Capacity Design in Communication and Computer Networks
[15]  
Resende M.G.C., 2006, Handbook of optimization in telecommunications
[16]   Optimal flow routing in muti-hop sensor networks with real-time constraints through linear programming [J].
Trdlicka, Jiri ;
Hanzalek, Zdenek ;
Johansson, Mikael .
ETFA 2007: 12TH IEEE INTERNATIONAL CONFERENCE ON EMERGING TECHNOLOGIES AND FACTORY AUTOMATION, VOLS 1-3, 2007, :924-+
[17]   DISTRIBUTED ASYNCHRONOUS OPTIMAL ROUTING IN DATA-NETWORKS [J].
TSITSIKLIS, JN ;
BERTSEKAS, DP .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1986, 31 (04) :325-332
[18]  
X, 2004, DATA NETWORKS, V52, P1136