Beispiel für iBeacons triangulieren

Ich prüfe die Möglichkeit, mehrere iBeacons zu verwenden, um eine "raue" Position in Innenräumen zu erreichen. Die Anwendung ist eine Art "Museums" -Einstellung, und es wäre einfacher, ein Raster mit Positionen für die verschiedenen Objekte als einzelne Beacons zu bilden (obwohl dies möglicherweise auch nicht unmöglich ist).

Gibt es Beispiele, Erfahrungen mit der Verwendung mehrerer Beacons zum Triangulieren an einen bestimmten Ort oder eine Logik, die mir beim Schreiben selbst hilft?

Ich habe einige Experimente durchgeführt, um mit drei Leuchtfeuern eine genaue Position zu erhalten.

Ergebnisse der Trilateration

Leider waren die Ergebnisse qualitativ sehr enttäuschend. Es gab hauptsächlich zwei Probleme:

1. In nicht kontrollierten Umgebungen, in denen Sie Metalle und andere Objekte finden, die das Signal beeinflussen, ändert sich die empfangene Signalstärke der Beacons so oft, dass es unmöglich erscheint, eine Fehlerreichweite unter 5 Metern zu erreichen.
2. Abhängig von der Art und Weise, wie der Benutzer mit dem Empfängergerät umgeht, können sich auch die Messwerte stark ändern. Wenn der Benutzer seine Hand über die Bluetooth-Antenne legt, hat der Algorithmus niedrige Signale als Eingabe, und daher sollten die Beacons sehr weit vom Gerät entfernt sein. In diesem Bild sehen Sie den genauen Standort der Bluetooth-Antenne.

Mögliche Lösungen

Nachdem ich mit einem Apple-Ingenieur gesprochen habe, der mich aktiv davon abgehalten hat, diesen Weg zu gehen, ist die Option, die ich derzeit eher nutzen möchte, Brute Force. Versuchen Sie, alle X Meter ein Beacon einzurichten (X ist der maximale Fehler, der im System toleriert wird), damit wir auf diesem Beacons-Raster die Position eines bestimmten Geräts verfolgen können, indem wir berechnen, welches Beacon auf dem Raster dem Gerät am nächsten liegt, und dies annehmen Das Gerät befindet sich in derselben Position.

Trilaterationsalgorithmus

Der Vollständigkeit halber teile ich jedoch unten die Kernfunktion des Trilaterationsalgorithmus. Es basiert auf Absatz 3 ("Drei Entfernungen bekannt") dieses Artikels .

- (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);
}

Hier ist eine Open-Source-Java-Bibliothek, die die Trilateration / Multilateration durchführt: https://github.com/lemmingapex/Trilateration

Es verwendet einen beliebten nichtlinearen Optimierer für kleinste Quadrate, den Levenberg-Marquardt-Algorithmus von Apache Commons Math.

double[][] positions = new double[][] { { 5.0, -6.0 }, { 13.0, -15.0 }, { 21.0, -3.0 }, { 12.42, -21.2 } };
double[] distances = new double[] { 8.06, 13.97, 23.32, 15.31 };

NonLinearLeastSquaresSolver solver = new NonLinearLeastSquaresSolver(new TrilaterationFunction(positions, distances), new LevenbergMarquardtOptimizer());
Optimum optimum = solver.solve();

// the answer
double[] calculatedPosition = optimum.getPoint().toArray();

// error and geometry information
RealVector standardDeviation = optimum.getSigma(0);
RealMatrix covarianceMatrix = optimum.getCovariances(0);

Die meisten wissenschaftlichen Beispiele, wie das auf Wikipedia , behandeln genau drei Kreise und setzen vollkommen genaue Informationen voraus. Diese Umstände ermöglichen viel einfachere Problemformulierungen mit genauen Antworten und sind für praktische Situationen normalerweise nicht zufriedenstellend.

Das Problem im euklidischen Raum R ² oder R ³ mit Abständen, die Messfehler, eine Fläche (Ellipse) oder ein Volumen (Ellipsoid) von Interesse enthalten, wird normalerweise anstelle eines Punktes erhalten. Wenn anstelle einer Region eine Punktschätzung gewünscht wird, sollte der Flächen- oder Volumenschwerpunkt verwendet werden. Der R ² -Raum erfordert mindestens 3 nicht entartete Punkte und Abstände, um eine eindeutige Region zu erhalten. und in ähnlicher Weise erfordert der R ³ -Raum mindestens 4 nicht entartete Punkte und Abstände, um eine eindeutige Region zu erhalten.

Ich habe das untersucht. Der Begriff, den Sie wollen, ist Trilateration. (In der Triangulation haben Sie Winkel von 3 bekannten Punkten. In der Trilateration haben Sie Abstand von 3 bekannten Punkten.) Wenn Sie es googeln, sollten Sie mehrere Artikel finden, darunter einen im Wiki. Es beinhaltet das Lösen eines Satzes von 3 simultanen Gleichungen. Die Dokumente, die ich gesehen habe, waren für die 3D-Trilateration gedacht - 2D ist einfacher, weil Sie einfach den Z-Term löschen können.

Was ich fand, war abstrakte Mathematik. Ich habe mir noch nicht die Zeit genommen, den allgemeinen Algorithmus in bestimmten Code abzubilden, aber ich habe vor, ihn irgendwann anzugehen.

Beachten Sie, dass die Ergebnisse, die Sie erhalten, SEHR grob sind, insbesondere in einem anderen als einem leeren Raum. Die Signale sind schwach genug, dass eine Person, eine Statue oder irgendetwas, das die Sichtlinie blockiert, Ihre Entfernungswerte erheblich erhöht. Möglicherweise haben Sie sogar Orte in einem Gebäude, an denen konstruktive Eingriffe (meistens von den Wänden) dazu führen, dass einige Orte so viel näher gelesen werden, als sie tatsächlich sind.

Eine genaue Positionierung in Innenräumen mit iBeacon ist aus folgenden Gründen eine Herausforderung:

1. Wie bereits in früheren Kommentaren erwähnt, schwankt das iBeacon-Signal tendenziell stark. Der Grund ist Multipath , die dynamischen Objekthindernisse zwischen dem Telefon und iBeacon, wenn sich die Person bewegt, andere 2,4-GHz-Interferenzen und vieles mehr. Idealerweise möchten Sie also nicht den Daten eines einzelnen Pakets vertrauen und stattdessen eine Mittelung für mehrere Pakete von demselben Beacon durchführen. Dies würde erfordern, dass sich die Telefon- / Beacon-Entfernung zwischen diesen verschiedenen Paketen nicht zu stark ändert. Für allgemeine BLE-Pakete (wie Beacons von StickNFind) kann problemlos eine Beaconing-Rate von 10 Hz eingestellt werden. Für iBeacon wird das jedoch schwierig, weil
2. Die Beaconing-Frequenz von iBeacon kann wahrscheinlich nicht höher als 1 Hz sein. Ich würde mich freuen, wenn jemand auf eine Quelle verweisen kann, die etwas anderes sagt, aber alle Informationen, die ich bisher gesehen habe, bestätigen diese Behauptung. Dies ist tatsächlich sinnvoll, da die meisten iBeacons batteriebetrieben sind und hohe Frequenzen die Batterielebensdauer erheblich beeinträchtigen. Wenn man bedenkt, dass die durchschnittliche Gehgeschwindigkeit der Menschen 5,3 km (~ 1,5 m / s) beträgt, ist es schwierig, eine Genauigkeit von ~ 5 m zu erreichen, selbst wenn Sie nur bescheidene 3-Beacon-Pakete für die Mittelwertbildung verwenden.

Auf der anderen Seite, wenn Sie könnten IBeacon Frequenz größer als 10 Hz erhöhen (was ich kann zweifeln), dann ist es möglich zu haben 5m oder höhere Genauigkeit geeignete Verarbeitungsverfahren. Erstens sind triviale Lösungen, die auf dem Inverse-Square-Gesetz basieren , wie die Trilateration, oft nicht gut, da in der Praxis die Distanz / RSSI-Beziehung für verschiedene Beacons aus dem obigen Grund oft weit vom Inverse-Sqare-Gesetz entfernt ist. Solange der RSSI für ein bestimmtes Beacon an einem bestimmten Ort relativ stabil ist (was normalerweise der Fall ist), können Sie einen Ansatz verwenden, der als Fingerabdruck bezeichnet wird , um eine höhere Genauigkeit zu erzielen. Eine übliche Methode für den Fingerabdruck ist kNN ( k-Nearest Neighbor ).

Update 2014-04-24

Einige iBeacons können mehr als 1 Hz senden, z. B. Estimote verwendet standardmäßig 5 Hz. Laut diesem Link jedoch : " Dies ist eine Apple-Einschränkung. IOS gibt jede Sekunde ein Beacons-Update zurück, unabhängig davon, wie häufig das Gerät Werbung macht. " Es gibt einen weiteren Kommentar gibt (wahrscheinlich aus dem Estimote Anbieter) sagen : „ Unsere Baken viel schneller übertragen können und es können Ergebnisse und Messung verbessern “. Ob eine höhere iBeacon-Frequenz von Vorteil ist, ist nicht klar.

Wenn Sie so etwas wie ich sind und keine Mathematik mögen, möchten Sie vielleicht schnell nach "Indoor Positioning SDK" suchen. Es gibt viele Unternehmen, die Indoor-Positionierung als Service anbieten.

Schamloser Stecker: Ich arbeite für indoo.rs und kann diesen Service empfehlen. Es umfasst auch das Routing und dergleichen zusätzlich zur "nur" Innenpositionierung.

Für diejenigen, die eine @Javier ChávarriTrilaterationsfunktion für AndroidGeräte benötigen (um Zeit zu sparen):

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;
}

Mein Architekt / Manager, der den folgenden Algorithmus geschrieben hat:

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. Berechnen Sie den Schwerpunkt für ein Dreieck (3 Leuchtfeuer)
2. Berechnen Sie die kürzeste Entfernung / das nächste Leuchtfeuer
3. Berechnen Sie den Abstand zwischen dem Leuchtfeuer und dem Schwerpunkt
4. Konvertieren Sie den kürzesten Abstand in Koordinateneinheiten, die nur eine Konstante sind. Er hat die Genauigkeit vorhergesagt. Sie können testen, indem Sie die Konstante variieren
5. Berechnen Sie das Distanzdelta
6. Addiere das Delta mit dem nächsten Leuchtfeuer x, y.

Nachdem ich es getestet hatte, fand ich es auf 5 Meter genau.

Bitte kommentieren Sie mir Ihre Tests, wenn wir sie verfeinern können.

Ich habe einen sehr einfachen Fingerabdruck- Algorithmus für Android 4.4 implementiert , der in einer relativ "schlechten" Umgebung getestet wurde:

• Fast 10 WiFi AP in der Nähe.
• mehrere andere Bluetooth-Signale in der Nähe.

Die Genauigkeit scheint in 5-8 Metern und hängt davon ab, wie ich diesen 3 Ibeacon-Sender platziert habe. Der Algorithmus ist recht einfach und ich denke, Sie können einen selbst implementieren. Die Schritte sind:

1. Laden Sie die Indoor-Karte.
2. Abtastung mit der Karte für alle anstehenden Positionierungspunkte.
3. Zeichnen Sie alle Abtastdaten auf. Die Daten sollten Folgendes enthalten: Kartenkoordinate, Positionssignale und deren RSSI.

Wenn Sie mit der Positionierung beginnen, ist dies nur eine Umkehrung der Schritte.

Wir versuchen auch, mit iBeacons den besten Weg zu finden, um jemanden in einem Raum genau zu lokalisieren. Die Sache ist, dass die Beacon-Signalleistung nicht konstant ist und von anderen 2,4-GHz-Signalen, Metallgegenständen usw. beeinflusst wird. Um maximale Präzision zu erreichen, ist es notwendig, jedes Beacon einzeln zu kalibrieren und sobald es in die gewünschte Position gebracht wurde . (und machen Sie einen Feldtest, um Signalschwankungen festzustellen, wenn andere Bluetooth-Geräte vorhanden sind). Wir haben auch einige iBeacons von Estimote (das gleiche wie das Video von Konrad Dzwinel), und sie haben bereits eine technische Demo entwickelt, was mit den iBeacons gemacht werden kann. In ihrer App ist es möglich, ein Radar zu sehen, in dem iBeacons angezeigt werden. Manchmal ist es ziemlich genau, aber manchmal nicht (und es scheint, dass Telefonbewegungen nicht berücksichtigt werden, um Positionen zu berechnen).http://goo.gl/98hiza

Obwohl theoretisch 3 iBeacons ausreichen sollten, um eine gute Präzision zu erzielen, werden in realen Situationen möglicherweise mehr Beacons benötigt, um die gewünschte Präzision sicherzustellen.

Was mir wirklich geholfen hat, war dieses Projekt auf Code.Google.com: https://code.google.com/p/wsnlocalizationscala/. Es enthält viel Code, mehrere Trilaterationsalgorithmen, alle in C # geschrieben. Es ist eine große Bibliothek, aber nicht wirklich dazu gedacht, "out-of-the-box" verwendet zu werden.

Bitte überprüfen Sie die Referenz https://proximi.io/accurate-indoor-positioning-bluetooth-beacons/

Das Proximi SDK kümmert sich um die Triangulation. Dieses SDK bietet Bibliotheken zur automatischen Verarbeitung der gesamten Logik für die Beacon-Positionierung, Triangulation und Filterung im Hintergrund. Zusätzlich zu Beacons können Sie IndoorAtlas, Wi-Fi, GPS und Mobilfunkpositionierung kombinieren.

Ich fand die Lösung von Vishnu Prahbu sehr nützlich. Ich habe es auf c # portiert, wenn jemand es braucht.

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;
    }

Alternative Gleichung

- (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);
}