Как мы разработали технологию обнаружения устройств поблизости



Эта история началась с функции “Рядом” в одном из наших мобильных приложений. Мы хотели, чтобы пользователи могли быстро создать групповой чат или добавить находящихся рядом пользователей в друзья. Мы попробовали решить эту задачу при помощи геолокации, Bluetooth, Wi-Fi и ультразвука, но у каждого из способов мы обнаружили критичные в нашем случае недостатки.

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

В статье мы расскажем о принципе его работы, а также рассмотрим достоинства и недостатки других распространенных способов обнаружения устройств.


Взаимодействие между устройствами поблизости


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

Например, Петров только что познакомился с Ивановым и они пытаются “подружиться” на Facebook. Спустя несколько безуспешных попыток найти друг-друга, они, скорее всего, закроют Facebook, обменяются номерами телефонов и будут общаться через WhatsApp.

Кстати, Вконтакте предусмотрели это: в их мобильном приложении для iOS и Android есть функция “Люди Рядом”, которая позволяет найти других пользователей при помощи геолокации. О минусах этого способа я расскажу чуть позже.
Поиск нового знакомого в FB Поиск нового знакомого в Vk

Чтобы функция действительно была удобна пользователю, она должна работать:

  • На любом смартфоне
  • Всегда и везде. На улице, в транспорте, в офисе и т.д.
  • Кроссплатформенно. Как минимум на iOS и Android, а лучше, и в браузере
  • Точно. Определять устройства, которые действительно рядом
  • Быстро. Устройство должно быть найдено менее, чем за 10 секунд
  • Просто. Без дополнительных действий со стороны пользователя

Окружающий шум


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

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


Схема работы

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

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


Пример и сравнение отпечатков с двух разных устройств

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

Используя эти данные, мы перебрали множество алгоритмов генерации и параметров сравнения отпечатков для достижения наилучшего результата. В итоге добились того, что 6-секундный отпечаток позволяет обнаружить устройство на расстоянии до 5 метров в 96% случаев, а ложноположительный результат возможен в 0.0039% случаев.

Мы разработали библиотеки для iOS и Android, которые скрывают от приложения всю реализацию через простой API и встроили их в свои приложения.

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

Иногда это выглядит забавно: пользователи молча ждут обнаружения секунд 10, после чего один из них говорит что-то вроде “Это не работает!”. Эта фраза работает как заклинание и через секунду устройства обнаруживают друг-друга.

Одно преимуществ данного подхода — кроссплатформенность. JS-версия библиотеки, работает в Chrome, Safari, Firefox, Edge, в том числе, в их мобильных версиях.

Еще один способ….


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

Геолокация


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

Если представить местоположение как центр окружности, а погрешность координат в виде радиуса, то 2 пользователя могут быть изображены следующим образом:


Если расстояние между устройствами (d) меньше суммы погрешностей (r1 + r2), значит есть вероятность (P), что пользователи находятся рядом.

Радиус поиска должен быть не меньше погрешности координат. Как оказалось, реальные координаты смартфона могут находиться и за пределами погрешности, например, в Android это происходит в 32% случаев. Значит, даже находясь рядом, пользователи все равно могут не “увидеть” друг-друга.

Координаты, полученные при помощи GPS и ГЛОНАСС точны, но этот способ зачастую не работает внутри помещений, кроме того, может потребоваться до минуты на поиск спутников. При этом, модуль GPS/ГЛОНАСС присутствует не во всех устройствах (Привет, iPad Wi-Fi!) или может быть отключён на уровне ОС (Привет, Android!).

На самом деле, даже вне здания, на улице с плотной застройкой GPS/ГЛОНАСС часто ошибается из-за отражения сигнала от зданий и может выдавать точность ниже 100 метров:


Поэтому в большинстве случаев приходится использовать координаты, полученные при помощи триангуляции по сигналу окружающих Wi-Fi сетей и сотовых вышек, этот способ работает быстро и энергоэффективно, но точность на порядок ниже: 100 — 1500 метров. На практике, устройство нередко определяет неверное местоположение в городе, а иногда может “телепортироваться” в другой город.

Мы реализовали этот способ и протестировали его в Москве, примерно в 15% случаев устройства не находят друг-друга из-за неверных координат. Особенно часто ошибки происходят внутри высоток Москва-Сити, в метро и наземном транспорте. Также из-за низкой точности часто будут попадаться “лишние” пользователи (не находящиеся рядом).

+ простой в реализации способ
− низкая точность
− плохо работает в транспорте (в движении)

Bump


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

Но в 2013 их поглотил Google, а уже в 2014 проект закрыли, несмотря на то, что Bump SDK был встроен во множество сторонних приложений, а приложение Bump для обмена файлами получило сотни миллионов скачиваний. Дальнейшая судьба технологии неизвестна.

Главный недостаток технологии заключается в том, что за один ”Бамп” связывается только пара устройств. Чтобы объединить группу пользователей, потребуется сделать множество “Бампов”.

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

Bluetooth, BLE и Wi-Fi


iOS и Android категорически не дружат по Bluetooth. Передача данных между этими платформами — нетривиальная задача: Apple позволяет приложению подключиться только к сертифицированным (Made For iPhone) Bluetooth-устройствам.

Чтобы устройства могли обнаружить друг-друга, используется следующий способ: iOS имитирует какую-либо Bluetooth Low Energy-периферию, устанавливая свой токен в качестве имени BLE-устройства. Android временно меняет Bluetooth-имя смартфона на свой токен и включает режим обнаружения. Теперь, чтобы обнаружить устройства вокруг, Android сканирует Bluetooth для обнаружения Android и BLE для обнаружения iOS-устройств. iOS сканирует только BLE для обнаружения iOS, т.к. сканирование Bluetooth-устройств невозможно с помощью публичного API. Для того, чтобы обнаружить Android, iOS через облако получает идентификаторы окружающих Android-устройств, которые обнаружили его BLE-токен.

Окружающие Wi-Fi-сети в некоторых случаях помогают обнаружить, что устройства рядом: iOS-приложение может получить BSSID Wi-Fi точки доступа, к которой в данный момент подключен пользователь, а Android BSSID всех видимых точек. Если найдено совпадение, значит, пользователи рядом.

Грамотно реализовать этот способ самостоятельно не так уж просто, в том числе из-за множества особенностей BLE-стека разных версий Android и iOS. Существуют библиотеки, которые скрывают сложную реализацию “под капот”.

Мы попробовали Google Nearby. Обнаружение пары iOS — Android происходит медленно, в среднем поиск занимает 20 секунд, а в некоторых случаях длится до 40 секунд, это оказалось главным останавливающим фактором.

Другой нюанс заключается в том, что Bluetooth выключен на большинстве смартфонов, поэтому пользователям iOS каждый раз при использовании функции нужно будет правильно ответить на вопрос “Разрешить приложению использовать Bluetooth?”.

Также, стоит помнить, что использование Bluetooth (на Android) сильно влияет на потребление заряда. Google предупреждает, что Google Nearby увеличивает потребление энергии в 2.5 — 3.5 раза.

+ proof of proximity (гарантия того, что устройства находятся рядом)
− медленное обнаружение
− высокое потребление энергии

Обмен информацией через звук


У всех смартфонов есть динамик и микрофон. Можно закодировать какой-либо идентификатор в звук на одном устройстве, воспроизвести его при помощи динамика, декодировать на устройствах в радиусе слышимости и таким образом объединить устройства в группу.


Пример спектрограммы сигнала Chirp.io

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

− плохо работает в шумных местах
− раздражает окружающих

Можно использовать диапазон 18-20 кГЦ, он обычно не зашумлен, а большинство взрослых людей не услышат раздражающий звук. К сожалению, некоторые смартфоны тоже воспринимают его плохо, становится актуальна проблема отражения и интерференции, дальность устойчивой связи уменьшается до 0.5 — 3 метров. Этот способ реализован в Google Nearby и Chirp.io, но включается отдельно.

− работает на слишком малых расстояниях

Вместо заключения


Мы тестируем технологию в собственном приложении уже более 2-х лет. За это время мы убедились в ее работоспособности и удобстве в “боевых” условиях. В очень скором времени мы хотим дать возможность любому разработчику быстро встроить и использовать ее в своем приложении.

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

С удовольствием отвечу на ваши вопросы в комментариях!
Поделиться публикацией
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 45
  • +3
    Любопытный метод, я только не уловил один момент: каким образом вы анализируете «похожесть» двух сэмплов, если два устройства могут записать звук с неким рассинхроном по времени? Одно устройство может начать запись в момент N, а второе (в силу разных причин — поздно нажали кнопку, или устройство подвисло, или еще что, и получается момент N + k). Как их засинхронить для сравнения? Также, правильно ли я понимаю, что понять дистанцию друг от друга при таком методе позиционирования — довольно проблематичная задача?
    • 0
      автор поправит, но как я понимаю, постоянно делается отпечаток куска времени и отправляется на сервер(тогда будет работать история про «пользователи молча ждут обнаружения секунд 10, после чего один из них говорит что-то вроде “Это не работает!”. Эта фраза работает как заклинание и через секунду устройства обнаруживают друг-друга. » )
      по моему не решаемая «дистанцию друг от друга», но это и логично, цель сего: нужно с высокой долей вероятности доказать что устройства находятся в одном помещении\пространстве
      • 0
        Верно. В начале работы мы синхронизируем локальное время с серверным. Отпечатки генерируются в реальном времени и отправляются на сервер вместе с точным временем записи исходного звука.
        Понять расстояние таким образом не получится, да.
        • 0
          Наверное, я немного не так выразился по поводу синхронизации. Я понимаю, что каждый сэмпл маркируется некой меткой времени, я о другом: как часто пишутся сэмплы, чтобы достичь хорошего качества позиционирования, но при этом не разрядить в ноль батарею и не забить до отказа свободное пространство на «диске»? Каждую секунду, каждые 10 секунд? И насколько длинными вы решили делать сэмплы, чтобы получалось с высокой точностью выполнять позиционирование, не расходуя тонну мегабайт свободного места? Допустим, если я от пользователя получаю 100 сэмплов с метками времени, и от другого ту же сотню, то потом я отброшу все сэмплы, не совпадающие по серверному времени, и проанализирую только те, что засинхронены. Верно же? А вот интервал какой между записью?
          • 0
            SDK позволяет запустить и остановить поиск когда угодно. Когда поиск запущен — звук пишется постоянно, хэшируется и отправляется на сервер в реальном времени, не занимает место на «диске» устройства.
            В нашем приложении поиск запускает сам пользователь, и он автоматически прекращается при сворачивании/закрытии приложения. По потреблению аккумулятора точных замеров нет. Алгоритм нагружает CPU Snapdragon 430 примерно на 3-4%.
            • 0
              т.е. такого понятия как «интервал между записью» нету, запись происходит непрерывно.
              • 0
                Интересно. Благодарю за ответ.
      • 0
        Я так понимаю запись происходит не в течении какого-то фиксированного времени, а пока не найдутся совпадения. То есть первый может начать записывать, второй начнет через какой-то промежуток времени и найдут они друг друга только при записи чего-то общего. Соответственно у первого побольше времени уйдет.
        Что касается дистанции, то если я правильно понял, то вычисление дистанции не нужно и поиск направлен на людей которые уже знакомы и находятся в непосредственной близости. Главная задача просто понять, что другой человек находится в зоне совпадения звуков.
        • 0
          Да, не обязательно начинать поиск одновременно. Тот, кто запустил поиск позже — будет найден как только отпечатки начнут совпадать.
      • 0
        iOS сканирует только BLE для обнаружения iOS, т.к. сканирование Bluetooth-устройств невозможно с помощью публичного API.

        Насколько актуальна эта информация? Есть какое-то подтверждение из внешних источников?
        • 0
          Информация актуальна для iOS 11. Есть два способа работать с BT: Core Bluetooth framework, который позволяет работать только с BLE и External Accessory framework, который позволяет обнаруживать только MFI устройства
          • 0
            попробовал написать программу, которая светит 32 байтной строкой по BLE в peripherial mode на андроиде. IOs при сканировании видит эту строку без проблем.

            Использовалась библиотека github.com/omergul/Discovery

            Тесть нет проблемы идентифицировать 2 девайса iOS/android, android/android, iOS/iOS по этой строке. Выглядит гораздо менее енергозатратно. Да и проще в разработке.
            • 0
              К сожалению, очень многие Android-устройства не поддерживают BLE peripherial mode. Здесь можно посмотреть статистику на эту тему.
              В ОС поддержка добавлена начиная с Android 5 (уже теряем около 15% пользователей), в железе/firmware эта возможность тоже реализована не везде.

              Именно поэтому в Google Nearby используется обычный Bluetooth для поиска Android-Android.
        • +3
          Еще бы совместили свой вариант со звуковым методом — если детектируется тишина в течение пары секунд — одно (или даже оба) из устройств генерирует какой-нибудь звук.
          • 0
            Вот-вот, у меня вопрос — а почему просто не проиграть что-то уникальное на одном устройстве и найти это на других?

            По крайней мере это будет вызывать меньше параноидальных подозрений… не люблю, когда на моем телефоне вдруг зажигается иконка доступа к звуку-видео просто так.
            • 0
              В этом случае как минимум одному из вас все равно придется разрешить доступ к микрофону. Рано или поздно этим человеком станете Вы, верно? Кстати, а где у вас зажигается иконка доступа к звуку или видео? Не припомню такого в Android и iOS.
          • +1
            А как же QR-код? Вряд ли сейчас есть телефоны без камеры.
            • 0
              Для нашего приложения важно уметь быстро объединять множество людей. Причем, эти люди не всегда находятся на расстоянии для сканирования QR, например, слушатели доклада на конференции. QR-код позволяет объединять устройства попарно, чем больше людей — тем больше времени будет потрачено.
              Для сценариев, где нужно объединить только 1 пару пользователей, QR-код может быть удобен.
              • 0
                Один может выставить свой экран-код перед толпой, которая направит свои камеры на его экран.
                Можно попросить показать код на большом экране всем слушателям.
            • 0
              А если, допустим, мы с другом на расстоянии, скажем, 10 км, смотрим одну и ту-же телепередачу?
              Да, сценарий средней реалистичности, но всё-же. Время одно и то-же, звук одинаковый.
              • 0
                В очень редких случаях. Дело в том, что каждый провайдер и оборудование даже в рамках города вносит различные задержки в вещании, по нашему опыту от 5 до 30 секунд.
                Это возможно, если вы оба смотрите радиовещение (без задержек), а посторонних звуков мало.
                Способ решить эту проблему у нас уже есть, но пока пользователей не так много — он не имеет смысла.
                • 0
                  Выходит, Вам нужно точное время, так?
                  А раз каждый провайдер вносит свои задержки, то даже у двух человек, стоящих рядом, но имеющих разного оператора, сэмпл будет иметь немного разное время? (те-же 5 — 30 секунд).
                  Но в целом идея понравилась, интересное решение. Не слышал раньше о подобном
                  • 0
                    Мы сами синхронизируем локальное время с серверным при помощи протокола, похожего на NTP, поэтому разница времени на устройствах пользователей не играет роли.
              • 0

                Простая и классная идея, супер! Вы берёте хэш от спектрограммы или от исходного сигнала?

                • 0
                  Спасибо! От спектрограммы
                • 0
                  Если в МакДональдсе несколько пар решили только попарно соединиться и пересеклись во времени включения, все соединятся?
                  • 0
                    Зависит от. Если громко играет фоновая музыка, то пользователи соеднятся. Но естественный шум в людном месте обычно очень изменчив. На расстоянии 5 метров может быть уже другой.

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

                    С точки зрения UX мы считаем, что нужно дать пользователю выбор или подтвердить действие «соединения».
                    • 0
                      Приложение для фанатов «Спартака» будет очень популярно )
                    • –2
                      Вместо свинга получилась групповуха. И всё это в макдачке.
                    • 0
                      Реализацию алгоритма (и данные нейросетей или коэффицентов в формулах, которые используются) ожиается закрытой? не собираетесь открывать ее на публику?

                      Такие вещи, по мне, так должны быть в операционных системах по умолчанию желательно без завязки на сервер (кроме как ради точного времени).
                      • 0
                        Если бы это собрали в кроссплатформенную библиотеку, вполне можно написать ещё одну статью.
                        • 0
                          Думаем насчет opensource, вполне возможно.
                        • +1
                          Не уверен, что тут можно постить ссылки, но вот ссылка на технологию Resonance www.getresonance.net и приложение DROP, которое ее использует www.getdrop.net
                          • +1
                            Хабр мотивирует!)
                            • 0
                              − работает на слишком малых расстояниях

                              А это минус?
                              Почему вы этот минус у бампа не написали? Там то вообще надо стукнуть телефоны друг о друга.
                              По сути это бамп только для кучи устройств сразу и без необходимости долбить телефоны друг о друга.
                              • 0
                                В нашем случае — минус. У Bump тоже этот минус стоит указать, согласен с Вами.
                              • 0

                                Гениально, правда. Всяческих успехов и обязательно защититесь патентами со всех сторон.

                                • 0
                                  Спасибо. Международную патентуную заявку мы подали давно, как только были первые прототипы технологии и только сейчас получили подтверждение получения патента.
                                • 0
                                  Обнаружен смартфон Apple Iphone X. Примерное расположение- левый карман куртки справа стоящего человека.

                                  А если серьезно, то я бы подождал пока nfc пойдет в массы и уже с этой технологией организовывал чаты.
                                  • 0
                                    Триангуляция оперирует углами, коих по понятным причинам нет в случае определения координат по базовым станциям и Wi-Fi.
                                    На самом деле в таких случаях используется трилатерация.
                                    • 0
                                      «Обмен информацией через звук» — давно хотел сделать приложение для обмена через звук которое бы использовало технологию которая была реализована в модемах. Для обмена ID, хватило бы даже 2400 бод.

                                      Звук хандшейка двух модемов многих бы заставил понастольгировать.

                                      Еще вариант, использовать технологию как у Shazam. Типа играем какую нибудь не очень популярную сейчас песню, но которая в есть базе и по ней определяем кто на другой стороне, музыка не должна привлекать сильно много внимания.
                                      • 0
                                        Что на счет штрихкода?
                                        Вася нажимает кнопку показать штрихкод.
                                        Петя, Таня, Оля, делают фотку дивайса с штрихкодом и с отправлением на сервер,
                                        5- 10 сек и все в группе.

                                        ps
                                        Юзайте на здоровье.
                                        • 0
                                          Очень круто, жаль что вы вероятно нарушаете патенты www.getresonance.net, хотя очень бы хотелось бы увидеть вашу реализацию в опенсоурс.
                                        • 0
                                          <del/>

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

                                          Самое читаемое