无线传感器网络体系结构和关键技术研究

文章介绍了无线传感器网络的体系结构,提出了一种基于跨层设计的管理控制机制;在对无线传感器网络的关键技术,如媒体接入控制(MAC)技术和无线路由协议,分别进行阐述和比较的基础上,提出了一种把简单的IEEE 802 MAC协议应用于无线传感器网络的思想;为了提高系统容量,提出了多信道策略,可以用来有效减少系统碰撞阻塞率,减少接入时延;认为虽然无线传感器网络的应用前景非常广阔,但是仍存在很多问题,除了要尽量减少功耗外,必须提高系统容量,减少碰撞阻塞率,以加快无线传感器网络实用化的进程.     

A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries,Selective Pickups and Time Windows

In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers.     

A memetic algorithm with dynamic population management for an integrated production–distribution problem

This paper studies an NP-hard multi-period production–distribution problem to minimize the sum of three costs: production setups, inventories and distribution. This problem is solved by a very recent form of metaheuristic called memetic algorithm with population management (MA∣PM). Contrary to classical two-phase methods (production planning, then distribution planning), the algorithm simultaneously tackles production and distribution decisions. Several versions with different population management strategies are evaluated and compared with a two-phase heuristic and a Greedy Randomized Adaptive Search Procedure (GRASP), on 90 randomly generated instances with 20 periods and 50, 100 or 200 customers. The significant savings obtained compared to the two other methods confirm both the interest of integrating production and distribution decisions and of using the MA∣PM template.     

Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns

We study the routing of a single vehicle that delivers multiple products under stochastic demand. Specifically, we investigate two practical variations of this problem: (i) The case in which each product type is stored in its dedicated compartment in the vehicle, and (ii) the case in which all products are stored together in the vehicle’s single compartment. Suitable dynamic programming algorithms are proposed to determine the minimum expected (routing) cost for each case. Furthermore, the optimal routing policy is derived by developing appropriate theorems. The efficiency of the algorithms is studied by solving large problem sets.     

On-Demand Multicast Routing Protocol in Multihop Wireless Mobile Networks

An ad hoc network is a dynamically reconfigurable wireless network with no fixed infrastructure or central administration. Each host is mobile and must act as a router. Routing and multicasting protocols in ad hoc networks are faced with the challenge of delivering data to destinations through multihop routes in the presence of node movements and topology changes. This paper presents the On-Demand Multicast Routing Protocol (ODMRP) for wireless mobile ad hoc networks. ODMRP is a mesh-based, rather than a conventional tree-based, multicast scheme and uses a forwarding group concept; only a subset of nodes forwards the multicast packets via scoped flooding. It applies on-demand procedures to dynamically build routes and maintain multicast group membership. ODMRP is well suited for ad hoc wireless networks with mobile hosts where bandwidth is limited, topology changes frequently, and power is constrained. We evaluate ODMRP performance with other multicast protocols proposed for ad hoc networks via extensive and detailed simulation.     

Geographical Reservation for Guaranteed Handover and Routing in Low Earth Orbit Constellations

In this paper, we address the problem of permanent guaranteed routing through a LEO satellite constellation with inter-satellite links. A reduction to a geometric problem of intersection of rectangles is given, along with algorithmic issues. We express the problem on a very simple model, and discuss the extension to more complicated schemes. We present some experimental results based on this framework that demonstrate the efficiency of the method in a call admission control process.     

一种新的无网格拆线重布算法

结合无网格布线的特点,提出一种新的无网格拆线重布算法.该算法显式地表示并动态更新线网所属区域的拥挤程度.在拆线重布进行待布线网的路径搜索时,每个扩展节点中增加拆除线网周边的拥挤权重,从而将待布线网的路径搜索过程和拆除线网的选择过程统一起来,有效地提高了被拆除线网重新布通的可能性.该算法利用改进的二叉区间树有效组织中间数据,降低计算的复杂度.实验结果表明,该算法能有效消除布线顺序对布线结果的影响,提高布通率,且算法运行速度较快.     

一个快速高效进行布线拥挤优化的总体布线器

设计实现了一个高效的线长模式下基于多处理机的并行总体布线器.通过对非时延驱动模式下串、并行算法的总运行时间和求解时间的比较,表明该并行算法能够在保证求解质量无明显变化的前提下大大加快总体布线算法的求解速度.同时,也提出了基于分布式体系结构的并行总体布线算法.     

车辆路径问题的改进遗传算法

提出一种基于遗传算法的求解车辆路径问题的新算法,避免传统遗传算法处理不可行约束条件中惩罚项系数选取不当所出现的问题.同时,通过现实例子分析该算法的优劣性,实验结果表明该算法是一种有效的算法.     

A variable neighborhood search for the capacitated arc routing problem with intermediate facilities

The capacitated arc routing problem (CARP) focuses on servicing edges of an undirected network graph. A wide spectrum of applications like mail delivery, waste collection or street maintenance outlines the relevance of this problem. A realistic variant of the CARP arises from the need of intermediate facilities (IFs) to load up or unload the service vehicle and from tour length restrictions. The proposed Variable Neighborhood Search (VNS) is a simple and robust solution technique which tackles the basic problem as well as its extensions. The VNS shows excellent results on four different benchmark sets. Particularly, for all 120 instances the best known solution could be found and in 71 cases a new best solution was achieved.