Optimization of geometry in TDoA method for navigation and detection.pdf Разностно-дальномерный метод, или TDoA (Time Difference of Arrival), порождает две задачи. Разностно-дальномерная задача (РДЗ): по моментам времени приема сигнала, синхронно излучаемого известными источниками (маяками), найти место приемника (потребителя). Эта задача местоопределения приемника сигнала является базовой для многих современных систем навигации, в том числе для спутниковых систем GPS, ГЛОНАСС, Galileo и др. Разностно-дальномерной задаче математически эквивалентна следующая -Обратная разностно-дальномерная задача (ОРДЗ): по моментам времени приема сигнала известными синхронными приемниками найти место источника сигнала. Эта задача местонахождения источника сигнала является базовой для многих систем обнаружения, в том числе для сейсмических систем, систем обнаружения терпящих бедствие, систем координатной идентификации пользователя мобильной сотовой связи, систем слежения за подвижным периодическим источником сигнала и т.п. Из самих формулировок прямой и обратной разностно-дальномерных задач ясно, что центральным аспектом основанных на них технических систем являются измерение и синхронизация времени. В качестве носителя сигнала в зависимости от физических свойств среды и источников, как правило, используется или электромагнитная, или акустическая, или тепловая, или еще какая-нибудь волна, например бактериологическая. Поскольку прямая и обратная разностно-дальномерные задачи математически эквивалентны, далее для краткости речь пойдет только о разностно-дальномерной задаче (РДЗ). Вопрос об оптимизации геометрии разностно-дальномерного метода в навигации впервые был поставлен в работе [1] применительно к GPS. Под оптимизацией в [1] понималась минимизация геометрического фактора PDOP. Там же было доказано, что 3/VN < PDOP(N) и что это неравенство превращается в равенство при N = 4, 6, 8, 12. Затем в работе [2] другим способом была доказана серия аналогичных неравенств. Вопрос о представлении абсолютных минимумов геометрических факторов (PDOP, GDOP) навигационных систем типа GPS в виде простых радикалов был впервые поставлен в работе [3]. Там же было доказано, что при всех N > 4 ,J9N < min PDOP(N), 4 эти неравенства становятся равенствами. Также в [3] было доказано, что при N = 5 л/05 < min PDOP(5), 5 остался неразрешенным. Работа [3] завершалась следующими вопросами: 1. Каково выражение для абсолютного минимума PDOP и GDOP для нечетного числа N маяков? 2. Как выглядят конфигурации маяков, минимизирующие PDOP и GDOP при N = 5, 7, ...? Независимо от [3] вопрос о нижних границах для PDOP и GDOP был позже рассмотрен в [4, 5], где также были доказаны неравенства (1). В работе [4] всем неравенствам в (1) бездоказательно был присвоен знак равенства. В работе [5] было сделано исключение для случая N = 5, остальные равенства, включая случай четных N, не получили доказательств. Дело в том, что для того, чтобы иметь в отдельно взятом неравенстве (1) равенство, необходимо построить соответствующую конфигурацию маяков, а это непросто. Как видим, поставленные выше вопросы взаимосвязаны. В настоящей статье проблема решена полностью, т.е. и для всех нечетных N > 5 построены примеры конфигураций маяков, обеспечивающие равенства в (1). Ничего подобного нет в [4, 5]. Между тем в работе [6] есть ссылки на [4, 5] как на уже доказанный результат. Отметим, что область применения полученных результатов не ограничивается GPS, где, конечно, препятствие тела Земли делает их абстрактными. Однако существует множество применений раз-ностно-дальномерного метода, которому посвящена данная статья, когда найденные оценки PDOP и GDOP приобретают безусловный смысл при отсутствии ограничения в распространении сигнала. Приведем только некоторые примеры. Пример 1. В рое беспилотных летательных аппаратов есть несколько командных, другие определяют свои координаты с помощью разностно-дальномерного метода по синхронным сигналам от командных аппаратов, располагающих абсолютными координатами. Пример 2. То же самое в Космосе, см. по этому поводу [7]. Пример 3. То же самое под водой на основе акустического сигнала. Пример 4. Микро-робот, погруженный в тело живого существа, определяет свои координаты по синхронным сигналам маяков, размещенных на поверхности тела (РДЗ). Или, напротив, по сигналу, поступающему от микро-робота, находится его местоположение наблюдателем (ОРДЗ). Коэффициенты PDOP и GDOP в настоящее время являются официальными стандартами (NMEA 0183, ГОСТ Р 52928-2010 и др.). Других стандартов относительно геометрических факторов в разностно-дальномерных системах навигации нами не обнаружено. Вопросам вычисления и минимизации PDOP и GDOP в различных разностно-дальномерных системах навигации посвящены десятки работ, ссылки на которые можно найти в упоминаемых здесь статьях. Одно из направлений - это мультисистемность (см., напр.: [6]). Другое - учет ограничений, что характерно для стандартной глобальной спутниковой навигационной системы типа GPS или ГЛОНАСС. Третье - композиция первого и второго (см., напр.: [8]). Очевидно, что, переходя к этим более сложным случаям, нужно досконально и окончательно разобраться с одной системой без ограничений. Таким образом, абсолютные нижние оценки PDOP и GDOP имеют фундаментальный характер и поэтому заслуживают строгого теоретического обоснования. 1. Постановка задачи Разностно-дальномерная навигационная задача в трехмерном пространстве состоит в решении системы N > 4 уравнений относительно столбца X = (т, x, x2, х3 )т: (2) т+ x - a. = tj, j = 1,..., N, где a =(ад, a 2, aj3) - известные столбцы декартовых координат маяков, Р - измеренные псевдодальности, т - неизвестная псевдодальность, x = (x, x2, x3 )т - неизвестный столбец декартовых ко-44 Оптимизация геометрии разностно-дальномерного метода в навигации и обнаружении ординат потребителя. При этом x - Oj ■\\j(. Х1 Ojl ) + (X2 Oj 2) + (X3 Oj 3) - расстояние между по требителем и маяком с номером j и Х0 = х, Xj = x, X2 = x2, X3 = x . Более обще, система (2) является одним функциональным уравнением F(X) = t, где X - неизвестная точка в «-мерном пространстве, t - известная точка в N-мерном пространстве, N > n . Фиксировать п = 3 нежелательно, так как в рассуждениях используются размерности п = 2 и п = 1. Объектом математического исследования ниже становится матрица Якоби J = 8F/дХ для F: (\\ ер J = (3) где е. = (x - о) x - о - «-мерный орт (столбец с единичным модулем), противоположный направлению от потребителя на маяк с номером j. Для краткости будем употреблять операции присоединения матриц: augment - справа, stack - снизу. Например, в (3) J = augment(1, A), где 1 = (1,..., 1)т , A = stack(e1T,..., eNт) . Отображение F является непрерывно дифференцируемым всюду, кроме точек, соответствующих aj. Поэтому в точке X, найденной из (2) методом наименьших квадратов, имеем J ■ dX = dt, где дифференциалы dt = (dtj,..., dtN )т, dX = (dх, dx,..., dxn )т в классической теории измерений, восходящей к Гауссу, принято трактовать как ошибки измеряемых и искомых величин соответственно. При стандартном предположении о несмещенности, равноточности и попарной некоррелированности измерений dtj метод наименьших квадратов [1-8; 9. С. 241] приводит к системе п зависимостей с = K ■ at где ct - среднеквадратическая ошибка (СКО) каждого отдельного измерения tj, j = 1,...,N, с. - СКО для искомой величины с номером i = 0,..., п , Ki - безразмерный коэффициент чувствительности измерительной системы (2) для искомой величины с номером і. Квадраты коэффициентов с = K С размещаются на главной диагонали матрицы f (J Т J)-1 = V С акцентом на GNSS (Global Navigation Satellite System) Kz=K0, Kx=jK?+- + K;, К = 4К;+К; . В стандартной терминологии для коэффициентов чувствительности измерительной системы GNSS [2-9], которые называются здесь геометрическими факторами, используются аббревиатуры K = TDOP (Time Dilution of Precision), Kx = n будем для простоты называть вертикальными. В работе [10] А.Н. Колмогоров поставил вопрос о существовании вертикальных матриц, которые в каноническом евклидовом смысле удовлетворяют трем требованиям: 45 Л.П. Барабанова 1. Квадраты строк равны единице. 2. Квадраты столбцов равны. 3. Столбцы попарно ортогональны. Положительный ответ на вопрос Колмогорова для всех натуральных пар N > n дал А.И. Мальцев [11]. Более простое разрешение вопроса Колмогорова было затем получено в [9. С. 237-238]. Идея [9] позволила доказать теоремы 3, 4 в [3], которые можно свести в одну следующую формулировку. Теорема 1 [3]. Коэффициенты PDOP, GDOP достигают своих наименьших значений min PDOP(N) = =N, min GDOP(N) =10/ N одновременно и тогда и только тогда, когда матрица A = stack^т,eNт) удовлетворяет трем приведенным требованиям и дополнительно требованию уравновешенности: 4. Сумма компонент каждого столбца матрицы равна нулю. Как видим, в РДЗ первое требование выполняется автоматически. Совмещение всех четырех требований нетривиально. Определение 1. Вертикальную матрицу, удовлетворяющую требованиям 1-4, назовем согласно [12] строящей матрицей, или building matrix (5-матрицей). Теоремой 1 устанавливается взаимно-однозначное соответствие между 5-матрицами и оптимальными (по критерию конъюнкции PDOP и GDOP) конфигурациями на единичной сфере потреби-теля-наблюдателя TDoA. В работе [3] было введено понятие дуальных 5-матриц. Определение 2. 5-матрицы P(N х m), Q(N х к) дуальны, если m + к = N -1 и столбцы матрицы P ортогональны всем столбцам матрицы Q. Очевидно, что отношение дуальности в классе 5-матриц симметрично. Построение новых 5-матриц опирается на две следующие леммы. Лемма 1 [3]. Если P(N х n) , R(M х п) - 5-матрицы, то матрица S ((N+M )х П = stack (P, R) также является 5-матрицей. Лемма 2 [3]. Для всякой 5-матрицы размера N х m, m < N -1 может быть построена дуальная 5-матрица. 3. Построение нетривиальных 5-матриц A(N х 3) при N > 5 Пусть натуральные числа n, m, к подчиняются неравенству П + п - mk > 0 . (4) Для таких натуральных троек предлагается следующий алгоритм. Вход: Пара дуальных 5-матриц P((n + m +1) х n), Q ((п + m +1) х m) и 5-матрица С((п + k) х n) . Выход: 5-матрица D(2n + m +1 + к)х(n + m) . Собираем искомую 5-матрицу D согласно следующей блочной схеме: D = raP PQ Л (5) C 0 х где а и Р - неопределенные коэффициенты, а матрица 0 размерности (n + к) х m состоит из одних нулей. При любых а и Р требования 3, 4 для D очевидно выполняются. Требование 1 означает V а2 +Р2 = 1. Для обеспечения требования 2 для 5-матриц должно быть 9 n + m +1 n + к „9 n + m +1 а -+-= Р n n m 46 Оптимизация геометрии разностно-дальномерного метода в навигации и обнаружении Система двух последних линейных алгебраических уравнений относительно а2 и р2 даст а2 = ■ n + n - mk 2 m(m + 2n + к +1) р2 = > 0 . (6) (n + m + 1)(n + m) (n + m + 1)(n + m) Таким образом, если (4) выполнено, то искомые а и р существуют, и матрица D - 5-матрица. Построение 5-матрицы 7 х 3. Положим на входе вышеприведенного алгоритма n = 2, m = 1, к = 1. Условие (4) выполняется. По размеру возьмем дуальные 5-матрицы Р(4 х 2), Q(4 х 1) : P = (1 0 > (1 1 0 1 , Q= -1 -1 0 1 V 0 -ъ V-1 , Возьмем также 5-матрицу C (3 х 2) в виде правильного треугольника ортов (по строкам), 0 1 2 1 2 C = Ѵз 2 Ѵэ 2 , и предписанные вышеприведенным алгоритмом коэффициенты согласно (6): 15 21 а =-, р =-. 6 6 Тогда соответствующая согласно (5) матрица D размера (7 х 3) примет вид: D = ( аР C PQ^ 0 /21/6 -ѴІ5/6 0 •721/6 0 -ѴІ5/6 -721/6 1 0 0 -1/2 Ѵз/2 0 -1/2 -Ѵз/2 0 Эта матрица D, изображенная в строках на рис. 1, а, даст образ оптимальной конфигурации 7 маяков (точки излома на рис. 1) на единичной сфере потребителя-наблюдателя. Рис. 1. Образцы оптимальных конфигураций N = 7 маяков (а), N = 9 маяков (b) Fig. 1. Samples of optimal configurations for N = 7 beacons (a), N = 9 beacons (b) Построение 5-матрицы 9 х 3. Положим на входе вышеприведенного алгоритма n = 2, m = 1, к = 3. Легко видеть, что условие (4) выполняется. Возьмем те же самые, что и при построении 47 Л.П. Барабанова 5-матрицы 7 х 3, дуальные 5-матрицы Р(4 х 2), Q (4 х 1) , а в качестве матрицы C возьмем 5-матрицу C (5 х 2) в виде правильного пятиугольника. Кроме того, возьмем согласно (6) а=2,р= Тогда построенная согласно (5) матрица D размера (9 _Ѵ3 2 х 3) будет искомой (рис. 1, Ъ). 1/2 0 V3/2 0 1/2 -V3/2 -1/2 0 V3/2 0 -1/2 -s/3 / 2 1 0 0 cos(2rc /5) sin(2rc /5) 0 cos(4rc /5) sin(4rc /5) 0 cos(6rc /5) sin(6rc /5) 0 cos(8rc/5) sin(8rc /5) 0 ( аР C V 4. Основной результат В дополнение к [3] получаем рис. 2, на котором по оси ординат откладывается размерность пространства. На этом рисунке темные клетки обозначают наличие 5-матриц, т.е. достижение нижних границ (1) в радикалах. Левая граница - это правильные симплексы (в трехмерном случае правильный тетраэдр маяков). Кресты обозначают отсутствие соответствующих 5-матриц [3], кружки -достижимость нижних границ (1) в плоском случае [1, 6] (это, например, 5-матрицы в виде правильных многоугольников). Значок «D» обозначает дуальность к 5-матрице (6 х2), что геометрически может быть представлено октаэдром [1, 3]. Квадратик - куб [1, 3]. Звездочки - последний результат, полученный в настоящей статье. Значки «S» - стеки уже обеспеченных 5-матриц слева направо согласно лемме 1, ибо 10 = 4 + 6, 11 = 4 + 7, 12 = 4 + 8 и т.д. Рис. 2. Схема заполнения списка оптимальных конфигураций Fig. 2. Scheme of filling out the list of optimal configurations В итоге мы получаем искомое усиление теоремы 1 (см. верхний уровень при n = 3 на рис. 2): Теорема 2. Коэффициенты PDOP, GDOP достигают своих наименьших значений min PDOP(N) = =N, min GDOP(N) = = при всех N Ф 5, N > 4 на общих для них конфигурациях, которые в строках являются 5-матрицами. При N = 5 будет min PDOP(N) > >N, min GDOP(N) >>0/N . Осталось рассмотреть случай N = 5. В работе [5. Appendix C] весьма сложным путем доказывается, что фф < minGDOP(5) . (7) 48 Оптимизация геометрии разностно-дальномерного метода в навигации и обнаружении В связи с этим уместно напомнить, что это неравенство было ранее доказано в работе [3] на основании дуальной леммы [3] методом от противного: если 5-матрица (5 х 3) существует, то по дуальной лемме существует и 5-матрица (5 х1), но последняя матрица не существует, так как сложением и вычитанием нечетного числа единиц нельзя получить ноль. Но раз не существует 5-матрицы (5 х 3), то согласно [3], т.е. на основании теоремы 1, имеет место строгое неравенство (7). Итак, как показано в [3], sl95 < min PDOP(5),

Скачать электронную версию публикации