Advanced
Throughput Scaling Law of Hybrid Erasure Networks Based on Physical Model
Throughput Scaling Law of Hybrid Erasure Networks Based on Physical Model
Journal of the Korea Institute of Information and Communication Engineering. 2014. Jan, 18(1): 57-62
Copyright © 2014, The Korea Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : November 12, 2013
  • Accepted : December 19, 2013
  • Published : January 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
원용 신
wyshin@dankook.ac.kr

Abstract
다수의 중계기가 균등하게 분포된 무선 소거 네트워크의 용량 스케일링 법칙을 분석함으로써 인프라 구조 사용시 이득을 보인다. 가정하는 네트워크 하에서 소거 확률을 적절히 모델링함에 근거하여, 혼합 소거 네트워크에서 취득 가능한 네트워크 용량을 보인다. 보다 구체적으로, 지수 감쇠 모델 및 다항 감쇠 모델 이렇게 두 가지 물리적 모델을 사용한다. 중계기 도움이 없는 다중 홉 전송, 중계기 도움을 받는 다중 홉 전송 이렇게 두 가지 존재하는 기술을 사용하여 취득 용량을 분석한다. 유도된 용량 스케일링 법칙은 두 가지 물리적 모델 모두에 대해 노드 수 및 중계기의 수에 의존함을 확인한다.
Keywords
I. 서 론
[1] 에서 Gupta와 Kumar 연구 그룹은 부가 가우시언(Gaussian) 잡음을 가진 거대 무선 네트워크에서 합 용량 스케일링을 소개하고 분석하였다. [1] 에서는 단위 면적에 랜덤하게 분포된 n 개의 source-destination (S-D)쌍을 갖는 네트워크에 대해 전체 용량이
PPT Slide
Lager Image
으로 스케일함을 보였다. 이 용량 스케일링은 다중 홉(multi-hop) 기술을 사용하여 취득된다. 최근 연구에서는 계층적 협력 (hierarchical cooperation) 기술을 사용함으로써 가우시언 네트워크 모델에서 거의 선형적인 용량, 즉, 임의의 작은 ε > 0에 대해 θ( n 1-ε )이 취득 가능함을 보였다 [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 < d min ≤ 1을 유지할 수 있게 된다 (이 때, d min n 과 독립). 분석적 편이를 위해 변수 n m β ∈[0,1) 에 대해 수식 m = n β 를 따르도록 한다. 게다가 [3 - 4] 에서와 같이, 중계기간 링크는 서로 무한대의 대역폭 (또는 무한대의 용량) 접속을 가지고 중계기들은 source나 destination 역할을 하지 않는다고 가정한다.
이제 두 노드 사이의 채널을 묘사한다. 채널은 독립적인 모든 채널에 대해 소거 이벤트를 가진 기억이 없는 (memoryless) 소거 채널로써 모델링 된다. 먼저 상향 링크에서의 채널 모델이 아래와 같이 주어진다. 노드 i ∈{1, ⋯, n }와 중계기 k ∈{1, ⋯, m } 사이 전송에 대한 소거 확률 ϵ ki 는 거리에 따른 증가 함수로 모델링된다. 먼저, 성공적인 전송 확률이 노드 i 와 중계기 k 사이의 거리 dki 와 함께 지수적으로 감소하는 그러한 지수 감쇠 모델을 고려한다. 이 때, 소거 확률은 아래와 같다.
PPT Slide
Lager Image
여기에서, α > 0는 감쇠 변수를 나타낸다. 이 모델은 긴 패킷을 가정할 때, 전파 거리와 함께 다항적으로 감소하는 수신 신호 대 잡음비 측면에서 각 패킷 안에 채널 부호를 사용하여 얻어지는 오류율 (error rate)에 착안한 것이다. 또한, 성공적인 전송 확률이 노드 i 와 중 계기 k 사이의 거리 dki 와 함께 다항적으로 감소하는 그러한 지수 감쇠 모델을 고려할 경우, 소거 확률은 아래와 같다.
PPT Slide
Lager Image
추가로, 무선 네트워크의 브로드캐스트 특성을 더 포함시키기 위해 finite-field 부가 간섭 [7 - 8] 의 경우를 고려한다. 매 시간 슬롯마다 각 노드 i ∈{1, ⋯, n }가 finite-field 알파벳 Fq 로부터 단일 심볼을 선택할 때, 중계기 k 에서의 수신 심볼 yk 는 아래와 같이 주어진다.
PPT Slide
Lager Image
여기에서, 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 β 에 대해 아래 용량이 취득 가능하다.
PPT Slide
Lager Image
증명 : 증명은 [7] 에서의 Theorem 2를 수정함으로써 유사하게 보여질 수 있다. 원하는 송신 단에 의해 전송된 심볼이 지워지지 않고 또한 모든 다른 동시에 전송하는 노드로부터의 심볼이 모두 지워진다면, 해당 심볼은 수신 단에서 성공적으로 복호 가능하다. t -TDMA 기술 기반으로 동작하는 접속 라우팅에 초점을 맞추자 (이 때, 변수 t 는 나중에 구체화된다). t -TDMA 기술 하에서, 최근거리 간섭 노드는 의도된 수신 단 (인프라 구 조 또는 무선 노드일 수 있음)으로부터 최소 거리
PPT Slide
Lager Image
이상 떨어져 있다. 이 때, PI 를 동시에 간섭하는 노드들 중 최소 하나 이상으로부터 전송된 심볼이 소거되지 않을 확률로 가정한다. 모든 간섭 모드에 대해 union bound 및 [5] 의 Section IV에서 보인 계층화 (layering) 기술을 사용함으로써, 아래와 같이 PI 에 대한 상향선을 얻을 수 있다.
PPT Slide
Lager Image
이 때, n 과 독립인 아래 식을 만족하는 정수 t 를 선택함으로써, 식 (4)는 1보다 작게 됨을 확인할 수 있다.
PPT Slide
Lager Image
따라서, 매 홉 당 전송 용량 α (1 - PI )/ t = Ω (1)이 취득 가능하다. 위와 유사하게 분석을 수행함으로써, 출구 라우팅 및 순수 애드 혹 라우팅 모두에 대해 전송 용량 Ω (1)이 역시 취득 가능함을 보일 수 있다. 중계기 도움을 받는 다중 홉 라우팅 및 중계기 도움을 받지 않은 다중 홉 라우팅에 대해 각각 동시에 m 개 및
PPT Slide
Lager Image
개까지의 source 노드를 활성화하는 것이 가능 하기 때문에, 전체 네트워크 용량은 최종적으로 식 (3)과 같이 주어진다.
가우시언 네트워크 모델 [5] 의 경우와는 달리, 계층적 협력 통신 [2] 또는 보다 복잡한 다중사용자 검출 기술 [5] 의 사용은 취득 가능한 용량 스케일링을 개선하는데 필요하지 않게 된다 (이에 대한 구체적인 증명은 본 논문의 범위를 넘어가므로 생략한다).
IV. 다항 감쇠 모델 기반 용량 스케일링
본 절에서는 다항 감쇠 모델 하에서 중계기 기반 소거 네트워크의 성능을 분석한다. III절에서와 동일하게 중계기 도움을 받는 최근거리 다중 홉 라우팅 및 중계기 도움을 받지 않는 최근거리 다중 홉 라우팅, 이렇게 두 가지 종류의 라우팅 기술 [3] , [4] 을 사용한다. 인프라 구조 노드를 활용하는 전송 기술은 지수 감쇠 모델 경우와 마찬가지로 세 단계 구성을 따른다 (보다 구체적인 묘사는 III절을 참고한다). 역시 두 가지 다중 홉 기술에 대해 간단한 TDMA 동작을 사용한다. 이제 가정하는 다항 감쇠 모델 기반 혼합 소거 네트워크에서 두 가지 다중 홉 프로토콜 사용 시 취득 가능한 용량을 보인다.
Theorem 2 : 중계기를 가진 확장 소거 네트워크에서 식 (2)로 주어지는 다항 감쇠 모델을 사용할 때, β ∈[0,1)를 만족하는 모든 m = n β α > 2에 대해 아래 용량이 취득 가능하다.
PPT Slide
Lager Image
증명 : 증명은 Theorem 1에서의 증명 과정을 본질적으로 따른다. 먼저, 접속 라우팅에 초점을 맞추자. 용량 스케일링 분석에서 널리 사용되어 온 t -TDMA 기술을 활용한다. 이 때, 각 시간 슬롯에서, 서로 최소 거리
PPT Slide
Lager Image
이상 떨어진 다수 개의 노드는 동시에 전송을 수행한다. 원하는 송신 단에 의해 전송된 심볼이 지워지지 않고 또한 모든 다른 동시에 전송하는 노드로부터의 심볼이 모두 지워진다면, 한 노드로부터 전송된 심볼은 성공적으로 복호된다. i 번째 계층에 8 i 개의 간섭 노드가 존재하는데 이 때 의도된 수신 단으로부터 거리는
PPT Slide
Lager Image
로 주어지기 때문에, 간섭 노드 중 최소 하나로부터 전송된 심볼이 지워지지 않을 확률 PI 는 아래와 같이 주어진다.
PPT Slide
Lager Image
여기에서, t > 1 이고 마지막 등호에서의 합은 α > 2 일 때 수렴한다. 합
PPT Slide
Lager Image
Kα 로 표기할 때, t 의 값을 아래와 같이 설정함으로써 확률 PI 를 1보다 작게 만들 수 있음을 보일 수 있다.
t >( 1 + ( 8 ( 1 + 2 Kα )) 1/α ) 2
이 때, t 의 값은 변수 n 에 의존하지 않는다. 따라서 매 홉 당 아래와 같은 전송 용량이 취득 가능하다.
PPT Slide
Lager Image
위와 유사하게 분석을 수행함으로써, 출구 라우팅 및 순수 애드 혹 라우팅 모두에 대해 전송 용량 Ω (1)이 역시 취득 가능함을 보일 수 있다. 중계기 도움을 받는 다중 홉 라우팅 및 중계기 도움을 받지 않은 다중 홉 라우팅에 대해 각각 동시에 m 개 및 Ω (
PPT Slide
Lager Image
)개까지의 source 노드를 활성하하는 것이 가능하기 때문에, 전체 네트워크 용량은 최종적으로 식 (5)와 같이 주어진다.
취득 가능 용량이 감쇠 변수 α 에 의존하지 않는 지수 감쇠 모델의 경우와는 달리, 다항 감쇠 모델 하에서 유도된 취득 가능 용량은 α > 2에 대해서 성립함을 확인할 수 있다. 또한, 지수/다항 감쇠 모델 기반으로 유도된 두 개의 용량 스케일링은 α > 2일 때 동일함을 알 수 있다. 즉, 경로 감쇠 변수 α 가 높을 때, 가정한 두 개의 소거 채널 모델에 대해 취득 가능한 용량 스케일링은 동일함이 밝혀진다.
V. 결 론
인프라 구조를 사용한 소거 네트워크에서 두 가지 다른 물리적 모델 사용 시 취득 가능한 용량 스케일링을 분석하였다. 용량 스케일링은 n m 의 함수로 유도되 었다. 먼저, 인프라 구조 지원의 영향력은 m
PPT Slide
Lager Image
보다 빠르게 스케일할 때 (즉, β ≥ 1/2), 우월함을 보였다. 또한, 유도된 용량 스케일링은 두 가지 물리적 모델 모두에 대해 네트워크 변수 n m 에 의존함을 확인하였다. 추가로, 다항 감쇠 모델에서 다항 변수 값이 높을 때, 용량 스케일링이 지수 감쇠 모델에서의 경우와 동일함을 보였다.
Acknowledgements
본 연구는 미래부가 지원한 2013년 정보통신·방송(ICT) 연구개발사업의 연구결과로 수행되었음
BIO
신원용(Won-Yong Shin) 2002년 연세대학교 기계전자공학부 학사 2004년 KAIST 전자전산학과 석사 2008년 KAIST 전자전산학부 박사 2008년 2월~4월 Harvard University 방문연구원 2008년 9월~2009년 2월 KAIST BK 정보전자연구소 박사후연구원 2009년 3월~4월 KAIST 고성능집적시스템연구센터 선임급 위촉연구원 2008년 8월~2009년 4월 (주)루미콤 방문연구원 2009년 5월~2011년 10월 Harvard University Postdoctoral Fellow 2011년 10월~2012년 2월 Harvard University Research Associate 2012년 3월~현재 단국대학교 국제학부 모바일시스템공학전공 조교수 ※관심분야 : 정보이론, 통신이론, 신호처리, 네트워킹 이슈로의 다양한 응용
References
Gupta P. , Kumar P. R. 2000 "The capacity of wireless networks," IEEE Trans. Inf. Theory 46 388 - 404    DOI : 10.1109/18.825799
Ozgur A. , Leveque O. , Tse D. N. C. 2007 "Hierarchical cooperation achieves optimal capacity scaling in ad hoc networks," IEEE Trans. Inf. Theory 53 3549 - 3572    DOI : 10.1109/TIT.2007.905002
Liu B. , Liu Z. , Towsley D. 2003 "On the capacity of hybrid wireless networks," in Proc. INFOCOM 1543 - 1552
Zemlianov A. , de Veciana G. 2005 "Capacity of ad hoc wireless networks with infrastructure support," IEEE J. Select. Areas Commun. 23 (3) 657 - 667    DOI : 10.1109/JSAC.2004.842536
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 57 5088 - 5102    DOI : 10.1109/TIT.2011.2158881
Dana A. , Gowaikar R. , Hassibi B. 2006 "Capacity of wireless erasure networks," IEEE Trans. Inf. Theory 32 789 - 804
Smith B. , Gupta P. , Vishwanath S. 2007 "Routing is orderoptimal in broadcast erasure networks with interference," in Proc. IEEE Int. Symp. Inf. Theory (ISIT) 141 - 145
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) 1 - 5
Swith B. , Vishwanath S. "Asymptotic transport capacity of wireless erasure networks," in Proc. 2006 Allerton Conf. on Commun., Control, and Computing
Xie L.-L. , Kumar P. R. 2004 "A network information theory for wireless communication: Scaling laws and optimal operating," IEEE Trans. Inf. Theory 50 748 - 767    DOI : 10.1109/TIT.2004.826631
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 53 1009 - 1018    DOI : 10.1109/TIT.2006.890791