Lattice Sensor Networks: Capacity Limits, Optimal Routing and Robustness to Failures
We study network capacity limits and optimal routing algorithms for regular sensor networks, namely, square and torus grid sensor networks, in both, the static case (no node failures) and the dynamic case (node failures). For static networks, we derive upper bounds on the network capacity and then we characterize and provide optimal routing algorithms whose rate per node is equal to this upper bound, thus, obtaining the exact analytical expression for the network capacity. We also provide the scaling law for the required size of the node buffer as a function of the network size. For dynamic networks, the unreliability of the network is modeled in two ways: a Markovian node failure and an energy based node failure. Depending on the probability of node failure that is present in the network, we propose to use a particular combination of two routing algorithms, the first one being optimal when there are no node failures at all and the second one being optimal when the probability of node failure is sufficiently high. The combination of these two routing algorithms defines a family of randomized routing algorithms, each of them being appropriate for a given probability of node failure.