Chinese Journal of Computers   Full Text
Title	Correlation Dominating Set Construction Based upon Entropy Evaluation in Wireless Sensor Networks
Authors	YU Rui-Yun1) WANG Xing-Wei2) LIU Yong-He3)
Address	1)(Software College, Northeastern University, Shenyang 110819) 2)(College of Information Science and Engineering, Northeastern University, Shenyang 110819) 3)(Computer Science and Engineering Department, the University of Texas at Arlington, TX 76019, USA)
Year	2011
Issue	No.1(87—95)
Abstract &   Background	Abstract Wireless sensor networks are usually densely deployed, so the data sensed from neighboring sensor nodes is highly correlated. For redundancy removal in wireless sensor networks, this paper presents an algorithm named entropy evaluation for correlation dominating set construction (EECDS). The algorithm first determines the correlation degree between sensor nodes by evaluating the entropy of Gaussian random variables, and then distributively generates a correlation graph. Based on the correlation graph, the EECDS algorithm finally constructs a connected correlation dominating set by removing redundant sensor nodes. Data gathering policies with the help of connected correlation dominating sets will greatly reduce data redundancy of dense sensor networks, and therefore result in decrease of energy consumption and prolong lifetime of wireless sensor networks. Keywords wireless sensor networks; information entropy; differential entropy; correlation graph; correlation dominating set; redundancy removal Background Wireless sensor networks are data-oriented, whose main task is data processing, including sensing, data gathering, transmission, compress, aggregation, and so on. Wireless sensor networks are usually densely deployed in a network area, and generate a great deal of data. Moreover, the data sensed by neighboring nodes is highly correlated. These all impose great challenges on the design of data gathering algorithms. Since the sensor nodes are power-constrained, transferring large amounts of data definitely will shorten the lifetime of sensor networks. Therefore, the network performance on energy consumption and stability could be improved through data redundancy removal. In this paper, an algorithm named the entropy evaluation for correlation dominating set construction (EECDS) is presented. The EECDS algorithm exploits the concept of the correlation dominating set. It first determines the correlation between sensor nodes by evaluating the entropy of random variables, and then distributively generates a correlation graph. At last, the algorithm constructs a correlation dominating set using the information of the correlation graph. The EECDS algorithm is very efficient on reducing data redundancy in wireless sensor networks, and performs well on energy balance and scalability. This work is supported by the National Natural Science Foundation of China under grant Nos.61070162, 71071028, 60802023 and 70931001; the Specialized Research Fund for the Doctoral Program of Higher Education under grant Nos.20100042110025 and 20070145017; the Fundamental Research Funds for the Central Universities under grant Nos.N090504003, N090504006 and N100417001; the Doctoral Scientific Research Fund of Liaoning Province under grant No.20101040. One of main tasks of the above mentioned projects is virtual backbone construction in wireless networks. Some published papers were focusing on connected dominating set construction, and generating connected dominating sets as backbones for routing, data collection, etc. This paper highly addresses the correlation fact of wireless sensor networks, and proposes a connected correlation dominating set construction algorithm. The correlation dominating set is used for data redundancy removal, and data gathered from the set could recover the network data within a predefined error bound. The entropy evaluation method exploited in the algorithm can leverage data correlation well, and hence guarantee the efficiency of data redundancy removal in wireless sensor networks.