Search

This paper studies the localization problem using noisy range-difference measurements, or equivalently time difference of arrival (TDOA) measurements. There is a reference sensor, and for each other sensor, the TDOA measurement is obtained with respect to the reference one. By minimizing the sum of squared errors, a nonconvex constrained least squares (CLS) problem is formulated. In this work, we focus on devising an algorithm to seek the global minimizer of the CLS problem, hoping that the numerical solution meets some precision requirement in terms of relative error. Based on the Lagrange multiplier method, we first branch the feasible Lagrange multiplier set into several subsets and develop a workflow in terms of if-then-else control structure to seek the global minimizer by searching for the optimal Lagrange multiplier. The execution order is carefully organized so that it is in line with the general principle of putting the flow that one normally understands to be executed first. We then dive into detailed searching methods in different cases and conduct computational error analysis, giving the error bound on the Lagrange multiplier, when we search for it, to meet the precision requirement on an approximate solution. Based on the above achievements, a programmable global minimizer seeking algorithm is proposed for the CLS problem. Simulations and experimental tests on a public dataset demonstrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper investigates the platoon control problem for vehicular cyber physical systems (VCPSs) under Denial-of-Service (DoS) attacks and multiple disturbances. DoS attacks often make data packets congested or even lost by jamming communication channels, which will lead to performance degradation of the VCPSs or even vehicle collisions. To counter DoS attacks, a recovery mechanism is introduced to confine the time duration rate and occurring frequency of the adverse effects of the DoS attacks on VCPSs. In the meanwhile, a resilient platoon control protocol is proposed to achieve internal stability of the VCPSs under DoS attacks. The propagation of disturbances among VCPSs is characterized by an $H_{\infty }$ performance index, whose upper bound is ensured by solving conditions related to matrix inequalities. Moreover, a controller design algorithm is proposed to minimize the disturbance propagation bound in the context of DoS attacks. Numerical examples show the effectiveness of the obtained theoretical results. [ABSTRACT FROM AUTHOR]

In this article, we propose a learning approach to analyze dynamic systems with an asymmetric information structure. Instead of adopting a game-theoretic setting, we investigate an online quadratic optimization problem driven by system noises with unknown statistics. Due to information asymmetry, it is infeasible to use the classic Kalman filter nor optimal control strategies for such systems. It is necessary and beneficial to develop an admissible approach that learns the probability statistics as time goes forward. Motivated by the online convex optimization (OCO) theory, we introduce the notion of regret, which is defined as the cumulative performance loss difference between the optimal offline-known statistics cost and the optimal online-unknown statistics cost. By utilizing dynamic programming and linear minimum mean square biased estimate (LMMSUE), we propose a new type of online state-feedback control policy and characterize the behavior of regret in a finite-time regime. The regret is shown to be sublinear and bounded by $O(\ln T)$. Moreover, we address an online optimization problem with output-feedback control policy and propose a heuristic online control policy. [ABSTRACT FROM AUTHOR]

Conflict-avoiding codes (CACs) were introduced by Levenshtein as a single-channel transmission scheme for a multiple-access collision channel without feedback. When the number of simultaneously active source nodes is less than or equal to the weight of a CAC, it is able to provide a hard guarantee that each active source node transmits at least one packet successfully within a fixed time duration, no matter what the relative time offsets between the source nodes are. In this article, we extend CACs to multichannel CACs for providing such a hard guarantee over multiple orthogonal channels. Upper bounds on the number of codewords for multichannel CACs of weights three and four are derived, and constructions that are optimal with respect to these bounds are presented. [ABSTRACT FROM AUTHOR]

The collision channel without feedback (CCw/oFB) introduced by Massey and Mathys, depicts a scenario where multiple users share a communication channel but have arbitrary time offsets, and can never learn these time offsets due to the lack of feedback. This paper considers an extension of the CCw/oFB, which allows the receiver to use successive interference cancellation (SIC) to cancel the interference caused by those collided packets whose contents have been known by the receiver. We derive the zero-packet-loss throughput regions of this model for both the unsynchronized and slot-synchronized cases. Given an arbitrary number of users and a packet alphabet of arbitrary size, it is shown that these two regions coincide, and the outer boundary of this common region is the set of all points with only nonnegative components that add up to one. It is further shown that all points on this outer boundary with only rational components can be achieved without packet loss in the slot-synchronized case. The constructive proofs are based on a joint design of protocol sequences, identification/location algorithm and erasure correcting codes. These findings indicate that the negative impact of the lack of time synchronization on the throughput performance can be removed by the help of SIC. [ABSTRACT FROM AUTHOR]

We consider a single-hop wireless sensor network in which each sensor node has an individual elastic data stream to transmit to each other node. We refer to this traffic pattern as unicast in this paper. The network has multiple slotted channels available for the data transmissions. To guarantee successful unicast within a bounded delay, we consider deterministic schemes that pre-assign each node a periodic schedule sequence to schedule transmitting and receiving at each time slot. The sequence period should be minimized since it upper bounds the unicast delay. We have investigated both synchronous TDMA sequences and asynchronous sequences. Since accurate time synchronization is difficult to achieve in sensor networks, we mainly present analysis and design for asynchronous sequences. In this paper, for a group-based channel assignment, we present a lower bound on the common period and propose a sequence construction method by which the period can achieve the same order as the lower bound. We also analyze optimal transmitting and receiving probabilities for two random schemes and compare their frequency utilization efficiency. Finally, unicast delay and energy consumption performance are compared by simulations. [ABSTRACT FROM AUTHOR]

This paper considers a multiple-access system with multiple-packet reception (MPR) capability $\gamma $ , i.e., a packet can be successfully received as long as it overlaps with $\gamma -1$ or fewer other packets at any instant during its lifetime. To efficiently utilize the MPR capability, this paper generalizes $p$ -persistent carrier-sense multiple access (CSMA) to consider that a user with carrier sensing capability $c$ adopts the transmission probability $p_{n}$ if this user has sensed $n$ ongoing transmissions for $n=0,1,\ldots ,c-1$. This paper aims to model the characteristics of such CSMA and to design transmission probabilities for achieving maximum saturation throughput. To this end, we first formulate such CSMA as a parameterized Markov decision process (MDP) and use the long-run average performance to evaluate the saturation throughput. Second, by observing that the exact values of optimal transmission probabilities are in general infeasible to find, we modify this MDP to establish an upper bound on the maximum throughput, and modify this MDP again to propose a heuristic design with near-optimal performance. Simulations with respect to a wide range of configurations are provided to validate our study. The throughput performance under more general models and the robustness of our design are also investigated. [ABSTRACT FROM AUTHOR]

The fat-tree networking topology have gained prominence in various parallel and distributed systems such as high-performance computing clusters and data centers. To support high throughput and low latency applications, effective load-balancing schemes are in great demand. However, the commonly deployed scheme, equal-cost multipath, suffers from severe hash collisions that lead to poor performance. Recently, another realization of randomized load balancing, DRILL, has been proposed, which adopts the two-choice algorithm to achieve in-network local-to-switch load balancing. Although DRILL can well balance uplink traffic, it shows some limitations on alleviating downlink contentions. Motivated by this observation, we propose a thresholded two-choice (TTC) scheme, which modifies the two-choice algorithm such that it can balance both uplink and downlink traffic. To balance downlink traffic, TTC sets a default path for every source-destination pair using the D-mod-k scheme. The rationale for this is that D-mod-k minimizes the level of path collision over downlinks for any permutation in a fat-tree network. To balance uplink traffic, TTC makes dynamic path decisions using an algorithm that is based on the two-choice idea. To better leverage default paths in downlink load balancing, it is desirable that TTC routes the majority of traffic onto the default paths. To this end, we introduce a new thresholding mechanism to the two-choice algorithm, which contributes to a better overall performance. Our analysis shows that the introduced thresholding mechanism does not significantly affect the uplink load balancing performance. Moreover, our numerical study indicates that TTC can achieve a better system-wide performance than DRILL. [ABSTRACT FROM AUTHOR]

In this paper, we study the delay-constrained input-queued switch, where each packet has a deadline and it will expire if it is not delivered before its deadline. Such new scenario is motivated by the proliferation of real-time applications in multimedia communication systems, tactile Internet, networked controlled systems, and cyber-physical systems. The delay-constrained input-queued switch is completely different from the well-understood delay-unconstrained one and thus poses new challenges. We focus on three fundamental problems centering around the performance metric oftimely throughput: (i) how to characterize the capacity region? (ii) how to design a feasibility/throughput-optimal scheduling policy? and (iii) how to design a network-utility-maximization scheduling policy? We use three different approaches to solve these three fundamental problems. The first approach is based on Markov Decision Process (MDP) theory, which can solve all three problems. However, it suffers from the curse of dimensionality. The second approach breaks the curse of dimensionality by exploiting the combinatorial features of the problem. It gives a new capacity region characterization with only a polynomial number of linear constraints. The third approach is based on the framework of Lyapunov optimization, where we design a polynomial-time maximum-weight $T$ -disjoint-matching scheduling policy which is proved to be feasibility/throughput-optimal. Our three approaches apply to the frame-synchronized traffic pattern but our MDP-based approach can be extended to more general traffic patterns. [ABSTRACT FROM AUTHOR]

In this paper, a delay-dependent algebraic Riccati equation (DARE) approach is developed to study the mean-square stabilization problem for continuous-time networked control systems. Different from most previous studies that information transmission can be performed with zero delay and infinite precision, this paper presents a basic constraint that the designed control signal is transmitted over a delayed communication channel, where signal attenuation and transmission delay occur simultaneously. The innovative contributions of this paper are threefold. First, we propose a necessary and sufficient stabilizing condition in terms of a unique positive definite solution to a DARE with ${Q>0}$ and ${R>0}$. In accordance with this result, we derive the Lyapunov/spectrum stabilizing criterion. Second, we apply the operator spectrum theory to study the stabilizing solution to a more general DARE with ${Q\geq 0}$ and ${R>0}$. By defining a delay-dependent Lyapunov operator, we propose the existence theorem of the unique stabilizing solution. It is shown that the stabilizing solution, if it exists, is unique and coincides with a maximal solution. Third, as an application, we derive the explicit maximal allowable delay bound for a scalar system. To confirm the validity of our theoretic results, two illustrative examples are included in this paper. [ABSTRACT FROM AUTHOR]

Data centers play an important role in today’s Internet development. Research to find scalable architecture and efficient routing algorithms for data center networks has gained popularity. The fat-tree architecture, which is essentially a folded version of a Clos network, has proved to be readily implementable and is scalable. In this paper, we investigate routing on a fat-tree network by deriving its global packing number and by presenting explicit algorithms for the construction of optimal, load-balanced routing solutions. Consider an optical network that employs wavelength division multiplexing in which every user node sets up a connection with every other user node. The global packing number is basically the number of wavelengths required by the network to support such a traffic load, under the restriction that each source-to-destination connection is assigned a wavelength that remains constant in the network. In mathematical terms, consider a bidirectional, simple graph, G and let N\subseteq V(G) be a set of nodes. A path system \mathcal P of G with respect to N consists of |N|(|N|-1) directed paths, one path to connect each of the source-destination node pairs in N . The global packing number of a path system , denoted by \Phi (G,N,\mathcal {P}) , is the minimum integer k to guarantee the existence of a mapping \phi :\mathcal P\to \1,2,\ldots, k\ , such that \phi (P)\neq \phi (\widehat P) if P and \widehat {P} have common arc(s). The global packing number of (G,N) , denoted by \Phi (G,N) , is defined to be the minimum \Phi (G,N,\mathcal {P}) among all possible path systems \mathcal {P} . In additional to wavelength division optical networks, this number also carries significance for networks employing time division multiple access. In this paper, we compute by explicit route construction the global packing number of (\text Tn,N) , where Tn denotes the topology of the n -ary fat-tree network, and $N$ is considered to be the set of all edge switches or the set of all supported hosts. We show that the constructed routes are load-balanced and require minimal link capacity at all network links. [ABSTRACT FROM AUTHOR]

Protocol sequences have recently been studied in collision channels without feedback for dynamic multiple-access mobile applications, such as wireless sensor and vehicular ad hoc networks. In this paper, a method of systematically adding mark chips into some families of prime sequences for the construction of protocol sequences with adjustable duty factors is investigated. Not relying on computer simulation only, new theoretical models of throughput and its variance are formulated to analyze the sequence performance by means of average hit probabilities. Numerical studies and computer simulations are performed to validate the new analytical models. With adjustable duty factors, these protocol sequences support flexible exchange between throughput and the number of active users. [ABSTRACT FROM PUBLISHER]

In this paper, we study completely irrepressible (CI) sequences. For a slot-asynchronous communication system supporting K users with such sequences, a key feature is that each user is guaranteed to be able to send out at least one contention-free packet in one common sequence period. This is a desirable property since it provides a bounded delay guarantee for medium access control (MAC) layer contention, in contrast to random access schemes. Generalizing previous studies on CI sequences, we investigate systems endowed with multiple-packet reception (MPR) capability \gamma, \mbox2 \leq \gamma < K. That is, a packet transmission is successful if and only if the total number of transmissions in the channel at any point in time during its transmission is less than or equal to \gamma. We investigate the minimum period L of CI sequences for MPR as L is a fundamental factor that affects the worst-case delay. The main result is that L is asymptotically upper bounded by when \gamma \geq \mbox{3}. For \gamma = \mbox{2}, the corresponding bound is \mbox2K^2. In contrast, the bound for the single-packet reception system (\gamma=\mbox1) is \mbox4K^2. Simulation results verify our analysis and present comparative studies between CI sequences and random access in an application of group-based detection in a wireless sensor network. [ABSTRACT FROM AUTHOR]

Consider a time-slotted communication channel that is shared by $K$ active users transmitting to a single receiver. It is assumed that the receiver has the ability of the multiple-packet reception to correctly receive up to $\gamma$ ($1 \leq \gamma < K$) simultaneously transmitted packets. Each user accesses the channel following a deterministic binary sequence, called the protocol sequence, and transmits a packet within a channel slot if the sequence value is equal to one. If the users are not time synchronized, the relative shifts among them can cause significant fluctuation in throughput. If the throughput of each user is independent of relative shifts, then the adopted protocol sequence set is said to be throughput-invariant (TI). If we define worst-case system throughput as the minimal system throughput that can be guaranteed for any set of relative shifts, then TI sequences maximize it and hence are of fundamental interest. This paper investigates TI sequences for $\gamma \geq 1$. Several new results are obtained including throughput value as a function of the duty factors, a lower bound on the sequence period, a construction that achieves the lower bound on the sequence period, and theorems on the intrinsic structure that establish connections with some other families of binary sequences. [ABSTRACT FROM PUBLISHER]