A multiuser waterfilling algorithm
Hello,
this blog entry documents a code snippet for a multi-user waterfilling algorithm. It's heuristic and relatively straightforward, making it easy to implement additional constraints or rules.
I rewrote parts of it to improve readability, but no extensive testing took place afterwards. Please double-check that it does what it promises.
Introduction to multiuser waterfilling.
Background information can be found for example in the presentation from Yosia Hadisusanto, here.
A base station is allowed to transmit over a given frequency band to a number of receivers.
The frequency band is divided into a finite number of "radio resources". For example, in a LTE radio system, a 4.5 MHz transmit bandwidth is divided into 25 subbands with 180 kHz bandwidth in each.
The quality of the radio channel is known for each user in each subband.
For a single-user, an optimal solution that maximizes throughput based on Shannon's capacity equation can be found by the well-known waterfilling algorithm: The transmit power is "poured" on top of the channel quality profile. The amount of water that ends up in each resource corresponds to the amount of transmit power allocated to the resource.
Figure 1: Single-user waterfilling
The concept of waterfilling can be extended to multiple users, where one resource is allocated to one user. Unfortunately, the computational complexity of the ideal solution explodes, because the two problems of allocating users to resources and distributing a user's transmit power budget are coupled.
While the ideal solution is of interest for theoretical research, it has important flaws that prevent its use in a real-world application:
- maximizing the sum throughput often means that cell-edge users with a "bad" channel get practically no throughput at all. This contradicts typical radio system design, where one of the most important design challenges is to reliably serve cell-edge users.
- Shannon's equation is not meaningful at extremes of the signal-to-noise ratio range. For example, a LTE radio link does not have modulation-and-coding schemes to exploit signal-to-noise ratios below about -2 dB. Waterfilling tends to spread the available power over the widest possible bandwidth, operating at very low signal-to-noise ratios.
In practice, the problem is very much driven by practical constraints, and maximizing sum throughput becomes almost an "afterthought".
Do I really need waterfilling?
The somewhat surprising answer is: Probably not.
Figure 2: Allocating transmit power to multiple users
The result in Figure 2 is taken from Yosia Hadisusanto's presentation, link: Transmit power is allocated in different ways over bandwidth, based on frequency-dependent channels (not shown).
1) shows a "dumb" allocation, where the channel is totally disregarded. The frequency range is split into four sections. All the transmit power "budget" of the first user is allocated to the first section, the second user to the second and so on.
The achieved throughput is normalized to 100 %. This is the reference result.
In 2), resources are assigned to users for optimum throughput, but the per-user power is distributed evenly. Throughput increases by a factor of 1.88.
The resource allocation in 3) is fixed (compare to first picture), but power allocation is variable, using waterfilling. This result could be obtained for example when conventional single-user waterfilling is applied on each user in the first picture individually. Throughput increases "only" by a factor of 1.22.
Finally, 4) combines an optimum resource allocation with waterfilling. Throughput improves by a factor of 1.92. It's the best result, but not that impressive when comparing it to the 1.88 achieved in 2) by merely selecting resources.
The presented algorithm implements allocations similar to 2) and 4) in a heuristic manner. It is relatively straighforward and can be easily extended to meet additional constraints.
Algorithm
 Figure 3: Algorithm |
Figure 3 shows a flowchart of the algorithm: Users are handled in a Round-Robin fashion, and the best free resource is tentatively allocated to the current user. The number of resources for any user can be limited to improve the performance of cell-edge users at the expense of sum throughput. The algorithm takes the power budget of each user as a parameter (again, for example one may allocate more power to cell-edge users). The mode parameter switches between fixed-power allocation as shown in Figure 2 part 2) and waterfilling as in Figure 2 part 4). The code can be further optimized for fixed power allocation by replacing the iterative "waterfill()" subroutine with another one that splits a user's power evenly between resources allocated to the user. |
Usage
The code snippet contains three parts: A header file, the main part and an example invocation.
It is possible to compile the whole code block as it is with a C compiler (gcc). If splitting header and main file, please note that the "top level" documentation is in the header file.
Depending on the application, it can be useful to call the waterfilling routine repeatedly and adapt parameters to "boost" users that do not meet quality-of-service targets or the like.
Summary
The presented code implements multi-user waterfilling. It is heuristic, suboptimal and pretty fast.
- Comments
- Write a Comment Select to add a comment
there's a link at the top of the page to the C code (look for "code snippet"). I've never used in from Matlab.
I'd use file IO myself to integrate it into matlab to make development work easier (as it's unlikely to do _exactly_ what you want.).
Later, wrapping it into a .MEX function seems straightforward.
To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.
Please login (on the right) if you already have an account on this platform.
Otherwise, please use this form to register (free) an join one of the largest online community for Electrical/Embedded/DSP/FPGA/ML engineers:
