UC Irvine

Establishing robust connectivity in heterogeneous networks (HetNets) is an important yet challenging problem. For a heterogeneous network accommodating a large number of nodes, establishing perturbation-invulnerable connectivity is of utmost importance.

This dissertation provides a robust advantaged node placement strategy best suited for sparse network graphs. In order to offer connectivity robustness, this work models the communication range of an advantaged node with a hexagon embedded within a circle representing the physical range of a node. Consequently, the proposed node placement method in this dissertation is based on a so-called hexagonal coordinate system (HCS) in which we develop an extended algebra. We formulate a class of geometric distance optimization problems aiming at establishing robust connectivity of a graph of multiple clusters of nodes. After showing that our formulated problem is NP-hard, we provide a heuristic algorithm based on HCS that efficiently solves the problem. Performance evaluation on different aspects of the algorithm is given. The results show that our algorithm is most effective in sparse networks for which we derive classification thresholds.

After connectivity is established, we consider the problem that when some nodes are exposed to mobility, how to maintain connectivity.

In this part, the network of interest consists of two types of nodes, pre-deployed (client) and intermediate nodes. We assume full control on the intermediate nodes but not the pre-deployed nodes. In such networks, on which we have only partial control, two types of node mobility scenarios are investigated. The first scenario analyzes the bounds of mobility when pre-deployed nodes move at small scales.

The bounds of node mobility preserving connectivity are derived through analysis and verified by simulations.The second scenario considers the movement of pre-deployed nodes beyond the bounds of the first scenario thereby breaking connected links and partitioning the connected network. This scenario then considers relocating the existing intermediate nodes in order to reestablish connectivity. A general formulation is proposed in the form of an optimization problem. We prove that the general formulation of the problem is NP-hard. Next, we turn our attention to a practical scenario in which the location of nodes is made available using GPS signals. We solve the problem of the practical scenario in polynomial time and analyze the complexity of our solution.

We also present comprehensive performance evaluation results of our proposed algorithm.