A Caltech Library Service

Network coding with periodic recomputation for minimum energy multicasting in mobile ad-hoc networks

Kim, Sukwon and Ho, Tracey and Effros, Michelle (2009) Network coding with periodic recomputation for minimum energy multicasting in mobile ad-hoc networks. In: 46th annual Allerton Conference on Communication, Control, and Computing. IEEE , Piscataway, NJ, pp. 154-161. ISBN 978-1-4244-2925-7 .

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider the problem of minimum-energy multicast using network coding in mobile ad hoc networks (MANETs). The optimal solution can be obtained by solving a linear program every time slot, but it leads to high computational complexity. In this paper, we consider a low-complexity approach, network coding with periodic recomputation, which recomputes an approximate solution at fixed time intervals, and uses this solution during each time interval. As the network topology changes slowly, we derive a theoretical bound on the performance gap between our suboptimal solution and the optimal solution. For complexity analysis, we assume that interior-point method is used to solve a linear program at the first time slot of each interval. Moreover, we can use the suboptimal solution in the preceding interval as a good initial solution of the linear program at each fixed interval. Based on this interior-point method with a warm start strategy, we obtain a bound on complexity. Finally, we consider an example network scenario and minimize the complexity subject to the condition that our solution achieves a given optimality gap.

Item Type:Book Section
Related URLs:
Additional Information:© 2008 IEEE. This work has been supported in part by the Defense Advanced Research Projects Agency (DARPA) under Contract No. W911NF-07-1-0029, and by Caltech’s Lee Center for Advanced Networking.
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)W911NF-07-1-0029
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number10479765
Record Number:CaltechAUTHORS:20100716-091516848
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:19092
Deposited By: Tony Diaz
Deposited On:04 Aug 2010 18:39
Last Modified:22 Jun 2016 23:13

Repository Staff Only: item control page