Distributed Topology Control with SINR Based Interference for Multihop Wireless Networks

In this paper, a distributed approach to topology control (TC) is proposed where the network topology is established considering interference and routing constraints. This optimization problem however involves link scheduling and power assignment under SINR constraint, which is an NP hard problem. Opting for heuristics rather than exact approach, the proposed algorithms in the literature, either cannot guarantee the quality of the solution, or approximate the interference (protocol interference model) rather than using realistic SINR models. There is also lack of distributed exact/approximation approaches which can reduce complexity and provide practical solutions. Here, we propose a distributed approximation algorithm using column generation (CG) with knapsack transformation on the SINR constraint. Particle Swarm Optimization (PSO) is integrated with CG, to provide robust initial feasible patterns. The results show that, DCG-PSO with knapsack transformation increase the solvable instances three fold in terms of number of nodes, in comparison to the state-of-art approaches. The links are scheduled with less power, shorter scheduling lengths and reduces the computation time at lower penalty cost.