Research On Parameterized Algorithms For Several NP-hard Problems In Wireless Networks

With increased complexity of the wireless networks design, more and more computation problems emerging from the application of wireless networks have been proved to be NP-hard with high complexity. As a new method solving NP-hard problems, parameterized computation method has attracted lots of attention, and has been used to solve hard problems in many fields.In this thesis, we mainly study four classical NP-hard problems emerging out of the fields of wireless networks:min-energy multicast routing, connected dominating set, max-lifetime target coverage and total p-domination. By employing the technology and theory of parameterized computation, based on discovering parameter characters of these problems, we study for them the construction of parameterized model, the analysis of multivariate parameterized complexity, and the design and implementation of parameterized algorithms.For Min-power Multicast, construction of parameterized model, multivariate parameterized complexity analysis, the design and implementation of parameterized algorithm are researched. Single Multicast is an efficient mechanism for one to many communication, and small group multicast, i.e., the size of the multicast group is small, has important applications in wireless ad hoc networks. Since the wireless nodes are battery powered and bounding the network delay is a critical issue for the QoS of the networks, it is essential to design delay-bounded and energy efficient multicast routing in wireless ad hoc networks. We first study Min-power Single source h-Multicast where the task is to find a minimum energy multicast tree in which the path between the source and every destination node is less than h hops. We first formalize it as a garph optimization problem, and then, based on the method of dynamic programming, present an exact algorithm in time0(3*·(n+m)·h+2k·(n+m)2·h). Herein, k is the size of the multicast group, n and m denote the numbers of vertices and edges of the networks, respectively. Simulation results show that, compared with existing heuristic or approximation algorithms, our algorithm saves energy consumption by factors between19%and42%with comparable running time for small group multicast. We further extend our study to multi-source multicast and strongly connected multicast. Multi-source multicast requires that each source can communicate with any destination, while strongly connected multicast requires any node in a set D of nodes can communiate with other nodes in D. By parameterized reduction, we then show that Min-power Multisource h-Multicast is W[2]-hard with respect to the number of senders, and Min-power Strongly Connected h-Multicast is W[1]-hard with both the number of terminals and the number of senders k2as parameters. Finally, we proved that Min-power Single-source h-Multicast with respect to combined parameter (k, k2) does not admit a polynomial kernel.For Planar Connected Dominating Set, an improved kernelization algorithm is designed. In wireless networks, Connected Dominating Set is usually used to construct the virtue backbone so as to provide effective communication infrastructure for broadcast and routing. By coloring the vertices in the graph, we observe many new combinatorial properties of its vertices, and then present a set of new, efficient and polynomial-time reduction and coloring rules exploring local structures of the graph. By using the method of region decomposition, we then decompose the reduced graph into at most3k-6regions where k is the size of solution for connected dominating set. We further classify the regions into two types, based on the distance between their anchor vertices:regions with distance one between their corresponding anchor vertices and regions with distance at least two between their anchor vertices. By using the connectivity property of the problem solutions, we can bound the number of the regions of the second type by2k-5. By combining the coloring reduction rules and properties of planar graph, we bound the number of vertices in the first type region by23and that in the second region by41. By fully using connectivity property of the problem solution and structure characteristics of region, we finally bound the number of vertices outside the regions, and then obtain a kernel of size130k for the Planar Connected Dominating Set problem, which is the currently best result.For Max-lifetime Target Coverage, multivariate parameterized complexity analysis and parameterized algorithms are researched, the task of Max-lifetime Target Coverage is to partition the sensors into groups and assign their time-slots such that the coverage lifetime is maximized while satisfying some coverage requirement. To gain insight into the source of the complexity, we initiate a systematic parameterized complexity study of two types of Max-lifetime Target Coverage: Max-min Target Coverage and Max-individual Target Coverage. We first prove that both problems remain NP-hard even in the special cases where each target is covered by at most two sensors or each sensor can cover at most two targets. By contrast, restricting the number of targets reduces the complexity of the considered problems. In other words, they are both fixed parameter tractable (FPT) with respect to the parameter "number of targets". Moreover, we extend our studies to the structural parameter "number k of sensors covering at least two targets". Positively, both problems are in FPT with respect to k. Finally, we show that Max-min Target Coverage can be solved in time O*((6.1k1k2)k1k2), where k1deontes the number of groups and k2denotes the number of targets covered by each group.For Total p-Domination, parameterized complexity analysis and the design of parameterized algorithm are researched. In wireless networks, Total p-Domination is usually used to construct the self-protection networks. We first prove that Total p-Domination is still NP-hard in UDG with vertex degree bounded by3. To gain insight into the source of the complexity, We further study the parameterized complexity of Total p-Domination in UDG. By parameterized reduction from k-clique, we show that Total p-Domination is W[1]-hard in UDG. Based on the methods of tree decomposition and dynamic programming, we finally design a parameterized sub-exponential algorithm in time O((2p+2)19.1·√kk3n+n3) for Total p-Domination in planar graph, where n is the number of vertices in given instance and k is the size of the solution.