Задачи и методы динамического кодирования ОП абонентов

Будем говорить, что кодирование приоритетов абонентов, предполагающее неизменное соответствие кодов приоритетов абонентам в течение всего времени функционирования системы, называется статическим кодированием ОП абонентов ВС. Однако изложенная концепция обслуживания по расписаниям предполагает смену ОП в процессе функционирования системы, а следовательно и смену по расписанию кодов ОП абонентов при реализации децентрализованного кодового управления множественным доступом к ресурсу. Будем говорить, что кодирование ОП абонентов, предполагающее изменение ОП в соответствии с какой-либо заданной очередностью в процессе функционирования системы, называется динамическим кодированием ОП абонентов ВС. Другими словами, статический код с заданными очередностью и моментами времени изменения его при функционировании системы называется динамическим кодом.

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

Очевидно, что динамический код можно рассматривать как конечное множество статических кодов, где каждый из статических кодов ( пусть в динамическом коде их M, ) характеризуется определенной средней скоростью кодирования . С учетом этого, можем ввести понятие средней скорости динамического кода , которая может рассматриваться как математическое ожидание скоростей кодирования применяемых статических кодов с учетом вероятности их появления в динамическом коде, замкнутый граф которого содержит M вершин - моменты времени , , каждая

из M вершин в замкнутом графе динамического кода встречается ровно раз

,

где

, ,

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

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

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

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

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

1. Инвертируется первый (младший) разряд кода приоритета.

2. Инвертируется второй разряд кода приоритета.

3. Инвертируется первый разряд кода приоритета.

4. Если код приоритета содержит два разряда, инвертируется второй разряд, переход к п.п. 1.

5. Инвертируется третий разряд кода приоритета.

6. Выполняются п.п. 1 - п.п. 3 алгоритма.

7. Если код приоритета содержит три разряда, инвертируется третий разряд, переход к п.п. 1.

8. Инвертируется четвертый разряд кода приоритета.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

k-1. Если k разрядов в коде приоритета, инвертируется k разряд, переход к п.п. 1.

k. Инвертируется k-й разряд.

k+1. Выполняются п.п. 1 - п.п k алгоритма.

k+2. Если разрядов в коде приоритета, инвертируется -й разряд, переход к п.п. 1.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Пример графа динамического кода при групповом кодировании для случая представлен на рис. 3.6.

Рассмотрим условия применения альтернативных способов динамического кодирования, с учетом того, что в зависимости от исходного задания входного потока требований ресурса в качестве оптимальных могут быть получены следующие статические коды: равномерный и неравномерный, полный и неполный (поэтапное кодирова­ние/декодирование).

Рис. 3.5

Рис. 3.6

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

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

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

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

Доказательство. Особенностью группового изменения кода является то, что сохраняются исходные группы абонентов, одинаково закодированных по отдельно взятому разряду. Это означает, что сохраняется соотношение длин приоритетов между абонентами в различные моменты времени . В рассматриваемом случае (входной поток требований определен параметром ) важно сохранение соотношения длин между группами абонентов , что здесь и обеспечивается.

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

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

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

Утверждение. Способ группового изменения кода при динамическом кодировании позволяет получить оптимальный динамический код при приоритетном статическом кодировании ОП абонентов.

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

Рассмотрим случай, когда в качестве оптимального выбирается неполный (поэтапное кодирование) код. Для реализации динамического кода в этом случае не может эффективно использоваться ни способ сквозного изменения кодов, ни рассмотренный способ группового изменения кодов приоритетов, т.к. особенностью рассматриваемого статического кода будет следующее - в предположении, что различные абоненты имеют равные вероятности занятия ресурса и поток заявок определяется лишь его интенсивностью, важным становится уже не длина кодов приоритета групп абонентов , а то, сколько абонентов имеют значение «1» в каждом отдельно взятом разряде кода приоритета (или число единиц в каждом кодовом слове). Здесь также должен быть реализован принцип группового кодирования, однако особенность получения динамического кода здесь состоит в том, что групповое кодирование осуществляется и внутри каждой

исходной группы абонентов (в групповом коде, приведенном выше, допускалось сквозное кодирование внутри групп).

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

Рис. 3.7

Рис. 3.8

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

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

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

.

Физический смысл гарантированной скорости динамического кода следующий - задает максимальное число разрядов, по которым должен быть произведен арбитраж при предоставлении прав занять ресурс m-му абоненту, при наличии требований ресурса у всех M абонентов системы. С учетом коэффициентов повторяемости моментов времени в цикле расписания : , , гарантированная скорость динамического кодирования приоритета m-го абонента

.

Метод динамического кодирования с минимальной гарантированной скоростью основывается на следующих утверждениях.

Утверждение. Выполнение условия достигается в том случае, когда , соответственно

.

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

,

.

Утверждение. Условие выполняется в том случае, когда динамический код реализуется по следующему правилу: в любой

момент времени в старшем разряде кода приоритета (именно с него начинается арбитраж требований) только наиболее приоритетного в этот момент времени абонента находится «1», у остальных абонентов системы в этом разряде «0».

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

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

Рис. 3.9

Очевидно, что средняя скорость кодирования при реализации данного способа увеличивается не более чем на 1 (вводится еще один разряд).

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

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

или

.

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

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

В завершение исследования вопросов кодирования приоритетов абонентов ВС сформулируем и докажем весьма важное утверждение.

Утверждение. При реализации в системе ДОСП динамическая смена ОП абонентов ВС по расписанию должна происходить как при занятии ресурса заявкой реального времени, так и при занятии ресурса заявкой оперативного обслуживания (т.е. при занятии ресурса любой заявкой).

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

Реализация передачи прав на занятие ресурса в ЛВС в соответствии с оптимальными кодами ОП рассматривается в следующем разделе.