[發明專利]一種基于邊緣計算策略的分簇AODV路由方法

有效

• 申請號: 202010570066.X
• 申請日: 2020-06-21
• 公開（公告）號: CN111741448B
• 公開（公告）日: 2022-04-29
• 發明（設計）人: 張德干;張捷;張婷;樸銘杰;龔倡樂;王法玉
• 申請（專利權）人: 天津理工大學
• 主分類號: H04W4/46
• 分類號: H04W4/46;H04W40/02;H04W40/10;H04W40/32;H04W84/18;H04L45/00;H04L45/122
• 代理公司: 天津耀達律師事務所 12223
• 代理人: 侯力

1.一種基于邊緣計算策略的分簇AODV路由方法，其特征在于該方法包括如下步驟：

第1、基本原理的描述：

第1.1、建立道路模型；

考慮一條雙向通行道路，總長度為L_ROAD，車輛在道路上以確定的速度勻速運動，在通信范圍內，車輛密度為ρ；沿路設有路邊設備RSU，相鄰的RSU之間的距離為L_RSU，RSU提供在通信范圍內的無線通信，將無線通信范圍設置為L_RSU/2；整條道路被看作分成為L_ROAD/L_RSU段；

第1.2、車載通信路由協議；

整個車輛網絡體系是建立在車輛密度較大的場景下，V2R和V2V都采用Ad Hoc網絡模型，在路由協議的選擇上，使用AODV路由協議；

第1.3、道路節點分簇；

分簇是由網絡拓撲結構的控制，建立數據傳輸路徑的過程，包括：簇頭節點的產生，簇的形成和數據傳輸三個部分，通過分簇，能夠有效的改善網絡的可擴展性，減少網絡的整體負載及開銷；

第1.4、節點能量消耗計算；

一條鏈路所有節點能量的總消耗需要作為整個路由路徑能量的考慮，計算如下：

其中，n為每條路徑的車輛節點總數，C表示一個任意的常數，Cost(a)表示為車輛節點a的能量消耗，可以通過無線傳感網絡節點能耗E_T(l，d)和E_R(l，d)表示，即發送和接受數據時的能量消耗，k表示車輛節點，計算如下：

Cost(k)＝E_T(l，d)+E_R(l，d) (2)

根據無線電能量消耗模型，每發送lbit的數據，節點的能耗如下：

其中，l為傳輸數據包字節數，d為傳輸距離；當節點以及節點之間距離小于等于閾值d₀時，采用自由空間模式；當節點以及節點之間的距離大于閾值d₀時，節點采用多徑衰減模式；E_elec為射頻能耗系數；E_fs為自由空間模式下電路放大器的能耗系數，E_mp為多徑衰減模式下電路放大器的能耗系數；

同時，節點接收lbit消息的能耗計算公式如下：

E_R(l，d)＝lE_elec (4)；

第2、通信方式的選擇：

第2.1、簇區內通信；

簇區內通信是指，當車輛A，B處于同一個邊緣超級節點的簇區內通信時，為了降低部署在RSU的邊緣服務器的能耗，選擇通過V2V模式，即車輛與車輛間的模式直接進行通信；當使用V2V模式進行通信的時候，主要使用的是按需路由協議中的AODV路由協議，同時，考慮到傳統的AODV路由協議僅通過最小跳數來建立路由鏈路，在網絡拓撲結構變化迅速的車輛自組織網絡中極有可能出現鏈路不穩定的情況，因此在鏈路選擇的方式上，通過使用Q-Learning算法，對中間節點的選擇進行優化；在Q-Learning算法中，S為給定的狀態空間，A為給定的動作集合，在t時刻的s_t狀態下(s_t∈S)采取動作a_t(a_t∈A)，同時根據動作反饋相應的獎勵R，即為Q(s，a)；Q-Learning采用狀態-動作迭代的方式來得到最優策略，得到函數Q更新的公式如下：

Q(s_t，a_t)←Q(s_t，a_t)+α(R_t+1+γmax_aQ(s_t+1，a)-Q(s_t，a_t)) (5)

式中，α為學習率，α越大，Q值收斂越快；max_aQ(s_t+1，a)指的是從動作集合A中選擇使得Q(s_t+1，a)取值最大的動作；γ在這里為折扣因子，γ∈[0，1]，接近1時指的是函數考慮將來回報，反之則是考慮即刻回報；

第2.2、簇區間通信；

簇區間通信是指，假設源車輛節點位于P₁簇區，目的車輛節點位于P_n簇區，當車輛節點在簇區間進行通信時，采用V2R模式，即車輛與道路的模式進行通信；

第3、路由協議設計：

第3.1、協議描述；

步驟1：簇區的劃分；

根據RSU-MEC設備，首先對于車輛節點進行簇區的劃分，每個RSU-MEC配置有邊緣服務器，只負責統計自身通信范圍內的車輛，每輛車在同一時刻只能在一個簇區內，在總長度為L_ROAD的道路上相鄰的RSU之間的距離為L_RSU，整個道路被分割為L_ROAD/L_RSU個簇區，每個簇區表示為：P₀＝{n₁，n₂，n₃，…，n_i}，其中，n_i表示為車輛節點，P為每個簇區；

步驟2：節點位置的確定；

根據已經劃分好的簇區，當簇區P的RSU-MEC收到車輛節點發出通信請求后，首先查找目的車輛節點是否位于本簇區，如果不在當前簇區，則向相鄰的邊緣超級節點發出請求，以此來確定目的車輛節點所處的位置；

步驟3：通信方式選擇及路由建立；

Ⅰ.如果車輛節點處于同一個簇區，采用簇區內的通信方式，即采用V2V的通信模式，根據通過優化后的AODV路由協議；

Ⅱ.如果車輛節點處于相鄰簇區，采用相鄰簇區的通信方式；

Ⅲ.如果車輛節點處于非相鄰簇區，采用非相鄰簇區的通信方式，即使用V2R通信模式，源車輛節點與該簇區的RSU-MEC進行通信，中間RSU-MEC相互進行通信，然后目的節點所在簇區的RSU-MEC與目的車輛節點進行通信；

第3.2、復雜度分析；

AODV-MEC算法的時間復雜度由對于車輛節點進行簇區劃分以及對通信分配方式的選擇來決定，在對于車輛所處簇區進行分配時需要通過車輛所處位置是否位于RSU-MEC的通信范圍之內，其時間復雜度為O(n²)；在簇區劃分完成并發起通信請求后，RSU-MEC需要通過判斷源車輛節點與目的車輛節點是否位于同一簇區內，本AODV-MEC算法中，在分配通信方式時其最壞情況時間復雜度為O(n)，綜合兩者的時間復雜度得到時間復雜度為O(n²)。