[發(fā)明專利]高速機動節(jié)點的安全拓撲構(gòu)建方法

有效

• 申請?zhí)枺?/td>: 201110358885.9
• 申請日: 2011-11-14
• 公開（公告）號: CN102420730A
• 公開（公告）日: 2012-04-18
• 發(fā)明（設(shè)計）人: 李千目;戚湧;劉剛;李齊鳴
• 申請（專利權(quán)）人: 無錫南理工科技發(fā)展有限公司
• 主分類號: H04L12/28
• 分類號: H04L12/28;H04L12/24
• 代理公司: 南京天華專利代理有限責(zé)任公司 32218
• 代理人: 徐冬濤

1.一種高速機動節(jié)點的安全拓撲構(gòu)建方法，其特征是它包括步驟如下：

第一步，每個節(jié)點u計算它本身和其兩跳以內(nèi)鄰居節(jié)點集N₂(u)中所有節(jié)點的節(jié)點信息，節(jié)點u根據(jù)它本身和其兩跳以內(nèi)鄰居節(jié)點集的節(jié)點信息，調(diào)用Delaunay三角剖分方法得到節(jié)點u兩跳以內(nèi)的Delaunay三角剖分平面拓撲圖Del(N₂(u))，完成本地拓撲圖的構(gòu)造；

第二步，對于Del(N₂(u))中的任意邊uv，令△uvw和△uvz為依附于uv的兩個三角形，如果∠uwv和∠uzv都小于π/2并且||uv||≤1，那么認定uv是一條Gabriel邊，節(jié)點u標(biāo)記所有的Gabriel邊uv，這些邊將不會被刪除；

第三部，每個節(jié)點u在Del(N₂(u))中找到所有三邊均不大于1的三角形△uvw，如果∠wuv≥π/3，節(jié)點u以廣播方式向其一跳以內(nèi)鄰居節(jié)點集N₁(u)中的各節(jié)點發(fā)一個建議三角形uvw加入拓撲圖的信息即proposal(u，v，w)信息，并對其鄰居節(jié)點發(fā)來的信息進行監(jiān)聽；

第四步，節(jié)點u收到一個proposal(u，v，w)信息后，如果△uvw不屬于節(jié)點u兩跳以內(nèi)Delaunay三角剖分平面拓撲圖，則節(jié)點u拒絕構(gòu)造△uvw，向其一跳以內(nèi)鄰居節(jié)點集N₁(u)中的各節(jié)點廣播拒絕三角形uvw加入拓撲圖的信息即reject(u，v，w)信息，否則，節(jié)點u同意這個建議，并向N₁(u)中的節(jié)點廣播接受三角形uvw加入拓撲圖的信息即accept(u，v，w)信息；

第五步，如果△uvw在Del(N₂(u))中，并且節(jié)點v和w曾經(jīng)發(fā)送過accept(u，v，w)或proposal(u，v，w)，那么節(jié)點u將把邊uv和uw加入它的關(guān)聯(lián)邊集合。

2.根據(jù)權(quán)利要求1所述的高速機動節(jié)點的安全拓撲構(gòu)建方法，其特征是所述的收集兩跳以內(nèi)鄰居節(jié)點集N₂(u)中節(jié)點信息的方法是：

節(jié)點u采用周期發(fā)送Hello消息的方式，各節(jié)點將能正確接收到一跳鄰居信息的節(jié)點建立一跳鄰居表；即節(jié)點u用組播地址發(fā)送hello包，所有收到u發(fā)送來hello包的節(jié)點都把u添加到一跳鄰居表中，并向u回發(fā)一個hello包，u收到這些包后會檢查這些包，如果包中含有自己的ID，則把那個節(jié)點加入到自己的一跳鄰居表中；

二維Local?Delaunay三角剖分拓撲圖構(gòu)建方法LDel(2)需要收集兩跳鄰居信息：即每個節(jié)點都需要維護兩個鄰居表：一跳鄰居表和兩跳鄰居表，兩張表共同構(gòu)成了物理鄰居表，即首先，節(jié)點周期性廣播自己的一跳鄰居表，收到其他節(jié)點發(fā)來的一跳鄰居表則更新自己的兩跳鄰居表。

3.根據(jù)權(quán)利要求1所述的高速機動節(jié)點的安全拓撲構(gòu)建方法，其特征是所述的節(jié)點計算它本身和其兩跳以內(nèi)鄰居節(jié)點集N₂(u)的Delaunay三角剖分Del(N₂(u))的具體步驟如下：

第一步，建立初始網(wǎng)格：假設(shè)給定點集首先選擇一個足夠大的輔助三角形能夠包含V中全部的點，將其作為初始Delaunay三角網(wǎng)格；

第二步，逐點插入：設(shè)已有Delaunay三角網(wǎng)格T，現(xiàn)在欲插入一個新點P：首先，找出所有外接圓包含P點的三角形，接著找出離P點最近的邊并將之刪除，從而形成一個Delaunay空腔；其次，將空腔的每一個頂點與新插入點P連接，即完成了P點的插入；

第三步，計算區(qū)域以外點的刪除：當(dāng)點集V中全部的點都插入完成后，對于相對簡單的凸單連通區(qū)域，將與輔助三角形頂點相連的全部三角形直接刪除；對計算區(qū)域以外的三角形進行刪除的同時確保界面的正確三角剖分，至此完成了對點集V的Delaunay三角剖分。