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

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

'''Теорема 2. Ожидаемое время передачи между узлами поддержки и протоколом координации движения типа «змея» ограничено сверху <math>\Theta ( \sqrt{mc})</math>, когда (оптимальный) размер подмножества поддержки равен <math>k = \sqrt{2mc}</math>, а c равен e/(e - 1)u, где u – «пороговое время разделения» случайного блуждания по G.'''

'''Теорема 3. Благодаря тому, что «голова» подмножества поддержки перемещается по регулярному остовному подграфу G, существует абсолютная постоянная <math>\gamma > 0</math>, такая, что ожидаемое время встречи A (или B) и узла поддержки ограничено сверху <math>\gamma n^2/k</math>. Таким образом, протокол гарантирует общее ожидаемое время передачи <math>\Theta( \rho)</math>, не зависящее от общего числа мобильных узлов и их перемещения.'''

Анализ предполагает, что «голова» <math>S_0</math> перемещается по траектории непрерывного по времени случайного блуждания с общей скоростью 1 (скорость выхода из узла G). Если <math>S_0</math> движется ''в <math>\psi</math> раз быстрее'', чем остальные узлы, то все оцениваемые времена, за исключением времени передачи между узлами поддержки, будут делиться на <math>\psi</math>. Таким образом, ожидаемое общее время передачи может быть уменьшено до <math>\Theta(\gamma \rho \sqrt{\psi})</math>, где <math>\gamma</math> – абсолютная постоянная. В случаях, когда <math>S_0</math> может использовать преимущества топологии сети, то все оцениваемые времена, за исключением времени передачи между узлами поддержки, улучшаются:

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

<math>E(T) \le \frac{2}{\lambda_2 (G)} \Theta \binom{n}{k} + \Theta(k).</math>

Способ перемещения и коммуникаций узлов поддержки является надежным в том смысле, что он сохраняет работоспособность при отказе узлов поддержки. Рассматриваемые типы отказов узлов являются устойчивыми, т. е. ошибками аварийной остановки. Как только происходит такой сбой, узел поддержки, на котором произошел сбой, больше не является участником децентрализованной мобильной сети. Коммуникационный протокол является ''<math>\beta</math>-отказоустойчивым'', если он по-прежнему позволяет участникам сети корректно взаимодействовать при наличии не более <math>\beta</math> устойчивых отказов узлов поддержки <math>(\beta \ge 1)</math>. В работе [5 ] показано, что:

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

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

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

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

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

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

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