RFID 기술를 이용한 다양한 응용분야에서 잘못된 RFID 리더기의 배치로 인해 리더기간의 간섭이 발생한다. 리더기간의 간섭은 어떤 리더기가 다른 리더기의 동작에 간섭을 일으키는 신호를 송신하여 태그를 인식하는 것을 방해할 때 발생한다. RFID 시스템에서 리더기의 충돌 문제는 시스템 처리량과 인식의 효율성의 병목현상을 발생 시킨다. 본 논문에서는 RIFD 안테나 배치의 적합도를 높이기 위해서 진화 연산알고리즘을 이용한 새로운 RFID 리더기 배치 설계 시스템을 제안한다. 먼저, 주위 환경에 민감한 안테나의 전파 특성을 분석하고, 특성 데이터베이스를 구축한다. 그리고, 안테나를 최적으로 배치하기 위한 진화 연산 알고리즘을 이용한 Encoding 기법과 Fitness 기법 및 유전잔 연산자를 제안한다. 제안하는 기법의 우수성을 보이기 위해서 시뮬레이션을 수행하였으며, 실험 결과, 약 100세대의 진화 연산을 통해 커버율 95.45%, 간섭율 10.29%의 RFID 안테나 배치의 적합도를 달성하였다.
RFID 기술를 이용한 다양한 응용분야에서 잘못된 RFID 리더기의 배치로 인해 리더기간의 간섭이 발생한다. 리더기간의 간섭은 어떤 리더기가 다른 리더기의 동작에 간섭을 일으키는 신호를 송신하여 태그를 인식하는 것을 방해할 때 발생한다. RFID 시스템에서 리더기의 충돌 문제는 시스템 처리량과 인식의 효율성의 병목현상을 발생 시킨다. 본 논문에서는 RIFD 안테나 배치의 적합도를 높이기 위해서 진화 연산 알고리즘을 이용한 새로운 RFID 리더기 배치 설계 시스템을 제안한다. 먼저, 주위 환경에 민감한 안테나의 전파 특성을 분석하고, 특성 데이터베이스를 구축한다. 그리고, 안테나를 최적으로 배치하기 위한 진화 연산 알고리즘을 이용한 Encoding 기법과 Fitness 기법 및 유전잔 연산자를 제안한다. 제안하는 기법의 우수성을 보이기 위해서 시뮬레이션을 수행하였으며, 실험 결과, 약 100세대의 진화 연산을 통해 커버율 95.45%, 간섭율 10.29%의 RFID 안테나 배치의 적합도를 달성하였다.
Incorrect deployment of RFID readers occurs reader-to-reader interferences in many applications using RFID technologies. Reader-to-reader interference occurs when a reader transmits a signal that interferes with the operation of another reader, thus preventing the second reader from communicating wi...
Incorrect deployment of RFID readers occurs reader-to-reader interferences in many applications using RFID technologies. Reader-to-reader interference occurs when a reader transmits a signal that interferes with the operation of another reader, thus preventing the second reader from communicating with tags in its interrogation zone. Interference detected by one reader and caused by another reader is referred to as a reader collision. In RFID systems, the reader collision problem is considered to be the bottleneck for the system throughput and reading efficiency. In this paper, we propose a novel RFID reader anti-collision algorithm based on evolutionary algorithm(EA). First, we analyze characteristics of RFID antennas and build database. Also, we propose EA encoding algorithm, fitness algorithm and genetic operators to deploy antennas efficiently. To show superiority of our proposed algorithm, we simulated our proposed algorithm. In the result, our proposed algorithm obtains 95.45% coverage rate and 10.29% interference rate after about 100 generations.
Incorrect deployment of RFID readers occurs reader-to-reader interferences in many applications using RFID technologies. Reader-to-reader interference occurs when a reader transmits a signal that interferes with the operation of another reader, thus preventing the second reader from communicating with tags in its interrogation zone. Interference detected by one reader and caused by another reader is referred to as a reader collision. In RFID systems, the reader collision problem is considered to be the bottleneck for the system throughput and reading efficiency. In this paper, we propose a novel RFID reader anti-collision algorithm based on evolutionary algorithm(EA). First, we analyze characteristics of RFID antennas and build database. Also, we propose EA encoding algorithm, fitness algorithm and genetic operators to deploy antennas efficiently. To show superiority of our proposed algorithm, we simulated our proposed algorithm. In the result, our proposed algorithm obtains 95.45% coverage rate and 10.29% interference rate after about 100 generations.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
보여줄 것이다. 결과 분석을 통해 제안된 방법의 타당성을 증명하고, 추후 활용 방안에 대해 생각해본다.
본 논문에서는 RHD 리더기 안테나를 최적으로 배치하기 위한 진화 연산 알고리즘을 제안하였다. 기존의문제 정의를 수정하여, RFID 안테나의 모델을 단순한 원반 형태가 아닌 실제 실험을 통해 얻어진 결과를 가지고 사용하였다.
본 논문에서는 RHD 안테나 배치를 기존의 방식과는 달리 서로 다른 크기의 인식 범위를 갖는 안테나 모델을 고려하여 안테나를 배치하는 문제로 생각하였다. 전체 영역을 최대한 커버하면서도 최소 개수의 리더기만을 사용하고 동시에 리더기간의 인식범위가 겹치는 것도 역시 최소화하는 문제로 정의하였다.
본 논문에서는 넓은 영역을 모두 커버하기 위한 RED 리더기 안테나의 배치 최적화 알고리즘을 제안한다. 이를 위해 실제 전파 특성 데이터를 분석, 데이터베이스화하고 거리에 따른 실제 실험 데이터를 활용하여 적용하였다.
가설 설정
또한 RFID 안테나 인식범위가 서로 겹치는 경우 간섭이 발생하여 인식에 부정적인 영향을 끼친다. 이러한 측면에서 볼 때에도 [그림 l](b) 배치가 더 적합하다는 것을 알 수 있다.
[5]는 무선 통신기술 가운데에서 라디오 네트워크 디자인 문제(Radio Network Design (RND) problem)# 다루면서 이를 해결하기 위해 차분 진화 연산 방법을 제안하였다. 중계기의 커버리지를 원 또는 정사각형 형태로 가정하였고, 중계기의 커버리지를 최대로 하면서 중계기 대수를 최소화 하는 문제로 접근하였다. 이 밖에도 타부 서치 (Tabu search)와 유전자 알고리즘(GA), Simulated annealing(SA) 그리고 진화 SA(ESA) 등의 방법들을 사용하여 RHD 관련 문제를 해결하려 노력했다[6T0I 이미 언급했듯이, RFID 리더기 안테나 배치와 관련된 연구는 아직 미미하다.
제안 방법
이를 해결하기 위해 메타 휴리스틱 서치 기법 중 가장 일반적으로 널리 사용되고 있는 진화 연산 알고리즘(EA) 을 사용하였다[9]. 그리고 RFID 안테나 배치 문제에 적합한 새로운 인코딩 기법을 제안하였다. 또한 사용자가 가중치를 조절 가능하도록 적합도 함수를 도출하여 진화 연산 알고리즘을 설계하였으며, 새로운 인코딩 방법에 맞도록 진화 연산자들 추가 제안하였다.
기존의문제 정의를 수정하여, RFID 안테나의 모델을 단순한 원반 형태가 아닌 실제 실험을 통해 얻어진 결과를 가지고 사용하였다. 또한 파워 레벨을 달리하여 서로 다른 크기의 인식 범위를 갖는 안테나들을 사용하였다.
이를 위해 실제 전파 특성 데이터를 분석, 데이터베이스화하고 거리에 따른 실제 실험 데이터를 활용하여 적용하였다. 단순한 원반 형태가 아닌 실제 전파 특성과 비슷한 형태의 안테나 모델을 활용하였으며, 안테나 이득의 변화에 따라 인식 거리가 달라진다는 점에 착안하여 다양한 안테나 이득을 적용하여 서로 다른 인식 거리를 갖는 안테나들이 적용 될 수 있도록 하였다. 이를 해결하기 위해 메타 휴리스틱 서치 기법 중 가장 일반적으로 널리 사용되고 있는 진화 연산 알고리즘(EA) 을 사용하였다[9].
돌연변이의 경우 개체의 각 유전자에 대하여 일정한 돌연변이 확률을 적용하여 대립 유전자의 값으로 바꾸는 것을 의미하기 때문에, 교배와 마찬가지로 4개의 유전자 그룹에 독립적으로 적용되도록 설계하였다. 앞의 세 그룹은 진화 초기에는 보다 넓은 영역을 탐색하고, 진화가 진행 될수록 탐색 영역을 좁히는 형태의 불균등 돌연변이(Non uniform mutation) 기법을 사용하였다.
그리고 RFID 안테나 배치 문제에 적합한 새로운 인코딩 기법을 제안하였다. 또한 사용자가 가중치를 조절 가능하도록 적합도 함수를 도출하여 진화 연산 알고리즘을 설계하였으며, 새로운 인코딩 방법에 맞도록 진화 연산자들 추가 제안하였다. 제안된 진화 연산 알고리즘의 성능을 평가한 결과 매 세대 얻어진 최우수 개체(Elite)의 적합도 값은 진화가 진행 될수록 적합도가 전체적으로 증가하였으며, 만약 세대 수를 늘려 진화를 계속 할 경우 더 좋은 값을 찾을 수도 있을 것이다.
기존의문제 정의를 수정하여, RFID 안테나의 모델을 단순한 원반 형태가 아닌 실제 실험을 통해 얻어진 결과를 가지고 사용하였다. 또한 파워 레벨을 달리하여 서로 다른 크기의 인식 범위를 갖는 안테나들을 사용하였다. 더욱이 임의의 영역 전체를 커버하기 위한 RFID 안테나 최적 배치 문제를 해결하기 위해서, 진화 연산 알고리즘을 새롭게 제안하였다.
먼저 유전자 교배의 경우, 산술 교배(Arithmetic crossover)를 기반으로 하여 3개의 유전자 그룹에 각각 독립적으로 적용되도록 하였다. 하지만 마지막 유전자 그룹의 경우 0 또는 1의 값으로 정의되기 때문에 일반적인 단순 교배(Simple crossover) 형태를 사용하였다.
RFID 태그 역시 안테나가 들어있고, 안테나의 성능이나 사양이 태그의 형태에 따라 인식 범위가 달라진다는 것을 알 수 있다. 믿을 만한 데이터를 얻는 것이 목적이므로 이들 중 가장 최적의 결과를 낼 수 있는 태그들을 골라서 실험을 진행하였다.
본 논문에서 제안한 진화 연산 알고리즘으로 실험을 진행하기 위해서 [표 3]과 같이 파라미터들을 설정하였다.
이때 문제에서 찾으려 하는 변수들을 숫자의 배열 형태로 만드는 것을 인코딩이라고 한다. 본 논문에서는 안테나를 최적으로 배치하기 위한 문제를 다루기 때문에, 안테나의 위치, 그리고 안테나의 인식반경, 안테나의 개수 등의 정보가 포함되도록 유전자형을 만들어야 한다. 이러한 목적을 이루기 위해 아래 [그림 4]와 같은 방식으로 유전자 인코딩을 제안한다.
살펴볼 필요가 있다. 본 실험에서는 30도 단위로 인식거리를 측정하였다.
따라서 신호를 전송하고 수신하는데 있어서 안테나의 출력이 중요한 역할을 한다. 본 실험에서는 IU9003의 경우에는 15dBm~ 30dBm을 10개의 레벨로 나누어 표현하고 ALR 9800 의 경우에는 OdB ~ 9dB attenuation을 10개의 레 벨로 나누어 표현하고 각 레벨에서의 태그 인식 거리를 측정하였다.
안테나와 태그의 종류에 따라서 인식 거리와 성능이 달라지기 때문에 여러 가지 종류별로 태그가 달라질 때의 인식 거리 정보를 측정하였다. 전원을 리더기에 연결하고 리더기가 부팅되면 UHF RFID 안테나를 리더기에 연결한다.
이를 위해 RFID 문제에 적합한 인코딩 방식을 제안하였고, 진화가 제대로 이루어지게 하기 위해 진화 연산자 역시 새롭게 설계하였다. 안테나의 커버율과 간섭율을 조합하여 적합도 함수를 구현하였다. 본 논문에서는 실제 실험을 통해 얻어진 데이터베이스를 기반으로 제안된 알고리즘을 검증하였고, 기존의 방식보다 나은 성능을 보임을 확인하였다.
위의 과정을 통해 실제 도면상에서 의미하는 값들을 얻어낸 후, 도면상에 가상으로 배치를 해본 후 그렇게 배치했을 경우의 커버율(Cover Rate, C과 간섭율 (Interference Rate, IR)을 계산한다. 이때, 커버율과 간섭율은 식⑺, ⑻과 같이 계산된다.
[그림 3]에서 나타내는 바와 같이 먼저 초기화 과정을 통해 무작위로 처음 세대를 생성한다. 이때 본 논문이 제안한 인코딩 방식을 사용하며, 안테나를 설치할 위치, 안테나 대수정보가 결정된다. 그 다음 현재 세대 각 개체들의 적합도를 계산하여, 각 개체들의 적합도를 기준으로 다음 세대를 만들 부모 세대를 선택한다.
이를 위해 실제 전파 특성 데이터를 분석, 데이터베이스화하고 거리에 따른 실제 실험 데이터를 활용하여 적용하였다. 단순한 원반 형태가 아닌 실제 전파 특성과 비슷한 형태의 안테나 모델을 활용하였으며, 안테나 이득의 변화에 따라 인식 거리가 달라진다는 점에 착안하여 다양한 안테나 이득을 적용하여 서로 다른 인식 거리를 갖는 안테나들이 적용 될 수 있도록 하였다.
유전자 형태가 바이너리 코드가 아닌 실수 형 인자들을 사용할 것이기 때문에 그에 맞도록 기법들을 선택할 필요가 있다. 특별히 본 논문에서 새롭게 제안한 유전자 형태가 각기 독립적인 4개의 부분으로 나누어져 있는 형태이기 때문에, 각 부분에 독립적으로 유전자 연산자를 적용하도록 제안하였다.
그 후 RFID 리더기의 이더넷 포트(Ethernet port)를 통해 네트워크에 연결한다. 특별히 본 논문의 실험을 위해서 RHD 리더기의 Subnet에 설정되어 있는 고정 IP를 이용하여 이더 넷 라우터 (Ethernet router)를 사용하였다. 직 렬 케이블을 리더기와 PC 사이에 연결하고 하이퍼 터미널을 사용하여 접속 후 사용하였다.
대상 데이터
가로 세로 8.35m의 로비를 가상으로 생성하여 실험을 진행하였다. 각 모서리 부분에 기등으로 판단되는 장애물 영역이 존재하도록 하였다.
본 논문에서는 LS산전의 IU9003과 Alien technology 의 ALR 9800를 사용하여 실험을 진행하였다. 실험은 [그림 기과 같이 구성하였다.
이론/모형
이는 이전 세대에서 가장 우수한 개체를 다음 세대에 전달하는 방식으로 빠른 수렴 속도를 얻을 수 있다는장점이 있다. 그리고 나머지 부모 세대를 선택하는 데에는 일대일 토너먼트 방식을 사용하였다.
이와 같이 문제를 확장할 경우, 기존의 위상 수학(Topological mathematics), 즉 정확한 해(Exact solution) 찾는 방법으로는 해결하기 어렵다' 이렇게 탐색 공간이 넓고’ 일반적인 규칙성을 찾아보기 힘든 경우, 최적화를 위해서 발견적 탐색 방법 (Heuristic search methods)을 주로 사용한다. 본 논문에서도 발견적 탐색 방법 중 대표적인 진화 연산 알고리즘(Evolutionary algorithm, EA) 을 활용하였다. 진화 연산 알고리즘의 경우, 발견적 탐색 방법 중에서도 지역적 극점이 많이 존재하는 문제 (Multi naodal problem)에서 지역적 극소 점(Local minimum)에 빠지지 않고 전역적 최소 점(Global minimum)을 찾아갈 수 있는 능력이 탁월하다는 장점이 있다.
부모 세대를 선택하기 위해서 먼저 엘리티즘 (Elitism)을 사용했다. 이는 이전 세대에서 가장 우수한 개체를 다음 세대에 전달하는 방식으로 빠른 수렴 속도를 얻을 수 있다는장점이 있다.
있는 최적화 엔진 모듈이 존재한다. 안테나 모델을 구축하기 위해 사용될 실제 안테나 실험을 통해 얻어진 데이터를 모아놓은 데이터베이스가 존재하며, 사용자는 UI를 통해 안테나 데이터베이스와 시뮬레이션 모듈에 모두 접근 가능하며, 바로 시뮬레이션 모듈을 통해 최적 배치 진화 연산 알고리즘을 적용한다.
설계하였다. 앞의 세 그룹은 진화 초기에는 보다 넓은 영역을 탐색하고, 진화가 진행 될수록 탐색 영역을 좁히는 형태의 불균등 돌연변이(Non uniform mutation) 기법을 사용하였다. 하지만 마지막 네 번째 그룹은 0과 1로 이루어진 이진수 형태이기 때문에 일반적인 단순 돌연변이를 활용하였다.
단순한 원반 형태가 아닌 실제 전파 특성과 비슷한 형태의 안테나 모델을 활용하였으며, 안테나 이득의 변화에 따라 인식 거리가 달라진다는 점에 착안하여 다양한 안테나 이득을 적용하여 서로 다른 인식 거리를 갖는 안테나들이 적용 될 수 있도록 하였다. 이를 해결하기 위해 메타 휴리스틱 서치 기법 중 가장 일반적으로 널리 사용되고 있는 진화 연산 알고리즘(EA) 을 사용하였다[9]. 그리고 RFID 안테나 배치 문제에 적합한 새로운 인코딩 기법을 제안하였다.
성능/효과
안테나의 커버율과 간섭율을 조합하여 적합도 함수를 구현하였다. 본 논문에서는 실제 실험을 통해 얻어진 데이터베이스를 기반으로 제안된 알고리즘을 검증하였고, 기존의 방식보다 나은 성능을 보임을 확인하였다. 하지만 아직 진화 초기 유전자들이 무작위로 선정되기 때문에 진화가 수렴하기까지 오랜 시간이 걸린다는 단점이 있다.
하지만 100세대 정도 되었을 때, 어느 정도 수렴했다고 볼 수 있기 때문에 여기에서 진화를 멈추었다. 이때 최종적으로 커버율이 45%, 간섭율이 10.29% 되도록 하는 RHD 안테나 배치 결과를 얻을 수 있었다.
하지만 100세대 정도 되었을 때, 어느 정도 수렴했다고 볼 수 있기 때문에 여기에서 진화를 멈추었다. 이때 최종적으로 커버율이 95.45%, 간섭율이 10.四% 되도록 하는 RFID 안테나 배치 결과를 얻을 수 있었다.
또한 사용자가 가중치를 조절 가능하도록 적합도 함수를 도출하여 진화 연산 알고리즘을 설계하였으며, 새로운 인코딩 방법에 맞도록 진화 연산자들 추가 제안하였다. 제안된 진화 연산 알고리즘의 성능을 평가한 결과 매 세대 얻어진 최우수 개체(Elite)의 적합도 값은 진화가 진행 될수록 적합도가 전체적으로 증가하였으며, 만약 세대 수를 늘려 진화를 계속 할 경우 더 좋은 값을 찾을 수도 있을 것이다. 하지만 100세대 정도 되었을 때, 어느 정도 수렴했다고 볼 수 있기 때문에 여기에서 진화를 멈추었다.
후속연구
하지만 아직 진화 초기 유전자들이 무작위로 선정되기 때문에 진화가 수렴하기까지 오랜 시간이 걸린다는 단점이 있다. 향후 연구는 유전자 초기화 단계에서 가능성 이 있는 유전자들을 미리 선출하여 연산 속도를 향상시키는 것이다.
참고문헌 (10)
http://www.impinj.com
김현태, 지용관, 박장현, "RFID 를 이용한 이동 로봇의 위치 추정을 위한 실내 공간에서의 태그 배치 알고리듬", 대한기계학회 2006년도 춘계학술대회 강연 및 논문 초록집, pp.1370-1375, 2006.
Nissan Lev-Tov and David Peleg, "Exact Algorithms and Approximation Schemes for Base Station Placement Problems," LNCS, Vol.2368/2002, pp.15-27, 2002(1).
Nissan Lev-Tov and David Peleg, "Polynomial time approximation schemes for base station coverage with minimum total radii," Computer Networks, pp.489-501, 2005(3).
Silvio Priem Mendes, Juan A. G.mez Pulido, Miguel A. Vega Rodr.guez, Mar.a D. Jara.z Sim.n, Juan M. S.nchez P.rez, "A Differential Evolution Based Algorithm to Optimize the Radio Network Design Problern," Second IEEE International Conference on e-Science and Grid Computing, 2000. e-Science '06, pp.116-119, 2000(12).
Hai Deng, "Perlonnance Enhancement of Radio Frequency Identification (RFID) Using Spread Spectrum Technology", Antennas and Propagation Society International Symposium, pp.1205-1208, 2007(6).
Qiang Guan, Yu Liu, Yiping Yang, Wenshneg Yu, "Genetic Approach for Network Planning in the RFID Systems," Sixth International Conference on Intelligent Systems Design and Applications, pp.567-572, 2006(10),
Chun-Fu Lin, Frank Yeong-Sung Lin, "A Simulated Annealing Algorithm for RFID Reader Networks," Wireless Communications and Networking Conference, pp.1669-1672, 2007(3)
Silvio Priem-Mendes, Juan A. Gomez-Pulido, Miguel A. Vega-Rodriguez, Antonio M. Pereira, Juan M. Sanchez Perez, "Fast Wide Area Network Design Optimisation Using Differential Evolution," International Conference on Advanced Engineering Computing and Applications in Sciences, pp.3-10, 2007(11).
황희수, Evolutionary Computer and Evolutionary Design by Computer, 내하출판사, 2002.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.