# US 10,119,829 B2 · Route planning method and device for navigation system and storage medium

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,119,829 B2
- Document ID: US10119829B2
- Status: Granted
- Kind: B2
- Application number: 15/112,512
- Filed: 2015-01-19
- Published: 2016-11-17
- Granted: 2018-11-06
- Earliest claimed: 2014-08-22
- Assignees: Xi'an Zhongxing New Software Co., Ltd.
- Applicants: ZTE Corporation
- Inventors: Lixue Wang
- Web page: https://patentgrep.com/patent/US10119829B2

## CPC

- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G08G 1/0968: Systems involving transmission of navigation instructions to the vehicle
- G08G 1/096844: {where the complete route is dynamically recomputed based on new data}
- H04W 4/02: Services making use of location information
- H04W 4/023: {using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds}
- H04W 4/024: Guidance services
- H04W 4/029: Location-based management or tracking services
- H04W 4/40: for vehicles, e.g. vehicle-to-pedestrians [V2P]
- H04W 8/18: Processing of user or subscriber data, e.g. subscribed services, user preferences or user profiles; Transfer of user or subscriber data
- H04W 36/326: {by proximity to another entity}
- H04L 67/06: specially adapted for file transfer, e.g. file transfer protocol [FTP]
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 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.

### Claim 4 (depends on 3)

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.

### Claim 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.

### Claim 6 (depends on 5)

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.