Mesterpróba 2016 Tudományos konferencia végzős MSc és elsőéves PhD hallgatóknak Távközlés és infokommunikáció témakörében
KONFERENCIA KIADVÁNY
Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar
BUDAPEST 2016. május 26.
Mesterpróba 2016 Tudományos konferencia végzős MSc és elsőéves PhD hallgatóknak Távközlés és infokommunikáció témakörében
A Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kara hallgatói konferenciát hirdet a Hírközlési és Informatikai Tudományos Egyesület tudományos bizottsága, az MTA Távközlési Tudományos Bizottsága és az IEEE Hungarian Joint AP/ED/MTT/EMC/ComSoc chapter támogatásával. A konferencia célja kettős. Egyrészt a legjobb végzős hallgatók számára fórumot biztosít, ahol a diplomamunkájuk készítése során elért kiemelkedő eredményeiket be tudják mutatni a szélesebb szakmai közönségnek. Másrészt támogatja a tudományos indíttatású hallgatók első konferencia részvételét. A konferenciára elsősorban az MSc képzésben 2016-ban a meghirdetett témakörökben diplomázó hallgatók és a tanulmányaikat a 2015/2016-os évben megkezdett doktorandusz hallgatók jelentkezését várjuk. A konferenciára egyszerzős, saját eredményeket bemutató magyar vagy angol nyelvű cikkeket lehet benyújtani (a konzulenst, mint társszerzőt megjelölve). A konferenciára szakmai színvonalának biztosítása érdekében a benyújtott anyagokat szakemberekből álló bíráló bizottság értékeli és dönt azok elfogadásáról.
Mesterpróba 2016
A KONFERENCIA TUDOMÁNYOS ÉS SZERVEZŐ BIZOTTSÁGA Társelnökök Gerhátné Dr. Udvary Eszter (IEEE MTT/AP/ED/ComSoc/EMC Chapter, BME-HVT) Prof. Pap László (MTA TTB, HTE, BME-HIT) Tagok Győri Erzsébet (BME-TMIT) Dr. Huszák Árpád (BME-HIT) Dr. Szabó Zsolt (BME-HVT) Kalvach Arnold (BME-HVT)
TÁMOGATÓK Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar Hírközlési és Informatikai Tudományos Egyesület MTA Távközlési Tudományos Bizottsága IEEE Hungarian Joint AP/ED/MTT/ComSoc/EMC chapter BME – Hálózati Rendszerek és Szolgáltatások Tanszék BME – Szélessávú Hírközlés és Villamosságtan Tanszék BME – Távközlési és Médiainformatikai Tanszék Pro Patria Electronics kft. Huawei Technologies Hungary kft.
Mesterpróba 2016 Program A konferencia időpontja: 2016. május 26. csütörtök, 9:50 – 17:00 A konferencia helye: BME V1. épület, 5. emelet, 502 terem Budapest XI. Egry József utca. 18. 9:50
Megnyitó
1. szekció 10:00
V1. 502
Hum Nath Parajuli ea: Schranz Ágoston
10:15
Szabó Gábor
10:30
Schranz Ágoston
10:45
Matolcsy Balázs
11:00 11:15
Csizmadia Miklós Marák Károly
2. szekció
V1. 502
12:00
Nagy Attila Mátyás
12:15
Miru György
12:30 12:45 13:00 13:15
Péteri Tamás Danyi Ádám Gajdos András Vass Balázs
3. szekció
V1. 502
14:15 14:30
Szabó Örs Németh Balázs
14:45
Péceli Bálint
15:00 15:15
Lévai Tamás Soós Gábor Kozma Dániel
15:30
elnök: Dr. Nagy Lajos Improving the Capacity of Radio Over Fiber System Using Pol-Mux and Vector Signal Transmission VLC Indoor Positioning with Code Division Multiplexing and Optical Orthogonal Codes Experimental Investigation of VCSEL for Quantum Communications Szélessávú impedanciaillesztés, szabadtéri kommunikácós célra használt VCSEL-hez 2,5kW/50V-os Li-ion töltő DC/DC teljesítményfokozatának tervezése Investigation of integrated microchannel based heat sinks for VLSI circuits
elnök: Prof. Pap László A crowdsensing platform for mass surveillance at outdoor events Where are my tokens: a Linux kernel based hidden host monitoring framework for honeytokens Orvosi multimédia-adatok mobil átvitelének QoE vizsgálata Felhasználók pozicionálása 4. generációs mobil hálózatokban Kereskedés érzelmi alapon: hírszentiment a webes Big Data-ban Listing Regional Failures
elnök: Dr. Biczók Gergely Flow based load balancer with Round-Robin Bloom filters A Fast and Efficient Algorithm for Online Resource Orchestration Integrating an Electrical Vehicle Charging System with the Arrowhead Framework Distributed Network Emulation over Cloud Infrastructure Use Cases for LTE Core Network Mass Testing Traffic Analysis Methods for the Evolved Packet Core in LTE
ea: Soós Gábor
15:45
Marosvári Borbála
16:30
Eredményhirdetés és zárszó
Annotation of movies for camera movement recognition
Mesterpróba 2016 DÍJAZOTTAK
Budapesti Műszaki és Gazdaságtudományi Egyetem, Villamosmérnöki és Informatikai Kar díja Lévai Tamás Distributed Network Emulation over Cloud Infrastructure Konzulens: Németh Felicián Marák Károly Investigation of integrated microchannel based heat sinks for VLSI circuits Konzulens: Takács Gábor Schranz Ágoston Experimental Investigation of VCSEL for Quantum Communications Konzulens: Dr. Kiss Zsolt, Fekete Gábor, Gerhátné Dr. Udvary Eszter
Pro Patria Electronics Kft. Különdíja Nagy Attila Mátyás A crowdsensing platform for mass surveillance at outdoor events Konzulens: Dr. Simon Vilmos Soós Gábor Use Cases for LTE Core Network Mass Testing Konzulens: Dr. Varga Pál Szabó Gábor VLC Indoor Positioning with Code Division Multiplexing and Optical Orthogonal Codes Konzulens: Gerhátné Dr. Udvary Eszter
Huawei Technologies Hungary Kft. különdíja Péteri Tamás Orvosi multimédia-adatok mobil átvitelének QoE vizsgálata Konzulens: Dr. Bokor László
HTE különdíj Vass Balázs Listing Regional Failures Konzulens: Tapolcai János, Kovács Erika, Kőrösi Attila
Improving the Capacity of Radio Over Fiber System Using Pol-Mux and Vector Signal Transmission Hum Nath Parajuli and Eszter Udvary, Member, IEEE
Áron Szabo
Department of Broadband Info Communication and Electromagnetic Theory Budapest University of Technology and Economics Budapest, Hungary
Department of Telecommunication and Media Informatics Budapest University of Technology and Economics Budapest, Hungary
[email protected]
{hum.nath.parajuli,udvary}@hvt.bme.hu
to provide the needed data rate for the end user. Thus, to provide Gbps wireless access the RoF technologies utilizing advanced modulation schemes and multiplexing techniques will be extremely beneficial.
Abstract— To increase capacity of radio over fiber (RoF) link, electrical subcarrier multiplexing technique can be used. This method introduces serious intermodulation distortion (IMD), which limits the transmission performance. In this paper, we propose a multiplexing technique in optical domain using polarization multiplexing (Pol-Mux) technique which is free of intermodulation distortion and increases the spectral efficiency. We discuss major transmission impairments of the RoF system which uses Pol-Mux technique and investigate the effect of polarization crosstalk in the transmission performance of such system. We analyze the performance of the QAM signal transmission in single sideband based Pol-Mux RoF system.
Conventionally, electrical subcarrier multiplexing (SCM) techniques have been used to increase the capacity of the RoF system. However, SCM technique suffers from strong nonlinearity due to the intermodulation distortion (IMD). In this paper, we propose the Pol-Mux technique which is not affected by IMD and can enhance the system capacity. The major transmission impairment in Pol-Mux based system is the polarization crosstalk. We show that with the sufficient extinction ratio of polarization beam splitter (PBS), crosstalk free system can be realized.
Keywords— radio over fiber; pol-mux; optical single sideband; modulation index; vector signal transmission;
I. INTRODUCTION The wireless bandwidths at conventional radio frequency (RF) bands (0.7-2.6 GHz) are not sufficient to fulfill the higher capacity demands [1]. The 5G deployment goal by 2020 is to provide 1-10 Gbps wireless signal for the end user [2]. The bandwidth limitation of wireless-based backhaul systems can be resolved through radio over fiver (RoF) technology. In RoF systems the radio signal is transmitted through low loss and huge bandwidth optical fiber. RoF links have the ability to deliver RF signals into remote cells without destroying their characteristics (RF, modulation formats etc.). It allows the small cell deployment in remote area providing Gbps wireless access and makes the network simple and scalable.
II. INCREASING THE CAPACITY OF THE ROF LINK The methods to increase the capacity of RoF system can be briefly described as: A. Subcarrier Multiplexing In SCM, digital or analogue modulated baseband signals are mixed using different sinusoidal frequencies and finally added together. The composite signal is fed for the optical sideband modulation. The modulation of the optical carrier can be done either by direct modulation or by using external modulation methods. At the receiver side all the frequency carriers are recovered through photodetection. The major distortion associated with SCM is IMD. The SCM system can further be extended in wavelength division multiplexing system (WDM) where each group of SCM channels represent different wavelength, enhancing the aggregate capacity.
The major approaches to resolve the problem of bandwidth demand can be put as: a) frequency reuse through small cell deployment, b) use of higher frequency bands such as millimetre wave bands and c) spectral efficiency improvement using advanced modulation formats and multiplexing techniques. All these approaches can be realized with the help of RoF technology. By reducing the cell size, frequency reuse can be done more repeatedly. Higher frequency bands such as millimeter wave bands can provide Gbps wireless access however it suffers from limited transmission range. Therefore, small cells architecture (pico cell/ femto cell) in combination with RoF provides a superior solution to increase the cellular system capacity. The advanced modulation formats and multiplexing technologies offer the suitable spectral efficiency
B. Vector Signal Transmission The modulation method plays important role in maintaining the better system performance. To increase the spectral efficiency advanced modulation formats have to be considered. mQAM, mPSK are the major modulation formats used in wireless communication for both single and multi carrier systems. The transmission of these modulation signals in RoF domain has been studied extensively in the past years. Since, the number of base stations (BS) will increase due to the use of millimeter wave band for 5G system, the BS cost should be as low as possible. The used modulation formats should simplify the base station complexity thus needs to use
1
simple direct detection instead of optical coherent detection system. However, for vector RF signal demodulation the coherent receiver in electrical domain is still required.
III. TRANSMISSION IMPAIRMENTS The RoF transmission system suffers from various kinds of noises and distortions. Thermal noise, shot noise, relative intensity noise (RIN), laser chirp, fiber nonlinearity, CD, polarization mode dispersion (PMD) etc. are present like in any other fiber optic links. Most importantly, CD and nonlinearity associated with modulator and square law photo detector are the major factors for impairments in RoF.
The choice of modulation type for any RoF system depends on the capacity and minimum reach that RoF system requires to fulfill. To combat with both linear and nonlinear impairments, optimum modulation formats have to be used. For example, the modulation format with longer symbol duration will be less affected by chromatic dispersion (CD). Similarly, the modulation format with constant power can be less susceptible to nonlinearity. The choice of the electrical modulation format also depends on the use of the optical sideband modulation method. The optical double sideband (ODSB) and optical single sideband modulation (OSSB) schemes can deliver the vector signal to the receiver. However, ODSB is seriously affected by CD which leads to the power fading of the received signal and not suitable for long reach and high frequency RoF system. OSSB can compensate the CD but requires more complex method for its generation and suffers from serious SNR degradation due to the strong dc component present in the detected signal. Optical carrier suppressed double sideband (OCS-DSB) scheme can compensate the CD and provides best SNR. However, this scheme cannot be used for vector signal transmission without doubling the signal frequency and phase at the receiver, as a consequence the sent signal will be modified while detecting at the receiver [3]. For example, if one intends to receive QPSK signal at the receiver, the sending side has to send 8PSK signal with half of the intended frequency. This adds extra complexity at the transmitter or receiver.
A. Effect of Chromatic Dispersion The ODSB transmission in dispersive fiber link leads to the different phase shifts between the sidebands. The power of the recovered signal after photo detection can be given as [4] ( ) = cos
.
Where, is the fiber length, is the speed of the light, is the dispersion parameter, is the optical carrier frequency and is the electrical carrier frequency. If the sidebands experience a total phase difference of 180˚ relative to the optical carrier the RF signal will be vanished [4-5]. Depending on the amount of phase shifts due to CD, power fading of the detected RF signal occurs. Also, the received signal shows periodic power variation based on the fiber length due to CD. To overcome the CD effect, CD tolerant sideband modulation schemes such as OSSB and OCS-DSB have to be used. B. Harmonic and Intermodulation Distortions Due to the cosine transfer characteristic of the MachZehnder modulator (MZM), infinite numbers of harmonic products and intermodulation products are generated. Let ( )= and ( ) = cos(ω t) are optical carrier and modulation electrical signal respectively. Where, and ω are the frequencies of the optical carrier and electrical signal respectively, is the amplitude of the optical carrier and is the voltage amplitude of the modulation signal. The general expression for the output electric field from single drive MZM can be derived as
C. Proposed Pol-Mux Technique To increase the spectral efficiency of the system the proposed Pol-Mux scheme is shown in Fig. 1. The idea is to use two orthogonal polarizations to carry different RF signals in the same fiber simultaneously. In the transmission side, two orthogonal polarizations are separated and multiplexed using polarization controller and polarization beam combiner (PBC). Each polarization can carry differently or identically modulated waveforms. The electrical carrier frequency can also be the identical or different. In the receiver side each polarization component is separated through the same PBC as in transmitter but in opposite direction. Since the multiplexing is done in two polarizations, the major benefit of this scheme is to avoid the intermodulation distortion associated with SCM system. With sufficient polarization extinction ratio (PER) of PBC, the polarization crosstalk can be substantially minimized.
( )= . . . .
( ( ( (
). cos( ) ). sin( ) ). cos( ) ). sin( )
− ( ( (
)
+ ) + ) +
(
−
)
(
)
(
)
− +⋯ (2)
Where, is the Bessel function of the first kind, is the half wave voltage of the modulator and is the applied dc bias | ( )| voltage to the modulator, = and = . Equation (2) shows that MZM output contains infinite numbers of harmonic components. The harmonic distortion (HD) mainly depends on the used modulation index. When higher modulation index is used harmonics intensity will be increased leading to the distortion. Each harmonic experiences different phase change due to CD in the fiber. The IMD arises mainly due to the use of number of subcarriers and high value of modulation index. For example, if the SCM system consists of
Figure 1. Basic block diagram of Pol-Mux technique.
2
two subcarriers f1 and f2, then the detected electrical spectrum consists of (f2- f1) and (2f1- f2) products just before f1. Suppression of these unwanted components can be very difficult. In higher modulation index condition, the intensity of these components will be high leading to serious distortion.
Stokes parameter measurement to achieve the orthogonal polarization multiplexing. Encoding the RF data in complete orthogonal polarizations removes the polarization crosstalk in Pol-Mux system, thus improves the performance of the RoF system.
C. Polarization Cross- talk in Pol-Mux System Before discussing polarization crosstalk, we introduce the concept of state of polarization (SOP) and Stokes vector; common terms used in polarization based optical system. The two orthogonal components X and Y of the E-field vector of optical beam can be given as
IV. SIMULATION RESULTS WITH VECTOR SIGNAL TRANSMISSION To observe the performance of the Pol-Mux technique for the vector signal transmission with different polarization cross talk, we built up the optical setup in VPItransmissionMaker simulator as shown in Fig. 1. In the setup, a continuous wave DFB laser is operated at 10 dBm, with emission frequency of 1553 nm and line width of 10 MHz. The optical beam is divided into two parts through 3-dB splitter. The orthogonal polarizations X and Y in two arms are generated with nonideal polarization controllers with Stokes parameters (S1, S2, S3) equal to (0.9999, 1.6×10-11, 5.3×10-6) and (-0.9999, 2.65×10-6, -1.3×10-11) respectively. Since the values of S2, S3 are very low, their contribution can be assumed negligible and thus X and Y polarizations can be assumed almost orthogonal. The fiber dispersion is 18e-6s/m2 and dispersion slope is 0.08e3 3 /s . In both arms, the OSSB signal was generated using dual drive MZM whose one of the driving signal phase is shifted by 90˚compared to another. The MZM is biased at quadrature point and the driving signal amplitude is set to 0.25 V. The half wave voltage ( ) of the MZM is at 4 V. The driving signal for modulators is a 1 Gbps, 4QAM with carrier frequency of 10 GHz for X-polarization arm and 1 Gbps, 16QAM with carrier frequency of 10 GHz for Y-polarization arm. The random and different bit patterns were used to code the 4QAM and 16QAM signals. The pseudo random binary sequence used is De Bruijn sequence.
(t) = A cos (ωt + ∅ )
(t) = A cos (
+ ∅ ).
Where, and ∅ is the magnitude and phase of ( ), is the optical carrier frequency. When two components are present in the light wave then the E-field vector is given as (t) =
(t) +
(t) .
SOP is a measure of the relative magnitude and phase of the ( ) and ( ) that are present in the composite light beam ( ). The values of SOP determine how the given light beam combines with other light beam and how it will be affected by polarization dependent optical components. To describe the SOP, generally Stokes vector S1×4 = [S0, S1, S2, S3] is used. Where, S0 represent the total power of the light beam, S1 represent the power difference of horizontal and vertical polarization components, S2 represent the power difference of +45˚ and -45˚ linear polarization components, S3 is the power difference between left hand and right hand circular polarization components. To display the Stokes vector, Poincare sphere is used. For example, for the ideal horizontal linear polarization the Stokes parameters can be given as (S1, S2, S3) = (1, 0, 0) and for ideal vertical linear polarization Stokes parameters can be given as (S1, S2, S3) = (1, 0, 0). Both of these polarizations lie in the equator of Poincare sphere.
Fig. 2 shows the effect of polarization crosstalk in 4QAM and 16QAM SER performance. The SER was calculated using Gaussian simulation method. The of PBS on transmitting and receiving sides were varied with the same values. Used fiber length is 35 km. For 10 GHz carrier, the first received signal power null due to CD occurs at 35 km, so this fiber length will be the minimum SER performance point. The CD and other fiber effects were considered except PMD. Any rotation of polarization can be realigned in receiver side using the polarization controller placed before receiver PBS as shown in Fig. 1 and the data rate is low (1 Gbps), this allows to consider negligible PMD.
When the polarized light is incident on the polarization beam splitter (PBS), it separates its composite incident polarization states. There will be some amount of crosscoupling of power between the two polarization components. This means, in the X/Y-polarization arm of the PBS, some amount of Y/X-polarization will be coupled. This is called a polarization crosstalk effect and it can be given by the polarization extinction ratio ( ). is a power ratio that describes the power exchange between the polarizations states in optical device. The for X and Y polarization arm of the PBS can be given as (
) = 10 log
log10(SER)
0
-10 -20
-40 -50 0
(
) = 10 log
.
4QAM 16QAM
-30
5
10
15
20
25
30
PER(dB)
Figure 2. The performance of QAM signals for different polarization extinction ratios. The results were obtained at fiber length of 35 km (power null point for 10 GHz carrier). After 22 dB PER, the SER values are constant, this means no cross talk effect. This is also true if there is no CD present.
Polarization crosstalk will be the inverse ratio of the . For the ideal system with no crosstalk, the value of will be infinite. The output of PBC should be optimized based on the
3
crosstalk can be assumed negligible. The CD, fiber attenuation and fiber nonlinearity were enabled. Due to the SSB signal transmission, the effect of CD has been reduced significantly. For the lower fiber lengths the CD effect will be very low so the SER is extremely low for both signals. As the fiber length increases the CD accumulates and becomes stronger. This causes some amount of periodic variation of the received signal power, which changes SNR. At 100 km fiber length, the 4QAM signal has SER at 10-17 and 16QAM signal has SER at 10-9. The SSB method alone to compensate the CD effectively is not adequate after 100 km fiber length, if one chooses the threshold of SER at 10-9.
From the Fig. 2 the SER values are decreasing as the values are increasing. For initial values, the SER of 4QAM is higher compared to 16QAM. Although, the crossing of 4QAM curve with 16QAM occurs earlier (at 15 dB ), 4QAM SER is not constant until 22 dB . After 22 dB , SER for both curves are not varying. For the low , the signal power coupling from the 4QAM/16QAM to 16QAM/4QAM will be high. The SER for 4QAM is higher compared to 16QAM at the low , because 4QAM receiver detects more unwanted constellation points than the actual 4QAM due to the strong coupling of the 16QAM signal. This effect can be well described through Fig. 3 (a) and 3 (c). The simulation parameters for Fig. 3 are also same as Fig. 2. Fig. 3 (a) and 3 (c) are the received constellation diagrams for 4QAM and 16QAM signals respectively at 5 dB . These figures show that, there is strong distortion in 4QAM signal compared to 16QAM for the lower values of . In 4QAM decision device, not only 4QAM constellation vector but also unwanted 16QAM signal vector with significant power will be present which reduce the performance.
log10(SER)
0 -20 -40 4QAM 16QAM
-60 -80 -100 20
30
40
50
60
70
80
90
100
Fiber Length (km)
As the separation between two polarizations becomes stronger, than the signal coupling effect will be reduced. This means, corresponding decision device can detect its own signal. Fig. 2 shows that as the is sufficiently high enough (about 22 dB), the SER of 16QAM exceed SER of 4QAM. After 22 dB , complete isolation of the two polarization components is achieved. Fig. 3 (b) and 3 (d) are the constellation diagrams for the received 4QAM and 16QAM signals at of 22 dB. At of 22 dB, the effect of polarization crosstalk is extremely low as shown in Fig. 2, thus the constellation diagrams of Fig. 3 (b) and 3 (d) can be considered as a coupling free constellation diagrams.
Figure 4. QAM signals performance with PER of 22 dB. As the fiber length increases CD effect will be stronger leading to a poor performance.
V. CONCLUSIONS To improve the capacity of RoF link, Pol-Mux provides the intermodulation free subcarrier multiplexing. The polarization cross talk is the major impairment in Pol-Mux based system. With the use of commercial polarization beam splitter of about 22 dB polarization extinction ratio along with polarization controller, the polarization crosstalk can be minimized substantially. Pol-Mux can support modulation types independent as well as carrier frequencies independent signals for multiplexing.
0.007
0.007
ACKNOWLEDGMENT
-0.007 -0.007
0
0.007
-0.007 -0.007
(a) 0.04
0
0
0
(c)
0
0.007
REFERENCES [1] Rappaport, T.S.; Shu Sun; Mayzus, R.; Hang Zhao; Azar, Y.; Wang, K.; Wong, G.N.; Schulz, J.K.; Samimi, M.; Gutierrez, F., "Millimeter Wave Mobile Communications for 5G Cellular: It Will Work!," in Access, IEEE , vol.1, no., pp.335-349, 2013. [2] Gee-Kung Chang; Lin Cheng; Mu Xu; Guidotti, D., "Integrated fiberwireless access architecture for mobile backhaul and fronthaul in 5G wireless data networks," in Avionics, Fiber-Optics and Photonics Technology Conference (AVFOP), 2014 IEEE , vol., no., pp.49-50, 11-13 Nov. 2014. [3] K. Wang, X. Zheng, H. Zhang and Y. Guo: A Radio-Over-Fiber Downstream Link Employing Carrier-Suppressed Modulation Scheme to Regenerate and Transmit Vector Signals, IEEE Photonics Technology Letters, vol. 19, no. 18, pp. 1365-1367, Sept.15, 2007. [4] H. Schmuck, “Comparison of optical millimeter-wave system concepts with regard to chromatic dispersion," in Electronics Letters, vol. 31, no. 21, pp. 1848-1849, 12 Oct 1995. [5] G.H. Smith, D. Novak, Z. Ahmed, "Technique for optical SSB generation to overcome dispersion penalties in fiber-radio systems," in Electronics Letters , vol. 33, no. 1, pp. 74-75, 2 Jan 1997.
(b)
0.021
-0.021 -0.021
This work has been carried out within the project FiWiN5G, supported from European Union’s Horizon 2020 research and innovation program.
0
0
0.021
-0.04 -0.04
0
0.04
(d)
Figure 3. The received constellation diagrams for different PER. (a) and (c) are for the PER = 5 dB and (b) and (d) are for the PER = 22 dB. (a) and (b) are for 4QAM and (c) and (d) are for 16QAM. The constellation diagrams show the slight rotation of the constellation points due to the strong CD effect at 35 km fiber length.
Fig. 4 shows the SER performance with different fiber lengths. The was fixed at 22 dB, thus the polarization
4
VLC Indoor Positioning with Code Division Multiplexing and Optical Orthogonal Codes Gábor Szabó Department of Broadband Infocommunications and Electromagnetic Theory Budapest University of Technology and Economics Budapest, Hungary
[email protected]
synchronization and complex optical devices [8], [9], [10], [11].
Abstract — The satellite based positioning techniques, such as the Global Positioning System (GPS), are not really suitable to establish indoor locations, because the construction materials of buildings cause not only severe attenuation to the microwave radio signals, but also the multi-path propagation leads to uncontrollable errors. A possible solution to this problem is to expand the functionality of LED indoor lighting with visible light communication (VLC) that allows implementing a localization service. This service may based on various channel access methods and modulation types. This paper investigates the possibilities of code division multiplexing (CDM) with baseband modulation and optical orthogonal codes (OOCs). Keywords: visible light communication, multiplexing, baseband, OOK, OOC
I.
code
An indoor positioning system does not require high data rate communication, so inter-symbol interferences (ISI) caused by multi-path propagation does not affect the operation. Moreover, one of the main drawbacks of the VLC – its relatively short range – can be converted into advantage, as the distant illumination devices less interfere with the relevant signals. Regardless of what positioning technique is used, the signals of different transmitters (lamps) have to be separated on the receiver side, so some kind of multiplexing methods should be used. With phosphor-converted white LEDs of illumination devices wavelength-division multiplexing (WDM) is not feasible without interfering with the lighting function. Using simple intensity modulation with direct detection (IM/DD) in an undivided space three fundamental multiplexing methods are possible. Time-division multiplexing (TDM) means that the participants do not communicate in the same time, but alternately, so the other communication parameters (e.g. frequency domain) may be the same for all transmitters. In the case of frequency-division multiplexing (FDM), different nodes transmit on different frequency bands even simultaneously, but this also makes the continuous reception of several signals more difficult. As for code-division multiplexing (CDM), the communication can be in the same time and on same frequency band, because the transmitters use different codes to identify their signals. This method enables the possibility of continuous communication with minimal bandwidth, which is suitable for an indoor positioning system along with other broadband VLC services.
division
INTRODUCTION
Visible light communication (VLC) refers to free space optical transmission with light emitting diodes (LEDs), adding an alternative functionality to lighting or visible light indicator devices [1], [2], [3]. So these light sources, beside their main purposes, can invisibly embed data in their light output, which is immune to radio interferences, does not have environmental and human health risks, and is able to provide a high data rate connection. Due to its benefits this technology has recently attracted significant attentions as a promising complementary technology for short range radio frequency communications [2], [4], [5], [6]. Using the indoor lighting system to positioning purposes via VLC may be a convenient and cost-efficient way to determine the location of portable devices, because the internal areas of a building are usually fully covered with light sources. A mobile node can be located with VLC on several different ways. With the angle of arrival (AoA) method very good accuracy may be achieved. Its main disadvantage is that it requires an image sensor array, which is far more expensive and has a lower bandwidth than a single photodiode [7], [8]. The signal traveling time measurement techniques, such as time of arrival (ToA) and time difference of arrival (TDoA), require not only ultra high speed circuits on the receiver side, but also synchronization between at least the transmitters, increasing the installation and circuit costs [7]. A less accurate but cost-efficient localization method is based on the received signal strength (RSS), which eliminates the need of any
In this paper an experimental visible light CDM system will be presented, which uses optical orthogonal codes (OOCs), and intended as the base of an indoor localization system. The next sections introduce code division multiplexing, the features of OOCs, and the manner of indoor positioning in this layout. Finally, the measurement results of the VLC CDM transmission will be presented. II.
CODE DIVISION MULTIPLEXING
Code division multiplexing is a digital multiplexing method based on binary code sets having special autocorrelation and cross-correlation properties. If the length of codes is n, every
5
bit of data is converted on the transmitter side to n chips. In other words, the transmitter puts out its own code or its bitwise negative on every bit, according to the actual data bit value. The detector receives all signals at the same time (superposition), and correlates this compound signal with each code. The polarity of correlation peak values indicates the bits sent.
There are two main possible modes of operation. The simplest way to roughly determine the position of the receiver is to select the highest signal strength, and state that we are somewhere under the belonging lamp. The accuracy of this method mainly depends on the lamp density of the area, but a high headroom vs. lamp “lattice constant” ratio may introduce major uncertainties.
In synchronous CDM systems, where the transmitter nodes are synchronized, it is possible to use orthogonal code sets, e.g. orthogonal variable spreading factor (OVSF) codes. In this case of perfect orthogonality the crosstalk between CDM channels is zero, but the synchronization requirements make this mode not suitable for a simple VLC system.
The more sophisticated (and accurate) manner is based on the fact that in the case of monotonically decreasing characteristics an RSS value determines a certain distance from a lamp. Detecting at least three transmissions in range, the position of the receiver can be established. The situation of the transmitters whose RSS values are actually utilized in the calculations seriously affects the precision. If their azimuths (center: receiver) are nearly the same and they are even far away, poor results should be expected.
The asynchronous CDM technique does not need any synchronization between the transmitters, it is based on quasiorthogonal codes, like the bipolar Gold codes and the unipolar optical orthogonal codes (OOCs). These codes are not orthogonal, but their cross-correlation peak is low between all circular shifted variants, also having low auto-correlation peak. Due to the lack of orthogonality there is some crosstalk between the CDM channels, but using appropriate codes the signal-to-interference-plus-noise-ratio (SINR) can be high enough to achieve good results.
V.
Our experiments are focused on asynchronous CDM transmission due to the suitability for simple VLC systems. III.
OPTICAL ORTHOGONAL CODES
OOCs are unipolar quasi-orthogonal codes which can be represented with four parameters, usually written in the following format: (n, w, λa, λc), where n is the code length, w is the code weight (number of ones), λa is the upper bound of the autocorrelation function, λc is the upper bound of the crosscorrelation function [12].
digital value (4096=3.3V)
3500
n −1 w, = 0 C xx ( ) = ∑ xi xi ⊕ = i =0 ≤ a , 1 ≤ ≤ n − 1 n −1
C xy ( ) = ∑ xi y i ⊕ i =0
≤ c
0 ≤ ≤ n −1
Unipolarity means that the codes comprise zeros (‘0’) and ones (‘1’), in contrast with bipolar codes, which consist of ‘-1’ and ‘+1’. Due to this fact the minimum value of OOC correlation parameters is 1, slightly limiting the maximal SINR compared to bipolar code sets. Nevertheless, the algorithmic efficiency of an OOC correlator can be very good especially for low weight OOCs, because a point of the correlation function is virtually just a sum of w values (multiplication with ones and zeros). This is an advantage when using a low performance portable device for VLC CDM indoor localization. IV.
CDM-BASED VLC TRANSMISSION
Our experimental VLC CDM system comprises a code generator unit, a warm white LED on-off keying (OOK) transmitter, a silicon photodiode detector circuit and a CDM decoder unit. We used a four elements (128, 6, 6, 1) optical orthogonal code set, because the 6x ratio at the correlator’s output for the proper vs. the other codes should be sufficient. It can be seen that the autocorrelation properties of the codes are not restricted at all. The reason is that we do not aim at data transmission, targeting only presence detection, so the actual displacement of a code on detection is irrelevant.
3000 2500 2000 1500 1000
0
200
Fig. 1.
400 600 sample no.
800
1000
The digitized CDM signal
The VLC transmitter repeatedly outputs the specified code with OOK, creating an intensity modulated light signal. The photodetector converts this to electrical signal, which is connected to the 12-bit analog-to-digital converter (ADC) of the CDM decoder unit. The circuits are AC-coupled to ensure the possibility of adequate gain at various ambient light levels. The digitized signal is showed on Fig. 1. The undershoots also anticipate that this may be an AC-coupled signal, the DC level is set to half power supply value. It is noticeable that the signal-to-noise ratio is good enough, the signal is ready to decode.
INDOOR POSITIONING
Our system is designed to do RSS-based positioning. For the sake of simplicity, assume that the transmitters (lamps) are point-like illuminators on the ceiling with centrosymmetric radiation pattern, and the receiver (detector) is directed vertically against the ceiling in a constant elevation and it has centrosymmetric directional characteristics. Also suppose that no reflections are present.
6
The computed presence indicator values were ≈4.4 and ≈24.7 in the two cases, so the practical values seem to corroborate the theory. This was a fixed position measurement. These values will vary with the position, representing the receiver-transmitter distance at once.
100 90
correlation value (a.u.)
80 70 60
VI.
In this paper we investigated the features of code division multiplexing and optical orthogonal codes in the viewpoint of indoor localization using VLC. Outlining the main types of indoor positioning techniques we selected the one that is most suitable for a low-cost system. Finally it was also demonstrated that the VLC CDM basis of this system with OOCs is feasible.
50 40 30 20 10 0
CONCLUSION
0
500
Fig. 2.
1000 start offset (samples)
1500
The next goals are testing the system with more simultaneous transmissions present, and investigating the positioning capabilities, interference immunity and other parameters of this method.
2000
Correlator output, right code
VII. ACKNOWLEDGEMENTS 100
The author would like to thank Viktor Zsolczai handing over his VLC transmitter circuit for the experiments, and Gábor Fehér to provide other equipment and programming guides of the selected microcontroller system. Special thanks to Eszter Udvary for consultations on theoretical issues.
90
correlation value (a.u.)
80 70 60
REFERENCES
50
[1]
40 30 20 10 0
0
500
Fig. 3.
1000 start offset (samples)
1500
2000
Correlator output, an other code
The digitized signal then undergoes the correlation procedure. The sent bits can not be incessantly restored unless correlating on all channels continuously, but in our case it is enough to correlate on channels in round-robin mode. This method decreases the position acquisition rates with a divider of the channel count, but the required computing time for a single acquisition is also proportionally decreasing. Although the overall computing time does not change, the memory requirements can be dramatically reduced, which is not negligible on portable devices. Fig. 2 and Fig. 3 show two outputs of the correlation procedure, which are the circular cross-correlations of the acquired samples and the codes at all possible start offsets. The “code presence indicator” value will be the ratio of the peak value and the average value of this randomly selected fixed length output block. Due to the minimal cross-correlation the result with an other code (not the one applied on the channel) is limited to a low level, no considerable peaks exist, so the presence indicator value for this code will be a smaller number. On Fig. 2 there are two different peak types. The lower is the consequence of unrestricted autocorrelation properties, and it is ignored by the algorithm what is searching for the highest peak. The presence indicator value for this code will be a larger number, which is approximately w times as large as the value for other codes, where w is the code weight.
7
T. Komine and M. Nakagawa, “Fundamental analysis for visible-light communication system using LED lights”, IEEE Transactions on Consumer Electronics, vol. 50, no. 1, pp. 100–107, 2004. [2] S. Randel, F. Breyer, S. C. Lee, and J. W. Walewski, “Advanced Modulation Schemes for Short-Range Optical Communications”, IEEE Journal of Selected Topics in Quantum Electronics, vol. 16, no. 5, pp. 1280–1289, 2010. [3] A. Street, P. Stavrinou, D. O’brien, and D. Edwards, “Indoor optical wireless systems – a review”, Optical and Quantum Electronics, vol. 29, no. 3, pp. 349–378, 1997. [4] T. Komine and M. Nakagawa, “Integrated system of white LED visiblelight communication and power-line communication”, IEEE Transactions on Consumer Electronics, vol. 49, no. 1, pp. 71–79, 2003. [5] S. Rajagopal, R. D. Roberts, and S.-K. Lim, “IEEE 802.15.7 visible light communication: modulation schemes and dimming support”, IEEE Communications Magazine, vol. 50, no. 3, pp. 72–82, 2012. [6] M. Kavehrad, “Broadband Room Service by Light”, Scientific American, vol. 297, no. 1, pp. 82–87, 2007. [7] T. Do, J. Hwang, and M. Yoo, “TDoA Based Indoor Visible Light Positioning System”, Fifth International Conference on Ubiquitous and Future Networks (ICUFN), 2013. [8] M. S. Rahman, M. M. Haque, and K. Ki-Doo, “High Precision Indoor Positioning Using Lighting LED and Image Sensor”, 14th International Conference on Computer and Information Technology (ICCIT), pp. 309314, December 2011. [9] L. Pengfei, Z. Min, Z. Xiang, C. Guangming, H. Dahai, and L. Qing, “An Indoor Visible Light Communication Positioning System Using DualTone Multi-Frequency Technique”, 2nd International Workshop on Optical Wireless Communications (IWOW), pp. 25-29, October 2013. [10] S. Yang, E. Jeong, D. Kim, H. Kim, Y. Son, and S. Han, “Indoor threedimensional location estimation based on LED visible light communication”, Electronics Letters, vol. 49, no. 1, pp. 54-56, January 2013. [11] S. Jung, C. Choi, S. Heo, S. Lee, and C. Park, “Received Signal Strength Ratio Based Optical Wireless Indoor Localization Using Light Emitting Diodes for Illumination”, IEEE International Conference on Consumer Electronics (ICCE), pp. 63-64, January 2013. [12] S. De Lausnay, L. De Strycker, J-P. Goemaere, N. Stevens, B. Nauwelaers, “Optical CDMA Codes for an Indoor Localization System using VLC”, 3rd International Workshop on Optical Wireless Communications (IWOW), pp. 50-54, September 2014.
Experimental Investigation of VCSEL for Quantum Communications Ágoston Schranz Department of Broadband Infocommunications and Electromagnetic Theory Budapest University of Technology and Economics Budapest, Hungary
[email protected] Abstract—Quantum communications is one of the most researched fields in recent years. An important application of quantum communications is Quantum Key Distribution (QKD), for which several provably secure protocols, like the BB84, have been proposed. These protocols rely on a quantum channel that is able to transmit single photons. This can be implemented by using very low-power coherent light sources where values of bits are encoded in the polarization of photons. In order to achieve this, it is essential to provide a stabilized output power laser and sufficient attenuation that is time-independent as well. Measurements of a vertical cavity surface-emitting laser (VCSEL) and its circuitry (intended for use as a free-space QKD transmitter) are presented.
pre-set value by driving current through a thermoelectric cooler using the Peltier effect. The heat transfer is aided by a block of aluminium (to which the laser is mechanically tied) and heat conductive paste. A.
Current Versus Optical Power In the measurement setup (Fig. 5.) the laser controller provides the bias current and the temperature control for the VCSEL. The light of the laser diode is guided to the optical multimeter through a single mode optical patch cord. Fig. 1. represents the output optical power versus bias current curves of the tested transmitter. Below the threshold current (approximately 2.3 mA) the laser’s output power barely changes with increasing current, above the threshold up until 6 mA it shows a linear characteristic, at higher bias currents the slope starts to decay and a break-off appears.
Keywords-VCSEl, quantum key distribution, laser, optical attenuation, free-space optical link
I.
The slope of the curve is approximately 79.5 µW/mA. The borders of the 95% confidence interval are 78.38 and 80.62 µW/mA. However, the curve depends on the actual temperature, therefore it was measured in two more different temperature values, at 20 and 30 °C. Theoretically, lasers have a negative temperature coefficient, meaning that their output power decreases with increasing temperatures [2]. The measured curves confirm the theoretical expectations: the three curves have slightly different slopes. Fig. 2. shows that the difference of two curves measured at two different temperatures mainly depend on the difference between the temperature values.
INTRODUCTION
This paper presents about the design and construction of an 850 nm VCSEL-based [1] laser transmitter with built-in temperature control. The transmitter was characterized and it was experimentally investigated how the output power and the laser spectrum changes as a function of temperature and bias current. Additional elements of the QKD transmitter are also discussed, including a programmable attenuator, a collimator and polarization filters. For free-space quantum key distribution schemes, it is essential to analyze elements and parameters of a low-power link, as in some proposed schemes [3] every bit is carried by a single photon. Therefore, further measurements were conducted on the full system analyzing long-term stability. II.
THE TRANSMITTER
A vertical-cavity surface-emitting laser was applied. The device (LDM-850-V) is operated at 850 nm and it has SC receptacle. The fabricated transmitter includes temperature control and a stabilized bias current source. The temperature sensor is a 10 kΩ NPC thermistor, the laser diode controller controls the temperature to reach and settle around a
Figure 1. Temperature dependence of the VCSEL’s current versus output power curve. At higher temperatures, the threshold current is higher and output power is less for a given value of current.
8
The 30/25 and 25/20 °C difference curves are showing similar tendencies apart from some fluctuation, but the difference of values measured at 30 and 20 °C are almost twice the value if the bias current is higher than the threshold. (Below the threshold there is no significant temperature dependence.)
difference; above threshold the power difference depends mostly on the temperature difference.
In order to be able to consistently emit a single output photon per impulse, stable output power is a key issue, the stability of temperature control cannot be neglected. After turning on the regulation, the stability was analyzed in multiple configurations: using single-mode (SM) and multi-mode (MM) fiber at 2 and 6 mA and SM fiber at 4.5 mA. The experiments showed that variances around the mean value do not depend neither on the type of fiber nor the bias current. Letting the regulation work for a sufficiently long time, the differences are in the range of ±1% around the average, apart from some rare extreme values.
B.
Spectrum of the VCSEL The spectrum of the laser light was observed by several bias currents: below the threshold (1 mA), around the threshold (2.1 mA) and in multiple points of the linear section. Under the threshold current a uniform noise level was measured in the full wavelength range. Around 2.1 mA the laser modes start to appear and get distinguishable from the noise. As the current was increased, more and more peaks turned up, meaning that the VCSEL is a multi-mode laser. There is a slight aberration (about -10 nm) in the central wavelength: most of the power is concentrated in between 839 and 841 nm. This difference is low enough to remain in the operational range of all the devices used in the experiments. Using different bias currents different modes carry the highest power (e.g. 839.79 nm, 840 nm). Additionally, the wavelengths of modes also depend on the biasing: increasing the current the spectrum slightly moves towards the longer wavelengths.
III.
As the long-term goal is to communicate using single photons, attenuation of the light leaving the transmitter is necessary. It is also important that the attenuation value be controllable, stable in time and easy to reproduce. Two different instruments had been characterized: the Anritsu MN924A, a manually adjustable attenuator and the Anritsu MN939C, which is programmable. Both of them are meant to be used in wavelength windows widely used in optical communications, 1310 nm and 1550 nm.
Furthermore, it is also necessary to describe the spectral width of the laser more accurately. TABLE I. concludes the measured central wavelengths and spectral widths (Δλ), where the limits of the band are defined as an ‘n’ dB decrease below the maximal value. The width defined for half power (-3 dB) is 0.462 nm, for 25% power (-6 dB) it is 0.7 nm. These values represent a relatively wide spectrum for a semiconductor laser. TABLE I.
After a calibration meant to provide a reference point and to eliminate the – albeit minimal – effect of the fiber patch cords’ attenuation, the attenuation curves were measured for both instruments (Fig. 5.). All measurements were conducted with a bias current of 4.5 mA in a temperature of 25 °C. A.
Non-Programmable Attenuator The instrument has two knobs, one of which is able to set the attenuation with a 10 dB step between 0 and 50. This knob has discrete values, meaning that there are no possible intermediate values, the change of state is clearly marked by a click, making it easy to reproduce the set value. The other knob (fine-tuner), on the other hand, can be rotated continuously between attenuations 0 and 15 dB. With the help of this knob finer tuning of attenuation is possible, but because of its continuous nature, repeatability is questionable.
VCSEL SPECTRAL WIDTHS
BW limit
λcentral (nm)
Δλ (nm)
-3 dB
840.054
0.462
-6 dB
839.94
0.7
-10 dB
839.932
0.717
-20 dB
839.658
1.84
CHARACTERIZATION OF OPTICAL ATTENUATORS
The effects of the knobs were examined separately on their full range, with the other knob being turned to 0 dB of attenuation level. The insertion loss of the instrument was measured to be 6.7-6.9 dB at 850 nm. Subtracting the insertion loss from the array of values, it becomes easier to observe the relationship between the set and measured attenuation values. This can be seen in Fig. 3. (Red curve represents the total attenuation; blue curve represents the attenuation minus the insertion loss). Using the fine-tuner, the attenuation above the insertion loss is almost identical to the set value even at 850 nm: the highest difference amidst the 15
Figure 2. Optical power differences between curves measured at different temperatures. Below threshold there is no significant
9
measurement points is 0.37 dB, the average difference is only 0.0531 dB. On the contrary, using the 10 dB knob the set levels are a good approximation of experimental values only up until 20 dB. Using higher values of attenuation the curve starts to get steeper. At 50 dB, the measured additional attenuation (not counting the insertion loss) is found to be 58.15 dB. It becomes clear in this range, that the instrument was not calibrated at this wavelength. However, a serious problem arises from the questionable repeatability of the values set by the continuously changeable finetuner. This can be cancelled by using the programmable attenuator.
Figure 4. Attenuation curve @850 nm of the programmable attenuator (red – measured with lower sensitivity device – & blue). Green is the reference curve @1310 nm. At 850 nm the insertion loss is significantly higher, the curves are steeper and sudden discontinuities occur.
B.
Programmable Attenuator Given that MN939C is a programmable attenuator, it was possible to measure its attenuation in more sample points than in case of the MN924A. A measurement was conducted in 601 different values of set attenuation in the range of 0 to 60 dB, using a uniform step size of 0.1 dB. The window setting was chosen to be 1310 nm, as it is closer to the wavelength of interest. This seems to indicate that the measured curve will be more similar to the 1310 nm curve than the 1550 nm one.
C.
Optical Power Splitter & Time Stability of Attenuation An optical power splitter was also investigated. The optical fiber-based device is meant to be used at 1310 nm, it has one input and two output ports with a nominal split rate of 95% – 5%. At 850 nm, however, the measured rate is 97.8% – 2.2%. During the measurement, the output ports were connected to the two optical multimeters. The monitor port was connected to the instrument with higher sensitivity, in order to minimize the probability of errors. The laser was thermally stabilized to 25 °C and biased at 4.5 mA. As mentioned before, keeping the output power unchanged is essential. In order to achieve this, it was needed to observe how the attenuation changes in time. Connecting the laser to the power splitter both of its output ports were monitored (one being attenuated beforehand, the other not) for the sake of eliminating the effects of temperature fluctuation (Fig. 5.). The programmable attenuator was found to have a time variance of approximately ±0.2 dB (±2%) at 10 dB set attenuation.
For reference, the attenuation curve at 1310 nm was measured as well. The current-power relationship at 850 nm was measured using two multimeters with different sensitivity. Above 35 dB of set attenuation the instrument with lower sensitivity starts to reach its noise level, therefore the slope of the curve gradually decreases. Below 35 dB of set attenuation the two curves are almost identical. There are two upfront differences between the reference curve (1310 nm) and the curve measured at 850 nm. First, the insertion loss has greatly increased (6.9-7.3 dB instead of 1.69 dB). The second is the presence of sudden jumps, discontinuities. As the latter is confirmed by two independent measurements, the possibility of it being a measurement error can be excluded. Apart from these sections, the slope of the curve is almost equal to that of the reference (Fig. 4.).
IV.
POLARIZATION MEASUREMENTS IN THE FREESPACE LINK
For the quantum communication scheme proposed in [3], there is a need for orthogonal linear polarizations. After setting up a free-space link, it was analyzed whether the light of the VCSEL was by itself linearly polarized or not. The link setup is based on an optical pad, positioned and held in a fix place to avoid errors originating from mechanical impacts. In addition to the transmitter and the programmable attenuator, the link also consists of a collimator that couples infrared light from the fiber into free space and a polarization beam splitter cube. The cube has a mirror which deflects horizontally polarized light by 90° but lets vertically polarized light pass through. Light coupled into free-space is directed to the input of the beam splitter. Using photodiodebased receiver circuits in the same distance from both outputs, the DC level of the voltage (that is proportional to the optical power) was measured in
Figure 3. Attenuation curve @850 nm of the non-programmable attenuator using the 10 dB knob including (red) and excluding (blue) insertion loss. The curves are steeper at this wavelength than at 1310 nm.
10
25 °C and biased at 6 mA.
both polarizations (Fig. 5.). The laser was stabilized to
Figure 5. Experimental setup. Yellow arrows represent optical fibers, dotted red arrows represent infrared free-space links.
For P (vertical) polarization the multimeter measured 51 mV at the output of the receiver, for S (horizontal) polarization this voltage was 58 mV. Given that these two values are in the same order of magnitude, it can be deduced that the light of the VCSEL is not polarized in either direction. As a conventional fiber patch cord may rotate the polarization, this measurement needs to be repeated using a polarization maintaining fiber. V.
ACKNOWLEDGMENT I would like to thank the help of Eszter Udvary, Gábor Fekete, Tamás Szili and Zsolt Kis.
SINGLE PHOTON DETECTOR COUNT DISTRIBUTION IN A LIGHT PULSE
A low-accuracy determination of photon statistics was also conducted. Using a single-photon detection module in place of the previous detectors several waveforms with different laser power (denoted by η in Fig. 6.) were recorded. Operating the VCSEL in CW mode, 100 ns long light pulses were simulated by applying a window to the measured waveform. The relative frequency of the number of detector impulses (“clicks”) in a 100 ns long time window was calculated. The lower the power, the more the distribution converges to an ideal Poisson-distribution. This is due to the effect that non-zero detector signal length and dead time limit the possibility of more detector signals in a window.
Figure 6. Relative frequency of the number of detector impulses using three different values of laser power. At lower power (blue) the distribution is close to an ideal Poisson-distribution, at higher power (green & red) the detector’s dead time limits the maximum number of impulses, causing distortion in the distribution.
REFERENCES [1]
CONCLUSION Results presented in this paper form a good basis for possible future quantum communicational connections using the polarization state of single photons to carry information. Experiments showed that the properties of applied devices are sufficient for this application, as they are able to provide a thermally stable environment for the laser to operate, maintain a constant value of attenuation to control output power. Future investigations should be carried out to implement two output ports for the transmitter which emit orthogonally polarized photons, and to realize the single-photon state of the light.
[2]
[3]
11
R. Michalzik, K. J. Ebeling. “Operating Principles of VCSELs”, Vertical-Cavity Surface-Emitting Laser Devices, Springer Series in Photonics, volume 6, pp. 53-98, 2003 Alfred R. Adams, Masahiro Asada, Yasuharu Suematsu and Shigehisa Arai “The Temperature Dependence of the Efficiency and Threshold Current of In1-xGaxAsyP1-y Lasers Related to Intervalence Band Absorption, Japanese Journal of Applied Physics, volume 19, number 10, 1980 C. H. Bennett and G. Brassard. "Quantum cryptography: Public key distribution and coin tossing", Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, volume 175, page 8. New York, 1984
Szélessávú impedanciaillesztés, szabadtéri kommunikácós célra használt VCSEL-hez Balázs Matolcsy (Szerző)
Dr. Zólomy Attila (Konzulens)
Budapesti Műszaki és Gazdaságtudományi Egyetem Szélessávú Hírközlés és Villamosságtan Tanszék Budapest, Magyarország
[email protected]
Budapesti Műszaki és Gazdaságtudományi Egyetem Szélessávú Hírközlés és Villamosságtan Tanszék Budapest, Magyarország
[email protected]
A modern költséghatékony kommunikációs rendszerek egy kiemelt kutatási területét képezik a VCSEL-alapú optikai kommunikációs rendszerek. Egy lehetséges alkalmazás, a VCSEL-alapú szabadtéri optikai kommunikáció. Mivel a szabadtéri optikai összeköttetések (Free Space Optical) lehetséges alternatívái a mikrohullámú összeköttetéseknek, ezért az adó lézerek számára megfelelően nagy sávszélességet kell biztosítani. Ehhez elengedhetetlen, hogy az adók (pl. VCSEL-ek) számára a teljes működési frekvenciatartományban megfelelő impedancia illesztést biztosítsunk. A cikk célja, egy analitikus impedancia illesztési módszer bemutatása, szabadtéri kommunikációban használt VCSEL-ek részére.
II.
TECHNIKÁK
Széleskörűen tárgyalt témája a szakirodalomnak a keskenysávú, komplex impedancia illesztési technikák több fajtája is. Ezen technikák kidolgozottsága szinte teljesnek tekinthető, és valamennyihez ismert analitikus, vagy numerikus leírás. Azonban a szélessávú impedancia illesztési technikák közül már jóval kevesebb ismert analitikus formában, illetve tetszőleges komplex lezárásra adott megoldással. Ezen illesztési technikákat H.W. Bode, R.M. Fano és Youla munkája alapozta meg. Elsőként Bode talált olyan elméleti korlátokat, amelyek segítségével meghatározhatjuk, hogy egy tetszőleges komplex impedanciát illesztve egy adott sávban, milyen minőségű illesztésre számíthatunk. Ezt nevezik a Bode-féle elméleti határnak, amely explicit kifejezést ad az elérhető legjobb reflexiós tényezőre, adott impedancia viszonyok mellett, egy meghatározott frekvenciasávon. Az analitikus formulák matematikai komplexitása miatt, Bode az elméleti határokat [5] csak egyetlen speciális lezárásra: párhuzamos R-C-re vezette le. Később R. M. Fano [6] munkássága révén, az elméleti határokat több típusú lezárásra is származtatták. Youla ezen határformulák segítségével kidolgozott egy olyan tetszőleges impedanciára vonatkozó illesztési módszert, amellyel elvileg bármilyen komplex impedanciát lehetséges illeszteni [7]. Ezen illesztési módszer tervezési egyenletei, matematikai bonyolultságuk miatt, kizárólag párhuzamos R-C lezárásokra ismertek. A Bode által kidolgozott illesztési módszer alapját képezte a Darlington-szintézis, mely szerint bármilyen komplex valós értékű impedancia helyettesíthető egy olyan L-C létrával, melynek lezárása egy tisztán valós egységnyi értékű ellenállás. Bode ennek segítségével visszavezette a problémát a kettős lezárású szűrők tervezésére. A következőkben a, Bode és Fano által kidolgozott szintézis módszert alkalmazom.
Kulcsszavak: impedancia illesztés, VCSEL, FSO, Bode-Fano módszer. lézer illesztés, szélessávú illesztés
I.
KESKENY- ÉS SZÉLESSÁVÚ IMPEDANCIA ILLESZTÉSI
BEVEZETÉS
A szélessávú infokommunikációs rendszerek iránti intenzív keresletnek köszönhetően megnőtt az érdeklődés, a mikrohullámú linkek alternatívájaként használható, optikai alapú kommunikációs rendszerek felé. [1] Ennek egy lehetséges alkalmazása, a szabadtéri optikai kommunikációs rendszer, azaz FSO (Free Space Optic). Több tanulmány témáját képezi olyan szabadtéri optikai link, amelyben az FSO link adó oldalán, úgynevezett VCSEL-eket alkalmaznak [2] (Vertical Cavity Surface Emitting Laser). Az ilyen típusú lézerek jelentős előnye a költséghatékonyság, és jobb megbízhatóság (a hagyományos oldalsugárzó lézerekhez képest). [3] Minden optikai adó oldali eszköz esetében fontos, hogy a rádiófrekvenciás tartománybeli jeleket megfelelő hatásfokkal tudják átalakítani optikai tartománybeli jelekké. Ehhez szükséges, hogy az adó lézert (pl. VCSEL, Fabry-Perot, DFB stb.) rádiófrekvenciás szempontból illesztetten vezéreljük, azaz, megfelelő impedancia illesztési hálózaton keresztül tápláljuk az RF jelet a az adó lézerbe [3]. Megfelelő illesztés esetén a lézer impedanciája (kiegészítve az illesztő hálózattal) éppen megegyezik a tápláló jelforrás komplex impedanciájának a konjugáltjával [4]. Esetünkben a jelforrás kimeneti impedanciája 50 Ω , és a -10 dB, és annál alacsonyabb bemeneti-reflexiós értékeket tekintjük elfogadható illesztettségnek. Bemutatásra kerül egy analitikus szélessávú impedancia illesztési módszer, melynek segítségével -10dB bemeneti reflexiónál, akár 50% feletti relatív illesztett sávszélesség érhető el.
III.
AZ ANALITIKUS IMPEDANCIA ILLESZTÉS MENETE
Elsőként meg kell határozni, hogy milyen elméleti illesztett sávszélességre számíthatunk az adott eszközre vonatkoztatva. Ehhez szükséges, hogy az illesztendő eszköz (VCSEL) impedanciáját klasszifikáljuk, úgy, hogy olyan helyettesítő impedancia modellt hozunk létre, amely egyrészt megfelelően illeszkedik a VCSEL impedancia-görbéjére (adott frekvencia tartományban), másrészt a modellre vonatkozó Bode-Fano-féle elméleti illesztési határok, és eljárások érvényesek. [8] Ismert, hogy a VCSEL impedanciája modellezhető soros R-L impedanciával, mivel a tokozás
12
(TO-18) hozzávezetései, és a tokozáson belüli bondolás induktív jelleget mutat, egy adott, későbbiekben ismertetett frekvenciatartományban. Az elméletileg elérhető maximális bemeneti reflexiók (illesztettséggel ekvivalens) [6]:
használtam, ezáltal megkaptam a soros hangoló kapacitás értékét: 𝐶𝑠𝑜𝑟𝑜𝑠 =
Soros R-L lezárás esetén: Γmax = 𝑒
1
⋅ = 2.20 𝑝𝐹
(4)
𝐿
A sáváteresztő struktúrák formulái alapján a következőkre számíthatunk, mint elméleti maximális illesztettségi határok:
−𝜋 ⋅𝑅 𝐿⋅𝜔 𝑙
(1) Γmax = 𝑒 −𝜋⋅𝛿 = 𝑒
Sáv-áteresztő struktúra esetén: Γmax = 𝑒 −𝜋⋅𝛿 = 𝑒
−𝜋⋅
𝜔 1 ⋅𝜔 2 1 ⋅ 𝜔 2 −𝜔 1 𝑄
𝑅
𝜔 1 ⋅𝜔 2 1 ⋅ 𝜔 2 −𝜔 1 𝑄
= −25.2 𝑑𝐵
𝐿
(5) (6)
𝑅
A számított eredmények alapján, és a jósági tényező ismeretében állítható, hogy elérhető a kitűzött illesztettség ebben a frekvencia sávban. A dekrementum ismeretében meghatározhatóak a Chebyshev-féle alul áteresztő prototípus struktúra elemértékei, felhasználva Matthei nomogrammjait [9]. Jelen alkalmazásban (és általánosan single-reactance esetben is) 2, vagy 3 elemű alul áteresztő prototípust elegendő használni [8]. Az elemértékek számításához segítséget nyújtanak, Green iteratív formulái [9].
Soros R-L-C struktúra esetén: 𝜔 0 ⋅𝐿
−𝜋⋅
𝑄 = 𝜔0 ⋅ = 1.3; 𝛿 = 1.8
(2)
ahol Γ𝑚𝑎𝑥 az adott frekvenciasávon értelmezett bemeneti reflexiós tényező maximális értéke (ez alá az érték alá nem mehetünk a teljes tartományon), 𝛿 az impedancia jellemző dekrementum, 𝜔1 és 𝜔2 az illesztési sávhatárok, és Q a sáváteresztő struktúra jósági tényezője.
𝑄=
1 2⋅𝜋⋅𝑓0 2
(3)
A Bode-Fano féle illesztési technika megköveteli az impedancia identifikációt (vagy más néven klasszifikációt), ezért a következőkben a mérési eredmények alapján meghatározom, hogy milyen impedancia modell illik az adott VCSEL-hez (párhuzamos R-C, soros R-L stb.) Az első lépés megmérni az illesztendő eszköz komplex impedancia menetét a frekvencia függvényében az 500 MHz ... 4 GHz tartományban. Ehhez a méréshez a vektor hálózat-analizátort használtam (VNA):
2. ábra - Alul-áteresztő prototípus hálózat elemértékei
A fenti ábrán látható, hogy a (Darlington szintézis feladat megoldásaként adódó) generátor impedanciája nem lehet tetszőleges, ezért impedancia inverter fokozatok alkalmazására lesz szükség a későbbiekben (ezek használatával eggyel több szabadsági fokunk lesz, a generátor impedanciáját megválaszthatjuk pl.: 50 Ω -nak). Az impedancia inverter struktúra elem-értékeit meghatároztam [8] [9] alapján, 3 elemű esetre: 1. TÁBLÁZAT - IMPEDANCIA INVERTER ELEMÉRTÉKEK 𝑪𝟐
𝑪𝟑
𝑪′𝟐
𝑪′′𝟐
𝑪′𝟑
𝑪′′𝟑
𝑱𝟐𝟑
𝑵𝟐𝟑
1.05
0.8623
0
1.05
1.05
-0.1878
0.0314
3.464
A microstrip struktúrára tervezett hálózat elemei, negyedhullámhosszú rövidre-zárt csonkok, melyek impedanciái számíthatók az ide vonatkozó egyenletekkel [8][9], ahol 𝑍𝑥𝑦 a keresett impedancia értékek.
1. ábra - A modell impedancia menete (kék) a VCSEL mellett (fekete)
𝜃1 = 2 ⋅ 𝜋 ⋅ 1 −
Az 1. ábra alapján, a VCSEL impedanciája az adott frekvenciatartományban az induktív fél-síkon helyezkedik el, ezért illeszthető rá egy soros R-L helyettesítő modell, amely impedancia menetének illeszkedése megfelelő az 1150...1600 MHz tartományban. A helyettesítő modell R és L értékeinek meghatározása optimalizációval történt (simplex algoritmus) (R = 39.12 Ω, L = 6.11 nH). A VCSEL impedancia-menete alapján megállapítottam, hogy a VCSEL-t soros rezonanciára [8] célszerű hangolni. Ehhez a megfelelő Thomson formulát
𝑤= 𝑌02 = 𝐶2′ ⋅ 𝑌03 = 𝐶3′′ ⋅
tan θ 1 𝑅𝑔 ⋅𝑔 0
tan θ 1 𝑅𝑔 ⋅𝑔 0
+ +
1 𝑅𝑔
1 𝑅𝑔
𝑤 2
(𝑓𝑚𝑎𝑥 − 𝑓 𝑚𝑖𝑛 ) 𝑓𝑐𝑒𝑛𝑡𝑒𝑟
(8)
⋅ 𝑁23 − 𝑅𝑔 ⋅ 𝐽23 → 𝑍02 = 17.92 Ω (9)
⋅ 𝑁23 − 𝑅𝑔 ⋅ 𝐽23 → 𝑍03 = 24.24 Ω (10)
𝑌23 = 𝐽23 → 𝑍23 = 31.85 Ω
13
(7)
(11)
A számított impedancia értékek alapján már felépíthető az illesztőhálózat, szimulációs környezetben. IV.
SZIMULÁCIÓS ELRENDEZÉS ÉS EREDMÉNYEK
Az illesztő hálózat működését szimulációs környezetben (AWR Microwave Office) ellenőriztem, két típusú realizáció esetén: ideális koaxiális tápvonalas, microstrip struktúrás realizáció.
3. ábra - Ideális, koncentrált elemű, koaxiális tápvonalas realizáció
A 3. ábrán, illetve az 5. ábrán a szimulált hálózat (illesztő és lezárás) sematikus ábráját jelenítettem meg. Mindkét sematikus ábrán (3,5) a bal oldalon szerepel a bemenet, és jobb oldalon a lezárás. A szimulált bemeneti reflexiós görbék (4. és 6. ábra) a sematikus ábrák alatt találhatóak. Az ideális koaxiális tápvonalas szimuláció esetében, (3. és 4. ábra) az optimalizált (magenta színnel), és az analitikusan számított elemértékekkel (kék színnel) felépített illesztő hálózat bemeneti reflexió görbéje látható, ideális, koncentrált paraméterű elemekből felépített lezárás esetén (soros R-L). Ez a szimulációs eredmény megfelel az illesztéssel szemben, előzetesen ismertetett követelményeknek, a 921...1812 MHz-es frekvenciasávban. Az FR4-es típusú hordozón megvalósított, microstrip struktúrás illesztő hálózat szimulációs eredménye a 6. ábrán látható. Ennél az elrendezésnél, a lezárás a mért VCSEL impedancia volt. Megfigyelhető a microstrip tápvonalas illesztő hálózatok által okozott periodicitás a bemeneti reflexió frekvenciamenetében (6. ábra). A szimuláció ebben az esetben is megfelelő eredményt adott (912...1801 MHz frekvenciasávon -10 dB alatti bemeneti reflexió). A szimulációs eredmények értékeléséhez érdemes kiemelni, hogy, bár az elméleti illesztettségi korlát ennél kisebb maximális reflexiót ír elő (-25 dB), a Bode-Fano féle analitikus illesztési eljárás nem garantálja, hogy ezt elérjük az adott frekvenciasávon. V.
MÉRÉSI EREDMÉNYEK
A szimulációs eredmények alapján realizáltam az illesztő hálózatot, FR4-es hordozón, microstrip struktúrákkal. Két féle mérési elrendezést is készítettem a szimulációs eredmények igazolása végett. Az első felépítésben az illesztendő impedancia, a klasszifikálás eredményeképpen adódó elemértékű, koncentrált paraméterű, nagyfrekvenciás, nagy jósági tényezőjű SMD induktivitásból és vele sorosan kapcsolt (szintén SMD) ellenállásból állt (modellezett soros R-L impedancia). A második esetben az illesztő hálózat közvetlenül a VCSEL-hez kapcsolódott. Mindkét mérési eredmény a 7. ábrán látható.
4. ábra - Ideális koaxiális tápvonalas illesztés szimulációs eredménye (a helyettesítő modellre)
A modellező impedancia esetében rosszabb eredményt kaptam, mint a szimulált esetben, de ez nem olyan jelentős, mint a VCSEL esetében, ahol az impedancia illesztés nem lett elfogadható (7. ábra). Ennek oka, hogy az illesztés minősége függ, a VCSEL hozzávezetési induktivitásától, a forrasztástól, illetve a hordozó relatív dielektromos állandójának pontosságától, és a forrasztott elemek (soros rezonanciára hangoló kapacitás) parazitáitól. Az eredmények alapján a probléma oka, hogy a VCSEL impedanciája változott, a mérési eredményhez képest (forrasztási és mechanikai változások). Ez kiküszöbölhető lehet, egy olyan elrendezéssel, ahol a VCSEL egy mechanikailag rögzített csatlakozón keresztül mérjük, és illesztjük. Így a jövőben kiemelt figyelmet kell fordítani a VCSEL impedanciájának mérésére, mivel ez kulcsfontosságú az impedancia klasszifikációhoz, ami a lényegét adja ennek az illesztési technikának.
5. ábra - Microstrip struktúrás realizáció
6. ábra - Microstrip struktúrás illesztés szimulációs eredménye (a mért VCSEL impedanciára)
14
Schranz Ágostonnak, Berceli Tibornak, továbbá kimagasló hálával tartozom Fűzy Csabának úttörő munkásságáért a témában. REFERENCIÁK [1]
[2]
7. ábra - Modellező impedancia, és VCSEL illesztési eredmények [3]
KONKLÚZIÓ A Bode-Fano-féle impedancia illesztő módszer megfelelő eredményeket ad olyan esetekre, amikor az illesztendő impedancia megfelelően modellezhető egyszerű helyettesítő impedanciákkal. Az eljárás legfontosabb lépése, emiatt az illesztendő eszköz impedanciájának mérése és klasszifikációja, amit különös körültekintéssel kell végrehajtani, mivel erőteljesen befolyásolja az illesztés minőségét. Ezzel a fajta illesztési módszerrel, stabil körülmények közt, megfelelően viselkedő impedancia esetén, nagy illesztett sávszélességet érhetünk el (50% relatív sávszélesség).
[4]
[5] [6]
[7] [8]
KÖSZÖNETNYILVÁNÍTÁS Meg szeretném köszönni a segítséget, és az inspiráló környezetet az OMT-LAB munkatársainak: Mészáros Gergelynek, Szalay Zoltán Attilának, Szili Tamásnak,
[9]
15
N. Zdravković, M. I. Petkovic, G. T. Djordjevic and K. Kansanen, "Outage Analysis of Mixed FSO/WiMAX Link," in IEEE Photonics Journal, vol. 8, no. 1, pp. 1-14, Feb. 2016. doi: 10.1109/JPHOT.2016.2516250 M. Yoshikawa, A. Murakami, J. Sakurai, H. Nakayama and T. Nakamura, "High power VCSEL devices for free space optical communications," Proceedings Electronic Components and Technology, 2005. ECTC '05., 2005, pp. 1353-1358 Vol. 2. doi: 10.1109/ECTC.2005.1441445 G. Fehér, C. Fűzy, A. Zólomy and T. Berceli, "Multi-band impulse filtered UWB signal transmission by wideband optical VCSEL transmitter," Microwaves, Radar and Remote Sensing Symposium (MRRS), 2011, Kiev, 2011, pp. 114-117. C. Fűzy, A. Zólomy: Design of Broadband Complex Impedancematching Networks and Their Applications for Broadbanding Microwave Amplifiers (YSC) 4th Microwave and Radar Week MRW-2010, June 1416, Vilnius, Lithuania Hendrik W. Bode ,Network Analysis & Feedback Amplifier Design Van Nostrand, 1945. Theoretical Limitations on the Broadband Matching of Arbitrary Impedances, R.M. Fano, TECHNICAL REPORT NO. 41, January 2, 1948. Youla - A NEW THEORY OF BROADBAND MATCHING, Polytechnic Institute of Brooklyn NY, Jan 1964 Investigations of Wideband Impedance Matching in Microwave Amplifiers, Csaba Fűzy, Master's Thesis, Budapest University of Technology and Economics, 2010 G. L. Matthei, Leo Young, E.M.T. Jones, Design of Microwave Filters, Impedance Matching Networks, and Coupling Structures Volume 1 pages 130-150, Stanford Research Institute, CA US
2,5kW/50V-os Li-ion töltő DC/DC teljesítményfokozatának tervezése Csizmadia Miklós
Szeli Zoltán
Automatizálási Tanszék Széchenyi István Egyetem M.Sc. szakos villamosmérnök hallgató Győr, Magyarország
[email protected]
Automatizálási Tanszék Széchenyi István Egyetem egyetemi tanársegéd Győr, Magyarország
[email protected]
Kivonat—Cikkünk
egy 2,5kW-os lítium alapú akkumulátorok töltésére alkalmas töltő fejlesztését mutatja be. A töltő alkalmazható 12 db,- a villamos járművekben is alkalmazott lítium alapú akkucellából álló csomagok gyorstöltésére, maximum 50A értékű áramerőséggel. Részletesen foglalkozik az egészhidas konverter tervezésével, a szükséges számításokkal és szimulációkkal, a kialakított hardveres védelmekkel, valamint a működéséhez szükséges kiegészítő áramkörök tervezésével. Bemutatja a kapcsolási rajzok alapján elkészített huzalozási terveket és a teljes áramkör látványtervét.
feszültségre. A DC-DC konverter számára szükséges vezérlőjeleket egy (iii) processzoros vezérlő biztosítja. Feladata többek közt a szenzorok által mért értékek kezelése, a szabályozási rendszer felügyelete, valamint kommunikálás más eszközökkel CAN buszon vagy USB porton keresztül. III.
A tápegységek kimeneti feszültségének stabilizálása több módon is lehetséges, de napjainkban ez szinte kizárólag kapcsolóüzemben (impulzusszélesség-modulációval) történik. A kapcsolóüzemű feszültségszabályzó topológiák két fő részre bonthatók: (i) Az energiaátviteli áramkörre, illetve a (ii) szabályozó áramkörre [2]. A továbbiakban az energiaátviteli áramkör tervezésével foglalkozunk. Figyelembe véve az eszköz alkalmazását egészhidas konvertert választottunk, mely feszültségcsökkentő, galvanikus leválasztást biztosít, illetve a kívánt teljesítményt (> 1000W) kezelni képes (1. ábra).
Kulcsszavak—egészhidas konverter, kapcsolóüzem, flyback konverter, nagyfrekvekvenciás transzformátor, LTSpice, modell, szimuláció, gate-vezérlő
I.
A FEJLESZTÉS CÉLJA
Az akkumulátortöltő a Széchenyi István Egyetem Járműipari Kutatóközpontjában dolgozó hallgatói, és munkatársai által fejlesztett SZElectra névre keresztelt elektromos jármű Li-ion akkumulátor töltési folyamataiért lesz felelős [1]. Mivel az akkumulátortöltő célzottan e járműhöz készült, így paramétereit ennek megfelelően határoztuk meg: Az akkumulátortöltőnek 30V – 50V közötti tartományban kell stabilan működnie, 2500W-os kimenőteljesítmény mellett, hálózati feszültségről (230VAC). II.
TELJESÍTMÉNYFOKOZAT SPECIFIKÁLÁSA
A TÖLTŐ FELÉPÍTÉSE
A hálózatról működő tápegységek feladata sokrétű: A hálózati feszültség átalakítása a szükséges egyenfeszültséggé, annak stabilizálása, illetve a hálózatról való galvanikus leválasztás [2]. Nagyobb teljesítmények esetén a tápegységek bemenetén PFC (Power Factor Correction) áramköröket is alkalmaznak. Így az akkumulátortöltő három nagy fő részre bontható: A (i) PFC a hálózati zavarok csökkentésére és a pulzáló áram ingadozásának kiküszöbölése érdekében került a kapcsolás bemenetére. További fontos feladata, hogy nagymértékben csökkentse a hálózatra jutó meddő teljesítményt,- és javítsa a fázistényezőt. A PFC áramkört egy (ii) DC-DC konverter követ, amely a PFC 400V-os kimeneti feszültségét alakítja át az akkumulátorok által használt
1. ábra. Egészhidas konverter elrendezés Modern konverterek esetén ZVS (Zero Voltage Switching) kapcsolást alkalmaznak, mely a veszteségeket hivatott csökkenteni. Ez főként a szabályozási algoritmusban jelenik meg, de az energiaátviteli áramkör méretezése során is figyelembe kell venni. Egészhidas konverter esetén a kapcsolási topológia ellenütemű, továbbá a kapcsolási elrendezésből kifolyólag egy kapcsolási periódus alatt két átkapcsolás történik. A félvezetők párban működnek (T1-T4, illetve T2-T3), így a kapcsolási periódus egyik félperiódusában ellentétes irányú feszültség és áram alakul ki. Ez nagyban megterheli a félvezetőket. A nagy
16
terhelést és a magas feszültséget (400V) figyelembe véve a hídban IGBT-k (Insulated Gate Bipolar Transistor) végzik a kapcsolást. A topológia fontos eleme a nagyfrekvenciás transzformátor. Esetünkben az energiaátvitel 50kHz-en történik. Figyelembe vettük, hogy a kapcsolási topológia nagyban befolyásolja a transzformátor vasmagjának kiválasztását. Mindezeket szem előtt tartva a transzformátor vasmagja 3C95, E80/38/20-as típusú. A transzformátor menetszámát az (1) összefüggés határozza meg [3]:
𝑉𝑜 𝑉𝑖
=
𝑁𝑠 𝑁𝑝
𝑝ℎ − 𝐼𝑜 (
𝑁𝑠 2 𝐿𝑘 𝑁𝑃
)
𝑉𝑖
𝑓
kifejezetten IGBT-k számára specializált vezérlőre volt szükség, továbbá fontos volt, hogy kezelni tudja a 400V-os feszültséget, és beépített védelmekkel rendelkezzen.
Az (1) összefüggésben Vo a kimeneti feszültséget, Vi a híd bemeneti feszültségét, ph a maximális fázistolás értékét, Io a kimeneti áramot, Lk a transzformátor szórt induktivitását, míg f a kapcsolási frekvenciát jelöli. Fontos megjegyezni, hogy az átkapcsolás során jelentkező időintervallumot (energiatranszfer kimaradást, veszteséget) figyelembe kell venni, mivel nagy terhelés esetén ez vezérléskiesést okozhat (főleg ha nagy a transzformátor szórt induktivitása). Mivel az energiaátvitel nagyfrekvencián történik, így a szkinhatás miatt - egyetlen nagyobb keresztmetszetű vezető esetén az áram kiszorulna a vezető felületére. Ennek elkerülése érdekében több elemi vezetőből alakítottuk ki a tekercselő kábelt. Átmérőjüket a (2) összefüggés szerint méreteztük annak érdekében, hogy a teljes keresztmetszet részt vegyen az 4𝐼𝑅𝑀𝑆
d=√
𝜋𝐽
2. ábra. Főáramköri elrendezés Az választott, IGBT-ket meghajtó Infineon 1ED020I12FA2 típusú IC a következő fontosabb tulajdonságokkal rendelkezik [3]:
áramvezetésben. A (2) összefüggésben d a kábel átmérője, IRMS a rajta átfolyó áram, J pedig a megengedett áramsűrűség értékét jelöli. A konverter kimeneti oldalán is számos hatásfokjavító megoldás található. A kimeneti áramot két fojtótekercs vezeti, így egyenként kisebb a terhelésük, továbbá jobban el tudják disszipálni a veszteségi hőmennyiséget. A kimeneti fojtótekercsek esetén a szkinhatással nem kell foglalkozni, mivel a kimeneti áram nagy része DC áram. Azt, hogy mikor melyik tekercs vezet, a szinkron egyenirányító dönti el. Az egyenirányítást MOSFET-ek (Metal Oxide Semiconductor Field Effect Transistor) végzik. Mind az IGBT-k, mind az MOSFET-ek robusztus tokban (TO247AC) kaptak helyet, mely elősegíti a hőleadást, továbbá jobb rögzítést tesz lehetővé a hűtőbordára. A nagyfeszültségű és kimeneti oldalon található szűrőkapacitások az alkalmazásnak megfelelően méreteztük. Fontos volt, hogy alacsony ESR (Equivalent Series Resistance) értékkel rendelkezzenek, mivel a rajtuk keletkező veszteséget ez az érték nagyban befolyásolja. A töltő főáramköri elrendezése a 2. ábrán látható. IV.
IGBT-k meghajtásához használják (600V és 1200Vos típusokhoz); 2A rail to rail áramerősségű kimenettel rendelkezik; Egyetlen kapcsolóelem (IGBT) vezérlésre alkalmas; Beépített védelmekkel rendelkezik, Active Miller Clamp, illetve deszaturációs védelemmel;
Az első védelem (Active Miller Clamp) akkor szükséges, amikor a kapcsolóelemet kikapcsoljuk. Kikapcsoláskor a Miller kapacitásban (CGC) töltések halmozódhatnak fel, melyek az eszköz gate pontján (az emitterpontohoz képest) feszültségkülönbséget okozhatnak. A Clamp funkció ezt hivatott korlátozni túl nagy du/dt estén. A szaturáció az IGBT túlterhelése esetén okozhat problémát, mivel a nagyobb áram miatt a megengedettnél nagyobb feszültség is esik a félvezető eszközön. A vezérlő figyeli, hogy az IGBT szaturációs feszültsége a megengedett tartományban legyen. További megoldásként még Advanced Active Clamping megoldás is beépítésre került az IGBT vezérlőkörébe. A kapcsolási folyamatok során az IGBT kollektorán - az általa kezelni képesnél - nagyobb feszültség jelenhet meg. Ez az eszköz károsodásához, illetve annak tönkremeneteléhez vezethet. Ennek elkerülése érdekében egy előre beállított feszültségérték túllépése esetén az IGBT gate pontja nyitófeszültséget kap, bekapcsolva az IGBT-t. Ez egy önszabályozó folyamatot gerjeszt. A kívánt feszültségértéket szupresszor diódával lehet beállítani. V.
IGBT MEGHAJTÓ ÁRAKÖR
MÉRÉSI MECHANIZMUSOK
A helyes és pontos működés érdekében a különböző áram és feszültség értékeket mérni szükséges. Ezeket korszerű és hatékony módon valósítottuk meg.
Napjainkban számos gate-meghajtó található a piacon, ezek különböző funkciókkal rendelkezhetnek. Ebben az esetben
17
Az áramértékeket a nagyfeszültségű oldalon, valamint a kimeneti oldalon mérjük. A mérést Hall szenzorok végzik, melyek így izolált szenzorjeleket szolgáltatnak. A szenzor által szolgáltatott feszültségjeleket egy differenciaerősítő mozgatja a megfelelő tartományba, hogy a processzor számára is kezelhető értékűek legyenek. A nagyfeszültségű oldalon alkalmaztunk még egy túláram érzékelő áramkör is, mely a hídágban egy adott áramerősség felett a gate-vezérlőket letiltja. Ennek értéke egy komparátor referenciájának megváltoztatásával beállítható. Feszültségmérés csak a kimeneti oldalon történik. A helyes működés érdekében, galvanikus leválasztást kellett biztosítani a kimenettől. Ezt egy izolált műveleti erősítő (AMC1200) biztosítja, melynek energiaigénye csekély. VI.
3. ábra. AC/DC flyback szimulációs kapcsolás
SEGÉDTÁPEGYSÉGEK
A DC/DC konverter rendszerelemeinek helyes és pontos működéséhez szükségük van segédenergiára. A kívánt értékek szintén kapcsolóüzemű tápegységekkel valósítottuk meg. A nagyfeszültségű oldal számára egy flyback konvertert terveztünk, mely a hálózati feszültségből (230VAC) 12VDC-t állít elő. Az áramkört az NCP1200-as IC vezérli [5]. A feszültségérték megválasztása a hűtőborda ventilátor tápfeszültségének figyelembevételével történt. A flyback konverterre további feszültségcsökkentő konverter csatlakozik (LT1940) [6], mely a nagyfeszültségű oldalt kiszolgáló elemek (IGBT meghajtó, áramkorlát logika, LEM szenzorok) számára szolgáltat energiát. A pontos feszültségértékeket LDO-k (Low Dropout Regaulator) szabályozzák. Természetesen ez némi hatásfokbeli romlást okoz, de a szenzorok miatt fontos a pontos érték betartása. A kimeneti oldalon a szinkron egyenirányítókat meghajtó Gate-optocsatoló, illetve a feszültségmérést megvalósító izolált műveleti erősítő számára szükséges segédenergia. Mivel a kimeneti oldalt kiszolgáló feszültségcsökkentő konverter (LT3988) [7] energiafelvétele csekély, így a főáramkör kimentére csatlakozik. Mind a nagyfeszültségű, mind a kimeneti oldalt ellátó feszültségcsökkentő konverter a Linear termékcsaládból választottuk. A DC/DC konverterek szükséges értékeit az első táblázatban foglaljuk össze. I. TÁBLÁZAT
Nagyfeszültségű oldalon Kimeneti oldalon
4. ábra. AC/DC flyback szimulációs eredmények A szimulációban (4. ábra) a flyback konverter kimeneti feszültsége, áramerőssége, a kapcsolóelem VDS feszültsége, illetve annak gate vezérlőjele került vizsgálatra. VIII. VESZTESÉGEK, HATÁSFOK. A várható hatásfok a teljesítményegységre maximális terhelés esetén kb. 93%. A teljesítményfokozatot alkotó áramkörök veszteségeit külön-külön is megvizsgáltuk, LTSpice szimulációs környezetben (azokon a részegységeken, ahol könnyebb volt ily módon meghatározni a veszteséget), illetve matematikai úton is. A veszteségek megoszlását az 5. ábra szemlélteti.
SZÜKSÉGES FESZÜLTSÉG ÉS ÁRAMÉRTÉKEK
Feszültség [V] 5 3,3 5 20
Maximális áramerősség [mA] 625 660 10 50
VII. ÁRAMKÖRI SZIMULÁCIÓK A tervezés során az egyes áramköri részek kialakításánál szimulációk segítségével ellenőriztük a számításokat. A szimulációk a Linear által kifejlesztett LTSpice szimulációs környezetben történtek. Segítségével alkatrész szintű szimuláció végezhető. A teljesítményfokozat esetében az összes részegység esetében történt szimuláció. Az AC/DC flyback konverter szimulációs kapcsolását például a 3. ábrán láthatjuk.
5. ábra. Veszteségek IX.
DISSZIPÁCIÓ ÉS HŰTŐBORDA
A veszteségek függvényében a keletkezett hőmennyiség elvezetéséről gondoskodni kell. Ehhez hűtőbordát,
18
illetve egy - a bordára szerelt – ventilátort használtunk fel. A borda kiválasztása során a hőellenállásból indultunk ki, továbbá fontos volt a borda geometriája is. A ventilátor vezérléséről egy hiszterézises komparátor gondoskodik [8], mely egy adott hőfok (65⁰C) elérésekor be, majd egy adott hőfok (55⁰C) esetén kikapcsolja a ventilátort. X.
PCB TERVEZÉS
A számítási és szimulációs eredményekre alapozva áramkör tervező szoftver segítségével elkészítettük a kapcsolási rajzokat és a huzalozási terveket. Tekintve az áramkör nagyságát és bonyolultságát a PCB-t 4 rétegben készítettük el. A tervezés során nagy figyelmet kaptak a nagyáramú részek, méretüket az IPC-2152-es szabványnak megfelelően alakítottuk ki. Az elkészült teljesítményfokozat modellje a 6. és 7. ábrán látható. XI.
6. ábra. PCB huzalozási terv
PROTOTÍPUS PARAMÉTEREK
I I. TÁBLÁZAT
TELJESÍTMÉNYFOKOZAT PARAMÉTEREI
Alkatrész/Paraméter VIN (bemeneti feszültség) VOUT (kimenti feszültség) POUTMAX (maximális kimeneti teljesítmény) fSW (kapcsolási frekvencia) LOUT (kimeneti fojtótekercs) BMAX (transzformátor maximális mágneses indukciója) aTR (transzformátor áttétel) NP (primer menetszám) NS (szekunder menetszám) Lm (mágnesező induktivitás) LLK (szórt induktivitás) IGBT IGBT vezérlő Szinkron egyenirányító MOSFET
Típus/Érték 380V – 402V 30V – 50V 2500W 50kHz 133µH 330mT 3 12 4 969,12µH 10µH IHW20N65R5 1ED020I12FA2 IRFP4568PbF
7. ábra. Teljesítményfokozat 3D terv
XII. ÖSSZEFOGLALÁS, KONKLÚZIÓ A fejlesztés jelenlegi fázisában kész PCB tervekkel rendelkezünk. A projekt további részében a már meglévőt PCBtervek alapján elkészítjük a prototípust, illetve az egyedi alkatrészeket (nagyfrekvenciás transzformátor, kimeneti fojtótekercsek), majd a töltő további részegyeségeivel (PFC, vezérlő) összehangoljuk. A pontos működés érdekében további mérésekre és tesztekre lesz szükség, hogy a töltő a kívánalmaknak megfelelően működjön. A fejlesztés során az LTSpice-s szimulációs lehetőségek nagyban megkönnyítették a tervezés menetét, az alkarészek kiválasztását és a veszteségek meghatározását, főként a segédtápegységek méretezése során. Az eredmények az terveknek és az elvárásoknak megfelelően alakultak. A töltő vezérlő és szabályozóegységének szimulációját (összehangolva a jelen cikkben közölt energiaátviteli egységgel) Matlab környezetben futtatjuk, ugyanis a választott processzoros vezérlő számára a szimulációban alkalmazott vezérlő algoritmusok lefordíthatók, így az egyéb nyelven végzett kódírás elkerülhető, illetve a szabályozási rendszer működése jól átlátható.
XIII. KÖSZÖNETNYILVÁNÍTÁS Az akkumulátortöltő a TÁMOP-4.2.1.C-14/1/Konv-2015-0005 azonosító számú projekt keretében valósult meg. FORRÁS [1] [2] [3] [4] [5] [6] [7] [8]
19
http://www.infogyor.hu/hirek/olvas/permalink:szelectra-sajatfejlesztesu-elektromos-jarmu-gyorbol-2014-05-26-093729 Ferenczi Ö. Kapcsolóüzemű Tápegységek. Műszaki Könykiadó, Budapest, 1978. Sam Abdel-Rahman, „Design of Phase Shifted Full-Bridge Converter with Current Doubler”, Infineon Design Note, V1.0 January 2013. Infineon 1ED020I12FA2 Single IGBT Driver IC, Datasheet. Christophe Basso, „A 70W Low Standby Power Supply with NCP 120x Series”, ON Semiconductor. LT1940/LT1940L Dual Monolithic 1.4A, 1.1MHz Step-Down Switching Regulator, Datasheet. LT3988 Dual 60V Monolithic 1A Step-Down Switching Regulator, Datasheet. Art Kay, „Timothy Claycomb, „Comparator with Hysteresis Reference Design”, Texas Instruments , 2013 June 14.
Investigation of microchannel based heat sinks for VLSI circuits Károly Marák Budapest University of Technology and Economics, Department of Electon Devices control volume. The resulting solution implies that the integral conservation of quantities such as mass, momentum and energy is exactly satisfied for any control volume and of course, for the whole domain. A large benefit of this approach is the fact that with a numerical model it is easy to modify parameters and repeat experiments, while this cannot be said of experiments in a laboratory. Analytical models do exist, but they are only applicable in very simple cases [5].
Abstract—Since the dawn of integrated circuit (IC) technology, the number of electronic components and heat dissipation per unit surface is rapidly increasing. Although heat dissipation of the components decreases with size, transport of the heat generated in ICs poses a serious technological challenge and is a limiting factor in increasing computational capacity. One of the most promising solutions to the problem are microchannel coolers. The main idea behind them is to get the coolant close to where heat is dissipated, so channels are created in the silicon chip on which the ICs are created. Because the mass flow of the coolant is limited, finding favorable channel geometries is crucial to increasing cooling efficiency. In this work, experimental and computational results concerning an already fabricated microchannel cooler are presented, and the influence of channel patterns (straight, zigzag, funnel) and material substitutions on its cooling efficiency are investigated.
II. E XPERIMENTAL AND NUMERICAL RESULTS At the Department of Electron Devices, there has been extensive experimental and theoretical research done on air based microchannel coolers [6], [7], [8]. The one inspected here (see Figure II.1) was manufactured using TMAH etching known from MEMS technology [7]. Although other solutions with different fluids (like water, which has a larger heat capacity [9], or a multiphase flow near boiling temperature [10]) have a better cooling efficiency, air is advantageous for practical reasons: in the case of possible spillage, liquid coolants can damage the equipment cooled.
I. I NTRODUCTION Integrated circuits manufactured in the classical, planar manner require serious cooling; a more serious challenge arises in the case of modern, 3D packaged circuits. Here, a controlled, stable temperature is even more important to prevent a decrease in speed and possible malfunctioning. Photovoltaics research is another field where moderation of temperature is needed, since an increase in temperature decreases the efficiency of energy conversion [1]. Conventional cooling methods are approaching their limits [2]. A possible solution is to use heat sinks with small channels with cross-section dimensions in the micrometers, as heat transfer scales inversely with channel width [3]. Since 95% of the silicon in the chip is unused, channels can be manufactured inside the chip itself. Because it is difficult to flow large amounts of coolant through such small channels (limited by the cross-section and pressure drop), an increase in cooling efficiency can mostly come from an optimization of channel patterns, material and hydrodynamic parameters. Using finite volume software, it is possible to investigate the effect of the aforementioned parameters on the heat sink [4], possibly develop an optimization method to improve its cooling efficiency. The finite volume method divides the inspected region into a number of control volumes, so that there is one grid point located in the center of each control volume. The governing equation is integrated over each control volume to derive an algebraic equation containing the grid point values of the dependent variable. The discretization equation then expresses the conservation principle (such conservation of mass or momentum) for a finite control volume just as the partial differential equation expresses it for an infinitesimal
Figure II.1. Microchannel cooler manufactured using TMAH etching .
A. Thermal transient testing The experimental method employed for examining thermal properties of the cooler is called thermal transient testing [11]. The point of this method is to measure the temperature response (thermal transient) of the system to a jump in power heating it. From this measurement, we can extract thermal properties of the heat sink, most important of which is the thermal resistance (a measure of cooling efficiency, the larger the efficiency, the smaller the thermal resistance), defined as:
20
Rth =
∆T , P
temperature difference between the heat source average and the outside temperature. Numerical and experimental results, along with results from a simplified analytical model [5] can be seen in Table II.1. Since the average Reynolds number of the channels is in the laminar region (for the largest examined mass flow, Re ≈ 830), we assume that the effects of turbulence are negligible. One can see that the experimental and numerical results are in good agreement, while the analytical results somewhat overestimate the thermal resistance of the device. Plots of the temperature and pressure distribution inside the cooler are included in Figure II.4.
(II.1)
where ∆T is the steady state temperature difference between the dissipating element and the environment and P is the power dissipated. With an experimental setup detailed in Figure II.2, temperature of the device was measured as a function of time, with a given mass flow rate and constant dissipation provided by a power transistor.
Table II.1 T HERMAL RESISTANCE AS A FUNCTION OF COOLANT MASS FLOW. ROWS CONTAIN THE EXPERIMENTAL , NUMERICAL AND ANALYTICAL RESULTS , RESPECTIVELY. T HE UNIT OF MASS FLOW RATE IS STANDARD LITER PER HOUR . m[sl/h] ˙ Rthexp [K/W] Rthsim [K/W] Rthanal [K/W]
Figure II.2. Thermal transient measurement setup
B. Numerical simulations
60 36.4 39.2 51.2
120 25.1 22.9 26.5
240 13.4 14.3 15.4
480 7.6 7.5 10.8
III. C HANNEL OPTIMIZATION Results seen in Subsection II-B indicate that the temperature of the coolant at the outlet is considerably lower than the bulk temperature of silicon. If we could increase the surface through which heat transfer happens between the chip and the coolant, we could further decrease thermal resistance. Assuming that we have the best possible channel cross-section allowed by technological limitations (in practice this usually means as deep and as narrow as possible), there are still other ways to do this. In this section, we are dealing with single-channel devices based on the heat sink mentioned in Section II, with a rectangular cross-section, thermally isolated except for the inlet and the outlet. We define a constant power dissipation, and calculate thermal resistance the same way as mentioned in Section II. A. Increasing effective length, material substitutions
Figure II.3. Geometrical model of a quarter of the microchannel cooler. In the upper right corner, indicated by the dark arrows pointing inwards, is the inlet, The outlet is the left and bottom side, indicated by the dark arrows pointing outwards. The red arrows specify symmetry boundary conditions. The outline of the heat source can be seen on the back side of the model.
By increasing the effective length of the channels, we increase the heat transfer surface as well. One way to do this is to use zigzag-shaped channels known from microfluidic mixing [12]. The examined designs can be seen in Figure III.1. In addition, because Reynolds numbers here are larger ˙ H (Re = mD ˙ is the mass flow rate, DH µA . 2400, where m is the hydraulic diameter, µ is the dynamic viscosity, A is the cross-section), we examine the effects of turbulence in the case of the straight channel, calculating for both laminar and turbulent flow, while using a turbulent model in the zigzagshaped channels. By switching out the borofloat glass cover to silicon with a much larger heat conduction coefficient, we basically increase the effective cross-section through which heat transfer can happen.
In the numerical software ANSYS, simulations were performed for a model of the microchannel cooler (shown in Figure II.3). Because of the symmetry of its geometry, it is sufficient to perform the simulations for a quarter of the cooler with the appropriate symmetry boundary conditions. On the air inlet, we specify a given mass flow rate and temperature for the air entering the cooler. On the outlet, we specify atmospheric pressure, and on the outside boundaries adjacent to the environment we specify boundary conditions corresponding to convective heat transfer. The heat source is defined by a constant power dissipation, while ∆T is the
21
(a) Temperature distribution (a) Straight channel
(b) Zigzag channel with an y to x ratio of 0.2
(c) Zigzag channel with an y to x ratio of 0.4
(d) Funnel shaped channel to illustrate cooling
Figure III.1. Channel geometries. The zigzag channels’ characteristic parameter is the tangent of their angle measured from the x axis, y/x. Table III.1 R ESULTS OF SINGLE CHANNEL SIMULATIONS : THERMAL RESISTANCE AND PRESSURE DROP AS A FUNCTION OF THE R EYNOLDS NUMBER II. Re Rstr [K/mW] Rstrlamin [K/mW] Rzig0.2 [K/mW] Rzig0.4 [K/mW] Rsilcover [K/mW]
(b) Pressure distribution
300 1.56 1.42 1.52 1.46 1.27
600 0.93 0.86 0.91 0.85 0.71
1200 0.63 0.44 0.59 0.47 0.48
2400 0.51 -0.007 0.42 0.22 0.42
(a) Thermal resistances
Figure II.4. Temperature and pressure distributions in a cross-section of the microchannel cooler for a mass flow rate of m ˙ = 480[sl/h]
Re pstr [kPa] pstrlamin [kPa] pzig0.2 [kPa] pzig0.4 [kPa] psilcover [kPa]
Results of the simulations for channel shapes and material substitutions can be seen in Table III.1. From the results, we can see that the pressure drop increases sharply with mass flow. The power required to keep the flow in motion is: Pf low = pQ,
150 2.56 2.46 2.55 2.50 2.39
150 2.2 3.6 2.4 3.6 2.2
300 4.4 7.1 5.1 9.1 433
600 10.6 15.5 12.6 30.0 10.3
1200 28.9 34.5 35.5 64.0 28.5
2400 89.4 84.2 109.6 216.2 88.5
(b) Pressure drop
Turbulence is not very significant until larger Reynolds numbers, where it starts to have a large effect through viscous eddy dissipation (Practically negligible until Re = 600, 35% of the electrical dissipation at Re = 1200, 120% at 2400, so the relation between ∆T and P in (II.1) can no longer be considered linear). It is also interesting to note that for a sufficiently large Reynolds number, thermal resistance calculated from equation (II.1) can take negative values for the laminar case. This also signals a limit of the applicability of the equation: for larger Reynolds numbers, function ∆T = ∆T (P ) has a slight offset; a cooling mechanism (independent of P ) is present next to the heating mechanism (∼ P, ∼ viscous term). To gain a better understanding of the cooling mechanism, we need to take a look at the some of the equations governing high speed flows.
(III.1)
where p is the pressure drop and Q is the volumetric flow rate. Usually, it can be assumed that this power is not increasing the coolant’s temperature, and the measurement setup used contains a thermometer which confirms this. However, the limitations of p and Q by the characteristic of the compressor have to be taken into consideration when making the tradeoff between pressure and thermal resistance. Substituting the borofloat glass cover for silicon decreases thermal resistance without a large effect on the pressure drop. It must also be noted that the more complicated channel patterns and material substitutions are more challenging to manufacture than earlier designs.
22
B. Large velocity compressible flow, Euler equations
IV. C ONCLUSIONS
In the case of high flow velocities, the kinetic energy of a fluid particle is comparable to its internal energy. Let us consider a situation of a compressible, inviscous, isentropic flow where we neglect all heat conduction. In this case, the set of mass, momentum and energy conservation laws are known as Euler’s equations. Rewriting these equations for a steady ∂ = 0, uy = uz = 0, state, single dimensional system ( ∂t ∂ ∂ u = ux , ∂y = ∂z = 0 ), they take the following form [13]: d (ρu) = 0, dx
In Section II, numerical and experimental results concerning a microchannel cooler are presented. Results from the numerical model are consistent with experimental results. Afterwards, in Section III, different methods to decrease the thermal resistance of microchannel coolers are examined. These are tested on single channel designs. It is demonstrated that using a silicon cover and zigzag patterned channels result in an improvement of cooling, with large y/x ratios being the most favorable, although requiring larger pressures. The effect of turbulence is also investigated, and it is concluded that it is significant at larger mass flow rates. A theoretical explanation is given and illustrated numerically as to why thermal resistance is still decreasing for larger Reynolds numbers, when increasing viscous dissipation should intuitively prevent this. It is also demonstrated that a decrease in cross-section area causes more significant cooling; suggesting a use in future designs.
(III.2)
d ρu2 + p = 0, dx h i p d u2 ρu e + + = 0 dx 2 ρ
(III.3) (III.4)
Here, p is the pressure, ρ is the density, u is the velocity, e is the specific internal energy. Assuming the fluid is an ideal gas, we can also write:
R EFERENCES [1] E. Skoplaki and J. Palyvos, “On the temperature dependence of photovoltaic module electrical performance: A review of efficiency/power correlations,” Solar energy, vol. 83, no. 5, pp. 614–624, 2009. [2] S. et al., “Air-cooling extension - performance limits for processor cooling applications,” Proceedings of the XXth SEMI-THERM Symposium, pp. 74–80, 2003. [3] D. B. Tuckerman and R. F. W. Pease, “High performance heat sink for vlsi,” IEEE Electron Dev. Lett., vol. EDL-2, no. 5, pp. 126–129, 1981. [4] K. Toh, X. Chen, and J. Chai, “Numerical computation of fluid flow and heat transfer in microchannels,” International Journal of Heat and Mass Transfer, vol. 45, no. 26, pp. 5133–5141, 2002. [5] G. Takács, P. Szabó, and G. Bognár, “Modelling of the flow rate dependent partial thermal resistance of integrated microscale cooling structures,” in Design, Test, Integration and Packaging of MEMS/MOEMS (DTIP), 2015 Symposium on. IEEE, 2015, pp. 1–4. [6] W. Yu, M. Desmulliez, A. Drufke, M. Leonard, R. Dhariwal, D. Flynn, G. Bogn’ar, A. Poppe, G. Horvath, Z. Kohari et al., “High-aspect-ratio metal microchannel plates for microelectronic cooling applications,” Journal of Micromechanics and Microengineering, vol. 20, no. 2, p. 025004, 2010. [7] G. Takács, P. Szabó, B. Plesz, and G. Bognár, “Improved thermal characterization method of integra ted microscale heat sinks,” Microelectronics Journal, vol. 45, pp. 1740–1745, 2014. [8] G. Takács, P. Szabó, and G. Bognár, “Enhanced thermal characterization method of microscale heatsink structures,” in Thermal Investigations of ICs and Systems (THERMINIC), 2015 21st International Workshop on. IEEE, 2015, pp. 1–4. [9] G.-L. Wang, D.-W. Yang, Y. Wang, D. Niu, X.-L. Zhao, and G.-F. Ding, “Heat transfer and friction characteristics of the microfluidic heat sink with variously-shaped ribs for chip cooling,” Sensors, vol. 15, no. 4, pp. 9547–9562, 2015. [10] D. Maddox and I. Mudawar, “Single-and two-phase convective heat transfer from smooth and enhanced microelectronic heat sources in a rectangular channel,” Journal of Heat Transfer, vol. 111, no. 4, pp. 1045–1052, 1989. [11] V. Székely and T. Van Bien, “Fine structure of heat flow path in semiconductor devices: a measurement and identification method,” Solid-State Electronics, vol. 31, no. 9, pp. 1363–1368, 1988. [12] V. Mengeaud, J. Josserand, and H. H. Girault, “Mixing processes in a zigzag microchannel: finite element simulations and optical study,” Analytical chemistry, vol. 74, no. 16, pp. 4279–4286, 2002. [13] M. Giles, “Analysis of the accuracy of shock-capturing in the steady quasi-1d euler equations,” 1995.
(III.5)
p = ρRT, where R is the individual gas constant. Finally,
(III.6)
e = cv T,
where cv is the specific heat capacity for constant volume. For a know pressure drop, the remaining thermodynamical parameters can be calculated. For temperature, the relation is:
p1 p2
=
cv +R T1 ( R ) . T2
(III.7)
This means that as the pressure decreases, so does the temperature. In a more realistic situation, viscous dissipation and heat conduction counter this effect, but numerical results confirm that a high enough pressure drop (so a high mass flow) causes observable ’self-cooling’, accounting for the ’negative’ thermal resistance in Subsection III-A. An isentropic simulation suggests that a reduction of crosssection area along the direction of the flow also causes cooling (see Table III.2). Here, we can see that for a similar pressure drop, air cools significantly more for a funnel shaped channel. Numerical results in Section II are consistent with this; at the area near the inlet, there is a sudden pressure drop and cooling. (see Figure II.4) caused by a change in cross-section. With further work, this may be possible to confirm experimentally, or to use this fact to create channel patterns in which the temperature is the lowest where cooling is needed the most. Table III.2 C OMPARISON OF THE SELF - COOLING OF STRAIGHT VS . FUNNEL SHAPED ( FIGURE III.1 D ) CHANNELS . T HE TEMPERATURE OF AIR AT THE INLET IS T = 293K. Re 1200
∆Tf un [K] -10.4
pf un [kPa] 25.7
∆Tstr [K] -4.4
pstr [kPa] 27.9
23
A crowdsensing platform for mass surveillance at outdoor events Attila Mátyás Nagy
Vilmos Simon
Department of Networked Systems and Services Budapest University of Technology and Economics Budapest, Hungary
[email protected]
Department of Networked Systems and Services Budapest University of Technology and Economics Budapest, Hungary
[email protected] A Bluetooth-based solution [3] is utilized as well, here the goal was to create a mobile application which can assist in the management and in the communication tasks of the organizers for large-scale outdoor events. To determine the size and the distribution of the crowd it uses the Traffax sensors[4], which are placed near the entrances of the event so they can count the the active Bluetooth devices passing by. This approach has limited capabilities, as it can only give us the density of the participants near the gate sensors, but has no knowledge about the internal state of the crowd. Of course, it is possible to place more gates at the area of the event, but it can be extremely costly in those cases.
Abstract— Nowadays festivals and city events attract huge number of visitors and unfortunately in large masses a minor panic could have incalculable consequences despite of the organizers’ efforts to do everything for participants’ safety. Therefore we have developed an integrated mass surveillance system based on crowdsensing data, where the system helps authorities and organizers in information gathering about the actual dynamics of the crowd. Based on real time and representative information, they are able to perform fast and targeted interventions. Keywords— mass surveillance; mobile crowd sensing; smart cities
Another system [5] uses GPS positioning and WiFi/ GSMfingerprinting [6] methods to determine the position of pedestrians. A festival application has been developed which gathers position information from participants at every second. These location data samples are transmitted to the mobile server where they are evaluated. After the evaluation, a heat map is generated to display the actual state of the crowd. The system assumes that the visitors using the application are statistically distributed in proportion to the crowd so correct conclusions can be made about the global behavior of the crowd. Naturally, if there are more active users in the system the heat map becomes more accurate, but the integration of a camera-based system can also improve the accuracy. The system has been tested at the Lord’s Mayor Show 2011 in London and at the Vienna City Marathon 2012. A major flaw in the system is that the mobile application queries the GPS position every second. This approach depletes the device’s battery really quickly therefore the participants will not use it in a long term.
I. INTRODUCTION AND RELATED WORKS The vast majority of visitors of today’s large events already have a mobile device (such as smart phones and tablets) which has various built-in sensors (GPS, accelerometer, gyroscope). Data from these sensors are collectable and by processing them valuable information can be obtained, thus it is possible to monitor crowd dynamics, and based on the history of the given venue to estimate future states. This is a typical case of crowd sourcing. Crowd sourcing is a way of cooperation where large group of users are solving different simple tasks (which are part of a bigger task), so complex problems can be handled more efficiently. Crowd sensing [1][2] is a subtype of crowd sourcing where the outsourced job is a sensing task. This can be very useful for several reasons. As organizers of large music festivals have explained to us, for such large events, although there are models and inaccurate estimates of distribution of the crowd, we can not exactly know how many people are staying in one area or moving to another one at a given moment. If we could measure it via a mobile crowd sensing platform, depending on the distribution of the crowd we could reallocate the security and medical personnel more precisely, furthermore we could also dynamically modify the evacuation plans if needed. The mobile crowdsensing platform should also allow us to send different messages to participants based on their position. These messages may include public notices, and even promotional messages.
The previously introduced systems can help the work of the organizers and authorities in different ways, but there is a clear need from the organizers for an integrated solution which combines the benefits of the previous systems and provides more accurate information for the organizers while it generates less network traffic and consumes much less energy at the devices. II. DEVELOPMENT OF A MASS SURVEILLANCE SYSTEM
There are different systems that perform various surveillance tasks, however they are not necessarily addressing the tasks the organizers are so keen to solve nowadays.
A. Mass surveillance model As a first step, we have studied thoroughly the literature of crowd dynamics models, to address the problems mentioned
24
above. The known models are always based on a physical model, since the movement of human masses shows a strong resemblance to dynamics of liquids and granular materials[7][8]. We have also studied discrete (cell based) mass surveillance models [9][10][11][12][13] and we found that although all of these approaches are working properly in simulation scenarios, we had to take into account other considerations which are really important in real life applications. Thus we have modified the cellular model to provide an adequate abstraction which allows us to reduce significantly the number of irrelevant data and the network traffic. First, we divided the space to discrete areas, so-called cells. We have to highlight that the cells are not squares like in other models[9][10], but they are arbitrary convex quadrangles. It is better to define areas which need to be examined as one coherent unit in one cell instead of dividing them to two or more cells. Convex quadrangles support this approach very well. For example, it is not appropriate when a cell is defined in a way that part of its area is covering a busy road, while the other part covers a building which will obviously block the movement of pedestrians inside the cell, actually breaking it down to two separate cells. We have to know each cell size for density calculation but they are calculated easily based on GPS coordinates. Secondly, we had to place the participants in our model. We assume that a participant’s mobile device has a built-in GPS sensor, a gyroscope and accelerometer. The data from these sensors is used to determine the participant’s position and velocity which are required to make correct evaluations about the crowd dynamics. By collecting samples from the gyroscope and accelerometer, the GPS needs to be activated only from time to time to obtain a more precise position, in the meanwhile the position of the user can be predicted in an energy efficient way, by utilizing the dead reckoning [19][20] method. This can be precise enough in the majority of the cases, as only the cell should be identified where the user resides, not the accurate geographical position (due to the cell based model). This means that the GPS sensor does not need to be active all the time of the surveillance (like in the above described system, where the samples were extracted every second), therefore the batteries of the participants’ smartphones
will not be depleted in short time. Therefore, it is unnecessary to send the exact GPS coordinates, it is enough to send only the previous and the next cells’ identifier. It speeds up the calculation because of two reasons. First is that we can aggregate measurement messages to cells so we do not have to use GPS coordinates during the evaluation phase. Second is that the devices send their measurement messages only when changing a cell, as in a real life scenario a participant is often standing still (watching a concert or speaking with other persons), not changing a cell for dozen of minutes (or even hours), therefore the communication and computation overhead can be decreased significantly. In our system the current status of a participant (or device, because they are the same in this case) can be described by two variables: the position (cell id) and the velocity of the person. Based on this two metrics we calculate the following crowd characteristics for each cell: crowd density, crowd velocity variance, crowd pressure[14]. Crowd density is a very useful metric, as it can be a warning sign of critical crowd conditions [14]. With velocity variance we can predict unexpected incidents (for example a stampede), while crowd pressure is the decisive variable quantifying the hazard to the crowd (it can be calculated by multiplying the crowd density with the variance of velocity). B. System architecture In our integrated mass surveillance system a number of separate components work together (Figure 1). The different tasks have been distributed among these units so a component failure does not cause the failure of the whole system. Our system has to be able to receive incoming data (measurement messages) from more than ten or hundred thousands of different sources (from participants’ devices). Thus our first job was to create a component (TrafficAggregatorService) which is able to handle this enormous amount of sources and aggregate their data to streams. Other important tasks to be solved were the evaluation of measurement messages and the position based notification mechanism for participants, so we have developed appropriate system components for them also. The unit responsible for the evaluation of measurement messages became the SparkEvaluationService, which is a cluster computing unit,
Figure 1: System architecture
based on Apache SparkStreaming [16]. It simply connects to the TrafficAggregatorService, downloads the continuous stream of data, runs our evaluation algorithms on them, and finally saves the results to the database.
all participants in a given cell (as there is a possibility to narrow the notifications to only one cell) they can do it instantaneously. Naturally, PNS is able to store different notification messages for different cells with an expiration date. Every time when a device changes its cell, PNS will send all notification messages which have been set to the given cell, because the PNS detects the cell handover by analyzing the position message stream from the TAS.
The PushNotificationService component is an own implementation of a general push notification service. We developed it because we did not want to depend on another third party service, this way we could customize and optimize it for our purposes. As the SparkEvaluationService, this component also connects to the TrafficAggregatorService, but it downloads only the position information and based on these it sends notification messages for the participants, when needed.
As the PNS needs to maintain lot of persistent connections for the mobile applications, we had to designed it to be able to handle huge number of persistent communication channels. The component has two types of subcomponents. First is the PushNotificationServer (PS), which is responsible to maintain the communication channels (here we also use Netty) and to store the notification messages. In some cases, one PS can not manage the overall load, thus our service can run on more instances, however then the operation of different instances should be synchronized. For this purpose, we developed a central control element, the PushNotificationController (PNC). On the one hand, PNC maintains the connection with the TAS and distributes the received position messages between the PS instances. On the other hand, PNC also handles and distributes new notification messages received from the safety authorities.
1) TrafficAggregatorService As we can seen on Figure 1, the TrafficAggregatorService (TAS) provides an interface for mobile applications to forward their measurement messages which contain the position (cell id) and velocity information. From this interface all received data is forwarded into TCP streams for the PushNotificationService and for the SparkEvaluationService. Naturally, TAS can provide more streams for the evaluation service if multiple cluster nodes are in operation at the SparkEvaluationService, furthermore it can also provide more streams for the PushNotificationService if necessary.
3) SparkEvaluationService The SparkEvaluationService (SES) is responsible for the efficient evaluation of measurement messages. Inside the component, we use the Apache Spark which is a fast and general-purpose cluster computing system. It supports a rich set of higher-level tools including Spark Streaming [16] which is the key feature in our case. Spark Streaming in an extension of the core Spark API that enables us to process live data stream from the TrafficAggregatorService. Therefore, we have implemented the communication interfaces to the TAS, our evaluation algorithm and our multithreaded thread-safe database access interface to save the evaluation results.
To be able to cope with the heavy loads of measurement messages, the TAS uses Netty [15], an asynchronous eventdriven framework at the mobile application interface (We provide TCP and UDP interface too). With Netty, TAS can handle tens of thousands simultaneous connections. For more efficient resource utilization there is no continuous connection between the applications and the TAS, the devices send the measurement message (a message is compressed in 29 bytes) only when they change the cell (as the mobile application downloads at the beginning the cell structure of the event). Sometimes one running TAS instance is not enough to serve huge number of incoming measurement messages. In this case, it is possible to chain more TAS instances together in a master-slave architecture, so the load capacity will increase. The slave instances behave like a normal instance except they forward all received measurement messages to the master instance.
Due to the operation of Spark Streaming our evaluation algorithm runs periodically on the actually received measurements – where the period time depends on the number of participants – so essentially every evaluation result is the change of the crowd’s state from the previous crowd’s state. Because of this we keep the actual state in the memory for efficient state computing and we always add the changes to it which is really fast in case of heavy loads too. At the end of an evaluation period we save the actual state to the database via our access interface. The SES calculates the headcount, the average velocity variance, the crowd density and the crowd pressure for each cell.
2) PushNotificationService The PushNotificationService (PNS) component’s job is to provide a one-way communication channel to notify participants based on their position, thus safety authorities are able to send information to participants in real time. To achieve the instant messaging functionality, we have to maintain a persistent TCP connection, so if the organizers want to notify
III. SIMULATION RESULTS The purpose of the scalability simulations was to validate
26 Figure 2: Number of forwarded messages in TrafficAggregatorService
Figure 3: Number of messages in PushNotificationServer message Fifo
our system, if it is working correctly and to check what is the maximum load that our solution is able to handle. To perform the tests, it was necessary to develop a device simulator application which is able to simulate thousands of devices which are able to communicate properly with the system and use algorithms which simulate the movement of the crowd properly. We wanted to apply proven solutions for the crowd movement simulation, therefore the Random Waypoint[17] and the Gauss-Markov[18] mobility model was adapted to our environment.
Two crucial components of the implemented system were subjected to detailed simulations tests. The tests showed that both components are prepared to process and forward even 10 000 messages per second, which means that an event of several hundred thousands of participants could be served by this system. As a next step, we plan to optimize the inner processes to reach an even better and more reliable performance, also adding new functionalities to the user interface. REFERENCES [1] Á. Petkovics, V. Simon, I. Gódor and B. Böröcz, “Crowdsensing Solutions in Smart Cities towards a Networked Society”, Endorsed Transactions of Internet of Things, vol. 15, 2015 [2] Ganti, R. K., Ye, F., and Lei, H., “Mobile crowdsensing: current state and future challenges”, Communications Magazine, IEEE, vol. 49, pp. 32-39, 2011 [3] Donna Nelson, Traffax Inc., Riverdale MD: Proximity Information Resources for Special Event, 2012
[4] Traffax Inc.: BluFAX Concept, online: http://www.traffaxinc.com/ content/blufax-concept, November 2013 [5] Eve Mitleton-Kelly, “Co-evolution of Intelligent Socio-technical Systems”, pp.61-77, 2013 [6] Kim, D.H., Kim, Y., Estrin, D., Srivastava, M.B., “Sensloc: Sensing everyday places and paths
using less energy” Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems, Zurich, pp. 43-56, 2010 [7] Dirk Helbing, “A Fluid Dynamic Model for the Movement of Pedestrians”, Complex Systems 6, pp. 391-415, 1992 [8] Henderson, L. F., “The Statistics of Crowd Fluids”, Nature vol. 229, pp. 381-383, 1971 [9] Victor J. Blue, Jeffrey L. Adler, “Cellular automata microsimulation for modeling bi-directional pedestrian walkways”, Transportation Research Part B: Methodological, vol. 35, issue 3, pp. 293-312, 2001 [10] Minoru Fukui and Yoshihiro Ishibashi, “Jamming Transition In Cellular Automaton Models for Pedestrians on Passageway”, Journal of the Physical Society of Japan, vol. 68, no. 11, pp. 3738-3739, 1999 [11] Ansgar Kirchner, Andreas Schadschneider, “Simulation of evacuation processes using a bionics-inspired cellular automaton model for pedestrian dynamics”, Physica A: Statistical Mechanics and its Applications, vol. 312, issues 1-2, pp. 260-276, 2002 [12] Andreas Schadschneider, “Cellular Automaton Approach to Pedestrian Dynamics – Theory”, Pedestrian and Evacuation Dynamics, Springer, pp. 75-85, 2001 [13] P.G. Gipps and B. Marksjö, “A micro-simulation model for pedestrian flows”, Mathematics and Computers in Simulation, vol. 27, issues 2-3, pp. 95-105, 1985 [14] Helbing, D., Johansson, A., Al-Abideen, H.Z.: Dynamics of crowd disasters: an empirical study. Phys. Rev. E 75(4), 046109, 2007 [15] Netty project, online: http://netty.io/, accessed: 3/20/2016 [16] Spark Streaming, online: http://spark.apache.org/streaming/, accessed: 3/20/2016 [17] David B. Johnson, David A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks”, The Kluwer International Series in Engineering and Computer Science, vol. 353, pp. 153-181, 1996 [18] Liang and Z. Haas, “Predictive Distance-based MobilityManagement for PCS Networks”, IEEE INFOCOM 1999, vol. 3, pp. 1377-1384, 1999 [19] A. Lin, J. Zhang, K. Lu and W. Zhang, “An efficient outdoor localization method for smartphones”, Computer Communication and Networks, 2014 23rd International Conference, pp. 1-8, 2014 [20] X. Zhu, Q. Li, G. Chen, “APT: Accurate outdoor pedestrian tracking with smartphones”, INFOCOM, 2013 Proceedings IEEE, pp. 25082516, 2013
We started the performance tests with the TrafficAggregatorService. In the case of this component we wanted know how many messages can be transmitted to other components per second, what is the processing time of a message in this component, the operation of the measurement message Fifo inside the component at a given moment and the memory usage of the component. We found that the TAS is able to forward even 10 000 messages per second (Fig. 2.). If we assume that a participant changes cell every 5 minutes in average, which can be a valid assumption in a real world operation, it means that the TAS can deal with around 3 million active participants. Meanwhile, we also measured the memory usage of the component and it was not been more than 2,4% in any moment of the testing. We also investigated the saturation of measurement message Fifo. The load of the Fifo was usually around zero, except for some cases. The reason for those could be various (GC call, context change, etc.), but the Fifo can store around 4.5 million messages and the measured peak was 110 message thus it is negligible. We have also investigated the performance of the PushNotificationService. We used the same load (10 000 messages per second) for the tests as in the case of the TrafficAggregatorService, using 200 cells and 150 notification messages which can correspond to a real-life setting. We have found similar results as in the case of the TrafficAggregatorService tests. Both components have low memory consumption and in most of the cases the load of Fifos were around zero (Fig. 3.). There were also some peaks in the load of the Fifo of the PNS, the highest was 600 messages, it is also negligible compared to the 4.5 million messages. IV. CONCLUSION Nowadays, the huge mass events have high attendance, therefore the occurrence of dangerous incidents is on the rise. We have developed a mass surveillance system which provides useful information for the organizers in real time via a simple and logical web interface. The cellular model was modified by us to provide an adequate abstraction which allows us to reduce significantly the number of irrelevant data and the network traffic. In our integrated mass surveillance the different tasks have been distributed among three components so a component failure does not cause the failure of the whole system. Our system was created to be able to receive incoming measurement messages from more than ten or hundred thousands of different sources.
27
Where are my tokens: a Linux kernel based hidden host monitoring framework for honeytokens Tam´as Holczer
Gy¨orgy Miru
Laboratory for Cryptography and System Security Budapest University of Technology and Economics Budapest, Hungary Email:
[email protected]
Laboratory for Cryptography and System Security Budapest University of Technology and Economics Budapest, Hungary Email:
[email protected]
Abstract—Intrusion detection techniques vary from host based to network based detection and from signature based to honeypot based approaches. A special case of honeypots is the honeytoken based intrusion detection. In a honeytoken based system, the attacker interacts with a bait in a detectable way. The detection is carried out by a monitoring subsystem. However, if the attacker first attacks the monitoring subsystem successfully, then she learns, where the honeytokens are placed. In this paper we give a Linux kernel based method, how the monitoring subsystem can be hidden from an adversary, without jeopardizing either its efficiency or its accuracy.
I.
I NTRODUCTION
Monitoring a host or a whole network of computers is an ordinary task of thousands of system administrators worldwide. This activity is supported by many different applications such as Nagios [2] or OpenView [11]. A special part of system monitoring is the detection of possible intrusions to the system. Many theoretic results and intrusion detection system implementations are available for various needs. Some approaches use a host based method, where the detection system looks for suspicious activities on the host, while in a network based method, the system checks the network traffic for adversarial traffic. Some other taxonomies [1] categorize the intrusion detection systems based on the detection technique. They can be signature based, anomaly based, policy based and honeypot based. The signature based method is the most widely used, where given patterns of adversarial traffic is defined as attack signatures. Unfortunately a signature based method can only detect priory known attacks, but the operation is quite simple and easy to manage. A totally different approach is used in a honeypot based system. Honeypots are closely monitored network decoys serving several purposes: they can distract adversaries from more valuable machines on a network, they can provide early warning about new attack and exploitation trends and they allow in-depth examination of adversaries during and after exploitation of a honeypot. Honeytokens are similar to honeypots, but they are less complex and easier to deploy (Lance Spitzner defines honeytoken as a honeypot that is anything but a computer [12]). A honeytoken can be a user credential or a file or any other information, which is not used in normal operation, so the access of this piece of information can be considered as an adversarial activity. Honeytokens are also called baits or decoys. The generation and management of different honeytokens
28
are discussed in [4], [5], while the requirements a useful honeytoken must meet is defined in [17]. An important part of any honeytoken system is the detection of the usage of the honeytoken. This problem mainly involves searches of logs for given activities. But what happens if the monitoring machine itself is attacked? Then the attacker can find out what is monitored, what are the honeytokens, where are they placed etc. So by compromising the monitoring subsystem, the whole honeytoken based intrusion detection system becomes useless. In the following we will give a solution for this problem. More precisely, the contributions of this paper are the following: •
We give a method to hide the monitoring subsystem
•
We evaluate the performance and stealthiness of our solution
•
We provide a proof of concept implementation
In the following we will assume, that the attacker has access to the detector machine (possibly root access), and she wants to find out, if it is an active detector machine. There are multiple ongoing studies and existing solutions [14] to limit the capabilities of the root user in case the system gets compromised. This theoretically allows a user space process to be unkillable even by the root user. However, this is not sufficient for our needs, we want to completely obscure the presence and activities of our detector. The remainder of this paper is organized as follows: In Section II we introduce our hidden detector. The tests of our implementation are described in Section III, while in Section IV we conclude our paper. II.
T HE H IDDEN D ETECTOR
The hidden detector is a Linux based machine, which runs normal and hidden activities as well. From the perspective of an attacker, it only offers normal services. Thus even if the attacker gains access to it (including root access), she will not suspect, that the machine is part of a honeytoken system. The detector is successful if it can identify the attacker and alert the monitoring infrastructure while remaining undetected. The alerting subsystem may reside on a different host and the attacker may actively scan for suspicious activities. Figure 1 demonstrates the place of the hidden detector in a honeytoken system.
mechanism, called workqueues. In general, workqueues provide a generic method to defer functionality to bottom halves. In the detector not exactly work deferring occurs, but this mechanism is suitable to implement the detector. A task of a workqueue runs in process context (allowed to be slow compared to interrupt handling), and handled by keventd. A new workqueue can be defined for special purposes, but there is a general global workqueue always present in the kernel responsible for some house keeping. Additional work can be added to this global workqueue, which is executed by the always present [kworker/X:Y] processes. This additional work can be the detection of triggered tokens.
Fig. 1.
Finding the suitable context is just the first step, the detector needs to communicate with other subsystems and is required to read user space files. Opening a socket or storing its initial configuration in a file can be detected by an attacker so a covert communication channel must be used.
Honeytoken System Scheme
Hiding a service in Linux is not trivial, but it is possible. Obviously a normal user space process cannot be launched to carry out the detection activities, because the process list is accessible to normal users of the machine (ps aux or ps -ef). One possible solution would be to create a new process, and unlink it from the list of processes. This can be done by manipulating the kernel data structure of processes [16] by modifying the kernel or inserting a special kernel module. This way a user space packet filter is required to process the packets to communicate with the alert and management subsystems. Such a suitable packet filter is the Berkeley Packet Filter [7], which is used for example in the netsniff-ng toolkit. The other promising solution is to extend the functionality of an existing process. The only general solution is to add the required detecting functionality to the kernel, because the kernel is present on every machine, unlike other processes. Also, the kernel always occupies some CPU time in every situation and the size of it makes binary analysis hard and time consuming. The common approach to implement new kernel features is to use kernel modules. Unfortunately, this approach is not sufficient in our scenario, because the list of loaded kernel modules is available from user space. This can be circumvented by unlinking the module from the list of loaded modules, which is essentially the same solution as unlinking the active process from the list of processes. The other less general approach is to implement the new feature inside the kernel itself. In kernel space, every activity can be done either in interrupt context or in process context. From the first glance, interrupt context fits better for detecting, because it runs immediately without any interruption totally out of control of any user. The main problem is that the interrupt context has a set of strict restrictions, such as it needs to be fast and cannot sleep. The detector is required to read log files to function properly, however I/O operations are slow and might require sleep. On the other hand, process context in kernel mode can sleep, or can be arbitrary slow, so it is suitable for detection purposes. Process context code can be run in a new kernel process (kthread_create and kthread_run), but these are visible for all the users. Linux kernels from version 2.5 offer a new deferrable
29
ICMP echo request and echo reply messages (defined in RFC 792 [15]) can be used to deliver data silently between machines. The echo request contains a data field which is returned in the echo reply. The content of the data field is not defined in the RFC. Different operating systems insert different data to the data field. This data field can be used to carry configuration parameters between the detector and the monitoring network. This allows a custom management protocol to be defined and embedded into the ICMP messages. The main advantage of this method is that in Linux systems ICMP messages are processed by the kernel. A small modification in the kernel allows the data contained in these messages, to be passed to the global workqueue. To further obscure the communication and prevent the reverse engineering of the management protocol strong encryption can be used. The Crypto API [6] provided by the kernel offers different cyphers to encrypt or decrypt data, including AES, DES, 3DES and Blowfish block cyphers. These cyphers are suitable to encrypt messages in real-time, because the same Crypto API is utilised by the kernel’s IPsec implementation. When an attacker’s presence is discovered, it is the hidden detector’s responsibility to alert the monitoring facility, that is often resides on a remote host. The same method can be used to carry out this task. There are multiple possible approaches to craft and send echo request from kernel space. To ensure reliability, two different methods are implemented in the detector. The first creates an echo request containing the alert data, and pushes it into the IP stack’s outgoing packet queue. If this approach fails to deliver the message, a fallback method is used, that creates a kernel raw socket to send the packet to the monitor. To demonstrate the feasibility of the above mentioned solutions a proof of concept hidden detector was created and tested. The rest of this section further details the implementation of the detector inside the Linux kernel. A. Detector Implementation with the Global Workqueue The purpose of the workqueue is to execute the registered routines queried by the top half, at a safer time and in process context. This mechanism allows the interrupt handlers to schedule their time consuming, slower parts to run out of interrupt context. The detector is a routine that is queued at the
global workqueue during the kernel initialisation. At the end of its execution the detector reschedules itself, thus a periodic execution of its code is provided by the workqueue. Each time the main routine of the detector is called, it parses the received echo requests from a queue. In case the detector finds a valid management message, it interprets the command contained in the message and carries out the requested operation. The configuration is kept in the operative memory and it contains the IP address of the monitoring infrastructure, the encryption key used in the communication and a linked list of the URIs of the logfiles that need to be scanned. This initial configuration is compiled into the kernel and can only be modified with the management messages. At this point of the development, changes made to the configuration are not persistent between reboots. After all the messages are administered the detector reschedules itself at the global workqueue and terminates. Within a predefined interval, the hidden detector scans the logs for expressions that suggest a breach in the system. During these scans the detector periodically releases CPU resources in order to not starve lower priority user space processes during heavy loads. If a matching expression is found the detector alerts the monitoring facility. The scanning requires the detector to read files that are stored on the hard drive. Reading a user space file from kernel space is a non trivial task because kernel threads reside in a different virtual address space [13] than user threads. Fortunately, a workaround exists that temporarily redefines the boundaries of the kernel virtual address space, thus allowing the kernel to open files from user space. It is important to note that the default implementation of vfs_read() does not use any file locking. In Linux systems it is the users responsibility to serialise multithreaded access to a file descriptor. The kernel only aims to avoid hardware or datablock damage, logical corruption caused by simultaneous file writing is left to the user to prevent. In the detector’s implementation locking is omitted on purpose, because a potential attacker is able to detect file locks. It is not a real problem, as the detector only reads files and never writes them. B. Implementation of Communication In Linux networking every packet sent or received is handled using a data structure called socket buffer (usually referred as sk buff or skb). When a packet is received by the network card, it is packed into an skb and then transferred to the network stack [10]. When an ICMP echo request packet arrives, at some point the icmp_echo(struct sk_buff *skb) method is called, and the skb representing the ping packet is passed to this function. With a slight modification of this routine it is possible to copy the data field of the received echo request packets to the detector’s virtual memory. The next time the detector is called, it can process the copied data. The path of a received ICMP packet in the network stack (the chain of calls) is shown in Figure 2. When a detection is triggered an icmp echo request is crafted and sent. There are two essentially different approaches to do this, one is the use of raw sockets to send the data, the other is to set up an skb and pass it to a chosen layer of the networking stack. While using sockets is simpler and more
30
Fig. 2.
Packet Path in the Detector
reliable it might be monitored by the attacker, although at this point her presence is already detected. Still, the second method is preferred because it is virtually undetectable. To increase the reliability, both of these solutions are implemented, sockets being used as a backup in case the primary method fails to deliver the message. In Linux networking when a packet is sent, the skb representing it goes through the network stack [10]. Unfortunately, the ICMP layer expect a socket buffer with no data field set. Changing this behaviour would require major modification in the Linux kernel. That is why the detector hands the skb over to the IP layer, using the ip_local_out() method. It is the same function that the kernel’s TCP implementation [8] uses. It requires an skb that has its IP header and routing table set up. This is done in the same way as in the TCP implementation. It needs to be mentioned that older kernel versions than 2.6.39 do not have the functions the detector uses to set up routing. In these kernels only the socket based solution can be used to send messages. Kernel sockets expect their data coming from the user space, to pass the check the same trick can be used as explaind in the previous subsection ( II-A). To increase the security of the communication and prevent attackers to inject malicious packets, the payload of the ICMP messages are encrypted with AES 128 CBC cypher [9] using the Linux kernel’s Crypto API [6]. III.
T ESTING AND V ERIFICATION
The two most important criteria for the detector is that it needs to stay hidden and it needs to fulfill its task reliably without making the whole system unstable. To further obscure its presence, the detector is intended to run on a host that is part of the real production environment and not on a dedicated server. The main concern is that the detector runs in the kernel so even the slightest mistakes in its code can result in a complete system crash. An error in the detector not only prevents it to fulfill its duty but may as well disturb or disable other important services that run on the same machine. To ensure that the detector works as intended an extended testing phase was performed with various benchmark tests. To assist the testing, three supplementary scripts were written in Python. The first one is a command generator, that sends simple commands to the detector. The second one is a manager with a CLI that can be used to supervise multiple detectors and build and manage large configurations. The third script is a monitor that listens for alert messages and if one arrives takes appropriate action.
TABLE I.
P ERFORMANCE B ENCHMARKS
Expressions/Match
Files
File Size
CPU usage
Mem usage
5/0
100
5/5
100
50MB
+1%
+20%
50MB
+4-10%
10/0
+20%
5
2GB
+20%
10/10
+70%
5
2GB
+40%
+70%
Without attempting to be comprehensive, the rest of this section describes the most important tests that were executed. For these benchmarks the following configuration was used: the detector was installed with debug mode turned off, on a virtual machine with a 2186 MHz one-core processor and 1 GB of RAM with an 5600 rpm hard drive. Each of the tests were performed multiple times. A. Testing performance and reliability The detector was compiled and tested with multiple kernels from 2.6 to recent versions. Workqueues were added to the Linux kernel in version 2.5, which means that older kernels are not supported. The testing begun with systematic and random (fuzz) testing of the different communication commands and configuration parameters, with an emphasis on list operations. The detection capabilities were tested by running the detector against a large number of ever changing files for an extended time period, which occasionally contained a matching expression. Under normal load the program had a perfect detection rate and even during the heaviest overloads it maintained a 99.95% detection rate. In order to verify that the presence of the detector does not disrupt other services multiple performance test were created. For all these tests the outputs of varius system monitoring programs commands were examined and compared to the reference output. The result of these test is demonstrated in table I. These tests were repeated while running CPU intensive user tasks (such as playing HD media and encrypting large files). The increase in CPU usage became less observable, the time needed to complete the scans increased by 30-40%. However, the user tasks were nor interrupted neither starved, the host system remained interactive and functional.
Since the detector does not use any other I/O resources, the only possible way to find its traces is to find the detector in the memory. By dumping and analysing the memory through /dev/kmem [3] file the detectors traces can be found. Fortunately, the /dev/kmem file can be disabled on Linux system (on most distributions it is disabled by default as it is considered a security vulnerability). The only possible way to find it is to analyse the binary data of the kernel if it is present on the hard drive, which can also be avoided by booting from the network. Also, the binary analysis of non-vanilla kernels is time consuming. IV.
In this paper we proposed a Linux kernel based method for hiding the detection activities of a honeypot based intrusion detection system. We analyzed the difficulties of hiding any services on a host, and gave a solution, which is almost undetectable. We analyzed the stealthiness of our solution, which is satisfactory, and also analyzed the performance of the solution, which is acceptable for most scenarios. In the future we are intended to further analyze our solution in real life scenarios, where both usability and performance issues may arise. April 11, 2016 R EFERENCES [1] [2] [3] [4] [5]
[6] [7] [8] [9]
B. Testing stealth To succeed in its task the detector must remain hidden, so its traces must not appear in any of the Linux’s administrative tools output. The detector is run by the global workqueue, and its code is executed by one of the [kworker/X:Y] processes. The direct consequence of this is that the detector does not appear as a separate process in the ps commands output or in the proc file system. The detector does not use file locks and the files last access, last modification and last change dates are not affected by the scans. By default the detector does not use sockets, so they can not be used to uncover its presence. The detector halts the processing of the echo request packets until it can copy their data. This roughly increases the round trip time of such messages by approximately 0.1 ± 0.03 ms. The measured value is less than the usual ping response time by at least two orders of magnitude.
31
S UMMARY
[10] [11] [12] [13] [14] [15] [16] [17]
S. Axelsson. Intrusion detection systems: A survey and taxonomy. Technical report, Technical report, 2000. W. Barth. Nagios. No Starch Press, 2008. T. Bowden, B. Bauer, J. Nerin, S. Feng, and S. Seibold. The/proc filesystem. Linux Kernel Documentation, 2000. B. M. Bowen, V. P. Kemerlis, P. Prabhu, A. D. Keromytis, and S. J. Stolfo. A system for generating and injecting indistinguishable network decoys. Journal of Computer Security, 20(2):199–221, 2012. B. M. Bowen, P. Prabhu, V. P. Kemerlis, S. Sidiroglou, A. D. Keromytis, and S. J. Stolfo. Botswindler: Tamper resistant injection of believable decoys in vm-based hosts for crimeware detection. In Recent Advances in Intrusion Detection, pages 118–137. Springer, 2010. J.-L. Cooke and D. Bryson. Strong cryptography in the linux kernel. In Proceedings of the Linux Symposium, 2003. J. Corbet. A jit for packet filters. Linux Weekly News, 2011. J. Crowcroft and I. Phillips. TCP/IP and Linux protocol implementation: systems code for the Linux Internet. John Wiley & Sons, Inc., 2001. S. Frankel, R. Glenn, and S. Kelly. The aes-cbc cipher algorithm and its use with ipsec. Technical report, 2003. G. Herrin. Linux ip networking: A guide to the implementation and modification of the linux protocol stack. Technical report, DTIC Document, 2000. J. Huntington-Lee, K. Terplan, and J. Gibson. HP OpenView: a manager’s guide. McGraw-Hill, Inc., 1997. Lance Spitzner. Honeytokens: The Other Honeypot, 2003. R. Love. Linux Kernel Development Second Edition. 2004. B. McCarty. Selinux: Nsa’s open source security enhanced linux. O’Reilly Media, Inc., 2004. J. Postel et al. Rfc 792: Internet control message protocol. InterNet Network Working Group, 1981. ubra. hiding processes ( understanding the linux scheduler ). Phrack Inc., 0x0b(0x3f):#0x12 of 0x14, 2004. J. Voris, J. Jermyn, A. D. Keromytis, and S. J. Stolfo. Bait and snitch: Defending computer systems with decoys. In Proceedings of Cyber Infrastructure Protection (CIP) Conference, 2012.
Mobil egészségügyi multimédia-átvitel QoE vizsgálata Péteri Tamás, Varga Norbert, Bokor László Budapesti Műszaki és Gazdaságtudományi Egyetem Hálózati Rendszerek és Szolgáltatások Tanszék Multimédia Hálózatok és Szolgáltatások Laboratórium (MediaNets) Magyar Tudósok krt. 2, H-1117, Budapest, Magyarország
[email protected],
[email protected],
[email protected] lehetőségeket, a mobilkészülékek és különféle szenzorokkal ellátott hordható kiegészítőik rohamos fejlődését az orvosi gyakorlatban, és támogatást nyújtanak a hétköznapi felhasználóknak, egészségükkel kapcsolatos törekvéseiben [6].
Összefoglalás—Mobil egészségügyi (mHealth) alkalmazások alatt azokat a napjainkban egyre népszerűbbé váló megoldásokat értjük, melyek a mobil/vezeték nélküli telekommunikációs hálózatok és hordozható eszközök adta lehetőségeket használják ki a mindennapi orvosi gyakorlat hatékonyságának növelése, a felhasználók saját, egészséggel kapcsolatos törekvéseinek támogatása, valamint különleges felhasználási lehetőségek elősegítése terén. Az mHealth alkalmazási területeinek egy jelentős csoportja egészségügyi multimédiás tartalmak mobil továbbításával, megjelenítésével és használatával foglalkozik. A mobil és vezeték nélküli kommunikáció jellemzője a szélsőségesen változékony átviteli környezet, mely által közvetlenül vagy közvetve okozott minőségromlás jellemzése történhet objektív és szubjektív módon. A szubjektív élményminőség (QoE) felmérésére és kiértékelésére kidolgozott módszertannál az orvosi alkalmazások esetén figyelembe kell venni azt, hogy az adott tartalom minősége a diagnosztikai célú alkalmazás szempontjából megfelelő-e. Cikkünk különböző mobilitási esetek orvosi multimédia-adatokra kifejtett hatásait mutatja be a QoE fényében.
Számos mHealth megoldás orvosi eszközök által előállított multimédiás jeleket használ, melyek átvitele vezeték nélküli telekommunikációs hálózatokon keresztül történik [7]. Az átvitel során figyelembe kell venni az elérhető sávszélességet és az egyéb hálózati paramétereket. Az álló- és mozgóképi jeleket tömöríteni kell annak érdekében, hogy az átvitel kielégítse a sávszélesség által meghatározott korlátot [8]. A tömörítéssel és az orvosi multimédiás jelek hálózati átvitelével együtt járó minőségromlás ezekben az esetekben legjobban egészségügyi szakemberek bevonásával értékelhető. Ekkor a diagnosztikai relevanciát fókuszba állító, mérhető QoE írja le a minőségromlás mértékét, melynek figyelembevétele elengedhetetlen az eHealth vagy mHealth szolgáltatások tervezésekor. Jelen tanulmány célja nagyfelbontású ultrahang videó és EKG adatok egyszerre történő, valós idejű átvitele során a digitális ultrahang videófolyamban keletkezett minőségromlás mérésére szolgáló orvosi QoE kiértékelő módszer bemutatása. A cikk a továbbiakban a következő felépítést követi: a második fejezet példákat hoz a létező mHealth szolgáltatásokra, az ezt követő harmadik fejezet az általános és orvosi QoE fogalmát és a multimédiás alkalmazások QoE kiértékelésére szolgáló mérési módszereket mutatja be az mHealth alkalmazások területén, a negyedik fejezet összefoglalja és elemzi egy ultrahangos videók minőségének QoE kiértékelés eredményeit, végül az utolsó fejezetben összefoglaljuk a cikk eredményeit és kitérünk a témához kapcsolódó lehetséges jövőbeli továbbfejlesztési irányokra.
Quality of Experience (QoE); mobil egészségügy (mHealth); elektronikus egészségügy (eHealth); orvosi multimédia; minőségkiértékelés; IP alapú mobilitáskezelés
I.
BEVEZETÉS
Az eHealth, mint fogalom 1999 óta létezik és az elektronikus infokommunikációs rendszerek használatát jelenti az egészségügyben. Az eHealth témakörébe eredetileg az orvosi adatok (például leletek) digitális átvitele és tárolása, illetve a digitális megoldások különféle oktató-jellegű felhasználásai [1], [2] tartoztak. A fogalom gyorsan tágult, és egy 2005-ből származó kutatás megállapította, hogy a szakemberek az eHealth témakör alatt rendkívül sokféle felhasználást értenek. A szerzők hangsúlyozták, hogy a fogalom nem rendelkezik egységes, tömör meghatározással [3]. Több, mint 10 évvel később sincs ez másként: az eHealth hihetetlen széles spektruma magába foglalja a távorvoslást (telemedicina), a páciens egészségügyi állapotát a távolból figyelő rendszereket és a klinikai információs rendszereket [4], [5] egyaránt.
II.
MOBIL EGÉSZSÉGÜGYI SZOLGÁLTATÁSOK ÁTTEKINTÉSE
Az mHealth megoldások kihasználják a mobil hálózatok, okostelefonok és a hordozható orvosi szenzorok lehetőségeit arra, hogy új vezeték nélküli megoldásokat kínáljanak pl. a telemedicína és a betegek monitorozásának területein [9]. Egy 2014-ben publikált felmérés megmutatta az mHealth leggyorsabban fejlődő területeit [10]: betegmonitorozás, betegkövetés, vészhelyzetre adott reagálás, gyógyszerek adagolása és gyógyszerek felügyelete. A betegmonitorozásra példa a magyar fejlesztésű Laborom iOS és Android alapú okostelefonokra fejlesztett ingyenes applikációja [11].
A 2000-es évek elején, a mobil világ újításainak hatására, egy új terület született az eHealth-en belül: az mHealth. Az ebben a témában létező megoldások kiaknázzák a folyamatosan fejlődő telekommunikációs hálózatok adta
32
A hordható, szenzorokkal ellátott, okostelefonnal kommunikáló készülékek segítségével a betegek monitorozása egyszerűbbé és pontosabbá válik. Ezen monitorozást valósítja meg valósidőben az Empatica által fejlesztett E4 okoskarkötő, amely a hordozójával kapcsolatos egészségügyi adatokat szolgáltat okostelefonos alkalmazások számára, például kardiovaszkuláris jelekről, test hőmérsékletről és elektromos aktivitásról [12].
hagyományos egészségügy minőségi és biztonsági előírásait [17]. Az eHealth következő területei különböző minőségbeli követelményt állítanak, például: szakmai, klinikai és nem klinikai (pl. oktatás). Az említett területek közül egyértelműen a klinikai alkalmazások rendelkeznek a legszigorúbb követelményekkel. További szubjektív tényezők is befolyásolhatják a szolgáltatás minőségét, például: a tartalom típusa (videó, hang, kép), a szolgáltatás nyújtásának helyzete (vészhelyzet, kórházi vagy járóbeteg ellátás) és környezete (valós idejű és nem valós idejű felhasználás) [17].
Diagnosztikai célú mHealth alkalmazások közül a Philips által fejlesztett Lumify elnevezésű termék [13] egy egyszerű, hordozható ultrahang megoldást valósít meg, egy kézi ultrahang készülékkel és a hozzá tartozó okoskészülék alkalmazás támogatásával. A megoldás otthoni diagnosztizálásra, sürgősségi vagy vészhelyzet esetén történő alkalmazásra való.
QoS és QoE igényei Elengedhetetlen az a követelmény, hogy a multimédiás mHealth szolgáltatást olyan robosztus vezeték nélküli szélessávú hálózaton működjön, amely biztosítani tudja a megfelelő sávszélességet. A következő mHealth szolgáltatások kritikus sávszélesség igényeket támasztanak: vezeték nélküli diagnosztikai rendszer távoli páciensek részére, orvosi videók élő-közvetítésén alapuló kórházi konzultáció és váratlan sürgősségi helyzet esetén a helyszín és a kórház közti adatátvitel [18]. A vezeték nélküli hálózatot használó szolgáltatás optimalizálása esetén meg kell határozni az mHealth alkalmazás QoS követelményeit (pl. késleltetés és csomagvesztés), ezt részletezi a [19] tanulmány. A [20] cikk szerzői ahhoz, hogy kielégítsék a több szenzoron alapuló páciens állapotát figyelő rendszerek esetén az orvosi szintű QoE/QoS igényeket, egy megfelelő Wi-Fi hálózat kiválasztási módszert mutattak be, amely „több-szempontú” döntési modellt használ.
A Tata Consultancy Services IT vállalat munkatársai az IEEE orvosi és egészségügyi készülékek kommunikációjának szabványán alapuló „Connected Health” elnevezésű keretrendszert alkották meg [14]. A keretrendszer egy páciens esetén összefoglalja a vezetékes és vezeték nélküli orvosi eszközök által a felhasználójáról szolgáltatott azon adatokat, melyek távmonitorozás alatt keletkeznek, például: súly, vérnyomás és testhőmérséklet. Az adatok valós időben figyelhetők meg különböző grafikus módok segítségével, így adott eseményekre azonnali visszajelzések adhatók. III.
SZUBJEKTÍV ÉLMÉNYMINŐSÉG BEMUTATÁSA DIGITÁLIS EGÉSZSÉGÜGYI ALKALMAZÁSOK ESETÉN
Az eHealth vagy mHealth alkalmazás tervezése kihívás, mivel szempontok széles skáláját kell szem előtt tartani. Ilyen befolyásoló tényezők lehetnek például: szakemberek és páciensek igényei, technológiai korlátok, gazdasági megfontolások és jogi akadályok. A [15] forrás statisztikája kiemeli, hogy a digitális egészségügyi szolgáltatások tervezése során felmerülő legfontosabb faktor a felhasználói elfogadás.
IV.
ELVÉGZETT MÉRÉSEK EREDMÉNYEINEK ISMERTETÉSE
Egészségügyi intézetbe tervezett digitális egészségügyi alkalmazás esetén fontos kihangsúlyozni a diagnosztikai relevanciát. Egészségügyi szakembereknek a fejlesztésbe történő bevonásával biztosítható az IT innováció érvényesítése. Néhány tanulmány (például a [21][22][23][24]) a veszteséges tömörítési eljárásokat vizsgálja orvosi videófelvételek esetén, a nagy sávszélesség igény és magas tömörítési arány csökkentésének érdekében. Az orvosi felvételek tömörítése során olyan mértékű minőségromlás következhet be, amely befolyásolhatja a felvétel diagnosztikai relevanciáját. Ennek a minőségromlásnak a vizsgálatához objektív vagy szubjektív minőség kiértékelési módszert lehet alkalmazni. Hasonlóan alkalmazhatóak a kiértékelési módszerek a vezeték nélküli kommunikációnál a szélsőségesen változékony átviteli környezet által közvetlenül vagy közvetve okozott minőségromlás a jellemzésére.
A szubjektív élményminőség (QoE) definíciója a következő: egy alkalmazás vagy szolgáltatás elfogadottsági szintje, a végfelhasználó szubjektív érzékelése alapján. A meghatározásból következik, hogy a QoE a rendszer egészére vonatkozik (végponttól végpontig). Ahhoz, hogy a QoE mérőszámok értelmezhetők legyenek egy teljes rendszer esetén az átvitelre, a rendszer szolgáltatásminőségét (QoS) meghatározó paramétereket is ismerni kell [16]. A.
Multimédiás mHealth alkalmazást kiszolgáló hálózat
B.
QoE meghatározása és szerepe az elektronikus és
mobil egészségügyi szolgáltatások esetén A QoE fontossága az eHealth esetén nyilvánvaló. Orvosi adatok elvesztése hamis diagnózishoz vezethet, vagy az adatok késése befolyásolhatja például a távsebész munkáját. Továbbá egy állandó egészségügyi állapotot figyelő rendszer esetén, amely heterogén hálózatot (HetNet) használ, az orvosi felvételek esetleges diagnosztikát befolyásoló átviteli hibáktól mentesnek kell lenniük. Fontos meghatározni az eHealth szolgáltatás jellemzőit, a QoE szerepével együtt, annak érdekében, hogy a felhasználói elfogadás növekedjen. Elvárható egy eHealth szolgáltatástól, hogy kövesse a
A [25] cikk csoportosítja és részletezi a különféle orvosi álló- illetve mozgókép minőség értékelő lehetőségeket. Az objektív módszerek által pontosabb kép kapható a minőséget illetően, mint a szubjektív módszerek esetén, ám azok hátránya, hogy nagyobb előkészületet és tervezést igényelnek, illetve résztvevők bevonásával járnak. Továbbiakban a QoE, mint fogalom a diagnosztikai relevanciát fejezi ki, abban az esetben, ha a kiértékelést végző személy az orvosi képalkotást tekintve szakember (például szülész-nőgyógyász, radiológus).
33
A mérésekbe szokás nem szakember (laikus) személyeket is bevonni, az ő esetükben a QoE-t a klasszikus értelemben kell érteni, tehát a laikusok csak a felvételek minőségét értékelik. Jelen fejezet összefoglalja az adott mérési helyzetet és bemutatja a jelenlegi eredményeket.
1. táblázat: A vizsgált forgatókönyvek
A. Adott mérési helyzet A méréshez olyan orvosi multimédia-adatokat választottunk, melyeknek széleskörű felhasználási lehetőségeik vannak és kellően terhelik a heterogén vezeték nélküli hálózatokat (3G/4G/Wi-Fi). Ezen jelek a digitális ultrahang és EKG adatok voltak, melyek felhasználása történhet például: kórházi élő-videóközvetítésen alapuló konzultáció során vagy olyan sürgősségi esetekben, melyeknél a mentőautó és kórház, vagy otthon és kórház között történik a vezeték nélküli átvitel, például táblagépre. A QoE vizsgálat középpontja az ultrahang felvételek átvitele során bekövetkezett minőségromlás mértékének mérése volt. A Mátyásföldi Klinika által a kutatáshoz biztosított H.264 szabvány szerint kódolt magzati szívultrahang videók HD felbontásban (720x1280 pixel), 30 fps képkockasebességgel és 880kbps bitrátán UDP/RTP csomagolva álltak rendelkezésünkre. A PhysioNet [27] által szolgáltatott, 257 Hz-en mintavételezett 12-csatornás EKGjelek koszorúér betegségben szenvedő betegektől származnak. A digitális EKG-jeleknek a küldése és fogadása egyszerű UDP socket-alapon, egyedi csomagolóval, 950kbps-on történt.
Elérhető hálózat(ok)
Használt hálózat(ok)
BT (Mbit/s)
Használt technológia
#1
3G
3G
-
-
#2
3G
3G
5
-
#3
LTE
LTE
-
-
#4
LTE
LTE
5
-
#5
Wi-Fi
Wi-Fi
-
-
#6
Wi-Fi
Wi-Fi
5
-
#7
Több Wi-Fi AP, 3G
Több AP
5 (Wi-Fi)
MIPv6
#8
Wi-Fi, 3G
Wi-Fi, 3G
5 (Wi-Fi)
MIPv6+MCoA +FlowB
#9
Wi-Fi, LTE
Wi-Fi, LTE
5 (Wi-Fi)
MIPv6+MCoA +FlowB
Wi-Fi
MM
Az 1. ábrán látható eredmények értelmezése az alábbi. A két csoport eredményeinél az egyik legszembetűnőbb különbség az 5 Mbit/s háttér forgalommal terhelt LTE videó esetén figyelhető meg. Míg a laikusok átlagosan nagy különbséget érzékeltek a két videó minőségét illetően (átlag DOS: 73), addig az orvosok jóval közelebbi minőségűnek ítélték meg a két felvételt (átlag DOS: 49). Látható továbbá, hogy mindkét csoportnál voltak olyan felvételek, ahol az adott pontszámok igen hasonlóak voltak a csoport minden tesztalanyának esetében, ilyen például az orvosoknál az LTE hálózaton átvitt videó és a laikusoknál a háttér forgalommal terhelt 3G hálózat használata, illetve a Wi-Fi – Wi-Fi közti váltás esete. Az összesített eredményből kiderül, hogy az LTE Wi-Fi vertikális hálózatváltás esetén egyeznek meg a tesztalanyok véleményei leginkább. A mérésben egyelőre kis létszámban voltak résztvevők, így nem lehet általános következtetéseket levonni, ám a különböző forgatókönyvek közti különbségek így is látszódnak. Az 1. ábra jelmagyarázata a következő: az egyes dobozokban az x-ek az adott esethez tartozó DOS értékek átlagát, a vízszintes vonalak a dobozon belül a mediánt és a pontok a minta középső felébe tartozó belső pontokat jelölik.
A mérésnél 9 különböző vezeték nélküli átvitel esetén előforduló forgatókönyvet vizsgáltunk, melyeket az 1. táblázat foglal össze. A mérés módszertanát a korábbi releváns tanulmányok ([21][22][23][24]) és az ITU [26] ajánlása alapján dolgoztuk ki, mérési módszernek a DSCQS 1 eljárást alkalmaztuk. A méréshez táblagépen futtatott saját fejlesztésű Android alkalmazást használtunk. A méréssorozat a cikk írása közben is folyik, így jelen tanulmányunkban csak 3 orvos és 2 laikus által szolgáltatott eredmények szerepelnek, hasonlóan, mint a [24] cikk mérése esetén. Az 1. táblázatban használt nem egyértelmű rövidítések a következők. BT: background traffic (háttérforgalom), MM: mobility management mechanism (mobilitáskezelési módszer), AP: access point (hozzáférési pont), MIPv6: Mobile IPv6 (RFC 6275), MCoA: Multiple Care-of Addresses Registration (MIPv6 szabvány kiegészítése, RFC 5648), FlowB: Flow Bindings (MIPv6 szabvány kiegészítése, RFC 6089). A videók előállításához használt tesztkörnyezetet és az alkalmazott mobilitáskezelési technológiákat részletesen a [20] mutatja be.
V.
ÖSSZEFOGLALÁS
Jelen kutatás különböző mobilitási esetek orvosi multimédia tartalomra kifejtett hatásainak vizsgálatára elvégzett QoE mérést mutatta be. A cikk az elérhető mHealth megoldásokra adott rövid áttekintést, majd a QoE szerepét példákkal szemléltetve definiálta az elektronikus- és mobilegészségügy területeken, a negyedik fejezetben bemutattuk a mérés jelenlegi eredményeit.
B. Mérési eredmények A mérésben résztvevők az 1. táblázatban leírt felvételeket és hozzájuk párban állított referencia felvételek minőségét értékelték ki egy ötfokú folytonos skálán (nagyon rossz, rossz, közepes, jó, nagyon jó). Az így páronként kapott pontoknak a különbségét kell venni, majd azt 0-tól 100-ig terjedő skálára kell átváltani (DOS: Differential Opinion Score), ahol, ha minél alacsonyabb érték adódik, annál jobban teljesített a tesztvideó a referencia felvételhez képest. 1
ID
A további mérési eredmények beérkezése után komplexebb statisztikai modelleket lehet alkalmazni az eredmények kiértékelésére, így pontosabb kép kapható az egyes videók minőségéről. A kutatás kibővíthető további olyan felvételek vizsgálatával, melyeknél még fontosabb, hogy a felvétel valósidejű átvitele a lehető legkevésbé befolyásolja annak minőségét. A következő forgatókönyvek igazán kritikusak: a sürgősségi, az otthon történő vizsgálatok és távkonzultáció esetei.
Double Stimulus Continuous Quality Scale
34
P. G. Svensson: „eHealth Applications in Health Care Management”, eHealth Int. 2002; 1: 5. [6] World Health Organization (WHO): mHealth - New horizons for health through mobile technologies, Based on the findings of the second global survey on eHealth,Global Observatory for eHealth series - Volume 3, 2011. [7] M. Razaak et al.: A Study on Quality Assessment for Medical Ultrasound Video Compressed via HEVC, IEEE Journal of Biomedical and Health Informatics, vol. 18, p. 2168-2194, 2014. [8] Axis Communications: „An explanation of video compression techniques”, white paper, 2008. [9] Istepanaian RS et al.: Guest editorial. Introduction to the special section: 4G Health - the long-term evolution of mHealth, IEEE Trans Inf Technol Biomed., vol. 16, p. 1-5, 2012. [10] Compass Intelligence: „mHealth Market Analysis: Opportunities and Evolving Ecosystem”, report, 2014. [11] Laborom, http://www.laborom.org/ [12] Empatica E4 wristband, http://www.empatica.com/e4wristband, 2016. 04. 04. [13] Philips: Lumify, http://www.lumify.philips.com/web/, 2016.04.21. [14] Ashok Khanna et al. (Tata Consultancy Services): Realtime Patient Helath Monitoring with Connected Health Solutions, white paper, 2014. [15] V. A. Rojas-Mendizabal et al.: Toward a model for Quality of Experience and Quality of Service in e-health ecosystems, Procedia Technology 9, p. 968-974, 2013. [16] Szendrői Balázs: Felhasználói élményt minősítő rendszer kidolgozása, Budapesti Műszaki és Gazdaságtudományi Egyetem, szakdolgozat, 2013. [17] Muhammad Ullah et al.: On the Ambiguity of Quality of Service and Quality of Experience Requirements for eHealth Services, Medical Information and Communication Technology (ISMICT), 2012. [18] S. A. Garawi et al.: 3G Wireless Communication for Mobile Robotic Tele-ultrasonography Systems, IEEE Comms. Mag., vol. 44, no. 4, pp.91-96, 2006. [19] Robert S. H. Istepanian et al.: Medical Quality of Service (m-QoS) and Quality of Experience (m-QoE) for 4GHealth Systems, Multimedia Networking and Coding, IGI Global, p. 359-376, 2013. [20] N.Varga et al: A network-assisted flow mobility architecture for optimized mobile medical multimedia transmission, Annals of Telecommunications 1: pp. 114., 2016. [21] Nedia Nouri et al.: Subjective MPEG2 Compressed Video Quality Assessment: Application to Tele-Surgery, IEEE International Symposium on Biomedical Imaging: From Nano to Macro, p. 764-767, 2010. [22] C. T.E.R. Hewage et al.: Quality evaluation of compressed 3D surgical video, 2nd International Workshop on Service Science for e-Health, IEEE HEALTHCOM, p. 71-76, 2014. Manzoor Razaak et al.: Rate-Distortion and Rate-Quality Performance Analysis of HEVC Compression of Medical Ultrasound Videos, Procedia Computer Science 40, p. 230236, 2014. Hongtao Yu et al.: Applications and Improvement of H.264 in Medical Video Compression, IEEE Transactions on Circuits and SystemsI: Regular papers, vol. 52, no. 12, p. 2707-2716, 2005. Manzoor Razaak et al.: Medical Image and Video Quality Assessment in e-Health Applications and Services, EEE HEALTHCOM, p. 6-10, 2013. ITU-R BT.500-13: Methodology for the subjective assessment of the quality of television pictures, 2012. A. L. Goldberger et al.: PhysioBank, PhysioToolkit, and PhysioNet: components of a new research resource for complex physiologic signals. In Circulation, volume 101, pages 215–220, 2000. [5]
1. ábra: Mérési eredmények összefoglalása: orvosok, laikusok eredményei és az összesített eredménytáblázat [23]
IRODALOMJEGYZÉK [1]
[2] [3] [4]
Mitchell J.: „From telehealth to e-health: the unstoppable rise of ehealth. Commonwealth Department of Communications”, Information Technology and the Arts, Australia, 1999. Vincenzo Della Mea: „What is e-Health (2): The death of telemedicine?”, J MedInternet Res, Vol 3, No 2, 2001. Hans Oh et al.: „What Is eHealth (3): A Systematic Review of Published Definitions”, J Med Internet Res, Vol 7, No 1, 2005. eHealth Industries Innovation Centre: What is eHealth? A new definition for eHealth, http://www.ehi2.swan.ac.uk/en/what-is-ehealth.htm, 2016. 03. 28.
[24]
[25] [26] [27]
35
Felhasználók pozicionálása 4. generációs mobil hálózatokban Danyi Ádám Vilmos
Dr. Imre Sándor
Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar Hálózati rendszerek és szolgáltatások tanszék Budapest
[email protected]
Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar Hálózati rendszerek és szolgáltatások tanszék Budapest
[email protected] már kifejezetten beltéri környezetből indított hívásokra, valamint az LTE hálózatra specifikálták a szabályozást, ahol az alábbi értékek szerepelnek kritériumként (a 911-es segélyhívószámra érkezett hívások pozíciójára vonatkoztatva, [2]:
Kivonat — A cikk keretében rávilágítok a mobil hálózat segítségével történő pozicionálás fontosságára, valamint röviden bemutatom a 4. generációs mobil hálózatokban alkalmazható, szabványos pozicionálási eljárásokat. A cikk további részében bemutatom az egyik 4. generációs helymeghatározási módszer (E-CID) szimulációs eljárással történő vizsgálatának eredményeit. A szimulációkhoz egy a tanszékünkön elkészült MATLAB alapú szimulációs környezetet választottam, amely alkalmas a különböző pozicionálási technikák tesztelésére a 4. generációs mobil hálózatokban, valamint könnyen bővíthető újabb (helymeghatározási) technikákkal.
A vízszintes irányú pozicionálás kritériumai:
koordinátára
vonatkozó)
• 2 éven belül: Az összes hívás legalább 40 %-nak helyzetét 50 méteres pontossággal kell ismerni • 3 éven belül: Az összes hívás legalább 50 %-nak helyzetét 50 méteres pontossággal kell ismerni
Kulcsszavak — Pozicionálás, 4G, LTE, Helymeghatározás, E-CID
I.
(X,Y
• 5 éven belül, vagy legkésőbb 6 hónappal azután hogy a VoLTE (Voice over LTE) szolgáltatás kereskedelmi forgalomba kerül: Az összes hívás legalább 70 %-nak helyzetét 50 méteres pontossággal kell ismerni
BEVEZETÉS
Pozicionálás alatt azt a folyamatot értjük, amikor a rendelkezésünkre álló technikai eszközök és technológiák segítségével, meghatározzuk egy adott eszköz tartózkodási helyét, vagyis célszerűen annak koordinátáit valamilyen formátumban, melyet később ismert címmé tudunk fordítani. A pozicionálás napjainkban sokféle technológia, illetve technológiai eszköz segítségével történhet, mint például a GPS (Global Positioning System), a WiFi hálózatok, valamint a mobil hálózat segítségével.
• 6 éven belül, vagy legkésőbb 1 évvel azután hogy a VoLTE szolgáltatás kereskedelmi forgalomba kerül: Az összes hívás legalább 80 %-nak helyzetét 50 méteres pontossággal kell ismerni • A pozicionálás lehetőleg kevesebb, mint 30 másodperc alatt történjen meg! A szabály a vízszintes irányú pozicionálás mellet a függőleges irányú (Z koordináta) pozicionálásra is iránymutatásokat ad, mely szerint a szolgáltatók kötelesek lesznek olyan eljárást is kidolgozni, amely segítségével a Z (magassági) koordináta is meghatározható.
A mobil hálózat segítségével történő pozicionálás azért kiemelten fontos, mivel manapság egyre nagyobb az igény arra, hogy a mobil távközlésben résztvevők helyzetét minél nagyobb pontossággal és minél gyorsabban meg tudjuk határozni. A hívások jelentős része beltéri környezetből indul, ahol sok esetben csak a mobil hálózatra tudunk támaszkodni a pozíció meghatározása során. Erre az igényre az FCC (Federal Communications Commission – egy amerikai szabványosító szervezet), már a 2000-es évek elején megalkotta az E911-es szabályozást, amely különböző elvárásokat fektetett le a mobil hálózatokkal történő pozicionálással szemben [1].
II.
A MOBIL HÁLÓZATTAL TÖRTÉNŐ POZICIONÁLÁS GYAKORLATI SZEREPE
A pozicionálás pontossága azonban nemcsak a hívások és a segélyhívások szempontjából lehet fontos: Manapság, az okostelefonok világában, különböző, egyre gyorsabban terjedő és egyre nagyobb népszerűségre szert tevő helyfüggő alkalmazások használata során is fontos a pozíció minél precízebb ismerete. A megfelelő felhasználói élmény szempontjából nemcsak a precíz pozíció ismeret, hanem a helymeghatározás gyorsasága is kulcskérdés lehet. Ráadásul, ezen alkalmazások sok esetben beltéri felhasználásra készülnek
Az évek, és a mobil hálózat folyamatos fejlődése során a pozicionálás pontosságára vonatkozó értékek egyre szigorodtak. Az LTE-ben (Long Term Evolution) már dedikált lehetőségek és erre szabványosított rendszerelemek állnak rendelkezésünkre a felhasználók helyzetének meghatározásához. A már említett E911-es szabályozás legfrissebb, 2015-ben kiadott változatában
36
Egy példát megemlítve fontos szerepe lehet a pozíció ismeretének a különböző tömegközlekedési, utazási eszközökön, hiszen ezáltal könnyen megtudhatjuk, hogy merre jár a vonat vagy a busz, amire épp várunk, vagy megbecsülhetjük a haladás sebességéből, hogy mikor érünk a célba, valamint elakadás esetén megtudhatjuk, hogy hol vagyunk pontosan. Egy jó példa lehet a mobil hálózattal történő pozicionálás tömegközlekedési eszközökön való szerepvállalása a metróval való utazás: A metró az esetek túlnyomó részében a föld alatt tartózkodik, azonban abban a helyzetben nem tudunk a GPS-re támaszkodni, míg a korszerű mobilhálózat a föld alatt is rendelkezésünkre állhat. Erre jó példa, hogy Budapest összes metróvonalán elérhető az összes magyarországi szolgáltató LTE hálózata [3], [4], [5]. Az ilyen típusú alkalmazásnál kicsit nagyobb pontatlanság (~100 m) is megengedhető, azonban fontos, hogy a pozicionálás minél gyorsabban (akár néhány másodperc alatt) megtörténjen.
Az LPP alapján a pozicionálási technikák közül az LTE-ben alkalmazott technikák a következők, a legfrissebb szabványt (3GPP TS 36.355 V13.1.0 (2016-03) [8]) alapul véve: OTDOA (Observed Time Difference Of Arrival) pozicionálás
•
E-CID (Enhanced Cell-ID) pozicionálás
•
A-GNSS (A-GPS) alapú pozicionálás
•
Barommetrikus szenzoron alapuló pozicionálás
•
TBS (Terrestrial Beacon System) alapú pozicionálás
•
W-LAN alapú pozicionálás
•
Bluetooth alapú pozicionálás
Jelen cikk keretein beül a fentebbi pozicionálás metódusok közül az OTDOA-t, és az E-CID-t emelném ki, mivel ezek a hálózat egészére kiterjedő pozicionálási technikák.
A jelen kor legnépszerűbb és legelterjedtebb pozicionálási technológiái a GPS, valamint a mobil hálózat által támogatott párja, az A-GPS (Assisted-GPS) a nagy pontosságuk, és egyre szélesebb körben történő elérhetővé válásuk miatt jó megoldást jelenthetnek, azonban sajnálatos módon nem minden esetben működnek a kellő hatékonysággal. A GPS modul ugyanis beltéri környezetben nem biztos, hogy megtalálja a szükséges jelet, mivel az őt kiszolgáló műholdakra rálátás (LOS – Line Of Sight, az a geometria helyzet, amikor az adó és vevő között nincs terepakadály) szükséges. További problémákat vethet fel, ha a készülékben nem megfelelő minőségű a GPS chip, továbbá annak folyamatos használata sok plusz energiát emészthet fel, ami a mobil készülékek esetében a jelentősen korlátos akkumulátorkapacitás miatt különösen problémás. Továbbá problémát jelenthet az is, hogyha a készülékben rendelkezésre is áll a GPS egység, az a felhasználón múlik, hogy bekapcsolja-e azt. Bár a bekapcsolásra vonatkozó feltétel elmondható lenne az LTE szolgáltatásra is, azonban ideális esetben azt feltételezhetjük, hogy egy teljes lefedettséggel rendelkező LTE hálózatot használunk, implementált VoLTE szolgáltatással, ezért LTE szolgáltatásunkat felesleges lenne ki/be kapcsolgatni.
A. OTDOA pozícionálás Az OTDOA egy idő(különbség)mérésen alapuló pozicionálási módszer. Az eljárás [9] során a bázisállomások egyszerre elindítanak a mobilkészülékhez egy-egy jelsorozatot. Ahhoz, hogy ezek a jelsorozatok ténylegesen egyszerre induljanak el a mobil készülék felé, szükséges, hogy a bázisállomások nagy pontossággal szinkronizáltak legyenek egymással. Szerencsére ez a feltétel az LTE rendszerekben adott. Az indított jelsorozatok a mobilkészülékhez más-más időkésleltetéssel érkeznek meg, mivel az egyes bázisállomások különböző távolságokra vannak a készüléktől és egymástól. A mobilkészülék ekkor azt méri, hogy az egyszerre elküldött jelsorozatokat milyen időkülönbségekkel veszi. Ezek az időkülönbségek legyenek a következők:
A GPS-ekkel kapcsolatos problémák megoldása lehet a már említett negyedik generációs (4G) / LTE mobil rendszerek által felkínált, szabványosított helymeghatározás használata, annak minél nagyobb mélységekig történő kiaknázása. Ezen technológia megfelelő alkalmazásával ugyanis megoldhatóak azok a beltéri pozicionálási problémák, melyeket a GPS rendszer jelenleg nem tud áthidalni. Továbbá egy másik jelentős előny az, hogy a hálózat általi pozicionálás plusz fogyasztást sem igényel az általános hálózathasználatból eredő fogyasztáshoz képest (amennyiben a korábban leírt, ideális jellegű LTE hálózatot használjuk), mivel ebben az esetben pusztán a hálózat jeleit használjuk fel, míg a GPS modul alkalmazása esetén egy külön chipet is működtetünk, ami jelentős többletfogyasztást generálhat. III.
•
∆𝑡1 = 𝑇3 − 𝑇1
∆𝑡2 = 𝑇3 − 𝑇2
∆𝑡3 = 𝑇2 − 𝑇1
Az egyes időkülönbségeket a készülék saját nagypontosságú, de a rendszerrel nem szinkronizált órája alapján - a jelsorozatot előállítva - korrelációs módszerrel méri. Az egyes bázisállomás-pároktól állandó távolságkülönbségre elhelyezkedő pontok egy hiperbola mentén helyezkednek el. A hiperbolák metszéspontjában megtalálható lesz a mobilkészülék. Az eljárást a következő ábra szemlélteti:
AZ LTE-BEN SZABVÁNYOS POZICIONÁLÁSI ELJÁRÁSOK
Az LTE-ben szabványosított pozicionálási technikákat, azok részletes vezérlő – és hiba üzeneteit, valamint az üzenetek küldési – és fogadási módjait, továbbá a pozicionálást segítő adatok leírását és azok küldési – és fogadási módjait az LPP (LTE Positioning Protocol) írja le.
III.1. Ábra: OTDOA eljárás szemléltetése
37
A módszer azért is kiemelten fontos, mivel az LTE rendszerekben külön erre az OTDOA eljárás támogatására létrehozott referencia jelek (PRS - Positioning Reference Signal) segítik az ilyen módon történő helymeghatározást, valamint az E-CID eljárás részeként is felhasználhatjuk az OTDOA eljárást.
IV.
VIZSGÁLATA
A 4. generációs mobil hálózatokon történő pozicionálás vizsgálata során először egy szimuláció keretében vizsgáltam az E-CID eljárást. A szimulációkhoz alkalmas keretrendszert választottam, amelybe implementáltam az E-CID eljárást.
B. E-CID pozícionálás A módszer az elemi Cella ID alapján történő pozícionálás (a kiszolgáló cella azonosítója alapján a cella területét adjuk meg, mint lehetséges pozíciót) továbbgondolása, annak nagymértékű továbbfejlesztése, melyet kifejezetten az LTE-hez hoztak létre és először a Release 9-es LTE szabványban jelent meg [8].
A. A szimulációs keretrendszer kiválasztása A szimulációs keretrendszer kiválasztása során több szempontot is figyelembe vettem. Ezek a következők voltak:
Az alapgondolat itt is az, hogy ismerjük a bázisállomás (LTE-ben: eNodeB) koordinátáit, valamint azt, hogy a felhasználó éppen melyik cellában tartózkodik, és ennek alapján kezdjük el végezni a pozícionálást, további vizsgálatokat alkalmazva a rádiós jeleken. A számos vizsgált jelparaméter közül a legfontosabbakat emelném ki, melyek a következők [8]: •
Cell ID (physCellID) – A cella egyedi (fizikai) azonosítója
•
RSRP (rsrpResult) – Az RSRP (Reference Signal Received Power) mérés eredménye
•
RSRQ (rsrqResult) – Az RSRQ (Reference Signal Received Quality) mérés eredménye
1 bázisállomástól való távolság becslésével
•
3, vagy több bázisállomástól való távolság mérésével
•
Legalább 2, de inkább 3 bázisállomástól való távolságméréssel, AOA (Angle of Arrival) eljárást alkalmazva
•
A (későbbi) könnyű bővíthetőség
•
A moduláris felépítés
•
A jó paraméterezhetőség
Tanszékünkön korábban, szintén a 4. generációs hálózattal történő pozícionálás kapcsán már ki lett fejlesztve egy az említett paraméterekkel rendelkező, WINNER II-es csatornamodellre [10] építő, MATLAB alapú szimulációs keretrendszer, valamint korábbi projektek kapcsán tapasztalatom is volt az adott keretrendszerrel, így az E-CID eljárás vizsgálatához választásom szintén erre a szimulációs keretrendszerre esett. B. A szimulációs keretrendszer bemutatása A szimulációs keretrendszer fő funkciója az átviteli csatorna modellezése: mérhetünk vele különböző terjedési időket, teljesítmény értékeket, csillapításokat a beállításoktól függően. Az egyes adatok és paraméterek tárolása vektorok, vektorstruktúrák, valamint mátrixok segítségével történik. A MATLAB-os alapokon való nyugvásnak köszönhetően ezekkel egyszerűen lehet matematikai műveleteket végezni. A szimulátor alkalmas az egyes szimulációs elrendezések grafikus reprezentálására. Az LTE szimulációkhoz azért is megfelelő, mivel MIMO antennákat alkalmaz.
Az E-CID eljárás háromféleképpen hajtódhat végre, annak függvényében, hogy hány bázisállomással tudjuk felvenni a kapcsolatot. Ez a három eset a következő [9]: •
AZ E-CID ELJÁRÁS SZIMULÁCIÓVAL TÖRTÉNŐ
A második esetben a távolságméréshez felhasználják az „A” pontban részletesen bemutatott OTDOA pozicionálási technikát, valamint ennek eredményét pontosítják az RSRP és RSRQ mérések eredményének segítségével.
A szimulációs környezetben számos paramétert állíthatunk, mint például a bázis állomások száma, pozíciója, a hálózat frekvenciája. A környezetben megjelenik a többutas terjedés, mivel egy adott összeköttetésen („linken”) a modell 20 darab allinket („subpath”) alakít ki, melyek a környezet beállításától függően különböző utakon és modell szerint érnek el a mobil készülékhez. A keretrendszerben többféle környezetben (például városi vagy vidéki környezetben) végezhetünk szimulációkat. A szimulátorban akár 100 MHz-es sávszélességű jelet is beállíthatunk, míg a működési frekvencia 2 GHz és 6 GHz között változhat. Ez számunkra azért megfelelő, mivel az LTE rendszerek többek között a 2600 MHz-es frekvenciát is használhatják.
A harmadik esetben alkalmazott AOA eljárás során az egyes jelek különböző bázisállomásokra történő beérkezési irányszögeit vesszük alapul. Két megmért irány és egy ismert távolság adat (például a bázisállomások egymástól mért távolsága) segítségével már két bázisállomás segítségével is meg lehet határozni a felhasználó pozícióját. AOA eljárás esetén a mérést és a számolást is a bázisállomás végzi. Az eredményeket itt is pontosítják az RSRP és RSRQ mérések eredményének segítségével.
C. Az implementált E-CID algoritmus Az implementáció egyik legfontosabb pontja a kiszolgáló bázisállomástól való távolság becslése (rECID), ami alapján jelentősen leszűkíthető a mobil készülék tartózkodási helye. Ezt a távolságot a rendelkezésünkre álló időkésleltetési adatok, valamint a vett jel teljesítményének segítségével határozzuk meg. A távolság meghatározását követően megvizsgáljuk hány bázisállomás található a rendszerben:
Az első esetben a távolságbecslés a Cella ID ismeretének következtében ismert pozíciójú bázisállomástól történik, az RSRP és RSRQ teljesítmény és minőségmérések eredményének segítségével, a méréseket a mobil készülék végzi, majd a mért paramétereket a bázisállomás megfelelő részegységének átadva a szükséges számításokat a bázisállomás végzi el. Ebben az esetben az eredmény csak egy kör lesz a bázisállomás körül, amelyen belül a mobil készülék megtalálható.
38
Amennyiben 1 bázisállomás található a rendszerben, a rendelkezésre álló teljesítmény és időadatokból kiszámolt megbecsüljük a felhasználó bázisállomástól való távolságát
A táblázatból jól látható, hogy a pozicionálás átlagos hibája az összes vizsgált környezetben az 32 méteres hibahatáron belül maradt, ami kitűnő eredménynek tekinthető. Figyelembe véve a szimulációs eredmények szórását is, ami egyik környezetben sem volt több, mint 21 méter, bátran állíthatjuk, hogy az E-CID eljárás teljesíti az FCC által megszabott, és a bevezetésben ismertetett 50 méteres határértéket.
Amennyiben 2 vagy 3 bázisállomás található a rendszerben, felhasználjuk az AOA algoritmust és eredményét korrigáljuk a kiszolgáló bázisállomástól mért távolsággal Amennyiben 4 vagy több bázisállomás található a rendszerben, felhasználjuk a TDOA algoritmust és eredményét korrigáljuk a kiszolgáló bázisállomástól mért távolsággal
Az egyes eredmények az összes környezetben megfelelőnek tekinthetőek. Kiemelkedően jól szerepelt a szimulációk során a külvárosi környezet, ahol az átlagos hiba, és a maximális hiba, valamint a szimulációs eredmények szórása is a legkisebb. Ez annak köszönhető, hogy ebben a környezetben a legideálisabbak a körülmények a mobil hálózattal történő pozicionálásra: A cellaátmérők még nem túlságosan nagyok (mint vidéki környezet estén), azonban a jel terjedési körülmények kiválóak. kisebb a beépítettség, mint városi környezet esetében, ezért a jelek kevesebb reflexiót szenvednek, aminek következtében javul a pozicionálás hatásfoka.
Az itt említett AOA, illetve TDOA algoritmusok már korábban implementálásra kerültek a szimulációs környezetbe, a TDOA algoritmus implementálásában jómagam is részt vettem. D. A szimuláció eredményei Az egyes szimulációkat több különböző módon, 1, 2, 3 és 4 bázisállomás rendelkezésre állása esetén is elvégeztem, különböző környezetekben, a 2600 MHz-es LTE frekvenciát használva. A szimulációs elrendezések szimulációnként véletlenszerűek voltak, a bázisállomásokat a szimulált területeken egyenletesen elosztva helyeztem el.
V.
KONKLÚZIÓ
A szimulációs eredményekből jól látható, hogy a 4. generációs mobil hálózatokkal történő pozicionálásnak jelentős szerepe lehet a jövőben, különösen olyan helyzetekben, ahol a GPS nem áll rendelkezésünkre. HIVATKOZÁSOK [1]
FCC: Guidelines for Testing and Verifying the Accuracy of Wireless E911 Location Systems, USA, 2000. [2] FCC: Small Entity Compliance Guide, Wireless E911 Location Accuracy Requirements, Fourth Report and Order, Washington D. C.., 2015. [3] http://www.telekom.hu/mobil/lakossagi/ugyintezes/gyakori_kerdesek/15 23/milyen_lefedettseg_erheto_el_a_budapesti_metrovonalakon_?appid= tudasbazis&tudasbazis-eventType=8 (2016. 04.24) [4] http://www.lokal.hu/2015-10-teljes-a-vodafone-4g-lefedettsege-ametrovonalakon/ (2016.05.19.) [5] http://pcworld.hu/mobil/lte-szolgaltatas-a-4-es-metroban-is.html (2016.05.19.) [6] 3GPP TS 36.355 V13.1.0: "Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (E-UTRA); LTE Positioning Protocol (LPP)", Release 13, 2016-03 [7] Takács Gy.: Helymeghatározás mobiltelefonnal és mobil hálózattal, Híradástechnika, LXIII. Évfolyam, 21-22 (2008/8) [8] 3GPP TS 36.355 v9.0: "LTE, Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (E-UTRA), LTE Positioning Protocol", Release 9, 2009-12 [9] Rohde & Schwarz: LTE Release 9 Technology Introduction White paper [10] IST-WINNER D1.1.2 P. Kyösti, et al., "WINNER II Channel Models", ver 1.1, Sept. 2007.: https://www.ist-winner.org/WINNER2Deliverables/D1.1.2v1.1.pdf
IV.1. Ábra Egy lehetséges szimulációs elrendezés
Jelen cikkben csak a valósághoz legközelebb álló, 4 bázisállomásos eset eredményeit ismertetem. Az eredményeket összefoglaló táblázatban a pozicionálás hibáját tüntetem fel, ami azt mutatja, hogy a mért pozíció hány méterrel tér el a valós pozíciótól. Ennek kiszámítása a következő képlettel történik: 2
2
ℎ = √(𝑥𝑣𝑎𝑙ó𝑠á𝑔𝑜𝑠 − 𝑥𝑏𝑒𝑐𝑠ü𝑙𝑡 ) + (𝑦𝑣𝑎𝑙ó𝑠á𝑔𝑜𝑠 − 𝑦𝑏𝑒𝑐𝑠ü𝑙𝑡 )
Így, az egyes szimulációk során a következő eredmények születtek: E-CID eljárás szimulációs eredményei Környezet
Átlagos hiba [m]
Szimulációs eredmények szórása [m]
Minimum hiba [m]
Maximum hiba [m]
Városi
24,69
19,63
4,37
60,22
Külvárosi
22,49
8,3
10,75
34,58
Vidéki
31,73
20,42
3,81
77,03
39
Listing Regional Failures Balázs Vass∗† , ∗ Department
of Operations Research, Eötvös University, Budapest, Hungary,
[email protected] Future Internet Research Group, Budapest University of Technology and Economics
† MTA-BME
to this problem with a technique that can significantly reduce the number of possible failure states that should be added as an SRLG to cover all regional failures that does not affect any node. In practice, regional failures can have any location, size and shape. It is a common best practice to fix the size or shape of regional failures, for example as cycles with given size (also called disk) [1], squares, equilateral triangles, etc.. Another approach to analyse the network vulnerability against regional failures is using probabilistic failure models, where each link in the SRLG has some probability to fail [2]. In this study we show an efficient way to generate the SRLGs of regional link failures which erase the network elements in a circular area and do not affect nodes. Based on the model and assumptions described in Section II, we have shown that with these assumption the number of SRLGs is small, O(|V |), in typical backbone network topology, and can be at most O(|E ||V |) in an artificial worst case scenario. We propose a systematic approach based on computational geometric tools that can generate the list of SRLGs in O(|V |2 ) steps on typical networks. We believe this result is a step towards filling the gap between the conventional SRLG based pre-planned protection and regional failures. A weakness of our study is ignoring node including failures. Such failures are left for future work. For now we may add all the O(|V |) single node failures to our SRLG-list as the sets of links incident to the failed nodes for upgrading the observed reliability of the network. The paper is organised as follows. In Section II we present the core mathematical model with several observations and in Section III we show the main result the O(|V 2 ) algorithm for generating the list of SRLG covering every regional link failures with a shape of disk that do not contain network nodes.
Abstract—Current backbone networks are designed to protect a certain pre-defined list of failures, called Shared Risk Link Groups (SRLG). During network design and operation protecting a failure not part of an SRLG is ignored as they assume to be extremely rare events. The list of SRLGs must be defined very carefully, because leaving out one likely failure event will significantly degrade the observed reliability of the network. The list of SRLGs is typically composed of every single link or node failure. It has been observed that some type of failure events manifested at multiple locations of the network, which are physically close to each other. Such failure events are called regional failures, and are often caused by a natural disaster. The number of possible regional failures can be very large, thus simply listing them as SRLGs is not a viable solution. In this study we focus on link failures only and assume nodes are never part of the failure. We provide a fast systematic approach for generating a list of SRLGs the protection of which is essential to increasing the observed reliability of the network. According to a practical assumption this list is very short with O(|V |) SRLGs in total, and can be computed very fast, in O(|V |2 ) time.
I. I NTRODUCTION Current backbone networks are built to protect a certain list of failures. Each of these failures (or termed failure states) are called Shared Risk Link Groups (SRLG), which is a set of links that is expected to fail simultaneously. The network is designed to be able to automatically reconfigure in case of a single SRLG failure, such that every connection further operates after a very short interruption. In practice it means the connections are reconfigured to by-pass the failed set of nodes and links. The list of SRLGs must be defined very carefully, because not getting prepared for one likely simultaneous failure event the observed reliability of the network significantly degrades. On one extreme is listing every single link or node failure as an SRLG. Often there is a known risk of a simultaneous multiple failure that can be added as an SRLG, for example if two links between different pair of nodes traverse the same bridge, etc. On the other hand, we have witnessed serious network outages because of a failure event that takes down almost every equipment in a physical region as a result of a disaster, such as weapons of mass destruction attacks, earthquakes, hurricanes, tsunamis, tornadoes, etc. For example the 7.1-magnitude earthquake in Taiwan in Dec. 2006 caused simultaneous failures of six submarine links between Asia and North America and hurricane Sandy in 2012 cased a power outage that silenced 46% of the network in the New York area. These type of failures are called regional failures. It is still a challenging open problem how to prepare a network to protect such failure events, as their location and size is not known at planning stage. In the study we propose a solution
II. M ODEL AND A SSUMPTIONS We model the network as an undirected geometric graph G(V, E ) with n = |V | nodes and m = |E | edges, we assume n ≥ 3. The nodes of the graph are embedded as points in the Euclidean plane, and the edges are embedded as line segments. The position of node v is denoted by (v x , v z ). A disk c(x, y, r ) is a circle with a centre point (x, y) and radius r . The failure caused by a disk is modelled as every interior node and edge with interior part is erased from the graph. For every disk c let E c denote the set of edges and nodes erased by c . Proposition 1. For any c 1 , c 2 ∈ C , c 1 ⊆ c 2 it holds that E c1 ⊆ E c2 .
40
Let C 0 denote the set of disks that do not have any node of V in their interior. Clearly, |C 0 | is infinite.
f is an exclusion-wise maximal element of F0 by definition of M0 , this is possible only if f = E c2 . We get that for every f ∈ M0 there exists a c 2 ∈ ∪{u,v}∈E O C 0u,v such that f = E c2 . This implies M0 ⊆
Claim 2. For any c 1 (x, y, r ) ∈ C 0 there exists a c 2 ∈ C 0 such that E c1 ⊆ E c2 and c 2 has at least 2 nodes of V on its boundary.
∪{u,v}∈E O M0u,v .
Proof. If E c1 = ;, than we can choose c 2 arbitrarily from among the non-empty set of disks with at least 2 points of V on their boundary. If there exists an edge e = {a, b} in E c1 , than we generate c 2 as follows. We start with disk c 1 (x, y, r ) and start to increase its radius. We do it until we reach a node u ∈ V . We can further blow the circle larger without loosing any covered area by moving the central point along the line (x, y) − (u x , u y ) while keeping u on the boundary. Assume indirectly that it never reaches a second node. We get a contradiction because c 1 intersects line ab and a, b ∈ V . Thus the circle will reach a second node v ∈ V . Let c 2 ⊇ c 1 be this circle having u, v ∈ V on its boundary. Clearly, E c2 ⊇ E c1 .
Before presenting our algorithm for determining M0 , we should take a look on its size. It turns out that |M0 | is O(nm). We use parameter θ0 for the maximum number of edges crossing the circumcircle of a Delaunay triangle. Since |M0 | can be asymptotically large, it is not possible to give an algorithm which is "really fast" on all graphs. On the other hand, our algorithm computes M0 in O(n 2 θ03 ) time (Thm. 5), what gives O(n 2 ) if θ0 is constant, which is a natural assumption for many types of networks. Our algorithm computes M0 in the following way. First it generates the Delaunay triangulation D O = (E O ,V ). After that for every {u, v} ∈ E O it generates sets M0u,v . Finally it computes M0 by gathering the globally maximal elements of sets M0u,v . We will realise this plan in Section III.
For nodes u and v , let C 0u,v be the set of disks from C 0 which have both u and v on the boundary. Firs let us ignore the edges of the network and focus only on the nodes. We are searching for disks of maximum size that do not have any nodes in interior. Clearly, each disk of maximum size passes through at least three nodes, otherwise its size could be further increased. By simplicity we assume that the nodes are in general position i.e. no four nodes are on the same cycle and no three nodes are on the same line. In this case connecting the three nodes we get triangles. The problem was deeply investigated in the past and it was shown the union of these triangles results a triangulation of the graph, called Delaunay triangulation [3]. Let D O = (E O ,V ) denote the Delaunay triangulation on the set of nodes, where E O denotes the edges of the triangulation, which can be very different form the edges of the network. In Delaunay triangulation no circumcircle of any triangle contains node in interior. Another interesting property that the dual graph of the Delaunay triangulation is called Voronoi diagram [4]. An important observation is the following.
III. T HE A LGORITHM Consider the Delaunay triangulation D O = (V, E O ) and the set T0 of Delaunay triangles given by their vertices. Since D O is a planar graph, for an edge (u, v) there exists one or two nodes in V that are neighbours of both u and v . If there exist two points of this kind, let us call them w 1 and w 2 . In this case both {u, v, w 1 } and {u, v, w 2 } are elements 1 2 of T0 . Let C u,v and C u,v be the disks with u, v, w 1 and u, v, w 2 on the boundary. If there exists only one common neighbour w 1 of u and v , 2 1 be an infinitely be the same as before, and let C u,v let C u,v large disk with boundary going through u and v not containing w 1 . Thus {u, v, w 1 } ∈ T0 and {u, v, w 2 } ∉ T0 . Let T0t denote the set of Delaunay-triangles which have common edge with t , for all t ∈ T0 . 1 ∪ It is easy to see that all disks in C 0u,v are covered by C uv 2 C u,v . 3 1 2 1 Let e ∈ E u,v iff e ∈ E intersects C u,v ∩ C u,v , e ∈ E u,v iff 3 1 2 2 3 e ∈ E \ E u,v intersects C u,v \ C u,v and e ∈ E u,v iff e ∈ E \ E u,v 2 1 intersects C u,v \ C u,v (see Figure 1). Using the previous plan and the specific properties of the Delaunay triangulation we proved the next theorem.
Proposition 3. C 0u,v is non-empty iff {u, v} is an edge of the D O = (V, E O ) Delaunay triangulation.
Theorem 5. M0 can be computed in O(n 2 θ03 )) using Algorithm 1, and has O(nθ0 ) elements, each of them consisting of O(θ0 ) edges.
Let F0 and F0u,v be the set of failures caused by elements of C 0 and C 0u,v , respectively. Formally, F0 = {E c |k ∈ C 0 } and F0u,v = {E c |k ∈ C 0u,v }. We call the elements of F0 regional link
Proof. At line 1 the Delaunay triangulation can be computed in O(n log n) time [3]. Sets T0 and T0t for all t ∈ T0 also can be computed in O(n log n). In line 2 we do some preparation in constant time for every i Delaunay edge {u, v}, then we calculate sets E u,v for all {u, v} ∈ 2 E O in O(n θ0 ) time according to Lemma 8. In line 3 we generate sets M0u,v in O(n 2 θ02 ) time (Lemma 9). Finally, in line 4 M0 is calculated from lists M0u,v in O(n 2 θ03 ) time (Lemma 12).
failures, or simply link failures. Let denote M0 and M0u,v the exclusion-wise maximal elements of F0 and F0u,v , respectively. Our goal is to determine M0 . Claim 4. M0 ⊆
S {u,v}∈E O
M0u,v .
Proof. Clearly, for all f ∈ M0 there exists a c 1 ∈ C 0 such that f = E c1 . According to Claim 2 and Prop. 3, there exists a c 2 ∈ ∪{u,v}∈E O C 0u,v for which E c2 ⊇ E c1 . This implies f ⊆ E c2 . Since
41
cannot be larger than θ0 times the number of the Delaunay triangles. We get m ≤ (2n − 5)θ0 .
c 1 C u,v
w2
w1 a
A graph family may have O(n 3 ) single regional failures. However, we are convinced that θ0 is small in case of typical backbone networks and there exists a small constant c that it never exceeds and thus |M0 | ≤ cn .
u
v
2 C u,v
B. Algorithm 2 (Method Getedgesets) i Lemma 8. Algorithm 2 computes sets E u,v for all {u, v} ∈ E O in O(n 2 θ0 ). If θ0 is constant, this gives O(n 2 ) time.
b
Proof. First we have to show the correctness of the algorithm. i Circles C u,v , i ∈ {1, 2} are the circumcircles of the Delaunay triangles, unless {u, v} is on the convex hull of V . By defini2 tion, if {u, v} is on the convex hull of V , E u,v is empty set. Therefore, it is easy to see that since in lines 5 - 8 we compute every edge set E t covered by circumcirlce of Delaunay tirangle i t , in lines 9 - 11 we also get set E u,v . Thus Algorithm 2 is correct. We make an estimation of the complexity of Algorithm 2 as follows. Clearly, calculations in lines 1-4 can be done overall in O(n) time. In lines 5 - 8 we get sets E t in O(n 2 θ0 ) time by Lemma 7. If θ0 is constant, this gives an O(n 2 ) complexity. i It is easy to see that lines 9 - 11 we find the desired E u,v sets in O(n 2 θ0 ), or if θ0 is constant, in O(n) complexity. The overall complexity of Algorithm 2 is O(n 2 θ0 ) time. If θ0 is constant, this means O(n 2 ).
1 Fig. 1: Example on a Delaunay-edge {u, v} with w 1 , w 2 , C u,v 2 1 2 3 and C u,v . Here E u,v = {{a, b}}, E u,v = {{a, b}, {c, w 2 }}, E u,v = {{c, v}}.
According to these results we can derive Theorem 5. Corollary 6. Assuming θ0 is upper bounded by a constant, M0 can be computed in O(n 2 ) time, and the total length of it is O(n). Algorithm 1: Generating the maximal regional link failures Input: G = (V, E ) Output: The set M0 of maximal single regional failures. begin 1 E O , T0 , T0t (t ∈ T0 ) ←DELAUNAY(V );
2
3 4
i E u,v (i ∈ {1, 2, 3}, {u, v} ∈ E O ) ← GETEDGESETS(V, E , E O , T0 ); M0u,v ({u, v} ∈ E O ) ← GENERATE i (V, E , E O , E u,v (i ∈ {1, 2, 3}, {u, v} ∈ E O )); M0 ← ELIMINATEREDUNTANTS(M0u,v , ∀{u, v} ∈ E O ); return M0
C. Algorithm 3 (Method Generate M0u,v ) Lemma 9. Algorithm 3 generates sets M0u,v in O(nθ02 ) time. Proof. Proposition 10 shows the correctness of Algorithm 3. We assume line 2 runs in constant time. This means that i for a given {u, v ∈ E O } in lines 1 and 2 we get values m a,b in O(θ0 ) time, in lines 3 and 4 we sort them in O(θ0 log θ0 ) time, and in lines 7-11 M0u,v is calculated in O(θ02 ) time. Since |E O | ≤ 3n − 6, this gives an overall complexity O(nθ02 ).
A. On the number of edges and size of θ0 Lemma 7. The number of edges is O(nθ0 ), more precisely m ≤ (2n − 5)θ0 . Proof. The Delaunay triangulation is a planar graph and thus |E O | ≤ 3n − 6. Since every Delunay triangle has 3 Delaunay edges, a Delaunay edge is edge of at most 2 Delaunay triangles, and there are at least 3 Delaunay edges on the convex hull of V , the number of Delaunay triangles is at most
Proposition 10. It can be shown that if a k ∈ C 0u,v does not contain L 1 [i −1] but contains L 1 [i ], then L 1 [ j ] is covered by k iff j ≥ i . Similarly, if k contains L 2 [i −1] but does not contain L 2 [i ], then L 2 [ j ] is covered by k iff j ≤ i − 1. Trivially, E 3 is covered by k , and that is also clear that for any e 1 ∈ E 1 and e 2 ∈ E 2 the edges e 1 , e 2 are covered by k iff m e11 + m e22 ≤ π.
2|E O | − 3 2 ≤ (3n − 6) − 1 = 2n − 5. 3 3
Corollary 11. For every {u, v} ∈ E O , |M0u,v | is O(θ0 ).
Since every c ∈ C 0 intersects at most θ0 edges of the network, and contains a Delaunay triangle and every edge intersects at least one triangle, the m number of the links
Proof. It can be deducted from the description and correctness of Algortithm 3.
42
Algorithm 3: Generaring sets M0u,v for all {u, v} ∈ E O
1 2 3 Algorithm 2: GETEDGESETS E u,v , E u,v , E u,v for all
{u, v} ∈ E O Input: V, E , E O , T0 i Output: E u,v for all i ∈ {1, 2, 3}, {u, v} ∈ E O
1 2 3
4
5
begin for {u, v} ∈ E O do 1 2 Determine w 1 , w 2 ,C u,v an C u,v ; 1 P ← the half plane having uv line as boundary and containing w 1 ("the half plane on left hand side"); P 2 ← the half plane having uv line as boundary and containing w 2 ("the plane on right hand side");
1
3 4 5 6 7 8
for t ∈ T0 do Et ← ;
7 8
E t ← E t ∪ {{a, b}}
10
10
for {u, v} ∈ E O do for i ∈ {1, 2} do if w i ∈ V then
M0u,v ← M0u,v ∪ {{L 1 (i ), . . . , L 1 (n), L 2 (1), . . . , L 2 ( j − 1)}} ∪ E 3 ; while m L1 1 (i ) +mL2 2 ( j ) > π and i ≤length(L 2 ) do i ← i +1
until i >length(L 1 ) or j >length(L 2 ); return M0u,v
i E u,v ← E w i uv ∆ \ E w 3−i uv ∆ ;
Algorithm 4: ELIMINATEREDUNTANTS Input: M0u,v for all {u, v} ∈ E O Output: M0 begin for {u, v} ∈ E O do for {w, z} ∈ E O , {w, z} 6= {u, v} do for f u,v ∈ M0u,v do for f u,v ∈ M0u,v do for f w,z ∈ M0w,z do if f u,v ⊇ f w,z then
i E u,v ← {{u, v}}
12
repeat while mL1 1 (i ) + mL2 2 ( j ) ≤ π and j ≤length(L 2 ) do
11
else if {u, v} ∈ E then 11
1 L 1 ←SORT(E 1 by m a,b values increasingly); 2 2 2 L ←SORT(E by m a,b values decreasingly); i ← 1, j ← 1; M0u,v ← ; ;
j ← j +1
9
9
i d m a,b ← max{m(ucv)|c ∈ [a, b] ∩ P i }
2
for {a, b} ∈ E do for t ∈ T0 do if [a, b] ∩C t 6= ; then
6
i Input: V, E , E O , E u,v (i ∈ {1, 2, 3}, {u, v} ∈ E O ) u,v Output: Sets M0 for all {u, v} ∈ E O . begin for {u, v} ∈ E O do i for i ∈ {1, 2} and {a, b} ∈ E u,v do
3 ← E w 1 uv ∆ ∩ E w 2 uv ∆ ; E u,v i return E u,v for all i ∈ {1, 2, 3}, {u, v} ∈ E O
D. Algorithm 4 (Method Eliminateredundants) Lemma 12. Algorithm 4 computes M0 in O(nθ03 ) using sets M0u,v .
M0w,z ← M0w,z \ f w,z
else if f u,v ⊂ f w,z then
Proof. We can prove the correctness of Algorithm 4 by checking that it eliminates all globally non-maximal elements of M0u,v and leaves exactly one copy of each element of M0u,v in the end. The proof of complexity is as follows. We have to compare O(n 2 θ02 ) times two sets of size O(θ0 ). Thus the overall complexity of Algorithm 4 is O(n 2 θ03 ). If θ0 is constant, this means O(n 2 ).
M0u,v ← M0u,v \ f u,v
1
2 3
ACKNOWLDEDGEMENTS
M0 ←
u,v {u,v}∈E O M0 ;
S
return M0
[2] S. Neumayer, G. Zussman, R. Cohen, and E. Modiano, “Assessing the vulnerability of the fiber infrastructure to disasters,” Networking, IEEE/ACM Transactions on, vol. 19, no. 6, pp. 1610–1623, 2011. [3] F. Aurenhammer, “Voronoi diagramsÑa survey of a fundamental geometric data structure,” ACM Computing Surveys (CSUR), vol. 23, no. 3, pp. 345–405, 1991. [4] M. De Berg, M. Van Kreveld, M. Overmars, and O. C. Schwarzkopf, Computational geometry. Springer, 2000.
I would like to express my deep gratitude to Erika BércziKovács, Attila K˝orösi and János Tapolcai, my research supervisors, for their patient guidance, enthusiastic encouragement and useful critiques of this research work. R EFERENCES [1] S. Neumayer, A. Efrat, and E. Modiano, “Geographic max-flow and mincut under a circular disk failure model,” Computer Networks, vol. 77, pp. 117–127, 2015.
43
Flow based load balancer with Round-Robin Bloom Filters Örs Szabó, Csaba Simon Department of Telecommunication and Media Informatics Budapest University of Technology and Economics Budapest, Hungary
networking costs. Having millions of data elements in any network it became increasingly important to develop efficient solutions for storing, updating, and querying them. One great idea introduced by Bloom filters is that by allowing the representation of the set of elements to lose some information, the storage requirements can be significantly reduced [2]. The Bloom filter is a space-efficient probabilistic data structure that supports set membership queries. This data structure provides a probabilistic way to represent a set that can never have false negatives (saying that an inserted element is not in the set) but can have false positive returns (saying that an element is part of the set when in fact it is not). Bloom filters can be used for flow based load balancing. One solution, using the adaptive highest random weight (HRW) method to account for the uneven flow size popularity, is described in [8].
Abstract—SDN gives the possibility to design new solutions for flow based load balancers, needed by the handling of quickly growing Internet data, and end user demands. A key element of this can be the Bloom filters and its probabilistic techniques to reduce information processing and networking costs. We present an OpenFlow standard compliant flow based load balancing solution with the use of RRBFs. We show that the RRBF based solution brings a promising approach to efficiently handle flows in a load balancer. The solution allows many possibilities to finetune the system depending on the ingress traffic characteristics, e.g. expected number of ingress flows, desired false positive probability, flow length etc. in order to achieve the most optimal flow distribution. Keywords-Round-Robin Bloom Filter; OpenFlow; Software-defined networking;
I.
load
balancing;
We designed and implemented a flow based load balancer solution using Round-robin Bloom filters (RRBF) supporting plug and play deployments. We solved the flow transient phenomenon occurring at the time when connecting the load balancer to the network. We ran a set of experiments in a simulated environment and proved that the solution works.
INTRODUCTION
Internet data traffic is quickly growing, as more and more people are getting easy access to different kinds of services, such as file sharing, video streaming, video-on-demand (VoD), IPTV, Voice-over-IP (VoIP), etc. Thus the data that needs to be transported from and to different nodes through a meshed network is increasing. This may cause capacity and performance issues on the serving nodes, which leads to the need of scaling. A commonly used technique is to group the serving nodes into a cluster, but still offer the service over a single access point (e.g., well known address). By doing so, the clients will still reach the service the same way as before. For this to work, a solution was needed to cleverly distribute the demand among the server cluster members. This functionality is provided by the load balancer: it tries to share the load within the cluster [1]. The packets transported over the Internet can be viewed as part of a session defined by the endpoints (e.g., source and destination addresses, port numbers). The load balancer should be able to identify the different sessions (or flows) and should direct the packets belonging to it to the same server within the cluster. Load balancing in Software-Defined Networking (SDN) can be achieved in different ways, one of which is to use Finite State Machine (FSM) models with defined network policies described in [6].
In Sec. II we present the Round-Robin Bloom Filter analysis. In Sec. III we discuss the Flow Based Load Balancer design and experiment results, and finally we draw conclusions in Sec. IV. II.
ROUND-ROBIN BLOOM FILTER
A. Background The accuracy of the Bloom filter depends on the filter size (m), the number of hash functions (k), and the number of elements included (n). The more elements are added to a Bloom filter, the higher the probability that the query operation reports false positives. A Bloom filter requires space O(n) and can answer membership queries in O(k) time. The below Table 1 examines the behavior of the three key parameters when their values are either decreased or increased. Table 1 Bloom filter key parameters Bloom Filter parameters Number of hash functions (k)
Nowadays many of the network solutions utilize probabilistic techniques to reduce information processing and
44
Increase More computation, lower false positive probability as k → k opt
Size of filter (m) Number of elements in the set (n)
More space is needed, lower false positive probability Higher false positive probability
Increasing or decreasing the number of hash functions towards kopt we can lower the false positive probability but the computations for the insertions and lookups will increase. The cost is directly proportional to the number of hash functions. A larger filter will result in fewer false positives. Fig. 1 Round-Robin Bloom Filter design (source: [2])
The calculation of false positive probabilities and the optimal number of hash functions for that is derived in [2]. It is shown that the false positive probability decreases as the size of the Bloom filter (m) increases, and it increases as more elements are added (n). In order to maintain a fixed false positive probability, the length of a Bloom filter must grow linearly with the number of elements inserted in the filter. The optimal Bloom filter size (m) for the expected number of elements (n) and false positive probability (p), is described in [2].
If we treat the incoming events as IP packets and their fingerprints being calculated from their IP headers, which we can call individual flows, then we can see that a consecutive number of packets of the same flow will have the same action executed, at least for (N-1)*T times, after which a reroute can happen. Assigning different output ports for the different actions means that we can create a load balancing solution among alternative paths. The sequence of the membership queries ensures that false positive answers of later filters will not influence the state associated with the original filter before it expires.
B. Round-Robin Bloom Filter Once a member is added to a BF, it cannot be deleted – during the lifetime of a BF, after a certain operation time it starts to be inefficient, because lots of expired flows are still referenced in the BF. In order to improve the applicability of BFs, several mechanisms were proposed to allow deleting members from BFs. One of the most efficient solutions is the Round-Robin Bloom Filter (RRBF). The design of the RRBF is derived in [3]. The operations over the RRBF are defined as follows: Membership query: we query for the existence of an event from the oldest to youngest filters and if a match is found then a corresponding action is executed without further queries. New element insert: if no match is found during the membership query, then the event is inserted into the youngest filter. Window jump: before entering into the next time slot, we reset the oldest filter and make a jump to select the next youngest and oldest filters.
III.
FLOW BASED LOAD BALANCER: DESIGN & EXPERIMENTS
In the previous sections we introduced RRBF, as a candidate solution to support efficient load balancing for large number of flows – typically in the backbone links. In this section we present an implementation of this system. Since the packet based networks are very dynamic and diverse, the implementation should be flexible, easily configurable and customizable. During the traffic engineering process the controlled flows, the available paths and the associated ports may change in time, which results in the request to change the RRBF configuration and the port assignments. SDN has been introduced in the last decade in computer networking to address this issue, separating the control and data planes from each other, and putting an open interface inbetween [5]. The cornerstone of the SDN framework is the control protocol over this interface that commands the switches, called OpenFlow. Having freedom in the control plane it gives room for innovation.
In the following we explain in brief the operation of a RRBF, summing up the detailed description from [2]. Fig. 1 presents an example of the RRBF operation. In each time slot, only one filter (red) will be used to insert new elements, while the others (cyan) are queried in decreasing age order. After N time slots, the oldest filter is reset and the next oldest and youngest filter will be selected in a round-robin fashion. When the event e(τ ) arrives in the 7th time slot, its hash is tested for containment in filters v4; v5; v1; v2 sequentially. If a match is found, the corresponding Ai action is executed and further querying is stopped. If no match is found, the event is inserted into filter v3 (the latest filter marked with red) and the corresponding A3 action is executed.
A. Design We show the design of the load balancer prototype supporting plug and play deployment by eliminating the flow transient at system start time. The issues presented in Sec. I. were considered during implementation, and the prototype was built in a way that the RRBF solution could be verified with different traffic characteristics. The system consists in the following modules: •
Emulated environment, provided by Mininet [7].
• Simulated OpenFlow controller, used to configure the switch with the necessary ports, tables and actions. Each table will have a different role, e.g. to match IP packets, select bloom filters or select output ports.
45
• Simulated OpenFlow switch [4], with internal RRBF system parameters, e.g. expected number of ingress flows, desired false positive probability, etc.
RRBF algorithm. For each ingress packet, after being matched as an IP packet by the flow entry and passed to the first group entry, we calculate the fingerprint as the XOR of source and destination IP addresses and then we check if it’s time to switch to the next youngest filter. If not, then we go through all the filters, from oldest to youngest, and do a membership query operation for the given fingerprint. If the fingerprint is present in any of the filters, we select that one; otherwise we do an insert operation to the youngest one. On the other hand, in case the period (T) has ended, we clear the oldest filter and recreate it, then shift the youngest filter to the next one and do the same as described above. Each bucket in the first group entry containing a filter, has the same action of forwarding the IP packet to the next group entry.
Fig. 2 shows the designed internal structure of the RRBF load balancer. There is only one flow table with one flow entry. The input port is passing all ingress packets to the flow entry. All packets are matched against the condition, eth_type=0x800, that is only IP packets will be processed further. The flow entry will pass the packets to the first group entry in the group table. Each bucket of the group entry contains a Bloom filter. Based on the Round-robin Bloom filter algorithm one bucket will be selected. Each bucket has the same action, passing the packets to the next group entry. The next group entry has a number of buckets, each associated with an output port. Based on the output port selection algorithm the packets will be sent out from one of the output ports.
D. Output port selection The implementation was also enhanced with a new output port selection algorithm. After the IP packet arrives to the second group entry, which has a number of buckets each having an action of forwarding the packet to an output port, it will be sent out on the selected port. Important to know, that after each period (T), when the youngest filter is shifted, we also search and select the least loaded port and assign it to the filter. So, at any given time, each filter has a port assigned to it which are continuously sending out packets, then at timeout, the youngest filter might get a new port assigned based on the number of transmitted packets on each port.
Fig. 2 Internal architecture of the RRBF based load balancer B. Control mechanism The following system parameters are implemented and can be controlled: • Number of Bloom filters (B) – it’s set by the controller via the OpenFlow protocol. • Number of output ports (P) – it’s set by the controller via the OpenFlow protocol. • Packet type – it’s set by the controller via the OpenFlow protocol. • Period (T) – time period in seconds after which there is a shift in Bloom filters, and the next one will be the youngest accepting new flows. • Epoch (Ep) – time period for the youngest Bloom filter until it becomes the youngest again, i.e. (B-1)*T seconds. • False positive probability (E) – used to calculate the number of hash functions (K) for the Bloom filters. • Number of elements (N) – number of expected flows per Bloom filter and it is used to calculate the size (M) of the Bloom filters. • Transient packets (Tr) – used to set the number of packets to be used at the beginning for flow transient elimination. • Flow rate (R) – used to decide if new output port can be selected for a filter depending on the rate of the ingress packets in the last period (T) compared to the number of ingress packets in the last epoch (Ep).
E. Flow transient elimination The implementation was also enhanced with a new flow transient elimination algorithm. Flow transient period is present at the time of connecting (or activating) the load balancer to the network. The input traffic can contain a lot of already active flows, and it is a concern that in the first period (T), the youngest filter can be filled with most of the ingress flows, and the system can remain unbalanced, because the first filter will not be cleared until the first epoch (Ep) has ended. In practice this means that all incoming flows during the first period (T) will be registered in the first youngest filter, and all other filters will remain empty. Therefore the youngest filter may fill up in a short period of time and so the false positive probability can increase significantly. The other issue introduced by the flow transient is that the flows present at the startup of the load balancer will always belong to the same filter. The system will get balanced only after most of the original flows decay, which can take time. To compensate for this flow transient problem, and to make plug and play deployment possible, the flow transient needs to be eliminated. We propose a solution that for a configurable amount of packets (Tr) at the beginning, the system will always rotate the youngest filter, as it would happen at the end of each period (T). The Bloom filter selection algorithm will be called for each consecutive packet, assuring that the existing flows will be associated to their original filters, and only the new flows will be stored in the youngest filter.
C. Bloom filter selection The implemented Bloom filter selection algorithm is compliant with the OpenFlow standard. The publicly available BF implementations were re-used and enhanced with the
46
RRBF with two BFs
N=100, E=0.01%
N=1000, E=0.01%
BF1 egress packets
37547
35652
35499
BF2 egress packets Egress packets due to false positive membership query
40943
42838
42991
13593
0
1236
BF1 egress flows
637
602
599
BF2 egress flows Egress flows due to false positive membership query
310
469
465
Total flows
flow the roles of the oldest and youngest filters were switched, so that each new flow could be stored in the next filter. The results, shown in Table 2 above, prove that the false positive probability can be influenced by the Bloom filter parameter values. Because the filters were not reset, in case the number of expected flows (N) was not high enough, false positives started to appear. We counted the number of egress packets and flows where the membership query resulted in false positive. This happened in case N was lower than the total number of ingress flows, or in case E was high enough.
N=1000, E=1%
124
0
7
1195
1071
1078
RRBF with flow transient
Table 2 Experiments with different settings of the number of expected flows (N) and false positive rate (E)
In this sub-section we illustrate the effect on the original RRBF proposal of the flow transient problem. We used a traffic trace in which ~65% of the flows in any period (T) were already active at least in the previous period as well. Fig. 4 shows the number of registered new flows per Bloom filter (bf_flow N) in every period (T). In the beginning the first Bloom filter from a RRBF mechanism with five BFs will carry more flows than the other ones, because it “keeps locked in” the long flows and so the flow distribution gets unbalanced. After an epoch has passed the first filter will be the youngest again and it will keep carrying its old flows.
Rotating the filters at every incoming packet gives the possibility for the incoming flows to be evenly distributed within the filters, ameliorating the flow transient effect. The solution can be further enhanced to achieve even better distribution of flows within the filters, e.g. by rotating the youngest filter only if the respective incoming packet was belonging to a new flow. This way we make sure that each filter will register new flows. F. Experiments A set of experiments were conducted with different system parameter combinations. The goal was to prove that the system is performing as expected under real-life traffic scenarios. We show below how the load balancer handles the flow transient at the beginning. We simulated the hot deployment scenario by running real-life traffic samples through the system. The publicly available Internet traffic traces were used provided for the research community from the SimpleWeb project [9]. The sample traces contain around 8000 to 16000 TCP/IP packets per period (T), and the ratio of new flows vs. old flows is around 35% to 92% per period (T) depending on the period length. Fig. 3 shows the flow distribution of one sample trace. It can be seen that on average ~8% of the flows present in a particular period (T) were also present at least in the previous period (T-1).
Fig. 4 Flows per Bloom filter with flow transient RRBF with eliminated flow transient Then we activate our flow transient eliminator solution and re-run the above experiment. Fig. 5 below shows the number of registered new flows per Bloom filter in every period (T). During the first period the incoming flows are evenly distributed within the Bloom filters, and this distribution keeps the system balanced throughout the measurement. Long flows (longer at least than one epoch) are carried by multiple filters.
Fig. 3 Ingress flow distribution Simplified RRBF experiment for the flow transient elimination We start with a basic experiment consisting of two Bloom filters each assigned to a separate output port. We want to examine the flow distribution and the false positive flow rate depending on the BF configuration. After every incoming new
Fig. 5 Flows per Bloom filter without flow transient
47
IV.
REFERENCES
CONCLUSIONS
We designed an OpenFlow compatible flow based load balancer with Round-robin Bloom filters supporting plug and play deployment scenarios with the help of our flow transient eliminator solution. We demonstrated in a simulated SDN environment, using real-life traffic samples that the solution can eliminate the transient flow problem at start time and the system remains balanced, meaning that the ingress flows are more evenly distributed within the Bloom filters. The solution is implemented in a simulated OpenFlow switch and it consists of the Bloom filter selection, output port selection and flow transient elimination algorithms together with a number of configurable parameters making it possible to do measurements with different parameter value configurations.
[1]
Cardellini, V., Colajanni, M. and Philip, S.Y., 1999. Dynamic load balancing on web-server systems. IEEE Internet computing, 3(3), p.2839. [2] Sasu Tarkoma, Christian Esteve Rothenberg, and Eemil Lagerspetz, “Theory and Practice of Bloom Filters for Distributed Systems”, IEEE Communications Surveys & Tutorials, Vol. 14. no. 1., 2012. [3] Róbert Szabó, “A Round-Robin Bloom Filter for Stateful Control over Event Streams”, 2013 IEEE 4th International Conference on Cognitive Infocommunications (CogInfoCom), 2013. [4] CPqD OpenFlow switch: http://cpqd.github.io/ofsoftswitch13/ (accessed on April 2016). [5] Open Networking Foundation: Software-defined Networking: The new norm for networks, 13th April 2012. [6] Yuanhao Zhou, Li Ruan, Limin Xiao, Rui Liu, “A Method for Load Balancing based on Software Defined Network”, Advanced Science and Technology Letters Vol.45 (CCA 2014), pp.43-48. [7] Mininet, http://www.mininet.org/. [8] Chengcheng Gou et.al., „A load-balancing scheme based on Bloom Filters”, in. proc. of the IEEE Second International Conference on Future Networks, Washington DC, USA, 2010, pp. 404-407. [9] SimpleWeb, http://www.simpleweb.org/wiki/Traces/.
Our future plan is to further investigate our solution in more complex traffic conditions. ACKNOWLEDGMENT The author thanks his Diploma Thesis supervisor Csaba Simon for his valuable comments to improve the paper.
48
A Fast and Efficient Algorithm for Online Resource Orchestration Balázs Németh, Balázs Sonkoly Budapest University of Technology and Economics, Department of Telecommunication and Media Informatics e-mail: {balazs.nemeth, balazs.sonkoly}@tmit.bme.hu Abstract—The extreme demands against the Internet of the future are unsatisfiable in the current networking architecture. Thanks to the revisited paradigm of Service Function Chaining (SFC) based on Network Function Virtualization and Software Defined Networking technologies, the envisioned networked world can be achieved. Due to the virtualization of data plane and softwarization of control plane, the resource optimization subsystem plays a vital role in the expected operation of the networking architecture. The provisioning of computing and networking resources, also known as orchestration problem, is N P-hard, but fast solution is essential even for very large networks, so heuristic solutions which are tractable in terms of algorithmic complexity are desirable. The present paper aims to describe such a resource orchestration solution, which is integrated into a novel SFC based networking architecture, and provides low running times and evenly distributed load.
I.
I NTRODUCTION
The recent paradigm shift in networking has been driven by Software Defined Networking (SDN) and Network Function Virtualization (NFV). SDN addresses the softwarization of the control plane, while the main goal of NFV is the softwarization of the data plane and middleboxes [1]. These techniques provide several benefits for different stakeholders of the networking ecosystem in terms of flexibility, scalability, costs (CAPEX and OPEX), and virtualization of resources. A typical network service consists of a series of service functions, traditionally implemented by middleboxes, that have to be traversed in a given order by traffic flows. Service chain (or more generally service graph) is an abstraction to describe high level services in a generic way and to assemble processing flows for given traffic. Due to the networking revolution driven by SDN/NFV and the evolution of cloud technologies, the concept of Service Function Chaining (SFC) has been revitalized and brought into the focus recently by both research and industry communities1 . Network services are realized on top of the underlying resources. Orchestrator is the core component of the architecture with the aim of operating the shared resources of the infrastructure optimally while provisioning the required high level services. One of the key elements of the resource orchestration is the optimization algorithm which is responsible for mapping requests to available resources. In our case, service graphs (containing virtual network functions and logical links between them) have to be embedded in substrate graphs (describing physical or virtual infrastructure), however, the requirements can be very tricky (e.g., delay requirements between arbitrary network functions, end-to-end bandwidth requirements, collocation constraint on given network functions). There is a 1 For instance, IETF Service https://datatracker.ietf.org/wg/sfc
Function
Working
Group:
49
number of algorithms proposed for similar or related problems following two different approaches. On the one hand, offline algorithms receive all requests as an input and seek for optimal or close to optimal solutions typically at the expense of long runtimes. On the other hand, online algorithms process individual requests and provide solutions on the fly based on heuristics. In this paper, we propose a novel customizable algorithm for service graph embedding which is able to jointly control and optimize the usage of compute and network resources, and it inherently supports network function sharing between multiple requests. The rest of the paper is organized as follows. In Section II, we introduce the problem of service graph embedding and main approaches for related problems. Section III is devoted to summarize our algorithm. In Section IV, the evaluation of the proposed mechanism is given and Section VI concludes the paper. II.
P ROBLEM D EFINITION
The problem of Virtual Network Embedding (VNE) is well-studied by the researchers of network virtualization. In VNE, the goal is to allocate network and computation resources for the requested virtual networks on a shared substrate network. Virtual nodes shall be hosted on substrate nodes, and communication links between virtual nodes shall be mapped to paths in the substrate network. An extensive survey on VNE algorithms collects the common elements from VNE problem variants and provides a detailed overview on the state-of-the-art solutions [2]. Most of the variants deal with constraints on the virtual nodes and links, such as requested number of CPUs and minimal bandwidth, respectively. An example formal definition for the VNE problem can be found in [3]. Service Function Chaining (SFC) has been revitalized based on the recent achievements of SDN and NVF researches. As a result, a novel mathematical problem has arisen rooted in VNE which we refer to as Service Graph Embedding (SGE). A service request is given as a Service Graph (SG), which consists of a set of directed connections on logical service elements and QoS requirements on the edges and paths. The computing and networking resources are described by the Resource Graph (RG). Users or other network domains are connected by Service Access Points (SAP) in both graphs. The notations used in the subsequent sections are summarized in Tab. I, and an illustration for the SGE problem is given in Fig. 1. A mapping of an SG to the RG solving an SGE consists of µ and λ functions which assign SG nodes and links to resources, respectively. Service Chains (SC) are defined as endto-end (E2E) paths in the SG, where endpoints are represented
as leg from now on, e.g. SG link 1 and nf 1 in Fig. 1). If such a pair cannot be mapped, the procedure backtracks for other possible mappings. The pseudo-code is shown in Alg. 1. An ordering on the legs is calculated by D IVIDE I NTO S UB CHAINS ().
Table I: Mathematical notations used in this paper. Notation V(G), E(G) P(G) PS (G) Ψ(SG) = {cp |p ∈ PS (SG)} cp = (Bp , Dp , p), Bp , Dp ∈ R+ 0 µ : V(SG) 7→ V(RG) λ : E(SG) 7→ P(RG)
Description Vertices and edges of G All simple paths of G Simple paths of G starting and ending in SAPs Set of E2E chains E2E bandwidth and delay requirement on path p Node and link mapping functions
A leg is denoted by (enf , nf ), where the link enf ∈ E(SG) terminates in the SG node nf ∈ V(SG), which are always mapped together, and this mapping is considered one greedy or backtracking step of the orchestration procedure. The mapping process iterates on each (enf , nf ) legs and tries to map them based on customizable preference parameters using heuristics implemented by M AP O NE NF() in line 7. Algorithm 1 SGE Algorithm 1: 2:
Figure 1: Illustration of Service Graph Embedding
by SAPs. The traversed SG nodes are Network Functions (NF) in a fixed order, defining the semantics of the chain, and the corresponding bandwidth and delay requirements specify the QoS parameters for the Service Chain (see Tab. I). The goal of the SGE is to minimize network resource utilization and maximize the number of embedded SGs. As a generalization of VNE, SGE is also N P-hard [4].
Some existing VNE algorithms can be used to partially solve an SGE problem, but generally, there are some aspects of SGE which are not supported by any of them. For instance, logical node collocation (mapping two neighbouring NFs to the same substrate node, e.g. nf 1 and nf 2 in Fig. 1) is neglected by ViNEYard [3], although some approaches have been made to fix this [4], direct collocation support is desirable. Contrary to VNE, SGE considers the functional types of logical nodes and maps them according to substrate network capabilities. More importantly, the maximal allowed latency requirement on an E2E path is not well adopted by most VNE problem variants so far.
3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:
procedure M AP(SG, RG, Ψ(SG)) ,→ µ, λ RG SG, RG, GΨ(SG) ← P REPROCESS(SG, RG, Ψ(SG)) Ψdiv (SG) ←D IVIDE I NTO S UBCHAINS(SG, Ψ(SG)) for all q ∈ Ψdiv (SG) do for all (enf , nf ) ∈ q do while µ(enf ) = ∅ or λ(nf ) = ∅ do success ←M AP O NE NF(enf , nf, q) if ¬success then (enf 0 , nf 0 ) ←P REVIOUS L EG() Undo mapping of (enf 0 , nf 0 ) (enf , nf ) ← (enf 0 , nf 0 ) end if end while end for end for return µ, λ end procedure
If the embedding step fails, P REVIOUS L EG() is used to retrieve the previous SG link - SG node pair, both denoted by primed variables in line 9. The existing mapping and resource reservation for leg (e0nf , nf 0 ) is undone, which establishes one backtracking step. In case of successful mapping step, the resources are reserved for leg (enf , nf ), the available delay of all affected Service Chains are updated and the mapping proceeds until all elements of SG are embedded to the Resource Graph and the result is returned. B. Preprocessing
A. Core processing
The P REPROCESS() of Alg. 1 prepares the input structures for the embedding process, and a helper structure is created. The end-to-end bandwidth requirement of Service Chains are added to link-wise bandwidth requirement of the SG, so from now on bandwidth requirement parameter Bp of all end-toend Service Chain cp ∈ Ψ(SG) are incorporated by the linkwise bandwidth requirement of SG links on path p ⊆ P(SG). The lower architecture layer reports the total networking and computing resources, in addition to the currently running NFs on the infrastructure. So during the preprocessing of RG, the available resources are calculated respecting the reserved resources for previously deployed services.
The orchestration algorithm greedily maps a Service Graph node and an adjacent link in one step (this pair is referred to
The mapping of SAPs from the SG can be done unambiguously to the SAPs of RG, so this is calculated in
III.
A LGORITHM
In this section, our algorithm is presented in hierarchical manner, focusing on the main ideas of the design. The goal of the orchestration algorithm is to maximize the number of provisioned SGs, which arrive online, and their resource requirements cannot be known in advance. The algorithm tries to evenly distribute the load to maximize the chances of a successful SG embedding in the future.
50
P REPROCESS() method, stored in µ structure and kept fixed during the whole orchestration. The definition of the helper structure, calculated in the preprocessing stage is denoted by RG GΨ(SG) and calculated as follows: RG GΨ(SG) = {Gcp |Gcp ⊆ RG, ∀cp = (Bp , Dp , p) ∈ Ψ(SG), (1) ∀v ∈ V(Gp ) : d(p.f irst, v) + d(v, p.last) ≤ Dp }
It contains an induced subgraph of RG for each Service Chain, which gathers all the nodes of RG whose sum of distances from the endpoints2 of the Service Chain measured in delay are not larger than the end-to-end delay requirement of the Service Chain. The matrix of d is calculated by FloydWarshall algorithm using edge delay as the weight function for the edges and nodes of RG, which needs to be done only once for a substrate network and d is cached for further RG orchestrations. In other words, the set GΨ(SG) contains a subgraph of RG for every Service Chain separately, which should be used to host all NFs of the corresponding SC. C. Service Chain division The goal of another important subroutine is to partition3 the E(SG) into simple paths, called subchains, and to determine an ordering between these subchains, which helps the algorithm to map the (enf , nf ) legs in predictable order. This is implemented by D IVIDE I NTO S UBCHAINS() function of Alg. 1. The subchain division subroutine takes into account the delay requirements of the Service Chains, contained in Ψ(SG), and ensures that the strict end-to-end chains are cut into less pieces, and mapped earlier during the mapping (so less placing possibility is compensated by less loaded RG). An NF node of the Service Graph can be used by multiple Service Chains, so that for these NFs host restrictions are saved to respect the sharing for all using SCs. A shared NF can only be hosted on a Resource Graph node, which is contained by RG all subgraphs Gcp ∈ GΨ(SG) for all cp Service Chains which uses this NF. The subroutine’s return value is Ψdiv (SG), which is an ordered container for the disjoint paths of the calculated subchains. D. One greedy step The M AP O NE VNF() function’s task is to map the given SG link – SG node pair to the best hosting RG path and node, in addition to saving some other good host candidates of the current leg (enf , nf ) for backtracking. Its return value reports whether the greedy mapping step was successful or not. Possible hosts for an NF must have enough resources, must be able to run the given NF type, must not be too far (measured in delay) from the termination of the end-to-end chain and must be accessible on a path which has enough bandwidth and must not be too far (measured in delay) from the previously used host. 2 p.f irst
3A
and p.last are always common SAP nodes of RG and SG. partition of a set U divides U into disjoint subsets, whose union is U .
51
An objective function value is calculated for every possible host v ∈ V(RG) and substrate path p ∈ P(SG), leading from the previously mapped leg’s hosting node to v (i.e. v = p.last). The objective function value of a potential (enf , nf ) ↔ (p, v) mapping is influenced by three components: i) average link bandwidth utilization on path p; ii) delay used by path p divided by the remaining delay budget; iii) weighted sum of preference values of utilization for every resource type on host v. Preference value of utilization on a host for a resource type can be defined by any real function φr : [0, 1] 7→ [0, 1], which should quantify how much a utilization state is preferred. The bigger the preference value, the less the state is preferred. By default this function is 0 if utilization is less than 0.2, and linear between φr (0.2) = 0 and φr (1.0) = 1.0 for each node resource type. The best host and path pair (p, v), i.e., the one with the lowest objective function value, is chosen for mapping, and a few other good candidates are saved for backtracking, in case of subsequent mapping failure. IV.
E VALUATION
The orchestration algorithm has been evaluated on a real world topology taken from SNDlib4 [5], which has 42 nodes and 157 edges, representing access, aggregation and core network parts, equipped with computation resources. Simple Service Chains with 1 to 8 NFs connected between two SAPs have been generated uniformly with randomized resource requirements with the same distribution. The resource requirement were relatively small compared to the available resources5 and are reproducible based on a given seed for the random generator to achieve a benchmarking-like test sequence. The SC benchmark can be used to measure the performance of embedding by the number of successfully mapped SCs, and this provides a comparable metric to other algorithms. The generated SC sequences have been cumulatively mapped to the network in batches of four (in other words, one Service Graph consists of four SCs), so the orchestration algorithm had to provision the request with monotonically decreasing available resources. Fig. 2 shows the load state of Resource Graph at two different moments of the benchmarking test. The Cumulative Distribution Function (CDF) of all resource types are plotted in both cases. A CDF of a given resource type shows the ratio of network elements which have their resource utilization lower or equal to the value on the horizontal axis. Resources of the computation nodes are CPU, memory, storage and bandwidth, while forwarding nodes have only bandwidth resource (i.e. the CDF of bandwidth has much more steps). The plotted link resource is bandwidth, denoted by link_bw in Fig. 2. Node resource CDFs show that our orchestration algorithm balances the load nicely throughout the network. For instance, the CDF of memory in Fig. 2b says all nodes are utilized between 35 and 45 percent. The CDF of CPU shows that it 4 The dfn-gwin topology was used with additional network parts (6 nodes have been attached to an access network) and computing resources (another 6 nodes have been attached to a data center). 5 Approximately 1000 NFs could be hosted on the whole network, limited by the most scarce resource type.
mem
1.0
bandwidth
storage
cpu
resource utilizations increase monotonically, until the utilization of CPU reaches its maximal capacity.
link_bw
The tests were executed on general personal computers, and the running time of a whole test sequence (which consists of approximately 900 NF mappings onto the extended SNDlib topology) is around 38 seconds, including all the preprocessing and the output generation, and excluding the Floyd-Warshall algorithm. Our orchestration algorithm’s running time scales polynomially with the input size.
CDF
0.8 0.6 0.4 0.2 0.0
0
20
40 60 Resource utilization [%]
80
V.
100
The presented orchestration algorithm is integrated into an all-round prototype implementation of an SDN/NFV-based SFC architecture, called ESCAPE, which is capable of connecting various domains in a technology agnostic manner [6]. ESCAPE provides a possibility for network segment aggregation, and our orchestration algorithm is capable to manage the resources of the global and local views as well.
(a) Less loaded state.
mem
1.0
bandwidth
storage
cpu
link_bw
CDF
0.8 0.6
VI.
0.4 0.2 0.0
0
20
40 60 Resource utilization [%]
80
100
(b) Almost fully loaded state in term of CPU resource.
Figure 2: Cumulative Distribution Function of various resource utilizations . Chart Title 1.2 1 0.8 0.6 0.4 0.2 0
90% 80%
R EFERENCES [1]
Average memory utilization
70%
avg(link_bw)
Average CPU utilization
60%
Average memory utilization
avg(storage)
avg(bandwidth)
50% 40% 30% 20% 10% 0%
5
29
53
77
101
C ONCLUSION
This work presents and analyses a fast and efficient solution for the problem of automatic resource optimization in a virtualization-based and software-controlled network architecture, which makes the presented algorithm a possible candidate to aid the service provisioning decisions of an Orchestrator. The analysed orchestration algorithm uses a preference value based greedy backtrack approach to provide a customizable and scalable solution for Service Graph Embedding on various network types. The presented evaluation results demonstrate the load balancing capability of our solution. Altogether, our Orchestrator logic is ready to be tested and deployed in reallife scenarios.
Average CPU utilization 5 17 29 41 53 65 77 89 101 113 125 137 149 161 173 185 197 209 221 233
Resource utilization of nodes
100%
D ISCUSSION
125
149
173
197
Number of provisioned Service Chains
Figure 3: Minimal, maximal and average utilization of CPU and memory under increasing load.
is the most scarce resource in the network, because it is the rightmost curve in both figures. Fig. 3 depicts the conformation of CPU and memory resources throughout the whole test sequence of SG requests. The horizontal axis shows the number of mapped SCs, and the vertical axis shows the minimal, average and maximal resource utilization at the shared RG. According to the expectations, the
52
S. D. Dan Pitt Rick Bauer. (2016). Open networking foundation, [Online]. Available: https : / / www . opennetworking.org/ (visited on 05/20/2016). [2] A. Fischer, M. B. J. Botero, H. D. Meer, and X. Hesselbach, “Virtual network embedding: A survey”, IEEE Communications Surveys Tutorials, vol. 15, no. 4, 2013. [3] M. Chowdhury, M. R. Rahman, and R. Boutaba, “Vineyard: Virtual network embedding algorithms with coordinated node and link mapping”, IEEE/ACM Trans. Netw., [4] C. Fuerst, S. Schmid, and A. Feldmann, “Virtual network embedding with collocation: Benefits and limitations of pre-clustering”, in IEEE 2nd International Conference on Cloud Networking, CloudNet 2013, San Francisco, CA, USA, November 11-13, 2013. [5] S. Orlowski, M. Pióro, A. Tomaszewski, and R. Wessäly, “SNDlib 1.0–Survivable Network Design Library”, in Proceedings of the 3rd International Network Optimization Conference (INOC 2007), Spa, Belgium, 2007. [6] B. Sonkoly, R. Szabó, D. Jocha, J. Czentye, M. Kind, and F.-J. Westphal, “Unifying cloud and carrier network resources: An architectural view”, in Proc. IEEE Global Telecommunications Conference (GLOBECOM), 2015.
Integrating an Electric Vehicle Charging System with the Arrowhead Framework Balint Peceli∗ , Pal Varga† and Zsolt Szepessy∗ ∗ evopro
Innovation Ltd. Email:
[email protected],
[email protected] † Department
of Telecommunications and Media Informatics Budapest University of Technology and Economics Email:
[email protected]
Abstract—The electric vehicle (EV) charging infrastructure is evolving in a strained way to be able to feed Europe’s growing EV fleet. Protocols are present for message exchanging between electro mobility partners, but the domain still lacks a framework that supports the dynamic and safe reconfiguration of the network of members’ ICT systems. This paper presents the Arrowhead framework, a service oriented platform for the Internet of Things (IoT), as a possible solution. Two use cases are discussed to enlighten the opportunities of Arrowhead. This supports the present network of charge points by dynamic service discovery and a future scenario of EV specific charge management by cloudbased battery and charge point virtualization. An embedded software gateway which enables the integration of an electric vehicle charging station with the framework is also proposed.
I.
I NTRODUCTION
The Arrowhead Consortium works with the support of the European Union’s H2020 program to develop a technical framework for the Industrial Internet of Things [1]. The Arrowhead framework is based on the concepts of System of Systems and Service Oriented Architecture [2] to enable collaborative automation by networked embedded devices. It is a platform motivated by industrial use cases, and that implies unique solutions in system and service design – compared to other known IoT frameworks [3]. The project has defined several pilot domains to demonstrate the usage and benefits of the Arrowhead framework. One of them is electro mobility and particularly the electric transportation charging market. According to the proposed model in [4], the primary actors of the EV charging market are the following: 1) 2) 3)
User: a human charging an electric vehicle, Electric Vehicle Service Provider (EVSP): a company that contracts EV users offering them services related to EV charging, Charge Point (CP) or Electric Vehicle Supply Equipment (EVSE) Operator: an organization, most often a municipality that owns and operates charging stations.
The EVSP holds a list of contracted users and makes this list available for the EVSE operator. Through his charge stations, the operator charges the EVs of the authorized users, and then sends transaction related information back to the EVSP. Based on the charging record, the EVSP issues the
53
invoice for the user and pays the operator the cost of the charging. Usually there is a fourth party on the charging market: the Navigation Service Provider (NSP). It offers live charge point information (status, availability, technical details, etc.) to help users find the most suitable EVSE in the remaining range. EVSP may also give navigation service, but NSP is still a relevant role as more EVSPs and even independent charge points may exist. The charging market is expected to become a dynamically changeable domain with mobile customers. EVSP, EVSE operator and NSP are the most important roles, but other ancillary service providers will enter the market soon. Managing authorization, charge point and charging transaction related information requires the cooperation of the market members’ ICT systems. The Arrowhead framework recommends solutions to compose reliable and robust system of systems and to manage interoperability as new members enter the market, consumers switch service providers, etc. However, as both the EV charging market and the Internet of Things are in early stages of maturity, before integrating an EVSE with the proposed framework, a deep investigation of possible use cases is needed. The main issues of this paper are the following: 1) 2)
How could the Arrowhead framework support the electric transportation charging market? How can an electric vehicle charging station be integrated with the Arrowhead framework?
In order to find the answers to these questions, Section II presents the main concept and functionality of the Arrowhead framework. Two use cases in Section III attempt to make clear its opportunities within the domain. Section IV proposes an embedded software adapter and application services for the integration of legacy or new charging stations. II.
T HE A RROWHEAD F RAMEWORK
The natural environment of Arrowhead is a factory, where a limited number of interconnected sensor, controller and actuator nodes work together on effectively assembling a product. This motivates the Local Cloud, a unique approach in the field of IoT platforms [3]: the group of devices of a specific factory or company belong to a distinct cloud having
Fig. 1.
Mandatory systems and services within the Arrowhead Local Cloud
common orchestration and security resources. Scalability is provided through global service discovery and inter-cloud communication, that is, member systems of different local clouds can collaborate, if intra-cloud servicing is not optimal or not even possible [5]. The Local Cloud is defined as a set of central and application entities as illustrated in Fig. 1 [6]. The mandatory core functions are provided by the Service Registry, the Orchestrator (Management) and the Authorization systems. The Service Registry stores the backend information of all the registered services and provider systems, the Orchestrator manages the communication of application systems and supports the reconfiguration of the cloud, and the Authorization system enables that only properly authorized systems can provide and/or consume services within the cloud. Application systems has to implement – either natively or by the use of a legacy adapter – an interface towards the core entities in order to be able to produce and/or consume services, i.e. to be Arrowhead compliant. III.
U SE CASES
A. Charge Point Management EVSE operators are free to manage different types of charge points from different vendors. Their charge point management system (CPMS) collects user authentication and charging transaction related information from the charge stations. It is desirable to standardize the messages between CPMS and EVSEs in order to provide interoperability. Open Charge Point Protocol is an application layer protocol for this purpose and is widely used in Europe and Asia [7]. Charge points are statically routed to the CPMS and that means no problem if the operator wants to run only a static set of them. However, a dynamic network is necessary if independent EVSEs are spread. They work for more then one operator in different time slots of the day, and therefore need to change OCPP connections occasionally. Another similar scenario is when the operator runs multiple backup servers on different locations, and EVSEs are dynamically routed to them according to the optimal resource utilization. Arrowhead proposes dynamic service discovery and orchestration support to help charge points to find CPMS running OCPP servers (see Fig. 2). The operator registers the CPMS and its OCPP service into the Arrowhead local cloud and sets the authorization rights. After that, the charge points belonging
54
Fig. 2.
Dynamic service discovery in the Arrowhead framework
to the same local cloud are able to discover and even consume the service on their own (in which case they have to be authorized). This method reduces the offline operation time of CPs as they are able to find equivalent CPMs running in the cloud (or even in another cloud) if the original servicing ceases. It is important not to reject or override but to aid OCPP and other well functioning protocols. Arrowhead does not ruin the unified way of communication but create lightweight, looselycoupled and trusted connections between communication parties. B. Battery Specific Charging The Arrowhead framework enables promising future use cases in the electro mobility domain. One of them is the individualized way of EV charging which conforms to the needs of the specific battery pack under charging. EVs continue to suffer the uncertainty of their batteries. The optimal charging profile depends on many parameters such as level of charge, age, temperature, humidity, etc. EV manufacturers or battery suppliers could offer the charge manager service to prevent battery health and to extend life cycle. Lee at al. [8] propose “Virtual Battery”, a cyber-physical model of EV battery package to simulate and predict behavior under various conditions. This model makes possible the calculation of the optimal charging profile for every transaction of every distinct electric vehicle. Similarly, every EVSE may have a virtual twin in the cloud. Virtual EVSEs could simulate charging processes, and based on the results, the charge manager of the EV manufacturer (or battery supplier) would choose the best CP being capable to fulfill the desire of the electric vehicle. After arriving at the charge station, the charge manager would take the control over the charger to orchestrate the optimal charging process. An Arrowhead-compliant charging station is able to act as a gateway between the EV, the Virtual Battery and the Charge Manager, and to perform the prescribed charging profile (see Fig. 3). Authentication and authorization is crucial to prevent batteries from random and harmful charging processes and therefore EVs should not trust CPs, but only the certificated core systems and the charge manager system. The built-in authorization functionality in the Arrowhead framework targets just these issues.
Fig. 3.
Fig. 4.
Battery specific charging with Arrowhead
IV.
I NTEGRATION
A. Arrowhead adapter The main purpose of an Arrowhead framework adapter is to manage interaction with the core systems on behalf of a legacy system. Supplemented with an adapter, the application system has to be able to register its own services, to discover other active services, and to get orchestration and authorization support from the Arrowhead local cloud. The adapter for a charge point is expected to support both service production and consumption, as an EVSE should communicate in both direction, e.g. it consumes the service of the EVSE operator’s management system and produces another service containing live power consumption information for the battery supplier. Current implementation of Arrowhead Generation 3 framework provides RESTful interface to the core systems and defines the communication sequences between them and the application systems. In order to register a service, the provider system has to send a Service Registry Entry message to the Service Registry’s REST interface. The payload consists of the backend data of the provider system, the URI on which the provided service is available, optional metadata information and a Transaction Signature Key, which is required by the Domain Name Server. (Deregistration is similar to registration only the applied HTTP method varies.) The consumer sends a Service Request Form to the Orchestrator if it is looking for providers of a specific service. The form contains data about the requester system and the requested service. The requester is allowed to prescribe several options to the orchestration process as well as preferred providers. In response, the Orchestrator gives back the list of the matching providers, their backend data and the authorization token which will be known for the provider system. The consumer is free to choose the provider that best suits its needs. The application servicing is not expected to be Arrowhead-specific, however, new services can be defined as well [6]. Fig. 4 illustrates the registration and orchestration process.
Arrowhead orchestration process
integration of an EVSE is provided through the implementation of OCPP (as before), however, considering it as a service and being able to discover and connect to its provider dynamically in run time. From the point of view of many stakeholders, an electric vehicle charge station is nothing more than a simple connection point to the electrical power grid. Users stop by, take energy and leave. That is why for primary actors (EVSP, EVSE operator and user) but for other parties as well (EV Manufacturer, Battery Supplier, Distribution System Operator) the most important information regarding a charging transaction is the amount and timing profile of energy consumption. This motivates the “Energy Metering” application service provided by the Arrowhead-compliant charge stations. OCPP gives data about power consumption, but the protocol adds too much overhead to the communication for stakeholders that are only interested in that particular information. The energy metering service is useful for EV manufacturers running a Charge Manager system in the cloud to validate pre-simulated charging processes and improve battery and charge point models. Similarly, a DSO could use the service to validate consumption forecast and provide smart charging opportunities [10]. C. Implementation
B. EVSE application services
A charging station consists of power electronics, a charge controller board to guide the power transmission process from grid to EV and a station controller board to manage high-level tasks, e.g. user interaction, IP communication, consumption measurement, etc. A station controller board for an EVSE has a powerful architecture, but still it is an embedded platform with an embedded operation system. The proposed Arrowhead adapter is therefore implemented in Qt/C++, in embedded Linux environment. By providing a middle layer between the OS and the application, Qt offers easy development, yet powerful and compact user code [9]. However, it does not take away the freedom of C++ in memory management or timing design.
In the present network of charge points and management system, the end points communicate most often by the use of the OCPP protocol (as described above). Leading this method towards the Arrowhead approach, OCPP becomes an application service, which is provided by the management system and consumed by the charge points. In that manner, the
The Arrowhead adapter consists of a main class called ArrowheadClient, which uses the ArrowheadSystem and ArrowheadService classes. ArrowheadSystem describes an application system with its name, IP address, port number, group identifier and assigns authentication information to it, whilst ArrowheadService contains similar data for application
55
Fig. 5.
Arrowhead module in the EVSE’s software system
Fig. 6.
services, such as name, group, list of interfaces and possible additional metadata. The implementation makes use of Qt’s embedded network management and JSON handling tools to send HTTP messages to the core systems of Arrowhead over 3G network. Fig. 5 illustrates how the Arrowhead module connects to the OCPP and Energy Metering modules of an EVSE’s legacy software system to transform them into application services for the Arrowhead framework. D. Verification The proposed Arrowhead adapter was implemented and integrated into evopro’s rapid charger [11] and a web GUI substituting the charge point management system (see Fig. 6). Both endpoints were taken into the Arrowhead local cloud running on the servers of Budapest University of Technology and Economics (BME). The web GUI registered an application service enabling charge points to report basic information related to charging transactions (user id, meter data and timestamp). The rapid charger was able to discover and consume this service in run time, which verified the operation of the proposed software adapter module.
IoT world. The electro mobility domain needs professional devices and applications that improve both the user’s and the operator’s experience. Arrowhead’s only way to convince the market is to develop products, first of all Arrowhead-compliant charging stations. ACKNOWLEDGMENT This work is supported by the EU ARTEMIS JU funding, within project ARTEMIS/0001/2012, JU grant nr. 332987 (ARROWHEAD). The authors would like to thank the support of the Hungarian team from Budapest University of Technology and Economics, AITIA International Inc., and from evopro Innovation Ltd. R EFERENCES [1] [2] [3]
[4]
V.
C ONCLUSION
[5]
The Arrowhead framework is able to support the electro mobility market by providing a flexible and reliable local cloud based infrastructure. The service oriented architecture with dynamic service discovery improves the usability of existing protocols. Further on, the framework enables promising future use case scenarios e.g. battery specific charging. Integration of legacy applications such as charge points and charge point management systems requires a lightweight, easy to use software component managing the communication with the Arrowhead core systems. The energy metering application service provided by the electric vehicle charge stations plays a primary important role in deepening the integration of stakeholder’s ICT systems and thus, enabling a higher quality of charging services. However, the Arrowhead framework is not a mature platform yet. Future work must extend functionality, strengthen authentication and authorization methods and prove robustness and usability through various and complex use cases to make Arrowhead a widely accepted and supported framework of the
56
Rapid charging station connected to the Arrowhead local cloud
[6]
[7]
[8] [9] [10]
[11]
Arrowhead Consortium, Arrowhead Project Home Page, [Online]. Available: http://www.arrowhead.eu/. [Accessed 14th April 2016]. Thomas Erl, SOA Principles of Service Design (The Prentice Hall Service- Oriented Computing Series from Thomas Erl), Upper Saddle River, NJ, USA: Prentice Hall PTR, 2007. Hasan Derhamy and Jens Eliasson and Jerker Delsing and Peter Priller, A Survey of Commercial Frameworks for the Internet of Things, IEEE 20th Conference on Emerging Technologies & Factory Automation (ETFA) 2015. D. Geldtmeijer, K. Hommes and A. Postma, Charging electric vehicles in a liberalized electricity market in Cired Conference, 2011. P. Varga and Cs. Heged˝us, Service Interactions through Gateways for Inter-Cloud Collaboration within the Arrowhead Framework in Conference on Wireless Communications, Vehicular Technology, Information Theory, Aerospace & Electronic Systems, Hyderabad, 2015. Fredrik Blomstedt and Luis Lino Ferreira and Markus Klisics and Jens Eliasson, The Arrowhead Approach for SOA Application Development and Documentation, The 40nd Annual Conference of IEEE Industrial Electronics Society (IECON), 2014. Open Charge Alliance, Open Charge Point Protocol v1.6, 8 October 2015. [Online]. Available: http://www.openchargealliance.org/protocols/ocpp/ocpp-16/. [Accessed 14th April 2016]. J. Lee, B. Bagheri and H.-A. Kao, Recent Advances and Trends of CyberPhysical Systems and Big Data Analytics in Industrial Informatics in Conference on Industrial Informatics (INDIN), 2014. The Qt Company, Qt Wiki, 28 March 2016. [Online]. Available: http://wiki.qt.io/Main. [Accessed 14th April 2016]. C. Montes Portela, P. Klapwijk, L. Verheijen, H. de Boer, H. Slootweg, M. van Eekelen, OSCP - An open protocol for smart charging of electric vehicles, 23rd International Conference on Electricity Distribution, CIRED, 2015. evopro group, evopro Home Page, [Online]. Available: http://www.evopro.hu/eng. [Accessed 7th May 2016].
Distributed Network Emulation over Cloud Infrastructure Tam´as L´evai and Felici´an N´emeth Department of Telecommunications and Media Informatics Budapest University of Technology and Economics Email: {levait,nemethf}@tmit.bme.hu Abstract—Many current research and development projects require large-scale realistic computer network testbeds. The access to these testbeds is limited, and simulation cannot model real-life scenarios, therefore these networks have to be emulated. The emulation of realistic large networks requires distributed systems. Currently, emulators run on clusters; however, physical clusters are not easily accessible because setting up and operating them require significant investment and management skills. In contrast, virtual clusters in cloud are easily accessible, and have small operation and maintenance costs. But, can virtual clusters provide at least the same reliability as physical clusters do? How effective can cloud-based emulation be in terms of time and cost? The paper focuses on these questions by presenting prior art, identifying the challenges of cost-effective and reliable network emulation in cloud, and presenting feasibility study with measurements and a tool that migrates an existing network emulator to the cloud.
I.
I NTRODUCTION
There is a high demand for carrying out experiments and measurements on certain large-scale computer networks in research and in industry (e.g., testing new routing protocols, design topologies). It is rarely the case that large-scale computer networks are available for these purposes. Instead, the test networks are emulated or simulated. There is a significant difference between network simulation and emulation; namely, a simulator [8] runs only an abstract model of the network elements as oppose to the emulator which imitates the network components. As a result, simulation is not capable to reliably model real-life scenarios; precise emulation is required for this purpose. Precise emulation of large networks with all of their components has such a big resource requirement that it cannot be satisfied by a single computer, therefore distributed systems, such as clusters, are required for this task. The infrastructure’s quality limits the performance of the emulation. For example, a link with 100 Mb/s throughput cannot forward 1 Gb/s emulated traffic in real-time. There are two types of clusters: physical and virtual. Physical clusters consist of multiple interconnected computers. The computers can range from SoC boards to server equipments. The interconnection is usually realised on Ethernet over cable or optic. The performance of a physical clusters depends highly on their dedicated components. The build and the operation of a cluster requires significant amount of money, time and skill. Moreover, the maintenance costs and expansion costs of physical clusters are high. Virtual clusters are realised in cloud. The fundamental idea behind cloud computing is to decouple the running software
57
from the underlying hardware. To achieve that the cloud computing environment consist of managed virtual machines and virtual links atop a computer grid. As oppose to the dedicated resources of clusters, clouds provide on-demand resources. Cloud providers sell these resources with flexible pricing that is proportional to the usage. Due to its flexibility in usage and in pricing, cloud had a significant success in recent past, therefore this paper examines and proposes the foundations of translating distributed network emulation from physical clusters to cloud-based virtual clusters in a costeffective and reliable manner. The three challenges of the work is to be cost-efficient and to overcome the quality issues of the platform and the distributed network emulation. Following paragraphs detail these challenges. First of all, there are key differences in the infrastructure: physical clusters provide dedicated, high quality and highly controllable resources. In contrast, cloud-based clusters access virtualised resources with fluctuating performance [11]. Due to the on-demand pricing model of cloud resources, it is essential to minimise resource usage to achieve high cost-efficiency. Beside the characteristics of the infrastructure, the current limitations of distributed network emulators have to be examined to successfully realise cloud-based emulation. It is still an open problem to optimally embed the emulated network into a cluster. If the network elements are not placed properly, bottlenecks might occur and the reliability of the emulation can be harmed – which is against the goal of reliable emulation. The aim of this paper is to utilise existing distributed network emulators in cloud. This work also involved performance measurements of the cloud infrastructure, resource-allocation algorithm design, and proof of concept development. The structure of the paper is the following: Section II presents existing distributed emulators and cloud infrastructure. Section III identifies the design challenges of network emulators in clouds. Section IV presents feasibility study of cloud-based emulation, Section V proposes a cost-efficient and reliable network emulator that suits for the circumstances of cloud infrastructure. Section VI concludes. II.
P RIOR A RT
A. Cloud Resources Cloud resources are provided by the cloud infrastructure. On physical level the cloud infrastructure is a third-party operated data centre with large number of servers and highspeed interconnections. All of the providers services are based
on the physical layer. For example, if the infrastructure is the service (IaaS), the end-user rents virtual resources realised (e.g., virtual machines and virtual networks). Each user’s assets are mapped to the physical servers at the providers’ data centre, there is no separation on physical level. Also, the provider gives a management interface to manage assets with no hassle: to instantiate virtual machines and to interconnect them with own virtual networks. This way it is easy to create a cluster consisting of virtual machines and virtual links atop a shared physical infrastructure. By default, the provider does not guarantee the locality of our resources: an asset might run on a single server or on different servers in the same data centre. It is possible, however it is not practical for network emulation, to use multiple data centres – providers usually have multiple data centres to have better geographical coverage. As a consequence, the same asset might have slightly different performance at each allocation. In the financial model of cloud the user pays directly for the used resources; there are no amortisation or upgrade costs. Moreover, the operation of dedicated servers is more cumbersome and expensive than renting virtual resources. In addition, there are different pricing models to cover various needs: the user can reserve resources on-demand or in advance in Amazon EC2 [5]. Google Preemptive VMs [6] provide an option in which the user can buy resources at low-cost, but there is no guarantee for their life-time. In conclusion, cloud resources are easily accessible and relatively cheap, but does not necessarily guarantee constant performance: as [11] states, CPU capacity, throughput and delay fluctuates in Amazon EC2. Solutions measuring cloud infrastructure in large-scale were presented in [14] and [15]. B. Distributed Network Emulators The key aspect of distributed emulation is to run the emulation on an interconnected set of computers. On the combined set of resources, large-scale networks that are not able to run on a single computer can be emulated. The important resources in network emulation are the processor units and the operational memory. Each node in the emulated network requires some amount of memory, therefore memory limits the size of the network. CPU is more important than memory: not only nodes use the CPU, packet forwarding also requires computation. Accordingly, CPU limits link and traffic characteristics (e.g., throughput, delay, jitter). In case of distributed network emulation physical links that interconnect computers determine the performance too. The amount of available resources are important for embedding the network into the physical infrastructure, because the performance of the emulation relies on proper embedding – proper utilisation of resources. This phase of emulation is still an open research; various heuristic approaches are utilised by existing network emulators. Mininet Cluster Edition [2] uses either random, round robin, or equal sized bins (relaxed bin packaging problem) algorithms to map virtual networks into the physical infrastructure. The Distributed OpenFlow Testbed [4] utilises integer linear programming and heuristics to effectively map networks. ModelNet [7] uses round-robin by default, but it is capable to use graph partitioning [12]. MaxiNet [3] relies on external graph partitioning library (METIS).
58
All of these algorithms try to distribute the load evenly between computers (implying a homogeneous cluster) and keep the number of emulated links over physical links low. The nature of virtual links must be also examined in order to understand the mechanics of distributed network emulation in detail. The emulators can use various technologies for virtual networking: virtual interfaces, virtual links and virtual switches. The end points of virtual links are virtual interfaces or virtual switches. Intra-computer virtual links are usually provided by the operating system. Virtual links over physical links rely on tunnelling protocols. MaxiNet and DOT use Generic Routing Encapsulation, Mininet Cluster Edition uses Secure Shell tunnelling. The characterisation of links is done by the Linux kernel’s traffic control. This feature is supported by MaxiNet and DOT. Virtual switches act as a software defined network switch: their function can be programmed. Commonly used virtual switch software are among others Linux bridge, OpenFlow software switch and Open vSwitch [9]. Technologies exist to overcome limits of physical links. One of these solutions is time dilation [10], but it cannot be used if real-time emulation is required, because time dilation slows down the system’s time to iron out the overload. Based on these technologies emulators provide various feature sets. Mininet Cluster Edition, the official cluster version of Mininet [1], [13], is still a proof-of-concept: it does not provide reliable emulation. In contrast, DOT provides advanced features like configurable link characteristics. Currently, MaxiNet seems a good solution to use for distributed network emulation. It is compatible with MiniNet, and link characteristics (bandwidth and latency) can be configured on each link. We believe that there is no distributed network emulator targeting clouds, however, non-distributed network emulation in cloud was successfully utilised in [13]. III.
D ESIGN C HALLENGES
A. Reliable Emulation A key aspect of this work is to establish a reliable emulation in which repeated measurements provide realistic and almost the same results on each run. Reliability should be one of the main design consideration for any cloud-based emulator, however, it is still an open problem even for cluster based emulators. However, they could use the dedicated resources of clusters. Hence, it is an open question how to provide reliable emulation on a platform that does not necessarily provide resource guarantees. Reliability is threatened if a bottleneck is reached. The main bottleneck of distributed network emulation is the capacity of physical links and the CPU. B. Cost-efficiency In cloud we pay directly for the used resources, therefore it is practical to reserve only the just enough set of resources that is required to reliably emulate. It is not trivial to determine this minimal set of required resources: beside a priori knowledge, a posteriori knowledge is also required.
Common cluster resource allocators try to span the virtual network over the whole physical infrastructure. As a result, emulators on clusters with three nodes will use all the three nodes even when networks require just one node. This way we utilise unnecessary and probably limiting physical links. Not only the possible performance degradation is the problem, unnecessary resources generate unnecessary costs. In cloud we pay directly for the used resources, therefore it is crucial to keep link traffic and number of running virtual machines low. On the other hand, if a network that requires three hosts will be emulated on one host only, the reliability of the emulation fails due to the insufficient amount of available resources. IV.
emulated link over the interconnecting link. With this setup we were capable to measure emulated intra-node links (links inside a VM) and emulated extra-node links (link between VMs). During the run, one of the virtual machines was restarted three times to cause its reallocation. Traffic was generated between each host-pair in the emulated network by iperf and ping.
F EASIBILITY S TUDY WITH M EASUREMENTS
h1
h2
h3
h4
A. Emulation on Cloud Infrastructure In order to examine the characteristics of the pseudophysical links in cloud, we carried out performance measurements focusing on throughput and round trip time between two Amazon EC2 free-tier t2.micro virtual machines in one virtual LAN. To examine the effect of other tenants load, the measurements ran over two days. Each measurement was interrupted three times to see the effect of different allocations. At each interruption one virtual machine was restarted to cause its reallocation. Throughput was measured with periodic iperf generated TCP traffic. The results showed that the link has 1010 Mbits/sec maximum throughput which was saturated in 76% of measurements providing a 995.2 Mbits/sec average throughput. The reallocation of virtual machines had no significant effect.
Fig. 2.
Arrangement to Determine Network Emulation Performance
Figure 3 shows the results of RTT measurement. The RTT of different types of links can be clearly seen. Pinging localhost (h1-h1) constantly provided infinitesimal results, intra-node link (h1-h2, h3-h4) RTTs were 3-4 ms. The extra-node links (h1-h3, h1-h4, h2-h3, h2-h4) had higher average results (67 ms) with significant deviation. By combining these results and the results of the infrastructural measurements, the RTT overhead of interconnecting links are visible.
Round trip time was measured by periodic runs of ping -c 5. The results of this measurement can be seen in Figure 1. The average RTT was 0.74 ms, however, there were big spikes in two of three allocations. The averaged results presents a good quality infrastructure. On the other hand, the high deviation validates the fluctuating performance of cloud resources and requires further actions to handle. Fig. 3.
Results of RTT Measurement in the Emulated Network
Figure 4 shows throughput measurement’s expressive results in which the different types of links are nicely clustered. The order of magnitudes are the following: localhost (h1-h1) throughput is 10 Gb/s, intra-node traffic (h1-h2, h3-h4) is 1 Gb/s, extra-node throughput is 100 Mb/s. Moreover, the extranode throughput was strongly affected by the allocation.
Fig. 1.
Results of RTT Measurement in Amazon EC2
The performance of cluster-based emulation on this infrastructure was measured with a virtual simple tree topology containing 4 hosts (h1, h2, h3, h4) emulated with MaxiNet on two interconnected Amazon EC2 free-tier t2.micro virtual machines. As Figure 2 shows, this arrangement has just one
59
These measurements prompted that the cloud infrastructure can provide anomalies such as big spikes in RTT that can threaten the reliability of measurements. Therefore, reliability cannot be guaranteed, only the faults of reliable emulation can be detected. To provide reliable emulation on this platform, monitoring its resources is required. The effect of extra-node links is also observable in these measurements: they limit throughput and RTT more than intra-node virtual switching does; throughput of a path having multiple inter-node links is the smallest throughput, and RTT is the sum of link RTTs. The limitation of links can be mitigated by using a network
and elaborated the design challenges of cloud-based network emulation; namely, to overcome the lack of dedicated resources by monitoring, and to provide cost-efficiency by minimising resource usage. This work also presented a network emulation feasibility study with measurements, and a proof of concept tool that migrates an existing network emulator to the cloud. B. Future Work One possible future work is to add dynamic scale-in and scale-out functions to the cloud-based emulator to further minimise costs. Fig. 4.
Results of Throughput Measurement in the Emulated Network.
partitioning algorithms that keeps large-bandwidth links inside the virtual machine. V.
ACKNOWLEDGMENT We would like to express our great appreciation to G´abor R´etv´ari (BME-TMIT) for his valuable discussion.
A C LOUD - BASED E MULATOR P ROOF OF C ONCEPT
A. Cost-efficient Resource Allocation Cloud costs are proportional to resource usage. In order to minimise costs, resource usage must be minimised. For this purpose we propose a cost-efficient resource allocation algorithm with try-error approach: the initial resource set is appraised, if it is not enough, the resource set gets increased and the emulation starts again. Changing the resource set is simple due to the flexible nature of clouds. To speed up this process, results of existing runs of emulations can be collected and used. B. Proof of Concept To prove viability of cloud-based emulation, real-life experiences are required. Therefore, we ported an existing network emulator (MaxiNet) to the cloud (Amazon EC2). We also hope, this easy-to-use tool will take others into cloud-based distributed network emulation. With this tool, users can easily reproduce measurements presented in this article, or run any MiniNet or MaxiNet experiments in cloud. The provision of the virtual-cluster is also automatised. As an example, let us suppose the user wants to run a measurement. In this case, she types the following command: maxinet-ec2 test.py --vmf t2.micro --vmn 2. As consequence, the tool connects to Amazon EC2, authenticates the user with its pre-set access key, creates two t2.micro instances with MaxiNet in the same subnet, runs the measurement, provides monitoring statistics, analyse them, and if it currently detects resource over-utilisation in multiple successive measurements, questions the reliability of the measurement. The user can choose whether she repeats the measurement and extends the virtual-cluster, or not. VI.
Another future work is to appraise the cost of the emulation at a given cloud provider before emulation, and based on this information do the resource allocation at that provider or choose a different one automatically.
R EFERENCES [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
[13]
C ONCLUSION AND F UTURE W ORK
A. Conclusion
[14]
Emulation of large-scale networks require distributed systems such as clusters. Physical clusters are expensive and hardly accessible. In contrast, virtual clusters realised in cloud have low, usage-based costs and easy access, but cloud does not guarantee constant performance. This paper identified
[15]
60
B. Lantz, et. al, A network in a laptop: rapid prototyping for softwaredefined networks. Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks, ACM, 2010. p 1–9. B. Lantz, et. al, A Mininet-based Virtual Testbed for Distributed SDN Development, Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, ACM, 2015. P. Wette, et. al, Maxinet: Distributed emulation of software-defined networks, Networking Conference, 2014 IFIP, IEEE, 2014. p. 1–9. A. Roy, et. al, Design and management of DOT: A distributed OpenFlow testbed, Network Operations and Management Symposium (NOMS), 2014 IEEE, IEEE, 2014. p. 1–9. Amazon EC2 Pricing https://aws.amazon.com/ec2/pricing/ Google Preemptive VMs https://cloud.google.com/compute/docs/ instances/preemptible A. Vahdat, et. al, Scalability and accuracy in a large-scale network emulator, ACM SIGOPS Operating Systems Review, 36, SI, 2002. p. 271-284. S. LIM, et. al, MDCSim: A multi-tier data center simulation, platform, Cluster Computing and Workshops, 2009. CLUSTER’09. IEEE International Conference, IEEE, 2009. p. 1–9. B. Pfaff, et. al, Extending Networking into the Virtualization Layer, Hotnets, 2009 D. Gupta, et. al, To infinity and beyond: time warped network emulation, Proceedings of the twentieth ACM symposium on Operating systems principles, ACM, 2005. p. 1–2. G. WANG, et. al, The impact of virtualization on network performance of amazon ec2 data center., INFOCOM, 2010 Proceedings IEEE, IEEE, 2010. p. 1–9. K. Yocum, et. al, Toward scaling network emulation using topology partitioning, Modeling, Analysis and Simulation of Computer Telecommunications Systems, 2003. MASCOTS 2003. 11th IEEE/ACM International Symposium, IEEE, 2003. p. 242–245. N. Handigol, et. al, Reproducable Network Experiments Using Container Based Emulation, Proceedings of the 8th international conference on Emerging networking experiments and technologies. ACM, 2012. p. 253–264. C. Guo, et. al, Pingmesh: A Large-Scale System for Data Center Network Latency Measurement and Analysis, Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. ACM, 2015. p. 139–152 S. Kandula, et. al, The nature of data center traffic: measurements & analysis, Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference. ACM, 2009, p. 202–208
Use Cases for LTE Core Network Mass Testing Gabor Soos
Pal Varga
Dept. of Telecommunications and Media Informatics Budapest University of Technology and Economics 2 Magyar Tudosok krt., Budapest, Hungary, H-1117 Email:
[email protected]
Dept. of Telecommunications and Media Informatics Budapest University of Technology and Economics 2 Magyar Tudosok krt., Budapest, Hungary, H-1117 Email:
[email protected]
Abstract— Mass testing is an essential part of service acceptance procedures. The smooth operation of 4G services requires a scalable, properly working LTE core network, among others. This creates a necessity of functional, integration, and mass testing of the LTE core. This latter issue is troublesome, because it requires proper handling of all network wide processes - for all equipment of the validation setup, while their utilization is pushed to its limits. In this paper we describe a mass-testing environment, where the Network Under Test (NUT) is the Evolved Packet Core, and the test equipment simulates hundreds of thousands of users attach to it, move between its routing areas (or even arriving from 2G or 3G segments), and generate traffic before detaching. In order to unveil the limitations of the NUT, use cases need to be defined and carried out. The verification is encumbered by authentication and encryption procedures, despite the fact that the endpoints are simulated; so as their keys.
I.
virtualized EPC vendors keep some functions of the systems in standby mode in case of medium load, to save system utilization capacity. This can be a bad approach in case of system failure or transient load. This paper briefly introduces the main elements of the LTE Core Network as NUT (Network Under Test), with its main elements, and the connecting interfaces to the LTE Load generator. Furthermore, we describe the actual connection of one evolved NodeB (eNB), with the following mass-load use cases. We show one possible scenario for a simple failure, and its effect to the core system. Later we focus on connecting a subscriber, and shortly describing the key-generation mechanism used, with mass load of users and their traffic.
II.
INTRODUCTION AND MOTIVATION
ARCHITECTURAL SETUP FOR LTE EPC MASS TESTING
Knowing the architectural dependencies and the exact protocols in depth are essential, because the parameters can cause scalability problems in case of mass testing or live system introduction.
The LTE Evolved packet Core (EPC) is based on continuously evolving 3GPP standards. It is always under development, due to the emerging technical and business requirements. The modifications of the systems are mostly software innovations. These are in most cases merely improvements of earlier existing implementations, where some fixed values are made configurable, or the new code is changing the behaviour algorithms inside the EPC. The parameters in question sometimes get new values, which in case of low load do not lead to different system behaviour, but in case of high load, serious effects can happen. In case of new software or network element, the mass load test is always compulsory to examine the whole system end-to-end, searching for transients and comparing the results with earlier measurements.
Fig. 1 represents the core LTE networks elements and the defined interfaces in between [1]. In our situation SGW-MMEPGW (Serving Gateway, Mobility Management Entity, Packet Data Network Gateway) are part of the NUT, and interfaces S1-MME [2], S1-U [3], S6a [4] and SGi [5] are interfaces (see Fig. 2) under test [6]. S5, S10 and S11 are internal interfaces in the NUT, using the same GTP (GPRS Tunneling Protocol) [7] protocol, and are not under direct test in this scenario.
The EPC devices are based on specialized HW architecture, which means that part of the SW also bonded to HW features. This is planned – sooner or later – to be changed to virtualHW-based solution. The HW dependencies, like interface and memory handling, or even HW bonded FPGA based controlling has to be minimized and separately handled. The advantage of the virtualized EPC is that it can run on almost all kinds of HW platform, hence the initial capex can be minimized. The disadvantage is that the EPC software will not have many contacts with the physical layer. Testing with low number of users and with low traffic can result in very different outcome when compared to cases of heavy mass load. The demand for mass-load test cases will rise. Lot of the
Figure 1. Evolved Packet Core and main interfaces
61
affected in this node. This is the edge point of the EPC to the external IP network. In the test-setup the PGW connects to the SGW via internal S5 interface, which is out of the scope of the testing. The SGi interface is connected to the Mass-Test environment over IP.
D. HSS (Home Subscriber Server) HSS is the user database in the LTE Network. It contains all of the user-related rules and attributes. In case of User attach, the MME queries the HSS for user authentication, identification rules and permissions. HSS connects to the HLR/AuC for authentication keys and also registers the subscribers’ location on the 4G network. In our situation HSS is part of the Mass-Test environment, where the connecting interface is S6a, IP and SCTP based Diameter protocol.
III.
BACKGROUND OF MASS TESTING USE CASES, TESTING SCENARIOS
Our goal is to grant reliable, error-free, fast data transfer and call establishment in a system – irrespectively of the system size or the load. To achieve it, we test the system step-by-step from the smallest scale up to the full loaded system [12]. There are several vendors on the market (e.g. Aitia and Ixia), who offer wide range possibilities of mass testing solutions [13]. Firstly we analyze the base infrastructure, the connection between the eNB and MME, and later with few simulated users we analyze a connection of a user from eNB to the PGW. Finally we test the EPC as NUT end-to-end, with thousands of simulated subscribers.
Figure 2. NUT and Traffic Generator.
A. MME MME is the main signaling node in the EPC, the UE’s can connect to the network through the eNB. It also handles SGW and other MMEs NAS (Non-access Stratum) signaling in case of handovers, including user authentication, controlling and roaming functions. The attaching users are initially connected to the MME in the EPC area [8]. MME connects to the MassTest environment via two interfaces. S1-MME is a reference point for signaling between MME and eNB, which protocol is based on IP level, for delivery guarantees provided by SCTP [9]. The signaling protocol is called S1AP. S6a (also called as Gr in 2G and 3G) is an IP based interface between MME and HSS (Home Subscriber Server). The transport is based on SCTP, while the application signaling is Diameter [10] based.
A. The connection of one eNB, the access layer of the EPC To get convinced by the proper work of the network, first we examine a use-case where all network node states are stable, there is no load at all, and we connect only one eNB to the NUT as represented at Fig. 3. To achieve this, we have to establish connection on each layer, one another.
B. SGW (Serving Gateway) The SGW’s main function is to control and allocate data path resources for User sessions in-between the eNBs and the PGW. The User Plane tunnels are established with GPRS Tunneling Protocol (GTP), based on the control guidance of the MME or PGW. The SGW connects to the Mass-Test environment through the S1-U interface where user traffic is expected on UDP (User Datagram Protocol) based GTP. Towards the PGW direction S5 connection is used, which is an internal interface on the NUT.
Examined EPC Node: MME Examined interface: S1-MME
Figure 3. Connecting one eNB to the NUT
1. C. PGW (Packet Data Network Gateway) PGW (or PDN-GW) is mainly responsible for connection to the outside IP network, and reserves endpoint IP addresses. Furthermore, it handles the UE traffic and related services [11] like billing, zero rating or Quality of Service controlling can be
2.
62
IP connection between MME and eNB addresses shall be up and running. To establish SCTP layer the protocol shall go through the establishment phases and shall be finished INIT, INIT_ACK, COOKIE_ECHO, COOKIE_ACK. Afterwards it can only send DATA
3. 4.
and SACK to establish the S1AP protocol. It is very important, that the SCTP setting on both sides match. The correct S1 Setup can be analyzed on the link and also on the MME. Status check. After the correct protocol match and setup request from both side, the MME and eNB shall know about their pair.
There are plenty solutions for failovers – such as redundancy paths, standby routers –, but the failure handover timing is usually not synchronized among the whole network, which could cause transients and unexpected signalling storms. At this point we investigate a situation when the S1-MME connection is stopped for a different duration. This allows testing the EPC reaction and its secondary effects on the whole core network.
B. Mass load of connecting and disconnecting eNodeBs After examining the system viability with one eNB in the previous (III.A) point, now we plan to simulate thousands of eNBs connection as shown at Fig. 4. During the simulation, the EPC was started with minimal HW resources. The main question was: how many eNBs can handle the core without failures. Furthermore: what happens when we reach the maximum number of eNBs: will there be any side effect, failure report; and how it avoids the next connecting eNBs. The beginning of the use-case is similar to III.A; in advance point 2 and 3 are repeated with different IP address. The result of the connection can be verified on the Mass test and also on the MME side.
Examined EPC Node: MME Examined interface: S1-MME 1. 2. 3.
4.
Examined EPC Node: MME Examined interface: S1-MME
5.
The SCTP and S1AP connection was established between MME and Mass-Test device. Based on the method mentioned in III.B, we connected 10 000 eNBs to the MME. Fix Parameters were: eNB group, TAC, S1mme_LocalPort, S1mme_RemotePort, changing parameters: S1mme_Local_IP_Address, eNB_ID Status checking: 10 000 eNBs can be seen in the MME, with different PeerID, Global ID, the SCTP path state is active. SCTP HB (HeartBeat) messages can be seen on the network. The SCTP link is banned for different time intervals.
The SCTP connection usually sends HeartBeat (HB) messages to check the path. In case of missing several HBs, the link is marked as down, however HB is still sent to the peer. In case of HB ACK returns after a link failure, the S1AP Setup is done immediately. In this situation the setup is not bonded to the load generator’s setup rate, however all eNBs shall be connected as shortly as possible. In a wrongly set system, this can cause 1000/s connection rate. At this point the interface can overflow, messages can be dropped, and the situations of losing HB recur. This situation can go to an endless error state. D. Connecting one user to the EPC, examine the session key caching from the HSS. In the previous use-cases the connection of the S1-MME link was investigated from the network nodes point of view – but not from the users. To examine the proper subscriber connection we shall also check the key caching and handling on the MME. In this case, the S6a connection to the HSS is also handled by the Mass-Test device as shown at Fig. 5. The keys – which are needed for the users to connect to the network – are pre-generated, and can be easily checked when connecting the users. The HSS shall generate the following keys in advance: CK, IK AUTN, based on the identifiers, calculating the Kasme, Integrity and ciphering algorithm (based mainly on EIA1/EEA1) [14].
Figure 4. Connecting lot of eNB to the NUT
Test allows to examining different features and abilities of the EPC: a) The establishment and destruction speed of SCTP layers among eNBs and MME. We can also check the COOKIE generation mechanism at both side. b) The setup and failure handling speed of S1AP. c) Testing the NUT capability limits of eNB handling. C. Effect of suddenly disconnected S1AP interface in case of Mass-loaded EPC and it’s effect to EPC network processor At the first point of this chapter (III.A) we tested with one connecting eNB. After (III.B) we investigated the limits of the MME with mass-loading them, and now we simulate some basic failure of the connecting link. One of the most occurring failures in the networks is the IP as transport layer’s failure.
Examined EPC Node: MME Examined interface: S1-MME
63
The examined features: a) The maximum connection and disconnection speed of Users to the EPC. b) Maximum throughput of the User data in both uplink and downlink direction. c) Maximum throughput of User data with different payload, such as TCP or UDP. d) Maximum number of connected users to the NUT. IV.
Figure 5. Connecting a subscriber to the NUT
1. 2. 3. 4.
5.
In the use cases above, we described some essential items of LTE functionality testing. The smooth introduction of a new feature or interface must be tested with basic one-user scenario, but to force the system into the live working conditions, mass-load testing is inevitable. To unveil the limitations of the NUT (in our case the Evolved Packet Core), we described several valid setup cases, where the test equipment simulated thousands of eNBs and hundreds of thousands of Users, so as their authentication and encryption procedures, even though the fact the users and nodes were simulated.
Subscriber connects to the eNB, request is forwarded to MME. Based on request, the MME asks authentication key from the HSS. The HLR-HSS sends back authentication key(s). Between the MME and the subscriber, the appropriate messages carrying the XRES shall match. This can be analyzed on the Mass test side. The subscriber establishes signalling connection with MME, and eNB establishes bearer with SGW for user data.
REFERENCES [1]
E. Mass connection of users to the the EPC. After checking one subscriber’s proper connection in the previous section, it is time to examine how many users can be handled simultaneously by the EPC as shown at Fig. 6.
[2] [3] [4]
Examined EPC Node: MME, SGW, PGW Examined interface: S1-MME, S6a, S1-U, SGi
[5] [6] [7]
[8]
[9] Figure 6. Mass load of subscribers
1. 2.
3. 4.
5.
CONCLUSION
[10]
Connect 50 eNBs to the MME. Based on fix parameters of MNC, MCC, HSS addr., and changing IMSI, IMEISC, MSISDN, connect thousands of Users. Status check on NUT and load generator. Compare the connected user number between the two sides. To test the data throughput, the Mass Testing environment can send data (TCP/UDP) packets to the emulated internet connection, and in return the traffic can be multiplied. Disconnect the subscribers and eNBs.
[11]
[12]
[13]
[14]
64
M. Olsson, S. Sultana, S. Rommer, L. Frid, and C. Mulligan, SAE and the Evolved Packet Core. Oxford, UK: Academic Press, 2009. 3GPP TS 36.413, S1 Application Protocol, February 2010 [Online]. Available: http://www.3gpp.org/dynareport/36413.htm 3GPP TS 29.060, GPRS Tunnelling Protocol, V6.9.0, 2005 [Online]. Available: www.3gpp.org/DynaReport/29060.htm 3GPP TS 29.272, Mobility Management Entity (MME) and Serving GPRS Support Node (SGSN) related interfaces based on Diameter protocol, 2010 [Online]. Available: www.3gpp.org/DynaReport/29272.htm Y. Chen, Xavier Lagrange, “Architecture and Protocols of EPC-LTE with relay”, pp. 9, Telecom Bretagne, May 2013. P. Varga, P. Olaszi, “LTE core network testing using generated traffic based on models from real-life data” IEEE ANTS, Chennai, India, 2013. 3GPP TS 29.274, Evolved General Packet Radio Service (GPRS) Tunnelling Protocol for Control plane, 2010 [Online] http://www.3gpp.org/DynaReport/29274.htm 3GPP TS 29.061, Interworking between the Public Land Mobile Network (PLMN) supporting packet based services and Packet Data Networks (PDN), 2010 [Online]. Available: www.3gpp.org/DynaReport/29061.htm IETF RFC 4960, Stream Control Transmission Protocol, September 2007 [Online]. Available: https://tools.ietf.org/html/rfc4960 IETF RFC 6733, Diameter Base Protocol, October 2012 [Online]. Available: https://tools.ietf.org/html/rfc6733 3GPP TS 23.401, General Packet Radio Service (GPRS) enhancements for Evolved Universal Terrestrial Radio Access Network (E-UTRAN) access, 2008 [Online]. Available: www.3gpp.org/ftp/Specs/htmlinfo/23401.htm P. Olaszi, “Complex Load Testing of Mobile PS and CS Core,” EuroNOG 2012, September 2012. [Online]. Available: http://www.data.proidea.org.pl/euronog/2edycja/materials/PeterOlasziComplex Load Testing of Mobile PS and CS Core.pdf Ixia, LTE Accessing Testing, 2016 [Online]. Available: https://jp.ixiacom.com/sites/default/files/resources/datasheet/ixload_lte_ access.pdf D. Kozma, “Network- and service management support through the analysis of S1AP CDR’s ”, MSc Thesis, 2015.
Traffic Analysis Methods for the Evolved Packet Core Daniel Kozma
Pal Varga
Subscriber Data Management SSC Magyar Telekom Budapest, Hungary Email:
[email protected]
Dept. of Telecommunications and Media Informatics Budapest University of Technology and Economics 2 Magyar Tudosok krt., Budapest, Hungary, H-1117 Email:
[email protected]
Abstract - While LTE networks are getting widely deployed all around the world, their network and service management processes are still destined to work based on raw traffic statistics. This is partially due to the limited capabilities of network-wide processing methods. These would allow operators to correlate control and user plane information of various interfaces and protocols of the Evolved Packet Core (EPC). This paper presents some of the desired outcomes for traffic processing - both from network and service management points of view and mainly raises problems which will gain increasing attention in the future. We discuss the basic requirements for these methods: which EPC interfaces are to be monitored, which key control messages and parameters help in cross-correlating the scattered pieces of information. After setting these targets and requirements, we describe processing methods that allow extracting the desired information. There are many obstacles to overcome here, including ciphered control messages and global identifiers hidden by temporary ones.
I.
INTRODUCTION
The worldwide deployment of LTE networks and the mass rise of the tablet and smartphone market surged the demand for mobile connectivity. These also increased the user’s expectations in terms of bandwidth, reliability, access speed and Quality of Service management (QoS).
networks as the LTE and IMS (IP Multimedia Subsystem) architectures merge. Previously these were two separate networks (voice and data) – and they now became one single all-IP system. This new network architecture with several interfaces and diverse protocols requires powerful troubleshooting tools. Operators need to monitor each and every subscriber session to immediately detect any decrease in Quality of Experience. To support this process, the operators need a powerful monitoring and troubleshooting system. Creating such a system is a challenge for designers and developers, as well. II.
PROTOCOL LAYER
This chapter introduces the protocol layers and the protocol stack in the LTE network. A. Physical Layer (PHY) Physical Layer handles typical Layer-1 functions, such as coding/decoding, modulation/demodulation, mapping, power control, cell search (for initial synchronization and handover purposes) and other measurements (inside the LTE system and between systems) for the RRC (Radio Resource Control) layer. The physical layer offers services to the MAC (Media Access Control) layer in the form of transport channels.
In this new network scenario, traffic characterization issues, traffic monitoring, and analysis are the major importance for the operators and the system developers. Additionally, mobile operators face the challenge of monitoring even larger scale
Figure 1: Protocol Layers within LTE [1]
B. Medium Access Control (MAC)
A. User Plane
The MAC layer’s main task is to handle the multiplexing of logical channels, uplink and downlink scheduling. It’s also responsible for the hybris automatic request (hybrid ARQ) retransmissions. The scheduling functionality is located in the eNodeB for both uplink and downlink. The MAC layer emulates a full-duplex logical communication channel in a multi-point network. It provides services to the RLC in the form of logical channels.
On the user plane, between the eNodeB and PGW (Packed Data Network Gateway) those packets are tunneled which are in the core network, and are encapsulated in a specific EPC protocol. On different interfaces, different protocols are used. The most widely used protocol over the core network interfaces is the GPRS Tunneling Protocol (GTP). The user data is tunneled by this protocol between SGW (Serving Gateway) and eNodeB, and also between the SGW and the PGW. All user IP packets are encapsulated by the GTP-U. The difference between the user plane (GTP-U) and the control plane (GTP-C) is that they can be distinguished by different RLC entities at the RLC layer.
C. Radio Link Control (RLC) RLC [3] can run in three specific modes: Transparent Mode (TM), Unacknowledged Mode (UM), and Acknowledged Mode (AM). The RLC is responsible for the retransmission handling, duplicate detection, segmentation and concatenation. Depending on the modes, RLC is also responsible for the insequence delivery to the higher layers such as PDCP or RRC. In case of PDCP the RLC provides services in the form of radio bearers, where one RLC entity is configured for a terminal.
B. Control Plane Methods of the Control Plane are responsible for mobility, security, bearer setup and connection. Radio-specific functionality is handled by the access stratum’s control plane. The methods handled by MME include EPS bearer management, security, authentication and idle-mode procedures such as paging. These are handled by the nonaccess stratum’s control plane.
D. Radio Resource Control (RRC) The RRC is located in the eNodeB and responsible for the RAN-related procedures including the broadcast of System Information related to the non-access stratum (NAS), broadcast of System Information related to the access stratum (AS), paging, establishment, maintenance and release of an RRC connection between the UE and E-UTRAN, security functions including key management, establishment, configuration, maintenance and release of point to point Radio bearers.
The RRC, which is a layer-3 access stratum protocol – is handled by the eNodeB. This is the access stratum’s main controlling function as it’s responsible for broadcasting system information, transmitting paging’s message from the MME, establishing the radio bearers and by RRC signaling, configuring all the lower layers between the UE and eNodeB. On the control plane between the eNodeB and the core network, the MME, the S1AP (S1 Application Protocol) is used. By the S1AP service like the S1 bearer set-up and paging initiation are provided.
E. Packet Data Convergence Control (PDCP) PDCP Layer is responsible for the IP header compression to reduce the number of bits to transmit over the radio interface. PDCP is also responsible for ciphering and – for the control plane – integrity protection of transmitted data. Maintenance of PDCP Sequence Numbers (SNs), in-sequence delivery of the upper layer Packet Data Units (PDU) at re-establishment of lower layers, duplicate elimination of the lower layer SDUs at re-establishment of lower layers for radio bearers mapped on RLC AM, mapped on DCCH and DTCH type of logical channels.
The GTP’s control part is the GTP-C (GPRS Tunneling Protocol Control Plane) protocol. It is used for specific signaling of the EPS bearer set-up and forwarding of UE context during MME change, on the control plane between the LTE core nodes, SGW, PGW and MME. The next generation Authentication, Authorization and Accounting (AAA) protocol is the Diameter protocol, which is widely used for IMS entities in the IMS architecture to exchange AAA-related information. The DIAMETER’s basic concept is to be able to provide a protocol that can be extended – in order to provide AAA services to new access technologies.
F. Non Access Stratum (NAS) Protocols The Non-Access Stratum (NAS) protocols form the highest stratum of the control plane between the user equipment (UE) and MME. NAS is handled by the MME and includes EPS bearer management, security and authentication and it’s also responsible for the different idle-mode procedures. III.
C. Special issues with conversion of ciphering keys EPS AKA [4] is the Authentication and Key Agreement procedure that is used between UE and EPC Core Network. EPS AKA produces keying material forming a basis for user plane (UP), RRC, and NAS ciphering keys as well as RRC and NAS integrity protection keys. The deciphering is hard in some cases – as presented below.
PROTOCOL ARCHITECTURE
In case of LTE, we separate the radio protocol architecture into control plane - and user plane.
66
There are two possible cases: 1) UE connects to 4G and the MME requests a new key. We have to find the Send Authentication Info message (SAI) on the S6a interface – between the HSS/HLR and SGSN/ MME – which was sent originally by the MME. After that the S1AP dialog is searched. The easiest way is to find the right XRES from the Accounting Request (ACRS) message. 2) The UE connects to 4G, but it gets keys from 3G (SGSN/MME). It’s possible, that the key delivery is not visible on the Gn interface, because of the combined SGSN/MME. In that case we have to search for the originally key requests on the MAP interface (SGSN-HLR). We have to find the Attach message on the S1-MME interface, which contains two TMSIs. We need the TMSI from the Old GUTI (Original UTRAN values P-TMSI). After that we have to search for “SGSN Context” or “SGSN Identity” messages with the P-TMSI on the Gn interface, which is between the SGSN and GGSN.
Figure 2: EPC and 3G Architectures with Stars marking interfaces for Ciphering Key collection
We have to examine the whole S1AP dialog, and if it contains ACRS message, then we have to find the new keys. There are two possible solutions: in the GTP message (on the Gn interface) and in the SAI (on the S6a interface). With the XRES [5] we can find the authentication vectors (CK, IK, AUTN, RAND, XRES). From that we can count the KASME. It’s hard to find the original keys, because the M-TMSI on the S1AP is encrypted. To solve this, we have to examine on Gn the “Create PDP Context” messages, and with the GTP TEID we are able to find the message on S1AP, because the S1AP message will contain the same GTP TEID identifier.
In the Attach Request or Tracking Area Request messages (on the S1-MME interface), - when the user connects to 4G – we will always find these identifiers: Old GUTI1, NAS Key Set Identifier, Additional GUTI (only when the UE contains 4G and 2G/3G identifiers at the same time). The Additional GUTI is always the 4G’s identifier, the Old GUTI is 2G/3G identifier if there is no 4G identifier. Two types of messages contain two different identifiers, but we have to decipher both identifiers in S1AP. We have to resolve the GUTI in the S1AP messages, because it’s a criterion to get the IMSI2 and the keys. There are more solutions [6] to handle this. In our case the Key Server (KS) can collect the keys from the specific interfaces, shown by Fig. 2. Stars mark interfaces for Ciphering Key collection, whereas the circle marks the S1-MME interface, with S1AP protocol messages to be deciphered.
IV.
TRAFFIC ANALYSIS METHODS
In an operator’s point of view, it’s very important that we can monitor our network as effectively as possible. In case of the LTE, the solution of its monitoring is a challenge, because the network itself is very complex, the tracking of the signaling between the nodes require serious network knowledge, because on the different interfaces we can go on by other and other identifiers to chart the signaling which belong to the given transaction.
Gn (GTP): IMSI, P-TMSI3, LAC/RAC4, authentication vectors (CK, IK, AUTN, XRES), and the actual key (CK, IK, KSI) Gr (MAP): IMSI, keys (CK, IK, AUTN, XRES)
Therefore, while formulating the monitoring system we must strive to be able to search the easiest way possible, because in case of only one mistake time is also critical, for example at tracking of a global network aim or fraud calls. Usually while searching for a transaction, mostly the user’s Mobile Subscriber ISDN Number (MSISDN) is available so the best solution would be if, by entering the MSISDN, we could get all the signaling - which belong to the given transaction or the given interval – of the user. However, this is a difficult monitoring challenge.
S6a (Diameter): IMSI, keys (KASME, XRES)
1
Globally Unique Temporary ID International Mobile Subscriber Identity 3 P-Temporary Mobile Station Identifier 4 Location Area Code/Routing Area Code 2
67
Let’s suppose [4], that we are interested in the messages on the S1-MME interface. If the deciphering on this interface is not solved, then with a deep knowledge of the network and with lots of time, we can get the required messages. The under mentioned diagram shows the process:
Multimedia Subsystem Application Server (IMS-AS)) the user’s equipment is identified by an IP address – which was not enough information about the user for us. However, we can search for the IP address on the Gx interface, where an International Mobile Subscriber Identity (IMSI) is assigned to the user’s IP address. In this case the other challenge is that it has to be online, if we want to merge these data’s from Gn to the Rx data’s. These interfaces are shown in Figure 2. where the External Packet Data Network represents the IMS. It will be very useful from the point of traffic analysis, that we could log all closed sessions in Gx. The logs must contain the important parameters of the session, such as MSISDN, IMSI, IP addresses, SessionID, message numbers, first message’s time stamp, last message’s time stamp and the reason of the closing. From the side of the network it would be interesting to know, how long a session takes and log the results, for example: 1 hour, 1 day, 2 days and so on. It would be a further move forward, if the protocols would know the IMSIMSISDN binding. With this, we could reduce the operator’s tasks greatly, although this is a complex problem. The appearance of the IMSI-MSISDN pairs on every protocol (or at least on the protocols important to the operator) is nontrivial, because in some cases it raises a serious question: from where we acquire the necessary data for this. VI.
In this work, first we got an inside view of the LTE protocol layers. After that we briefly discussed what kind of problems we are facing in case of ciphering and deciphering. Handling this is a difficult engineering problem, because we have to know the contexts between the protocols, keys and identifiers. With an example, we saw a case that showed us, how difficult it is to verify a single call nowadays. In the future to handle this, we have to think about intelligent message and parameter correlations, as solutions. This paper revealed some possibilities, like the IMSI-MSISDN binding, which makes the operator’s work simpler. One of the most important things is to develop the network monitoring system in parallel with the rising expectations of the customers.
Figure 3: Call-flow in case of CS fallback [4]
This non-standard case presents, that we have to count with many various cases while monitoring the LTE network. The example above belongs to a CS fallback case. The progress’ essence is, that our user is on 4G, but because of the call – due to the fact that our network can’t handle the VoLTE calls yet or because of some other network aim – it falls back to 3G and the call gets built up on 3G. The possibilities of the process are shown in the Figure 2. This is a good example to see, how difficult is to get the identifiers and keys for the deciphering. It shows us where and which data are necessary for us to get the IMSI in the LTE network. This paper does not explain the detailed processes, for further information, refer to [4]. V.
CONCLUSIONS
REFERENCES
POSSIBLE SOLUTIONS
The best solution according to an operator expert would be the search for the MSISDN, as the users and Charging Data Records (CDR) are usually identified with MSISDN. However, currently as a first step we always have to acquire the IMSI that belongs to the MSISDN, so that we can start the search. For example, on the Rx Interface (which is between the Policy and Charging Rules Function (PCRF) and the IP
68
[1]
Y. Chen, Xavier Lagrange, “Architecture and Protocols of EPC-LTE with relay”, pp. 9, Telecom Bretagne, May 2013.
[2]
E. Dahlman, S. Parkvall, J. Sköld, “4G LTE/LTE-Advanced for Mobile Broadband”, Academic Press is an imprint of Elsevier, pp.109–126, 2011.
[3]
EventHelix.com Inc, “3GPP LTE Radio Link Control (RLC) Sub-Layer”, pp. 7-17, 2009.
[4]
D. Kozma, “Network- and service management support through the analysis of S1AP CDR’s ”, 2015.
[5]
J. Korhonen, T, Savolainen, J. Soininen, “Deploying iPv6 in 3GPP Networks”, pp. 7-17, John Wiley and Sons Ltd, 2013.
Annotation of movies for camera movement recognition Borbála Marosvári Department of Telecommunications and Media Informatics Faculty of Electrical Engineering and Informatics Budapest University of Technology and Economics Budapest, Hungary
[email protected] Abstract—An automated camera movement recognition system would make the iconic analysis of motion pictures a fast and easy process. For classic art movies the video metadata is not always available digitally, if at all. Recreating these metadata manually is a hard task. In the following I present the system I developed for automatically creating annotations for movies identifying occurring camera movements. The system analyzes the video stream itself by using different computer vision algorithms, such as optical flow and SURF descriptors, after which the extracted features were fed into a learning algorithm. The finished system includes the use of different frameworks and platforms. I tested the entire system on a complete movie, and evaluated the results.
In order to circumvent these shortcomings I decided to use the annotations only when testing the system’s ability to differentiate static camera movement from every other one. Following this I tested the system’s performance differentiating between subcases of non-static movements mostly by visual inspection.
A. Definitions Static: The camera is still, no movement occurs.
Tilt: The camera is tilted upwards or downwards, while staying in place.
Fahrt (dolly/track): The camera is moved on a horizontal plane.
Svenk-fahrt (pan and track): Panning and tracking at the same time.
However there were certain errors in the annotations, which may have made learning and testing somewhat unreliable. In some cases the timing of the annotations were off by a few seconds, while in others shorter camera movements, which take less than a second, or camera adjustments necessary to fit characters in the shot were considered static. Another imperfection in the annotations proved to be the fact that when two camera movements occur at the same time, they were annotated as one. Furthermore every tilt is noted as being a pan, which is incorrect use of nomenclature resulting in the inability to determine whether the system is able to recognize horizontal and vertical directions correctly. In summary the annotations are not as precise, as they needed to be for the task at hand.
The ability to recognize camera movement in videos is of great importance for the iconic analysis of motion pictures. Especially with regards to movies of great artistic significance, which originate from times where automatic metadata collection during filming was impossible. It could also be of help in identifying different signatures, for example the wandering camera [1]. An automated recognition system would make the process faster and easier. Therefore my aim is to create such a system. My preliminary findings and results are described in this paper. As a first step I attempted to completely automate camera movement annotation of movies. This plays an important role in computer vision and object tracking tasks. Accurate camera motion detection is required in the fields of scene analysis, shot boundary detection, vision based control, medical imaging and augmented reality as well.
Pan: The camera is horizontally rotated around its axis. Panning is possible to the left and right. The camera itself doesn’t move.
B. Manual annotations The annotations for the movies contain second-by-second notes on camera movements.
INTRODUCTION
Pedestal: Moving the camera vertically up or down.
These definitions can vary in different industries, the aforementioned terminology are the ones that I received in manual annotations from directors and movie experts.
Keywords: computer vision, annotation, camera movement, optical flow, neural network, video mining
I.
II.
RELATED WORK
Related works in camera movement recognition are mostly aimed at bettering video segmentation, shot detection algorithms. For shot characterization a set of features derived from motion vectors of P and B frames of MPEG video has been used [2]. The central component of the characterization scheme is a decision tree classifier built through a process of supervised learning. The method differentiates the following motions: stationery, object motion, panning, zooming, tracking,
69
and ambiguous. This method showed an accuracy of 78% per frame testing, and an overall of 86% accuracy per shot testing.
B. Feature Extraction For camera movement estimation and general motion detection I used different computer vision algorithms [8], [9] implemented in OpenCV library, namely Farnebäck’s optical flow algorithm [10], and SURF descriptors [11]. I derive two sets of features, one for motion detection, and the other for recognition of the different camera movements.
A template-matching algorithm to classify basic camera operations has been proposed in [3]. The method aims to index videos compressed using MPEG-1, -2, faster than real time. It constructs motion vector fields from the MPEG vectors. The method differentiates between three types of movements: panning left or right, tilting left or right, and zooming in or out.
1) Features for Motion Detection The basic concept for motion detection is to observe the optical flow vectors in the SURF points of the pictures, from which a single vector can be created to represent the overall movement of the picture, which would correspond to the main movement direction and displacement rate. The output of this algorithm is a normalized vector length, and the angle of this vector. This vector is shown in Figure 2. and Figure 3. in blue.
The mentioned methods both use the MPEG standard’s motion vectors. However when dealing with not MPEG encoded videos, which may be the case with older or rare art movies, then re-encoding would be necessary. To avoid this, I decided to use the uncompressed data of the videos. A different approach uses motion vectors that are computed using an exhaustive search block-matching algorithm [4]. From this, it extracts two features; one is the magnitude of the average of the vectors, and the other is the average magnitude of the vectors. With the combination of these vectors two types of movements are detectable, namely panning and zooming. The camera motions are constructed into a Hidden Markov Model in separate states. The HMM is then used for video segmentation.
This method is inefficient in recognizing the different camera movements, as it results in a similar vector for both tilting and pedestal movements, and for panning and tracking as well. 2) Features for camera movement recognition In order to attempt to differentiate between the particular camera movements, another algorithm I implemented divides the picture into nine equal sized rectangles, 3 by 3, and extracts a single vector from these areas, by averaging the optical flow vectors computed for the observed areas. This generates 9 vectors in total, as depicted in Figure 2. and Figure 3.
Another method uses linear combinations of optical flow models to estimate camera motion parameters [5]. They demonstrated that the proposed method estimates the camera motion parameters accurately and at a low computational cost. However the method was only tested on video data in which no object was moving.
From these vectors certain patterns of the different camera movements can be recognized. For tilting and pedestal all 9 vectors should be vertical, while for tracking and panning, the vectors are all horizontal. When dollying in or out, the vectors on the perimeter of the picture should all point outwards or inwards respectively. My goal was to recognize these patterns, in order to recognize the camera movements. The program looks for elements of these patterns, either at the top, or at the bottom of the picture.
The aim of the previous works has been to achieve better video segmentation or indexing. My aim is to be able to create statistics for different movies with regards to their artistic functions, to enable the end user to analyze the different styles of directors and photographers, similar to [6], in which data mining techniques were used to extract patterns from the metadata of a video. Collecting and analyzing camera movement data is the first step in this direction. III.
However, tilt and pedestal, and pan and track are still hardly distinguishable this way. During development I found no distinct marks which would make these movements easily separable. I resorted to a geometrical-optical solution, which is as follows.
ANNOTATION SYSTEM
The finished system includes the use of different frameworks and platforms, and also includes the subsystems for testing and evaluating the performance of the recognition system.
If we observe the two types of movement, we can see that panning or tracking the same distance results in different optical flow patterns. In Figure 1. a schematic representation of tilting and pedestal movements is shown. To reach the same point (Point B’ in Figure 1.), Point B travels the same distance in both tilting and pedestal, Point A however travels less when tilting. This is due to change in Angle of View during tilting. In pedestal, the Angle of View stays the same. With the change of the Angle of View, the size of the Field of View also changes. Therefore, in Figure 1., the optical flow in Point A’ has to be slower, than in Point B’, while in Point A” and Point B” the optical flow vectors are the same length. The side, at which the picture moves more slowly depends on the Angle of View. The same concept is true for panning and tracking (Figure 1. can also be interpreted as visualizing these movements.) In my algorithm I computed the medians for the picture’s two sides – the left and right side for panning and tracking, the top and
A. Shot detection and video sampling Finding the shot boundaries is essential in order to correctly estimate the movement of the pictures. When two consecutive frames are analyzed, they must be from the same scene, a cut occurring between them would yield incorrect results for movement estimation. Therefore the first step is to find the shot boundaries. For this I used ffmpeg’s shot detector [7], with a scene-change threshold of 0.35. The program creates a list with the first frames of the detected shots, the type of the picture (I, B, or P), and a timestamp belonging to the frame. The video is sampled every 6 frames, but a shot’s first and last frames are always analyzed.
70
bottom side for tilting and pedestal. I then computed the ratio of these two: when the ratio is between 0.9 and 1.1 it is considered tracking or pedestal, otherwise it is panning or tilting.
correcting the 6719 labels I resorted to visual inspection of the different camera movements. For this I chose a number of short video clips from the annotated movies which demonstrate the different camera movements, and tested my method on these. The tests resulted in an accuracy of 74.89%. TABLE II.
CONFUSION MATRIX OF CAMERA MOVEMENT RECOGNITION true pan
true track/dolly
true tilt
true pedestal
class precision
pred. pan
262
12
12
2
90.97%
pred. track/dolly
38
23
1
pred. tilt
3
67
pred. pedestal
7
12
class recall
84.52%
65.71%
72,83%
37.10% 31
66.34% 0%
0%
Confusion matrix of camera movement recognition
Figure 1. Schematic representation of tilting and pedestal. When tilting, A and B travels to A’ and B’, when pedestal movement occurs, they travel to A” and B” respectively.
C. Aggregating vectors, joining with ground truth labels As the manual annotations only provide information second-by-second, the computed vectors either need to be aggregated to a second-by-second level, or the labels need to be distributed to a finer granularity. I chose to distribute the labels, in order to maintain details measured with optical flow. The labels are distributed for the sampling period, which was 240ms for motion detection, and 40ms for the camera movement recognition. I also created subtitles in .srt format, in order to have the option to verify the results visually as well. These tasks are done by Excel VBA scripts. IV.
Figure 2. Correctly recognized fast left panning movement. The blue vector represents the vector averaged in the SURF points. (The vectors are enlarged for better visualization.)
TRAINING, TESTING, EVALUATION
The aggregated list for motion detection has been fed to a Neural Network learning algorithm in RapidMiner. The example set consisted of 28835 examples, which included 20537 static, and 8298 dynamic examples. I used 10-fold cross validation with shuffled sampling. The testing resulted in an accuracy of 80.84% ± 0.55%. TABLE I.
Figure 3. Correctly recognized downwards tilting movement. (The vectors are enlarged for better visualization.)
The results show that the direction of the movements is correctly identified, the problem is still separating the different camera movements: telling panning – tracking, and pedestal – tilting apart. The improvement in tracking motion recognition is due to the correct recognition of forward and backward dollying, which were considered to be the same in the annotations, because in Hungarian terminology these movements are named alike, which is the reason why I grouped them together as well.
CONFUSION MATRIX OF MOTION DETECTION true static
true non-static
class precision
pred. static
18322
3311
84.69%
pred. non-static
2215
4987
69.24%
class recall
89.21%
60.10% Confusion matrix of motion detection.
The results however include the errors in the manual annotations, which in some cases are so severe, that it is unusable for differentiating the camera movements. Instead of
71
V.
Acoustics, Speech, and Signal Processing (ICASSP), 2002 IEEE International Conference on. Vol. 4. IEEE, 2002. [4] Boreczky, John S., and Lynn D. Wilcox. "A hidden Markov model framework for video segmentation using audio and image features." Acoustics, Speech and Signal Processing, 1998. Proceedings of the 1998 IEEE International Conference on. Vol. 6. IEEE, 1998. [5] Srinivasan, Mandyam V., Svetha Venkatesh, and Robin Hosie. "Qualitative estimation of camera motion parameters from video sequences." Pattern Recognition 30.4 (1997): 593-606. [6] Kimiaki Shirahama, Yuya Matsuo, Kuniaki Uehara: Extracting Alfred Hitchcock's Know-How by Applying Data Mining Technique [7] FFmpeg Filters Documentation, http://www.ffmpeg.org/ffmpegfilters.html#select_002c-aselect Retrieved: 2015. 11. 28. [8] Motion Analysis and Object Tracking, OpenCV 2.4.13.0 documentation. http://docs.opencv.org/2.4/modules/video/doc/motion_analysis_and_obj ect_tracking.html#calcopticalflowfarneback Retrieved: 2015. 11. 28. [9] Feature Detection and Description, OpenCV 2.4.13.0 documentation. http://docs.opencv.org/2.4/modules/nonfree/doc/feature_detection.html# surf Retrieved: 2015. 11. 28. [10] G. Farnebäck, “Two-frame motion estimation based on polynomial expansion,” Lecture Notes in Computer Science, 2003, (2749), pp. 363370. [11] Bay, Herbert, Tinne Tuytelaars, and Luc Van Gool, "Surf: Speeded up robust features." Computer vision–ECCV 2006. Springer Berlin Heidelberg, 2006. pp. 404-417.
DISCUSSION
In summary, in its current state the system is capable of differentiating between static, horizontal and vertical movements, however when it comes to distinguishing between similar camera movements, such as track and pan, or tilt and pedestal, the classification’s accuracy remains relatively low. Though the basic operation hypothesis is seemingly sound, during actual implementation the vectors do not show the expected patterns due to various obstructions in the frame. A solution to this problem might be background-foreground segmentation, but as of the writing of this paper no attempt was successful in achieving this. REFERENCES [1]
[2]
[3]
Johnson, K. (1993). „The Point of View of the Wandering Camera.” Cinema Journal, 32(2), 49-56. doi:1. Retrieved from http://www.jstor.org/stable/1225604 doi:1 Nilesh V. Patel, Ishwar K. Sethi: “Video shot detection and characterization for video databases.” Pattern Recognition, Vol. 30, No. 4, 1997, pp. 583-592. Lee, Sangkeun, and Monson H. Hayes III. "Real-time camera motion classification for content-based indexing and retrieval using templates."
72