陳翰林,胡 明,2,胡潔珺,顏 輝

(1.長春工業(yè)大學 計算機科學與工程學院,長春 130012；2.長春工程學院 計算機技術(shù)與工程學院,長春 130012；3.吉林大學 計算機科學與技術(shù)學院,長春 130012；4.長春工程學院 吉林省水利電力工程物理級仿真與安全科技創(chuàng)新中心,長春 130012)

0 引 言

車載自組織網(wǎng)絡(vehicular ad-hoc networks,VANET)[1]作為智能交通系統(tǒng)(intelligent transport system,ITS)的一個重要組成部分,近年來備受關(guān)注[2].ITS系統(tǒng)的主要目標是減少道路交通事故導致的死亡和財產(chǎn)損失,同時提供駕駛舒適性[3].VANET作為結(jié)構(gòu)開放、自組織、方便實用的無線通信網(wǎng)絡,為ITS提供了更好的通信環(huán)境.一般在ITS中可分為兩種通信模型[4]: 車輛到車輛通信(vehicule to vehicule,V2V)和車輛到基礎設施通信(vehicule to road,V2R),也稱為車輛到路邊單元通信.

VANET通常是指具有可選基礎設施支持的移動車輛的無線Ad-hoc網(wǎng)絡.一種情況是采用基礎設施獨立的VANET可由一組移動車輛節(jié)點自發(fā)地構(gòu)建,這些節(jié)點在附近移動并不依賴于基礎設施;另一種情況,VANET的許多新興應用程序(依賴于基礎設施)利用各種公共和私有基礎設施進行研發(fā),例如公共/私有云、政府機構(gòu)服務器等.本文采用后一種VANET類型.與基礎設施無關(guān)的VANET相比,依賴于基礎設施的VANET的特點為有大量后端基礎設施的存在,例如路邊單元(roadside units,RSU)的使用.

RSU在VANET中具有重要作用.RSU是將VANET連接到Inter網(wǎng)的外部網(wǎng)絡的中繼節(jié)點,提供組合有線和無線鏈路的混合路由路徑,用于遠程VANET節(jié)點間的高速大容量通信.通過使用高速數(shù)據(jù)鏈路在遠程車輛間的信息通信,可顯著減少延遲.而且RSU是VANET中協(xié)作和分布式應用程序的關(guān)鍵組件.目前,RSU也被考慮作為連接車載網(wǎng)絡和寬帶網(wǎng)絡(如蜂窩網(wǎng)絡)的網(wǎng)關(guān),從而擴展VANET的覆蓋范圍并為用戶提供服務.但存在部署和運營信息系統(tǒng)成本較高的問題.以農(nóng)村地區(qū)為例,RSU通常由電網(wǎng)供電,需要物理基礎設施連接RSU,從而導致部署和維護信息系統(tǒng)的成本增加.因此,可通過研究能源合作和可再生能源問題,實現(xiàn)VANET網(wǎng)絡周期最大化,以降低成本.在VANET中,使用具有能量收集和能量存儲的RSU,能量收集源根據(jù)環(huán)境提供隨機可用的能量,但這種存儲設備的容量有限.當RSU未獲得足夠的能量或沒有充分可用的能量時,其充電達不到合適的飽和狀態(tài).RSU必須能通過適應能量收集過程要求和通信要求,才能有效管理其可用能量.

近年來,關(guān)于VANET的研究已有許多成果,關(guān)于RSU的相關(guān)研究工作有：RSU設置和管理,車輛到RSU的數(shù)據(jù)傳輸和訪問調(diào)度,車輛與RSU間的通信設置.

1) RSU的能量收集.Atallah等[5]研究了能量收集系統(tǒng)在車輛環(huán)境中的挑戰(zhàn)和可用性；Vageesh等[6]研究了電網(wǎng)和太陽能供電的RSU,并提出了部署RSU數(shù)量的優(yōu)化策略,證明了將最佳RSU布局策略與高效的睡眠調(diào)度方法相結(jié)合的策略,可使整體成本降低；Ibrahim[7]提出了太陽能收集電路RSU的設計；Ali[8]提出了一種基本的電源管理方案,降低了RSU的功耗；Muhtar等[9]考慮了RSU由可再生能源——風能提供動力的車載自組網(wǎng)絡,并根據(jù)所需能量、數(shù)據(jù)包阻塞概率和平均數(shù)據(jù)包延遲分析了網(wǎng)絡性能.但上述研究只考慮了能量收集下RSU的實時調(diào)度成本問題,并未對收集的能量進行管理和合理分配等問題展開相關(guān)研究.

2) RSU的功耗和管理.Yang等[10]將數(shù)據(jù)傳輸和能量傳輸?shù)氖諗恳暈橐粋€完整的系統(tǒng),不僅考慮了物理層,還考慮了更高層;Fouladgar等[11]提出了在接收節(jié)點后,循環(huán)使用節(jié)點的思想,并考慮了能量和數(shù)據(jù)傳輸,以達到最大化通信網(wǎng)絡中數(shù)據(jù)速率的效果；Gurakan等[12]提出了具有數(shù)據(jù)和能量協(xié)作的能量收集通信網(wǎng)絡延遲最小化問題；Dai等[13]提出了無線傳感器網(wǎng)絡中數(shù)據(jù)路由和能量路由的聯(lián)合優(yōu)化算法；Wu等[14]提出了一種基于IEEE 802.11的能量MAC層協(xié)議,為ITS通信模塊提供能量；Zou等[15]研究了RSU調(diào)度節(jié)能問題,目的是如何在給定時間內(nèi)打開和關(guān)閉它們的最佳可用時間表,以便在網(wǎng)絡連接時降低系統(tǒng)中RSU的總能量消耗率；Hammad等[16]考慮了在滿足車輛通信需求的同時,最小化路邊接入點所需能源的問題,為任何可實現(xiàn)調(diào)度算法的性能提供了一個上界,使用車輛位置和速度輸入解決該問題;Tao等[17]提出了兩種不同的指標確定連通性指數(shù)和節(jié)能指數(shù),提高了VANET中RSU的連通性和節(jié)能效率；雷建軍等[18]提出了一種能量有效的數(shù)據(jù)收集協(xié)議，通過在不計算睡眠調(diào)度算法獲得的能量增益情形下，減少網(wǎng)絡整體能耗.

3) RSU數(shù)據(jù)傳輸和通信管理.Jiang等[19]提出了一種公共車輛網(wǎng)絡,公共車輛和路邊單元RSU一起用于交通數(shù)據(jù)傳播,以便得到更高的覆蓋率；Huang等[20]提出了一種基于總線的nexthop轉(zhuǎn)發(fā)方案,并分析了車載自組網(wǎng)絡總線輔助多播容量的上限和下限,車輛在向其他節(jié)點發(fā)送消息時選擇總線作為下一跳轉(zhuǎn)發(fā)節(jié)點；Reis等[21]設置車輛作為車載自組網(wǎng)絡的中繼轉(zhuǎn)發(fā)節(jié)點,即使用普通車輛作為臨時路邊單元RSU充當網(wǎng)絡中其他車輛的通信橋梁,但普通車輛(臨時RSU)的短暫?？坑锌赡苁拐w系統(tǒng)的穩(wěn)定性和可靠性極大降低.

4) 網(wǎng)絡生命周期.Hu等[22]提出了一種可持續(xù)性、高質(zhì)量的MCS感知任務執(zhí)行的博弈方法,從而提高了網(wǎng)絡的生命周期；林海峰等[23]提出了一種啟發(fā)式解決方案,可最大化網(wǎng)絡生命周期,并盡可能地保證傳感器自身的能量大于傳輸?shù)狡渥罱従庸?jié)點所需的能量限度；Gatzianas等[24]研究了計算數(shù)據(jù)流的問題,最大化網(wǎng)絡生命周期,但兩個鏈路上的傳輸速率都是固定的,并且只考慮了有效負載傳輸功率；Yildiz等[25]提出了一個通信和計算功耗之間最佳權(quán)衡的框架,并研究了在延遲服務質(zhì)量約束下的網(wǎng)絡壽命最大化問題;曹建玲等[26]提出了一種能量高效分簇算法協(xié)議延長網(wǎng)絡生存時間.

本文主要研究能量收集的RSU與參與車輛間的能源合作問題,以實現(xiàn)最大網(wǎng)絡生命周期的目標.本文將能源合作引入VANET中,即RSU節(jié)點與鄰居RSU節(jié)點協(xié)作,并且RSU節(jié)點可接收下行鏈路車輛傳輸能量,從而達到RSU可維持工作所需的能量.同時為了更好地實現(xiàn)網(wǎng)絡生命周期最大化,本文提出一種分布式Lagrange-Newton迭代算法,并證明該算法具有良好的收斂性和準確性.模擬實驗結(jié)果表明,有能量合作的VANET比無能量合作的傳統(tǒng)VANET具有更好的網(wǎng)絡生命周期.

1 系統(tǒng)模型

1.1 物理問題

本文研究在具有能量合作的車載自組網(wǎng)絡中聯(lián)合優(yōu)化數(shù)據(jù)和能量路由的問題,以實現(xiàn)網(wǎng)絡生命周期最大化.假設:

圖1 VANET中數(shù)據(jù)和能量的協(xié)作路由Fig.1 Collaborative routing of data and energy in VANETs

1) RSU可部署在靜態(tài)位置,移動交通車輛可根據(jù)需要部署在可控的位置;

2) 每個RSU上都部署能量收集裝置；

3) 對于部署車輛,假設每輛參與車輛都不會延誤,其運動軌跡是相對靜止的,即當參與車輛將數(shù)據(jù)上傳到相鄰的RSU時,可檢測到車輛位置；

4) 每個參與車輛只能在RSU的感知覆蓋范圍內(nèi)進行能量傳輸.

在上述場景下,RSU向其鄰居RSU傳輸數(shù)據(jù)和能量,車輛向最近的RSU傳輸數(shù)據(jù)和能量,包括其ID、電池狀態(tài)、感測數(shù)據(jù)大小.該過程將形成新VANET的拓撲結(jié)構(gòu),如圖1所示.

1.2 模型構(gòu)建

(1)

1.2.2 能量模型 考慮RSU能源管理和能源合作.每個RSU僅由可再生能源和下行車輛傳輸能量供電.所有RSU節(jié)點都配備了能量收集設備,可從環(huán)境中獲取能量并將其存儲在可充電電池中.由于位置隨機,不同環(huán)境中的RSU節(jié)點具有不同的能量收集率,RSU節(jié)點m的能量收集率表示為hm.在RSU節(jié)點m的感知范圍內(nèi),每個車輛n都可將能量上傳給RSU節(jié)點m,其中單個車輛上傳能量表示為En.此外,RSU不接受來自電網(wǎng)的電力供應.因此,RSU節(jié)點m收集的電池能量Bm可表示為

(2)

(3)

考慮到能量可持續(xù)性條件,類似于傳統(tǒng)的數(shù)據(jù)路由,在網(wǎng)絡中最佳能量流的引導和決策同樣具有重要作用,稱為能量路由.與數(shù)據(jù)路由類似,每個能量鏈路標記為q={1,2,…,Q},定義Oe(m)為從RSU節(jié)點m流向相鄰RSU節(jié)點N(m)在鏈接q上的輸出能量流;Ie(m)定義為從相鄰RSU節(jié)點N(m)到RSU節(jié)點m在鏈接q上的輸入能量流;eq為轉(zhuǎn)移的能量;θq表示轉(zhuǎn)移效率.因此,能量可持續(xù)性條件應滿足：

(4)

確保了每個RSU節(jié)點的能量供應率不低于能量消耗率.式(4)中右邊兩項分別表示通信和能量轉(zhuǎn)移中的能量消耗率;左邊三項分別是能源合作中的能量收集率、車輛傳輸能量和能量接收率.

1.3 目標函數(shù)

本文的優(yōu)化目標是最大化網(wǎng)絡生命周期,首個RSU節(jié)點的能量耗盡將導致整個網(wǎng)絡生命周期結(jié)束.網(wǎng)絡生命周期Tnet定義[28]為

(5)

2 模型求解方案

針對式(6)采用分布式優(yōu)化的方法,每個RSU節(jié)點與其鄰居RSU交換數(shù)據(jù)時可計算出最佳路由,并伴隨著網(wǎng)絡中的迭代,每個節(jié)點的計算復雜度不隨網(wǎng)絡規(guī)模而變化.因此本文提出一種分布式Lagrage-Newton迭代算法[29]求解該問題.

問題轉(zhuǎn)換后,應用Lagrange更新式(10)的優(yōu)化變量,得

其中γq和ηl是Lagrange乘數(shù).KKT最優(yōu)性條件為

其中:

n(l)和m(l)分別為數(shù)據(jù)鏈路l的源節(jié)點和目的節(jié)點;k(q)和z(q)分別為能量鏈接q的源節(jié)點和目標節(jié)點.互補的松弛條件為

(20)

其中Δ是防止出現(xiàn)復根而影響算法收斂性的算子,Δ≥0.通過計算式(20),可在迭代中獲得最優(yōu)變量值為

目標函數(shù)中的變量將在迭代后逐步改變,可表示為

(22)

根據(jù)Newton算法的收斂性,式(22)的步長需滿足的條件為

(23)

通過迭代允許能量一次通過鏈路的前提條件是所有鏈路都經(jīng)常被訪問.

需在迭代前調(diào)查任何可能傳輸?shù)哪芰?跟蹤每個能量鏈路上的傳輸能量,以便在最優(yōu)解中確定哪些能量鏈路處于活動狀態(tài).在迭代檢測時,當γk(q)<θqγz(q)時,搜索滿足式(21)的γq.如果無解,則有γk(q)>θqγz(q), 表明RSU節(jié)點不具備轉(zhuǎn)移的能量,需要車輛進行能量傳輸.因為目標函數(shù)的嚴格凸性,因此確定每次迭代都減小了目標函數(shù).由于算法的收斂性,有界實單調(diào)序列總收斂,并且極限點是局部最小值,因為迭代只能在能量鏈路的γk(q)=θqγz(q)時停止,其中eq>0,因此它們與式(16)的KKT最優(yōu)條件相同.由于問題的凸性,因此這個局部最小值也是唯一的全局最小值.

算法1分布式協(xié)同Lagrange-Newton優(yōu)化算法.

步驟1) 初始化: 設定k=1,Δ≥0,λ∈(0,1),ε≥0;

步驟2) 更新變量: 利用式(21)更新其主要變量；

步驟3) 傳遞權(quán)重變量：RSU節(jié)點和車輛節(jié)點需要將初始值發(fā)送給鄰近RSU;

步驟4) 行搜索變量: 計算步長λk,如果滿足式(23),則轉(zhuǎn)步驟5)；否則步長λk=λk/4,轉(zhuǎn)步驟4)；

步驟5) 增加迭代次數(shù): 設置k=k+1,轉(zhuǎn)步驟2)；

3 實驗結(jié)果

圖2為當有100輛車參與時,將數(shù)據(jù)包發(fā)送到sink事件區(qū)域內(nèi)RSU節(jié)點的能量消耗.由圖2可見,與無能量合作的情形相比,有能源合作將消耗更少的能量.圖3為在車載自組網(wǎng)絡中彼此通信所需的額外時間.由圖3可見,與無能量收集的情形相比,有能量收集時的網(wǎng)絡延遲減少了.

圖2 RSU節(jié)點的能量消耗Fig.2 Energy consumption of RSU node

圖3 網(wǎng)絡開銷Fig.3 Network overhead

圖4 車輛數(shù)量與網(wǎng)絡生命周期的關(guān)系Fig.4 Relationship between vehicle quantity and network life cycle

圖4為車輛數(shù)量與網(wǎng)絡生命周期的關(guān)系.由圖4可見,隨著車輛數(shù)量的增加,網(wǎng)絡生命周期不斷遞增,最終趨于平穩(wěn).這是因為當車輛達到RSU感知覆蓋范圍飽和時,網(wǎng)絡生命周期將不會隨著車輛數(shù)量而增加.因此,有能量收集的情形比無能量收集的情形具有更長的網(wǎng)絡生命周期.圖5為RSU數(shù)量與網(wǎng)絡生命周期的關(guān)系.由圖5可見,有能量合作時的網(wǎng)絡生命周期遠大于無能量合作時的網(wǎng)絡生命周期,但這種情形也不是絕對的.當RSU數(shù)量小于50時,無能源合作情形下有200輛車參與比有能源合作情形下有100輛車參與時網(wǎng)絡生命周期更優(yōu).圖6為次梯度算法與本文算法的收斂性對比.由圖6可見,本文算法收斂性更好.

圖5 RSU數(shù)量與網(wǎng)絡生命周期的關(guān)系Fig.5 Relationship between RSU quantity and network life cycle

圖6 不同算法的收斂性對比Fig.6 Comparison of convergence of different algorithms

綜上所述,本文在車載自組網(wǎng)絡中,通過RSU間的能量合作和RSU與下行車輛的能量傳輸,實現(xiàn)了網(wǎng)絡生命周期最大化.在提出的協(xié)同路由策略中,車載自組網(wǎng)絡的每個RSU和車輛都需要考慮數(shù)據(jù)流和能量流,確定數(shù)據(jù)流與能量流的聯(lián)合問題,以及RSU之間的能量合作和能量收集.本文提出了一種分布式Lagrange-Newton迭代算法求解該問題,為算法的收斂性建立了必要條件.實驗數(shù)值結(jié)果表明,VANET策略中的能量和數(shù)據(jù)路由協(xié)作可有效改善網(wǎng)絡生命周期.