基于邻居表的ZigBee网络树路由改进算法

针对ZigBee网络树路由算法路由跳数多、数据传输延时长等问题,提出一种基于邻居表的ZigBee网络树路由改进算法。借助一跳邻居节点地址信息,建立邻居节点选择策略,在节点的一跳邻居节点中,选择到达目的节点树路由跳数最少的邻居节点作为下一跳转发节点。在树路由跳数相同时,选取LQI值大的节点为下一跳转发节点。理论分析结果表明,该算法路由路径优于树路由算法和ITRA算法路由路径;实验结果表明,该算法能很好地减少转发节点个数,提高了网络数据传输的可靠性,达到网络性能提高的目的。     

采用Hull树的贪婪地理位置路由算法的设计

地理位置路由算法是指借助节点获得的地理位置信息进行无线传感网络中的路由发现与数据转发工作。本文提出一种基于Hull树的贪婪地理位置路由算法——Greedy Hull Tree Geographic Routing(GHTGR)。通过图形学中凸包的概念,在网络初始阶段分布式地在各节点上建立Hull树以探查网络局部拓扑结构;同时在数据分组的路由转发阶段,通过Hull树内的搜索,寻找下一跳转发节点,完成数据分组的转发传输。通过仿真实验表明,与现有地理位置路由算法相比,该算法能够正确地寻找数据转发路径,有效地减少网络能耗,提高网络传输性能。     

一种基于能耗度量的融合树构建算法

基于传感器节点能耗情况对数据压缩以及数据融合进行了分析,针对在非完全融合情况下,贪婪增长树(GIT)算法构建融合树时并不能很好选择最优路由的问题,提出了一种基于能耗度量的融合树构建算法,通过融合节点反馈能耗以及到达Sink节点的跳数信息,对多个路由的能耗进行评估,进而选择低能耗路由.同时提出了一种由信息源节点进行路径加强的策略,减小了路径加强信息量以及多路径记录带来的负担.模拟实验数据表明,该算法在数据融合压缩比较小的情况下节能效果优于贪婪增长树GIT算法,并且随着信息源与Sink节点距离的增大,路径加强信息的数量也有很大降低.     

一种无线传感器网络的节能路由算法

提出一种基于逆向多播树的路由算法,该算法依赖局部信息建立基于逆向多播树的路由拓扑结构。利用该算法对不同类型的传感器数据建立不同的路由策略并进行传输。实验测试表明,该路由算法能有效地减少网络通信量,并具有较好的节能性能。     

一种半径自适应成簇多跳传感器网络路由算法

针对低功耗自适应聚类路由算法LEACH随机选择簇头和簇头间单跳通信的缺陷,提出一种新的成簇路由算法——半径自适应成簇多跳路由算法RACMH．它将半径自适应成簇技术与多跳通信方式相结合,节点根据本地信息独立地决定成为簇头节点或成员节点;簇类覆盖的区域限制在一定半径范围内,所有簇头节点根据权重消息组织成一棵路由树,采用多跳通信方式向基站传输数据．仿真实验表明,与LEACH相比较,该算法能更有效地延长网络生命周期,节省网络能量消耗,实现网络负载平衡．     

一种新的传感器网络能量有效路由算法

基于对LEACH、PEGASIS经典分簇算法的研究,提出一种基于分簇的传感器网络能量有效的路由算法NCEER。NCEER每隔20轮进行一次簇重构,簇内利用贪心算法形成短链,选取剩余能量最大者为簇首。然后,以基站为树根,各簇首节点根据跳数和能量级别建立层次路由树。最后,各簇首通过最优路径将采集到的数据发送到基站。该算法减少了簇重构的开销,建立了一条负载均衡的簇内路由、能量有效的簇间路由,减少了数据的传输时延。仿真结果表明,该算法的性能优于LEACH和PEGASIS。     

一种基于最小生成树的非均匀分簇路由算法

分簇式路由是无线传感器网络路由协议研究的重点,本文提出一种新的基于最小生成树的非均匀分簇路由算法,该算法利用EECS路由协议产生大小非均匀的簇,簇内结点通过单跳的方式将数据发送给簇首结点,所有簇首结点构成最小生成树路由网络,并通过树内结点的多跳通信,最终将数据发送给sink结点.实验证明,本文算法与EECS相比能够更加有效地降低整个网络的能量消耗,延长网络的生命周期.     

一种有时延约束的动态组播路由算法

贪婪算法是一种动态组播路由算法,该算法获得的通信树时延较大。文章在改进的多标号算法基础上,提出了一种有时延约束的动态组播路由算法,可以获得满足时延约束的通信树,仿真显示该算法可以获得问题的次优解。     

一种高效的多媒体无线传感器网络地理路由算法

针对多媒体无线传感器网络数据流巨大的特点,本文提出一种高效的地理路由算法AOGR。与现有的地理路由算法以路由单包时的性能最优化为目标相比,AOGR将一次会话中所有交互数据包作为整体,使得平均每包传输的路由跳数最少。它充分利用先行包在路由方面的参考作用以优化后续包的路由。随着路由数据包的增多,AOGR最终收敛于最短路径。最后,通过仿真实验验证该路由算法能够有效地减少GPSR协议在周边转发模式时产生的绕道跳数,路由平均跳数有明显减少。     

一种高效的de bruijn有向图路由算法

通过对de bruijn有向图最长路径路由算法和最短路径路由算法的分析,提出了一种新的路由算法,它有效结合了两种算法的优点,并能根据网络时延来选择最优路径,对于时延的判断是由下一跳的时延和剩余各跳的预测时延两个部分组成,从而有效避免路由信息的局部性。分析表明,新的路由算法是行之有效的。     

A fast algorithm for computing minimum routing cost spanning trees

Communication networks have been developed based on two networking approaches: bridging and routing. The convergence to an all-Ethernet paradigm in Personal and Local Area Networks and the increasing heterogeneity found in these networks emphasizes the current and future applicability of bridging. When bridging is used, a single active spanning tree needs to be defined. A Minimum Routing Cost Tree is known to be the optimal spanning tree if the probability of communication between any pair of network nodes is the same. Given that its computation is a NP-hard problem, approximation algorithms have been proposed.We propose a new approximation Minimum Routing Cost Tree algorithm. Our algorithm has time complexity lower than the fastest known approximation algorithm and provides a spanning tree with the same routing cost in practice. In addition, it represents a better solution than the current spanning tree algorithm used in bridged networks.     

关于实际构造最大带宽路径算法的研究

建立最大带宽路径一直是网络路由研究，尤其是在最近的网络QoS路由研究中的基本问题，在以往的文献中，有人提出了利用修改的Dijkstra算法或修改的Bellman-Ford算法来构建最大带宽路径。该文给出了一个简单的证明，指出了最大生成树与最大带宽路径之间的特殊关系，证明了可以使用修改的Kruskal算法来构建最大带宽路径，文中给出了修改的Kruskal算法，并且与已有的Kijkstra算法作了性能上的比较，尽管从理论上说，Dijstra算法和Kruskal算法的时间复杂度具有同样的阶，但在多种不同网络结构上的模拟测试结果表明，用Kruskal算法构建最大带宽路径的实际运行比Dijkstra算法至少要快3倍，而且在实际上比Dijkstra算法更简单，灵活。     

WSN中基于树型标号系统的分布式路由算法

针对无线传感器网络中数据中心存储的路由问题,提出一种基于树型标号系统的分布式路由算法。将网络中的节点组织成以参考节点为根的树型结构,通过比较目的节点标号与邻居节点标号,选择转发节点,实现数据路由。分析与仿真结果表明,该路由算法的空间开销较低、路由效率较高,并且生成的路径接近最短路径。     

Hierarchical spanning tree network design with Nash genetic algorithm

In this paper, we will propose a Nash genetic algorithm (Nash GA) for solving a hierarchical spanning tree network design problem, formulated as a bi-level programming problem. The proposed algorithm can be employed in designing the backbone topology in a hierarchical link-state (LS) routing domain. Because the well-designed backbone topology structure has a great impact on the overall routing performance in a hierarchical LS domain, the importance of this research is evident. The proposed algorithm is to find an optimal configuration of backbone network for backbone provider (BP) and distribution network for internet service provider (ISP), properly meeting two-aspect engineering goals: i.e., average message delay and connection costs. Also, it is assumed that there are the decision makers for BP and the decision makers for ISP join in the decision making process in order to non-cooperatively optimize the own objective function. From the experiment results, we can see clearly that our proposed algorithm can be employed in effectively designing the spanning tree network of hierarchical LS routing domain considering not only engineering aspects but also specific benefits from systematical layout of backbone network.     

无线传感器网络异构驱动路由算法

融合表驱动路由和按需驱动路由的优点提出一种异构驱动的无线传感器网络路由算法,以实现无线传感器网络监测数据的高效汇集。算法将无线传感器网络的原有单一汇聚节点(Sink节点)扩充为一组无环连通点集,称为虚拟槽节点以覆盖全网。感知节点采用按需驱动路由策略将监测数据在短距离内传递给虚拟槽节点,随后数据在虚拟槽节点内部依照表驱动路由实现高速汇集。通过理论计算确定最优虚拟槽节点选取方式,并提出两跳邻居算法实现路由。经仿真实验,算法可保证网络内任意节点两跳可达虚拟槽节点,并通过分析仿真数据论证算法的有效性。     

Convergence routing on disjoint spanning trees

This paper presents a new design and a performance study for convergence routing in a general network with multiple spanning trees. Such an arbitrary topology network is used in the design of a switch-based LAN/MAN architecture. Convergence routing can be viewed as a variant of deflection routing which combines, in a dynamic fashion, the on-line routing decision with the traffic load inside network. However, unlike other deflection techniques, convergence routing guarantees that packets will reach (or converge) to their destinations.In particular, a new algorithm for constructing two edge-disjoint spanning trees of a given network is presented, and the resulting trees are used for convergence routing. It is shown empirically that convergence routing on two edge-disjoint spanning trees yields a better bound than a single spanning tree, on the maximum route length. The construction of the two edge-disjoint spanning trees is done with specific strategies for improving the fault-tolerance and performance of the system.     

Low latency and energy efficient routing tree for wireless sensor networks with multiple mobile sinks

We propose the minimum Wiener index spanning tree (MWST) as a routing topology that is suitable for sensor networks with multiple mobile base nodes. However, it was proved that finding a spanning tree with the minimum Wiener index from a weighted graph is NP-hard. To address this problem and analyze the effectiveness of the MWST as the routing tree on sensor networks with multiple mobile base nodes, we designed two algorithms: a branch and bound algorithm for small-scale wireless sensor networks and a simulated annealing algorithm for large-scale wireless sensor networks. The simulation results show that MWST outperforms the minimum spanning tree (MST), one of the representative spanning trees used in many routing protocols for sensor networks, in terms of energy efficiency and packet delay.     

基于最小生成超树的无线传感器网络路由算法研究

设计能量有效的路由协议以延长网络生存周期,提供健壮可靠的网络服务成为资源有限无线传感器网络研究的核心问题.研究并采用超图理论,将大规模,高连通度的无线传感器网络拓扑抽象为超图模型,从而有效减少网络控制消息.并基于超图模型提出同步无线传感器网络最小生成超树路由算法,以建立数据汇聚的最小能耗树.随后理论证明MSHT-SN算法的正确性和有效性.通过仿真,基于超图模型的MSHT-SN算法较优于基于最短路树策略路由算法,其能够有效的提高数据传输成功率,并节省网络总能耗,延长网络生存周期.     

无线Mesh网络中多信道生成树路由算法

无线Mesh网络是一种特殊的AdHoc网络。它易于部署、安装,能有效地构建无线骨干网,通常被用作宽带Internet接入和扩展无线LAN的覆盖范围。针对无线Mesh网络的特点,提出了一种不同于一般MANET路由协议的路由算法。该算法基于网络拓扑生成树,使用多个无重叠信道;在解决信道分配问题的同时,兼顾信道多样性和信道重用,更好地利用无线频谱资源,支持链路并行传输。