Adv Syst Sci Appl 2020; 02:131–145 Published online at https://ijassa.ipu.ru. Original Russian Text © A. V. Kuznetsov, 2017, published in Upravlenie Bol’shimi Sistemami / Large-Scale Systems Control, 2017, No. 66, pp. 68-93. Allocation of Limited Resources in a System with a Stable Hierarchy (on the Example of the Prospective Military Communications System) Alexander V. Kuznetsov1* 1 Voronezh State University, Voronezh, Russia Abstract: The article is devoted to the formalization of the resource allocation problem in the hierarchical social system, where resources are distributed according to the agent’s role in the system. We study the application of a proposed mathematical model to the organization of the special purpose communication network. Also, we propose an algorithm of the automatic partitioning of the radio communication system according to the role of nodes. None of the nodes has complete knowledge about the entire communication system, and the initially unknown information about the purpose of nodes is established in the process of the beacons exchange. Keywords: resource allocation problem, graphs dissimilarity measures, abstract data structures, radio network planning, communication protocols, cognitive networks 1. INTRODUCTION The problem of the limited resources allocation and an optimal schedule construction in network structures, including hierarchical structures of the transport type, is well known. A large number of articles on this topic appears every year. For example, we can mention the work [1] on the planning of the rail transportation, the article [2] studies the problems of resource allocation in hierarchical systems, the article [3] considers the problem of balancing the input and output parameters of a section of a gas transmission system, etc. Usually in such problems, it is necessary to distribute resources between the vertices of a graph, and the flow of resources through the edges of the graph is somehow restricted. The solution to such problems will be, for example, an optimal (in some sense) schedule or distribution of resources (which are not elements of the graph itself) over the vertices of the graph. This article, however, describes a fundamentally different type of resource allocation problems, often found in military communications planning problems (and, to a lesser extent, in civilian communications), more precisely, in the problem of frequency allocation and assignment. In the described problem, the resource is the edges of a certain graph corresponding to communication channels. This resource should be distributed between pairs of vertices in accordance with a given template. The template itself, which later will be called the requirements graph, is similar to the network of needs and opportunities from [4]. The vertices - consumers of the resources are users of the communication system and/or their telecommunication devices. Moreover, the structure of the relationship between agents of the certain types in the system is much more constant than the composition of specific agents. The solution for this problem is a channel allocation variant that meets certain requirements. We will approach ∗Corresponding author: avkuz@bk.ru 132 A.V. KUZNETSOV solving such problems, focused on working not with specific agents of the system, but with an abstract structure of the agent system, “untied” from the agents themselves. It is also worth noting that despite a large amount of literature about the frequency planning (see, for example, the monograph [5]), it focuses on the physical compatibility of frequencies and on the optimal placement of radio stations. The distribution and redistribution of already known electromagnetically compatible frequencies across several thousand mobile radio stations (and this is a common situation for a military formation of the tactical level) are addressed rather little. It is usually customary to formulate the problem of the optimal assignment of frequency channels as the problem of the minimal colouring of the graph, in which, unlike the classical formulation of the problem, the adjacency of the vertices is determined by the restrictions on the use of not only one colour, but also some of their combinations (see, for example, [6, 7]). However, this formulation usually does not take into account either the hierarchy of agents, to which frequencies must be assigned nor possible changes in the composition of agents nor a case of the lack of frequencies. At the same time, preparing a list of electromagnetically compatible frequencies is a rather difficult computational task and to solve it anew each time with each change in the composition of a radio network, as is sometimes suggested in more specialized publications, is an extremely hard task. There are other possible approaches to the spectrum management, which are mainly used in cognitive radio networks and based, for example, on game theory [8], but also oriented to a much simpler communication system (actually consisting of peer-to-peer devices with the “point-to-point” connection) than what is considered in this article. 2. STATEMENT OF THE PROBLEM For further discussion, we need to give a mathematical description of the communication system and “the communication system settings” (i.e. the channel resource allocation), using the concepts proposed by the author in [9]. The resource allocation problem mentioned in the introduction, in its simplest form, is usually formulated as follows. 2.1. Objects Let us define the following entities: 1. The set of the device classes CComm = {ccomm1, . . . , ccomms}. 2. The set of the devices Comm = {(comm1; ccommi1), . . . , (commn; ccommin)}, where commi is the identifier of the i-th device, and ccommij is the class of the ij-th device, 1 ≤ i ≤ s. 3. The set of the agents Ag = {ag1, . . . , agm}. 4. The ownership relation between Ag and Comm fhave : Comm→ Ag. If for comm ∈ Comm holds fhave(comm) = ag, then we say that the agent ag has the device comm. 5. The set of the channel classes CF = {cf1, . . . , cfl}. Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) ALLOCATION OF RESOURCES ON THE EXAMPLE OF MILITARY COMMUNICATIONS SYSTEM 133 In real-world applications, a class corresponds to a frequency or a bandwidth, or similar channel characteristics. 6. The devices’ capabilities function fcomm : CComm× CF → Z, determining the maximal number of channels of a given type that can be formed simultaneously by a device of a given type; 7. The set of the channels F = {(f1; cfi1), . . . , (fp; cfip)}, where fi is the identifier of the i-th channel and cfij is the class of the ij-th channel, 1 ≤ i ≤ p. 8. The loop-free labelled requirements multigraph (an example of such a graph is shown in Figure 2.1) Req = (Ag,EReq, ϕReq), EReq ⊆ Ag2 × CF, ϕReq : Ag × EReq → Z is an incidence function, showing which agents should be interconnected as well as the number of channels in each connection; the channel classes act as edge labels; Fig. 2.1. Requirements graph Req 9. The channel class capacity function fe : CF → N, determining how many agents can maximally use a channel of a given class. 2.2. Conditions It is necessary to distribute the channels from F by all the devices from Comm to obtain the communication graph Γ = (Comm,E, ϕ), E ⊆ F, ϕ : Comm× E → {0, 1} is the incidence function, so that Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) 134 A.V. KUZNETSOV Fig. 2.2. Communication graph Γ 1. Each edge of the graph Req corresponds to one edge of the graph Γ or to a continuous path in the graph Γ (a relay case); 2. Each vertex ag of the graph Req would correspond to a vertex comm of the graph Γ such that fhave(comm) = ag; 3. The number of edges e of the graph Γ marked with the same channel (f, cf) ∈ F does not exceed the capacity of the channel of this class fe(cf); 4. The number of edges e of the graph Γ marked with the channel (f, cf) and incident to the vertex comm does not exceed the capabilities of the device fcomm(ccomm, cf). An example of the graph Γ corresponding to the graph Req shown in Fig. 2.1 is presented in Fig. 2.2. To summarize, in the model under study the incidence matrix of the graph Γ, informally sometimes called “the radio frequency distribution variant”, is the sought variable. Known parameters of the model are channels F , devices Comm, agents Ag, relationships fhave, fe, fcomm, and the graph Req. The process of distributing channels from the set F between agents and devices belonging to them is often informally called “the communication system setup”. For simplicity, we assume that all channels from F are electromagnetically compatible. Otherwise, it will be necessary to add more edge length labels Γ and restrictions on possible channel assignments for close to each other devices, after which we will use already known methods such as the coordination rings method. 2.3. Model Deficiencies Although the author did not see articles describing this type of a task of resource allocation, it is quite typical in certain areas of activity and solved by the ordinary brute-force search. Concerning military communications (in which the agents are personnel of armed forces), such algorithm was implemented by the author as part of the large team in the form of the software developed by the JSC “Concern “Sozvezdie” [10]. In the traditional approach to the discussed distribution problem, the following disadvantages are observed: 1. The graph Req is literally drawn by the operator for a fairly long time. Each time the composition of the sets Comm, Ag is changed, it is necessary to redraw it again, which with the cardinality of the sets Comm, Ag in hundreds of elements can drag on indefinitely. 2. Moreover, in reality, the set of channels F is not constant: usually, the channels drop out of it over time in an unpredictable way due to the intentional or unintentional interference. With a significant change in the set of channels, the graph Γ, of course, needs to be redesigned. Relations between new agents will have approximately same structure as between their predecessors. Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) ALLOCATION OF RESOURCES ON THE EXAMPLE OF MILITARY COMMUNICATIONS SYSTEM 135 3. Usually, agents fromAg have unequal importance, and for each agi ∈ Ag the weight αi can be set. This weight determines what part of the channels available in F can be allocated to this agent in a situation lack of channels on all agents. 4. The graph Γ is brought to radio stations using various types of storage devices. This methodology dates back to the times when there were relatively few telecommunication devices and it was not difficult to group them. 5. The graph Γ can also be sent over the communication channel, but the question arises: after all, Γ sets the configuration of the communication channel (frequency, at least) and how to send Γ when there are no configured channels at all? 6. Finally, in the event of the accidental failure of the planning centre capable of calculating the graphs Γ, the entire system generally gradually fails. The purpose of this article is twofold: 1. Give the extended formulation of the previously formulated problem taking into account the above disadvantages. 2. Describe the communication system (whether civilian or military, although the author initially worked with military communication systems), in which channels are not assigned in a centralized way, but are selected by each device based on the characteristics of the devices and the position of this devices in the whole system, thereby continuing the work begun in [11]. Note that in the prospective military communications systems [12], currently being developed abroad, the problems 1–6 are being actively solved with the help of the cognitive network technology, in which all nodes have spectrum sensing ability, as in the previously proposed methodology of cognitive radio, and the general knowledge plane of the network, which contains, inter alia, the information about the form, purpose and state network nodes. Among other technologies, the dynamic spectrum control is used, during which nodes consistently occupy or free one or another frequency channel depending on device’s position in the node hierarchy, changes in the interference environment, or other circumstances. In this article, we consider a particular problem of dynamic spectrum control in a cognitive radio network: the initial allocation of frequencies in accordance with the roles of agents. Earlier, the author of [11] considered the organization of a radio network configuration over a previously unorganized communication channel through the exchange of configuration beacons (CB) and response beacons (RB) between a communication control centre (CCC) and radio stations which are necessary to configure. To do this, all the radio stations were supplied with the same grid of technical channels, the central control centre sent the CB on one of channels selected from the pre-set grid, while the radio stations scanned the above- mentioned channel grid and, when the CB was detected, sent the RBs. After receiving the RB, the CCC sent to the radio stations pre-generated configuration data, including the operating frequency and other parameters. We assumed that the configuration data was calculated based on the information about the composition and structure of a custom communication system. The securing of the transmitted data was performed, using an asymmetric cryptosystem like RSA. This eliminated the need for the preliminary distribution of keys (the author do not consciously touch on the possibility of using RSA in Russia for this purpose since this is a more political than a technical issue). It should be noted that automatic clustering algorithms have been known for a long time (see, for example, [13]). However, they are mainly used for the sensor networks’ organization, where the main principle of the cluster construction is the energy efficiency, rather than the position of the device in a hierarchy of some kind. Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) 136 A.V. KUZNETSOV 3. DISTRIBUTION OF RESOURCES, DEPENDING ON THE ROLE OF THE AGENT AND IN CONDITIONS OF INSUFFICIENT RESOURCES The unequal importance of agents from Ag was already mentioned earlier. The problems of the specific organization of agents, which may be determined by the graph of the military hierarchy or other social structure, go far beyond the scope of this article. Suffice it to say that each agent ag ∈ Ag uniquely corresponds to the agent’s feature vector I : ag ↔ (ag1, . . . , agq), and the agent’s “weight” α(ag1, . . . , agq) = α(I(ag)) = α ◦ I(ag) , α ◦ I(ag) ∈ [0, 1] is defined. In the actual implementation of the system, which will be further described in the article, we will assume that the agent’s feature vector is stored in each agent. We can say that each agent even before the distribution of resources “knows” its (and only its) features. In military communication systems, such features may be the level of the military hierarchy to which the agent belongs, the type of agent’s military formation, a serial number of a device, and so on. I note that in military systems such information becomes secret only in aggregate and the fact that it is contained in the agent, more precisely, in the telecommunication devices belonging to the agent, does not compromise the entire system. The set of all agents’ feature vectors is denoted by S. Thus, the entities of Subsection 2.1 are supplemented by the entities: 10. The agent importance function α : S → [0, 1]; 11. The bijective function I : Ag → S,∑ ag∈Ag α ◦ I(ag) = 1. In the case of the lack of resources (channels), Condition 1 of Subsection 2.2 will be replaced by 1. ∑ ag∈Ag ∣∣∣∣α ◦ I(ag)− |F (ag)| |F | ∣∣∣∣→ min, where F (ag) is the set of edges Γ incident to at least one device from the set Comm(ag) ⊂ Comm, Comm(ag) = {comm ∈ Comm|fhave(comm) = ag}. As a result, the problem of channel allocation under conditions of limited channel resources will turn into a combinatorial optimization problem. If the graph Req is set manually, the following happens. The human-compiler of the graph has in his mind a predicates Pi : S |Ag| → {0, 1}, allowing him to group agents into groups that should be connected on the basis of certain signs: Pi(I(ag1), . . . , I(agm))→ ϕReq(agji , cfki) = ni ∧ ji ∈ Ji ⊂ {1, . . . ,m} ∧ ki ∈ Ki ⊂ {1, . . . , l}, (3.1) So, if some statement Pi about agents ags, s = 1,m holds, then some of them should be connected by 1 ≤ ni ≤ p channels of class cfki . Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) ALLOCATION OF RESOURCES ON THE EXAMPLE OF MILITARY COMMUNICATIONS SYSTEM 137 Of course, these signs can be formalized, and the entire graph Req of Subsection 2.1 is completely replaced by 8. The predicate family PReq = {Pi}. Thus, it is possible to replace the complexity of the constant (for each distribution of resources) construction of the graph Req with the complexity of the initial classification of objects and the identification of signs of their association. When implementing the communication system, which will be described in the article below, it must be assumed that the set PReq is also “contained inside” agent. It seems that one could restrict oneself to the introduced concepts when formalizing the task, but in the tasks of forming military communications networks (and indeed in mobile networks) the composition of the set of Ag is not constant - agents drop out over time, reinforcements arrive, etc., although the structure of relationships between agents remains largely unchanged. Finally, such the situation is possible when it is necessary to sequentially distribute channels for several units of the same organizational structure and equipment, but different in composition. 4. STRUCTURAL SIMILARITY 4.1. Definitions To complete the description of the problem posed in the article, it remains only to determine which agents can be considered similar. We can apply the approach from [14]: two graphs are considered similar if they are isomorphic or have isomorphic subgraphs. To simplify, we will assume that the graph Req describes the needs for telecommunication, for example, of some ideal military formation consisting of exactly the same smaller units. Definition 4.1: Let Req = (Ag,EReq, ϕReq), Req′ = (Ag′, EReq, ϕ ′ Req). Assume that edges of Req, Req′ are marked with labels from the one labels set. A one-to-one mapping of sets of graph vertices H : Ag → Ag′ is said to be an isomorphism of the graphs Req, Req′, if it translates adjacent vertices with the edge marked by β to adjacent vertices with the edge marked by β. On the set of all subgraphs of the graph Req (we denote it by 2Req) we can use the graph isomorphism to introduce an equivalence relation: two subgraphs are equivalent, if they are homomorphic in the sense of the above definition. Thus, it is possible to construct the factor set (2Req/ ∼). In the above example of an ideal military formation, the equivalence classes Req containing more than one subgraph are subgraphs corresponding to the telecommunication requirements for platoons, companies, battalions, and other military units of the same type. We say that two different equivalent subgraphs are maximal equivalent subgraphs if no subgraphs containing them are equivalent to any subgraph except themselves. The vertices ag1, ag2, H(ag1) = ag2 of two maximal equivalent subgraphs can be identified with each other by introducing the equivalence relation on the set of agents, assuming that ag1 ∼ ag2 if H(ag1) = ag2. Denote Ag = (Ag/ ∼). Definition 4.2: Let Req = (Ag,EReq, ϕReq). The structure of the graph Req is the graph Req′ = (Ag, EReq, ϕ̃Req), where each vertex ag ∈ Ag is replaced by the corresponding equivalence class ag ∈ Ag, ag ∈ ag. Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) 138 A.V. KUZNETSOV For the most complete separation of the structure from Req, we can use the following algorithm for isomorphism construction: input: minimum diameter of the selected subgraph δ > 0 1 Req′ := Req; 2 i := 0; 3 while diam(Req′) > δ do 4 extract the maximum subgraph Reqi which is isomorphic with the isomorphism Hi to at least one other subgraph Req′ from Req′; 5 Req′ := Reqi // the way to select a subgraph will be described in 4.2; 6 i := i+ 1; 7 end 8 m := i; 9 for all Reqj ,Hj found do 10 if ag is the vertex of Reqj and is not the vertex of Reqj+1 then 11 construct the general isomorphismHδ,Hδ(ag) = Hj(ag); 12 end 13 exit; 14 end Algorithm 1: Structuring Obviously, the construction of the factor set of agent classes can also be done through predicates from PReq, assuming that agents ag1, ag2 are equivalent if the values of predicates from PReq coincide on them when all possible values of other agents from the set Ag are substituted into these predicates. Thus, it is possible to consider not all features (ag1, . . . , agq) of the agent ag, but only those that are the same for all agents of the class ag, ag ∈ ag, and distribute resources not between agents, but between classes of agents, taking into account only the total number of agents. Once we have selected the structure for a certain graph PReq and then distribute channels over the given structure, we can use this distribution option for other requirements graphs, which can be presented as a variant of implementation for the source structure in whole or in part for a sufficiently large subgraph. In this case, it is possible to achieve both scalability and portability of the solution of the resource allocation problem to other sets of agents with the same structure, and to eliminate the dependence of the solution of the problem on the current composition of agents. It remains to consider the case if the requirements graph does not consist of subgraphs which are exactly isomorphic to each other, but of somewhat similar subgraphs? In this case, we define the measure of dissimilarity of the subgraphs as follows: Definition 4.3: Let Req′ = (Ag′, EReq, ϕ ′ Req), Req′′ = (Ag′′, EReq, ϕ ′′ Req), Ag′ ⊆ Ag, Ag′′ ⊆ Ag. Assume that edges of Req′, Req′′ are marked with labels from the one set of labels. LetHε be one-to-one mapping of graph vertices, Hε : Ag′ \BAg′ → Ag′′ \BAg′′, translating adjacent vertices fromAg′ \BAg′ with the edge marked by β to adjacent vertices from Ag′′ \BAg′′ with the edge marked by β. Then the corresponding toHε measure µ of graph dissimilarity is defined as µ(Req′,Req′′) = |BAg′|+ |BAg′′| |Ag′|+ |Ag′′| − |Ag′ \BAg′| . Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) ALLOCATION OF RESOURCES ON THE EXAMPLE OF MILITARY COMMUNICATIONS SYSTEM 139 The so-defined measure of dissimilarity for isomorphic graphs Req′, Req′′ with an isomorphism H0 : Ag′ → Ag′′ is equal to zero. This measure, in essence, coincides with the biotopic distance, which, in turn, is a special case of the Steinhaus distance [15]. Definition 4.4: The mapping Hε from Definition 4.3 is called an ε-similarity of the graphs Req′ and Req′′ if µ(Req′,Req′′) < ε. If ε > 0, then one can define maximal ε-similar subgraphs on the analogy of maximal isomorphic subgraphs. That is, two ε-similar subgraphs are maximal if no subgraphs of the graph Req containing them are ε-similar with any subgraph except themselves. The mapping Hε generates the equivalence relation ag1 ∼ ag2 ≡ ag1 = Hε(ag2), and all the above considerations about constructing the structure of the graph Req. Summing up, we can say that the problem of distributing channels between agents according to a given template is replaced by the problem of distributing channels between equivalence classes of agents according to a given template, followed by replacing the agent classes with arbitrary pairwise different representatives of these classes that are currently available in the system. In other words, the graph Req of Subsection 2.1 is completely replaced by 8. The structure of the requirements graph Req′ = (Ag, EReq, ϕ̃Req) or its equivalent predicate set. 4.2. Structuring the requirements graph as a clustering task The graph structuring described in the previous subsection is inherently close to the clustering problem known in machine learning [16]. To work with such a problem, we define the function ρ : S2 → R in the space of feature vectors of agents, ρ(sag1, sag2) > 0, ρ(sag1, sag2) = ρ(sag2, sag1), sag1, sag2 ∈ S, sag1 6= sag2, ρ(sag, sag) = 0, sag ∈ S, which shows how close the types of the two agents are. If the cluster structure of the graph Req would be known in advance (in the case of a military communications system, this means that it is immediately completely known which regiments, battalions, and other units consist of the military formation for which we want to distribute frequency), then it would only be necessary to check the cluster of approximately the same size (differing by no more than E0 ≥ 0) for the isomorphism or for the ε-similarity. Although there are several methods for constructing graph isomorphisms, obviously, not all Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) 140 A.V. KUZNETSOV of them are suitable for us. To select the desired mapping, consider the algorithm below. 1 if Ag′, Ag′′ ⊂ Ag are two clusters, 0 ≤ |Ag′′| − |Ag′| < E0 then 2 Identify with the vertex ag′ ∈ Ag′ the vertex ag′′ ∈ arg min ag∈Ag′′ ρ(I(ag′), I(ag)). (4.2) 3 end 4 Introduce an additional condition in order to prohibit the choice of too dissimilar agents as similar “for lack of a better ones” ρ(I(ag′), I(ag′′)) < E1. (4.3) 5 Get the family of mappings H1 = {Mi : Ag′ → Ag′′}. From H1 we select only the injective mappingsHε : D′ → Ag′′, D′ ⊆ Ag′, resulting in a family of mappings H2. // Note that by virtue of (4.3) the map Hε may not be defined on all Ag′. 6 Denote by B(Hε) the number of edges such that if ag1, ag2 ∈ Ag′ are connected by the edge with the label β, thenHε(ag1),Hε(ag2) ∈ Ag′′ are connected by the edge with the label β. 7 From H2, we choose a map with the largest by cardinality domain D′ and with the largest value B(Hε). Thus, when choosingHε, it is necessary to maximize the value of |D′|+B(Hε). Algorithm 2: Construction of the isomorphism or the ε-similarity If the cluster structure Req is not known in advance, and the agents are represented only by their feature vectors, since we know that the agents are organized hierarchically, a hierarchical clustering algorithm with the dendrogram construction can be applied. After that, it remains only to look at the dendrogram and apply Algorithm 2 to clusters that are at the same level of the dendrogram. Table 4.1. Values of the function I for the agents from Fig. 2.1 Agent Feature Vector ag1 (1, 1, 1, 0) ag2 (1, 1, 2, 0) ag3 (1, 1, 3, 0) ag4 (1, 2, 4, 0) ag5 (1, 2, 5, 0) ag6 (1, 2, 6, 0) ag7 (1, 1, 7, 1) ag8 (1, 2, 8, 1) ag9 (2, 1, 9, 1) For illustration, consider the most simplified example of the graph Req shown in Fig. 2.1. Let the agents represented on the graph have the feature vectors shown in the table 4.1, i.e. S ⊂ Z4. Here, if I(ag) = sag = (ag1, ag2, ag3, ag4), then ag1 is the agent’s level in the hierarchy, ag2 is the number of some community of agents within the hierarchy level (for example, “1 motorized rifle platoon of 1 motorized infantry battalion”), ag3 is the agent’s identifier, ag4 is the sign of whether the agent is the leader (for example, a platoon commander). As a measure of the dissimilarity of the objects ag1 and ag2, I(ag1) = sag1 = (ag11, ag 2 1, ag 3 1, ag 4 1), I(ag2) = sag2 = (ag12, ag 2 2, ag 3 2, ag 4 2) we use Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) ALLOCATION OF RESOURCES ON THE EXAMPLE OF MILITARY COMMUNICATIONS SYSTEM 141 the function ρ(sag1, sag2) = 3∑ i=1 [agi1 − agi2] + 1 2 [ag41 − ag42], (4.4) where [x− y] = 0 if x− y = 0 and [x− y] = 1 in all other cases. Fig. 2.1 with a dashed line shows that, for example, when clustering from agents with a dissimilarity measure ρ, which is strictly less than 2, we get the clusters Ag′(2) and Ag′′(2) (and possibly others). When forming clusters from agents with a dissimilarity measure ρ, which is less than 5, we obtain only one Ag′(5) cluster. If we choose as the corresponding pair of agents from Ag′(2) and Ag′′(2) for which ρ is minimal (step 1 of Algorithm 2), then we get the isomorphism H : Ag′(2)→ Ag′′(2) specified in Table 4.2. In general, several options for constructing an isomorphism are possible, but due to the construction of the function ρ (4.4), the “leading” agent in one cluster will always go to the “leading” agent in the other, which is fundamentally important in applications. Table 4.2. Construction of the isomorphismH : Ag′(2)→ Ag′′(2) Agent in Ag′(2) ag1 ag2 ag3 ag7 Agent in Ag′′(2) ag6 ag5 ag4 ag8 The value of ρ 2 2 2 2 As a result of applying of the structuring algorithm with the minimum diameter of the extracted subgraph 2, we obtain the graph shown in Fig. 4.3, ag1 = {ag1, ag6}, ag2 = {ag2, ag5}, ag3 = {ag3, ag4}, ag4 = {ag7, ag8}, ag5 = {ag9}. Thus, we have the graph with Fig. 4.3. Structure Req′ of the requirements graph from Fig. 2.1 five vertices instead of the requirements graph with nine vertices. If we take a smaller minimum diameter of the selected subgraph, then it would be possible to construct a structure with three vertices. When constructing the communication graph Γ, this can significantly accelerate the frequency distribution process, since it will be necessary to look through almost half as many vertices of the requirements graph. Note that in the analysed case, the rules for constructing the graph Req from the set PReq mentioned in Section 3 are formulated as follows: 1. If ag1 6= ag2 and ρ(I(ag1), I(ag2)) < 2, then the vertices ag1 and ag2 must be connected by an edge marked with cf2. Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) 142 A.V. KUZNETSOV 2. If (I(ag1)) 1 = 1 and (I(ag1)) 4 = 1, and (I(ag2)) 1 = 2, then the vertices ag1 and ag2 must be connected by an edge labelled cf1. 3. If (I(ag1)) 1 = 1 and (I(ag1)) 4 = 1, and (I(ag2)) 1 = 2, then the vertices ag1 and ag2 must be connected by an edge labelled cf2. If F = {(f1; cf2), (f2; cf2), (f3; cf2), (f4; cf1)} and fhave(commi; ccomm2) = agi, 1 ≤ i ≤ 9, fhave(comm10; ccomm1) = ag9, fhave(comm11; ccomm1) = ag7, fhave(comm12; ccomm1) = ag8, and also fcomm(ccomm1, cf1) = fcomm(ccomm2, cf2) = 16, fcomm(ccomm2, cf1) = fcomm(ccomm1, cf2) = 0, then we can easily obtain the communication graph shown in Fig. 2.2 from the graph Req shown in Fig. 2.1, or from the structure Req′ requirements graph (Fig. 4.3) in accordance with the rules of Section 2.2. 5. EXAMPLE OF THE COMMUNICATION SYSTEM BASED ON THE STRUC- TURAL APPROACH We have presented a formal description of the problem of channel distribution over the agent system in accordance with a given template. This description corrects almost all the shortcomings of the conventional approach, given at the beginning of the work. There is only one question lefts: is it possible to build a communication system that generally eliminates a single distribution centre for a channel resource, but which can occupy communication channels in accordance with the mission of each agent, and not chaotically? As the answer to this question, we propose the telecommunication system depicted in Fig. 5.4, which is a further development of the system described in [11]. Let each agent ag ∈ Ag “knows” its Fig. 5.4. Scheme of the hierarchical self-organizing network feature vector (descriptor) I(ag) = (ag1, . . . , agn) and the predicate family PReq. Further, each agent can have three roles: 1) the main communication control centre (MCCC); 2) the communication control centre (CCC); 3) the network node – communication centre (CC). Agents can change their roles as necessary. The cognitive radio device described in [17, 18] may be proposed as the prototype of the real telecommunication device with such functionality. All agents have one common technological grid of channels F ′ ⊂ F . The functioning of the communication system in brief looks like described in Algorithm 3. The work of the algorithm is additionally illustrated by the UML diagram in Fig. 5.5. As mentioned earlier, if necessary, the encryption and the authentication of the beacons can be carried out using an asymmetric RSA type cryptosystem. Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) ALLOCATION OF RESOURCES ON THE EXAMPLE OF MILITARY COMMUNICATIONS SYSTEM 143 1 agM ∈ Ag with the role “MCCC” selects the best in certain sense channel ft ∈ F ′ and starts transmitting its descriptor dM = I(agM) on it as a part of a configuration beacon (CB), which also contains the response channel fr ∈ F ′. Agents with other roles sequentially cycle through the channels from F ′ and wait for some descriptor to be received. At the same time, “MCCC” is waiting for answers on the channel fr ∈ F ′ 2 If the agent ag1 with the role of “CCC” or “CC” and the family of predicates PReq found CB with the descriptor d2 ∈ S of the agent ag2, such that from the predicates in accordance with (3.1) ag1 and ag2 should be connected in the process of cycling through the channels, then ag1 sends a response beacon (RB) via channel fr containing the descriptor d1 = I(ag1) and the transmitter identifier comm ∈ Comm. 3 When “MCCC” receives a sufficient amount of RBs, it constructs a fragment of the graph Req from the descriptors of the agents and the corresponding transmitter identifiers and solves, according to the rules PReq inside the MCCC, the problem of distribution of the channels for this fragment. The resulting fragment of the communication graph Γ is sent to all registered senders of the RB as a configuration data packet (CD). Thus, “MCCC” divides the frequencies set F into the subsets Fi, ∪iFi = F between the agents agi with the role of “CCC”. 4 The agent agi with the role of “CCC”, after receiving the CD, configures its devices in accordance with CD and starts transmitting CB at a certain frequency f it ∈ Fi, similar to the same as “MCCC”. 5 Assume that the agent ag1 has the role of “CC” and the family of predicates PReq. Also, assume that the agent ag2 with the descriptor d2 ∈ S must be connected with a1 in accordance with (3.1). If ag1 in the process of searching the channel founds CB from “CCC” with the descriptor d2 ∈ S, then ag1 sends the response beacon (RB) via channel fr, containing the descriptor d1 = I(ag1) and the transmitter identifier comm ∈ Comm. 6 When “CCC” receives a sufficient amount of RBs, it builds a fragment of the graph Req from the descriptors of the agents and the corresponding identifiers of the transmitter and decides according to the rules inside it PReq for it distribution channel resource problem. The resulting fragment of the communication graph Γ is sent to all registered senders of the RB as the configuration data packet (CD). Thus, “CCC” distributes the frequencies from F between agents agi with the role “CC”. Algorithm 3: Operation of the communication system 6. CONCLUSIONS AND PERSPECTIVES The article presents a mathematical description of a special kind of the resource allocation problem in accordance with a given template. An algorithm for the structuring the set of resource consumers is also proposed. It should be noted that this problem is not necessarily related to radio communication systems and frequency distribution. “Channels” may correspond, for example, information channels of different bandwidth with specified QoS between users of different ranges in the wide area network. Also, there can be options for laying railway tracks between settlements with “given channels” for a given matrix of connectivity of settlements and with a restriction on the total length of rails. The choice of the problem statement presented in the article using the conceptual apparatus of graph theory is connected with the fact that the author used precisely such constructions in creating a simulation model of the movement and the communication of hierarchically organized agents, including for visualizing changes in the state of the communication system. The above model is based on a cellular automaton simulating the Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) 144 A.V. KUZNETSOV Fig. 5.5. Beacons Exchange movement of groups of agents over rough terrain [19]. Moreover, the vertices of the graph Γ at each moment of time are mapped to the cells of the automaton in which the agents are located. In the process of movement, the agents lose each other out of visibility due to the characteristics of the terrain being travelled, as a result of which there is a need to rebuild the communication graph Γ. The author thinks the requirements graph as the imaginary device that generates an endless stream of communication graphs according to certain rules. So, the structure of the communication system can be represented by entities of the codata type. Further development may be in the direction of improving measures of dissimilarity for communication requirements graphs. For example, we can represent the communication requirements graph in the form of the state transition model and replace the isomorphism of subgraphs in the definition of the dissimilarity of subgraphs with relations of mutual simulation or bisimulation. REFERENCES 1. Lazarev, A., Musatova, E., Gafarov, E., & etc. (2012) Teorija raspisanij. Zadachi zheleznodorozhnogo planirovanija. Nauchnoe izdanie. M.: IPU RAN. 2. Afraimovich, L. G. & Prilutskii, M. K. (2006) Multiindex resource dis- tributions for hierarchical systems. Autom. Remote Control, 67, 1007–1016, https://dx.doi.org/10.1134/S0005117906060130. 3. Prilutsky, M. K. & Dikarev, K. I. (2012) Resource allocation in hierarchical systems containing active components [in russian]. Vestnik NNGU, 181–189. 4. Vittikh, V. A. & Skobelev, P. (2003) Multiagent interaction models for constructing the needs-and-means networks in open systems. Automation and Remote Control, 64, 162– 169. 5. Byhovskij, M., Vasil’ev, A., & Lashkevich, A. (2012) Osnovy upravlenija ispol’zovaniem radiochastotnogo spektra: Chastotnoe planirovanie setej teleradiovesh- hanija i podvizhnoj svjazi. Avtomatizacija upravlenija ispol’zovaniem radiochastotnogo spektra, vol. 3. Moskva: Krasand. 6. Geniatulin, K. & Nosov, V. (2014) Using of vertex-paint and paint-vertex algorithms to modify coordinating rings method in frequency-spatial planning of mobile satellite communication system with zonal maintenance [in russian]. Vestnik SibGUTI, 23–36. Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) ALLOCATION OF RESOURCES ON THE EXAMPLE OF MILITARY COMMUNICATIONS SYSTEM 145 7. Nosov, V. (2007) Metody obespechenija jelektromagnitnoj sovmestimosti v setjah radiosvjazi. Vestnik SibGUTI, 52–56. 8. Oshmarin, D. (2010) Raspredelenie kanal’nyh resursov v setjah kognitivnogo radio na osnove teorii igr. Biznes-informatika, 38–45. 9. Bessonov, V. & Kuznetsov, A. (2010) Communication system mathematical model [in russian]. Teorija i tehnika radiosvjazi, 58–64. 10. Bessonov, V., Kruchinin, S., Kuznetsov, A., & Sviridov, A. (2011) Object- linguistic model unified visual projection counseling and format storage and transfer data communication system based on XML [in russian]. Vestnik Voronezhskogo Gosudarstvennogo Tehnicheskogo Universiteta, 7, 56–60. 11. Kuznetsov, A. & Zharkov, S. (2016) A special wireless network configuration over a secure radiochannel [in Russian]. Jelektrosvjaz’, 28–35. 12. Redi, J. & Ramanathan, R. (2011) The darpa wnan network architecture. In 2011 - MILCOM 2011 Military Communications Conference, 2258–2263, https://dx.doi.org/10.1109/MILCOM.2011.6127657. 13. Sumaiya, B. D., Nithya, R., & Prasanth, K. (2014) Energy efficient hierarchical cluster based routing protocols in wsn – a survey. International Journal for Innovative Research in Science & Technology, 1, 261–266. 14. Pelillo, M. (1999) Replicator equations, maximal cliques, and graph isomorphism. Neu- ral Computation, 11, 1933–1955, https://dx.doi.org/10.1162/089976699300016034. 15. Marczewski, E., Steinhaus, H. (1958) On a certain distance of sets and the corresponding distance of functions. Colloquium Mathematicum 6.1, 319–327, http://eudml.org/doc/210378. 16. Jain, A. K., Murty, M. N., & Flynn, P. J. (1999) Data clustering: A review. ACM Comput. Surv., 31, 264–323, https://dx.doi.org/10.1145/331499.331504. 17. Bessonov, V. & Kuznetsov, A. (2014) The technology for creating ad hoc radio network with functions of cognitive radio on the principles of software defined radio [in russian]. In Kibernetika i vysokie tehnologii XXI veka. XV Mezhdunarodnaja nauchno- tehnicheskaja konferencija. Voronezh: NPF Sakvoee OOO, 176–187, no. 2. 18. Obel’chenko, M., Bessonov, V., Kuznetsov, A., & Mohrjakov, V., Telecommunication network data transmission means and telecommunication network // patent for an invention no. ru 2549120, publ. 20.04.2015. 19. Kuznetsov, A. V. (2017) A Model of the joint motion of agents with a three- level hierarchy based on a cellular automaton. Computational Mathematics and Mathematical Physics, 57, 340–349, https://dx.doi.org/10.1134/S0965542517020099. Copyright © 2020 ASSA. Adv Syst Sci Appl (2020) Introduction Statement of the problem Objects Conditions Model Deficiencies Distribution of resources, depending on the role of the agent and in conditions of insufficient resources Structural Similarity Definitions Structuring the requirements graph as a clustering task Example of the communication system based on the structural approach Conclusions and Perspectives