一種公平的路邊基站下行業務調度算法

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

（西北工業大學電子信息學院，陜西西安 710072）

一種公平的路邊基站下行業務調度算法

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

（西北工業大學電子信息學院，陜西西安 710072）

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

車輛網絡；業務調度；公平性；網絡流

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

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

筆者提出了一種基于網絡流的業務調度算法，在保證最大化車輛業務請求的情況下，提高了車輛之間業務調度的公平性.

1 系統模型

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

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

其中，Rmin（Rmax）為路邊基站與車輛之間的最小（最大）距離，P0（d0）為參考功率（距離），ρ為擴展因子，α為路徑衰弱指數.因此，在時隙t內，路邊基站所消耗的能量為

其中，γ=τρP0dα0.

設路邊基站能夠將每個時隙獨立地分配給不同的車輛.當時隙tj被分配給車輛vi時，路邊基站將花費Ei，j的能量，且車輛vi一個單位的業務請求將被滿足.定義布爾值變量Bi，j表示時隙tj是否被分配給車輛vi，表示為

則B=｛Bi，j|1≤i≤N，1≤j≤M｝，為路邊基站所確定的對應時隙集合T的業務調度策略.

（i）最大化總的車輛業務請求.定義車輛業務請求滿足差，則該目標等價于

令S2為求解式（5）所得的業務調度策略集，S2?S1.在此基礎上進一步地最小化路邊基站進行業務傳輸所花費的能量.

（iii）最小化路邊基站數據傳輸能耗.在求得式（4）～（5）業務調度策略的基礎上，該目標為

由于路邊基站的主要作用就是為過往車輛提供信息服務，因此最大化地滿足車輛請求（即式（4））的優先級最高，之后再進一步地最大化業務調度的公平性（即式（5）），最后一步是最小化路邊基站數據傳輸的能耗（即式（6）），則具有較低的優先級.

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

2 基于網絡流的公平業務調度算法

一般來說，多步最優化問題（比如式（4）～（6））的求解非常困難.因為后續步驟的最優化問題的求解是基于前面問題的求解.比如，需要首先求出式（4）的所有最優解之后才能求出式（5）的最優解；接著，求出式（5）的所有最優解之后才能求出式（6）的最優解.筆者提出一種基于網絡流的公平業務調度算法，可以一次性地求解該多步最優化問題（即式（4）～（6）），極大地降低了問題的求解復雜度.

2.1算法描述

圖1給出了筆者所提出的網絡流算法中所采用的二部圖與網絡流圖.基于網絡流的公平業務調度算法的偽代碼如下:

圖1　二部圖與網絡流圖

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

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

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

至此，網絡流圖Gf構建結束.通過在Gf上運行典型的最小花費最大流算法，比如Push-relabel算法［7］，將可以計算出圖Gf對應的最小花費最大流F.如果在所得的最小花費最大流F中，邊e（vi，tj）的流不為零，則表示路邊基站應該將時隙tj分配給車輛vi，即對應的布爾值變量Bi，j=1.

2.2online數據傳輸決策討論

上節給出了在已知所有時隙以及所有到達車輛的情況下（即offline的情況［2］），計算公平的路邊基站業務調度問題的算法.需要指出的是，該算法同樣適用于在未知所有時隙以及所有到達車輛的情況（即online的情況［2］）.下面討論筆者所提出的算法如何應用到online的情況.

首先，當第1輛車v1進入路邊基站的傳輸覆蓋范圍時，使用筆者所提出的算法，即可為車輛v1計算出一個最小化路邊基站能耗的業務調度算法（因為此時只有一輛車，故最大化公平性Jain因子（式（5））不存在）.此時，車輛節點集V′=｛v1｝，時隙節點集T′=｛t1，t2，…，tM′｝，其中M′=2Rmaxs1，s1為車輛的恒定速率.其他部分參照基于網絡流的公平業務調度算法.

設在時隙tj，一個新的車輛vi到達并進入到路邊基站的數據傳輸區域.設此時在路邊基站的數據傳輸區域內，同時還存在著N′個車輛正在被路邊基站服務.不管現有的業務調度決策是否已經被執行結束，筆者所提出的基于網絡流的公平業務調度算法將被重新調用，并計算新的業務調度決策.此時，節點集V′=｛v1，v2，…，vN′｝，時隙節點集T′=｛tj，tj+1，…，tj+M′｝，其中tj+M′為V′中最后一個車輛離開路邊基站數據傳輸區域的時隙.其他部分參照基于網絡流的公平業務調度算法.

當新的數據傳輸決策被計算出來之后，路邊基站將更新并執行新的數據傳輸決策.在online情況下，每當有新的車輛到達，路邊基站都將根據當前車輛的情況，重新計算并執行新的數據傳輸決策.

2.3算法的計算復雜度及算法可行性討論

筆者所提算法的計算復雜度取決于所使用的Push-relabel算法的復雜度，而Push-relabel算法的復雜度為O（V2E ）［7］，其中V 為網絡流圖中節點的個數，E 為網絡流圖中邊的個數.文中，在最壞情況下，V=2+N+M，而E=N+M+NM，因此算法的計算復雜度為O （max（N3，M3））.

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

3 仿真結果

總的車輛請求信息被滿足的個數、路邊基站總的能耗以及業務調度決策的公平性是衡量業務調度決策性能的重要指標.將筆者所提出的算法與文獻［2］中的算法進行了仿真比較，同時比較了offline和online兩種情況.

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

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

圖2　總的車輛請求信息被滿足的個數

圖3 路邊基站總的能耗

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

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

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

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

4 總 結

在車輛網絡中，路邊基站的數據業務傳輸策略是車輛網絡高效工作的基礎.筆者研究了在車輛請求較多的情況下，如何公平地進行業務調度傳輸并同時最小化數據傳輸能耗的問題，提出了一種基于網絡流的業務調度算法，可適用于offline和online兩種情況.仿真結果表明，與現有文獻［2］只最小化路邊基站能耗的算法相比，筆者提出的算法在保證最大化車輛被服務業務請求的情況下，提高了車輛間被服務的公平性，特別是在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，FAWAZ 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 網絡出版時間：2015-04-14

國家自然科學基金資助項目（61201157，61271279）；國家863計劃資助項目（2014AA01A707）；國家重大專項資助項目（2015ZX03002006）；西北工業大學基礎研究基金資助項目（3102015ZY038，3102015ZY039）

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

網絡出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.021.html