一种基于信任评估的连通支配集生成算法

黄庆东, 曹丽霞, 郭 欢, 袁润芝, 卢 茜

(西安邮电大学 通信与信息工程学院, 陕西 西安 710121)

无线自组织网络是由大量带有无线收发装置的节点组成的多跳网络，节点间通信不依靠基站、接入点等基础设施，主要通过节点间的相互协作和自我组织快速构建网络并实现网络通信，虚拟骨干网[1]的构建在无线自组织网络路由以及拓扑控制中起着至关重要的作用。支配集是构成骨干子网的节点集合，若支配集内任意两节点通过某路径连通则称为连通支配集(connected dominating set, CDS)，由连通支配集组成的虚拟骨干网可以有效管理网络拓扑[2-3]，减少网络信息的开销[4-5]。

基于功率选择的连通支配集构建算法[6]，以及考虑节点的覆盖范围和剩余能量构建的支配集[7]，都是为了减少能量的消耗。文献[8]考虑整个网络拓扑结构并对其进行分簇，由簇头节点组成连通支配集，不仅减少了支配集的规模还降低了网络的信息开销。文献[9]为得到最优的连通支配集，在网络中引入特征矢量中心性值对节点进行编号，避免了节点缩减的随机性，同时提出最大编号节点缩减规则，解决了在生成连通支配集时存在的完全NP难问题。但是上述支配集构建算法旨在缩减支配集的规模，节省能耗，均未考虑生成支配集时的网络恶意节点攻击问题，而信任评估[10]作为抵抗节点攻击的主要手段，可以有效避免无线自组织网络受到恶意节点的攻击[11]。为了去除恶意节点的虚假推荐信任，文献[12]提出了一种不可信推荐信任检测模型来过滤推荐值，对于可信推荐采用加权聚合的方式计算间接信任值，可以有效抵御诽谤、吹捧、随机意见攻击的影响。

信任评估是抵御网络内恶意节点攻击的有效工具，基于此,文章在构建连通支配集时引入间接信任评估机制来剔除支配集中存在的恶意节点，并对支配集的连通性进行判定与维护得到可信连通支配集，然后缩减冗余支配节点，以此提高连通支配集的可靠性和有效性。

1 信任评估模型

无线自组织网络中，节点的信任值被理解为该节点的可信程度，根据信任信息的来源将信任分为直接信任和推荐信任[13]。如图1所示，节点i，j有直接的交互，i可通过监测与j的直接交互经验得出j的直接信任值Ti,j；而节点i，k没有直接交互，i无法直接得出k的信任值，为增加信任评估的精确性需采用第三方节点j的推荐信任值Rj,k来评估节点k的信任值。

图1 信任关系

被评估节点k的第j(j=1,2,…,n)个推荐值的偏差因子dj可表示为[12]

(1)

其中median()为求中值函数,根据dj由大到小的顺序对推荐信任值进行排序。CR是AR对应于排序后的推荐信任集，依据排序顺序从推荐节点集逐次逐个选择可疑节点，补充放入可疑节点集SR，这样每次SR会增加一个节点，逐次对其计算相应的平滑因子[12]

s=|M[d(CR)-d(CR-SR)]|,

(2)

式中d(CR)表示所有偏差因子之和，CR-SR表示除可疑集后CR内剩余元素组成的集合，M表示剩余元素个数。

间接信任评估机制实现过程：利用式(1)计算每个推荐信任的偏差因子；根据偏差因子由大到小的顺序对AR排序得到集合CR，并按序从推荐节点集中逐个选择可疑节点，补充放入可疑集SR，利用式(2)计算每个可疑集对应的平滑因子s；选择s最大的最小可疑集为不可信推荐集。

节点i得到节点k的平均推荐信任为

(3)

式中n为推荐节点数量；节点i对节点k的间接信任值[14]

(4)

其中，N为n个推荐节点中可信推荐节点数量。

2 基于信任评估的可信连通支配集生成算法

将支配集概念引入Ad Hoc网络中构建虚拟骨干网，网络中的节点属于支配集，或者属于支配集的单跳邻居。针对无线自组织网络的恶意支配节点攻击问题，引入间接信任评估方式对于恶意节点进行检测，构建可信支配集，并对由恶意支配节点的剔除造成的CDS连通性破坏问题引入可达矩阵[15]进行判定与修护，保障其承担虚拟骨干网的功能。

假设可信支配集包含m个支配节点{v1,v2,…,vm}，定义可达矩阵P=(pij)m×m

(5)

A为可信支配节点生成的邻接矩阵，Am表示邻接矩阵A的m次幂矩阵，对幂矩阵求和

Q=A+A2+…+Am,

(6)

将矩阵Q内非零元素全部换为1，零元素不变即可求得可达矩阵P。

假设无线自组织网络内各节点位置确定并保持稳定的拓扑结构，每个节点具有唯一的节点编号且均可与其邻居节点建立稳定的通信链路，评估节点为可信节点，恶意节点在网络内不仅可与其邻居节点交换信息，而且对被评估节点发起诽谤、吹捧等攻击，影响虚拟骨干网的可靠性。预定义迭代周期为T，可信连通支配集构建算法具体过程如下。

步骤1根据网络拓扑结构，初始标记支配节点[16]，依据网络通信链路关系得到邻接矩阵。

步骤2选择网络中一个节点作为评估节点，评估节点的非邻居节点依次作为被评估节点，利用邻接矩阵寻找评估节点和被评估节点的共同邻居作为推荐节点。

步骤3每一时刻t=1,2,…,T，评估节点收集到推荐节点对被评估节点的推荐信任集AR，及评估节点对于推荐节点的直接信任集BT，利用推荐信任检测模型检测出不可信节点，保留可信节点，并按式(3)和式(4)求被评估节点的平均推荐信任值和间接信任值。

步骤4判断是否所有节点都经过检测，若是则检测结束；否则重新从剩余节点内选择一个评估节点，对其非邻居节点进行评估，重复步骤3，直到所有的节点都经过检测为止，剔除检测出的恶意支配节点得到可信支配集。

步骤5利用式(5)和式(6)计算可达矩阵P，判断可信支配集的连通性。若可达矩阵P内元素全为非零元素，则可信支配集连通，保存此可信支配集；若可达矩阵P内存在零元素，则可信支配集不连通，执行下一步。

步骤6若可信支配集不连通，寻找可信非支配节点中间接信任值最高的节点加入网络，验证可信支配集连通性。若连通则将此节点加入可信支配集，选择结束；若不连通，则重新选择间接信任值次高的可信非支配节点加入可信支配集继续判断其连通性，以此类推直到可信支配集连通。

步骤7若一个可信非支配节点加入可信支配集仍然无法连通，那就需要选择多个可信非支配节点加入，将间接信任值最高的可信非支配节点作为第一个新加入的支配节点，重复步骤6继续选择下一个可信非支配节点并验证其连通性，直到可信支配集连通。

步骤8对于可信连通支配集中存在的冗余支配节点，利用缩减规则[16]进行缩减得出最小的可信连通支配集。

无线自组织网络中可信支配集的构建，保证了由连通支配集组成的虚拟骨干网的可靠性，使支配节点间的数据传输更加可靠安全，而且是完全分布式计算方法，方便在全网络实施。

3 仿真结果及分析

利用Matlab2014a软件对于改进算法进行仿真验证。假设在1×1的单位区域中随机布署12个网络节点，节点的身份地位均相同且节点间的归一化通信距离为0.6，两节点之间连线表示存在通信链路即在互相的通信范围内，网络节点按照出现的先后顺序进行编号1～12。网络中随机设置一定数量的恶意节点，分别在诽谤攻击、吹捧攻击、随机意见攻击3种攻击类型下对于恶意支配节点进行检测。

以图2所示的网络模型为例，网络中恶意攻击节点为{7,10}，用“★”符表示；初始标记的支配节点为{1,2,3,4,5,6,8,10,11,12}，用“○”符表示；文献[16]未加信任评估时网络生成的连通支配集为{10,11,12}，用“□”符表示，恶意节点{10}为支配节点，影响连通支配集的可靠性。

图2 原连通支配集生成图

可信支配集算法构建过程如表1所示。表1中评估节点为2，被评估节点为7时，因为两节点无法直接交互，因此使用间接信任评估模型对于被评估节点进行评估，推荐节点为{1,4,10,11}且对应的推荐信任集和推荐者的可信集分别为

AR={0.47,0.485,0.282,0.425}，
BT={0.265,0.45,0.53,0.49}，

评估时首先利用式(1)计算每个推荐节点的偏差因子d，根据d由大到小的顺序对于推荐信任值进行排序得到

CR={0.282,0.485,0.47,0.425}，

排序后的推荐节点为{10,4,1,11}；其次按照CR排序顺序依次选定可疑集合SR，每个可疑集合利用式(2)计算其平滑因子s，可疑集合

SR={0.282}

对应的平滑因子最大(s=0.1551)，所以此可疑集合对应的推荐节点{10}为不可信节点，可信节点为{4,1,11}，以此类推将所有节点经过信任评估。恶意支配节点{10}从支配集中剔除掉，得到可信支配集{1,2,3,4,5,6,8,11,12}；利用可达矩阵判断其连通性并修护，对可信连通支配集中的冗余支配节点缩减得到最小可信连通支配集为{8,11,12}，如图3所示，“○”符表示网络中初始标记的支配节点为{1,2,3,4,5,6,8,10,11,12}；最小可信连通支配集为{8,11,12}，用“□”符表示。改进算法在生成可信支配集时将恶意支配节点从初始标记的支配节点集中剔除掉，选择可信支配节点构建连通支配集，从而使所生成的连通支配集更加可靠。

表1 可信支配集构建算法描述

图3 可信连通支配集生成图

由于网络拓扑随机生成，结果具有一定的偶然性，因此基于蒙特卡罗思想，独立进行100次实验，将其对应的平均值作为节点的间接信任值和平均推荐信任值并在不同攻击类型下与节点的实际信任值进行对比分析，以此验证信任模型对于恶意节点检测的有效性。

诽谤攻击节点故意推荐较低的信任值给评估节点，降低被评估节点信任值。如图4所示，可看出恶意节点存在时，被评估节点的平均推荐信任值低于其间接信任值和实际信任值；加入信任评估模型后滤除了恶意节点的推荐值，对于可信推荐值进行聚合的间接信任与被评估节点的实际信任值近乎相等；而对于节点11评估时，因推荐节点中无恶意节点，所以间接信任、平均推荐信任都接近于实际信任值。

吹捧攻击节点故意夸大被评估节点的信任值。如图5所示，恶意节点存在时，被评估节点的平均推荐信任值高于节点聚合的间接信任值与实际信任值；而经过信任检测后由于滤除了恶意节点对于被评估节点的影响，得到的间接信任值与实际信任值近乎相等；而对节点11评估时，因为推荐节点内没有恶意节点，所以其实际信任值、平均推荐信任以及间接信任值几乎相等。

图4 诽谤攻击时节点信任值

图5 吹捧攻击时节点信任值

随机意见攻击是以上两种攻击方式的合谋攻击。如图6所示，每个节点都经过了信任评估，由于恶意节点的随机意见攻击，被评估节点的平均推荐信任值相对于间接信任值和实际信任值出现上下波动；但是经过信任评估后剔除了恶意节点的影响，聚合的间接信任值接近于节点的实际信任值；对于节点{6,7}进行评估时，由于推荐节点内无恶意攻击节点，所以得到的平均推荐信任、间接信任、实际信任值三者几乎相等。

图6 随机意见攻击时节点信任值

4 结语

通过分析无线自组织网络中节点的信任评估机制，在构建连通支配集时，结合节点信任评估提出了可信连通支配集的构建方法。利用信任检测模型对网络中的恶意支配节点进行筛选并剔除，由此导致的可信支配集不连通问题采用选取可信节点加入的方式使可信支配集连通，其次对于可信连通支配集中的冗余支配节点进行缩减得到最小可信连通支配集。仿真结果表明，改进算法比原支配集算法，提升了虚拟骨干网的可靠性，且在抵抗诽谤、吹捧、随机意见攻击方面表现出良好的性能。