Tree-based routing protocols in low-rate wireless mesh networks usually have the detour problem in return for the no route discovery overhead. In this paper, we propose a novel routing protocol, named Incre-mental Path Reduction (IPR), which incrementally shortens inefficient detoured path as more packets are de-livered. In IPR, data packets are delivered along the tree route in use by using 1-hop broadcast, enabling neighbor nodes to learn about the data packets’ hop count. Using the hop counts, each node estimates their residual hop count to destination. As a result, each forwarder selects next hop node which has small residual hop count. In this way, IPR incrementally reduces detoured path and shorten the route as more packets are delivered. To verify our protocol, we applied IPR to the representative tree routing protocols in ZigBee, Shortcut tree routing, and RPL, and evaluated the path stretch and delivery ratio as well as control packet overhead. Simulation results show that IPR significantly enhances the overall routing metrics for any types of tree-based routing protocols.
Low-Rate Wireless Mesh Networks에서 리소스의 효율적인 운용을 목적으로 트리 기반의 라우팅 기법을 채택하여 사용한다. 하지만 트리 기반의 라우팅 기법은 트리 구조를 따라 라우팅 경로가 설정되기 때문에, 점대점 통신에서 있어서는 우회 경로를 갖는 문제를 갖는다. 우회 경로 문제는 네트워크 트레픽이 루트 주변으로 집중되는 현상를 야기시켜, 패킷 전달율 저하, 전달 지연시간 등 네트웍 성능 저하를 발생시킨다.
본 논문에서는 트리 기반의 라우팅 프로토콜이 가지는 우회 경로 문제를 해결하기 위해, 점진적 경로 개선 알고리즘인 IPR(Incremental path reduction)을 제안하였다. IPR은 트리 기반 라우팅 프로토콜이 생성한 경로를 따라 패킷을 전달하면서, 경로를 줄일 수 있는 기회를 찾아 라우팅 홉을 줄여가는 알고리즘이다. IPR에서 최초 경로는 트리 기반 라우팅을 통해 설정되며, 설정된 경로를 통해 각 포워딩 노드는 소스로부터의 홉 거리를 데이터 패킷에 담아 1홉 브로드케스트 형태로 전달한다. 주변 이웃 노드들은 포워딩 노드의 홉정보를 이용하여, Residual 홉 정보를 예측, 단축 경로를 선택할 수 있다. 또한 단축된 홉정보를 1홉 브로드케스트하여 주변 포워딩 노드들이 새로운 라우팅 경로를 설정할 수 있도록 한다. 이러한 메커니즘으로 IPR은 라우팅 경로를 단축할 수 있을 뿐 아니라, 점진적으로 우회 경로를 개선시킨다. 결과적으로 루트 노드로 집중되었던 트레픽이 분산되면서 패킷 전달률이 향상 된다. 시뮬레이션을 통해 IPR은 적은 오버해드로 대표적인 On-demand 방식인 AODV와 비슷한 경로 Path stretch를 가지는 것을 확인하였다. 또한 기존 연구와 달리 알고리즘에 대한 제약 사항이 없어 어떠한 트리 기반의 라우팅 프로토콜에 적용할 수 있다. 마지막으로 본 논문에서는 수학적 모델링을 통해 IPR을 Mobile Node에 적용했을 때 발생하는 컨트롤 메시지 오버해드와 개선된 라우팅 경로를 통해 절약하는 전달 비용에 대한 상관 관계를 분석하였다. 그리고 Service to Mobility Ratio (SMR)이 클 수록 IPR이 갖는 컨트롤 메시지 오버해드는 무시할 수 있을 정도로 작아진다는 결론을 맺을 수 있었다.
