Two-Criteria Technique for the Resource-Saving Computing in the Fog and Edge Network Tiers

Introduction. Currently, applications using edge and fog network segments are widely used [1–5]. Distributed computing performed on the nodes of these segments has significant difference from distributed computing performed in cloud structures, namely, relatively high topology dynamics and, in addition, the presence of certain distances between the nodes used. This results in the need to take this parameter into account when modeling the time of information exchanges between executable tasks. The existence of topology dynamics is explained by the fact that network edge devices are, as a rule, user devices (including all kinds of sensors, smartphones, laptops, etc.) that belong to certain people and can be moved, turned off, access to data/resources may be prohibited. At the same time, all of them depend on the presence of a battery charge (power source) [6][7]. The fog layer of the network is less dynamic. However, it is also characterized by all of the above to one degree or another: the occurrence of a certain distance between nodes with the presence of transit sections of the network, the possible mobility of the nodes themselves, e.g., in case of data processing by groups of mobile devices. An interesting example in this sense are groups of low-orbit satellites that are currently used for data processing, but the nodes are displaced relative to the Earth's surface at a fairly high speed (access time is on the order of several minutes) and, therefore, the question arises about the routing and transmission of processing results to ground stations [8].

As part of the issues of resource saving of devices used in the dynamic layers of the network, a number of works have been published [9–11], in which attention is focused on energy saving. As a rule, the model assumes the dependence of the consumed energy of the device on its workload [12]. At the same time, such an important factor as saving the residual computing resource of the device remained outside the focus of research [13].

The residual computing resource of a device is a value that is closely related to such reliability characteristics as the probability of failure-free operation and gamma-percentage time to failure. Also, the average residual life, taking into account the use of the exponential law of failure rate distribution, is characterized by the following expression:

(1)

where P(x) — probability of faultless operation (PFO) of the object during time x.

For the exponential resource distribution law, the PFO is defined as:

(2)

where  — hazard rate,  > 0 .

Then, according to formula (1), the average residual life is determined from the following formula:

(3)

At the same time, there are works devoted to the relationship between the values of PFO, gamma-percentage time to failure, and the average residual resource on the temperature of the computing element of the device, which, in turn, is described as a function of the device load [14–16]. The problem of device resource saving can also be posed as the problem of maximizing the average residual resource of the device.

Thus, the problem of resource saving is considered in recent works either as a task of minimizing the power consumption of devices, or as a task of saving the residual computing resource.

However, under present-day conditions, it is reasonable to talk about two-criteria optimization of resource consumption of devices for the following reasons:

• electricity is a renewable but critical resource for the mission of the device, whether it is a sensor of an information and control system or a controlled mobile device;
• residual computing resource determines the duration of the device's expedient operation, and the operation time, respectively, is the sum of the missions performed by the device.

Therefore, the objective of this study was to develop a resource saving method for devices of dynamic network layers, within which the assessment would be carried out on the basis of two criteria — power consumption and computing resource consumption of the device.

Materials and Methods. Let us define the concept of “mission of a group of devices” as a predetermined sequence of solving by a group of devices a complex of computational tasks related to information exchanges. The mission of a group of devices can be described by an acyclic graph, whose vertices will be weighted by the complexity of the tasks, and the arcs, respectively, will determine the limits of the sequence and the amount of data transmitted by the tasks. Let the mission be described by graph W = {wl, zl, I }, where wl — complexity of the task, zl — proportion of the task completed by the time of the topology change, I — matrix of data volumes transferred between tasks. A group of devices in a dynamic network layer is described by a set of graphs, each of which defines the topology of the network at time ti. We assume that the mission execution time includes a certain time interval with discrete instants of time [t0, t1, …tk], each of which corresponds to the topology graph Gi={, H}, j=1…m, pij — performance of the j-th node of the i-th topology, eij — energy resource of the j-th node of the i-th topology, Rij — average residual computing resource of the j-th node of the i-th topology, m — number of devices in a group, H — matrix of network connections between nodes. We also assume that at each subsequent time t_i+1, for graphs G_i+1 and Gi, the following is true: at least one of the vertices belonging to Gi, will be contained in G_i+1, which is required to continue the mission.

We also assume that if the topology graph changes at time t_i+1, it is possible to reassign tasks that were performed in the i- th topology on the nodes that ceased to exist at _i+1 time, to any of the available topology nodes _i+1. At the same time, we make the assumption that the tasks transferred to new nodes start to be executed at the same place where their execution was interrupted.

Estimation of the residual computational resource will be implemented as follows: to estimate the PFO of the device of the fog layer, we will use the expressions proposed in [17, 18]:

(4)

where D — calculator load (in fractions).

(5)

where wi — complexity of the work performed.

Accordingly, PFO (t) can be estimated, as well as the average residual resource:

(6)

where t_constraint — time limit for which the task must be completed by the node to meet the mission time limit tm.

When estimating the residual energy resource, we also assume that the energy consumption is proportional to the workload of the computing node, and there are no more energy costs:

(7)

where Ej0 — initial level of energy available, Ejm — residual level,  — coefficient expressing the relationship between the load of the computing element and its energy consumption.

The result of the operation of the two-criteria method for ensuring resource saving will be a sequence of distributions of still unsolved mission tasks over time [t0, ti-1] by topology Gi taking into account the fact that some of the tasks that are in the process of being solved on the nodes inherited from topology Gi-1, remain at their places and are not transferred: A = { A_i } ;

(8)

Matrix А describes the distribution of unsolved problems for which zl<1. At the same time, the number of nodes corresponds to new topology Gi. Nodes inherited from Gi-1, are renumbered and occupy indices starting from 1.

Since the mission may involve more than one topology, we will decompose the problem as follows: we will use the “greedy” policy and assume that a satisfying solution (minimization of resource consumption, estimated by two chosen criteria) can be obtained, if for each topology, we choose the best solution.

Consider the possible priority of the formulated objective functions. For each individual topology, it is required to minimize both the power consumption and the consumption of computing resources. In some special cases, the coincidence of optimization goals for two criteria can be achieved. Specifically, the task is distributed to the node in such a way that it will provide it with the minimum workload of the computational element and at the same time the minimum power consumption.

However, this situation is not always possible. For example, there is a node loaded less than other calculations, but at the same time its energy resource is almost exhausted. By assigning a task to it, we jeopardize the mission (or it is necessary to change topologies as the supply of electricity runs out), and by assigning a task to a more loaded node, we worsen the value of the residual computing resource criterion. The opposite situation can also occur: a node with a large residual power resource may have a low residual computing resource as a result of participating in previous device missions.

Therefore, it is advisable to rank the objective function (OF) in terms of importance, on the basis of which to select a further solution method.

For critical missions, the battery life of the device plays a leading role [19–21]. Accordingly, the OF that determines the residual computing resource can be reduced to an additional constraint. Uncompleted mission tasks will be redistributed depending on the remaining battery charge.

It should be noted that the above is also true for missions that do not have critical execution. In the event that the device loses battery power without completing the mission, it may be lost. Then the optimization of the computing resource will become meaningless.

On the other hand, by reducing the residual computational resource to a limitation, the solution may not be obtained at all due to the lack of available nodes whose characteristics would satisfy it.

Research Results. Multicriteria optimization problems, as a rule, are reduced to solving one or more single-criteria problems. In this case, it is more expedient to leave one OF, and present the second one as a constraint.

For the system under consideration, the fulfillment of the mission is critical for each node; therefore, we transform the OF for energy consumption into a restriction, the implementation of which will cut off unacceptable options for distributing tasks among the nodes. Further, within the framework of the resulting set of nodes, the distribution will occur with minimization of the consumption of the residual computing resource.

Let us describe the main stages of the two-criteria method for ensuring resource saving as the basic result of the study:

• on the existing Gi-topology, select nodes that have sufficient energy resources to complete the mission without changing the topology;
• distribute mission tasks among selected nodes in such a way as to minimize the consumption of computing resources for idle nodes, to which unsolved tasks will be attached.

It is possible to rank the nodes obtained at the first step of the method in descending order of the availability of an energy resource. But then, by distributing tasks primarily among nodes with the maximum amount of energy resource, there may be a deterioration in the values of the residual computing resource criterion.

Let us illustrate the dependence of the PFO values of devices on the selection of a node for solving the problem (in this experiment, we compare the states of the nodes under the transmission of incoming data and during their processing).

The topology is shown in Figure 1.

The experiment was carried out for 10-time intervals, each of which was 100 hours with the following parameter values: Wreceive (amount of data received by the task) — 500 units, Wsend (amount of data sent by the task) — 100 units, Wprocess (data processing complexity) — 150 units, Tdecl (time allotted for solving the task) — 50 units.

The following are graphs of PFO nodes depending on whether the node processes data or only transmits it (Fig. 2–5).

Further, Figure 6 shows comparison of differences in the values of the average residual computing resource.

Discussion and Conclusions. The article proposes a two-criteria method for ensuring resource saving in the edge and fog layers of the network. It differs from those previously presented in the subject area of organizing distributed computing in the dynamic layers of the network in the following. The proposed method takes into account both the state of the battery of the device (which is critical for the mission) and the residual resource of the computing device (what affects the duration of the appropriate use of the device outside the mission).

The developed method is based on the formulated problem of two-criteria optimization, which is then proposed to be reduced to a single-criteria one through converting the objective function of the energy resource balance into a constraint.

The nodes that are not suitable for the battery level are cut off in advance. Then there is a distribution of tasks according to the criterion of the residual computing resource.

The conducted experiment makes it possible to compare the results of task distribution over nodes in the presence of information interactions between tasks. It is clearly shown that the method of task distribution affects significantly the value of the residual resource of a computing device (up to 25 %). Thus, it is possible to improve the resource consumption indicators of devices involved in calculations in the edge and fog layers of the network.