Geometric Water-Filling

P. He, L. Zhao, S. Zhou and Z. Niu, “Water-filling: a geometric approach and its application to solve generalized radio resource allocation problems”, IEEE Transaction on Wireless Communications, vol. 12, No. 7, July, pp. 3637-3647, 2013.

The Geometric Water-Filling (GWF) algorithm has two advantages over the Conventional Water -Filling (CWF) approach; it can compute the exact solution with less computation without determining the water level and it can handle more constraints. The target problem has a fundamental form of RRA problem as

The problem needed to be solved has two constraints: the first constraint tells us that the power allocated for each channel must be non-negative. The second constraint states that the sum of all the allocated power must equal to the total power.

GWF Algorithm

To explain the procedure of the GWF algorithm, an example from the published paper can be used; Fig.1 shows a problem with 4 stairs/steps.

The first step in this algorithm is finding step k* which is the highest step underwater. This is done by finding till what step is the power above step k, P2(k), is a positive value. The step before the step that exhibits negative power above it is denoted as step k*. In Fig. 1, step 3 is step k*.
Secondly, the power allocated at step k* must be calculated. This is simply the total power above step k* (P2(k*)) divided by the step number itself. Since the width of all steps is unit width, the power can be evenly divided. This is shown in Fig 1.a, where S3* is the allocated power at step 3 which is step k*.
Knowing k* and Sk*, the power allocation for the steps below step k* can now be calculated. Proposition 2.1 is the explicit solution to the GWF problem. To calculate the power allocated at each step below step k* (si), take sk* and add it with the difference in the depths of step k* and step i. From this, all the power can be allocated in an optimal way.

This algorithm can be extended to weighted cases as well; this is further shown in the paper, but the methodology remains the same.

MATLAB Code

The proposed algorithm can be written in MATLAB to view the results. From the code below, it is evident that the steps taken are as described above.

*Note: To run this function, the input parameters (power, gain and weight) must be inputted to the GWF function and the function must be assigned to and array of output parameters (water_level, index, value, si and height) to receive an output.

function [water_level,index,value,si,height] = GWF(power,gain,weight)

power=power; %Assign total power

count=0;

a=sort(gain,'descend');

w=weight

[height,ind]=sort(1./(w.*a));

weight=weight(ind);

original_size=length(a); %size of gain array, i.e total # of channels.

channel=length(a);

isdone=false;

while isdone==false

    Ptest=0;    %Ptest is total 'empty space' under highest channel under water.

    for i= 1:(channel-1)

        Ptest=Ptest + (height(channel)-height(i))*weight(i);

end

    if (power-Ptest)>0 || (power-Ptest)==0  %If power is greater than Ptest, index(or k*) is equal to channel.

        index=channel;                      %Otherwise decrement channel and run while loop again.

        break;

end

    channel=channel-1;

end

value=power-Ptest;                          %'value' is P2(k*).

water_level=value/sum(weight(1:(index))) + height(index);

si=(water_level - height).*weight;

si(si(:)<0)=[0];

end

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

MATLAB Simulation

Using the aforementioned example in the algorithm section, the GWF_Call file can be used to generate the optimal solution along with a figure of the output. Assuming a total power of 6 units, the simulation can be ran to output the optimal power allocation

Applications

Google Sites

Report abuse