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

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

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

Задача связи между мобильными узлами является одной из самых фундаментальных задач в децентрализованных мобильных сетях и лежит в основе многих алгоритмов, таких как подсчет количества узлов, выборы лидера, обработка данных и т. д. Получить представление о нескольких важных проблемах в децентрализованных мобильных сетях можно в [ ]. Работа Хацигианнакиса, Николетсиса и Спиракиса [5] посвящена беспроводным мобильным сетям, которые подвержены высокодинамичным структурным изменениям, вызванным мобильностью, флуктуациями каналов и отказами устройств. Эти изменения влияют на топологическую связность, происходят с высокой частотой и не могут быть предсказаны заранее. Поэтому среда, в которой перемещаются узлы (в трехмерном пространстве с возможными препятствиями), а также движение, которое выполняют узлы, являются входными данными для любого распределенного алгоритма.

Пространство возможных движений мобильных узлов комбинаторно обобщается графом движений, т. е. подробные геометрические характеристики движения игнорируются. Предполагается, что каждый мобильный узел имеет диапазон передачи, представленный сферой tr с центром в самом этом узле. Любой другой узел внутри сферы tr может получить любое сообщение, переданное данным узлом. Эта сфера аппроксимируется кубом tc с объемом V(tc), где V(tc) < V(tr). Размер tc может быть выбран таким образом, чтобы его объем V(tc) был максимальным, при условии сохранения соотношения V(tc) < V(tr); и если мобильный узел внутри tc передает сообщение, то это сообщение получает любой другой узел в tc. Учитывая, что мобильные узлы движутся в пространстве S, это пространство можно разделить на последовательные кубы объема V(tc).

'''Определение 1'''. Граф движения G(V, E), (|V| = n, |E| = m), который соответствует квантованию S, строится следующим образом: узел u 2 G представляет куб объемом V(tc), а ребро (u, v) 2 G существует, если соответствующие кубы являются смежными.

Количество узлов n фактически аппроксимирует соотношение между объемом V(S) пространства S и пространством, занимаемым диапазоном передачи мобильного узла V(tr). В предельном случае, когда V(S) & V(tr), диапазон передачи узлов аппроксимирует пространство, в котором они движутся, и n = 1. Учитывая диапазон передачи tr, n линейно зависит от объема пространства S независимо от выбора tc, и n = O(V(S)/V(tr)). Соотношение V(S)/V(tr) является относительным размером пространства движения и обозначается p. Поскольку ребра G представляют собой соседние многогранники, каждый узел связан с постоянным числом соседей, из чего следует, что m = 0(n). В данном примере, где tc является кубом, G имеет максимальную степень 6, и m < 6n. Таким образом, граф движения G (обычно) является графом ограниченной степени, поскольку он получен из обычного графа невысокой степени путем удаления его частей, соответствующих препятствиям для движения или связи. Обозначим за A максимальную степень вершины графа G.

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

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

Основная идея заключается в том, чтобы воспользоваться преимуществами естественного движения мобильных узлов путем обмена информацией при каждой случайной встрече мобильных узлов. Однако представляется очевидным, что если узлы расположены в удаленных областях и не выходят за их пределы, то информация никак не сможет до них дойти, если только протокол специально не позаботится о таких ситуациях. Хацигианнакис, Николетсис и Спиракис [5] предложили следующую идею – заставить только небольшое подмножество развернутых узлов перемещаться в соответствии с требованиями протокола; они называют это подмножество узлами поддержки сети. При наличии таких узлов они могут использоваться для реализации простой, корректной и эффективной стратегии связи между любой парой узлов сети, которая позволяет избежать переполнения ее сообщениями.

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

Протокол 1 (протокол координации движения поддержки «Змея»). Пусть S0, S1, ..., S^-i – члены команды поддержки, а за S0 обозначается узел-лидер (возможно, избранный). Протокол заставляет узел S0 совершить случайное перемещение по графу движения, а каждый из остальных узлов Si должен выполнить простой приказ «переместиться туда, где раньше находился Si-1». Когда S0 готов двигаться, он посылает S1 сообщение, в котором указывается новое направление движения. S1 изменит направление движения в соответствии с инструкциями S0 и передаст сообщение S2. Аналогичным образом, Si будет следовать приказам Si-1 после передачи новых инструкций Si +1. Приказы на движение, полученные Si, помещаются в очередь Qi для последовательной обработки. Самый первый ход Si, 8i 2 f1; 2... , k - 1g задерживается на период времени 8.

Цель случайного блуждания «головы змеи» S0 заключается в том, чтобы обеспечить покрытие в течение некоторого конечного времени всего графа G без знания и запоминания деталей топологии, кроме локальных. Такое движение без запоминания также обеспечивает справедливость, низкий уровень издержек и устойчивость к структурным изменениям.

Рассмотрим случай, когда любому отправителю или получателю разрешена неизвестная стратегия движения общего вида, но его стратегия предоставляется соперником с ограниченным движением. Это означает, что каждый узел, не являющийся узлом поддержки, либо (а) выполняет детерминированное движение, которое или останавливается в вершине, или входит в бесконечный цикл после некоторой начальной части, либо (б) реализует стохастическую стратегию, которая, однако, не зависит от движения узлов поддержки. Авторы в [ ] приводят следующие доказательства корректности и эффективности. Для получения полноценного представления о цепях Маркова и случайных блужданиях читателю предлагается ознакомиться с превосходной книгой Олдоса и Филла [1].

Теорема 1. Узлы поддержки и протокол координации движения типа «змея» гарантируют надежную коммуникацию между любой парой отправитель-получатель (A, B) за конечное время, ожидаемое значение которого ограничено только функцией относительного размера пространства движений p и не зависит от числа узлов, а также не зависит от того, как движутся MHS и MHR, при условии, что мобильные узлы, не входящие в подмножество поддержки, не пытаются намеренно избежать встречи с узлами поддержки.

Теорема 2. Ожидаемое время передачи между узлами поддержки и протоколом координации движения типа «змея» ограничено сверху 0(*Jmc), когда (оптимальный) размер подмножества поддержки равен k = 2mc, а c равен e/(e - 1)u, где u – «пороговое время разделения» случайного блуждания по G.

Теорема 3. Благодаря тому, что «голова» подмножества поддержки перемещается по регулярному остовному подграфу G, существует абсолютная постоянная у > 0, такая, что ожидаемое время встречи A (или B) и узла поддержки ограничено сверху yn2/k. Таким образом, протокол гарантирует общее ожидаемое время передачи @(p), не зависящее от общего числа мобильных узлов и их перемещения.

Анализ предполагает, что «голова» S0 перемещается по траектории непрерывного по времени случайного блуждания с общей скоростью 1 (скорость выхода из узла G). Если S0 движется в \j/ раз быстрее, чем остальные узлы, то все оцениваемые времена, за исключением времени передачи между узлами поддержки, будут делиться на. Таким образом, ожидаемое общее время передачи может быть уменьшено до &(yplp), где у – абсолютная постоянная. В случаях, когда S0 может использовать преимущества топологии сети, то все оцениваемые времена, за исключением времени передачи между узлами поддержки, улучшаются:

 

Теорема 4. Когда «голова» подмножества поддержки движется по регулярному остовному подграфу G, ожидаемое время встречи A (или B) и узла поддержки не может быть меньше (n - 1)2 /2m. Поскольку m = 0(n), нижняя граница ожидаемого времени передачи равна &(n). В этом смысле ожидаемое время передачи посредством протокола «Змея» является оптимальным для размера подмножества поддержки, составляющего &(n).

Анализ временной эффективности протокола «в среднем случае» предполагает, что движение мобильных узлов, не входящих в подмножество поддержки, является случайным блужданием по графу движения G. Случайное блуждание каждого мобильного узла осуществляется независимо от других узлов.

Теорема 5. Ожидаемое время передачи между узлами поддержки с протоколом координации движения типа «змея» ограничено сверху формулой

Верхняя граница минимизируется при k = sj2nl\i(G), где A 2 – второе собственное значение матрицы смежности графа движения.

Способ перемещения и коммуникаций узлов поддержки является надежным в том смысле, что он сохраняет работоспособность при отказе узлов поддержки. Рассматриваемые типы отказов узлов являются устойчивыми, т. е. ошибками аварийной остановки. Как только происходит такой сбой, узел поддержки, на котором произошел сбой, больше не является участником децентрализованной мобильной сети. Коммуникационный протокол является p-отказоустойчивым, если он по-прежнему позволяет участникам сети корректно взаимодействовать при наличии не более /} устойчивых отказов узлов поддержки. (/*>!)-[ ] показывает, что:

Теорема 6. Протокол координации движения типа «змея» является 1-отказоустойчивым.

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

Наиболее распространенным способом установления связи является формирование маршрутов промежуточных узлов, которые находятся в пределах дальности передачи данных друг друга и могут напрямую взаимодействовать друг с другом. Мобильные узлы выступают одновременно в качестве хостов и маршрутизаторов, обеспечивая пересылку пакетов по этим путям. Такой подход к поддержанию глобальной структуры для временной сети является сложной задачей. Поскольку узлы перемещаются, лежащий в основе сети граф коммуникаций меняется, и узлы должны быстро адаптироваться к таким изменениям и восстанавливать свои маршруты. Буш и Тиртапура [ ] впервые проанализировали производительность некоторых характерных протоколов [8, 13] и показали, что в некоторых случаях им требуется Q(u2) времени, где u – число узлов, чтобы стабилизироваться, то есть быть в состоянии обеспечить связь.

Работа Хацигианнакиса, Николетсиса и Спиракиса [5] посвящена сетям, топологическая связность которых подвержена частым непредсказуемым изменениям, и изучает проблему эффективной доставки данных в разреженных сетях, в которых разделение может сохраняться на протяжении долгого времени. В таких случаях для осуществления поддержки можно иметь небольшую команду быстро передвигающихся и универсальных транспортных средств. Такими транспортными средствами могут быть автомобили, мотоциклы, вертолеты или группа независимо управляемых мобильных модулей, то есть роботов. Этот специфический подход вдохновлен работой Уолтер, Уэлч и Амато [ ], которые изучали проблему координации движения в распределенных системах, состоящих из роботов, способных могут соединяться, разъединяться и перемещаться.

Использование мобильности для повышения производительности в децентрализованных мобильных сетях рассматривалось в различных контекстах в [6, 9, 11, 15]. Основной задачей было обеспечение прерывистой связи в отключенной децентрализованной сети. Каждое подобное решение обеспечивает определенные свойства сквозной связи, такие как задержка и потеря сообщений между узлами сети. Некоторые из них требуют беспроводной передачи данных на большие расстояния, другим необходимо, чтобы все узлы активно перемещались согласно протоколу и сотрудничали таким образом, чтобы чаще встречаться друг с другом. Ключевая идея – сделать ответственными за коммуникацию только подмножество узлов используется аналогичным образом в работах [10, 15]. Однако в [15] основное внимание уделяется случаям, когда для этой цели доступен только один узел. В последующем применение мобильности в области беспроводных сенсорных сетей рассматривалось в [3, 10, 12].

Некоторые задачи, имеющие отношение к работе Хацигианнакиса, Николетсиса и Спиракиса [ ], остаются нерешенными. Очевидно, что размер подмножества поддержки k, форма и способ перемещения узлов поддержки влияют на производительность сквозной связи. Открытым вопросом является исследование альтернативных структур подмножества поддержки, различных стратегий координации движения и сравнительное изучение влияния соответствующих эффектов на скорость коммуникаций. С этой целью в работе [4] идея поддержки была расширена на иерархические и сильно меняющиеся графы движения. Идея кооперативной маршрутизации на основе существования узлов поддержки также способна повысить уровень безопасности и доверия.

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

В [5] была проведена экспериментальная оценка с помощью симуляции для моделирования различных возможных ситуаций, связанных с географической областью, покрываемой децентрализованной мобильной сетью. Был проведен ряд экспериментов для графов-решеток (двух- и трехмерных), случайных графов (модель Gn,p), двудольных многоступенчатых графов и двухъярусных графов движения (двух- и трехмерных).

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