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

'''Теорема 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>.

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

'''Теорема 6. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые максимальные значения интерференции узлов в структурах EMST, GG, RNG и Yao составляют по меньшей мере <math> \Theta\ (log n)</math>.'''

'''Теорема 7. Для множества узлов, созданных при помощи точечного процесса Пуассона с интенсивностью n, ожидаемые средние значения интерференции узлов в структуре EMST ограничены сверху константой.'''

Этот результат верен также для узлов, сформированных при помощи равномерного распределения случайной величины.