Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Wireless Networks
Erschienen in: Wireless Networks 6/2018

01.02.2017

Census: fast, scalable and robust data aggregation in MANETs

verfasst von: Vinod Kulathumani, Anish Arora, Mukundan Sridharan, Kenneth Parker, Masahiro Nakagawa

Erschienen in: Wireless Networks | Ausgabe 6/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper describes Census, a protocol for data aggregation and statistical counting in MANETs. Census operates by circulating a set of tokens in the network using biased random walks such that each node is visited by at least one token. The protocol is structure-free so as to avoid high messaging overhead for maintaining structure in the presence of node mobility. It biases the random walks of tokens so as to achieve fast cover time; the bias involves short albeit multi-hop gradients that guide the tokens towards hitherto unvisited nodes. Census thus achieves a cover time of O(N) and message overhead of \(O(N\,log(N))\) where N is the number of nodes. Notably, it enjoys scalability and robustness, which we demonstrate via simulations in networks ranging from 100 to 4000 nodes under different network densities and mobility models. We also observe a speedup by a factor of k when k different tokens are used (\(1 \le k \le \sqrt{N}\)).
Vorheriger Artikel Performance analysis of high-traffic cognitive radio communication system using hybrid spectrum access, prediction and monitoring techniques
Nächster Artikel Development of coded-cooperation based multi-relay system for cognitive radio using mathematical modeling and its performance analysis

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Literatur
1.
Alon, N., Avin, C., Koucky, M., Kozma, G., Lotker, Z., & Tuttle, M. R. (2008). Many random walks are faster than one. In Proceedings of the twentieth annual symposium on parallelism in algorithms and architectures (pp. 119–128). SPAA ’08.
2.
Avin, C., & Brito, C. (2004). Efficient and robust query processing in dynamic environments using random walk techniques. In International symposium on information processing in sensor networks (IPSN) (pp. 277–286).
3.
Avin, C., Koucký, M., & Lotker, Z. (2008). How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, & I. Walukiewicz (Eds.), Automata, languages and programming: 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, proceedings, part I (pp. 121–132). Berlin: Springer.
4.
Avin, C., & Krishnamachari, B. (2006). The power of choice in random walks: An empirical study. In Proceedings of the 9th ACM international symposium on modeling analysis and simulation of wireless and mobile systems (pp. 219–228). MSWiM ’06.
5.
Boudec, J. Y. L., & Vojnovic, M. (2005). Perfect simulation and stationarity of a class of mobility models. In IEEE 24th annual joint conference of the IEEE computer and communications societies (INFOCOM) (Vol. 4, pp. 2743–2754).
6.
Boyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006). Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6), 2508–2530.MathSciNetCrossRefMATH
7.
Byrnes, C., & Guttman, A. J. (1984). On self-repelling random walks. Journal of Physics A: Mathematical and General, 17(17), 3335–3342.CrossRef
8.
Camp, T., Boleng, J., & Davies, V. (2002). A survey of mobility models for ad hoc network research. In Wireless communication and mobile computing (WCMC): Special issue on mobile ad-hoc networking (Vol. 2, pp. 483–502).
9.
Chen, Y., Shakkottai, S., & Andrews, J. (2013). On the role of mobility on multi-message gossip. IEEE Transactions on Information Theory, 56(12), 3953–3970.CrossRefMATH
10.
Clementi, A. E. F., Monti, A., Pasquale, F., & Silvestri, R. (2011). Information spreading in stationary Markovian evolving graphs. IEEE Transactions on Parallel and Distributed Systems, 22(9), 1425–1432.CrossRef
11.
Clementi, A. E. F., Pasquale, F., & Silvestri, R. (2009). MANETs: High mobility can make up for low transmission power. In S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. Nikoletseas, & W. Thomas (Eds.), Automata, languages and programming: 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009, proceedings, part II (pp. 387–398). Berlin: Springer.
12.
Cooper, C., Frieze, A., & Radik, T. (2009). Multiple random walks in random regular graphs. SIAM Journal of Discrete Mathematics, 23(4), 1738–1761.MathSciNetCrossRefMATH
13.
DARPA. Clean slate ideas for MANETs. Accessed September 2, 2015.
14.
DARPA. Fixed wireless at a distance. Accessed September 2, 2015. (Online).
15.
DARPA. (2013). Novel methods for information sharing in large scale mobile ad-hoc networks. Request for information: DARPA-SN-13-35.
16.
Doumas, A. V., & Papanicolaou, V. G. (2014). The coupon collector’s problem revisited: Generalizing the double Dixie Cup problem of Newman and Shepp. (ArXiv e-prints).
17.
Ercal, G., & Avin, C. (2005). On the cover time of random geometric graphs. Automata, Languages, and Programming, 3580(1), 677–689.MathSciNetMATH
18.
Feige, U. (1995). A tight lower bound for the cover time of random walks on graphs. Random Structures and Algorithms, 6(4), 433–438.MathSciNetCrossRefMATH
19.
Feige, U. (1995). A tight upper bound on the cover time for random walks on graphs. Random Structures and Algorithms, 6(1), 51–54.MathSciNetCrossRefMATH
20.
Feund, H., & Grassberger, P. (1993). How a random walk covers a finite lattice. Physica A, 192, 465–470.CrossRef
21.
Friedman, R., Gavidia, D., Rodrigues, L., Viana, A., & Voulgaris, S. (2007). Gossiping on MANETs: The beauty and the beast. ACM SIGOPS Operating Systems Review, 41(5), 67–74.CrossRef
22.
Frieze, A., & Cooper, C. (2005). The cover time of random regular graphs. SIAM Journal of Discrete Mathematics, 18(4), 728–740.MathSciNetCrossRefMATH
23.
Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., & Levis, P. (2009). Collection tree protocol. In Proceedings of the 7th ACM conference on embedded networked sensor systems (pp. 1–14). SenSys ’09.
24.
Intanogonwiwat, C., Govindan, R., Estrin, D., Heidemann, J., & Silva, F. (2003). Directed diffusion for wireless sensor networking. IEEE Transactions on Networking, 11(1), 2–16.CrossRef
25.
Jacquet, P., Muhlethaler, P., Clausen, T., Laouiti, A., Qayyum, A., & Viennot, L. (2001). Optimized link state routing protocol for ad hoc networks. In IEEE international multi-topic conference (INMIC) (pp 62–68).
26.
Joint Tactical Radio System. (2015). Jtrs—Wikipedia, the free encyclopedia. Accessed September 2, 2015. (Online).
27.
Kulathumani, V., Arora, A., Sridharan, M., Parker, K., & Lemon, B. (2016). On the repair time scaling wall for MANETs. IEEE Communications Letters, 20(8), 1623–1626.CrossRef
28.
Kulathumani, V., Parker, K., Sridharan, M., & Arora, A. (2014). Census: Fast, scalable and robust data aggregation in MANETs. CoRR, abs/1409.7368.
29.
Kulathumani, V., Sridharan, M., Arora, A., Lemon, B., & Parker, K. (2014). On the repair time scaling wall for MANETs. CoRR, abs/1409.7370.
30.
Levis, P., Patel, N., Shenker, S., & Culler, D. (2004). Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks. In USENIX/ACM symposium on networked systems design and implementation (NSDI) (pp. 15–28).
31.
Lovascz, L. (1993). Random walks on graphs: A survey. Combinatorics, Paul Erdos, 80.
32.
Madden, S., Franklin, M. J., Hellerstein, J. M., & Hong, W. (2002). Tag: A tiny aggregation service for ad-hoc sensor networks. ACM SIGOPS Operating Systems Review, 36(SI), 131–146.CrossRef
33.
Naik, V., Arora, A., Sinha, P., & Zhang, H. (2007). Sprinkler: A reliable and energy efficient data dissemination service for extreme scale wireless networks of embedded devices. IEEE Transactions on Mobile Computing, 6(7), 777–789.CrossRef
34.
Nain, P., Towsley, D., Liu, B., & Liu, Z. (2005). Properties of random direction models. In IEEE 24th annual joint conference of the IEEE computer and communications societies (INFOCOM) (Vol. 3, pp. 1897–1907).
35.
36.
Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007). Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE, 95(1), 215–233.CrossRefMATH
37.
38.
Pettarin, A., Pietracaprina, A., Pucci, G., & Upfal, E. (2011). Tight bounds on information dissemination in sparse mobile networks. In 30th annual ACM SIGACT-SIGOPS symposium on principles of distributed computing (pp. 355–362). PODC ’11.
39.
Rabbat, M. G. (2007). On spatial gossip algorithms for average consensus. In 2007 IEEE/SP 14th workshop on statistical signal processing (pp. 705–709).
40.
Sarwate, A. D., & Javidi, T. (2011). Opinion dynamics and distributed learning of distributions. In 2011 49th annual Allerton conference on communication, control, and computing (Allerton) (pp. 1151–1158).
41.
The ns-3 network simulator. Accessed June 2, 2016. (Online).
42.
Zeng, W., Arora, A., & Srinivasan, K. (2013). Low power counting via collaborative wireless communications. In Proceedings of the 12th international conference on information processing in sensor networks (pp. 43–54). IPSN ’13.
Metadaten
Titel
Census: fast, scalable and robust data aggregation in MANETs
verfasst von
Vinod Kulathumani
Anish Arora
Mukundan Sridharan
Kenneth Parker
Masahiro Nakagawa
Publikationsdatum
01.02.2017
Verlag
Springer US
Erschienen in
Wireless Networks / Ausgabe 6/2018
Print ISSN: 1022-0038
Elektronische ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-017-1452-y

Weitere Artikel der Ausgabe 6/2018

Wireless Networks 6/2018 Zur Ausgabe

OriginalPaper

A reliable relay selection scheme for SSK modulation in cooperative communication systems

OriginalPaper

D2D-based Survival on Sharing for critical communications

OriginalPaper

Novel Markov channel predictors for interference alignment in cognitive radio network

OriginalPaper

A reliable energy-efficient pressure-based routing protocol for underwater wireless sensor network

OriginalPaper

Novel sensing and joint beam and null steering based resource allocation for cross-tier interference mitigation in cognitive femtocell networks

OriginalPaper

Performance analysis of high-traffic cognitive radio communication system using hybrid spectrum access, prediction and monitoring techniques

Neuer Inhalt

    Bildnachweise