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

Ключевые слова и синонимы

Случайные геометрические графы; свойства монотонности; изолированные вершины; связность; графы Гэбриэла; триангуляции Делоне; жадные алгоритмы прямой маршрутизации

Постановка задачи

Пусть дано множество V. Граф с множеством вершин V, в котором между двумя вершинами имеется ребро в том и только том случае, если расстояние между ними не превышает некоторого положительного вещественного числа r, называется графом r-кругов над множеством вершин V и обозначается [math]\displaystyle{ G_r (V) \; }[/math]. Если [math]\displaystyle{ r1 \le r2 \; }[/math], то, очевидно, [math]\displaystyle{ G_{r_1} (V) \subseteq G_{r_2} (V) \; }[/math]. Свойство графа является монотонным (возрастающим), если в том случае, если граф обладает таким свойством, то каждый суперграф с тем же множеством вершин также обладает этим свойством. Задача о поиске критического диапазона (или критического радиуса) заключается в том, чтобы найти некоторый минимальный диапазон r, такой, что [math]\displaystyle{ G_r (V) \; }[/math] обладает некоторым монотонным свойством. К примеру, свойство связности графа является монотонным и очень важным для множества приложений. Любопытно узнать, является ли [math]\displaystyle{ G_r (V) \; }[/math] связным. Обозначим за pcon (V) минимальный диапазон r, такой, что [math]\displaystyle{ G_r (V) \; }[/math] является связным. Тогда [math]\displaystyle{ G_r (V) \; }[/math] является связным, если [math]\displaystyle{ r \ge \rho_{con} (V) \; }[/math], и несвязным в противном случае. В данном случае [math]\displaystyle{ \rho_{con} (V) \; }[/math] будет называться критическим диапазоном для свойства связности V. Формально задача о критическом диапазоне определяется следующим образом.

Определение 1. Критическим диапазоном для монотонного свойства графа ж над множеством точек V, обозначаемым [math]\displaystyle{ \rho_{\pi} (V) \; }[/math], является наименьший диапазон r, такой, что [math]\displaystyle{ G_r (V) \; }[/math] обладает свойством [math]\displaystyle{ \pi \; }[/math].

С другой стороны, для заданного геометрического свойства соответствующая геометрическая структура обычно бывает встроена. Во многих случаях задача нахождения критического диапазона для свойства графа оказывается родственной или эквивалентной задаче о самом длинном ребре в соответствующей геометрической структуре. Например, если граф [math]\displaystyle{ G_r (V) \; }[/math] является связным, он содержит евклидово минимальное остовное дерево (EMST), а pcon (V) эквивалентно длине наибольшего ребра в EMST. Таким образом, задача нахождения критического диапазона для свойства связности эквивалентна задаче нахождения самого длинного ребра в EMST, а критическим диапазоном для свойства связности является наименьшее значение r, такое, что [math]\displaystyle{ G_r (V) \; }[/math] содержит EMST.

В большинстве случаев, как в приведенном примере, критический диапазон можно вычислить при помощи алгоритмов с полиномиальным временем выполнения. Таким образом, эта задача не является вычислительно сложной. Исследователей интересует вероятностный анализ критического диапазона, особенно асимптотическое поведение графов r-кругов над множествами случайных точек. В качестве общего термина для теории графов r-кругов над множествами случайных точек используется обозначение «случайные геометрические графы» [8].

Основные результаты

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

Вершина в графе называется изолированной, если она не имеет соседей. В связном графе изолированных вершин не существует. Асимптотическое распределение количества изолированных вершин задается следующей теоремой [2, 6, 14].

Теорема 1. Пусть [math]\displaystyle{ r_n = \sqrt { \frac{ln \; n + \xi}{\pi \; n} } }[/math], а [math]\displaystyle{ \Omega \; }[/math] – круг или квадрат единичной площади. Количество изолированных вершин в [math]\displaystyle{ G_r ( \mathcal{X}_n (\Omega)) \; }[/math] или [math]\displaystyle{ G_r (\mathcal{P}_n (\Omega)) \; }[/math] является асимптотически пуассоновским со средним значением [math]\displaystyle{ e^{- \xi} \; }[/math].

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

Теорема 2. Пусть [math]\displaystyle{ r_n = \sqrt { \frac{ln \; n + \xi}{\pi \; n} } }[/math], а [math]\displaystyle{ \Omega \; }[/math] – круг или квадрат единичной площади. Тогда:

[math]\displaystyle{ Pr[G_r(\mathcal{X}_n (\Omega)) }[/math] является связным [math]\displaystyle{ ] \to exp(-e^{- \xi}) }[/math] и

[math]\displaystyle{ Pr[G_r(\mathcal{P}_n (\Omega)) }[/math] является связным [math]\displaystyle{ ] \to exp(-e^{- \xi}) }[/math].

В беспроводных сетях датчиков область развертывания является k-покрытой, если каждая точка в области развертывания находится внутри диапазона покрытия не менее чем k датчиков (вершин). Предположим, что диапазоны покрытия представляют собой круги радиуса r с центрами в вершинах. Пусть k – фиксированное неотрицательное целое число, а [math]\displaystyle{ \Omega \; }[/math] – круг или квадрат единичной площади с центром в точке o. Для любого вещественного числа t обозначим за [math]\displaystyle{ t \Omega \; }[/math] множество [math]\displaystyle{ \{ tx: x \in \Omega \} \; }[/math], то есть круг или квадрат площадью [math]\displaystyle{ t^2 \; }[/math] с центром в той же точке. Пусть [math]\displaystyle{ C_{n, r} \; }[/math] ([math]\displaystyle{ C'_{n, r} \; }[/math], соответственно) обозначает событие, заключающееся в том, что [math]\displaystyle{ \Omega \; }[/math] (k + 1)-покрыто (открытыми или закрытыми) кругами радиуса r с центрами в точках [math]\displaystyle{ \mathcal{P}_n (\Omega) \; (\mathcal{X}_n (\Omega) }[/math], соответственно). Пусть [math]\displaystyle{ K_{s, n} \; }[/math] ([math]\displaystyle{ K'_{s,n} \; }[/math], соответственно) обозначает событие, заключающееся в том, что [math]\displaystyle{ \sqrt{s} \Omega \; }[/math] (k + 1)-покрыто (открытыми или закрытыми) единичными кругами с центрами в точках [math]\displaystyle{ \mathcal{P}_n( \sqrt{s} \Omega ) \; }[/math] ([math]\displaystyle{ \mathcal{X}_n (\sqrt{s} \Omega) \; }[/math], соответственно). Для упрощения представления обозначим за [math]\displaystyle{ \eta \; }[/math] периферию [math]\displaystyle{ \Omega \; }[/math], которая равна 4 ([math]\displaystyle{ 2 \sqrt{ \pi} \; }[/math], соответственно), если [math]\displaystyle{ \Omega \; }[/math] является квадратом (или, соответственно, кругом). Для любого [math]\displaystyle{ \xi \in \mathbb{R} \; }[/math] положим

[math]\displaystyle{ \alpha( \xi) = \begin{cases} \frac{(\frac{\sqrt{ \pi} \; \eta}{2} + e^{- \frac{ \xi}{2}})^2} {16 (2 \sqrt {\pi} \eta + e^{- \frac{ \xi}{2}})} \; 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]

Асимптотика Pr [С„;Г] и Pr[C^r], когда n стремится к бесконечности, и асимптотика Pr[jCS;n] и Pr \K'S n], когда стремится к бесконечности, задаются следующими двумя теоремами [4, 10, 16].

Теорема 3. Пусть rn = |„ = % для некоторого f 2 R. Тогда 1 - /3 (?) < Hm Pr [С„,г„] < 1 n-s-oo L "J 1 + a 1 - P (I) < lim Pr ГС' n ; r.

Если limn!1 |„ = 1, то lim Pr \Cn r 1 = lim Pr \C' 1 = 1. Если limn^oofn = -oo, то lim Pr \Cn r 1 = lim Pr \C' 1 = 0.

Теорема 4. ii{s) = lns + 2 (k + 1)lnlns + | (s). Если lims!1 | (s) = % для некоторого f 2 R, то 1, и 1 - P (I) < lim Pr |X w(s)sl < 1 1 - P (I) < lim Pr \K's (J) 1 < 1  : lims!1 | (s) = 1; то Если lims!1 f (s) = - infty то 0: Д^ Pr [KsMs)s] = Дт Pr [K'sMs)s] =

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

Теорема 5. Пусть Q – круг единичной площади. Для любой константы существует среднее 2e ?, и асимптотическое пуассоновское с

Обозначим за pDei (V) длину наибольшего ребра триангуляции Делоне над множеством точек V. Козма и др. [3] доказали следующую теорему. [3].

Теорема 6. Пусть Q – круг единичной площади. Тогда pDel {Xn{Q)) = O.

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

В этом определении (u, v) – пара «источник – точка назначения», а w – вершина, находящаяся ближе к v, чем u. Если каждая вершина имеет радиус передачи не менее PGFR(^)>, алгоритм может гарантировать доставку в паре «источник – точка назначения» [12].

Теорема 7. Пусть Q – выпуклая компактная область единичной площади с ограниченной кривизной, а p0 = 1/ (2/3 - */Ъ12л) « 1:62. Предположим, что плг2п = (f$ + o (1))ln n для некоторого f$ > 0. Тогда

1. Если P > Po, то рорлСР„(^2)) < rn является асимптотическим «почти наверное».

2. Если P < fa, то PGFR {Tn{Q)) > rn является асимптотическим «почти наверное».

Применение

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

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

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

Открытые вопросы

Некоторые задачи, имеющие отношение к критическим диапазонам, остаются нерешенными. Большинство рассматривавшихся выше задач применяют геометрию двумерной плоскости. Иными словами, множество точек расположено на одной плоскости. Первым направлением последующих работ должно стать исследование этих задач в пространствах больших размерностей. Также представляет интерес область задач о самом длинном ребре на других геометрических структурах – например, графах относительных окрестностей и графах Яо. Третье направление будущих исследований может касаться рассматривания отношений между свойствами графов. Хорошо известный результат из теории случайных геометрических графов говорит о том, что исчезновение изолированных вершин асимптотически приводит к возникновению связности сетей. Однако для беспроводных сетей с ненадежными линиями связи это свойство еще не доказано. Кроме того, представляют интерес отношения между связностью и покрытием в беспроводных сетях датчиков.

См. также

• Применение геометрических остовных сетей
• Связное доминирующее множество
• Протяженность геометрических сетей
• Геометрические остовы
• Минимальные геометрические остовные деревья
• Минимальные k-связные геометрические сети
• Рандомизированная широковещательная передача в радиосетях
• Рандомизированный мгновенный обмен сообщениями в радиосетях

Литература

1. Cartigny, J., Ingelrest, F., Simplot-Ryl, D., Stojmenovic, I.: Localized LMSTand RNG based minimum-energy broadcast protocols in ad hoc networks. Ad Hoc Netw. 3(1), 1-16 (2004)

2. Dette, H., Henze, N.: The limit distribution of the largest nearest-neighbour link in the unit d-cube. J. Appl. Probab. 26, 67-80(1989)

3. Kozma, G., Lotker, Z., Sharir, M., Stupp, G.: Geometrically aware communication in random wireless networks. In: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, 25-28 July 2004, pp. 310-319

4. Kumar, S., Lai,T.H., Balogh, J.:On k-coverage in a mostly sleeping sensor network. In: Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MobiCom'04), 26 Sept-1 Oct 2004

5. Li, N., Hou, J.C., Sha, L.: Design and analysis of a MST-based distributed topology control algorithm for wireless ad-hoc net works. In: 22nd Annual Joint Conference Of The IEEE Computer And Communications Societies (INFOCOM 2003), vol. 3, 1-3 April 2003, pp. 1702-1712

6. Penrose, M.: The longest edge of the random minimal spanning tree. Ann. Appl. Probab. 7(2), 340-361 (1997)

7. Penrose, M.: On k-connectivity for a geometric random graph. Random. Struct. Algorithms 15(2), 145-164 (1999)

8. Penrose, M.: Random Geometric Graphs. Oxford University Press, Oxford (2003)

9. Wan, P.-J., Yi, C.-W.: Asymptotic critical transmission ranges for connectivity in wireless ad hoc networks with Bernoulli nodes. In: IEEE Wireless Communications and Networking Conference (WCNC 2005), 13-17 March 2005

10. Wan, P.-J., Yi, C.-W.: Coverage by randomly deployed wireless sensor networks. In: Proceedings of the 4th IEEE International Symposium on Network Computing and Applications (NCA 2005), 27-29 July 2005

11. Wan, P.-J., Yi, C.-W.: On the longest edge of Gabriel graphs in wireless ad hoc networks. Trans. Parallel Distrib. Syst. 18(1), 1-16(2007)

12. Wan, P.-J., Yi, C.-W., Yao, F., Jia, X.: Asymptotic critical transmission radius for greedy forward routing in wireless ad hoc networks. In: Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 22-25 May 2006, pp. 25-36

13. Wang, Y., Li, X.-Y.: Localized construction of bounded degree and planar spanner for wireless ad hoc networks, In: Proceedings of the 2003 joint workshop on Foundations of mobile computing (DIALM-POMC’03), 19 Sept 2003, pp. 59-68

14. Yi, C.-W., Wan, P.-J., Li, X.-Y., Frieder, O.: Asymptotic distribution of the number of isolated nodes in wireless ad hoc networks with Bernoulli nodes. In: IEEE Wireless Communications and Networking Conference (WCNC 2003), March 2003

15. Yi, C.-W., Wan, P.-J., Lin, K.-W., Huang, C.-H.: Asymptotic distribution of the Number of isolated nodes in wireless ad hoc networks with unreliable nodes and links. In: the 49th Annual IEEE GLOBECOM Technical Conference (GLOBECOM 2006), 27 Nov-1 Dec 2006

16. Zhang, H., Hou, J.: On deriving the upper bound of a-lifetime for large sensor networks. In: Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc 2004), 24-26 March 2004