PatentDe  


Dokumentenidentifikation DE102006030282A1 10.01.2008
Titel Verfahren und Netzwerkknoten zur Broadcast-Übertragung von Daten
Anmelder Siemens AG, 80333 München, DE
Erfinder Hollick, Matthias, 64289 Darmstadt, DE;
Mogre, Parag Sudhir, Mumbai, IN;
Schwingenschlögl, Christian, Dr., 85640 Putzbrunn, DE
DE-Anmeldedatum 30.06.2006
DE-Aktenzeichen 102006030282
Offenlegungstag 10.01.2008
Veröffentlichungstag im Patentblatt 10.01.2008
IPC-Hauptklasse H04L 12/18(2006.01)A, F, I, 20060630, B, H, DE
IPC-Nebenklasse H04J 3/00(2006.01)A, L, I, 20060630, B, H, DE   
Zusammenfassung Verfahren zur Broadcast-Übertragung von Daten von einem Sendeknoten (SK) zu mehreren benachbarten Empfangsknoten (EK) eines Netzes in Rahmen, die jeweils mehrere Zeitschlitze (TS) aufweisen, wobei jeder Zeitschlitz (TS) eines Rahmens einen Verfügbarkeitsstatus aufweist, der sich in Abhängigkeit von Zeitschlitzreservierungen anderer Knoten des Netzes verändert, wobei der Sendeknoten (SK) die Daten in mindestens einem Zeitschlitz (TS) mit einer bestimmten einstellbaren Wahrscheinlichkeit (p) zu den Empfangsknoten (EK) sendet, wenn der Verfügbarkeitsstatus des jeweiligen Zeitschlitzes (TS) angibt, dass der Zeitschlitz (TS) zur Datenübertragung frei verfügbar ist.

Beschreibung[de]

Die Erfindung betrifft ein Verfahren und einen Netzwerkknoten zur Broadcast-Übertragung von Daten in einem Netz, insbesondere in einem Mesh-Datennetz.

Der IEEE 802.16-Standard spezifiziert die Luftschnittstelle einschließlich der Medium Access Control (MAC) und verschiedener Spezifikationen der physikalischen Schicht eines Breitband-drahtlosen Zugriffsystems (BWA: Broadband Wireless Access) zur Unterstützung verschiedener Dienstleistungen. Der IEEE 802.16-Standard spezifiziert zwei Betriebsmodi, nämlich einen Punkt zu Mehrpunkt-Betriebsmodus (PMP: Point-to-Multipoint-Mode) und einen optionalen Mesh-Betriebsmodus.

In dem PMP-Betriebsmodus ist es ausschließlich möglich, dass Teilnehmerstationen bzw. Subscriberstationen (SS) nur direkt mit einer Basisstation (BS) kommunizieren können. Die einzelnen Teilnehmerstationen SS, bei denen es beispielsweise um mobile Endgeräte handelt, können nicht direkt miteinander kommunizieren. Daher müssen sich die einzelnen Teilnehmerstationen SS innerhalb der direkten Sendereichweite der Basisstation BS befinden, um einen Zugang zu dem Netzwerk zu erhalten.

Der andere in dem Standard 802.16 spezifizierte Betriebsmodus wird als Mesh-Betriebsmodus (Mesh Mode/MSH) bezeichnet. Der Hauptunterschied zwischen dem PMP-Betriebsmodus und dem MSH-Betriebsmodus besteht darin, dass in dem PMP-Betriebsmodus der Datenaustausch ausschließlich zwischen der Basisstation BS und den Teilnehmerstationen SS stattfindet, während in dem Mesh-Betriebsmodus Daten zwischen einer Teilnehmerstation SS und der Basisstation BS ausgetauscht werden indem die Daten über andere Teilnehmerstationen SS geroutet werden. Ein Datenaustausch kann auch direkt zwischen unterschiedlichen Teilnehmerstationen SS erfolgen. Der Vorteil eines Mesh-Betriebsmodus besteht darin, dass er eine indirekte Datenkommunikation eines Teilnehmergerätes SS mit der Basisstation BS erlaubt, d. h. es müssen weniger Basisstationen BS bei der Implementierung des Netzes vorgesehen werden. Ein weiterer Vorteil besteht in einer erhöhten Reichweite der Basisstation BS, die über deren physikalische Sendereichweite hinausgeht.

Die auf dem Standard 802.16-2004 basierenden Mesh-Datennetze beschreiben keinen Mechanismus für einen Broadcast- oder einen Multicast von Daten. Bei einer Broadcast-Datenübertragung von Daten sendet ein Sendeknoten (SK) Daten an alle (Broadcast) oder an eine bestimmte Untergruppe von benachbarten Knoten (Multicast). Damit ein Sendenknoten SK an die benachbarten Knoten Daten senden kann, muss er gemäß dem 802.16-2004-Standard seine Broadcast-Nachrichten sequentiell senden, d. h. der Sendeknoten (SK) sendet die Daten zunächst an einen ersten Empfangsknoten EKi und dann anschließend an einen weiteren Empfangsknoten EKi+1 usw. bis alle benachbarten Knoten erreicht sind. Die dabei benötigte Bandbreite steigt mit der Anzahl der benachbarten Knoten. Die zeitliche Verzögerung der übermittelten Broadcast-Nachrichten wird ebenfalls erhöht. Die zeitliche Verzögerung bzw. das Delay für darauf folgende Nachrichten steigt ebenfalls durch den Aufwand für die Übermittlung der Broadcast-Nachricht.

Es ist daher die Aufgabe der vorliegenden Erfindung, ein Verfahren und einen Netzwerkknoten zur effizienten Broadcast-Übertragung von Daten, insbesondere in 802.16-basierten Mesh-Netzen, zu schaffen.

Diese Aufgabe wird erfindungsgemäß durch ein Verfahren mit den im Patentanspruch 1 angegebenen Merkmalen sowie durch einen Netzwerkknoten gemäß Anspruch 9 gelöst.

Die Erfindung schafft ein Verfahren zur Broadcast-Übertragung von Daten von einem Sendeknoten zu mehreren benachbarten Empfangsknoten eines Netzes in Rahmen, die jeweils mehrere Zeitschlitze aufweisen,

wobei jeder Zeitschlitz eines Rahmens einen Verfügbarkeitsstatus aufweist, der sich in Abhängigkeit von Zeitschlitzreservierungen anderer Knoten des Netzes verändert,

wobei der Sendeknoten die Daten in mindestens einem Zeitschlitz mit einer bestimmten einstellbaren Wahrscheinlichkeit zu dem Empfangsknoten sendet, wenn der Verfügbarkeitsstatus des jeweiligen Zeitschlitzes angibt, dass der Zeitschlitz zur Datenübertragung frei verfügbar ist.

Dabei wird bei einer ersten Ausführungsform die Sende-Wahrscheinlichkeit in Abhängigkeit von einer Netzlast des Netzes eingestellt.

Bei einer alternativen Ausführungsform wird die Sende-Wahrscheinlichkeit in Abhängigkeit von einer Anzahl der zu einem Sendeknoten benachbarten Knoten eingestellt.

Bei einer weiteren alternativen Ausführungsform wird die Wahrscheinlichkeit von einem Nutzer eingestellt.

Bei einer bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens weist ein Zeitschlitz zur Datenübertragung als Verfügbarkeitsstatus den Zustand "frei verfügbar" auf, wenn der Sendeknoten in diesem Zeitschlitz weder selbst Daten sendet noch empfängt und wenn ferner keiner der zu dem Sendeknoten benachbarten Knoten in diesem Zeitschlitz Daten sendet oder empfängt.

Bei einer bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens wird das Netz durch ein drahtloses Datennetz gebildet.

Bei einer bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens wird das Netz durch ein drahtloses Mesh-Netz gebildet.

Bei einer besonders bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens wird das Netz durch ein drahtloses WiMax-Mesh-Netz gebildet.

Die Erfindung schafft ferner einen Netzwerkknoten zur Broadcast-Übertragung von Daten zu mehreren benachbarten Empfangsknoten eines Netzes in Rahmen, die jeweils mehrere Zeitschlitze aufweisen, wobei jeder Zeitschlitz eines Rahmens einen Verfügbarkeitsstatus aufweist, der in Abhängigkeit von Zeitschlitzreservierungen anderer Knoten des Netzes veränderbar ist, wobei der Netzwerkknoten eine Sende/Empfangseinrichtung und eine Prozessiereinrichtung aufweist, die derart ausgestaltet sind, dass die Daten in mindestens einem Zeitschlitz mit einer bestimmten einstellbaren Wahrscheinlichkeit zu dem Empfangsknoten gesendet werden, wenn der Verfügbarkeitsstatus des jeweiligen Zeitschlitzes angibt, dass der Zeitschlitz zur Datenübertragung frei verfügbar ist.

Bevorzugt ist der Netzwerkknoten ausgestaltet zur drahtlosen Datenübertragung, insbesondere gemäß IEEE 802.16.

Bevorzugt weist der Netzwerkknoten einen Verfügbarkeitsspeicher auf, in dem zu jedem Zeitschlitz eines Rahmens ein veränderbarer Verfügbarkeitsstatus des Zeitschlitzes gespeichert ist.

Das System zur Broadcast-Übertragung von Daten von einem Sendeknoten zu mehreren benachbarten Empfangsknoten eines Netzes in Rahmen, die jeweils mehrere Zeitschlitze aufweisen weist wenigstens einen erfindungsgemäßen Netzwerkknoten auf.

Bei einer bevorzugten Ausführungsform des Systems ist das Netz ein drahtloses Datennetz. Bei einer weiteren Ausführungsform des Systems ist das Netz ein drahtloses Mesh-Datennetz. Bei einer besonders bevorzugten Ausführungsform des Systems ist das Netz ein drahtloses 802.16-Mesh-Datennetz.

Die Knoten werden vorzugsweise durch mobile Endgeräte oder Basisstationen gebildet.

Bei einer Ausführungsform des Systems zur Broadcast-Datenübertragung weisen die Knoten des Netzes jeweils einen Verfügbarkeitsspeicher auf, in dem zu jedem Zeitschlitz TS eines Rahmens ein veränderbarer Verfügbarkeitsstatus des Zeitschlitzes gespeichert ist.

Bei einer Ausführungsform des Systems gibt der Verfügbarkeitsstatus eines Zeitschlitzes als einen ersten Zustand eine freie Verfügbarkeit a (available) des Zeitschlitzes an, wenn der Knoten in diesem Zeitschlitz weder bereits Daten selbst sendet noch empfängt und wenn ferner keiner der zu dem Knoten benachbarten Knoten in diesem Zeitschlitz TS Daten sendet oder empfängt.

Bei einer Ausführungsform des Systems gibt der Verfügbarkeitsstatus eines Zeitschlitzes als einen zweiten Zustand eine Sendeverfügbarkeit t (transmit-available) des Zeitschlitzes an, wenn der Knoten in diesem Zeitschlitz weder bereits Daten selbst sendet noch empfängt und wenn keiner der zu dem Knoten benachbarten Knoten in diesem Zeitschlitz Daten empfängt und wenn mindestens einer der zu dem Knoten benachbarten Knoten in diesem Zeitschlitz Daten sendet.

Bei einer Ausführungsform des Systems zur Broadcast-Übertragung gibt der Verfügbarkeitsstatus eines Zeitschlitzes als einen dritten Zustand eine Empfangsverfügbarkeit r (receive-available) des Zeitschlitzes an, wenn der Knoten in diesem Zeitschlitz weder bereits Daten selbst sendet noch empfängt und wenn keiner der benachbarten Knoten Daten in diesem Zeitschlitz sendet und wenn ferner mindestens einer der benachbarten Knoten in dem Zeitschlitz Daten empfängt.

Bei einer weiteren Ausführungsform des Systems zur Broadcast-Übertragung gibt der Verfügbarkeitsstatus eines Zeitschlitzes TS als einen vierten Zustand keine Verfügbarkeit u (unavailable) des Zeitschlitzes an, wenn der Knoten selbst Daten in dem Zeitschlitz sendet oder empfängt oder wenn mindestens einer der benachbarten Knoten in diesem Zeitschlitz Daten sendet und mindestens einer der benachbarten Knoten in diesem Zeitschlitz Daten empfängt.

Im Weiteren werden bevorzugte Ausführungsformen des erfindungsgemäßen Verfahrens und des erfindungsgemäßen Netzwercknotens wie des Systems zur Broadcast-Übertragung von Daten unter Bezugnahme auf die beigefügten Figuren zur Erläuterung erfindungswesentlicher Merkmale beschrieben.

Es zeigen:

1: ein Schema zur Erläuterung der Funktionsweise des erfindungsgemäßen Verfahrens;

2: ein Diagramm zur Erläuterung der bei dem erfindungsgemäßen Verfahren eingesetzten verschiedenen Zeitschlitz-Verfügbarkeiten;

3: ein Blockschaltbild einer möglichen Ausführungsform eines in dem erfindungsgemäßen System zur Broadcast-Übertragung vorgesehenen Knotens;

4: ein Beispiel für einen Speicherinhalt eines Verfügbarkeitsspeichers innerhalb des in 3 dargestellten Knotens;

5: ein Diagramm zur Darstellung des Aufbaus eines in dem erfindungsgemäßen Verfahren eingesetzten Rahmens;

6: ein Ablaufdiagramm zur Darstellung einer möglichen Ausführungsform des erfindungsgemäßen Verfahrens zur Broadcast-Übertragung von Daten;

7: ein Diagramm zur Darstellung eines Beispiels von verschiedenen Zeitschlitz-Zustandswahrscheinlichkeiten als Funktion der Anzahl der zu dem Sendeknoten benachbarten Knoten zur Erläuterung des erfindungsgemäßen Verfahrens;

8: ein weiteres Diagramm zur Darstellung eines Beispiels von Veränderung der Zeitschlitz-Wahrscheinlichkeiten in Abhängigkeiten von der Anzahl der zu dem Sendeknoten benachbarten Knoten zur Erläuterung des erfindungsgemäßen Verfahrens.

Wie man aus 1 erkennen kann, überträgt ein Sendeknoten SK bei einer Broadcast-Datenübertragung Daten an alle (Broadcast) oder an eine bestimmte Untergruppe seiner benachbarten Empfangsknoten (Multicast). Ein Mechanismus zur Unterstützung von Multicast- und Broadcast-Nachrichten ist wesentlich, um die Kapazität an der Luftschnittstelle möglichst effizient zu nutzen und die auftretenden Delays zur Datenübertragung zu minimieren. Bei einigen Datennetzen, insbesondere bei Mesh-Datennetzen, die auf dem IEEE 802.16-Standard beruhen, werden Daten in Sende-Rahmen (Frames) übertragen, die in viele Zeitschlitze TS unterteilt sind, wobei a priori eine Reservierung der Zeitschlitze TS vor der eigentlichen Datenübertragung erfolgt. Vor der Datenübertragung wird dabei bei 802.16 ein Zeitschlitz TS in einem Drei-Wege-Handshake-Verfahren reserviert.

Bei der Broadcast-Übertragung von Daten überträgt ein Sendeknoten Daten mit der Absicht, dass alle Nachbarknoten die Daten empfangen. Bei den Nachbarknoten handelt es sich um Knoten, die sich innerhalb der Sendereichweite des Sendeknotens befinden und die in der Lage sind, die gesendeten Daten zu empfangen und zu decodieren. Bei einer normalen Datenübertragung werden Zeitschlitze verwendet, die a priori, d. h. vor der eigentlichen Datenübertragung reserviert werden. Die Knoten können jedoch Zeitschlitze nur für eine bestimmte Datenverbindung bzw. Link anfordern (request) und reservieren.

Derartige herkömmliche Knoten besitzen daher nicht die Fähigkeit, die Broadcast-Datenübertragung an alle Nachbarn in einer einzelnen Datenübertragung bzw. innerhalb eines Rahmens durchzuführen.

2 zeigt ein Diagramm zur Erläuterung verschiedener Zustände, die Knoten und die Zeitschlitze TS in einem Netz einnehmen können. Bei dem in 2 dargestellten Beispiel möchte ein erster Knoten A an einen zweiten Knoten B Daten übertragen. NAB bezeichnet eine Gruppe von gemeinsamen Nachbarknoten des Knotens A und des Knotens B. NA bezeichnet eine Gruppe von Knoten, die die Nachbarknoten zu Knoten A bilden, die jedoch nicht einen Nachbarknoten zu Knoten B darstellen. NB bezeichnet eine Gruppe von Nachbarknoten des Knotens B, die jedoch keine Nachbarknoten des Knotens A sind. Wenn die Zeitschlitze anfänglich den Status "frei verfügbar" einnehmen, erfolgt die Datenübertragung zwischen dem Knoten A und dem Knoten B wie folgt. Zunächst reservieren die Knoten A, B mindestens einen Zeitschlitz zur Datenübertragung in einem Drei-Wege-Handshake-Verfahren, d. h. mit einer Anforderungsnachricht (Request), einer Grant-Nachricht bzw. Gewährnachricht gefolgt von einer Bestätigungsnachricht (Grant-Confirmation). Nach der Ausführung der Handshake-Reservierung weisen die für die Datenübertragung von dem Knoten A bzw. Knoten B zugewiesenen Zeitschlitze einen unterschiedlichen Verfügbarkeitsstatus bei den verschiedenen Knoten auf. Die Knoten NA befinden sich innerhalb der Sendereichweite des sendenden Knotens A und sind daher nicht in der Lage, andere Daten während des Zeitschlitzes zu empfangen. Dieser Status wird als Sendeverfügbarkeit t (transmit-available) bezeichnet. Diese Knoten können während des gleichen Zeitschlitzes TS Daten senden, ohne dass es zu Kollisionen an dem Empfänger B kommt. Der Status des zugewiesenen Zeitschlitzes TS ist eine Empfangsverfügbarkeit r (receive-available) für die Knoten der Gruppe NB. Die in der Gruppe NAB befindlichen Knoten, d. h. die Knoten, die sowohl benachbart zu dem Knoten A als auch zu dem Knoten B sind, verändern den Status des zugewiesenen Zeitschlitzes TS zu U "nicht verfügbar" (unavailable). Wie man aus 2 erkennen kann, verändert eine einzelne Datenübertragung die Verteilung des Status des Zeitschlitzes TS in dem gesamten Netzwerk. Ein Zeitschlitz TS kann einen von vier Zuständen einnehmen, nämlich "frei verfügbar" (available), "sendeverfügbar" (transmit-available), "empfangsverfügbar" (receive-available) und "nicht verfügbar" (unavailable). Ein Knoten des Netzwerkes befindet sich entweder in einem Leerbetrieb (idle), d. h. er sendet weder Daten an benachbarte Knoten noch empfängt er Daten, die an ihn adressiert sind, von benachbarten Knoten. Andererseits kann es sich bei dem Knoten um einen Sendeknoten SK handeln oder um einen Empfangsknoten EK. Ein Sendeknoten SK sendet Daten an einen benachbarten Knoten. Ein Empfangsknoten empfängt Daten, die an ihn adressiert sind, von einem benachbarten Knoten.

Ein Zeitschlitz TS kann einen von vier Zuständen einnehmen. Ein Zeitschlitz hat den Status "frei verfügbar" (available), falls der Sendeknoten selbst keine Daten in diesem Zeitschlitz sendet oder empfängt und wenn gleichzeitig keiner der benachbarten Knoten Daten in diesem Zeitschlitz empfängt oder sendet. Ein Zeitschlitz hat den Status "empfangsverfügbar" (receive-available), wenn der Sendeknoten selbst keine Daten in diesem Zeitschlitz TS sendet oder empfängt und wenn keiner seiner Nachbarknoten in diesem Zeitschlitz TS Daten sendet und wenn ferner wenigstens einer der Nachbarknoten Daten in dem Zeitschlitz TS empfängt. Ein Zeitschlitz TS befindet sich in dem Zustand bzw. Status "sendeverfügbar" (transmit-available) an einem Knoten, wenn der Knoten selbst weder Daten in dem Zeitschlitz TS sendet oder empfängt und ferner keiner seiner Nachbarknoten Daten in dem Zeitschlitz TS empfängt und mindestens einer der Nachbarknoten Daten in dem Zeitschlitz TS überträgt. Ein Zeitschlitz TS befindet sich in dem Status "nicht verfügbar" (unavailable), wenn der Knoten selbst Daten in dem Zeitschlitz TS sendet oder empfängt oder wenn mindestens einer der Nachbarknoten Daten sendet und mindestens einer der Nachbarknoten Daten empfängt.

Ein Knoten k des Datennetzes befindet sich entweder im Leerlauf, d. h. er empfängt weder Daten von einem Nachbarknoten noch sendet er Daten zu einem Nachbarknoten. Als zweite Alternative, sendet der Knoten Daten, d. h. er ist ein Sendeknoten, oder als dritte Alternative, empfängt der Knoten Daten, d. h. er ist ein Empfangsknoten EK. Pi + Ps + Pe = 1, wobei

Pi
die Wahrscheinlichkeit darstellt, dass sich der Knoten im Leerlauf (idle) befindet,
Ps
die Wahrscheinlichkeit darstellt, dass Knoten Daten sendet, und
Pe
die Wahrscheinlichkeit angibt, dass der Knoten Daten empfängt.

Ein Zeitschlitz TS kann entweder "frei verfügbar" a (available), "empfangsverfügbar" r (receive-available), "sendeverfügbar" t (transmit-available) oder "nicht verfügbar" u (unavailable) sein: Pu + Pr + Pt + Pu = 1

Weist ein Knoten d einen Nachbarknoten auf, d. h. ist sein Knotengrad d, erhält man die folgenden Beziehungen über die verschiedenen Zeitschlitz-Wahrscheinlichkeiten an einem bestimmten Knoten Pa = Pid+1 Pr = Pi((Pe + Pi)d – Pid Pt = Pi((Pe + Pi)d – Pid Pu = (1 – Pi) + Pi(1 + Pid – (Pe + Pi)d – (Ps + Pi)d)

7 zeigt den Trend einer einzelnen Zeitschlitz-Wahrscheinlichkeit in Abhängigkeit von dem Knotengrad d. Es wird eine Leerlauf-Wahrscheinlichkeit Pi von 0,9 angenommen, d. h. das Netzwerk ist leicht belastet. Ferner wird angenommen, dass die Sendewahrscheinlichkeit Ps gleich der Empfangswahrscheinlichkeit Pe ist und einen Wert von 0,5 einnimmt. Wie man aus 7 erkennen kann, nimmt die Wahrscheinlichkeit für Zeitschlitze TS mit dem Status "frei verfügbar" bzw. "available" drastisch mit dem Knotengrad d ab, selbst wenn die Wahrscheinlichkeit, dass die Knoten inaktiv sind (Pi) sehr hoch ist.

8 zeigt den Trend der verschiedenen Zeitschlitzstatus in Abhängigkeit von dem Knotengrad d, wobei hierbei eine geringere Netzwerklast betrachtet wird, bei der die Wahrscheinlichkeit, dass ein Knoten inaktiv bzw. idle in einem Zeitschlitz TS ist, bei beispielsweise 0,5 liegt. Bei dem gegebenen Beispiel ist die Wahrscheinlichkeit, dass ein Knoten sendet bzw. empfängt ebenfalls gleich mit 0,25 angenommen. Wie man aus 8 erkennen kann, nimmt mit zunehmendem Knotengrad d bzw. zunehmender Anzahl benachbarter Knoten die Anzahl der nicht-verfügbaren Zeitschlitze (unavailable) drastisch zu und die Anzahl der Zeitschlitze mit dem Status "frei verfügbar" bzw. "available" nimmt stark ab.

Bei dem erfindungsgemäßen Verfahren zur Broadcast-Datenübertragung erfolgt die Datenübertragung in einem Zeitschlitz TS des Sendeknotens dessen Status als "frei verfügbar" (available) gekennzeichnet ist. Dabei werden die Daten mit einer bestimmten einstellbaren Wahrscheinlichkeit p gleichzeitig an die benachbarten Knoten gesendet bzw. gebroadcastet. Möchte ein Knoten Daten bzw. ein Datenpaket via Broadcast übertragen, wartet er bei dem erfindungsgemäßen Verfahren, bis ein Zeitschlitz bzw. Mini-Slot TS mit dem Status "available" verfügbar wird. Mit einer Wahrscheinlichkeit p überträgt dann der Knoten das Datenpaket bzw. die Daten in diesen Mini-Slot bzw. Zeitschlitz TS.

Bei dem erfindungsgemäßen Verfahren erfolgt die Broadcast-Übertragung von Daten in Rahmen, wie sie beispielhaft in 5 dargestellt sind. Jeder Sende-Rahmen (Frame) besteht aus einem Steuer-Subframe (Control-Subframe) und einem Daten-Subframe (Data-Subframe), die ihrerseits in eine Vielzahl von Zeitschlitzen TS untergliedert sind. Im Steuer-Subframe erfolgt die Übertragung von Steuernachrichten während die eigentliche Datenübertragung in den Zeitschlitzen TS der Data-Subframes erfolgt. Bei dem erfindungsgemäßen Verfahren wird jedem Zeitschlitz TS des Data-Subframes ein Verfügbarkeitsstatus zugeordnet, wobei dieser Verfügbarkeitsstatus in Abhängigkeit von Zeitschlitzreservierungen anderer Knoten des Netzes veränderbar ist. Bei dem erfindungsgemäßen Verfahren sendet ein Sendeknoten SK die Daten in mindestens einem Zeitschlitz TS des Data-Subframes mit einer bestimmten einstellbaren Wahrscheinlichkeit p zu dem Empfangsknoten EK, wenn der Verfügbarkeitsstatus des jeweiligen Zeitschlitzes TS angibt, dass der Zeitschlitz TS zur Datenübertragung frei verfügbar (available) ist.

3 zeigt ein Blockschaltbild eines bei dem erfindungsgemäßen System zur Broadcast-Übertragung vorgesehenen Knotens. Der Knoten des Netzwerkes enthält einen Transceiver 1 zum Senden und Empfangen von Daten, der durch eine Steuerung 2 angesteuert wird. Die Datenübertragung durch den Transceiver 1 erfolgt vorzugsweise über eine drahtlose Schnittstelle. Die Steuerung 2 zur Ansteuerung des Transceivers 1 weist eine Schnittstelle zum Einstellen der Sendewahrscheinlichkeit p auf. Darüber hinaus weist der Knoten k einen Speicher 3 auf, in dem der Verfügbarkeitsstatus für alle Zeitschlitze TS eines Rahmens abgespeichert ist, wobei sich der Verfügbarkeitsstatus eines jeden Zeitschlitzes TS dynamisch ändert.

4 zeigt ein Beispiel für einen Speicherinhalt eines Speichers 3. Jedem Zeitschlitz TS des Rahmens bzw. des Data-Subframes ist ein Verfügbarkeitsstatus zugeordnet, der die Verfügbarkeit des jeweiligen Zeitschlitzes TS angibt. Bei dem in 4 dargestellten Beispiel ist beispielsweise der Zeitschlitz TS = 1 nicht verfügbar (unavailable), der Zeitschlitz TS = 2 und der Zeitschlitz TS = 3 sind sendeverfügbar (transmit available), der Zeitschlitz TS = 4 ist empfangsverfügbar (receive-available) und der Zeitschlitz TS = 5 ist frei verfügbar (available). Ein Zeitschlitz TS ist frei verfügbar, wenn der Knoten in diesem Zeitschlitz TS weder bereits Daten selbst sendet noch empfängt und wenn ferner keiner der zu dem Knoten benachbarten Knoten in diesem Zeitschlitz TS Daten sendet oder empfängt.

Ein Zeitschlitz TS ist nicht verfügbar (unavailable), wenn der Knoten selbst Daten in diesem Zeitschlitz sendet oder empfängt oder wenn mindestens einer der benachbarten Knoten in diesem Zeitschlitz Daten sendet und mindestens einer der benachbarten Knoten in diesem Zeitschlitz TS Daten empfängt.

Der Verfügbarkeitsstatus eines jeden Zeitschlitzes TS verändert sich dynamisch in Abhängigkeit von den Zeitschlitzreservierungen anderer Knoten des Netzes. Ein Knoten k sendet Daten in mindestens einem Zeitschlitz mit einer bestimmten einstellbaren Wahrscheinlichkeit p in einer Broadcast-Datenübertragung an die benachbarten Empfangsknoten EK, wenn der Verfügbarkeitsstatus des jeweiligen Zeitschlitzes TS angibt, dass der Zeitschlitz TS zur Datenübertragung frei verfügbar (available) ist.

Die Wahrscheinlichkeit p wird dabei beispielsweise in Abhängigkeit von einer Netzlast eingestellt. Alternativ dazu kann die Wahrscheinlichkeit p in Abhängigkeit von der Anzahl der zu dem Sendeknoten SK des benachbarten Knotens eingestellt werden. Schließlich kann die Wahrscheinlichkeit p bei einer alternativen Ausführungsform auch durch einen Nutzer eingestellt werden. Auch Kombinationen zur Einstellung der Wahrscheinlichkeit p sind möglich.

Der in 3 dargestellte Knoten k befindet sich vorzugsweise in einem drahtlosen Datennetz, insbesondere in einem drahtlosen Mesh-Datennetz. Bei einer besonders bevorzugten Ausführungsform befindet sich der Knoten k in einem drahtlosen WiMax-Datennetz. Bei dem Knoten k, wie er in 3 dargestellt ist, kann es sich um ein beliebiges mobiles Endgerät oder um eine Basisstation BS handeln.

Bei einer bevorzugten Ausführungsform des erfindungsgemäßen Verfahren lässt sich durch folgenden Pseudo-Code beschreiben:

/*pseudocode for scheduling broadcast transmissions*/

while (true)

if (mini-slot.status==available)

/*falls mini-slot den status available hat, also nicht für eine Übertragung reserviert ist*/

with probability p

transmit (broadcast data);

end if;

end while;

Bei dem erfindungsgemäßen Verfahren erfolgt die (nicht-garantierte) Übertragung von Broadcast-Nachrichten basierend auf der Datenübertragung in Zeitschlitzen TS, die aktuell nicht für die Datenübertragung reserviert sind. Hierdurch ist es möglich, die Bandbreite, die aktuell verfügbar ist, d. h. die Zeitschlitze TS, die verfügbar (available) sind, und die bei Anwendung der standardisierten Mechanismen (Verzögerung aufgrund der Reservierung über Drei-Wege-Handshake) entfallen würde, erfindungsgemäß für Broadcast-Nachrichten zu Nutzen.

Ein weiterer Vorteil des erfindungsgemäßen Verfahren besteht in den niedrigen Delays für Broadcast-Nachrichten und damit auch der geringen Verzögerung für nachfolgende, gegebenenfalls ebenfalls zeitkritische Unicast-Nachrichten. Durch das erfindungsgemäße Verfahren wird der erfindungsgemäße Reservierungsansatz mit garantierter Zustellung in reservierten Zeitschlitzen, wie er in IEEE 802.16 standardisiert ist, nicht gefährdet, d. h. er funktioniert auch weiterhin ohne Beeinflussung durch den erfindungsgemäßen Broadcast-Mechanismus.

Ein weiterer Vorteil des erfindungsgemäßen Verfahrens besteht darin, dass nahezu alle Routing-Protokolle, die in Mesh-Datennetzen verwendet werden, Broadcast-Nachrichten benutzen, um entweder einen Überblick über Nachbarknoten zu bekommen, um Änderungen in der Menge der benachbarten Knoten zu erkennen oder zur Routensuche von Quellknoten zu Zielknoten. Das AODV-Protokoll (Adhoc On Demand Distance Vector Routing Protocol) versendet beispielsweise die Route-Request-Nachricht, d. h. die Nachricht zur Routenfindung, als Broadcast-Nachricht. Mit dem erfindungsgemäßen Verfahren ist es möglich, derartige Protokolle effizient in Mesh-Netzen anzuwenden, die auf dem 802.16-Standard beruhen.

6 zeigt ein Ablaufdiagramm einer möglichen Ausführungsform eines erfindungsgemäßen Verfahrens. Möchte ein Sendeknoten SK eine Broadcast-Datenübertragung durchführen, durchsucht er zunächst im Schritt S1 den Verfügbarkeitsspeicher 3 nach dem Verfügbarkeitsstatus der Zeitschlitze TS. Für jeden gewünschten Broadcast wird im Schritt S2 nachgesehen, ob der Status des aktuellen Zeitschlitzes TS eine freie Verfügbarkeit (available) anzeigt. Ist dies der Fall, erfolgt im Schritt S3 eine Broadcast-Datenübertragung der Daten mit einer einstellbaren Wahrscheinlichkeit p. Ist der Status des aktuellen Zeitschlitzes ein anderer, d. h., ist er nicht verfügbar (unavailable), sondern nur sendeverfügbar (transmit-available) oder empfangsverfügbar (receive-available), wartet der Knoten im Schritt S4 auf den nächsten Zeitschlitz mit dem Status "verfügbar" und kehrt dann wieder zur Schritt S1 zurück.


Anspruch[de]
Verfahren zur Broadcast-Übertragung von Daten von einem Sendeknoten (SK) zu mehreren benachbarten Empfangsknoten (EK) eines Netzes in Rahmen, die jeweils mehrere Zeitschlitze (TS) aufweisen,

wobei jeder Zeitschlitz (TS) eines Rahmens einen Verfügbarkeitsstatus aufweist, der sich in Abhängigkeit von Zeitschlitzreservierungen anderer Knoten des Netzes verändert,

wobei der Sendeknoten (SK) die Daten in mindestens einem Zeitschlitz (TS) mit einer bestimmten einstellbaren Wahrscheinlichkeit (p) zu den Empfangsknoten (EK) sendet, wenn der Verfügbarkeitsstatus des jeweiligen Zeitschlitzes (TS) angibt, dass der Zeitschlitz (TS) zur Datenübertragung frei verfügbar ist.
Verfahren nach Anspruch 1, wobei die Wahrscheinlichkeit (p) in Abhängigkeit von einer Netzlast eingestellt wird. Verfahren nach Anspruch 1, wobei die Wahrscheinlichkeit (p) in Abhängigkeit von der Anzahl der zu dem Sendeknoten (SK) benachbarten Knoten eingestellt wird. Verfahren nach Anspruch 1, wobei die Wahrscheinlichkeit (p) von einem Nutzer eingestellt wird. Verfahren nach einem der vorangehenden Ansprüche, wobei ein Zeitschlitz (TS) als Verfügbarkeitsstatus einen Zustand frei verfügbar aufweist, wenn der Sendeknoten (SK) in diesem Zeitschlitz (TS) weder bereits selbst Daten sendet noch empfängt und wenn ferner keiner der zu dem Sendeknoten (SK) benachbarten Knoten in diesem Zeitschlitz (TS) Daten sendet oder empfängt. Verfahren nach einem der vorangehenden Ansprüche, wobei das Netz durch ein drahtloses Datennetz gebildet wird. Verfahren nach Anspruch 6, wobei das Netz durch ein drahtloses Mesh-Netz gebildet wird. Verfahren nach Anspruch 7, wobei das Netz durch ein drahtloses WiMax-Mesh-Netz gebildet wird. Netzwerkknoten zur Broadcast-Übertragung von Daten zu mehreren benachbarten Empfangsknoten (EK) eines Netzes in Rahmen, die jeweils mehrere Zeitschlitze (TS) aufweisen,

– wobei jeder Zeitschlitz (TS) eines Rahmens einen Verfügbarkeitsstatus aufweist, der in Abhängigkeit von Zeitschlitzreservierungen anderer Knoten des Netzes veränderbar ist,

– wobei der Netzwerkknoten eine Sende/Empfangseinrichtung und eine Prozessiereinrichtung aufweist, die derart ausgestaltet sind, dass die Daten in mindestens einem Zeitschlitz (TS) mit einer bestimmten einstellbaren Wahrscheinlichkeit (p) zu dem Empfangsknoten (EK) gesendet werden, wenn der Verfügbarkeitsstatus des jeweiligen Zeitschlitzes (TS) angibt, dass der Zeitschlitz (TS) zur Datenübertragung frei verfügbar ist.
Netzwerkknoten gemäß Anspruch 9, ausgestaltet zur drahtlosen Datenübertragung, insbesondere gemäß IEEE 802.16. Netzwerkknoten gemäß Anspruch 9 oder 10, der einen Verfügbarkeitsspeicher aufweist, in dem zu jedem Zeitschlitz (TS) eines Rahmens ein veränderbarer Verfügbarkeitsstatus des Zeitschlitzes (TS) gespeichert ist. System zur Broadcast-Übertragung von Daten von einem Sendeknoten (SK) zu mehreren benachbarten Empfangsknoten (EK) eines Netzes in Rahmen, die jeweils mehrere Zeitschlitze (TS) aufweisen, aufweisend wenigstens einen Netzwerkknoten gemäß wenigstens einem der Ansprüche 9 bis 11. System nach Anspruch 12, wobei das Netz ein drahtloses Datennetz, ein drahtloses Mesh-Netz oder ein drahtloses IEEE 802.16-Mesh-Netz ist. System nach Anspruch 12 oder 13, wobei die Knoten durch mobile Endgeräte oder Basisstationen gebildet werden. System nach einem der Ansprüche 12 bis 14, wobei die Knoten des Netzes jeweils einen Verfügbarkeitsspeicher aufweisen, in dem zu jedem Zeitschlitz (TS) eines Rahmens ein veränderbarer Verfügbarkeitsstatus des Zeitschlitzes (TS) gespeichert ist. System nach Anspruch 15,

wobei der Verfügbarkeitsstatus eines Zeitschlitzes (TS) als einen ersten Zustand eine freie Verfügbarkeit des Zeitschlitzes (TS) angibt,

wenn der Knoten in diesem Zeitschlitz (TS) weder bereits Daten selbst sendet noch empfängt und wenn ferner keiner der zu dem Knoten benachbarten Knoten in diesem Zeitschlitz (TS) Daten sendet oder empfängt.
System nach Anspruch 15 oder 16,

wobei der Verfügbarkeitsstatus eines Zeitschlitzes (TS) als einen zweiten Zustand eine Sendeverfügbarkeit (transmit-available) des Zeitschlitzes (TS) angibt,

wenn der Knoten in diesem Zeitschlitz (TS) weder bereits Daten selbst sendet noch empfängt und wenn ferner keiner der zu dem Knoten benachbarten Knoten in diesem Zeitschlitz (TS) Daten empfängt und wenn ferner mindestens einer der zu dem Knoten benachbarten Knoten in diesem Zeitschlitz (TS) Daten sendet.
System nach einem der Ansprüche 15 bis 17, wobei der Verfügbarkeitsstatus eines Zeitschlitzes (TS) als einen dritten Zustand eine Empfangsverfügbarkeit (receive-available) des Zeitschlitzes (TS) angibt, wenn der Knoten in diesem Zeitschlitz (TS) weder bereits Daten selbst sendet noch empfängt und wenn ferner keiner der benachbarten Knoten in diesem Zeitschlitz (TS) Daten sendet und wenn ferner mindestens einer der benachbarten Knoten in diesem Zeitschlitz (TS) Daten empfängt. System nach einem der Ansprüche 15 bis 18, wobei der Verfügbarkeitsstatus eines Zeitschlitzes (TS) als einen vierten Zustand eine Nicht-Verfügbarkeit des Zeitschlitzes (TS) angibt, wenn der Knoten in diesem Zeitschlitz selbst Daten sendet oder empfängt oder wenn einer der benachbarten Knoten Daten sendet und einer der benachbarten Knoten Daten empfängt.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com