| Wireless networks can have properties not present in traditional wired networks. There is no physical backbone, and wireless nodes may be operating with a limited energy supply, as is the case for wireless sensor networks. We can adapt the idea of a wired network's physical backbone, creating virtual backbones. Therefore, in this dissertation, we examine how we might construct a virtual backbone for improved energy efficiency in broadcasting and routing. In detail, we consider cluster-based routing and CDS construction with guaranteed routing cost.;We propose a new problem based on customer fairness, which looks for a minimum CDS in a given communication model with shortest path constraints. It guarantees that any two clients can communicate with each other through this CDS with hop counts the same as the best path from the original graph, which means that routing on such a CDS will not bring additional traffic for every client.;Since the shortest path constraint is very strict, we study a CDS with relaxed constraint, in which we guarantee any two clients can communicate with hop count a most a constant factor from that in the original graph. We propose a heuristic algorithm, and we demonstrate that this relaxation is helpful since the CDS size is reduced greatly.;To further save energy consumption, we apply directional antennas to CDS construction. We study a special virtual backbone (VB) using directional antennas, requiring that from one node to any other node in the network, there exists at least one directional shortest path all of whose intermediate directions should belong to the VB.;Previously, Minimum Average Routing Path Clustering Problem (MARPCP) in multi-hop USNs was studied. The goal of this problem is to find a clustering of a USN so that the average clustering-based routing path from a node to it nearest underwater sink is minimized. We relaxed MARPCP to a special case of Minimum Weight Dominating Set Problem (MWDSP), for which we propose a PTAS. Derived from this result, we give a (3 + epsilon)-approximation algorithm for MARPCP. |
