УДК 621.398  PACS: 84.30.-r

СПОСОБ  УСТРАНЕНИЯ КОНФЛИКТОВ ДОСТУПА

Г. Г. Стецюра

Институт проблем управления им. В.А. Трапезникова РАН, Москва

Получена 25 мая 2012 г.

 

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

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

Abstract. We describe fast access conflicts elimination method for hard real time systems of measuring and control. Optoelectronic means are used.

Keywords: access conflict, hard real time, data exchange synchronization, retroreflector.

 

1. Вступление

Современные измерительные и управляющие системы (ИУС) часто являются сложными, многокомпонентными, включающими распределенные вычислительные средства. При этом ИУС обычно работают в режиме жесткого реального времени (ЖРВ), предъявляющего высокие требования к скорости реакции на возникающие события.

В условиях ЖРВ трудно планировать действия ИУС заранее. Непредсказуемые события требуют незапланированного доступа к различным компонентам системы, что ведет к конфликтам доступа. Для разрешения таких конфликтов желательна разработка быстрого и простого способа, чтобы его можно было реализовать аппаратными средствами.

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

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

Предлагаемый способ разрешения конфликтов доступа ориентирован на системы, компоненты которых распределены на небольшие расстояния ~ 10 м и обмениваются оптическими сигналами на предельно высоких для настоящего времени скоростях ~ 10¹¹ ÷ 10¹² бит/сек.

 Работа УРКД базируется на двух результатах, приведенных в разделе 2.

 

2. Основы предлагаемого способа устранения конфликтов

2.1. Первый результат  изложен в статье [1].  Пусть имеется группа из n объектов, каждый из которых посылает сигналы другим объектам, применяя оптический демультиплексор, состоящий из последовательно соединенных оптических переключателей, направляющих поступающий от предшествующего переключателя луч света в одном из двух возможных для переключателя направлений. Выходящий из демультиплексора луч света направляется в заданное объектом одно из n направлений, где расположены объекты. Cложность такого демультиплексора , так как каналы формируются демультиплексором только  по мере необходимости.

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

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

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

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

2.2. Второй результат изложен в [2]. Здесь группа произвольно расположенных n объектов бесконфликтно обменивается между собой по беспроводным каналам сигналами одинаковой частоты на предельно высокой скорости, не зависящей  от расположения объектов. Для этого использован центр, и каждый объект может определить интервал  времени T_i,  требуемый для прохождения его сигнала до центра и обратно. Каждому объекту известно  ,  .

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

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

 

3. Схема взаимодействия объектов с УРКД

Функции приведенного в разделе 2.2 центра возложим на УРКД, который содержит приемо-передатчик с ретрорефлектором и модулятором отраженных световых лучей. Каждый из n объектов соединен с УРКД любого другого объекта трактом, состоящим из трех беспроводных оптических каналов  f₁,  f₂,  f₃. Тракты создаются по мере необходимости, как показано в разделе 2.1. Каждый канал обеспечивает два пути распространения сигнала – от источника к УРКД (прямые пути) и от УРКД к источнику (обратные пути). Обозначим прямые пути как  f₁₁,  f₂₁,   f₃₁,   обратные как –  f₁₂,  f₂₂,   f₃₂. По трем каналам f₁,  f₂,  f₃ оптические  сигналы передаются на трех частотах f₁,  f₂,  f₃ соответственно. В зависимости от используемого пути сигналы обозначим так же, как эти пути: f₁₁,  f₂₁,  f₃₁ и  f₁₂,  f₂₂,  f₃₂.

По путям  f₁₁ объекты посылают в УРКД импульсные сигналы для определения удаленности объектов от УРКД. При неподвижных объектах и неизменности условий прохождения сигналов эти измерения могут быть выполнены заранее. По пути f₂₁ объект, которому УРКД предоставит право передачи сообщения, передает двоичные сигналы сообщения. По пути  f₃₁ объекты посылают непрерывные сигналы  f₃₁. УРКД принимает сигналы  f₂₁ и при появлении каждого приходящего импульсного сигнала с помощью модулятора прерывает непрерывные сигналы  f₃₂ – возвращаемые ретрорефлектором сигналы f₃₁ источников. В результате все объекты получат передаваемое по пути  f₂₁ сообщение. УРКД может также модулировать  f₃₂ собственными сигналами и сигналами объекта-приемника.

Для обмена информацией используются импульсные сигналы трех длительностей ν, σ, t, которые связаны соотношением ν < σ < t.  Ниже они указываются перед именем сигнала.

При подаче управляющего электрического сигнала модулятор в УРКД одновременно модулирует все сигналы  f₃₂ и только их.

 

4. Решение задачи устранения конфликтов доступа

Объекты взаимодействуют с УРКД, как указано в разделе 3. Для устранения конфликтов применен приведенный ниже алгоритм.

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

– Каждый объект – участник обмена сообщениями посылает в УРКД приемника непрерывный сигнал f₃₁, возвращаемый объектам как сигнал f₃₂.

– Каждый объект-источник сообщения посылает в УРКД импульсный сигнал  f₁₁. Ретрорефлектор УРКД возвращает этот сигнал источнику в виде сигнала f₁₂, который источник использует для измерения интервала времени прохождения сигнала от объекта до УРКД (раздел 2.2 статьи). Длительность сигнала f₁₁ не регламентируется.

– Синхронизация передачи сообщений источников выполняется в соответствии с разделом 2.1. Для этого УРКД приемника модулирует сигналы f₃₂ кодами или сигналами, разрешающими источникам передачу. Модуляция возможна при отсутствии в УРКД  сигнала νf₂₁. Если приемник обнаруживает конфликт, то его УРКД выполняет следующий алгоритм разрешения конфликта доступа.

 

 Алгоритм

1. Если объект-приемник обнаруживает конфликт, то он прерывает одновременно все возвращаемые источникам с помощью УРКД сигналы  f₃₂ одиночным синхроимпульсом tf₃₂. Этот сигнал все объекты воспринимают как начало процесса устранения конфликта.

2. Получив синхроимпульс tf₃₂, каждый объект, которому требуется передать сообщение в УРКД, посылает в УРКД импульс νf₂₁ с задержкой kν, где k – порядковый номер объекта. Источники действуют, как указано в разделе 2.3 и в результате все объекты создадут единое сообщение S1 длительностью nν, содержащее импульсы νf₂₁ в количестве, равном количеству запрашивающих доступ объектов. Здесь n – максимально возможное количество объектов, которым может потребоваться доступ к  УРКД, ν – длительность сигнала сообщения.

Получая в сообщения S1 сигналы νf₂₁, УРКД ретранслирует их всем объектам, прерывая сигналы f₃₂ каждым сигналом νf₂₁. Этим УРКД создает сообщение S2. Приемник или его УРКД, обнаружив завершение сообщения S1, посылает сигнал σ f₃₂, прерывая f₃₂, как при посылке сигнала tf₃₂.

3. Получив S2, каждый объект формирует сообщение С_i, в котором объект указывает размер будущего сообщения в пакетах – сообщениях фиксированного объема.

Так как в S2 отмечены только объекты, запрашивающие доступ в текущий момент времени, то, анализируя S2, объекты создадут новую, возможно сокращенную нумерацию порядка передачи С_i.

4. В ответ на синхросигнал σ f₃₂ объекты сигналами f₂₁ посылают в УРКД сообщение S3, состоящее из созданных в п. 3 сообщений С_i, одинаковой длительности, с временным сдвигом, соответствующим порядковому номеру передачи С_i. Эти сообщения УРКД также ретранслирует объектам, прерывая f₃₂.

5. Как и на шаге 2 приемник, обнаружив завершение передачи сообщения S3, содержащего все С_i, посылает сигнал σ f₃₂.

6. В ответ на сигнал σf₃₂ объекты посылают, используя f₂₁, свои сообщения приемнику с временным сдвигом, соответствующим порядковому номеру передачи. В результате в УРКД поступит состоящее из этих сообщений общее сообщение S4, длительность которого также не зависит от расположения объектов. УРКД направляет S4 своему объекту-приемнику и ретранслирует всем объектам, создавшим S4.

Для сигнализации объектам о завершении устранения конфликта приемник повторно посылает сигнал tf₃₂.

Устранение конфликта завершено.

Шаги 3, 4, 5 алгоритма отсутствует, если каждое сообщение передается одним пакетом.

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

Результаты работ приемник рассылает всем заказчикам, модулируя сигналы  f₃₂.

Рассмотрим некоторые модификации алгоритма.

– Так как сообщение S4 предназначено только объекту-приемнику, связанному с УРКД, то об отсутствии ошибок надо сообщить только источнику, пославшему это сообщение. Поэтому, во-первых, сигналы сообщения S4 можно посылать одновременно, используя разные частоты, во-вторых, для возвращения источнику многочастотных сигналов источнику не нужен модулятор, достаточно применить ретрорефлектор.

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

– Так как размеры S2 и S3 объектам известны, то УРКД  может не посылать сигналы σ f₃₂.

– УРКД можно использовать как канал множественного доступа. В этом случае, как указано выше, сообщения источников УРКД просто рассылает всем объектам.

 

5. Сложные сеансы взаимодействия источников с приемником

Обращение источника запроса к приемнику может состоять из последовательности обменов данными – получив ответ на запрос, источник на его основе может скорректировать следующий запрос и т.д. В этом случае следует гарантировать группе источников, получивших доступ к приемнику, что более поздние запросы других групп источников не поступили к приемнику до завершения взаимодействия с первой группой. Для этого помимо сигнала длительности t, разрешающего любым объектам начинать сеанс взаимодействия, используем дополнительный сигнал ρf₂₁ длительности ρ, разрешающий работу только объектам первой группы. Для длительностей сигналов справедливо .

Имеем иерархию сигналов: сигнал длительности t разрешает любым объектам начать новый сеанс обмена сообщениями; сигнал длительности ρ разрешает начать новый сеанс только объектам из указанной группы; сигнал длительности σ управляет внутренней организацией сеанса обмена в соответствии с алгоритмом.

Как и в основном  варианте алгоритма, УРКД не принимает решения по организации обмена сообщениями – все возложено на инициаторов взаимодействия объектов.

Длительность интерактивных сеансов следует контролировать, так как в системах ЖРВ могут появляться события, реакцию на которые откладывать нельзя. Этот случай легко учесть, указывая  каким-либо способом приоритеты объектов, требующих срочных действий. Например, можно разрешить таким объектам реагировать, как указано, на сигналы длительности ρ и информировать остальные объекты в ретранслируемом УРКД сообщении о появлении срочных заявок на связь.

 

6. О времени разрешения конфликта

Пусть один из источников послал сообщение, которое искажено конфликтующими с ним сообщениями. В худшем случае УРКД  обнаружит конфликт через время , где L – наибольшее расстояние между объектами системы, с – скорость света, – наибольшая длительность сообщений источников. Обнаружив конфликт, УРКД  посылает сигнал tf_32. Источники получат этот сигнал через время , начнут передавать S1, и через интервал времени  получат S2. Сразу после этого будет послано S3, которое источники получат с задержкой . После этого начинается передача сообщения S4 – последовательности индивидуальных сообщений источников. Таким образом, задержка на разрешение конфликта

Для указанных в разделе 1 параметров высокоскоростных систем, для которых в первую очередь предназначен способ, и количестве объектов ~ 1000 имеем:  Такие расходы времени, определяемые   весьма существенны, сокращать их можно введением дополнительных средств близких связей и предварительным тщательным планированием обменов данными, направленным на снижение количества конфликтов. При снижении скорости передачи данных и уменьшении количества объектов системы вклад  в общее время обмена данными существенно уменьшается.

 

7. Заключение

Суммируем особенности предложенного способа устранения конфликта.

– Способ использует полностью децентрализованные средства: УРКД лишь синхронизует действия объектов, все решения по упорядочению запросов децентрализовано принимают объекты.

– Коммутатор в УРКД отсутствует: ретрорефлектор возвращает объектам-источникам ответ приемника.

– УРКД не использует собственную энергию для отправки ответов: используется энергия поступающих от объектов сигналов  f₃₁, которые УРКД превращает в модулированные сигналы  f₃₂.

– Способ позволяет одновременно и непосредственно, без промежуточных звеньев, соединять любые пары объектов. Это, как показано в разделе 2.1, требует незначительного количества аппаратных средств.

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

– УРКД может использоваться как создаваемый в динамике общий канал.

Быстродействующий оптический ретрорефлектор и модулятор, представляющие интерес для рассмотренной задачи устранения конфликта доступа, можно найти в [3]. В обзоре [4] рассмотрена более сложная задача, чем измерение времени распространения сигнала между объектами –  позиционирование подвижных объектов в закрытых помещениях, и показано, что достигается точность лучше 0,1 мм. Такая точность достаточна для проведения требуемых в статье временных измерений в скоростных системах, компоненты которых разнесены на метры и более.

 

Литература

1. Стецюра Г.Г. Уменьшение сложности распределенного полного коммутатора для параллельных систем  обработки данных //АиТ. 2010. №5. С. 147 – 154.

2. Стецюра Г.Г. Синхронизация взаимодействия цифровых устройств с помощью центра ретрансляции сигналов// Автоматика и телемеханика. 2012 г. № 5. С. 111-124.

3. Rabinovich W.S., Goetz P.G., Mahon R. et al. 45-Mbit/s cat’s-eye modulating retroreflectors// Optical Engineering. 2007. V. 46. № 10. P. 1-8.

4. Mautz R., Tilch S., Optical Indoor Positioning Systems// IPIN. Portugal. 2011.