In the paper we consider the problem of allocation of network resources in telecommunication networks using both utility and reliability. We suggest a scalar utility maximization problem subject to capacity constraints and within the pre-defined reliability level. This problem is proposed to be solved by a penalty method. We present the results of numerical results on various test problems for the method.
We begin our description from the basic optimal flow distribution problem in wireless telecommunication networks from [KMT98]. For a fixed time period we are given a network that contains a set L of transmission links (arcs) Copyright ⃝c by the paper's authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). and accomplishes some submitted data volume transmission requirements from a set I of selected pairs of origindestination vertices. Denote by xi and i the current and maximal value of data transmission for pair demand i 2 I, respectively, and by cl the capacity of link l 2 L. For the sake of simplicity we suppose that each pair demand is associated with a unique data transmission path, hence each link l is associated uniquely with the set Nl of pairs of origin-destination vertices, whose data transmission paths contain this link. For each pair demand i we denote by ui(xi) the utility value at the data transmission volume xi. Then the problem of the total utility maximization of the network is written as follows: subject to where subject to If the functions ui(xi) are concave, this is a convex optimization problem over a polyhedron.
In order to extend the model and take into account the reliability of connections we now suppose that the reliability depends on arc flow volumes. More precisely, let l(fl) denote the non-reliability of arc l at its flow volume fl. Hence, we have to add the second goal: and obtain a vector optimization problem. The scalarized goal version with some weights will take the form min ! 1 ∑ l(fl)
2 ∑ ui(xi); l∈L i∈I but the choice of right weights 1 and 2 for so different goals seems too difficult here. For this reason, it is better to determine the pre-defined non-reliability level i for each connection i 2 I and to maximize utility under all these constraints. That is, the origin-destination vertices require some desired level of their reliability to work. This problem is now formulated as follows: max ! max ! ∑ xi = fl; l 2 L; i∈Nl ∑ l∈Li fl 0 l(fl)
i; i 2 I; cl; l 2 L; xi i; i 2 I: (1) (2) (3) (4) (5) If the functions l(fl) are convex, this is a convex optimization problem. 3
Usually, the functions ui(xi) and l(fl) in problem (1)–(5) are smooth, hence we can apply a number of well known smooth optimization methods; see e.g. [DR68, PD78]. However, these problems have large dimensionality and inexact data, hence their solution methods should be rather simple and provide some desired accuracy within an acceptable time interval. Therefore, the penalty based methods are suitable here; see e.g. [FM72, GK81]. We impose penalties only on binding constraints in (2)–(3). Set and define the penalty functions and
We take positive penalty parameters 1 and 2 and define the penalized problem where = ( 1; 2),
max (x;f)∈W
! Ψ(x; f; ); Denote by (x∗( ); f ∗( )) a solution of problem (6)–(7). If each i is positive, increasing, and tending to +1, then the corresponding points (x∗( ); f ∗( )) will tend to a solution of problem (1)–(5). Moreover, this is the case for some approximations of points (x∗( ); f ∗( )). In order to find these approximate solutions of problem (6)–(7) we propose to apply the gradient projection method; see e.g. [DR68, PD78].
Let g(x; f ) = (gx(x; f ); gf (x; f )) denote the gradient of Ψ(x; f; ) where is fixed. At the current point (x; f ) we find the points where ′ > 0, ′′ > 0. The next iterate (xnew; f new) can be found from (xe; fe) after inserting a proper line-search if necessary. That is, we set (6) (7) (8) (9) X F W = fx j 0 = ff j 0 = X F; Φ1(x; f ) = ∑
∑ xi Φ2(x; f ) = ∑
l(fl) xi fl [ l∈L i∈Nl xe = fe =
X [x + ′gx(x; f )];
F [f + ′′gf (x; f )]; xnew f new = = x + (1 e fe+ (1 )x; )f; for
2 (0; 1]: gxi (x; f ) = u′i(xi) 2 1 ∑
∑ xj l∈L j∈Nl
fl il;
The partial derivatives of Ψ(x; f; ) are written as follows: where and where gfl (x; f ) = 2 1 ( ∑ xi i∈Nl fl ) 2 2 ∑ [
∑ i∈I s∈Li i ]
+ s(fs)
′l(fl) il; il = { 1; if i 2 Nl;
0; otherwise; il = { 1; if i 2 Nl; 0; otherwise; for all i 2 I and l 2 L. By using these formulas the main steps in (8)–(9) decompose into single-dimensional problems: 0≤myia≤x i !
max 0≤vl≤cl ! { { gxi (x; f )(yi
xi) gfl (x; f )(vl fl) 1 The coefficients 0;l, u0;i, u1;i, and u2;i were determined on the basis of trigonometric functions: The maximal flow follows:
i for connection i was selected in the segment [1, 7] depending on the connection number as
The maximal flow cl along arc l was selected in the segment [
2 j sin(2i)j + 1; = j sin(i + 1)j + 1;
3 j sin(2i)j + 1: cl = 10 j cos(l + 2)j + 1: i = 7 j sin(i
1)j + 1: i = 3 j cos(i 1)j + 1: The upper non-reliability bound i was selected in the segment [1, 5] depending on the connection number as follows: The parameters 1, 2, ′, and ′′ were fixed as follows:
1 = 0:9; 2 = 0:9; ′ = 0:009; ′′ = 0:009: The distribution of the available arcs across the connections was chosen either uniformly or according to the normal distribution law. We took two versions of the gradient projection method. The first does not involve any line-search, the second involves an Armijo type line-search.
Let us introduce the additional notations: " is the accuracy of a solution of the problem;
T" is the total solution time (in seconds) of the penalty method containing the gradient projection method without line-search;
T";ls is the total solution time (in seconds) of the penalty method containing the gradient projection method with line-search;
I" is the number of iterations of the penalty method containing the gradient projection method without line-search;
I";ls is the number of iterations of the penalty method containing the gradient projection method with linesearch.
T" 0.032 0.094 0.157 0.203
T" 0.032 0.047 0.109 0.109
The penalty method was stopped if the norm difference between two sequential iterates appeared less than the accuracy. In Table 1, the numerical results are given for the case where jIj = 620, jLj = 310 and for different values of the accuracy ".
Note that the working time was less than one second. We can also observe that similar results were obtained for fixed " and jLj and different jIj (see 2), and for fixed " andjIj and different jLj (see 3).
From the experiments we conclude that the version of the penalty method containing the gradient projection method without line-search appeared somewhat better than that with the line-search. In general, the method attained a solution with low accuracy quickly enough, but the additional analysis and selection of parameters for more effective implementation of the method are necessary. 4.0.1
Acknowledgments The results of the first author in this work were obtained within the state assignment of the Ministry of Science and Education of Russia, project No. 1.460.2016/1.4. In this work, the first author was also supported by Russian Foundation for Basic Research, project No. 19-01-00431. The work of the second author was performed within the Russian Government Program of Competitive Growth of Kazan Federal University. The first and third authors were also supported by grant No. 331833 from Academy of Finland.
I" 626 914 869 809