4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 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 | '''Теорема 3. Структура <math>LS \Theta\ GG</math> представляет собой планарный остов ограниченной степени, имеющий константный коэффициент растяжения по мощности 2p + 1, где p – коэффициент растяжения по мощности S&GG. Степень узлов ограничена значением k -1, где k > 9 – настраиваемый параметр в S&GG.''' | ||
'''Теорема 4. Структура LS | '''Теорема 4. Структура <math>LS \Theta\ GG</math> имеет малые веса.''' | ||
'''Теорема 5. Предположим, что как идентификатор, так и геометрическое положение узла могут быть представлены при помощи log n битов каждый. Тогда общее число сообщений за время построения структуры LS | '''Теорема 5. Предположим, что как идентификатор, так и геометрическое положение узла могут быть представлены при помощи log n битов каждый. Тогда общее число сообщений за время построения структуры <math>LS \Theta\ GG</math> лежит в диапазоне [5n, 13n], при этом каждое сообщение содержит не более O(log n) битов.''' | ||
По сравнению с ранее известными структурами с малыми весами [10,12] LS | По сравнению с ранее известными структурами с малыми весами [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. Построение | '''Алгоритм 1. Построение <math>S \Theta\ GG</math>: энергоэффективная одноадресная топология''' | ||
1. Вначале каждый узел самостоятельно строит локальный граф Гэбриэла (GG). Алгоритм построения графа Гэбриэла хорошо известен; одну из возможных реализаций можно найти в [13]. Вначале все узлы помечают себя меткой WHITE, т.е. «необработанные». | 1. Вначале каждый узел самостоятельно строит локальный граф Гэбриэла (GG). Алгоритм построения графа Гэбриэла хорошо известен; одну из возможных реализаций можно найти в [13]. Вначале все узлы помечают себя меткой WHITE, т.е. «необработанные». | ||
Строка 73: | Строка 73: | ||
'''Алгоритм 2. Построение | '''Алгоритм 2. Построение <math>LS \Theta\ GG</math>: планарный остов ограниченной степени с низкими весами''' | ||
1: Все вершины совокупно составляют граф S | 1: Все вершины совокупно составляют граф <math>S \Theta\ GG</math> в локализованной форме, построенный при помощи алгоритма 1. Каждая вершина помечает инцидентные ей дуги в <math>S \Theta\ GG</math> как необработанные. | ||
2: Каждый узел u локально рассылает инцидентные ему дуги в S | 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 | 5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все дуги. Обозначим за <math>LS \Theta\ GG</math> финальную структуру, сформированную всеми оставшимися дугами в <math>S \Theta\ GG</math>. | ||
== Применение == | == Применение == |
правка