Recursive Geometric Water-Filling

P. He, L. Zhao, S. Zhou and Z. Niu, “Recursive water-filling for wireless links with energy harvesting transmitters”, IEEE Transaction on Vehicular Technology, vol 63, No. 3, March, pp1232-1241, 2014.

When we consider energy harvesting communication, the system can be modelled in the figure to the right. We consider the time period from (0, T] in epochs. Each epoch is the result of the channel state change or the harvest energy arrival or both events. We use Li to denote the time duration and ai to denote the fading gain of the ith epoch. At the beginning of each epoch, the energy arrival is denoted by Ein(i) and is a non-negative value.

The objective is to maximize the number of bits transmitted by the deadline T within K epochs. The optimal power management strategy is such that the transmit power is constant in each epoch. Therefore, let us denote the transmit power in epoch i by si, for i = 1,..., K.

The Recursive Geometric Water-Filling (RGWF) algorithm can compute the optimal exact solution to the following problem within finite loops.

The first constraint states that the power allocated at each step must be positive. The second constraint states that the sum of all the allocated power must be less than or equal to the total sum of energy harvested.

RGWF Algorithm

In line 3, the algorithm sequentially processes from the second epoch to the Kth epoch. The inner for loop from lines 6-17 updates power levels for the current processing epoch (L) and its previous L - n epochs to form a processing window. The GWF algorithm is applied to this window to find a common water level.

In line 8, a summation is used to sum up all the harvested energy in the processing window.

The condition is that if the lower limit of the summation is greater than the upper limit, the result of this summation is defined as zero. Then the if clause compares the water level of this processing window with the previous epoch's water level. If the water level non-decreasing condition is satisfied, then output RGWF(L), and move to processing the next epoch. If the water level non-decreasing condition is not satisfied, the window is expanded by one epoch on the left side.

The figure on the right is an illustration of the inner for loop of the RGWF. It is assumed that the current processing epoch is L = 6, with Ein(6) = 0. The power allocation for the first five epochs has been completed as shown in Fig. 3a.

Using line 9 of the algorithm, since there is no energy harvested in epoch 6, the power level for epoch 6 is zero and the water level is just the fading level. Lines 10-12 calculate ke* = 5 and then line 13 compares the water level of the current processing window with that of the ke*th epoch.

Since the comparison does not hold, the algorithm goes back to line 6 by decreasing n to 5and then the processing window is extended to including epochs 5 and 6 as shown in Fig. 3b.

The algorithm continues until the water-level non-decreasing condition is satisfied.

MATLAB Code

To run this function, the input parameters (Ein, gain, weight) must be inputted to the RGWF function and the function must be assigned to an array of output paramters (si, a ,w) to receive an output.

This algorithm can be obtained here.

function [si,a,w] = RGWF_GOOD(Ein,gain,weight)

%w: weight   Ein: Energy harvested    a:fading gain

Ein=Ein;

w=weight;

a=gain;

% w=true(1,20);

% Ein=abs((0.5+ 0.1.*randn(20,1)))';

% a=abs((0.2 + 0.2.*randn(20,1)))';

si(1)=Ein(1);                      %Assign energy harvested to first epoch

for L=2:length(a)

    si(L)=Ein(L);                      %Assign energy harvested to L'th epoch

    k=L;

    n=L;

    while n>=1

        if n>1

            k=max(find(si(1:k-1)~=0));                  %Finds index of maximum step under water before most recent k

        else

            k=1;

end

        if isempty(k)==1                                %If no step before k is under water, break out of while loop

            break;

end

        if (si(n)/w(n)+1/(a(n)*w(n))) >= (si(k)/w(k)+1/(a(k)*w(k)))             %Compare total height of nth epoch with maximum index under water before k

            break;

        else

            si(k:L)=(GWF(sum(si(k:L)),a(k:L),w(k:L)) - 1./(a(k:L).*w(k:L))).*w(k:L); %Do GWF with k up to n

            si(si<0)=[0];              %Zero out all negative powers.

            if si(k)~=0                 %If after doing GWF index k does not have zero power, make n=k. Check While loop condition. If it does have zero power....

                n=k;                   %...check while loop condition without updating n

end

end

end

end

A user friendly script has also been developed which makes visualizing the output easier. This file (called RGWF_call.m) can be accessed here.

MATLAB Simulation

Using unit width weights with arbitrary gain values the non-decreasing condition of the RGWF approach can be observed. The RGWF_Call file can be used to generate the optimal solution along with a figure of the output

Applications

Google Sites

Report abuse