(72) 발명자 이성원 경기도성남시분당구서현동 91 한양아파트 327 동 807 호 최영준 서울특별시관악구봉천 6 동 호 - 2 -

Size: px

Start display at page:

Download "(72) 발명자 이성원 경기도성남시분당구서현동 91 한양아파트 327 동 807 호 최영준 서울특별시관악구봉천 6 동 호 - 2 -"

윤영 호
5 years ago
Views:

1 (51) Int. Cl. (19) 대한민국특허청 (KR) (12) 등록특허공보 (B1) H04B 7/26 ( ) (21) 출원번호 (22) 출원일자 2002 년 03 월 30 일 심사청구일자 2007 년 03 월 21 일 (65) 공개번호 (43) 공개일자 2003 년 10 월 08 일 (56) 선행기술조사문헌 KR A KR A KR A US A (45) 공고일자 2009년01월07일 (11) 등록번호 (24) 등록일자 2008년12월23일 (73) 특허권자 삼성전자주식회사 경기도수원시영통구매탄동 416 (72) 발명자 문상준 서울특별시동작구상도 4 동약수아파트 박세웅 서울특별시강남구청담 2 동삼환아파트 101 동 805 호 ( 뒷면에계속 ) (74) 대리인 이건주 전체청구항수 : 총 6 항심사관 : 정구웅 (54) 무선통신시스템에서사용자만족도에따른하향링크스케줄링방법 (57) 요약 본발명은무선셀룰러데이터시스템의하향링크에서데이터패킷의전송을스케줄링하는방법에관한것으로서, 기지국과무선으로통신을연결하고있는복수의사용자들에게원하는크기의데이터패킷을전송하기위하여시분할다중화를지원하는무선통신시스템의하향링크스케줄링방법에있어서, 상기복수의사용자별로서로다른만족도를설정하는과정과, 매스케줄링주기마다상기설정된만족도를이용하여상기복수의사용자들중전체사용자의만족도합을최대로하는사용자를선택하는과정과, 상기선택된사용자에게데이터전송을위한타임슬롯을할당하는과정을포함한다. 이로써본발명은사용자의서비스지연시간을최소화하여실제만족도를향상시키며기지국의데이터처리율을향상시킨다. 대표도 - 도 8-1 -

2 (72) 발명자 이성원 경기도성남시분당구서현동 91 한양아파트 327 동 807 호 최영준 서울특별시관악구봉천 6 동 호 - 2 -

3 특허청구의범위청구항 1 기지국과무선으로통신을연결하고있는복수의사용자들에게원하는크기의데이터패킷을전송하기위하여시분할다중화를지원하는무선통신시스템의하향링크스케줄링방법에있어서, 상기복수의사용자별로서로다른만족도를설정하는과정과, 매스케줄링주기마다상기설정된만족도를이용하여상기복수의사용자들중전체사용자의만족도합을최대로하는사용자를선택하는과정과, 상기선택된사용자에게데이터전송을위한타임슬롯을할당하는과정을포함하는것을특징으로하는하향링크스케줄링방법. 청구항 2 제 1 항에있어서, 상기만족도는사용자의지연시간에따른함수인것을특징으로하는하향링크스케줄링방법. 청구항 3 제 2 항에있어서, 상기사용자의지연시간은, 데이터전송을위한슬롯이할당되기를기다리는스케줄링지연시간과데이터패킷을할당된슬롯으로전송하기위해처리하는처리지연시간의합인것을특징으로하는하향링크스케줄링방법. 청구항 4 제 2 항에있어서, 상기사용자를선택하는과정은, 하기의 < 수학식 12> 의결과를최대로하는사용자를선택하는것을특징으로하는하향링크스케줄링방법. 수학식 12 여기서, 상기는스케줄링시점 t 에서사용자 j 를선택한경우전체사용자의만족도합이고, 는사용 자 j 의만족도이고, 는사용자 j 의데이터전송을위한슬롯이할당되기를기다리는스케줄링지연시간이고, 는사용자 j 의데이터패킷을할당된슬롯으로전송하기위해처리하는처리지연시간이고, N 은전체사용자의수임. 청구항 5 기지국과무선으로통신을연결하고있는복수의사용자들에게원하는크기의데이터패킷을전송하기위하여 시분할다중화를지원하는무선통신시스템의하향링크스케줄링방법에있어서, 상기복수의사용자별로사용자지연시간에따라정해지는서로다른만족도를설정하는과정과, 매스케줄링주기마다상기설정된만족도를이용하여상기복수의사용자들각각에대하여한사용자의만족도 이득과다른모든사용자의처리지연시간이증가함으로써발생하는만족도손실을이용하여사용자를선택하는 과정과, 상기선택된사용자에게데이터전송을위한타임슬롯을할당하는과정을포함하는것을특징으로하는하향링 크스케줄링방법. 청구항 6 제 5 항에있어서, 상기사용자를선택하는과정은, 하기의 < 수학식 13> 의결과를최대로하는사용자를선택하 는것을특징으로하는하향링크스케줄링방법

4 수학식 13 여기서, 상기는스케줄링시점 t 에서사용자 j 를선택한경우전체사용자의만족도합이고, 는사용 자 j 의만족도이고, 는사용자 j 의데이터전송을위한슬롯이할당되기를기다리는스케줄링지연시간이고, 는사용자 j 의데이터패킷을할당된슬롯으로전송하기위해처리하는처리지연시간이고, N 은전체사용자의수임. 명세서 발명의상세한설명 발명의목적 <16> <17> <18> <19> <20> <21> <22> <23> 발명이속하는기술및그분야의종래기술본발명은무선셀룰러 (Wireless Cellular) 데이터시스템에관한것으로서, 특히하향링크에서데이터패킷의전송을스케줄링하는방법에관한것이다. 일반적으로 CDMA(Code Division Multiple Access)2000, WCDMA/UMTS(Wideband Code Division Multiple Access/Universal Mobile Telecommunications System), GPRS(General Packet Radio System) 및 CDMA2000 1xEV-DO(Evolution Data Only) 와같은무선통신시스템은제3세대 (3rd Generation) 무선통신을수행하는시스템이다. 이러한제3세대무선통신시스템은음성서비스나저속의데이터서비스만을지원하던전형적인제2세대무선통신시스템과는달리, 음성서비스뿐만아니라고속의패킷데이터서비스 (high speed packet data service) 를지원한다. 무선통신시스템에서복수의사용자에게데이터패킷을전송하기위해서코드분할다중화 (Code Division Multiplex: CDM) 또는시간분할다중화 (Time Division Multiplex: TDM) 방식을사용할수있으며두방식을함께사용할수도있다. 무선통신시스템에서음성서비스를하는경우사용자에게하나의코드또는타임슬롯을할당하면되지만데이터서비스는사용자마다서비스하고자하는패킷의크기에따라필요로하는타임슬롯의개수가다르며전송률또한가변적이다. 따라서데이터서비스에서자원을효율적으로할당하는것은매우중요한문제가된다. 도 1은무선통신시스템에서코드분할다중화와시간분할다중화를설명하는도면이다. 상기도 1의 ( 가 ) 에도시한바와같이, 코드분할다중화는각사용자에게코드를할당하여동시에여러명을서비스할수있다. 그러나코드간의관계가완전한독립을유지하지못하면간섭이생기고전송하려는패킷의크기에따라코드를유연하게할당할수없는단점을갖고있다. 반면도 1의 ( 나 ) 에도시한시간분할다중화는하나의타임슬롯을단지한명의할당된사용자만이사용할수있지만패킷크기가크면타임슬롯을많이주면되므로패킷크기에유연하고코드분할에비해간섭이없다는장점을갖고있다. 전송의연속성에큰영향을받지않는데이터서비스에서는시간분할방식이보다효율적인것으로알려져있다. 이미언급한바와같이시간분할에서는하나의타임슬롯을한명의할당된사용자만이사용할수있기때문에기지국에복수의단말기들이연결되어있는경우매타임슬롯을사용할사용자를선택하는것은데이터전송의효율성을높이는데매우중요한작업이다. 이러한작업은스케줄링 (Schedulling) 이라고불린다. 무선통신시스템은단말기가기지국에데이터를전송하는상향링크 (uplink) 와기지국이단말기에게데이터를전송하는하향링크 (downlink) 를가진다. 상향링크와하향링크는코드분할다중화방식에따라각기다른코드를사용하여구분되는데, 데이터서비스에서는상향링크보다는하향링크를통해전송되는데이터패킷의양이월등하게많은경우가대부분이다. 따라서하향링크에서의스케줄링을효율화하기위한여러가지기술들이연구되고있다. 알려진스케줄링기법의일예로서, F. Kelly, A. Maulloo and D. Tan, "Charging and rate control for - 4 -

5 elastic traffic", European Transactions on Telecommunications, Vol 8, pp 33-37, 1997 은비례공평성 (Proportional fairness) 을기준으로하는스케줄링기법을개시한것으로서이는고속데이터시스템 (Highspeed Data Rate: HDR) 에적용되고있다. 만약어떤사용자의데이터처리율 (throughput) 이특정스케줄링알고리즘을사용할때보다 x% 증가한다고할때이로인해다른모든사용자들이겪게될데이터처리율의감소가 x% 보다크게된다고할때, 상기특정스케줄링알고리즘은비례공평성 (Proportional fairness) 기준으로사용된다고할수있으며, 이러한경우하기의 < 수학식 1> 이만족되도록하는스케줄링이수행된다. 수학식 1 <24> <25> 여기서, i 는기지국과데이터통신을연결하고있는사용자들의집합 S 에서사용자를구분하는식별자이며, 상 기은비례공평성기준에따라각사용자에게주어진전송률이고은임의의다른스케줄링기법을사용할때각사용자들의가능한전송률이다. 이스케줄링기법에서는단지사용자의전송률만을고려하여스케줄링을수행한다. 그러나이는각사용자의서비스등급및트래픽의특성에따른서비스의우선도를고려하고있지않다는문제가있다. <26> 알려진스케줄링기법의다른예로서, A. Jalali, R. Padovani and R. Pankaj, "Data Throughput of CDMA-HDR a High Efficiency High Data Rate Personal Communication Wireless System", IEEE VTC 2000 은코드분할 다중화기반의데이터전용시스템에서이용되는스케줄링알고리즘을개시한다. 어떤임의의시간 t( 여기서 t 는슬롯인덱스 ) 에사용자 i 에의해서기지국으로요구된전송률을 라고하고사용자 i 의평균적인전송률 을이라고하면이스케줄링알고리즘은다음과같은조건을고려한다. <27> <28> 1) 어떤스케줄링시점 t 에서전송할데이터가있는모든사용자들중 / 값이가장큰사용자를선 택하여슬롯이할당된다. 값이같은사용자들이존재하면이들중임의의사용자가선택된다. 2) 슬롯이할당되면사용자 i 의평균전송률는하기의 < 수학식 2> 와같이갱신된다. 수학식 2 <29> <30> 여기서상기은가중치를이용하여얻은평균전송률이다. 즉, 가클수록과거의전송률이 높은비율로반영되고가작을수록현재의전송률이높은비율로반영된다. 또한상기값을현재슬롯을할당받은사용자에대해서는현재의요구된전송률로하고나머지사용자에대해서는 0으로하면, 전송할데이터가없는사용자들에대해서도평균전송률을계산할수있다. 그러나이러한스케줄링은단순히과거의전송률에기반한평균전송률을이용하며채널상태의변화에적응하고있지않기때문에사용자의이동성에대해취약하다는단점을보이게된다. <31> <32> 알려진스케줄링기법의또다른예로서, Xin Liu, Ediwin K.P.Chong and Ness B. Shroff, "Transmission Scheduling for Efficient Wireless Utilization", IEEE INFOCOM 2001 은, 각사용자측면에서만족도함수 (Utility function) 를고려한다. 앞서설명한스케줄링기법들에서동일한만족도함수를사용하고있는것과는달리이스케줄링기법에서는사용자마다사용자의채널상태, 즉신호대잡음비 (Signal to Noise Ratio: SNR) 에따라각기다른만족도함수를설정할수있다. 즉각사용자에대해서전력잡음의비 (SNR) 에따라사용자만족도함수를각기다르게설정하고모든사용자의만족도함수의합이최대가되도록스케줄링한다. 이스케줄링기법은각사용자의만족도함수를다르게설정하고있기는하지만이는단지사용자의채널상태만을고려한것이므로, 실제사용자의만족도에큰영향을미치는데이터패킷의길이나지연시간등을고려하고있지않다는문제점이있었다

6 <33> <34> <35> <36> <37> <38> <39> <40> 발명이이루고자하는기술적과제따라서상기한바와같이동작되는종래기술의문제점을해결하기위하여창안된본발명의목적은, 무선데이터통신시스템에서데이터패킷을스케줄링하는방법을제공하는것이다. 본발명의다른목적은, 데이터패킷의길이를고려하여사용자만족도를설정하는방법을제공하는것이다. 본발명의다른목적은, 지연시간을고려하여사용자만족도를설정하는방법을제공하는것이다. 본발명의또다른목적은, 사용자마다고유하게설정된만족도에따라데이터패킷을스케줄링하는방법을제공하는것이다. 상기한바와같은목적을달성하기위하여창안된본발명의실시예는, 기지국과무선으로통신을연결하고있는복수의사용자들에게원하는크기의데이터패킷을전송하기위하여시분할다중화를지원하는무선통신시스템의하향링크스케줄링방법에있어서, 상기복수의사용자별로서로다른만족도를설정하는과정과, 매스케줄링주기마다상기설정된만족도를이용하여상기복수의사용자들중전체사용자의만족도합을최대로하는사용자를선택하는과정과, 상기선택된사용자에게데이터전송을위한타임슬롯을할당하는과정을포함한다. <41> <42> <43> <44> <45> <46> <47> 발명의구성및작용이하첨부된도면을참조하여본발명의바람직한실시예에대한동작원리를상세히설명한다. 하기에서본발명을설명함에있어관련된공지기능또는구성에대한구체적인설명이본발명의요지를불필요하게흐릴수있다고판단되는경우에는그상세한설명을생략할것이다. 그리고후술되는용어들은본발명에서의기능을고려하여정의된용어들로서이는사용자, 운용자의의도또는관례등에따라달라질수있다. 그러므로그정의는본명세서전반에걸친내용을토대로내려져야할것이다. 후술되는본발명은무선통신시스템에서하향링크를통한데이터패킷의전송을효율적으로스케줄링하기위한것이다. 보다구체적으로본발명은기지국의스케줄러에의한스케줄링및그에따른무선트래픽채널의할당에관계된다. 이러한본발명은공유매체의시간분할다중화 (Time Division Multiplex: TDM) 방식에기반한무선통신시스템을구성하는기지국의스케줄러에의하여수행된다. 도 2는본발명이적용되는무선통신네트워크모델을보여주는도면이다. 도시된바와같이전체서비스영역은셀 (Cell) 이라불리는복수개의소규모서비스영역들 1로분할되며각셀은무선통신을수행하는기지국 2에의하여서비스된다. 도 3은도 2에도시된무선통신네트워크의시스템구성을보여주는도면이다. 상기도 3을참조하면, 무선통신시스템은가입자단말기들 (Mobile Stations: MSs) 11,12와, 상기단말기들 11,12와각각무선으로접속되고이들과무선채널을통해통신하는기지국들 (Base Transceiver Subsystems: BTSs) 20,30과, 상기기지국들 20,30과접속되어통신하는기지국제어기 (Base Station Controllers: BSC) 40 을포함한다. 상기기지국제어기 40은이동교환국 (Mobile Switching Center: MSC) 50에접속되고, 또한게이트웨이 (Gateway: GW) 60에접속된다. 상기이동교환국 50은공중교환전화네트워크 (Public Switched Telephone Network: PSTN) 등의회선네트워크 (Circuit Network) 에접속되고, 상기게이트웨이 60은인터넷 (Internet)/ 공중교환데이터네트워크 (PSDN: Public Switched Data Network) 등의패킷교환네트워크 (Packet Switched Network) 에접속된다. 상기단말기들 11,12 는상기기지국제어기 40의제어하에상기이동교환국 50 또는상기게이트웨이 60으로접속된다. 상기도 3에서도시된구조는무선통신시스템의구조를일반화하여표시한것으로, 그구성요소들의명칭은무선통신시스템이어떠한시스템 ( 예 : IS-2000, WCDMA, UMTS, CDMA2000 1xEV-DO, GPRS, 1xEV-DV 등 ) 인지에따라서달라질수도있을것이다. 예를들어, 상기게이트웨이 60은논리적인명칭으로서, 패킷데이터서비스노드 (Packet Data Service Node: PDSN), 액세스게이트웨이 (Access Gateway: AG), 미디어게이트웨이 (Media Gateway) 등의다른이름으로불릴수있다. 다른예로서, 상기게이트웨이 60과이동교환국 50은동일한시스 - 6 -

7 템으로통합될수도있다. <48> <49> <50> <51> <52> <53> <54> <55> <56> <57> 상기와같이구성되는무선통신시스템에서단말기 11,12와기지국 20,30간호설정 (call setup) 및데이터전송은사용자의서비스등급에따라수행된다. 상기서비스등급은상기무선통신시스템에서상기단말기가처음으로호를설정할때채널운반자 (channel bearer) 에대한대역할당등급과트래픽 (traffic) 제어를위한큐잉 (queuing) 등급으로서정해진다. 특히본발명에있어서상기서비스등급은사용자의만족도함수를결정하는데이용된다. 기지국에서복수의단말기들을서비스하기위해서매스케줄링주기마다전송할데이터가있는단말기들의만족도를고려하여스케줄링을수행하여야한다. 이러한스케줄링동작을위하여상기기지국들 20,30은각각버퍼 (Buffer) 22,32과스케줄러 (Scheduler) 21,31을포함한다. 도 4는도 3에도시된기지국 (BTS) 20의구성을보여주는도면이다. 여기서는기지국이도 3의기지국 20인것으로가정될것이나, 다른기지국 30인경우에도동일하다. 상기도 4를참조하면, 상기기지국 20은주제어기 (Main Processor) 210, 라인인터페이스 (Line Interface) 220, 스위치 ( 또는라우터 )(Intra-BTS Switch or Router) 230, 채널카드들 (Channel Cards) , 고주파 (Radio Frequency: 이하 RF라한다.) 송수신기 (Transmitter/Receiver) 250 및스케줄러 21을포함한다. 상기주제어기 210은상기기지국 20을전반적으로제어한다. 상기라인인터페이스 220은상기기지국제어기 40과의연결을위한것이다. 상기 RF 송수신기 250은단말기 11과의사이에서데이터및제어신호를무선신호 (RF Signal) 형태로송수신하기위한것이다. 상기스위치 230은상기기지국내의트래픽경로를결정한다. 상기스케줄러 21은무선자원의효율적인관리를지원한다. 도 5는도 4에도시된채널카드들 의구성을보여주는도면이다. 이구성은채널카드 241인것으로가정될것이나, 다른채널카드들 의경우에도동일하다. 상기도 5를참조하면, 상기채널카드 241은입출력인터페이스 (Input/Output Interface) 24-1, 주프로세서 (Main Processor) 24-2, 메모리 (Memory) 24-3, 적어도하나의변조기 (Modulator) 24-4 및적어도하나의복조기 (Demodulator) 24-5를포함한다. 상기입출력인터페이스 24-1은상기스위치 230과의연결을위한것이다. 상기변조기 24-4는상기 RF 송수신기 250의송신기 251을통해상기단말기 11로송신될데이터및제어신호를변조한다. 상기복조기 24-5는상기 RF 송수신기 250의수신기 252를통해상기단말기 11로부터수신되는데이터및제어신호를복조한다. 상기변조기 24-4 및상기복조기 24-5는각각하나의순방향채널또는역방향채널을형성한다는점에서채널소자 (Channel Element: CE) 라고도한다. 상기메모리 24-3은상기단말기 11로전송될패킷데이터를상기기지국제어기 40으로부터수신하여일시적으로저장하는내부버퍼 ( 도 3의버퍼 22) 를포함한다. 또한상기메모리 24-3은각종제어정보를저장할수있다. 상기도 2 내지도 5에나타낸바와같이데이터서비스를위하여시간분할스케줄링기법을사용하는무선통신시스템에서, 사용자가느끼게되는지연시간 (delay) 은데이터패킷을사용자의채널특성에맞게슬롯에할당하는스케줄링지연 (scheduling delay) 시간뿐만아니라다른사용자의데이터패킷을서비스하는동안대기하는처리지연 (processing delay) 시간등이포함되어야한다. 다시말해서, 사용자가요청한전체데이터패킷을완전히서비스받게되는시점까지의지연은다음과같이구분될수있다. 지연시간 = 억세스지연시간 + 매체전송시간 + 스케줄링지연시간 + 처리지연시간여기서상기억세스지연시간 (access delay) 은무선사용자가상향으로요청하는데필요한지연시간으로서스케줄링기법과는무관하므로본명세서에서는고려하지않도록한다. 또한상기매체전송시간 (propagation delay) 도유무선매체를통과하는데걸리는지연시간으로서무시될수있다. 그러면스케줄링기법에영향을 미치는지연시간은스케줄링지연시간과처리지연시간의두가지이다. 이지연시간을각각, 라고 하면사용자가느끼는지연시간 T 는하기의 < 수학식 3> 과같이근사화된다. 수학식 3 <58> - 7 -

8 <59> 여기서처리지연시간은사용자가서비스받게될패킷의길이와그사용자의채널상태에의해결정된다. 만약채널상태가변하지않아서사용자 j 에게소정의전송률 가허용되고상기사용자 j 에의하여요구된데 이터패킷의크기가이고한타임슬롯의시간이이면이사용자의예상되는처리지연시간은하기의 < 수 학식 4> 와같이주어진다. 수학식 4 <60> <61> 이를앞서언급한 < 수학식 2> 와비교하면, 각사용자에게주어진전송률 길이가고려되었음을알수있다. 뿐만아니라사용자가요청한패킷의 <62> 데이터서비스를받고자하는사용자들은요구한패킷을완전히받게될때까지걸리는지연시간과채널상태 에따라주어지는전송률등에따라다른만족도를느끼게된다. 상기 < 수학식 4> 에따르면사용자의요구된전 송률는의함수로주어지므로결과적으로사용자의만족도는의함수가된다고할수있다. 즉사용 자 j 의만족도함수를라고하면이사용자의만족도함수는하기의 < 수학식 5> 과같이표현된다. 수학식 5 <63> <64> <65> <66> <67> 상기만족도함수는사용자의서비스등급등에따라다양하게설정가능하다. 일예로서, 사용자의신규가입시시스템운영자는사용자의요구된서비스종류에따라고유한만족도함수를설정한다. 도 6은본발명에따라사용자마다지연시간에따라설정된만족도 (Utility) 함수를곡선의형태로나타낸것으로서, 도시된바와같이곡선 a는볼록형 (convex) 이고곡선 b는선형 (linear) 이며곡선 c는오목형 (concave) 이다. 여기서곡선 a는곡선 c에비하여지연시간에민감하며곡선 b는곡선 c보다는지연시간에민감하고곡선 a보다는덜민감함을알수있다. 일반적으로각사용자가지연시간에대해느끼는만족도는시간이지나면서줄어들게되며지연이커지게되면만족도가크게떨어지지않게된다. 지연시간에민감한트래픽인경우일정시간이지나게되면도 6에나타낸곡선 a와같이급격히만족도가떨어진다. 이러한곡선 a는예를들어실시간동영상서비스등을원하는사용자에게적용가능하다. 스케줄러는매타임슬롯마다어떤사용자에게현재의타임슬롯을할당할것인지를결정해야한다. 그런데무선채널은사용자와기지국간의거리에따른경로손실 (Path loss), 인접장애물및반사효과등으로인한페이딩 (Fading) 으로인해일정한상태를유지하지못한다. 뿐만아니라사용자의이동성 (mobility) 에의해도플러효과가발생하고경로손실과페이딩이더욱영향을미치기때문에채널상태는예측이불가능하다. <68> 따라서처리지연시간 는채널상태에따라변하게되고사용자의만족도또한스케줄링시점에따라달라 질수있다. 게다가시간분할스케줄링기법에서는한사용자 j 의처리지연시간 가다른사용자 k 의처리 지연시간에영향을미치게되기때문에어떤시점에서어느사용자에게슬롯을할당했느냐는다른모든사용자들의만족도에도영향을미치게된다. 따라서어떤스케줄링시점에서어느사용자에게슬롯을할당했을때모든사용자의만족도의합이최대가되도록스케줄링해야한다. 따라서현재채널상태를기준으로현재스케줄링시점에서어떤사용자 j에게패킷을서비스한다고할때이로인한만족도값의변화를계산하여야한다. 이를수학식으로표현하면하기의 < 수학식 6> 과같다

9 수학식 6 <69> <70> <71> 여기서는사용자 j 의만족도함수를의미한다. 만일현재의채널상태가유지된다고할때특정사용자에게연속적으로슬롯을할당하는것이사용자의잠재적 인만족도의합을증가시킨다. 이에대하여설명하면, 연속적으로슬롯을할당받고있는사용자 i 가있고현재 잠재적인만족도의합은 로서최대라고가정하기로한다. 만약연속적으로슬롯을할 당하지않고현재슬롯하나를두슬롯이상의처리지연시간을가진다른사용자 j 에게먼저할당하면, 원래 연속적으로할당받으려했던사용자 i 의처리지연시간 합은하기의 < 수학식 7> 과같다. 가한슬롯밀려나게된다. 즉잠재적인만족도의 수학식 7 <72> <73> <74> 여기서는한슬롯의시간이다. 만약사용자 j 의처리지연시간이한슬롯이라고하면사용자 j 에게먼저서비스를하는것이본래스케줄링 방식보다만족도의합이더커지는것이자명하므로 다. 가최대라는최초설정에위배된 <75> 이를도 7 을참조하여보다상세히설명하면, 연속적스케줄링을나타낸 ( 가 ) 에서사용자 1 이원하는데이터패 킷을모두서비스받기위해소요된지연시간은 이고, 사용자 2 가원하는데이터패킷을모두서비스받 기위해소요된지연시간은 이다. 이에비하여불연속적스케줄링을나타낸 ( 나 ) 를보면, 사용자 1 은 연속적으로슬롯을할당받지못하였기때문에총지연시간은한슬롯시간만큼증가하여으로 증가되었으나사용자 2 또한연속적으로슬롯을할당받지못하였기때문에총지연시간은 다. 으로유지되었 <76> <77> <78> 이상에서상세히설명한바와같이, 지연시간에따른사용자의만족도는단조감소함수이므로채널상태가일정하다고가정했을때한사용자에게연속적인슬롯할당을하는것이여러사용자에게슬롯을섞어서할당하는것보다전체사용자의만족도가더커지게됨을알수있다. 어떤스케줄링시점에데이터서비스를원하는 N 명의사용자가기지국과통신을연결하고있고각사용자는하나의큐를가지고있다고하면, 임의의스케줄링시점에서는앞으로남은패킷들에대해어떤순서로스케줄링하는것이모든사용자의만족도의합을최대화할수있는지를계산할수도있을것이다. 그러나이러한계산은기지국과데이터통신을연결하고있고데이터를서비스받고자하는사용자의수 N에따라계산의복잡도가크게증가하며, 계속하여변화하는채널상태에적응하기위하여매시점마다새로운계산이이루어져야한다는부담이있다. 따라서본발명에서는한사용자에게자원을먼저할당했을때이사용자가얻게되는만족도에대한이득과다른사용자가잃게되는만족도에대한손실을평균적으로계산하는알고리즘을사용하기로한다. 임의의스케줄링시점에서각사용자의큐에남은전체패킷에대해처리지연시간이각각,,,..., 이고스케줄링지연시간이각각,,,..., 라고했을때, 임의의사용자 j 가먼저서 비스된다고하면사용자 j 의예상만족도는 이다. 그런데사용자 j 가먼저서비스받게되면다른사 용자 k의스케줄링지연시간이커지기때문에이로인한만족도의손실은이다. 사용자 j가서비스를마친후에어떤사용자가서비스를받게될지는예측이불가능하다. 따라서모든사용자에대한손실의기대값은하기의 < 수학식 8> 과같이계산된다

10 수학식 8 <79> <80> 상기의 < 수학식 8> 을고려하면, 시점 t 에서사용자 j 에게먼저서비스를한다고할때예상되는전체사용자의 만족도합의변화는하기의 < 수학식 9> 과같이쓸수있다. 수학식 9 <81> <82> 따라서매스케줄링시점에서 할당하면, 모든사용자들의만족도의합을최대화할수있다. 중최대값을갖는사용자에게먼저타임슬롯을 <83> <84> <85> 이하본발명에따른하향링크스케줄링동작을도 8을참조하여설명하기로한다. 여기서상기도 8에도시된동작은기지국의스케줄러에의하여수행되는것임에유의하여야한다. 또한상기기지국은적어도하나의단말기 ( 사용자 ) 와통신을연결하고데이터서비스를제공한다. 또한사용자들은데이터서비스에가입할때또는통신을개시할때서비스등급등에따라각기다른만족도를설정한다. 상기도 8을참조하면, 매스케줄링주기 ( 전송채널의타임슬롯 ) 가시작할때마다 (S105), 기지국의스케줄러는기지국과통신을연결하고있고데이터를서비스받고자하는사용자가존재하는지를판단한다.(S110) 만일그러한사용자가존재하지않으면현재슬롯은유휴상태로유지된다. 그러한사용자가단지 1명존재한다면 (S115) 현재슬롯은그사용자에게사용가능하도록할당된다.(S120) 즉기지국은현재슬롯에서상기 1명의사용자에게요구된데이터를전송한다. 반면상기사용자가 2명이상존재한다면, 과정 (S125) 내지과정 (S155) 에따른스케줄링이시작된다. 과정 (S125) 에서기지국과통신을연결하고있고데이터를서비스받고자하는사용자들을식별하는변수 j와사 용자별만족도를식별하는변수 는모두초기값 0으로설정되고, 파라미터 max_ 는상기 로설정되며, 파 라미터 max_user는 j로설정된다. 과정 (S130) 에서상기 j는 1만큼증가되고, 과정 (S135) 에서사용자 j에게현재 슬롯을할당할시모든사용자의만족도합 을계산한다. 여기서상기모든사용자의만족도합 는이미 언급한 < 수학식 9> 에의하여계산된다. <86> 과정 (S140) 에서상기계산된는 max_ 와비교된다. 만일가 max_ 보다작거나같으면과정 (S150) 에서 j 가사용자의수에도달하였는지를확인한다. 만일도달하지않았으면과정 (S130) 으로복귀하고도달하였으면과 정 (S155) 으로진행한다. 반면에상기과정 (S140) 에서상기가 max_ 보다크면, 과정 (S145) 에서 max_ 는상기계산된로다시설정되고 max_user는 j로다시설정된후과정 (S150) 으로진행하여 j가사용자의수에도달하였는지를확인한다. 만일도달하지않았으면과정 (S130) 으로복귀하고도달하였으면과정 (S155) 으로진행한다. <87> 이상과같은과정들을 j 가사용자의수에도달할때까지반복하면 max_user 는최대의만족도합을가지는사용 자를가리키게된다. 따라서과정 (S155) 에서 max_user 가가리키는사용자에게현재슬롯을할당한다. <88> 그런데스케줄링을요구하는사용자의수가많은경우채널상태가좋지않아평균적인전송률 가작은사용 자의경우시간이지날수록그처리지연시간가커지게된다. 이러한경우같은만족도함수를가진사용자간에수율의차이가커지는공평성이문제가될수있다. 이는전체사용자의만족도의합을고려하고있기때문이다. 따라서전체수율을다소희생하더라도이러한사용자가서비스받을수있도록보정해줄수있다. 공 평성을위해사용자 j 에게고려된인자를 < 수학식 10> 과같이다시쓸수있다. 라고하면본발명에따른스케줄링의목적인 < 수학식 6> 은하기의

11 수학식 10 <89> <90> <91> <92> <93> 여기서상기는사용자 j의공평성인자로서, 예를들어소정개수의슬롯동안연속해서슬롯을할당받지못한사용자에대하여미리정해지는소정값으로설정될수있다. 이하도 9 내지도 16을참조하여, 이상에서설명한본발명에따른스케줄링의모의실험결과를설명하기로한다. 모의실험은 1.25MHZ의대역을사용하고 2GHz의주파수를사용하는코드분할다중화 (Code Division Multiple Access: CDMA) 시스템의셀룰러환경에서진행하였다. 도 2에도시한바와같은근사화된육각형셀룰러모델이적용되었으며인접한 6개의셀까지고려되었고, 여기서셀반경은 500m이다. 채널환경에대해서는경로지수가 -4이고시속 3km의속도를가지는레일레이페이딩 (Rayleigh Fading) 이고려되었다. 데이터를전송하는한슬롯의길이는 1.67ms이며, 전력제어를하지않고전송률제어를하고, 기지국에서는 20W의송신전력을사용한다. 전송률은 CDMA의 HDR(high data rate) 시스템에서사용되는바와같이 38.4, 76.8, 102.6, 153.6, 204.8, 307.2, 614.4, 921.6, , , kbps의불연속적인값을가지며단말기에의해요구된가장큰전송률이사용가능하다. 이때기지국은남는전력에대해서다른코드를할당하지는않으며한슬롯을한명의사용자에게만할당한다. 트래픽모델로서유선망에서의 HTTP(Hypertext Transfer Protocol) 모델을이용하는것은무선네트워크의특성상적합하지않으므로여기에서는 WAP(Wireless Application Protocol) 트래픽모델을사용한다. WAP 모델에서한사용자로부터세션이시작되어서비스에대한요청을하게되면, 이때 WAP 요청패킷의크기는 76바이트이고요청한자료에대해서 WAP 게이트웨이까지응답패킷이도달할때까지걸리는시간은 2.5초의지수분포 (Exponential distribution) 를가진다. 한번의요청에대해 WAP 게이트웨이로부터몇번의패킷들이도달하게되는데이때각패킷들의평균크기는 256바이트이고최대크기가 1400바이트인하기의 < 수학식 11> 과같은파레토분포 (Pareto distribution) 를가진다. 수학식 11 <94> <95> <96> <97> 여기서 k는 71.7이고 α는 1.1이다. 본발명에서는하향링크의스케줄링에대한것이기때문에단말기에서데이터서비스를요청하는데걸리는시간은고려하지않았으며트래픽을계속발생시키기위한무선사용자의요청은없고하향링크의패킷이계속발생하는것으로한다. 한편지연시간에대해민감한비디오스트리밍트래픽에대한모의실험에있어서는, 비디오스트리밍트래픽에서각각의영상프레임은 8개의패킷으로구성되어있으며각패킷의최대크기는 125바이트이고 K=20바이트, =1.2인제한적인파레토분포를가지고있는것으로한다. 각패킷이도착하는시간간격은최대 6ms이고, K=2.5ms, =1.2인제한적인파레토분포를가지며, 각영상프레임의시작시간의간격은 100ms이다. 또한비디오스트리밍트래픽은계속발생하는것으로한다. <98> <99> 수율 (throughput) 은한타임슬롯당평균적으로보낸패킷의크기를바이트로나타낸것이며지연시간 (delay) 은 msec단위로표기한것이다. 한사용자의패킷들의도착시간간격은프아송 (Poisson) 분포를갖는데이평균값을조절하면스케줄러의이용도 (utilization) 를구할수있다. 트래픽로드는이값이 1보다작을때의로드를기준으로트래픽분포를늘려간값이다. 도 9는도 6에서트래픽로드가 1.0일때주어진각각의만족도 ( 곡선 a,b,c) 에대해본발명에따른스케줄링알고리즘의성능을종래기술과비교한도면으로서, 서비스받은패킷전체의지연시간에대한누적밀도함수 (CDF) 그래프들을나타내었다. 이하도 9 내지도도 11에서, HDR(High Data Rate) 은지연시간을고려하지않고비례공평성을사용하는종래기술을나타내며, concave는도 6의곡선 c를나타내고, convex는도 6의곡선 a를

12 나타내고, linear 는도 6 의곡선 b 를나타낸다. 이는도 10 내지도 11 에서도동일한의미로사용된다. <100> <101> 도시된바와같이본발명에따른스케줄링알고리즘을사용하면 80% 의패킷이 17슬롯만에서비스가완료되지만, 종래기술의경우에는 104슬롯에야서비스가완료된다. 또한도 9에나타낸지연시간에대한누적밀도함수의분포는정규화된수율 (normalized throughput) 로서생각할수도있다. 상기도 9에서알수있듯이본발명은종래기술에비하여더빠른시간안에대부분의패킷을서비스할수있으며, 전체수율에서도본발명은 HDR보다크게떨어지지않으며평균지연시간역시더좋은성능을보여준다. 본발명은매스케줄링시점에서한사용자에게자원을먼저할당했을때이사용자가얻게되는만족도에대한이득과이로인해다른사용자가잃게되는만족도에대한손실을평균적으로계산한다. 그러나언급한바와같이사용자가 N명있는경우매스케줄링시점에서이모든사용자를어떤순서로서비스하는것이모든사용자의잠재적인만족도의합을최대로할것인지결정하기위해서는 O(N!) 만큼의계산이필요하다. 이러한알고리즘 ( 이하 MAXU라하기로한다.) 을사용하는경우와본발명의경우만족도를비교하면하기의 < 표 1> 과같은결과를얻을수있다. 표 1 <102> 트래픽로드종래기술본발명 MAXU <103> <104> <105> 상기 < 표 1> 을보면 MAXU는본발명과거의비슷한결과를보이고있으며따라서본발명은사용자만족도의합을가장효율적으로최대화한다. 게다가트래픽로드가 0.8인경우는오히려본발명이 MAXU에비하여다소높은결과를보여주는데이는채널상태가계속바뀌게되므로매스케줄링시점마다 MAXU와같은계산을하는것이큰의미가없기때문이다. 상기 < 표 1> 을보다상세히살펴보면, 트래픽로드가커질수록스케줄링알고리즘의활용도가커지므로사용자의평균만족도가감소한다. 그러나트래픽로드가 1.0에서 1.2로넘어가게되면스케줄러가처리할수있는것보다트래픽이많아져서우선순위가낮은패킷에대해자체적으로서비스를하지않기때문에만족도가증가하게된다. 도 10 및도 11은사용자 1,2,4,5를채널상태가좋은순서대로일정한위치에고정시킨후사용자 3에대해서각기다른방향으로움직이게한경우에대하여전체수율과평균지연을나타낸것이다. 여기서 WAP 트래픽이 36 초간발생하였고트래픽로드는 0.9 이다. 또한이때사용된사용자만족도함수는, = 100 이며, 사용자 3 은시속 50km 의일정한속도를가지고이동하였고, 셀반경은 500m 인것으로한다. <106> <107> <108> 보다상세히설명하면, 도 10은사용자 3이셀경계에서셀중심으로이동하는경우지연시간의누적밀도분포 (Cumulative Density Function : CDF) 와수율을나타낸것이며, 도 11은사용자 3이셀중심에서셀경계로이동하는경우지연시간의누적밀도분포와수율을나타낸것이다. 여기서도 10과도 11에서종래기술1은 100 슬롯타임 (167ms) 의상수를가지는저역통과필터 (Low Pass Filter: LPF) 를사용하는종래기술에따른스케줄러를의미하며, 종래기술2는 1 슬롯타임 (1.67ms) 의상수를가지는저역통과필터를사용하는종래기술에따른스케줄러를의미한다. 상기종래기술1,2에따른스케줄링알고리즘은과거의채널상태를나타내는평균채널상태를고려하여지수평균 (exponential weighted averaging) 을내기때문에이동성에취약할수밖에없다. 즉도 11에나타낸바와같이셀중앙에서셀경계로이동할때는평균채널상태가변화하는것에비해현재채널상태가급격히떨어지기때문에지연시간이급속히증가하며반대로이동할때에는반대의현상이나타난다. 종래기술1과종래기술 2 모두유사한결과를보이고있다. 도 11에서와같이셀경계로이동하는경우채널상태가나빠지기때문에현재채널상태에많은비중을주어평균채널상태를구한종래기술2의경우가종래기술1보다평균지연시간에서약간나쁜결과를보이며, 반대로도 10에서와같이셀중심으로이동하는경우채널상태가좋아지기때문에종래기술2가종래기술1보다다소

13 좋은결과를보이는것을확인할수있다. 그럼에도불구하고도 11에서보는바와같이사용자가셀중심에서셀경계로이동하는경우에종래기술1,2는모두본발명보다떨어지는성능을보인다. 반대로셀경계에서셀중심으로이동하는경우에는도 10에서보인바와같이본발명과어느정도비슷한결과를보이고있지만평균지연시간에서는여전히본발명이우수한결과를보이고있다. <109> <110> <111> 이상의도 9 내지도 11에나타낸모의실험결과는 WAP 트래픽모델만을적용한경우이다. 이하도 12 내지도 16을참조하여, 비디오스트리밍트래픽과 WAP 트래픽을모두서비스하는경우본발명을적용한모의실험결과에대하여설명하기로한다. 상기도 12 내지도 16은, 같은채널상태를갖는사용자에대해서 20% 의사용자는비디오스트리밍트래픽을, 나머지 80% 의사용자는 WAP 트래픽을다운로드받는경우에대하여 1분씩 100번의모의실험을반복하여수행한결과를나타낸것이다. 여기서 HDR은지연시간을고려하지않고비례공평성을사용하는종래기술의스케줄링알고리즘을의미한다. 또한 Proposed1은 WAP 트래픽과비디오스트리밍트래픽에대해같은만족도함수를적용한경우를의미하고, Proposed2는비디오스트리밍트래픽에대해지연시간을고려한다른만족도함수를적용한경우를의미한다. 비디오스트리밍에대하여다른만족도함수를적용한경우에적용되는만족도함수의형태는도 12에나타낸바와같다. 상기도 12에서볼록형 (convex) 곡선 a는비디오스트리밍트래픽을나타내고오목형 (concave) 곡선 b는 WAP 트래픽을나타낸다. 즉, WAP 트래픽에대한만족도함수는오목형인로, 비디오스트 리밍트래픽에대한만족도함수는 로설정하였다. 여기서 β = γ = 100 이다. 비디오스트리밍 트래픽의경우한영상프레임의크기가 100ms 이므로지연시간이 100ms 보다커지게되면만족도는 0 이된다. <112> <113> <114> <115> 도 13 내지도 16은지연시간에대한패킷들의분포를나타낸것이다. 도 13은비디오트래픽사용자가 1명일때비디오스트리밍트래픽의지연시간에대한패킷들의누적밀도함수의분포를나타낸것이다. Proposed1,2를종래기술과비교했을때본발명은 WAP 트래픽과같은만족도함수를준경우에도훨씬좋은성능을나타내고있다. 왜냐하면비디오스트리밍트래픽의특성상한패킷의크기가 WAP 트래픽의경우보다작기때문에스케줄링에서이득을보기때문이다. 특히비디오스트리밍트래픽은지연시간에대해민감하므로, 볼록형 (convex) 만족도함수를적용한경우가동일한만족도를적용한경우보다더좋은성능을나타낸다. 도 14는비디오스트리밍사용자가 1명인경우나머지 WAP 트래픽사용자의지연시간에대한누적밀도함수를보인것이다. 도시된바와같이, 비디오스트리밍트래픽의성능이좋아진것과반대로 WAP 트래픽의경우 Proposed1,2는종래기술보다성능이떨어진다. 그러나두트래픽의특성을따져볼때비디오스트리밍트래픽이지연에훨씬민감하기때문에 WAP 트래픽의성능이다소떨어지더라도이와같은결과가더만족스럽다고볼수있다. 도 15 및도 16은비디오스트리밍트래픽사용자가 2명인경우각트래픽에대한지연시간의누적밀도함수분포를보인것이다. 도 15 및 16을도 13 및 14와비교하면, 비디오스트리밍트래픽사용자에게다른만족도함수를적용한본발명2의결과가더양호하게나타나고있다. <116> 한편본발명의상세한설명에서는구체적인실시예에관해설명하였으나, 본발명의범위에서벗어나지않는 한도내에서여러가지변형이가능함은물론이다. 그러므로본발명의범위는설명된실시예에국한되지않으 며, 후술되는특허청구의범위뿐만아니라이특허청구의범위와균등한것들에의해정해져야한다. <117> <118> 발명의효과이상에서상세히설명한바와같이동작하는본발명에있어서, 개시되는발명중대표적인것에의하여얻어지는효과를간단히설명하면다음과같다. 본발명은사용자별로그트래픽특성에따라지연시간에따른만족도를설정하고, 매스케줄링주기마다모든사용자의만족도합을최대로하는사용자를선택하여슬롯을할당함으로써, 사용자의서비스지연시간을최소화하고실제만족도를향상시킨다. 게다가본발명은스케줄링을효율화하여기지국의데이터처리율을향상시

14 킬수있는효과가있다. <1> <2> <3> <4> <5> <6> <7> <8> <9> <10> <11> <12> <13> <14> <15> 도면의간단한설명도 1은무선통신시스템에서코드분할다중화와시간분할다중화를설명하는도면. 도 2는본발명이적용되는무선통신네트워크모델을보여주는도면. 도 3은본발명이적용되는무선통신시스템의네트워크구성을보여주는도면. 도 4는도 3에도시된기지국 (BTS) 의구성을보여주는도면. 도 5는도 4에도시된채널카드들의구성을보여주는도면. 도 6은본발명에따라사용자마다설정된만족도함수를곡선의형태로나타낸도면. 도 7은연속적스케줄링과불연속적스케줄링을비교하여도시한도면. 도 8은본발명에따른하향링크스케줄링동작을나타낸흐름도. 도 9는도 6에서본발명에따른스케줄링알고리즘을, 지연시간을고려하지않고비례공평성을사용하는종래기술과비교하여도시한그래프. 도 10 및도 11은사용자의이동시평균지연시간의누적밀도함수와전체수율을본발명과종래기술을비교하여도시한그래프. 도 12는비디오스트리밍에대하여다른만족도함수를적용한경우에사용되는만족도함수를곡선의형태로나타낸도면. 도 13은비디오사용자가 1명일때비디오스트리밍트래픽의지연시간에대한패킷들의누적밀도함수의분포를본발명과종래기술을비교하여도시한그래프. 도 14는비디오사용자가 1명일때 WAP 트래픽의지연시간에대한패킷들의누적밀도함수의분포를본발명과종래기술을비교하여도시한그래프. 도 15는비디오사용자가 2명일때비디오스트리밍트래픽의지연시간에대한패킷들의누적밀도함수의분포를본발명과종래기술을비교하여도시한그래프. 도 16은비디오사용자가 2명일때 WAP 트래픽의지연시간에대한패킷들의누적밀도함수의분포를본발명과종래기술을비교하여도시한그래프

15 도면 도면

16 도면

17 도면

18 도면 4 도면

19 도면

20 도면

21 도면

22 도면 9 도면

23 도면 11 도면

24 도면 13 도면

25 도면 15 도면

(72) 발명자 박세웅 서울특별시관악구신림동산 56-1 서울대학교뉴미디어통신공동연구소 최진구 서울특별시영등포구당산동 2 가대우메종아파트 101 동 909 호 - 2 -

(72) 발명자 박세웅 서울특별시관악구신림동산 56-1 서울대학교뉴미디어통신공동연구소 최진구 서울특별시영등포구당산동 2 가대우메종아파트 101 동 909 호 - 2 - (51) Int. Cl. (19) 대한민국특허청 (KR) (12) 등록특허공보 (B1) H04B 7/26 (2006.01) H04B 7/155 (2006.01) H04Q 7/30 (2006.01) H04Q 7/20 (2006.01) (21) 출원번호 10-2006-0085572 (22) 출원일자 2006 년 09 월 06 일 심사청구일자 2006 년 09 월