Hyperbolic trees for efficient routing computation

Complex system theory is increasingly applied to develop control protocols for distributed computational and networking resources. The paper deals with the important subproblem of finding complex connected structures having excellent navigability properties using limited computational resources. Recently, the two-dimensional hyperbolic space turned out to be an efficient geometry for generative models of complex networks. The networks generated using the hyperbolic metric space share their basic structural properties (like small diameter or scale-free degree distribution) with several real networks. In the paper, a new model is proposed for generating navigation trees for complex networks embedded in the two-dimensional hyperbolic plane. The generative model is not based on known hyperbolic network models: the trees are not inferred from the existing links of any network; they are generated from scratch instead and based purely on the hyperbolic coordinates of nodes. We show that these hyperbolic trees have scale-free degree distributions and are present to a large extent both in synthetic hyperbolic complex networks and real ones (Internet autonomous system topology, US flight network) embedded in the hyperbolic plane. As the main result, we show that routing on the generated hyperbolic trees is optimal in terms of total memory usage of forwarding tables.

     

Energy-aware self-organisation algorithms with heterogeneous connectivity in wireless sensor networks

Heterogeneity of node energy is a common phenomenon in wireless sensor networks. In such node energy heterogeneous sensor network, how to balance the energy consumption is the key problem on extending the lifetime of the sensor network system. An energy-efficient self-organisation algorithm with heterogeneous connectivity based on energy-awareness is proposed. Each sensor node in the network adjusts its own transmission radius based on the local energy information during the constructing and operating phase. Thus heterogeneous network topology, in which the nodes can choose different transmission radius, is formed. In contrast to the homogeneous network model, in which the node carries the same radius, simulation and analysis are conducted to explore the topology characteristics and robustness with different node energy distribution. The degree distribution shows the scale-free property in the heterogeneous model. The proposed network model enjoys higher efficiency of transmitting data, less clustering, higher robustness under node random failures and longer network lifetime than those in the homogeneous ones.     

考虑节点亲密度的社交网络谣言传播研究

考虑到真实社交网络中节点间亲密程度对谣言传播的影响,提出一种新的SI2R传播模型,建立谣言传播动力学方程组,研究谣言在无标度网络上的传播特性。该模型中不同节点间谣言传播率的非一致性同时取决于节点度与节点间亲密度,理论分析得到了无标度网络上谣言传播阈值表达式。随后,在BA（Barabási-Albert）无标度网络中就节点亲密度对谣言传播过程的影响进行了仿真实验,并利用Twitter和Live Journal两种真实网络数据集对仿真结果进行验证。研究表明,无标度网络中节点间平均亲密度随网络聚类系数的增大而减小,随着网络中节点间平均亲密度增大,谣言传播最终范围变大。研究还发现,节点间亲密度的存在使无标度网络中存在传播阈值,传播阈值随着节点间平均亲密度增大而减小。     

基于共同邻居邻域拓扑稠密性加权的链路预测方法

链路预测旨在利用已知的网络节点和拓扑结构信息,预测网络中未连接的两个节点之间存在连边的可能性。基于网络拓扑相似性的链路预测方法计算复杂度低且预测效果好,但现有的相似性指标对共同邻居的邻域拓扑信息考虑较少。针对此问题,提出一种基于共同邻居邻域拓扑稠密性加权的链路预测方法。首先,基于邻域拓扑相对稠密指数量化节点的邻域拓扑结构;然后,利用共同邻居的节点度和邻域拓扑相对稠密指数刻画共同邻居及其邻域拓扑的相似性贡献;最后,提出基于共同邻居邻域拓扑稠密性加权的节点相似性指标。在多个实际网络数据上的实验结果表明,与现有相似性指标相比,该方法能够取得更高的预测精度。     

无线传感器网络簇级拓扑演化模型研究

复杂网络理论研究表明,复杂系统的容错能力不仅仅存在于具有冗余组件的系统之中;而且也同样存在于具有无标度(scale-free)特征的网络之中;文章借助于复杂网络理论和偏好依附机制提出一种无线传感器网络簇级拓扑演化模型;拓扑动态分析表明,该模型能够很好地体现无线传感器簇间的拓扑生长过程,由该模型演化成的无线网络拓扑具有无标度网络的性质,所以该拓扑模型具有很强的容错性。     

多网关无线Mesh网络干扰与负载感知路由度量

提出一种应用于多网关无线Mesh网络中的路由度量。首先建立多网关网络模型,获取网络拓扑信息并依此为网络节点分配不同的权值;然后通过网络拓扑信息及无线链路的衰落特性,推导网络中链路信号与干扰噪声比SINR的分布特性,进而计算链路的中断概率和中断速率;最后获取Mesh路由器节点缓存包数量,并计算网关节点容量占比,针对客户端业务和Internet业务设计具有保序性的ILR(Interfere and Load aware Routing)路由度量,网络依据路由度量为客户端业务和Internet业务选路。ILR路由度量考虑了网络干扰因素和负载分布信息,能够有效降低网络干扰,达到网络负载均衡、提高网络吞吐量的目的。     

基于H运算的动态网络重要节点识别方法

传统K-shell网络重要节点识别方法迭代时需网络全局拓扑信息,而且难以应用于动态网络。为解决该问题,提出基于邻域优先异步H运算的动态网络重要节点识别方法。首先,证明该算法收敛于Ks值,其次以各节点的度作为h指数初始值;然后,通过节点h指数排序和邻居节点h指数变化选择更新节点,同时针对动态网络节点的增减数目和最大度,修改h指数适应拓扑变化,直至算法收敛并找到重要节点。仿真实验结果表明,该方法通过邻居节点局部信息且以更高效率找到动态网络的重要节点,收敛时间在静态网络中较随机选择更新节点法与变化邻居选点法分别下降77.4%和28.3%,在网络拓扑变化后分别下降84.3%和38.8%。     

无线传感器网络能量均衡拓扑模型研究

针对BA模型仅考虑节点寿命对网络拓扑结构影响的现状,考虑到拓扑能量利用率不高会缩短网络生命周期,在分析网络平均剩余能量和通信半径对网络生命周期影响的基础上,提出一种无线传感器网络能量均衡拓扑模型.该模型在拓扑演化过程中,综合考虑节点剩余能量、通信半径和节点度,并引入剩余能量调节参数、通信半径调节参数和节点度调节参数,最终使剩余能量大的节点连接概率更高.理论分析和仿真实验结果表明,该模型不仅具有无标度网络的幂律特性,具有较好的稳定性,且能够均衡节点和网络能耗,延长网络的生命周期.     

自组网中基于自适应波束天线的拓扑控制算法

定向天线自组网拓扑的构建问题比全向天线网络复杂.基于自适应波束定向天线模型提出一种分布式拓扑控制算法,通过调整节点发射功率,改变天线波束的朝向、宽度和增益来构建拓扑.网络中每个节点收集其邻居节点信息,采用功率控制调度策略选择最优相邻节点,并选取覆盖所有最优相邻节点的最小发射功率为此节点的发射功率.算法在保证网络连通性与无向性的同时,降低了节点的发射功率,减小了节点的平均度数,从而降低节点能耗,减少了节点间干扰,提高了网络吞吐量.仿真结果表明,算法显著提高了网络性能.     

区域物流网络表述模型与结构分析*

为了定量化表述区域物流网络以及分析其结构特征,提出了区域物流网络表述模型。以湖南省为例,从节点度和强度分布、边的权重差异度、集聚性、节点度相关性等对区域物流网络结构进行定量分析。发现其网络为无标度网络,具有双幂律特征,边权差异度大、大节点联系紧密,拓扑结构为非同类网络等结构特征。     

基于有限节点集的网络毁伤最大化问题研究

对网络实施攻击时,人们希望在有限的资源下获得最大的毁伤效果,而节点排序策略并不能实现毁伤最大.针对这种情况,定义攻击有限节点集的网络毁伤最大化问题,并给出问题的近似求解算法.由于近似求解算法计算复杂度较高,进一步提出基于重要节点的贪婪算法(greedy algorithm based on important nodes,GABIN).对无标度网络的实验表明:GABIN算法能够有效地减少计算时间,且效果接近于近似求解算法;当无标度网络的度指数$\gamma\geqslant2.5$时,GABIN算法的效果明显优于排序算法,所得节点集中超过30%的节点不同于排序算法.对Power网络的毁伤实验表明,GABIN算法适用于较大规模的实际网络,且效果显著优于度、介数、接近度、删除节点等排序算法.实验发现,利用GABIN算法获得的关键节点集包含大量的非中心性节点,这为网络攻击或网络防护提供了一个新的思路.     

无线传感器网络中保证交付的贪心路由算法

针对传感器网络提出了一种高效的点对点的路由方法.通过对每个节点分配坐标,将网络映射到由它的若干生成树构成的度量空间,根据节点坐标使用贪婪算法路由,即总是选择离目的节点最近的邻居转发包.该方法在每个节点的路由表中只需要维护邻居的坐标,包首部开销最多为O(log2n)2比特.与很多基于位置的贪婪路由算法相比较,该方法的特点是贪婪路由算法能够保证网络中任意一对节点之间都是可达的,并且路径长度不超过这对节点在生成树上的距离.仿真表明该方法同时能够在路径拉伸度和负载平衡上取得较好的性能.     

基于压缩感知的异构网络数据动态重构算法

针对异构网络数据资源存在节点及链路均衡度过低且数据重构资源分配路径误差较大的问题,设计一种基于节点拓扑感知的异构网络数据动态重构算法。利用模糊核聚类算法将数据样本集映射至高维空间内,聚类目标数据,根据节点在网络中对应的坐标构建异构网络拓扑模型及数据权矩阵模型;设置路由器物理链路通信图,根据链路带宽约束优化数据重构资源的分配路径,将节点核心区数据重构,并分配至聚类节点来感知数据的动态变化,为每一个核心聚类节点拓扑感知一个路由器数据的动态变化,来实现全局的数据动态重构,至此完成基于节点拓扑感知的异构网络数据动态重构算法的设计。设计仿真实验,测试算法的节点均衡度与链路均衡度。实验结果表明,设计的算法的节点均衡度为0.93,链路均衡度为0.90,均高于对比方法,因此可以得出,该算法的资源均衡度更好。     

具有动态拓扑感知的无线自组对等网

针对无线自组对等网中逻辑拓扑与物理拓扑之间的失配问题,综合节点位置信息和分布状况,构造出具有静态拓扑相关的无线自组对等网.通过中心节点获取网络拓扑的变化信息,将节点标号的最佳分配转化为最大旅行商问题.同时,采用模拟退火算法进行优化求解,实现了网络的动态拓扑感知性.仿真结果表明,该对等网在资源定位过程中,访问路径明显缩短,时延和数据丢包率明显减小.     

基于引力模型及相对路径数的节点重要度评估算法

准确度量复杂网络中节点的重要度对于研究网络结构和功能等方面具有重要的指导意义。现有多数节点重要度评估算法考虑了节点及其邻居节点的相关信息,却忽略了节点间的拓扑结构对节点重要度的影响。针对此问题,提出了基于引力模型及相对路径数的节点重要度评估算法。该算法首先分析了相对最短路径数对节点间信息传播的影响效果,同时考虑到非最短路径及路径距离等因素的影响,然后以三阶范围内邻居节点与中心节点的相互作用力之和定义节点重要度值,最后在六个真实网络中进行仿真实验。实验结果表明,所提算法不仅能有效区分网络中不同节点之间的重要度差异,还能准确度量网络节点的重要度大小。     

基于节点亲密度的重要性评估算法

识别复杂网络中的重要节点一直是社会网络分析和挖掘领域的热点问题,有助于理解有影响力的传播者在信息扩散和传染病传播中的作用。现有的节点重要性算法充分考虑了邻居信息,但忽略了邻居节点与节点之间的结构信息。针对此问题,考虑到不同结构下邻居节点对节点的影响力不同,提出了一种综合考虑节点的邻居数量和节点与邻居间亲密程度的节点重要性评估算法,其同时体现了节点的度属性和“亲密”属性。该算法利用相似性指标来测量节点间的亲密程度,以肯德尔相关系数为节点排序的准确度评价指标。在多个经典的实际网络上利用SIR(易感-感染-免疫)模型对传播过程进行仿真,结果表明,与度指标、接近中心性指标、介数中心性指标与K-shell指标相比,KI指标可以更精确地对节点传播影响力进行排序。     

基于能量感知的无线传感器网络拓扑演化

针对无线传感器网络中能源效率的问题,引入复杂网络理论的研究方法,提出基于能量感知无线传感器网络拓扑动态演化模型。在建模过程中考虑到无线传感器网络拓扑变化与节点的度数和剩余能量密切相关,而且网络中节点和链路是有增有减的动态行为,利用连续场理论推导出此模型具有无标度的特征,无标度网络对于节点的随机故障具有较高的鲁棒性。数值计算与实验仿真结果显示,算法可以有效地改善整个网络的结点均衡能耗。     

面向大规模学术社交网络的社区发现模型

针对基于标签传播的复杂网络重叠社区发现算法中预先输入参数在真实网络中的局限性以及标签冗余等问题,提出一种基于标签传播的面向大规模学术社交网络的社区发现模型。该模型通过寻找网络中互不相交的最大极大团(UMC)并对每个UMC中的节点赋予唯一标签来减少冗余标签,提高社区发现的效率以及稳定性。标签更新时以UMC作为核心单位采用亲密度的方式由中心向四周更新UMC邻接节点的标签及权重,以权重最大值的方式更新网络中非UMC邻接节点的权重。后期处理阶段采用自适应阈值方式去除节点标签中的噪声,有效克服了预先输入重叠社区个数在真实网络中的局限性。通过在学术社交网络平台——学者网数据集上的实验表明,该模型能够将具有一定共性的节点划分到同一个社区中,并为学术社交网络平台进一步的好友推荐、论文分享等精确的个性化服务提供了支持。     

基于藕合系数的无标度网络建模

经典的无标度网络模型在全局范围内按照一定的概率选取节点进行优先连接,而现实网络很难做到这一点。为了解决这一问题,在BA无标度网络模型的基础上,通过新增两个参数耦合系数和吸引因子来构建基于耦合系数的无标度网络模型,并通过理论计算得出该演化模型的度分布。分析发现,它具有更明显的无标度网络特性。实验仿真结果也表明,其度分布在服从幂律分布的基础上更具有平稳性和广泛的适用性。     

基于多生成树和子网-节点度联合权重的MCDS构造算法

提出了一种基于多生成树和子网-节点度联合权重的静态无线网络极小连通支配集MCDS构造算法SWNMCDS。算法首先设定一个概率p,每个节点随机生成一个概率并与p对比后决定是否成为候选根节点。两跳范围内的候选根节点相互交换信息,确定最终的根节点。每个根节点基于节点权重的连通树生成算法生成多棵连通树。最后基于子网-节点度联合权重选择连通节点,将多棵连通树连成极小连通支配集。经分析,SWNMCDS算法近似比上限为2β(2+H(Δ)),时间复杂度为O(Δ2),消息复杂度为O(Δ2)(Δ为最大一跳邻居节点集合的大小,β为生成树数目)。仿真实验表明,与经典MCDS算法比较,SWNMCDS所构造的连通支配集具有较小的规模。