基于拓扑凝聚图的机会网络关键节点评估

机会网络是一种不需要源节点与目的节点之间存在稳定链路，利用节点移动带来的相遇机会实现通信的自组织网络^[1].机会网络以“存储—携带—转发”的模式传递信息，信息多跳转发时，网络会面临关键节点失效导致网络分割或连通性^[2]下降等问题.因此，评估网络中的关键节点对于优化和维护网络，增强网络连通性都具有非常重要的意义.

关键节点评估方法主要包括基于单一参数和基于多参数的方法.基于单一参数的方法有节点收缩^[3]等；基于多参数的方法有多属性决策^[4]、多参数节点排序^[5]、关键区域识别^[6]等.但这些大多是针对静态网络，未考虑机会网络的时变性，使得这些指标不再适用于机会网络关键节点的评估.因此，需要根据机会网络的特性构建相应的指标评估关键节点.

针对机会网络的时变性构建拓扑凝聚图模型，刻画动态变化的拓扑；结合机会网络中节点的局部特性、行为特性以及全局特性，定义二阶节点度、连接强度以及关键域重要度3个评估指标，在此基础上采用欧式距离评估机会网络中的关键节点.

1 机会网络的特性

从局部特性、行为特性以及全局特性3个方面表征机会网络的特性，在此基础上构建反映节点重要性的评估指标.

1.1 局部特性

机会网络的局部特性可用节点的局部连接情况表示.常用节点度表征节点的局部重要性.但节点度反映的仅是邻域内的连接情况，不能表征邻域外的交互情况.当网络中存在“桥节点”或度相同的节点时，节点度无法反映该节点的重要性.因此，可将节点的直接邻居扩展到多跳邻居.机会网络基本不存在端到端的连接，节点间通过移动转发的模式通信，因此，网络中的节点大多处于游离态，只有极少数的节点间存在连接.为降低计算复杂度，考虑节点的2跳邻居，用二阶节点度表征节点的局部重要性，该指标可以识别出“桥节点”的情况.

1.2 行为特性

机会网络大多是以人为主体通过携带通讯设备而产生的网络，因而具有一定的社会性.在社会生活中，与他人交互的频率通常可反映出关系的紧密程度.两人联系的次数越多，联系时间越长，说明两人关系越紧密，相互之间越重要.基于图论的相关理论，给节点间的连边赋予一定的权重，表征节点之间的紧密程度，紧密程度越大，连边的权重越大.考虑将某段时间内节点对间发生连接的总次数和总时长的乘积作为节点间连边的权重，用节点与邻居节点的权重之和表征节点的关系特性.

1.3 全局特性

机会网络具有一定的社团属性，相比社团内部节点，社团间节点维持不同社团之间的数据传输.这些节点大多处于网络的中心，经过这些节点传递的数据以及传输的路径更多.这些节点发生故障会影响网络的数据传输.介数中心性和接近中心性均能较为准确地发现静态网络中心位置的节点.在对机会网络的动态拓扑进行表示的基础上研究表征节点全局特性的指标.结合机会网络的稀疏性，考虑某个范围内节点的介数中心性和接近中心性，将两者的乘积作为机会网络节点全局特性的一个指标.

2 机会网络关键节点评估方法

对机会网络动态变化的拓扑进行表示，结合机会网络的特性构建评估指标，通过建立评估模型对关键节点进行评估，同时给出关键节点评估算法.

2.1 动态拓扑表示

机会网络的时变性使得网络的拓扑结构不断变化，准确描述这种变化是评估关键节点的前提.将总时长分割成一系列时间窗口，在每个时间窗口内，将所有发生通信的节点互相连接起来，即将时间窗口内的动态拓扑凝聚成一系列静态网络拓扑图.

定义1拓扑凝聚图

拓扑凝聚图集合G={G₁, G₂, …, G_n}是一系列时间窗口(t₀, t₁], (t₁, t₂], …, (t_n-1, t_n]的有序图集, 且(t₀, t_n]=T，(t₀, t₁]=(t₁, t₂]=…=(t_n-1, t_n]=Δt，G_i=(V_i, E_i, ω_i)表示时间窗口(t_i-1, t_i]内的拓扑凝聚图，即第i个时间窗口内节点间边的凝聚结果，V_i为该时间窗口内的节点集合，E_i为该时间窗口内发生连接的节点间边的集合，ω_i为边集E_i各边的权值所构成的集合.

定义2拓扑凝聚图权值

在拓扑凝聚图G_i=(V_i, E_i, ω_i)中，节点对之间边的权值集合ω_i定义为该时间窗口内节点对之间连接次数与连接时长之积，定义为

$ \begin{array}{c} \omega_{i}:=\{\omega_{a b}^{i}=H \sum\limits_{k=1}^{H}\left(t_{k- ext { end }}^{a b}-t_{k- ext { stant }}^{a b}\right) | \forall a, \\ b \in V(a eq b) \wedge(a, b) \in E , \\k \in N^{*}, H \in N\} \end{array} $

(1)

其中：ω_abⁱ为第i个拓扑凝聚图中节点a与b之间边的权值，H为第i个时间窗口内节点a与b建立连接的次数，k为节点a与b第k次建立连接，t_k-end^ab为节点a与b第k次连接断开的时刻，t_k-start^ab为节点a与b第k次连接开始的时刻.

根据定义1和定义2，可以对机会网络的动态拓扑进行表示，得到如图 1所示的模型.

2.2 关键节点评估指标

用二阶节点度、连接强度以及关键域重要度3个评估指标表征节点在机会网络中的重要程度，定义如下.

定义3二阶节点度

给定拓扑凝聚图集合G={G₁, G₂, …, G_n}，在拓扑凝聚图G_i中，任意节点a的邻域为α_a，即与节点a邻接的节点集合，α_a={b|(a, b)∈E}，b是a的邻接节点，设b的节点度为K_b, 定义节点a的二阶节点度为

$ D_{a}=\sum\limits_{b \in \alpha_{a}} K_{b} $

(2)

节点a的二阶节点度不仅能反映节点a与邻接节点间通信的情况，而且能够体现与a不直接相邻的节点与节点a间接通信的情况.

定义4连接强度

在拓扑凝聚图G_i中，任意节点a的连接强度定义为与节点a连接的所有边的权值之和，节点a的连接强度定义为

$ Q_{a}=\sum\limits_{b \in \alpha_{a}} \omega_{a b} $

(3)

其中ω_ab为节点a和b连边的权值.

连接强度反映了目标节点与周围节点相互通信的紧密程度，某个节点的连接强度越大，则该节点作为局部网络枢纽的可能性越大.

定义5关键域重要度

在节点a的邻域α_a中，任意2个节点h、j的邻域分别为α_h、α_j，定义a的关键域为F_a={s|s∈(α_h∩α_j)∪α_a, s≠a}，B_a表示F_a中任意节点对之间不经过a的最短路径数，S_a表示F_a中任意节点对之间经过a的最短路径数.设a的节点度为K_a，基于关键域节点a的介数定义为

$ G_{a}=\left\{\begin{array}{l}{0, \quad K_{a}=1} \\ {\frac{S_{a}}{S_{a}+B_{a}}, \quad K_{a} \geqslant 2}\end{array}\right. $

(4)

F_a中节点a到b的长度(最短跳数)用d(a, b)表示，基于关键域的节点a的接近度定义为

$ C_{a}=\frac{1}{\sum\limits_{b \in F_{a}} d(a, b)}, a eq b $

(5)

定义节点a的关键域重要度为

$ I_{a}=G_{a} C_{a} $

(6)

节点的关键域重要度越大，表明节点位于网络中心的可能性越大，节点越重要.

2.3 关键节点评估模型

从多个角度考虑机会网络的特点，建立了反映节点重要性的3个评估指标，提出基于欧式距离的评估模型，综合考虑节点的二阶节点度、连接强度以及关键域重要度评估机会网络中的关键节点.

给定节点的二阶节点度D_a、连接强度Q_a以及关键域重要度I_a，将这3个指标归一化后，定义节点a的欧式距离，即评估模型为

$ U_{a}=\sqrt{\left\|D_{a}\right\|^{2}+\left\|Q_{a}\right\|^{2}+\left\|I_{a}\right\|^{2}} $

(7)

节点的模型值越大，则该节点成为关键节点的可能性越大.

2.4 关键节点评估算法的设计

评估机会网络关键节点的算法如下.

算法1基于拓扑凝聚图的机会网络关键节点评估算法

输入：数据集U，时间窗口Δt，总时长T.

输出：关键节点的编号.

步骤1用Δt对T切片，建立第一个时间窗口内的拓扑凝聚图模型，获取节点的评估指标值.

步骤2对3个评估指标值归一化处理后作为评估模型的输入，输出得到节点的模型值，模型值最大的节点为疑似关键节点.

步骤3重复实验步骤1~2，获取其余时间窗口内的疑似关键节点编号.

步骤4统计每个节点被判定为疑似关键节点的次数，并按由大到小的顺序排列.

步骤5输出排序靠前的节点编号.

3 仿真实验设计与分析

设计不同场景和时间窗口下的对比仿真实验，与目前常用的介数中心性方法对比验证本文评估模型的合理性和有效性.

3.1 仿真实验设计

采用机会网络环境模拟器(ONE，opportunistic network environment)进行仿真实验，设置3个不同的实验场景获取仿真实验数据集，数据集格式为:节点ID、节点ID、连接开始时刻、连接结束时刻.使用Matlab2014a对数据集进行分析处理.仿真实验参数设置见表 1，其中，区域内节点的移动模型为随机路径点(RWP，RandomWayPoint)，区域间节点的移动模型为基于地图移动(MBM，map based movement).

关键节点失效会导致网络分割，从网络分割程度不同的角度评估关键节点.考虑关键节点失效导致网络某个区域分割的情况，设置实验场景1；考虑关键节点失效导致网络多个区域分割的情况，设置实验场景2；考虑关键节点失效导致网络所有区域分割的情况，设置实验场景3.

仿真实验场景如图 2所示，设置如下.

1) 场景1:包含A~D共4个区域，区域内部节点随机移动，区域之间有1~4号共4个节点按固定路径移动，如图 2(a)所示.

2) 场景2:包含A~F共6个区域，区域内部节点随机移动，区域之间有1~6号共6个节点按固定路径移动，如图 2(b)所示.

3) 场景3:包含A~E共5个区域，区域内部节点随机移动，有1~5号共5个节点按固定路径移动，如图 2(c)所示.

3.2 实验结果及分析

由于区域内部节点随机游走，且节点密度和通信半径都较大，故暂不考虑区域内部节点，网络的关键节点从区域间的节点中产生. 3个场景下，每个区域间节点被判定为疑似关键节点次数的统计结果如图 3~5所示.

场景1中，若3号节点失效会使区域A从整网分割出去，故该节点是关键节点.由图 3可知，3号节点的疑似关键节点次数最多，是评估出的关键节点，与实际相符.本文模型中，3号节点在10、20、30 min时的疑似关键节点次数分别为25、19、12，评估准确度分别为41.7%、63.3%、60%.场景2中，若3号或4号节点失效会使网络分割成ABC、DEF两个不连通的区域，故3号和4号节点是关键节点，与图 4显示的评估结果一致.本文模型中，3号和4号节点在10、20、30 min时的疑似关键节点次数分别为43、24、13，评估准确度分别为71.7%、80%、65%.场景3中，1号节点失效会导致网络所有区域产生分割，该节点是关键节点，与评估结果一致.本文模型中，1号节点在10、20、30 min时的疑似关键节点次数分别为52、30、18，评估准确度分别为86.6%、100%、90%.

不同时间窗下的对比实验结果表明: 20 min比10 min情况下的准确度更高，30 min时的准确度有所下降，且低于介数中心性方法.这是由于随着时间窗的增大，时间窗口内节点间的连接更密集，将其作为一个时间切片计算各个指标的值，不符合机会网络连接稀疏性的特点，导致评估结果的准确度有所下降，故时间窗取20 min左右时评估效果较好.

综上所述，这3个场景代表了关键节点失效导致网络分割的典型情况，笔者提出的关键节点评估模型可以准确评估出不同场景下机会网络的关键节点，该模型具有有效性.

4 结束语

提出了机会网络关键节点评估指标，通过3个评估指标刻画机会网络运行过程中的节点重要性.与介数中心性方法的对比实验结果验证了评估指标的有效性和优越性.此外，不同时间窗下的实验结果进一步表明，时间窗取20 min时具有较高的评估准确率.下一步考虑将该方法运用到实验床实验中，以验证所提出评估模型的有效性.