Research On Computational Complexity And Algorithm Of Sustainable Communication Network Construction

With the development of 5G technology,the advantages of high speed,large capacity and low latency of 5G network make it widely applied in industrial production and social life.However,the shortcoming of 5G signal transmission distance will lead to an increase in the number of base stations deployed during the 5G network upgrade process,which in turn increases the cost.In this context,this paper studies the construction of wireless sensor networks for sustainable communication in the Industrial Internet of Things.The task of this network construction problem is to optimize energy saving by deploying relays at suitable locations so that:(1)the data from the IoT device terminals can be transmitted to the sink node;(2)the IoT devices are running out of battery power.It can be wirelessly charged by a certain relay.In this paper,different situations of this problem are mathematically modeled mainly from a theoretical level,and their computational complexity and algorithms are studied.The specific research contents mainly include the following two aspects.In this paper,the following two constraints on the construction of wireless sensor networks with sustainable communication are discussed:(1)whether the deployment locations of relays are constrained;(2)whether the number of relays is limited.Combined with the energy loss model of sustainable communication network studied in this paper,three reasonable mathematical models are proposed,and three different combinatorial optimization problems are obtained.This paper uses two NP-hard problems to prove by polynomial reduction that when the number of relays is limited,the combinatorial optimization problems corresponding to these two cases are both NP-hard regardless of whether the relay position is constrained or not.In addition,this paper proves that when the positions of relays are constrained but the number of relays is unlimited,the corresponding combinatorial optimization problem is polynomial-solvable through a polynomial optimal solution algorithm.In addition,this paper proves the unapproximatability of the above two NP-hard problems.In this paper,the algorithm of combinatorial optimization problem corresponding to the situation that the positions of relays are constrained and the number of relays are limited in the construction of wireless sensor network with sustainable communication is studied.In view of the NP-intractable and the unapproximatability of this problem,this paper proposes two heuristic algorithms with different time complexity and energy consumption by using local search technology,and compares the performance of these two algorithms through simulation experiments.analyze.Experimental data show that in most cases more algorithm running time can lead to less energy consumption.However,when the problem input reaches a certain condition,the energy consumption of the two algorithms is not significantly different.The wireless sensor network model of sustainable communication and its computational complexity proof proposed in this paper have certain theoretical significance.The heuristic algorithm proposed in this paper can be used as a reference for solving related computing problems in practical applications,so it has certain application value.