суббота, 20 октября 2012 г.

Обнаружение и разруливание коллизий в сети на протоколе UART

Я долго думал над проблемой объединения кучи микроконтроллеров (МК AVR) в общую сеть. Хотелось иметь простой протокол, в идеале - UART. Но он во-первых не умеет разруливать коллизии, и во-вторых вообще-то даже не предусматривает присутствие нескольких устройств на общей шине!
Но нас такими глупостями не испугаешь.
Поскольку UART мне был нужен также "для самых маленьких" МК (вплоть до tiny13), его пришлось программить самому. Ну а раз пишем сами, то и правила устанавливаем свои :)

Описать сеть я мог бы так: один ПК, много МК на общей шине, полный дуплекс, т.е. отдельные линии RxD и TxD, ПК рассылает на всех разом, МК могут инициировать связь с ПК (но не друг с другом). Схема будет под катом.

В итоге был реализован немного расширенный UART-протокол общения с ПК, который вообще-то полностью совместим с generic-UART, имеет обнаружение коллизий, режим пакетной передачи и позволяет иметь на линии сколь угодно много МК, каждый из которых совершенно свободно может передавать данные в сеть, как только пожелает.
Особенности: никаких арбитров, маркеров, "ответов-только-если-спросили" и прочих ограничений. Абсолютная демократия!
То есть посылаешь в сеть широковещательное "Кто тут?!" и получаешь в ответ аккуратные пакеты, содержащие ответ с адресом каждого МК. Никакой каши.
В виде бонуса, каждому МК можно поставить 3 светика, которые будут отражать соответствующие системные флаги "Линия занята", "Коллизия" и "FRAME ERROR".

Как же я этого добился?!

Схема UART-сети

Каждый МК включается линией TxD в сеть через диод, причем катодом к ноге МК, а анодом на общую шину. То есть выдача разных уровней разными МК ничего никому электрически не попалит. Шина подтягивается резистором к питанию, создавая "1" по-умолчанию. Линия RxD просто разводится ко всем МК звездой. Секрет в третьей ноге (назовем ее Busy), которая слушает, что происходит за диодом. Этот прием и позволяет определить коллизию.

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

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

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

Правила просты:
 - в процедуре reset по-умолчанию ставим флаг "BUSY"
 - начинаем передавать пакет, когда флаг не взведен
 - если обнаружили коллизию ставим флаги BUSY, COLLISION, указатель на начало пакета, возвращаемся в очередь, ждем освобождения линии
 - при приеме пакета отслеживаем таймаут после принятия последнего байта, если их принято меньше пяти
Таким образом добиваемся того, что по сети гуляют аккуратные четко выраженные паузами пакеты.

Вся соль в определении коллизии, и алгоритм прост, как все гениальное!
Если за диодом 0, в то время как мы выдаем 1, значит произошла коллизия, т.е. какой то МК передал на линию 0 и перебил наш сигнал. Отмечаем себе этот факт флагом COLLISION и, что критически важно, сразу прекращаем передачу байта. Иначе ближайшим же нулем сами кому-то попортим байт, и тогда чей-то пакет данных до ПК уже будет безвозвратно испорчен.
ПК конечно сравнит CRC и запросит повторную передачу пакета, просто на это будут потрачены ресурсы и время.
Алгоритм настолько удачен, что позволяет не заморачиваться рандомными интервалами выдержек после затишья на линии (все равно есть вероятность, что два МК начнут передавать одновременно), всяческими тайм-слотами, маркерами, арбитражом и прочими сложностями для определения, кому же можно в данный момент говорить.

Алгоритм опробован на сети из 4 МК, просимулирован в Proteus. При запуске все МК одновременно передавали тестовый пакет. Вот какие картины наблюдались:
Здесь показана коллизия при передаче четырьмя МК разных байтов. Как видно, дольше всех держался тот, кто дольше всех держал линию в нуле. Т.е. само содержимое байта определяет, кто отвалится, а кто продолжит передачу. Этим достигается некая случайность выбора "победителя". Трое отвалились, определив коллизию, четвертый спокойно закончил передачу байта.
Здесь осцилограмма попытки одновременной передачи каждым из четырех МК своего тестового пакета. Видны паузы между пакетами, после которых МК пытаются снова передать пакет, но натыкаются на коллизию. В итоге все очень красиво доходит до ПК!
UPD: алгоритм опробован в железе, работает на ура

4 комментария:

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

    ОтветитьУдалить
    Ответы
    1. обратите внимание на фразу в начале статьи
      "Поскольку UART мне был нужен также "для самых маленьких" МК (вплоть до tiny13), его пришлось программить самому".
      UART программный.
      насчет аппаратного была мысль попробовать его вырубать, но эксперимента так и не провел.

      Удалить
  2. Валера, спасибо. Если что обратиться можно?

    ОтветитьУдалить