Throughput Analysis of Opportunistic Routing in Long-Haul Multi-hop Wireless Networks

논문 2012-49TC-8-3

롱 홀 다중 홉 무선 네트워크에서의 Opportunistic 라우팅의

전송 용량 분석

( Throughput Analysis of Opportunistic Routing in Long-Haul

Multi-hop Wireless Networks )

이 구 연

*

, 이 용

***

( Goo Yeon Lee and Yong Lee )

요 약 본 논문에서는 롱 홀 (long–haul) 다중 홉 무선 네트워크에서 단일 데이터 스트림에 대한 opportunistic 라우팅 기법의 성 능분석을 수행한다. 성능분석에서는 네트워크 노드간의 링크 레벨 간섭을 고려한다. 일반적으로 opportunistic 라우팅 기법은 무선 다중 홉 네트워크의 성능을 크게 향상시킬 것으로 기대되어 왔고 이에 대한 성능향상 및 전송 기법에 대한 많은 연구가 수행되어 왔으나, 본 논문의 연구 결과는 롱 홀의 경우에는 opportunistic 라우팅의 성능향상 정도가 그리 크지 않다는 것을 보 여준다. 이와 같은 연구 결과는 opportunistic 라우팅 기법은 구현의 복잡성을 고려할 경우에 롱 홀 환경에서는 적용하는 것이 적당치 않으며, 환경에 따라 short-haul 환경에 집중하여 적용해야 함을 의미한다. Abstract

In this paper, we analyze the maximum throughput of opportunistic routing along a long-haul multi-hop wireless network path for a single data stream, while considering link-level interference among the network nodes. Surprisingly, we find out that opportunistic routing does not provide much improvement in throughput for long-haul paths. The results of this research show that when we compare the extra cost for the complex implementation of the opportunistic routing scheme to the performance improvement obtained from it, opportunistic routing scheme needs to be applied to only short-haul multi-hop wireless network paths

Keywords: Opportunistic 라우팅, 전송 용량, 링크 레벨 간섭, 다중 홉 무선 네트워크

Ⅰ. 서 론

다중 홉 무선 네트워크는 인프라가 필요 없고, 저비

*

정회원, 강원대학교 컴퓨터학부

(Dept. of Computer Eng. Kangwon National

University)

**

정회원-교신저자, 코넬대학교 연구원 (Dept. of ECE, Cornell University)

※ 이 논문은 2012년도 정부(교육과학기술부)의 재원으 로 한국연구재단의 기초연구사업 지원을 받아 수행 된 것임(No. 2012-0004625) 용으로 구축 가능하며, 그리고 설치 및 운영이 용이하 다는 측면에서 지금까지 많은 연구 및 개발이 수행되어 져 왔다. 일반적인 다중 홉 무선 네트워크는 홉 간 통신 을 기반으로 하고 있는데, 인접 노드간의 간섭 및 매체 접근 제어로 인하여 주어진 대역폭 중 일부만 사용할 수 있다. 이러한 대역폭의 낭비를 줄여 보고자 하는 여 러 방법 중의 하나로 opportunistic 라우팅 기법이 제안 되었다. 이러한 opportunistic 라우팅 기법은 무선 통신 의 내재된 브로드캐스트의 특성을 이용한 것으로 지금 까지 다양한 구현 기법 및 성능분석에 관한 많은 연구 가 수행되어 왔다[1][2].

0 1 2 3 4 One-hop Transmission Opportunistic Delivery Interference to Opportunistic Delivery 5 6 Opportunistic Delivery Possible Transmission

Interference to Opportunistic delivery 그림 1. Opportunistic 전송에서의 링크 레벨 간섭 효과

Fig. 1. Link-level interference from a traffic flow with opportunistic transmission.

Opportunistic 라우팅의 수신 노드는 송신 신호를 에 러없이 수령한 노드들 중 하나가 선택되어지며, 일반적 으로 목적지 노드에 가장 근접한 노드가 선택되어진다. 이러한 방식의 전송은 홉 간 전송방식의 기존의 방식보 다 한 번의 전송으로 보다 많은 거리를 나아가게 하므 로 많은 성능의 향상을 기대하게 된다. 성능 향상 측면에서 보면 기존의 전통적인 홉 간 라 우팅 기법에 비하여 숏 홀(short-haul) 다중 홉 네트워 크 경로에 대하여서는 단일 데이터 스트림에 대하여 링 크 레벨 간섭 효과(한 노드의 전송이 다른 노드의 전송 을 방해하는 과정을 지칭함)가 적기 때문에 opportunistic 라우팅 방법을 적용할 경우 적지 않은 수 율의 향상을 예상할 수 있다. 그러나 롱 홀(long-haul) 다중 홉 네트워크 경로의 경우 목적지에 대한 패킷의 진행속도를 빠르게 할 수 있는 많은 opportunistic 전송의 기회가 존재하지만, 여 전히 종단간 수율의 측면에서는 성능향상의 정도는 크 지 않을 것으로 예상된다. 이는 네트워크 경로가 길수 록 동일 데이터 스트림으로 인한 노드들 간의 링크 레 벨 간섭 효과가 심해지기 때문이다. 예를 들면 그림 1 에서 노드 0로부터 노드 4로의 opportunistic한 전달의 기회는 노드 3, 5, 6의 있을 수 있는 전송 때문에 방해 를 받을 수 있다. 이에 본 논문에서는 opportunistic 라우팅의 성능에 대하여 링크 레벨 간섭 효과를 고려하여 원거리에 있는 출발지 노드와 목적지 노드사이에서의 단일 데이터 스 트림에 대한 최대 수율을 수식적인 방법으로 분석하고 자 한다. 이는 opportunistic 라우팅이 많은 성능향상을 가지고 온다는 기존의 연구 결과에 대한 확인이 된다. 숏 홀의 경우에는 RTS/CTS/ACK의 미디어 액세스 절 차의 단축효과로 인한 링크 레벨 간섭의 효과가 적은 관계로, opportunistic 라우팅의 효과가 분명해 보이나, 이를 롱 홀에 적용시킬 경우에는 그 성능 향상 효과를 확인할 필요가 있기 때문이다. 본 논문의 성능분석에서 사용된 네트워크 모델은 1 차원의 선형적인 노드 배치를 이용한다. 이와 같은 모 델은 일반적인 2차원 배치 혹은 3차원 배치와 비교해 제한적으로 보일 수 있으나, 분석의 용이함을 제공해 줄 뿐만 아니라, 이와 같은 모델의 분석 결과가 네트워 크의 전송 용량에 대한 링크 레벨 간섭 효과를 쉽게 이 해할 수 있게 해준다는 측면에서 의미가 있다. 다음은 본 논문의 성능 분석에 사용된 네트워크 모델 에 대한 가정이다. z 각 노드는 하나의 송신기/수신기를 가지고 있어 어느 한 시점에서는 송신 또는 수신만 가능하고 이를 동시에 수행할 수 없다. z 채널 액세스는 RTS/CTS/ACK의 MAC 계층 다 이알로그를 따른다. z 분석의 용이성을 위해 ACK 패킷은 송신 노드 및 수신 후보 노드 모두에게 에러없이 전달된다 고 가정한다. 이와 같은 가정은 ACK 패킷의 크 기가 아주 작고 또한 제어 패킷은 가장 낮은 저 속으로 전송된다는 측면에서 받아들여질 수 있 다. z 무선 네트워크상의 두 인접한 한 홉간의 노드사 이에 데이터 전송 용량은 C[bps]로 동일하다고

가정하고 홉 간 패킷의 전송 성공확률은 p라고 가정한다. 본 논문의 구성은 다음과 같다. Ⅰ장의 서론에 이어 서 Ⅱ장에서 관련연구를 기술하고, Ⅲ장에서 기존의 홉 간 전송방식에서의 최대 수율을 분석한다. 이어 Ⅳ장에 서 롱 홀 환경에서의 opportunistic 라우팅의 성능을 분 석하고, V장에서 결론을 맺는다. Ⅱ. 관련 연구 지금까지 opportunistic 라우팅에 대한 연구는 많이 수행되어 왔으나, 수식적인 분석을 통한 성능 분석에 대한 분야는 그리 많이 연구되어 오지 않았다. 더구나 기존에 수행되어 온 수식적인 분석도 주로 패킷 전달 속도의 상한 값이나 한 번의 전송으로 얻을 수 있는 최 대 수율 등으로 제한되어 왔다. 예를 들어 Zeng 등은 [3]에서 한 홉에서 얻을 수 있는 기대 수율에 대한 상한 값을 연구했으며, Jacquet 등은 [4]에서 opportunistic 라우팅의 패킷 전파 속도에 대한 상한 값을 제시하였 다. Li 등은 전역적인 스케줄링 대신 그래프 분할에 기 초한 지역적인 스케줄링 방법을 제안하였으며, 이 방법 은 종단 간 전송 지연 및 라우팅 계산 비용을 현저하게 감소시킨다고 주장하고 있다[5]. Cacciapuoti, Caleffi, 그 리고 Paura는 노드와 노드 사이의 우선 순위에 기반한 전송 비율의 정보가 제공된다는 전제하에, 성공적인 패 킷의 전달을 위한 평균 전송 횟수를 구하는 식을 도출 하였다[6]. Zeng, Lou, 그리고 Zhai는 opportunistic 라우 팅에 의한 종단간 최대 수율의 문제를 상호 간섭이 이 루어지는 노드사이의 링크의 관계를 나타내는 충돌 (conflict) 그래프를 이용한 최대 흐름을 나타내는 선형 방정식으로 나타내었다[7]. 이러한 opportunistic 라우팅에 대한 여러 분석 연구 들은 특정 트래픽 플로우를 전달하는 네트워크 노드들 사이의 링크 레벨 간섭 효과를 명시적으로 다루지 않고 있다. 이것은 opportunistic 라우팅의 성능을 분석할 때 아주 중요한 요소로서 반드시 고려되어져야 하는데, 그 이유는 특정 트래픽을 전달하는 네트워크 노드들사이 에서의 링크 레벨 간섭은 상호간의 깊이 연관되어 있어 opportunistic 라우팅의 성능을 크게 저하시키는 작용을 하기 때문이다[8]. Ⅲ. 기존 전통적인 라우팅 방식의 최대 수율 홉 간 전송 성공 확률은 p이므로 한 홉간에 패킷이 성공적으로 수신할 때까지의 평균 전송 횟수는 1/p이 된다. 그러므로 최대 수율은 pC가 된다. 두 홉의 경우에 는 출발지 노드와 그 다음 노드중 하나의 노드만 전송 이 가능하므로 최대 수율은 pC/2가 된다. 세 홉(그림 2 참조) 또는 그 이상의 홉에 대한 경로의 경우에는 연속 되는 3개의 노드중에 한 개의 노드만이 전송이 가능하 므로 최대 수율은 pC/3이 된다. 즉 그림 2에서 노드 2 가 노드 3에게 전송을 하게 되면 노드 1은 노드 2에게 전송을 할 수 없게 된다. 왜냐 하면 노드 2가 노드 1의 전송 데이터를 수신할 수 없기 때문이다. 또한 노드 0 도 노드 1에게 전송을 할 수 없는데, 이는 노드 1에서의 노드 0의 송신 데이터와 노드 2의 송신 데이터의 충돌 (히든 터미널 현상)을 피해야 하기 때문이다. 0 1 2 3 그림 2. 링크 레벨 간섭의 예 : 노드 2가 전송할 경우 노드 0 및 노드 1은 전송을 하지 못함

Fig. 2. An example of link-level inerference, where transmission of node 2 prevents node 0 and 1 from transmitting. Ⅳ. 롱 홀 다중 홉 무선 네트워크에서의 Opportunistic 라우팅의 최대 수율 롱 홀 다중 홉 무선 네트워크에서의 opportunistic 라 우팅의 최대 수율을 분석하기 위하여 다음과 같은 가정 을 추가로 한다. z 시스템은 정상상태에 있다. z 수신 후보 노드 수는 N 이다. z 목적지 노드에 가장 가까운 수신 노드가 ACK 패킷을 보내며. 이 ACK 패킷은 송신노드 및 다 른 후보 노드들이 모두 수신한다고 가정한다. ACK 패킷을 보낸, 목적지 노드에 가장 가까운 수신 노드는 수신 패킷을 포워딩하는 노드가 된 다. z 송신 노드는 ACK를 받지 못하면(즉 어떤 수신 후보 노드도 패킷을 수령하지 못한 경우에는) 재

0

1

2

N-1

N

T

₀

B

₀

B

₁

B

₂

B

_N-1

B

_N

p

_0,1

p

_0,2

p

_0,N-1

p

_0,N 그림 3. 롱 홀 다중 홉 무선 네트워크의 분석 모델

Fig. 3. Reception probabilities of node in a long haul multi-hop path.

전송을 수행한다. z 물리 레벨에서의 간섭에 대한 고려로서, 보다 가 까이 위치하고 있는 노드의 물리적인 신호크기는 보다 멀리 있는 노드로부터의 신호크기보다 훨씬 커서, 멀리 있는 노드로부터의 신호는 상대적으 로 무시된다. 만약 등거리 있는 두 개의 노드가 동시에 패킷을 전송하는 경우 어느 패킷도 성공 적으로 수신되지 않는다고 가정한다. 일반적으로 물리적인 신호의 간섭은 실제 네트워크 의 토폴로지나 송신노드 및 수신노드사이의 상대적인 위치, 무선 신호의 전파 조건 등에 영향을 받는다. 본 논문에서는 그러한 영향이 통합 반영된 결과로서 노드 i로부터의 패킷 전송이 노드 j에서 수신될 확률로서  를 가정한다. _를 구하는 방법은 본 논문의 영역을 벗어나는 부분이나, 이는 무선 전파의 전달 방식의 모 델링에 따라서, 또는 직접적인 측정을 통하여 이루어질 수 있다. 그림 3은 롱 홀 경로의 중간 노드로서 노드 0룰 가정 하고, 노드 0가 송신할 때 각 수신 노드에서의 opportunistic 라우팅에 의한 수신 확률을 나타낸 그림 이다. 그림에서 노드 i의 수신 확률은 그림에 표시된 바 와 같이 _로 나타낸다.



_를 재전송을 제외한 노드 0에서의 송신에 대한 수율이라고 하고,



_{}를



_의 최대 수율이라 가정한다. 또한



를 노드 i에서의 재전 송을 포함한 송신에 대한 수율이라고 가정한다.



_를 노드 i가 패킷을 전송하지 않고 유휴상태에 있 을 확률이라고 하면.



_는 다음과 같이 주어진다.



_{ }









_ (1)



_를 노드 0가 송신할 때 노드 i가 수신이 가능할 확률이라고 가정하자. 이는 노드 i가 송신중이 아닌 유 휴상태에 있어야 하며, 노드 i입장에서 노드 0보다 더 가까운 노드들 중 전송하는 노드가 없어야 하는 것을 의미한다. 앞서 시스템이 정상상태에 있다고 가정했으므로 다 음의 식이 성립한다.



_



_ ⋯ 



_{ ≦ } 



(2)



_를 노드 0가 한 번의 전송으로 후보 노드들 중 최 소 1개 이상의 노드들이 수신할 확률이라 하면



_는 다음과 같이 구해진다.



_ _



_   _



__{  }



_{  }              ⋯    __  _{  }_{  } ⋯   (3) 단 (3)식에서



_는 다음과 같이 주어진다.



_{ ,}











,



















, ⋯



_ _{  } 

_





    

_

 ( ≦  ≦



) (4)

p=1 p=0.9 p=0.8 p=0.7 p=0.6 p=0.5 TRAD. 0.333333 0.3 0.266667 0.233333 0.2 0.166667 OPP. N=1 0.333333 0.3 0.266667 0.233333 0.2 0.166667 N=2 0.333333 0.306667 0.278519 0.248889 0.217777 0.185185 N=3 0.333333 0.307852 0.280684 0.251808 0.221201 0.188843 N=4 0.333333 0.308104 0.281146 0.252434 0.221939 0.189636 N=5 0.333333 0.308159 0.281248 0.252572 0.222102 0.189811 N=6 0.333333 0.308171 0.281271 0.252603 0.222139 0.18985 N=7 0.333333 0.308174 0.281276 0.25261 0.222147 0.189859 N=8 0.333333 0.308175 0.281277 0.252611 0.222148 0.189861 TRAD. : traditional routing, OPP.:opportunistic routing

표 1. 롱 홀 다중 홉 경로에 대한 기존의 홉 간 라우팅 및 opportunistic 라우팅 의 최대 수율

Table 1. Maximum Throughput of Traditional Routing and Opportunistic Routing in Long-Haul Multi-hop Paths.

0.95 1 1.05 1.1 1.15 1.2 1 2 3 4 5 6 7 8 Candidate Size Ra ti o of M a xi m u m T h rou gh pu t o f O ppo rt u n is ti c R o ut in g t o T ra d it io n a l R o u ti n g p=0.5 p=0.6 p=0.7 p=0.8 p=0.9 p=1.0 그림 4. 롱 홀 다중 홉 무선 네트워크에서의 기존 라우 팅 방식과 opportunistic 라우팅 방식의 최대 수 율 비율

Fig. 4. The ratio of the maximum throughputs of the opportunistic routing and the traditional routing schemes for long-haul multi-hop paths.

위의 식에서 가 성립하므로, 최대 수율 _{}는 다음이 조건이 만족할 때 구할 수 있다.   ⋯    _  (5) 위의 분석으로부터, 기존의 홉 간 라우팅 방식과 opportunistic 라우팅간의 최대 수율을 구하였으며, 이 를 표 1에서 비교하였다. 그림 4는 두 수율의 비율을 나 타낸다. 표 1 및 그림 4의 비교에서 _{ }     를 가정 하였고, 수신 후보 노드의 수 N을 증가시키면서 두 방 식의 최대 수율의 변화를 보였다. 표 1 및 그림 4의 결과로부터, 롱 홀 다중 홉 무선 네 트워크에서의 opportunistic 라우팅에 의한 성능 향상 정도는 그리 크지 않다는 것을 알 수 있다. 특히 p=1일 때 opportunistic 라우팅에 의한 수율 향상은 전혀 없으 며, 다만 p가 작아질수록 그 효과가 다소 나타나고 있 다. 예를 들어 p=0.5이고, 후보 노드의 수가 아주 클 때, 최대 수율은 0.189로서 기존 전통적인 홉 간 라우팅의 0.166 보다 14%정도의 향상에 그치고 있다. 이러한 미 미한 수율 향상은 경로상의 단일 데이터 스트림에 의한 링크 레벨 간섭 효과의 결과이다. 본 연구의 결과로부터, opportunistic 라우팅은 예상 과는 달리 모든 환경에서 높은 성능향상을 가져오지는 않는다는 것을 알 수 있었다. 특히 롱 홀 다중 홉 경로 의 경우에는 성능향상이 없거나 있다 하더라도 미미한 정도의 성능향상만이 얻어질 수 있었다. 이러한 미미한 성능향상 정도는 opportunistic 라우팅을 도입할 때 요 구되는 시스템의 복잡성 등을 고려하면, 롱 홀 다중 홉 무선 네트워크의 경우에는 그다지 좋은 선택이라고 볼 수 없다. 그러므로 opportunistic 라우팅을 고려할 때는 숏 홀 환경에 국한하여해 함을 알 수 있다.

저 자 소 개 이 구 연(정회원) 1986년 서울대학교 전자공학과 (학사) 1988년 KAIST 전기및전자공학과 (석사) 1993년 KAIST 전기및전자공학과 (박사) 1993년～1996년 디지콤정보통신 연구소 1996년 삼성전자 1997년～현재 강원대학교 컴퓨터학부 교수 <주관심분야 : 이동통신, 네트워크보안, 인터넷, 초고속통신망, ad-hoc 네트워크> 이 용(정회원)-교신저자 1997년 연세대학교 컴퓨터과학과 (석사) 2001년 연세대학교 컴퓨터과학과 (박사) 1993년～1994년 디지콤정보통신 연구소 2001년〜2003년 한국정보보호진흥원 선임연구원 2004년〜2005년 코넬대학교 방문연구원 2005년〜2007년 삼성전자 통신연구소 책임연구원 2008년〜2010년 충주대학교 전자통신공학전공 조교수 2009년〜현재 코넬대학교 방문연구원

<주관심분야 : Mobile and Wireless Security, Ubiquitous Sensor Network, Wireless Mesh Network, Mobile Ad hoc network>

V. 결 론 본 논문에서는 롱 홀 다중 홉 무선 네트워크에서의 opportunistic 라우팅에 의한 최대 수율을 분석하였다. 분석 결과 opportunistic 라우팅에 의한 수율 향상 정도 는 미미함을 보였으며, 이는 기존의 opportunistic 라우 팅이 큰 성능향상을 가져올 것이라는 기존의 기대에 반 한 결과이다. 특히 p=1일때는 전혀 성능향상이 없었으 며, 일반적으로 통용되는 홉 간 최소 패킷 에러 확률의 경우(0.8 정도의 p값)에도 성능향상 정도는 5% 정도이 었다. 이와 같은 연구는 opportunistic 라우팅을 도입할 때 롱 홀 환경에서는 신중해야 함을 의미하고, 특히 opportunistic 라우팅 도입 시에 시스템이 복잡해지는 것을 고려하면 오히려 기존의 홉 간 라우팅이 더 선호 될 수도 있음을 알 수 있다. 참 고 문 헌

[1] S. Biswas and R. Morris, “ExOR: Opportunistic Multi-Hop Routing for Wireless Networks,” in Proc. Sigcomm Conf., 2005, pp. 133-143

[2] H. Liu, B. Zhang, H. T. Mouftah, X Shen and J. Ma, “Opportunistic Routing for Wireless Ad Hoc and Sensor Networks: Present and Future Directions,” IEEE Communications Magazine, Dec. 2009, pp. 103-109

[3] K. Zeng, W. Lou, J. Yang and D. R. Brown III, “On Throughput Efficiency of Geographic Opportunistic Routing in Multihop Wireless Networks,” Mobile Networks and Applications, vol. 12, no. 5, Dec. 2007, pp. 347–357

[4] P. Jacquet, B. Mans, P. Mühlethaler and G. Rodolakis, “Opportunistic routing in wireless ad hoc networks: upper bounds for the packet propagation speed,”IEEE Journal on Selected Areas in Communications, vol.27, no. 7, 2009, pp. 1192-1202

[5] Y. Li, Y. Liu, L.Li and P. Luo, “Local scheduling scheme for opportunistic routing,” in Proc. WCNC’09, 2009, pp.2432-2437

[6] A. S. Cacciapuoti, M. Caleffi and L. Paura, “A theoretical model for opportunistic routing in ad hoc networks,” ICUMT’09,2009, pp. 1-7

[7] K. Zeng, W. Lou and H. Zhai, “On End-to-End Throughput of Opportunistic Routing in Multirate and Multihop Wireless Networks,” in

Proc. IEEE INFOCOM 2008. April 2008, pp. 816 –824