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

Количество узлов 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.

Анализ предполагает, что «голова» S0 перемещается по траектории непрерывного по времени случайного блуждания с общей скоростью 1 (скорость выхода из узла G). Если S0 движется в \j/ раз быстрее, чем остальные узлы, то все оцениваемые времена, за исключением времени передачи между узлами поддержки, будут делиться на. Таким образом, ожидаемое общее время передачи может быть уменьшено до &(yplp), где у – абсолютная постоянная. В случаях, когда S0 может использовать преимущества топологии сети, то все оцениваемые времена, за исключением времени передачи между узлами поддержки, улучшаются:

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