1035. RFID 충돌 방지 알고리즘 - 알로하 기반 슬롯 트리 검색 알고리즘 다중 태그 식별 물류 유통 바코드 대체 통신망 제어

핵심 인사이트: 마트 계산대에서 바코드를 하나씩 띡! 띡! 찍는 건 조선시대 방식이다. 유니클로 옷가게에선 박스 째로 옷 100벌을 결제기 위에 올려놓으면 1초 만에 "100벌, 200만 원입니다" 하고 계산이 끝난다. 바코드 대신 RFID 스티커(태그)가 붙어있기 때문이다. 그런데 여기서 기적이 일어난다. 무선 리더기가 전파를 "쾅!" 쏘면 박스 안의 100벌의 태그가 동시에 "나 여기 있어!"라고 소리를 지를 텐데, 전파가 공중에서 엉켜서(충돌) 터지지 않고 어떻게 100벌의 가격을 순서대로 귀신같이 분리해서 읽어냈을까? 그 전파 충돌의 아수라장을 정리하는 무선 교통경찰, RFID 충돌 방지 알고리즘이다.

Ⅰ. RFID (Radio Frequency Identification) 시스템의 구조

바코드를 죽이고 물류 혁명을 일으킨 3총사입니다.

  1. 태그 (Tag, 스티커): 건전지도 없는 멍청한 스티커. 리더기가 쏘는 전파의 힘(전자기 유도)에 의해 0.1초 깨어나 자기 일련번호를 반사해 내뱉습니다.
  2. 리더기 (Reader, 안테나 총): 전파를 쏴서 밥(전기)을 먹여주고 데이터를 읽어냅니다.
  3. 호스트 서버: 읽어 들인 일련번호를 데이터베이스에서 찾아 "아, M사이즈 파란색 패딩 3만 원!" 매핑합니다. (1036번 EPCglobal 연계)

Ⅱ. RFID 태그 충돌(Collision)의 대재앙

  • 상자 안의 100개 태그가 리더기의 전파를 맞고 밥을 먹자마자 100개가 0.001초의 오차도 없이 일제히 100개의 주파수 소리를 질러버립니다.
  • 허공에서 100개의 파동이 겹치면서 삐-이-익 하는 노이즈 쓰레기로 변해, 리더기는 100벌 중 단 1벌의 바코드도 해독하지 못합니다.
  • 이를 1초 만에 깔끔하게 줄 세워 1명씩 입을 열게 만드는 것이 안티 콜리전(Anti-Collision, 충돌 방지) 알고리즘입니다.

Ⅲ. 충돌 방지 알고리즘의 2대 산맥 🌟 핵심 기출 🌟

1. 확률적 꼼수: 슬롯 알로하 (Slotted ALOHA) 방식

네트워크 950번 ALOHA의 응용판입니다. "운에 맡기고 주사위 굴려라!"

  • 작동 방식: 리더기가 허공에 10개의 '시간 방(Slot)'을 뿌립니다. "자! 100개의 태그들아! 1번부터 10번 방 중에 랜덤으로 주사위 굴려서 골라 들어가서 소리쳐라!"
  • 충돌: 1번 방에 3개의 태그가 우연히 같이 들어가면 "꽝! 충돌!" ➜ 리더기는 무시.
  • 성공: 우연히 7번 방에 태그가 딱 1개만 들어갔다! ➜ "오! 너 혼자네? 너 아이디 읽었어! 넌 이제 입 닫아(Sleep)!"
  • 반복: 입 닫은 놈을 제외하고, 남은 놈들을 향해 또 주사위를 굴리게 합니다. 몇십 번 반복하면 결국 주사위 운에 의해 100명이 각자 1명씩 혼자 방을 차지하는 순간이 오고, 1초 만에 100개의 식별이 끝납니다. (수학적 확률의 승리)

2. 논리적 추적: 트리(Tree) 검색 방식 🌟

이건 주사위 도박이 아니라, 스무고개 질문으로 범인을 색출하는 완벽한 이진 탐색(Binary Search)입니다.

  • 작동 방식:
    1. 리더기가 묻습니다. "첫 번째 자리가 0인 태그들만 대답해!" ➜ 50개가 "저요!" 충돌.
    2. 리더기: "안 되겠다. 그럼 앞 두 자리가 00인 놈만 대답해!" ➜ 25개가 충돌.
    3. 리더기: "그럼 000인 놈!" ➜ 12개 충돌.
    4. 계속 자릿수를 늘려가며 묻다가, 마침내 "앞 일곱 자리가 0001011인 놈 대답해!" ➜ 딱 1개만 대답합니다. 식별 완료!
  • 결과: 이렇게 스무고개를 계속 반으로 쪼개 내려가며(나뭇가지 Tree 구조), 100개의 고유 번호를 한 놈씩 콕콕 찝어서 멱살 잡고 끌어내는, 도박이 없는 100% 확실한 색출 흑마법입니다.

📢 섹션 요약 비유: 박스 안에 100명의 학생(RFID 태그)이 갇혀 있습니다. 선생님(리더기)이 "이름 불러!"라고 외치자 100명이 동시에 이름을 소리쳐서 교실이 폭발할 뻔했습니다(태그 충돌). 이를 통제하는 알로하(ALOHA) 방식은 선생님이 주사위를 던지게 하는 겁니다. "주사위 던져서 1 나온 사람만 이름 말해!" 3명이 나오면 "너넨 탈락! 주사위 다시!" 하다가 딱 1명만 1이 나오면 "오케이, 홍길동 확인! 넌 엎드려 자!" 이걸 1초에 100번 반복해 전원을 색출합니다. 반면 트리(Tree) 검색 방식은 지독한 스무고개입니다. "성씨가 김씨인 사람? 30명 충돌! 그럼 김씨 중 두 번째 글자가 '민'인 사람? 5명 충돌! 그럼 김민철! 오, 너 하나구나. 통과!" 이렇게 조건을 반씩 계속 좁혀가며 절대 두 명이 겹치지 않는 바늘구멍 질문을 던져 100명을 완벽하게 핀셋으로 한 명씩 골라내 침묵시키는 미친 속도의 출석부 검사 시스템입니다.