基于非均匀分簇的无线传感器网络路由协议

在无线传感器网络中,分簇技术是一种有效延长网络生命周期的方法。但是这种多跳的网络模型,如果节点均匀分布并且簇的大小相等,则靠近基站的簇头由于要中继更多的数据,则会导致能量空洞现象。因此提出一种非均匀分簇方法来缓解能量空洞问题。首先,通过节点的剩余能量、到基站的距离以及邻居节点数量来选择簇头。簇一旦形成之后,通过单跳和多跳的混合机制将数据发送到基站。实验结果表明,此协议能有效的延长网络的生命周期,均衡网络能耗,有效延缓能量空洞的形成速度。     

Design of a Two layer Scalable Wavelength Routing Optical Interconnection Network

１　Ｉｎｔｒｏｄｕｃｔｉｏｎ　　Ｈｉｇｈｐｅｒｆｏｒｍａｎｃｅｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｐｌａｔｆｏｒｍｍａｄｅｕｐｏｆｗｏｒｋｓｔａｔｉｏｎｓｏｒｐｅｒｓｏｎａｌｃｏｍｐｕｔｅｒｓｉｎｔｅｒｃｏｎｎｅｃｔｅｄｂｙｎｅｔｗｏｒｋｈａｓｂｅｃｏｍｅｔｈｅｍａｉｎｄｅｖｅｌｏｐｍｅｎｔｓｔｒｅａｍｏｆｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｔｅｃｈｎｏｌｏｇｉｅｓ［１,２］．Ｗｉｔｈｔｈｅｅｎｈａｎｃｅｍｅｎｔｏｆｎｏｄｅｃｏｍｐｕｔｅｒｐｒｏｃｅｓｓｉｎｇｃａｐａｂｉｌｉｔｉｅｓ,ｉｔｂｅｃｏｍ…     

Routing multiterminal nets on a hexagonal grid

Channel routing is a vital task in the layout design of VLSI circuits. Multiterminal channel routing is different from two-terminal one. While the later is quite understood, the former still poses the difficulty. In this paper, we investigate the multiterminal channel routing problem in a hexagonal model, whose grid is composed of horizontal tracks, right tracks (with slope +60°), and left tracks (with slope −60°). We present an efficient algorithm for routing multiterminal nets on a channel of width d + 3, where d is the problem density. Furthermore, we can wire the layout produced by the router using four layers and there are no overlaps among different layers. This improves the previous known results [15, 19].     

多时间窗车辆路径问题的智能水滴算法

研究了多时间窗车辆路径问题,考虑了车容量、多个硬时间窗限制等约束条件,以动用车辆的固定成本和车辆运行成本之和最小为目标,建立了整数线性规划模型。根据智能水滴算法的基本原理,设计了求解多时间窗车辆路径问题的快速算法,利用具体实例进行了模拟计算,并与遗传算法的计算结果进行了对比分析,结果显示,利用智能水滴算法求解多时间窗车辆路径问题,能够以很高的概率得到全局最优解,是求解多时间窗车辆路径问题的有效算法。     

复杂网络的一种加权路由策略研究

复杂网络的传输能力是其功能正常运转的重要保障,提高网络的吞吐量有着重要意义.提出一种新的高效路由策略,以提高复杂网络的传输能力,称之为加权路由策略.即对网络的每一条边加权,权值与该边的两端节点的度相关,然后数据包按照这个加权网络的最短路径路由.这样的路径可以更均匀地经过各个节点,发挥它们的传输能力,极大地提高网络的吞吐量.可以避免数据包集中地通过个别度大的节点,在这些节点发生拥塞.仿真显示,该策略比传统的最短路径策略优越,对很多结构的网络,可以提高几十倍的吞吐量. 关键词： 复杂网络 路由策略 吞吐量 拥塞     

Blocking probability analysis of pruned optical banyan networks on vertical stacking scheme with extra banyan planes

Vertically stacked pruned optical banyan networks with extra planes (in short, EP-VSOB networks) have lower switch count and optimal time complexity (O(log₂ N)) for routing N input requests. However, blocking probability is relatively higher than that of a VSOB networks using regular banyan planes. In the EP-VSOB architecture, the number of pruned planes has always been considered as , and a few extra planes (regular banyan) have been added with these pruned planes. In this paper we present the results of blocking analysis of a more generalized architecture in which the number of pruned planes can be 2^x, where x ? 0 in addition to the variable extra planes. This generalization helps us make a compromise between different constraints and performance metrics. Our simulation results show that for some given performance requirements (e.g. cost, speed or blocking probability) we can choose a network that has lower switch count compared to -plane pruned crosstalk-free optical banyan networks. For example, to ensure blocking probability <0.02, previously we would chose a pruned network of 32 pruned planes and 1 extra planes (a regular banyan); however, our simulations results show that a network of 16 pruned planes and 2 extra planes is enough to ensure the same performance. It is notable that, the hardware cost decreases by 28.65% in this new combination of pruned and extra planes. We believe our results will provide more flexibility in choosing a particular EP-VSOB network satisfying given requirements.     

An optimization approach for communal home meal delivery service: A case study

This paper is the first to discuss the communal home meal delivery problem. The problem can be modelled as a multiple travelling salesman problem with time windows, that is closely related to the well-studied vehicle routing problem with time windows. Experimental results are reported for a real-life case study from Central Finland over several alternative scenarios using the SPIDER commercial solver. The comparison with current practice reveals that a significant savings potential can be obtained using off-the-shelf optimization tools. As such, the potential for supporting real-life communal routing problems can be considered to be important for VRP practitioners.     

Analysis,modeling and solution of the concrete delivery problem

This paper describes a specific local search approach to solve a problem arising in logistics which we prove to be NP-hard. The problem is a complex scheduling or vehicle routing problem where we have to schedule the tours of concrete mixer vehicles over a working day from concrete-producing depots to concrete-demanding customers and vice versa. We give a general mixed integer programming model which is too hard to solve for state of the art mixed integer programming optimizers in the case of the usually huge problem instances coming from practice. Therefore we present a certain local search approach to be able to handle huge practical problem instances.     

An approximate dynamic programming approach for the vehicle routing problem with stochastic demands

This paper examines approximate dynamic programming algorithms for the single-vehicle routing problem with stochastic demands from a dynamic or reoptimization perspective. The methods extend the rollout algorithm by implementing different base sequences (i.e. a priori solutions), look-ahead policies, and pruning schemes. The paper also considers computing the cost-to-go with Monte Carlo simulation in addition to direct approaches. The best new method found is a two-step lookahead rollout started with a stochastic base sequence. The routing cost is about 4.8% less than the one-step rollout algorithm started with a deterministic sequence. Results also show that Monte Carlo cost-to-go estimation reduces computation time 65% in large instances with little or no loss in solution quality. Moreover, the paper compares results to the perfect information case from solving exact a posteriori solutions for sampled vehicle routing problems. The confidence interval for the overall mean difference is (3.56%, 4.11%).     

An empirical study on the benefit of split loads with the pickup and delivery problem

Splitting loads such that the delivery of certain loads is completed in multiple trips rather than one trip has been shown to have benefit for both the classic Vehicle Routing Problem (VRP) and the Pickup and Delivery Problem (PDP). However, the magnitude of the benefit may be affected by various problem characteristics. In this paper, we characterize those real world environments in which split loads are most likely to be beneficial. Based on practitioner interest, we determine how the benefit is affected by the mean load size and variance, number of origins relative to the number of destinations, the percentage of origin–destination pairs with a load requiring service, and the clustering of origin and destination locations. We find that the magnitude of benefit is greatest for load sizes just over one half vehicle capacity as these loads can not be combined without splitting, while they are the easiest to combine on a vehicle with splitting; increases as the number of loads sharing an origin or destination increases because there are more potential load combinations to split at each stop; and increases as the average distance from an origin to a destination increases because splitting loads reduces the trips from origins to destinations.