Research On Complexity And Algorithms Of Superposed-Data Uploading Problem

Nowadays,with the rapid development of Internet technology and scientific information,the continuous innovation and development of the Internet of Things have led to many combinatorial optimization problems.Prolonging smart devices'(SDs')battery life time has been a challenging open-ended question in edge computing systems which have significant applications in the industrial production environment.Aiming at this problem,we research on the energy consumption in the process of superposed-data transmission based on the data transmission in actual network communication.This paper proposes a special solution for the special case where data is transmitted andmerged between SDs of a certain size and finally transmitted to in vehicle base stations(VBSs)or servers.We specifically consider the data transmission problem of distributed devices in the device communication system to minimize the total energy consumption of uploading data as the research goal.For better analysis and research,we transform this problem into a combinatorial optimization problem,which we call the superposed-data uploading problem(SDUP).This paper systematically studies how to analyze and solve the problem in different situations and combined with the actual situation from the perspective of computational complexity and algorithm design.From the perspective of computational complexity,the paper analyzes the complexity ofthe SDUP by using different methods for the limited and unlimited server capacity.In the case of unlimited capacity,we designed a polynomial-time algorithm based on the Prim to demonstrate that the SDUP is a P problem.In combination with the actual situation,when the server capacity is limited,we prove that the SDUP is NP-hard through k-MST*problem specification.From the perspective of algorithm design,this paper designs an approximation algorithm,polynomial optimization algorithm and two different heuristic algorithms for the difference of computing complexity of SDUP in different situations.For the SDUP,it is NP-hard when there are only two servers.For this reason,we propose an approximation algorithm with an approximation rate of 2.In addition,for the SDUP,when the servers capacity is not limited,we design the polynomial optimization algorithm I-SDUP based on the Prim algorithm;when the servers capacity is limited,we design the D-SDUP heuristic algorithm based on the Dijkstra and P-SDUP heuristic algorithm based on Prim algorithm,and compare and analyze the performance of the algorithms through experiments.This paper is a new application of combinatorial optimization problems and has certain reference values for theory research of network data transmission and parameter calculation.