iBeacons的三角测量示例

Question

我正在研究使用多个iBeacons来做一个"粗略"的室内位置的可能性.该应用程序是一种"博物馆"设置,并且能够更容易地形成具有不同对象的位置的网格,然后是单独的信标(尽管这也许不是不可能的).

有没有例子,经验,使用多个信标进行三角测量到某种位置,或者是一些逻辑来帮助我自己编写它的方式？

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库,它将执行trilateration/multilateration:https: //github.com/lemmingapex/Trilateration

它使用了一种流行的非线性最小二乘优化器,Levenberg-Marquardt算法,来自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);

大多数学术性的例子,如维基百科上的例子,只涉及三个圆圈,并假设完全准确的信息.这些情况允许具有精确答案的更简单的问题公式,并且在实际情况下通常不令人满意.

通常获得R ²或R ³欧几里德空间中包含测量误差,面积(椭圆)或体积(椭圆体)的距离而不是点的问题.如果需要点估计而不是区域,则应使用区域质心或体积质心.R ²空间需要至少3个非简并点和距离才能获得一个独特的区域; 类似地,R ³空间需要至少4个非简并点和距离以获得唯一区域.

Answer 3

我调查了这个.你想要它三分法的术语.(在三角测量中,你有3个已知点的角度.在三角测量中你有3个已知点的距离)如果你谷歌你应该找到几篇文章,包括一个在维基上.它涉及求解一组3个联立方程.我看到的文件是3D三边测量 - 2D更容易,因为你可以放弃Z术语.

我发现的是抽象数学.我还没有花时间将一般算法映射到特定代码,但我计划在某个时候处理它.

请注意,您获得的结果将非常粗糙,特别是在空房间以外的任何地方.信号很弱,一个人,一个雕像或任何阻挡视线的东西都会显着增加你的距离读数.你甚至可能在建筑物中有一些地方,建设性的干扰(主要来自墙壁)使得一些地方的阅读距离实际上更近.

Answer 4

由于以下原因,使用iBeacon进行准确的室内定位将具有挑战性:

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

另一方面,如果你可以将iBeacon频率提高到大于10Hz(我怀疑是可能的话),那么使用合适的处理方法可以达到5m或更高的精度.首先,基于反平方定律的平凡解决方案,如三边测量,往往表现不佳,因为在实践中,由于上述原因,不同信标的距离/ RSSI关系通常偏离逆Sqare定律.但只要RSSI对于任何特定位置的某个信标(通常是这种情况)相对稳定,您就可以使用称为指纹识别的方法来实现更高的准确性.用于指纹识别的常用方法是kNN(k-最近邻).

更新2014-04-24

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

Answer 5

如果你像我一样,不喜欢数学,你可能想快速搜索"室内定位sdk".有很多公司提供室内定位服务.

无耻的插件:我为indoo.rs工作,可以推荐这项服务.它还包括路由等"仅"室内定位.

Answer 6

对于那些需要设备@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 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. 将最短距离转换为坐标单位,这只是一个常数,他用来预测准确性.您可以使用varing常量进行测试
5. 计算距离delta
6. 使用最近的信标x,y添加增量.

经过测试,我发现它精确到5米.

如果我们可以改进它,请评论您的测试.