bluetooth-lowenergy - iBeacons の三角測量の例

Question

複数の iBeacon を使用して「大まかな」屋内位置を特定する可能性を検討しています。アプリケーションは一種の「博物館」設定であり、個々のビーコンよりもさまざまなオブジェクトの場所を含むグリッドを形成できる方が簡単です (ただし、それも不可能ではないかもしれません)。

複数のビーコンを使用してある種の場所に三角測量する例、経験、またはそれを自分で作成するのに役立つロジックはありますか?

Answer 1

3 つのビーコンを使用して正確な位置を取得するための実験を行っています。

三辺測量の結果

残念ながら、結果は品質の点で非常に残念でした。主に次の 2 つの問題がありました。

1. 信号に影響を与える金属やその他のオブジェクトを見つけることができる制御されていない環境では、ビーコンの受信信号強度が頻繁に変化するため、5メートル未満のエラー範囲を取得することは不可能に思えます.
2. ユーザーが受信デバイスをどのように扱っているかによって、測定値も大きく変わる可能性があります。ユーザーが Bluetooth アンテナに手をかざすと、アルゴリズムの入力信号が低くなるため、ビーコンはデバイスから非常に遠くにあると見なされます。Bluetooth アンテナの正確な位置を確認するには、この画像を参照してください。

可能な解決策

Apple のエンジニアと話した結果、私がこの方法で降りるのを積極的に思いとどまらせた後、私が今より使いたくなる選択肢は力ずくです。X メートル (X はシステムで許容される最大誤差) ごとにビーコンを設定してみてください。これにより、このビーコン グリッドで特定のデバイスの位置を追跡できるようになります。グリッド上のどのビーコンがデバイスに最も近いかを計算し、次のように仮定します。デバイスは同じ位置にあります。

三辺測量アルゴリズム

ただし、完全を期すために、三辺測量アルゴリズムのコア機能を以下で共有します。これは、この記事の段落 3 (「既知の 3 つの距離」) に基づいています。

- (CGPoint)getCoordinateWithBeaconA:(CGPoint)a beaconB:(CGPoint)b beaconC:(CGPoint)c distanceA:(CGFloat)dA distanceB:(CGFloat)dB distanceC:(CGFloat)dC {
    CGFloat W, Z, x, y, y2;
    W = dA*dA - dB*dB - a.x*a.x - a.y*a.y + b.x*b.x + b.y*b.y;
    Z = dB*dB - dC*dC - b.x*b.x - b.y*b.y + c.x*c.x + c.y*c.y;

    x = (W*(c.y-b.y) - Z*(b.y-a.y)) / (2 * ((b.x-a.x)*(c.y-b.y) - (c.x-b.x)*(b.y-a.y)));
    y = (W - 2*x*(b.x-a.x)) / (2*(b.y-a.y));
    //y2 is a second measure of y to mitigate errors
    y2 = (Z - 2*x*(c.x-b.x)) / (2*(c.y-b.y));

    y = (y + y2) / 2;
    return CGPointMake(x, y);
}

Answer 2

私はこれを調べました。あなたがそれを三辺測量したい用語。(三角測量では、既知の 3 点からの角度が得られます。三角測量では、既知の 3 点からの距離が得られます) Google で検索すると、Wiki の記事を含むいくつかの記事が見つかるはずです。3 つの連立方程式を解く必要があります。私が見たドキュメントは 3D 三辺測量に関するものでした。Z 項を削除するだけでよいので、2D の方が簡単です。

私が見つけたのは抽象的な数学でした。一般的なアルゴリズムを特定のコードにマッピングする時間はまだ取っていませんが、いつか取り組む予定です。

特に空の部屋以外では、得られる結果は非常に粗いものになることに注意してください。信号は十分に弱いため、人、彫像、または視線を遮るものがあれば、距離の測定値が大幅に増加します. 建物内には建設的な干渉 (主に壁からの) により、一部の場所が実際よりも近くに表示される場合もあります。

Answer 3

iBeacon を使用した正確な屋内測位は、次の理由から困難です。

1. 以前のコメントで指摘したように、iBeacon 信号は大きく変動する傾向があります。その理由には、マルチパス効果、人が動いているときの電話と iBeacon 間の動的オブジェクト障害、その他の 2.4GHz 干渉などが含まれます。したがって、理想的には、1 つのパケットのデータを信頼するのではなく、同じビーコンからの複数のパケットの平均化を行います。それには、これらのいくつかのパケット間で電話/ビーコンの距離があまり変化しないことが必要です。一般的な BLE パケット (StickNFind のビーコンなど) の場合、10Hz のビーコン レートに簡単に設定できます。ただし、iBeacon の場合は難しいでしょう。
2. iBeacon のビーコン周波数は、おそらく 1Hz より高くすることはできません。誰かが別のことを言っている情報源を指摘してくれるとうれしいですが、これまでに見たすべての情報はこの主張を裏付けています. ほとんどの iBeacon はバッテリー駆動であり、高周波はバッテリーの寿命に大きな影響を与えるため、これは実際には理にかなっています。人間の平均歩行速度が5.3 km (~1.5 m/s) であることを考慮すると、3 つのビーコン パケットを適度に使用して平均化を行ったとしても、~5 m の精度を得るのは困難です。

一方、iBeacon の周波数を 10Hz よりも大きくすることができれば(これは可能ではないと思います)、適切な処理方法を使用して 5m 以上の精度を実現できます。最初に、三辺測量のような逆二乗則に基づく自明なソリューションは、実際には、上記の理由 1 により、さまざまなビーコンの距離/RSSI 関係が逆二乗則からかけ離れていることが多いため、うまく機能しないことがよくあります。ただし、RSSI が特定の場所の特定のビーコンに対して比較的安定している限り (通常はそうです)、フィンガープリンティングと呼ばれるアプローチを使用して、より高い精度を実現できます。フィンガープリンティングに使用される一般的な方法は kNN ( k-Nearest Neighbor ) です。

2014-04-24 更新

Estimote がデフォルトで 5Hz を使用するように、一部の iBeaconsは1Hz 以上をブロードキャストできます。ただし、このリンクによると、 「これは Apple の制限です。IOS は、デバイスがアドバタイズする頻度に関係なく、毎秒ビーコンの更新を返します。」. そこには別のコメントがあります (Estimote ベンダーからのものと思われます)。したがって、より高い iBeacon 頻度が有益かどうかは明らかではありません。

Answer 4

@Javier Chávarriデバイスの三辺測量機能が必要な場合Android(時間を節約するため):

public static Location getLocationWithTrilateration(Location beaconA, Location beaconB, Location beaconC, double distanceA, double distanceB, double distanceC){

    double bAlat = beaconA.getLatitude();
    double bAlong = beaconA.getLongitude();
    double bBlat = beaconB.getLatitude();
    double bBlong = beaconB.getLongitude();
    double bClat = beaconC.getLatitude();
    double bClong = beaconC.getLongitude();

    double W, Z, foundBeaconLat, foundBeaconLong, foundBeaconLongFilter;
    W = distanceA * distanceA - distanceB * distanceB - bAlat * bAlat - bAlong * bAlong + bBlat * bBlat + bBlong * bBlong;
    Z = distanceB * distanceB - distanceC * distanceC - bBlat * bBlat - bBlong * bBlong + bClat * bClat + bClong * bClong;

    foundBeaconLat = (W * (bClong - bBlong) - Z * (bBlong - bAlong)) / (2 * ((bBlat - bAlat) * (bClong - bBlong) - (bClat - bBlat) * (bBlong - bAlong)));
    foundBeaconLong = (W - 2 * foundBeaconLat * (bBlat - bAlat)) / (2 * (bBlong - bAlong));
    //`foundBeaconLongFilter` is a second measure of `foundBeaconLong` to mitigate errors
    foundBeaconLongFilter = (Z - 2 * foundBeaconLat * (bClat - bBlat)) / (2 * (bClong - bBlong));

    foundBeaconLong = (foundBeaconLong + foundBeaconLongFilter) / 2;

    Location foundLocation = new Location("Location");
        foundLocation.setLatitude(foundBeaconLat);
        foundLocation.setLongitude(foundBeaconLong);

    return foundLocation;
}

Answer 5

次のアルゴリズムを書いた私のアーキテクト/マネージャーは、

public static Location getLocationWithCenterOfGravity(Location beaconA, Location beaconB, Location beaconC, double distanceA, double distanceB, double distanceC) {

    //Every meter there are approx 4.5 points
    double METERS_IN_COORDINATE_UNITS_RATIO = 4.5;

    //http://stackoverflow.com/a/524770/663941
    //Find Center of Gravity
    double cogX = (beaconA.getLatitude() + beaconB.getLatitude() + beaconC.getLatitude()) / 3;
    double cogY = (beaconA.getLongitude() + beaconB.getLongitude() + beaconC.getLongitude()) / 3;
    Location cog = new Location("Cog");
    cog.setLatitude(cogX);
    cog.setLongitude(cogY);


    //Nearest Beacon
    Location nearestBeacon;
    double shortestDistanceInMeters;
    if (distanceA < distanceB && distanceA < distanceC) {
        nearestBeacon = beaconA;
        shortestDistanceInMeters = distanceA;
    } else if (distanceB < distanceC) {
        nearestBeacon = beaconB;
        shortestDistanceInMeters = distanceB;
    } else {
        nearestBeacon = beaconC;
        shortestDistanceInMeters = distanceC;
    }

    //http://www.mathplanet.com/education/algebra-2/conic-sections/distance-between-two-points-and-the-midpoint
    //Distance between nearest beacon and COG
    double distanceToCog = Math.sqrt(Math.pow(cog.getLatitude() - nearestBeacon.getLatitude(),2)
            + Math.pow(cog.getLongitude() - nearestBeacon.getLongitude(),2));

    //Convert shortest distance in meters into coordinates units.
    double shortestDistanceInCoordinationUnits = shortestDistanceInMeters * METERS_IN_COORDINATE_UNITS_RATIO;

    //http://math.stackexchange.com/questions/46527/coordinates-of-point-on-a-line-defined-by-two-other-points-with-a-known-distance?rq=1
    //On the line between Nearest Beacon and COG find shortestDistance point apart from Nearest Beacon

    double t = shortestDistanceInCoordinationUnits/distanceToCog;

    Location pointsDiff = new Location("PointsDiff");
    pointsDiff.setLatitude(cog.getLatitude() - nearestBeacon.getLatitude());
    pointsDiff.setLongitude(cog.getLongitude() - nearestBeacon.getLongitude());

    Location tTimesDiff = new Location("tTimesDiff");
    tTimesDiff.setLatitude( pointsDiff.getLatitude() * t );
    tTimesDiff.setLongitude(pointsDiff.getLongitude() * t);

    //Add t times diff with nearestBeacon to find coordinates at a distance from nearest beacon in line to COG.

    Location userLocation = new Location("UserLocation");
    userLocation.setLatitude(nearestBeacon.getLatitude() + tTimesDiff.getLatitude());
    userLocation.setLongitude(nearestBeacon.getLongitude() + tTimesDiff.getLongitude());

    return userLocation;
}

1. 三角形の重心を計算する (3 つのビーコン)
2. 最短距離/最寄りのビーコンを計算する
3. ビーコンと重心の距離を計算する
4. 最短距離を単なる定数である座標単位に変換します。彼は精度を予測するために使用しました。定数を変化させてテストできます
5. 距離デルタを計算する
6. 最も近いビーコン x、y でデルタを追加します。

テストした後、5メートルまで正確であることがわかりました。

テストを改善できる場合は、コメントしてください。

Answer 6

Android 4.4用の非常に単純な指紋アルゴリズムを実装し、相対的な「悪い」環境でテストしました：

• 近くに 10 台近くの Wi-Fi AP があります。
• 他のいくつかの Bluetooth 信号が近くにあります。

正確な距離は 5 ～ 8 メートルで、3 つの Ibeacon ブロードキャスターをどのように配置したかによって異なります。アルゴリズムは非常に単純で、自分で実装できると思います。手順は次のとおりです。

1. インドア マップを読み込みます。
2. すべての保留中の測位ポイントのマップを使用してサンプリングします。
3. すべてのサンプリング データを記録します。データには、マップ座標、位置信号、およびそれらの RSSI が含まれている必要があります。

したがって、ポジショニングを開始するときは、手順を逆にするだけです。

Answer 7

私を本当に助けてくれたのは、Code.Google.com のこのプロジェクトでした: https://code.google.com/p/wsnlocalizationscala/ これには、すべて C# で記述された多くのコード、いくつかの三辺測量アルゴリズムが含まれています。これは大きなライブラリですが、「そのまま」使用することを意図したものではありません。

Answer 8

また、iBeacons を使用して部屋にいる人の位置を正確に特定する最善の方法を見つけようとしています。問題は、ビーコン信号の電力が一定ではなく、他の 2.4 GHz 信号や金属物体などの影響を受けるため、最大の精度を達成するには、各ビーコンを個別に調整し、目的の位置に設定したら、ビーコンを個別に調整する必要があることです。 . (そして、他の Bluetooth デバイスが存在する場合の信号の変動を確認するためにフィールド テストを行います)。また、Estimote の iBeacon (Konrad Dzwinel のビデオと同じもの) もあり、iBeacons で何ができるかの技術デモを既に開発しています。彼らのアプリ内では、iBeacon が表示されるレーダーを見ることができます。かなり正確な場合もあれば、そうでない場合もあります (また、位置を計算するために電話の動きが考慮されていないようです)。http://goo.gl/98hiza

理論上は 3 つの iBeacon で十分な精度が得られるはずですが、実際の状況では、求めている精度を確保するにはさらに多くのビーコンが必要になる場合があります。

Answer 9

Vishnu Prahbu のソリューションが非常に役立つことがわかりました。誰かがそれを必要とするなら、私はそれをc＃に移植しました。

public static PointF GetLocationWithCenterOfGravity(PointF a, PointF b, PointF c, float dA, float dB, float dC)
    {
        //http://stackoverflow.com/questions/20332856/triangulate-example-for-ibeacons
        var METERS_IN_COORDINATE_UNITS_RATIO = 1.0f;

        //http://stackoverflow.com/a/524770/663941
        //Find Center of Gravity
        var cogX = (a.X + b.X + c.X) / 3;
        var cogY = (a.Y + b.Y + c.Y) / 3;
        var cog = new PointF(cogX,cogY);

        //Nearest Beacon
        PointF nearestBeacon;
        float shortestDistanceInMeters;
        if (dA < dB && dA < dC)
        {
            nearestBeacon = a;
            shortestDistanceInMeters = dA;
        }
        else if (dB < dC)
        {
            nearestBeacon = b;
            shortestDistanceInMeters = dB;
        }
        else
        {
            nearestBeacon = c;
            shortestDistanceInMeters = dC;
        }

        //http://www.mathplanet.com/education/algebra-2/conic-sections/distance-between-two-points-and-the-midpoint
        //Distance between nearest beacon and COG
        var distanceToCog =  (float)(Math.Sqrt(Math.Pow(cog.X - nearestBeacon.X, 2)
                + Math.Pow(cog.Y - nearestBeacon.Y, 2)));

        //Convert shortest distance in meters into coordinates units.
        var shortestDistanceInCoordinationUnits = shortestDistanceInMeters * METERS_IN_COORDINATE_UNITS_RATIO;

        //http://math.stackexchange.com/questions/46527/coordinates-of-point-on-a-line-defined-by-two-other-points-with-a-known-distance?rq=1
        //On the line between Nearest Beacon and COG find shortestDistance point apart from Nearest Beacon
        var t = shortestDistanceInCoordinationUnits / distanceToCog;
        var pointsDiff = new PointF(cog.X - nearestBeacon.X, cog.Y - nearestBeacon.Y);
        var tTimesDiff = new PointF(pointsDiff.X * t, pointsDiff.Y * t);

        //Add t times diff with nearestBeacon to find coordinates at a distance from nearest beacon in line to COG.
        var userLocation = new PointF(nearestBeacon.X + tTimesDiff.X, nearestBeacon.Y + tTimesDiff.Y);

        return userLocation;
    }

Answer 10

代替方程式

- (CGPoint)getCoordinateWithBeaconA:(CGPoint)a beaconB:(CGPoint)b beaconC:(CGPoint)c distanceA:(CGFloat)dA distanceB:(CGFloat)dB distanceC:(CGFloat)dC {


CGFloat x, y;
x = ( ( (pow(dA,2)-pow(dB,2)) + (pow(c.x,2)-pow(a.x,2)) + (pow(b.y,2)-pow(a.y,2)) ) * (2*c.y-2*b.y) - ( (pow(dB,2)-pow(dC,2)) + (pow(c.x,2)-pow(c.x,2)) + (pow(c.y,2)-pow(b.y,2)) ) *(2*b.y-2*a.y) ) / ( (2*b.x-2*c.x)*(2*b.y-2*a.y)-(2*a.x-2*b.x)*(2*c.y-2*b.y) );

y = ( (pow(dA,2)-pow(dB,2)) + (pow(c.x,2)-pow(a.x,2)) + (pow(b.y,2)-pow(a.y,2)) + x*(2*a.x-2*b.x)) / (2*b.y-2*a.y);



return CGPointMake(x, y);
}