[發明專利]一種用于智能交通系統的非均勻分簇路由的方法

有效

• 申請號: 201510084264.4
• 申請日: 2015-02-16
• 公開（公告）號: CN104640154B
• 公開（公告）日: 2017-12-05
• 發明（設計）人: 游子毅
• 申請（專利權）人: 貴州師范大學
• 主分類號: H04W28/08
• 分類號: H04W28/08;H04W40/02
• 代理公司: 貴陽東圣專利商標事務有限公司52002
• 代理人: 袁慶云

1.一種用于智能交通系統的非均勻分簇路由協議的方法，包括以下步驟：

(1)建立網絡模型與分簇策略：

在二維平面區域：Z²＝{(x,y),0≤x,0≤y}，所有傳感器節點隨機分布，將區域網格化，其格狀網每個正方形區域為α×α，邊長α根據應用任務的求解精度而定；

兩個節點的位置分別為L_P(x_i,y_i)和L_Q(x_j,y_j)，則兩個位置之間的距離為：

將該區域劃分成n個區，n的數量由該區域的長度和分區節點的通信半徑確定，匯聚節點(Sink)節點部署在區域外的一個固定位置；為了實現能耗均衡，距離匯聚節點(Sink)近的分區內的簇數目應多于遠的分區；由于交通環境下車輛節點的高移動性，每個簇的簇頭由Sink節點指定為簇區內的一個固定設施；其它節點與簇頭之間單跳通信，簇頭可通過調整通信半徑控制成員數以減小通信負載；對于相鄰的兩個簇簇頭CH_i和CH_j,則 其中D(CH_i,CH_j)表示CH_i與CH_j之間的距離，和表示相應的半徑；此外，不在任何一個簇通信半徑覆蓋下的傳感器節點可采用鏈式結構的多跳通信，基于貪婪算法選擇信號強度最好的中繼節點傳送感知數據，以此方式將數據傳遞至距離最近的簇內的成員節點；該節點作為鏈首進行一次數據融合后，將數據包發送至簇頭；

網絡中的每一個傳感器節點，都有一個唯一的標志(ID)，由可信中心(Trusted Authority)負責對節點認證、注冊并授權，節點通過標志(ID)和可信中心(Trusted Authority)簽發的數字證書相互驗證身份；

若節點發射l比特數據到距離為d的位置，則發送端的能量為：

E＝E_elec+E_DA

接收端的能量為：

E_EX(l)＝l×E_elec(3)

(2)簇間路由參數初始化：

簇區內簇頭CH_i周期性地向其他成員節點發送詢問報文REQ以同步時間；

每一輪采樣l,1≤l≤N,簇頭CH_i將接收到的感知數據進行融合，生成新的數據包傳送至匯聚節點(Sink)；傳送時，CH_i會選擇相鄰簇頭作為中繼節點轉發數據包；因此，從源點CH_i到匯聚節點(Sink)之間可生成一條或多條不同的路徑；除與匯聚節點(Sink)一跳距離的 簇外，簇頭CH_i隨機生成F只青蛙，每只青蛙個體表示一條從CH_i到匯聚節點(Sink)的可行路徑，即P＝{P₁,P₂,...,P_d}，其中d表示解空間的維數，P_i＝{CH_i,...,CH_x,Sink}，P即為生成的初始群體；

青蛙個體適應度函數為：

式(5)中，α₁+α₂+α₃＝1，CH_i∈P_i表示CH_i是路徑P_i上的一個節點，n_k∈c_i表示n_k是簇c_i內成員節點，E_RX(CH_i,n_k)/E_TX(CH_i,n_k)表示簇頭CH_i對成員節點n_k接收/發送數據所消耗的能量，CH_j∈adj(CH_i)表示CH_j是CH_i的相鄰簇頭，E_RX(CH_i,CH_j)/E_TX(CH_i,CH_j)表示CH_i對CH_j接收/發送數據所消耗的能量，E_DA(CH_i)表示CH_i融合數據所消耗的能量，E_comput(CH_i)表示CH_i進行相應計算所消耗的能量；

函數f_i描述路徑P_i的總體能量消耗，包括該路徑上各節點的計算代價和通信負荷，每一輪數據采樣，簇頭CH_i接收簇內成員節點和來自相鄰簇頭的消息，計算出各能耗參數并更新從該簇頭到匯聚節點(Sink)的每條路徑的代價，其中，系數α₁,α₂,α₃為各種參數在節點總體能耗中的比重；簇間最優路徑問題等于青蛙最優解問題；最優解是目標函數E(P_i)取最小值，即f_i取最大值；

CH_i將生成的青蛙適應度按降序排列成P₁,P₂,...,P_F，并劃分成m個種群Y₁,Y₂,...,Y_m，構造子種群，m的數值由P中源點的下一跳節點的個數來決定；每個子種群包含s只青蛙，滿足下列關系：

Y_ik＝{(P_i)^k,f(i)^k},(P_i)^k＝P(i+(k-1)×s),

f(i)^k＝f(i+(k-1)×s),k＝1,2,...,s

i＝1,2,...,m,F＝m×s

(3)簇間路由優化：

簇間路由優化步驟包括簇間路由局部優化步驟以及簇間路由全局優化步驟；

(3.1)簇間路由局部優化：

簇間路由局部優化是對青蛙種群劃分的子種群分別進行局部搜索；

簇間路由局部優化步驟1：在第l輪,1≤l≤N，計算子種群Y_i的適應度f(i)^k，以概率p一一進行更新，并找出最優解P_b和最差解P_w；

簇間路由局部優化步驟2：P_b與P_w進行交叉替換操作，即查找兩條徑中的相同節點，從選中的一個公共節點開始到下一個公共節點對P_w進行鏈路替換，如果兩條路徑僅有一個相同節點，則取匯聚節點(Sink)為下一個公共點；

簇間路由局部優化步驟3：計算交叉后最差解P_w的適應度newf(i)^w，如果newf(i)^w大于替換前最差解適應度f(i)^w，則替換成功，否則，交叉失敗，如果交叉失敗，則再選用全局最優解P_g對P_w進行交叉替換，如果newf(i)^w仍沒有得到改進，則隨機產生一個新的青蛙來代替原P_w；

(3.2)簇間路由全局優化：

簇間路由全局優化步驟1：本輪搜索結束后，進行新一輪局部搜索；

簇間路由全局優化步驟2：重復簇間路由全局優化步驟1，經過N輪局部優化后，將所有子種群的解重新混合在一起，按適應度f(i)降序排列，重新劃分簇群；

簇間路由全局優化步驟3：重復簇間路由全局優化步驟2，直到滿足目標函數E(P_i)值最小為止；

(4)簇半徑的動態調整：

每一輪采樣l(1≤l≤N),簇頭CH_i可計算其競爭半徑如下：

式(6)中，為簇區c_i內成員節點到匯聚節點(Sink)的最大距離和最小距離，R_max為簇頭CH_i競爭半徑的最大取值，c為0-1之間的參數，用來控制取值范圍；簇內成員節點與簇頭采用單跳通信方式通信，成員節點除了發送自身采集的數據，還需轉發來自簇外其它節點的通過鏈式結構傳送的數據；為避免簇頭節點承擔過重負擔，消耗更多的能量，使得簇頭過早失效或丟棄數據包，從而造成感知空洞，為此，非均勻分簇路由協議(UCSNP)采取一種動態的簇半徑優化策略以調整節點間負載均衡，

設置權值W_i計算公式如下：

式(7)中，為0-1之間的參數，E(n_k)為簇c_i內成員節點n_k在本輪采樣中所消耗的能量，E(CH_i)為簇頭CH_i在本輪采樣中所消耗的能量，R₀為簇頭CH_i在本輪的通信半徑，從式(7)可得出，權值W_i由成員節點總能耗與簇頭能耗之比和成員節點到簇頭距離總和與到簇頭通信半徑之比來決定。

2.如權利要求1所述的一種用于智能交通系統的非均勻分簇路由協議的方法，其中：所述傳感器節點包括車輛節點和固定設施節點。