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 runs
6 that runs in polynomial time, the best algorithm available is still linear with n but exponential with k, with unsatisfactory 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 transmission scheme. C. Mapping into the Transmission Scheme Based on the Steiner tree we computed, we proceed to design 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 destinations. 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 approximation 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
> energy is linear to the number of receivers;when the MAC layer model has repeated transmissions and no ACKs,the 2-o 3 receiving energy is sublinear to the number of receivers;for 12 1=2 certain reliable MAC layer multicast schemes with repeated transmissions and ACKs,the receiving energy is superlinear to the number of receivers. 1=3 power level A.Linear Receiving Energy Functions ●original node source vs(d In this case,the receiving energy of a transmission is destination directly proportional to the number of receivers.Hence,we can suppose f(k)=Ak.The optimization combined with Fig.3.Illustration of ConMap on a five-node mobile network with a receiving energy can be easily integrated into the framework delay constraint of three time slots. by setting the weights of all the edges from power levels to original vertices in the intermediate graph as A instead of zero in T(V,El,k)time and achieves an approximation ratio of and keeping the conversion procedures and the pruning process g(k)on graph G(V,E).If we only consider the transmitting unchanged.We can easily verify that this modification does energy,then ConMap returns a transmission scheme of which not influence the complexity and approximation ratio of the the energy cost is less than g(k)times the optimal one in time framework.Hence,straightforwardly we have the following O(T(Dn2,Dn3)). theorem. Proof:First,we focus on the time complexity of ConMap. Theorem 3:For a mobile network with n,k,D be pa- In the first phase,since there are at most (n-1)power rameters defined as above,suppose the directed Steiner tree levels for each node and the intermediate graph contains algorithm embedded in ConMap runs in T(V,El,k)time D layers,it takes a time of O(Dn3)to construct such an and achieves an approximation ratio of g(k)on graph G(V,E). intermediate graph.Note that the intermediate graph has at Then ConMap returns a transmission scheme of which the most Dn2 vertices and Dn3 edges.Hence,the time complexity energy cost is less than g(k)times the optimal one in time of phase 2 is O(T(Dn2,Dn3)).As for phase 3,the pruning O(T(Dn2,Dn3))when the receiving energy is linear to the and the converting process can both be done by traversing number of intended receivers. the tree,which takes O(Dn3)time.Hence,the total running time is O(T(Dn2,Dn3)).Obviously the approximation ratio B.Sublinear and Superlinear Receiving Energy Functions of the whole framework is determined by the second phase. When the receiving energy is not linear with regard to the By Lemma 2 and the fact that the number of terminals in number of receivers,the straightforward modification made in the intermediate graph equals to the number of destinations the case of linearity is not applicable.We therefore present we conclude that the approximation ratio of the proposed a new way to tackle this and merge the consideration of framework well preserves that obtained under the Steiner tree sublinear and superlinear receiving energy into our ConMap algorithm. ■ framework. Now we give a concrete instantiation of our ConMap Construction of intermediate graph:The main idea lies framework.If we embed the approximation algorithm for in that instead of adding a simple edge from each power level directed Steiner tree in [35],then we have a procedure that runs in O((Dn2k)og)time and returns a transmission scheme that of transmitters to their receivers,we create gadgets in the intermediate graph that charges the Steiner trees for the cost is within a 2log-k factor of the optimal one. corresponding to receiving energy. For a power level wp(recall the definition in Section 5.1)of VI.INTEGRATION OF RECEIVING ENERGY original vertex u that covers k receiving nodes v1,v2,...,vk, In this section,we illustrate how to integrate the optimiza- the construction of the gadget is as follows.First,we create tion of receiving energy in our ConMap framework.Adopting k rows of new vertices,with each row containing k vertices. the same assumption in [9],we consider the receiving energy which,in the sequel,will be referred to as "virtual vertices" of a multicast transmission grows sublinearly,linearly or We denote the vertices in row i as vi,vi2,...,vik.Second, superlinearly with respect to the number of intended receivers. we add a zero-weight edge from each virtual vertex to its The reasonability of this assumption is supported by Johnson corresponding receiving node (e.g,from v11,v21,...,Uk1 to et al.[9]through a theoretical abstraction of practical scenarios v1).Then,for the virtual vertices in two adjacent rows,we with different underlying protocols.Accordingly,we also insert edges between them such that the subgraph formed by divide the optimization technique into three regimes where the the nodes in each two adjacent rows is a complete bipartite receiving energy function f is sublinear,linear or superlinear graph.The direction of these edges is from the row with lower respectively.For completeness,we present the results in [9]index to the row with higher index.And we set the weights of regarding the modeling of receiving energy in the following all the edges between row i and row i+1 as f(i+1)-f(i). proposition. Finally,we add edges from vp to all the virtual vertices in Proposition 1:[9]When the MAC layer of the wireless net- the first row and set their weights as f(1).An example of the work has ACKs without repeated transmissions,the receiving gadget is shown in Figure 4
7 power level original node source destination t =1 t = 2 t = 3 1v (s) 1v (s) 1v (s) 2v 2v 2v 3v 3v 3v 4 1 v (d ) 4 1 v (d ) 4 1 v (d ) 5 2 v (d ) 5 2 v (d ) 5 2 v (d ) w12 w11 w21 w22 w23 w31 w32 w51 w52 Fig. 3. Illustration of ConMap on a five-node mobile network with a delay constraint of three time slots. in T (|V |, |E|, k) time and achieves an approximation ratio of g(k) on graph G(V, E). If we only consider the transmitting energy, then ConMap returns a transmission scheme of which the energy cost is less than g(k) times the optimal one in time O(T (Dn2 , Dn3 )). Proof: First, we focus on the time complexity of ConMap. In the first phase, since there are at most (n − 1) power levels for each node and the intermediate graph contains D layers, it takes a time of O(Dn3 ) to construct such an intermediate graph. Note that the intermediate graph has at most Dn2 vertices and Dn3 edges. Hence, the time complexity of phase 2 is O(T (Dn2 , Dn3 )). As for phase 3, the pruning and the converting process can both be done by traversing the tree, which takes O(Dn3 ) time. Hence, the total running time is O(T (Dn2 , Dn3 )). Obviously the approximation ratio of the whole framework is determined by the second phase. By Lemma 2 and the fact that the number of terminals in the intermediate graph equals to the number of destinations we conclude that the approximation ratio of the proposed framework well preserves that obtained under the Steiner tree algorithm. Now we give a concrete instantiation of our ConMap framework. If we embed the approximation algorithm for directed Steiner tree in [35], then we have a procedure that runs in O((Dn2k) log k ) time and returns a transmission scheme that is within a 2 log2 k factor of the optimal one. VI. INTEGRATION OF RECEIVING ENERGY In this section, we illustrate how to integrate the optimization of receiving energy in our ConMap framework. Adopting the same assumption in [9], we consider the receiving energy of a multicast transmission grows sublinearly, linearly or superlinearly with respect to the number of intended receivers. The reasonability of this assumption is supported by Johnson et al. [9] through a theoretical abstraction of practical scenarios with different underlying protocols. Accordingly, we also divide the optimization technique into three regimes where the receiving energy function f is sublinear, linear or superlinear respectively. For completeness, we present the results in [9] regarding the modeling of receiving energy in the following proposition. Proposition 1: [9] When the MAC layer of the wireless network has ACKs without repeated transmissions, the receiving energy is linear to the number of receivers; when the MAC layer model has repeated transmissions and no ACKs, the receiving energy is sublinear to the number of receivers; for certain reliable MAC layer multicast schemes with repeated transmissions and ACKs, the receiving energy is superlinear to the number of receivers. A. Linear Receiving Energy Functions In this case, the receiving energy of a transmission is directly proportional to the number of receivers. Hence, we can suppose f(k) = Ak. The optimization combined with receiving energy can be easily integrated into the framework by setting the weights of all the edges from power levels to original vertices in the intermediate graph as A instead of zero and keeping the conversion procedures and the pruning process unchanged. We can easily verify that this modification does not influence the complexity and approximation ratio of the framework. Hence, straightforwardly we have the following theorem. Theorem 3: For a mobile network with n, k, D be parameters defined as above, suppose the directed Steiner tree algorithm embedded in ConMap runs in T (|V |, |E|, k) time and achieves an approximation ratio of g(k) on graph G(V, E). Then ConMap returns a transmission scheme of which the energy cost is less than g(k) times the optimal one in time O(T (Dn2 , Dn3 )) when the receiving energy is linear to the number of intended receivers. B. Sublinear and Superlinear Receiving Energy Functions When the receiving energy is not linear with regard to the number of receivers, the straightforward modification made in the case of linearity is not applicable. We therefore present a new way to tackle this and merge the consideration of sublinear and superlinear receiving energy into our ConMap framework. Construction of intermediate graph: The main idea lies in that instead of adding a simple edge from each power level of transmitters to their receivers, we create gadgets in the intermediate graph that charges the Steiner trees for the cost corresponding to receiving energy. For a power level wup (recall the definition in Section 5.1) of original vertex u that covers k receiving nodes v1, v2, . . . , vk, the construction of the gadget is as follows. First, we create k rows of new vertices, with each row containing k vertices, which, in the sequel, will be referred to as “virtual vertices”. We denote the vertices in row i as vi1, vi2, . . . , vik. Second, we add a zero-weight edge from each virtual vertex to its corresponding receiving node (e.g, from v11, v21, . . . , vk1 to v1). Then, for the virtual vertices in two adjacent rows, we insert edges between them such that the subgraph formed by the nodes in each two adjacent rows is a complete bipartite graph. The direction of these edges is from the row with lower index to the row with higher index. And we set the weights of all the edges between row i and row i + 1 as f(i + 1) − f(i). Finally, we add edges from vp to all the virtual vertices in the first row and set their weights as f(1). An example of the gadget is shown in Figure 4