bluetooth-lowenergy - iBeacons 的三角剖分示例

Question

我正在研究使用多个 iBeacon 进行“粗略”室内定位的可能性。该应用程序是一种“博物馆”设置，并且能够更容易地形成具有不同对象位置的网格，然后是单个信标（尽管这也可能不是不可能的）。

有没有使用多个信标三角定位到某种位置的示例、经验，或者一些逻辑来帮助我自己编写它？

Answer 1

我一直在做一些实验来使用三个信标来获得精确的位置。

三边测量结果

不幸的是，结果在质量方面非常令人失望。主要有两个问题：

1. 在非受控环境中，您会发现金属和其他影响信号的物体，信标接收到的信号强度变化如此频繁，以至于似乎不可能将误差范围控制在 5 米以下。
2. 根据用户处理接收器设备的方式，读数也会发生很大变化。如果用户将他/她的手放在蓝牙天线上，那么算法将有低信号作为输入，因此信标应该离设备很远。请参阅此图像以查看蓝牙天线的精确位置。

可能的解决方案

在与一位积极劝阻我走这条路的苹果工程师交谈后，我觉得现在更倾向于使用的选项是蛮力。尝试每 X 米设置一个信标（X 是系统中允许的最大误差），这样我们就可以通过计算网格上哪个信标最接近设备并假设在这个信标网格上跟踪给定设备的位置设备在同一位置。

三边测量算法

但是，为了完整起见，我在下面分享三边测量算法的核心功能。它基于本文的第 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

这是一个将执行三边测量/多边测量的开源 java 库： https ://github.com/lemmingapex/Trilateration

它使用来自 Apache Commons Math 的流行的非线性最小二乘优化器 Levenberg-Marquardt 算法。

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

大多数学术示例，例如wikipedia上的示例，恰好处理三个圆圈并假设信息完全准确。这些情况允许更简单的问题公式和精确的答案，并且通常不能满足实际情况。

距离包含测量误差的 R ²或 R ^{3欧几里得空间中的问题，通常获得感兴趣的面积（椭圆）或体积（椭圆体）而不是点。}如果需要点估计而不是区域，则应使用面积质心或体积质心。R ²空间需要至少3个非退化点和距离才能获得唯一区域；同样，R ³空间需要至少 4 个非退化点和距离才能获得唯一区域。

Answer 3

我调查了这个。您想要三边测量的术语。（在三角测量中，您有来自 3 个已知点的角度。在三边测量中，您有与 3 个已知点的距离）如果您使用 Google 搜索，您应该会找到几篇文章，包括 Wiki 上的一篇文章。它涉及求解一组 3 个联立方程。我看到的文件是 3D 三边测量的 - 2D 更容易，因为你可以去掉 Z 项。

我发现的是抽象数学。我还没有花时间将通用算法映射到特定代码中，但我计划在某个时候解决它。

请注意，您得到的结果将非常粗糙，尤其是在除了空房间之外的任何地方。信号非常微弱，以至于一个人、一座雕像或任何阻挡视线的东西都会显着增加您的距离读数。您甚至可能在建筑物中的某些地方存在建设性干扰（主要来自墙壁），使某些地方的阅读距离比实际距离更近。

Answer 4

使用 iBeacon 进行准确的室内定位将具有挑战性，原因如下：

1. 正如前面评论中所指出的，iBeacon 信号往往波动很大。原因包括多径效应、人移动时手机和 iBeacon 之间的动态物体障碍、其他 2.4GHz 干扰等等。因此，理想情况下，您不想信任 1 个单个数据包的数据，而是对来自同一个信标的多个数据包进行一些平均。这将要求电话/信标距离在这几个数据包之间没有太大变化。对于一般的 BLE 数据包（如来自 StickNFind 的信标）可以轻松设置为 10Hz 信标速率。但是对于 iBeacon 来说，这会很困难，因为
2. iBeacon 的信标频率可能不能高于 1Hz。如果有人能指出另有说明的来源，我会很高兴，但到目前为止我所看到的所有信息都证实了这一说法。这实际上是有道理的，因为大多数 iBeacon 将由电池供电，并且高频会显着影响电池寿命。考虑到人们的平均步行速度是5.3km（~1.5m/s），所以即使你只使用适度的 3 个信标包进行平均，你也很难获得 ~5m 的精度。

另一方面，如果您可以将 iBeacon 频率提高到大于 10Hz（我怀疑这是可能的），那么使用合适的处理方法可以达到 5m 或更高的精度。首先，基于平方反比定律的简单解决方案（如三边测量）通常表现不佳，因为在实践中，由于上述原因 1，不同信标的距离/RSSI 关系通常与平方反比定律相差甚远。但是只要RSSI对于任何特定位置的特定信标相对稳定（通常是这种情况），您就可以使用一种称为指纹的方法来实现更高的准确度。用于指纹识别的常用方法是 kNN（k-Nearest Neighbor）。

2014-04-24 更新

一些 iBeacons可以广播超过 1Hz，例如 Estimote 默认使用 5Hz。但是，根据此链接：“这是Apple限制。无论设备广告的频率如何，IOS都会每秒返回信标更新。 ”。那里还有另一条评论（可能来自 Estimote 供应商）说“我们的信标可以更快地广播，它可能会改善结果和测量”。因此，较高的 iBeacon 频率是否有益尚不清楚。

Answer 5

对于那些需要设备@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 6

如果你和我一样不喜欢数学，你可能想快速搜索“室内定位 sdk”。有很多公司提供室内定位服务。

无耻插件：我为indoo.rs工作，可以推荐这项服务。它还包括“仅”室内定位之上的路由等。

Answer 7

我的架构师/经理，他编写了以下算法，

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 8

我为 android 4.4 实现了一个非常简单的指纹算法，在相对“糟糕”的环境中进行了测试：

• 附近有近 10 个 wifi AP。
• 附近还有其他几个蓝牙信号。

准确的似乎是 5-8 米，这取决于我如何放置 3 个 Ibeacon 广播器。该算法非常简单，我认为您可以自己实现一个，步骤是：

1. 加载室内地图。
2. 使用地图对所有待定定位点进行采样。
3. 记录所有采样数据，数据应包括：地图坐标、位置信号及其RSSI。

因此，当您开始定位时，这只是进行步骤的逆向。

Answer 9

真正帮助我的是 Code.Google.com 上的这个项目：https ://code.google.com/p/wsnlocalizationscala/ 它包含大量代码，几个三边测量算法，全部用 C# 编写。这是一个很大的库，但并不是真的要“开箱即用”地使用。

Answer 10

我们还试图找到使用 iBeacons 将某人精确定位到房间中的最佳方法。问题是信标信号功率不是恒定的，它会受到其他 2.4 Ghz 信号、金属物体等的影响，因此为了达到最大精度，需要单独校准每个信标，并且一旦将其设置在所需位置. （并进行一些现场测试以查看存在其他蓝牙设备时的信号波动）。我们还有一些来自 Estimote 的 iBeacon（与 Konrad Dzwinel 的视频相同），他们已经开发了一些关于 iBeacons 可以做什么的技术演示。在他们的应用程序中，可以看到显示 iBeacons 的雷达。有时是相当准确的，但有时不是，（似乎手机移动不被考虑计算位置）。http://goo.gl/98hiza

虽然理论上 3 个 iBeacon 应该足以实现良好的精度，但在现实世界中，可能需要更多的信标来确保您正在寻找的精度。

Answer 11

请查看参考https://proximi.io/accurate-indoor-positioning-bluetooth-beacons/

Proximi SDK 将负责三角测量。该 SDK 提供了用于在后台自动处理信标定位、三角测量和过滤的所有逻辑的库。除了信标之外，您还可以结合使用 IndoorAtlas、Wi-Fi、GPS 和蜂窝定位。

Answer 12

我发现 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 13

替代方程

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