| With the explosive growth of wireless communications, new types of data transmission and data management technologies are required urgently to meet the increasing popularity of mobile and wireless customers. This dissertation contains researches on novel approaches for data transmission, dissemination, and communication problems, to satisfy new requirements from clients, to improve current system performance, and to optimize existing transmission protocols. The whole project can be divided into two parts.In the first part, we mainly discuss data management, data scheduling, indexing technology, and data transmission problems for Wireless Data Broadcast, a new data dissemination method for wireless and mobile users to retrieve database information. We design a novel and automatic system named SAMBox for data broadcast under asynchronous multi-channel wireless communication environment, including index design, data structure construction, and channel scheduling algorithm, with optimized parameter selection. We then propose several exact algorithms to data scheduling problem for a special kind of database management system: multi-media databases. These algorithms are the first approaches for wireless data broadcast under the fourth generation network with MIMO technology. Next, we give a novel data dissemination algorithm, which saves around 50% energy comparing with current system. This part also includes three approximations for query dissemination in a special type of wireless network, wireless sensor network.In the second part, we focus on the theoretical analysis for data transmission problem over "backbone" network, which is usually represented as connected dominating set (CDS) in a communication network model. The routing protocols rely on such infrastructure can simplify the routing process and improve system performance. Thus it is desirable to choose a minimum CDS for efficiency. We are aiming at constructing a "good" backbone effectively by optimizing the selection strategies innovatively and analyzing the approximation ratio carefully. We provide a constant-factor (10+epsilon) approximation algorithm for weighted connected dominating set problem, which is much smaller than the existing literature. We prove a better theoretical bound to approximate dominating set using Euler formula. And finally, we give the first polynomial time approximation scheme (PTAS) for d-hop connected dominating set problem. |
