Browsing by Author "Li, Yingshu"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Fault Tolerant Topology Control for All-to-One and One-to-All Communication in Wireless Networks
    (2005-11-29) Wang, Feng; Thai, My T.; Li, Yingshu; Du, Ding-Zhu
    This paper introduces the problem of fault tolerant topology control for all-to-one and one-to-all communication in static wireless networks with asymmetric wireless links. This problem is important in both theoretical and practical aspects. We investigate two approaches, namely minimum weight based approach and nearest neighbor augmentation approach,to address this problem. Specifically, for each approach, we propose three algorithms for three interpretations of the problem: 1) construct k-node disjoint paths from every node to a specific root node, 2) construct k-node disjoint paths from the root node to every other node, 3) construct k-node disjoint paths from the root node to every other node and also from every node to the root node. Furthermore, we give theoretical analysis for all six algorithms. Among other results, we show that the minimum weight based approach has a k-approximation algorithm for all-to-one fault tolerant topology control where k is the number of disjoint paths. When k=1, this approach solves the minimum power all-to-one 1-connected topology control problem. Through extensive simulations, we demonstrate that minimum weight based approach performs better for the first two interpretations and the augmentation based approach performs better for the third interpretation. To the best of our knowledge, this paper is the first to study the fault tolerant topology control for all-to-one and one-to-all communication in asymmetric static wireless networks, and also is the first to demonstrate that the minimum power all-to-one 1-connected topology control problem has an optimal solution.
  • Thumbnail Image
    Item
    Maximal Independent Set and Minimum Connected Dominating Set in Unit Disk Graphs
    (2004-12-13) WuLi, Wei; Du, Hongwei; Jia, Xiaohua; Li, Yingshu; Huang, Scott C.-H.; Du, Ding-Zhu
    In ad hoc wireless networks, the connected dominating set can be used as a virtual backbone to improve the performance. Many constructions for approximating the minimum connected dominating set are based on construction of maximal independent set. The relation between the size mis(G) of a maximum independent set and the size cds(G) of minimum connected dominating set in the same graph G plays an important role in establishing the performance ratio of those approximation algorithms. Previously, it is known that mis(G)<=4*cds(G)+1 for all unit disk graph G. In this paper, we improve it by showing mis(G)<=3.8*cds(G)+1.2.
  • Thumbnail Image
    Item
    On Greedy Construction of Connected Dominating Sets in Wireless Networks
    (2004-12-16) Li, Yingshu; Thai, My T.; Wang, Feng; Yi, Chih-Wei; Wan, Pengjun; Du, Ding-Zhu
    Since no fixed infrastructure and no centralized management present in wireless networks, a Connected Dominating Set (CDS) of the graph representing the network is widely used as the virtual backbone and plays an important role in the network. Constructing a minimum CDS is NP-hard. Many CDS construction algorithms have been designed. In this paper, we propose a new greedy algorithm, called S-MIS, with the help of Steiner tree that can construct a CDS within a factor of 4.8+ln5 from the optimal solution. We also introduce the distributed version of this algorithm. The theoretical proof shows that our algorithm is better than the current best performance ratio which is 6.8. A simulation is conducted to compare S-MIS with its variation which is rS-MIS. The simulation shows that the sizes of the CDSs generated by S-MIS and rS-MIS are almost the same.
  • Thumbnail Image
    Item
    On the Construction of a Strongly Connected Broadcast Arborescence with Bounded Transmission Delay
    (2004-12-13) Li, Yingshu; Thai, My T.; Wang, Feng; Du, Ding-Zhu
    Energy conservation is an important concern in wireless networks. Many scenarios for constructing a broadcast tree with minimum energy consumption and other goals have been developed. However, no previous research work considers the total energy consumption and transmission delays of the broadcast tree simultaneously. In this paper, based on (alpha, beta)-tree, a novel concept to wireless networks, we define a new Strongly Connected Broadcast Arborescence with Bounded Transmission Delay (SBAT) Problem and design the strongly connected broadcast arborescence (SBA) construction algorithm with linear running time to construct a strongly connected broadcast tree with bounded cost, i.e., total energy, while satisfying the constraint that the transmission delay between the source and other hosts are also bounded. We also propose the distributed version of the SBA algorithm. The theoretical analysis and simulation results show that the SBA algorithm gives a proper solution to the SBAT problem.