Abstract
The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard.
SINR diagrams appear to be fundamental to understanding the behavior of wireless networks, and may play a key role in the development of suitable algorithms for such networks, analogous perhaps to the role played by Voronoi diagrams in the study of proximity queries and related issues in computational geometry. So far, however, the properties of SINR diagrams have not been studied systematically, and most algorithmic studies in wireless networking rely on simplified graph-based models such as the unit disk graph (UDG) model, which conveniently abstract away interference-related complications, and make it easier to handle algorithmic issues, but consequently fail to capture accurately some important aspects of wireless networks.
This article focuses on obtaining some basic understanding of SINR diagrams, their properties and their usability in algorithmic applications. Specifically, we have shown that assuming uniform power transmissions, the reception zones are convex and relatively well-rounded. These results are then used to develop an efficient approximation algorithm for a fundamental point location problem in wireless networks.
- Agarwal, P. and Erickson, J. 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry. American Mathematical Society, 1--56.Google Scholar
- Aggarwal, A., Hansen, M., and Leighton, T. 1990. Solving query-retrieval problems by compacting voronoi diagrams. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing. ACM, 331--340. Google ScholarDigital Library
- Andrews, M. and Dinitz, M. 2009. Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory. In Proceedings of the 28th Conference. of IEEE Computer and Communications Societies (INFOCOM).Google Scholar
- Avin, C., Lotker, Z., and Pignolet, Y. 2009. On the power of uniform power: Capacity of wireless networks with bounded resources. In Proceedings of the 17th Annual Europe Symposium on Algorithms (ESA 2009). 373--384.Google Scholar
- Bertsekas, D. 1999. Nonlinear programming. Athena Scientific.Google Scholar
- Black, U. 1996. Mobile and Wireless Networks. Prentice Hall. Google ScholarDigital Library
- Chazelle, B., Edelsbrunner, H., Guibas, L., and Sharir, M. 1991. A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theoret. Comput. Sci. 84, 1, 77--105. Google ScholarDigital Library
- Clark, B., Colbourn, C., and Johnson, D. 1990. Unit disk graphs. Disc. math. 86, 1, 165--177. Google ScholarDigital Library
- de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. 2008. Computational Geometry: Algorithms and Applications. Springer-Verlag, New York. Google ScholarCross Ref
- Goussevskaia, O., Oswald, Y., and Wattenhofer, R. 2007. Complexity in geometric SINR. In Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM, 100--109. Google ScholarDigital Library
- Goussevskaia, O., Wattenhofer, R., Halldórsson, M., and Welzl, E. 2009. Capacity of arbitrary wireless networks. In Proceedings of the 28th Conference of IEEE Computer and Communications Societies (INFOCOM). 1872--1880.Google Scholar
- Gupta, P. and Kumar, P. 2000. The capacity of wireless networks. Inf. Theory, IEEE Trans. 46, 2, 388--404. Google ScholarDigital Library
- Halldórsson, M. 2009. Wireless scheduling with power control. In Proceedings of the 17th Annual Europe Symposium on Algorithms (ESA 2009), 361--372.Google ScholarCross Ref
- Halldorsson, M. and Wattenhofer, R. 2009. Wireless communication is in apx. Automat. Lang. Prog., 525--536. Google ScholarDigital Library
- Kuhn, F. and Zollinger, A. 2003. Ad-Hoc Networks Beyond Unit Disk Graphs. In Proceedings of the 2003 Joint Workshop on Foundations of Mobile Computing. ACM, 69--78. Google ScholarDigital Library
- Lotker, Z., Parter, M., Peleg, D., and Pignolet, Y. 2011. Distributed power control in the SINR model. In Proceedings of the 2011 INFOCOM. IEEE, 2525--2533.Google Scholar
- Moscibroda, T. 2007. The worst-case capacity of wireless sensor networks. In Proceedings of the 6th International Conference on Information Processing in Sensor Networks (IPSN). 1--10. Google ScholarDigital Library
- Moscibroda, T. and Wattenhofer, R. 2006. The complexity of connectivity in wireless networks. In Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM 2006). IEEE, 1--13.Google Scholar
- Moscibroda, T., Wattenhofer, R., and Weber, Y. 2006a. Protocol design beyond graph-based models. In Proceedings of the 5th Workshop on Hot Topics in Networks (HOTNETS).Google Scholar
- Moscibroda, T., Wattenhofer, R., and Zollinger, A. 2006b. Topology control meets SINR: The scheduling complexity of arbitrary topologies. In Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). 310--321. Google ScholarDigital Library
- Pahlavan, K. and Levesque, A. 1995. Wireless information networks. Vol. 95. Wiley Online Library. Google ScholarDigital Library
- Rappaport, T. S. 1996. Wireless Communications-Principles and Practice. Prentice-Hall. Google ScholarDigital Library
- Von Rickenbach, P., Schmid, S., Wattenhofer, R., and Zollinger, A. 2005. A robust interference model for wireless ad-hoc networks. In Proceedings 19th IEEE International Parallel and Distributed Processing Symposium. IEEE, 8. Google ScholarDigital Library
Index Terms
- SINR Diagrams: Convexity and Its Applications in Wireless Networks
Recommendations
SINR diagrams: towards algorithmically usable SINR models of wireless networks
PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computingThe rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, ...
Capacity of wireless networks under SINR interference constraints
A fundamental problem in wireless networks is to estimate their throughput capacity--given a set of wireless nodes and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction ...
SEMP: Self-Elimination MAC Protocol for IEEE 802.11 Wireless Networks
IEEE 802.11-based wireless networks are becoming more popular, and a lot of research is done to enhance the performance of the distributed control function (DCF) found in the IEEE 802.11 standard. Many researchers utilized jamming to further enhance the ...
Comments