On the characterization of Aloha in underwater wireless networks

Standard analyses of wireless random access protocols that are available in the literature assume negligible propagation delay between any two nodes. This assumption holds good in reasonably short-range terrestrial RF (radio frequency) wireless networks. On the contrary, in wireless communications involving acoustic wave propagation, as in underwater wireless networks, even short distance propagation has appreciably large propagation delay. This observation has led to several recent simulation and experimental studies on underwater Aloha and slotted-Aloha (S-Aloha) protocols and also a few new proposals on random access protocols for underwater wireless ad hoc networks (UWN). To study the efficiency of more advanced multiaccess communication protocols for UWN, it is important to benchmark their performances with respect to the two basic random access protocols, Aloha and S-Aloha. This paper provides an analytic framework to capture the performance of Aloha and S-Aloha protocols in an underwater environment with high and random internodal signal propagation delay. The performance of underwater Aloha and S-Aloha are contrasted with those in short-range terrestrial RF wireless networks. The analysis shows that random internodal propagation delay has no effect on the underwater Aloha performance. It also sheds light on the throughput degradation of underwater S-Aloha with a slotting concept that achieves RF S-Aloha equivalent one-slot vulnerability. Additionally, a modified slotting concept is introduced where the slot size is judiciously reduced such that even by allowing some collisions the overall system throughput can be increased. Our calculations show that, with the modified slotting approach up to 17% throughput performance gain can be achieved over the naive (RF S-Aloha equivalent) slotting approach in UWN. Our analytic results are supported by discrete event simulations.     

Optimal policies for a delay time model with postponed replacement

We develop a delay time model (DTM) to determine the optimal maintenance policy under a novel assumption: postponed replacement. Delay time is defined as the time lapse from the occurrence of a defect up until failure. Inspections can be performed to monitor the system state at non-negligible cost. Most works in the literature assume that instantaneous replacement is enforced as soon as a defect is detected at an inspection. In contrast, we relax this assumption and allow replacement to be postponed for an additional time period. The key motivation is to achieve better utilization of the system’s useful life, and reduce replacement costs by providing a sufficient time window to prepare maintenance resources. We model the preventive replacement cost as a non-increasing function of the postponement interval. We then derive the optimal policy under the modified assumption for a system with exponentially distributed defect arrival time, both for a deterministic delay time and for a more general random delay time. For the settings with a deterministic delay time, we also establish an upper bound on the cost savings that can be attained. A numerical case study is presented to benchmark the benefits of our modified assumption against conventional instantaneous replacement discussed in the literature.     

On a Characteristic Initial Value Problem in Plasma Physics

The relativistic Vlasov-Maxwell system of plasma physics is considered with initial data on a past light cone. This characteristic initial value problem arises in a natural way as a mathematical framework to study the existence of solutions isolated from incoming radiation. Various consequences of the mass-energy conservation and of the absence of incoming radiation condition are first derived assuming the existence of global smooth solutions. In the spherically symmetric case, the existence of a unique classical solution in the future of the initial cone follows by arguments similar to the case of initial data at time t=0. The total mass-energy of spherically symmetric solutions equals the (properly defined) mass-energy on backward and forward light cones. Communicated by Sergiu Klainerman submitted 8/03/05, accepted 26/05/05     

Delay analysis of extended rtPS for VoIP service in IEEE 802.16e by matrix analytic method

Extended real time polling service (ErtPS) is added to IEEE 802.16e-2005 standards in order for VoIP service to use uplink resources efficiently by considering on/off characteristic of voice source. Recently average queueing delay of ErtPS algorithm for VoIP service was investigated, and it was shown that ErtPS allows to admit more users than UGS algorithm. But we need the probability distribution of queueing delay rather than average queueing delay in order to provide a necessary information for QoS. In this paper we obtain the probability distribution of queueing delay of ErtPS for VoIP service by using the matrix analytic method for the GI/M/1 type and the M/G/1 type matrices in cases of the service time being exponential and deterministic respectively. By applying the results on deterministic service time we find the maximum allowable number of VoIP users with the required constraint on queueing delay. This research was supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).     

Approximations for multi-server queues: System interpolations

This paper provides a unifying method of generating and/or evaluating approximations for the principal congestion measures in aGI/G/s queueing system. The main focus is on the mean waiting time, but approximations are also developed for the queue-length distribution, the waiting-time distribution and the delay probability for the Poisson arrival case. The approximations have closed forms that combine analytical solutions of simpler systems, and hence they are referred to as system-interpolation approximations or, simply, system interpolations. The method in this paper is consistent with and generalizes system interpolations previously presented for the mean waiting time in theGI/G/s queue.     

Spatiotemporal dynamics on small-world neuronal networks: The roles of two types of time-delayed coupling

We investigate temporal coherence and spatial synchronization on small-world networks consisting of noisy Terman–Wang (TW) excitable neurons in dependence on two types of time-delayed coupling: {x_j(t − τ) − x_i(t)} and {x_j(t − τ) − x_i(t − τ)}. For the former case, we show that time delay in the coupling can dramatically enhance temporal coherence and spatial synchrony of the noise-induced spike trains. In addition, if the delay time τ is tuned to nearly match the intrinsic spike period of the neuronal network, the system dynamics reaches a most ordered state, which is both periodic in time and nearly synchronized in space, demonstrating an interesting resonance phenomenon with delay. For the latter case, however, we cannot achieve a similar spatiotemporal ordered state, but the neuronal dynamics exhibits interesting synchronization transitions with time delay from zigzag fronts of excitations to dynamic clustering anti-phase synchronization (APS), and further to clustered chimera states which have spatially distributed anti-phase coherence separated by incoherence. Furthermore, we also show how these findings are influenced by the change of the noise intensity and the rewiring probability of the small-world networks. Finally, qualitative analysis is given to illustrate the numerical results.     

Scattering on Reissner-Nordstrøm Metric for Massive Charged Spin 1/2 Fields

We consider massive charged Dirac fields on the Reissner-Nordstrøm metric. We prove the existence and asymptotic completeness of wave operators, classical at horizon and modified at infinity. Communicated by Piotr Chrusciel submitted 24/05/02, accepted: 14/02/03     

On unit time open shops with additional restrictions

We consider open shop problems with unit processing times,n jobs have to be processed onm machines. The order in which a given job is processed on the machines is not fixed. For each job a release time or a due date may be given. Additional, we consider the restriction that every machine must perform all corresponding operations without any delay time. Unit time open shop problems with release times to minimize total completion time were unsolved up to now for both allowed and forbidden delay times. We will solve these problems in the case of two and three machines. Furthermore we will give polynomial algorithms for several no-delay-problems with due dates.     

Priority queues with semi-exhaustive service

This paper studies a new type of multi-class priority queues with semi-exhaustive service and server vacations, which operates as follows: A single server continues serving messages in queuen until the number of messages decreases toone less than that found upon the server's last arrival at queuen, where 1nN. In succession, messages of the highest class present in the system, if any, will be served according to this semi-exhaustive service. Applying the delay cycle analysis and introducing a super-message composed of messages served in a busy period, we derive explicitly the Laplace-Stieltjes transforms (LSTs) and the first two moments of the message waiting time distributions for each class in the M/G/1-type priority queues with multiple and single vacations. We also derive a conversion relationship between the LSTs for waiting times in the multiple and single vacation models.     

Analysis of queueing policies in QoS switches

It is widely accepted that next-generation networks will provide guaranteed services, in contrast to the “best effort” approach today. We study and analyze queueing policies for network switches that support the QoS (Quality of Service) feature. One realization of the QoS feature is that packets are not necessarily all equal, with some having higher priorities than the others. We model this situation by assigning an intrinsic value to each packet. In this paper we are concerned with three different queueing policies: the nonpreemptive model, the FIFO preemptive model, and the bounded delay model. We concentrate on the situation where the incoming traffic overloads the queue, resulting in packet loss. The objective is to maximize the total value of packets transmitted by the queueing policy. The difficulty lies in the unpredictable nature of the future packet arrivals. We analyze the performance of the online queueing policies via competitive analysis, providing upper and lower bounds for the competitive ratios. We develop practical yet sophisticated online algorithms (queueing policies) for the three queueing models. The algorithms in many cases have provably optimal worst-case bounds. For the nonpreemptive model, we devise an optimal online algorithm for the common 2-value model. We provide a tight logarithmic bound for the general nonpreemptive model. For the FIFO preemptive model, we improve the general lower bound to 1.414, while showing a tight bound of 1.434 for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also show an improved lower bound of 1.618 for the 2-variable bounded delay model, matching the previously known upper bound.     

New bounds for expected delay in FIFO M/G/c queues

Most bounds for expected delay, E[D], in GI/GI/c queues are modifications of bounds for the GI/GI/1 case. In this paper we exploit a new delay recursion for the GI/GI/c queue to produce bounds of a different sort when the traffic intensity p = λ/μ = E[S]/E[T] is less than the integer portion of the number of servers divided by two. (S AND T denote generic service and interarrival times, respectively.) We derive two different families of new bounds for expected delay, both in terms of moments of S AND T. Our first bound is applicable when E[S₂] < ∞. Our second bound for the first time does not require finite variance of S; it only involves terms of the form E[S^β], where 1 < β < 2. We conclude by comparing our bounds to the best known bound of this type, as well as values obtained from simulation. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Feynman-Kac type formula for a fixed delay CIR model

Stochastic delay differential equations (SDDE’s) have been used for financial modeling. In this article, we study a SDDE obtained by the equation of a CIR process, with an additional fixed delay term in drift; in particular, we prove that there exists a unique strong solution (positive and integrable) which we call fixed delay CIR process. Moreover, for the fixed delay CIR process, we derive a Feynman-Kac type formula, leading to a generalized exponential-affine formula, which is used to determine a bond pricing formula when the interest rate follows the delay’s equation. It turns out that, for each maturity time T, the instantaneous forward rate is an affine function (with time dependent coefficients) of the rate process and of an auxiliary process (also depending on T). The coefficients satisfy a system of deterministic differential equations.     

A Study on the Propagation of Plane Stress Waves across the Thickness of a Plate by the Method of Analytic Continuation in Time

The interaction of plane tension/compression waves propagating within a plate perpendicularly to its surface is considered. The analytic solution is obtained by a modified method of characteristics for the one-dimensional wave equation used in problems on an impact of a rigid body on the surface of a plate. The displacements, velocities, and stresses in the plate are determined by the edge disturbance caused by the initial velocity and the stationary force field of masses of the striker and the plate. The method of analytic continuation in time put forward allows a stress analysis for an arbitrary time interval by using finite expressions. Contrary to a stress analysis in the frequency domain, which is commonly used in harmonic expansion of disturbances, the approach advanced allows one to analyze the solution in the case of discontinuous first derivatives of displacements without calculating jumps in summing series. A generalized closed-form solution is obtained for stresses in an arbitrary cycle n(t), which is determined by the multiplicity of the time of wave travel across the double thickness of the plate. A method of recurrent solution based on calculating the convolution of repeated integrals of the initial form of disturbance at t = 0 is elaborated. The procedure can be used for evaluating the maximum stress and the contact time in a plane impact on the surface of a plate.     

Rejection rules in theM/G/1 queue

We consider aM/G/1 queue modified such that an arriving customer may be totally or partially rejected depending on a r.v. (the barricade) describing his impatience and on the state of the system. Three main variants of this scheme are studied. The steady-state distribution is expressed in terms of Volterra equations and the relation to storage processes, dams and queues with state-dependent Poisson arrival rate is discussed. For exponential service times, we further find the busy period Laplace transform in the case of a deterministic barricade, whereas for exponential barricade it is shown by a coupling argument that the busy period can be identified with a first passage time in an associated birth-death process.     

On the explosive instability in a three‐species food chain model with modified Holling type IV functional response

In earlier literature, a version of a classical three‐species food chain model, with modified Holling type IV functional response, is proposed. Results on the global boundedness of solutions to the model system under certain parametric restrictions are derived, and chaotic dynamics is shown. We prove that in fact the model possesses explosive instability, and solutions can explode/blow up in finite time, for certain initial conditions, even under the parametric restrictions of the literature. Furthermore, we derive the Hopf bifurcation criterion, route to chaos, and Turing bifurcation in case of the spatially explicit model. Lastly, we propose, analyze, and simulate a version of the model, incorporating gestation effect, via an appropriate time delay. The delayed model is shown to possess globally bounded solutions, for any initial condition. Copyright © 2017 John Wiley & Sons, Ltd.     

Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems

Lagrangian relaxation is a powerful bounding technique that has been applied successfully to manyNP-hard combinatorial optimization problems. The basic idea is to see anNP-hard problem as an easy-to-solve problem complicated by a number of nasty side constraints. We show that reformulating nasty inequality constraints as equalities by using slack variables leads to stronger lower bounds. The trick is widely applicable, but we focus on a broad class of machine scheduling problems for which it is particularly useful. We provide promising computational results for three problems belonging to this class for which Lagrangian bounds have appeared in the literature: the single-machine problem of minimizing total weighted completion time subject to precedence constraints, the two-machine flow-shop problem of minimizing total completion time, and the single-machine problem of minimizing total weighted tardiness.     

On the Queue Length Distribution for the GI/G/1/K/VM Queue

Abstract

We present a transform-free distribution of the steady-state queue length for the GI/G/1/K queueing system with multiple vacations under exhaustive FIFO service discipline. The method we use is a modified supplementary variable technique and the result we obtain is expressed in terms of conditional expectations of the remaining service time, the remaining interarrival time, and the remaining vacation, conditional on the queue length at the embedded points. The case K → ∞ is also considered.     

On the T 3-Gowdy Symmetric Einstein-Maxwell Equations

Recently, progress has been made in the analysis of the expanding direction of Gowdy spacetimes. The purpose of the present paper is to point out that some of the techniques used in the analysis can be applied to other problems. The essential equations in the case of the Gowdy spacetimes can be considered as a special case of a wider class of variational problems. Here we are interested in the asymptotic behaviour of solutions to this class of equations. Two particular members arise when considering the T³-Gowdy symmetric Einstein-Maxwell equations and when considering T³-Gowdy symmetric IIB superstring cosmology. The main result concerns the rate of decay of a naturally defined energy. A subclass of the variational problems can be interpreted as wave map equations, and in that case one gets the following picture. The non-linear wave equations one ends up with have as a domain the positive real line in Cartesian product with the circle. For each point in time, the wave map can thus be seen as a loop in some Riemannian manifold. As a consequence of the decay of the energy mentioned above, the length of the loop converges to zero at a specific rate. Communicated by Sergiu Klainerman submitted 14/02/05, accepted 21/04/05