DISTRIBUTED FLOW OPTIMIZATION IN DENSE WIRELESS NETWORKS

Abstract

Due to large number of variables, optimizing information flow in a dense wire- less network using discrete methods can be computationally prohibitive. Instead of treating the nodes as discrete entities, these networks can be modeled as continuum of nodes providing a medium for information transport. In this scenario multi-hop information routes transform into an information flow vector field that is defined over the geographical domain of the network. At each point of the network, the orientation of the vector field shows the direction of the flow of information, and its magnitude shows the density of information flow. Modeling the dense network in continuous domain enables us to study the large scale behavior of the network under existing routing policies; furthermore, it justifies incorporation of multivariate calculus techniques in order to find new routing policies that optimize a suitable cost function, which only depend on large scale properties of the network. Thus, finding an optimum routing method translates into finding an optimal information flow vector field that minimizes the cost function. In order to transform the optimal information flow vector field into a routing policy, connections between discrete space (small scale) and continuous space (large scale) variables should be made and the question that how the nodes should interact with each other in the microscopic scale in order that their large scale behavior become optimal should be answered. In the past works, a centralized method of calculating the optimal information flow over the entire geographical area that encompasses the network has been suggested; however, using a centralized method to optimize information flow in a dynamic network is undesirable. Furthermore, the value of information flow vector field is needed only at the locations of randomly scattered nodes in the network, thus calculation of the information flow vector field for the entire network region (as suggested in previous models) is an unnecessary overhead. This poses a gap between the continuous space and discrete space models of information flow in dense wireless networks. This gap is how to calculate and apply the optimum information flow derived in continuous domain to a network with finite number of nodes. As a first step to fill this gap, a specific quadratic cost function is considered. In previous works, it is proved that the the vector field that minimizes this cost function is irrotational, thus it is written as the gradient of a potential function. This potential function satisfies a Poisson Partial Differential Equation (PDE) which in conjunction with Neumann boundary condition has a unique solution up to a constant. In this thesis the PDE resulted by optimization in continuous domain is discretized at locations of the nodes. By assuming a random node distribution with uniform density, the symmetries present enable us to solve the PDE in a distributed fashion. This solution is based on Jacobi iterations and requires only neighboring nodes to share their local information with each other. The gradient of the resulting potential defines the routes that the traffic should be forwarded. Furthermore, based on a graph theory model, we generalize our distributed solution to a more general cost function, namely, the p-norm cost function. This model also enables us to enhance the convergence rate of the Jacobi iterations.