Clustering in wireless sensor networks

In our discussion of wireless networks, selection for connected or unconnected clusters (dominating sets) is the main approach to solve certain problems in WSNs. First, we discuss the problem of finding a backbone in wireless ad-hoc networks, namely, the minimum d-hop connected dominating set problem. We prove that this problem is NP-Complete for planar unit disk graphs, one of the simplest topologies in wireless networks. We extend a few known heuristics for 1-hop dominating sets to the d-hop case.;For the network lifetime problem in WSNs, we discuss the problem of finding the maximum number of connected dominating sets to extend the network lifetime. For the problem of extending network lifetime for area coverage with minimum total power usage, we discuss the problem of finding the maximum number of dominating set in which each set covers all nodes that are not in the dominating set. For both of these network lifetime problems, we provide the NP-Completeness proofs and propose heuristics.;For the energy efficiency problem in WSNs, we discuss the problem of building a backbone for data transferring and local base station for data receiving by using dominating set and connected dominating set. We reduce the power usage of each node by constructing a d-hop dominating set to serve as local base stations. For data transferring, we construct a connected dominating set to act as a backbone of the WSN. We show that computing a minimum d-hop dominating set or finding a d-hop connected dominating set for simple topologies such as planar geometric graphs is NP-Complete. We also provide heuristics and investigate the trade-offs between power usage and dominating set size.;In our study of interference, we first look at the problem of finding a simple topology such as planar trees as a natural way to reduce interference in WSNs. We prove that the problem of finding a planar geometric tree with minimum total energy usage is NP-Complete. Looking further to the proposed interference model in [6], [4], [29] and [67], we prove that the problem of assigning power to nodes in the plane to yield a planar geometric graph whose nodes have bounded interference is NP-complete under the receiver interference definition. These problems were left open in [6], [4] and [29].