Optimal patrol to uncover threats in time when detection is imperfect

Consider a patrol problem, where a patroller traverses a graph through edges to detect potential attacks at nodes. An attack takes a random amount of time to complete. The patroller takes one time unit to move to and inspect an adjacent node, and will detect an ongoing attack with some probability. If an attack completes before it is detected, a cost is incurred. The attack time distribution, the cost due to a successful attack, and the detection probability all depend on the attack node. The patroller seeks a patrol policy that minimizes the expected cost incurred when, and if, an attack eventually happens. We consider two cases. A random attacker chooses where to attack according to predetermined probabilities, while a strategic attacker chooses where to attack to incur the maximal expected cost. In each case, computing the optimal solution, although possible, quickly becomes intractable for problems of practical sizes. Our main contribution is to develop efficient index policies—based on Lagrangian relaxation methodology, and also on approximate dynamic programming—which typically achieve within 1% of optimality with computation time orders of magnitude less than what is required to compute the optimal policy for problems of practical sizes. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 557–576, 2014     

A search game on a cyclic graph

There is a finite cyclic graph. The hider chooses one of all nodes except the specified one, and he hides an (immobile) object there. At the beginning the seeker is at the specified node. After the seeker chooses an ordering of the nodes except the specified one, he examines each nodes in that order until he finds the object, traveling along edges. It costs an amount when he moves from a node to an adjacent one and also when he checks a node. While the hider wishes to maximize the sum of the traveling costs and the examination costs which are required to find the object, the seeker wishes to minimize it. The problem is modeled as a two‐person zero‐sum game. We solve the game when unit costs (traveling cost + examination cost) have geometrical relations depending on nodes. Then we give properties of optimal strategies of both players. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

一类带配送中心运输问题的容量扩张模型研究

运输问题一般采用表上作业法来解决,考虑一类带配送中心的运输问题,若仍采用表上作业法,会使问题复杂化.文中采用一种构造辅助网络的方法:在运输网络中将每个配送中心均拆分成两个点,连接两点形成新弧,构造出新的网络,并给每条弧赋予参数,将此类运输问题转换为最小费用流模型来解决,可以使问题模型和运算简单化.在此基础上,考虑运输网络中配送中心和边的容量扩张问题.     

无线传感器网络在军用仓库中的应用

针对军用仓库环境检测安全防护系统成本高、布线繁琐和维护困难等缺点，提出了采用无线传感器网络技术解决军用仓库环境检测和安全防护问题的新方法。以基于ZigBee技术的无线网络控制器芯片CC2430为核心，设计了由4个温湿度传感器节点、4个烟雾浓度传感器节点、2个红外传感器节点和4个协调器节点组成的3层树状网络结构的实验系统。实验测试结果表明：系统可快速布置并实施监测作业，维护简便，扩展性强，具有良好的鲁棒性和抗干扰能力。     

基于启发式算法的复杂军事网络路径优化

使用一种启发式算法,使得复杂网络中最大介数最小化,可以达到接近最优化的路径,以改善复杂网络的信息容量。针对海上编队作战系统复杂网络的平均介数、最大介数与网络大小、迭代次数、介数分布情况的仿真发现,复杂网络容量超出比对文献中理论预测的最大值,这对于解决复杂军事网络的拥塞,提高复杂军事网络容量和作战效能重大意义。     

无人飞行器Ad Hoc网络中容错节点移动控制算法

针对无人飞行器Ad Hoc网络的容错设计需求,基于UAV节点的可控移动特性,提出了一种基于强化边启发的节点移动控制算法.首先采用文化基因算法对给定通信网络对应的拓扑图进行搜索,求解使图获取顶点2 -连通属性所需新增的最小成本强化边组合.以强化边为启发,将连接的节点移动到彼此通信范围内来实现强化边,同时以这些节点为leader,采用基于一致性算法的leader-follower控制算法移动其他关联节点,使变化后的网络为顶点2-连通,从而实现网络容错.仿真实验结果表明算法的可行性与有效性,节点总的移动距离少于用于对比的块移动算法和紧缩算法.     

军事通信网节点重要度评估方法

针对军事通信网的应用环境和业务流传输的特殊性，考虑节点类型以及节点之间的相互关系，将节点按功能分为侦察节点、处理节点、指控节点、行动节点、传输节点五类节点。根据军事通信网信息流传输的特点，改进了传统的网络介数基本概念，定义了符合军事通信网特征的节点和链路重要度的新指标。最后，通过实例对军事通信网的节点重要度进行仿真计算，画出了所有节点重要度柱状分布图。     

Approximation algorithms for general one‐warehouse multi‐retailer systems

Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross‐docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within ε‐optimality can be obtained by solving a related piece‐wise linear concave cost multi‐commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + ε) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece‐wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece‐wise concavity feature of the cost functions. This gives rise to a unified and generic LP‐based approach for a large class of complicated logistical planning problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

A network isolation algorithm

A set of edges D called an isolation set, is said to isolate a set of nodes R from an undirected network if every chain between the nodes in R contains at least one edge from the set D. Associated with each edge of the network is a positive cost. The isolation problem is concerned with finding an isolation set such that the sum of its edge costs is a minimum. This paper formulates the problem of determining the minimal cost isolation as a 0–1 integer linear programming problem. An algorithm is presented which applies a branch and bound enumerative scheme to a decomposed linear program whose dual subproblems are minimal cost network flow problems. Computational results are given. The problem is also formulated as a special quadratic assignment problem and an algorithm is presented that finds a local optimal solution. This local solution is used for an initial bound.     

卫星中断容忍网络路由算法研究

针对卫星网络易中断、长时延等问题,提出一种适合卫星DTN网络的路由算法——SDTNR算法。该算法在节点缓存中设置了3个存放不同服务等级报文的队列,队列根据报文响应比排序,响应比小的报文优先发送。SDTNR算法根据卫星运行规律,建立节点选择表并实时更新该表,根据表中信息选择满足条件的节点作为下一跳节点,以此保证通信的可靠性。仿真结果表明,SDTNR与EPR、PR、FC 3种算法相比,SDTNR更好地提高了报文的投递率、降低了网络开销和平均时延。     

移动通信网络位置群体节点的挖掘方法

对移动通信网络的位置群体节点进行了优化定位和挖掘,优化移动通信网络的覆盖度和可靠度,传统的位置群体节点挖掘算法采用信息度增益控制挖掘算法,算法不能自主感知节点信息数据的变化,无法实现数据信息的实时传递和决策。提出基于位置群体节点信息融合和滤波控制的移动通信网络位置群体节点的挖掘方法。构建移动通信网络节点的分布模型和信道模型,采用多径信道均衡设计实现位置群体节点信息融合,采用自适应滤波控制方法实现对通信节点挖掘的干扰抑制。仿真结果表明,采用该方法进行通信节点挖掘,信标定位准确,信号的覆盖度较合理,实现了信道空间的合理高效利用,实现了信道均衡和干扰抑制,有效降低了通信的误比特率。     

节点非独立失效下的局域网可靠性建模与分析

以具有层次结构的局域网作为拓扑模型,考虑共因失效和关联失效这2类节点非独立失效事件发生的情况,建立了交换机节点失效模型来模拟交换机失效,利用Monte-Carlo仿真算法近似计算出网络的两端可靠性,研究2种共因失效事件和3种关联失效事件对网络端端可靠性的影响。结果表明:因资源节点出现故障和协议层出现错误而导致交换机失效的共因失效事件均会降低网络可靠性,且资源节点失效概率或协议层失效概率越大,网络可靠性越低;而由于使用了热备份技术、堆叠技术以及发生广播风暴导致的关联失效事件,即使节点独立失效概率很小,只要相关因数足够大,故障都会快速传播,导致网络可靠性迅速下降。     

基于节点映射的武器装备需求生成方法

针对目前武器装备需求分析过程中,作战任务域向装备功能域映射方法可操作性不强的问题,研究了基于＂作战节点＂向＂系统节点＂映射的武器装备需求分析方法。该方法通过分析确定作战节点和系统节点,完成作战节点向系统节点映射、作战节点连接线向系统接口映射,最终得到装备系统需要的功能子系统及功能,较好地解决了需求映射过程中的随意性问题。     

基于PageRank算法的武器装备体系重要节点评估

将武器装备系统抽象为网络节点,利用复杂网络理论研究评估武器装备体系中的重要节点。针对传统PageRank算法在该应用中存在的问题,提出一种修正的PageRank算法。该算法对悬挂节点及有向环状网络节点的重要度评估具备收敛性。仿真实例验证了该修正算法对双目标作战环节点重要度评估的有效性。为了进一步验证所提算法的准确性,引入特征谱理论和移除节点法评估网络的抗毁性。     

Single‐commodity stochastic network design under demand and topological uncertainties with insufficient data

Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown distributions given limited data. In this article, we design arcs in a network to optimize the cost of single‐commodity flows under random demand and arc disruptions. We minimize the network design cost plus cost associated with network performance under uncertainty evaluated by two schemes. The first scheme restricts demand and arc capacities in budgeted uncertainty sets and minimizes the worst‐case cost of supply generation and network flows for any possible realizations. The second scheme generates a finite set of samples from statistical information (e.g., moments) of data and minimizes the expected cost of supplies and flows, for which we bound the worst‐case cost using budgeted uncertainty sets. We develop cutting‐plane algorithms for solving the mixed‐integer nonlinear programming reformulations of the problem under the two schemes. We compare the computational efficacy of different approaches and analyze the results by testing diverse instances of random and real‐world networks. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 154–173, 2017     

基于遗传算法的通信网络可靠性优化设计

在可靠性条件约束下 ,使网络成本最低是网络规划NP hard问题 .文章提出一种基于遗传算法的优化方法解决了这类问题 .仿真结果表明这种算法是有效的 .     

基于感知信息共享的C2网络特征分析

指挥控制（C2，Commandand Control）关系网络连接数的增加会增强指控节点之间的信息共享，但也会增加节点信息处理和交换负荷，如果达到一定程度，则会造成节点本身的“信息过载”从而影响C2网络性能。对此，通过研究C2网络在两种不同处理方式下的共享感知信息平均提交时间，用网络节点响应时间的均方差表征一个C2网络的共享态势感知时间的一致性，最后对两种不同结构C2网络特征参数的计算，说明了网络连接增加会导致信息提交时间的延长，但一致性会增强。     

航空加权网络抗毁性综合评估方法

根据目前网络抗毁性研究中指标单一、网络无权等不足,针对航空网络的特点,以流量为边权,提出了一种多指标的航空网络抗毁性评估方法。基于网络吞吐量、相似权网络流量、节点相邻边权重分布分别构建了鲁棒性度量、网络效率度量、网络适应性度量。最后通过建立西北地区航空网络进行仿真,结果表明:西北地区航空网络具有与星型网络相似的性能,鲁棒性较差,网络效率较好,咸阳和乌鲁木齐作为中心节点,具有较好的主抗性能。实验结果证明了该评估方法的有效性。     

基于复杂网络的联合作战指挥体系研究

以作战指挥理论需求为牵引,从复杂网络的角度对联合作战指挥体系问题进行网络抽象,将指挥体系中的指挥机构作为网络的节点,将指挥关系作为网络的边,按照指挥体系历史发展的规律,从简单到复杂,分别构建了传统层级纵长树状型的指挥体系网络模型,在树状模型基础上,增加了横向联系但依然具有层级结构的信息共享改进型的指挥体系网络模型,以及...     

Chance‐constrained multi‐terminal network design problems

We consider a reliable network design problem under uncertain edge failures. Our goal is to select a minimum‐cost subset of edges in the network to connect multiple terminals together with high probability. This problem can be seen as a stochastic variant of the Steiner tree problem. We propose two scenario‐based Steiner cut formulations, study the strength of the proposed valid inequalities, and develop a branch‐and‐cut solution method. We also propose an LP‐based separation for the scenario‐based directed Steiner cut inequalities using Benders feasibility cuts, leveraging the success of the directed Steiner cuts for the deterministic Steiner tree problem. In our computational study, we test our branch‐and‐cut method on instances adapted from graphs in SteinLib Testdata Library with up to 100 nodes, 200 edges, and 17 terminals. The performance of our branch‐and‐cut method demonstrates the strength of the scenario‐based formulations and the benefit from adding the additional valid inequalities that we propose. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 321–334, 2015