Opportunistic Communication Protocols for End-to-End Throughput Enhancement in Multirate Multihop Wireless Networks

Abstract

Wireless multihop communication still needs more improvement as its scale, traffic intensity, node density, and/or node speed becomes more challenging than originally conceived. Being readily-available in most of 802.11 radios, multirate capability appears to be useful to address some of these issues and is particularly helpful in high-density scenarios where inter-node distance is short, making it possible to utilize high data rates and thus demanding a prudent multirate adaptation algorithm. However, communication at high data rates mandates a large number of hops for a given node pair in a multihop network and thus, can easily be depreciated as per-hop overhead at several layers of network protocol is aggregated over the increased number of hops. Moreover, exploiting the multirate capability in mobile ad hoc networks (MANETs) is more complex than in single-hop WLANs because of the rate-distance and rate-hop count trade-offs, and has not been tackled by many researchers while rate adaptation has been an active area of research in the context of WLANs and wireless mesh networks (WMNs). Those developed for WLANs prefer a high rate as long as the channel condition allows but a high rate is not always desirable in MANETs because this mandates a shorter communication range or a more number of hop count for a given source-destination pair. Those developed for WMNs (e.g., Srcr) may not be directly applicable because proactive updates of link cost, which is typically approached in WMNs, becomes prohibitively expensive in MANETs as the updates must be performed more often in the presence of mobility and separately at all available rates. In this dissertation, we propose two protocols for reducing MAC- and routing-layer overhead in multirate multihop wireless networks: (i) Multihop Transmission OPportunity (MTOP) and (ii) Path-centric on-demand Rate Adaptation for MANETs (PRAM). The key idea of them is to forward a packet back-to-back without contention, and to take path-centric or top-down approach to rate adaptation, such that they can reduce MAC- and routing-layer overhead, respectively. First, MTOP allows a frame to be forwarded a number of hops consecutively to minimize the MAC-layer overhead between hops. This seemingly collision-prone multihop nonstop forwarding is proven to be safe via analysis and USRP/GNU Radio-based experiment in this dissertation. The idea of MTOP is in clear contrast to, but not mutually exclusive with, the conventional opportunistic transmission mechanism, referred to as TXOP, where a node transmits multiple frames back-to-back when it gets an opportunity in a single-hop WLAN. Second, a unique feature that sets PRAM apart from most of previous studies is its path-centric or top-down approach. While others focus on finding the best data rate for each link and offering a routing path as a collection of links at their best rates, PRAM finds the best data rate for a source-destination pair and then, dynamically adapts it based on path lifetime and other factors. Another distinctive feature of PRAM is that it can be seamlessly incorporated with an on-demand routing protocol. We performed our simulation study to evaluate the performance of the proposed protocols via OPNET and ns-2 for MTOP and PRAM, respectively. Our simulation study results show that each proposed protocols shows improved performance over comparison protocols under a wide range of network scenarios.

무선 멀티 홉 통신은 최초의 구상과는 달리 그 규모, 트래픽량, 노드 밀도, 노드 이동 속도 등 고려되어야 할 다양한 조건들이 생겨남에 따라 성능 개선 및 향상이 요구되고 있다. 보편화된 대부분의 802.11 기반의 장치들이 멀티 레이트 기능을 지원함에 따라 멀티 레이트를 활용하여 위와 같은 이슈들을 다루는 것이 효과적일 수 있으며, 특히 노드간 거리가 짧은 높은 노드 밀도의 시나리오에서는 멀티 레이트 적응 알고리즘을 통해 높은 데이터 레이트를 적극적으로 활용함으로써 멀티 레이트 기능을 유용하게 사용할 수 있다. 그러나 멀티 홉 네트워크에서 높은 데이터 레이트로의 통신은 특정 노드 쌍 간에 더 많은 홉 수를 유발시키고 늘어난 홉 수로 인해 네트워크 프로토콜의 여러 계층에서의 오버헤드가 누적되어 발생하기 때문에 높은 데이터 레이트 사용의 이점이 떨어지게 된다. 또한, MANET 환경에서 멀티 레이트 기능을 다루는 것은 레이트-거리 및 레이트-홉 수 간 trade-off로 인해 싱글 홉 무선랜에서의 경우보다 훨씬 더 복잡하다. 데이터 레이트 적응 문제는 무선랜이나 무선 메쉬 네트워크에서 다양한 연구가 많이 진행되었으나 MANET 환경에서는 많이 다뤄지지 않았다. 무선랜을 위해 개발된 알고리즘들은 채널 상태가 지원하는 가장 높은 레이트를 선택하고자 하였으나 MANET 환경에서는 높은 레이트로의 전송은 짧은 통신 거리 또는 소스-목적지간 더 많은 홉 수를 의미하기 때문에 원치 않는 결과를 가져올 수 있다. 무선 메쉬 네트워크를 위해 개발된 알고리즘들은 proactive 방식으로 링크 비용을 업데이트하기 때문에 MANET과 같이 노드 이동 및 링크 변화가 존재하는 경우에는 업데이트 오버헤드로 인해 MANET으로의 직접 적용은 어렵다. 본 논문에서는 맥 계층 및 라우팅 계층의 오버헤드를 줄이기 위한 MTOP (Multihop Transmission OPportunity)과 PRAM (Path-centric on-demand Rate Adaptation for MANETs)의 두 가지 프로토콜을 제안한다. 첫번째로 MTOP 프로토콜은 각 홉 간 맥 계층 오버헤드가 최소화될 수 있도록 하나의 프레임을 연속적으로 여러 홉을 거쳐 전달하도록 한다. 이러한 방식을 사용함으로써 연속적인 각 전달마다 경쟁의 부재로 인해 충돌 발생이 빈번할 것으로 예상될 수 있지만 본 논문에서는 분석과 USRP/GNU Radio 기반 실험을 통해 이러한 경우라도 프레임이 안전하게 전달될 수 있음을 보였다. MTOP의 개념은 싱글 홉 무선랜에서 기회적으로 여러 개의 프레임을 연속적으로 전송하는 기존의 TXOP 프로토콜과 분명히 구별되며 경우에 따라 상호 보완적으로 사용될 수도 있다. 두번째로 PRAM 프로토콜은 기존의 연구들과 달리 패스 중심 또는 상의하달식의 접근 방식을 취한다는 고유한 특징을 가진다. 기존 연구에서는 각 링크에 초점을 맞추어 특정 링크에서의 최적의 데이터 레이트를 선정하고 이 링크 정보들의 집합 내에서 라우팅 패스를 찾고자 하였다. 반면, PRAM은 소스-목적지 쌍에 대해 최적의 데이터 레이트를 찾고 패스 수명 등의 요소를 고려하여 이를 적응적으로 변화시킨다. PRAM은 다른 기존의 on-demand 라우팅 프로토콜과 잘 통합될 수 있다는 특징도 가진다. 제안하는 프로토콜의 성능을 평가하기 위해 OPNET과 ns-2를 사용하여 시뮬레이션을 수행하였다. 시뮬레이션 결과 MTOP과 PRAM 프로토콜은 비교 프로토콜들에 비해 다양한 네트워크 시나리오에서 향상된 성능을 제공할 수 있음을 보여 주었다.