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

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

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

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

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

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

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

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

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