Результат интеллектуальной деятельности: Способ и устройство группового разрешения конфликтов доступа со случайной временной шкалой

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

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

Известен способ разрешения конфликтов коммутируемых устройств по патенту RU 2538314 С1 (прототип). Известный способ содержит следующие сходные со способом настоящего патента признаки.

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

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

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

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

(5) Каждый источник обнаруживает наличие конфликта при доступе его к приемнику.

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

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

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

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

Таким образом, в способе прототипа при наличии конфликта каждому источнику ставится в соответствие разряд во временной шкале.

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

Известно устройство, реализующее способ по патенту RU 2538314 С1 (прототип).

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

Недостатки устройства:

- отсутствует возможность устранять конфликт в системах с большим количеством коммутируемых устройств;

- низкая скорость разрешения конфликта из-за отсутствия специализированного устройства устранения конфликта.

Задача настоящего изобретения для способа - устранить указанные недостатки способа прототипа.

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

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

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

Технический результат для устройства разрешения конфликта заключается в расширении арсенала технических средств, т.е. результат заключается в реализации назначения.

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

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

Фиг. 1. Устройство разрешения конфликтов доступа

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

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

Краткое описание предлагаемого устройства разрешения конфликта.

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

Подробное описание предлагаемого способа.

Исходные данные для способа. Как в прототипе считаются реализованными перечисленные выше возможности 1-9.

Источник и приемник используют оптические сигналы, передаваемые по беспроводному каналу, как в прототипе. Сигналы имеют двоичные значения 1 и 0, которые могут быть представлены для сигнала 1 присутствием сигнала, для сигнала 0 отсутствием сигнала; могут быть представлены парами таких двоичных значений - 10 для значения 1 и 01 для значения 0; разными частотами для сигналов 1 и 0; различной поляризацией сигналов 1 и 0. Как в прототипе, ретрорефлектор приемника, получив сигналы из каналов, объединяет их, и полученный общий сигнал одновременно посылает всем источникам полученных сигналов.

Все источники передают сообщения одинаковой длины, как это сделано в прототипе.

Передаваемая источником шкала начинается с метки начала F. Разряды шкалы, в которые источники не посылают равный единице сигнал, не должны содержать такого сигнала.

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

Для начала передачи шкалы источник с номером i, обнаружив конфликт, отсчитывает интервал времени ^*T_i=T_max-T_i, где T_i - интервал времени, требующийся, чтобы посланный источником сигнал достиг источника, T_max≥T_i для всех i (Это соотношение применяется и обосновано в прототипе).

Способ разрешения конфликта.

Шаг 1 (подготовительный)

Приведенные на этом шаге действия источник выполняет до посылки шкалы приемнику.

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

Источник к полученному им значению ^*T_i добавляет временную задержку, такую, чтобы после посылки источником шкалы единичный сигнал попал в приемнике в выбранный источником разряд шкалы.

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

Шаг 2

Источник в определенные на шаге 1 моменты времени посылает приемнику метку начала шкалы F и подготовленный на шаге 1 единичный разряд шкалы. Приемник возвращает шкалу всем следящим за приемником источникам. Источник, получив от приемника шкалу, переходит к шагу 3.

Шаг 3

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

Комментарий к способу

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

Подробное описание предлагаемого устройства.

Общая схема устройства разрешения конфликта, действующего по предложенному в патенте способу, показана на фиг. 1.

Схема устройства и его связи с источником показаны на фиг. 1, на которой:

1 - источник сообщения; 2 - блок управления; 3 - индикатор занятости приемника сообщения; 4 - датчик случайных чисел; 5 - анализатор наличия конфликта.

Блоки соединены следующим способом.

Источник 1 имеет канал 6 передачи команды в блок 2; канал 7 получения сигналов от блока 2; канал 8 передачи сигналов от фотоприемника источника в блоки 3 и 5. Блок управления 2 имеет канал 9 получения от блока 3 сигнала о занятости приемника сообщения; канал 10 включения блока 4; канал 11 получения случайного числа от блока 4; канал 12 получения сигнала от блока 5 о наличии конфликта.

Блоки взаимодействуют следующим образом.

Источник 1 с номером i выполняет следующие действия. Перед посылкой сообщения источник 1 загружает в блок 2 значение ^*T_i - приведенную в способе задержку начала передачи шкалы, и подает в блок 2 команду разрешать конфликт. В ответ на команду блок 2 начинает следить за сигналом, поступающим из блока 3, и передает источнику сигнал, если приемник занят. Появление этого сигнала позволяет источнику отказаться от передачи сообщения приемнику или ожидать его освобождения. Если приемник свободен, то сигнал об этом, переданный источнику от блока 2, разрешает источнику передать сообщение. При этом полученные источником от приемника сигналы источник направляет в блок 5, и если последний обнаруживает конфликт, то сигнал блока 5 поступает в блок 2 и последний посылает сигнал источнику, информирующий о наличии конфликта.

Получив сигнал от блока 5, блок 2 через указанный в способе интервал времени ^*T_i=T_max-T_i фиксирует момент начала передачи шкалы, используя передатчик источника, отправляет в приемник признак начала шкалы F и со сдвигом относительно этого момента времени, определенном в способе, используя передатчик источника, отправляет в приемник единичный сигнал.

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

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

Блок 2 следит за возвращаемым приемником сообщением своего источника и при обнаружении конфликта посылает об этом сигнал источнику.

Замечание к описанию устройства

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