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