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 com.jom.DoubleMatrixND; 027import com.jom.OptimizationProblem; 028import com.net2plan.interfaces.networkDesign.*; 029import com.net2plan.libraries.NetworkPerformanceMetrics; 030import com.net2plan.libraries.WirelessUtils; 031import com.net2plan.utils.InputParameter; 032import com.net2plan.utils.Triple; 033 034import java.util.List; 035import java.util.Map; 036 037/** 038 * Optimizes the persistence probability of the links in a wireless network based on a random-access (ALOHA-type) MAC, solving a formulation. 039 * @net2plan.description 040 * @net2plan.keywords Capacity assignment (CA), Random-access MAC, JOM, Wireless, NUM 041 * @net2plan.ocnbooksections Section 5.4.1 042 * @net2plan.inputParameters 043 * @author Pablo Pavon-Marino 044 */ 045public class Offline_ca_wirelessPersistenceProbability implements IAlgorithm 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 alphaFairnessFactor = new InputParameter ("alphaFairnessFactor", (double) 2 , "Fairness alpha factor (alpha factors below to one are not accepted since the problem may be nonconvex)" , 1 , true , Double.MAX_VALUE , true); 051 private InputParameter minLinkPersistenceProb = new InputParameter ("minLinkPersistenceProb", (double) 0.01 , "Minimum persistence porbability of a link" , 0 , true , 1 , true); 052 private InputParameter maxNodePersistenceProb = new InputParameter ("maxNodePersistenceProb", (double) 0.99 , "Maximum persistence probability of a node" , 0 , true , 1 , true); 053 private InputParameter linkNominalCapacity = new InputParameter ("linkNominalCapacity", (double) 1 , "Nominal rate of the links. If non positive, nominal rates are rates of the initial design"); 054 private InputParameter simultaneousTxAndRxPossible = new InputParameter ("simultaneousTxAndRxPossible", false , "If false, a node cannot transmit and receive simultaneously. If true, it can. Affects the interference map"); 055 056 @Override 057 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 058 { 059 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 060 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 061 final int E = netPlan.getNumberOfLinks(); 062 final int N = netPlan.getNumberOfNodes(); 063 064 /* Check input parameters */ 065 for (Node n : netPlan.getNodes()) if (minLinkPersistenceProb.getDouble() * n.getOutgoingLinks().size () > maxNodePersistenceProb.getDouble()) throw new Net2PlanException("Minimum persistence per link is too high or maximum persistence per node too small"); 066 067 /* Take link nominal capacities */ 068 if (linkNominalCapacity.getDouble() > 0) netPlan.setVectorLinkCapacity(DoubleFactory1D.dense.make (E, linkNominalCapacity.getDouble())); 069 070 DoubleMatrix1D mac_linkNominalCapacities = netPlan.getVectorLinkCapacity(); 071 DoubleMatrix2D nodeInterferesToLink_ne = WirelessUtils.computeInterferenceMap (netPlan.getNodes () , netPlan.getLinks () , simultaneousTxAndRxPossible.getBoolean()).getFirst(); 072 073 /* Make the formulation */ 074 OptimizationProblem op = new OptimizationProblem(); 075 op.addDecisionVariable("p_e", false , new int[] { 1 , E }, minLinkPersistenceProb.getDouble() , maxNodePersistenceProb.getDouble()); 076 op.addDecisionVariable("q_n", false , new int[] { 1 , N }, minLinkPersistenceProb.getDouble() , maxNodePersistenceProb.getDouble()); 077 078 op.setInputParameter("Aout_ne", netPlan.getMatrixNodeLinkOutgoingIncidence()); 079 op.setInputParameter("interf_en", nodeInterferesToLink_ne.viewDice()); 080 op.setInputParameter("b", 1-alphaFairnessFactor.getDouble()); 081 op.setInputParameter("nomU_e", netPlan.getVectorLinkCapacity() , "row"); 082 op.setInitialSolution("p_e" , minLinkPersistenceProb.getDouble()); 083 DoubleMatrix1D initQn = DoubleFactory1D.dense.make (N); for (Node n : netPlan.getNodes ()) initQn.set (n.getIndex () , minLinkPersistenceProb.getDouble() * n.getOutgoingLinks().size ()); 084 op.setInitialSolution("q_n" , new DoubleMatrixND (new int [] { 1 , N} , initQn)); 085 086 /* For the objective function we use that e^(ln(x) = x */ 087 if (alphaFairnessFactor.getDouble() == 1) 088 op.setObjectiveFunction("maximize", "sum ( ln(nomU_e') + ln(p_e') + interf_en *ln(1-q_n)' )"); 089 else 090// op.setObjectiveFunction("maximize", "(1/b) * sum ( exp( b*ln(nomU_e') + b*ln(p_e') + b*interf_en *ln(1-q_n)' ) )"); 091 op.setObjectiveFunction("maximize", "(1/b) * sum ( exp( ln(nomU_e') + ln(p_e') + interf_en *ln(1-q_n)' )^b )"); 092 093 094 op.addConstraint("q_n' == Aout_ne * p_e'"); // relate link and node persistence prob 095 096 /* Call the solver to solve the problem */ 097 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 098 099 /* If no solution is found, quit */ 100 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 101 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 102 103 /* Retrieve the optimum solutions. Convert the bps into Erlangs */ 104 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 105 final double [] p_e = op.getPrimalSolution("p_e").to1DArray(); 106 final double [] q_n = op.getPrimalSolution("q_n").to1DArray(); 107 108 /* Save solution */ 109 for (int e = 0 ; e < E ; e ++) 110 { 111 double u_e = mac_linkNominalCapacities.get(e) * p_e [e]; 112 for (int n =0 ; n < N ; n ++) if (nodeInterferesToLink_ne.get(n,e) == 1) u_e *= Math.max(0 , 1 - q_n [n]); 113 netPlan.getLink (e).setAttribute("p_e" , "" + p_e [e]); 114 netPlan.getLink (e).setCapacity(u_e); 115 } 116 for (int n = 0; n < N ; n ++) { netPlan.getNode (n).setAttribute("q_n" , "" + q_n [n]); } 117 118 /* check constraints etc in the solution (sometimes IPOPT makes numerical errors) */ 119 checkSolution (netPlan); 120 121 final double optimumNetUtilityFromCapacities = NetworkPerformanceMetrics.alphaUtility(netPlan.getVectorLinkCapacity() , alphaFairnessFactor.getDouble()); 122 123 return "Ok! Optimal net utility: " + optimumNetUtilityFromCapacities + ", from JOM output: " + optNetworkUtility; 124 } 125 126 @Override 127 public String getDescription() 128 { 129 return "This algorithm computes the persistence probability of each link in a wireless network, that is operating using a random access MAC protocol (ALOHA-type), so that the resulting link capacities 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."; 130 } 131 132 @Override 133 public List<Triple<String, String, String>> getParameters() 134 { 135 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 136 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 137 } 138 139 private void checkSolution (NetPlan netPlan) 140 { 141 for (Link e : netPlan.getLinks ()) 142 { 143 final double pThisLink = Double.parseDouble(e.getAttribute("p_e")); 144 if (pThisLink < minLinkPersistenceProb.getDouble() - 1E-3) throw new RuntimeException ("Bad"); 145 } 146 for (Node n : netPlan.getNodes ()) 147 { 148 final double qThisNode = Double.parseDouble(n.getAttribute("q_n")); 149 if (qThisNode < 0) throw new RuntimeException ("Bad"); 150 if (qThisNode > maxNodePersistenceProb.getDouble() +1E-3) throw new RuntimeException ("Bad"); 151 double peAccum = 0; 152 for (Link e : n.getOutgoingLinks()) peAccum += Double.parseDouble(e.getAttribute("p_e")); 153 if (Math.abs(peAccum - qThisNode) > 1E-3) throw new RuntimeException ("Bad"); 154 } 155 } 156}