Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks

详细信息    查看全文

• 作者：Tomasz Jurdzinski (1)
  Dariusz R. Kowalski (2)
• 关键词：Wireless networks &#8211 ; SINR &#8211 ; Backbone structure &#8211 ; Distributed algorithms &#8211 ; Leader Election &#8211 ; Multi ; message broadcast
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7611
• 期：1
• 页码：106-120
• 全文大小：253.2 KB
• 参考文献：1. Avin, C., Lotker, Z., Pasquale, F., Pignolet, Y.-A.: A Note on Uniform Power Connectivity in the SINR Model. In: Dolev, S. (ed.) ALGOSENSORS 2009. LNCS, vol. 5804, pp. 116–127. Springer, Heidelberg (2009)
  2. Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. J. Comput. Syst. Sci. 45(1), 104–126 (1992)
  3. Censor-Hillel, K., Gilbert, S., Kuhn, F., Lynch, N.A., Newport, C.C.: Structuring unreliable radio networks. In: PODC, pp. 79–88. ACM (2011)
  4. Chung, H.C., Robinson, P., Welch, J.L.: Optimal regional consecutive leader election in mobile ad-hoc networks. In: FOMC, pp. 52–61. ACM (2011)
  5. Cidon, I., Kutten, S., Mansour, Y., Peleg, D.: Greedy packet scheduling. SIAM J. Comput. 24(1), 148–157 (1995)
  6. Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. In: FOCS, pp. 492–501. IEEE Computer Society (2003)
  7. DeMarco, G.: Distributed broadcast in unknown radio networks. SIAM J. Comput. 39(6), 2162–2175 (2010)
  8. Dessmark, A., Pelc, A.: Broadcasting in geometric radio networks. J. Discrete Algorithms 5(1), 187–201 (2007)
  9. Emek, Y., Gasieniec, L., Kantor, E., Pelc, A., Peleg, D., Su, C.: Broadcasting in udg radio networks with unknown topology. Distributed Computing 21(5), 331–351 (2009)
  10. Fangh盲nel, A., Kesselheim, T., R盲cke, H., V枚cking, B.: Oblivious interference scheduling. In: PODC, pp. 220–229. ACM (2009)
  11. Galc铆k, F., Gasieniec, L., Lingas, A.: Efficient broadcasting in known topology radio networks with long-range interference. In: PODC, pp. 230–239. ACM (2009)
  12. Goussevskaia, O., Moscibroda, T., Wattenhofer, R.: Local broadcasting in the physical interference model. In: DIALM-POMC, pp. 35–44. ACM (2008)
  13. Goussevskaia, O., Pignolet, Y.A., Wattenhofer, R.: Efficiency of wireless networks: Approximation algorithms for the physical interference model. Foundations and Trends in Networking 4(3), 313–420 (2010)
  14. Hobbs, N., Wang, Y., Hua, Q.-S., Yu, D., Lau, F.C.M.: Deterministic Distributed Data Aggregation under the SINR Model. In: Agrawal, M., Cooper, S.B., Li, A. (eds.) TAMC 2012. LNCS, vol. 7287, pp. 385–399. Springer, Heidelberg (2012)
  15. Jurdzinski, T., Kowalski, D.: Distributed backbone structure for deterministic algorithms in the sinr model of wireless networks. CoRR abs/1207.0602v2 (2012)
  16. Kesselheim, T.: A constant-factor approximation for wireless capacity maximization with power control in the sinr model. In: SODA, pp. 1549–1559. SIAM (2011)
  17. Kesselheim, T., V枚cking, B.: Distributed Contention Resolution in Wireless Networks. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 163–178. Springer, Heidelberg (2010)
  18. Kowalski, D.R., Pelc, A.: Optimal deterministic broadcasting in known topology radio networks. Distributed Computing 19(3), 185–195 (2007)
  19. Kowalski, D.R., Pelc, A.: Leader Election in Ad Hoc Radio Networks: A Keen Ear Helps. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol. 5556, pp. 521–533. Springer, Heidelberg (2009)
  20. Kuhn, F., Lynch, N.A., Newport, C.C.: The abstract mac layer. Distributed Computing 24(3-4), 187–206 (2011)
  21. Kushilevitz, E., Mansour, Y.: An omega(d log (n/d)) lower bound for broadcast in radio networks. SIAM J. Comput. 27(3), 702–712 (1998)
  22. Richa, A., Scheideler, C., Schmid, S., Zhang, J.: Towards jamming-resistant and competitive medium access in the sinr model. In: S3 2011, pp. 33–36. ACM (2011)
  23. Scheideler, C., Richa, A.W., Santi, P.: An o(log n) dominating set protocol for wireless ad-hoc networks under the physical interference model. In: MobiHoc, pp. 91–100. ACM (2008)
  24. Yu, D., Hua, Q.-S., Wang, Y., Tan, H., Lau, F.C.M.: Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model. In: Even, G., Halld贸rsson, M.M. (eds.) SIROCCO 2012. LNCS, vol. 7355, pp. 111–122. Springer, Heidelberg (2012)
  25. Yu, D., Wang, Y., Hua, Q.S., Lau, F.C.M.: Distributed local broadcasting algorithms in the physical interference model. In: DCOSS, pp. 1–8. IEEE (2011)
• 作者单位：1. Institute of Computer Science, University of Wroc艂aw, Poland2. Department of Computer Science, University of Liverpool, United Kingdom
• ISSN：1611-3349

文摘

The Signal-to-Interference-and-Noise-Ratio (SINR) physical model is one of the most popular models of wireless networks. Despite of the vast amount of study done in design and analysis of centralized algorithms supporting wireless communication under the SINR physical model, little is known about distributed algorithms in this model, especially deterministic ones. In this work we construct, in a deterministic distributed way, a backbone structure on the top of a given wireless network, which can be used for efficient transformation of many algorithms designed in a simpler model of ad hoc broadcast networks without interference into the SINR physical model with uniform power of stations. The time cost of the backbone data structure construction is only O(D\text polylog N)O(\Delta \text{ \!polylog\! } N) rounds, where Δ is roughly the network density and {1,…,N} is the range of identifiers (IDs) and thus N is an upper bound on the number of nodes in the whole network. The core of the construction is a novel combinatorial structure called SINR-selector, which is introduced in this paper. We demonstrate the power of the backbone data structure by using it for obtaining efficient O(D+D\text polylog N)O(D+\Delta \text{ \!polylog\! } N) round and O(D+k+D\text polylog N)O(D+k+\Delta \text{ \!polylog\! } N) round deterministic distributed solutions for leader election and multi-broadcast, respectively, where D is the network diameter and k is the number of messages to be disseminated.