Method and system for partitioning a continental roadway network for an intelligent vehicle highway system

Abstract

An intelligent vehicle highway system collects and provides real-time traffic data to a vehicle traveling on a continental roadway network. A digitized continental roadway network has nodes interconnected by links that define a digitized representation of the continental roadway network. To enable intelligent data collection and navigation over large expanses of the continental network, which would otherwise be computationally onerous, the digitized continental roadway network is partitioned into a plurality of digitized roadway subnetworks. The onboard vehicle navigation device has a processor for executing an application that instantiates a subset of the digitized roadway subnetworks in a vicinity of a current position of the vehicle to collect and provide relevant real-time traffic data to the vehicle in a computationally efficient manner.

1 . A method of collecting real-time traffic data using moving vehicles and providing the real-time traffic data to an occupant of a vehicle traveling on a continental roadway network, the method comprising steps of:
 partitioning a digitized continental roadway network having a plurality of nodes and links that define a digitized representation of the continental roadway network into a plurality of contiguous digitized roadway subnetworks, each subnetwork having its own lifeline; and   instantiating a plurality of traffic managers in an onboard vehicle navigation device wherein at least one traffic manager is instantiated for each one of a subset of contiguous digitized roadway subnetworks that lie in a vicinity of a current position of the vehicle to collect traffic data and provide relevant real-time traffic data to the occupant of the vehicle, wherein the at least one traffic manager is instantiated in relation to the lifelines associated with its respective neighboring subnetworks.   
   
   
       2 . The method as claimed in  claim 1  wherein the step of partitioning the network comprises a step of dividing the continental roadway network into regions represented by respective subnetworks of nodes interconnected by links, the regions being demarcated by demarcation lines which are drawn such that no line segment of any demarcation line coincides with a link of any of the subnetworks. 
   
   
       3 . The method as claimed in  claim 2  wherein each demarcation line comprises a plurality of artificially defined demarcation nodes with which are associated an ID of an immediately adjacent subnetwork. 
   
   
       4 . The method as claimed in  claim 3  further comprising steps of:
 detecting that the vehicle has arrived at one of the demarcation nodes; and   causing a control process executing in a processor of an onboard vehicle navigation device to hand over responsibility from a first traffic manager that is managing the first subnetwork from which the vehicle is departing to a second traffic manager that is managing the adjacent subnetwork which the vehicle is entering.   
   
   
       5 . The method as claimed in  claim 1  wherein the step of partitioning the network comprises a step of defining, as an inner belt running along each side of each demarcation line, a joint awareness zone comprising an awareness line having awareness nodes along the awareness line, the awareness nodes comprising a list of the one or more neighboring regions whose traffic managers are to be made jointly aware of the vehicle position. 
   
   
       6 . The method as claimed in  claim 5  comprising steps of:
 detecting that the vehicle has arrived at one of the awareness nodes; and   forwarding vehicle position information to one or more traffic managers for neighboring regions to make the one or more traffic managers jointly aware of a current position of the vehicle.   
   
   
       7 . The method as claimed in  claim 1  wherein the step of partitioning the network comprises a step of defining, as an outer belt running approximately parallel to each demarcation line on each side of each demarcation line, an instantiating/terminating threshold (ITT), the ITT comprising a plurality of lifeline nodes each having a list of neighboring regions for instantiating traffic managers for subnetworks corresponding to neighboring regions that become relevant and for terminating traffic managers for subnetworks of regions that become no longer relevant. 
   
   
       8 . The method as claimed in  claim 7  further comprising steps of:
 detecting that the vehicle has arrived at one of the lifeline nodes;   determining whether the vehicle is traveling toward or away from a demarcation line;   if the vehicle is traveling toward the demarcation, instantiating a new traffic manager for the subnetwork which the vehicle is approaching; and   if the vehicle is traveling away from the demarcation, terminating the traffic manager for the subnetwork from which the vehicle has departed.   
   
   
       9 . The method as claimed in  claim 1  wherein the step of partitioning comprises steps of:
 defining a joint awareness zone as an inner buffer immediately on each side of each demarcation line that partitions one subnetwork from a neighboring subnetwork, the joint awareness zone having a plurality of awareness nodes forming an awareness line approximately parallel to the respective demarcation line; and   defining an instantiating/terminating threshold (ITT) as an outer buffer immediately on each side of the joint awareness zone, the instantiating/terminating threshold having a plurality of lifeline nodes arranged approximately parallel to both the awareness line and the demarcation line.   
   
   
       10 . The method as claimed in  claim 9  further comprising steps of:
 instantiating a traffic manager for each of one or more neighboring subnetworks when the vehicle arrives at a lifeline node;   sharing vehicle position information with a traffic manager responsible for each of the one or more neighboring subnetworks when the vehicle arrives at an awareness node; and   terminating a traffic manager corresponding to the subnetwork from which the vehicle has exited when the vehicle, traveling away from the demarcation line, arrives at a lifeline node on the opposite side of the instantiating/terminating threshold.   
   
   
       11 . The method as claimed in  claim 1  wherein the step of instantiating the subset of digitized roadway subnetworks comprises instantiating no more than four subnetworks. 
   
   
       12 . The method as claimed in  claim 1  wherein the step of instantiating the subset of digitized roadway subnetworks comprises a step of instantiating exactly four subnetworks consisting of a continental expressway subnetwork, a first regional capillary subnetwork, and two neighboring regional capillary subnetworks. 
   
   
       13 . An intelligent vehicle highway system for collecting and providing real-time traffic data from and to vehicles traveling on roadways that are part of a continental roadway network, the system comprising:
 a plurality of vehicles each having an onboard vehicle navigation device having a global positioning system (GPS) receiver for generating real-time position data for the vehicle, a wireless transceiver for transmitting the real-time position data and for receiving traffic data, the onboard vehicle navigation device having a processor that executes an application for instantiating a plurality of traffic managers wherein at least one traffic manager is instantiated for each of the contiguous digitized roadway subnetworks defined by partitioning a digitized continental roadway network representative of the roadways of a continent to form a partitioned continental roadway network, each subnetwork having its own lifeline which, when traversed by the vehicle, causes the application to instantiate the at least one traffic manager for the neighboring subnetworks associated with the lifeline being traversed; and   a traffic data center having a wireless transceiver for receiving real-time position data from the plurality of vehicles in the network and for transmitting to the vehicles processed traffic data based on the real-time position data received from the plurality of vehicles in the network.   
   
   
       14 . The system as claimed in  claim 13  wherein the application instantiates no more than four traffic managers and executes a control process to control each of the traffic managers. 
   
   
       15 . The system as claimed in  claim 13  wherein the partitioned continental roadway network comprises a plurality of demarcation lines, each demarcation line comprising artificially defined demarcation nodes, the demarcation lines being drawn to partition the network into subnetworks such that no line segment of any demarcation line coincides with any link of the network. 
   
   
       16 . The system as claimed in  claim 15  wherein the partitioned continental roadway network comprises a joint awareness zone defining an inner buffer immediately on each side of each demarcation line that partitions one subnetwork from a neighboring subnetwork, the joint awareness zone having a plurality of awareness nodes forming an awareness line approximately parallel to a respective demarcation line whereby vehicle position data for a vehicle located within the joint awareness zone is shared between the traffic managers associated with the neighboring subnetworks on either side of the demarcation line. 
   
   
       17 . The system as claimed in  claim 15  wherein the partitioned continental roadway network comprises an instantiating/terminating threshold (ITT) on each side of the demarcation line, the instantiating/terminating threshold having a plurality of lifeline nodes arranged approximately parallel to the demarcation line whereby arrival of the vehicle at one of the lifeline nodes causes instantiation of a new traffic manager or termination of an existing traffic manager. 
   
   
       18 . The system as claimed in  claim 15  wherein the partitioned continental roadway network comprises:
 a joint awareness zone defining an inner buffer immediately on each side of each demarcation line that partitions one subnetwork from a neighboring subnetwork, the joint awareness zone having a plurality of awareness nodes forming an awareness line approximately parallel to the respective demarcation line whereby vehicle position data for a vehicle located within the joint awareness zone is shared between the traffic managers associated with the neighboring subnetworks on either side of the demarcation line; and   an instantiating/terminating threshold (ITT) as an outer buffer immediately on each side of the joint awareness zone, the instantiating/terminating threshold having a plurality of lifeline nodes arranged approximately parallel to both the awareness line and the demarcation line whereby arrival of the vehicle at one of the lifeline nodes causes instantiation of a new traffic manager or termination of an existing traffic manager.   
   
   
       19 . An onboard vehicle navigation device for collecting, transmitting and receiving real-time traffic data and for providing intelligent navigation to an occupant of a vehicle traveling on a continental roadway network, the device comprising:
 a global positioning system (GPS) receiver for generating a current position of the vehicle;   a wireless transceiver for transmitting the current position of the vehicle to a traffic data center for generating traffic data to be communicated back to the wireless transceiver;   a processor that executes an application for instantiating a plurality of traffic managers wherein at least one traffic manager is instantiated for each one of a plurality of partitioned subnetworks relevant to the current position of the vehicle, the partitioned subnetworks being defined by partitioning a digitized continental roadway network that represents the continental roadway network in terms of nodes interconnected by links to thus form a partitioned continental roadway network represented by contiguous subnetworks, each subnetwork having its own lifeline which, when traversed by the vehicle, causes the application to instantiate the at least one traffic manager for the neighboring subnetworks associated with the lifeline being traversed; and   a user interface for presenting the traffic data to the occupant of the vehicle to enable intelligent navigation through the roadway network.   
   
   
       20 . The device as claimed in  claim 19  wherein the partitioned subnetworks are divided by demarcation lines, each demarcation line comprising demarcation nodes, the demarcation lines being drawn to partition the continental network into subnetworks such that no line segment of any demarcation line coincides with any link of any of the subnetworks and wherein the partitioned continental roadway network comprises:
 a joint awareness zone defining an inner buffer immediately on each side of each demarcation line that partitions one subnetwork from a neighboring subnetwork, the joint awareness zone having a plurality of awareness nodes forming an awareness line approximately parallel to the respective demarcation line whereby vehicle position data for a vehicle located within the joint awareness zone is shared between the traffic managers associated with the neighboring subnetworks on either side of the demarcation line; and   an instantiating/terminating threshold (ITT) as an outer buffer immediately on each side of the joint awareness zone, the instantiating/terminating threshold having a plurality of lifeline nodes arranged approximately parallel to both the awareness line and the demarcation line whereby arrival of the vehicle at one of the lifeline nodes causes instantiation of a new traffic manager or termination of an existing traffic manager.