无线 Ad hoc 网络和传感网络中基于位置的、可靠的无信标传输路由方法

Existing position-based routing algorithms, where packets are forwarded in the geographic direction of the destination, normally require that the forwarding node should know the positions of all neighbors in its transmission range. This information on direct neighbors is gained by observing beacon messages that each node sends out periodically. Several beaconless greedy routing schemes have been proposed recently. However, none of the existing beaconless schemes guarantee the delivery of packets. Moreover, they incur communication overhead by sending excessive control messages or by broadcasting data packets. In this paper, we describe how existing localized position based routing schemes that guarantee delivery can be made beaconless, while preserving the same routes. In our guaranteed delivery beaconless routing scheme, the next hop is selected through the use of control RTS/CTS messages and biased timeouts. In greedy mode, the neighbor closest to destination responds first. In recovery mode, nodes closer to the source will select shorter timeouts, so that other neighbors, overhearing CTS packets, can eliminate their own CTS packets if they realize that their link to the source is not part of Gabriel graph. Nodes also cancel their packets after receiving data message sent by source to the selected neighbor. We analyze the behavior of our scheme on our simulation environment assuming ideal MAC, following GOAFR+ and GFG routing schemes. Our results demonstrate low communication overhead in addition to guaranteed delivery.     

On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs

Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. It has been an open conjecture whether every 3-connected plane graph has a greedy drawing in the Euclidean plane R ² (by Papadimitriou and Ratajczak in Theor. Comp. Sci. 344(1):3–14, 2005). Leighton and Moitra (Discrete Comput. Geom. 44(3):686–705, 2010) recently settled this conjecture positively. One main drawback of this approach is that the coordinates of the virtual locations require Ω(nlogn) bits to represent (the same space usage as traditional routing table approaches). This makes greedy routing infeasible in applications. In this paper, we show that the classical Schnyder drawing in R ² of plane triangulations is greedy with respect to a simple natural metric function H(u,v) over R ² that is equivalent to Euclidean metric D _E (u,v) (in the sense that $D_{E}(u,v) \leq H(u,v) \leq2\sqrt{2}D_{E}(u,v)$ ). The drawing uses two integer coordinates between 0 and 2n?5, which can be represented by logn bits. We also show that the classical Schnyder drawing in R ² of 3-connected plane graphs is weakly greedy with respect to the same metric function H(?,?). The drawing uses two integer coordinates between 0 and f (where f is the number of internal faces of G).     

Compact Routing on Chordal Rings of Degree 4

A chordal ring G(n;c) of degree 4 is a ring of n nodes with chords connecting each vertex i to the vertex (i + c) mod n . In this paper we investigate compact routing schemes on such networks. We show an optimal boolean routing scheme for any such network that requires O( log n) bits of storage at each node, and O(1) time to compute a shortest path to any destination. This improves on the results of [16] which gives a linear time algorithm for such networks and [6] where efficient routing schemes for certain fixed values of c were developed. Further, we show several bounds on interval routing schemes for such networks. We show that while every chordal ring has an optimal interval routing scheme with at most intervals on any edge, there exist chordal rings for which any optimal interval routing scheme that labels the vertices around the ring in the graph requires intervals on some edges. Additionally, there are chordal rings which admit no optimal one-interval routing schemes, regardless of the vertex labeling. We also consider interval routing schemes under relaxed requirements for the lengths of paths. Received September 5, 1997; revised December 1, 1997.     

高动态航空自组网中考虑优先级的逐跳路由协议

针对航空自组网频繁的拓扑变化、网络断开的问题,提出一种考虑优先级的逐跳路由（priority concern hop-by-hop routing,PCHHR）协议。PCHHR依据运动方向优先、距离次之的原则选择下一跳路由节点,优先选择向目的节点运动的邻居作为下一跳节点,次优选择距离目的节点最近的邻居作为下一跳节点;区分数据报文的时延需求,优先转发时延约束小的数据。仿真结果表明,PCHHR在较低的控制开销和端到端时延下,总体数据分组投递率高于航空路由协议（aeronautical routing protocol,AeroRP）、贪婪转发路由和传统的端到端路由协议,提高了高实时性数据分组的投递率。     

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

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

Unicast-based fault-tolerant multicasting in wormhole-routed hypercubes

A unicast-based fault-tolerant multicasting method is proposed for hypercubes, which can still work well when the system contains enough faults. A multicast message may be unable to reach a destination if Hamming distance between the destination and the multicast source is large enough. A multicast message fails if any one of the destinations is unreachable from the source. An effective destination ordering scheme of the destinations is proposed for one-port systems first, it is extended to all-port systems for unicast-based fault-tolerant multicasting. Unreachable destinations from the source based on the local safety information are forwarded to a reachable destination, where the multicast message can be routed reliably. Destination ordering is completed based on Hamming distance. A multiple round p-cube routing scheme is presented for a deadlock-free fault-tolerant routing for each unicast step in hypercubes, where the same virtual channel is used for each round of p-cube routing. Sufficient simulation results are presented by comparing with the previous methods.     

A Lower Bound for Nearly Minimal Adaptive and Hot Potato Algorithms

Recently, Chinn et al. [10] presented lower bounds for store-and-forward permutation routing algorithms on the n \times n mesh with bounded buffer size and where a packet must take a shortest (or minimal ) path to its destination. We extend their analysis to algorithms that are nearly minimal. We also apply this technique to the domain of hot potato algorithms, where there is no storage of packets and the shortest path to a destination is not assumed (and is in general impossible). We show that ``natural' variants and ``improvements' of several algorithms in the literature perform poorly in the worst case. As a result, we identify algorithmic features that are undesirable for worst-case hot potato permutation routing. Recent works in hot potato routing have tried to define simple and greedy classes of algorithms. We show that when an algorithm is too simple and too greedy, its performance in routing permutations is poor in the worst case. Specifically, the technique of [10] is also applicable to algorithms that do not necessarily send packets in minimal or even nearly minimal paths: it may be enough that they naively attempt to do so when possible. In particular, our results show that a certain class of greedy algorithms that was suggested recently by Ben-Dor et al. [6] contains algorithms that have poor performance in routing worst-case permutations. Received August 24, 1995; revised May 27, 1997.     

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

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

Concurrent face traversal for efficient geometric routing

We present a concurrent face routing CFR algorithm. We formally prove that the worst case latency of our algorithm is asymptotically optimal. Our simulation results demonstrate that, on average, the path stretch, i.e., the speed of message delivery, achieved by CFR is significantly better than by other known geometric routing algorithms. In fact, it approaches the shortest possible path. CFR maintains its advantage over the other algorithms in pure form as well as in combination with greedy routing. CFR displays this performance superiority both on planar and non-planar graphs.     

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.     

A dynamic fault-tolerant message routing algorithm for double-loop networks

Message routing is a fundamental function of a network, and fault-tolerance is an important tool to ensure the quality of service of a network. Assume that the network contains at most one faulty element and the algorithm does not know the faulty element in advance. We present an optimal fault-tolerant message routing algorithm for double-loop networks. We show that sending at most two messages with different routing strategies can ensure that one of the messages will be sent through a shortest path that avoids the faulty element. At each vertex, for any destination, the algorithm needs only constant time and space to determine the next vertex to which the message is to be sent.     

基于方向预测的移动自组网概率转发算法

移动自组网中传统的路由算法大多采用拉网式的盲搜索,导致路由开销较大,针对这一问题,提出一种基于方向预测的概率转发算法。该算法通过监听网络中传输的各种数据包,从中提取节点ID和时间信息,这些信息反映了到目的节点的距离;在此基础上,计算节点的转发概率,并根据网络的变化自适应地调整,使得路由过程始终沿着目的节点所在方向进行,限定了搜索区域。仿真结果表明,该算法的路由开销比洪泛降低了70%,比经典概率转发算法降低了20%,提高了网络性能。     

A parallel routing algorithm on recursive cube of rings networks employing Hamiltonian circuit Latin square

Recursive cube of rings (RCR) networks [Y. Sun, P. Cheung, X. Lin, Recursive cube of rings: a new topology for interconnection networks, IEEE Trans. Parallel Dist. Syst. 11 (3) (2000) 275-286] can be widely used in the design and implementation of parallel processing architectures. In this paper, we investigate the routing of a message on RCR networks, that is a key to the performance of this network. We would like to transmit k+1 packets from a source node to a destination node simultaneously along paths on RCR networks, the ith packet will traverse along the ith path (1?i?k+1). In order for all packets to arrive at a destination node quickly and securely, the ith path must be node-disjoint from all other paths. For construction of these paths, employing Hamiltonian circuit Latin square (HCLS), we present O(n²) parallel routing algorithm on RCR networks.     

Fault-Tolerant Permutation Routing in Hypercubes

This paper introduces a deterministic mechanism for fault-tolerant permutation routing on an n-cube with less than n processor and/or link faults, using O(n) steps and constant queue size. The basic approach is to modify an existing route of a given permutation to avoid the faulty processors and/or faulty links, yet only incurring a constant factor slowdown in communication by ensuring that, at each step of the routing, every message either stays where it is or is sent to a nonfaulty neighbor, each link has at most one message traversing it in each direction, and the routing uses constant queue size. The existing route used in this paper is Benes routes. However, our method can be applied to any routing method where, in each step, all messages use links across the same dimension. The same approach can also be applied to online routing based on Batcher′s bitonic sorting to avoid faults.     

An exact algorithm and a metaheuristic for the generalized vehicle routing problem with flexible fleet size

The generalized vehicle routing problem (GVRP) involves finding a minimum-length set of vehicle routes passing through a set of clusters, where each cluster contains a number of vertices, such that the tour includes exactly one vertex from each cluster and satisfies capacity constraints. We consider a version of the GVRP where the number of vehicles is a decision variable. This paper introduces a new mathematical formulation based on a two-commodity flow model. We solve the problem using a branch-and-cut algorithm and a metaheuristic that is a hybrid of the greedy randomized adaptive search procedure (GRASP) and the evolutionary local search (ELS) proposed in [18]. We perform computational experiments on instances from the literature to demonstrate the performance of our algorithms.     

基于邻居缓存的AODV路由协议

在移动自组网（MANET）中,传统的洪泛和扩展环路由发现方法路由开销较大。针对这一问题,提出一种基于邻居缓存的路由发现算法。该算法从网络中的各种数据分组中提取单跳邻居信息,建立邻居信息缓存表。在此基础上,将路由搜索分解为两个步骤：1）寻找刚刚和目标节点接触过的节点;2）找到后以它为中心展开新的扩展环搜索。使搜索限定在目标节点最可能出现的区域,减少了路由发现的盲目性,从而降低路由开销。仿真结果表明,与洪泛和传统扩展环算法相比,该方法节省了路由开销,提高了网络性能。     

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

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

一种基于分治策略的多路径Ad Hoc路由协议

在无线自组织网络(MANET)中,比起单路径路由协议,多路径路由协议提供了更好的可靠性、容错性、负载平衡等,并且提供较小的端对端延迟、提供较大的有效总带宽;但是,当网络规模较大、通信节点之间相距较远时,多路径路由协议的开销会很大,多路径的条数也减少.针对这一问题,提出了一种基于分治思想的多路径路由协议(DCMR).当通信节点之间必须经过的节点较多时,将这些节点划分为较小的节点集,对各个节点集分别进行路径查找及维护.模拟实验表明,该协议明显提高了路由寻径效率,减小了网络维护开销,并且实现简单,更具实用性.     

There is no optimal routing policy for the torus

A routing policy is the method used to select a specific output channel for a message from among a number of acceptable output channels. An optimal routing policy is a policy that maximizes the probability of a message reaching its destination without delays. Optimal routing policies have been proposed for several regular networks, including the mesh and the hypercube. An open problem in interconnection network research has been the identification of an optimal routing policy for the torus. In this paper, we show that there is no optimal routing policy for the torus. Our result is demonstrated by presenting a detailed example in which the best choice of output channel is dependent on the probability of each channel being available. This result settles, in the negative, a conjecture by Wu concerning an optimal routing policy for the torus.     

基于路由长度的多径路由协议

针对单径路由协议在高速Ad hoc网络中平均端到端时延和丢包率高的问题,在动态源路由协议的基础上,提出基于邻居节点变化率与路由长度的多径路由协议DSR_HD。利用HELLO消息获得一跳范围内可用邻居数,根据邻居数求得节点的邻居节点变化率。在路由发现过程中,采用路由距离与路由跳数相结合的方法计算路由长度,并选择邻居节点变化率和路由长度低的节点加入路由,从而提高路由的稳定性。仿真实验结果显示,DSR_HD协议可以有效减少数据分组传输的端到端时延及路由开销,提高分组成功投递率。