Research On Exact Algorithms Of Optimal Routing Tree In Wireless Sensor Networks

In wireless sensor networks,a routing tree is used for data collection.In different routing trees,the number of messages sent and received by each node is different,so the performance of different routing trees is different.Because the energy of the sensor node is limited,finding the routing structure that makes the whole network survive for a longest time is a key problem.Optimal routing tree problem has been proved to be NP-hard.The current algorithm for this problem is usually heuristic algorithms and approximation algorithms,but these algorithms cannot guarantee an optimal solution.When evaluating such algorithms,we need to compare their outputs with the optimal solution.Although the time complexity of exact algorithms is exponential,the empirical running time of different exact algorithms is different.In this thesis,two exact algorithms are proposed to improve computational efficiency and reduce running time.Main contributions are as follows:(1)We propose speeding up existing exact algorithms by using multi-core CPU to their full potential.The previous exact algorithms are based on single CPU core.The basic idea is to decompose the problem into independent subproblems,and solve them on different cores,to accelerate the operation of exact algorithms by parallel computing.(2)We propose a new exact algorithm based on the branch and bound method.A new bounding method and a pre-processing mechanism are proposed.The bounding method makes the upper bound tighter by bounding twice.The pre-processing mechanism can reduce the solution space and the problem size.Extensive simulations show that the multi-core approach can accelerate the existing exact algorithm well,and the branch and bound algorithm can find the optimal solution faster.The proposed algorithms outperform existing algorithms in terms of the average running time and the number of solved networks within fixed time budget.