Research On Area Coverage And Point Covering Problems Based On Graph Theory

Area coverage and point Covering problem are two fundamental problems in computer geometry. In practice, coverage problems are mainly used in wireless sensor networks, biological networks which distributed in 3 dimensional space. The earliest coverage problem is gallery problem, which mainly study how to deploy a minimum number of cameras to cover the entire gallery. Energy efficient coverage problems are able to save energy or prolong the lifetime of the networks. Wireless networks have a good prospect in many fields such as national security, supporting battlefield communications, emergency relief scenarios and environmental monitoring. Therefore, it has an important practical significance to study efficient coverage algorithms.In terms of classification, the main current coverage problems are point covering problem, area coverage problem, target coverage problem and path coverage problem. Coverage problems have two kind of targets, one is how to guarantee a full coverage with minimum number of nodes, another is how to guarantee a full coverage and maximize the lifetime of the entire networks at the same time. Methods used to study the problem of coverage are some computational geometry and graph theory methods such as Voronoi graph, Delaunay triangulation, the classical algebraic topology methods, connected dominating set and integer programming. Since the coverage problems usually involves very classic mathematical problems, for example, hole detection by algebraic topology approach and consistency problem can both be modeled by the high dimensional Laplacian Matrix. Therefore, coverage problems attract a large number of researchers in different fields.The main contributions of this paper is as follows,1. we present the coverage criteria based on only connectivity information in 2D and 3D.2. we propose a construction algorithm of connected dominating set with the current best approximation ratio in DGB and BGB. In this paper, we introduce the research status of the point covering problem, area coverage problem, target problem and path coverage problem. Through target coverage problem, we first present a brief analysis of the relations and the differences in the algorithm design goals and models of various coverage problems. Then we give some commonly used methods of solving the problem of coverage problems, such as linear programming, connected dominating set problem.For the area coverage problem, we first give a description of the basic algebraic topology method, including simple complex, mixed Laplace Matrix, cycle space theory. Then we give some concrete examples for hole detection in 2D and 3D space. At last, in this paper we present the coverage criteria based on only connectivity information in 3D. We prove that when the transmission ratio is ??(?), the interior area of 2-cycles is full covered. This criteria has a great significance for design of area coverage algorithm in 3D space. We also present some open problems on solution spaces of XOR equations and the minimum bases of high dimensional cycles. For the point covering problem, in this paper we propose a construction algorithm of connected dominating set with the current best approximation ratio in DGB and BGB. First, in two dimensional space, we use classical circle packing problem to analyze the upper bound of maximal independent set in DGB. In DGB, when the transmission range ratio is (1,1.152], (1.152,1.307], (1.307,1.407], (1.407,1.462], (1.462,1.515], (1.515,1.618], (1.618,1.932], the size of any Maximal Independent Set is upper bounded by 6opt+1,7opt+1,8opt+ 1,9opt+1,10opt+1, 11opt+1,16.7778opt+1.2222, where opt denotes the size of an optimal solution of the CDS problem. It means that all the approximation ratio of construction algorithms of connected dominating set are improved. Then, the analysis method is extended to 3D space. Upper bounds for maximal independent sets in BGB are given by the classical sphere packing problem. In other words, the method proposed in this paper is not only applicable to the network distributed in two-dimensional space but also the three-dimensional space.