[發明專利]一種改進Delaunay三角剖分的虛擬力算法部署節點方法

有效

• 申請號: 201811038870.2
• 申請日: 2018-09-06
• 公開（公告）號: CN109068334B
• 公開（公告）日: 2021-06-18
• 發明（設計）人: 劉忠濤;陳小輝
• 申請（專利權）人: 三峽大學
• 主分類號: H04W16/18
• 分類號: H04W16/18;G06F9/455
• 代理公司: 宜昌市三峽專利事務所 42103
• 代理人: 吳思高

1.一種改進Delaunay三角剖分的虛擬力算法部署節點方法，其特征在于：在節點自部署網絡的Delaunay三角剖分鄰接節點集中，選擇最佳鄰接關系作為節點新的鄰接關系節點集；

包括以下步驟：

S1、初始化分布n個節點，設置總的迭代次數，對節點進行Delaunay三角剖分，獲取節點的鄰接節點集S_i,(i＝1,2,…,n)；

S2、采用最佳鄰接關系選擇策略，對鄰接節點集S_i,(i＝1,2,…,n)，進行選擇，獲取新的鄰接關系節點集S_Ni,(i＝1,2,…,n)；

S3、采用新的鄰接關系節點集S_Ni,(i＝1,2,…,n)計算節點之間的虛擬力，并進行位置更新計算，獲取新的節點分布坐標，新的節點坐標滿足邊界節點與邊界距離D＝R/2,R為節點的感知半徑；

二維覆蓋問題虛擬力位置公式：

其中，(x_{i_old},y_{i_old})為節點i更新前的坐標，(x_{i_new},y_{i_new})，為節點i更新后的坐標，為節點在網絡中所受虛擬力合力，為節點在網絡中所受虛擬力合力在x方向的分量，為節點在網絡中所受虛擬力合力在y方向的分量；Maxstep為虛擬力算法中位置更新移動最大步長；

S4、判斷是否完成迭代次數，設定迭代次數完成則停止迭代，否則，進行S2；

虛擬力計算模型為：

式中，表示在節點s_i受節點s_j的虛擬力，ω_A為虛擬力的引力系數，ω_R為虛擬力的斥力系數，α_ij為節點s_i指向節點s_j的單位方向向量，d_ij表示節點s_i與節點s_j之間的歐氏距離，D_th表示節點s_i與節點s_j之間的歐氏距離的閾值大小，C_th為虛擬力截斷距離；D_th取值為C_th取值為2*R或2.5*R；當d_ijD_th時，節點s_i受節點s_j的引力；當d_ij＝D_th時，節點s_i受節點s_j的虛擬力為0；當d_ijD_th時，節點s_i受節點s_j的斥力。

2.根據權利要求1所述一種改進Delaunay三角剖分的虛擬力算法部署節點方法，其特征在于：所述最佳鄰接關系選擇策略分為三步，以節點O為分析對象，包括：

(1)：在全局網絡中，通過Delaunay三角剖分定義節點O的鄰接節點集S_O；

(2)：選擇鄰接節點集S_O中與節點O的歐式距離最小的點A，節點O與節點A在Delaunay三角剖分有△OAB和△OAC；

(3)：在四邊形OBAC中比較線段OB和線段OC的長度，若線段OB的長度小于線段OC的長度，那么選擇節點A和節點B作為節點O新的鄰接節點集S_ON，否則選擇節點A和節點C；

節點O的最佳鄰接關系選擇的新鄰接節點集為S_ON，節點O所受虛擬力只與新鄰接節點集S_ON中關聯的節點有關，與非鄰接節點無關。