{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Optimal Power and Bandwidth Allocation in a Gaussian Channel\n", "by Robert Gowers, Roger Hill, Sami Al-Izzi, Timothy Pollington and Keith Briggs\n", "\n", "from Boyd and Vandenberghe, Convex Optimization, exercise 4.62 page 210\n", "\n", "Consider a system in which a central node transmits messages to $n$ receivers. Each receiver channel $i \\in \\{1,...,n\\}$ has a transmit power $P_i$ and bandwidth $W_i$. A fraction of the total power and bandwidth is allocated to each channel, such that $\\sum_{i=1}^{n}P_i = P_{tot}$ and $\\sum_{i=1}^{n}W_i = W_{tot}$. Given some utility function of the bit rate of each channel, $u_i(R_i)$, the objective is to maximise the total utility $U = \\sum_{i=1}^{n}u_i(R_i)$.\n", "\n", "Assuming that each channel is corrupted by Gaussian white noise, the signal to noise ratio is given by $\\beta_i P_i/W_i$. This means that the bit rate is given by:\n", "\n", "$R_i = \\alpha_i W_i \\log_2(1+\\beta_iP_i/W_i)$\n", "\n", "where $\\alpha_i$ and $\\beta_i$ are known positive constants.\n", "\n", "One of the simplest utility functions is the data rate itself, which also gives a convex objective function.\n", "\n", "The optimisation problem can be thus be formulated as:\n", "\n", "minimise $\\sum_{i=1}^{n}-\\alpha_i W_i \\log_2(1+\\beta_iP_i/W_i)$\n", "\n", "subject to $\\sum_{i=1}^{n}P_i = P_{tot} \\quad \\sum_{i=1}^{n}W_i = W_{tot} \\quad P \\succeq 0 \\quad W \\succeq 0$\n", "\n", "Although this is a convex optimisation problem, it must be rewritten in DCP form since $P_i$ and $W_i$ are variables and DCP prohibits dividing one variable by another directly. In order to rewrite the problem in DCP format, we utilise the $\\texttt{kl_div}$ function in CVXPY, which calculates the Kullback-Leibler divergence.\n", "\n", "$\\text{kl_div}(x,y) = x\\log(x/y)-x+y$\n", "\n", "$-R_i = \\text{kl_div}(\\alpha_i W_i, \\alpha_i(W_i+\\beta_iP_i)) - \\alpha_i\\beta_iP_i$\n", "\n", "Now that the objective function is in DCP form, the problem can be solved using CVXPY." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "#!/usr/bin/env python3\n", "# @author: R. Gowers, S. Al-Izzi, T. Pollington, R. Hill & K. Briggs\n", "\n", "import numpy as np\n", "import cvxpy as cp" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "def optimal_power(n, a_val, b_val, P_tot=1.0, W_tot=1.0):\n", " # Input parameters: α and β are constants from R_i equation\n", " n = len(a_val)\n", " if n != len(b_val):\n", " print('alpha and beta vectors must have same length!')\n", " return 'failed', np.nan, np.nan, np.nan\n", " \n", " P = cp.Variable(shape=n)\n", " W = cp.Variable(shape=n)\n", " alpha = cp.Parameter(shape=n)\n", " beta = cp.Parameter(shape=n)\n", " alpha.value = np.array(a_val)\n", " beta.value = np.array(b_val)\n", "\n", " # This function will be used as the objective so must be DCP; \n", " # i.e. elementwise multiplication must occur inside kl_div, \n", " # not outside otherwise the solver does not know if it is DCP...\n", " R = cp.kl_div(cp.multiply(alpha, W),\n", " cp.multiply(alpha, W + cp.multiply(beta, P))) - \\\n", " cp.multiply(alpha, cp.multiply(beta, P))\n", "\n", " objective = cp.Minimize(cp.sum(R))\n", " constraints = [P>=0.0,\n", " W>=0.0,\n", " cp.sum(P)-P_tot==0.0,\n", " cp.sum(W)-W_tot==0.0]\n", " \n", " prob = cp.Problem(objective, constraints)\n", " prob.solve()\n", " \n", " return prob.status, -prob.value, P.value, W.value" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Example\n", "\n", "Consider the case where there are 5 channels, $n=5$, $\\alpha = \\beta = (2.0,2.2,2.4,2.6,2.8)$, $P_{\\text{tot}} = 0.5$ and $W_{\\text{tot}}=1$." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status: optimal\n", "Optimal utility value = 2.451\n", "Optimal power level:\n", "[1.151e-09 1.708e-09 2.756e-09 5.788e-09 5.000e-01]\n", "Optimal bandwidth:\n", "[3.091e-09 3.955e-09 5.908e-09 1.193e-08 1.000e+00]\n" ] } ], "source": [ "np.set_printoptions(precision=3)\n", "n = 5 # number of receivers in the system\n", "\n", "a_val = np.arange(10,n+10)/(1.0*n) # α\n", "b_val = np.arange(10,n+10)/(1.0*n) # β\n", "P_tot = 0.5\n", "W_tot = 1.0\n", "status, utility, power, bandwidth = optimal_power(n, a_val, b_val, P_tot, W_tot)\n", "\n", "print('Status: {}'.format(status))\n", "print('Optimal utility value = {:.4g}'.format(utility))\n", "print('Optimal power level:\\n{}'.format(power))\n", "print('Optimal bandwidth:\\n{}'.format(bandwidth))" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.6" } }, "nbformat": 4, "nbformat_minor": 1 }