Способ и система для определения местоположения с использованием множества выбранных начальных оценок местоположения
Изобретение относится к определению местоположения модуля, работающего в сети связи, включающего в себя множество модулей, и в частности, к использованию множества начальных оценок местоположения, основанных на установленной области возможного местоположения для каждого из модулей, местонахождение которых определяется. Техническим результатом является улучшение точности оценки местоположения и снижение ошибок ложного решения. Технический результат достигается тем, что предложен способ определения местоположения для каждого из множества модулей, которое выбрано из одного из нескольких наборов местоположений, каждое из которых оценивается на основе различных начальных оценок местоположения. Выбранный набор местоположений включает в себя набор, который имеет минимальное значение ошибки, причем значение ошибки основано на совокупном значении разностей между расстоянием, определенным из предполагаемых местоположений, и измеренным расстоянием. При использовании различных наборов начальных оценок местоположения имеется высокая вероятность того, что, по меньшей мере, один из наборов начальных оценок местоположения позволит избежать любых локальных минимумов и обеспечит выполнение более точной оценки местоположения модуля. 2 н. и 21 з.п. ф-лы, 10 ил.
Настоящее изобретение относится к определению местоположения модуля, работающего в сети, включающего в себя множество модулей, более конкретно, к использованию множества начальных оценок местоположения, основанных на установленной области возможного местоположения для каждого из модулей, местонахождение которых определяется.
УРОВЕНЬ ТЕХНИКИ
Имеются различные случаи, когда может быть желательно проследить и/или оценить местоположение отдельных модулей в пределах сети. По меньшей мере, в некоторых из этих случаев некоторые из традиционных методов, таких как основанные на глобальной системе позиционирования (GPS), могут столкнуться с трудностями. Один такой пример соответствует ситуации, когда отслеживаемые модули расположены внутри здания. Это объясняется трудностями проникновения сигналов системы GPS через стены здания и/или пересечения других преград. В некоторых из этих же или в других случаях может иметь место недостаточное количество измерений расстояний относительно одного или более опорных модулей, местоположения которых либо известны, либо определены, чтобы обеспечить возможность определения позиции отдельного модуля методом триангуляции.
По меньшей мере, в некоторых из этих случаев можно использовать информацию измеренного расстояния между, по меньшей мере, некоторыми из модулей для определения оценки местоположения для одного или более модулей. По меньшей мере, в одном таком случае значение ошибки, связанное с оценкой, включающее в себя по меньшей мере, в одном случае сумму квадратов разностей между измеренным расстоянием и расстоянием, соответствующим вычисленному пространству между парой модулей, и ассоциированное с набором оценок местоположений, минимизируется посредством итерационного процесса минимизации. По меньшей мере, один такой пример соответствующей системы и способа описан в патенте США № 6473038 на имя Patwari и др., раскрытие которого включено здесь посредством ссылки. Однако в некоторых случаях в зависимости от того, как выбрана начальная оценка местоположения, итерационный подход, который минимизирует значение ошибки, может дать ложный результат, соответствующий локальному минимуму, испытывать затруднение в сходимости к более точному решению. Следовательно, было бы полезно разработать подход, который более вероятно определяет решение и который позволяет избежать ложного решения, соответствующего локальныму минимуму.
Авторы данного изобретения исходили из того, что подход к выбору множества различных наборов начальных оценок местоположения, каждый из которых используется для итерационной оценки местоположения для каждого из множества модулей в сети, был бы полезен при достижении решения, которое позволяет более надежно избежать любых локальных минимумов. Из множества оценок местоположения, которые определены, выбирается набор решений, имеющий наименьшее значение ошибки, и используется в качестве оценки местоположения для множества модулей. Авторы данного изобретения также исходили из того, что было бы полезно выбирать различные наборы начальных оценок местоположения из области возможного местоположения, определенной для каждого из модулей. Таким образом, можно обеспечить систему и способ с улучшенной точностью оценки местоположения.
СУЩНОСТЬ ИЗОБРЕТЕНИЯ
Настоящее изобретение обеспечивает способ определения местоположения множества модулей, причем каждый модуль соединен средствами связи, по меньшей мере, с некоторыми другими из множества модулей, и, по меньшей мере, некоторые из множества модулей находятся на расстоянии дальности связи с одним или более опорных модулей, местоположения которых, по меньшей мере, либо определены, либо известны. Способ включает в себя измерение расстояния между каждым из модулей и любым опорным модулем в пределах дальности связи между ними. Область возможного местоположения затем устанавливается для каждого из модулей, включая множество возможных начальных оценок местоположения.
Затем выбирается начальная оценка местоположения для каждого из модулей, местоположение которых не известно, из области, ближайшей к области возможного местоположения, и оценивается местоположение для каждого из модулей, которое минимизирует значение ошибки, на основе разности между измеренными значениями расстояния и расстоянием, вычисленным из предполагаемых значений местоположения. Выбор начальных оценок местоположения с использованием другого набора начальных оценок местоположения для каждого из модулей из множества возможных начальных оценок местоположения и оценки местоположения для каждого из модулей, которая минимизирует значение ошибки, затем повторяется, по меньшей мере, один раз. Затем выбирается набор оценок местоположения из повторных оценок, имеющих наименьшее минимизированное значение ошибки.
По меньшей мере, в одном варианте воплощения выбор начальной оценки местоположения для каждого из модулей включает в себя случайный выбор местоположения из множества возможных начальных местоположений из установленной области возможного местоположения.
По меньшей мере, в еще одном варианте воплощения выбор начальной оценки местоположения для каждого из модулей включает в себя последовательный выбор местоположения из подмножества множества возможных начальных местоположений, связанных с установленной областью возможного местоположения, которые расположены по предопределенному образцу по области возможного местоположения.
В еще одном варианте воплощения способ также включает в себя выполнение определения относительно модулей, имеющих связи с достаточным количеством опорных модулей, чтобы определить местоположение посредством триангуляции, и затем определение путем триангуляции местоположения для каждого из идентифицированных модулей и идентификацию триангулированных модулей в качестве опорных модулей во время последующей обработки, в которой триангулированное местоположение остается действительным.
Данное изобретение также обеспечивает систему для определения местоположения для каждого из множества модулей в сети с множеством участков ретрансляции, где каждый модуль соединен средствами связи, по меньшей мере, с некоторыми из другого множества модулей, причем, по меньшей мере, некоторые из множества модулей находятся на расстоянии дальности связи от одного или более опорных модулей, местоположения которых, по меньшей мере, либо определены, либо известны. Система содержит приемопередатчик, который предназначен для приема информации о возможности соединения и расстоянии для множества модулей и опорных модулей на расстоянии дальности связи между ними, и процессор, связанный с приемопередатчиком.
Процессор содержит область памяти для хранения информации о возможности соединения, дальности связи и множества наборов оценок местоположения и соответствующих минимизированных значений ошибки. Процессор также содержит вычислительный модуль, предназначенный для определения областей возможного местоположения для каждого из модулей и оценки местоположения для каждого из модулей, которое минимизирует значение ошибки, на основе каждого набора начальных оценок местоположения. Кроме того, процессор также содержит один или более модулей выбора для последовательного выбора множества различных наборов начальных оценок местоположения, связанных с областями возможного местоположения для каждого из модулей, и выбора набора предполагаемых местоположений, который связан с наименьшим минимизированным значением ошибки.
Эти и другие особенности и преимущества данного изобретения очевидны из последующего описания одного или более предпочтительных вариантов воплощения данного изобретения со ссылкой на иллюстрирующие чертежи.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Фиг.1 - частичная пространственная обзорная диаграмма, показывающая иллюстративные пространственные отношения между соседними членами, по меньшей мере, части сети связи в соответствии, по меньшей мере, с одним вариантом воплощения данного изобретения;
Фиг.2 - частичный иллюстративный граф, показывающий значения ошибки, связанные с различными оценками местоположения одного или более модулей;
Фиг.3 - частичный пространственный вид, показывающий перекрывающиеся зоны связи для множества модулей, осуществляющие связь с общим модулем, и приближенное местоположение, на основе иллюстративного варианта воплощения, включая набор расстояний между несколькими модулями и общим модулем;
Фиг.4 - частичный пространственный вид, показывающий перекрывающиеся зоны связи для множества модулей, образующие область возможного местоположения для модуля, осуществляющего связь с множеством модулей, и набор возможных начальных оценок местоположения;
Фиг.5 - частичный пространственный вид, показывающий перекрывающиеся зоны связи для множества модулей, образующие область возможного местоположения для модуля, осуществляющего связь с множеством модулей, и набор возможных начальных оценок местоположения;
Фиг.6 - частичный пространственный вид, показывающий область возможного местоположения для модуля на основе известного предшествующего местоположения, скорости перемещения и времени, прошедшего с момента, когда модуль находился в последнем известном местоположении; и
Фиг.7 - частичный пространственный вид, показывающий область возможного местоположения для модуля на основе известного предшествующего местоположения и оценки движения;
Фиг.8 - блок-схема, показывающая систему для определения местоположения для каждого из множества модулей в сети с множеством участков ретрансляции в соответствии, по меньшей мере, с одним вариантом воплощения данного изобретения;
Фиг.9 - блок-схема, показывающая способ определения местоположения множества модулей в соответствии, по меньшей мере, с одним вариантом воплощения данного изобретения; и
Фиг.10 - более конкретная блок-схема, показывающая определение и триангуляцию модулей, имеющих достаточное количество связей как часть или в дополнение к этапу измерения информации расстояния в соответствии, по меньшей мере, с одним вариантом воплощения по фиг.9.
ПОДРОБНОЕ ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНОГО ВАРИАНТА ВОПЛОЩЕНИЯ
Хотя данное изобретение может быть реализовано в различных вариантах воплощения, на чертежах показаны и в дальнейшем описаны предпочтительные в настоящее время варианты воплощения. При этом следует иметь в виду, что данное раскрытие следует рассматривать как пояснение данного изобретения на примерах, и оно не предназначено для ограничения изобретения конкретными иллюстрированными вариантами воплощения.
Фиг.1 показывает частичную пространственную обзорную диаграмму, представляющую иллюстративные пространственные отношения между соседними членами, по меньшей мере, части сети 10 связи в соответствии, по меньшей мере, с одним вариантом воплощения данного изобретения. Сеть 10 содержит опорные модули 12, которые представлены как треугольники, и местоположения которых известны или могут быть определены, и множество «слепых» модулей 14, которые представлены как круги. «Слепые» модули 14 соответствуют модулям, местоположения которых должны быть оценены. По меньшей мере, в иллюстрированном варианте воплощения сеть 10 является сетью с множеством участков ретрансляции, что соответствует сетям, в которых некоторые из пар модулей не могут взаимодействовать непосредственно и/или должны взаимодействовать через другой модуль в сети 10. Модули, которые могут взаимодействовать непосредственно друг с другом, показаны линией 16, проходящей между модулями. Одна из указанных линий показана на чертежах во взаимосвязи с соответствующей ссылочной позицией.
Каждый модуль, как правило, содержит приемопередатчик и соответствующую антенну, которые обеспечивают беспроводную связь между другими модулями в пределах дальности связи. Посредством передач между соседними модулями определяется оценка расстояния на основе характеристик и/или временных характеристик принятого сигнала. По меньшей мере, в одном варианте воплощения для определения измеренного значения расстояния используются одно или более из следующих измерений: индикация уровня полученного сигнала, измерение времени прихода, измерение разности во времени прихода и/или измерение угла прихода. Например, можно измерить уровень принятого сигнала и, зная уровень сигнала, когда он был передан, можно вычислить оценку расстояния на основе модели, которая прогнозирует ослабление уровня сигнала как функцию расстояния. В качестве другого примера можно определить время распространения сигнала, переданного между парой модулей, и аппроксимировать расстояние между модулями на основе аппроксимации скорости распространения сигнала и определенного времени распространения. В некоторых случаях может использоваться передача в прямом и обратном направлениях, чтобы определить задержку распространения. Специалисту в данной области техники очевидно, что существуют дополнительные методы для аппроксимации расстояния между модулями на основе характеристик принятого сигнала и/или временных соотношений, связанных с принятым сигналом, что также может быть использовано без отступления от идеи данного изобретения.
Как только определено расстояние между соседними модулями, в том числе ближайшими опорными модулями, может быть выбрано начальное местоположение для каждого из модулей, не являющихся опорными. Затем используется итерационный процесс для обновления начальных и последующих оценок местоположения до тех пор, пока значение ошибки, связанное с разностью между расстоянием, определенным на основе выбранных координат, и расстоянием, основанным на измеренном расстоянии, больше не уменьшается, а в идеальном случае минимизировано. Однако при использовании некоторых методов минимизации ошибки можно попасть в ловушку, то есть получить ложный результат, связанный с локальным минимумом. В некоторых из этих случаев отклонения от локального минимума проявляются в увеличении значения ошибки и в результате смещают значение обратно к локальному минимуму. Один такой пример локального минимума, показанный для двумерного случая, проиллюстрирован на фиг.2.
Более конкретно фиг.2 показывает частичный граф 20 иллюстративных значений ошибки, связанных с различными оценками местоположения одного или более модулей. Часто граф, иллюстрирующий значения ошибки, будет более чем двумерным. Однако локальные минимумы могут подобным образом возникнуть в случаях, в которых имеется большее количество измерений. В проиллюстрированном примере кривая содержит минимальное значение 22 и локальный минимум 24. Локальные минимумы могут быть созданы точкой 26 перегиба, гребнем или неровностью, которая расположена между локальным минимумом 24 и действительным минимумом 22, и которая может сместить итерационное решение в сторону от действительного минимума 22 в зависимости от того, на какой стороне от точки 26 перегиба находилась отправная точка. Поскольку отправная точка может привести к большому различию в том, достигается ли сходимость к локальному минимуму 24 или действительному минимуму 22, выбор начальных значений для определяемых значений может быть важным.
Исходя из того, что начальные оценки могут повлиять на то, сходится ли решение к локальному минимуму 24 или оно сходится к действительному минимуму 22, был разработан подход к выбору начальных оценок, который стремится увеличить возможность идентифицировать решение, которое будет сходиться к действительному минимуму 22. Вообще в соответствии, по меньшей мере, с одним аспектом данного изобретения используются множество различных наборов начальных оценок местоположения.
По меньшей мере, в некоторых случаях возможное местоположение модуля может быть определено областью, которая может быть определена. Фиг.3 иллюстрирует область 30 возможного местоположения для модуля, местоположение которого должно быть определено. Более конкретно, на фиг.3 представлен частичный пространственный вид, показывающий перекрывающиеся зоны связи для нескольких модулей, которые осуществляют связь с модулем 32, местоположение которого должно быть определено на основе набора предопределенных дальностей передачи множества модулей и модуля 32, местоположение которого должно быть определено. Например, если модуль 32, местоположение которого должно быть определено, может принимать передачи от трех различных модулей, то модуль 32, местоположение которого должно быть определено, вероятно расположен в области 30, где перекрываются зоны передачи, ограниченные дугами 34A-C, для каждого из трех различных модулей. Это мало чем отличается от триангуляции, однако вместо этого обеспечивается схождение к приблизительной позиции на основе определенного расстояния между каждым из модулей и модулем 32, местоположение которого должно быть определено. Область 30 определена оцениванием предопределенной дальности 34 передачи для каждого из модулей. Пример более определенного местоположения, как потенциально определенного посредством триангуляции, проиллюстрирован как сходимость трех приближенных расстояний 36A-C между модулем 32, местоположение которого должно быть определено, и другими модулями.
В случае, когда начальное местоположение является неопределенным для одного из модулей, имеющих оцененную предопределенную дальность передачи, которая используется для содействия определению области 30 возможного местоположения, предопределенная дальность 34 передачи может быть увеличена на величину, соответствующую величине неопределенности, что будет служить дополнительному расширению области 30 возможного местоположения.
Как только определена область, в которой, вероятно, должен находиться модуль, могут быть выбраны начальные оценки местоположения, которые связаны с этой областью. Такой выбор начальных оценок местоположения может содержать любой один или более из нескольких различных подходов без отступления от идеи данной заявки, однако, по меньшей мере, в одном аспекте данной заявки выбирается множество различных наборов начальных оценок местоположения. В некоторых вариантах воплощения начальные оценки местоположения могут быть выбраны случайным образом. В других вариантах воплощения начальные оценки местоположения могут быть упорядочены, в основном, с равномерными промежутками. В других вариантах воплощения начальные оценки местоположения могут быть выбраны на основе предопределенного образца распределения. Кроме того, в некоторых случаях начальные оценки местоположения будут ограничены определенной областью возможного местоположения, в то время как в других случаях некоторые из начальных оценок местоположения могут отклоняться за пределы области возможного местоположения.
Фиг.4 иллюстрирует частичный пространственный вид с выделением области 40 возможного местоположения, ограниченной парой дуг 42A и 42B, которые могут соответствовать паре перекрывающихся зон связи 44A и 44B для пары модулей (не показаны), осуществляющих связь с модулем, местоположение которого должно быть определено (не показан). Дополнительно изображен иллюстративный набор 46 возможных начальных оценок местоположения для модуля, местоположение которого должно быть определено, показанный как множество точек, из которых лишь некоторые явно связаны с соответствующей ссылочной позицией. В иллюстрированном варианте воплощения начальные оценки 46 местоположения в общем равномерно распределены по области 40 возможного местоположения. По меньшей мере, в нескольких случаях начальные оценки 46 местоположения выходят за пределы области 40 возможного местоположения. В некоторых случаях может быть желательно корректировать любые местоположения, которые выходят за пределы области возможного местоположения таким образом, чтобы они были внутри области. Фактический промежуток может зависеть от количества оценок 46 местоположения, которое будет использоваться.
Фиг.5 показывает частичный пространственный вид с выделением области 50 возможного местоположения, ограниченной тремя дугами 52A-C. Аналогично фиг.4 фиг.5 дополнительно изображает иллюстративный набор 54 возможных начальных оценок местоположения. Однако, в отличие от фиг.4, иллюстративный набор 54 возможных начальных оценок местоположения расположен с промежутками по предопределенному или заранее указанному образцу. В иллюстрированном варианте воплощения предопределенный образец центрирован относительно местоположения 56, которое может соответствовать начальной оценке с наилучшим предположением на основе любых предопределенных критериев, которые могут быть либо связанными, либо несвязанными с описываемыми здесь концепциями. Один возможный вариант воплощения может расположить предопределенный образец на основе предварительно определенной позиции. В конкретном иллюстрированном образце плотность расположения начальных оценок 54 местоположения больше по мере приближения к начальной оценке 56 местоположения с наилучшим предположением. Специалисту в данной области техники должно быть понятно, что и другие предопределенные образцы могут использоваться альтернативно без отступления от идеи данного изобретения.
В еще одном альтернативном варианте область возможного местоположения может принимать во внимание особенности окружающей среды, которые могут ограничивать или препятствовать определению местоположения модуля в некоторой области и/или затруднять перемещение или вход модуля в другие области. Фиг.6 показывает частичный пространственный вид области 60 возможного местоположения для модуля на основе известного предшествующего местоположения 62. В иллюстрированном варианте воплощения возможное местоположение также основывается на предполагаемой или возможной скорости перемещения и времени, прошедшем с момента, когда модуль находился в последнем известном местоположении 62. Пара стен 64 и 66, которые определяют проход 68 и, соответственно, ограничивают движение модуля, используется для того, чтобы более точно определить область 60 возможного местоположения.
В еще одном альтернативном варианте может быть определена область возможного местоположения, которая подобным образом принимает во внимание предварительно определенное местоположение и информацию инерциальной навигации, полученную от модуля. Например, модуль может содержать шагомер, который может отслеживать количество шагов, которые проходит человек, несущий модуль, или одометр, который может отслеживать расстояние, проходимое колесом. Также модуль может содержать компас, который мог бы обеспечивать информацию направления перемещения относительно измеренного расстояния перемещения. В качестве альтернативы модуль может содержать один или более гироскопов, которые могут определять движение и/или ускорение в определенном направлении.
В некоторых случаях предварительно определенное местоположение может являться местоположением, основанным на альтернативном методе определения местоположения, который может быть доступен в области, из которой отслеживаемый модуль выходит, но который может быть недоступным в новой области, в которую отслеживаемый модуль входит. Одним таким примером может являться глобальная система позиционирования, в которой модули триангулируются относительно сети спутников или базовых станций, причем это метод определения местоположения может оказаться недоступным после того, как модуль входит в здание. Может существовать некоторая степень определенности относительно предварительно определенного местоположения, на основе которого затем может быть определена и/или оценена область возможного местоположения
Фиг.7 показывает частичный пространственный вид области 70 возможного местоположения для модуля, определяемой на основе известного предшествующего местоположения 72 и оценки 74 движения, которая, как отмечено выше, может быть реализована на оценке инерциальной навигации некоторого типа. Оценка 74 движения может представлять собой один вектор расстояния и направления и может являться усредненным или интегрированным значением. В качестве альтернативы, оценка 74 движения может содержать множество различных векторов или компонентов 74A-C и соответствующее множество связанных направлений. Фиг.7 также показывает возможные совокупные эффекты неопределенности в оценке инерциальной навигации и то, каким образом они могут привести к области 70 возможного местоположения, из которой могут быть взяты начальные оценки.
Фиг.8 показывает блок-схему системы 100 для определения местоположения для каждого из множества модулей в сети с множеством участков ретрансляции в соответствии, по меньшей мере, с одним вариантом воплощения данного изобретения. Система 100 для определения местоположения может быть реализована в одном или более модулей, местоположение которых должно быть определено, или, в качестве альтернативы, может находиться в другом модуле, который, по меньшей мере, соединен средствами связи с модулями, местоположение которых должно быть определено, одним или более участков ретрансляции сети, таком как опорный модуль.
Система 100 содержит приемопередатчик 102, соединенный с антенной 104 для обеспечения связи с другими модулями, с помощью которых определяется измеренное расстояние каждым из модулей и может быть получена информация для определения области возможного местоположения. Приемопередатчик 102 может быть совместимым со многими видами связи, включая связь с использованием беспроводного приемопередатчика мобильного телефона, беспроводного приемопередатчика беспроводного телефона, беспроводного соединения с локальной сетью LAN, беспроводного приемопередатчика малого радиуса действия, такого как приемопередатчик Bluetooth, приемопередатчика инфракрасной связи или другого подобного устройства связи. Специалисту в данной области техники должно быть понятно, что могут использоваться и другие виды связи и/или их комбинации.
Система 100 также содержит процессор 106, соединенный с приемопередатчиком 102. Процессор 106 содержит область 108 памяти для приема и хранения информации о возможности связи и расстоянии и для сохранения одной или более оценок местоположения и соответствующих значений ошибки, связанных с оценками 110 местоположения. Область 108 памяти может также содержать один или более наборов предварительно записанных в память команд 112.
Процессор 106 дополнительно содержит вычислительный модуль 114, который предназначен для определения областей возможного местоположения для каждого из модулей и определения оценки местоположения для каждого из модулей на основе набора начальных оценок местоположения, который минимизирует значение ошибки. Процессор 106 также содержит один или более модулей 116 выбора. По меньшей мере, в одном варианте воплощения процессор содержит модуль 118 выбора для выбора начальных оценок местоположения и модуль 120 выбора для выбора набора минимизированных ошибок. В некоторых вариантах воплощения вычислительный модуль 114 и один или более модулей 116 выбора будут реализованы как, по меньшей мере, часть одного или более наборов предварительно записанных в память команд 112.
По меньшей мере, в одном варианте воплощения процессор 106 может быть реализован в форме специализированного компьютера или компьютера общего назначения, который содержит один или более микропроцессоров для выполнения одного или более наборов предварительно записанных в память команд 112. Процессор может также содержать один или более типов запоминающих устройств и/или памяти, некоторые из них могут быть связаны с микропроцессором или встроены в микропроцессор для хранения данных программы и одного или более наборов предварительно записанных в память команд. Примеры различных типов памяти включают в себя один или более видов энергозависимой и/или энергонезависимой памяти, в том числе традиционное постоянное запоминающее устройство (ПЗУ), стираемое программируемое постоянное запоминающее устройство (СППЗУ), оперативное запоминающее устройство (ОЗУ) или электрически стираемое программируемое постоянное запоминающее устройство (ЭСППЗУ). Также различные типы памяти могут включать в себя вспомогательные запоминающие устройства, такие как стационарные или сменные носители, в том числе магнитный диск или накопители на оптических дисководах.
Фиг.9 показывает блок-схему способа 200 для определения местоположения множества модулей в соответствии, по меньшей мере, с одним вариантом воплощения данного изобретения. Способ 200 включает в себя измерение (202) информации расстояния между каждым из модулей и любыми опорными модулями в пределах расстояния дальности связи. Как отмечено выше, это может быть реализовано, по меньшей мере, несколькими различными способами. По меньшей мере, несколько примеров включают в себя использование индикации уровня принятого сигнала, измерения времени прихода и измерения разности времени прихода. Затем определяется (204) область возможного местоположения для каждого из модулей. Затем выбирается (206) начальное местоположение для каждого из модулей на основе области возможного местоположения, определенной для каждого из модулей. Затем выполняется (208) оценка местоположения для каждого из модулей, которая минимизирует значение ошибки.
По меньшей мере, в некоторых случаях поддерживается запись определенных оценок местоположения и соответствующего минимизированного значения ошибки. Затем выполняется определение (210) того, было ли вычислено желательное количество оценок местоположения. По меньшей мере, в некоторых случаях желательное количество оценок местоположения может быть фиксированным предопределенным числом. Однако в других случаях желательное количество оценок местоположения может быть функцией других факторов. Например, желательное количество оценок местоположения может изменяться в зависимости от размера одной или более областей возможного местоположения для каждого из модулей, местоположение которых должно быть определено.
Также желательное количество оценок местоположения, которое реализуется или превышается, может быть функцией минимальных значений ошибки, которые были определены. Например, желательное количество оценок местоположения может быть определено так, чтобы оно достигалось, если найдено значение ошибки ниже предопределенного порога. Это может альтернативно быть представлено как дальнейшее условие, которое потенциально прерывает цикл и заставляет последовательность способа выйти из цикла до достижения альтернативно определенного предопределенного количества вычислений оценки местоположения. Также помимо этого можно указать, что желательное количество вычисляемых оценок местоположения достигнуто, если одновременно превышено уменьшенное предопределенное количество и найдено значение ошибки, которое меньше, чем предопределенный порог. Специалисту в данной области техники должно быть понятно, что возможны и другие альтернативы без отступления от идеи изобретения.
В любом случае, пока не вычислено желательное количество оценок местоположения, выбирается (206) новый набор начальных оценок местоположения и используется для определения (208) оценки местоположения для каждого из модулей, и эти этапы последовательно повторяются. После того как желательное количество оценок местоположения было определено, и/или вычисления оценок местоположения были прерваны иным образом, выбирается (212) набор оценок местоположения с наименьшей ошибкой.
По меньшей мере, в одном варианте воплощения оценка ошибки является функцией суммы квадрата разностей между измеренным расстоянием и вычисленным расстоянием между предполагаемыми местоположениями. Во время каждой оценки местоположения используется итерационный подход, который стремится минимизировать значение ошибки.
Как отмечено выше в связи, по меньшей мере, с фиг.4-5, существуют, по меньшей мере, несколько возможностей для выбора начальной оценки местоположения, в том числе случайный выбор начальной оценки, ближайшей к определенной области возможного местоположения, последовательный выбор обособленно расположенных начальных оценок местоположения относительно области возможного местоположения. Когда начальные оценки местоположения последовательно выбираются из обособленно расположенных начальных оценок местоположения, оценки местоположения могут располагаться, в принципе, на равных расстояниях или альтернативно они могут быть упорядочены по предопределенному образцу с применяющейся плотностью размещения относительно области возможного местоположения. В некоторых случаях начальные оценки местоположения будут иметь наибольшие плотности ближе к области, которая согласуется с местоположением для наилучшего предположения.
В другом варианте воплощения, как показано на фиг.10, количество модулей, местоположение которых должно быть определено, может быть минимизировано путем определения местоположения некоторых из модулей посредством альтернативных средства определения местоположения, где это возможно. Например, можно определить местоположение одного или более модулей посредством триангуляции 224, если существует достаточное количество оценок расстояния между модулем, местоположение которого должно быть определено, и достаточным количеством опорных модулей. Также любой модуль, местоположение которого определено посредством триангуляции, может, в свою очередь, быть классифицирован или принят за опорный модуль 226, по меньшей мере, в течение времени, когда триангулированное местоположение остается действительным. В свою очередь, это может позволить другим модулям более точно определить местоположение посредством альтернативных средств определения местоположения, таких как триангуляция. Этот процесс может повторяться, пока никакие дополнительные модули не смогут быть локализованы этим способом 228.
Также возможно, что как часть процесса определения местоположения в целях триангуляции или в связи со способом определения местоположения множества модулей, как предусмотрено на фиг.9, количество коммуникационных связей и соответствующих измерений расстояний может быть увеличено (222) за счет увеличения мощности и, соответственно, дальности любой беспроводной передачи между модулями.
Вообще описанный способ 200 и система 100 могут использоваться в связи с определением местоположения модулей во множестве сред. По меньшей мере, один такой пример включает в себя определение местоположения устройств, таких как один или более мобильных телефонов или других устройств, расположенных в пределах сети. Дополнительно система 100 может использоваться для отслеживания местоположения предметов, хранимых на складе.
Другие примеры включают в себя реализацию модулей, местоположение которых должно быть определено, в качестве части оборудования для одной или более групп людей, работающих во взаимодействии в пределах данной области или среды. Один такой пример включает в себя персонал служб по чрезвычайным ситуациям. В этом случае модули, местоположение которых должно быть определено, могут быть встроены или расположены совместно с одним или более пожарным шлемом, курткой или другой частью оборудования. Специалисту в данной области техники должно быть понятно, что данный способ и система определения местоположения множества модулей также будут в равной степени применимы к другим средам.
Хотя были иллюстрированы и описаны предпочтительные варианты воплощения изобретения, следует понимать, что изобретение не ограничено ими. Многочисленные модификации, изменения, разновидности, замены и эквиваленты могут быть предложены специалистами в данной области техники без отступления от сущности и объема настоящего изобретения, как определено приложенной формулой изобретения.
1. Способ определения местоположения множества модулей связи, причем каждый модуль связи соединен средствами связи, по меньшей мере, с некоторыми другими из множества модулей связи, и, по меньшей мере, некоторые из множества модулей связи находятся на расстоянии дальности связи с одним или более опорными модулями связи, местоположения которых, по меньшей мере, либо определены, либо известны, при этом указанный способ содержит
измерение информации расстояния между каждым из модулей связи и любыми опорными модулями связи в пределах дальности связи между ними;
определение области возможного местоположения для каждого из модулей связи, включающей в себя множество возможных начальных оценок местоположения;
выбор начальной оценки местоположения для каждого из модулей связи, местоположение которых не известно, из области, соответствующей области возможного местоположения;
выполнение оценки местоположения для каждого из модулей связи, которая минимизирует значение ошибки, на основе разности между измеренными значениями расстояния и расстоянием, вычисленным из оцененных значений местоположения;
повторение, по меньшей мере, один раз выбора начальных оценок местоположения с использованием различных наборов начальных оценок местоположения для каждого из модулей связи из множества возможных начальных оценок местоположения и оценки местоположения для каждого из модулей связи, которая минимизирует значение ошибки; и
выбор набора оценок местоположения из повторных оценок, имеющих наименьшее минимизированное значение ошибки.
2. Способ по п.1, в котором измерение информации расстояния между каждым из модулей связи и любыми опорными модулями в пределах дальности связи между ними включает в себя, по меньшей мере, одно из измерения индикации уровня принятого сигнала, угла прихода, времени прихода и разности времен прихода для сигналов, переданных одним или более из модулей связи.
3. Способ по п.1, в котором определение области возможного местоположения для каждого из модулей связи включает в себя определение перекрывающейся области на основе дальности связи и известных или оцененных местоположений других модулей связи, связанных с возможностью связи с модулем связи, для которого определяется область возможного местоположения.
4. Способ по п.1, в котором определение области возможного местоположения для каждого из модулей связи включает в себя определение известного предыдущего местоположения и оценку величины возможного отклонения в течение интервала времени, которое прошло с момента, когда модуль связи находился в предыдущем известном местоположении.
5. Способ по п.4, в котором возможное отклонение основано на предполагаемой скорости перемещения и интервале времени с момента, когда модуль связи находился в предыдущем известном местоположении.
6. Способ по п.4, в котором возможное отклонение основано на оценке инерциальной навигации в течение времени, после момента предыдущего известного местоположения.
7. Способ по п.1, в котором выбор начальной оценки местоположения для каждого из модулей связи включает в себя случайный выбор местоположения из множества возможных начальных местоположений из установленной области возможного местоположения.
8. Способ по п.1, в котором выбор начальной оценки местоположения для каждого из модулей связи включает в себя последовательный выбор местоположения из подмножества множества возможных начальных местоположений из установленной области возможного местоположения, которые упорядочены по предопределенному образцу относительно области возможного местоположения.
9. Способ по п.8, в котором предопределенный образец включает в себя местоположения, которые, по существу, разнесены равномерно.
10. Способ по п.9, в котором расстояние разнесения основано на размере области возможного местоположения и предопределенном количестве повторных итераций оценок местоположения.
11. Способ по п.1, в котором минимизация ошибки включает в себя минимизацию суммы квадрата разностей между расстоянием, основанным на оцененном местоположении, и измеренным расстоянием.
12. Способ по п.1, в котором выполнение оценки местоположения для каждого из модулей связи включает в себя, после выбора начальной оценки местоположения для каждого из модулей связи, итерационную оценку обновленного местоположения для каждого из модулей связи, по меньшей мере, до тех пор, пока значение ошибки не перестанет уменьшаться.
13. Способ по п.1, дополнительно содержащий увеличение дальности связи, по меньшей мере, для некоторых из множества модулей связи.
14. Способ по п.1, дополнительно содержащий определение модулей связи, имеющих связи с достаточным количеством опорных модулей, чтобы определить местоположение посредством триангуляции, определение местоположения посредством триангуляции для каждого из идентифицированных модулей и идентификацию триангулированных модулей в качестве опорных модулей при последующей обработке, в которой триангулированное местоположение остается действительным.
15. Способ по п.14, в котором, если любые из модулей связи были вновь триангулированы и идентифицированы в качестве опорных модулей связи, повторение попытки триангулировать другие модули и затем идентифицировать их в качестве опорных модулей связи, до тех пор, пока никакие другие модули связи не смогут быть триангулированы.
16. Система для определения местоположения для каждого из множества модулей связи в сети с множеством участков трансляции, причем каждый модуль связи связан с возможностью связи с, по меньшей мере, некоторыми другими из множества модулей связи, причем, по меньшей мере, некоторые из множества модулей связи находятся на расстоянии дальности связи с одним или более опорными модулями связи, местоположение которых, по меньшей мере, либо определено, либо известно, при этом упомянутая система содержит:
приемопередатчик для приема информации о возможности связи и расстоянии для множества модулей связи и опорных модулей связи на расстоянии дальности связи между ними; и
процессор, соединенный с приемопередатчиком, причем процессор содержит область памяти для хранения информации о возможности связи, дальности связи и множества наборов оценок местоположения и соответствующих минимизированных значений ошибки,
вычислительный модуль, предназначенный для определения областей возможного местоположения для каждого из модулей связи и оценки местоположения для каждого из модулей связи, которая минимизирует значение ошибки, на основе каждого набора начальных оценок местоположения, и
один или более модулей выбора для последовательного выбора множества различных наборов начальных оценок местоположения, соответствующих областям возможного местоположения для каждого из модулей связи, и выбора набора оцененных местоположений, которые связаны с наименьшим минимизированным значением ошибки.
17. Система по п.16, в которой, по меньшей мере, один из вычислительных модулей и один или более модулей выбора содержат один или более наборов предварительно записанных в память команд.
18. Система по п.17, в которой один или более наборов предварительно записанных в память команд сохранены в области памяти.
19. Система по п.16, в которой один или более модулей выбора предназначены для случайного выбора начальной оценки местоположения из соответствующей области возможного местоположения для каждого из модулей связи.
20. Система по п.16, в которой один или более модулей выбора предназначены для последовательного выбора начальной оценки местоположения из соответствующей области возможного местоположения для каждого из модулей связи, которые упорядочены по предопределенному образцу.
21. Система по п.16, в которой система для определения местоположения встроена как часть одного из модулей связи, местоположение которого должно быть определено.
22. Система по п.16, в которой, по меньшей мере, некоторые из модулей связи являются устройствами мобильной связи.
23. Система по п.22, в которой, по меньшей мере, некоторые из устройств мобильной связи являются сотовыми радиотелефонами.
