Amar Prakash Azad

Sara Alouf
email: salouf@sophia.inria.fr

Eitan Altman
email: altman@sophia.inria.fr

Vivek Borkar
email: borkar@tifr.res.in

Georgios S Paschos

Optimal Control of Sleep periods for Wireless terminals

Keywords: Dynamic programming, optimization, performance evaluation, WiMAX

We consider a mobile connected to a base station, saving energy by shutting off its transceiver, and

we try to answer the fundamental question: what is the optimal sleep policy? Firstly, we study the model from optimal control perspective. We consider off-times (periods of inactivity) of unknown duration. We study the question of scheduling "waking up" instants in which the mobile communicates with the base station and checks whether the inactivity period is over. There is a cost proportional to the delay from the moment the off-time ends until the mobile discovers it, a (small) running cost while the mobile is sleeping and also a cost for waking up.

We show that constant sleep periods are optimal for Poisson arrivals and derive the optimal period. We show that this structure does not hold for other off-time distributions but manage to obtain suboptimal solutions which perform strictly better than the constant one. We finally obtain structural properties for optimal policies for the case of arbitrary distribution of off-times.

Technological restrictions often permit a limited set of policies to be implemented. Motivated by this, we investigate classes of policies with specific constraints. What is the optimal policy within each class and what are the optimal parameters for it? To answer these questions, we adopt the parametric optimization approach which entails cost minimization for a given parameterized policy and selection of the best policy among a class. We provide the optimal solution for each class which can be used in closed form or evaluated numerically depending on the case. Our framework allows us to compare the performance of obtained optimal policies, proposed suboptimal policies as well as that of standard policies like IEEE 802.16e.

I. INTRODUCTION

Mobile terminals using contemporary radios consume a significant amount of energy, while being idle, by using unnecessary compartments of their electrical circuits. Therefore, one way to reduce the consumed energy and increase battery life, is to shut off the transceiver totally, i.e. put the mobile terminal into sleep mode. This approach has been recently supported by novel protocols like IEEE 802.16e (see [START_REF]Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems -Amendment: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands[END_REF]) and 3GPP LTE (see [START_REF]3GPP TS 36.300[END_REF]) where a general framework for sleep is defined. Since these standards allow for vendor design of the sleep policy, optimal design of such policies is an open issue of great interest.

Nevertheless, shutting off the transceiver whenever there is no scheduled activity has side effects on the responsiveness A part of this article was presented in the IEEE conference of decision and control (CDC) Shanghai, China, Dec. 2009 and in the conference IFIP Wireless Days, Paris, France, Dec. 2009, where it received the best paper award.

of the terminal. If the attention of the mobile is suddenly required, the transceiver might be shut off and thus the mobile unavailable. The longer the sleep periods, the longer the expected response delay. Therefore, one can identify an inherent tradeoff of energy management: increase sleep period length to improve energy saving or decrease sleep period length to reduce delays. Careful scheduling of sleep periods is then needed in order to minimize energy consumption while keeping the delays small.

A. Related Work

Since the initial announcement of IEEE 802.16e Standards for mobility [START_REF]Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems -Amendment: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands[END_REF], there has been an important volume of performance studies on the subject. The first approach chronologically is found in [START_REF] Xiao | Energy saving mechanism in the IEEE 802.16e wireless MAN[END_REF]. In an effort to relax some assumptions, [START_REF] Zhang | Energy management in the 802.16e MAC[END_REF]- [START_REF] Zhu | Delay analysis for sleep-based power saving mechanisms with downlink and uplink traffic[END_REF] study the impact of outgoing traffic, [START_REF] Lee | MAC sleep mode control considering downlink traffic pattern and mobility[END_REF], [START_REF] Han | Performance analysis of sleep mode operation in IEEE 802.16e mobile broadband wireless access systems[END_REF] study the effect of setup time while [START_REF] Park | Performance modelling and analysis of the sleep mode in IEEE 802.16e WMAN[END_REF]- [START_REF] Zhu | Queueing delay and energy efficiency analyses of sleep based power saving mechanism[END_REF] deal with queueing implications in the analysis. [START_REF] Paschos | Providing quality of service guarantees in multiclass IEEE 802.16e sleep mode[END_REF] deals with the multiclass version of sleep mode in IEEE 802.16e. The impact of bidirectional traffic on sleep mode is studied in [START_REF] Turck | Performance of the ieee 802.16e sleep mode mechanism in the presence of bidirectional traffic[END_REF] and correlated traffic is studied in [START_REF] Turck | Performance of the sleep-mode mechanism of the new ieee 802.16m proposal for correlated downlink traffic[END_REF] which is applied to IEEE 802.16m.

The above models assume a Poisson process for the packet arrivals. The Poisson modeling is rationalized by the fact that the activity requests are generated by a potentially very large population of sources. In [START_REF] Zhang | Performance modeling of energy management mechanism in IEEE 802.16e mobile WiMAX[END_REF], the authors are using hyper-Erlang distribution for the packet interarrival period. In [START_REF] Feldmann | Fitting mixtures of exponentials to longtail distributions to analyze network performance models[END_REF], [START_REF] Almhana | Traffic estimation and power saving mechanism optimization of IEEE 802.16e networks[END_REF], hyper-exponential arrivals are proposed. In any of the above cases, an exogenous arrival process that does not depend on the energy management scheme is considered. Moreover, the delay metric taken is the average packet delay in the system.

Regarding the process of arriving packets, there are other works that provide evidence of heavy-tailed off-time distributions on the Internet and on the World Wide Web (e.g., a Pareto type distribution). In [START_REF] Crovella | Self-similarity in world wide web traffic-evidence and possible causes[END_REF] the operator's idle periods are found to be heavy-tailed. As heavy-tailed distributed random variables can be well approximated by hyper-exponential distributions [START_REF] Feldmann | Fitting mixtures of exponentials to longtail distributions to analyze network performance models[END_REF], [START_REF] Riska | Efficient fitting of long-tailed data sets into hyperexponential distributions[END_REF], this gives motivation to study off-times with hyper-exponential distributions. In [START_REF] Azad | Optimal sampling for state change detection with application to the control of sleep mode[END_REF] we modeled the arrival process as an hyper-exponential process to investigate sleep mode.

Recent works [START_REF] Lee | MAC sleep mode control considering downlink traffic pattern and mobility[END_REF], [START_REF] Xiao | An enhanced energy saving mechanism in IEEE 802.16e[END_REF], [START_REF] Jeong | Performance of adaptive sleep period control for wireless communications systems[END_REF] focus on heuristic adaptive algorithms whose goal is to control the sleep period length according to the incoming arrival process. The work [START_REF] Shuman | Optimal sleep scheduling for a wireless sensor network node[END_REF] derives an optimal sleep policy using average cost structure for a given number of consecutive sleep durations. In [START_REF] Azad | Vacation policy optimization with application to ieee 802.16e power saving mechanism[END_REF], we derive the optimal sleep policy in a given class of policies.

Our work departs from the existing models in the following aspect: rather than assuming an exogenous independent arrival process, we have in mind elastic arrival processes in which (i) the duration of the activity period does not depend on the response delay-defined as the duration between the instant a request is issued and the instant at which the service actually begins-and (ii) the off-time begins when the activity of the mobile ends. Both assumptions are appropriate to interactive applications such as web browsing, see [START_REF] Tran-Gia | Source traffic modeling of wireless applications[END_REF] for a coupling between traffic models and actual applications. As a result, the measure for delay is taken to be the mobile's response delay to the oldest activity request taking place while in sleep mode.

B. Contribution

In this section we clarify our contribution. Our objective is to obtain the optimal sleep policy; the policy which minimizes the energy consumption and the system response delay simultaneously, while maintaining the desired balance between the two (the balance is expressed via a weight). For the off-time period distribution we will consider a. Exponential distribution; b. Hyper-exponential distribution; c. General distribution.

Off-times of exponentially distributed length correspond to the Poisson arrivals case. Also, we shall consider the case when the parameter of the exponential distribution is unknown but we have a known prior distribution on that parameter. This is equivalent to using a hyper-exponential distribution for the off-time. Modeling the hyper-exponential distribution for off-times will offer insight to the case of heavy-tailed distributions as well. Lastly, we will provide structural results for the optimal policy in case of general distributions.

In the above framework we will seek optimal sleep policies. Also, technological restrictions often allow only certain types of policies to be implemented. Motivated from such scenarios, we constrain the set of policies to those fulfilling certain conditions and seek the optimal policies within this set. Furthermore, we study the performance of the IEEE 802.16e standard mechanism. In particular, these standards provide degrees of freedom for the vendor which we utilize to optimize the performance. We show, that in many cases, the proposed standards are suboptimal in the sense that even if the best parameters are selected, the optimal performance cannot be achieved.

Our contributions are the following: 1. We formulate the problem of cost minimization where the cost is a weighted function of energy consumption and response delay measured from the first activity request when inactive. We show that this cost indeed depends on the off-time distribution as well as the selected sleep policy. 2. We use dynamic programming (DP) and show that:

-For exponential off-times, the constant sleep period is optimal and given in closed form.

-For hyper-exponential off-times, interesting structural properties exist. In particular, we show that the optimal policy has sleep periods of bounded length. Asymptotically, the optimal policy converges to the constant policy corresponding to the smallest rate phase, irrespective of the initial state. This optimal policy can be computed numerically using value iteration.

-For any general off-time distribution, the optimal policy has sleep periods of bounded length. 3. We propose suboptimal policies using policy iteration which perform strictly better than optimal "homogeneous" policies and are simpler to compute. We show numerically the performance of such suboptimal solutions using one stage and two stage policy iteration. 4. We use parametric optimization to identify optimal parameters for the following family of sleep policies: (i) Random exponential periods; they can be derived in closed form for any off-time distribution. (ii) Constant periods. (iii) Scaled and General random periods. (iv) Semi-constant periods. (v) Multiplicative periods; similar to those used in WiMAX. (vi) General deterministic periods; 5. We compare the proposed policies with that of the IEEE 802.16e standard [START_REF]Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems -Amendment: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands[END_REF] under various statistical assumptions.

C. Structure

The rest of the paper is structured as follows: Section II outlines our system model, introduces the cost function and presents some preliminaries calculations for the rest of the paper. Section III introduces DP and derives the optimal sleep control and relevant characteristics for hyper-exponential offtimes. Section III-D tackles the problem of finding the optimal policy under the worst case process of arrivals. In IV, the parametric optimization preliminaries are laid out. Section IV-A investigates policies with identically distributed sleep periods while those with non-identically distributed ones are tackled in Section IV-B. Numerical results and a comparative study of the different optimal policies and of the IEEE 802.16e standards are reported in Section V. We last conclude the paper in Section VI.

II. SYSTEM MODEL

We consider a mobile terminal connected to a base station. The terminal goes through consecutive active and inactive periods. Focusing on periods of inactivity, the terminal goes through a sequence of sleep and listen periods until an incoming activity request is detected, see Fig. 1. In particular, in the beginning of each sleep period, the device chooses the sleep period length (also called sleep mode window in the IEEE 802.16e standards) while the listen period length window is considered negligible. At the end of the sleep period, the terminal communicates with the base station to check for activity requests. In case there is no incoming activity waiting at the base station, a fixed energy cost is incurred for checking the system state. In case at least one activity has arrived, the inactivity period is finished and a delay cost is incurred depending on the waiting time of the first activity request (the 1. An inactivity period T X . At time T i , the mobile decides on a sleep period length B i+1 and returns to sleep. At time T i+1 = T i + B i+1 , it wakes up to check for activity requests. The inactivity period ends when an activity request is detected on a listen period. oldest one), which itself depends on the terminal's choice for the sleep period length.

τ B 1 B 2 B 3 B X T 1 T 2 T 3 T X-1 T X T 0 . . . Fig.
An equivalent modeling of the system is one that considers a server that goes on repeated vacations, see [START_REF] Alouf | Analysis of an M/G/1 queue with repeated inhomogeneous vacations with application to IEEE 802.16e power saving mechanism[END_REF]. The incoming traffic load is replaced by customers waiting to be served and the vacation length is then equivalent to sleep period length. In this paper we will use the same notation as [START_REF] Alouf | Analysis of an M/G/1 queue with repeated inhomogeneous vacations with application to IEEE 802.16e power saving mechanism[END_REF] but refer to sleep periods instead.

Let X denote the number of sleep periods in an inactivity period. X is a discrete random variable (rv) taking values in IN *1 . The duration of the kth sleep period is a rv denoted B k , for k ∈ IN * . For analytical tractability, we consider periods {B k } k∈IN * that are mutually independent rvs. The time at the end of the kth sleep period is a rv denoted T k , for k ∈ IN * . We denote T 0 as the time at the beginning of the first sleep period; by convention T 0 = 0. We naturally have

T k = T k-1 + B k = k i=1 B i .
Observe that a generic inactivity period ends at time T X .

We will be using the following notation Y(s) := E[exp(-sY )] to denote the Laplace-Stieltjes transform of a generic rv Y evaluated at s. Hence, we can readily write T k (s) = k i=1 B i (s). Let τ denote the time length between the start of the first sleep period and the arrival of an activity request; this time is referred to as the "off-time". Since a generic inactivity period ends at time T X , the service of the first activity request to arrive during the inactivity period will be delayed for T X -τ units of time. τ is a rv whose probability density function is f τ (t), t ≥ 0. In most of the cases, and unless otherwise stated, we will be assuming that τ is hyper-exponentially distributed with n phases and parameters λ λ λ = (λ 1 , . . . , λ n ) and q = (q 1 , . . . , q n ). In other words, we have

f τ (t) = n i=1 q i λ i exp(-λ i t), n i=1 q i = 1. (1)
Given its definition, the off-time τ is also the conditional residual inter-arrival time. Observe that when n = 1, τ will be exponentially distributed with parameter λ = λ 1 , which, thanks to the memoryless property of this distribution, is equivalent to having a Poisson arrival process with rate λ.

The power required by a mobile to keep the transceiver on while listening to the channel and checking for requests (packets or flows) is denoted P L . We assume that the listen period is a fixed parameter, which makes the energy consumed during listen periods a fixed quantity, name it E L . This is actually a penalty paid at the end of each sleep period. Instead, while sleeping (the device is turned off) , the power consumed is denoted by P S , with P S < P L . The energy consumed by a mobile during sleep period B k is then equal to E L + P S B k , and that consumed during a generic inactivity period is equal to E L X + P S T X . The device is then eager to use longer sleep periods in order to save energy and extend battery lifetime.

In the spirit of achieving a Quality of Service (QoS) tradeoff, we are interested in finding the optimal policy that minimizes energy consumption and delay. Formally, we are interested in minimizing the cost of the power save mode, which is seen as a weighted sum of the energy consumed during the power save mode and the extra delay incurred on the traffic by a sleeping mobile. Let V be this cost; it is written as follows

V := E [¯ (T X -τ ) + (E L X + P S T X )] (2) = -¯ E[τ] + E L E[X] + ηE[T X ] (3)
where is a normalized weight that takes value between 0 and 1; ¯ = 1 -; η := ¯ + P S ; and the expectation is taken over the random off-time τ as well as the randomness of selected sleep periods (if they are selected at random).

The derivation of the elements of (3) when τ is hyperexponentially distributed is straightforward. We derive

P (X = k) = P (τ > T k-1 ) -P (τ > T k ) = n i=1 q i T k-1 (λ i ) (1 -B k (λ i )) ; E[τ] = n i=1 q i /λ i ; E[X] = ∞ k=0 n i=1 q i T k (λ i ); (4) E[T X ] = ∞ k=0 n i=1 q i T k (λ i )E[B k+1 ]. (5)
Using (3)-( 5), the cost can be rewritten

V = -¯ E[τ] + ∞ k=0 n i=1 q i T k (λ i ) ( E L + ηE[B k+1 ]) . (6)
Equation ( 6) is very interesting in that the off-time τ appears only through its expectation. Given that the cost depends only on E[τ], so will the minimal cost and the optimal control. This is true for any distribution of the sleep periods.

For convenience, we have grouped the major notation used in the paper in Table II.

III. DYNAMIC PROGRAMMING

Dynamic programming (DP) is a well-known tool which allows to compute the optimal decision policy to be taken at each intermediate observation point, taking into account the whole lifetime of the system. Considering our system model, we want to identify the optimal sleep policy where decisions are taken at each intermediate wake-up instance. Hence, a DP Branch of the Lambert W function that is real-valued on the interval [-exp(-1), 0] and always below -1 λ λ λ, q rate/probability vector in the n-phase hyper-exponential distribution, λ λ λ = (λ 1 , . . . , λn), q = (q 1 , .

η = ¯ + P S , 0 < η ≤ 1 + P S ζ i = 1 + λ i E L η , i = 1, . . . , n, ζ i > 1
approach is a natural candidate for determining the optimal policy. The observation points are at the end of the sleep periods, i.e., at t k . The conditional residual off-time at a time t is denoted τ t . We introduce the following DP:

V k (t k ) = min b k+1 ≥0 E[c(t k , b k+1 )]+P (τ t k > b k+1 )V k+1 (t k+1 ) .
Here, V k (t k ) represents the optimal cost at time t k where the argument t k denotes the state of the system at time t k . The terms P (τ t k > b k+1 ) and c(t k , b k+1 ) respectively represent the transition probability and the stage cost at t k when the control is b k+1 . In generic notation, the per stage cost is

c(t, b) = ¯ E[(b -τ t )1 τt≤b ] + (E L + P S b). (7)
We can see that each stage is characterized by the distribution of the residual off-time τ t . The state of the system in sleep mode can then by described by the distribution of τ t .

In the rest of this section, three cases will be considered following the distribution of the off-time. We start with the DP solution for exponential off-times, then derive some structural properties of the DP solution for hyper-exponential off-times. Last, the case of general off-times is considered: structural properties of the optimal policy are found and then suboptimal solutions through DP are discussed.

A. Exponential Off-Time

By setting n = 1 in (1) we study the particular case of Poisson arrivals with rate λ (in the next subsection we will study the case of arbitrary n). In such a case, both the off-time τ and the conditional residual off-time τ t will be exponentially distributed with parameter λ, for all t (i.e., for any stage). The distribution of τ t is characterized solely by the rate λ. In other words, as time goes on, the state of the system is always represented by the parameter λ. Henceforth, the DP involves a single state, denoted λ.

We are faced with a Markov Decision Process (MDP), a single state λ, a Borel action space (the positive real numbers) and discrete time. Note that the sleep durations are not discrete. However, decisions are taken at discrete embedded times: the kth decision is taken at the end of the (k -1)st sleep period. Therefore, we are dealing with a discrete time MDP. This is called "negative" dynamic programming [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. It follows from [START_REF] Feinberg | On stationary strategies in borel dynamic programming[END_REF] that we can restrict to stationary policies (that depend only on the state) and that do not require randomization. Since there is only one state (at which decisions are taken) this implies that one can restrict to sleep periods that have fixed size and that are the same each time a decision has to be taken. In other words, the optimal sleep policy is the constant one. Hence the optimal value is given by the minimization of the following MDP:

V (λ) = min b≥0 ¯ E b -τ (λ) 1 τ (λ)≤b + (E L + bP S ) + P τ (λ) > b V (λ) . ( 8
)
Proposition III.1. The optimal sleep period length for exponential off-time and the minimal cost are given by b = -

1 λ ζ + W -1 -e -ζ ; (9)
V (λ) = - 1 λ ¯ + ηW -1 -e -ζ , (10)
with ζ := 1 + λ E L /η, and where W -1 denotes the branch of the Lambert W function2 that is real-valued on the interval [-exp(-1), 0] and always below -1.

Proof : The proof is given in Appendix A.

B. Hyper-Exponential Off-Time

We assume in this section that τ is hyper-exponentially distributed with n phases and parameters λ λ λ = (λ 1 , . . . , λ n ) and q = (q 1 , . . . , q n ).

1) Distribution of the Conditional Residual off-time τ t : The tail of τ t can be computed as follows

P (τ t > a) = P (τ > t + a | τ > t) = P (τ > t + a) P (τ > t) = n i=1 q i exp(-λ i t) exp(-λ i a) n j=1 q j exp(-λ j t) = n i=1 g i (q, t) exp(-λ i a) (11)
where

g i (q, t) := q i exp(-λ i t) n j=1 q j exp(-λ j t) , i = 1, . . . , n. (12)
We denote g(q, t) as the n-tuple of functions g i (q, t), i = 1, . . . , n. Observe that g(q, 0) = q. The operator g transforms the distribution q into another distribution q such that n j=1 q j = 1 and q j > 0. Equation ( 11) is nothing but the tail of a hyper-exponential rv having n phases and parameters λ λ λ and g(q, t). Except for the probabilities of the n phases, the off-time τ and its residual time τ t have the same distribution and same parameter λ λ λ. As time goes on, the residual time keeps its distribution but updates its phases' probabilities, through the operator g. It can be shown that

g i (q, b 1 + b 2 ) = g i g i (q, b 1 ), b 2 . ( 13
)
In other words, the operator g is such that the result of the transformation after b 1 + b 2 units of time is the same as that of a first transformation after b 1 units of time, followed by a second transformation after b 2 units of time.

To simplify the notation, we will drop the subscript of the residual off-time τ t , and instead, we will add as argument the current probability distribution (which is transformed over time through the operator g). For instance, if at some point in time, the residual off-time has the probability distribution q , then we will use the notation τ (q ).

The results above can be extended to account for a random passed time T . We have

P (τ > T + a | τ > T ) = n i=1 g i (q, T ) exp(-λ i a)
where

g i (q, T ) := q i T(λ i ) n j=1 q j T(λ j ) = q i T(λ i ) P (τ > T ) . ( 14
)
There is an abuse of notation in the definition of g i (q, T ), as this function depends on the distribution of T and not on the rv T itself. The function g i (q, T ) is not a rv. Observe that [START_REF] Paschos | Providing quality of service guarantees in multiclass IEEE 802.16e sleep mode[END_REF], where time is deterministic, is a particular case of [START_REF] Turck | Performance of the sleep-mode mechanism of the new ieee 802.16m proposal for correlated downlink traffic[END_REF]. Asymptotic properties of g are provided next. Define the composition g m (q, b) = g g m-1 (q, b), b = g(q, mb), where g 1 (q, b) is the vector whose ith element is given in [START_REF] Paschos | Providing quality of service guarantees in multiclass IEEE 802.16e sleep mode[END_REF]. Assume, without loss of generality, that λ 1 ≤ . . . ≤ λ n . Let e(i) be the n-dimensional vector whose ith element is 1 and all other elements are zero.

Lemma III.1. Fix q and let I(q) be the smallest j for which q j > 0. Then lim m→∞ g m (q, b) = e(I(q)).

Proof : The proof is given in Appendix B.

Lemma III.1 states that, as time passes, the residual offtime's distribution translates its mass towards the phase with the smallest rate, and converges asymptotically irrespective of the initial distribution. This suggests that there exists a threshold on the time after which the optimal policy is the one that corresponds to the optimal policy for state I(q). Lemma III.2. For any q we have lim q →q V (q ) = V (q). Lemma III.2 states that as the state converges, the value also converges to the value at the converged state.

2) DP Solution: Below we formulate the optimization problem as an MDP where the state space is taken to be the simplex of dimension n, i.e. the set of probability measures over the set {1, 2, ..., n}. At each stage, the residual off-time sees its probability distribution being updated. Let q 0 denote the probability distribution of the total off-time. It is then the probability distribution of the residual off-time at time 0. Thanks to the property [START_REF] Turck | Performance of the ieee 802.16e sleep mode mechanism in the presence of bidirectional traffic[END_REF], the probability distribution of the residual off-time at stage k + 1, i.e., at time t k , is q = g(q 0 , t k ). Henceforth, there is a one to one relation between the stage and the current probability distribution of the residual off-time. Without loss of optimality, either of them can be the state in the MDP [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]Sect. 5.4].

The system state is denoted q and represents the current probability distribution of the residual off-time. The initial state is q 0 . We assume that the controller can choose any time b (a constant or a rv) until he wakes up. The transition probabilities are simply P q,b,q = 1 q =g(q,b) .

We are faced with an MDP with a Borel action space and a state space that is the set of probability vectors q. Note however that, starting from a given q, there is a countable set Q of q's so that only states within Q can be reached from q. Therefore we may restrict the state space to the countable set Q. We can again use [START_REF] Feinberg | On stationary strategies in borel dynamic programming[END_REF] to conclude that we may restrict to policies that choose at each state a non-randomized decision b, and the decision depends only on the current state (and need not depend on the previous history). We next show that there is some b such that actions may be restricted to the compact interval [0, b] without loss of optimality.

Consider the policy w that takes always a constant one unit length sleep period. It is easily seen that the total expected cost, when using policy w, is upper bounded by v := ¯ + 1 + sup i 1/λ i (E L + P S ). Here, ¯ is an upper bound on the expected waiting cost and 1 + sup i 1/λ i is an upper bound on E[X], the expected number of sleep periods, and on E[T X ],

the expected off-time duration. We conclude that Lemma III.3. For all q, V (q) ≤ v.

Lemma III.4. Without loss of optimality, one may restrict to policies that take only actions within [0, b] where b = (1/¯ ){v + 1 + 1/(min i λ i )}.

Proof : Let u be an -optimal Markov policy that does not use randomization, where ∈ (0, 1). If u i > b for some i then the expected immediate cost at step i is itself larger than 1 plus the total expected cost that would be incurred under the policy w: E b -τ (q) 1 τ (q)≤b > v + 1. Thus, by switching from time i onwards to w, the expected cost strictly decreases by at least 1 unit; thus u cannot be -optimal.

We conclude that the MDP can be viewed as one with a countable state space, compact action space, discrete time, and non-negative costs (known as "negative dynamic programming"). Using [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] we then conclude:

(i) The optimal value (minimal cost) is given by the mini-mal solution of the following DP:

V (q) = min b≥0 ¯ E b -τ (q) 1 τ (q)≤b (15)
+ (E L + bP S ) + P τ (q) > b V g(q, b) .

(ii) Let B(q) denote the set of all b's that minimize the right hand side of (15) for a given q. Then any policy that chooses at state q some b ∈ B(q) is optimal. The value iteration can be used as an iterative method to compute V (q). Starting with V 0 = 0 we write

V k+1 (q) = min b≥0 ¯ E b -τ (q) 1 τ (q)≤b + (E L + bP S ) + P τ (q) > b V k g(q, b) .
Then V (q) = lim k→∞ V k (q), see [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]. The iteration is to be performed for every possible state q. Lemma III.1 implies that the moving state, g(q, b), converges asymptotically to e(I(q)).

To complete the value iteration, we compute, for a fixed b,

E b -τ (q) 1 τ (q)≤b = b - n i=1 q i 1 -exp(-λ i b) λ i .

C. General Distribution of Off-Time

In this section, off-times have a general distribution. As a consequence, one can no longer expect that the residual offtime will keep the same distribution over time, updating only its parameters. Therefore, the system state is the instant t at which a sleep period is to start. We use again τ t to denote the conditional residual value of τ at time t (i.e., τ -t given that τ > t.

As a state space, we consider the set of non-negative real numbers. An action b is the duration of the next sleep period. We shall assume that b can take value in a finite set. The set of t reachable (with positive probability) by some policy is countable. We can thus assume without loss of generality that the state space is discrete. Then the following holds: Proposition III.2. (i) There exists an optimal deterministic stationary policy. (ii) Let V 0 := 0, V k+1 := LV k , where

LV (t) := min b {c(t, b) + P (τ t > b)V (t + b)}
where c(t, b) has been defined in [START_REF] Lee | MAC sleep mode control considering downlink traffic pattern and mobility[END_REF]. Then V k converges monotonically to the optimal value V . (iii) V is the smallest nonnegative solution of V = LV .

A stationary policy that chooses at state t an action that achieves the minimum of LV is optimal.

Proof : (i) follows from [ Observe that V k expresses the optimal cost for the problem of minimizing the total cost over a horizon of k steps.

Proposition III.3. Assume that τ t converges in distribution to some limit τ . Define v(b

) := c(b)/[1 -P ( τ > b)]. Then (i) lim t→∞ V (t) = min b v(b). (ii)
Assume that there is a unique b that achieves the minimum of v(b) and denote it by b. Then there is some stationary optimal policy b(t) such that for all t large enough, b(t) equals b.

Proof : The proof is given in Appendix C.

To recapitulate, we have shown, that for a general offtime, it is enough to consider deterministic policies to achieve optimal performance. Also, if the residual off-time distribution converges in time then the optimal policy converges to the constant policy and in fact becomes constant after finite time (under the appropriate conditions). This can be shown to be the case with the hyper-exponential distribution. Indeed, its residual time converges in distribution to an exponential distribution, having as parameter the smallest among the rates of the hyper-exponential distribution.

1) Suboptimal policies through Dynamic Programming: In this section, we propose a suboptimal solution approach using policy iteration for a few stages. For the rest of the stages, we consider a static control that is computed through parametric optimization, which is done next.

Consider a class of policies in which all sleep periods are i.i.d. exponentially distributed rvs with parameter b. We will refer to this class as the "Exponential sleep policy." With this policy, the cost, denoted V e , depends only on E[τ], as detailed hereafter. Conditioning on a given off-time τ , the number of sleep periods decremented by one is a Poisson variable with rate τ /b. It is straightforward to write

E[X] = E[τ]/b + 1; E[T X ] = bE[X] = E[τ] + b.
Equation (3) can be rewritten (recall that η = ¯ + P S )

V e = P S + E L /b E[τ] + E L + ηb. (16)
Observe that ( 16) stands for any distribution of τ . We next find the optimal total cost under the Exponential policy.

Proposition III.4. The cost V e is a convex function having a minimum at

b e = E L E[τ] ¯ + P S . (17)
The minimal total cost is

V e = (P S E[τ] + E L ) + 2 (¯ + P S )E L E[τ] (18)
Proof : Let us compute the first and second derivative of the cost w.r.t. b. We find

V e = η - E L E[τ] b 2 ; V e = 2 E L E[τ] b 3 .
Clearly, V e ≥ 0 for any b > 0, hence V e is a convex function. The derivative V e has a root at b e as given in [START_REF] Almhana | Traffic estimation and power saving mechanism optimization of IEEE 802.16e networks[END_REF], which yields a minimum in the cost V e at b e . Substituting the optimal b e in ( 16) we obtain the minimal cost [START_REF] Crovella | Self-similarity in world wide web traffic-evidence and possible causes[END_REF].

The optimal control is b e . Proposition III.4 is really interesting in that it says that with i.i.d. exponential sleep periods, only the expected off-time defines the optimal control. The off-time τ can be generally distributed. Therefore, Proposition III.4 stands valid for any user application. Now that we have computed the static control for all stages, we proceed with one stage policy iteration. With this iteration, the sleep periods have the form (b 1 , B, B, . . .) where B is an exponentially distributed rv with mean b. We can use DP to compute the optimal policy within this class. The problem is given by

V 1 (0) = min b≥0 {c(0, b 1 ) + P (τ > b 1 )V (b 1 )} (19)
where V (b 1 ) is equivalent to V e in (18) after replacing the off-time τ with the residual off-time at time b 1 , i.e., τ b1 . The optimal control identified through DP is b 1 and b . When τ is hyper-exponentially distributed, the system state is the distribution q which is transformed after each stage through the operator g.

If we add the constraint that the first sleep period should be exponentially distributed with the same distribution as B, then we will be back to the problem of finding an optimal exponentially distributed sleep period with state-independent mean. Since we do not impose this restriction, the policy obtained after one stage iteration will do strictly better than the exponential sleep policy.

This suboptimal method for one stage policy iteration can be extended to more stages. Instances of the two stage policy iteration are provided in Sect. V. As the number of stages of the policy iteration increases, the suboptimal solution converges to the optimal solution (obtained from [START_REF] Zhang | Performance modeling of energy management mechanism in IEEE 802.16e mobile WiMAX[END_REF] if τ is hyper-exponentially distributed).

D. Worst Case Performance

We consider in this section the case where the off-time is exponentially distributed with an unknown parameter. When the distribution of the parameter is known (Bayesian framework) the problem reduces to the study of the hyperexponentially distributed off-time. In practice there could be many situations when the statistical distribution of the offtime is unknown or hard to estimate. In such non-Bayesian frameworks, we can conduct a worst-case analysis: optimize the performance under the worst case choice of the unknown parameter. We assume that this parameter lies within the interval [λ a , λ b ]. The worst case is identified as follows λ w := arg max λ∈[λa,λ b ] min {B k },k∈IN * V . Given that τ is assumed to be exponentially distributed, it is enough to analyze the case of the Constant sleep policy, which has been found to be the optimal in Sect. III-A. The minimal cost under this policy is given in [START_REF] Alouf | Analysis of an M/G/1 queue with repeated inhomogeneous vacations with application to IEEE 802.16e power saving mechanism[END_REF]. We have studied (10) using the mathematics software tool, Maple 11. We found the following: V (λ) is a monotonic function, decreasing with λ; lim λ→+∞ V (λ) = E L ; and lim λ→0 V (λ) = +∞. Thus, the optimal control under worst case is the one corresponding to the smallest rate in the interval considered, i.e., λ w = λ a .

IV. PARAMETRIC OPTIMIZATION

In this section we provide computations of the total cost of equation ( 6) for the case of some interesting parametric policies. We repeat here the equation for ease of reading,

V (b) = -¯ E[τ] + ∞ k=0 n i=1 q i T k (λ i ) ( E L + ηE[B k+1 ]) , (20)
where b above is the vector of selected sleep period lengths. Then we calculate the optimal parameters for these policies which can be used for comparison. In particular, for the Exponential and Constant policies we give closed form results while the rest of the policies are derived up to a point where they are evaluated numerically.

A. Identically Distributed Sleep Periods

This section deals with identically distributed sleep periods, in other words, the control is static. Let B be a generic rv having the same distribution as any of the sleep periods. Thence, [START_REF] Azad | Optimal sampling for state change detection with application to the control of sleep mode[END_REF] can be rewritten as

V (b) = -¯ E[τ] + ( E L + ηE[B]) n i=1 q i 1 -B(λ i ) . (21)
We now propose different policies and derive the optimal control in each case.

E[X] = E[τ]/b + 1; E[T X ] = bE[X] = E[τ] + b.
Equation ( 2) can be rewritten (recall that η = ¯ + P S )

V e (b) = P S + E L /b E[τ] + ( E L + ηb). ( 22
)
Remark IV.1. Equation ( 22) stands for any distribution of τ .

We naturally obtain the same expression if we substitute B(s) for 1/(1 + bs) in [START_REF] Xiao | An enhanced energy saving mechanism in IEEE 802.16e[END_REF]. The same result is obtained via DP in section III-C1.

2) The Constant Policy: In this policy, all sleep periods are equally sized. In other words, B = b. The performance is optimized by controlling the size of b. Substituting B(s) for exp(-sb) in ( 21) yields the following simplified expression for the cost (the subscript stands for "constant")

V c (b) = -¯ E[τ] + ( E L + ηb) n i=1 q i 1 -exp(-λ i b) . ( 23
)
Proposition III.1 yields the optimal values and the minimizer for the case of n = 1.

Proposition IV.1. The cost V c (b) is a convex function having a minimum in ]0, ∞[.

Proof :

The proof is given in Appendix D. Proposition IV.1 proves the existence of a global minimum. Unfortunately, we are not able to derive the optimal b c analytically and use numerical methods to find b c . The dimensionality of the problem can be showcased by the following result.

Proposition IV.2. When n > 1, no optimal constant policy (deterministic with constant sleep period) can be independent of q = (q 1 , . . . , q n ).

Proof : We develop a proof by contradiction. We assume that the optimal b c does not depend on q. Hence, the coefficients of the q i 's in (32) must be null, namely,

1 -exp(-λ i b c )(ζ i + λ i b c ) = 0 for i ∈ {1, . . . , n}. For a given i, the solution is b c = -1 λi ζ i + W -1 (-e -ζi ) (cf.
proof of Proposition III.1). Since b c is a constant, the left-hand-side of the above equality must be a constant whatever i is. This is not the case (the left-hand-side depends on λ i ). We have thereby shown that the optimal control b c must depend on q = (q 1 , . . . , q n ) when n > 1.

3) The Scaled Policy: In this third policy, we consider the random sleep period B to be a factor α of a random variable S with a general distribution, i.e. B = αS. For a given distribution of S, the scaling factor α is controlled to optimize the performance. The cost V s (α) (the subscript stands for "scaled") follows readily from (21) using B(s) = S(αs)

and E[B] = αE[S].

We consider now that S is a discrete random variable taking values in a finite set {a j } j=1,...,J with a probability distribution p = (p 1 , . . . , p J ), i.e., P (S = a j ) = p j and J j=1 p j = 1. Hence, S(s) = J j=1 p j exp(-sa j ), and

E[S] = J j=1 p j a j .
This policy advocates to have each sleep period follow a discrete general distribution, taking values in {αa j } j=1,...,J . The probability distribution p is assumed fixed whereas the set of possible values can be scaled for minimal cost.

The optimization problem can be stated as

V s = min α>0 V s (α); α = arg V s . ( 24
)
It is intractable to solve analytically (24), we will therefore resort to a numerical resolution (cf. Section V).

4) The General Discrete Policy: The fourth policy resembles the third one in that it equally considers a discrete general sleep period for the variable B. However, the set of possible values is now fixed (i.e., α = 1) whereas the probability distribution p can be optimized for minimal cost. We denote the cost as V g (p), where the subscript stands for "general", and write

V g (p) = -¯ E[τ] + n i=1 q i E L + η J j=1 p j a j 1 - J j=1 p j exp(-λ i a j ) .
Our objective is to find p = arg min p V g (p) such that 0 ≤ p j ≤ 1 for j = 1, . . . , J and J j=1 p j = 1. This optimization problem can only be solved numerically.

B. Non-identically Distributed Sleep Periods

If we relax the constraint of identically distributed sleep periods, the mobile is free to choose any sleep period distribution at each waking up instant, a fact that complexes the problem immensely. We will narrow the problem by considering only deterministic sleep periods.

The k th sleep period is now of fixed size b k , the instants {T k } k∈IN are now deterministic, and we let t k = T k for any k to reflect this. We have t 0 = 0 and t k = k j=1 b j . The policies that are considered in this section are: (i) "Semi-Constant" policy: Most sleep periods are equal; (ii) "Multiplicative" policy: Sleep periods increase with time; (iii) "General Deterministic" policy: Sleep periods can last for any positive time.

1) The Semi-Constant Policy: As the name indicates, only a few sleep periods are allowed to be of different size. This is expected to bring some improvement with respect to the Constant policy. For the sake of illustration, let the first sleep period be of size b 0 while all the subsequent ones are of size b. This particular policy will be referred to as "one-stage" policy. The cost is Notice that the m-stage Semi-Constant policy approaches the absolute optimal policy when m → ∞. However, it adds immense computational complexity as m grows. Hence, for practical purposes, one can optimize until a few stages.

V sc (b 0 , b) = -¯ E[τ] + ( E L + ηb) n i=1 q i exp(-λ i b 0 ) 1 -exp(-λ i b) . (25
Also, note that the LTE standards propose an m-stage Semi-Constant policy where the first m stages have equal sleep period length and then the system switches to another value (usually larger).

2) The Multiplicative Policy: This policy is inspired by the power save mode of the IEEE 802.16e [START_REF]Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems -Amendment: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands[END_REF], and more precisely, by type I power saving classes. There, the length of a sleep period is doubled over time until a maximum permissible sleep window, denoted b max , is reached. The size of the k th sleep period is then b k = b 1 2 min{k-1,l} , k ∈ IN * where l := log 2 (b max /b 1 ). We also have

t k = b 1 2 min{k,l} -1 + 2 l (k -l)1 k>l , k ∈ IN * .
The cost of the power save mode of the IEEE 802.16e Standard can be derived from [START_REF] Azad | Optimal sampling for state change detection with application to the control of sleep mode[END_REF], yielding

V Std = -¯ E[τ] + ∞ k=0 n i=1 q i e -λit k E L + ηb 1 2 min{k,l} .
(26) Instead of doubling the sleep periods over time, the multiplicative policy increases the sleep periods by a multiplicative factor f (in the Standard policy, f = 2). The performance is then optimized by controlling the factor f . In this policy, we have

b k = b 1 f min{k-1,l} , k ∈ IN * t k = b 1 f min{k,l} -1 f -1 + f l (k -l)1 k>l , k ∈ IN * V m (f ) = -¯ E[τ] + ∞ k=0 n i=1 q i e -λit k E L + ηb k+1 (27) f = arg min f >1 V m (f ). (28)
The optimal f and the minimal cost V m = V m (f ) (the subscript stands for "multiplicative") will be computed numerically.

3) The General Deterministic Policy: In this section, no particular pattern is imposed on the sleep periods. This policy is a generalization of the Semi-Constant policy as m → ∞. We denote the cost as V d (µ µ µ) where the subscript stands for "deterministic" and µ µ µ := (b 1 , b 2 , . . .) is the deterministic policy. The cost has the same expression as [START_REF] Feinberg | On stationary strategies in borel dynamic programming[END_REF]. A necessary condition for the existence of an optimal control sequence µ µ µ = (b 1 , b 2 , . . .) is that grad V d (µ µ µ ) = 0. Our next step is then to compute the partial derivatives. We have, for j ∈ IN * ,

∂V d (µ µ µ) ∂b j = n i=1 ηq i   e -λitj-1 - ∞ k=j λ i e -λit k b k+1 + E L η   . ( 29
)
Proposition IV.4. When n > 1, no optimal deterministic policy (with arbitrary period length) can be independent of q = (q 1 , . . . , q n ).

Proof : The proof is given in Appendix E. The contradiction between (33) and (34) arises because of n > 1. For n = 1 more results are expected. Indeed, in section III, it shown that the optimal policy is given in closed form and it is constant in time and a function of the arrival rate λ 1 .

V. NUMERICAL INVESTIGATION

In this section we present numerical results when the offtime τ is either exponentially or hyper-exponentially distributed. In each case, the best control and the corresponding cost are computed. Also, we utilize the results of section IV to compare several classes of policies. The cost V , captures the main performance measures: energy consumed during the sleep duration and Const. policy, ε= 0.1 Exp. policy, ε= 0.1 Const. policy, ε= 0.9 Exp. policy, ε= 0.9 (a) Impact on optimal expected sleep duration extra delay incurred due to the sleep mode. The cost V is a weighted sum of both metrics. From (2), it comes that a large value of makes V more sensitive to the energy consumption than to the extra delay, whereas a small gives more weight to the delay.

The various policies are compared through: (i) the optimal expected sleep duration, (ii) the minimal cost achieved, and (iii) the relative improvement with respect to the IEEE 802.16e protocol. The improvement ratio, denoted I, is defined as follows: I := (V Std -V r )/V Std . where the cost V Std of the standard's policy is calculated using [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. The parameters of the Standard policy are b 1 = 2 and l = 10. The physical parameters are set to the following values: E L = 10, P S = 1.

A. Exponential Off-Time

In this case, the optimal is to fix all sleep periods to the value found in [START_REF] Park | Performance modelling and analysis of the sleep mode in IEEE 802.16e WMAN[END_REF].

We evaluate three sleep policies from section IV (cf. Table II) and compare them. The performance of each policy de-

Policy

Optimal cost Control and its optimal value Exponential [START_REF] Crovella | Self-similarity in world wide web traffic-evidence and possible causes[END_REF] expected sleep duration, ( 17) Constant [START_REF] Alouf | Analysis of an M/G/1 queue with repeated inhomogeneous vacations with application to IEEE 802.16e power saving mechanism[END_REF] size of fixed sleep duration, (9) Standard [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF], n = 1 pends on the arrival rate λ and on the normalized weight .

In the following evaluation, we will alternatively vary one of the parameters and fix the other. We first vary λ and fix to 0.1 and 0.9. The weight equal to 0.1 mimics the situation when energy consumption is given lower priority over delay, while equal to 0.9 mimics the opposite situation. Looking at Fig. 2, one can observe the impact of the arrival rate λ on (i) the optimal expected sleep duration (cf. Fig. 2(a)), (ii) the minimal cost (cf. Fig. 2(b)), and (iii) the cost improvement (cf. Fig. 2(c)). We naturally find that the expected sleep duration decreases as λ increases, as foreseen in [START_REF] Park | Performance modelling and analysis of the sleep mode in IEEE 802.16e WMAN[END_REF]. The physical explanation is that, a large arrival rate forces the mobile to be available after shorter breaks, otherwise the cost is too high.

Of more interest are the curves reported in Fig. 2(a), where the optimal cost achieved by the Constant policy always outperforms the costs of the two other policies. This is in agreement with the discussion in Section III, namely, that the constant policy should be the optimal among all possible policies. The Exponential policy outperforms the Standard policy for a large range of values of λ as seen more clearly in Fig. 2(c) where = 0.1.

Observe in Fig. 2(b) how the cost decreases asymptotically to E L (1 for = 0.1 and 9 for = 0.9) as the rate λ increases. The same trend is observed for the cost of the Standard policy. As λ decreases, the increase in V c and V e is due to the increase of the optimal expected sleep duration, while for V Std the increase is due to the extra (useless and costly) listening.

We next vary and fix λ to 0.1 (low traffic) and 5 (high traffic). The results are depicted in Fig. 3. As gets smaller, the extra delay gets more penalizing, enforcing then smaller optimal sleep durations. This is observed in Fig. 3(a). As mentioned earlier, smaller optimal sleep durations yield smaller optimal costs. Thus, the optimal costs increase as increase, as can be observed in Fig. 3(b). For < 0.1, the cost of the Standard policy is fairly insensitive to . This is due to its compromising nature; the first small periods guarantee responsiveness if the off-time is short, and the large periods guarantee a good energy performance if the off-time is large. Evidently, this results in a total cost always above the optimal policies. Also, we can observe that the Standard has been designed to favor energy over delay: it performs quite close to the optimal policy when → 1, i.e. when the cost is indifferent to delay.

Looking at Fig. 3(c), we find again that the Constant policy is the best and that the Exponential policy outperforms the Standard policy in most cases: the Exponential policy yields a substantial improvement over a large range of values of λ and . Exp. policy, q 1 Scaled policy, q 1 Const. policy, q 2 Exp. policy, q 2 Scaled policy, q 2 (a) Impact on optimal expected sleep duration

B. Hyper-Exponential Off-Time

In this case, we compute two suboptimal policies using policy iteration. We compare the performance of these to that of the Exponential sleep policy and the standard's policy. The off-time distribution is hyper-exponential with parameters λ λ λ = {0.2, 3, 10} and q = {0.1, 0.3, 0.6}. The suboptimal solutions are evaluated using [START_REF] Riska | Efficient fitting of long-tailed data sets into hyperexponential distributions[END_REF], the Exponential sleep policy using ( 18)-( 17) and the standard's policy using [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF].

The performance of the four policies is depicted in Fig. 5 against the energy coefficient weight . Naturally, the suboptimal policies perform strictly better than the Exponential sleep policy, having the two stage iteration policy strictly outperforming the one stage one (cf. Fig. 5(b)). Interestingly, for large value of , the standard's policy outperforms all the other policies. As observed earlier, the standard favors energy over delay, so that at large , it is very efficient in reducing the cost. It is expected however that n-stage policy iteration will outperform the standard for sufficiently large n.

Again, we utilize the findings of IV to make a comparison between the Exponential, Constant, Scaled (cf. Section IV-A3), Semi-Constant (cf. Section IV-B1) and Standard policies. Analytical expression are available only for the Exponential policy, for the rest of the policies we resort to using numerical solutions.

For this study, we consider for τ two distinct distributions , namely, q 1 = [0.1, 0.3, 0.6] and q 2 = [0.6, 0.3, 0.1],

yielding an expected off-time E[τ] equal to 0.66 (high incoming traffic) and 3.11 (moderate incoming traffic), respectively. These values of q 1 , q 2 have been intentionally chosen so as to show different behavior of the policies. The parameters of the Scaled policy are (distribution of the variable S) {a 1 , a 2 , a 3 } = {0.2, 1, 3} and p = [0.6, 0.3, 0.1]. The optimal expected sleep duration is then 0.72α . As for the Semi-Constant policy, we report the results of the two-stage one (the first two sleep periods are allowed to have a different size from the rest of the sleep periods).

We vary the weight between 0.001 and 1. The impact of on the expected sleep period length, the cost and the cost improvement can be observed in Fig. 4. We observe the same trends for the optimal expected sleep period length and the optimal cost as with Poisson arrivals (cf. Fig. 3). Unlike the case in Fig. 3(a), the optimal cost achieved by the Constant policy (i.e., V c ) is not the smallest among all costs, at least at high arrival rate (E[τ ] = 0.66 in Fig. 4(b)). The best performance at this arrival rate is achieved by the Exponential and Scaled policies for most values of . Notice the poor performance of the Constant and Semi-Constant policies, which, interestingly enough, exhibit the same trend as the Standard policy.

The performance of the policies at moderate rate can be seen in 4(c)). For E[τ] = 3.11, the Exponential policy is the best whatever the weight , performing at least as good as the Standard policy if not better.

The last policy that we evaluate is the Multiplicative policy (cf. Section IV-B2). We want to compute the optimal multiplicative factor for a variety of distributions of τ . To this end, the rates of the n = 3 phases is taken to be C λ λ λ λ = [0.2C λ , 3C λ , 10C λ ] and the probabilities of the phases are q 2 = [0.6, 0.3, 0.1]. The expected off-time is then E[τ] = 3.11/C λ . We vary the scaling factor C λ from 0.001 (extremely low traffic) to 1 (moderate traffic).

Results are depicted in Fig. 6. On can deduce from Fig. 6(a) that the value f = 2 used in the Standard policy is actually optimal (considering the Multiplicative policy) when there is almost no traffic (E[τ ] = 3110). Even though the values of f for different are very close to each other at C λ = 0.01, we observe a large impact on the cost improvement (cf. Fig. 6(b)).

We can conclude that the optimal cost is highly sensitive to the Multiplicative factor at very low traffic. This is not surprising as sleep periods increase exponentially in the Multiplicative policy, and this is much likely to happen when traffic is very low.

VI. CONCLUSION

The control of sleep periods for mobile terminals is studied. In particular, an optimization problem is formulated where the goal is to minimize energy consumption in wireless networks taking into account the incurred response delays. Previous models studied in the literature have considered an exogenous arrival process, whereas we considered an on-off model in which the off-time begins when the terminal goes to sleep mode and where the duration of the on-time does not depend on the delay imposed by the sleeping during the inactivity period. We derived the optimal policy in case of a Poisson arrival process and found many structural properties of the optimal policy for hyper-exponential and general off-times. Suboptimal policies have been derived in this case using one and two stage policy iteration. Also, we considered several constrained classes of policies with certain optimization parameters and degrees of freedom. Among them, we considered classes that depict the functionality of IEEE 802.16e standards. We showed how these classes are optimized and compared them with each other yielding insightful conclusions. When the off-time is hyper-exponentially distributed, we showed that the IEEE 802.16e standard can be improved substantially if the multiplicative factor is optimized. Also, if one gives small weight to the mobile's response delay and favors the minimization of energy use, then both the exponential and scaled policies are candidate to substitute the standard. The optimal control for the Exponential policy is found in closed form for a general off-time.

Furthermore, our model is general enough to capture other standards for sleep mode with small alterations, like the DRX of 3GPP LTE [START_REF]3GPP TS 36.300[END_REF] and the WMM of IEEE 802.11 (WiFi) [29], a work left for the future. In terms of the model itself, a possible extension is to utilize renewal theory to capture the effect of residual interarrival off-time, thus changing the scope from interactive applications to applications where the service time biases the arrival process. Note, that the case n = 1, analyzed in this paper, covers both cases, but for n > 1 we have only covered interactive applications. Finally, in this paper, we have focused on policies that keep no memory of the past. Alternatively, one can study adaptive policies which can exploit the history of the inactivity period.

) Proposition IV. 3 .

 3 For n = 1, all sleep periods are equal at optimum, i.e., b 0 = b = b c (recall (9)).

  Optimal mean sleep size b *

9 ( 1 Fig. 2 .

 912 Fig. 2. Exponential τ : Impact of λ for various sleep policies.

5 ( 5 ( 8 Fig. 3 .

 5583 Fig. 3. Exponential τ : Impact of for various sleep policies.

Fig. 4 .

 4 Fig. 4. Hyper-exponential τ : Impact of for various sleep policies.

Fig. 5 .

 5 Fig. 5. Sleep durations and costs with hyper-exponential off-times.

  Fig. 6. Hyper-exponential τ : Impact of C λ on the multiplicative policy.

  Duration of kth sleep period T kElapsed time until kth sleep period,T k = k i=1 B i T 0Starting time of power save mode, T 0 = 0 E L

		TABLE I
		GLOSSARY OF NOTATIONS
	X	Number of sleep periods
	B k
		Energy consumed in the listen period
	P S	Power consumed by a mobile in a sleep state
	, ¯	Normalized energy/delay weight, 0 < ≤ 1, ¯ = 1 -
	V	Cost function
	c(t, b)	Cost incurred by sleep period of size b having started at time
		t
	W -1

  . . , qn) τ Off-time (i.e., arrival time of first activity request) τt Conditional residual off-time (i.e., from t to the arrival of first activity request) B = {B k } k∈IN * , generic sleep policy b Parameter of the policy B α Parameter of the distribution of B

k for Scaled policy p Distribution of B k for Scaled and General Discrete policies Y Laplace-Stieltjes transform of a random variable Y

TABLE II POLICIES

 II USED FOR COMPARISON WHEN τ EXPONENTIAL

Given that our objective is to study energy saving, the value X = 0 is not allowed.

The Lambert W function, satisfies W (x) exp(W (x)) = x. As y exp(y) = x has an infinite number of solutions y for each (non-zero) value of x, the function W (x) has an infinite number of branches.

VII. ACKNOWLEDGEMENTS The authors of INRIA were partly supported by the ANR ECOSCELL. The work of V Borkar and E Altman was partly supported by Indo-French Centre for the Promotion of Advanced Research (IFCPAR), project 4000-IT. The work of G Paschos is partly supported by European Commission IST projects FP7-ICT-257740 (TREND) and STREP-FP7-INFO-ICT-224218 (OPNEX).

APPENDIX A PROOF OF PROPOSITION III.1

Proof : From (8) we can express

Substituting E b -τ (λ) 1 τ (λ)≤b = λb -1 + exp(-λb) λ and P τ (λ) > b = exp(-λb) in [START_REF] Corless | On the Lambert W function[END_REF] and differentiating w.r.t. b we obtain

At the extremum of V (λ), denoted b , we must have

The last expression is of the form y exp(y) = x with y = -ζ -λb and x = -exp(-ζ). The solution y is the Lambert W function [START_REF] Corless | On the Lambert W function[END_REF], denoted W , at the point x. 9) is readily found. Replacing [START_REF] Park | Performance modelling and analysis of the sleep mode in IEEE 802.16e WMAN[END_REF] in [START_REF] Corless | On the Lambert W function[END_REF] and using the relation exp(y) = x/y, one can derive [START_REF] Alouf | Analysis of an M/G/1 queue with repeated inhomogeneous vacations with application to IEEE 802.16e power saving mechanism[END_REF].

Similarly we proceed to the second order conditions to determine if b yields minimum cost. The second derivative function of the cost is

The sign of V (λ) depends on the value of z 1 (b

The following can be derived exp(-λ I(q) b) . Then (12) can be rewritten

In particular, g m I(q) (q, b) = q I(q) q I(q) + j>I(q) q j α m j .

Since λ i ≤ λ j for I(q) < i < j, then α j < α i ≤ α I(q)+1 ≤ α I(q) = 1. Hence

1 -q I(q) q I(q) .

We then have that lim m→∞ j>I(q) g m j (q, b) = 0, which implies the lemma.

APPENDIX C PROOF OF PROPOSITION III.3

Proof : By the bounded convergence theorem,

which is a constant. Hence by the monotone convergence of V k to V , the limit V := lim t→∞ V (t) exists and satisfies the limit dynamic programming (DP) V = min b L V . This DP corresponds to an MDP that has a single state and thus there exists an optimal constant deterministic policy that takes always the same b, which we denote b. This gives

Any other stationary (constant) deterministic policy b for the limit DP gives a larger value

This establishes (i).

In part (ii), the last inequality is strict for all b = b. Since the limit DP is obtained from the original one by considering large t, it follows that for all t large enough, b will give a strictly lower value of c(t, b) + P (τ t > b)V (t + b) than any other value of b. Thus by part (iii) of the previous theorem, b is optimal at all t large enough.

APPENDIX D PROOF OF PROPOSITION IV.1

Proof : For convenience, we introduce

The first and second derivative functions of V c (b) are, respectively

To study the sign of V c (b), we need to evaluate the functions Proof : We prove Proposition IV.4 by contradiction. We assume that there exists an optimal control µ µ µ = (b 1 , b 2 , . . .) which does not depend on q = (q 1 , . . . , q n ). Therefore, the coefficients of the probabilities {q i } i=1,...,n in (29) must all be null when µ µ µ = µ µ µ . In other words, we must have for i = 1, . . . , n and j

Subtracting, for a given i, the expression for j from that for j -1, we get after simplification for j ∈ IN * . For a given j, the above equality holds only when b j = 0, i.e., if there were no jth sleep period. Given that (34) must hold for j ∈ IN * , then all sleep periods need to be null. However, on the other hand, replacing b j = 0 in (33) yields b j+1 = -E L /η < 0, which is absurd. Equations (33) and (34) contradict each other. Therefore, the starting hypothesis is wrong and the optimal control must depend on q = (q 1 , . . . , q n ).


Sangnam Nam

Michael E Davies

Michael Elad

Rémi Gribonval

COSPARSE ANALYSIS MODELING

Keywords: Sparse Representation, Inverse Problems, Algorithms, Cosparse Analysis Model

ABSTRACT

A ubiquitous problem that has found many applications, from signal processing to machine learning, is to estimate a highdimensional vector x 0 ∈ R d from a set of incomplete linear observations y = Mx 0 ∈ R m . This is an ill-posed problem which admits infinitely many solutions, hence solving it is hopeless unless we can use additional prior knowledge on x 0 .

The assumption that x 0 admits a sparse representation z 0 in some synthesis dictionary D is known to be of significant help, and it is now well understood that under incoherence assumptions on the matrix MD, one can recover vectors x 0 with sufficiently sparse representations by solving the optimization problem:

xS := Dẑ; ẑ := arg min z z τ subject to y = MDz (1) for 0 ≤ τ ≤ 1.
An alternative to (1) which has been used successfully in practice is to consider the analysis ℓ τ -optimization:

xA := arg min x Ωx τ subject to y = Mx, (2)
where Ω : R d → R p is an analysis operator. Typically the dimensions are m ≤ d ≤ p, n.

The focus of our work is the study of a data model that makes possible to identify a collection of signals x 0 that can be recovered via the optimization (2). Roughly speaking, in the case of (1), the signals x 0 that are sparse, in other words, satisfy the sparse synthesis model, can be recovered via [START_REF] Blumensath | Sampling theorems for signals from the union of finite-dimensional linear subspaces[END_REF]. In the sparse synthesis model, we consider the number of the non-zeros z 0 of the representation z of x 0 (meaning that x 0 = Dz), and we say that x 0 is sparse if there is a representation z 0 of x 0 with small z 0 0 . To the contrary, in the case of (2), we are more interested in the number of the zeros p -Ωx 0 0 of the representation Ωx 0 of x 0 . We call the quantity ℓ = p -Ωx 0 0 the cosparsity of x 0 and say that x 0 is cosparse, or it satisfies cosparse analysis model, if ℓ is large.

For the cosparse analysis model, we have the following uniqueness result: Proposition 1. Let Ω be an analysis operator in general position. Then, for almost all M (with respect to the Lebesgue measure), a necessary and sufficient condition for (2) with τ = 0 to have a unique minimum is

m ≥ 2(d -ℓ). (3)
The proposition characterizes the collection of signals that can be recovered from (2) for the generic case. We also observe that by comparing with the uniqueness result for the sparse synthesis model, again in generic cases, dℓ is playing the role of the sparsity k = z 0 0 .

In the sparse synthesis model, armed with the fact that x 0 has a sparse representation, one may try to recover/approximate x 0 by greedily selecting atoms from MD and matching the observation y. The Orthogonal Matching Pursuit (OMP) is an example of such approachs. Similarly, we can consider a greedy algorithm as an alternative to (2) in the cosparse analysis model. As such an algorithm, we propose the Greedy Analysis Pursuit (GAP). In this algorithm, contrary to the greedy algorithms for the synthesis model, we try to identify the rows of Ω that correspond to the zeros of Ωx 0 . Moreover, again contrary to the typical greedy approach, GAP greedily-perhaps, generouslyremoves a row that is likely not to correspond the zeros from a collection of candidate rows that may do. This way, instead of building the support of z 0 by growing the size of the support as is done in, for example, OMP, we are carving out unwanted rows in order to obtain the correct cosupport of x 0 , i.e., the set of the indices that correspond to the zeros of Ωx 0 .

Finally, we run a synthetic experiment to demonstrate the effectiveness of the proposed algorith, GAP. Interestingly, we observe from the phase transition diagrams obtained from the experiment that GAP performs better than the analysis ℓ 1minimization.

The authors acknowledge the support by the European Community's FP7-FET program, SMALL project, under grant agreement no. 225913.


Anisoara Nica
email: anica@sybase.com

Fabian M Suchanek
email: fabian@suchanek.name

Aparna S Varde
email: vardea@montclair.edu

Emerging multidisciplinary research across database management systems

The database community is exploring more and more multidisciplinary avenues: Data semantics overlaps with ontology management; reasoning tasks venture into the domain of artificial intelligence; and data stream management and information retrieval shake hands, e.g., when processing Web click-streams. These new research avenues become evident, for example, in the topics that doctoral students choose for their dissertations. This paper surveys the emerging multidisciplinary research by doctoral students in database systems and related areas. It is based on the PIKM 2010, which is the 3 rd Ph.D. workshop at the International Conference on Information and Knowledge Management (CIKM). The topics addressed include ontology development, data streams, natural language processing, medical databases, green energy, cloud computing, and exploratory search. In addition to core ideas from the workshop, we list some open research questions in these multidisciplinary areas.

SURVEY OF TOPICS

Our survey groups the topics of the workshop into six research domains. We start with two core areas of database research, data mining and stream processing. We proceed to the sister domain of database management, Information Retrieval, before venturing into Information Extraction and the relatively new area of Privacy and Trust. We conclude with an application-driven domain, data warehouse management. We shed light on new research proposals in each of these domains, as well as on open issues.

Data mining

Data mining, the science of discovering meaningful knowledge in data, has always been a core area of database research. Nowadays, with the advent of large semantic knowledge bases, the area faces new challenges, for example with the task of integrating and aligning ontologies. The keynote of our workshop, Leveraging Logical and Statistical Inference in Ontology Alignment [START_REF] Miller | Leveraging Logical and Statistical Inference in Ontology Alignment, Keynote Talk In PIKM[END_REF] by Professor Renée J. Miller from the University of Toronto, gave an overview on the work done in this area. It also presented a new approach, "Integrated Learning In Alignment of Data and Schema" (ILIADS), which combines data matching and logical reasoning to achieve better matching of ontologies. Professor Miller ended her talk with advice for graduate students based on her own experience -both as a student and as a graduate adviser.

Another problem in the area of data mining is frequent subgraph mining. Garcia et al. [START_REF] Garcia | Efficient algorithms based on relational queries to mine frequent graphs[END_REF] study this problem with techniques available inside a database management system. Three fundamental research problems under a database approach are discussed: efficient graph storage and indexing, searching for frequent subgraphs and finding subgraph isomorphism using SQL. The solutions toward these problems are outlined, together with the preliminary experimental validation, focusing on query optimizations and time complexity.

Park et al. [START_REF] Park | Probabilistic ranking for relational databases based on correlations[END_REF] research the issue of finding statistical correlations among pairs of attribute values in relational database systems. By extending the Bayesian network models the authors provide a probabilistic ranking function based on a limited assumption of value independence. Experimental results show that the proposed model improves the retrieval effectiveness on real datasets and has a reasonable query processing time compared to previous related work.

Discussions with the speakers at the workshop pointed to open research avenues in the area of data mining in general. One such avenue, inspired by the keynote talk, is investigating the usefulness of data mining in the Semantic Web: Data can be mined from the Semantic Web (for tasks such as summarization or alignment) as well as for the Semantic Web (with the purpose of adding new knowledge to an ontology). The interplay of these two directions appears still largely unexplored.

Stream processing

As more and more data (such as sensor data) becomes available in the form of continuous streams, new avenues of research open up. Amiguet et al. [START_REF] Amiguet | Annotations: Dynamic semantics in stream processing[END_REF], for example, address the issue of semantic changes (annotations) in the stream data processing of sensor networks. The propagation of annotations through the workflow, as part of the data processing, raises interesting research questions related to how the propagation depends on the structural and temporal contributions, and on the annotation significance. The work shows its practical viability through a case study from a climate forecasting application that processes temperature sensor data. This paper won the best paper award in the PIKM 2010 workshop.

Another problem in stream processing is the adaptation of the system to different utilizations. Farag et al. [START_REF] Farag | Adaptive query processing in data stream management systems under limited memory resources[END_REF] propose new algorithms for providing good data stream system performance during periods of peak load and periods of delays. The "External Memory Sliding Window Join" (EM-SWJoin) algorithm utilizes external memory data structures to adapt to the variable data arrival rates while keeping disk access latency at minimum. The "ADaptive Execution of DAta Streams" (ADEDAS) algorithm guarantees ordered release of output results to the user/application while controlling the impact of delays over stream processing. Thus, it addresses the problem of releasing output results in an increasing order of timestamp when the input data items arrive out-of order. The authors exemplify their approach through a system that monitors online stocks.

In some scenarios, several data streams come together. Huq et al. [START_REF] Huq | Identifying the challenges for optimizing the process to achieve reproducible results in E-science applications[END_REF] discuss how different data streams can be coordinated, how storage space can be optimized and how the database state can be kept consistent in a distributed scenario. The main application the authors have in mind is sensor-based experiments, for example based on motion sensors. This last talk brought up the idea to investigate column-oriented data representations in data stream environments. Such a representation will require stronger coordination (horizontally in addition to vertically), but might potentially improve output efficiency and overall system performance.

Information retrieval

Recent years have seen an opening up of the border between the database research and information retrieval. Storing data and querying data go hand in hand, and this applies to both structured data and unstructured data. In many scenarios, queries can be classified into "lookup searches" and "exploratory searches". In lookup searches, users "look up" details on topics known to them; in exploratory searchers they "explore" new information. Mirizzi et al. [START_REF] Mirizzi | From exploratory search to web search and back[END_REF] propose to combine these two concepts. They present a Web-based tool called "Lookup Discover Explore" (LED) that improves lookup search by adding exploration capabilities. LED supports a lookup step, an exploratory step and a meta search process. Given a keyword query, their system can display DBpedia resources with a graph explorer, a ranker and a context analyzer. One of the contributions of their work is a novel approach to browsing by exploiting the Semantic Web.

Di Buccio et al. [START_REF] Buccio | Toward the design of a methodology to predict relevance through multiple sources of evidence[END_REF] address the related problem of querying a document collection with short textual queries. Newer systems use relevance feedback from different sources of evidence. In this paper, the authors propose a uniform model for these evidence sources.

One area of Information Retrieval that is gaining more and more attention lately is the exploitation of the deep Web. Tjin-Kam-Jet [START_REF] Tjin-Kam-Jet | Research proposal for distributed deep web search[END_REF] proposes to address this challenge in a distributed environment. Given the fact that the deep Web is up to two orders of magnitude larger than the surface Web, they argue that distribution might be the key to scalability. This work proposes to automatically convert free-text queries to structured queries for complex web forms in order to make the deep web more easily searchable. Challenges include developing a formal query description syntax, translating queries with correct interpretation, bridging the gap between user expectations and system capabilities, adapting query description for resource selection, ranking top k resources, merging results from resources to maximize precision, recall and suggestion ranking for users with respect to resources. He aims to evaluate this solution with a prototype system and user studies, criteria being processing time and user satisfaction.

Discussions following the talk [START_REF] Tjin-Kam-Jet | Research proposal for distributed deep web search[END_REF] brought up the idea of studying distributed deep web searches in the context of handheld mobile devices. As mobile devices become practically ubiquitous (and reasonably powerful, too), it might become possible to utilize their capacities for distributed query processing.

Information extraction

Information extraction, in its widest sense, is the extraction of structured data from unstructured data. One domain where large corpora of unstructured text would particularly benefit from information extraction is the medical domain. Raghavan et al. [START_REF] Raghavan | Leveraging natural language processing of clinical narratives for phenotype modeling[END_REF] are concerned with extracting information from medical reports. A medical report is a natural language description of diagnoses, treatments or medications, together with structured information about the patient. The goal is to extract a chronology of events from the reports. Such chronologies can then be used to review a patient's history or to gather statistical data about the effectiveness or consequences of medical treatments. The task is challenging, because the reports use medical jargon and colloquial temporal expressions ("two days ago"). The paper conducts two initial case studies: In the first, machine learning on medical reports is used to determine whether patients qualify for Leukemia trials. In the second, a bio-specimen repository is augmented with data from medical reports. This additional data facilitates the classification of tissue probes and also information retrieval on the specimen database.

Kliegr [START_REF] Kliegr | Entity classification by bag of Wikipedia articles[END_REF] discusses the problem of noun phrase classification: Given a noun phrase (such as an image caption) and given a set of classes (such as "Nature" or "City"), the task is to assign a class to the noun phrase. This problem is challenging, because the classes are userdefined and the noun phrases do not necessarily have context. The paper proposes to map the noun phrase to a weighted set of related Wikipedia articles (a "bag of articles", BOA). Likewise, each class is mapped to a BOA. Then, the classification problem is reduced to determining the similarity between the noun phrase BOA and the class BOAs. This last talk [START_REF] Kliegr | Entity classification by bag of Wikipedia articles[END_REF] has shown us that the possibilities that Wikipedia offers for information extraction are not yet fully exploited. The first talk [START_REF] Raghavan | Leveraging natural language processing of clinical narratives for phenotype modeling[END_REF] has pointed us to an area where Information Extraction (and possibly data mining) could find attractive applications: the medical domain.

Privacy and Trust

As more and more data is being produced, stored and made public, issues such as security, trust and privacy gain more and more attention. Consider for example pervasive health care systems. These are systems that monitor medical indicators on the patient and send their data to a medical center. These systems can greatly increase efficiency and safety, but come with the problem of data security. Acharya et al. [START_REF] Acharya | A secure pervasive health care system using location dependent unicast key generation scheme[END_REF] address the possible security threats in pervasive health care systems. One particular security loophole is the need to exchange encryption keys. The paper proposes a communication scheme that eliminates the need to broadcast encryption keys.

Security and trust are even more obvious issues when it comes to sharing data in cloud computing systems. Driven by this insight, Thorpe [START_REF] Thorpe | Modeling a trust cloud context[END_REF] develops a trust paradigm for the cloud. The paper considers interactions, reputation, knowledge and experience with respect to the cloud. Concepts such as user trust, cloud trust, cloud trust peer and cloud distrust are defined and an algorithm is proposed for a trust cloud context graph. The algorithm takes all the variables into account that are relevant to the cloud, i.e., machines, storage components and connected nodes. This encourages work on a contextneutral autonomous cloud monitor agent.

Just as [START_REF] Raghavan | Leveraging natural language processing of clinical narratives for phenotype modeling[END_REF], the authors of [START_REF] Acharya | A secure pervasive health care system using location dependent unicast key generation scheme[END_REF] target the medical domain. We take this as an indication that this domain can attract research from different areas of computer science, including security, privacy, data management, information extraction and systems research.

Workflow and Management

Research in databases can also touch quite practical issues such as the management of data centers. As data centers grow larger and larger and ever more powerful, pragmatic concerns such as heat management and environmental compatibility arise. Pawlish et al. [START_REF] Pawlish | A decision support system for green data centers[END_REF], for example, are concerned with the environment-friendly management of data centers. The ultimate aim is to provide the data center manager with a tool that can help decide management questions, such as whether to buy new hardware and what hardware, in order to minimize the environmental impact of the facility. For this purpose, the paper first explains what data is necessary to support such decisions. These include, e.g., data on energy use, humidity, acoustic levels, and the carbon footprint of the center. For proof of concept, the authors have collected such data for one data center. Then, the paper proposes to build decision trees on top of these data and to use case based reasoning in order to determine economically sensible management steps. The paper outlines this framework supported by some real world examples.

Another issue in data warehousing environments is the problem of consistent data quality. As warehousing environments are often dynamically changing the quality of various resources and also the users' quality requirements, there is a need to capture quality changes on-the-fly and also provide automated quality notifications back to end users. Therefore, Li et al. [START_REF] Li | Quality factory and quality notification service in data warehouse[END_REF] propose an extended data warehousing systems architecture that incorporates and extends the concepts of the "Quality Factory" (QF) and the "Quality Notification Service" (QNS), and adopts the "Data Warehouse Quality" (DWQ) methodology to provide both subjective and objective quality assessments of the end-users' quality requirements.

Apart from quality, efficiency of processes is also almost always an issue. Naseri et al. [START_REF] Naseri | A multi-functional architecture addressing workflow and service challenges using provenance data[END_REF] are concerned with optimizing workflow management. They propose to systematically store, analyze and mine data about successful workflow executions in order to optimize workflow composition, workflow selection and workflow refinement.

Discussions during the workshop were particularly attracted to the concept of managing data warehouses. This area touches not just several domains of computer science (such as storage, querying, and quality estimation), but also other domains such as economics, the environmental sciences and the legal domain. The talks in this session have raised awareness for the practical impacts of our ever-growing amounts of data, their quality and their storage.

CONCLUSIONS

This paper presents a short survey of emerging research across database systems and related areas. It focused on the work that doctoral students presented at the PIKM workshop in ACM CIKM 2010. From a research point of view, the work is spread over areas as diverse as information extraction and workflow management, stream processing and security. From an application point of view, the work is concerned with cloud computing systems, sensor networks, practical aspects of data warehouse management and Web search. The medical domain with its applications has also attracted particular interest. The new research proposals as well as discussions with the students have illuminated some of the new research avenues in the domain of databases and beyond.

ACKNOWLEDGMENTS

We sincerely thank the CIKM 2010 organizers for their help and support in organizing the Ph.D. workshop PIKM. In particular we thank the General Chair, Jimmy Huang and the Workshops Chair, Mounia Lalmas, for their cooperation. We also express our sincere gratitude towards the 24 PC members of PIKM, spread over 12 countries across the globe. They comprised well-known experts from industry and academia and their exhaustive reviews helped to make this workshop a fruitful and enriching experience. All of this helped set the stage for writing this article.

* The work by Fabian Suchanek has been partially funded by the European Research Council under the European Community's Seventh Framework Programme (FP7/2007-2013) / ERC grant Webdam, agreement 226513. http://webdam.inria.fr/