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