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

Перейти к навигации Перейти к поиску

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

Версия от 15:13, 19 сентября 2013

272 байта добавлено ,  19 сентября 2013
м
→‎Основные результаты
Строка 40: Строка 40:




'''Лемма 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> – настраиваемый параметр.'''
Строка 46: Строка 46:
Очевидно, что для двух конечных точек каждой дуги эта конструкция является согласованной: если дуга uv принадлежит к узлу u, то она точно также принадлежит и к узлу v. Стоит отметить, что число 3 в критерии \\xy\\ > тах(||ку||, 3||мх||, 3||vy||) было выбрано со всей тщательностью.
Очевидно, что для двух конечных точек каждой дуги эта конструкция является согласованной: если дуга uv принадлежит к узлу u, то она точно также принадлежит и к узлу v. Стоит отметить, что число 3 в критерии \\xy\\ > тах(||ку||, 3||мх||, 3||vy||) было выбрано со всей тщательностью.


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


'''Теорема 4. Структура LS&GG имеет малые веса.'''
'''Теорема 4. Структура <math>LS \Theta\ GG</math> имеет малые веса.'''


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


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


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


'''Алгоритм 1. Построение S0 GG: энергоэффективная одноадресная топология'''
'''Алгоритм 1. Построение <math>S \Theta\ GG</math>: энергоэффективная одноадресная топология'''


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




'''Алгоритм 2. Построение LS0 GG: планарный остов ограниченной степени с низкими весами'''
'''Алгоритм 2. Построение <math>LS \Theta\ GG</math>: планарный остов ограниченной степени с низкими весами'''


1: Все вершины совокупно составляют граф S&GG в локализованной форме, построенный при помощи алгоритма 1. Каждая вершина помечает инцидентные ей дуги в S&GG как необработанные.
1: Все вершины совокупно составляют граф <math>S \Theta\ GG</math> в локализованной форме, построенный при помощи алгоритма 1. Каждая вершина помечает инцидентные ей дуги в <math>S \Theta\ GG</math> как необработанные.
2: Каждый узел u локально рассылает инцидентные ему дуги в S&GG своим односкачковым соседям при помощи широковещательной трансляции и сам прослушивает своих соседей. Затем каждый узел x исследует существование множества двухскачковых связей ЕгМ., определяемое следующим образом: £гМ = fuv 2 S&GG j u или v 2 NUDG(X)G. Иными словами, ЕгМ представляет собой набор дуг в S&GG, имеющих по меньшей мере одну конечную точку в диапазоне передачи узла x.
2: Каждый узел u локально рассылает инцидентные ему дуги в <math>S \Theta\ GG</math> своим односкачковым соседям при помощи широковещательной трансляции и сам прослушивает своих соседей. Затем каждый узел x исследует существование множества двухскачковых связей ЕгМ., определяемое следующим образом: £гМ = fuv 2 <math>S \Theta\ GG</math> j u или v 2 NUDG(X)G. Иными словами, ЕгМ представляет собой набор дуг в S&GG, имеющих по меньшей мере одну конечную точку в диапазоне передачи узла x.
3: После того, как узел x обнаружит, что необработанная инцидентная ему дуга xy имеет наименьший идентификатор среди всех необработанных связей в E2(x), он удаляет дугу xy в случае, если существует дуга uv € ЕгМ (где u и v отличны от x и y), такая, что kxyk > max(kuvk; 3kuxk; 3kvyk); в противном случае он помечает дугу xy как обработанную. Предположим, что uvyx представляет собой выпуклую оболочку, состоящую из узлов u, v, x и y. Тогда статус связи передается всем соседям при попомщи широковещательного сообщения UPDATESTATUS(XY).
3: После того, как узел x обнаружит, что необработанная инцидентная ему дуга xy имеет наименьший идентификатор среди всех необработанных связей в E2(x), он удаляет дугу xy в случае, если существует дуга uv € ЕгМ (где u и v отличны от x и y), такая, что kxyk > max(kuvk; 3kuxk; 3kvyk); в противном случае он помечает дугу xy как обработанную. Предположим, что uvyx представляет собой выпуклую оболочку, состоящую из узлов u, v, x и y. Тогда статус связи передается всем соседям при попомщи широковещательного сообщения UPDATESTATUS(XY).
4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в E2(u).
4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в E2(u).
5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все дуги. Обозначим за LS&GG финальную структуру, сформированную всеми оставшимися дугами в S&GG.
5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все дуги. Обозначим за <math>LS \Theta\ GG</math> финальную структуру, сформированную всеми оставшимися дугами в <math>S \Theta\ GG</math>.


== Применение ==
== Применение ==
Irina
4446

правок

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

Навигация