|
Position-Based Multicast for Mobile Ad-hoc Networks
Transier, Matthias
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)  Vorschau |
|
PDF
Transier2008_PositionBasedMulticast.pdf
- Veröffentlichte Version
Download (2MB)
|
|
URL:
|
http://ub-madoc.bib.uni-mannheim.de/2020
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-20209
|
|
Dokumenttyp:
|
Dissertation
|
|
Erscheinungsjahr:
|
2008
|
|
Titel einer Zeitschrift oder einer Reihe:
|
None
|
|
Verlag:
|
Universität Mannheim
|
|
Gutachter:
|
Effelsberg, Wolfgang
|
|
Datum der mündl. Prüfung:
|
3 Juli 2008
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Praktische Informatik IV (Effelsberg 1989-2017)
|
|
Fachgebiet:
|
004 Informatik
|
|
Fachklassifikation:
|
CCS:
C.2.1 Wire C.2.2 Rout ,
|
|
Normierte Schlagwörter (SWD):
|
Multicastingverfahren , Ad-hoc-Netz , Routing , Mobile Telekommunikation
|
|
Freie Schlagwörter (Englisch):
|
Mobile Ad-hoc Networks , Multicast , Routing , Congestion Control
|
|
Abstract:
|
In general, routing protocols for mobile ad-hoc networks (MANETs) can be classified into topology-based protocols and position-based protocols. While for unicast routing many proposals for both classes exist, the existing approaches to multicast routing basically implement topology-based algorithms and only a few of them make use of the geographic positions of the network nodes. These have in common that the sending node has to precalculate the multicast tree over which the packets are distributed and store it in each packet header. This involves two main issues: (a) These approaches are not very flexible with regard to topological changes which abandons the advantages that position-based routing has against topology-based routing, and (b) they do not scale with the number of receivers, since every one of them has to be named in the packet header. This thesis solves these issues and further advances position-based multicast routing. Position-Based Multicast (PBM) enhances the flexibility of position-based multicast routing by following the forwarding principle of position-based unicast routing. It transfers the choice of the next hops in the tree from the sender to the forwarding nodes. Based on the positions of their neighboring nodes, these are able to determine the most suitable next hop(s) at the moment when the packet is being forwarded. The scalability with respect to the number of receiving nodes in a group is solved by Scalable Position-Based Multicast (SPBM). It includes a membership management fulfilling different tasks at once. First, it administers group memberships in order to provide multicast sources with information on whether nodes are subscribed to a specific group. Second, it implements a location service providing the multicast sources with the positions of the subscribed receiver nodes. And third, it geographically aggregates membership data in order to achieve the desired scalability. The group management features two modes of operation: The proactive variant produces a bounded overhead scaling well with the size of the network. The reactive alternative, in contrast, reaches low worst-case join delays but does not limit the overhead. Contention-Based Multicast Forwarding (CBMF) addresses the problems that appear in highly mobile networks induced by outdated position information. Instead of basing forwarding decisions on a perception that may no longer be up to date, the packets are addressed only to the final destination; no explicit next hops are specified. The receiving nodes, which are candidate next hops, then decide by means of contention which of them are the most suitable next hop(s) for a packet. Not only is the decision made based on the most currently available data, but this procedure also saves the regular sending of beacon messages, thus reducing the overhead. The lack of multicast congestion control is another unsolved problem obstructing high-bandwidth data transmission. Sending out more and more packets to a multicast group lets the performance decrease. Backpressure Multicast Congestion Control (BMCC) takes care that the network does not need to handle more packets than it is able to. It achieves this by limiting the packet queues on the intermediate hops. A forwarder may not forward the next packet of a stream before it has noticed---by overhearing the transmission of the next hop---that the previous packet has succeeded. If there is congestion in an area, backpressure is implicitly built up towards the source, which then stops sending out packets until the congestion is released. BMCC takes care that every receiving node will receive packets at the same rate. An alternative mode of operation, BMCC with Backpressure Pruning (BMCC-BP) allows the cutting of congested branches for single packets, permitting a higher rate for uncongested receivers. Besides presenting protocols for multicast communication in MANETs, this thesis also describes implementations of two of the above-mentioned protocols. The first one is an implementation of SPBM for the Linux kernel that allows IP applications to send data via UDP to a group of receivers in an ad-hoc network. The implementation resides between the MAC layer and the network/IP layer of the network stack. It is compatible with unmodified standard kernels of versions 2.4 and 2.6, and may be compiled for x86 or ARM processor architectures. The second implementation is an implementation of CBMF for the ScatterWeb MSB430 sensor nodes. Due to their low-level programmability they allow an integration of the routing protocol with the medium access control. The absence of periodic beacon messages makes the protocol especially suitable for energy-constrained sensor networks. Furthermore, other constraints like limited memory and computational power demand special consideration as well.
|
|
Übersetzter Titel:
|
Positionsbasierter Multicast für mobile Ad-hoc-Netzwerke
(Deutsch)
|
|
Übersetzung des Abstracts:
|
Im Allgemeinen können Routingprotokolle für mobile Ad-hoc-Netzwerke (MANETs) in topologie- und positionsbasierte Protokolle eingeteilt werden. Während es im Bereich des Unicastroutings zahlreiche Vertreter beider Klassen gibt, beschränken sich die existierenden Multicastprotokolle im Wesentlichen auf topologiebasierte Ansätze, und nur einige wenige nutzen Positionsinformationen. Diese Verfahren haben gemeinsam, dass der sendende Netzwerkknoten den Multicastbaum, der für die Paketzustellung genutzt werden soll, vorberechnet und ihn in jedem versendeten Paket ablegt. Dieses Vorgehen bringt zwei Probleme mit sich: (a) Die Verfahren reagieren nicht flexibel auf topologische Veränderungen und verschenken damit die Vorteile des positionsbasierten Routings. (b) Sie skalieren nicht gut mit der Anzahl der Empfänger, da jeder einzelne von ihnen im Paketkopf aufgeführt werden muss. Diese Dissertation löst die angesprochenen Probleme und bringt das positionsbasierte Multicastrouting weiter voran. Position-Based Multicast (PBM) erhöht die Flexibilität des positionsbasierten Multicastrouting, indem es das Prinzip der Weiterleitung wie es für Unicastrouting angewandt wird für Multicast adaptiert. Es verlagert die Auswahl der Routen im Baum vom Sender zu den weiterleitenden Knoten im Netzwerk. Basierend auf den Positionen der benachbarten Knoten können diese die zum Zeitpunkt der Weiterleitung am besten geeigneten Nachbarn bestimmen. Die Skalierbarkeit in Bezug auf die Anzahl der Empfänger in der Gruppe wird durch Scalable Position-Based Multicast (SPBM) erreicht. Dieses Protokoll schließt eine Mitgliedschaftsverwaltung ein, die mehrere Aufgaben erfüllt. Erstens verwaltet sie die Mitgliedschaften und versorgt die Quellknoten mit Informationen darüber, ob eine bestimmte Gruppe Mitglieder enthält. Zweitens implementiert sie einen Ortungsdienst, der die Quellen mit den Positionen der angemeldeten Empfänger versorgt. Und drittens aggregiert sie die Mitgliedschaftsinformationen geographisch, um die gewünschte Skalierbarkeit zu ermöglichen. Contention-Based Multicast Forwarding (CBMF) geht die Probleme an, die in hochmobilen Netzwerken durch veraltete Positionsinformationen entstehen. Statt die Weiterleitungsentscheidung auf Basis einer Wahrnehmung zu fällen, werden die Pakete nur an die Zielpositionen adressiert; es werden keine expliziten Weiterleiter angegeben. Die Kandidaten für die Weiterleitung entscheiden selbst in einem Wettbewerb, wer von ihnen am besten geeignet ist. Die Entscheidung wird dadurch nicht nur auf Basis der bestmöglichen Daten getroffen, dieses Vorgehen spart zusätzlich das regelmäßige Versenden von Positionsnachrichten ein und reduziert so den Overhead. Ein weiteres ungelöstes Problem ist das Fehlen einer Staukontrolle für Multicast in Ad-hoc-Netzwerken. Das Senden von immer mehr Paketen an eine Multicastgruppe verringert den Durchsatz. Backpressure Multicast Congestion Control (BMCC) sorgt dafür, dass das Netzwerk nicht mehr Pakete aufnehmen muss als es kann. Das wird erreicht, indem die Paketwarteschlangen auf den Knoten unterwegs streng limitiert werden. Ein Knoten darf kein weiteres Paket eines Datenstroms weiterleiten, bevor er nicht mitbekommen hat, dass das vorherige Paket bereits auf dem Weg zum übernächsten Knoten ist. Dadurch wird, wenn ein Gebiet überlastet ist, implizit ein Rückdruck in Richtung der Quelle aufgebaut, die daraufhin das Versenden weiterer Pakete aussetzt. BMCC sorgt dafür, dass jeder Empfänger Pakete mit der gleichen Rate erhält. Ein alternativer Modus, BMCC mit Backpressure Pruning (BMCC-BP), erlaubt das Abschneiden überlasteter Zweige für einzelne Pakete, wodurch Empfänger, die nicht überlastet sind, die Möglichkeit bekommen, Daten mit einer höheren Datenrate zu empfangen. Neben der Vorstellung von Protokollen für die Multicastkommunikation in MANETs beschreibt diese Dissertation auch die Implementierungen zweier oben erwähnter Protokolle. Die erste ist eine Implementierung von SPBM für den Linuxkern, die es IP-Anwendungen erlaubt, Daten per UDP an eine Gruppe von Empfängern in einem Ad-hoc-Netzwerk zu senden. Die Implementierung ist im Schichtenmodell zwischen der Medienzugriffs- und der Netzwerkschicht angesiedelt. Sie ist mit den unmodifizierten Standardkernen der Versionen 2.4 und 2.6 kompatibel und kann sowohl für x86- also auch für ARM-Prozessorarchitekturen kompiliert werden. Die zweite Implementierung ist eine Implementierung von CBMF für die Sensorknoten ScatterWeb MSB430. Da sie sich auf unterster Netzwerkebene programmieren lassen, erlauben sie eine Integration des Routingprotokolls mit der Medienzugriffskontrolle. Das Fehlen periodischer Positionsnachrichten erleichtert den Einsatz des Protokolls in Sensornetzwerken mit beschränkten Energievorräten. Darüberhinaus erfordern auch andere Einschränkungen wie ein begrenzter Speicherplatz und eine eingeschränkte Rechenleistung besondere Beachtung.
(Deutsch)
|
|
Zusätzliche Informationen:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
