Abstract
In the light of energy conservation and the expansion of existing networks, wireless networks face the challenge of nodes with heterogeneous transmission power. However, for more realistic models of wireless communication only few algorithmic results are known. In this paper we consider nodes with arbitrary, possibly variable, transmission power in the so-called physical or SINR model. Our first result is a bound on the probabilistic interference from all simultaneously transmitting nodes on receivers. This result implies that current local broadcasting algorithms can be generalized to the case of non-uniform transmission power with minor changes. The algorithms run in \({\mathcal{O}}(\Gamma^{2} \Delta \log n)\) time slots if the maximal degree Δ is known, and \({\mathcal{O}}((\Delta + \log n)\Gamma^{2} \log n)\) otherwise, where Γ is the ratio between the maximal and the minimal transmission range. The broad applicability of our result on bounding the interference is further highlighted, by generalizing a distributed coloring algorithm to this setting.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Daum, S., Gilbert, S., Kuhn, F., Newport, C.: Broadcast in the ad hoc SINR model. In: Afek, Y. (ed.) DISC 2013. LNCS, vol. 8205, pp. 358–372. Springer, Heidelberg (2013), http://dx.doi.org/10.1007/978-3-642-41527-2_25
Derbel, B., Talbi, E.G.: Distributed Node Coloring in the SINR Model. In: Proc. 30th Internat. Conf. on Distributed Computing Systems (ICDCS 2010), pp. 708–717. IEEE Computer Society (2010)
Fuchs, F., Wagner, D.: On Local Broadcasting Schedules and CONGEST Algorithms in the SINR Model. In: Flocchini, P., Gao, J., Kranakis, E., Meyer auf der Heide, F. (eds.) ALGOSENSORS 2013. LNCS, vol. 8243, pp. 170–184. Springer, Heidelberg (2014)
Fuchs, F., Wagner, D.: Arbitrary transmission power in the SINR model: Local broadcasting, coloring and mis. CoRR abs/1402.4994 (2014)
Fujii, T., Takahashi, T., Bandai, T., Udagawa, T., Sasase, T.: An efficient MAC protocol in wireless ad-hoc networks with heterogeneous power nodes. In: 5th Internat. Symp. Wireless Personal Multimedia Communications (WPMC 2002), vol. 2, pp. 776–780. IEEE (2002)
Goussevskaia, O., Moscibroda, T., Wattenhofer, R.: Local Broadcasting in the Physical Interference Model. In: Proc. 5th ACM Internat. Workshop on Foundations of Mobile Computing (DialM-POMC 2008), pp. 35–44. ACM Press (2008)
Halldórsson, M.M., Mitra, P.: Towards Tight Bounds for Local Broadcasting. In: Proc. 8th ACM Internat. Workshop on Foundations of Mobile Computing (FOMC 2012). ACM Press (July 2012)
Halldórsson, M.M., Mitra, P.: Wireless connectivity and capacity. In: Proc. 23rd Ann. ACM-SIAM Symp. Discrete Algorithms (SODA 2012), pp. 516–526. SIAM (2012), http://dl.acm.org/citation.cfm?id=2095116.2095160
Jurdziński, T., Stachowiak, G.: Probabilistic algorithms for the wakeup problem in single-hop radio networks. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 535–549. Springer, Heidelberg (2002)
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), http://dl.acm.org/citation.cfm?id=1888781.1888803
Moscibroda, T., Wattenhofer, M.: Coloring Unstructured Radio Networks. J. Distr. Comp. 21(4), 271–284 (2008)
Moscibroda, T., Wattenhofer, R.: Coloring unstructured radio networks. In: Proc 17th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA 2005), pp. 39–48. ACM (2005)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial Mathematics (2000)
Poojary, N., Krishnamurthy, S.V., Dao, S.: Medium access control in a network of ad hoc mobile nodes with heterogeneous power capabilities. In: IEEE Internat. Conf. on Communications (ICC 2001), vol. 3, pp. 872–877. IEEE (2001)
Wang, G., Turgut, D., Bölöni, L., Ji, Y., Marinescu, D.C.: A MAC layer protocol for wireless networks with asymmetric links. Ad Hoc Networks 6(3), 424–440 (2008)
Yu, D., Hua, Q.S., Wang, Y., Lau, F.C.M.: An O(log n) Distributed Approximation Algorithm for Local Broadcasting in Unstructured Wireless Networks. In: Proc. 8th Internat. Conf. on Distributed Computing in Sensor Systems (DCOSS 2012), pp. 132–139. IEEE Computer Society (2012)
Yu, D., Wang, Y., Hua, Q.-S., Lau, F.C.M.: Distributed (Δ + 1)-Coloring in the Physical Model. In: Erlebach, T., Nikoletseas, S., Orponen, P. (eds.) ALGOSENSORS 2011. LNCS, vol. 7111, pp. 145–160. Springer, Heidelberg (2012)
Yu, D., Wang, Y., Hua, Q.S., Lau, F.C.M.: Distributed Local Broadcasting Algorithms in the Physical Interference Model. In: Proc. 7th Internat. Conf. on Distributed Computing in Sensor Systems (DCOSS 2011), pp. 1–8. IEEE Computer Society (2011)
Zuhairi, M., Zafar, H., Harle, D.: On-demand routing with unidirectional link using path loss estimation technique. In: Proc. Wireless Telecommunications Symposium (WTS 2012), pp. 1–7 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Fuchs, F., Wagner, D. (2014). Local Broadcasting with Arbitrary Transmission Power in the SINR Model. In: Halldórsson, M.M. (eds) Structural Information and Communication Complexity. SIROCCO 2014. Lecture Notes in Computer Science, vol 8576. Springer, Cham. https://doi.org/10.1007/978-3-319-09620-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-09620-9_15
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09619-3
Online ISBN: 978-3-319-09620-9
eBook Packages: Computer ScienceComputer Science (R0)