001/******************************************************************************* 002 * Copyright (c) 2017 Pablo Pavon Marino and others. 003 * All rights reserved. This program and the accompanying materials 004 * are made available under the terms of the 2-clause BSD License 005 * which accompanies this distribution, and is available at 006 * https://opensource.org/licenses/BSD-2-Clause 007 * 008 * Contributors: 009 * Pablo Pavon Marino and others - initial API and implementation 010 *******************************************************************************/ 011 012 013 014package com.net2plan.examples.ocnbook.offline; 015 016import cern.colt.matrix.tdouble.DoubleFactory2D; 017import cern.colt.matrix.tdouble.DoubleMatrix1D; 018import cern.colt.matrix.tdouble.DoubleMatrix2D; 019import cern.jet.math.tdouble.DoubleFunctions; 020import com.jom.OptimizationProblem; 021import com.net2plan.interfaces.networkDesign.*; 022import com.net2plan.libraries.NetworkPerformanceMetrics; 023import com.net2plan.libraries.WirelessUtils; 024import com.net2plan.utils.Constants.RoutingType; 025import com.net2plan.utils.InputParameter; 026import com.net2plan.utils.Triple; 027 028import java.util.List; 029import java.util.Map; 030 031/** 032 * Jointly optimizes the demand injected traffic (congestion control) and link transmission powers ina wireless network, solving a NUM formulation. 033 * @net2plan.description 034 * @net2plan.keywords Capacity assignment (CA), Transmission power optimization, JOM, NUM, Wireless 035 * @net2plan.ocnbooksections Section 11.5, Section 5.5, Section 6.2 036 * @net2plan.inputParameters 037 * @author Pablo Pavon-Marino 038 */ 039public class Offline_cba_wirelessCongControlTransmissionPowerAssignment implements IAlgorithm 040{ 041 private double PRECISIONFACTOR; 042 043 private InputParameter solverName = new InputParameter ("solverName", "#select# ipopt", "The solver name to be used by JOM. "); 044 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 045 private InputParameter maxSolverTimeInSeconds = new InputParameter ("maxSolverTimeInSeconds", (double) -1 , "Maximum time granted to the solver to solve the problem. If this time expires, the solver returns the best solution found so far (if a feasible solution is found)"); 046 private InputParameter mac_pathLossExponent = new InputParameter ("mac_pathLossExponent", 3.0 , "Exponent in the model for propagation losses" , 0 , true , Double.MAX_VALUE , true); 047 private InputParameter mac_worseRiseOverThermal_nu = new InputParameter ("mac_worseRiseOverThermal_nu", 10.0 , "Worse case ratio between interference power and thermal power at any receiver. Used to set the common thermal power in the receivers" , 0 , true , Double.MAX_VALUE , true); 048 private InputParameter mac_interferenceAttenuationFactor_nu = new InputParameter ("mac_interferenceAttenuationFactor_nu", 1.0e6 , "The interference power received in natural units is divided by this to reduce its effect" , 1 , true , Double.MAX_VALUE , true); 049 private InputParameter mac_maxTransmissionPower_logu = new InputParameter ("mac_maxTransmissionPower_logu", 3.0 , "The maximum link transmission power in logarithmic units (e.g. dBm)"); 050 private InputParameter mac_minTransmissionPower_logu = new InputParameter ("mac_minTransmissionPower_logu", 0.0 , "The minimum link transmission power in logarithmic units (e.g. dBm)"); 051 private InputParameter cc_minHd = new InputParameter ("cc_minHd", 0.1 , "Minimum traffic assigned to each demand" , 0 , true , Double.MAX_VALUE , true); 052 private InputParameter cc_maxHd = new InputParameter ("cc_maxHd", 1.0E6 , "Maximum traffic assigned to each demand" , 0 , true , Double.MAX_VALUE , true); 053 private InputParameter cc_fairnessFactor = new InputParameter ("cc_fairnessFactor", 1.0 , "Fairness factor in utility function of congestion control" , 0 , true , Double.MAX_VALUE , true); 054 055 @Override 056 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 057 { 058 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 059 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 060 final int E = netPlan.getNumberOfLinks(); 061 if (E == 0) throw new Net2PlanException ("The input topology has no links"); 062 063 this.PRECISIONFACTOR = Double.parseDouble(net2planParameters.get("precisionFactor")); 064 065 /* Remove all demands, then create a demand per input output node pair */ 066 netPlan.removeAllDemands(); 067 netPlan.setRoutingTypeAllDemands(RoutingType.SOURCE_ROUTING); 068 for (Node n1 : netPlan.getNodes()) 069 for (Node n2 : netPlan.getNodes()) 070 if (n1 != n2) 071 netPlan.addDemand(n1, n2, cc_minHd.getDouble(), RoutingType.SOURCE_ROUTING , null); 072 netPlan.addRoutesFromCandidatePathList(netPlan.computeUnicastCandidatePathList(netPlan.getVectorLinkLengthInKm() , 1 , -1, -1, -1, -1, -1, -1, null)); // one route per demand, so P equals D 073 074 075 /* Initialize the gains between links, normalizing them so that the maximum gain is one */ 076 DoubleMatrix2D mac_g_nu_ee = WirelessUtils.computeInterferenceMatrixNaturalUnits (netPlan.getLinks () , mac_interferenceAttenuationFactor_nu.getDouble() , mac_pathLossExponent.getDouble()); 077 final double maxGainValue = mac_g_nu_ee.getMaxLocation() [0]; 078 mac_g_nu_ee.assign (DoubleFunctions.div(maxGainValue)); 079 080 /* Initialize the thermal noise at the receivers, to have a worse case ROT (rise over thermal) */ 081 double worseInterferenceReceivedAtMaxPower_nu = WirelessUtils.computeWorseReceiverInterferencePower_nu (mac_maxTransmissionPower_logu.getDouble() , mac_g_nu_ee); 082 083 /* Adjust the thermal noise in the receivers so that we have a given ROT */ 084 final double mac_receptionThermalNoise_nu = worseInterferenceReceivedAtMaxPower_nu / mac_worseRiseOverThermal_nu.getDouble(); 085 086 /* Make the formulation */ 087 final int D = netPlan.getNumberOfDemands(); 088 089 /* Make the formulation */ 090 DoubleMatrix2D G_ee = DoubleFactory2D.sparse.make (E,E); 091 DoubleMatrix2D G_eep = mac_g_nu_ee.copy (); 092 for (int e = 0; e < E ; e ++) { G_ee.set(e,e,mac_g_nu_ee.get(e,e)); G_eep.set (e,e,0); } 093 094 OptimizationProblem op = new OptimizationProblem(); 095 op.addDecisionVariable("p_e", false , new int[] { 1 , E }, mac_minTransmissionPower_logu.getDouble() , mac_maxTransmissionPower_logu.getDouble()); 096 op.addDecisionVariable("h_d", false , new int[] { 1 , D }, cc_minHd.getDouble() , cc_maxHd.getDouble()); 097 098 op.setInputParameter("b", 1-cc_fairnessFactor.getDouble()); 099 op.setInputParameter("s2", mac_receptionThermalNoise_nu); 100 op.setInputParameter("G_ee", G_ee); 101 op.setInputParameter("G_eep", G_eep); 102 op.setInputParameter("R_de", netPlan.getMatrixDemand2LinkAssignment()); 103 104 /* For the objective function we use that e^(ln(x) = x */ 105 if (cc_fairnessFactor.getDouble() == 1) 106 op.setObjectiveFunction("maximize", "sum ( ln ( h_d ))"); 107 else 108 op.setObjectiveFunction("maximize", "(1/b) * sum ( h_d^b ) "); 109 110 op.addConstraint("h_d * R_de <= ln ( exp(p_e)*G_ee ./ (s2 + exp(p_e)*G_eep) )" , "constr"); 111 112 /* Call the solver to solve the problem */ 113 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 114 115 /* If no solution is found, quit */ 116 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 117 if (op.foundUnboundedSolution()) throw new Net2PlanException ("Found an unbounded solution"); 118 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 119 120 /* Retrieve the optimum solutions. Convert the bps into Erlangs */ 121 final double optNetworkUtility = op.getOptimalCost(); // Warning: I saw in some tests, that IPOPT returned this value different to the optimum solution cost: I could not see if I did something wrong 122 DoubleMatrix1D p_e_array = op.getPrimalSolution("p_e").view1D (); 123 DoubleMatrix1D h_d_array = op.getPrimalSolution("h_d").view1D (); 124 DoubleMatrix1D pi_e_array = op.getMultipliersOfConstraint("constr").view1D (); 125 126 /* Update the netplan object with the resulting capacities */ 127 for (Link e : netPlan.getLinks()) 128 { 129 final double sinr_e = computeSINR_e (e ,p_e_array , mac_g_nu_ee , mac_receptionThermalNoise_nu , netPlan); 130 e.setCapacity(Math.log(sinr_e)); 131 e.setAttribute("p_e" , "" + p_e_array.get(e.getIndex ())); 132 e.setAttribute("pi_e" , "" + Math.abs (pi_e_array.get(e.getIndex ()))); 133 } 134 /* Update the netplan object with the resulting demand offered and carried traffic */ 135 for (Demand d : netPlan.getDemands()) 136 { 137 final double h_d = h_d_array.get (d.getIndex ()); 138 d.setOfferedTraffic(h_d); 139 d.getRoutes().iterator().next().setCarriedTraffic(h_d , h_d); 140 } 141 142 /* Check constraints */ 143 for (Link e : netPlan.getLinks ()) 144 { 145 final double p_e = Double.parseDouble(e.getAttribute("p_e")); 146 if (p_e < mac_minTransmissionPower_logu.getDouble() - 1E-3) throw new RuntimeException ("Bad"); 147 if (p_e > mac_maxTransmissionPower_logu.getDouble() + 1E-3) throw new RuntimeException ("Bad"); 148 if (e.getCapacity() < e.getCarriedTraffic() - PRECISIONFACTOR) throw new RuntimeException ("Bad"); 149 } 150 151 boolean allMaxPower = true; 152 for (Link e : netPlan.getLinks()) 153 if (Math.abs(mac_maxTransmissionPower_logu.getDouble() - Double.parseDouble(e.getAttribute("p_e"))) > 1E-3) allMaxPower = false; 154 155 final double optimumNetUtilityFromCapacities = NetworkPerformanceMetrics.alphaUtility(netPlan.getVectorDemandOfferedTraffic() , cc_fairnessFactor.getDouble()); 156 System.out.println ("Ok! Optimal net utility: " + optimumNetUtilityFromCapacities + ", from JOM output: " + optNetworkUtility + ", all links at maximum power: " + allMaxPower); 157 return "Ok! Optimal net utility: " + optimumNetUtilityFromCapacities + ", from JOM output: " + optNetworkUtility + ", all links at maximum power: " + allMaxPower; 158 } 159 160 @Override 161 public String getDescription() 162 { 163 return "Given a wireless network where each link capacity is determined by the link SNR (signal to noise ratio - incliding interferences), and given a set of unicast traffic demands defined in it. This algorithm first computes one shortest path route per demand, which will carry the demand traffic. Then, jointly optimizes (i) the traffic to inject by each demand, and (ii) the transmission power in the wireless links, to optimize a fair allocation of the traffic among the sources (demands). The link capacity is approximated as proportional to the logarithm of the link SNR. Initially, the input network interference matrix is normalized so that the worst case rise-over-thermal (ROT) of any link matches a given value. The solution is found solving a problem formulation with JOM."; 164 } 165 166 @Override 167 public List<Triple<String, String, String>> getParameters() 168 { 169 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 170 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 171 } 172 173 174 private double computeSINR_e (Link e , DoubleMatrix1D p_e , DoubleMatrix2D mac_g_nu_ee , double mac_receptionThermalNoise_nu , NetPlan np) 175 { 176 final double receivedPower_nu = Math.exp(p_e.get(e.getIndex ())) * mac_g_nu_ee.get(e.getIndex (),e.getIndex ()); 177 double interferencePower_nu = mac_receptionThermalNoise_nu; 178 for (Link eInt : np.getLinks ()) 179 if (eInt != e) interferencePower_nu += Math.exp(p_e.get(eInt.getIndex ())) * mac_g_nu_ee.get(eInt.getIndex (),e.getIndex ()); 180 return receivedPower_nu / interferencePower_nu; 181 } 182 183}