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

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

Протокол 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.