Tutorial 1: 9:00 - 12:00 (Mon, 29th Jan)

Title: "Mathematical Modeling of Data-Centric Querying
in Wireless Sensor Networks"

Speaker: Bhaskar Krishnamachari (USC, USA)

Abstract: The central paradigm of data-centric networking in wireless sensor networks allows for in-network storage of named events and their retrieval through on-demand queries. Much of the activity in querying protocol design and evaluation for sensor networks has focused on a design-by-intuition/validate-by-simulation approach. However, particularly given the scarce resources and need for efficient operation, it is important to also develop complementary mathematical models that can provide quantitative insights into design tradeoffs, parameter optimization, protocol selection, and scalable operation.

A key aim of this tutorial is to show how to develop simple first-order mathematical models of querying mechanisms in order to characterize their performance in a general manner with respect to various design and application parameters.

We begin with a high-level discussion of the art of first-order mathematical modeling, emphasizing the importance of simplicity and identifying the key ingredients. We also discuss how such a mathematical modeling approach plays a complementary role to simulations and experimental evaluations.

Then, we provide an organized taxonomy and survey of various data-centric storage and querying techniques for sensor networks, and identify the kinds of questions that modeling these techniques can help answer.

We then present four concrete case studies demonstrating the modeling of querying protocols. The first two pertain to unstructured querying. We first examine optimal content replication for expanding ring-based queries. We then examine how random-walk based queries can be enhanced significantly in heterogeneous networks. The third case study pertains to a comparison of two hybrid push-pull mechanisms for structured querying --- hash-based data-centric storage and the combs-and-needles approach --- with and without aggregation, for ALL and ANY query types. Finally, we present an interesting analysis that reveals fundamental scaling laws for both unstructured and structured querying mechanisms. This analysis shows that there are limiting query and event growth conditions beyond which data-centric storage and querying cannot be sustained in arbitrarily large sensor networks.

Audience: The tutorial is aimed at researchers in academia and industry that are interested in developing first-order mathematical modeling skills to complement protocol design, simulation, and experimental implementation efforts. Advanced high school or first-year undergraduate mathematics will suffice to understand the mathematical content of this tutorial, as all topics will be treated in a self-contained manner. In particular, it should be
accessible to all graduate students in computer science and electrical engineering.

<< Back to Program