Fig. 1 MOSNs scenario
图1 MOSNs场景
刘琳岚 1 张 江 1 舒 坚 2 郭 凯 1 孟令冲 1
1 (南昌航空大学信息工程学院 南昌 330063) 2 (南昌航空大学软件学院 南昌 330063)
(liulinlan@nchu.edu.cn)
摘 要 提前获知或预测网络的关键节点,便可根据关键节点的相关信息对网络进行优化,当网络瘫痪时,可第一时间排查关键节点,减少网络维护时间和成本.现有静态无线传感器网络关键节点预测方法,不适用于机会传感器网络(opportunistic sensor networks, OSNs).针对机会传感器网络结构动态变化、消息传输时延高的特点,分析多区域机会传感器网络分层结构的消息传输过程,定义阶段贡献度反映Ferry节点在消息传输过程中的贡献程度,定义区域贡献度反映Ferry节点对区域的贡献程度.在此基础上,以Ferry节点在网络中的综合贡献度作为判断关键节点的依据,提出基于多属性决策中理想点法(technique for order preference by similarity to ideal solution, TOPSIS)的关键节点预测方法.实验结果表明:采用改进TOPSIS算法能够获得更高的预测精度;搭建了实验床以进一步验证提出的预测方法,结果表明,采用改进TOPSIS算法的预测精度更高.
关键词 机会传感器网络;关键节点;区域贡献度;阶段贡献度;多属性决策
机会传感器网络(opportunistic sensor networks, OSNs)是一种利用节点移动带来的相遇机会实现通信的自组织网络,具有移动自组织网络(mobile ad hoc network, MANET)和延迟容忍网络(delay tolerant network, DTN)的特点 [1] ,常被应用于野生动物追踪 [2] 、森林环境监测 [3] 以及智能交通 [4] 等方面,网络中某些节点的损坏可能导致整个网络运行不正常,甚至瘫痪,这种节点被称为关键节点.如能提前获知或预测网络的关键节点,便可根据关键节点的相关信息对网络进行优化,并尽可能地消除关键节点,以增强网络的健壮性;网络运行过程中,通过重点监视关键节点的状态、及时维护关键节点,以确保网络正常运行;一旦网络出现瘫痪,能够第一时间排查关键节点是否正常,可减少网络维护的时间和成本.本文研究OSNs的关键节点预测方法.
目前,主要有基于准则 [5-6] 、基于参数 [7] 和基于节点重要度 [8-9] 的关键节点预测方法.传统网络中关键节点的预测方法不再适用于机会传感器网络.本文针对OSNs消息传输时延高、网络拓扑变化频繁的特点,探索其关键节点的预测方法,为OSNs的实际应用提供支撑.
通过分析OSNs中区域节点与Sink节点之间的消息传输过程,以Ferry节点在该过程中的贡献衡量Ferry节点的重要程度,主要工作如下:1)将OSNs抽象成多区域机会传感器网络(multi-region opportunistic sensor networks, MOSNs);2)分析OSNs的拓扑特性,定义关键节点及割点;3)分析 OSNs的分层结构,将其消息传输过程分为3个阶段,定义Ferry节点的阶段贡献度及区域贡献度;4)提出基于改进多属性决策中理想点法(technique for order preference by similarity to ideal solution, TOPSIS)的OSNs关键节点预测方法;5)通过仿真实验和实验床实验验证本文提出的方法.
国内外学者对网络割点(关键节点)的判定 [5,10-12] 、节点重要度的评估 [13-15] 、多属性决策理论在无线传感器网络中的应用 [16-17] 进行了研究.
文献[5]将覆盖网络中的所有非叶子节点视为候选割点,每一个候选割点都可发起主动探测命令,如果某候选割点有2个或2个以上的邻居之间不存在回路,则认定该疑似割点为实际割点;文献[11]针对引起耦合网络级联失效的节点,提出Max-Cas算法,采用最大连通分支的节点数鉴别关键节点;文献[12]利用前一时刻的关键节点集更新动态网络的关键节点,达到自适应探测关键节点的目的,针对动态网络,提出无需重复计算的关键节点自适应检测算法;文献[6]提出适用于大规模ad hoc网络的分布式拓扑分割探测算法(distributed partition detection protocol, DPDP),若网络中节点的邻节点度 N 和基本回路度 M 满足 N - M ≥2,则判定该节点为割点.
文献[18]指出加权网络中,任意2个节点对之间最重要的节点是移除后使这2个节点间的最短距离增加最多的那个节点;文献[19]比较通信网络中生成树的数目评价任意数目的2组节点的重要程度;文献[20]考虑节点自身属性及其 m 阶邻居节点的属性,提出复杂网络的节点重要度评价方法;文献[8]利用领域“结构洞”判别社会网络的最具影响力节点,即关键节点;文献[7]综合考虑节点度、接近度 [21] 、介数 [22] 、等价拓扑结构、邻居列表的影响,评估节点在复杂网络中的重要程度;文献[9]针对节点删除法存在的不足,定义节点效率和节点重要度评价矩阵,利用重要度评价矩阵确定复杂网络的关键节点;文献[23]提出以节点“移除”导致的网络能耗值为衡量基准,并考虑节点剩余生命期,采用节点删除法评价节点在无线传感器网络中的重要程度.
文献[16]提出基于传感器节点信誉度集对分析的安全数据进行融合,并采用多属性决策方法选择转发下一跳数据的节点;文献[17]针对无线传感器网络易出现数据流量集中于少数路径的现象,提出基于多属性决策的能量平衡路由策略MADMR(multiple attribute decision making routing).
本文参考文献[6],考虑OSNs的传输特点,定义OSNs的关键节点及割点,定义区域贡献度反映区域对Ferry节点的依赖程度,采用多属性决策(multiple attribute decision making, MADM)方法预测OSNs的关键节点.
根据OSNs分层结构的特点,分析OSNs中关键节点的特点,定义OSNs关键节点、区域贡献度.
2.1 OSNs场景模型
本文研究场景如图1 [24] 所示,区域内感知节点发送消息至移动节点,移动节点通过1次或多次转发将消息发送至Sink节点.
Fig. 1 MOSNs scenario
图1 MOSNs场景
将一个区域抽象成一个“超级节点”,称为区域节点,得到MOSNs模型,如图2所示, R 1 , R 2 , R 3 , R 4 为区域节点, F 1 , F 2 , F 3 为Ferry节点.
Fig. 2 MOSNs model
图2 MOSNs模型
MOSNs由3类节点构成:Sink节点、Ferry节点和区域节点.区域节点负责感知周围物理世界,Sink节点负责汇聚网络消息,区域节点和Sink节点固定不动,相互之间不连通;Ferry节点负责转发消息,以随机游走或按一定规律在区域节点和Sink间移动,通过“存储—携带—转发”方式建立区域节点与Sink节点之间的通信.根据节点功能的不同,将整个网络划分为3层,如图3 [25] 所示.
Fig. 3 MOSNs hierarchical structure
图3 MOSNs的分层结构
2.2 MOSNs的关键节点
关键节点的概念来自图论,目前仍没有统一的定义.本文针对MOSNs的特点,以网络分裂概率为衡量标准,定义关键节点.
定义1. 关键节点.设 G 表示MOSNs,若 G 中某节点 F 移除后网络产生分裂的可能性最大,则称 F 为 G 的关键节点.
定义2. 割点.设 G 表示MOSNs,若移除某节点 C 后网络 G 产生分裂,则称 C 为网络 G 的割点.
由定义1、定义2得到推论1、推论2.
推论1. MOSNs的割点一定是关键节点.
证明. 由定义2可知,移除MOSNs的割点后,网络一定产生分裂.即移除MOSNs的割点后,网络产生分裂的概率为100%,故MOSNs的割点一定是关键节点.
证毕.
与传统无线传感器网络不同,MOSNs中Ferry节点的位置运动变化,其拓扑随之变化,即MOSNs处于间歇性连通状态,只要该间歇时间间隔在实际应用可容忍的范围内,便可认为整个网络是连通的.如果由于部分节点损毁、丢失或Ferry节点提供的通信机会不够频繁,使得网络的间歇时间间隔大于最大容忍值,便认为MOSNs不连通,也就是说,MOSNs结构出现了分裂,这些导致MOSNs产生分裂的节点就是关键节点.由上述分析可知,MOSNs的Ferry节点最有可能成为关键节点,但是,哪些Ferry节点是MOSNs的关键节点?这就是本文需要解决的问题.
为便于研究,本文进行如下假设:
1) 将每个区域抽象成一个“超级节点”,称区域节点;
2) 设Ferry节点的内存足够存储其经过区域时收集的全部消息;
3) MOSNs中区域节点、Ferry节点及Sink节点均有唯一的标识;
4) MOSNs已具备时钟同步机制.
2.3 阶段贡献度
Ferry节点是MOSNs的消息传输媒介,对整个网络至关重要,部分Ferry节点可能是关键节点.通过分析MOSNs的路由机制和分层结构,不难发现,感知消息从产生到最终投递到Sink的过程,可分为3个阶段:消息投递阶段、消息转发阶段和消息到达阶段,如图4所示:
Fig. 4 MOSNs message transmission process
图4 MOSNs消息传播过程
1) 消息投递阶段.Ferry节点将感知消息带离区域.
2) 消息转发阶段.消息在Ferry节点间转发.
3) 消息到达阶段.消息被Ferry节点投递至Sink.
定义3. 第1阶段贡献度(first stage contribu-tion, FSC).设时间 T 内,Sink收到 M j 条来自区域 R j 的消息,如果Ferry节点 F i 在消息投递阶段共接收 n i j ( n i j ≤ M j )条来自区域 R j 的消息,则 F i 对区域 R j 的第1阶段贡献度为 n i j 
M j ,记为 FSC ( F i , R j ).
定义4. 第2阶段贡献度(second stage contri-bution, SSC). 设时间 T 内,Sink收到 M j 条来自区域 R j 的消息,如果Ferry节点 F i 在消息转发阶段共转发 m i j ( m i j ≤ M j )条来自区域 R j 的消息,则 F i 对区域 R j 的第2阶段贡献度为 m i j M j ,记为 SSC ( F i , R j ).
定义5. 第3阶段贡献度(third stage contribu-tion, TSC). 设时间 T 内,Sink收到 M j 条来自区域 R j 的消息,如果Ferry节点 F i 在消息到达阶段共投递 k i j ( k i j ≤ M j )条来自区域 R j 的消息至Sink节点,且 F i 对区域 R j 的第3阶段贡献度为 k i j M j ,记为 TSC ( F i , R j ).
显然,FSC反映了Ferry节点在消息投递阶段对消息传输的贡献程度;SSC反映了Ferry节点在消息转发阶段对消息传输的贡献程度;TSC反映了Ferry节点在消息到达阶段对消息传输的贡献程度.
2.4 区域贡献度
定义6. 区域贡献度(region contribution, RC). 时间 T 内,若Ferry节点 F i 对区域 R j 的第1阶段、第2阶段、第3阶段的贡献度分别为 FSC ( F i , R j ), SSC ( F i , R j ), TSC ( F i , R j ),则称 RC ( F i , R j )= αFSC ( F i , R j )+ βSSC ( F i , R j ) + γTSC ( F i , R j )为 F i 对区域 R j 的区域贡献度,记为 RC ( F i , R j ),其中, α + β + γ =1,0< α , β , γ <1.
本文采用层次分析法 [26-28] (analytic hierarchy process, AHP),使用层次分析法软件yaahp(yet another AHP)得到 α =0.681 3, β =0.068 8, γ =0.249 9.
区域贡献度RC反映Ferry节点对区域贡献程度的同时,也反映了区域对Ferry节点的依赖程度,即Ferry节点对区域的RC越大,区域对Ferry节点的依赖程度越高,移除此节点后,区域从网络中分裂出去的可能性越大,则该节点为关键节点的可能性就越大.若Ferry节点 F i 对某区域 R j 的贡献值为1,则表明 R j 完全依赖于 F i ,即移除 F i 后, R j 从整网中分离.由此,可以得到推论2.
推论2. 区域贡献度为1的Ferry节点是MOSNs的割点.
由推论1、推论2得到推论3.
推论3. 区域贡献度为1的Ferry节点是MOSNs的关键节点.
MOSNs关键节点的预测步骤如下:
1) 根据推论2判定网络中是否存在割点.计算每个Ferry节点对各区域的贡献度,判断是否存在对某区域贡献度为1的Ferry节点.若存在,则该割点为网络的关键节点,预测结束,否则进入步骤2.
2) 采用MADM方法找出导致网络分裂可能性最大的节点,即为关键节点.用区域贡献度表征区域对Ferry节点的依赖程度,故Ferry节点的区域贡献度越大,其导致网络分割的可能性越大,因此本文采用改进TOPSIS方法将MOSNs中每个Ferry节点看作一个待评价方案,将Ferry节点对每个区域节点的贡献度看作方案的属性,对Ferry节点的区域贡献度进行评价.
3.1 预测算法描述
MOSNs网络结构动态变化,用一个时间长度 ΔT 时间计算的结果作为最后的预测结果是不准确的,将每一个 ΔT 预测的结果称为疑似关键节点.选取 N × ΔT 作为预测时间长度,得到 N 个疑似关键节点,统计每个Ferry节点被判定为疑似关键节点的次数.
设MOSNs中有 n 个Ferry节点(方案)和 m 个区域节点(属性),对决策矩阵 X =( x i j ) n × m 归一化,得到规范化决策矩阵 Y =( y i j ) n × m 且:
(1)
其中, x i j 为第 i 个Ferry节点对第 j 个区域节点的区域贡献度, i =1,2,…, n , j =1,2,…, m .
确定正理想方案 Y + 和负理想方案 Y - ,以及各Ferry节点方案与 Y + , Y - 的距离 D + , D - :
(2)
(3)
(4)
D - =( d - j | j =1,2,…, m ). 
(5)
其中,正理想方案为
}.
(6)
负理想方案为
}.
(7)
根据指标权重对欧氏距离计算公式进行改进:
(8)
(9)
其中, 
A j ,ω j 为第j个区域节点的指标权重,A j 表示第j个区域节点内的感知节点数.
计算各Ferry节点与正理想解和负理想解的灰色关联度:
,
s.t. 
(10)
(11)
s.t. 
,
其中, 
为由 n 个 Y + 向量构成的 n × m 矩阵中的元素； 
为由 n 个 Y - 向量构成的 n × m 矩阵中的元素； ξ 为分辨系数,取经验值0.5.则灰色关联度为
(12)
(13)
其中, 
.
对灰色关联度和距离进行无量纲转化:
(14)
(15)
(16)
(17)
其中， i =1,2,…, n .
构建相对贴近度 
如下:
(18)
(19)
其中, i =1,2,…, n ； α 为偏好系数,取经验值0.5.则各Ferry节点的相对贴近度为
).
(20)
根据计算得到 C * ,对Ferry节点进行排序, 
越大,则Ferry节点 i 是关键节点的可能性越大.
由于网络中可能存在多个割点,故预测的结果可能是多个关键节点.这就需要计算某个Ferry节点为关键节点的概率.
设MOSNs中有 d 个Ferry节点且每个Ferry节点都可能导致网络产生分割,若Ferry节点 F i 被判定为疑似关键节点 q 次,则 F i 为关键节点的概率为
P ( F i )=
(21)
计算出 P ( F i )的最大值,记为max( P ( F i )),此时对应Ferry节点记为 F k , k ∈{1,2,…, d },即为关键节点.
3.2 算法流程
算法1. 基于灰关联度的改进TOPSIS算法.
输入:多属性决策矩阵 X =( x i j ) n × m ；
输出:节点 F i 的出现概率 P ( F i ).
Step1. 基于时间长度 ΔT ,对数据进行采样分析,构建决策矩阵 X =( x i j ) n × m ,并依据式(1)进行归一化,得到规范化矩阵 Y =( y i j ) n × m ;
Step2. 根据式(2)～(5)分别计算决策的正理想方案 Y + 和负理想方案 Y - ,以及各节点方案与 Y + , Y - 的距离 D + , D - ;
Step3. 依据式(10)～(11)计算正理想方案和负理想方案的灰关联度 G + , G - ;
Step4. 基于式(14)～(17)分别对距离和灰关联度进行无量纲转化;
Step5. 根据式(20)计算每个方案到理想方案的贴近度 
最大的节点记为疑似关键节点;
Step6. 重复Step1～Step5共 N 次,统计每个Ferry节点被判定为疑似关键节点的次数;
Step7. 根据式(21)计算每个节点的出现概率 P ( F i ),并进行排序,从中选出最大概率值所对应的Ferry节点即为关键节点.
4.1 实验场景与相关参数
采用芬兰赫尔辛基科技大学开发的ONE(opportunistic networking environment)进行仿真实验,主要参数如表1所示,4种典型场景下区域节点数和各区域内感知节点数如表2所示.
Table 1 Parameters of Simulation Experiment
表1 仿真实验参数
如图5所示,场景1不存在割点.Ferry节点 fb , fc , fd 在区域节点 ra , rb , rc 间移动,不能与Sink节点直接通信,Ferry节点 fa , fe , fg 为区域节点 ra 与Sink提供通信机会. ra 与Sink间的绝大部分通信机会由 fa 提供, ra 与Sink间极少部分的通信机会由 fe , fg 提供.因此, fa 为场景1的关键节点.
Table 2 The Number of Region Nodes in Four Scenarios
表2 4种场景下区域内感知节点数
Fig. 5 Scenario 1
图5 场景1
如图6所示,场景2的关键节点为 fd .如果移动节点 fd 丢失或失效,区域节点 rc , rd , re 无法将消息传递到Sink节点,网络产生分割,故 fd 既是网络的割点,也是网络的关键节点.
Fig. 6 Scenario 2
图6 场景2
Fig. 7 Scenario 3
图7 场景3
Fig. 8 Scenario 4
图8 场景4
如图7所示,场景3不存在割点.区域节点 ra , rb 与Sink节点间绝大部分的通信机会由移动节点 fa 提供,极少的通信机会由移动节点 fe , fg 提供.可见, fa 为场景3的关键节点.
如图8所示,场景4的关键节点为 fd , fe .如果移动节点 fd 丢失或失效会导致区域节点 rd , re 从网络分裂,移动节点 fe 失效会导致区域节点 re 从网络分离.深入分析场景4,发现移动节点 fc 也是该网络的1个割点,移动节点 fa , fb , fc 使区域节点 ra , rb 与Sink节点形成两两相互连通的稳定状态,移动节点 fc 又连通着区域节点 ra , rb , rc ,若移动节点 fc 丢失或失效,则区域节点 rc , rd , re 均无法与Sink节点连通.所以,场景4的关键节点为移动节点 fc , fd , fe .
4.2 实验结果与分析
对上述4种场景进行了大量模拟实验,采用TOPSIS算法和改进TOPSIS算法对实验数据进行关键节点预测,预测结果如图9～12所示:
Fig. 9 Predicted results of scenario 1
图9 场景1的预测结果
Fig. 10 Predicted results of scenario 2
图10 场景2的预测结果
Fig. 11 Predicted results of scenario 3
图11 场景3的预测结果
Fig. 12 Predicted results of scenario 4
图12 场景4的预测结果
如图9所示,场景1中移动节点 fa 被预测为关键节点的次数最多,与前述分析结果一致,说明采用本文预测算法的合理性;如图10所示,场景2中被预测为关键节点次数最多的是移动节点 fd ;如图11所示,场景3中被预测为关键节点次数最多的是移动节点 fa ,均与前述分析一致;如图12所示的场景4中,移动节点 fc , fd , fe 多次被预测为关键节点,且三者的次数之和远远大于总实验次数200,这是因为场景4中存在3个割点,因此每次预测的关键节点可能不唯一,Ferry节点 fc , fd , fe 均为该场景下的关键节点.
由图9～12可得采用TOPSIS算法与改进TOPSIS算法预测关键节点的精度对比情况,如图13所示.场景2与场景4存在割点,2种算法的预测精度接近;场景1与场景3不存在割点,采用TOPSIS算法的预测精度在60%～70%范围内,而采用改进TOPSIS算法的预测精度达到80%～90%.可见,当MOSNs存在割点时,2种预测方法均较为准确;当MOSNs不存在割点时,采用改进TOPSIS算法的预测精度更高.
Fig. 13 The accuracy comparison chart of two measures
图13 2种方法的预测精度对比图
4.3 实验床实验
搭建实验床如图14所示,在寻迹小车上捆绑美国Crossbow公司的TelosB节点,模拟MOSNs中移动节点寻迹移动,利用黑线规划4条小车的移动轨迹.TelosB节点遵循IEEE802.15.4协议,通信范围约100 m,在实验中,将节点功率调至最低,并去掉天线,使节点的通信范围为10～20 cm,以满足图1场景.
Fig. 14 The test bed
图14 实验床
设置了3个区域节点,每个区域节点内放置若干个感知节点,区域节点 ra , rb 与Sink节点间设置了2辆小车,为了模拟小车 fa 为区域 ra , rb 提供绝大部分通信机会,小车 fb 为区域 ra , rb 提供较少的通信机会,设置轨迹半径较小的小车 fa 速度较快,轨迹半径较大的小车 fb 速度较慢,那么该场景下,小车 fa 是关键节点.
利用TOPSIS算法与改进TOPSIS算法分别对实验数据进行分析,100次实验的预测结果如图15所示.100次预测中,采用改进TOPSIS算法预测小车 fa 为关键节点的次数为73,预测精度为73%,采用 TOPSIS算法的预测精度为55%,显然改进TOPSIS算法具有更高的预测精度.
Fig. 15 The predicted results of real scenario
图15 真实场景预测结果
本文分析了OSNs消息传输的特点,针对典型OSNs——多区域机会传感器网络MOSNs模型,定义了割点和关键节点,将MOSNs关键节点预测问题转化为评估Ferry节点区域贡献度的问题,采用改进TOPSIS算法预测关键节点.仿真实验和实验床实验均说明本文的定义是合理的,通过评估Ferry节点区域贡献度预测MOSNs关键节点是可行的,采用改进TOPSIS算法具有更高的预测精度.
参考文献
[1]Xiong Yongping, Sun Limin, Niu Jianwei, et al. Opportunistic networks[J]. Journal of Software, 2009, 20(1): 124-137 (in Chinese)(熊永平, 孙利民, 牛建伟, 等. 机会网络[J]. 软件学报, 2009, 20(1): 124-137)
[2]Hull B, Bychkovsky V, Zhang Yang, et al. CarTel: A distributed mobile sensor computing system[C] 
Proc of ACM SenSys’06. New York: ACM, 2006: 125-138
[3]Wang Yu, Wu Hongyi. DFT-MSN: The delay fault-tolerant mobile sensor network for pervasive information gathering[C] Proc of INFOCOM’06. Piscataway, NJ: IEEE, 2006: 1021-1034
[4]Juang P, Oki H, Wang Yong, et al. Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with ZebraNet[J]. ACM SIGPLAN Notices, 2002, 37(10): 96-107
[5]Liu Xiaomei, Xiao Li, Kreling A, et al. Optimizing overlay topology by reducing cut vertices[C] Proc of ACM NOSSDAV’06. New York: ACM, 2006
[6]Li Jiandong, Tian Ye, Sheng Min, et al. Partition detection for large scale ad hoc networks[J]. Journal on Communications, 2008, 29(9): 54-61 (in Chinese)(李建东, 田野, 盛敏, 等. 大规模ad hoc网络拓扑分割探测研究[J]. 通信学报, 2008, 29(9): 54-61)
[7]Hu Jun, Wang Bing, Lee Deyi. Evaluating node importance with multi-criteria[C] Proc of IEEE ACM GreenCom-CPSCom. Piscataway, NJ: IEEE, 2010: 792-797
[8]Su Xiaoping, Song Yurong. Leveraging neighborhood “structural holes” to identifying key spreaders in social networks[J]. Acta Physica Sinica, 2015, 64(2): 1-11 (in Chinese)(苏晓萍, 宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点[J]. 物理学报, 2015, 64(2): 1-11)
[9]Zhou Xuan, Zhang Fengming, Li Kewu, et al. Finding vital node by node importance evaluation matrix in complex networks[J]. Acta Physica Sinica, 2012, 61(5): 1-7 (in Chinese)(周漩, 张凤鸣, 李克武, 等. 利用重要度评价矩阵确定复杂网络关键节点[J]. 物理学报, 2012, 61(5): 1-7)
[10]Xiong Shuguang, Li Jianzhong. An efficient algorithm for cut vertex detection in wireless sensor networks[C] Proc of IEEE ICDCS’10. Piscataway, NJ: IEEE, 2010: 368-377
[11]Nguyen D T, Shen Y, Thai M T. Detecting critical nodes in interdependent power networks for vulnerability assessment[J]. IEEE Trans on Smart Grid, 2013, 4(1): 151-159
[12]Shen Yilin, Nguyen N P, Xuan Ying, et al. On the discovery of critical links and nodes for assessing network vulnerability[J]. IEEE ACM Trans on Networking, 2013, 21(3): 963-973
[13]Nacher J C, Akutsu T. Analysis on critical nodes in controlling complex networks using dominating sets[C] Proc of IEEE SITIS’13. Piscataway, NJ: IEEE, 2013: 649-654
[14]Du Guiping, He Lidan, Fang Junxiang. The component importance evaluation of power converter based on complex network[C] Proc of IEEE PEAC’14. Piscataway, NJ: IEEE, 2014: 988-992
[15]Lin Jian, Dai Fei, Li Baichao, et al. Electromagnetic compatibility supernetwork modeling and node importance evaluation[C] Proc of the 5th Int Conf on Intelligent Human-Machine Systems and Cybernetics. Piscataway, NJ: IEEE, 2013: 306-310
[16]Ma Shouming, Wang Ruchuan, Ye Ning. Secure data aggregation algorithm based on reputation set pair analysis in wireless sensor networks[J]. Journal of Computer Research and Development, 2011, 48(9): 1652-1658 (in Chinese)(马守明, 王汝传, 叶宁. 基于信誉度集对分析的WSN安全数据融合[J]. 计算机研究与发展, 2011, 48(9): 1652-1658)
[17]Zeng Jia, Mu Chundi, Li Shu. Multiple attribute decision making routing in wireless sensor networks[J]. Journal of System Simulation, 2009,21(3): 878-881 (in Chinese)(曾加, 慕春棣, 李戍. 基于多属性决策的无线传感器网络路由算法[J]. 系统仿真学报, 2009, 21(3): 878-881)
[18]Corley H W, Sha D Y. Most vital links and nodes in weighted networks[J]. Operations Research Letters, 1982, 1(4): 157-160
[19]Chen Yong, Hu Aiqun, Hu Xiao. Evaluation method for node importance in communication networks[J]. Journal on Communications, 2004, 25(8): 129-134 (in Chinese)(陈勇, 胡爱群, 胡啸. 通信网中节点重要性的评价方法[J]. 通信学报, 2004, 25(8): 129-134)
[20]Zhang Xiping, Li Yongshu, Liu Gang, et al. Evaluation method of importance for nodes in complex networks based on importance contribution[J]. Complex Systems and Complexity Science, 2014, 11(3): 26-32 (in Chinese)(张喜平, 李永树, 刘刚, 等. 节点重要度贡献的复杂网络节点重要度评估方法[J]. 复杂系统与复杂性科学, 2014, 11(3): 26-32)
[21]Sabidussi G. The centrality index of a graph[J]. Psychometrika, 1966, 31(4): 581-603
[22]Freeman L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41
[23]Liu Bin, Wang Wenji, Li Yaqian, et al. Crucial node decision algorithm based on energy in WSNs[J]. Journal of Electronics and Information Technology, 2014, 36(7): 1728-1734 (in Chinese)(刘彬, 王文吉, 李雅倩, 等. 基于能量因素的无线传感器网络关键节点判定算法[J]. 电子与信息学报, 2014, 36(7): 1728-1734)
[24]Shu Jian, Geng Xiaotian, Zeng Linxin, et al. Connectivity influencing factors and modeling for opportunistic sensor networks[J]. Journal of Beijing University of Posts and Telecommunications, 2015, 38(6): 109-114 (in Chinese)(舒坚, 耿潇湉, 曾林新, 等. 机会传感网络连通度影响因素与连通度模型[J]. 北京邮电大学学报, 2015, 38(6): 109-114)
[25]Shu Jian, Guo Kai, Liu Qun, et al. Research of connectivity parameter in opportunistic sensor networks[J]. Chinese Journal of Computers, 2016, 39(5): 1067-1080 (in Chinese)(舒坚, 郭凯, 刘群, 等. 机会传感网络连通性参数研究[J]. 计算机学报, 2016, 39(5): 1067-1080)
[26]Yu Hui, Liu Zun, Li Yongjun. Key nodes in complex networks identified by multi-attribute decision-making method[J]. Acta Physica Sinica, 2013, 62(2): 46-54 (in Chinese)(于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法[J]. 物理学报, 2013, 62(2): 46-54)
[27]Sha Letian, Fu Jianming, Chen Jing, et al. A sensitivity measurement for sensitive information processing[J]. Journal of Computer Research and Development, 2014, 51(5): 1050-1060 (in Chinese)(沙乐天, 傅建明, 陈晶, 等. 一种面向敏感信息处理的敏感度度量方法[J]. 计算机研究与发展, 2014, 51(5): 1050-1060)
[28]Wang Wenbin, Sun Qibo, Yang Fangchun. Environment-aware quantitative assessment model for service availability in MANET[J]. Journal of Computer Research and Development, 2012, 49(3): 558-564 (in Chinese)(王文彬, 孙其博, 杨放春. MANET下环境感知的服务可用性量化评估模型[J]. 计算机研究与发展, 2012, 49(3): 558-564)
Zhang Jiang, born in 1992. MSc candidate in Nanchang Hangkong University. His main research interests include opportunistic sensor networks (zhangjiangky@163.com).
Shu Jian, born in 1964. Received his MSc degree in computer networks from North-western Polytechnical University. Professor in Nanchang Hangkong University. Senior member of CCF. His main research interests include wireless sensor networks, embedded system and software engineering.
Guo Kai, born in 1990. MSc candidate in Nanchang Hangkong University. Student member of CCF. His main research interests include opportunistic sensor networks (1056692868@qq.com).
Meng Lingchong, born in 1991. MSc candidate in Nanchang Hangkong University. His main research interests include opportunistic sensor networks (282733193@qq.com).
Liu Linlan 1 , Zhang Jiang 1 , Shu Jian 2 , Guo Kai 1 , and Meng Lingchong 1
1 ( School of Information Engineering , Nanchang Hangkong University , Nanchang 330063) 2 ( School of Software , Nanchang Hangkong University , Nanchang 330063)
Abstract If critical nodes have been predicted, the network can be optimized according to the information of the critical nodes. Furthermore, maintenance time and cost of network can be dramatically reduced by checking the critical nodes at the first time when the network is crashed. Unfortunately, the existing methods of predicting critical nodes in static wireless sensor networks are not suitable for opportunistic sensor networks (OSNs). According to the characteristics of dynamic changes of network topology and high latency, for multi-region OSNs (MOSNs) with hierarchical structure, this paper analyzes the message transferring process. The stage contribution is defined to reflect the contribution of Ferry nodes in the process of message transmission, and the region contribution is defined to reflect the contribution of Ferry nodes to regions. In terms of the comprehensive contribution of Ferry nodes, the prediction method of critical nodes is proposed, which is based on multiple attribute decision making—technique for order preference by similarity to ideal solution (TOPSIS). The experimental results show that the prediction method with improved TOPSIS algorithms achieves better accuracy. Furthermore, test bed is established so as to validate the proposed method. The test bed experimental results show that the prediction method with improved TOPSIS algorithms achieves better accuracy as well.
Key words opportunistic sensor networks (OSNs); critical node; region contribution; stage contribution; multiple attribute decision making
Received her BSc degree in computer application from the National University of Defence Technology. Professor in Nanchang Hangkong University. Member of CCF. Her main research interests include software engineering and distributed system.
收稿日期： 2016-08-22；
修回日期： 2017-02-06
基金项目： 国家自然科学基金项目(61363015,61262020,61501217,61501218);江西省自然科学基金重点项目(20171ACB20018,20171BAB202009,20071BBH80022);江西省教育厅科学技术重点项目(GJJ150702); 江西省研究生创新专项资金项目(YC2015-S324,YC2016-042) This work was supported by the National Natural Science Foundation of China (61363015, 61262020, 61501217, 61501218), the Natural Science Foundation of Jiangxi Province (20171ACB20018, 20171BAB202009, 20071BBH80022), the Key Research Foundation of Education Bureau of Jiangxi Province(GJJ150702), and the Innovation Foundation for Postgraduate Student of Jiangxi Province (YC2015-S324, YC2016-042).
通信作者: 舒坚(shujian@nchu.edu.cn)
中图法分类号 TP393