<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta />
    <article-meta>
      <title-group>
        <article-title>ГЕО-ОТМЕТКИ НА ОСНОВЕ ИНФОРМАЦИИ О СЕТЕВОЙ БЛИЗОСТИ*</article-title>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <string-name>Namiot D.E.</string-name>
          <email>dnamiot@gmail.com</email>
          <xref ref-type="aff" rid="aff2">2</xref>
          <xref ref-type="aff" rid="aff3">3</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Shabalin D.G.</string-name>
          <email>shabalindm@gmail.com</email>
          <xref ref-type="aff" rid="aff2">2</xref>
          <xref ref-type="aff" rid="aff3">3</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Zubareva E.V.</string-name>
          <email>e.zubareva@cs.msu.ru</email>
          <xref ref-type="aff" rid="aff0">0</xref>
          <xref ref-type="aff" rid="aff1">1</xref>
          <xref ref-type="aff" rid="aff2">2</xref>
          <xref ref-type="aff" rid="aff3">3</xref>
        </contrib>
        <aff id="aff0">
          <label>0</label>
          <institution>Bunin Yelets State University</institution>
          ,
          <addr-line>Yelets</addr-line>
          ,
          <country country="RU">Russia</country>
        </aff>
        <aff id="aff1">
          <label>1</label>
          <institution>Federal Research Center Computer Science and Control of the Russian Academy of Sciences</institution>
          ,
          <addr-line>Moscow</addr-line>
          ,
          <country country="RU">Russia</country>
        </aff>
        <aff id="aff2">
          <label>2</label>
          <institution>Lomonosov Moscow State University</institution>
          ,
          <addr-line>Moscow</addr-line>
          ,
          <country country="RU">Russia</country>
        </aff>
        <aff id="aff3">
          <label>3</label>
          <institution>Namiot Dmitry E., PhD, Senior Researcher faculty of computational mathematics and Cybernetics, Lomonosov Moscow State University</institution>
        </aff>
      </contrib-group>
      <fpage>425</fpage>
      <lpage>436</lpage>
      <abstract>
        <p>1 Московский государственный университет имени М.В. Ломоносова, г. Москва, Россия 2 Елецкий государственнйы университет им. И.А. Бунина, г. Елец, Россия 3 Федеральный исследовательский центр «Информатика и управлен,иге.» МРоАскНва, Россия В работе изложен подход к созданию сервисов, основанных на местоположении, где информация о гео-координатах заменяется данными о сетевой близости. Этот подход основан на использовании сетевой близости для идентификации местоположения мобильных пользователей. Местоположение пользователя «привязывается» непосредственно к беспроводным точкам доступа, без вычисления географических координат. Соответственно, гео-отметки пользователей эмулируются с помощью информации о доступных узлах беспроводной сети. В работе описаны компоненты системы, предоставляющей сервис гео-отметки, предложены схемы с различными функциональными характеристиками. Предложен способ организации эффективного и масштабируемого хранилища данных о местоположении мобильных пользователей в реляционной СУБД. Создана демонстрационная система, предоставляющая сервис гео-отметки, доступная в виде open-source проекта.</p>
      </abstract>
    </article-meta>
  </front>
  <body>
    <sec id="sec-1">
      <title>ON GEO-MARKS BASED ON NETWORK PROXIMITY</title>
      <p>
        The work outlines the approach to creating location-based services, where information about
geocoordinates is replaced with data on network proximity. This approach is based on the use of network
proximity to identify the location of mobile users. The user's location is "snapped" directly to wireless
access points, without computing geographic coordinates. Accordingly, geo-tagged users are
emulated using information about available wireless network nodes. The work describes the
components of the system that provides geo-tagging services, schemes with various functional
characteristics are proposed. A method for organizing an efficient and scalable storage of location
data of mobile users in a relational database is proposed. A demonstration system was created that
provides a geo-tagging service available as an open-source project.
Существуют различные определения контекста. Первоначальрнеодеелеонпие [
        <xref ref-type="bibr" rid="ref1 ref1 ref13 ref13">1</xref>
        ] описывает контекст
как информацию о местоположении, людях, находящихся рядом, и их изменениях. Соответств
контекстно-зависимые вычисления– это вычисления, использующие контекст. В общем случае, под
контекстом понимается любая информ,ацихаярактеризующая ситуацию, в которой оказалась сущность
[
        <xref ref-type="bibr" rid="ref14 ref14 ref2 ref2">2</xref>
        ]. Местоположение входит в понятие контекста. В случае мобильного устройства, данные, образ
контекст, обычно поступают от датчиков, которыми оборудовано устройство.
      </p>
      <p>Концепция контекстн-озависимых вычислений позволяет рассматривать понятие местоположения в
обобщенном смысле, как любую информацию, позволяющую связать конкретного пользователя
некоторой точкой в пространстве или локацией. Например, в качестве данных о местоположении
служить адрес дома, название станции метро или торгового центра. Нахождение устройства пользов
в зоне действия определенной беспроводной сети также позволяет с некоторой точностью локали
его положение в пространстве.</p>
      <p>
        Приложения с зависимостью от молесотжоепния базируются на различных методах определения
местоположения. Традиционным способом определения местоположения является использование
глобальной системы позиционирования (GPS, ГЛОНАСС). Однако сигнал системы глобальной навига
может быть недостнупе в помещениях или густо застроенной местности. Для определен
местоположения в этих условиях используются другие методы [
        <xref ref-type="bibr" rid="ref15 ref15 ref16 ref16 ref3 ref3 ref4 ref4">3, 4</xref>
        ]. Некоторые из них
использования специального оборудования. Так, система локации, основанная на метках R
предполагает наличие у пользователей радиометок (активных или пассивных) и установленны
помещении сканеров, которые определяют положение меток. Система локации-WUidWebBand()Ultra
состоит из установленных в помещении сканеров и приемопередатчиков у пСоклаьнзоерваытелей.
определяют положение приемопередатчиков, и, следовательно, их носителей, анализируя вре
прохождения низкочастотного сигнала.
      </p>
      <p>Системы позиционирования, основанные на анализе сигналов беспроводных точек доступа, WiFi
Bluetooth, имеют ряд пурщеиемств. Такие системы часто представляют чисто программные решения,
требующее использования специального оборудования и соответствующего проприетарного ПО.
Источником сигнала для таких систем могут быть точки доступа, имеющиеся в большом коли
современных городах. Возможно и установление дополнительных беспроводных точек. Приемнико
сигнала может служить любое устройство, поддерживающее взаимодействие по беспроводной с
Использование стандартных частот и протоколов множественного достухпа WiвFi сеитляи Bluetooth
существенно снижают опасность р-аиднитоерференции с другими системами.</p>
      <p>
        Протокол WiFi описывается серией стандартов IEEE 802.11 [
        <xref ref-type="bibr" rid="ref17 ref5">5</xref>
        ]. Стандарт определяет набор
(service set) как множество устройств, относящихся к некоторойй блеоскпарлоьвноодной сети (WLAN).
Идентификатор набора служб (service set identifier, SSID) состоит из 32 байт и обычно пре
понятное для человека имя беспроводной сети. Существуют два режима функционирова–ния сети
инфраструктурный (infrastructurmeode) и Adhoc. В инфраструктурном режиме беспроводные устройства
общаются между собой через точки доступа (access point). В режиме Adhoc связь устанав
непосредственно между устройствами, оборудованными WiFi адаптерами. Беспроводная сеть состоит
блоков, именуемых как базовый набор служб (basic service set). В инфраструктурном режиме
набор служб представляет собой одну точку доступа c соответствующей ей станцией. Базовый
служб имеет идентификатор, обозначаемый как BSSID (bassiect siedrevnitciefier). В инфраструктурном
режиме в качестве BSSID выступает-адрМесАС беспроводной точки доступа. Таким образом,
идентификатором отдельной точки доступа сети WiFi, работающей в инфраструктурном реж
является BSSID, представленный -аМдАрСесом этой точки.
      </p>
      <p>
        Методы определения положения с использованием точек доступа WiFi могут быть разделен
четыре основныx класса. Метод интенсивности сигнала (RSSI) основан на измерении интенсив
сигнала WiFi от нескольких точек доступа. Для вычисцлиеинияисппоолзьизуется трилатерация. Метод
достаточно прост в реализации, однако имеет низкую точность и подверже-зна оншалиибкчаимя из
препятствий с различной радиопрозрачностью. Метод отпечатков (FingerPrints) также основывается
измерении интенсивности двхяощего сигнала. Векторы значений интенсивности сигнала от различных
точек доступа сохраняются в базе данных вместе с сопутствующими координатами. Эта инфо
может быть детерминированной или вероятностной. Для определения координат текущий век
значений интенсивности сравнивается с векторами интенсивностей, сохраненными в базе, с ц
нахождения записи, наилучшим образом соответствующей текущему положению. Имеются так
методики, основанные на измерении времени прохода (ToF) и углов полугчнеанлиояв ([A6]o.A) си
Общей особенностью указанных методов являются необходимость предварительного составления
базы данных (карты) с координатами беспроводных точек доступа. Составление такой ба
поддержание ее в актуальном состоянии является трудной зтаедранчаетйи.внАылйь подход [
        <xref ref-type="bibr" rid="ref15 ref15 ref16 ref16 ref17 ref18 ref19 ref19 ref20 ref20 ref3 ref3 ref4 ref4 ref5 ref6 ref7 ref7 ref8 ref8">3-8,</xref>
        ] 7не
нуждается в базе данных координат беспроводных точек доступа. Идея заключается в том,
идентификации положения пользователя не обязательно вычислять его координаты. Информация мо
быть «привязана» непосредственно ескпробводным сетям или к отдельным точкам доступа. Позиция
пользователя, таким образом, будет идентифицироваться параметрами беспроводных сетей, видим
устройством пользователя. Для наиболее точной идентификации позиции пользователя и приня
решения, каакя информация является для него в данный момент актуальной, могут использов
различные параметры беспроводной сети: SSID, BSSID, сила сигнала (RSSI) и др.
      </p>
      <p>Впервые такой подход был предложен в SpсoиtсEтxем[7е,8]. Эта система позволяет привязывать
данные (например, справочную или рекламную информацию) к публично видимым беспроводным с
или к отдельным точкам доступа. Привязка проходит путем составления базы данных правил.
создаются и редактируются заинтересованными лицами и организацизямиве-бичнетреерфейс.
Устройство пользователя сканирует беспроводные точки доступа и отсылает их параметры на
Сервер сопоставляет полученный набор с хранящимися у него правилами и определяет, какие
соответствуют полученному набору. Предоставелениинформации пользователю происходит в
соответствии с этими правилами.</p>
      <p>Особенностью системы SpotEx является то, что изменение базы данных правил проис
значительно реже, чем обращение к ней за получением информации. Потребителями информ
являются мбоильные пользователи, для которых в общем случае не требуется авторизация,
информация является публично доступной. Авторизация требуется лишь при добавлении
редактировании правил.</p>
      <p>В данной работе предлагается использовать аналогичный подход андиляя ссеорзвдиса -гоетометки,
т.е. сервиса, позволяющего пользователям обмениваться информацией о собственном местоположени
С помощью этого сервиса, мобйилпьонлыьзователь, по прибытию в определенную локацию, может
«отметиться» в ней. Эта отметка «притвсяяз»ываке находящимся в зоне видимости точкам доступа Wi
и становится доступной для других пользователей, находящихся в этой же локации. В отл
экспертной системы SpotEx, серви-сотмгетоки предполагает, что конечные пользователи являются как
источниками, так и потребителям информации, привязанной к беспроводным точкам доступа. Подо
сервис может иметь реализацию, как в виде самостоятельного приложения, так и являться комп
более общей системы сервисов, зависящих от местоположения.</p>
      <p>Типичная мдоель использования (базовый сервис) может выглядеть следующим образом. Мобильн
пользователь авторизуется в приложении с помощью своего идентифFиaкcаeтbоoрoаk. вСистема
запоминает ссылку на аккаунт пользователя и информацию о доступных беспхров(ноадпнрыихмерсе,тя
видимые точки достуWпаi-Fi). Соответственно, любой авторизовавшийся пользователь будет видеть
ссылку на профиль Facвebook (например, картинку из профайлаURLидля перехода) других
пользователей с такими же характеристиками беспроводноугжоенияокр (то есть, по факту,
находящимися гд-ето рядом). Соответственно, можно перейти на страницу такого пользователя
социальной сети и далее уже пользоваться средствами Fэaтcоeйbooсkе,тинап(ример) для контактов.
Естественно, что вмесFтaоcebook может быть любая другая сVетkьonta(kte, LinkedIn, etc.). При этом в
самой социальной сети никакого статус-аотмсеткгоейо (та-кназываемый check-in не создается).
Архитектура системы геoотметки</p>
      <p>Под сервисом -гоетометки будем понимать сервис обмена между теплоялмьзиоваинформацией об их
местоположении. Систему, реализующую серви-сотмгетоки, будем называть системо-йотмгетоки. Под
отметкой местоположения будем понимать информационную единицу, связывающую пользователя
определенным положением в пространстве.моОжнеат иметь атрибуты, такие как время отметки, срок
действия, и др. В данной работе местоположение в пространстве представлено набором идентифик
BSSID беспроводных точек доступа, в зоне действия которых находится устройство пользователя.
образом, отметку местоположения в узком смысле можно понимать как структуру данных, состоя
идентификатора пользователя, набора BSSID и набора атрибутов. Функциями -остемревтиксиа гео
являются создание отметок местоположения, их хранение и обеспеччиенипео врыедзаультатам поиска
среди сохраненных отметок.</p>
      <p>Предлагаемая в данной работе систе-моатмегтекои состоит из сервера, агрегирующего данные о
местоположении пользователей, и клиентской программы, устанавливаемой на мобильные устройств
Клиентская прогрмама обеспечивает сбор и отправку на сервер списка идентификаторов BS
обнаруженных беспроводных точек доступа, а также служебных команд. Получив список BSSID
может:</p>
      <p>а) Использовать полученный список для фиксации местоположения владельца, уссотзрдоайвства
отметку местоположения. Информация о местоположении владельца устройства, сохраненная в в
отметки местоположения, может быть доступна для других пользователей.</p>
      <p>б) Вернуть клиентской программе список пользователей, расположенных в той, чжтео лиокации
владелец устройства.
Клиентская программа, получив список пользователей, отображает его на экране.
Предполагается, что пользователь представлен в системе в виде идентификатора учетной зап
одной из социальных сетей. Для получения идентипфриикатпореравом старте клиентской программы
пользователю предлагается авторизоваться в социальной сети. Для получения фамилий, и
фотографий и других, необходимых для отображения данныпохльозователях, клиентская
программа формирует запрос к соответствмуюсщеирвисам социальной сети. Общая архитектура системы
изображена на рис. 1.</p>
      <p>Рис. 1. Общая архитектура системы гео-отметки
Детали функционирования</p>
      <p>Для определения, находятся ли пользователи в одной локации, используется следующий крит
наличие хотя обдыной точки доступа, видимой устройствами обоих пользователей. В терминах отме
о местоположении наличие общей точки доступа означает, что у каждого пользователя и
действующая отметка, и множества BSSID у этих отметок имеют не пустРоаессмпоетррееснеичение.
более сложных критериев близости, учитывающих, например, количество совместно видимых точек
интенсивность сигнала (RSSI), выходит за рамки данной работы. Отметим лишь, что задачу
пользователей с использованием сложных критериеовстиблимзожно свести к задаче поиска по простому
критерию с последующим наложением некоторых фильтров на результат выборки.</p>
      <p>Отметка местоположения пользователя может характеризоваться таким параметром, как видимост
Видимая отметка является публичной и жа щсоадяесря в ней информация о местоположении
пользователя может быть отображена устройствами других пользователей.</p>
      <p>Если отметка невидима, то информация о местоположении пользователя доступна только серв
самому пользователю. Невидимые отметки могут зоивсаптоьлсья для сбора статистики посещений, или в
других целях. В простейшем случае все отметки являются видимыми.</p>
      <p>Отметим следующую особенность, которую следует учитывать при выборе архитектуры- системы
отметки. Как было сказано, список BSSID, полсуечревнерноымй, может использоваться в двух целях: для
фиксации местоположения владельца устройства (создания отметки), и поиска пользователе
находящихся в той же локации, что и владелец устройства.</p>
      <p>С точки зрения экономии трафика целесообразно организоавиамтьодейвсзтвие клиентской
программы и сервера таким образом, чтобы полученный сервером список BSSID использо
одновременно в обоих целях. С другой , тсаткоорйоныподход может быть недостаточно гибким для
придания системе нужных эксплуатационных харасктитекр.и</p>
      <p>Для описания различных способов организации работы системы геоотметки и выбора конкре
схемы с необходимой функциональностью, рассмотрим статический и динамический аспект
функционирования. Статический аспект функционирования системы опредаеклоягеот, рокда структуры
данных хранятся в системе и могут быть доступны для обработки и отображения. Для
структуры хранимых данных удобно использовать объектную модель. Замедтаинмн,омчтораздвеле
объектная модель используется для описания лоойгичсетсркуктуры данных, а не конкретных классов
языка программирования. Базовыми элементами объектной модели являются:
• пользователь (User;)
• отметка местоположения пользователя (Che;ckin)
• беспроводная точка доступа (WirelessSpot).
Объектная модель данных мохжареатктеризоваться:
1. Возможным количеством отметок местоположения на одного пользователя. В простейшем слу
пользователю соответствует одна отметка, соответствующая его последнему местоположению. В бо
сложных случаях может храниться более однтокйи. отЭмтое позволяет получать данные не только о
текущем местоположении, но и, например, историю перемещений пользователя.</p>
      <p>2. Состояниями или типами отметок. Как было указано выше, предлагается рассматривать вид
и невидимые отметки.</p>
      <p>3. Набором атрибутов,характеризующих базовые элементы объектной модели. Например,
атрибутами отметки местоположения могут быть время создания, срок действия, и др..</p>
      <p>4. Дополнительной информацией, привязанной к базовым элементам модели: к пользователю,
отметке, к точкам удпоас.т Например, к точкам доступа может быть привязана справочная или рекла
информация. Отметим, что детальное обсуждение дополнительных сервисов, которые мож
предоставлять система -гоетометки, выходит за рамки текущей работы.</p>
      <p>Примеры диаграмм для котбнъоей структуры данных приведены на рис. 2.</p>
      <p>Рис. 2. Варианты объектной структуры данных, хранимых на сервере. Срок действия ttl указан в скобках, что
означает, что имеется два варианта объектной структуры: в одной из них атрибут ttl присутствует, а в другой –
отсутствует
Динамический аспект функционирования системы определяется, главным образом, правилами
создания, удаления и изменения атрибутов отметок местоположения, т.е. жизненным циклом отм
Жизненный цикл отметки характеризуется двумя аспектами:
1. Правилами фиксации положения пользователя, т.е. создания отметки.</p>
      <p>2. Правилами отслеживания положения пользователя после создания отметки. Эти правила ну
для определения момента, после которого будет считаться, что пользователь покинул отмече
положение.</p>
      <p>В части фиксации положения пользователя (создания отметки) можно предложить следующ
варианты организации жизненного цикла отметки местоположения (рис. 3):</p>
      <p>1. Отметка всегда является видимой и создается при каждом получении списка тBвSаSID от ус
пользователя. См. рис. 3 а.</p>
      <p>2. Отметка всегда является видимой и создается при получении списка BSSID совместно с
указанием создать отметку. См. рис. 3 б.</p>
      <p>3. Отметка может быть невидимой. При получении списка BSSID создается невидимая отм
Впоследствии она может стать видимой при получении соответствующей команды от пользовател
рис. 3 в.
4. Отметка может быть невидимой. При получении списка BSSID создается невидимая отметка,
получении списка BSSID одновременно с соответствуюащнедйой к–овмидимая. См. рис. 3 г.
В части отслеживания местоположения пользователя можно предложить следующие подходы:
1. Без отслеживания. Отметка имеет единственный а–тврриебмуят создания, и удаляется только
тогда, когда становиться заведомо не акт.уалПьрниойпопадании в определенную локацию пользователь
сможет увидеть список других пользователей, отмечавшихся в этой локации, сортированный по в
отметки.</p>
      <p>2. Отслеживание по времени. Отметка имеет два –атврриебмуята создания и срок действия. По
истечении сроакдействия пользователь считается покинувшим локацию. Срок действия может быть:
• фиксированным.
• задаваемым пользователем.</p>
      <p>При получении нового списка BSSID или команд пользователя возможно автоматическое изме
срока действия отметки в стомреонньушеуния или увеличения.</p>
      <p>3. Непрерывное отслеживание. Передача списка BSSID происходит через определенные интервал
Отслеживание может происходить:
• все время при включенном приложении (режим on/off).</p>
      <p>• начинаться или заканчиваться при наступлении опнрыедхеленсобытий. Например,
отслеживание может начинаться после создания отметки и заканчиваться через некоторый проме
времени. Отметим, что режим с непрерывным отслеживанием требует большего расхода бата
потребляет больше трафика.</p>
      <p>Рис 3. Способы организации жизненного цикла отметки местоположения. Обозначения: BSSIDs – получение списка
BSSID, checkin – получение команды создать видимую отметку. Not exists – отметка не создана, Visible – видимая
отметка, Invisible – невидимая отметка
Примеры конкретных схем</p>
      <p>Схема А. Данная схема является одной из простейших. Для каждого пользователя на сервере
единственная отметка, соответствующая его последнему местоположению (рис. 2 а). Она
единственный атрибут– время создания. При каждом полученсиписка BSSID от устройства
пользователя происходит обновление данных о местоположении пользователя (рис. 3 а). Отслежи
положения пользователя не ведется.</p>
      <p>При прибытии в некоторую локацию L пользователь запускает клиентскую программу с целью
какие еще пользователи, кроме него, находятся в локации L. Устройство пользователя сканирует
беспроводных точек доступа и отправляет его на сервер. Предыдущая отметка удаляется, и вм
создается новая, соответствующая локации L. В ответ телпьользпоовлаучает список других
пользователей, отмеченных в локации L. Для каждого пользователя отображается время его от
локации.</p>
      <p>Схема B. Следующая схема была выбрана для демонстрационной реализации. Для ка
пользователя на сервере храниться тевдеиннсая отметка, соответствующая его последнему
местоположению (рис. 2а). Она имеет в качестве атрибутов время создания и срок действия.
создается при получении данных позиционирования с указанием создать отметку (рис 3. б
действия выбираетяс пользователем при создании отметки.</p>
      <p>При прибытии в некоторую локацию L пользователь может запустить клиентскую программу и
какие еще пользователи, кроме него, находятся в локации L. Кроме того, пользователь при жела
сам отметиться в цлиоика L. При создании отметки пользователь выбирает интервал времени, в те
которого он планирует находиться в данной локации (15 мин, 30 мин, 1 ч, и т.д.). Спи
пользователем BSSID и выбранный интервал времени пересылается на сервзедранися цоетлмьюеткисо
местоположения. После создания отметки информация том, что пользователь находится в локац
будет доступна другим пользователям, находящимся в этой локации, в течение указанного инт
времени.
Способы организации хранилища данных о местоположении пользователей</p>
      <p>Проанализировав различные аспекты функционирования системы, предоставляющей сервис
геоотметки, можно сделать вывод, что организация хранилища отметок местоположения пользоват
требует эффективной реализации следующих базоеврыахцийо:п</p>
      <p>1. Поиск пользователей по списку BSSID. Устройство пользователя посылает спис
идентификаторов точек доступа, которые оно видит в настоящий момент, и в ответ получае
пользователей, находящихся в радиусе действия этих точек.</p>
      <p>2. Создание отемтки о местоположении пользователя. Сервер получает список BSSID и сохраняет
в виде отметки;
3. Удаление отметки о местоположении пользователя.</p>
      <p>Операция удаления единичной отметки в некоторых случаях может быть не обязател
Неактуальные отметки мутог накапливаться в системе и удаляться групповым образом во время за
обслуживающей процедуры. В некоторых случаях две или три операции могут быть объединены
целью оптимизации. Например, в системе, использующей схему А, все три воыпепроалцнияиютсвясегда
последовательно: удаление предыдущей отметки, создание новой и поиск пользователей по списку
Кроме перечисленных также могут требоваться сервисные операции, связанные с удалением
хранилища неактуальной информации: неактивных потлеьлзеойва, их отметок, неиспользуемых BSSID.</p>
      <p>Структуры данных, описанные выше, можно хранить в реляционной СУБД естественным обр
сохраняя каждую пару {BSSID, отметка} в отдельной строке таблицы. Однако, в таком случае,
поиска пользователей по сксупиBSSID потребует выборки всех этих строк. Если обо–зснраечдинтеье за u
количество пользователей в радиусе видимости одной беспроводной точки –дсорстедупнае,е w
количество точек доступа, видимых устройством пользователя, то количество обращкуе,ний к д
необходимых для выполнения операции поиска пользователей, можно оценить как u*w.
Рис. 4. Схема базы данных c высокой степенью нормализации, используемая в системе гео-отметки, работающей по
схеме А. user_id – идентификатор пользователя, time – время отметки, BSSID – идентификатор беспроводной точки
доступа
Поясним сказанное на примере системы, работающей по схеме А. Для этой системы
использовать базу данных со схемой, изображенной на рис. 4. Операция поиска пользователей п
BSSID может тбьы выполнена с помощью запроса:</p>
      <p>SELECT DISTINCT USER_ID FROM CROSS_TABLE WHERE BSSID IN {список BSSID}
Выполнение этого запроса потребует выборки из таблицы CROSS_TABLE всех строк, BSSID к
находится в заданном списке. В общем случае строки OSтSа_бTлAиBцLыE CфRизически расположены на
диске не упорядоченно, поэтому выборка каждой строки потребует перемещения головки диска.</p>
      <p>В настоящей работе мы предлагаем способ организации хранилища данных, позволяющий уменьш
количество дисковых операций, необхоыдхим для выполнения запросов. При этом объем данных,
хранимых на диске, увеличивается, а сами данные хранятся в реляционной СУБД в ненормализ
форме. Рассмотрим суть этого подхода на примере организации хранилища для системы со схем
Данные хранятяс в реляционной базе данных со схемой, изображенной на рис 5. В базе
поддерживается структура из двух таблиц. Одна из них содержит списки беспроводных точек дос
каждого пользователя, друг–аясписки пользователей для каждой беспроводноий дтосчткупа. Списки
хранятся в виде строки с использованием разделителя (например, запятой) и обновляются при по
новых данных о местоположении пользователей.
Рис. 5. Схема базы данных для системы геоотметки, работающей по схеме А. user_id – идентификатор пользователя,
time – время отметки, BSSID_list – список идентификаторов беспроводных точек доступа, user_list – список
идентификаторов пользователей, находящихся вблизи беспроводной точки доступа
}
// Удаление записи из таблицы PERSON
DELETE FROM PERSON WHERE USER_ID=:u.userId;
}
3. Поиск пользователей ппоисксу BSSID.
class User{
StringuserID;
Date time;
}
User[] getUsersNear(String[] bssidList){
// Выборка строк из таблицы PERSON
String[] user_lists ={SELECT USER_LIST FROM WIRELESS_SPOT WHERE BSSID IN (:bssidList)};
// разделение всех строк из userа_listоsтденльные идентификаторы, выборка неповторяющихся
идентификаторов и создание на их основе массива из User.</p>
      <p>User[] united_user_list= makeUnitedList(user_lists);
// нахождение и установка атрибута времени для каждого пользователя. for(User[]
united_user_list){
u.time = {SELECT TIME FROM PERSON WHERE USER_ID = :u.userId};
}
returnunited_user_list;
}
При выполнении операции поиска пользователей по списку BSSID, после создания объедине
множества идентификаторов пользователей происходит обращение е табPлEиRцSON за временем
отметки, что требует дополнительных дисковых операций. Решением может быть хранение вре
создания отметки в таблице WIRELESS_SPOT вместе с идентификаторами пользователей.</p>
      <p>Отметим, что во многих случаях, и для схемы А верацчиасятноссотзид,аниояп отметки и операция
поиска пользователей часто выполняются последовательно в рамках одного запроса. Как нетр
заметить, эти операции требуют обращения к одним и тем же строчкам таблицы WIRELESS_SPOT.
целесообразно объединить этпиераоции, избежав лишних обращений к базе данных.</p>
      <p>В системе ге-отметки, работающей по схеме B (используется в демонстрационной реализаци
используется схем,аизображенная на рис. 6.
Рис. 6. Схема базы данных, используемая в системе, работающей по схеме В. user_id, – идентификатор пользователя,
BSSID_list – список беспроводных точек доступа, user_list – строка, содержащая список идентификаторов</p>
      <p>пользователей, находящихся вблизи беспроводной точки доступа, и сроки действия их отметок
Для наибольшей проиодзвительности в поле user_list вместе с каждым идентификатором
пользователя хранится закодированное значение времени, после которого отметка становится
актуальной. Базовые операции происходят аналогичным образом. При выполнении операции пои
пользователей по списку BSSID учитывается срок действия отметки: пользователи, срок дей
отметок которых истек, не попадают в выборку. Имеется также сервисная операция, удаляющая
пользователей, срок действия которых завершился. Она представляет хосдобопйо пврсоем строкам
таблицы WIRELESS_SPOT и вычеркивание из списков user_list идентификаторов пользователей, с
действия отметки которых истек. Операция нужна, чтобы избежать разрастания списков user_
таблице WIRELESS_SPOT.</p>
      <p>Для систем -гоетометки, использующих модель данных с более чем одной отметкой на одн
пользователя (рис. 2 б), можно использовать схему, изображенную на рис. 7. Роль первичного
таблице CHECKIN играют идентификатор пользователя и время отметки. Базовые оператции проис
аналогично.</p>
      <p>Предлагаемый способ организации хранилища данных легко обобщается на случай, есл
архитектуре используются видимые и невидимые отметки. Одним из способов является хранение
по видимым и невидимым отметкам в различных таблиацзаахн, о канка проикс. 8.
Рис. 7. Схема базы данных, позволяющая хранить более одной отметки местоположения на каждого пользователя.</p>
      <p>user_id – идентификатор пользователя, time – время отметки, ttl – срок действия отметки, BSSID_list – список
беспроводных точек доступа, checkin_list – строка, содержащая список отметок, совершенных в радиусе действия
беспроводной точки доступа; строка checkin_list содержит идентификаторы пользователей, времена и сроки
действия их отметок
Рис. 8 . Возможная схема базы данных, обеспечивающая хранение отметок различных типов – видимых и невидимых.
user_id – идентификатор пользователя, time – время отметки, ttl – срок действия отметки, BSSID_list – список
видимых пользователем беспроводных точек доступа, visible_checkin_list – список видимых отметок,</p>
      <p>invisible_checkin_list – список невидимых отметок
Демонстрационная реализация системы гео-отметки</p>
      <p>
        Для демонстрационной реализации системы геоотметки была выбрана схема В, описанная в
Клиентское приложение реализовано для платформыid. AnПdрroиложение работает с аккаунтами из
социальной сети Facebook. Для входа в Facebook, а также получения от Facebook данных, необхо
отображения списка пользователей, использовалась предлагаемая Facebook библиотека Facebook SDK
Android [
        <xref ref-type="bibr" rid="ref21 ref21 ref9 ref9">9</xref>
        ]. Снимки экрана клиентского приложения приведены на рис. 9. Скомпилирова
приложение и его исходный код лежат в репозитории:
https://github.com/shabalindm/SSID_Checkin_Demo,
ссылка для скачивания скомпилированного приложения:
https://github.com/shabalindm/SSID_Checkin_Demo/blob/master/release/SSID_Checkin_Demo.apk.
      </p>
      <p>
        Серверная часть написана на java и исполняется под управлением сервера прилож
Взаимодействие с базой данных происходит с использованием технологии JDBC через интер
javax.sql.DataSource. Реализация этого интерфейса обеспечивает поддержание пула соединений с ба
данных и пула подготовленных запросов (PreparedStatement), обеспечивая эффективную работу
многопоточном режиме. Схема базы данных представлена на рис. 6. Сервереспзлааптунщомен на б
хостинге OpenShift [
        <xref ref-type="bibr" rid="ref10 ref22">10</xref>
        ], с использованием СУБД Postgresql. Исходный код серверной части л
репозитории: https://github.com/shabalindm/SSID_Checkin_Demo_S.
Рис. 9. Снимки экрана демонстрационной реализации приложения гео-отметки
а – авторизация при первом входе, б – просмотр списка пользователей, находящихся поблизости, с – диалог при
отметке, г – просмотр списка пользователей после отметки
Заключение
      </p>
    </sec>
    <sec id="sec-2">
      <title>References</title>
      <p>Об авторах:
Намиот Дмитрий Евгеньевич, акндидат физик-оматематических наук, старший научный сотрудник
лаборатории открытых информационных технолофгаикйультета вычислительной математики
и кибернетики, Московский государственный университет именЛиомонМо.сВо. ва,
dnamiot@gmail.com
Шабалин Дмитрий Григорьевич, выпускник факультета вычислительной математики и кибернетики,
Московский государственный университет имени М.В. Ломоsнhоaсbоaвliаn,dm@gmail.com
Зубарева Елена Васильевна, кандидат педагогических наук, доцент, руководитель Центра открытых
информационных технологий, Елецкий государственный университет им. И.Ан.ауБчнуныийна;
сотрудник, Федеральный исследовательский центр «Информатика и управление» Российской
академии наук; старший научный сотрудник лаборатории открытых информационных
технологий факультета вычислеилтьной математики и кибернетики, Московский
государственный университет имени М.В. Ломонeо.сzоuвbаa,reva@cs.msu.ru</p>
    </sec>
  </body>
  <back>
    <ref-list>
      <ref id="ref1">
        <mixed-citation>
          1.
          <string-name>
            <surname>Schilit</surname>
            <given-names>B.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Adams</surname>
            <given-names>N.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Want</surname>
            <given-names>R</given-names>
          </string-name>
          .
          <article-title>Context-aware computing applications</article-title>
          . // IEEE Workshop on Mobile
          <source>Computing Systems and Applications (WMCSA'94)</source>
          . - Santa Cruz, CA, US:
          <year>1994</year>
          . - P.
          <fpage>89</fpage>
          -
          <lpage>101</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref2">
        <mixed-citation>
          2.
          <string-name>
            <surname>Anind</surname>
            <given-names>K.</given-names>
          </string-name>
          <string-name>
            <surname>Dey</surname>
          </string-name>
          . Understanding and Using Context // Personal Ubiquitous Computing.
          <article-title>-</article-title>
          <year>2001</year>
          .
          <article-title>- №5 (1)-</article-title>
          .
          <source>P. 4-7.</source>
        </mixed-citation>
      </ref>
      <ref id="ref3">
        <mixed-citation>
          3.
          <string-name>
            <surname>Namiot</surname>
            <given-names>D.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Schneps-Schneppe M. About</surname>
          </string-name>
          location-aware mobile messages // Next Generation Mobile Applications,
          <source>Services and Technologies (NGMAST)</source>
          ,
          <year>2011</year>
          5th
          <string-name>
            <given-names>International</given-names>
            <surname>Conference</surname>
          </string-name>
          . - Cardiff:
          <year>2011</year>
          . -P.
          <fpage>48</fpage>
          -
          <lpage>53</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref4">
        <mixed-citation>
          4.
          <string-name>
            <surname>Namiot</surname>
            <given-names>D</given-names>
          </string-name>
          . On Indoor Positioning // International Journal of Open Information Technologies.
          <article-title>-</article-title>
          <year>2015</year>
          . - №
          <volume>3</volume>
          .3. - P.
          <fpage>23</fpage>
          -
          <lpage>26</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref5">
        <mixed-citation>
          5.
          <string-name>
            <surname>Varshney</surname>
            <given-names>U.</given-names>
          </string-name>
          <article-title>The status</article-title>
          and
          <source>future of 802</source>
          .11-based WLANs //Computer. - 2003. -
          <fpage>Т</fpage>
          .
          <year>36</year>
          . -
          <fpage>№</fpage>
          . 6. -
          <fpage>С</fpage>
          .
          <fpage>10</fpage>
          -
          <lpage>2105</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref6">
        <mixed-citation>
          6.
          <string-name>
            <surname>Lassabe F</surname>
          </string-name>
          . et al.
          <article-title>Indoor Wi-Fi positioning: techniques and systems //annals of telecommunications-annales des télécommunications</article-title>
          .
          <source>- 2009</source>
          . -
          <fpage>Т</fpage>
          .
          <year>64</year>
          . -
          <fpage>№</fpage>
          .
          <fpage>9</fpage>
          -
          <lpage>10</lpage>
          . - С.
          <year>651</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref7">
        <mixed-citation>
          7.
          <string-name>
            <surname>Namiot</surname>
            <given-names>D.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Sneps-Sneppe</surname>
            <given-names>M</given-names>
          </string-name>
          .
          <article-title>Context-aware data discovery // Intelligence in Next Generation Networks (ICIN</article-title>
          ),
          <year>2012</year>
          16th International Conference on. - IEEE Conference,
          <year>2012</year>
          . - P.
          <fpage>134</fpage>
          -
          <lpage>141</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref8">
        <mixed-citation>
          8.
          <string-name>
            <surname>Namiot</surname>
            <given-names>D.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Schneps-Schneppe</surname>
            <given-names>M</given-names>
          </string-name>
          .
          <article-title>Proximity as a service // Future Internet Communications (BCFIC</article-title>
          ),
          <year>2012</year>
          2nd
          <string-name>
            <given-names>Baltic</given-names>
            <surname>Congress on</surname>
          </string-name>
          . - Vilnius:
          <year>2012</year>
          . - P.
          <fpage>199</fpage>
          -
          <lpage>205</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref9">
        <mixed-citation>
          9.
          <string-name>
            <surname>Facebook</surname>
            <given-names>SDK</given-names>
          </string-name>
          для
          <string-name>
            <surname>Android</surname>
            <given-names>URL</given-names>
          </string-name>
          : https://developers.facebook.com/docs/android (дата обращения:
          <volume>23</volume>
          .
          <fpage>08</fpage>
          .
          <year>2017</year>
          ).
        </mixed-citation>
      </ref>
      <ref id="ref10">
        <mixed-citation>
          10.
          <string-name>
            <surname>OpenShift: PaaS by Red Hat</surname>
          </string-name>
          , Built on Docker and Kubernetes URL: https://www.openshift.com/ (дата обращения:
          <volume>23</volume>
          .
          <fpage>08</fpage>
          .
          <year>2017</year>
          ).
        </mixed-citation>
      </ref>
      <ref id="ref11">
        <mixed-citation>
          11.
          <string-name>
            <surname>Namiot</surname>
            <given-names>D.</given-names>
          </string-name>
          <article-title>Network proximity on practice: Context-aware applications</article-title>
          and Wi-Fi proximity //International Journal of Open Information Technologies.
          <article-title>-</article-title>
          <year>2013</year>
          . -
          <fpage>Т</fpage>
          . 1. -
          <fpage>№</fpage>
          . 3.
          <string-name>
            <surname>- С</surname>
          </string-name>
          . -
          <volume>14</volume>
          .
        </mixed-citation>
      </ref>
      <ref id="ref12">
        <mixed-citation>
          12.
          <string-name>
            <surname>Намиот</surname>
            <given-names>Д. Е.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Зубарева</surname>
            <given-names>Е</given-names>
          </string-name>
          . В.
          <article-title>Об одном способе доставки информации мобильным пользователям</article-title>
          //International J Open Information Technologies.
          <article-title>-</article-title>
          <year>2017</year>
          . -
          <fpage>Т</fpage>
          .
          <fpage>5</fpage>
          -. №. -
          <lpage>8С</lpage>
          ..
          <fpage>12</fpage>
          -
          <lpage>17</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref13">
        <mixed-citation>
          1.
          <string-name>
            <surname>Schilit</surname>
            <given-names>B.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Adams</surname>
            <given-names>N.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Want</surname>
            <given-names>R</given-names>
          </string-name>
          .
          <article-title>Context-aware computing applications</article-title>
          . // IEEE Workshop on Mobile
          <source>Computing Systems and Applications (WMCSA'94)</source>
          . - Santa Cruz, CA, US:
          <year>1994</year>
          . - P.
          <fpage>89</fpage>
          -
          <lpage>101</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref14">
        <mixed-citation>
          2.
          <string-name>
            <surname>Anind</surname>
            <given-names>K.</given-names>
          </string-name>
          <string-name>
            <surname>Dey</surname>
          </string-name>
          . Understanding and Using Context // Personal Ubiquitous Computing.
          <article-title>-</article-title>
          <year>2001</year>
          .
          <article-title>- №5 (1)-</article-title>
          .
          <source>P. 4-7.</source>
        </mixed-citation>
      </ref>
      <ref id="ref15">
        <mixed-citation>
          3.
          <string-name>
            <surname>Namiot</surname>
            <given-names>D.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Schneps-Schneppe M. About</surname>
          </string-name>
          location-aware mobile messages // Next Generation Mobile Applications,
          <source>Services and Technologies (NGMAST)</source>
          ,
          <year>2011</year>
          5th
          <string-name>
            <given-names>International</given-names>
            <surname>Conference</surname>
          </string-name>
          . - Cardiff:
          <year>2011</year>
          . -P.
          <fpage>48</fpage>
          -
          <lpage>53</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref16">
        <mixed-citation>
          4.
          <string-name>
            <surname>Namiot</surname>
            <given-names>D</given-names>
          </string-name>
          . On Indoor Positioning // International Journal of Open Information Technologies.
          <article-title>-</article-title>
          <year>2015</year>
          . - №
          <volume>3</volume>
          .3. - P.
          <fpage>23</fpage>
          -
          <lpage>26</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref17">
        <mixed-citation>
          5.
          <string-name>
            <surname>Varshney</surname>
            <given-names>U.</given-names>
          </string-name>
          <article-title>The status</article-title>
          and
          <source>future of 802</source>
          .11-based WLANs //Computer. - 2003. -
          <fpage>Т</fpage>
          .
          <fpage>36</fpage>
          -. №.
          <fpage>6</fpage>
          -.
          <source>С</source>
          .
          <volume>10</volume>
          -
          <fpage>2105</fpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref18">
        <mixed-citation>
          6.
          <string-name>
            <surname>Lassabe F</surname>
          </string-name>
          . et al.
          <article-title>Indoor Wi-Fi positioning: techniques and systems //annals of telecommunications-annales des télécommunications</article-title>
          .
          <source>- 2009</source>
          . -
          <fpage>Т</fpage>
          .
          <fpage>64</fpage>
          -. №. -
          <lpage>910</lpage>
          . - С.
          <year>651</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref19">
        <mixed-citation>
          7.
          <string-name>
            <surname>Namiot</surname>
            <given-names>D.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Sneps-Sneppe</surname>
            <given-names>M</given-names>
          </string-name>
          .
          <article-title>Context-aware data discovery // Intelligence in Next Generation Networks (ICIN</article-title>
          ),
          <year>2012</year>
          16th International Conference on. - IEEE Conference,
          <year>2012</year>
          . - P.
          <fpage>134</fpage>
          -
          <lpage>141</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref20">
        <mixed-citation>
          8.
          <string-name>
            <surname>Namiot</surname>
            <given-names>D.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Schneps-Schneppe</surname>
            <given-names>M</given-names>
          </string-name>
          .
          <article-title>Proximity as a service // Future Internet Communications (BCFIC</article-title>
          ),
          <year>2012</year>
          2nd
          <string-name>
            <given-names>Baltic</given-names>
            <surname>Congress on</surname>
          </string-name>
          . - Vilnius:
          <year>2012</year>
          . - P.
          <fpage>199</fpage>
          -
          <lpage>205</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref21">
        <mixed-citation>
          9.
          <string-name>
            <surname>Facebook</surname>
            <given-names>SDK</given-names>
          </string-name>
          для
          <string-name>
            <surname>Android</surname>
            <given-names>URL</given-names>
          </string-name>
          : https://developers.facebook.com/docs/android (дата обращения:
          <volume>23</volume>
          .
          <fpage>08</fpage>
          .
          <year>2017</year>
          ).
        </mixed-citation>
      </ref>
      <ref id="ref22">
        <mixed-citation>
          10.
          <string-name>
            <surname>OpenShift: PaaS by Red Hat</surname>
          </string-name>
          , Built on Docker and Kubernetes URL: https://www.openshift.com/ (дата обращения:
          <volume>23</volume>
          .
          <fpage>08</fpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref23">
        <mixed-citation>
          11.
          <string-name>
            <surname>Namiot</surname>
            <given-names>D.</given-names>
          </string-name>
          <article-title>Network proximity on practice: Context-aware applications</article-title>
          and Wi-Fi proximity //International Journal of Open Information Technologies.
          <article-title>-</article-title>
          <year>2013</year>
          . -
          <fpage>Т</fpage>
          .
          <fpage>1</fpage>
          -. №. 3
          <string-name>
            <given-names>-.</given-names>
            <surname>С</surname>
          </string-name>
          . -
          <volume>14</volume>
          .
        </mixed-citation>
      </ref>
      <ref id="ref24">
        <mixed-citation>
          12.
          <string-name>
            <surname>Namiot</surname>
            <given-names>D.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Zubareva</surname>
            <given-names>E</given-names>
          </string-name>
          . On one approach to delivering information to mobile users //International Journal of Open Information Technologies.
          <article-title>-</article-title>
          <year>2017</year>
          . -
          <fpage>Т</fpage>
          .
          <fpage>5</fpage>
          -. №.
          <fpage>8</fpage>
          -.
          <source>С</source>
          . 1-
          <fpage>217</fpage>
          .
        </mixed-citation>
      </ref>
    </ref-list>
  </back>
</article>