Performance evaluation of adaptive routing algorithms in packet‐switched intersatellite link networks

This paper addresses the performance evaluation of adaptive routing algorithms in non‐geostationary packet‐switched satellite communication systems. The dynamic topology of satellite networks and variable traffic load in satellite coverage areas, due to the motion of satellites in their orbit planes, pose stringent requirements to routing algorithms. We have limited the scope of our interest to routing in the intersatellite link (ISL) segment. In order to analyse the applicability of different routing algorithms used in terrestrial networks, and to evaluate the performance of new algorithms designed for satellite networks, we have built a simulation model of a satellite communication system with intersatellite links. In the paper, we present simulation results considering a network‐uniform source/destination distribution model and a uniform source–destination traffic flow, thus showing the inherent routing characteristics of a selected Celestri‐like LEO satellite constellation. The updates of the routing tables are centrally calculated according to the Dijkstra shortest path algorithm. Copyright © 2002 John Wiley & Sons, Ltd.     

基于位置的 Ad Hoc 路由协议现状及发展

基于位置的Ad Hoc路由协议因其消除了对拓扑存储的依赖性,降低了相关能耗,提升了网络性能,成为了学者们重点关注的研究领域。介绍了基于位置的Ad Hoc路由协议的概念,分析了几个典型的基础路由协议,总结了现阶段研究面临的问题,归纳了基于地理位置路由协议国内外研究现状及发展趋势。     

A Stochastic and Dynamic Vehicle Routing Problem with Time Windows and Customer Impatience

In this paper, we study the problem of designing motion strategies for a team of mobile agents, required to fulfill request for on-site service in a given planar region. In our model, each service request is generated by a spatio-temporal stochastic process; once a service request has been generated, it remains active for a certain deterministic amount of time, and then expires. An active service request is fulfilled when one of the mobile agents visits the location of the request. Specific problems we investigate are the following: what is the minimum number of mobile agents needed to ensure that a certain fraction of service requests is fulfilled before expiration? What strategy should they use to ensure that this objective is attained? This problem can be viewed as the stochastic and dynamic version of the well-known vehicle routing problem with time windows. We also extend our analysis to the case in which the time service requests remain active is itself a random variable, describing customer impatience. The customers’ impatience is only known to the mobile agents via prior statistics. In this case, it is desired to minimize the fraction of service requests missed because of impatience. Finally, we show how the routing strategies presented in the paper can be executed in a distributed fashion.     

Risky traveling salesman problem

In this paper we introduce a methodology for optimizing the expected cost of routing a single vehicle which has a probability of breaking down or failing to complete some of its tasks. More specifically, a calculus is devised for finding the optimal order in which each site should be visited.     

The snowblower problem

We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a snowblower passes over each region along the tour, it displaces snow into a nearby region. The constraint is that if the snow is piled too high, then the snowblower cannot clear the pile.We give an algorithmic study of the SBP. We show that in general, the problem is NP-complete, and we present polynomial-time approximation algorithms for removing snow under various assumptions about the operation of the snowblower. Most commercially available snowblowers allow the user to control the direction in which the snow is thrown. We differentiate between the cases in which the snow can be thrown in any direction, in any direction except backwards, and only to the right. For all cases, we give constant-factor approximation algorithms; the constants increase as the throw direction becomes more restricted. Our results are also applicable to robotic vacuuming (or lawnmowing) with bounded-capacity dust bin.     

Distributed Borrowing Addressing Scheme for ZigBee/IEEE 802.15.4 Wireless Sensor Networks

This paper proposes a distributed borrowing addressing (DIBA) scheme to solve problems of failure in address assignments resulting from limited tree depth and width when the distributed address assignment mechanism is used in a ZigBee/IEEE 802.15.4 wireless sensor network. DIBA is a method of borrowing addresses from neighbor nodes for newly entering nodes and assigning the borrowed addresses. Its network or sensing coverage can increase with almost the same overhead as the existing method. DIBA is a simple and lightweight means of addressing and routing, making it suitable for wireless sensor networks. Simulations showed that DIBA is a distributed addressing scheme with consistently excellent performance.     

A concurrent two-layer restoration scheme for GMPLS WDM networks

Next generation backbone networks will likely consist of IP routers as well as optical cross connects (OXCs) and will deploy an optical control plane protocol. Generalized Multi Protocol Label Switching (GMPLS) has been proposed as the candidate of choice for the control plane. Optical fibers may carry large volumes of traffic and therefore adequate mechanisms must exist to enable the network to automatically recover from failures of fiber. In mission critical networks survivability becomes very important. We investigate the problem of autonomous recovery in such networks. The literature contains work in this area that investigates the problem of multilayer recovery. Such recovery had only been sequential in the sense that the published work recovers first in the optical domain, assuming the availability of redundant resources, and then proceeds to recover packet label switched paths. We report a recovery procedure for recovering packet label switch paths (packet LSPs) and lambda label switch paths (λLSP) concurrently. We have conducted an OPNET-based simulation study that compares the performance of the concurrent scheme with the previously published sequential two-layer recovery scheme. The study shows that the concurrent two-layer recovery scheme performs as much as forty-four percent faster than the sequential two-layer recovery scheme.     

IP网流量工程的一种权值设置方法

提出一种新的基于传统路由协议的流量控制方法。该方法首先在不限制总流量条件下求解最小化最大连接利用率。然后在固定最大连接利用率条件下最小化总流量。由此求得最优流量分配方案并从其对偶问题中求出各连接的权值配置。实验结果显示，文中算法较现有算法明显降低最大连接利用率，并且增加了稳定性。     

Integrated Routing Algorithms for Provisioning “Sub-Wavelength” Connections in IP-Over-WDM Networks

This work focuses on developing and implementing comprehensive unified constraint-based routing algorithms within the generalized multi-protocol label switching framework (GMPLS) to provision sub-wavelength circuits (low-rate traffic streams). Constraint-based routing is further augmented in this work by dynamically routing both an active and another alternate link/node-disjoint backup path at the same time in order to provision a given connection request. This new integrated approach combines both IP routing and optical resource allocation to setup end-to-end connections.     

MANET中基于动态拓扑的多路径自适应流量分配算法

移动自主网络中的大多数多路径路由方案几乎没有考虑流量分配和负载均衡问题。显然,无论路径质量好坏给每条路径分配相同的负荷,会大大降低多路径路由机制的性能,最后会大幅增加网络的通信开销和节点的处理开销。围绕这些问题,提出了一个基于动态拓扑的多路径自适应动态流量分配方案,根据路径质量的权重来动态地给多条路径分配数据流量的比例。大多数情况下仅用局部的信息做路由决定,因此大大减少网络开销。在OPNET模拟平台中实现了这个协议,结果表明,该方案对于MANET网络来说的确是一个可行的方法。