Network coding with periodic recomputation for minimum energy multicasting in mobile ad-hoc networks
- Creators
- Kim, Sukwon
- Ho, Tracey
- Effros, Michelle
Abstract
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.
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.Attached Files
Published - Kim2008p79932008_46Th_Annual_Allerton_Conference_On_Communication_Control_And_Computing_Vols_1-3.pdf
Files
Name | Size | Download all |
---|---|---|
Kim2008p79932008_46Th_Annual_Allerton_Conference_On_Communication_Control_And_Computing_Vols_1-3.pdf
md5:29902f9d3467e100c2013075976a5537
|
205.4 kB | Preview Download |
Additional details
- Eprint ID
- 19092
- Resolver ID
- CaltechAUTHORS:20100716-091516848
- Defense Advanced Research Projects Agency (DARPA)
- W911NF-07-1-0029
- Caltech Lee Center for Advanced Networking
- Created
-
2010-08-04Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 10479765