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}