4551
правка
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Материал из WEGA
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 17:04, 19 сентября 2013
, 19 сентября 2013→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
2. ОГРАНИЧЕННАЯ СТЕПЕНЬ: [1, 9, 11, 13, 16, 17]. Желательно также, чтобы логическая степень узла в построенной топологии была ограничена сверху некоторой небольшой константой. Структуры с ограниченной логической степенью находят применение в беспроводных сетях, работающих по протоколу Bluetooth, в которых главный узел может одновременно иметь не более семи подчиненных узлов. Структура с логическими узлами невысокой степени сокращает стоимость обновления таблицы маршрутизации при мобильности узлов. Структура с малым значением степени и укороченными связями может значительно повысить общую пропускную способность сети [6]. | 2. ОГРАНИЧЕННАЯ СТЕПЕНЬ: [1, 9, 11, 13, 16, 17]. Желательно также, чтобы логическая степень узла в построенной топологии была ограничена сверху некоторой небольшой константой. Структуры с ограниченной логической степенью находят применение в беспроводных сетях, работающих по протоколу Bluetooth, в которых главный узел может одновременно иметь не более семи подчиненных узлов. Структура с логическими узлами невысокой степени сокращает стоимость обновления таблицы маршрутизации при мобильности узлов. Структура с малым значением степени и укороченными связями может значительно повысить общую пропускную способность сети [6]. | ||
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]. Если структура маршрутизации основана на топологии планарной сети, эти локализованные протоколы маршрутизации гарантируют доставку сообщения без применения таблицы маршрутизации: каждый промежуточный узел способен определить, какому соседнему логическому узлу переслать пакет, используя только локальную информацию и позиции источника и пункта назначения. | 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]. Если структура маршрутизации основана на топологии планарной сети, эти локализованные протоколы маршрутизации гарантируют доставку сообщения без применения таблицы маршрутизации: каждый промежуточный узел способен сам определить, какому соседнему логическому узлу переслать пакет, используя только локальную информацию и позиции источника и пункта назначения. | ||
