Modeling and worst-case dimensioning of cluster-tree wireless sensor networks

Time-sensitive Wireless Sensor Network (WSN) applications require finite delay bounds in critical situations. This paper provides a methodology for the modeling and the worst-case dimensioning of cluster-tree WSNs. We provide a fine model of the worst-case cluster-tree topology characterized by its depth, the maximum number of child routers and the maximum number of child nodes for each parent router. Using Network Calculus, we derive “plug-and-play” expressions for the endto- end delay bounds, buffering and bandwidth requirements as a function of the WSN cluster-tree characteristics and traffic specifications. The cluster-tree topology has been adopted by many cluster-based solutions for WSNs. We demonstrate how to apply our general results for dimensioning IEEE 802.15.4/Zigbee cluster-tree WSNs. We believe that this paper shows the fundamental performance limits of cluster-tree wireless sensor networks by the provision of a simple and effective methodology for the design of such WSNs.

Sequencing cutting patterns with colored interval graphs

The problem addressed here originates in the industry of flat glass cutting and wood panel sawing, where smaller items are cut from larger items accordingly to predefined cutting patterns. In this type of industry the smaller pieces that are cut from the patterns are piled around the machine in stacks according to the size of the pieces, which are moved to the warehouse only when all items of the same size have been cut. If the cutting machine can process only one pattern at a time, and the workspace is limited, it is desirable to set the sequence in which the cutting patterns are processed in a way to minimize the maximum number of open stacks around the machine. This problem is known in literature as the minimization of open stacks (MOSP). To find the best sequence of the cutting patterns, we propose an integer programming model, based on interval graphs, that searches for an appropriate edge completion of the given graph of the problem, while defining a suitable coloring of its vertices.