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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пока что мы покажем, что можем достичь постоянных пределов с точек зрения, как задержки, так и нагрузки, в случае расположения узлов в узкой полосе; стоит обратить внимание на простой пример (рис.1), который, вообще говоря, неверен, когда узлы располагаются в одной плоскости.

Белая точка содержит m узлов, черная точка o содержит один узел.

Пакеты от p до q проходят через o и сильно его нагружают или же пакеты проходят по длинному маршруту и создают большую задержку.

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

Высокая эффективность нашего алгоритма с таким же успехом подтвердилась результатами моделирования.

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

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

<i>А. Прикрепленные к статье работы.</i>

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

Статья Йосси Азара [2] и Аллана Бородина, книга Рана Эль-Янива [3] содержат превосходный обзор данного предмета.

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

Это уже известная нам задача NP-сложности, которую можно аппроксимировать к O(lg n/lglg n) [4], [5].

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

Другой задачей является постоянно действующая проблема маршрутизации виртуального канала, которая также была широко изучена. [6], [2], [3].

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

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

Протоколы, использующие кратчайшую маршрутизацию, включают в себя алгоритмы маршрутизации с динамическим источником (DSR) [7], протокол динамической маршрутизации для мобильных ad-hoc сетей и других беспроводных сетей, использующий для вычисления маршрутов дистанционно-векторный алгоритм (AODV) [8], и др.

Обращайтесь к обзорам и ссылкам. [9]

C другой стороны, вызывали большой интерес алгоритмы маршрутизации, потребляющие малое количество энергии и пытающиеся увеличить сетевую жизнеспособность, [10-24].

Энергозависимые параметры, такие как "увеличение времени разделения" и "уменьшение максимума узловых затрат" были впервые предложены в работе Singh et al. [15].

Chang et al. [16], [17] использовали алгоритмы увеличения и перераспределения потока в сторону баланса потребления энергии на различных узлах.

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

Подробности этого подхода были рассмотрены в [22], [23].

Li et al. [11] изучили энергосберегающую маршрутизацию в режиме online, уменьшающую начальный момент времени, когда пакет еще не отправлен.

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

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

Xu et al. [24] предложили GAF-алгоритм, разработанный для снижения потребления энергии, выкидывая ненужные узлы.

В ссылках [25], [26] указаны традиционные энергозатратные протоколы маршрутизации такие как: DSR или AODV, они были переработаны, чтобы принять во внимание энергосберегающие параметры.

Все вышеупомянутые протоколы действуют по принципу эвристики и не предоставляют никаких гарантий по эффективности.

Данная статья организована следующим образом.

Во втором разделе будут введены некоторые понятия и обозначения.

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

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

В шестом разделе продемонстрируем результаты нашего моделирования.

Переведено на Нотабеноиде
http://notabenoid.org/book/12083/39018

Переводчики: Burd0SS