Algorithm optimization in wireless sensor networks and data center networks

Abstract

Different types of networks have different features and usages. In this thesis, we consider Wireless Sensor Networks (WSN) and Data Center Networks (DCN). The WSN features the sensor nodes with limited power. It is mainly used to collect data from fields. The DCN features the virtualization technology, in which physical resources (i.e., computing, storage, networking) are partitioned and multiplexed into Virtual Machines (VM). It is used to host various applications on VMs and provide flexible resource managements. Various problems arise in these networks due to different requirements: in the WSN, transmission-efficient data collection methods are required to reduce the energy consumption in data transmissions; in the DCN, seamless virtual machine migration methods are required so that VMs can be migrated and consolidated for the purposes such as load balancing, performance optimization and interruption-free system maintenance; also in the DCN, it is required to improve the data retrieval performance for the High-Performance Computing (HPC) applications hosted. In this thesis, we will investigate these problems and propose efficient algorithms to solve them. First in the WSN, compressive sensing (CS) can reduce the number of data transmissions. However, the total number of transmissions for the data collections by using pure CS is still large. In this thesis, we propose a clustering method that uses hybrid CS for sensor networks. The sensor nodes are organized into clusters. Within a cluster, the nodes transmit data to a cluster head (CH) without using CS. The CHs use CS to transmit data to the sink. We first propose an analytical model to determine the optimal size of clusters that can lead to the minimum number of transmissions. Then we propose a centralized clustering algorithm and a distributed implementation based on the results obtained from the analytical model. Second, we still aim to reduce the number of data transmissions in the WSN. It is observed that there are many zero elements in the sparse measurement matrix of the CS method. In each round of data transmission in the CS method, the sensor nodes corresponding to the zero elements in the measurement matrix do not have their own data to transmit. Thus we compute a data gathering tree by taking advantages of these zero elements in the measurement matrix, such that the total number of data transmissions is minimized. We propose a heuristic algorithm to compute a minimum transmission tree in this regard. Third in the DCN, the traditional methods for virtual machine migrations (VMM) could not avoid the service interruption completely. Moreover, they often result in longer delay and proneness to failures. In this thesis, we leverage the emerging named data networking to design an efficient and robust service protocol to support seamless VMM in cloud data center. Specifically, virtual machines (VMs) are named with the services they provide. The request routing is based on the service names instead of the IP addresses that are normally bounded with physical machines. As such, the services would not be interrupted when migrating the supported VMs to different physical machines. Fourth in the DCN, a variety of High-Performance Computing (HPC) applications have been deployed in the cloud platforms. A huge volume of data for the HPC applications need to be transmitted from a remote data repository to the computing nodes in parallel before processing. However, the low throughput and the bandwidth sharing in the cloud platforms degrade the data retrieval efficiency, and negatively impact the computing performance of the HPC applications. In this thesis, we propose a bandwidthaware cooperative caching scheme to minimize the data retrieval time. We propose an optimization algorithm based on the technique of branch-and-cut to solve it.

Date of Award	3 Oct 2014
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Xiaohua JIA (Supervisor)