A Scenario Based Heuristic for the Robust Shortest Path Tree Problem*

IPv6 Low Wireless Personal Area Networks (6LoWPAN) is the most promising technology for implementing the Internet of Things (IoT). In order for IoT to become a reality, many challenges still need to be addressed, such as the design of energy-efficient routing protocols. The latter have to be specially resilient to high variations in transmission quality, due to constant changes in the network surrounding, which is characteristic of IoT. The most promising of these protocols is the IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL). In this paper, we model the RPL routing protocol as a Robust Shortest Path Tree (RSPT), a robust variation of the Shortest Path Tree that considers the uncertainty in the link quality to improve the resilience in network routing. In RSPT, the cost of each arc is defined by an interval of feasible values instead of a single value. Then, we extend a Scenario-Based heuristic (SBA), a O(n · log n) 2-approximation algorithm for this problem that can be implemented in the RPL protocol. We also implement a Mixed Integer Linear Programming (MILP) formulation for RSPT, which is used to assess the quality of our algorithm. Computational results showed that the exact algorithm based on the MILP formulation was able to find optimal solutions for all networks with up to 100 sensors in less than 8 seconds. SBA produces an average relative optimality gap below 7% for the largest networks with 200 sensors.