물리적 모델 기반 혼합 소거 네트워크의 용량 스케일링 법칙

Throughput Scaling Law of Hybrid Erasure Networks Based on Physical Model

  • cc icon
  • ABSTRACT

    다수의 중계기가 균등하게 분포된 무선 소거 네트워크의 용량 스케일링 법칙을 분석함으로써 인프라 구조 사용시 이득을 보인다. 가정하는 네트워크 하에서 소거 확률을 적절히 모델링함에 근거하여, 혼합 소거 네트워크에서 취득 가능한 네트워크 용량을 보인다. 보다 구체적으로, 지수 감쇠 모델 및 다항 감쇠 모델 이렇게 두 가지 물리적 모델을 사용한다. 중계기 도움이 없는 다중 홉 전송, 중계기 도움을 받는 다중 홉 전송 이렇게 두 가지 존재하는 기술을 사용하여 취득 용량을 분석한다. 유도된 용량 스케일링 법칙은 두 가지 물리적 모델 모두에 대해 노드 수 및 중계기의 수에 의존함을 확인한다.


    The benefits of infrastructure support are shown by analyzing a throughput scaling law of an erasure network in which multiple relay stations (RSs) are regularly placed. Based on suitably modeling erasure probabilities under the assumed network, we show our achievable network throughput in the hybrid erasure network. More specifically, we use two types of physical models, a exponential decay model and a polynomial decay model. Then, we analyze our achievable throughput using two existing schemes including multi-hop transmissions with and without help of RSs. Our result indicates that for both physical models, the derived throughput scaling law depends on the number of nodes and the number of RSs.

  • KEYWORD

    취득 용량 스케일링 법칙 , 소거 확률 , 혼합 소거 네트워크 , 인프라 구조 , 다중 홉 , 물리적 모델

  • I. 서 론

    [1]에서 Gupta와 Kumar 연구 그룹은 부가 가우시언(Gaussian) 잡음을 가진 거대 무선 네트워크에서 합 용량 스케일링을 소개하고 분석하였다. [1]에서는 단위 면적에 랜덤하게 분포된 n개의 source-destination (S-D)쌍을 갖는 네트워크에 대해 전체 용량이 으로 스케일함을 보였다. 이 용량 스케일링은 다중 홉(multi-hop) 기술을 사용하여 취득된다. 최근 연구에서는 계층적 협력 (hierarchical cooperation) 기술을 사용함으로써 가우시언 네트워크 모델에서 거의 선형적인 용량, 즉, 임의의 작은 ε > 0에 대해 θ(n1-ε)이 취득 가능함을 보였다 [2]. 무선 네트워크의 용량을 선형 스케일링으로 개선하기 위해, 무선 애드 혹 노드뿐만 아니라 인프라 구조 노드 (또는 동일한 의미로 중계기(relay station) 노드)로 구성된 혼합 네트워크에 대한 연구가 [3-4]에서 역시 수행되었는데, 이 때 중계기는 서로 고 대역폭 (또는 고 용량)으로 연결되어 있다고 가정하였다. 혼합 네트워크에서는 중계기의 수 m에 따른 선형 용량 스케일링을 취득하기 위해 m이 특정 임계값 을 넘어야하는 엄격한 조건이 요구된다. [5]에서는 각각 의 중계기에서 다중 안테나를 사용하는 더욱 일반화된 혼합 네트워크에서 최적 용량 스케일링이 분석되었는 데, 취득 용량은 중계기 기반 단일 홉, 중계기 기반 다중 홉, 순수 다중 홉 전송 [1], 그리고 계층적 협력 통신 [2] 중 하나를 선택함으로써 얻을 수 있음을 보였다.

    게다가, 네트워크의 또 다른 근본적인 종류로써, 무선 소거 네트워크가 소개되었다 [6]. [6]에서는 용량 영역 (capacity region)의 정확한 규명이 몇몇 간단한 멀티캐스트 문제에 대해 이루어졌다. 또한, [7-9]에서는 S-D 쌍이 랜덤하게 선택된다고 가정할 때, 부가 간섭을 갖는 소거 네트워크에 다수 개의 노드가 존재하는 보다 일반적인 시나리오에 대해 스케일링 법칙 측면에서 용량에 대한 분석이 수행되었다. 이러한 소거 네트워크 모델은 모든 정보 전송이 패킷화되는 그러한 Automatic Repeat reQuest (ARQ)와 같은 기능을 가지는 시스템에 적합하다 할 수 있다.

    본 논문에서는, m개의 균등하게 위치한 인프라 구조 노드를 가진 혼합 소거 네트워크에 대한 용량 스케일링 법칙을 분석한다. 구체적으로 단위 노드 밀도의 확장 네트워크 [2], [5], [10]에서 취득 가능한 용량을 보인다. 가우시언 네트워크 모델에서 중계기 지원에 대한 깊이 있는 연구가 수행되어 온 반면, 소거 네트워크에 대한 그러한 시도는 현재까지 시도되어 온 바가 없다. 소거 확률은 [7-9]에서와 같이 송신 단과 수신 단 사이 거리뿐만 아니라 감쇠 변수의 함수로 구체화될 수 있다. 본 논문에서는 [9]에서와 마찬가지로 소거 확률을 두 가지 다른 식으로 모델링하는데, 지수 감쇠 모델다항 감쇠 모델 을 사용하도록 한다. 취득 용량을 분석하기 위해, 중계기의 도움을 받는 다중 홉 프로토콜, 중계기의 도움을 받지 않는 다중 홉 프로토콜, 이렇게 두 가지 존재하는 라우팅 기술 [3-4]을 사용한다. 그리고 라우팅 기술 하에서 취득 가능한 용량 스케일링 법칙을 보인다. 주요 결과로써, 유도된 용량 스케일링은 두 가지 물리적 모델 (지수 감쇠 모델 및 다항 감쇠 모델) 모두에 대해 노드 수 n과 중계기 수 m에는 의존함을 확인한다. 또한, 지수 감쇠 모델 하에서 유도된 용량 스케일링 결과는 감쇠 변수 (즉, 소거 확률)에는 의존하지 않는 반면, 다항 감쇠 모델 하에서의 결과는 감쇠 변수에 의존함을 보인다.

    본 논문의 구성은 다음과 같다. II장에서는 시스템 및 채널모델을 소개한다. III장에서는 지수 감쇠 모델에 기반 용량 스케일링을 분석한다. IV장에서는 다항 감쇠 모델 기반 용량 스케일링을 분석한다. V장에서는 본 논문을 요약 및 마무리 한다. 본 논문에서는, 전체적인 가독성을 높이기 위해 필요 시 theorem의 간략한 증명만을 제공하도록 한다.

    II. 시스템 및 채널 모델

    단위 노드 밀도를 가지는 스퀘어에 분포된 n개의 무선 노드로 구성된 2차원 애드 혹 네트워크 (즉, 확장 네트워크)를 고려한다. 두 인접 노드가 서로 거리 1만큼 떨어져있는 균일 네트워크 [10]를 가정한다. 각 노드가 정확히 source 하나의 destination이 되도록 S-D 쌍을 랜덤하게 고르도록 한다. 전체 영역이 m개의 스퀘어 셀로 분할되고 셀 각각은 중앙에 하나의 단일 안테나 중계기를 갖는다고 가정한다. n개의 노드가 중계기 영역을 제외한 부분에 고르게 분포되어 있다고 가정하면, 각각의 중계기와 중계기로부터 가장 인접한 노드 사이의 최소 거리 0 < dmin ≤ 1을 유지할 수 있게 된다 (이 때, dminn과 독립). 분석적 편이를 위해 변수 nmβ∈[0,1) 에 대해 수식 m = nβ를 따르도록 한다. 게다가 [3-4]에서와 같이, 중계기간 링크는 서로 무한대의 대역폭 (또는 무한대의 용량) 접속을 가지고 중계기들은 source나 destination 역할을 하지 않는다고 가정한다.

    이제 두 노드 사이의 채널을 묘사한다. 채널은 독립적인 모든 채널에 대해 소거 이벤트를 가진 기억이 없는 (memoryless) 소거 채널로써 모델링 된다. 먼저 상향 링크에서의 채널 모델이 아래와 같이 주어진다. 노드 i∈{1, ⋯, n}와 중계기 k∈{1, ⋯, m} 사이 전송에 대한 소거 확률 ϵki는 거리에 따른 증가 함수로 모델링된다. 먼저, 성공적인 전송 확률이 노드 i와 중계기 k 사이의 거리 dki와 함께 지수적으로 감소하는 그러한 지수 감쇠 모델을 고려한다. 이 때, 소거 확률은 아래와 같다.

    여기에서, α > 0는 감쇠 변수를 나타낸다. 이 모델은 긴 패킷을 가정할 때, 전파 거리와 함께 다항적으로 감소하는 수신 신호 대 잡음비 측면에서 각 패킷 안에 채널 부호를 사용하여 얻어지는 오류율 (error rate)에 착안한 것이다. 또한, 성공적인 전송 확률이 노드 i와 중 계기 k 사이의 거리 dki와 함께 다항적으로 감소하는 그러한 지수 감쇠 모델을 고려할 경우, 소거 확률은 아래와 같다.

    추가로, 무선 네트워크의 브로드캐스트 특성을 더 포함시키기 위해 finite-field 부가 간섭 [7-8]의 경우를 고려한다. 매 시간 슬롯마다 각 노드 i∈{1, ⋯, n}가 finite-field 알파벳 Fq로부터 단일 심볼을 선택할 때, 중계기 k에서의 수신 심볼 yk는 아래와 같이 주어진다.

    여기에서, I는 동시에 전송하는 노드 집합을 나타내고, γki는 인덱스 및 시간 슬롯에 대해 독립적인 Bernoulli 랜덤 변수인데 확률 ϵki로 값 0을 가진다. 출력은 모든 수거되지 않은 심볼의 합으로 표현되게 된다. 마찬가지 로, 중계기 k∈{1, ⋯, m}와 노드 i∈{1, ⋯, n} 사이의 하향링크 채널, 그리고 무선 노드 i와 (i,k∈{1, ⋯, n}) 사이의 채널도 유사한 방법으로 모델링될 수 있다.

    III. 지수 감쇠 모델 기반 용량 스케일링

    본 절에서는 지수 감쇠 모델 하에서 중계기 기반 소거 네트워크의 성능을 분석한다. 이 때 부가 가우시언 잡음을 가정한 애드 혹 네크워크에서 일반적으로 사용되어 온 중계기 도움을 받는 최근거리 다중 홉 라우팅 및 중계기 도움을 받지 않는 최근거리 다중 홉 라우팅, 이렇게 두 가지 종류의 라우팅 기술 [3], [4]을 사용한다. 인프라 구조 노드를 활용하는 전송 기술은 다음과 같이 세 단계로 구성된다. 1) source 노드는 가장 가까운 중계기로 패킷을 전송한다. (즉, 접속 라우팅 (access routing)이 수행된다.) 2) 패킷을 가진 중계기는 유선 중계기 간 링크를 통해 source의 해당 destination에 가장 가까운 중계기로 패킷을 전송한다. 3) 출구 라우팅 (exit routng)에 대해, destination은 최근거리에 있는 중계기로부터 최종적으로 데이터를 수신하게 된다. 어느 중계기 도움도 받지 않는 순수 다중 홉 프로토콜은 본질적으로 [1]에서의 과정을 따른다. 큰 간섭 야기를 피하기 위해, 위에서 언급한 두 가지 프로토콜에 대해 간단한 시분할 다중 접속 (TDMA: time division multiple access) 동작을 수행한다. 이제 가정하는 지수 감쇠 모델 기반 혼합 소거 네트워크에서 위 두 가지 다중 홉 프로토콜 사용 시 취득 가능한 용량을 보인다.

    Theorem 1: 중계기를 가진 확장 소거 네트워크에서 식 (1)로 주어지는 지수 감쇠 모델을 사용할 때, β∈[0,1)를 만족하는 모든 m = nβ에 대해 아래 용량이 취득 가능하다.

    증명 : 증명은 [7]에서의 Theorem 2를 수정함으로써 유사하게 보여질 수 있다. 원하는 송신 단에 의해 전송된 심볼이 지워지지 않고 또한 모든 다른 동시에 전송하는 노드로부터의 심볼이 모두 지워진다면, 해당 심볼은 수신 단에서 성공적으로 복호 가능하다. t-TDMA 기술 기반으로 동작하는 접속 라우팅에 초점을 맞추자 (이 때, 변수 t는 나중에 구체화된다). t-TDMA 기술 하에서, 최근거리 간섭 노드는 의도된 수신 단 (인프라 구 조 또는 무선 노드일 수 있음)으로부터 최소 거리 이상 떨어져 있다. 이 때, PI 를 동시에 간섭하는 노드들 중 최소 하나 이상으로부터 전송된 심볼이 소거되지 않을 확률로 가정한다. 모든 간섭 모드에 대해 union bound 및 [5]의 Section IV에서 보인 계층화 (layering) 기술을 사용함으로써, 아래와 같이 PI 에 대한 상향선을 얻을 수 있다.

    이 때, n과 독립인 아래 식을 만족하는 정수 t를 선택함으로써, 식 (4)는 1보다 작게 됨을 확인할 수 있다.

    따라서, 매 홉 당 전송 용량 α(1 - PI)/t = Ω(1)이 취득 가능하다. 위와 유사하게 분석을 수행함으로써, 출구 라우팅 및 순수 애드 혹 라우팅 모두에 대해 전송 용량 Ω(1)이 역시 취득 가능함을 보일 수 있다. 중계기 도움을 받는 다중 홉 라우팅 및 중계기 도움을 받지 않은 다중 홉 라우팅에 대해 각각 동시에 m개 및 개까지의 source 노드를 활성화하는 것이 가능 하기 때문에, 전체 네트워크 용량은 최종적으로 식 (3)과 같이 주어진다.

    가우시언 네트워크 모델 [5]의 경우와는 달리, 계층적 협력 통신 [2] 또는 보다 복잡한 다중사용자 검출 기술 [5]의 사용은 취득 가능한 용량 스케일링을 개선하는데 필요하지 않게 된다 (이에 대한 구체적인 증명은 본 논문의 범위를 넘어가므로 생략한다).

    IV. 다항 감쇠 모델 기반 용량 스케일링

    본 절에서는 다항 감쇠 모델 하에서 중계기 기반 소거 네트워크의 성능을 분석한다. III절에서와 동일하게 중계기 도움을 받는 최근거리 다중 홉 라우팅 및 중계기 도움을 받지 않는 최근거리 다중 홉 라우팅, 이렇게 두 가지 종류의 라우팅 기술 [3], [4]을 사용한다. 인프라 구조 노드를 활용하는 전송 기술은 지수 감쇠 모델 경우와 마찬가지로 세 단계 구성을 따른다 (보다 구체적인 묘사는 III절을 참고한다). 역시 두 가지 다중 홉 기술에 대해 간단한 TDMA 동작을 사용한다. 이제 가정하는 다항 감쇠 모델 기반 혼합 소거 네트워크에서 두 가지 다중 홉 프로토콜 사용 시 취득 가능한 용량을 보인다.

    Theorem 2: 중계기를 가진 확장 소거 네트워크에서 식 (2)로 주어지는 다항 감쇠 모델을 사용할 때, β∈[0,1)를 만족하는 모든 m = nβα > 2에 대해 아래 용량이 취득 가능하다.

    증명 : 증명은 Theorem 1에서의 증명 과정을 본질적으로 따른다. 먼저, 접속 라우팅에 초점을 맞추자. 용량 스케일링 분석에서 널리 사용되어 온 t-TDMA 기술을 활용한다. 이 때, 각 시간 슬롯에서, 서로 최소 거리 이상 떨어진 다수 개의 노드는 동시에 전송을 수행한다. 원하는 송신 단에 의해 전송된 심볼이 지워지지 않고 또한 모든 다른 동시에 전송하는 노드로부터의 심볼이 모두 지워진다면, 한 노드로부터 전송된 심볼은 성공적으로 복호된다. i번째 계층에 8i개의 간섭 노드가 존재하는데 이 때 의도된 수신 단으로부터 거리는 로 주어지기 때문에, 간섭 노드 중 최소 하나로부터 전송된 심볼이 지워지지 않을 확률 PI는 아래와 같이 주어진다.

    여기에서, t > 1 이고 마지막 등호에서의 합은 α > 2 일 때 수렴한다. 합 을 Kα로 표기할 때, t의 값을 아래와 같이 설정함으로써 확률 PI 를 1보다 작게 만들 수 있음을 보일 수 있다.

    t >( 1 + ( 8 ( 1 + 2Kα))1/α)2

    이 때, t의 값은 변수 n에 의존하지 않는다. 따라서 매 홉 당 아래와 같은 전송 용량이 취득 가능하다.

    위와 유사하게 분석을 수행함으로써, 출구 라우팅 및 순수 애드 혹 라우팅 모두에 대해 전송 용량 Ω(1)이 역시 취득 가능함을 보일 수 있다. 중계기 도움을 받는 다중 홉 라우팅 및 중계기 도움을 받지 않은 다중 홉 라우팅에 대해 각각 동시에 m개 및 Ω()개까지의 source 노드를 활성하하는 것이 가능하기 때문에, 전체 네트워크 용량은 최종적으로 식 (5)와 같이 주어진다.

    취득 가능 용량이 감쇠 변수 α에 의존하지 않는 지수 감쇠 모델의 경우와는 달리, 다항 감쇠 모델 하에서 유도된 취득 가능 용량은 α > 2에 대해서 성립함을 확인할 수 있다. 또한, 지수/다항 감쇠 모델 기반으로 유도된 두 개의 용량 스케일링은 α > 2일 때 동일함을 알 수 있다. 즉, 경로 감쇠 변수 α가 높을 때, 가정한 두 개의 소거 채널 모델에 대해 취득 가능한 용량 스케일링은 동일함이 밝혀진다.

    V. 결 론

    인프라 구조를 사용한 소거 네트워크에서 두 가지 다른 물리적 모델 사용 시 취득 가능한 용량 스케일링을 분석하였다. 용량 스케일링은 nm의 함수로 유도되 었다. 먼저, 인프라 구조 지원의 영향력은 m이 보다 빠르게 스케일할 때 (즉, β ≥ 1/2), 우월함을 보였다. 또한, 유도된 용량 스케일링은 두 가지 물리적 모델 모두에 대해 네트워크 변수 nm에 의존함을 확인하였다. 추가로, 다항 감쇠 모델에서 다항 변수 값이 높을 때, 용량 스케일링이 지수 감쇠 모델에서의 경우와 동일함을 보였다.

  • 1. Gupta P., Kumar P. R. 2000 "The capacity of wireless networks," [IEEE Trans. Inf. Theory] Vol.46 P.388-404 google doi
  • 2. Ozgur A., Leveque O., Tse D. N. C. 2007 "Hierarchical cooperation achieves optimal capacity scaling in ad hoc networks," [IEEE Trans. Inf. Theory] Vol.53 P.3549-3572 google doi
  • 3. Liu B., Liu Z., Towsley D. 2003 "On the capacity of hybrid wireless networks," [in Proc. INFOCOM] P.1543-1552 google
  • 4. Zemlianov A., de Veciana G. 2005 "Capacity of ad hoc wireless networks with infrastructure support," [IEEE J. Select. Areas Commun.] Vol.23 P.657-667 google doi
  • 5. Shin W.-Y., Jeon S.-W., Devroye N., Vu M. H., Chung S.-Y., Lee Y. H., Tarokh V. 2011 "Improved capacity scaling in wireless networks with infrastructure," [IEEE Trans. Inf. Theory] Vol.57 P.5088-5102 google doi
  • 6. Dana A., Gowaikar R., Hassibi B. 2006 "Capacity of wireless erasure networks," [IEEE Trans. Inf. Theory] Vol.32 P.789-804 google
  • 7. Smith B., Gupta P., Vishwanath S. 2007 "Routing is orderoptimal in broadcast erasure networks with interference," [in Proc. IEEE Int. Symp. Inf. Theory (ISIT)] P.141-145 google
  • 8. Smith B., Gupta P., Vishwanath S. 2007 "Routing versus network coding in erasure networks with broadcast and interference constraints," [in Proc. IEEE Military Commun. Conf. (MILCOM)] P.1-5 google
  • 9. Swith B., Vishwanath S. "Asymptotic transport capacity of wireless erasure networks," [in Proc. 2006 Allerton Conf. on Commun., Control, and Computing] google
  • 10. Xie L.-L., Kumar P. R. 2004 "A network information theory for wireless communication: Scaling laws and optimal operating," [IEEE Trans. Inf. Theory] Vol.50 P.748-767 google doi
  • 11. Franceschetti M., Dousse O., Tse D. N. C., Thiran P. 2007 "Closing the gap in the capacity of wireless networks via percolation theory," [IEEE Trans. Inf. Theory] Vol.53 P.1009-1018 google doi