초기 프레임 크기 예측을 통한 DFSA(Dynamic Frame Slotted Aloha) 알고리즘 성능 개선 Performance Improvements of DFSA(Dynamic Frame Slotted Aloha) Algorithm through Estimation of Intial frame Size원문보기
이강원
(Department of Industrial and Information System Engineering, Seoul National University of Science & Technology)
,
이문형
(Department of Industrial and Information System Engineering, Seoul National University of Science & Technology)
,
이현교
(Department of Industrial and Information System Engineering, Seoul National University of Science & Technology)
,
임경희
(Department of Industrial and Information System Engineering, Seoul National University of Science & Technology)
기존의 충돌 방지 알고리즘들은 현 프레임내의 충돌 정보를 토대로 다음 프레임내의 슬롯 수를 결정하기 때문에 충돌 정보가 전혀 없는 초기 프레임의 슬롯 수는 결정할 수가 없다. 따라서 이들 알고리즘들은 초기 슬롯 수를 임의의 상수로 설정해 사용하고 있는데 알고리즘의 효율이 초기 슬롯 수에 민감하다는 연구결과를 감안하면 이는 개선 할 필요성이 있다. 본 연구에서는 이를 위해 효율적인 초기 프레임 슬롯 수 결정을 위한 두 가지 방법을 제안하였는데 이를 통해 Dynamic Frame Slotted Aloha Algorithm의 성능 개선을 시도하였다. 본 연구에서 제안한 알고리즘의 성능을 검증하기 위하여 2.4 GHz RFID 시스템을 사용하였으며 성능 측도로 사용한 Throughput과 Delay Time을 유도하기 위해 시뮬레이션 모형을 Java로 구축하였다. 본 연구에서 제안한 방법을 통해 Throughput은 9.6%, Delay Time은 9.8% 개선됨을 확인하였다.
기존의 충돌 방지 알고리즘들은 현 프레임내의 충돌 정보를 토대로 다음 프레임내의 슬롯 수를 결정하기 때문에 충돌 정보가 전혀 없는 초기 프레임의 슬롯 수는 결정할 수가 없다. 따라서 이들 알고리즘들은 초기 슬롯 수를 임의의 상수로 설정해 사용하고 있는데 알고리즘의 효율이 초기 슬롯 수에 민감하다는 연구결과를 감안하면 이는 개선 할 필요성이 있다. 본 연구에서는 이를 위해 효율적인 초기 프레임 슬롯 수 결정을 위한 두 가지 방법을 제안하였는데 이를 통해 Dynamic Frame Slotted Aloha Algorithm의 성능 개선을 시도하였다. 본 연구에서 제안한 알고리즘의 성능을 검증하기 위하여 2.4 GHz RFID 시스템을 사용하였으며 성능 측도로 사용한 Throughput과 Delay Time을 유도하기 위해 시뮬레이션 모형을 Java로 구축하였다. 본 연구에서 제안한 방법을 통해 Throughput은 9.6%, Delay Time은 9.8% 개선됨을 확인하였다.
Traditional anti-collision algorithms determine slot size of initial frame based on the information of number of collision slots, idle slots, and success slots. Since there is no information about collision at the beginning of tag information collection, traditional anti-collision algorithms can not...
Traditional anti-collision algorithms determine slot size of initial frame based on the information of number of collision slots, idle slots, and success slots. Since there is no information about collision at the beginning of tag information collection, traditional anti-collision algorithms can not determine the initial frame size. Considering that performance of anti-collision algorithm is very sensitive to initial slot size traditional anti-collision algorithms need some improvements. In this study two methods are proposed to determine slot size of initial frame efficiently, through which we can improve the performance of dynamic frame slotted aloha algorithm. To verify the performance of proposed algorithms, 2.4GHz RFID system is used. Throughput and delay time are derived through simulation, which is developed using JAVA. We have seen that proposed algorithm improves throughput by 9.6% and delay time by 9.8%.
Traditional anti-collision algorithms determine slot size of initial frame based on the information of number of collision slots, idle slots, and success slots. Since there is no information about collision at the beginning of tag information collection, traditional anti-collision algorithms can not determine the initial frame size. Considering that performance of anti-collision algorithm is very sensitive to initial slot size traditional anti-collision algorithms need some improvements. In this study two methods are proposed to determine slot size of initial frame efficiently, through which we can improve the performance of dynamic frame slotted aloha algorithm. To verify the performance of proposed algorithms, 2.4GHz RFID system is used. Throughput and delay time are derived through simulation, which is developed using JAVA. We have seen that proposed algorithm improves throughput by 9.6% and delay time by 9.8%.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
그러므로 파라미터 값 i와 C를 태그의 개수에 따라 동적으로 변화시키는 과정이 무엇보다도 필요하다. 따라서 본 연구에서는 NEDFSA의 파라미터 값 i와 C를 프레임내의 충돌상태 정보를 토대로 조정하는 알고리즘을 제안 하였다. 즉 모든 슬롯에 충돌이 발생하면 태그 수가 매우 많이 존재 한다고 예측되므로 i 와 C를 1씩 증가 시키고 반대로 모든 슬롯이 idle 슬롯으로 나타나면 현재 태그 수가 많지 않음으로 판단되어 i 와 C를 1씩 감소시킨다.
본 연구에서는 위에서 언급한 NEDFSA의 두 가지 문제점을 보완하는 새로운 방법을 제안하고자 한다. Final Q에서 초기 프레임 크기를 예측 할 때 단순하게 0.
본 연구의 목적중 하나가 초기 타임 슬롯 수를 예측하는 것과 그렇지 않은 경우에 대하여 성능을 비교해보는 것이다. 따라서 초기 타임 슬롯 수를 예측하지 않는Schoute 알고리즘과 예측하는 NEDFSA, 본 연구의 제안 방법인 Proposal 1, 2와 비교해보았다.
가설 설정
한편 NEDFSA 에서는 최종적으로 프레임 크기(FinalQ)를 추정한 후 초기 프레임 크기가 2Q-1과 2Q 사이에 존재 한다고 가정하여 0.67*Final Q 로 초기 프레임크기를 결정하였다. 이때 사용한 0.
제안 방법
Final Q에서 초기 프레임 크기를 예측 할 때 단순하게 0.67을 곱하는 대신에 마지막 프레임내의 충돌 슬롯 수와 ‘idle’ 슬롯수를 토대로 예측하는 방법을 제안하였다.
Step 1: 정보 전송을 원하는 Active 태그의 개수를 임의의 구간(Small, Medium, Large)으로 나누었다. Small 구간은 1~100개, Medium 구간은 100~1,000개, Large 구간은 1,000~2,000개의 태그의 개수를 나타낸다.
그리고 예측에 사용하는 슬롯 수 i 와 슬롯 수의 증감을 나타내는 C를 상수로 사용하는 대신에 프레임내의 충돌 슬롯 수와 ‘idle’슬롯수를 토대로 동적으로 결정해나가는 새로운 방법을 제안하였다.
본 시뮬레이션 모델에서 사용한 입력 자료들은 기본적으로 ISO 18000-7을 토대로 하였다. 다만 433 MHz 대역의 전송 속도가 아닌 2.4 GHz 대역의 전송 속도에 맞도록 일부 데이터를 수정하였다.
본 연구의 목적중 하나가 초기 타임 슬롯 수를 예측하는 것과 그렇지 않은 경우에 대하여 성능을 비교해보는 것이다. 따라서 초기 타임 슬롯 수를 예측하지 않는Schoute 알고리즘과 예측하는 NEDFSA, 본 연구의 제안 방법인 Proposal 1, 2와 비교해보았다. 이 때 태그 수집 과정에서 다음프레임 크기 예측은 모두 Schoute 알고리즘을 사용하였다.
67은 어떠한 이론적 근거 없이 직관적인 경험에 바탕을 둔 값이기 때문에 받아들이기 어렵다. 또한 예측에 사용하는 슬롯 수 i 와 슬롯 수의 증감을 나타내는 C를 태그 수가 100개 일 때를 기준으로 각각 3과 1로 설정하여 사용하였다. 그런데 태그의 개수가 동적으로 변하는 상황 하에서 이 값들이 최적의 효율을 보장 한다고 말 할 수 없다.
그리고 예측에 사용하는 슬롯 수 i 와 슬롯 수의 증감을 나타내는 C를 상수로 사용하는 대신에 프레임내의 충돌 슬롯 수와 ‘idle’슬롯수를 토대로 동적으로 결정해나가는 새로운 방법을 제안하였다. 본 연구에서 제안한 알고리즘의 성능을 검증하기 위하여 2.4 GHz RFID 시스템을 사용하였으며 성능 측도로 사용한 Throughput과 Delay Time을 유도하기 위해 시뮬레이션 모형을 Java로 구축하였다. 제안한 방법의 우수성을 검증하기 위해 Schoute 방법과 NEDFSA 방법과 비교하였다.
본 연구에서는 2장에서 제안한 초기 프레임 크기를 예측하는 충돌 방지 알고리즘의 성능을 보다 정확하게 분석 할 수 있는 시뮬레이션 방법을 사용하였다. 본 연구에서 사용한 시뮬레이션 모형의 절차를 살펴보면 그림 4와 같다.
본 연구에서는 다음의 두 가지 제안을 하여 이를 Proposal 1과 Proposal 2로 하였다.
따라서 실제로 태그의 정보 수집에 들어가기 전에 최초 타임 슬롯 수를 예측하는 알고리즘이 필요하다. 본 연구에서는 초기 프레임 크기를 예측하는 NEDFSA 알고리즘을 개선하여 두 개의 알고리즘 Proposal 1 과 Proposal 2를 제안하였다. 이를 2.
본 장에서는 2장에서 제안한 초기 프레임 크기를 예측하는 충돌 방지 알고리즘을 2.4 GHz 능동형 RFID 시스템 하에서 다른 충돌 제어 알고리즘과 성능비교를 통해 우수성을 검증해 보았다.
시뮬레이션 모형은 Java 언어로 구축하였다. 본 장에서는 시뮬레이션을 위해 사용한 모형 및 입력 자료와 시뮬레이션 결과를 분석하였다. 입력 자료는 시뮬레이션을 위해 필요한 2.
본장에서는 본 연구에서 제안하는 알고리즘을 설명하였으며 그에 앞서 제안한 알고리즘의 성능의 우수함을 보이기 위해 비교대상으로 선정한 Schoute 알고리즘과 NEDFSA 알고리즘을 간단하게 소개하였다.
서론에 이어 2장에서는 Shoute방법과 NEDFSA 방법을 간단하게 살펴보았으며 본 연구에서 제안한 방법을 설명하였다. 3장에서는 제안한 알고리즘의 성능을 검증하기 위한 2.
본 연구에서는 초기 프레임 크기를 예측하는 NEDFSA 알고리즘을 개선하여 두 개의 알고리즘 Proposal 1 과 Proposal 2를 제안하였다. 이를 2.4 GHz Active RFID 환경에서 검증하고자 시뮬레이션을 통해 제안한 알고리즘들의 Throughput과 Delay Time을 유도 하였다.
충돌 제어 알고리즘의 4가지 방법(Schoute, NEDFSA, 본 연구에서 제안한 Proposal 1, Proposal 2)에 대하여 초기 타임 슬롯 수 Q0(= 16, 32, 64, 128, 256)를 변화시키면서 Throughput과 Delay Time을 시뮬레이션을 통해 구하였다. 이중 본문에는 Q0 = 16, 64 그리고 256인 경우만 수록하였다.
대상 데이터
본 시뮬레이션 모델에서 사용한 입력 자료들은 기본적으로 ISO 18000-7을 토대로 하였다. 다만 433 MHz 대역의 전송 속도가 아닌 2.
(= 16, 32, 64, 128, 256)를 변화시키면서 Throughput과 Delay Time을 시뮬레이션을 통해 구하였다. 이중 본문에는 Q0 = 16, 64 그리고 256인 경우만 수록하였다.
데이터처리
한편 초기 프레임 크기를 예측하는 NEDFSA를 제안한 Mota와 Batista[10]는 대표적인 DFSA 알고리즘의 하나인 Q-algorithm에 비해 Throughput이 27% 향상됨을 보였다. 본 연구에서 제안한 충돌 방지 알고리즘을 NEDFSA와 직접 비교하여 성능 우수성을 검증하였다.
제안한 방법의 우수성을 검증하기 위해 Schoute 방법과 NEDFSA 방법과 비교하였다. 제안한 방법에서 초기 프레임크기 예측을 위해 사용하는 슬롯들은 실제로는 정보 전송이 되지 않는 불필요한 슬롯들이기 때문에 태그 수가 매우 작을 경우 Throughput이 떨어지리라 예측 되는데 이때 가장 단순한 DFSA 알고리즘인 Schoute방법과 비교해 보았다.
4 GHz RFID 시스템을 사용하였으며 성능 측도로 사용한 Throughput과 Delay Time을 유도하기 위해 시뮬레이션 모형을 Java로 구축하였다. 제안한 방법의 우수성을 검증하기 위해 Schoute 방법과 NEDFSA 방법과 비교하였다. 제안한 방법에서 초기 프레임크기 예측을 위해 사용하는 슬롯들은 실제로는 정보 전송이 되지 않는 불필요한 슬롯들이기 때문에 태그 수가 매우 작을 경우 Throughput이 떨어지리라 예측 되는데 이때 가장 단순한 DFSA 알고리즘인 Schoute방법과 비교해 보았다.
이론/모형
따라서 초기 타임 슬롯 수를 예측하지 않는Schoute 알고리즘과 예측하는 NEDFSA, 본 연구의 제안 방법인 Proposal 1, 2와 비교해보았다. 이 때 태그 수집 과정에서 다음프레임 크기 예측은 모두 Schoute 알고리즘을 사용하였다.
한편 태그의 정보 수집과정에서 현 라운드의 프레임의 출동 상태 정보를 토대로 다음 라운드의 프레임의 크기를 결정하기 위해서 앞의 2장에서 설명한 Schoute 알고리즘을 이용하였다.
성능/효과
이는 초기 프레임 크기를 예측하는 다른 방법들 하에서는 초기 슬롯 수예측을 위해 여분의 슬롯을 사용해야 하는데 태그의 개수가 작을 때에는 그 효과가 제대로 나타나지 않기 때문이다. 그렇지만 태그의 개수가 커질수록 초기 타임 슬롯 수를 추정하는 과정이 효과를 나타내는 것을 확인할 수 있었는데, 이 때 기존의 NEDFSA 알고리즘보다 제안한 알고리즘들의 성능이 좋게 나타났다. 이는 Final Q 프레임 내에 충돌 슬롯수가 많으면 프레임 크기를 늘리고 idle 슬롯 수가 많으면 프레임 크기를 줄이는 방식이 효과적임을 보여준다.
이는 Final Q 프레임 내에 충돌 슬롯수가 많으면 프레임 크기를 늘리고 idle 슬롯 수가 많으면 프레임 크기를 줄이는 방식이 효과적임을 보여준다. 또한 Proposal 1 알고리즘보다 Proposal 2 알고리즘의 성능이 대체적으로 우수하게 나타났다. 이는 NEDFSA의 파라미터 값 i와 C를 프레임내의 충돌 상태 정보를 토대로 조정하는 알고리즘의 효용성을 나타낸다고 볼 수 있다.
초기 프레임크기를 예측하는 3개의 방법 중에서는 Q0 = 16에서와 마찬가지로 본 연구에서 제안한 Proposal 2의 성능이 Throughput과 Delay Time 모두 가장 좋게 나타났다.
최초 타임 슬롯 수(Q0) = 16일 때와는 다르게 그림 6과 표 4, 표 5에서 볼 수 있듯이 태그의 개수가 Small 구간에 있을 때에도 기존의 Schoute 알고리즘이 나머지 알고리즘들 보다 Throughput은 낮고 Delay Time은 크게 나타났다. 이는 태그의 개수가 작음에도 불구하고 초기 타임 슬롯 수를 64로 비교적 크게 설정하여 ‘idle’ 슬롯수가 많이 발생함에 기인한다.
최초 타임 슬롯 수(Q0) = 64 일 때와 마찬가지로 그림 7과 표 6, 표 7에서 볼 수 있듯이 태그의 개수가 Small 구간에 있을 때에 기존의 Schoute 알고리즘이나머지 알고리즘들에 비해 Throughput은 0.1476으로 매우 낮고 Delay Time은 973.94로 가장 크게 나타났다. 이는 태그의 개수가 작음에도 불구하고 초기 타임 슬롯 수를 256으로 크게 설정하여 ‘idle’슬롯수가 많이 발생함에 기인한다.
태그의 수와 무관하게 좋은 성능을 보이는 알고리즘은 없다. 태그의 개수가 작을 때에는 기존의 Schoute알고리즘의 성능이 좋게 나타났다. 이는 초기 프레임 크기를 예측하는 다른 방법들 하에서는 초기 슬롯 수예측을 위해 여분의 슬롯을 사용해야 하는데 태그의 개수가 작을 때에는 그 효과가 제대로 나타나지 않기 때문이다.
이는 초기 프레임 크기를 예측하는 다른 3가지 방법에서는 태그의 개수가 작을 때에 초기 타임 슬롯 수를 예측하는 과정에서 슬롯 낭비가 발생했기 때문이다. 하지만 태그의 규모가 Medium, Large로 커질수록 제안한 Proposal 2의 성능이 우수하게 나타났다. 초기 프레임 크기를 예측하는 방법은 태그의 개수가 많을 경우에 처음에 예측을 위해 다수개의 슬롯을 낭비하더라도 비교적 정확하게 초기 프레임 크기를 예측하여 Throughput을 높이고 Delay Time을 줄일 수 있었다.
후속연구
먼저 Schoute 알고리즘은 DFSA 알고리즘 가운데 가장 간단한 알고리즘이다. 본 연구에서 제안한 방법에서 초기 프레임 크기 예측을 위해 사용하는 슬롯들은 정보전송이 되지 않는 불필요한 슬롯들이기 때문에 태그 수가 매우 작을 경우 Throughput이 초기 프레임 크기를 예측 하지 않는 다른 DFSA 알고리즘에 비해 떨어지리라 예측된다. 이때 가장 단순한 DFSA 알고리즘인 Schoute와 비교를 통해 태그 수가 매우 작을 경우 Throughput 저하의 심각성 여부를 판단 할 수 있다.
질의응답
핵심어
질문
논문에서 추출한 답변
Q-algorithm을 바탕으로 하는 NEDFSA에서 프레임 크기를 0.67로 하였을 때 문제점은 무엇인가?
이때 사용한 0.67은 어떠한 이론적 근거 없이 직관적인 경험에 바탕을 둔 값이기 때문에 받아들이기 어렵다. 또한 예측에 사용하는 슬롯 수 i 와 슬롯 수의 증감을 나타내는 C를 태그 수가 100개 일 때를 기준으로 각각 3과 1로 설정하여 사용하였다.
Q-algorithm은 무엇인가?
즉 현 프레임 내에 성공 슬롯 수에 비해 충돌 슬롯 수가 많으면 다름 프레임내의 슬롯 수를 늘리고 반대로 충돌 슬롯 수가 거의 없으면 다음 프레임의 슬롯 수를 줄여서 무선 채널 사용 효율을 극대화 하는 방법이다. 한편 Q-algorithm은 연구[9]에 잘 설명되어 있는데 한 프레임내의 충돌 슬롯 수와 성공 슬롯 수를 토대로 프레임내의 슬롯 수를 2Q 형태로 조정해 나가는 방법인데 ‘fixed Q-algorithm’과 ‘adjustableQ-algorithm’이 존재한다.
사물인터넷 통신 기술은 무엇이 있는가?
또한 전 세계적으로 사물인터넷 서비스 제공을 위해 다양한 통신 기술이 사용되고 있다. 가장 많이 활용되고 있는 WiFi, ZigBee, Bluetooth, RFID, LTE 기술 외에도 다양한 LPWA(Low Power Wide Area) 사물인터넷 통신 기술이 등장하고 있다. 따라서 이들을 효율적으로 사용하는 것이 무엇보다도 중요해졌다.
참고문헌 (12)
Y. Quin, O. Z. Sheng, N. J. Falker, S. Dustdar, H. Wang, and A. V. Vasilakos, "When things matter:A survey on data-centric internet of things," Journal of Network Computing Applications, vol. 64, pp. 137-153, February 2016.
D. Gil, A. Ferrandez, H. M. Mora, and J. Peral, "Internet of things:a review of surveys based on context aware intelligent services," Sensors, vol.16, 1069, July 2016.
A. Botta, W. Donato, V. Persico, and A. Pescape, "Integration of cloud computing and internet of things: a survey," Future Generation of Computing System, vol.56. pp.684-700, March 2016.
F. Schoute, "Dynamic frame length ALOHA," IEEE Transactions on Communications, vol. 31, no.4, pp. 235- 242, April 1983.
J. B. Eom and T. J. Lee, "Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems," Communication Letters IEEE, vol. 14, no. 1, pp. 60-62, January 2010.
H. Vogt, "Efficient object identification with passive RFID tags," in Proceedings of IEEE International Conference of Systems, Man and Cybernetics, vol.3, pp.98-113, August 2002.
W. T. Chen, "An accurate tag estimate method for improving the performance of an RFID anti-collision algorithm based on dynamic frame length ALOHA," IEEE Transactions on Automation Science Engineering, vol. 6, no. 1, pp.9-15, January 2009.
J. T. Kim, J. S. Kim, and K. W. Lee, "Study on the performance improvement of active RFID System," The Journal of Korean Institute of Communications and Information Sciences, vol. 40, no. 05, pp. 871-885, May 2015.
V. Namboodiri, M. DeSilva, K. Deegala, and S. Ramamoorthy, "An extensive study of slotted Aloha-based RFID anti-collision protocols," Computer Communications, vol.35, no.16, pp.1955-1966, September 2012.
R. P. B. Mota and D. M. Batista, "A dynamic frame slotted ALOHA anti-collision algorithm for the internet of things," in Proceedings of. the 29th Annual ACM Symposium of Applied Computing, pp. 686-691, March 2014.
J. T. Kim and K. W. Lee, "Study on the low Low Power Consumption of Active RFID Tag System," The Journal of Korean Institute of Information and Communication Engineering, vol. 19, no. 06, pp. 1419-1435, June 2015.
ISO/ISE 18000-7, Information Technology-radio Frequency Identification for Item Management - Part 7: Parameters for Active Air Interface Communications at 433 MHz, pp.3-54, 2009.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.