Я изучаю возможность использования нескольких iBeacons для выполнения "грубой" внутренней позиции местоположения. Приложение представляет собой своего рода "музейную" настройку, и было бы легче иметь возможность создавать сетку с местоположениями для разных объектов, а затем отдельные маяки (хотя это тоже может быть невозможно).
Есть ли примеры, опыты, с использованием нескольких маяков для триангуляции в какое-то место или какую-то логику, чтобы помочь мне на пути к ее написанию?
Я делал некоторые эксперименты, чтобы получить точную позицию, используя три маяка.
Результаты трилатерации
К несчастью, результаты были очень разочаровывающими с точки зрения качества. В основном было два вопроса:
Возможные решения
После разговора с инженером Apple, который активно отговаривал меня идти по этому пути, вариант, который я считаю более склонным использовать прямо сейчас, - это грубая сила. Попытайтесь настроить маяк каждые X метров (X является максимальной ошибкой, допущенной в системе), поэтому мы можем отслеживать на этой сетке маяков позицию данного устройства, вычисляя, какой маяк на сетке является ближайшим к устройству, и предполагая, что устройство находится в одном положении.
алгоритм Trilateration
Однако, для полноты, я разделяю основную функцию алгоритма трилатерации. Он основан на пункте 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);
}
Я изучил это. Термин, который вы хотите, это трилатерация. (В триангуляции у вас есть углы из 3 известных точек. В трилатерации у вас есть расстояние от 3 известных точек). Если вы Google, вы должны найти несколько статей, в том числе один на Wiki. Он включает в себя решение набора из трех одновременных уравнений. Документы, которые я видел, были для трехмерной трилатерации - 2D проще, потому что вы можете просто отказаться от Z-термина.
Я нашел абстрактную математику. Я еще не нашел времени, чтобы нарисовать общий алгоритм в конкретном коде, но я планирую его решить в какой-то момент.
Обратите внимание, что полученные вами результаты будут ОЧЕНЬ грубыми, особенно во всех, кроме пустой комнаты. Сигналы достаточно слабы, что человек, статуя или что-то, что блокирует видимость, значительно увеличит ваши показания расстояния. Возможно, у вас могут быть места в здании, где конструктивное вмешательство (в основном из стен) делает некоторые места более точными, чем они есть на самом деле.
Вот библиотека Java с открытым исходным кодом, которая будет выполнять трилатерацию/мультилатерацию: https://github.com/lemmingapex/Trilateration
В нем используется популярный нелинейный оптимизатор наименьших квадратов, алгоритм Левенберга-Марквардта, из 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);
Большинство научных примеров, таких как wikipedia, занимаются ровно тремя кругами и предполагают точную информацию. Эти обстоятельства позволяют получить более простые формулировки проблем с точными ответами и обычно не подходят для практических ситуаций.
Задача в R 2 или R 3 евклидовом пространстве с расстояниями, которые содержат ошибку измерения, интересующую область (эллипс) или объем (эллипсоид) точки. Если необходима точечная оценка вместо области, необходимо использовать центроид площади или объемный центроид. R 2 требуется не менее 3 невырожденных точек и расстояний для получения единственной области; и, таким образом, пространство R 3 требует не менее 4 невырожденных точек и расстояний для получения единственной области.
Точное внутреннее позиционирование с iBeacon будет сложным по следующим причинам:
С другой стороны, если вы можете увеличить частоту iBeacon до более 10 Гц (что, я сомневаюсь, это возможно), тогда можно получить точность 5 м или более, используя подходящий метод обработки. Во-первых, тривиальные решения, основанные на обратном квадрате закона, как и trilateration, часто не работают хорошо, потому что на практике отношение расстояние /RSSI для разных маяков часто выходит из Закон об обратном Sqare по причине 1 выше. Но пока RSSI относительно стабилен для определенного маяка в любом определенном месте (что обычно имеет место), вы можете использовать подход, называемый fingerprinting, для достижения более высокой точности. Общим методом, используемым для снятия отпечатков пальцев, является kNN (k-Nearest Neighbor).
Некоторые iBeacons могут транслировать более 1 Гц, например Estimote используют по умолчанию 5 Гц. Однако в соответствии с этой ссылкой : "Это ограничение Apple. IOS возвращает обновление маяков каждую секунду, независимо от того, как часто реклама устройства" . Там есть еще один комментарий (вероятно, от поставщика Estimote): "Наши маяки могут транслироваться гораздо быстрее, а может улучшать результаты и измерения" . Поэтому неясно, является ли более высокая частота iBeacon полезной.
Если вы что-то вроде меня и не любите математику, вам может понадобиться быстрый поиск "внутреннего позиционирования sdk". Там много компаний, предлагающих внутреннее позиционирование в качестве услуги.
Бесстыдный плагин: я работаю для indoo.rs и могу рекомендовать эту услугу. Он также включает в себя маршрутизацию и таковую поверх "только" внутреннего позиционирования.
Для тех, кому нужна @Javier Chávarri функция trilateration для устройств 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;
}
Мой архитектор/менеджер, который написал следующий алгоритм,
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;
}
После тестирования я нашел его точным до 5 метров.
Прокомментируйте мое тестирование, если мы его уточним.
Я реализовал очень простой алгоритм Fingerprint для android 4.4, протестированный в относительной "плохой" среде:
точность кажется в 5-8 метрах и зависит от того, как я разместил эту 3-я телекомпания Ibeacon. Алгоритм довольно прост, и я думаю, что вы можете реализовать его самостоятельно, шаги:
поэтому, когда вы начинаете позиционирование, это просто обратная сторона шагов.
Мы также пытаемся найти лучший способ точно найти кого-то в комнате с помощью iBeacons. Дело в том, что мощность маякового радиосигнала не является постоянной, и на нее влияют другие сигналы 2,4 ГГц, металлические объекты и т.д., Поэтому для достижения максимальной точности необходимо выполнить калибровку каждого маяка в отдельности и как только он будет установлен в желаемом положении, (и провести полевые испытания, чтобы увидеть колебания сигнала, когда присутствуют другие устройства Bluetooth). У нас также есть некоторые iBeacons из Estimote (то же самое из видео Konrad Dzwinel), и они уже разработали техническую демонстрацию того, что можно сделать с iBeacons. В их приложении можно увидеть радар, в котором отображаются iBeacons. Иногда это довольно точно, но иногда это не так (и, кажется, движение телефона не считается для вычисления позиций). Проверьте Демо в видео, которое мы сделали здесь: http://goo.gl/98hiza
Хотя теоретически 3 iBeacons должны быть достаточными для достижения хорошей точности, возможно, в реальных ситуациях больше маяков необходимы для обеспечения точности, которую вы ищете.
То, что действительно помогло мне, это проект на Code.Google.com: https://code.google.com/p/wsnlocalizationscala/ содержит много кода, несколько алгоритмов трилатерации, все написано на С#. Это большая библиотека, но на самом деле не предназначалась для использования "из коробки".
Я нашел решение Vishnu Prahbu очень полезным. Я портировал его на С#, если кому-то это нужно.
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;
}
Альтернативное уравнение
- (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);
}