Plenary Lecture / Robotics and Cyber Physical System의 21일 22일 강연
David Harel 교수님과 Kyung-Suk Kim 교수님의 PlenaryLecture 는 정말 최고였습니다.
프레젠테이션속에 녹아있는 전달하고자 하는 명확한 내용과 전체 강의의 튼튼한 뼈대를 하나도 놓치지 않고서
두루 설명하시면서 중간중간 집중이 떨어질만한 타이밍에 동영상을 보여주시면서 간간히 웃겨주시는 스킬이 보통의 강연자와 달랐습니다.
Harel 교수님은 CS와 소프트웨어 엔지니어들이 어떻게 과학적인 테크닉을 적용하여 문제를 이해하고 풀어나가야 할지를 재미있는 영상과 함께 자신의 생각을 풀어주셨습니다. 특히 biological systems의 실제적인 modeling 에 대한 이해법과 전체의 시스템을 볼때 세세한 부분들까지 어떻게 분석하며 이해해야 할지를 쉽게 가르쳐주셨습니다.
Kyung-Suk Kim 교수님은 "Science and Technology in New Bridging Era: Engineering of Self-organized Emergence"의 주제로 이제는 beyond frontiers 를 향하는 우리의 세대들이 가져야 공학도의 마인드와 현 DGIST의 교육이념을 잘 적목시키셔서 미래의 우리 공학도가 가져야 할 마인드에 대해서 자신의 업적(ruga)과 함께 적절한 예로 풀어서 명쾌하게 설명해주셨습니다. As this is a talk for a science and technology institution, special emphasis will be focused on science and engineering education for next generation scientists and engineers with strong three C’s – “Commitment”, “Credibility” and “Creativity”.
그밖의 인상깊었던 강연.
- 정말 기대했던 펜실베니아 대학의 Vijay Kumar 교수님의 "Beyond UAVs: Flying Robot Swarms" 강연
- Chenyang Lu 교수님의 “Wireless Clinical Monitoring at Scale”
- Ji-Woong Choi 교수님의 “Bio-medical CPS and Its Applications”
* I sincerely promise that this paper would be used for purely academic purposes only and not for any commercial applications.this copyright belong to original author. - from blog owner.
This content refer to "Channel Models A tutorial' paper of Raj Jain, jain@acm.org author in Google.
V1.0February 21, 2007
Channel Models A tutorial
1. The Basic Concepts
Wireless signal의 특성은 그것이 전파하는 (송수신간의) 매체를 통과하면서 변하게 된다. 이러한 특성은 송,수신 안테나 사이의 거리에 의하여 의존하게 되며, 그 거리에는 신호가 지나가는 경로와 환경(방해가능한 빌딩과 어떠한 물체 -> 이는 신호의 반사 및 흡수가 가능하다.) 적인 요소가 존재하여 채널의 특성을 변화시킨다.
만약 우리가 송수신 안테나사이의 매체 i.e 채널을 알수있다면, 입력신호를 앎으로써, 출력신호를 알수있게 된다.
Therefore, this model of the medium is called channel model.
In general, the power profile of the received signal can be obtained by convolving the power profile of
the transmitted signal with the impulse response of the channel. Convolution in time domain is
equivalent to multiplication in the frequency domain. Therefore, the transmitted signal x, after
propagation through the channel H becomes y
y(f)=H(f)x(f)+n(f)
일단, 송신신호와 수신신호와의 상관관계를 통하여 채널 추정이 가능하다.
위의 식에서 H(f)는 우리는 Chaneel responce라고 부를것이며, n(f)는 노이즈성분이다.
Note that x, y, H, and n are all functions of the signal frequency f.
The three key components of the channel response are path loss, shadowing, and multipath as explained below.
따라서, 우리는 채널에 영향을 주는 대략적인 3가지의 성분 path loss, shadowing, and multipath 를 통하여서, 채널을 추정할수가 있게 된다.
2.1 Path Loss
The simplest channel is the free space line of sight channel with no objects between the receiver and the transmitter or around the path between them. In this simple case, the transmitted signal attenuates since the energy is spread spherically around the transmitting antenna. For this line of sight (LOS) channel,the received power is given by:
먼저, 가장 간단한 형태의 채널을 정의해보자. 이는 자유공간 즉, 벽면도 없고 반사도 없는 그래서 손실도 없는 LOS (direct path propagation) 타입이다.
감쇠의 원인은 안테나의 전파(신호) 방사형태가 구면의 형태로 에너지를 확산시키기 때문에 P는 D^-2에 비례한다.
Here, Pt is the transmitted power,Gl is the product of the transmit and receive antenna field radiation patterns, λ is the wavelength, and d is the distance. Theoretically, the power falls off in proportion to the square of the distance. In practice, the power falls off more quickly, typically 3rd or 4th power of distance.
G1은 안테나의 방사패턴에 해당하는 Loss를 의미한다.
이론적으로 파워는 거리의 제곱에 비례하여 감소하지만, 사실 실제환경에서는 이보다 빠른 세제곱, 네제곱배로 감소한다.
The presence of ground causes some of the waves to reflect and reach the transmitter. These reflected
waves may sometime have a phase shift of 180 ° and so may reduce the net received power. A simple two-ray approximation for path loss can be shown to be:
자 이제 Free space 시나리오를 좀더 꼬아서 Ground 가 존재한다고 가정한다면, 이는 반사를 야기시킨다. -> 위상을 180도로 변화시키며, Power를 감소시킨다.
Here, ht and hr are the antenna heights of the transmitter and receiver, respectively.
Note that there are three major differences from the previous formula. First, the antenna heights have effect. Second, the wavelength is absent and third the exponent on the distance is 4.
이 공식의 앞전의 위의 공식과 3가지의 주요한 다른점이 존재한다.
안테나높이 고려, 파장고려X, 지수부4승.
2.1.5 Reflection from a ground plane (by Fundamentals Wirelsess Communication)
Consider a transmit and a receive antenna, both above a plane surface such as a road (Figure 2.6). When the horizontal distance r between the antennas becomes very large relative to their vertical displacements from the ground plane (i.e., height), a very surprising thing happens. In particular, the difference between the direct path length and the reflected path length goes to zero as r−1 with increasing r (Exercise 2.5). When r is large enough, this difference between the path lengths becomes small relative to the wavelength c/f .
Since the sign of the electric field is reversed on the reflected path5, these two waves start to cancel each other out. The electric wave at the receiver is then attenuated as r−2, and the received power decreases as r−4. This situation is particularly important in rural areas where base-stations tend to be placed on roads.
In general, a common empirical formula for path loss is:
그리고 이를 더욱 일반화한 형태로, 경험에 의한(실험에 의한) 공식은 아래와 같다.
위의 공식은 실제적인 path loss를 고려한 형태의 수신되는 신호의 Power를 의미한다.
Where P0 is the power at a distance 0 d and α is the path loss exponent.
The path loss is given by:
Path Loss 공식은 아래와 같이 dB표현식으로 주어진다
HerePL(d0 ) is the mean path loss in dB at distance 0 d . The thick dotted line in Figure A.1.2 shows the received power as a function of the distance from the transmitter.
If you want to know the more detail information about this section, please refer to Fundamentals Wireless Communication text book's chapter 2. It's free on website.
If there are any objects (such buildings or trees) along the path of the signal, some part of the transmitted signal is lost through absorption, reflection, scattering, and diffraction. This effect is called shadowing. As shown in Figure A.1.3, if the base antenna were a light source, the middlebuilding would cast a shadow on the subscriber antenna. Hence, the name shadowing.
쉐도잉은 송신 신호가 수신단으로 가기까지 어떠한 장애물이 존재하여, 송신신호가 흡수,반사,회절,흩어짐을 겪게 됨으로 소실되거나 딜레이되어 수신단에 도착하게 되는데 이로 인해 다른 크기와 위상의 신호가 중첩되어서, 이를 평균전력그래프로 그려보았을 때, "로그노말분포"로 나타나기에 흔히 우리는 로그노말쉐도잉이라고 부른다.
[보충]
Shadowing은 문자적 뜻은 음영 손실 (Shadowing Loss)을 의미하며, 현상은 전파 장애물 바로 뒤에 전파적인 그림자(음영)가 드리워져 나타나는 전파 손실을 말한다. 예를들면, 송신 전파가 산,빌딩 등 장애물의 불규칙적인 전파 반사면,산란체 등 때문에 수신 전파 전력이 평균을 중심으로 요동치는 현상 이라고 볼 수있다.
The net path loss becomes:
Here χ is a normally (Gaussian) distributed random variable (in dB) with standard deviation σ . χ represents the effect of shadowing. As a result of shadowing, power received at the points that are at the same distance d from the transmitter may be different and have a log-normal distribution. This phenomenon is referred to as log-normal shadowing.
2.1.6 Power decay with distance and shadowing
The previous example with reflection from a ground plane suggests that the received power can decrease with distance faster than r−2 in the presence of disturbances to free space. In practice, there are several obstacles between the transmitter and the receiver and, further, the obstacles might also absorb some power while scattering the rest. Thus, one expects the power decay to be considerably faster than r−2. Indeed, empirical evidence from experimental field studies suggests that while power decay near the transmitter is like r−2,
at large distances the power can even decay exponentially with distance.
The ray tracing approach used so far provides a high degree of numerical accuracy in determining the electric field at the receiver, but requires a precise physical model including the location of the obstacles. But here, we are only looking for the order of decay of power with distance and can consider an alternative approach. So we look for a model of the physical environment with the fewest parameters but one that still provides useful global information about the field properties. A simple probabilistic model with two parameters of the physical environment, the density of the obstacles and the fraction of energy each object absorbs, is developed in Exercise 2.6. With each obstacleabsorbing the same fraction of the energy impinging on it, the model allows
us to show that the power decays exponentially in distance at a rate that is proportional to the density of the obstacles. With a limit on the transmit power (either at the base-station or at the mobile), the largest distance between the base-station and a mobile at which communication can reliably take place is called the coverage of the cell.
For reliable communication, a minimal received power level has to be met and thus the fast decay of power with distance constrains cell coverage. On the other hand, rapid signal attenuation with distance is also helpful; it reduces the interference between adjacent cells. As cellular systems become more popular, however, the major determinant of cell size is the number of mobiles in the cell. In engineering jargon, the cell is said to be capacity limited instead of coverage limited. The size of cells has been steadily decreasing, and one talks
of micro cells and pico cells as a response to this effect. With capacity limited cells, the inter-cell interference may be intolerably high. To alleviate the inter-cell interference, neighboring cells use different parts of the frequency spectrum, and frequency is reused at cells that are far enough. Rapid signal attenuation with distance allows frequencies to be reused at closer distances. The density of obstacles between the transmit and receive antennas depends very much on the physical environment. For example, outdoor plains have very little by way of obstacles while indoor environments pose many obstacles.
This randomness in the environment is captured by modeling the density of obstacles and their absorption behavior as random numbers; the overall phenomenon is called shadowing.6 The effect of shadow fading differs from multipath fading in an important way. The duration of a shadow fade lasts for multiple seconds or minutes, and hence occurs at a much slower time-scale compared to multipath fading.
2.3 Multi-path
The objects located around the path of the wireless signal reflect the signal. Some of these reflected waves are also received at the receiver. Since each of these reflected signals takes a different path, it has a different amplitude and phase.
반사되는 신호들이 서로 다른 경로를 가지므로, 다른 위상,크기를 가진 신호가 되기에 이를 다중경로 페이딩이라고 부른다.
[보충] : Multi-path Fading
서로 다른 경로를 따라 수신된 전파들이 여러 물체에 의한 다중 반사로 인해 서로다른 진폭,위상,입사각,편파 등이 간섭
(보강간섭,소멸간섭)을 일으켜 불규칙 요동치는 현상
Depending upon the phase, these multiple signals may result in increased or decreased received power at the receiver. Even a slight change in position may result in a significant difference in phases of the signals and so in the total received power. The three components of the channel response are shown clearly in Figure A.1.4. The thick dashed line represents the path loss. The log-normal shadowing changes the total loss to that shown by the thin dashed line. The multipath finally results in variations shown by the solid thick line. Note that signal strength variations due to multipath change at distances in the range of the signal wavelength.
그래서 아래 그림과 같은 형태의 수신 파워를 보인다. 아래의 그래프는 x축 거리가 멀어짐에 따른 y축 수신파워/송신파워의 db비를 나타낸 그래프이다. 이를 통하여 각 채널에 영향을 주는 3가지 성분들로 인하여 입력신호가 어떻게 수신되는지를 대략적으로 알수가 있다.
Since different paths are of different lengths, a single impulse sent from the transmitter will result in multiple copies being received at different times as shown in Figure A.1.5
아래의 그림은 송신 신호가 수신측에서 Multipath를 겪고서 어떻게 페이딩현상으로 나타나는지를 보여준다.
The maximum delay after which the received signal becomes negligible is called maximum delay spread τmax. A large τmax indicates a highly dispersive channel. Often root-mean-square (rms) value of the delay-spread τrms is used instead of the maximum.
송순 후에 multipath fading으로 너무 많은 딜레이와 감쇄효과가 있어서 무시해도 되는 수신신호파워를 우리는 τmax 라고 부른다.
3. Tapped Delay Line Model
One way to represent the impulse response of a multipath channel is by a discrete number of impulses as follows:
Note that the impulse response h varies with time t. The coefficients ci(t) vary with time. There are N coefficients in the above model. The selection of the N and delay values τi depends upon what is considered a significant level. This model represents the channel by a delay line with N taps. For example, the channel shown in Figure A.1.5 can be represented by a 4-tap model as shown in Figure A.1.6.
멀티 패스 채널의 임펄스 응답의 표현은 위의 식처럼, 임펄스들의 이산적인 합으로 표현될수가 있다.
[보충] : 왜 임펄스 함수인가?
흔히 채널은 시스템으로 표현할수가 있다고 한다. 왜냐하면, 입력신호를 어떤 시스템에 넣고 (채널) 출력신호를 보는 과정이 통신의 송/수신과 매우 흡사하며, 이를 수학적으로 모델링하여 나타내면 간단 명료하게 채널의 특성을 보여줄수 있기 때문이다. 임펄스 응답이란? 시스템에 단위 임펄스함수를 인가하였을 때의 출력을 의미하며, 임펄스 응답에 대한 '푸리에변환'은 통신의 주파수 특성 (전달함수 H)와 같다. 그래서 임펄스 응답을 알면 우리는 주어진 입력에 대한 출력을 쉽게 구할수 있기 때문에 우리는 임펄스 함수를 사용하게 되었다.
If the transmitter, receiver, or even the other objects in the channel move, the channel characteristics change. The time for which the channel characteristics can be assumed to be constant is called coherence time. This is a simplistic definition in the sense that exact measurement of coherence time requires using the auto-correlation function.
만약 송/수신기(ex.안테나)가 움직이면 채널의 특성도 변하게 된다. 그래서 우리는 채널이 제한된 특성을 가지고 있는 시간을 하나의 척도로 명명하였는데 이것이 coherence time 이다.
coherence bandwidth 도 이와 매우 유사하다.
For every phenomenon in the time domain, there is a corresponding phenomenon in the frequency domain. If we look at the Fourier transform of the power delay profile, we can obtain the frequency dependence of the channel characteristics. The frequency bandwidth for which the channel characteristics remain similar is called coherence bandwidth. Again, a more strict definition requires determining the auto-correlation of the channel characteristics. The coherence bandwidth is inversely related to the delay spread. The larger the delay spread, less is the coherence bandwidth and the channel is said to become more frequency selective.
delay spread는 LOS와 비교하였을 때, 위의 Figure A.1.6과 같이 지연되어 수신되는 현상을 말한다.
delay spread가 크다면 coherencebandwidth 은 작으며, 이때 채널을 우리는 frequency selective하다고 말한다.
4. Doppler Spread
The power delay profile gives the statistical power distribution of the channel over time for a signal transmitted for just an instant. Similarly, Doppler power spectrum gives the statistical power distribution of the channel for a signal transmitted at just one frequency f. While the power delay profile is caused by multipath, the Doppler spectrum is caused by motion of the intermediate objects in the channel. The Doppler power spectrum is nonzero for (f-fD, f+fD), where fD is the maximum Doppler spread or Doppler spread.
The coherence time and Doppler spread are inversely related:
coherence time과 Doppler Spread는 서로 역수관계를 가진다.
Thus, if the transmitter, receiver, or the intermediate objects move very fast, the Doppler spread is large and the coherence time is small, i.e., the channel changes fast.
Table A.1.1 lists typical values for the Doppler spread and associated channel coherence time for two WiMAX frequency bands. Note that at high mobility, the channel changes 500 times per second, requiring good channel estimation algorithms
높은 대역으로 Carrier Frequency가 갈수록 Coherence Time은 작으며, Max Doppler Spread가 높을수록 채널의 안정적인 시간 = 주파수가 Flat한 시간이 적다.
여기에선 Coherence Time과 Doppler Spread만을 비교하였으며, Doppler Spread에 대한 자세한 정보가 필요하다면 위에서 소개한 책의 Chapter 2.1.4를 참고하기 바란다.
in this Tutorial, we just handled the comparison with Coherence Time and Doppler Spread. If you want to learn the Doppler Spread, you can easier understand though the textbook which we already introduced.
솔루션들이필요하다. 그리고우리는어떻게 Cross Layer framework에서불완전한스케줄링을사용할것인지를시연하고, 최근에개발된분산알고리즘에대해서도알아볼것이다. 그리고마지막으로우리는 a set of open research problems을토의함으로써마칠것이다.
즉, 다시말해서위논문은아래의 5가지단계를따른다.
1) 기회주의적스케줄링을살펴봄
2) 멀티홉무선네트워크에서의자원배분문제를알아봄
3) 위의자원배분문제를 Loosely-coupled 된 Cross Layer에서다시자원배분문제를접근함
4) 그리고어떻게불완전한스케줄링알고리즘을사용했는지, 분산알고리즘은무엇인지설명할것이다.
5) 마지막으로이와함께고민할수있는Open Problems을다룸으로마친다.
1. 기회주의적스케줄링 ‘Opportunistic scheduling’ 의의미는?
무선시스템은 무선채널의 시변특성, 한정된 자원의 공유, 페이딩 등의 특성으로 인해 유선시스템과 비교할 때 높은 대역폭을 사용자들에게 제공하기에 어려운 문제점들을 안고 있다. 이러한 문제점을 해결하기 위해 제시된 무선채널에서의 스케줄링 방법이 Opportunistic Scheduling (기회주의적 스케줄링) 또는 Channel-Aware Scheduling 방식이다
기회주의적 스케줄링이란 하나의 엑세스 포인트가 여러 사용자를 TDMA 방식을 통해 동시에 수용할 경우, 매 타임슬롯마다 가장 채널 상태가 좋은 사용자들을 “기회주의”적으로 선택하여 서비스를 제공하는 방식을 말한다.기존의 방식에서는 사용자들의 채널정보를 알지 못하기 때문에 정적인 시분할 방식을 사용하였다. 그에 따라 채널속도가 빠르지 않은 사용자가 채널을 점유할 경우, 그 효율이 떨어지는 단점이 있었다. 이를 극복하기 위해서 매 타임슬롯마다 사용자들이 자신의 채널정보를 엑세스 포인트로 피드백하고, 엑세스 포인트는 각 사용자들로부터 받은 정보를 토대로 가장 좋은 채널상태를 갖는 사용자를 골라서 서비스를 하게 된다.
기회주의적 스케줄링을 구현하는 방법에 있어서 시스템의 처리량을 최대화하는 방식과 사용자간의 공평성을 맞추는 방식 사이의 적절한 조화를 위한 노력이 있어왔으며 또한 QoS와 best effort 트래픽을 동시에 지원하기 위한 노력이 있어왔다. 반면, 현재까지 개발된 많은 알고리즘들은 사용자수가 변하지 않고 각 사용자들의 큐가 다 비워지지 않는다고 가정하는 패킷레벨에서의 방식들이었다. 반면, 실제 시스템에서는 각 사용자들의 트래픽이 유한한 서비스 시간 또는 파일사이즈를 갖고 큐에 랜덤하게 도착하고 서비스를 다 받으면 큐를 떠나게 된다. 이를 효과적으로 분석하기 위해서는 패킷레벨에서의 분석 대신 플로우 레벨에서의 분석이 필요하다. 그에 따라, 본 논문에서 다루는 것이 기회주의적 무선시스템에서의 QoS와 best effort 트래픽의 통합과 그에 따른 문제점의 플로우레벨에서의 분석이다.
A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in many varied application areas of distributed computing, such as telecommunications, scientific computing, distributed information processing, and real-time process control. Standard problems solved by distributed algorithms include leader election, consensus, distributed search, spanning tree generation, mutual exclusion, and resource allocation.[1]
I. INTRODUCTION
Optimization-based 의접근법은지금까지통신네트워크영역에서 “Resource allocation problem” 해결을위해서광범위하게연구되어왔다. 예를들면, Internet congestion control은시스템의성능을최대한으로끌어내는convex optimization problem 으로 distributed primal or dual solutions 자원배분문제를어떻게해결하는가에대한모범적인예로써생각할수가있다. 이런류의접근법(실험법) 은 TCP(transmission control protocol)에대한깊은이해와향상된혼잡제어(congestion control) 라는솔루션을보여준다.[1-6]
어쨌든질문의핵심은앞서말한접근법이통합된 multi-hop wireless networks에서 *a clean-slate design of the protocol stack으로적용될수있다는점이다. 사실, Internet setting에서의그러한기술의직접적인어플리케이션을허용하지않는무선통신의맥락에서있어서꽤특별한도전들이있다. 특히, 무선매체는본질적으로유저들의데이터송신에의한간섭이많이일어나는다중접속매체로써, 채널의 capacity가 time-varying 의성격을보인다. 이러한이유로, 무선매체는사용자와네트워크 Layer간의상호의존성을띄기때문에기존의유선과는반대의성격을가진다. 하지만, 이런어려움에도불구하고, 최근에통합및최적화된형태로써의 Multiple layer들의무선자원을자유로이공유하거나넘나드는(Cross Layer개념) 진보된결과들을보여준다. 이와관련된흥미로운내용은섹션3에서설명한다.
(The solution of such an optimization framework will itself exhibit a layered structure with only a limited degree of cross-layer coupling.)
*The notion of a clean-slate design becomes especially attractive for multi-hop wireless networks, where the burdens of legacy systems are far less than for the Internet.
; 특히, convex programming에서Lagrange duality은복잡한최적화문제를간단한여러가지문제로써분해하는중요한핵심도구이다. 하지만, 우리는종종우리는이것만으로문제를 100% 해결하는것에는부족하단것을안다. 왜냐하면, 유선네트워크와는반대로, 많은무선네트워크에서의 Cross-layer control problems 은 not convex (볼록) 않기때문이다.
예를든다면, 무선네트워크에서의간섭문제들로인하여, 각각의시간에대해서활성화되어야하는링크들의부분집합들에대한선택에있어서정확히선택해야하는정교한스케줄링 mechanisms을요구하는것같은것이다. 무선네트워크에서, 각링크들의 capacity는신호와간섭레벨에의존적이고, 그러한것들은파워와링크의전송스케줄에의존적이다. 그래서 link capacity, power assignment, and the transmission schedule 에서의관계들은전형적으로 non-convex 하다.
6)Heavy-traffic limits are used to obtain realistic and efficient solutions to the cross-layer control problem.
cross-layer optimization 는 최근 사이에 꽤 큰 이슈로 발전 되었고, 이를 위한 포괄적인 조사는 공간적인 (space constraints) 제한을 가진다. 따라서, 이 paper에선 모두를 다 조사하진 못했다. 오히려, 포커스는 주요한 이슈와 도전들, 그리고 테크닉과 open problem들에 대해서 독자들에게 알려주는 정보전달에 대해서 맞춰져 있다. [7]을 참조하길 바란다.
Section III: we investigate the joint congestion-control and scheduling problem in multi-hop wireless networks.
섹션3의내용은주로 the cross-layer problem 를 a congestion control component and a scheduling component 2가지로깔끔하게분해하며접근한다. 하지만, non-convexity성격때문에실제네트워크에서스케줄링은매우어렵지만 cross-layer solution으로심플하지만불완전한해결법으로어느정도접근해본다.
Section IV: 당연히이부분은앞으로더보완되고다듬어져가야한다.
Section V: recent developments in obtaining imperfect distributed scheduling policies with provably achievable throughput bounds.
We then conclude with a set of open problems.
II. OPPORTUNISTIC SCHEDULING FOR CELLULAR WIRELESS NETWORKS
오랫동안 multiuser scheduling problem은산업과학교에서많은조명을받아왔다. 그리고 multiuser scheduling problem은무선네트워크에서독특한특징으로써많은동기부여를받아왔다. : 자원의크기, mobile 유저의간섭문제, 시변채널의조건들(이동성과페이딩으로인한)
게다가, 가정해보자. 유저들의 base station 으로부터의타임슬롯시스템과다운링크통신에대해서가정해보자.
base station은채널조건을기반으로어느유저가전송이가능한지결정할수가있다. 이아이디어는 SINR기반의채널컨디션에따라서수신단으로의전송을베이스스테이션이주어진 BER을만족시키며높은속도로전송을허용하는것을의미한다. 이것은 Base Station 이기회주의적기법으로, 즉높은네트워크성능유지를위하여채널의조건을이용한다는의미이다.
이와는달리기존의전통적인방법에선, 채널의가변성을제거하는것이주된관심사였다.
(예를들면, spread spectrum, repetitive coding, and power averaging)
Opportunistic scheduling 에대한설명~ (앞장참고)
우리의초점은 Downlink에서의 base station 전송시나리오로한정하며, 유/무한 backlogged cased을위한 Opportunistic scheduling solutions을볼것이다.
A. Infinite-Backlog Case
Infinite-Backlog Case 종종통신시스템분야에서프로토콜의성능평가와최대의성능량을보기위하여사용된다.
• Fairness in utility: Each user receives at least a fraction of the aggregate utility value [11], [13].
• Minimum data rate requirement: Each user receives a minimum data rate of bps [13].
• Proportional fairness: Here, the objective is to achieve a solution that is proportionally fair, i.e., increasing the mean throughput of one user from the optimal level by results in a cumulative percentage decrease by greater than of the mean throughput of other users [14]. It turns out that such a solution is achieved when the optimization problem is to maximize the sum of the logarithms of the expected rates (or the product of the expected rates), i.e.,
게다가, 시스템이증가하는경우와초기에증가하는총네트워크처리량정책안에서, 주어진 delay조건을위반하며,
Moreover, for a given delay violation constraint, when the number of users in the system increases, the total network throughput under policy (1) initially increases, and then eventually decreases to zero, but not so under the QLB policy. This should not be entirely surprising since index policies of the form (1) are agnostic to the delays incurred for different users and may not serve users whose queues are building up fast enough to remain within a delay violation probability.
또한, 주어진지연위반제약조건, 시스템증가에있는사용자의수가정책에따라전체네트워크처리량이처음증가할때, 그리고결국그렇게 QLB 정책하에서제로로감소하지만. 폼의인덱스정책이다른사용자에따른지연독립적이며, 해당대기열지연시간위반확률내에남아있는만큼빠르게구축하는사용자에게서비스를제공할수없습니다때문에이것은전혀놀라운일이안된다.
..작성중
REFERENCES
[1] F. P. Kelly, A. Maulloo, and D. Tan, “Rate control in communication networks: Shadow prices, proportional fairness and stability,” J. Oper. Res. Soc., vol. 49, pp. 237–252, 1998.
[2] H. Yaiche, R. Mazumdar, and C. Rosenberg, “A game theoretic framework for bandwidth allocation and pricing in broadband networks,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 667–678, Oct. 2000.
[3] S. H. Low and D. E. Lapsley, “Optimization flow control-I: Basic algorithm and convergence,” IEEE/ACM Trans. Netw., vol. 7, no. 6, pp. 861–874, Dec. 1999.
[4] S. Kunniyur and R. Srikant, “End-to-end congestion control schemes: Utility functions, random losses and ECN marks,” in Proc. IEEE INFOCOM, Tel-Aviv, Israel, Mar. 2000, pp. 1323–1332.
[5] S. H. Low and R. Srikant, “A mathematical framework for designing a low-loss low-delay Internet,” Netw. Spatial Econom., vol. 4, no. 1, pp. 75–102, Mar. 2004.
[6] R. Srikant, The Mathematics of Internet Congestion Control. Cambridge, MA: Birkhauser, 2004.
[7] M. Chiang, S. H. Low, R. A. Calderbank, and J. C. Doyle, “Layering as optimization decomposition,” Proc. IEEE, Dec. 2006, to be published.
[8] R. Knopp and P. Humblet, “Information capacity and power control in single-cell multiuser communications,” in Proc. ICC, 1995, pp. 331–335.
[9] P. Bender, P. Black, M. Grob, R. Padovani, N. Sindhushayana, and A. Viterbi, “CDMA/HDR: A bandwidth-efficient high-speed wireless data service for nomadic users,” IEEE Commun. Mag., pp. 70–77, Jul. 2000.
[10] S. Borst and P. Whiting, “Dynamic rate control algorithms for HDR throughput optimization,” in Proc. IEEE INFOCOM, Alaska, Apr. 2001, pp. 976–985.
[11] ——, “The use of diversity antennas in high-speed wireless systems: Capacity gains, fairness issues, multi-user scheduling,” Bell Laboratories Technical Memorandum, 2001.
[12] X. Liu, E. K. P. Chong, and N. B. Shroff, “Opportunistic transmission scheduling with resource-sharing constraints in wireless networks,” IEEE J. Sel. Areas Commun., vol. 19, no. 10, pp. 2053–2064, Oct. 2001.
[13] ——, “A framework for opportunistic scheduling in wireless networks,” Comput. Netw., vol. 41, no. 4, pp. 451–474, Mar. 2003.
[14] A. Jalali, R. Padovani, and R. Pankaj, “Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system,” in Proc. IEEE Veh. Technol. Conf., 2000, pp. 1854–1858.
[15] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936–1948, Dec. 1992.
[16] M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, P. Whiting, and R. Vijayakumar, “Providing quality of service over a shared wireless link,” IEEE Commun. Mag., vol. 39, pp. 150–153, Feb. 2001.
[17] S. Shakkottai and A. Stolyar, “Scheduling for multiple flows sharing a time-varying channel: The exponential rule,” Translations of the AMS, 2001, a volume in memory of F. Karpelevich.
[18] ——, “Scheduling of a shared a time-varying channel: The exponential rule stability,” in Proc. INFORMS Appl. Prob. Conf., New York, Jul. 2001.
[19] R. Buche and H. J. Kushner, “Control of mobile communication systems with time-varying channels via stability methods,” IEEE Trans. Autom. Control, vol. 49, no. 11, pp. 1954–1962, Nov. 2004.
[20] A. L. Stolyar, “Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm,” Queueing Syst., vol. 50, no. 4, pp. 401–457, 2005.
[21] S. Borst, “User-level performance of channel-aware scheduling algorithms in wireless data networks,” IEEE/ACM Trans. Netw., vol. 13, no. 3, pp. 636–647, Jun. 2005.
[22] S. Shakkottai, “Effective capacity and QoS for wireless scheduling,” preprint, 2004.
[23] L. Ying, R. Srikant, A. Eryilmaz, and G. Dullerud, “A large deviations analysis of scheduling in wireless networks,” Trans. Inf. Theory, 2005, Earlier versions of the paper appeared in the IEEE CDC 2004, IEEE
CDC 2005 and IEEE ISIT 2006, submitted for publication.
[24] S. Sarkar and L. Tassiulas, “End-to-end bandwidth guarantees through fair local spectrum share in wireless ad-hoc networks,” in Proc. IEEE Conf. Decision and Control, Maui, HI, Dec. 2003, pp. 564–569.
[25] Y. Yi and S. Shakkottai, “Hop-by-hop congestion control over a wireless multi-hop network,” in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, pp. 2548–2558.
[26] Y. Xue, B. Li, and K. Nahrstedt, “Price-based resource allocation in wireless ad hoc networks,” in Proc. 11th Int. Workshop on Quality of Service, also Lecture Notes in Computer Science. New York: Springer-Verlag, vol. 2707, Monterey, CA, Jun. 2003, pp. 79–96.
[27] L. Chen, S. H. Low, and J. C. Doyle, “Joint congestion control and media access control design for wireless ad hoc networks,” in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 2212–2222.
[28] X. Lin and N. B. Shroff, “Joint rate control and scheduling in multihop wireless networks,” in Proc. IEEE Conf. Decision and Control, Paradise Island, Bahamas, Dec. 2004, pp. 1484–1489.
[29] ——, “The impact of imperfect scheduling on cross-layer rate control in multihop wireless networks,” in Proc. INFOCOM, Miami, FL, Mar. 2005, pp. 1804–1814.
[30] A. Eryilmaz and R. Srikant, “Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control,” in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 1794–1803.
[31] A. Eryilmaz and R. Srikant, “Joint congestion control, routing and MACfor stability and fairness in wireless networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1514–1524, Aug. 2006.
[32] I. Paschalidis, W. Lai, and D. Starobinski, “Asymptotically optimal transmission policies for low-power wireless sensor networks,” in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 2458–2469.
[33] M. J. Neely, E. Modiano, and C. Li, “Fairness and optimal stochastic control for heterogeneous networks,” in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 1723–1734.
[34] M. Johansson and L. Xiao, “Scheduling, routing and power allocation for fairness in wireless networks,” in Proc. IEEE Veh. Technol. Conf.–Spring, Milan, Italy, May 2004, pp. 1355–1360.
[35] T. Bonald and L. Massoulie, “Impact of fairness on Internet performance,” in Proc. ACM Sigmetrics, Cambridge, MA, Jun. 2001, pp. 82–91.
[36] J. Mo and J.Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 556–567, Oct. 2000.
[37] M. J. Neely, E. Modiano, and C. E. Rohrs, “Dynamic power allocation and routing for time varying wireless networks,” in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 745–755.
[38] R. L. Cruz and A. V. Santhanam, “Optimal routing, link scheduling and power control in multi-hop wireless networks,” in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 702–711.
[39] S. Toumpis and A. J. Goldsmith, “Capacity regions for wireless ad hoc networks,” IEEE Trans. Wireless Commun., vol. 2, no. 4, pp. 736–748, Jul. 2003.
[40] X. Lin and N. B. Shroff, “The impact of imperfect scheduling on cross-layer congestion control in wireless networks,” IEEE/ACM Trans. Netw., vol. 14, no. 2, pp. 302–315, Apr. 2006.
[41] G. Sharma, R. R. Mazumdar, and N. B. Shroff, “Maximum weighted matching with interference constraints,” in Proc. IEEE Int. Workshop Foundations and Algorithms ForWireless Networking, Pisa, Italy,Mar. 2006, pp. 70–74.
[42] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall, 1982. LIN et al.: A TUTORIAL ON CROSS-LAYER OPTIMIZATION IN WIRELESS NETWORKS 1463
[43] L. Xiao, M. Johansson, and S. Boyd, “Simultaneous routing and resource allocation via dual decomposition,” in Proc. 4th Asian Control Conf., Singapore, Sep. 2002, pp. 29–34.
[44] M. Chiang, “Balancing transport and physical layer in multihop wireless networks: Jointly optimal congestion and power control,” IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 104–116, Jan. 2005.
[45] ——, “Geometric programming for communication systems,” Foundations and Trends in Communications and Information Theory, vol. 2, no. 1–2, pp. 1–154, Jul. 2005.
[46] M. Arisoylu, T. Javidi, and R. L. Cruz, “End-to-end and MAC-layer fair rate assignment in interference limited wireless access networks,” in Proc. IEEE ICC , Istanbul, Turkey, Jun. 2006, to be published.
[47] X. Wang and K. Kar, “Cross-layer rate control for end-to-end proportional fairness in wireless networks with random access,” in Proc. ACM Mobihoc, Urbana-Champaign, IL, May 2005, pp. 157–168.
[48] J. W. Lee, M. Chiang, and R. A. Calderbank, “Jointly optimal congestion and contention control in wireless ad hoc networks,” IEEE Commun. Lett., vol. 10, no. 3, pp. 216–218, Mar. 2006.
[49] J. Zhang and D. Zheng, “A stochastic primal-dual algorithm for joint flow control andMAC design in multi-hop wireless networks,” in Proc. Conf. Inf. Sci. Syst., Princeton, NJ, Mar. 2006.
[50] L. Bui, A. Eryilmaz, R. Srikant, and X. Wu, “Joint congestion control and distributed scheduling in multihop wireless networks with a nodeexclusive interference model,” in Proc. IEEE INFOCOM, 2006.
[51] E. Leonardi, M. Mellia, F. Neri, and M. A. Marsan, “On the stability of input-queued switches with speed-up,” IEEE/ACM Trans. Netw., vol. 9, no. 1, pp. 104–118, Feb. 2001.
[52] X. Wu and R. Srikant, “Regulated maximal matching: A distributed scheduling algorithm for multi-hop wireless networks with node-exclusive spectrum sharing,” in Proc. IEEE Conf. Decision Control, 2005, pp. 5342–5347.
[53] T. Weller and B. Hajek, “Scheduling non-uniform traffic in a packetswitching system with small propagation delay,” IEEE/ACM Trans. Netw., pp. 813–823, Dec. 1997.
[54] J. Dai and B. Prabhakar, “The throughput of data switches with and without speedup,” in Proc. IEEE INFOCOM, 2000, pp. 556–564.
[55] X. Wu, R. Srikant, and J. R. Perkins, “Queue-length stability of maximal greedy schedules in wireless network,” in Proc. Inf. Theory Appl. Inaugural Workshop, Feb. 2006, Univ. California, San Diego.
[56] P. Chaporkar, K. Kar, and S. Sarkar, “Achieving queue length stability through maximal scheduling in wireless networks,” in Proc. Inf. Theory Appl. Inaugural Workshop, Feb. 2006, Univ. California,
San Diego.
[57] ——, “Throughput guarantees in maximal scheduling in wireless networks,” in Proc. 43rd Annu. Allerton Conf. Commun., Control, Comput., Monticello, IL, Sep. 2005.
[58] X. Lin and S. Rasool, “Constant-time distributed scheduling policies for ad hoc wireless networks,” IEEE CDC 2006. [Online]. Available: http://min.ecn.purdue.edu/~linx/papers.html, submitted for publication
[59] X. Lin, N. Shroff, and R. Srikant, “On the connection-level stability of congestion-controlled communication networks,” IEEE Trans. Inf. Theory, 2006, submitted for publication.
[60] P. R. Kumar and T. I. Seidman, “Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems,” IEEE Trans. Autom. Control, pp. 289–298, Mar. 1990.
[61] A. Rybko and A. Stolyar, “Ergodicity of stochastic processes describing the operation of open queueing networks,” Problems of Information Transmission, vol. 28, pp. 199–220, 1992, translated from
Problemy Peredachi Informatsii, vol. 28, no. 3, pp. 3–26, 1992.
[62] A. Eryilmaz, E. Modiano, and A. Ozdaglar, “Distributed control for throughput-optimality and fairness in wireless networks,” preprint, 2006.
[63] Y. Yi, G. de Veciana, and S. Shakkottai, “Learning contention patterns and adapting to load/topology changes in a MAC scheduling algorithm,” preprint, 2006.
[64] J.-W. Lee, R. R. Mazumdar, and N. B. Shroff, “Downlink power allocation for multi-class CDMA wireless networks,” in Proc. IEEE INFOCOM, 2002, vol. 3, pp. 1480–1489.
[65] ——, “Opportunistic power scheduling for multi-server wireless systems with minimum performance constraints,” in Proc. IEEE INFOCOM, Hong Kong, China, 2004, pp. 1067–1077.
[66] M. Chiang, S. Zhang, and P. Hande, “Distributed rate allocation for inelastic flows: Optimization frameworks, optimality conditions, and optimal algorithms,” in Proc. IEEE INFOCOM,Miami, FL, Mar. 2005,
DGIF_poster.pdf
