problem and now we show that it is equivalent to the original assumption [17]that there are p adjustable transmitting power acyclic directed Steiner tree instance levels for a generic node v.Note that even for nodes with For a Steiner tree in G. if it contains infinitely adjustable transmitting power,there are at most edges {e1,eh,e}, then obviously the (V-1)power levels that need to be taken into consideration. corresponding transmission scheme with tuples Upon the power level assignment,we can now construct an {（1,{v},h,deh),,(uy,{vg,,5,d(ey)} is intermediate graph at layer t by applying to all nodes the feasible.Conversely,consider a feasible transmission scheme procedures listed as follows,with the resulting layer denoted for the mobile wireless network.Since in each time slot there as Lt: only exists one edge,each tuple in a feasible transmission 1)Create a vertex in Lt for each node in Gt and call these scheme corresponds to some edge in the acyclic graph G.And vertices“original vertices”. from the requirements for the scheme to be feasible,it follows 2)For the pu power levels of node u,add a set of that those edges form a Steiner tree in G.Most importantly, vertices denoted as {w,w2,...,wup to the graph the energy consumption of a feasible transmission scheme Lt.Hereby,without ambiguity,we will also refer to equals to the cost of its corresponding Steiner tree and all these vertices as "power levels"and their labels as their the reduction processes are implementable in polynomial corresponding transmission powers. time.Therefore,the above reduction is an approximation 3)Add a directed edge from u to each of its power levels preserving reduction.Since for a fixed k there is no efficient and set the edge's weight as the transmission power In k approximation for acyclic directed Steiner tree problem consumed by u when transmitting at that power level. unless NPC DTIME(nPolylogn)[34],we obtain the same 4)Add edges from wj to all the vertices that can be approximation hardness for DeMEM problem. covered by u when transmitting at power level j and assign their weights as zero.Formally,a vertex v can V.THE APPROXIMATION FRAMEWORK:CONMAP be covered by u at power level j if and only if Since by Theorem 1,even approximating the DeMEM prob- 3e=(,v)∈Et and wi(e）≤wuj lem better than a logarithmic factor is NP-hard,it is unlikely Upon the construction of D layers that correspond to D time that the DeMEM problem can be solved in polynomial time. slots,we connect them into the intermediate graph.Starting Therefore,we need to design efficient approximation scheme from L1,we establish the relation of adjacent layers by adding to trade complexity for the optimality of the transmission zero-weight edges between the original vertices in them that scheme.In this section,we therefore propose a novel approxi- correspond to the same node in different time slots.These mation framework-ConMap,which effectively achieves such edges resemble the temporal links in the model of [33].with tradeoff by transforming our DeMEM problem into a directed their directions following the chronological order.With all Steiner tree problem. the operations above,we complete the construction of the Given a specific DeMEM problem instance,ConMap first intermediate graph denoted as C,which,in the sequel,will converts the mobile wireless network graph to an intermediate be demonstrated to well capture both node mobility and the graph,then adopts established algorithms to compute an broadcast nature of wireless networks. approximate minimum Steiner tree in the intermediate graph, and finally uses the computed Steiner tree to construct a near optimal transmission scheme for the original DeMEM B.Computation of the Steiner Tree problem.As we will disclose in the sequel,all the conversion We designate in L1 the vertex that corresponds to the processes are efficiently implementable,with a polynomial source node in the network as the root r and in Lp the time complexity and the size of the intermediate graph being original vertices that correspond to k destinations as terminals. polynomial to that of the original network graph.Also,we can Therefore,the DeMEM problem is equivalent to establishing embed different algorithms for directed Steiner tree to obtain a minimum Steiner tree rooted at r spanning all k terminals various performance guarantees. in the intermediate graph C.Recall that in the intermediate Here for clarity and convenience,we first consider DeMEM graph,the weight of edges from original vertices to their power problem without receiving energy and will demonstrate in levels equals to the transmission power.And the weights of Section VI how to integrate the receiving energy into the edges from power levels to the original vertices they cover optimization. are zero.It follows that the weight assignment ensures that the summation of the weights of edges in a Steiner tree characterizes the energy consumption of a wireless multicast A.Conversion into an Intermediate Graph session.In addition,the directed layering structure of the To derive an energy efficient transmission scheme,we firstly intermediate graph captures the nodes'mobility and ensures need to generate an intermediate graph so that the mobility of that the Steiner tree in C will be generated following the nodes and the broadcast nature of wireless environment can chronological order.Hence,the intermediate graph C is an be captured.Note that the intermediate graph is a directed accurate abstraction of mobile wireless network. layered graph,with each layer corresponding to the network Since our task now becomes computing the minimum at a certain time slot. Steiner tree in a directed graph,we can adopt existing efficient Given a mobile wireless network g=[G1,G2,...,GD}, approximate algorithms [35],[36]to fulfill our purpose.With before we construct an intermediate graph,we adopt previous considerable efforts of searching an approximate algorithm5 problem and now we show that it is equivalent to the original acyclic directed Steiner tree instance. For a Steiner tree in G, if it contains edges {ey1 , ey2 , . . . , eyj }, then obviously the corresponding transmission scheme with tuples {(uy1 , {vy1 }, y1, d(ey1 )), . . . ,(uyj , {vyj }, yj , d(eyj ))} is feasible. Conversely, consider a feasible transmission scheme for the mobile wireless network. Since in each time slot there only exists one edge, each tuple in a feasible transmission scheme corresponds to some edge in the acyclic graph G. And from the requirements for the scheme to be feasible, it follows that those edges form a Steiner tree in G. Most importantly, the energy consumption of a feasible transmission scheme equals to the cost of its corresponding Steiner tree and all the reduction processes are implementable in polynomial time. Therefore, the above reduction is an approximation preserving reduction. Since for a fixed k there is no efficient 1 4 ln k approximation for acyclic directed Steiner tree problem unless NP⊆ DTIME(n polylogn) [34], we obtain the same approximation hardness for DeMEM problem. V. THE APPROXIMATION FRAMEWORK: CONMAP Since by Theorem 1, even approximating the DeMEM prob￾lem better than a logarithmic factor is NP-hard, it is unlikely that the DeMEM problem can be solved in polynomial time. Therefore, we need to design efficient approximation scheme to trade complexity for the optimality of the transmission scheme. In this section, we therefore propose a novel approxi￾mation framework – ConMap, which effectively achieves such tradeoff by transforming our DeMEM problem into a directed Steiner tree problem. Given a specific DeMEM problem instance, ConMap first converts the mobile wireless network graph to an intermediate graph, then adopts established algorithms to compute an approximate minimum Steiner tree in the intermediate graph, and finally uses the computed Steiner tree to construct a near optimal transmission scheme for the original DeMEM problem. As we will disclose in the sequel, all the conversion processes are efficiently implementable, with a polynomial time complexity and the size of the intermediate graph being polynomial to that of the original network graph. Also, we can embed different algorithms for directed Steiner tree to obtain various performance guarantees. Here for clarity and convenience, we first consider DeMEM problem without receiving energy and will demonstrate in Section VI how to integrate the receiving energy into the optimization. A. Conversion into an Intermediate Graph To derive an energy efficient transmission scheme, we firstly need to generate an intermediate graph so that the mobility of nodes and the broadcast nature of wireless environment can be captured. Note that the intermediate graph is a directed layered graph, with each layer corresponding to the network at a certain time slot. Given a mobile wireless network G = {G1, G2, . . . , GD}, before we construct an intermediate graph, we adopt previous assumption [17] that there are pv adjustable transmitting power levels for a generic node v. Note that even for nodes with infinitely adjustable transmitting power, there are at most (|V |−1) power levels that need to be taken into consideration. Upon the power level assignment, we can now construct an intermediate graph at layer t by applying to all nodes the procedures listed as follows, with the resulting layer denoted as Lt: 1) Create a vertex in Lt for each node in Gt and call these vertices “original vertices”. 2) For the pu power levels of node u, add a set of vertices denoted as {wu1, wu2, . . . , wupu } to the graph Lt. Hereby, without ambiguity, we will also refer to these vertices as “power levels” and their labels as their corresponding transmission powers. 3) Add a directed edge from u to each of its power levels and set the edge’s weight as the transmission power consumed by u when transmitting at that power level. 4) Add edges from wuj to all the vertices that can be covered by u when transmitting at power level j and assign their weights as zero. Formally, a vertex v can be covered by u at power level j if and only if ∃e = (u, v) ∈ Et and wt(e) ≤ wuj . Upon the construction of D layers that correspond to D time slots, we connect them into the intermediate graph. Starting from L1, we establish the relation of adjacent layers by adding zero-weight edges between the original vertices in them that correspond to the same node in different time slots. These edges resemble the temporal links in the model of [33], with their directions following the chronological order. With all the operations above, we complete the construction of the intermediate graph denoted as L, which, in the sequel, will be demonstrated to well capture both node mobility and the broadcast nature of wireless networks. B. Computation of the Steiner Tree We designate in L1 the vertex that corresponds to the source node in the network as the root r and in LD the original vertices that correspond to k destinations as terminals. Therefore, the DeMEM problem is equivalent to establishing a minimum Steiner tree rooted at r spanning all k terminals in the intermediate graph L. Recall that in the intermediate graph, the weight of edges from original vertices to their power levels equals to the transmission power. And the weights of edges from power levels to the original vertices they cover are zero. It follows that the weight assignment ensures that the summation of the weights of edges in a Steiner tree characterizes the energy consumption of a wireless multicast session. In addition, the directed layering structure of the intermediate graph captures the nodes’ mobility and ensures that the Steiner tree in L will be generated following the chronological order. Hence, the intermediate graph L is an accurate abstraction of mobile wireless network. Since our task now becomes computing the minimum Steiner tree in a directed graph, we can adopt existing efficient approximate algorithms [35], [36] to fulfill our purpose. With considerable efforts of searching an approximate algorithm