Onboard unit and method for updating geodata therein

Abstract

An onboard unit for levying tolls for a vehicle comprises a satellite navigation receiver for generating position fixes, a memory for recording geoobjects, a radio interface, and a processor, which generates toll data from a geographical comparison of position fixes with geoobjects in a digital map and transmits this data via the radio interface. The memory has an index memory region for an index tree for geoobjects, a first static object memory region for a primary list with geoobjects, and a second object memory region, which can be written dynamically via the radio interface, for a secondary list with geoobjects. At least one leaf of the index tree contains a reference to a secondary list, and wherein the processor is configured, upon accessing a geoobject via a leaf, to use the secondary list before the primary list. A method for updating geodata in such an onboard unit is also disclosed.

Claims

1. An onboard unit for levying toll for a vehicle, comprising: a satellite navigation receiver for generating position fixes; a memory for recording geoobjects; a radio interface; and a processor coupled to the satellite navigation receiver, the memory, and the radio interface, the processor configured to generate toll data from a geographical comparison of position fixes with geoobjects in a digital map and to transmit this data via the radio interface; wherein the memory has: an index memory region, in which an index tree for geoobjects is stored, of which the outermost branches are each assigned to a cell of the digital map and carry a leaf with identifiers of geoobjects of this cell, a first static object memory region, in which a primary list with geoobjects and identifiers thereof is stored, and a second object memory region, which can be written dynamically via the radio interface and in which at least one secondary list with geoobjects and identifiers thereof is stored; wherein at least one leaf of the index tree contains a reference to a secondary list of the at least one secondary list; wherein the processor is configured, upon accessing a geoobject via a leaf of the index tree, when this leaf contains a reference to the secondary list of the at least one secondary list, to use the secondary list of the at least one secondary list as a matter of priority before the primary list; and wherein a dedicated secondary list for each of at least two leaves of the index tree is stored in the second memory region.

2. The onboard unit according to claim 1, wherein the geoobjects in the secondary list are all of identical size.

3. The onboard unit according to claim 1, wherein the index tree is a balanced quadtree.

4. An onboard unit for levying toll for a vehicle, comprising: a satellite navigation receiver for generating position fixes; a memory for recording geoobjects; a radio interface; and a processor coupled to the satellite navigation receiver, the memory, and the radio interface, the processor configured to generate toll data from a geographical comparison of position fixes with geoobjects in a digital map and to transmit this data via the radio interface; wherein the memory has: an index memory region, in which an index tree for geoobjects is stored, of which the outermost branches are each assigned to a cell of the digital map and carry a leaf with identifiers of geoobjects of this cell, a first static object memory region, in which a primary list with geoobjects and identifiers thereof is stored, and a second object memory region, which can be written dynamically via the radio interface and in which at least one secondary list with geoobjects and identifiers thereof is stored; wherein at least one leaf of the index tree contains a reference to a secondary list of the at least one secondary list; wherein the processor is configured, upon accessing a geoobject via a leaf of the index tree, when this leaf contains a reference to the secondary list of the at least one secondary list, to use the secondary list of the at least one secondary list as a matter of priority before the primary list; wherein at least two leaves of the index tree refer to the same secondary list.

5. The onboard unit according to claim 4, wherein the index tree is a balanced quadtree.

6. An onboard unit for levying toll for a vehicle, comprising: a satellite navigation receiver for generating position fixes; a memory for recording geoobjects; a radio interface; and a processor coupled to the satellite navigation receiver, the memory, and the radio interface, the processor configured to generate toll data from a geographical comparison of position fixes with geoobjects in a digital map and to transmit this data via the radio interface; wherein the memory has: an index memory region, in which an index tree for geoobjects is stored, of which the outermost branches are each assigned to a cell of the digital map and carry a leaf with identifiers of geoobjects of this cell, a first static object memory region, in which a primary list with geoobjects and identifiers thereof is stored, and a second object memory region, which can be written dynamically via the radio interface and in which at least one secondary list with geoobjects and identifiers thereof is stored; wherein at least one leaf of the index tree contains a reference to a secondary list of the at least one secondary list; wherein the processor is configured, upon accessing a geoobject via a leaf of the index tree, when this leaf contains a reference to the secondary list of the at least one secondary list, to use the secondary list of the at least one secondary list as a matter of priority before the primary list; wherein at least one geoobject in the secondary list is provided with a “deleted”-flag, and the processor is configured, upon accessing a geoobject of which the “deleted”-flag is set, to ignore this geoobject.

7. The onboard unit according to claim 6, wherein the index tree is a balanced quadtree.

8. An onboard unit for levying toll for a vehicle, comprising: a satellite navigation receiver for generating position fixes; a memory for recording geoobjects; a radio interface; and a processor coupled to the satellite navigation receiver, the memory, and the radio interface, the processor configured to generate toll data from a geographical comparison of position fixes with geoobjects in a digital map and to transmit this data via the radio interface; wherein the memory has: an index memory region, in which an index tree for geoobjects is stored, of which the outermost branches are each assigned to a cell of the digital map and carry a leaf with identifiers of geoobjects of this cell, a first static object memory region, in which a primary list with geoobjects and identifiers thereof is stored, and a second object memory region, which can be written dynamically via the radio interface and in which at least one secondary list with geoobjects and identifiers thereof is stored; wherein at least one leaf of the index tree contains a reference to a secondary list of the at least one secondary list; wherein the processor is configured, upon accessing a geoobject via a leaf of the index tree, when this leaf contains a reference to the secondary list of the at least one secondary list, to use the secondary list of the at least one secondary list as a matter of priority before the primary list; wherein at least one geoobject of the secondary list of the at least one secondary list contains the identifier of a further geoobject of the secondary list of the at least one secondary list.

9. The onboard unit according to claim 8, wherein the index tree is a balanced quadtree.

10. An onboard unit for levying toll for a vehicle, comprising: a satellite navigation receiver for generating position fixes; a memory for recording geoobjects; a radio interface; and a processor coupled to the satellite navigation receiver, the memory, and the radio interface, the processor configured to generate toll data from a geographical comparison of position fixes with geoobjects in a digital map and to transmit this data via the radio interface; wherein the memory has: an index memory region, in which an index tree for geoobjects is stored, of which the outermost branches are each assigned to a cell of the digital map and carry a leaf with identifiers of geoobjects of this cell, a first static object memory region, in which a primary list with geoobjects and identifiers thereof is stored, and a second object memory region, which can be written dynamically via the radio interface and in which at least one secondary list with geoobjects and identifiers thereof is stored; wherein at least one leaf of the index tree contains a reference to a secondary list of the at least one secondary list; wherein the processor is configured, upon accessing a geoobject via a leaf of the index tree, when this leaf contains a reference to the secondary list of the at least one secondary list, to use the secondary list of the at least one secondary list as a matter of priority before the primary list; wherein at least one geoobject of the primary list contains the identifier of a further geoobject of the primary list.

11. The onboard unit according to claim 10, wherein the index tree is a balanced quadtree.

12. A method for updating geodata in an onboard unit that includes a radio interface, comprising: generating toll data from a geographical comparison of position fixes with geoobjects in a digital map; storing an index tree for geoobjects in an index memory region of a memory in the onboard unit, of which the outermost branches are each assigned to a cell of the digital map and carry a leaf with identifiers of geoobjects of the cell; storing a primary list with geoobjects and identifiers thereof in a first static object memory region of the memory; storing at least one secondary list with geoobjects and identifiers thereof in a second object memory region of the memory, wherein at least one leaf of the index tree contains a reference to a secondary list of the at least one secondary list; and upon accessing a geoobject via a leaf of the index tree that contains a reference to the secondary list of the at least one secondary list, using the secondary list of the at least one secondary list as a matter of priority before the primary list; wherein the secondary list of the at least one secondary list is created in a central unit and transmitted, without the index tree and without the primary list, from the central unit to the onboard unit and received in the onboard unit via the radio interface for storing in the second object memory region.

13. The method according to claim 12, wherein an identifier of the branch carrying the leaf with the reference to the created secondary list is also transmitted with the created secondary list, and the created secondary list is stored in the second object memory region at the location specified by the reference to the created secondary list.

14. The method according to claim 12, wherein the index tree is a balanced quadtree.

Description

BRIEF DESCRIPTION OF THE DRAWINGS/FIGURES

(1) The present subject matter will be described in greater detail hereinafter on the basis of exemplary embodiments illustrated in the accompanying drawings, in which:

(2) FIG. 1 shows a digital map with geoobjects and a quadtree index tree for the locating thereof.

(3) FIG. 2 shows the quadtree index tree of FIG. 1 in another schematic illustration style.

(4) FIG. 3 shows a block diagram of the onboard unit for carrying out the method of an embodiment in conjunction with a satellite navigation system and a central unit of a road toll system.

(5) FIG. 4 shows the internal structure of the memory of the onboard unit of FIG. 3.

(6) Embodiments will now be described with reference to the accompanying drawings.

DETAILED DESCRIPTION

(7) FIG. 1 shows a geographical area 1, in which a vehicle 2 with an onboard unit (OBU) 3 is moving on a path 4, for example. To determine the path 4 for toll levying purposes, the OBU 3 is equipped with a satellite navigation receiver 5, see FIG. 3, which receives satellite navigation data 6 from a global satellite navigation system (GNSS) 7 and from this continuously generates position fixes p.sub.1, p.sub.2, . . . , generally p.sub.i.

(8) FIG. 1 at the same time shows a digital map 8 of the geographical area 1, in which geoobjects ob.sub.1, ob.sub.2, . . . , generally ob.sub.j, of actual geographical objects of the geographical region 1 are stored. Examples of geoobjects ob.sub.j are area boundaries, such as city borders, parking space borders, inner city borders, etc. (see ob.sub.1, ob.sub.3), transfer points, such as country borders, entry or exit borders, barriers, etc. (see ob.sub.4), or crossing points, such as locations such as “virtual toll points”, check points, etc. (see ob.sub.2, ob.sub.5, ob.sub.6, ob.sub.7). The geoobjects ob.sub.j are stored in an internal memory 9 of the OBU 3, of which the structure will be explained in greater detail later on the basis of FIG. 4.

(9) An internal processor 10 of the OBU 3 continuously compares the sequence {p.sub.i} of position fixes p.sub.i with the geoobjects ob.sub.j stored in the memory 9 in order to determine the closest geoobject(s) ob.sub.j and to detect from this the passing for example of a border, toll levying point, a check point, or the residence in a certain area or on a certain road portion, etc. The result of this geographical comparison (“map matching”) serves as a basis for the generation of corresponding toll data tr, which is then transmitted by the processor 10 via a radio interface 11 of the OBU 3 to a remote central unit 12 for evaluation or toll levying of the path 4 of the vehicle 2 (arrow 13).

(10) The radio interface 11 is for example a mobile radio module for a mobile radio network 14, for example according to a 3G, 4G or 5G radio network standard, such as GSM, UMTS or LTE, via which the central unit 12 is connected to the OBU 3. The central unit 12 can generate, from the received toll data tr, corresponding paths or toll protocols 15 for levying tolls for the location uses of the vehicle 2, as known in the art.

(11) In order to quickly locate the closest geoobject(s) ob.sub.j at one or more position fixes p.sub.i, the geoobjects ob.sub.j in the digital map 8 or the memory 9 of the OBU 3 are indexed, more specifically with a hierarchical index in the form of an index tree 16, which is illustrated in FIGS. 1, 2 and 4 in various illustration styles.

(12) The index tree 16 may be a geographical, that is to say two-dimensional, index of the quadtree, R-tree or kd-tree type or the like, and FIGS. 1, 2 and 4 show the special embodiment of a quadtree, in which each node n.sub.1, n.sub.2, . . . , generally n.sub.k, branches in each case to four branches b.sub.1, b.sub.2, . . . , generally b.sub.1, which, at the ends thereof, branch or not via further nodes n.sub.k to further branches b.sub.1.

(13) The outermost branches b.sub.1 distanced furthest from the “original” node (the root) n.sub.1 of the index tree 16 are each assigned to a cell c.sub.1, c.sub.2, . . . , generally c.sub.m, of the digital map 8 and carry a “leaf” lv.sub.1, lv.sub.2, . . . , generally lv.sub.m, which contains or references the geoobjects ob.sub.j contained in this cell c.sub.m, as will be explained later with reference to FIG. 4.

(14) FIG. 1 illustrates the fact that such a quadtree index tree 16 divides the digital map 8 into successive smaller cell quadruples nested one inside the other. The geographical division lines 17 between the cells c.sub.m, and therefore the branches b.sub.1 and nodes n.sub.k of the index tree 16, are selected such that the most uniform distribution possible of the number of geoobjects ob.sub.j over the leaves lv.sub.m or cells c.sub.m is achieved. This minimises the average access time to the geoobjects ob.sub.j when searching through the index tree 16, as known to a person skilled in the art.

(15) FIG. 4 shows another illustration of the same index tree 16 with (here by way of example) two nodes n.sub.1, n.sub.2, of which the hierarchically lower node n.sub.2 branches in two branches b.sub.1 and b.sub.2, illustrated by way of example and each having a leaf lv.sub.1, lv.sub.2. Each leaf lv.sub.m comprises a limited number of memory cells 18 for object identifiers id.sub.j of geoobjects ob.sub.j, which are stored in a first list or “primary list” 19 of geoobjects ob.sub.j.

(16) Each geoobject ob.sub.j of the primary list 19 is stored therein with its object identifier id.sub.j and may additionally contain a chain field 20 and a “deleted”-flag 21, the functions of which will be discussed later in greater detail. Each memory cell 21 of a leaf lv.sub.m, which stores an object identifier id.sub.j, thus refers to a geoobject ob.sub.j of the primary list 19, for example see the link 22. Two leaves lv.sub.1, lv.sub.2 can also refer to the same geoobject ob.sub.j of the primary list 19, as shown by the two links 22, 23.

(17) The index tree 16 and the primary list 19 can be stored in the memory 9 of the OBU 3, for example with the delivery of the OBU 3 to the user, see arrow 24. Since the primary list 19 may contain a very large number of geoobjects ob.sub.j in the case of a large geographical area 1, for example thousands or tens of thousands of geoobjects ob.sub.j, the primary list 19 is very comprehensive and the structure of a balanced index tree 16 is very complex, and an updating during running operation via the radio interface 11 is not practicable for the reasons mentioned in the introduction. Although only few geoobjects ob.sub.j would be transmitted via the radio interface 11, a recalculation of the index tree 16 in order to balance this out so as to minimise access time is difficult to implement with a limited computing power in the OBU 3. The below-described extension of the presented system is used to minimise the updating and calculation effort of the index tree 16 and of the geoobjects ob.sub.j.

(18) The memory 9 of the OBU 3 is divided into a first static object memory region M.sub.1, which contains the primary list 19, and a second dynamic object memory region M.sub.2, which contains a second list or “secondary list” 25 with geoobjects ob.sub.j that can be updated dynamically. The index tree 16 is stored in a separate static index memory region M.sub.3 of the memory 9. The term “static” storage of the index tree 16 and of the primary list 19 in the memory regions M.sub.1 and M.sub.3 is understood to mean a feed repeated just once or seldom via the data path 24. The term “dynamic” storage of the secondary list 25 in the object memory region M.sub.2 is understood to mean a feed from the central unit 12 via the radio interface 11 during running operation of the OBU 3 (see data paths 26, 27).

(19) The leaves lv.sub.m of the index tree 16 are additionally each provided with a reference field 18 to an entry 29 in the secondary list 25, which entry 29, as in the primary list 19, contains an identifier id.sub.j of a geoobject ob.sub.j, this geoobject ob.sub.j and also (optionally) a chain field 20 and a “deleted”-flag 21. The reference field 28 of the leaf lv.sub.m stores, for example directly, the object identifier id.sub.j of the geoobject ob.sub.j of the entry 29 of the secondary list 25, which produces a link 30.

(20) When the processor 10 of the OBU 3 in the case of the aforementioned map matching and search for this purpose through the index tree 16 comes across a leaf lv.sub.m, in the reference field 28 of which an object identifier id.sub.j is stored, it removes the object ob.sub.j thus referenced from the secondary list 26 instead of from the primary list 19, and the secondary list is used as a matter of priority before the primary list 19 with regard to the same geoobject ob.sub.j.

(21) If, in the primary list 19, no such object ob.sub.j was present, the locating of the object ob.sub.j in the secondary list 25 corresponds to an “addition” of a new geoobject ob.sub.j in a leaf lv.sub.m and the existence of geoobjects ob.sub.j in the OBU 3. If a geoobject ob.sub.j of the identifier id.sub.j located in the secondary list 25 was also present in the primary list 19, this corresponds to a “replacement”. The “deleted”-flag 21 of a geoobject ob.sub.j in the secondary list 25 (and additionally also in the primary list 19) can be used to “delete” a geoobject ob.sub.j by setting the “deleted”-flag 21, and the processor 10 ignores geoobjects ob.sub.j with set flag 21 when performing map matching. A “replacement” can additionally also be performed by initially deleting a geoobject ob.sub.j with the identifier id.sub.j and then adding it in again.

(22) A dedicated secondary list 25 can be created in the second object memory region M.sub.2 for each leaf lv.sub.m of the index tree 16, or a common secondary list 27 can be used for all (or at least a number of) leaves lv.sub.m.

(23) The chain fields 20 in the primary and secondary lists 19, 25 can be used to refer from a geoobject ob.sub.j located via the links 22, 23, 30 to another geoobject ob.sub.j in the respective primary or secondary list 19, 25, see the chains 31, 32, 33. For example with the aid of a single reference 30 from a leaf lv.sub.m to the secondary list 25 or an entry 29 therein, it is thus possible to reference an entire row of newly added or updated geoobjects ob.sub.j or geoobjects ob.sub.j intended for deletion, that is to say to assign these geoobjects to the leaf lv.sub.m. A change of the leaf lv.sub.m in the index tree 16 (and therefore in the static index memory region M.sub.3) is not necessary for this purpose, and therefore the index tree 16 is hereby also updated so to speak. The secondary list 25 thus enables a dynamic updating at the same time both of the index tree 16 in the index memory region M.sub.1 and of the primary list 19 in the first object memory region M.sub.2.

(24) In order to quickly store a secondary list 25 received via the radio interface 11 in the OBU 3, an identifier of the branch b.sub.1 carrying the leaf lv.sub.m with the reference 28 to this secondary list 25 can also be transmitted with each secondary list 25, and the secondary list 25 can be stored in the second object memory region M.sub.2 at the location specified by this reference 28.

CONCLUSION

(25) The invention is not limited to the presented embodiments, but includes all variants, combinations and modifications that lie within the scope of the accompanying claims.