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