Phase transition phenomena in wireless ad hoc networks

Abstract

There are many contexts in distributed wireless networks where there is a critical threshold, corresponding to a minimum amount of the communication effort or power expenditure by individ- ual nodes, above which a desirable global property exists with high probability. When this individual node effort is below this threshold the desired global property exists with a low probabil- ity. This "phase transition" is typically seen to become sharper as the number of nodes in the network increases. We discuss in this paper some examples of such critical behav- ior that arise when considering node reachability in probabilis- tic flooding and fixed transmission range connectivity in ad-hoc networks, as well as coordination tasks in sensor networks. We discuss the connections between these phenomena and the phase transitions that have been shown to arise in random graphs. We argue that a good understanding of these phase transition phe- nomena can provide useful design principles for engineering dis- tributed wireless networks.