A study on weighted graph matching algorithms for wireless sensor networks

Wireless Sensor Networks (WSN) consist of devices that can communicate each other without using any fixed infrastructure. These devices can gather necessary information from 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, in this thesis Hoepman Algorithm that is one of the greedy asynchronous distributed weighted matching algorithm has been modified to run for synchronous WSNs systems. After this designed synchronous algorithm is improved by using overhearing method to design ICO algorithm. These algorithms are tested on various settings in TOSSIM simulator by comparing central algorithm. Result of these tests showed that ICO is more effective in terms in terms of energy consumption and transmitted bytes than Senkron Hoepman and central algorithm.