Synchronous Distributed Greedy Weighted Graph Matching Algorithms For Wireless Sensor Networks

Wireless Sensor Networks (WSN) consist of devices that can communicate with each other without using any fixed infrastructure. These devices can gather necessary information from the environment via their sensors and share collected data with each others. WSNs can be modelled with graphs (G (V, E)) where V is the set of vertices (nodes) and E is the set of edges. Graph theoretical structures such as graph matching can be used to solve various problems such as backup assignment in WSNs. With this aim, we first design a synchronous distributed weighted graph matching algorithm based on Hoepman's algorithm. After this the synchronous algorithm is improved by using overhearing method to design ICO algorithm. Proposed ICO algorithm aims to decrease the transmitted message count for graph matching operation by applying in-network processing. These algorithms are tested on various settings having different node counts and degrees in TOSSIM simulator by comparing with each other. The results of these extensive tests reveal us that ICO is more effective in terms of energy consumption and transmitted bytes.