Interval graph based energy efficient routing scheme for a connected topology in wireless sensor networks

Energy conservation has always been a major issue in wireless sensor network since wireless sensors spend lots of energy while sensing, receiving and transmitting signals, meanwhile network lifetime decreases. Excessive power usage in transmission among the sensors can be reduced by designing an energy efficient routing topology which reduces nodes’ energy consumption by abandoning those links which are highly energy expensive. In this paper, energy optimizing algorithms are taken over those wireless sensor network whose graphical layout formation can be a ‘connected bidirectional interval graph’, in which each node has been assigned with an appropriate power interval to hold network communication. Two new polynomial time algorithms are proposed to optimize energy consumption over the network subject to constraint that the resultant network topology remains strongly connected with minimum number of required links. Both the algorithms work to evaluate an energy optimal path cover whose path components combine to result an energy efficient connected routing structure (spanning path/tree) in an interval graph, reduces power usage over links and nodes in wireless sensor network. Optimization of maximum transmission cost in worst case scenario over a maximum weighted bidirectional interval graph and reduction of maximum power consumption limit of nodes in an interval weighted interval graph to the minimum possible value are also discussed.