Routing with multiple quality-of-services constraints: An approximation perspective

Finding a path that satisfies multiple Quality-of-Service (QoS) constraints is vital to the deployment of current emerged services. However, existing algorithms are not very efficient and effective at finding such a path. Moreover, few works focus on three or more QoS constraints. In this paper, we present an enhanced version of fully polynomial time approximation scheme (EFPTAS) for multiconstrainted path optimal (MCOP) problem. Specifically, we make four major contributions. We first allow the proposed algorithm to construct an auxiliary graph, through which the QoS parameters on each of the finding path can be guaranteed not to exceed the given constraints. Then we adopt a concept, called nonlinear definition of path constraints in EFPTAS for reducing both time and space complexity. Also, we enable EFPTAS to run iteratively to facilitate a progressive refinement of the finding result. In addition to these, we identify some “deployment” issues for proposed algorithm, the essential steps that how and when the EFPTAS takes place are presented. By analyzing the proposed algorithm theoretically, we find that the presented EFPTAS can find a (1+ε)-approximation path in the network with time complexity O(|E||V|/ε) (where |E| is the number of edges and |V| is the number of nodes), which outperforms the previous best-known algorithm for MCOP. We conduct an extensive comparison between the algorithm presented in this paper and previous best-known study experimentally, our results indicate that EFPTAS can find a path with low complexity and preferable quality.     

A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests

Combinatorial optimization problems are usually modeled in a static fashion. In this kind of problems, all data are known in advance, i.e. before the optimization process has started. However, in practice, many problems are dynamic, and change while the optimization is in progress. For example, in the dynamic vehicle routing problem (DVRP), new orders arrive when the working day plan is in progress. In this case, routes must be reconfigured dynamically while executing the current simulation. The DVRP is an extension of a conventional routing problem, its main interest being the connection to many real word applications (repair services, courier mail services, dial-a-ride services, etc.). In this article, a DVRP is examined, and solving methods based on particle swarm optimization and variable neighborhood search paradigms are proposed. The performance of both approaches is evaluated using a new set of benchmarks that we introduce here as well as existing benchmarks in the literature. Finally, we measure the behavior of both methods in terms of dynamic adaptation.     

A preliminary study of a diagonal channel-routing model

The layout of two-terminal nets in a VLSI channel is realized in a new diagonal channel-routing model (DCRM), where the tracks are segments respectively displayed at +45 ° and –45 ° on the two layers of the channel. A new definition of channel density is introduced, and a lower bound to the channel width is derived by the application of an algorithm, whose complexity is evaluated as a function of the channel density, and other parameters of the problem.A simple linear-time algorithm is proposed, which produces an optimal layout (i.e., it requires a channel of minimum width) if the length of the longest net equals the lower bound for the channel width. In any case, the number of vias is at most one for each net. Some particular solutions are proposed for problems with long nets.Specific problems are much easier in DCRM than in the classical Manhattan model. For example, any shift-by-i can be realized in DCRM in a channel of widthi.This work has been supported by Consiglio Nazionale delle Ricerche of Italy under a research grant.     

非相似度保持投影

由主成分分析(PCA)可知任何一幅人脸图像都可以通过一组特征脸的线性加权来重构,PCA是最小均方误差意义下图像的最优表示,但是传统的PCA最终只通过比较加权系数的欧氏距离来进行识别,没有考虑残差。因此,提出非相似尺度的概念,将两个样本同时投影到相同向量上,在确定它们关系时既考虑投影系数,也考虑重构所产生的残差。两者的投影系数和残差相差越大,说明这两个样本越不相似。和保局投影(LPP)有所不同,非相似度保持投影算法不必预先设定近邻个数,它是利用非相似度的概念,创建非相似度散布矩阵,最终通过最大化目标函数获取最优子空间。在AR库和Feret库上的实验结果证明了该方法的有效性。     

改进的蚁群算法在飞行路径模型中的应用

为了保障飞机安全地运行,FAA规定每架飞机在飞行一定时间后都要进行周期性检修。通常考虑到检修成本,任一种检修都要在指定的机场完成,因此要求飞机每飞行一定的小时数后都要返回到指定的维护基地进行定期检修。如何合理地进行飞机飞行路径的调度以使飞机周期性地返回指定检修机场进行检修是本文研究的关键。为了问题简化,本文主要针对单检修基地、单机型的检修路径调度问题进行研究。本文结合经典蚁群算法,对现有算法参数的设置及信息的更新等方面进行改进后应用到飞行路径模型中,并运用Matlab对该算法编程,运用具体数据进行计算实现,确保了飞机周期性返回检修机场,实现周期性检修。     

基于种群多样性的自适应PSO算法求解VRPSPD问题

为有效求解逆向物流车辆路径(VRPSPD)模型,本文提出一种基于种群多样性的自适应PSO算法(SDAPSO)。在SDAPSO运行时,根据种群多样性,自适应地对种群中运行较差的粒子进行扰动操作,提升这些粒子向最优解收敛的能力;同时,对全局最优粒子进行概率扰动,以增加种群的多样性。标准检测函数的仿真结果表明SDAPSO算法是对基本PSO算法的有效改进。在对VRPSPD模型求解中,通过与其它粒子群算法相比,表明SDAPSO是求解该类问题的一种有效方法。     

一种无线链状网络路由算法的研究与应用

文章基于货运列车状态监控的无线传感器网络应用,针对网络节点能量有限以及链状网络节点负载不均衡的问题进行分析和研究,提出一种适合该应用的新型路由算法,该算法基于网络节点可通过功率控制来调整通信距离这一前提,为每个传感器节点选择合适的数据传输路径,以达到整个网络节省能耗,负载均衡的目的。仿真结果验证了该算法有效地平衡了网络负载,节省了网络能量,提高了网络生命周期。     

A faster divide-and-conquer algorithm for constructing delaunay triangulations

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its (n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn2¹⁶, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL _p metric for 1<p.This research was supported by National Science Foundation Grants DCR-8352081 and DCR-8416190.     

5G时代下的移动自组织网络探讨

移动自组织网络在高带宽低延时的5G下,赋予更多的技术优势,使其综合性、应用性以及系统性都得到有效的提高,本文从基于5G移动自组织网络展开探讨,论述移动自组织mesh的网络架构技术及其应用前景和未来趋势。     

无线传感器网络多路径路由协议研究进展*

在研究目前存在的多径路由协议特点及核心路由机制基础上,总结了多路径路由协议的特征,并对不同的多路径路由相关项进行了比较。最后指出了多路径路由的研究思路以及未来的发展趋势。