This thesis investigates designs that enable individual components of a distributed system to work together and coordinate their actions towards a common goal. While the basic motivation for our research is to develop engineering principles for large-scale autonomous systems, we address the problem in the context of resource management in server clusters that provide web services. To this end, we have developed, implemented and evaluated a decentralized design for resource management that follows four principles. First, in order to facilitate scalability, each node has only partial knowledge of the system. Second, each node can adapt and change its role at runtime. Third, each node runs a number of local control mechanisms independently and asynchronously from its peers. Fourth, each node dynamically adapts its local configuration in order to optimize a global utility function. The design includes three fundamental building blocks: overlay construction, request routing and application placement. Overlay construction organizes the cluster nodes into a single dynamic overlay. Request routing directs service requests towards nodes with available resources. Application placement partitions the cluster resources between applications, and dynamically adjusts the allocation in response to changes in external load, node failures, etc. We have evaluated the design using complexity analysis, simulation and prototype implementation. Using complexity analysis and simulation, we have shown that the system is scalable, operates efficiently in steady state, quickly adapts to external events and allows for effective service differentiation by a system administrator. A prototype has been built using accepted technologies (Java, Tomcat) and evaluated using standard benchmarks (TPC-W and RUBiS). The evaluation results show that the behavior of the prototype matches closely that of the simulated design for key metrics related to adaptability and robustness, therefore validating our design and proving its feasibility. / QC 20100629

The Transmission Control Protocol (TCP) has successfully governed the Internet congestion control for two decades. It is by now, however, widely recognized that TCP has started to reach its limits and that new congestion control protocols are needed in the near future. This has spurred an intensive research effort searching for new congestion control designs that meet the demands of a future Internet scaled up in size, capacity and heterogeneity. In this thesis we derive network fluid flow models suitable for analysis and synthesis of window based congestion control protocols such as TCP. In window based congestion control the transmission rate of a sender is regulated by: (1) the adjustment of the so called window, which is an upper bound on the number of packets that are allowed to be sent before receiving an acknowledgment packet (ACK) from the receiver side, and (2) the rate of the returning ACKs. From a dynamical perspective, this constitutes a cascaded control structure with an outer and an inner loop. The first contribution of this thesis is a novel dynamical characterization and an analysis of the inner loop, generic to all window based schemes and formed by the interaction between the, so called, ACK-clocking mechanism and the network. The model is based on a fundamental integral equation relating the instantaneous flow rate and the window dynamics. It is verified in simulations and testbed experiments that the model accurately predicts dynamical behavior in terms of system stability, previously unknown oscillatory behavior and even fast phenomenon such as traffic burstiness patterns present in the system. It is demonstrated that this model is more accurate than many of the existing models in the literature. In the second contribution we consider the outer loop and present a detailed fluid model of a generic window based congestion control protocol using queuing delay as congestion notification. The model accounts for the relations between the actual packets in flight and the window size, the window control, the estimator dynamics as well as sampling effects that may be present in an end-to-end congestion control algorithm. The framework facilitates modeling of a quite large class of protocols. The third contribution is a closed loop analysis of the recently proposed congestion control protocol FAST TCP. This contribution also serves as a demonstration of the developed modeling framework. It is shown and verified in experiments that the delay configuration is critical to the stability of the system. A conclusion from the analysis is that the gain of the ACK-clocking mechanism dramatically increases with the delay heterogeneity for the case of an equal resource allocation policy. Since this strongly affects the stability properties of the system, this is alarming for all window based congestion control protocols striving towards proportional fairness. While these results are interesting as such, perhaps the most important contribution is the developed stability analysis technique. / QC 20100813

This thesis studies some fundamental aspects of wireless systems with partial channel state information at the transmitter (CSIT), with a special emphasis on the high signal-to-noise ratio (SNR) regime. The first contribution is a study on multi-layer variable-rate communication systems with quantized feedback, where the expected rate is chosen as the performance measure. Iterative algorithms exploiting results in the literature of parallel broadcast channels are developed to design the system parameters. Necessary and sufficient conditions for single-layer coding to be optimal are derived. In contrast to the ergodic case, it is shown that a few bits of feedback information can improve the expected rate dramatically. The next part of the thesis is devoted to characterizing the tradeoff between diversity and multiplexing gains (D-M tradeoff) over slow fading channels with partial CSIT. In the multiple-input multiple-output (MIMO) case, we introduce the concept of minimum guaranteed multiplexing gain in the forward link and show that it influences the D-M tradeoff significantly. It is demonstrated that power control based on the feedback is instrumental in achieving the D-M tradeoff, and that rate adaptation is important in obtaining a high diversity gain even at high rates. Extending the D-M tradeoff analysis to decode-and-forward relay channels with quantized channel state feedback, we consider several different scenarios. In the relay-to-source feedback case, it is found that using just one bit of feedback to control the source transmit power is sufficient to achieve the multiantenna upper bound in a range of multiplexing gains. In the destination-to-source-and-relay feedback scenario, if the source-relay channel gain is unknown to the feedback quantizer at the destination, the diversity gain only grows linearly in the number of feedback levels, in sharp contrast to an exponential growth for MIMO channels. We also consider the achievable D-M tradeoff of a relay network with the compress-and-forward protocol when the relay is constrained to make use of standard source coding. Under a short-term power constraint at the relay, using source coding without side information results in a significant loss in terms of the D-M tradeoff. For a range of multiplexing gains, this loss can be fully compensated for by using power control at the relay. The final part of the thesis deals with the transmission of an analog Gaussian source over quasi-static fading channels with limited CSIT, taking the SNR exponent of the end-to-end average distortion as performance measure. Building upon results from the D-M tradeoff analysis, we develop novel upper bounds on the distortion exponents achieved with partial CSIT. We show that in order to achieve the optimal scaling, the CSIT feedback resolution must grow logarithmically with the bandwidth ratio for MIMO channels. The achievable distortion exponent of some hybrid schemes with heavily quantized feedback is also derived. As for the half-duplex fading relay channel, combining a simple feedback scheme with separate source and channel coding outperforms the best known no-feedback strategies even with only a few bits of feedback information. / QC 20100817

This dissertation presents adaptation techniques that can achieve high spectral efficiency for single user multiple-input multiple-output (MIMO) systems. Two types of adaptation techniques, adaptive modulation and adaptive powe allocation, are employed to adapt the rate and the transmit power to fading channels. We start by investigating the adaptive modulation subject to a certain bit-error-ratio (BER) constraint, either instantaneous BER constraint or average BER constraint. The resulting average spectral efficiencies are obtained in closed-form expressions. It turns out that, by employing the average BER constraint, we can achieve the optimal average spectra efficiency at the cost of prohibitive computational complexity. On the other hand, instantaneous BER constraint leads to inferior performance with little computational complexity. In order to achieve comparable performance to the average BER constraint with limited complexity, a non-linear optimization method is proposed. To further enhance the average spectra efficiency, adaptive power allocation schemes are considered to adjust the transmit power across the temporal domain or the spatial domain, depending on the specific situation. Provided the closed-form expressions of the average spectral efficiency, the optimal MIMO coding scheme that offers the highest average spectral efficiency under the same circumstances can be identified. As we take into account the effect of imperfect channel estimation, the adaptation techniques are revised to tolerate interference introduced by the channel estimation errors. As a result, the degradation with respect to the average spectral efficiency is in proportion to signal-to-noise ratio (SNR). In order to facilitate fast development and verification of the adaptation schemes proposed for various MIMO systems, a reconfigurable Link Layer Simulator (LiLaS) which accommodates a variety of wireless/wireline applications is designed in the environment of MATLAB/OCTAVE. The idea of the simulator is originated from Software Defined Radio (SDR) and evolved to suit Cognitive Radio (CR) applications. For the convenience of modification and reconfiguration, LiLaS is functionally divided into generic blocks and all blocks are parameterized. / QC 20100812

Numerous control and decision problems in networked systems can be posed as optimization problems. Examples include the framework of network utility maximization for resource allocation in communication networks, multi-agent coordination in robotics, and collaborative estimation in wireless sensor networks (WSNs). In contrast to classical distributed optimization, which focuses on improving computational efficiency and scalability, these new applications require simple mechanisms that can operate under limited communication. In this thesis, we develop several novel mechanisms for distributed optimization under communication constraints, and apply these to several challenging engineering problems. In particular, we devise three tailored optimization algorithms relying only on nearest neighbor, also known as peer-to-peer, communication. Two of the algorithms are designed to minimize a non-smooth convex additive objective function, in which each term corresponds to a node in a network. The first method is an extension of the randomized incremental subgradient method where the update order is given by a random walk on the underlying communication graph, resulting in a randomized peer-to-peer algorithm with guaranteed convergence properties. The second method combines local subgradient iterations with consensus steps to average local update directions. The resulting optimization method can be executed in a peer-to-peer fashion and analyzed using epsilon-subgradient methods. The third algorithm is a center-free algorithm, which solves a non-smooth resource allocation problem with a separable additive convex objective function subject to a constant sum constraint. Then we consider cross-layer optimization of communication networks, and demonstrate how optimization techniques allow us to engineer protocols that mimic the operation of distributed optimization algorithms to obtain an optimal resource allocation. We describe a novel use of decomposition methods for cross-layer optimization, and present a flowchart that can be used to categorize and visualize a large part of the current literature on this topic. In addition, we devise protocols that optimize the resource allocation in frequency-division multiple access (FDMA) networks and spatial reuse time-division multiple access (TDMA) networks, respectively. Next we investigate some variants of the consensus problem for multi-robot coordination, for which it is usually standard to assume that agents should meet at the barycenter of the initial states. We propose a negotiation strategy to find an optimal meeting point in the sense that the agents' trajectories to the meeting point minimize a quadratic cost criterion. Furthermore, we also demonstrate how an augmented state vector can be used to boost the convergence rate of the standard linear distributed averaging iterations, and we present necessary and sufficient convergence conditions for a general version of these iterations. Finally, we devise a generic optimization software component for WSNs. To this end, we implement some of the most promising optimization algorithms developed by ourselves and others in our WSN testbed, and present experimental results, which show that the proposed algorithms work surprisingly well. / QC 20100813

In mobile speech communication, adverse conditions, such as noisy acoustic environments and unreliable network connections, may severely degrade the intelligibility and natural- ness of the received speech quality, and increase the listening effort. This thesis focuses on countermeasures based on statistical signal processing techniques. The main body of the thesis consists of three research articles, targeting two specific problems: speech enhancement for noise reduction and flexible source coder design for unreliable networks. Papers A and B consider speech enhancement for noise reduction. New schemes based on an extension to the auto-regressive (AR) hidden Markov model (HMM) for speech and noise are proposed. Stochastic models for speech and noise gains (excitation variance from an AR model) are integrated into the HMM framework in order to improve the modeling of energy variation. The extended model is referred to as a stochastic-gain hidden Markov model (SG-HMM). The speech gain describes the energy variations of the speech phones, typically due to differences in pronunciation and/or different vocalizations of individual speakers. The noise gain improves the tracking of the time-varying energy of non-stationary noise, e.g., due to movement of the noise source. In Paper A, it is assumed that prior knowledge on the noise environment is available, so that a pre-trained noise model is used. In Paper B, the noise model is adaptive and the model parameters are estimated on-line from the noisy observations using a recursive estimation algorithm. Based on the speech and noise models, a novel Bayesian estimator of the clean speech is developed in Paper A, and an estimator of the noise power spectral density (PSD) in Paper B. It is demonstrated that the proposed schemes achieve more accurate models of speech and noise than traditional techniques, and as part of a speech enhancement system provide improved speech quality, particularly for non-stationary noise sources. In Paper C, a flexible entropy-constrained vector quantization scheme based on Gaus- sian mixture model (GMM), lattice quantization, and arithmetic coding is proposed. The method allows for changing the average rate in real-time, and facilitates adaptation to the currently available bandwidth of the network. A practical solution to the classical issue of indexing and entropy-coding the quantized code vectors is given. The proposed scheme has a computational complexity that is independent of rate, and quadratic with respect to vector dimension. Hence, the scheme can be applied to the quantization of source vectors in a high dimensional space. The theoretical performance of the scheme is analyzed under a high-rate assumption. It is shown that, at high rate, the scheme approaches the theoretically optimal performance, if the mixture components are located far apart. The practical performance of the scheme is confirmed through simulations on both synthetic and speech-derived source vectors. / QC 20100825

Wireless communication links with multiple antennas at both the transmitter and the receiver sides, so-called multiple-input-multiple-output (MIMO)systems, are attracting much interest since they can significantly increase the capacity of band-limited wireless channels to meet the requirements of the future high data rate wireless communications. The treatment of channel state information (CSI) is critical in the design of MIMO systems. Accurate CSI at the transmitter is often not possible or may require high feedback rates, especially in multi-user scenarios. Herein, we consider the robust design of linear transceivers with imperfect CSI either at the transmitter or at both sides of the link. The framework considers the design problem where the imperfect CSI consists of a channel mean and an channel covariance matrix or, equivalently, a channel estimate and an estimation error covariance matrix. For single-user systems, the proposed robust transceiver designs are based on a general cost function of the average mean square errors. Under different CSI conditions, our robust designs exhibit a similar structure to the transceiver designs for perfect CSI, but with a different equivalent channel and/or noise covariance matrix. Utilizing majorization theory, the robust linear transceiver design can be readily solved by convex optimization approaches in practice. For multi-user systems, we consider both the communication link from the users to the access point (up-link) as well as the reverse link from the access point to the users (down-link). For the up-link channel, it is possible to optimally design robust linear transceivers minimizing the average sum mean square errors of all the data streams for the users. Our robust linear transceivers are designed either by reformulating the optimization problem as a semidefinite program or by extending the design of a single-user system in an iterative manner. Under certain channel conditions, we show that the up-link design problem can even be solved partly in a distributed fashion. For the down-link channel, a system with one receive antenna per user is considered. A robust system design is obtained by reducing the feedback load from all users to allow only a few selected users to feed back accurate CSI to the access point. We study the properties of four typical user selection algorithms in conjunction with beamforming that guarantee certain signal-to-interference-plus-noise ratio (SINR) requirements under transmit power minimization. Specifically, we show that norm-based user selection is asymptotically optimal in the number of transmitter antennas and close-to-optimal in the number of users. Rooted in the practical significance of this result, a simpler down-link system design with reduced feedback requirements is proposed. / QC 20100922

This thesis describes the simulation of the proposed IEEE 802.11p Physical layer (PHY). A MATLAB simulation is carried out in order to analyze baseband processing of the transceiver. Orthogonal Frequency Division Multiplexing (OFDM) is applied in this project according to the IEEE 802.11p standard, which allows transmission data rates from 3 up to 27Mbps. Distinct modulation schemes, Binary Phase Shift Keying (BPSK), Quadrate Phase Shift Keying (QPSK) and Quadrature Amplitude modulation (QAM), are used according to differing data rates. These schemes are combined with time interleaving and a convolutional error correcting code. A guard interval is inserted at the beginning of the transmitted symbol in order to reduce the effect of Intersymbol Interference (ISI). The Viterbi decoder is used for decoding the received signal. Simulation results illustrate the Bit Error Rate (BER), Packet Error Rate (PER) for different channels. Different channel implementations are used for the simulations. In addition a ray-tracing based software tool for modelling time variant vehicular channels is integrated into SIMULINK. BER versus Signal to Noise Ratio (SNR) statistics are as the basic reference for the physical layer of the IEEE 802.11p standard for all vehicular wireless network simulations.

The GSM network technology has been developed and improved during several years which have led to an increased complexity. The complexity results in more network parameters and together with different scenarios and situations they form a complex set of configurations. The definition of the network parameters is generally a manual process using static values during test execution. This practice can be costly, difficult and laborious and as the network complexity continues to increase, this problem will continue to grow.This thesis presents an implementation of an automated performance optimization algorithm that utilizes genetic algorithms for optimizing the network parameters. The implementation has been used for proving that the concept of automated optimization is working and most of the work has been carried out in order to use it in practice. The implementation has been applied to the Link Quality Control algorithm and the Improved ACK/NACK feature, which is an apart of GSM EDGE Evolution. / GSM-nätsteknologin har utvecklats och förbättrats under lång tid, vilket har lett till en ökad komplexitet. Denna ökade komplexitet har resulterat i fler nätverksparameterar, tillstånd och standarder. Tillsammans utgör de en komplex uppsättning av olika konfigurationer. Dessa nätverksparameterar har hittills huvudsakligen bestämts med hjälp av en manuell optimeringsprocess. Detta tillvägagångssätt är både dyrt, svårt och tidskrävande och allt eftersom komplexiteten av GSM-näten ökar kommer problemet att bli större.Detta examensarbete presenterar en implementering av en algoritm för automatiserad optimering av prestanda som huvudsakligen använder sig av genetiska algoritmer för att optimera värdet av nätverksparametrarna. Implementeringen har använts för att påvisa att konceptet med en automatiserad optimering fungerar och det mesta av arbetet har utförts för att kunna använda detta i praktiken. Implementeringen har tillämpats på Link Quality Control-algoritmen och Improved ACK/NACK-funktionaliteten, vilket är en del av GSM EDGE Evolution.

The wide spread use of IEEE Wireless LAN 802.11 in battery operated mobile devices introduced the need of power consumption optimization while meeting Quality-of-Service (QoS) requirements of applications connected through the wireless network. The IEEE 802.11 standard specifies a baseline power saving mechanism, hereafter referred to as standard Power Save Mode (PSM), and the IEEE 802.11e standard specifies the Automatic Power Save Delivery (APSD) enhancement which provides support for real-time applications with QoS requirements. The latest amendment to the WLAN 802.11 standard is the IEEE 802.11n standard which enables the use of much higher data rates by including enhancements in the Physical and MAC Layer. In this thesis, different 802.11n MAC power saving and QoS optimization possibilities are analyzed comparing against existing power saving mechanisms. Initially, the performance of the existing power saving mechanisms PSM and Unscheduled-APSD (UAPSD) are evaluated using the 802.11n process model in the OPNET simulator and the impact of frame aggregation feature introduced in the MAC layer of 802.11n was analyzed on these power saving mechanisms. From the performance analysis it can be concluded that the frame aggregation will be efficient under congested network conditions. When the network congestion level increases, the signaling load in UAPSD saturates the channel capacity and hence results in poor performance compared to PSM. Since PSM cannot guarantee the minimum QoS requirements for delay sensitive applications, a better mechanism for performance enhancement of UAPSD under dynamic network conditions is proposed. The functionality and performance of the proposed algorithm is evaluated under different network conditions and using different contention settings. From the performance results it can be concluded that, by using the proposed algorithm the congestion level in the network is reduced dynamically thereby providing a better power saving and QoS by utilizing the frame aggregation feature efficiently.