ROUTE PLANNING METHOD AND DEVICE FOR NAVIGATION SYSTEM AND STORAGE MEDIUM

• US 20160334237A1
• Filed: 01/19/2015
• Published: 11/17/2016
• Est. Priority Date: 08/22/2014
• Status: Active Grant

• Current Assignee: Xi'An Zhongxing New Software Co., Ltd. (ZTE Corporation)
• Original Assignee: ZTE Corporation
• Inventors: Wang, Lixue
• Granted Patent: US 10,119,829 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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/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:

dividing an actual geographic space into grids, the grids being cells of a cellular network;

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

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

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

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

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

2. The method according to claim 1, further comprising:

before the modelling an inter-cell adjacency according to the handover record,

filtering the handover record according to a pre-set filtering solution.

3. The method according to claim 1, 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.

4. The method according to claim 3, wherein the modelling the inter-cell adjacency within the period of time according to the snapshot comprises:

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, or a duration needed for transfer between two cells.

5. 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.

6. A route planning device for a navigation system, comprising a grid modelling module, a grid path finding module, and a path converting module, wherein

the grid modelling module is configured for:

dividing an actual geographic space into grids, the grids being cells of a cellular network;

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

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

the grid path finding module is configured for;

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

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

the path converting module is configured for;

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

7. The device according to claim 6, wherein the grid modelling module is further configured for:

filtering the handover record according to a pre-set filtering solution.

8. The device according to claim 6, wherein the grid modelling module comprises:

a trajectory extracting sub-module configured for;

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

a snapshot managing sub-module configured for;

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

a modelling sub-module configured for;

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

9. The device according to claim 8, wherein the modelling sub-module is further configured for:

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, or a duration needed for transfer between two cells.

10. The device according to claim 6, wherein the path converting module comprises:

a Geographic Information System (GIS) map matching sub-module configured for;

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

/or

a satellite map matching sub-module configured for;

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

11. 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:

dividing an actual geographic space into grids, the grids being cells of a cellular network;

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

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

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

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

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

12. The storage medium according to claim 11, wherein the method further comprises:

before the modelling an inter-cell adjacency according to the handover record,

filtering the handover record according to a pre-set filtering solution.

13. The storage medium according to claim 11, 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.

14. The storage medium according to claim 13, wherein the modelling the inter-cell adjacency within the period of time according to the snapshot comprises:

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, or a duration needed for transfer between two cells.

15. The storage medium according to claim 11, 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.