路标迭代提取和剔除的自适应空洞处理算法

针对无线传感器网络贪婪地理路由协议中的路由空洞问题,提出一种高效的基于路标迭代提取和剔除的自适应空洞处理算法.该算法中,当探测包贪婪转发遇到空洞时,在网络拓扑局部平面化的基础上,以左(右)手法则提取空洞边界并沿其逆(顺)时针周边模式双向转发,同时,分布式地进行路标的迭代提取和剔除,直到获取的路标使得后续的数据包依次以它们为中间目标节点进行传输而不再遇到空洞为止.仿真结果表明,该协议能够以较小的控制开销代价获得次最优的传输路径,极大地提高了路由协议的性能,可以应用于无法消除路由空洞的大规模无线传感器网络贪婪地理路由协议.     

基于空洞模型的地理位置路由改进算法研究

针对现有WSN中地理位置路由遇路由空洞后会产生冗余路由的问题,提出一种基于感知空洞形状的分段贪婪路由(Easy Modeling Greedy Routing,EMGR)算法。EMGR引入虚拟坐标概念,利用空洞边界探测包收集空洞边界节点信息,将其映射到虚拟坐标系中;根据空洞边界节点在虚拟坐标系的不同分布,定义凹、凸域来概括路由空洞形状;根据不同的空洞形状找到合适的中转节点,采用分段贪婪路由方式传输数据。仿真实验结果表明,相较于GPSR算法,EMGR算法产生的路由跳数减少了35%,网络能耗低,路径扩张率和网络时延小。     

地理路由算法在三维传感器网络中应用

为解决三维传感器网络中应用地理路由算法引起的路由空洞问题,引入树型网络路由算法,提出一种新的地理路由算法———基于树型网络的贪婪算法（ GAT）。根据三维传感器网络拓扑结构信息,GAT生成一个树型网络拓扑,并为每个节点分配ID信息,当基于真实地理位置的贪婪算法遇到路由空洞时,采用树型网络路由算法作为恢复机制,保证了数据分组的可达性。GAT克服了三维空间中贪婪算法的路由空洞问题,可以保证三维传感器网络中任意节点之间数据分组的可达性。仿真实验验证了GAT在三维空间的可行性以及高效的路由性能。     

无线传感器网络中一种基于标号的贪婪转发算法

针对传统地理路由存在的路由空洞问题,提出一种新的路由算法:基于标号的贪婪转发LBGF算法。算法将网络中的节点组织为一个带环树,在构建树的同时,父节点依据子节点的位置信息为其分配隐含节点间亲缘关系的标号,从而形成一个树型标号系统,并设计相应的贪婪转发算法。分析与仿真结果表明:相对于GPSR,LBGF算法具有空洞避免、容错性强、通信与存储开销低、计算简便等优点,适于节点稀疏或障碍物较多的无线传感器网络。     

基于虚拟坐标系统的无线网络地理路由算法

针对地理路由算法中的路由空洞问题,通过引入虚拟坐标的方式,提出了一种新颖的无线网络地理路由算法——双重贪婪算法(DGA)。根据网络的拓扑结构信息,DGA为每个节点分配虚拟坐标,在基于真实地理位置的贪婪算法遇到路由空洞时,以基于虚拟坐标系统的贪婪算法作为恢复机制,从而保证路由算法的收敛性。DGA克服了GPSR等传统地理路由算法只能适用于理想的单位圆图(UDG)的缺点,能够适用于更加真实的无线网络模型。仿真实验验证了DGA高效的路由性能及良好的扩展性。     

三维AD-HOC 网络地理信息路由算法

在二维AD-HOC 网络中,可以充分利用节点的地理信息进行路由,即AD-HOC 中节点根据邻居节点的距离目标节点的距离,选择下一跳节点进行路由转发.由于AD-HOC 中节点部署通常不满足均匀分布,造成网络中出现路由空洞,贪婪转发算法在遭遇空洞的情况下将无法正确执行.在二维AD-HOC 网络环境中,往往采用贪婪(Greedy)算法结合表面路由(Face Routing)的方法跳出路由空洞.但是在三维条件下,目前没有很好跳出路由空洞的算法能够实现有效的路由.提出了一种在三维AD-HOC 网络中的地理信息路由算法GSG,该算法使用3D RDT 图和3D RRNG 图的方法实现三维网络空间的划分.采用3D 表面路由的方法进行信息传递,在遭遇局部最小点时,可有效跳出路由空洞.仿真实验结果表明,GSG 算法可提升三维AD-HOC 网络条件下地理信息路由的效率,具有良好的可扩展性.     

矿井无线传感器监测网络路由改进算法的研究

分析了煤矿监测无线传感器网络的网络特点及其对应的路由协议的基本要求,针对井下网络拓扑变化频繁的特点,提出一种基于位置信息和网络梯度的贪婪型路由算法。该路由算法很好地解决了节点如何走出空洞现象和如何选择最优下一跳路由节点两个关键问题,路由信息简单可维护性强,研究结果表明该算法下的网络具备很好鲁棒性和可扩展性,满足井下实时监测网络的应用需求。     

无线传感器网络通信空洞分析

本文简述无线传感器网络近代发展的情况。详细介绍了以地理位置信息为基础的贪婪路由算法。分析了现有的贪婪算法存在的不足,着重讨论了贪婪路由算法中通信空洞现象各种不同的解决方法。基于以上分析对地理位置信息在无线传感器网络路由协议的发展提出看法。     

WMSN中的一种实时地理路由算法

针对基于地理位置的路由协议在无线多媒体传感器网络中存在的路由空洞问题,提出了一种新的地理路由算法RTGR.该算法通过周期性的空洞检测收集所有空洞边界节点的位置信息,并利用距离形成一个覆盖空洞的感知域.数据包到达感知域后,动态选择空洞边界上的凸包节点作为中间节点进行转发,形成有效的空洞迂回路径,避免陷入路由空洞.仿真结果表明,该算法的路由平均跳数明显减少,能够保证多媒体数据在多路由空洞环境下的实时传输.     

三维无线传感器网络贪婪地理路由协议

针对已有的三维无线传感器网络路由协议均将三维问题转换到二维平面上解决,没有充分利用三维空间的特点,提出了一种基于地理信息的三维无线传感器网络贪婪地理路由(GGR)协议。该协议在通常状况下采用贪婪转发算法,针对基于地理信息的贪婪算法中易出现的路由空洞问题,给出一种三维滚动球边界遍历算法。实验结果表明:该协议具有较高的路由成功率,路由跳数也得到优化,尤其是在节点密度较低的情况下体现出较强的优势。     

贪婪协议路由代数及其应用

在无线网络路由协议中,错误地使用路由尺度会降低网络的路由性能,甚至会导致某些节点之间根本无法正常通信,称为路由尺度的兼容性问题.基于路由代数理论,分析了贪婪协议中路由尺度的兼容性问题,推导出了贪婪算法用作数据分组的转发机制时贪婪协议具有可达性的充分必要条件,并以4个路由尺度实例说明了分析结论在贪婪协议设计中的具体应用,为贪婪协议的设计提供了重要的技术依据.     

改进的遗传算法求解旅行商问题

提出一种解决旅行商问题的改进遗传算法.在传统遗传算法的基础上,引入贪婪算法进行种群初始化;从遗传进化代数和个体适应函数值两个方面实现遗传参数自适应调节,在加快寻优速度的同时防止寻优陷入局部最优;采用基于贪婪方法的启发式交叉算子优化交叉结果;对交叉前后的种群分别实施精英个体保留策略,保证最优基因结构得以延续.实验结果分析表明,改进的遗传算法可以在种群规模较小的情况下具有更可靠的寻优能力.     

改进的基于地理位置的可靠车载网络路由协议

提出了一种新的基于地理位置信息的车载网络路由协议——GDGP。GDGP是一种包转发机制,在进行包转发时将贪婪转发与方向转发相结合,通过两个独立的消息交互机制,更新各个节点上存储的目的节点的位置信息,以确保各个节点上记录的目的节点的位置信息的一致性,进而保证路由算法的可靠性。利用NS-2仿真平台,采取接近现实车辆运动情况的节点运动模式进行实验,和已有的GPSR路由协议进行比较。仿真结果表明,改进的路由协议在城市场景中有较好的性能。     

Design and analysis of a multi-candidate selection scheme for greedy routing in wireless sensor networks

Sleep and wake-up scheduling of sensor nodes is an efficient solution to prolong the network lifetime. However, existing scheduling algorithms may significantly decrease the number of active nodes so that the network may be intermittently connected. In such networks, traditional geographic routing protocols are inappropriate to obtain low latency routes due to route discovery and data forwarding latency. In this paper, we propose a novel multi-candidate selection (MCS) scheme for greedy routing that makes the best effort to find minimum latency routes in the sensor networks. In MCS, each source node sends an RREQ to a list of first wake-up forwarder candidates and selects a route with minimum estimated delivery latency based on their replies. The route found by MCS may be longer than that of distance-based greedy forwarding (DGF) (Finn, 1987). Hence, we introduce a latency-adaptive distance-based multi-candidate selection scheme for greedy forwarding to find routes with a small number of hops and acceptable delivery latency. Probabilistic analysis and simulation results demonstrate that MCS increases the routing performance significantly compared with DGF and ODML (Su et al., 2008) in terms of delivery latency.     

贪婪封装二进制差分进化算法求解高维背包问题

提出一种处理高维背包问题(KP)的贪婪封装二进制差分进化算法(GPBDE),并设计了一种贪婪封装的修补策略处理不可行解.为了提高种群的多样性及算法的全局搜索能力,对适应度较低的个体执行对偶变换.数值实验选取4种KP对GPBDE的优化能力进行测试,并将所提出的算法与4种同类算法进行比较,结果表明,GPBDE具有较强的寻优和约束处理能力,且收敛速度较快.     

Experimental validation of resilient tree-based greedy geometric routing

Geometric routing is an alternative for IP routing based on longest prefix matching. Using this routing paradigm, every node in the network is assigned a coordinate and packets are forwarded towards their intended destination following a distance-decreasing policy (greedy forwarding). This approach makes the routers significantly more memory-efficient compared to the current IP routers. In this routing, greedy embeddings are used to guarantee a 100% successful delivery to every destination in the network. Most of the existing proposals lack resiliency mechanisms to react efficiently to network changes. We propose a distributed algorithm to calculate a greedy embedding based on a spanning tree of the network. In this algorithm, nodes are triggered to re-calculate their coordinates upon a change in the topology such as link or node failures. The advantage of this approach is that it recovers from topology failures within a very short period of time. We further extend the algorithm to generate backups to apply protection in distributed setups. Different trade-offs and trends of re-convergence for geometric routing have been evaluated in an emulation environment. Realistic results are achieved through emulation as no model or abstraction is involved. The proposed routing scheme is implemented in Quagga routing software and new elements are developed in Click modular router to enable greedy forwarding. For the first time, the performance of this scheme is evaluated through emulation on a large topology of 1000 nodes and the results are compared with BGP. The experimental results indicate that the proposed scheme has interesting characteristics in terms of convergence time upon a change in the network topology.     

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

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

基于联合配送的城市物流配送路径优化

针对城市多区域协同发展造成的商业中心相对分散的现状, 提出“多对多” 的城市网络化联合配送机制. 以运输距离、实载率等与成本密切相关的油耗成本为优化目标, 建立面向城市多区域配送需求的车辆路径模型; 同时,利用量子比特位设计染色体结构, 利用云模型云滴随机性与稳定性改进遗传算子, 设计云量子遗传算法对所建立的联合配送模型进行求解. 最后, 结合不同算例对模型和算法进行了仿真实验分析.

     

事件驱动传感器网络中基于数据聚合的自适应路由算法

为优化事件驱动传感器网络总能耗,提出一个基于数据聚合的自适应路由算法,它能够实现低控制开销的事件域节点分布式成簇,计算并借助于路由汇聚中心,建立一棵基于事件的近似Steiner树,有效减少网内数据分组与控制分组的传输量.理论分析与实验表明,该算法的路由结构建立与维护开销较少,能优化数据聚合效率,实现高能效的数据收集,提升网络性能.