We investigate coding schemes that map source symbols into multisets of an alphabet. Such a formulation of source coding is an alternative approach to the traditional framework and is inspired by an object tracking problem over proximity sensor networks. We define amultiset combinatorial Gray codeas a mulitset code with fixed multiset cardinality that possesses combinatorial Gray code characteristic. For source codes that are organized as a grid, namely an integer lattice, we propose a solution by first constructing a mapping from the grid to the set of symbols, which we referred to as colors. The codes are then defined as the images of rectangular blocks in the grid of fixed dimensions. We refer to the mapping as acolor mappingand the code as acolor multiset code. We propose the idea of product multiset code that enables us to construct codes for high dimensional grids based on 1-dimensional (1D) grids. We provide a detailed analysis of color multiset codes on 1D grids, focusing on codes that require the minimal number of colors. To illustrate the application of such a coding scheme, we consider an object tracking problem on 2D grids and show its efficiency, which comes from exploiting transmission parallelism. Some numerical results are presented to conclude the paper.

We focus on the Age of Information (AoI) performance in a system where each user generates packets periodically to send to a common access point (AP) for status updating. To avoid heavy overhead, we assume that channel sensing, feedback information from the AP, and time synchronization are not available in the system. We adopt a multi-access scheme called the sequence scheme, where each user is assigned a periodic binary sequence to schedule their transmissions. In our previous work, we have thoroughly studied the AoI performance under the sequence scheme when the sequence period,L, is equal to the status generating period,T. However, the case ofT̸=Lis not covered by the previous work. Therefore, in this paper, we aim at analyzing the AoI performance for general values ofTandL, which is more challenging and requires different approaches. We conduct in-depth analysis and develop a mathematical tool based on integer partitions to facilitate the analysis. We derive low-complexity closed-form expressions for two special cases. Based on the obtained analytical results, we propose an optimization method for parameter selection in sequence construction to minimize the average AoI. Finally, we compare our proposed sequence scheme with two commonly used baselines, and show that our proposed scheme outperforms the baselines in terms of AoI performance while consuming less energy.

We consider the tracking problem of an object that can randomly appear on a line of a fixed length. We want to determine the position of the object and rely on sensors that can detect objects with a predefined range and report that to a remote observer. Sensors are equipped with a transmitter that can transmit at a limited data rate. Once a sensor is triggered, it transmits its own ID to inform. A straightforward protocol is to label each sensor with different ID. However, this would require a large number of unique IDs and many bits to represent. As a result, higher data rate is required. We propose a newly defined protocol using multiset color coding with optimal design or efficiency in reusing a much smaller number of IDs for the whole system. We only require the minimal number of bits for labeling each sensor. We derive the factor of reduction and show its significance. We present some optimal constructions for the required multiset color coding sequence. Besides, we derive the general upper and lower bounds for the maximum length (size) of the system. Numerical examples have also demonstrated the effectiveness and improvement by the proposed new method.

In this correspondence, a corrected version of the upper bound on the number of codewords for a multichannel CAC of weight three is presented.

This paper considers a system in which multiple users send periodically generated status information to a common access point (AP) over a collision channel. To avoid high overhead, there is no time synchronization and no feedback information from the AP to indicate whether a transmission is successful or not. The performance metric that we focus on is the age-of-information (AoI), which represents the freshness of the status information received at the AP. For this model, we propose a sequence based MAC scheme in which each user is pre-assigned a periodic sequence to schedule transmissions. This scheme guarantees each user at least one successful packet transmission within a sequence period, in the absence of time synchronization and feedback information from the AP. To the best of our knowledge, this is the first study investigating AoI performance under a sequence based MAC scheme. We derive the closed-form expressions for average AoI, average peak AoI and average age penalty under the sequence based scheduling. Besides, we derive several critical properties of the sequences to optimize the AoI performance. Comparison results show that our proposed sequence scheme outperforms slotted ALOHA and framed ALOHA in various settings.

We focus on the problem of asymptotically mean-square stabilization in discrete-time stochastic systems that exhibit plant uncertainty, multiple input delays, and multiplicative noises. Our innovative contributions are described as follows. First, we employ a reduction method to transform the original model into a delay-free auxiliary system, and establish an equivalent proposition for stabilization based on this reformulation. On the basis of the reformulated model, we propose two stabilization criteria for the uncertainty-free case, including both Lyapunov-type and Riccati-type criteria. More generally, we extend the stabilization result to the uncertain model, and propose a necessary and sufficient stabilization criterion utilizing matrix homogeneous polynomials. Finally, we explore the existence and uniqueness of a delay margin under certain structural restrictions, and provide a closed-form representation of this margin.

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(lnT) . Moreover, we address an online optimization problem with output-feedback control policy and propose a heuristic online control policy.

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.

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.

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.

This paper studies adversarial bandits with corruptions. In the basic adversarial bandit setting, the reward of arms is predetermined by an adversary who is oblivious to the learner’s policy. In this paper, we consider an extended setting in which an attacker sits in-between the environment and the learner, and is endowed with a limited budget to corrupt the reward of the selected arm. We have two main results. First, we derive a lower bound on the regret of any bandit algorithm that is aware of the budget of the attacker. Also, for budget-agnostic algorithms, we characterize an impossibility result demonstrating that even when the attacker has a sublinear budget, i.e., a budget growing sublinearly with time horizon T, they fail to achieve a sublinear regret. Second, we propose ExpRb, a bandit algorithm that incorporates a biased estimator and a robustness parameter to deal with corruption. We characterize the regret of ExpRb as a function of the corruption budget and show that for the case of a known corruption budget, the regret of ExpRb is tight.

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.

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.

This paper considers a multiple-access system with multiple-packet reception (MPR) capability γ, i.e., a packet can be successfully received as long as it overlaps with γ -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, if this user has sensed n ongoing transmissions for n = 0, 1,⋯, 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.

Optical technologies based on Wavelength Division Multiplexing (WDM) are gaining popularity for Data Center Networks (DCNs) due to their technological strengths such as low communication latency, low power consumption, and high link bandwidth. Observe that the BCube networking topology has been widely applied to modular DCNs due to its high scalability and cost effectiveness. Therefore, it is worth investigating optical techniques into BCube DCNs. Routing and Wavelength Assignment (RWA) is a critical problem in optical networks, which can be formulated as an integer programming problem. To gain better insights into RWA solutions, researchers proposed two concepts: the forwarding and optical indices. Consider the all-to-all traffic in an all-optical network, where every host sets up a connection with every other host. The optical index is defined as the minimum number of wavelengths, required to support simultaneous all-to-all communication, under the restriction that each connection is assigned a fixed wavelength. The forwarding index is measured to be the minimum of maximum link loads over all possible all-to-all routings, where we define the maximum link load as the maximum number of paths passing through any link, and define an all-to-all routing as a set of paths specified for all host pairs. In this paper, we study the forwarding and optical indices of an all-optical BCube DCN. First, we compute the forwarding index, which is also a natural lower bound of the optical index. Second, we propose an oblivious RWA scheme, which is further used to derive an upper bound of the optical index. Finally, we derive a tighter upper bound of the optical index by means of the chromatic numbers in Graph Theory.

We consider an ad hoc network in which each node has an individual data stream to unicast to each of its neighboring nodes. Since the nodes may start their communications at different times, there exist delay offsets among them. The values of delay offsets are assumed to be unknown due to a lack of cooperation among the nodes and the absence of a centralized coordination mechanism. For such a network, we propose a distributed transmission scheduling scheme that pre-assigns to each node a periodic schedule sequence. We show that there exist schedule sequence sets for any finite number of nodes to ensure that each node can transmit at least one packet to each other node within a period, for all possible delay offsets. In this paper, we analyze the lower bounds on the period length and propose sequence construction methods to approach the lower bounds, for both of the single channel model and the multi-channel model.

We study delay-constrained input-queued switches where each packet has a deadline that will expire if it is not delivered before its deadline. Such a new scenario is motivated by the proliferation of real-time applications in multimedia communication systems, tactile Internet, networked controlled systems, and cyber-physical systems. One fundamental problem centering around the performance metric of timely throughput is how to characterize the capacity region. In this work, for the frame-synchronized traffic pattern, we characterize the capacity region by a polynomial number of linear constraints.

In this paper, we aim to effectively utilize in-network buffering to schedule and route packets with low communication overhead, small delay and throughput optimality in fat-tree networks. While nearly zero in-network queueing can be guaranteed by performing precise time allocation and path assignment at network endpoints as in Fastpass, there is a high communication overhead, and buffer occupancy at the endpoints can become bottlenecks. By spreading scheduling functionalities to different network layers in a fat-tree network, the complexity can be decreased significantly at the cost of moderate buffer occupancy at intermediate switches. Inspired by this observation, we propose a simple dynamic pod scheduling (DPS) scheme, which performs scheduling at the granularity of pod units, each of which is paired to at most one other pod unit to transmit packets at each slot. By doing so, less information is required to arrange the packet transfers and inter-pod traffic will experience less downlink contentions. Through extensive evaluations, we find that DPS outperforms Fastpass in terms of delay while still guaranteeing throughput-optimality.

Protocol sequences are deterministic binary sequences of a common period, which enjoy some special Hamming cross-correlation property by design. In contrast to random or contention-based medium access control schemes, a protocol sequence-based scheme can serve to provide at least a certain number of contention-free packet transmissions within a bounded delay for each asynchronous user in a feedback-free multiple access system. However, all protocol sequence-based schemes in the literature require that all sequence entries are mapped to slots with the same time duration, which produces a relatively low channel utilization. To overcome this inefficiency that is undesirable in delay-constrained wireless sensor networks, building on the idea of combining sequence-based access and carrier sensing, this paper proposes a new protocol sequence-based scheme, called the PS-CS. We derive the theoretical average throughput, average access delay, worst-case delay, and average energy consumption of the PS-CS. It is shown that the PS-CS produces average throughput close to the optimal capacity of p-persistent carrier sense multiple access (CSMA), and enjoys smaller access delay than the optimal p-persistent CSMA. In addition, we study the energy-delay tradeoff, impact of carrier sensing fault and channel error, and how to modify the PS-CS to support real-time downlink for feedback control.

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 of timely 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.

In this paper, a delay-dependent algebraic Riccati equation (DARE) approach is developed to study the meansquare 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 ≥ 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.

Protocol sequences are periodic zero-one sequences for the scheduling of packet transmissions in a time-slotted channel. A special class of protocol sequences, called shift-invariant sequences, plays a key role in achieving the information-theoretic capacity of the collision channel without feedback. This class of shift-invariant protocol sequences has the property that the pairwise Hamming crosscorrelation functions are invariant to relative delay offsets. However, the common period of shift-invariant sequences grows exponentially as a function of the number of supported users. In this paper, we consider a family of protocol sequences, whose period increases roughly as a quadratic function of the number of the users, and show that it is close to shift-invariant by establishing a bound on the pairwise Hamming crosscorrelation. The construction is based on the Chinese remainder theorem (CRT), and hence the constructed sequences are called CRT sequences. Applications to collision channel allowing successive interference cancellation at the receiver are discussed.

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.

The collision channel without feedback (CCw/oFB) model depicts a scenario in which multiple users share a communication channel with random relative time offsets among their clocks. This paper considers an extension of this model, which allows the receiver to use successive interference cancellation (SIC) to iteratively cancel the interference caused by those collided packets that have been decoded by the receiver. We derive the zero-error capacity region of this channel in the slot-synchronous case, and present a zero-error capacity achieving scheme by joint protocol sequences and channel coding design. It is shown that the negative impact on the zero-error capacity due to a lack of time synchronization can be removed by SIC.

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 ⊆ V(G) be a set of nodes. A path system 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 P, denoted by Φ(G, N, P), is the minimum integer k to guarantee the existence of a mapping φ : P → (1, 2, ..., k), such that φ(P) ≠ φ(P̅) if P and P̅ have common arc(s). The global packing number of (G, N), denoted by Φ(G, N), is defined to be the minimum Φ(G, N, P) among all possible path systems ?. 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 (Tn, N), where Tndenotes 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.

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.

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 γ (1 ≤ γ <; 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 γ ≥ 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.

We consider the slot-synchronized collision channel without feedback, in which K active users all transmit their packets to one sink. It is assumed that the channel has the ability of the multiple-packet reception (MPR), i.e., can accommodate at most γ (1 ≤ γ1. For both design objective, we establish a lower bound on sequence period and prove the lower bound can be achieved by some construction.

In this paper we investigate the identification and synchronization problems on a multiple access collision channel. Following Massey's lead, solutions to these problems are addressed by protocol sequences. This paper considers two different levels of user synchroneity: frame-synchronous access and slot-synchronous access. For the identification problem, we study user-detectable sequences. These are sequences with the cross-correlation property that allows each active user be detected within a bounded delay basing only on the channel activity information observed. Furthermore, we investigate the synchronization problem for delay-detectable sequences under the slot-synchronous access assumption. The goal of the synchronization problem is to determine the offset relations among all the active users. Sequences that allow such determination can be viewed as a special subset of user-detectable sequences. For both of these sequence families, it is desirable that the sequence length should be as short as possible. Hence, it is important to derive the minimum sequence lengths for these respective families. This is an extremely difficult open problem. Nevertheless, lower and upper bounds on these minimum lengths are presented in this paper under different levels of synchroneity assumptions. In addition, the performance of these sequences is demonstrated via numerical simulation.

Protocol sequences offer a promising alternative for media access control of mobile ad hoc networks, because they do not require any coordination among the users nor any centralized synchronization. We show that by using suitably designed deterministic scheduling, the delay performance can indeed be much better than using random and pseudo-random sequences. The reported results indicate that protocol sequences can offer practical solutions to complicated multiple-access problems in ad hoc networks, such as vehicular ad hoc networks (VANET). The cumulative distribution function of delay and an upper bound of the individual delay in the cases of protocol sequences are derived.

Ideally, many application systems for distributed users should be designed without requiring a centralized controller, for example cloud computing or wireless sensor networks. A fundamental challenge to developing distributed algorithms for these systems is load balancing, which is the focus of study in this paper. A common feature of these distributed algorithms is that routing decisions should be derivable without requiring much information from the system, probabilistic routing is one example coming to mind. In this paper, we propose a new routing strategy based on the idea of shift-invariant protocol sequences. We study this load balancing approach in the context of a queuing model of multi-server system. Our model and strategy can be applied to many practical systems, including wireless networks. Numerical studies were carried out to compare our strategy with other routing strategies such as probabilistic routing and random sequences routing. The results show that the proposed algorithm has better performance than these strategies.

This paper derives respective precise bit error probability (BEP) expressions for a two-user binary phase shift keying (BPSK) system in Rayleigh, Nakagami and Rician fading channels. Our expressions allow for different symbol rate and symbol timing asynchronism between the desired user and interfering user. We provide some theoretical results concerning the BEP performance with respect to the fading severity. Comprehensive simulation study and comparison of the BEP performance between the Gaussian and non-Gaussian interference models are also provided. The results show that the Gaussian interference model has limitation in predicting the exact BEP performance in fading channels. It fails in accurately tracking the variation of the BEP with respect to the signal-to-noise ratio (SNR), signal-to-interference ratio (SIR), symbol rate ratio and fading severity.

In some real-time networked control applications, information between sensors and controllers is exchanged over a shared wireless channel. One key issue is to manage multiple access to the shared medium to accomplish different control tasks. In the paper, a protocol sequence based media access control (MAC) design is presented for networked control systems (NCSs). It is challenging to design an optimal or suboptimal controller since the sensor packets and control packets could be lost in unreliable wireless networks. An ad hoc and efficient control policy is presented. Numerical results illustrate that the cost performance of the protocol sequence based NCS is much better than that of the π-persistent random access based NCS.

Strongly conflict-avoiding codes (SCACs) are used in the slot-asynchronous multiple-access collision channel without feedback to guarantee that each active user can send at least one packet successfully in the worst case within a fixed period of time. The number of codewords in an SCAC is the number of potential users that can be supported. In this paper, a general upper bound on the size of SCAC is derived. We further improve the upper bound if the code has some special structure, called equi-difference, and we show this bound is asymptotically tight.

Signal-to-noise (SNR) ratio is commonly regarded as a reliable performance measure for wireless communication systems. Knowledge of fundamental properties of the feasible SNR region can facilitate the performance optimization of multi-user wireless systems. This paper examines the concavity of the feasible SNR region. In particular, it is shown that for systems with only three users, the feasible SNR region is always concave. As concavity for 2-D systems is well known and concavity for 4-D systems does not hold in general, this result fills in a gap on this issue. A concavity result for systems with a general number of users is also established under certain technical conditions.

This paper investigates a wireless communication system where the mutual user interference is not assumed to be a Gaussian process. We derive an exact expression for the average bit error probability (BEP) for such a system and study the non-Gaussian interference model through two types of power control problems. We analyze the situation under which the system can be asymptotically error-free, the behavior of users' BEP when scaling up a fixed power setting by a uniform scalar and the effect of varying symbol rate on the system performance. Our work shows that the non-Gaussian model has significantly different performance characteristics from the traditional Gaussian interference model. Simulations also show that the Gaussian model is generally pessimistic in comparison with the non-Gaussian model.

Protocol sequences are used in channel access for the multiple-access collision channel without feedback. A new construction of protocol sequences with a guarantee of worst-case system throughput is proposed. The construction is based on Chinese remainder theorem. The Hamming cross-correlation is proved to be concentrated around the mean. The sequence period is much shorter than existing protocol sequences with the same throughput performance. The new construction reduces the complexity in implementation and also shortens the waiting time until a packet can be sent successfully.

Protocol sequences are used for channel access in the collision channel without feedback. Each user accesses the channel according to a deterministic zero-one pattern, called the protocol sequence. In order to minimize fluctuation of throughput due to delay offsets, we want to construct protocol sequences whose pairwise Hamming cross-correlation is as close to a constant as possible. In this paper, we present a construction of protocol sequences which is based on the bijective mapping between one-dimensional (1-D) sequence and two–dimensional (2-D) arrays by the Chinese Remainder Theorem (CRT). In the application to the collision channel without feedback, a worst-case lower bound on system throughput is derived.

Conflict-avoiding codes are used in the multiple-access collision channel without feedback. The number of codewords in a conflict-avoiding code is the number of potential users that can be supported in the system. In this paper, a new upper bound on the size of constant-weight conflict-avoiding codes is proved. This upper bound is general in the sense that it is applicable to all code lengths and all Hamming weights. Several existing constructions for conflict-avoiding codes, which are known to be optimal for Hamming weights equal to four and five, are shown to be optimal for all Hamming weights in general.

Protocol sequences are used for channel access in the collision channel without feedback. Each user is assigned a deterministic zero-one pattern, called protocol sequence. The zeros and ones in a protocol sequence are read out periodically, and a packet is sent if and only if it is one. A collision occurs if two or more users transmit at the same time. Due to the lack of feedback from the receiver and cooperation among users, the beginning of the protocol sequences cannot be synchronized and relative delay offsets are incurred. We study the design of protocol sequences from two different perspectives. Under the first one, called shift invariance, we aim at minimizing the fluctuation of throughput due to relative delay offsets. As for the second one, called user irrepressibility, we want to guarantee that each user can send at least one packet successfully in each period. For both design criteria, we derive a lower bound on sequence period and give an optimal construction that achieves this lower bound.

This paper investigates the power control problem involving a small number of active users whereby the standard Gaussian interference noise assumption does not hold. The model also allows for different user transmission rates. We analyze the situation under which the system can be asymptotically error-free. Subsequently, we formulate a power control optimization problem and propose an iterative descent algorithm for solution. We prove that under suitable conditions, the power control optimization problem has a unique solution which is achieved by the proposed algorithm. Simulations are carried out and compared with the power control results under the classical Gaussian assumption.

The authors consider collision channel without feedback in which collided packets are considered unrecoverable. For each user, the transmission of packets follows a specific periodical pattern, called the protocol sequence. Due to the lack of feedback, the beginning of the protocol sequences cannot be synchronized and nonzero relative offsets are inevitable. It results in variation of throughput. In this paper, we investigate optimal protocol sequence sets, in the sense that the throughput variance is zero. Such protocol sequences are said to be shift-invariant (SI). The characterizing properties of SI protocol sequences are presented. We also prove that SI sequences are identifiable, meaning that the receiver is able to determine the sender of each successfully received packet without any packet header. A general construction of SI sequences that meets the lower bound on sequence length is given. Besides, we study the least periods of SI sequences, and show that the least periods must be distinct in some cases. The throughput performance is compared numerically with other protocol sequences.

In this paper, a family of linear congruence sequences with interesting cross-correlation properties is investigated for potential applications in defining new multiple access protocols for distributed wireless systems. One can show that for any finite subset of the sequences with rate sum not exceeding a certain level, there cannot have enough collisions to completely block any particular user no matter how they are shifted with respect to one another. The user un-suppressibility and service guarantee can be exploited in many applications such as wireless sensor or impulse radio systems. To enhance the system's allowable rate sum while possessing the non-blocking property, new protocol sequences are designed. Besides, the throughput shift-invariant property is obtained.

In this paper we investigate the power control problem associated with a special class of Wireless Mesh Networks, known as the Wireless Lattice Networks. These networks function mainly as backbone networks. A natural question for a network in such a class is to determine its maximum flow for a given an end-to-end traffic distribution. For a given set of self-interfering links, known as a web, the maximum flow is shown to be the solution of a nonlinear matrix equation. The maximum flow of the network can then be determined from the maximum flows of the webs it contains.

In wireless ad hoc networks, PHY-layer interference is highly dependent on link scheduling schemes, and in turn heavily affects the performance of link scheduling. However, most existing link scheduling schemes ignore such relationship between the PHY and network layers, and hence fail to achieve the optimal end-to-end throughput due to large co-channel interference. This paper proposed a general framework for optimal TDMA (time division multiple access) link scheduling in multi-hop wireless ad hoc networks with general topology. In contrast to existing work, we maximizes the end-to-end throughput by taking into consideration the explicit relationship between the transmission rate of a link and its PHY-layer SINR (signal to interference and noise ratio). In particular, the authors formulate the scheduling problem into a LP (linear programming) problem based on the rate matrices with each entry being a function of SINR. With this formulation, the cross-layer link scheduling problem can be solved in polynomial time. To further reduce the computational complexity the authors proposed an algorithm to effectively reduce the size of the LP problem. Furthermore, to handle large-scale wireless networks, the authors present a decentralized scheduling algorithm that achieves a suboptimal TDMA scheduling solution with dramatically lower computational complexity comparing to the original LP formulation. Numerical results show that the proposed cross-layer link scheduling schemes outperform the existing schemes that assume a simplistic PHY-layer interference model by 59.45%.

This paper proposes and analyzes a new distributed power-control algorithm based on the theory of stochastic approximation. The power-control problem is first converted into a stochastic approximation problem in which the zero point of a specific function is determined. A distributed power-control algorithm is then derived and its convergence properties are analyzed using standard techniques. In the distributed algorithm, each user iteratively updates its power level by using estimates of the inverse of the signal-to-interference ratio (SIR) of its channel. No knowledge of the channel gains or state information of other users is required. Moreover, the algorithm is robust in the sense that it can handle errors in the bit-error rate estimates, and hence, can be used in practical scenarios. Convergence of the algorithm is analyzed in the almost-sure sense

This paper deals with a class of power control problems where the system link gains are assumed to be time varying and SIR estimates are allowed to be corrupted with bounded noises. A simple distributed algorithm of fixed-step power control is devised and the feedback requires only local information. As a generalization of the power control algorithm proposed by Sung and Wong, we have obtained a more robust solution which can handle time varying link gains and measurement noises. Convergence of the new algorithm is analyzed and numerical studies show that it is effective.

In integrated wireless multimedia service, isochronous traffic of different connections can be scheduled by using a most regular binary sequence (MRBS). Such a sequence schedules traffic in an evenly spaced manner to achieve any arbitrary rate asymptotically and while avoiding excessive delay or buffering requirement. Flexible slot assignment that can match requests exactly improves bandwidth efficiency in multirate operations. The most regular binary sequence provides a distributed solution for multiaccess control that is based on limited information exchange. As a generalization, the concept of a most regular code sequence (MRCS) is proposed to support variable rate transmission in wideband code division multiple access (CDMA) systems and to provide spreading factor (SF) optimization. This scheme improves channel utilization efficiency in supporting traffics of various classes and hence results in an overall capacity gain.

We consider the convergence issues of distributed power-control algorithms for mobile cellular systems. A convergence theorem for power-control algorithms of canonical type is proved. Our result generalizes Yates' framework and provides a new outlook on the problem. The general applicability of the theorem is demonstrated by showing that many well-known distributed algorithms are canonical. Furthermore, by devising some new discrete algorithms, we exemplify how the theorem can be used to aid new design.

With the enormous growth of the World Wide Web in recent years, the issue of how to discover Web pages efficiently has become an important challenge for Web crawler designers. In this paper, we will outline a simple model to predict the distribution of the search depth in a breadth-first search to reach the first Web pages relevant to a user query. We define this probability as the crawler confidence. Recent studies by Y. Deshpande and S. Hansen (2001) indicate that at a large scale the Web structure subscribes to power law distribution on several aspects. However, our work tries to model a microscopic linkage structure of the Web from an intelligent crawler's point of view. With the information provided by crawler confidence, an intelligent crawler can adjust its crawling behavior to achieve a higher harvest rate.

The authors consider a multirate code-division multiple acess system, in which all users have the same chip rate and vary their data rate by adjusting the processing gain. The receivers are assumed to be implemented using conventional matched filters, whose performance is sensitive to the received power levels. The authors' goal is to maximize the total system throughput by means of power control. A game theoretic approach is adopted. It is shown that for a certain type of pricing function, a unique Nash equilibrium solution exists and it possesses nice global properties. For example, it can be shown that for the optimal solution a high-rate connection should maintain a higher energy per bit than low-rate ones. The asymptotic spectral efficiency is also derived.

We consider the convergence issues of distributed power control algorithms for mobile cellular systems. A convergence theorem for power control algorithms of canonical type is proven. Our result generalizes Yates' (1995) framework and provides a new outlook on the problem. The general applicability of the theorem is demonstrated by showing that all the well-known algorithms are canonical. Furthermore, by devising a new discrete algorithm, we exemplify how the theorem can be used to aid new design.

We consider a wireless multimedia code-division multiple-access system, in which the terminals transmit at different rates. We formulate the problem as a constrained optimization problem, with the objective of maximizing the total effective rate. An optimal power control strategy is derived. When the scale of the system is large, the optimal solution takes a simple form, which is easy to be applied practically. Furthermore, our basic model can be extended to include delay-sensitive traffic.

A new dynamic scheduling algorithm for controlling multimedia traffic is proposed. It is based on the idea of proportionally balancing a prescribed queue parameter so that the performance of sub-queues conform to stated quality of service (QoS) requirements. We call such algorithms, QPB algorithms. The new scheduling algorithm can guarantee different QoS requirements for heterogeneous traffic with a large multiplexing gain. Furthermore, we use the large deviation technique (LDT) in conjunction with the QPB algorithm to replace the conventional FIFO service discipline, and develop a generalized large deviation technique (GLDT). The combination of the QPB scheduling algorithm and GLDT admission control policy forms a complete dynamic resource sharing scheme for heterogeneous traffic streams with QoS provisioning, which is based on stochastic bounds instead of deterministic bounds. Some simulation results for the QPB algorithm are also provided. Since the basic model is based on a frame structure, the QPB algorithm is very appropriate for multimedia traffic control in wireless networks.

For Pt.I see ibid., p.1378-83, (2000). We discuss the performance of the QPB algorithm and modification of associated admission criteria when there are large deviations among the average arrival rates or quality of service (QoS) requirements from input traffic streams. By simulation analysis, the asymptotical characteristics of the probability distribution of backlog in a global queue are revealed, and is close to the bound determined by the generalized large deviation technique (GLDT). Furthermore, we present a numerical analysis approach to evaluate the performance and the stochastic tight bound of the QPB algorithm. The approach is particularly effective for scenarios with low packet loss probability. The obtained numerical results can be transformed into performance bounds and stored in a base station database as a criterion of traffic admission. Such a performance bound is normally more tight than the bound from large deviation theory. As an example, we present the numerical results under the assumption that all input traffic sources are independent Poisson processes.

We consider a wireless multimedia CDMA system, in which the terminals transmit at different rates. We formulate the problem as a constrained optimization problem, with the objective of maximizing the total effective rate. An optimal power control strategy is derived. When the scale of the system is large, the optimal solution takes a simple form, which is easy to be applied practically. Furthermore, our basic model can be extended to include delay-sensitive traffic. We have shown that the problem can be decoupled and our results are still valid in the general model.

This paper presents a dynamic location area assignment (DLA) algorithm. When a mobile unit (MU) exits a location area, a new location area is assigned based on the time-varying mobility statistics recorded by the MU. The overlapping region of the new and the original location area, and the location area size are dynamically adjusted. For any location area size, the expected dwell time of a MU in the assigned location area is maximized. Numerical examples show that the proposed algorithm outperforms conventional strategies under all mobility scenarios.

In a hybrid TDMA/FDMA digital communication system such as the GSM system, Global System for Mobile communications, a channel is defined by a tuple consisting of frequency band number and slot number. For a normal voice connection, an idle time slot will be assigned upon a channel request in uplink direction and correspondingly one for downlink direction. For multimedia applications with multi-rate connections, multiple slots are to be assigned. The problem of how to assign the slots efficiently arises if the slots can be chosen from different frequency bands. In the study presented here, a heuristic channel assignment algorithm is proposed under the assumption that a mobile unit can simultaneously transmit data through multiple frequency bands. The goal is to keep the number of frequencies used small in each connection so as to keep the intercell interference low. The proposed algorithm, having an inference property, is based on the binary clustering of idle time slots to speed up the channel assignment process. The proposed algorithm is compared to a locally optimal algorithm by simulation and is shown to be more time efficient with minimal tradeoff.

A hybrid Bloom filter location update algorithm is proposed for wireless cellular systems. This belongs to a new category of algorithms characterized by contention free access of uplink control channels during location update. Two or more mobile units are permitted to register with a base station simultaneously without contention on the uplink channel. The location updating procedure is hybrid in the sense that it could be temporally or geographically triggered. Based on the location information stored in all base stations, Bloom filtering is used to select cells to be paged to locate the targeted mobile unit. The performance of this scheme is compared to other algorithms previous proposed. Numerical results shows that the new algorithm requires less combined location update and paging bandwidth than other algorithms.

The huge amount of handoffs generated by microcells creates a problem for the future PCN. To alleviate the problem, we propose a hierarchical cellular system which comprises cells of different sizes. Ideally, one would like to use large cells to serve high-mobility users. A challenging issue is to obtain a good estimate of the user speed. A simple speed estimation is proposed and based on this estimate one can implement a number of dynamic channel allocation algorithms on such a hierarchical network. A comparative study of these algorithms will be presented based on a detailed simulation model.>

A new distributed power control algorithm is introduced. The algorithm is based on the assumption that some limited control data communication between interfering transceivers is allowed. A summary of the convergence property and simulation studies of the algorithm is presented.>

By analyzing mathematical models, it is shown that combining channel borrowing with a coordinated sectoring or overlying scheme provides effective ways to handle hot-spots in the system. Blocking probabilities with these arrangements are derived, and the dynamic sharing with bias (DSB) rule is suggested for increasing the trunking efficiency. A simple handoff model is formulated and analyzed for comparing the probabilities of additional handoffs due to sectoring and overlaying of cells. With the nominal allocation of 60 channels per cell and a donor cell having a load of 30 Erlangs, numerical results show that at a blocking requirement of 1%, the traffic load in the hot-spot cell can be increased from 47 to 63 Erlangs with the use of the channel borrowing with the cell sectoring scheme: while with the use of the DSB rule, the load can be increased further to 71 Erlangs. A slightly higher load can be carried in the hot-spot cell with the use of cell overlaying arrangement.>

The elastic network approach is extended to solve the obstacle-avoidance tour-planning problem. The problem has potential applications to robot path planning and automatic assembly. It is shown that the elastic net approach is well suited for this problem. A software package was developed and is capable of solving problems of realistic size

Neural network memories with storage prescriptions based on Hebb’s rule are known to collapse as more words are stored. By requiring that the most recently stored word be remembered precisely, a new simple short-term neural network memory is obtained and its steady state capacity analyzed and simulated. Comparisons are drawn with Hopfield’s method, the delta method of Widrow and Hoff, and the revised marginalise model of Mezard, Nadal, and Toulouse.

The LRU cache hit function is used as a general characterization of locality of reference to address the synthesis question of whether benchmarks can be created that have a required locality of reference. Several results are given that show circumstances under which this synthesis can or cannot be achieved. An additional characterization called the warm-start cache hit function is introduced and shown to be efficiently computable. The operations of repetition and replication are used to form new programs, and their characteristics are derived. Using these operations, a general benchmark synthesis technique is obtained and demonstrated with an example.>

An arbitrary interleaved execution of transactions in a database system can lead to an inconsistent database state. A number of synchronization mechanisms have been proposed to prevent such spurious behavior. To gain insight into these mechanisms, we analyze them in a simple centralized system that permits one read operation and one write operation per transaction. We show why locking mechanisms lead to correct operation, we show that two proposed mechanisms for distributed environments are special cases of locking, and we present a new version of lockdng that alows more concurrency than past methods. We also examine conflict graph analysis, the method used in the SDD-1 distributed database system, we prove its correctness, and we show that it can be used to substantially improve the performance of almost any synchronization mechanisn.