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

'''Определение 1'''. Граф движения G(V, E), (|V| = n, |E| = m), который соответствует квантованию S, строится следующим образом: узел u 2 G представляет куб объемом V(tc), а ребро (u, v) 2 G существует, если соответствующие кубы являются смежными.

Количество узлов n фактически аппроксимирует соотношение между объемом V(S) пространства S и пространством, занимаемым диапазоном передачи мобильного узла V(tr). В предельном случае, когда V(S) & V(tr), диапазон передачи узлов аппроксимирует пространство, в котором они движутся, и n = 1. Учитывая диапазон передачи tr, n линейно зависит от объема пространства S независимо от выбора tc, и n = O(V(S)/V(tr)). Соотношение V(S)/V(tr) является относительным размером пространства движения и обозначается p. Поскольку ребра G представляют собой соседние многогранники, каждый узел связан с постоянным числом соседей, из чего следует, что m = 0(n). В данном примере, где tc является кубом, G имеет максимальную степень 6, и m < 6n. Таким образом, граф движения G (обычно) является графом ограниченной степени, поскольку он получен из обычного графа невысокой степени путем удаления его частей, соответствующих препятствиям для движения или связи. Обозначим за A максимальную степень вершины графа G.

Рисунок 1. Исходная область сети S (a), ее разбиение на последовательные кубы объема V(tc) (b) и полученный граф движения G (c)

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

В целях изучения эффективности распределенных алгоритмов для децентрализованных сетей в среднем случае движения узлов моделируются одновременными и независимыми случайными блужданиями. Предположение о том, что мобильные узлы движутся случайным образом, либо в соответствии с равномерно распределенными изменениями их направлений и скоростей, либо в соответствии с моделью мобильности случайных промежуточных точек, выбирая случайные пункты назначения, широко использовалось в других исследованиях.