Presentation

Offline Delay-Optimal Transmission for Energy Harvesting Nodes

Yirui Cong and Xiangyun Zhou Research School of Engineering, The Australian National University, Canberra, ACT 0200, Australia

Emails: {yirui.cong, xiangyun.zhou}@anu.edu.au

Abstract—This paper investigates the offline packet-delay- minimization problem for an energy harvesting transmitter. To overcome the non-convexity of the problem, we propose a C2- diffeomorphic transformation and provide the necessary and sufficient condition for the transformed problem to a standard convex optimization problem. Based on this condition, a simple choice of the transformation is determined which allows an analytically tractable solution of the original non-convex problem to be easily obtained once the transformed convex problem is solved. We further study the structure of the optimal transmission policy in a special case and find it to follow a weighted-directional- water-filling structure. In particular, the optimal policy tends to allocate more power in earlier time slots and less power in later time slots. Our analytical insight is verified by simulation results.

Index Terms—Energy harvesting, offline transmission policy, packet delay minimization, weighted-directional-water-filling.

I. INTRODUCTION

A. Motivation and Related Work

Energy harvesting is recognized as a key enabling tech- nology for self-sustainable communication networks. It also brings in significant and necessary changes in the design of the communication protocol when energy harvesting becomes the main or sole source of energy supply for the communi- cation nodes [1]–[3]. By focusing on the design of an energy harvesting transmitter, the existing studies can be categorized into offline and online scenarios. For offline scenarios, all future information (such as the energy arrival process, data arrival process and channel fading process) is assumed to be predictable or completely deterministic. Hence, the trans- mission policy is designed offline by using the available knowledge about the future. For online scenarios, although the exact future behaviors of the energy arrival, data arrival and channel fading processes are not known, the existing literature have considered different levels of statistical knowledge: the statistics of the processes in the future are exactly known (e.g., [4]), partly known (e.g., [5]) or completely unknown (e.g., [6]).

The importance of studying the offline design for energy harvesting transmitters is two-fold [7]–[9]: (i) The offline design tells the fundamental performance limit of an energy harvesting communication system. It serves as a benchmark for any online algorithm. Methods such as competitive anal- ysis [7] can be used to derive and analyze online algorithms once the performance of the offline design is known. (ii) The offline solution often helps one to gain insights on the design problem and the behavior of the optimal transmission policy,

which inspire possible online design solutions (e.g., Section VI.B in [8] and Section VII in [9]). As a result, a significant effort has been made into the study of offline designs in the past few years.

The objective of energy harvesting transmission design has been defined from a range of perspectives, includ- ing throughput maximization (e.g., [5]–[9]), remaining en- ergy maximization (e.g., [9]), completion time minimiza- tion (e.g., [6], [8]–[12]), and packet delay minimization [4], [13], [14]. In particular, efficient offline designs have been found for the throughput-maximization, remaining- energy-maximization and completion-time-minimization prob- lems [8]–[10]. However, effective solutions to the offline packet-delay-minimization problem are still yet to be found. A very recent study in [14] considered the packet-delay- minimization problem in a non-fading channel and obtained a deep insight of the solution structure given through the KKT conditions. However, the optimal solution was derived for the dual problem rather than the original problem. Since the original problem is non-convex, there is a duality gap [15] between the original and dual problems.

Another interesting issue is the relationship among the pa- cket-delay-minimization, completion-time-minimization, and throughput-maximization problems. For the last two problems, they are linked through the maximum departure curve (see Section V in [8]). However, it is unclear whether the first problem has any correlation with the last two problems. Intuitively, the first two problems are related: the quicker the transmission is completed, the smaller the packet delay is. A similar observation was also made in the literature (e.g., [9], [16]). Then, through the maximum departure curve, all these three problems appear to be highly related. Nevertheless, there has not been any analytical studied on the extent to which the three problems are related and, more importantly, whether the optimal offline transmission designs for the three problems have the similar behaviors.

B. Our Contribution

In this work, we tackle the aforementioned challenge of finding an effective solution to the offline packet-delay- minimization problem in a general fading channel. We con- sider a time-slotted system and use the average data queue length to measure delay, which is a commonly adopted delay metric in the literature [4], [13]. Although the formulated delay-minimization problem is non-convex, we are able to

978-1-5090-1328-9/16/$31.00 ©2016 IEEE

transform it into a single convex optimization problem, which can be solved very efficiently.

In order to obtain insights into the behavior of the optimal offline delay-minimizing transmission policy, we focus on a special case where the battery energy is insufficient to clear the data queue in all time slots. In this case, we analytically show that the optimal transmission policy has a weighted- directional-water-filling structure for the power allocation. In particular, the optimal policy tends to allocate more power in earlier time slots and less power in later time slots. This result is further verified by simulations in more general cases.

The insights obtained from the optimal transmission policy also allow us to investigate the relationship and difference among the delay-minimization problem studied in this work, the completion-time minimization problem in [10], and the throughput-maximization problem in [8]. Surprisingly, the optimal offline solution to the delay-minimization problem is found to be fundamentally different: the delay-minimizing solution tends to reduce the transmit power over time, while the completion-time-minimizing and throughput-maximizing solutions trend to increase the transmit power over time.

C. Paper Organization and Notation

The system model and problem description are given in Section II and Section III, respectively. In Section IV, the delay-minimization problem is efficiently solved and the struc- ture of the optimal solution is studied. Simulation results are presented in Section V to corroborate our analysis. Finally, the concluding remarks are given in Section VI.

II. SYSTEM MODEL

We consider a point-to-point communication system with an energy harvesting transmitter (see Fig. 1). The time is slotted, and t ∈ {1, . . . , T} =: T stands for the tth time slot, where T ∈ Z+ is the total number of slots. For each time slot, the battery energy of the transmitter is Et ∈ R+, and is determined by the battery energy equation:

Et = Et−1 + Ht − pt, t ∈ T , (1)

where Ht ∈ R+ is the harvested energy and pt ∈ R+ is the transmit power. Note that E0 ∈ R+ represents the initial battery energy. The data queue length of the transmitter is Qt ∈ R+, determined by the data queue equation:

Qt = Qt−1 + Dt − r(pt, gt), t ∈ T , (2)

where Dt ∈ R+ is the amount of data arrived and r(pt, gt) is the rate function, which is only dependent on the transmit power pt and the power gain of the communication channel gt ∈ R+. We label r(pt, gt) ≡ rgt(pt) and assume that rgt : R+ → R+ is strictly increasing and concave, and has a continuous second derivative, e.g., for fading channel with Gaussian white noise rgt(pt) = log(1+gtpt). Also, Q0 ∈ R+ is the initial data queue length.

Note that Et and Qt for any t ∈ T can be totally determined by (1), (2), E0 and Q0. Since we consider an offline scenario, the energy arrival Ht, data arrival Dt, and channel gain gt

t H

t D

t E

t Q

, t t

r p g

Fig. 1. The point-to-point communication system with an energy harvesting transmitter.

are known in advance. This completes the description of the system model.

III. PROBLEM DESCRIPTION: MINIMIZING THE AVERAGE DATA QUEUE LENGTH

In this paper, we use the average data queue length as the delay metric, which is commonly adopted in the literature [4], [13]. The average data queue length L is given by

L = 1

T

T∑ t=1

Qt. (3)

The average-data-queue-minimization problem is to find pt to minimize L in (3) with constraints from the battery energy equation (1) and the data queue length equation (2). Since (3) does not explicitly contain pt, we rewrite L as

1

T

T∑ t=1

Qt (a) =

1

T

{ TQ0 +

T∑ t=1

t∑ i=1

[Di − rgi(pi)]

}

= Q0 + 1

T

T∑ t=1

(T + 1 − t) [Dt − rgt(pt)] ,

(4)

where (a) follows from

Qt = Q0 +

t∑ i=1

[Di − rgi(pi)] , t ∈ T . (5)

We also rewrite (1) and (2) to obtain the battery energy and data queue constraints for the optimization problem. More specifically, the battery energy equation (1) can be rewritten as a series of inequalities, called the battery energy constraints

Et = E0 + t∑

i=1

(Hi − pi) ≥ 0, t ∈ T . (6)

Similarly, we can get the data queue constraints from the data queue equation as

Qt = Q0 +

t∑ i=1

(Di − rgi(pi)) ≥ 0, t ∈ T . (7)

Also note that pt should be non-negative for t ∈ T . To sum up, we can write the offline average-data-queue-minimization problem into an explicit form whose optimization variables are pt (t ∈ T ), which is given as follows:

Problem 1 (Average-Data-Queue-Minimization Problem). The average-data-queue-minimization problem is

minimize pt, t∈T

Q0 + 1 T

∑T t=1 (T + 1 − t) [Dt − rgt(pt)]

subject to ∑t

i=1 pi ≤ E0 + ∑t

i=1 Hi, t ∈ T ,∑t i=1 rgi(pi) ≤ Q0 +

∑t i=1 Di, t ∈ T ,

pt ≥ 0, t ∈ T , (8)

where the optimal solution and optimal objective are labelled as p∗t (t ∈ T ) and L∗, respectively.

Remark 1. It should be noted that Problem 1 is not a convex optimization problem, since the data queue constraints correspond to the intersection of non-convex regions w.r.t. pt. Nevertheless, in Section IV-A, we will show that Problem 1 can be converted to a standard convex optimization problem with transformation on the optimization variables.

IV. OPTIMAL SOLUTION FOR THE AVERAGE-DATA-QUEUE-MINIMIZATION PROBLEM

This section is divided into two parts. In Section IV-A, we discuss how to efficiently solve Problem 1 by transforming it into a standard convex optimization problem. In Section IV-B, we provide insights into the structure of the optimal solution.

A. Solving the Average-Data-Queue-Minimization Problem

In this subsection, we discuss how to convert Problem 1 into a standard convex optimization problem such that it can be solved efficiently.

Let map φt : R+ → R+ (t ∈ T ) be C2-diffeomorphic1. With the transformation pt = φt(qt), Problem 1 can be rewritten as

minimize qt, t∈T

Q0 + 1 T

∑T t=1 (T + 1 − t) [Dt − rgt(φt(qt))]

subject to ∑t

i=1 φi(qi) ≤ E0 + ∑t

i=1 Hi, t ∈ T ,∑t i=1 rgi(φi(qi)) ≤ Q0 +

∑t i=1 Di, t ∈ T ,

φt(qt) ≥ 0, t ∈ T , (9)

where rgt(φt(qt)) is twice continuously differentiable, since both rgt and φt are twice continuously differentiable.

The following theorem gives the necessary and sufficient condition for guaranteeing the convexity of (9).

Theorem 1 (Necessary and Sufficient Condition for Convexity of Transformed Problem). Problem (9) is a standard convex optimization problem if and only if ∀t ∈ T ,

φt(qt) = r −1 gt

(atqt + bt), (10)

where at ∈ R+ and bt ∈ R.

Proof: The proof is divided into three steps. In the first step, we show that the condition φt(qt) ≥ 0 is equivalent to qt ≥ 0 for all t ∈ T . In the second step, we prove the necessary and sufficient condition for the convexity of Problem (9) is that

1For each t ∈ T , φt is bijective and twice continuously differentiable, and the inverse φ−1t is also twice continuously differentiable.

the map φt is convex and the composition rgt ◦ φt is affine. In the third step, we show that (10) holds.

i) Since, for each t ∈ T , φt is bijective from R+ to R+, we can derive that if pt = φt(qt) ∈ R+, then qt ∈ R+, vice versa. Thus, the domains of φt(qt) ≥ 0 and qt ≥ 0 are totally the same, and Problem (9) is equivalent to the following problem

minimize qt, t∈T

Q0 + 1 T

∑T t=1 (T + 1 − t) [Dt − rgt(φt(qt))]

subject to ∑t

i=1 φi(qi) ≤ E0 + ∑t

i=1 Hi, t ∈ T ,∑t i=1 rgi(φi(qi)) ≤ Q0 +

∑t i=1 Di, t ∈ T ,

qt ≥ 0, t ∈ T . (11)

ii) Now, we prove the necessary and sufficient condition for the convexity of Problem (11) instead of Problem (9).

Necessity. If Problem (11) is a standard convex optimiza- tion problem, then the objective function and the inequality constraints are convex (see Chapter 4.2 in [15]). Firstly, we focus on the battery energy constraints (the first row of the constraints in (11)). For t = 1, we have φ1(q1) ≤ E0 + H1 and this means that φ1(q1) is convex w.r.t. q1. For t = 2, we have φ1(q1)+φ2(q2) is convex w.r.t. q1 and q2, which implies φ2(q2) is convex w.r.t. q2, since φ1(q1) is convex w.r.t. q1. Likewise, we can derive that φt is convex for all t ∈ T .

Similarly, the data queue constraints (the second row of the constraints in (11)) tell that rgt ◦ φt is also convex for all t ∈ T .

Furthermore, with convex rgt ◦φt, we see that the objective function is concave, which implies it is affine (both convex and concave), so does the map rgt ◦ φt. This completes the necessity.

Sufficiency. If φt is convex and rgt ◦ φt is affine (affinity also means convexity) for t ∈ T , then the objective function as well as all the inequality constraints are convex. Therefore, Problem (11) is a convex optimization problem.

iii) Since the composition rgt ◦ φt is affine and invertible, we have rgt(φt(qt)) = atqt + bt, where at ∈ R \ {0} and bt ∈ R. This means φt(qt) = r−1gt (atqt + bt). Note that r

−1 gt

is convex, and to make φt convex, at should be greater than 0. To sum up, condition (10) is established.

Theorem 1 gives an important guideline for selecting the transformation φt. With this guideline, we further choose at = 1 and bt = 0 for all t ∈ T such that the transformation is φt = r−1gt , which can largely reduce the complexity of the transformed problem. Therefore, we obtain the following transformed problem by applying the transformation pt = r−1gt (qt) for Problem 1.

Problem 2 (Transformed Problem). With pt = r−1gt (qt) for all t ∈ T , Problem 1 is transformed into the following convex optimization problem

minimize qt, t∈T

Q0 + 1 T

∑T t=1 (T + 1 − t) (Dt − qt)

subject to ∑t

i=1 r −1 gi

(qi) ≤ E0 + ∑t

i=1 Hi, t ∈ T ,∑t i=1 qi ≤ Q0 +

∑t i=1 Di, t ∈ T ,

qt ≥ 0, t ∈ T , (12)

where the optimal solution is q∗t (t ∈ T ), but not necessarily unique2. The optimal objective is the same as that in Prob- lem 1, i.e., L∗.

Remark 2 (Solving the Original Problem with the Solution of the Transformed Problem). The optimal solution of Problem 1 can be derived in the following way

p∗t = r −1 gt

(q∗t ), t ∈ T , (13)

where q∗t is the optimal solution to Problem 2. This implies that we can use (13) to obtain the optimal solution of Prob- lem 1 after deriving the optimal solution of Problem 2. Since Problem 2 is convex, it can be solved efficiently (e.g., using the interior-point method [15]). Therefore, the optimal solution of Problem 1 can also be derived efficiently.

B. Discussions on the Structure of the Optimal Solution

In general, it is difficult to derive the structure of the optimal solution of Problem 2 by its KKT conditions. However, the KKT conditions can give insights into the structure of the optimal solution when Qt > 0 for all t ∈ T . Such a case happens when the transmitter does not have sufficient energy in the battery to completely clear the data queue in all time slots. In order to shed light on the structure of the delay- minimization transmission policy, we study this special case using the original problem (Problem 1) rather than Problem 2.

In this special case, since Qt > 0 for all t ∈ T , the data queue constraints in Problem 1 can be removed. We further assume the channel is a fading channel with Gaussian white noise, and the rate function is rgt(pt) = log(1 + gtpt), which achieves the channel capacity. Noting that to minimize Q0 + 1 T

∑T t=1(T + 1 − t)[Dt − rgt(pt)] is equivalent to maximize∑T

t=1(T + 1 − t)rgt(pt), we can rewrite Problem 1 as the following problem.

Problem 3 (Weighted-Throughput-Maximization Problem).

maximize pt, t∈T

∑T t=1 (T + 1 − t) log(1 + gtpt)

subject to ∑t

i=1 pi ≤ E0 + ∑t

i=1 Hi, t ∈ T , pt ≥ 0, t ∈ T .

(14)

Interestingly, Problem 3 maximizes the throughput over all time slots with a weighting factor (T + 1 − t) applied to each time slot. It is a convex optimization problem and has a unique maximizer, because log(1 + gtpt) is strictly concave for all t ∈ T and the constraints are all affine. We claim that the solution to Problem 3 has a weighted-directional-water- filling structure3, which is an extension of the directional- water-filling structure in [8].

2Since the objective of Problem 2 is not strictly convex, we cannot ensure that it always has a unique global minimizer under any given Ht, Dt, E0 and Q0. However, since this problem is convex, we can still get at least one global minimizer using an efficient method, e.g., interior-point method.

3Note that the mathematical form of Problem 3 is similar to (38a) and (38b) in [17], where the weights are preferences to broadcast channels. However, our solution has a more explanation (see Fig. 2).

Applying KKT conditions to Problem 1, we can derive the structure of the optimal power as

p∗t =

( T + 1 − t∑T i=t λi − ηt

− 1

gt

)+ , (15)

where λt and ηt correspond to the battery energy constraints (the first row of the constraints in (14)) and pt ≥ 0. Defining

νt = 1∑T

i=t λi − ηt , (16)

we have the following theorem.

Theorem 2 (Nondecreasing Property of Water Levels). Let the time set T0 contains those t corresponding to p∗t = 0, i.e., T0 = {t : p∗t = 0, t ∈ T }. We have νt+1 ≥ νt for all t ∈ {1, . . . , T −1}\T0. Furthermore, ∀t ∈ {1, . . . , T −1}\T0, if the battery energy constraint (the first row of the constraints in (14)) is satisfied without equality, then νt+1 = νt.

Proof: When p∗t > 0, it follows the complementary slackness (see Chapter 5.5.2 in [15]) that ηt = 0, and νt becomes νt = 1/

∑T i=t λi. Observing that λt ≥ 0, we

have νt+1 ≥ νt for all t ∈ {1, . . . , T − 1}\T0. Moreover, ∀t ∈ {1, . . . , T − 1}\T0, if the battery energy constraint (the first row of the constraints in (14)) is satisfied without equality, then λt = 0, which implies νt+1 = νt.

Theorem 2 tells that the optimal solution p∗t has the weighted-directional-water-filling structure, and νt is exactly the water level in the tth time slot. The water depth dt is

dt := p∗t

T + 1 − t = (νt − δt)

+ , t ∈ T (17)

where δt = 1/[(T + 1 − t)gt]. Therefore, the weighted- directional-water-filling algorithm can be derived, which is illustrated in Fig. 2.

In Fig. 2(a), the white blocks at the bottom are the ground with levels δt = 1/[(T +1 − t)gt], corresponding to the effect of the channel gain. The above dash lines complement the shape of the water tank, where the widths (T + 1 − t) are decreasing linearly with t. The walls between any adjacent time slots are right permeable [8], which means the water can flow to the right if the water in the left slot has a higher level, but the water cannot flow back to the left in all cases. In Fig. 2(b), the shaded blocks are water, which is determined by E0 as well as Ht arriving in each time slot. In this particular example, the water depths in time slots 1, 4, and 5 are d′1 = (E0 + H1)/T , d

′ 4 = H4/T and d

′ 5 = H5/T ,

respectively. Thus, the water levels in these three time slots can be calculated by ν′t = δt + d

′ t. On the other hand, the

energy arrived is zero in time slots 2, 3, and 6, and hence, no water exists in those time slots. In Fig. 2(c), the water is filled across time slots, and the final water volume for each time slot is exactly the power allocation. The new water level, after using the weighted-directional-water-filling algorithm, is νt = δt +dt for all t ∈ T . In this example, time slots 1, 2 and 4 share a same water level, since the original water level ν′1 in slot 1 is higher than ν′2 and ν

′ 4, so is the water level in time

t

w 1T t

t

1 2 3 4 5 6

(a)

t

w

t d

t

1 2 3 4 5 6

(b)

t

w

t d

t

1 2 3 4 5 6

(c)

Fig. 2. An illustration of the weighted-directional-water-filling algorithm. The t-axis refers to the time slot, and the w-axis stands for the weight T + 1 − t. (a) The shape of the water tank and the levels of the ground. (b) The original water levels, which are determined by the initial battery energy and energy arrival process. (c) The new water levels after applying the weighted-directional-water-filling algorithm.

slots 5 and 6. However, there is no water pouring from time slot 5 to 4, even though ν′4 < ν

′ 5, because the walls are right

permeable. This completes the description of the weighted- directional-water-filling algorithm in this example.

Remark 3. From Fig. 2, we observe that the weight (T +1−t) is initially large and decreases as time goes by. As a result, the optimal solution of Problem 3 tends to allocate more transmit power in the earlier time slots, which implies the transmit power is more likely to decrease with t. Furthermore, if Ht = 0 for t ∈ {2, . . . , T} and gt ≡ 1 for t ∈ T , we can prove that the transmit power pt is linearly decreasing with t.

As mentioned in Section I-A, the delay-minimization prob- lem studied in this work was previously considered to be highly related to the completion-time-minimization problem, and the throughput-maximization problem. However, Re- mark 3 tells a fact that the completion-time-minimization and throughput-maximization problems are inherently different from the delay-minimization problem. This is because the allocated transmit power in the solutions to the completion- time-minimization and throughput-maximization problems (if the battery storage is infinite and the channel is non-fading) are increasing with time t (see [10] and Theorem 1 in [8]), while the optimal power allocation in the delay-minimization problem tends to decrease with t.

V. SIMULATION RESULTS

In this section, firstly, we numerically illustrate that the opti- mal solution to the delay-minimization problem is fundamen- tally different from that to the completion-time-minimization and throughput-maximization problems. Note that the simu- lations contain more cases than that in Section IV-B, e.g., not limited to the case that the transmitter has insufficient energy in the battery to clear the data queue. The Monte Carlo method is employed to investigate the behavior of the optimal solution to Problem 1, which can be efficiently solved by our results in Section IV-A. Secondly, we compare the packet delay between our delay-minimization algorithm and the throughput-maximization algorithm to stress the optimality

of our algorithm. To focus on the decreasing or increasing property of the

power allocation over time, we introduce a concept, named the inversion number. The inversion number for a sequence of power values (pt)t∈T is defined as

inv((pt)t∈T ) := # {(pt1, pt2) : t1 < t2 ∧ pt1 > pt2} , (18)

where # returns the cardinality of a finite set, and ∧ means the logical “and”. It can be observed that: if a sequence is non- decreasing, then the inversion number is 0; while, if a sequence is strictly decreasing, the inversion number is T(T + 1)/2. Thus, the larger the inversion number is, the more likely a sequence (pt)t∈T is decreasing with t.

The simulation parameters are given as follows. The number of time slots is T = 10, i.e., the simulations are done within the time horizon {1, . . . , 10}. The initial battery energy and the initial data queue length are E0 = 1 and Q0 = 1, respectively. We set the power gain of the channel as gt ≡ 1, with the rate function given by log(1 + gtpt), in order to compare with the power allocation solution to the completion- time-minimization problem derived in [10]. The energy arrival process Ht follows an independent and identically distributed (i.i.d.) uniform distribution, so does the data arrival process Dt. Additionally, the mean values E[Ht] and E[Dt] are set within {0, 0.5, . . . , 5} and {0, 1, 2}, respectively (see Fig. 3). Each point in Fig. 3 is obtained from averaging over 10, 000 simulation runs.

From Fig. 3, we have the following observations: For a fixed E[Dt], the average inversion number decreases with E[Ht]. More importantly, the case E[Ht] = 0 corresponds to a strictly decreasing sequence of power values, since the average inversion number is exactly T(T + 1)/2 = 45. Note that, in this case (E[Ht] = 0 means Ht ≡ 0), the decreasing property has been explained analytically in Remark 3. When E[Ht] goes large enough, the average inversion number for a fixed E[Dt] gradually converges to a constant. This is because, in every time slot, there is sufficient battery energy to clear the data queue with high probability, and hence, the sequence of power values is largely dependent on Dt, and independent

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 20

25

30

35

40

45

E[H t ]

A v e ra

g e I

n v e rs

io n N

u m

b e r

E[D t ] = 0

E[D t ] = 1

E[D t ] = 2

Fig. 3. Average inversion numbers.

of Ht. We can see that for E[Dt] ∈ {0, 1, 2}, the average inversion numbers converge to 31.8, 27.9, and 24.7, respec- tively, which are far from 0. According to the results in [10] and [8], the sequences of power values of the completion- time-minimization and the throughput-maximization solutions are non-decreasing, hence their inversion numbers are 0. This confirms that the optimal solution of the delay-minimization problem has a very different behavior from those of the completion-time-minimization and throughput-maximization problems.

Using the same simulation parameters but with the channel power gain gt following i.i.d. Nakagami-2 fad- ing, we compare our delay-minimization algorithm with the throughput-maximization algorithm (adopted from [8]). The results are shown in Fig. 4, and we can see that the delay-minimization algorithm performs much better, and the throughput-maximization algorithm does not give good de- lay performance. This result again confirms the fundamental difference between the delay-minimization and throughput- maximization problems.

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0

0.5

1

1.5

2

2.5

3

E[H t ]

A v e ra

g e D

a ta

Q u e u e L

e n g th

L

DM E[D t ] = 0

TM E[D t ] = 0

DM E[D t ] = 1

TM E[D t ] = 1

Fig. 4. Packet delay comparisons between the delay-minimization algorithm (labeled by DM) and the throughput-maximization algorithm (labeled as TM).

VI. CONCLUSION

The offline packet-delay-minimization problem for an en- ergy harvesting transmitter has been investigated in a time- slotted system. We have proposed an effective transforma- tion that converts the original non-convex problem into a convex problem, which then can be solved very efficiently. We have found that the optimal offline transmission policy of the packet-delay-minimization design is fundamentally dif- ferent from those of the completion-time-minimization and throughput-maximization designs reported in the literature. The former one tends to decrease the allocated power as time increases, while the latter two allocate more power as time increases.

REFERENCES [1] D. Gündüz, K. Stamatiou, N. Michelusi, and M. Zorzi, “Designing

intelligent energy harvesting communication systems,” IEEE Commun. Mag., vol. 52, no. 1, pp. 210–216, Jan. 2014.

[2] S. Ulukus, A. Yener, E. Erkip, O. Simeone, M. Zorzi, P. Grover, and K. Huang, “Energy harvesting wireless communications: A review of recent advances,” IEEE J. Sel. Areas Commun., vol. 33, no. 3, pp. 360– 381, Mar. 2015.

[3] O. Ozel, K. Tutuncuoglu, S. Ulukus, and A. Yener, “Fundamental limits of energy harvesting communications,” IEEE Commun. Mag., vol. 53, no. 4, pp. 126–132, Apr. 2015.

[4] V. Sharma, U. Mukherji, V. Joseph, and S. Gupta, “Optimal energy management policies for energy harvesting sensor nodes,” IEEE Trans. Wireless Commun., vol. 9, no. 4, pp. 1326–1336, Apr. 2010.

[5] P. Blasco, D. Gunduz, and M. Dohler, “A learning theoretic approach to energy harvesting communication system optimization,” IEEE Trans. Wireless Commun., vol. 12, no. 4, pp. 1872–1882, Apr. 2013.

[6] Y. Cong and X. Zhou, “Event-trigger based robust-optimal control for energy harvesting transmitter,” arXiv preprint arXiv:1508.00962, 2015.

[7] R. Vaze, R. Garg, and N. Pathak, “Dynamic power allocation for maximizing throughput in energy-harvesting communication system,” IEEE/ACM Trans. Netw., vol. 22, no. 5, pp. 1621–1630, Oct. 2014.

[8] O. Ozel, K. Tutuncuoglu, J. Yang, S. Ulukus, and A. Yener, “Transmis- sion with energy harvesting nodes in fading wireless channels: Optimal policies,” IEEE J. Sel. Areas Commun., vol. 29, no. 8, pp. 1732–1743, Sept. 2011.

[9] O. Orhan, D. Gunduz, and E. Erkip, “Energy harvesting broadband communication systems with processing energy cost,” IEEE Trans. Wireless Commun., vol. 13, no. 11, pp. 6095–6107, Nov. 2014.

[10] J. Yang and S. Ulukus, “Optimal packet scheduling in an energy harvesting communication system,” IEEE Trans. Commun., vol. 60, no. 1, pp. 220–230, Jan. 2012.

[11] O. Ozel, J. Yang, and S. Ulukus, “Optimal broadcast scheduling for an energy harvesting rechargeable transmitter with a finite capacity battery,” IEEE Trans. Wireless Commun., vol. 11, no. 6, pp. 2193–2203, June 2012.

[12] K. Tutuncuoglu and A. Yener, “Optimum transmission policies for bat- tery limited energy harvesting nodes,” IEEE Trans. Wireless Commun., vol. 11, no. 3, pp. 1180–1189, Mar. 2012.

[13] F. Zhang and V. Lau, “Closed-form delay-optimal power control for energy harvesting wireless system with finite energy storage,” IEEE Trans. Signal Process., vol. 62, no. 21, pp. 5706–5715, Nov. 2014.

[14] T. Tong, S. Ulukus, and W. Chen, “Optimal packet scheduling for delay minimization in an energy harvesting system,” in Proc. IEEE Int. Conf. Commun. (ICC), June 2015, pp. 4241–4246.

[15] S. Boyd and L. Vandenberghe, Convex optimization. Cambridge University Press, 2004.

[16] J. Yang and S. Ulukus, “Transmission completion time minimization in an energy harvesting system,” in Proc. Conf. Inform. Sci. Syst., Mar. 2010, pp. 1–6.

[17] K. Tutuncuoglu, A. Yener, and S. Ulukus, “Optimum policies for an energy harvesting transmitter under energy storage losses,” IEEE J. Sel. Areas Commun., vol. 33, no. 3, pp. 467–481, Mar. 2015.