KR101874259B1

KR101874259B1 - 링크 성능과 지연 시간 사이의 트레이드 오프를 고려한 mtc를 위한 압축 센싱 기반 랜덤 액세스 방법 및 시스템

Info

Publication number: KR101874259B1
Application number: KR1020170140302A
Authority: KR
Inventors: 장경희; 하유경; 진완; 석림
Original assignee: 인하대학교 산학협력단
Priority date: 2017-10-26
Filing date: 2017-10-26
Publication date: 2018-07-03

Abstract

링크 성능, 복잡도 및 지연 시간 사이의 트레이드 오프를 고려한 MTC를 위한 압축 센싱 기반 랜덤 액세스 방법 및 시스템이 개시된다. MTC(Machine Type Communication)를 위한 압축 센싱 기반의 랜덤 액세스 방법에 있어서, 링크 성능, 복잡도 및 지연 시간(latency) 간의 트레이드오프(tradeoff)에 기초하여 GOMP 기반의 복수의 랜덤 액세스 알고리즘 중 랜덤 액세스에 이용될 어느 하나의 알고리즘을 결정하는 단계, 및 결정된 알고리즘에 기초하여 랜덤 액세스를 수행하는 단계를 포함할 수 있다.

Description

링크 성능과 지연 시간 사이의 트레이드 오프를 고려한 MTC를 위한 압축 센싱 기반 랜덤 액세스 방법 및 시스템{METHOD AND SYSTEM FOR PERFORMING RANDOM ACCESS BASED ON COMPRESSIVE SENSING FOR MACHINE TYPE COMMUNICATIONS CONSIDERING TRADEOFF BETWEEN LINK PERFORMANCE AND LATENCY}

본 발명의 실시예들은 대규모 연결(massive connectivity) 및 산발적인 트래픽 요구 사항(sporadic traffic requirements)을 지원하는 압축 센싱(compressive sensing, CS) 기반의 랜덤 액세스 기술에 관한 것이다.

최근 몇 년 동안 기계식 통신(machine type communications, MTC)을 사용하는 어플리케이션이 엄청나게 증가하였다. 그러나, MTC 장치들 다수는 그들의 신호 오버 헤드 및 지연 시간으로 인한 초과 비용으로 인하여 기존의 랜덤 액세스 방식에 문제점을 발생시킨다.

아래의 비특허 문헌 [ 1]M Hasan , E Hossain , D Niyato , Random access for machine-to-machine communication in LTE -advanced networks: issues and approaches. IEEE Communications Magazine. 51(6), 86-93 (2013).에서는 MTC 시스템을 제시하고 있다. MTC 시스템에서, 제곱 킬로미터 당 수십만 개의 센서 노드가 네트워크에 연결되며, 이러한 연결은 필연적으로 현재 통신 네트워크에서 혼잡 및 과부하를 발생시킨다. 예를 들어, 아래의 비특허 문헌 [2] SY Lien, KC Chen, Y Lin, Toward ubiquitous massive accesses in 3GPP machine-to-machine communications. IEEE Communications Magazine. 49(4), 66-74 (2011).에 제시된 LTE-A 시스템에서는 제어 채널 요소(control channel element, CCE)를 사용하여 수십 개의 장치만을 지원 가능하다.

또한, 신호 오버 헤드에 대한 높은 비용을 갖는 현재의 랜덤 액세스 표준은 작은 패킷 크기와 낮은 데이터 속도를 특징으로 하는 MTC에 비효율적이다. LTE 시스템에서, 네트워크에 액세스하기 위해, 사용자 단말(UE)은 E-UTRAN NodeB(eNB)에 스케줄링 요청을 보내고 응답을 기다려야 한다. 충돌을 무시하더라도, 요청 승인 절차(request-grant procedure)에서 7ms의 액세스 지연 시간이 존재하며, 이러한 액세스 지연 시간으로 인해 산업 자동화 및 의료 등과 같이 업무에 중대한 MTC 어플리케이션의 엄격한 지연 제약을 충족시키지 못하게 된다.

이러한 랜덤 액세스 문제에 효율적으로 대처하기 위해, 낮은 신호 오버 헤드 및 MTC에 대한 낮은 지연 시간을 갖는 랜덤 액세스의 새로운 접근법이 요구된다. 아래의 비특허 문헌 [3] C Bockelmann , HF Schepker , Compressive sensing based multi-user detection for machine-to-machine communication. Transaction on Emerging Telecommunications Technologies. 24(44), 384-400 (2013).에서는 센서 노드가 직접 요청 승인 절차를 거치지 않고 액세스 포인트 (AP)로 자신들의 데이터를 송신하는 CS에 기반한 랜덤 액세스 방식을 제시하고 있다. 이때, 서로 다른 센서 노드를 구별하기 위해, CDMA(Code Division Multiple Access)가 사용되며, 이는 다양한 데이터 속도와 서비스 품질을 지원하는 유연성으로 인해 MTC에 매우 효과적이다. 그러나, 센서 노드의 수가 굉장히 많기 때문에, CDMA 시스템은 센서 노드의 수가 확산 계수보다 클 경우 과부화될 수 있고, 이는 미정(underdetermined) 시스템 방정식을 초래할 수 있다.

그리고, MTC 시스템에서, 센서 노드는 대부분 비활성 상태이므로 산발적인 트래픽이 발생한다. 따라서, 수신 측에서, 네트워크 내의 모든 센서 노드로부터 전송된 모든 데이터를 포함하는 수신 신호는 희박(sparse)해 진다. 미정 방정식에서 이 희박한 신호는 CS 이론을 사용하여 추정 가능하다. 그러나, MTC에 대한 기존의 CS 기반의 랜덤 액세스 방법(예컨대, 다중 시퀀스 확산을 사용한 CS 기반 랜덤 액세스 기법, CS 감지기에 채널 디코더를 도입한 방법 등)은 대부분 계산 복잡도(complexity)와 지연시간(latency)를 증가시킨다.

따라서, 링크성능, 복잡도 및 지연시간을 고려하여 MTC에 대한 기존의 CS 기반의 랜덤 액세스 방법을 개선한 기술이 요구된다. 즉, 5세대(5G) 이동 통신에서 다양한 서비스 시나리오의 요구 사항을 고려하여, 다양한 어플리케이션에서 사용 가능한 CS 기반의 랜덤 액세스 알고리즘이 요구된다.

한국등록특허 제10-1701421호는 다중 시퀀스 확산을 이용한 랜덤 접속 및 다중 사용자 검출 방법에 관한 것으로, 사용자 장치가 별도의 자원 할당 및/또는 확산 시퀀스 할당과정 없이 복수의 확산 시퀀스 집합 중 하나의 확산 시퀀스 집합을 선택하고, 사용자 장치가 하나의 확산 시퀀스 집합에 포함된 복수의 확산 시퀀스 각각을 그룹 내에 포함된 복수의 심볼 각각에 적용하고, 사용자 장치가 복수의 확산 시퀀스 각각을 기반으로 확산된 복수의 심볼 각각을 전송하는 기술을 개시하고 있다.

[1] M Hasan, E Hossain, D Niyato, Random access for machine-to-machine communication in LTE-advanced networks: issues and approaches. IEEE Communications Magazine. 51(6), 86-93 (2013). [2] SY Lien, KC Chen, Y Lin, Toward ubiquitous massive accesses in 3GPP machine-to-machine communications. IEEE Communications Magazine. 49(4), 66-74 (2011). [3] C Bockelmann, HF Schepker, Compressive sensing based multi-user detection for machine-to-machine communication. Transaction on Emerging Telecommunications Technologies. 24(44), 384-400 (2013). [4] AT Abebe, CG Kang, Iterative order recursive least square estimation for exploiting frame-wise sparsity in compressive sensing-based MTC. IEEE Communications Letters. 20(5), 1018-1021 (2016). [5] H Zhu, W Chen, B Li, F Gao, An improved square-root algorithm for V-BLAST based on efficient inverse Cholesky factorization. IEEE Transactions on Wireless Communications. 10(1), 43-48 (2011).

본 발명은 다양한 어플리케이션에 대한 랜덤 액세스 기술을 개선하기 위해, 링크 성능, 복잡도 및 지연 시간(latency) 사이의 트레이드 오프(tradeoff)를 고려한 WIGOMP-ICF 알고리즘 기반의 랜덤 액세스 방법을 제공하는 기술에 관한 것이다.

MTC(Machine Type Communication)를 위한 압축 센싱 기반의 랜덤 액세스 방법에 있어서, 링크 성능, 복잡도 및 지연 시간(latency) 간의 트레이드오프(tradeoff)에 기초하여 GOMP 기반의 복수 랜덤 액세스 알고리즘 중 랜덤 액세스에 이용될 어느 하나의 알고리즘을 결정하는 단계, 및 결정된 알고리즘에 기초하여 랜덤 액세스를 수행하는 단계를 포함할 수 있다.

일측면에 따르면, 상기 복수 랜덤 액세스 알고리즘은, GOMP(Group Orthogonal Matching Pursuit)에 최소 자승법(Least Squares, LS)이 적용된 GOMP-LS 알고리즘, 상기 GOMP에 가중 반복(Weighted Iteration)이 적용된 WIGOMP 알고리즘, 및 상기 WIGOMP에 역 콜레스키(cholesky) 인수분해가 적용된 WIGOMP-ICF 알고리즘을 포함할 수 있다.

다른 측면에 따르면, 상기 결정하는 단계는, 서비스하고자 하는 애플리케이션이 미리 정의된 기준 신뢰도 이상의 높은 신뢰도를 요구하는 경우, 상기 GOMP 기반의 복수 랜덤 액세스 알고리즘, WIGOMP-ICF 알고리즘 중 상기 GOMP-LS 알고리즘을 상기 랜덤 액세스에 이용될 알고리즘으로 결정할 수 있다.

또 다른 측면에 따르면, 상기 결정하는 단계는, 서비스하고자 하는 애플리케이션이 미리 정의된 기준 지연 시간 이하의 낮은 지연 시간(latency)를 요구하는 경우, 상기 GOMP 기반의 복수 랜덤 액세스 알고리즘, WIGOMP-ICF 알고리즘 중 WIGOMP 및 WIGOMP-ICF 중 어느 하나를 상기 랜덤 액세스에 이용될 알고리즘으로 결정할 수 있다.

또 다른 측면에 따르면, 상기 랜덤 액세스를 수행하는 단계는, 결정된 알고리즘이 WIGOMP 알고리즘인 경우, 수신 신호를 나타내는 복잡한 문제(complicated problem)를 하위 문제(sub-problems)로 분할하는 단계, 분할된 각 하위 문제 별로 가중치(weight)를 부여하는 단계, 및 부여된 상기 가중치를 조정하여 상기 수신 신호에 포함된 센서 노드에서 전송한 신호를 나타내는 희소 벡터(sparse vector)를 추정하는 단계를 포함할 수 있다.

또 다른 측면에 따르면, 현재 반복(i^th iteration)에 해당하는 하위 문제에 부여된 상기 가중치는 이전 반복((i-1)^th iteration)에 해당하는 하위 문제의 해(solution)의 2-norm의 합으로 조정될 수 있다.

또 다른 측면에 따르면, 결정된 알고리즘이 WIGOMP-ICF 알고리즘인 경우, 수신 신호에 포함된 측정행렬의 부분행렬(sub-matrix), 부분행렬의 허미션 행렬(hermition matrix)을 기반으로 역 콜레스키(cholesky) 인수분해를 이용하여 하위 문제의 해(solution)를 구함으로써, 센서 노드에서 전송한 신호를 추정하는 단계를 포함할 수 있다.

또 다른 측면에 따르면, 상기 부분 행렬과 상기 허미션 행렬의 곱으로 표현되는 특정 변수

의 역 콜레스키 인자(factor)

는 이전 반복에 해당하는 역 콜레스키 인자(factor)

및 V-BLAST기반 제급근 알고리즘(square-root algorithm for V-BLAST based on efficient inverse Cholesky factorization)에 기초하여 계산될 수 있다.

MTC(Machine Type Communication)를 위한 압축 센싱 기반의 랜덤 액세스 시스템에 있어서, 링크 성능, 복잡도 및 지연 시간(latency) 간의 트레이드오프(tradeoff)에 기초하여 GOMP 기반 복수의 랜덤 액세스 알고리즘 중 랜덤 액세스에 이용될 어느 하나의 알고리즘을 결정하는 결정부, 및 결정된 알고리즘에 기초하여 랜덤 액세스를 수행하는 액세스 수행부를 포함할 수 있다.

본 발명은, 다양한 어플리케이션에 대한 랜덤 액세스 기술을 개선하기 위해, 링크 성능, 복잡도 및 지연 시간(latency) 사이의 트레이드 오프(tradeoff)를 고려하여 GOMP(Group Orthogonal Matching Pursuit) 기반의 랜덤 액세스 방법을 제공함으로써, 어플리케이션의 요구 사항에 적합한 랜덤 액세스 기술을 적용할 수 있다. 즉, 지연 시간이 짧은 어플리케이션에 적합한 랜덤 액세스 기술, 링크 성능 개선이 적합한 랜덤 액세스 기술을 적용하여 랜덤 액세스를 수행함으로써, 다양한 어플리케이션의 요구 사항(예컨대, 대규모 연결성, 산발적인 트래픽 요구 등)을 만족시킬 수 있다.

도 1은 본 발명의 일실시예에 있어서, MTC에 대한 랜덤 액세스 시스템 모델을 도시한 도면이다.
도 2는 본 발명의 일실시예에 있어서, 복잡한 문제(complicated problem)를 2개의 간단한 하위 문제(simple sub-problems)로 분할하는 동작을 도시한 도면이다.
도 3은 본 발명의 일실시예에 있어서, CS 기반의 랜덤 액세스 시스템의 내부 구성을 도시한 블록도이다.
도 4는 본 발명의 일실시예에 있어서, CS 기반의 랜덤 액세스 방법을 도시한 흐름도이다.
도 5는 본 발명의 일실시예에 있어서, 랜덤 액세스 시스템에서 수행하는 GOMP-LS 알고리즘의 동작을 도시한 블록도이다.
도 6은 본 발명의 일실시예에 있어서, 랜덤 액세스 시스템에서 수행하는 WIGOMP 알고리즘의 동작을 도시한 블록도이다.
도 7은 본 발명의 일실시예에 있어서, WIGOMP 알고리즘을 도시한 흐름도이다.
도 8은 본 발명의 일실시예에 있어서, 그룹 사이즈 변화에 따른 GOMP 및 GOMP-LS 알고리즘의 BER을 도시한 그래프를 나타낼 수 있다.
도 9는

인 센서 노드의 활성 에러율(sensor node activity error rate)에 대한 활성 확률(activity probability)을 도시한 그래프를 나타낼 수 있다.
도 10은 본 발명의 일실시예에 있어서, 활성 확률과 BER 성능 간의 관계를 도시한 그래프를 나타낼 수 있다.
도 11은 본 발명의 일실시예에 있어서, 활성 확률과 계산 복잡도 간의 관계를 도시한 그래프를 나타낼 수 있다.
도 12는 본 발명의 일실시예에 있어서, 프레임당 심볼의 수에 따른 지연 시간(latency) 변화를 도시한 그래프를 나타낼 수 있다.
도 13은 본 발명의 일실시예에 있어서, 링크 성능, 복잡도 및 지연 시간 간의 트레이드 오프를 고려하여 GOMP 기반 복수 랜덤 액세스 알고리즘들의 장단점을 비교 도시한 블록도이다.

이하, 본 발명의 실시예를 첨부된 도면을 참조하여 상세하게 설명한다.

본 실시예들은 MTC를 위한 압축 센싱(CS) 기반의 랜덤 액세스 기술에 관한 것으로서, 특히, 링크 성능, 복잡도 및 지연 시간(latency) 간의 트레이드 오프(tradeoff) 관계를 고려하여, CS 기반의 랜덤 액세스 알고리즘을 이용하여 센서 노드에서 전송한 송신 신호를 추정하는 기술에 관한 것이다.

본 실시예들에서, CS 기반의 랜덤 액세스 알고리즘들은 "GOMP-LS 알고리즘", "WIGOMP 알고리즘", 및 "WIGOMP-ICF 알고리즘"을 포함하고, "GOMP-LS 알고리즘"은 GOMP(Group Orthogonal Matching Pursuit)에 최소 자승법(Least Squares, LS)이 적용된 알고리즘을 나타내고, "WIGOMP 알고리즘"은 GOMP에 가중 반복(Weighted Iteration)이 추가된 알고리즘을 나타내고, "WIGOMP-ICF 알고리즘"은 WIGOMP에 역 콜레스키(cholesky) 인수분해가 적용된 알고리즘을 나타낼 수 있다.

본 실시예들에서, "CS"는 압축 센싱(compressive sensing)을 나타낼 수 있다.

본 실시예들에서, "랜덤 액세스 시스템"은 사용자 단말(User Equipment, UE)이 액세스 포인트(Access Point, AP)를 액세스하는 업링크(Up-link) 동기 및 자원 할당을 위해 이용되는 시스템을 나타낼 수 있다. 예컨대, GOMP-LS, WIGOMP, 또는 WIGOMP-ICF 알고리즘에 기초하여 수신 신호 y로부터 송신 신호

를 추정하는 경우, 랜덤 액세스 시스템은 추정부를 포함할 수 있으며, 추정부에서 상기 알고리즘에 기초하여 송신 신호

를 추정할 수 있다.

먼저, 본 실시예들에서 이용되는 압축 센싱(compressive sensing) 기술에 대해 설명하고자 한다.

압축 센싱(CS)은 신호의 가장 중요한 정보가 나이키스트 레이트(Nyquist rate)의 요구 사항보다 훨씬 적은 샘플로부터 복구 될 수 있다는 사실에 기반한다. CS 이론에 따르면, 유한 길이(finite length)

을 가지는 실수 이산 시간 신호

는 아래의 수학식 1과 같이 정규직교기준(orthonormal basis)

로 표현될 수 있다.

[수학식 1]

수학식 1에서,

는 상기 신호 의 계수 시퀀스(sequence)로서,

로 표현될 수 있다. 계수

의

만이 0이 아니고,

인 경우, 신호

는 압축 가능하며, 희소성 표현 모델(sparse representation)을 가지며,

로 표현될 수 있다. 그리고,

는

의 희소성 표현 모델(sparse representation)에 해당할 수 있다.

그러면, 상기 희소성 신호(sparse signal)

는

측정 행렬

하에서 압축 측정될 수 있으며, 샘플링된 벡터(sampled vector)

는 아래의 수학식 2와 같이 표현될 수 있다.

[수학식 2]

수학식 2에서,

는 센싱 행렬(sensing matrix)로 표현될 수 있다. 일반적으로 상기

측정 행렬에서,

이

보다 작으므로 미정 방정식(underdetermined equation)에서

로부터

를 복원하는 것은 불가능하나,

가

이고,

인 경우에는 아래의 수학식 3과 같이 표현되는

최소화에 기초하여

로부터

가 복원될 수 있다.

[수학식 3]

이때, 희소성 신호(sparse signal)를 높은 확률로 정확하게 복구하기 위해 여러 알고리즘들이 이용될 수 있다. 예컨대, 매칭 추적(matching pursuit, MP) 알고리즘, 직교 매칭 추적(orthogonal matching pursuit, OMP) 알고리즘, GOMP, 연쇄 결합 추적(chaining pursuit, CP) 등이 이용될 수 있다. OMP는 각 반복(iteration)에서 현재 잔차(residuals)와 가장 관련이 있는 열(column)을 선택하여 희소성 신호(sparse signal)의 지원 집합을 복구할 수 있는 반복 그리디(greedy) 알고리즘에 해당할 수 있다.

이때, 상기 알고리즘들 이외에, 5 세대(5G) 이동 통신에서 다양한 서비스 시나리오의 요구 사항을 고려하여, 다양한 어플리케이션에서 사용 가능한 GOMP 기반 알고리즘들이 이용될 수 있다. 예컨대, 링크 성능, 복잡도 및 지연 시간(latency) 간의 트레이드 오프(tradeoff)를 고려한 GOMP 기반 알고리즘들이 이용될 수 있으며, GOMP에 최소 자승법(Least Square, LS)를 도입한 GOMP-LS 알고리즘, GOMP에 가중된 반복(weighted iteration)을 추가한 WIGOMP 알고리즘, WIGOMP에 역 콜레스키(cholesky) 인수분해를 도입한 WIGOMP-ICF 알고리즘이 이용될 수 있다.

이하에서는 GOMP-LS 알고리즘, WIGOMP 알고리즘, 및 WIGOMP-ICF 알고리즘을 이용한 랜덤 액세스 방법에 대해 설명하기로 한다.

도 1은 본 발명의 일실시예에 있어서, MTC에 대한 랜덤 액세스 시스템 모델을 도시한 도면이다.

도 1에서, 랜덤 액세스 시스템(100)은 하나의 액세스 포인트(110)와 K개의 센서 노드들(120)을 포함하며, 프레임 동기화를 수행할 수 있다. 액세스 포인트(110)는 정교한 신호 처리가 가능하지만, 센서 노드들(120)은 액세스 포인트(110)에 비해 상대적으로 간단한 구조를 가지며, 작은 패킷을 생성하여 최근 프레임의 시작 시간에 액세스 포인트(110)로 전송할 수 있다. 센서 노드들(120) 각각은 프레임 내에서 활성 확률(activity probability)

로 독립적으로 전송할 데이터를 가질 수 있다. 예컨대, 상기 프레임 내에서 활성 확률(activity probability)

는 실제 통신 시스템, 특히, 대규모 MTC 시스템에서

일 수 있다.

도 1에서는 프레임에

개의 심볼이 존재하는 경우를 가정할 수 있다. 그리고, k번째 센서 노드(

)의 전송 신호는

로 표현될 수 있다. 여기서,

는 k번째 센서 노드

의 n번째 전송 심볼

을 나타낼 수 있다. 그리고, 전송할 데이터가 없는 비활성 센서 노드(inactive sensor nodes)는 모든 전송 데이터가 0일 수 있다. 전송할 데이터가 있는 활성 센서 노드(active sensor nodes)는 이산 유한 변조 알파벳(discrete finite modulation alphabet)

로부터 심볼을 전송할 수 있다. 이에 따라, 수신측에서 검출된(또는 복원된) 신호는 증대된 변조 알파벳, 즉,

로부터 검출될 수 있다.

랜덤 액세스 시스템(100)에서, 모든 센서 노드들(120)은 동일한 시간-주파수 리소스 블록에서 자신의 데이터를 전송할 수 있다. 그러면, 모든 센서 노드들(120)을 식별하기 위해, 고유한 확산 시퀀스(unique spreading sequence)가 센서 노드들(120) 각각에 영구적으로 할당될 수 있다. 예컨대, k번째(

) 센서 노드에 할당된 확산 시퀀스는

로 표현될 수 있다. 여기서,

은 확산 인자(spreading factor)에 해당할 수 있다. 변조 및 확산 후 전송된 신호는 주파수 선택적 페이딩 채널(frequency-selective fading channel)에 의해 왜곡되고, 액세스 포인트(110)에 의해 수신될 수 있다. 길이

인 채널은 전체 프레임에 대해 불변이며, 수신 측에 완벽하게 알려져 있다고 가정할 수 있다. 그러면, 액세스 포인트(110)에서 수신되는 i번째 심볼(즉,

수신 심볼)은 아래의 수학식 4와 같이 표현될 수 있다.

[수학식 4]

수학식 4에서,

는

센서 노드의 채널에 대한 컨볼루션 행렬(convolution matrix)을 나타내고, 아래의 수학식 5와 같이 표현될 수 있다.

[수학식 5]

이때, 하나의 프레임에서 수신된 신호는 아래의 수학식 6과 같이 표현될 수 있다.

[수학식 6]

수학식 6에서,

은 부가 백색 가우시안 잡음(Additive White Gaussian Noise)을 나타내고, y는 액세스 포인트(110)에서 수신된 신호로서,

로 표현될 수 있다. 그리고,

는

센서 노드의 확산 행렬(spreading matrix)로서 아래의 수학식 7과 같이 표현될 수 있다.

[수학식 7]

수학식 6에서 상기 액세스 포인트(110)에서 수신된 신호 y는 아래의 수학식 8과 같이 단순화될 수 있다.

[수학식 8]

수학식 8에서,

는 하나의 프레임 내 모든 K개 센서 노드들(120) 각각으로부터 전송되는 모든 심볼을 포함하는 송신 신호로서, 적층 벡터(stacked vector)로 표현될 수 있다. 그리고, 측정 행렬

는 확산 행렬

과 채널 행렬 을 결합한 형태로 표현될 수 있다.

이때, 압축 센싱(CS) 알고리즘을 이용하여 위의 수학식 3의

최소화를 가진 위의 수학식 8의 문제를 풀면 희소 벡터(sparse vector)

(즉, 송신 신호)에 대한 위치뿐만 아니라, 0이 아닌 값을 추정할 수 있다.

에 대해 0이 아닌 값을 가지는 위치는 활성 센서 노드의 인덱스(index)에 해당할 수 있으며, 0이 아닌 값은 활성 센서 노드가 전송한 데이터에 해당할 수 있다.

도 1의 시스템 모델에서,

는 희소 벡터(sparse vector)로서, 각 센서 노드의 활성 확률인

가 1보다 훨씬 작다는 사실때문에

의 소수 원소만이 0이 아닐 수 있다. 수신 측에서는 희소 벡터

를 CS 알고리즘을 기반으로 미정 방정식(under-determined equation)인 위의 수학식 8에 기초하여 추정할 수 있다. 이때, CS 알고리즘의 계산 복잡도는

의 길이에 따라 기하 급수적으로 증가할 수 있다. 위의 수학식 8에서,

의 길이는

이며, 상기

의 길이는 CS 알고리즘을 사용하여 추정하기에는 너무 큰 길이에 해당할 수 있다. 이에 따라, 복잡도를 줄이기 위해 본연의 문제(original problem)를

개의 하위 문제(sub-problems)로 나눌 수 있다. 위의 비특허 문헌 [4] AT Abebe , CG Kang , Iterative order recursive least square estimation for exploiting frame-wise sparsity in compressive sensing-based MTC . IEEE Communications Letters. 20(5), 1018-1021 (2016).에 제시된 하위 문제로 나누는 방식을 기반으로 상기 본연의 문제(original problem)를

개의 하위 문제(sub-problems)로 나눌 수 있다. 각 하위 문제에서, 연속적인 전송 심볼의 수는 그룹 사이즈

에 해당하고, 계산 복잡도는 그룹 크기에 따라 증가하지만 CS 알고리즘의 성능은 동시에 감소할 수 있다. 이때, 각 하위 문제는 동일한 측정 행렬

를 사용할 수 있으며,

은 오리지널 측정 행렬(measurement matrix)인

의 부분 행렬(sub-matrix)에 해당할 수 있다. 이때, 단순화를 위해, 인접 하위 문제들 사이의 심볼 간 간섭(Inter-Symbol Interference, ISI)은 무시될 수 있으며, 오리지널 문제인 위의 수학식 8의 i번째 하위 문제(

, sub-problem)는 아래의 수학식 9와 같이 표현될 수 있다.

[수학식 9]

수학식 9에서,

는

의

부터

벡터로 구성되고,

는

로 구성될 수 있다. 여기서,

는

의

부터

원소(element)로 구성된 벡터를 나타낼 수 있다. 여기서, 문제 분할(problem division)에 대한 간단한 예가 도 2에 도시되어 있으며, 도 2를 참고하면, 사용자 수

, 확산 계수

, 단일 프레임의 심볼 수

, 그룹 크기

에 해당할 수 있다.

본 실시예들에서는 복수의 GOMP 기반 알고리즘들(예컨대, GOMP-LS 알고리즘, WIGOMP 알고리즘, WIGOMP-ICF 알고리즘 등) 이 랜덤 액세스에 이용될 수 있으며, 이하에서는 GOMP 알고리즘에 대해 설명하기로 한다.

MTC에 대한 CS 기반 랜덤 액세스 시스템에서, 적층 벡터로 표현되는 송신 신호

는 모든 센서 노드로부터 전송된 전체 신호를 포함할 수 있다. 센서 노드가 프레임에서 비활성화되면, 센서 노드는 액세스 포인트(AP, 예컨대, 랜덤 액세스 시스템)에 0을 전송할 수 있다. 결과적으로, 단일 센서 노드에 속하는 심볼들이 모두 단일 프레임(즉, 하나의 프레임)에서 0이 아니거나 0이기 때문에, 추정해야 할 전송 신호는 블록 희소(block sparse)에 해당할 수 있다.

의 블록 희소성(block sparsity)을 이용하기 위하여, 낮은 복잡도의 CS 알고리즘인 GOMP가 이용될 수 있다. GOMP 알고리즘은, 아래의 표 1과 같을 수 있으며, 표 1에 따르면, GOMP 알고리즘은 가장 높은 상관 관계를 가지는 단일의 인덱스를 OMP(Orthogonal Matching Pursuit)에서 선택하는 대신에, 잔차(residual)에 대해 가장 높은 상관 관계를 포함하는 전체 그룹의 인덱스가 선택될 수 있다.

위의 표 1에서,

는 그룹의 총 수이고,

는 한 그룹의 원소 수를 나타낼 수 있다. 반복 정지 기준(iteration stop criterion)은 최대 반복 시간(maximal iteration time)

와 최소 잔차 계수(minimum residual coefficient)

에 의해 결정될 수 있다. 그리고,

은

의

열을 나타내고,

은

의 부분 행렬(sub-matrix)로서

의 인덱스를 가질 수 있으며,

의 열만을 포함할 수 있다. 이처럼, CS 기반 랜덤 액세스 시스템에서, 복잡성을 감소시키기 위해, 위의 수학식 8의 복잡한 문제(complicated problem)는 위의 수학식 9에 표현된 바와 같이 몇 가지의 하위 문제로 나뉘어 질 수 있다. 이때,

에 속하는 원소의 일부를 포함하는 각 하위 문제인

도 블록 희소(block sparse)에 해당할 수 있다. GOMP를 통해 각 하위 문제를 풀면, 즉, 각 하위 문제의 해(solution)를 구함으로써, 센서 노드가 전송한 신호가 액세스 포인트에 의해 추정될 수 있다.

이하에서는 지연 시간, 복잡도, 링크 성능 사이의 트레이드 오프(tradeoff)를 고려하여 GOMP 알고리즘을 기반으로 변형된 복수의 GOMP 알고리즘에 대해 설명하기로 한다. 예컨대, GOMP(Group Orthogonal Matching Pursuit) 알고리즘에 최소 자승법(LS)을 적용한 GOMP-LS 알고리즘, GOMP 알고리즘에 가중 반복(weighted iteration)을 적용한 WIGOMP 알고리즘, 및 WIGOMP 알고리즘에 역 콜레스키 인수분해를 적용한 WIGOMP-ICF 알고리즘에 대해 설명하기로 한다.

먼저, CS 기반의 랜덤 액세스 시스템(100)에서, 각 센서 노드(120)는 각 프레임에서 데이터를 전송하거나 비활성(inactive) 상태를 유지할 수 있다. 이에 따라, 단일 센서 노드의 하위 문제 각각에서 심볼은 모두 0이 아니거나, 0에 해당할 수 있다. 즉, 하위 문제 각각의 해(solution)의 지원 집합(support set)은 동일할 수 있다. CS 기반의 랜덤 액세스 시스템(100)에서 상기 해(solution)의 특성을 이용하여 GOMP 알고리즘의 성능이 향상될 수 있다. 이때, 지연 시간 및 복잡도와 링크 성능 사이의 트레이드 오프(tradeoff)를 고려하여 GOMP 기반의 복수 알고리즘들이 이용될 수 있다. 예컨대, GOMP-LS 알고리즘, WIGOMP 알고리즘, WIGOMP-ICF 알고리즘 등이 이용될 수 있다.

도 3은 본 발명의 일실시예에 있어서, CS 기반의 랜덤 액세스 시스템의 내부 구성을 도시한 블록도이고, 도 4는 본 발명의 일실시예에 있어서, CS 기반의 랜덤 액세스 방법을 도시한 흐름도이다.

도 3을 참고하면, 랜덤 액세스 시스템(300)은 결정부(310) 및 액세스 수행부(320)를 포함할 수 있다. 도 3에서, 랜덤 액세스 시스템(300)은 센서 노드(예컨대, 사용자 단말)와 액세스 포인트(AP)를 포함할 수 있다.

그리고, 도 4의 각 단계들(410 내지 420 단계)은 도 3의 구성 요소인 결정부(310) 및 액세스 수행부(320)에 의해 수행될 수 있다.

먼저, CS 기반의 랜덤 액세스 시스템(300)에서, 각 센서 노드(예컨대, 사용자 단말)는 각 프레임에서 데이터를 전송하거나 비활성(inactive) 상태를 유지할 수 있다. 이에 따라, 단일 센서 노드의 하위 문제 각각에서 심볼은 모두 0이 아니거나, 0에 해당할 수 있다. 즉, 하위 문제 각각의 해(solution)의 지원 집합(support set)은 동일할 수 있다. CS 기반의 랜덤 액세스 시스템(300)에서 상기 해(solution)의 특성을 이용하여 GOMP 알고리즘의 성능이 향상될 수 있다. 이때, 지연 시간 및 복잡도와 링크 성능 사이의 트레이드 오프(tradeoff)를 고려하여 GOMP 기반의 복수 알고리즘들이 이용될 수 있다. 예컨대, GOMP-LS 알고리즘, WIGOMP 알고리즘, WIGOMP-ICF 알고리즘 등이 이용될 수 있다.

410 단계에서, 결정부(310)는 링크 성능, 복잡도 및 지연 시간(latency) 간의 트레이드 오프(tradeoff)에 기초하여 GOMP 기반의 복수 랜덤 액세스 알고리즘 중 어느 하나의 알고리즘을 결정할 수 있다. 여기서, GOMP 기반의 복수 랜덤 액세스 알고리즘은 GOP 알고리즘에 최소 자승법이 적용된 GOMP-LS 알고리즘(411), GOMP 알고리즘에 가중 반복이 적용된 WIGOMP 알고리즘(412) 및 WIGOMP 알고리즘에 역 콜레스키 인수분해가 적용된 WIGOMP-ICF 알고리즘(413)을 포함할 수 있다. GOMP-LS 알고리즘, WIGOMP 알고리즘은 후술될 도 5 및 도 6을 참고하여 상세히 설명하기로 한다.

420 단계에서, 액세스 수행부(320)는 결정된 알고리즘에 기초하여 랜덤 액세스를 수행할 수 있다. 예컨대, 결정된 알고리즘에 기초하여 각 센서 노드에서 전송된 신호가 추정될 수 있으며, 액세스 수행부(320)는 상기 전송된 신호를 추정하기 위해 분할부(321), 가중치 부여부(322), 및 추정부(323)를 포함할 수 있다.

도 5는 본 발명의 일실시예에 있어서, 랜덤 액세스 시스템에서 수행하는 GOMP-LS 알고리즘의 동작을 도시한 블록도이다.

GOMP-LS 알고리즘은, GOMP 알고리즘에 최소 자승법(Least Square)을 적용한 것으로서, 높은 신뢰성을 가지는 어플리케이션에 대한 BER 성능을 향상시키기 위해 이용될 수 있다. GOMP(Group Orthogonal Matching Pursuit) 알고리즘에 기초하여 계산된 각 하위 문제에 대한 해(solution)는 무선 통신 채널의 페이딩(fading) 및 잡음 중 적어도 하나로 인해 센서 노드가 전송하는 데이터와 상이할 수 있다. 이때, 각 하위 문제에서 0이 아닌 해(solution)의 위치가 동일하기 때문에 하위 문제에 따른 다양성 이득이 달성될 수 있다.

도 5를 참고하면, GOMP-LS 알고리즘을 이용하는 경우, 수신 측에서 특정 문제(예컨대, 수신 신호, 510)는 몇 개의 하위 문제(sub-problems, 520)로 분할되고, 각 하위 문제(521, 522, 523)는 GOMP 알고리즘(530)에 기초하여 해(즉, 지원 집합(support set))를 구할 수 있다. 이때, 최대 확률로 지원 집합(support set)을 얻기 위하여, 모든 하위 문제들에 대한 지원 집합이 동일 이득 결합(equal gain combining, EGC, 540)을 사용하여 결합될 수 있다. 압축 센싱(CS) 이론에 따르면,

가 희박(sparse)하므로,

의 지원 집합을 알고 있을 때

의 0이 아닌 원소의 값은 LS 추정을 사용하여 추정될 수 있다. 즉, EGC(540)를 사용하여 결합된 지원 집합을 대상으로, LS 추정(550)이 수행될 수 있으며, 추정된 신호

(560)가 출력될 수 있다. 즉, 센서 노드에서 전송한 송신 신호

가 추정될 수 있다.

이처럼, GOMP 알고리즘에 최소 자승법을 적용한 GOMP-LS 알고리즘은 아래의 표 2와 같을 수 있다.

위의 표 2에 따르면, GOMP-LS 알고리즘에서,

는 활성 센서 노드의 인덱스를 포함하는 집합을 나타낼 수 있다. 그리고,

는

에서

원소(element)를 나타낼 수 있다. 센서 노드에 대한 프레임에서 추정된 0이 아닌 원소의 수가

보다 큰 경우, 해당 센서 노드는 활성(active) 센서 노드로 지정되고, 해당 센서 노드의 인덱스는 집합

에 추가될 수 있다. 그리고,

는 집합

에서 센서 노드의 인덱스를 가지는

의 열(column)만을 포함하는

의 부분 행렬을 나타낼 수 있다.

도 6은 본 발명의 일실시예에 있어서, 랜덤 액세스 시스템에서 수행하는 WIGOMP 알고리즘을 기반으로 랜덤 액세스를 수행하는 동작을 도시한 흐름도이다.

도 6에서 각 단계들(610 내지 630 단계)은 도 3의 랜덤 액세스 수행부(320)의 구성 요소인 분할부(321), 가중치 부여부(322), 및 추정부(323)에 의해 수행될 수 있다.

610 단계에서, 분할부(321)는 수신 신호로부터 센서 노드에서 전송한 신호를 추정하기 위해, 상기 수신 신호를 나타내는 복잡한 문제(complicated problem)를 하위 문제(sub-problems)로 분할할 수 있다.

620 단계에서, 가중치 부여부(322)는, WIGOMP 알고리즘을 이용하여 각 하위 문제에 대한 해(solution)를 구하기 위해. 각 하위 문제 별로 가중치(weight)를 부여할 수 있다.

630 단계에서, 추정부(323)는 각 하위 문제에 대해 부여된 가중치를 조정함으로써, 수신 신호에 포함된 센서 노드에서 전송한 신호를 나타내는 희소 벡터(sparse vector)를 추정할 수 있다. 여기서, WIGOMP 알고리즘을 기반으로 가중치를 조정하여 송신 신호를 추정하는 동작은 아래의 도 7 및 표 3에서 자세히 설명하기로 한다.

이때, 추정부(323)는 WIGOMP 알고리즘에 역 콜레스키 인수분해를 적용한 WIGOMP 알고리즘을 이용하여 송신 신호를 추정할 수 있다. 예를 들어, 추정부(323)는 수신 신호에 포함된 측정행렬의 부분행렬(sub-matrix), 부분행렬의 허미션 행렬(hermition matrix)을 기반으로 역 콜레스키(cholesky) 인수분해를 이용하여 하위 문제의 해(solution)를 구함으로써, 송신 신호를 추정할 수 있다. 여기서, 역 콜레스키 인수분해를 이용하여 송신 신호를 추정하는 동작은 아래의 표 4에서 상세히 설명하기로 한다.

도 7은 일실시예에 있어서, 랜덤 액세스 시스템에서 수행하는 WIGOMP 알고리즘의 동작을 도시한 블록도이다.

도 3에서 설명한 GOMP-LS에서는 링크 성능을 향상시키기 위해 모든 하위 문제의 지원 집합을 결합하지만, 추가적인 복잡도와 지연 시간도 같이 도입될 수 있다. 5G 이동 통신에서 낮은 지연 시간의 요구 사항을 만족시키기 위해, 도 7에 도시된 바와 같이 WIGOMP 알고리즘이 이용될 수 있다.

도 7을 참고하면, WIGOMP 알고리즘을 이용하는 경우, 추정부(323)는 지연 시간(latency)의 추가 없이 가중치(weight)를 조정(710)함으로써 링크 성능을 개선할 수 있다. 하위 문제가 해결되면 해(solution)가 직접 출력될 수 있다(720). 즉, GOMP-LS처럼 모든 하위 문제가 해결될 때까지 기다릴 필요가 없다. 이전 하위 문제에서 0이 아닌 요소의 위치는 후속되는 하위 문제에 대한 추정 정확도를 향상시키는데 사용될 수 있다. 이에 따라, 후속되는 하위 문제에서 심볼이 부정확하게 추정될 확률은 상대적으로 더 작기 때문에, 임계 신호가 프레임의 후속 심볼에서 전송될 수 있다.

아래의 표 3은 WIGOMP 알고리즘의 의사 코드(pseudo code)를 나타낼 수 있다.

표 3에서,

는

반복(iterationi)에서 가중치 벡터를 나타내고,

는

에서의

원소(element)를 나타낼 수 있다. 이때, 모든 가중치는 표 3의 1단계에서 1로 초기화될 수 있으며, 반복(iteration)으로 인해, 이전에 발생하는 오류의 영향을 억제하기 위해 표 3의 2.2 단계에서, 이전의

하위 문제의 가중치를 1로 유지할 수 있다. 그리고,

하위 문제로부터

하위 문제에서의 가중치는 이전

하위 문제의 해의 2-norm의 합으로 조정될 수 있다.

아래의 표 4에서는 WIGOMP-ICF 알고리즘을 나타낼 수 있다.

GOMP 및 WIGOMP 알고리즘, OMP 및 OMP의 확장 알고리즘에서, 0이 아닌 원소의 수와 함께 해(solution)를 구하는 계산 복잡도가 기하 급수적으로 증가할 수 있다. 이때, 행렬 역전을 회피함으로써 계산 복잡도의 증가를 해결할 수 있으며, WIGOMP-ICF 알고리즘은 역 콜레스키(cholesky) 인수분해를 WIGOMP 알고리즘에 적용함으로써, 상기 계산 복잡도를 낮출 수 있다.

먼저, WIGOMP-ICF 알고리즘을 이용하는 경우, 추정부(323)는 WIGOMP 알고리즘에 역 콜레스키 인수분해를 적용할 수 있다. 이때, 위의 표 3의 2.3.4 단계에 해당하는

를 계산하기 위해,

를 가정할 수 있다. 즉, 수신 신호에 포함된 측정 행렬의 부분 행렬(sub-matrix)

과 측정 행렬의 허미션(hermition) 행렬

의 곱을 미리 지정된 특정 변수

로 가정할 수 있다.

그러면,

의 역 콜레스키 인자(factor)인

와 상기 인자

는 아래의 수학식 10을 만족할 수 있다.

[수학식 10]

수학식 10에서,

의 역 콜레스키 인자(factor)

는 이전 반복에 해당하는 역 콜레스키 인자(factor)

및 V-BLAST 기반 제급근 알고리즘(square-root algorithm for V-BLAST based on efficient inverse Cholesky factorization)에 기초하여 계산될 수 있다. 이때,

로부터

를 반복적으로 계산하기 위해 위의 비특허 문헌 [ 5]H Zhu , W Chen, B Li , F Gao , An improved square-root algorithm for V-BLAST based on efficient inverse Cholesky factorization. IEEE Transactions on Wireless Communications. 10(1), 43-48 (2011).에 제시된 효율적인 알고리즘이 이용될 수 있다.

이하에서는 도 8 내지 도 12를 참고하여, GOMP-LS 알고리즘, WIGOMP 알고리즘 및 WIGOMP 알고리즘의 성능 평가에 대해 설명하기로 한다.

도 8 내지 도 12에서, 링크 성능을 평가하기 위해 다양한 파라미터를 가지는 몬테 카를로(Monte Carlo) 시뮬레이션이 수행될 수 있으며,

개의 센서 노드를 포함하는 시나리오가 고려될 수 있다. 그리고, 프레임은 길이가

인 PN(pseudo-noise) 시퀀스를 통해 BPSK(binary phase shift keying) 변조 및 확산(spread)을 가지는

인 심볼을 포함할 수 있다.

도 8은 본 발명의 일실시예에 있어서, 그룹 사이즈 변화에 따른 GOMP 및 GOMP-LS 알고리즘의 BER을 도시한 그래프를 나타낼 수 있다.

도 8을 참고하면, 다양한 그룹 사이즈

에서 GOMP 알고리즘 및 GOMP-LS 알고리즘의 BER 성능을 알 수 있으며, 이때, 활성 확률

에 해당할 수 있다. 도 8에 따르면, GOMP와 GOMP-LS 모두에서 그룹 사이즈

가 증가할수록 블록 희소성(block sparsity)이 증가하게 되어 BER이 감소함을 알 수 있다. 그리고,

일 때, 그룹 사이즈가 2에서 8로 증가함에 따라, GOMP의 BER은

에서

로 감소함을 확인할 수 있다. 따라서, GOMP-LS는 GOMP 대비 명백히 더 우수한 BER 성능을 달성함을 확인할 수 있다.

예컨대,

에서, GOMP-LS의 BER 조차도

일 때의 GOMP의 BER 보다 더 낮음을 확인할 수 있다. 즉, 동일한 BER 성능을 충족시키기 위해, 더 큰 그룹 사이즈를 갖는 GOMP 알고리즘 대신 더 작은 그룹 사이즈를 갖는 GOMP-LS 알고리즘을 이용하여 계산 복잡도를 감소시킬 수 있다. 그리고, 그룹 사이즈가 8에서 2로 감소하면, GOMP 알고리즘의 경우, GOMP-LS 알고리즘보다 BER 증가가 훨씬 큼을 확인할 수 있다. 즉, GOMP-LS 알고리즘은 각 하위 문제 사이의 관계를 고려하기 때문에, 그룹 사이즈가 작으면 하위 문제의 수가 많으므로 GOMP-LS에서 하위 문제 다양성 이득이 더 많이 발생하므로, GOMP 알고리즘의 BER 증가가 GOMP-LS 알고리즘보다 클 수 있다.

도 9는

인 센서 노드의 활성 에러율(sensor node activity error rate)에 대한 활성 확률(activity probability)을 도시한 그래프를 나타낼 수 있다.

CS 기반 랜덤 액세스에서, 센서 노드의 활성과 전송된 데이터 모두가 수신 측에서 검출될 수 있으며, 센서 노드의 활동 오류에는 활성 노드가 비활성 상태로 감지되는 경우와 그 반대의 경우가 모두 포함될 수 있다.

도 9를 참고하면, 그룹 사이즈

에 대한 다양한 활성 확률

를 갖는 센서 노드의 활성 오류율은

가 증가하는 동안 감소할 수 있다. 이때, 높은 활성 확률로 인해 더 많은 탐지 오류가 발생할 수 있다. 압축 센싱(CS) 이론의 관점에서, 높은 활성 확률은 전반적으로 높은 희소성(sparsity)에 해당하며, 상기 희소성은 활성 확률이 증가함에 따라 점진적으로 파괴되고, 결국 CS 알고리즘에서의 성능 저하를 가져올 수 있다.

인 경우, 활성 확률이 0.01에서 0.1로 증가하면서 센서 노드의 활성 오류율은

에서

로 증가함을 확인할 수 있다.

도 10은 본 발명의 일실시예에 있어서, 활성 확률과 BER 성능 간의 관계를 도시한 그래프를 나타낼 수 있다.

도 10에서는 그룹 사이즈

가 8인 경우에 GOMP 알고리즘, GOMP-LS 알고리즘, WIGOMP 알고리즘 별 BER 성능을 비교하기 위한 그래프이다.

도 10을 참고하면, GOMP-LS는 하위 문제들 사이의 관계를 이용하고 더욱 다양한 이득을 획득하여 BER을 크게 감소시키기 때문에 GOMP-LS의 성능이 가장 좋음을 확인할 수 있다. 그리고, 이전 반복에서 계산된 하위 문제의 해(solution)에 따라 각 사용자 단말의 가중치를 도입함으로써 후속되는 하위 문제에서 다양한 이득이 달성되기 때문에, WIGOMP의 성능은 GOMP보다 우수함을 확인할 수 있다. WIGOMP의 성능은 후속되는 하위 문제의 BER 성능을 향상시킬 수 있기 때문에 GOMP-LS보다 좋지 않은 반면, GOMP-LS에서는 모든 하위 문제의 성능이 향상됨을 알 수 있다.

,

인 경우에 GOMP, WIGOMP 및 GOMP-LS의 BER은 각각

,

및

임을 확인할 수 있다. 그리고,

가 높아지면 GOMP 대신에 GOMP-LS 또는 WIGOMP 알고리즘을 사용하는 것이 BER 성능에 대한 이득이 더 많음을 확인할 수 있다. 즉, 높은 의 조건 하에서, 에러 데이터의 수는 감소하므로, EGC 또는 가중된 반복에 의해 에러 비트를 정정하는 것이 더 수월해 질 수 있다. 그리고. WIGOMP-ICF는 행렬 역전을 피함으로써 WIGOMP의 계산 복잡도만을 감소시키기 때문에, WIGOMP의 BER 성능과 동일한 WIGOMP-ICF의 BER 성능은 도 10에서 생략되었다.

아래의 표 5는 GOMP 알고리즘과 GOMP 기반 알고리즘들(GOMP-LS 알고리즘, WIGOMP 알고리즘, WIGOMP-ICF 알고리즘)의 계산 복잡도와 지연 시간을 비교한 테이블(table)을 나타낼 수 있다.

계산 복잡도는 복소 곱셈(complex multiplication)의 수이고, 지연 시간(latency)은 첫 번째 심볼 입력에서부터 마지막 심볼 출력까지의 지연(delay)을 나타낼 수 있다. 알고리즘의 지연 시간은 심볼 지속 시간

로 표현될 수 있으며, 다양한 계산 복잡도의 처리 시간(processing time)은 아래의 수학식 11과 같이 표현될 수 있다.

[수학식 11]

도 11은 본 발명의 일실시예에 있어서, 활성 확률과 계산 복잡도 간의 관계를 도시한 그래프를 나타낼 수 있다.

구체적으로, 도 11은 위의 표 5에 표현된 네 가지 알고리즘의 활성 확률에 따라 변화하는 계산 복잡도를 나타낼 수 있다. 표 5에서, 파라미터들의 값은 다음과 같을 수 있다. 센서 노드 들의 수

, 확산 인자(spreading factor)

, 프레임 당 심볼들의 수

, 그룹 사이즈

, 하위 문제 수(number of sub-problems)

.

도 11을 참고하면, GOMP와 WIGOMP의 계산 복잡도는 거의 동일하며, WIGOMP-ICF의 계산 복잡도보다는 크고 GOMP-LS의 계산 복잡도보다는 작음을 확인할 수 있다. 그리고, 활성 확률이 증가함에 따라, WIGOMP-ICF의 계산 복잡도는 거의 변하지 않는 반면, 다른 알고리즘들(즉, GOMP, WIGOMP, GOMP-LS) 의 계산 복잡도는 기하 급수적으로 증가함을 확인할 수 있으며, 특히, GOMP-LS의 계산 복잡도가 더욱 급격히 증가함을 확인할 수 있다. 예컨대,

일 때, GOMP의 계산 복잡도는 WIGOMP-ICF의 약 5배이며, GOMP-LS의 계산 복잡도는 WIGOMP-ICF의 약 8배임을 확인할 수 있다.

도 12는 본 발명의 일실시예에 있어서, 프레임당 심볼의 수에 따른 지연 시간(latency) 변화를 도시한 그래프를 나타낼 수 있다.

도 12에서는 GOMP 기반 알고리즘들(GOMP-LS 알고리즘, WIGOMP 알고리즘, WIGOMP-ICF 알고리즘)의 지연 시간을 GOMP 알고리즘과 비교하기 위해, 다양한 계산 복잡도에 대한 처리 시간이

임을 가정할 수 있다.

도 12를 참고하면, 지연 시간(latency)은 프레임 당 심볼 수가 증가함에 따라 선형적으로 증가함을 확인할 수 있다. 이때, GOMP와 GOMP-LS의 지연 시간은 거의 동일하며, WIGOMP-ICF의 지연 시간은 GOMP보다 7% 낮음을 확인할 수 있다. 그리고, GOMP-LS의 지연 시간은 다른 알고리즘들(즉, GOMP 알고리즘, WIGOMP 알고리즘, WIGOMP-ICF 알고리즘)의 두 배에 해당함을 확인할 수 있다.

도 13은 본 발명의 일실시예에 있어서, 링크 성능, 복잡도 및 지연 시간 간의 트레이드 오프를 고려하여 GOMP 기반의 복수 랜덤 액세스 알고리즘들의 장단점을 비교 도시한 블록도이다.

도 13의 1310을 참고하면, 높은 신뢰도를 가지는 어플리케이션의 경우, GOMP 기반의 복수 알고리즘들(예컨대, GOMP, GOMP-LS, WIGOMP, WIGOMP-ICF 알고리즘) 중에서 GOMP-LS 알고리즘(1320)이 랜덤 액세스에 적용될 알고리즘으로 결정될 수 있다. 이때, 도 3의 결정부(310)에서 링크 성능, 복잡도 및 지연 시간(latency) 간의 트레이드 오프(tradeoff)를 고려하여 랜덤 액세스에 이용될 알고리즘이 결정될 수 있다. 도 8 내지 도 12에서 살펴본 바와 같이, GOMP-LS 알고리즘은 링크 성능을 급격히 향상시키지만, 계산 복잡도와 지연 시간을 급격히 증가시킬 수 있다.

이에 따라, 낮은 지연시간을 요구하는 어플리케이션의 경우(1330), 상기 복수의 알고리즘들 중에서 WIGOMP 알고리즘 또는 WIGOMP-ICF 알고리즘이 랜덤 액세스에 이용될 알고리즘으로 결정될 수 있다. 즉, 수신 측에서 신호

를 추정 하기 위한 알고리즘으로서, WIGOMP 알고리즘 또는 WIGOMP-ICF 알고리즘이 결정될 수 있다. 그러면, WIGOMP 알고리즘 또는 WIGOMP-ICF 알고리즘을 기반으로 압축 센싱을 수행하여 생성된 신호가 채널을 통해 상대 수신단으로 전송될 수 있다. 수신단 각각은 수신된 신호를 상기 결정된 알고리즘(예컨대, 송신 단에서 적용한 WIGOMP 알고리즘 또는 WIGOMP-ICF 알고리즘)에 기초하여 추정할 수 있다.

이때, 위의 도 8 내지 도 12에서 설명한 바와 같이, WIGOMP 알고리즘은 링크 성능을 향상시키지만, GOMP 알고리즘과 동일한 링크 성능과 지연 시간을 가지며, WIGOMP-ICF 알고리즘은 링크 성능을 향상시키지만 계산복잡도와 지연시간을 감소시키므로, 어플리케이션에서 요구되는 지연 시간이 낮을수록(예컨대, 기준 지연 시간 이하의 낮은 지연 시간을 요구하는 어플리케이션에 해당하는 데이터를 송수신하고자 하는 경우), 계산복잡도가 낮은 WIGOMP-ICF가 이용될 수 있다.

예컨대, 기준 신뢰도 이상의 높은 신뢰도를 요구하는 어플리케이션일수록(즉, 지연 시간이 걸리더라도 일정값 이상의 링크에서 데이터 송수신이 요구되는 어플리케이션일 수록) GOMP-LS 알고리즘이 이용될 알고리즘으로 결정될 수 있다. 그리고, 링크 성능보다는 저지연이 요구될수록 WIGOMP-ICF 알고리즘이 적용될 알고리즘으로 결정될 수 있다. 그리고, 요구되는 지연 시간을 GOMP 알고리즘과 기정의된 범위 내에서 GOMP 알고리즘과 동일하게 유지하면서, 상대적으로 높은 신뢰도를 달성하고자 하는 경우 WIGOMP 알고리즘이 적용될 알고리즘으로 결정될 수 있다. 즉, GOMP 알고리즘에서 요구되는 지연 시간을 증가시키지 않으면서 GOMP 알고리즘보다는 상대적으로 높은 신뢰도를 가지는 어플리케이션과 관련하여 데이터 송수신 시, WIGOMP 알고리즘이 적용될 수 있다.

이상과 같이 실시예들이 비록 한정된 실시예와 도면에 의해 설명되었으나, 해당 기술분야에서 통상의 지식을 가진 자라면 상기의 기재로부터 다양한 수정 및 변형이 가능하다. 예를 들어, 설명된 기술들이 설명된 방법과 다른 순서로 수행되거나, 및/또는 설명된 시스템, 구조, 장치, 회로 등의 구성요소들이 설명된 방법과 다른 형태로 결합 또는 조합되거나, 다른 구성요소 또는 균등물에 의하여 대치되거나 치환되더라도 적절한 결과가 달성될 수 있다.

그러므로, 다른 구현들, 다른 실시예들 및 특허청구범위와 균등한 것들도 후술하는 특허청구범위의 범위에 속한다.

Claims

MTC(Machine Type Communication)를 위한 압축 센싱 기반의 랜덤 액세스 방법에 있어서,
링크 성능, 복잡도 및 지연 시간(latency) 간의 트레이드오프(tradeoff)에 기초하여 GOMP 기반의 복수 랜덤 액세스 알고리즘 중 랜덤 액세스에 이용될 어느 하나의 알고리즘을 결정하는 단계; 및
결정된 알고리즘에 기초하여 랜덤 액세스를 수행하는 단계
를 포함하고,
상기 복수 랜덤 액세스 알고리즘은, GOMP(Group Orthogonal Matching Pursuit)에 최소 자승법(Least Squares, LS)이 적용된 GOMP-LS 알고리즘, 상기 GOMP에 가중 반복(Weighted Iteration)이 적용된 WIGOMP 알고리즘, 및 상기 WIGOMP에 역 콜레스키(cholesky) 인수분해가 적용된 WIGOMP-ICF 알고리즘을 포함하는 것
을 특징으로 하는 압축 센싱 기반의 랜덤 액세스 방법.
삭제
제1항에 있어서,
상기 결정하는 단계는,
서비스하고자 하는 애플리케이션이 미리 정의된 기준 신뢰도 이상의 높은 신뢰도를 요구하는 경우, 상기 GOMP 기반의 복수 랜덤 액세스 알고리즘, WIGOMP-ICF 알고리즘 중 상기 GOMP-LS 알고리즘을 상기 랜덤 액세스에 이용될 알고리즘으로 결정하는 것
을 특징으로 하는 압축 센싱 기반의 랜덤 액세스 방법.
제1항에 있어서,
상기 결정하는 단계는,
서비스하고자 하는 애플리케이션이 미리 정의된 기준 지연 시간 이하의 낮은 지연 시간(latency)를 요구하는 경우, GOMP 기반의 복수 랜덤 액세스 알고리즘, WIGOMP-ICF 알고리즘 중 WIGOMP 및 WIGOMP-ICF 중 어느 하나를 상기 랜덤 액세스에 이용될 알고리즘으로 결정하는 것
을 특징으로 하는 압축 센싱 기반의 랜덤 액세스 방법.
MTC(Machine Type Communication)를 위한 압축 센싱 기반의 랜덤 액세스 방법에 있어서,
링크 성능, 복잡도 및 지연 시간(latency) 간의 트레이드오프(tradeoff)에 기초하여 GOMP 기반의 복수 랜덤 액세스 알고리즘 중 랜덤 액세스에 이용될 어느 하나의 알고리즘을 결정하는 단계; 및
결정된 알고리즘에 기초하여 랜덤 액세스를 수행하는 단계
를 포함하고,
상기 랜덤 액세스를 수행하는 단계는,
결정된 알고리즘이 WIGOMP 알고리즘인 경우, 수신 신호를 나타내는 복잡한 문제(complicated problem)를 하위 문제(sub-problems)로 분할하는 단계;
분할된 각 하위 문제 별로 가중치(weight)를 부여하는 단계; 및
부여된 상기 가중치를 조정하여 상기 수신 신호에 포함된 센서 노드에서 전송한 신호를 나타내는 희소 벡터(sparse vector)를 추정하는 단계
를 포함하는 압축 센싱 기반의 랜덤 액세스 방법.
제5항에 있어서,
현재 반복(i^th iteration)에 해당하는 하위 문제에 부여된 상기 가중치는 이전 반복((i-1)^th iteration)에 해당하는 하위 문제의 해(solution)의 2-norm의 합으로 조정되는 것
을 특징으로 하는 압축 센싱 기반의 랜덤 액세스 방법.
MTC(Machine Type Communication)를 위한 압축 센싱 기반의 랜덤 액세스 방법에 있어서,
링크 성능, 복잡도 및 지연 시간(latency) 간의 트레이드오프(tradeoff)에 기초하여 GOMP 기반의 복수 랜덤 액세스 알고리즘 중 랜덤 액세스에 이용될 어느 하나의 알고리즘을 결정하는 단계; 및
결정된 알고리즘에 기초하여 랜덤 액세스를 수행하는 단계
를 포함하고,
상기 랜덤 액세스를 수행하는 단계는,
결정된 알고리즘이 WIGOMP-ICF 알고리즘인 경우, 수신 신호에 포함된 측정행렬의 부분행렬(sub-matrix), 부분행렬의 허미션 행렬(hermition matrix)을 기반으로 역 콜레스키(cholesky) 인수분해를 이용하여 하위 문제의 해(solution)를 구함으로써, 센서 노드에서 전송한 신호를 추정하는 단계
를 포함하는 압축 센싱 기반의 랜덤 액세스 방법.
제7항에 있어서,
상기 부분 행렬과 상기 허미션 행렬의 곱으로 표현되는 특정 변수
의 역 콜레스키 인자(factor)
는 이전 반복에 해당하는 역 콜레스키 인자(factor)
및 V-BLAST기반 제곱근 알고리즘(square-root algorithm for V-BLAST based on efficient inverse Cholesky factorization)에 기초하여 계산되는 것
을 특징으로 하는 압축 센싱 기반의 랜덤 액세스 방법.
MTC(Machine Type Communication)를 위한 압축 센싱 기반의 랜덤 액세스 시스템에 있어서,
링크 성능, 복잡도 및 지연 시간(latency) 간의 트레이드오프(tradeoff)에 기초하여 GOMP 기반의 복수 랜덤 액세스 알고리즘 중 랜덤 액세스에 이용될 어느 하나의 알고리즘을 결정하는 결정부; 및
결정된 알고리즘에 기초하여 랜덤 액세스를 수행하는 액세스 수행부
를 포함하고,
상기 복수 랜덤 액세스 알고리즘은, GOMP(Group Orthogonal Matching Pursuit)에 최소 자승법(Least Squares, LS)이 적용된 GOMP-LS 알고리즘, 상기 GOMP에 가중 반복(Weighted Iteration)이 적용된 WIGOMP 알고리즘, 및 상기 WIGOMP에 역 콜레스키(cholesky) 인수분해가 적용된 WIGOMP-ICF 알고리즘을 포함하는 것
을 특징으로 하는 압축 센싱 기반의 랜덤 액세스 시스템.