Дипломной практике тема диплома: Разработка системы позиционирования транспорта по сигналам сотовых сетей




Скачать 113.42 Kb.
НазваниеДипломной практике тема диплома: Разработка системы позиционирования транспорта по сигналам сотовых сетей
Дата публикации18.03.2013
Размер113.42 Kb.
ТипДиплом
odtdocs.ru > Спорт > Диплом
МОСКОВСКИЙ ИНСТИТУТ ЭЛЕКТРОНИКИ И МАТЕМАТИКИ

(Технический Университет)

Кафедра Информационно-коммуникационные технологии

ОТЧЕТ
ПО ПРЕДДИПЛОМНОЙ ПРАКТИКЕ


Тема диплома: Разработка системы позиционирования транспорта по сигналам сотовых сетей

Выполнил:




М.М. Ковалев




(подпись)




Принял:




^ Д.О. Столяров




(подпись)





Москва 2012

Оглавление

Введение 3

Сценарий использования 3

Существующие решения 3

Пути улучшения решений 4

Априорные данные 4

Статистические данные 5

Пример собранных данных 5

Существующие математические методы 5

Использование Байесовского классификатора для поиска 5

Использование нейросетей 6

Предлагаемый алгоритм 7

Исходные данные 7

Интерполяция 7

Применение обратной метрики 10

Нахождение результирующей метрики 11

Нахождение результата 12

Пути использования статистических данных 13

Архитектура системы 14

Общая архитектура 14

Архитектура серверной части 15

Вывод 16


Введение


Задача мониторинга положения и скорости наземного общественного транспорта зачастую встаёт перед городскими властями; её решение также может быть интересно для создания мобильного сервиса, помогающего пассажирам выбирать маршрут с учётом реального движения транспорта.
^

Сценарий использования


  • До: Вася Пупкин вышел из дома не в час пик, но и не при свободных улицах, подождал своего любимого транспорта десять минут, потом плюнул и ещё за десять дошёл до метро, причём на пятой минуте транспорт его обогнал, но до остановки было далеко.

  • После: Вася Пупкин вышел из дома, дошёл до остановки, открыл на телефоне карту, и увидел, что транспорт ещё далеко, быстрее пешком дойти. И дошёл. Либо понял, что можно и подождать. И подождал.

  • До: Вася Пупкин вышел из метро, пошёл на остановку. Через некоторое время подошла маршрутка. Довольно долго ждала. Он решил плюнуть и сесть в неё. Ещё через пять минут, она тронулась, потому что её сзади догнал муниципальный транспорт.

  • После: вышел, посмотрел на карту и всё понял.
^

Существующие решения


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

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

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

Решение

Описание

Его преимущества

Преимущества разрабатываемой системы

Триангуляция GSM

  • Устройство передаёт данные об уровнях сигналов БС GSM по GPRS.

  • С помощью устройств GSM+GPS собираются данные об уровнях сигнала в разных местах.

  • На сервере собираются данные, строится примерная карта БС.

  • Устройство передаёт данные об уровнях сигналов.

  • Сервер осуществляет триангуляцию.

  • Данные передаются обратно на устройство (опционально).

  • Дёшево

  • Работает много где

  • Намного точнее

  • Схема впервые применяется на транспорте




^ GPS/ГЛОНАСС + GPRS

Устройство позиционирует себя по спутникам, отдаёт данные о координатах по GRPS.

Возможно применять в любой точке планеты без предварительной подготовки.

Устройства без спутникового модуля существенно дешевле.
^

Пути улучшения решений

Априорные данные


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

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

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

При наборе данных об уровнях сигнала с помощью спутниковой навигации, требуется отыскать ближайшую к определённой точку на маршруте, и считать, что она является подлинным расположением.
^

Статистические данные


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

Вместо одного раза, маяк будет 25-50 раз измерять сигнал, считать математическое ожидание его уровня, а также дисперсию, минимум и максимум, и уже эти данные посылать серверу.

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

Также необходимо понять, следует ли при обновлении данных об уровне сигнала их просто перезаписывать, или же каким-то образом хранить последний результат и данные о предыдущих.
^

Пример собранных данных


AT+CENG=2,1     OK     +CENG: 0,"0089,49,0,250,01,12,ca5a,05,05"   +CENG: 1,"0083,35,55,ca59"   +CENG: 2,"0007,34,18,0123"   +CENG: 3,"0121,31,40,ca5b"   +CENG: 4,"0785,30,48,ca5d"   +CENG: 5,"0773,30,45,ca5c"   +CENG: 6,"0006,26,??,????"
^

Существующие математические методы

Использование Байесовского классификатора для поиска


Случай выглядит очень подходящим для применения Байеса: у нас есть много данных, для них известна достоверность (величина, обратная дисперсии), надо выбрать наиболее правдоподобный ответ.

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

Этот недостаток можно устранить, считая вероятности для всех точек, и а потом посчитать математическое ожидание положения трамвая.

Однако, остаётся ещё один недостаток. Байесовский классификатор предполагает использования конченого множества вариантов ответов, тогда как в данном случае оно континуальное. Общепринятых обобщений метода на такой случай авторам найти не удалось.
^

Использование нейросетей


Другим способом обработки недостоверных данных являются нейросети. В отличие от Байесовского классификатора, они идеально подходят к рассматриваемому случаю.

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

Недостатком является большая вычислительная сложность. Очевидно, что создать сеть, которая бы принимала сразу все тысячи вышек, и давала ответ о точке на маршруте, на реальном оборудовании невозможно вообще.

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

Ещё одним потенциальным недостатком является сложность учёта дисперсии измеренных значений для отбрасывания данных с низкой достоверностью.
^

Предлагаемый алгоритм

Исходные данные


Исходными данными для алгоритма являются таблицы соответствия точки на маршруте и уровня сигнала для каждой вышки, а также измененные реальные уровни сигналов от них. Требуется по этим данным определить, в какой точке маршрута было проведено измерение.

Голубой штрих-пунктир -- уровень сигнала от станции 1; красный -- от станции 2; синие точки -- известные значения уровня сигнала от станции 1; чёрные точки -- от станции 2; точки соединены отрезками только для наглядности, в реальности эти данные не используются.

Интерполяция


Для работы с непрерывными данными требуется от табличного вида перейти к аналитическому. Для этого нужно воспользоваться каким-либо алгоритмом интерполяции. В результате должен получиться многочлен известной степени, поскольку только для него мы можем гарантировать, что максимумов у него имеется не более определённого числа. Алгоритм интерполяции и определения степени многочлена следует выбрать.

На этом этапе, для каждой станции n мы имеем функцию уровня её сигнала от положения на маршруте: SigLev_n(x) = P(x), где P(x) -- многочлен. Стоит отметить, что считать эти многочлены можно заранее, в момент сбора данных об уровне сигнала. Но для этого потребуется применение разбиения на кластеры.





Пунктиром показана интерполяция известных уровней сигнала от первой и второй вышки многочленами степени 6.

Чтобы это можно было осуществить, маршрут должен быть задан аналитически. Было решено использовать сплайн на основе кубических кривых Безье.

Требования к алгоритму построение сплайна предъявляются следующие:

  1. Сплайн должен проходить через ряд поставленных точек в количестве больше или равном трём.

  2. Сплайн должен быть всюду гладким.

  3. Должна быть возможность сделать сплайн вогнутым.

  4. Должна быть возможность, указав точку на сплайне, узнать длину кривой от неё до назначанной началом сплайна точки.

  5. Должна быть возможность добавлять точки в сплайн.

Ни одной готовой реализации, удовлетворяющей требованиям, не было найдено, поэтому было решено делать свою.

Тестовый прототип реализован с помощью библиотек PyGame и NumPy.





Интерфейс написанной тестовой программы

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

Чтобы оптимально выбрать промежуточные точки между точками start и end, требуется также знать две соседние с ними опорные точки: prestart и postend. Отметим, что они могут совпадать, поэтому для построения достаточно всего трёх точек.

Поскольку промежуточные точки должны лежать на касательных к точкам start и end, алгоритм начинается с нахождения этих касательных.

Рассмотрим нахождение касательной к точке start. Из точек prestart и end к ней строятся векторы, которые затем нормируются на длину 1. Сумма этих векторов будет рассматриваться как нормаль к касательной.

Опорный вектор полученной касательной направляется в сторону от start к end. Для этого рассматривается, какой угол больше: при повороте нормали на 90 градусов по часовой стрелке или против. Результат поворота на меньший из углов и будет результатом.

Аналогичные расчёты осуществляются для тройки start, end, postend.

После того, как касательные найдены, промежуточные точки на них выбираются как некий процент от расстояния между точками start и end, отложенный на этих касательных, который является "магическим числом", параметризующим алгоритм. Оптимальное значение получается равным примерно 0,25.

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

Сплайн задаётся последовательностью точек в списке (причём считается, что за последней точкой следует первая), поэтому для добавления точки в сплайн, нужно понять, между какими из них нужно добавить новую. Для этого выбирается такая пара точек, для которой сумма расстояний от точек до новой, разделённая на расстояние между ними, минимальна. Именно такая метрика соответствует интуитивному понятию о том, куда новую точку нужно добавлять.

Также, если точек в сплайне больше трёх, их можно удалять.

Написанный скрипт на языке Python можно запустить, имея интерпретатор версии 2.xx с установленными библиотеками PyGame и NumPy.

Точки сплайна можно перетаскивать, удерживая их левой кнопкой мыши. Добавлять точки можно левым кликом на свободном месте, а удалять -- правым на удаляемой точке. Магическое число, названное "надутость", управляется клавишами "вверх" и "вниз". Параметр "уровень бесконечности" является устаревшим, оставшимся от старых версий, в которых использовался для обхода ошибки деления на ноль, возникавшей при ином алгоритме выбора точек на касательных, и сейчас не используется. Он меняется клавишами "w" и "s", но его изменение ни на что не влияет.

Что касается определения расстояния, это сейчас в стадии разработки. Кривая Безье, за исключением тривиальных случаев, не является интегрируемой, поэтому аналитически выразить параметр t в зависимости от требуемого расстояния, невозможно. Для этого будут использованы численные методы интегрирования, работа которых будет оптимизироваться с помощью предвычисления расстояний в опорных точках.
^

Применение обратной метрики


На этом этапе нужно понять, насколько в каждой точке на маршруте реальный уровень сигнала похож на значение, которое там должно быть, в соответствии с интерполяцией. Для этого для каждой вышки n нужно посчитать функцию Sim_n(x, l_n) = Ro(SigLev_n(x), l_n), где x -- точка на маршруте; l_n -- реальный уровень сигнала для вышки n; SigLev_n(x) -- предполагаемый уровень сигнала для точки x; Ro -- обратная метрика.

Функция Ro(a, b) -- обратная метрика -- это функция, которая равна 1, если a и b совпадают, и асимптотически стремится к нулю по мере увеличения расстояния от a до b. Конкретный её вид следует определить. Самый простой -- это 1/(1+abs(a-b)). Однако, следует отметить, что уровень сигнала падает пропорционально квадрату расстояния, а не самому расстоянию, поэтому, возможно, точнее эту зависимость будет выражать обратная метрика Ro(a, b) = 1/(1+(a-b)^2).

Если опуститься на уровень мощности сигнала, то можно увидеть, что GSM-модули отдают уровень сигнала в условных единицах asu, таких что dBm = -113 + 2*asu[19]. Сами же децибелы и милливатты связаны как mW = 10^(dBm/10)[20]. В связи с этим, может потребоваться применение обратной метрики в логарифмическом масштабе (например Ro(a, b) = e^(-(a-b)^2) ), либо перевод децибел в милливатты, но для большей точности можно учитывать не только разность точек, но и их отношение.

Значения обратной метрики 1/(1+(a-b)^2)


Первая станция


Вторая станция


^

Нахождение результирующей метрики


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





Результирующая вероятность для рассмотренного случая.
^

Нахождение результата


Точка, которая будет ответом -- это точка, в которой результирующая вероятность достигает максимума.

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





Точка на маршруте найдена.
^

Пути использования статистических данных


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

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

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

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

Архитектура системы

Общая архитектура






  1. Маяки GSM

    • Устанавливаются на большинство ТС.

    • Передают на сервер по GPRS данные об уровнях сигнала от БС.

  2. Маяки GPS/ГЛОНАСС

    • Устанавливаются на 10% ТС.

    • Передают на сервер по GPRS данные об уровнях сигнала БС и своём положении.

  3. БД

    • Хранит данные о реально принятых уровнях сигнала в известных точках.

    • Хранит данные о маршрутах.

  4. Сервер

    • Заполняет БД.

    • По данным об уровнях сигнала, маршруту и БД, с помощью изобретённого алгоритма позиционирует маяк.

    • Может взаимодействовать с провайдером геолокации (Яндекс) для позиционирования вне маршрутов.

    • Отдаёт данные клиентам.


Архитектура серверной части


Вывод


В ходе данной работы показана возможность создания принципиально нового алгоритма позиционирования транспорта, который покажет своё превосходство над существующими, и его реализации в ходе создания серверной стороны разрабатываемой системы.

Добавить документ в свой блог или на сайт

Похожие:

Дипломной практике тема диплома: Разработка распределенной системы управления хостингом
То есть, фактически описываемые модели маршрутизаторов являются небольшими компьютерами. Далее везде под понятиями «маршрутизатор»...

Дипломной практике тема диплома: Разработка библиотеки для просмотра...
Тема диплома: Разработка библиотеки для просмотра сферических панорам средствами html5

Дипломной практике тема диплома: Разработка сетевой инфраструктуры...
Тема диплома: Разработка сетевой инфраструктуры единой информационной среды кафедры икт

План диплома «Разработка методов балансировки нагрузки для платформы...
План диплома «Разработка методов балансировки нагрузки для платформы моделирования сетей ns-3»

Отчет по преддипломной практике тема диплома
Федеральное государственное автономное образовательное учреждение высшего Профессионального образования

Дипломной практики На тему: «Разработка системы развертывания и управления...
На тему: «Разработка системы развертывания и управления образов операционных систем»

Пояснительная записка к дипломной работе На тему: «Разработка системы...
На тему: «Разработка системы развертывания и управления образов операционных систем»

Отчет о преддипломной практике Тема «Разработка решения для централизованного...
Тема «Разработка решения для централизованного мониторинга ресурсов еис кафедры икт»

Пояснительная записка содержит описание выполнения дипломной работы...
Работа была защищена в 2009 году в Учебно-научно-исследовательском институте Орловского государственного технического университета...

Дипломное проектирование. Тема: «Разработка автоматизированной информационно-поисковой...
...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
odtdocs.ru
Главная страница