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

Для поддержки энергоэффективной широковещательной связи [15] локально построенная топология должна обладать свойством [[малые веса|малых весов]]: полная длина линии связи финальной топологии не более чем в константное число раз превышает длину линии в [[минимальное Евклидово остовное дерево|минимальном Евклидовом остовном дереве]] (Euclidean Minimum Spanning Tree, EMST). Некоторые локализованные алгоритмы [10, 12] были применены для построения структур с малыми весами, способных аппроксимировать энергоэфективность EMST по мере роста плотности сети. Однако ни один из них не был достаточно энергоэффективным для одноадресной передачи.

До сих пор все известные алгоритмы управления топологиями не были способны обеспечить энергоэффективные одноадресную и широковещательную передачи в рамках одной и той же структуры. Была поставлена задача проектирования унифицированной топологии, обладающей одновременно свойствами остовности и малых весов. Основной целью разработки алгоритма было решение этой задачи.