This paper discusses ways of structuring networks using clusterization. In the work, the probabilities of reaching fixed network nodes are calculated for various characteristics of a data transmission system. It will be shown here the clustarization in the network allows us to specify digraph, the numbering of vertices in which makes it possible to calculate the stages of transmission using multiplication table of substitution.
Currently, the systems based on the network organization are of great interest. Moreover, equally determined challenges are
faced both by the sphere of development of the material components of data transmission tools, in particular, in the field of
quantum communication [
The connectivity criterion for such networks is described in detail in the articles [
a) b)
Figure 1 – An example of connectivity in the sensor network (a) and clustering (b) [
The sensory node interconnection area s is the area in which one sensor node can interact with other sensor nodes. The limit of interconnection (Ri) of an arbitrary sensor node sj is the maximum distance between nodes si and sj, where sj is within the interconnection range si.
The number of sensors closest to the node is calculated as : , where d is the Euclidean distance between si and sj. With this in mind, the connectivity criterion can be defined as following: | |.
From the mathematical point of view, this condition presents the Delaunay condition for the (R, r)-system: the distance from any point of the set to the point of the same set nearest to it is greater than or equal to some fixed segment of length r, and the distance from any point of space to the closest point from the one of the system points are less than or equal to some fixed segment of length R (Figure 2a).
As an example of such an (r, R)-system can serve a system containing symmetry, which Delaunay first used to describe
the periodic structures of the material. A similar approach can also be applied to clusterization networks based on the
principles of symmetric partitioning of space (with the topology of the dual symmetric graph selected as a network model
(Fig. 2b) [
An area is counterposed to a node or a set of nodes combined into one cluster. Space consisting of equal squares
polyominos, the connection between nodes (or Clusters Head) is depicted for the case, when the polyominos has joint sides.
Thus, if a neighbourhood relation is given on the set of polyominos, one can always proceed to the geometrical description
of the network in the form of a graph. To implement a clustering procedure based on symmetric partitioning, layer-by-layer
growth algorithms for partitioning and packaging, elementary polyomino clusters [
In this way, the connection is being formed between the nodes located in such an area, the connected nodes are usually
called adjacent. Network reliability is determined by the number of "neighbours": the more connected nodes there are, the
more reliable is the network: the failure of one of the sensors should not affect the ability of data transfer, which can be
implemented through any alternative routes [
a) b)
By analogy with crystals (Figure 5b), whose growth can be modelled in a discrete periodic space, the formation of links can occur in a discrete periodic space, where to each network node an elementary descriptor of such a space is assigned — i.e. polyomino. The neighbourhood relation of the set of polyominos also makes it possible to form a connection between the nodes corresponding to the neighbouring (possessing a common side) polyominos (Fig. 6).
When moving to a “virtual” discrete space, where connections arise in accordance with a given polyomino
neighbourhood relation, it becomes possible to structurize the logical topology, including the case of a chaotic distribution
of nodes in the sensory field (for example, Poisson ensemble). In such a network, there should not be any problems with the
"inclusion" even of such nodes in the network, which doesn't possess radio coverage of any node. The sensor nodes in such
a network may have mobile properties, since their logical topology does not depend on the location of the nodes in real
space, and the nodes in the network will have a guaranteed number of "neighbours", that in itself ensures the reliability of
the network. The presence of symmetry in a discrete network space (built out from the polyominos) allows one to select a
fundamental area in it, the transmission of which completely defines the space itself, which can be used as an element of
standardization in algorithms [
Let's consider, that the clusterization of the network on the principles of symmetric partitioning has been carried out (Fig. 7), and the routing problem has been posed for a finite number of nodes (in order to reduce calculations).
It is necessary to determine the systems properties which can be implemented by various algorithms for finding optimal routes in order to estimate the probability of channeling the data packet from one arbitrary node to another. By analogy with the properties of an intellectual system, we can distinguish the following properties:
1. “The Faith” — characterizes the purposefulness of the system (confidence in the ability to reach a certain node). Grades of Faith are: • no faith — no data packet is being sent; • absolute faith — passing of a data packet through a node is possible only in one direction and is impossible in the opposite direction; • doubt — passing of a data packet is possible in the given and in the opposite direction.
2. “The Memory” — describes the ability of the system to store information about various routes and, if necessary, to remove the inefficient routes.
3. “The Knowledge” — describes the ability of the system to predict and choose the shortest route.
For the network shown in Figure 5, the probability of reaching a data packet from any arbitrary node (for example, 8) to any other arbitrary (for example, 16) can be estimated.
Doubt.
Memory.
Knowledge.
No data packet is transmitted. The system has no purpose. P = 0
There is a chance to get into the "dead-end" nodes, to which only one communication channel leads (9, 12, 18). The probability of reachability can be calculated through the probability of a reverse event: to get to the "dead end" node. P = 0.82.
Data transfer may loop, and the data may not reach the specified node. Possible cycles (1-10-2-0-1), (2-11-3-0-2), (8-1-0-6-7-8), etc. P = 0.5.
The data will be delivered to any node with a probability of P = 1, however, the delivery time without knowing the optimal routes can be long.
The route is selected following the optimal criterion: the shortest in the number of intermediary nodes or the buffering time. P = 1, the gain in time in comparison with the previous condition.
We give a calculation of the probability for the case: “Absolute faith. No memory. No knowledge.” It is necessary to enumerate all possible routes from node 8 to nodes 9, 12 and 18, which are considered to be “dead ends”, then find the probability of passing a packet of data from node 8 to node 16 as well as the probability of a reverse event of falling to a “dead end”. P (hit from 8 to 16 nodes) = 1-0.178 = 0.822. Determining the shortest paths with the smallest number of intermediary nodes allows one to concentrate on calculating the probabilities for the following 6 routes (Fig. 8).
The pre-condition providing the minimum number of intermediary nodes was chosen as a criterion for obtaining the optimal of all possible routes (therefore, only routes with 3 and 4 mediators were considered in this calculation), the probability of choosing this route, determined by the degree of vertices in the network graph (probability from 1 node to get to 0 – 1/3, and from 0 to 6 node – ¼) was taken into consideration. The result of multiplying of the probabilities at all nodes that fall in the route gives the total probability of choosing this route and can signify the measure of its effectiveness (priority in the process of choice when the system possesses “ the Knowledge”). 15 14 a) 8 1 17 16
18 17 16 18 7 7 1 15 14 6 0 5
It can be seen from the data in the table 2 above, that route (a) contains the minimum number of choices, therefore passing of the data packet along it will be characterized by the highest speed (the time for buffering is reduced), and the probability of reaching a given node along this route is the maximum one. But if the system possesses “the Knowledge”, that is, the complete information about the logical structure of communication nodes, a quick calculation of the shortest route (not occupied and not containing nodes that have failed) allows the system to deliver data to the destination node rapidly. This confirms the increase in network efficiency due to the introduction of “intellectual” properties to the system through appropriate algorithms.
Let us return to the analysis of the network graph presented in Figure 7. If we consider the network topology, we can see that node number 0 is located in the center and has indirect or direct communication with all nodes of the system, and therefore we'll call it server node and set the task of collecting data from all system nodes into it. Excluding the cycles (for example 1-10-2-0-1)), we define a directed graph of the network. Information may be collected continuously or according to a schedule set by the user.
As it was already shown by the authors in [
Initially, there is a g [0] permutation (substitution, because the numbers are repeated) describing the relationship of all nodes: g[0] = (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20).
By transferring data from node to node, one can get the following substitution g[
It can be concluded from the above-mentioned version of substitutions and the presented table, that the complete transfer
of information from all nodes of this network will take place already in the third step of routing. This can be used to
algorithmize the process of collecting data into the server, as well as estimating the number of steps necessary for the
system to be able to accumulate data into a common center for further processing and prediction of the systems operational
behavior. It should be noted that the substitutions constitute the so-called broken symmetry group [
The presented ideas can be used for the automatization of the procedure of collecting biometric data of any given person or to predict the weather in a network of sensor nodes distributed in a certain area.
This article discusses ways of structuring networks using clusterization, a method of clusterization based on translational partitions of space (flat surface) is proposed, allowing the increase of the efficiency of the network with regard to the failure of nodes. A comparison of networks' efficiency depending on the presence of properties of intellectual systems in them was carried out; the probabilities of data reaching the destination node for various combinations of properties were estimated. For example, the introduction of a route memory algorithm in the considered system allows increasing the probability of 426 reaching a destination node up to 82%. And if the algorithm for comparing routes in the network is implemented, then choosing the optimal route allows you to save transmission time (the difference between the transmission efficiency of neighboring routes is 2-3%). The possibility of automatization of the process of assembling the data to a server (central) node using the procedure of multiplying substitutions according to a given oriented graph is shown. In the demonstrated example, the number of intermediary nodes in the sensor network is calculated (it is 3) which is necessary for data transfer to the server.
Acknowledgements The authors would like to acknowledge financial support from the Russian Foundation for Basic Research under the grant No.18-07-00170.