Dominating Set Based Topology control for Life-time Maximization in Wireless Sensor Networks

Dominating Set Based Topology control for Life-time Maximization in Wireless Sensor Networks

Kaviya P, Elavarasi G, Nivetha S

Kamaraj College of Engineering and technology, Virudhunagar

Abstract – An important issue in wireless sensor networks is to prolong networks life time. Sensors are hard to recharge, since it is battery powered. A set of active sensors are chosen to pro- vide better coverage which perform sensing and data transfer- ring. In this work, the Connected Dominating Set (CDS) has been recommended to serve as a virtual backbone which pro- vides coverage and connectivity. This algorithm will also re- duce routing overhead and improve the network life time with energy efficient routing.

Index Terms Wireless sensor networks, Connected Dominating Set, Coverage and Connectivity, residual energy.

1. INTRODUCTION

   A Wireless sensor network consists of a large number of sensor nodes that are densely deployed. These nodes are able to perform sensing as well as processing and are addi- tionally capable of communicating with each other. Sensors collect the data and transmit to sink node using hop-by-hop communication. Sensor nodes are used in different applica- tions. The military applications include surveillance and monitoring, guidance systems of intelligent missiles. Sen- sors are also used in environmental application habitat ex- ploration of animals, forest fire and flood detection.

   An important issue in WSNs is energy management, battery power and better coverage. One of the issues is den- sity control. A subset of sensor nodes operates in the active mode, to conserve energy. The two requirements are: (1) coverage: The area that can be monitored by a set of sen- sors. (2) Connectivity: Sensor nodes collect the information and relay back to data sinks or controllers.

   Topology control is an iterative process. Topology control is used by wireless ad hoc and sensor networks. Many cen- tralized and distributed algorithms ensure topology control. The main aim of topology control is to save energy, to re- duce interference between nodes, extend lifetime of the

   • Kaviya.P, is with the Department of Information Technology, Kamaraj College of Engineering and Technology, Virudhunagar, India 626001.

   • G.Elavarasi is with the Information Technology, Kamaraj College of Engineering and Technology, Virudhunagar, India 626001.

   • S.Nivetha is with the Information Technology, Kamaraj College of Engineering and Technology, Virudhunagar, India 626001.

   networks. Topology control involves two mechanisms: To- pology construction and Topology Maintenance.

   The connectivity framework requires a set of ac- tive sensors to be connected all the time. This condition is significantly necessary for the communication between sen- sors and the sink in operation such as data reporting, query propagating, and forwarding of control messages.

   A Connected Dominating Set (CDS) based localized mechanism is proposed to provide fault tolerant topology control. Initially, a basic backbone (CDS) is constructed. CDS is an energy-efficient mechanism which constructs a connected backbone in order to provide both coverage and connectivity.

   The rest of the paper is categorized as follows. We dis- cuss previous works on related topics in Section II. Section III describes CDS backbone selection algorithm in detail. Section IV provides the simulation results include CDS size, energy consumption, and delay for coverage and con- nectivity mechanism. Section V finally concludes the paper.

2. RELATED WORKS

Hakki Bagci, et al [1] proposed a Disjoint Path Vector (DPV) Algorithm. DPV are guaranteed to satisfy k-vertex super node connectivity. This algorithm finds the shortest path and then to transmit the data. The total power con- sumption is minimized.

Mohamed Younis, et al [2] discussed a cone-based dis- tributed topology-control (CBTC) algorithm.They have focused on network topology management techniques for tolerating/handling node failure in WSNs. They have identi- fied the reactive and proactive methods to ensure the net- work connectivity and to prolong networks lifetime.

Jie Wu, et al [3] proposed a simple and efficient distrib- uted algorithm for calculating connected dominating set in ad hoc wireless networks, where connections of nodes are determined by geographical distances of nodes. This algo- rithm prolongs the life span of each node and balance the energy consumption in the network.

Khaled M. Alzoubiet al [4] explained a minimum con- nected dominating set (MCDS). MCDS for the unit-disk- graph is constructed with a constant approximation ratio, and linear time and linear message complexity. This algo- rithm is fully localized, and does not depend on the span- ning tree. The message length is O(log n) bits.

Ivan Stojmenovic et al [5] proposed a localized domi- nating set algorithm to significantly reduce or eliminate the communication overhead of a broadcasting task. Also this algorithm maintains the positions of neighboring nodes. Existing dominating sets are improved by using node de- grees instead of their ids as primary keys.

Jamil A. Shaikh et al [6] proposed new metrics for source-independent localized dominating set, based on combinations of node degrees and remaining energy levels, for deciding activity status. Also they proposed CDS scheme to prolong network life while preserving connectivi- ty.

Fei Dai et al [7] proposed simple and efficient localized algorithm that can quickly determine a CDS in ad hoc net- works. The efficiency of dominating-set based routing mainly depends on the overhead, introduced in the for- mation of the dominating set and the size of the dominating set. A localized formation of a connected dominating set called marking process and dominating-set-based routing. The dominant pruning rule to reduce the size of the domi- nating set.

Lu Ruana et al [8] described a connected dominating set is a subset of vertices. Every vertex is either in the subset or adjacent to a vertex in the subset and the sub graph induced by the subset is connected. A minimum connected dominat- ing set is such a vertex subset with minimum cardinality. It represents a new one-step greedy approximation with per- formance ratio ln + 2 where is the maximum degree in the input graph. The interesting aspect is that the greedy poten- tial function of this algorithm is not sub-modular.

Zheng Gengzhong, et al [9] proposed a topology control techniques.To provide energy efficient control topology structure of sensor networks, the common approaches are to adjust the transmission power of sensors and to dynamically schedule sensors cycle.

Masoumeh Haghpanahi et al [10] proposed a new nota- tion of connectivity called path-implement ability. It repre- sents the ability of sensor nodes to relay traffic along a giv- en direction field. Also they proposed a point MAC and routing protocol to forward traffic along the flow field.

IV. PROPOSED WORK

In wireless sensor network where the source node sense and send the data to sink node. Sensors are equipped with one or more sensing components. In our paper, a connected dominating set (CDS) based localized mechanism is used to provide coverage and connectivity.

A Dominating Set based Topology control algo- rithm for Wireless Sensor Networks is designed. Initially, it generates topology for wireless sensor nodes. Backbone node is selected based on node id, node degree and residual energy. To construct the backbone topology, such that a set of active sensors are chosen to work alternatively t serve different types of data, the global connectivity requirements can be achieved.

This algorithm analyzes the performance of nodes and getting better results. Also it provides energy conserved connectivity and coverage, it also maximized the nodes Lifetime.

1. Background

   1. Dominating Set

      Consider G = (V, E) is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge. Domination number (G) is the number of ver- tices in a smallest dominating set for G.

   2. Connected Dominating set

      In a given graph, subset of nodes such that it forms a dominating set in the graph and the sub graph induced is connected. Involves two properties,

      • Any node in D can reach any other node in D by a path that stays entirely within D. That is, D induces a connected sub graph of G.

      • Every vertex in G either belongs to D or is adjacent to a vertex in D. It implies that D is a dominating set of G.

2. Topology Control

The fundament problem in Wireless Sensor Network is Topology control. It is of great importance for prolonged lifetime, increasing the efficiency of routing protocol, ensur- ing the quality of connectivity and coverage and increasing the network services. Also it is used to maintain network connectivity while improving energy efficiency and increas- ing network capacity.

1. Network Coverage

   Coverage is a method for evaluating the QoS of Wire- less Sensor Networks. The most important factor of cover- age is network sensing capability of physical world. Cover- age in wireless sensor networks is defined as a measure of how well and for how long the sensors are able to observe the physical space.

2. Network Connectivity

   Network connectivity is the process of connecting vari- ous parts of a network to one another. WSNs is a large scale network, sensory data need to be sent to sink through hop by hop communication. This requires topology control to prove the connectivity of network.

3. Network Lifetime

An important issue in wireless sensor networks is to prolong networks life time. Sensors are hard to recharge them, since it is battery powered. Network lifetime depends on the objective of an application. The common definition includes the time until the first or last node in the network depletes its energy and the time until the node is discon- nected from the case station.

1. Minimum CDS Backbone Selection

   In the beginning, an initial CDS backbone is selected so that the sensed data can be propagated to the sink along the backbone. These sensors provide coverage and connectivity.

   Each sensor u has associated the following fields: time t (u), a priority p (u), status (u), CDS (u), and role label r (u). The time data structure describes the amount of time that u has to be active. Sensor priority p (u) is defined as a 2-tuple p (u) = (E (u), D (u)), where E (u) is the node u's residual energy and D (u) is the node u's degree. A node with higher residual energy has higher priority. If the residual energy of two nodes is same, then the node degrees are used to deter- mine the priority.

   The status field can either be active or not. The field CDS (u) can be TRUE or FALSE, depending on whether node u is currently in the backbone CDS or not. The field r keeps information about the role of a sensor, whether the node is active for serving the connectivity. Sensors collect h-hop neighborhood information by exchanging Hello mes- sages.

   Sink

   Transmission Range : 100m Sensing Range : 20m

   Bandwidth : 2Mbps Initial Energy Model : Battery Initial Battery Power : 1000Joules

   Communication Model : Bi-Directional TC Protocol : MCDS

   Routing Protocol : Simple Forwarding Sensor & Data Protocol : Simple S&D Protocol Interval : 5.0Seconds

   Number of Nodes : 50,100,150,200,250

   CDS Node Non CDS Node

   Fig. 1 Connected Dominating Set

   Algorithm for Minimum CDS Backbone Selection

   //Initialization

   Each sensor u has following fields:

   Time t (u) =0; //amount of time u is active Node Degree D (u);

   Energy E (u);

   Priority p (u) = (E (u), D (u));

   CDS (u) =FALSE; // sensor u is not in CDS role r (u) =NULL; // sensor u is in CDS or not

   Status (u) =active; // all nodes are initially active

   //Backbone Selection

   for each sensor u do

   Compute energy E (u) and Node Degree D (u) Priority p (u) = (Higher energy, Node Degree); for time interval T on each sensor u do

   1. Exchange Hello message within its range

among its neighbors;

(b)for sensors u and v compute energy do if (u has higher energy) then

Sensor u is in CDS; // sensor u is in active

end if

if (sensors u and v has same energy) and (compare Node Degree of u and v) then Sensor u is in CDS (active); // D (u)>D (v) else

Fig. 2 Network Setup

Fig. 3 descibes the number of active nodes (i.e) number of nodes present in CDS backbone, coverage, and connectivity of the network.

Fig. 3 Network Topology

Fig. 4 represents the variation of active nodes as compared to the total number of nodes. It shows that the topology control algorithm chooses fewer number of active sensors for sensing and data relying tasks. This CDS backbone ensures network coverage and connectivity.

end for end for

Sensor v is in CDS; // u is in sleep state

end if end for

1. PERFORMANCE ANALYSIS

   In this section we evaluate the performance of dominating set based topology control algorithm to maximize the network lifetime. We study the average number of active sensors, energy consumption and delay. Sensors are randomly deployed in an area of 600m × 600m. The network setup is shown in the following Fig.2,

   Fig. 4 Average Number of Active Sensors

   Fig. 5 shows that the dominating set based topology control algorithm consumes less energy for building a topology, since it also has the lowest number of messages sent. It can be observed that the MCDS algorithm is developed to ensure energy consumption. Also less energy is wasted on control messages since most of the sensors do not take part in the data communication and as a result less energy is consumed. The simulation result shows that the algorithm is more energy efficient.

   Fig. 5 Total Energy Consumption

   Fig. 6 shows that the number of packets sent in order to achieve the topology construction. MCDS algorithm transmits packets (2197 packets) for the topology with a total of 250 nodes.

   Fig. 6 Number of Packets sent to achieve topology construction

2. CONCLUSION

Thus, topology control entails changing the node parameter in order to develop a network topology that would ensure the lowest energy consumption and the high- est throughput within the network. A MCDS based localized

mechanism is proposed. The minimum CDS backbone se- lection algorithm constructs topology with reduced size and although the algorithm is designed for optimal energy con- sumption. The coverage and global connectivity requirements are met. MCDS is energy efficient; it provides coverage, connectivity and prolong the network lifetime.

REFERENCES

1. Hakki Bagci, Ibrahim Korpeoglu and Adnan Yazc A Distributed Fault Tolerant Topology Control Algorithm for Heterogeneous Wireless Sensor Networks, IEEE Transac- tions on Parallel and Distributed Systems, Vol.26, No.4, April 2015.

2. Mohamed Younis, Izzet F.Senturk, Kemal Akkaya, Sookyoung Lee, Fatih Senel Topology management tech- niques for tolerating node failures in wireless sensor net- works: A survey, Survey paper vol.58, January 2014.

3. M. Azharuddin, P. Kuila, and P. K. JanaA distributed fault- tolerant clustering algorithm for wireless sensor networks, IEEE (ICACCI),Aug. 2013.

4. Masoumeh Haghpanai, Mehdi Kalantari, Mark Shayman Topology control in large-scale wireless sensor networks: Between information source and sink, Ad Hoc Networks vol.11 Issue.3, May 2012.

5. Kranthi K. Mamidisetty, Michael J. Ferrara, Shivakumar Sastry Systematic selection of cluster heads for data collec- tion, Journal of Network and Computer Applications vol.35, Issue.5, September 2012.

6. Zheng Gengzhong, Liu Qiumei A Survey on Topology Con- trol in Wireless Sensor Networks, IEEE ICSCN, Jan 2010.

7. Mihaela Cardei, Shuhui Yang, and Jie Wu Algorithms for Fault-Tolerant Topology in Heterogeneous Wireless Sensor Networks, IEEE Transactions on Parallel and Distributed Systems Vol.19, Issue.4, April 2008.

8. Ning Li, and Jennifer C. Hou Localized Fault-Tolerant To- pology Control in Wireless Ad Hoc Networks,IEEE Trans- actions on Parallel and Distributed Systems vol.17,Issue.4,April 2006.

9. Ossama Younis, Marwan Krunz, and Srinivasan Ramasubra- manian Node Clustering in Wireless Sensor Networks: Re- cent Developments and Deployment Challenges, IEEE Net- work vol.20 Issue.3, May-June 2006.

10. Weili Wu, Hongwei Du, Xiaohua Jia, Yingshu Li, Scott C.-H. Huang Minimum connected dominating sets and maximal independent sets in unit disk graphs, Theoretical Computer ScienceVol.352, Issue.1-3, March 2006.

11. Ning Li, Jennifer C. Hou, and Lui Sha Design and Analysis of an MST-Based Topology Control Algorithm IEEE Trans- actions on Wireless Communications Vol.4, Issue.3, May 2005.

12. Li (Erran) Li, Joseph Y. Halpern, Paramvir Bahl, Yi-Min Wang, and Roger WattenhoferA Cone-Based Distributed Topology-ControlAlgorithm for Wireless Multi-Hop Net- worksIEEE/ACM Transactions on Networking Vol.13, Is- sue.1, February 2005.

13. Mihaela Cardie, and Jie Wu, "Energy-efficient coverage problems in wireless ad-hoc networks", Computer Comm., Vol.29, pp. 413. February 2006.

14. Mihaela Cardie, My T. Thai, Yingshu Li, and Weili Wu, "Energy-Efficient Target Coverage in Wireless Sensor Networks", Proceedings of IEEE. March 2005.

15. Lu Ruana , Hongwei Du , Xiaohua Jia , Weili Wu , Yingshu Li , Ker-I Ko A greedy approximation for minimum con- nected dominating sets,Theoretical Computer Science Vol:329 Issue:1-3,August2004.

16. Fei Dai, and Jie Wu An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks IEEE Transactions on Parallel and Distributed SystemsVol:15 Issue:10,Oct. 2004.

17. Jamil A. Shaikh, Julio Solano, Ivan Stojmenovic, and Jie Wu, "New Metrics for Dominating Set Based Energy Efficient Ac- tivity Scheduling in Ad Hoc Networks", Proceedings of the 28th Annual IEEE International Conference on Local Com- puter Networks, Article, January 2003.

18. Ivan Stojmenovic, Mahtab Seddigh, and Jovisa Zunic Domi- nating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems Vol.13, Issue.1, June 2002.

19. Khaled M. Alzoubi, Peng-Jun Wan, Ophir Frieder Message- Optimal Connected Dominating Sets in Mobile Ad Hoc Net- works, Journal on Communication Networks, August 2002.

20. Jie Wu, Fei Dai, Ming Gao, and Ivan Stojmenovic, "On Cal- culating Power-Aware Connected Dominating Sets for Ener- gy Efficient Routing in Ad Hoc Wireless Networks", Journal of Networks, Vol. 4, October 2002.