Коммуникация в децентрализованных мобильных сетях с использованием метода случайного блуждания
Ключевые слова и синонимы
Отключенные децентрализованные сети; устойчивые к задержке сети; переправка сообщений; ретрансляция сообщений; физическая перевозка носителей данных; мобильный накопитель данных
Постановка задачи
Под децентрализованной мобильной сетью понимается временная динамическая сеть межсоединений беспроводных мобильных узлов, не имеющая какой-либо организованной инфраструктуры или централизованного управления. Основная задача коммуникации в децентрализованных мобильных сетях заключается в передаче информации от узла-отправителя A другому назначенному узлу-получателю B. Если мобильные узлы A и B находятся в пределах дистанции беспроводной связи друг с другом, то они могут взаимодействовать друг с другом. Если же это не так, то они могут взаимодействовать, если другие узлы сети готовы пересылать их пакеты. Одним из способов решения этой задачи является протокол уведомления всех узлов, которые встречаются отправителю A, и предоставления им всей информации в надежде, что некоторые из них в конечном итоге встретят получателя B.
Существует ли более эффективный метод (кроме уведомления каждого узла, который встречает отправитель, в надежде, что некоторым из них в конечном итоге встретится получатель), который успешно решает задачу установления связи без переполнения сети и без истощения аккумуляторов и вычислительной мощности узлов?
Задача связи между мобильными узлами является одной из самых фундаментальных задач в децентрализованных мобильных сетях и лежит в основе многих алгоритмов, таких как подсчет количества узлов, выборы лидера, обработка данных и т. д. Получить представление о нескольких важных проблемах в децентрализованных мобильных сетях можно в [13]. Работа Хацигианнакиса, Николетсиса и Спиракиса [5] посвящена беспроводным мобильным сетям, которые подвержены высокодинамичным структурным изменениям, вызванным мобильностью, флуктуациями каналов и отказами устройств. Эти изменения влияют на топологическую связность, происходят с высокой частотой и не могут быть предсказаны заранее. Поэтому среда, в которой перемещаются узлы (в трехмерном пространстве с возможными препятствиями), а также движение, выполняемое узлами, являются входными данными для любого распределенного алгоритма.
Пространство движений
Пространство возможных движений мобильных узлов комбинаторно обобщается графом движений, т. е. подробные геометрические характеристики движения игнорируются. Предполагается, что каждый мобильный узел имеет диапазон передачи, представленный сферой tr с центром в самом этом узле. Любой другой узел внутри сферы tr может получить любое сообщение, переданное данным узлом. Эта сфера аппроксимируется кубом tc с объемом [math]\displaystyle{ \mathcal{V}(tc) }[/math], где [math]\displaystyle{ \mathcal{V}(tc) \lt \mathcal{V}(tr) }[/math]. Размер tc может быть выбран таким образом, чтобы его объем [math]\displaystyle{ \mathcal{V}(tc) }[/math] был максимальным, при условии сохранения соотношения [math]\displaystyle{ \mathcal{V}(tc) \lt \mathcal{V}(tc) }[/math]; и если мобильный узел внутри tc передает сообщение, то это сообщение получает любой другой узел в tc. Учитывая, что мобильные узлы движутся в пространстве S, это пространство можно разделить на последовательные кубы объема [math]\displaystyle{ \mathcal{V}(tc) }[/math].
Определение 1. Граф движения G(V, E), (|V| = n, |E| = m), который соответствует квантованию S, строится следующим образом: вершина [math]\displaystyle{ u \in G }[/math] представляет куб объемом [math]\displaystyle{ \mathcal{V}(tc) }[/math], а ребро [math]\displaystyle{ (u, v) \in G }[/math] существует, если соответствующие кубы являются смежными.
Количество вершин n фактически аппроксимирует соотношение между объемом [math]\displaystyle{ \mathcal{V}(S) }[/math] пространства S и пространством, занимаемым диапазоном передачи мобильного узла [math]\displaystyle{ \mathcal{V}(tr) }[/math]. В предельном случае, когда [math]\displaystyle{ \mathcal{V}(S) \approx \mathcal{V}(tr) }[/math], диапазон передачи узлов аппроксимирует пространство, в котором они движутся, и n = 1. Учитывая диапазон передачи tr, n линейно зависит от объема пространства S независимо от выбора tc, и [math]\displaystyle{ n = O(\mathcal{V}(S) / \mathcal{V}(tr)) }[/math]. Соотношение [math]\displaystyle{ \mathcal{V}(S) / \mathcal{V}(tr) }[/math] является относительным размером пространства движений и обозначается [math]\displaystyle{ \rho }[/math]. Поскольку ребра G представляют собой соседние многогранники, каждая вершина графа связана с постоянным числом соседей, из чего следует, что [math]\displaystyle{ m = \Theta(n) }[/math]. В данном примере, где tc является кубом, G имеет максимальную степень 6, и [math]\displaystyle{ m \le 6n }[/math]. Таким образом, граф движения G (обычно) является графом ограниченной степени, поскольку он получен из обычного графа невысокой степени путем удаления его частей, соответствующих препятствиям для движения или связи. Обозначим за [math]\displaystyle{ \Delta }[/math] максимальную степень вершины графа G.
Рисунок 1. Исходная область сети S (a), ее разбиение на последовательные кубы объема [math]\displaystyle{ \mathcal{V}(tc) }[/math] (b) и полученный граф движения G (c)
Движение узлов-соперников
В общем случае движение узлов зависит от рассеянного соперника, который определяет шаблоны движения любым возможным способом, но независимо от распределенного алгоритма. Иными словами, исключается случай, когда некоторые узлы сознательно пытаются злонамеренно повлиять на протокол – например, избежать определенных узлов. Это прагматическое предположение, которого обычно придерживаются приложения, реализующие данный подход. Такие соперники в процессе движения называются соперниками с ограниченным движением.
В целях изучения эффективности распределенных алгоритмов для децентрализованных сетей в среднем случае движения узлов моделируются одновременными и независимыми случайными блужданиями. Предположение о том, что мобильные узлы движутся случайным образом – либо в соответствии с равномерно распределенными изменениями их направлений и скоростей, либо в соответствии с моделью мобильности случайных промежуточных точек, выбирая случайные пункты назначения – широко использовалось в других исследованиях.
Основные результаты
Основная идея заключается в том, чтобы воспользоваться преимуществами естественного движения мобильных узлов путем обмена информацией при каждой случайной встрече этих узлов. Однако представляется очевидным, что если узлы расположены в удаленных областях и не выходят за их пределы, то информация никак не сможет до них дойти, если только протокол специально не позаботится о таких ситуациях. Хацигианнакис, Николетсис и Спиракис [5] предложили следующую идею – заставить только небольшое подмножество развернутых узлов перемещаться в соответствии с требованиями протокола; они называют это подмножество узлами поддержки сети. При наличии таких узлов ими можно воспользоваться для реализации простой, корректной и эффективной стратегии связи между любой парой узлов сети, которая позволяет избежать переполнения ее сообщениями.
Пусть имеется заранее определенный набор из k узлов, которые становятся узлами поддержки. Эти узлы перемещаются случайным образом и достаточно быстро, так что за достаточно короткое время они посещают весь граф движения. Когда какой-либо узел поддержки находится в пределах диапазона передачи отправителя, он уведомляет отправителя о том, что тот может отправить свое сообщение или несколько сообщений. После этого сообщения хранятся «где-то в структуре поддержки». Когда получатель оказывается в пределах диапазона передачи узла поддержки, он получает уведомление о том, что его «ожидает» сообщение, и данное сообщение пересылается получателю.
Протокол 1 (протокол координации движения узлов поддержки типа «Змея»). Пусть [math]\displaystyle{ S_0, S_1, ..., S_{k-1} }[/math] – члены команды поддержки, а за [math]\displaystyle{ S_0 }[/math] обозначается узел-лидер (возможно, избранный). Протокол заставляет узел [math]\displaystyle{ S_0 }[/math] совершить случайное перемещение по графу движения, а каждый из остальных узлов [math]\displaystyle{ S_i }[/math] должен выполнить простой приказ «переместиться туда, где раньше находился [math]\displaystyle{ S_{i - 1} }[/math]». Когда [math]\displaystyle{ S_0 }[/math] готов двигаться, он посылает [math]\displaystyle{ S_1 }[/math] сообщение, в котором указывается новое направление движения. [math]\displaystyle{ S_1 }[/math] изменит направление движения в соответствии с инструкциями [math]\displaystyle{ S_0 }[/math] и передаст сообщение [math]\displaystyle{ S_2 }[/math]. Аналогичным образом, [math]\displaystyle{ S_i }[/math] будет следовать приказам [math]\displaystyle{ S_{i-1} }[/math] после передачи новых инструкций [math]\displaystyle{ S_{i+1} }[/math]. Приказы на движение, полученные [math]\displaystyle{ S_i }[/math], помещаются в очередь [math]\displaystyle{ Q_i }[/math] для последовательной обработки. Самый первый ход [math]\displaystyle{ S_i, \forall i \in \{ 1, 2, ..., k - 1 \} }[/math], задерживается на период времени [math]\displaystyle{ \delta }[/math].
Цель случайного блуждания «головы змеи» [math]\displaystyle{ S_0 }[/math] заключается в том, чтобы обеспечить покрытие в течение некоторого конечного времени всего графа G без знания и запоминания деталей топологии, кроме локальных. Такое движение без запоминания также обеспечивает справедливость, низкий уровень издержек и устойчивость к структурным изменениям.
Рассмотрим случай, когда любому отправителю или получателю разрешена неизвестная стратегия движения общего вида, но его стратегия предоставляется соперником с ограниченным движением. Это означает, что каждый узел, не являющийся узлом поддержки, либо (а) выполняет детерминированное движение, которое или останавливается в вершине, или входит в бесконечный цикл после некоторой начальной части, либо (б) реализует стохастическую стратегию, которая, однако, не зависит от движения узлов поддержки. Авторы в [5] приводят следующие доказательства корректности и эффективности. Для получения полноценного представления о цепях Маркова и случайных блужданиях читателю предлагается ознакомиться с превосходной книгой Олдоса и Филла [1].
Теорема 1. Узлы поддержки и протокол координации движения типа «змея» гарантируют надежную коммуникацию между любой парой «отправитель-получатель» (A, B) за конечное время, ожидаемое значение которого ограничено только функцией от относительного размера пространства движений [math]\displaystyle{ \rho }[/math] и не зависит от числа узлов, а также не зависит от того, как движутся [math]\displaystyle{ MH_S }[/math] и [math]\displaystyle{ MH_R }[/math], при условии, что мобильные узлы, не входящие в подмножество поддержки, не пытаются намеренно избежать встречи с узлами поддержки.
Теорема 2. Ожидаемое время передачи информации между узлами поддержки и протоколом координации движения типа «змея» ограничено сверху [math]\displaystyle{ \Theta ( \sqrt{mc}) }[/math], когда (оптимальный) размер подмножества поддержки равен [math]\displaystyle{ k = \sqrt{2mc} }[/math], а c = e/(e - 1)u, где u – «пороговое время разделения» случайного блуждания по G.
Теорема 3. Благодаря тому, что «голова» подмножества поддержки перемещается по регулярному остовному подграфу G, существует абсолютная постоянная [math]\displaystyle{ \gamma \gt 0 }[/math], такая, что ожидаемое время встречи узла A (или B) и узла поддержки ограничено сверху значением [math]\displaystyle{ \gamma n^2/k }[/math]. Таким образом, протокол гарантирует общее ожидаемое время передачи [math]\displaystyle{ \Theta( \rho) }[/math], не зависящее от общего числа мобильных узлов и их перемещения.
Анализ предполагает, что «голова» [math]\displaystyle{ S_0 }[/math] перемещается по траектории непрерывного по времени случайного блуждания с общей скоростью 1 (скорость выхода из узла G). Если [math]\displaystyle{ S_0 }[/math] движется в [math]\displaystyle{ \psi }[/math] раз быстрее, чем остальные узлы, то все оцениваемые времена, за исключением времени передачи между узлами поддержки, будут делиться на [math]\displaystyle{ \psi }[/math]. Таким образом, ожидаемое общее время передачи может быть уменьшено до [math]\displaystyle{ \Theta(\gamma \rho \sqrt{\psi}) }[/math], где [math]\displaystyle{ \gamma }[/math] – абсолютная постоянная. В случаях, когда [math]\displaystyle{ S_0 }[/math] может использовать преимущества топологии сети, все оцениваемые времена, за исключением времени передачи между узлами поддержки, улучшаются:
Теорема 4. Когда «голова» подмножества поддержки движется по регулярному остовному подграфу G, ожидаемое время встречи A (или B) и узла поддержки не может быть меньше [math]\displaystyle{ (n - 1)^2 / 2m }[/math]. Поскольку [math]\displaystyle{ m = \Theta(n) }[/math], нижняя граница ожидаемого времени передачи равна [math]\displaystyle{ \Theta(n) }[/math]. В этом смысле ожидаемое время передачи посредством протокола «змея» является оптимальным для размера подмножества поддержки, составляющего [math]\displaystyle{ \Theta(n) }[/math].
Анализ временной эффективности протокола «в среднем случае» предполагает, что движение мобильных узлов, не входящих в подмножество поддержки, является случайным блужданием по графу движения G. Случайное блуждание каждого мобильного узла осуществляется независимо от других узлов.
Теорема 5. Ожидаемое время передачи между узлами поддержки с протоколом координации движения типа «змея» ограничено сверху формулой
[math]\displaystyle{ E(T) \le \frac{2}{\lambda_2 (G)} \Theta \bigg( \frac{n}{k} \bigg) + \Theta(k). }[/math]
Верхняя граница минимизируется при [math]\displaystyle{ k = \sqrt{2n / \lambda_2 (G)} }[/math], где [math]\displaystyle{ \lambda_2 }[/math] – второе собственное значение матрицы смежности графа движения.
Способ перемещения и коммуникаций узлов поддержки является надежным в том смысле, что он сохраняет работоспособность при отказе узлов поддержки. Рассматриваемые типы отказов узлов являются устойчивыми, т. е. ошибками аварийной остановки. Как только происходит такой отказ, узел поддержки, на котором он произошел, больше не является участником децентрализованной мобильной сети. Коммуникационный протокол является [math]\displaystyle{ \beta }[/math]-отказоустойчивым, если он по-прежнему позволяет участникам сети корректно взаимодействовать при наличии не более [math]\displaystyle{ \beta }[/math] устойчивых отказов узлов поддержки [math]\displaystyle{ (\beta \ge 1) }[/math]. В работе [5] показано, что:
Теорема 6. Протокол координации движения типа «змея» является 1-отказоустойчивым.
Применение
Децентрализованные мобильные сети – это быстро развертываемые и самоконфигурирующиеся сети, которые находят широкое применение во многих критически важных областях, таких как помощь при стихийных бедствиях, «окружающий интеллект», считывание и наблюдение на большой территории. Возможность создания сети в любом месте и в любое время позволяет проводить телеконференции, создавать домашние сети, сети датчиков, персональные сети и встроенные вычислительные приложения [13].
Родственные работы
Наиболее распространенным способом установления связи является формирование маршрутов промежуточных узлов, которые находятся в пределах дальности передачи данных друг друга и могут напрямую взаимодействовать друг с другом. Мобильные узлы выступают одновременно в качестве хостов и маршрутизаторов, обеспечивая пересылку пакетов по этим путям. Такой подход к поддержанию глобальной структуры для временной сети является сложной задачей. Поскольку узлы перемещаются, лежащий в основе сети граф коммуникаций меняется, и узлы должны быстро адаптироваться к таким изменениям и восстанавливать свои маршруты. Буш и Тиртапура [2] впервые проанализировали производительность некоторых характерных протоколов [8, 13] и показали, что в некоторых случаях им требуется [math]\displaystyle{ \Omega(u^2) }[/math] времени, где u – число узлов, чтобы стабилизироваться, то есть быть в состоянии обеспечить связь.
Работа Хацигианнакиса, Николетсиса и Спиракиса [5] посвящена сетям, топологическая связность которых подвержена частым непредсказуемым изменениям, и изучает проблему эффективной доставки данных в разреженных сетях, в которых разделение может сохраняться на протяжении долгого времени. В таких случаях для осуществления поддержки можно иметь небольшую команду быстро передвигающихся и универсальных транспортных средств. Такими транспортными средствами могут быть автомобили, мотоциклы, вертолеты или группа независимо управляемых мобильных модулей, то есть роботов. Этот специфический подход вдохновлен работой Уолтер, Уэлч и Амато [14], которые изучали проблему координации движения в распределенных системах, состоящих из роботов, способных соединяться, разъединяться и перемещаться.
Использование мобильности для повышения производительности в децентрализованных мобильных сетях рассматривалось в различных контекстах в [6, 9, 11, 15]. Основной задачей было обеспечение прерывистой связи в отключенной децентрализованной сети. Каждое подобное решение стремится сгладить определенные недостатки сквозной связи, такие как задержка и потеря сообщений между узлами сети. Некоторые из них требуют беспроводной передачи данных на большие расстояния, другим необходимо, чтобы все узлы активно перемещались согласно протоколу и сотрудничали таким образом, чтобы чаще встречаться друг с другом. Ключевая идея – сделать ответственными за коммуникацию только подмножество узлов – используется аналогичным образом в работах [10, 15]. Однако в [15] основное внимание уделяется случаям, когда для этой цели доступен только один узел. В последующем применение мобильности в области беспроводных сенсорных сетей рассматривалось в [3, 10, 12].
Открытые вопросы
Некоторые задачи, имеющие отношение к работе Хацигианнакиса, Николетсиса и Спиракиса [5], остаются нерешенными. Очевидно, что размер подмножества поддержки k, форма и способ перемещения узлов поддержки влияют на производительность сквозной связи. Открытым вопросом является исследование альтернативных структур подмножества поддержки, различных стратегий координации движения и сравнительное изучение влияния соответствующих эффектов на скорость коммуникаций. С этой целью в работе [4] идея поддержки была расширена на иерархические и сильно меняющиеся графы движения. Идея кооперативной маршрутизации на основе концепции узлов поддержки также способна повысить уровень безопасности и доверия.
Важным вопросом для случая, когда сеть разрежена или скорость движения слишком высока, является изучение производительности протоколов построения и обслуживания путей. В этом направлении была проделана определенная работа в [2], которая также может быть использована для исследования сквозной связи в беспроводных сенсорных сетях. До сих пор неизвестно, существуют ли доказательства невозможности для распределенных алгоритмов, которые пытаются поддерживать структурную информацию получившейся хрупкой сети виртуальных связей.
Еще одной открытой областью исследований является анализ свойств сквозной связи при определенных стратегиях движения узлов поддержки. Существуют случаи, когда взаимодействие мобильных узлов может вести себя согласно парадигме взаимодействующих частиц и их моделированию в физике. Исследования времени взаимодействия и времени распространения информации в различных графах представлены в работе [7] и по-прежнему важны для дальнейших исследований в этом направлении.
Экспериментальные результаты
В [5] была проведена экспериментальная оценка с помощью симуляции для моделирования различных возможных ситуаций, связанных с географической областью, покрываемой децентрализованной мобильной сетью. Был проведен ряд экспериментов для графов-решеток (двух- и трехмерных), случайных графов (модель [math]\displaystyle{ G_{n, p}) }[/math], двудольных многоступенчатых графов и двухъярусных графов движения.
Все результаты подтверждают выводы теоретического анализа и дают полезное представление о том, как далее использовать идею узлов поддержки. В [4] исследуется модель иерархических и сильно меняющихся децентрализованных сетей. Эксперименты показывают, что даже в сетях такого типа закономерность работы алгоритма типа «змея» остается неизменной.
Ссылка на код
См. также
Литература
1. Aldous, D., Fill, J.: Reversible markov chains and random walks on graphs. http://stat-www.berkeley.edu/users/aldous/book.html (1999). Accessed 1999
2. Busch, C., Tirthapura, S.: Analysis of link reversal routing algorithms. SIAM J. Comput. 35(2):305-326 (2005)
3. Chatzigiannakis, I., Kinalis, A., Nikoletseas, S.: Sink mobility protocols for data collection in wireless sensor networks. In: Zomaya, A.Y., Bononi, L (eds.) 4th International Mobility and Wireless Access Workshop (MOBIWAC 2006), Terromolinos, pp 52-59
4. Chatzigiannakis, I., Nikoletseas, S.: Design and analysis of an efficient communication strategy for hierarchical and highly changing ad-hoc mobile networks. J. Mobile Netw. Appl. 9(4), 319-332 (2004). Special Issue on Parallel Processing Issues in Mobile Computing
5. Chatzigiannakis, I., Nikoletseas, S., Spirakis, P.: Distributed communication algorithms for ad hoc mobile networks. J. Parallel Distrib. Comput. (JPDC) 63(1), 58-74 (2003). Special Issue on Wireless and Mobile Ad-hoc Networking and Computing, edited by Boukerche A
6. Diggavi, S.N., Grossglauser, M., Tse, D.N.C.: Even one-dimensional mobility increases the capacity of wireless networks. IEEE Trans. Inf. Theory 51(11), 3947-3954 (2005)
7. Dimitriou, T., Nikoletseas, S.E., Spirakis, P.G.: Analysis of the information propagation time among mobile hosts. In: Nikolaidis, I., Barbeau, M., Kranakis, E. (eds.) 3rd International Conference on Ad-Hoc, Mobile, and Wireless Networks (ADHOC-NOW 2004), pp 122-134. Lecture Notes in Computer Science(LNCS), vol. 3158. Springer, Berlin (2004)
8. Gafni, E., Bertsekas, D.P.: Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE Trans. Commun. 29(1), 11-18 (1981)
9. Grossglauser, M., Tse, D.N.C.: Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Trans. Netw. 10(4), 477-486 (2002)
10. Jain, S., Shah, R., Brunette, W., Borriello, G., Roy, S.: Exploiting mobility for energy efficient data collection in wireless sensor networks. J. Mobile Netw. Appl. 11 (3), 327-339 (2006)
11. Li, Q., Rus, D.: Communication in disconnected ad hoc networks using message relay. Journal of Parallel and Distributed Computing (JPDC) 63(1), 75-86 (2003). Special Issue on Wireless and Mobile Ad-hoc Networking and Computing, edited by A Boukerche
12. Luo, J., Panchard, J., Piorkowski, M., Grossglauser, M., Hubaux, J.P.: Mobiroute: Routing towards a mobile sink for improving lifetime in sensor networks. In: Gibbons, P.B., Abdelzaher, T., Aspnes, J., Rao, R. (eds.) 2nd IEEE/ACM International Conference on Distributed Computing in Sensor Systems (DCOSS 2005). Lecture Notes in Computer Science (LNCS), vol. 4026, pp 480^97. Springer, Berlin (2006)
13. Perkins, C.E.: Ad Hoc Networking. Addison-Wesley, Boston (2001)
14. Walter, J.E., Welch, J.L., Amato, N.M.: Distributed reconfiguration of metamorphic robot chains. J. Distrib. Comput. 17(2), 171-189(2004)
15. Zhao, W., Ammar, M., Zegura, E.: A message ferrying approach for data delivery in sparse mobile ad hoc networks. In: Murai, J., Perkins, C., Tassiulas, L (eds.) 5th ACM international symposium on Mobile ad hoc networking and computing (MobiHoc 2004), pp 187-198. ACM Press, Roppongi Hills, Tokyo (2004)