Spelling suggestions: "subject:"worstcase analysis"" "subject:"worstcases analysis""
1 |
Survivable Networks, Linear Programming Relaxations and the Parsimonious PropertyGoemans, Michel X., Bertsimas, Dimitris J. 06 1900 (has links)
We consider the survivable network design problem - the problem of designing, at minimum cost, a network with edge-connectivity requirements. As special cases, this problem encompasses the Steiner tree problem, the traveling salesman problem and the k-connected network design problem. We establish a property, referred to as the parsimonious property, of the linear programming (LP) relaxation of a classical formulation for the problem. The parsimonious property has numerous consequences. For example, we derive various structural properties of these LP relaxations, we present some algorithmic improvements and we perform tight worstcase analyses of two heuristics for the survivable network design problem.
|
2 |
Influence of Customer Locations on Heuristics and Solutions for the Vehicle Routing ProblemTilashalski, Melissa Christine 07 July 2023 (has links)
The vehicle routing problem (VRP) determines preferred vehicle routes to visit multiple customer locations from a depot location based on a defined objective function. The VRP is an NP-hard network optimization problem that is challenging to solve to optimality. Over the past 60 years, multitudes of heuristics and metaheuristics have been developed in order to minimize the computational burden of solving the VRP. In order to compare the performance of VRP heuristics, researchers have developed bench-marking datasets. These datasets, however, lack properties found in industry datasets.
In this dissertation, we explore how properties of industry datasets influence VRP heuristics and objective functions. In Chapter 2, we quantify and compare features of bench-marking and industry datasets. In order to determine if these features influence heuristic performance, we conduct extensive computational runs on three heuristics, Tabu Search, Genetic Algorithm, and Clarke-Wright Savings Procedure, on standard and industry datasets. In Chapter 3, we derive worst-case analysis on how VRP objective functions and metrics relate to one another. These bounds depend on properties of customer locations. These bounds illustrate how customer locations can influence how different routes behave for different routing metrics. Finally, in Chapter 4, we improve two VRP heuristics, Clarke-Wright Saving Procedure and Hybrid Genetic Search Algorithm, by developing new enhancements to the algorithms. These enhancements rely on certain properties of the datasets in order to perform well. Thus, these heuristics perform better on specific VRP dataset types. / Doctor of Philosophy / The vehicle routing problem (VRP) creates vehicle routes that have the shortest travel distance. The routes determine how vehicles should visit multipl customer locations, to deliver or pickup goods, and return to a depot location. While explaining what the VRP entails is simple, the VRP is actually very difficult for even the most sophisticated algorithms on the best computers to solve. Over the past 60 years, many algorithms have been developed in order to more easily and quickly solve the VRP. In order to compare the performance of VRP algorithms, researchers have developed bench-marking datasets. However, these datasets lack properties of datasets found in industry. In this dissertation, we look to connect the disconnect between industry and bench-marking datasets by 1) comparing feature differences between these two types of datasets, 2) determining if differences in datasets imply differences in algorithm performance, 3) proving how problem differences influence VRP routes, and 4) enhancing existing VRP algorithms to perform better on specific VRP dataset types.
|
3 |
Robust Control Design and Analysis for Small Fixed-Wing Unmanned Aircraft Systems Using Integral Quadratic ConstraintsPalframan, Mark C. 29 July 2016 (has links)
The main contributions of this work are applications of robust control and analysis methods to complex engineering systems, namely, small fixed-wing unmanned aircraft systems (UAS). Multiple path-following controllers for a small fixed-wing Telemaster UAS are presented, including a linear parameter-varying (LPV) controller scheduled over path curvature. The controllers are synthesized based on a lumped path-following and UAS dynamic system, effectively combining the six degree-of-freedom aircraft dynamics with established parallel transport frame virtual vehicle dynamics. The robustness and performance of these controllers are tested in a rigorous MATLAB simulation environment that includes steady winds, turbulence, measurement noise, and delays. After being synthesized off-line, the controllers allow the aircraft to follow prescribed geometrically defined paths bounded by a maximum curvature. The controllers presented within are found to be robust to the disturbances and uncertainties in the simulation environment. A robust analysis framework for mathematical validation of flight control systems is also presented. The framework is specifically developed for the complete uncertainty characterization, quantification, and analysis of small fixed-wing UAS. The analytical approach presented within is based on integral quadratic constraint (IQC) analysis methods and uses linear fractional transformations (LFTs) on uncertainties to represent system models. The IQC approach can handle a wide range of uncertainties, including static and dynamic, linear time-invariant and linear time-varying perturbations. While IQC-based uncertainty analysis has a sound theoretical foundation, it has thus far mostly been applied to academic examples, and there are major challenges when it comes to applying this approach to complex engineering systems, such as UAS. The difficulty mainly lies in appropriately characterizing and quantifying the uncertainties such that the resulting uncertain model is representative of the physical system without being overly conservative, and the associated computational problem is tractable. These challenges are addressed by applying IQC-based analysis tools to analyze the robustness of the Telemaster UAS flight control system. Specifically, uncertainties are characterized and quantified based on mathematical models and flight test data obtained in house for the Telemaster platform and custom autopilot. IQC-based analysis is performed on several time-invariant H∞ controllers along with various sets of uncertainties aimed at providing valuable information for use in controller analysis, controller synthesis, and comparison of multiple controllers. The proposed framework is also transferable to other fixed-wing UAS platforms, effectively taking IQC-based analysis beyond academic examples to practical application in UAS control design and airworthiness certification. IQC-based analysis problems are traditionally solved using convex optimization techniques, which can be slow and memory intensive for large problems. An oracle for discrete-time IQC analysis problems is presented to facilitate the use of a cutting plane algorithm in lieu of convex optimization in order to solve large uncertainty analysis problems relatively quickly, and with reasonable computational effort. The oracle is reformulated to a skew-Hamiltonian/Hamiltonian eigenvalue problem in order to improve the robustness of eigenvalue calculations by eliminating unnecessary matrix multiplications and inverses. Furthermore, fast, structure exploiting eigensolvers can be employed with the skew-Hamiltonian/Hamiltonian oracle to accurately determine critical frequencies when solving IQC problems. Applicable solution algorithms utilizing the IQC oracle are briefly presented, and an example shows that these algorithms can solve large problems significantly faster than convex optimization techniques. Finally, a large complex engineering system is analyzed using the oracle and a cutting-plane algorithm. Analysis of the same system using the same computer hardware failed when employing convex optimization techniques. / Ph. D.
|
4 |
Optimization Techniques for Performance and Power Dissipation in Test and ValidationJayaraman, Dheepakkumaran 01 May 2012 (has links)
The high cost of chip testing makes testability an important aspect of any chip design. Two important testability considerations are addressed namely, the power consumption and test quality. The power consumption during shift is reduced by efficiently adding control logic to the design. Test quality is studied by determining the sensitization characteristics of a path to be tested. The path delay fault models have been used for the purpose of studying this problem. Another important aspect in chip design is performance validation, which is increasingly perceived as the major bottleneck in integrated circuit design. Given the synthesizable HDL code, the proposed technique will efficiently identify infeasible paths, subsequently, it determines the worst case execution time (WCET) in the HDL code.
|
5 |
Online algoritmy pro varianty bin packingu / Online algorithms for variants of bin packingVeselý, Pavel January 2014 (has links)
An online algorithm must make decisions immediately and irrevocably based only on a part of the input without any knowledge of the future part of the input. We introduce the competitive analysis of online algorithms, a standard worst-case analysis, and present main results of this analysis on the problem of online Bin Packing and on some of its variants. In Bin Packing, a sequence of items of size up to 1 arrives to be packed into the minimal number of unit capacity bins. Mainly, we focus on Colored Bin Packing in which items have also a color and we cannot pack two items of the same color adjacently in a bin. For Colored Bin Packing, we improve some previous results on the problem with two colors and present the first results for arbitrarily many colors. Most notably, in the important case when all items have size zero, we give an optimal 1.5-competitive algorithm. For items of arbitrary size we present a lower bound of 2.5 and a 3.5-competitive algorithm. Powered by TCPDF (www.tcpdf.org)
|
6 |
Projeto e análise de aplicações de circuladores ativos para a operação em frequências de ultrassom Doppler de ondas contínuas / Design and application analysis of active circulators for operation in frequencies of continuous-wave Doppler ultrasoundSantini, Tales Roberto de Souza 11 July 2014 (has links)
Os circuladores tradicionais são amplamente utilizados em telecomunicações e defesa militar para o simultâneo envio e recepção de sinais por um único meio. Esses circuitos passivos, fabricados a partir de materiais ferromagnéticos, possuem a desvantagem do aumento de dimensões, peso e custos de fabricação com a diminuição da frequência de operação definida no projeto destes dispositivos, inviabilizando sua aplicação em frequências abaixo de 500 MHz. O circulador ativo surgiu como uma alternativa aos tradicionais, tendo aplicações em frequências desde o nível DC até a ordem de dezenas de gigahertz. As suas maiores aplicações ocorrem quando são necessários dispositivos compactos, de baixo custo e de baixa potência. Os primeiros circuitos propostos possuíam uma grande limitação em termos de frequência de operação e de potência entregue à carga. Entretanto, com os avanços tecnológicos na eletrônica, tais problemas podem ser amenizados atualmente. Neste trabalho é apresentado o desenvolvimento de um circuito circulador ativo para a utilização em instrumentação eletrônica, em particular para a operação em frequências na ordem das utilizadas em equipamentos de ultrassom Doppler de ondas contínuas, na faixa de 2 MHz a 10 MHz. As possíveis vantagens da implementação de circuladores em sistemas de ultrassom estão relacionadas ao incremento da relação sinal-ruído, aumento da área de recepção do transdutor, simplificação da construção do transdutor, simplificação do circuito de demodulação/ processamento, e maior isolação entre os circuitos de transmissão e recepção de sinais. Na fase inicial, o circulador ativo proposto é modelado por equacionamento, utilizando-se tanto o modelo ideal dos amplificadores operacionais como o seu modelo de resposta em frequência. Simulações computacionais foram executadas para confirmar a validade do equacionamento. Um circuito montado em placa de prototipagem rápida foi apresentado, e testes de prova de conceito em baixas frequências foram realizados, mostrando uma grande semelhança entre o teórico, o simulado e o experimental. A segunda parte contou com o projeto do circuito circulador para a operação em maiores frequências. O circuito proposto é composto por três amplificadores operacionais de realimentação por corrente e vários componentes passivos. Uma análise de sensibilidade utilizando os métodos de Monte-Carlo e análise do pior caso foi aplicada, resultando em um perfil de comportamento frente às variações dos componentes do circuito e às variações da impedância de carga. Uma placa de circuito impressa foi projetada, utilizando-se de boas práticas de leiaute para a operação em altas frequências. Neste circuito montado, foram realizados os seguintes testes e medições: comportamento no domínio do tempo, faixa dinâmica, nível de isolação em relação à amplitude do sinal, largura de banda, levantamento dos parâmetros de espalhamento, e envio e recepção de sinais por transdutor de ultrassom Doppler de ondas contínuas. Os resultados dos testes de desempenho foram satisfatórios, apresentando uma banda de transmissão de sinais para frequências de 100 MHz, isolação entre portas não consecutivas de 39 dB na frequência de interesse para ultrassom Doppler e isolação maior que 20 dB para frequências de até 35 MHz. A faixa dinâmica excedeu a tensão de 5 Vpp, e o circuito teve bom comportamento no envio e na recepção simultânea de sinais pelo transdutor de ultrassom. / Traditional circulators are widely used in both telecommunications and military defense for sending and receiving signals simultaneously through a single medium. These passive circuits which are manufactured from ferromagnetic materials, have the disadvantages of having suffered an increase in dimensions, weight, and manufacturing costs along with the decrease in the operation frequency established in the designs of such devices, thus preventing their useful employment in frequencies below 500 MHz. The active circulator emerged as an alternative to the traditional ones, and has applications on frequencies ranging from a DC level to levels involving dozens of gigahertz. It is applicable when compact devices are made necessary, at a low cost, and for low frequencies. The first circuits to be introduced had a major limitation in terms of operating frequency and power delivered to the load. However, due to technological advances in electronics, problems such as the aforementioned can now be minimized. This research work presents the development of an active circulator circuit to be used in electronic instrumentation, particularly for operation at frequencies such as those used in continuous wave Doppler ultrasound equipment, ranging from 2 MHz to 10 MHz. The advantages made possible by implementing ultrasound systems with circulators are related to an increase in the signal-to-noise ratio, an increase in the transducers reception area, a simplified construction of the transducer, simplification of the demodulation/processing circuit, and a greater isolation between the transmission circuits and signal reception. In the initial phase, the proposed active circulator was modeled by means of an equating method, using both the ideal model of operational amplifiers and the model of frequency response. Computer simulations were carried out in order to confirm the validity of the equating method. A circuit mounted upon a breadboard was introduced and proof of concept assessments were performed at low frequencies, showing a great similarity among the theoretical, simulated and experimented data. The second phase is when the circulator circuits design was developed in order make its operation at higher frequencies possible. The proposed circuit is comprised of three currentfeedback operational amplifiers and several passive components. A sensitivity analysis was carried out using Monte-Carlo methods and worst-case analyses, resulting in a certain behavioral profile influenced by variations in circuit components and variations in load impedance. A printed circuit board was designed, employing good practice layout standards so that operation at high frequencies would be achieved. The following evaluations and measurements were performed on the circuit that was assembled: time domain behavior, dynamic range, isolation level relative to signal amplitude, bandwidth, survey of the scattering parameters, and transmission and reception of signals by a continuous wave Doppler ultrasound transducer. The results of the performance tests were satisfactory, presenting a 100 MHz signal transmission band, isolation between non-consecutive ports of 39 dB at the frequency of interest to the Doppler ultrasound, and an isolation greater than 20 dB for frequencies of up to 35 MHz. The dynamic range exceeded the 5Vpp and the circuit performed satisfactorily in the simultaneous transmission and reception of signals through the ultrasound\'s transducer.
|
7 |
Projeto e análise de aplicações de circuladores ativos para a operação em frequências de ultrassom Doppler de ondas contínuas / Design and application analysis of active circulators for operation in frequencies of continuous-wave Doppler ultrasoundTales Roberto de Souza Santini 11 July 2014 (has links)
Os circuladores tradicionais são amplamente utilizados em telecomunicações e defesa militar para o simultâneo envio e recepção de sinais por um único meio. Esses circuitos passivos, fabricados a partir de materiais ferromagnéticos, possuem a desvantagem do aumento de dimensões, peso e custos de fabricação com a diminuição da frequência de operação definida no projeto destes dispositivos, inviabilizando sua aplicação em frequências abaixo de 500 MHz. O circulador ativo surgiu como uma alternativa aos tradicionais, tendo aplicações em frequências desde o nível DC até a ordem de dezenas de gigahertz. As suas maiores aplicações ocorrem quando são necessários dispositivos compactos, de baixo custo e de baixa potência. Os primeiros circuitos propostos possuíam uma grande limitação em termos de frequência de operação e de potência entregue à carga. Entretanto, com os avanços tecnológicos na eletrônica, tais problemas podem ser amenizados atualmente. Neste trabalho é apresentado o desenvolvimento de um circuito circulador ativo para a utilização em instrumentação eletrônica, em particular para a operação em frequências na ordem das utilizadas em equipamentos de ultrassom Doppler de ondas contínuas, na faixa de 2 MHz a 10 MHz. As possíveis vantagens da implementação de circuladores em sistemas de ultrassom estão relacionadas ao incremento da relação sinal-ruído, aumento da área de recepção do transdutor, simplificação da construção do transdutor, simplificação do circuito de demodulação/ processamento, e maior isolação entre os circuitos de transmissão e recepção de sinais. Na fase inicial, o circulador ativo proposto é modelado por equacionamento, utilizando-se tanto o modelo ideal dos amplificadores operacionais como o seu modelo de resposta em frequência. Simulações computacionais foram executadas para confirmar a validade do equacionamento. Um circuito montado em placa de prototipagem rápida foi apresentado, e testes de prova de conceito em baixas frequências foram realizados, mostrando uma grande semelhança entre o teórico, o simulado e o experimental. A segunda parte contou com o projeto do circuito circulador para a operação em maiores frequências. O circuito proposto é composto por três amplificadores operacionais de realimentação por corrente e vários componentes passivos. Uma análise de sensibilidade utilizando os métodos de Monte-Carlo e análise do pior caso foi aplicada, resultando em um perfil de comportamento frente às variações dos componentes do circuito e às variações da impedância de carga. Uma placa de circuito impressa foi projetada, utilizando-se de boas práticas de leiaute para a operação em altas frequências. Neste circuito montado, foram realizados os seguintes testes e medições: comportamento no domínio do tempo, faixa dinâmica, nível de isolação em relação à amplitude do sinal, largura de banda, levantamento dos parâmetros de espalhamento, e envio e recepção de sinais por transdutor de ultrassom Doppler de ondas contínuas. Os resultados dos testes de desempenho foram satisfatórios, apresentando uma banda de transmissão de sinais para frequências de 100 MHz, isolação entre portas não consecutivas de 39 dB na frequência de interesse para ultrassom Doppler e isolação maior que 20 dB para frequências de até 35 MHz. A faixa dinâmica excedeu a tensão de 5 Vpp, e o circuito teve bom comportamento no envio e na recepção simultânea de sinais pelo transdutor de ultrassom. / Traditional circulators are widely used in both telecommunications and military defense for sending and receiving signals simultaneously through a single medium. These passive circuits which are manufactured from ferromagnetic materials, have the disadvantages of having suffered an increase in dimensions, weight, and manufacturing costs along with the decrease in the operation frequency established in the designs of such devices, thus preventing their useful employment in frequencies below 500 MHz. The active circulator emerged as an alternative to the traditional ones, and has applications on frequencies ranging from a DC level to levels involving dozens of gigahertz. It is applicable when compact devices are made necessary, at a low cost, and for low frequencies. The first circuits to be introduced had a major limitation in terms of operating frequency and power delivered to the load. However, due to technological advances in electronics, problems such as the aforementioned can now be minimized. This research work presents the development of an active circulator circuit to be used in electronic instrumentation, particularly for operation at frequencies such as those used in continuous wave Doppler ultrasound equipment, ranging from 2 MHz to 10 MHz. The advantages made possible by implementing ultrasound systems with circulators are related to an increase in the signal-to-noise ratio, an increase in the transducers reception area, a simplified construction of the transducer, simplification of the demodulation/processing circuit, and a greater isolation between the transmission circuits and signal reception. In the initial phase, the proposed active circulator was modeled by means of an equating method, using both the ideal model of operational amplifiers and the model of frequency response. Computer simulations were carried out in order to confirm the validity of the equating method. A circuit mounted upon a breadboard was introduced and proof of concept assessments were performed at low frequencies, showing a great similarity among the theoretical, simulated and experimented data. The second phase is when the circulator circuits design was developed in order make its operation at higher frequencies possible. The proposed circuit is comprised of three currentfeedback operational amplifiers and several passive components. A sensitivity analysis was carried out using Monte-Carlo methods and worst-case analyses, resulting in a certain behavioral profile influenced by variations in circuit components and variations in load impedance. A printed circuit board was designed, employing good practice layout standards so that operation at high frequencies would be achieved. The following evaluations and measurements were performed on the circuit that was assembled: time domain behavior, dynamic range, isolation level relative to signal amplitude, bandwidth, survey of the scattering parameters, and transmission and reception of signals by a continuous wave Doppler ultrasound transducer. The results of the performance tests were satisfactory, presenting a 100 MHz signal transmission band, isolation between non-consecutive ports of 39 dB at the frequency of interest to the Doppler ultrasound, and an isolation greater than 20 dB for frequencies of up to 35 MHz. The dynamic range exceeded the 5Vpp and the circuit performed satisfactorily in the simultaneous transmission and reception of signals through the ultrasound\'s transducer.
|
8 |
Robust Optimization of Private Communication in Multi-Antenna Systems / Robuste Optimierung abhörsicherer Kommunikation in MehrantennensystemenWolf, Anne 06 September 2016 (has links) (PDF)
The thesis focuses on the privacy of communication that can be ensured by means of the physical layer, i.e., by appropriately chosen coding and resource allocation schemes. The fundamentals of physical-layer security have been already formulated in the 1970s by Wyner (1975), Csiszár and Körner (1978). But only nowadays we have the technical progress such that these ideas can find their way in current and future communication systems, which has driven the growing interest in this area of research in the last years.
We analyze two physical-layer approaches that can ensure the secret transmission of private information in wireless systems in presence of an eavesdropper. One is the direct transmission of the information to the intended receiver, where the transmitter has to simultaneously ensure the reliability and the secrecy of the information. The other is a two-phase approach, where two legitimated users first agree on a common and secret key, which they use afterwards to encrypt the information before it is transmitted. In this case, the secrecy and the reliability of the transmission are managed separately in the two phases.
The secrecy of the transmitted messages mainly depends on reliable information or reasonable and justifiable assumptions about the channel to the potential eavesdropper. Perfect state information about the channel to a passive eavesdropper is not a rational assumption. Thus, we introduce a deterministic model for the uncertainty about this channel, which yields a set of possible eavesdropper channels. We consider the optimization of worst-case rates in systems with multi-antenna Gaussian channels for both approaches. We study which transmit strategy can yield a maximum rate if we assume that the eavesdropper can always observe the corresponding worst-case channel that reduces the achievable rate for the secret transmission to a minimum.
For both approaches, we show that the resulting max-min problem over the matrices that describe the multi-antenna system can be reduced to an equivalent problem over the eigenvalues of these matrices. We characterize the optimal resource allocation under a sum power constraint over all antennas and derive waterfilling solutions for the corresponding worst-case channel to the eavesdropper for a constraint on the sum of all channel gains. We show that all rates converge to finite limits for high signal-to-noise ratios (SNR), if we do not restrict the number of antennas for the eavesdropper. These limits are characterized by the quotients of the eigenvalues resulting from the Gramian matrices of both channels. For the low-SNR regime, we observe a rate increase that depends only on the differences of these eigenvalues for the direct-transmission approach. For the key generation approach, there exists no dependence from the eavesdropper channel in this regime. The comparison of both approaches shows that the superiority of an approach over the other mainly depends on the SNR and the quality of the eavesdropper channel. The direct-transmission approach is advantageous for low SNR and comparably bad eavesdropper channels, whereas the key generation approach benefits more from high SNR and comparably good eavesdropper channels. All results are discussed in combination with numerous illustrations. / Der Fokus dieser Arbeit liegt auf der Abhörsicherheit der Datenübertragung, die auf der Übertragungsschicht, also durch geeignete Codierung und Ressourcenverteilung, erreicht werden kann. Die Grundlagen der Sicherheit auf der Übertragungsschicht wurden bereits in den 1970er Jahren von Wyner (1975), Csiszár und Körner (1978) formuliert. Jedoch ermöglicht erst der heutige technische Fortschritt, dass diese Ideen in zukünftigen Kommunikationssystemen Einzug finden können. Dies hat in den letzten Jahren zu einem gestiegenen Interesse an diesem Forschungsgebiet geführt.
In der Arbeit werden zwei Ansätze zur abhörsicheren Datenübertragung in Funksystemen analysiert. Dies ist zum einen die direkte Übertragung der Information zum gewünschten Empfänger, wobei der Sender gleichzeitig die Zuverlässigkeit und die Abhörsicherheit der Übertragung sicherstellen muss. Zum anderen wird ein zweistufiger Ansatz betrachtet: Die beiden Kommunikationspartner handeln zunächst einen gemeinsamen sicheren Schlüssel aus, der anschließend zur Verschlüsselung der Datenübertragung verwendet wird. Bei diesem Ansatz werden die Abhörsicherheit und die Zuverlässigkeit der Information getrennt voneinander realisiert.
Die Sicherheit der Nachrichten hängt maßgeblich davon ab, inwieweit zuverlässige Informationen oder verlässliche Annahmen über den Funkkanal zum Abhörer verfügbar sind. Die Annahme perfekter Kanalkenntnis ist für einen passiven Abhörer jedoch kaum zu rechtfertigen. Daher wird hier ein deterministisches Modell für die Unsicherheit über den Kanal zum Abhörer eingeführt, was zu einer Menge möglicher Abhörkanäle führt. Die Optimierung der sogenannten Worst-Case-Rate in einem Mehrantennensystem mit Gaußschem Rauschen wird für beide Ansätze betrachtet. Es wird analysiert, mit welcher Sendestrategie die maximale Rate erreicht werden kann, wenn gleichzeitig angenommen wird, dass der Abhörer den zugehörigen Worst-Case-Kanal besitzt, welcher die Rate der abhörsicheren Kommunikation jeweils auf ein Minimum reduziert.
Für beide Ansätze wird gezeigt, dass aus dem resultierenden Max-Min-Problem über die Matrizen des Mehrantennensystems ein äquivalentes Problem über die Eigenwerte der Matrizen abgeleitet werden kann. Die optimale Ressourcenverteilung für eine Summenleistungsbeschränkung über alle Sendeantennen wird charakterisiert. Für den jeweiligen Worst-Case-Kanal zum Abhörer, dessen Kanalgewinne einer Summenbeschränkung unterliegen, werden Waterfilling-Lösungen hergeleitet. Es wird gezeigt, dass für hohen Signal-Rausch-Abstand (engl. signal-to-noise ratio, SNR) alle Raten gegen endliche Grenzwerte konvergieren, wenn die Antennenzahl des Abhörers nicht beschränkt ist. Die Grenzwerte werden durch die Quotienten der Eigenwerte der Gram-Matrizen beider Kanäle bestimmt. Für den Ratenanstieg der direkten Übertragung ist bei niedrigem SNR nur die Differenz dieser Eigenwerte maßgeblich, wohingegen für den Verschlüsselungsansatz in dem Fall keine Abhängigkeit vom Kanal des Abhörers besteht. Ein Vergleich zeigt, dass das aktuelle SNR und die Qualität des Abhörkanals den einen oder anderen Ansatz begünstigen. Die direkte Übertragung ist bei niedrigem SNR und verhältnismäßig schlechten Abhörkanälen überlegen, wohingegen der Verschlüsselungsansatz von hohem SNR und vergleichsweise guten Abhörkanälen profitiert. Die Ergebnisse der Arbeit werden umfassend diskutiert und illustriert.
|
9 |
Robust Optimization of Private Communication in Multi-Antenna SystemsWolf, Anne 02 June 2015 (has links)
The thesis focuses on the privacy of communication that can be ensured by means of the physical layer, i.e., by appropriately chosen coding and resource allocation schemes. The fundamentals of physical-layer security have been already formulated in the 1970s by Wyner (1975), Csiszár and Körner (1978). But only nowadays we have the technical progress such that these ideas can find their way in current and future communication systems, which has driven the growing interest in this area of research in the last years.
We analyze two physical-layer approaches that can ensure the secret transmission of private information in wireless systems in presence of an eavesdropper. One is the direct transmission of the information to the intended receiver, where the transmitter has to simultaneously ensure the reliability and the secrecy of the information. The other is a two-phase approach, where two legitimated users first agree on a common and secret key, which they use afterwards to encrypt the information before it is transmitted. In this case, the secrecy and the reliability of the transmission are managed separately in the two phases.
The secrecy of the transmitted messages mainly depends on reliable information or reasonable and justifiable assumptions about the channel to the potential eavesdropper. Perfect state information about the channel to a passive eavesdropper is not a rational assumption. Thus, we introduce a deterministic model for the uncertainty about this channel, which yields a set of possible eavesdropper channels. We consider the optimization of worst-case rates in systems with multi-antenna Gaussian channels for both approaches. We study which transmit strategy can yield a maximum rate if we assume that the eavesdropper can always observe the corresponding worst-case channel that reduces the achievable rate for the secret transmission to a minimum.
For both approaches, we show that the resulting max-min problem over the matrices that describe the multi-antenna system can be reduced to an equivalent problem over the eigenvalues of these matrices. We characterize the optimal resource allocation under a sum power constraint over all antennas and derive waterfilling solutions for the corresponding worst-case channel to the eavesdropper for a constraint on the sum of all channel gains. We show that all rates converge to finite limits for high signal-to-noise ratios (SNR), if we do not restrict the number of antennas for the eavesdropper. These limits are characterized by the quotients of the eigenvalues resulting from the Gramian matrices of both channels. For the low-SNR regime, we observe a rate increase that depends only on the differences of these eigenvalues for the direct-transmission approach. For the key generation approach, there exists no dependence from the eavesdropper channel in this regime. The comparison of both approaches shows that the superiority of an approach over the other mainly depends on the SNR and the quality of the eavesdropper channel. The direct-transmission approach is advantageous for low SNR and comparably bad eavesdropper channels, whereas the key generation approach benefits more from high SNR and comparably good eavesdropper channels. All results are discussed in combination with numerous illustrations. / Der Fokus dieser Arbeit liegt auf der Abhörsicherheit der Datenübertragung, die auf der Übertragungsschicht, also durch geeignete Codierung und Ressourcenverteilung, erreicht werden kann. Die Grundlagen der Sicherheit auf der Übertragungsschicht wurden bereits in den 1970er Jahren von Wyner (1975), Csiszár und Körner (1978) formuliert. Jedoch ermöglicht erst der heutige technische Fortschritt, dass diese Ideen in zukünftigen Kommunikationssystemen Einzug finden können. Dies hat in den letzten Jahren zu einem gestiegenen Interesse an diesem Forschungsgebiet geführt.
In der Arbeit werden zwei Ansätze zur abhörsicheren Datenübertragung in Funksystemen analysiert. Dies ist zum einen die direkte Übertragung der Information zum gewünschten Empfänger, wobei der Sender gleichzeitig die Zuverlässigkeit und die Abhörsicherheit der Übertragung sicherstellen muss. Zum anderen wird ein zweistufiger Ansatz betrachtet: Die beiden Kommunikationspartner handeln zunächst einen gemeinsamen sicheren Schlüssel aus, der anschließend zur Verschlüsselung der Datenübertragung verwendet wird. Bei diesem Ansatz werden die Abhörsicherheit und die Zuverlässigkeit der Information getrennt voneinander realisiert.
Die Sicherheit der Nachrichten hängt maßgeblich davon ab, inwieweit zuverlässige Informationen oder verlässliche Annahmen über den Funkkanal zum Abhörer verfügbar sind. Die Annahme perfekter Kanalkenntnis ist für einen passiven Abhörer jedoch kaum zu rechtfertigen. Daher wird hier ein deterministisches Modell für die Unsicherheit über den Kanal zum Abhörer eingeführt, was zu einer Menge möglicher Abhörkanäle führt. Die Optimierung der sogenannten Worst-Case-Rate in einem Mehrantennensystem mit Gaußschem Rauschen wird für beide Ansätze betrachtet. Es wird analysiert, mit welcher Sendestrategie die maximale Rate erreicht werden kann, wenn gleichzeitig angenommen wird, dass der Abhörer den zugehörigen Worst-Case-Kanal besitzt, welcher die Rate der abhörsicheren Kommunikation jeweils auf ein Minimum reduziert.
Für beide Ansätze wird gezeigt, dass aus dem resultierenden Max-Min-Problem über die Matrizen des Mehrantennensystems ein äquivalentes Problem über die Eigenwerte der Matrizen abgeleitet werden kann. Die optimale Ressourcenverteilung für eine Summenleistungsbeschränkung über alle Sendeantennen wird charakterisiert. Für den jeweiligen Worst-Case-Kanal zum Abhörer, dessen Kanalgewinne einer Summenbeschränkung unterliegen, werden Waterfilling-Lösungen hergeleitet. Es wird gezeigt, dass für hohen Signal-Rausch-Abstand (engl. signal-to-noise ratio, SNR) alle Raten gegen endliche Grenzwerte konvergieren, wenn die Antennenzahl des Abhörers nicht beschränkt ist. Die Grenzwerte werden durch die Quotienten der Eigenwerte der Gram-Matrizen beider Kanäle bestimmt. Für den Ratenanstieg der direkten Übertragung ist bei niedrigem SNR nur die Differenz dieser Eigenwerte maßgeblich, wohingegen für den Verschlüsselungsansatz in dem Fall keine Abhängigkeit vom Kanal des Abhörers besteht. Ein Vergleich zeigt, dass das aktuelle SNR und die Qualität des Abhörkanals den einen oder anderen Ansatz begünstigen. Die direkte Übertragung ist bei niedrigem SNR und verhältnismäßig schlechten Abhörkanälen überlegen, wohingegen der Verschlüsselungsansatz von hohem SNR und vergleichsweise guten Abhörkanälen profitiert. Die Ergebnisse der Arbeit werden umfassend diskutiert und illustriert.
|
Page generated in 0.0643 seconds