-We consider two frequently arising problems in the modeling of a communication network related to the construction of a graph of a communication network that satisfies certain conditions. An algorithm is proposed to which the solution of both problems related to the class of greedy algorithms can be reduced. The question of the uniqueness of the solution of the tasks is investigated. A positive result of solving the problem is obtained and sufficient conditions for uniqueness are identified. The research and development of the corresponding software are of practical importance in the design of real communication networks.
I. INTRODUCTION AND MOTIVATION
The modern development of information technology seriously affects all spheres of human life, and especially on the means of communication. Increasing the bandwidth of communication networks and increasing their computing power makes it possible to create networks with parameters that were impossible several years ago. This led to the concept of super-large communication networks. For the successful functioning of such a communication network, it is necessary to fulfill a number of strict requirements: a small number of lost packets, a short delay time for signal delivery, the ability to transmit large flows of information, etc. Failure to comply with one of these requirements may lead to unsatisfactory operation of the entire network system.
All these requirements become significantly more accessible when designing communication networks in which the minimum total length of edges is realized. This is done by applying various modifications of the Kruskal algorithm (and similar algorithms), which we begin to consider in this article.
Consider the task of building a communication network based on the disparate fragments of a communication network. Such a task often arises during network modernization and is accompanied by a set of analytical studies to identify and achieve the required technical characteristics by the communication network. In this case, we will consider the construction of a connected graph of a communication network on the basis of existing
In fact, the situation under consideration is the task of constructing a spanning tree of minimum weight [1]; please see similar algorithms in [2-5]. We will solve this problem using the heuristic greedy algorithm. Two varieties of this problem will be considered (hereinafter we will call them Task 1 and Task 2), which is of rather high practical significance in the field of the theory of communication networks [6]. When constructing a mathematical model of a communication network in terms of solving Tasks 1,2, it is proposed to use one general algorithmic module based on a greedy algorithm. In addition, the following publications will provide rigorous proof of the uniqueness of a solution under certain conditions (see below for sufficient conditions for uniqueness). Note that in the general case, according to Kirchhoff 's theorem [1, p. 57], there can exist more than one spanning tree in a connected graph. To find the skeleton of minimum weight, Kruskal and Prim algorithms can be used [1, p. 60]. In our case, the existing graph of the communication network needs to be completed to such a graph for which all newly constructed edges would be elements of a spanning tree, which for the constructed graph is determined using the above algorithms. The following algorithms can be considered as adaptations of the Kruskal algorithm to the task of constructing an optimal communication network with the introduction of novelty of uniqueness conditions for the optimal solution. Adaptation is subject to the Kruskal algorithm being applied to some complete graph constructed on the basis of the existing graph of the communication network.
II. TASK 1 A. Construction of a communication network based on a given source communication network that satisfies the condition of connectivity and the minimum total length of the completed communication lines
The problem statement looks like this. Let be G= <V, E> graph of the communication network. We have an optimization problem of the following type:
Here ri is building a line of communication, ( ri ) is the length of the communication line ri , ( ri ) R it is a function of the geographical distance between points with specified geographical coordinates determined by the incident vertices of the communication line ri , is a set of all possible information communication directions [7], is a number of all possible communication directions d i ( v1( i ) , v 2( i ) ) is communication, ( N Dˆ С N2 I Z is binomial
coefficient), the where information
direction v1( i ) V (identifier)
of and v 2( i ) V (identifier) form an offsetting pair, f ( d i ) is reliability of the information direction of communication d i
, f ( d i ) 0 ,1 , f ( d i ) R . In other words, you need to build a connected graph for a given source graph with the minimum total length of the completed edges. The optimal solution of the problem is found using a greedy algorithm. Among pairs of graph vertex ( v1 , v 2 ), where v1 , v 2 , not yet included in the set of edges, such is chosen, the first one, vertex v1 and v 2 in an already constructed graph belong to different connected components (i.e. f ( d ) 0 , where d Dˆ , d ( v1 , v 2 ) ), and, the second one, among all such pairs, one is selected for which the value ( v1 , v 2 ) is minimal.
Step 1. For all edges of the original graph, put the weight coefficient equal to zero.
Step 2. We set the set of edges to be M : Step 3. We set the auxiliary set of vertices to V v1 , v1 V . v1 V from the set V . satisfying the condition:
and , Step 4. We set V : V V , i.e. exclude a vertex Step 5. If
, then end. Else go to step 6.
Step 6. Choosing a pair of graph vertices ( v1 , v 2 ) If there exists a pair of graph vertices, then we assume 1) 2) 3) 4) 1) 2) , , .
, , satisfying the condition: and , ,
, .
Step 7. Choosing a pair of graph vertices ( v1 , v 2 ) , is minimum among all the condition .
If there exists a pair of graph vertices, then we assume 1) , 2) , satisfying 3) 4)
Proof. To join the next vertex, you need to look through the list of all available edges of the original graph, therefore, the complexity will be proportional to (in fact, it is possible to optimize the enumeration of edges by viewing only those that do not yet connect the vertices in the graph already constructed). Consider the procedure for enumerating the vertices of a graph to attach another vertex. Let be n a number of vertices in a graph and i is a number of vertices already attached. To join the next -th vertex the analysis of pairwise vertices from sets of cardinalities and . From here the number of pairs analyzed will be . Convert this expression.
We get
Therefore, we have the cubic complexity of the power of the set of vertices. Given the proportionality of the algorithmic complexity of the cardinality of the set of edges of the graph , we obtain the asymptotic .
The following statement is proved, which gives the sufficiency of uniqueness of the optimal solution to Task 1. D. Condition for optimal solution to Task 1
If the distances between non-incident vertices of the graph are different, then this algorithm leads to the only optimal solution to Task 1.
Note that the difference in pairwise distances between the vertices of the graph is easily achieved due to the high resolution of the real number (for example, for the floatingpoint number format in the IEEE 754 standard, the possible range of numbers is from 4,94⋅10−324 to 1,79⋅10308), which represents the distance between the vertices and takes place on real-time communication networks.
Consider another problem that often arises when modeling a communication network. Namely, this is the task of optimal binding of consumer nodes to nodes of communication providers. Optimality here will also be considered with respect to the minimum total length of the ribs being completed. Thus, a graph should be composed of many subgraphs (not necessarily interconnected), such that each subgraph must contain exactly one element of the set I M s iM iNI1M , and the total length of the edges should be minimal.
III. TASK 2 A. Building bindings of consumers nodes of the communication network to nodes-providers, satisfying the condition of the minimum total length of the completed communication lines
The statement of the problem is as follows. Let be G= <V, E> source graph of the communication network, moreover, V I M I Z , where I M of nodes of communication providers, N s M N I M is the set i i 1 I M N ; s iM is communication provider node; I Z s iZ iNI1Z is the set of communication consumer
nodes, communication consumer node, N I Z task is
N G ( ri ) i 1 m i n
N I Z N , is N . Optimization s iZ (3) I M I M
N I M G V ( i ), E ( i ) , (4) i 1 where V ( i ) contains exactly one element from the set s M N I M
i i 1 , and no element s iM I M can be included in different sets V ( i ) и V ( j ) ( i j ). That is, there is a bijective correspondence of elements of sets s M N I M
i i 1 and V ( i )iNI1M .
Moreover E ( i ) it contains at least one edge incident s iM I M ( i 1 .. N I M ) (5)
This task can also be successfully solved using the greedy algorithm. For this, it is necessary to carry out algorithmic adaptation of the solution of problem 2 to the solution of task 1. As a result, the algorithm will be as follows.
The algorithm for solving Task 2 is as follows.
Step 1. For all edges of the graph, put the weight coefficient ( v , v ) equal to zero.
Step 2. We assume that there are many edges to be completed M :
Step 3. We assume an auxiliary set of vertices V I M that is, a set of vertices corresponding to provider nodes.
Step 4. We assume V I Z , that there are many peaks corresponding to consumer nodes.
Step 5. Next, we use the algorithm for solving task 1, starting from step 5.
The implementation of this algorithm will ensure that the requirements (3-5) are met. Algorithmic complexity will also be (see 2.2).
Concerning Task 2, it can also be proved that the greedy algorithm given will give the only optimal solution if all pairwise distances between the vertices are different. solution in this case, the probability of which can be reduced to unity. The second one, greedy algorithms are an effective tool for building and/or upgrading networks communication. The proposed algorithms were implemented in the construction of real large-scale communication networks, and can accordingly be used in solving problems of constructing a complete communication network with the condition of minimizing the built-up communication lines, and in solving problems of optimal connection of communication network consumer nodes to provider nodes.