Коммуникация в децентрализованных мобильных сетях с использованием метода случайного блуждания: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 63: | Строка 63: | ||
Теорема 4. Когда «голова» подмножества поддержки движется по регулярному остовному подграфу G, ожидаемое время встречи A (или B) и узла поддержки не может быть меньше (n - 1)2 /2m. Поскольку m = | '''Теорема 4. Когда «голова» подмножества поддержки движется по регулярному остовному подграфу G, ожидаемое время встречи A (или B) и узла поддержки не может быть меньше <math>(n - 1)^2 / 2m</math>. Поскольку <math>m = \Theta(n)</math>, нижняя граница ожидаемого времени передачи равна <math>\Theta(n)</math>. В этом смысле ожидаемое время передачи посредством протокола «Змея» является оптимальным для размера подмножества поддержки, составляющего <math>\Theta(n)</math>.''' | ||
Анализ временной эффективности протокола «в среднем случае» предполагает, что движение мобильных узлов, не входящих в подмножество поддержки, является случайным блужданием по графу движения G. Случайное блуждание каждого мобильного узла осуществляется независимо от других узлов. | Анализ временной эффективности протокола «в среднем случае» предполагает, что движение мобильных узлов, не входящих в подмножество поддержки, является ''случайным блужданием по графу движения'' G. Случайное блуждание каждого мобильного узла осуществляется независимо от других узлов. | ||
Теорема 5. Ожидаемое время передачи между узлами поддержки с протоколом координации движения типа «змея» ограничено сверху формулой | '''Теорема 5. Ожидаемое время передачи между узлами поддержки с протоколом координации движения типа «змея» ограничено сверху формулой''' | ||
<math>E(T) \le \frac{2}{\lambda_2 (G)} \Theta \binom{n}{k} + \Theta(k).</math> | |||
Верхняя граница минимизируется при k = | '''Верхняя граница минимизируется при <math>k = \sqrt{2n / \lambda_2 (G)}</math>, где <math>\lambda_2</math> – второе собственное значение матрицы смежности графа движения.''' | ||
Способ перемещения и коммуникаций узлов поддержки является надежным в том смысле, что он сохраняет работоспособность при отказе узлов поддержки. Рассматриваемые типы отказов узлов являются устойчивыми, т. е. ошибками аварийной остановки. Как только происходит такой сбой, узел поддержки, на котором произошел сбой, больше не является участником децентрализованной мобильной сети. Коммуникационный протокол является | Способ перемещения и коммуникаций узлов поддержки является надежным в том смысле, что он сохраняет работоспособность при отказе узлов поддержки. Рассматриваемые типы отказов узлов являются устойчивыми, т. е. ошибками аварийной остановки. Как только происходит такой сбой, узел поддержки, на котором произошел сбой, больше не является участником децентрализованной мобильной сети. Коммуникационный протокол является ''<math>\beta</math>-отказоустойчивым'', если он по-прежнему позволяет участникам сети корректно взаимодействовать при наличии не более <math>\beta</math> устойчивых отказов узлов поддержки <math>(\beta \ge 1)</math>. В работе [5 ] показано, что: | ||
Теорема 6. Протокол координации движения типа «змея» является 1-отказоустойчивым. | '''Теорема 6. Протокол координации движения типа «змея» является 1-отказоустойчивым.''' | ||
== Применение == | == Применение == | ||