Аноним

Планарные остовы ограниченной степени с малыми весами: различия между версиями

Материал из WEGA

Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)

Версия от 23:55, 12 мая 2016

44 байта добавлено ,  12 мая 2016
м
→‎См. также
 
(не показана 1 промежуточная версия этого же участника)
Строка 10: Строка 10:
2. ОГРАНИЧЕННАЯ СТЕПЕНЬ: [1, 9, 11, 13, 16, 17]. Желательно также, чтобы логическая степень узла в построенной топологии была ограничена сверху некоторой небольшой константой. Структуры с ограниченной логической степенью находят применение в беспроводных сетях, работающих по протоколу Bluetooth, в которых главный узел может одновременно иметь не более семи подчиненных узлов. Структура с логическими узлами невысокой степени сокращает стоимость обновления таблицы маршрутизации при мобильности узлов. Структура с малым значением степени и укороченными связями может значительно повысить общую пропускную способность сети [6].
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]. Если структура маршрутизации основана на топологии планарной сети, эти локализованные протоколы маршрутизации гарантируют доставку сообщения без применения таблицы маршрутизации: каждый промежуточный узел способен сам определить, какому соседнему логическому узлу переслать пакет, используя только локальную информацию и позиции источника и пункта назначения.
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]. Если структура маршрутизации основана на топологии планарной сети, эти локализованные протоколы маршрутизации гарантируют доставку сообщения без применения таблицы маршрутизации: каждый промежуточный узел способен сам определить, какому соседнему логическому узлу переслать пакет, используя только локальную информацию и позиции источника и пункта назначения.




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


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


3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с k – 1 логическими соседями, где <math>k \ge 9</math> – настраиваемый параметр.
3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с k – 1 логическими соседями, где <math>k \ge 9</math> – настраиваемый параметр.
Строка 29: Строка 29:
4. '''Ограниченная средняя физическая степень узла''': ожидаемая средняя физическая степень узла не превышает константы малой величины. Здесь физическая степень узла u в структуре H определяется как число узлов внутри диска с центром в u и радиусом <math>max_{uv \in H} \big\| uv \big\| </math>.
4. '''Ограниченная средняя физическая степень узла''': ожидаемая средняя физическая степень узла не превышает константы малой величины. Здесь физическая степень узла u в структуре H определяется как число узлов внутри диска с центром в u и радиусом <math>max_{uv \in H} \big\| uv \big\| </math>.


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


6. '''<math>\Theta\ </math>-разделенные соседи''': направления между любыми двумя логическими соседями любого узла разделены углом не менее <math>\Theta\ </math>, что снижает интерференцию коммуникации.
6. '''<math>\Theta\ </math>-разделенные соседи''': направления между любыми двумя логическими соседями любого узла разделены углом не менее <math>\Theta\ </math>, что снижает интерференцию коммуникации.
Строка 36: Строка 36:




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


Пусть <math>N_{UDG}(u) \;</math> – множество соседей узла u в UDG. Пусть N(u) – множество соседей узла u в финальной топологии, которая была инициализирована как множество соседних узлов в GG.
Пусть <math>N_{UDG}(u) \;</math> – множество соседей узла u в UDG. Пусть N(u) – множество соседей узла u в финальной топологии, которая была инициализирована как множество соседних узлов в GG.
Строка 42: Строка 42:




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


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


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


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


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


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


3: После того, как узел x обнаружит, что необработанная инцидентная ему дуга xy имеет наименьший идентификатор среди всех необработанных связей в <math>E_2 (x) \; </math>, он удаляет дугу xy в случае, если существует дуга <math>uv \in E_2 (x) \; </math> (где u и v отличны от x и y), такая, что <math>\big\| xy \big\| > max( \big\| uv \big\|, 3\big\| ux \big\|, 3\big\| vy \big\|)</math>; в противном случае он помечает дугу xy как обработанную. Предположим, что uvyx представляет собой выпуклую оболочку, состоящую из узлов u, v, x и y. Тогда статус связи передается всем соседям при помощи широковещательного сообщения UPDATESTATUS(XY).
3: После того, как узел x обнаружит, что необработанное инцидентное ему ребро xy имеет наименьший идентификатор среди всех необработанных связей в <math>E_2 (x) \; </math>, он удаляет ребро xy в случае, если существует ребро <math>uv \in E_2 (x) \; </math> (где u и v отличны от x и y), такая, что <math>\big\| xy \big\| > 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>E_2 (u) \; </math>.
4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в <math>E_2 (u) \; </math>.


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


== Применение ==
== Применение ==
Строка 104: Строка 104:
* ''[[Геометрические остовы]]
* ''[[Геометрические остовы]]
* ''[[Планарные геометрические остовы]]
* ''[[Планарные геометрические остовы]]
* ''[[Остовы разреженных графов]]
* ''[[Разреженные остовы графов]]


== Литература ==
== Литература ==
Irina
4430

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/10470...11502