使用不准确的距离数据实现多线程

2018-06-30 10:47:11

我正尝试创建一款使用Apples iBeacon技术确定当前室内位置的Android智能手机应用程序。我已经设法得到所有可用的信标，并通过rssi信号计算出它们的距离。

目前我面临的问题是，我无法找到任何库或算法的实现，该算法通过使用3个（或更多）个固定点与条件的距离来计算2D中的估计位置，这些距离不准确（这意味着三个“三边圈”在一点上不相交）。

如果任何人能以任何常见编程语言（Java，C ++，Python，PHP，Javascript或其他）发布我的链接或实现，我将深表谢意。我已经阅读了很多有关该主题的stackoverflow，但找不到任何答案，我可以在代码中转换（只有一些数学方法与矩阵和反转它们，用矢量或类似的东西计算）。

编辑

我想到了一种自己的方法，对我来说效果很好，但并不那么高效和科学。我遍历位置网格的每一个米（或类似于我的例子0.1米），并通过比较该位置到所有信标的距离以及我计算的距离来计算该位置成为手机实际位置的可能性收到rssi信号。

代码示例：

public Location trilaterate(ArrayList<Beacon> beacons, double maxX, double maxY)
{
    for (double x = 0; x <= maxX; x += .1)
    {
        for (double y = 0; y <= maxY; y += .1)
        {
            double currentLocationProbability = 0;
            for (Beacon beacon : beacons)
            {
                // distance difference between calculated distance to beacon transmitter
                // (rssi-calculated distance) and current location:
                // |sqrt(dX^2 + dY^2) - distanceToTransmitter|
                double distanceDifference = Math
                    .abs(Math.sqrt(Math.pow(beacon.getLocation().x - x, 2)
                                   + Math.pow(beacon.getLocation().y - y, 2))
                         - beacon.getCurrentDistanceToTransmitter());
                // weight the distance difference with the beacon calculated rssi-distance. The
                // smaller the calculated rssi-distance is, the more the distance difference
                // will be weighted (it is assumed, that nearer beacons measure the distance
                // more accurate)
                distanceDifference /= Math.pow(beacon.getCurrentDistanceToTransmitter(), 0.9);
                // sum up all weighted distance differences for every beacon in
                // "currentLocationProbability"
                currentLocationProbability += distanceDifference;
            }
            addToLocationMap(currentLocationProbability, x, y);
            // the previous line is my approach, I create a Set of Locations with the 5 most probable locations in it to estimate the accuracy of the measurement afterwards. If that is not necessary, a simple variable assignment for the most probable location would do the job also
        }
    }
    Location bestLocation = getLocationSet().first().location;
    bestLocation.accuracy = calculateLocationAccuracy();
    Log.w("TRILATERATION", "Location " + bestLocation + " best with accuracy "
                           + bestLocation.accuracy);
    return bestLocation;
}

当然，其中的缺点是，我在300平方米的地板上必须迭代30,000个位置，并测量距离我获得信号的每个灯塔的距离（如果那是5，我只做150.000个计算，仅用于确定一个位置）。这是很多 - 所以我会让这个问题开放，并希望进一步的解决方案或对现有解决方案的改进，以使其更高效。

当然，它不一定是Trilateration方法，就像这个问题的原始标题一样，对于位置确定（Multilateration），包含超过三个信标的算法也是很好的。

如果目前的方法很好，除非速度太慢，那么可以通过递归地细分飞机来加速它。这有点像在kd树中寻找最近的邻居。假设我们有一个轴对齐的方框，并希望在方框中找到近似的最佳解决方案。如果箱子足够小，则返回中心。

否则，将盒子分成两半，按x或y取决于哪一侧较长。对于这两个半部分，如下计算解决方案质量的界限。由于目标函数是加法的，所以对每个信标求和下限。信标的下界是圆与框的距离，乘以缩放因子。以较低的下界递归地找到儿童中的最佳解决方案。只有当第一个孩子的最佳解决方案比另一个孩子的下限差时，才检查另一个孩子。

这里的大多数实现工作是盒子到圆圈的距离计算。由于框是轴对齐的，因此我们可以使用区间运算来确定从框点到圆心的精确距离。

PS： Math.hypot是计算二维欧氏距离的一个很好的函数。

考虑到个别信标的置信度，我不会考虑个别信标的置信水平，而是在用可用数据做出最佳猜测后，尝试为结果指定一个整体置信水平。我认为唯一可用的指标（感知功率）是准确度的一个很好的指标。由于几何形状不佳或行为不当，您可能会高度信任可怜的数据。根据假设您信任所有信标的方式，信标与信标的距离与计算得出的点之间的吻合程度，提出一个总体置信水平可能更有意义。

我在下面写了一些Python，根据3-beacon情况下提供的数据计算出前两个信标的两个圆的交点，然后选择最接近第三个的点。它意味着开始解决问题，而不是最终的解决方案。如果信标不相交，它会稍微增加每个信标的半径直到它们符合或达到阈值。同样，它确保第三个灯塔在可设定的阈值内达成一致。对于n-beacons，我会选择3或4个最强的信号并使用它们。有很多优化可以完成，我认为这是由于信标的笨重性质而导致的试火问题。

import math

beacons = [[0.0,0.0,7.0],[0.0,10.0,7.0],[10.0,5.0,16.0]] # x, y, radius

def point_dist(x1,y1,x2,y2):
    x = x2-x1
    y = y2-y1
    return math.sqrt((x*x)+(y*y))

# determines two points of intersection for two circles [x,y,radius]
# returns None if the circles do not intersect
def circle_intersection(beacon1,beacon2):
    r1 = beacon1[2]
    r2 = beacon2[2]
    dist = point_dist(beacon1[0],beacon1[1],beacon2[0],beacon2[1])
    heron_root = (dist+r1+r2)*(-dist+r1+r2)*(dist-r1+r2)*(dist+r1-r2)
    if ( heron_root > 0 ):
        heron = 0.25*math.sqrt(heron_root)
        xbase = (0.5)*(beacon1[0]+beacon2[0]) + (0.5)*(beacon2[0]-beacon1[0])*(r1*r1-r2*r2)/(dist*dist)
        xdiff = 2*(beacon2[1]-beacon1[1])*heron/(dist*dist) 
        ybase = (0.5)*(beacon1[1]+beacon2[1]) + (0.5)*(beacon2[1]-beacon1[1])*(r1*r1-r2*r2)/(dist*dist)
        ydiff = 2*(beacon2[0]-beacon1[0])*heron/(dist*dist) 
        return (xbase+xdiff,ybase-ydiff),(xbase-xdiff,ybase+ydiff)
    else:
        # no intersection, need to pseudo-increase beacon power and try again
        return None

# find the two points of intersection between beacon0 and beacon1
# will use beacon2 to determine the better of the two points
failing = True
power_increases = 0
while failing and power_increases < 10:
    res = circle_intersection(beacons[0],beacons[1])
    if ( res ):
        intersection = res
    else:
        beacons[0][2] *= 1.001
        beacons[1][2] *= 1.001
        power_increases += 1
        continue
    failing = False

# make sure the best fit is within x% (10% of the total distance from the 3rd beacon in this case)
# otherwise the results are too far off
THRESHOLD = 0.1

if failing:
    print 'Bad Beacon Data (Beacon0 & Beacon1 don't intersection after many "power increases")'
else:
    # finding best point between beacon1 and beacon2
    dist1 = point_dist(beacons[2][0],beacons[2][1],intersection[0][0],intersection[0][1])
    dist2 = point_dist(beacons[2][0],beacons[2][1],intersection[1][0],intersection[1][1])
    if ( math.fabs(dist1-beacons[2][2]) < math.fabs(dist2-beacons[2][2]) ):
        best_point = intersection[0]
        best_dist = dist1
    else:
        best_point = intersection[1]
        best_dist = dist2
    best_dist_diff = math.fabs(best_dist-beacons[2][2])
    if best_dist_diff < THRESHOLD*best_dist:
        print best_point
    else:
        print 'Bad Beacon Data (Beacon2 distance to best point not within threshold)'

如果你想更多地信任更接近的信标，你可能需要计算两个最接近的信标之间的交点，然后使用更远的信标进行抢七。请记住，对于单个测量，几乎所有您对“置信水平”所做的任何事情都是最好的。由于您将始终处理非常糟糕的数据，因此您必须放松power_increases限制和阈值百分比。

你有3个点：A（xA，yA，zA），B（xB，yB，zB）和C（xC，yC，zC），它们分别近似于dA，dB和dC，来自你的目标点G（xG， YG，ZG）。假设cA，cB和cC是每个点的置信度（0 <cX <= 1）。基本上，你可能会接近1，如{0.95,0.97,0.99}。如果您不知道，请根据距离avg尝试不同的系数。如果距离真的很大，你可能对此不太确定。

这是我会这样做的方式：

var sum = (cA*dA) + (cB*dB) + (cC*dC);
dA = cA*dA/sum;
dB = cB*dB/sum;
dC = cC*dC/sum;

xG = (xA*dA) + (xB*dB) + (xC*dC);
yG = (yA*dA) + (yB*dB) + (yC*dC);
xG = (zA*dA) + (zB*dB) + (zC*dC);

基本的，并不是很聪明，但会完成一些简单任务的工作。

编辑

你可以在[0，inf [中使用任意置信系数，但恕我直言，限制在[0,1]是一个好主意，以保持一个现实的结果。

链接地址: http://www.djcxy.com/p/84957.html

上一篇: Multiliteration implementation with inaccurate distance data

下一篇: Trilaterate the two points given with 3 points and 3 distances