Electric vehicles (EVs) are at the intersection of transportation systems and energy systems. The EV batteries, an increasingly prominent type of energy resource, are largely underutilized. We propose a new business model that monetizes underutilized EV batteries as mobile energy storage to significantly reduce the demand charge portion of many commercial and industrial users’ electricity bills. This business requires minimal hardware to enable discharging the batteries of electric vehicles and a sharing platform that matches EVs to commercial electricity users in real time. Using real meter data, we show that a large number of users can be served by a small number of EVs in the proposed business model. Cost-revenue analysis based on a real electric tariff suggests that the demand charge saving covers the capital costs of needed hardware and the compensation for EV drivers to provide the service.

A signal phase and timing (SPaT) message describes the current phase at a signalized intersection for each lane, together with an estimate of the residual time of that phase. Accurate SPaT messages can be used to construct a speed profile for a vehicle that reduces its fuel consumption as it approaches or leaves an intersection. This paper presents SPaT estimation algorithms at an intersection with a semi-actuated signal, using real-time signal phase measurements. The algorithms are evaluated using high-resolution data from an intersection in Montgomery County, MD, USA. The algorithms can be readily implemented at signal controllers. This paper supports three findings. First, real-time information dramatically improves the accuracy of the prediction of the residual time compared with the prediction based on historical data alone. Second, as time increases, the prediction of the residual time may increase or decrease. Third, as drivers differently weight errors in predicting “end of green” and “end of red,” drivers on two different approaches may prefer different estimates of the residual time of the same phase.

The paper evaluates the influence of the maximum vehicle acceleration and variable proportions of ACC/CACC vehicles on the throughput of an intersection. Two cases are studied: (1) free road downstream of the intersection; and (2) red light at some distance downstream of the intersection. Simulation of a 4-mile stretch of an arterial with 13 signalized intersections is used to evaluate the impact of (C)ACC vehicles on the mean and standard deviation of travel time as the proportion of (C)ACC vehicles is increased. The results suggest a very high urban mobility benefit of (C)ACC vehicles at little or no cost in infrastructure.

Automatic vehicle classification (AVC) systems provide data about vehicle classes that are used for many purposes. This paper describes a prototype axle count and spacing AVC system using wireless accelerometers and magnetometers. The accelerometers detect vehicle axles, and the magnetometers report vehicle arrivals and departures and estimate speed. The prototype system is installed on Interstate 80 at Pinole, CA, USA, and tested under various traffic conditions. Video images and reports from a nearby commercial weigh-in-motion station provide ground truth to evaluate the performance of the system, including classification, axle spacing, and vehicle counts. The results show that the prototype AVC system is reliable in classifying vehicles even under congested traffic with accuracy of 99%.

Truck weight data is used in many areas of transportation such as weight enforcement and pavement condition assessment. This paper describes a wireless sensor network (WSN) that estimates the weight of moving vehicles from pavement vibrations caused by vehicular motion. The WSN consists of: acceleration sensors that report pavement vibration; vehicle detection sensors that report a vehicle's arrival and departure times; and an access point (AP) that synchronizes all the sensors and records the sensor data. The paper also describes a novel algorithm that estimates a vehicle's weight from pavement vibration and vehicle detection data, and calculates pavement deflection in the process. A prototype of the system has been deployed near a conventional Weigh-In-Motion (WIM) system on I-80 W in Pinole, CA. Weights of 52 trucks at different speeds and loads were estimated by the system under different pavement temperatures and varying environmental conditions, adding to the challenges the system must overcome. The error in load estimates was less than 10% for gross weight and 15% for individual axle weights. Different states have different requirements for WIM but the system described here outperformed the nearby conventional WIM, and meets commonly used standards in United States. The system also opens up exciting new opportunities for WSNs in pavement engineering and intelligent transportation.

High speed communication systems play an important role in the development of advanced networks. The optimum design of these communication links under bandwidth and power constraints needs the use of efficient approaches. In this paper, a novel power efficient modulation scheme is introduced. For this purpose, the modulator at the transmitter uses simple and effective pulse shaping functions to change the amplitude and width of the transmitter pulse. Using this simple method, a high power efficient transceiver structure, with the same performance as typical NRZ signaling, can be designed. Our results show that not only we can reduce the power consumption by more than 10\% without loosing the performance but also the probability of error is improved in the presence of jitter and interference.

The drastic reduction of carbon emission to combat global climate change cannot be realized without a significant contribution from the electricity sector. Renewable energy resources must take a bigger share in the generation mix, effective demand response must be widely implemented, and high-capacity energy storage systems must be developed. A smart grid is necessary to manage and control the increasingly complex future grid. Certain smart grid elements—renewables, storage, microgrid, consumer choice, and smart appliances—increase uncertainty in both supply and demand of electric power. Other smart gird elements—sensors, smart meters, demand response, and communications—provide more accurate information about the power system and more refined means of control. Simply building hardware for renewable generators and the smart grid, but still using the same operating paradigm of the grid, will not realize the full potential for overall system efficiency and carbon reduction. In this paper, a new operating paradigm, called risk-limiting dispatch, is proposed. It treats generation as a heterogeneous commodity of intermittent or stochastic power and uses information and control to design hedging techniques to manage the risk of uncertainty.

A system is described that measures the vehicle count and travel time in the links of a road network. The measurements require matching vehicle signatures recorded by a wireless magnetic sensor network. The matching algorithm is based on a statistical model of the signatures. The model itself is estimated from the data. The approach is first discussed for a single-lane road and extended to multiple-lane roads. The algorithm yields a correct matching rate of 75% for a false matching rate of 5% and reliably estimates the number of vehicles on each link and its travel-time distribution. The system is tested on a 0.9-mi-long segment of San Pablo Avenue, Albany, CA.

Algorithms for scheduling TDMA transmissions in multi-hop networks usually determine the smallest length conflict-free assignment of slots in which each link or node is activated at least once. This is based on the assumption that there are many independent point-to-point flows in the network. In sensor networks however often data are transferred from the sensor nodes to a few central data collectors. The scheduling problem is therefore to determine the smallest length conflict-free assignment of slots during which the packets generated at each node reach their destination. The conflicting node transmissions are determined based on an interference graph, which may be different from connectivity graph due to the broadcast nature of wireless transmissions. We show that this problem is NP-complete. We first propose two centralized heuristic algorithms: one based on direct scheduling of the nodes or node-based scheduling, which is adapted from classical multi-hop scheduling algorithms for general ad hoc networks, and the other based on scheduling the levels in the routing tree before scheduling the nodes or level-based scheduling, which is a novel scheduling algorithm for many-to-one communication in sensor networks. The performance of these algorithms depends on the distribution of the nodes across the levels. We then propose a distributed algorithm based on the distributed coloring of the nodes, that increases the delay by a factor of 10–70 over centralized algorithms for 1000 nodes. We also obtain upper bound for these schedules as a function of the total number of packets generated in the network.

In this paper, we present a novel algorithm for distributed transmit beamforming enabling multiple single-antenna nodes to simultaneously transmit a common message such that they constructively interfere at the receiver. In order to constructively interfere, the nodes iteratively estimate and adjust their carrier phases with the help of receiver feedback. The receiver's feedback is based on composite channel estimates calculated from two simultaneous transmissions initiated by the nodes at each iteration. We prove that starting from arbitrary carrier phases, the algorithm converges to the maximum gain almost surely. The algorithm is compared to the 1-Bit Feedback algorithm presented in [3] through simulation, and is shown to outperform it by margins of 4:1 and 3:1 on metrics reflecting power consumption and convergence rate, respectively. We simulate the impact of phase estimation errors on the algorithm's steady-state gain and show it to be robust to moderately large errors of plusmn 20deg. We analyze the causes of asynchrony in simultaneous message transmissions and simulate its contribution to phase estimation errors in the context of IEEE 802.15.4 packets. We show that the contribution falls within the acceptable plusmn 20deg range.

Monitoring its health by detecting its failed sensors is essential to the reliable functioning of any sensor network. This paper presents a distributed, online, sequential algorithm for detecting multiple faults in a sensor network. The algorithm works by detecting change points in the correlation statistics of neighboring sensors, requiring only neighbors to exchange information. The algorithm provides guarantees on detection delay and false alarm probability. This appears to be the first work to offer such guarantees for a multiple sensor network. Based on the performance guarantees, we compute a tradeoff between sensor node density, detection delay and energy consumption. We also address synchronization, finite storage and data quantization. We validate our approach with some example applications.

Advances in low-power and low-cost sensor networks have led to solutions mature enough for use in a broad range of applications, requiring various degrees of reliability. To facilitate this, a broad range of options are possible to tune reliability, throughput or energy cost in the IEEE 802.15.4 standard defining the medium access control (MAC) and physical layer for sensor networks. Knowing how to tune those knobs however requires detailed models of the protocol behavior under different conditions. In our earlier work, we have proposed a very accurate model for the slotted Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) access scheme of the IEEE 802.15.4 standard for the unacknowledged transmission mode. Because of the design of the 802.15.4 carrier sensing mechanism, modeling the performance of the network in case of acknowledged transmissions is not a trivial extension. In this paper, we hence derive such model and illustrate through simulations that it is extremely accurate. Next, using the model, guidelines are derived to optimize the energy or throughput performance of sensor networks using the IEEE 802.15.4 standard.

Advances in low-power and low-cost sensor networks have led to solutions mature enough for use in a broad range of applications varying from health monitoring to building surveillance. The development of those applications has been stimulated by the finalization of the IEEE 802.15.4 standard, which defines the medium access control (MAC) and physical layer for sensor networks. One of the MAC schemes proposed is slotted carrier sense multiple access with collision avoidance (CSMA/CA), and this paper analyzes whether this scheme meets the design constraints of those low-power and low-cost sensor networks. The paper provides a detailed analytical evaluation of its performance in a star topology network, for uplink and acknowledged uplink traffic. Both saturated and unsaturated periodic traffic scenarios are considered. The form of the analysis is similar to that of Bianchi for IEEE 802.11 DCF only in the use of a per user Markov model to capture the state of each user at each moment in time. The key assumptions to enable this important simplification and the coupling of the per user Markov models are however different, as a result of the very different designs of the 802.15.4 and 802.11 carrier sensing mechanisms. The performance predicted by the analytical model is very close to that obtained by simulation. Throughput and energy consumption analysis is then performed by using the model for a range of scenarios. Some design guidelines are derived to set the 802.15.4 parameters as function of the network requirements.

An adaptive beamforming algorithm that enhances the quality of the signal recorded by a microphone array is presented. The system described here attenuates the interference from spatially scattered sources while preserving the desired signal quality in the speech frequency range. A novel method for defining additional constraints within the adaptation process and performing beamforming in parallel across several frequency bands achieves undistorted recording even with slight errors in localizing the speaker. Simulation results show nearly optimal improvement of speech quality in various noisy environments. The algorithm is modified to perform in a real environment by introducing two modes of adaptation that switch according to the speaker activity. The implementation of this modified system demonstrates SNR gain close to that of the original simulated system. It is robust to localization errors and non-ideal environmental effects.

We derive formulas for the energy J(n) that a station's radio consumes when it transmits 1 MB of data in an IEEE 802.11 network with n stations. Calculations show that J(ra) grows approximately linearly with n, for n ges 4. The useful energy consumed in successful transmission and reception of data is constant; the remaining energy is wasted. When n = 15, the waste amounts to 80 percent of total energy, and this proportion grows with n. More than 60 percent of the waste is due to overhearing - reception of packets intended for another station. Overhearing can be eliminated by using information in RTS/CTS packets.

An unequal importance communication approach, for cheap, reliable and real-time image communication over heterogeneous networks and its applications in mobile multimedia communication systems is presented. Here, an image is partitioned into different layers of importance: base layer and enhancement layers. The low-rate base layer description, which can be strongly protected, is transmitted through a low-bandwidth, but robust and more expensive channel, supporting delay-sensitive applications (e.g. GSM network), while the high-rate enhancement layer description(s) are transmitted through a high-bandwidth, but high/variable-delay and cheap channel which does not support delay-sensitive applications (e.g. WLAN). In the receiver, when the base layer description is quickly received, an acceptable quality image is reconstructed, and when the enhancement layer description(s) are received a high quality image can be reconstructed. Our practical results indicated that this effective, flexible, and highly compatible method not only facilitates high quality image distribution among heterogeneous networks and increases the coverage, quality of service, and bandwidth and power efficiency but also decreases the delay and cost of image distribution in mobile communication systems.

The IEEE 802.15.4 standard defines the medium access control (MAC) and physical layer for sensor networks. One of the MAC schemes proposed is slotted carrier sense multiple access with collision avoidance (CSMA/CA), and this paper analyzes whether this scheme meets the design constraints of low-power and low-cost sensor networks. The paper provides a detailed analytical evaluation of its performance in a star topology network for both saturated and unsaturated periodic traffic.The form of the analysis is similar to that of Bianchi for IEEE 802.11 DCF only in the use of a per user Markov model to capture the state of each user at each moment in time. The key assumptions to enable this important simplification and the coupling of the per user Markov models are however different, as a result of the very different designs of the 802.15.4 and 802.11 carrier sensing mechanisms. The performance predicted by the analytical model is very close to that obtained by simulation. Throughput and energy consumption analysis is then performed and design guidelines are derived.

Energy efficient system design in wireless sensor networks has been previously discussed at different levels of the network protocol stack so as to provide the maximum possible lifetime of a given network. This paper proposes a novel idea to save energy through extra re lay nodes by eliminating geometric deficiencies of the given topology. Given the sensing locations, the problem is to determine the optimal locations of relay nodes together with the optimal energy provided to them so that the network is alive during the desired lifetime with minimum total energy. We first formulate the problem as a nonlinear programming problem. We then propose an approximation algorithm based on restricting the locations where the relay nodes are allowed to a square lattice. This algorithm approximates the original problem with performance ratio of as low as 2 by trading complexity. For the parking lot application we consider, the relay nodes provide a significant decrease in the total energy required to achieve a specific lifetime.

We address the effect of the errors occurring at the analog-to-digital converter (ADC), from quantization noise, circuit noise, aperture uncertainty and comparator ambiguity, on the accuracy of sensor field reconstruction. We focus on the oversampling of bandlimited sensor fields in a distributed processing environment. It has previously been shown that pulse code modulation (PCM) style sampling fails to decrease the quantization error above some finite sampling rate. We show that the dither-based scheme, developed to decrease the quantization error, fails to decrease random errors associated with circuit noise, aperture uncertainty and comparator ambiguity. We propose an advanced dither-based sampling scheme with the goal of reducing both kinds of errors by increasing the density of the sensor nodes. It is based on distributing the task of improving the quantization error and random error among the nodes. The error of the scheme is shown to be O(1/r/sup 1/2 /) for oversampling rate r. The maximum energy consumption per node is O(log(r)). Finally, the bit rate of the scheme is O(1/r/sup 1/2 /log(r)) and it offers robustness to node failures in terms of a graceful degradation of reconstruction error.

We consider the following problem of decentralized-statistical inference: given i.i.d. samples from an unknown distribution, estimate an arbitrary quantile subject to limits on the number of bits exchanged. We analyze a standard fusion-based architecture, in which each of m sensors transmits a single bit to the fusion center, which in turn is permitted to send some number k bits of feedback. Supposing that each of m sensors receives n observations, the mean-squared error of the optimal centralized protocol decays as O(1/nm). First, we describe the decentralized protocol based on k = m bits of feedback that is strongly consistent, and achieves the same asymptotic MSE as the centralized optimum. Second, we describe and analyze a decentralized protocol based on only a single bit (k = 1) of feedback. For step sizes independent of m, it achieves an asymptotic MSE of order O(1/nradicm), whereas for step sizes decaying as m-1/2, it achieves the same order of MSE - namely, O(1/nm) - as the centralized optimum. We discuss the tradeoffs between these different protocols

In recent years, there has been a lot of interest in using wireless local area networks (WLAN) for voice communications with the expanded coverage of hot spots. This paper describes packet aggregation method that increases the throughput of WLAN for voice communication by decreasing the overhead of backoff at the beginning of each packet transmission. Aggregation allows AP to acquire the channel and send its packets inside a multicast packet or back-to-back. Implementation and analysis of frame aggregation show that it improves the performance of voice over IP (VoIP) operating on IEEE 802.11 considerably

We study the use of multi-cast probes to infer network internal loss behavior from losses observed in multi-cast receivers. First part of the paper analyzes the estimation problem based on the assumption that there is no temporal correlation between link losses for different probes. We have applied expectation-maximization (EM) algorithm to this problem. We compared the results of EM with a direct approach developed in R. Cacerer et al. (1999). The second part of the paper is based on the assumption of Markov temporal correlation between packet losses. We applied EM algorithm to this problem with E-step approximated by Gibbs sampling, completely factorized variational and structured variational approximation. We observed from simulation that the links closer to observed nodes give more accurate results and that structured variational approximation improves simple variational approximation results considerably

We use game theoretic models to show the lack of incentives in the transport control protocol congestion avoidance algorithm and the consequential system-wide network problems. We then propose a Vickery-Clark-Groves (VCG) mechanism-based access control mechanism for packet traffic. Our mechanism is called "smart pay access control (SPAC)". We prove both the incentive compatibility and individual rationality of SPAC, which achieves Pareto efficient allocation of network resource. The computing problems are NP-hard for the general VCG mechanism, whereas our mechanism computes the winner's determination problem as fast as a sorting algorithm. The speed of SPAC makes it feasible for the real world usage. As a positive side effect, the mechanism provides the base for a pricing scheme, which we present in the context of the differentiated service architecture for the Internet.

PEDAMACS is a Time Division Multiple Access (TDMA) scheme that extends the common single hop TDMA to a multihop sensor network, using a high-powered access point to synchronize the nodes and to schedule their transmissions and receptions. The protocol first enables the access point to gather topology (connectivity) information. A scheduling algorithm then determines when each node should transmit and receive data, and the access point announces the transmission schedule to the other nodes. The performance of PEDAMACS is compared to existing protocols based on simulations in TOSSIM, a simulation environment for TinyOS, the operating system for the Berkeley sensor nodes. For the traffic application we consider, the PEDAMACS network provides a lifetime of several years compared to several months and days based on random access schemes with and without sleep cycles, respectively, making sensor network technology economically viable.

The problem of computing bandwidth guaranteed paths for given flow requests in an ad-hoc network is complicated because neighboring links share the medium. We define the path width on top of the conflict-graph based interference model, and present the ad-hoc shortest widest path (ASWP) routing problem in an ad-hoc network context. We propose a distributed algorithm to address the ASWP problem. Adopting the Bellman-Ford architecture and the k-shortest-path approach, the proposed algorithm achieves a performance close to the optimum. Numerical simulations demonstrate the performance of the algorithm, and also analyze gains achieved over prevalent shortest-path algorithms.

We present a method to determine the throughput of an extended service set in an IEEE 802.11 network. The method combines two tools. The first tool takes the location of access points and a floor plan and uses an RF propagation model to predict the spatial distribution of SNR and interference that mobile stations will experience. The second tool takes the SNR of mobile stations and predicts system throughput, based on an analytical Markov chain model. The method can help to intelligently plan WLAN deployment.

We extend the probably approximately correct (PAC) model of learning to Markov decision processes (MDPs) and dynamic games. We obtain simulation-based uniform sample complexity bounds for value function estimates of discounted reward MDPs. We also obtain uniform sample complexity results for Markov games with a finite number of players.

A game theoretic pricing mechanism for statistically guaranteed service in packet-switched networks is proposed. The mechanism provides congestion control, differentiated qualities of service, and efficient resource allocation. For users, the mechanism offers better quality and lower price. Service providers can base new service and revenue models within the mechanism. We apply this mechanism to the Internet.

We propose a power efficient system architecture that exploits the characteristics of sensor networks in order to decrease the power consumption in the network. The primary characteristic of sensor networks is that the destination of all the data packets in the network is a central data collector, which is usually denoted as access point (AP), has unlimited transmission power and energy whereas the sensor nodes have one battery energy to remain alive fro several years. Our system uses the AP to directly synchronize and explicitly schedule the nodes' transmissions over time division multiple access (TDMA) time slots. Simulations performed in TOSSIM, a simulation environment for the TinyOS, show that the battery lifetime of the network with this scheme can be increased to 1-2 years from 10 days that can be obtained from a general random access network.

The paper presents the performance advantage of wireless token ring protocol (WTRP) versus IEEE 802.11 in DCF mode. WTRP is a medium access control (MAC) protocol and is designed to provide quality of service in WLANs. WTRP supports guaranteed QoS in terms of bounded latency and reserved bandwidth which are crucial constraints of the real time applications and inapplicable in an IEEE 802.11 network. WTRP is a distributed MAC protocol and partial connection is enough for full connectivity. The stations take turn to transmit and are forced to suspend the transmission after having the medium for a specified amount of time. WTRP is robust against wireless medium imperfections. The DCF mode of IEEE 802.11, also a distributed MAC protocol, is based on contention among stations and is not homogeneous due to the existence of hidden terminals and random behavior. Consequently, QoS is not provided.

In IEEE 802.11 wireless LANs, the DCF access method and the PCF access method operate alternatively within a superframe to service the time-varying traffic demands. Due to different medium access mechanisms deployed by DCF and PCF, they work well for some particular types of traffic scenarios respectively, while their performance may degrade under some other types of traffic demands. None of them can keep high performance under all types of traffic demands. In this paper, we propose an adaptive control algorithm to keep the aggregate throughput of access points close to the best capacity of both DCF mode and PCF mode upon various traffic requests, by dynamically adjusting the duration of DCF mode and PCF mode within a superframe based on recent traffic scenarios in wireless LANs. We modified the MAC module of IEEE 802.11 wireless LANs in OPNET to support our algorithm. Extensive simulations have been done using OPNET. The simulation results show that high performance of access points is achieved during the dynamic traffic demands. The new control algorithm only requires simple extensions to the MAC layer of access points and is compatible with the MAC layer defined in IEEE 802.11 standard.

Describes the design of an automated highway system (AHS) developed over the past ten years in the California PATH program. The AHS is a large, complex system, in which vehicles are automatically controlled. The design and implementation of the AHS required advances in actuator and sensor technologies, as well as the design, analysis, simulation, and testing of large-scale, hierarchical hybrid control systems. The paper focuses on the multilayer AHS control architecture and some questions of implementation. It discusses in detail the design and safety verification of the on-board vehicle control system and the design of the link-layer traffic-flow controller.

The proliferation of electronic commerce has emphasized \nthe need for multiple qualities of service (QoS) that meet \nuser requirements for, e.g., best-eort services, transactional \nguarantees, prioritized services, and bandwidth reservations. \nWhen Internet users will be able to choose from a large selection \nof network services, an important question is whether \nthis \nexibility will be appreciated by the user and how much \nvalue is placed on network resources. This paper focuses on \nuser acceptance of dierent usage-based pricing models for \nnetwork services as well as on which users benet from dynamic \npricing. The analytic results presented here are based \non pricing experiments conducted within the INternet Demand \nEXperiment (INDEX). The pricing experiments comprise \nper-minute and byte-volume pricing. After describing \nthe experimental design and characterizing our subject pool \nusing demographic data, we analyze user demand for Internet \naccess by comparing the three experiments in terms of \ntraÆc generation, QoS selection, and expenditure. Finally, \nwe show which user groups will benet from such services.

Hybrid automata model systems with both digital and analog components, such as embedded control programs. Many verification tasks for such programs can be expressed as reachability problems for hybrid automata. By improving on previous decidability and undecidability results, we identify a boundary between decidability and undecidability for the reachability problem of hybrid automata. On the positive side, we give an (optimal) PSPACE reachability algorithm for the case of initialized rectangular automata, where all analog variables follow independent trajectories within piecewise-linear envelopes and are reinitialized whenever the envelope changes. Our algorithm is based on the construction of a timed automaton that contains all reachability information about a given initialized rectangular automaton. The translation has practical significance for verification, because it guarantees the termination of symbolic procedures for the reachability analysis of initialized rectangular automata. The translation also preserves theω-languages of initialized rectangular automata with bounded nondeterminism. On the negative side, we show that several slight generalizations of initialized rectangular automata lead to an undecidable reachability problem. In particular, we prove that the reachability problem is undecidable for timed automata augmented with a single stopwatch.

We obtain the Shannon capacity of a fading channel with channel side information at the transmitter and receiver, and at the receiver alone. The optimal power adaptation in the former case is "water-pouring" in time, analogous to water-pouring in frequency for time-invariant frequency-selective fading channels. Inverting the channel results in a large capacity penalty in severe fading.

The finite-state Markov channel (FSMC) is a discrete time-varying channel whose variation is determined by a finite-state Markov process. These channels have memory due to the Markov channel variation. We obtain the FSMC capacity as a function of the conditional channel state probability. We also show that for i.i.d. channel inputs, this conditional probability converges weakly, and the channel's mutual information is then a closed-form continuous function of the input distribution. We next consider coding for FSMCs. In general, the complexity of maximum-likelihood decoding grows exponentially with the channel memory length. Therefore, in practice, interleaving and memoryless channel codes are used. This technique results in some performance loss relative to the inherent capacity of channels with memory. We propose a maximum-likelihood decision-feedback decoder with complexity that is independent of the channel memory. We calculate the capacity and cutoff rate of our technique, and show that it preserves the capacity of certain FSMCs. We also compare the performance of the decision-feedback decoder with that of interleaving and memoryless channel coding on a fading channel with 4PSK modulation.

Hybrid automata model systems with both digital and analog components, such az embedded control programs.Many verification tasks for such programs can be expressed as reachability problems for hybrid automata.By improving on previous decidability and undecidability results, we identify the precise boundary between decidability and undecidability of the reachability problem for hybrid automata.On the positive side, we give an (optimal) PSPACE reachability algorithm for the case of initialized rectangular automata, where all analog variables follow trajectories within piecewise-linear envelopes and are reinitialized whenever the envelope changes.Our algorithm is based on a translation of an initialized rectangular automaton into a timed automaton that defines the same timed language.The translation has practical significance for verification, because it guarantees the termination of symbolic procedures for the reachability analysis of initialized rectangular automata.On the negative side, we show that several slight generalizations of initialized rectangular automata lead to an undecidable reachability problem.In particular, we prove that the reachability problem is undecidable for timed automata with a single stopwatch.

This paper presents a system for billing users for their TCP traffic. This is achieved by postponing the establishment of connections while the user is contacted, verifying in a secure way that they are prepared to pay. By presenting the user with cost and price information, the system can be used for cost recovery and to encourage efficient use of network resources. The system requires no changes to existing protocols or applications and can be used to recover costs between cooperating sites. Statistics collected from a four-day trace of traffic between the University of California, Berkeley, and the rest of the Internet demonstrate that such a billing system is practical and introduces acceptable latency. An implementation based on the BayBridge prototype router is described. Our study also indicates that pricing schemes may be used to control network congestion either by rescheduling time-insensitive traffic to a less expensive time of the day, or by smoothing packet transfers to reduce traffic peaks.>

A model of a power system with load dynamics is studied by investigating qualitative changes in its behavior as the reactive power demand at a load bus is increased. In addition to the saddle node bilification often associated with voltage collapse, the power system exhibits sub- and supercritical Hopf bifurcations, cyclic fold bifurcation, and period doubling bifurcation. Cascades of period doubling bifurcation terminate in chaotic invariant sets. The presence of these new bifurcations motivates a reexamination of the saddle-node bifurcation as the boundary of the feasible set of power injections.

The authors propose a microeconomic approach to service provisioning in ATM networks. The provisioning procedure consists of two algorithms, one executed by the network and the other by individual users. The network offers directly for rent its bandwidth and buffers. Users purchase freely resources to meet their desired quality based on their own traffic parameters and delay requirements. The network periodically adjusts resource prices based on user requests monitored in the previous period. They describe the networks adjustment scheme and users' decision rule, and show that under the proposed price adjustment scheme, in order to minimize their own service cost, individual users will indeed request amounts of resources that optimize a measure of overall network performance. Since this approach does not require the network to know user traffic and delay parameters, it does not mandate traffic policing on the part of the network.>

The authors model an ATM virtual circuit as a tandem queueing system. At each queue, transmission of the virtual circuit traffic is interrupted by cross traffic, causing the scattering and coalescing of cells. They study this phenomenon using entropy as a traffic descriptor. They compute the entropy of traffic streams produced in simulation, via an estimation technique based on the Lempel-Ziv universal data compression method. The estimator modifies the Lempel-Ziv method to compute entropy rather than compress data. They show that the entropy of virtual circuit traffic at successive queues can either increase or decrease depending upon the types of input traffic. Even when bursty input is scattered, its entropy does not achieve maximum entropy within a reasonable number of queues. They also define a distance metric to compare the correlation structures of two output processes and observe this metric at successive queue outputs.>

The merging of telephone and computer networks is introducing multiple resources into networks, and information is becoming increasingly distributed across the network. Related services are being integrated onto a single network rather than being offered on separate uncoordinated networks. The authors focus upon communication networks that integrate multiple services using multiple resources. In particular, they look at the decision of whether to accept or deny service requests in such a system. They prove a conjecture for the optimal policy for a related system introduced in Foschini and Gopinath (1983) and characterize the optimal coordinate convex policy for the present multiple service, multiple resource system.>

An exact analysis of the dynamic behavior of IGRP, an adaptive shortest-path routing algorithm, is performed. The distance metric is a weighted sum of traffic-sensitive and traffic-insensitive delay components. The optimality and stability of the protocol is related to the ratio of the weights. In particular, it is shown that if the traffic-sensitive component is not given enough weight, then starting from any initial routing, the subsequent routings after finitely many update periods will oscillate between two worst cases. Otherwise, the successive routings will converge to the unique equilibrium routing. It is also shown that load sharing among routes whose distances are within a threshold of the minimum distance helps stabilize the dynamic behavior.>

A framework for studying a stream of traffic or a message as it is transferred over an asynchronous transfer mode (ATM) connection was previously proposed by the authors (1991). A message is modeled as a deterministic fluid flow, and an ATM node is modeled as a server that allocates bandwidth among concurrent messages. The key concept is that of the burstiness curve of an incoming message, which gives the buffer size needed if the message is served at rate mu . It is shown there that the fixed rate, the leaky bucket, and the affine server are burst reducing. The burstiness bound for each of these servers is presented. A sequence of identical affine servers is related to a fixed rate server, and it is suggested how quality-of-service parameters can usefully be based on the burstiness curve.>

A system which uses multiple asynchronous transfer mode (ATM) virtual circuits operating in parallel in order to control two WAN hosts at gigabit speeds is studied. Packets in parallel channels can bypass each other, so reordering of packets before delivery to the host is required. Performance parameters of this system, including ATM channel delay, packet loss, and resequencing delay, are analyzed, using a model for an ATM channel that multiplexes ATM virtual circuits carrying bursty and nonbursty traffic. It is found that the mean and variance of packet delay through an ATM switch grow linearly with burst size, and that the delay distribution can be closely approximated by a normal distribution. It is shown that packet loss is log-linear in the ratio of buffer size to burst size, and for maximum bursts larger than 50 cells, a buffer size of twice the maximum burst size is sufficient to achieve packet loss probabilities less than 10/sup -9/. Resequencing delay is shown to be insensitive to burst size, but the variance is large and grows linearly with burst size.>

The cell loss suffered by a data stream in an asynchronous transfer mode (ATM) network is studied using its loss function L( mu , beta ). This is the number of cells lost if the stream were allocated a transmission bandwidth of mu cells per second and a buffer of beta cells. Properties of the loss function are derived. Two popular allocation schemes are studied: the fixed-rate-fixed-buffer scheme and the leaky bucket scheme. An example suggests how the loss function might be used to relate pricing of bandwidth and buffer resources to the resulting cell loss.>

The authors formulate and solve a problem of allocating resources among competing services differentiated by user traffic characteristics and maximum end-to-end delay. The solution leads to an alternative approach to service provisioning in an ATM network, in which the network offers directly for rent its bandwidth and buffers and users purchase freely resources to meet their desired quality. Users make their decisions based on their own traffic parameters and delay requirements and the network sets prices for those resources. The procedure is iterative in that the network periodically adjusts prices based on monitored user demand, and is decentralized in that only local information is needed for individual users to determine resource requests. The authors derive the network's adjustment scheme and the users' decision rule and establish their optimality. Since the approach does not require the network to know user traffic and delay parameters, it does not require traffic policing on the part of the network.>

The authors focus upon communication networks that integrate multiple services using multiple resources. In particular, the authors address the decision of whether to accept or deny service requests in such a system. A conjecture for the optimal policy for a related system introduced by G.J. Foschini and B. Gopinath (1983) is proved, and the optimal coordinate convex policy for a multiple service, multiple resource system is characterized.>

Communication networks that integrate multiple services using multiple resources are considered. In particular, the authors pose resource allocation problems, present a sensitivity analysis, and provide a glimpse of the possible behavior of such networks. The simplest discipline is assumed: a service request is accepted if the necessary resources are available; otherwise it is rejected. Two results are obtained. The first gives the sensitivity of throughput of service requests of type i with respect to offered traffic and service rates of type j. The second result is that the set of vectors of achievable throughput rates is a convex polyhedron given by an explicit set of linear inequalities.>

The Programmable Network Prototyping System (PNPS), which is a rapid-prototyping tool used for emulating a wide variety of communication networks, is discussed. There are two parts to the PNPS hardware: the reusable hardware modules and the control and observation system. The reusable hardware modules consist of a channel emulator and a collection of node emulators. The channel emulator can be programmed to behave like a variety of network topologies, and each node emulator is configured to behave like a node on a network under study. The control and observation system links these modules together for configuration, experimentation, and monitoring purposes. There are three phases to using PNPS. first, the various components of a proposed network are designed. Next, the components are combined and run on the hardware while its behavior is monitored. Finally, the monitoring data is analyzed in order to evaluate the network design. A menu-driven user interface guides the user through the various tools of the system.>

The authors consider discrete event models (DEMs) that describe logical system behavior, i.e. mathematical models that represent the set of traces of sequences of events that the system can execute. Examples of DEM formalisms include state machines, Petri nets, and Hoare's communicating sequential processes. All these formalisms are algebras, i.e. a set of models together with operators that combine models to form other models in ways in which real systems are interconnected. A general approach toward constructing model algebras is proposed. The approach covers both deterministic and nondeterministic models, and it can be tailored to recover existing formalisms and to obtain model families.>

Transient stability analysis of a power system is concerned with the system's ability to remain in synchronism following a disturbance. In utility planning, transient stability is studied by numerical simulation. The long CPU run times for simulation preclude their use for on-line security analysis. Interest has therefore shifted toward the Lyapunov direct method of stability analysis. This paper provides a critical review of research on direct methods since 1970. Considerable progress has been made on both theoretical properties of energy functions and on criteria suitable for on-line implementation. Current theory provides a satisfactory treatment of voltage-dependent reactive power demand, transfer conductances, and flux decay. However, it cannot incorporate the exciter control Proposed on-line criteria appear to work very well on sample examples; but, they still lack rigorous justification. Finally, recent work has shown that power systems can exhibit chaotic behavior. This surprising fact demonstrates that our understanding of the dynamics of power systems remains incomplete.

The symbols produced by a finite Markov source are causally encoded so as to be transmitted through a noisy memoryless channel. The encoder is assumed to have channel feedback information and the decoder to be causal. The feedback information is shown to be useful in general. Separation results are derived and used to prove that encoding is useless for a class of symmetric channels.

A group of new experiments which we have performed using Forrester's model are presented: a study of rent control, effects of changing key parameters, and a study of changing labor requirements which explores the implications of exogenous variables for the model. A second section presents specific criticisms of Forrester's model, an economic evaluation of the model, and ends with some general remarks concerning validation and extension of large models. In order to make this paper accessible to a wide audience, the paper begins with a tutorial description of Forrester's work.