Способ и система для хранения и быстрого извлечения высотных отметок цифровых моделей местности для использования в системах определения местоположения

Способ и система для хранения и быстрого извлечения высотных отметок цифровых моделей местности для использования в системах определения местоположения

Иллюстрации

Показать все

Реферат

Изобретение относится к комбинированным системам определения местоположения с помощью беспроводной связи, и более конкретно к хранению и извлечению (поиску) отметок превышения рельефа, или высотных отметок, в цифровых моделях рельефа местности.

Для выполнения определения местоположения в беспроводных сетях сотовой связи (например, сеть сотовой телефонной связи) в некоторых подходах выполняют триангуляцию, основанную на использовании информации об измерениях времени, которую посылают между каждой из нескольких базовых станций и подвижным мобильным устройством, таким как сотовый телефон. Один подход, имеющий название Расширенная трилатерация (трехстороннее измерение) по прямой линии связи (РТПЛС) или Усовершенствованная фиксация разности времен (прихода сигналов) (EOTD), измеряет на подвижном устройстве времена прихода сигналов, переданных от каждой из нескольких базовых станций. Эти значения времен передают на сетевой Элемент (ЭОМ) определения местоположения абонента (например, на сервер определения местоположения, или сервер местоположения), который вычисляет местоположения подвижного устройства, используя эти времена приема. Истинные времена («времена-дня») на этих базовых станциях скоординированы так, что в конкретный момент времени истинные времена, связанные со множественными базовыми станциями, находятся в пределах заданной ошибки (погрешности). Точные местоположения базовых станций и времена приема используют для определения местоположения подвижного устройства.

На фиг. 1 показан пример системы РТПЛС, в которой времена (TR1, TR2, и TR3) приема сигналов от базовых станций 101, 103, 105 сотовой связи измеряют на мобильном сотовом телефоне 111. Эти данные об измерении времени затем могут быть использованы, чтобы вычислить местоположение подвижного устройства. Такое вычисление может быть сделано непосредственно на подвижном устройстве, или на сервере местоположения, если информацию об измерении времени, полученную таким образом подвижным устройством, передают на сервер местоположения посредством линии связи. Обычно времена приемов передают на сервер 115 местоположения через одну из базовых станций сотовой связи (например, базовую станцию 101, или 103, или 105). Сервер 115 местоположения соединяют для приема данных от базовых станций посредством центра 113 коммутации мобильной связи. Центр 113 коммутации мобильной связи обеспечивает сигналы (например, передачу речевых сообщений) на Коммутируемую телефонную систему (PSTS) общего пользования наземной линии связи и от PSTS, так что сигналы могут быть переданы на мобильный телефон и от мобильного телефона на другие телефоны (например, телефоны наземной линии связи в PSTS или другие подвижные телефоны). В некоторых случаях сервер местоположения может также обмениваться информацией с центром коммутации подвижной связи через линию сотовой связи. Сервер местоположения может также управлять распространением сигналов от нескольких из базовых станций при определении относительного времени распространения этих сигналов.

В другом подходе, который назван Разность моментов времени прихода сигналов (TDOA), времена приема сигнала от подвижного устройства измеряют на нескольких базовых станциях. Фиг. 1 применима к такому случаю, если направления стрелок TR1, TR2 и TR3 изменены на противоположные. Такие данные об измерении времени затем могут быть переданы на сервер местоположения, чтобы вычислить местоположение подвижного устройства.

Следующий, третий, способ определения местоположения включает в себя использование в подвижном устройстве приемника, предназначенного для Глобальной спутниковой системы (GPS) США определения местоположения абонента сотовой связи или другой Спутниковой системы (ССОМ) определения местоположения, такой как российская (Глобальная навигационная спутниковая) система GLONASS и предложенная Европейским Союзом система Galileo, или комбинации спутников и станций-псевдоспутников. Станции-псевдоспутники являются наземными передатчиками, которые передают PN-код (псевдошумовой, ПШ) (подобный сигналу GPS), модулируемый на сигнале с несущей на полосе сверхвысоких частот, обычно синхронизируемом со временем ССОМ. Каждому передатчику может быть назначен уникальный PN-код, чтобы допустить идентификацию удаленным приемником. Станции-псевдоспутники являются полезными в ситуациях, в которых сигналы ССОМ от орбитального спутника могут быть недоступными, например в туннелях, шахтах, зданиях или других замкнутых пространствах. Термин "спутник", используемый в описании, подразумевает станцию-псевдоспутник или эквиваленты станций-псевдоспутников, и термин «GPS-сигналы», используемый в описании, подразумевает сигналы, подобные сигналам GPS, от станциий-псевдоспутников или эквивалентов станций-псевдоспутников. Такой способ, использующий приемник для ССОМ-сигналов, может быть полностью автономным или может использовать сеть сотовой связи для обеспечения вспомогательных (для помощи в установлении соединения) данных, или для совместного использования в вычислении местоположения. Примеры такого способа описаны в патентах США № 5841396; № 5945944; и № 5812087. Для краткости также способы здесь названы как способы "ССОМ". В практических недорогих вариантах осуществления и приемник сети подвижной сотовой связи, и ССОМ-приемник объединены в один конструктивный блок (корпус) и могут фактически совместно использовать общую электронную схему.

Комбинацию из либо РТПЛС, либо TDOA с системой ССОМ называют "комбинированной" системой.

В следующем способе определяют двустороннюю временную задержку (ДВЗ) для сигналов, которые посылают с базовой станции на подвижное устройство и затем возвращают. В подобном, но альтернативном, способе определяют двустороннюю временную задержку для сигналов, которые посылают от подвижного устройства на базовую станцию и затем возвращают. Каждую из этих двусторонних временных задержек делят на два, чтобы определить оценку односторонней временной задержки. Знание местоположения базовой станции, включая одностороннюю задержку, ограничивает местоположение подвижного устройства окружностью на поверхности Земли. Два таких измерения имеют затем результатом пересечение двух окружностей, которое в свою очередь ограничивает местоположение двумя точками на поверхности Земли. Третье измерение (даже угол прихода или сектор сотовой ячейки) разрешает неоднозначность.

Поддержку измерения высоты, или высотную поддержку, использовали в различных способах, предназначенных для определения местоположения подвижного устройства. Высотная поддержка обычно основана на псевдоизмерении высоты. Знание высоты для местоположения подвижного устройства ограничивает возможные местоположения подвижного устройства поверхностью сферы (или эллипсоида) с центром, помещенным в центр Земли. Такое знание может быть использовано, чтобы уменьшить количество независимых измерений, требуемых для определения местоположения подвижного устройства. Обычно оценка высоты может быть вручную подана оператором подвижного устройства, или может быть установлена на значение высоты из предыдущего трехмерного решения, или может быть установлена на заранее установленное значение, или может быть получена из картографической информации, такой как база топографических или геодезических данных, поддерживаемая на сервере местоположения.

В патенте США № 6061018, который включен в настоящее описание в качестве ссылки, описан способ, в котором оценку высоты определяют на основании информации объекта сотовой связи, который может быть узлом сотовой связи, имеющим передатчик при обмене информацией с подвижным устройством. В патенте США № 6061018 также описан способ определения условия измерений псевдодальностей от множества спутников ССОМ посредством сравнения высоты, вычисленной на основании измерений псевдодальности, с оценкой высоты.

Иногда таблицу данных о высоте, имеющих более низкое разрешение, сохраняют в оперативном запоминающем устройстве. Обычно картографическую информацию с высоким разрешением, такую как топографическая или геодезическая базы данных, сохраняют в одном или нескольких однородных, или плоских, файлах (неиндексированных) на сервере местоположения. Например, глобальная Цифровая модель рельефа (DEM), имеющая шаг сетки по горизонтали, соответствующий дуге в 30 секунд (приблизительно 1 километр), может быть получена из Геологической службы США в комплекте из пяти компакт-дисков КД-ПЗУ (CD-ROM). Файл DEM из Геологической службы США (http://edcdaac.usgs.gov/) поставляют в виде 16-битовых целых чисел со знаком в простом общем двоичном растровом формате. В данные изображения вложены ограниченный заголовок и иногда заключительные байты. Данные сохраняют в сквозном порядке строк (все данные для строки 1, за которыми следуют все данные для строки 2, и т.д.).

Иногда на Цифровую модель рельефа (DEM) также ссылаются, как на Цифровую модель (ЦММ) местности (земной поверхности).

Настоящее описание раскрывает способы и устройства для формирования сжатых и индексированных высотных отметок и осуществления доступа к сжатым и индексированным высотным отметкам Цифровых моделей рельефа.

В одном аспекте настоящего изобретения способ хранения данных о высотных отметках включает в себя: сжатие данных высотных отметок из первой (начальной) порции Цифровой модели рельефа (DEM), чтобы сформировать первые (начальные) сжатые данные высотных отметок; сохранение первых сжатых данных высотных отметок в ячейке запоминающего устройства, на которую указывает первый индекс; и сохранение первого индекса. В одном примере, соответствующем этому аспекту, данные высотных отметок из первой порции являются сжатыми посредством: вычитания опорной высоты из данных высотных отметок первой порции Цифровой модели рельефа (DEM), чтобы сформировать нормированные данные высотных отметок; масштабирование нормированных данных высотных отметок, чтобы сформировать масштабированные данные высотных отметок; и групповое кодирование (длины серий) масштабированных данных высотных отметок, чтобы сформировать первые сжатые данные высотных отметок. В одном примере параметры, требуемые для определения, находится или не находится местоположение в первой порции Цифровой модели рельефа, а также данные преобразования, задающие систему координат, используемую для представления данных высотных отметок из первой порции Цифровой модели рельефа, являются также сохраняемыми. В одном примере Цифровая модель рельефа разделена на множество областей; область Цифровой модели рельефа разделена на множество элементов «мозаичного» представления модели, или элементов модели, и профили в каждом из множества элементов модели, находящихся в области Цифровой модели рельефа, являются индивидуально сжатыми. Параметры, требуемые для определения, находится или не находится местоположение в одном из множества элементов модели, а также параметры, требуемые для определения, находится или не находится местоположение в одном из множества областей, являются также сохраняемыми.

В другом аспекте настоящего изобретения способ извлечения данных высотных отметок включает в себя: определение местоположения первой сжатой порции Цифровой модели (DEM) рельефа, используя первый индекс; и развертывание сжатых данных первой сжатой порции, чтобы извлечь первые данные высотных отметок по меньшей мере для одной точки дискреты представления модели в Цифровой модели рельефа. Цифровая модель рельефа имеет множество сжатых порций, которое включает в себя первую сжатую порцию, и первый индекс, указывающий ячейку запоминающего устройства, в которой сохраняют первую сжатую порцию.

В одном примере в соответствии с этим аспектом развертывание первой сжатой порции осуществляют посредством: группового декодирования первой сжатой порции, чтобы сформировать масштабированные данные высотных отметок; обратного масштабирования масштабированных данных высотных отметок, чтобы сформировать нормированные данные высотных отметок; и сложения опорной высоты с нормированными данными высотных отметок, чтобы сформировать первые данные высотных отметок. В одном примере множество сжатых порций сохраняют в одном из: a) в файле, отображенном на память (MMF); b) оперативном запоминающем устройстве (ОЗУ, RAM); и c) в файле файловой системы в системе цифровой обработки; и множество сжатых порций являются порциями сжатых профилей в элементе модели Цифровой модели рельефа.

В одном примере, чтобы вычислить высотную отметку местоположения, идентифицируют область в множестве областей Цифровой модели рельефа; из множества элементов модели, находящихся в области, идентифицируют элемент модели, который содержит местоположение; идентифицируют профиль, который находится вблизи, или в окрестности, местоположения; и осуществляют развертывание по меньшей мере порции профиля, чтобы извлечь данные высотных отметок по меньшей мере для одной точки дискреты. Идентифицируют множество точек дискрет вблизи местоположения. После того как высотные отметки для множества точек дискрет извлечены из Цифровой модели рельефа, высотную отметку местоположения вычисляют на основании интерполяции, используя высотные отметки множества точек дискрет. Выполняют преобразование координат, чтобы позицию местоположения в горизонтальной плоскости выразить в системе координат, используемой Цифровой моделью рельефа. В вычислении высотной отметки местоположения выполняют преобразование координат так, чтобы высотная отметка местоположения была выражена в системе координат, используемой Элементом определения местоположения. Высотную отметку местоположения подают на Элемент определения местоположения, чтобы выполнить высотную поддержку в системе определения местоположения. В одном сценарии высотную отметку поставляют в реальном времени в ответ на запрос от Элемента определения местоположения; и высотную отметку поставляют, чтобы наполнить информацию для данных справочника базовой станции, которые в другом сценарии впоследствии используются Элементом определения местоположения для высотной поддержки.

Настоящее изобретение включает в себя устройства для осуществления этих способов, содержащие системы обработки данных, которые выполняют эти способы, и машиночитаемые носители, которые обеспечивают системам обработки данных выполнять эти способы.

Другие признаки настоящего изобретения будут очевидны из сопроводительных чертежей и из подробного описания, которые следуют ниже.

Настоящее изобретение проиллюстрировано посредством примера, а не ограничения, на сопроводительных чертежах, на которых одними и теми же ссылочными позициями обозначены сходные элементы.

Фиг. 1 - пример относящейся к предшествующему уровню техники сети сотовой связи, которая определяет местоположение подвижного устройства сотовой связи.

Фиг. 2 - пример сервера местоположения, который может быть использован с настоящим изобретением.

Фиг. 3 - способ использования Базы данных рельефа местности (БДРМ) для обеспечения информации о высотных точках местности, или информации о высотах, в реальном времени в течение навигационной обработки в Элементе (ЭОМ) определения местоположения в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 4 - способ наполнения информации о высотах для справочника данных базовой станции, информация из которого может быть использована в течение навигационной обработки в Элементе (ЭОМ) определения местоположения для высотной поддержки, в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 5 - способ формирования Цифровых моделей рельефа в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 6 - примерная схема нумерации элементов модели в области.

Фиг. 7 - пример профиля данных высотных отметок местности.

Фиг. 8 - способ определения высотных отметок местности для местоположения на основании Цифровой модели (DEM) рельефа в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 9 - Обслуживающая подсистема поддержки высотных отметок в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 10 - представление данных элемента Цифровой модели (DEM) рельефа в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 11 - представление данных заголовка, предназначенного для сохранения порции Цифровой модели (DEM) рельефа, в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 12 - схема группового кодирования, которая может быть использована с настоящим изобретением.

Фиг. 13 - пример кодирования порции Цифровой модели (DEM) рельефа для хранения в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 14 - способ кодирования порции Цифровой модели рельефа (DEM) для хранения в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 15 - способ вычисления высотной отметки местоположения в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 16 - один способ извлечения и декодирования порции Цифровой модели (DEM) рельефа для вычисления высотной отметки местоположения в соответствии с одним вариантом осуществления настоящего изобретения.

Нижеследующее описание и чертежи являются иллюстративными для изобретения и не должны рассматриваться в качестве ограничивающих настоящее изобретение. Многочисленные конкретные подробности описаны, чтобы предоставить полное понимание настоящего изобретения. Однако в некоторых примерах известные или обычные подробности не описаны, чтобы избежать внесения неясностей в описание настоящего изобретения.

По меньшей мере один вариант осуществления настоящего изобретения направлен на эффективное хранение данных о высотных отметках местности, или рельефе местности, в базе данных и на эффективное использование данных о рельефе местности из базы данных, чтобы обеспечить оценку высоты для местоположения.

На фиг. 2 показан пример системы обработки данных, которая может быть использована в качестве обслуживающей системы или сервера, в различных вариантах осуществления настоящего изобретения. Например, как описано в патенте США № 5841396, сервер может поставлять вспомогательные (поддерживающие) данные, например доплеровские (Doppler) или другие спутниковые вспомогательные данные, на приемник GPS в подвижной станции. В дополнение, или альтернативно, вычисление конечного местоположения может выполнять сервер местоположения, а не подвижная станция (после приема от подвижной станции данных псевдодальностей или других данных, посредством которых могут быть определены данные псевдодальности), и затем результаты определения конечного местоположения могут быть направлены на базовую станцию или на некоторую другую систему. Система обработки данных в качестве сервера местоположения обычно включает в себя устройства 212 связи, такие как модемы или сетевые интерфейсы. Сервер местоположения может быть соединен с некоторым количеством различных сетей через устройства 212 связи (например, модемы или другие сетевые интерфейсы). Такие сети включают в себя центр коммутации сотовой связи или множественные центры 225 коммутации сотовой связи, коммутаторы 223 наземных телефонных систем, базовые станции сотовой связи, другие источники 227 сигналов GPS или другие процессоры из других серверов 221 местоположения.

Множественные базовые станции сотовой связи обычно расположены, чтобы охватить географическую область зоной обслуживания радиосвязи, и эти различные базовые станции соединены по меньшей мере с одним центром коммутации подвижной связи, как известно из предшествующего уровня техники (например, см. фиг. 1). Таким образом, множество базовых станций может быть географически распределено и соединено вместе посредством центра коммутации подвижной связи. Сеть 220 может быть соединена с сетью из опорных GPS-приемников, которые обеспечивают дифференциальную информацию GPS и могут также обеспечивать данные об эфемеридах GPS для использования в вычислении местоположения подвижных систем. Сеть соединена посредством модема или другого интерфейса связи с процессором 203. Сеть 220 может быть соединена с другими компьютерами или сетевыми компонентами. Сеть 220 также может быть соединена с вычислительными системами, управляемыми операторами аварийных ситуаций, такими как Пункты ответственности за общественную безопасность, которые отвечают на телефонные вызовы (по номеру) 911. Различные примеры способов для использования сервера местоположения были описаны в многочисленных патентах США, например патенты США № 5841396; № 5874914; № 5812087; и № 6215442, которые включены в настоящее описание путем ссылок.

Сервер 201 местоположения, который является разновидностью системы обработки данных, включает в себя шину 202, которая соединена с микропроцессором 203, и ПЗУ 207 (ROM), и энергозависимым ОЗУ 205 (RAM), и энергонезависимым запоминающим устройством 206. Процессор 203 соединен со сверхоперативным запоминающим устройством, или кэшем 204, как показано в примере на фиг. 2. Шина 202 осуществляет межкомпонентное соединение этих различных компонентов вместе. Тогда как на фиг. 2 показано, что энергонезависимая память является локальным устройством, соединенным непосредственно с остальными компонентами в системе обработки данных, и настоящее изобретение может использовать энергонезависимое запоминающее устройство, которое является удаленным от системы, такое как сетевое запоминающее устройство, которое соединено с системой обработки данных посредством сетевого интерфейса, например модемом или сетевым интерфейсом Ethernet. Шина 202 может включать в себя одну или несколько шин, соединенных между собой посредством различных мостов, контроллеров и/или адаптеров, как известно в данном уровне техники. Во многих ситуациях сервер местоположения может выполнять свои операции автоматически без участия персонала. В некоторых схемах (проектах), в которых требуется взаимодействие с персоналом, контроллер 209 ввода/вывода может обмениваться информацией с дисплеями, клавиатурами и другими устройствами ввода/вывода.

Обратите внимание, что, тогда как на фиг. 2 проиллюстрированы различные компоненты системы обработки данных, не предусмотрено представление какой-либо конкретной архитектуры или способа межсоединения компонентов, поскольку такие подробности не входят в настоящее изобретение. Будет также отмечено, что сетевые компьютеры и другие системы обработки данных, которые имеют меньшее количество компонентов или возможно большее количество компонентов, также могут быть использованы с настоящим изобретением и могут действовать в качестве сервера местоположения или ЭОМ.

Из данного описания будет очевидно, что аспекты настоящего изобретения могут быть воплощены, по меньшей мере частично, в программном обеспечении. То есть способы могут быть выполнены в вычислительной системе или в другой системе обработки данных в ответ на исполнение ее процессором последовательностей команд, содержащихся на запоминающем устройстве таком, как ПЗУ 207, энергозависимое ОЗУ 205, энергонезависимое запоминающее устройство 206, кэш 204 или удаленное запоминающее устройство. В различных вариантах осуществления могут быть использованы аппаратные схемы в комбинации с командами программного обеспечения для того, чтобы осуществить настоящее изобретение. Таким образом, способы не являются ограниченными ни какой-либо конкретной комбинацией схемы аппаратного обеспечения и программного обеспечения, ни каким-либо конкретным источником для команд, исполняемых системой обработки данных. В дополнение по всему данному описанию различные функции и операции описаны, как исполняемые или вызываемые программой программного обеспечения, чтобы упростить описание. Однако специалисты в данной области техники признают, что подразумеваемое под такими выражениями является результатом функций от исполнения программы процессором, например процессором 203.

В некоторых вариантах осуществления способы настоящего изобретения могут быть выполнены на вычислительных системах, которые одновременно используются для других функций таких, как коммутация сотовой связи, служба передачи сообщений, и т.д. В таких случаях некоторые или все из средств аппаратного обеспечения по фиг. 2 были бы совместно используемы для нескольких функций.

Тогда как сохранение или извлечение данных высотных отметок местности из базы данных могут быть выполнены на сервере местоположения, эти операции также могут быть выполнены на других системах цифровой обработки, подобных проиллюстрированной на фиг. 2.

На фиг. 3 показан способ использования Базы (БДРМ) данных рельефа местности, чтобы обеспечить информацию о высотах местности в реальном времени в течение навигационной обработки в Элементе определения местоположения (ЭОМ) в соответствии с одним вариантом осуществления настоящего изобретения. База (БДРМ) 301 данных рельефа местности, сохраняемая в соответствии с настоящим изобретением (например, на запоминающем устройстве с произвольной выборкой (ОЗУ, RAM) или на жестком диске), обеспечивает доступ в реальном времени на линии 311 (шине) к серверу 305 местоположения для высотной поддержки. Сервер 305 местоположения может эффективно извлекать высоту для любого заданного местоположения в ходе выполнения определения местоположения подвижной станции.

В одном примере данные 303 справочника на базовой станции поставляют соответствующую горизонтальной плоскости оценку позиции узла сотовой связи на сервер местоположения, который может быть использован, чтобы получить начальную оценку высоты подвижной станции.

Сигналы 309 ССОМ, исходящие от базовых станций или спутников GPS (или других типов спутников ССОМ), принимают на подвижной станции. Сигнал 307 ССОМ, принятый на подвижной станции, используют, чтобы определить моменты времени прихода для сигналов ССОМ, исходящих от базовых станций или спутников ССОМ. Сервер 305 местоположения использует моменты времени прихода, чтобы определить местоположение подвижной станции.

В ходе выполнения многократного определения местоположения подвижной станции, лучшие оценки высоты подвижной станции могут быть извлечены из БДРМ 301, если сервер 305 местоположения определяет более точные координаты в горизонтальной плоскости для подвижной станции на основании времен-прихода (или псевдодальностей).

В другом примере позиция в горизонтальной плоскости, или позиция по горизонтали, определенная на основании времен-прихода, может быть использована для извлечения оценки высоты подвижной станции из БДРМ для того, чтобы определить состояние измерения момента времени прихода (или псевдодальности), используя способы, описанные в патенте США № 6061018.

Тогда как на фиг. 3 проиллюстрирован пример, в котором моменты времени прихода измеряют на мобильной станции, такой как система РТПЛС, система ССОМ или комбинированная система РТПЛС, будет оценено, что такой доступ в реальном времени к БДРМ также может быть использован в других системах определения местоположения, в которых моменты времени прихода измеряют на базовых станциях, например в системе TDOA, в которой моменты времени прихода сигнала от подвижной станции определяют на множестве базовых станций.

На фиг. 4 показан способ наполнения информации о высотах для данных справочника базовой станции, информация которого может быть использована в течение навигационной обработки в Элементе (ЭОМ) определения местоположения для высотной поддержки, в соответствии с одним вариантом осуществления настоящего изобретения. База 401 (БДРМ) данных рельефа местности, сохраняемая в соответствии с настоящим изобретением (например, на запоминающем устройстве с произвольным доступом (ОЗУ, RAM) или на жестком диске), обеспечивает автономный доступ по линии 411, чтобы наполнить информацию о высотах в справочнике данных, поддерживаемом на базовой станции. В одном примере программный модуль, называемый Вычислителем/Редактором (413) Справочника базовой станции, используют, чтобы вычислить оценку высоты местности для каждого из узлов сотовой связи, каталогизированных в справочнике данных, поддерживаемом на базовой станции. Оцененную высоту местности для каждого узла сотовой связи поддерживают на базовой станции, чтобы поставлять высотную поддержку на сервер 405 местоположения. Однако если используют подход автономного доступа, сервер местоположения не может получить лучшие оценки высоты подвижной станции, если более точные оценки позиции по горизонтали подвижной станции определяют на основании моментов времени прихода сигналов ССОМ, принятых на подвижной станции.

На фиг. 5 показан способ формирования Цифровых моделей рельефа в соответствии с одним вариантом осуществления настоящего изобретения. Область 501 из Цифровой модели рельефа покрыта множеством прямоугольных элементов модели (например, элементы 511, 512, 513 и 514 модели). Например, область 501 может быть США, или Кореей, или Японией. Когда для некоторого региона являются доступными Цифровые модели рельефа, имеющие различные разрешающие способности, используют иерархию элементов модели. Элемент модели на более низком уровне (слое) имеет более высокую разрешающую способность, и элемент модели на более высоком уровне имеет более низкую разрешающую способность. Элемент модели более высокого уровня имеет индикатор, который указывает, есть ли элементы модели более низкого уровня, которые моделируют тот же регион области. Например, элемент 511 модели и подэлементы 521, 522, 523, и 524 модели моделируют один и тот же регион области 501. Элемент 511 модели является элементом модели более высокого уровня; элементы 521, 522, 523, и 524 модели являются элементами модели более низкого уровня. Если высотная отметка местоположения не может быть определена на основании элемента модели более низкого уровня, то может быть использован элемент модели более высокого уровня, который содержит элемент модели более низкого уровня для того, чтобы определить с меньшей точностью высотную отметку местоположения.

Такая схема иерархической сетки дает возможность быстрого извлечения данных. Сначала идентифицируют область, которая содержит местоположение. Затем идентифицируют элемент модели высокого уровня, который содержит местоположение. Если есть элемент модели более низкого уровня, то осуществляют доступ к элементу модели более низкого уровня, который содержит местоположение. Элементы модели являются хэшированными по координатам в направлениях по широте и по долготе, так что элемент модели, содержащий заданное местоположение, может быть легко идентифицирован, исходя из координат в горизонтальной плоскости, соответствующих местоположению.

На фиг. 6 показана примерная схема для нумерации элементов модели. Такая схема может быть использована, чтобы отслеживать элементы модели более низкого уровня, находящиеся внутри элемента модели более высокого уровня, или элементов модели внутри области. Формируя прямоугольную сетку, элементы модели нумеруют по столбцам или по строкам, чтобы индексировать элементы модели так, чтобы индекс элемента модели мог быть легко определен из его индексов строки и столбца. Его индексы строки и столбца также могут быть легко определены из индекса элемента модели. В примере по фиг. 6 элементы модели пронумерованы от верхнего левого (Северо-западного) угла региона построчным способом. В предположении, что индексом столбца элемента модели является I, индексом строки элемента модели является J и количеством столбцов сетки является N, индекс элемента модели есть J*N+I. В предположении, что индексом элемента модели является М, индекс столбца I=mod(М,N), и индекс строки J=(M-I)/N. Поскольку индекс столбца и индекс строки элемента модели, который содержит заданное местоположение, могут быть вычислены из координат в горизонтальной плоскости, соответствующих местоположению, и позиции сетки, может быть легко идентифицирован элемент модели, который содержит местоположение.

На фиг. 7 показан пример профиля высотных отметок местности. Профиль формируют высотные отметки множества точек дискрет, находящиеся по линии развертки по широте (или по долготе) в элементе модели Цифровой модели рельефа. Интерполяция высотных отметок в точках дискрет обеспечивает высотную отметку для любой заданной точки на линии. Например, высота 703 представляет высотную отметку в точке Hn; и кривая 701 представляет модель рельефа для сегмента между точками Н₀ и H_n. Могут быть использованы различные схемы 1D-интерполяции (одномерной), чтобы формировать кривую 701.

На фиг. 8 показан способ определения высотной отметки местности для местоположения на основании Цифровой модели (DEM) рельефа в соответствии с одним вариантом осуществления настоящего изобретения. Элемент модели в DEM содержит множество профилей. Например, профили P1, P2, P3 и P4 по фиг. 8 содержатся внутри отдельного элемента модели DEM. Высотная отметка местоположения может быть определена из высотных отметок точек дискрет вблизи местоположения.

Например, высотная отметка точки X по фиг. 8 может быть определена на основании интерполяции, используя высотные отметки в точках дискрет X1, X2, X3 и X4. В примере по фиг. 8 используют билинейную интерполяцию, чтобы вычислить высотную отметку для точки между двумя профилями и между двумя линиями точек дискрет (которые находятся в направлении, не являющемся параллельным линиям профилей). В одном варианте осуществления настоящего изобретения используют схему биквадратной интерполяции для определения высотной отметки местоположения, используя высотные отметки точек дискрет вблизи местоположения в элементе модели Цифровой модели рельефа.

Данные профиля для элемента модели обычно сохраняют в определенной для области системе координат. Например, координаты по горизонтали могут быть представлены в системе WGS84, или в системе NAD83, или в системе, определенной для Японии или Кореи; и система координат в вертикальной плоскости, или система вертикальных координат, может быть системой Среднего уровня (MSL) моря (например, NAD88 или NAD27), или системой Высота над эллипсоидом (ВНЭ). Следует отметить, что различные системы ВНЭ (например, система WGS84, система WGS72, система Clarke 1866, или система Bessel 1841) могут использовать различные модели эллипсоида (например, различные большие полуоси оси и коэффициенты сжатия (сплющивания)). Могут быть использованы таблицы уровней приведения (уровненных поверхностей для начала отсчета высот) для определения преобразований от разнообразных различных систем координат к одной системе координат (например, координат, используемых ЭОМ, таких как система WGS84).

На фиг. 9 показана Обслуживающая подсистема поддержки высотных отметок в соответствии с одним вариантом осуществления настоящего изобретения. Обслуживающая подсистема 901 поддержки высотных отметок содержит блок интерполятора, или интерполятор 910, геодезический компьютер 920, блок 930 управления цифровой моделью рельефа и блок управления доступом, или администратор 940 доступа к данным цифровой модели рельефа.

Интерполятор 910 содержит 1D-интерполятор 911 (в одном измерении) и 2D-интерполятор 913 (в двух измерениях), чтобы обеспечить интерполяцию 1D и 2D. В одном варианте осуществления настоящего изобретения 2D-интерполятор может исполнять билинейную интерполяцию, которую использует NGS (Национальная геодезическая служба) и NIMA (Национальное агентство картографии США) для интерполяции различных сеток данных. В другом варианте осуществления настоящего изобретения 2D-интерполятор также может выполнять биквадратную интерполяцию, чтобы вычислять высотную отметку местоположения, исходя из высотных отметок точек дискрет вблизи местоположения.

Геодезический компьютер 920 содержит блок 921 управления преобразованиями уровней приведения и картографический проектор 923. Геодезический компьютер 920 используют, чтобы исполнить преобразование координат местоположения, осуществляемое между одной системой координат (например, системой, используемой сервером местоположения) и другой системой координат (например, системой, используемой элемент