A hybrid approach to evaluate the complexity of RCA strategies in WSNs

Since radio channel allocation (RCA) is usually formulated as an NP-hard problem, most existing strategies use heuristic approaches to find sub-optimum solutions with unknown complexity. As an indicator to the complexity, computational scale (CS) is defined as the number of channel reallocations until a network reaches a convergence state. In this paper, we propose a hybrid approach to evaluate the CS of RCA strategies in WSNs. First, we propose a simple relation model to describe the interference relation between a cluster head (CH) and its neighboring CHs. Second, for one of the simplest cases in the relation, we find an analytical solution for the CS and validate it by simulations. Third, for more general cases, we combine the cases with similar CS means by using one-way ANOVA and find the upper bound of the CS with extensive simulations. It is demonstrated by simulations that the hybrid approach is simple and accurate as compared to the traditional intuitive comparison methods.