Sensor placement in active multistatic sonar networks

The idea of deploying noncollocated sources and receivers in multistatic sonar networks (MSNs) has emerged as a promising area of opportunity in sonar systems. This article is one of the first to address point coverage problems in MSNs, where a number of points of interest have to be monitored in order to protect them from hostile underwater assets. We consider discrete “definite range” sensors as well as various diffuse sensor models. We make several new contributions. By showing that the convex hull spanned by the targets is guaranteed to contain optimal sensor positions, we are able to limit the solution space. Under a definite range sensor model, we are able to exclude even more suboptimal solutions. We then formulate a nonlinear program and an integer nonlinear program to express the sensor placement problem. To address the nonconvex single‐source placement problem, we develop the Divide Best Sector (DiBS) algorithm, which quickly provides an optimal source position assuming fixed receivers. Starting with a basic implementation of DiBS, we show how incorporating advanced sector splitting methods and termination conditions further improve the algorithm. We also discuss two ways to use DiBS to find multiple source positions by placing sensors iteratively or simultaneously. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 287–304, 2017     

双(多)基地声纳浮标系统在反潜中的应用研究

在双基地声纳系统中,根据能量关系推导出双基地声纳系统最大可探测范围的数学模型;在此基础上,讨论了用双(多)基地声纳浮标系统布放直线阵、圆形阵时的阵形宽度、搜索面积及所需浮标数,并将之与传统被动浮标阵进行了比较.结果表明:采用双(多)基地浮标阵可以在一定程度上节省浮标数,提高了浮标的使用效率.     

利用会聚区隐蔽解算目标运动要素的方法

在浅海,当被动声纳探测到目标后,由于舰艇间不断的运动,测得的目标方位随时间的不同而不断地发生变化,利用目标方位的变化,通过纯方位法和滤波估计等方法可解算出目标的运动要素.当声纳利用深海会聚区的声学效应在远距离上探测到目标时,因舰艇被动声纳在隐蔽条件下往往只能测得目标的方位,此时的目标方位随着时间的不同变化很小,难以利用浅海的解算方法求出目标的运动要素.为解决这一问题,基于对深海会聚区声学效应的分析,提出了利用会聚区宽度等特点,采用本舰艇合理机动的方式,来求解目标的运动要素的方法.通过对本舰艇各种可能机动方式的建模和计算机仿真计算的结果可见,该方法可行,且在第一、第二会聚区效果明显.     

基于匹配处理的纯方位目标运动分析方法

以被动声纳观测的目标方位信息为基础,将匹配处理技术用到目标运动参数纯方位估计中,建立了进行纯方位目标运动分析的匹配处理模型,给出相关的优化处理算法,并通过仿真计算验证了模型的有效性。仿真结果表明该算法在目标运动参数的收敛时间和距离等指标上有较明显改善。     

A multi‐stage stochastic programming approach for network capacity expansion with multiple sources of capacity

In networks, there are often more than one sources of capacity. The capacities can be permanently or temporarily owned by the decision maker. Depending on the nature of sources, we identify the permanent capacity, spot market capacity, and contract capacity. We use a scenario tree to model the uncertainty, and build a multi‐stage stochastic integer program that can incorporate multiple sources and multiple types of capacities in a general network. We propose two solution methodologies for the problem. Firstly, we design an asymptotically convergent approximation algorithm. Secondly, we design a cutting plane algorithm based on Benders decomposition to find tight bounds for the problem. The numerical experiments show superb performance of the proposed algorithms compared with commercial software. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 600–614, 2017     

Probabilistic partial set covering problems

In this article, we consider a situation in which a group of facilities need to be constructed in order to serve a given set of customers. However, the facilities cannot guarantee an absolute coverage to any of the customers. Hence, we formulate this problem as one of maximizing the total service reliability of the system subject to a budgetary constraint. For this problem, we develop and test suitable branch-and-bound algorithms and study the effect of problem parameters on solution difficulty. Some generalizations of this problem are also mentioned as possible extensions.     

利用多基地雷达实现目标的无源定位

对利用多基地雷达实现目标的无源定位功能所涉及到的系统关键技术进行了研究。如针对多基地雷达不同的系统结构提出了相应的无源定位方法和时间同步方案,并对接收机的一体化设计和脉冲分选方法做了简要论述。     

The traveling salesman problem: An update of research

During the course of the last few years, attacks on the traveling salesman problem have resulted in a variety of often innovative and rather powerful computational procedures. In this article, we present a review of these results for problems defined on weighted and unweighted graphs. Some account of computational behavior for exact algorithms is provided; however, the primary coverage deals with the strategy of particular procedures. In addition, we include some aspects of nonexact algorithms with major interest confined to the establishment of worst-case bounds.     

基于线性数据融合的双椭圆定位模型优化算法

为了充分利用分离式台声源声纳定位系统的冗余测量信息,提高系统的定位精度,提出了基于线性数据融合的双椭圆定位模型优化算法。并通过数值仿真,对不同条件下的定位误差几何分布曲线图(GDOP)进行了研究。仿真结果表明,大部分探测范围内,两个声源之间距离的变化和时间测量误差对定位性能影响较小,而角度测量误差对该算法的定位精度影响较大。与仅利用距离信息进行定位的方法相比较,采用数据融合的优化手段,可以充分利用定位系统的冗余信息,有效地降低了系统的定位误差,探测盲区的定位性能也得到明显改善。仿真结果和性能分析为解决远距离探潜定位优化问题提供了理论依据。     

Worst‐case performance of approximation algorithms for tool management problems

Since the introduction of flexible manufacturing systems, researchers have investigated various planning and scheduling problems faced by the users of such systems. Several of these problems are not encountered in more classical production settings, and so‐called tool management problems appear to be among the more fundamental ones of these problems. Most tool management problems are hard to solve, so that numerous approximate solution techniques have been proposed to tackle them. In this paper, we investigate the quality of such algorithms by means of worst‐case analysis. We consider several polynomial‐time approximation algorithms described in the literature, and we show that all these algorithms exhibit rather poor worst‐case behavior. We also study the complexity of solving tool management problems approximately. In this respect, we investigate the interrelationships among tool management problems, as well as their relationships with other well‐known combinatorial problems such as the maximum clique problem or the set covering problem, and we prove several negative results on the approximability of various tool management problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 445–462, 1999     

Optimal sensor placement for underwater threat detection

The optimization framework for optimal sensor placement for underwater threat detection has been developed. It considers single‐period and multiperiod detection models, each of which includes two components: detection algorithm and optimization problem for sensor placement. The detection algorithms for single‐period and multiperiod models are based on likelihood ratio and sequential testing, respectively. For the both models, the optimization problems use the principle of superadditive coverage, which is closely related to energy‐based and information‐based approaches. An algorithm for quasi‐regular sensor placement approximating solutions to the optimization problems has been developed based on corresponding continuous relaxations and a criterion for its applicability has been obtained. Numerical experiments have demonstrated that the algorithm consistently outperforms existing optimization techniques for optimal sensor placement.© 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Decomposition-based approximation algorithms for the one-warehouse multi-retailer problem with concave batch order costs

We study the one-warehouse multi-retailer problem under deterministic dynamic demand and concave batch order costs, where order batches have an identical capacity and the order cost function for each facility is concave within the batch. Under appropriate assumptions on holding cost structure, we obtain lower bounds via a decomposition that splits the two-echelon problem into single-facility subproblems, then propose approximation algorithms by judiciously recombining the subproblem solutions. For piecewise linear concave batch order costs with a constant number of slopes we obtain a constant-factor approximation, while for general concave batch costs we propose an approximation within a logarithmic factor of optimality. We also extend some results to subadditive order and/or holding costs.     

潜艇规避被动声纳浮标阵方法及期望驶离时间

基于对反潜巡逻机布放被动声纳浮标阵的研究,对方形阵的布放建立了模型。利用该模型研究了我潜艇规避被动浮标声纳阵的方法。通过计算,得出潜艇驶离被动声纳浮标阵搜索范围的期望时间,用选取的声纳浮标阵间距和潜艇规避速度对结果进行分析,为潜艇的下一步行动提供辅助决策。     

On efficient algorithms for finding efficient salvo policies

We consider the salvo policy problem, in which there are k moments, called salvos, at which we can fire multiple missiles simultaneously at an incoming object. Each salvo is characterized by a probability p_i: the hit probability of a single missile. After each salvo, we can assess whether the incoming object is still active. If it is, we fire the missiles assigned to the next salvo. In the salvo policy problem, the goal is to assign at most n missiles to salvos in order to minimize the expected number of missiles used. We consider three problem versions. In Gould's version, we have to assign all n missiles to salvos. In the Big Bomb version, a cost of B is incurred when all salvo's are unsuccessful. Finally, we consider the Quota version in which the kill probability should exceed some quota Q. We discuss the computational complexity and the approximability of these problem versions. In particular, we show that Gould's version and the Big Bomb version admit pseudopolynomial time exact algorithms and fully polynomial time approximation schemes. We also present an iterative approximation algorithm for the Quota version, and show that a related problem is NP-complete.     

Pricing bridges to cross a river

We consider a pricing problem in directed, uncapacitated networks. Tariffs must be defined by an operator, the leader, for a subset of m arcs, the tariff arcs. Costs of all other arcs in the network are assumed to be given. There are n clients, the followers, and after the tariffs have been determined, the clients route their demands independent of each other on paths with minimal total cost. The problem is to find tariffs that maximize the operator's revenue. Motivated by applications in telecommunication networks, we consider a restricted version of this problem, assuming that each client utilizes at most one of the operator's tariff arcs. The problem is equivalent to pricing bridges that clients can use in order to cross a river. We prove that this problem is APX‐hard. Moreover, we analyze the effect of uniform pricing, proving that it yields both an m approximation and a (1 + lnD)‐approximation. Here, D is upper bounded by the total demand of all clients. In addition, we consider the problem under the additional restriction that the operator must not reject any of the clients. We prove that this problem does not admit approximation algorithms with any reasonable performance guarantee, unless P = NP, and we prove the existence of an n‐approximation algorithm. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

舰艇编队对潜水声警戒主/被动探测转换区的决策指挥

从大型舰艇编队反潜战术及水声装备作战使用的角度出发,提出了水声警戒主/被动转换区的概念,分析了各种影响因素及其相互关系,研究了水声警戒主/被动转换区的计算方法,建立了转换区的数学模型,得出了多潜艇突防编队警戒幕的概率和水面舰艇编队的对潜警戒探测能力,提出了水声警戒主/被动转换区决策与指挥的方法。     

多重优化的分布式无线覆盖探测算法

为满足无线通信网络信号覆盖有效性的实时实地可重复探测的需求,提出一种基于传感器网络的分布式无线覆盖探测算法。通过随机部署于目标区域内的无线传感器节点对无线通信网接收信号强度进行感知和预处理;利用变异函数构造新的BP神经网络目标函数,通过改进粒子群算法优化其初始权值和阈值;利用训练好的网络模型对存在探测盲区的目标区域进行插值估计,并联合传感器节点采集到的数据生成无线通信网络等信号强度线。仿真结果表明,所提算法比其他经典算法具有更高的精度,可有效探测目标区域无线通信网络的信号覆盖情况。     

A robust sensor covering and communication problem

We consider the problem of placing sensors across some area of interest. The sensors must be placed so that they cover a fixed set of targets in the region, and should be deployed in a manner that allows sensors to communicate with one another. In particular, there exists a measure of communication effectiveness for each sensor pair, which is determined by a concave function of distance between the sensors. Complicating the sensor location problem are uncertainties related to sensor placement, for example, as caused by drifting due to air or water currents to which the sensors may be subjected. Our problem thus seeks to maximize a metric regarding intrasensor communication effectiveness, subject to the condition that all targets must be covered by some sensor, where sensor drift occurs according to a robust (worst‐case) mechanism. We formulate an approximation approach and develop a cutting‐plane algorithm to solve this problem, comparing the effectiveness of two different classes of inequalities. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 582–594, 2015     

被动传感器融合检测系统的优化分布密度

被动传感器由于采用无源探测,而且制造成本低,体积小,在战场环境中将采用并配置大量的被动传感器来检测目标.不论是主动还是被动式传感器,在实际应用中均存在资源优化配置问题.针对被动传感器的具体应用模型,采取了若干合理近似,得到了在"OR"融合检测条件下,基于最大检测概率的被动传感器优化配置密度计算公式.     

Solving partially observable agent‐intruder games with an application to border security problems

In this paper, we introduce partially observable agent‐intruder games (POAIGs). These games model dynamic search games on graphs between security forces (an agent) and an intruder given possible (border) entry points and high value assets that require protection. The agent faces situations with dynamically changing, partially observable information about the state of the intruder and vice versa. The agent may place sensors at selected locations, while the intruder may recruit partners to observe the agent's movement. We formulate the problem as a two‐person zero‐sum game, and develop efficient algorithms to compute each player's optimal strategy. The solution to the game will help the agent choose sensor locations and design patrol routes that can handle imperfect information. First, we prove the existence of ?‐optimal strategies for POAIGs with an infinite time horizon. Second, we introduce a Bayesian approximation algorithm to identify these ?‐optimal strategies using belief functions that incorporate the imperfect information that becomes available during the game. For the solutions of large POAIGs with a finite time horizon, we use a solution method common to extensive form games, namely, the sequence form representation. To illustrate the POAIGs, we present several examples and numerical results.