近隣のデバイス発見技術の開発方法

この話は、モバイルアプリの1つの「周辺」機能から始まりました。 ユーザーがグループチャットをすばやく作成したり、近くのユーザーを友達として追加したりできるようにしたかったのです。 ジオロケーション、Bluetooth、Wi-Fi、および超音波を使用してこの問題を解決しようとしましたが、各方法で重大な欠陥を発見しました。



その結果、私たちは新しい方法を思いつきました。 これは、周囲のノイズの一致を見つけることに基づいています。デバイスが同じことを聞いた場合、おそらく近くにあります。



この記事では、その動作原理について説明し、デバイスを検出する他の一般的な方法の長所と短所についても検討します。

近くのデバイス間の相互作用

隣同士の人は、ファイルを共有したり、新しい友達を友達に追加したり、一緒にゲームをしたり、送金したり、アカウントを共有したり、他の共同アクションを実行したりします。 このようなアプリケーションは、ユーザーが周囲の人やデバイスと簡単にやり取りできるようにすると便利になります。



たとえば、ペトロフはイワノフに会ったばかりで、Facebookで「友達を作ろう」としています。 お互いを見つけようとする試みが何度か失敗した後、彼らはおそらくFacebookを閉じ、電話番号を交換し、WhatsAppを介して通信します。



ちなみに、Vkontakteはこれを提供しました。iOSおよびAndroid向けのモバイルアプリケーションには、「近くの人」機能があり、ジオロケーションを使用して他のユーザーを見つけることができます。 この方法の短所については、少し後で説明します。

FBで新しい友達を検索する	Vkで新しい友達を検索する

関数がユーザーにとって本当に便利であるためには、機能する必要があります。

• どんなスマートフォンでも
• いつでもどこでも。 路上、輸送中、オフィス内など
• クロスプラットフォーム。 少なくともiOSとAndroidで、さらに良いのはブラウザで
• そうだね 本当に近くにあるデバイスを特定する
• 早く。 デバイスは10秒以内に検出される必要があります
• シンプル。 追加のユーザー操作はありません

周囲騒音

どこにいても（オフィス、交通機関、カフェ、路上、会議、コンサートなど）-周囲の騒音があるすべての場所：人々の声、音楽、エンジン操作、ホイールノイズ、キーのノッキングなど。



自然な周囲のノイズの短いサンプルと、それが記録された正確な時間は、ほとんどの場合、地球上のあらゆる場所に固有のものです。 周囲のノイズと時間の一致は、録音デバイスが近くにあることを意味します。 技術が機能するのは、これに基づいています。





作業スキーム



各デバイスはリアルタイムでマイクから音をキャプチャし、 知覚ハッシュ関数を使用して特殊な指紋に変換します 。 知覚的ハッシュ関数の特徴は、ソースデータの小さな違いが、結果のハッシュの小さな違いで表されることです。



正確なタイムスタンプを持つサウンドのフィンガープリントがサーバーに送信されます。 同時に作成された他のデバイスの指紋と比較することにより、サーバーは元の音がどれだけ似ているかを判断できます。 類似性インジケータが特定のしきい値を超えている場合、デバイスは後続の相互作用のために互いの識別子を受け取ります。





2つの異なるデバイスからのプリントの例と比較



この原理が機能し、数メートルの距離で異なるデバイスによって記録されたサウンドの一致を見つけることができ、また明らかに異なるサウンドが一致しないことを確認する必要がありました。 さまざまな場所の複数のデバイスで同時に録音された数百時間の音声を手動で収集しました。



このデータを使用して、多くの生成アルゴリズムと指紋比較パラメーターを調べて、最良の結果を達成しました。 その結果、6秒の印刷により、96％のケースで最大5メートルの距離でデバイスを検出でき、0.0039％のケースで偽陽性の結果が得られることが達成されました。



iOSおよびAndroid用のライブラリを開発し、シンプルなAPIを介してアプリケーションから実装全体を隠し、アプリケーションに埋め込みます。



このアプローチの欠点は、完全な静寂では機能しないことです。 無音は他の無音と非常によく似ており、アルゴリズムは意図的にそれを無視して誤報を防ぎます。 絶対的な沈黙は、実際の状況では非常にまれであることは注目に値します。 デバイスがお互いを検出するには、キーボードキーのノックまたはステップの音で十分です。



時々おかしいように見えます。ユーザーは10秒間検出されるのを静かに待った後、そのうちの1人が「これは機能しません！」などと言います。 このフレーズは呪文のように機能し、1秒後にデバイスがお互いを検出します。



このアプローチの利点の1つは、クロスプラットフォームです。 ライブラリのJSバージョンは、モバイルバージョンを含むChrome、Safari、Firefox、Edgeで動作します。

別の方法....

このアプリケーションでは、「Near」機能が重要な要素の1つです。 その実装にさまざまな既存の方法を適用しようとしましたが、私たちにとって重大な制限と問題に直面しました。

別の方法を詳しく見てみましょう。

ジオロケーション

これが問題を解決する最も明白な方法です。 ユーザーが「近く」セクションを開くと、現在の場所を取得し、サーバー上の最も近いユーザーを検索します。



場所を円の中心として表し、座標エラーを半径の形式で表す場合、2人のユーザーは次のように表すことができます。









デバイス間の距離（d）がエラーの合計（r1 + r2）より小さい場合、ユーザーが近くにいる可能性（P）があります。



検索半径は、座標誤差以上でなければなりません。 判明したように、スマートフォンの実際の座標は誤差の範囲を超えている可能性があります。たとえば、Androidではこれはケースの32％で発生します。 そのため、近くにいても、ユーザーはお互いを「見る」ことができません。



GPSとGLONASSを使用して取得した座標は正確ですが、この方法は屋内ではうまく動作しないことが多く、さらに衛星を検索するのに最大1分かかる場合があります。 同時に、GPS / GLONASSモジュールはすべてのデバイスに存在しない（Hello、iPad Wi-Fi！）、またはOSレベルで無効にすることができます（Hello、Android！）。



実際、建物の外でも、密集した建物がある通りでは、GPS / GLONASSは建物からの信号の反射のためにしばしば誤解され、100メートル未満の精度を与えることができます。









したがって、ほとんどの場合、周囲のWi-Fiネットワークとセルタワーからの信号を三角測量することによって取得した座標を使用する必要があります。この方法は迅速かつエネルギー効率よく機能しますが、精度は1桁低くなります：100〜1500メートル。 実際には、デバイスは都市内の誤った場所を検出することが多く、場合によっては別の都市に「テレポート」できます。



この方法を実装し、モスクワでテストしました。約15％のケースでは、座標が正しくないためにデバイスがお互いを見つけることができません。 特に、モスクワ市の高層ビル内、地下鉄および地上輸送でエラーが発生します。 また、精度が低いため、「余分な」ユーザー（近くにいないユーザー）がよく遭遇します。



+実装が簡単な方法

-低精度

-（移動中の）輸送ではうまく機能しない

バンプ

Bumpチームは、ジオロケーション検索の精度を向上させる独自の方法を考案しました。 ユーザーはスマートフォンをノックする必要がありますが、加速度計は正確な接触時間を記録して座標とともにサーバーに送信しますが、アルゴリズムは同じ接触時間を持つデバイス間でのみペアを検索します。 この単純なアイデアにより、偽陽性結果の確率が桁違いに減少し、検索範囲を大幅に拡大することが可能になります。



しかし、2013年にGoogleがそれらを吸収し、2014年にBump SDKが多くのサードパーティアプリケーションに組み込まれ、Bumpファイル共有アプリケーションが何億ものダウンロードを受け取ったという事実にもかかわらず、プロジェクトは既に終了しました。 技術のさらなる運命は不明です。



この技術の主な欠点は、1つの「バンプ」に接続されているデバイスが2つしかないことです。 ユーザーのグループを結合するには、たくさんの「バンプ」を作成する必要があります。



+高精度

-デバイスを一緒にプッシュする必要があります

-ペアワイズデバイス検出

-プロジェクトは終了しました

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は、Androidを検出するために、そのBLEトークンを検出した周囲のAndroidデバイスの識別子をクラウド経由で受け取ります。



周囲のWi-Fiネットワークは、デバイスが近くにあることを見つけるのに役立ちます。iOSアプリケーションは、ユーザーが現在接続しているWi-FiアクセスポイントのBSSIDを受信でき、Androidはすべての可視ポイントのBSSIDを受信できます。 一致が見つかった場合、ユーザーは近くにいます。



この方法を自分で適切に実装するのはそれほど簡単ではありません。AndroidとiOSの異なるバージョンのBLEスタックの多くの機能のためです。 「内部」で複雑な実装を隠すライブラリがあります。



Google Neighborhoodを試しました 。 iOSとAndroidのペアの検出は遅く、平均して検索に20秒かかり、場合によっては最大40秒続きますが、これが主な停止要因であることが判明しました。



もう1つの微妙な点は、ほとんどのスマートフォンでBluetoothがオフになっていることです。そのため、iOSユーザーは「Bluetoothの使用をアプリケーションに許可しますか？」という質問に答える必要があります。



また、Bluetooth（Android）の使用はバッテリー消費に大きく影響することを覚えておく価値があります。 グーグルはグーグル・ネイバーフッドがエネルギー消費を2.5〜3.5倍増加させると警告している 。



+近接性の証明（デバイスが近くにあることを保証）

-検出が遅い

-高エネルギー消費

音による情報交換

すべてのスマートフォンにはスピーカーとマイクがあります。 1つのデバイスで任意の識別子をサウンドにエンコードし、スピーカーで再生し、耳元のデバイスでデコードして、デバイスをグループにまとめることができます。





Chirp.io信号スペクトログラムの例



可聴域では、信号は音声、音楽、周囲のノイズと混合されます。正しいデコードの可能性を高めるには、最大音量でサウンドを再生する必要があります。 ほとんどの場合、FSKおよびPSK変調が使用され、口dataやノイズ（データ密度に依存）に似た音を生成し、多くの人を悩ます（ 音の例 ）。 このメソッドは、 Chirp.ioプロジェクトに実装されています。



-騒がしい場所ではうまく機能しない

-他人を悩ます



18〜20 kHzの範囲を使用できます。通常はうるさくなく、ほとんどの大人は迷惑な音を聞きません。 残念ながら、一部のスマートフォンはそれをあまり認識しておらず、反射と干渉の問題が関連するようになり、安定した通信の範囲は0.5〜3メートルに減少します。 このメソッドはGoogle NeighborhoodとChirp.ioに実装されていますが、個別に含まれています。



-距離が短すぎる

結論の代わりに

私たちは、2年以上にわたって独自のアプリケーションでテクノロジーをテストしてきました。 この間、「戦闘」状態でのパフォーマンスと利便性を確信しました。 近い将来、すべての開発者がアプリケーションで迅速にビルドして使用できるようにしたいと考えています。



この記事が有益で有益であることを願っています。 トピックが興味深いことが判明した場合、以下の記事で、サラウンドサウンドの「プリント」を作成および比較するアルゴリズムと、直面しなければならない困難についてさらに詳しく説明する予定です。



コメントでご質問にお答えします！