The robust shortest path tree problem: formulations and algorithms

Abstract

IPv6 Low Wireless Personal Area Networks (6LoWPAN) is the most promising technology for implementing the so called Internet of Things. In order for this technology to become a reality, routing protocols need to be resilient to variations in the links quality, due the constantly changes in the channels. The most promising of these protocols is the IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL). In this work, the RPL routing protocol was extended to consider the uncertainty in the link quality. The RPL Robust routing problem is modeled as a Robust Shortest Path Tree problem (RSPT). Three heuristics for the RSPT are developed, besides two different mathematical formulations, and an exact algorithm based on one of the proposed formulations. The proposed algorithms are compared with two algorithms from the literature. One of the proposed heuristics has presented better results that the literature algorithms, and its can be implemented as a routing protocol for 6LoWPANs.