Exemple de triangulation pour iBeacons

j'ai fait quelques expériences pour obtenir une position précise en utilisant trois balises.

résultats de la trilatération

Malheureusement, les résultats ont été très décevants en termes de qualité. Il y avait principalement deux questions:

1. dans les environnements non contrôlés, où vous pouvez trouver des métaux, et d'autres objets qui affectent le signal, la force du signal reçu des balises change de façon souvent qu'il semble impossible d'obtenir la portée d'erreur en dessous de 5 mètres.
2. selon la façon dont l'utilisateur manipule l'appareil récepteur, les lectures peuvent changer beaucoup aussi bien. Si l'utilisateur met sa main sur l'antenne bluetooth, puis l'algorithme ont de faibles signaux d'entrée, et donc les balises censé être très loin de l'appareil. Voir cette image pour voir l'emplacement précis de l'antenne Bluetooth.

solutions possibles

après avoir parlé avec un ingénieur Apple qui m'a activement découragé de passer par là, l'option que je me sens plus enclin à utiliser maintenant est la force brute. Essayez de mettre en place une balise tous les X mètres (X étant l'erreur maximale tolérée dans le système) afin que nous puissions suivre sur cette grille de balises La position d'un appareil donné en calculant quelle balise sur la grille est la plus proche de l'appareil et en supposant que le l'appareil est sur la même position.

algorithme de trilatération

cependant, par souci d'exhaustivité, je partage ci-dessous la fonction principale de l'algorithme de trilatération. Il est basé sur le paragraphe 3 ("trois distances connues") de cet article .

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

Voici une bibliothèque java open source qui effectuera la trilatération / multilatération: https://github.com/lemmingapex/Trilateration

utilise un optimiseur de moindres carrés non linéaire populaire, l'algorithme de Levenberg-Marquardt, D'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);

la plupart des exemples savants, comme celui sur wikipedia , traitent exactement de trois cercles et supposent des informations parfaitement exactes. Ces circonstances permettent des formulations de problèmes beaucoup plus simples avec des réponses exactes, et ne sont généralement pas satisfaisantes pour les situations pratiques.

le problème dans R ² ou R ³ espace euclidien avec des distances qui contiennent une erreur de mesure, une zone (ellipse) ou un volume (ellipsoïde) d'intérêt est généralement obtenu au lieu d'un point. Si l'on désire une estimation ponctuelle plutôt qu'une région, il faut utiliser le centroïde de la zone ou le centroïde du volume. R ² l'espace nécessite au moins 3 points et distances Non dégénérés pour obtenir une région unique; et de même R ³ l'espace nécessite au moins 4 points et distances non dégénérés pour obtenir une région unique.

j'ai regardé ça. Le terme que vous voulez qu'il trilatération. (Dans la triangulation vous avez des angles à partir de 3 points connus. Dans la trilatération vous avez la distance de 3 points connus) Si vous Google it vous devriez trouver plusieurs articles dont un sur Wiki. Il s'agit de résoudre un ensemble de 3 équations simultanées. Les documents que j'ai vus étaient pour la trilatération 3D - 2D est plus facile parce que vous pouvez juste laisser tomber le terme Z.

ce que j'ai trouvé était des mathématiques abstraites. Je n'ai pas pris le temps encore mappez l'algorithme général en code spécifique, mais je prévois de l'aborder à un moment donné.

notez que les résultats que vous obtiendrez seront très grossiers, surtout dans tout sauf une pièce vide. Les signaux sont assez faibles pour qu'une personne, une statue, ou tout ce qui bloque la ligne de vue augmente vos lectures de distance de façon assez significative. Vous pourriez même avoir des endroits dans un bâtiment où l'interférence constructive (principalement à partir des murs) fait lire certains endroits beaucoup plus près que ils sont en réalité.

le positionnement précis à l'intérieur avec iBeacon sera difficile pour les raisons suivantes:

1. comme indiqué dans les commentaires précédents, le signal d'iBeacon a tendance à fluctuer beaucoup. La raison comprend multipath effet, l'objet dynamique obstructions entre le téléphone et iBeacon lorsque la personne se déplace, d'autres interférences de 2,4 GHz, et plus. Donc, idéalement, vous ne voulez pas faire confiance aux données d'un seul paquet et faites plutôt une moyenne pour plusieurs paquets de la même balise. Cela nécessiterait la distance téléphone / balise ne change pas trop entre ces plusieurs paquets. Pour les paquets en général (comme les balises de StickNFind) peuvent facilement être réglés à 10Hz. Cependant pour iBeacon, ce sera difficile, parce que
2. la fréquence de clignotement d'iBeacon ne peut probablement pas être supérieure à 1Hz. Je serai heureux si quelqu'un peut indiquer la source qui dit le contraire, mais toutes les informations que j'ai vu jusqu'à présent confirme ceci affirmation. En fait, cela a du sens puisque la plupart des iBeacons seront alimentés par batterie et la haute fréquence aura un impact significatif sur la durée de vie de la batterie. Compte tenu de la vitesse moyenne de marche des gens est 5,3 km (~1,5 m/s), donc, même si vous utilisez juste un modeste pack de 3 balises pour faire la moyenne, vous serez difficile d'obtenir ~précision 5m.

d'autre part, si vous pourrait augmenter la fréquence iBeacon à plus de 10Hz (ce que je doute est possible), alors il est possible d'avoir une précision de 5m ou plus en utilisant la méthode de traitement appropriée. Tout d'abord , les solutions triviales basées sur la loi Inverse-carré , comme la trilatération, ne fonctionnent souvent pas bien parce que dans la pratique la relation distance/RSSI pour les différentes balises sont souvent loin de la loi Inverse-carré pour la raison 1 ci-dessus. Mais tant que le RSSI est relativement stable pour une certaine balise dans un certain endroit (ce qui est généralement le cas), vous peut utiliser une approche appelée empreintes digitales pour obtenir une plus grande précision. Une méthode courante utilisée pour la prise d'empreintes digitales est kNN ( K-plus proche voisin ).

mise à jour 2014-04-24

Certains iBeacons peut la diffusion de plus de 1Hz, comme Estimote utilisation 5Hz en tant que par défaut. Cependant, selon ce lien : " il s'agit D'une restriction Apple. IOS retourne des balises mettre à jour chaque seconde, peu importe la fréquence de la publicité périphérique. ". Il y a un autre commentaire là-bas (probablement de L'Estimote vendeur) disant " nos balises peuvent diffuser beaucoup plus rapidement et il mai améliorer les résultats et la mesure ". Ainsi, on ne sait pas si une fréquence plus élevée d'iBeacon est bénéfique.

si vous êtes quelque chose comme moi et que vous n'aimez pas les mathématiques, vous pourriez faire une recherche rapide pour "indoor positioning sdk". Il y a beaucoup d'entreprises qui offrent le positionnement intérieur comme un service.

Shameless plug: je travaille pour indoo.rs et peut recommander ce service. Il comprend également le routage et tels Sur le dessus de "juste" positionnement intérieur.

pour ceux qui ont besoin de @Javier Chávarri fonction de trilatération pour Android dispositifs (pour gagner du temps):

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

mon Architecte / Directeur, qui a écrit l'algorithme suivant,

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. calculez le centre de gravité d'un triangle (3 balises)
2. calculer la distance la plus courte / la balise la plus proche
3. calculer la distance entre la balise et le centre de gravité
4. convertissez la distance la plus courte en Coordonnées, ce qui est juste une constante, il a utilisé pour prédire la précision. Vous pouvez tester avec varing la constante
5. calculer la distance delta
6. ajouter le delta avec la balise x, Y.

après l'avoir testé, je l'ai trouvé précis à 5 mètres.

s'il vous Plaît commentaire m'votre test, si nous pouvons l'améliorer.

j'ai implémenté un algorithme très simple Fingerprint pour android 4.4, testé dans un environnement relatif "mauvais":

• près de 10 Accès wifi à proximité.
• plusieurs autres signaux Bluetooth à proximité.

la précision semble à 5-8 mètres et dépend de comment j'ai placé ce 3 iBeacon broadcaster. L'algorithme est assez simple et je pense que vous pouvez en œuvre un par vous-même, les étapes sont:

1. chargez la carte intérieure.
2. échantillonnage avec la carte pour tout le point de positionnement en attente.
3. enregistrer toutes les données d'échantillonnage, les données devraient inclure: coordonnées de la carte, signaux de position et leur RSSI.

donc quand vous commencez à vous positionner, c'est juste une marche arrière.

Nous essayons également de trouver la meilleure façon de localiser précisément quelqu'un dans une pièce en utilisant des iBeacons. Le problème est que la puissance du signal de la balise n'est pas constante et qu'elle est affectée par d'autres signaux 2,4 Ghz, objets métalliques, etc., de sorte que pour obtenir un maximum de précision, il est nécessaire de calibrer chaque balise individuellement, et une fois qu'elle a été placée dans la position désirée. (et faire quelques essais sur le terrain pour voir les fluctuations du signal lorsque D'autres dispositifs Bluetooth sont présents). Nous avons aussi quelques iBeacons de Estimote (le même de la vidéo de Konrad Dzwinel), et ils ont déjà développé une démonstration technique de ce qui peut être fait avec les iBeacons. Dans leur application il est possible de voir un Radar dans lequel on montre des iBeacons. Parfois est assez précis, mais parfois il ne l'est pas, (et semble que le mouvement du téléphone n'est pas considéré pour calculer les positions). Voir la démo dans la vidéo que nous avons fait ici: http://goo.gl/98hiza

bien qu'en théorie 3 iBeacons devraient être assez pour atteindre une bonne précision, peut-être que dans des situations réelles, plus de balises sont nécessaires pour assurer la précision que vous recherchez.

la chose qui m'a vraiment aidé était ce projet sur Code.Google.com: https://code.google.com/p/wsnlocalizationscala / il contient beaucoup de code, plusieurs algorithmes de trilatération, tous écrits en C#. C'est une grande bibliothèque, mais pas vraiment destiné à être utilisé "out-of-the-box".

Veuillez vérifier la référence https://proximi.io/accurate-indoor-positioning-bluetooth-beacons/

Proximi SDK va s'occuper de la triangulation. Ce SDK fournit des bibliothèques pour manipuler toute la logique pour le positionnement de balise, la triangulation et le filtrage automatiquement dans l'arrière-plan. En plus des balises, Vous pouvez combiner IndoorAtlas, Wi-Fi, GPS et positionnement cellulaire.

j'ai trouvé la solution de Vishnu Prahbu très utile. Je l'ai porté sous c#, si quelqu'un en a besoin.

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

Équation Alternative

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