9 D.Impact of Mobility Prediction In this section,we briefly discuss the impact of the accuracy power level of future mobility prediction on the performance of ConMap original node virtual node from a theoretical perspective.We will characterize this impact fo) empirically in Section VII-E.As assumed previously,the f(2)-f() theoretical guarantees of ConMap are derived on the basis 3)-12) 0 of perfect future mobility prediction.Now suppose that the a (b) mobility prediction we are able to make has an accuracy -transmission scheme before the pruning procedure transmission scheme after the pruning pocedure of 1-o,i.e.,for each edge e =(u,v)in some Gt,it satisfies that (1-a)w we (1+a)we,where we is Fig.5.Illustration of two pruning processes of converting the computed Steiner tree in the intermediate graph into canonical form.(a)and (b) the true value of the weight of e.We subsequently prove are two cases of the conversion. that,based on this inaccurate prediction of future mobility, the degradation of ConMap will be no larger than a factor of which demonstrates the robustness of ConMap against energy function is superlinear.Therefore,we propose a second mobility prediction errors. method of constructing gadgets in ConMap to capture the Let To denote the optimal transmission scheme in the receiving energy that can eliminate this factor for superlinear (1-a)-accurate network and *denote the optimal transmis- receiving energy functions.The method produces polynomial sion scheme in the true network.A straightforward observation number of additional nodes when the maximum number of is that the inaccuracy of the mobility prediction only has neighbors of a node in the network is logarithmic to the total influence on transmitting energy optimization.Denote as number of nodes. the energy consumption function in the true network and E The construction works as follows.Starting from the orig- as the energy consumption function in the inaccurate network. inal intermediate graph constructed in Section V,for each Since we≤吃≤。e,we have E'(r)≤。(* 1 power level,we add a new vertex for each possible combi- By the optimality of in the inaccurate network we also have nation of receiving nodes and refer these vertices as receiving ()E().It follows that ()()Hence, levels.Then,we add edges from each power level to all their if ConMap is guaranteed to find a transmission scheme that is corresponding receiving levels and from the receiving levels less than B times the optimal one in the inaccurate network we to all their corresponding receivers.The first set of edges are possess,then the transmission scheme it finds is also within assigned with weights equal to the receiving energy,ie,f(k) for a receiving level with k receivers.And the second set of of the optimal transmission scheme in the true network, where the energy consumption is calculated with respect to edges are zero-weighted ones. the true network. Now.we justify the validity of the construction.In the gadgets constructed as above,a tuple (u,V',t,p)in a transmis- sion scheme corresponds to a subgraph consisting of an edge from the original vertex associated with u to its power level 0 power level corresponding to p in Lt,an edge from the aforementioned 1Ψ 2 recerving level power level to the receiving level corresponding to V as the ● original node intended receivers and edges from the receiving level to all P,p2,P the vertices associated with nodes in V'at time slot t.For the f(1) pruning procedure,apart from the first one mentioned in the f(2) previous section,we also need to guarantee that the receiving f(3) levels included in the computed Steiner tree is connected to all 0 its receivers.If not,we can replace this receiving level with Fig.6.An alternative construction of receiving gadgets. the receiving level that corresponds to the set of connected receivers only.This,again,will not increase the cost of the VII.EXPERIMENTS resulting Steiner tree,and thereby the approximation ratio can In this section,we empirically evaluate the performance be preserved. of ConMap framework.We discuss our experimental settings In terms of the time complexity of the framework,suppose in Section VII-A and present detailed empirical results in the embedded Steiner tree algorithm runs in T(V,E,k) subsequent sections. time.In this case,the number of additional vertices in a gadget is of the order O(△2)（△is the degree of the original vertex u).Hence,the total time complexity of ConMap that A.Experimental Setup adopts this alternative gadget construction method becomes We validate the effectiveness of our ConMap framework O(T(A2 Dn2,A2Dn3)).Therefore,this method is suitable for based on three real datasets.The basic descriptions of the three implementation only when the maximum degree of a node is data sets are presented as follows. no larger than logarithmic to the total number of nodes in Brightkite Social Network [38]:Brightkite is a location- the network.An example of this alternative construction is based networking service provider where users share illustrated in Figure 6. their locations by checking-in.We consider the users9 11 v 12 v 13 v 21 v 22 v 23 v 31 v 32 v 33 v 11 v 12 v 13 v 21 v 22 v 23 v 31 v 32 v 33 v transmission scheme before the pruning procedure transmission scheme after the pruning procedure u u power level original node virtual node (1) (2) (1) (3) (2) 0 f f f f f − − 1 v 2 v 3 v 1 v 2 v 3 v w up w up p (a) (b) Fig. 5. Illustration of two pruning processes of converting the computed Steiner tree in the intermediate graph into canonical form. (a) and (b) are two cases of the conversion. energy function is superlinear. Therefore, we propose a second method of constructing gadgets in ConMap to capture the receiving energy that can eliminate this factor for superlinear receiving energy functions. The method produces polynomial number of additional nodes when the maximum number of neighbors of a node in the network is logarithmic to the total number of nodes. The construction works as follows. Starting from the orig￾inal intermediate graph constructed in Section V, for each power level, we add a new vertex for each possible combi￾nation of receiving nodes and refer these vertices as receiving levels. Then, we add edges from each power level to all their corresponding receiving levels and from the receiving levels to all their corresponding receivers. The first set of edges are assigned with weights equal to the receiving energy, i.e, f(k) for a receiving level with k receivers. And the second set of edges are zero-weighted ones. Now, we justify the validity of the construction. In the gadgets constructed as above, a tuple (u, V 0 , t, p) in a transmis￾sion scheme corresponds to a subgraph consisting of an edge from the original vertex associated with u to its power level corresponding to p in Lt, an edge from the aforementioned power level to the receiving level corresponding to V 0 as the intended receivers and edges from the receiving level to all the vertices associated with nodes in V 0 at time slot t. For the pruning procedure, apart from the first one mentioned in the previous section, we also need to guarantee that the receiving levels included in the computed Steiner tree is connected to all its receivers. If not, we can replace this receiving level with the receiving level that corresponds to the set of connected receivers only. This, again, will not increase the cost of the resulting Steiner tree, and thereby the approximation ratio can be preserved. In terms of the time complexity of the framework, suppose the embedded Steiner tree algorithm runs in T (|V |, |E|, k) time. In this case, the number of additional vertices in a gadget is of the order O(∆2 ) (∆ is the degree of the original vertex u). Hence, the total time complexity of ConMap that adopts this alternative gadget construction method becomes O(Γ(∆2Dn2 , ∆2Dn3 )). Therefore, this method is suitable for implementation only when the maximum degree of a node is no larger than logarithmic to the total number of nodes in the network. An example of this alternative construction is illustrated in Figure 6. D. Impact of Mobility Prediction In this section, we briefly discuss the impact of the accuracy of future mobility prediction on the performance of ConMap from a theoretical perspective. We will characterize this impact empirically in Section VII-E. As assumed previously, the theoretical guarantees of ConMap are derived on the basis of perfect future mobility prediction. Now suppose that the mobility prediction we are able to make has an accuracy of 1 − α, i.e., for each edge e = (u, v) in some Gt, it satisfies that (1 − α)w ∗ e ≤ we ≤ (1 + α)w ∗ e , where w ∗ e is the true value of the weight of e. We subsequently prove that, based on this inaccurate prediction of future mobility, the degradation of ConMap will be no larger than a factor of 1 1−α , which demonstrates the robustness of ConMap against mobility prediction errors. Let π0 denote the optimal transmission scheme in the (1−α)-accurate network and π ∗ denote the optimal transmis￾sion scheme in the true network. A straightforward observation is that the inaccuracy of the mobility prediction only has influence on transmitting energy optimization. Denote E as the energy consumption function in the true network and E 0 as the energy consumption function in the inaccurate network. Since 1 1+α we ≤ w ∗ e ≤ 1 1−α we, we have E 0 (π ∗ ) ≤ 1 1−α E(π ∗ ). By the optimality of π ∗ in the inaccurate network we also have E 0 (π0) ≤ E0 (π ∗ ). It follows that E 0 (π0) ≤ 1 1−α E(π ∗ ). Hence, if ConMap is guaranteed to find a transmission scheme that is less than β times the optimal one in the inaccurate network we possess, then the transmission scheme it finds is also within β 1−α of the optimal transmission scheme in the true network, where the energy consumption is calculated with respect to the true network. power level original node receiving level (1) (2) (3) 0 f f f 1 v 2 v 3 v u 1 2 3 p , p , p 1 p 2 p 3 p w u1 w u 2 w u3 Fig. 6. An alternative construction of receiving gadgets. VII. EXPERIMENTS In this section, we empirically evaluate the performance of ConMap framework. We discuss our experimental settings in Section VII-A and present detailed empirical results in subsequent sections. A. Experimental Setup We validate the effectiveness of our ConMap framework based on three real datasets. The basic descriptions of the three data sets are presented as follows. • Brightkite Social Network [38]: Brightkite is a location￾based networking service provider where users share their locations by checking-in. We consider the users