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

'''Теорема 1. Узлы поддержки и протокол координации движения типа «змея» гарантируют надежную коммуникацию между любой парой отправитель-получатель (A, B) за конечное время, ожидаемое значение которого ограничено только функцией относительного размера пространства движений p и не зависит от числа узлов, а также не зависит от того, как движутся <math>MH_S</math> и <math>MH_R</math>, при условии, что мобильные узлы, не входящие в подмножество поддержки, не пытаются намеренно избежать встречи с узлами поддержки.'''

'''Теорема 2. Ожидаемое время передачи между узлами поддержки и протоколом координации движения типа «змея» ограничено сверху <math>\Theta ( \sqrt{mc})</math>, когда (оптимальный) размер подмножества поддержки равен <math>k = \sqrt{2mc}</math>, а c равен e/(e - 1)u, где u – «пороговое время разделения» случайного блуждания по G.'''

'''Теорема 3. Благодаря тому, что «голова» подмножества поддержки перемещается по регулярному остовному подграфу G, существует абсолютная постоянная <math>\gamma > 0</math>, такая, что ожидаемое время встречи A (или B) и узла поддержки ограничено сверху <math>\gamma n^2/k</math>. Таким образом, протокол гарантирует общее ожидаемое время передачи <math>\Theta( \rho)</math>, не зависящее от общего числа мобильных узлов и их перемещения.'''

Анализ предполагает, что «голова» <math>S_0</math> перемещается по траектории непрерывного по времени случайного блуждания с общей скоростью 1 (скорость выхода из узла G). Если <math>S_0</math> движется ''в <math>\psi</math> раз быстрее'', чем остальные узлы, то все оцениваемые времена, за исключением времени передачи между узлами поддержки, будут делиться на <math>\psi</math>. Таким образом, ожидаемое общее время передачи может быть уменьшено до <math>\Theta(\gamma \rho \sqrt{\psi})</math>, где <math>\gamma</math> – абсолютная постоянная. В случаях, когда <math>S_0</math> может использовать преимущества топологии сети, то все оцениваемые времена, за исключением времени передачи между узлами поддержки, улучшаются: