Topology Control Algorithm Using Fault-Tolerant 1-Spanner for Wireless Ad Hoc Networks

A fault-tolerant 1-spanner is used to preserve all the minimum energy paths after node failures to cope with fault-tolerant topology control problems in wireless ad hoc networks.A fault-tolerant 1-spanner is a graph such that the remaining graph after node failures will not only remain connected,but also have a stretch factor of one.The fault-tolerant 1-spanner is used in a localized and distributed topology control algorithm,named the k-Fault-Tolerant 1-Spanner (k-FT1S),where each node constructs a minimum energy path tree for every local failed node set.This paper proves that the topology constructed by k-FT1S is a k-fault-tolerant 1-spanner that can tolerate up to k node failures,such that the remaining network after node failures preserves all the minimum energy paths of the remaining network gained from the initial network by removing the same failed nodes.Simulations show that the remaining network after removal of any k nodes still has the optimal energy efficiency and is competitive in terms of average logical degree,average physical degree,and average transmission radius.     

基于最小生成树的R~*-树结点分裂算法

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出了一种新的R*-树结点分裂算法.该算法将R*-树索引结点表示为轴向包围盒,依据轴向包围盒外接球间的重叠度计算结点相似度,并将其作为权值构建结点无向连通图,用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树,并基于结点外接球体积对R*-树结构进行优化,从而实现了R*-树结点分裂.实例表明,R*-树结点分裂算法可处理各种复杂数据的结点分裂问题,能够有效地提高R*-树的构建效率及空间数据的查询效率.     

用遗传算法模拟复杂最优网络的自然涌现过程

为了模拟复杂最优网络从树演化到完备图的整个过程，解决现有邻接节点编码方法只适用于低密度网络，而传统的交叉变异方法又有大量不可行解的问题，提出了基于三角阵的变长基因编码方法和段间交叉、段内变异平衡的交叉变异方法．该编码方法只记录对称邻接矩阵中三角阵的信息，反映了无向网络的所有可能变化，因而编码串长度适中，网络边数不需限制，可以模拟网络从树到完备图的整个演化过程．段间交叉只交换节点一级近邻的连接方式，段内变异平衡对边进行重绕，这既符合遗传算法的要求，又保证了网络的连通性．模拟结果表明，与邻接节点编码和传统交叉变异方法相比，所提方法适用范围更广，收敛速度较快．     

物联网专用频点自组网驱动路由协议算法分析

为了解决物联网专用频点自组网网络节点能量消耗容易失衡,当节点数增加时易产生链路故障的问题,设计一种改进物联网专用频点自组网驱动路由协议算法.以感知现场、汇聚节点和Internet为主要结构,构建物联网专用频点自组网网络模型.模型采用多媒体印刷读物(multimedia print reader,MPR)集合综合选取节点机制,以网络节点总能量消耗以及能量代价为基础,通过节点优化目标函数,确保自组网能量消耗处于均衡状态.通过网络路由协议改进算法,采用最小覆盖集实现物联网专用频点自组网链路故障的修复.结果表明,改进后的算法对路由链路信息转发具有良好的吞吐性能,可以提高网络数据传输性和连通性,并可增加节点生存时间,最终提升数据包到达率和数据控制量.     

基于最大完全子图与最小树形图的无线定向网络广播算法

现有关于无线定向网络广播的研究主要集中于如何选择中继节点或计算转发概率以提升分组递交率,减少广播冗余,但未对中继节点选择及波束指向计算开展联合设计,导致源节点及中继节点在广播过程中存在冗余指向,增加了消息转发次数。为提升无线定向网络广播效率,提出一种基于最大完全子图与最小树形图的无线定向网络广播算法(maximum complete subgraph and minimum arborescence based directional broadcasting algorithm, MCSMA)。算法首先利用最大完全子图理论计算源节点或中继节点波束指向,使单个波束指向覆盖的邻居节点数量最多,然后利用最小树形图理论选择中继节点,使中继节点使用少量波束覆盖全网所有节点,降低广播过程中的消息转发次数。仿真表明,所提算法可有效减少广播过程中源节点和中继节点的波束指向次数,提升定向广播效率。     

基于可调发射功率的无线传感器能量空洞避免算法

基于无线传感器数据收集网络的多对一收集特征,部分节点因为过早耗尽自身能量而导致网络原有覆盖区域缺失或者数据无法送达Sink节点,从而形成能量空洞现象.针对这一问题,提出一种避免能量空洞的算法ATPAEH(adjusting transmission power to avoid energy-hole).首先,根据网络中所有节点的剩余能量信息将节点分为门限节点和充裕节点两个集合.然后,对于门限节点集合中的节点形成最短路径树以多跳的方式将数据传送到Sink节点.而充裕节点集合中的节点根据该节点与Sink的距离调节其自身的发射功率,直接将数据传送到Sink节点.最后,通过与MILD算法的对比实验表...     

基于邻介熵和邻度熵的复杂网络中心性算法

识别复杂网络的重要节点是复杂网络研究的关键点,也是网络稳定性判定的重要理论基础.常用的识别节点影响力的中心性指标有介数中心性、度中心性、特征向量中心性和K-core 中心性等,这些指标在识别重要节点时存在一定的局限性.为了解决以上问题,将节点v_i的邻居节点集划分成关联邻居节点集(MR)和非关联邻居节点集(M_UR),结合图的信息熵以及节点的介数中心性和度中心性,提出新的中心性指标,即基于邻介熵(NBE)和邻度熵(NDE)的关联邻居中心性RNC 和非关联邻居中心性URNC.实验通过动态攻击来评估新的中心性指标在一个实验网络模型和五个真实网络上的效率,结果表明,新的中心性比传统的中心性具有更高的识别重要节点的效率.     

无线传感器网络能效时延平衡数据收集机制

在追求无线传感器网络高能量效率的同时,考虑数据汇聚时延,提出了一种能效与时延平衡的数据收集机制(energy efficiency and delay balancing data gathering,EEDBDG).该机制采用一种新型动态树来组织网络拓扑,消除了"热区"问题,节点动态选择路由并轮换充当树根,根节点收集数据并与基站直接通信.同时,针对不同的时延和能效要求,提出了3种数据收集策略:时延最优算法(EEDBDG-D),能效最优算法(EEDBDG-E)和能效时延平衡算法(EEDBDG-M).仿真结果表明,在节点通信半径受限的情况下,EEDBDG平衡了节点能量消耗,延长了网络生命时间,在节能与省时上均表现出了突出的性能.与GSEN相比,在最好情况下,EEDBDG-E网络生命期提高了72%,EEDBDG-D汇聚时延降低了74%.     

基于图注意力和特征融合的链路预测方法

链路预测是一种还原网络缺失信息的方法，通过当前已观察到的链路，预测实际存在但未被观察到的链路或可能出现的新链路.当前链路预测主要是基于图神经网络的深度学习方法，相比基于规则的启发式方法，前者可有效利用网络拓扑结构信息，较大地提升了网络链路预测性能，并可应用到类型更广泛的网络中.但是现有基于图神经网络的方法，仅利用网络中节点相对位置信息，忽视了节点基本属性和链路的邻居信息，且无法区分不同节点对链路形成的重要程度.为此，本文提出一种基于图注意力网络和特征融合的链路预测方法.通过增加节点的度、链路的共同邻居数量和共同邻居最大度等特征，丰富了网络的输入特征信息.本文首先提取以目标节点对为中心的子图，然后将其转化为对应的线图，线图中的节点和原图中的链路一一对应，从而将原图节点和链路信息融合到线图的节点中，提升了特征融合的有效性和可解释性.同时本文使用图注意力机制学习节点的权重，增强了特征融合的灵活性.实验表明，本文所提出的方法，在多个不同领域数据集上的AUC和AP均超过90%,在已观测链路缺失较多时，预测性能保持80%以上，且均优于现有最新方法.     

A hybrid cache placement scheme for multi-hop wireless service network

In this paper,a hybrid cache placement scheme for multihop wireless service networks is proposed. In this scheme,hot nodes in data transferring path are mined up by means of rout-ing navigation graph,and whole network is covered with network clustering scheme. A hot node has been chosen for cache place-ment in each cluster,and the nodes within a cluster access cache data with no more than two hops. The cache placement scheme reduces data access latency and workload of the server node. It also reduces the average length of data transferring,which means that fewer nodes are involved. The network system energy con-sumption decreased as involved relay nodes reduced. The per-formance analysis shows that the scheme achieves significant system performance improvement in network environment,with a large number of nodes.     

基于筛选机制的L1核学习机分布式训练方法

为降低无线传感器网络中核学习机训练时的数据通信代价和节点计算代价,研究了基于筛选机制的L1正则化核学习机分布式训练方法。提出了一种节点局部训练样本筛选机制,各节点利用筛选出的训练样本,在节点模型对本地训练样本的预测值与邻居节点间局部最优模型对本地训练样本预测值相一致的约束下,利用增广拉格朗日乘子法求解L1正则化核学习机分布式优化问题,利用交替方向乘子法求解节点本地的L1正则化核学习机的稀疏模型;仅依靠相邻节点间传输稀疏模型的协作方式,进一步优化节点局部模型,直至各节点模型收敛。基于此方法,提出了基于筛选机制的L1正则化核最小平方误差学习机的分布式训练算法。仿真实验验证了该算法在模型预测正确率、模型稀疏率、数据传输量和参与模型训练样本量上的有效性和优势。     

基于细化和最小生成树的多边形主骨架线提取

现有的不规则多边形主骨架线提取方法存在设计复杂、执行效率低等缺点,对此提出一种基于细化和最小生成树的多边形主骨架线提取方法 .首先,确定多边形的最小包围盒,并在其中生成均匀分布、数值分别为0或1的点,运用细化算法提取多边形骨架;再利用Prim算法生成最小生成树;最后,计算最小生成树上的两个叶子节点间的路径长度,将长度最长的路径定义为主骨架线.实验结果表明：本方法提取出的主骨架线效果较好,具有一定的实用性.     

考虑节点异质性和故障函数的电力信息物理系统风险传播模型

由于电力信息物理系统的耦合建模方法大多数依赖网络拓扑结构划分节点类型,未考虑节点信息的属性,同时也忽略了不同节点类型对风险传播的影响,削弱了对风险预测的能力。因此,提出了一种考虑节点异质性和故障函数的电力信息系统风险传播模型。首先对实际电力网络节点特性以及耦合性特点进行分析,结合节点异质性提出双网节点的表征方法,基于双网物理和逻辑依赖关系,设计了电力信息物理融合系统(cyber physical systems, CPS)表征模型。在此基础上,考虑双网状态交互影响的方向性及节点的依赖性,分析影响风险传播的因素,通过定义基于节点度的故障概率函数,构建了电力CPS风险传播模型。以合成网络和意大利真实数据所建立的耦合网络进行实验分析,证明模型的有效性。     

上海股票市场网络拓扑指标与波动率的相关性

以股票作为网络的节点,股票间关联性作为边,使用最小生成树方法构建上海证券市场股票网络,计算网络的基本拓扑指标,分析这些指标与股票市场波动率的相关性.结果表明:网络的平均路径长度和市场波动率成负相关,当市场波动率越高,节点之间的距离越短,网络收缩越紧密;平均占有层和市场波动率成负相关,当市场波动率增加,网络中的点更趋近于中心节点;节点的最大度和市场波动率成正相关,随着市场波动率增加,网络节点之间的关联性增强,协同运动趋势增强.通过分析股票网络拓扑指标的变化规律从而对股票市场波动的变化进行预测.     

基于二叉推荐树的可信评估模型

在网络安全领域,可信被定义为一个实体期望另外一个实体执行某个特定动作的可能性大小。为了加强网络的安全性,允许某个结点去评估其他结点的可信性是非常重要的。本文主要讨论的是对可信事件的推荐评估。首先介绍了可信的相关概念和特性;接着,网络被抽象成一个有向图,在该图中,顶点代表实体或用户,边被看成可信关系,这样,评估过程可以看成是在有向图当中寻找最短路径问题,通过对影响推荐信任的因素分析,得到间接信任计算公式,为每个结点建立一个二叉推荐树,用来存储该结点能够推荐的结点以及这些结点推荐信任值,并在每个周期后动态地调整和整理该二叉推荐树;最后,对该模型的有效性进行了分析。     

几类具有可分解结构图的最小填充数

在计算数学领域,稀疏矩阵的最小填充问题由于其重要的实际意义而受重视.本文从图论的观点提出一种方法,即利用图的分解约化定理给出了麻花图,火箭图,网图等的填充数表达式,从而为确定这些图类的填充奠定了基础,并提出进一步的建议.     

基于CDMA技术的Ad Hoc网络联合功率控制算法

提出了一种用于Ad Hoc CDMA网络的联合功率控制算法．对于一个接收终端,分配在同一时隙的各个发射终端的功率调整是基于通信链路的当前状态信息,其中包括各发射终端下一步使用的调整后的新发射功率值．即发射终端调整后的新发射功率值是基于共同的通信资源计算得出的．使得各移动终端能够共享通信网络链路资源．仿真结果表明,这一新的功率控制算法能有效地减小接收端信噪比动态范围,降低干扰信号强度,提高能量效率和系统性能．     

厂网分开条件下购电配电计划的优化方法

将电力系统描述为一个由发电节点和用电节点两类构成的二分图·在电力系统的经济决策和系统运行技术分析可以分别进行的前提下,提出一种电力市场下电力购买与配送计划优化的模型,基于图论理论给出模型解存在的必要条件·并提出基于线性规划的模型求解算法·根据各类节点的电量和资金平衡条件,构造包含节点电价的线性方程组,从而构成确定各节点成本电价的方法·上述方法对大量来源于实际电力系统购配电计划模拟问题进行了计算,取得了满意的结果·     

MPLPK: A mobile path localization protocol based on key nodes

To alleviate the localization error introduced by irregular sensor network deployment,a new mobile path localization based on key nodes(MPLPK) protocol is proposed.It can recognize all concave/convex nodes in the network as fixed anchor nodes,and simplify the following localization process based on these key nodes.The MPLPK protocol is composed of three steps.After all key nodes are found in the network,a mobile node applying improved minimum spanning tree(MST)algorithm is introduced to traverse and locate them.By taking the concave/convex nodes as anchors,the complexity of the irregular network can be degraded.And the simulation results demonstrate that MPLPK has 20%to 40%accuracy improvements than connectivity-based and anchor-free three-dimensional localization(CATL) and approximate convex decomposition based localization(ACDL).     

基于攻击图的APT脆弱节点评估方法

高级可持续性威胁(advanced persistent threat,APT)具有行为隐蔽性强、攻击周期持久的特点,增加了攻击检测的难度.据此,引入攻击图理论评估网络系统在APT攻击下的脆弱节点,提出了一种基于攻击图的APT脆弱节点评估方法,有效地提高了发现攻击的概率.对APT攻击行为的异常特征进行提取和定义,对目标网络系统建立风险属性攻击图(risk attribute attack graph,RAAG)模型;基于APT攻击行为特征的脆弱性对系统节点的行为脆弱性进行评估,并以通用漏洞评分系统(common vulnerability scoring system,CVSS)标准做为参照评估系统节点的通联脆弱性;基于上述2个方面的评估,计算系统中各节点的整体脆弱性,并发现目标网络系统在面向APT攻击时的脆弱节点.实验结果表明,所提方法能够对APT攻击行为特征进行合理量化,对系统节点的脆弱性进行有效评估,在APT攻击检测率上有较好表现.