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}