Minimum-energy multicast in mobile ad hoc networks using network coding

Yunnan Wu, Philip A. Chou, and Sun-Yuan Kung

Abstract

The minimum energy required to transmit one bit of

information through a network characterizes the most economical

way to communicate in a network. In this paper, we show

that, under a layered model of wireless networks, the minimum

energy-per-bit for multicasting in a mobile ad hoc network can

be found by a linear program; the minimum energy-per-bit

can be attained by performing network coding. Compared with

conventional routing solutions, network coding not only allows a

potentially lower energy-per-bit to be achieved, but also enables

the optimal solution to be found in polynomial time, in sharp contrast

with the NP-hardness of constructing the minimum-energy

multicast tree as the optimal routing solution. We further show

that the minimum energy multicast formulation is equivalent to

a cost minimization with linear edge-based pricing, where the

edge prices are the energy-per-bits of the corresponding physical

broadcast links. This paper also investigates minimum energy multicasting

with routing. Due to the linearity of the pricing scheme,

the minimum energy-per-bit for routing is achievable by using a

single distribution tree. A characterization of the admissible rate

region for routing with a single tree is presented. The minimum

energy-per-bit for multicasting with routing is found by an integer

linear program. We show that the relaxation of this integer linear

program, studied earlier in the Steiner tree literature, can now be

interpreted as the optimization for minimum energy multicasting

with network coding. In short, this paper presents a unifying

study of minimum energy multicasting with network coding and

routing.

Details

Publication typeArticle
Published inIEEE Trans. Communications
PublisherInstitute of Electrical and Electronics Engineers, Inc.
> Publications > Minimum-energy multicast in mobile ad hoc networks using network coding