Sensor Network Information Flow Dynamics
Abstract
The objective of this research is to develop numerical techniques for solving Partial Differential Equations (PDE) that govern information flow in dense wireless networks. Despite the analogy of information flow in dense wireless networks to physical phenomena such as thermodynamics and fluid mechanics, many physical and protocol imposed constraints make the information flow PDEs unique and different from the observed PDEs in known physical phenomena. The approach is to develop a systematic method where a unified framework is capable of optimizing a broad class of objective functions on the information flow. The objective function is defined depending on property of interest in the geometric paths of information. This leads to a set of PDEs whose form varies depending on the optimization objective. Finally, numerical techniques will be developed to solve the PDEs in a network setting and in a distributed manner.
Different methods for routing the traffic in these networks have been studied. Most of these methods model the network as a discrete set of nodes. As the number of nodes grows, careful behavioral analysis of a wireless sensor network becomes very hard by using these conventional methods that employ a discrete model in space. A shortcoming of discrete space approaches is that often the traffic flow models become computationally prohibitive when the number of wireless nodes grows large. As the number of wireless nodes increases, information transport is done in a sequence of many short range multihop transmissions in a medium of massively large number of nodes, and therefore, information can be treated as a fluid being transported through a continuum of nodes. Based on this observation, we propose a continuous space model to formulate flow of information in a wireless network that has a massively large number of sensors. In the proposed methodology an information flow vector field models the transportation of traffic. This vector field has two components at each location of the network: a magnitude representing the density of traffic at that location and an orientation that gives the direction to which the traffic is forwarded.
Basic flow conservation laws and optimization of a communication cost function results in equations very similar to Maxwell equations governing information flow in the network with a high density of wireless nodes. Furthermore, optimizing a quadratic form of the communication cost will result in an information flow vector field that is conservative (or irrotational). As a result, the information flow vector field is the gradient of a potential function defined over the domain of the network. The potential function satisfies a Poisson PDE with Neumann boundary condition. Solution of this PDE leads to a simple mechanism for routing the traffic: each node forwards the traffic to a neighbor with least potential (steepest potential decent).
An advantage of continuous space model for information flow is the use strong analytical tools of vector calculus for optimization of information routes in a network; however, a main shortcoming is that the potential function that is essential for routing, can only calculated in a centralized way. In such centralized schemes, it has been assumed that a central node calculates the potential of nodes and sends the results to the nodes in the network. This is practically impossible in networks with large number of nodes in dense wireless networks.
An important milestone of this research is to bridge the gap between the continuous space models and discrete space models of information flow in massively dense wireless networks. We provide a method to compute the potentials in a distributed fashion such that each node computes its own potential as a function of its neighboring nodes potentials. Additionally, the proposed method is discrete and the potential value is calculated at locations of wireless nodes. The discrete and decentralized scheme for calculation of potential function enables the routing method based on the potential function to be employed in networks with large number of nodes in a geographically distributed region. The continuous Poisson PDE is converted to a discrete model that is valid at locations of wireless nodes using a Finite Difference Method (FDM). The discrete algorithm for finding potential function uses iterations in which each wireless node only needs to communicate with its neighboring nodes to compute and update its potential value.
Award ID: 0931957