Route planning method and device for navigation system and storage medium

• US 10,119,829 B2
• Filed: 01/19/2015
• Issued: 11/06/2018
• Est. Priority Date: 08/22/2014
• Status: Active Grant

• Current Assignee: Xi'An Zhongxing New Software Co., Ltd. (ZTE Corporation)
• Original Assignee: Xi'An Zhongxing New Software Co., Ltd. (ZTE Corporation)
• Inventors: Wang, Lixue
• Primary Examiner(s): Cass, Jean Paul
• Application Number:
  US15/112,512
• Publication Number:
  US 20160334237A1
• Time in Patent Office: 1,387 Days
• Field of Search: None
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G08G 1/0968 Systems involving transmission of navigation instructions to the vehicle
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04W 36/32 by location or mobility data, e.g. speed data
• CPC Class Codes: H04W 36/326 by proximity to another entity
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/40 for vehicles, e.g. vehicle-to-pedestrians [V2P]
• CPC Class Codes: H04W 8/18 Processing of user or subscriber data, e.g. subscribed services, user preferences or user profiles; Transfer of user or subscriber data

Abstract

Disclosed is a route planning method for a navigation system. The method comprises: performing grid processing on an actual geographic space, the grids being cells in a cellular network, acquiring a mobile station cell handover record, and creating a cell adjacency model according to the mobile station cell handover record; making a source and a destination in the actual geographic space correspond to a source grid and a destination grid after the grid processing, and determining a grid-level path from the source grid to the destination grid according to the inter-grid adjacency model; and converting the grid-level path into an actual route from the source to the destination in the actual geographic space. Also disclosed is a route planning device for a navigation system.

Claims

1. A route planning method for a navigation system, comprising:

acquiring a handover record of inter-cell handovers of mobile stations; and

modelling an inter-cell adjacency according to the handover record, wherein an actual geographic space is divided into a grid of cells of a cellular network;

mapping a departure point and a destination point in the actual geographic space respectively to a departure cell and a destination cell; and

determining, according to the modelled inter-cell adjacency, a grid-level path from the departure cell to the destination cell; and

converting the grid-level path into an actual route from the departure point to the destination point in the actual geographic space,

wherein the acquiring a handover record of inter-cell handovers of mobile stations comprises;

reading a file recording inter-cell handovers of mobile stations stored in a dedicated File Transfer Protocol (FTP) server by a signalling collecting platform of a mobile operator, and acquiring handover records from the file,

wherein the method further comprises, before the modelling an inter-cell adjacency according to the handover record;

filtering the handover record by at least one of;

deleting a record related to a number of a mobile station with no mobility;

retaining only records related to specific mobile station numbers;

or

deleting a handover record when a cell identifier in the handover record is not one of cell identifiers loaded in memory,

wherein the modelling an inter-cell adjacency according to the handover record comprises;

extracting trajectories of the mobile stations according to the handover record;

setting a set of all the trajectories within a period of time as a snapshot; and

modelling the inter-cell adjacency within the period of time according to the snapshot by;

establishing, according to the snapshot, a weighted directed graph, with base stations of all the cells as vertices, inter-cell adjacencies as edges, and with an inter-cell adjacency index as a weight of an edge,

wherein the inter-cell adjacency index is a probability of transfer between two cells, and

wherein the probability is a number of records of transfer from a source cell to a target cell divided by a number of all records of transfer from the source cell.

2. The method according to claim 1, wherein the converting the grid-level path into an actual route from the departure point to the destination point in the actual geographic space comprises:

converting the grid-level path into an actual route from the departure point to the destination point in a Geographic Information System (GIS) map; and

/or

converting the grid-level path into an actual route from the departure point to the destination point in a satellite map.

3. A route planning device for a navigation system, comprising:

a processor; and

memory storing instructions executable by the processor, wherein the processor

is configured for performing a route planning method for a navigation system, the method comprising;

acquiring a handover record of inter-cell handovers of mobile stations; and

modelling an inter-cell adjacency according to the handover record, wherein an actual geographic space is divided into a grid of cells of a cellular network;

mapping a departure point and a destination point in the actual geographic space respectively to a departure cell and a destination cell; and

determining, according to the modelled inter-cell adjacency, a grid-level path from the departure cell to the destination cell; and

converting the grid-level path into an actual route from the departure point to the destination point in the actual geographic space,

wherein the acquiring a handover record of inter-cell handovers of mobile stations comprises;

reading a file recording inter-cell handovers of mobile stations stored in a dedicated File Transfer Protocol (FTP) server by a signalling collecting platform of a mobile operator, and acquiring handover records from the file,

wherein the method further comprises, before the modelling an inter-cell adjacency according to the handover record;

filtering the handover record by at least one of;

deleting a record related to a number of a mobile station with no mobility;

retaining only records related to specific mobile station numbers;

or

deleting a handover record when a cell identifier in the handover record is not one of cell identifiers loaded in memory,

wherein the modelling an inter-cell adjacency according to the handover record comprises;

extracting trajectories of the mobile stations according to the handover record;

setting a set of all the trajectories within a period of time as a snapshot; and

modelling the inter-cell adjacency within the period of time according to the snapshot by;

establishing, according to the snapshot, a weighted directed graph, with base stations of all the cells as vertices, inter-cell adjacencies as edges, and with an inter-cell adjacency index as a weight of an edge,

wherein the inter-cell adjacency index is a probability of transfer between two cells, and

wherein the probability is a number of records of transfer from a source cell to a target cell divided by a number of all records of transfer from the source cell.

4. The device according to claim 3, wherein the converting the grid-level path into an actual route from the departure point to the destination point in the actual geographic space comprises:

converting the grid-level path into an actual route from the departure point to the destination point in a Geographic Information System (GIS) map; and

/or

converting the grid-level path into an actual route from the departure point to the destination point in a satellite map.

5. A non-transitory computer-readable storage medium, storing therein computer executable instructions for executing a route planning method for a navigation system, the method comprising:

acquiring a handover record of inter-cell handovers of mobile stations; and

modelling an inter-cell adjacency according to the handover record, wherein an actual geographic space is divided into a grid of cells of a cellular network;

mapping a departure point and a destination point in the actual geographic space respectively to a departure cell and a destination cell; and

determining, according to the modelled inter-cell adjacency, a grid-level path from the departure cell to the destination cell; and

converting the grid-level path into an actual route from the departure point to the destination point in the actual geographic space,

wherein the acquiring a handover record of inter-cell handovers of mobile stations comprises;

reading a file recording inter-cell handovers of mobile stations stored in a dedicated File Transfer Protocol (FTP) server by a signalling collecting platform of a mobile operator, and acquiring handover records from the file,

wherein the method further comprises, before the modelling an inter-cell adjacency according to the handover record;

filtering the handover record by at least one of;

deleting a record related to a number of a mobile station with no mobility;

retaining only records related to specific mobile station numbers;

or

deleting a handover record when a cell identifier in the handover record is not one of cell identifiers loaded in memory,

wherein the modelling an inter-cell adjacency according to the handover record comprises;

extracting trajectories of the mobile stations according to the handover record;

setting a set of all the trajectories within a period of time as a snapshot; and

modelling the inter-cell adjacency within the period of time according to the snapshot by;

establishing, according to the snapshot, a weighted directed graph, with base stations of all the cells as vertices, inter-cell adjacencies as edges, and with an inter-cell adjacency index as a weight of an edge,

wherein the inter-cell adjacency index is a probability of transfer between two cells, and

wherein the probability is a number of records of transfer from a source cell to a target cell divided by a number of all records of transfer from the source cell.

6. The non-transitory computer-readable storage medium according to claim 5, wherein the converting the grid-level path into an actual route from the departure point to the destination point in the actual geographic space comprises:

converting the grid-level path into an actual route from the departure point to the destination point in a Geographic Information System (GIS) map; and

/or

converting the grid-level path into an actual route from the departure point to the destination point in a satellite map.