Interval Jobs Oriented Resource Allocation Research In CPS

Cyber-Physical System(CPS)is the next generation of intelligent system based on cloud computing,Internet of things and so on.It is a system with deep integration of information process and physical process which can have huge potential applications.Resource allocation is the core technology in the resource management CPS.CPS consists of a large number of heterogeneous resources,which are interconnected by high speed networks.In CPSs,different resources have different functions and thus have different abilities,which brings great challenges to resource management and allocation in CPS.Interval jobs refer to the ones that have fixed starting and finishing times,and the corresponding scheduling problem is called interval scheduling.In CPS job scheduling scenarios,there are lots of scheduling problems in the form of time interval,such as traffic flow monitoring and control in the peak period,target tracking in air defense early warning system and so on.These jobs in the form of time interval undoubtedly increased the difficulty of system resource allocation.Further more,in CPSs,sensors and other devices require to transmit data to computing devices and storage devices while getting data from environment.These data are analyzed and processed in real time to make timely decision.As a consequence,jobs in CPS often require a variety of resources to be completed,which can not be decomposed sequentially.Therefore,stably running of CPS can be realized by a flexible and efficient resource allocation technology,which could become one of the key technologies of CPS research.This paper is driven by performance requirements for CPS resource allocation and mainly concerns on the resource allocation problem in CPS that is interval jobs oriented,and provides theoretical basis of resource management technology in CPS while improving the efficiency of CPS system.The main contributions of this paper are as follows:(1)The basic concept and system structure of CPS are studied in this paper,as well as the system architecture of CPS resource allocation.According to the system configuration of CPS and the processing procedure of jobs,resource allocation architecture is proposed to unify resource call interface and to support effective allocation methods.The method of describing resources and jobs is also considered.Based on the optimization theory,the modeling method of CPS resource allocation problem is proposed,in which the representation form of the general problem is given.To study the stability problem of CPS,model based on queue system is presented,in which the mathematical expression of the parameters such as average queue length and waiting time that analyzed in experiments are derived.These approaches can provide a theoretical basis for the stability analysis of the system.(2)The stability analysis method of resource allocation in CPS is studied according to queuing theory.Job handling efficiency,that can have influence on system load performance,is determined by the strategy of resource allocation while system load performance has close relationship with system stability.Through regarding job inputs as stochastic process(such as Poisson process,etc),job inputs’ influences on system load performance are considered under different resource allocation mechanisms and the relationship between allocation mechanism and system stability is also established.By regrading utilization(approximate)optimal algorithm as an example,through modeling system’s states in different time as Markov Chain,which is analyzed using Lyapunov Drift theory,the conclusion of system stability is obtained.The corresponding proofs of theories and analysis are also proposed.Massive simulations are made to evaluate utilization of the algorithm under different job inputs which verifies the correctness of the theoretical analysis.The stability performance of the recommended algorithm is also studied while the parameter of job input changes.(3)Interval jobs oriented resource allocation method on single type of resource in CPS is researched.Models are constructed to minimize the total required resources under the condition of resource sufficient.Then the time constraints are transformed to an algebraic form by using Maximal Overlapping Subsets Algorithm,based on which an integer programming model is described.The approximated algorithms,GreedyBS and GreedyMR,are proposed to solve the model and the theoretical analysis of the complexity is also given based on submodular function’s property.In simulations,the performances of different algorithms on the optimality and running time are evaluated by comparison with branch-and-bound algorithm according to the integer programming model.The system stability as well as influence of related parameters on these algorithms are also analyzed.(4)Interval jobs oriented resource allocation method on multiple types of resource in CPS is studied under the condition of resource sufficient as well as resource constrained.In the condition of resource sufficient,to reduce the complexity and avoid the repetitive research,the problem is transformed into a single type of resource allocation problem through deep analysis of the problem.While in the condition of resource constrained,two situations are considered: A)no relations between job value and resource ability;B)job value and resource ability are related.The planning model of the problem is established by analyzing and comparing the similarities as well as differences of the resource allocation problem in A and B situations.Due to the hard constraint conditions of this problem,this paper proposes a feasible set judgment algorithm to verify the feasibility of the candidate job subsets,based on which algorithms GA and BnB are studied.Massive experiments are made to evaluate the performances and the effectiveness of different algorithms by comparison with Greedy algorithm.At the same time,methods for resource allocation problems in different scenarios are recommended,and a brief analysis of the stability is also discussed.(5)The application of CPS resource allocation method in the area air defense early warning system is discussed.Area air defense early warning system is a typical military Cyber-Physical system.Through deep analysis on the characteristics of the system resources and jobs,models are explored under the conditions of resource sufficient and resource constrained,which are solved by the methods proposed ahead with given simulation data.(6)In summary,this paper studies an allocation problem in operational research,also known as the assignment problem.Resource allocation problem exists in the practical application of many industries.With variety of the application environment,the optimization goal as well as the constraints of the allocation problem will also be changed,which brings varying of solutions.The difficulties in CPS resource allocation problem is the co-allocation of multiple resources,this paper considers the research of CPS resource allocation framework and model,relationship between allocation mechanism and system stability,single type as well as multiple types of resources allocation problems which are carried on step by step from the concept and character of the CPS.It is worth mentioning that,in the same or similar environment,part of the theories and methods proposed in this paper can also be applied to other areas,such as cloud computing,networking and so on.