Joint Optimization of Multicast Energy in Delay-constrained Mobile Wireless Networks

Joint Optimization of Multicast Energy in Delay-constrained Mobile Wireless Networks Luoyi Ful,Xinzhe Ful,Zesen Zhang2,Zhiying Xu2,Xudong Wul,Xinbing Wang2,and Songwu Lu3 Dept.of Computer Science,Shanghai Jiao Tong University,China. Email:{yiluofu,fxz0114,xudongwu,xwang8 @sjtu.edu.cn. 2Dept.of Electrical Engineering,Shanghai Jiao Tong University,China. Email:{zesenzhang,xuzhiying @sjtu.edu.cn 3Dept.of Computer Science,University of California,Los Angeles,USA.Email:{slu@cs.ucla.edu Abstract-This paper studies the problem of optimizing mul- As the majority of nodes are battery powered,a key problem ticast energy consumption in delay-constrained mobile wireless of energy cost reduction in mobile wireless networks is to find networks,where information from the source needs to be deliv- a route with minimum total energy consumption for a given ered to all the k destinations within an imposed delay constraint Most existing works simply focus on deriving transmission communication session [2.Under such circumstance,multi- schemes with the minimum transmitting energy,overlooking cast turns out to be more efficient due to the increasing demand the energy consumption at the receiver side.Therefore,in this of information sharing in those communication scenarios. paper,we propose ConMap,a novel and general framework for It outperforms unicast by aggregating multiple flows from efficient transmission scheme design that jointly optimizes both the same source so that network resources such as capacity the transmitting and receiving energy.In doing so,we formulate our problem of designing minimum energy transmission scheme, and energy can be saved.However,as a traffic pattern that called DeMEM,as a combinatorial optimization one,and prove generalizes both unicast and broadcast,the issue of minimum- that the approximation ratio of any polynomial time algorithm energy multicast is far more complicated compared to that of for DeMEM cannot be better than Ink.Aiming to provide minimum-energy unicast,which is essentially a shortest path more efficient approximation schemes,the proposed ConMap first converts DeMEM into an equivalent directed Steiner tree problem in static network. problem through creating auxiliary graph gadgets to capture Among existing works that indeed study the minimum- energy consumption,then maps the computed tree back into a energy multicast problem,most of them [3],[4]are limited to transmission scheme.The advantages of ConMap are threefold- static networks,which fail to well characterize many realistic ed:i)Generality-ConMap exhibits strong applicability to a wide scenarios where users are manifested to be moving.Conse- range of energy models;ii)Flexibility-Any algorithm designed for the problem of directed Steiner tree can be embedded quently,the potential energy saving brought with mobility is into our ConMap framework to achieve different performance also overlooked.Another concern lies in that the state of art guarantees and complexities;iii)Efficiency-ConMap preserves mostly focuses on optimizing the energy consumed only at the the approximation ratio of the embedded Steiner tree algorithm, transmitting side [5],[6],but does not take into consideration to which only slight overhead will be incurred.The three features the receiving energy,which,as suggested by empirical studies are then empirically validated,with ConMap also yielding near- 7,8,is as significant as the transmission cost.Further- optimal transmission schemes compared to a brute-force exact algorithm.To our best knowledge,this is the first work that more,due to the possible collisions and retransmissions in jointly considers both the transmitting and receiving energy in multicast/broadcast protocols,the energy consumption is not the design of multicast transmission schemes in mobile wireless synonymous at transmitting and receiving sides.Interpreted in networks. a more detailed way,the energy consumption of the transmit- Index Terms-Mobile Wireless Networks,Energy Optimiza- ting side is usually determined by transmitting power,while tion,Multicast at the receiving side,taking reliable MAC layer multicast as an example [9],the energy consumption may depend on the number of intended recipients as each transmission involves I.INTRODUCTION waiting for feedback from the receivers and resending the With the surge of mobile data traffic,energy consumption in missing packets.Such inherent heterogeneity between trans- communication is rising radically in recent years.As reported mitting and receiving energy can also be found in many other by a survey [1]where Telecom Italia is said to be the second real applications such as wireless multihop networks [10]and largest consumer in Italy,energy consumption of mobile com- full-duplex energy harvesting infrastructures [11].Therefore, munication is already ranking the top.Hence,energy saving it is difficult to directly embed the receiving energy into becomes a crucial issue that receives considerable attention in existing algorithms.These motivate us to propose a general the design and implementation of mobile wireless networks. framework that jointly optimizes both the transmitting and receiving energy in mobile wireless networks. The early version of this paper is to appear in the Proceedings of ACM In addition to the energy,our framework needs to incor- MobiHoc 2017 [40]. porate the latency,another crucial performance metric,of

1 Joint Optimization of Multicast Energy in Delay-constrained Mobile Wireless Networks Luoyi Fu1 , Xinzhe Fu1 , Zesen Zhang2 , Zhiying Xu2 , Xudong Wu1 , Xinbing Wang1,2, and Songwu Lu3 1Dept. of Computer Science, Shanghai Jiao Tong University, China. Email:{yiluofu,fxz0114,xudongwu,xwang8}@sjtu.edu.cn. 2Dept. of Electrical Engineering, Shanghai Jiao Tong University, China. Email:{zesenzhang,xuzhiying}@sjtu.edu.cn 3Dept. of Computer Science, University of California, Los Angeles, USA. Email:{slu}@cs.ucla.edu Abstract—This paper studies the problem of optimizing mul￾ticast energy consumption in delay-constrained mobile wireless networks, where information from the source needs to be deliv￾ered to all the k destinations within an imposed delay constraint. Most existing works simply focus on deriving transmission schemes with the minimum transmitting energy, overlooking the energy consumption at the receiver side. Therefore, in this paper, we propose ConMap, a novel and general framework for efficient transmission scheme design that jointly optimizes both the transmitting and receiving energy. In doing so, we formulate our problem of designing minimum energy transmission scheme, called DeMEM, as a combinatorial optimization one, and prove that the approximation ratio of any polynomial time algorithm for DeMEM cannot be better than 1 4 ln k. Aiming to provide more efficient approximation schemes, the proposed ConMap first converts DeMEM into an equivalent directed Steiner tree problem through creating auxiliary graph gadgets to capture energy consumption, then maps the computed tree back into a transmission scheme. The advantages of ConMap are threefold￾ed: i) Generality– ConMap exhibits strong applicability to a wide range of energy models; ii) Flexibility– Any algorithm designed for the problem of directed Steiner tree can be embedded into our ConMap framework to achieve different performance guarantees and complexities; iii) Efficiency– ConMap preserves the approximation ratio of the embedded Steiner tree algorithm, to which only slight overhead will be incurred. The three features are then empirically validated, with ConMap also yielding near￾optimal transmission schemes compared to a brute-force exact algorithm. To our best knowledge, this is the first work that jointly considers both the transmitting and receiving energy in the design of multicast transmission schemes in mobile wireless networks. Index Terms—Mobile Wireless Networks, Energy Optimiza￾tion, Multicast I. INTRODUCTION With the surge of mobile data traffic, energy consumption in communication is rising radically in recent years. As reported by a survey [1] where Telecom Italia is said to be the second largest consumer in Italy, energy consumption of mobile com￾munication is already ranking the top. Hence, energy saving becomes a crucial issue that receives considerable attention in the design and implementation of mobile wireless networks. The early version of this paper is to appear in the Proceedings of ACM MobiHoc 2017 [40]. As the majority of nodes are battery powered, a key problem of energy cost reduction in mobile wireless networks is to find a route with minimum total energy consumption for a given communication session [2]. Under such circumstance, multi￾cast turns out to be more efficient due to the increasing demand of information sharing in those communication scenarios. It outperforms unicast by aggregating multiple flows from the same source so that network resources such as capacity and energy can be saved. However, as a traffic pattern that generalizes both unicast and broadcast, the issue of minimum￾energy multicast is far more complicated compared to that of minimum-energy unicast, which is essentially a shortest path problem in static network. Among existing works that indeed study the minimum￾energy multicast problem, most of them [3], [4] are limited to static networks, which fail to well characterize many realistic scenarios where users are manifested to be moving. Conse￾quently, the potential energy saving brought with mobility is also overlooked. Another concern lies in that the state of art mostly focuses on optimizing the energy consumed only at the transmitting side [5], [6], but does not take into consideration the receiving energy, which, as suggested by empirical studies [7], [8], is as significant as the transmission cost. Further￾more, due to the possible collisions and retransmissions in multicast/broadcast protocols, the energy consumption is not synonymous at transmitting and receiving sides. Interpreted in a more detailed way, the energy consumption of the transmit￾ting side is usually determined by transmitting power, while at the receiving side, taking reliable MAC layer multicast as an example [9], the energy consumption may depend on the number of intended recipients as each transmission involves waiting for feedback from the receivers and resending the missing packets. Such inherent heterogeneity between trans￾mitting and receiving energy can also be found in many other real applications such as wireless multihop networks [10] and full-duplex energy harvesting infrastructures [11]. Therefore, it is difficult to directly embed the receiving energy into existing algorithms. These motivate us to propose a general framework that jointly optimizes both the transmitting and receiving energy in mobile wireless networks. In addition to the energy, our framework needs to incor￾porate the latency, another crucial performance metric, of

3 which the demand varies in different scenarios.Real time destinations:Finally.it maps the obtained tree in that inter- applications such as video conferencing and traffic monitoring mediate graph back into a multicast transmission scheme in require the network latency to be fairly small,whereas in the original network.The proposed ConMap flexibly allows us other networks (e.g.satellites network).network delay is not to embed any directed Steiner tree algorithm into it,and turns so critical.Hence,it is reasonable to add to the network out to be efficiently implementable with only a polynomial a delay constraint,meaning that all the packages must be time complexity as well as preserving the approximation ratio delivered within a time length of D.Based on that,all the of the underlying directed Steiner tree algorithms.Our main above cases can be well characterized by simply adjusting the contributions are listed as follows: size of D.Following this,there emerge a flurry of studies that We prove that the approximation ratio of DeMEM quest for the relationship between delay constraint and other problem in mobile wireless networks cannot be better network performances.For instance,Small et al.show that than Ink for any polynomial-time algorithm,which is relaxing delay constraint can bring about energy reduction or an even stronger result than demonstration of its NP- throughput gain [12].Ra et al.propose an online algorithm for hardness. achieving near optimal energy-delay tradeoff in smartphone We propose ConMap,a novel framework that jointly applications [13].However,current literature on energy-delay optimizes the transmitting and receiving energy in the tradeoff is limited to some specific applications,where the multicast session and harnesses the results of existing main goal is to empirically optimize the tradeoff without the directed Steiner tree algorithms to achieve a good ap- corresponding theoretical exploration [13],[14].Under such proximation for DeMEM.Our framework does not rely circumstance.two questions still remain open: on any specific characterization of energy consumption How hard is it to achieve the minimum multicast energy and is thus applicable to a broad range of applications. under delay constraint in mobile wireless networks? We empirically evaluate the performance of ConMap How should we efficiently design such optimal multicast on real datasets,where ConMap exhibits good appli- transmission schemes with minimum energy consumption cability to real network traces and yields near optimal in delay-constrained mobile wireless networks? transmission schemes compared to a brute-force exact algorithm.We also demonstrate the significance of jointly We therefore present a first look into the problem of mul- optimizing transmitting and receiving cost by showing ticast energy consumption optimization in delay-constrained that incorporating receiving energy into ConMap leads wireless mobile networks,with both transmitting and receiv- to transmission schemes of lower energy consumption. ing energy considered.Specifically,we consider a multicast The rest of this paper is organized as follows:Section II is session with k destinations selected in advance from all the n nodes in the network.With time divided into equal slots, contributed to literature review and we introduce our network and energy models in Section III.We prove the approximation we impose a delay constraint D on the multicast session in hardness of DeMEM in Section IV.The approximation frame- the sense that packets from the source must be delivered to all the k destinations within D time slots.We aim to design work,ConMap,is proposed in Sections V and VI.We conduct efficient multicast routing schemes that achieve the minimum simulations to evaluate the performance of our framework in transmitting and receiving energy.Unlike traditional multicast Section VII and give concluding remarks as well as future in wired network,which is essentially a minimum Steiner directions in in Section VIII. tree problem,the issue becomes more complicated when it comes to mobile wireless mulitcast.First,network topology II.RELATED WORK is time-varying due to the mobility of nodes.This makes A.Minimum Energy Multicast-related Problems the task of designing an optimal transmission scheme rather In the literature,the problem of transmitting energy con- challenging since the same tree may correspond to many sumption optimization is referred to as Minimum-Energy different transmission schemes.Second,the "broadcast nature" Multicast (MEM)problem,and has been extensively studied in wireless communication.to a large extent,complicates the in static networks.Since both MEM problem and Minimum- calculation of energy consumption since it cannot be obtained Energy Broadcast (MEB)problem,a special case of MEM, by simply taking the summation of edge weights in a minimum are proven to be NP-hard [15],[16],[17].the community Steiner tree problem. focuses on designing efficient heuristics.Wieselthier et al. We approach the problem of multicast energy optimization study the MEM problem using the same approach as the in delay-constrained wireless mobile networks by formulating MEB problem and propose three greedy heuristics [16],[3]. it as a combinatorial optimization problem called the DeMEM Wan et al.prove that both MEM problem and MEB problem problem.Upon theoretical analysis on the approximation hard- can be approximated within constant ratio [4].[18].Liang ness of the DeMEM problem,we propose a novel energy et al.propose approximation algorithms for MEB problem optimizing framework called ConMap.Particularly,ConMap where the nodes have discrete transmission power levels [17]. realizes multicast transmission in three major steps.First,Existing works also relate to the extensions of MEM and it constructs an intermediate graph resulted from snapshots MEB such as MEM and MEB problem with reception cost of graph states taken under D different slots and auxiliary [19],[9],duty-cycle-aware MEM [6]and delay-constrained gadgets for transmitting and receiving energy;Second,it builds MEM [5].Furthermore,energy efficient multicast/broadcast a Steiner tree in that intermediate graph spanning all the algorithms for specific applications is also an active topic

2 which the demand varies in different scenarios. Real time applications such as video conferencing and traffic monitoring require the network latency to be fairly small, whereas in other networks (e.g. satellites network), network delay is not so critical. Hence, it is reasonable to add to the network a delay constraint, meaning that all the packages must be delivered within a time length of D. Based on that, all the above cases can be well characterized by simply adjusting the size of D. Following this, there emerge a flurry of studies that quest for the relationship between delay constraint and other network performances. For instance, Small et al. show that relaxing delay constraint can bring about energy reduction or throughput gain [12]. Ra et al. propose an online algorithm for achieving near optimal energy-delay tradeoff in smartphone applications [13]. However, current literature on energy-delay tradeoff is limited to some specific applications, where the main goal is to empirically optimize the tradeoff without the corresponding theoretical exploration [13], [14]. Under such circumstance, two questions still remain open: • How hard is it to achieve the minimum multicast energy under delay constraint in mobile wireless networks? • How should we efficiently design such optimal multicast transmission schemes with minimum energy consumption in delay-constrained mobile wireless networks? We therefore present a first look into the problem of mul￾ticast energy consumption optimization in delay-constrained wireless mobile networks, with both transmitting and receiv￾ing energy considered. Specifically, we consider a multicast session with k destinations selected in advance from all the n nodes in the network. With time divided into equal slots, we impose a delay constraint D on the multicast session in the sense that packets from the source must be delivered to all the k destinations within D time slots. We aim to design efficient multicast routing schemes that achieve the minimum transmitting and receiving energy. Unlike traditional multicast in wired network, which is essentially a minimum Steiner tree problem, the issue becomes more complicated when it comes to mobile wireless mulitcast. First, network topology is time-varying due to the mobility of nodes. This makes the task of designing an optimal transmission scheme rather challenging since the same tree may correspond to many different transmission schemes. Second, the “broadcast nature” in wireless communication, to a large extent, complicates the calculation of energy consumption since it cannot be obtained by simply taking the summation of edge weights in a minimum Steiner tree problem. We approach the problem of multicast energy optimization in delay-constrained wireless mobile networks by formulating it as a combinatorial optimization problem called the DeMEM problem. Upon theoretical analysis on the approximation hard￾ness of the DeMEM problem, we propose a novel energy optimizing framework called ConMap. Particularly, ConMap realizes multicast transmission in three major steps. First, it constructs an intermediate graph resulted from snapshots of graph states taken under D different slots and auxiliary gadgets for transmitting and receiving energy; Second, it builds a Steiner tree in that intermediate graph spanning all the destinations; Finally, it maps the obtained tree in that inter￾mediate graph back into a multicast transmission scheme in the original network. The proposed ConMap flexibly allows us to embed any directed Steiner tree algorithm into it, and turns out to be efficiently implementable with only a polynomial time complexity as well as preserving the approximation ratio of the underlying directed Steiner tree algorithms. Our main contributions are listed as follows: • We prove that the approximation ratio of DeMEM problem in mobile wireless networks cannot be better than 1 4 ln k for any polynomial-time algorithm, which is an even stronger result than demonstration of its NP￾hardness. • We propose ConMap, a novel framework that jointly optimizes the transmitting and receiving energy in the multicast session and harnesses the results of existing directed Steiner tree algorithms to achieve a good ap￾proximation for DeMEM. Our framework does not rely on any specific characterization of energy consumption and is thus applicable to a broad range of applications. • We empirically evaluate the performance of ConMap on real datasets, where ConMap exhibits good appli￾cability to real network traces and yields near optimal transmission schemes compared to a brute-force exact algorithm. We also demonstrate the significance of jointly optimizing transmitting and receiving cost by showing that incorporating receiving energy into ConMap leads to transmission schemes of lower energy consumption. The rest of this paper is organized as follows: Section II is contributed to literature review and we introduce our network and energy models in Section III. We prove the approximation hardness of DeMEM in Section IV. The approximation frame￾work, ConMap, is proposed in Sections V and VI. We conduct simulations to evaluate the performance of our framework in Section VII and give concluding remarks as well as future directions in in Section VIII. II. RELATED WORK A. Minimum Energy Multicast-related Problems In the literature, the problem of transmitting energy con￾sumption optimization is referred to as Minimum-Energy Multicast (MEM) problem, and has been extensively studied in static networks. Since both MEM problem and Minimum￾Energy Broadcast (MEB) problem, a special case of MEM, are proven to be NP-hard [15], [16], [17], the community focuses on designing efficient heuristics. Wieselthier et al. study the MEM problem using the same approach as the MEB problem and propose three greedy heuristics [16], [3]. Wan et al. prove that both MEM problem and MEB problem can be approximated within constant ratio [4], [18]. Liang et al. propose approximation algorithms for MEB problem where the nodes have discrete transmission power levels [17]. Existing works also relate to the extensions of MEM and MEB such as MEM and MEB problem with reception cost [19], [9], duty-cycle-aware MEM [6] and delay-constrained MEM [5]. Furthermore, energy efficient multicast/broadcast algorithms for specific applications is also an active topic

20.Gong et al.propose an efficient distributed algorithm network node is associated with a queue for packets,and the for multicast tree construction in wireless Sensor Network feasibility condition of the transmitting policies are that the [21].However,as noted earlier,prior literature only focuses long term time average queue backlogs for all nodes must be on the minimization of transmitting energy,relies on the finite.The routing schemes designed in latter kind of works assumption that the receiving energy is directly proportional to [27],[28],[29]make transmitting decisions in a distributed the number of receivers [19]or considers the receiving energy manner only based on nodes'queue backlogs.This gives them in the context of network-wide broadcast [9].In contrast, an advantage as the policies can achieve the properties without the proposed framework in our work jointly minimizes the the knowledge of future packets arrival,future nodes mobility, transmitting and receiving energy,with applicability to more etc [30],[31].However,as the feasibility condition is defined general scenarios using the time average instead of deterministic short term In spite of a flurry of works addressing the issue of MEM in conditions,the algorithms in the latter works cannot be applied static networks,little is known about the energy consumption to derive delay-constrained transmission schemes.Indeed,the in mobile scenarios.As two exceptions.Wu et al.[22]study class of back pressure policies [32]often incur high packet MEM in mobile ad hoc networks using network coding,but delay that increases with the size of the networks.On the other their focus is on energy gain from network coding rather than hand,the algorithm designed in our work yields transmission mobility.Guo et al.[2]propose an efficient Distributed Min- schemes with constant delay (under a certain delay constraint imum Energy Multicast algorithm,but how delay constraint threshold)and is approximately energy optimal. affects the energy consumption is not considered.In many cases where the timely delivery of messages is not of primary III.MODELS AND ASSUMPTIONS concern,relaxing delay constraint can bring gain in many A.Mobile Wireless Network Model aspects such as capacity and energy [12].Considerable efforts have been made to investigate the theoretical delay-capacity We adopt the mobile wireless network model in [33]that can be reproduced as follows:time is divided into discrete relationship in large scale static and mobile wireless networks time slots and the nodes remain static within a time slot.And 231,[24],25],[26] this model permits a reasonable prediction of nodes'future Despite those dedications to multicast energy optimization, movements.The reason behind is that the node mobility and as far as we know,there is no prior work,other than ours,that considers the problem of jointly optimizing transmitting and the evolution of topology are heavily dependent on social and temporal characteristics of the network participants.And there receiving energy of multicast in mobile wireless networks. are lots of examples such as the easy discovery of the topology for a DTN formed by public buses [41].And more details of B.Stochastic Network Control reason can be referred to [33].With reasonable prediction of nodes'future movements,a mobile network can be modeled as Apart from the aforementioned works that mostly rely on graphical modeling of networks and deterministic packet a sequence of static graphs g={G1,G2,...}.with each static arrival that are analogous to ours,there are a different line of graph interpreted as a snapshot of nodes'positions in a time research in the area of stochastic network control that deals slot.Specifically,denoted as G(V,Et,w)Eg,each static with similar issues of network performance optimizations.The graph is a weighted directed graph with V={v1,v2,....vn} pioneering work of Tassiulas and Ephremides [27]studies the corresponding to the n network nodes.E C VxV denotes the throughput optimal (unicast)routing policy of parallel-queue edge set and w:ER+assigns each edge a corresponding networks.The policy they proposed are subsequently referred weight.An edge e=(vi,vj)E Et means that vi can send to as back-pressure routing,and the Lyapunov-drift argument messages to vj in time slot t with minimum transmission they applied set the basis for many works that follow.Neely power wi(e). et al.extend the throughput-optimal back pressure routing B.Multicast Model to time varying wireless networks [28].Neely also proposes We consider a wireless multicast session with a source s e an energy-optimal unicast routing algorithm for time varying V and destination nodes set Tc V in mobile network G. wireless networks [29.Generalizing the unicast transmission We impose an integral delay constraint D on the multicast pattern,Sinha et al.propose throughput optimal routing policy session in the sense that the message must be delivered to all for multicast,broadcast and anycast transmission in wireless nodes in T within D slots.Therefore,for a mulicast session, networks [30],[31].Interested readers can refer to [32]for a we only need to consider the network snapshots within the complete survey and tutorial on this topic. delay constraint.Hence,in the sequel,we truncate the mobile It is meaningful to distinguish our work from the aforemen- network g into D static graphs denoted as [G1,G2,...,GD. tioned research in stochastic network control and analyze their Since we aim to design a minimum energy transmission pros and cons.Although the two kinds of works both focus on scheme for a delay-constrained multicast session in a mo- designing transmission/routing schemes with desirable prop- bile wireless network,we next formally define the notion erties,the feasibility of the schemes are defined in different of transmission scheme.We refer to the process of some fashions.In our work.a transmission scheme is feasible if transmitter transmitting message to the intended receivers as a all the designated destinations can successfully receive the transmission.A transmission scheme specifies the transmitter. packets within the delay constraint (as will be formally defined intended receivers,timing and transmission power of each in Section III).While.in stochastic network control.each transmission

3 [20]. Gong et al. propose an efficient distributed algorithm for multicast tree construction in wireless Sensor Network [21]. However, as noted earlier, prior literature only focuses on the minimization of transmitting energy, relies on the assumption that the receiving energy is directly proportional to the number of receivers [19] or considers the receiving energy in the context of network-wide broadcast [9]. In contrast, the proposed framework in our work jointly minimizes the transmitting and receiving energy, with applicability to more general scenarios. In spite of a flurry of works addressing the issue of MEM in static networks, little is known about the energy consumption in mobile scenarios. As two exceptions, Wu et al. [22] study MEM in mobile ad hoc networks using network coding, but their focus is on energy gain from network coding rather than mobility. Guo et al. [2] propose an efficient Distributed Min￾imum Energy Multicast algorithm, but how delay constraint affects the energy consumption is not considered. In many cases where the timely delivery of messages is not of primary concern, relaxing delay constraint can bring gain in many aspects such as capacity and energy [12]. Considerable efforts have been made to investigate the theoretical delay-capacity relationship in large scale static and mobile wireless networks [23], [24], [25], [26]. Despite those dedications to multicast energy optimization, as far as we know, there is no prior work, other than ours, that considers the problem of jointly optimizing transmitting and receiving energy of multicast in mobile wireless networks. B. Stochastic Network Control Apart from the aforementioned works that mostly rely on graphical modeling of networks and deterministic packet arrival that are analogous to ours, there are a different line of research in the area of stochastic network control that deals with similar issues of network performance optimizations. The pioneering work of Tassiulas and Ephremides [27] studies the throughput optimal (unicast) routing policy of parallel-queue networks. The policy they proposed are subsequently referred to as back-pressure routing, and the Lyapunov-drift argument they applied set the basis for many works that follow. Neely et al. extend the throughput-optimal back pressure routing to time varying wireless networks [28]. Neely also proposes an energy-optimal unicast routing algorithm for time varying wireless networks [29]. Generalizing the unicast transmission pattern, Sinha et al. propose throughput optimal routing policy for multicast, broadcast and anycast transmission in wireless networks [30], [31]. Interested readers can refer to [32] for a complete survey and tutorial on this topic. It is meaningful to distinguish our work from the aforemen￾tioned research in stochastic network control and analyze their pros and cons. Although the two kinds of works both focus on designing transmission/routing schemes with desirable prop￾erties, the feasibility of the schemes are defined in different fashions. In our work, a transmission scheme is feasible if all the designated destinations can successfully receive the packets within the delay constraint (as will be formally defined in Section III). While, in stochastic network control, each network node is associated with a queue for packets, and the feasibility condition of the transmitting policies are that the long term time average queue backlogs for all nodes must be finite. The routing schemes designed in latter kind of works [27], [28], [29] make transmitting decisions in a distributed manner only based on nodes’ queue backlogs. This gives them an advantage as the policies can achieve the properties without the knowledge of future packets arrival, future nodes mobility, etc [30], [31]. However, as the feasibility condition is defined using the time average instead of deterministic short term conditions, the algorithms in the latter works cannot be applied to derive delay-constrained transmission schemes. Indeed, the class of back pressure policies [32] often incur high packet delay that increases with the size of the networks. On the other hand, the algorithm designed in our work yields transmission schemes with constant delay (under a certain delay constraint threshold) and is approximately energy optimal. III. MODELS AND ASSUMPTIONS A. Mobile Wireless Network Model We adopt the mobile wireless network model in [33] that can be reproduced as follows: time is divided into discrete time slots and the nodes remain static within a time slot. And this model permits a reasonable prediction of nodes’ future movements. The reason behind is that the node mobility and the evolution of topology are heavily dependent on social and temporal characteristics of the network participants. And there are lots of examples such as the easy discovery of the topology for a DTN formed by public buses [41]. And more details of reason can be referred to [33]. With reasonable prediction of nodes’ future movements, a mobile network can be modeled as a sequence of static graphs G = {G1, G2, . . .}, with each static graph interpreted as a snapshot of nodes’ positions in a time slot. Specifically, denoted as Gt(V, Et, wt) ∈ G, each static graph is a weighted directed graph with V = {v1, v2, . . . , vn} corresponding to the n network nodes. Et ⊆ V ×V denotes the edge set and wt : Et 7→ R + assigns each edge a corresponding weight. An edge e = (vi , vj ) ∈ Et means that vi can send messages to vj in time slot t with minimum transmission power wt(e). B. Multicast Model We consider a wireless multicast session with a source s ∈ V and destination nodes set T ⊆ V in mobile network G. We impose an integral delay constraint D on the multicast session in the sense that the message must be delivered to all nodes in T within D slots. Therefore, for a mulicast session, we only need to consider the network snapshots within the delay constraint. Hence, in the sequel, we truncate the mobile network G into D static graphs denoted as {G1, G2, . . . , GD}. Since we aim to design a minimum energy transmission scheme for a delay-constrained multicast session in a mo￾bile wireless network, we next formally define the notion of transmission scheme. We refer to the process of some transmitter transmitting message to the intended receivers as a transmission. A transmission scheme specifies the transmitter, intended receivers, timing and transmission power of each transmission

Now we formulate the DeMEM problem as follows. Definition 3:(The DeMEM Problem)Given a mobile wire- less network g=[G1,G2,...,Gp},a source node s,a set T of destination nodes,and a delay constraint D,the goal is to find a feasible transmission scheme with minimum energy consumption. We note that in the definitions above,we make the fol- time 1=2 13 1三4 4 lowing characterizations of communication in mobile wireless ©source 。unreached node intended receiver networks.First,we assume that the transmission rate is much ©destination 。reached node faster than that of the nodes'mobility.In other words,it is Fig.1.A mobile wireless network and a feasible transmission scheme feasible to transmit multiple times to different receivers in a for a multicast session in the network;(a)a mobile wireless network single time slot.This may not be desirable if we only consider (a sequence of snapshots);(b)a feasible transmission scheme for a transmission cost.However,it can bring possible gain when multicast session in the network with v1 being the source,v4,v6 being the destinations and a delay constraint of four time slots. we take the receiving energy into account.Second,we can utilize the wireless broadcast nature during communications, Definition 1:A transmission scheme c V x 2V x i.e.,different nodes can be reached within one transmission {1,...,D}xR+is a sequence of tuples {(u,V',t,p)},where as long as the transmission power is large enough.Third, a tuple T=(ur,Vr,tr,pr)E m denotes that node ur should in the present work,we focus on the multicast of one data transmit to the nodes in V at time slottr with power pr. packet in the network,which alleviates us from the burden Also,in a transmission scheme we define a node to be of interference and packet scheduling issues.We leave the "reached in time slot t"in a recursive way as follows:(i)the minimum energy multicast with a streaming of packets as source s is reached in time slot 1.(ii)if a node is reached in future work. time slot t,then it is reached in time slot t'for all t'>t,and (iii)if a node u is reached in time slot t and (u,V,t,p)), IV.APPROXIMATION HARDNESS then all nodes in V are reached after time slot t,or we say they have been reached in time slot t+1.Now,we give the In this section we analyze the approximation hardness of definition of feasible transmission scheme and will restrict our DeMEM problem.We show that even without receiving energy (i.e.,f 0),the DeMEM problem cannot be approximated consideration to the set of feasible transmission schemes in the sequel.Intuitively,a scheme is said to be feasible if it within a/textcolorredlogarithmic factor in polynomial time by is without redundancy and qualified for the delay constrained reduction from acyclic directed Steiner tree problem multicast session. Theorem 1:The DeMEM problem cannot be approximated Definition 2:A transmission scheme m is feasible if it ob- in polynomial time within a factor better than nk,where k serves the following conditions:(i)For allT=(u,V',t,p) is the number of destination. T,it satisfies that u is reached in t and for all v e V Proof:Consider an instance of acyclic directed Steiner e=(u,v）∈Er and p≥maxe=(u,w)eE,vev{wt(e).() tree problem defined by an acyclic directed graph G(V,E) For allT-(,V',t,p)∈π，no node in V'is reached before and an edge cost function d:ER+,a root r V and t.(iii)All nodes in T are reached in time slot D. a set of vertices SCV with S=k.The goal is to find a minimum cost Steiner tree (arborescence)covering all vertices Figure 1 illustrates an example of a mobile wire- in S.Based on these,we will construct an instance of the less network,along with a feasible transmission scheme proposed under a multicast session in the network. DeMEM problem by encoding the graph information into a The transmission scheme corresponding to the tuples mobile wireless network. {(v1,{2,v4},1,p1),(v2,{vs},2,p2),(v5,{6},4,p3)}- To begin with,we do a topological sort on the graph and get a sequence of nodes following the topological order.Without loss of generality,we only consider the nodes that do not lie C.Energy Model before the root r in the sequence,i.e.,a truncated sequence For a transmission specified by tuple T =(ur,V,tr,p), r=vo,v1,....Then,we sort the relevant edges according to we model the energy consumption of this transmission as the order of their outgoing nodes in the truncated sequence into E(T)=p,f(IV-), [eo,e1,...,e}.From this sequence,we will build a mobile wireless network g where the first part denotes the energy consumed by the First,we set V as the set of nodes that appear in the transmitter side and f is a function of the number of intended truncated sequence.Then,for any generic edge ei=(ui,vi)in receivers that can represent the receiving energy.Note that our the edge sequence,we add (ui,vi)into Gi(V',Ei,wi)and set framework does not restrict to any specific f and the choice of f may depend on practical settings [7],[9],which will be its cost as wi(e)=d(e).The constructed network g consists of static graphs [G1,G2,...,G}where each static graph has specified in Section VI.It follows that the energy consumption only one edge.Further,we designate r as the source,the nodes of a transmission scheme is given by: corresponding to the vertices in S as the destinations.and set (m)=∑(r) the delay constraint D=l,the receiving energy function as TER zero.By above procedures,we have an instance of DeMEM

4 time sp a c e t =1 t = 2 t = 3 t = 4 time sp a c e source destination reached node unreached node intended receiver 1 v 1 v 1 v 1 v 2 v 2 v 2 v 2 v 3 v 3 v 3 v 3 v 4 v 4 v 4 v 4 v 5 v 5 v 5 5 v v 6 v 6 v 6 v 6 v t =1 t = 2 t = 3 t = 4 1 v 1 v 1 v 1 v 2 v 2 v 2 v 2 v 3 v 3 v 3 v 3 v 4 v 4 v 4 v 4 v 5 v 5 v 5 5 v v 6 v 6 v 6 v 6 v Fig. 1. A mobile wireless network and a feasible transmission scheme for a multicast session in the network; (a) a mobile wireless network (a sequence of snapshots); (b) a feasible transmission scheme for a multicast session in the network with v1 being the source, v4, v6 being the destinations and a delay constraint of four time slots. Definition 1: A transmission scheme π ⊆ V × 2 V × {1, . . . , D}×R + is a sequence of tuples {(u, V 0 , t, p)}, where a tuple τ = (uτ , Vτ , tτ , pτ ) ∈ π denotes that node uτ should transmit to the nodes in Vτ at time slot tτ with power pτ . Also, in a transmission scheme π, we define a node to be “reached in time slot t” in a recursive way as follows: (i) the source s is reached in time slot 1, (ii) if a node is reached in time slot t, then it is reached in time slot t 0 for all t 0 ≥ t, and (iii) if a node u is reached in time slot t and (u, V , t, p) ∈ π), then all nodes in V are reached after time slot t, or we say they have been reached in time slot t + 1. Now, we give the definition of feasible transmission scheme and will restrict our consideration to the set of feasible transmission schemes in the sequel. Intuitively, a scheme is said to be feasible if it is without redundancy and qualified for the delay constrained multicast session. Definition 2: A transmission scheme π is feasible if it ob￾serves the following conditions: (i) For all τ = (u, V 0 , t, p) ∈ π, it satisfies that u is reached in t and for all v ∈ V 0 , e = (u, v) ∈ Et and p ≥ maxe=(u,v)∈Et,v∈V 0{wt(e)}. (ii) For all τ = (u, V 0 , t, p) ∈ π, no node in V 0 is reached before t. (iii) All nodes in T are reached in time slot D. Figure 1 illustrates an example of a mobile wire￾less network, along with a feasible transmission scheme proposed under a multicast session in the network. The transmission scheme corresponding to the tuples {(v1, {v2, v4}, 1, p1),(v2, {v5}, 2, p2),(v5, {v6}, 4, p3)}. C. Energy Model For a transmission specified by tuple τ = (uτ , Vτ , tτ , pτ ), we model the energy consumption of this transmission as E(τ ) = pτ + f(|Vτ |), where the first part denotes the energy consumed by the transmitter side and f is a function of the number of intended receivers that can represent the receiving energy. Note that our framework does not restrict to any specific f and the choice of f may depend on practical settings [7], [9], which will be specified in Section VI. It follows that the energy consumption of a transmission scheme π is given by: E(π) = X τ∈π E(τ ). Now we formulate the DeMEM problem as follows. Definition 3: (The DeMEM Problem) Given a mobile wire￾less network G = {G1, G2, . . . , GD}, a source node s, a set T of destination nodes, and a delay constraint D, the goal is to find a feasible transmission scheme with minimum energy consumption. We note that in the definitions above, we make the fol￾lowing characterizations of communication in mobile wireless networks. First, we assume that the transmission rate is much faster than that of the nodes’ mobility. In other words, it is feasible to transmit multiple times to different receivers in a single time slot. This may not be desirable if we only consider transmission cost. However, it can bring possible gain when we take the receiving energy into account. Second, we can utilize the wireless broadcast nature during communications, i.e., different nodes can be reached within one transmission as long as the transmission power is large enough. Third, in the present work, we focus on the multicast of one data packet in the network, which alleviates us from the burden of interference and packet scheduling issues. We leave the minimum energy multicast with a streaming of packets as future work. IV. APPROXIMATION HARDNESS In this section we analyze the approximation hardness of DeMEM problem. We show that even without receiving energy (i.e., f = 0), the DeMEM problem cannot be approximated within a /textcolorredlogarithmic factor in polynomial time by reduction from acyclic directed Steiner tree problem. Theorem 1: The DeMEM problem cannot be approximated in polynomial time within a factor better than 1 4 lnk, where k is the number of destination. Proof: Consider an instance of acyclic directed Steiner tree problem defined by an acyclic directed graph G(V, E) and an edge cost function d : E → R +, a root r ∈ V and a set of vertices S ⊆ V with |S| = k. The goal is to find a minimum cost Steiner tree (arborescence) covering all vertices in S. Based on these, we will construct an instance of the DeMEM problem by encoding the graph information into a mobile wireless network. To begin with, we do a topological sort on the graph and get a sequence of nodes following the topological order. Without loss of generality, we only consider the nodes that do not lie before the root r in the sequence, i.e., a truncated sequence {r = v0, v1, . . .}. Then, we sort the relevant edges according to the order of their outgoing nodes in the truncated sequence into {e0, e1, . . . , el}. From this sequence, we will build a mobile wireless network G. First, we set V 0 as the set of nodes that appear in the truncated sequence. Then, for any generic edge ei = (ui , vi) in the edge sequence, we add (ui , vi) into Gi(V 0 , Ei , wi) and set its cost as wi(e) = d(e). The constructed network G consists of static graphs {G1, G2, . . . , Gl} where each static graph has only one edge. Further, we designate r as the source, the nodes corresponding to the vertices in S as the destinations, and set the delay constraint D = l, the receiving energy function as zero. By above procedures, we have an instance of DeMEM

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 algorithm

5 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

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 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

> 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 optimiza￾tion 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 net￾work 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 pa￾rameters 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

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+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 receiving

8 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

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 users

9 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

10 20 Con.Yap-CHA 2国 CosMap-CHA Loanlap-SI Coalap-SP f-Com山pST 一Coa Map-lST Brute Force 1B0 2 10 Datacet Briabdilt DatB整 Recching Energy:Seblnrar 20 Delay Constraint Delay Constraint Delay Constraint (a) (b) (c) 2 24 十-ConMap-CHA CenMap-CHA ConVap-C 1200 21 2 CoMap-SPT e一ConMap-5T CoaMapSPT 20 CoMp-MSI CeMaD-MsT 2e 令CoaMap-ST 马一Brute force 5树 2 40 5 1 4000 Delay Constraint Delay Constraint Delay Constraint (d) (e) (田 +Can山e-CHA +-Coe山pCHA CenMaD-CH 130 ConM-SPT 150 ConMap-MST -Brute Force 1 10 1销 Delay Constraint Delay Constraint Delay Constraint g (h) () Fig.7.The energy consumption of the transmission schemes yielded by the three/four algorithms under different scenarios with six destinations. The dataset and receiving energy function are labeled in the figures. as network nodes and use their location information at representatives of linear,sublinear and superlinear functions different timestamps to create mobility trace. of receiving energy,respectively.All the results demonstrated Gowalla Social Network [38]:Gowalla is a location- are the average of the ten groups.Note that we are interested based social networking website where users share their in the relative quantity of energy consumption,and thus we locations by checking-in.Similarly,we consider users as do not relate the amount of energy consumption to specific network nodes and use their location information to create physical quantity. mobility trace. Algorithms used for performance comparison:To justify Roma Taxi [39]:This dataset contains mobility traces of the performance and flexibility of our ConMap framework,we taxi cabs in Rome.Italy.It contains GPS coordinates of embed three different algorithms in ConMap for computing approximately 320 taxis collected over 30 days. the Steiner tree in the intermediate graph.The first one is Parameter setting:For each dataset,we extract ten groups the SPT heuristic [3],[4].It constructs the Steiner tree by data of 50 nodes in 100 time slots and normalize the distance finding the shortest path from the source to all the destinations. between nodes into the range of 10 to 5000 for consistency. The second one is the MST heuristic [3].[4]that computes We designate one source and four/six destinations and set the Steiner tree by firstly establishing a minimum spanning the delay constraint of the multicast session from 10 to 100 arborescence and then pruning the unnecessary edges.And time slots.Due to space limitations,we defer all the graphical the last one is the approximation algorithm for directed representation of results in the scenarios of four destinations to Steiner tree problem proposed by Charikar et al.[35]and Appendix A.Furthermore,for the energy model,we adopt a further improved in [37].We also implement a brute-force widely used assumption that the transmission energy is a pow- algorithm to obtain the exact solutions for linear receiving er of the transmission range [4].[3].And for receiving energy, energy function as the baseline.We omit the corresponding we select f()=50k,f(k)=100 and f()=20k2 where exact results for the cases of sublinear and suplinear settings k is the number of intended receivers in a transmission as the primarily due to two reasons:(i)our algorithm adds a gadget

10 Delay Constraint 10 20 30 40 50 60 70 80 90 100 Energy 400 600 800 1000 1200 1400 1600 1800 2000 2200 2400 ConMap-CHA ConMap-SPT ConMap-MST Brute Force Dataset: Brightkite Receiving Energy: Linear (a) Delay Constraint 10 20 30 40 50 60 70 80 90 100 Energy 400 600 800 1000 1200 1400 1600 1800 2000 2200 2400 ConMap-CHA ConMap-SPT ConMap-MST Dataset: Brightkite Receiving Energy: Sublinear (b) Delay Constraint 10 20 30 40 50 60 70 80 90 100 Energy 400 600 800 1000 1200 1400 1600 1800 2000 2200 2400 ConMap-CHA ConMap-SPT ConMap-MST Dataset: Brightkite Receiving Energy: Superlinear (c) Delay Constraint 10 20 30 40 50 60 70 80 90 100 Energy 400 600 800 1000 1200 1400 1600 1800 2000 2200 2400 ConMap-CHA ConMap-SPT ConMap-MST Brute Force Dataset: Gowalla Receiving Energy: Linear (d) Delay Constraint 10 20 30 40 50 60 70 80 90 100 Energy 400 600 800 1000 1200 1400 1600 1800 2000 2200 2400 ConMap-CHA ConMap-SPT ConMap-MST Dataset: Gowalla Receiving Energy: Sublinear (e) Delay Constraint 10 20 30 40 50 60 70 80 90 100 Energy 400 600 800 1000 1200 1400 1600 1800 2000 2200 2400 ConMap-CHA ConMap-SPT ConMap-MST Dataset: Gowalla Receiving Energy: Superlinear (f) Delay Constraint 10 20 30 40 50 60 70 80 90 100 Energy 400 600 800 1000 1200 1400 1600 1800 2000 2200 2400 ConMap-CHA ConMap-SPT ConMap-MST Brute Force Dataset: Roma Taxi Receiving Energy: Linear (g) Delay Constraint 10 20 30 40 50 60 70 80 90 100 Energy 100 300 500 700 900 1100 1300 1500 1700 1900 2100 ConMap-CHA ConMap-SPT ConMap-MST Dataset: Roma Taxi Receiving Energy: Sublinear (h) Delay Constraint 10 20 30 40 50 60 70 80 90 100 Energy 100 300 500 700 900 1100 1300 1500 1700 ConMap-CHA ConMap-SPT ConMap-MST Dataset: Roma Taxi Receiving Energy: Superlinear (i) Fig. 7. The energy consumption of the transmission schemes yielded by the three/four algorithms under different scenarios with six destinations. The dataset and receiving energy function are labeled in the figures. as network nodes and use their location information at different timestamps to create mobility trace. • Gowalla Social Network [38]: Gowalla is a location￾based social networking website where users share their locations by checking-in. Similarly, we consider users as network nodes and use their location information to create mobility trace. • Roma Taxi [39]: This dataset contains mobility traces of taxi cabs in Rome, Italy. It contains GPS coordinates of approximately 320 taxis collected over 30 days. Parameter setting: For each dataset, we extract ten groups data of 50 nodes in 100 time slots and normalize the distance between nodes into the range of 10 to 5000 for consistency. We designate one source and four/six destinations and set the delay constraint of the multicast session from 10 to 100 time slots. Due to space limitations, we defer all the graphical representation of results in the scenarios of four destinations to Appendix A. Furthermore, for the energy model, we adopt a widely used assumption that the transmission energy is α pow￾er of the transmission range [4], [3]. And for receiving energy, we select f(k) = 50k, f(k) = 100k 1 2 and f(k) = 20k 2 where k is the number of intended receivers in a transmission as the representatives of linear, sublinear and superlinear functions of receiving energy, respectively. All the results demonstrated are the average of the ten groups. Note that we are interested in the relative quantity of energy consumption, and thus we do not relate the amount of energy consumption to specific physical quantity. Algorithms used for performance comparison: To justify the performance and flexibility of our ConMap framework, we embed three different algorithms in ConMap for computing the Steiner tree in the intermediate graph. The first one is the SPT heuristic [3], [4]. It constructs the Steiner tree by finding the shortest path from the source to all the destinations. The second one is the MST heuristic [3], [4] that computes the Steiner tree by firstly establishing a minimum spanning arborescence and then pruning the unnecessary edges. And the last one is the approximation algorithm for directed Steiner tree problem proposed by Charikar et al. [35] and further improved in [37]. We also implement a brute-force algorithm to obtain the exact solutions for linear receiving energy function as the baseline. We omit the corresponding exact results for the cases of sublinear and suplinear settings primarily due to two reasons: (i) our algorithm adds a gadget