An Algorithmic Study On Two Kinds Of Covering Problems In The WSN

As a new information acquisition and processing technology,Wireless sensor network is one of the most important technologies in the 21 st century,which is widely used in many fields such as anti-terrorism disasterm,national defense,health care and environmental monitoring.The covering problem is one of the most important research focuses in wireless sensor networks,which is widely used in target identification,monitoring,tracking and so on.Recently,the target coverage types are divided into three categories: point coverage,line coverage and regional coverage.This thesis is divided into three parts.The first part is the basics knowledge of preparation and issues.This part presents a graph theory,combinatorial optimization and computational complexity and other related knowledge,and introduces the wireless sensor networks covering background issues,applications,development history and some of the research results.The second part is the main content: the study of two types of wireless sensor networks covering problem,segments coverage and points coverage under certain conditions.The first one is segments coverage problem with the certain restrictions: the goal line in the horizontal or vertical position and the maximal length does not exceed twice of the sensor sensing radius.As the problem is NP-hard,we design an approximation algorithm for solving the problem by dividing the plane,this algorithm's performance ratio is 18 and time complexity is O(n~2).In addition,we get algorithm simulation and stability test with Java program.Finally,we obtain some new conclusions for the general case of the problem.The second one is point coverage problem subject to: the deployment location can not cross a line(Resitricted by geographical conditions or other factors,deployment location of the sensor there may have some restriction).We design an approximation algorithm for solving the problem,whose performance ratio is 2 and time complexity is O(nlog n).Similarly,we also get algorithm simulation and stability test with Java program.The third part is summarizes and expansion.We summarize the main contents and provide some prospects for further research.