4431
правка
Критический диапазон для беспроводных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
м
Критический диапазон для беспроводных сетей (посмотреть исходный код)
Версия от 11:34, 6 августа 2017
, 6 августа 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 94: | Строка 94: | ||
В беспроводных сетях с жадной прямой маршрутизацией каждая вершина отбрасывает полученный пакет в случае, если ни один из ее соседей не расположен ближе к точке назначения пакета, чем она сама, либо перенаправляет его ближайшему к точке назначения соседу. Поскольку каждой вершине требуется помнить только расположение соседей, доступных в результате одного перехода, а каждый пакет должен содержать расположение вершины – места назначения, алгоритм жадной прямой маршрутизации может быть реализован как локальный и не требующий памяти. В силу существования локального минимума, когда ни один из соседей вершины не оказывается более близким к точке назначения, чем текущая вершина, пакет может быть отброшен до того, как достигнет точки назначения. Чтобы гарантировать, что каждый пакет достигнет нужной точки, все вершины должны обладать достаточно большим диапазоном передачи во избежание попадания в ситуацию локального минимума. Применяя модель r-кругов, мы предполагаем, что все вершины имеют один и тот же радиус передачи r, а каждая пара вершин, находящихся на расстоянии не более r, связана друг с другом. Для множества точек V критический радиус передачи для алгоритма жадной прямой маршрутизации задается формулой | В беспроводных сетях с жадной прямой маршрутизацией каждая вершина отбрасывает полученный пакет в случае, если ни один из ее соседей не расположен ближе к точке назначения пакета, чем она сама, либо перенаправляет его ближайшему к точке назначения соседу. Поскольку каждой вершине требуется помнить только расположение соседей, доступных в результате одного перехода, а каждый пакет должен содержать расположение вершины – места назначения, алгоритм жадной прямой маршрутизации может быть реализован как локальный и не требующий памяти. В силу существования локального минимума, когда ни один из соседей вершины не оказывается более близким к точке назначения, чем текущая вершина, пакет может быть отброшен до того, как достигнет точки назначения. Чтобы гарантировать, что каждый пакет достигнет нужной точки, все вершины должны обладать достаточно большим диапазоном передачи во избежание попадания в ситуацию локального минимума. Применяя модель r-кругов, мы предполагаем, что все вершины имеют один и тот же радиус передачи r, а каждая пара вершин, находящихся на расстоянии не более r, связана друг с другом. Для множества точек V критический радиус передачи для алгоритма жадной прямой маршрутизации задается формулой | ||
<math>\rho_{GFR} (V) = max_{(u, v) \in V^2, u \neq v} \bigg( min_{||w - v|| < ||u - v||} ||w - u|| \bigg)</math> | <math>\rho_{GFR} (V) = max_{(u, v) \in V^2, u \neq v} \bigg( min_{||w - v|| < ||u - v||} ||w - u|| \bigg)</math>. | ||
В этом определении (u, v) – пара «источник – точка назначения», а w – вершина, находящаяся ближе к v, чем u. Если каждая вершина имеет радиус передачи не менее <math>\rho_{GFR} (V) \;</math>, алгоритм может гарантировать доставку в паре «источник – точка назначения» [12]. | В этом определении (u, v) – пара «источник – точка назначения», а w – вершина, находящаяся ближе к v, чем u. Если каждая вершина имеет радиус передачи не менее <math>\rho_{GFR} (V) \;</math>, алгоритм GFR может гарантировать доставку в паре «источник – точка назначения» [12]. | ||
| Строка 103: | Строка 103: | ||
'''1. Если <math>\beta > \beta_0 \;</math>, то <math>\rho_{GFR} (\mathcal{P}_n (\Omega)) \le r_n \;</math> является асимптотическим «почти наверное».''' | '''1. Если <math>\beta > \beta_0 \;</math>, то <math>\rho_{GFR} (\mathcal{P}_n (\Omega)) \le r_n \;</math> является асимптотическим «почти наверное».''' | ||
''' | |||
2. Если <math>\beta < \beta_0 \;</math>, то <math>\rho_{GFR} (\mathcal{P}_n (\Omega)) > r_n \;</math> является асимптотическим «почти наверное».''' | '''2. Если <math>\beta < \beta_0 \;</math>, то <math>\rho_{GFR} (\mathcal{P}_n (\Omega)) > r_n \;</math> является асимптотическим «почти наверное».''' | ||
== Применение == | == Применение == | ||