Top

Published in:

2020 | OriginalPaper | Chapter

Minimizing Total Interference in Asymmetric Sensor Networks

Authors : A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz

Published in: Algorithms for Sensor Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The problem of computing a connected network with minimum interference is a fundamental problem in wireless sensor networks. Several models of interference have been studied in the literature. The most common model is the receiver-centric, in which the interference of a node p is defined as the number of other nodes whose transmission range covers p. In this paper, we study the problem of assigning a transmission range to each sensor, such that the resulting network is strongly connected and the total interference of the network is minimized.

For the one-dimensional case, we show how to solve the problem optimally in \(O(n^3)\) time. For the two-dimensional case, we show that the problem is NP-complete and give a polynomial-time 2-approximation algorithm for the problem.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter Distributed Localization of Wireless Sensor Network Using Communication Wheel

Agrawal, P., Das, G.K.: Improved interference in wireless sensor networks. In: Hota, C., Srimani, P.K. (eds.) ICDCIT 2013. LNCS, vol. 7753, pp. 92–102. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36071-8_6CrossRef

Bilò, D., Proietti, G.: On the complexity of minimizing interference in ad-hoc and sensor networks. Theor. Comput. Sci. 402(1), 43–55 (2008)MathSciNetCrossRef

Brise, Y., Buchin, K., Eversmann, D., Hoffmann, M., Mulzer, W.: Interference minimization in asymmetric sensor networks. In: Gao, J., Efrat, A., Fekete, S.P., Zhang, Y. (eds.) ALGOSENSORS 2014. LNCS, vol. 8847, pp. 136–151. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46018-4_9CrossRef

Buchin, K.: Minimizing the maximum interference is hard. CoRR, abs/0802.2134 (2008)

Burkhart, M., von Rickenbach, P., Wattenhofer, R., Zollinger, A.: Does topology control reduce interference? In: MOBIHOC, pp. 9–19 (2004)

Edmonds, J.: Optimum branchings. J. Res. Nat. Bur. Stand. 71B(4), 233–240 (1967)MathSciNetCrossRef

Estrin, D., Govindan, R., Heidemann, J., Kumar, S.: Next century challenges: scalable coordination in sensor networks. In: MOBICOM, pp. 263–270 (1999)

Fussen, M., Wattenhofer, R., Zollinger, A.: Interference arises at the receiver. In: WirelessComBur (2005)

Halldórsson, M., Tokuyama, T.: Minimizing interference of a wireless ad-hoc network in a plane. Theor. Comput. Sci. 402(1), 29–42 (2008)MathSciNetCrossRef

10.

Hubaux, J.-P., Gross, T., Boudec, J.-Y.L., Vetterli, M.: Towards self-organized mobile ad-hoc networks: the terminodes project. IEEE Commun. Mag. 39(1), 118–124 (2001)CrossRef

11.

Itai, A., Papadimitriou, C.H., Szwarcfiter, J.L.: Hamilton paths in grid graphs. SIAM J. Comput. 11(4), 676–686 (1982)MathSciNetCrossRef

12.

Lam, N.X., Nguyen, T.N., Huynh, D.T.: Minimum total node interference in wireless sensor networks. In: Zheng, J., Simplot-Ryl, D., Leung, V.C.M. (eds.) ADHOCNETS 2010. LNICST, vol. 49, pp. 507–523. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17994-5_35CrossRefMATH

13.

Moaveni-nejad, K., Li, X.Y.: Low-interference topology control for wireless ad hoc networks. Ad Hoc Sens. Wirel. Netw. 1, 41–64 (2005)

14.

Moscibroda, T., Wattenhofer, R.: Minimizing interference in ad hoc and sensor networks. In: DIALM-POMC, Cologne, Germany, pp. 24–33 (2005)

15.

Tan, H., Lou, T., Wang, Y., Hua, Q.-S., Lau, F.C.M.: Exact algorithms to minimize interference in wireless sensor networks. Theor. Comput. Sci. 412(50), 6913–6925 (2011)MathSciNetCrossRef

16.

Tarjan, R.E.: Finding optimum branchings. Networks 7(1), 25–35 (1977)MathSciNetCrossRef

17.

von Rickenbach, P., Schmid, S., Wattenhofer, R., Zollinger, A.: A robust interference model for wireless ad-hoc networks. In: IPDPS (2005)

18.

von Rickenbach, P., Wattenhofer, R., Zollinger, A.: Algorithmic models of interference in wireless ad hoc and sensor networks. IEEE/ACM Trans. Netw. 17(1), 172–185 (2009)CrossRef

Title: Minimizing Total Interference in Asymmetric Sensor Networks
Authors: A. Karim Abu-Affash
Paz Carmi
Matthew J. Katz
Publisher: Springer International Publishing
Book: Algorithms for Sensor Systems
Print ISBN: 978-3-030-62400-2

Electronic ISBN: 978-3-030-62401-9

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-62401-9_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner