Бортовой блок и способ обновления геоданных в нем
Изобретение относится к вычислительным технологиям для взимания платы. Технический результат заключается в минимизации среднего времени доступа к геообъектам для обеспечения взимания платы за транспортное средство. Технический результат достигается за счет бортового блока, предназначенного для взимания платы за транспортное средство, с приемником спутниковой навигации для образования привязок (pi) местоположения, памятью для регистрации геообъектов (obj), радиоинтерфейсом и процессором, который образует данные (tr) о сборах на основании географического сравнения привязок (pi) местоположения с геообъектами (obj) на цифровой карте и передает эти данные через радиоинтерфейс, при этом память имеет область (М3) памяти для индексов, предназначенную для дерева индексов геообъектов (obj), первую область (М1) статической памяти для объектов, предназначенную для первичного списка геообъектов (obj), и вторую область (М2) памяти для объектов, в которую можно динамически записывать через радиоинтерфейс, для вторичного списка геообъектов (obj), при этом по меньшей мере один лист (lvm) дерева индексов содержит ссылку на вторичный список. 2 н. и 8 з.п. ф-лы, 4 ил.
Изобретение относится к бортовому блоку для взимания платы за транспортное средство, содержащему приемник спутниковой навигации для образования привязок местоположения, память для регистрации геообъектов, радиоинтерфейс и процессор, соединенный с этими компонентами, который сконфигурирован для образования данных о плате на основании географического сравнения привязок местоположения с геообъектами на цифровой карте и для передачи этих данных через радиоинтерфейс. Кроме того, изобретение относится к способу обновления геоданных в таком бортовом блоке.
В бортовых блоках (БП), основанных на спутниковых навигационных системах (глобальных навигационных спутниковых системах, ГНСС), в качестве радиоинтерфейса обычно используют мобильный радиомодуль для наземных мобильных радиосетей (наземных сетей мобильной связи общего пользования, НСМСОП) и поэтому их относят к бортовым блокам ГНСС/НСМСОП. Для упомянутого выше географического сравнения («сопоставления с картой») привязок местоположения, полученных на основе глобальной навигационной спутниковой системы, с геообъектами, сохраняемыми в бортовом блоке, необходимо быстро обнаруживать ближайшие геообъекты. Для этого в настоящее время используют целый ряд географических или двумерных индексов, таких как индексы квадродеревьев, R-деревьев или kd-деревьев и преобразований их, см., например, Hanan Samet, “Foundation of Multidimensional and Metric Data Structures”, Morgan Kaufmann, 2006; M. deBerg et al., “Computational Geometry - Algorithms and Applications”, Springer, 1997; или Yannis Manolopoulos et al., “R-Trees: Theory and Applications”, Springer, 2006. Деревья индексов этого вида оптимизируют относительно поля данных, чтобы они были обследованными («сбалансированными») для минимизации среднего времени доступа к геообъектам, расположенным на кончиках ветвей дерева. Поэтому деревья индексов и геообъекты согласовывают друг с другом, так что обновление индивидуальных геообъектов в общем случае означает, что индекс также может быть пересчитан. Для этого требуется передача больших объемов данных через радиоинтерфейс, если вычисления выполняют централизованно, или более значительная вычислительная мощность в бортовых блоках, если вычисления выполняют децентрализованно, при этом в любом случае возникают проблемы с обновлением геообъектов и индексов. Задача изобретения заключается в нахождении решения для этих проблем.
Согласно первому аспекту эта задача решается бортовым блоком упомянутого во введении вида, который в соответствии с изобретением отличается тем, что память имеет:
область памяти для индексов, в которой сохранено дерево индексов для геообъектов, каждая из самых дальних ветвей которого приписана к ячейке цифровой карты и несет лист с идентификатором геообъекта этой ячейки,
первую область статической памяти для объектов, в которой сохранен первичный список с геообъектами и их идентификаторами, и
вторую область памяти для объектов, в которую можно динамически записывать через радиоинтерфейс и в которой сохраняются по меньшей мере один вторичный список с геообъектами и их идентификаторами;
при этом по меньшей мере один лист дерева индексов содержит ссылку на вторичный список; и
при этом процессор сконфигурирован, при доступе к геообъекту (obj) через лист (lvm), когда этот лист содержит ссылку (28) на вторичный список (25), с возможностью использования вторичного списка в приоритетном порядке перед первичным списком.
Согласно второму аспекту изобретения дополнительно разработан способ обновления геоданных в таком бортовом блоке, содержащий этапы, на которых:
создают вторичный список в центральном блоке,
передают вторичный список, без дерева индексов и без первичного списка, из центрального блока к бортовому блоку и принимают вторичный список в бортовом блоке через функциональный интерфейс.
В соответствии с изобретением геообъекты, подлежащие сохранению в бортовом блоке, подразделяются на основную запись («первичный список» статически сохраняемых геообъектов и обновляемую запись («вторичный список») динамически обновляемых геообъектов, при этом для обновления только последний необходимо передавать через радиоинтерфейс, поскольку дерево индексов снабжено согласно изобретению ссылками на вторичный список и связями с ним. С одной стороны, этим экономится значительная ширина полосы при обновлении через радиоинтерфейс, поскольку ни дерево индексов, ни обширный первичный список не должны передаваться, и с другой стороны, дерево индексов в бортовом блоке не должно повторно рассчитываться, в результате чего экономится значительная вычислительная мощность в бортовом блоке.
Кроме того, чтобы содействовать сохранению обновленного вторичного списка (списков) в бортовом блоке, идентификатор ветви, несущий лист со ссылкой на этот вторичный список, предпочтительно передавать с каждым вторичным списком, а вторичный список сохранять во второй области памяти для объектов на месте, точно определенном этой ссылкой.
Согласно дальнейшим предпочтительным вариантам осуществления изобретения выделенный вторичный список для по меньшей мере двух листьев можно сохранять в бортовом блоке во второй области памяти для объектов, что облегчит организацию и вычисление вторичных списков, или по меньшей мере два листа могут ссылаться на один и тот же вторичный список, что будет минимизировать необходимый объем памяти в бортовом блоке.
При использовании вторичного списка (списков) геообъекты можно добавлять в бортовой блок, удалять из него или обновлять без передачи или перерасчета дерева индексов и первичного списка. Для операций удаления предпочтительно по меньшей мере один геообъект во вторичном списке снабжать флагом «удаления» и процессор конфигурировать, при доступе к геообъекту, для которого установлен флаг «удаления», с возможностью игнорирования этого геообъекта. При добавлении нового геообъекта во вторичный список можно легко выполнять дополнительные операции, а при желании операции обновления можно выполнять при использования сочетания операций, в частности, удаляя старые версии геообъектов с помощью флага «удаления» и добавляя новую версию того же самого геообъекта.
Кроме того, несколько новых геообъектов можно добавлять на лист дерева индексов и сохранять эти добавляемые геообъекты связанными в цепь во вторичном списке, к которому этот лист относится. Для этого предпочтительно, чтобы по меньшей мере один геообъект из вторичного списка содержал идентификатор следующего геообъекта из вторичного списка.
Эту концепцию цепочечного хранения геообъектов можно также использовать в первичном списке, чтобы экономить объем памяти в листьях дерева индексов, поскольку по меньшей мере один геообъект из первичного списка содержит идентификатор следующего геообъекта из первичного списка.
Управление областью динамической памяти для объектов вторичного списка может быть упрощено, если все геообъекты во вторичном списке имеют одинаковый размер. Поэтому при обновлении вторичного списка можно легко осуществлять перезапись отдельных геообъектов.
Бортовой блок и способ изобретения пригодны для географического индекса любого вида, например, для структур индексов, поясненных во введении, таких как квадродеревья, R-деревья или kd-деревья. Особенно предпочтительно, чтобы дерево индексов было сбалансированным квадродеревом, которое особенно хорошо подходит для поиска ближайших геообъектов в случае сопоставления с картой.
Ниже изобретение будет описано более подробно на основе примеров вариантов осуществления, показанных на сопровождающих чертежах, на которых:
фиг. 1 - вид цифровой карты с геообъектами и деревом индексов типа квадродерева, предназначенной для обнаружения объектов;
фиг. 2 - вид дерева индексов типа квадродерева из фиг. 1 в другом схематичном иллюстративном стиле;
фиг. 3 - структурная схема бортового блока в сочетании со спутниковой навигационной системой и центральным узлом системы платы за проезд для осуществления способа изобретения; и
фиг. 4 - внутренняя структура памяти бортового блока из фиг. 3.
На фиг. 1 показан географический район 1, в котором транспортное средство 2 с бортовым блоком (БП) 3 движется, например, по маршруту 4. Чтобы определять маршрут 4 для взимания платы, бортовой блок 3 снабжен приемником 5 спутниковой навигации, см. фиг. 3, который принимает данные 6 спутниковой навигации из глобальной спутниковой навигационной системы (ГСНС) 7 и на основании их непрерывно образует привязки p1, p2, …, местоположения, в общем случае pi.
Вместе с тем на фиг. 1 показана цифровая карта 8 географического района 1, на которую нанесены геообъекты ob1, ob2, …, в общем случае obj, из числа фактических геообъектов obj географического района 1. Примерами геообъектов obj являются границы района, такие как границы городов, границы площадок для парковки, внутренние городские границы и т.д. (см. ob1, ob3), пункты перегрузки, такие, как на границах стран, пункты пересечения границы при въезде и выезде, шлагбаумы и т.д. (см. ob4), или пропускные пункты, например, такие места, как «виртуальные пункты взимания платы», контрольные пункты и т.д. (см. ob2, ob5, ob6, ob7). Геообъекты obj сохраняются во внутренней памяти 9 бортового блока 3, структура которого будет подробно пояснена позже на основе фиг. 4.
Внутренний процессор 10 бортового блока 3 непрерывно сравнивает последовательность {pi} привязок pi местоположения с геообъектами obj, сохраняемыми в памяти 9, для нахождения ближайшего геообъекта (объектов) obj и для обнаружения на основании этого, например, пересечения границы, пункта взимания платы, контрольного пункта или проезда мимо жилища на определенной части или на определенном участке дороги и т.д. Результат этого географического сравнения («сопоставления с картой») используется как основа для образования соответствующих данных tr о сборах, которые затем передаются процессором 10 через радиоинтерфейс 11 бортового блока 3 в удаленный центральный узел 12 для оценивания или взимания платы по маршруту 4 транспортного средства 2 (стрелка 13).
Радиоинтерфейс 11 представляет собой, например, мобильный радиомодуль для мобильной сети 14 радиосвязи, работающий, например, в соответствии со стандартом 3G, 4G или 5G сети радиосвязи, таким как GSM, UMTS или LTE, через который осуществляется связь центрального узла 12 с бортовым блоком 3. Как известно в соответствующей области техники, на основании принимаемых данных tr о сборах в центральном узле 12 могут создаваться соответствующие путевые или платежные протоколы 15 для взимания платы за место, используемое транспортным средством 2.
Чтобы быстро определять место нахождения ближайшего геообъекта (объекта) obj в соответствии с одной или несколькими привязками pi местоположения, геообъекты obj на цифровой карте 8 или в памяти 9 бортового блока 3 индексируют, более конкретно, иерархическими индексами в виде дерева 16 индексов, которое показано на фиг. 1, 2 и 4 в различных иллюстративных стилях.
Предпочтительно, чтобы дерево 16 индексов было географическим, то есть, например, двумерным деревом индексов типа квадродерева, R-дерева или kd-дерева или аналогичного, и на фиг. 1, 2 и 4 показан отдельный вариант осуществления квадродерева, на котором каждый узел n1, n2, …, в общем случае nk, в каждом случае разветвляется на четыре ветви b1, b2, …, в общем случае bl, которые на концах разветвляются или не разветвляются через посредство дальнейших узлов nk на дальнейшие ветви bl.
Самые дальние ветви bl, дальше всего отстоящие от исходного узла (корня) n1 дерева 16 индексов, приписаны к ячейкам c1, c2, …, в общем случае cm, цифровой карты 8, и они несут листья lv1, lv2, …, в общем случае lvm, которые, как будет пояснено впоследствии с обращением к фиг.4, содержат или обозначают геообъекты obj, содержащиеся в этой ячейке cm.
На фиг. 1 показано, что такое дерево 16 индексов типа квадродерева разделяет цифровую карту 8 на последовательные небольшие четверки ячеек, вложенные одна в другую. Географические разделительные линии 17 между ячейками cm и, следовательно, ветви bl и узлы nk дерева 16 индексов выбирают так, чтобы достигалось наиболее равномерное распределение возможно большего количества геологических объектов obj по листьям lvm или ячейкам cm. Как известно специалисту в соответствующей области техники, этим минимизируется среднее время доступа к геообъектам obj при поиске на протяжении дерева 16 индексов.
На фиг. 4 показан другой вид такого же дерева 16 индексов с (в данном случае для примера) двумя узлами n1, n2, из которых иерархически нижерасположенный узел n2 разветвляется на две ветви b1 и b2, показанные для примера, и каждая имеет лист lv1, lv2. Каждый лист lvm содержит ограниченное количество запоминающих ячеек 18 для объектных идентификаторов idj геообъектов obj, которые сохраняются в первом списке или «первичном списке» 19 геообъектов obj.
Каждый геообъект obj из первичного списка 19 сохраняется вместе с идентификатором idj объекта и может дополнительно содержать поле 20 цепи и флаг 21 «удаления», функции которых будут рассмотрены более подробно впоследствии. Поэтому каждая запоминающая ячейка 21 листа lvm, в которой сохраняется идентификатор idj объекта, относится к геообъекту obj из первичного списка 19, см., например, связь 22. Кроме того, листья lv1, lv2 могут относиться к одному и тому же геообъекту obj из первичного списка 19, что показано двумя связями 22, 23.
Дерево 16 индексов и первичный список 19 могут сохраняться в памяти 9 бортового блока 3, например, с выдачей из бортового блока 3 пользователю, см. стрелку 24. Поскольку первичный список 19 может содержать очень большое количество геообъектов obj в случае большого географического района 1, например, тысячи или десятки тысяч геообъектов obj, первичный список 19 является весьма объемлющим, и структура сбалансированного дерева 16 индексов является очень сложной, и обновление во время выполнения операции через радиоинтерфейс 11 практически невозможны по причинам, упомянутым во введении. Хотя через радиоинтерфейс 11 передаются сведения только о небольшом количестве геообъектов obj, повторный расчет дерева 16 индексов для балансировки с тем, чтобы минимизировать время доступа, трудно реализовать при ограниченной вычислительной мощности бортового блока 3. Описанное ниже расширение представленной системы используется для минимизации затрат при обновлении и вычислении дерева 16 индексов и геообъектов obj.
Память 9 бортового блока 3 разделена на первую область М1 статической памяти для объектов, в которой содержится первичный список 19, и вторую область М2 динамической памяти для объектов, в которой содержится второй список или «вторичный список» 25 геообъектов obj, который может обновляться динамически. Дерево 16 индексов сохраняется в отдельной области М3 статической памяти для индексов, принадлежащей к памяти 9. Понятно, что термин «статическое» запоминание дерева 16 индексов и первичного списка 19 в областях М1 и М3 памяти означает передачу, повторяемую только один раз или изредка по маршруту 24 передачи данных. Понятно, что термин «динамическое» запоминание вторичного списка 25 в области М2 памяти для объектов означает передачу из центрального узла 12 через радиоинтерфейс 11 во время выполнения операций бортовым блоком 3 (см. маршруты 26, 27 передачи данных).
Каждый лист из листьев lvm дерева 16 индексов дополнительно снабжен полем 18 ссылки на ввод 29 во вторичный список 25, а этот ввод 29, как и в случае первичного списка 19, содержит идентификатор idj геообъекта obj, этот геообъект obj и также (необязательно) поле 20 цепи и флаг 21 «удаления». В поле 28 ссылки на листья lvm сохраняется, например непосредственно, объектный идентификатор idj геообъекта obj из ввода 29 вторичного списка 25, и это поле образует связь 30.
Когда в случае упомянутого выше сопоставления с картой и поиска для этого сопоставления с помощью дерева 16 индексов процессор 10 бортового блока 3 доходит до листа lvm, в поле 28 ссылки которого сохраняется идентификатор idj объекта, он удаляет объект obj, таким образом обозначенный, из вторичного списка 25, но не из первичного списка 19, и относительно того же самого геообъекта obj вторичный список используется в приоритетном порядке перед первичным списком 19.
Если в первичном списке 19 такой объект obj не присутствует, локализация объекта obj во вторичном списке 25 соответствует «добавлению» нового геообъекта obj в лист lvm и существованию геообъектов obj в бортовом блоке 3. Если геообъект obj, принадлежащий идентификатору idj, находящийся во вторичном списке 25, также присутствует в первичном списке 19, это соответствует «замене». Флаг 21 «удаления» геообъекта obj во вторичном списке 25 (и дополнительно также в первичном списке 19) можно использовать для «удаления» геообъекта obj путем установки флага 21 «удаления», и в случае установленного флага 21 процессор 10 будет игнорировать геообъекты obj при выполнении сопоставления с картой. Кроме того, дополнительно «замену» можно выполнять путем первоначального удаления геообъекта obj вместе с идентификатором idj и затем добавления его заново.
Выделенный вторичный список 25 может быть образован во второй области М2 памяти для объектов применительно к каждому листу lvm дерева 16 индексов или общий вторичный список 27 может быть использован для всех (или по меньшей некоторого количества) листьев lvm.
Поля 20 цепей в первичном и вторичном списках 19, 25 могут использоваться для ссылки от геообъекта obj, обнаруживаемого с помощью связей 22, 23, 30, на другой геообъект obj в соответствующем первичном или вторичном списке 19, 25, см. цепи 31, 32, 33. Поэтому, например, с помощью единственной ссылки 30 от листа lvm на вторичный список 25 или ввод 29 в нем можно сослаться на весь ряд вновь добавленных или обновленных геообъектов obj или к геообъектам obj, намеченным к удалению, иначе говоря, можно приписать эти геообъекты к листу lvm. Для этого нет необходимости изменять лист lvm на дереве 16 индексов (и поэтому в области М3 статической памяти для индексов) и, следовательно, тем самым также обновлять, если можно так выразиться, дерево 16 индексов. Таким образом, вторичный список 25 дает возможность одновременно выполнять динамическое обновление дерева 16 индексов в области М1 памяти для индексов и первичного списка 19 в первой области М3 памяти для объектов.
Для быстрого сохранения вторичного списка 25, принимаемого через радиоинтерфейс 11 в бортовом блоке 3, идентификатор ветви bl, несущей лист lvm с полем 28 ссылки на этот вторичный список 25, также может быть передан вместе с каждым вторичным списком 25, и вторичный список 25 может быть сохранен во второй области М2 памяти для объектов на месте, задаваемом этим полем 28 ссылки.
Изобретение не ограничено представленными вариантами осуществления, а включают в себя все варианты, сочетания и модификации, которые находятся в объеме прилагаемой формулы изобретения.
1. Бортовой блок для взимания платы за транспортное средство, содержащий:
приемник (5) спутниковой навигации для образования привязок (pi) местоположения;
память (9) для регистрации геообъектов (obj);
радиоинтерфейс (11); и
процессор (10), соединенный с этими компонентами (5, 9, 11), который сконфигурирован для образования данных (tr) о плате на основании географического сравнения привязок (pi) местоположения с геообъектами (obj) на цифровой карте (8) и для передачи этих данных через радиоинтерфейс (11);
отличающийся тем, что память (9) имеет:
область (М3) памяти для индексов, в которой сохранено дерево (16) индексов для геообъектов (obj), каждая из самых дальних ветвей (bl) которого приписана к ячейке (cm) цифровой карты (8) и несет лист (lvm) с идентификаторами (idj) геообъектов (obj) этой ячейки (cm),
первую область (М1) статической памяти для объектов, в которой сохранен первичный список (19) с геообъектами (obj) и их идентификаторами (idj), и
вторую область (М2) памяти для объектов, в которую можно динамически записывать через радиоинтерфейс и в которой сохраняются по меньшей мере один вторичный список (19) с геообъектами (obj) и их идентификаторами (idj);
при этом по меньшей мере один лист (lvm) дерева (16) индексов содержит ссылку (28) на вторичный список (25); и
при этом процессор (10) сконфигурирован, при доступе к геообъекту (obj) через лист (lvm), когда этот лист содержит ссылку (28) на вторичный список (25), с возможностью использования вторичного списка (25) в приоритетном порядке перед первичным списком(19).
2. Бортовой блок по п. 1, отличающийся тем, что выделенный вторичный список (29) для каждого из по меньшей мере двух листьев (lvm) сохранен во второй области (М2) памяти.
3. Бортовой блок по п. 1, отличающийся тем, что по меньшей мере два листа (lvm) ссылаются на один и тот же вторичный список (25).
4. Бортовой блок по одному из пп. 1-3, отличающийся тем, что по меньшей мере один геообъект (obj) во вторичном списке (25) снабжен флагом (21) «удаления« и процессор (10) сконфигурирован, при доступе к геообъекту (obj), для которого установлен флаг (21) «удаления«, с возможностью игнорирования этого геообъекта.
5. Бортовой блок по одному из пп. 1-3, отличающийся тем, что по меньшей мере один геообъект (obj) из вторичного списка (25) содержит идентификатор (idj) следующего геообъекта (obj) из вторичного списка (25).
6. Бортовой блок по одному из пп. 1-3, отличающийся тем, что по меньшей мере один геообъект (obj) из первичного списка (19) содержит идентификатор (idj) следующего геообъекта (obj) из первичного списка (19).
7. Бортовой блок по одному из пп. 1-3, отличающийся тем, что все геообъекты (obj) во вторичном списке (25) имеют одинаковый размер.
8. Бортовой блок по одному из пп. 1-3, отличающийся тем, что дерево (16) индексов представляет собой сбалансированное квадродерево.
9. Способ обновления геоданных в бортовом блоке по одному из пп. 1-8, содержащий этапы, на которых:
создают вторичный список (25) в центральном блоке (12),
передают вторичный список (25), без дерева (16) индексов и без первичного списка (19), из центрального блока (12) к бортовому блоку (3) и принимают вторичный список (25) в бортовом блоке (3) через радиоинтерфейс (11).
10. Способ по п. 9 в сочетании с п. 2, отличающийся тем, что идентификатор ветви (bl), несущей лист (lvm) со ссылкой (28) на этот вторичный список (25), также передают вместе с каждым вторичным списком (25), а вторичный список (25) сохраняют во второй области (М2) памяти для объектов на месте, точно определенном этой ссылкой (28).
