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

Далее будут рассматриваться точки на двумерной плоскости. Пусть <math>X_1, X_2, ... \;</math> – независимые и равномерно распределенные случайные точки в ограниченной области A. Пусть имеется целое положительное число n. Точечным процессом <math>\{ X_1, X_2, ..., X_n \} \;</math> называется равномерный n-точечный процесс над A, обозначаемый <math>\mathcal{X}_n (A) \;</math>. Пусть имеется положительное число <math>\lambda \;</math>. Обозначим за <math>P_0 (\lambda) \;</math> пуассонову случайную переменную с параметром A, независимую от <math>\{ X_1, X_2, ... \; \} </math>. Тогда точечный процесс <math>\{ X_1, X_2, ..., X_{P_o (n)} \} \; </math> представляет собой пуассоновский точечный процесс со средним значением n над A и обозначается <math>\mathcal{P}_n (A) \;</math>. A называется областью развертывания. Событие называется асимптотическим «почти наверное», если оно случается с вероятностью, стремящейся к 1 при <math>n \to \infty \;</math>.

Согласно этой теореме, вероятность события, заключающегося в том, что в графе нет изолированных вершин, асимптотически равна <math>exp \big( - e^{- \xi} \big) \;</math>. По утверждению теории случайных геометрических графов, в графе нет изолированных вершин, он почти наверное является связным. Из этого следует формулировка теоремы 2 [6, 8, 9].

\frac{\sqrt{ \pi} + \frac{1}{ \sqrt{ \pi}}} {2^{k - 1} \; k!}\; e^{- \frac{ \xi}{2}}, k \ge 1  

В графах Гэбриэла (Gabriel graphs, GG) между двумя вершинами существует ребро в том и только том случае, если не существует другой вершины в круге, диаметром которого является сегмент двух этих вершин. Пусть V – множество точек, а ''l'' – положительное вещественное число. Обозначим за <math>\rho_{GG} (V) \;</math> длину наибольшего ребра графа GG над множеством V, а за N (V, ''l'') – количество ребер GG над V, имеющих длину не менее l. Ван и И (2007) [ ] доказали следующую теорему.

<math>lim_{n \to \infty} Pr\bigg[ \rho_{GG} (\mathcal{P}_n (\Omega)) < 2 \sqrt{ \frac{ln \; n + \xi}{\pi n}} \bigg] = exp \big( -2 e^{- xi} \big)</math>.

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

В этом определении (u, v) – пара «источник – точка назначения», а w – вершина, находящаяся ближе к v, чем u. Если каждая вершина имеет радиус передачи не менее <math>\rho_{GFR} (V) \;</math>, алгоритм может гарантировать доставку в паре «источник – точка назначения» [12].

'''

2. Если <math>\beta < \beta_0 \;</math>, то <math>\rho_{GFR} (\mathcal{P}_n (\Omega)) > r_n \;</math> является асимптотическим «почти наверное».'''

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

Одной из сфер применения критических диапазонов является связность сетей. Сеть является k-вершинно-связной, если между любой парой вершин существует k вершинно-непересекающихся путей. Если сети присуще это свойство, то между любой парой вершин имеется по меньшей мере k различных путей коммуникации, и сеть остается связной даже в случае отказа k-1 вершин. Таким образом, благодаря более высокому уровню связности сеть может обладать повышенной пропускной способностью и более высокой отказоустойчивостью. В работах [9, 14] и [15] рассматривались сети с отказавшими узлами или линиями связи.

Еще одной областью применения является управление топологией. Для эффективного управления децентрализованными беспроводными сетями необходимо строить и поддерживать подмножества топологии сети. Соответствующий раздел называется управлением топологией. Остов представляет собой подмножество топологии сети, в котором минимальная полная стоимость пути между любыми двумя вершинами (отражающая, например, расстояние или энергопотребление) только в константное число раз больше минимальной полной стоимости в исходной топологии сети. Таким образом, остовы оказываются подходящими кандидатами на роль виртуальных магистралей. Такие геометрические структуры, как евклидовы минимальные остовные деревья, графы относительных окрестностей, графы Гэбриэла, триангуляции Делоне, графы Яо и другие, широко используются в качестве компонентов при построении остовов [1, 5, 13]. Применение знаний о критических диапазонах способно снизить сложность разработки алгоритмов [3, 11].