一种基于博弈论的无线网状网络路由与信道分配联合优化算法

无线网络中的路由与信道分配可极大地影响网络的性能.为了解决无线网状网络中的路由与信道分配问题,提出并研究了一种称为CRAG(基于博弈论的无线网状网络路由与信道分配联合优化)的方法.CRAG采用协同博弈的方式将网络中的每个节点模型化为一个弈者,每个弈者的策略为与其相关的路由与信道分配方案,收益函数为给定流量需求矩阵下的成功传输流量.弈者通过协同博弈来优化收益函数以最大化网络的吞吐量.基于NS3的仿真结果表明,CRAG在收敛性、时延、丢包率和吞吐量方面优于其他当前的算法,从而证明了协同博弈的方法可以用于无线网状网络的路由与信道分配联合优化,并有效地改进网络性能.     

Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

基于树分解/合并策略的QoS多播路由方法

针对多约束QoS多播路由的NP-Complete特性,提出一种可控的多播树分解与合并策略,使多播树的生成在兼顾低费用的同时具有多样性,有效克服多播路由优化的局部极值问题。基于该策略设计蚁群算法,分解蚂蚁种群为与多播目标点相对应的蚂蚁子群,引入基于“死点”惩罚和多播树奖惩的信息素更新机制,提高了算法的收敛速度。仿真实验表明,该方法能有效地解决QoS多播路由问题,且随着网络规模的增大保持了良好的性能。     

Transformations of node‐balanced routing problems

This article describes a polynomial transformation for a class of unit‐demand vehicle routing problems, named node‐balanced routing problems (BRP), where the number of nodes on each route is restricted to be in an interval such that the workload across the routes is balanced. The transformation is general in that it can be applied to single or multiple depot, homogeneous or heterogeneous fleet BRPs, and any combination thereof. At the heart of the procedure lies transforming the BRP into a generalized traveling salesman problem (TSP), which can then be transformed into a TSP. The transformed graph exhibits special properties which can be exploited to significantly reduce the number of arcs, and used to construct a formulation for the resulting TSP that amounts to no more than that of a constrained assignment problem. Computational results on a number of instances are presented. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 370–387, 2015     

无线传感器网络动态汇聚节点调度算法研究

移动汇聚节点调度是传感器网络中一个新的研究热点.通过建立一个普适的多目标优化模型,提出了贴近实际的汇聚节点循环路径规划模型,采用以连续时间离散化为理论基础的时域-空域转化方法,将时域中的优化模型无损地转至空域中,从而大大减少了所涉及的变量数量,降低了求解的复杂度.通过实验可以看出,调度移动汇聚节点可以有效扩展网络的生命周期.     

Modeling and analysis of flexible queueing systems

We consider queueing systems with multiple classes of customers and heterogeneous servers where customers have the flexibility of being processed by more than one server and servers possess the capability of processing more than one customer class. We provide a unified framework for the modeling and analysis of these systems under arbitrary customer and server flexibility and for a rich set of control policies that includes customer/server‐specific priority schemes for server and customer selection. We use our models to generate several insights into the effect of system configuration and control policies. In particular, we examine the relationship between flexibility, control policies and throughput under varying assumptions for system parameters. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Network routing for insurgency: An adversarial risk analysis framework

Problems in counterterrorism and corporate competition have prompted research that attempts to combine statistical risk analysis with game theory in ways that support practical decision making. This article applies these methods of adversarial risk analysis to the problem of selecting a route through a network in which an opponent chooses vertices for ambush. The motivating application is convoy routing across a road network when there may be improvised explosive devices and imperfect intelligence about their locations. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

面向片上网络的多播吞吐率和能量模型

片上网络逐渐成为片上众核中非常有前景的互连方式.基于目录的cache一致性协议的维护需要片上互连网络高效的支持多播.在借鉴单播的网络吞吐率模型基础上,建立了面向多播的网络吞吐率模型和体系结构级的能量模型.相对于传统的多播路由算法,负载平衡维序路由算法(BDoR)和最小路径维序路由算法(MPDoR)通过平衡X和Y两个方向...     

求最大数目不相交多约束QoS路由的一种新方法

针对多约束QoS路由问题中从资源点到目的点的最大数目的不相交路由,文章给出了一种基于罚函数与整数规划的求满足QoS约束的最大数目的互不相交路由算法。该算法利用了路由模型的结构特性,使整数规划问题转化为线性规划问题,初步的算例表明算法是有效的。