Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 53: | Строка 53: | ||
'''Теорема 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] показали, что в общем случае оно неверно. Кроме того, в этой работе показано, что хотя малые логические степени узлов сами по себе не гарантируют малый уровень интерференции, ожидаемая средняя интерференция будет мала, если внимательно выбирать логических соседей по коммуникации. | ||
'''Теорема 6. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые максимальные значения интерференции узлов в структурах EMST, GG, RNG и Yao составляют по меньшей мере <math> \Theta\ (log n)</math>.''' | '''Теорема 6. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые максимальные значения интерференции узлов в структурах EMST, GG, RNG и Yao составляют по меньшей мере <math> \Theta\ (log n)</math>.''' | ||
'''Теорема 7. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые средние значения интерференции узлов в структуре EMST ограничены сверху константой.''' | '''Теорема 7. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые средние значения интерференции узлов в структуре EMST ограничены сверху константой.''' | ||
Этот результат верен также для узлов, сформированных при помощи равномерного распределения случайной величины. | Этот результат верен также для узлов, сформированных при помощи равномерного распределения случайной величины. |