Легенда о триангуляциях в сети GSM и ее разоблачение

[dastapov]

Вот типичный комментарий от govorun на один из моих постов: "чисто теоретически, если можно стандартными средствами определить расстояние от БС до телефона, то по расстояниям от трех БС можно получить точные координаты аппарата, а во расстоянию от двух БС - 2 точки, в одной из которых будет находиться телефон".

Комментарий достаточно типичный - подобное мнение широко распространено на просторах интернета. Так как часть этого утверждения - сущая правда (стандартными средствами иногда можно определить расстояние от БС до телефона (тсс! ни слова о точности измерения!)), кажется, что все утверждение целиком - тоже правда. Так ли это? Давайте разберем его на части и исследуем подробнее.

UPDATE: для тех, кто в материале. Я в курсе, что существуют A-GPS, TOA, AOA, и другие страшные слова. Я в курсе, что иногда достаточно знать местоположение телефона с точностью до location area. Я в курсе, что можно послать на телефон SMS или позвонить, и при этом обновится информация о camped cell, что тоже может быть приемлимым способом "засечь" местоположение конкретного телефона для каких-то конкретных применений. Данный пост не ставит своей целью показать, что все эти способы - чушь и не могут существовать. Данный пост посвящен одной вполне конкретной легенде: что, мол, базовые станции GSM триангулируют местоположение телефона (вариант - всех телефонов в зоне покрытия) и эта возможность является стандартной функцией любой BS.

Начнем с аналогии (кто же из нас не любит начать с аналогии?). Рассмотрим такое утверждение: "поскольку при помощи ping-а можно определить расстояние от одного компьютера до другого, то по расстояниям от трех компьютеров (зная их координаты), можно получить точные координаты искомого компьютера". Не торопитесь кричать: "Бред!".

А что если мы возьмем четыре компьютера, соединим их проводами (если надо - с репитерами) по схеме "звезда" (один - в центре, три - соединены с ним), причем провода проложим строго по прямой, и обеспечим такую длину проводов, чтобы ошибка измерения времени пинга не влияла существенно на вычисление расстояния.

Сможем ли мы в таком случае определить координаты центрального компьютера, зная координаты периферийных и пользуясь только ping-ом? Сможем. Означает ли это, что подобный способ можно использовать всегда? Безусловно, нет. Во-первых, провода редко соединяют два компьютера строго по прямой, во-вторых мы как правило не знаем точных координат тех машин, которые мы пингуем, и т.п. Думаю, вы сами сможете продолжить этот список.

Теперь вернемся к исходному утверждению. Можно ли "стандартными средствами определить расстояние от БС до телефона?". Короткий и ничего не объясняющий ответ - "можно". Зададимся дополнительными вопросами:
1)Кто сказал, что это будет кратчайшее расстояние?
2)Кто занимается измерениями - базовая или телефон?
3)С какой точностью будет произведено измерение?

Ответы на эти вопросы будут такими:
Действительно, базовая станция в процессе обслуживания разговора занимается расчетом величин т.н. timing advance и передает их телефону. Телефон использует их, чтобы корректировать ход своего clock timer-а так, чтобы у него и у базовой "часы тикали одинаково". Действительно, базовая "замеряет" время прохождения сигнала от базовой до телефона, но ей абсолютно пофиг, сколько раз по пути следования сигнал отразился от зданий и т.п.

Итак, вот первая ложка дегтя: несмотря на то, что базовая измеряет время прохождения сигнала от себя до телефона, делает она это только в процессе обслуживания звонка и мы не можем рассчитать на основании этого времени расстояние от базовой до телефона по прямой. Плюс ко всему, даже в идеальных условиях TA дает точность измерения до 500 метров [1].

Едем дальше. Знает ли базовая, сколько телефонов находятся в зоне ее покрытия в режиме ожидания и каково время прохождения сигнала до них? Нет и нет.

Знает ли телефон, какие базовые находятся в "зоне слышимости" и каково время прохождения сигнала до них? Да и нет. Телефон может измерить уровень сигнала базовой (и занимается этим все время), но он не знает/не может измерить величину затухания сигнала.

Даже если телефон мог бы измерить уровень затухания и/или время прохождения сигнала до соседних базовых, мог бы он сам вычислить свои координаты? Нет, т.к. он не знает координат базовых.

О! Идея! Раз базовые (или BSC - не суть важно) "знают" свои координаты и "знают", какова мощность их передатчиков, а телефон "знает", насколько хорошо он их "слышит", давайте каким-то образом сведем эти данные в одну точку, и там проведем расчет координат.

Допустим, в SIM-карте телефона будет специальный applet, которых по сигналу извне (или с какой-то периодичностью) будет передавать по RACH пакетик, в котором будут CellID и RxLevel соседних базовых, а BSC будет получать эти пакетики, и на их основании высчитывать координаты телефона и передавать их дальше, какому-то выделенному серверу (для простоты, назовем его LBS), который будет хранить координаты и при нужде отдавать другим системам. А если какой-то телефон надумает позвонить или принять звонок, BSC дополнительно скорректирует уже имеющиеся координаты с учетом TA.

Смотрите, мы построили систему, которая по запросу к LBS-серверу может отдать нам координаты произвольного телефона в этой GSM-сети (при условии наличия в его SIM-карте нужного нам applet-а). Казалось бы, победа?

А теперь давайте посчитаем, что нам пришлось (пусть и умозрительно) модифицировать в обычной GSM Phase 2+ сети, чтобы получить такой результат:
1)Добавить в SIM-карту applet
2)Модифицировать все BSC и/или BS
3)Добавить LBS-сервер и обеспечить его каналами (физическими или логическими) связи с BSC.

Другими словами - мы разработали и "внедрили" на сети GSM-оператора решение для предоставление location-based services.

А теперь вернемся к начальному утверждению. Как видно, понадобилось существенно модифицировать сеть для того, чтобы превратить теоретическую возможность в возможность практическую. Очевидно, что далеко не все GSM-операторы проделали такую работу (или подобную [2]) работу и обладают возможностью определять местоположение вашего телефона.

Соответственно, если не тыкать пальцем в конкретного оператора, а говорить о GSM как о технологии вообще, то лучше ограничится тем, что "стандартные возможности сети GSM допускают построение системы определения местоположения абонента на основании измерения параметров прохождения радиосигнала, но стандарта GSM Phase 2+ на такие системы/технологии - нет". И не более того.

Ну как, теперь-то тема сисек триангуляции раскрыта полностью?

Литература:

1. http://en.wikipedia.org/wiki/Timing_advance
   
2. http://gsm.net.ua/position.html
   
3. http://www.technocom-wireless.com/pdf/COMDEX_Fall2001.pdf (тут - веселые картинки, которые показывают точность работы разных методов определения местоположения)
   

Comments

[dbg.livejournal.com]

Хорошие у тебя рассказы про GSM. Спасибо. Пиши еще.

[kolbusa.livejournal.com]

Большое спасибо за рассказы. Вопрос: как узнать модифицирована ли данная sim-карта и как? (т.е. содержит ли она какие-то дополнительные апплеты, etc).

[http://users.livejournal.com/_adept_/]

Можно притвориться телефоном и попросить карту ответить на запрос "PROFILE DOWNLOAD" (в рамках интерфейса, описаного в GSM 11.14) - по идее карта должна рассказать, какими расшириными возможностями она "оснащена".

Возможно, аплет, который реагирует на входящие сигналы (скорее всего, SMS-ки) регистрирует себя как "incoming event interception" (или как оно там?) в терминах "SIM Toolkit".

Но все это - не более чем мои предположения.

[maycat.livejournal.com]

учитывая, что у КС появился сервис определения местоположения абонента, у них либо есть построенная дополнительная схема, либо они не заморачиваются, и просто определяют на какой соте висит телефон. это на сколько мне известно сделать элементарно.

[http://users.livejournal.com/_adept_/]

А почему "либо"? :)

У них есть дополнительная система, но она простая - они не особо заморачиваются. :)

[http://users.livejournal.com/_navi_/]

ну, раз точность измерения TA ~500м (там вроде какое-то неровное число было типа 518?), то в худшем случае мы всё равно получим зону (пересечение n "цилиндров") диаметром 500 метров, правильно?

[http://users.livejournal.com/_adept_/]

550 м (1100 m round-trip).

У меня есть ряд вопросов:
1)Что будем делать с отражением сигнала и изменением его направления?
2)Откуда возьмутся значения TA от более чем одной базовой?

В лучшем случае мы получим сектор кольца, с радиусом, кратным 550 метрам (см [2])

[akshaal.livejournal.com]

на самом деле это все работает (не у меня, а вообще патчи есть) ))

я не знаю как, но наверное типа:

1-х, по инету гуляют списки с привязками БС к GPS координатам (для Киева в т.ч.).

2-х, у нас вроде как есть rxl ближайших до ближайших 6 БС. Получается имея rxl до одной БС у нас область возможного нахождения телефона, это трехмерное пространство R1 между шаром с радиусом R1min и шаром с радиусом R1max, где R1max-R1min = dR погрешности связанные с отражением сигнала (те самые 500метров). Центр окружности БС, коородинаты которой мы знаем. Берем еще одну БС. У нас еще два радиуса R2max и R2min. Опять трехмерная область R2. И так 6 пространственных областей вокруг каждой БС, которая определяет координаты нахождения телефона. Совмещаем R1 и R2 получаются две области ромбоподобные области (только трехмерные и с непрямыми стенками, рисовать лень). Совмещаем с R3 - это в идеале одна область ромбоподобная. И у нас есть еще 3 совмещения, чтобы уточнить и уменьшить погрешность измерения - каждый раз при наложении оно будет точнее и точнее, область будет сужаться. Если точки пересечения не получится - значит взяли сильно маленькую dR. Увеличиваем и повторяем. Какая в итоге получится погрешность - другой вопрос ).

Но обычно такую фигню используют для автоматической смены профиля телефона - мол на работе один, дома другой у подруги третий...

Вот еще ссылку нашел на эту тему:
http://forum.allsiemens.com/viewtopic.php?t=12774

[http://users.livejournal.com/_adept_/]

Почитал ссылки. Везде пишут о том, как подставлять текстовые строки вместо CellID, делая таким образом свой "cell broadcast для бедных" :)

Касательно твоего пункта 2:
Откуда у тебя берутся радиусы? Если ты их меряешь на основании только timing advance, то точность у тебя будет еще та, если же ты предлагаешь мерять затухание сигнала от базовой, то откуда ты возмешь "tx level" базовой (да, "rx level" у тебя действительно есть)?

[lomeo.livejournal.com]

спасибо

[faceted-jacinth.livejournal.com]

Во-первых конкретно в Латвии услугу отслеживания координат по телефону успешно продают и у меня есть знакомые знакомых, которые ей пользуются - очень удобно для владельца небольшого бизнеса, следить за тем, чтобы шофёр какой-нибудь не останавливался во всяких барах. Ergo, это технически реализуемо, не знаю уж с каким временным/пространственным разрешением, если хотите, могу выяснить.

А по вопросам -
1)Кто сказал, что это будет кратчайшее расстояние? Отражённый сигнал НЕ МОЖЕТ нести информацию, он слишком слабый и слишком хаотично меняется. Его невозможно перепутать с прямым, не говоря уж о том, чтобы использовать вместо него. Он может выступать только в роли помех.
2)Кто занимается измерениями - базовая или телефон? Два варианта:
а) базовая, конечно, причём не одна (чтобы триангуляцию делать). И, конечно, не всё время, а иногда, посылая пинги (от которых на колонки идут наводки, Вы писали про них) чаще чем обычно. Это же платная услуга, почему бы и нет?
б) телефон. В него ставится симка со специальным апплетом и вперёд. Это, повторюсь, платная услуга.

Опять же, если хотите, могу попытаться найти реальную информацию о том, как оно конкретно реализуется. Может быть, конечно, что там разрешающая способность - одна сота, но вряд ли, по рассказам там точность довольно хорошая даже за городом.

[faceted-jacinth.livejournal.com]

Да, апплету вовсе не обязательно знать координаты всех базовых станций, даже наоборот - вредно, из соображений секьюрности. Лучше пусть он производит измерения (только лучше не мощности а задержек всё-таки) и отсылает сырые данные, интерпретировать их будут уже Надёжные Люди у оператора.

[http://users.livejournal.com/_adept_/]

Отражённый сигнал НЕ МОЖЕТ нести информацию, он слишком слабый и слишком хаотично меняется

Чтобы это не было только моими словами, сошлюсь на http://www.gmat.unsw.edu.au/snap/publications/lib_etal2005e.pdf. Цитата: "Mobile phone location methods based on signal time delay and angle of arrival measurements, such as time of arrival (TOA), time difference of arrival (TDOA), or angle of arrival (AOA), suffer from the non-line-of-sight (NLOS) error and multipath, especially in urban and suburban areas."

Разговаривать с использованием отраженного сигнала вполне себе можно. При желании, можно поставить пару опытов с алюминиевой фольгой, чтобы в этом убедиться.

Измерениями занимается базовая, конечно, причём не одна (чтобы триангуляцию делать). И, конечно, не всё время, а иногда, посылая пинги (от которых на колонки идут наводки, Вы писали про них)
На paging телефон всегда отвечает одной базовой. Откуда возьмутся замеры от нескольких?

В него ставится симка со специальным апплетом и вперёд. Это, повторюсь, платная услуга.
Это понятно. Повторюсь еще раз - для этого нужно иметь в сети кучу "апгрейдов" и содействие со стороны аппарата. Соответственно неверно говорить, что в любой GSM сети любой телефон может быть "вычислен". Мой point был именно в этом.

[http://users.livejournal.com/_adept_/]

Опять же, если хотите, могу попытаться найти реальную информацию о том, как оно конкретно реализуется. Может быть, конечно, что там разрешающая способность - одна сота, но вряд ли, по рассказам там точность довольно хорошая даже за городом.

Не стоит трудиться, я занимался внедрением таких систем, и материалы у меня есть :)

[us2yw.livejournal.com]

>Отражённый сигнал НЕ МОЖЕТ нести информацию, он слишком слабый и слишком хаотично меняется. Его невозможно перепутать с прямым, не говоря уж о том, чтобы использовать вместо него. Он может выступать только в роли помех.
С точностью до наоборот. :) См http://users.livejournal.com/_adept_/43668.html?thread=521108#t521108

>Кто занимается измерениями - базовая или телефон?
- телефон. Но номера каналов, которые надо "слушать " и "мерять" сообщает контроллер.

[blackshaman.livejournal.com]

Спасибо. Очень популярно (я правда бауманский закончил :).

[braveua.livejournal.com]

но ведь работает
http://www.kyivstar.net/press_center/news/common/?id=1219
или я что-то неправильно понимаю?

[http://users.livejournal.com/_adept_/]

Да, работает. Но не за счет какой-то мифической "триангуляции с помощью стандартных средств сети GSM", а за счет установки отдельной LBS-платформы.

[http://users.livejournal.com/_login_/]

Насколько мне известно у основных вендоров уже имеется продукты которые реализуют эту фичу(Ericsson LBS к примеру). Как я понял, действует эта штука примерно так: тулза имеет вазу с точными координатами (GPS) азимутами секторов и мощьностями передатчиков. Когда нужно получить расстояние до базовой, посылается спец. смска по пейджингу от которой определяется time advance. Также я так понимаю(не уверен) при пейджинге передается инфа в зоне действия каких целлов находится MS. Из этой информации можно посчитать координаты MS достаточно точно.

PS Как правило операторы не проделывают никакой работы. Они просто покупают готовый солюшен у вендора. Во-первых так быстрее задеплоить услугу. Во-вторых саппорт. Если чтото заглючило, нагибаем вендора:)
--
С уважением,
Андрей Логинов

[http://users.livejournal.com/_adept_/]

Конечно, есть продукты, и их даже покупают. А еще покупают PDA с телефоном и GPS внутри.

Я ж не говорю о том, что вообще-вообще никак такое не сделать. И не говорю о том, что операторы строят такие системы сами. Я говорю о том, что априори утрверждать что определение местоположения - возможно, да еще и ссылатся на "триангуляцию, которую делают базовые" - неверно. Вот и все.

Впрочем, в комментариях я это уже писал. Раз пять :)

[dadaev.livejournal.com]

продавец с нашего магазина купила на радиорынке краденый телефон, через день в магазин пришла милиция, начала требовать телефон (он принадлежал человеку по которому шло следствие как они объяснили), ну и собственно забрали его
...как?

[http://users.livejournal.com/_adept_/]

из прокуратуры пришло заявление на выдачу звонков с этого номера.

Самая вероятная версия того, что было дальше: следователи нашли и опросили тех, _кому_ были звонки, через них вышли на текущего владельца номера, получив его ФИО и адрес от знакомых (которым были звонки). Все.

[http://users.livejournal.com/_adept_/]

Вот тут ее обсуждали:
http://users.livejournal.com/_adept_/41389.html?thread=464557#t464557

Если коротко, то:
1)Я писал про конкретную легенду: "триангуляцию, которую делают базовые". Тут такого нет.
2)Не надо путать "это можно заюзать в конкретной сети" с "это можно заюзать всегда и в любой сети", и с "это можно в принципе реализовать в любой сети". С последним и первым - я согласен. Со вторым - нет.

[(Anonymous)]

Я так понимаю, вы хотите опровергнуть общеизвестное заблуждение о возможности идентификации положения абонента
тем, приводя во внимание, что для определения местоположения обязательно требуются пункты 1 2 и 3 ?

ладно, подскажите может ли оператор в своих целях отказать в доступе конкретному мобильнику на избранные базовые станции? просто не пустить и все, невзирая на качество и силу сигнала.

Если да, то можно заставить телефон делать звонки поочередно через несколько базовых, замерить параметры и таким образом, к досаде мафиози базирующегося в пригородной вилле, за некое приемлимое время(ну сутки) по десятку сделаных звонков и измереных растояний _без_тех_трех_пунктов_ оператор вполне может определить местоположение.

Так ведь? Ну так вот они и корни заблуждения. Cценарий вполне реальный.

[http://users.livejournal.com/_adept_/]

Приведеные мной пункты 1, 2 и 3 - это только один из возможных вариантов реализации, вместо 1 и 2 может быть что-то другое. А (3) - т.е. какой-то application server - нужен всегда.

может ли оператор в своих целях отказать в доступе конкретному мобильнику на избранные базовые станции

Может. Теоретически. Назначить этой мобилке отдельный access class, и заблокировать доступ этому access class-у на все соты в каком-то LA, кроме одной. Но это - нефиговый кусок ручной работы, т.к. в штатоном режиме такое с сетью никто не делает.

С большой вероятностью, попытка такого ограничения обернется тем, что человек будет 50% времени сидеть без связи вообще - т.к. "издалека" непонятно, что у него там ловит мобилка и с каким качеством, за какую соту он "зацепится", а за какую - нет.

Да, потом можно выждать какое-то кол-во звонков и все такое прочее, только вот затраты на весь процесс и его точность будут такие, что лучше и не начинать.

Про реальные сценарии я еще сегодня отдельный пост напишу.

[dfase.livejournal.com]

Насамом деле все ОЧЕНЬ просто: мобилка должна прозвонить всех соседей, и получить от каждого ТА, которое может дать от 500м до 32км.
Используя прицип "охоты на лис" или проще радиопеленгации, можно кругами приблизительно отметить где находиться абонент.
То есть если задействовать офигенное колличество ресурсов то теоритически можно вычислить местоположение абонента.

Другое дело, что в полях, где 1 базуха на 20км мы получим погрешность...20км.

Вообще в сетях получить погрешность ниже 500м сложно, практически невыполнима.

Вообщем все что сейчас крутят по телеку фигня.

[yanek.livejournal.com]

Есть еще страшилка, что местоположение абонента или хотя бі базовую станцию можно определить просто послав ММС. Но при єтом не имея доступа к аппаратуре оператора, те.е теоретически єто доступно простім смертнім.