Journal of the Korea Institute of Information and Communication Engineering 한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 18, No. 1 : 57~62 Jan. 2014 물리적모델기반혼합소거네트워크의용량스케일링법칙 신원용 * Throughput Scaling Law of Hybrid Erasure Networks Based on Physical Model Won-Yong Shin * Department of Computer Science and Engineering, Dankook University, Yongin 448-701, Korea 요약 다수의중계기가균등하게분포된무선소거네트워크의용량스케일링법칙을분석함으로써인프라구조사용시이득을보인다. 가정하는네트워크하에서소거확률을적절히모델링함에근거하여, 혼합소거네트워크에서취득가능한네트워크용량을보인다. 보다구체적으로, 지수감쇠모델및다항감쇠모델이렇게두가지물리적모델을사용한다. 중계기도움이없는다중홉전송, 중계기도움을받는다중홉전송이렇게두가지존재하는기술을사용하여취득용량을분석한다. 유도된용량스케일링법칙은두가지물리적모델모두에대해노드수및중계기의수에의존함을확인한다. 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. 키워드 : 취득용량스케일링법칙, 소거확률, 혼합소거네트워크, 인프라구조, 다중홉, 물리적모델 Key word : Achievable throughput scaling law, erasure probability, hybrid erasure network, infrastructure, multi-hop, physical model 접수일자 : 2013. 11. 12 심사완료일자 : 2013. 12. 09 게재확정일자 : 2013. 12. 19 * Corresponding Author Won-Yong Shin (E-mail:wyshin@dankook.ac.kr, Tel:+82-31-8005-3253) Department of Computer Science and Engineering, Dankook University, Yongin 448-701, Korea Open Access http://dx.doi.org/10.6109/jkiice.2014.18.1.57 print ISSN: 2234-4772 online ISSN: 2288-4165 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. Copyright C The Korea Institute of Information and Communication Engineering.
한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 18, No. 1 : 57~62 Jan. 2014 Ⅰ. 서론 [1] 에서 Gupta와 Kumar 연구그룹은부가가우시언 (Gaussian) 잡음을가진거대무선네트워크에서합용량스케일링을소개하고분석하였다. [1] 에서는단위면적에랜덤하게분포된 개의 source-destination (S-D) 쌍을갖는네트워크에대해전체용량이 log 으로스케일함을보였다. 이용량스케일링은다중홉 (multi-hop) 기술을사용하여취득된다. 최근연구에서는계층적협력 (hierarchical cooperation) 기술을사용함으로써가우시언네트워크모델에서거의선형적인용량, 즉, 임의의작은 에대해 이취득가능함을보였다 [2]. 무선네트워크의용량을선형스케일링으로개선하기위해, 무선애드혹노드뿐만아니라인프라구조노드 ( 또는동일한의미로중계기 (relay station) 노드 ) 로구성된혼합네트워크에대한연구가 [3-4] 에서역시수행되었는데, 이때중계기는서로고대역폭 ( 또는고용량 ) 으로연결되어있다고가정하였다. 혼합네트워크에서는중계기의수 에따른선형용량스케일링을취득하기위해 이특정임계값을넘어야하는엄격한조건이요구된다. [5] 에서는각각의중계기에서다중안테나를사용하는더욱일반화된혼합네트워크에서최적용량스케일링이분석되었는데, 취득용량은중계기기반단일홉, 중계기기반다중홉, 순수다중홉전송 [1], 그리고계층적협력통신 [2] 중하나를선택함으로써얻을수있음을보였다. 게다가, 네트워크의또다른근본적인종류로써, 무선소거네트워크가소개되었다 [6]. [6] 에서는용량영역 (capacity region) 의정확한규명이몇몇간단한멀티캐스트문제에대해이루어졌다. 또한, [7-9] 에서는 S-D 쌍이랜덤하게선택된다고가정할때, 부가간섭을갖는소거네트워크에다수개의노드가존재하는보다일반적인시나리오에대해스케일링법칙측면에서용량에대한분석이수행되었다. 이러한소거네트워크모델은모든정보전송이패킷화되는그러한 Automatic Repeat request (ARQ) 와같은기능을가지는시스템에적합하다할수있다. 본논문에서는, 개의균등하게위치한인프라구조노드를가진혼합소거네트워크에대한용량스케일링법칙을분석한다. 구체적으로단위노드밀도의확장네트워크 [2], [5], [10] 에서취득가능한용량을보 인다. 가우시언네트워크모델에서중계기지원에대한깊이있는연구가수행되어온반면, 소거네트워크에대한그러한시도는현재까지시도되어온바가없다. 소거확률은 [7-9] 에서와같이송신단과수신단사이거리뿐만아니라감쇠변수의함수로구체화될수있다. 본논문에서는 [9] 에서와마찬가지로소거확률을두가지다른식으로모델링하는데, 지수감쇠모델및다항감쇠모델을사용하도록한다. 취득용량을분석하기위해, 중계기의도움을받는다중홉프로토콜, 중계기의도움을받지않는다중홉프로토콜, 이렇게두가지존재하는라우팅기술 [3-4] 을사용한다. 그리고라우팅기술하에서취득가능한용량스케일링법칙을보인다. 주요결과로써, 유도된용량스케일링은두가지물리적모델 ( 지수감쇠모델및다항감쇠모델 ) 모두에대해노드수 과중계기수 에는의존함을확인한다. 또한, 지수감쇠모델하에서유도된용량스케일링결과는감쇠변수 ( 즉, 소거확률 ) 에는의존하지않는반면, 다항감쇠모델하에서의결과는감쇠변수에의존함을보인다. 본논문의구성은다음과같다. II장에서는시스템및채널모델을소개한다. III장에서는지수감쇠모델에기반용량스케일링을분석한다. IV장에서는다항감쇠모델기반용량스케일링을분석한다. V장에서는본논문을요약및마무리한다. 본논문에서는, 전체적인가독성을높이기위해필요시 theorem의간략한증명만을제공하도록한다. Ⅱ. 시스템및채널모델단위노드밀도를가지는스퀘어에분포된 개의무선노드로구성된 2차원애드혹네트워크 ( 즉, 확장네트워크 ) 를고려한다. 두인접노드가서로거리 1만큼떨어져있는균일네트워크 [10] 를가정한다. 각노드가정확히 source 하나의 destination이되도록 S-D 쌍을랜덤하게고르도록한다. 전체영역이 개의스퀘어셀로분할되고셀각각은중앙에하나의단일안테나중계기를갖는다고가정한다. 개의노드가중계기영역을제외한부분에고르게분포되어있다고가정하면, 각각의중계기와중계기로부터가장인접한노드사이의최소거리 min 을유지할수있게된다 ( 이 58
물리적모델기반혼합소거네트워크의용량스케일링법칙 때, min 은 과독립 ). 분석적편이를위해변수 과 은 에대해수식 를따르도록한다. 게다가 [3-4] 에서와같이, 중계기간링크는서로무한대의대역폭 ( 또는무한대의용량 ) 접속을가지고중계기들은 source나 destination 역할을하지않는다고가정한다. 이제두노드사이의채널을묘사한다. 채널은독립적인모든채널에대해소거이벤트를가진기억이없는 (memoryless) 소거채널로써모델링된다. 먼저상향링크에서의채널모델이아래와같이주어진다. 노드 와중계기 사이전송에대한소거확률 는거리에따른증가함수로모델링된다. 먼저, 성공적인전송확률이노드 와중계기 사이의거리 와함께지수적으로감소하는그러한지수감쇠모델을고려한다. 이때, 소거확률은아래와같다. (1) 여기에서, 는감쇠변수를나타낸다. 이모델은긴패킷을가정할때, 전파거리와함께다항적으로감소하는수신신호대잡음비측면에서각패킷안에채널부호를사용하여얻어지는오류율 (error rate) 에착안한것이다. 또한, 성공적인전송확률이노드 와중계기 사이의거리 와함께다항적으로감소하는그러한지수감쇠모델을고려할경우, 소거확률은아래와같다. (2) 추가로, 무선네트워크의브로드캐스트특성을더포함시키기위해 finite-field 부가간섭 [7-8] 의경우를고려한다. 매시간슬롯마다각노드 가 finite-field 알파벳 로부터단일심볼을선택할때, 중계기 에서의수신심볼 는아래와같이주어진다. 여기에서, 는동시에전송하는노드집합을나타내고, 는인덱스및시간슬롯에대해독립적인 Bernoulli 랜덤변수인데확률 로값 0을가진다. 출력은모든수거되지않은심볼의합으로표현되게된다. 마찬가지로, 중계기 와노드 사이의하향링크채널, 그리고무선노드 와 ( ) 사이의채널도유사한방법으로모델링될수있다. Ⅲ. 지수감쇠모델기반용량스케일링본절에서는지수감쇠모델하에서중계기기반소거네트워크의성능을분석한다. 이때부가가우시언잡음을가정한애드혹네크워크에서일반적으로사용되어온중계기도움을받는최근거리다중홉라우팅및중계기도움을받지않는최근거리다중홉라우팅, 이렇게두가지종류의라우팅기술 [3], [4] 을사용한다. 인프라구조노드를활용하는전송기술은다음과같이세단계로구성된다. 1) source 노드는가장가까운중계기로패킷을전송한다. ( 즉, 접속라우팅 (access routing) 이수행된다.) 2) 패킷을가진중계기는유선중계기간링크를통해 source의해당 destination에가장가까운중계기로패킷을전송한다. 3) 출구라우팅 (exit routng) 에대해, destination은최근거리에있는중계기로부터최종적으로데이터를수신하게된다. 어느중계기도움도받지않는순수다중홉프로토콜은본질적으로 [1] 에서의과정을따른다. 큰간섭야기를피하기위해, 위에서언급한두가지프로토콜에대해간단한시분할다중접속 (TDMA: time division multiple access) 동작을수행한다. 이제가정하는지수감쇠모델기반혼합소거네트워크에서위두가지다중홉프로토콜사용시취득가능한용량을보인다. Theorem 1: 중계기를가진확장소거네트워크에서식 (1) 로주어지는지수감쇠모델을사용할때, 를만족하는모든 에대해아래용량이취득가능하다. max (3) 증명 : 증명은 [7] 에서의 Theorem 2를수정함으로써유사하게보여질수있다. 원하는송신단에의해전송된심볼이지워지지않고또한모든다른동시에전송 59
한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 18, No. 1 : 57~62 Jan. 2014 하는노드로부터의심볼이모두지워진다면, 해당심볼은수신단에서성공적으로복호가능하다. -TDMA 기술기반으로동작하는접속라우팅에초점을맞추자 ( 이때, 변수 는나중에구체화된다 ). -TDMA 기술하에서, 최근거리간섭노드는의도된수신단 ( 인프라구조또는무선노드일수있음 ) 으로부터최소거리 이상떨어져있다. 이때, 를동시에간섭하는노드들중최소하나이상으로부터전송된심볼이소거되지않을확률로가정한다. 모든간섭모드에대해 union bound 및 [5] 의 Section IV에서보인계층화 (layering) 기술을사용함으로써, 아래와같이 에대한상향선을얻을수있다. (4) 이때, 과독립인아래식을만족하는정수 를선택함으로써, 식 (4) 는 1보다작게됨을확인할수있다. log 따라서, 매홉당전송용량 이취득가능하다. 위와유사하게분석을수행함으로써, 출구라우팅및순수애드혹라우팅모두에대해전송용량 이역시취득가능함을보일수있다. 중계기도움을받는다중홉라우팅및중계기도움을받지않은다중홉라우팅에대해각각동시에 개및 개까지의 source 노드를활성화하는것이가능하기때문에, 전체네트워크용량은최종적으로식 (3) 과같이주어진다. 가우시언네트워크모델 [5] 의경우와는달리, 계층적협력통신 [2] 또는보다복잡한다중사용자검출기술 [5] 의사용은취득가능한용량스케일링을개선하는데필요하지않게된다 ( 이에대한구체적인증명은본논문의범위를넘어가므로생략한다 ). Ⅳ. 다항감쇠모델기반용량스케일링 본절에서는다항감쇠모델하에서중계기기반소거네트워크의성능을분석한다. Ⅲ절에서와동일하게중 계기도움을받는최근거리다중홉라우팅및중계기도움을받지않는최근거리다중홉라우팅, 이렇게두가지종류의라우팅기술 [3], [4] 을사용한다. 인프라구조노드를활용하는전송기술은지수감쇠모델경우와마찬가지로세단계구성을따른다 ( 보다구체적인묘사는 Ⅲ절을참고한다 ). 역시두가지다중홉기술에대해간단한 TDMA 동작을사용한다. 이제가정하는다항감쇠모델기반혼합소거네트워크에서두가지다중홉프로토콜사용시취득가능한용량을보인다. Theorem 2: 중계기를가진확장소거네트워크에서식 (2) 로주어지는다항감쇠모델을사용할때, 를만족하는모든 및 에대해아래용량이취득가능하다. max (5) 증명 : 증명은 Theorem 1에서의증명과정을본질적으로따른다. 먼저, 접속라우팅에초점을맞추자. 용량스케일링분석에서널리사용되어온 -TDMA 기술을활용한다. 이때, 각시간슬롯에서, 서로최소거리 이상떨어진다수개의노드는동시에전송을수행한다. 원하는송신단에의해전송된심볼이지워지지않고또한모든다른동시에전송하는노드로부터의심볼이모두지워진다면, 한노드로부터전송된심볼은성공적으로복호된다. 번째계층에 개의간섭노드가존재하는데이때의도된수신단으로부터거리는 로주어지기때문에, 간섭노드중최소하나로부터전송된심볼이지워지지않을확률 는아래와같이주어진다. 60
물리적모델기반혼합소거네트워크의용량스케일링법칙 여기에서, 이고마지막등호에서의합은 일때수렴한다. 합 을 로표기할때, 의값을아래와같이설정함으로써확률 를 1보다작게만들수있음을보일수있다. 이때, 의값은변수 에의존하지않는다. 따라서매홉당아래와같은전송용량이취득가능하다. 모두에대해네트워크변수 과 에의존함을확인하였다. 추가로, 다항감쇠모델에서다항변수값이높을때, 용량스케일링이지수감쇠모델에서의경우와동일함을보였다. 감사의글본연구는미래부가지원한 2013년정보통신 방송 (ICT) 연구개발사업의연구결과로수행되었음 위와유사하게분석을수행함으로써, 출구라우팅및순수애드혹라우팅모두에대해전송용량 이역시취득가능함을보일수있다. 중계기도움을받는다중홉라우팅및중계기도움을받지않은다중홉라우팅에대해각각동시에 개및 개까지의 source 노드를활성하하는것이가능하기때문에, 전체네트워크용량은최종적으로식 (5) 와같이주어진다. 취득가능용량이감쇠변수 에의존하지않는지수감쇠모델의경우와는달리, 다항감쇠모델하에서유도된취득가능용량은 에대해서성립함을확인할수있다. 또한, 지수 / 다항감쇠모델기반으로유도된두개의용량스케일링은 일때동일함을알수있다. 즉, 경로감쇠변수 가높을때, 가정한두개의소거채널모델에대해취득가능한용량스케일링은동일함이밝혀진다. Ⅴ. 결론 인프라구조를사용한소거네트워크에서두가지다른물리적모델사용시취득가능한용량스케일링을분석하였다. 용량스케일링은 과 의함수로유도되었다. 먼저, 인프라구조지원의영향력은 이 보다빠르게스케일할때 ( 즉, ), 우월함을보였다. 또한, 유도된용량스케일링은두가지물리적모델 REFERENCES [ 1 ] P. Gupta and P. R. Kumar, ""The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, pp. 388-404, Mar. 2000. [ 2 ] A. Ozgur, O. Leveque, and D. N. C. Tse, "Hierarchical cooperation achieves optimal capacity scaling in ad hoc networks," IEEE Trans. Inf. Theory, vol. 53, pp. 3549-3572, Oct. 2007. [ 3 ] B. Liu, Z. Liu, and D. Towsley, "On the capacity of hybrid wireless networks," in Proc. INFOCOM, Mar. 2003, pp. 1543-1552. [ 4 ] A. Zemlianov and G. de Veciana, "Capacity of ad hoc wireless networks with infrastructure support," IEEE J. Select. Areas Commun., vol. 23, no. 3, pp. 657-667, Mar. 2005. [ 5 ] W.-Y. Shin, S.-W. Jeon, N. Devroye, M. H. Vu, S.-Y. Chung, Y. H. Lee, and V. Tarokh, "Improved capacity scaling in wireless networks with infrastructure," IEEE Trans. Inf. Theory, vol. 57, pp. 5088-5102, Aug. 2011. [ 6 ] A. Dana, R. Gowaikar, and B. Hassibi, "Capacity of wireless erasure networks," IEEE Trans. Inf. Theory, vol. 32, pp. 789-804, Mar. 2006. [ 7 ] B. Smith, P. Gupta, and S. Vishwanath, Routing is orderoptimal in broadcast erasure networks with interference," in Proc. IEEE Int. Symp. Inf. Theory (ISIT), June 2007, pp. 141-145. [ 8 ] B. Smith, P. Gupta, and S. Vishwanath, Routing versus network coding in erasure networks with broadcast and interference constraints," in Proc. IEEE Military Commun. 61
한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 18, No. 1 : 57~62 Jan. 2014 Conf. (MILCOM), Oct. 2007, pp. 1-5. [ 9 ] B. Swith and S. Vishwanath, "Asymptotic transport capacity of wireless erasure networks," in Proc. 2006 Allerton Conf. on Commun., Control, and Computing. [10] L.-L. Xie and P. R. Kumar, "A network information theory for wireless communication: Scaling laws and optimal operating," IEEE Trans. Inf. Theory, vol. 50, pp. 748-767, May 2004. [11] M. Franceschetti, O. Dousse, D. N. C. Tse, and P. Thiran, "Closing the gap in the capacity of wireless networks via percolation theory," IEEE Trans. Inf. Theory, vol. 53, pp. 1009-1018, Mar. 2007. 신원용 (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 월 ~ 현재단국대학교국제학부모바일시스템공학전공조교수 관심분야 : 정보이론, 통신이론, 신호처리, 네트워킹이슈로의다양한응용 62