Critical Density Thresholds and Complexity in Wireless Networks

Bhaskar Krishnamachari
Cornell University

Trends in communication technology and MEMS research point towards a
coming age of intelligent systems that will consist of thousands of
minature devices -- each capable of a combination of computation,
communication, sensing, actuation and motion -- all networked together
wirelessly. These large networks will start to resemble thermodynamic
particle systems where global properties emerge at a critical level of
local interactions.

We will discuss some properties that undergo abrupt "phase
transitions" in large-scale wireless networks. At a
critical density threshold, the probability that the network obtains these
properties changes sharply from nearly zero to nearly one. These
thresholds arise in a number of contexts including k-connectivity, token
ring formation, probabilistic flooding, channel allocation, and target
tracking. By modeling the achievement of some of these properties
as constraint satisfaction problems, we show that the critical
region also corresponds to a peak in average computational
and communication complexity in the network.

We argue that this approach is useful for determining feasible
and resource-efficient operating points in both pre-designed and
self-configuring wireless networks.

Presentation (PowerPoint File)

Back to Massively Distributed Self-Organizing Networks