Resource optimization in wireless and optical networks

In this work, we discuss some resource optimization problems in wireless and optical networks. In chapter 1, we consider Minimum Strongly Connected Dominating and Absorbent Set (MSCDAS) problem in a heterogeneous wireless ad-hoc network, where nodes may have different transmission ranges. The MSCDAS problem is the counterpart of minimum connected dominating set problem in a homogeneous wireless ad-hoc network. Since MSCDAS problem is NP-hard, we introduce a constant approximation algorithm when the ratio of the maximum to the minimum in transmission range is bounded. We also present two heuristics and compare the performances of the proposed schemes through simulation. In chapter 2, we discuss a fault-tolerant power assignment problem in wireless sensor networks, where a node can have either low power or high power. Specifically, a power assignment for 2-edge connectivity is considered, assuming that the graph induced by the power assignment must be symmetric. Since the problem is NP-hard, we propose an approximation algorithm called Prioritized Edge Selection Algorithm. We prove that the PESA achieves an approximation ratio of 4 and show the tightness of the approximation bound. We also provide experimental results on the performance of the algorithm through simulation. In chapter 3, we consider the Minimum Frequencies for the Virtual Maximum MAC Capacity (MFVMC) problem in a multichannel wireless ad-hoc network. The objective of this problem is to find the minimum frequencies to guarantee collision-free transmissions for any maximum matching of a given graph. Focusing our interest on the set of unit disk graphs with maximum node degree d, we prove that theta(d) is the tight bound for the MFVMC problem. We discuss the implications of this result on the asymptotic network capacity of a multichannel wireless ad-hoc network.; In chapter 4 and 5, we discuss techniques to enhance the performance of a wavelength-routed network with wavelength-continuity constraint. Specifically, we discuss a novel signaling mechanism referred to as label prioritization in chapter 4. The label prioritization attempts to reduce the backward-link blocking in GMPLS-centric all-optical networks by assigning different priorities to the suggested wavelengths of each connection request. The label prioritization mechanism consists of two components: a signaling extension to GMPLS to support the label prioritization and a modification in the optical switch controller to support the signaling extension. Simulation results show that the label prioritization method can effectively reduce wavelength conflicts. Finally, in chapter 5, we study the impact of imprecise network state information on dynamic routing and wavelength assignment (RWA) under a distributed control architecture with dynamic traffic. We evaluate existing techniques in the case of inaccurate network state information and propose two techniques to improve the overall blocking performance and reduce control overhead. Extensive simulation results with various underlying topologies show that the proposed techniques can significantly improve the overall blocking performance and reduce control overhead when there exists imprecise network state information.