Scatternet formation in high-rate wireless personal area networks by integer linear programming

Scatternet formation is one of the most important issues of emerging Wireless Personal Area Networks (WPANs). Numerous papers pointed out that the performance of a WPAN highly depends on the scatternet structure; however, for next generation WPANs (IEEE 802.15.3 and 802.15.4) the issue of scatternet formation is not discussed in the literature so far. This paper presents the techniques, constraints and effects of scatternet formation. First, the theoretically based problem is formulated in Integer Linear Programming (ILP) framework. Two heuristic methods are proposed for high-rate WPANs (802.15.3), which can be extended for low-rate WPANs (802.15.4) as well. The constructed networks are analyzed based on two metrics: (1) total network load, (2) amount of piconets. We show that network performance highly depends on the used algorithm: the network load can be reduced by up to 30% by using a proper scatternet formation algorithm. Furthermore, the scatternet can be optimized depending on the actual network traffic and individual objectives..