基于車載自組織網絡的數據和能量協同路由算法

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

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

0 引 言

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

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

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

近年來,關于VANET的研究已有許多成果,關于RSU的相關研究工作有：RSU設置和管理,車輛到RSU的數據傳輸和訪問調度,車輛與RSU間的通信設置.

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

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

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

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

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

1 系統模型

1.1 物理問題

本文研究在具有能量合作的車載自組網絡中聯合優化數據和能量路由的問題,以實現網絡生命周期最大化.假設:

圖1 VANET中數據和能量的協作路由Fig.1 Collaborative routing of data and energy in VANETs

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

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

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

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

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

1.2 模型構建

(1)

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

(2)

(3)

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

(4)

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

1.3 目標函數

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

(5)

2 模型求解方案

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

問題轉換后,應用Lagrange更新式(10)的優化變量,得

其中γq和ηl是Lagrange乘數.KKT最優性條件為

其中:

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

(20)

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

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

(22)

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

(23)

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

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

算法1分布式協同Lagrange-Newton優化算法.

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

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

步驟3) 傳遞權重變量：RSU節點和車輛節點需要將初始值發送給鄰近RSU;

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

步驟5) 增加迭代次數: 設置k=k+1,轉步驟2)；

3 實驗結果

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

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

圖3 網絡開銷Fig.3 Network overhead

圖4 車輛數量與網絡生命周期的關系Fig.4 Relationship between vehicle quantity and network life cycle

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

圖5 RSU數量與網絡生命周期的關系Fig.5 Relationship between RSU quantity and network life cycle

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

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