АДАПТИВНОЕ ОПРЕДЕЛЕНИЕ ПОЗИЦИИ
ADAPTIVE POSITIONING

Уровень техники
[0001] Оценка местоположения используется мобильными устройствами обработки, чтобы устанавливать позицию устройства, и представляет собой признак, который является полезным для некоторого числа приложений на устройстве. Технологии оценки местоположения могут использовать любое число различных способов, чтобы вычислять позицию. Хотя спутниковые системы, такие как глобальная навигационная спутниковая система (GNSS), могут помогать в определении позиций, использование Wi-Fi-радиомаяков в технологиях вычислений может обеспечить более точную привязку позиции и/или обеспечить привязки позиции в областях, в которых спутниковые системы не являются доступными. Позиция мобильного вычислительного устройства может оцениваться посредством использования интенсивности радиосигнала из радиомаяка. Однако, непрогнозируемость распространения сигнала через окружения в помещениях является сложностью в определении привязки позиции. Может быть затруднительным обеспечить соответствующую статистическую модель измерений интенсивности сигнала. Некоторые разработки акцентируют внимание на технологиях, которые могут формировать точную эмпирическую модель из обучающих данных, собранных в зоне испытания, и оценку в реальном времени для мобильных устройств обработки. Точность таких подходов, по меньшей мере, частично зависит от числа позиций, которые известны для алгоритма позиционирования. Тем не менее, возможные флуктуации сигналов, которые могут возникать, могут увеличивать ошибки и неточности в тракте пользователя. В зависимости от позиции устройства, один способ вычисления может превосходить другие в обеспечении точности позиционирования.
Сущность изобретения
[0002] Обеспечена технология для вычисления позиции в ответ на запрос позиции. Запрос позиции может включать в себя наблюдаемые данные радиомаяков, ассоциированные с запросом, и на которых частично должно быть основано вычисление. В ответ на запрос на вычисление позиции, проводится выбор между алгоритмами позиционирования и потенциально отличающимися источниками и моделями данных. Выбор моделей данных и алгоритмов зависит от ряда факторов, включающих в себя характеристики устройства, выполняющего обработку, число наблюдаемых радиомаяков и доступность данных, чтобы разрешать позицию в публичном месте.
[0003] Данная сущность изобретения предоставлена для того, чтобы представлять в упрощенной форме выбор концепций, которые дополнительно описаны ниже в подробном описании. Эта сущность не имеет намерение идентифицировать ключевые или важнейшие признаки заявленного предмета изобретения, а также не имеет намерение использоваться в качестве помощи при определении объема заявленного предмета изобретения.
Краткое описание чертежей
[0004] Фиг. 1 является блок-схемой, иллюстрирующей мобильные вычислительные устройства относительно беспроводных радиомаяков, используемых для вычислений позиции.
[0005] Фиг. 2 является покомпонентным видом в перспективе позиции в закрытом помещении с множеством беспроводных радиомаяков.
[0006] Фиг. 3 является блок-схемой последовательности операций, представляющей способ в соответствии с настоящей технологией для того, чтобы определять позицию с использованием выбранного способа.
[0007] Фиг. 4 является блок-схемой последовательности операций способа, иллюстрирующей этап выбора самого точного способа вычисления.
[0008] Фиг. 5 является блок-схемой последовательности операций способа, иллюстрирующей создание моделей данных для способа по фиг. 3.
[0009] Фиг. 6 является блок-схемой последовательности операций способа, иллюстрирующей выбор этажа на основе интервала признаков голосования.
[0010] Фиг. 7 является блок-схемой, иллюстрирующей сценарии вычисления позиции с использованием EZ-алгоритма.
[0011] Фиг. 8 является таблицей, иллюстрирующей первую AP-модель.
[0012] Фиг. 9 является таблицей, иллюстрирующей гибридную AP-модель.
[0013] Фиг. 10 является таблицей, иллюстрирующей интервальные данные признаков голосования.
[0014] Фиг. 11 является примерным ответом на запрос на получение местоположения с использованием цифрового отпечатка (GLUF), представленный в XML.
[0015] Фиг. 12 является блок-схемой функционального представления первого устройства обработки и вычислительного устройства.
[0016] Фиг. 13 является блок-схемой функционального представления второго устройства обработки и вычислительного устройства.
[0017] Фиг. 14 является блок-схемой системы обработки.
Подробное описание изобретения
[0018] Обеспечена технология для определения или вычисления позиции в ответ на запрос позиции. Запрос позиции может включать в себя наблюдаемые данные радиомаяков, ассоциированные с запросом, и на которых частично должно быть основано вычисление. В ответ на запрос на вычисление позиции, проводится выбор между альтернативными алгоритмами позиционирования и потенциально отличающимися источниками и моделями данных. Посредством обеспечения определенного числа различных алгоритмов, возникает оптимальный способ вычисления позиции на основе наблюдаемых данных в запросе позиции.
[0019] В соответствии с этой технологией, система вычисления позиции использует один, по меньшей мере, из двух алгоритмов и двух моделей данных, чтобы вычислять позицию, на основе которой алгоритм обеспечивает более точное вычисление позиции. Выбор моделей данных и алгоритмов зависит от ряда факторов, включающих в себя характеристики устройства, выполняющего обработку, число наблюдаемых радиомаяков и доступность данных, чтобы разрешать позицию в публичном месте. В раскрытии сущности в данном документе, используемые радиомаяки могут представлять собой точки доступа по стандарту высококачественной беспроводной связи (Wi-Fi), имеющие один или более идентификаторов базовых наборов служб (BSSID). (Следует отметить, что одна физическая точка доступа может быть выполнена с возможностью поддерживать несколько BSSID.)
[0020] Первый тип алгоритма использует данные, состоящие из цифровых отпечатков точек Wi-Fi-доступа и GPS-привязок позиции на основе двумерной модели на базе точек доступа. Двумерная модель включает в себя долготу и широту различных точек доступа, имеющих известные позиции. Хранилище двумерных данных позиций точки доступа поддерживается с позициями всех точек Wi-Fi-доступа в модели, обеспеченной в приблизительном центре всех наблюдаемых местоположений. Таким образом, позиция, ассоциированная с точкой доступа, содержит наиболее статистически вероятную позицию обнаруженной точки доступа, а не место, в котором может на самом деле находиться точка доступа. Используя обнаружения радиомаяков, несколько измерений комбинируются во время вычисления позиции в ответ на запрос позиции, чтобы вычислять позицию и радиус ошибки. Этот способ альтернативно упоминается в данном документе как создание "логически выведенной" позиции. Этот первый способ является менее чувствительным к характеристикам RF-окружения, поскольку RF-окружение влияет только на то, может или нет наблюдаться радиомаяк, и является эффективным, когда плотность радиомаяков является низкой. Первый способ хорошо работает в окружениях с более высокой плотностью с прогнозируемыми RF-характеристиками, тем не менее, второй алгоритм позиционирования, описанный ниже, обеспечивает статистически лучшие результаты позиционирования в таких окружениях с более высокой плотностью.
[0021] Второй алгоритм позиционирования использует трехмерные цифровые Wi-Fi-отпечатки на основе наблюдений на основе радиомаяков, состоящих из цифровых Wi-Fi-отпечатков, публичного места, этажа и предоставляемых пользователем экспериментально полученных проверочных данных относительно известной позиции. Обеспечено хранилище трехмерных данных, в котором может быть обеспечена модель на базе точек доступа, имеющая характеристики широты, долготы, публичного места и этажей публичного места. Модель позиционирует точки Wi-Fi-доступа в местах, в которых точки доступа предположительно расположены, с использованием интенсивности сигнала для того, чтобы ранжировать позицию. Чтобы вычислять позицию, алгоритм позиционирования позиционирует устройство с использованием трилатерации, с использованием интенсивности сигнала для того, чтобы определять расстояние от опубликованных точек доступа в трехмерном хранилище. Усиление приемного устройства в устройстве автоматически определяется, и четыре наблюдаемые точки Wi-Fi-доступа используются, чтобы вычислять позицию. Модель обнаружения этажей на основе распределения интенсивности сигнала используется, чтобы определять этаж из цифрового Wi-Fi-отпечатка. Эта система вычисления является преимущественной, когда RF-окружение является более прогнозируемым (т.е. приблизительно соответствует кривой потерь в тракте распространения), и когда плотность радиомаяков является высокой.
[0022] В контексте этого раскрытия сущности, вычисленная позиция может включать в себя широту, долготу и другую логическую информацию местоположения, такую как идентификатор публичного места и идентификатор этажа в публичном месте.
[0023] Фиг. 1 иллюстрирует примерный контекст, в котором может быть использована технология, описанная в данном документе. Фиг. 1 иллюстрирует блок-схему множества мобильных вычислительных устройств 102, 104, которые используют один или более радиомаяков 110a-110d или других узлов 120a, 120b сотовой связи, чтобы вычислять позицию для мобильного устройства. Мобильные вычислительные устройства 102, 104 наблюдают или иным способом обнаруживают один или более радиомаяков 110, 120 и используют сигналы из этих радиомаяков, чтобы вычислять позицию. Примерные радиомаяки включают в себя вышки сотовой связи, базовые станции, базовые приемо-передающие станции, узлы базовых станций и/или любые другие сетевые элементы, поддерживающие любое количество и тип режима вакации. Типично, радиомаяки 110a-110d представляют Wi-Fi-радиомаяки, которые имеют известные свойства распространения и сигналы, которые обеспечивают информацию, чтобы обеспечивать возможность, например, мобильным устройствам вычислять позиции в областях, в которых другие типы сигналов не могут присутствовать, таких как внутренняя часть зданий и т.п. Каждое из мобильных вычислительных устройств 102, 104, может сохранять свойства для каждого радиомаяка 110, 120. В некоторых вариантах осуществления, примерные свойства включают в себя широту и долготу наблюдающего мобильного вычислительного устройства и время наблюдения. Во внутренних позициях, таких как публичное место, наблюдения могут включать в себя более детализированную информацию, такую как позиция этажа.
[0024] Каждое мобильное вычислительное устройство может само выполнять вычисление позиции или может предоставлять информацию в службу 125 определения местоположения через сеть 50, при этом служба 125 определения местоположения возвращает вычисленную позицию устройства устройству. Каждое вычисление позиции может использовать фильтр Калмана (или другие способы) для цифрового отпечатка радиомаяков (например, набора радиомаяков, наблюдаемых посредством вычислительного устройства), чтобы формировать логически выведенную позицию устройства. Также может вычисляться радиус ошибки. Радиус ошибки может отражаться в качестве окружности, имеющей оцененный радиус ошибки устройства в качестве радиуса. Как результат, если конкретный радиомаяк обнаруживается с данным доверительным уровнем, может формироваться логически выведенная позиция устройства, которая находится в пределах окружности с центром в оцененной позиции радиомаяка с оцененным радиусом радиомаяка, как проиллюстрировано на 418 по фиг. 12.
[0025] Служба 125 определения местоположения, которая может выполнять вычисление позиции на основе наблюдений мобильного вычислительного устройства (102, 104), доступных исследований позиции и других данных, которые собираются и сохраняются в службе 125 определения местоположения. В некоторых вариантах осуществления, служба 125 определения местоположения может собирать данные из множества различных мобильных вычислительных устройств, а также наблюдения радиомаяков относительно известных фактических позиций, упоминаемые в данном документе в качестве экспериментально полученных проверочных данных. Мобильные вычислительные устройства 102, 104 могут отправлять свойства наблюдаемых позиций и радиомаяков, наблюдаемых в различных позициях, в службу определения местоположения через сеть 50. Служба 125 определения местоположения может управлять одним или более вычислительных устройств, как проиллюстрировано в данном документе, чтобы обеспечивать услуги определения позиции для мобильных устройств обработки через сеть 50.
[0026] Вычисленная или логически выведенная позиция может как включать в себя позицию, так и иметь ассоциированный радиус ошибки. Радиус ошибки является отражением неопределенности или ошибки, которая может присутствовать в вычислении позиции. Иллюстрация радиуса ошибки, отображаемого посредством картографического приложения с использованием вычисленной позиции, приведена на фиг. 12. В общем, радиус ошибки представляет область, окружающую вычисленную позицию, которая указывает пользователю вычисленной позиции относительную точность вычисления.
[0027] Наблюдения могут использоваться в сочетании с GPS-службами, чтобы определять позицию. В некоторых случаях, GPS-данные недоступны. Когда мобильное вычислительное устройство присутствует во внутренней части публичного места-здания, доступ к GPS-данным, в общем, трудно принимать. Следовательно, использование Wi-Fi или другой информации может давать в результате более точные данные логически выведенных позиций.
[0028] Фиг. 2 иллюстрирует покомпонентный вид в перспективе публичного места 200, имеющего множество Wi-Fi-радиомаяков, позиционированных в районе внутренней части конструкции. Публичное место 200, например, может представлять собой торговый центр, школу, офисное здание, аэропорт или другое здание, в котором доступ к GPS-данным не является легкодоступным. Фиг. 2 иллюстрирует первый этаж 210 и второй этаж 212 публичного места 200. Множество стен 220 разделяет различные помещения 225 в публичном месте 200. Радиомаяки 110 позиционируются по обоим этажам в публичном месте 200. Устройство обработки может использовать свойства радиомаяков в публичном месте 200, чтобы вычислять позицию устройства обработки. Обычно, вычисленные позиции возвращаются в приложения, которые используют вычисленную позицию, чтобы предоставлять информацию пользователю. Хотя имеется определенное число различных типов приложений для определения местоположения, картографическое приложение представляет собой типичное использование вычисленной позиции.
[0029] Локальное позиционирование может выполняться с использованием множества различных свойств. Некоторые способы используют физические свойства сигнала, в то время как другие используют время, потраченное для достижения сигналом узла назначения. Некоторые стандартные способы позиционирования включают в себя способы беспроводного позиционирования на основе угла поступления сигналов, идентификатора соты, времени поступления сигналов, разности времен поступления сигналов и мощности. Один стандартный подход использует исследование информации интенсивности сигнала в конкретной области. Эта информация формирует базу данных, описывающую цифровой отпечаток интенсивности сигналов этой области. База данных впоследствии используется, чтобы определять позицию мобильного устройства посредством конкретного алгоритма сопоставления с шаблоном. Другой подход на базе беспроводного позиционирования на основе мощности использует модель потерь в тракте передачи, чтобы оценивать взаимосвязь между интенсивностью сигнала и расстоянием от передающих устройств. Оцененные расстояния от трех или более передающих устройств используются, чтобы трилатерировать конечную позицию устройства. Хотя конкретные способы и алгоритмы позиционирования описываются в данном документе, настоящая технология может включать любое число различных способов вычисления позиции в сочетании с идеями технологии.
[0030] Фиг. 3 является блок-схемой последовательности операций, иллюстрирующей способ в соответствии с настоящей технологией, чтобы определять вычисленную позицию. В одном контексте позиция вычисляется в ответ на запрос позиции. Запрос позиции может формироваться, например, посредством мобильного устройства обработки, нацеленного на определение вычисленной позиции для одного или более привязанных к местоположению приложений на мобильном устройстве обработки. Способ может осуществляться полностью или частично исключительно на мобильном устройстве обработки либо в связи и во взаимодействии со службой 125 определения местоположения.
[0031] На этапе 320 информация радиомаяка публичного места получается для одного или более публичных мест. Публичное место может представлять собой местоположение с физическими объектами, такими как здание, либо любое местоположение, в котором расположены один или более радиомаяков "точек доступа" (AP). Информация публичного места может получаться в результате исследования позиции, в течение которого собирается информация, содержащая цифровые отпечатки радиомаяков позиций радиомаяков, которые обнаруживаются в публичном месте. Радиомаяки могут обнаруживаться посредством мобильного вычислительного устройства 102, 104, в данный момент времени представляют наблюдения позиции и включают в себя цифровой отпечаток радиомаяка. Цифровой отпечаток радиомаяка также может включать в себя другие атрибуты обнаружения, такие как интенсивность сигнала и дата и время наблюдения. Один механизм для сбора информации узлов раскрыт в Заявке на патент (США) номер US20140057651A1.
[0032] Обычно, информация исследования позиции может собираться посредством физического исследования узла с использованием мобильного устройства обработки, определения цифрового отпечатка радиомаяка для местоположения и установления набора экспериментально полученных проверочных данных фактических позиций, ассоциированных с цифровыми отпечатками радиомаяков для публичного места. Чтобы устанавливать экспериментально полученные проверочные данные для конкретного публичного места, наблюдаемые данные для публичного места ассоциированы с известными позициями для наблюдаемых данных. Наблюдаемые данные могут быть ассоциированы посредством исследования с использованием известной информации позиции (с точки зрения известной широты, долготы и позиций этажей), которая увязывается на карте с цифровым отпечатком радиомаяка в данное время. Цифровые отпечатки известных радиомаяков в каждом наборе позиций на карте создаются. Корреляция между логически выведенными позициями используется для того, чтобы оценивать точность определения позиции посредством сравнения логически выведенной позиции с экспериментально полученными проверочными данными.
[0033] На этапе 330 и в то время, которое может совпадать либо находиться после получения цифровых отпечатков местоположения на этапе 320, может приниматься запрос на то, чтобы определять позицию. Запрос может приниматься, например, из привязанного к местоположению приложения на мобильном устройстве обработки. Запрос может приниматься посредством вычисления для мобильного устройства обработки или передаваться из мобильного устройства и приниматься посредством службы 125 определения местоположения. Множество таких приложений для определения местоположения на мобильном устройстве обработки могут использовать вычисленные позиции, чтобы обеспечивать информацию и услуги пользователям мобильного устройства обработки. После того, как запрос определения позиции принимается на этапе 330, определение радиомаяков, наблюдаемых посредством мобильного устройства позиционирования, инициирующего запрос, выполняется на этапе 340. Наблюдаемые радиомаяки используются в вычислении позиции устройства относительно цифровых отпечатков позиции. В одном варианте осуществления, запрос на этапе 330 может включать в себя набор наблюдаемых радиомаяков на этапе 340 в качестве части запроса.
[0034] На этапе 350 выполняется определение в отношении того, какой из одного или более альтернативных способов вычисления позиции должен обеспечивать самое точное вычисление позиции на основе ряда факторов. Определение способа, используемого для вычисления позиции, описывается ниже относительно фиг. 4.
[0035] На этапе 360 выбранный способ используется, чтобы вычислять позицию, и вычисленная позиция возвращается в ответ на запрос на этапе 370.
[0036] Фиг. 4 является блок-схемой последовательности операций, иллюстрирующей один способ определения того, какой из множества альтернативных способов обеспечивает наилучшее вычисление позиции на этапе 350 на фиг. 3. В одном варианте осуществления, могут быть использованы два потенциальных способа вычисления. Тем не менее, следует понимать, что число различных типов способов вычисления не обязательно должно быть ограничено.
Дополнительно, настоящая технология является применимой к вычислениям позиционирования в помещениях, и следовательно, может требоваться присутствие достаточного числа радиомаяков публичного места для конкретного способа вычисления.
[0037] Первоначально следует отметить, что способ по умолчанию с использованием алгоритма на основе логического вывода на основе алгоритма Калмана с данными двумерной модели радиомаяков показан на этапе 360A. Способ по 306A по умолчанию используется, чтобы определять вычисленную позицию, если другие более надежные способы позиции не допускают использование, как описано в данном документе. Результат в виде логически выведенной позиции из этого алгоритма обеспечивается на этапе 372. Хотя в одном аспекте алгоритм Калмана используется на этапе 360A, другие способы для вычисления позиции могут использоваться в качестве способа по умолчанию в соответствии с технологией.
[0038] На этапе 344 предпринимается попытка определять публичное место, в котором расположено устройство. Публичное место может определяться, например, на основе порогового значения, по меньшей мере, двух обнаруженных и идентифицированных по публичному месту радиомаяков, присутствующих в наблюдениях, проведенных посредством устройства на этапе 340 выше. В одном варианте осуществления, публичное место верифицируется, если два радиомаяка, имеющие минимальную обнаруженную пороговую интенсивность сигнала, присутствуют в наблюдениях 340. Если обнаружение публичного места не завершается удачно на этапе 346, то способ возвращается к способу вычисления по умолчанию на этапе 360A.
[0039] Если обнаружение публичного места завершается удачно на этапе 346, то предпринимается попытка обнаруживать этаж в публичном месте на этапе 348. В одном варианте осуществления, обнаружение этажей может осуществляться посредством процесса голосования, как пояснено ниже относительно фиг. 6.
[0040] Если обнаружение этажей не завершается удачно, то способ возвращается к способу вычисления по умолчанию на этапе 360A.
[0041] В другой альтернативе обнаружение 355 публичного места и этажей может быть выполнено с использованием этапов 348 и 352 обнаружения этажей. В этой альтернативе обнаружение этажа может включать в себя данные, идентифицирующие публичное место, в котором расположен этаж, так что обнаружение цифрового отпечатка радиомаяка данного этажа, по сути, дает в результате публичное место, в котором этаж расположен.
[0042] Если обнаружение этажей завершается удачно на этапе 352, то один из алгоритма на основе логического вывода с использованием трехмерной гибридной модели на базе точек доступа (AP) на основе публичного места (в 360B) или алгоритма на основе EZ-алгоритма позиционирования с использованием трехмерной AP-модели публичного места (в 360C) может использоваться, чтобы определять вычисленную позицию. EZ-алгоритм подробно описан в работе авторов K. Chintalapudi и V. Padmanabhan, "Indoor Localization Without the Pain", MOBICOM, Association for Computing Machinery, Inc., сентябрь 2010 года (http://research.microsoft.corn/pubs/135721/ez-mobicom.pdf).
[0043] Если обнаружение этажей завершается удачно на этапе 352, первоначально выполняется попытка вычислять позицию с использованием EZ-алгоритма на этапе 360C. Если вычисление завершается удачно на этапе 374, вычисленная позиция решается на этапе 376. Если вычисление не завершается удачно, алгоритм на основе логического вывода с использованием гибридной AP-модели, включающей данные этажей и публичного места, используется для того, чтобы вычислять позицию на этапе 360B. На этапе 378, вычисленная позиция возвращается.
[0044] На этапе 380 проверка когерентности и конфиденциальности может выполняться для вычисленных результатов.
Проверка когерентности и конфиденциальности определяет, согласуется или нет результат с указываемым минимальным стандартом данных. Например, если только один Wi-Fi-радиомаяк найден в наблюдаемых данных, и двумерные данные недоступны для радиомаяка, проверка когерентности должна обеспечивать то, что результат в виде позиции не обеспечивается вследствие проблем конфиденциальности.
[0045] В общем EZ-алгоритм использует допущение, что все наблюдения, сообщаемые из начального исследования, и наблюдения, используемые в вычислении позиции, ограничены посредством базовых физических явлений RF-распространения. EZ-алгоритм моделирует эти ограничения и затем использует их, чтобы определять AP-модель и неизвестные позиции одновременно. Ссылаясь на фиг. 7, допустим, что имеется два пользователя (M1, M2) и две AP (AP1, AP2), и известны все четыре расстояния между AP и пользователем (как показано в сценарии I-A на фиг. 7). На основе этой информации, могут составляться несколько различных четырехугольников, с позициями AP и пользователей в качестве вершин, как проиллюстрировано на сценарии I-A и I-B. Реализация относительных позиций (перемещения в пространстве по модулю, вращения и отражения) AP и пользователей не является уникальной. Тем не менее, можно доказать, что если имеется три AP и три пользователя мобильной связи, может осуществляться только уникальная реализация для относительных позиций AP и пользователей (сценарий II). Это демонстрирует то, что с учетом достаточных ограничений по расстоянию между AP и пользователями мобильной связи, можно уникально определять их позиции в относительном смысле.
[0046] На практике, расстояния между AP и пользователями мобильной связи могут логически выводиться через интенсивность принимаемого сигнала (RSS). Популярная модель, которая связывает расстояние с RSS, задается следующим образом:
[0047] В вышеприведенном уравнении,  является принимаемой RSS для j-ого пользователя мобильной связи из i-ой AP,  является мощностью передачи i-ой AP,  является позицией j-ой AP, является позицией j-ого пользователя мобильной связи,  является экспонентой потерь в тракте передачи около i-ой AP, и  является усилением j-ого мобильного приемного устройства.
[0048] Для каждого RSS-наблюдения получается одно уравнение в вышеуказанной форме. Поскольку большое число наблюдений может собираться из различных местоположений (некоторых известных местоположений, но в основном неизвестных местоположений) для каждого мобильного устройства обработки по мере того, как оно перемещается, в конечном счете, достаточно уравнений (т.е. ограничений) обеспечивается для решения для всех переменных.
[0049] Поскольку решение таких уравнений является нетривиальным, специализированный генетический алгоритм разрабатывается, чтобы решать их. Посредством использования гибридного способа с генетическим алгоритмом и градиентным спуском, нахождение решения становится задачей оптимизации:
[0050] Вышеуказанная задача не имеет известных аналитических решений и имеет большое число локальных минимумов. Чтобы решать вышеуказанное, ограничение на двумерное пространство поиска используется, чтобы разрешать позицию с использованием EZ-алгоритма. Ограничивающий прямоугольник публичного места может использоваться в качестве ограничения. Коммерческие картографические системы, такие как BING Maps, предоставляют метаданные публичных мест, которые могут быть включены в качестве ограничения. Ограничивающий прямоугольник представляет собой набор из двух позиций, которые указывают нижний левый угол и верхний правый угол прямоугольника, который покрывает область публичного места.
[0051] Фиг. 5 иллюстрирует способ для сбора и компоновки двумерного и трехмерного хранилища радиомаяков в соответствии с настоящей технологией. В одном варианте осуществления, фиг. 5 представляет способ для выполнения этапа 320 на фиг. 3. На этапе 510, информация радиомаяка публичного места собирается с использованием любой из ряда известных технологий. Служба 125 определения местоположения может собирать и поддерживать различные хранилища радиомаяков, описанные в данном документе, и может предоставлять все или часть моделей, созданных и описанных в данном документе, в мобильное вычислительное устройство. В некоторых вариантах осуществления, служба 125 определения местоположения может собирать данные из множества различных мобильных вычислительных устройств, а также диспетчеризованных наблюдений радиомаяков относительно известных фактических позиций, упоминаемых в данном документе в качестве экспериментально полученных проверочных данных. Мобильные вычислительные устройства 102, 104 могут передавать наблюдения в службу 125 определения местоположения через сеть 50.
[0052] На этапе 520 хранилище радиомаяков публичного места может быть заполнено с использованием наблюдений на основе радиомаяков относительно позиций из экспериментально полученных проверочных данных. Обычно, информация исследования публичного места может собираться посредством физического исследования узла с использованием мобильного устройства обработки, определения цифрового отпечатка радиомаяка для местоположения и установления набора экспериментально полученных проверочных данных фактических позиций, ассоциированных с цифровыми отпечатками радиомаяков для публичного места. Чтобы устанавливать экспериментально полученные проверочные данные для конкретного радиомаяка, наблюдаемые данные для радиомаяка ассоциированы с известными позициями для наблюдаемых данных. Наблюдаемые данные могут быть ассоциированы посредством исследования с использованием известной информации позиции (с точки зрения известной широты, долготы и позиций этажей), которая увязывается на карте с цифровым отпечатком радиомаяка в данное время. Цифровые отпечатки известных радиомаяков в каждом наборе позиций на карте создаются. Корреляция между логически выведенными позициями используется для того, чтобы оценивать точность определения позиции.
[0053] На этапе 530 AP-модель публичного места создается на основе AP-данных публичного места, собираемых на этапе 510.
[0054] Двумерные (по широте и долготе) наблюдения для AP аналогично могут присутствовать в хранилище данных на этапе 515 для определенного числа публичных мест. Двумерные наблюдения 515 могут включать в себя наблюдения AP со ссылкой на позиционные данные, но без наблюдений этажей, и могут быть ассоциированы или не ассоциированы с публичными местами на основе точности позиционных данных, ассоциированных с AP. Если AP-измерения могут коррелироваться с позициями, двумерная модель может формироваться на этапе 525.
[0055] Как для EZ-алгоритма на этапе 360C, так и для алгоритма на основе логического вывода (по внутреннему алгоритму Калмана) на этапе 360B, используется трехмерная модель публичного места на базе точек доступа. В одном варианте осуществления, трехмерная модель публичного места на базе точек доступа может формироваться посредством мобильного устройства обработки или службы 125 определения местоположения по фиг. 1. Как проиллюстрировано на фиг. 8, трехмерная AP-модель публичного места представляет собой таблицу данных, состоящую из следующих столбцов: BSSID (идентификатор набора базовой службы), широта, долгота, мощность, гамма, VenueId и FloorId.
[0056] Как отмечено выше, если присутствует пороговое число радиомаяков, предпринимается попытка использовать вычисление по EZ-алгоритму на этапе 36°C с использованием трехмерной AP-модели. Если EZ-алгоритм не может логически выводить позицию (на этапе 374), то система должна откатываться к использованию алгоритма на основе логического вывода на этапе 360B для того, чтобы логически выводить позицию. С этой целью, трехмерное хранилище радиомаяков на основе публичного места используется в качестве части AP-модели.
[0057] В соответствии с этой технологией трехмерное хранилище радиомаяков на основе публичного места формируется на этапе 535. Это формирование может выполняться посредством службы 125 определения местоположения. Пример гибридной модели показан на фиг 9. Чтобы добиваться этого, гибридная AP-модель на основе публичного места формируется с использованием EZ-модели для наблюдений в помещениях с использованием идентичных обучающих данных, используемых для того, чтобы формировать AP-модель в помещениях (фиг. 8), и трехмерного хранилища радиомаяков для публичного места. Эта информация объединяется с AP-моделью публичного места, сформированной посредством технологии уточнения данных в помещениях, чтобы создавать гибридную модель в помещениях. EZ-алгоритм используется для того, чтобы находить позицию (широту, долготу), мощность и экспоненту потерь в тракте передачи (гамму) внутренней части AP публичного места. Для цифрового отпечатка, каждый радиомаяк с интенсивностью принимаемого сигнала может записываться в качестве уравнения с позицией (широтой, долготой) в качестве неизвестных. Чтобы разрешать позицию (широту, долготу), по меньшей мере, три (3) радиомаяка используются для трилатерации. Тем не менее, для различных устройств, усиление приемного устройства, которое влияет на интенсивность принимаемого сигнала, также неизвестно. Это добавляет еще одно измерение в решение, и в силу этого, по меньшей мере, еще один радиомаяк в цифровом отпечатке используется для того, чтобы решать уравнения. Следовательно, в одном варианте осуществления, минимальное число радиомаяков в цифровом отпечатке, чтобы разрешать его позицию, составляет четыре радиомаяка. Чтобы компоновать эту гибридную модель, решения неизвестных величин AP основаны на наблюдениях (причем каждое наблюдение представляет собой уравнение с этими неизвестными). Способ для того, чтобы находить решение, представляет собой алгоритм градиентного спуска, который пытается находить решение посредством выполнения поиска различных комбинаций неизвестных в уравнениях, чтобы минимизировать ошибку. Этот EZ-алгоритм формирования является эквивалентом алгоритма позиционирования, используемого на этапе 360C для вычисления позиции, и основан на идентичном принципе.
[0058] Фиг. 6 иллюстрирует способ выполнения этапа 360C. На этапе 610, выполняется начальное определение, чтобы обеспечивать, что, по меньшей мере, два радиомаяка присутствуют. На этапе 620, может выполняться определение определения публичных мест, что два радиомаяка, ассоциированные с публичным местом, найдены в наблюдаемых данных (340) из запроса позиции.
[0059] На этапе 630 извлекается каждый радиомаяк в цифровом отпечатке наблюдения, и обнаружение этажей определяется посредством процесса обнаружения этажей на этапе 640. Этаж может определяться, например, через алгоритм на основе голосования или алгоритм на основе максимального правдоподобия.
[0060] В алгоритме на основе максимального правдоподобия, проводится вычисление статистической вероятности, которое использует метод максимального правдоподобия для оценки смещения усиления приемного устройства для того, чтобы выбирать этаж, и усиление приемного устройства, которое максимизирует вероятность того, что данный этаж "формирует" цифровой Wi-Fi-отпечаток. Чтобы выбирать этаж, способ находит решение для максимальной вероятности согласно следующему:
где:
R является смещением усиления приемного устройства;
floor_i является i-ым этажом;
AP_ij является принимаемой мощностью из AP_j в floor_i (где AP является "точкой доступа"); и
rssi_j является принимаемой мощностью из AP_j в цифровом отпечатке
[0061] В модели на основе голосования каждый радиомаяк в цифровом Wi-Fi-отпечатке из входящего запроса имеет голос для каждого этажа в хранилище радиомаяков в помещениях (по всем публичным местам), и этаж с наибольшим числом голосов побеждает. Победивший этаж также верифицирует публичное место. Если ни один из этажей не принимает голос, то этаж не может определяться, и публичное место не верифицировано. Таким образом, информация этажей/публичного места не может предоставляться в ответе. Модель на основе голосования основана на модели на основе интервалов признаков голосования (VFI), такой как модель, описанная в работе авторов G. Demiroz и H. Guvenir, "Classification by Voting feature Intervals", Proceedings of the 9th European Conference on Machine Learning, стр. 85-92, 1997 год. VFI-модель представляет собой таблицу, содержащую следующую информацию для радиомаяков в публичном месте: Bssid, VenueId, FloorId, IntervalStart, IntervalEnd и весовой коэффициент. Частичная VFI-модель показана на фиг 10. Каждая запись в таблице представляет радиомаяк (Bssid), голос (весовой коэффициент) (между 0 и 1) для FloorId и VenueId, если RSS радиомаяка в цифровом отпечатке попадает в интервал, указываемый посредством IntervalStart и IntervalEnd. Радиомаяк может иметь несколько неперекрывающихся интервалов на идентичном этаже или иметь интервалы для различных этажей. Следовательно, может быть несколько записей в таблице для идентичного радиомаяка.
[0062] На этапе 650 возвращается этаж, определенный посредством любого из вышеописанных способов.
[0063] В одном варианте осуществления служба 125 определения местоположения может предоставлять информацию позиции в ответ на запрос позиции из мобильного устройства. В таких случаях, возвращаемые данные могут быть представлены на расширяемом языке разметки (XML), предоставленном в ответ на запрос на получение местоположения с использованием цифрового отпечатка (GLUF), когда этаж и публичное место разрешаются. Пример XML, предоставленного в ответ на этот запрос, проиллюстрирован на фиг. 11. Элемент <ResolvedLocation> является XmlElement в <LocationResult> и является поставщиком свойств. Он представляет логическую позицию, в которую могут добавляться дополнительные подробные элементы публичного места. Например, могут добавляться подробные элементы "магазин", "парк магазинов", "ворота" и т.п. <ResolvedLocation> не заполняется, если отсутствует результат по помещениям. Также можно возвращать только публичное место (VENUEID) без результата по этажам, и только свойство VenueId заполняется в<ResolvedLocation>. Улучшенный GLUF-ответ является обратно совместимым только с одним дополнительным XML-узлом, который содержит объекты в логических позициях, к примеру, VenueId и FloorId.
[0064] Фиг. 12 иллюстрирует блок-схему мобильного вычислительного устройства 400, которое может содержать одно из мобильного вычислительного устройства 102, 104 по фиг. 1 и может включать в себя элементы мобильного устройства, к примеру, элементы, проиллюстрированные на фиг. 10, ниже. Вычислительное устройство 400 может включать в себя, например, процессор 412 и пользовательский интерфейс 418. Покомпонентный вид отображения пользовательского интерфейса 418 иллюстрирует вид сверху карты 200a публичного места, такого как место 200, с индикатором 415 логически выведенной позиции, отображаемым на карте вместе с радиусом 417 ошибки, окружающим индикатор 415 логически выведенной позиции.
[0065] Устройство 400 включает в себя запоминающее устройство 410, которое может сохранять множество наблюдений 411, 422 позиции. Хотя указываются только два наблюдения 411 и 422 позиции, следует понимать, что определенное число наблюдений позиции присутствуют в запоминающем устройстве 410. Каждое наблюдение позиции включает в себя цифровой отпечаток радиомаяков 402 и ассоциированные данные 404 радиомаяков. Наблюдения позиции могут быть использованы посредством приложения 420 для вычисления позиции. Приложение 420 для вычисления позиции может быть использовано, чтобы вычислять позицию из наблюдений 411, 422 позиции. Привязанные к местоположению приложения 430 используют логически выведенную позицию, вычисленную посредством приложения для вычисления позиции, для любой из ряда целей. В одном варианте осуществления (проиллюстрирован на фиг. 4) привязанное к местоположению приложение может представлять собой картографическое приложение и отображать логически выведенную позицию вместе с радиусом ошибки в пользовательском интерфейсе. Следует понимать, что множество других типов приложений используют логически выведенные позиции, и технология, поясненная в данном документе, не ограничена привязанными к местоположению приложениями, которые представляют собой картографические приложения.
[0066] Фиг. 13 иллюстрирует блок-схему функциональных компонентов вычислительного устройства 1400, которое в одном варианте осуществления может быть использовано, чтобы обеспечить службу 125 определения местоположения. Вычислительное устройство 1400 включает в себя процессор 1412 и пользовательский интерфейс 1418. Устройство 1400 дополнительно может включать в себя запоминающее устройство 1410, имеющее обеспеченные компоненты, включающие в себя хранилище 1411 радиомаяков по умолчанию и хранилище 1422 радиомаяков публичного места/AP. Хранилище 1411 радиомаяков по умолчанию может включать в себя двумерные наблюдения, используемые для обработки алгоритма по умолчанию (этап 360A), в то время как хранилище 1422 радиомаяков публичного места может включать в себя данные для способов на основе логического вывода EZ и в помещениях, описанных выше. Запоминающее устройство 1410 дополнительно может включать в себя приложения 1430, 1435 для вычисления позиции и приложение 1472 корреляции. Необязательно, привязанные к местоположению приложения 1478, к примеру, привязанные к местоположению приложения, используемые в мобильном устройстве обработки, также могут присутствовать в запоминающем устройстве 1410.
[0067] Фиг. 14 иллюстрирует примерную блок-схему мобильного устройства для реализации операций раскрытой технологии. Устройство по фиг. 14 является более подробной иллюстрацией, например, устройств 102, 104 по фиг. 1. Проиллюстрирована примерная электронная схема типичного мобильного устройства обработки. Мобильное устройство 1000 включает в себя один или более микропроцессоров 1012 и запоминающее устройство 1010 (например, энергонезависимое запоминающее устройство, такое как ROM, и энергозависимое запоминающее устройство, такое как RAM), которое сохраняет процессорночитаемый код, который выполняется посредством одного или более процессоров управляющего процессора 1012 для того, чтобы реализовывать функциональность, описанную в данном документе.
[0068] Мобильное устройство 1000 может включать в себя, например, процессоры 1012, запоминающее устройство 1010, включающее в себя приложения и энергонезависимое устройство хранения данных. Процессор 1012 может реализовывать связь, а также любое число приложений, включающих в себя приложения, поясненные в данном документе. Запоминающее устройство 1010 может представлять собой любой из множества типов запоминающих носителей хранения данных, включающих в себя энергонезависимое и энергозависимое запоминающее устройство. Операционная система устройства обрабатывает различные операции мобильного устройства 1000 и может содержать пользовательские интерфейсы для таких операций, как осуществление и прием телефонных вызовов, обмен текстовыми сообщениями, проверка голосовой почты и т.п. Приложения 1030 могут представлять собой любую совокупность программ, таких как приложение для работы с камерой для фотографий и/или видео, адресная книга, приложение для работы с календарем, мультимедийный проигрыватель, Интернет-обозреватель, игры, приложение будильника или другие сторонние приложения. Компонент 1040 энергонезависимого хранения данных в запоминающем устройстве 1010 содержит такие данные, как веб-кэши, музыка, фотографии, контактные данные, данные планирования и другие файлы.
[0069] Процессор 1012 также обменивается данными с приемо-передающей RP-схемой 1006, которая, в свою очередь, соединяется с антенной 1002, с инфракрасным приемо-передающим устройством 1008 и с датчиком 1014 перемещения/ориентации, такими как акселерометр и магнитометр 1015. Акселерометры включены в мобильные устройства для того, чтобы активировать такие приложения, как интеллектуальные пользовательские интерфейсы, которые позволяют пользователям вводить команды посредством жестов, GPS-функциональность в помещениях, которая вычисляет перемещение и направление устройства после того, как прерван контакт с GPS-спутником, и обнаруживать ориентацию устройства и автоматически изменять отображение с портретной на ландшафтную ориентацию, когда телефон поворачивается. Акселерометр может обеспечиваться, например, посредством микроэлектромеханической системы (MEMS), которая представляет собой миниатюрное механическое устройство (микрометрических размеров), скомпонованное на полупроводниковом кристалле. Могут считываться направление ускорения, а также ориентация, вибрация и удар. Процессор 1012 дополнительно обменивается данными с вызывным устройством/вибратором 1016, клавишной панелью/экраном 1018 пользовательского интерфейса, динамиком 1020, микрофоном 1022, камерой 1024, светочувствительным датчиком 1026 и температурным датчиком 1028. Магнитометры включены в мобильные устройства, чтобы активировать такие приложения, как цифровой компас, которые измеряют направление и абсолютную величину магнитного поля около мобильного устройства, отслеживают изменения магнитного поля и отображают направление магнитного поля пользователям.
[0070] Процессор 1012 управляет передачей и приемом беспроводных сигналов. В ходе режима передачи, процессор 1012 обеспечивает голосовой сигнал из микрофона 1022 или другой сигнал данных в приемо-передающую схему 1006. Приемо-передающая схема 1006 передает сигнал в удаленную станцию (например, в стационарную станцию, оператору, в другие сотовые телефоны и т.д.) для связи через антенну 1002. Вызывное устройство/вибратор 1016 используется для того, чтобы сообщать о входящем вызове, текстовом сообщении, календарном напоминании, напоминании будильника или выдавать другое уведомление пользователю. В ходе режима приема, приемо-передающая схема 1006 принимает голосовой или другой сигнал данных из удаленной станции через антенну 1002. Принимаемый речевой сигнал предоставляется в динамик 1020, тогда как другие принимаемые сигналы данных также обрабатываются надлежащим образом.
[0071] Дополнительно, физический разъем 1088 может использоваться, чтобы подключать мобильное устройство 100 к внешнему источнику питания, такому как сетевой адаптер или стыковочная станция с внешним питанием. Физический разъем 1088 также может использоваться в качестве соединения для передачи данных в вычислительное устройство. Соединение для передачи данных обеспечивает возможность таких операций, как синхронизация данных мобильного устройства с вычислительными данными на другом устройстве. Приемное устройство 1065 на основе глобальной системы позиционирования (GPS), использующее спутниковую радионавигацию для того, чтобы ретранслировать позицию пользовательских приложений, активируется для такой услуги.
[0072] Технология может работать во множестве других окружений конфигураций на основе вычислительных систем общего назначения или специального назначения. Примеры хорошо известных вычислительных систем, окружений и/или конфигураций, которые могут быть подходящими для использования с технологией, включают в себя, но не в качестве ограничения, персональные компьютеры, серверные компьютеры, карманные или переносные устройства, многопроцессорные системы, микропроцессорные системы, абонентские приставки, программируемую бытовую электронную аппаратуру, сетевые PC, миникомпьютеры, мейнфреймы, распределенные вычислительные окружения, которые включают в себя любые из вышеприведенных систем или устройств, и т.п.
[0073] Технология также может быть описана в общем контексте машиноисполняемых инструкций, таких как программные модули, выполняемые компьютером. Программные модули, в общем, включают в себя процедуры, программы, объекты, компоненты, структуры данных и т.д., которые выполняют отдельные задачи или реализуют отдельные абстрактные типы данных. Технология может быть реализована на практике в распределенных вычислительных окружениях, в которых задачи выполняются удаленными обрабатывающими устройствами, которые связаны через сеть связи. В распределенном вычислительном окружении, программные модули могут быть размещены как на локальных, так и на удаленных компьютерных носителях хранения данных, включающих в себя запоминающие устройства.
[0074] Хотя предмет изобретения описан на языке, характерном для структурных признаков и/или технологических этапов, следует понимать, что предмет изобретения, заданный в прилагаемой формуле изобретения, не обязательно ограничен характерными признаками или этапами, описанными выше. Вместо этого, характерные признаки и этапы, описанные выше, раскрываются как примерные формы реализации формулы изобретения.