4431
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→См. также) |
||
(не показано 15 промежуточных версий этого же участника) | |||
Строка 8: | Строка 8: | ||
1. СИЛЬНЫЙ ОСТОВ: [1, 9, 13, 16, 17]. Подграф H называется [[сильный остов|сильным остовом]] графа G, если существует положительная вещественная константа <math>\rho\ </math>, такая, что для любых двух вершин графа потребление энергии на кратчайшем пути в H не более чем в <math>\rho\ </math> раз выше потребления энергии на кратчайшем пути в G. <math>\rho\ </math> называется [[коэффициент растяжения по мощности|коэффициентом растяжения по мощности]] или просто [[коэффициент растяжения|коэффициентом растяжения]]. | 1. СИЛЬНЫЙ ОСТОВ: [1, 9, 13, 16, 17]. Подграф H называется [[сильный остов|сильным остовом]] графа G, если существует положительная вещественная константа <math>\rho\ </math>, такая, что для любых двух вершин графа потребление энергии на кратчайшем пути в H не более чем в <math>\rho\ </math> раз выше потребления энергии на кратчайшем пути в G. <math>\rho\ </math> называется [[коэффициент растяжения по мощности|коэффициентом растяжения по мощности]] или просто [[коэффициент растяжения|коэффициентом растяжения]]. | ||
2. ОГРАНИЧЕННАЯ СТЕПЕНЬ: [1, 9, 11, 13, 16, 17]. Желательно также, чтобы логическая степень узла в построенной топологии была ограничена сверху некоторой небольшой константой. | 2. ОГРАНИЧЕННАЯ СТЕПЕНЬ: [1, 9, 11, 13, 16, 17]. Желательно также, чтобы логическая степень узла в построенной топологии была ограничена сверху некоторой небольшой константой. Структуры с ограниченной логической степенью находят применение в беспроводных сетях, работающих по протоколу Bluetooth, в которых главный узел может одновременно иметь не более семи подчиненных узлов. Структура с логическими узлами невысокой степени сокращает стоимость обновления таблицы маршрутизации при мобильности узлов. Структура с малым значением степени и укороченными связями может значительно повысить общую пропускную способность сети [6]. | ||
3. ПЛАНАРНОСТЬ: [1, 4, 13, 14, 16]. Топология сети в идеале должна быть планарной (что означает, что никакие | 3. ПЛАНАРНОСТЬ: [1, 4, 13, 14, 16]. Топология сети в идеале должна быть планарной (что означает, что никакие два ребра графа не пересекают друг друга), благодаря чему будут корректно и эффективно работать некоторые локализованные алгоритмы маршрутизации – такие как [[жадная маршрутизация по граням]] (Greedy Face Routing, GFG) [2], [[жадная маршрутизация по периметру без контроля состояния]] (Greedy Perimeter Stateless Routing, GPSR) [5], [[адаптивная маршрутизация по граням]] (Adaptive Face Routing, AFR) [7] и [[жадно-адаптивная маршрутизация по граням]] (Greedy Other Adaptive Face Routing, GOAFR) [8]. Если структура маршрутизации основана на топологии планарной сети, эти локализованные протоколы маршрутизации гарантируют доставку сообщения без применения таблицы маршрутизации: каждый промежуточный узел способен сам определить, какому соседнему логическому узлу переслать пакет, используя только локальную информацию и позиции источника и пункта назначения. | ||
Для поддержки энергоэффективной широковещательной связи [15] локально построенная топология должна обладать свойством [[малые веса|малых весов]]: полная длина линии связи финальной топологии не более чем в константное число раз превышает длину линии в [[минимальное Евклидово остовное дерево|минимальном Евклидовом остовном дереве]] (Euclidean Minimum Spanning Tree, EMST). Некоторые локализованные алгоритмы [10, 12] были применены для построения структур с малыми весами, способных аппроксимировать энергоэфективность EMST по мере роста плотности сети. Однако ни один из них не был достаточно энергоэффективным для одноадресной передачи. | Для поддержки энергоэффективной широковещательной связи [15] локально построенная топология должна обладать свойством [[малые веса|малых весов]]: полная длина линии связи финальной топологии не более чем в константное число раз превышает длину линии в [[минимальное Евклидово остовное дерево|минимальном Евклидовом остовном дереве]] (Euclidean Minimum Spanning Tree, EMST). Некоторые локализованные алгоритмы [10, 12] были применены для построения структур с малыми весами, способных аппроксимировать энергоэфективность EMST по мере роста плотности сети. Однако ни один из них не был достаточно энергоэффективным для одноадресной передачи. | ||
До сих пор все известные алгоритмы управления топологиями не были способны обеспечить энергоэффективные одноадресную и широковещательную передачи в рамках одной и той же структуры. Была поставлена задача проектирования унифицированной топологии, обладающей одновременно свойствами остовности и малых весов. Основной целью разработки алгоритма было решение этой задачи. | До сих пор все известные алгоритмы управления топологиями не были способны обеспечить энергоэффективные одноадресную и широковещательную передачи в рамках одной и той же структуры. Была поставлена задача проектирования унифицированной топологии, обладающей одновременно свойствами остовности и малых весов. Основной целью разработки алгоритма было решение этой задачи. | ||
Строка 20: | Строка 21: | ||
Это первый локализованный алгоритм управления топологиями для всех узлов, работающий на базе унифицированной энергоэффективной типологии для одноадресной и широковещательной передачи в децентрализованных беспроводных сетях и сенсорных сетях. В рамках единой структуры гарантируются следующие свойства сети: | Это первый локализованный алгоритм управления топологиями для всех узлов, работающий на базе унифицированной энергоэффективной типологии для одноадресной и широковещательной передачи в децентрализованных беспроводных сетях и сенсорных сетях. В рамках единой структуры гарантируются следующие свойства сети: | ||
1. '''Энергоэффективная одноадресная передача''': пусть даны два любых узла, тогда между ними в структуре существует путь, полные энергозатраты которого не более чем в <math>2 \rho\ + 1</math> раза превышают энергозатраты любого пути, соединяющего их в исходной сети. Здесь <math>\rho\ > 1</math> – некоторая константа, которая будет определена | 1. '''Энергоэффективная одноадресная передача''': пусть даны два любых узла, тогда между ними в структуре существует путь, полные энергозатраты которого не более чем в <math>2 \rho\ + 1</math> раза превышают энергозатраты любого пути, соединяющего их в исходной сети. Здесь <math>\rho\ > 1</math> – некоторая константа, которая будет определена далее в описании алгоритма. Предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до своего соседа v на любом выбранном пути одноадресной передачи. | ||
2. '''Энергоэффективная широковещательная передача''': энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина | 2. '''Энергоэффективная широковещательная передача''': энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина ее ребер не более чем в константное число раз превышает полную длину ребер в минимальном Евклидовом остовном дереве. Для случая широковещательной передачи и в целом любой многоабонентской передачи предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до самого далекого достижимого узла любой выбранной структуры (обычно дерева) при передаче нескольким абонентам. | ||
3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с k – 1 логическими соседями, где <math>k \ge 9</math> – настраиваемый параметр. | 3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с k – 1 логическими соседями, где <math>k \ge 9</math> – настраиваемый параметр. | ||
Строка 28: | Строка 29: | ||
4. '''Ограниченная средняя физическая степень узла''': ожидаемая средняя физическая степень узла не превышает константы малой величины. Здесь физическая степень узла u в структуре H определяется как число узлов внутри диска с центром в u и радиусом <math>max_{uv \in H} \big\| uv \big\| </math>. | 4. '''Ограниченная средняя физическая степень узла''': ожидаемая средняя физическая степень узла не превышает константы малой величины. Здесь физическая степень узла u в структуре H определяется как число узлов внутри диска с центром в u и радиусом <math>max_{uv \in H} \big\| uv \big\| </math>. | ||
5. '''Планарность''': не имеется | 5. '''Планарность''': не имеется ребер, пересекающих друг друга. Свойство планарности позволяет выполнять над этой структурой некоторые локализованные алгоритмы маршрутизации [2, 5, 7, 8], гарантируя доставку пакетов без использования таблицы маршрутизации. | ||
6. '''<math>\Theta\ </math>-разделенные соседи''': направления между двумя логическими соседями любого узла разделены углом не менее <math>\Theta\ </math>, что снижает интерференцию. | 6. '''<math>\Theta\ </math>-разделенные соседи''': направления между любыми двумя логическими соседями любого узла разделены углом не менее <math>\Theta\ </math>, что снижает интерференцию коммуникации. | ||
Это первая известная локализованная стратегия управления топологиями для всех узлов, совместно поддерживающих такую простую структуру с подобными свойствами. Прежде был известен только централизованный алгоритм, представленный в [1]. Первый шаг представляет собой Алгоритм 1, который строит энергоэффективную топологию для одноадресной передачи; затем Алгоритм 2 строит топологию, способную одновременно поддерживать энергоэффективную широковещательную передачу. | Это первая известная локализованная стратегия управления топологиями для всех узлов, совместно поддерживающих такую простую структуру с подобными свойствами. Прежде был известен только централизованный алгоритм, представленный в [1]. Первый шаг представляет собой Алгоритм 1, который строит энергоэффективную топологию для одноадресной передачи; затем Алгоритм 2 строит топологию, способную одновременно поддерживать энергоэффективную широковещательную передачу. | ||
'''Определение 1 ( <math>\Theta\ </math>-доминирующая область)'''. Для каждого соседа v узла u <math>\Theta\ </math>-доминирующей областью v является <math>2 \Theta\ </math>-конус с вершиной в u, осью которого является | '''Определение 1 ( <math>\Theta\ </math>-доминирующая область)'''. Для каждого соседа v узла u <math>\Theta\ </math>-доминирующей областью v является <math>2 \Theta\ </math>-конус с вершиной в u, осью которого является ребро uv. | ||
Пусть <math>N_{UDG}( | Пусть <math>N_{UDG}(u) \;</math> – множество соседей узла u в UDG. Пусть N(u) – множество соседей узла u в финальной топологии, которая была инициализирована как множество соседних узлов в GG. | ||
Алгоритм 1 строит сильный планарный остов степени k–1. | Алгоритм 1 строит сильный планарный остов степени k–1. | ||
'''Лемма 1'''. Граф <math>S \Theta\ GG</math> является связным, если лежащий в его основе граф <math>GG \;</math> является связным. Более того, для любых двух вершин u и v существует путь <math>\{ u, t_1, ... , t_r, v \} \; </math>, соединяющий их, такой, что все его | '''Лемма 1'''. Граф <math>S \Theta\ GG</math> является связным, если лежащий в его основе граф <math>GG \;</math> является связным. Более того, для любых двух вершин u и v существует путь <math>\{ u, t_1, ... , t_r, v \} \; </math>, соединяющий их, такой, что все его ребра имеют длину менее <math>\sqrt{2} \big\| uv \big\| </math>. | ||
'''Теорема 2. Структура <math>S \Theta\ GG</math> состоит из узлов степенью не выше k – 1 и представляет собой сильный планарный остов с <math>\Theta\ </math>-разделенными соседями. Его коэффициент растяжения по мощности не превышает <math>\rho\ = \sqrt{2}^\beta\ / (1 - (2 \sqrt{2} sin \frac{ \pi\ }{k} )^\beta\ )</math>, где <math>k \ge 9</math> – настраиваемый параметр.''' | '''Теорема 2. Структура <math>S \Theta\ GG</math> состоит из узлов степенью не выше k – 1 и представляет собой сильный планарный остов с <math>\Theta\ </math>-разделенными соседями. Его коэффициент растяжения по мощности не превышает <math>\rho\ = \sqrt{2}^\beta\ / (1 - (2 \sqrt{2} sin \frac{ \pi\ }{k} )^\beta\ )</math>, где <math>k \ge 9</math> – настраиваемый параметр.''' | ||
Очевидно, что для двух конечных точек | Очевидно, что для двух конечных точек каждого ребра эта конструкция является согласованной: если ребро uv принадлежит к узлу u, то оно точно также принадлежит и к узлу v. Стоит отметить, что число 3 в критерии <math>\big\| xy \big\| > max( \big\| uv \big\|, 3\big\| ux \big\|, 3\big\| vy \big\|)</math> было выбрано со всей тщательностью. | ||
'''Теорема 3. Структура <math>LS \Theta\ GG</math> представляет собой планарный остов ограниченной степени, имеющий константный коэффициент растяжения по мощности <math>2 \rho\ + 1</math>, где <math>\rho\ </math> – коэффициент растяжения по мощности S | '''Теорема 3. Структура <math>LS \Theta\ GG</math> представляет собой планарный остов ограниченной степени, имеющий константный коэффициент растяжения по мощности <math>2 \rho\ + 1</math>, где <math>\rho\ </math> – коэффициент растяжения по мощности структуры <math>S \Theta\ GG</math>. Степень узлов ограничена значением k - 1, где <math>k \ge 9</math> – настраиваемый параметр в <math>S \Theta\ GG</math>.''' | ||
'''Теорема 4. Структура <math>LS \Theta\ GG</math> имеет малые веса.''' | '''Теорема 4. Структура <math>LS \Theta\ GG</math> имеет малые веса.''' | ||
'''Теорема 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 ограничены сверху константой.''' | ||
Этот результат верен также для узлов, сформированных при помощи равномерного распределения случайной величины. | Этот результат верен также для узлов, сформированных при помощи равномерного распределения случайной величины. | ||
Строка 72: | Строка 76: | ||
а) Вначале узел 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 принадлежит к <math> \theta\ </math>-доминирующей области узла w. Здесь <math>\theta\ = 2 \pi\ / k</math>, где <math>k \ge 9</math> – настраиваемый параметр. | б) Узел 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. | ||
Строка 82: | Строка 86: | ||
'''Алгоритм 2. Построение <math>LS \Theta\ GG</math>: планарный остов ограниченной степени с низкими весами''' | '''Алгоритм 2. Построение <math>LS \Theta\ GG</math>: планарный остов ограниченной степени с низкими весами''' | ||
1: Все вершины совокупно составляют граф <math>S \Theta\ GG</math> в локализованной форме, построенный при помощи алгоритма 1. Каждая вершина помечает инцидентные ей | 1: Все вершины совокупно составляют граф <math>S \Theta\ GG</math> в локализованной форме, построенный при помощи алгоритма 1. Каждая вершина помечает инцидентные ей ребра в <math>S \Theta\ GG</math> как необработанные. | ||
2: Каждый узел u локально рассылает инцидентные ему | 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>E_2 (x) \; </math> представляет собой набор ребер в <math>S \Theta\ GG</math>, имеющих по меньшей мере одну конечную точку в диапазоне передачи узла x. | ||
3: После того, как узел x обнаружит, что | 3: После того, как узел x обнаружит, что необработанное инцидентное ему ребро xy имеет наименьший идентификатор среди всех необработанных связей в <math>E_2 (x) \; </math>, он удаляет ребро xy в случае, если существует ребро <math>uv \in E_2 (x) \; </math> (где u и v отличны от x и y), такая, что <math>\big\| xy \big\| > max( \big\| uv \big\|, 3\big\| ux \big\|, 3\big\| vy \big\|)</math>; в противном случае он помечает ребро xy как обработанное. Предположим, что uvyx представляет собой выпуклую оболочку, состоящую из узлов u, v, x и y. Тогда статус связи передается всем соседям при помощи широковещательного сообщения UPDATESTATUS(XY). | ||
4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в <math>E_2 (u) \; </math>. | 4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в <math>E_2 (u) \; </math>. | ||
5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все | 5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все ребра. Обозначим за <math>LS \Theta\ GG</math> финальную структуру, сформированную всеми оставшимися ребрами в <math>S \Theta\ GG</math>. | ||
== Применение == | == Применение == | ||
Локализованное управление топологией в децентрализованных беспроводных сетях является важнейшим механизмом поддержки связности сети и организации обратной связи для протоколов обмена данными. Большая часть сетевого трафика приходится на одноадресные передачи. Основными задачами являются экономия энергозатрат и повышение производительности работы сети за счет поддержки энергоэффективной типологии локальным образом. Данный алгоритм решает эти задачи за счет выбора относительно малого уровня мощности передачи и числа соседей по коммуникации для каждой вершины, что позволяет снизить уровень интерференции. Протоколы маршрутизации MANET нередко требуют применения широковещательной передачи. К примеру, такие одноадресные протоколы маршрутизации, как [[динамическая маршрутизация от источника]] (Dynamic Source Routing, DSR), [[дистанционно-векторный алгоритм маршрутизации по запросу]] (Ad Hoc On Demand Distance Vector, AODV), [[протокол зонной маршрутизации]] (Zone Routing Protocol, ZRP) и [[протокол географической маршрутизации]] (Location Aided Routing, LAR), используют для прокладки маршрутов широковещательную передачу или какие-либо ее разновидности. Крайне важно использовать в таких сетях энергоэффективные алгоритмы широковещательной передачи, поскольку беспроводные устройства часто работают от аккумуляторов. | Локализованное управление топологией в децентрализованных беспроводных сетях является важнейшим механизмом поддержки связности сети и организации обратной связи для протоколов обмена данными. Большая часть сетевого трафика приходится на одноадресные передачи. Основными задачами являются экономия энергозатрат и повышение производительности работы сети за счет поддержки энергоэффективной типологии локальным образом. Данный алгоритм решает эти задачи за счет выбора относительно малого уровня мощности передачи и числа соседей по коммуникации для каждой вершины, что позволяет снизить уровень интерференции. Протоколы маршрутизации MANET нередко требуют применения широковещательной передачи. К примеру, такие одноадресные протоколы маршрутизации, как [[динамическая маршрутизация от источника]] (Dynamic Source Routing, DSR), [[дистанционно-векторный алгоритм маршрутизации по запросу]] (Ad Hoc On Demand Distance Vector, AODV), [[протокол зонной маршрутизации]] (Zone Routing Protocol, ZRP) и [[протокол географической маршрутизации]] (Location Aided Routing, LAR), используют для прокладки маршрутов широковещательную передачу или какие-либо ее разновидности. Крайне важно использовать в таких сетях энергоэффективные алгоритмы широковещательной передачи, поскольку беспроводные устройства часто работают только от аккумуляторов. | ||
== См. также == | == См. также == | ||
Строка 100: | Строка 104: | ||
* ''[[Геометрические остовы]] | * ''[[Геометрические остовы]] | ||
* ''[[Планарные геометрические остовы]] | * ''[[Планарные геометрические остовы]] | ||
* ''[[ | * ''[[Разреженные остовы графов]] | ||
== Литература == | == Литература == |
правка