!6. Протоколы коллективного и последовательного доступа.

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

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

-Когда данные для передачи есть только у одного узла, этот узел обладает пропускной способностью в R бит/с. -Когда данные для передачи есть у М узлов, каждый из этих узлов обладает пропускной способностью в R/M бит/с. Это не означает, что каждый из М узлов в каждый момент времени может передавать данные со скоростью R/M бит/с, — это средняя скорость передачи данных каждого из узлов. -Протокол является децентрализованным, то есть не существует управляющих узлов, выход из строя которых может остановить работу всей сети. -Протокол прост и дешев в реализации.

CSMA/CD (Carrier Sense Multiple Access with Collision Detection — множественный доступ с контролем несущей и обнаружением коллизий) — технология(802.3) множественного доступа к общей передающей среде в локальной компьютерной сети с контролем коллизий Коллизия (англ. collision — ошибка наложения, столкновения) — в терминологии компьютерных и сетевых технологий, наложение двух и более кадров от станций, пытающихся передать кадр в один и тот же момент времени.

Как уже упоминалось, двумя желательными свойствами протокола коллективного доступа являются, во-первых, возможность единственного активного узла передавать свои данные с максимальной пропускной способностью канала R бит/с, во-вторых, возможность для каждого из М активных узлов передавать свои данные со скоростью R/M бит/с. Протоколы ALOHA и CSMА удовлетворяют первому требованию, но не удовлетворяют второму. Это подвигло исследователей на создание нового класса протоколов — протоколов последовательного доступа. Как и в случае с протоколами произвольного доступа, существуют десятки протоколов последовательного доступа, и у каждого есть множество вариантов. Здесь мы рассмотрим два наиболее важных протокола последовательного

доступа. Первый из них — протокол опроса. При использовании протокола опроса один из узлов должен быть назначен главным (управляющим) узлом. Главный узел поочередно опрашивает все узлы. Например, сначала главный узел посылает сообщение узлу 1, сообщая ему, что он может передать некоторое максимальное количество кадров. После того как узел 1 передает несколько кадров, главный узел разрешает передать некоторое количество кадров узлу 2. (Главный узел может определить момент завершения передачи очередным узлом по отсутствию сигнала в канале.) Данная процедура продолжается бесконечно, при этом главный узел в цикле опрашивает все узлы.

!7. Генетические алгоритмы. Представление генетической информации. Генетические операторы.

Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

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

В задачах поиска оптимальных решений каждое решение из множества возможных можно представить набором информации, который может быть изменен путем введения в него элементов другого решения. Возможные решения соответствуют хромосомам, состоящим из генов, причем в ходе оптимизации происходит обмен генами между хромосомами (рекомбинация). При построении генетических алгоритмов важен выбор принципа генетической рекомбинации. Существует несколько типов перераспределения наследственных факторов: рекомбинация хромосомных и нехромосомных генов; рекомбинация целевых негомологических хромосом; рекомбинация участков хромосом, представленных непрерывными молекулами ДНК.

Оператор отбора (селекции) На этом этапе отбирается оптимальная популяция для дальнейшего размножения. Обычно берут определённое число лучших по приспособленности. Имеет смысл также отбрасывать "клонов", т.е. особей с одинаковым набором генов.

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

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