논문 09-34-01-10 한국통신학회논문지 '09-01 Vol. 34 No. 1 OFDMA 시스템에서 Elastic 서비스를위한 Opportunistic 스케줄링기법 준회원권정안 *, 종신회원이장원 * Opportunistic Scheduling Schemes for Elastic Services in OFDMA Systems Jeong-Ahn Kwon* Associate Member, Jang-Won Lee* Lifelong Member 요 약 본논문에서는 OFDMA를이용하는시스템에서의 elastic 서비스를위한공평성을고려한 opportunistic 스케줄링기법에대하여연구한다. 본논문에서는각유저의만족도를유틸리티로정의한후네트워크유틸리티극대화기법을이용한다. 이러한유틸리티는각유저가이용하는서비스에따라서로다르게정의할수있으며 elastic 서비스의경우에는평균전송률이높을수록유저의만족도가높아지게된다. 이를반영하기위하여각유저의유틸리티를평균전송률에대한함수로정의한다. 또한각유저사이의공평한자원배분을위한조건을유저들의유틸리티를이용하여정의하고이를만족하는동시에각유저의유틸리티의합으로정의되는네트워크유틸리티를극대화하기위한 opportunistic 스케줄링기법을연구한다. 본논문에서는각각의공평성조건에대한 opportunistic 스케줄링문제를최적화문제로정의하고이를 dual 기법과 stochastic sub-gradient 기법으로풀어스케줄링기법을구현하도록한다. Key Words : OFDMA, Opportunistic scheduling, Network utility maximization, Fairness ABSTRACT In this paper, we provide opportunistic scheduling schemes for elastic services in OFDMA systems with fairness constraints for each user. We adopt the network utility maximization framework in which a utility function is defined for each user to represent its level of satisfaction to the service. Since we consider elastic services whose degree of satisfaction depends on its average data rate, we define the utility function of each user as a function of its average data rate. In addition, for fair resource allocation among users, we define fairness requirements of each user by using utility functions. We first formulate an optimization problem for each fairness requirement that aim at maximizing network utility, which is defined as the sum of utilities of users. We then develop an opportunistic scheduling scheme for each fairness requirement by solving the problem using a dual approach and a stochastic sub-gradient algorithm. 이논문은 2007 년도정부재원 ( 교육인적자원부학술연구조성사업비 ) 으로한국학술진흥재단의지원을받아연구되었음 (KRF-2007-31 3-D00522). * 연세대학교전기전자공학과통신망연구실 (pooheup@yonsei.ac.kr), (jangwon@yonsei.ac.kr) 논문번호 :KICS2008-09-410, 접수일자 :2008 년 9 월 19 일, 최종논문접수일자 :2008 년 11 월 25 일 76
논문 /OFDMA 시스템에서 Elastic 서비스를위한 Opportunistic 스케줄링기법 Ⅰ. 서론최근들어광대역무선통신시스템에대한다양한연구가진행되고있으며, 일부는이미상용화단계에이르렀다. 이러한시스템들의가장큰특징은무선망을통하여기존의유선망과비슷한수준의서비스를제공하는것에그목표를두고있다는점이다. 이를실현하기위한주요기술로서 OFDMA (Orthogonal Frequency Division Multiple Access) opportunistic 스케줄링이주목을받고있다. OFDMA는최근에각광받고있는다중접속기법으로서 3GPP LTE나 IEEE 802.16등에적용되고있다. 이는주어진대역폭을여러개의 sub-carrier 로분할하여데이터를전송하는방식으로서 sub-carrier들을각각다른유저에게자유롭게할당할수있다. 이를이용하면, 각유저의각 sub-carrier에서의채널상태에따라자원을할당할수있어이함께 opportunistic 스케줄링을적용한다면보다높은이득을얻을수있다. Opportunistic 스케줄링이란상대적으로좋은채널상태를갖는유저에게자원을할당해주는기법을말한다 [1]-[3]. 무선통신에서각유저가겪는채널상태는시간에따라변하는특징을가지고있다. 이를이용하여, 공유하고있는무선자원을현재의채널상태가상대적으로좋은유저에게할당해줌으로써보다더높은성능을얻을수있다. 하지만단순히채널상태가좋은유저에게자원을할당하는것은불공정한자원배분을야기할수있다. 예를들어기지국에가까이있는, 상대적으로채널상태가좋은유저에게많은자원이할당되고기지국에서멀리있는, 상대적으로채널상태가나쁜유저에게는적은양의자원이할당될수있다. 따라서여러유저에게자원이공평하게배분될수있도록만들어주어야하며이에최근여러연구에서효율적인자원할당뿐만아니라공평한자원할당도중요하게고려가되고있다. 본논문에서는 OFDMA 시스템에서효율성과공평성을고려한 opportunistic 스케줄링을통한자원할당기법을네트워크유틸리티최대화기법을이용하여연구할것이다. 유틸리티란각유저가얻는만족도를뜻하는것으로일반적으로이는유저가할당받은자원에대한함수로표현된다. 유저가할당받은자원의양이많을수록만족도가증가하겠지만, 정비례관계에있는것은아니기때문에이를 유틸리티함수를이용하여나타낸다. 본기법의목적은주어진조건하에서각유저의유틸리티의합으로정의되는시스템유틸리티를최대화하는것이다. 이러한유틸리티공평성을위한조건은유저가이용하는서비스에따라서로다를수있다. 특히대용량의파일등을전송하는 elastic 서비스의경우시스템을통하여얻는평균전송률이높을수록유저의만족도가높게된다. 따라서본논문에서는각유저의유틸리티를각유저가얻는평균전송률에대한함수로정의한다. 이경우, 각유저는자원을불규칙적으로할당받더라도일정량이상의평균전송률을보장받으면된다. 또한각유저의공평성조건을이러한유틸리티를이용하여정의한다. 본논문에서는 elastic 서비스의특징을고려하여각유저가받아야할최소한의유틸리티를각유저의공평성조건으로정의한다. 이는각유저가자신이필요로하는양의유틸리티를얻을수있기때문에보다정확히유저의만족도를충족시켜줄수있다. 하지만, 이경우시스템이지원할수없는공평성조건이발생할수있어상위계층에서의 admission control이필요하다. 현재 OFDMA 시스템에서자원할당에관한다양한연구가되어있다 [4]-[8]. 각시간슬롯에서전송률을최대화하는기법들은 [4]-[6] 에서연구되었다. 이들은각유저의공평성을고려하여스케줄링을하였지만, 시간상에서의스케줄링이아닌하나의시간슬롯에서의자원할당만을고려하였기때문에상대적으로비효율적인자원할당이이루어진다. 또한전송률의유틸리티측면이아닌전송률자체를증가시키는것에대하여연구하여유저의만족도를효과적으로반영하지못한다. 또한 [7] 은각유저가얻는전송률에대한유틸리티를최대화하는방안에대하여연구하였지만, 공평성에대한조건을고려하지않고있기때문에불공평한자원할당이될수가있다. 마지막으로 [8] 은여러시스템에서많이쓰이는 proportional fair (PF) 스케줄링을 OFDMA를사용하는시스템에적용하는방안에대하여논하고있다. 이는손쉽게구현가능한효율적인알고리즘이지만, 각유저의서비스에따른공평성조건을변경할수없기때문에보다융통성있는스케줄링기법이필요하다. 따라서본논문에서는각유저의공평성에대한조건을고려한 opportunistic 스케줄링기법에대한연구를할것이다. 본논문은다음과같이구성된다. Ⅱ장에서는본 77
한국통신학회논문지 '09-01 Vol. 34 No. 1 논문에서고려할시스템모델에대하여설명한다. Ⅲ장에서는스케줄링기법을설명하며 Ⅳ장에서는이에대한시뮬레이션결과를보여준다. 마지막으로 Ⅴ장에서는본논문에대한결론과함께앞으로진행하여야할부분에대하여정리하도록한다. Ⅱ. 시스템모델본논문에서는 OFDMA를사용하는셀룰러시스템에서하향링크만을고려하도록하며하나의셀만이존재하는환경을가정한다. 또한시스템의시간이슬롯화되어있어각시간슬롯마다기지국이각유저에게 sub-carrier파워를스케줄해주는시스템을고려한다. 하나의셀안에는 N명의유저가존재하며 M개의 sub-carrier가존재한다. 또한모든유저는언제나전송하여야할데이터들을가지고있다고가정한다. 무선시스템에서유저가얻게되는전송률은각유저의채널상태밀접한관련이있다. 특히 OFDMA 시스템에서는여러개의 sub-carrier가존재하며각 sub-carrier마다채널상태가서로다르다. 이러한각유저의각 sub-carrier에서의채널상태는시간에따라변하며이는 stochastic process로모델링할수있다. 이러한채널상태는분석의편의를위하여 stationary 특성을갖으며하나의시간슬롯에서는변하지않는다고가정한다. 따라서하나의시간슬롯에서각 sub-carrier마다각유저가갖는채널상태는해당유저가가질수있는몇가지채널상태단계중하나가될것이다. 하나의시간슬롯에서셀내의모든유저의채널상태의조합을하나의시스템채널상태 s라정의하며이런시스템채널상태의집합을 ={1, 2,, S} 로나타내도록한다. 1) 따라서시스템채널상태로써각유저의각 sub-carrier에서의채널상태를표현할수가있다. 또한시스템이시스템채널상태 s에있을확률을 라한다. 논문 [9] [10] 의연구결과에따르면 sub-carrier 할당후, power control을수행해주는것은수행하지않는것과큰성능차이를보이지않는다. 이는 sub-carrier 할당과정에서이미한번의최적화가이루어지기때문이다. 이를바탕으로본논문에서는기지국에서데이터의전송시사용되는최대파워 1) 이러한가정이가능한점은채널상태는연속적인특성을지니지만, 실제시스템에서유저의채널상태는 quantization을통하여정해진몇단계의 level set 중하나의 level로대응되기때문이다. 는고정되어있고기지국이사용할수있는최대파워를각 sub-carrier에동일하게할당한다고가정한다. 따라서본논문에서는각유저의 sub-carrier 의채널상태에따른 sub-carrier 할당만을고려할것이다. 본논문에서다루는시스템은 OFDMA 환경에서하나의셀만을고려하기때문에각유저가겪게되는채널상태는간섭이존재하지않는다. 따라서단지수신한신호의파워노이즈파워의비즉, SNR (Signal to Noise Ratio) 에의해채널상태를나타낼수있다. 는기지국에서사용할수있는전체파워라하고, 는시스템채널상태 s하에서유저 i가 sub-carrier j를이용할경우의채널 gain, 는데이터의수신과정에서발생하는노이즈의파워로정의한다. 이경우채널상태 s하에서유저 i에게 sub-carrier j가할당되었을경우의 SNR, 는 (2.1) 이다. 본논문에서는각유저가각 sub-carrier에서의 SNR을측정한후기지국에전송을해주어기지국이알고있다고가정을한다. 또한전송률을나타내주는 SNR에대한함수를 g라하면, 채널상태 s하에서유저 i에게 sub-carrier j가할당되었을경우의전송률 는 (2.2) 로나타내어진다. 본논문에서는전송파워가고정되어있기때문에, 전송률은 SNR 즉, 채널상태만을변수로갖는함수로표현되며이는기지국에서쉽게구할수있다. 다음으로는각 sub-carrier 할당을나타내주는변수 를정의하도록한다. 이는채널상태 s에서유저 i에게 sub-carrier j가할당될확률을의미한다. 따라서본값은 0에서 1 사이의실수를갖게된다. 이에따라시스템채널상태 s에서유저 i가얻는평균전송률은 (2.3) 이며, 유저 i 가얻게되는평균전송률은 (2.4) 78
논문 /OFDMA 시스템에서 Elastic 서비스를위한 Opportunistic 스케줄링기법 로나타낼수있다. 또한하나의 sub-carrier가각유저에게할당될수있는확률의합은 1보다작아야하므로 (2.5) 가각 j s에대하여성립하여야한다. 마지막으로, 본논문에서각유저 i의만족도즉, 유틸리티 ( ) 는각유저가할당받은자원을통하여얻게되는평균전송률에따른함수라정의하며이는유저의평균전송률에대하여 strictly concave 함수라가정한다. 따라서유저 i의평균전송률에대한유틸리티는 (2.6) 로나타내진다. 또한각유저 i의공평성조건인할당받아야할최소한의유틸리티를 라고정의하고이는 (2.7) 의조건을만족시켜주어야한다. 이러한유틸리티는각유저의만족도를반영하기위하여도입된것으로서, 일반적으로유저의만족도는할당받은전송률이증가할수록전송률의증가량에비하여만족도의증가량이감소한다. 따라서 (2.8) 같은 concave 형태의유틸리티함수를많이사용한다. 특히유틸리티함수를식 (2.8) 의 log 함수를사용하고, 각유저의공평성조건을별도로설정하지않은상태에서 ( 즉, 식 (2.7) 의 값이 0인경우 ) 시스템유틸리티를최대화시키는스케줄링기법을 PF 스케줄링기법이라한다 [11]. 따라서본논문에서제안하는스케줄링기법은 PF 스케줄링기법을포함한보다일반적인기법이다. Ⅲ. Opportunistic 스케줄링기법본장에서는앞에서말한각유저가할당받아야할최소한의유틸리티가정의되어있는경우의스케줄링기법을논하도록한다. 이경우최적화문제는다음과같다. (3.1) 이는각유저의유틸리티가유저가얻은평균전송률에대한함수로정의되고이의최소값을공평성요구로갖는시스템유틸리티를최대화하는문제가된다. 유틸리티함수는유저의평균전송률에대하여 strictly concave 함수라가정하였기때문에만약시스템채널상태확률 를알수있다면, 본문제는 deterministic convex 최적화문제로서쉽게풀수있다. 하지만실제시스템에서는이값을알기가어렵기때문에본논문에서는채널상태확률 에대한정보가없는상태에서문제를풀수있는기법을개발할것이다. 이를위하여유틸리티함수내에존재하는시스템채널상태확률 를외부로나오게하는과정이필요하며이를위하여유저의평균전송률 를정의하여위의문제를다음과같이재정의한다. (3.2) 하지만아직 가문제상에존재하며이를해결하기위하여위의문제를 dual 문제를통하여풀도록한다. 따라서먼저위문제에대한 Lagrange 함수를구하면다음과같다. (3.3) 여기에서, 는각각 의벡터이며, 는 dual 변수 의벡터이다. 따라서 dual 79
한국통신학회논문지 '09-01 Vol. 34 No. 1 문제는 (3.4) 으로정의되고, 이때 (3.5) 이며여기에서, 각항이 i에대한합으로이루어져있으며이에따라각 i에대하여분리할수있다. 마찬가지로 의경우식 (3.10) 은각 j에대하여분리할수있다. 따라서식 (3.9) 식 (3.10) 의해는 (3.11) (3.6) (3.12) 로정의된다. 식 (3.4) 를풀기위해서는그에앞서식 (3.5) 를풀어야한다. 이때각각 에관한항과 에관한항을분리하여 (3.7) 이라정의하면식 (3.3) 은 (3.8) 이라할수있다. 따라서함수 L의최대값은고정된 에대하여각각 L 1 과 L 2 의최대값을구함으로써구할수있다. 이경우 L 1 과 L 2 를최대화하는 는 (3.9) (3.10) 으로구할수가있다. 식 (3.9) 의 를구하기위하여 를살펴보면이는 를통하여구할수있으며그해는 (3.13) (3.14) 가된다. 만약식 (3.14) 에서둘혹은그이상의유저가같은 의최대값을갖는다면해당유저중한유저만 가 1이고나머지는 0이되어야하며, 이는임의로선택하여도관계없다. 이제 dual 문제를풀도록한다. 식 (3.5) 의 dual 문제 는 를모르는 stochastic convex optimization problem이므로직접적으로는풀기가어렵다. 따라서본논문에서는 stochastic sub-gradient method를이용하도록한다 [12],[13]. 이는자원할당이행해지는매시간슬롯 t에서다음과같은 iteration process를이용한다. (3.15) (3.16) 여기에서 이고 는벡터 의원소로써본벡터들이 의 stochastic sub-gradient 이며이는다음과같이구할수있다. 그리고 (3.17). (3.18) 80
논문 /OFDMA 시스템에서 Elastic 서비스를위한 Opportunistic 스케줄링기법 여기에서 는시간슬롯 t에서의채널상태 s를의미하며 는시간슬롯 t에서의 값이고,, 는시간슬롯 t에서식 (3.13) 과 (3.14) 를통하여구한해이다. 본문제는 convex 문제이기때문에상기의 dual 문제를통해구한최적의 는 primal 문제의최적해로수렴한다. 이를이용하여실제통신시스템에서스케줄링을할경우에는매시간슬롯에서다음과같은과정이반복된다 Utility 5 4 3 2 1 0-1 -2-3 -4-5 Fairness requirement C i Proposed scheme Proportional fair scheduling Static sub-carrier allocation Data rate maximization 1 2 3 4 5 6 7 8 9 10 User i. 기지국은식 (3.14) 에따라각 sub-carrier에서 가가장큰유저에게해당 sub-carrier를할당한다. ii. 각유저는 i에서할당받은자원을이용하여통신한다. iii. 기지국은 i에서의 식 (3.13) 을통해구한 값과식 (3.15) 및 (3.16) 을이용하여다음시간슬롯에서의각유저의 dual. variable 값을재조정한다. Ⅳ. 성능분석시뮬레이션은 10명의유저가 128개의 sub-carrier 를이용하는경우에대하여수행하였고, 각유저의유틸리티함수를각유저가얻은전송률에대하여일반적으로많이사용하는 log 함수를이용하여 (4.1) 로정의하였다. 신호의세기는거리의네제곱에반비례하도록만들어주었으며시간에따라변하는채널은 Rayleigh 분포표준편차가 8dB인 log-normal 분포를이용하여모델링하였다. 제안한알고리즘의성능을알아보기위하여, 본기법을통해구현한 PF 스케줄링기법과각유저에게동일한양의 sub-carrier를 static하게할당 (Static sub-carrier allocation) 한기법, 각유저의만족도인유틸리티공평성조건을고려하지않고각시간슬롯마다데이터전송률이최대화되도록하는스케줄링 (Data rate maximization) 기법과의비교를그림 1을통해나타내었다. 유저는기지국에서부터가까운순서로배열을하였다. 그림 1에서보듯이제안된기법은모든유저의공평성조건을만족시키고있음을알수가있다. 이 그림 1. 할당받아야할최소한의유틸리티조건에따른스케줄링기법에서각유저의유틸리티 표 1. 할당받아야할최소한의유틸리티조건에따른스케줄링기법의유틸리티및전송률비교 Total Utility Average data rate per Hz (bps/hz) Proposed scheme 10.30 0.220 PF scheduling 13.10 0.560 Static allocation 3.96 0.246 Data rate maximization -9.83 0.838 에반해 PF 스케줄링기법과 static sub-carrier allocation 기법, data rate maximization 기법은기지국에서가까운유저의만족도는상당히높지만기지국에서먼유저의만족도는아주낮아공평성조건을만족시키지못함을알수가있다. 또한표 1을보면제안한기법이 static sub-carrier allocation 기법과 data rate maximization 기법에비하여시스템이주파수대역폭 1Hz당얻는평균전송률은더낮았지만시스템유틸리티는더높음을알수있다. 이는본논문의목적이시스템유틸리티를최대화시키기위한것이고, 유틸리티전송률은정비례하지않기때문에발생한현상이다. 이때, 보다높은전송률을얻고자한다면유틸리티함수를식 (4.1) 에비하여선형에가까운것으로바꾸어줌으로써그목적을이룰수있다. 즉, 유틸리티함수의조절을통하여시스템설계자의목적에 ( 혹은사용자의목적에 ) 부합하는스케줄링을할수있다. 마지막으로 PF 스케줄링의경우각유저의유틸리티함수및전송률이보다높아짐을알수있다. PF 스케줄링은모든유저의공평성조건 값이 0 81
한국통신학회논문지 '09-01 Vol. 34 No. 1 인상황에서의제안한알고리즘을적용한것이므로, 본논문에서제안한알고리즘을통하여얻을수있는최대의시스템유틸리티를의미한다. 즉, 각유저의공평성조건을조절하여보다높은시스템의효율을얻을수있다는것을의미하며, 따라서이를통해시스템효율과공평성간의 tradeoff를조절할수있다. Ⅴ. 결론본논문에서는 OFDMA 시스템에서 elastic 서비스에대하여각유저가보장받는최소한의유틸리티값이존재하는경우 opportunistic 스케줄링기법에대한연구를수행하였으며, 그성능을시뮬레이션을통하여검증하였다. 앞으로는이외에도또다른종류의서비스에대한유틸리티를정의하고, 이에대한스케줄링기법을연구할예정이다. 참고문헌 [1] X. Liu, E. Chong, and N. Shroff, A framework for opportunistic scheduling in wireless networks, Computer Networks, Vol.41, pp.451-474, Mar. 2003. [2] X. Liu, E. Chong, and N. Shroff Opportunistic transmission scheduling with resource-sharing constraints in wireless networks, IEEE Journal on Selected Areas in Communications, Vol. 19, no10, pp.2053-2064, Oct. 2001. [3] J.-W. Lee, R. R. Mazumdar, and N. B. Shroff, Opportunistic power scheduling for dynamic multi-server wireless systems, IEEE Transactions on Wireless Communications, Vol.5, No.6, pp.1506-1515, Jun. 2006. [4] Y. J. Zhang and K. B. Letaief, Multiuser adaptive subcarrier-and-bit allocation with adaptive cell selection for OFDM systems, IEEE Transactions on Wireless Communications, Vol.3, No.5, Sept. 2004. [5] W. Xu, C. Zhao, P. Zhou, and Y. Yang, Efficient adaptive resource allocation for multiuser OFDM systems with minimum rate constraints, IEEE ICC, pp.5126-5131, Jun. 2007. [6] H. Yin and H. Liu, An Efficient multiuser loading algorithm for OFDM-based broadband wireless systems, IEEE Globecom, pp.103-107, Nov. 2000. [7] J. Huang, V. Subramanian, R. Agrawal, and R. Berry, Downlink scheduling and resource allocation for OFDM systems, CISS, pp.1272-1279, Mar. 2006. [8] Z. Shen, J.G. Andrews, B.L. Evans, Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints, IEEE Transactions on Wireless Communications, vol 4, np 6, pp.2726-2737, Nov. 2005. [9] J. Jang and K. B. Lee, Transmit power adaptation for multiuser OFDM systems, IEEE Journal on Selected Areas in Communications, Vol.21, No.2, pp.171-178, Feb. 2003. [10] Y. J. Zhang, and K. B. Letaief, Multiuser adaptive subcarrier-and-bit allocation with adaptive cell selection for OFDM systems, IEEE Transactions on Wireless Communication, Vol.3, No.5, pp.1566-1575, Sept. 2004. [11] F. Kelly, A. Maulloo and D. Tan, Rate control in communication networks: shadow prices, proportional fairness and stability., Journal of the Operational Research Society, vol 49, no 3, pp.237-252, Mar. 1998 [12] P. Kall and S. W. Wallace, Stochastic programming, Wiley, 1994. [13] Y. Ermoliev, Stochastic quasigradient methods and their application to system optimization, Stochastics, Vol.9, pp.1 36, 1983. 권정안 (Jeong-Ahn Kwon) 준회원 2006년 2월연세대학교전기전자공학부졸업 2008년 2월연세대학교전기전자공학부석사 2008년 3월 ~ 현재연세대학교전기전자공학부박사과정 < 관심분야 > 통신네트워크프로토콜, 네트워크자원할당, 다계층최적화, cognitive radio 82
논문 /OFDMA 시스템에서 Elastic 서비스를위한 Opportunistic 스케줄링기법 이장원 (Jang-Won Lee) 종신회원 1994년 2월연세대학교전자공학과졸업 1996년 2월한국과학기술원전기및전자공학과석사 2004년 8월미국 Purdue Univ. Electrical & Computer Eng. 박사 2004년 9월 ~2005년 8월 Princeton Univ. Post Doc. 2005년 9월 ~ 현재연세대학교전기전자공학부조교수 < 관심분야 > 통신네트워크프로토콜, 네트워크자원할당, 다계층최적화 83