Routing tree implementation based on semimatching algorithm(s)

Abstract

This paper proposes and evaluates the variation of an algorithm for optimal semi-matching, based on the Hungarian method. The proposed algorithm balances the parent-child vertexes in a bipartite graph and can be applied to a wireless sensor network as an algorithm for building virtual routing tree topology. Virtual routing tree topology optimizes the minimum number of message hops to the sink and load balancing. The proposed algorithm runs faster than other compared methods. Virtual topology (spanned tree) is used during very simple routing protocol. Experimental results show that the proposed algorithm preserves the energy, excludes bottle necks, red spots, and expands the lifetime of a network.