WSN design based on polynomial time approximation and its improved algorithm

In order to meet certain performance objectives and network cost optimization in WSN design,a polynomial time approximation and its improved algorithm are proposed. Firstly,the problem is constructed as a multisink network-minimum cost-hop constraint problem,and then the problem is reduced to a modified version of the weighted set cover problem,and the solution of the problem is obtained by using the greedy algorithm for weighted set cover. Secondly,in order to improve the solution obtained by polynomial time approximation algorithm,the heuristic works by iteratively removing part of the current solution on the basis of the former,and rebuilding the solution by exploring other parts of the search space,thus,a higher quality solution can be obtained. The simulation results show that the proposed algorithm can not only achieve lower design cost, but also achieve less execution time under certain QoS requirements.