閆中江，李 波，高 田，左曉亞

（西北工業(yè)大學(xué)電子信息學(xué)院，陜西西安 710072）

一種公平的路邊基站下行業(yè)務(wù)調(diào)度算法

閆中江，李 波，高 田，左曉亞

（西北工業(yè)大學(xué)電子信息學(xué)院，陜西西安 710072）

針對車輛網(wǎng)絡(luò)中現(xiàn)有路邊基站下行業(yè)務(wù)調(diào)度算法公平性差的問題，提出了一種公平的基于網(wǎng)絡(luò)流的路邊基站下行業(yè)務(wù)調(diào)度算法.首先，建立包含車輛節(jié)點(diǎn)和時(shí)隙節(jié)點(diǎn)的二部圖，如果在給定時(shí)隙內(nèi)車輛節(jié)點(diǎn)位于路邊基站的通信覆蓋范圍內(nèi)，則在該車輛節(jié)點(diǎn)與對應(yīng)的時(shí)隙節(jié)點(diǎn)之間添加邊；然后，在二部圖的基礎(chǔ)上添加虛擬的源節(jié)點(diǎn)和目的節(jié)點(diǎn)，建立網(wǎng)絡(luò)流圖；最后，通過計(jì)算網(wǎng)絡(luò)流圖的最小花費(fèi)最大流，得到了一種公平的路邊基站下行業(yè)務(wù)調(diào)度策略.仿真結(jié)果表明，在保證最大化車輛業(yè)務(wù)請求的情況下，與現(xiàn)有算法相比，這種算法提高了車輛之間業(yè)務(wù)請求的公平性，在offline情況下公平性提高了約116.4%，在online情況下公平性提高了約25.9%.

車輛網(wǎng)絡(luò)；業(yè)務(wù)調(diào)度；公平性；網(wǎng)絡(luò)流

路邊基站（Road Side Unit，RSU）是車輛網(wǎng)絡(luò)中為過往車輛提供信息服務(wù)的基礎(chǔ)設(shè)施.為克服有線電力部署的局限性，采用太陽能、風(fēng)能等形式的電池供電，成為車輛網(wǎng)絡(luò)中路邊基站的主要工作方式之一［1-2］.因此，在滿足車輛業(yè)務(wù)請求的情況下，設(shè)計(jì)低能耗、公平的路邊基站下行業(yè)務(wù)調(diào)度算法具有重要意義［3-5］.路邊基站的能耗主要由路邊基站數(shù)據(jù)傳輸能耗組成.文獻(xiàn)［1］提出了一種啟發(fā)式的Nearest-Fastest業(yè)務(wù)調(diào)度算法，降低了路邊基站數(shù)據(jù)傳輸能耗，但卻沒有考慮最大化車輛業(yè)務(wù)請求的問題；文獻(xiàn)［2］提出采用網(wǎng)絡(luò)流的方法，在最大化車輛業(yè)務(wù)請求的情況下，降低了路邊基站數(shù)據(jù)傳輸能耗，但卻沒有考慮車輛之間的公平性問題.

當(dāng)車輛業(yè)務(wù)請求較少時(shí)，每個(gè)車輛的業(yè)務(wù)請求都能被成功服務(wù)，不需要考慮車輛間的公平性問題.然而，當(dāng)車輛業(yè)務(wù)請求較多時(shí)，則可能會出現(xiàn)部分車輛的業(yè)務(wù)請求無法得到服務(wù)的情況，即出現(xiàn)業(yè)務(wù)調(diào)度不公平的問題.在城市或部分高速公路場景中，車流量大、車輛業(yè)務(wù)請求多，所有這些業(yè)務(wù)請求均需路邊基站服務(wù)，因此如何在最大化總的車輛業(yè)務(wù)請求的情況下，保證每個(gè)車輛的業(yè)務(wù)請求都能夠得到公平調(diào)度，同時(shí)降低路邊基站的數(shù)據(jù)傳輸能耗，成為一個(gè)亟待解決的問題.

筆者提出了一種基于網(wǎng)絡(luò)流的業(yè)務(wù)調(diào)度算法，在保證最大化車輛業(yè)務(wù)請求的情況下，提高了車輛之間業(yè)務(wù)調(diào)度的公平性.

1 系統(tǒng)模型

設(shè)有1個(gè)路邊基站被部署在高速公路上，為過往車輛提供業(yè)務(wù)請求服務(wù).路邊基站只有一個(gè)無線收發(fā)機(jī)，在任意時(shí)隙t，路邊基站只能與一個(gè)車輛進(jìn)行通信.每個(gè)進(jìn)入路邊基站傳輸覆蓋區(qū)域的車輛，在與路邊基站建立連接時(shí)都向路邊基站提出業(yè)務(wù)請求；路邊基站根據(jù)其傳輸覆蓋區(qū)域內(nèi)車輛總的業(yè)務(wù)請求，做出下行業(yè)務(wù)調(diào)度傳輸決策，最大化地滿足車輛的業(yè)務(wù)請求，并同時(shí)保證車輛間的公平性，降低路邊基站數(shù)據(jù)傳輸能耗.

設(shè)車輛的隨機(jī)到達(dá)過程是密度為λ的泊松過程，在時(shí)間段T內(nèi)共有N輛車經(jīng)過路邊基站，其中時(shí)間段T=｛t1，t2，…，tM｝，表示時(shí)隙集合.令V= ｛v1（q1，s1），v2（q2，s2），…，vN（qN，sN）｝，表示過往車輛集合，其中qi表示車輛vi的請求，si表示車輛vi的速度，1≤i≤N.令di，j表示車輛vi與路邊基站在時(shí)刻tj的距離，1≤i≤N，1≤j≤M，則由無線信號的自由空間衰弱模型可得，為使得車輛vi成功接收路邊基站數(shù)據(jù)，路邊基站所需的發(fā)送功率為

其中，Rmin（Rmax）為路邊基站與車輛之間的最?。ㄗ畲螅┚嚯x，P0（d0）為參考功率（距離），ρ為擴(kuò)展因子，α為路徑衰弱指數(shù).因此，在時(shí)隙t內(nèi)，路邊基站所消耗的能量為

其中，γ=τρP0dα0.

設(shè)路邊基站能夠?qū)⒚總€(gè)時(shí)隙獨(dú)立地分配給不同的車輛.當(dāng)時(shí)隙tj被分配給車輛vi時(shí)，路邊基站將花費(fèi)Ei，j的能量，且車輛vi一個(gè)單位的業(yè)務(wù)請求將被滿足.定義布爾值變量Bi，j表示時(shí)隙tj是否被分配給車輛vi，表示為

則B=｛Bi，j|1≤i≤N，1≤j≤M｝，為路邊基站所確定的對應(yīng)時(shí)隙集合T的業(yè)務(wù)調(diào)度策略.

（i）最大化總的車輛業(yè)務(wù)請求.定義車輛業(yè)務(wù)請求滿足差，則該目標(biāo)等價(jià)于

令S2為求解式（5）所得的業(yè)務(wù)調(diào)度策略集，S2?S1.在此基礎(chǔ)上進(jìn)一步地最小化路邊基站進(jìn)行業(yè)務(wù)傳輸所花費(fèi)的能量.

（iii）最小化路邊基站數(shù)據(jù)傳輸能耗.在求得式（4）～（5）業(yè)務(wù)調(diào)度策略的基礎(chǔ)上，該目標(biāo)為

由于路邊基站的主要作用就是為過往車輛提供信息服務(wù)，因此最大化地滿足車輛請求（即式（4））的優(yōu)先級最高，之后再進(jìn)一步地最大化業(yè)務(wù)調(diào)度的公平性（即式（5）），最后一步是最小化路邊基站數(shù)據(jù)傳輸?shù)哪芎模词剑?）），則具有較低的優(yōu)先級.

在不同的場景下，筆者所提出的問題具有不同的形式.當(dāng)每個(gè)車輛的請求較少，并且所有的車輛請求都能夠被滿足時(shí)，式（4）～（5）的最優(yōu)值為零，式（4）～（6）退化為最小化路邊基站能耗問題（即式（6））.該最小化路邊基站能耗的問題可以采用基于網(wǎng)絡(luò)流的方法得到最優(yōu)解［2］.然而，當(dāng)車輛請求較多，存在部分車輛的請求不能夠被滿足的情況時(shí)，文獻(xiàn)［2］則沒有考慮車輛之間的公平性問題，不能得到公平性的最優(yōu)調(diào)度策略.因此，筆者將著重研究當(dāng)車輛請求較多、存在部分車輛請求不能被滿足情況時(shí)，如何公平地服務(wù)車輛請求、并同時(shí)最小化路邊基站能耗的問題.

2 基于網(wǎng)絡(luò)流的公平業(yè)務(wù)調(diào)度算法

一般來說，多步最優(yōu)化問題（比如式（4）～（6））的求解非常困難.因?yàn)楹罄m(xù)步驟的最優(yōu)化問題的求解是基于前面問題的求解.比如，需要首先求出式（4）的所有最優(yōu)解之后才能求出式（5）的最優(yōu)解；接著，求出式（5）的所有最優(yōu)解之后才能求出式（6）的最優(yōu)解.筆者提出一種基于網(wǎng)絡(luò)流的公平業(yè)務(wù)調(diào)度算法，可以一次性地求解該多步最優(yōu)化問題（即式（4）～（6）），極大地降低了問題的求解復(fù)雜度.

2.1算法描述

圖1給出了筆者所提出的網(wǎng)絡(luò)流算法中所采用的二部圖與網(wǎng)絡(luò)流圖.基于網(wǎng)絡(luò)流的公平業(yè)務(wù)調(diào)度算法的偽代碼如下:

圖1　二部圖與網(wǎng)絡(luò)流圖

（1）對于每一條連接S與vi的邊e（S，vi），設(shè)置邊的容量a（S，vi）=qi，其物理意義是:保證為車輛vi所分配的時(shí)隙總數(shù)不超過車輛vi的請求數(shù)qi.設(shè)置邊的花費(fèi)c（S，vi）=ri2Cmax，其中Cmax是路邊基站最大傳輸能耗的倍數(shù)，其物理意義是:最大化車輛之間業(yè)務(wù)請求的公平性Jain因子.

（2）對于每一條連接vi與tj的邊e（vi，tj），設(shè)置邊的容量a（vi，tj）=1，其物理意義是:每個(gè)時(shí)隙路邊基站僅能滿足車輛vi一個(gè)單位的請求.設(shè)置邊的花費(fèi)c（vi，tj）=Ei，j，其物理意義是:如果路邊基站在時(shí)隙tj給車輛vi傳輸數(shù)據(jù)，則將需要花費(fèi)Ei，j的能量.

（3）對于每一條連接tj與D的邊e（tj，D），設(shè)置邊的容量a（tj，D）=1，其物理意義是:每個(gè)時(shí)隙路邊基站僅能傳輸一個(gè)單位的信息.設(shè)置邊的花費(fèi)c（tj，D）=0，其物理意義是:該邊沒有花費(fèi).

至此，網(wǎng)絡(luò)流圖Gf構(gòu)建結(jié)束.通過在Gf上運(yùn)行典型的最小花費(fèi)最大流算法，比如Push-relabel算法［7］，將可以計(jì)算出圖Gf對應(yīng)的最小花費(fèi)最大流F.如果在所得的最小花費(fèi)最大流F中，邊e（vi，tj）的流不為零，則表示路邊基站應(yīng)該將時(shí)隙tj分配給車輛vi，即對應(yīng)的布爾值變量Bi，j=1.

2.2online數(shù)據(jù)傳輸決策討論

上節(jié)給出了在已知所有時(shí)隙以及所有到達(dá)車輛的情況下（即offline的情況［2］），計(jì)算公平的路邊基站業(yè)務(wù)調(diào)度問題的算法.需要指出的是，該算法同樣適用于在未知所有時(shí)隙以及所有到達(dá)車輛的情況（即online的情況［2］）.下面討論筆者所提出的算法如何應(yīng)用到online的情況.

首先，當(dāng)?shù)?輛車v1進(jìn)入路邊基站的傳輸覆蓋范圍時(shí)，使用筆者所提出的算法，即可為車輛v1計(jì)算出一個(gè)最小化路邊基站能耗的業(yè)務(wù)調(diào)度算法（因?yàn)榇藭r(shí)只有一輛車，故最大化公平性Jain因子（式（5））不存在）.此時(shí)，車輛節(jié)點(diǎn)集V′=｛v1｝，時(shí)隙節(jié)點(diǎn)集T′=｛t1，t2，…，tM′｝，其中M′=2Rmaxs1，s1為車輛的恒定速率.其他部分參照基于網(wǎng)絡(luò)流的公平業(yè)務(wù)調(diào)度算法.

設(shè)在時(shí)隙tj，一個(gè)新的車輛vi到達(dá)并進(jìn)入到路邊基站的數(shù)據(jù)傳輸區(qū)域.設(shè)此時(shí)在路邊基站的數(shù)據(jù)傳輸區(qū)域內(nèi)，同時(shí)還存在著N′個(gè)車輛正在被路邊基站服務(wù).不管現(xiàn)有的業(yè)務(wù)調(diào)度決策是否已經(jīng)被執(zhí)行結(jié)束，筆者所提出的基于網(wǎng)絡(luò)流的公平業(yè)務(wù)調(diào)度算法將被重新調(diào)用，并計(jì)算新的業(yè)務(wù)調(diào)度決策.此時(shí)，節(jié)點(diǎn)集V′=｛v1，v2，…，vN′｝，時(shí)隙節(jié)點(diǎn)集T′=｛tj，tj+1，…，tj+M′｝，其中tj+M′為V′中最后一個(gè)車輛離開路邊基站數(shù)據(jù)傳輸區(qū)域的時(shí)隙.其他部分參照基于網(wǎng)絡(luò)流的公平業(yè)務(wù)調(diào)度算法.

當(dāng)新的數(shù)據(jù)傳輸決策被計(jì)算出來之后，路邊基站將更新并執(zhí)行新的數(shù)據(jù)傳輸決策.在online情況下，每當(dāng)有新的車輛到達(dá)，路邊基站都將根據(jù)當(dāng)前車輛的情況，重新計(jì)算并執(zhí)行新的數(shù)據(jù)傳輸決策.

2.3算法的計(jì)算復(fù)雜度及算法可行性討論

筆者所提算法的計(jì)算復(fù)雜度取決于所使用的Push-relabel算法的復(fù)雜度，而Push-relabel算法的復(fù)雜度為O（V2E ）［7］，其中V 為網(wǎng)絡(luò)流圖中節(jié)點(diǎn)的個(gè)數(shù)，E 為網(wǎng)絡(luò)流圖中邊的個(gè)數(shù).文中，在最壞情況下，V=2+N+M，而E=N+M+NM，因此算法的計(jì)算復(fù)雜度為O （max（N3，M3））.

文獻(xiàn)［8］提出了一種分層的車載容遲網(wǎng)絡(luò)架構(gòu)，其中控制層面（BSC）負(fù)責(zé)完成車輛注冊、關(guān)聯(lián)等，并以較大的通信半徑、較低的數(shù)據(jù)傳輸速率，在車輛與路邊基站進(jìn)行數(shù)據(jù)通信之前建立連接，數(shù)據(jù)層面（BAD）則以較小的通信半徑、較大的數(shù)據(jù)傳輸速率在車輛進(jìn)入到BAD區(qū)域時(shí)才開始進(jìn)行數(shù)據(jù)傳輸.假設(shè)BSC半徑區(qū)域?yàn)?00 m，BAD區(qū)域半徑為200 m，車輛行駛速度為120 km/s，則車輛在進(jìn)入BSC后而未進(jìn)入BAD前的時(shí)間為7.8 s；設(shè)車輛到達(dá)密度λ=0.1輛/秒，時(shí)隙長度t=0.01 s，則在BAD區(qū)域內(nèi)平均有3輛車，總的時(shí)隙個(gè)數(shù)M=1.2×103；設(shè)路邊基站的CPU時(shí)鐘頻率為1 GHz，則完成O（max（N3，M3））的計(jì)算平均需要1 s（遠(yuǎn)小于7.8 s），因此筆者所提出的算法是可行的.

3 仿真結(jié)果

總的車輛請求信息被滿足的個(gè)數(shù)、路邊基站總的能耗以及業(yè)務(wù)調(diào)度決策的公平性是衡量業(yè)務(wù)調(diào)度決策性能的重要指標(biāo).將筆者所提出的算法與文獻(xiàn)［2］中的算法進(jìn)行了仿真比較，同時(shí)比較了offline和online兩種情況.

設(shè)總的仿真時(shí)間Tsimu=150 s，車輛到達(dá)密度λ=0.1輛/秒.設(shè)車輛速度s為服從高斯分布的隨機(jī)變量，平均車速s=120 km/s，方差為2.0.設(shè)路邊基站最大傳輸半徑Rmax=200 m，車輛與路邊基站之間的最小距離Rmin=5 m.設(shè)每個(gè)車輛的業(yè)務(wù)請求從40以步長10增長到100.對于每一組仿真參數(shù)，隨機(jī)產(chǎn)生30個(gè)仿真場景，并取所有結(jié)果的均值為最終的仿真結(jié)果.

圖2給出了文獻(xiàn)［2］中的算法與筆者提出的算法分別在offline和online情況下，總的車輛請求信息被滿足的情況.從圖中可以看出，在兩種情況下，兩種算法的性能幾乎完全相同.由于online情況下車輛以及業(yè)務(wù)請求信息的不完整性，總的車輛請求信息被滿足的個(gè)數(shù)比offline情況要小約6.5%.

圖2　總的車輛請求信息被滿足的個(gè)數(shù)

圖3 路邊基站總的能耗

圖3給出了兩種算法分別在offline和online情況下，所有車輛總的能耗情況.從圖中可以看出，在offline情況下，由于所傳輸?shù)臉I(yè)務(wù)信息較多，因此路邊基站花費(fèi)了比online情況更多的能量；在online情況下，兩種算法性能差別不大，筆者提出的算法花費(fèi)的能量比文獻(xiàn)［2］的高出約1.2%.

圖4　offline情況的公平性Jain因子

圖5 online情況的公平性Jain因子

圖4和圖5分別給出了兩種算法在offline和online情況下的公平性Jain因子的比較.在offline情況下，筆者提出算法的Jain因子比文獻(xiàn)［2］的高出約116.4%.在online情況下，筆者所提出的算法比文獻(xiàn)［2］的高出約25.9%.

4 總 結(jié)

在車輛網(wǎng)絡(luò)中，路邊基站的數(shù)據(jù)業(yè)務(wù)傳輸策略是車輛網(wǎng)絡(luò)高效工作的基礎(chǔ).筆者研究了在車輛請求較多的情況下，如何公平地進(jìn)行業(yè)務(wù)調(diào)度傳輸并同時(shí)最小化數(shù)據(jù)傳輸能耗的問題，提出了一種基于網(wǎng)絡(luò)流的業(yè)務(wù)調(diào)度算法，可適用于offline和online兩種情況.仿真結(jié)果表明，與現(xiàn)有文獻(xiàn)［2］只最小化路邊基站能耗的算法相比，筆者提出的算法在保證最大化車輛被服務(wù)業(yè)務(wù)請求的情況下，提高了車輛間被服務(wù)的公平性，特別是在offline情況下公平性提高了約116.4%，在online情況下公平性提高了約25.9%.

［1］HAMMAD A A，BADAWY G H，TODD T D，et al.Traffic Scheduling for Energy Sustainable Vehicular Infrastructure ［C］//Proceedings of the 2010 IEEE Global Telecommunications Conference.New York:IEEE，2010:5683759.

［2］HAMMAD A A，TODD T D，KARAKOSTAS G，et al.Downlink Traffic Scheduling in Green Vehicular Roadside Infrastructure［J］.IEEE Transactions on Vehicular Technology，2013，62（3）:1289-1302.

［3］YAN Z，ZHANG Z，JIANG H，et al.Optimal Traffic Scheduling in Vehicular Delay Tolerant Networks［J］.IEEE Communications Letters，2012，16（1）:50-53.

［4］RAMAIYAN V，ALTMAN E，KUMAR A.Delay Optimal Scheduling in a Two-hop Vehicular Relay Network［J］. Mobile Networks and Applications，2010，15（1）:97-111.

［5］KHABBAZ M J，F(xiàn)AWAZ W F，ASSI C M.Probabilistic Bundle Relaying Schemes in Two-hop Vehicular Delay Tolerant Networks［J］.IEEE Communications Letters，2011，15（3）:281-283.

［6］JAIN R，DURRESI A，BABIC G.Throughput Fairness Index:an Explanation［R］.Columbus:Department of CIS，the Ohio State University，1999.

［7］CORMEN T H，LEISERSON C E，RIVEST R L，et al.Introduction to Algorithms［M］.2nd Edition.Cambridge:MIT Press，2001.

［8］ISENTO J N G，RODGIGUES J J P C，DIAS J A F F，et al.Vehicular Delay-tolerant Networks a Novel Solution for Vehicular Communications［J］.IEEE Intelligent Transportation Systems Magazine，2013，5（4）:10-19.

（編輯:郭 華）

Fair traffic scheduling algorithm for the roadside unit

YAN Zhongjiang，LI Bo，GAO Tian，ZUO Xiaoya （School of Electronics and Information，Northwestern Polytechnical Univ.，Xi’an 710072，China）

To improve the fairness performance of the downlink traffic scheduling algorithm，a network flow based downlink traffic scheduling algorithm is proposed for the roadside unit（RSU）in vehicular networks.In the proposed algorithm，a bipartite graph is constructed firstly，where the node set is composed by the vehicle set and the timeslot set.At any given timeslot if a vehicle can communicate with the RSU，then an edge between the given timeslot and that vehicle is added into the edge set.Next，a flow network graph is constructed based on the bipartite graph by adding a virtual source node and a virtual sink node.By applying the conventional minimum cost maximum flow algorithms，a minimum cost maximum flow can be computed，which is converted to the fair traffic scheduling strategy.Simulation results show that，when the total vehicle requirements are maximized，compared with the existing algorithms，the fairness performance of the proposed algorithm is improved by 116.4%in the offline case，and by 25.9%in the online case.

vehicular networks；traffic scheduling；fairness；network flow

TP393

A

1001-2400（2016）01-0133-06

10.3969/j.issn.1001-2400.2016.01.024

2014-08-18 網(wǎng)絡(luò)出版時(shí)間：2015-04-14

國家自然科學(xué)基金資助項(xiàng)目（61201157，61271279）；國家863計(jì)劃資助項(xiàng)目（2014AA01A707）；國家重大專項(xiàng)資助項(xiàng)目（2015ZX03002006）；西北工業(yè)大學(xué)基礎(chǔ)研究基金資助項(xiàng)目（3102015ZY038，3102015ZY039）

閆中江（1983-），男，副教授，博士，E-mail:zhjyan@nwpu.edu.cn.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.021.html