DE102010023299B4

DE102010023299B4 - Verfahren zum Übertragen von Daten

Info

Publication number: DE102010023299B4
Application number: DE201010023299
Authority: DE
Inventors: Dr. Liva Gianluigi; Christian Kissling
Original assignee: Deutsches Zentrum fuer Luft und Raumfahrt eV
Current assignee: Deutsches Zentrum fuer Luft und Raumfahrt eV
Priority date: 2010-06-10
Filing date: 2010-06-10
Publication date: 2012-01-05
Anticipated expiration: 2030-06-11
Also published as: DE102010023299A1

Abstract

Die Erfindung betrifft ein Verfahren zum Übertragen von Daten von einem Broadcast- oder Multicast-Transmitter zu mehreren Receivern, bei dem jeder Receiver eine erneute Übertragung durch den Broadcast-Transmitter verlangt, falls ein Datenpaket fehlerhaft ist oder fehlt. Gemäß der Erfindung wird zum Durchführen der erneuten Übertragung mindestens ein redundantes Paket generiert. Jedes redundante Paket weist ein fehlendes oder fehlerhaftes Datenpaket oder eine lineare Kombination eines derartigen fehlenden oder fehlerhaften Datenpakets mit einem korrekt empfangenen Datenpaket auf.

Description

Die Erfindung betrifft ein Verfahren zum Übertragen von Daten von einem Broadcast-Transmitter zu mehreren Receivern.
Das in dieser Patentanmeldung angesprochene Problem tritt z. B. im Kontext der Verwendung von Satellitensystemen zum Senden von Information an mehrere User auf. Das über den Satellit erfolgende Senden von Daten von einer Quelle an mehrere User, die sämtlich den gleichen Inhalt empfangen, wird in Datenpaketen, z. B. IP-Datagrammen, organisiert. Aufgrund der Übertragungskanalbedingungen erfahren die User verschiedene Bitfehlerraten und somit Paketfehlerraten (PER). Infolge der Paketfehlerraten ist bei jedem User ein Teil der empfangenen Pakete fehlerhaft, oder er fehlt. Bei den Paketen, die bei verschiedenen Usern fehlerhaft sind, handelt es sich nicht notwendigerweise um die gleichen Pakete. Dieses Szenario ist in 1 gezeigt.
Dort ist ersichtlich, dass das Gateway (G) über das Satellitensystem 6 Pakete an vier User (A bis D) sendet. Aufgrund des PER auf dem Kanal verliert jeder User einige Pakete (die in der Figur dunkel markiert sind). Die User müssen nun die erneute Übertragung jedes der Pakete verlangen, die sie verloren haben. In dem Beispiel bedeutet dies eine erneute Übertragung des Pakets 1 (das für den User D verlorengegangen ist), des Pakets 2 (für den User C), des Pakets 5 (für den User B) und des Pakets 4 (für den User A). Da es hier um ein Sendesystem geht, müssen sämtliche verlorenen Pakete an sämtliche mit dem System verbundene User gesendet werden. Da z. B. das Paket 1 von den Usern A–C korrekt empfangen wurde, stellt für diese User die erneute Übersendung dieses Pakets unnötige Information dar und reduziert somit die Systemeffizienz.
Dies bedeutet, dass in einem derartigen Broadcast- oder Multicast-Szenario sämtliche User die wiederholten Pakete empfangen, auch wenn sie für einen anderen User vorgesehen sind und für die übrigen User keinen weiteren Nutzen haben. Somit besteht der Hauptnachteil eines derartigen ARQ-Systems (Automatic Repeat Request) darin, dass eine hohe Kapazität für eine erneute Übertragung von Daten verschwendet wird, die nicht für sämtliche User in den Systemen nützlich sind. Dies führt zu einem Verschleiß an Zeit und Kapazität. Ein Beispiel für ein solches Szenario ist in 2 gezeigt.
Wie ersichtlich ist, werden sämtliche fehlerhaften Pakete durch das Gateway erneut übertragen, nämlich die Pakete 1, 2, 4 und 5 (siehe rechte Seite in 2).
Wie ebenfalls gezeigt ist, werden sämtliche Pakete an sämtlichen Terminals empfangen, jedoch kann jeder User nur ein einziges der Pakete nutzen, nämlich dasjenige, dass er zuvor vermisst hat. Die übrigen 3 empfangenen Pakete können nicht verwendet werden und stellen somit für den Terminal unnötige Information dar. Dies bedeutet, dass, obwohl sämtliche 4 Pakete erneut übertragen werden müssen, damit alle User die erforderlichen Daten erhalten, jedes Terminal nur ein einziges der 4 Pakete nutzen kann. Aus dem Blickwinkel jedes Users ist die erneute Übertragung der anderen 3 Pakete gleichbedeutend mit einer Kapazitätsverschwendung, die sich in höheren Kosten für den Service widerspiegelt, da sie Bandbreite benötigt. Zudem verursacht diese Art der erneuten Übertragung für die User eine Zunahme an Verzögerung und Verzögerungs-Jitter, da jedes Terminal, bevor es das fehlende Paket empfängt, warten muss, bis es an der Reihe ist. Die höhere Verzögerung und das höhere Verzögerungs-Jitter wirken sich dann möglicherweise in Form einer niedrigeren Service-Qualität aus, insbesondere bei Echtzeit-Anwendungen wie Video- oder Audio-Streaming.
Aus DE 10 2008 003 588 ist bekannt, durch das Gateway eine Neuübertragung einer linearen Kombination von Paketen vorzunehmen. Die Idee bei dieser Patentanmeldung besteht darin, dass sämtliche User derartige lineare Kombinationen empfangen, wodurch sie in der Lage sind, ihre fehlenden Pakete rückzugewinnen, indem sie deren Anteil an der linearen Kombination subtrahieren. Ein mögliches Szenario der in dieser Patentanmeldung präsentierten Lösung ist in 3 gezeigt. In dem Beispiel wird angenommen, dass sämtliche User die Pakete empfangen, wie in 1 gezeigt ist.
Jedes Terminal sendet dann – wie zuvor – an das Gateway ein Repeat Request für die Pakete, die es vermisst. Das Gateway sendet dann nicht sämtliche 4 Pakete, wie in 2 gezeigt, sondern berechnet die Modulo-2-Summe der 4 Pakete, die dann ein neues Paket bildet, das in 3 als ”CODED” bezeichnet ist. Dieses Paket wird an sämtliche Terminals gesendet. Die Terminals berechnen dann die Modulo-2-Summe ihrer korrekt empfangenen Pakete zusammen mit dem empfangenen ”CODED”-Paket, wodurch sich das fehlende Paket ergibt. Dieser Mechanismus funktioniert für sämtliche Terminals. Auf diese Weise kann in diesem Beispiel die Rückübertragungs-Anzahl von Paketen von 4 auf 1 reduziert werden. Ferner empfängt jedes Terminal die fehlende Information gleichzeitig, ohne auf seinen Neuübertragungs-Slot warten zu müssen.
Um dieses Prinzip allgemein anzuwenden, muss das Gateway signalisieren, z. B. in dem Paket-Header, für welche Pakete die Mod-2-Summe berechnet worden ist, so dass die Terminals ihre Mod-2-Summe mit den korrekten Paketen durchführen können.
Falls mehr als ein einziges Paket pro Terminal verloren ist, bedeutet dies, dass mehr als ein einziges ”CODED”-Paket gesendet werden muss, wobei jedes ”CODED”-Paket auf der Basis eines unterschiedlichen Sets von Paketen berechnet werden muss.
Zu Veranschaulichungszwecken wird das Verfahren gemäß der oben erwähnten Patentanmeldung im Kontext von 4–7 beschrieben. In 4 wird angenommen, dass vier Pakete, die als W, X, Y, Z bezeichnet sind, an die Terminals gesendet werden, die als A, B, C, D bezeichnet sind. Wie in 4 gezeigt, verliert aufgrund der auf dem Kanal auftretenden PER das Terminal C das Paket X, das Terminal B das Paket Y und das Terminal A das Paket Z.
Die Terminals geben nun an das Gateway eine Rückmeldung darüber, welche Pakete sie nicht korrekt empfangen konnten. Das Gateway führt nun keine einzelne Übertragung eines jeden der nicht empfangenen Pakete durch, sondern berechnet ein CODEC-Paket gemäß dem in 5 gezeigten Beispiel.
In diesem Beispiel ist der Inhalt der vier Pakete zufallsbedingt erzeugt worden, wobei 1 und 0 ein Bit repräsentieren. Wie hier gezeigt ist, wird die CODED-Meldung berechnet, indem eine Mod-2-Summe über sämtliche Pakete hinweg angewandt wird. Dieses Paket wird nun durch das Gateway übertragen, statt sämtliche 4 Pakete W–Z zu übertragen.
Das CODED-Paket wird dann an sämtlichen Terminals A–D empfangen. Der Dekodiervorgang ist exemplarisch für die Terminals D und B gezeigt. 6 zeigt den Dekodiervorgang für das Terminal D.
Wie 6 zeigt, wurde das Paket W nicht empfangen. Das Terminal berechnet nun die Mod-2-Summe sämtlicher korrekter empfangener Pakete (X–Z) und der zusätzlichen empfangenen Pakete ”CODED”. Das Resultat dieser Dekodieroperation ist das fehlende Paket W.
Das Dekodierbeispiel für das Terminal B ist in 7 gezeigt.
Wie ersichtlich ist, kann auch hier das fehlende Paket (Y) reproduziert werden, indem die Mod-2-Summe auf die empfangenen Pakete plus dem zusätzlichen CODED-Paket angewandt wird.
Der Neuübertragungsaufwand könnte somit von 4 Paketen auf 1 Paket reduziert werden, während die Zeit für einen korrekten Empfang des vollen Inhalts von 4 Paketübertragungszeiten (für das letzte Terminal) auf 1 Paketübertragungszeit reduziert wird.
Weitere Verfahren zum Übertragen fehlerhafter oder fehlender Daten in einem Broadcast-Scenario, bei denen redundante Datenpakete generiert werden, sind in den folgenden Druckschriften beschrieben: EP 0 898 820 B1 und XIAO, Xiao et al.: A Wireless Broadcasting Retransmission Approach Based an Network Coding, in 4th IEEE International Conference an Circuits and Systems for Communications (ICCSC 2008), Proceedings, 26.–28. Mai 2008, S. 782–786.
Es ist Aufgabe der vorliegenden Erfindung, ein Verfahren zum Übertragen von Daten bereitzustellen, bei dem die Wahl linear zu kombinierender Pakete in effizienter Weise durchgeführt wird.
Diese Aufgabe wird durch die Merkmale gemäß Anspruch 1 der Erfindung gelöst.
Bei einem Verfahren zum Übertragen von Daten von einem Broadcast- oder Multicast-Transmitter zu mehreren Receivern fordert jeder Receiver eine erneute Übertragung durch den Broadcast- oder Multicast-Transmitter an, falls ein Datenpaket fehlerhaft ist oder fehlt. Die Erfindung ist dadurch gekennzeichnet, dass zum Durchführen der erneuten Übertragung fehlerhafter oder fehlender Datenpakete mindestens ein redundantes Paket generiert wird. Jedes redundante Paket enthält ein fehlendes oder fehlerhaftes Datenpaket oder eine lineare Kombination eines derartigen fehlenden oder fehlerhaften Datenpakets mit einem korrekt empfangenen Datenpaket.
Gemäß der Erfindung wird das mindestens eine redundante Paket durch die folgenden Verfahrensschritte generiert:

a) Identifizieren des Datenpakets, für das die höchste Anzahl von Usern eine erneute Übertragung angefordert hat, wobei, falls die gleiche höchste Anzahl von Usern mehr als ein einziges Datenpaket angefordert hat, ein Datenpaket zufallsbedingt ausgewählt wird,
b) Identifizieren sämtlicher weiterer Datenpakete, die für sämtliche User, welche eine erneute Übertragung des Datenpakets mit der höchsten Anzahl von Neuübertragungs-Requests angefordert haben, verlorengegangen sind, und Markieren dieser weiteren Datenpakete als tabu,
c) Generieren des ersten redundanten Datenpakets als lineare Kombination des Datenpakets mit der höchsten Anzahl von Neuübertragungs-Requests und sämtlicher weiterer nicht als tabu markierter Datenpakete,
d) Identifizieren des Datenpakets, für das die zweithöchste Anzahl von Usern eine erneute Übertragung angefordert hat,
e) Identifizieren sämtlicher weiterer Datenpakete, die für sämtliche User, welche eine erneute Übertragung des Datenpakets mit der zweithöchsten Anzahl von Neuübertragungs-Requests angefordert haben, verlorengegangen sind, und Markieren dieser weiteren Datenpakete als tabu,
f) Generieren des zweiten redundanten Datenpakets als lineare Kombination des Datenpakets mit der zweithöchsten Anzahl von Neuübertragungs-Requests und sämtlicher weiterer nicht als tabu markierter Datenpakete,
g) Generieren der weiteren redundanten Datenpakete durch jeweiliges Wiederholen der Verfahrensschritte d–f, bis sämtliche fehlerhaften oder fehlenden Datenpakete auf der Basis der redundanten Pakete rückgewonnen werden können.

Es ist zu beachten, dass die Verfahrensschritte d–f auch an einem zweiten Datenpaket, das die gleiche höchste Anzahl von Neuübertragungs-Requests wie das in dem Verfahrensschritt a identifizierte Datenpaket aufweist, vorgenommen werden können, falls diese beiden Datenpakete die gleiche höchste Anzahl von Neuübertragungs-Requests haben und das erste Datenpaket entsprechend dem Verfahrensschritt a zufallsbedingt gewählt worden ist. Selbstverständlich gilt dies auch für die weiteren Datenpakete mit der gleichen höchsten Anzahl (zweithöchste Anzahl, dritthöchste Anzahl, ...) von Neuübertragungs-Requests.
Ein redundantes Datenpaket kann nur ein einziges fehlendes oder fehlerhaftes Datenpaket sein, falls sämtliche weiteren Datenpakete gemäß dem Verfahrensschritt b als tabu markiert sind, was bedeutet, dass sie nicht als Teile einer linearen Kombination zum Erzeugen eines redundanten Datenpakets verwendet werden können. Falls ein oder mehrere weitere Datenpakete nicht als tabu markiert sind, können sie für die lineare Kombination verwendet werden, um das redundante Datenpaket zu erzeugen. Somit kann das redundante Datenpaket ein fehlendes oder fehlerhaftes Datenpaket oder eine lineare Kombination eines derartigen fehlenden oder fehlerhaften Datenpakets mit einem Datenpaket aufweisen, das korrekt von einem der User empfangen wurde.
Folglich bietet das erfindungsgemäße Verfahren die Möglichkeit, das Neuübertragungs-Overhead und dadurch die Neuübertragungs-Verzögerung und das Neuübertragungsverzögerungs-Jitter zu reduzieren. Es ist keine erneute Übertragung jedes fehlenden Pakets erforderlich. Stattdessen wird ein kodiertes Paket berechnet, nur dieses kodierte Paket wird erneut übertragen.
Das Verhältnis zwischen den in der linearen Kombination involvierten Quell-Paketen und den resultierenden redundanten Paketen kann als Paritätsgleichung aufgefasst werden. Nimmt man den Fall an, dass ein generischer User die erneute Übertragung eines in einer Paritätsgleichung involvierten Pakets angefordert hat, dann wäre dieser User in der Lage, das fehlende Paket durch Bilden einer bit-weisen Summe des zugehörigen redundanten Pakets und der in derselben Gleichung involvierten anderen (komplementären) Quell-Pakete rückzugewinnen. Der oben beschriebene Vorgang wird dann und nur dann erfolgreich sein, wenn der User sämtliche komplementären Pakete zusammen mit dem redundanten Paket besitzt. Die aufgrund dieses Ansatzes eingetragene Latenz ergibt sich aus dem maximalen (zeitlichen) Abstand zwischen einem in einer Gleichung involvierten Paket und dem zugehörigen Redundanzpaket. Um die Latenz unter Kontrolle zu halten, wird somit vorzugsweise das Konzept des Combining Window eingeführt. Ein Combining Window repräsentiert den Satz von L Paketen, über die hinweg eine Paritätsprüfungsgleichung erstellt werden kann. Die Zeitachse ist somit in Blöcke von L Paketen unterteilt.
Mit {ρ_K}, k = 1 ... L, ist der Satz von L Quell-Paketen innerhalb eines Combining Window bezeichnet. Ferner ist durch ψ der Satz von Quell-Paketen definiert, die dem i-ten User in dem Fenster verlorengegangen sind. Die Anzahl der für den i-ten User verlorenen Pakete ist q_i = |ψ_i|.
Mit {ϕ_k}, k = 1 ... R, ist der Satz redundanter Pakete bezeichnet, die gebildet werden, um die in dem Combining Window verlorenen Quell-Pakete rückzugewinnen. Jedes redundante Paket wird als (bit-weise) lineare Kombination der Quell-Pakete erhalten, d. h. ϕ_k = a_k,1ρ₁ ⊕ a_k,2ρ₂ ⊕ a_k,3ρ₃ ⊕ ... ⊕ a_k,Lρ_L = ⊕ L / j = 1a_k,jρ_j, with a_k,j ∈ {0, 1}. R ergibt ein Maß des Neuübertragungs-Overhead, da es die Anzahl redundanter Pakete repräsentiert, die für ein Combining Window erzeugt werden. Der i-te User muss das System binärer Gleichungen Aρ = ϕ lösen, d. h.
und zwar mit Unbekannten in Y_i. Dies kann erreicht werden, falls und nur falls Rang A = q. Somit kann R nach unten hin begrenzt werden als R ≥ max_i{q_i}. (2)
Es ist bevorzugt, dass fehlende oder fehlerhafte Datenpakete auf der Seite des Users aus dem Satz redundanter Pakete durch Rücksubstitution statt durch Verwendung Gaußscher Eliminations-Algorithmen rückgewonnen werden.
Gemäß einer bevorzugten Ausführungsform wird ein Fehlerzählvektor e = {e₁, e₂, ..., e_L} erzeugt, wobei e_i die Anzahl der User bezeichnet, denen das i-te Paket verlorengegangen ist, wobei 0 ≤ e_i ≤ N.
Ferner wird vorzugsweise ein Hilfsvektor t = {t₁, t₂, ..., t_L} erzeugt, wobei jedes Element von t einen Wert innerhalb des Satzes von Flags (T, M, K) annimmt, wobei ein Element t_i auf K (known) gesetzt wird, falls das Datenpaket ρ_i seitens sämtlicher User empfangen worden ist, d. h. falls e_i = 0, und sollte dies nicht der Fall sein, wird t_i auf M (missing) gesetzt.
Zum Erzeugen eines redundanten Pakets wird t_i auf T (tabu) gesetzt, falls für das Datenpaket ρ_i eine Neuübertragung seitens irgendeines der User angefordert worden ist, die das rückzugewinnende Datenpaket vermissen.
Es wird nun ein bevorzugter Algorithmus für die Wahl des Neuübertragungs-Musters eingeführt, der es möglich macht, dass jeder User das Gleichungssystem (1) mit Hilfe einfacher Rücksubstitutionen löst, statt smarte Gaußsche Eliminations-Algorithmen zu verwenden. Nach dem Durchführen der oben erwähnten Verfahrensschritte wird der Redundanzpaket-Index k auf 1 initialisiert. Die Erstellung der redundanten Datenpakete umfasst die folgenden Verfahrensschritte:
Wiederholen von (1–5), bis t_i = K, ∀i = 1 ... L:

1. Für j = 1 ... L, Setzen a_k,j = 0.
2. Wiederholen von (a–c), bis t_i ≠ M, ∀i = 1 ... L: a. Ermitteln l = argmax_i{e_i} unter der Beschränkung t_i = M. b. Setzen a_k,1 = 1, e_i = 0 und t_i = K. c. Für j = 1 ... N, falls ρ_i ∊ Ψ_j, für sämtliche i, vorausgesetzt ρ_i ∊ Ψ_j und t_i = M, Setzen t_i = T (tabu).
3. Errechnen des k-ten Redundanzpakets als φ_k = ⊕ L / j = 1a_k,jρ_j.
4. Für sämtliche ∀i = 1 ... L, falls t_i = T, Setzen t_i = M.
5. Inkrementieren von k um 1.

Der Algorithmus wird gestoppt, sobald sämtliche Elemente von t als K markiert sind, d. h. falls sämtliche verlorenen Pakete aus dem Satz redundanter Pakete rückgewonnen werden können.
Im Folgenden werden bevorzugte Ausführungsformen der Erfindung im Zusammenhang mit den Figuren eingehender erläutert.
1–7 zeigen aus dem Stand der Technik bekannte Szenarien zum Übertragen von Daten in Broadcast-Anwendungen.
8 zeigt ein exemplarisches Szenario des Verfahrens gemäß der Erfindung.
9 und 10 zeigen Leistungs-Auswertungen, die auf dem Verfahren gemäß der Erfindung basieren.
1–7 wurden bereits in der Einführung der vorliegenden Anmeldung im Kontext des bekannten Standes der Technik beschrieben.
Gemäß dem in 8 gezeigten Beispiel wird anfangs der Vektor e auf {1, 3, 2, 2, 1, 1} gesetzt, während t = {M, M, M, M, M, M}. Das Verfahren beginnt mit der Erstellung des ersten redundanten Pakets (k = 1). Das zweite Paket ist dasjenige mit dem höchsten Wert von e (zu prüfen ist, dass argmax_i{e_i} = 2). Der Vektor e wird modifiziert als {1, 0, 2, 2, 1, 1}. Das zweite Paket ging für die User 1, 2 und 3 verloren. Die anderen für diese User verlorengegangen Pakete müssen als tabu markiert werden. Folglich ist t = {T, K, T, T, T, T}. Somit gilt ϕ₁ = ρ₂. Für das zweite redundante Paket (k = 2) muss t auf t = {M, K, M, M, M, M} rückgesetzt werden. Nun existieren zwei Pakete, bei denen e den höchsten Wert hat: ρ₃ und ρ₄. Unter der Annahme, dass das erste gewählt wird, wird e modifiziert als {1, 0, 0, 2, 1, 1} und t = {M, K, K, M, T, M}. Bei der nächsten Iteration wird ρ₄ gewählt als (t₄ = M und argmax_i{e_i} = 4). Folglich wird e zu {1, 0, 0, 0, 1, 1} und t = {T, K, K, K, T, T}. Das zweite redundante Paket ist somit ϕ₂ = ρ₃ ⊕ ρ₄. Bei Fortsetzung des Vorgangs sind dann die anderen redundanten Pakete ϕ₃ = ρ₁ ⊕ ρ₅ und ϕ₄ = ρ₆. Bemerkenswerterweise arbeitet bei diesem Beispiel der vorgeschlagene Algorithmus optimal, d. h. bei ihm wird die geringstmögliche Anzahl von Neuübertragungen (R = 4) gemäß (2) erreicht.
Als nächstes wird eine Leistungsauswertung des vorgeschlagenen C-ARQ-Schemas aufgeführt. Zunächst wird auf der Basis von (2) eine untere Begrenzung für die mittlere Anzahl von Neuübertragungen abgeleitet. Mit Q_i ist die zufallsbedingte Variable (r. v. random variable) für die Anzahl von Paketen bezeichnet, die für den i-ten User innerhalb eines Fensters verlorengegangen sind. Die r. v.-bezogene Anzahl erforderlicher Neuübertragungen ist definiert durch R = max{Q_i}. Die mittlere Anzahl von Neuübertragungen für ein ideales Schema, das (2) mit Gleichheit erfüllt, beträgt
wobei Pr{
= R} die Wahrscheinlichkeit ist, dass der schlechteste User R Paketverluste erfährt. Anzumerken ist, dass (3) eine untere Begrenzung für die mittlere Anzahl von Neuübertragungen ist, die von irgendeiner Neuübertragungstechnik verlangt wird. Im folgenden wird auf den Fall eingegangen, dass die Paketverluste zeitlich sowie unter den Usern unkorreliert sind. Ferner wird angenommen, dass jeder User die gleiche Paketverlust-Wahrscheinlichkeit e erfährt. Der Term Pr{
= R} kann ausgedrückt werden als Pr {
= R} = Pr{Q_i < R + 1, ∀i} – Pr{Q_i < R, ∀i}, was in Anbetracht der User-Unabhängigkeit gekürzt wird auf Pr{⌈ = γ} = [Pr{Q_i < R + 1}]^N – [Pr{Q_i < R}]^N, wobei Pr{Q_i < R} nicht von i abhängt, d. h.
Es sei der Fall des S-ARQ angenommen. Die Wahrscheinlichkeit, dass ein Paket neu übertragen werden muss, ist gegeben durch P_SARQ = 1 – (1 – ε)^N. Die mittlere Anzahl von Neuübertragungen für ein Fenster ist
In 9 ist die mittlere Anzahl von Neuübertragungen pro Combining Window (normalisiert auf L) als Funktion der Fenstergröße L dargestellt. Das Schaubild gibt die Leistung gemäß (3) und (4) an, unter Zugrundelegung von N-100 Usern und einer Paketverlustratenwahrscheinlichkeit ε = 10^–2. Simulationsergebnisse für den Algorithmus A werden ebenfalls angegeben.
Eine starke Reduzierung der Anzahl von Neuübertragungen wurde für das C-ARQ beobachtet. Bei L = 800 konnte auf nahezu 97% der von dem S-ARQ verlangten Neuübertragungen verzichtet werden. Anzumerken ist, dass sich der Algorithmus A eng an die Grenze von (3) annähert. Die Leistung des C-ARQ tendiert zu einer Sättigung bei großen Werten von L, so dass es zweckmäßig ist, L im Bereich von 100–200 zu halten, um die System-Latenz zu begrenzen.
In 10 ist die durchschnittliche Anzahl von Neuübertragungen pro Fenster (normalisiert auf L) als Funktion der Paketverlustwahrscheinlichkeit ε für den Fall von L = 100 und N = 100 gezeigt. Das Schaubild zeigt die Leistungsfähigkeit gemäß (3) und die Simulationsergebnisse für den Algorithmus A. Wiederum reicht der vorgeschlagene Algorithmus fast an die Begrenzung von (3) heran. Der Vorteil der vorgeschlagenen Technik ist bei moderaten bis hohen Paketverlustraten (d. h., ε > 10^–3) ziemlich offensichtlich, während bei niedrigen Paketverlustraten die Leistungsfähigkeiten des C-ARQ und des S-ARQ dazu tendieren, zu konvergieren. (Wenn e sehr klein ist, wird meistens nur ein einziges Paket in einem Combining Window verloren, und sowohl das C-ARQ als auch das S-ARQ führen eine einzelne Neuübertragung durch.
Das Verfahren gemäß der Erfindung ist für sämtliche Typen kommerzieller drahtloser Transmissionstypen anwendbar. Es hat sich erwiesen, dass das Verfahren das Neuübertragungs-Overhead reduziert, was zu niedrigen Kosten führt und den Service verbessert, da sich die Verzögerung und das Verzögerungs-Jitter reduzieren. Dies ist von besonderem Interesse für kommerzielle Kunden, die Echzeit-Anwendungen wie z. B. Video-Streaming oder Audio-Streaming verwenden.

Claims

Verfahren zum Übertragen von Daten von einem Broadcast- oder Multicast-Transmitter zu mehreren Receivern, bei dem jeder Receiver eine erneute Übertragung durch den Broadcast-Transmitter verlangt, falls ein Datenpaket fehlerhaft ist oder fehlt, wobei zum Durchführen der erneuten Übertragung fehlerhafter oder fehlender Datenpakete mindestens ein redundantes Datenpaket generiert wird, jedes redundante Datenpaket ein fehlendes oder fehlerhaftes Datenpaket oder eine lineare Kombination eines derartigen fehlenden oder fehlerhaften Datenpakets mit einem korrekt empfangenen Datenpaket enthält, dadurch gekennzeichnet, dass das mindestens eine redundante Datenpaket durch die folgenden Verfahrensschritte generiert wird: a) Identifizieren des Datenpakets, für das die höchste Anzahl von Usern eine erneute Übertragung angefordert hat, wobei, falls die gleiche höchste Anzahl von Usern mehr als ein einziges Datenpaket angefordert hat, ein Datenpaket zufallsbedingt ausgewählt wird, b) Identifizieren sämtlicher weiterer Datenpakete, die für sämtliche User, welche eine erneute Übertragung des Datenpakets mit der höchsten Anzahl von Neuübertragungs-Requests angefordert haben, verlorengegangen sind, und Markieren dieser weiteren Datenpakete als tabu, c) Generieren des ersten redundanten Datenpakets als lineare Kombination des Datenpakets mit der höchsten Anzahl von Neuübertragungs-Requests und sämtlicher weiterer nicht als tabu markierter Datenpakete, d) Identifizieren des Datenpakets, für das die zweithöchste Anzahl von Usern eine erneute Übertragung angefordert hat, e) Identifizieren sämtlicher weiterer Datenpakete, die für sämtliche User, welche eine erneute Übertragung des Datenpakets mit der zweithöchsten Anzahl von Neuübertragungs-Requests angefordert haben, verlorengegangen sind, und Markieren dieser weiteren Datenpakete als tabu, f) Generieren des zweiten redundanten Datenpakets als lineare Kombination des Datenpakets mit der zweithöchsten Anzahl von Neuübertragungs-Requests und sämtlicher weiterer nicht als tabu markierter Datenpakete, g) Generieren der weiteren redundanten Datenpakete durch jeweiliges Wiederholen der Verfahrensschritte d–f, bis sämtliche fehlerhaften oder fehlenden Datenpakete auf der Basis der redundanten Datenpakete rückgewonnen werden können.
Verfahren zum Übertragen von Daten nach Anspruch 1, bei dem fehlende oder fehlerhafte Datenpakete auf der Seite des Users aus dem Satz redundanter Datenpakete durch Rücksubstitution statt durch Verwendung Gaußscher Eliminations-Algorithmen rückgewonnen werden können.
Verfahren zum Übertragen von Daten nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass ein Fehlerzählvektor e = {e₁, e₂, ..., e_L} erzeugt wird, wobei e_i die Anzahl der User bezeichnet, denen das i-te Datenpaket verlorengegangen ist, wobei 0 ≤ e_i ≤ N.
Verfahren zum Übertragen von Daten nach Anspruch 3, dadurch gekennzeichnet, dass ein Hilfsvektor t = {t₁, t₂, ..., t_L} erzeugt wird, wobei jedes Element von t einen Wert innerhalb des Satzes von Flags (T, M, K) annimmt, wobei ein Element t_i auf K (known) gesetzt wird, falls das Datenpaket ρ_i seitens sämtlicher User empfangen worden ist, d. h. falls e_i = 0, und falls dies nicht der Fall ist, t_i auf M (missing) gesetzt wird.
Verfahren zum Übertragen von Daten nach Anspruch 4, dadurch gekennzeichnet, dass, um ein redundantes Datenpaket φ_K zu erzeugen, t_i auf T (tabu) gesetzt wird, falls für das Datenpaket ρ_i eine Neuübertragung seitens irgendeines der User angefordert worden ist, die das rückzugewinnende Datenpaket vermissen.
Verfahren zum Übertragen von Daten nach einem der Ansprüche 1–5, dadurch gekennzeichnet, dass das Erzeugen der redundanten Datenpakete die folgenden Verfahrensschritte umfasst: Wiederholen von (1–5), bis t_i = K, ∀i = 1 ... L: 1. Für j = 1...L, Setzen a_k,j = 0, 2. Wiederholen von (a–c), bis t_i ≠ M, ∀i = 1 ... L: a. Ermitteln l = argmax_i{e_i} unter der Beschränkung t_i = M, b. Setzen a_k,1 = 1, e_i = 0 und t_i = K, c. Für j = 1 ... N, falls ρ_i ∊ Ψ_j, für sämtliche i, vorausgesetzt, dass ρ_i ∊ Ψ_j und t_i = M, Setzen t_i = T (tabu), 3. Errechnen des k-ten Redundanzpakets als φ_k = ⊕ L / j = 1a_k,jρ_j, 4. Für sämtliche ∀i = 1 ... L, falls t_i = T, Setzen t_i = M, 5. Inkrementieren von k um 1, wobei der Algorithmus gestoppt wird, wenn sämtliche Elemente von t als K (known) markiert sind, d. h. falls sämtliche fehlenden oder fehlerhaften Pakete auf der Basis der redundanten Datenpakete rückgewonnen werden können.