3 which the demand varies in different scenarios.Real time destinations:Finally.it maps the obtained tree in that inter- applications such as video conferencing and traffic monitoring mediate graph back into a multicast transmission scheme in require the network latency to be fairly small,whereas in the original network.The proposed ConMap flexibly allows us other networks (e.g.satellites network).network delay is not to embed any directed Steiner tree algorithm into it,and turns so critical.Hence,it is reasonable to add to the network out to be efficiently implementable with only a polynomial a delay constraint,meaning that all the packages must be time complexity as well as preserving the approximation ratio delivered within a time length of D.Based on that,all the of the underlying directed Steiner tree algorithms.Our main above cases can be well characterized by simply adjusting the contributions are listed as follows: size of D.Following this,there emerge a flurry of studies that We prove that the approximation ratio of DeMEM quest for the relationship between delay constraint and other problem in mobile wireless networks cannot be better network performances.For instance,Small et al.show that than Ink for any polynomial-time algorithm,which is relaxing delay constraint can bring about energy reduction or an even stronger result than demonstration of its NP- throughput gain [12].Ra et al.propose an online algorithm for hardness. achieving near optimal energy-delay tradeoff in smartphone We propose ConMap,a novel framework that jointly applications [13].However,current literature on energy-delay optimizes the transmitting and receiving energy in the tradeoff is limited to some specific applications,where the multicast session and harnesses the results of existing main goal is to empirically optimize the tradeoff without the directed Steiner tree algorithms to achieve a good ap- corresponding theoretical exploration [13],[14].Under such proximation for DeMEM.Our framework does not rely circumstance.two questions still remain open: on any specific characterization of energy consumption How hard is it to achieve the minimum multicast energy and is thus applicable to a broad range of applications. under delay constraint in mobile wireless networks? We empirically evaluate the performance of ConMap How should we efficiently design such optimal multicast on real datasets,where ConMap exhibits good appli- transmission schemes with minimum energy consumption cability to real network traces and yields near optimal in delay-constrained mobile wireless networks? transmission schemes compared to a brute-force exact algorithm.We also demonstrate the significance of jointly We therefore present a first look into the problem of mul- optimizing transmitting and receiving cost by showing ticast energy consumption optimization in delay-constrained that incorporating receiving energy into ConMap leads wireless mobile networks,with both transmitting and receiv- to transmission schemes of lower energy consumption. ing energy considered.Specifically,we consider a multicast The rest of this paper is organized as follows:Section II is session with k destinations selected in advance from all the n nodes in the network.With time divided into equal slots, contributed to literature review and we introduce our network and energy models in Section III.We prove the approximation we impose a delay constraint D on the multicast session in hardness of DeMEM in Section IV.The approximation frame- the sense that packets from the source must be delivered to all the k destinations within D time slots.We aim to design work,ConMap,is proposed in Sections V and VI.We conduct efficient multicast routing schemes that achieve the minimum simulations to evaluate the performance of our framework in transmitting and receiving energy.Unlike traditional multicast Section VII and give concluding remarks as well as future in wired network,which is essentially a minimum Steiner directions in in Section VIII. tree problem,the issue becomes more complicated when it comes to mobile wireless mulitcast.First,network topology II.RELATED WORK is time-varying due to the mobility of nodes.This makes A.Minimum Energy Multicast-related Problems the task of designing an optimal transmission scheme rather In the literature,the problem of transmitting energy con- challenging since the same tree may correspond to many sumption optimization is referred to as Minimum-Energy different transmission schemes.Second,the "broadcast nature" Multicast (MEM)problem,and has been extensively studied in wireless communication.to a large extent,complicates the in static networks.Since both MEM problem and Minimum- calculation of energy consumption since it cannot be obtained Energy Broadcast (MEB)problem,a special case of MEM, by simply taking the summation of edge weights in a minimum are proven to be NP-hard [15],[16],[17].the community Steiner tree problem. focuses on designing efficient heuristics.Wieselthier et al. We approach the problem of multicast energy optimization study the MEM problem using the same approach as the in delay-constrained wireless mobile networks by formulating MEB problem and propose three greedy heuristics [16],[3]. it as a combinatorial optimization problem called the DeMEM Wan et al.prove that both MEM problem and MEB problem problem.Upon theoretical analysis on the approximation hard- can be approximated within constant ratio [4].[18].Liang ness of the DeMEM problem,we propose a novel energy et al.propose approximation algorithms for MEB problem optimizing framework called ConMap.Particularly,ConMap where the nodes have discrete transmission power levels [17]. realizes multicast transmission in three major steps.First,Existing works also relate to the extensions of MEM and it constructs an intermediate graph resulted from snapshots MEB such as MEM and MEB problem with reception cost of graph states taken under D different slots and auxiliary [19],[9],duty-cycle-aware MEM [6]and delay-constrained gadgets for transmitting and receiving energy;Second,it builds MEM [5].Furthermore,energy efficient multicast/broadcast a Steiner tree in that intermediate graph spanning all the algorithms for specific applications is also an active topic2 which the demand varies in different scenarios. Real time applications such as video conferencing and traffic monitoring require the network latency to be fairly small, whereas in other networks (e.g. satellites network), network delay is not so critical. Hence, it is reasonable to add to the network a delay constraint, meaning that all the packages must be delivered within a time length of D. Based on that, all the above cases can be well characterized by simply adjusting the size of D. Following this, there emerge a flurry of studies that quest for the relationship between delay constraint and other network performances. For instance, Small et al. show that relaxing delay constraint can bring about energy reduction or throughput gain [12]. Ra et al. propose an online algorithm for achieving near optimal energy-delay tradeoff in smartphone applications [13]. However, current literature on energy-delay tradeoff is limited to some specific applications, where the main goal is to empirically optimize the tradeoff without the corresponding theoretical exploration [13], [14]. Under such circumstance, two questions still remain open: • How hard is it to achieve the minimum multicast energy under delay constraint in mobile wireless networks? • How should we efficiently design such optimal multicast transmission schemes with minimum energy consumption in delay-constrained mobile wireless networks? We therefore present a first look into the problem of mul￾ticast energy consumption optimization in delay-constrained wireless mobile networks, with both transmitting and receiv￾ing energy considered. Specifically, we consider a multicast session with k destinations selected in advance from all the n nodes in the network. With time divided into equal slots, we impose a delay constraint D on the multicast session in the sense that packets from the source must be delivered to all the k destinations within D time slots. We aim to design efficient multicast routing schemes that achieve the minimum transmitting and receiving energy. Unlike traditional multicast in wired network, which is essentially a minimum Steiner tree problem, the issue becomes more complicated when it comes to mobile wireless mulitcast. First, network topology is time-varying due to the mobility of nodes. This makes the task of designing an optimal transmission scheme rather challenging since the same tree may correspond to many different transmission schemes. Second, the “broadcast nature” in wireless communication, to a large extent, complicates the calculation of energy consumption since it cannot be obtained by simply taking the summation of edge weights in a minimum Steiner tree problem. We approach the problem of multicast energy optimization in delay-constrained wireless mobile networks by formulating it as a combinatorial optimization problem called the DeMEM problem. Upon theoretical analysis on the approximation hard￾ness of the DeMEM problem, we propose a novel energy optimizing framework called ConMap. Particularly, ConMap realizes multicast transmission in three major steps. First, it constructs an intermediate graph resulted from snapshots of graph states taken under D different slots and auxiliary gadgets for transmitting and receiving energy; Second, it builds a Steiner tree in that intermediate graph spanning all the destinations; Finally, it maps the obtained tree in that inter￾mediate graph back into a multicast transmission scheme in the original network. The proposed ConMap flexibly allows us to embed any directed Steiner tree algorithm into it, and turns out to be efficiently implementable with only a polynomial time complexity as well as preserving the approximation ratio of the underlying directed Steiner tree algorithms. Our main contributions are listed as follows: • We prove that the approximation ratio of DeMEM problem in mobile wireless networks cannot be better than 1 4 ln k for any polynomial-time algorithm, which is an even stronger result than demonstration of its NP￾hardness. • We propose ConMap, a novel framework that jointly optimizes the transmitting and receiving energy in the multicast session and harnesses the results of existing directed Steiner tree algorithms to achieve a good ap￾proximation for DeMEM. Our framework does not rely on any specific characterization of energy consumption and is thus applicable to a broad range of applications. • We empirically evaluate the performance of ConMap on real datasets, where ConMap exhibits good appli￾cability to real network traces and yields near optimal transmission schemes compared to a brute-force exact algorithm. We also demonstrate the significance of jointly optimizing transmitting and receiving cost by showing that incorporating receiving energy into ConMap leads to transmission schemes of lower energy consumption. The rest of this paper is organized as follows: Section II is contributed to literature review and we introduce our network and energy models in Section III. We prove the approximation hardness of DeMEM in Section IV. The approximation frame￾work, ConMap, is proposed in Sections V and VI. We conduct simulations to evaluate the performance of our framework in Section VII and give concluding remarks as well as future directions in in Section VIII. II. RELATED WORK A. Minimum Energy Multicast-related Problems In the literature, the problem of transmitting energy con￾sumption optimization is referred to as Minimum-Energy Multicast (MEM) problem, and has been extensively studied in static networks. Since both MEM problem and Minimum￾Energy Broadcast (MEB) problem, a special case of MEM, are proven to be NP-hard [15], [16], [17], the community focuses on designing efficient heuristics. Wieselthier et al. study the MEM problem using the same approach as the MEB problem and propose three greedy heuristics [16], [3]. Wan et al. prove that both MEM problem and MEB problem can be approximated within constant ratio [4], [18]. Liang et al. propose approximation algorithms for MEB problem where the nodes have discrete transmission power levels [17]. Existing works also relate to the extensions of MEM and MEB such as MEM and MEB problem with reception cost [19], [9], duty-cycle-aware MEM [6] and delay-constrained MEM [5]. Furthermore, energy efficient multicast/broadcast algorithms for specific applications is also an active topic