Introduction

我今天要跟大家分享的這個主題，其實是我們去年的一個計畫，幾乎你只要講到WiMax，大概大家都知道是怎麼回事，那為了不知道有沒有同學對這方面不熟，所以我等一下大概會有一些比較簡單的簡介來告訴你，它現在的功能一些background，那我們看一下，這個題目其實是看起來好像很長，可是也不用全部看完，因為這個是一個計畫的名稱來的，譬如資策會委託我們做的一個計畫，他的計畫幹嘛的呢，是這樣子的，是說他希望在WiMax上面提供IPTV multicast的service，是群撥的服務，那問題是，你要做這個服務的時候，大概會遇到有一些技術上的一些問題，那他希望我們從這個問題出發，來告訴他們說，如果我們要提供這種服務，我們大概需要做哪些事情，那這個基本上這是一個整合型的服務，那我比較談的大概，我會簡單講一下我們的架構，然後我們做了哪些東西，還有我們現在正在進行中的大概是甚麼，那我會偏向一個簡單的語言來跟大家分享這個主題。

那基本上這個在WiMax裡面，我們現在大家聽得比較多的大概就是a, b，那基本上大都就是b的，我們目前聽到的這種不會動的大概都是b的，那d的，其實是不會動的，可是他基本上，你那個mac上，所有的這些基本的東西，大多都定義在這裡面，那現在很多人都在做e，因為現在的主流其實是e，可是從mac的角度來看，他基本上是沒有甚麼區隔的，所以其實這個，對d跟e基本上是沒有甚麼要求的，只是我們要做的時候，資策會希望我們作e的，大概是這個樣子，那這個剛才有讓大家看到，就是說依著string這個下來，我們會做一些scheduling然後再送下去，那我們會base on下層的這個information來做那個相關的這個scheduling，那這個是我們系統的整個架構。

ＷiMax

那往下講，我們怎麼作這些事之前，我們很簡單的overview一下，這個整個WiMax的一些基本架構，那這樣子講了這些東西，因為我們如果要講WiMax，那個information我在想大概一個小時大概也講不完，所以我大概就挑跟我們這個在做計畫有關的那一部分，來讓大家那個re-flash一下memory，這樣比較容易聽下去，那我們來看，這個基本上，802.16他基本上是一個wireless program access technology，是一個寬頻擷取的技術，那他基本上，比較重要的東西大概有兩個，一個是平行緒，一個是base station，那他的這個基本上，我大概講說，我們如果從base station往下看，這個方向是broadcast的，也就是說，都是由base station在送，除了ping在broadcast，那我如果在這個方向，在unlink的方向，基本上是所有的station都可以送，那這個在ping，所以往下送應該比較簡單，這個叫broadcast，往上送，會比較困難一點，為什麼，因為這個receiver層的比較多，所以往上送，你需要mac的這個prog來做這件事情，那所以說那這個再怎麼有機會去K這個802.11這個wireless的space，就會發現，我們扣掉fight不講，因為我們做的事跟那個CS有關的，我們看的那個會從mac往上看，就會發現說，其實整個802.16的mac，基本上是一個reservation，再加上TDMA的架構，他是這個樣子，他是一個TDMA的架構，那這個我們就不再仔細講了。

那目前我們看到的evolution mode大概有三種，我講的是d，就是說所有的，目前我們看到的有三種，一種叫做點對多點，point to multipoint，那這個基本上，就很適合我們在resent station上用的，就是我們在住架上用的，如果說你今天都這樣子，這個叫PMP mode，另外一個，就是mesh mode，mesh mode就是說，PMP mode就是說，我們這個送的方，一定是base station，base station一定是下面的人，彼此之間是不work的，那我如果是mesh mode，這個其實是想當然爾，就是說我這個其實之間是可以talk的，我不需要經過A station，我倆倆之間就可以talk，可是你如果是PMP mode，它們兩個mode牽涉到這樣才可以，那另外呢，還有一個東西叫做mesh mode，那如果你去看過這個叫做create mode，那如果你去看過這個mesh mode這個stack的話，我在想很多人大概心裡的疑惑會跟我當時在看是一樣的，就是說，這怎麼可能，這根本不可能做出來，太複雜了，然後呢，真的就是這樣，所以呢，可是這樣聽起來好像也不錯啊，最後找了一個簡單的版本，基本上也是multicast的樣子，很快就是relay，那也就是說我在base station跟relay station中間，放relay station，這些relay station呢，可以來幫你做這個relay的動作，可以增加你的colleague，還有提供你的throw input，那這個呢，大概是指整個WiMax的基本架構大概是長這樣。那有了這個東西之後呢，我們還要看一個東西，就是說，在WiMax裡面，他有一種東西叫做burst profile，那這個burst profile基本上是一些這個modulation跟coding的一些技術，那這個呢是說，我每一個這個sursival station，我要開始使用這個service，要用你這個channel之前，基本上呢，我要先跟base station跟你negotiate一下，來決定說等一下你送給我的時候，你要用哪一組的coding或encoding的skin來送給我，那對他們來講呢，他們就是把另一層各式各樣不同的burst profile，所以呢，這個每個sursival station要開始送之前，要跟base station先negotiate好一下，我現在或許是這樣，或是說是這幾種，那我等一下就這組這樣好不好，所以它們基本上是每一個都要跟它們negotiate，那基本上大概是這樣子，我離這個base station越近，我的channel quality越好，所以速度應該是越快才對，應該是這樣，那當我離他越遠，我的距離基本上越遠，所以我的這個channel quality就會越差，所以呢，這個data rate就會越低才對，應該就是這樣，那對於這個WiMax來講呢，他就是這樣講了，當我的這個距離base station越近，這樣講，距離他越遠好了啦，那他的airway會增高，所以呢，我就要用比較burst profile來幫你做encoding，那你越burst profile，那data rate基本上就是越低，所以呢，你越往base station靠近，你的burst profile就可以不要用burst的，那相對之下，他的data rate就會提升，那這整個就是目前在做的是這樣，那你要開始做之前，要建連線之前，要先跟他negotiate好，所以呢，你就會先有一個burst profile來等一下，我等一下才會知道說，因為base station送給我這個東西，我要如何去decode好，那你的decode burst profile，你除了在連線剛開始的時候要做這件事情之外，其實你再連線當中，你都還可以持續的在base station進行negotiate這件事情，這個是基本上，這個是WiMax本來就有，而且是一定要這樣子做的，那這個呢，也是我們等一下我們要做multicast的時候，我們很重要的一個我們需要考量的這個因素，那我們都知道，這個802.16他基本上有兩個mode，一個是TDT mode，一個是FTD mode，那這兩個是說，我在切上下型的時候，一個是用時間來切，一個是用frequency來切，這樣可以聽得懂嗎？那用時間來切呢！其實我剛剛講過，這個其實滿容易了解，就是說我一個frame我切，這個是下型，這個是上型，所以這兩個是沒有辦法同時進行的，譬如這個是跟著這次的時間走，所以呢！第一個就是下型先做完之後，broadcast完之後，接下來呢，uplink的部分才輪到…這樣送，這個是TDT部分，那你如果是FTD呢，其實是兩個基本上是瘦一點的，可是基本上兩個是可以同步進行的，是有一點不太一樣的，那我們現在目前所看到的大部分是TDT的系統架構，他們上下型切的是二比一，我問過所有的廠商都這樣，那這個default大致的樣子，那這個每個802.16的connection，他基本上是一個connection oriented，就是說你要接受某些service之前，你要先跟base station講說我要建連線，這個每一個connection 就會有一個connection id給你，base station他基本上是很明確的知道有誰跟他連線，要用甚麼service等等他全部都知道了，所以這個基本上是一個centralize的架構，那這種cad的connection有三種，你可以是你自己跟他連的，unit-cast的，你也可以是multicast的，multicast就是說，你只要進到某一個channel你都可以同一個multicast 的connection，大概這樣，那你也可以是broadcast的cid ，這種connection這種broadcast cid開始的話就表示說人人都可以說話，這基本上目前訂定出來大概由這幾個其實是建連線的時候可以用，基本上還有一個細節啦，我就不再細講了，這也是大家很常在WiMax所看到的，還有uplink各式各樣的service class，那我猜呢，還有很多人再做WiMax study的時候，很多人很喜歡從這個地方著手，上型，因為上型有mac，所以比較容易去操作，可是呢，我們這一次的talk呢，我們這個只看下型broadcast的部分，所以這個部分我就不再細講了，我想這個很容易了解的，你不用跟他要求他定期給你，比如你給我ip port的話，所以他每一次給你64k，大概是這樣，他是固定給你，你不用跟他要她也會給你，那這個不好，所以我想很多同學看過，她多了一個，他可以多一個service connection，你不要講話的時候他也會幫你把這個resource擠壓出來，那另外這兩個是toren，一個是real-time toren，一個是non real-time toren，那因為這個方法其實沒什麼，一個是上型部分，我要往上送東西的時候，看你要哪一種，這個才要去選，那我們今天要看的呢，base station我要送IPTV給大家去看，所以這個才是下型，那這個東西其實不太一樣的，不過這只是給你做參考。

IPTV Multicast on WiMax

我們其實今天這不是我們的主題，看到這裡呢，其實我們等一下要用到的WiMax的基本概念，大概都複習差不多了，有了那個東西之後我們就容易往下講，我們來看一下呢，我們剛才講過，因為我們的目的，基本上是希望在WiMax上面提供IPTV service，所以除了呢，我這個一個program送下來，那我這個這邊是畫成兩種不同種類的顏色，一種是綠色的，一種是紅色，我如果是綠色的呢，就跟你說我這個channel quality不錯，然後我如果是紅色的，我跟你說我這個channel quality不太好，可是我program送下去，我這些人通通都要去收看這個節目，那我用哪個burst profile，因為我如果全部都只有綠色，那簡單，我就用綠色burst profile來幫你做coding跟coordination的動作就可以了，我如果全部都是紅色的，那也簡單，我就用他的burst profile來幫你做這件事情就好，我如果是visa怎麼辦呢，這個還簡單，因為這麼只有兩種，我如果有很多種的時候該怎麼辦，因為在外面看到burst profile很多很多個，這時候你怎麼辦，這是我們今天所要討論的問題，在這個stack裡面呢，你說他既然有提供multicast service，大家應該有想到這個問題才對，他怎麼做呢，這個很簡單啊，為了顧及大家的權利，我選擇用最爛的，最爛的來做encoding的動作，那這樣好了，這應該沒問題啊，我都可以收到，這樣的感覺蠻奇怪的，有一些人他基本上離base station比較近，他需要接受他卻需要因為某一個人，她距離base station比較遠，那時候ping進來，我把它看得好好的，忽然品質就變差了，如果說某個比較遠的人離開了，忽然品質就變好了，這種感覺蠻奇怪的，所以說這個是space目前是很簡單的告訴我們說，如果你今天，如果要做multicast service的時候，沒關係，反正我就是這樣嘛，那你如果要提供比較好的，可以，你可以當成你base station，或者你這個service，你可以去做這件事情，那這個呢，是我們整個study的開始，我們就是從這個地方開始的，那這個剛才有跟大家提了，就是說你要做encoding的時候，你就是用最差一個人的來做，那如果要解決這個問題怎麼做呢，其實我不要往下講，其實我不斷講只要有做過這個multimedia的成員，應該會馬上就想到說，這也蠻簡單的，我就layer encoding來做就好了啦，這同學有聽過嗎，layer encoding你們知道嗎，就是說，他可以看，這個基本上呢，我有video我可以把他encode成不同的layer，就最基本的那個呢，我們稱做他為base layer，然後我可以在上面在連一層，那妳們看了就會quality會再稍微好一點，那往上在連一層，就會再好一點，那所以說呢，最基本的單一個，你可以看得那麼清楚輪廓的，我們稱他叫做base layer，然後呢，往上呢，看你要加幾層都可以，當你的頻寬越大的時候，你就可以加越多層，那上面這個呢，就叫enhance layer，這個不是我們發明的，這本來就有，那有了這個東西之後呢，同學們大概就可以猜得到了，那你就是channel quality好的人，就收多一點嘛，那channel quality差的人，就收少一點就好了嘛，大概是這樣，那如果就這樣子的話，我們這個計畫大概就撐不下去，因為這樣講完就結束了，那接下來要幹麻，所以我等一下跟妳們說問題在哪裡，所以這個基本上就是說，我今天把你交給base station，他在multicast下去，然後呢，我這個每一個layer，都當成是一個multicast layer，所以我送下去之後，每一個人就根據你的channel quality，來決定我要收幾成，這樣子，那你channel quality越好的，表示你離base station越近的，你可以用比較burst profile來解的，你就可以收多一點，你離越遠的，你改變他的就比較低，那你就是收比較少成，這樣子不就好了嗎，概念大概是這樣。

可是如果要做這件事情的話，其實我剛剛是有提，就是不用做啦，那問題是重點在哪裡呢，重點就是這樣，我們來看一下這個，重點就是這樣子說，如果呢，應該說問題就是剛才那樣，這個問題就那樣，可是問題是，wireless的resource，如果很充裕的話，剛才那樣做基本上沒有問題，可是呢，不知道妳們那個甚麼資訊展，還是那個甚麼WiMax forum有沒有去參觀過，有沒有座那個體驗車，聽他跟妳們講他的那些話，有沒有像今年，他就會跟你說，我一個這個WiMax的base station呢，他比這個Wi-Fi還要好，我不知道妳們有沒有去座這種體驗車，它們都是這樣講的，因為一個base station呢，他的data rate可以up 150個mega per second，我不知道妳們知不知道，然後呢，其實呢，他們沒有跟妳們講一件很重要的事情，就是說，這個150，跟WiFly不一樣，WiFly呢，就all directional，all directional就是說我是全向性發射的，所以說你150，就是全部都是收到150，可是WiMax呢，叫作指向性的，他是切成三個chapter，150是給三個chapter share，所以他每一個chapter大概是50 mega per second，可是說改覺蠻多的啊，但是還沒結束啊，這個50 mega per second是分上下型，那現在大概是切二比一嘛，所以你仔細想想看，其實下型沒那麼多啦，大概是甚麼30 mega per second，沒有你想像中大到那個程度啦，所以說呢，你如果是聽一下producer跟你說，每個人呢，你可以家裡的ADSL不要了啦，改用WiMax啦，其實你應該再仔細再想想看，因為他如果這個chapter裡面超過30個人以上，你的data rate一定是less then 1 mega per second，而且我剛剛講這個150，這個基本上是講多了，因為目前大概一個大概45，目前大概如果是motorola的這個產品大概到45 mega per second沒問題，然後再切上下型大概30，頂多就是這樣子而已，那所以說呢，我剛剛跟你講這句話的最重要的意思是告訴你說，wireless resource是沒有你想像中的那麼多的，所以說呢，我這個一個base station要射給那麼多人，我一個second，如果是每一個人都要收到這個節目，每一個人都要收很好，基本上呢，是撐不下去的啦，這個基本上是這樣，而且呢，你這個30 mega當stream，不是所有都拿來作IPTV用，因為有很多人是來做寬頻截取用，所以呢，你不可以說我這個30 mega全部都拿來當成這個東西使用，所以這告訴我們一件很重要的事情就是說resource不夠，那不夠呢，我如果呢，每一個我tune到這個不同的channel的人，我就可以看節目，那我現在要決定，到底哪幾個program，我要allocate resource，然後我每一個program呢，我都會切成不同的layer，每一個layer呢，他要的resource不一定會一樣，而且呢，還有一點，就是說因為我每一個layer都當成一個multicast這樣送下去，所以說每一個user就可以根據我們burst profile來決定我能不能收，所以我每一個layer裡面可以serve的人好像也不一樣多，那問題是就是這樣，當我可以serve的人越多的時候，他是有一個something在裡面的，那這個應該是個合理的something，當我serve的人越多，我一個layer裡面serve的人越多，什麼越低？data rate一定越低，為什麼？因為裡面已經有一些了，搞不好你就，因為你如果人比較少is lake likely大家就比較集中，不一定啦，可是當你人多的時候，其實你就有一個風險，就有一些搞不好他channel的quality比較不好，所以距離就比較遠，所以你就要用比較robust的burst profile來call他，這時候，效果就會不好，所以我們要去決定說，每一個layer，要含進來多少人，這個是第一個，每一個layer要給多少人，那這樣子囉我要決定每一個layer我要給多少resource來送她，第二，每一個program有幾個layer我要把它包含進來，第三，哪幾個program我要給他resource給他，所以其實有很多要決定的啦，那這個在中英search的來說是非常非常愉快的一件事情，沒有搞成那麼複雜，還真寫不了paper，那這樣子一搞下去，馬上就發現這是一個NP的問題，是這樣是一個NP的問題，那所以說，我們等一下馬上會來看這個東西，在講這些東西我們先來看我們的objective。

Utility-based Resource Allocation

這個基本上我們是希望能夠設計一個比較好的，這是最主要的目標，那接下來，我們的objective是什麼？我們的objective是希望說，我可以讓我的user都很happy，我們可以maximum，這個基本上用我們專業的術語maximum他的utility，當然，滿意度怎麼樣去衡量，這個有各種的方式去衡量，等一下來跟大家分享一下，我們希望，我們customer越happy越好，以這為目標，除此之外，我也希望呢可以maximum我整個radio resource，這是我們問題的目標，我們希望達成的，那我希望我們設計出來的這個機制，可以反應wireless channel的condition，因為有線網路上的NP maximum太多了，可是在wireless上的做的很少，有做的，基本上也是假設這個channel quality是差不多的，所以做這個的其實不太多，此外，像這個WiMax或4G的這種技術，它基本上有所謂的 Adaptive modulation Coding的技術。所以有AMC這種技術，是可以dynamic這樣調的。有了這一點，我們又可以多做一點時情了，此外除了考量channel quality之外，我們還要考量一點，就是video的受歡迎程度，比方說，我有兩個visual program，一個是王建民的球賽，另一個是很無聊的古典電影。那他們的interface是不一樣的，所以我們希望我們設計出來這個機制還可以在某一程度在做allocation的時候，是可以反應我這個video的popularity. 是否受歡迎與我們如何serve它，user才會高興一點，當然我們猜的出來，愈popular我們serve它，user就會高興比較多，可是也不能只有一個user在看，就不理他。這樣子很多客人就會跑掉了，因為哪有這麼巧，每次都跟別人看同一個節目，所以這是同時要兼顧的。這就是我們設計object。

那我們簡單的approach是什麼呢?我們基本上是一個utility-based的架構，那什麼是utility呢，就是當我把resource給你的時候，有一種東西叫utility function，是指我給你resource時，你的高興程度是多少。如果是IPTV的utility function，在我們這個work是這樣定義的，我們把一個program分成很多個layer，對每一個user來講，我收到這個base Layer，我有一個基本的高興程度，而且應該是高興程度最多，然後接下來我收到第二層enhancement Layer就是再高興一點，可是當resource愈來愈多，增加的utility會有遞減的效果。可是若是我最基本的一個都沒有拿到，那麼便快樂不起來。每個user收到一個layer都會有一個conditional 的快樂指標。但是這個exactly的數字是多少呢，其實我們也不知道。我們先把它當成是有這個東西，但是一般我們怎麼量出來呢，目前有兩種方法，第一個叫作per signal promote? threshold，這個是IPTV定的，它基本是可以利用公式轉換出來。比如說我們可以base on delay or error rate等等，可以轉換出來你的高興程度是多少。透過這個來量我們就可以知道這個影片該給的layer是多少。另外一個是大家最常聽到的，My opinion 4，發問卷調查來得知user的高興程度，如很高興就給五分，普通高興就四分，這樣遞減。然後把這些分數統計起來會有個值。聽起來雖然怪怪的，但是很多人都是這樣講的，不管是video或audio，很多人在量快樂程度都是這樣講的，所以倒底他們是怎麼量出來的，我們也不知道。但是我們假設給定一個resource，它的utility已知。還有呢，怎麼IPTV的utility function一定是長這樣的，是什麼意思呢，是說我這個utility function在收到第二個layer之前，我第一個layer要先收到。我光只收第二個layer也快樂不起來，因為我第一個layer沒收到，還是不會有東西，要兩個layer加起來才會有東西。所以我收到這個東西要快樂是conditional的，要下面的東西也要收完才對，所以這個快樂程度要加進來，是要下面都要收到了，以此類推。所以這樣看，你可以看出來，這整個utility function是呈階梯狀的。如果這個x軸是resource的話，我resource allocate愈多的話，我就可以有愈多的layer可以設它，這樣我的高興程度也可以往上升。我們文獻要說的function 就是長這個樣子。

剛才有提過，每個使用者倒底是高興到哪裡是depends on channel quality，才知道你是說這個，這個，還是這個。唯一可以知道的是他的utility一定是summation，所有他所接到的layer的utility 把它加起來，一定是整行的加起來。有了這個之後，我們再往上看，每個user可以收到幾個layer，是可以adjustable的，可以根據channel quality 來決定你可以收到幾層，還有目前available的resource，resource不夠時，系統自動不會broadcast那一層出來，你自然就不會收到了，所以non-availiable layer? for each user，基本上depend on 這幾個條件，自己的channel quality還有system protocal resource，兩個可以決定每個人可以收到幾個layer。我們接下來做了optimization的問題，基本上是希望maximize total utility。我是利用available radio來判斷，但基本上這個是NP的問題，所以我們一定要搞一個heuristic方法出來。這個heuristic我們證過了，跟 optimum只差一點點，他有個tie-bound。 往下看之前，另外我們有幾個基本假設，我在說明這個問題的時候，我們整個WiMax在送東西的時候，從station送下來的frame會切上行跟下行，怎麼切就depends on 你用的是SDD還TDD，我們這個系統假設它是TDD，因為我若按時間來切，就沒什麼差別，我只需要看downlink substream那部分就好，所以我們這裡說downlink subframe，而另外還有一個uplink subframe，這樣整個才構成一個frame。那在downlink substream的broadcast裡面不可能整個拿來傳IPTV用，所以我們就假設只有這一個部分拿來當IPTV的使用，所以我們用的resource就是這個的意思。另外我們做一個假設，我們裡面所探討的program有m個，每一個program我頂多用這個MPEG4的coding可以分為k個layer，system所提供的burst profile有n個，這個burst profile長這樣，它有各式各樣的modulation，所以在選burst profile的時候可以根據channel rate來可以決定我的modulation可以有哪幾個。因為我們有一個老師在做Python，他給我們一個小程式，只要input一個channel quality，它就可以告訴我們用了哪一組burst profile。有了這個之後，我們馬上便可看的出來這圖是多少。我們假設我們set off 我們的burst profile，我們先假設有n個及robust的程度，愈robust的，data rate愈低。我同樣的data量，data rate愈低，傳的愈久，所以我們在分這個resource是用時間，是用幾個time slot來分，所以愈robust，時間就要拉長，用的resource 就愈多，有了這個之後，便可以來做optimization的問題。

我們現比方說有個很簡單的例子，現在這裡有五個program在裡面，每個program都可以分為base layer跟很多個enhance layer。接下來，每個program有興趣看的custom不一定一樣多，這裡假設有三種不同的channel quality，channel quality加愈多的表示channel quality愈好，加愈少的愈差。所以若channel quality最差的只能收到base layer，稍微好的可以收到base layer及第一層enhance layer，愈好的可以收到愈多個enhance layer。於是我們便可把program的utility怎麼出來呢，每個user收到base layer的高興層度是一樣的，有收到一層的enhance layer等於這個加這個，所以我們看他收到幾層，就把幾層summation起來。接下來，我把這些東西加起來，並maximum它，但是我目前無法決定的是，我到底有多少人可以放到每個layer裡面去，我每一個program 可以切幾個layer在裡面，所以我要決定的objective function就有兩個。這個可以很簡單便可證明出來，用traditional 的101 algorithm便可證出來這是NP Problem。到這裡就不用再證了，因為很高興它是NP，所以我們只要找個heuristic 就好了，並且告訴大家它有多好。但是我們等下不會講這些，因為它太理論了，我們只跟你說我們怎麼做，讓你感受一下怎麼跟optimum很接近。我們的基本作法是，現在有好多好多個program在這裡面，每後有的program有user在看，有的沒有，所以每個user channel condition都不一樣，每個user要收的也都不會都一樣，我們先把他們全都畫出來。我們先會對他們做sorting，channel condition愈高的放愈前面，因為channel condition愈好的，它就不需要用很robust的方法去解，消秏的resource就愈少，效果非常的好。但program的觀迎程度還沒談到，等會會再討論這個問題。

我們先假設每個user要看哪幾個program，及channel condition為已知，接下來，每個layer裡面我們可以include幾個user進來，因為include愈多，用的resource愈多。我們可以看這個例子，我們先看一個layer，也就是一個program中的同一個layer。假設我有四個user，他們的channel quality都不一樣，加愈多的表示channel quality愈好，data rate愈高。基本上我這個例子是normalize過的，我對這個data rate最高的做normalization，所以我data rate愈高的就會愈大。我們把它取倒數，取倒數就等於說我們用了time slots有幾個，比如說data rate是1的話time slot就是1，data rate是0.5就有兩個time slot，所以很明顯的data rate 愈低效果愈不好，要愈robust來encode，消耗的resource也愈多。接下來看，這個橫軸告訴我們要用多少resource給你這個layer，也就是說我要include多少人進來，如果我只include一個人進來，我要include channel quality 最好的這個。因為他只需要一個time slot就好。如果我要include第二好的進來，要include兩個人進來，我就需要兩個time slot，那我要include三個人進來，就需要2.5個time slot。所以可以看到，include 愈多人進來，風險愈大，用的resource愈多，每include一個人進來便可收到這個layer，那他收到這個layer便會很高興。每include進來的人的utility程度是一樣的，include一個人就一個人很高興，include兩個人就兩個人很高興，include三個人就三個人很高興，這張圖告訴你一件事，include愈多人total utility就愈大。他呈現的是一個遞增的函數，但是若取它的marginal的值來看的話，你可以發現，它的marginal utility是遞減的，這是一個non-decreasing的例子，可以看到它的斜率是愈來愈低的，因為每次進來都忽略，所以我們可以看到，這是愈來愈低的，若如果要在上面做，你要用這一條，之後你就可以決定要include多少人進來，這個問題我們證明過，是NP的問題，可是若是我們做一些小手腳，馬上變成polynomial time。

Envelope Function

你呢？用這一條就好了，你用那一條，我們就做一個東西叫作envelope function，這個envelope function不是我們發明的，如果曾經有人做過streaming stabiler，你去看這個，再做VOP的話，它最喜歡用的就是envelope function，那什麼叫envelope function呢？Envelope是信封的意思，envelope function可以把原來的function包起來，這就是envelope function。我只要找到一條envelope function跟你愈貼近，我的效果就會愈好，因為我等一下allocate的時候，不是原本這一條，而是envelope function去allocate，基本上就不是NP了，就馬上從NP變成polynomial time。雖然有點饒舌，但都是可以證明的。一旦做了這件事情以後，你就可以決定要include多少人、要多少resource、utility是怎樣，接下來，你再根據系統所有的available resource來決定，反正每個layer、每個program這種圖全部都畫出來，接下來我再一個一個決定說，現在每個layer、每個program都來看，然後我就來看include第一個user進來時，resource是否用完，所以應該要找哪個user進來？我就找在全部layer和program裡，用resource最少的那個user，把它include進來。

接下來，我就把這個resource剪掉，再來看看，一個user已經放進來了，那我要決定第二個user，第二個user不一定是同一個program，有可能是其他的program或layer，反正我就是用這個方法，就可以把user全部通通都抓出來，抓出來之後，我就把它們分堆。如：這幾個是同一堆的、這幾個是同一個layer的。你把它分完之後，就可以很清楚地看到就是那幾堆需要分配resource，其他的都分不到resource，因為我已經用完了。

這基本上是一個很簡單的idea，可是你不可以直接用在utility上面，你要做一點小手腳。這個小手腳怎麼做呢？很容易，你找一個envelope function，我要serve之前，我不直接碰這一條，我用內插法來決定，畫一條直線，把相交點畫出來，接下來，下一個要serve的user，就用這一點。這是一個很簡單的例子，那如果是平面很多的話，只要把這條線畫起來，其他部分進來時，utility就是用這一點來決定的。

這裡有一個簡單的演算法，complexity是program數、每個program的layer數以及user數乘積的平方，這樣才是polynomial time，雖然complexity還滿高的，但目的達成了。

Simulation and Conclusion

我們除了分析之外，還做了很簡單的simulation study，這不是NS2的，因為我們沒有牽涉到任何TCP或UDP的結構。這裡面有一些假設，我們的burst profile就是剛才看到的，我們有它做normalization，這個就可以滿足我們的要求。這個的倒數，我們把它當成是start time來分。然後，每一個 layer，我們把它切成base layer和enhancement layer，它們都有自己的data rate，基本上，base layer是最高的，愈往上就愈低。還有，每個user的kernel condition會隨著時間變動。我們來看兩種program，一種是有include，就是有一個layer encode，那我們有兩個program可以互相比較，另一個是single layer approach，這一個是為了看看有無layer encode時效果是否比較好。為公平以見，這整個加起來會是1，而utility加總是b。整個layer encode的utility少了兩個，那這個是比較用的，一個是program 1，一個是program 2。那program 1我們故意把它的utility弄得一樣，但實際上應該是不一樣的，這裡只是方便比較用的，這個的目的是要看有無encoding的好處，接下來要來看看這個演算法是不是真的對每個user的channel quarter的好壞，會影響到allocation的量，還有這個program送望遠程度還是會考慮進去，所以你可以看到，一個是沒layer的，一個是有切layer的，然後用的是utility遞減的那一個。你可以看看這個簡單的例子，當resource用愈多的時候，utility都遞增了，它遞增的程度讓它與utility遞減，所以這個其實稍微比它好一點點，這其實是剛剛那個例子，這個只要resource不一樣，你可以看出很明顯的效果。那另外一個是user popularity不一樣，分堆的方式也不一樣，這裡也有兩個部分，藍色的是program 1，program 1就是utility是一樣的，program 2是utility不一樣，是遞減那一個，也就是說，愈高層的layer，它的utility就愈低。可以看一下，X軸是program 1的user個數，那我代過這個simulation時，它user總數是fixed的，接下來，fixed 100個，那再來看說，若program 1的user數是遞增的，就表示program 2的user數是遞減的，這裡可以看到program 1的user遞增，所以在你resource分愈多時，utility值愈高。這裡program 2也是一樣，program 2 user愈多就表示popularity愈高，它分到的resource也愈多。所以這張圖主要是讓你感受一下，user的popularity和utility function它是同樣都會考慮的。

最後，它有某一個極小的balance，因為在做的過程中，紅色的program 1 utility是一樣的，藍色的program 2是遞增的那一個，我們可以看看，一樣是fixed total number of users，所以program 1的user愈多，就表示program 2的user愈少。從中我們可以發現，就算program 1只有10個user，另外一個program有90個人在看，被serve的還有45%，因為你人比較少，所以45%其實是整天都要播，可是你這45%的user是happy的。同理，這個是utility愈高層就愈小那個，你可以看同樣只有10個人的時候，被serve的user數是60%，為什麼呢？基本上它的utility是不太一樣的，所以才會有不一樣的區隔出來。那秀這個是為了讓你看一下，不是說user人很多的時候，resource就通通你，並不會，它也會allocate一些resource給比較少人看的節目，當然，節目愈popular，系統能serve的人就愈多。

看完這些之後，我們這整個project去年的第一部分就是這些，我們會做resource allocation，有fitting之後，我再傳給下一個老師，他是做scheduling的。這個基本上是一個t-based的allocation機制，這本身是一個NP的問題，所以我們弄了一個polynomial time的solution，就是我們剛剛講到的envelope function那一部分。這是一個polynomial time的heuristic。此外，我們方法完全遵守standard operation，也就是說，我們只是在上面做了一些小模組。因為這是資策會贊助的，所以他們希望我們所有的operation不要違背Alifried standard的規定。而且，這不只是WiMAX，只要支援adapted modulation的polling，你從HSPA這種3.5G以上的，這種multicast resource allocation技術都可以用在上面。

剛才講到我們去年做的，那我們現在在做什麼呢？我們現在是extend到LvLAN有mobile LAN的環境，要來做allocation的問題。那你有LvLAN，你就多了一個，那到底要怎麼做呢？你是要直接跟fake station連呢？透過real連呢？這個大概是目前這整個計劃進行的情形。

這些東西我們在今年六月在ICC有報告過，而我們的journal版本目前正在批閱當中。這大概就是我們今天的talk。

Q&A

Q：Bayesian problem有一個標準的作法，就是把它的profit設成任意的utility，處理它載量的大小，就是time slots，這個叫profit basif，然後把它sort一下，把最高的放到方向去下，這樣也是一個很好的heuristic。相對於你用一個envelope把它包起來，事實上它變成一個linear function，linear function到時候也是一樣，那這兩個東西那一個比較好？

A：我沒有比較過這兩者的差別，我可以讓學生再想想看。不過倒是有一個方法，我們現在正在決定要送那一個layer，有點像Bayesian problem那一個要進來。還有一個問題跟這個很接近，我們可以想想看solution，因為有一些做multimedia的老師跟我說，我在user端，我要real-time去compose這些layer，困難度很高。所以有一個方法就是說，我全部都收，我還是切成layer，可是我fake station來決定給layer的resource。那一個好呢？我覺得這個是更貼近目前，可是你在system resource的使用上，也許沒有這個方法好，可是我們這方法complexity還是有點高。

Q：layer跟layer之間，應該有第一個layer才會有第二個layer，這個有negative在……。

A：對，這個有考慮，就是說我們在決定讓那個user進來之前，我們會考慮兩件事情，第一，你是不是utility最高的，第二，你是不是allegeable的。

Q：MPEG有什麼i-frame、p-frame這些，那麼它在每一個layer都有i-frame、p-frame？

A：我只知道它們今天在切layer時，它們的傳輸同步不太一樣，我覺得有可能，不太確定。

Q：你multicasting時，它的transfer protocol怎麼運作？

A：不需要運作，就使用UDP。