System and method for providing traffic information using operational data of a wireless network
Abstract
A system to extract information from the movement of vehicles using operational data for mobile stations operating in a previously existing wireless telephone communications network, including the system: a processor module, logically coupled to the existing wireless telephone communications network, which can operate to generate a plurality of traffic data records based on operational data obtained from the existing wireless telephone communications network, each traffic data record identifying a position within the cellular sector coverage area of the wireless telephone communications network for one of the mobile stations at a specific time; and a motion detection and filtration module, logically coupled to the processor module, which can operate to generate a motion record in response to processing a pair of traffic data records associated with a wireless communication activity by the same mobile station , including each movement record first and second positions within the wireless telephone communications network for the same mobile station at different times; an analysis configuration module, logically coupled to at least one database including network information for the existing wireless telephone communications network and geographic road information within the geographical area covered by the wireless telephone communications network, which can operate to generate the plurality of traffic routes by processing network information and geographic road information; and a traffic modulator module, logically coupled to the analysis configuration module, which can operate to generate a plurality of data records by processing motion records of the mobile stations within a context provided by the plurality of traffic routes, including each motion record first and second positions within the wireless telephone communications network for the same mobile station at different times, Each data record includes an identification of the average speed of a vehicle along a specific route of the traffic routes at a specific time, where the identification of the specific route of the traffic routes includes performing a probabilistic analysis to identify one or more of the traffic routes most likely traveled by the vehicle.

Term
Term ended
Projected expiry passed 13 September 2022, 4 years ago.
- Priority
- Filed
- Published
- Projected expiry
- Today
15 claims: 2 independent, 13 dependent
- 1ES 2 309 178 T3 REIVINDICACIONES 1. Un sistema para extraer información del movimiento de vehículos usando datos operativos para estaciones móviles que operan en una red de comunicaciones telefónicas inalámbricas previamente existente, incluyendo el sistema:un módulo procesador, acoplado lógicamente a la red de comunicaciones telefónicas inalámbricas existente, que puede operar para generar una pluralidad de registros de datos de tráfico en base a datos operativos obtenidos de la red de comunicaciones telefónicas inalámbricas existente, identificando cada registro de datos de tráfico una posición dentro de la zona de cobertura de sector celular de la red de comunicaciones telefónicas inalámbricas para una de las estaciones móviles en un tiempo concreto;y un módulo de detección y filtración de movimiento, acoplado lógicamente al módulo procesador, que puede operar para generar un registro de movimiento en respuesta a procesar un par de los registros de datos de tráfico asociados con una actividad de comunicación inalámbrica por una misma estación móvil, incluyendo cada registro de movimiento posiciones primera y segunda dentro de la red de comunicaciones telefónicas inalámbricas para la misma estación móvil en tiempos diferentes;un módulo de configuración de análisis, acoplado lógicamente a al menos una base de datos incluyendo información de red para la red de comunicaciones telefónicas inalámbricas existente e información geográfica de carreteras dentro de la zona geográfica cubierta por la red de comunicaciones telefónicas inalámbricas, que puede operar para generar la pluralidad de rutas de tráfico procesando la información de red y la información geográfica de carreteras;y un módulo modulador de tráfico, acoplado lógicamente al módulo de configuración de análisis, que puede operar para generar una pluralidad de registros de datos procesando registros de movimiento de las estaciones móviles dentro de un contexto proporcionado por la pluralidad de rutas de tráfico, incluyendo cada registro de movimiento posiciones primera y segunda dentro de la red de comunicaciones telefónicas inalámbricas para la misma estación móvil en tiempos diferentes, incluyendo cada registro de datos una identificación de la velocidad media de un vehículo a lo largo de una ruta concreta de las rutas de tráfico en un tiempo específico, donde la identificación de la ruta concreta de las rutas de tráfico incluye realizar un análisis probabilístico para identificar una o varias de las rutas de tráfico más probablemente recorridas por el vehículo.
- 2El sistema de la reivindicación 1, donde el módulo procesador puede operar además para proteger el número identificador de estación móvil que identifica una de las estaciones móviles de cada uno de los registros de datos de tráfico como información confidencial.
- 3El sistema de la reivindicación 1 incluyendo además un módulo de configuración y supervisión, acoplado lógicamente al módulo procesador y al módulo de detección y filtración de movimiento, operativo para configurar la actividad operativa del módulo procesador y el módulo de detección y filtración de movimiento y para supervisar la actividad operativa del módulo procesador y el módulo de detección y filtración de movimiento.
- 4El sistema de la reivindicación 1 donde el módulo procesador incluye:una pluralidad de interfaces de archivo para extraer datos de movimiento y posición de los datos operativos para las estaciones móviles obtenidos de la red de comunicaciones telefónicas inalámbricas;y un motor de análisis acoplado lógicamente a las interfaces para generar la pluralidad de registros de datos de tráfico en respuesta a los datos de movimiento y posición extraídos.
- 5El sistema de la reivindicación 1 incluyendo además una interface HTTP, acoplada lógicamente al módulo de filtración y detección de movimiento, adaptado para comunicar cada registro de movimiento a un nodo de análisis de datos para facilitar una evaluación de las características del tráfico de vehículos en una zona de tráfico de vehículos asociada con la zona de cobertura de sector celular de la red de comunicaciones telefónicas inalámbricas.
- 6El sistema de la reivindicación 1 incluyendo además un módulo de determinación del sistema de posición móvil, acoplado lógicamente al módulo modulador de tráfico y un sistema de posicionamiento móvil para la red de comunicaciones telefónicas inalámbricas, que puede operar para pedir al sistema de posicionamiento móvil datos de posición de estación móvil si la velocidad media a lo largo de la ruta de tráfico asociada con el registro de datos concreto en el tiempo específico se basa en un número de los registros de movimiento menor que un valor umbral.
- 7El sistema de la reivindicación 1 incluyendo además una base de datos de rutas, acoplada lógicamente al módulo modulador de tráfico, que puede operar para almacenar la pluralidad de registros de datos para acceso por un usuario final.
- 8Un método para determinar velocidades de tráfico a lo largo de rutas de tráfico en base al movimiento de estaciones móviles que operan dentro de una red de comunicaciones telefónicas inalámbricas previamente existente incluyendo una zona de cobertura de sector celular que se solapa con las rutas de tráfico y que tiene una pluralidad de sectores celulares, incluyendo los pasos de:ES 2 309 178 T3 crear una pluralidad de rutas de tráfico entre cualesquiera dos de los sectores celulares procesando información de zona de cobertura de sectores celulares para la red de comunicaciones telefónicas inalámbricas existente e información geográfica de carreteras dentro de la zona de cobertura de sector celular de la red de comunicaciones telefónicas inalámbricas, y identificar una ruta concreta de las rutas de tráfico recorridas por un vehículo asociado con una de las estaciones móviles procesando registros de movimiento para la estación móvil dentro de un contexto geográfico definido por la pluralidad de rutas de tráfico, incluyendo cada registro de movimiento posiciones primera y segunda dentro de la red de comunicaciones telefónicas inalámbricas para una misma estación móvil en tiempos diferentes y reflejando el movimiento de la misma estación móvil;donde el procesado incluye realizar un análisis probabilístico para identificar una o varias de las rutas de tráfico más probablemente recorridas por el vehículo: y calcular una estimación de una velocidad media y una desviación estándar de velocidad del vehículo asociado con la estación móvil a lo largo de la ruta de tráfico concreta en un tiempo específico.
- 9El método de la reivindicación 8, incluyendo además los pasos de:generar una pluralidad de registros de datos de tráfico en base a datos operativos de la red de comunicaciones telefónicas inalámbricas existente, identificando cada registro de datos de tráfico una posición dentro de la zona de cobertura de sector celular de la red de comunicaciones telefónicas inalámbricas para una de las estaciones móviles en un tiempo concreto;y generar un registro de movimiento en respuesta a procesar un par de los registros de datos de tráfico asociados con una actividad de comunicación inalámbrica por una misma estación móvil.
- 10El método de la reivindicación 9 incluyendo además el paso de recibir un flujo continuo de los datos operativos de la red de comunicaciones telefónicas inalámbricas.
- 11El método de la reivindicación 9 incluyendo además el paso de procesar la pluralidad de registros de datos de tráfico extrayendo cierta información confidencial asociada con los datos operativos para las estaciones móviles que operan dentro de la red de comunicaciones telefónicas inalámbricas, incluyendo el paso de procesado, para cada uno de los registros de datos de tráfico, los pasos de sustituir el identificador de estación móvil en el registro de datos de tráfico por un número identificador único;y mantener una relación entre el identificador de estación móvil sustituido y el número identificador único para asistir el seguimiento de registros de movimiento generados para la misma estación móvil.
- 12El método de la reivindicación 8 donde el paso de crear una pluralidad de rutas de tráfico incluye, para cada uno de los sectores celulares, los pasos de:determinar todos los segmentos de carretera que cruzan uno de los sectores celulares en base a la información geográfica de carreteras;determinar una pluralidad de segmentos límite de carretera para el sector celular en base a todos los segmentos de carretera que cruzan el sector celular;y calcular las rutas de tráfico entre cada segmento límite de carretera en el sector celular.
- 13El método de la reivindicación 8 donde el paso de identificar una ruta concreta de las rutas de tráfico recorridas por un vehículo asociado con una de las estaciones móviles incluye los pasos de:identificar pares de sectores celulares de inicio y fin a partir de una polilínea de posiciones de movimiento asociadas con los registros de movimiento para la misma estación móvil;para cada par de sectores celulares de inicio y fin, determinar todas las rutas de tráfico entre los sectores celulares en el par de sectores celulares;calcular una puntuación de desvío de célula para cada ruta de tráfico entre los sectores celulares en el par de sectores celulares;eliminar cualquiera de las rutas de tráfico entre los sectores celulares en el par de sectores celulares que no están dentro de un rango aceptable de las puntuaciones de desvío;calcular una velocidad a lo largo de cada ruta de tráfico entre los sectores celulares en el par de sectores celulares que no son eliminados por la puntuación de desvío usando sellos de tiempo en el registro de movimiento;ES 2 309 178 T3 acortar cada ruta de tráfico para la que se calculó una velocidad en el caso de que la velocidad calculada exceda de un corte de velocidad máximo;eliminar cualesquiera rutas de tráfico para las que se calculó una velocidad en el caso de que la velocidad calculada exceda del corte de velocidad máximo y la ruta de tráfico no pueda ser acortada;eliminar cualquier ruta de tráfico para la que se calculó una velocidad en el caso de que la velocidad calculada sea menor que un corte de velocidad mínimo;calcular una puntuación z de la velocidad calculada para todas las rutas de tráfico restantes que no han sido eliminadas;y seleccionar la ruta de tráfico concreta de las rutas de tráfico restantes en base a la puntuación z de la velocidad calculada y la puntuación de desvío.
- 14El método de la reivindicación 8 donde el paso de calcular una estimación de una velocidad media y desviación estándar de la velocidad de tráfico de vehículos a lo largo de la ruta de tráfico concreta durante un tiempo específico incluye además los pasos de:determinar una velocidad media de un vehículo para cada segmento de ruta en la ruta de tráfico concreta usando los registros de movimiento asociados con el segmento concreto de ruta de tráfico;determinar una velocidad media de un vehículo para una ruta de tráfico incluyendo una pluralidad de segmentos de rutas usando una distancia de la ruta de tráfico concreta y el tiempo de recorrido de la distancia usando los registros de movimiento asociados con la ruta de tráfico concreta;determinar la desviación estándar de la velocidad media para un vehículo para cada segmento de ruta en la ruta de tráfico concreta usando la diferencia de la suma de la velocidad media de un vehículo para cada segmento de ruta incluyendo una ruta de tráfico de la ruta de tráfico concreta y la velocidad media de un vehículo para una ruta de tráfico.
- 15El método de la reivindicación 8 incluyendo además el paso de determinar si los datos del sistema de posicionamiento móvil son necesarios para calcular una estimación de la velocidad media y la desviación estándar de la velocidad de tráfico de vehículos a lo largo de la ruta de tráfico concreta durante un tiempo específico, incluyendo además este paso los pasos de:determinar si la estimación de la velocidad media de tráfico de vehículos a lo largo de la ruta de tráfico concreta durante un tiempo específico se basa en un nivel de confianza a o superior a un umbral;para las rutas de tráfico donde la estimación de velocidad está por debajo del nivel de confianza, pedir datos de posición de estación móvil a la red de comunicaciones telefónicas inalámbricas asociada con la ruta de tráfico concreta en el tiempo específico;recibir los datos de posición de estación móvil pedidos de la red de comunicaciones telefónicas inalámbricas;y revisar el cálculo de la estimación de la velocidad media y la desviación estándar de la velocidad de tráfico de vehículos a lo largo de la ruta de tráfico concreta durante el tiempo específico usando los datos de posición de estación móvil recibidos.
Independent claims15
200 paragraphs in 11 sections, as filed
ES 2 309 178 T3
DESCRIPTION
System and method for providing traffic information using operational data and developed by a wireless network.
This invention relates to a system and method for providing traffic information. More specifically, this invention relates to using operational data developed by a wireless telephone communication network to generate traffic information.
Traffic congestion has reached crisis levels in major cities in the United States and will also be a major problem in smaller cities and rural areas. Traffic congestion is not only a source of frustration for commuters, it is also costly and a significant factor in air pollution. The Texas Transport Institute's 2001 Urban Mobility Report estimates that the total costs of congestion from New York City's 68 urban areas to cities with populations of 100,000 is $ 78 billion, which was the value of 4.5 billion hours behind schedule and 6.8 billion gallons of increased fuel consumption. From 1982 to 1999, the time passengers wasted in traffic increased from 12 hours to 36 hours per year.
Research has shown that meaningful travel information can reduce travel times by 13% and the demand for traffic data is growing exponentially. A recent Gallup study has shown that nearly 30% of all commuters and passing vehicles want to pay $ 1 to $ 5 per use and nearly 50% of commercial vehicle operators want to pay $ 10 per month; however, the data is simply not available.
Currently, transportation agencies collect highway traffic data from radar devices, video cameras, road sensors, and other hardware that requires expensive on-site installation and maintenance. Transportation agencies currently spend more than $ 1 billion a year on traffic monitoring systems that cover less than 10% of our national highway system. The data is sent to a Traffic Management Center (TMC) by means of high-speed fiber optic communications, where it is organized, analyzed and subsequently sent to the public by higher indicators or on the road, web pages of the Department of Transportation, and through radio, television, and other media collaborators. This hardware-oriented field team approach to collecting traffic data and providing information using hardware-oriented on-site equipment is costly and only practical in selected urban areas.
An emerging concept is the idea of using a global positioning system (GPS) device to determine a series of mobile communication device positions and transmit this data over a wireless network to a central processor. The processor can then calculate the speed and direction of the device for use in determining the flow of traffic. Although this approach can give very accurate information regarding a small number of devices, any attempt to collect position information from a large number of devices will use large amounts of the scarce bandwidth of the wireless network and will be very costly. Additionally, GPS data is not available for most wireless networks operating today. Although some national trucking companies have GPS positioning devices on their trucks, these vehicles represent a small fraction of the number of vehicles that use the roads.
Although most wireless telephone networks do not have GPS data capabilities, they do have an extensive infrastructure of communications facilities. These facilities routinely generate data to allow the system to function properly, for example, to allow cell phone users to make and receive calls and to remain connected to these calls when navigating the cellular sectors of a system. Examples of this data include call detail records (CDR), transfer messages, and log messages.
In September 1999, the FCC ordered wireless carriers to begin selling and activating phones that could be reached within 100 meters in the event of a 911 call. This requirement is called Phase II or Enhanced 911. Phase II 911 is not expected to be fully implemented until 2005. This system uses GPS or signal features to locate the cell phone. Regardless of the process used, the limited capacity of the network makes it impractical to monitor traffic using this capacity as the primary source of position data.
In view of the above, there is a need for a traffic information system that is capable of using existing types of data routinely generated by wireless telephone communication networks that can be extracted from the wireless network infrastructure without adversely affecting the operation of the wireless system. or taxing network resources.
WO 01/23835 relates to a traffic monitoring system for monitoring traffic including a population of users having a multiplicity of mobile communication devices and useful methods for monitoring traffic, the system including a mobile phone network interface that receives, of at least one communication network that serves the multiplicity of mobile communication devices and stores position information that characterizes at least some of the multiple mobile communication devices, and a traffic supervisor operative to calculate at least one characterization parameter of the traffic based on position information.
ES 2 309 178 T3
The present invention overcomes the deficiencies of other systems and methods for providing traffic information using operational data extracted from existing wireless telephone communication network infrastructure without adversely impacting network resources.
A wireless telephone communication network consists of base stations or cell towers that communicate with mobile phones and other wireless communication devices using licensed radio frequencies. When a mobile phone is switched on, it periodically registers its position with the network so that calls can be processed without delay. Additionally, the mobile phone is in contact with the wireless network when the phone makes or receives phone calls.
The present invention uses network position information, combined with computerized street maps, to measure the time it takes to move from one geographic position to another. By aggregating and analyzing anonymous data from thousands of wireless communication devices, the present invention is capable of determining real-time and historical travel speeds and times between cities, intersections, and along specific routes.
Aspects of the present invention may be more clearly understood and appreciated by careful reading of the following detailed description of the disclosed embodiments and by reference to the drawings and claims.
Brief description of the drawings
Figure 1 illustrates the operating environment of an exemplary embodiment of the present invention.
Figure 2a presents a block diagram depicting the main components of an exemplary embodiment of the present invention.
Figure 2b presents a general process flow diagram of an exemplary embodiment of the present invention.
Figure 3a depicts the relationship between a data extraction module and a data analysis node in an exemplary embodiment of the present invention.
Figure 3b depicts the relationship between data extraction modules and a data analysis node in an alternative embodiment of the present invention.
Figure 3c depicts the relationship between a data extraction module and data analysis nodes in an alternative embodiment of the present invention.
Figure 3d represents the relationship between data extraction modules and data analysis nodes in an alternative embodiment of the present invention.
Figure 4 illustrates a process-level block diagram of the data extraction module of an exemplary embodiment of the present invention.
Figure 5 presents a block diagram of the data extraction module of an exemplary embodiment of the present invention, focusing on a data input and processing function.
Figure 6 presents a process flow diagram for a file query and analysis process of an exemplary embodiment of the present invention.
Figure 7 presents a flow diagram of a privacy process of an exemplary embodiment of the present invention.
Figure 8 presents a flow diagram of a motion detection and filtering process of an exemplary embodiment of the present invention.
Figure 9 presents a block diagram of a data extraction module of an exemplary embodiment of the present invention, focusing on the configuration and monitoring function.
Figure 10 illustrates a process-level block diagram of a data analysis node of an exemplary embodiment of the present invention.
Figure 11 presents a flow diagram of a route generation process of an exemplary embodiment of the present invention.
Figure 12 presents a flow diagram of a route processing process of an exemplary embodiment of the present invention.
Figure 13a presents an illustrative example of a cellular sector / highway overlay.
ES 2 309 178 T3
Figure 13b presents an improved view of an illustrative example of a highway / cellular sector overlay.
Figure 14 presents a real example of a cellular sector / highway overlay.
Figure 15 presents a flow diagram of a route selection process of an exemplary embodiment of the present invention.
Figure 16 presents a process flow diagram for a path shortening process of an exemplary embodiment of the present invention.
Figure 17 presents a flow diagram of a speed estimation process of an exemplary embodiment of the present invention.
FIG. 18 presents a flow chart of a mobile positioning system determination process of an exemplary embodiment of the present invention.
Detailed description of exemplary embodiments
Exemplary embodiments of the present invention provide a system and method for using operational data from existing wireless telephone communication networks to estimate traffic movement throughout a traffic system. Figure 1 presents the wireless telephone communication network operating environment for an exemplary embodiment of the present invention, traffic information system 100. Mobile station (MS) 105 transmits signals to and receives signals from radio frequency transmission tower 110 while within a geographic cell covered by the tower. The size of these cells varies based on the anticipated signal volume. A base transceiver system (BTS) 115 is used to provide service to mobile subscribers within their cell. Several base transceiver systems are combined and controlled by a base station controller (BSC) 120 through a connection called Interface A<sub>bi</sub>s. Traffic information system 100 can connect to interface line A<sub>Bis</sub>. A mobile switching center (MSC) 125 performs the complex task of coordinating all base station controllers, via interface connection A, keeping track of all active mobile subscribers using the visitor location register (VLR). ) 140, maintaining home subscriber records using home location register (HLR) 130, and connecting mobile subscribers to the public service telephone network (PSTN) 145.
In an Enhanced or Phase II 911 system, the position of a mobile station 105 can be determined by embedding a GPS chip in the mobile station 105, or by measuring certain characteristics of the signal between the mobile station 105 and the BTS 115. In any scenario , the process of locating a mobile station 105 with the degree of accuracy necessary for the Enhanced or Phase II 911 system is managed with a mobile positioning system (MPS) 135. The MPS 135 uses the same network resources that are used to handle and process calls, which makes its availability somewhat limited.
The input-output gateway (IOG) 150 processes call detail records (CDRs) to facilitate actions such as billing to the mobile subscriber. IOG 150 receives call related data from MSC 125 and can connect to traffic information system 100.
In the exemplary embodiment of the present invention depicted in FIG. 1, the traffic information system 100 can receive data from various locations in the wireless network. These positions include the BSC 120 and its interface, via Interface A<sub>Bis</sub>, with the BTS 115, MSC 125, HLR 130, and MPS 135.
Inbound communications processes monitor the wireless service provider's network elements and extract relevant information from selected fields of selected records. Traffic information system 100 can use data from any network element that contains at least the mobile station identifier number, cell ID, and a timestamp. Some of the more common data sources are explained below.
CDRs can ask distribution centers for invoices or distribution centers can autonomously send records using file transfer protocol (FTP). Alternatively the CDRs can be extracted when they are routinely passed from the IOG 150 to a billing gateway, possibly using a router that duplicates the packets. The specific method used will depend on the equipment and the preferences of the wireless service provider.
Transfer and log messages can be obtained by monitoring the proprietary or standard A-interface signals between the MSC 125 and the BSCs 120 it controls. Traffic information system 100 may monitor such signals directly or may obtain signal information from a signal monitoring system such as a protocol analyzer. In the latter case the signal information may already be filtered to remove extraneous information (see FIG. 7 for an explanation of the privacy process for the exemplary embodiment of the present invention). Alternatively, these messages can be retrieved from a base station manager that continuously monitors the message flows in the BTS 115.
ES 2 309 178 T3
Turning to Figure 2a, in an exemplary embodiment, an existing wireless telephone communication network 220, also referred to as a wireless network, exchanges information with data extraction modules 240 of traffic information system 100. The data extraction modules ( DEX) 240 exchange information with data analysis nodes (DAN) 260, which in turn exchange information with end users 280 of the traffic information. In an alternative embodiment of the present invention, the DEX modules could exchange information directly with end users 280. In another alternative embodiment of the present invention, a process other than the DEX module 240 may supply motion vectors to the DAN module 260 for analysis with respect to to an end user 280. End users 280 may include departments of transportation, media, private transportation companies, or information service providers. Details on the types of information exchanged between modules are explained below.
FIG. 2b presents an overview of the traffic information system 200 process with respect to an exemplary embodiment of the present invention. DEX module 240 interacts with wireless network 220 to extract vehicle movement information from operational data in wireless communication devices. In step 241, the DEX module 240 polls the wireless network 220 at preset time intervals to identify flat files and FTP files containing operational data, including movement and position data, created by the wireless network 220 since the last query. Independent of, and parallel to, this query step, step 242 continuously receives operations data files from the wireless network 220 including motion and position data. In step 243, the DEX module requests mobile station position data from the MPS on the wireless network 220 in response to a request from the DAN module 260. In step 244, the data files received from the wireless network 220 are sent to analyzers configured to receive each specific type of data files. The analyzers extract data for the privacy and motion detection and filtering modules. In step 245, the analyzed data records are sent to the privacy module.
In step 247 of the exemplary embodiment, the privacy module acts on the analyzed data, extracting any personally identifiable information about the mobile station associated with the data record. The process assigns a unique serial number, also called a unique identifier number, to the record, substituting for the mobile station identifier number. Additionally, if the record is associated with a phone call and the dialed number is included in the analyzed data record, the call is classified. Categories can include emergency calls (911), traveler information calls (511), operator assistance calls (411), or other calls. In step 248, the cleaned data records are sent to the motion detection and filtering module.
In step 249, the motion detection and filtering module creates a motion record associated with each unique serial number contained in the data records. These motion records are then stored in a motion record hash table and serve as the output of the DEX 240 module.
In step 246, the configuration and monitoring module constantly monitors operations of the other components of the DEX module. If the trades are outside of a preset range of expected trades, then an email or other alert is sent to a system administrator. Additionally, reports on configuration and operational status can be sent to the system administrator. This administrator can also access the DEX 240 module and modify the configuration parameters.
In this exemplary embodiment, the DAN module 260 analyzes movement records from the DEX module 240 to estimate traffic speeds along predetermined travel routes. In step 261, the DAN module 260 receives coverage maps of cellular sectors from the wireless network 220 and road maps from the department of transportation or commercial vendor. These maps are received periodically, provided they have been updated. In step 262, these maps are used by the DAN configuration module, also referred to as the analysis configuration module, to generate road / cell sector overlay maps. Overlay maps identify which road segments are in which cell sectors. From these maps, all possible traffic routes between cellular sectors are identified and stored in a route database and route speeds and standard deviations are initialized.
In step 263, the traffic shaper receives the road / cellular sector overlay maps from the DAN configuration module and movement records from the DEX module 240. In step 264, the traffic shaper determines the traffic route traveled by stations individual mobiles associated with the motion record and the speed of the mobile station along said route. The route database is updated with the new route speed information.
In step 265 (for wireless networks 220 with MPS capabilities), the MPS determination module monitors the traffic shaper. The MPS determination module evaluates the statistical quality of the data used by the traffic shaper. If the speed estimates from the traffic shaper are based on a number of data records less than a threshold value necessary to meet statistical quality requirements, then the MPS determination module requests mobile station position data from the MPS on the wireless network. 220 through the DEX 240 module. This data is further processed like any other data in the DEX 240 module.
Figure 3 presents alternative embodiments of the relationship between data extraction module 240 and data analysis node 260. In one embodiment 300, shown in Figure 3a, a single data extraction module 240a may be paired with a single data analysis node 260a. As depicted in an embodiment 310 in
In FIG. 3b, multiple data extraction modules 240a, b, and c can exchange information with a single data analysis node 260a. For example, data extraction modules located at different wireless network operators in a metropolitan area can exchange information with a single data analysis node that processes traffic information for the entire metropolitan area. Figure 3c illustrates alternative embodiment 320 in which a single data extraction module 240a exchanges information with multiple data analysis nodes 260a, b, and c. For example, a data extraction module at a wireless service provider can exchange information with data analysis nodes located at single end users. Figure 3d illustrates alternative embodiment 330 in which multiple data extraction modules 240a, b, and c exchange information with multiple data analysis nodes 260a, b, and c. For example, data mining modules at multiple wireless service providers can exchange information with data analysis nodes located at single end users.
Figure 4 presents a process-level block diagram of an exemplary DEX module 240. A data input and processing module 442 exchanges information with wireless network 220. Data received from wireless network 220 is sent through a privacy module 444, where the personal identification data of the network subscriber is removed. Data input and processing module 442 and privacy module 444 include processor module 441. The scrubbed data is subsequently sent to a motion detection and filtering module 446. In the exemplary embodiment of the present invention, this module converts the scrubbed data from the wireless network into motion records associated with a mobile station. The movement records are sent to the data analysis node 260 through an HTTP query interface 450. The HTTP query interface 450 also sends information queries through the data input and processing module 442 to the wireless network 220. A configuration and monitoring component 448 provides the means to monitor the operation of the traffic information system and establish the operating parameters of the system.
FIG. 5 highlights a data input and processing module 442 of the exemplary embodiment of the present invention. A data input and processing module 442 exchanges data with a wireless network 220. A data input and processing module 442 includes file interfaces. These interfaces can be specific to a certain type of file. In the exemplary embodiment illustrated in Figure 5, a data input and processing module 442 includes a flat file interface 542 and an FTP file interface 544. These interfaces can interrogate a wireless network 220, each interrogating the component of network containing the specific file type, data files on a local storage disk (flat files), and files on an FTP server (FTP files) in this exemplary embodiment.
Additionally, a wireless network 220 can send a continuous stream of data to another continuous file interface 546, that is, a data input and processing module 442 does not have to interrogate this data source. This data is taken from a BSC 522, MSC and VLR 524, and HLR 526 and can include call detail records, transfer messages, and registration messages. Those skilled in the art will appreciate that a data input and processing module 442 may be configured to collect information as generated by a wireless network 220.
In the exemplary embodiment, a data input and processing module 442 is also capable of receiving position data from wireless network 220 that includes a mobile positioning system. An MPS 548 interface interacts directly with an MPS 528 gateway to request specific mobile station position data, based on a request from a data analysis node 260 distributed through an HTTP query interface 450. The MPS 548 interface sends the mobile station position data directly to the analysis engine 550. The details of this request are set forth later in this description, in connection with Figure 18. It is also explained with respect to Figures 11-14. the use of cellular sector coverage maps 530 by data analysis nodes 260.
The file interfaces in a data input and processing module 442 send the data to a working directory. The files in the working directory cause events to be generated and sent to a parser engine 550 for processing. The message contains the file name of the data file to analyze. From this name the most appropriate analysis syntax is selected and the file is analyzed. The program directory for the exemplary embodiment of the present invention contains a parser subdirectory. The jAr files containing analyzers are placed in this directory. The name of the JAR file must match a class name in the JAR file, and that class must implement the parser interface. Once implemented, the parser converts the extracted data into a format that can be used by privacy module 442 and motion detection and filtering module 446. When file processing is complete, the file is moved to a directory of indicted. At the start of the data input and processing module 442, all files in the processing directory are purged if they are older than a specified number of days.
Figure 6 presents details about the query and analysis process 241 under an exemplary embodiment of the data input and processing module. In process step 615, wireless network data 610, also called operational data, flows continuously from the network to a designated data storage location in traffic information system 100 for other data formats 636. These data files are analyzed, in step 640, based on the specific file type. Parallel to step 615, step 620 periodically queries the wireless network FTP server and local flat file storage units for operational data. If new data files are found in decision step 625, the files are classified in step 627. For example, BTS activity data is sent to file storage location 632 for that data type, it is
ES 2 309 178 T3 send CDRs to storage location 634 and data from interface A and interface A ,,, .. is sent to storage location 636. Those skilled in the art will appreciate that the present invention can accommodate a wide range of variety of file data types in this step, as evidenced by other 638 data types. If no new files are found in step 625, the process returns to step 620 and queries the data from the wireless network 610 at the next preset time interval.
The data files are subsequently sent from storage locations 632, 634, and 636 to the analyzer in step 640. In this step, the algorithm is specific to the type of data analyzed. For example, a unique algorithm would be used for CDRs compared to BTS activity data. The analyzed data is then sent to a mobile station data log file 645. Each data record in this file is read in step 650 and the data necessary to support a traffic information system 100, the traffic data record, also called the raw data record, is extracted in step 655 and sent. to the privacy module in step 670. This traffic data log contains wireless telephone communication network operational data used to evaluate the movement of vehicle traffic. In the exemplary embodiment of the present invention, this traffic data record may include the start and end times of a call, the cell ID or specific positions for the start and end of the call, the mobile station identifier number, the number dialed, the category of the call, and the number of transfers and the cell IDs and times of the transfers. Those skilled in the art will appreciate that other data can be included in the raw data record.
Figure 7 presents how data is processed 247 in the privacy module for an exemplary embodiment of the present invention. The traffic data records associated with a mobile station are received from the data input and processing module in step 710. In step 720, the hash table 730 is searched for the mobile station identifier number contained in the data record. . Hash table 730 contains mobile station identifier numbers adapted to a unique serial number assigned to said identifier by the privacy module. In decision step 740, if the mobile station identifier number is not in the hash table 730, then a unique serial number is assigned to said mobile station identifier number and the serial number / identifier pair is stored in the Hash table 730 in step 742. In an exemplary embodiment, the serial number is generated with the following algorithm in Table I. Those skilled in the art will appreciate that various techniques could be used to generate a unique alphanumeric indicator to represent the mobile station ID.
TABLE I
S = ((d * 1000) + mod (r, 100)) * (log<sub>10</sub>(n) * 10) + n where:
S = unique serial number d = day of year (1-365) = counter for the number of restarts mod = modulo function = number of entries in the serial number hash table
In step 744, the serial number associated with that identifier number is retrieved from the Hash table 730. These steps clear the record of personally identifiable information. In this embodiment, the traffic information system 100 does not associate motion records with a mobile station specific identifier number. In an alternative embodiment of the present invention, however, this scrubbing step could be omitted. One possible application of this alternative embodiment is to allow the system to track a given mobile station as it moves, for example, a parent tracks the position of a child with a cell phone.
In decision step 750, it is determined whether the dialed telephone number is part of the raw data record. If so, then step 760 classifies the call based on the characteristics of the dialed number and the process proceeds to step 770. Table II below summarizes the classification with respect to the exemplary embodiment.
TABLE II
Cell Phone Call Categories
<td>Dialed number</td><td>Category</td>
<td> 911</td><td>EMERGENCY 911</td>
<td>511, * X<sup>x</sup></td><td>TRAVELER INFO</td>
<td>411.0X</td><td>OPERATOR ASST</td>
<td>Others</td><td>DIALED CALL</td>
1. X is any string of dialed numbers
ES 2 309 178 T3
If the telephone number is not part of the traffic data record, the process proceeds directly from decision step 750 to step 770. In step 770, the privacy module 444 creates a location record. This record is passed to motion detection and filtering module 446 in step 780. In the exemplary embodiment of the present invention, this location record may include the start and end times of a call, the cell ID or specific locations for the start and end of the call, the serial number, the dialed number, the call category, log information, whether the call was forwarded or transferred, and the number of diversions and cell IDs and diversion times. Those skilled in the art will appreciate that other data can be included in the location register.
Figure 8 illustrates the motion detection and filtering process 249. As shown in Figure 8, at step 810, motion detection and filtering module 446 receives position records from privacy module 444. At step 820 each position record is loaded. For each record, step 840 interrogates the position hash table 830 and retrieves the last known position of the serial number associated with the record. In decision step 850, the position indicated in the position register is compared with the last known position of said serial number registered in the position hash table 830. If the position differs, a movement register is generated and stored in cache at step 860. Then, at step 870, the position hash table is updated and the move record is recorded in the move record hash table 880. If the last known position is not different from the current position in step 850, step 860 is skipped and the process proceeds to step 870. This process is repeated for all position records.
Figure 9 outlines the processing 246 performed by a configuration and supervision module 448 on a DEX module 240. A configuration and supervision module 448 interacts with another module on a DEX module 240 to evaluate system operations. A configuration and monitoring module 448 of an exemplary embodiment serves to alert a system administrator if the DEX module 240 is operating outside of a preset operating range 916 and to allow a system administrator to set configuration parameters 916. In the exemplary embodiment, a system administrator can configure traffic information system 100 over an Intranet or virtual private network (VPN) by performing configuration activity 916 using a fixed connection, for example, Secure Sockets Layer passwords or certificates. (SSL). This 916 configuration activity may include the following tasks, listed in Table III.
TABLE III * Establish the frequency of consultation of the wireless network 220;
* Establish the maximum time that a mobile station can be in a position before its serial number is released;
* Set the maximum amount of time that an individual cache record can be in the DEX before being discarded;
* Establish the minimum time between position requests. It is used to pace requests to the wireless network 220 mobile positioning system;
* Establish the minimum time between position requests for the same MS. This position is used to pace requests to the mobile positioning center;
* Establish the positions that can be sent to the DAN 260 for each event notification (for example, nothing, zone, cell, edge, or position);
* Authorize the details of a dialed number to send to DAN 260 for each event notification (for example, nothing, a classification, three-digit NPA, the six-digit office code, or the entire number called);
* Authorize the details of an inbound call number to be sent to DAN 260 for each event notification (eg nothing, a classification, three-digit APN, the six-digit office code, or the entire number called); and * Identification of the mobile stations that have given permission to send CPNI information for the application in this DAN 260.
Additionally, the performance statistics cache 914 may store system performance statistics data defined by the system administrator. This statistics cache can lead to 918 alert and report activity that reports on the behavior of the monitored system, containing routine information, or alerting the administrator that the system is operating out of specification. This 918 alert and report activity can be transmitted via email, personal pagers, telephone, instant messages, or other similar alert or report actions. In the exemplary embodiment, the cache statistics may include the following information, as set forth in Table IV.
ES 2 309 178 T3
TABLE IV * Number of CDRs processed;
* Number of A-interface messages processed, that is, BTS interface data;
* Number of cell-based position requests requested;
* Number of cell-based position requests canceled;
* Number of position requests based on mobile station identifier requested;
* Number of canceled mobile station identifier based position requests;
* Number of requested position requests released;
* Number of responses to requested position request received;
* Number of responses to unsolicited position request received;
* Number of event notifications generated for each DAN 260;
* Number of event notifications sent to each DAN 260; and * number of bytes sent to each DAN 260.
Figure 10 presents the process-level block diagram for data analysis node 260 in an exemplary embodiment. A DAN 260 module includes a DAN 1050 configuration module, a DAN 1060 traffic shaper, and a DAN 1070 MPS determination module. A DAN 1050 configuration module receives data in the form of cellular sector coverage maps 530 from the network provider. wireless 220, and 1040 road maps from the department of transportation or a commercial vendor. These maps are used to define routes used by traffic shaper 1060 to translate the cellular sector ID to a physical location. How the maps are used is detailed below, in association with Figures 11-14. This data is updated whenever the source data changes. For example, if the wireless network 220 changes its infrastructure resulting in a new coverage map of cellular sectors 1030, the new data is supplied to the DAN configuration module 1050.
In an exemplary embodiment, a DAN 1060 traffic shaper accepts motion records from a motion record 880 hash table in a DEX 240 module. One function of the DAN 1060 traffic shaper is to send traffic information in the form of speed estimates. of the trip along designated routes. This information is stored in a route database 1080. A DAN 1060 traffic modeler develops these estimates by determining the route taken by a mobile station based on movement logs and routes generated in a DAN 1050 configuration module. A DAN 1060 traffic modeler then chooses a route of possible routes and uses timing data associated with the motion log to estimate speed along the chosen route. Potential routes are identified from the route database 1080 and modified, or shortened, if necessary. Path identification and shortening are explained in association with Figures 15 and 16, respectively.
A DAN module 260 also augments motion records 880 it receives from a DEX module 240 with mobile station position data from an MPS on a wireless network 220. A determination module MPS 1070 is used to routinely evaluate the quantity and quality of the rate estimates from the traffic shaper 1060 and, if necessary, sends a request for mobile station position specific data through the DEX module 240. The MPS 1070 determination module is used with wireless telephone communication networks that support MPS.
Figure 11 depicts the route generation process 262a in a DAN configuration module 1050 for an exemplary embodiment. Cell sector coverage maps are stored, by cell sector, in a database 530. In step 1110 a cell sector is selected from database 530. At step 1140, the geographic information system database containing road maps 1040 is queried to determine all road segments that cross the cellular sector. The results of this query are highway boundary segments 1150 associated with the cellular sector, that is, highway segments that cross the boundary of a cellular sector, connecting a cellular sector to an adjacent cellular sector. Highway boundary segments 1150 serve as the input for route processing 1160, explained below in association with FIG. 12. The route processing results return at step 1170. The general process is repeated with respect to each cell sector in the database in step 1180. As explained in more detail below, this process generates a database of potential routes used by traffic shaper 1060. The route generation process 262 is executed by a DAN 1050 configuration module as long as the cellular sector coverage maps or road maps are up to date.
ES 2 309 178 T3
Figure 12 details the routing process 262b by a DAN 1050 configuration module for the exemplary embodiment. In step 1210, the routes including the boundary segments are stored in the route database 1240. For example, a boundary segment connecting cell sector A with cell sector B is a route from cell sector A to cell sector B These routes serve as the initial building blocks for the routes in the 1240 route database. In step 1215, the inter-sector path between two boundary segments is determined. This route is the shortest route, in terms of distance, from one boundary segment to another boundary segment on existing roads. This route is determined from a road GIS database. This database will define road segments between boundary segments. The GIS database can use one of several ways to define road segments. For example, a segment can be a stretch of road from one intersection to another or a road name change. The present invention can use the GIS data in whatever way the database has been established.
The shortest path between boundary segments defines a path between sectors, a path from one sector through an adjacent sector, to a third sector. Figures 13a and b illustrate an illustrative example of cellular sectors and roads. For illustrative purposes, cell sectors have been defined as squares of uniform size and alignment. Figure 13a depicts sixteen cell sectors, labeled "A" through "P". Dark lines indicate roads. Figure 13b represents an enlarged image of cell sector C and adjacent sectors. In this example, a route between sectors would be from cellular sector A to cellular sector D on the highway from point 1310 to point 1330 to point 1320. Another route between sectors would be from cellular sector A to cellular sector F on the highway from point 1310 to point 1320 to point 1340. A third route between sectors would be from cellular sector D to cellular sector F on the highway from point 1330 to point 1320 to point 1340.
Figure 13 illustrates a simplified representation of a highway / cellular sector overlay. Figure 14 presents a more realistic illustration. Shaded polygons represent single cell sectors. As can be seen in Figure 14, cellular sectors vary in size and the roads within a sector can be complex.
Returning to Figure 12, step 1220 initiates a loop for each defined inter-segment traffic route developed in step 1215. In step 1225, the speed of the segment is initialized to the limit speed indicated for the segment plus or minus one variance of twenty-five percent of said indicated speed limit. This initialization step is performed for each of the 168 hours of a week. In an alternative embodiment, the time increments can be set to every 15 minutes, for a total of 672 increments. Those skilled in the art will appreciate that the number of time increments can be based on any time division, for example, per hour, per half hour, per fifteen minutes, or per minute. The calculation for a division of time by hours is as follows:
<img file="ES2309178T3_D0001.tif" />
var<sub>jZ</sub> = 0.5 = ¾ where:
<td>I</td><td>= the hour of the week, from 1 to 168, with 1 being the hour between 12:00 in the morning and 1:00 in the morning on Sunday</td>
<td>s</td><td>= road segment s</td>
<td>vs, I</td><td>= average speed per hour I</td>
<td>Vps</td><td>= speed limit indicated for segment s</td>
<td>vars, i</td><td>= range of variance of velocity at hour I for segment s, representing the range from -25% to + 25%</td>
As stated above, the GIS database defines what a segment includes. In the illustrative example of figure 13, one segment can be the road section from point 1310 to 1320 and another segment the road section from 1320 to 1340. The entire route from A to F would be the road section defined by the two segments. At step 1230, the speed of the route is initialized to the weighted average speed for the traffic route, weighted by the normalized length of each segment. The calculation is as follows:
<img file="ES2309178T3_D0002.tif" />
ES 2 309 178 T3 where:
<sub>vr j</sub> = average speed for route r in hour I <sub>s</sub> = road segment s where the route r is defined by the connection of each segment <sub>vs j</sub> = average speed in hour I d<sub>s</sub> = distance of road segment d<sub>r</sub> = path distance = Zd<sub>s</sub>
At step 1233, the process initializes the variance of the traffic route speed to plus or minus twenty-five percent of the weighted average speed calculated in step 1230. The calculation is as follows:
var<sub>r</sub>,<sub>j</sub> = v <sub>rJ</sub>* 0.5 where:
<td>varr, j</td><td>= velocity variance for route r during hour I</td>
<td><sup>v</sup>r, j</td><td>= average speed for route r during hour I</td>
The traffic routes and initialized speeds for those routes for each of the 168 hours in a week, the time increment in this exemplary embodiment, are stored at step 1235 in the route database 1080. At step 1240 the number of detours on each route is calculated. The number of detours is the number of times a route crosses a boundary cellular sector. For example, in Figure 13, the route from cellular sector A to cellular sector E would have three detours, one when the mobile station transitions from sector A to C, one when it transitions from C to F, and another when it transitions from F to E . In step 1245, the sector where the route ends, “to sector”, and the sector where the route originates, “from sector”, together with the route ID and the number of detours, are stored in the database. routes 1080. The process is repeated for each path between sectors associated with the boundary segment. The process then returns to the route generation process at step 1255. This process has been explained above. The entire route generation process is repeated in step 1250, and is based on previous routes, until route database 1080 contains all possible routes from each cellular sector to each cellular sector.
Figure 15 presents the route selection process 264a for an exemplary embodiment of the present invention. This process 264a defines the traffic path for a mobile station and is performed by traffic shaper 1060. In step 1505, motion vectors are retrieved from the DEX for a given serial number. In the exemplary embodiment of the present invention, these vectors are periodically retrieved at specified time intervals, time intervals based on the DEX configuration.
In step 1510 a polyline of the movement positions associated with the mobile station is generated. With reference to the illustrative example in Figure 13, assuming that a mobile station makes a call at time ti while in cellular sector D. The call ends at time t<sub>2</sub> while the mobile station is in sector G. The same mobile station a short time later, time t<sub>3</sub>, makes a call from sector M and the call ends at time t<sub>4</sub> in sector O. The DEX would have developed three vectors of motion, one of sector D in t<sub>1</sub> to sector G in t<sub>2</sub>, another from sector G at t<sub>2</sub> to sector M in t<sub>3</sub>, and another from sector M in t<sub>3</sub> to sector O at t<sub>4</sub>. The polyline associated with this motion would be from D to G to M to O.
In step 1515, the polyline is decomposed into start and end sector pairs. In the example presented in the previous paragraph, the start and end sector pairs would be DG, DM, DO, GM, GO, and MO. In other words, the start and end pairs include the combination of all the points that include the polyline. For each of these pairs of start and end sectors, step 1520 of the process queries the database for all traffic routes between said pair of start and end sectors. This query returns all information about the route stored in route database 1525. In the exemplary embodiment of the present invention, this information includes the route ID, the average speed, and the variance of the speed on that route during each of the 168 hours in a week, the start and end sectors associated with that route, and the expected number of detours associated with the route.
The exemplary process analyzes each of the possible routes, as represented by the loop initiated at step 1530. At step 1535, the detour score is calculated. Deviation scoring is an exemplary technique that assesses the probability that the mobile station will follow the analyzed route. The score is calculated as follows:
Deviation score =
<img file="ES2309178T3_D0003.tif" />
ES 2 309 178 T3 where:
H = the number of deviations for the given polyline
TO<sub>h</sub> = absolute difference between observed deviations and expected deviations <sub>nR</sub> = number of routes where Ah = 0
B<sub>h</sub> = base drift score (default is 0.9) <sub>ω</sub> = deviation weight (default is 0.01)
At step 1540, the bias score is compared to a cutoff value. If yes, the route is saved in step 1545. If not, the route is discarded in step 1550. With respect to the saved routes, in step 1555 the speed on that route is calculated and based on the length of the route and start and end timestamps associated with the motion vector supplied by the data extraction module. The speed is:
<img file="ES2309178T3_D0004.tif" />
where:
<sub>vr</sub> = path speed d<sub>r</sub> = path distance t<sub>2</sub> = timestamp time<sub>2</sub>, the end of the movement ti = time of the timestamp i, the beginning of the movement.
In steps 1560 and 1563 this speed is compared with the maximum and minimum cuts for the speed on that route. These cutoff values are based on speeds and variances contained in the 1080 route database and a preset tolerance level, in terms of the number of standard deviations used to calculate the maximum and minimum cutoff values. For example, a system with a wide tolerance can put the number of standard deviations in the acceptable range to three or four, while a system with a narrow tolerance can put the number of standard deviations to one or two. The maximum and minimum cut-off values are calculated as follows:
<img file="ES2309178T3_D0005.tif" />
where:
<td><sup>v</sup>max</td><td>= maximum cutting speed</td>
<td>vr, you</td><td>= route speed at hour ti</td>
<td>Cv</td><td>= cutoff for speed comparison in number of standard deviations</td>
<td>varr.ti</td><td>= variance of speed for route r at time ti</td>
<td><sup>t</sup>i</td><td>= timestamp time<sub>1</sub>, the beginning of the movement</td>
<img file="ES2309178T3_D0006.tif" />
where:
<td><sup>v</sup>min</td><td>= minimum cutting speed</td>
<td>Vr, you</td><td>= speed of the route at hour t<sub>1</sub></td>
<td>Cv</td><td>= cut-off for speed comparison in number of standard deviations</td>
ES 2 309 178 T3 var<sub>r</sub>,<sub>tl</sub><sup>t</sup>l = variance of speed for route r at time t<sub>1</sub> = timestamp time<sub>1</sub>, the beginning of the movement
Routes with speeds less than the maximum cutoff speed and greater than the minimum cutoff speed are stored in step 1570. Routes with speeds that exceed the maximum cutoff go to decision step 1565 to determine if the route can be shortened. A route can be shortened if it consists of multiple segments. If the route can be shortened, the process proceeds to step 1575. If not, the route is discarded at step 1550. The results of the route shortening process go back to the route selection process 264 in step 1580. For the routes saved in step 1570, the process proceeds to decision step 1585. If another route is to be evaluated, the process returns to step 1530. If not, the process proceeds to speed estimation in step 1590.
Figure 16 presents the process for shortening route 264b for an exemplary embodiment of the present invention. This process 264b is a loop that compares the calculated speed of the route to the maximum cutting speed for that route. The process then removes the segments from the route and compares the new speed with the cutting speed. In the initial speed calculation, the traffic shaper 1060 assumes that the mobile station is at the farthest end of a cellular sector relative to the position of the end sector and also that the mobile station ends up at the farthest part of the sector. end in relation to the start sector. These assumptions make the route distance as long as possible. By removing a segment from either end of the route, the route is shorter and the speed calculated by the 1060 traffic shaper decreases (a shorter trip of the route in a fixed period of time produces a lower lower speed of the route) . In process step 1610, the first loop (counter equal to 0, set in step 1605) is the speed value calculated in the route selection process (see FIG. 15).
Decision step 1615 determines whether the speed of the route is less than the maximum speed of the route. For route speeds that are less than the maximum speed, the process returns to the route selection process in step 1620. For route speeds that are equal to or greater than the maximum speed cutoff in step 1615, the process consults the loop counter at step 1630. If the loop counter is even, the process queries the start sector in the stream. At step 1625, the process determines if there are more than two segments including the path to the home cellular sector. If so, the process removes the first segment from the route, in step 1645. The process increments the loop counter in step 1660. If there are no more than two segments at the start of the route, the process moves to step Decision 1640. If the answer to step 1640 is yes, the loop counter is odd, then the process goes to step 1650 and returns an invalid route. This step exists because the process left the fork "the loop counter is even", so an affirmative result means that the process fails. If the result in step 1640 is negative, the process goes to step 1635.
Step 1635 determines if there are more than two segments including the route in the end cell sector. If so, then the process removes the last segment at step 1655, increments the loop counter at step 1660, and returns to the start of the process at step 1670. The process returns to the route selection process when there are no more than two road segments in the start sector or end sector of the route or when enough segments are removed so that the speed is below the cutoff.
The traffic modeler 1060 estimates a speed, based on the possible routes that the mobile station followed, as indicated in FIG. 17. In step 1710, the speed estimation process 264c is triggered by the speed selection process. route 264b. At step 1720 the best route is selected from all possible routes that survived the route selection process (see FIG. 15). In the exemplary embodiment of the present invention, the "best" route is based on a statistical analysis of the speeds and detour scores for each possible route. Statistical analysis results in a z-score for each possible path. Those skilled in the art will appreciate that a variety of statistical analyzes could be performed to select the "best" route. The best path is the path with the minimum of the following expression:
Βι ((α, * (ω „* Λ)) where:
<sup>ω</sup>ζ <sup>t</sup>1 = weight of z-score, default is 0.3 = weight of deviation score, default is 0.7 = z-score of speed at time t1 = deviation score = time stamp<sub>1</sub>, start of movement
ES 2 309 178 T3
With respect to the best route, the process then calculates the speed of the route in step 1730. The speed is calculated as follows:
<img file="ES2309178T3_D0007.tif" />
where:
<sub>vr j</sub> = average speed for route r during hour I <sub>s</sub> = road segment s where the route r is defined by the connection of each segment <sub>vs j</sub> = average speed in hour I d<sub>s</sub> = distance of road segment d<sub>r</sub> = path distance = Zd<sub>s</sub>
In step 1740, the process calculates the speed of the route based on the overall distance and time of the route. In other words, the speed of the route is the ratio of the total length of the route to the time it takes for the mobile station to go from the initial position to the final position. Step 1745 initiates a loop for all route segments. In step 1750 the difference of these two speed estimates is calculated. This difference, V<sub>diff</sub>, is used in step 1760 to calculate a new segment velocity, as follows:
<img file="ES2309178T3_D0008.tif" />
where:
<td>vs<sup>0</sup></td><td>= the current speed on the road segment s</td>
<td>... hour (tl) s</td><td>= average speed for segment s during timestamp1</td>
<td><sup>v</sup>diff</td><td>= the difference between the observed and the calculated speed</td>
<td>vars</td><td>= variance of the speed for the road segment s at time t1</td>
<td>Ivar<sup>t1</sup>s<sub>and</sub>g</td><td>= sum of the variances for each of the segments in route r</td>
The difference in the two speed estimates is a measure of the variance of the speed and the above calculation establishes a new variance (compared to the initialized variance from step 1225, Figure 12) based on the calculated difference.
At step 1780 the average speed per segment and variance is updated in the database. These values are determined by the following equations:
<img file="ES2309178T3_D0009.tif" />
<img file="ES2309178T3_D0010.tif" />
<img file="ES2309178T3_D0011.tif" />
ES 2 309 178 T3 where:
<td>n hour (ti) s</td><td>= number of samples for segment s at time t1</td>
<td>v hour (ti) s</td><td>= average speed for segment s for timestamp1</td>
<td>var<sub>s</sub><sup>hour (t1)</sup></td><td>= variance of velocity at hour t1 for segment s</td>
At step 1790, the process updates the mean speed and variance for the entire route. These updates are based on the following calculation:
<img file="ES2309178T3_D0012.tif" />
<img file="ES2309178T3_D0013.tif" />
<img file="ES2309178T3_D0014.tif" />
where:
<td>s</td><td>= road segment s where r is defined by the connection of all segments</td>
<td>ds</td><td>= distance of road segment</td>
<td>dr</td><td>= path distance = Zd<sub>s</sub></td>
<td><sub>n</sub> hour (ti) r</td><td>= number of samples for route r at time ti</td>
<td><sub>v</sub> hour (ti) s</td><td>= average speed for segment s for timestampi</td>
<td>var<sub>s</sub><sup>hour (ti)</sup></td><td>= variance of velocity in hour ti for segment s</td>
In the exemplary embodiment of the present invention, a separate module, the MPS 1070 determination module from the DAN 260 module, ascertains the quality of the speed estimates from the traffic shaper 1060, based on the number of samples used to generate the estimates of speed. Step 1795 of the rate estimation process 264c serves as a gateway for the MPS determination module 1070 that queries the traffic shaper 1060. Figure 18 presents the operation of the determination module MPS 1070. In step 1805, the process consults the traffic shaper, extracting the updated segment speed and variance data from the speed estimation process 264c (see Figure 17 at 1795 ). Step 1810 initiates a loop for each road segment analyzed in speed estimation process 264c, the determination module MPS 1070 determines, in step 1815, the number of samples needed for the desired level of precision and determines, in 1820 , if this level is met. The number of samples required for a given level of precision is calculated as follows:
<img file="ES2309178T3_D0015.tif" />
where
<td><sup>z</sup>a / 2</td><td>= is the z-score of the desired confidence interval (for example 90% or z = 1.645)</td>
<td><sub>v</sub>ar<sub>2</sub><sup>hour (ti)</sup>=</td><td>variance of road segment speed</td>
<td>AND</td><td>= is half the width of the range (for example +/- 10 MPH)</td>
If the number of samples used in the traffic model is equal to or greater than the desired number calculated in step 1815, then the segment is no longer considered, in step 1825. If not, the segment is added to the
ES 2 309 178 T3 MPS request list at step 1835 and the loop repeats at step 1840 for each segment. Once all the segments have been evaluated, the process, in step 1845, retrieves from the route database 1830 all the routes that contain the segments in the 1835 MPS request list. In step 1850, the process requests mobile station position data from DEX for mobile stations on traffic routes containing the listed segments. This limited use of MPS data minimizes the load on wireless network resources, revealing a desired element of the exemplary embodiment of the present invention.
In summary, the present invention relates to a traffic information system 100. An exemplary embodiment of the system includes two main components, a DEX module 240 and a DAN module 260. In this embodiment, a DEX module 240 extracts data related to the communication activity of mobile stations on an existing wireless network 220 with minimal impact on the operations of the wireless network 220. In an exemplary embodiment, a DEX module 240 processes such data to remove personally identifiable information about the mobile station. In this process, the traffic data record can be classified based on the type of phone call made. These traffic data records are also processed to generate motion records associated with individual mobile stations.
In an exemplary embodiment, a DAN module 260 combines the motion records from the DEX module 240 with data associated with the geographic arrangement of cellular sectors and roads to estimate travel speeds along specific travel routes. Using the data associated with the geographic arrangement of cellular sectors and roads, a DAN 260 module generates maps that overlap the grid of cellular sectors on road maps. These overlay maps are used to generate all possible travel routes between any two cell sectors. The DAN module 260 can also retrieve mobile station position data from an MPS in a wireless network 220 to improve the statistical quality of the rate estimates.
Contents11
35 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14 Sheet 15 Sheet 16 Sheet 17 Sheet 18 Sheet 19 Sheet 20 Sheet 21 Sheet 22 Sheet 23 Sheet 24 Sheet 25 Sheet 26 Sheet 27 Sheet 28 Sheet 29 Sheet 30 Sheet 31 Sheet 32 Sheet 33 Sheet 34 Sheet 35
19 members in 11 offices
Priority claims5
| Document | Office | Kind | Date |
|---|---|---|---|
| 20010318858P | United States of America | – | |
| 31885801 | United States of America | P | |
| 31885801 | United States of America | P | |
| 318858P02740023 | – | – | – |
| US20010318858P | – | – | – |
Members19
| Document | Office | Kind | |
|---|---|---|---|
| CA2460136A1 | Canada | A1 | |
| WO03024132A1 | World Intellectual Property Organization (WIPO) | A1 | |
| US2003078055A1 | United States of America | A1 | |
| EP1437013A1 | European Patent Office (EPO) | A1 | |
| MXPA04002383A | Mexico | A | |
| US6842620B2 | United States of America | B2 | |
| CN1582584A | China | A | |
| US2005079878A1 | United States of America | A1 | |
| HK1067844A1 | Hong Kong, China | A1 | |
| EP1437013A4 | European Patent Office (EPO) | A4 | |
| CN1294773C | China | C | |
| AU2000280390B2 | Australia | B2 | |
| EP1437013B1 | European Patent Office (EPO) | B1 | |
| AT402464T | Austria | T | |
| ATE402464T1 | Austria | T1 | |
| DE60227825D1 | Germany | D1 | |
| ES2309178T3This record | Spain | T3 | |
| US7546128B2 | United States of America | B2 | |
| CA2460136C | Canada | C |
Numbers
- Publication
- 2309178
- Publication, DOCDB
- 2309178
- Publication, EPODOC
- ES2309178T
- Application
- 2740023
- Application, DOCDB
- 02740023
- Application, EPODOC
- ES20020740023T
Titles2
- Spanish
- SISTEMA Y METODO PARA PROPORCIONAR INFORMACION DE TRAFICO USANDO DATOS OPERATIVOS Y DESARROLLADOS POR UNA RED INALAMBRICA.
- English
- SYSTEM AND METHOD TO PROVIDE TRAFFIC INFORMATION USING OPERATIONAL DATA AND DEVELOPED BY A WIRELESS NETWORK.
Classification
- CPC, 1
- G08G1/0104
- IPC, 2
- G08G1 01
- H04Q7 20