logo标签列表

iBeacon三角定位示例

bluetooth-lowenergyibeacon
77

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

是否有使用多个信标三角定位到某种位置或某种逻辑的实例和经验，可以帮助我自己编写代码？

5
请查看我的演示：https://www.youtube.com/watch?v=dMWEl6GBGqk 。在评论区中，您会发现Jakub Krzych的回复，他的公司生产了我正在使用的信标。 - Konrad Dzwinel
谢谢，这非常有用。如果Estimote将发布API，那么我可能会等待并查看它的工作方式，而不是自己研究数学，并尝试按评论中建议的方式动态校准和纠正信标。 - Luuk D. Jansen
@LuukD.Jansen 我也在关注这个问题... 有什么消息吗？ - Leonardo
我还没有进一步研究它。我认为在我需要的规模（楼层空间）上，三角定位将无法足够精确。在所有重要位置放置信标会更容易/更便宜。 - Luuk D. Jansen
13个回答
76

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

三边测量结果

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

  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);
}
2
我似乎总是得到NaN或Inf+作为我的y值。在开发算法时，你是否遇到过这种情况？ - Yazid
8
我发现当点a和点b具有相同的y坐标时，y的公式有时会出错。这是因为/(2*(b.y-a.y))这一部分会产生0，然后导致除以零错误。 - Yazid
1
这真的帮了我很多。我将这个方法转换成了Java，而且它完美地运行了。我们正在使用它工作。 - Dennis Anderson
信标的静态坐标只是它们相对于已知原点（例如，其中一个信标为0,0，其他信标相对于此表示）的米数位置吗？ - jdmunro
1
我同意这个方程式不起作用。信标设置为1.5mx2.5m，我的uiview为300x500。根据您的乘数，我的xy值落在4k像素区域内。 - jdog
显示剩余12条评论
23
这是一个开源的Java库，可以执行三角定位/多边定位: https://github.com/lemmingapex/Trilateration 它使用Apache Commons Math中流行的非线性最小二乘优化器—Levenberg-Marquardt算法。
同时还有一张图片展示了实例：

example

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

大多数学术示例（例如维基百科上的一个）涉及恰好三个圆，并假设信息完全准确。这种情况下，问题的形式更简单，有精确答案，但通常不适用于实际情况。

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

16

我进行了调查。你需要的术语是“三边测量”。（在三角测量中，你有3个已知点的角度，而在三边测量中，你有3个已知点的距离）。如果你在Google上搜索，你应该能找到几篇文章，其中一篇是Wiki上的。它涉及解决一组三元一次方程。我看到的文件都是针对3D三边测量的 - 2D更容易，因为你可以忽略Z项。

我发现的是抽象的数学知识。我还没有花时间将一般算法映射到具体代码，但我计划在某个时候着手解决它。

请注意，你得到的结果会非常粗略，特别是在除空房间以外的任何地方。信号足够弱，以至于一个人、雕像或任何挡住视线的物体都会显著增加你的距离读数。你甚至可能会在建筑物内的某些地方出现构造干涉（主要来自墙壁），使一些地方读数比实际距离更接近。

谢谢 Duncan，我会看一下的。 我知道它的缺点，但还是想测试一下。 如果能够节省在每个点上放置信标的麻烦，那么几米的准确性就足够了。 即使那是正确的方法，我也想试一下。 - Luuk D. Jansen
8
iBeacon 的精准室内定位将面临以下挑战：
如早期评论所指出的，iBeacon信号往往会波动很大。原因包括multipath效应、人在移动时手机和iBeacon之间的动态物体障碍、其他2.4GHz干扰等。因此，理想情况下，您不希望仅依赖单个数据包的数据，而是对来自同一信标的多个数据包进行一些平均处理。这将要求手机/信标之间的距离在这些数据包之间不要发生太大变化。对于普通的BLE数据包（例如StickNFind的信标），可以轻松设置为10Hz的信标速率。然而，对于iBeacon来说，这将是困难的，因为iBeacon的信标频率可能不能高于1Hz。如果有人能指出反之的来源，我会很高兴，但迄今为止我所看到的所有信息都证实了这一说法。这实际上是有意义的，因为大多数iBeacons将使用电池供电，高频率会显著影响电池寿命。考虑到人们的平均步行速度为5.3km（~1.5m/s），所以即使您只使用适度的3个信标数据包进行平均处理，也很难获得约5米的准确度。

另一方面，如果您可以将iBeacon频率提高到大于10Hz（我怀疑是否可能），则使用适当的处理方法可能可以实现5m或更高的精度。首先基于反比例定律的琐碎解决方案，如三边测量，通常表现不佳，因为在实践中，不同信标的距离/RSSI关系经常与反比例定律有很大偏差，原因是上述第1个原因。但只要RSSI在任何特定位置对于某个信标相对稳定（通常情况下是这样），您就可以使用称为指纹识别的方法来实现更高的精度。用于指纹识别的常用方法是kNN（k-最近邻）。

更新2014-04-24

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

1
不用深究，我有一组Estimote信标，默认间隔设置为200毫秒。然而，它可以设置为50毫秒（但自然会影响电池寿命）。 - Luuk D. Jansen
在这种情况下，您的iOS应用程序中是否可以看到>1Hz的测距更新？ - Penghe Geng
我不知道，我现在没有适当的代码进行测试，说实话也没有时间编写。我只是一段时间前看到了这个选项并添加了评论，但答案的更新似乎表明它并没有。 - Luuk D. Jansen
7

对于那些需要在Android设备上使用@Javier Chávarri的三边测量函数（为了节省时间）的人：

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;
}
你好， 我正在尝试你的代码，但是不理解它给我的结果？ 我有三个点：49.348657, 6.173041, 3.126米 - 49.348658, 6.172981, 5.452米 - 49.348588, 6.173028, 4.065米 在我的位置中得到的结果为：纬度始终为-90.0，而经度会根据距离而改变？ 有什么想法吗？ - Lord St John
1
检查您的三个位置点是否构成一个三角形，且它们不会形成一条直线。我正在手机上回答。一旦我在电脑上，我将测试您的位置。 - hrskrs
@LordStJohn 你尝试过其他点吗？我的意思是你总是得到那个结果吗？ - hrskrs
是的，我尝试了其他点，总是在同一栋建筑物内。始终获得相同类型的结果，纬度始终为-90.0，经度随距离变化。 - Lord St John
1
@LordStJohn 我刚刚尝试了这些统计数据：49.348657，6.173041，3.126m - 49.348658，6.172981，5.452m - 49.348588，6.173028，4.065，但它并没有给出-90。请尝试进行“调试”，确保您正在使用这些位置。 - hrskrs
显示剩余3条评论
6
如果你和我一样不喜欢数学，你可能想快速搜索“室内定位sdk”。有很多公司提供室内定位服务。
不要脸地打广告：我在indoo.rs工作，可以推荐这项服务。它还包括路由等其他功能，不仅仅是室内定位。
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;

    //https://dev59.com/jXRB5IYBdhLWcg3wv5tA#524770
    //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米。

如果我们能够进一步完善它，请评论给我您的测试结果。

1
你是如何将RSSI值转换为距离的？你是如何获取参考信标的距离的？ - Mahamutha M
4

我已经为Android 4.4实现了一个非常简单的指纹算法，在相对“恶劣”的环境下进行了测试:

  • 附近有近10个WiFi接入点。
  • 附近还有几个蓝牙信号。

精度在5-8米之间，具体取决于我放置3个Ibeacon广播器的方式。该算法非常简单，我认为您也可以自己实现，步骤如下：

  1. 加载室内地图。
  2. 对所有待处理的定位点进行地图采样。
  3. 记录所有采样数据，包括：地图坐标、位置信号以及它们的RSSI。

因此，当您开始定位时，只需要按照上述步骤反向进行即可。

你的指纹识别算法使用三边测量或其他技术吗？ - andrea.spot.
3

对我最有帮助的是Code.Google.com上的这个项目：https://code.google.com/p/wsnlocalizationscala/，其中包含大量代码、多种三边测量算法，均使用C#编写。这是一个大型库，但并不真正意味着可以“开箱即用”。

3
我们也正在尝试寻找使用iBeacons精确定位某人进入房间的最佳方式。问题在于，信标信号功率并不是恒定的，并且会受到其他2.4 GHz信号、金属物体等影响，因此要实现最大精度，需要逐个校准每个信标，并将其设置在所需位置（并进行一些现场测试以查看是否存在其他蓝牙设备时的信号波动）。
我们还有一些来自Estimote的iBeacons（与Konrad Dzwinel视频中的相同），他们已经开发了一些iBeacons的技术演示。在他们的应用程序中，可以看到显示iBeacons的雷达。有时非常准确，但有时则不太准确（似乎没有考虑手机移动来计算位置）。请在我们制作的视频中检查演示: http://goo.gl/98hiza
虽然理论上3个iBeacons就足以实现良好的精度，但在实际情况下，可能需要更多的信标来确保您所寻求的精度。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接