基于車載自組織網(wǎng)絡(luò)的數(shù)據(jù)和能量協(xié)同路由算法

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

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

0 引 言

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

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

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

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

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的設(shè)計(jì)；Ali[8]提出了一種基本的電源管理方案,降低了RSU的功耗；Muhtar等[9]考慮了RSU由可再生能源——風(fēng)能提供動(dòng)力的車載自組網(wǎng)絡(luò),并根據(jù)所需能量、數(shù)據(jù)包阻塞概率和平均數(shù)據(jù)包延遲分析了網(wǎng)絡(luò)性能.但上述研究只考慮了能量收集下RSU的實(shí)時(shí)調(diào)度成本問題,并未對(duì)收集的能量進(jìn)行管理和合理分配等問題展開相關(guān)研究.

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

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

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

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

1 系統(tǒng)模型

1.1 物理問題

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

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

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

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

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

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

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

1.2 模型構(gòu)建

(1)

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

(2)

(3)

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

(4)

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

1.3 目標(biāo)函數(shù)

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

(5)

2 模型求解方案

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

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

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

其中:

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

(20)

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

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

(22)

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

(23)

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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