Содержание к диссертации
Введение
1 Анализ и исследование характеристик существующих беспроводных ячеистых информационных систем 10
1.1 Принципы построения существующих беспроводных ячеистых информационных систем и управление передачей информации в них 10
1.1.1 Понятие и принцип работы беспроводных информационных систем с ячеистой структурой 10
1.1.2 Классификация беспроводных ячеистых информационных систем 13
1.1.3 Основные характеристики беспроводных ячеистых информационных систем 14
1.2 Пропускная способность как один из основных показателей работы беспроводных ячеистых информационных систем 16
1.3 Надежность передачи данных в беспроводных ячеистых информационных системах 25
1.3.1 Надежность и достоверность передачи данных в беспроводных ячеистых информационных системах 25
1.3.2 Управление ресурсами беспроводных ячеистых информационных систем 27
1.4 Определение направлений исследования диссертационной работы 36
2 Разработка рациональной структуры беспроводной ячеистой информационной системы и математической модели управления её пропусной способностью 38
2.1 Основные характеристики каналов беспроводных ячеистых информационных систем 38
2.2 Определение пропускной способности беспроводной ячеистой информационной системы 41
2.3 Разработка структуры дистанционного управления беспроводной ячеистой информационной системой 50
Выводы по главе 2 57
3 Синтез алгоритмов управления работой беспроводных ячеистых информационных систем 58
3.1 Разработка метода управления возможными вариантами информационного обмена 58
3.2 Разработка алгоритма определения маршрута с минимальным шумом в информационных каналах 62
3.3 Разработка алгоритма определения минимального расстояния между передающим и принимающим узлами в беспроводной ячеистой информационной системе 66
Выводы по главе 3 75
4 Практическая реализация беспроводной ячеистой информационной системы со средством управления и результаты её апробации 76
4.1 Экспериментальные результаты сравнения топологии беспроводных ячеистых информационных систем 76
4.2 Сравнение беспроводной ячеистой информационной системы со средством управления с текущими беспроводными ячеистыми информационными системами по результатам времени передачи информации 78
4.3 Результаты моделирования средних задержек доставки информации в беспроводных ячеистых информационных системах 82
Выводы по главе 4 90
Заключение 91
Список литературы 93
Приложения 99
- Принципы построения существующих беспроводных ячеистых информационных систем и управление передачей информации в них
- Пропускная способность как один из основных показателей работы беспроводных ячеистых информационных систем
- Основные характеристики каналов беспроводных ячеистых информационных систем
- Разработка алгоритма определения маршрута с минимальным шумом в информационных каналах
Введение к работе
Актуальность работы. Научно-технический прогресс в сфере передачи информации движется с огромной скоростью. В настоящее время идет. процесс развития беспроводных технологий. Одной из таких технологий являются беспроводные ячеистые информационные системы (БЯИС).
Основными задачами беспроводных ячеистых информационных систем являются: а) обеспечение управления прямой связью между вершинами сети без базовой станции; б) управление данными БЯИС для обеспечения связи в удаленных и труднодоступных местностях; в) обеспечение управления связью в чрезвычайных ситуациях.
На качество беспроводной связи немалое влияние оказывает пропускная способность и площадь покрытия связью. Поэтому необходимо создать модель управления беспроводной ячеистой информационной системой с высокой пропускной способностью, отвечающую всем современным требованиям.
Разработка методов и алгоритмов управления БЯИС - сложная комплексная задача, требующая согласованного решения ряда вопросов:
- выбора рациональной структуры (определяется состав элементов и звеньев системы, их расположение, способы соединения);
- выбора типа каналов передачи информации между узлами системы и оценки их пропускной способности для обеспечения управления системой;
- распределения аппаратных, информационных и программных ресурсов по звеньям беспроводных каналов; защиты прав пользователей, циркулирующих в системе;
- оптимального использования пропускной способности и расширения площади покрытия связью БЯИС.
Система должна быть проста по структуре, относительно недорога для производства, доступна для потребителей. Целью данной работы является разработка метода дистанционной маршрутизации для управления работой БЯИС с расширением площади покрытия связью и сохранением высокой пропускной способности.
Поставленная цель может быть достигнута при условии решения следующих задач:
- исследовании характеристик БЯИС;
- разработки математической модели пропускной способности информационных каналов;
- разработки рациональной структуры БЯИС с применением дистанционного средства управления (СУ);
разработки метода управления возможными вариантами информационного обмена;
- разработки алгоритма определения маршрута с минимальным шумом в информационных каналах.
Научная новизна работы заключается в разработке метода управления БЯИС, на основе которого предлагается структура БЯИС, улучшающая ее характеристики.
1. Разработана математическая модель управления пропускной способностью информационных каналов.
2. Предложена новая структура БЯИС с повышенной площадью покрытия связью и высокой пропускной способностью на основе разработанной математической модели.
3. Разработан алгоритм определения маршрута с минимальным шумом в информационном канале.
4. Разработан алгоритм определения минимального расстояния между передающим и принимающим узлами в БЯИС.
Практическая ценность работы. Разработанная структура БЯИС на основе управления данными предназначена для развития технологий управления информационным обменом, в том числе с подвижными объектами.
Разработан метод управления возможными вариантами информационного обмена.
Полученные результаты позволяют создать беспроводные системы управления работой оборудования промышленных предприятий.
Реализация и внедрение результатов. Разработанные в диссертации модели, алгоритмы использовались при выполнении научно-исследовательских работ с участием автора диссертации.
Основные результаты диссертационной работы позволяют создать беспроводные системы управления работой оборудования промышленных предприятий
Апробация работы. Работа в целом и ее отдельные результаты докладывались и обсуждались в период с 2005 по 2008 гг.
- на заочной конференции «Инновационные технологии в проектировании»;
- на международном симпозиуме «Надёжность и качество 2008»;
- на научно-технических семинарах кафедры «Конструирование и
технология радиоэлектронных средств» ВлГУ.
Публикации. Основные результаты исследований опубликованы в 3 работах, в числе которых 2 статьи в изданиях из перечня ВАК, а также научно-технических отчетах о применении разработанной структуры БЯИС на базовом предприятии.
На защиту выносятся:
- математическая модель пропускной способности информационных каналов;
- структура БЯИС с применением дистанционного средства управления;
- метод управления обменом данными в БЯИС;
- алгоритм определения маршрута в БЯИС; Структура и объем диссертации. Диссертация состоит из введения, четырех глав и заключения, изложенных на 98 страницах и иллюстрированных 36 рисунками и 9 таблицами, а также списка литературы из 76 наименований и 10 приложений.
В первой главе дается определение, определяются анализ и исследование характеристики существующих беспроводных ячеистых информационных систем, принципы их построения и управление передачей информации в них, рассматривается пропускная способность как один из основных показателей работы БЯИС, надёжность передачи данных и управление ресурсами БЯИС. На основании проведённого анализа определяется практическая необходимость и актуальность решения задач, подлежащих исследованию и разработке.
Вторая глава посвящена вопросам разработки математической модели пропускной способности БЯИС и рациональной структуры управления информационными каналами с учетом их основных характеристик.
В третьей главе выполняется разработка метода управления возможными вариантами передачи информации в БЯИС, алгоритма определения маршрута с минимальным шумом и алгоритма определения минимального расстояния между передающим и принимающим узлами в БЯИС.
В четвертой главе рассматриваются результаты моделирования БЯИС-СУ по основным характеристикам системы при сравнении с текущими БЯИС. Приводятся экспериментальные результаты сравнения топологии БЯИС, сравнение БЯИС-СУ с текущими беспроводными ячеистыми информационными системами по результатам времени передачи информации, результаты моделирования средних задержек доставки информации.
Принципы построения существующих беспроводных ячеистых информационных систем и управление передачей информации в них
Ячеистые информационные системы работают за счет устройств, определяющих взаимное присутствие и договаривающихся друг с другом о создании системы для передачи сообщений. Вместо того, чтобы проходить через контролируемые из центра хабы, данные, которыми обмениваются в ячеистой информационной системе, проходят по многоканальному специализированному пути, причём каждый пункт, или «узел», на этом пути функционирует как маршрутизатор для передачи сообщений на другие ближайшие узлы. Задействованный узел может быть мобильным или фиксированным, проводным или беспроводным [13].
Основным преимуществом ячеистой информационной системы является её специализированный характер: ячеистая информационная система может формироваться между узлами, не требующими инфраструктуры, и зависит исключительно от возможностей каждого отдельного узла соединяться с другим узлом. Так, например, ячеистая система позволит спасательной команде, работающей на месте разлива отравляющих веществ, сформировать собственную систему для обмена информацией [22].
Точно так же ячеистая информационная система, использующая радио или другие технологии беспроводной передачи информации, может быть развернута на местности, на которой отсутствует инфраструктура проводной связи из-за особенностей данной местности или по другим причинам. Если система должна быть подключена к Интернету, такое соединение можно. установить одним дополнительным узлом с соответствующим информационным трафиком. Таким образом, ячеистая информационная система может предоставить слаборазвитым регионам некоторое ограниченное число интернет соединений. Для связи с удаленными районами к БЯИС нужно просто добавлять узлы.
Ячеистые информационные системы отличаются способностью предоставлять множество разнообразных маршрутов для передачи данных, и такая избыточность делает эти системы надежными даже в случае выхода из строя какого-либо узла. Несмотря на то, что в бизнесе представление об избыточности неотделимо от неэффективности, в ячеистых информационных системах ситуация прямо противоположна: 1) узлы сами по себе довольно дешевы; 2) установка -их проста (узел определяется автоматически и задействуется системой); 3) плотная система из беспроводных узлов позволяет осуществлять информационный обмен с использованием более слабых сигналов (Lower powered communication).
Ячеистые информационные системы имеют и другие сферы применения. Датчики могут использовать слабосильные ячеистые"" системы для отправки прямых сообщений на другие устройства в ней или, например,-передавать определенный ответный сигнал в случае обнаружения разлива химических отравляющих веществ.
Поскольку ячеистые информационные системы используют метод распределенного управления и сообщения не должны проходить через центральный узел, системы становятся самонаводящимися. БЯИС могут быть спроектированы на основе трех топологий: плоской БЯИС, иерархической БЯИС и гибридной БЯИС.
Плоская БЯИС сформирована машинами клиента, действующими как управляющий и маршрутизатор. Здесь все узлы находятся на одном уровне. Беспроводные узлы клиента координируют между собой для направления, конфигурации системы, обслуживания и другого прикладного обеспечения. Эта архитектура является самой близкой к беспроводной сети (ad hoc), и это самый простой случай среди трёх архитектур БЯИС. Основное преимущество такой архитектуры - простота; недостатки включают отсутствие масшабируемости системы и высокие требования к ресурсам. Важные проблемы в проектировании плоской БЯИС - метод адресации, направление и обслуживание открытия схем. В плоской ячеистой информационной системе адресация может стать узким местом против масшабируемости.
В иерархической БЯИС есть множественные ряды, или иерархические уровни, в которых узлы клиента системы формируют самый низкий уровень. Эти вершины клиента могут связываться с магистралью БЯИС, которая сформировалась маршрутизаторами БЯИС. В большинстве случаев узлы БЯИС - специализированные узлы, которые формируют магистраль БЯИС. Это означает, что магистральные узлы, возможно, не дают поступать или ограничивают трафик узлов клиента БЯИС. Маршрутизаторы БЯИС поддерживают магистральную информационную систему, в которой могут находиться внешние поверхности раздела к Интернету - точке доступа.
Пропускная способность как один из основных показателей работы беспроводных ячеистых информационных систем
Термин «пропускная способность» в области знаний о компьютерах и сетях соотносится с объёмами данных, которые могут передаваться при имеющемся сетевом информационном обмене или интерфейсе. Самая распространенная оценка пропускной способности - в единицах «бит в секунду» (бит/сек). Само понятие пришло из электроинженерной отрасли, где пропускная способность (bandwidth - дословно переводится как «ширина полосы частот» (диапазона) или «полоса пропускания») представляет собой общее расстояние или область между самым высоким и самым низким сигналами коммуникационного канала (частоты) [10,55]. Пропускная способность не является единственным определяющим фактором при оценке «скорости» передачи информации, как зачастую думают конечные пользователи. Среди других ключевых элементов — производительность информационной системы, задержки, а также выполняемые сетевые приложения могут оказывать свое влияние.
Производители сетевого оборудования проделали большую работу, развивая и углубляя само понятие пропускной способности. Практически каждый знает пропускную способность своего модема или своего широкополосного интернет-соединения. В сущности, пропускная способность представляет собой качество соединения, и очевиден факт, что чем лучше качество соединения, тем более высокой будет производительность. Пропускная способность может соотноситься как с практической, так и с теоретической производительностью, и в данном случае весьма важно отличать одно от другого.
Согласно [43, 48, 49, 51, 52, 55, 60, 64, 67, 73, 75], ёмкость пропускной способности, достижимая для вершин БЯИС, ограничена в одноканальной системе по сравнению с многоканальной системой. Таблица 1 показывает отклонения пропускной способности в струнной топологии.
Из рис. 2 видно, что пропускная способность в системе БЯИС ухудшается при увеличении числа скачков и длины пробега. Существует несколько коэффициентов, влияющих на ухудшение пропускной способности, например: характеристики протокола MAC, подверженность предельно скрытым узловым задачам, непредсказуемый и высокий коэффициент погрешности в беспроводном канале - все эти проблемы возникают именно в одноканальной системе.
Например, как видно из рис. 3, когда узел 1 связывается с узлом 2, особенно когда CSMA/CA основан на протоколе MAC, узлы 2 и 3 не могут приступить к другой передаче. Узел 2 предотвращен от одновременной передачи, поскольку беспроводная поверхность раздела в большинстве БЯИС является полудуплексом, тогда как узел 2 воздерживается от передачи, так как продолжается передача между узлами 1 и 2. Подобный узел способствует ухудшению пропускной способности в БЯИС по переданному пути мультискачка. Например, поток с двумя прыжками между узлами 1 и 3 должен разделить ширину полосы между двумя, и поэтому, из таблицы 1, непрерывная пропускная способность для пути с двумя прыжками составляет только 47 % из пропускной способности единственного скачка. В экспериментальной произвольной одномерной (ID) системе деградация пропускной способности найдена как функция О (1/п), где п - число прыжков, когда длина прыжка - меньше чем пять прыжков, и вне пяти прыжков пропускная способность остается константой, хотя в очень низкой величине.
БЯИС с одноканальным разделом, где 1,2,3,4,5,6 - узлы системы Другая важная проблема в единственном радио БЯИС несправедливость высокой пропускной способности узлов в системе. Ячеистая информационная система показывает высокую справедливость пропускной способности, если все узлы получают равную пропускную способность при подобных ситуациях исходного трафика и груза системы. БЯИС показывает высокую несправедливость пропускной способности среди борющихся потоков трафика, особенно когда протоколы CSMA/CA, основанные на MAC, используются для разрешения. На рис. 3 и 4 показана простая топология в пределах БЯИС, которая служит высокой несправедливости пропускной способности [50, 54, 57, 65].
Два важных свойства связаны с CSMA/CA, основанном на протоколе МАС в системе БЯИС: а) асимметрия информации (рис. 4), б) зависимость узлов от локализации (рис. 5), в) полудуплексный характер системы единственного канала. Из рис. 4 видно, что только получатель трафика из потока Р доступен и передатчику, и получателю потока Q, и поэтому передатчик потока Р не получает информации от канала о продолжающихся передачах на других потоках. С другой стороны, деятельность канала, как известно, является передатчиком потока Q. Эта информационная асимметрия вызывает несправедливое совместное использование полной пропускной способности. Таким образом, среди потоков Р и Q поток Р получает приблизительно 5 % полной пропускной способности по сравнению с 95 % пропускной способности, достигнутой потоком Q. Например, когда узел 1 имеет пакеты, готовые к передаче, после обнаружения холостого информационного канала, он может запустить передачу, посылая «запрос послать» (RTS) пакет в узел 2. В это время, если есть продолжающаяся передача между узлами 3 и 4, узел 2 не отвечает на RTS, оставляя узел 1 отступать по экспоненте и повторять снова. Этот повторный возврат и несколько попыток ретрансляции приводят к достижению низкой пропускной способности для потока Q. С другой стороны, подобная ситуация может случиться с узлом 3 с намного более низкой вероятностью, и это пропорционально уязвимости периода схемы MAC, которой в этом случае является задержка при распространении между узлами 2 и 3.
В то время как информационная асимметрия вызвана отсутствием информации в определенных узлах, чрезмерная информация может также способствовать несправедливости пропускной способности. Например, на рисунке 3 потоки Р и R не имеют информации о любых других потоках в системе, тогда как у потока Q есть информация об обоих других потоках. Поэтому поток Q должен установить его вектор распределения системы (NAV) и воздержаться от передачи всякий раз, когда видит передачу пакетов управления или данных пакетов, принадлежащих потокам Р и R. Это принуждает поток Q ждать незанятый канал, который, по существу, зависит от случая одновременного освобождения обоих потоков Р и Q. В этом случае локализация потока Q находится в таком положении, при котором отмечается наибольшая вероятность, чем у остальной части потоков, и поэтому поток Q получает только 28 % полной пропускной способности по сравнению с 36% пропускной способности, полученными потоками Р и R. Фактически, доля пропускной способности потока Q обратно пропорциональна номеру вероятности соседних потоков для его ширины полосы. Другой эффект этой зависимости от локализации известен как воспринятое столкновение, которое может произойти в потоке Q.
Основные характеристики каналов беспроводных ячеистых информационных систем
Как и во многих других технических областях, в беспроводных системах главным параметром является максимальная скорость передачи данных. Информационные каналы должны обладать следующими характеристиками: - вероятность доставки сообщения; - пропускная способность.
Вероятность доставки сообщения Р зависит от расстояния L, на которое передаются сообщения. На очень маленькие расстояния передавать сообщения нецелесообразно. Вероятность доставки сообщений стремится к нулю при передаче на большие расстояния. Вероятность доставки сообщения целесообразна при оптимальном расстоянии L [71].
Проектирование беспроводных информационных систем связано с прогнозированием предполагаемой нагрузки, поэтому вопрос о нагрузке в узлах и в целом во всей системе является одним из ключевых. Правильный расчет нагрузки делает информационную систему гибкой, готовой к любым неординарным ситуациям. Изучению нагрузки уделяется много внимания, но в большинстве своём это работы по исследованию статистических данных уже работающих систем. Данная информация, безусловно, важна для дальнейшей эксплуатации беспроводной информационной системы, так как позволяет повысить пропускную способность, избавиться от перегрузок или исправить погрешности результатов проектирования.
В настоящее время при расчете нагрузки ориентируются на данные, нормированные в рекомендации Международного союза электросвязи (ITU). Предлагаемое в рекомендации нормирование нагрузки рассматривается с точки зрения вероятности отказа в час наибольшей нагрузки. На практике вероятность потерь составляет, приблизительно, от 3 до 5 % .
Согласно [24, 30, 34, 53, 71], правильный порог вероятности потерь возможно определить только после начала эксплуатации информационной системы, когда нагрузка будет создаваться реально с реальным трафиком, но, тем не менее, предварительные расчеты нагрузки позволят заложить тот фундамент, на котором будет основана вся система.
Вероятность отказа в обслуживании определяется по формуле Эрланга: В этой формуле значение п указывает на число информационных каналов, принадлежащих звену системы связи і — j , где / и j - номера узлов связи; а - безразмерная величина, получившая наименование приведённой плотности потока сообщений, значение этого коэффициента определяется по формуле А а - — , ,а , где X - плотность простейшего потока сообщений (обычно измеряется числом сообщений за час). 1 и 7 - величина, обратная среднему времени tcp обслуживания сообщения. Для правильного решения поставленной задачи размерность времени в указанных показателях должна быть приведена к одинаковым единицам.
Определив значение вероятности отказа для каждого звена системы передачи информации, приступают к анализу возможности доставки сообщения с заданной вероятностью. В системах связи нормируется именно этот показатель. Обычно вероятность обслуживания заявки должна соответствовать значению:
Обнаруживается степень увеличения обеспечения информационного обмена за счет увеличения радиуса передачи: каждая вершина способна поддержать связь с большим количеством вершин на одном прыжке. В дополнение к изменению радиуса передачи имеется дополнительная степень свободы, а именно - вероятность передачи. Изменение радиуса передачи имеет два эффекта на пропускную способность информационных каналов. Во-первых, поскольку каждый узел слышит больше других узлов, есть предположение, что будет соответствующее увеличение количества трафика, полученного в каждом узле. Во-вторых, возможно противодействие этому ухудшению производительности, поскольку радиус передачи увеличивает источник назначения длины пути и будет уменьшен, поскольку каждый скачок осуществляет приближение к адресату. Таким образом, каждое сообщение потребует, чтобы меньше передач достигло его адресата и вызвало меньше загрузки в системе, которая позволяет соответственно поддерживать более высокий уровень трафика.
Очевиден обмен между этими двумя эффектами, но неясно, какой из них будет доминировать. Фактически обнаруживается, что есть оптимальный радиус передачи, который развертывает доступную пропускную способность.
Узлы информационной системы рассматриваются как однородно распространенные в (двухразмерном) пространстве с плотностью X (то есть будет среднее число точек в единичную площадь), и каждый узел имеет вероятность передачи р в кадре. Кадры соответствуют времени передачи самого длинного пакета, используемого в системе. Каждый узел передаёт с тем же самым радиусом г, который определится обеспечением связи (топологией) системы. Любые узлы, находящиеся в пределах круга радиуса / , в состоянии услышать друг друга и передавать.
Матрица трафика однородна, где каждый узел желает связываться со всеми другими на равной основе. Поэтому полагается, что каждый узел эквивалентен, имея тот же самый радиус передачи, вероятность передачи и загрузку трафика. (Здесь предполагается, что эффекты края и неустойчивость трафика из-за маршрутизации имеют незначительное значение).
Обнаруживается ёмкость информационных каналов, которая является максимальной достижимой пропускной способностью, измеренной числом передач в единицу времени, которые могут быть обработаны системой.
Число успешных передач в слоте - критерий пропускной способности, когда узлы связываются со своими соседями. Если, однако, некоторый трафик потребует больше чем одного скачка, то каждая передача вдоль пути считается как содействие пропускной способности. Определяется ht . вероятность связывания произвольного узла / с другими узлами и Н, . вероятность нахождения в диапазоне і других узлов.
Разработка алгоритма определения маршрута с минимальным шумом в информационных каналах
На графе G=(V,U) , v=r называется такая последовательность дуг, при которой конец каждой предыдущей совпадает с началом последующей. Для" неориентированного графа подобную последовательность рёбер называют маршрутом. В дальнейшем рассматриваются неориентированные графы, однако метод определения пути с минимальным шумом легко распространить на ориентированные графы. На рис.21 графе G задана функция D: каждому ребру UJJ, соединяющему вершины щ и vj , поставлено в соответствие некоторое неотрицательное число (мощность шума) Ц : D={ ly}, i,j= 1,2, ...п.
Здесь переменная Xy принимает значение 1 или 0 в зависимости от того, проходит или не проходит путь с минимальным шумом через это ребро.
Рассмотренная задача имеет важное прикладное значение. При конструировании беспроводных ячеистых информационных систем к построению пути с минимальным шумом в графе сводится задача прокладки беспроводного соединения при трассировке.
Аддитивный характер целевой функции (1) позволяет для решения задачи использовать идеи динамического программирования. Принципы оптимальности Бельмана применительно к данной задаче формулируются следующим образом: «Любая часть оптимального пути оптимальна». Этот принцип позволяет заменить вершины одной сложной задачи - определение пути с минимальным шумом между заданными точками - решением совокупности более простых задач - определение простейших путей с минимальным шумом, которые могут быть частью искомого пути. Динамическое программирование выражено в алгоритме Форда [2, 5, 7, 8, 9, 11, 14, 20, 24, 38] посредством метода расстановки пометок над вершинами графа. Пометка і-й вершины представляет собой два числа: Li5 pj. Первое из них - текущее значение целевой функции L, второе - номер предыдущей вершины, через которую проходит оцениваемый путь. Тогда алгоритм можно представить в виде следующей последовательности шагов: 1. Первоначально метки имеют следующие значения: Ьь = 0, для остальных вершин L; = со, (3j = b для всех вершин. 2. Для каждой j- вершины рассматриваются связанные с ней і- вершины. Если выполняется неравенство Lj Lj + ljj , то над j-й вершиной старая пометка стирается и ставится новая пометка: Lj = L; + 1у; (3; = і. 3. Шаг 2 выполняется до тех пор, пока возможны изменения в системе пометок. 4. Совершается обратный ход в схеме алгоритма, в результате которого определяется критический путь. Пометка над вершиной а фа = к) указывает на номер вершины к, которая лежит на искомом пути. Затем пометка Рд укажет номер следующей вершины и т.д., до тех пор пока не дойдем до вершины b (пометка рь = Ь).
Пример определения пути с минимальным шумом на графе. Пусть требуется определить путь с минимальным шумом между вершинами V3 и V5 графа G. Будем считать конечной вершину V5. Значения пометок записаны в двух столбцах таблицы 4, соответствующих нулевому шагу алгоритма. Далее берем по очереди каждую j-ю вершину, рассматриваем каждую смежную с ней і-ю вершину, и если Lj L[ + Ljj , то заменяем пометку над j-й вершиной в соответствии с алгоритмом. В рассматриваемом примере на первом шаге первая вершина достижима из V2 и V3. Однако уменьшить значение L, невозможно. Просмотрев все вершины, получим результат, записанный в таблице 4 в столбцах, соответствующих первому шагу. Затем вновь просматриваются вершины, начиная с первой, и так далее до тех пор, пока возможны изменения в системе пометок. В рассматриваемом примере это состояние достигается на третьем шаге. Алгоритм Форда позволяет определить путь с минимальным шумом до- конечной вершины (V5 в данном примере) от любой из остальных. Мощность шума этих путей получена в столбце L; на последнем шаге. Вершины, через которые проходит путь с минимальным шумом, определяются просмотром столбцов последнего шага таблицы 4. Так, для вершины V3 вторая часть пометки = 6 означает: следует перейти к вершине V6, Рб = 4, переходим к V4; Р4 = 8, переходим к вершине V8, (38 = 5, переходим к конечной вершине V5
Таким образом, дуть с минимальным шумом от вершины V3 к вершине V5 определен: (Уз, Уб, У , Vs, V5), и его суммарный шум 32.
На примере можно заметить, что простейшая стратегия: выбирай на каждом шаге минимальное ребро - определяет путь (V3, Уб, У» , Vs) с суммарным шумом 42, значительно превышающим минимальный.
Разработка алгоритма определения минимального расстояния между передающим и принимающим узлами в беспроводной ячеистой информационной системе
Согласно [24, 36], деревом называется связный граф без циклов. Очевидно, что в дереве любые две вершины связаны единственной цепью. Различаются несколько видов деревьев. 1. Свободные деревья. Деревья являются самым распространенным классом графов, применяемых в программировании. Граф без циклов называется ациклическим, или лесом. Связный ациклический граф называется (свободным) деревом. Если в связном графе G выполняется неравенство q (G) р (G) - 1. Граф G, в котором q (G) = р (G) - 1, называется древовидным. В ациклическом графе G z(G) = 0. Пусть и и v - несмежные вершины графа G, х = (u, v) Е. если граф G + х имеет только один простой цикл, z(G + х) = 1, то граф G называется субциклическим. Связность, ацикличность, древовидность и субцикличность - свойства, характеризующие граф как дерево. 2. Ориентированные, упорядоченные и бинарные деревья.
