Handbook on Array Processing and Sensor Networks

CHAPTER 23

Routing for Statistical Inference in Sensor Networks

A. Anandkumar¹, A. Ephremides², A. Swami³, L. Tong³

¹Cornell University

²University of Maryland

³U.S. Army Research Laboratory

23.1 INTRODUCTION

Routing in communication networks, both wireline and wireless, has been a subject of extensive and in-depth study over the last few decades. It is a subject that is fairly well understood. Its state-of-the-art status can be summarized as follows: If a well-defined performance measure can be translated to a link metric, then there are low-complexity, efficient, robust, fast-converging, and often distributed algorithms for finding the optimal routes. Note the important distinction regarding the possibility of mapping the performance measure to a link metric. For example, on the Internet, if end-to-end latency is the performance measure, then the link metric is delay over the link. Bellman-Ford types of algorithms then perform very well and quickly discover the best routes [1]. By contrast, on the traditional circuit-switched voice telephone network, where the performance measure is blocking probability, there is no known link metric that captures the performance measure and, hence, up to this day we only have heuristic routing algorithms for assigning routes to accepted calls.

At this point it is also important to note that the routing problem, being basically a discrete optimization ...