[發(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
• 代理公司: 南京天華專利代理有限責任公司 32218
• 代理人: 徐冬濤

技術(shù)領(lǐng)域

本發(fā)明屬于機動節(jié)點間拓撲構(gòu)建技術(shù)，特別是一種高速機動節(jié)點的安全拓撲構(gòu)建方法。

背景技術(shù)

目前，隨著信息化進程的深入發(fā)展，越來越多的企業(yè)和個人加入到Internet中，人們的工作與生活越來越與計算機網(wǎng)絡(luò)緊密聯(lián)系在一起。計算機網(wǎng)絡(luò)廣泛輔助人們的工作中，一方面改變?nèi)藗円酝墓ぷ鞣绞剑瑫r人們對一個可靠穩(wěn)定的網(wǎng)絡(luò)環(huán)境產(chǎn)生了強烈的要求。在網(wǎng)絡(luò)廣泛覆蓋的環(huán)境中，網(wǎng)絡(luò)系統(tǒng)節(jié)點呈現(xiàn)無中心特點，網(wǎng)絡(luò)系統(tǒng)也不可能始終保持連續(xù)的能量，所以在現(xiàn)實網(wǎng)絡(luò)環(huán)境中由于網(wǎng)絡(luò)結(jié)構(gòu)、數(shù)據(jù)流向等原因出現(xiàn)實際的關(guān)鍵節(jié)點，這些事實上的中心點，與比鄰節(jié)點相比，轉(zhuǎn)發(fā)數(shù)據(jù)可能性大，該節(jié)點負荷較重，容易發(fā)生分組丟失、重發(fā)等情況，進一步加劇此處能量消耗，一旦能量消耗殆盡，該節(jié)點癱瘓，造成鏈路斷裂，引起網(wǎng)絡(luò)性能下降。網(wǎng)絡(luò)故障和數(shù)據(jù)流瓶頸等重要信息能直觀的反映在網(wǎng)絡(luò)拓撲上，所以通過拓撲控制來改善網(wǎng)絡(luò)性能已經(jīng)獲得廣泛研究。

移動自組網(wǎng)絡(luò)節(jié)點間組網(wǎng)拓撲控制主要面向的研究方向是：在網(wǎng)絡(luò)覆蓋度和連通度得到滿足的前提下，采取骨干網(wǎng)節(jié)點選擇以及功率控制，對節(jié)點之間不必要的通信鏈路進行清除，形成一個數(shù)據(jù)轉(zhuǎn)發(fā)的優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)。在拓撲控制方面已經(jīng)有很多的研究，提出的拓撲控制算法大體可以劃分為分布式算法和集中式算法兩種類型，從其實施手段上看，可以分為鏈路控制轉(zhuǎn)發(fā)與功率控制。和集中式算法相比較，由于機動節(jié)點組網(wǎng)具有動態(tài)變化的特性，分布式算法更能適應(yīng)網(wǎng)絡(luò)拓撲的這種不斷變化，適于維護網(wǎng)絡(luò)的連通性、優(yōu)化網(wǎng)絡(luò)的吞吐量、節(jié)省能量和增加網(wǎng)絡(luò)的容錯性。

發(fā)明內(nèi)容

本發(fā)明的目的是針對移動自組網(wǎng)絡(luò)節(jié)點間組網(wǎng)拓撲控制的問題，提出一種高速機動節(jié)點的安全拓撲構(gòu)建方法，通過鏈路轉(zhuǎn)發(fā)控制的方式，在完成拓撲構(gòu)造以后，各個節(jié)點維護自己在拓撲結(jié)構(gòu)中的鄰居節(jié)點，僅由拓撲結(jié)構(gòu)中的鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包，從而達到控制洪泛，優(yōu)化網(wǎng)絡(luò)性能的目的。

本發(fā)明的技術(shù)方案是：

一種高速機動節(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邊(是Gabriel圖的邊，Gabriel圖是K.R.Gabriel于1969年首次提出的)，節(jié)點u標記所有的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)邊集合。

本發(fā)明的收集兩跳以內(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é)點加入到自己的一跳鄰居表中；