KR101201029B1

KR101201029B1 - Ｕｗｂ시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법

Info

Publication number: KR101201029B1
Application number: KR1020110109713A
Authority: KR
Inventors: 이영포; 정다해; 강승구; 김준환; 윤석호
Original assignee: 성균관대학교산학협력단
Priority date: 2011-10-26
Filing date: 2011-10-26
Publication date: 2012-11-14
Anticipated expiration: 2031-10-26

Abstract

본 발명의 일 실시예에 따른 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법은 UWB 시스템에서 신호획득을 위한 LJK 탐색 알고리즘 또는 BR 탐색 알고리즘이 수행되는 S1 단계, S1 단계에서 탐색 알고리즘을 이용한 신호획득 시간(M)이 m에 수행될 확률이 산출되는 S2 단계 및 S2 단계에서 산출된 확률을 이용하여 LJK 탐색 알고리즘 또는 BR 탐색 알고리즘의 평균신호획득시간이 산출되는 S3 단계를 포함한다.
본 발명에서 제안한 분석 방법은 실제적인 채널 환경에서 UWB 신호획득을 위한 LJK 및 BR 알고리즘의 정확한 MAT 성능을 분석할 수 있는 툴로서 널리 활용될 수 있을 것으로 기대된다

Description

ＵＷＢ시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법{METHOD FOR ANALYZING PERFORMANCE OF SEARCHING ALGORITHM FOR TIME ACQUISITION IN UWB SYSTEM}

본 발명은 초광대역 (ultra-wideband: UWB) 시스템에서 신호획득을 수행하는 탐색 알고리즘의 성능을 분석하기 위한 방법에 관한 것이다. 특히 본 발명은 전체 탐색 상태의 수(N) 대 다중 대립가설의 수(K)의 비(N/K)가 정수가 아닌 경우에도 적용가능한 탐색 알고리즘의 성능을 분석하기 위한 방법에 관한 것이다.

UWB 통신은 무선 통신에서의 저비용, 낮은 전력 소비, 높은 데이터 전송률을 지향하고 있는 IEEE 802. 15.3a 표준의 핵심 기술이다.

UWB 시스템은 다양한 홈 네트워킹에 적용될 예정인데, 실내 무선통신 환경에서는 고밀도 다중경로의 영향으로 신호획득에 큰 어려움이 있다. 따라서 UWB 시스템이 사용되는 실내 무선통신 환경에서는, 다수의 H₁을 고려해야 한다. 여기서 H₁은 가설 검정을 (hypothesis testing) 통한 신호 검파에서 대립 가설을 (alternative hypothesis) 의미하고, H₀는 귀무 가설을 (null hypothesis) 나타낸다.

실내 무선통신 환경에서 UWB 통신을 위한 신호획득을 위해 선형 (Linear) 탐색, LJK (look and jump by K bins) 탐색, BR (bit reversal) 탐색과 같은 다중 H₁ 을 고려한 알고리즘들이 제시되었다.

Aedudodla의 연구에서는 LJK 와 BR 탐색 알고리즘에 대한 평균 획득 시간이 (mean acquisition time: MAT) 제시되었지만, 전체 탐색 상태의 수 N 대 다중 H₁의 수 K의 비 N/K가 정수인 경우에 대해서만 고려를 하였기 때문에 N/K가 정수가 아닐 경우에는 정확한 MAT를 구할 수 없다 (S. R. Aedudodla, S. Vijayakumaran, and T. F. Wong, “Timing acquisition in ultra-wideband communication systems,” IEEE Trans. Vehicular Technology, vol. 54, no. 5, Sep. 2005. 참조).

Homier도 유사한 연구를 수행하였으나 역시 N/K가 정수가 아닐 경우에는 정확한 MAT를 구할 수 없다는 문제점이 있었다 (E. A. Homier and R. A. Scholtz, “Rapid acquisition of ultrawideband signals in the dense multipath channel,” Proc. IEEE UWBST, pp. 105-109, Baltimore, MD, May 2002. 참조).

본 발명에 따른 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법은 다음과 같은 해결과제를 목적으로 한다.

첫째, UWB 시스템의 신호획득을 위한 탐색 알고리즘의 성능을 분석하고자 한다.

둘째, UWB 시스템의 신호획득을 위한 탐색 알고리즘 중 LJK 탐색 알고리즘 및 BR 탐색 알고리즘에 대한 성능을 분석하고자 한다.

셋째, LJK 탐색 알고리즘 및 BR 탐색 알고리즘에서 N/K가 정수가 아닌 경우에도 성능을 분석하는 방법을 제공하고자 한다.

본 발명의 해결과제는 이상에서 언급된 것들에 한정되지 않으며, 언급되지 아니한 다른 해결과제들은 아래의 기재로부터 당업자에게 명확하게 이해될 수 있을 것이다.

본 발명에 따른 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법은 UWB 시스템에서 신호획득을 위한 LJK (look and jump by K bins) 탐색 알고리즘이 수행되는 S1 단계, S1 단계에서 탐색 알고리즘을 이용한 신호획득이 신호획득 시간(M)이 m에 수행될 확률(P _LJK{M = m}, m = 1,2,...,N/K)이 산출되는 S2 단계 및 S2 단계에서 산출된 확률(P _LJK{M = m})을 이용하여 LJK 탐색 알고리즘의 평균신호획득시간이 산출되는 S3 단계를 포함한다.

UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법은 전체 탐색 상태의 수(N) 대 다중 대립가설의 수(K)의 비(N/K)가 정수인 경우 및 N/K가 정수가 아닌 경우에 적용되는 것을 특징으로 한다.

S3 단계의 평균신호획득시간(

)은 아래의 식으로 표현되는 것을 특징으로 한다.

여기서, N은 전체 탐색 상태의 수, K는 다중 대립가설의 수, mod는 모듈로 연산자를 의미하고,

와

는 각각 버림과 올림 연산을 의미한다.

본 발명의 다른 측면에 따른 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법은 UWB 시스템에서 신호획득을 위한 BR (bit reversal) 탐색 알고리즘이 수행되는 S1 단계, S1 단계에서 탐색 알고리즘을 이용한 신호획득이 신호획득 시간(M)이 m에 수행될 확률(P _BR{M = m}, m = 1,2,...,N/K)이 산출되는 S2 단계 및 S2 단계에서 산출된 확률(P _BR{M = m})을 이용하여 BR 탐색 알고리즘의 평균신호획득시간이 산출되는 S3 단계를 포함한다.

상기 S3 단계의 평균신호획득시간(

)은 아래의 식으로 표현되는 것을 특징으로 한다.

여기서, N은 전체 탐색 상태의 수, K는 다중 대립가설의 수이고, 여기서 X와 Y는 X > K, Y ≤ K를 만족하는 자연수로서 2ⁿ의 형태를 가진다 (n = 1,2,...).

본 발명에 따른 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법은 LJK와 BR 탐색 알고리즘에 대하여 N/K가 정수가 아닐 때도 적용 가능한 일반화된 MAT 표현 분석을 수행한다. K는 다중경로의 수에 따라서 정해지므로 실제적인 채널 환경에서는 N/K가 정수가 아닌 경우가 많으며, 따라서 본 발명에서 제안한 분석 방법은 실제적인 채널 환경에서 UWB 신호획득을 위한 LJK 및 BR 알고리즘의 정확한 MAT 성능을 분석할 수 있는 툴로서 널리 활용될 수 있을 것으로 기대된다.

본 발명의 효과는 이상에서 언급된 것들에 한정되지 않으며, 언급되지 아니한 다른 효과들은 아래의 기재로부터 당업자에게 명확하게 이해될 수 있을 것이다.

도 1은 UWB 시스템의 일반적인 신호획득 과정을 도시한 구성도이다.
도 2는 N = 1024인 경우에 대하여 LJK 및 BR 탐색 알고리즘의 실제 MAT와 수학식 3으로 표현되는 방법으로 구한 MAT와의 차이를 도시한 그래프이다.
도 3은 본 발명에 따른 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법의 순서를 개략적으로 도시한 순서도이다.
도 4는 N = 1024인 경우에 대하여 LJK 탐색 알고리즘의 실제 MAT와 본 발명에서 제안한 방법으로 구한 MAT와의 차이를 비교한 그래프이다.
도 5는 N = 1024인 경우에 대하여 BR 탐색 알고리즘의 실제 MAT와 본 발명에서 제안한 방법으로 구한 MAT와의 차이를 비교한 그래프이다.

본 발명은 다양한 변경을 가할 수 있고 여러 가지 실시예를 가질 수 있는 바, 특정 실시예들을 도면에 예시하고 상세하게 설명하고자 한다. 그러나, 이는 본 발명을 특정한 실시 형태에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다.

제1, 제2, A, B 등의 용어는 다양한 구성요소들을 설명하는데 사용될 수 있지만, 해당 구성요소들은 상기 용어들에 의해 한정되지는 않으며, 단지 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만 사용된다. 예를 들어, 본 발명의 권리 범위를 벗어나지 않으면서 제1 구성요소는 제2 구성요소로 명명될 수 있고, 유사하게 제2 구성요소도 제1 구성요소로 명명될 수 있다. 및/또는 이라는 용어는 복수의 관련된 기재된 항목들의 조합 또는 복수의 관련된 기재된 항목들 중의 어느 항목을 포함한다.

본 명세서에서 사용되는 용어에서 단수의 표현은 문맥상 명백하게 다르게 해석되지 않는 한 복수의 표현을 포함하는 것으로 이해되어야 하고, "포함한다" 등의 용어는 설시된 특징, 개수, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것이 존재함을 의미하는 것이지, 하나 또는 그 이상의 다른 특징들이나 개수, 단계 동작 구성요소, 부분품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 배제하지 않는 것으로 이해되어야 한다.

이하에서는 도면을 참조하면서 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법에 관하여 구체적으로 설명하겠다.

도면에 대한 상세한 설명을 하기에 앞서, 본 명세서에서의 구성부들에 대한 구분은 각 구성부가 담당하는 주기능 별로 구분한 것에 불과함을 명확히 하고자 한다. 즉, 이하에서 설명할 2개 이상의 구성부가 하나의 구성부로 합쳐지거나 또는 하나의 구성부가 보다 세분화된 기능별로 2개 이상으로 분화되어 구비될 수도 있다. 그리고 이하에서 설명할 구성부 각각은 자신이 담당하는 주기능 이외에도 다른 구성부가 담당하는 기능 중 일부 또는 전부의 기능을 추가적으로 수행할 수도 있으며, 구성부 각각이 담당하는 주기능 중 일부 기능이 다른 구성부에 의해 전담되어 수행될 수도 있음은 물론이다.

먼저 UWB 시스템에서의 신호획득 과정에 대해 간략하게 살펴보기로 한다. 도 1은 UWB 시스템의 일반적인 신호획득 과정을 도시한 구성도이다.

UWB 시스템에서 시간-도약 패턴을 (time-hopping) 지닌 송신 신호는 아래의 수학식 1과 같이 표현된다.

여기서

는 2차 미분된 가우시안 펄스, T _f는 프레임 시간, T _C는 칩 지속 시간, c _n은 N _c의 주기를 갖는 시간-도약 시퀀스, d _n은 정보 신호로 인해 변조된 펄스 위상을 나타낸다. 본 발명에서는 신호획득 과정 동안에는 d _n=0 (데이터의 변조가 없음)이라고 가정한다.

채널의 임펄스 응답은

과 같이 표현된다. 여기서

는 디락 델타 함수,

은

번째 경로의 진폭 감쇄 파라미터, L은 다중 경로의 수,

은

번째 경로의 시간 지연을 각각 나타낸다. 다중 H₁ 은

인 상태에 해당되고, 여기서

은 수신기에서 생성된 참조 신호의 시간 지연이다. 채널을 통과한 후의 수신된 신호는 아래의 수학식 2와 같이 표현된다.

여기서 n(t)는 전력 스펙트럼 밀도가 N ₀인 덧셈꼴 백색 정규잡음, *는 컨벌루션 연산이다.

수신된 신호 r(t)는 참조 신호 생성기에서 생성된 참조 신호와의 상관값을 계산하여, 주어진 문턱값과 비교를 하게 된다. 상관값이 문턱값을 넘으면 부호 획득 과정이 종료되고 추적 과정이 초기화된다. 상관값이 문턱값보다 작은 경우, 탐색 알고리즘에 의해 선택된 새로운

을 참조 신호에 적용하여, 상기 과정을 반복한다.

기존 대역확산 시스템의 획득 과정에서는 하나의 H₁이 존재한다고 가정을 하고 신호획득을 실시하였다. 하지만 실내 환경 등의 고밀도 다중 경로 환경에서 적용되는 UWB 시스템의 경우 다중 경로의 영향을 고려하여, 하나의 H₁이 아닌 다중 H₁을 고려하여 신호획득 과정을 실시하게 된다. 또한 빠른 신호획득을 위하여 UWB 시스템에서는 LJK 탐색과 BR 탐색 알고리즘을 적용하고 있다.

E. A. Homier and R. A. Scholtz, “Rapid acquisition of ultrawideband signals in the dense multipath channel,”(Proc. IEEE UWBST, pp. 105-109, Baltimore, MD, May 2002.)에서 LJK 및 BR 탐색 알고리즘에 대한 기존 MAT 표현은 아래의 수학식 3과 같이 제시하였다. 수학식 3은 검파 확률= 1, 오경보 확률= 0 인 상황에서 산출된 것이다.

여기서

은 평균 연산자, M은 획득 시간 (단위: T _c), N은 전체 탐색 상태의 수,

는 다중 H₁의 수와 같다. 그러나 상기의 수학식 3으로 제시한 MAT 표현은 N/K가 정수인 경우에만 (BR 탐색 알고리즘인 경우 N은 자연수인 경우에만) 유효한 식이다.

도 2는 N = 1024인 경우에 대하여 LJK 및 BR 탐색 알고리즘의 실제 MAT와 수학식 3으로 표현되는 방법으로 구한 MAT와의 차이를 도시한 그래프이다. 도 2를 살펴보면, N/K가 정수가 아닌 경우에는 수학식 3을 통해 구한 MAT와 실제 MAT값이 차이가 있음을 확인할 수 있다.

본 발명에서는 N/K가 정수가 아닌 일반적인 경우를 고려한 MAT 수식을 아래의 수학식 4와 같이 유도한다. 신호획득이 신호획득 시간(M)이 m에 수행될 확률(P{M=m})은 m= 1,2,...N/K에 대해서 다음과 같이 나타낼 수 있다.

여기서

와

는 각각 버림과 올림 연산을 나타내고, mod는 모듈로 연산을 나타낸다. 따라서 상기 확률들을 이용하여 LJK 탐색 알고리즘에 대한 일반화된 MAT 표현을 아래의 수학식 5와 같이 얻을 수 있다.

한편 유사한 접근 방식을 통해 BR 탐색 알고리즘에 대한 일반화된 MAT 표현을 아래의 수학식 6과 같이 얻을 수 있다. 여기서 X와 Y는 X > K, Y ≤ K를 만족하는 자연수로서 2ⁿ의 형태를 가진다 (n = 1,2,...).

본 발명의 일 실시예에 따른 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법은 UWB 시스템에서 신호획득을 위한 LJK (look and jump by K bins) 탐색 알고리즘이 수행되는 S1 단계, S1 단계에서 탐색 알고리즘을 이용한 신호획득이 신호획득 시간(M)이 m에 수행될 확률(P _LJK{M = m})이 산출되는 S2 단계 및 S2 단계에서 산출된 확률(P _LJK{M = m}, m = 1,2,...,N/K)을 이용하여 LJK 탐색 알고리즘의 평균신호획득시간이 산출되는 S3 단계를 포함한다.

UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법은 전체 탐색 상태의 수(N) 대 다중 대립가설의 수(K)의 비(N/K)가 정수인 경우 및 N/K가 정수가 아닌 경우에 모두 적용이 가능하다.

S3 단계의 평균신호획득시간은 (

) 상기 수학식 5로 표현된다.

본 발명의 다른 실시예에 따른 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법은 UWB 시스템에서 신호획득을 위한 BR (bit reversal) 탐색 알고리즘이 수행되는 S1 단계, S1 단계에서 탐색 알고리즘을 이용한 신호획득이 신호획득 시간(M)이 m에 수행될 확률(P _BR{M = m})이 산출되는 S2 단계 및 S2 단계에서 산출된 확률(P _BR{M = m}, m = 1,2,...,N/K)을 이용하여 BR 탐색 알고리즘의 평균신호획득시간이 산출되는 S3 단계를 포함한다.

이 실시예도 전체 탐색 상태의 수(N) 대 다중 대립가설의 수(K)의 비(N/K)가 정수인 경우 및 N/K가 정수가 아닌 경우에 적용이 가능하다.

S3 단계의 평균신호획득시간은 (

) 상기의 수학식 6으로 표현된다.

도 4는 N = 1024인 경우에 대하여 LJK 탐색 알고리즘의 실제 MAT와 본 발명에서 제안한 방법을 통해 구한 MAT를 비교한 그래프이다. 도 5는 N = 1024인 경우에 대하여 BR 탐색 알고리즘의 실제 MAT와 본 발명에서 제안한 방법을 통해 구한 MAT를 비교한 그래프이다.

도 4 및 도 5를 살펴보면, LJK와 BR 탐색 알고리즘에서 실제 MAT와 본 발명에 따른 수학식 5와 수학식 6의 MAT가 동일한 것을 확인할 수 있다.

본 실시예 및 본 명세서에 첨부된 도면은 본 발명에 포함되는 기술적 사상의 일부를 명확하게 나타내고 있는 것에 불과하며, 본 발명의 명세서 및 도면에 포함된 기술적 사상의 범위 내에서 당업자가 용이하게 유추할 수 있는 변형 예와 구체적인 실시예는 모두 본 발명의 권리범위에 포함되는 것이 자명하다고 할 것이다.

Claims

UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법에 있어서,
상기 UWB 시스템에서 신호획득을 위한 LJK (look and jump by K bins) 탐색 알고리즘이 수행되는 S1 단계;
상기 S1 단계에서 탐색 알고리즘을 이용한 신호획득이 신호획득 시간(M)이 m에 수행될 확률(P _LJK{M = m}, m = 1,2,...,N/K)이 산출되는 S2 단계; 및
상기 S2 단계에서 산출된 확률(P _LJK{M = m})을 이용하여 LJK 탐색 알고리즘의 평균신호획득시간이 산출되는 S3 단계를 포함하는 것을 특징으로 하는 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법.
제1항에 있어서,
상기 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법은
전체 탐색 상태의 수(N) 대 다중 대립가설의 수(K)의 비(N/K)가 정수인 경우 및 N/K가 정수가 아닌 경우에 적용되는 것을 특징으로 하는 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법.
제1항에 있어서,
상기 S3 단계의 평균신호획득시간(
)은 아래의 식으로 표현되는 것을 특징으로 하는 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법.

(여기서, N은 전체 탐색 상태의 수, K는 다중 대립가설의 수, mod는 모듈로 연산자를 의미하고,
와
는 각각 버림과 올림 연산을 의미함.)
UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법에 있어서,
상기 UWB 시스템에서 신호획득을 위한 BR (bit reversal) 탐색 알고리즘이 수행되는 S1 단계;
상기 S1 단계에서 탐색 알고리즘을 이용한 신호획득이 신호획득 시간(M)이 m에 수행될 확률(P _BR{M = m}, m = 1,2,...,N/K)이 산출되는 S2 단계; 및
상기 S2 단계에서 산출된 확률(P _BR{M = m})을 이용하여 BR 탐색 알고리즘의 평균신호획득시간이 산출되는 S3 단계를 포함하는 것을 특징으로 하는 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법.
제4항에 있어서,
상기 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법은
전체 탐색 상태의 수(N) 대 다중 대립가설의 수(K)의 비(N/K)가 정수인 경우 및 N/K가 정수가 아닌 경우에 적용되는 것을 특징으로 하는 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법.
제4항에 있어서,
상기 S3 단계의 평균신호획득시간(
)은 아래의 식으로 표현되는 것을 특징으로 하는 UWB 시스템의 신호획득을 위한 탐색 알고리즘 성능 분석 방법.

(여기서, N은 전체 탐색 상태의 수, K는 다중 대립가설의 수, 여기서 X와 Y는 X > K, Y ≤ K를 만족하는 자연수로서 2ⁿ의 형태를 가짐 (n = 1,2,...))