Geometric optimization issues in wireless networks

Geometric optimizations play a very important role in wireless networks because wireless communications are performed via open space and the signal strength corresponds directly to the distance between wireless devices. This dissertation presents and solves several geometric optimization issues in wireless networks. The dissertation first proposed algorithms to construct optimal virtual cellular networks for non-uniformly distributed base stations. The constructed virtual cellular networks are optimal in the sense that their corresponding uniform cell sizes reach the largest possible. The algorithms work for mesh networks as well as honeycomb networks. Based on a novel concept, referred to as the projection locus, both kinds of optimal virtual cellular networks can be constructed in O(nlogn) time for n non-uniformly distributed base stations.; The dissertation also proposed a new geometric diagram, referred to as the umbrella diagram. The umbrella diagram is comparable to the well known Voronoi diagram. The Voronoi diagram deals with a set of points, whereas the umbrella diagram deals with a set of different hexagonal networks derived from a set of points. The umbrella diagram of a set of hexagonal networks is to divide the plane into regions such that the points in a region have a larger distance to one network than to the other networks. Unlike the Voronoi diagram, the regions in the umbrella diagram are not necessarily convex. The dissertation shows that the umbrella diagram of n networks with the same hexagon size and orientation can be computed in O(n3) time.; The umbrella diagram can be used to solve many problems in wireless networks. The dissertation applied the umbrella diagram to solve the problems of the optimal network deployment and the maximum sensor reuse. The optimal network deployment problem is to optimally deploy a cellular network such that the distance between the existing base stations and their corresponding cell centers is minimized. The maximum sensor reuse problem intends to apply a new sensor network in a way to maximize the number of existing sensors that are within a given communication bound.