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