Способ и устройство группового детерминированного разрешения конфликтов доступа со случайным выбором коммутируемых устройств
METHOD AND DEVICE FOR GROUP DETERMINISTIC CONFLICT RESOLUTION WITH RANDOM SWITCHED DEVICE SELECTION

Изобретение относится к области вычислительной техники и может быть использовано для разрешения конфликтов доступа к приемнику сообщений, поступающих от источников, каждый из которых связан с приемником непосредственно отдельным оптическим беспроводным каналом связи с помощью распределенных средств коммутации, расположенных в каждом источнике.
Разрешение конфликтов доступа - одна из центральных задач вычислительной техники. Ее решение определяется конкретными требованиями со стороны системы, в которой возникают указанные конфликты. Решение зависит как от количества объектов, которые потенциально могут быть источниками сообщений, так и от количества источников, которые одновременно обращаются к приемнику сообщений и создают конфликтную ситуацию.
Известен способ разрешения конфликтов коммутируемых устройств по патенту RU 2538314 С1 (прототип). Известный способ содержит следующие сходные со способом настоящего патента признаки.
(1) Источники и приемники обмениваются сигналами, передаваемыми по беспроводным оптическим каналам, индивидуальным для каждой связи источник - приемник.
(2) Каждому источнику сообщений известно время доставки его сигнала приемнику сообщения. Это время может быть измерено различными способами, в частности в процессе начального размещения в пространстве источников системы.
(3) Одновременно поступающие к приемнику сообщения от нескольких источников посылаются источниками так, чтобы одинаковые по порядку размещения разряды сообщения приходили к приемнику одновременно. Это достигается использованием возможности (2).
(4) Сигналы из (3) объединяются наложением одинаково расположенных в сообщении сигналов, и сформированное так сообщение возвращается ретрорефлектором всем источникам исходных сообщений. При объединении сигнал 1 не может быть искажен. Приемник имеет возможность пропускать или не пропускать отдельные разряды возвращаемого сообщения ко всем источникам (модулировать сигналы сообщения).
(5) Каждый источник обнаруживает наличие конфликта при доступе его к приемнику.
(6) Источники могут посылать сигналы приемникам, используя несколько частот сигналов. Приемник может модулировать возвращаемые источникам сигналы разных частот независимо друг от друга.
(7) Источник должен иметь возможность послать сигнал либо непосредственно приемнику, либо посреднику (ретранслятору), который видим источнику и приемнику. Далее эти конструкции не различаются и для них использован термин «приемник»
(8) Источник, обнаружив конфликт, посылает приемнику единичный сигнал так, чтобы последний поступил в приемник в заданный относительно сигналов других источников момент времени. Это условие означает, что формируется временная шкала, в которой каждому источнику выделен соответствующий ему разряд шкалы.
(9) Приемник возвращает всем источникам полученную им временную шкалу. Каждый источник определяет количество единичных сигналов в разрядах шкалы, предшествующих разряду данного источника. После этого источник, пославший указанный в (8) сигнал, посылает свое сообщение приемнику с задержкой, достаточной для получения приемником сообщений от всех источников, пославших сигналы в разряды шкалы, предшествующие разряду данного источника.
(10) Конфликты устраняются при большом их количестве, вплоть до количества конфликтов, равного количеству разрядов в шкале.
Способ прототипа имеет следующие недостатки. В прототипе каждому источнику в шкале выделяется разряд. Если количество обслуживаемых системой коммутации источников велико настолько, что невозможно или нецелесообразно применять шкалы с требуемым количеством разрядов, то способ должен формировать шкалы с меньшим количеством разрядов, учитывающим права доступа источников к конкретному приемнику, и доставить их соответствующим источникам.
Вторая ситуация, при которой невозможно выделить каждому источнику разряд в шкале, возникает, если источники имеют индивидуальные имена (например, номера устройства, присвоенные каждому источнику его изготовителем) и они неизвестны системе заранее.
Таким образом, есть области применения, в которых способ разрешения конфликта доступа к приемнику, примененный в прототипе, либо существенно усложняет и замедляет процесс разрешения конфликта, либо неосуществим.
Известно устройство, реализующее способ по патенту RU 2538314 С1 (прототип). Известное устройство содержит следующие сходные с устройством настоящего патента признаки. Устройство выполняет все действия способа, приведенные в настоящем патенте, за исключением формирования и использования временной шкалы со случайным количеством разрядов. При этом в прототипе для выполнения всех указанных действий специализированное устройство не создается. Все необходимые действия выполняет процессор источника сообщений наряду с другими действиями по передаче сообщений.
Недостатки устройства:
- отсутствует возможность устранять конфликт в системах с большим количеством коммутируемых устройств;
- низкая скорость разрешения конфликта из-за отсутствия специализированного устройства устранения конфликта.
Задача настоящего изобретения для способа - устранить указанные недостатки способа прототипа, обеспечив при этом детерминированность способа разрешения конфликта.
Задача настоящего изобретения для устройства - устранить указанные недостатки устройства прототипа.
Технический результат для способа разрешения конфликта состоит в том, что он упрощает и ускоряет разрешение конфликта за счет того, что разрядность временной шкалы не связана с количеством источников и их именами, и последние используют случайным образом размещаемые в шкале приемника свои коды приоритета, применяя их в борьбе за право передачи сообщения при конфликте. При этом, несмотря на случайность в формировании шкал, способ гарантирует детерминированное разрешение конфликта при любом количестве участвующих в конфликте устройств.
Технический результат для способа разрешения конфликта достигается тем, что в нем каждый конфликтующий источник сообщения посылает приемнику во временной шкале группу из нулевых и одного единичного сигнала, расположенного в двоичном разряде группы, соответствующем значению старшего разряда кода приоритета источника в борьбе за разрешение конфликта, при этом количество двоичных разрядов в группе равно максимально возможному значению любого разряда кода приоритета, каждый источник случайным способом выбирает группу из разрешенного количества n, а время посылки относительно момента обнаружения конфликта выбирается так, чтобы группы одна за другой в порядке их нумерации поступали в приемник, причем все источники получают от приемника переданную ему последовательность групп сигналов, после чего в каждой группе остаются источники, имеющие наибольшее значение старшего разряда кода приоритета, затем эти источники посылают приемнику шкалу, перемещая в группу сигналов следующий разряд кода приоритета, и т.д. до исчерпания всех разрядов кода приоритета, и единственные оставшиеся в каждой группе источники бесконфликтно передают сообщения.
Технический результат для устройства разрешения конфликта состоит в том, что оно устраняет конфликт в соответствии с предложенным способом, обеспечивая быструю реакцию на действия участвующих в конфликте источников сообщений как при большом количестве источников сообщения системы, так и при большом количестве конфликтующих источников.
Технический результат для устройства разрешения конфликта достигается тем,
что это устройство содержит буфер, индикатор занятости приемника сообщения, анализатор наличия конфликта, блок управления, датчик случайных чисел, при этом буфер соединен с источником сообщения, индикатор занятости приемника сообщения и анализатор наличия конфликта соединены с источником сообщения для получения сигналов приемника, блок управления соединен с датчиком случайных чисел для получения случайного числа, соединен с источником, буфером, индикатором, анализатором для получения соответственно команды разрешения конфликта, сигнала о наличии конфликта, соединен с источником для отправки в источник данных о состоянии действий по разрешению конфликта и порядкового номера момента передачи сообщения источником.
Техническая сущность и принцип действия предложенного устройства поясняются чертежами.
Фиг. 1. Устройство шкалы и группы.
Фиг. 2. Устройство разрешения конфликтов доступа.
Приведенные на чертежах устройства следует рассматривать как примеры технической реализации предлагаемого в патенте устройства.
Краткое описание предлагаемого способа разрешения конфликта. В способе для конкретного источника случайным образом выбирается группа во временной шкале приемника, в которую источник помещает единичный сигнал. Одну и ту же группу может одновременно выбрать несколько источников. Источники, выбравшие одну и ту же группу, проводят между собой борьбу за право передать сообщение. Источники, выигравшие борьбу во всех группах, передают свои сообщения без конфликта одно за другим без временных пробелов между ними.
Краткое описание предлагаемого устройства разрешения конфликта.
Для выполнения действий способа по разрешению конфликта устройство содержит буфер хранения получаемой от источника сообщения управляющей информации, индикатор занятости приемника сообщения, датчик случайных чисел, анализатор конфликта, а также блок управления, управляющий перечисленными устройствами и взаимодействующий с источником сообщения для обеспечения разрешения конфликта.
Подробное описание предлагаемого способа.
Исходные данные для способа. Как в прототипе считаются реализованными перечисленные выше возможности 1-10.
Источник и приемник обмениваются оптическими сигналами по беспроводному каналу, как в прототипе. Сигналы имеют двоичные значения 1 и 0, которые могут быть представлены для сигнала 1 присутствием сигнала, для сигнала 0 отсутствием сигнала; двоичные значения могут быть также представлены парами сигналов - 10 для значения 1 и 01 для значения 0; разными частотами для сигналов 1 и 0; различной поляризацией сигналов 1 и 0. Как в прототипе, ретрорефлектор приемника, получив сигналы из каналов, объединяет их и полученный общий сигнал одновременно посылает всем источникам полученных сигналов.
Все источники передают сообщения одинаковой длины, как это сделано в прототипе.
Источники и приемник обнаруживают конфликт идентично действиям прототипа.
1
n
1
В способе применяется показанная на фиг. 1 шкала, начинающаяся с метки шкалы F, после которой располагается последовательность групп G, …, G, имеющих одинаковое количество p двоичных разрядов. Разряд, соответствующий значению содержащегося в группе значения p-ичного разряда кода приоритета, равен единице, остальные - нули. На фиг. 1 группа G содержит значение, равное 3 (на фиг. нумерация разрядов в группе справа налево, начиная от метки F).
Для передачи сообщений, относительно которых неизвестно, находятся ли они в конфликте, и для сообщений, для которых конфликт обнаружен, используются сигналы разных частот.
1
2
3
4
Сигналы первого вида сообщений источник передает приемнику на частоте f и получает сигналы, возвращаемые приемником, на частоте f. Для второго вида сообщений этим сигналам соответствуют f и f.
2
4
1
3
2
4
Для того, чтобы проверить занят приемник приемом сообщения другого источника или нет, источник посылает приемнику непрерывный сигнал частоты f (f) и проверяет, модулирует или нет этот сигнал приемник. Сообщение источник посылает сигналами f (f), которыми приемник модулирует возвращаемые всем коммутируемым устройствам сигналы f (f) соответственно.
i
max
i
i
max
i
Источник отсчитывает интервал времени *T=T-T, где T - интервал времени, требуемый, чтобы сигнал источника достиг приемника, T≥T для всех i. Это соотношение обосновано в прототипе.
На основе этих исходных данных источники разрешают конфликт указанным ниже способом.
Способ разрешения конфликта.
Шаг 1. Источнику известна показанная на фиг. 1 организация временной шкалы. Источник случайным способом выбирает группу из разрешенного количества n и помещает в нее старший разряд своего кода приоритета. Как указано выше, код каждого разряда кода приоритета представлен единичным сигналом в k-том двоичном разряде группы, если значение разряда равно k, и остальными разрядами, представленными нулевыми сигналами. Коды приоритета всех источников различны. В частности кодами приоритета могут быть адреса источников.
Все приведенные операции источник выполняет до посылки сообщения приемнику.
2
Шаг 2. Перед посылкой сообщения приемнику источник посылает приемнику непрерывный сигнал f и начинает следить за этим сигналом, возвращаемым приемником.
2
1
2
Если источник обнаруживает, что приемник не модулирует сигнал f, то это означает, что в приемник не поступает сообщение другого источника. При этом источник передает приемнику свое сообщение сигналами f и для обнаружения конфликта следит за этим сообщением, возвращаемым приемником сигналами f. При обнаружении конфликта источник переходит к шагу 3. Иначе он бесконфликтно завершает передачу сообщения.
Комментарий к шагу 2. В шаге 2, если источник обнаруживает конфликт при передаче сообщения, он прекращает передачу и переходит к шагу 3. Однако при высокой скорости передачи и достаточно большом расстоянии между источником и приемником конфликт может быть обнаружен после завершения передачи сообщения. Чтобы в этом случае можно было обнаружить конфликт, требуется каждое сообщение начинать с индивидуального имени сообщения. Сообщение может быть разрушено настолько, что источник не сможет опознать его имя. Однако источнику известно время ожидаемого возврата сообщения, и невозможность в это время обнаружить имя сообщения - признак конфликта.
3
4
1
2
4
Шаг 3. Источник переходит к использованию частот f и f, освобождая канал с частотами f и f. Перед посылкой сообщения приемнику источник посылает приемнику непрерывный сигнал f и начинает следить за этим сигналом, возвращаемым приемником.
4
max
Источник ожидает отсутствия модуляции своего сигнала f приемником в течение интервала времени > 3T, достаточного для завершения текущего устранения конфликта. После этого момента любой источник может послать сообщение, не нарушая это устранение.
3
4
Источник передает приемнику сообщение сигналами f и для обнаружения конфликта следит за этим сообщением, возвращаемым приемником сигналами f. При отсутствии конфликта источник завершает передачу сообщения. Иначе он переходит к шагу 4.
max
max
max
max
max
Комментарий к шагу 3. Следует объяснить выбор значения 3T. Рассмотрим обнаружение конфликта. Если конфликт возник в приемнике, то через интервал времени Tо нем будет известно наиболее удаленному от приемника источнику. Источник начнет процесс устранения конфликта (шаг 4) и первый сигнал этого процесса достигнет приемника через интервал T, еще через T сигналы разрешения конфликта достигнут наиболее удаленного источника, и пауза исчезнет. Далее в процессе устранения конфликта не будет длительного отсутствия сигналов. Рассмотрим теперь завершение устранения конфликта. В худшем случае последним передаст сообщение в последовательности сообщений, устраняющих конфликт, наиболее удаленный источник, возникнет пауза, которую обнаружит любой источник за время не более 2T.
max
Таким образом, пауза 3T достаточна для того, чтобы обнаружить отсутствие устранения конфликта.
Шаг. 4. Источник посылает приемнику метку начала шкалы F, подготовленные на шаге 1 для шкалы данные и получает возвращенную приемником шкалу. Момент начала передачи шкалы, как в прототипе, выбирается так, чтобы сигналы от всех источников на входе в приемник образовали единую временную шкалу, в которой любой сигнал источника занимает тот же разряд, который выбрал источник.
i
i
Для начала передачи шкалы источник с номером i, обнаружив конфликт, отсчитывает интервал времени *T. Для передачи в разряд выбранной источником группы сигналов, который соответствует значению разряда кода приоритета, к *T добавляется необходимая временная задержка.
После этого источник следующим способом анализирует возвращенную приемником группу. Пусть в группе старшая позиция, занятая единичным сигналом, равна k. Все источники, выбравшие эту группу и имеющие значение старшего разряда кода приоритета < k, прекращают участвовать в устранении конфликта и отказываются от передачи своего сообщения. Остальные источники переходят к шагу 5.
Шаг 5. Источник посылает приемнику шкалу, как на шаге 4, но помещает в группу следующий разряд кода приоритета. Победитель выполняет аналогичные действия с этим разрядом и т.д. до исчерпания всех разрядов кода приоритета, после чего единственный оставшийся в группе источник - победитель переходит к шагу 6.
На шагах 4 или 5 каждый источник, наблюдая за борьбой, определяет, в каких группах ведется борьба, игнорируя группы, расположенные дальше от метки F, чем группа данного источника. Если код приоритета содержит единственный разряд, то шаг 5 отсутствует.
Шаг 6. Все источники, победившие в своих группах, передают сообщения одно за другим как единое сообщение без пауз между сообщениями, игнорируя те группы, которые в борьбе за разрешение конфликта не участвовали.
После выполнения шага 5 текущий конфликт доступа устранен.
Модификации способа разрешения конфликта доступа.
3
4
1
2
Вариант 1: упрощение реализации способа. В способе исключается шаг 2. После шага 1 выполняется шаг 3, в описании которого исключается фраза «Источник переходит к использованию частот f и f, освобождая канал с частотами f и f». В результате модификации упрощается техническая реализация способа, но отсутствует возможность быстро передать не конфликтующее сообщение.
Вариант 2: обмен сообщениями переменной длины. На шаге 2 передается сообщение переменной длины, ограниченной только общесистемным соглашением.
На шаге 3 после возвращения шкалы к источникам вместо последовательности сообщений посылается последовательность коротких указателей. Источник в соответствующий ему указатель помещает длину своего сообщения (количество пакетов фиксированной длины). После возвращения этой последовательности источник с применением описанной выше временной задержки посылает свое сообщение.
Вариант 3: управление ожиданием источником начала передачи сообщения. Для этого в код приоритета добавляются разряды, учитывающие время ожидания передачи сообщения и срочность сообщения, что и позволяет управлять порядком передачи сообщений.
Комментарии к способу разрешения конфликта доступа.
1
2
1
2
2
1
2
2
p
1
2
-11
1. Частным случаем p-ичной группы является двоичная группа, состоящая из одного двоичного разряда. Действия с этой группой не отличаются от приведенных выше, но время разрешения конфликта в системах с высокоскоростной передачей сигналов увеличивается, так как во многих применениях основное время затрачивается на доставку кода разряда приоритета источника приемнику и возврат кода от приемника. Обозначим время разрешения конфликта при двоичных группах через Т, при p-ичных группах через Т, тогда T=logp[(kt+2L/c)/(ktp+2L/c)]T. Здесь k - количество групп, t - длительность сигнала кода приоритета, L - расстояние между источником и приемником, с - скорость передачи сигнала. Это следует из равенств T=(kt+2L/c)logN; Т=(ktp+2L/c)logN. Например, при L=10 м, t=10 сек, р=32, k=10 получаем T=4,79Т.
2. Способ при каждом выполнении гарантированно уменьшает количество конфликтов как при большом количестве коммутируемых устройств, так и при большом количестве участвующих в конфликте источников. После выполнения всех шагов способа бесконфликтно передадут сообщения по одному источнику из каждого разряда шкалы, содержащего единицы.
Подробное описание предлагаемого устройства разрешения конфликта доступа.
Схема устройства и его связи с источником показаны на фиг. 2, на котором:
1 - источник сообщения; 2 - блок управления; 3 - буфер; 4 - индикатор занятости приемника сообщения; 5 - датчик случайных чисел; 6 - анализатор конфликта.
Блоки соединены следующим способом.
Источник 1 имеет канал 7 для передачи в блок 3 кода приоритета количества групп в шкале, количества разрядов в группе шкалы и для передачи команды в блок 2; канал 8 получения сигналов от блока 2; канал 9 передачи сигналов от фотоприемника источника в блоки 4 и 6. Блок управления 2 имеет канал 10 управления сдвигом кода приоритета в блоке 3, канал 11 получения данных из блока 3, канал 12 получения от блока 4 сигнала обнаружения передачи сигналов в приемник сообщений, канал 13 включения блока 5, канал 14 получения случайного числа от блока 5, канал 15 получения сигнала от блока 6 о занятости приемника сообщений.
Блоки взаимодействуют следующим образом.
Источник 1 - это произвольный источник с порядковым номером i, применяющий предлагаемый в патенте способ разрешения конфликта. Он выполняет следующие действия.
i
Источник сообщения 1 загружает в блок 3 код приоритета количество разрядов в группе шкалы приемника, количество групп в шкале (необходимое при формировании случайного числа). В частности, эти параметры могут быть неизменными для системы и задаваться заранее. Источник также загружает в блок 2 значение *T - приведенную в способе задержку начала передачи шкалы и подает в блок 2 команду разрешить конфликт. В ответ на команду от источника блок 2 начинает следить за сигналом, поступающим из блока 4, и передает источнику сигнал, если приемник занят. Появление этого сигнала позволяет источнику отказаться от передачи сообщения приемнику или ожидать его освобождения. Если приемник свободен (или освобождается), то сигнал об этом, полученный источником от блока 2, разрешает источнику передать сообщение. При этом полученные источником от приемника сигналы источник направляет в блок 6 и если последний обнаруживает конфликт, то сигнал блока 6 поступает в блок 2 и последний посылает об этом сигнал источнику.
i
max
i
Получив сигнал от блока 6, блок 2 через указанный в способе интервал времени *T=T-T отправляет через передатчик источника в приемник метку начала шкалы F. Заранее, до получения сигнала от блока 6 блок 2 получает из блока 3 значение старшего разряда кода приоритета источника и значение группы, в которую он должен послать значение старшего разряда. Блок 2 отправляет приемнику через передатчик источника сигнал, соответствующий значению старшего разряда кода приоритета. Место этого сигнала в группе определено в описании способа. Для этого в пределах шкалы блок 2 выбирает группу, порядковый номер которой в шкале равен номеру, полученному блоком 2 от блока 5. В пределах группы блок 2 посылает сигнал в разряд группы, порядковый номер которого в группе равен значению старшего разряда кода приоритета.
Послав приемнику старший разряд кода приоритета, блок 2 переходит к анализу полученного от приемника набора сигналов, посланных в группу блоками 2 других источников. Для этого блок 2 проверяет наличие сигналов в разрядах группы, старших по сравнению с использованным данным блоком 2. При их обнаружении блок 2 прекращает участвовать в разрешении конфликта. Иначе выполняется аналогичная проверка для второго и всех последующих разрядов кода приоритета. Сигналы, соответствующие значениям каждого разряда, посылаются аналогично действиям с первым разрядом кода приоритета так, чтобы подобно первому разряду они попали в выбранную блоком 2 группу в шкале.
Во время описанных действий устройства блок 2 определяет, в каком количестве групп, предшествующих выбранным блоком 5, проводилась борьба.
После успешной проверки всех разрядов кода приоритета блок 2 посылает сигнал источнику, уведомляющий, что источник получил право передачи сообщения, и количество участвовавших в борьбе групп, расположенных ближе к метке F, чем группа данного источника. Получив эту информацию, источник пошлет свое сообщение с задержкой, позволившей передать сообщения всем источникам, использовавшим указанные группы шкалы.
Выше предполагается, что блок 2 устройства - это обычный программируемый контроллер, быстродействие которого достаточно для выполнения шагов способа разрешения конфликта. Если требуется более высокое быстродействие, то в блоке 2 потребуется отказаться от применения программируемых средств, но такие модификации не влияют на сущность изобретения.