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.

PDF file

In: IEEE Trans. Communications

Publisher: Institute of Electrical and Electronics Engineers, Inc.
© 2005 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Details