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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Composition and Scaling Challenges in Sensor Networks: An Interaction-Centric View Kapitel lesen Erstes Kapitel lesen

2011 | OriginalPaper | Buchkapitel

6. Theoretical Aspects of Graph Models for MANETs

verfasst von : Josep Díaz, Dieter Mitsche, Paolo Santi

Erschienen in: Theoretical Aspects of Distributed Computing in Sensor Networks

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We survey the main theoretical aspects of models for mobile ad hoc networks (MANETs). We present theoretical characterizations of mobile network structural properties, different dynamic graph models of MANETs, and finally we give detailed summaries of a few selected articles. In particular, we focus on articles dealing with connectivity of mobile networks and on articles which show that mobility can be used to propagate information between nodes of the network while at the same time maintaining small transmission distances and thus saving energy.

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
Vorheriges Kapitel Population Protocols and Related Models
Nächstes Kapitel Networked Distributed Source Coding
Fußnoten
1
Note that a usual graph with n vertices is said to be dense if it has \(\varTheta(n^2)\) edges.
 
2
Note that the fact that the expected pause time at waypoints tends to infinity implies that nodes are asymptotically static, i.e., RWP model under this condition degenerates to a static network.
 
3
Values of \(f_{{\mathrm{RWP}},0}\) in the other regions of the unit square are obtained by symmetry.
 
Literatur
1.
V. Anand A. Bharathidasas. Sensor Networks: An Overview. Technical Report, Department of Computer Science, University of California at Davis, 2002.
2.
C. Avin and G. Ercal. On the cover time and mixing time of random geometric graphs. Theoretical Computer Science, 380(1-2):2–22, 2007.MATHCrossRefMathSciNet
3.
P. K. Agarwal, L. J. Guibas, H. Edelsbrunner, J. Erickson, M. Isard, S. Har-Peled, J. Hershberger, C. Jensen, L. Kavraki, P. Koehl, M. Lin, D. Manocha, D. Metaxas, B. Mirtich, D. Mount, S. Muthukrishnan, D. Pai, E. Sacks, J. Snoeyink, S. Suri, and O. Wolefson. Algorithmic issues in modeling motion. ACM Computing Surveys, 34(4):550–572, 2002.CrossRef
4.
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless sensor networks: a survey. Computer Networks, 38:393–422, 2002.CrossRef
5.
A. Boukerche and L. Bononi. Simulation and modeling of wireless, mobile, and ad hoc networks. In S. Basagni, M. Conti, S. Giordano, and I. Stojmenović, editors, Mobile Ad Hoc Networking, chapter 14, pages 373–409. IEEE Press, New York, NY, 2004.
6.
C. Bettstetter. Mobility modeling in wireless networks: categorization, smooth movement, and border effects. Mobile Computing and Communications Review, 5(3):55–66, 2001.CrossRef
7.
C. Bettstetter. Smooth is better than sharp: a random mobility model for simulation of wireless networks. In Proceedings of the 4th ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, pages 19–27, ACM, New York, 2001.
8.
9.
C. Bettstetter, G. Resta, and P. Santi. The node distribution of the random waypoint mobility model for wireless ad hoc networks. IEEE Transactions on Mobile Computing, 2(3):257–269, 2003.CrossRef
10.
T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. Wireless Communications and Mobile Computing, 2(5):483–502, 2002.CrossRef
11.
Y. A. Chau and Y.-H. Chen. Analytical link lifetime of a manet based on the three-dimensional brownian mobility model. In Proceedings of the International Symposium on intelligent Signal Processing and Communication Systems, (ISPACS), pages 428–431, IEEE Computer Society, Los Alamitos, CA, 2007.
12.
13.
A. E. F. Clementi, F. Pasquale, and R. Silvestri. Manets: High mobility can make up for low transmission power. In S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. E. Nikoletseas, and W. Thomas, editors, Proceedings of 36th International Collogquium on Automata, Languages and Programming, pages 387–398, 2009.
14.
C. de Morais Cordero and D. P. Agrawal. Ad Hoc and Sensor Networks. World Scientific, New Jersey, 2006.
15.
J. Díaz, D. Mitsche, and X. Pérez. Connectivity for dynamic random geometric graphs. IEEE Transactions on Mobile Computing, 8:821–835, 2009.CrossRef
16.
J. Díaz, D. Mitsche, and X. Pérez. On the probability of existence of mid-size components in random geometric graphs. Advances of Applied Probability, 41:1–14, 2009.CrossRef
17.
J. Díaz, J. Petit, and M. J. Serna. A random graph model for optical networks of sensors. IEEE Transactions on Mobile Computing, 2:143–154, 2003.CrossRef
18.
J. Díaz, X. Pérez, M. J. Serna, and N. Wormald. On the walkers problem. SIAM Journal of Discrete Mathematics, 22:747–775, 2008.MATHCrossRef
19.
S. Dolev, E. Schiller, and J. L. Welch. Random walk for self-stabilizing group communication in ad hoc networks. IEEE Trans. Mobile Computing, 5(7):893–905, 2006.CrossRef
20.
L. J. Guibas, J. Hershberger, S. Suri, and L. Zhang. Kinetic connectivity for unit disks. Discrete & Computational Geometry, 25:591–610, 2001.MATHMathSciNet
21.
E. N. Gilbert. Random plane networks. Journal of the Society for Industrial and Applied Mathematics, 9:533–543, 1961.MATHCrossRef
22.
P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. In W. McEneaney, G. G. Yin, and Q. Zhang, editors, Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, pages 547–566. Birkhäuser, 1998.
23.
24.
M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, NY, 1980.MATH
25.
A. Goel, S. Rai, and B. Krishnamachari. Sharp thresholds for monotone properties in random geometric graphs. Annals of Applied Probability, 15:364–370, 2005.MathSciNet
26.
G. Grimmett and D. Stirzaker. Probability and Random Processes. Oxford University Press, 2001.
27.
M. Grossglauser and D. N. C. Tse. Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Transactions on Networking, 10(4):477–486, 2002.CrossRef
28.
R. A. Guerin. Channel occupancy time distribution in a cellular radio system. IEEE Transactions on Vehicular Technology, 36(3):89–99, 1987.CrossRef
29.
S. Guo and O. W. W. Yang. Energy-aware multicasting in wireless ad hoc networks: A survey and discussion. Computer Communications, 30:2129–2148, 2007.CrossRef
30.
P. G. Hall. Introduction to the Theory of Coverage Processes. Wiley, New York, NY, 1988.MATH
31.
R. Hekmat. Ad-hoc Networks: Fundamental Properties and Network Topologies. Springer, Heidelberg, 2006.
32.
X. Hong, M. Gerla, G. Pei, and C.-C. Chiang. A group mobility model for ad hoc wireless networks. In Proceedings of the 2nd ACM international workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM), pages 53–60, ACM, New York, NY, 1999.
33.
E. Hyytiä, P. Lassila, and J. Virtamo. Spatial node distribution of the random waypoint mobility model with applications. IEEE Transactions on Mobile Computing, 5(6):680–694, 2006.CrossRef
34.
M. Hollick, I. Martinovic, T. Krop, and I. Rimac. A survey on dependable routing in sensor networks, ad hoc networks, and cellular networks. In EUROMICRO Conference, pages 495–502, Los Alamitos, CA, 2004. IEEE Computer Society.
35.
Z. J. Haas and M. R. Pearlman. The performance of query control schemes for the zone routing protocol. IEEE/ACM Transactions on Networking, 9(4):427–438, 2001.CrossRef
36.
A. P. Jardosh, E. M. Belding-Royer, K. C. Almeroth, and S. Suri. Real-world environment models for mobile network evaluation. IEEE Journal on Selected Areas in Communications, 23(3):622–632, 2005.CrossRef
37.
D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, pages 153–181. Kluwer Academic Publishers, 1996.
38.
P. Jacquet, B. Mans, and G. Rodolakis. Information propagation speed in mobile and delay tolerant networks. In Proceeding of the 29th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Los Alamitos, CA, 2009. IEEE Computer Society.
39.
L. M. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc. Power consumption in packet radio networks. Theoretical Computer Science, 243(1-2):289–305, 2000.MATHCrossRefMathSciNet
40.
S. Kumar, T.-H. Lai, and J. Balogh. On k-coverage in a mostly sleeping sensor network. Wireless Networks, 14:277–294, 2008.CrossRef
41.
W. Kieß and M. Mauve. A survey on real-world implementations of mobile ad-hoc networks. Ad Hoc Networks, 5:324–339, 2007.CrossRef
42.
X.-Y. Li. Topology control in wireless ad hoc networks. In S. Basagni, M. Conti, S. Giordano, and I. Stojmenović, editors, Mobile Ad Hoc Networking, chapter 6, pages 175–204. IEEE Press, New York, NY, 2004.
43.
J.-Y. LeBoudec and M. Vojnović. The random trip model: Stability, stationary regime, and perfect simulation. IEEE/ACM Transactions on Networking, 14:1153–1166, 2006.CrossRef
44.
S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In Proceeding of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 1380–1387, 2001.
45.
46.
47.
48.
J. Pitman. Probability. Springer, New York, NY, 1999.
49.
R. Rajaraman. Topology control and routing in ad hoc networks: A survey. SIGACT News, 33:60–73, 2002.CrossRef
50.
E. M. Royer and C-K. Toh. A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Personal Communications, 7:46–55, 1999.CrossRef
51.
P. Santi. The critical transmitting range for connectivity in mobile ad hoc networks. IEEE Transactions Mobile Computing, 4(3):310–317, 2005.CrossRef
52.
P. Santi. Topology control in wireless ad hoc and sensor networks. ACM Computing Surveys, 37:164–194, 2005.CrossRef
53.
P. Santi and D. M. Blough. The critical transmitting range for connectivity in sparse wireless ad hoc networks. IEEE Transactions on Mobile Computing, 2(1):25–39, 2003.CrossRef
54.
P. Santi, D. M. Blough, and F. S. Vainstein. A probabilistic analysis for the range assignment problem in ad hoc networks. In Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing, (MobiHoc), pages 212–220, 2001.
55.
A. Sen and M. L. Huson. A new model for scheduling packet radio networks. In Proceedings of the 15th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), IEEE Computer Society, Los Alamitos, CA, 1997.
56.
S. Schmid and R. Wattenhofer. Algorithmic models for sensor networks. In Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS), IEEE Computer Society, Los Alamitos, CA, 2006.
57.
S. Tilak, N. B. Abu-Ghazaleh, and W. Heinzelman. A taxonomy of sensor network communication models. Mobile Computing and Communication Review, 6:28–36, 2002.CrossRef
58.
J. Tian, J. Hahner, C. Becker, I. Stepanov, and K. Rothermel. Graph-based mobility model for mobile ad hoc network simulation. In Proceedings. 35th Annual Simulation Symposium, IEEE Computer Society, Los Alamitos, CA, 2002.
59.
E. J. van Leeuwen. Optimization and Approximation on Systems of Geometric Objects. PhD thesis, Universiteit van Amsterdam, 2009.
60.
W. Wang, V. Srinivasan, and K.-C. Chua. Trade-offs between mobility and density for coverage in wireless sensor networks. In Proceedings of the 13th annual ACM international conference on Mobile computing and networking (MobiCom), pages 39–50, ACM, New York, 2007.
61.
P.-J. Wan and C.-W. Yi. Asymptotic critical transmission radius and critical neighbor number for -connectivity in wireless ad hoc networks. In J. Murai, C. E. Perkins, and L. Tassiulas, editors, Proceedings of the 5th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, pages 1–8. ACM, New York, NY, 2004.CrossRef
62.
P.-J. Wan and C.-W. Yi. Coverage by randomly deployed wireless sensor networks. IEEE Transaction on Information Theory, 52(6):2658–2669, 2006.CrossRefMathSciNet
63.
X.Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill. Integrated coverage and connectivity configuration in wireless sensor networks. In Proceedings of ACM SenSys, pages 28–39, 2003.
64.
J. Yoon, M. Liu, and B. Noble. Random waypoint considered harmful. In Proceeding of he 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), IEEE Computer Society, Los Alamitos, CA, 2003.
65.
J. Yoon, M. Liu, and B. Noble. Sound mobility models. In D. B. Johnson, A. D. Joseph, and N. H. Vaidya, editors, Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking (MOBICOM), pages 205–216. ACM, New York, NY, 2003.
66.
J. Yick, B. Mukherjee, and D. Ghosal. Wireless sensor network survey. Computer Networks, 52:2292–2330, 2008.CrossRef
67.
F. Zhao and L. Guibas, editors. Distributed Environmental Monitoring Using Random Sensor Networks, vol. 2634, Lecture Notes in Computer Science. Springer, 2003.
68.
H. Zang and J. Hou. On deriving the upper bound of alpha-lifetime for large sensor networks. In J. Murai, C. E. Perkins, and L. Tassiulas, editors, Proceedings of the 5th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, pages 16–24. ACM, New York, NY, 2004.
69.
Z. Zhang. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges. IEEE Communications Surveys and Tutorials, 8(1-4):24–37, 2006.CrossRef
Metadaten
Titel
Theoretical Aspects of Graph Models for MANETs
verfasst von
Josep Díaz
Dieter Mitsche
Paolo Santi
Copyright-Jahr
2011
Verlag
Springer Berlin Heidelberg
Buch
Theoretical Aspects of Distributed Computing in Sensor Networks

Print ISBN: 978-3-642-14848-4

Electronic ISBN: 978-3-642-14849-1

Copyright-Jahr: 2011

DOI
https://doi.org/10.1007/978-3-642-14849-1_6

Premium Partner

    Bildnachweise