Approximation Algorithmic Performance for CEDS in Wireless Network

A well-organized design of routing protocols in wireless networks, the connected dominating set (CDS) is widely used as a virtual backbone. To construct the CDS with its size as minimum, many heuristic, meta-heuristic, greedy, approximation and distributed algorithmic approaches have been anticipated. These approaches are concentrated on deriving independent set and then constructing the CDS using UDG, Steiner tree and these algorithms perform well only for the graphs having smaller number of nodes. For the networks that are generated in a fixed simulation area. This paper provides a novel approach for constructing the CDS, based on the concept of total edge dominating set. Since the total dominating set is the best lower bound for the CDS, the proposed approach reduces the computational complexity to construct the CDS through the number of iterations. The conducted simulation reveals that the proposed approach finds better solution than the recently developed approaches when important factors of network such as transmission radio range and area of network density varies