CN111010434A

Movatterモバイル変換

Info

Publication number: CN111010434A
Application number: CN201911264618.8A
Authority: CN
Inventors: 刘通; 邓荣; 刘宇; 唐林; 江希
Original assignee: Chongqing Vocational Institute of Engineering
Current assignee: Chongqing Vocational Institute of Engineering
Priority date: 2019-12-11
Filing date: 2019-12-11
Publication date: 2020-04-14
Anticipated expiration: 2039-12-11
Also published as: CN111010434B

Abstract

Translated fromChinese

本发明公开了一种基于网络时延和资源管理的优化任务卸载方法，在融合区块链和雾计算系统中基于节点剩余资源和网络时延对优化卸载PoW难题进行了研究。在由基站雾节点、固定位置雾节点及移动雾节点共同构成的网络场景中分析了将PoW难题卸载至各种类型的雾节点所需要的总时长。此后基于网络节点剩余的计算资源、存储资源、功率资源和节点间的社交关系对MUB的支出进行了分析。并基于节点剩余资源和网络时延提出了优化任务卸载方案，并以最大化MUB收益为目标构建了数学优化模型，使用SA算法和博弈理论对优化模型进行了求解。最后，通过模拟仿真分析证明上述方案的优越性。未来的工作中将考虑在系统内引入人工智能的智能任务卸载方式。

The invention discloses an optimized task offloading method based on network delay and resource management, and studies the problem of optimizing offloading PoW based on node remaining resources and network delay in a fusion blockchain and fog computing system. The total time required to offload the PoW problem to various types of fog nodes is analyzed in a network scenario composed of base station fog nodes, fixed-position fog nodes and mobile fog nodes. Afterwards, the expenditure of MUB is analyzed based on the remaining computing resources, storage resources, power resources and social relations among nodes of the network. Based on the remaining resources of nodes and network delay, an optimization task offloading scheme is proposed, and a mathematical optimization model is constructed with the goal of maximizing the MUB revenue, and the optimization model is solved using SA algorithm and game theory. Finally, the superiority of the above scheme is proved by simulation analysis. Future work will consider the introduction of artificial intelligence into the system for intelligent task offloading.

Description

Optimized task unloading method based on network delay and resource management

Technical Field

The invention belongs to the technical field of communication, relates to an optimized task unloading method based on network delay and resource management, and particularly relates to an optimized task unloading method based on network delay and resource management in a fusion block chain and fog computing system.

Background

The basic idea of the fog computing technology is to sink the network function provided by the cloud server to the edge of the network, and as the position of the fog server is deployed closer to a network user, compared with cloud computing, the fog computing can effectively reduce data transmission delay. In addition, the distributed processing mode adopted by the fog computing can effectively relieve the problem of network congestion caused by the fact that a large amount of data burst into the cloud. The fog calculation has received a lot of attention because its advantages can meet the future network application requirements.

Moreover, the continued increase in bitcoin value has prompted the industry and academia to conduct extensive research into blockchain technology. The blockchain is a distributed accounting technology based on the Internet, and is characterized by dispersion and transparency. The distributed account book can effectively solve the problems that transaction cost is high, data is easy to lose and the like in a centralized authentication mode, and can also effectively improve the trust degree among nodes in a virtual currency system. The advantages enable each device with the blockchain application program to participate in data recording and storage, and greatly improve flexibility and safety of accounting modes in electronic transactions.

In block chain technology, the equipment that excavates digital currency is referred to visually as a "miner" because it excavates digital currency in a manner that is relatively similar to the manner in which traditional miners excavate mineral deposits. Miners will gain considerable digital monetary revenue by solving the computationally intensive pow (pro of work) puzzle, i.e., the solution of the hash value. However, solving the PoW problem requires a large amount of computing resources, and thus it is common in real-world applications to use large-scale hardware facilities, such as CPUs and GPUs, for hash value solving. Due to the size constraint of the device, it is obviously impractical to deploy a large-scale computing unit on the mobile terminal, so that the application of the block chain technology on the mobile intelligent terminal faces great difficulty and challenge.

In order to solve the above problem, it is considered to introduce a fog calculation technique into the blockchain system, solve the PoW problem with the strong computational power provided by the fog calculation, and provide low-latency network performance guarantee to the mobile user mub (mobile user with blockchain) in which the blockchain application is installed. The authors in the prior art analyzed the feasibility of fusing blockchain and fog computing systems from a security, versatility perspective. By incorporating a block chain into a fog computing network, the system can provide reliable access and control, storage, and computation of the network over a large number of distributed edge nodes. In addition, a few scholars have conducted system revenue studies based on resource management in converged blockchain and fog computing network environments. Some prior arts propose a Stackelberg game model, which provides an effective management method for resource allocation in fog computing. A blockchain system model supporting fog calculation is introduced thereafter to help fog service providers gain more profits. There are also prior art authors that have employed the two-stage Stackelberg game to maximize the revenue for both the provider and the individual MUBs of the fog calculation. During the gaming process, the operator sets the price for the service in the first phase and the MUB purchases the service in the second phase by observing it. The author deduces the Nash equilibrium point of the game by adopting a reverse induction method, and finally realizes the maximization of the system income.

These excellent prior research results are dedicated to the research on the fusion of fog computing and block chain technology, and there are few documents analyzing the resource management and benefit problems of the system. However, these documents neglect to study the income of the MUB. Only the profits of the network operator have been analyzed in the prior art. Meanwhile, different network resource management schemes have a significant impact on network performance, which further determines the benefits of the MUB. Based on the above analysis, there is still a need for further research on the following problems in the fused blockchain and fog computing system:

1) the main purpose of running the blockchain application is to obtain the transaction record right and then obtain the digital currency reward by solving the PoW problem, and the MUB is the main body for executing the blockchain application, so the benefit analysis of the MUB should be intensively studied in the system fusing the blockchain and fog calculation.

2) A MUB is essentially a mobile communication device whose computing power, storage power, etc. device performance is determined by its hardware configuration, such as CPU frequency, storage space, battery capacity, etc. of the device, which determines the computing resources, storage resources, power resources, etc. that the device has. Different resource allocation and management schemes will certainly affect the yield of the MUB, so how the resource allocation affects the expected yield of the MUB is a problem worthy of further study.

3) When the MUB unloads the PoW problem to the fog node, the network time delays corresponding to different unloading schemes are different, so that the influence of the network time delay on the MUB benefit is researched. The network has a large number of MUBs to solve the PoW problem at the same time, and only the MUB which solves the PoW problem at the earliest can obtain the benefit, so the time consumed in communication and calculation has a decisive influence on the benefit of the MUB. Therefore, it is necessary to analyze how network delays of the converged blockchain and fog computing system affect the MUB benefit problem.

4) There may be multiple offloading methods for offloading PoW problems from the MUB to the fog node, and different offloading methods for tasks may have a significant impact on the benefits of the MUB. Therefore, how to perform the optimized offloading of tasks to enable the MUB to obtain the maximum monetary benefit is also a matter of research.

In a fusion system of block chain and fog calculation, whether the PoW problem can be solved successfully directly determines whether the MUB can obtain the final benefit, and the PoW problem is not practical to be solved directly on the mobile terminal due to the limitation of the performance of the equipment. The invention combines network resource management and focuses on researching the optimization task unloading strategy in the fusion block chain and fog computing system.

Disclosure of Invention

The invention aims to overcome the defects in the prior art and provides an optimized task unloading method based on network time delay and resource management. The problem of optimizing and unloading PoW is researched in a fusion block chain and fog computing system based on node residual resources and network delay. The total time required to offload PoW problems to various types of fog nodes is analyzed in a network scenario consisting of a base station fog node, a fixed location fog node, and a mobile fog node. The expenditure of the MUBs is thereafter analyzed based on the remaining computing resources, storage resources, power resources of the network nodes, and social relationships between the nodes. And an optimized task unloading scheme is provided based on node residual resources and network time delay, a mathematical optimization model is constructed with the maximized MUB benefit as a target, and the optimization model is solved by using an SA algorithm and a game theory. Finally, the superiority of the scheme is proved by analog simulation analysis. In future work, an intelligent task unloading mode of introducing artificial intelligence into the system is considered.

The specific technical scheme is as follows:

a task unloading optimization method based on network time delay and resource management is characterized in that a considered task unloading mode is that an original task is divided into a plurality of subtasks by an MUB according to a certain proportion and the subtasks are respectively unloaded to different types of fog nodes for processing. Let the MUB divide the task into three parts, offloaded to BN, FN and MN respectively. Let the total task amount of tasks be Q_nThe proportion of the workload unloaded to BN, FN and MN to the total workload is α and gamma, respectively, satisfying 0. ltoreq. α. ltoreq.1, 0. ltoreq. β. ltoreq.1, 0. ltoreq. gamma. ltoreq.1 and α + β + gamma. 1.

The method comprises the following steps:

step 1 revenue analysis

According to the Nakamoto definition, there is a linear relationship between the probability that the MUB can acquire virtual currency and the data volume of the PoW puzzle. The greater the number of tasks calculated by the MUB, the greater its probability of getting rewards and the higher the expected revenue. Let the task amount of a task be Q_nThe probability that the MUB can obtain the digital currency reward after the task is executed is p_incomeThen the gains gained by the MUB can be expressed as:

U_exp＝p_incomeQ_n(1)

step 2 time delay analysis

If a fog servers are deployed at the base station, the computing power is f_bnWill amount to α Q_nPoW ofWhen the problem is migrated to the base station foggy node, the required transmission time can be expressed as:

is the channel rate between the MUB to the base station. W_iRepresenting the bandwidth of channel i, P_mIs the transmit power of the MUB and,

for channel gain, ω_iAnd I_iRepresenting the noise and interference, respectively, of channel i.

The calculation time required for migrating the task to the BN to solve is as follows:

it is further obtained that the total time taken to offload a task to a BN is:

in addition, b calculation capacities are all f within the communication range of the MUB_fnThe fixed position fog server of (2), the task amount is β Q_nThe transmission time required for the migration of the PoW problem to the FN can be expressed as:

representing the achievable channel rate between the MUB and the jth FN. W_jIs the bandwidth, P, of channel j_mIs the transmit power of the MUB and,

for channel gain, ω_jAnd I_jRepresenting the noise and interference, respectively, of channel j.

The computation required for the task to perform the computation at the FN is given by:

the total time required to unload the task to the FN is:

c pieces of c pieces_mnThe fixed position fog server of (2), then the task amount is gamma Q_nThe transit time taken for the PoW problem to migrate to the MN can be expressed as:

representing the channel rate between the MUB to the k-th MN. W_kFor the channel bandwidth, P_mIs the transmit power of the MUB and,

for channel gain, ω_kAnd I_kRepresenting the noise and interference, respectively, of channel k.

The time required for the MN to process the data is:

the total time required to offload the task to the MN can be expressed as:

according to the above analysis, the total delay for successfully solving the PoW problem can be expressed as:

T_s＝arg max(T^bn,T^fn,T^mn)+T_back(11)

in the formula, T_backRepresenting the time consumed by a network node to successfully resolve the PoW issue by transmitting the transaction record information back to the MUB via the backhaul link. Because the returned information after the PoW problem is successfully solved is a transaction record in the block chain system, compared with the task amount of the PoW problem, the data amount of the transaction record is very small, and the transaction record is set to 0 in many researches, the invention adopts the same analysis method, and finally obtains the expression of task execution delay as follows:

T_s＝arg max(T^bn,T^fn,T^mn)(12)

step 3 stage of expenditure analysis

The residual resources and the total resources of the nodes are regarded as factors influencing the quotation of the fog nodes, and the quotation of the fog nodes of the three types is compared on the same standard, so that the quotation fairness among the nodes is improved, and the MUB can conveniently select the most economic task unloading mode. Unit quotes for three types of fog nodes are expressed as:

in the formula (I), the compound is shown in the specification,

and

respectively representing the total number of base station nodesStorage resources, total computational resources, and total power resources. s^bn(t)、c^bn(t) and e^bnAnd (t) respectively represents the residual storage resources, computing resources and power resources at the moment t.

And

the weight values represent the influence of three different types of resources on the price respectively. The emphasis of different types of fog nodes on each resource is different, for example, MN pays more attention to power resource, so

Will be higher than

And

at the same time higher than

And

the symbol definitions in equations (14) and (15) are consistent with the above analysis and will not be described in detail.

Step 4 two-stage expenditure analysis

After the MUB successfully solves the POW problem, the event is broadcasted to other MUBs (called RMUBs in the invention, Recording Mobile User with Block), the RMUBs help the MUB to record the event and route the information to other RMUBs, and when more than 51% of the RMUBs record the message, the MUB can successfully acquire the digital currency reward. However, since RMUB itself is also attempting to solve the PoW problem, there is a competitive relationship between RMUB and the MUB, and RMUB is reluctant to assist the MUB in recording and routing the transaction information without any compensation. That is, the MUB that successfully acquired the transaction record would need to pay a fee to the RMUB for the purchase of the RMUB service in order to reach the RMUB as soon as possible, and the fee the MUB paid to the RMUB is its expenditure in the second phase.

Since both the MUB and the RMUB wish to maximize their income, the MUB as a service purchaser sets a lower price at an initial stage, whereas the RMUB as a service provides a higher price, so that there is a difference between their prices, and both parties need to adjust their prices continuously by asking for a counter-offer to finally reach a transaction. Let the total time of MUB consumption in the second stage be T_s2。

Representing the time taken by MUB and the ith RMUB to reach a transaction by bargaining, the number of MUB in the network is M, the composition set M is {1,2,3 … M }, the number of RMUB to finally reach a transaction with the MUB is N, the composition set N is {1,2,3 … N },

this is true. The time spent by the MUB in the second stage can be expressed as:

further, m and n satisfy the following relationship:

through T_s2After a time when the transaction is complete, let the MUB pay each RMUB for the duration of the transaction be C_i(t) i ═ 1,2.. n, then the total cost of the MUB in the second stage can be expressed as

Further, the method also comprises thestep 5 of mathematical modeling

According to the definition of Nakamoto, the final benefit of the MUB is equal to the expected benefit minus the cost in the first and second phases, so the final benefit of the MUB can be expressed as:

U_u＝Q_np_income-C_s1-C_s2(19)

accordingly, an optimization model that maximizes the benefits of the MUB can be expressed as:

since the benefits of the MUB are closely related to the execution time of the task, the constraint C1 limits the total latency to T_τWithin a range to ensure that the MUB addresses the speed of the PoW. C2 and C3 are the means for offloading the total task divided into sub-tasks to BN, FN and MN respectively to reduce the total time for executing the task. Equation C4 ensures that during the second phase, the MUB can agree with 51% of the RMUBs in the network to obtain virtual currency rewards. C5 requires the delay of the second stage alone To ensure that the total time consumed in the second stage cannot exceed the time-To-live ttl (time To live) of the message.

Considering that the process of mining the MUB is mainly divided into two stages, and the total expenditure in the optimization target also consists of the expenditures of the two stages respectively, in the process of relaxing the model, the original optimization model is decomposed into two sub-optimization models simultaneously, and the expenditures of the MUB in the two stages are optimized respectively. Secondly, under the condition of fixed task quantity, maximizing the benefit of the MUB is equivalent to minimizing the overhead of the MUB, so the optimization target of the original optimization model is further converted after the original problem is relaxed.

Further,step 5 finally obtains two sub-optimization models, which are respectively expressed as:

sub-optimization model 1:

sub-optimization model 2:

since thesub-optimization model 1 has a nonlinear relationship between the optimization objective and the constraint condition, it is solved by using a simulated annealing algorithm suitable for solving such problems. Forsub-optimization model 2, however, since there is a bargaining between the MUB and the RMUB, it is solved using the Rubinstein-Stahl game suitable for solving the bargaining problem.

Compared with the prior art, the invention has the beneficial effects that:

(1) the influence of the residual computing resources, storage resources and power resources of the nodes on the benefit of the MUB virtual currency is analyzed, and the fog nodes with sufficient resources provide lower service quotations to attract tasks of the MUB, so that the utilization rate of idle resources of the network is improved.

(2) The influence of the transmission delay and the calculation delay on the MUB benefit when the PoW problem is transferred to various types of fog nodes is analyzed, and a closed expression of the total delay of the PoW problem calculated by the fog nodes is obtained.

(3) Social relationship analysis among the nodes is introduced to improve the digital currency income of the MUB, and a quotation mechanism based on the social relationship analysis can effectively improve the trust degree among the nodes.

(4) Based on the analysis of node residual resources and network time delay, an optimization task unloading model is established with the aim of maximizing the virtual currency income of the MUB.

(5) The task unloading proportion is used as an optimization solution, the optimization model is solved by using a simulated annealing algorithm and a Rubinstein-stahl game theory, the performance of the optimization model is compared with a greedy algorithm and a random algorithm, and the superiority of the scheme provided by the invention is proved by a simulation result.

Drawings

FIG. 1 System model;

FIG. 2 is a diagram of a simulation environment;

FIG. 3 is a relationship between the number of nodes and the delay;

FIG. 4 is a graph comparing task volume to network latency;

FIG. 5 relationship of different resource types and pricing;

FIG. 6 is a comparison of the relationship between idle resource utilization and task volume;

FIG. 7 is a comparison of the overheads of migrating tasks to different execution agents;

FIG. 8 shows a comparison of profits for migrating tasks to different executing agents;

FIG. 9 MUB benefit comparison using different algorithms;

FIG. 10 data size versus revenue;

FIG. 11 message remaining time versus offer;

FIG. 12 relationship (MUB) between message remaining time and discount factor;

FIG. 13 is a Relationship (RMUB) between message remaining time and a discount factor;

FIG. 14 relationship between number of nodes and price.

Detailed Description

The technical solution of the present invention will be described in further detail with reference to specific embodiments.

1 System model

A distributed fog service structure of a fusion block chain and fog computing system is shown in fig. 1, and a fog server can be deployed on not only a base station but also access terminals such as intelligent vehicles. According to the service capability provided by the fog server and the mobility of the fog server, the fog nodes are divided into three categories: base station mist server BN (Base station-based fog Node), Fixed-position mist server FN (Fixed-location fog Node) and mobile mist server mn (moving fog Node). The base station fog server is used for deploying a plurality of fog servers with fog computing capability in a base station and providing services such as computing, storing and the like for network access users. Meanwhile, the fog server can be deployed on some devices with fixed geographic positions, such as rsu (road unit), notebook computer and the like, to form a fixed-position fog node. In addition, the fog server can also be deployed on mobile equipment such as intelligent vehicles, and the mobile equipment capable of providing the fog service is called a mobile fog node in the invention. The three types of fog servers form a ubiquitous fog structure, and provide fog services for users at the same time.

The MUB carries out the solution of the hash value by executing the block chain application program, massive calculation is needed in the process of solving the hash value, a large amount of calculation resources are consumed, and the calculation of the PoW problem is impractical to be directly carried out locally due to the limitation of the mobile equipment on hardware configuration. In the ubiquitous fog structure, the MUB can transfer the PoW problem to three types of fog nodes, the solution of the PoW problem is carried out by means of the strong computing power of the fog server, the data processing time is further saved, and the MUB is ensured to obtain benefits at the fastest speed.

The task unloading mode considered by the invention is that the MUB divides the original task into a plurality of subtasks according to a certain proportion, and the subtasks are respectively unloaded to different types of fog nodes for processing. Let the MUB divide the task into three parts, offloaded to BN, FN and MN respectively. Let the total task amount of tasks be Q_nThe proportion of the workload unloaded to BN, FN and MN to the total workload is α and gamma, respectively, satisfying 0. ltoreq. α. ltoreq.1, 0. ltoreq. β. ltoreq.1, 0. ltoreq. gamma. ltoreq.1 and α + β + gamma. 1.

2 optimized task unloading scheme based on resource management

Offloading of tasks to the fog node by the MUB takes up resources of the fog node, so the fog node charges it for services to be provided to the MUB, and the fog node offers two options to the MUB for pricing. The first is a total price quote mechanism, i.e. for a fixed data volume task, the MUB only has to pay the rated fee to the fog node, which ensures that the task can be executed. Another way of quoting is a unit quoting mechanism, i.e. the fog node charges a unit amount of data per unit time of execution. The MUB tends to accept the second offer scheme from the standpoint that it wishes to resolve PoW as quickly as possible. Because the node in fog is in the process of executing task for the MUB, it will face other new task with higher priority, such as dialing telephone number by mobile phone user, at this moment, the node in fog has to stop the service facing to MUB, and then service the local service with higher priority. If the MUB admits the first offer scenario, the extended task execution time caused by queuing will reduce the expected revenue of the MUB when this occurs. If the MUB adopts the second quotation scheme, when a service with higher priority is executed on the fog node, the MUB can select to migrate the rest tasks to other fog nodes, so that the task solving time is shortened. Based on the analysis, the method is based on a unit quotation mechanism, and analyzes the time required by the three types of fog nodes to execute tasks and the unit quotation to obtain the total expense of the MUB.

The earning of the MUB is divided into two phases. In the first stage, the MUB transfers the PoW problem to the fog node for solving, once the fog node successfully solves the problem, namely the transaction information is found in the network, the transaction information is immediately fed back to the MUB, and the MUB records the transaction record on a local accounting book. In the second phase, the MUB broadcasts the events that it has recorded the transaction to other MUBs in the network, and when 51% of the MUBs in the network confirm the transaction, the original MUB can receive the reward of digital money.

2.1 revenue analysis

The purpose of the MUB to solve the PoW problem is to obtain the record right of the transaction information, and the final purpose is to obtain the virtual currency reward, such as bitcoin and the like. According to the Nakamoto definition, there is a linear relationship between the probability that the MUB can acquire virtual currency and the data volume of the PoW puzzle. The greater the number of tasks calculated by the MUB, the greater its probability of getting rewards and the higher the expected revenue. Let the task amount of a task be Q_nThe probability that the MUB can obtain the digital currency reward after the task is executed is p_incomeThen the gains gained by the MUB can be expressed as:

U_exp＝p_incomeQ_n(1)

2.2 time delay analysis

If a fog servers are deployed at the base station, the computing power is f_bnWill amount to α Q_nThe PoW problem is migrated to the base station node, and the required transmission time can be expressed as:

it is further obtained that the total time taken to offload a task to a BN is:

the total time required to unload the task to the FN is:

The time required for the MN to process the data is:

the total time required to offload the task to the MN can be expressed as:

T_s＝arg max(T^bn,T^fn,T^mn)+T_back(11)

in the formula, T_backAfter solving the PoW problem successfully on behalf of a certain network node, the transaction is recorded through the return linkThe time it takes to record information back to the MUB. Because the returned information after the PoW problem is successfully solved is a transaction record in the block chain system, compared with the task amount of the PoW problem, the data amount of the transaction record is very small, and the transaction record is set to 0 in many researches, the invention adopts the same analysis method, and finally obtains the expression of task execution delay as follows:

T_s＝arg max(T^bn,T^fn,T^mn) (12)

2.3 one-stage expenditure analysis

The introduction of the fog nodes greatly shortens the calculation time of various applications, and the terminal equipment with limited calculation capacity can transfer different types of service requests to the fog server, for example, an intelligent vehicle in an internet of vehicles can transfer a picture analysis task to the fog nodes, and a mobile phone user can send a high-definition video cache request to the fog nodes. In order to avoid the situation that the mobile terminal unloads excessive tasks to the fog node, under the precondition that the local service execution is not influenced, the fog node firstly considers whether the residual computing resources, storage resources and power resources of the current local server can meet the resource requirements of the unloading tasks. When the remaining resources are sufficient, the fog node may set a lower quote to attract the MUB to migrate more tasks to the local server, thereby increasing the utilization of the local idle resources. In addition, if the current remaining resources of the fog node are deficient, in order to ensure that the normal operation of the local task is not affected, the fog node may set the quotation to be higher to guide the MUB to offload the task to other fog nodes. Namely, the residual resources of the fog nodes and the quotation are in inverse proportion.

On the other hand, the BN server is provided by the operator, and in general, such a fog server is much more powerful than the FN and MN, even in the case where the remaining resources of the BN are larger than the maximum amount of resources of the FN and MN. If only the remaining resources are used as the pricing criteria of the fog server, it is obvious that unfair pricing is caused, and further the task unloading strategy of the MUB is affected.

Based on the consideration, the invention takes the residual resources and the total resources of the nodes as factors influencing the quotation of the fog nodes, and aims to compare the quotation of the three types of fog nodes on the same standard, improve the fairness of the quotation among the nodes and facilitate the MUB to select the most economic task unloading mode. Unit quotes for three types of fog nodes are expressed as:

in the formula (I), the compound is shown in the specification,

and

respectively representing the total storage resource, the total calculation resource and the total power resource of the base station fog node. s^bn(t)、c^bn(t) and e^bnAnd (t) respectively represents the residual storage resources, computing resources and power resources at the moment t.

And

Will be higher than

And

at the same time higher than

And

2.4 two-stage expenditure analysis

T_2iRepresenting the time taken by MUB and the ith RMUB to reach a transaction by bargaining, the number of MUB in the network is M, the composition set M is {1,2,3 … M }, the number of RMUB to finally reach a transaction with the MUB is N, the composition set N is {1,2,3 … N },

this is true. The time that the MUB spends in the second stageCan be expressed as:

further, m and n satisfy the following relationship:

3 mathematical modeling

U_u＝Q_np_income-C_s1-C_s2(19)

The above optimization model is computationally intensive and the variables in the constraints are tightly coupled to each other. Solving this optimization model first requires relaxing it. Considering that the process of mining the MUB is mainly divided into two stages, and the total expenditure in the optimization target also consists of the expenditures of the two stages respectively, in the process of relaxing the model, the original optimization model is decomposed into two sub-optimization models simultaneously, and the expenditures of the MUB in the two stages are optimized respectively. Secondly, under the condition of fixed task quantity, maximizing the benefit of the MUB is equivalent to minimizing the overhead of the MUB, so the optimization target of the original optimization model is further converted after the original problem is relaxed. Finally, two sub-optimization models are obtained and are respectively expressed as:

sub-optimization model 1:

sub-optimization model 2:

4 algorithm solution

4.1 simulated annealing Algorithm solution

The simulated annealing algorithm is a random optimization algorithm based on a Monte-Carlo iterative solution strategy, and the starting point of the simulated annealing algorithm is based on the similarity between the annealing process of solid matters and a general combinatorial optimization problem. The simulated annealing algorithm starts from a certain high initial temperature, and a global optimal solution of the objective function is searched in a solution space by combining with the probability jump characteristic along with the continuous decrease of the temperature parameter, namely, the global optimal solution can jump out probabilistically in a local optimal solution and finally tends to be global optimal.

For the optimization model, under the precondition that 0 is not less than α and not more than 1, 0 is not less than β and not more than 1, 0 is not less than gamma and not more than 1 and α + β + gamma is 1, different values of α and gamma form a solution space, when a simulated annealing algorithm is used for seeking an optimal solution, the highest temperature T is firstly set_maxAnd the temperature reduction speed v meets the condition that T (k +1) ═ v T (k), T (k) represents the temperature at the moment k, and when the temperature is reduced to the minimum temperature T_minWhen so, the algorithm ends. In each cooling process, L solutions appear, and in order to obtain the optimal solution, the solution of the system in the current state i is assumed to be

The solution at the next state j is

According to the metropolis criterion, the following holds:

wherein p is_solTo accept the probability that the current solution is the optimal solution, it can be expressed as:

in the formula

Is a Boltzmann constant, satisfies

The simulated annealing algorithm flow for solving the optimization model is described as follows:

set in SA algorithm from the highest temperature T_maxReduced to a minimum temperature T_maxNeeds to be cooled for N times, and L cooling units are generated at each timeThe solution space, so the complexity of this algorithm is O (N × L). In addition, if the convergence rate is set to a smaller value, for example, v is 0.9, the convergence rate of the algorithm can be increased, and thus, the algorithm has higher flexibility.

4.2 Rubnstein-Stahl game solving based on node residual resources

Forsub-optimization problem 2, since the MUB and the RMUB need to be bargained for a plurality of times, the solution ofsub-optimization problem 2 is performed by means of Rubinstein-Stahl game theory which is most suitable for solving the bargaining problem. The Rubinstein-Stahl bargaining model is a dynamic game model established under complete information. Without the intervention of a third party, the buyer and seller of the goods eventually form a consensus by bargaining off.

In the Rubinstein-Stahl game theory, buyers and sellers of items set an initial price for the item before the bargaining counter-offer begins. In this study, buyers and sellers in game theory represent MUBs and RMUBs, respectively, and the goods are recorded messages provided by RMUBs to MUBs and provide routing services.

When the remaining resources of the MUB are scarce, it is imperative that they agree with the RMUB as soon as possible to obtain the reward before the resources are exhausted, so the offer is set high at the time of the initial offer. Otherwise, if the remaining resources of the MUB are sufficient, the price quote is set lower. On the other hand, for RMUB, when its remaining resources are low, RMUB will set a high initial price to guarantee the resource demand of the local application. If the remaining resources of the RMUB are sufficient, the RMUB may provide a lower initial price in order to fully utilize these idle resources. From the above analysis, the price of both parties is inversely related to the amount of the respective remaining resources.

In addition, the price settings for both parties may change over time, subject to the remaining time of the message. Specifically, at the beginning of the bargaining, the MUB will set a lower price offer to maximize its own revenue due to the time being sufficient. As messages become less and less available, the MUB will want to reach an agreement as soon as possible, so the price it offers will gradually increase. For RMUB, it will set a higher price quote in the initial phase to gain more benefit. However, as the MUB increases its price, the RMUB also needs to make a concession based on the original price to complete the transaction, so the price of RMUB decreases gradually over time. But as the remaining duration of the message approaches, the magnitude of the price reduction becomes lower and lower, because in the transaction, the stronger the urgency is to be the MUB rather than the RMUB.

Based on the above analysis, the quotes of the MUB and RMUB for the resource are defined as:

in the above formula, R_mub(t) represents the offer of the MUB for the resource. s_mub(t)，c_mub(t) and e_mub(t) represents the remaining storage, computation and power resources of the MUB at time t, respectively. Sigma S_mub，∑C_mubSum E_mubRespectively representing the total storage resources, total computational resources and total power resources of the MUB.

And

the weights of the three resources at the time of pricing are respectively. The definitions of the symbols in equation (27) are the same as those in equation (26), and are not described again.

Through the foregoing analysis, the offer of a MUB is affected by both time and resources, so the initial offer of a MUB is defined as:

T_m(T) represents the remaining time of the message, satisfying T_m(t)≤TTL。

And

the weights of the resources and the time are respectively.

Further initial quotes for RMUB are:

and

the weight values of the resources and the time in the RMUB quoted price are respectively.

After the game starts, the MUB and RMUB points present their initial offers in succession. If it is

The transaction fails; if it is

Representing the space for further bargaining for both parties, the transaction is expected to be achieved.

The difference between the two quotes is expressed as:

this difference is called "cake" in the Rubinstein-Stahl game. During the subsequent bargaining process, the bids of both the MUB and the RMUB are made around the cake, and both hopefully share a higher proportion of the cake, defining z_mAnd

representing the ratio of MUB and ith RMUB respectively occupied in sharing the cake, the following holds:

in addition, the gains obtained by the game by the MUB and the ith RMUB are respectively set as

And

then there are:

the process of the game is accompanied by consumption of time and resources, and the MUB and RMUB have different levels of tolerance to such consumption, which is commonly referred to as a discount factor in the Rubinstein-Stahl game. Let the discount factors of the two be delta_mubAnd

then there are:

at the beginning of the bargaining, the MUB wishes to purchase the service of RMUB at the lowest price, so its initial price is low. However, if the MUB does not yield the cake, there will be no RMUB to assist it in recording information and forwarding information of how the PoW problem has been solved, which eventually results in no profit being obtained. As the remaining time of the message continues to decrease, the desire of the MUB to share the cake gets lower and lower. That is, as time goes by, its discount factor becomes smaller and smaller, the discount factor being a decreasing function with respect to time, satisfying:

and is

And

many functions can satisfy the above mathematical expressions, such as Sigmoid function and ReLU function, and the present invention uses Tanh function for describing the discount function of the MUB, which is expressed as:

if the EMUB is not serving the MUB without any loss, it is less desirable to share the cake in the early stages of the game. However, as the remaining message time is shorter and shorter, the MUB is more and more urgent to reach the transaction as soon as possible, and the eager degree of cake by the EMUB which is dominant in the transaction is higher and higher, so that the discount factor is an increasing function of time and satisfies the following conditions:

and is

And

the function used to describe the above mathematical expression is represented as:

after the bargaining of multiple rounds, the MUB and the RMUB finally agree that a game equilibrium point appears, which is expressed as:

5 simulation results

Since the research is a document for researching the optimization task unloading mode by integrating the residual resources and the task execution time of the nodes in the block chain and fog computing system earlier, the related analysis methods cannot be inquired and compared with the research. In the simulation, only random algorithms and greedy algorithms often used to solve such problems are compared.

The parameters in the simulation are set as follows. The number a of the deployed fog servers in the base station fog node is 10. The number of FN and MN within the range of the MUB communication is also set to 10. For ease of analysis, all bandwidths are set to 10MHz, and all noise and interference are set to 1. The fading models of the channels are:

in the formula of_i～CN(0,1)i＝1,2,3，

Is a mean value of m_μVariance of

A circularly symmetric complex gaussian distribution. σ is the path loss factor, which was set to 3 in the simulation. d is the distance between the communication nodes, which is determined by the simulation environment diagram in fig. 2.

Fig. 2 shows the geographical location distribution of the MUBs, BN, FN and MN in the simulation. The base station is centered and has a coverage radius of 300 meters. The location of the MUBs randomly occurs within the coverage area of the base station, which is also 300 meters in communication range. The positions of 10 FNs are fixedly set within the communication range of the MUB, and the positions of 10 MNs are randomly generated by the system.

The total storage resources, total computational resources and total power resources of BN, FN and MN are shown in table 1. In order to reflect fairness among various resources, the weighted values are set to be approximately equal.

TABLE 1 Total and remaining resource amounts of various nodes and setting of their weights

The [ x, y ] in Table 1 represents a uniform distribution obeying x to y. In addition, we set the maximum temperature and the minimum temperature in the simulated annealing algorithm to 200 ° and 1 °, respectively, the annealing rate is 0.99, and the cycle number L is 10000.

The total resources, remaining resources and corresponding weight values of the MUBs and RMUB in the second stage of the simulation are set as shown in table 2. Also the number of EMUBs is set to 20,

the message lifetime TTL is 150ms, and the parameter λ in the discount function is 0.5.

TABLE 2 setting of total and remaining resource amounts of MUB and EMB and their weights

Fig. 3 analyzes the relationship between the number of fog nodes and the network delay. As is apparent from fig. 3, as the number of network nodes (including BN, FN and MN) increases, the network delay gradually decreases. Fig. 3 illustrates that offloading of pows by the MUBs onto multiple fog nodes may save task execution time for computation. If 10 mist servers are deployed in the network, the total network latency reaches 17ms, whereas if the number of mist servers in the network increases to 30, the network latency can decrease to 10 ms.

In addition, for the case of completely unloading the tasks to the BN, the FN and the MN and unloading the tasks according to the optimized proportion solved by the simulated annealing algorithm, network delay data corresponding to four modes are recorded in simulation, and an experimental result is shown in fig. 4. from fig. 4, it is obvious that the network delay for completely unloading the tasks to the BN is lower than the network delay for completely unloading the tasks to the FN and the MN, mainly because the computing capacity of the BN server is stronger than that of the FN and MN., but the network delay of the optimized unloading scheme provided by the invention is obviously lower than that for completely unloading the tasks to a certain type of fog nodes^*,β^*,γ^*The time delay consumed for offloading is 33ms, while for the same amount of tasks, offloading all tasks to BN, FN and MN, the corresponding network delays are 62ms, 68ms, 85ms respectively.

In the following simulation, MN is taken as an example, the size of the task is set to be 2GB, and under the condition that the weight value is fixed, the influence of different types of resources on the quoted price is analyzed. As can be seen first in fig. 5, an increase in the amount of remaining resources results in lower and lower prices for the nodes. This is mainly because when there are more resources left, the MN, in order to fully utilize the idle resources, setting the price quote lower, can direct the MUB to migrate more tasks to the MN. Furthermore, it can also be observed from fig. 5 that the power resources have the greatest impact on the MN's price quotes, mainly because MNs tend to be power-limited devices. For example, when the remaining power resource is only 10%, the price of the MN for the power resource is 9.3, while under the same remaining resource proportion condition, the price of the MN for the storage resource and the computing resource is only 2.4.

Fig. 6 analyzes the resource utilization rate of the fog node by taking the storage resource as an example, if it is assumed that the proportion of the total resource occupied by the local service of the current fog node is 20%. As can be seen from fig. 6, if the PoW task is delivered to the MUB for processing, since the task is not offloaded to the fog node, the resource utilization rate of the fog node remains unchanged. However, when the task is unloaded to the fog node for processing, the idle resource utilization rate of the fog system is continuously increased along with the continuous increase of the task amount. If the total task volume is 6GB, the resource utilization rate for offloading all tasks to MN is 0.25, and if the task volume is increased to 12GB, the value is increased to 0.29. It can also be seen from fig. 6 that the resource utilization is highest for offloading the tasks to the MN in their entirety, mainly because the hardware configuration of the MN is weaker than that of the FN and BN, and the amount of tasks of the same size will occupy a higher proportion on lower performing servers. The resource utilization rate when the SA algorithm is used is lower than the resource utilization rate when the tasks are all offloaded to the MN, the FN and the BN, and the main reason is that when the resource utilization rate is measured, the object oriented by the SA algorithm is a fog system formed by the MN, the FN and the BN together, that is, the SA algorithm aims at the resource utilization rate of the whole fog system, and the tasks are all offloaded to the BN, the FN and the MN corresponding to a single type of fog node.

In the analysis of fig. 4, it is seen that the optimization task offloading strategy provided by the present invention can effectively shorten the task execution time. Since the execution duration of the task is proportional to the overhead of the MUB, the same conclusion holds for the overhead of the MUB. As is apparent from fig. 7, the overhead of offloading tasks to scale according to the SA algorithm is minimal. For example, when the task amount is 5GB, the total overhead of offloading the tasks to the MN, FN, BN and using the SA algorithm is 107, 80, 68, 48, respectively.

The benefits corresponding to different migration patterns are compared in fig. 8. The scheme provided by the invention can effectively improve the benefit of the MUB. If the task amount is 5GB, the total profit of unloading the tasks to MN, FN, BN and using SA algorithm is 105, 127, 140, 161 respectively.

FIG. 9 compares the number of tasks with the benefits of MUB overhead when using the simulated annealing algorithm, the greedy algorithm, and the random unload algorithm, respectively. As can be seen from fig. 9, the cost of the MUB increases with the increase of the task amount, and the main reason is that the increase of the task amount occupies more resources of the fog node, the fog node charges more fees, and the cost of the MUB naturally rises. Meanwhile, due to the increase of the task amount, the transmission delay and the processing delay are increased together, so the expense of the MUB is increased. For example, when the task size is 4GB, the overhead of the MUB using the SA algorithm is 36, and when the task size increases to 7GB, the overhead increases to 73. Meanwhile, as can be seen from fig. 9, when the task amount is 5GB, the overhead of using SA is 50, which is lower than 62 when using GA, which is much lower than 104 of RA. The above data show that the performance of the SA algorithm is better than that of the GA, which is in turn better than that of the RA. The same conclusion can be drawn in fig. 10, mainly because the solution obtained by GA algorithm is only the local optimal solution, and the solution of RA algorithm is randomly generated, and its performance is not as good as that of SA algorithm.

It was noted in the previous analysis that if the remaining time of the message is longer, both the MUB and the RMUB would set the offer lower because they have sufficient time to bargain. The same conclusion is seen intuitively in fig. 11, where both the MUB and RMUB prices trend downward as the time remaining in the message, represented by the abscissa, increases. Among these, the tendency of EMUB to decline is steeper than that of the MUB, and the main reason for this is that EMUB dominates the transaction and wants to share more cakes.

FIGS. 12 and 13 are simulated functions of the discount factors for MUB and EMBB, respectively. As can be seen from fig. 12, the MUB wants to obtain all cakes in the initial stage of bargaining, but as the remaining time of the message gets smaller and smaller, the MUB will continue to earn for reaching consensus as soon as possible, which satisfies the requirements for the functional properties in equation (35). Fig. 13 is a simulation function of the discount factor of the RMUB, and shows characteristics that more accurately simulate the variation trend of the RMUB discount factor.

Finally, the performances of the Rubinstein-Stahl game and the epidemic algorithm are compared. As can be seen from fig. 14, the cost corresponding to the Rubinstein-Stahl game is lower than that of the epidemic algorithm, for example, when the number of RNs is 30, the cost of the epidemic algorithm is 55, and the cost of the game is only 35. This is mainly because in the epidemic algorithm, once the price quote of the MUB is higher than that quote of RMUB, the transaction is completed, and such a processing manner undoubtedly increases the expense of the MUB.

The above description is only a preferred embodiment of the present invention, and the scope of the present invention is not limited thereto, and any simple modifications or equivalent substitutions of the technical solutions that can be obviously obtained by those skilled in the art within the technical scope of the present invention are within the scope of the present invention.

Claims

1. A method for optimizing task unloading based on network time delay and resource management is characterized by comprising the following steps:

step 1 revenue analysis

According to the definition of Nakamoto, a linear relation exists between the probability that the MUB can acquire the virtual currency and the data amount of the PoW problem; the more tasks the MUB calculates, the greater the probability that the MUB obtains the reward, and the higher the expected profit; let the task amount of a task be Q_nThe probability that the MUB can obtain the digital currency reward after the task is executed is p_incomeThen the gains obtained by the MUB are expressed as:

U_exp＝p_incomeQ_n(1)

step 2 time delay analysis

If a fog servers are deployed at the base station, the computing power is f_bnThe task amount is α Q_nThe PoW problem is migrated to the base station misty node, and the required transmission time is expressed as:

is the channel rate between the MUB to the base station; w_iRepresenting the bandwidth of channel i, P_mIs the transmit power of the MUB and,

for channel gain, ω_iAnd I_iRespectively generation by generationTable noise and interference for channel i;

further the total time taken to offload a task to the BN is:

in addition, b calculation capacities are all f within the communication range of the MUB_fnThe fixed position fog server of (2), the task amount is β Q_nThe transmission time required for migrating the PoW problem to FN is expressed as:

representing the channel-reaching rate between the MUB and the jth FN; w_jIs the bandwidth, P, of channel j_mIs the transmit power of the MUB and,

for channel gain, ω_jAnd I_jRepresenting the noise and interference of channel j, respectively;

the total time required to unload the task to the FN is:

c pieces of c pieces_mnThe fixed position fog server of (2), then the task amount is gamma Q_nThe transit time taken for the PoW problem to migrate to the MN is expressed as:

representing the channel rate from the MUB to the kth MN; w_kFor the channel bandwidth, P_mIs the transmit power of the MUB and,

for channel gain, ω_kAnd I_kRepresenting the noise and interference of channel k, respectively;

the time required for the MN to process the data is:

the total time required to offload the task to the MN is then stated as:

according to the above analysis, the total delay for successfully solving the PoW problem is expressed as:

T_s＝arg max(T^bn,T^fn,T^mn)+T_back(11)

in the formula, T_backRepresenting the time consumed by a certain network node for returning the transaction record information to the MUB through a return link after the PoW problem is successfully solved; since the returned information after the PoW problem is successfully solved is the transaction record in the block chain system, compared with the task amount of the PoW problem, the data amount of the transaction record is very small, and is set to 0 in many researches, and the returned information is adoptedWith the same analysis method, the expression of the task execution delay is finally obtained as follows:

T_s＝arg max(T^bn,T^fn,T^mn) (12)

step 3 stage of expenditure analysis

The residual resources and the total resources of the nodes are taken as factors influencing the quotation of the fog nodes, and the purpose is to compare the quotation of the three types of fog nodes on the same standard, improve the fairness of quotation among the nodes and facilitate the MUB to select the most economical task unloading mode; unit quotes for three types of fog nodes are expressed as:

in the formula (I), the compound is shown in the specification,

and

respectively representing the total storage resource, the total calculation resource and the total power resource of the base station fog node; s^bn(t)、c^bn(t) and e^bn(t) respectively representing the residual storage resources, computing resources and power resources at the moment t;

and

the weight values represent the influence of three different types of resources on the price respectively; different types ofThe emphasis of the misty nodes on each resource is different, for example, MN pays more attention to power resource, so

Will be higher than

And

at the same time higher than

And

the symbol definitions in the formulae (14) and (15) are in accordance with the above analysis;

step 4 two-stage expenditure analysis

Let the total time of MUB consumption in the second stage be T_s2；

if true; the time spent by the MUB in the second stage is expressed as:

further, m and n satisfy the following relationship:

through T_s2After a time when the transaction is complete, let the MUB pay each RMUB for the duration of the transaction be C_i(t) i ═ 1,2.. n, then the total cost of the MUB in the second stage is expressed as

2. The method for optimizing task offloading based on network latency and resource management as recited in claim 1, further comprising step 5 of mathematically modeling

According to the definition of Nakamoto, the final benefit of the MUB is equal to the expected benefit minus the cost in the first and second phases, so the final benefit of the MUB is expressed as:

U_u＝Q_np_income-C_s1-C_s2(19)

accordingly, the optimization model that maximizes the benefit of the MUB is expressed as:

constraint C1 limits the total delay to T_τIn the range to ensure the speed at which the MUB resolves the PoW; c2 and C3 divide the total task into subtasks to be respectively unloaded to BN, FN and MN so as to achieve the purpose of reducing the total time for executing the tasks; the formula C4 ensures that during the second phase, the MUB can agree with 51% of the RMUB in the network to obtain virtual currency rewards; c5 separately requires the delay of the second stage, to ensure that the total time consumed in the second stage cannot exceed the time-to-live TTL of the message;

considering that the process of mining the MUB is mainly divided into two stages, and simultaneously, because the total expenditure in the optimization target also consists of the expenditure of the two stages respectively, in the process of relaxing the model, the original optimization model is decomposed into two sub-optimization models simultaneously, and the expenditure of the MUB in the two stages is optimized respectively; secondly, under the condition of fixed task quantity, maximizing the benefit of the MUB is equivalent to minimizing the overhead of the MUB, so the optimization target of the original optimization model is further converted after the original problem is relaxed.

3. The method for offloading optimization tasks based on network latency and resource management as recited in claim 2, wherein step 5 finally obtains two sub-optimization models, which are respectively expressed as:

sub-optimization model 1:

sub-optimization model 2:

because a nonlinear relation exists between the optimization target and the constraint condition of the sub-optimization model 1, the sub-optimization model is solved by using a simulated annealing algorithm suitable for solving the problem; for sub-optimization model 2, however, since there is a bargaining between the MUB and the RMUB, it is solved using the Rubinstein-Stahl game suitable for solving the bargaining problem.