Бинарные алгоритмы с запросом

Другой широкий класс антиколлизионных алгоритмов во временной области представляет собой детерминистические протоколы, которые для определения уникального номера UID используют бинарный поиск. Эти протоколы классифицируют в зависимости от того, какая информация требуется при передаче сигнала метки. Некоторые алгоритмы требуют, чтобы метки в течение поиска отвечали полным или почти полным номером UID. Другие алгоритмы заставляют считыватель достраивать UID бит за битом, при этом метки просто отвечают при совпадении запроса. Мы остановимся на этом позже, так как ситуация может упрощаться исходя из требований к метке. Многие особенности предложенных методов [73, 75] мы рассмотрим на основе анализа алгоритмов QT (рис.6.4).

отвечающих меток

Tag - Метка, Reader - Считыватель, Resp.- Ответ

По этой схеме считыватель может генерировать две команды поиска: одна - DN, инструктирует метку двигаться по дереву, другая - TG (toggle), инструктирует метку перейти на другую ветвь дерева и двигаться по ней. Если последний идентифицируемый бит был равен 0, команда DN инструктирует метку двигаться дальше по ветви 0. Если последний бит равен 1, считыватель инструктирует метку далее двигаться по ветви 1. Команда перехода TG инструктирует метку перейти на ветвь, которая противоположна значению последнего бита. Если в следующей битовой позиции метка имеют совпадение с 0 или 1, она отвечает подтверждением. В случае несовпадения битовых значений метка перестает отвечать и битовый указатель останавливается на последнем бите, который был удачно идентифицирован.

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

Как отмечалось ранее, если в метке нет совпадения с 0 или 1 в текущей битовой позиции, она прекращает отвечать и битовый указатель останавливается на последнем идентифицированном бите. Кроме того, метка устанавливает флаг, обозначая ошибку. После того, как путь по дереву завершен и одна метка идентифицирована, считыватель может инициировать UP команду. Эта команда предписывает меткам снять флажки и установить их указатели на ближайшие 8 бит, привязанные к полным 64 битам UID. Если на данной ветви дерева метки отсутствуют, может быть инициирована еще одна команда UP. Такой алгоритм называется QT.ds.

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

Моделирование

Результаты моделирования показаны в табл. 6.1.

Таблица 6.1. Результаты моделирования времени, необходимого для считывания различного количества меток в поле считывания.

Данные по алгоритму Supertag получены моделированием CSIR SuperSim. Результаты получены в результате усреднения 10 попыток для различного числа меток, при этом в качестве оптимального выбрано максимальное время. Также в результате моделирования получены данные по алгоритму QT.ds. В каждом случае скорость обмена принималась равной 64 кб/с, а длина идентификационного кода - 64 бит. Несмотря на то, что данные получены посредством небольшой выборки и доверительный интервал велик, приведенные в табл. 6.1 результаты моделирования позволяют оценить основные тенденции при использовании типичных антиколлизионных алгоритмов.