=Paper=
{{Paper
|id=Vol-2588/paper47
|storemode=property
|title=Analysis of the Optimization Problem of the Cyber-Physical Objects Distribution
|pdfUrl=https://ceur-ws.org/Vol-2588/paper47.pdf
|volume=Vol-2588
|authors=Siarhei Palavenia,Yuliya Duinova,Marina Popova
|dblpUrl=https://dblp.org/rec/conf/cmigin/PalaveniaDP19
}}
==Analysis of the Optimization Problem of the Cyber-Physical Objects Distribution==
https://ceur-ws.org/Vol-2588/paper47.pdf
Analysis of the Optimization Problem of the Cyber-
Physical Objects Distribution
Siarhei Palavenia [0000-0002-1151-7625], Yuliya Duinova [0000-0002-3795-4428],
Marina Popova [0000-0001-6290-9162]
Belarusian State Academy of Telecommunications
s.polovenia@gmail.com
Abstract. The article discusses the movement of one and a group of cyber-
physical objects in the form of a telecommunication system with queues or a
queuing system. Their interaction in the group and the exchange of information
between them with minimal delays and the highest speed are described. The
conditions of optimal interaction are shown, the analysis of the distribution
functions of applications depending on the number of objects in the group is
carried out.
Keywords: Сyber-physical objects, Queuing system, Group Interaction,
Telecommunication system.
1 Introduction
An important role in the successful implementation of modern information
technologies within a particular subject area is played and will be played by the
relevant unified information space. In general, under these spaces is understood a set
of data and knowledge, organized in a special way and built with the use of database
systems, file storage and technologies for their use, as well as information and
telecommunication systems and networks that operate according to general rules and
provide information interaction and access to consumers geographically distributed
information resources of organizations and enterprises involved in improving the
information system. In connection with the emergence and widespread
implementation in practice of cyber-physical and mobile robotic systems, as well as
the need to organize individual and group management of them, the issues of
formation of unified information spaces that ensure effective interaction of these
systems are of particular relevance [1].
Cyber-physical systems – a new technological paradigm that combines various
information and telecommunication systems from the standpoint of isolation and
integration into a single whole layer of physical elements and their information
displays. Along with the Internet of things, BigData technologies and pervasive
sensor networks, cyber-physical systems form the technology platform for Industry
4.0 [2, 3]. In view of the pervasive spread of cyber-physical systems, developers of
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0) CMiGIN-2019: International Workshop on Conflict Management
in Global Information Networks.
specialized software and hardware solutions are searching for unified approaches that
would simplify the development of various solutions in the field of cyber-physical
systems and reduce the cost of creating specialized control and monitoring systems. In
addition, the existence of a unified approach will simplify the problems associated
with scaling, which will arise with the further expansion of the considered systems
[4].
2 Models of cyber-physical objects
The cyber-physical approach allows to consider information aspects of
communication and interaction of objects of management among themselves and with
an external environment. The cyber-physical model describes the processes of
formation or antientropy, i.e. organized movement of objects of reality taking into
account information influences. CPhS is a much more general concept for the terms
«robot» and «artificial intelligence», representing in some cases the integration of the
two concepts. In the general case of cyber-physical object – the object that is data-
driven.
Each robot is a cyber-physical object that corrects its state, reacting to the impact
of the surrounding physical and information environment. Due to the widespread
introduction of digital technology for the collection, storage, processing and
transmission of robot data, any modern robotic object exists exclusively in digital
reality. Each physical object surrounding the robot is represented in its memory in the
form of digital information. If something cannot be measured and recorded, it simply
does not exist for a robot [5].
The concept of CPhS is comprehensive. Under certain conditions, a significant part
of the phenomena of the modern world can be called CPhS.
According to the format of devices, CPhS can include global «systems of
systems», their individual components, sensors and measuring instruments, objects of
any size and scale.
CPhS includes both hardware and computing parts. Each of these components, in
turn, can interact with most modern technologies.
The term «CPhS» can be used both to describe a particular device and to describe a
system or concept (implying the integration of a computational component into a
physical process).
The model of infocommunication system assumes division of interaction space into
three levels (domains), each of which is connected with groups of objects of the
General nature – physical, information (cybernetic) and cognitive. These objects
represent the entities of the respective domains – physical (PhD), information (ID)
and cognitive (CD). Appropriate interfaces are implemented at domain boundaries to
allow interaction between system elements. Each element of the system has a finite
ordered set of States that define the element's own thesaurus.
CPhS and CPhO exist in cyberspace, which is a fundamentally new environment of
confrontation between competing States, not being geographical, but being
international.
At the heart of any cyberphysical system is the model of the cyberphysical atom
(CPhA). The atom is the smallest indivisible element of the system. Accordingly, the
CPhA describes one entity of the physical domain and its corresponding cybernetic
part. Both of these entities form a single complex that exists in PhD and ID.
The transition from the physical domain to the information domain is realized with
the help of various devices-sensors (sensor). The reverse transition is performed by
actuating devices (actor).
CPhA must be considered to formally describe the behavior or state of an
individual cyber-physical object, for example, if the system operator aims to analyze
an individual object operating within the system. However, the cyber-physical
network is traditionally represented as a network of interacting CPhOs, in which case
the CPhA will be the basis for further, more complex abstractions.
The CPhT is based on the topological description of the CPhA network. CPhT
defines the graph of the cyber-physical atom network. The main descriptor of CPhT is
a connectivity matrix.
Cybernetic or information exchange is implemented through various protocols and
its features are described by the information communication operator of the «cyber-
object – cyber-object» type.
CWTS together with the CPhA set are theoretically capable of fully describing any
cyber-physical network, but a few more abstractions may be required for ease of
simulation. The following model describes a cyber physical cluster (AS). This model
shows its useful properties in the problems of scaling CPhO networks. If it is required
to operate with a significant number of cyber-physical atoms and cyber-physical
typology, when whole constellations of CPhA and segments of the general cyber-
physical typology need to be considered as a single entity, it is advisable to use CPhC.
Accordingly, the complex network of a cyber-physical object can be simplified to
describe a connection between several cyber-physical clusters.
Although any CPhS can be described in terms of a cyber-physical topology or
using Bazis CPhT, this approach does not allow to reflect genetic relationships in
cyber-physical network as well as the process of evolutionary transitions, sub-
processes, etc. at the same time, such information is essential as the selection of
classes and instances of classes will allow you to install respective Parallels in the
thesaurus of the monitoring subsystem and to structure the process of presenting
information to the operator. Thus, to describe the hereditary relationships within the
CPhS, we will use the cyber-physical hierarchy.
Сyber-physical hierarchy completes the set of models used to describe CPhS.
However, further research aimed at modeling CPhS may lead to the need to create
additional classes of models.
3 Dynamics of the behavior of a cyber-physical object
The movement of CPhO in three-dimensional space, interaction in the group and
the exchange of information between them with minimal delays and the highest speed
can be described as a telecommunications system with queues or Queuing system.
Each CPhO is a node of the network capable of being at rest or moving according to a
given algorithm.
If we assume that one CPhO is the master, and the rest are static in space , then the
movement of the leading CPhO during the interaction s t0 v , where t0 – the
time of interaction with one node of the network, v – its speed of movement. For
t0 v
correct description it is necessary that 0 , where R - radius of coverage
R
area.
If v 0 and t0 0 , then the connection at the boundary of the circle by radius
R is lost (figure 1).
v
R
Fig.1. Unserved nodes on the zone boundary at v 0
With a known time spent in the service area of the node is determined by the
boundary of the area in which the node is guaranteed to be serviced at a known speed
of the leading CPhO. With minimal maintenance time t0 , the distance to the zone
boundary is equal to (figure 2):
S c t0 v
At interaction of a set of nodes CPhO can be considered as Queuing system on
which input applications arrive, in a certain priority [6].
v
SC
( x0 , y0 )
Fig. 2. Service Area of CPhO at v 0
Nodes that are not serviced will be refused. The flow rate is determined by the
value R , the number of nodes in the service area and the speed of the leading CPhO.
Time is spent on servicing each request, during which the node must be in the zone
R (figure 3).
r1
r2
( x0 , y0 ) v
ri
R
Fig. 3. CPhO Interaction with network nodes
Depending on the determination of the coordinates of the nodes, two service cases
are possible. If the coordinates of the nodes are known, then a deterministic flow of
requests enters the system. In this case, the optimal operation will be according to a
certain service rule.
If the coordinates of the nodes are not known, then a random stream of requests
enters the system. In this case, you need to know the probability of denial of service
from the system settings.
For the first case, the number of nodes interactсing with the leading CPhO is equal
to:
R
k MAX
v t0
where is the k – number of interacting nodes.
The number of nodes depends on the time spent in the interaction area and location
in space (figure 4).
v v
SC SC
( x0 , y0 ) ( x0 , y0 )
Fig. 4. Examples of node placement in the service area
Let there be a node in the service k area, and the time spent in it is equal to:
ri
ti
v
where is the ri – distance from the node to the boundary of the i -st node.
It takes time to maintain each node t 0 . When you select the interaction sequence in
which the number of serviceс nodes is maximum, the initial point in time t1 0 and
one node is serviced at the same time. Then the start time of the j node is equal to
t j ( j 1) t0 .
To solve the problem, you need to determine the order of service nodes, which
would be served their maximum number.
In the second case, when the coordinates of the nodes are unknown, the following
restrictions are required:
– the number of static nodes is constant and represents a Poisson field,
– the leading CPhO moves rectilinearly at a constant speed,
– the interaction zone has the area of a circle with a radius R .
We define the distribution function for the incoming flow of applications. To do
this, consider the CPhO service area at time 0 and at time t .
During the time t the system will receive those applications (nodes) that are in the
area shown in figure 5.
According to the properties of the Poisson field, the probability that in some region
is n the number of nodes is determined by the Poisson distribution and depends only
on the area of this area.
The probability that in the S will be m knots, equal
am a
Pm e
m!
where a S (t )
– is the number of nodes per unit area;
S (t ) – the area of the region.
( x0 , y0 ) v
R
vt
Fig. 5. Probability of hit n nodes in the region S
S (t )
m
P (t )
m e S ( t )
m!
The area of a given area is
S (t ) 2 R vt
m=1
m=2
m=3
m=4
m=5
Fig. 6. Distribution Function of the number of applications m 1...5
The flow rate, i.e. the average number of applications per unit of time, will then be:
2R v
Consider a random variable T – the time interval between two adjacent events in
the stream – and find its distribution function:
F (t ) P(T t )
The probability that the time interval is long t m applications will be received,
equal to:
P(T t ) 1 F (t )
P(T t ) p0 (t ) e 2 Rvt
The distribution function of the time interval between applications has the
following form (figure 7):
F (t ) 1 e 2 Rvt
Thus, the input of the system receives a stream, the time intervals between
applications in which are distributed with an average value:
1
a
2R v
and dispersion:
1
a2
4( 2 Rv) 2
Fig. 7. Time interval distribution Function between applications
If the time of stay of the node in the interaction zone is not limited, then:
2
K 1
1 2
2
P 2
Ca Cb
2 2
K 1
1 C a C b
where t0
Ca – coefficient of variation of the time interval between applications;
Cb – coefficient of variation of service time;
K – number of waiting places in the queue.
In this instance Ca 1, Cb 0 , with this in mind
1
P 2K
1 2 K 1
4 Dynamics of the behavior of a group of cyber-physical objects
When considering the problem of data collection from nodes located on a large
territory, it is advisable to consider the possibility of using a group of CPhO.
The CPhO group can be represented as a queuing system [7].
The flow of requests (messages) coming to the node of each of the CPhOs, i it
has the properties of the simplest flow of applications.
Host message output i with probability rij fed to the input node j .
n
With probability 1 r applications leave the node i and are directed to the
j 1
ij
external environment.
Service time on the route section t it consists of the time of transmission of the
message on the channel and the standby time of the ready state channels that
are random.
Channel state change is a random process that occurs under the influence of a
variety of independent factors, such as input and output from the communication
zone, due to a random deviation from a given trajectory, the impact of interference
from transmitting devices located on other elements of the system, etc. With a
sufficiently large number of such independent events, the channel readiness intervals
will have a distribution close to exponential.
r25 5
2 n2 n5
r23
r35
n3 r45
r31 r43
4
1 n1 r14 n4
3
Fig. 8. Data delivery route model between source (s) and receiver (t)
As shown in [8], the average delivery time in such a network can be estimated as:
M j
T Tj
j 1
where M - number of channels in the network;
n – number of nodes in the network;
1
Tj – delay on the j -th channel;
j j
n
i – total network traffic;
i 1
j – total traffic in the j -th channel;
1
j – service intensity in the j -th channel;
tj
Delivery times for a particular network route can be estimated using Jackson
network properties. It is known that each of the nodes of such a network can be
considered as an independent Queuing system M/M/1, and the entire route-as a
sequence of independent Queuing systems M/M/1.
The function of distribution of time of delivery of the message on a route in such
system can be described by distribution of Erlang. By i and i
ti t 1 i 1,..., m , with an average of m t , which is the average delivery
time of the message along the route k mk t , where mk – number of channels in
k -m route.
m (m x) m1 m x
S ( x, m) e
(m 1)!
The order m in this case corresponds to the number of transitions, assuming that
the message transmission time on each of them is the same.
The approximation of the network in question by the Jackson network is probably
the more accurate the larger n and the closer the service time distribution is to the
exponential distribution. With a relatively small number of nodes and a small number
of routes, network properties can differ significantly from Jackson network properties.
In such a case, the route model can be described as a multiphase g/G/1 system.
Obtaining a delivery time allocation function in this case can be very difficult.
m=5
m=4
m=1
m=3
m=2
Fig. 9. Probability Density of delivery time along a route length of m 1, 2,3, 4,5 transitions
However, an approximate estimate of the average delivery time in the j -th
channel of the route is possible, as shown in [9]:
j tj a t tj t
2 2 2 2
Tj j
2 j
j
2(1 j ) t j 2 a j t2
j
where j j t j
a2j – dispersion of intervals between messages;
t2j – the variance of service time in j -th channel;
t j – service time in channel j ;
1
aj – the average value of the interval between messages in the j -th
j
channel.
Then the delivery time on the route will be equal to:
mk
k Tj
j 1
where mk – number of channels in the k -th route.
The probability of connectivity can be defined as the probability of hitting a sphere
of a given radius. From the properties of the Poisson field, this probability is:
P1 1 e a
where a V the expectation of the number of points in a sphere.
4
V x3 – the volume of the sphere of radius x;
3
– node density (number of nodes per cubic meter).
Then the dependence of the probability of connectivity on the density and radius of
the network node is equal to:
4
x3
P 1 e 3
If the boundary is a plane, then the volume in which communication with a
neighboring node is possible is half that for a node located near the center of the
considered area.
5 Conclusion
The above analysis shows that in the case where the location of network nodes can
be described by the Poisson field, the model of interaction between the CPhO and the
ground control point can be described by the model of a Queuing system with a
combined service discipline (expectation and losses), which receives the simplest
flow of applications. With a random distribution of nodes, to describe the quality of
service of nodes (probability of losses) is required to evaluate the coefficients of
variation of time intervals between requests (the moments of ingress nodes in range
RPO) and service time application (time of transmission).
References
1. Ronzhin A.L., Basov O.O., Sokolov B.V., Yusupov R.M. Conceptual and
formal models of synthesis of cyberphysical systems and spaces, Izv. higher
educational, Instrument Making. 2016. Vol. 59, No. 11. pp. 897-904
2. Malygin, I.G., Komashinsky V.I., Korolev O.A. Information and control
systems of water transport in the period of the fourth industrial revolution,
Transport: science, technology, management, 2017, No. 8. pp. 3-12.
3. Cyber-physical control system stevedoring company stevedore CPS eyes.
URL: http://www.plm.pw /2017/06/cps-stevedore-eye.HTML
4. Rogozinsky G.G. Multidomain approach and models of objects of
cyberphysical space in problems of information display, Proceedings of
Educational Institutions of Communication, 2017, Vol. No. 4, pp. 88-93
5. Mulyukha. A., Zaborovsky V.S., Ilyashenko A.S., Lukashin A.A. Network-
Centric method of organization of information interaction of cyberphysical
objects in the environment of cloud computing, robotics and technical
Cybernetics. 2014, No. 3 (4). pp. 43-47.
6. Kirichek R.V. Unmanned aerial vehicle as a Queuing system / R.V. Kirichek,
A.I. Paramonov, Telecommunication, 2015, No. 7, pp. 16-19.
7. Dao, N. analysis of routes in the Network based on a swarm of UAVs / N.
Dao, A. Kucheryavy, A. Paramonov, Abstract of Lectures on Electrical
Engineering (LNEE), 2016, Thom. 376, pp. 1261-1271.
8. Kleinrock, L. Queuing Systems, Vol. 2: Computer Applications, New York:
Wiley, 1976, 576 P.
9. Kleinrock, L. Queuing Systems, Vol. 1: Theory, J.Wiley and sons, 1975.