A Research On Data Gathering Algorithms In Wireless Sensor Networks

Wireless sensor networks have been the targets of active research in the recent past due to their military and civil applications. One of the most important missions of wireless sensor networks is gathering data sampled by sensor nodes, and then transmitting them to Sink (i.e. base station) be processed by users finally. This dissertation focuses on the challenges of data gathering in wireless sensor networks, aiming at high energy and storage efficiency and low network delay. The main works are as follows:(1) We propose a distributed spatio-temporal wavelet data compression algorithm in the presence of in-networking compression issues. Aiming at the spatial correlations among the sensory data stored in different sensor nodes, a virtual grid based ring topology (VGRT) is designed. Based on VGRT, a distributed spatio-temporal data compression scheme is presented. It is capable of exploring the spatial and temporal correlations among the sensory data simultaneously. Our proposed algorithm can eliminate the redundant information existed in sensory data, balance and reduce energy consumption, decrease delay and thus improve data gathering efficiency.(2) We further propose a distributed data compression algorithm based on optimal wavelet transform, and present a performance evaluation model (AP) for data compression algorithm in wireless sensor networks. By designing hybrid decomposition based distributed wavelet transform, we can utilize the computation resource of sensor nodes to decrease the communication overhead in wavelet coefficients production. Thereafter, an optimal wavelet transform is proposed, which can decide the optimal transforming levels adaptively according to the trade-off point between compression efficiency and the corresponding communication overhead. AP model is an excellent method for evaluating data compression algorithm since it exploits compression quality, energy consumption and network delay synthetically.(3) Aiming at solving the problem of the limited memory in sensor nodes, we propose a VGRT based 2-dimensional spatio-temporal data gathering algorithm (2DDG) and an overlapping clustering topology based 3-dimensional spatio-temporal data gathering algorithm (3DDG). 2DDG and 3DDG cope with the memory-efficient data gathering problem in middle-small and large clusters respectively. The proposed algorithms select data units, which are transmitted progressively, according to the specific wavelet function and the size of sensory data stored in single nodes. Correspondingly, the needed memory of each cluster-head doesn't depend on the size of sensory data, and thus our proposed algorithms are memory-efficient.(4) Considering the multi-level clustering architecture in wireless sensor networks, we further study the memory-efficient data gathering problem among cluster-heads. By designing virtual memory, virtual memory unit and virtual memory block, we first introduce the idea of virtual nodes, which can extend the limited memory of practical nodes virtually. We then propose a progressive data gathering algorithm among cluster-heads (CHDG). CHDG selects data units being transmitted progressively according to the memory of virtual block and the connection among virtual nodes. Hence the needed memory of cluster-heads in every level doesn't depend on the size of sensory data.(5) We introduce the problem of mobile agent based data gathering in wireless sensor networks, and then propose a data-gathering algorithm based on a trajectory-based mobile agent dynamic routes. By designing data packet and data table with specific data structure, we first present the OBIC algorithm. OBIC obtains the basic information of object nodes and the optimal path between object nodes and processing element. We then form an optimization problem of mobile agent static route, and present the MASR algorithm to solve the optimal static route for mobile agent migration. Subsequently, we get the trajectory-based mobile agent dynamic routes algorithm MATDR. Our proposed scheme is able to provide less consumption and network delay compared to other schemes.(6) Based on the above achievements, we implement a data collection prototype-system of temperature and light measurements for a wireless sensor network. On the basis of the LEPS flat protocol along with TinyOS, the prototype-system implements a clustering route protocol and a wavelet data compression algorithm with run length encoding. Our system runs in Micaz and can surveil the place deployed with the wireless sensor network through Internet in real time.