Advanced
Performance Improvement of STAC Protocol by Grouping the Number of Tags
Performance Improvement of STAC Protocol by Grouping the Number of Tags
Journal of the Korea Institute of Information and Communication Engineering. 2015. Apr, 19(4): 807-812
Copyright © 2015, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : January 06, 2015
  • Accepted : February 16, 2015
  • Published : April 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
인택 임
itlim@bufs.ac.kr

Abstract
RFID 시스템에서 리더의 식별영역 내에 있는 태그들이 동시에 응답하면 충돌이 발생한다. 이러한 충돌을 해결하기 위한 방법이 충돌 방지 알고리즘이다. Auto-ID 센터에서는 13.56MHz RFID 시스템에서 다중 태그를 식별하기 위한 충돌 방지 알고리즘으로 STAC 프로토콜을 제안하였다. PS 알고리즘은 리더의 송신 전력을 점진적으로 증가시키면서 리더의 식별 영역 내에 있는 태그들을 그룹화 하여 식별하는 기법이다. 본 논문에서는 STAC 프로토콜에 PS 알고리즘을 적용한 STAC/PS 알고리즘을 제안하고, 이에 대한 성능을 분석한다. 시뮬레이션을 통한 성능분석의 결과, 제안한 기법은 충돌률이 STAC 프로토콜에 비하여 50% 정도 낮으므로 태그 식별 시간이 짧음을 알 수 있었다.
Keywords
Ⅰ. 서 론
RFID 시스템에서 리더는 무선채널을 통하여 태그들과 통신하는데, 모든 태그들은 리더가 보낸 신호를 동시에 듣게 된다. 하나의 리더로부터 요청 메시지를 받은 태그들은 동시에 리더로 자신의 식별코드를 전송하기 때문에 태그 충돌이 발생한다 [1] . 이 때 리더가 동시에 응답한 여러 개의 태그를 식별해야하는 문제가 발생하는데 이를 해결하는 기술이 충돌 방지(Anti-collision) 알고리즘이며, 이는 RFID 시스템에서 가장 핵심이 되는 기술이다. 다중 태그를 식별하기 위한 충돌방지 알고리즘은 크게 확률적 방법과 결정적 방법으로 구분된다. 확률적 방법은 ALOHA 기법을 기반으로 하는 FSA(Frame Slotted ALOHA) 알고리즘을 사용하고 있으며, 이는 EPCglobal Class-1 Gen-2와 ISO/IEC 18000-6 Type C에서 표준으로 채택하고 있다 [2 , 3] . 결정적 방법은 트리 검색 방식을 기반으로 하고 있으며 EPCglobal Class-0와 ISO/IEC 18000-6 Type B에서 표준으로 채택하고 있다 [4] .
RFID 시스템의 태그 식별 성능은 동시에 응답하는 태그들로 인한 태그 충돌 확률과 밀접한 관계가 있다. 태그 충돌 확률을 줄이기 위한 방법으로는 PS(Progressing Scanning) 알고리즘 등이 있다 [5] . 이러한 기법들은 리더의 식별영역 내에 있는 태그들을 그룹화 하여 동시에 응답하는 태그의 수를 제한함으로써 충돌 확률을 줄인다. 이 중에서 PS 알고리즘은 리더의 송신 전력 세기에 따라 리더의 식별영역이 다른 점을 이용한 방법이다. 먼저 리더는 낮은 전력으로 식별을 시작하여 점차 전력을 증가시켜서 식별영역을 확장한다. 이렇게 함으로써 리더와 가까이 있는 태그들은 멀리 있는 태그와 충돌이 발생하지 않기 때문에 식별 성능이 증가된다. 또한 PS 알고리즘에서는 송신 전력을 증가시켜서 새로운 태그 식별 과정을 수행할 때마다 식별영역내에 있는 태그의 수에 관계없이 고정된 크기의 프레임을 사용한다.
Auto-ID 센터에서는 13.56MHz RFID 시스템에 대한 표준안을 제안하였다 [6] . 제안한 시스템에서 리더의 식별영역 내에 있는 태그들을 식별하기 위한 충돌 방지 알고리즘으로 STAC(Slotted Terminating Adaptive Collection) 프로토콜을 사용한다. STAC 프로토콜에서 응답 라운드는 BeginRound 명령으로부터 시작된다. BeginRound 명령을 수신하면 식별되지 않은 태그들은 응답할 자신이 응답할 슬롯 위치를 임의로 선택하여 슬롯-카운터에 적재하고, 슬롯-카운터의 값이 응답 슬롯위치가 되면 자신의 EPC 코드로 응답한다. 수신한 응답에 충돌이 없으면 성공적으로 식별된 경우이므로 리더는 FixSlot 명령을 전송한다. 반면, 응답 슬롯에 충돌이 발생했거나 아무런 응답이 없으면 리더는 CloseSlot 명령을 전송한다. 하나의 응답 라운드가 종료되면 리더는 새로운 응답 라운드를 위하여 BeginRound 명령을 전송한다. STAC 프로토콜인 경우 리더가 식별해야하는 태그의 수가 증가함에 따라 많은 충돌이 발생할 것으로 예상된다. 따라서 본 논문에서는 STAC 프로토콜에 PS 알고리즘을 적용하여 리더는 낮은 전력에서 시작하여 점차 전력을 증가시켜서 식별 영역을 확장하는 STAC/PS (STAC with PS) 알고리즘을 제안하고, 이에 대한 성능을 분석한다.
본 논문의 구성은 다음과 같다. II장에서는 기존의 STAC 프로토콜과 PS 알고리즘의 동작을 기술하고, III장에서는 본 논문에서 제안하는 STAC/PS 알고리즘을 설명한다. IV장에서는 제안한 기법의 시뮬레이션 결과를 기술하고, 마지막으로 V장에서는 결론을 맺는다.
Ⅱ. 관련 연구
- 2.1. STAC 프로토콜
STAC 프로토콜에서 태그를 식별하기 위한 응답 라운드는 BeginRound 명령으로부터 시작된다. 그림 1 은 STAC 프로토콜에서 하나의 응답 라운드 구조를 나타낸 것으로, 한 라운드 동안 응답 슬롯의 개수는 리더에 의해서 제어된다. 응답 라운드가 시작되면 태그는 하나의 응답 라운드에 있는 임의의 슬롯을 선택하여 응답한다 [7] .
PPT Slide
Lager Image
STAC 프로토콜의 응답 라운드 구조 Fig. 1 Structure of reply round in STAC protocol
STAC 프로토콜에서 리더는 식별영역 내에 있는 태그들을 식별하기 위하여 응답 라운드의 시작을 알리는 BeginRound 명령을 전송한다. BeginRound 명령을 수신한 태그들은 자신이 응답할 슬롯 위치를 임의로 선택하여 슬롯-카운터에 적재한다. 적재한 슬롯-카운터 값이 응답 슬롯 위치가 되면 자신의 EPC 코드로 응답한다. 한편, 리더는 매 슬롯마다 응답 슬롯의 정보를 읽는다. 만일 응답 슬롯에 태그의 응답이 없어서 빈 슬롯이거나 또는 여러 개의 태그가 동시에 응답하여 충돌이 발생하면 리더는 CloseSlot 명령을 전송한다. 반면, 하나의 태그만 응답한 경우에는 FixSlot 명령을 전송한다. 이 과정은 응답 라운드의 모든 응답 슬롯을 식별할 때까지 반복된다. 하나의 응답 라운드가 종료되었음에도 불구하고 충돌이 발생하여 식별영역 내에 있는 모든 태그가 식별되지 않은 경우 리더는 새로운 응답 라운드를 시작한다.
- 2.2. PS 알고리즘
그림 2 는 PS 알고리즘의 동작을 나타낸 것이다. PS 알고리즘을 설명하기 위하여 리더가 송신하는 최소 전력과 최대 전력을 각각 Pr,min , Pr,max 라 하고, 송신전력 증가 값을 k 라 한다. 리더가 태그를 식별하는 과정에서 임의의 전력으로 송신하여 리더의 식별영역 내에 있는 태그를 식별하는 과정을 스캔이라 정의하고, 최소 전력으로 시작하여 최대 전력이 될 때까지의 전체 스캔 과정을 사이클로 정의하면, PS 알고리즘의 동작은 다음과 같다 [5] .
  • ① 먼저 리더는Pr,min의 전력으로 명령을 송신한다. 이 경우Pr,min의 전력을 수신하는 태그들은 FSA 알고리즘을 이용하여 응답한다.
  • ② 리더는 송신전력을k만큼 증가시킨Pr,min+k의 전력으로 명령을 송신하여 스캔 과정을 반복한다. 이 경우, 이전의 스캔 과정에서 응답한 태그들은 응답하지 않고, 새롭게 식별영역 내에 들어온 태그들만 응답한다.
  • ③ 리더는 송신전력을 계속하여k만큼 증가시키면서 스캔 과정을 반복하고, 마지막으로 송신전력을 최대 전력인Pr,max로 하여 스캔한다. 이상의 과정을 마치면 하나의 사이클이 완성되고, 하나의 사이클은번의 스캔 과정으로 구성된다.
  • ④ 하나의 사이클이 종료되었음에도 불구하고 식별되지 않은 태그가 있으면 위의 과정 ①부터 새로운 사이클을 반복한다.
PPT Slide
Lager Image
PS 알고리즘의 동작 Fig. 2 Operations of PS algorithm
PS 알고리즘은 태그들을 리더의 송신전력 제어를 통하여 그룹화하고, 각 그룹별로 스캔 과정을 수행한다. 이 경우, 매 스캔마다 식별해야하는 태그의 수가 적으므로 빠른 식별이 가능한 장점이 있다.
Ⅲ. 제안하는 알고리즘
STAC 프로토콜에서 리더의 식별 영역 내에 태그의 수가 많은 경우 빈번한 충돌로 인하여 식별 성능이 저하된다. 따라서 본 장에서는 리더의 송신 전력 제어를 통하여 식별 영역에 있는 태그들을 그룹화 하는 PS 알고리즘을 STAC 프로토콜에 적용한 STAC/PS 알고리즘을 제안한다. 그림 3 은 STAC/PS 알고리즘에서 리더의 동작을 나타낸 것이다. STAC 프로토콜에서 BeginRound 명령으로 시작되는 하나의 식별 라운드는 STAC/PS 알고리즘의 스캔 개념과 동일하다. 하나의 사이클에서 리더는 i 번째 스캔마다 송신 전력을 Pr,min + k ( i -1)로 하여 BeginRound 명령을 전송한 후 STAC 프로토콜과 동일한 방법으로 태그의 응답 슬롯을 식별한다.
PPT Slide
Lager Image
STAC/PS 알고리즘의 리더 동작 Fig. 3 Reader's operation of STAC/PS algorithm
모든 응답 슬롯을 식별하여 응답 라운드가 종료되면 리더는 스캔 카운터를 증가시킨다. 하나의 사이클은 최소 전력에서 시작하여 최대 전력이 될 때까지의 스캔 과정이다. 따라서 증가시킨 스캔 카운터에서의 송신 전력이 최대 송신 전력에 도달하면 하나의 사이클이 종료된 것이므로 리더의 식별 영역 내에 식별되지 않은 태그가 있으면 새로운 사이클을 반복한다.
Ⅳ. 시뮬레이션 결과
본 논문에서는 시뮬레이션을 통하여 제안한 STAC/PS 알고리즘과 STAC 프로토콜의 성능을 비교 분석하였다.
시뮬레이션 프로그램은 SMPL 라이브러리 [8] 로 작성되었으며, STAC 프로토콜의 시뮬레이션을 위한 매개변수는 참고문헌 [6] 에서 정의된 값과 동일하게 가정하였다. STAC/PS 알고리즘에서 리더의 최소 전력( Pr,min)╲ )과 최대 전력( Pr,max )은 각각 0.4W와 4.0W로 가정하였다. 또한 STAC/PS 알고리즘의 프레임 크기는 64개의 슬롯으로 구성되고, 전력 증가 값( k )은 0.4W로 가정하였다.
그림 4 는 태그의 수에 따른 충돌률을 나타낸 것이다. 여기서, 충돌률은 모든 태그를 식별하기 위하여 소요된 총 슬롯 중에서 충돌이 발생한 슬롯의 수에 대한 비율로 정의한다. 시뮬레이션 결과, 제안한 기법의 충돌률은 29%이며, 이는 STAC 프로토콜에 비하여 50% 정도 적다. STAC 프로토콜의 프레임 구조에서 충돌이 발생한 슬롯의 길이는 2303.35usec이고, 빈 슬롯의 길이는 490.85usec이다 [6] . 충돌 슬롯의 길이가 빈 슬롯의 길이에 비하여 약 4.7배정도 더 길기 때문에 가능하면 충돌이 발생하지 않는 것이 식별 성능을 높일 수 있다. 따라서 STAC/PS 알고리즘의 충돌률이 STAC 프로토콜의 충돌률의 절반 정도에 불과하므로 STAC/PS 알고리즘의 식별 성능이 우수할 것으로 보인다.
PPT Slide
Lager Image
충돌률 비교 Fig. 4 Comparison of collision ratio
그림 5 6 은 리더의 식별 영역에 있는 태그의 수에 따른 식별 지연 및 식별 속도를 나타낸 것이다. 식별 지연은 리더가 모든 태그를 식별하는데 소요되는 시간을 의미하며, 식별 속도는 초당 리더가 식별하는 태그의 수를 의미한다.
PPT Slide
Lager Image
식별 지연 비교 Fig. 5 Comparison of identification delay
PPT Slide
Lager Image
식별 속도 비교 Fig. 6 Comparison of identification speed
태그의 수가 증가함에 따라 두 기법의 식별 지연은 거의 일정하게 증가하고, 식별 속도는 일정하게 감소한다. STAC 프로토콜의 평균 식별 지연은 23.16sec이고, STAC/PS 알고리즘의 평균 식별 지연은 16.32sec이다. 따라서 STAC/PS 알고리즘의 평균 식별 지연 성능이 STAC 프로토콜에 비하여 약 30% 개선된다.
STAC 프로토콜인 경우, 태그의 수가 증가하면 증가할수록 태그들의 충돌확률이 증가한다. 이에 따라 식별지연도 증가한다. 반면, STAC/PS 알고리즘인 경우, 리더의 식별 영역 내에 있는 태그들을 전력에 따라 그룹화하는 효과가 있다. 따라서 동일한 전력 범위 내에 있지 않는 태그들은 충돌이 발생하지 않으므로 STAC 프로토콜에 비하여 식별 시간이 빠르다.
그림 6 에서 나타낸 바와 같이 태그의 수가 적은 경우 (약 200개 이하인 경우), STAC 프로토콜의 식별속도가 STAC/PS 알고리즘에 비하여 빠르다. 이는 STAC/PS 알고리즘인 경우, 태그의 수가 적음에도 불구하고 전력을 증가시키면서 모든 태그가 식별될 때까지 사이클을 반복하므로 빈 슬롯이 많이 발생하기 때문이다.
그림 7 은 전력 증가 값에 따른 STAC/PS 알고리즘의 식별 지연을 나타낸 것이다. 전력 증가 값이 크면 한 사이클에서 스캔해야할 횟수가 적으므로 매 스캔할 때마다 리더의 식별영역 내에 많은 태그가 존재한다. 따라서 STAC/PS 알고리즘에서 태그의 수가 많은 경우, 증가 값을 크게 하면 한 스캔에서의 많은 태그로 인하여 충돌이 많이 발생하므로 식별 지연이 증가한다. 빈면, 전력 증가 값이 작으면 한 사이클의 스캔 횟수가 많아지므로 매 스캔마다 식별영역 내에 있는 태그의 수가 적다. 따라서 STAC/PS 알고리즘의 경우 빈 슬롯이 많이 발생하므로 식별 지연이 증가한다.
PPT Slide
Lager Image
전력 증가 값 k에 따른 식별 지연 Fig. 7 Identification delay according to step size k
Ⅴ. 결 론
본 논문에서는 STAC 프로토콜의 식별 성능을 개선하기 위하여 PS 알고리즘을 적용한 STAC/PS 알고리즘을 제안하고, 시뮬레이션을 통하여 이에 대한 성능을 분석하였다.
제안한 기법에서는 STAC 프로토콜의 응답 라운드를 PS 알고리즘의 스캔으로 하여 리더는 전력을 증가시키면서 하나의 사이클 동안 스캔과정을 반복한다. 이에 따라 동일한 스캔과정에 포함되지 않는 태그들은 충돌이 발생하지 않는다. RFID 시스템에서 태그 식별 성능은 충돌률과 밀접한 관계가 있다. 성능 분석의 결과, 제안한 기법은 STAC 프로토콜에 비하여 충돌률이 낮으므로 식별 시간이 짧음을 알 수 있었다.
Acknowledgements
이 논문은 2015년도 부산외국어대학교 학술연구조성비에 의해 연구되었음
BIO
임인택(Intaek Lim)
1984년 2월 울산대학교 전자계산학과 공학사
1986년 2월 서울대학교 계산통계학과 이학석사
1998년 2월 울산대학교 컴퓨터공학과 공학박사
1984년 ~ 1993년 (주)삼성전자 선임연구원
1998년 3월 ~ 현재 부산외국어대학교 임베디드소프트웨어학과 교수
※관심분야 : MAC 프로토콜, RFID, 사물네트워크
References
Chen W. , Lin G. 2006 “An Efficient Anti-Collision Method for Tag Identification in a RFID System,” IEICE Trans Commun. E89-B (12) 3386 - 3392    DOI : 10.1093/ietcom/e89-b.12.3386
EPCglobal 2008 “EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocols for Communication at 860 MHz-960MHz, Ver.1.2.0," EPCGlobal Inc.
ISO/IEC 2006 “Information Technology - Radio Frequency Identification for Item Management - Part 6: Parameters for Air Interface Communication at 860-960 MHz, 18000-6,” ISO/IEC
Auto-ID Center 2003 “860MHz-930MHz Class 0 Radio Frequency Identification Tag Protocol Specification Candidate Recommendation, Version 1.0.0,”
Su W. , Alchazidis N. V. , Ha T. T. 2010 "Multiple RFID Tags Access Algorithm," IEEE Trans. Mobile Computing 9 (2) 174 - 187    DOI : 10.1109/TMC.2009.106
Auti-ID Center 2003 “13.56MHz ISM Band Class 1 Rafio Frequency Identificatin Tag Interface Specification: Candidate Recommendation, Version 1.0.0,”
Lim I. 2013 “Performance Improvement of STAC Protocol by Early Release of Reply Round and Transmission Probability Control” Journal of KIICE 17 (11) 2569 - 2574
MacDaugall M. H. 1987 Simulating Computer Systems Techniques and Tools MIT Press