Method and apparatus to trigger dag reoptimization in a sensor network

Abstract

In one embodiment, a probing technique allows a root node to determine whether to trigger reoptimization of a computer network represented by a directed acyclic graph (DAG) without injecting unnecessary traffic into the network. The root node may store and maintain information indicative of an ideal shape or topology of the DAG. During a normal DAG maintenance operation, the root node may transmit a DAG discovery request (probe request) that is configured to probe each node within the DAG for information used to determine a current topology of the DAG. In response, each node may record the information, e.g., routing and non-routing metrics, in a DAG discovery reply (probe reply) that is propagated to the root node. Upon receiving one or more replies, the root node may analyze the metrics to determine whether the current topology of the DAG deviates from the ideal DAG topology. The root node may thus determine DAG topology deviation upon probing at minimal cost. A number of algorithms may then be used to determine whether reoptimization, i.e., global repair, of the DAG is is required and, if so, the root node may dynamically trigger the global repair.