4430
правок
Критический диапазон для беспроводных сетей: различия между версиями
Материал из WEGA
Критический диапазон для беспроводных сетей (посмотреть исходный код)
Версия от 12:42, 6 августа 2017
, 6 августа 2017→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| (не показана 31 промежуточная версия этого же участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть дано множество V. Граф с множеством вершин V, в котором между двумя вершинами имеется ребро в том и только том случае, если расстояние между ними не превышает некоторого положительного вещественного числа r, называется графом r-кругов над множеством вершин V и обозначается <math>G_r (V) \;</math>. Если <math>r1 \le r2 \;</math>, то, очевидно, <math>G_{r_1} (V) \subseteq G_{r_2} (V) \;</math>. Свойство графа является монотонным (возрастающим), если в том случае, если граф обладает таким свойством, то каждый суперграф с тем же множеством вершин также обладает этим свойством. Задача о поиске критического диапазона (или критического радиуса) заключается в том, чтобы найти некоторый минимальный диапазон r, такой, что <math>G_r (V) \;</math> обладает некоторым монотонным свойством. К примеру, свойство связности графа является монотонным и очень важным для множества приложений. Любопытно узнать, является ли <math>G_r (V) \;</math> связным. Обозначим за | Пусть дано множество точек V. Граф с множеством вершин V, в котором между двумя вершинами имеется ребро в том и только том случае, если расстояние между ними не превышает некоторого положительного вещественного числа r, называется графом r-кругов над множеством вершин V и обозначается <math>G_r (V) \;</math>. Если <math>r1 \le r2 \;</math>, то, очевидно, <math>G_{r_1} (V) \subseteq G_{r_2} (V) \;</math>. Свойство графа является монотонным (возрастающим), если в том случае, если верно утверждение: если граф обладает таким свойством, то каждый суперграф с тем же множеством вершин также обладает этим свойством. Задача о поиске критического диапазона (или критического радиуса) заключается в том, чтобы найти некоторый минимальный диапазон r, такой, что <math>G_r (V) \;</math> обладает некоторым монотонным свойством. К примеру, свойство связности графа является монотонным и очень важным для множества приложений. Любопытно узнать, является ли <math>G_r (V) \;</math> связным. Обозначим за <math>\rho_{con} (V) \;</math> минимальный диапазон r, такой, что <math>G_r (V) \;</math> является связным. Тогда <math>G_r (V) \;</math> является связным, если <math>r \ge \rho_{con} (V) \;</math>, и несвязным в противном случае. В данном случае <math>\rho_{con} (V) \;</math> будет называться критическим диапазоном для свойства связности V. | ||
Формально задача о критическом диапазоне определяется следующим образом. | |||
'''Определение 1'''. Критическим диапазоном для монотонного свойства графа <math>\pi \;</math> над множеством точек V, обозначаемым <math>\rho_{\pi} (V) \;</math>, является наименьший диапазон r, такой, что <math>G_r (V) \;</math> обладает свойством <math>\pi \;</math>. | |||
С другой стороны, для заданного геометрического свойства соответствующая геометрическая структура обычно бывает встроена. Во многих случаях задача нахождения критического диапазона для свойства графа оказывается родственной или эквивалентной задаче о самом длинном ребре в соответствующей геометрической структуре. Например, если граф <math>G_r (V) \;</math> является связным, он содержит евклидово [[минимальное остовное дерево]] (EMST), а | |||
С другой стороны, для заданного геометрического свойства соответствующая геометрическая структура обычно бывает встроена. Во многих случаях задача нахождения критического диапазона для свойства графа оказывается родственной или эквивалентной задаче о самом длинном ребре в соответствующей геометрической структуре. Например, если граф <math>G_r (V) \;</math> является связным, он содержит евклидово [[минимальное остовное дерево]] (EMST), а <math>\rho_{con} (V) \;</math> равно длине наибольшего ребра в EMST. Таким образом, задача нахождения критического диапазона для свойства связности эквивалентна задаче нахождения самого длинного ребра в EMST, а критическим диапазоном для свойства связности является наименьшее значение r, такое, что <math>G_r (V) \;</math> содержит EMST. | |||
| Строка 15: | Строка 17: | ||
== Основные результаты == | == Основные результаты == | ||
Далее будут рассматриваться точки на двумерной плоскости. Пусть <math>X_1, X_2, ... \;</math> – независимые и равномерно распределенные случайные точки в ограниченной области A. Пусть имеется целое положительное число n. Точечным процессом <math>\{ X_1, X_2, ..., X_n \} \;</math> называется равномерный n-точечный процесс над A, обозначаемый <math>\ | Далее будут рассматриваться точки на двумерной плоскости. Пусть <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> пуассонову случайную переменную с параметром <math>\lambda \;</math>, независимую от <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>. | ||
Вершина в графе называется изолированной, если она не имеет соседей. В связном графе изолированных вершин не существует. Асимптотическое распределение количества изолированных вершин задается следующей теоремой [2, 6, 14]. | Вершина в графе называется изолированной, если она не имеет соседей. В связном графе изолированных вершин не существует. Асимптотическое распределение количества изолированных вершин задается следующей теоремой [2, 6, 14]. | ||
'''Теорема 1. Пусть <math>r_n = \sqrt { \frac{ln \; n + \xi}{\pi \; n} }</math>, а <math>\Omega \;</math> – круг или квадрат единичной площади. Количество изолированных вершин в <math>G_r ( \ | '''Теорема 1. Пусть <math>r_n = \sqrt { \frac{ln \; n + \xi}{\pi \; n} }</math>, а <math>\Omega \;</math> – круг или квадрат единичной площади. Количество изолированных вершин в <math>G_r ( \mathcal{X}_n (\Omega)) \;</math> или <math>G_r (\mathcal{P}_n (\Omega)) \;</math> является асимптотически пуассоновским со средним значением <math>e^{- \xi} \;</math>.''' | ||
Согласно этой теореме, вероятность события, заключающегося в том, что в графе нет изолированных вершин, асимптотически равна <math>exp \big( - e^{- \xi} \big) \;</math>. Согласно теории случайных геометрических графов, если в графе нет изолированных вершин, он почти наверное является связным. Из этого следует формулировка теоремы 2 [6, 8, 9]. | |||
'''Теорема 2. Пусть <math>r_n = \sqrt { \frac{ln \; n + \xi}{\pi \; n} }</math>, а <math>\Omega \;</math> – круг или квадрат единичной площади. Тогда:''' | |||
<math>Pr[G_r(\mathcal{X}_n (\Omega))</math> является связным <math>] \to exp(-e^{- \xi})</math> и | |||
<math>Pr[G_r(\mathcal{P}_n (\Omega))</math> является связным <math>] \to exp(-e^{- \xi})</math>. | |||
В беспроводных сетях датчиков область развертывания является k-покрытой, если каждая точка в области развертывания находится внутри диапазона покрытия не менее чем k датчиков (вершин). Предположим, что диапазоны покрытия представляют собой круги радиуса r с центрами в вершинах. Пусть k – фиксированное неотрицательное целое число, а <math>\Omega \;</math> – круг или квадрат единичной площади с центром в точке '''o'''. Для любого вещественного числа t обозначим за <math>t \Omega \;</math> множество <math>\{ tx: x \in \Omega \} \;</math>, то есть круг или квадрат площадью <math>t^2 \;</math> с центром в той же точке. Пусть <math>C_{n, r} \;</math> (<math>C'_{n, r} \;</math>, соответственно) обозначает событие, заключающееся в том, что <math>\Omega \;</math> (k + 1)-покрыто (открытыми или закрытыми) кругами радиуса r с центрами в точках <math>\mathcal{P}_n (\Omega) \; (\mathcal{X}_n (\Omega)</math>, соответственно). Пусть <math>K_{s, n} \;</math> (<math>K'_{s,n} \;</math>, соответственно) обозначает событие, заключающееся в том, что <math>\sqrt{s} \Omega \;</math> (k + 1)-покрыто (открытыми или закрытыми) единичными кругами с центрами в точках <math>\mathcal{P}_n( \sqrt{s} \Omega ) \;</math> (<math>\mathcal{X}_n (\sqrt{s} \Omega) \;</math>, соответственно). Для упрощения представления обозначим за <math>\eta \;</math> периферию <math>\Omega \;</math>, которая равна 4 (<math>2 \sqrt{ \pi} \;</math>, соответственно), если <math>\Omega \;</math> является квадратом (или, соответственно, кругом). Для любого <math>\xi \in \mathbb{R} \;</math> положим | |||
<math>\alpha( \xi) = | |||
\begin{cases} | |||
\frac{ \Big( \frac{\sqrt{ \pi} \; \eta}{2} + e^{- \frac{ \xi}{2}} \Big) ^2} {16 \Big( 2 \sqrt {\pi} \eta + e^{- \frac{ \xi}{2}} \Big) } \; e^{- \frac{ \xi}{2}}), k = 0 \\ | |||
\frac{\sqrt{ \pi} \eta}{2^{k+ 6} (k + 2)!} \; e^{- \frac{ \xi}{2}}, k \ge 1 | |||
\end{cases}</math> | |||
и | |||
<math>\beta( \xi) = | |||
\begin{cases} | |||
4 e^{- \xi} + 2 \Big( \sqrt{ \pi} + \frac{1}{\sqrt{ \pi}} \Big) \eta \; e^{- \frac{\xi}{2} } , k = 0 \\ | |||
\frac{\sqrt{ \pi} + \frac{1}{ \sqrt{ \pi}}} {2^{k - 1} \; k!}\; \eta \; e^{- \frac{ \xi}{2}}, k \ge 1 | |||
\end{cases}</math> | |||
Асимптотика <math>Pr[C_{n, r}] \;</math> и <math>Pr[C'_{n, r}] \;</math> при n, стремящемся к бесконечности, и асимптотика <math>Pr[K_{s, n}] \;</math> и <math>Pr[K'_{s, n}] \;</math> при s, стремящемся к бесконечности, задаются следующими двумя теоремами [4, 10, 16]. | |||
'''Теорема 3. Положим <math>r_n = \sqrt{\frac{ln \; n + (2k + 1) ln \; ln \; n + \xi_n}{\pi \; n}}</math>. Если <math>lim_{n \to \infty} \xi_n = \xi \;</math> для некоторого <math>\xi \in \mathbb{R} \;</math>, то''' | |||
<math>1 - \beta(\xi) \le lim_{n \to \infty} Pr[C_{n, r_n}] \le \frac{1}{1 + \alpha(\xi)} \;</math> и | |||
<math>1 - \beta(\xi) \le lim_{n \to \infty} Pr[C'_{n, r_n}] \le \frac{1}{1 + \alpha(\xi)} \;</math>. | |||
Если <math>lim_{n \to \infty} \xi_n = \infty\;</math>, то <math>lim_{n \to \infty} Pr[C_{n, r_n}] = lim_{n \to \infty} Pr[C'_{n, r_n}] = 1.</math> | |||
Если <math>lim_{n \to \infty} \xi_n = - \infty\;</math>, то <math>lim_{n \to \infty} Pr[C_{n, r_n}] = lim_{n \to \infty} Pr[C'_{n, r_n}] = 0.</math> | |||
'''Теорема 4. Пусть <math>\mu (s) = ln \; s + 2 (k + 1) \; ln \; ln \; s + \xi(s)</math>. Если <math>lim_{s \to \infty} \xi(s) = \xi \;</math> для некоторого <math>\xi \in \mathbb{R} \;</math>, то''' | |||
<math>1 - \beta(\xi) \le lim_{s \to \infty} Pr[K_{s, \mu(s)s}] \le \frac{1}{1 + \alpha(\xi)}</math> и | |||
<math>1 - \beta(\xi) \le lim_{s \to \infty} Pr[K'_{s, \mu(s)s}] \le \frac{1}{1 + \alpha(\xi)}</math>. | |||
Если <math>lim_{s \to \infty} \xi (s) = \infty\;</math>, то <math>lim_{s \to \infty} Pr[K_{s, \mu(s)s}] = lim_{s \to \infty} Pr[K'_{s, \mu(s)s}] = 1.</math> | |||
Если <math>lim_{s \to \infty} \xi (s) = - \infty\;</math>, то <math>lim_{s \to \infty} Pr[K_{s, \mu(s)s}] = lim_{s \to \infty} Pr[K'_{s, \mu(s)s}] = 0.</math> | |||
В графах Гэбриэла (Gabriel graphs, GG) между двумя вершинами существует ребро в том и только том случае, если не существует другой вершины в круге, диаметром которого является сегмент двух этих вершин. Пусть V – множество точек, а ''l'' – положительное вещественное число. Обозначим за <math>\rho_{GG} (V) \;</math> длину наибольшего ребра графа GG над множеством V, а за N (V, ''l'') – количество ребер GG над V, имеющих длину не менее ''l''. Ван и И (2007) [11] доказали следующую теорему. | |||
'''Теорема 5. Пусть <math>\Omega \;</math> – диск единичной площади. Для любой константы <math>\xi \;</math> значение <math>N \bigg( \mathcal{P}_n (\Omega), 2 \sqrt{ \frac{ln \; n + \xi}{\pi n}} \bigg)</math> является асимптотически пуассоновским со средним <math>2 e^{- \xi} \;</math> и''' | |||
<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>. | |||
Обозначим за <math>\rho_{Del} (V) \;</math> длину наибольшего ребра триангуляции Делоне над множеством точек V. Козма и др. доказали следующую теорему [3]. | |||
'''Теорема 6. Пусть <math>\Omega \;</math> – круг единичной площади. Тогда <math>\rho_{Del} ( \mathcal{X}_n (\Omega)) = O \bigg( \sqrt[3] \frac{ln \; n}{n} \bigg)</math>.''' | |||
В беспроводных сетях с жадной прямой маршрутизацией каждая вершина отбрасывает полученный пакет в случае, если ни один из ее соседей не расположен ближе к точке назначения пакета, чем она сама, либо перенаправляет его ближайшему к точке назначения соседу. Поскольку каждой вершине требуется помнить только расположение соседей, доступных в результате одного перехода, а каждый пакет должен содержать расположение вершины – места назначения, алгоритм жадной прямой маршрутизации может быть реализован как локальный и не требующий памяти. В силу существования локального минимума, когда ни один из соседей вершины не оказывается более близким к точке назначения, чем текущая вершина, пакет может быть отброшен до того, как достигнет точки назначения. Чтобы гарантировать, что каждый пакет достигнет нужной точки, все вершины должны обладать достаточно большим диапазоном передачи во избежание попадания в ситуацию локального минимума. Применяя модель 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>. | |||
В этом определении (u, v) – пара «источник – точка назначения», а w – вершина, находящаяся ближе к v, чем u. Если каждая вершина имеет радиус передачи не менее | В этом определении (u, v) – пара «источник – точка назначения», а w – вершина, находящаяся ближе к v, чем u. Если каждая вершина имеет радиус передачи не менее <math>\rho_{GFR} (V) \;</math>, алгоритм GFR может гарантировать доставку в паре «источник – точка назначения» [12]. | ||
Теорема 7. Пусть | '''Теорема 7. Пусть <math>\Omega \;</math> – выпуклая компактная область единичной площади с ограниченной кривизной, а <math>\beta_0 = 1 / (2/3 - \sqrt{3/2 \pi}) \approx 1.6^2 \;</math>. Предположим, что <math>n \pi r^2_n = (\beta + o(1)) \; ln \; n</math> для некоторого <math>\beta > 0 \;</math>. Тогда''' | ||
1. Если | '''1. Если <math>\beta > \beta_0 \;</math>, то <math>\rho_{GFR} (\mathcal{P}_n (\Omega)) \le r_n \;</math> является асимптотическим «почти наверное».''' | ||
2. Если | '''2. Если <math>\beta < \beta_0 \;</math>, то <math>\rho_{GFR} (\mathcal{P}_n (\Omega)) > r_n \;</math> является асимптотическим «почти наверное».''' | ||
== Применение == | == Применение == | ||
В литературе графы r-кругов (или графы единичных кругов | В литературе графы r-кругов (или графы единичных кругов после надлежащего масштабирования) широко используются для моделирования гомогенных беспроводных сетей, в которых каждая вершина снабжена всенаправленной антенной. Из-за затухания радиосигнала диапазоны (радиусы) передачи беспроводных устройств зависят от мощности передачи. Для простоты задача распределения мощностей обычно моделируется соответствующей задачей присваивания диапазонов передачи. В последние годы децентрализованные беспроводные сети привлекли внимание множества исследователей из-за широкого спектра областей применения. Во многих таких областях в силу того, что беспроводные устройства питаются от аккумуляторов, присваивание диапазонов передачи стало одним из важнейших способов продления продолжительности работы системы. Применяя теорию критических диапазонов, можно обеспечить для децентрализованной беспроводной сети со случайным расположением элементов высокую вероятность того, что диапазон передачи будет больше некоторого критического значения. | ||
Одной из сфер применения критических диапазонов является связность сетей. Сеть является k-вершинно-связной, если между любой парой вершин существует k вершинно-непересекающихся путей. Если сети присуще это свойство, то между любой парой вершин имеется по меньшей мере k различных путей коммуникации, и сеть остается связной даже в случае отказа k-1 вершин. Таким образом, благодаря более высокому уровню связности сеть может обладать повышенной пропускной способностью и более высокой отказоустойчивостью. В работах [9, 14] и [15] | Одной из сфер применения критических диапазонов является связность сетей. Сеть является k-вершинно-связной, если между любой парой вершин существует k вершинно-непересекающихся путей. Если сети присуще это свойство, то между любой парой вершин имеется по меньшей мере k различных путей коммуникации, и сеть остается связной даже в случае отказа k-1 вершин. Таким образом, благодаря более высокому уровню связности сеть может обладать повышенной пропускной способностью и более высокой отказоустойчивостью. В работах [9, 14] и [15] рассматриваются сети с отказавшими узлами или линиями связи. | ||
Еще одной областью применения является управление топологией. Для эффективного управления децентрализованными беспроводными сетями необходимо строить и поддерживать подмножества топологии сети. Соответствующий раздел называется управлением топологией. Остов представляет собой подмножество топологии сети, в котором минимальная полная стоимость пути между любыми двумя вершинами (отражающая, например, расстояние или энергопотребление) только в константное число раз больше минимальной полной стоимости в исходной топологии сети. Таким образом, остовы оказываются подходящими кандидатами на роль виртуальных магистралей. Такие геометрические структуры, как евклидовы минимальные остовные деревья, графы относительных окрестностей, графы Гэбриэла, триангуляции Делоне, графы Яо и другие, широко используются в качестве компонентов при построении остовов [1, 5, 13]. Применение знаний о критических диапазонах | Еще одной областью применения является управление топологией. Для эффективного управления децентрализованными беспроводными сетями необходимо строить и поддерживать подмножества топологии сети. Соответствующий раздел называется управлением топологией. Остов представляет собой подмножество топологии сети, в котором минимальная полная стоимость пути между любыми двумя вершинами (отражающая, например, расстояние или энергопотребление) только в константное число раз больше минимальной полной стоимости в исходной топологии сети. Таким образом, остовы оказываются подходящими кандидатами на роль виртуальных магистралей. Такие геометрические структуры, как евклидовы минимальные остовные деревья, графы относительных окрестностей, графы Гэбриэла, триангуляции Делоне, графы Яо и другие, широко используются в качестве компонентов при построении остовов [1, 5, 13]. Применение знаний о критических диапазонах позволяет снизить сложность разработки алгоритмов [3, 11]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
