Wireless Scheduling Algorithms in Complex Environments
Preprint
Abstract
Efficient spectrum use in wireless sensor networks through spatial reuse requires effective models of packet reception at the physical layer in the presence of interference. Despite recent progress in analytic and simulations research into worst-case behavior from interference effects, these efforts generally assume geometric path loss and isotropic transmission, assumptions which have not been borne out in experiments. Our paper aims to provide a methodology for grounding theoretical results into wireless interference in experimental reality. We develop a new framework for wireless algorithms in which distance-based path loss is replaced by an arbitrary gain matrix, typically obtained by measurements of received signal strength (RSS). Gain matrices allow for the modeling of complex environments, e.g., with obstacles and walls. We experimentally evaluate the framework in two indoors testbeds with 20 and 60 motes, and confirm superior predictive performance in packet reception rate for a gain matrix model over a geometric distance-based model. At the heart of our approach is a new parameter $\zeta$ called metricity which indicates how close the gain matrix is to a distance metric, effectively measuring the complexity of the environment. A powerful theoretical feature of this parameter is that all known SINR scheduling algorithms that work in general metric spaces carry over to arbitrary gain matrices and achieve equivalent performance guarantees in terms of $\zeta$ as previously obtained in terms of the path loss constant. Our experiments confirm the sensitivity of $\zeta$ to the nature of the environment. Finally, we show analytically and empirically how multiple channels can be leveraged to improve metricity and thereby performance. We believe our contributions will facilitate experimental validation for recent advances in algorithms for physical wireless interference models.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Nearly optimal bounds for distributed wireless scheduling in the SINR modelDistributed Computing, 2014
- Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods2014
- Wireless capacity and admission control in cognitive radio2012
- Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates2012
- SIR based interference modeling for wireless mesh networks: A detailed measurement study2012
- Accuracy-Aware Interference Modeling and Measurement in Wireless Sensor Networks2011
- On a game theoretic approach to capacity maximization in wireless networks2011
- Distributed Contention Resolution in Wireless NetworksLecture Notes in Computer Science, 2010
- Capacity of Arbitrary Wireless Networks2009
- Wireless Communication Is in APX2009