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
011package com.net2plan.examples.ocnbook.offline;
012
013import java.util.List;
014import java.util.Map;
015
016import cern.colt.matrix.tdouble.DoubleFactory2D;
017import cern.colt.matrix.tdouble.DoubleMatrix1D;
018import cern.colt.matrix.tdouble.DoubleMatrix2D;
019import cern.jet.math.tdouble.DoubleFunctions;
020
021import com.jom.OptimizationProblem;
022import com.net2plan.interfaces.networkDesign.Configuration;
023import com.net2plan.interfaces.networkDesign.Demand;
024import com.net2plan.interfaces.networkDesign.IAlgorithm;
025import com.net2plan.interfaces.networkDesign.Link;
026import com.net2plan.interfaces.networkDesign.Net2PlanException;
027import com.net2plan.interfaces.networkDesign.NetPlan;
028import com.net2plan.interfaces.networkDesign.Node;
029import com.net2plan.libraries.NetworkPerformanceMetrics;
030import com.net2plan.libraries.WirelessUtils;
031import com.net2plan.utils.Constants.RoutingType;
032import com.net2plan.utils.InputParameter;
033import com.net2plan.utils.Triple;
034
035/**
036 * Jointly optimizes the demand injected traffic (congestion control) and link transmission powers ina wireless network, solving a NUM formulation. 
037 * @net2plan.description
038 * @net2plan.keywords Capacity assignment (CA), Transmission power optimization, JOM, NUM, Wireless 
039 * @net2plan.ocnbooksections Section 11.5, Section 5.5, Section 6.2
040 * @net2plan.inputParameters 
041 * @author Pablo Pavon-Marino
042 */
043public class Offline_cba_wirelessCongControlTransmissionPowerAssignment implements IAlgorithm
044{
045        private double PRECISIONFACTOR;
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 mac_pathLossExponent = new InputParameter ("mac_pathLossExponent", 3.0 , "Exponent in the model for propagation losses" , 0 , true , Double.MAX_VALUE , true);
051        private InputParameter mac_worseRiseOverThermal_nu = new InputParameter ("mac_worseRiseOverThermal_nu", 10.0 , "Worse case ratio between interference power and thermal power at any receiver. Used to set the common thermal power in the receivers" , 0 , true , Double.MAX_VALUE , true);
052        private InputParameter mac_interferenceAttenuationFactor_nu = new InputParameter ("mac_interferenceAttenuationFactor_nu", 1.0e6 , "The interference power received in natural units is divided by this to reduce its effect" , 1 , true , Double.MAX_VALUE , true);
053        private InputParameter mac_maxTransmissionPower_logu = new InputParameter ("mac_maxTransmissionPower_logu", 3.0 , "The maximum link transmission power in logarithmic units (e.g. dBm)");
054        private InputParameter mac_minTransmissionPower_logu = new InputParameter ("mac_minTransmissionPower_logu", 0.0 , "The minimum link transmission power in logarithmic units (e.g. dBm)");
055        private InputParameter cc_minHd = new InputParameter ("cc_minHd", 0.1 , "Minimum traffic assigned to each demand" , 0 , true , Double.MAX_VALUE , true);
056        private InputParameter cc_maxHd = new InputParameter ("cc_maxHd", 1.0E6 , "Maximum traffic assigned to each demand" , 0 , true , Double.MAX_VALUE , true);
057        private InputParameter cc_fairnessFactor = new InputParameter ("cc_fairnessFactor", 1.0 , "Fairness factor in utility function of congestion control" , 0 , true , Double.MAX_VALUE , true);
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                if (E == 0) throw new Net2PlanException ("The input topology has no links");
066
067                this.PRECISIONFACTOR = Double.parseDouble(net2planParameters.get("precisionFactor"));
068
069                /* Remove all demands, then create a demand per input output node pair */
070                netPlan.removeAllDemands();
071                netPlan.setRoutingType(RoutingType.SOURCE_ROUTING);
072                for (Node n1 : netPlan.getNodes())
073                        for (Node n2 : netPlan.getNodes())
074                                if (n1 != n2)
075                                        netPlan.addDemand(n1, n2, cc_minHd.getDouble(), null);
076                netPlan.addRoutesFromCandidatePathList(netPlan.getVectorLinkLengthInKm().toArray()  , "K" , "1");
077                
078                /* Initialize the gains between links, normalizing them so that the maximum gain is one */
079                DoubleMatrix2D mac_g_nu_ee = WirelessUtils.computeInterferenceMatrixNaturalUnits (netPlan.getLinks () , mac_interferenceAttenuationFactor_nu.getDouble() , mac_pathLossExponent.getDouble());
080                final double maxGainValue = mac_g_nu_ee.getMaxLocation() [0];
081                mac_g_nu_ee.assign (DoubleFunctions.div(maxGainValue));
082                
083                /* Initialize the thermal noise at the receivers, to have a worse case ROT (rise over thermal) */
084                double worseInterferenceReceivedAtMaxPower_nu = WirelessUtils.computeWorseReceiverInterferencePower_nu (mac_maxTransmissionPower_logu.getDouble()  , mac_g_nu_ee);
085
086                /* Adjust the thermal noise in the receivers so that we have a given ROT */
087                final double mac_receptionThermalNoise_nu = worseInterferenceReceivedAtMaxPower_nu / mac_worseRiseOverThermal_nu.getDouble();
088
089                /* Make the formulation  */
090                final int D = netPlan.getNumberOfDemands();
091
092                /* Make the formulation  */
093                DoubleMatrix2D G_ee = DoubleFactory2D.sparse.make (E,E);
094                DoubleMatrix2D G_eep = mac_g_nu_ee.copy ();
095                for (int e = 0; e < E ; e ++) { G_ee.set(e,e,mac_g_nu_ee.get(e,e)); G_eep.set (e,e,0); }
096
097                OptimizationProblem op = new OptimizationProblem();
098                op.addDecisionVariable("p_e", false , new int[] { 1 , E }, mac_minTransmissionPower_logu.getDouble() , mac_maxTransmissionPower_logu.getDouble());
099                op.addDecisionVariable("h_d", false , new int[] { 1 , D }, cc_minHd.getDouble() , cc_maxHd.getDouble());
100                
101                op.setInputParameter("b", 1-cc_fairnessFactor.getDouble());
102                op.setInputParameter("s2", mac_receptionThermalNoise_nu);
103                op.setInputParameter("G_ee", G_ee);
104                op.setInputParameter("G_eep", G_eep);
105                op.setInputParameter("R_de", netPlan.getMatrixDemand2LinkAssignment());
106                
107                /* For the objective function we use that e^(ln(x) = x */
108                if (cc_fairnessFactor.getDouble() == 1)
109                        op.setObjectiveFunction("maximize", "sum ( ln ( h_d ))");
110                else
111                        op.setObjectiveFunction("maximize", "(1/b) * sum (   h_d^b ) ");
112
113                op.addConstraint("h_d * R_de <= ln (  exp(p_e)*G_ee ./ (s2 + exp(p_e)*G_eep) )" , "constr");
114                
115                /* Call the solver to solve the problem */
116                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () ,  "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
117
118                /* If no solution is found, quit */
119                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
120                if (op.foundUnboundedSolution()) throw new Net2PlanException ("Found an unbounded solution");
121                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
122        
123                /* Retrieve the optimum solutions. Convert the bps into Erlangs */
124                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
125                DoubleMatrix1D p_e_array = op.getPrimalSolution("p_e").view1D ();
126                DoubleMatrix1D h_d_array = op.getPrimalSolution("h_d").view1D ();
127                DoubleMatrix1D pi_e_array = op.getMultipliersOfConstraint("constr").view1D ();
128
129                /* Update the netplan object with the resulting capacities */
130                for (Link e : netPlan.getLinks())
131                {
132                        final double sinr_e = computeSINR_e (e ,p_e_array , mac_g_nu_ee , mac_receptionThermalNoise_nu , netPlan); 
133                        e.setCapacity(Math.log(sinr_e));
134                        e.setAttribute("p_e" , "" + p_e_array.get(e.getIndex ()));
135                        e.setAttribute("pi_e" , "" + Math.abs (pi_e_array.get(e.getIndex ())));
136                }
137                /* Update the netplan object with the resulting demand offered and carried traffic */
138                for (Demand d : netPlan.getDemands())
139                {
140                        final double h_d = h_d_array.get (d.getIndex ());
141                        d.setOfferedTraffic(h_d);
142                        d.getRoutes().iterator().next().setCarriedTraffic(h_d , h_d);
143                }
144
145                /* Check constraints */
146                for (Link e : netPlan.getLinks ()) 
147                { 
148                        final double p_e = Double.parseDouble(e.getAttribute("p_e"));
149                        if (p_e < mac_minTransmissionPower_logu.getDouble() - 1E-3) throw new RuntimeException ("Bad");
150                        if (p_e > mac_maxTransmissionPower_logu.getDouble() + 1E-3) throw new RuntimeException ("Bad");
151                        if (e.getCapacity() < e.getCarriedTrafficIncludingProtectionSegments() - PRECISIONFACTOR) throw new RuntimeException ("Bad"); 
152                } 
153
154                boolean allMaxPower = true;
155                for (Link e : netPlan.getLinks())
156                        if (Math.abs(mac_maxTransmissionPower_logu.getDouble() - Double.parseDouble(e.getAttribute("p_e"))) > 1E-3) allMaxPower = false;
157                
158                final double optimumNetUtilityFromCapacities = NetworkPerformanceMetrics.alphaUtility(netPlan.getVectorDemandOfferedTraffic() , cc_fairnessFactor.getDouble());
159                System.out.println ("Ok! Optimal net utility: " + optimumNetUtilityFromCapacities + ", from JOM output: " + optNetworkUtility + ", all links at maximum power: " + allMaxPower);
160                return "Ok! Optimal net utility: " + optimumNetUtilityFromCapacities + ", from JOM output: " + optNetworkUtility + ", all links at maximum power: " + allMaxPower;
161        }
162
163        @Override
164        public String getDescription()
165        {
166                return "Given a wireless network where each link capacity is determined by the link SNR (signal to noise ratio - incliding interferences), and given a set of unicast traffic demands defined in it. This algorithm first computes one shortest path route per demand, which will carry the demand traffic. Then, jointly optimizes (i) the traffic to inject by each demand, and (ii) the transmission power in the wireless links, to optimize a fair allocation of the traffic among the sources (demands). The link capacity is approximated as proportional to the logarithm of the link SNR. Initially, the input network interference matrix is normalized so that the worst case rise-over-thermal (ROT) of any link matches a given value. The solution is found solving a problem formulation with JOM.";
167        }
168
169        @Override
170        public List<Triple<String, String, String>> getParameters()
171        {
172                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
173                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
174        }
175
176        
177        private double computeSINR_e (Link e , DoubleMatrix1D p_e , DoubleMatrix2D mac_g_nu_ee , double mac_receptionThermalNoise_nu , NetPlan np)
178        {
179                final double receivedPower_nu = Math.exp(p_e.get(e.getIndex ())) * mac_g_nu_ee.get(e.getIndex (),e.getIndex ());
180                double interferencePower_nu = mac_receptionThermalNoise_nu;
181                for (Link eInt : np.getLinks ())
182                        if (eInt != e) interferencePower_nu += Math.exp(p_e.get(eInt.getIndex ())) * mac_g_nu_ee.get(eInt.getIndex (),e.getIndex ());
183                return receivedPower_nu / interferencePower_nu;
184        }
185
186}