An approximation algorithm for dominating nodes selection in multi-channel multi-radio wireless sensor networks
In this paper, we study the dominating selection optimisation problem with multiple channels and multiple radios in wireless sensor networks. The objective is to maximise the number of targets covered while selecting at most k nodes and at most k(i) channels with each selected node v(i). Our problem is a general case of the maximum coverage problem. We propose two algorithms: the first one is based on linear programming and PIPAGE rounding, in which its approximation ratio is 1/K(1-(1-1/m)(m)), where m is the number of the dominating nodes and K = max k(i). The second algorithm is based on greedy strategy with low time complexity. The simulation shows that the both two algorithms have good performance.
approximation algorithm dominate node selection multi-channel multi-radio wireless sensor networks