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