4551
правка
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Материал из WEGA
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 16:11, 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> каждому узлу необходимо собрать только информацию в | По сравнению с ранее известными структурами с малыми весами [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] показали, что в общем случае оно неверно. Кроме того, в этой работе показано, что хотя малые логические степени узлов сами по себе не гарантируют малый уровень интерференции, ожидаемая средняя интерференция будет мала, если внимательно выбирать логических соседей по коммуникации. | ||
'''Теорема 6. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые максимальные значения интерференции узлов в структурах EMST, GG, RNG и Yao составляют по меньшей мере | '''Теорема 6. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые максимальные значения интерференции узлов в структурах EMST, GG, RNG и Yao составляют по меньшей мере <math> \Theta\ (log n)</math>.''' | ||
'''Теорема 7. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые средние значения интерференции узлов в структуре EMST ограничены сверху константой.''' | '''Теорема 7. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые средние значения интерференции узлов в структуре EMST ограничены сверху константой.''' | ||
| Строка 65: | Строка 65: | ||
1. Вначале каждый узел самостоятельно строит локальный граф Гэбриэла (GG). Алгоритм построения графа Гэбриэла хорошо известен; одну из возможных реализаций можно найти в [13]. Вначале все узлы помечают себя меткой WHITE, т.е. «необработанные». | 1. Вначале каждый узел самостоятельно строит локальный граф Гэбриэла (GG). Алгоритм построения графа Гэбриэла хорошо известен; одну из возможных реализаций можно найти в [13]. Вначале все узлы помечают себя меткой WHITE, т.е. «необработанные». | ||
2. Если WHITE-узел u имеет наименьший идентификатор среди всех WHITE-соседей в N(u), он использует следующую стратегию выбора соседей: | 2. Если WHITE-узел u имеет наименьший идентификатор среди всех WHITE-соседей в N(u), он использует следующую стратегию выбора соседей: | ||
а) Вначале узел u сортирует всех своих BLACK-соседей в N(u), если таковые имеются, по порядку возрастания расстояния, а затем сортирует всех WHITE-соседей N(u), если таковые имеются, подобным же образом. После этого отсортированные результаты восстанавливаются в N(u); вначале записывается отсортированный список BLACK-соседей, а затем – отсортированный список WHITE-соседей. | а) Вначале узел u сортирует всех своих BLACK-соседей в N(u), если таковые имеются, по порядку возрастания расстояния, а затем сортирует всех WHITE-соседей N(u), если таковые имеются, подобным же образом. После этого отсортированные результаты восстанавливаются в N(u); вначале записывается отсортированный список BLACK-соседей, а затем – отсортированный список WHITE-соседей. | ||
б) Узел u сканирует отсортированный список N(u) слева направо. На каждом шагу он сохраняет в списке текущего указываемого соседа w, но удаляет каждый конфликтующий узел v из оставшейся части списка. «Узел v конфликтует с w» означает, что этот узел v принадлежит к | |||
б) Узел u сканирует отсортированный список N(u) слева направо. На каждом шагу он сохраняет в списке текущего указываемого соседа w, но удаляет каждый конфликтующий узел v из оставшейся части списка. «Узел v конфликтует с w» означает, что этот узел v принадлежит к <math> \theta\ </math>-доминирующей области узла w. Здесь <math>\theta\ = 2 \pi\ / k</math>, где <math>k \ge 9</math> – настраиваемый параметр. | |||
Затем узел u помечает себя меткой BLACK, т.е. «обработанный», и уведомляет каждый удаленный соседний узел v из N(u) при помощи широковещательного сообщения UPDATEN. | Затем узел u помечает себя меткой BLACK, т.е. «обработанный», и уведомляет каждый удаленный соседний узел v из N(u) при помощи широковещательного сообщения UPDATEN. | ||
3. Как только узел v получает сообщение UPDATEN от соседа u из N(v), он проверяет, не находится ли он сам в списке узлов, предназначенных для удаления: обнаружив себя в нем, он удаляет узел-отправитель u из списка N(v), в противном случае помечает u как BLACK в N(v). | 3. Как только узел v получает сообщение UPDATEN от соседа u из N(v), он проверяет, не находится ли он сам в списке узлов, предназначенных для удаления: обнаружив себя в нем, он удаляет узел-отправитель u из списка N(v), в противном случае помечает u как BLACK в N(v). | ||
4. После того, как все узлы будут обработаны, все выбранные ссылки fuvjv 2 N(u); 8v 2 GGg образуют финальную топологию сети, обозначаемую S&GG. Каждый узел может уменьшить диапазон передачи таким образом, чтобы успешно доставать до самого далекого соседа в финальной топологии. | 4. После того, как все узлы будут обработаны, все выбранные ссылки fuvjv 2 N(u); 8v 2 GGg образуют финальную топологию сети, обозначаемую S&GG. Каждый узел может уменьшить диапазон передачи таким образом, чтобы успешно доставать до самого далекого соседа в финальной топологии. | ||
