利索能及
我要发布
收藏
专利号: 2021102551475
申请人: 中山大学
专利类型:发明专利
专利状态:已下证
更新日期:2025-11-27
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种基于邻接矩阵构造的跳数矩阵恢复方法,其特征在于:所述的方法包括步骤如下:S1:由于不完整的泛洪过程或者恶意节点的攻击,获取的跳数矩阵 中含有缺失项;

S2:如果跳数矩阵 中,缺失的跳数的对称位置被观测到,使用对称位置跳数将其补全;

S3:通过缺失的跳数矩阵 推断出不同节点对之间的连通性,从而得到邻接矩阵A=[aij]n×n,i=1,...,n;j=1,...,n;

S4:采用最短路径算法对步骤S3得到的邻接矩阵进行处理,得到初步的跳数矩阵;

S5:对初步得到的跳数矩阵进行遍历,对于没有跳数值的位置,使用邻居补全的跳数值代替,从而恢复得到完整的跳数矩阵;

步骤S3,具体的,

S301:对于被观测到的跳数位置,若节点i到节点j的跳数值为1,则这两个节点可以直接通信,邻接矩阵对应的位置为1;反之,两个节点在邻接矩阵中对应的位置为0;

S302:对于跳数缺失的位置,若节点i和节点j相对于网络中其它任意节点k,存在节点i到节点k的跳数值与节点k到节点j的跳数值之差大于1,则邻接矩阵对应的位置为0;否则进入下一步;

S303:采用初步补全方法补全跳数矩阵 若节点i和节点j相对于网络中其它任意节点k,若存在节点i到节点k的跳数值和节点k到节点j的跳数值之差大于3,且对应的两个跳数值都为补全的跳数,则邻接矩阵对应的位置为0;否则进入下一步;

S304:判断网络中是否存在任意节点k,使得节点i到节点k的跳数值和节点k到节点j的跳数值之差大于2,且对应的两个跳数值中有一个为补全的跳数,则邻接矩阵对应的位置为

0;否则邻接矩阵对应的位置为1;

S305:若邻接矩阵补充完整,则进行下一步,否则回到步骤S302。

2.根据权利要求1所述的基于邻接矩阵构造的跳数矩阵恢复方法,其特征在于:步骤S1,构造的缺失跳数矩阵 表示如下:其中,⊙表示Hadamard乘积;Ω=[ωij]n*n表示一个随机观测矩阵,ωij表示跳数矩阵对应位置是否缺失,表示为:其中,i=1,....,n;j=1,....,n。

3.根据权利要求2所述的基于邻接矩阵构造的跳数矩阵恢复方法,其特征在于:所述的初步补全的方法:如果节点i和节点j之间的跳数值hij缺失,则使用节点i的邻居到节点j的跳数和节点j的邻居到节点i的跳数的平均值,来补全缺失的跳数值hij。

4.根据权利要求3所述的基于邻接矩阵构造的跳数矩阵恢复方法,其特征在于:所述的初步补全方法,具体如下:对于一个跳数缺失的值 初始化两个邻居列表Li和Lj,根据跳数向量 选择节点i的邻居,根据跳数向量 选择节点j的邻居;节点i的邻居节点的索引存储在邻居列表Li中,节点j的邻居节点的索引存储在邻居列表Li中;变量ni表示节点i的可用邻居节点,变量nj表示节点j的可用邻居节点数;如果观察到邻居节点Li(k)与节点j之间的跳数 则可用邻居节点ni加1。

5.根据权利要求4所述的基于邻接矩阵构造的跳数矩阵恢复方法,其特征在于:初步补全的跳数值由下式得到:其中, 表示矩阵初始补全后,节点i到节点j之间的跳数值。

6.根据权利要求5所述的基于邻接矩阵构造的跳数矩阵恢复方法,其特征在于:所述的最短路径算法为Floyd算法。

7.根据权利要求6所述的基于邻接矩阵构造的跳数矩阵恢复方法,其特征在于:所述的Floyd算法具体如下:假设节点k为中继节点,k=1,2,...,n,k≠i,k≠j,节点i为起始节点,i=1,2,...,n,节点j为到达节点,j=1,2,...,n;通过三次循环,在循环中比较aij与aik+akj的最小值,保存在aij中,来得到任意两个节点间的最短跳数。

8.一种计算机系统,包括存储器、处理器以及存储在存储器上并可在处理器上运行的计算机程序,其特征在于:所述的处理器执行所述的计算机程序时,实现如权利要求1~7任一项所述的方法的步骤。

9.一种计算机可读存储介质,其上存储有计算机程序,其特征在于:所述的计算机程序被处理器执行时,实现如权利要求1~7任一项所述的方法的步骤。