基于調(diào)度集合的移動終端聯(lián)合調(diào)度算法

基于調(diào)度集合的移動終端聯(lián)合調(diào)度算法

隨著無線通信技術(shù)的發(fā)展，移動設(shè)備上的支持業(yè)務(wù)變得越來越普遍。例如，3g網(wǎng)絡(luò)不僅支持語音通信，還可以支持?jǐn)?shù)據(jù)、多媒體和其他業(yè)務(wù)。然而，許多移動設(shè)備都是由電池供電的，電池有限的功率極大地影響了各種業(yè)務(wù)的發(fā)展。因此，如何有效利用電池能量，提高終端能耗效率，降低終端能耗已成為無線通信系統(tǒng)設(shè)計的主要目標(biāo)之一。能源消耗效率也是評估系統(tǒng)整體性能的重要指標(biāo)之一。IEEE802.16e是一種新興的寬帶無線接入技術(shù),它以低成本、高帶寬、提供服務(wù)質(zhì)量保證、支持終端移動及IP接入等特點,成為第四代移動通信標(biāo)準(zhǔn)的備選方案之一.802.16e協(xié)議也特別關(guān)注了能耗效率問題,其中定義的休眠模式即為一種降低移動臺(mobilestation,簡稱MS)能耗的機(jī)制.在休眠模式中,MS有兩種狀態(tài):清醒狀態(tài)和休眠狀態(tài).當(dāng)基站(basestation,簡稱BS)和移動臺之間沒有數(shù)據(jù)傳輸時,MS可以進(jìn)入休眠狀態(tài),關(guān)閉某些物理部件(如射頻模塊等)以減小能耗.其中,休眠時間長度由BS和MS通過MOB-SLP_REQ消息和MOB-SLP_RSP消息進(jìn)行協(xié)商.802.16e中的休眠模式被提出以后,迅速成為新的研究熱點,國內(nèi)外專家學(xué)者開始研究IEEE802.16e中的休眠模式及相關(guān)算法,包括對休眠模式的分析、改進(jìn)及休眠參數(shù)選擇等.終端能否進(jìn)入休眠狀態(tài)是由其數(shù)據(jù)傳輸情況決定的,而調(diào)度算法在很大程度上決定了數(shù)據(jù)傳輸情況.例如若調(diào)度算法頻繁地為終端調(diào)度數(shù)據(jù),雖然每次調(diào)度的數(shù)據(jù)量很小,但終端為接收數(shù)據(jù)需要一直處于清醒狀態(tài),不能進(jìn)入休眠,此時休眠模式就不能發(fā)揮作用.因此,休眠模式的省電性能需要通過合理地設(shè)計系統(tǒng)中的調(diào)度算法進(jìn)行優(yōu)化.針對該問題,文獻(xiàn)提出一種降低終端能耗的單播業(yè)務(wù)調(diào)度算法,該算法以虛擬突發(fā)(virtualburst)的方式為MS調(diào)度數(shù)據(jù)包,在不影響其他MS服務(wù)質(zhì)量的前提下,為每個MS一次傳輸盡可能多的數(shù)據(jù),并讓未參與調(diào)度的MS進(jìn)入休眠狀態(tài)以達(dá)到省電的目的.文獻(xiàn)考慮了如何進(jìn)行多播業(yè)務(wù)的調(diào)度以降低終端能耗,旨在解決802.16e網(wǎng)絡(luò)中多播數(shù)據(jù)的傳輸吞吐量與能耗之間的權(quán)衡問題.它首先定義了“多播超幀”的概念,基于“多播超幀”提出了一種多播數(shù)據(jù)的傳輸方法,該方法可以使終端僅在需要接收的多播數(shù)據(jù)的傳輸時隙內(nèi)處于清醒狀態(tài),其他時間可以進(jìn)入休眠,以降低能耗.目前的研究表明,可降低終端能耗的調(diào)度算法的基本思想是以突發(fā)的方法傳輸數(shù)據(jù),即將某一終端的數(shù)據(jù)一次集中地發(fā)送完畢,使得該終端在較長的一段時間內(nèi)不必進(jìn)行數(shù)據(jù)收發(fā),從而可以進(jìn)入休眠,達(dá)到降低終端能耗的目的.此外,由于IEEE802.16e協(xié)議中的業(yè)務(wù)有服務(wù)質(zhì)量(qualityofservice,簡稱QoS)要求,終端的休眠不能影響其上業(yè)務(wù)的服務(wù)質(zhì)量,因此,突發(fā)傳輸方式需要在不影響其他終端服務(wù)質(zhì)量的前提下,盡可能長時間地為某一終端連續(xù)發(fā)送數(shù)據(jù)包.然而,目前的算法都是在考慮終端上只存在單播業(yè)務(wù)或多播業(yè)務(wù)的情況下設(shè)法降低終端能耗,而沒有考慮單播和多播兩種類型的業(yè)務(wù)共存的情況.隨著多媒體應(yīng)用的普及,多播和單播業(yè)務(wù)越來越多地同時存在于一個MS上.此時,若不同時考慮多播業(yè)務(wù)和單播業(yè)務(wù)的傳輸特點,只針對一種業(yè)務(wù)類型設(shè)計調(diào)度算法是不能實現(xiàn)最大化降低終端能耗的,這可以通過下面的例子進(jìn)行簡要說明.圖1給出在不同調(diào)度方式下MS需要接收的數(shù)據(jù)的傳輸時間.MS1,MS2和MS3除了要接收單播數(shù)據(jù)以外,還要接收同一個多播業(yè)務(wù)的數(shù)據(jù),MS4僅接收單播數(shù)據(jù)它們在無數(shù)據(jù)接收時均進(jìn)入休眠狀態(tài).若單播和多播數(shù)據(jù)被孤立地調(diào)度,則MS1,MS2和MS3都需要醒來兩次以分別接收屬于自己的單播數(shù)據(jù)和多播數(shù)據(jù),如圖1(a)所示;若調(diào)度算法能夠綜合考慮單播和多播數(shù)據(jù)的傳輸特點,則可以盡量在多播業(yè)務(wù)傳輸時隙的相鄰時隙內(nèi)為MS1,MS2和MS3調(diào)度單播數(shù)據(jù),如圖1(b)所示,從而MS1,MS2和MS3只需要醒來一次便可以接收完單播數(shù)據(jù)和多播數(shù)據(jù),與圖1(a)相比,減少了MS在清醒狀態(tài)和休眠狀態(tài)之間的轉(zhuǎn)換次數(shù),從而降低了MS在狀態(tài)轉(zhuǎn)換中耗費(fèi)的電量.通過以上分析可知,多播、單播聯(lián)合調(diào)度算法在提高終端能耗效率方面的必要性主要體現(xiàn)在兩個方面:首先,由于所有接收相同多播業(yè)務(wù)的MS都需要在接收該業(yè)務(wù)的時隙內(nèi)醒來,因此,如果一個調(diào)度算法可以充分利用多播數(shù)據(jù)傳輸時隙的相鄰時隙為接收該多播業(yè)務(wù)的MS傳輸單播數(shù)據(jù),將會節(jié)省終端的電量,如圖1所示,其二,多播業(yè)務(wù)的存在給單播數(shù)據(jù)的突發(fā)傳輸方式帶來了限制,突發(fā)長度的確定受多播傳輸模式的影響,因此傳統(tǒng)的針對單播數(shù)據(jù)的突發(fā)調(diào)度算法是不完全適用的.由此可見,多播單播聯(lián)合調(diào)度算法在提高終端能耗效率方面很有必要,但目前在寬帶無線通信領(lǐng)域尚未提出相關(guān)的算法.為此,本文提出一種基于調(diào)度集合的聯(lián)合調(diào)度算法(schedulingsetbasedintegratedscheduling,簡稱SSBIS),該算法首先將所有的MS劃分到單播調(diào)度都集合(unicastschedulingset)或多播調(diào)度集合(multicastschedulingset)中,多播調(diào)度集合中MS的所有單播數(shù)據(jù)均在多播數(shù)據(jù)傳輸?shù)南噜彆r隙內(nèi)調(diào)度;對于單播調(diào)度集合,將根據(jù)由凸優(yōu)化方法求得的使單播調(diào)度集合中MS休眠時間最長的時隙分配方案,基于突發(fā)的方式為MS調(diào)度單播數(shù)據(jù).SSBIS算法的核心思想就是充分利用多播數(shù)據(jù)的傳輸特點,結(jié)合突發(fā)調(diào)度方法,達(dá)到節(jié)省MS電量的目標(biāo).本文第1節(jié)在給定的系統(tǒng)模型下,根據(jù)單播業(yè)務(wù)和多播業(yè)務(wù)的傳輸特點分析調(diào)度算法如何降低終端能耗的問題.第2節(jié)針對該問題給出SSBIS算法的設(shè)計.第3節(jié)對算法進(jìn)行仿真和分析.第4節(jié)進(jìn)行總結(jié).1多播業(yè)務(wù)組ms的能耗本文基于IEEE802.16e無線城域網(wǎng)中點到多點的網(wǎng)絡(luò)架構(gòu),以下行傳輸為例進(jìn)行研究.802.16e標(biāo)準(zhǔn)將下行數(shù)據(jù)業(yè)務(wù)劃分為以下5種類型:UGS,RT-VR,ERT-VR,BE和NRT-VR.其中,UGS,RT-VR和ERT-VR屬于實時業(yè)務(wù),為保證其實時性,若終端上存在這3種類型的業(yè)務(wù),一般不進(jìn)入休眠狀態(tài).因此,本文與大部分研究802.16e中休眠問題的文獻(xiàn)一樣,只討論終端上存在BE和NRT-VR這兩類非實時業(yè)務(wù)的情況.在該情況下,最小數(shù)據(jù)速率是一個簡單、有效的可以保證MS服務(wù)質(zhì)量的參數(shù).基于此,本文采用最小數(shù)據(jù)速率作為MS的QoS要求本文中的帶寬以時隙(timeslot)來衡量,并假設(shè)每個時隙所能傳輸?shù)臄?shù)據(jù)速率對一個MS來說是固定的,用ci表示MSi在每個時隙上所能獲得的數(shù)據(jù)速率.文獻(xiàn)提出的多播傳輸模型可以在多播數(shù)據(jù)吞吐率和終端的能耗效率之間取得很好的折衷,因此,本文采用文獻(xiàn)中的靜態(tài)模型作為多播業(yè)務(wù)的傳輸方式,它提前確定多播業(yè)務(wù)和邏輯廣播信道之間的對應(yīng)關(guān)系.邏輯廣播信道為每一幀中傳輸廣播和多播數(shù)據(jù)的區(qū)域,緊隨前序頭.如圖2所示,多播業(yè)務(wù)#1在邏輯廣播信道#1上傳輸,多播業(yè)務(wù)#2在邏輯廣播信道#2上傳輸,依此類推.假設(shè)系統(tǒng)中存在G個多播業(yè)務(wù),則需要G個邏輯廣播信道,邏輯廣播信道的大小固定,并且每G個連續(xù)的幀組成一個“多播超幀”.根據(jù)MS接收的多播業(yè)務(wù)將MS劃分到對應(yīng)的多播業(yè)務(wù)組中,例如多播業(yè)務(wù)組1中的MS接收多播業(yè)務(wù)#1,依此類推.因此,多播業(yè)務(wù)組j中的MS應(yīng)在邏輯廣播信道#j內(nèi)處于清醒狀態(tài)以接收多播業(yè)務(wù)#j的數(shù)據(jù).在討論MS的能耗問題之前,首先給出以下假設(shè):一個小區(qū)中有M個MS,使用標(biāo)志符i索引(i=1,2,…,M);一個小區(qū)中包含G個不同的多播業(yè)務(wù)組,用j來索引(j=1,2,…,G),本文中一個MS在某一時刻只能屬于一個多播業(yè)務(wù)組;Paw表示處于清醒狀態(tài)的MS在每個時隙上的平均能耗,Ptn表示MS從休眠狀態(tài)轉(zhuǎn)換到清醒狀態(tài)過程的平均能耗,由于MS從清醒狀態(tài)轉(zhuǎn)化到休眠狀態(tài)的能耗及處于休眠狀態(tài)時的能耗很小,因此可以忽略;ni表示MSi為接收單播數(shù)據(jù)而從休眠狀態(tài)轉(zhuǎn)化到清醒狀態(tài)的次數(shù);di表示一個調(diào)度周期內(nèi)分配給MSi的時隙數(shù)量,ri為一個調(diào)度周期后MSi所獲得的數(shù)據(jù)速率;MSi為保證其服務(wù)質(zhì)量的最小數(shù)據(jù)速率要求為Rimin.基于以上分析和假設(shè),一個MS的能耗由其處于清醒狀態(tài)的時間和從休眠狀態(tài)到清醒狀態(tài)的轉(zhuǎn)換次數(shù)來決定.屬于一個多播業(yè)務(wù)組的MS不僅需要在接收單播數(shù)據(jù)時醒來,而且需要在相應(yīng)的邏輯廣播信道中醒來,以接收多播數(shù)據(jù).因此,MSi在一段時間T內(nèi)(T足夠長)的總能耗Pi可以表示為其中,BGj={i:MSi屬于多播業(yè)務(wù)組j}.PMj是多播業(yè)務(wù)組j中的一個MS在T內(nèi)接收該多播業(yè)務(wù)所消耗的能量,mj是接收該多播業(yè)務(wù)所需的從休眠狀態(tài)到清醒狀態(tài)的轉(zhuǎn)換次數(shù),等于時間T內(nèi)邏輯廣播信道#j的數(shù)量.由于本文中多播數(shù)據(jù)傳輸方式是提前確定的,因此,時間T內(nèi),PMj和mj的值固定不變.Di是MSi在時間T內(nèi)除接收多播數(shù)據(jù)的時隙外處于清醒狀態(tài)的時隙數(shù)量.降低MS能耗的調(diào)度算法的目標(biāo)是在保證每個MS服務(wù)質(zhì)量的同時,最小化所有MS的平均能耗(在足夠長的時間T內(nèi)).本文以最小數(shù)據(jù)速率作為MS的服務(wù)質(zhì)量要求,因此,調(diào)度算法的目標(biāo)可以形式化為為獲得最優(yōu)化的結(jié)果,調(diào)度算法應(yīng)該同時考慮多播業(yè)務(wù)和單播業(yè)務(wù)的傳輸特點.基于該思想,本文將在第2節(jié)中闡述解決優(yōu)化問題(2)的調(diào)度算法.2基于波動集的聯(lián)合波動算法ssbis算法2.1多播調(diào)度集合的聯(lián)合調(diào)度算法文獻(xiàn)將MS處于清醒狀態(tài)而未接收數(shù)據(jù)的情形定義為空閑狀態(tài),并且指出MS處于空閑狀態(tài)時是在浪費(fèi)電量.因此,若MS能夠在處于清醒狀態(tài)時一直收發(fā)數(shù)據(jù),一旦無數(shù)據(jù)傳輸則進(jìn)入休眠狀態(tài),便可以避免處于空閑狀態(tài)時的能耗.但由于MS從休眠狀態(tài)轉(zhuǎn)換到清醒狀態(tài)也需要耗電,如果MS處于空閑狀態(tài)的時間比較短,導(dǎo)致狀態(tài)轉(zhuǎn)換的能耗大于空閑狀態(tài)的能耗,則MS不必進(jìn)入休眠狀態(tài).因此,MS進(jìn)入休眠狀態(tài)的條件是MS預(yù)期處于空閑狀態(tài)的能耗大于狀態(tài)轉(zhuǎn)換的能耗,即其中,Pidle代表處于空閑狀態(tài)的MS在每個時隙上的平均能耗,t代表處于空閑狀態(tài)的預(yù)期時間(以時隙衡量).定義Ttn為空閑時間閾值,若處于空閑狀態(tài)的預(yù)期時間大于Ttn,則MS需要進(jìn)入休眠狀態(tài).綜上可得:根據(jù)式(4),本文定義在一個多播超幀內(nèi),邏輯廣播信道#j的相鄰時隙區(qū)間Sj為Sj=(ts-Ttn,ts)∪(te,te+Ttn),其中ts和te分別為邏輯廣播信道#j在該多播超幀內(nèi)的開始時隙和結(jié)束時隙.假設(shè)i∈BGj且ti代表某次基站為MSi發(fā)送單播數(shù)據(jù)的開始時隙.若ti∈Sj,則MSi在本次接收多播數(shù)據(jù)和單播數(shù)據(jù)之間不必進(jìn)入休眠,這是因為MSi預(yù)期處于空閑狀態(tài)的時間在ti和te(或ts)之間,小于Ttn.若MSi每次單播數(shù)據(jù)的傳輸開始時隙均處于Sj內(nèi),則ni=0.在式(1)中,PMj和mj是確定的值,因此Pi僅由Di和ni決定.如果ni=0則通過適當(dāng)?shù)恼{(diào)度策略可以使Di最小,并且最小值接近于傳輸MSi的單播數(shù)據(jù)所需的總時隙數(shù).因此,當(dāng)ni=0時,Pi可以取得最小值.基于以上分析,聯(lián)合調(diào)度算法需要使盡可能多的接收多播數(shù)據(jù)的MS滿足ni=0以降低系統(tǒng)總能耗,不能滿足ni=0條件的接收多播數(shù)據(jù)的MS將與不屬于任何多播業(yè)務(wù)組的MS一起調(diào)度.據(jù)此,本文提出基于調(diào)度集合的聯(lián)合調(diào)度算法(SSBIS),為不同類型的MS分配時隙.其中,調(diào)度集合的定義是:一個調(diào)度集合由將在同一組時隙內(nèi)以相同策略被調(diào)度的多個MS組成.一個MS屬于且僅屬于一個調(diào)度集合.調(diào)度集合分為兩類:多播調(diào)度集合和單播調(diào)度集合.SSBIS算法將系統(tǒng)中所有的MS劃分到一個單播調(diào)度集合Cu和G個多播調(diào)度集合Cj(j=1,2,…,G)中.多播調(diào)度集合Cj由屬于多播業(yè)務(wù)組j且可以在邏輯廣播信道#j的相鄰時隙區(qū)間Sj內(nèi)完成單播數(shù)據(jù)接收的MS組成不屬于任何多播調(diào)度集合的MS組成單播調(diào)度集合Cu.Cj中MS的單播數(shù)據(jù)將在邏輯廣播信道#j的相鄰時隙區(qū)間Sj內(nèi)被調(diào)度完畢,Cu中MS的單播數(shù)據(jù)將在除邏輯廣播信道#j(j=1,2,…,G)及其所有相鄰時隙區(qū)間外的其余時隙內(nèi)被調(diào)度,這些時隙統(tǒng)一定義為Su.圖3給出了Sj,Su和邏輯廣播信道的分布關(guān)系.本文將一個調(diào)度周期定義為一組連續(xù)的時隙,這組時隙包括一個Su、一個邏輯廣播信道及其相鄰時隙區(qū)間.基于以上分析,SSBIS算法需要解決以下兩個主要問題:(a)如何決定MS屬于哪個調(diào)度集合;(b)針對不同類型的調(diào)度集合設(shè)計不同的調(diào)度策略.本文將在第2.2節(jié)和第2.3節(jié)中分別闡述解決問題(a)和問題(b)的方法.2.2多播調(diào)度集合中ms的數(shù)量根據(jù)多播調(diào)度集合Cj的定義,Cj的生成原則是從多播業(yè)務(wù)組j中選擇盡可能多的MS組成,這些MS都能在Sj中調(diào)度完畢且滿足ni=0的條件.因為當(dāng)ni=0時,Pi最小,所以Cj的生成原則可以使最多的MS能耗達(dá)到其最小值.以下將根據(jù)Cj的生成原則設(shè)計一種多播調(diào)度集合的生成方法.假設(shè)i∈BGj,SLi代表一個調(diào)度周期后MSi的最長休眠時間.根據(jù)普遍采用的滑動窗口機(jī)制,SLi的計算方法如下:其中,Lsw代表滑動窗口的大小.本文定義Tj為邏輯廣播信道#j的循環(huán)周期,即一個多播超幀的長度.SLi≥Tj是ni=0的必要條件,因為若SLi<Tj,MSi不僅需要在邏輯廣播信道中醒來接收多播數(shù)據(jù),還需要在邏輯廣播信道#j的循環(huán)周期內(nèi)的某一時間醒來接收單播數(shù)據(jù),ni不為0.因此,基于式(5)可以得到ri的下限:根據(jù)滑動窗口機(jī)制,可以計算出為獲得數(shù)據(jù)傳輸率ri需要為MSi分配的時隙數(shù)di:由式(7)可以看出,di與ri成正比.因此,當(dāng)ri取得最小值,即SLi=Tj時,di最小,其最小值可表示為假設(shè)多播業(yè)務(wù)組j中共有M′個MS,根據(jù)式(8)計算出這M′個MS的di值并按升序排列,得到集合,則在Sj內(nèi)最多能為Kj個MS傳輸數(shù)據(jù),并保證它們的休眠時間等于Tj.下面證明Kj為多播業(yè)務(wù)組j中能夠達(dá)到能耗最小值的MS的最大數(shù)量.證明:假設(shè)存在K′個MS可以在Sj中調(diào)度完畢且K′>Kj.因為,所以K′>MS中至少有一個MSk,dk<(RkminTjLsw)((Lsw-Tj)ck).因為SLk<Tj,MSk必將在邏輯廣播信道#j的循環(huán)周期內(nèi)醒來.因此kn≠0,MSk的能耗沒有達(dá)到最小值.所以,Kj為多播業(yè)務(wù)組j中能夠達(dá)到能耗最小值的MS的最大數(shù)量.根據(jù)以上分析,本文提出的調(diào)度集合劃分方法是對于每一個多播業(yè)務(wù)組j,根據(jù)式(8)計算出其中所有MS的di值并按升序排列,計算Kj并選擇排列中前Kj個MS組成多播調(diào)度集合Cj.當(dāng)所有的多播調(diào)度集合生成后,剩余的未屬于任何多播調(diào)度集合的MS將組成單播調(diào)度集合Cu.一旦多播調(diào)度集合Cj生成,則需要為Cj中的每個MS分配的時隙數(shù)也隨之確定.根據(jù)每個MS應(yīng)分配的時隙數(shù),在Sj上為其連續(xù)分配時隙,則可完成對多播調(diào)度集合中MS的單播業(yè)務(wù)的調(diào)度.由以上分析可知,多播調(diào)度集合中MS的數(shù)量越多,能耗達(dá)到其最小值的MS就越多,系統(tǒng)的能耗效率也就越高.多播調(diào)度集合中MS的數(shù)量是由多播業(yè)務(wù)與單播業(yè)務(wù)的共存情況決定的,包括多播業(yè)務(wù)與單播業(yè)務(wù)的比例及在時間上的分布.其中,多播業(yè)務(wù)在系統(tǒng)中所占的比例可以通過多播業(yè)務(wù)的數(shù)量及接收每個多播業(yè)務(wù)的MS個數(shù)來體現(xiàn),若多播業(yè)務(wù)的數(shù)量較少或接收每個多播業(yè)務(wù)的MS個數(shù)較少,則將造成多播調(diào)度集合中MS的數(shù)量較少;多播業(yè)務(wù)與單播業(yè)務(wù)在時間上的分布主要體現(xiàn)在MS是否可以同時接收兩種業(yè)務(wù),若由于MS上單播業(yè)務(wù)的服務(wù)質(zhì)量要求或多播業(yè)務(wù)與單播業(yè)務(wù)未同時存在,使得MS無法同時接收兩種業(yè)務(wù),則MS無法劃入多播調(diào)度集合,從而減少了多播調(diào)度集合中MS的數(shù)量.多播調(diào)度集合中MS數(shù)量的減少將降低相鄰時隙區(qū)間調(diào)度方法帶來的省電效果.同時,多播調(diào)度集合中MS數(shù)量的減少將使單播調(diào)度集合中MS的數(shù)量增加.因此,為保證SSBIS算法在多播調(diào)度集合中MS數(shù)量較少時也能達(dá)到較高的能耗效率,本文也需要針對單播調(diào)度集合設(shè)計一種省電的調(diào)度算法,盡量降低單播調(diào)度集合中MS的總能耗.第2.3節(jié)將針對單播調(diào)度集合Cu設(shè)計一種基于最長休眠時間的調(diào)度算法.2.3基于lsdb調(diào)度的ms恢復(fù)算法LSDB算法的設(shè)計思想是在多播傳輸模式的限制下,充分利用突發(fā)傳輸?shù)乃枷?使Cu中所有MS的總休眠時間最長,從而達(dá)到總能耗最小.itawake代表MSi為保證其服務(wù)質(zhì)量最晚應(yīng)該醒來接收數(shù)據(jù)的時間,可以通過SLi來計算.LSDB算法為Cu中每個MS記錄該時間,并在每次為MSi分配完時隙后更新其itawake值.根據(jù)itawake可判斷MSi是否需要在當(dāng)前Su內(nèi)調(diào)度.假設(shè)在當(dāng)前Su中,MSi(i=1,…,K)需要被調(diào)度,則調(diào)度算法的目標(biāo)就是在保證這K個MS的服務(wù)質(zhì)量的同時,使它們的總能耗最小.在突發(fā)傳輸方式下,這K個MS的總休眠時間最長,則它們的總能耗最小.因此,該問題可以表示為如下優(yōu)化問題:其中,Tc是當(dāng)前Su的長度,Lmin為MS休眠的最小時間,即緊隨當(dāng)前Su的邏輯廣播信道#j及其相鄰時隙區(qū)間Sj的長度之和.這是因為該邏輯廣播信道及其相鄰時隙區(qū)間中的時隙不能分配給Cu中的MSi,因此,MSi的休眠時間必須大于Lmin才能保證其服務(wù)質(zhì)量,這就是條件(9c)的含義.目標(biāo)函數(shù)(9a)代表調(diào)度的目標(biāo)是使MS(i=1,…,K)的總休眠時間最長.條件(9b)的意義是保證本次調(diào)度為這K個MS分配的時隙總數(shù)等于當(dāng)前Su的長度.根據(jù)式(7),條件(9b)可以用ri表示如下:目標(biāo)函數(shù)(9a)的等價函數(shù)為可以證明,以(9a′)為目標(biāo)函數(shù)的非線性優(yōu)化問題(9)是一個凸規(guī)劃問題(決策變量為r1,r2,…,rK),這類問題可以通過內(nèi)點法有效地解決.為使用內(nèi)點法,需要先尋找優(yōu)化問題(9)的一個嚴(yán)格可行解.設(shè)其中,bi=(RiminLsw)(Lsw-Lmin),δ=(Tc?ci)Lsw+∑Ki=1(Rimin-bi)K.如果δ≤0,則表示系統(tǒng)已經(jīng)超負(fù)荷,不能滿足每個MS的服務(wù)質(zhì)量要求,此時問題(9)不存在可行解,這種情況可以通過系統(tǒng)的接納控制等機(jī)制避免.除此異常情況以外,r(0)始終是問題(9)的嚴(yán)格可行解,因此可以基于r(0)利用內(nèi)點法求得優(yōu)化問題(9)的最優(yōu)解r*.利用式(7)可以將r*轉(zhuǎn)換為在本次調(diào)度中需要分配給MS的時隙數(shù)di(i=1,…,K).但依此求出的di可能不是整數(shù),因此需要將di取整,可直接采用四舍五入的方法.di取整后,若∑Ki=1di>Tc,則本算法通過減少分配給休眠時間最長的MS的時隙數(shù)來滿足條件(9b),否則直接將取整后的di(i=1,…,K)作為最終的時隙分配結(jié)果.基于突發(fā)傳輸思想和上述為MS應(yīng)分配時隙數(shù)的計算方法,給出在一個Su中應(yīng)用LSDB調(diào)度算法的步驟:1)從Cu中選擇需要在當(dāng)前Su內(nèi)調(diào)度的MS,假設(shè)選擇結(jié)果為MSi(i=1,…,K).hi代表本次調(diào)度中已經(jīng)為MSi分配的時隙數(shù),n代表已經(jīng)完成調(diào)度的MS的數(shù)量,Tu代表當(dāng)前調(diào)度時隙.在調(diào)度開始時,n=0,hi=0,Tu為Su的開始時隙.2)計算優(yōu)化問題(9)的最優(yōu)解r*,根據(jù)r*計算di(i=1,…,K),并在限制條件(9b)和(9c)下將di(i=1,…,K)取整.3)選擇當(dāng)前未完成調(diào)度的MS中最晚醒來時間最小的MS,設(shè)為MSj.4)如果hj≥dj,則已經(jīng)完成對MSj的調(diào)度,更新tjawake并將MSj置于休眠狀態(tài),然后執(zhí)行步驟7);否則執(zhí)行步驟5).5)如果存在tjawake(i≠j)小于Tu,則將當(dāng)前時隙分配給MSi,設(shè)置hi=hi+1,Tu=Tu+1,并更新tjawake,然后執(zhí)行步驟4);否則執(zhí)行步驟6).6)將當(dāng)前時隙分配給MSj,設(shè)置hj=hj+1,Tu=Tu+1,然后執(zhí)行步驟4)進(jìn)行下一個時隙的分配.7)n=n+1.如果n=K,則本次調(diào)度完成,算法結(jié)束;否則執(zhí)行步驟3).此外,若系統(tǒng)中沒有多播業(yè)務(wù),則所有的MS均屬于單播調(diào)度集合,仍可以采用LSDB算法來降低系統(tǒng)能耗此時,優(yōu)化問題(9)將不包括條件(9c),Tc為系統(tǒng)參數(shù).其解決方法可以較容易地獲得,這里不再贅述.2.4ssbis算法SSBIS算法的核心思想是將系統(tǒng)中所有的MS劃分到不同的多播調(diào)度集合和單播調(diào)度集合中,針對多播調(diào)度集合中的MS在相鄰時隙區(qū)間內(nèi)進(jìn)行調(diào)度,針對單播調(diào)度集合中的MS采用LSDB算法進(jìn)行調(diào)度.基于此核心思想,給出完整的SSBIS算法如下:1)在調(diào)度開始時,首先根據(jù)第2.2節(jié)給出的調(diào)度集合劃分方法將所有MS劃分到多播調(diào)度集合Cj(j=1,2,…,G)或單播調(diào)度集合Cu中,并為Cj(j=1,2,…,G)確定調(diào)度方法Aj,Aj為Cj中的每個MS分配相鄰時隙區(qū)間Sj上連續(xù)的時隙,應(yīng)分配的時隙數(shù)量根據(jù)式(8)計算.除非多播業(yè)務(wù)組j發(fā)生改變,否則Aj始終保持不變.2)對于每個調(diào)度周期,如果t∈Su,則根據(jù)LSDB調(diào)度算法為Cu中的MS分配時隙如果t∈Sj,則采用調(diào)度方法Aj為Cj中的MS分配時隙;否則調(diào)度多播業(yè)務(wù)#j的數(shù)據(jù).其中,t代表當(dāng)前調(diào)度時隙每個時隙分配完畢后則指向下一個時隙.3多播業(yè)務(wù)仿真本節(jié)將通過仿真實驗來驗證SSBIS算法的性能及多播業(yè)務(wù)傳輸情況對算法的影響.仿真系統(tǒng)基于IEEE802.16e協(xié)議,包括一個BS和多個MS組成的一個小區(qū).無線帶寬為5Mbps,幀長為5ms,每幀包含200個時隙仿真中,終端上同時存在多播業(yè)務(wù)和有最小數(shù)據(jù)速率要求的單播數(shù)據(jù)業(yè)務(wù),單播數(shù)據(jù)的到達(dá)遵從泊松分布,MS上單播數(shù)據(jù)業(yè)務(wù)的最小數(shù)據(jù)速率要求為10kbps~40kbps.默認(rèn)情況下,每個多播業(yè)務(wù)組包括4個MS.根據(jù)文獻(xiàn)的測量和計算結(jié)果,本仿真實驗中假設(shè)MS處于空閑狀態(tài)、清醒狀態(tài)和從休眠狀態(tài)轉(zhuǎn)換到清醒狀態(tài)這3種情況下在每個時隙上的平均能耗相等,且每次狀態(tài)轉(zhuǎn)換將消耗兩個時隙單位的能量.3.1相鄰時隙對能耗效率的影響本文利用文獻(xiàn)中定義的AEE(averageenergyefficiency)來衡量能耗效率,AEE是終端用于數(shù)據(jù)傳輸?shù)哪芎呐c總能耗的比值.圖4給出SSBIS算法和LVBF算法在系統(tǒng)中存在不同數(shù)量的MS情況下的AEE值(此時系統(tǒng)中存在2個多播業(yè)務(wù)組).從圖4可以看出,在能耗效率方面,SSBIS算法與LVBF算法相比提高20%以上這主要存在3個原因:一是SSBIS算法充分利用了邏輯廣播信道的相鄰時隙,減少了MS狀態(tài)轉(zhuǎn)換的次數(shù),因此SSBIS算法中狀態(tài)轉(zhuǎn)換次數(shù)小于LVBF算法;二是在SSBIS算法中,一旦MS的預(yù)期空閑時間達(dá)到一定閾值,就進(jìn)入休眠狀態(tài),而LVBF算法中總是有一些MS長時間處于空閑狀態(tài),因此,SSBIS算法相對于LVBF算法減少了MS的空閑時間;三是SSBIS算法通過凸優(yōu)化方法求得的時隙分配方案使單播調(diào)度集合中所有MS的總休眠時間長于采用LVBF算法的休眠時間.以上3個原因是由SSBIS算法的兩個主要組成部分,即針對多播調(diào)度集合的相鄰時隙區(qū)間調(diào)度方法及針對單播調(diào)度集合的LSDB算法帶來的.圖5給出利用相鄰時隙區(qū)間調(diào)度多播調(diào)度集合中MS的數(shù)據(jù)及采用LSDB算法分別為能耗效率帶來的提高(與LVBF算法相比).在該仿真實驗中,為分別得出這兩部分對能耗效率的影響,本文首先為單播調(diào)度集合采用LVBF算法,只利用相鄰時隙區(qū)間調(diào)度多播調(diào)度集合中MS的數(shù)據(jù),得到其為能耗效率帶來的提高;然后為單播調(diào)度集合采用LSDB算法,從而得到SSBIS算法相對于LVBF算法在能耗效率方面總的提高值,兩個提高值之差即為LSDB算法為能耗效率帶來的提高如圖5所示,利用相鄰時隙區(qū)間調(diào)度多播調(diào)度集合中MS的數(shù)據(jù)對能耗效率的提高約占SSBIS算法總的能耗效率提高量的40%~60%.3.2多播調(diào)度集合中ms的增加單播業(yè)務(wù)與多播業(yè)務(wù)的不同共存情況將決定多播調(diào)度集合的劃分,從而影響SSBIS算法的能耗效率.本質(zhì)上,單播業(yè)務(wù)與多播業(yè)務(wù)的共存情況是通過系統(tǒng)中多播業(yè)務(wù)的數(shù)量(即多播業(yè)務(wù)組數(shù)量)、接收每個多播業(yè)務(wù)的MS個數(shù)及MS對單播業(yè)務(wù)的最小數(shù)據(jù)速率要求來決定多播調(diào)度集合劃分的.例如,系統(tǒng)中多播業(yè)務(wù)組的個數(shù)一定,而接收每個多播業(yè)務(wù)的MS個數(shù)較少,從而造成每個多播調(diào)度集合中的MS個數(shù)較少,則可能無法充分利用相鄰時隙區(qū)間進(jìn)行調(diào)度,限制了SSBIS算法對能耗效率的提高程度.下面將通過仿真實驗驗證以上3個因素對SSBIS算法能耗效率的影響.圖6給出了系統(tǒng)中多播業(yè)務(wù)組數(shù)量對SSBIS算法能耗效率的影響.該實驗場景下共存在32個MS.由圖6可知,隨著系統(tǒng)中多播業(yè)務(wù)組個數(shù)的增加,AEE值基本呈上升趨勢.這是由于,當(dāng)系統(tǒng)中存在更多的多播業(yè)務(wù)組時(但未超過系統(tǒng)容量),邏輯廣播信道數(shù)量增加,將會有更多的MS可以在邏輯廣播信道的相鄰時隙區(qū)間內(nèi)完成調(diào)度,達(dá)到其最小能耗值,即多播調(diào)度集合中MS增多,從而提高了系統(tǒng)的能耗效率.但這種趨勢不是絕對的,如圖6所示中,當(dāng)多播業(yè)務(wù)組個數(shù)為5時,其AEE值反而小于多播業(yè)務(wù)組個數(shù)為4時的值.原因是,隨著多播業(yè)務(wù)組個數(shù)的增加和邏輯廣播信道數(shù)量的增多,超幀長度增大(即Tj變大),根據(jù)式(8),相鄰時隙區(qū)間內(nèi)需要分配給每個MS的時隙數(shù)增加,可能導(dǎo)致能夠在相鄰時隙區(qū)間內(nèi)完成調(diào)度的MS數(shù)量減少.在此仿真實驗中,當(dāng)多播業(yè)務(wù)組個數(shù)為4時,每個相鄰時隙區(qū)間可以調(diào)度3個MS,因此所有多播調(diào)度集合中MS的總數(shù)為12;而當(dāng)多播業(yè)務(wù)組個數(shù)為5時,每個相鄰時隙區(qū)間只能調(diào)度2個MS,則所有多播調(diào)度集合中MS的總數(shù)為10,因此,其AEE值小于多播業(yè)務(wù)組個數(shù)為4時的值.同理,隨著多播業(yè)務(wù)組個數(shù)的增加,其AEE值的增加幅度將減小,這由圖7可以清楚地看出:多播業(yè)務(wù)組個數(shù)為2(G=2)時的AEE值與多播業(yè)務(wù)組個數(shù)為4(G=4)時的AEE值之差、多播業(yè)務(wù)組個數(shù)為4時與多播業(yè)務(wù)組個數(shù)為6(G=6)時的AEE值之差、多播業(yè)務(wù)組個數(shù)為6時與多播業(yè)務(wù)組個數(shù)為8(G=8)時的AEE值之差依次減小.圖8給出在多播業(yè)務(wù)組個數(shù)不變、而接收每個多播業(yè)務(wù)的MS個數(shù)發(fā)生變化時,SSBIS算法的性能變化場景1中每個多播業(yè)務(wù)組包括2個MS,場景2中每個多播業(yè)務(wù)組包括4個MS,場景1和場景2中均存在2個多播業(yè)務(wù)組.由圖8可知,當(dāng)在系統(tǒng)中存在數(shù)量相同的MS時,場景2中AEE值總是高于場景1,這同樣是由多播調(diào)度集合中MS的個數(shù)不同所導(dǎo)致.在多播業(yè)務(wù)組個數(shù)和MS的服務(wù)質(zhì)量要求確定的情況下,每個邏輯廣播信道的相鄰時隙區(qū)間可調(diào)度的MS數(shù)量也已確定,若某多播業(yè)務(wù)組中MS的個數(shù)小于該數(shù)量,則對應(yīng)多播調(diào)度集合中MS的數(shù)量將不能達(dá)到最大值,使足夠多的MS達(dá)到其能耗最小值.例如,該仿真中,每個邏輯廣播信道的相鄰時隙區(qū)間最多可以調(diào)度4個MS,但場景1中接收每個多播業(yè)務(wù)的MS只有2個,因此不能充分利用相鄰時隙區(qū)間,導(dǎo)致其能耗效率始終低于場景2.在該仿真中,場景1與場景2中MS的最小數(shù)據(jù)速率要求相同若MS的最小數(shù)據(jù)速率要求不同,則即使兩個場景中多播業(yè)務(wù)組包含的MS個數(shù)相同,可在邏輯廣播信道的相鄰時隙區(qū)間內(nèi)完成調(diào)度