Research On Path Optimal Allocation Algorithm For Multi-channel Real-time Monitoring System

Real-time monitoring in the field of industrial control often involves specific monitoring networks or sensor networks.The network usually has a large number of intermediate nodes,and the monitoring and troubleshooting of the specific parameters need to consider the specific constraints.In the process of finding the optimal measurement and diagnosis scheme,it is necessary to optimize the path of the network and finally generate the optimal measurement path automatically.The path optimization problem usually involves some specific requirements,such as finding the optimal node measurement order;the cost of the optimal path is the smallest;the measurement path must go through some special nodes;adapt to the dynamic changes of the network topology and so on.Because the network size is large and the node resources are strictly limited,the path optimization algorithm of network nodes data acquisition is simply designed and to reduce the algorithm storage and computing cost as much as possible.This paper focuses on solving a class of path optimization problem with constraints,that is,the optimal path problem with protection points.The problem model can be simply described as a shortest path from the starting point,through all the points within a particular set,and finally to the end point.The problem of the optimal path in the ILP solver could be solved by the method of integer linear programming,but the problem is that the time complexity of the solution will increase exponentially with the problem scale,since this is similar to traverse all possible paths from the origin to the end by the way of breadth-first search or depth-first search.In the case of an increase in the size of the network,ILP solvers often can not find the optimal solution to the problem within a reasonable time,or even find a feasible solution.In order to solve the difficulty of this problem,this paper tries to find the approximate optimal solution of the problem in a reasonable time with a heuristic method.In this paper,we try to combine the ACO algorithm with the SK algorithm,and solve the other problems of the SK algorithm in the concrete implementation.The new SK_ACO will give full play to the advantages of the two algorithms,especially the use of ACO pheromone concept to optimize the solution structure,and the improved SK algorithm to fully play out the useful information of middle solutions,so that the new algorithm to find a feasible solution will be greatly improved.Finally,the results of the SK_ACO algorithm are compared with the results of CPLEX in the experiment.SK_ACO algorithm mainly use the three representative versions of ACO: AS,MMAS and ACS.The experimental results show that the improved SK algorithm with MMAS or ACS has higher performance than AS algorithm.The experiment compares the probabilities of the feasible solutions from the reasonable CPU computation time,the probability of the relative errors at different given point ratios,and time-consuming between the improved heuristic algorithm and the CPLEX solver.The results show that the SK_ACO algorithm can achieve better results when the ratio of protection points is low,and the computation time is much less than that of CPLEX solver.Therefore,the SK_ACO algorithm is a more effective way to solve most of these problems.