Some operations in multi-channel wireless communications and social network

Usage of Multi-Channel in wireless network brings new challenges to algorithm design for network operations. In this paper we discuss the minimum latency broadcast problem (MLB) in multi-channel multi-hop wireless networks (MLB-MC). This problem is NP-hard since its special version, MLB in single-channel network (MLB-SC) is proved to be NP-hard (57). We design an efficient approximation for MLB-MC, analyze its approximation ratio, and evaluate its performance via numerical experiments. Furthermore, we give a general theorem as an upper bound to compare the performance between approximations for MLB-MC and MLB-SC. We also consider Minimum Interference Connected Dominating Set Problem in multi-radio multi-hop wireless network, in which each node is equipped with multiple interfaces and all nodes cooperate together to fulfill a network task. Routing based on a connected dominating set (CDS) is a frequently used approach, where the searching space for a route is reduced to the nodes in this set. CDS is actually a virtual backbone of multi-hop wireless network. To improve wireless network throughput, in this paper we firstly define the minimum interference connected dominating set problem in a multi-radio multi-hop wireless network, and then propose two different algorithm for which theoretical analysis are given. However, due to the characteristics of the problem it self, it is difficult to compute the approximation ratio for our algorithms. Simulation results compare these two proposed algorithms. Next we study the dominating optimization problem with multiple channels and multiple radios in wireless sensor networks. The objective is to maximize the number of targets covered while selecting at most k nodes and at most ki channels with each selected node vi. Our problem is a general case of the maximum coverage problem. We propose two algorithms. The first one is base on linear programming and PIPAGE rounding and its approximation ratio is 1K1- 1-1mm , where m is the number of the dominating nodes and K = maxi∈I ki. And the second algorithm is based on greedy strategy with low time complexity. The simulation shows that the two algorithms both have good performance. With concern of minimize energy consumption for wireless network in multi-channel environment, we also study the minimum energy broadcast problem (MEB-MB) in multi-channel wireless ad hoc networks that use directional antennas. We propose a constant ratio approximation algorithm named MST-MB for MEB-MC and provide its approximation ratio. Experiment results evaluate the performance of MST-MB. We investigate the positive influence dominating set (PIDS) which has applications in social networks. We prove that PIDS is APX-hard and propose a greedy algorithm with an approximation ratio of H(delta) where H is the harmonic function and delta is the maximum vertex degree of the graph representing a social network. Motivated from application in social networks, a new type of dominating sets has been studied in the literature. In this paper, we present results on its complexity and approximation in general graphs.