Energyefficient scheduling with individual packet

Authors: Wanshi Chen Urbashi Mitra Michael J Neely

Publish Date: 2008/01/17

Volume: 15, Issue: 5, Pages: 601-618

PDF Link

Abstract

This article focuses on energyefficient packet transmission with individual packet delay constraints over a fading channel The problem of optimal offline scheduling visàvis total transmission energy assuming information of all packet arrivals and channel states before scheduling is formulated as a convex optimization problem with linear constraints The optimality conditions are analyzed From the analysis a recursive algorithm is developed to search for the optimal offline scheduling The optimal offline scheduler tries to equalize the energyrate derivative function as much as possible subject to causality and delay constraints in contrast to the equalization of transmission rates for optimal scheduling in static channels It is shown that the optimal offline schedulers for fading and static channels have a similar symmetry property Combining the symmetry property with potential idling periods upper and lower bounds on the average packet delay are derived The properties of the optimal offline schedule and the impact of packet sizes individual delay constraints and channel variations are demonstrated via simulations A heuristic online scheduling algorithm assuming causal traffic and channel information is proposed and shown via simulations to achieve energy and delay performances comparable to those of the optimal offline scheduler in a wide range of scenariosFor Lemma 2 since r mast 0 and r m+1ast 0 we have mu 3mast=mu 3m+1ast=0 Case 1 is further due to an empty buffer at the end of slot m and hence a non delaycritical slot such that mu 2mast=0 in 6 Case 2 is further due to mu 1mast=0 as slot m is delaycritical and hence nonempty ending Case 3 is further due to mu 1mast=0 and mu 2mast=0 as slot m is neither emptyending nor delaycriticalFor Lemma 3 Case 1 is due to mu 3m+1ast=0 nonidling slot and mu 1mast=0 nonempty ending slot in 6 Case 2 is due to mu 3mast=0 nonidling slot and the last condition in 5 ie slot m can not be delaycritical if slot m + 1 is idleFor Lemma 4 Case 1 is due to mu 3m+last=0 nonidling slot and mu 1iast=0 i=mldotsm+l1 idling slots can not be emptyending while Case 2 is due to mu 3mast=0 nonidling slot and mu 2iast=0 i=mldotsm+l1 an idling slot can not be preceded by a delaycritical slot in 7For Lemma 5 since r mast 0 and r m+last 0 we have mu 3mast=mu 3m+last=0 Case 1 is further due to mu 2iast=0 i=mldotsm+l2 as slots i = m + 1m + l − 1 are idle and mu 2m+l1ast=0 non delaycritical in 7 Case 2 is further due to mu 1 mast=0 non emptyending and mu 1iast=0 i=m+1ldotsm+l1 as slots i = m + 1m + l − 1 are idle in 7 The last case is further due to the combination of Case 1 and Case 2 ie mu 1iast=0 and mu 2iast=0 i=mldotsm+l1First note that any idling periods between time 0 and t start 1 and in between a packet transmission have no impact on Updelta t mv forall m For a particular min1ldotsM1 if there is one or more idle slot between t endm and t startm+1 Δt m v   0 and it equals to half of the idling period However any other idling periods between t end j and t start j + 1   j ≠ m have no impact on Updelta t mv In the special case of m = M if there are idling slots after packet M transmission we have Updelta t Mv = M+D1tau st endM However due to the symmetry property there must exist a realization of the same length of an idling period between time 0 and t start 1 which does not impact Updelta t 1v Effectively the idling period after t endM if any only contributes half of its duration to Updelta t mv Therefore we have

Keywords: