Finding a Maximal Weighted Independent Set in Wireless Networks

This paper introduces MWIS, a distributed algorithm for the efficient determination of a maximal weighted independent set in the topology graph G of a wireless network. Motivated by the observation that the problem of partitioning wireless nodes into clusters easily reduces to the problem of finding a maximal weighted independent set of nodes, the proposed algorithm is described by taking into account two main characteristics of wireless networks, namely, the broadcast nature of the wireless medium and the possibility to support nodes mobility. MWIS is executed at each node by means of fast message triggered procedures that require the sole knowledge of the topology local to the node. Moreover, its time complexity is proven to be bounded by a topology dependent parameter of the network (the stability number (G) of the network topology graph G), rather than by the invariant number n of the network nodes. Based on this result, and by using a well known result about (G) in the theory of random graphs the paper concludes with a brief discussion on the average time complexity of MWIS.