that runs in polynomial time,the best algorithm available is still linear with n but exponential with k,with unsatisfacto- ry approximation ratio.However,for completeness,we still present the result in the following lemma. 1 Wup3 Lemma 1:There exists an algorithm that provides an l(1- 1)k approximation to Steiner tree problem in directed graph in time O(nk!+n2k+nm)where n is the number of vertices, k is the number of terminals and m is the number of edges. V. Specifically,set I logk,we get an 2log2k approximation in time O((nk)ogk)[35].[37]. Fig.2. Illustration of the pruning procedure in ConMap without Through implementation of the Steiner tree algorithm,we receiving energy.The left part denotes a subgraph of a constructed Steiner tree that is not in canonical form.The right part represents obtain an approximate Steiner tree in our intermediate graph, the corresponding subgraph after the pruning procedure:absorb the which will serve as the basis for the construction of transmis- original vertices that are connected to wup2 into wup3.And the solid sion scheme. lines are the way that we have chosen to transmit and the dashed lines present the way that we have not chosen. C.Mapping into the Transmission Scheme Based on the Steiner tree we computed,we proceed to de- After describing the three main stages of the framework,we sign the corresponding transmission scheme.First,we present summarize ConMap in Algorithm 1. a crucial property of the conversion process. Lemma 2:For an instance M of DeMEM problem.let Algorithm 1 ConMap Steiner Framework for DeMEM M'be the directed Steiner tree instance converted from M Input:An instance of the DeMEM problem M by ConMap framework.Each feasible transmission scheme Output:A transmission scheme n for M in M corresponds to a valid Steiner tree in M',and the 1:Construct the corresponding intermediate graph C of M energy consumption of the scheme equals to the cost of its and form an instance of directed Steiner tree M'. corresponding Steiner tree. 2:Compute a(approximate)minimum Steiner tree Er in C Proof:We describe a procedure that maps a feasible for M' transmission scheme m for M to an edges set E that forms 3:Prune Er into canonical form. a Steiner tree for M'.For each tuple (u,V,t,p)m,we 4:Convert the pruned Er to its corresponding transmission add the edge from u to the power level corresponding to p schemeπforM. in layer Lt together with the edges from the aforementioned power level to the original vertices of vertices in V of Lt into Er.Finally,we add the necessary inter-layer edges into D.Illustration of ConMap the set.The edge set constructed by the above procedure will be a valid Steiner tree for M'.In the sequel,we refer to the Now we illustrate our proposed framework,ConMap,using an example of a five-node mobile network,where multicast Steiner trees that have corresponding transmission schemes as is between one source and two destinations with a delay being in canonical form. ◆ From the proof of Lemma 2,we note that the energy constraint of three time slots.Figure 3 shows the intermediate consumption of any scheme is no less than the cost of the graph of the network.Note that we omit some of the power optimal Steiner tree in the constructed instance.Therefore,a levels due to space limitations.As shown in the figure,v transmission strategy mapped from an o-optimal Steiner tree is corresponds to the source,v4 and vs correspond to the desti- nations.The solid lines denote the Steiner tree the algorithm guaranteed to be an a-optimal transmission scheme.However, computes in the intermediate graph.Here,the transmission the Steiner tree computed in the intermediate graph may exhibit "aberrant phenomena"so that it has no corresponding scheme is{(v1,{2},1,1),(2,{v3,vs},2,w22), feasible transmission scheme.Hence,in the final phase of (v3,[v),3,w32)},which can be interpreted as follows:In the ConMap,before we map our computed Steiner tree back into a first time slot,the source transmits to v2 using power w1;In transmission scheme,we need to prune it into canonical form. the second time slot,v2 transmits to v3 and vs using power The possible aberrant phenomena that can cause a Steiner w22:In the last time slot,v3 transmits to v using power w32. tree Er not to have its corresponding feasible transmission scheme is:there are edges from different power levels to E.Performance Analysis of ConMap multiple original vertices that correspond to the same network We proceed to provide analysis on the performance of node,leading to redundant transmissions.To deal with this the ConMap framework in terms of running time and ap- case we keep the edge with the original vertex in the earliest proximation ratio.Without loss of generality,we assume the time slot and delete other redundant edges.An example of approximation guarantee of embedded algorithms for directed the pruning procedure is illustrated in Figure 2.Then,we add Steiner tree only depends on the number of terminals in the necessary inter-layer edges to reconnect the resulting edge set graph34,[35]. into a Steiner tree.Note that the above two procedures do not Theorem 2:For a mobile network with n nodes,let k be the increase the cost of the resulting Steiner tree.Therefore,the number of destinations and D be the delay constraint.Suppose pruned Steiner tree can only be closer to optimal. the directed Steiner tree algorithm embedded in ConMap runs6 that runs in polynomial time, the best algorithm available is still linear with n but exponential with k, with unsatisfacto￾ry approximation ratio. However, for completeness, we still present the result in the following lemma. Lemma 1: There exists an algorithm that provides an l(l − 1)k 1 l approximation to Steiner tree problem in directed graph in time O(n lk l+n 2k+nm) where n is the number of vertices, k is the number of terminals and m is the number of edges. Specifically, set l = log k, we get an 2 log2 k approximation in time O((nk) log k ) [35], [37]. Through implementation of the Steiner tree algorithm, we obtain an approximate Steiner tree in our intermediate graph, which will serve as the basis for the construction of transmis￾sion scheme. C. Mapping into the Transmission Scheme Based on the Steiner tree we computed, we proceed to de￾sign the corresponding transmission scheme. First, we present a crucial property of the conversion process. Lemma 2: For an instance M of DeMEM problem, let M0 be the directed Steiner tree instance converted from M by ConMap framework. Each feasible transmission scheme in M corresponds to a valid Steiner tree in M0 , and the energy consumption of the scheme equals to the cost of its corresponding Steiner tree. Proof: We describe a procedure that maps a feasible transmission scheme π for M to an edges set ET that forms a Steiner tree for M0 . For each tuple (u, V 0 , t, p) ∈ π, we add the edge from u to the power level corresponding to p in layer Lt together with the edges from the aforementioned power level to the original vertices of vertices in V 0 of Lt into ET . Finally, we add the necessary inter-layer edges into the set. The edge set constructed by the above procedure will be a valid Steiner tree for M0 . In the sequel, we refer to the Steiner trees that have corresponding transmission schemes as being in canonical form. From the proof of Lemma 2, we note that the energy consumption of any scheme is no less than the cost of the optimal Steiner tree in the constructed instance. Therefore, a transmission strategy mapped from an α-optimal Steiner tree is guaranteed to be an α-optimal transmission scheme. However, the Steiner tree computed in the intermediate graph may exhibit “aberrant phenomena” so that it has no corresponding feasible transmission scheme. Hence, in the final phase of ConMap, before we map our computed Steiner tree back into a transmission scheme, we need to prune it into canonical form. The possible aberrant phenomena that can cause a Steiner tree ET not to have its corresponding feasible transmission scheme is: there are edges from different power levels to multiple original vertices that correspond to the same network node, leading to redundant transmissions. To deal with this case we keep the edge with the original vertex in the earliest time slot and delete other redundant edges. An example of the pruning procedure is illustrated in Figure 2. Then, we add necessary inter-layer edges to reconnect the resulting edge set into a Steiner tree. Note that the above two procedures do not increase the cost of the resulting Steiner tree. Therefore, the pruned Steiner tree can only be closer to optimal. u wup1 wup2 wup3 1 v 2 v 3 v u wup1 wup2 wup3 1 v 2 v 3 v Fig. 2. Illustration of the pruning procedure in ConMap without receiving energy. The left part denotes a subgraph of a constructed Steiner tree that is not in canonical form. The right part represents the corresponding subgraph after the pruning procedure: absorb the original vertices that are connected to wup2 into wup3. And the solid lines are the way that we have chosen to transmit and the dashed lines present the way that we have not chosen. After describing the three main stages of the framework, we summarize ConMap in Algorithm 1. Algorithm 1 ConMap Steiner Framework for DeMEM Input: An instance of the DeMEM problem M Output: A transmission scheme π for M 1: Construct the corresponding intermediate graph L of M and form an instance of directed Steiner tree M0 . 2: Compute a (approximate) minimum Steiner tree ET in L for M0 . 3: Prune ET into canonical form. 4: Convert the pruned ET to its corresponding transmission scheme π for M. D. Illustration of ConMap Now we illustrate our proposed framework, ConMap, using an example of a five-node mobile network, where multicast is between one source and two destinations with a delay constraint of three time slots. Figure 3 shows the intermediate graph of the network. Note that we omit some of the power levels due to space limitations. As shown in the figure, v1 corresponds to the source, v4 and v5 correspond to the desti￾nations. The solid lines denote the Steiner tree the algorithm computes in the intermediate graph. Here, the transmission scheme is {(v1, {v2}, 1, w11),(v2, {v3, v5}, 2, w22), (v3, {v4}, 3, w32)}, which can be interpreted as follows: In the first time slot, the source transmits to v2 using power w11; In the second time slot, v2 transmits to v3 and v5 using power w22; In the last time slot, v3 transmits to v4 using power w32. E. Performance Analysis of ConMap We proceed to provide analysis on the performance of the ConMap framework in terms of running time and ap￾proximation ratio. Without loss of generality, we assume the approximation guarantee of embedded algorithms for directed Steiner tree only depends on the number of terminals in the graph [34], [35]. Theorem 2: For a mobile network with n nodes, let k be the number of destinations and D be the delay constraint. Suppose the directed Steiner tree algorithm embedded in ConMap runs