Boosting sensor network calculus by thoroughly bounding cross-traffic

Sensor Network Calculus (SensorNC) provides a framework for worst-case analysis of wireless sensor networks. The analysis proceeds in two steps: For a given flow, (1) the network is reduced to a tandem of nodes by computing the arrival bounds of cross-traffic; (2) the flow is separated from the cross-traffic by subtracting cross-flows and concatenating nodes on its path. While the second step has seen much treatment, the first step has not at all. This is in sharp contrast to the fact that arrival bounding takes roughly 80% of the total analysis time and is equally crucial for the tightness of the bounds. Therefore, we turn our attention to this first SensorNC analysis step with the goal to boost the performance and applicability of the overall framework. The main technical contribution is a generalized version of the concatenation theorem within the SensorNC setting. This generalization is instrumental in simplifying and streamlining the cross-traffic arrival bound computations such that run times can be reduced by more than a factor of 5. Even more important, it enables a localization of the information necessary to execute the calculations at the node level, thus enabling a distribution of the SensorNC analysis within a self-modeling WSN.