DE112014004794T5

DE112014004794T5 - Zuteilen von Kartenabgleichaufgaben durch Cluster-Server im Internet der Fahrzeuge

Info

Publication number: DE112014004794T5
Application number: DE112014004794.5T
Authority: DE
Inventors: Peng Gao; Ning Duan; Weishan Dong; Baohua Wang; Xin Zhang
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 2013-11-29
Filing date: 2014-10-11
Publication date: 2016-07-21
Anticipated expiration: 2034-10-12
Also published as: CN104683405B; DE112014004794B4; US9683852B2; US20150153187A1; WO2015078238A1; CN104683405A

Abstract

Die vorliegende Erfindung betrifft ein Verfahren und eine Vorrichtung zum Zuteilen einer Aufgabe zum Abgleichen von Karten auf einem Cluster-Server im Internet der Fahrzeuge. Insbesondere wird ein Verfahren offenbart, aufweisend: Ermitteln einer Straßensegmentgruppenmenge, die einem bestimmten Zeitraum entspricht, und einer Entsprechungsbeziehung zwischen jeder Straßensegmentgruppe in der Straßensegmentgruppenmenge und einem Datenverarbeitungsknoten des Cluster-Servers, wobei die Straßensegmentgruppe eine Gruppe von Straßensegmenten ist, die gemäß der Anzahl von Datenverarbeitungsknoten des Cluster-Servers und der Unähnlichkeit zwischen unterteilten Straßensegmenten in einem Straßennetz gruppiert sind; als Reaktion auf eine Empfangen mehrerer GPS-Abtastdaten von einem Fahrzeug ein Erzeugen einer Kartenabgleichanforderung in Abhängigkeit vor den mehreren GPS-Abtastdaten; und als Reaktion auf ein Erzeugen einer Kartenabgleichanforderung und ein Erhalten eines Straßensegments, zu dem der letzte Standort des Fahrzeugs gehört, Senden der Kartenabgleichanforderung zum Kartenabgleichen an einen Datenverarbeitungsknoten, der einer Straßensegmentgruppe entspricht, zu der das erhaltene Straßensegment gehört. Das Verfahren gemäß der Ausführungsform der vorliegenden Erfindung kann Konflikte auflösen, die auftreten, wenn Datenverarbeitungsknoten des Cluster-Servers Kartenabgleichanforderungen verarbeiten.

Description

GEBIET
Die vorliegende Erfindung betrifft das Abgleichen von Karten im Internet der Fahrzeuge und insbesondere ein Verfahren und eine Vorrichtung zum Zuteilen einer Aufgabe zum Abgleichen von Karten auf einem Cluster-Server im Internet der Fahrzeuge.
HINTERGRUND
Mit dem Aufkommen der Ära des Internets der Fahrzeuge wird die Bereitstellung von standortbezogenen Diensten (Location-based Services, LBS) in Echtzeit für Millionen von Fahrzeugen zu einem Trend und letztendlich Wirklichkeit. Eine Voraussetzung für das Bereitstellen standardbezogener Dienste besteht in der exakten Positionierung von Echtzeitstandorten von Fahrzeugen in Straßensegmenten. Aufgrund der Drift von GPS-Signalen, der Komplexität von Bedingungen auf städtischen Straßen (z. B. komplexe Überführungsbauwerke) und anderer Faktoren ist eine Kartenabgleichtechnologie erwünscht, bei der es sich um eine kritische Technologie zur exakten Positionierung von Echtzeitstandorten von Fahrzeugen handelt.
Eine ideale Wahl beim praktischen Betrieb besteht darin, an einem Serverende Kartenabgleichdienste für Fahrzeuge einheitlich bereitzustellen, die auf das Internet der Fahrzeuge zugreifen, wodurch Kartenversionsabweichungen auf unterschiedlichen Terminaleinheiten vermieden werden, Latenzen beim Aktualisieren von Karten vermieden werden und ein gemeinschaftliches Abgleichen von Cluster-Fahrzeugen erreicht wird. Anschließend wird ein Cluster-Hochleistungsserver mit Lastausgleich benötigt, um eine latenzarme Hochleistungstechnologie zum Abgleichen von Karten für Millionen von Fahrzeugen bereitzustellen.
Die bestehende Lastausgleichstechnologie berücksichtigt die Leistungsfähigkeit von Cluster-Servern, gemeldete Berechnungsarbeitslasten, die Reaktionsgeschwindigkeit, Netzwerk-Arbeitslasten, geographische Standorte und andere Faktoren, kann aber Konflikte zwischen Anforderungen zum Abgleichen von Karten nicht lösen.
Seit dem Übergang in das Mehrkernzeitalter ist es unverzichtbar und von großer Bedeutung, die Parallelverarbeitungsfähigkeiten mehrerer Kerne voll zu nutzen, um die Gesamt-Datenverarbeitungsleistung eines Clusters zu verbessern. Bei einem Kartenabgleichalgorithmus ist eine große Anzahl von Kurzstreckensuchvorgängen einer der Hauptfaktoren, die Berechnungsressourcen in Anspruch nehmen. Es ist notwendig, von Parallelverarbeitungsfähigkeiten mehrerer Kerne in ausreichender Weise Gebrauch zu machen, um eine große Anzahl von Kurzstreckensuchvorgängen zu bewältigen. Beim wirksamen Einsatz von Parallelverarbeitungsfähigkeiten mehrerer Kerne zur Realisierung paralleler Kurzstreckensuchvorgänge treten Konflikte zwischen Streckensuchaufgaben bei benachbarten geographischen Standorten auf, anschließend entsteht eine Synchronisierungswarteschlange, und letztendlich verschlechtert sich die Gesamt Datenverarbeitungsleistung. Ein Grund, aus dem Konflikte zwischen Streckensuchaufgaben bei benachbarten geographischen Standorten auftreten, liegt darin, dass bei GIS-Daten infrage kommende Abgleichstandorte von Abtastpunkten normalerweise keine Originalknoten in einem Straßennetz sind. Daher müssen beim Suchen nach der kürzesten Strecke zwischen diesen infrage kommenden Standorten zeitweilige Knoten zum Straßennetzmodell hinzugefügt werden. In der Zwischenzeit muss, wenn ein Bedarf zur Verwendung heuristischer Suchvorgänge besteht, um die Suchgeschwindigkeit zu erhöhen, eine große Anzahl zeitweiliger Status in Mittenknoten registriert werden. Diese häufigen Schreibvorgänge verursachen ein schwerwiegendes Konfliktproblem bei der Paralleldatenverarbeitung.
Daher besteht ein Bedarf an einem Verfahren zum Lösen von Konflikten, die auftreten, wenn Datenverarbeitungsknoten eines Cluster-Servers Kartenabgeichaufgaben bewältigen.
KURZDARSTELLUNG
Gemäß einem Aspekt der vorliegenden Erfindung wird ein Verfahren zum Zuteilen einer Kartenabgleichaufgabe auf einem Cluster-Server im Internet der Fahrzeuge bereitgestellt, aufweisend: Ermitteln einer Straßensegmentgruppenmenge, die einem bestimmten Zeitraum entspricht, und einer Entsprechungsbeziehung zwischen jeder Straßensegmentgruppe der Straßensegmentgruppenmenge und einem Datenverarbeitungsknoten des Cluster-Servers, wobei die Straßensegmentgruppe eine Gruppe von Straßensegmenten ist, die gemäß der Anzahl von Datenverarbeitungsknoten des Cluster-Servers und der Unähnlichkeit zwischen unterteilten Straßensegmenten in einem Straßennetz gruppiert sind; als Reaktion auf den Empfang mehrerer GPS-Abtastdaten von einem Fahrzeug ein Erzeugen einer Kartenabgleichanforderung in Abhängigkeit von den mehreren GPS-Abtastdaten; und als Reaktion auf das Erzeugen einer Kartenabgleichanforderung und den Erhalt eines Straßensegments, zu dem der letzte Standort des Fahrzeugs gehört, Senden der Kartenabgleichanforderung zum Kartenabgleichen an einen Datenverarbeitungsknoten, der einer Straßensegmentgruppe entspricht, zu der das erhaltene Straßensegment gehört.
Gemäß einem weiteren Aspekt der vorliegenden Erfindung wird eine Vorrichtung zum Zuteilen einer Kartenabgleichaufgabe auf einem Cluster-Server im Internet der Fahrzeuge bereitgestellt, aufweisend: ein Ermittlungsmodul, das so konfiguriert ist, dass eine Straßensegmentgruppenmenge, die einem bestimmten Zeitraum entspricht, und eine Entsprechungsbeziehung zwischen jeder Straßensegmentgruppe in der Straßensegmentgruppenmenge und einem Datenverarbeitungsknoten des Cluster-Servers ermittelt wird, wobei die Straßensegmentgruppe eine Gruppe von Straßensegmenten ist, die gemäß der Anzahl von Datenverarbeitungsknoten des Cluster-Servers und der Unähnlichkeit zwischen unterteilten Straßensegmenten in einem Straßennetz gruppiert sind; ein Abgleichanforderungs-Erzeugungsmodul, das so konfiguriert ist, dass als Reaktion auf den Empfang mehrerer GPS-Abtastdaten von einem Fahrzeug in Abhängigkeit von den mehreren GPS-Abtastdaten eine Kartenabgleichanforderung erzeugt wird; und ein Zuteilungsmodul, das so konfiguriert ist, dass als Reaktion auf das Erzeugen einer Kartenabgleichanforderung und den Erhalt eines Straßensegments, zu dem der letzte Standort des Fahrzeugs gehört, die Kartenabgleichanforderung zum Kartenabgleichen an einen Datenverarbeitungsknoten gesendet wird, der einer Straßensegmentgruppe entspricht, zu der das erhaltene Straßensegment gehört.
Mithilfe des Verfahrens und der Vorrichtung gemäß den Ausführungsformen der vorliegenden Erfindung können Konflikte aufgelöst werden, die verursacht werden, wenn Datenverarbeitungsknoten des Cluster-Servers Kartenabgleichanforderungen verarbeiten.
KURZBESCHREIBUNG DER VERSCHIEDENEN ANSICHTEN IN DEN ZEICHNUNGEN
Anhand der ausführlicheren Beschreibung einiger Ausführungsformen der vorliegenden Offenbarung in den beigefügten Zeichnungen werden die oben genannten und andere Aufgaben, Merkmale und Vorteile der vorliegenden Offenbarung deutlicher, wobei das gleiche Bezugszeichen im Allgemeinen die gleichen Komponenten in den Ausführungsformen der vorliegenden Offenbarung bezeichnet.
1 zeigt ein beispielhaftes Computersystem bzw. einen beispielhaften Server 12, das bzw. der zur Realisierung der Ausführungsformen der vorliegenden Erfindung anwendbar ist;
2 zeigt ein Verfahren zum Zuteilen einer Kartenabgleichaufgabe auf einem Cluster-Server im Internet der Fahrzeuge gemäß einer Ausführungsform der vorliegenden Erfindung;
3 zeigt ein Flussdiagramm des Unterteilens von Straßensegmenten durch Verwenden eines rekursiven Verfahrens zur gleichmäßigen Aufteilung gemäß einer Ausführungsform der vorliegenden Erfindung;
4 zeigt ein Flussdiagramm des Unterteilens von Straßensegmenten gemäß einer weiteren Ausführungsform der vorliegenden Erfindung; und
5 zeigt eine Vorrichtung 500 zum Zuteilen einer Kartenabgleichaufgabe auf einem Cluster-Server im Internet der Fahrzeuge gemäß einer Ausführungsform der vorliegenden Erfindung.
AUSFÜHRLICHE BESCHREIBUNG
Einige vorzuziehende Ausführungsformen werden unter Bezugnahme auf die beigefügten Zeichnungen ausführlicher beschrieben, in denen die vorzuziehenden Ausführungsformen der vorliegenden Offenbarung dargestellt sind. Die vorliegende Offenbarung kann jedoch in verschiedener Weise realisiert werden und sollte daher nicht als auf die hierin offenbarten Ausführungsformen beschränkt ausgelegt werden. Diese Ausführungsformen werden im Gegenteil bereitgestellt, um dem Fachmann das gründliche und vollständige Verständnis der vorliegenden Offenbarung zu ermöglichen und den Schutzbereich der vorliegenden Erfindung vollständig aufzuzeigen.
Dem Fachmann wird klar sein, dass Aspekte der vorliegenden Erfindung in Form eines Systems, Verfahrens oder Computerprogrammprodukts verkörpert sein können. Dementsprechend können Aspekte der vorliegenden Erfindung die Form einer vollständig in Hardware realisierten Ausführungsform, einer vollständig in Software realisierten Ausführungsform (einschließlich Firmware, residenter Software, Mikrocode usw.) oder einer Ausführungsform annehmen, die Software- und Hardwareaspekte kombiniert, die hierin allgemein als „Schaltung”, „Modul” oder „System” bezeichnet werden. Des Weiteren können Aspekte der vorliegenden Erfindung die Form eines Computerprogrammprodukts annehmen, das in einem oder mehreren computerlesbaren Medien verkörpert ist, auf denen computerlesbarer Programmcode verkörpert ist.
Es können beliebige Kombinationen eines oder mehrerer computerlesbarer Medien verwendet werden. Das computerlesbare Medium kann ein computerlesbares Signalmedium oder ein computerlesbares Speichermedium sein. Zu computerlesbaren Speichermedien können beispielsweise, ohne auf diese beschränkt zu sein, ein elektronisches, ein magnetisches, ein optisches, ein elektromagnetisches System bzw. ein Infrarot- oder ein Halbleitersystem bzw. eine derartige Vorrichtung oder Einheit oder eine beliebige geeignete Kombination des Vorstehenden gehören. Zu konkreteren Beispielen (unvollständige Liste) des computerlesbaren Speichermediums zählen unter anderem folgende: eine elektrische Verbindung mit einer oder mehreren Leitungen, eine tragbare Computerdiskette, eine Festplatte, ein Direktzugriffsspeicher (RAM), ein Nur-Lese-Speicher (ROM), ein löschbarer programmierbarer Nur-Lese-Speicher (EPROM oder Flash-Speicher), ein Lichtwellenleiter, ein tragbarer Nur-Lese-Speicher in Form einer Compact Disc (CD-ROM), eine optische Speichereinheit, eine magnetische Speichereinheit oder eine beliebige geeignete Kombination des Vorstehenden. Im Kontext dieses Dokuments kann ein computerlesbares Speichermedium jedes beliebige vergegenständlichte Medium sein, das ein Programm enthalten oder speichern kann, das von oder in Verbindung mit einem System, einer Vorrichtung oder einer Einheit zur Befehlsausführung genutzt werden kann.
Ein computerlesbares Signalmedium kann unter anderem ein im Basisband oder als Teil einer Trägerwelle verbreitetes Datensignal mit darin verkörpertem computerlesbarem Programmcode aufweisen. Ein derartiges verbreitetes Signal kann eine beliebige Vielfalt von Formen annehmen, einschließlich und ohne auf diese beschränkt zu sein, einer elektromagnetischen oder optischen Form oder einer beliebigen geeigneten Kombination davon. Ein computerlesbares Signalmedium kann ein beliebiges computerlesbares Medium sein, bei dem es sich nicht um ein computerlesbares Speichermedium handelt und das ein Programm übertragen, verbreiten oder transportieren kann, das von oder in Verbindung mit einem System, einer Vorrichtung oder einer Einheit zur Befehlsausführung genutzt werden kann.
Auf einem computerlesbaren Medium verkörperter Programmcode kann unter Verwendung jedes beliebigen geeigneten Mediums, einschließlich, ohne auf diese beschränkt zu sein, drahtloser, drahtgebundener Medien, von Lichtwellenleitern, HF usw. oder unter Verwendung einer beliebigen geeigneten Kombination des Vorstehenden übertragen werden.
Computerprogrammcode zum Ausführen von Operationen bei Aspekten der vorliegenden Erfindung kann in einer beliebigen Kombination aus einer oder mehreren Programmiersprachen geschrieben sein, darunter in einer objektorientierten Programmiersprache wie Java, Smalltalk, C++ oder dergleichen und in herkömmlichen prozeduralen Programmiersprachen wie „C” oder ähnlichen Programmiersprachen. Der Programmcode kann vollständig auf dem Computer des Benutzers, teilweise auf dem Computer des Benutzers, als eigenständiges Softwarepaket, teilweise auf dem Computer des Benutzers und teilweise auf einem entfernt angeordneten Computer oder vollständig auf dem entfernt angeordneten Computer oder Server ausgeführt werden. Beim letztgenannten Szenario kann der entfernt angeordnete Computer mit dem Computer des Benutzers über eine beliebige Art von Netzwerk verbunden sein, unter anderem über ein lokales Netzwerk (Local Area Network, LAN) oder über ein Weitverkehrsnetzwerk (Wide Area Network, WAN), oder die Verbindung kann zu einem externen Computer hergestellt werden (beispielsweise über das Internet unter Nutzung eines Internet-Dienstanbieters (Internet Service Provider)).
Nachfolgend sind Aspekte der vorliegenden Erfindung unter Bezugnahme auf Flussdiagramme und/oder Blockschemata von Verfahren, Vorrichtungen (Systemen) und Computerprogrammprodukten gemäß Ausführungsformen der Erfindung beschrieben. Es wird klar sein, dass jeder Block der Flussdiagramme und/oder der Blockschemata und Kombinationen von Blöcken in den Flussdiagrammen und/oder Blockschemata durch Computerprogrammanweisungen realisiert werden kann bzw. können. Diese Computerprogrammanweisungen können einem Prozessor eines Mehrzweckcomputers, eines Spezialcomputers oder anderer programmierbarer Datenverarbeitungsvorrichtungen bereitgestellt werden, um eine Maschine zu erzeugen, sodass die Anweisungen, die über den Prozessor des Computers oder anderer programmierbarer Datenverarbeitungsvorrichtungen ausgeführt werden, Mittel zum Realisieren der in einem Block bzw. in den Blöcken der Flussdiagramme und/oder der Blockschemata angegebenen Funktionen/Aktionen schaffen.
Diese Computerprogrammanweisungen können ebenfalls in einem computerlesbaren Medium gespeichert sein, das einen Computer, andere programmierbare Datenverarbeitungsvorrichtungen oder andere Einheiten anweisen kann, in einer bestimmten Weise zu funktionieren, sodass die im computerlesbaren Medium gespeicherten Anweisungen ein Erzeugnis schaffen, das die Anweisungen aufweist, die die in einem Block bzw. in den Blöcken der Flussdiagramme und/oder der Blockschemata angegebene Funktion/Aktion realisieren.
Die Computerprogrammanweisungen können auch in einen Computer, in andere programmierbare Datenverarbeitungsvorrichtungen oder in andere Einheiten geladen werden, um zu bewirken, dass auf dem Computer, auf anderen programmierbaren Vorrichtungen oder anderen Einheiten eine Reihe von Arbeitsschritten ausgeführt wird, um einen mittels Computer realisierten Prozess zu schaffen, sodass die Anweisungen, die auf dem Computer oder auf anderen programmierbaren Vorrichtungen ausgeführt werden, Prozesse zur Realisierung der in einem Block bzw. in den Blöcken der Flussdiagramms und/oder der Blockschemata angegebenen Funktionen/Aktionen bereitstellen.
1 veranschaulicht ein beispielhaftes Computersystem bzw. einen beispielhaften Senner 12, das bzw. der zur Realisierung der Ausführungsformen der vorliegenden Erfindung anwendbar ist. Das Computersystem bzw. der Server 12, wie in 1 dargestellt, ist lediglich ein Beispiel, das keinerlei Einschränkung der Funktionen und des Anwendungsbereiches der Ausführungsformen der vorliegenden Erfindung bilden sollte.
Wie in 1 dargestellt, ist das Computersystem/der Server 12 in Form einer allgemeinen Datenverarbeitungseinheit verkörpert. Komponenten des Computersystems/Servers 12 können, ohne auf diese beschränkt zu sein, einen oder mehrere Prozessoren bzw. eine oder mehrere Verarbeitungseinheiten 16, einen Systemspeicher 28 und einen Bus 18 aufweisen, der unterschiedliche Systemkomponenten (einschließlich des Systemspeichers 28 und der Verarbeitungseinheit 16) verbindet.
Der Systembus 18 bezeichnet eine oder mehrere einer Mehrzahl von Busstrukturen, einschließlich eines Speicherbusses oder einer Speichersteuereinheit, eines Peripheriebusses, eines Grafikbeschleunigungsanschlusses, eines Prozessors oder eines lokalen Busses, die eine beliebige Busstruktur in der Mehrzahl von Busstrukturen nutzen. Beispielsweise gehören zu den oben aufgeführten hierarchischen Strukturen, ohne auf diese beschränkt zu sein, ein ISA-Bus (ISA Industrial Standard Architecture), ein MCA-Bus (MCA = MicroChannel Architecture), ein erweiterter ISA-Bus, ein lokaler VESA-Bus (VESA = Video Electronic Standard Association) und ein PCI-Bus (PCI = Peripheral Component Interconnection).
Das Computersystem/der Server 12 weist normalerweise verschiedene Arten von computerlesbaren Medien auf. Diese Medien können beliebige verfügbare Medien sein, auf die das Computersystem/der Server 12 zugreifen kann, und weisen flüchtige und nichtflüchtige Medien, mobile und nichtmobile Medien auf.
Der Systemspeicher 28 kann ein für Computersysteme lesbares Medium in Form von flüchtigem Speicher wie zum Beispiel einen Direktzugriffsspeicher (Random Access Memory, RAM) 30 und/oder einen Cache 32 aufweisen. Das Computersystem/der Server 12 kann ferner andere mobile/nichtmobile, flüchtige/nichtflüchtige Computersystem-Speichermedien aufweisen. Als Beispiel kann das Speichersystem 34 verwendet werden, um von einem nichtmobilen/nichtflüchtigen magnetischen Medium (in 1 nicht dargestellt, allgemein als „Festplattenlaufwerk” bezeichnet) zu lesen bzw. auf dieses zu schreiben. Obwohl in 1 nicht dargestellt, können ein Magnetplattentreiber zum Lesen von einer und Schreiben auf eine mobile, nichtflüchtige Magnetplatte (zum Beispiel eine „Diskette”) und ein Treiber für optische Platten zum Lesen von einer oder Schreiben auf eine mobile, nichtflüchtige optische Platte (zum Beispiel ein CD-ROM, DVD-ROM oder ein anderes optisches Medium) bereitgestellt sein. In diesen Fällen kann jeder Treiber über eine oder mehrere Datenmedienschnittstellen mit dem Bus 18 verbunden sein. Der Speicher 28 kann mindestens ein Programmprodukt aufweisen, das eine Menge Programmmodule (zum Beispiel mindestens eines) enthält, und diese Programmmodule können so konfiguriert sein, dass die Funktionen verschiedener Ausführungsformen der vorlegenden Erfindung durchgeführt werden.
Ein Programm-Tool/Dienstprogramm-Tool 40, das eine Menge von Programmmodulen (mindestens eines) 42 aufweist, kann zum Beispiel im Speicher 28 gespeichert sein; ein derartiges Programmmodul 42 weist, ohne auf diese beschränkt zu sein, ein Betriebssystem, eine oder mehrere Anwendungen, andere Programmmodule und Programmdaten auf, und jedes dieser Beispiele oder eine bestimmte Kombination davon könnte eine Realisierungsform einer Netzwerkumgebung aufweisen. Das Programmmodul 42 führt wie gemäß der vorliegenden Erfindung beschrieben allgemein die Funktionen und/oder Verfahren in den Ausführungsformen aus.
Das Computersystem/der Server 12 kann außerdem mit einer oder mehreren Peripherieeinheiten 14 (zum Beispiel einer Tastatur, einer Druckeinheit, einer Anzeige 24 usw.) Daten austauschen, und es bzw. er kann auch mit einer oder mehreren Einheiten Daten austauschen, die es dem Benutzer ermöglichen, mit dem Computersystem/Server 12 zu interagieren, und/oder mit einer beliebigen Einheit (zum Beispiel Netzwerkkarte, Modem usw.) Daten austauschen, die es dem Computersystem/Server 12 ermöglicht, Daten mit einer oder mehreren anderen Datenverarbeitungseinheiten auszutauschen. Ein derartiger Datenaustausch kann über eine Eingabe/Ausgabe-Schnittstelle (E/A-Schnittstelle) 22 stattfinden. Darüber hinaus kann das Computersystem/der Server 12 Daten mit einem oder mehreren Netzwerken austauschen (zum Beispiel mit einem lokalen Netzwerk (LAN), mit einem Weitverkehrsnetzwerk (WAN) und/oder mit einem öffentlichen Netzwerk, zum Beispiel mit dem Internet). Wie in der Figur dargestellt, tauscht ein Netzwerkadapter 20 über den Bus 18 Daten mit anderen Modulen des Computersystems/Servers 12 aus. Es sollte klar sein, dass, obwohl in der Figur nicht dargestellt, andere Hardware- und/oder Softwaremodule in Kombination mit dem Computersystem/Server 12 verwendet werden können, einschließlich und ohne auf diese beschränkt zu sein, Mikrocode, ein Gerätetreiber, eine Redundanzverarbeitungseinheit, ein Plattenlaufwerksarray, ein RAID-System, Magnetbandtreiber und ein Datensicherungs-Speichersystem usw.
Unter Bezugnahme auf 2 zeigt diese Figur ein Verfahren zum Zuteilen einer Kartenabgleichaufgabe auf einem Cluster-Server im Internet der Fahrzeuge, wobei das Verfahren aufweist: in Schritt S201 Ermitteln einer Menge von Straßensegmentgruppen, die einem bestimmten Zeitraum entspricht, und einer Entsprechungsbeziehung zwischen jeder Straßensegmentgruppe in der Menge von Straßensegmentgruppen und einem Datenverarbeitungsknoten des Cluster-Servers, wobei die Straßensegmentgruppe eine Gruppe von Straßensegmenten ist, die gemäß der Anzahl von Datenverarbeitungsknoten des Cluster-Servers und der Unähnlichkeit zwischen unterteilten Straßensegmenten in einem Straßennetz gruppiert sind; in Schritt S202 als Reaktion auf den Empfang mehrerer GPS-Abtastdaten von einem Fahrzeug ein Erzeugen einer Kartenabgleichanforderung in Abhängigkeit von den mehreren GPS-Abtastdaten; in Schritt S203 als Reaktion auf die Erzeugung einer Kartenabgleichanforderung und den Erhalt eines Straßensegments, das dem letzten Standort des Fahrzeugs entspricht, Senden der Kartenabgleichanforderung zum Kartenabgleichen an einen Datenverarbeitungsknoten, der einer Straßensegmentgruppe entspricht, zu der das erhaltene Straßensegment gehört.
Vor dem Schritt S201 muss das Straßennetz im Internet der Fahrzeuge vorverarbeitet werden; Zeiträume können in Abhängigkeit von historischen Straßenverkehrsdaten unterteilt werden, sodass sich die durchschnittliche Fahrzeugdichte des Straßennetzes in jedem Zeitraum nicht abrupt ändert. Als Nächstes werden Straßensegmente in dem Straßennetz unter Berücksichtigung eines bestimmten Zeitraums unterteilt. Das Straßensegment in einer Karte des Internets der Fahrzeuge bezeichnet eine kleinste Einheit zum Definieren des Straßennetzes in einer Kartendatei des Internets der Fahrzeuge. Dem Fachmann ist unter Umständen klar, dass Straßensegmente in dem Straßennetz unter Verwendung eines dem Stand der Technik entsprechenden Verfahrens zum Unterteilen von Straßensegmenten unterteilt werden können. Gemäß der Ausführungsform der vorliegenden Erfindung werden Straßensegmente in dem Straßennetz in Abhängigkeit von historischen Straßennetzdaten wie zum Beispiel, ob die Anzahl von Fahrzeugen in jedem entstehenden Straßensegment nahe bei einem Durchschnittswert liegt, unterteilt.
Gemäß der Ausführungsform der vorliegenden Erfindung weist das Unterteilen von Straßensegmenten in dem Straßennetz in Abhängigkeit von historischen Straßenverkehrsdaten ferner auf: Anlegen von Statistiken über die Anzahl von Fahrzeugen in einem Straßensegment in dem Straßennetz in einem bestimmten Zeitraum und über die Gesamtzahl von Fahrzeugen in dem Straßensegment in dem Zeitraum, insbesondere über die Anzahl von Fahrzeugen in einem Straßensegment in dem Straßennetz in dem jeweiligen Zeitraum, und die Gesamtzahl von Fahrzeugen in dem Straßennetz in dem Zeitraum kann aus historischen Verkehrsüberwachungsdaten einer öffentlichen Informationsplattform erhalten werden; Berechnen einer Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum in Abhängigkeit von der Gesamtzahl von Fahrzeugen in dem Straßennetz und der Anzahl von Straßensegmenten; und Unterteilen des Straßensegments in dem Straßennetzwerk in Abhängigkeit von der Anzahl von Fahrzeugen in dem Straßensegment in dem Straßennetz in dem Zeitraum und der Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum.
Gemäß der Ausführungsform der vorliegenden Erfindung weist das Unterteilen des Straßensegments in dem Straßennetz in Abhängigkeit von der Anzahl von Fahrzeugen in dem Straßensegment in dem Straßennetz in dem Zeitraum und der Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum auf: Beurteilen, ob die Anzahl von Fahrzeugen in einem bestimmten Straßensegment in einem bestimmten Zeitraum nicht kleiner als die Straßensegment Durchschnittsfahrzeuganzahl ist; als Reaktion auf die Beurteilung, dass das Ergebnis nicht kleiner ist, ein gleichmäßiges Unterteilen des betreffenden Straßensegments in zwei Straßensegmente; iteratives Ausführen des Beurteilungsschrittes, bis die Anzahl von Fahrzeugen in jedem Straßensegment kleiner als die Straßensegment-Durchschnittsfahrzeuganzahl ist. 3 zeigt ein Flussdiagramm des Unterteilens von Straßensegmenten durch Verwenden eines rekursiven Verfahrens zur gleichmäßigen Aufteilung gemäß einer Ausführungsform der vorliegenden Erfindung. In Schritt S301 werden Statistiken über die Gesamtanzahl n von Straßensegmenten in einer Straßensegmentmenge N eines Straßennetzes angelegt, und es werden Statistiken über die Anzahl s_i(i = 1 ... n) von Fahrzeugen in jedem Segment in einem bestimmten Zeitraum in Abhängigkeit von historischen Straßenverkehrsdaten und der Gesamtanzahl
von Fahrzeugen in allen Straßensegmenten in dem Zeitraum angelegt. In Schritt S302 wird eine Straßensegment-Durchschnittsfahrzeuganzahl S/n im Zeitraum berechnet. In Schritt S303 wird ein Segment aus den n Straßensegmenten ausgewählt. In Schritt S304 wird eine Beurteilung dahingehend vorgenommen, ob die Anzahl von Fahrzeugen in dem Straßensegment größer als die Straßensegment-Durchschnittsfahrzeuganzahl ist. Wenn das Ergebnis der Beurteilung „Ja” lautet, wird das Straßensegment in Schritt S305 gleichmäßig in zwei Straßensegmente unterteilt. Wenn das Ergebnis der Beurteilung „Nein” lautet, geht der Ablauf zu Schritt S306 über, in dem eine Beurteilung dahingehend vorgenommen wird, ob die Anzahl von Fahrzeugen in jedem Straßensegment kleiner als die Straßensegment-Durchschnittsfahrzeuganzahl ist. Wenn das Ergebnis der Beurteilung „Ja” lautet, wird in Schritt S307 eine Straßensegmentmenge M ausgegeben. Wenn das Ergebnis der Beurteilung „Nein” lautet, kehrt der Ablauf zu Schritt S303 zurück und wiederholt die Schritte S303 bis S306, bis die Anzahl von Fahrzeugen in jedem Straßensegment kleiner als die Straßensegment-Durchschnittsfahrzeuganzahl ist.
4 zeigt ein Flussdiagramm des Unterteilens von Straßensegmenten gemäß einer weiteren Ausführungsform der vorliegenden Erfindung. In Schritt S401 werden Statistiken über die Gesamtanzahl n von Straßensegmenten in einer Straßensegmentmenge N in einem Straßennetz angelegt, und es werden Statistiken über die Anzahl s_i(i = 1 ... n) von Fahrzeugen in jedem Segment in einem bestimmten Zeitraum in Abhängigkeit von historischen Straßenverkehrsdaten und der Gesamtanzahl
von Fahrzeugen in allen Straßensegmenten in dem Zeitraum angelegt. In Schritt S402 wird eine Straßensegment-Durchschnittsfahrzeuganzahl S/n im Zeitraum berechnet. In Schritt S403 wird ein Segment i aus den n Straßensegmenten ausgewählt, wobei i = 1 ist. In Schritt S404 wird eine Beurteilung dahingehend vorgenommen, ob die Anzahl v von Fahrzeugen in dem Straßensegment größer als die Straßensegment-Durchschnittsfahrzeuganzahl ist. Wenn das Ergebnis der Beurteilung „Ja” lautet, wird in Schritt S405 C = ⌊v/m⌋ + 1 berechnet, wobei ⌊v/m⌋ für den abgerundeten Wert von v/m steht. Wenn das Ergebnis der Beurteilung „Nein” lautet, wird das Straßensegment in Schritt S406 in C Straßensegmente unterteilt, wobei i = i + 1 ist. In Schritt S407 wird eine Beurteilung dahingehend vorgenommen, ob i kleiner als n ist. Wenn das Ergebnis der Beurteilung „Ja” lautet, geht der Ablauf anschließend zu Schritt S403 über. Wenn das Ergebnis der Beurteilung „Nein” lautet, wird in Schritt S408 eine resultierende Straßensegmentmenge M ausgegeben. In Schritt S409 wird eine Beurteilung dahingehend vorgenommen, ob beliebige zwei benachbarte Straßensegmente existieren und die Bedingung „a + b < Straßensegment-Durchschnittsfahrzeuganzahl” erfüllt ist, wobei a und b die jeweiligen Anzahlen von Fahrzeugen sind, die in dem Zeitraum in den beiden Straßensegmenten vorliegen.
Wenn das Ergebnis der Beurteilung „Ja” lautet, werden in Schritt S410 die beiden benachbarten Straßensegmente zusammengeführt. Wenn das Ergebnis der Beurteilung „Nein” lautet, wird in Schritt S411 eine resultierende Straßensegmentmenge W ausgegeben.
Unterteilte Straßensegmente werden in Abhängigkeit von der Anzahl von Datenverarbeitungsknoten des Kartenabgleichs des Cluster-Servers und der Unähnlichkeit zwischen zwei unterteilten Straßensegmenten gruppiert, sodass die Anzahl von Straßensegmenten in jeder Gruppe nahezu gleich ist und die Unähnlichkeit zwischen jeweils zwei Straßensegmenten in einer Gruppe so hoch wie möglich ist, wodurch eine Straßensegmentmenge gebildet wird, die jedem Zeitraum entspricht.
Die Unähnlichkeit kann die folgenden drei Umstände in beliebigen zwei Straßensegmenten in jeder Straßensegmentgruppe unterscheiden, sodass die Unähnlichkeit zwischen beliebigen zwei Straßensegmenten in jeder Straßensegmentgruppe so hoch wie möglich ist: zwei Straßensegmente sind weit voneinander entfernt, d. h., die Bedingung ist erfüllt, dass die Entfernung zwischen beliebigen zwei Punkten der beiden Straßensegmente größer als 2δ ist (δ ist der größte Entfernungsoffsetfehler abgetasteter Daten); zwei Straßensegmente schneiden sich; zwei Straßensegmente verlaufen nahezu parallel.
Gemäß der Ausführungsform der vorliegenden Erfindung wird eine Straßensegmentmenge V = (v₁, v₂, v₃ ... v_n) angenommen, wobei die Anzahl von Datenverarbeitungsknoten in dem Cluster-Server, der den Kartenabgleich realisiert, N beträgt. Straßensegmente in V sind in N Gruppen unterteilt, und die Bedingung ist erfüllt, dass die Unähnlichkeit zwischen jeweils zwei Straßensegmenten in jeder Gruppe so hoch wie möglich ist, sodass die Möglichkeit des Auftretens von Aufgabenkonflikten so gering wie möglich ist, wenn Datenverarbeitungsknoten nach der kürzesten Strecke des Kartenabgleichs suchen.
Gemäß der Ausführungsform der vorliegenden Erfindung ist definiert, dass die Unähnlichkeit Dsim(v_i, v_j) zwischen beliebigen zwei Straßensegmenten v_i und v_i in S folgende Werte annimmt:
wobei sowohl M als auch m Konstanten mit einem Wert von größer 1 sind und M > m ist;
δ der maximale Entfernungsoffsetfehler von GPS-Abtastdaten ist;
F(A, B) ein Verfahren zum Berechnen des Fréchet-Abstands ist, das vielfach zum Berechnen der Ähnlichkeit zwischen zwei Kurven verwendet wird:
Angenommen, S ist ein kontinuierlicher zweidimensionaler Raum, wobei jede Kurve als kontinuierliche Kartenfunktion einer Reihe von Punkten von [0, 1] bis S betrachtet werden kann. Angenommen, A(x) und B(x) sind zwei Kurven in S, x ∊ [0, 1]. Und angenommen, α(t), β(t) ist jeweils eine monotone, stetige, nicht abnehmende Kartenfunktion t ∊ [0, 1] von [0, 1] bis [0, 1]. Dann kann der Fréchet-Abstand von Kurve A(x) und Kurve B(x) definiert werden als untere Begrenzung des durch alle möglichen Abbildungsbeziehungen α(t), β(t) berechneten maximalen Abstands zwischen zwei Kurven.
Bei Aufbau eines Optimierungsmodells zum Gruppieren von Straßensegmenten und Erfüllung der Bedingung, dass die Anzahl von Straßensegmenten in jeder Gruppe so durchschnittlich wie möglich ist, ist die Summe der Unähnlichkeit zwischen beliebigen zwei Straßensegmenten in jeder Gruppe ist so groß wie möglich.
Die Parameter in dem Optimierungsmodell sind nachfolgend definiert:
S – Straßensegmentmenge, ist ein Index.
N – Datenverarbeitungsknotenmenge, j ist ein Index.
Dsim(i, i') – Unähnlichkeitsfunktion zwischen dem Straßensegment i und dem Straßensegment i'.
Pair(.) – Menge aus allen Mengen mit einer Größe von 2 in einer Potenzmenge einer gegebenen Menge, k ist ein Index.
0_k – erstes Element in der Potenzmenge.
d_k – zweites Element in der Potenzmenge.
x_ji – Variable zwischen 0 und 1, wenn das Straßensegment i auf dem Datenverarbeitungsknoten j berechnet wird, dann x_ji = 1; anderenfalls x_ji = 0.
Wobei die Entscheidungsvariable x_ji unter Verwendung verschiedener Optimierungsalgorithmen berechnet werden kann, unter anderem mithilfe von Greedy-Algorithmen, k-Means, Simulated Annealing, genetischen Algorithmen, Tabusuche usw., die hier nicht erläutert werden. Dem Fachmann sollte klar sein, dass alle Optimierungsalgorithmen, mit deren Hilfe die Entscheidungsvariable erhalten werden kann, in den Schutzbereich der vorliegenden Erfindung fallen. Eine Beschreibung dieser Algorithmen ist unter http://baike.baidu.com/view/1660520.htm zu finden.
Eine Straßensegmentgruppenmenge wird gemäß dem oben erwähnten Optimierungsalgorithmus erhalten, jede Straßensegmentgruppe in der Straßensegmentgruppenmenge wird nach dem Zufallsprinzip einem Datenverarbeitungsknoten im Cluster-Server zugeteilt, eine Entsprechungsbeziehung zwischen jeder Straßensegmentgruppe und dem Datenverarbeitungsknoten wird registriert, und eine Kartenabgleichaufgabe, die zu mehreren Straßensegmenten in jeder Straßensegmentgruppe gehört, wird einem entsprechenden Datenverarbeitungsknoten zum Verarbeiten zugeteilt. Vor dem Zuteilen von Kartenabgleichaufgaben in Echtzeit ist es notwendig, eine Straßensegmentgruppenmenge, die einem aktuellen Zeitraum entspricht, und eine Entsprechungsbeziehung zwischen jeder Straßensegmentgruppe in der Straßensegmentgruppenmenge und einem Datenverarbeitungsknoten des Cluster-Servers zu ermitteln.
In Schritt S202 wird als Reaktion auf das Empfangen mehrerer GPS-Abtastdaten von einem Fahrzeug in Abhängigkeit von den mehreren GPS-Abtastdaten eine Kartenabgleichanforderung erzeugt. Während des Fahrens sendet das Fahrzeug GPS-Abtastpunktdaten an einen Zuteilungsknoten des Cluster-Servers, und in Abhängigkeit von mehreren zeitlich aufeinanderfolgenden GPS-Abtastpunktdaten wird auf dem Zuteilungsknoten eine Straßennetzabgleichanforderung erzeugt.
Gemäß der Ausführungsform der vorliegenden Erfindung kann sich die Reihenfolge der Schritte S201 und S202 ändern, d. h. Schritt S201 kann nach Schritt S202 ausgeführt werden.
In Schritt S203 wird als Reaktion auf das Erzeugen einer Kartenabgleichanforderung und den Erhalt eines Straßensegments, zu dem der letzte Standort des Fahrzeugs gehört, die Kartenabgleichanforderung an einen Datenverarbeitungsknoten zum Kartenabgleichen gesendet, der einer Straßensegmentgruppe entspricht, zu der das erhaltene Straßensegment gehört.
Gemäß der Ausführungsform der vorliegenden Erfindung ist ferner enthalten: als Reaktion auf das Erzeugen einer Kartenabgleichanforderung und den Nichterhalt eines Straßensegments des letzten Standortes des Fahrzeugs, Senden der Kartenabgleichanforderung zum Verarbeiten an einen zufälligen Datenverarbeitungsknoten. Insbesondere wird, wenn ein Datenverarbeitungsknoten einen Kartenabgleich auf die GPS-Abtastdaten des Fahrzeugs durchgeführt hat, ein Straßensegment des letzten Standortes des Fahrzeugs an den Zuteilungsknoten gesendet, auf dem Straßensegmentdaten registriert sind, die dem letzten Standort des Fahrzeugs entsprechen. Wenn eine Kartenabgleichanforderung des Fahrzeugs erzeugt und ein Straßensegment des letzten Standortes des Fahrzeugs gefunden wird, wird die Kartenabgleichanforderung zum Verarbeiten an einen Datenverarbeitungsknoten gesendet, der dem erhaltenen Straßensegment entspricht. Wenn kein Datenverarbeitungsknoten einen Kartenabgleich auf die GPS-Abtastdaten des Fahrzeugs durchgeführt hat, liegt auf dem Zuteilungsknoten kein Datensatz mit Straßensegmentdaten vor, zu denen der letzte Standort des Fahrzeugs gehört. Wenn eine Kartenabgleichanforderung des Fahrzeugs erzeugt und kein Straßensegment gefunden wird, zu dem der letzte Standort des Fahrzeugs gehört, wird die Kartenabgleichanforderung zum Verarbeiten an einen zufälligen Datenverarbeitungsknoten gesendet.

Gemäß einer Ausführungsform der vorliegenden Erfindung empfängt der Zuteilungsknoten mehrere GPS-Abtastpunktdaten eines Fahrzeuges mit einer Kennung XYZ001. Tabelle 1 zeigt Daten, die in einer Straßennetzabgleichanforderung enthalten sind, die in Abhängigkeit von GPS-Abtastpunktdaten erzeugt wird; Tabelle 2 zeigt einen Datensatz des letzten Standortes des Fahrzeugs gemäß der Ausführungsform der vorliegenden Erfindung, aus dem zu entnehmen ist, dass sich der letzte Standort des Fahrzeugs im Straßensegment 5 befindet; ferner, dass ein Datenverarbeitungsknoten 2 in Tabelle 3 gefunden wurde, der dem Straßensegment 5 entspricht. Daher wird die Straßennetzabgleichanforderung des Fahrzeugs zum Kartenabgleichen an den Datenverarbeitungsknoten 2 gesendet. Tabelle 1: Daten in einer Straßennetzabgleichanforderung gemäß der Ausführungsform der vorliegenden Erfindung

Fahrzeugkennung	X1-Länge	Y1-Breite	Datum/Uhrzeit
XYZ001	87,436	45,795	10.112003, 10:31:31
XYZ001	87,434	45,795	10.11.2003, 10:32:01
XYZ001	87,431	45,795	10.112003, 10:32:31

Tabelle 2: Daten über den letzten Fahrzeugstandort gemäß der Ausführungsform der vorliegenden Erfindung

Fahrzeugkennung	Letzter Standort
XYZ001	Straßensegment 5

Tabelle 3: Entsprechungsbeziehung zwischen Straßensegmentgruppe und Datenverarbeitungsknoten gemäß der Ausführungsform der vorliegenden Erfindung

Straßensegmentgruppe	Straßensegment	Datenverarbeitungsknoten
Gruppe 1	Straßensegmente 1, 3, 7	Knoten 1
Gruppe 2	Straßensegmente 2, 5, 8	Knoten 2
Gruppe 3	Straßensegmente 4, 6, 9	Knoten 3

Die obige Beschreibung der verschiedenen Ausführungsformen zur Realisierung des Verfahrens der vorliegenden Erfindung erfolgte unter Bezugnahme auf die beigefügten Zeichnungen. Dem Fachmann ist möglicherweise klar, dass das Verfahren im Softwaremodus, Hardwaremodus oder in einer Kombination aus Software und Hardware realisiert werden kann. Darüber hinaus ist dem Fachmann möglicherweise klar, dass durch Ausführen der verschiedenen Schritte in dem Verfahren in Software, Hardware oder in einer Kombination aus Software und Hardware eine Vorrichtung zum Zuteilen einer Kartenabgleichaufgabe auf einem Cluster-Server im Internet der Fahrzeuge bereitgestellt werden kann. Obwohl die Vorrichtung denselben Hardwareaufbau wie eine Mehrzweckverarbeitungseinheit hat, bewirkt die Funktionalität darin enthaltener Software, dass die Vorrichtung im Vergleich zu der Mehrzweckverarbeitungseinheit deutliche Unterscheidungsmerkmale zeigt und dadurch eine Vorrichtung der verschiedenen Ausführungsformen der vorliegenden Erfindung bildet.
Unter Bezugnahme auf 5 folgt nachstehend eine Beschreibung einer Vorrichtung 500 zum Zuteilen einer Kartenabgleichaufgabe auf einem Cluster-Server im Internet der Fahrzeuge gemäß der Ausführungsform der vorliegenden Erfindung. Die Vorrichtung 500 weist eine Vorrichtung zum Zuteilen einer Kartenabgleichaufgabe auf einem Cluster-Server im Internet der Fahrzeuge auf, aufweisend: ein Ermittlungsmodul 501, das so konfiguriert ist, dass eine Straßensegmentgruppenmenge, die einem bestimmten Zeitraum entspricht, und eine Entsprechungsbeziehung zwischen jeder Straßensegmentgruppe in der Straßensegmentgruppenmenge und einem Datenverarbeitungsknoten des Cluster-Servers ermittelt wird, wobei die Straßensegmentgruppe eine Gruppe von Straßensegmenten ist, die gemäß der Anzahl von Datenverarbeitungsknoten des Cluster-Servers und der Unähnlichkeit zwischen unterteilten Straßensegmenten in einem Straßennetz gruppiert sind; ein Abgleichanforderungs-Erzeugungsmodul 502, das so konfiguriert ist, dass als Reaktion auf ein Empfangen mehrerer GPS-Abtastdaten von einem Fahrzeug in Abhängigkeit von den mehreren GPS-Abtastdaten eine Kartenabgleichanforderung erzeugt wird; und ein Zuteilungsmodul 503, das so konfiguriert ist, dass als Reaktion auf die Erzeugung einer Kartenabgleichanforderung und die Registrierung eines Straßensegments, das dem letzten Standort des Fahrzeugs entspricht, die Kartenabgleichanforderung zum Kartenabgleichen an einen Datenverarbeitungsknoten gesendet wird, der einer Straßensegmentgruppe entspricht, zu der das erhaltene Straßensegment gehört.
Gemäß der Ausführungsform der vorliegenden Erfindung entstehen die unterteilten Straßensegmente aus dem Unterteilen von Straßensegmenten in dem Straßennetz in Abhängigkeit von historischen Straßenverkehrsdaten wie zum Beispiel, ob die Anzahl von Fahrzeugen in jedem unterteilten Straßensegment nahe bei einem Durchschnittswert liegt.
Gemäß der Ausführungsform der vorliegenden Erfindung weist das Unterteilen von Straßensegmenten in dem Netzwerk in Abhängigkeit von historischen Straßenverkehrsdaten auf: Anlegen von Statistiken über die Anzahl von Fahrzeugen in einem Straßensegment in dem Straßennetz in einem bestimmten Zeitraum und über die Gesamtzahl von Fahrzeugen in dem Straßensegment in dem Zeitraum; Berechnen einer Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum in Abhängigkeit von der Gesamtzahl von Fahrzeugen in dem Straßennetz und der Anzahl von Straßensegmenten; und Unterteilen des Straßensegments in dem Straßennetzwerk in Abhängigkeit von der Anzahl von Fahrzeugen in dem Straßensegment in dem Straßennetz in dem Zeitraum und der Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum.
Gemäß der Ausführungsform der vorliegenden Erfindung weist das Unterteilen des Straßensegments in dem Straßennetz in Abhängigkeit von der Anzahl von Fahrzeugen in dem Straßensegment in dem Straßennetz in dem Zeitraum und der Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum auf: Beurteilen, ob die Anzahl von Fahrzeugen in einem bestimmten Straßensegment in einem bestimmten Zeitraum nicht kleiner als die Straßensegment-Durchschnittsfahrzeuganzahl ist; als Reaktion auf die Beurteilung, dass das Ergebnis nicht kleiner ist, ein gleichmäßiges Unterteilen des betreffenden Straßensegments in zwei Straßensegmente; iteratives Ausführen des Beurteilungsschrittes, bis die Anzahl von Fahrzeugen in jedem Straßensegment kleiner als die Straßensegment-Durchschnittsfahrzeuganzahl ist.
Gemäß der Ausführungsform der vorliegenden Erfindung kann die Unähnlichkeit die folgenden drei Umstände in beliebigen zwei Straßensegmenten in jeder Straßensegmentgruppe unterscheiden, sodass die Unähnlichkeit zwischen beliebigen zwei Straßensegmenten in jeder Straßensegmentgruppe so hoch wie möglich ist: zwei Straßensegment sind weit voneinander entfernt, d. h., die Bedingung ist erfüllt, dass die Entfernung zwischen beliebigen zwei Punkten zweier Straßensegmente größer als 2δ ist (δ ist der größte Entfernungsoffsetfehler abgetasteter Daten); zwei Straßensegmente schneiden sich; zwei Straßensegmente verlaufen nahezu parallel.
Gemäß der Ausführungsform der vorliegenden Erfindung ist das Zuteilungsmodul 504 ferner konfiguriert, um: als Reaktion auf das Erzeugen einer Kartenabgleichanforderung und die Nichtregistrierung eines Straßensegments, das dem letzten Standort des Fahrzeugs entspricht, die Kartenabgleichanforderung zum Verarbeiten an einen zufälligen Datenverarbeitungsknoten zu senden.
Ein konkretes Realisierungsverfahren eines jeden der oben genannten Module kann auf die ausführliche Beschreibung des Verfahrens zum Zuteilen einer Kartenabgleichaufgabe auf einem Cluster-Server im Internet der Fahrzeuge gemäß der Ausführungsform der vorliegenden Erfindung Bezug nehmen, was hier nicht ausführlich beschrieben wird.
Die Flussdiagramme und Blockschemata in den Figuren veranschaulichen die Architektur, Funktionalität und Wirkungsweise möglicher Realisierungsformen von Systemen, Verfahren und Computerprogrammprodukten gemäß verschiedenen Ausführungsformen der vorliegenden Erfindung. Dementsprechend kann jeder einzelne Block in den Flussdiagrammen bzw. in den Blockschemata ein Modul, ein Segment oder einen Teil des Codes darstellen, der eine oder mehrere ausführbare Anweisungen zur Realisierung der angegebenen Logikfunktion bzw. Logikfunktionen aufweist. Außerdem sollte beachtet werden, dass bei einigen alternativen Realisierungsformen die in dem Block angegebenen Funktionen in einer anderen Reihenfolge als der ausgeführt werden können, die in den Figuren angegeben ist. Beispielsweise können zwei hintereinander aufgeführte Blöcke tatsächlich im Wesentlichen gleichzeitig ausgeführt werden, oder die Blöcke können je nach der damit verbundenen Funktionalität manchmal in umgekehrter Reihenfolge ausgeführt werden. Darüber hinaus ist anzumerken, dass jeder Block der dargestellten Blockschemata und/oder des dargestellten Flussdiagramms sowie Kombinationen von Blöcken in den dargestellten Blockschemata und/oder im dargestellten Flussdiagramm mithilfe von bestimmten Zwecken dienenden, hardwaregestützten Systemen zur Ausführung der angegebenen Funktionen bzw. Aktionen oder mithilfe von Kombinationen aus bestimmten Zwecken dienender Hardware und Computeranweisungen realisiert werden kann bzw. können.
Die Beschreibungen der verschiedenen Ausführungsformen der vorliegenden Erfindung sollen der Veranschaulichung dienen, sind jedoch nicht als vollständig oder auf die Erfindung in der offenbarten Form beschränkt gedacht. Für den Fachmann sind viele Modifikationen und Variationen denkbar, ohne dass diese eine Abweichung vom Schutzbereich und Gedanken der beschriebenen Ausführungsformen darstellen würden. Die hier verwendete Terminologie wurde gewählt, um die Grundgedanken der Ausführungsformen, die praktische Anwendung bzw. die technische Verbesserung gegenüber den auf dem Markt vorgefundenen Technologien auf bestmögliche Weise zu erläutern bzw. anderen mit entsprechenden Fachkenntnissen das Verständnis der hier offenbarten Ausführungsform zu ermöglichen.

Claims

Verfahren zum Zuteilen einer Kartenabgleichaufgabe auf einem Cluster-Server im Internet der Fahrzeuge, aufweisend: Ermitteln einer Straßensegmentgruppenmenge, die einem bestimmten Zeitraum entspricht, und einer Entsprechungsbeziehung zwischen jeder Straßensegmentgruppe in der Straßensegmentgruppenmenge und einem Datenverarbeitungsknoten des Cluster-Servers, wobei die Straßensegmentgruppe eine Gruppe von Straßensegmenten ist, die gemäß der Anzahl von Datenverarbeitungsknoten des Cluster-Servers und der Unähnlichkeit zwischen unterteilten Straßensegmenten in einem Straßennetz gruppiert sind; als Reaktion auf den Empfang mehrerer GPS-Abtastdaten von einem Fahrzeug ein Erzeugen einer Kartenabgleichanforderung in Abhängigkeit von den mehreren GPS-Abtastdaten; und als Reaktion auf die Erzeugung einer Kartenabgleichanforderung und den Erhalt eines Straßensegments, zu dem der letzte Standort des Fahrzeugs gehört, Senden der Kartenabgleichanforderung zum Kartenabgleichen an einen Datenverarbeitungsknoten, der einer Straßensegmentgruppe entspricht, zu der das erhaltene Straßensegment gehört.
Verfahren nach Anspruch 1, wobei die unterteilten Straßensegmente aus dem Unterteilen von Straßensegmenten in dem Straßennetz in Abhängigkeit von historischen Straßenverkehrsdaten entstehen, wie zum Beispiel, ob die Anzahl von Fahrzeugen in jedem unterteilten Straßensegment nahe bei einem Durchschnittswert liegt.
Verfahren nach Anspruch 2, wobei das Unterteilen von Straßensegmenten in dem Straßennetz in Abhängigkeit von historischen Straßenverkehrsdaten aufweist: Anlegen von Statistiken über die Anzahl von Fahrzeugen in einem Straßensegment in dem Straßennetz in einem bestimmten Zeitraum und über die Gesamtzahl von Fahrzeugen in dem Straßensegment in dem Zeitraum; Berechnen einer Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum in Abhängigkeit von der Gesamtzahl von Fahrzeugen in dem Straßennetz und der Anzahl von Straßensegmenten; und Unterteilen des Straßensegments in dem Straßennetzwerk in Abhängigkeit von der Anzahl von Fahrzeugen in dem Straßensegment in dem Straßennetz in dem Zeitraum und der Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum.
Verfahren nach Anspruch 2, wobei das Unterteilen des Straßensegments in dem Straßennetzwerk in Abhängigkeit von der Anzahl von Fahrzeugen in dem Straßensegment in dem Straßennetz in dem Zeitraum und der Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum aufweist: Beurteilen, ob die Anzahl von Fahrzeugen in einem bestimmten Straßensegment in einem bestimmten Zeitraum nicht kleiner als die Straßensegment-Durchschnittsfahrzeuganzahl ist; als Reaktion auf die Beurteilung, dass das Ergebnis nicht kleiner ist, ein gleichmäßiges Unterteilen des betreffenden Straßensegments in zwei Straßensegmente; und iteratives Ausführen des Beurteilungsschrittes, bis die Anzahl von Fahrzeugen in jedem Straßensegment kleiner als die Straßensegment-Durchschnittsfahrzeuganzahl ist.
Verfahren nach Anspruch 1, wobei die Unähnlichkeit die folgenden drei Umstände in beliebigen zwei Straßensegmenten in jeder Straßensegmentgruppe unterscheiden kann, sodass die Unähnlichkeit zwischen beliebigen zwei Straßensegmenten in jeder Straßensegmentgruppe so hoch wie möglich ist: zwei Straßensegmente sind weit voneinander entfernt; zwei Straßensegmente schneiden sich; zwei Straßensegmente verlaufen nahezu parallel.
Verfahren nach Anspruch 1, ferner aufweisend: als Reaktion auf das Erzeugen einer Kartenabgleichanforderung und den Nichterhalt eines Straßensegments, zu dem der letzte Standort des Fahrzeugs gehört, Senden der Kartenabgleichanforderung zum Verarbeiten an einen zufälligen Datenverarbeitungsknoten.
Vorrichtung zum Zuteilen einer Kartenabgleichaufgabe auf einem Cluster-Server im Internet der Fahrzeuge, aufweisend: ein Ermittlungsmodul, das so konfiguriert ist, dass eine Straßensegmentgruppenmenge, die einem bestimmten Zeitraum entspricht, und eine Entsprechungsbeziehung zwischen jeder Straßensegmentgruppe in der Straßensegmentgruppenmenge und einem Datenverarbeitungsknoten des Cluster-Servers ermittelt wird, wobei die Straßensegmentgruppe eine Gruppe von Straßensegmenten ist, die gemäß der Anzahl von Datenverarbeitungsknoten des Cluster-Servers und der Unähnlichkeit zwischen unterteilten Straßensegmenten in einem Straßennetz gruppiert sind; ein Abgleichanforderungs-Erzeugungsmodul, das so konfiguriert ist, dass als Reaktion auf den Empfang mehrerer GPS-Abtastdaten von einem Fahrzeug in Abhängigkeit von den mehreren GPS-Abtastdaten eine Kartenabgleichanforderung erzeugt wird; und ein Zuteilungsmodul, das so konfiguriert ist, dass als Reaktion auf die Erzeugung einer Kartenabgleichanforderung und Erhalten eines Straßensegments, zu dem der letzte Standort des Fahrzeugs gehört, die Kartenabgleichanforderung zum Kartenabgleichen an einen Datenverarbeitungsknoten gesendet wird, der einer Straßensegmentgruppe entspricht, zu der das erhaltene Straßensegment gehört.
Vorrichtung nach Anspruch 7, wobei die unterteilten Straßensegmente aus dem Unterteilen von Straßensegmenten in dem Straßennetz in Abhängigkeit von historischen Straßenverkehrsdaten entstehen, wie zum Beispiel, ob die Anzahl von Fahrzeugen in jedem unterteilten Straßensegment nahe bei einem Durchschnittswert liegt.
Vorrichtung nach Anspruch 8, wobei das Unterteilen von Straßensegmenten in dem Straßennetz in Abhängigkeit von historischen Straßenverkehrsdaten aufweist: Anlegen von Statistiken über die Anzahl von Fahrzeugen in einem Straßensegment in dem Straßennetz in einem bestimmten Zeitraum und über die Gesamtzahl von Fahrzeugen in dem Straßensegment in dem Zeitraum; Berechnen einer Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum in Abhängigkeit von der Gesamtzahl von Fahrzeugen in dem Straßennetz und der Anzahl von Straßensegmenten; und Unterteilen des Straßensegments in dem Straßennetzwerk in Abhängigkeit von der Anzahl von Fahrzeugen in dem Straßensegment in dem Straßennetz in dem Zeitraum und der Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum.
Vorrichtung nach Anspruch 9, wobei das Unterteilen des Straßensegments in dem Straßennetzwerk in Abhängigkeit von der Anzahl von Fahrzeugen in dem Straßensegment in dem Straßennetz in dem Zeitraum und der Straßensegment-Durchschnittsfahrzeuganzahl in dem Zeitraum aufweist: Beurteilen, ob die Anzahl von Fahrzeugen in einem bestimmten Straßensegment in einem bestimmten Zeitraum nicht kleiner als die Straßensegment-Durchschnittsfahrzeuganzahl ist; als Reaktion auf die Beurteilung, dass das Ergebnis nicht kleiner ist, ein gleichmäßiges Unterteilen des betreffenden Straßensegments in zwei Straßensegmente; und iteratives Ausführen des Beurteilungsschrittes, bis die Anzahl von Fahrzeugen in jedem Straßensegment kleiner als die Straßensegment-Durchschnittsfahrzeuganzahl ist.
Vorrichtung nach Anspruch 7, wobei die Unähnlichkeit zwischen den unterteilten Straßensegmenten die folgenden drei Umstände in beliebigen zwei Straßensegmenten in jeder Straßensegmentgruppe unterscheiden kann, sodass die Unähnlichkeit zwischen beliebigen zwei Straßensegmenten in jeder Straßensegmentgruppe so hoch wie möglich ist: zwei Straßensegmente sind weit voneinander entfernt; zwei Straßensegmente schneiden sich; zwei Straßensegmente verlaufen nahezu parallel.
Vorrichtung nach Anspruch 7, wobei das Zuteilungsmodul ferner konfiguriert ist, um: als Reaktion auf das Erzeugen einer Kartenabgleichanforderung und den Nichterhalt eines Straßensegments, zu dem der letzte Standort des Fahrzeugs gehört, die Kartenabgleichanforderung zum Verarbeiten an einen zufälligen Datenverarbeitungsknoten zu senden.
Computerprogramm das Programmcode aufweist, der so gestaltet ist, dass die Verfahrensschritte eines beliebigen der Ansprüche 1 bis 6 durchgeführt werden, wenn das Programm auf einem Computer ausgeführt wird.