Research On Distributed Maximal Independent Set Algorithm And Its Application In Wireless Sensor Network

The maximum independent set(MIS) problem is a classical combinatorial optimization problem in graph theory, which is NP completed. The optimization of MIS algorithm in the distributed environment(for example: sensor networks) has important significance on efficiency and stability of the distributed system. Recently, Afek et al. were inspired by the biological growth mechanism, who proved a linear time complexity, space complexity of the distributed MIS algorithm(Science 2011). However, how to apply Afek-MIS algorithm in sensor network, especially in the physical interference(i.e. Signal-to-Interference-Plus-Noise-Ratio, SINR) model, the analysis and improvement of this algorithm is still a problem to be solved.This article is on the analysis and improvement of Afek-MIS algorithm in the distributed sensor networks SINR model. Through the theoretical analysis, it proved that the node degree of MIS algorithm is restricted by the path loss exponent and signal-to-noise ratio of SINR model. Meanwhile, derive the corresponding formula. Simulation and analysis results by using NetLogo and Matlab software: the greater the path loss exponent and the signal to noise ratio value are, the smaller the node degree is, the longer the running time of MIS algorithm is, and vice versa.That is the path loss exponent, signal-to-noise ratio is inversely proportional to the node degree, proportional to the running time of MIS algorithm. Moreover, the smaller the node degree is, the looser the network distribution is, nodes are not closely connected, the running time of MIS algorithm is longer; with the increase of the degrees of nodes, the nodes connected with each other more closely, the running time of MIS algorithm is faster. The studies of this paper contribute to the application of Afek-MIS algorithm in distributed sensor networks.