基于不准确距离数据的多重识字实现

Question

我正在尝试创建一个安卓智能手机应用程序，它使用苹果iBeacon技术来确定自己目前的室内位置。我已经设法得到所有可用的信标，并通过rssi信号计算到它们的距离。

目前我面临的问题是，我无法找到一个算法的任何库或实现，该算法使用3(或更多)不动点的距离来计算2D中的估计位置，这些距离不精确(这意味着三个“三边圆”在一个点上不相交)。

如果有人能以任何通用编程语言(Java、C++、Python、Javascript或其他任何语言)向我发送链接或实现，我将非常感激。关于这个话题，我已经读了很多关于堆栈溢出的文章，但是找不到任何我能用代码来转换的答案(只有一些用矩阵的数学方法，用向量或类似的东西进行计算)。

编辑

我想了一种自己的方法，这对我来说很好，但没有那么有效和科学。我遍历位置网格的每一米(或类似于我的示例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的计算，只有确定一个位置)。这是很多-所以我会让这个问题打开，并希望有一些进一步的解决方案或良好的改进现有的解决方案，以使它更有效率。

当然，这不一定是一种三元制办法，就像这个问题最初的标题一样，有一种包括三个以上的定位(多边)信标的算法也是很好的。

Answer 1

我不考虑单个信标的置信度，而是在对可用数据进行最佳猜测之后，尝试为您的结果分配一个总体信任级别。我不认为唯一可用的度量(感知的力量)是一个准确的指示。有了糟糕的几何学或错误的信标，你可能会高度信任糟糕的数据。如果你对所有信标的信任是相等的话，根据你对信标的感知距离与计算点的吻合程度，得出一个总体的自信水平可能会更有意义。

我在下面写了一些Python，通过计算前两个信标的两个圆点相交点，然后选择与第三个点最匹配的点，根据3信标中提供的数据进行最佳猜测。这是为了开始这个问题，而不是一个最终的解决方案。如果信标不相交，它会稍微增加每个信标的半径，直到它们满足或达到一个阈值为止。同样，它确保第三个信标在可设定的阈值内达成一致。对于n-信标，我会选择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限制和阈值百分比。

Answer 2

你有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}。如果你不知道，试试不同的系数，取决于距离的平均值。如果距离真的很大，你可能对此不太自信。

以下是我要做的方法：

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[，但IMHO，限制在0,1是一个好主意，以保持一个现实的结果。