Algorithm 2 Pruning procedure for subgraph go Input:An subgraph go in the intersection of Er and some power level gadget original node Output:A pruned gadget that is eligible for a Steiner tree in virtual node canonical form 0 f1) 1:G:=the gadget that go lies in. f2-f1 f(3)-f(2 2:[r,Ur2,...,r:=the set of receiving nodes in go. a (b) 3:u,wup :the transmitting node and the transmitting Fig.4.Illustration of the gadgets for receiving energy:(a)the original power level in go. gadget in ConMap without receiving energy for a power level of original 4:Delete all the edges except (u,wup)in go. vertex u and the nodesv1,v2,vs that u can cover transmitting at power p.(b)the corresponding gadget ConMap creates for this power level of 5:Add the edge (Wup,vr11)to go. u when considering the receiving energy. 6:Add the set of edges {(vr1,vr22),...,(Ur1(k-1),Urk)} to g. 7:Add the set of edges {(vr1,vr1),...,(Urk,Ur)to go. We justify the above construction by proving a similar 8:return go argument as Lemma 2 in the following lemma. Lemma 3:For an instance M of DeMEM problem with receiving energy,let M'be the directed Steiner tree instance Performance analysis of ConMap with receiving energy: converted from M by ConMap framework considering the We summarize the performance guarantee of ConMap with receiving energy.Each feasible transmission scheme in M receiving energy in the following theorem. corresponds to a valid Steiner tree in M',and the energy con- Theorem 4:For a mobile network with n nodes,let k be the sumption of the scheme equals to the cost of its corresponding number of destinations and D be the delay constraint.Suppose Steiner tree. the directed Steiner tree algorithm embedded in ConMap runs Proof:Indeed,for a tuple T={ur,[v1,v2,...,Um}, in T(V,E,k)time and achieves an approximation ratio p,t,it can be encoded as a subgraph consisting of an edge of g(k)on graph G(V,E).Then in time O(T(Dn4,Dn5)), from the original vertex corresponding to u to its power level ConMap returns a transmission scheme of which the energy pr in Lt,edges that form a path traversing one of each receiver cost is less than g(k)times the optimal when the receiving node's corresponding virtual nodes once in the gadget on some energy is sublinear to the number of receivers and less than row (e.g.v11,022,...,Umm)and edges from the traversed virtual vertices in the gadget to their corresponding receiver times the optimal when the receiving energy is kf(① superlinear to the number of receivers. nodes (e.g.(v11,U1),(v22,v2),...,(vmm,Um)).It is easy to Proof:Based on Lemma 3.we only need to consider the verify from the weight assignments of the edges that the total change of cost of the tree brought by the pruning process. weight of this subgraph equals to the energy consumption of An important observation of the pruning procedure is that,the the transmission.And also as in the proof of Lemma 2,we add edges in the gadget can only move to upper level.Therefore, necessary edges between different layers,relating a feasible when f is sublinear,we have f(i+2)-f(i+1)<f(i+ transmission scheme to a Steiner tree ◆ 1)-f(i)for all i,and it follows that the pruning procedure After the computation of a Steiner tree Er in the interme- does not increase the cost of the resulting tree.When f is diate graph,however,the existence of the gadgets complicates superlinear,we have f(i+2)-f(i+1)>f(i+1)-f(i) the pruning process for converting the constructed Steiner tree for all i.And as we know f(1)represents the least energy Er into canonical form.In addition to the pruning procedures consumption.The consumption after the pruning procedure is mentioned in the previous section,we also need to consider the f(k).However,before pruning the least energy consumption aberrant phenomena caused by the edges in the gadgets.The is kf(1).Hence,in the worst case the pruning procedure pruning process is demonstrated in Figure 5 using two illus- increases the cotofactor of at mostFor compleity trative cases.Taking Figure 5(b)for example,the constructed issues,an m-receiver gadget contains at most m2 vertices Steiner tree entails two receivers vi and v2 in the transmis- and m3 edges.Hence,all the gadgets in the intermediate sion but the edges that the algorithm chooses in the gadget graph contain at most Dn4 vertices and Dn5 edges.Hence, are（v11,v1),(11,v22),(v22,v2),(11,23),(23,g）instead if we use a Steiner tree algorithm with a time complexity of the path(v11,v22),(v22,v33)and edges(v11,v1),(v22,v2). of T(V,El,k)and an approximation ratio of g(k),our (v33,v3),whereas the latter are the ones that correspond to Conmap framework will yield a g(k)-approximation of the a legitimate transmission scheme.Therefore,we incorporate optimal transmission scheme for sublinear cost functions and searching such aberrant subgraphs in the gadgets and correct aapproximation for superlinear cost functions ina them to the legitimate ones in the pruning process of the time complexity of O(T(Dn4,Dn5,k)). ◆ framework.For the Steiner tree Er that ConMap constructs for the intermediate graph,denote go as a generic subgraph that lies in the intersection of Er and some gadget.We formally C.An Alternative Gadget Construction present the pruning procedure for go in Algorithm 2.We As mentioned in the previous section,ConMap framework process all the subgraphs go in Er as in Algorithm 2 and increases the approximation ratio of the embedding Steiner finally convert E to an feasible transmission scheme tree algorithm by a factor up to when the receiving8 11 v 12 v 13 v 21 v 22 v 23 v 31 v v32 33 v power level original node virtual node (1) (2) (1) (3) (2) 0 f f f f f − − u u 1 v 2 v 3 v p 1 v 2 v 3 v w up w up (a) (b) Fig. 4. Illustration of the gadgets for receiving energy: (a) the original gadget in ConMap without receiving energy for a power level of original vertex u and the nodes v1, v2, v3 that u can cover transmitting at power p. (b) the corresponding gadget ConMap creates for this power level of u when considering the receiving energy. We justify the above construction by proving a similar argument as Lemma 2 in the following lemma. Lemma 3: For an instance M of DeMEM problem with receiving energy, let M0 be the directed Steiner tree instance converted from M by ConMap framework considering the receiving energy. Each feasible transmission scheme in M corresponds to a valid Steiner tree in M0 , and the energy con￾sumption of the scheme equals to the cost of its corresponding Steiner tree. Proof: Indeed, for a tuple τ = {uτ , {v1, v2, . . . , vm}, pτ , tτ }, it can be encoded as a subgraph consisting of an edge from the original vertex corresponding to uτ to its power level pτ in Lt, edges that form a path traversing one of each receiver node’s corresponding virtual nodes once in the gadget on some row (e.g. v11, v22, . . . , vmm) and edges from the traversed virtual vertices in the gadget to their corresponding receiver nodes (e.g. (v11, v1),(v22, v2), . . . ,(vmm, vm)). It is easy to verify from the weight assignments of the edges that the total weight of this subgraph equals to the energy consumption of the transmission. And also as in the proof of Lemma 2, we add necessary edges between different layers, relating a feasible transmission scheme to a Steiner tree. After the computation of a Steiner tree ET in the interme￾diate graph, however, the existence of the gadgets complicates the pruning process for converting the constructed Steiner tree ET into canonical form. In addition to the pruning procedures mentioned in the previous section, we also need to consider the aberrant phenomena caused by the edges in the gadgets. The pruning process is demonstrated in Figure 5 using two illus￾trative cases. Taking Figure 5(b) for example, the constructed Steiner tree entails two receivers v1 and v2 in the transmis￾sion but the edges that the algorithm chooses in the gadget are (v11, v1),(v11, v22),(v22, v2),(v11, v23),(v23, v3) instead of the path (v11, v22),(v22, v33) and edges (v11, v1), (v22, v2), (v33, v3), whereas the latter are the ones that correspond to a legitimate transmission scheme. Therefore, we incorporate searching such aberrant subgraphs in the gadgets and correct them to the legitimate ones in the pruning process of the framework. For the Steiner tree ET that ConMap constructs for the intermediate graph, denote g0 as a generic subgraph that lies in the intersection of ET and some gadget. We formally present the pruning procedure for g0 in Algorithm 2. We process all the subgraphs g0 in ET as in Algorithm 2 and finally convert ET to an feasible transmission scheme. Algorithm 2 Pruning procedure for subgraph g0 Input: An subgraph g0 in the intersection of ET and some gadget Output: A pruned gadget that is eligible for a Steiner tree in canonical form 1: G := the gadget that g0 lies in. 2: {vr1 , vr2 , . . . , vrk } := the set of receiving nodes in g0. 3: u, wup := the transmitting node and the transmitting power level in g0. 4: Delete all the edges except (u, wup) in g0. 5: Add the edge (wup, vr11) to g0. 6: Add the set of edges {(vr11, vr22), . . . ,(vrk−1(k−1), vrkk)} to g. 7: Add the set of edges {(vr11, vr1), . . . ,(vrkk, vrk )} to g0. 8: return g0 Performance analysis of ConMap with receiving energy: We summarize the performance guarantee of ConMap with receiving energy in the following theorem. Theorem 4: 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 in T (|V |, |E|, k) time and achieves an approximation ratio of g(k) on graph G(V, E). Then in time O(T (Dn4 , Dn5 )), ConMap returns a transmission scheme of which the energy cost is less than g(k) times the optimal when the receiving energy is sublinear to the number of receivers and less than g(k)f(k) kf(1) times the optimal when the receiving energy is superlinear to the number of receivers. Proof: Based on Lemma 3, we only need to consider the change of cost of the tree brought by the pruning process. An important observation of the pruning procedure is that, the edges in the gadget can only move to upper level. Therefore, when f is sublinear, we have f(i + 2) − f(i + 1) ≤ f(i + 1) − f(i) for all i, and it follows that the pruning procedure does not increase the cost of the resulting tree. When f is superlinear, we have f(i + 2) − f(i + 1) ≥ f(i + 1) − f(i) for all i. And as we know f(1) represents the least energy consumption. The consumption after the pruning procedure is f(k). However, before pruning the least energy consumption is kf(1). Hence, in the worst case the pruning procedure increases the cost to a factor of at most f(k) kf(1) . For complexity issues, an m-receiver gadget contains at most m2 vertices and m3 edges. Hence, all the gadgets in the intermediate graph contain at most Dn4 vertices and Dn5 edges. Hence, if we use a Steiner tree algorithm with a time complexity of T (|V |, |E|, k) and an approximation ratio of g(k), our Conmap framework will yield a g(k)-approximation of the optimal transmission scheme for sublinear cost functions and a g(k)f(k) kf(1) -approximation for superlinear cost functions in a time complexity of O(T (Dn4 , Dn5 , k)). C. An Alternative Gadget Construction As mentioned in the previous section, ConMap framework increases the approximation ratio of the embedding Steiner tree algorithm by a factor up to f(k) kf(1) when the receiving