Load Balanced Short Path Routing in Wireless Networks / Стабильная нагрузка короткой маршрутизации в беспроводных сетях: Глава 1.

I) Введение.
В мобильной ad-hoc сети или сенсорной сети, устройства соединяются с соседними узлами и формируют ad-hoc сеть связи мультитранзитного участка.

Burd0SS 27.10.10 в 18:02

Маршрутизация в такой сети является сложной задачей из-за отсутствия централизованного управления и высокой динамичности.

Burd0SS 27.10.10 в 18:03

Ранние работы были направлены на выявление и сохранение маршрутов, включающих в себя возможность соединения между узлами и, если это возможно, сведение к минимуму количества переходов на пути.

Burd0SS 27.10.10 в 18:04

Одно важное ограничение беспроводной сети заключается в том, что состояние узлов, их характеристики зависят от «запаса» энергии в узле.

Burd0SS 27.10.10 в 18:12

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

Burd0SS 27.10.10 в 18:13

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

Burd0SS 27.10.10 в 18:16

Это весьма загрузит данные узлы, даже если существуют другие возможные пути.

Burd0SS 27.10.10 в 18:13

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

Burd0SS 31.01.11 в 19:06

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

Burd0SS 31.01.11 в 19:06

Кроме того, нецелесообразное использование узлов может препятствовать другим узлам участию в маршрутизации.

Burd0SS 31.01.11 в 19:06

Так как самая большая потеря энергии приходится на передачу пакетов, соизмеряем расход энергии узла полным размером пакетов, переданных узлом.

Burd0SS 31.01.11 в 19:07

В таком случае, маршрутизация при сбалансированной нагрузке рассматривается, как минимизация предельной нагрузки на узлы в сети.

Burd0SS 31.01.11 в 19:07

Идеальный алгоритм должен минимизировать и задержку, и предельную нагрузку одновременно.

Burd0SS 27.10.10 в 18:18

В некоторой степени эти две задачи противоречивы: кратчайшая маршрутизация ограничивает используемые ресурсы, в то время как маршрутизация при сбалансированной нагрузке выравнивает нагрузку, используя все имеющиеся ресурсы.

Burd0SS 31.01.11 в 19:08

Легко на примере показать, что эти две задачи действительно несовместны, то есть

Burd0SS 31.01.11 в 19:14

алгоритм кратчайшей маршрутизации неизбежно создает тяжело загруженные узлы, а оптимальный алгоритм сбалансированной нагрузки непременно использует длинные пути.

Burd0SS 31.01.11 в 19:14

На практике, узлы часто распределяют таким образом, чтобы мы смогли достичь хорошей, пусть и не обязательно лучшей производительности обоих приёмов одновременно.

Burd0SS 31.01.11 в 19:14

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

Burd0SS 31.01.11 в 19:15

Рассматриваемый нами случай - когда узлы находятся в "узкой" полосе шириной не более 0.86

Burd0SS 31.01.11 в 19:15

радиуса связи для каждого узла.

Burd0SS 31.01.11 в 19:17

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

Burd0SS 31.01.11 в 19:18

В таких случаях, маршрутизация может быть реализована в две стадии.

Burd0SS 31.01.11 в 19:18

На первой стадии узлы вычисляют "мета-путь", необходимый для отправки пакета при помощи сообщения о нахождении, и карту сети, которая, как правило, статична и легко доступна.

Burd0SS 31.01.11 в 19:18

На второй стадии, происходит маршрутизация узлов на мета-пути.

Burd0SS 31.01.11 в 19:18

Вся задача сводится к маршрутизации узлов, расположенных в узкой полосе.

Burd0SS 31.01.11 в 19:19

По сравнению с широким использованием кратчайшей маршрутизации в беспроводных сетях, маршрутизации при сбалансированной нагрузке уделяли меньше внимания.

Burd0SS 31.01.11 в 19:20

Это, наверное, не должно слишком сильно удивлять, поскольку баланс нагрузки – процесс наиболее трудоёмкий.

Burd0SS 31.01.11 в 19:20

Например, для кратчайшей маршрутизации этот процесс является задачей NP-сложности вычисления наиболее сбалансированного маршрута, даже в очень простой сети.

Burd0SS 31.01.11 в 19:20

Были разработаны примерные алгоритмы для этой задачи.

Burd0SS 31.01.11 в 19:20

Но ни один из предшествующих алгоритмов не локален, т.е.

Burd0SS 31.01.11 в 19:21

они требуют глобального согласования, и приближенное отношение этих алгоритмов часто носит лишь теоретический интерес.

Burd0SS 31.01.11 в 19:21

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

Burd0SS 31.01.11 в 19:21

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

Burd0SS 31.01.11 в 19:21

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

Burd0SS 31.01.11 в 19:22

Мы покажем, что это действительно так, для полосы шириной не более 0.86 диапазона связи узла.

Burd0SS 31.01.11 в 19:22

Впрочем, даже при переадресации пакета, очевидно, что есть свобода выбора: на какой узел, среди окружающих, передать пакет.

Burd0SS 31.01.11 в 19:23

Если мы желаем достичь кратчайшей маршрутизации, то алгоритм использует соответствующий жадный метод отправки пакета в самый дальний достижимый узел в правой области.

Burd0SS 31.01.11 в 19:23

Однако это может создать тяжело нагруженные узлы.

Burd0SS 31.01.11 в 19:23

С другой стороны, если мы принимаем жадную стратегию отправки пакета к узлу с самой легкой нагрузкой, это может привести к чрезвычайно длинному пути.

Burd0SS 31.01.11 в 19:23

В этой статье мы объединяем жадные стратегии для уменьшения длины пути и уменьшения нагрузки, чтобы достичь постоянного конкурентоспособного отношения.

Burd0SS 31.01.11 в 19:24

Фундаментальная идея наших методов состоит в том, что мы обслуживаем множество ребер для каждого узла, именуемых мостами, которые обеспечивают оперативное продвижение.

Burd0SS 31.01.11 в 19:24

Потом каждый раз узел выбирает "самый легкий" мост, для передачи пакета.

Burd0SS 31.01.11 в 19:24

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

Burd0SS 31.01.11 в 19:24

В дополнении к этому, мосты могут динамически обслуживаться только при использовании локальной информации.

Burd0SS 31.01.11 в 19:25

В особенности, гарантируем следующие свойства нашего алгоритма:

Burd0SS 31.01.11 в 19:25

1) Использует только короткие пути: количество переходов, задействованных в пути, не должно быть в четыре раза больше количества переходов алгоритма кратчайшей маршрутизации.
2) Выравнивает нагрузку: общий максимальный размер пакетов, передаваемых любому узлу, не должен быть в три раза больше оптимального.

Burd0SS 31.01.11 в 19:25

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

Burd0SS 31.01.11 в 19:26

Работает в режиме реального времени: решение маршрутизации пакета зависит только от ранее отправленных пакетов, то есть, от текущего состояния сети.

Burd0SS 31.01.11 в 19:26

то есть, от текущего состояния сети.

Burd0SS 31.01.11 в 19:26

В будущем нет необходимости различать пакеты.

Burd0SS 31.01.11 в 19:27