4551
правка
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 16:50, 19 сентября 2013
, 19 сентября 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 52: | Строка 52: | ||
'''Теорема 5. Предположим, что как идентификатор, так и геометрическое положение узла могут быть представлены при помощи log n битов каждый. Тогда общее число сообщений за время построения структуры <math>LS \Theta\ GG</math> лежит в диапазоне [5n, 13n], при этом каждое сообщение содержит не более O(log n) битов.''' | '''Теорема 5. Предположим, что как идентификатор, так и геометрическое положение узла могут быть представлены при помощи log n битов каждый. Тогда общее число сообщений за время построения структуры <math>LS \Theta\ GG</math> лежит в диапазоне [5n, 13n], при этом каждое сообщение содержит не более O(log n) битов.''' | ||
По сравнению с ранее известными структурами с малыми весами [10, 12] <math>LS \Theta\ GG</math> не только обладает большим числом желаемых свойств, но и требует рассылки намного меньшего числа сообщений во время построения. Для построения <math>LS \Theta\ GG</math> каждому узлу необходимо собрать только информацию в <math>E_2(x)</math>, для чего требуется не более 6n сообщений для n узлов. Алгоритм 2 может применяться к любому известному планарному остову ограниченной степени для того, чтобы превратить его в остов с малыми весами, сохранив при этом все имеющиеся свойства, за исключением коэффициента растяжения, который потенциально может возрасти с <math>\rho\ </math> до <math>2 \rho\ + 1</math>. | По сравнению с ранее известными структурами с малыми весами [10, 12] <math>LS \Theta\ GG</math> не только обладает большим числом желаемых свойств, но и требует рассылки намного меньшего числа сообщений во время построения. Для построения <math>LS \Theta\ GG</math> каждому узлу необходимо собрать только информацию в <math>E_2(x) \; </math>, для чего требуется не более 6n сообщений для n узлов. Алгоритм 2 может применяться к любому известному планарному остову ограниченной степени для того, чтобы превратить его в остов с малыми весами, сохранив при этом все имеющиеся свойства, за исключением коэффициента растяжения, который потенциально может возрасти с <math>\rho\ </math> до <math>2 \rho\ + 1</math>. | ||
Кроме того, ожидаемая средняя интерференция узлов в структуре ограничена константой малой величины. Это само по себе важно по следующей причине: до сих пор утверждение «топология сети с малыми логическими степенями узлов гарантирует малую интерференцию» по умолчанию принималось на веру, и лишь недавно Беркхарт и коллеги [3] показали, что в общем случае оно неверно. Кроме того, в этой работе показано, что хотя малые логические степени узлов сами по себе не гарантируют малый уровень интерференции, ожидаемая средняя интерференция будет мала, если внимательно выбирать логических соседей по коммуникации. | Кроме того, ожидаемая средняя интерференция узлов в структуре ограничена константой малой величины. Это само по себе важно по следующей причине: до сих пор утверждение «топология сети с малыми логическими степенями узлов гарантирует малую интерференцию» по умолчанию принималось на веру, и лишь недавно Беркхарт и коллеги [3] показали, что в общем случае оно неверно. Кроме того, в этой работе показано, что хотя малые логические степени узлов сами по себе не гарантируют малый уровень интерференции, ожидаемая средняя интерференция будет мала, если внимательно выбирать логических соседей по коммуникации. | ||
| Строка 82: | Строка 82: | ||
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 исследует существование множества двухскачковых связей | |||
3: После того, как узел x обнаружит, что необработанная инцидентная ему дуга xy имеет наименьший идентификатор среди всех необработанных связей в E2(x), он удаляет дугу xy в случае, если существует дуга uv € ЕгМ (где u и v отличны от x и y), такая, что kxyk > max(kuvk; 3kuxk; 3kvyk); в противном случае он помечает дугу xy как обработанную. Предположим, что uvyx представляет собой выпуклую оболочку, состоящую из узлов u, v, x и y. Тогда статус связи передается всем соседям при | 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>S \Theta\ GG</math>, имеющих по меньшей мере одну конечную точку в диапазоне передачи узла 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). | |||
4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в E2(u). | 4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в E2(u). | ||
5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все дуги. Обозначим за <math>LS \Theta\ GG</math> финальную структуру, сформированную всеми оставшимися дугами в <math>S \Theta\ GG</math>. | 5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все дуги. Обозначим за <math>LS \Theta\ GG</math> финальную структуру, сформированную всеми оставшимися дугами в <math>S \Theta\ GG</math>. | ||