Способы определения приближенного местоположения устройства на основании внешних сигналов

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

 

Ссылка на родственную заявку

По настоящей заявке испрашивается приоритет предварительной заявки на патент США № 60/489,274, поданной 22 июля 2003г., озаглавленной «SYSTEMS AND METHODS FOR APPROXIMATING A LOCATION OF A DEVICE» (СИСТЕМЫ И СПОСОБЫ АППРОКСИМАЦИИ МЕСТОПОЛОЖЕНИЯ УСТРОЙСТВА).

Область техники, к которой относится изобретение

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

Предшествующий уровень техники

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

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

Стоит рассудить, что если люди наслаждаются преимуществами от инструмента, подобного Интернет, они хотели бы иметь возможность использования этого инструмента везде, где они находятся. Развитие портативных компьютеров помогло предоставлять более подвижные точки доступа к Интернет. Однако портативные компьютеры все еще требуют некоторый тип соединения, либо проводного, либо беспроводного, со средством соединения с Интернет. Это в значительной степени ограничивает их гибкость для обычного пользователя, который всегда "на ходу". Технологии продолжали отвечать на это разработкой компьютеров, которые требуют, чтобы устройство было помещено на теле человека вместе с большими батареями и стеклянной оптикой, которая обеспечивает экран просмотра. Хотя они намного более портативны, малый объем таких устройств ограничивает их пригодность, а сокращение размера устройства (по сравнению с обычным настольным компьютером) обычно ограничивает его вычислительные возможности. Дополнительно, из-за его сложностей, оно является устройством, которое пользователь должен выбирать для того, чтобы носить (на себе), зная его ограничивающие условия и ограничения, и быть осторожным, чтобы не повредить чувствительное оборудование.

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

Несмотря на миниатюрный размер вычислительных устройств, доступных в настоящее время, их операционная концепция остается в целом такой же, что для первого изобретенного вычислительного устройства. Пользователь "входит в" устройство и задает ему вопрос. Затем устройство пытается обеспечить пользователя информацией. Продвижение было сделано в "технике проталкивания", при которой пользователь заранее программирует устройство для поиска требуемой информации. Однако это является трудоемким, и обычно программирование осуществляют в предположении, что пользователь является неподвижным (стационарным). Если даже пользователь хочет знать время и температуру в городе, в котором он(и) живет, тогда, когда он(и) находится дома, при перемещении в другой город эта информация становится нерелевантной пользователю в этот момент времени. В попытке преодолеть такую трудность технологии начали сосредотачиваться на решении задач обнаружения, или определения, местоположения пользователя. Наиболее очевидным выбором было использование Глобальной системы позиционирования или ГСП (GPS). Она предназначена для военных целей спутниковой системой определения местоположения, разработанной для того, чтобы способствовать вооруженным силам в определении местоположения (дислокации) передвижений войск и оборудования. Правительство обеспечило доступную публике версию с меньшим разрешением слежения со своих спутников. Хотя не столь же точная, как военная версия, она является очень точной в сравнении с обычными средствами. Первые гражданские устройства, которые использовали спутниковое слежение, были громоздкими и жестко ограниченными для использования. Со временем модули ГСП были значительно уменьшены в размере и могли быть легко транспортируемыми. Даже были разработаны модули, которые вставляют непосредственно в переносные компьютеры, такие как портативный компьютер. Эта комбинация разрешила пользователям отслеживать их продвижение, как, например, по уличным картам, отображаемым на их портативных ЭВМ, во время их езды на автомобиле. К сожалению, перенесение портативного компьютера, подключение всех соединений к антеннам ГСП и отыскание источника энергии для всего оборудования сделало использование такого технического средства обременительным. Дополнительно, по сути своей методики ГСП работает только тогда, когда она может непосредственно осуществлять доступ к минимальному количеству спутников, ограничивая свое использование на густонаселенных территориях, таких как большие города с небоскребами, и в особенности в тех случаях, когда человек находится в закрытом помещении.

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

Краткое описание сущности изобретения

Ниже представлено упрощенное краткое описание сущности изобретения для того, чтобы представить основное понимание некоторых аспектов изобретения. Данное краткое описание сущности изобретения не является исчерпывающим обзором изобретения. Оно не предназначено для идентификации ключевых/критических элементов настоящего изобретения или очерчивания объема изобретения. Его единственная цель состоит в том, чтобы представить некоторые концепции изобретения в упрощенной форме в качестве вводной части к более подробному описанию, которое представлено далее.

Настоящее изобретение относится в целом к определению местоположения и более конкретно - к способам обеспечения приближенного местоположения устройства с использованием множественных внешних сигналов от излучающих сигналов объектов, или источников, таких как, например, базовые станции, радиомачты, подвижные платформы, антенны на зданиях и подобное. Свойство монотонного возрастания между фактическими уровнями сигналов и индикаторами уровней сигналов, обеспечиваемыми такой методикой, как, например, Технология интеллектуального персонального объекта SPOT (ТИПО), предложенная компанией Microsoft, использовано как средство для определения местоположения устройства. Это обеспечивает средство определения местоположения без необходимости калибровки индивидуальных устройств и/или требования определенного измерительного устройства для определения местоположения. Посредством использования логического вывода, применяемого к наблюдениям частот внешних сигналов, получают средство определения местоположения устройства. В одном аспекте настоящего изобретения используют вектор ранжирования, чтобы выделить результаты из монотонно возрастающей функции векторов измеренных уровней сигналов. Это уменьшает необходимость получения в настоящем изобретении абсолютных уровней сигналов для того, чтобы определить местоположения. Настоящее изобретение также способствует аппроксимации при определении местоположения устройства, обеспечивая систему, которая не требует получения значительного количества доступных сигналов, однако обеспечивая при этом значимую точность в определении местоположений, снижая требования к вычислительным ресурсам и ресурсам хранения данных.

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

Краткое описание чертежей

Фиг.1 - блок-схема информационной системы в соответствии с аспектом настоящего изобретения.

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

Фиг.3 - иллюстрация устройства, использующего систему определения местоположения в соответствии с аспектом настоящего изобретения.

Фиг.4 - график, иллюстрирующий точность уровней сигналов в соответствии с аспектом настоящего изобретения.

Фиг.5 - график, иллюстрирующий монотонность уровней сигналов в соответствии с аспектом настоящего изобретения.

Фиг.6 - трехмерный график, иллюстрирующий перестановки хэш-кода в соответствии с аспектом настоящего изобретения.

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

Фиг.8 - график, иллюстрирующий значения индикатора уровней радиосигналов в соответствии с аспектом настоящего изобретения.

Фиг.9 - пример точностей классификации в соответствии с аспектом настоящего изобретения.

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

Фиг.11 - таблица моделируемых уровней сигналов для радиостанций в зоне Сиэтла в соответствии с аспектом настоящего изобретения.

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

Фиг.13 - карта, иллюстрирующая тестовую зону, в соответствии с аспектом настоящего изобретения.

Фиг.14 - график, иллюстрирующий связь между шириной ячейки и средней ошибкой, в соответствии с аспектом настоящего изобретения.

Фиг.15 - графики, иллюстрирующие ошибки функции плотности (распределения) вероятностей и накопленные ошибки функции плотности для заданной ширины ячейки, в соответствии с аспектом настоящего изобретения.

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

Фиг.17 - график, иллюстрирующий связь между размером окна (интервала времени) и средней ошибкой, в соответствии с аспектом настоящего изобретения.

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

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

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

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

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

Фиг.23 - схема последовательности операций для способа оптимизации наборов внешних сигналов для использования при определении местоположения устройства в соответствии с аспектом настоящего изобретения.

Фиг.24 - пример операционной среды, в которой может функционировать настоящее изобретение.

Фиг.25 - другой пример операционной среды, в которой может функционировать настоящее изобретение.

Подробное описание изобретения

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

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

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

Настоящее изобретение раскрывает подход к идентификации информации об огрубленном, или приближенном, местоположении внутри помещения и/или вне помещения посредством анализа внешних сигналов от множественных источников сигналов, таких как, например, коммерческие радиостанции и подобных. В одном примере настоящего изобретения он (источник) оперирует крайне малыми величинами мощности, делая его допустимым источником информации местоположения для небольших устройств малой мощности, которые предусматривают форму индикации уровня сигнала такую, как, например, SPOT компании Microsoft. SPOT сконцентрирована на разработке устройства, имеющего размеры наручных часов, со способностью принимать уведомления посредством цифровых данных, кодированных в пределах обычного радиовещания ЧМ (FM), или ЧМ-радиовещания. Устройство и/или способ, применяющие настоящее изобретение, дают возможность создания определяемых местоположением услуг уведомления, в одном примере использующих ранее существовавшую способность SPOT-устройств принимать ЧМ-сигналы и измерять уровни сигналов. В одном примере настоящее изобретение использует алгоритм, названный алгоритмом "RightSPOT". Настоящее изобретение является также нечувствительным к изменениям, вызванным различиями в конструкции устройств, использующих настоящее изобретение.

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

На Фиг.1 показана блок-схема информационной системы 100 в соответствии с аспектом настоящего изобретения. Информационная система 100 состоит из компонента 102 информационной системы, содержащего информационный компонент 104, системы 106 определения местоположения и компонента 108 сигналов. Сигнал 110 принимают посредством компонента 108 сигналов и обрабатывают (преобразуют) в индикатор уровня сигнала. Такая обработка обычно требует аналого-цифрового преобразования. Компонент 108 сигналов может быть способным к обработке различных сигналов, таких как внешние радиосигналы и т.п., включая, но не ограниваясь таковыми: сигналы с частотной модуляцией (ЧМ, FM). Как только сигнал преобразован в индикатор сигнала, его передают на систему 106 определения местоположения. Система 106 определения местоположения обрабатывает индикаторы сигнала и подает местоположение (данные) на информационный компонент 104. Информационный компонент 104 использует эти данные местоположения, чтобы сформировать набор релевантных данных. Релевантность данных может быть строго основана на местоположении и/или комбинации местоположения и предпочтений пользователя (посредством входных данных пользователя, не показаны). Данные могут также быть связаны с информацией из загружаемых справочных таблиц, которые способствуют обработке. Как только данные выбраны, их поставляют пользователю в качестве "требуемой относительной информации" 112 посредством пользовательского интерфейса, например графического пользовательского интерфейса (ГПИ, GUI) и/или пользовательского интерфейса на основе текста и подобного.

В другом примере настоящего изобретения система 106 определения местоположения сохраняет данные местоположения. Это дает возможность использовать данные о местоположении в точке, более поздней по времени, так, например, чтобы уменьшить чувствительность в определении местоположения вследствие ориентации устройства (например, усредняя количество "X" последних логических выводов местоположения). Системы слежения (например, транспортное средство, пакет программ, персонал, аппаратура слежения и т.п.) также могут использовать этот тип данных местоположения из предыстории. Таким образом, настоящее изобретение может быть использовано, например, чтобы способствовать полиции, например, в определении того, где находился похищенный объект, например автомобиль, или для помощи службе доставки груза, чтобы определить, как конкретный груз был транспортирован после того, как была обнаружена задержка доставки. Родители также могли бы использовать пример настоящего изобретения, чтобы узнать, где были их дети в течение предшествующего интервала времени. Аналогично, предприниматели могут отслеживать служащих и оборудование, чтобы повысить производительность. Настоящее изобретение также может быть использовано для отслеживания животных, например домашних животных и подобного. Компьютеры также могут автоматически сообщать о своих местоположениях, используя настоящее изобретение. Это позволяет компьютеру настраивать себя автоматически на основании своего местоположения для таких параметров, как часовые пояса, страны и языки и т.п.

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

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

Что касается Фиг.2, на ней проиллюстрирована блок-схема системы 200 определения местоположения в соответствии с аспектом настоящего изобретения. Систему 200 определения местоположения составляет компонент 202 определения местоположения. Компонент 202 определения местоположения принимает обучающие данные 204, используемые, чтобы обучить компонент 202 определения местоположения. Обучающие данные 204 могут быть составлены из перестановок хэш-кодов и т.п. для различных, конкретных для местности, сигналов и т.п. Эти данные 204 могут быть вычислены исходя из информации, полученной посредством физического перемещения к местоположению для получения характеристик сигнала и/или посредством программного обеспечения (имитационного) моделирования, которое обеспечивает требуемые характеристики сигнала. В других примерах настоящего изобретения обучающие данные не используются. Входные данные 206 индикатора уровня сигнала дают возможность компоненту 202 определения местоположения определить его местоположение на основании индикаторов уровней сигналов. Не требуется, чтобы индикаторы были абсолютными в терминах фактического уровня сигнала. Компонент 202 определения местоположения обрабатывает входные данные 206 уровня сигнала в имеющем уменьшенную чувствительность средстве по отношению к абсолютному значению, чтобы обеспечить местоположение 208. Компонент 202 определения местоположения обычно состоит из компонента анализа (не показан), который вычисляет вектор ранжирования, который обеспечивает средство ранжирования индикаторов уровней сигналов безотносительно к абсолютным значениям.

Обращаясь к Фиг.3, на ней показано SPOT-устройство 300. SPOT-устройство 300 включает в себя носимое устройство 302, окно 304 прогноза погоды, окно 306 трафика, окно 308 ресторана и окно 310 развлечений. Одним из обещаний вездесущей вычислительной техники является соединение пользователей с важной информацией по мере их перемещения по миру. Один пример настоящего изобретения использует возможности небольшой платформы устройств малой мощности из SPOT-устройств. SPOT обеспечивает пользователей средством для приема критических уведомлений на устройстве, имеющем размеры наручных часов, как изображено на Фиг.3. SPOT-устройство разработано для прослушивания кодированных в цифровой форме данных, таких как новости, прогнозы погоды, личные сообщения, изменения трафика и розничные каталоги, и подобное, передаваемых на стандартных несущих частотах радиовещания ЧМ, на полосе частот, которую специально арендуют у ведущих радиостанций. Устройство имеет возможность для соединения миллионов людей со значимыми уведомлениями и предупреждениями.

Помимо форм-фактора небольшого размера особенностью SPOT-устройства является длительный срок службы аккумулятора, такой, который ассоциируют с цифровыми часами, что максимизирует интервал времени между зарядками. Таким образом, SPOT-устройство создано, чтобы минимизировать размер и потребление мощности. Настоящее изобретение в одном примере применяют, чтобы обеспечить использующий крайне малую мощность способ идентификации местоположения устройств, таких как, например, SPOT-устройства. Поскольку SPOT-устройство, использующее настоящее изобретение, может определить информацию местоположения, оно поддерживает новые виды опытов, таких как разрешение устройству прослушивать только те предупреждения, которые являются релевантными конкретным местоположениям. Предшествующие основные способы определения местоположения данных для передачи на конкретные устройства основывались на ограниченном диапазоне радиосигналов ЧМ (сигналов ЧМ-радиовещания). Таким образом, только устройства в пределах диапазона конкретной радиомачты принимали данные, релевантные зоне обслуживания этой мачты. Однако для некоторых сообщений такая разрешающая способность местоположения является слишком грубой. Обновление трафика, ограниченное время предложений, имеющих скидки, и перечни близлежащих аттракционов нуждаются в фильтрации местоположения с более высоким разрешением, чем обеспечивается зонами обслуживания радиостанций ЧМ. Хотя ГСП является кандидатом для предоставления более точной информации местоположения, ГСП-приемник будет потреблять дорогую мощность батареи и увеличивать объем и стоимость уже плотно упакованного устройства. Дополнительно, ГСП ограничен использованием вне помещения, при котором может быть установлена непосредственная связь с искусственными спутниками.

В одном примере настоящего изобретения предусмотрено средство для определения местоположения устройства на основании анализа уровней внешних сигналов от имеющихся источников частотных сигналов, таких как, например, ЧМ-радиостанции (станции ЧМ-радиовещания). Системы и способы настоящего изобретения, которые используют алгоритмы, такие как "RightSPOT", могут быть созданы на основе методики SPOT, которая была уже разработана для приема уведомлений, включая аппаратные средства и программное обеспечение для измерения уровня сигнала на произвольных частотах в полосе частот ЧМ.

Настоящее изобретение в одном примере использует вектор уровней радиосигналов, воспринятых на различных частотах, чтобы идентифицировать местоположение. Всякий раз, когда местоположение должно быть логически выведено, устройство осуществляет сканирование набора ЧМ-частот и регистрирует уровень сигнала для каждой. Стандартное SPOT-устройство сканирует многочисленные ЧМ-радиостанции и измеряет уровень сигнала для того, чтобы найти один достаточно мощный, передающий SPOT-данные. В одном примере настоящего изобретения Индикацию уровня принимаемого сигнала (ИУПС, RSSI) для SPOT обеспечивают посредством аналого-цифрового преобразователя (АЦП, ADC) в устройстве согласно настоящему изобретению. Необработанные цифровые измерения для каждой частоты масштабируют и затем усредняют, например, по 20 показаниям за 13 миллисекунд. АЦП и соответствующая схема обычно не калиброваны для измерения ИУПС в каких-либо конкретных единицах измерения или должны быть согласованными между устройствами (от устройства к устройству). Специалист в данной области техники может оценить, что хотя вышеупомянутый пример использует методику SPOT, такую как ИУПС, другие средства для получения индикатора уровня сигнала являются совместимыми с настоящим изобретением. Настоящее изобретение может использовать любой индикатор уровня сигналов, имеющий единицы измерения, или без единиц измерения, который обеспечивает относительные уровни сигналов.

На Фиг.4 показан график 400, иллюстрирующий уровни сигналов в соответствии с аспектом настоящего изобретения. Вертикальная ось представляет уровень входного сигнала, и горизонтальная ось - измеренный уровень (ИУПС) сигнала, поступивший от устройства, такого как, например, SPOT-устройство, которое обеспечивает ИУПС. Кривая 402 представляет математическую функцию, подобранную для точек измеренных данных, представленных маленькими треугольниками 404. Ожидаемая несогласованность между устройствами для показателей ИУПС представляет препятствие, поскольку такой разброс значений затрудняет попытки обобщения для повторного использования однозначного соответствия между уровнями сигнала и местоположениями. Одно возможное решение данной проблемы состоит в том, чтобы специально калибровать каждое устройство априори, используя источник известных уровней передач ЧМ. Результат одного из таких испытаний показан на Фиг.4, демонстрируя то, как показания ИУПС для конкретного устройства изменяются при изменении известного уровня переданного сигнала. Данные для этого испытания были приняты в клетку Фарадея, но процедуру посчитали слишком дорогостоящей для массового производства. Другое решение состоит в том, чтобы обучить каждое устройство в различных местоположениях, регистрируя векторы уровней сигналов в известных местах, которые подлежат использованию в том же устройстве позднее. Обычные потребители вероятно не допустят такой режим обучения.

В дополнение к разновидностям изготовления на уровни сигнала воздействует также ориентация устройства, его окружение и установка средства крепления, например, браслета и подобного, которое также может служить в качестве приемной антенны сигнала. Было бы почти невозможно упреждать все эти переменные факторы, воздействующие на абсолютный уровень сигнала. Если абсолютные уровни сигналов могут быть упреждены, вероятностная схема, подобная представленной Roos, T., P. Myllymaki и H. Tirri в «A Statistical Modeling Approach to Location Estimation», IEEE Transactions on Mobile Computing, 2002; 1 (1): p. 59-69, была бы приемлемой. Однако учитывая неосуществимость исследования частотных характеристик отклика для каждого устройства, необходим альтернативный способ сравнения уровней сигнала.

Вместо того, чтобы зависеть от абсолютного уровня сигнала в качестве индикатора позиции, настоящее изобретение использует преобразования уровней сигнала, что обеспечивает более устойчивые логические выводы. В обычных тестах устройства, использующие настоящее изобретение, как, например, алгоритм RightSPOT, дали результаты ранжирования набора радиостанций по их измеренным ИУПС, такие, как описаны ниже. Ясно, что устройства не могут быть зависимыми от необходимости выдавать согласованные абсолютные уровни сигнала. В силу данного факта используют дополнительное предположение, основанное на том факте, что относительные уровни сигналов являются относительно согласованными (то есть упорядоченный перечень радиостанций, отсортированных по уровню сигнала, значительно не изменяется для заданного местоположения). Более точно, предполагают, что связь между уровнем входного сигнала и измеренным ИУПС является монотонно возрастающей. На Фиг.5 показан график 500, иллюстрирующий монотонность уровней сигналов в соответствии с аспектом настоящего изобретения. На графике 500 показано, что если измеренный ИУПС подвижного устройства является монотонно возрастающей функцией уровня входного сигнала, то упорядоченность уровня сигнала для входных данных также сохраняется. Например, если А<B<C, то эти значения, преобразованные посредством различающихся функций ИУПС-измерения, поддерживаются существенно в том же порядке, что и уровни сигнала. Это дает возможность настоящему изобретению оперировать с широким многообразием устройств несмотря на изменения между устройствами в том, как они измеряют уровни сигналов.

Настоящее изобретение в одном примере использует алгоритм, который логически выводит местоположение устройства посредством сканирования перечня n радиочастот (частот радиовещания) (например, радиочастот ЧМ и подобных), f = (f₁, f₂,..., f_n), имея результатом соответствующий вектор измеренных уровней сигналов, s = (s₁,s₂,…,s_n). Затем используют процедуру сортировки, чтобы вычислить вектор ранжирования для уровней сигнала, ν=(r₁,r₂,...,r_n) в порядке возрастания, при этом каждый r_i задает ранг для соответствующего s_i в s. Например, если вектором уровней сигналов является s=(12,40,38,10), то соответствующим вектором ранжирования является ν=(2,4,3,1). Следует отметить, что вектор ранжирования является нечувствительным к любой монотонно возрастающей функции для элементов из s, что делает алгоритм устойчивым к изменениям в том, как различные устройства измеряют уровень сигнала. Таким образом, настоящее изобретение не требует абсолютный уровень сигнала, чтобы определить местоположение устройства.

В качестве дополнительного примера радиочастоты могут представлять различные радиостанции, которые могут быть идентифицированы посредством индекса [1...n]. Измерение ИУПС для каждой станции имеет результатом набор упорядоченных пар, задающих для каждой радиостанции индекс станции и уровень сигнала: {(1,s₁),(2,s₂),(n,s_n)}. Такой набор кортежей уровней радиостанций затем сортируют по уровню сигнала, чтобы получить вектор ранжирования. Например, пусть n=3 и результатами сканирования являются {(1,40),(2,30),(3,35)}. Сортировка такого набора упорядоченных пар по уровню сигнала дает {(2,30),(3,35),(1,40)}. Тогда вектором ранжирования являются индексы радиостанции, взятые в порядке уровня принятых сигналов, то есть ν=(2,3,1), указывающим, что s₂<s₃<s₁. Равные уровни сигналов могут быть разрешены, например, посредством произвольной сортировки, сортировки по первым обнаруженным, сортировки по наиболее часто обнаруженным и подобного.

Для n радиостанций существуют n! возможных векторов ранжирования, которые являются перестановками целых чисел 1,2...,n. Каждый вектор ранжирования может быть поставлен в соответствие целому числу r {0,1...,n!-1}, используя смешанное позиционное представление целых чисел, как описано Knuth, D.; Seminumerical Algorithms; в «The Art of Computer Programming»; 1981; Addison-Wesley: Reading, Massachusetts; p. 64 (Algorithm P). Таким образом, уникальный хэш-код генерируют для каждой перестановки уровней сигнала.

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

Должно быть оценено, что классификация в соответствии с различными аспектами настоящего изобретения может использовать вероятностный анализ и/или анализ на основе статистики (например, разложение на анализ полезности и анализ затрат) для того, чтобы прогнозировать или логически выводить действие, которое пользователь желает, чтобы было автоматически выполняемым. Классификатор может быть функцией, которая ставит в соответствие вектору входных атрибутов, x=(x₁,x₂,x₃...,x_n), доверительность, что входные данные принадлежат классу, то есть f(x)=доверительность (класс). Например, может использоваться классификатор машин (алгоритмов) опорных векторов (МОВ), который обычно действует посредством нахождения динамически изменяющейся гиперповерхности в пространстве возможных входных данных. Могут использоваться другие подходы к классификации с применением направленных и ненаправленных моделей, которые включают в себя, например, простые байесовские (naïve Bayes), байесовские (Bayesian) сети, деревья принятия решений и вероятностные модели классификации, обеспечивающие различные модели независимости. Классификация, как используется в документе, является также включающей статистическую регрессию, которую используют, чтобы разработать модели приоритета.

На Фиг.6 изображен трехмерный график 600, иллюстрирующий перестановки хэш-кодов в соответствии с аспектом настоящего изобретения. График 600 составляют ось 602 нормированной гистограммы, ось 604 местоположения и ось 606 выведенного (полученного) перестановочного хэш-кода. В одном примере настоящего изобретения, например, чтобы обучить систему, приемное устройство, такое как, например, SPOT-устройство, вводят в каждое из L местоположений, регистрируя хэш-коды r_i ^(l), при этом l=1,2...,L являются индексами местоположений и i=1,2...,N_l являются индексами хэш-кодов, наблюдаемых в местоположении l. Для каждого местоположения создают нормированную гистограмму хэш-кодов, чтобы аппроксимировать дискретное распределение вероятностей хэш-кодов, наблюдаемых в этой точке . Пример таких нормированных гистограмм для шести местоположений и трех частот показан на Фиг.6.

При заданных правдоподобиях наблюдений и наблюдении R* вычисляют вероятность нахождения в любом из L местоположений, используя правило Байеса (Bayes):

= (1)

При этом является априорной вероятностью нахождения в местоположении l. Поскольку отсутствует конкретное предшествующее знание о местоположении устройства, то предполагают однородное распределение, устанавливая p(l)=1/L. Вместо вычисления правдоподобия (вероятности) непосредственно сравнивают ненормированные апостериорные (распределения). Классификатор, такой как, например, классификатор Байеса, идентифицирует класс по максимальной апостериорной вероятности, то есть:

l^* = = (2)

Алгоритмически это означает, что для наблюдения r* принимают во внимание нормированную гистограмму (например, Фиг.6), просматривая значения по всему диапазону местоположений l ∈ {1,2,...,L} и выбирая местоположение l с наибольшим значением .

В качестве образца использования одного примера настоящего изобретения описан следующий тест. Три SPOT-устройства наблюдения были выбраны случайным образом из лабораторного хранилища тестов-устройств. Не были сделаны какие-либо усилия, чтобы выбрать устройства наблюдения, которые давали бы согласованные уровни сигналов, и не были сделаны какие-либо усилия, чтобы калибровать устройства наблюдения относительно источника абсолютного сигнала или относительно друг друга. Это моделирует обычное массовое производство таких устройств, учитывая экономическую недопустимость выполнения тестирования для калибровки устройств.

На Фиг.7 показана иллюстрация карты 700, используемой в соответствии с аспектом настоящего изобретения. Карту 700 составляют шесть местоположений 702-712, представляющих пригороды Сиэтла. Каждое устройство было запрограммировано для измерения уровней сигналов от 32 различных местных радиостанций ЧМ. Затем устройства были транспортированы в шесть различных пригородов в зоне Сиэтла, регистрируя все 32 уровня сигналов, делая для каждой станции один замер в секунду. В каждом пригороде были сняты (~10 минут) в среднем приблизительно 720 показаний при перемещении вокруг центра розничной торговли пригорода. Розничный центр, который был выбран в качестве убедительных (контролирующих) применений для одного примера настоящего изобретения, включает в себя, например, розничные предприятия, рассылающие чувствительные ко времени предложения и номенклатуру местных соблазнов (аттракционов).

На Фиг.8 изображен график 800, иллюстрирующий значения индикатора уровней радиосигналов в соответствии с аспектом настоящего изобретения. График 800 составлен из необработанных ИУПС-данных 802 и данных 804, отфильтрованных медианным фильтром. Было обнаружено, что необработанные ИУПС-данные от устройств должны быть с шумами, как показано на Фиг.8, поэтому к данным был применен обрабатываемый методом окна медианный фильтр, заменяя каждый ИУПС медианой, формируемой из собственного значения и предшествующих 29 нефильтрованных значений. Специалист в данной области техники может оценить, что могут быть осуществлены другие средства фильтрации вместо обрабатываемого методом окна медианного фильтра.

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

На Фиг.9 проиллюстрирован пример 900 точности классификации в соответствии с аспектом настоящего изобретения. Пример 900 составляют некоторое количество 902 источников внешних сигналов, поднабор источников 904 внешних сигналов и результат 906 точности классификации. Он показывает, как часто устройство было корректно классифицировано по одному из шести пригородов, используемых для испытания. В попытке минимизировать затраты ресурсов хранения и вычислительных при определении местоположения был выполнен эксперимент, такой как, например, использование значительно сокращенного поднабора из 32 зарегистрированных радиостанций. Для каждого испытания n радиостанций был исследован набор из различных комбинаций из станций, подлежащих использованию для классификации местоположения. Результаты показаны на Фиг.9 в терминах точности классификации. Таким образом, настоящее изобретение может использоваться с меньшим количеством источников внешних сигналов и, однако, быть использовано для определения местоположения устройства.

Представленная точность является частью корректных логических выводов, сделанных по всем тестам, в которых одно устройство использовали для создания гистограмм и два других использовали для испытания. При n≤5 все возможные комбинации могут быть исчерпывающе протестированы. Для n>5 был протестирован составленный случайным образом поднабор из 10,000 комбинаций. Это объясняет, почему точность классификации снижается при переходе от n=5 к n=6 станциям; вероятно, что не была найдена наилучшая комбинация посредством сделанного на основе моделирования выбора случайного поднабора для n=6. Наивысшей точностью классификации является 81,7% при использовании n=8 радиостанций. Следует отметить, что использование данного уровня точности определения местоположения было осуществлено ситуационно-обусловленным образом, используя источники внешних сигналов (например, радиопередатчики и т.п.) и используя приемники, которые были не предназначены для обеспечения информации местоположения.

Данный пример демонстрирует возможность использования существующих источников внешних сигналов, таких как, например, радиосигналы ЧМ, для того чтобы определить местоположение устройства в пригороде, используя один пример настоящего изобретения. Посредством использования существующих технических средств, таких как, например, SPOT-устройства, вместе с настоящим изобретением, существующие аппаратные средства могут быть использованы, чтобы измерять уровни сигналов, таких как, например, уровни радиосигналов ЧМ, так что в одном примере настоящего изобретения возможность для определения местоположения требует дополнения к настоящей конфигурации только небольшого объема программного обеспечения. Различные устройства измеряют уровни сигналов различным образом, и на уровни сигналов воздействуют также многие другие переменные. Настоящее изобретение, применяющее, например, алгоритм байесовской классификации, не использует абсолютные уровни сигналов, но вместо этого использует ранжирование уровней сигналов, чтобы гарантировать устойчивость к устройствам и другим переменным.

Очевидно, чтобы логически вывести местоположение, исходя из хэш-кода ранжирования, должна быть связь между местоположением и хэш-кодами. Один способ установить такую связь, как описано выше, состоит в том, чтобы физически посетить местоположения на местности и зарегистрировать уровни сигналов. Однако для обычного использования это утомительно и требует работы по техническому обслуживанию, если радиостанция изменяет мощность своего передатчика и/или местоположение. Таким образом, настоящее изобретение также может использоваться, чтобы упреждать характеристики уровней сигналов от различных местоположений без фактического их посещения для получения характеристик сигнала, или "обучающих данных". Вместо выполнения большого количества физических измерений используют программное обеспечение ComStudy компании RadioSoft (см. в целом, Интернет-сайт http://www.radiosoft.com) и подобное, чтобы генерировать карты моделируемых уровней радиосигнала ЧМ. Такое моделирование может также способствовать определению хорошего поднабора радиостанций, чтобы прослушивать их с целью лучшего определения местоположения. Методики для оптимального использования карт уровней радиосигналов включают в себя использование вероятностных способов, чтобы изучить, как надежность и потенциальные смещения имитационного моделирования отличаются от фактических принятых данных на основании таких свойств, как топология, геометрические связи между топологией и/или передатчиками, и присутствие зданий и других искусственных структур. Например, можно обучить статистические классификаторы надежности и/или смещению на основании совокупности данных о различиях в моделируемых уровнях радиовещания и фактических обнаруженных уровнях радиовещания и использовать такие классификаторы для совершенствования доверительности и/или поправок в таблицах карт радиовещания и функциях упорядочивания уровней радиовещания.

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

Программное обеспечение ComStudy поддерживает много моделей распространения радиовещания, которые могут быть использованы для прогнозирования карт радиовещания ЧМ. Модель Longley-Rice (см. P.L. Rice, A.G. Longley, K.A. Norton, and Barsis, A.P.; Transmission Loss Predictions for Tropospheric Communication Circuits; National Bureau of Standards Technical Note 101, January, 1967) была выбрана в этом примере образца настоящего изобретения благодаря ее известной точности. В целом она является наиболее точной из вариантов выбора, поскольку она включает в себя отражение, преломление (отклонение лучей по мере того, как они проходят сквозь атмосферу) и несколько типов дифракции (рассеивание сигнала ЧМ по возвышенностям). Модель использует карту рельефа местности, чтобы моделировать влияние возвышенностей и впадин.

ComStudy параметризует каждый передатчик радиостанции посредством его частоты, мощности передачи и местоположения (широта, долгота). Для каждого передатчика генерируют матрицу уровней (напряженности) полей. Матрица является сеткой из прямоугольных ячеек, разнесенных по выбранной зоне на местности, причем каждая ячейка содержит информацию об уровне сигнала от рассматриваемого передатчика. Ширина ячеек была выбрана так, чтобы быть дугой в 6 секунд (приблизительно 185 метров в направлении север-юг и 124 метра на восток-запад). Это эквивалентно наличию 40 точек (ячеек) на квадратный километр. Затем ComStudy применяет выбранную модель распространения, чтобы вычислить уровень (напряженности) поля в центре каждой ячейки. В данном примере были сгенерированы карты для 28 местных радиостанций ЧМ в зоне Сиэтла, Вашингтон (Seattle, Washington).

Перед использованием карт моделируемых уровней сигналов для логического вывода местоположения было сделано определение относительно уровня доверительности того, что карты точно прогнозируют векторы ранжирования. Чтобы это выполнить, SPOT-устройства наблюдения были запрограммированы для измерения уровней сигналов от тех же 28 радиостанций ЧМ для сгенерированных карт. Затем SPOT-устройства наблюдения были транспортированы по зоне, регистрируя уровни сигналов ото всех 28 станций, делая одно сканирование 28 станций в секунду, имея результатом приблизительно 3920 показаний для каждой станции. Широта и долгота были зарегистрированы также от приемника ГСП. Для оценивания точности (имитационного) моделирования была вычислена ранговая корреляция Spearman'а (см. William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery; Numerical Recipes in C; 1992, Cambridge Press) между ранжированными радиостанциями по измеренным уровням сигналов и по моделируемым уровням сигналов, используя показания ГСП, чтобы определить, какие моделируемые уровни использовать из карт. Ранговая корреляция Spearman'а была использована вместо (корреляции) Kendall'а, потому что различиям между значениями данных, ранжированных дополнительно отдельно, задают больший вес с помощью Spearman. Обе корреляции находятся в диапазоне [-1...1], причем "1" указывает эквивалентные ранжирования и "-1" указывает противоположные ранжирования.

Гистограмма 1000 для корреляций Spearman'а между измеренным уровнем сигнала и моделируемым уровнем сигнала в соответствии с аспектом настоящего изобретения изображена на Фиг.10. На гистограмме 1000 показано, что более 95% измеренных ранжирований были коррелированными с моделируемыми ранжированиями с коэффициентом по меньшей мере 0,6 в масштабе [-1...1]. Это указывает, что моделируемые результаты являются достаточно точными для определения местоположения SPOT-устройств наблюдения. Достижима даже более высокая степень корреляции, если количество станций является сокращенным, как обсуждено более подробно ниже.

При 28 доступных радиостанциях обеспечиваются 28!≈3,05×l0²⁹ различных векторов ранжирования, которые требуют огромных непроизводительных затрат вычислительных ресурсов и ресурсов хранения. Однако многие из таких станций осуществляют вещание с одной и той же радиомачты, причем некоторые имеют сходную мощность передачи. Измерение уровней сигналов от совместно расположенных со сходной мощностью передачи станций является избыточным. Чтобы устранить такую избыточность, 28 станций разделены на группы из примерно сходных станций. Затем используют нижеследующие критерии, чтобы оценить сходство.

1. Вычислить коэффициент корреляции Пирсона (Pearson) (наблюдение, идентификатор) между всеми парами станций на основании пространственно соответствующих точек на картах моделируемых уровней сигналов. (Следует отметить: коэффициент корреляции Пирсона является стандартным коэффициентом линейной корреляции, не ранговой корреляции.)

2. Найти группы станций, которые являются коррелированными между собой в большей степени, чем некоторая пороговая величина . Для данного примера образца настоящего изобретения используют =0,95.

3. Из каждой коррелированной группы выбрать станцию с наивысшим средним уровнем сигнала для представления группы.

Применением вышеупомянутых критериев к моделируемому уровню сигнала для зоны Сиэтла (критерий был также применен к фактическим измерениям от SPOT-устройств наблюдения и привел примерно к тем же результатам при τ=0,9) было установлено, что имеются семь групп коррелированных станций, имеющих коэффициент корреляции Пирсона по меньшей мере 0,95. На Фиг.11 изображена таблица 1100 для моделируемых уровней сигналов радиостанций в зоне Сиэтла в соответствии с аспектом настоящего изобретения. В таблице 1100 показаны семь групп станций наряду с частотами, средними значениями и дисперсиями для коррелированных станций в каждой группе. Станции, выбранные из каждой группы, показаны жирным шрифтом.

Применением вышеупомянутых критериев количество станций сокращено с 28 до 7. Это означает, что вместо наличия 28! различных векторов ранжирования имеются только 7!=5040 векторов ранжирования, или сокращение на 25 порядков от величины. Это имеет существенно положительное воздействие на производительность вычислительную и хранения данных для способов, используемых для определения местоположения. Это особенно важно для устройств с ограниченными ресурсами. На Фиг.12 проиллюстрирована гистограмма 1200 для корреляций Spearman'а между измеренным уровнем сигнала и моделируемым уровнем сигнала для семи выбранных станций в соответствии с аспектом настоящего изобретения. Гистограмма 1200 демонстрирует значительное улучшение по сравнению с подобной гистограммой 1000 для 28 станций (Фиг.10), даже с более высокой степенью корреляции между измеренными и моделируемыми уровнями сигналов. Более 95% векторов ранжирования измеренных уровней сигналов являются коррелированными с моделируемым уровнем сигнала с коэффициентом 0,8 или выше. Это дополнительно подчеркивает, что моделируемые результаты являются действительными для того, чтобы использовать для определения местоположения SPOT-устройства наблюдения и аналогичных устройств и подобных.

Каждую ячейку из карт моделируемых уровней сигналов преобразуют к хэш-коду ранжирования, который в конечном счете используют для логического вывода местоположения по измеренным хэш-кодам ранжирования. Карты моделируемых уровней сигналов генерируют на сетке, имеющей ячейки приблизительно 124 метра шириной («восток-запад») и 185 метров высотой («север-юг»). Это является близким к пределу максимальной разрешающей способности моделирования ComStudy и является намного более точным, чем необходимо для данного примера настоящего изобретения. Кроме того, такая высокая разрешающая способность обеспечивает 442,806 ячеек (811 «восток-запад» на 546 «север-юг»), чтобы представить испытательную зону вокруг Сиэтла. Хэш-коды ранжирования находятся в диапазоне [0...7!-1], означая, что для каждой ячейки с высоким разрешением (мелкой) требуется 13-битовое целое число, чтобы представить ее хэш-код. Карта радиовещания потребовала бы 811×546×13/8≈0,7 Мбайт, чтобы представить мелкую сетку из хэш-кодов для тестируемой зоны. В сущности говоря, это слишком много для малых, с ограниченными ресурсами устройств.

Чтобы смягчить эту проблему хранения и представлять хэш-коды с приемлемой разрешающей способностью, по мелкой сетке создают огрубленную, или крупную сетку, и каждую крупную ячейку представляют в качестве гистограммы хэш-кодов ранжирования, которые относятся к ее нижележащим мелким ячейкам. Размер крупных ячеек был изменяем, но обычным размером является 3 км × 3 км, что покрывает 16×24=384 мелкие ячейки. Гистограмма каждой крупной ячейки нормирована, чтобы для ячейки дать оценку распределения вероятностей хэш-кодов ранжирования. Математически такой оценкой правдоподобия (вероятности) является , причем r ∈ [0...n!-1] представляет хэш-код ранжирования для n радиостанций и c_i, i [0...m] представляет одну из m крупных ячеек.

На практике гистограммы являются разреженно заполненными из-за большого количества возможных хэш-кодов ранжирования. Вследствие помех, ориентации устройства и немоделируемых эффектов распространения радиоволн в ячейке часто измеряют хэш-коды ранжирования, для которых моделируемое правдоподобие является нулевым. Соответственно, оценку правдоподобия сглаживают, чтобы заполнить пропуски. К сожалению, простое сглаживание хэш-кодов ранжирования r не является приемлемым, поскольку соседние (близкие) хэш-коды не обязательно представляют подобные (одинаковые) векторы ранжирования. Вместо этого выполняют сглаживание, заменяя значение в каждом дискретном элементе (столбике) гистограммы максимальным значением по всем дискретным элементам, у которых коэффициент корреляции Spearman'а с рассматриваемым дискретным элементом превышает выбранное пороговое значение . В форме уравнения (ненормированное) сглаженное правдоподобие вычисляют как:

(3)

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

При заданном измеренном хэш-коде r ранжирования вероятность нахождения в ячейке c_k задается по правилу Байеса:

(4)

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

c = (5)

В действительной практике эти результаты сглаживают взятием ячейки, наиболее часто логически выводимой по «K» последним сканированиям уровня сигнала (размеру временного окна). Это помогает удерживать логический вывод местоположения от необоснованных скачков с места на место, хотя чрезмерное значение «K» может вызвать то, что логический вывод будет "слишком привязанным к месту".

Пример выше был выполнен в большей зоне Сиэтла со SPOT-устройством наблюдения, запрограммированным для измерения уровней сигналов для сокращенного набора из 7 местных радиостанций ЧМ. SPOT-устройство наблюдения было транспортировано по зоне, регистрируя уровни сигналов для всех 7 станций, снимая показания одного сканирования 7 станций в секунду, имея результатом приблизительно 3920 показаний для каждой станции вместе с показаниями ГСП о местоположении. Тем временем была сгенерирована карта моделируемого радиовещания для 7 станций. На Фиг.13 изображена карта 1300, иллюстрирующая тестовую зону в соответствии с аспектом настоящего изобретения. На карте 1300 показан путь 1302 движения вместе с крупной сеткой 1304, имеющей ширину ячейки 7 км, которая была использована для осуществления логического вывода местоположения. Путь 1302 движения включал в себя как автомагистрали, так и дороги местного движения.

Пример иллюстрирует, что местоположение устройства может быть определено с помощью настоящего изобретения с точностью до менее чем 10 миль (≈16 километров), используя простые гистограммы, созданные поверх карты моделируемого радиовещания. Ниже приведено описание влияния на точность оцениваемого местоположения порогового значения корреляции , размера «K» временного окна и ширины w ячейки сетки.

Пример показывает, что ширина w ячейки крупной сетки является важным параметром в терминах воздействия на точность логического вывода местоположения. Увеличение ширины крупной ячейки имеет преимущество наличия большего количества ячеек мелкой сетки в оценке гистограммы для и, следовательно, большей информации о распределениях вероятностей ранжирования. К тому же увеличение ширины ячейки уменьшает общее количество ячеек в сетке и таким образом сокращает непроизводительные издержки вычислений. Однако по мере увеличения ширины ячейки разрешающая способность определения местоположения естественным образом снижается. На Фиг.14 показан график 1400, иллюстрирующий связь между шириной ячейки и средней ошибкой, для =0,9 и K=5 в соответствии с аспектом настоящего изобретения. Из графика 1400 можно видеть, что есть три значения (1,7,11 километров), которые приводят к более низкой средней ошибке, приблизительно 10 миль (~16 километров). На Фиг.15 на графиках 1500, 1502 иллюстрированы ошибки функции плотности (распределения) вероятностей и накопленные ошибки функции плотности для заданной ширины ячейки в соответствии с аспектом настоящего изобретения. График 1500 функции плотности вероятностей (ФПВ, PDF) ошибки и график 1502 накопленной ошибки функции плотности (распределения вероятностей) (КФП, CDF) соответствуют ширине ячейки w=1 километр, =0,9 и K=5.

Вторым фактором, который воздействует на точность алгоритма логического вывода, является сглаживающее пороговое значение корреляции. Как описано выше, пороговое значение корреляции было введено для сглаживания оценки правдоподобия. Поэтому увеличение будет приводить к заполнению большего количества пропусков в основанной на гистограмме оценке . Однако увеличение выше некоторого значения будет приводить к слишком сильному сглаживанию, уменьшая различимость различных местоположений. На Фиг.16 изображен график 1600, иллюстрирующий связь между пороговым значением корреляции и средней ошибкой в соответствии с аспектом настоящего изобретения. На графике 1600 показано, что есть глобальный минимум средней ошибки при =0,9, причем w=1 километр и K=5 (Аномалия интерполяции графика несет ответственность за ложный спад вблизи =0,95).

Другим фактором, который воздействует на точность, является размер «K» временного окна. Поскольку радиостанции были сканированы с частотой 1 Гц, то «K» соответствует количеству секунд, в которые используют данные, чтобы логически вывести позицию. Ясно, что увеличение «K» повышает точность; однако это также повышает требования к устройствам хранения данных и вычислительным возможностям. На Фиг.17 показан график 1700, иллюстрирующий связь между размером окна и средней ошибкой в соответствии с аспектом настоящего изобретения. Из графика 1700 ясно, что среднюю ошибку менее чем 10 миль (~16 километров), получают при размере «К» окна K≥10, при этом w=1 километр и =0,9.

Настоящее изобретение обеспечивает средство для логического вывода местоположения устройства на основании уровней внешних сигналов, таких как уровни радиосигналов ЧМ и подобных. Преимущества изобретения включают в себя широкую зону обслуживания радиовещания ЧМ, охватывающую местоположения внутри помещений и вне помещений, и подготовленность целевого устройства, такого как SPOT-устройство и подобного, к измерению уровня радиосигнала, обеспечивая точность в несколько миль. Настоящее изобретение является устойчивым к различиям измерений между устройствами, полагаясь на логические выводы, основанные на ранжировании внешних сигналов, нежели на их абсолютных уровнях сигналов. При использовании моделируемых уровней сигналов не требуется ручной сбор информации об уровне сигнала как функции местоположения. Посредством использования сглаженных гистограмм хэш-кодов ранжирования местоположение устройства может быть логически выведено с точностью до менее чем 10 миль (~16 километров). Крайне низкое использование ресурсов, применяемое согласно настоящему изобретению, дает возможность обеспечивать функциональность для устройств с ограниченными ресурсами, таких как малые носимые устройства.

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

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

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

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

Обращаясь к Фиг.18, на ней изображена схема последовательности операций способа 1800 для определения местоположения устройства в соответствии с аспектом настоящего изобретения. Способ 1800 начинает этап 1802, обеспечивая индикаторы 1804 уровней сигналов. Индикаторы являются обычно представлениями сигналов, например внешних сигналов и подобных, от источников сигналов, таких как радиомачты, антенны зданий и подвижные устройства (включая наземные и воздухоплавательные устройства и подобные) и подобное. Сигналы могут включать в себя, но не ограничиваться таковыми: частотно-модулированные сигналы, амплитудно-модулированные сигналы, сверхвысокочастотные сигналы, сигналы очень высокой частоты и подобные и даже более направленные сигналы, такие как СВЧ-сигналы верхнего диапазона и т.п. Настоящее изобретение также может быть приспособлено для функционирования с устройствами, принимающими более высокие частоты, которые способны индицировать уровни сигналов инфракрасного, рентгеновского и космического излучения и подобного. Подобным образом устройства, принимающие более низкие частоты, которые обеспечивают прием сверхзвуковых, звуковых и инфразвуковых частот и подобного, также являются работоспособными с настоящим изобретением. Настоящее изобретение может также принимать во внимание изменяющиеся во времени сигналы и сигналы, излучаемые от подвижных платформ. Чувствительные к рельефу местности модели распространения также могут использоваться, чтобы принимать во внимание изменения в сигналах вследствие препятствий рельефа местности. Аналогично, другие модели распространения могут использоваться, чтобы принимать во внимание такое, как отражения от больших структур, таких как здания, памятники и искусственные объекты и подобное. Используя модели прогнозирования скорости, настоящее изобретение также может использоваться для определения скорости устройства, а также его местоположения.

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

На Фиг.19 показана другая схема последовательности операций способа 1900 для определения местоположения устройства в соответствии с аспектом настоящего изобретения. Способ 1900 начинает этап 1902, получая внешние сигналы, например сигналы радиочастоты ЧМ от таких источников, как, например, радиомачты коммерческого радиовещания ЧМ и/или станции 1904. Затем осуществляют сканирование 1906 ряда радиочастот и определяют 1908 векторы измеренных уровней сигналов. Затем сортируют относительные уровни и вычисляют вектор ранжирования для частот 1910. Затем генерируют хэш-коды на основании перестановок уровней 1912 сигналов. Затем от каждого требуемого местоположения получают хэш-коды, чтобы обучить систему 1914 определения местоположения. Затем создают нормированные гистограммы по хэш-кодам 1916. Затем вычисляют вероятность посредством, например, правила 1918 Байеса. Затем используют классификатор, такой как, например, байесовский классификатор, чтобы идентифицировать максимальное значение апостериорной вероятности, указывающей, какое устройство наиболее вероятно находится в этом конкретном местоположении 1920, завершая последовательность 1922.

На Фиг.20 проиллюстрирована схема последовательности операций способа 2000 для обучения устройства определения местоположения в соответствии с аспектом настоящего изобретения. Способ 2000 начинает этап 2002 определения местоположения устройства, которое принимает внешние сигналы в конкретном местоположении 2004. Внешние сигналы, такие как сигналы радиочастоты и подобные, сканируют многократно каждый, чтобы получить их уровни 2006 сигналов. Затем вычисляют информацию о ранжировании, такую как хэш-коды ранжирования и подобную, для каждого сканирования 2008. Нормированную гистограмму информации о ранжировании, например хэш-коды ранжирования, генерируют для конкретного местоположения и сохраняют 2010. Затем выполняют определение относительно того, требует ли другое местоположение получения данных от 2012. Если да, то устройство транспортируют к другому местоположению 2004 и вновь выполняют способ 2000. Если более местоположений не требуется, то завершают последовательность 2014.

На Фиг.21 показана схема последовательности операций способа 2100 сглаживания гистограмм, используемого для определения местоположения устройства в соответствии с аспектом настоящего изобретения. Способ 2100 начинает этап 2102 вычисления гистограмм ячеек крупной сетки на основании нижележащих ячеек 2104 мелкой сетки. Посредством использования крупной сетки вместо мелкой сетки, предоставляемой программным обеспечением имитационного моделирования, например ComStudy и подобным, получают приемлемую разрешающую способность без того, чтобы вызывать значительные накладные расходы хранения и обработки данных на нижележащем устройстве. Затем нормируют 2106 гистограммы ячеек крупной сетки. Это обеспечивает оценку распределения вероятностей хэш-кодов ранжирования для ячейки. Затем выбирают 2108 пороговое значение корреляции. Это позволяет осуществить управление сглаживанием разреженно заполненных гистограмм, задавая большее сглаживание при более высоких значениях. Затем определяют 2110 дискретные элементы гистограммы, имеющие коэффициенты корреляции Spearman'а выше порогового значения корреляции. Вычисляют 2112 максимальное значение по всем тем дискретным элементам гистограмм, которые превышают пороговое значение корреляции. Значение каждого дискретного элемента гистограммы, которое выше значения порога корреляции, заменяют максимальным значением 2114, завершая последовательность 2116. В форме уравнения сглаженную вероятность вычисляют как:

(3)

при этом S(r,r') является коэффициентом корреляции Spearman'а между векторами ранжирования, представленными хэш-кодами ранжирования r и r'. Затем нормируют по r в , чтобы задать функцию сглаженного правдоподобия для хэш-кода ранжирования заданной крупной ячейке.

На Фиг.22 изображена схема последовательности операций способа 2200 для сглаживания логически выводимого местоположения в соответствии с аспектом настоящего изобретения. Способ 2200 начинает этап 2202 получением предыстории сканирований 2204 уровней сигналов. Затем выбирают 2206 сглаживающее значение "K" (размер временного окна) вывода местоположения. Затем по последним "K" сканированиям уровней сигналов определяют 2208 наиболее часто логически выводимое местоположение, завершая последовательность 2210. Наиболее часто логически выводимое местоположение становится местоположением, используемым для нижележащего устройства. Это обычно делают, чтобы предотвратить устройство от "скачка" от местоположения к местоположению вследствие перемещения ориентации устройства и других влияний внешней среды. Посредством сглаживания логически выведенного местоположения устройство показывает существенно стабильное (установившееся) значение.

На Фиг.23 показана схема последовательности операций способа 2300 оптимизации наборов внешних сигналов для использования при определении местоположения устройства в соответствии с аспектом настоящего изобретения. Способ 2300 начинает этап 2302 получением набора внешних сигналов и их соответствующих уровней 2304 сигналов. Затем вычисляют коэффициент корреляции Пирсона между всеми парами источников сигналов из набора 2306. В одном примере настоящего изобретения составление пар источников сигналов основано на пространственно соответствующих точках на карте моделируемых уровней сигналов и подобном. Коэффициент корреляции Пирсона представляет коэффициент стандартной линейной корреляции, а не ранговой корреляции. Затем выбирают 2308 пороговое значение корреляции. Обычным значением для порога корреляции в одном примере настоящего изобретения является приближенно 0,95. Источники сигнала, которые являются коррелированными в большей степени, чем выбранное пороговое значение корреляции, группируют вместе 2310. Затем для каждой группы выбирают сигнал с наивысшим средним уровнем сигналов, чтобы представить данную группу 2312, завершая последовательность 2314. Данный способ 2300 сокращает количество векторов ранжирования, подлежащих использованию при определении местоположения устройства, на несколько порядков величины. Способ 2300 также особенно полезен тогда, когда внешние сигналы исходят от одиночного источника, устраняя избыточность источников.

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

Для обеспечения дополнительного контекста для осуществления различных аспектов настоящего изобретения представлены Фиг.24 и нижеследующее краткое, общее описание подходящей вычислительной среды 2400, в которой могут быть осуществлены различные аспекты настоящего изобретения. Тогда как изобретение было описано выше в общем контексте машиноисполнимых инструкций компьютерной программы, которую исполняют на локальном компьютере и/или удаленном компьютере, специалисты в данной области техники признают, что изобретение также может быть осуществлено в комбинации с другими программными модулями. В целом, программные модули включают в себя процедуры, программы, компоненты, структуры данных и т.д., которые выполняют конкретные задачи и/или осуществляют особые абстрактные типы данных. Более того, специалистам в данной области техники ясно, что методика изобретения может быть осуществлена с помощью других конфигураций вычислительной системы, включая однопроцессорные или многопроцессорные вычислительные системы, мини-компьютеры, мейнфреймы (большие ЭВМ), а также персональные компьютеры, переносные или портативные вычислительные устройства, микропроцессорную и/или программируемую бытовую электронику и т.п., каждое из которых может оперативно обмениваться информацией с одним или несколькими связанными устройствами. Иллюстрированные аспекты изобретения также могут быть осуществлены на практике в распределенных вычислительных средах, в которых некоторые задачи выполняют посредством устройств удаленной обработки, которые связаны посредством сети связи. Однако некоторые, если не все, аспекты изобретения могут быть осуществлены на практике на автономных компьютерах. В распределенной вычислительной среде программные модули могут быть размещены на локальных и/или удаленных устройствах хранения данных.

Используемый в данной заявке термин "компонент" предназначен, чтобы ссылаться на связанный с компьютером элемент либо аппаратных средств, комбинации аппаратных средств и программного обеспечения, программного обеспечения, либо программного обеспечения во время исполнения. Например, компонент может быть, но не ограничен таковыми: процессом, исполняющимся на процессоре, процессором, объектом, исполняемым файлом, потоком (подпроцессом) управления, программой и компьютером. В качестве иллюстрации приложение, исполняющееся на сервере, и/или сервер могут быть компонентами. В дополнение, компонент может включать в себя один или несколько компонентов.

При ссылке на Фиг.24 примерная среда 2400 системы для осуществления различных аспектов настоящего изобретения включает в себя обычный компьютер 2402, включая блок 2404 обработки, или процессор, системное запоминающее устройство 2406 и системную шину 2408, которая связывает различные системные компоненты, включая системное запоминающее устройство, с блоком 2404 обработки. Блок 2404 обработки может быть любым коммерчески доступным или разработанным самой фирмой процессором. В дополнение, блок обработки может быть осуществлен многопроцессорным, образованным из нескольких процессоров, например, возможно соединенных параллельно.

Системная шина 2408 может быть произвольного типа из нескольких типов шинных архитектур, включая шину памяти или контроллер памяти, периферийную шину и локальную шину, использующую произвольную архитектуру из множества обычных шинных архитектур, например шины PCI (PCI), локальную шину стандарта VESA (VESA), шину MicroChannel, шину промышленного стандарта ISA (ISA) и расширенную ISA (EISA). Системное запоминающее устройство 2406 включает в себя постоянное запоминающее устройство (ПЗУ, ROM) 2410 и оперативное запоминающее устройство (ОЗУ, RAM) 2412. Базовая система ввода-вывода (BIOS) 2414, содержащая основные программы, которые помогают передавать информацию между элементами компьютера 2402, например, в течение запуска, хранится в ОЗУ 2410.

Компьютер 2402 также может включать в себя, например, дисковод 2416 накопителя на жестких дисках, дисковод 2418 магнитного диска, например, для считывания со сменного диска 2420 или записи на сменный диск 2420 и накопитель 2422 на оптических дисках, например, для считывания с компакт-диска 2424 или записи на компакт-диск (КД-ОЗУ, CD-ROM) или другой оптический носитель. Дисковод 2416 накопителя на жестких дисках, дисковод 2418 магнитного диска и накопитель 2422 на оптических дисках связаны с системной шиной 2408 посредством интерфейса 2426 накопителя на жестких дисках, интерфейса 2428 дисковода магнитного диска и интерфейса 2430 накопителя на оптических дисках, соответственно. Накопители на дисках 2416-2422 и ассоциированные с ними машиночитаемые носители обеспечивают энергонезависимое хранилище данных, структур данных, машиноисполнимых инструкций и т.д. для компьютера 2402. Хотя вышеуказанное описание машиночитаемых носителей ссылается на накопитель на жестких дисках, сменный магнитный диск и компакт-диск, специалисты в данной области техники должны оценить, что другие типы носителей, которые являются машиночитаемыми, такие как магнитные кассеты, карты флэш-памяти, цифровые видео диски, картриджи Bernoulli и т.п., также могут быть использованы в примерной операционной среде 2400, и, кроме того, любые подобные носители могут содержать машиноисполнимые инструкции для выполнения настоящего изобретения.

Некоторое количество программных модулей может быть сохранено на накопителях на дисках 2416-2422 и в ОЗУ 2412, включая операционную систему 2432, одну или несколько прикладных программ 2434, другие программные модули 2436 и программные данные 2438. Операционная система 2432 может быть любой подходящей операционной системой или комбинацией операционных систем. В качестве примера прикладные программы 2434 и программные модули 2436 могут включать в себя логический вывод местоположения устройства в соответствии с аспектом настоящего изобретения.

Пользователь может вводить команды и информацию в компьютер 2402 посредством одного или нескольких пользовательских устройств ввода данных, таких как клавиатура 2440 и указывающее устройство (например, мышь 2442). Другие устройства ввода данных (не показаны) могут включать в себя микрофон, джойстик, игровую панель, спутниковую антенну, удаленное радиовещание, сканер или подобное. Эти и другие устройства ввода данных обычно связаны с блоком 2404 обработки посредством интерфейса 2444 последовательного порта, соединенного с системной шиной 2408, но могут быть связаны посредством других интерфейсов, таких как параллельный порт, игровой порт или универсальная последовательная шина (USB). Монитор 2446 или другой тип устройства отображения также соединен с системной шиной 2408 посредством интерфейса, такого как видеоадаптер 2448. В дополнение к монитору 2446 компьютер 2402 может включать в себя другие периферийные устройства вывода данных (не показаны), таких как динамики, принтеры и т.д.

Должно быть оценено, что компьютер 2402 может функционировать в сетевой среде, используя логические соединения с одним или несколькими удаленными компьютерами 2460. Удаленный компьютер 2460 может быть рабочей станцией, серверным компьютером, маршрутизатором, устройством равноправного узла сети или другим узлом сети общего пользования и обычно включает многие или все из элементов, описанных относительно компьютера 2402, хотя для целей краткости только запоминающее устройство 2462 проиллюстрировано на Фиг.24. Логические соединения, изображенные на Фиг.24, могут включать в себя локальную сеть (ЛС, LAN) 2464 и глобальную сеть (ГС, WAN) 2466. Подобные сетевые среды являются обычными в учреждениях, сетях масштаба предприятия, внутренних сетях и Интернет.

При использовании в сетевой среде LAN, например компьютер 2402, соединен с локальной сетью 2464 посредством сетевого интерфейса или адаптера 2468. При использовании в сетевой среде WAN компьютер 2402 обычно включает в себя модем (например, телефонный, цифровой абонентской линии (ЦАЛ, DSL), кабельный и т.д.) 2470, или является соединенным с сервером системы связи по LAN, или имеет другое средство для установления связи по WAN 2466, как, например, Интернет. Модем 2470, который может быть внутренним или внешним относительно компьютера 2402, соединен с системной шиной 2408 через интерфейс последовательного порта 2444. В сетевой среде программные модули (включая прикладные программы 2434) и/или программные данные 2438 могут сохраняться на удаленном запоминающем устройстве 2462. Очевидно, что показанные сетевые соединения являются иллюстративным примером, и другие средства (например, проводные или беспроводные) установления линии связи между компьютерами 2402 и 2460 могут быть использованы при выполнении аспекта настоящего изобретения.

В соответствии с инструкциями для специалистов в области техники программирования компьютера настоящее изобретение было описано с помощью ссылки на действия и символические представления операций, которые выполняет компьютер, такой как компьютер 2402 или удаленный компьютер 2460, если не обозначено иное. Такие действия и операции иногда называют «являющиеся машиноисполнимыми». Будет оценено, что действия и символически представленные операции включают в себя манипулирование блоком 2404 обработки электрическими сигналами, представляющими биты данных, которое вызывает результирующее преобразование или предварительную обработку представления электрического сигнала, и поддержание битов данных в ячейках запоминающего устройства в запоминающей системе (включая системное запоминающее устройство 2406, накопитель 2416 на жестких дисках, гибкие диски 2420, КД-ПЗУ 2424 и удаленное запоминающее устройство 2462), чтобы таким образом повторно настраивать или иным образом изменять функционирование вычислительной системы, а также другую обработку сигналов. Ячейки запоминающего устройства, в которых такие биты данных поддерживают, являются физическими местоположениями, которые имеют конкретные электрические, магнитные или оптические свойства, соответствующие битам данных.

На Фиг.25 показана другая блок-схема примера вычислительной среды 2500, с которой может взаимодействовать настоящее изобретение. Система 2500 дополнительно иллюстрирует систему, которая включает в себя один или несколько клиентских блоков, или клиентов 2502. Клиент(ы) 2502 может быть аппаратным и/или программным (например, потоками, процессами, вычислительными устройствами). Система 2500 также включает в себя один или несколько серверов 2504. Сервер(ы) 2504 также может быть аппаратным и/или программным (например, потоками, процессами, вычислительными устройствами). Сервер(ы) 2504 может содержать потоки для выполнения преобразований посредством использования настоящего изобретения, например. Одна (из) возможных передач информации между клиентом 2502 и сервером 2504 может быть в форме пакета данных, приспособленного для передачи между двумя или несколькими вычислительными процессами. Система 2500 включает в себя структуру 2508 передачи информации, которая может быть использована, чтобы способствовать обмену сообщениями между клиентом(ами) 2502 и сервером(ами) 2504. Клиент(ы) 2502 оперативно соединен(ы) с одним или несколькими клиентскими хранилищами 2510 данных, которые могут использоваться, чтобы хранить информацию, локальную для клиента(ов) 2502. Подобным образом сервер(ы) 2504 оперативно соединен(ы) с одним или несколькими серверными хранилищами 2506 данных, которые могут использоваться, чтобы хранить информацию, локальную для сервера(ов) 2504.

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

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

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

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

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

То, что было описано выше, включает в себя примеры настоящего изобретения. Конечно, не представляется возможным описать каждую потенциальную комбинацию компонентов или методик для целей описания настоящего изобретения, но средний специалист в данной области техники может признать, что возможны многие дополнительные комбинации и изменения настоящего изобретения. Соответственно, настоящее изобретение предназначено, чтобы охватить все такие изменения, модификации и разновидности, которые подпадают под существо и объем прилагаемой формулы изобретения. Кроме того, в той мере, в которой термин "включает в себя" использован либо в подробном описании, либо в формуле изобретения, такой термин предназначен быть «включающим» таким образом, который сходен с термином "содержащий" так, как "содержащий" интерпретируют при использовании в качестве промежуточного слова в формуле изобретения.

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

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

3. Способ по п.2, отличающийся тем, что вектор ранжирования вычисляют на основании программы сортировки.

4. Способ по п.2, дополнительно заключающийся в том, что используют способ сглаживания по меньшей мере по одной гистограмме.

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

6. Способ по п.5, отличающийся тем, что пороговое значение корреляции является приближенно равным 0,9.

7. Способ по п.5, отличающийся тем, что информацию ячейки мелкой сетки получают от компонента моделирования уровня внешнего сигнала.

8. Способ по п.7, отличающийся тем, что компонент моделирования уровня внешнего сигнала содержит программу ComStudy компании RadioSoft.

9. Способ по п.5, отличающийся тем, что информацию ячейки мелкой сетки получают на основании транспортирования устройства к каждой представляющей интерес ячейке мелкой сетки.

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

11. Способ по п.10, отличающийся тем, что оптимизация поднабора уровней внешних сигналов заключается в том, что:
вычисляют по меньшей мере один коэффициент корреляции Пирсона (Pearson) между парами внешних сигналов на основании пространственно соответствующих источников сигналов;
выбирают пороговое значение, р_s корреляции, чтобы способствовать оптимизации поднабора уровней внешних сигналов;
определяют группы сигналов, которые коррелированны в большей степени, чем пороговое значение корреляции; и
выбирают внешний сигнал из каждой группы с наивысшим средним значением уровня сигнала, чтобы представлять данную группу в определении приближенного местоположения устройства.

12. Способ по п.11, отличающийся тем, что пороговое значение корреляции является приближенно равным 0,95.

13. Способ по п.1, дополнительно заключающийся в том, что:
сохраняют приближенное местоположение устройства в допускающем извлечение пространстве;
выбирают изменяемое сглаживающее значение для представляющих местоположение устройства данных из набора предшествующих сканирований уровней сигналов; и
используют местоположения, наиболее часто логически выводимые на основании набора предшествующих сканирований уровней сигналов, в качестве приближенного местоположения устройства на данный момент времени.

14. Способ по п.13, отличающийся тем, что изменяемое значение сглаживания содержит временное окно К, представляющее количество сканирований сигналов за промежуток времени.

15. Способ по п.1, отличающийся тем, что определение местоположения дополнительно заключается в том, что:
аппроксимируют дискретное распределение вероятностей для информации об уровне сигнала, полученной из конкретного местоположения.

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

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

18. Способ по п.17, отличающийся тем, что информация ранжирования содержит хэш-коды ранжирования.

19. Способ по п.1, отличающийся тем, что уровни внешних сигналов содержат уровни сигналов радиочастоты (РЧ).

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

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

22. Способ по п.21, отличающийся тем, что пользовательское ограничение содержит по меньшей мере одну географическую зону.

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

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

25. Способ по п.24, дополнительно заключающийся в том, что:
используют статистические классификаторы, чтобы способствовать корректированию релевантных характеристик моделирования уровня сигнала.

26. Способ по п.25, отличающийся тем, что релевантные характеристики содержат по меньшей мере одну, выбранную из группы, состоящей из: надежности, смещений между фактическими воспринятыми уровнями сигналов и моделируемыми значениями, и поведением в отношении топологических особенностей и структур.

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

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

29. Способ по п.28, дополнительно заключающийся в том, что:
используют последний известный доверительный логический вывод в качестве приближенного местоположения устройства, если промежуток времени после последнего известного доверительного логического вывода меньше порогового значения промежутка времени.

30. Устройство определения местоположения, содержащее, в том числе, компьютер, выполняющий функции, реализующие этапы способа по п.1.