역압 라우팅

Backpressure routing

확률의 수학적 이론 내에서의 수학적 이론인 대기열 이론에서, 역압 라우팅 알고리즘은 랴푸노프 드리프트의 개념을 이용하여 확립된 최대 네트워크 처리량을 달성하는 대기열 네트워크를 중심으로 트래픽을 유도하는 방법이다.[1] 역압 라우팅은 각 작업이 네트워크의 여러 서비스 노드를 방문할 수 있는 상황을 고려한다. 각 작업이 단일 서비스 노드만 방문하는 최대 가중치 스케줄링의 확장이다.

소개

역압 라우팅은 정체 구배를 사용하여 멀티홉 네트워크를 통해 트래픽을 동적으로 라우팅하는 알고리즘이다. 이 알고리즘은 센서 네트워크, 모바일 애드혹 네트워크(MANETS), 무선 및 유선 구성 요소를 갖춘 이기종 네트워크를 포함한 무선 통신 네트워크에 적용할 수 있다.[2][3]

역압 원리는 제품 조립 시스템 및 처리 네트워크 연구와 같은 다른 분야에도 적용될 수 있다.[4] 이 기사는 여러 데이터 스트림에서 나오는 패킷이 도착하고 적절한 목적지에 전달되어야 하는 통신 네트워크에 초점을 맞추고 있다. 역압 알고리즘은 슬롯된 시간에 작동한다. 슬롯마다 인접 노드 간의 차등 백로그를 최대화하는 방향으로 데이터를 라우팅하려고 한다. 이것은 물이 압력 구배를 통해 파이프의 네트워크를 통해 흐르는 방법과 유사하다. 그러나 역압 알고리즘은 다중 통신망(다른 패킷이 다른 목적지를 가질 수 있는 경우)과 전송 속도를 (시간 변동) 옵션 집합에서 선택할 수 있는 네트워크에 적용할 수 있다. 백압 알고리즘의 매력적인 특징은 다음과 같다: (i) 최대 네트워크 처리량을 유도한다. (ii) 시간 변동을 일으키는 네트워크 조건에 대해 확실히 강력하다. (iii) 트래픽 도착률이나 채널 상태 확률을 알지 못하고 구현될 수 있다. 그러나 알고리즘은 큰 지연을 초래할 수 있으며, 간섭이 있는 네트워크에서 정확히 구현하기 어려울 수 있다. 지연을 줄이고 구현을 단순화하는 역압의 수정은 지연분산 역압 개선 아래에 설명되어 있다.

역압 라우팅은 주로 이론적인 맥락에서 연구되어 왔다. 실제로, 애드혹 무선 네트워크는 일반적으로 애드혹 온디맨드 거리 벡터 라우팅(AODV), 지리적 라우팅극히 기회주의적 라우팅(ExOR)과 같은 최단 경로 계산이나 네트워크 홍수에 기초한 대체 라우팅 방법을 구현해 왔다. 그러나, 역압의 수학적 최적성 특성은 남캘리포니아 대학과 노스캐롤라이나 주립대학의 무선 테스트베드에 대한 최근의 실험 실험에 동기를 부여했다.[5][6][7]

오리진스

원래의 역압 알고리즘은 타시울라와 에프레미데스에 의해 개발되었다.[2] 그들은 무작위 패킷 도착과 고정된 링크 선택 옵션 세트를 가진 멀티홉 패킷 무선 네트워크를 고려했다. 그들의 알고리즘은 최대 중량 링크 선택 단계와 차등 백로그 라우팅 단계로 구성되었다. Awerbuch와 Leighton에서 다변량 네트워크 흐름을 계산하기 위해 설계된 역압 관련 알고리즘이 개발되었다.[8] 역압 알고리즘은 이후 닐리, 모디아노, 로어스에 의해 확장되어 모바일 네트워크 스케줄링을 치료하게 되었다.[9] 역압은 랴푸노프 드리프트 이론을 통해 수학적으로 분석되며, 흐름 제어 메커니즘과 공동으로 사용하여 네트워크 효용 극대화를 제공할 수 있다.[10][11][3][12][13] (유틸리티 최적화 패널티 최소화를 포함한 Backpression도 참조)).

작동 방식

백 압력 라우팅은 네트워크의 대기열 백로그 합계를 한 번에서 다음 번으로 최소화하는 결정을 내리도록 설계된다. 이 기법의 정확한 수학적 발달은 나중의 절에 설명되어 있다. 이 절에서는 이 모델에 관한 일반적인 네트워크 모델과 역압 라우팅의 작동을 설명한다.

멀티홉 대기열 네트워크 모델

A 5-node multihop network
그림 1: 6노드 멀티홉 네트워크. 노드 사이의 화살표는 현재 이웃을 나타낸다.

N 노드가 있는 멀티홉 네트워크를 고려하십시오(N = 6인 예는 그림 1 참조). 네트워크는 슬롯타임 ,2, \}}}각 슬롯에서 새로운 데이터가 네트워크에 도착할 수 있으며, 라우팅 및 전송 스케줄링 결정은 모든 데이터를 적절한 목적지에 전달하기 위한 노력으로 이루어진다 노드 ,, }{\c\\{에 대해 지정된 데이터를 일반 c 데이터로 라벨링하도록 두십시오. 각 노드의 데이터는 상품에 따라 저장된다. For and , let be the current amount of commodity c data in node n, also called the queue backlog. 노드 내부의 대기열 백로그 클로즈업은 그림 2와 같다. ( )( ) 의 단위는 문제의 맥락에 따라 달라진다. 예를 들어, 백로그는 패킷의 정수 단위를 취할 수 있는데, 이것은 데이터가 고정 길이 패킷으로 분할되는 경우에 유용하다. 대신에, 그것은 비트의 실제 가치 있는 단위를 가질 수 있다. 1,… , ,N 대해 c(= 인 것으로 가정한다. 매 시간, 노드는 다른 사람에게 데이터를 전송할 수 있다. 한 노드에서 다른 노드로 전송되는 데이터는 첫 번째 노드의 대기열에서 제거되고 두 번째 노드의 대기열에 추가된다. 목적지로 전송되는 데이터는 네트워크에서 제거된다. 는 네트워크에 자연적으로 도착할 수도 있으며, n( )( t) n}^{(는 결국 노드 c에 전달되어야 하는 슬롯 t에서 노드 n에 도착하는 새 데이터의 양으로 정의된다.

( ) (를) 슬롯 t의 네트워크 over link (a,b)에서 사용하는 전송 속도로, 현재 슬롯의 노드 a에서 노드 b로 전송할 수 있는 데이터의 양을 나타낸다. ( 을 전송 속도 매트릭스로 한다. 이러한 전송 속도는 가능한 시간 변동 옵션의 집합 내에서 선택해야 한다. 구체적으로는, 네트워크는 시간변동 채널과 노드 이동성을 가질 수 있으며, 이것은 모든 슬롯에 그것의 전송 능력에 영향을 미칠 수 있다. 이것을 모델링하기 위해, S(t)가 전송에 영향을 미치는 슬롯 t에서 네트워크의 속성을 캡처하는 네트워크의 토폴로지 상태를 나타내도록 한다. S( ) 은(는) 위상 상태 S(t)에서 사용할 수 있는 전송 속도 매트릭스 옵션 집합을 나타낸다. 슬롯 t마다, 네트워크 컨트롤러는 S(t)를 관찰하고, 세트 ( t ) (\ 셋트 γ S ( ) 내에서 전송 속도 ( a )를 선택한다 각 슬롯 t에서 선택할( ( t) 매트릭스의 선택은 다음 하위섹션에 설명되어 있다.

이 시간 간격 네트워크 모델은 모든 슬롯 t의 전송 속도가 채널 상태 매트릭스와 전력 할당 매트릭스의 일반적인 기능에 의해 결정되는 경우를 위해 처음 개발되었다.[9] 서버 할당, 서브밴드 선택, 코딩 유형 등과 같은 다른 제어 결정에 의해 요금이 결정되는 경우에도 모델을 사용할 수 있다. 지원 가능한 전송 속도가 알려져 있고 전송 오류가 없다고 가정한다. 다중 수신기 다양성을 통해 무선 방송 이점을 이용하는 네트워크를 포함하여 확률론적 채널 오류가 있는 네트워크에 확장된 역압 라우팅 형식을 사용할 수 있다.[1]

역압 제어 결정

모든 슬롯 t 역압 제어기는 S(t)를 관찰하고 다음 3단계를 수행한다.

  • 첫째, 각 링크(a,b)에 대해 사용할 t ( ){\를 선택한다.
  • 다음으로 ( 행렬에서 사용할(a b(t ) {\를 결정한다.
  • 마지막으로, 링크(a,b)를 통해 전송할 상품 c ,( a( ){\의 양을 결정한다(최대 ( )

최적의 물품 선택

각 노드 a는 자체 대기열 백로그와 현재 인접 네트워크의 백로그를 관찰한다. 노드 a현재 인접 네트워크는 현재 슬롯에서 0이 아닌 전송 속도 ( ) 을(를) 선택할 수 있는 노드 b이다. 따라서 이웃은 ( t로 결정되는데 극단적인 경우 노드는 다른 N - 1의 모든 노드를 이웃으로 가질 수 있다. 그러나 특정 지리적 거리 이상으로 분리된 노드 간 전송을 금지하거나 특정 임계값보다 낮은 전파 신호 강도를 갖는 ( 세트를 사용하는 것이 일반적이다. 따라서 이웃의 수가 N - 1보다 훨씬 적은 것이 일반적이다. 그림 1의 예는 노드 5가 인접 4와 6을 갖도록 링크 연결을 통해 인접 항목을 보여준다. 이 사례는 이웃 간의 대칭적 관계(따라서 5가 이웃 4인 경우 4가 이웃 5인 경우)를 제시하지만, 일반적으로 이럴 필요는 없다.

지정된 노드의 인접 네트워크 집합은 현재 슬롯의 전송에 사용할 수 있는 송신 링크 집합을 결정한다. 각 발신 링크(a,b)에 대해 최적의 상품 c ( ) 는 상품 { 1,, N 로 정의되어 다음과 같은 차등 미분백로그 양을 최대화한다.

최적의 상품을 선택하는데 있어서 어떠한 관계도 임의로 깨진다.

A closeup of nodes 1 and 2. The optimal commodity to send over link (1,2) is the green commodity.
그림 2: 노드 1과 노드 2의 클로즈업. 링크(1,2)를 보내기에 최적의 상품은 녹색 상품이다. 다른 방향(오버링크(2,1))으로 보낼 최적의 상품은 파란색 상품이다.

예는 그림 2에 나와 있다. 이 예에서는 각 큐에 현재 빨간색, 녹색, 파란색 3개 상품만 있다고 가정하며, 이러한 상품들은 패킷의 정수 단위로 측정된다. 방향 링크(1,2)를 중심으로 차등 백로그는 다음과 같다.

따라서 슬롯 t에서 링크(1,2)를 전송하기 위한 최적의 물품은 녹색 물품이다. 반면 슬롯 t의 리버스 링크(2,1)를 통해 보낼 최적의 상품은 파란색 상품이다.

μab(t) 행렬 선택

각 링크(a,)에 대해 최적의 상품이 결정되면, 네트워크 컨트롤러는 다음의 W ( t )을 계산한다

중량 ( ) 은 0으로 최대화된 링크(a,b)에 대한 최적 물품과 관련된 차등 백로그 값이다. 그런 다음 제어기는 다음과 같은 최대 중량 문제에 대한 해결책으로 전송 속도를 선택한다.

최대 가중치 결정의 예로서, 현재 슬롯 t에서 6 노드 네트워크의 각 링크에 있는 차등 백로그가 다음과 같이 주어지는 W a ( )}(t을(를) 링크한다고 가정한다.

설정된 S( ) 은(는) 가능한 전송 속도 매트릭스를 셀 수 없을 정도로 무한히 포함할 수 있지만, 단순성을 위해 현재 위상 상태가 가능한 4가지 선택만 허용한다고 가정하십시오.

현재 위상 상태 S(t)에서 가능한 4개의 전송 속도 선택 그림. 옵션 (a) = 의 전송 속도로 단일 링크(1,5)를 활성화한다 다른 모든 옵션은 두 개의 링크를 사용하며, 각각의 활성화된 링크에서 전송 속도는 각각 1이다.

이 네 가지 가능성은 매트릭스 형태로 다음과 같이 표현된다.

이러한 가능성 하에서 노드 6은 송신하거나 수신할 수 없다는 점을 유념하십시오. 이는 노드 6이 현재 통신 범위를 벗어났기 때문에 발생할 수 있다. 네 가지 가능성 각각에 대한 비율의 가중 합계는 다음과 같다.

  • 선택 (a): ( ) a ()= .
  • 선택 (b): W ( t ) ( )= 1
  • 선택(c): W ( t) ()= \sum
  • 선택 (d): ( t ) ( )= .

최대 중량이 12인 동점이 있기 때문에 네트워크 컨트롤러는 옵션 또는 옵션 중 하나를 선택하여 임의로 동점을 깰 수 있다.

라우팅 변수 마무리

이제 각 링크에 대해 최적의 상품 a t( ) 이 결정되었고, 전송률μ a ( ) ab도 결정되었다고 가정하자. 특정 링크(a,b)의 최적 물품에 대한 차등 백로그가 음수인 경우, 현재 슬롯의 이 링크를 통해 데이터가 전송되지 않는다. 그렇지 않으면 네트워크는 이 를 통해 상품 a b( ) 단위를 b ( t) 데이터 전송을 제안한다. 이는 각 링크(a,b) 및 각 물품 c에 대해 라우팅 변수 ) a (c () _{ab을 정의함으로써 이루어진다. 여기서:

( )( ) 의 값은 슬롯 t의 링크(a,b)를 통해 일반 c 데이터에 제공되는 전송 속도를 나타낸다. 그러나 노드에는 모든 송신 링크에서 제공되는 요금으로 전송을 지원할 수 있는 특정 상품이 충분하지 않을 수 있다. 이는 다음과 같은 경우 노드 n과 상용 c의 슬롯 t에서 발생한다.

이 경우 ( )( t) n}^{( 데이터를 모두 전송하고, null 데이터를 사용하여 제공된 비율의 사용되지 않은 부분을 채우며, 실제 데이터와 null 데이터를 해당 송신 링크(제공 비율에 따라)에 임의로 할당한다. 이것을 대기열 과소 흐름 상황이라고 한다. 그러한 저유량은 네트워크의 처리량이나 안정성 속성에 영향을 미치지 않는다. 직관적으로 이는 전송 노드의 백로그량이 적을 때만 언더플로우가 발생하기 때문에 노드가 불안정해질 위험이 없다는 것을 의미한다.

지연 개선

역압 알고리즘은 사전 지정된 경로를 사용하지 않는다. 경로는 동적으로 학습되며, 패킷마다 다를 수 있다. 특히 시스템이 목적지를 향해 데이터를 밀기에 충분한 압력이 없을 정도로 가볍게 적재된 경우 지연이 매우 클 수 있다. 예를 들어, 한 패킷이 네트워크에 들어가고 다른 패킷은 전혀 입력되지 않는다고 가정해 보십시오. 이 패킷은 압력 구배가 쌓이지 않기 때문에 네트워크를 통과하는 루피한 걸음을 할 수 있고 목적지에 도착하지 않을 수 있다. 이는 네트워크가 언제든지 최대 한 패킷을 가지고 있기 때문에 사소한 안정(도달률 0 달성, 도착률과 동일)이기 때문에 역압의 처리량 최적성이나 안정성 속성과 모순되지 않는다.

사전 지정된 경로 집합에 대해 역압을 구현할 수도 있다. 이는 용량 영역을 제한할 수 있지만 주문형 배송 및 지연을 개선할 수 있다. 용량 영역에 영향을 주지 않고 지연을 개선하는 또 다른 방법은 바람직한 방향으로 가중치를 연결시키는 향상된 버전을 사용하는 것이다.[9] 그러한 편향의 시뮬레이션은 상당한 지연 개선을 보여주었다.[1][3] 역압은 대기열에서 FIFO(선입선출) 서비스를 필요로 하지 않는다는 점에 유의하십시오. LIFO(Last-in-First-Out) 서비스는 처리량에 영향을 주지 않으면서 대부분의 패킷에 대한 지연을 획기적으로 개선할 수 있다는 것이 관찰되었다.[7][14]

분산 역압

전송 속도 a( )를 선택한 후에는 라우팅 결정 변수 a ( )( t) ( ) {\{ab}^{를 간단한 분산 방식으로 계산할 수 있으며, 여기서 각 노드에는 대기열 백로그 차이에 대한 지식만 필요하다.그리고 그 이웃들. 단, 전송 속도를 선택하려면 Eqs. (1)-(2)의 최대 중량 문제에 대한 해결책이 필요하다. 채널이 직교하는 특별한 경우, 알고리즘은 자연적으로 분산된 구현을 가지며 각 노드에서 별도의 결정으로 감소한다. 그러나 최대 중량 문제는 채널 간 간섭이 있는 네트워크에 대한 중앙집중식 제어 문제다. 중앙집권적인 방법으로도 해결하기가 매우 어려울 수 있다.

신호 대 잡음+간섭 비율(SINR)에 의해 결정되는 링크 속도를 가진 간섭 네트워크에 대한 분산 접근법은 무작위화를 사용하여 수행할 수 있다.[9] 각 노드는 임의로 모든 슬롯 t 전송을 결정한다(현재 전송할 패킷이 없는 경우 "null" 패킷 전송). 실제 전송 속도 및 보낼 해당 실제 패킷은 2단계 핸드셰이크로 결정된다. 첫 번째 단계에서 임의로 선택한 송신기 노드는 실제 전송에 비례하는 신호 강도로 파일럿 신호를 전송한다. 두 번째 단계에서, 모든 잠재적 수신기 노드는 결과적인 간섭을 측정하고 그 정보를 송신기로 다시 보낸다. 그러면 모든 발신 링크(,b에 대한 SINR 수준이 모든 노드 n에 알려지며, 각 노드 n은 이 정보를 기반으로 b( t) ((){nb}^( 변수를 결정할 수 있다. 결과적인 처리량이 반드시 최적의 것은 아니다. 단, 임의의 전송 프로세스는 채널 상태 프로세스의 일부로 볼 수 있다(과소 흐름의 경우, 채널 상태 프로세스가 과거의 결정에 좌우되지 않도록 null 패킷이 전송되는 경우). 따라서 이 분산 구현의 결과 처리량은 그러한 무작위 전송을 사용하는 모든 라우팅 및 스케줄링 알고리즘의 등급에 걸쳐 최적이다.

대체 분산 구현은 대략 다음과 같은 두 종류로 분류할 수 있다. 알고리즘의 첫 번째 등급은 최대 중량 문제에 대한 일정한 곱셈 인자 근사치를 고려하며, 일정한 요인 처리량 결과를 산출한다. 알고리즘의 두 번째 등급은 시간에 따른 최대 중량 문제에 대한 최신 솔루션을 기반으로 최대 중량 문제에 대한 부가적 근사치를 고려한다. 이 두 번째 클래스의 알고리즘은 적절한 가정 하에서 최대 처리량을 달성할 수 있지만 정적 채널 조건과 더 긴 (종종 비-다항식) 수렴 시간을 필요로 하는 것으로 보인다.[15][4][13] 부가적인 근사치는 종종 구식 대기열 백로그 정보로 구현했을 때 백압의 최적성을 입증하는 데 유용하다(Neely 텍스트의 연습 4.10 참조).[13]

랴푸노프 표류를 통한 수학적 구조

이 절에서는 대기열 백로그의 제곱합이 슬롯에서 다음 슬롯으로 변경되는 것을 탐욕스럽게 최소화하는 자연적인 결과로서 백압 알고리즘이 어떻게 발생하는지를 보여준다.[9][3]

의사 결정 제약 조건 및 대기열 업데이트 방정식 제어

의 섹션에서 설명한 대로 N 노드가 있는 멀티홉 네트워크를 고려하십시오. 슬롯 t마다 네트워크 컨트롤러는 토폴로지 상태 S(t)를 관찰하고 전송 속도 a ( ){\(\ _ 라우팅 변수 a ( (\ _{ab를 선택한다.

이러한 라우팅 변수가 결정되면 전송이 이루어지며(필요한 경우 유휴 채우기 사용), 결과적으로 발생하는 대기열 백로그는 다음을 충족한다.

where is the random amount of new commodity c data that exogenously arrives to node n on slot t, and is the transmission rate allocated to commodity c traffic on link (n,b) on slot t. ( )( ) 이(가) 슬롯 t의 링크(a,b)에서 실제로 전송되는 일반 c 데이터의 양보다 클 수 있다는 점에 유의하십시오. 노드 n에 충분한 백로그가 없을 수 있기 때문이다. 이와 같은 이유로 Eq. (6)는 동등하기 보다는 불평등이다. 왜냐하면 a= ( n(t ) an}^{ 슬롯 n 노드에 대한 실제 내생성 도착보다 클 수 있기 때문이다. Eq. (의 중요한 특징은 μ a ( c) ( )ab}^{의 결정 변수를 백로그와 독립적으로 선택해도 유지한다는 것이다.

대기열이 목적 데이터를 저장하지 않으므로 모든 슬롯 t {,…,N} c\\{에 대해 )= 0 인 것으로 가정한다.

랴푸노프 표류

( t)=( ( )( t)) 을(를) 현재 대기열 백로그의 매트릭스로 정의하십시오. 랴푸노프 함수라고 하는 다음과 같은 비음수 함수를 정의한다.

이는 대기열 백로그의 제곱합을 합한 것이다(나중 분석 시 편의를 위해 1/2로 곱함). The above sum is the same as summing over all n, c such that because for all and all slots t.

조건부 Lyapunov 드리프트 ( ) 은(는) 다음과 같이 정의된다.

다음 부등식은 0 0 0{\0}, 0 {\ 0에 대해 유지된다는 점에 유의하십시오

By squaring the queue update equation (Eq. (6)) and using the above inequality, it is not difficult to show that for all slots t and under any algorithm for choosing transmission and routing variables and :[3]

여기서 B는 도착의 두 번째 순간과 전송 속도의 최대 가능한 두 번째 순간에 따라 달라지는 유한 상수다.

합계를 전환하여 드리프트 바인딩 최소화

The backpressure algorithm is designed to observe and S(t) every slot t and choose and to minimize the right-hand-side of the drift bound Eq. (7). B는 상수 (c)이고 상수이므로 이는 다음을 최대화하는 데 해당한다.

최대화 결정을 밝히기 위해 유한 총액이 기대치를 통과하여 추진된 경우. 기회적으로 최대화한다는 원칙에 의해, 된 Q( t) ( ) 의 내부 기능을 최대화하여 위의 기대치를 최대화한다. 따라서 다음과 같은 제약조건을 하여 (μ a b ( t ) 하고 다음을 최대화한다.

어떤 결정이 위와 같은 것을 최대화하는지 즉각적으로 알 수 없다. 이것은 합계를 바꾸면 조명할 수 있다. 실제로 위의 표현은 다음과 같다.

중량 ( )( t)- () ( ) ( t) {\a}^{은 노드 a와 b 사이에 있는 상품 c의 현재 차등 백로그라고 불린다. 그 아이디어는 위의 가중 합계를 최대화하기 위해 결정 변수 a ( ) (t)를 선택하는 것이다. 여기서 가중치는 차등 백로그다. 직관적으로 이것은 더 큰 차등 백로그의 방향으로 더 큰 비율을 할당하는 것을 의미한다.

분명히 사람 μ;0}. 추가, μ 특정 링크(a, b){\displaystyle(a,b)}을 위한 b(t){\displaystyle \mu_{ 어릴 때}(t)} 주어질 때마다 Q(c)(t)− Qb(c)(t)<0{\displaystyle Q_{}(t)-Q_ᆼ^ᆽ(t)< b(c)(t))0{\displaystyle \mu_{ 어릴 때}(t)=0}을 선택해야 한다., Eqs. (3)-(5)에 따라 최적의 (c) ( ){\ab}^{( 선택 항목은 다음과 같이 결정됨을 보여주는 것은 어렵지 않다. 먼저 링크(a,b)에 대한 차등 백로그를 최대화하는 상품 (,… , 을(를) 찾으십시오. 최대화 차등 백로그가 링크(a,b)에 대해 음수인 경우, 모든 상품 ,… ,} 대해 ( ( = }^{(c을 링크 (a,b)에 할당하십시오. 그렇지 않으면 전체 링크 속도 ( ) ( ){\}(t를 상품 하고, 0 rate를 상품 c a t( t ) 0 rate를 이 링크의 다른 모든 상품에 할당한다. 이 선택과 함께 다음과 같다.

여기서 ( t) 은 슬롯 t의 링크(a,b)에 대한 최적의 물품(b)의 차등 백로그(0으로 최대):

\에서 a ( ( )_{S(t)}}}만 선택하면 된다 이는 다음 사항을 해결함으로써 이루어진다.

위의 문제는 Eqs. (1)-(2)의 최대 중량 문제와 동일하다. 백압 알고리즘( a ( 에 대한 최대 중량 결정을 사용한 다음 위에서 설명한 최대 차등 백로그를 통해 라우팅 변수 를 선택한다.

백압 알고리즘의 주목할 만한 특성은 관측된 토폴로지 상태 S(t)와 해당 슬롯에 대한 대기열 백로그 Q 에만 근거하여 모든 슬롯 t를 탐욕스럽게 작동한다는 것이다. 따라서 도착률( 또는 위상 상태 확률 = P [ (t) = {\ _

성과분석

이 절은 역압 알고리즘의 처리량 최적성을 입증한다.[3][13] 단순성을 위해 비 I.i.d 시나리오(아래 비 I.i.d 작동범용 스케줄링 참조)에서 동일한 알고리즘이 작동하는 것으로 보일 수 있지만 이벤트가 독립적이고 슬롯에 걸쳐 동일한 분산(i.d.)이 되는 시나리오를 고려한다.

동적 도착

t의 외부 도착 행렬이 되도록 (A ( )( t) )이(가) 되도록 한다. 이 매트릭스가 유한한 두 번째 모멘트와 수단의 슬롯에 대해 독립적이고 동일한 분포(즉, i.d)라고 가정한다.

()= 을(를) 모든 c , {\\{ 대해 자체적으로 예정된 데이터가 도착하지 않는 것으로 가정한다. 따라서 도착률 매트릭스(){\(\ 음이 아닌 실수의 time N 행렬이며 대각선에 0이 표시된다.

네트워크 용량 영역

Assume the topology state S(t) is i.i.d. over slots with probabilities (if S(t) takes values in an uncountably infinite set of vectors with real-valued entries, then is a probability distribution, not a probability mass function). 네트워크에 대한 일반 알고리즘은 모든 슬롯 t를 관측하고 Eqs. (3)-5의 제약조건에 따라 전송률( a ( ) (\ 을 선택한다. 네트워크 용량 영역 은(는) 네트워크를 안정화하는 알고리즘이 존재하는 모든 도착 속도 매트릭스 (){\의 집합이 닫히는 것이다. 모든 대기열의 안정성은 네트워크로 전송되는 트래픽의 총 입력 속도가 목적지에 전달되는 데이터의 총 입력 속도와 동일하다는 것을 의미한다. It can be shown that for any arrival rate matrix in the capacity region , there is a stationary and randomized algorithm that chooses decision variables and )따라서 대기열 백로그와는 독립적으로) 모든 슬롯 t는 모든 yields 에 대해 다음을 산출한다[9][13]

오직 S(t)에만 근거한 결정을 하는 고정적이고 무작위화된 알고리즘을 S 전용 알고리즘이라고 한다. 있는ϵ를 그것은 자주 그(λ n(c)){\displaystyle(\lambda_{n}^{(c)}으로 추정하는 것)}{\Lambda\displaystyle}Λ에 인테리어, 0{\displaystyle \epsilon>0}가(λ n(c)+ϵ 1n(c))∈Λ{\displaystyle(\lambda_{n}^{(c)}+\epsilon 1_{n}^{(c)})\in \Lambda}, 유용하다.where ( 는) 1이고, 그 경우는 경우, 모든 c{\에 대해 다음을 산출하는 S 전용 알고리즘이 있다

기술적 요건으로서, 전송률의 두 번째 순간 a( ) 이러한 속도를 선택하는 알고리즘에 따라 유한하다고 가정한다. 은 한정된 최대 속도 x 가 있는 경우 사소한 것으로 유지된다

S 전용 알고리즘과 비교

Because the backpressure algorithm observes and S(t) every slot t and chooses decisions and to minimize the right-hand-side of the drift bound Eq. (7), we have:

여기서( a ( t)) (\( a ( c )( {\(\ _은 무작위 결정을 포함하여 Eqs. (3)-(5를 만족하는 모든 대안적 결정이다.

이제 에 (() ∈ { { { { { { { { 을 가정해 보십시오. 그러면 Eq. (8)를 만족하는 S 전용 알고리즘이 존재한다. 이것을 Eq. (10)의 오른쪽에 연결하고 이 S 전용 알고리즘에 따라 ( ) 이(가) 주어진 조건부 기대치가 무조건적인 기대치와 동일하다는 점에 주목하십시오(S(t)는 슬롯에 대한 I.i.d이고 S 전용 알고리즘은 현재 대기열 백로그 수율과 독립적이기 때문이다).

따라서 2차 랴푸노프 함수의 드리프트는 모든 슬롯 t에 대해 상수 B보다 작거나 같다. 이러한 사실은 대기열 도착이 두 번째 순간으로 한정되었다는 가정과 함께 모든 네트워크 대기열에 대해 다음을 암시한다.[16]

For a stronger understanding of average queue size, one can assume the arrival rates are interior to , so there is an such that Eq. (9) holds for some alternative S-only algorithm. Eq. (9)를 Eq. (10) 산출물의 오른쪽에 꽂으면:

여기서 즉시 다음을 얻는다(참조[3][13]).

용량 영역 경계까지의 거리 zero 이(가) 0이 되면 평균 대기열 크기가 증가한다. 이는 평균 대기열 크기가 1/1/1/1/1/{\ 및 서비스 속도 에 비례하는 단일 M/M/1 대기열과 동일한 정성적 성능이며 여기서 평균 대기열 는 μ = = = -displaystym - \

위 공식의 확장

비 I.I.D 운영 및 범용 스케줄링

위의 분석에서는 단순성을 위한 I.I.D 속성을 가정한다. 그러나 동일한 역압 알고리즘이 비 I.i.d 상황에서 강하게 작동한다는 것을 보여줄 수 있다. 도착 프로세스와 토폴로지 상태가 에고딕적이지만 반드시 i.는 아닐 때, 역압은 { { { { { { { { { { \(\}^{(c}}\c. 보다 보편적인 스케줄링 접근법을 사용하여 임의의 안정성과 최적성을 제공하는 것으로 나타났다[9] (비에너지) 샘플 경로.[17]

유틸리티 최적화 및 패널티 최소화를 통한 백 압력

역압은 표류+페널티 기법을 통한 흐름 제어와 함께 작용하는 것으로 나타났다.[10][11][3] 이 기술은 탐욕스럽게 드리프트와 가중치 있는 벌점 표현의 합을 최대화한다. 벌칙은 성능 상쇄를 결정하는 파라미터 V에 의해 가중된다. 이 기법은 평균 지연이 O(V)인 동안 처리량 효용이 최적성의 O(1/V) 이내에 있음을 보장한다. 따라서 효용성은 평균 지연에 상응하는 절충으로 최적성에 가깝게 임의로 밀릴 수 있다. 평균 전력 최소화와[18] 더 일반적인 네트워크 속성의 최적화를 위해 유사한 특성이 나타날 수 있다.[13]

유체 모델 분석,[12] 공동 유체 분석 및 라그랑주 곱셈 분석,[19] 볼록 최적화,[20] 확률적 그라데이션 등을 사용하여 대기열을 안정화하는 대안 알고리즘이 개발되었다.[21] 이러한 접근방식은 O(1/V), O(V) 효용 지연 결과를 제공하지 않는다.

참고 항목

참조

  1. ^ Jump up to: a b c d M. J. 닐리와 R. Urgaonkar, "Multi-Receiver Diversity가 있는 무선 네트워크의 최적 백압 라우팅," AdHort Networks (Elsevier), vol. 7, 5, 페이지 862-881, 2009년 7월.
  2. ^ Jump up to: a b L. 타시울라와 A. Ephremides, "멀티홉 무선 네트워크의 최대 처리량을 위한 제한된 대기열 시스템의 안정성 특성, 자동 제어에서의 IEEE 트랜잭션, vol. 37, 12, 1936-1948, 1992년 12월.
  3. ^ Jump up to: a b c d e f g h L. Georgiadis, M. J. Neely, L. Tassiulas, "무선 네트워크의 자원 할당 및 계층 간 제어," 네트워킹의 기초동향, 제1권, 제1권, 페이지 1-149, 2006.
  4. ^ Jump up to: a b L. Jiang과 J. Walrand. Morgan & Claypool, 2010년 무선 및 처리 네트워크에 대한 스케줄링정체 제어.
  5. ^ A. Sridharan, S. Moeller, B. 크리슈나무나차리, 6번 째 인틀, "랴푸노프 드리프트를 이용한 분산 요금제어를 무선 센서 네트워크에 현실로 만든다." 2008년 4월 모바일, 애드혹 및 무선 네트워크에서의 모델링 및 최적화에 관한 심포지엄.
  6. ^ A. 워리어, S. 얀나키라만, S. 하, 그리고 나. 이승만, "DiffQ: 무선 네트워크를 위한 실용적인 차등 백로그 정체 제어," Proc. IEEE INFOCOM, 브라질 리우데자네이루, 2009.
  7. ^ Jump up to: a b S. Moeller, A. Sridharan, B. Krishnamachari, O. 쐐발리, "루트 없는 호통: Backpressure Collection Protocol," Proc. 9번째 ACM/IEEEE Intl. 2010년 4월, 센서 네트워크(IPSN)의 정보 처리에 관한 설명.
  8. ^ Awerbuch와 T. Leighton, "다중 불편 유동에 대한 간단한 로컬-컨트롤 근사 알고리즘," Proc. 34번째 IEEE Conf. 1993년 10월 컴퓨터 과학의 기초 위에서.
  9. ^ Jump up to: a b c d e f g M. J. Neely, E. Modiano, C. E. Rohrs, "시간 변화무쌍한 무선 네트워크를 위한 동적 전력 할당 및 라우팅," IEEE 저널, 23권, 1, 페이지 89-103, 2005년 1권.
  10. ^ Jump up to: a b M. J. 닐리 시간 변화 채널을 가진 위성 및 무선 네트워크를 위한 동적 전력 할당 및 라우팅. 2003년 11월 LIDS 매사추세츠 공과대학 박사학위 논문.
  11. ^ Jump up to: a b M. J. 닐리, E. 모디아노, C. Li, "이종 네트워크의 공정성과 최적 확률적 제어," Proc. IEEE INFOCOM, 2005년 3월.
  12. ^ Jump up to: a b A. Stolyar, "안정성에 따른 대기열 네트워크 유틸리티 최대화: 탐욕스러운 원시-듀얼 알고리즘", 대기열 시스템, 제50권, 제4권, 페이지 401-457, 2005.
  13. ^ Jump up to: a b c d e f g M. J. 닐리 Morgan & Claypool, 2010년 통신 및 대기열 시스템에 대한 응용을 통한 확률적 네트워크 최적화.
  14. ^ L. Huang, S. Moeller, M. J. Neely, B. 크리슈나마차리, "LIFO-백압, 거의 최적 효용 달성-딜레이 트레이드오프," 프로크. WiOpt, 2011년 5월.
  15. ^ E. 모디아노, D. Shah와 G. Zussman, "가십을 통한 무선 네트워크 처리량 극대화" Proc. ACM SIGMETRYS, 2006.
  16. ^ M. J. Neely, "Lyapunov Optimization을 통한 Queu 안정성과 확률 1 수렴," Journal of Applied Mathics, vol. 2012, doi:10.1155/2012/831909.
  17. ^ M. J. Neely, "임의 트래픽, 채널 및 모빌리티가 있는 네트워크에 대한 범용 스케줄링," Proc. IEEE Conf. 2010년 12월, 애틀랜타, GA, 의사결정 및 통제(Cdecision and Control, CDC, Atlanta, GA, 2010).
  18. ^ M. J. Neely, "시간 변화 무선 네트워크를 위한 에너지 최적 제어", 정보 이론에 관한 IEEE 거래, vol. 52, no. 7, 페이지 2915-2934, 2006년 7월
  19. ^ A. 에릴마즈와 R. Srikant, "Query-Length-Based Scheduling and Bloom Control을 이용한 무선 네트워크에서의 공정한 자원 할당," Proc. IEEE INFOCOM, 2005년 3월.
  20. ^ X. 린과 N. B. Shroff, 43번째 IEEE Conf의 "멀티홉 무선 네트워크의 공동 속도 제어 및 스케줄링," Proc. 2004년 12월, 바하마 파라다이스 섬의 결정과 통제에 관하여.
  21. ^ J. W. Lee, R. R. Mazumdar, N. B. Shroff, "다이나믹 멀티시저 무선 시스템을 위한 기회주의적 전원 스케줄링," IEEE 무선 통신 거래 5, no.6, 페이지 1506–155, 2006년 6월.

일차 출처

  • L. 타시울라와 A. Ephremides, "멀티홉 무선 네트워크에서 최대 처리량을 위한 제한된 대기열 시스템의 안정성 속성 및 스케줄링 정책," IEEE 자동 제어에 관한 거래, vol. 37, no. 12, 페이지 1936–1948, 1992년 12월.
  • L. Georgiadis, M. J. Neely, L. Tassiulas, "무선 네트워크의 자원 할당 및 계층 간 제어," 네트워킹의 기초 동향, 제1권, 제1권, 페이지 1–149, 2006.
  • M. J. 닐리 Morgan & Claypool, 2010년 통신 및 대기열 시스템에 대한 응용을 통한 확률적 네트워크 최적화.