DE60320082T2

DE60320082T2 - Gerät und Verfahren zur dynamischen Zuteilung von Mitteln in einem interaktiven multimedia Satellitenkommunikationssystem

Info

Publication number: DE60320082T2
Application number: DE60320082T
Authority: DE
Inventors: Ki-Dong Lee; Yong-Hoon Cho; Ho-Jin Lee
Original assignee: Electronics and Telecommunications Research Institute ETRI
Current assignee: Electronics and Telecommunications Research Institute ETRI
Priority date: 2002-12-11
Filing date: 2003-08-29
Publication date: 2009-06-04
Anticipated expiration: 2023-08-30
Also published as: ATE391363T1; KR100565896B1; EP1429473A3; EP1429473B1; US20040125784A1; US7346069B2; DE60320082D1; KR20040051007A; EP1429473A2

Description

GEBIET DER ERFINDUNG
Die vorliegende Erfindung betrifft eine Vorrichtung und ein Verfahren zur Ressourcenzuteilung in einem interaktiven Satellitenmultimediasystem und insbesondere eine Vorrichtung und ein Verfahren zum dynamischen Zuteilen von Ressourcen zum Zuweisen eines Zeitschlitzes in einem Rückkanal im Mehrfrequenz-Zeitmultiplexverfahren (Multi-Frequency Time Division Multiple Access, MF-TDMA), um einen maximalen Durchsatz zu erhalten.
BESCHREIBUNG DES STANDES DER TECHNIK
Es wurden verschiedene Vorrichtungen und Verfahren zur Ressourcenzuteilung in einem Zeitmultiplexverfahren (TDMA) entwickelt, wie etwa ein Zeitschlitzzuweisungsverfahren für Verbindungen zwischen Satelliten (Inter-Satellite Link, ISL) und ein Ressourcenzuteilungsverfahren im TDMA in einem Mobilfunkt-Kommunikationssystem.
Dabei stellt eine Ressource eine Frequenzbandbreite dar, die für eine Rückverbindung verwendet wird, bei der es sich um eine Verbindung zwischen RCST-Endgeräten (Return Channel Satellite Terminal) und einem Satelliten handelt. Das heißt, die Ressource ist eine Gruppe von Zeitschlitzen in der Rückverbindung im Mehrfrequenz-Zeitmultiplexverfahren MF-TDMA. Im MF-TDMA werden die Ressourcen als eine Frame-Einheit oder eine Superframe-Einheit zugeteilt. Ein Frame weist mehrere Zeitschlitze auf und ein Superframe weist mehrere Frames auf.
Ein interaktives Satellitenmultimediasystem ist ein Satellitennetzwerk mit einer Erdstation (HUB) und mehreren Endgeräten, die RCST-Endgeräte genannt werden. Die Erdstation (HUB) empfängt über Satelliten eine Dienstanforderung und stellt über Satelliten Dienste für die (RCST-)Endgeräte bereit, indem sie auf die Anforderung reagiert. Da die Funkressourcen im Vergleich zu landgestützten Mobilfunk-Kommunikationssystemen sehr kostspielig sind, besteht im Satellitenkommunikationssystem eine der wesentlichsten Aufgaben darin, den Verbindungsdurchsatz unter Verwendung der begrenzten verfügbaren Ressourcen zu maximieren.
Besonders im interaktiven Satellitenkommunikationssystem mit zentraler Ressourcenverwaltungsfunktion in der Erdstation (HUB) muss die Ressource unter Berücksichtigung der Umlaufzeit (Round-Trip Time, RTT) zugewiesen werden, die für die Anforderung der Ressource vom (RCST-)Endgerät an die Erdstation (HUB) und das Empfangen einer Zuweisungsebene von der Erdstation (HUB) an die Endgerätstation (RCST) verbraucht wird. In Hinsicht auf die Ressourcenzuteilung unter Berücksichtigung der RTT unterscheidet sich das Ressourcenzuteilungsverfahren im interaktiven Satellitenkommunikationssystem von der herkömmlichen Technik zur Ressourcenzuteilung in der Satellitenkommunikation.
Darüber hinaus unterscheidet es sich im Vergleich zu einer Zeitschlitzzuweisungsplanung und Paketzuweisungsplanung eines Mobilkommunikationssystems auch in Hinsicht auf die Verzögerung der Übertragung und darin, dass die Frequenzbandbreite vergleichsweise breitbandig ist. Im Breitband-TDMA ist die Länge jedes Zeitschlitzes gewöhnlich viel kürzer als in einem Schmal- oder Mittelband-TDMA. Im Ergebnis verkürzt sich die Planungsperiode oder die Anzahl der Zeitschlitze pro Planungsperiode steigt, was beides eine schnelle Zeitschlitzplanung erschwert, besonders in einem interaktiven Satellitennetzwerk mit einer spezifischen Umlaufzeit zwischen Kapazitätsanfrage und -zuteilung.
Infolgedessen wird eine so kurze Zeitplanungsperiode wie möglich bevorzugt, um die negative Auswirkung der RTT zu minimieren.
Im interaktiven Satellitenmultimediasystem ist deshalb ein Verfahren zum schnellen und dynamischen Ausgeben eines Ressourcenzuteilungsplanes als Reaktion auf Kapazitätenanfragen von mehreren (RCST-)Endgeräten äußerst wichtig.
Ein Beispiel eines Ressourcenzuteilungsplanes in einem Satellitenkommunikationssystem ist in der US-Patentschrift 5,812,545 beschrieben. Dieses System verwendet effizient TDMA-Vermittlungstechnologie, um über eine Satellitenverbindung Daten in Burstform zwischen einer Anzahl von Endgeräten auf der Erde zu übertragen. Jedes der Endgeräte umfasst einen programmierbaren Rechner (Programmable Computing Device, PCD) für die Kommunikation in einem vollständig vermaschten Netzwerk, die auf Daten in Form von TDMA-Frames beruht. Der PCD arbeitet als Vermittlungsstelle, die Daten mit Hilfe eines Fragmentierungsprotokolls zu Bursts priorisiert. Die Vermittlungsstelle organisiert Bursts in mindestens einem von mehreren Schlitzen, die gemäß einem Burstplan einen TDMA-Frame bilden. Jedes Endgerät hat Zugang zu einer garantierten Anzahl von Schlitzen. Die Zuteilung der verbleibenden Schlitze auf die Endgeräte variiert dynamisch, um die Burstübertragungsraten der Endgeräte nach Bedarf zu erhöhen oder zu verringern.
KURZDARSTELLUNG DER ERFINDUNG
Somit ist es eine Aufgabe der vorliegenden Erfindung, eine Vorrichtung und ein Verfahren zum schnellen Erzeugen eines Planes zur dynamischen Ressourcenzuteilung bereitzustellen, um den Durchsatz in einer auf MF-TDMA basierenden Rückverbindung eines interaktiven Multimedianetzwerkes zu maximieren.
Gemäß einem Aspekt der vorliegenden Erfindung ist eine Vorrichtung zum dynamischen Zuteilen von Ressourcen in einem interaktiven Satellitenmultimediasystem bereitgestellt, die Folgendes umfasst: eine Erfassungseinheit für Ressourcenanforderungen zum Summieren einer angeforderten Ressourcenmenge während einer Superframe-Periode, die jedem der Endgeräte entspricht, eine Verarbeitungseinheit für Ressourcenanforderungsmengen zum Dividieren einer summierten angeforderten Ressourcenmenge durch die Anzahl der Framepaare in einem Superframe und Speichern einer Summe aus einem Ergebnis der Division und aus einer Aufrundung des Divisionsrestes auf die nächste Ganzzahl als eine Anforderungsmenge für das entsprechende Endgerät, und eine Ressourcenzuteilungseinheit zum Bestimmen eines Zeitschlitzes, der jedem der Endgeräte entsprechend einem Framepaar auf der Basis einer optimalen Zuteilungsmenge zugeteilt wird, welche auf der Basis der angeforderten Menge von der Anforderungsmengenverarbeitungseinheit bestimmt wird.
Gemäß einem Aspekt der vorliegenden Erfindung ist außerdem ein Verfahren zum dynamischen Zuteilen von Ressourcen in einem interaktiven Satellitenmultimediasystem bereitgestellt, das folgende Schritte umfasst: a) Summieren einer Anforderungsmenge von Ressourcen während einer Superframe-Periode, die jedem der Endgeräte entspricht, b) Dividieren einer summierten angeforderten Ressourcenmenge durch die Anzahl der in einem Superframe enthaltenen Framepaare und Speichern einer Summe aus einem Ergebnis der Division und aus einer Aufrundung des Divisionsrestes auf die nächste Ganzzahl als eine Anforderungsmenge und c) Bestimmen einer optimalen Zuteilungsmenge auf der Basis der Ressourcenanforderungsmenge und Bestimmen eines Zeitschlitzes, der jedem der Endgeräte auf der Basis der optimalen Zuteilungsmenge zugeteilt werden soll.
Gemäß einem Aspekt der vorliegenden Erfindung ist außerdem ein computerlesbares Aufzeichnungsmedium bereitgestellt, in dem Befehle zum Ausführen eines Verfahrens zum aktiven Zuteilen von Ressourcen in einem bidirektionalen Satellitenmultimediasystem gespeichert sind und das folgende Funktionen aufweist: a) Summieren einer Ressourcenanforderungsmenge, die jedem der Endgeräte entspricht, während einer Superframe-Periode, b) Dividieren einer summierten angeforderten Ressourcenmenge durch die Anzahl der in einem Superframe enthaltenen Framepaare und Speichern einer Summe aus einem Ergebnis der Division und aus einer Aufrundung des Divisionsrestes auf die nächste Ganzzahl als eine Ressourcenanforderungsmenge und c) Bestimmen einer optimalen Zuteilungsmenge auf der Basis der Ressourcenanforderungsmenge und Bestimmen eines Zeitschlitzes, der jedem der Endgeräte auf der Basis der optimalen Zuteilungsmenge zugeteilt werden soll.
KURZBESCHREIBUNG DER ZEICHNUNG(EN)
Das Vorangehende sowie weitere Aufgaben und Merkmale der vorliegenden Erfindung werden aus der folgenden Beschreibung der bevorzugten Ausführungsformen ersichtlich, die im Zusammenhang mit den dazugehörigen Zeichnungen zu lesen ist. Es zeigen:
1 ein Diagramm, das ein herkömmliches interaktives Satellitenmultimediasystem darstellt,
2 ein Blockdiagramm, das eine Vorrichtung zur dynamischen Ressourcenzuteilung gemäß einer bevorzugten Ausführungsform der vorliegenden Erfindung abbildet,
3 ein Ablaufdiagramm zur Erklärung eines Verfahrens zur dynamischen Ressourcenzuteilung gemäß einer bevorzugten Ausführungsform der vorliegenden Erfindung,
4 ein Diagramm, das eine Struktur eines Superframes gemäß einer bevorzugten Ausführungsform der vorliegenden Erfindung darstellt, und
5A bis 5D die Ergebnisse einer umfassenden Simulation einer bevorzugten Ausführungsform der vorliegenden Erfindung.
DETAILLIERTE BESCHREIBUNG DER ERFINDUNG
Weitere Aufgaben und Aspekte der Erfindung werden aus der folgenden Beschreibung der Ausführungsformen in Bezug auf die beigefügten Zeichnungen ersichtlich, die hierin im Folgenden dargelegt ist.
1 ist eine Ansicht, die ein herkömmliches interaktives Satellitenmultimediasystem darstellt.
Das herkömmliche interaktive Satellitenmultimediasystem in 1 weist mehrere Endgeräte 11, einen Satelliten 12 und eine Host-Station (HUB) 13 auf. Die Endgeräte 11 senden über den Satelliten 12 eine Ressourcenanforderung an die Host-Station 13. Die Host-Station 13 stellt über den Satelliten 12 Dienste für die Endgeräte 13 bereit. Im interaktiven Satellitenmultimediasystem ist es eine der wichtigsten Aufgaben, einen Durchsatz entsprechend dem Benutzerverkehr zu maximieren.
In 1 sind nur eine Host-Station und ein Satellit dargestellt; es sind jedoch auch mehrere Host-Stationen und Satelliten in dem Satellitenkommunikationsnetzwerk möglich.
Die mehreren Endgeräte 11 fordern gleichzeitig Ressourcen von der Host-Station 13 an und jedes der Endgeräte verwendet nur die zugeteilte Ressource (Zeitschlitz).
Die Host-Station 13 empfängt und analysiert Ressourcenanforderungen von den mehreren Endgeräten und bestimmt eine entsprechende Anzahl von Zeitschlitzen, die gemäß der Analyse jedem der Endgeräte zugewiesen werden.
Das Bestimmungsergebnis der Host-Station wird jedem der Endgeräte über den Satelliten 12 gemeldet.
Die Host-Station umfasst einen Algorithmus zum Berechnen eines Planes zur dynamischen Ressourcenzuteilung, um den Durchsatz einer Rückverbindung zwischen dem Endgerät 11 und dem Satelliten 12 zu maximieren. Die Host-Station empfängt Frequenzressourcenanforderungen von den Endgeräten 11 und berechnet schnell den Plan zur dynamischen Ressourcenzuteilung. Hierbei ist eine angeforderte Frequenzressource eine Frequenzbandbreite, die für eine Rückverbindung zwischen dem Endgerät 11 und dem Satelliten 12 verwendet wird. Das heißt, die angeforderte Frequenzressource ist eine Gruppe aus einer bestimmten Anzahl von Zeitschlitzen in der Rückverbindung auf MF-TDMA-Basis. Zum schnellen Berechnen eines Planes zur Zuteilung von Ressourcen für jeden der Superframes muss die vorliegende Erfindung die rechnerische Effizienz der Zeitschlitzplanung durch Einsatz der so genannten Problemreduktions- und Dekompositionstechnik verbessern, wobei im Vorliegenden getrennt betrachtet wird, wie eine Zuteilungsmenge entsprechend jedem der Endgeräte bestimmt wird und wie ein Zeitschlitz zur Zuteilung an jedes der Endgeräte ausgewählt wird.
Durch die Verwendung eines Problemreduktionsverfahrens können der Berechnungsumfang verringert und die Geschwindigkeit der Berechnung erhöht werden.
2 ist ein Diagramm, das einen dynamischen Ressourcenzuteiler zum dynamischen Zuteilen von Ressourcen gemäß einer bevorzugten Ausführungsform der vorliegenden Erfindung zeigt.
Der dynamische Ressourcenzuteiler in der Host-Station (HUB) in 2 umfasst ein Erfassungsmittel für Ressourcenanforderungen 21, einen Ressourcenanforderungsmengenprozessor 22 zum Berechnen einer Ressourcenzuteilungsmenge durch Dividieren der erfassten Anforderungsmenge durch die Anzahl der Framepaare und Aufrunden des Ergebnisses der Division auf die nächste Ganzzahl, ein Bestimmungsmittel der Ressourcenzuteilungsmenge 24, einen Ressourcenzuteilungsplaner 25 und ein Kopiermittel des Ressourcenzuteilungsplaners 26.
Das heißt, zum Planen der Ressource des ersten Framepaares bestimmt das Bestimmungsmittel der Ressourcenzuteilungsmenge 24 die optimale Menge für jedes Framepaar unter Berücksichtigung der Anzahl der Frames, die jedem der Endgeräte 11 zugeteilt sind. Der Ressourcenzuteilungsplaner 25 erstellt einen Plan auf der Basis der optimalen Zuteilungsmenge und wählt eines der Endgeräte aus, dem die zugeteilte Ressource zugewiesen werden soll. Das Kopiermittel des Ressourcenzuteilungsplaners 26 kopiert den Zuteilungsplan des ersten Framepaares auf die verbleibenden Framepaare in demselben Superframe.
In 2 enthält der für die Host-Station 13 verwendete dynamische Ressourcenzuteiler ein Erfassungsmittel für Ressourcenanforderungen 21 zum Summieren einer Ressourcenanforderungsmenge während einer Superframe-Periode, einen Ressourcenanforderungsmengenprozessor 22 zum Berechnen einer angeforderten Ressourcenmenge durch Dividieren der erfassten Anforderungsmenge durch die Anzahl der Framepaare in einem Superframe und Addieren des Ergebnisses der Division und des Aufrundens des Divisionsrestes auf die nächste Ganzzahl und einen Ressourcenzuteiler 23 zum Bestimmen einer optimalen Zuteilungsmenge auf der Basis der Anforderungsmenge vom Anforderungsmengenprozessor 22 und zum Bestimmen eines Zeitschlitzes, der jedem der Endgeräte 11 entsprechend den Framepaares auf der Basis der optimalen Zuteilungsmenge zugewiesen wird.
Der Ressourcenzuteiler 23 weist ein Bestimmungsmittel der Ressourcenzuteilungsmenge 24 zum Bestimmen der optimalen Menge auf der Basis der im Ressourcenanforderungsprozessor 22 verarbeiteten Anforderungsmenge auf, einen Ressourcenzuteilungsplaner 25 zum Auswählen und Bestimmen eines der RCST-Endgeräte 11, dem auf der Basis der optimalen Zuteilungsmenge ein Zeitschlitz zugewiesen werden soll, der im ersten Framepaar enthalten ist, und ein Kopiermittel des Ressourcenzuteilungsplaners 26 zum Kopieren eines Zeitschlitzzuteilungsplanes des ersten Framepaares auf die im selben Superframe verbleibenden Frampaare.
Das Erfassungsmittel für Ressourcenanforderungen 21 summiert eine angeforderte Ressourcenmenge, die während einer Superframe-Periode entsprechend jedem RCST-Endgerät erzeugt wird, und meldet diese an den Ressourcenanforderungsmengenprozessor 22. Nach der Meldung wird die summierte Menge auf 0 gesetzt und das Erfassungsmittel für Ressourcenanforderungen 21 beginnt die im nächsten Superframe angeforderte Ressourcenmenge zu summieren.
Der Ressourcenanforderungsmengenprozessor 22 berechnet eine optimale Zuteilungsmenge durch Dividieren einer Ressourcenanforderungsmenge jedes RCST-Endgerätes 11 durch die Anzahl der Framepaare und Aufrunden eines Ergebnisses der Division auf die nächste Ganzzahl und das Bestimmungsmittel der Ressourcenzuteilung 24 bestimmt die optimale Zuteilungsmenge entsprechend den Prioritäten, wie etwa Kosten und Gewichtung.
Der Ressourcenzuteilungsplaner 25 bestimmt auf der Basis der optimalen Zuteilungsmenge die Endgeräte entsprechend jedem Zeitschlitz, der im ersten Framepaar enthalten ist.
Das Kopiermittel des Ressourcenzuteilungsplanes 26 kopiert den Ressourcenzuteilungsplan vom Ressourcenzuteilungsplaner 25 einschließlich eines Zeitschlitzzuteilungsplanes, der dem ersten Framepaar zugewiesen wurde, auf die im Superframe verbleibenden Framepaare.
3 ist ein Ablaufdiagramm, das das Verfahren zur dynamischen Ressourcenzuteilung gemäß einer bevorzugten Ausführungsform der vorliegenden Erfindung erklärt.
Zuerst wird in Schritt 301 eine Ressourcenzuteilungseinheit entsprechend einem Plan definiert. Das heißt, ein Superframe und ein Framepaar werden definiert.
Im MF-TDMA wird der Zuteilungsplan auf der Basis einer Frameeinheit im Superframe erstellt, wobei ein Superframe mehrere Frames enthält.
Ein Framepaar ist eine Untergruppe des Superframes und ist durch die folgenden Bedingungen definiert.
Ein Framepaar ist eine Gruppe von Frames mit einer identischen Zeitspanne. Jedes der Framepaare weist den gleichen Zeitschlitz-Gruppierungstyp und eine gleiche Frequenzbandbreite auf und der einzige Unterschied zwischen den Framepaaren ist die Zeitspanne. Somit ist jedes Framepaar eine Untergruppe des Superframes und eine Summe aller in einem bestehenden Superframe definierten Framepaare bildet einen Superframe.
Im Fall des in 4 gezeigten Superframes mit 32 Frames zum Beispiel existieren 16 Framepaare durch Paarung von Frame 0 und Frame 16 zu einem Framepaar und so weiter.
Nach dem Definieren des Framepaares oder des Superframes speichert das Erfassungsmittel für Ressourcenanforderungen 21 eine Kennung der Endgeräte, die in Schritt 302 angemeldet werden, und die während einer Superframelänge summierte Anforderungsmenge wird in Schritt 303 gespeichert. In Schritt 303 wird die Anforderungsmenge aktualisiert. Die summierte Anforderungsmenge jedes Terminals wird berechnet durch Dividieren der summierten angeforderten Anforderungsmenge durch die Anzahl der Framepaare im Superframe und Addieren des Ergebnisses der Division und der Aufrundung des Divisionsrestes auf die nächste Ganzzahl. Eine geringe Abweichung wird ignoriert, da jede Anforderungsmenge auf die gesamte Anzahl von Framepaaren verteilt wird.
Als nächstes berechnet das Bestimmungsmittel der Ressourcenzuteilung 24 die optimale Zuteilungsmenge auf der Basis der Anforderungsmenge von Schritt 304 und des Ressourcenzuteilungsplaners 25. Das Kopiermittel der Ressourcenzuteilung 26 bestimmt in Schritt 305 und 306 auf der Basis der optimalen Zuteilungsmenge Zeitschlitze für die Zuteilung zu jedem Endgerät entsprechend dem Framepaar.
In Schritt 305 bestimmt der Ressourcenzuteilungsplaner 25 die Zuordnung aller im ersten Framepaar enthaltenen Zeitschlitze zu den RCST-Endgeräten 11. In Schritt 306 kopiert das Kopiermittel des Ressourcenzuteilungsplanes 26 einen Zeitschlitzzuteilungsplan des ersten Framepaares auf die im selben Superframe verbleibenden Framepaare.
Im Fall des in 4 gezeigten Superframes mit 32 Frames wird zum Beispiel ein Algorithmus der Gleichungen 4 und 5 zum Bestimmen der Zuteilung eines Zeitschlitzes zu einem ersten Framepaar durch Erzeugen eines Ressourcenzuteilungsplanes angewandt und für die anderen Framepaare werden die Zeitschlitze durch Kopieren des Ressourcenzuteilungsplanes des ersten Framepaares zugeteilt. Das oben erwähnte Verfahren zum Bestimmen der Zuweisung jedes Zeitschlitzes kann die Berechnungsschritte und die Verarbeitungszeit verringern. Wenn zum Beispiel in einem Frame 2000 Zeitschlitze vorhanden sind, sind 2000 × 2 Berechnungen für das erste Framepaar erforderlich. Das heißt, es sind 4000 Zuteilungspläne erforderlich und die anderen Framepaare verwenden den für den ersten Frame berechneten Zuteilungsplan. Wenn hingegen Zuteilungspläne für alle Frames berechnet werden müssen, sind 64000 Zuteilungspläne erforderlich.
Hierin werden im Folgenden ein Schritt 304 zum Bestimmen der optimalen Zuteilungsmenge des ersten Framepaares im selben Superframe und ein Schritt 305 zum schnellen Zuteilen eines Zeitschlitzes auf der Basis der optimalen Zuteilungsmenge im Einzelnen erklärt.
Zunächst wird erklärt, wie die optimale Zuteilungsmenge auf der Basis einer summierten Anforderungsmenge berechnet wird, die während einer Superframelänge von den angemeldeten RCST-Endgeräten 11 empfangen wird.
Die Gleichung unten zeigt das Ausgangsproblem des dynamischen Zuteilens von Zeitschlitzen.
In Gleichung 1 ist i der i. Zeitschlitz, j das j. Endgerät und R eine Gruppe von Kennungen angemeldeter Endgeräte. A ist eine Gruppe von Kennungen von Rückverbindungsdemodulatoren, die verfügbar sind. S_m ist eine Gruppe von Kennungen verfügbarer Zeitschlitze und Q_j ist die maximale Anzahl von Zeitschlitzen, die dem Endgerät j zugeteilt werden können, und X_j ist die Anzahl der Zeitschlitze, die vom Endgerät j angefordert werden, und Y_j ist die Mindestanzahl von Zeitschlitzen, die dem Endgerät j zugeteilt werden sollen. X_ij ist eine Bestimmungsvariable, die einen Wert von 1 aufweist, wenn ein Zeitschlitz i einem Endgerät j zugeteilt wird, und anderenfalls einen Wert von 0 aufweist. V_j ist ein Strafkoeffizient (eine Strafgwichtung). Der Strafkoeffizient wird nach Maßgabe verschiedener Faktoren bestimmt, wie etwa der Verzögerung der restlichen Pakete in der Übertragungswarteschlange jedes RCST-Endgerätes. Das heißt, dem Strafkoeffizienten für das RCST-Endgerät wird ein hoher Wert zugewiesen, wenn das Endgerät viele verzögerte Daten enthält. Im Ergebnis kann eine gerechte Zuteilung der Ressourcen erreicht werden.
In Gleichung 1 ist g(x) die Gesamtstrafe, die durch die mit der Matrix [x_ij] gekennzeichnete Zeitschlitzzuteilung verursacht wird. Es gibt mehrere Bedingungen. Erstens muss die Anzahl von Zeitschlitzen zur Zuteilung zu jedem Endgerät kleiner als eine Obergrenze (Schwellenwert) oder eine Anforderungsanzahl sein, die von Systemparametern wie etwa dem Aufbau des Superframes bestimmt wird. Zweitens muss die Anzahl von Zeitschlitzen zur Zuteilung zu jedem Endgerät größer als eine Untergrenze sein, die zur Gewährleistung der Dienstgüte bestimmt wird. Und schließlich kann ein Zeitschlitz nicht zwei oder mehreren Endgeräten zugeteilt werden.
Die Gleichung 1 kann zur folgenden Gleichung 2 verändert werden, um das Problem einer Ressourcenzuteilung auf der Basis eines Konzepts von Framepaaren gemäß der vorliegenden Erfindung effizient zu lösen. Das Problem der Kapazitätszuteilung (Capacity Allocation Problem, CAP) kann mathematisch wie folgt formuliert werden:
Der Unterschied zwischen Gleichung 1 und Gleichung 2 besteht darin, dass die Anzahl der Objekte für den Zuteilungsplan aus einer Gesamtzahl von Schlitzen in einem Framepaar und einer Gesamtzahl von Schlitzen in einem Superframe besteht; somit kann die Verarbeitungszeit verringert werden, da die Größe des Problems (CAP) und der zur Lösung des Problems (CAP) erforderliche Aufwand verringert werden. Des Weiteren kann, wenn der Zuteilungsplan des ersten Framepaares kopiert und für die verbleibenden Framepaare verwendet wird, der Zuteilungsplan für die Zeitschlitze im Superframe effizient und schnell erstellt werden.
In Gleichung 2 ist S_m,1 eine Gruppe von verfügbaren Zeitschlitzen, die im ersten Superframe enthalten sind. Das Ausgangsproblem (CAP) wird in n Teilprobleme geteilt und x optimiert. Im Ergebnis ist
die optimale Lösung x.
Gleichung 2 erfordert eine Vorverarbeitung zur Berechnung einer bestimmten Zuteilungsmenge.
Ein Problem des Bestimmens einer Zuteilungsmenge v_j ist die Gewichtung, die darstellt, wie wichtig ein Endgerät j im Vergleich zu anderen Endgeräten ist. Die Gewichtung kann entsprechend einer Dienstgüte bestimmt werden. Zum Beispiel werden Ressourcen effizient und schnell an die Endgeräte zugeteilt, indem einem Endgerät höhere Priorität zugewiesen wird, dem seit langer Zeit keine Ressourcen zugewiesen wurden.
In Gleichung 3 ist Z_j eine Bestimmungsvariable, die die Anzahl der dem Endgerät j zugeteilten Zeitschlitze bezeichnet.
f(z) bezeichnet eine Gesamtstrafe, die der durch den Vektor z bezeichneten Zuteilungsmenge entspricht. Es bestehen folgende einschränkenden Bedingungen. Erstens muss die Zuteilungsmenge für jedes Endgerät geringer sein als eine gegebene Obergrenze und die Anforderungsmenge sein. Zweitens muss die Zuteilungsmenge für jedes Endgerät größer als eine gegebene Untergrenze sein und schließlich muss die Gesamtzuteilungsmenge geringer sein als die verfügbare Ressourcenmenge.
Ein Problem des Bestimmens einer Zuteilungsmenge ist im Folgenden dargestellt. Schritt 1 (Sortiere [vj]) k := 1, Jk-1 = { } Für (; k <= |R|; k + +){ jk := argmax{vj, j ∊ R – Jk-1} Jk := Jk-1 ⋃ {jk} } Schritt 2 (Finde optimales y*) n := max{n|Σnk=1 yjk ≤ Σm∊A|Sm| – Σj∊RYj} wenn n = |R|, dann yj := min{Qj – Yj, Xj} für j ∊ R Sonst y*j := min{Qj – Yj, Xj} für j ∊ Jn ym + 1 := Σm∊A|Sm| – ΣJ∊RYj –Σj∊fmmin{Qj – Yj, Xj} Schritt 3 (Finde optimales Z*) Z* := y* + ⌊Yj⌋ Gleichung 4
In Schritt 1 wird V_j absteigend von großer Gewichtung zu kleiner Gewichtung sortiert. Hierbei ist j_k eine Kennung eines Endgerätes mit der k-größten Strafgewichtung (V_j). J_k ist eine Gruppe mit {j₁, ..., j_k).
In In Schritt 2 wird die zusätzliche Zuteilungsmenge optimal bestimmt. Bei n := max{...} ist die zusätzliche Zuteilungsmenge die Anzahl der variablen Zeitschlitze Σx_jk. Ist eine verbliebene Ressourcenmenge ausreichend, wird eine zusätzlich angeforderte Ressource maximal zugeteilt und ist die verbliebene Ressourcenmenge nicht ausreichend, wird die zusätzlich angeforderte Ressourcemenge zuerst maximal dem Endgerät J_n mit der höchsten Priorität zugeteilt und die dann noch verbliebene Ressourcenmenge an andere Endgeräte.
Schritt 3 ist ein Schritt der Bestimmung der Gesamtzuteilungsmenge. Die Gesamtzuteilungsmenge ist eine Summe der Grundzuteilungsmenge und der zusätzlichen Zuteilungsmenge und wird für jedes Endgerät berechnet.
In Bezug auf Gleichung 4 wird im Folgenden ein Schritt 304 zum Bestimmen der optimalen Ressourcenzuteilungsmenge erklärt.
Zunächst wird absteigend von hoher Gewichtung zu niedriger Gewichtung sortiert. Zu diesem Zeitpunkt weist die höchste Gewichtung einen Index j₁ auf, der in einer Gruppe J₁ gespeichert ist. In ähnlicher Weise weist die k-höchste Gewichtung einen Index j_k auf, der in einer Gruppe J_k gespeichert ist.
Danach wird in Schritt 2 eine zusätzliche Zuteilungsmenge y * / j bestimmt, wobei die minimale Zuteilungsmenge ausgenommen bleibt. In Schritt 3 wird durch Addieren der bestimmten zusätzlichen Zuteilungsmenge und der optimalen Zuteilungsmenge eine Gesamtzuteilungsmenge z * / j berechnet. Hierbei ist y* = [y * / j] und z* = [z * / j].
Andererseits zeigt die folgende Gleichung 5 einen Schritt 305 zum Bestimmen eines Zeitschlitzes, der jedem der RCST-Endgeräte auf der Basis des optimalen Zuteilungsvektors z* zuzuteilen ist. Das heißt, dies ist ein Schritt zum Auswählen des Zeitschlitzes, der jedem der Endgeräte auf der Basis der bestimmten Zuteilungsmenge [z * / j], zuzuteilen ist.
In Gleichung 5 ist einem Endgerät j_k ein Schlitz i zugewiesen und x_i und j_k sind auf 1 gesetzt. Das heißt, i wird um die Anzahl der Zuteilungen erhöht und x_i und j_k sind auf 1 gesetzt, daher ist eine Zuteilungsmenge an die Endgeräte j_k z * / j.
In Gleichung 5 sind objektive Zeitschlitze alle Zeitschlitze eines ersten Framepaares. Die Zeitschlitze werden ausgehend von dem mit der niedrigsten Frequenz (Träger) in Richtung der zeitlichen Zunahme zugeteilt. Der oben erwähnte Schritt wird für den nächsten Träger wiederholt.
Ein in den Schritten 304 und 305 erzeugter Plan von Framepaaren wird in Schritt 306 auf die verbleibenden Framepaare kopiert. Damit ist der Zuteilungsplan für alle im Superframe enthaltenen Zeitschlitze fertig gestellt.
Wie oben erwähnt, liegt ein Grund für die Berechnung der optimalen Zuteilungsmenge darin, dass die Werte der objektiven Gleichung nicht verändert werden, wenn sie in irgendeine Richtung verändert wird.
5A bis 5D zeigen ein Simulationsergebnis der bevorzugten Ausführungsform der Erfindung zum Nachweis der Effektivität der vorliegenden Erfindung. Zum Ausführen der Simulation der vorliegenden Erfindung wird ein Personalcomputer mit Pentium III 1,0 GHz verwendet. Die Simulation verwendet ein Modellnetzwerk mit 128 Endgeräten und 65024 Zeitschlitzen unter den Bedingungen, dass alle Gewichtungen 1 sind, eine Mindestzuteilungsmenge 6 pro Frame beträgt und eine maximale Zuteilungsmenge 508 pro Frame beträgt. Die Simulation wird fortgeführt, indem willkürlich eine Ressourcenanforderungsmenge erzeugt und die Zeit gemessen wird, die zum Lösen von zwei Problemen der angeforderten Ressourcenmenge benötigt wird.
Für die Simulation wurde ein Programm verwendet, das bereits als Echtzeit-Ressourcenmanager in einer Host-Station HUB 13 verwendet wurde und das eine Zeit zum Formulieren eines Ressourcenzuteilungsplanes als eine Art des Datentransfers zwischen Einheiten des realen Systems enthält. Gemäß dem Ergebnis der Simulation wird eine Zeit von maximal 10 ms zum Bestimmen einer Zuteilungsmenge und ferner eine Zeit von maximal 30 ms zum Auswählen eines Zeitschlitzes benötigt. Außerdem werden 500 ms zum Anfordern einer Ressource von einer Hauptstation HUB 13 für ein RCST-Endgerät 11, zum vollständigen Erstellen eines Zuteilungsplanes und zur Rücksendung des Zuteilungsplanes an das RCST-Endgerät 11 benötigt. Obwohl eine Länge eines Superframes im Bereich von 2000–9200 ms (ein DVB-RCS-Standard) liegt, wird deutlich gezeigt, dass die Verarbeitungsgeschwindigkeit der vorliegenden Erfindung im Vergleich zum Stand der Technik sehr schnell ist.
Das oben erwähnte Verfahren gemäß der vorliegenden Erfindung kann in Form von Befehlen ausgeführt sein und auf einem computerlesbaren Aufzeichnungsmedium, wie einer CD-ROM, einem RAM, einer Diskette, einer Festplatte und optischen Magnetplatten, gespeichert sein.
Wie oben erwähnt kann die vorliegende Erfindung einen Ressourcenzuteilungsplan ausgeben, um einen maximalen Durchsatz bei einer Zeitschlitzzuteilung in einer auf MF-TDMA basierenden Rückverbindung eines interaktiven Multimedianetzwerkes zu erreichen, indem ein Verfahren der Problemteilung mit Hilfe eines Framepaares verwendet wird.
Obwohl die vorliegende Erfindung in Bezug auf bestimmte bevorzugte Ausführungsformen beschreiben wurde, ist es für den Fachmann offensichtlich, dass verschiedene Änderungen und Modifikationen vorgenommen werden können, ohne vom Anwendungsbereich der Erfindung abzuweichen, der in den folgenden Ansprüchen definiert ist.

Claims

Vorrichtung zur dynamischen Zuteilung von Ressourcen in einem interaktiven Zeitmultiplex-Satellitenmultimediasystem, in dem mehrere Endgeräte (11) über einen Satelliten (12) Ressourcenanforderungen an einen zentralen Ressourcenplaner (13) senden, dadurch gekennzeichnet, dass die Vorrichtung am zentralen Ressourcenplaner Folgendes umfasst: Erfassungsmittel für Ressourcenanforderungsmengen (21) zum Summieren (303) einer angeforderten Ressourcenmenge für jedes der mehreren Endgeräte (302) während einer Superframe-Periode, wobei der Superframe in eine Anzahl von Framepaaren geteilt ist (301), Verarbeitungsmittel für Ressourcenanforderungsmengen (22) zum Dividieren der summierten angeforderten Ressourcenmenge durch die Anzahl der Framepaare im Superframe für jedes der Endgeräte und Speichern des Ergebnisses der Division, aufgerundet auf die nächste Ganzzahl, als eine Anforderungsmenge für das entsprechende Endgerät für das erste Framepaar, Ressourcenzuteilungsmittel (24, 25) zum Zuteilen (304, 305) von Zeitschlitzen des ersten Framepaares an die Endgeräte auf der Basis einer optimalen Zuteilungsmenge und Kopiermittel des Ressourcenzuteilungsplaners (26) zum Kopieren (306) der Zuteilung von Zeitschlitzen des ersten Framepaares auf alle anderen Framepaare des Superframes.
Verfahren zur dynamischen Zuteilung von Ressourcen in einem interaktiven Zeitmultiplex-Satellitenmultimedia system, in dem mehrere Endgeräte (11) über einen Satelliten (12) Ressourcenanforderungen an einen zentralen Ressourcenplaner (13) senden, dadurch gekennzeichnet, dass das Verfahren am zentralen Ressourcenplaner folgende Schritte umfasst: a) Summieren (303) einer angeforderten Ressourcenmenge für jedes der mehreren Endgeräte (302) während einer Superframe-Periode durch ein Erfassungsmittel für Ressourcenanforderungsmengen (21), wobei der Superframe in eine Anzahl von Framepaaren geteilt ist (301), b) Dividieren, mit Hilfe von Verarbeitungsmitteln für Ressourcenanforderungsmengen (22), der für jedes Endgerät summierten angeforderten Ressourcenmenge durch die Anzahl der Framepaare im Superframe und Speichern des Ergebnisses der Division, aufgerundet auf die nächste Ganzzahl, als eine Anforderungsmenge für das entsprechende Endgerät für das nächste Framepaar c) Zuteilen (304, 305) der Zeitschlitze des ersten Framepaares an die Endgeräte auf der Basis einer optimalen Zuteilungsmenge durch Ressourcenzuteilungsmittel (24, 25) und d) Kopieren (306) der Zuteilung der Zeitschlitze des ersten Framepaares auf alle anderen Framepaare des Superframes durch die Kopiermittel des Ressourcenzuteilungsplaners (26).
Verfahren nach Anspruch 2, wobei der Schritt c) über die optimale Zuteilungsmenge gemäß den Prioritäten der Ressourceanfragemengen, die in Schritt b) verarbeitet wurden, entscheidet.
Computerlesbares Aufzeichnungsmedium, das Befehle zum Ausführen eines Verfahrens zur dynamischen Zuteilung von Ressourcen in einem interaktiven Zeitmultiplex-Satellitenmultimediasystem speichert, in dem mehrere Endgeräte (11) über einen Satelliten (12) Ressourcenanforderungen an einen zentralen Ressourcenplaner (13) senden, dadurch gekennzeichnet, dass das Verfahren folgende Schritte umfasst: a) Summieren (303) einer angeforderten Ressourcenmenge für jedes der mehreren Endgeräte (302) während einer Superframe-Periode, wobei der Superframe in eine Anzahl von Framepaaren geteilt ist (301), b) Dividieren der für jedes Endgerät summierten angeforderten Ressourcenmenge durch die Anzahl der Framepaare im Superframe und Speichern des Ergebnisses der Division, aufgerundet auf die nächste Ganzzahl, als eine Anforderungsmenge für das entsprechende Endgerät für das erste Framepaar, c) Zuteilen (304, 305) der Zeitschlitze des ersten Framepaares an die Endgeräte auf der Basis einer optimalen Zuteilungsmenge und d) Kopieren (306) der Zuteilung der Zeitschlitze des ersten Framepaares auf alle anderen Framepaare des Superframes.