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 011 012 013 014 015 016 017 018package com.net2plan.examples.ocnbook.offline; 019 020import java.util.List; 021import java.util.Map; 022 023import cern.colt.matrix.tdouble.DoubleFactory1D; 024import cern.colt.matrix.tdouble.DoubleMatrix1D; 025import cern.colt.matrix.tdouble.DoubleMatrix2D; 026import cern.jet.math.tdouble.DoubleFunctions; 027 028import com.jom.OptimizationProblem; 029import com.net2plan.interfaces.networkDesign.IAlgorithm; 030import com.net2plan.interfaces.networkDesign.Link; 031import com.net2plan.interfaces.networkDesign.Net2PlanException; 032import com.net2plan.interfaces.networkDesign.NetPlan; 033import com.net2plan.libraries.NetworkPerformanceMetrics; 034import com.net2plan.libraries.WirelessUtils; 035import com.net2plan.utils.DoubleUtils; 036import com.net2plan.utils.InputParameter; 037import com.net2plan.utils.Triple; 038 039/** 040 * Optimizes the backoff window size of the links in a wireless network based on a CSMA MAC, solving a formulation. 041 * @net2plan.description 042 * @net2plan.keywords Capacity assignment (CA), CSMA, JOM, Wireless, NUM 043 * @net2plan.ocnbooksections Section 5.4.2 044 * @net2plan.inputParameters 045 * @author Pablo Pavon-Marino 046 */ 047public class Offline_ca_wirelessCsmaWindowSize implements IAlgorithm 048{ 049 050 private InputParameter solverName = new InputParameter ("solverName", "#select# ipopt", "The solver name to be used by JOM. "); 051 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 052 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)"); 053 private InputParameter alphaFairnessFactor = new InputParameter ("alphaFairnessFactor", (double) 2 , "Fairness alpha factor" , 0 , true , Double.MAX_VALUE , true); 054 private InputParameter betaFactor = new InputParameter ("betaFactor", (double) 1000 , "Factor weighting the network utility in the objective function" , 0 , true , Double.MAX_VALUE , true); 055 private InputParameter linkNominalCapacity = new InputParameter ("linkNominalCapacity", (double) 1 , "Nominal rate of the links. If non positive, nominal rates are THE rates of the initial design"); 056 private InputParameter minimumSchedFractionTime = new InputParameter ("minimumSchedFractionTime", (double) 0.00001 , "Minimum fraction time of any feasible schedule. To avoid numerical problems" , 0 , true , Double.MAX_VALUE , true); 057 058 @Override 059 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 060 { 061 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 062 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 063 final int E = netPlan.getNumberOfLinks(); 064 065 /* Take link nominal capacities */ 066 if (linkNominalCapacity.getDouble() > 0) netPlan.setVectorLinkCapacity(DoubleFactory1D.dense.make (E, linkNominalCapacity.getDouble())); 067 DoubleMatrix1D mac_linkNominalCapacities = netPlan.getVectorLinkCapacity(); 068 069 /* Make the formulation */ 070 final DoubleMatrix2D A_em = WirelessUtils.computeSchedulingMatrix (netPlan.getLinks ()); 071 final int M = A_em.columns (); 072 073 OptimizationProblem op = new OptimizationProblem(); 074 op.addDecisionVariable("pi_m", false , new int[] { 1 , M }, minimumSchedFractionTime.getDouble() , 1); 075 op.addDecisionVariable("u_e", false , new int[] { 1 , E }, DoubleUtils.zeros(E) , mac_linkNominalCapacities.toArray()); 076 077 op.setInputParameter("A_em", A_em); 078 op.setInputParameter("b", 1-alphaFairnessFactor.getDouble()); 079 op.setInputParameter("beta", betaFactor.getDouble()); 080 op.setInputParameter("nomU_e", mac_linkNominalCapacities , "row"); 081 op.setInputParameter("A_em", A_em); 082 083 /* For the objective function we use that e^(ln(x) = x */ 084 if (alphaFairnessFactor.getDouble() == 1) 085 op.setObjectiveFunction("maximize", "-pi_m * ln(pi_m') + beta* sum(ln (u_e)) "); 086 else 087 op.setObjectiveFunction("maximize", "-pi_m * ln(pi_m') + beta/b* sum(u_e ^ b) "); 088 089 op.addConstraint("sum(pi_m) == 1"); // relate link and node persistence prob 090 op.addConstraint("u_e <= nomU_e .* (pi_m * A_em')" , "r_e"); // relate link and node persistence prob 091 092 /* Call the solver to solve the problem */ 093 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 094 095 /* If no solution is found, quit */ 096 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 097 if (op.foundUnboundedSolution()) throw new Net2PlanException ("Found an unbounded solution"); 098 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 099 100 /* Retrieve the optimum solutions */ 101 final DoubleMatrix1D pi_m = op.getPrimalSolution("pi_m").view1D(); 102 final DoubleMatrix1D u_e = op.getPrimalSolution("u_e").view1D(); 103 final DoubleMatrix1D r_e = op.getMultipliersOfConstraint("r_e").view1D().assign (DoubleFunctions.abs); // multipliers are positive 104 105 /* Compute the link capacities according to the schedules. Check if it is equal to returned solution */ 106 DoubleMatrix1D fromSched_ue = A_em.zMult(pi_m, null).assign (mac_linkNominalCapacities , DoubleFunctions.mult); 107 final double maxErrorInLinkCapacity = fromSched_ue.size () > 0? fromSched_ue.copy ().assign (u_e , DoubleFunctions.minus).assign (DoubleFunctions.abs).getMaxLocation () [0] : 0; 108 if (maxErrorInLinkCapacity > 1E-3) throw new RuntimeException ("Bad"); 109 110 /* Save solution */ 111 for (Link e : netPlan.getLinks ()) 112 { 113 e.setAttribute("r_e" , "" + r_e.get(e.getIndex ())); 114 e.setCapacity(u_e.get(e.getIndex ())); 115 } 116 117 final double netUtilityByBeta = betaFactor.getDouble() * NetworkPerformanceMetrics.alphaUtility(u_e , alphaFairnessFactor.getDouble()); 118 double objFunc = netUtilityByBeta; for (int m = 0 ; m < M ; m ++) objFunc -= pi_m.get(m) * Math.log(pi_m.get(m)); 119 120 netPlan.setAttribute("optimumCSMAObjectiveFunction", "" + objFunc); 121 netPlan.setAttribute("optimumCSMAUtilityByBeta", "" + netUtilityByBeta); 122 netPlan.setAttribute("optimumCSMAUtility", "" + (netUtilityByBeta/betaFactor.getDouble())); 123 124 return "Ok! Num Valid schedules: " + M + ", Optimal Obj Func: " + objFunc + ", Objective function just considering network utility: " + netUtilityByBeta; 125 } 126 127 @Override 128 public String getDescription() 129 { 130 return "This algorithm computes the optimum backoff window size for each link in a wireless network governed by the CSMA protocol, so that the resulting link capacities in the network globally optimize a fairness function (that is, link capacities are allocated in a fair form). The solution is found solving a problem formulation with JOM."; 131 } 132 133 @Override 134 public List<Triple<String, String, String>> getParameters() 135 { 136 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 137 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 138 } 139 140}