Phase transitions, structure, and complexity in wireless networks
Stephen B. Wicker, Bhaskar Krishnamachari · 2002
What are the conditions under which tasks can be performed tractably and efficiently in resource-constrained wireless networks? We address this question through several case studies that relate problem structure to computational complexity. We first consider the task of locating mobile users through sequential paging in cellular networks. We show that the problem of minimizing the paging cost under an average delay constraint, previously believed to be NP-complete, is in fact polynomial time solvable because certain properties inherent in the problem make it structured and tractable to dynamic programming. We also derive the conditions under which cluster paging, an even simpler and faster sequential paging technique, results in provably optimal performance. We then examine data-centric routing protocols for wireless sensor networks. We show that, although data aggregation in such protocols is NP-complete in general, there exist polynomial special cases corresponding to particular topological arrangements of data sources where simple heuristic algorithms can achieve optimum energy savings. We also derive useful bounds on the energy costs of such protocols. Finally, we study emergent structure in multi-hop wireless networks. In these distributed wireless networks, many tasks such as multi-path routing, conflict-free channel allocation, Hamiltonian cycle formation, coordinated target tracking, and probabilistic flooding, are characterized by zero-one phase transitions. These tasks can be performed with high probability above a critical resource threshold and with negligible probability below the threshold. This emergent structure can be exploited to simplify problem solving. For some of these tasks that can be formulated as constraint satisfaction problems, we show that the average computational complexity decreases to manageable levels beyond the phase transition threshold, even though the problems are NP-complete. The common theme in all these case studies, which pertain to some of the hardest problems in wireless networks, is the identification of special conditions or emergent structures that help bound the computational complexity. The results serve to demonstrate the usefulness of a computational complexity perspective in analyzing and engineering large-scale wireless networks.