Parallel and distributed computations of maximum independent set by a Hopfield neural net embedded into a wireless sensor network

摘要

This paper, as the first one in a three-paper sequence, presents a proposed framework to employ a wireless sensor network as a hardware computation platform for fully parallel and distributed computation of maximum independent set of a given graph through a Hopfield neural network. Theoretical and mathematical foundations of the proposed framework will be discussed. Mapping the maximum independent set problem to Hopfield neural network dynamics is presented. This is followed by the demonstration of embedding the Hopfield neural network as a static optimizer into the wireless sensor network in fully parallel and distributed mode. The outcome is a wireless sensor network operating as a parallel and distributed computing hardware platform for a Hopfield neural network configured to solve a static optimization problem. The nesC-TinyOS model of the proposed computational framework and the corresponding simulation study are deferred to the second and third papers, respectively, in the three-paper sequence.