[發明專利]車聯網大規模網絡互聯互通的連通基組件構造方法

有效

• 申請號: 201710397807.7
• 申請日: 2017-05-31
• 公開（公告）號: CN107196835B
• 公開（公告）日: 2020-08-14
• 發明（設計）人: 程久軍;臧笛;余潤身
• 申請（專利權）人: 同濟大學
• 主分類號: H04L12/46
• 分類號: H04L12/46;H04L12/751;H04L29/08;H04W4/40;H04W4/46
• 代理公司: 上海科律專利代理事務所(特殊普通合伙) 31290
• 代理人: 葉鳳

1.一種建立車聯網大規模網絡互聯互通的連通基組件的方法，其特征在于，包括

步驟1，將單位圓盤圖表示為G＝(V，E)，其中V＝{v₁，v₂，…，v_n}代表網絡節點集合，E＝{E_ij}表示網絡中邊的集合，E_ij表示節點v_i和v_j之間的邊；

定義車聯網連通基：對于車聯網絡拓撲G＝(V，E)，若有子圖滿足以下條件：

(1)其中

(2)都有或者v至少和中一個節點相鄰；

(3)是連通的；

則稱為網絡的G車聯網連通基；

定義連通元：連通基中的節點稱為連通元，不在連通基中的節點稱為普通節點；連通元節點控制著與其相連的普通節點，存儲其所控制普通節點的信息；

定理：對于網絡G，若存在連通基網絡中任意兩個節點都可通過連通基相連；

步驟2，構造車聯網的連通基

在車聯網連通基中，連通元節點承載普通節點的信息并且普通節點通信都交給連通基處理；

引入鏈路穩定度和節點重要度來構建連通因子，作為篩選連通元節點時的權值，所謂鏈路穩定度：

車聯網中車輛節點位置時刻變化，RSU節點位置不變，鏈路穩定度用節點之間鏈路的壽命來衡量；在計算鏈路壽命度時需要區分車輛間和車輛與RSU節點之間兩種情況；假設車輛節點對信號的傳輸力相同，即傳輸半徑相同，都為R_vehicle，RSU節點的傳輸能力比車輛節點強，為R_RSU，R_RSU＞R_vehicle；網絡時間一直同步，當兩個節點的距離小于通信半徑時，被認為是相連接的；每個車輛節點v_i都通過GPS獲得自己在網絡中的坐標(x_i，y_i)，RSU節點位置是固定的；Ve_i用來表示節點v_i的移動速度，θ_i表示節點v_i的移動方向；

車輛v_i，相對于車輛v_i的其它車輛v_j，兩者之間的鏈路壽命LET_i，j為：

其中a＝v_icosθ_i-v_jcosθ_j，b＝x_i-x_j，c＝v_isinθ_i-v_jsinθ_j，d＝y_i-y_j，θ表示兩輛車運行方向的夾角；

假設RSU節點v_R的位置為(x_R，y_R)，其與車輛節點v_i之間的鏈路壽命LET_i，R為：

其中

表示路邊基礎設施RSU節點與車輛節點之間的夾角；

式(1)、式(2)分別給出了車輛與車輛之間和車輛與RSU節點之間鏈路壽命計算公式；

定義節點v_i的鏈路穩定度，為

其中表示節點v_i與其鄰居節點的鏈路壽命之和；節點v_i的鏈路穩定度可衡量節點v_i與鄰居節點之間鏈路的穩定程度；

所謂節點重要度：

使用節點所在局域網絡的節點數目來度量此節點的重要性；

定義 局域節點集LN(v_i)：對于節點v_i，其局域節點集是指由節點v_i的一跳鄰居節點集Ne₁(v_i)和二跳鄰居節點集Ne₂(v_i)組成的節點集合，也就是

LN(v_i)＝Ne₁(v_i)∪Ne₂(v_i) (4)

定義節點v_i的權重定義為

w_i＝|LN(v_i)| (5)

w_i表示節點v_i局域節點集中節點的數目；

依據式(5)，節點v_i的權重取決于節點v_i的Ne₁(v_i)和Ne₂(v_i)的節點數目，Ne₁(v_i)的節點數目為節點v_i的度，Ne₂(v_i)的節點數目則為v_i鄰居節點度之和；那么節點v_i的度和其鄰居節點的度共同決定了其權重大小，節點度和鄰居節點度越高，該節點越重要；

定義節點v_i的重要度為

步驟3，構建車聯網分布式的連通基

步驟3.1，每個車輛節點維護以下核心數據結構：

·鄰接節點信息表

對于任意節點v_i，其鄰居節點信息列表表示為NeiList_i，NeiList_i1存儲節點v_i的1跳鄰接節點信息，NeiList_i2存儲節點v_i的2跳鄰接節點信息，具體包括：節點ID，節點連通因子Γ以及節點是否已被選為連通元節點CC；

對于有NeiList_i[v_j].ID＝ID(v_j)，

NeiList_i[v_j].Γ＝Γ_j，

·鄰接連通元表

對于任意節點v_i，其鄰接連通元表表示為CCList_i，

CCList_i＝{v_j|NeiList_i[v_j].IfCC＝1∧v_j∈Ne₁(v_i)}；

步驟3.2，包括三個階段：步驟3.2.1、發起節點篩選；步驟3.2.2、連通樹構造；步驟3.2.3、連通樹連接；

所述步驟3.2.1、發起節點篩選：

在每個局域網絡選取各自的發起節點，局域網絡是指發起節點的2跳鄰居節點集合組成的網絡，所選中的發起節點的連通因子應該是最大的；發起節點篩選過程從任意節點開始，每個節點把其InitID初始化為自己的ID；節點之間首先發送兩次Hello消息來獲取其2跳鄰居節點集合Ne₂(v)，然后根據各個節點d(v)，Vel(v)，Dir(v)計算節點的連通因子Γ(v)；接著每個節點廣播Beacon消息，包含自身ID，m(v)，InitID(v)，Γ(v)和InitiatorFlag；為了確保Γ(InitNode)最大，此Beacon消息發送三遍；兩個Beacon周期之后，若節點v的InitID(v)保持不變，則設置Initiator Flag，以此來標記節點v已經被選為發起節點；當收到第三條Beacon消息并且Initiator Flag的值為1時，節點v就把自己的狀態設為連通元；

至此發起節點篩選階段結束，所選發起節點為局域網絡中連通因子最大的節點，并且局域網絡中所有節點的InitID都變為其發起節點ID；

所述節點d(v)：表示節點度，與鄰居節點的連接數；

所述Vel(v)：表示節點V行駛速度；

所述Dir(v)：表示節點V行駛方向；

所述m(v)：表示節點v的狀態，取值0到4，分別表示初始狀態，被覆蓋狀態，連通元，普通節點；

所述InitID(v)：表示發起節點V；

所述步驟3.2.2連通樹構造：

從發起節點開始構建連通樹，目的是構造覆蓋每個發起節點2跳鄰居節點Ne₂(v)這個局部網絡的連通基，即連通樹；這階段的算法應滿足如下規則：

·若連通元節點v只有一個鄰居節點u，則把u送入S₁并令m(v)＝1；

·若連通元節點v的鄰居節點u有處于S₀狀態的鄰居節點，并且鄰居節點u的連通因子最大，則把u送入S₂并令m(v)＝2；

·若節點v為普通節點，且處于S₁狀態，并且沒有鄰居節點處于S₀狀態，則把u送入S₃并令m(u)＝3；

至此，所有節點都為連通元或者普通節點狀態，篩選出的連通元組成發起節點2跳范圍這個局域網絡的連通樹，并且每個普通節點都確保有一個連通元來支配；

所述步驟3.2.3連通樹連接：

通過選取一些普通節點作為連通元把相鄰接的連通樹連接起來，如果收到鄰居節點發送來的Beacon信息，此鄰居節點處于S₂或者S₃狀態，所述鄰居節點所持有的InitID不同于自己的InitID，表明此鄰居節點來自于不用的連通樹，發送CT通知鄰居節點其為邊界節點。