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

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

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

'''Протокол 1 (протокол координации движения узлов поддержки типа «Змея»)'''. Пусть <math>S_0, S_1, ..., S_{k-1}</math> – члены команды поддержки, а за <math>S_0</math> обозначается узел-лидер (возможно, избранный). Протокол заставляет узел <math>S_0</math> совершить случайное перемещение по графу движения, а каждый из остальных узлов <math>S_i</math> должен выполнить простой приказ «переместиться туда, где раньше находился <math>S_{i - 1}</math>». Когда <math>S_0</math> готов двигаться, он посылает <math>S_1</math> сообщение, в котором указывается новое направление движения. <math>S_1</math> изменит направление движения в соответствии с инструкциями <math>S_0</math> и передаст сообщение <math>S_2</math>. Аналогичным образом, <math>S_i</math> будет следовать приказам <math>S_{i-1}</math> после передачи новых инструкций <math>S_{i+1}</math>. Приказы на движение, полученные <math>S_i</math>, помещаются в очередь <math>Q_i</math> для последовательной обработки. Самый первый ход <math>S_i, \forall i \in \{ 1, 2, ..., k - 1 \}</math> задерживается на период времени <math>\delta</math>.

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