KR101305585B1

KR101305585B1 - 다중 사용자 다운링크 릴레이 네트워크에서 급변하는 사용자 요구 통신품질에 대한 만족도 개선방법

Info

Publication number: KR101305585B1
Application number: KR1020110147757A
Authority: KR
Inventors: 김성철; 이웅희; 최지원
Original assignee: 서울대학교산학협력단
Priority date: 2011-12-30
Filing date: 2011-12-30
Publication date: 2013-09-09
Anticipated expiration: 2031-12-30
Also published as: KR20130078683A

Abstract

사용자가 요구하는 통신 서비스 품질의 변화량이 대폭 증가하고 있는 데에 반해, 현재 스케쥴링 기법들은 그 점을 고려하지 않고 있다. 본 발명에서는, 다중 사용자 다운링크 릴레이 (혹은 펨토셀) 네트워크에서 게임 이론을 바탕으로 분산적인 방법을 통하여 시간 자원과 주파수 자원을 할당하여 사용자 단말기가 받는 간섭량을 최소화하여 모든 사용자가 받을 수 있는 정보 전송량을 극대화한다. 복잡도와 정보 전송량 증대의 관점에서 시간 자원 할당을 수행함으로써 전력 자원 할당을 활용할 때 보다 더 큰 이득을 이끌어낼 수 있다. 또한 QoS에 대해 만족 상태에 있는 사용자 단말기가 불만족 상태가 되는 경우, 만족 상태에 있는 사용자 단말기의 주파수 자원을 공백화(frequency nulling) 함으로써 각 사용자 단말기의 만족도를 극대화할 수 있다. 이 주파수 공백화를 통해 각 사용자 단말기가 요구하는 QoS가 변동할 때에도 현명하게 대처할 수 있다.

Description

다중 사용자 다운링크 릴레이 네트워크에서 급변하는 사용자 요구 통신품질에 대한 만족도 개선방법 {Method for improving satisfaction of various user's requiring QoS in a multi-users downlink relay network}

본 발명은 네트워크의 통신품질을 개선하기 위한 방법에 관한 것으로서, 보다 구체적으로는 다중 사용자 다운링크 릴레이(또는 펨토셀) 네트워크에서 게임 이론을 바탕으로 분산적인 방법을 통해 모든 사용자 단말기가 받을 수 있는 정보 전송량을 극대화함과 더불어 QoS에 대한 만족도도 극대화할 수 있는 통신품질 개선방법에 관한 것이다.

협동적인 릴레이 네트워크는 상대적으로 좋은 통신 서비스 품질(

)을 보장한다. 하지만 이는 소스 또는 소스스테이션(Source: S)과 각 릴레이 스테이션(Relay Station: RS), 사용자 단말기(User Equipment: UE)끼리 역할 조정을 하고 정보를 주고받는 데에 높은 신호량 오버헤드가 발생하기 때문에 실질적으로 구현하기가 힘들다. 하지만 게임이론을 사용하여 협동적이 아닌 경쟁적인 구도로 네트워크 구조를 설정하면, 전체 셀의 정보를 필요로 하지 않고 자신이 속한 기지국 셀만의 정보에만 관심을 갖기 때문에 훨씬 간편한 연산이 되고, 이는 전체 셀들을 고려하여 최적화한 결과와 근사한 결과를 가져오기 때문에 게임이론을 사용하여 릴레이 네트워크 문제를 푸는 것이 중요한 문제가 되고 있다.

지금까지의 연구 결과를 살펴보면,

와

들이 각자 갖고 있는 송신전력제한을 가지고 게임을 하는 연구들이 많이 진행되었다. 논문 'A Game-Theoretic Approach for Distributed Power Control in Interference Relay Channels' 에서는 두 셀이 존재하고 각 셀마다

가 한 개씩 존재하며 셀 엣지에 있는 상황을 고려하고 있으며, 인접 셀에 미치는 간섭량과 최종적으로

가 받는 정보 전송량을 게임이론을 통해 풀고 있다. 하지만 한 셀에서의

의 전력과

의 전력의 합이 일정하다는 다소 무리라고 할 수 있는 가정을 하고 있고 시나리오 자체도 굉장히 빈약하다. 또한, 전력 조절을 통하여 얻는 정보 전송량의 이득은 굉장히 적고, 정보 전송량의 조절 범위 또한 턱없이 좁기 때문에 다이나믹하게 변화하는 요구

를 만족시켜 주는 데는 한계가 있다. 또한 전력 조절 게임의 복잡도에 비해 그로 인한 이득은 굉장히 적다.

논문 'Distributed Power Allocation in Multi-User Multi-Channel Cellular Relay Networks'에서는 단일 셀에서 다수의

와

가 존재할 때, 각각의

들이 자신이 담당한

의 높은

보장을 위해서 자신의 전력을 가지고 게임에 참여하게 된다. 위에서 지적한 바와 같이 전력을 가지고 게임을 하기 때문에 복잡도에 비해 그로 인해 얻는 이득은 적게 될 것이다. 또한 논문 'Distributed Power Allocation in Multi-User Multi-Channel Cellular Relay Networks'에서는 사용하고 있는 기존의

의 경우,

의 개수를

개라 한다면, 총

개의 타임 슬롯(time slot) 중에

개의 타임 슬롯 동안

들은 휴지 상태에 있다. 즉, 기존의

방식은 도 1과 같이 한 프레임의

번째 타임 스롯 동안에,

가

개의

에게 순서대로 타임 오쏘고날하게 정보를 전송하고, 그 프레임의 마지막

번째 타임 슬롯에 모든

로부터의 동시적 전송이 활성화된다. 그러므로

번째 서브캐리어에서

의 정보 전송량(UE's capacity)은 다음과 같이 정의된다.

......(1)

와

는 각각

번째 서브캐리어를 이용한

와

의 수신 전력이고,

와

는 각각

번째 서브캐리어를 이용한

와

의 통계적으로 독립적인 부가적 백색 가우스 잡음(AWGN) 전력이다.

이 종래의 OFD 방식은 여러 가지 문제점을 가진다. 첫 번째 문제로는, 시간 활용 측면에서 비효율성이 있다는 점이다. 모든

가

개의 전체 타임 슬롯 동안에 활성화되지 못하고, 모든

들이 마지막 타임 슬롯에만 동기적으로 활성화 되는 방식이기 때문이다.

두 번째 문제는 전력 조절 게임의 비효율성이다. 정보 전송량에서 전력은 로그함수 안에 들어있다. 전력 조절 게임을 통해서 낮은 SINR일 때엔 많은 이득을 보지만, 높은 SINR일 때엔, 즉 도 2와 같이 전력을 사용하여 정보 전송량을 늘리는 데엔 한계가 있고, 그 복잡도에 비해 얻어지는 이득은 너무도 적다.

세 번째 문제는 요구하는

의 변화에 대한 대처에 미흡하다는 점이다. 가장 일반적으로 사용하는 비례적 공평성(Proportional Fairness: PF) 의 경우에도 각

들이 실제로 어떤

를 요구하고 그것을 스케쥴링에 반영하는 연산이 전혀 되어있지 않다.

본 발명자들은 기존의 ODF 기법의 문제점들로부터 다음과 같은 몇 가지 사항들을 착안하게 되었다.

첫째, 주파수와 시간 자원을 활용한다면 정보 전송량이 정수배로 늘어나게 되고, 전력을 서브캐리어에 나누어 싣는 복잡하고 구체적인 계산에 비해 훨씬 간단한 연산이 될 것이라는 점이다. 또한 주파수와 시간 자원을 활용하면 정보 전송량의 가능한 크기 조절 범위가 훨씬 넓어져 다이내믹하게 변화하는 요구

를 만족시켜 줄 수 있다.

둘째, 활용되지 못하여 낭비되고 있는 나머지 타임스롯까지도 즉, 휴지 상태에 있는 시간을 각

들이 '현명한 전략'을 통해 활용한다면 기존의

기법 보다 더 큰 정보 전송량을 갖게 될 것이라는 점이다. 그렇게 되면 한 프레임에 타임 슬롯의 갯수도

에서

로 줄어들어 노말라이즈 팩터도

에서

로 늘어날 수 있을 것이다.

끝으로, 요구하는

의 변화에 대한 대처가 미흡한 점을 해결하기 위해, 공평성(fairness)의 개념을

들의 요구하는

충족도로 바꾸어 스케쥴링을 하면 자원 활용이 훨씬 효율적일 것이라는 점이다.

이러한 착안점들에 입각하여, 본 발명은 기존의

의 시간 활용 측면의 비효율성과 전력 조절 게임의 비효율성을 개선하기 위해, 다중 사용자 다운링크 릴레이 네트워크에서 주파수 자원과 시간 자원을 활용한 완벽하게 분산적인 게임이론을 채용하여 사용자 단말기가 받는 간섭량을 최소화하여 정보 전송량을 극대화할 수 있는 통신품질 개선방법을 제공하는 것을 하나의 목적으로 한다.

본 발명은 또한 복잡도와 정보 전송량 증대의 관점에서 시간 자원을 활용하므로써 파워 자원을 활용할 때보다 더 큰 이득을 이끌어낼 수 있는 통신품질 개선방법을 제공하는 것을 다른 목적으로 한다.

또한, 본 발명은 주파수 자원을 이용하여 각 사용자들이 요구하는 QoS가 변동할 때 다이내믹하게 대처하여 모든 사용자 단말기가 통신 품질에 만족하는 상태에 처하도록 해줄 수 있는 통신품질 개선방법을 제공하는 것을 또 다른 목적으로 한다.

위와 같은 목적을 달성하기 위한 본 발명의 일 측면에 따르면, 무선통신 서비스 영역을 복수의 셀로 구분하고, 각 셀마다 하나의 소스 스테이션(S)과 복수 개의 릴레이스테이션(RS) 그리고 랜덤하게 분포되어 있는 복수 개의 사용자 단말기(UE)가 존재하며, 상기 소스스테이션(S)과 상기 릴레이스테이션(RS)들은 모두 N개(단, N은 2이상의 자연수)의 서브캐리어를 가지며, 상기 소스스테이션(S)은 상기 릴레이스테이션(RS)들을 시분할다중접속[

]방식으로 서비스하고, 각 릴레이스테이션(RS)들은 자신이 갖고 있는 N개의 서브캐리어를 사용하여 자신에게 할당된 사용자 단말기(UE)들에게 직교주파수다중분할접속(

) 방식으로 무선통신 서비스를 제공하는 다중 사용자 다운링크 릴레이 네트워크에서, (1) 상기 소스 스테이션(S)이 상기 릴레이 스테이션(RS)들을 서비스 해주는 동안에, 모든 사용자 단말기(UE)들은 각각 매 타임 슬롯마다 자신이 겪게 되는 간섭량을 스캔하여 자신이 가장 적게 간섭을 받게 될 타임 슬롯을 선택하는 단계; (2) 상기 사용자 단말기(UE)는 선택한 그 타임 슬롯에 자신을 담당하는 릴레이 스테이션(RS)에게 서비스를 요청하는 단계; (3) 상기 복수 개의 릴레이 스테이션(RS)들은 각각 자신이 담당하는 사용자 단말기(UE)들에 대해 그 사용자 단말기(UE)가 요청한 타임 슬롯에서 서비스를 제공하는 단계; 및 (4) 상기 복수 개의 사용자 단말기(UE)들이 모두 다른 타임 슬롯을 선택하여도 간섭량에 있어서 더 이상 지금보다 나은 결과를 가져오지 못하는 상태인 나쉬 평형(Nash Equilibrium) 상태에 도달할 때까지 상기 단계 (1) 내지 상기 단계 (3)을 반복적으로(iteratively) 수행하는 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 급변하는 사용자 요구 통신품질에 대한 만족도 개선방법이 제공된다.

상기 사용자 요구 통신품질에 대한 만족도 개선방법은, 상기 서비스를 요청한 사용자 단말기(UE)들은 다른 사용자 단말기(UE)가 자신과 같은 타임 슬롯을 선택하여 서비스를 요청함으로 인해 자신이 선택한 타임 슬롯이 최소 간섭을 일으키는 타임 슬롯이 아닌 것으로 판단되는 경우, 최소 간섭을 유발하는 타임 슬롯을 다시 선택하여 자신을 담당하는 릴레이 스테이션(RS)에게 서비스를 다시 요청하는 단계를 더 포함할 수 있다.

또한, 상기 사용자 요구 통신품질에 대한 만족도 개선방법은, 상기 릴레이스테이션(RS)에서 상기 사용자 단말기(UE)로의 정보 전송량(RS->UE 전송률)이 상기 소스스테이션(S)에서 상기 릴레이스테이션(RS)으로의 정보 전송량(S->RS 전송률) 보다 크지 않으면, 해당 사용자 단말기(UE)는 타임 슬롯을 추가적으로 더 선택하여 자신을 담당하는 릴레이 스테이션(RS)에게 서비스를 요청하는 단계를 더 포함할 수 있다.

상기 사용자 요구 통신품질에 대한 만족도 개선방법은 또한, 상기 복수 개의 릴레이스테이션(RS) 각각은 자신이 서비스하고 있는 사용자 단말기(UE)들에 대하여 주파수를 할당하는 단계를 더 포함할 수 있다. 이 경우, 상기 릴레이스테이션(RS)이 자신이 담당하는 2 이상의 사용자 단말기(UE)에게 상기 주파수를 할당함에 있어서, 한 가지 방법은, 각 사용자 단말기(UE)의 QoS 요구에 관한 히스토리를 참조하여 QoS의 변동(variation)이 큰 사용자 단말기(UE)에 대해서는 많은 주파수를 할당하고 QoS의 변동(variation) 적은 사용자 단말기(UE)에 대해서는 적은 주파수를 할당하는 것이다. 상기 릴레이스테이션(RS)이 자신이 담당하는 2 이상의 사용자 단말기(UE)에게 상기 주파수를 할당함에 있어서, 다른 한 가지 방법은, 각 사용자 단말기(UE)의 QoS 요구에 관한 히스토리를 참조하여 가장 많은 QoS의 변동을 보여주는 사용자 단말기(

)에게 서브캐리어

을 모두 할당을 하여 시작하고, 자신이 담당하는 사용자 단말기(UE)가 추가될 때마다 그 사용자 단말기(UE)의 QoS 변동 정보를 바탕으로 하여 그 변동의 정도가 큰 순서로 등비수열로 서브캐리어를 할당하는 것이다. 그리고 상기 등비수열로 서브캐리어를 할당할 때 적용되는 등비는 1/2인 것이 바람직하다.

위와 같은 사용자 요구 통신품질에 대한 만족도 개선방법에 있어서, 특정 사용자 단말기(UE)가 QoS 요구를 올리면, 그 특정 사용자 단말기(UE)에 대한 서비스를 담당하는 릴레이 스테이션(RS)은 자신이 서비스를 담당하는 사용자 단말기(UE)들 중에서 만족상태에 있는 사용자 단말기(UE)의 주파수 양보에 따른 주파수 공백화를 수행하는 단계를 더 포함하는 것이 바람직하다.

상기 주파수 공백화는, 한 가지 방법으로서, (a) 상기 릴레이 스테이션(RS)의 서비스에 대해 만족 상태에 있는 사용자 단말기(UE)가 주파수 공백화를 자신을 담당하는 릴레이 스테이션(RS)에게 요청하는 단계; (b) 주파수 공백화를 요청받은 릴레이 스테이션(RS)은 그 요청을 자신을 담당하는 소스 스테이션(S)에게 전달하여 그 소스 스테이션(S)이 해당 서브캐리어를 공백화(nulling) 하고, 그 주파수 공백화를 요청받은 상기 릴레이 스테이션(RS) 또한 상기 해당 서브캐리어를 공백화하는 처리를 하는 단계를 통해 달성될 수 있다. 그리고, 상기 단계 (a)에서 상기 만족 상태에 있는 사용자 단말기(UE)는 자기 자신이 만족 상태를 유지할 수 있는 한도 내에서 상기 주파수 공백화를 요청하는 것이 바람직하다.

상기 주파수 공백화는, 다른 방법으로서, (i) 상기 릴레이 스테이션(RS)의 서비스에 대해 불만족 상태에 있는 사용자 단말기(UE)가 자신에게 가장 간섭을 많이 주는 서브캐리어와 해당 타임 슬롯에 관한 정보를 자신을 담당하는 릴레이 스테이션(RS)에게 업로드해주는 단계; (ii) 그 릴레이 스테이션(RS)은 그 업로드 받은 정보를 자신을 담당하는 소스 스테이션(S)에게 업로드해 주어 그 소스 스테이션(S)이 그 업로드 받은 그 정보를 토대로 해당 서브캐리어를 공백화(nulling)하고, 그 주파수 공백화를 요청받은 상기 릴레이 스테이션(RS) 또한 상기 해당 서브캐리어를 공백화하는 처리를 하는 단계를 통해 달성될 수 있다.

본 발명에 의하면, 릴레이 네트워크에서 완벽히 분산적으로 운영되는 게임이론에 입각하여 시간 자원과 주파수 자원을 활용하여 사용자 단말기(UE)가 받는 간섭량을 최소화하여 정보 전송량을 극대화할 수 있다. 복잡도와 정보 전송량 증대의 관점에서 시간 자원을 활용함으로써 파워 자원을 활용할 때보다 더 큰 이득을 이끌어낼 수 있다.

또한,

가 처한 상황에 따라 다수의 타임 슬롯을 선택할 수 있게 하므로써 최적의 정보 전송량을 얻을 수 있고, 이로 인해 셀 전체의

들은 만족 상태에 도달하게 된다.

나아가, 모든

들이 만족 상태에 도달한 후 불특정

가 자신이 요구하는

를 올리게 될 경우, 이를 유연하게 대처할 수 있는 서브캐리어 할당 및 주파수 공백화 기법을 이용하여 기존에 상용화되던 공평성 개념보다 더 실질적인 공평성 개념을 충족시켜 준다.

도 1은 종래의 ODF방식으로 게임을 하는 방법을 설명하기 위한 도면이고,
도 2는 파워와 정보 전송량의 관계를 나타내는 그래프이고,
도 3은 본 발명에 따른 다중 셀 셀룰러 네트워크 시스템 모델이고,
도 4는 발명에 따른 다중 셀 셀룰러 네트워크 시스템 모델을 단일 셀 모델화 한 도면이고,
도 5는

의 RB 행렬이며,
도 6은

번째 서브캐리어에서 이루어지는 한 판의 게임 (제1단계)을 도시하며,
도 7은

번째 서브캐리어에서 이루어지는 한 판의 게임 (제2단계)을 도시하며,
도 8은

번째 서브캐리어에서 이루어지는 한 판의 게임 (제3단계)을 도시하며,
도 9는 임의의

번째 게임을 도시하며,
도 10은 RB 선택의 제1단계를 도시하며,
도 11은 특정 타임 슬롯에 몰려든 복수의

쌍 때문에 간섭량이 늘어나는 상황을 나타낸 도면이며,
도 12는 나쉬 평형(Nash Equilibrium) 상태에 도달하여 게임을 멈출 수 있는 상황을 도시하며,
도 13은 S가 특정 RS에게 서비스할 때 그 특정 RS와 연동되어 있는 UE가 간섭량을 스캔하는 것을 나타낸 도면이며,
도 14는 본 발명이 제시하는 셀 전체 정보 전송량을 최대화 하기 위한 게임의 실행순서를 나타낸 흐름도이며,
도 15는 UE들에게 QoS의 변동이 큰 순서대로 1/2의 등비로 서브캐리어를 할당하는 본 발명의 방법을 나타낸 도면이며,
도 16은 불만족 상태에 있는 UE가 확률적으로 정보 전송량을 증가시킬 수 있는 완벽히 분산적인 RS의 주파수 공백화 기법을 설명하기 위한 도면이며,
도 17은 불만족 상태에 있는 UE가 확률적으로 정보 전송량을 증가시킬 수 있는 완벽히 분산적인 RS의 주파수 공백화 기법의 실행 순서를 나타낸 흐름도이며,
도 18 내지 도 20은 불만족 상태에 있는 UE의 정보 전송량을 확실하게 증가시켜줄 수 있는 주파수 공백화 기법을 설명하기 위한 도면들이며,도 21은 불만족 상태에 있는 UE의 정보 전송량을 확실하게 증가시켜줄 수 있는 주파수 공백화 기법의 실행순서를 나타낸 흐름도이다.

이하에서는 첨부한 도면을 참조하여 본 발명에 대하여 보다 구체적으로 설명하기로 한다.

I. 본 발명이 적용될 수 있는 시스템 모델

(1)시스템 모델

본 발명에서 최종적으로 고려하게 될 시스템 모델(100)은 도 3과 같다. 한 개의 중심 셀(102)이 있고, 그 주위에 인접셀(104) 6개가 존재하게 된다. 각 셀마다 1개의

가 존재하고,

개의

이 존재하고, 7개의 셀에

개의

가 랜덤하게 분포되어 있는 경우를 고려한다.

와

들은 모두

개의 서브캐리어를 갖는다. 무선 이동통신망에서, 소스 또는 소스스테이션 S는 예컨대 하나의 셀을 담당하는 기지국(base station)이고, 릴레이 스테이션 RS는 중계기, 그리고 사용자 단말기 UE는 가입자의 이동통신단말기일 수 있다.

는

들을

방식으로 서비스하고, 각

들은 자신이 갖고 있는

개의 서브캐리어를 사용하여 자신에게 할당된

들을

방식으로 서비스한다.

는

로 동작하여 동시에 송수신을 하지 않는 것을 가정하고,

방식을 사용한다. 그리고 주파수, 시간 자원의 효율성과 문제 해결의 간략화를 위해

링크는 없다고 가정한다.

(2) 용어의 정의

본 발명의 설명에 사용되는 용어 간섭(Interference), 나쉬 평형(Nash Equilibrium), 분산적 방식(Distributed Manner), 그리고 주파수 공백화(Frequency Nulling)는 다음과 같은 의미를 갖는다.

(i) 간섭(Interference): 같은 주파수 대역을 사용하는 다른 링크에 의하여 받게 되는 간섭량.

(ii) 나쉬 평형(Nash Equilibrium): 사용자 단말기가 다른 선택을 하여도 더 이상 지금보다 나은 결과를 가져오지 않는 상태

(iii) 분산적 방식(Distributed Manner): 중앙집중식 방식(Centralized Manner)과 반대되는 기법으로 중앙에서 연산을 일괄적으로 하는 것이 아니라, 연산을 분산적으로 처리하는 것을 의미한다.

(iV) 주파수 공백화(Frequency Nulling): 사용자 단말기를 서비스 해주는 다수의 서브캐리어 중 일부를 공백화(nulling) 하는 기법.

(3) 신호 모델

먼저, 기본 게임의 알고리즘을 소개하기 위해 도 3의 다중 셀 환경을 도 4와 같은 단일 셀 환경으로 간략화 해보자.

개의

쌍이 존재하게 된다. 다른 조건은 위에서 가정한 것과 모두 동일하다.

은 S에서

번째 서브캐리어를 이용하여

번째

로 가는 채널 이득을 의미한다.

{h _{i,j} ^{k}은

번째

에서

번째 서브캐리어를 이용하여

번째

로 가는 채널 이득을 의미한다. 그에 따라,

일 때의 {h _{i,j} ^{k}는

번째

가

번째

에게 주는 간섭 채널 이득이 된다.

은

에서

번째 서브캐리어를 이용하여

번째

를 서비스 해주는 동안

번째

가 겪는 간섭 채널 이득이다. S에서

들을 서비스 해줄 때

방식을 사용하므로 모든 서브캐리어들을 해당 시간에 해당

에게 모두 사용하고 있기 때문에

와

의 직접적인 링크는 없다고 본다. 따라서

일 때의 {y _{i,j} ^{k}는 모두 0이 된다.

은

번째

가

번째

를 서비스 해주는 동안

번째

가 받는 간섭 채널 이득을 의미한다. 따라서 이 역시

일 때는 자기 자신에게 주는 간섭 채널 이득을 의미하므로

는 모두 0이 된다.

S의

번째 서브캐리어에 실리는 송신 전력과 i번째

의

번째 서브캐리어에 실리는 송신 전력은 각각

,

이다.

II. 문제 해결을 위한 게임 디자인

1. 게임

의 전략 (셀 전체 정보 전송량 최대화)

경쟁적 전력 조절 게임(competitive power allocation game)의 비효율성을 개선하기 위해, 본 발명에서는 게임 자원 자체를 전력에서 시간과 서브캐리어 자원으로 바꾼다. 또한 기존의 ODF의 시간 활용 측면의 비효율성을 고려하여, 기존의 방식처럼 마지막 타임 슬롯에서 동시에 모든 RS가 동기화가 되는 기법이 아닌, 각 RS가 자신이 담당하는 UE를 서비스해줄 시간을 선택한다는 아이디어를 기본으로 한다.

본 발명의 구체적인 아이디어를 설명하기에 앞서 자원블록(Resource Block: RB)이라는 개념을 소개한다.

는

번째 서브캐리어와

번째 타임 슬롯에 관한 RB를 나타낸다. 현재의 시스템 모델에서는 도 5에 나와 있는 바와 같이

의 RB 행렬이 형성되고, 게임의 기본 주제는

번째 RS가 자신이 담당하는

번째 UE를 서비스해 줄 때, 마지막 타임 슬롯에서 동시적으로 활성화되는 것이 아니라,

번째 서브캐리어를 활용할 수 있는 타임 슬롯을 결정하여 그 타임 슬롯에 해당하는 RB를 선택하는 것이 된다.

------------------------------------------------------------------

(문제 1) : maximize

subject to

,

......(2)

------------------------------------------------------------------

은

가

번째 서브캐리어로 인해 서비스 받는 정보의 양이며

에 관한 함수이다.

는

가 서비스 받는 총 정보 전달양이다.

는

개의 서브캐리어의 집합이다.

는

의

번째 게임에서

번째 이터레이션(iteration)에서의

선택 행렬이고, 뒤편에

선택 과정에서 자세히 다룬다.

, 즉

번째

를 제외한 다른

들의

선택 행렬을

로 나타내기로 한다.

는

번째 게임

에서

를 선택할 수 있는 모든 경우의 수를 나타낸 집합이 된다. 가장 현명한

를 찾는 것이 이 게임의 목적이다.

가

번째 서브캐리어로 인해 서비스 받는 정보의 양

는 다음과 같다.

......(3)

는

링크에서의

번째 서브캐리어로 인해 전송된 정보가 받는 간섭량이고, 이는

에 대한 함수이다.

는

링크에서의

번째 서브캐리어로 인해 전송된 정보가 받는 간섭량이다.

완벽히 분산적인 상황을 고려하고 있기 때문에

는

가 선택할 수 있는 사항이 아니며, 자신이 조절할 수 있는

만이 게임의 요소가 된다. 모든

가 자신의

를 최소화 하려는 이기적인 철학을 가지고 움직이는 게임이 이루어진다. 정보의 양의 식에 따라 문제 1은 게임

으로 귀결된다. 게임

를 수학적으로 표현하면 아래와 같다.

------------------------------------------------------------------

: minimize

subject to

,

......(4)

------------------------------------------------------------------

정의 1 :

는 가장 현명한

가 되고, 게임

의

이 된다.

(

,

)

.......(5)

------------------------------------------------------------------

따라서 서브캐리어

개에 해당하는 수만큼의 게임이 완벽히 독립적으로 이루어진다. 시간 축에 비어있는

개의 RB를 가지고

개의

쌍이 경쟁적으로 게임을 하는 구도가 된다.

아래 정리 1에 의해 게임

는 적어도 하나의

지점을 갖게 된다.

------------------------------------------------------------------

정리 1 : 게임

는 적어도 하나의

지점을 갖는다.

집합

의

는

개로 유한개이다.

집합

는 유클리디안 스페이스의

이다.

------------------------------------------------------------------

가능한 모든

의 집합인

가 유한 집합이기 때문에 (따라서, 동시에

하기 때문에)

를 만족시키는

가 반드시 적어도 한 개는 존재한다.

가. 게임 개념 소개

링크가 이미 형성되어 있고,

는 송신과 수신을 동시에 수행하는 것은 불가능한

기법을 사용하고 있기 때문에, 도 5에서

에 해당하는 RB는 '

' 표시를 해 두었다. 즉, (

)에 해당하는 RB의 '×' 표시는

번째 타임 슬롯이

가

에 서비스하는 타임 슬롯인 관계로

가

에 송신할 수 없음을 의미한다.

는

번째

쌍 (RS->UE)i이

번째 서브캐리어에서

번째 타임 슬롯

을 선택한 것을 의미한다.

이하에서 설명하는 게임은 서브캐리어

개에 해당하는 수만큼의 완전히 독립적인 게임들이다.

번째 서브캐리어에서 이루어지는 한 판의 게임을 살펴본다.

① 주어진 초기 조건에 의해 모든

쌍들이 도 6과 같은 선택을 한다. 도 6의 예로 본다면

쌍,

쌍, 그리고

쌍이 모두

를, 즉

번째 게임에서 3번째

를 선택했다.

② 모든

쌍들은 이기적 철학에 기반하여 자신이 처음에 선택했던 것보다 더 나은

를 찾아서 선택을 변경하게 된다. 도 7에 예시된 경우에 있어서는,

쌍은 현재 선택된

에 만족하여 그

를 유지하는 데 반해,

쌍 과

쌍은 현재 선택된

에 만족하지 못하여 더 나은 다른

로 선택을 변경한다. 이와 같은 작업이 반복하여 이루어진다.

③ 모든

쌍들이 더 이상 다른 선택을 해도 나아질 것이 없는 상황 즉, 나쉬 평형상태(

)에 도달한다. 그렇게 되면 모든

쌍들은 안정된 상황에 봉착하게 되고 게임을 멈추게 된다.

나. 게임 알고리즘 소개 (The strategy of game)

이제, 본 발명이 제안하는 알고리즘을 구체적으로 설명한다. 각

가 가지고 있는

개의 서브캐리어를 할당하는 것도 하나의 이슈가 되므로 각

당 담당하는

가 1개 일 때와, 각

당 담당하는

가 복수 개 일 때로 나누어 살핀다.

우선, 서브캐리어 할당의 문제를 일단 배제하기 위해 각

당 담당하는

가 1개라고 가정을 한다.

각

당 담당하는

가 1개 이므로

개의 모든 서브캐리어를 자신이 담당하는

에게 모두 할당한다. 이번에도 게임 개념 소개에서와 마찬가지로 임의의

번째 게임을 보겠다.

------------------------------------------------------------------

● 정리 2 :

링크들이 완전히 타임 오쏘고날 할 때, 완벽히 분산적인 상황에서 이상적인 RS 타임 스케줄링이 존재한다.

①

가 비는 시간을 활용하여 time scheduling을 하였을 경우 (본 발명의 아이디어의 경우)

는 서브캐리어

를 사용하는

들이

가

로부터 서브캐리어

를 통하여 서비스 받는 동안 주는 간섭량이다.

가

로부터 서비스 받는 타임 슬롯을 선택한

만이

에게 간섭을 주게 된다. 이는 뒤에 나올

와 차이를 보인다.

는 서브캐리어

를 사용하는

들이

가

로부터 서브캐리어

를 통하여 서비스 받는 동안 주는 간섭량이다.

②

가 비는 시간을 활용하지 않고

번째 타임 슬롯에 모든

가 동시에 동기화 되는 경우

]

는

로, 자신에게 지정된

가 아닌, 다른 모든

들이

에게 미치는 총 간섭량이다.

③

scheduling 없이 남는 모든 시간에

가

를 서비스하는 경우

가 된다.

서비스 시간에 모든

들이 동작하고 있기 때문에 모든

로부터

로 가는 간섭이 발생한다.

는

가 된다.

③번에서의

에서는

이 아닌

로 노말라이즈 해 준다. 그 이유는 ③번에서는

스케쥴링 없이 남는 모든 시간에

가

를 서비스 해주기 때문에

서비스 시간을 제외한 모든 시간을

로 활용한다.

①과②의 대소를 비교하면,

이고, ①과 ③의 대소를 비교하면

임을 알 수 있다.

------------------------------------------------------------------

정리 2에 의해 모든

들은 자신에 상황에 맞는 현명한

를 선택하여 스케쥴링을 할 이유가 생겼다.

칸에 해당하는

들은 모두

가 서브캐리어

를 사용하여

를 서비스해주는 것을 의미한다. 즉

는 자신이 서비스 받는

번째 타임 슬롯을 선택할 수 없고 이를 제외한

개의 선택이 가능하다.

쌍은 가장 현명한 선택을 하기 위해

개의 타임 슬롯 동안 자신이 겪는 간섭을 스캔한다. 초기 상태에는

링크만 존재하기 때문에

가

를 서비스 해주는 동안엔

를 제외한 다른 모든

들은 간섭을 받게 된다.

번째 게임에서,

에 의해서

가 겪는 간섭량을 벡터로 표시하면 아래와 같다.

,

......(6)

,

......(7)

위의 시스템 모델에서 제시하였듯이,

에서

번째 서브캐리어를 이용하여

를 서비스 해주는 동안

번째

가 겪는 간섭 채널 이득을

로 표시하기로 한다. 전력은 균등하게

등분 하여 각 서브캐리어에 싣게 되므로

로부터

가 받은 수신 전력을

로 나타낸다면,

는

에서

번째 서브캐리어를 이용하여

를 서비스 해주는 동안

가 겪는 간섭량을 나타내고,

는

를 구성성분(element)으로 하는

의 간섭량 벡터를 나타낸다. 마찬가지로,

로부터

가 받는 수신 전력을

로 표시할 때,

는

에서

번째 서브캐리어를 이용하여

를 서비스 해주는 동안

가 겪는 간섭량을 나타내고,

는

의 간섭량 벡터를 나타낸다.

는 0이다. 즉,

의 경우,

개의 구성성분이 있고,

번째 타임 슬롯에는 자기 자신의

, 즉

가 서비스 받는 시간이기 때문에 역시 간섭이 0이 된다. 마찬가지로

의 경우,

개의 구성성분이 있고,

번째 타임 슬롯에는 자기 자신의

, 즉

가

를 서비스하는 시간인 바

가

를 서비스하는 것은 넌센스이기 때문에 역시 간섭이 0이 된다. 위의 식처럼

가

들을 서비스 해주는 동안에

개의

쌍이 각자 자신이 겪는 간섭을 나타내는 간섭량 벡터

를 갖게 되었고,

들끼리의 간섭량을 나타내는

가 구해진다.

모든

의

와

를 행으로 덧붙여

행렬로 나타내고, 이를

와

라 하면 다음과 같다.

,

......(8)

각자 가지고 있는 간섭량 정보인,

링크로 인해 발생되는 간섭량 테이블

와

링크로 인해 발생되는 간섭량 테이블

를 토대로 게임을 시작한다.

㉠

선택 과정

는

번째 게임에서

에 의해서

가 겪는 간섭량을 나타낸

들을 각자 초기 패로 가지고 있다. 완벽히 분산적이기 때문에 각

는 자신의

만을 알게 된다.

여기서 중요한 점은 게임을 하는

쌍은

는 스스로 알 수 있지만,

는 모든

쌍들이 '

선택'을 하기 전까지는 스스로 알지 못한다는 점이다. 그 이유는

는 단지 간섭량을 나타내는 표에 불과하고, 몇 번째

가 몇 번째 타임 슬롯을 선택하느냐가 결정이 되어야

에서 해당하는 값들을 뽑아 낼 수 있기 때문이다. 즉, 각

들이 어떤 타임 슬롯을 선택하느냐에 따라 서로 영향을 미치는 간섭량이 달라지기 때문에

간의 간섭량을 나타내는 새로운 벡터

가 필요하다.

이를 알아보기 위하여 우선, '

선택' 과정을 살펴보자.

첫 번째 이터레이션(iteration)에서는

간의 간섭량 정보가 전혀 없으므로(아직 동작하는

가 하나도 없으므로),

만을 가지고 게임을 한다. 모든

쌍이 이기적이고, 분산적으로 움직이기 때문에 자신이 겪는 간섭량 중 가장 적은 간섭량에 해당하는

를 선택하여, 자신을 담당하고 있는

에게

를 업데이트하여 자신이 서비스 받았으면 하는 타임 슬롯을 업데이트 한다. 이는 이 게임에 기본 전략이 된다.

= {

번째 게임에서,

쌍이 선택한 타임 슬롯}

=

......(9)

(element '0'을 제외한

값)

이로 인해

선택 행렬이 만들어 진다.

= {

쌍의

선택 행렬}

= {

번째 게임에서,

번째 이터레이션에서,

쌍이 선택한 타임 슬롯}

=

......(10)

번째만 1이고 나머지는 모두 0이다. 즉

쌍이 선택한

번째 타임 슬롯에만

가 작동하여

를 서비스 해 준다는 의미로, 나머지 타임 슬롯은 사용하지 않겠다는 의미가 된다.

이 또한 마찬가지로 행으로 덧붙여

선택 행렬

를 만들 수 있다.

......(11)

라는 초기 패를 가지고 모두 자신이 가장 간섭을 덜 받을

를 선택하여 그 타임 슬롯에 자신이 담당하는

를 서비스 해 준다. 모두 같은 전략으로 행동하기 때문에 특정 타임 슬롯을 동시에 선택하는 경우가 생길 수 있다. 예를 들어,

에서

를 서비스 해줄 때,

가 아닌 다른

들에게

가 미치는 간섭량이 현저히 작을 때 다른

들은 모두들

, 즉

번째 타임 슬롯을 선택할 것이다. 이렇게 되었을 시에 모두들 지금 현재 선택이 옳다면 (다른 타임 슬롯을 선택하여도 지금보다 나아질 것이 없다면), 현재 상태에서 멈춰도 된다. 하지만 모두들

번째 타임 슬롯을 선택하였기 때문에, 간섭량이 가장 작은 줄 알았던

번째 타임 슬롯이 오히려 같이 몰려든

쌍 때문에 간섭량이 늘어나는 사태가 발생한다. 도 11은 그 현상을 보여주고 있다.

쌍과

쌍이 동시에 4번째 타임 슬롯을, 즉

=

가 되었다. 간섭량이 가장 적은 것으로 판단하여 동시에 4번째 타임 슬롯에 각각

과

를 서비스 해 주었지만,

은

과 동시에 활성화된

때문에,

는

와 동시에 활성화된

때문에 결과적으로 더 큰 간섭량을 받게 된다.

따라서

번째 게임에서의,

번째 이터레이션에서의,

간의 간섭량

는 아래와 같이 정의된다.

= {

번째 게임에서의,

번째 이터레이션에서의,

간의 간섭량}

=

......(12)

또한,

쌍이

번째 게임에서의,

번째 이터레이션에서의,

쌍에 의한 간섭량

는 아래와 같이 정의된다.

= {

의

번째 행} ......(13)

다음 이터레이션 시에 간섭량들을 다시 스캔할 때,

는 전의 이터레이션에서 선택했던 타임 슬롯보다 더 작게 간섭을 받게 될 타임 슬롯이 존재 하지 않는다면 더 이상 다른 선택을 하지 않고 게임을 멈추게 된다. 하지만 모든

쌍들이 게임을 한 후에 더 작게 간섭을 받게 될 타임 슬롯이 생겨난 것으로 스캔 결과가 나온다면, 그 다음 이터레이션 때에 지금의 결과를 반영한다.

쌍이

번째 이터레이션에서 스캔한 총 간섭량을

이라 정의하자.

처음 이터레이션에서는

링크에 의한 간섭량만이 존재하므로,

......(14)

번째 이터레이션에서는,

링크에 의한 간섭량

정보와 (

)번째 이터레이션에서의

선택 행렬이 고려된다.

......(15)

위의 수식 (15)를 바탕으로

번째 게임에서의

쌍의 모든 타임 슬롯 마다의 간섭량이 업데이트 된다.

업데이트된 간섭량

을 바탕으로

가 결정된다.

(

)

=

......(16)

수식 (16)에서 정의한 바와 같이 '*' 번째 원소만 1이고 나머지는 0이다.

이터레이션이 반복 되다가,

이 되었다면

쌍은 게임을 종료하고 마지막에 선택한

번째 타임 슬롯인

에

가 동작하여

를 서비스해준다.

이로 인해 최종적으로

가 서브캐리어

에서 겪는 간섭량이 결정된다.

는 게임이 종료되어

에 도달했을 때의 간섭량 벡터가 된다. 최종

선택 행렬에

를 곱하여 최종적으로 겪게 되는 간섭량을 얻는다.

......(17)

------------------------------------------------------------------

정리 2:

가 되는 지점, 즉

가 최종적으로 선택하는

는 유일한

지점을 갖게 되고, 나아가

또한

로 수렴한다.

------------------------------------------------------------------

선택 행렬을 선택하는 알고리즘을 정리하면 아래와 같다.

------------------------------------------------------------------

● 알고리즘 I: 완벽히 분산적인

선택 (서브캐리어 별로 각각 게임)

단계 1.

서비스 기간에

가 겪는 간섭량

를 바탕으로 첫 번째 선택을 한다.

는 자신이 가장 덜 간섭을 받는 타임 슬롯을 선택한다.

여기서,

는

쌍이

번째 이터레이션에서 스캔한 총 간섭량이며, 처음 이터레이션에서는

링크에 의한 간섭량만이 존재하므로

이다.

단계 2. 모든

가 자신이 가장 덜 간섭을 받는 타임 슬롯을 선택하였기 때문에, 간섭량

가 업데이트 되고 새로운 최소값(

)을 찾게 된다.

단계 3.

가 될 때까지 단계 2 반복하고, 조건이 만족되면 게임 종료.

------------------------------------------------------------------

알고리즘 I를 통하여 모든

들은 서브캐리어

를 통하여 겪는 간섭량을 계산하고, 자신이 가장 적게 간섭을 받게 되는 타임 슬롯을 반복적으로 선택하게 되어 결국엔 모든

들이 자신들에게 최적화된

를 선택하게 되어

를 최소화 하였다.

하지만, 이렇게 서브캐리어 별로 게임을 따로 하게 되면

가 모든 간섭량을 서브캐리어 별로 다 올려야 되기 때문에 서브캐리어의 수만큼의 게임

가 독립적으로 운영되어 복잡도가 높다.

모든

가 자신이 겪는 간섭량

을 모든 서브캐리어

마다

에게 업데이트를 하게 된다면, (서브캐리어의 수

게임

의 복잡도

쌍의 수

) 만큼 복잡도가 늘어나게 된다. 따라서 아래와 같은 간략하고 새로운 방법을 제시한다.

게임 운영 방법은 위의 알고리즘 I과 정확히 일치한다. 하지만 서브캐리어

개의 모든 정보를 합쳐서

개의 독립적인 게임을 단 한 개의 게임으로 압축한다. 따라서 게임의 기본 정보가 되는

는 아래와 같이

로 바뀌게 된다.

......(18)

......(19)

에 의해

는

로 대체된다.

는 아래와 같다.

......(20)

를 선택하는 게임 운영 방법은 알고리즘 I와 일치하므로 자세한 설명은 생략한다.

= {

쌍이 선택한 타임 슬롯}

=

......(21)

= {

쌍의

선택 행렬}

= {

번째 이터레이션에서,

쌍이 선택한

}

=

......(22)

------------------------------------------------------------------

● 알고리즘 II: 완벽히 분산적인 RB 선택 (서브캐리어 한 개인 것처럼 압축)

단계 1.

서비스 기간에

가 겪는 간섭량

를 바탕으로 첫 번째 선택을 한다.

는 자신이 가장 덜 간섭을 받는 타임 슬롯을 선택한다.

단계 2. 모든

가 업데이트 되고 새로운 최소값(

)을 찾게 된다.

단계 3.

가 될 때까지 단계 2 반복하고, 조건이 만족되면 게임 종료.

------------------------------------------------------------------

알고리즘 II는 알고리즘 I 와 달리 서브캐리어

마다 독립적인 게임이 운영되는 것이 아니라,

쌍이 매 타임 슬롯마다 겪는 간섭량을 서브캐리어 구분 없이 하나로 보게 되어, 게임 수가

개에서 한 판으로 줄어들게 된다. 따라서 알고리즘 II는 복잡도가 (게임

의 복잡도

쌍의 수

) 에 비례하게 되어 복잡도가 훨씬 줄어들게 된다.

㉡ 정보 전송량 결정

위에서 결정된

를 통하여

가 결정된다.

......(23)

가 서브캐리어

를 통하여 서비스 받는 정보의 양

는 아래 식과 같이 결정된다.

......(24)

여기서,

인 상황이라면,

가 최종 정보의 양이 되기 때문에 별다른 문제가 없다. 하지만

인 상황에서는 최종 정보의 양이

가 되기 때문에 최종 정보의 양을 증가시킬 수 있다. 즉,

인

는 또 다른 타임 슬롯을 추가적으로 선택할 수 있다. 따라서

의 조건에 놓인

는 게임을 더 할 필요가 없게 되고,

인 조건에 놓은

는 사용하지 않은

를 활용하여 추가적인 게임

을 전개한다.

결국,

인

는

가 될 때 까지 게임

을 반복하게 된다.

는

가 되도록 타임 슬롯을 복수 개를 선택할 수 있기 때문에 결론적으로

가 된다. 하지만,

가

개의 타임 슬롯을 모두 선택하였음에도 불구하고

라면,

가 될 것이다.

......(25)

도 14는 게임

를 간략하게 나타낸 순서도이다. 이 순서도를 참조하면서 게임

의 전략에 기반한 셀 전체 정보 전송량을 최대화 하는 방법을 구체적으로 설명한다. 각 RS(400)는 자신이 서비스하고 있는 UE들에 대하여 주파수를 할당한다(S10 단계). 주파수를 할당함에 있어서, 각 UE(500)의 QoS 요구에 관한 히스토리를 기반으로 변동(variation)이 큰 UE에 대해서는 많은 주파수를 할당하고 변화가 적은 UE에 대해서는 적은 주파수를 할당한다.

주파수 할당이 완료되고 나면 S(300)는 이제 서비스를 시작한다(S12단계). 모든 RS(400)에게 TDMA 방식을 사용하여 시간적으로 오쏘고날(orthogonal)하게 서비스 한다. S(300)가 RS_i(400)들을 서비스 해주는 동안에 각 UE는 매 타임 슬롯마다 자신이 겪게 되는 간섭량을 스캔한다(S14 단계). 각 UE(500)는 스캔한 간섭량을 바탕으로 하여 자신이 가장 적게 간섭을 받게 될 타임 슬롯을 정하여(S16 단계) 자신을 담당하는 RS(400)에게 정보를 요청한다(S18 단계).이러한 요청을 받은 RS(400)들은 각각 자신이 담당하는 UE에게 그 UE가 요청한 타임 슬롯에 서비스를 제공한다(S20 단계).

하지만 공교롭게도 복수의 UE(500)들이 같은 타임 슬롯을 선택하여 정보제공 서비스 요청을 한 경우(S18 단계)에는 간섭량이 최소 간섭이 되지 않고 오히려 더 늘어날 수 있다. 각 UE(500)는 그러한 상황이 발생하였는지를 체크한다(S22 단계). 선택된 타임 슬롯이 최소 간섭을 일으키는 타임 슬롯이 아닌 경우에는 단계 S16으로 돌아가서 최소 간섭을 유발하는 타임 슬롯을 다시 선택하는 과정을 새로 밟아, 종국에는 모든 UE가 자신이 만족하는 최소 간섭 유발 타임 슬롯을 결정하도록 한다.

이처럼 선택된 타임 슬롯이 최소 간섭을 일으키는 것으로 단계 S22에서 판단되는 경우, 모든 UE(500)가 만족 상태인 Nash equilibrium 상태에 도달하고(S24 단계), 정보 전송량도 최적에 도달하게 된다(S24 단계)였다. 물론 모든 UE(500)가 만족 상태에 이르지 못했을 수도 있지만, 이 또한 후설할 주파수 공백화(frequency nulling) 기법으로 해결될 수 있음).

또한, UE(500)는 RS(400)에서 UE(500)로의 정보 전송량(RS->UE 전송률)이 S(300)에서 RS(400)으로의 정보 전송량(S->RS 전송률) 보다 큰 상황이면(S26 단계), S(300)에서 RS(400)으로의 정보 전송량(S->RS 전송률)

가 최종 정보의 양이 되어 문제가 되지 않아 모든 UE(500)가 만족 상태에 있게 된다(S30 단계). 하지만, 전자가 후자보다 크지 않으면, 즉,

인 경우에는(S26 단계), 최종 정보의 양이

가 되기 때문에 최종 정보의 양을 증가시킬 수 있고, 그 경우 해당 UE(500)는 타임 슬롯을 추가적으로 더 선택하여(S28 단계) 자신을 담당하는 릴레이 스테이션(RS)에게 서비스를 요청하는 절차를 다시 밟는다(S14-S18 단계).

2. 서브캐리어 할당 및 주파수 공백화 기법 게임

(페어니스 만족과

의 요구사항 만족)

다음으로, 멀티 유저일 때, 즉

가 담당한

가 다수일 경우, 공정성(fairness)을 만족하면서 각

들이 요구하는

가 변동할 때 이에 대해 유연하게 대처하는 방법을 살펴보자.

가 담당한

가 하나일 때는 모든 서브캐리어를

에게 할당시키면 되었지만,

가 담당하는

가 다수가 될 경우엔 현명하게 서브캐리어를 나누어 주고, 또한 그 선택이 다른

가 서비스해주는

들에게 끼치는 영향을 고려하여야 한다.

㉠ 서브캐리어 할당

모든

마다

로서 동작을 시작하면서부터 지금까지 제각각 다른 QoS 이력(history)을 갖고 있을 것이다. 어떤

는 요구하는 QoS의 변동이 클 수 있고, 어떤

는 요구하는 QoS의 변동이이 작을 수 있다. 이를 고려하여

의 서브캐리어를 자신이 담당하는 다수의

에게 할당하는 방법을 생각하여 보자.

는

번째

가 담당하고 있는

의 개수이다. 따라서,

가 성립한다.

......(26)

위 수식 (26)에서 구한 QoS 평균을 가지고 QoS 변동

을 구한다.

......(27)

이제 각

마다

를 갖게 되고 자신을 담당하고 있는

에게 자신의

를 올리게 된다.

는 받은

정보들을 취합하고, 이를

라 하면,

가 된다.

가 갖고 있는 서브캐리어

을

번째

커버리지에 속해 있는

개 만큼의

에게 분배한다. 방법은 다음과 같다.

우선

안의 원소인

중에 큰 순서대로 우선순위를 갖게 된다. 편의를 위해

를 가정한다.

가 할당 받는 서브캐리어 수를

라 한다면,

가 성립한다.

를 가정하였으므로,

가 되어 QoS의 변동이 큰

에게 많은 서브캐리어를 할당하게 한다. 단계는 총

단계로 이루어진다.

가장 많은 QoS의 변동을 보여주는

에게 서브캐리어

을 모두 할당을 하고 시작을 한다.

그 후,

번째

가 추가 될 때마다

를 만족시키면서 서브캐리어를 할당한다. 즉, 각 RS당 담당하는 UE가 추가될 때마다, UE의 QoS 변동 정보를 바탕으로 하여 그 변동의 정도가 큰 순서로 등비수열로 서브캐리어를 할당한다. 이를 수학적으로 표현하면 아래와 같다.

------------------------------------------------------------------

● 알고리즘 III:

의 서브캐리어 할당

.....(28)

------------------------------------------------------------------

알고리즘 III 를 적용하여

들에게 서브캐리어를 할당하면 아래의 수식 (29)처럼 간략화 된 서브캐리어 할당이 나오게 된다.

......(29)

위와 같이 서브캐리어를 할당하여, 요구하는 QoS의 변동이 큰

에게 많은 서브캐리어를 할당하고, 상대적으로 요구하는 QoS의 변동이 작은

에게 적은 서브캐리어를 할당하게 된다.

또한 위 수식(29)와 같은 점화식 형태로 분배를 하게 되면 도 15에서 볼 수 있는 바와 같이 서브캐리어의 인덱스를 모든

마다 맞출 수 있을 것이다. 이는 뒤에서 다룰 주파수 공백화 기법에 매우 크게 기여할 사항이 된다. 또한, 서브캐리어를 알고리즘 III와 같이 배분함으로써, 위의 알고리즘 I와 알고리즘 II의 장점만을 배합하여 게임을 할 수 있게 된다.

도 15는 등비가 1/2인 경우의 서브캐리어 할당을 도시한다. 이와 같이 서브캐리어의 인덱스를 맞춰 준 후 N/2, N/4, N/8, ...를 새로운 게임의 최소 단위로 삼아 게임을 돌리게 된다. 그렇게 되면 N에 비례하던 복잡도가 log₂N+1에 비례하게 되어 서브캐리어의 개수가 많을수록 더욱 더 실용성이 높아진다.

● 가장 현명한 게임 구조 (알고리즘 IV)

위의 알고리즘 I는 가장 좋은 쓰루풋을 보이며

가 담당하는

가 다수일 때도 사용 가능하지만, 모든 서브캐리어 별로 독립적인 게임을 운영하기 때문에 서브캐리어의 수

만큼 복잡도가 상승하게 된다. 그리고 알고리즘 II는 복잡도가 서브캐리어의 수

과 상관없다는 장점을 갖지만, 알고리즘 I에 비해 쓰루풋이 낮고

가 담당하는

가 다수일때는 적용하기 힘든 단점이 있다.

알고리즘 IV에서는, 알고리즘 III에서

의 서브캐리어 할당을 기반으로 게임을 운영한다.

......(30)

......(31)

서브캐리어의 집합

을 위와 같은 방법으로 새로운 집합

로 쪼갠다. 모든

마다 자신이 담당하는

에게 서브캐리어를 알고리즘 III 과 같은 방법으로 배분하였기 때문에 위와 같은 새로운 집합

로 게임 운영이 가능하다. 예를 들면,

에는

,

가 있고,

에는

,

가 있다고 가정해 보자.

와

라 가정한다면,

만큼 서브캐리어가 할당될 것이다.

매치업 테이블
상대자		게임 자원
vs
vs

위의 매치업 테이블에서 나타낸 것처럼,

와

는

를 가지고 알고리즘 II와 같은 방식으로(모든 서브캐리어 정보를 독립적으로 보지 않고 한데 묶어서 활용) 게임을 운영한다.

의 경우 게임 자원을

만큼 가지고 있기 때문에,

를 가지고 있는

,

를 가지고 있는

,

를 가지고 있는

이렇게 총 3개와 게임을 진행한다.

알고리즘 IV의 장점은 각

당 최대

개의 다수의

를 커버할 수 있으며, 서브캐리어의 개수

에 비례하던 것을,

에 비례하는 복잡도를 갖도록 함으로서 복잡도 문제를 해결할 수 있고, 알고리즘 II 처럼 모든 서브캐리어를 한데 묶어서 한 번의 게임을 할 때보다 좋은 성능을 보인다는 점이다.

------------------------------------------------------------------

● 알고리즘 IV: 완벽히 분산적인

선택 (

가 담당하는

가 다수일 때)

1. 알고리즘 III을 통해 서브캐리어 할당

2. 게임 운영의 최소 단위

집합의 원소

내부에서는 알고리즘 II 방법으로 게임을 운영하고 서로 다른

끼리는 알고리즘 I 방법으로 게임을 운영한다.

------------------------------------------------------------------

㉡ 주파수 공백화 기법 게임

이와 같이, 요구하는 QoS의 변동을 토대로 서브캐리어를 할당을 한 후, 지금 현재의

들의 QoS를 만족시켜주기 위한 알고리즘을 제시한다. 도 15에서 표현하는 바와 같이, 위에 기법대로 서브캐리어를 할당하였다면 각

마다 할당된

들을 서비스 해주는 서브캐리어의 인덱스가 맞아 떨어질 것이다. 위의 게임

을 통하여

에 도달하는 것은 셀 전체의 쓰루풋을 극대화 시키는 것에만 초점이 맞추어져 있기 때문에 각

마다 원하는 데이터 량을 유동적으로 조절해 주는 것은 불가능 하다. 이제 공정성을 맞춰줄 수 있는 주파수 공백화 기법에 대해 살펴보자. 이는 전적으로 이타적인 기법이 된다.

: minimize

가 요구하는 QoS를

라 하고, 위의 게임

을 통해 결정된

의 정보 전송량을

라 하자.

인 경우는 문제가 되지 않겠지만,

인 경우엔

가 원하는 만큼의 데이터 량을 충족시켜 주지 못하기 때문에 문제가 발생하게 된다. 혹은 셀에 모든

들이 안정된 상태로 수렴한 뒤에, 갑자기

가 큰

를 요구할 때에도 이와 같은 문제가 발생하게 된다. 이를 해결하기 위해 아래와 같은 알고리즘 두 개를 제안한다.

첫 번째로, 완벽히 분산적인

의 주파수 공백화 기법

이다.

이는 완벽하게 분산적인 기법으로,

는 기존의 방식처럼 모든 서브캐리어를 사용하여 타임 오쏘고날하게 각

들을 서비스한다. 모든

들도 자신이 담당한

들을 서비스 해 주고

에 도달한 상태이다. 주파수 공백화 기법은 그 다음에 이루어진다.

도 16을 보자.

에 있는

는 요구하는 QoS인

보다 서비스 받고 있는 정보 전송량인

가 큰 단말이다. 이를 편의상 '만족 상태' 라 하자. 반대로

에 있는

는 요구하는 QoS인

보다 서비스 받고 있는 정보 전송량인

가 큰 단말이다. 이를 편의상 '불만족 상태'라 하자. 공백화 기법에서의

쌍들은 베이스 게임과는 반대로 이타적으로 작동하게 된다.

이를 위한 첫 번째 알고리즘이 아래에 정리된 알고리즘 V이다.

------------------------------------------------------------------

● 알고리즘 V:

의 주파수 공백화 기법 (완벽히 분산적)

게임

을 통하여

상태에 도달 한 후,

단계 1:만약 '만족 상태' 라면,

가 자신을 담당하고 있는

에게 자신이 할당받은 서브캐리어 중 임의의 서브캐리어를 공백화 시킬것을 요청한다.

만약 '불만족 상태'라면,

쌍은 기다린다.

단계 2: '만족 상태'에 있는

쌍의 공백화에 의해 '불만족 상태'에 있는

가 (확률적으로) 간섭량을 적게 받게 되고, 이로 인해 정보 전송량이 올라간다.

단계 3: 모든

가 '만족 상태'가 될 때 까지 단계1,2 를 반복한다.

------------------------------------------------------------------

도 17은 알고리즘 V에 따라 주파수 공백화를 수행하여 UE의 QoS 요구의 변화에 대처하는 방법을 도시하는 흐름도이다. 모든 UE들이 RS의 서비스에 대하여 만족 상태에 있다가 적어도 어느 하나의 UE가 QoS 요구가 높아져 불만족 상태로 바뀌는 경우를 고려한다.

이 경우, 먼저 만족 상태에 있는 UE(500)가 주파수 공백화(nulling)을 자신을 담당하는 RS(400)에게 요청한다(S50 단계). 다만 주파수 공백화를 요청하는 UE는 자기 자신이 만족 상태를 유지할 수 있는 한도 내에서 요청한다. 그 주파수 공백화를 요청한 UE(500)는 공백화 처리가 될 때까지 기다리고(S52 단계), 그 요청을 받은 RS(400)는 S(300)에게 이를 전달한다(S54 단계). S(300)는 RS(400)에 대해 주파수 공백화 요청을 받은 해당 서브캐리어를 공백화되도록 처리하고(S56 단계), 그 RS(400) 역시 UE(500)에 대하여 해당 서브캐리어에 대하여 주파수 공백화 처리를 수행한다(S58 단계).

이처럼 만족상태에 있는 UE의 양보에 의해 간섭량이 줄어들게 되어 결국 불만족 상태에 있는 UE도 만족 상태로 가게 된다(도 18 참조).

위의 알고리즘 V는 완벽하게 분산적이라는 장점이 있지만, '불만족 상태'에 놓인

의 정보 전송량이 '확률적으로' 증가한다는 단점이 있다. 즉, 불만족 상태에 있는 UE에게 직접적으로 혜택이 주어지는 것은 다분히 확률적이다. 왜냐하면

가

를 위하여 공백화를 한 서브캐리어

가 정작 불만족 상태에 있는

에게 큰 간섭을 주지 않았던 서브캐리어일수도 있고, 심지어는 애초부터

에게 할당되지 않았던 서브캐리어일 수도 있기 때문이다. 도 17은 이러한 상황을 도시한 것이다.

따라서 '불만족 상태'에 놓인

의 정보 전송량을 확실하게 증가시켜 줄 수 있는 방안이 필요하다. 이 방안을 아래 알고리즘 VI로 제시한다.

------------------------------------------------------------------

● 알고리즘 VI:

의 주파수 공백화 기법 (하이브리드)

게임

을 통하여

상태에 도달 한 후,

단계 1. '불만족 상태'에 놓인

는 자신이 '불만족 상태'에 놓였다는 사실과 자신을 가장 크게 괴롭히고 있는

's

(

는 게임

을 통해 찾은 타임 슬롯을 의미하고,

는 해당

에서 가장 큰 간섭을 주는 서브캐리어를 의미함.)를 자신을 담당하고 있는

에게 업로드한다.

단계 2.

는 스스로

에 해당하는 자원을 공백화 하고, 모든

에게

를 보내준다.

단계 3. 모든

는

자원을 사용하고 있는

가 '불만족 상태'라면 그대로 두고, '만족 상태' 라면 공백화를 시행한다.

단계 4. 모든

가 '만족 상태'가 될 때 까지 단계 1,2,3 을 반복한다.

------------------------------------------------------------------

도 21은 알고리즘 VI에 따라 주파수 공백화를 수행하여 UE의 QoS 요구의 변화에 대처하는 방법을 도시하는 흐름도이다. 위의 알고리즘 V와 마찬가지로 모든 UE들이 RS의 서비스에 대하여 만족 상태에 있다가 적어도 어느 하나의 UE가 QoS 요구가 높아져 불만족 상태로 바뀐 경우를 고려한다.

먼저, 불만족 상태에 있는 UE(500)가 자신에게 가장 간섭을 많이 주는 서브캐리어와 해당 타임 슬롯을 자신을 담당하는 RS(400)에게 업로드 한다(S70 단계). 그러면 그 RS(400)는 그 정보를 다시 S(300)에게 업로드 한다(S72 단계). S(300)가 해당 정보를 토대로 RS(400)에 대해 해당 서브캐리어 자원의 공백화를 수행한다(S74 단계). 계속해서 RS(400)가 해당 정보를 토대로 UE(500)에 대하여 해당 서브캐리어 자원의 공백화를 수행한다(S76 단계). 이를 통해, 불만족 상태에 있는 UE가 좀 더 확실한 확률로 만족상태에 도달하게 된다(S78 단계).

주파수 공백화 기법

의 경우,

의 입장에서 보았을 때, 해당 서브캐리어를 해당 타임 슬롯에 사용할 지 사용하지 않을지를 결정하는

의 문제이기 때문에 굉장히 간단한 연산이 된다. 더구나 필요한 정보를

가 직접 계산하는 것이 아니고, 단지

는

정보 전달 역할만 하기 때문에 더더욱 간단한 연산이 된다. 또한,

에서도 '불만족 상태'의

들의

를 공백화 해주는 것은 공평성충족에 더욱 결정적으로 기여한다. 알고리즘 VI의 경우, '불만족 상태'에 놓은

의 정보 전송량을 확실하게 올려 주기 때문에 아주 적은 양의 피드백 정보를 가지고 좋은 효과를 보는 효율적인 방법이다.

이상에서 설명한 본 발명의 방법은 S(300)용 프로그램, RS(400)용 프로그램 및 UE(500)용 프로그램으로 각각 만들어져 각각 해당 장비에 설치되어 실행됨으로써 구현될 수 있다. 당해 기술분야의 기술자라면 위에서 한 설명을 토대로 각 장비별 프로그램의 기능이 어떠해야 하는지는 충분히 이해할 수 있을 것이다. S(300), RS(400, UE(500)은 해당 프로그램을 실행할 수 있는 무선통신장치, 컴퓨팅 장치, 데이터 저장장치 등을 기본적으로 갖추어야 함은 물론이다. 이들 장치의 하드웨어 구성이나 본 발명에 의한 프로그램 실행 이외의 사항에 관한 작동방식은 이미 공지된 기술이고 본 발명의 아이디어와는 직접적인 관련이 없으므로 그에 관한 설명은 생략한다.

300: 소스 스테이션
400: 릴레이 스테이션
500: 사용자 단말기

Claims

무선통신 서비스 영역을 복수의 셀로 구분하고, 각 셀마다 하나의 소스 스테이션(S)과 복수 개의 릴레이스테이션(RS) 그리고 랜덤하게 분포되어 있는 복수 개의 사용자 단말기(UE)가 존재하며, 상기 소스스테이션(S)과 상기 릴레이스테이션(RS)들은 모두 N개(단, N은 2이상의 자연수)의 서브캐리어를 가지며, 상기 소스스테이션(S)은 상기 릴레이스테이션(RS)들을 시분할다중접속[
]방식으로 서비스하고, 각 릴레이스테이션(RS)들은 자신이 갖고 있는 N개의 서브캐리어를 사용하여 자신에게 할당된 사용자 단말기(UE)들에게 직교주파수다중분할접속(
) 방식으로 무선통신 서비스를 제공하는 다중 사용자 다운링크 릴레이 네트워크에서,
(1) 상기 소스 스테이션(S)이 상기 릴레이 스테이션(RS)들을 서비스 해주는 동안에, 모든 사용자 단말기(UE)들은 각각 매 타임 슬롯마다 자신이 겪게 되는 간섭량을 스캔하여 자신이 가장 적게 간섭을 받게 될 타임 슬롯을 선택하는 단계;
(2) 상기 사용자 단말기(UE)는 선택한 그 타임 슬롯에 자신을 담당하는 릴레이 스테이션(RS)에게 서비스를 요청하는 단계;
(3) 상기 복수 개의 릴레이 스테이션(RS)들은 각각 자신이 담당하는 사용자 단말기(UE)들에 대해 그 사용자 단말기(UE)가 요청한 타임 슬롯에서 서비스를 제공하는 단계;
(4) 상기 복수 개의 사용자 단말기(UE)들이 모두 다른 타임 슬롯을 선택하여도 간섭량에 있어서 더 이상 지금보다 나은 결과를 가져오지 못하는 상태인 나쉬 평형(Nash Equilibrium) 상태에 도달할 때까지 상기 단계 (1) 내지 상기 단계 (3)을 반복적으로(iteratively) 수행하는 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 변하는 사용자 요구 통신품질에 대한 만족도 개선방법.
제1항에 있어서, 상기 서비스를 요청한 사용자 단말기(UE)들은 다른 사용자 단말기(UE)가 자신과 같은 타임 슬롯을 선택하여 서비스를 요청함으로 인해 자신이 선택한 타임 슬롯이 최소 간섭을 일으키는 타임 슬롯이 아닌 것으로 판단되는 경우, 최소 간섭을 유발하는 타임 슬롯을 다시 선택하여 자신을 담당하는 릴레이 스테이션(RS)에게 서비스를 다시 요청하는 단계를 더 포함하는 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 변하는 사용자 요구 통신품질에 대한 만족도 개선방법.
제1항에 있어서, 상기 릴레이스테이션(RS)에서 상기 사용자 단말기(UE)로의 정보 전송량(RS->UE 전송률)이 상기 소스스테이션(S)에서 상기 릴레이스테이션(RS)으로의 정보 전송량(S->RS 전송률) 보다 크지 않으면, 해당 사용자 단말기(UE)는 타임 슬롯을 추가적으로 더 선택하여 자신을 담당하는 릴레이 스테이션(RS)에게 서비스를 요청하는 단계를 더 포함하는 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 변하는 사용자 요구 통신품질에 대한 만족도 개선방법.
제1항에 있어서, 상기 복수 개의 릴레이스테이션(RS) 각각은 자신이 서비스하고 있는 사용자 단말기(UE)들에 대하여 주파수를 할당하는 단계를 더 포함하는 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 변하는 사용자 요구 통신품질에 대한 만족도 개선방법.
제4항에 있어서, 상기 릴레이스테이션(RS)이 자신이 담당하는 2 이상의 사용자 단말기(UE)에게 상기 주파수를 할당함에 있어서, 각 사용자 단말기(UE)의 QoS 요구에 관한 히스토리를 참조하여 QoS의 변동(variation)이 미리 설정해둔 기준값보다 큰 사용자 단말기(UE)에 대해서는 제1 주파수를 할당하고, QoS의 변동(variation)이 상기 기준값보다 작은 사용자 단말기(UE)에 대해서는 상기 제1주파수보다 더 적은 제2 주파수를 할당하는 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 변하는 사용자 요구 통신품질에 대한 만족도 개선방법.
제4항에 있어서, 상기 릴레이스테이션(RS)이 자신이 담당하는 2 이상의 사용자 단말기(UE)에게 상기 주파수를 할당함에 있어서, 각 사용자 단말기(UE)의 QoS 요구에 관한 히스토리를 참조하여 가장 많은 QoS의 변동을 보여주는 사용자 단말기(
)에게 서브캐리어
을 모두 할당을 하여 시작하고, 자신이 담당하는 사용자 단말기(UE)가 추가될 때마다 그 사용자 단말기(UE)의 QoS 변동 정보를 바탕으로 하여 그 변동의 정도가 큰 순서로 등비수열로 서브캐리어를 할당하는 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 변하는 사용자 요구 통신품질에 대한 만족도 개선방법.
제6항에 있어서, 상기 등비수열로 서브캐리어를 할당할 때 적용되는 등비는 1/2인 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 변하는 사용자 요구 통신품질에 대한 만족도 개선방법.
제1항 내지 제7항 중 어느 하나에 있어서, 특정 사용자 단말기(UE)가 QoS 요구를 올리면, 그 특정 사용자 단말기(UE)에 대한 서비스를 담당하는 릴레이 스테이션(RS)은 자신이 서비스를 담당하는 사용자 단말기(UE)들 중에서 만족상태에 있는 사용자 단말기(UE)의 주파수 양보에 따른 주파수 공백화를 수행하는 단계를 더 포함하는 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 변하는 사용자 요구 통신품질에 대한 만족도 개선방법.
제8항에 있어서, 상기 주파수 공백화는, (a) 상기 릴레이 스테이션(RS)의 서비스에 대해 만족 상태에 있는 사용자 단말기(UE)가 주파수 공백화를 자신을 담당하는 릴레이 스테이션(RS)에게 요청하는 단계; (b) 주파수 공백화를 요청받은 릴레이 스테이션(RS)은 그 요청을 자신을 담당하는 소스 스테이션(S)에게 전달하여 그 소스 스테이션(S)이 해당 서브캐리어를 공백화(nulling) 하고, 그 주파수 공백화를 요청받은 상기 릴레이 스테이션(RS) 또한 상기 해당 서브캐리어를 공백화하는 처리를 하는 단계를 통해 달성되는 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 변하는 사용자 요구 통신품질에 대한 만족도 개선방법.
제9항에 있어서, 상기 단계 (a)에서 상기 만족 상태에 있는 사용자 단말기(UE)는 자기 자신이 만족 상태를 유지할 수 있는 한도 내에서 상기 주파수 공백화를 요청하는 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 변하는 사용자 요구 통신품질에 대한 만족도 개선방법.
제8항에 있어서, 상기 주파수 공백화는, (i) 상기 릴레이 스테이션(RS)의 서비스에 대해 불만족 상태에 있는 사용자 단말기(UE)가 자신에게 가장 간섭을 많이 주는 서브캐리어와 해당 타임 슬롯에 관한 정보를 자신을 담당하는 릴레이 스테이션(RS)에게 업로드해주는 단계; (ii) 그 릴레이 스테이션(RS)은 그 업로드 받은 정보를 자신을 담당하는 소스 스테이션(S)에게 업로드해 주어 그 소스 스테이션(S)이 그 업로드 받은 그 정보를 토대로 해당 서브캐리어를 공백화(nulling)하고, 그 주파수 공백화를 요청받은 상기 릴레이 스테이션(RS) 또한 상기 해당 서브캐리어를 공백화하는 처리를 하는 단계를 통해 달성되는 것을 특징으로 하는 다중 사용자 다운링크 릴레이 네트워크에서 변하는 사용자 요구 통신품질에 대한 만족도 개선방법.