Планарные остовы ограниченной степени с малыми весами

Планарные остовы ограниченной степени с малыми весами --- Degree-bounded planar spanner

with low weight

Ключевые слова и синонимы: унифицированное энергоэффективное управление одноадресной и широковещательной топологиями (Unified energy-efficient unicast and broadcast topology

control)

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

Важным требованием к децентрализованным беспроводным сетям является возможность их самоорганизации; необходима динамическая реструктуризация диапазонов передачи и трактов передачи данных при изменении топологии. Рациональное использование энергии и производительность работы сети – два наиболее важных параметра функционирования децентрализованных беспроводных сетей, поскольку беспроводные устройства обычно работают только от аккумуляторов, а их вычислительные возможности и объем памяти ограничены. Таким образом, в этой динамичной среде с ограниченными ресурсами каждый беспроводной узел должен локально выбирать соседей по коммуникации и соответствующим образом корректировать мощность передачи; в результате все узлы сети самостоятельно формируют топологию, являющуюся энергоэффективной и для одноадресной передачи, и для широковещательной рассылки.

Для поддержки энергоэффективной одноадресной передачи топология должна обладать следующими свойствами:

1. СИЛОВОЙ ОСТОВ: [1, 9, 13, 16, 17]. Подграф H называется силовым остовом графа G, если существует положительная вещественная константа [math]\displaystyle{ \rho\ }[/math], такая, что для любых двух вершин графа потребление энергии на кратчайшем пути в H не более чем в [math]\displaystyle{ \rho\ }[/math] раз выше потребления энергии на кратчайшем пути в G. [math]\displaystyle{ \rho\ }[/math] называется коэффициентом растяжения по мощности или просто коэффициентом растяжения.

2. ОГРАНИЧЕННАЯ СТЕПЕНЬ: [1, 9, 11, 13, 16, 17]. Желательно также, чтобы логическая степень узла в построенной топологии была ограничена сверху некоторой небольшой константой. Структуры с ограниченной логической степенью находят применение в беспроводных сетях, работающих по протоколу Bluetooth, в которых главный узел может одновременно иметь не более семи подчиненных узлов. Структура с логическими узлами невысокой степени сокращает стоимость обновления таблицы маршрутизации при мобильности узлов. Структура с малым значением степени и укороченными связями может значительно повысить общую пропускную способность сети [6].

3. ПЛАНАРНОСТЬ: [1, 4, 13, 14, 16]. Топология сети в идеале должна быть планарной (что означает, что никакие два ребра графа не пересекают друг друга), благодаря чему будут корректно и эффективно работать некоторые локализованные алгоритмы маршрутизации – такие как жадная маршрутизация по граням (Greedy Face Routing, GFG) [2], жадная маршрутизация по периметру без контроля состояния (Greedy Perimeter Stateless Routing, GPSR) [5], адаптивная маршрутизация по граням (Adaptive Face Routing, AFR) [7] и жадно-адаптивная маршрутизация по граням (Greedy Other Adaptive Face Routing, GOAFR) [8]. Если структура маршрутизации основана на топологии планарной сети, эти локализованные протоколы маршрутизации гарантируют доставку сообщения без применения таблицы маршрутизации: каждый промежуточный узел способен сам определить, какому соседнему логическому узлу переслать пакет, используя только локальную информацию и позиции источника и пункта назначения.

Для поддержки энергоэффективной широковещательной связи [15] локально построенная топология должна обладать свойством малых весов: полная длина линии связи финальной топологии не более чем в константное число раз превышает длину линии в Евклидово минимальном остовном дереве (Euclidean Minimum Spanning Tree, EMST). Некоторые локализованные алгоритмы [10, 12] были применены для построения структур с малыми весами, способных аппроксимировать энергоэфективность EMST по мере роста плотности сети. Однако ни один из них не был достаточно энергоэффективным для одноадресной передачи.

До сих пор все известные алгоритмы управления топологиями не были способны обеспечить энергоэффективные одноадресную и широковещательную передачи в рамках одной и той же структуры. Была поставлена задача проектирования унифицированной топологии, обладающей одновременно свойствами остовности и малых весов. Основной целью разработки алгоритма было решение этой задачи.

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

Это первый локализованный алгоритм управления топологиями для всех узлов, работающий на базе унифицированной энергоэффективной типологии для одноадресной и широковещательной передачи в децентрализованных беспроводных сетях и сенсорных сетях. В рамках единой структуры гарантируются следующие свойства сети:

1. Энергоэффективная одноадресная передача: пусть даны два любых узла, тогда между ними в структуре существует путь, полные энергозатраты которого не более чем в [math]\displaystyle{ 2 \rho\ + 1 }[/math] раза превышают энергозатраты любого пути, соединяющего их в исходной сети. Здесь [math]\displaystyle{ \rho\ \gt 1 }[/math] – некоторая константа, которая будет определена далее в описании алгоритма. Предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до своего соседа v на любом выбранном пути одноадресной передачи.

2. Энергоэффективная широковещательная рассылка: энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина ее ребер не более чем в константное число раз превышает полную длину ребер в минимальном Евклидовом остовном дереве. Для случая широковещательной рассылки и в целом любой многоабонентской рассылки предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до самого далекого достижимого узла любой выбранной структуры (обычно дерева) при передаче нескольким абонентам.

3. Ограниченная логическая степень узла: каждый узел должен связываться не более чем с k – 1 логическими соседями, где [math]\displaystyle{ k \ge 9 }[/math] – настраиваемый параметр.

4. Ограниченная средняя физическая степень узла: ожидаемая средняя физическая степень узла не превышает константы малой величины. Здесь физическая степень узла u в структуре H определяется как число узлов внутри диска с центром в u и радиусом [math]\displaystyle{ max_{uv \in H} \big\| uv \big\| }[/math].

5. Планарность: не имеется ребер, пересекающих друг друга. Свойство планарности позволяет выполнять над этой структурой некоторые локализованные алгоритмы маршрутизации [2, 5, 7, 8], гарантируя доставку пакетов без использования таблицы маршрутизации.

6. [math]\displaystyle{ \Theta\ }[/math]-разделенные соседи: направления между любыми двумя логическими соседями любого узла разделены углом не менее [math]\displaystyle{ \Theta\ }[/math], что снижает интерференцию коммуникации.

Это первая известная локализованная стратегия управления топологиями для всех узлов, совместно поддерживающих такую простую структуру с подобными свойствами. Прежде был известен только централизованный алгоритм, представленный в [1]. Первый шаг представляет собой Алгоритм 1, который строит энергоэффективную топологию для одноадресной передачи; затем Алгоритм 2 строит топологию, способную одновременно поддерживать энергоэффективную широковещательную рассылку.

Определение 1 ( [math]\displaystyle{ \Theta\ }[/math]-доминирующая область). Для каждого соседа v узла u [math]\displaystyle{ \Theta\ }[/math]-доминирующей областью v является [math]\displaystyle{ 2 \Theta\ }[/math]-конус с вершиной в u, осью которого является ребро uv.

Пусть [math]\displaystyle{ N_{UDG}(u) \; }[/math] – множество соседей узла u в UDG. Пусть N(u) – множество соседей узла u в финальной топологии, которая была инициализирована как множество соседних узлов в GG. Алгоритм 1 строит сильный планарный остов степени k–1.

Лемма 1. Граф [math]\displaystyle{ S \Theta\ GG }[/math] является связным, если лежащий в его основе граф [math]\displaystyle{ GG \; }[/math] является связным. Более того, для любых двух вершин u и v существует путь [math]\displaystyle{ \{ u, t_1, ... , t_r, v \} \; }[/math], соединяющий их, такой, что все его ребра имеют длину менее [math]\displaystyle{ \sqrt{2} \big\| uv \big\| }[/math].

Теорема 2. Структура [math]\displaystyle{ S \Theta\ GG }[/math] состоит из узлов степенью не выше k – 1 и представляет собой сильный планарный остов с [math]\displaystyle{ \Theta\ }[/math]-разделенными соседями. Его коэффициент растяжения по мощности не превышает [math]\displaystyle{ \rho\ = \sqrt{2}^\beta\ / (1 - (2 \sqrt{2} sin \frac{ \pi\ }{k} )^\beta\ ) }[/math], где [math]\displaystyle{ k \ge 9 }[/math] – настраиваемый параметр.

Очевидно, что для двух конечных точек каждого ребра эта конструкция является согласованной: если ребро uv принадлежит к узлу u, то оно точно также принадлежит и к узлу v. Стоит отметить, что число 3 в критерии [math]\displaystyle{ \big\| xy \big\| \gt max( \big\| uv \big\|, 3\big\| ux \big\|, 3\big\| vy \big\|) }[/math] было выбрано со всей тщательностью.

Теорема 3. Структура [math]\displaystyle{ LS \Theta\ GG }[/math] представляет собой планарный остов ограниченной степени, имеющий константный коэффициент растяжения по мощности [math]\displaystyle{ 2 \rho\ + 1 }[/math], где [math]\displaystyle{ \rho\ }[/math] – коэффициент растяжения по мощности структуры [math]\displaystyle{ S \Theta\ GG }[/math]. Степень узлов ограничена значением k - 1, где [math]\displaystyle{ k \ge 9 }[/math] – настраиваемый параметр в [math]\displaystyle{ S \Theta\ GG }[/math].

Теорема 4. Структура [math]\displaystyle{ LS \Theta\ GG }[/math] имеет малые веса.

Теорема 5. Предположим, что как идентификатор, так и геометрическое положение узла могут быть представлены при помощи log n битов каждый. Тогда общее число сообщений за время построения структуры [math]\displaystyle{ LS \Theta\ GG }[/math] лежит в диапазоне [5n, 13n], при этом каждое сообщение содержит не более O(log n) битов.

По сравнению с ранее известными структурами с малыми весами [10, 12] [math]\displaystyle{ LS \Theta\ GG }[/math] не только обладает большим числом желаемых свойств, но и требует рассылки намного меньшего числа сообщений во время построения. Для построения [math]\displaystyle{ LS \Theta\ GG }[/math] каждому узлу необходимо собрать только информацию в [math]\displaystyle{ E_2(x) \; }[/math], для чего требуется не более 6n сообщений для n узлов. Алгоритм 2 может применяться к любому известному планарному остову ограниченной степени для того, чтобы превратить его в остов с малыми весами, сохранив при этом все имеющиеся свойства, за исключением коэффициента растяжения, который потенциально может возрасти с [math]\displaystyle{ \rho\ }[/math] до [math]\displaystyle{ 2 \rho\ + 1 }[/math].

Кроме того, ожидаемая средняя интерференция узлов в структуре ограничена константой малой величины. Это само по себе важно по следующей причине: до сих пор утверждение «топология сети с малыми логическими степенями узлов гарантирует малую интерференцию» по умолчанию принималось на веру, и лишь недавно Беркхарт и коллеги [3] показали, что в общем случае оно неверно. Кроме того, в этой работе показано, что хотя малые логические степени узлов сами по себе не гарантируют малый уровень интерференции, ожидаемая средняя интерференция будет мала, если внимательно выбирать логических соседей по коммуникации.

Теорема 6. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые максимальные значения интерференции узлов в структурах EMST, GG, RNG и Yao составляют по меньшей мере [math]\displaystyle{ \Theta\ (log n) }[/math].

Теорема 7. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые средние значения интерференции узлов в структуре EMST ограничены сверху константой.

Этот результат верен также для узлов, сформированных при помощи равномерного распределения случайной величины.

Алгоритм 1. Построение [math]\displaystyle{ S \Theta\ GG }[/math]: энергоэффективная одноадресная топология

1. Вначале каждый узел самостоятельно строит локальный граф Гэбриэля (Gabriel graph, GG). Алгоритм построения графа Гэбриэля хорошо известен; одну из возможных реализаций можно найти в [13]. Вначале все узлы помечают себя меткой WHITE, т.е. «необработанные».

2. Если WHITE-узел u имеет наименьший идентификатор среди всех WHITE-соседей в N(u), он использует следующую стратегию выбора соседей:

а) Вначале узел u сортирует всех своих BLACK-соседей в N(u), если таковые имеются, по порядку возрастания расстояния, а затем сортирует всех WHITE-соседей N(u), если таковые имеются, подобным же образом. После этого отсортированные результаты восстанавливаются в N(u); вначале записывается отсортированный список BLACK-соседей, а затем – отсортированный список WHITE-соседей.

б) Узел u сканирует отсортированный список N(u) слева направо. На каждом шагу он сохраняет в списке текущего указываемого соседа w, но удаляет каждый конфликтующий узел v из оставшейся части списка. «Узел v конфликтует с w» означает, что этот узел v принадлежит к [math]\displaystyle{ \theta\ }[/math]-доминирующей области узла w. Здесь [math]\displaystyle{ \theta\ = 2 \pi\ / k }[/math], где [math]\displaystyle{ k \ge 9 }[/math], – настраиваемый параметр. Затем узел u помечает себя меткой BLACK, т.е. «обработанный», и уведомляет каждый удаленный соседний узел v из N(u) при помощи широковещательного сообщения UPDATEN.

3. Как только узел v получает сообщение UPDATEN от соседа u из N(v), он проверяет, не находится ли он сам в списке узлов, предназначенных для удаления: обнаружив себя в нем, он удаляет узел-отправитель u из списка N(v), в противном случае помечает u как BLACK в N(v).

4. После того, как все узлы будут обработаны, все выбранные ссылки [math]\displaystyle{ \{ uv | v \in N(u), \forall v \in GG \} }[/math] образуют финальную топологию сети, обозначаемую [math]\displaystyle{ S \Theta\ GG }[/math]. Каждый узел может уменьшить диапазон передачи таким образом, чтобы успешно доставать до самого далекого соседа в финальной топологии.

Алгоритм 2. Построение [math]\displaystyle{ LS \Theta\ GG }[/math]: планарный остов ограниченной степени с низкими весами

1: Все вершины совокупно составляют граф [math]\displaystyle{ S \Theta\ GG }[/math] в локализованной форме, построенный при помощи алгоритма 1. Каждая вершина помечает инцидентные ей ребра в [math]\displaystyle{ S \Theta\ GG }[/math] как необработанные.

2: Каждый узел u локально рассылает инцидентные ему ребра в [math]\displaystyle{ S \Theta\ GG }[/math] своим односкачковым соседям при помощи широковещательной трансляции и сам прослушивает своих соседей. Затем каждый узел x исследует существование множества двухскачковых связей [math]\displaystyle{ E_2 (x) \; }[/math], определяемое следующим образом: [math]\displaystyle{ E_2 (x) = \{ uv \in S \Theta\ GG | u }[/math] или [math]\displaystyle{ v \in N_{UDG}(x) \} }[/math]. Иными словами, [math]\displaystyle{ E_2 (x) \; }[/math] представляет собой набор ребер в [math]\displaystyle{ S \Theta\ GG }[/math], имеющих по меньшей мере одну конечную точку в диапазоне передачи узла x.

3: После того, как узел x обнаружит, что необработанное инцидентное ему ребро xy имеет наименьший идентификатор среди всех необработанных связей в [math]\displaystyle{ E_2 (x) \; }[/math], он удаляет ребро xy в случае, если существует ребро [math]\displaystyle{ uv \in E_2 (x) \; }[/math] (где u и v отличны от x и y), такая, что [math]\displaystyle{ \big\| xy \big\| \gt max( \big\| uv \big\|, 3\big\| ux \big\|, 3\big\| vy \big\|) }[/math]; в противном случае он помечает ребро xy как обработанное. Предположим, что uvyx представляет собой выпуклую оболочку, состоящую из узлов u, v, x и y. Тогда статус связи передается всем соседям при помощи широковещательного сообщения UPDATESTATUS(XY).

4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в [math]\displaystyle{ E_2 (u) \; }[/math].

5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все ребра. Обозначим за [math]\displaystyle{ LS \Theta\ GG }[/math] финальную структуру, сформированную всеми оставшимися ребрами в [math]\displaystyle{ S \Theta\ GG }[/math].

Применение

Локализованное управление топологией в децентрализованных беспроводных сетях является важнейшим механизмом поддержки связности сети и организации обратной связи для протоколов обмена данными. Большая часть сетевого трафика приходится на одноадресные передачи. Основными задачами являются экономия энергозатрат и повышение производительности работы сети за счет поддержки энергоэффективной типологии локальным образом. Данный алгоритм решает эти задачи за счет выбора относительно малого уровня мощности передачи и числа соседей по коммуникации для каждой вершины, что позволяет снизить уровень интерференции. Протоколы маршрутизации MANET нередко требуют применения широковещательной рассылки. К примеру, такие одноадресные протоколы маршрутизации, как динамическая маршрутизация от источника (Dynamic Source Routing, DSR), дистанционно-векторный алгоритм маршрутизации по запросу (Ad Hoc On Demand Distance Vector, AODV), протокол зонной маршрутизации (Zone Routing Protocol, ZRP) и протокол географической маршрутизации (Location Aided Routing, LAR), используют для прокладки маршрутов широковещательную рассылку или какие-либо ее разновидности. Крайне важно использовать в таких сетях энергоэффективные алгоритмы широковещательной рассылки, поскольку беспроводные устройства часто работают только от аккумуляторов.

См. также

• Применение геометрических остовных сетей
• Геометрические остовы
• Планарные геометрические остовы
• Разреженные остовы графов

Литература

1. Bose, P., Gudmundsson, J., Smid, M.: Constructing plane spanners of bounded degree and low weight. In: Proceedings of European Symposium of Algorithms, University of Rome, 17-21 September 2002

2. Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. ACM/Kluwer Wireless Networks 7(6), 609-616 (2001). 3rd int. Workshop on Discrete Algorithms and methods for mobile computing and communications, 48-55 (1999)

3. Burkhart, M., von Rickenbach, P., Wattenhofer, R., Zollinger, A.: Does topology control reduce interference. In: ACM Int. Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc), Tokyo, 24-26 May 2004

4. Gabriel, K.R., Sokal, R.R.: A new statistical approach to geographic variation analysis. Syst. Zool. 18, 259-278 (1969)

5. Karp, B., Kung, H.T.: Gpsr: Greedy perimeter stateless routing for wireless networks. In: Proc. of the ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), Boston, 6-11 August 2000

6. Kleinrock, L., Silvester, J.: Optimum transmission radii for packet radio networks or why six is a magic number. In: Proceedings of the IEEE National Telecommunications Conference, pp. 431-435, Birmingham, 4-6 December 1978

7. Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically optimal geometric mobile ad-hoc routing. In: International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), Atlanta, 28 September 2002

8. Kuhn, F., Wattenhofer, R., Zollinger, A.: Worst-case optimal and average-case efficient geometric ad-hoc routing. In: ACM Int. Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc) Anapolis, 1-3 June 2003

9. Li, L., Halpern, J.Y., Bahl, P., Wang, Y.-M., Wattenhofer, R.: Analysis of a cone-based distributed topology control algorithms for wireless multi-hop networks. In: PODC: ACM Symposium on Principle of Distributed Computing, Newport, 26-29 August 2001

10. Li, X.-Y.: Approximate MST for UDG locally. In: COCOON, Big Sky, 25-28 July 2003

11. Li, X.-Y., Wan, P.-J., Wang, Y., Frieder, O.: Sparse power efficient topology for wireless networks. In: IEEE Hawaii Int. Conf. on System Sciences (HICSS), Big Island, 7-10 January 2002

12. Li, X.-Y., Wang, Y., Song, W.-Z., Wan, P.-J., Frieder, O.: Localized minimum spanning tree and its applications in wireless ad hoc networks. In: IEEE INFOCOM, Hong Kong, 7-11 March 2004

13. Song, W.-Z., Wang, Y., Li, X.-Y. Frieder, O.: Localized algorithms for energy efficient topology in wireless ad hoc networks. In: ACM Int. Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc), Tokyo, 24-26 May 2004

14. Toussaint, G.T.: The relative neighborhood graph of a finite planar set. Pattern Recognit. 12(4), 261-268 (1980)

15. Wan, P.-J., Calinescu, G., Li, X.-Y., Frieder, O.: Minimum-energy broadcast routing in static ad hoc wireless networks. ACM Wireless Networks (2002), To appear, Preliminary version appeared in IEEE INFOCOM, Anchorage, 22-26 April 2001

16. Wang, Y., Li, X.-Y.: Efficient construction of bounded degree and planar spanner for wireless networks. In: ACM DIALMPOMC Joint Workshop on Foundations of Mobile Computing, San Diego, 19 September 2003

17. Yao, A.C.-C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11, 721-736(1982)