Browsing by Author "Wang, Feng"

Now showing 1 - 6 of 6
  • Thumbnail Image
    Item
    Connected Dominating Sets in Wireless Networks with Different Transmission Ranges
    (2005-11-21) Thai, My T.; Wang, Feng; Liu, Dan; Zhu, Shiwei; Du, Ding-Zhu
    Since there is no fixed infrastructure or centralized management in wireless ad hoc networks, a Connected Dominating Set (CDS) has been proposed as the virtual backbone. The CDS of a graph representing a network has a significant impact on an efficient design of routing protocols in wireless networks. This problem has been studied extensively in Unit Disk Graphs (UDG), in which each node has the same transmission range. However, in practice, the transmission ranges of all nodes are not necessary equal. In this paper, we model a network as a disk graph and introduce the CDS problem in disk graphs. We present three constant approximation algorithms to obtain a minimum CDS of a given network. These algorithms can be implemented as distributed algorithms. Furthermore, we show the size relationship between a maximal independent set and a CDS as well as the bound of the maximum number of independent neighbors of a node in disk graphs. The theoretical analysis and simulation results are also presented to verify our approaches.
  • 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
    Hydrostatic Transmission for Wind Power Generation
    (2011-11) Stelson, Kim; Kildegaard, Arne; Brad Bohlmann, Brad; Wang, Feng; Thul, Brenen; Dutta, Rahul
    The University of Minnesota is performing research on the application of continuously variable hydrostatic transmissions for wind turbines. By replacing the gearbox of traditional wind turbines with a continuously variable hydrostatic transmission (HST) more efficient turbine operation could be achieved without the use of unreliable gearbox and power electronics.
  • 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 2-Connected Virtual Backbones in Wireless Networks
    (2005-11-29) Wang, Feng; Thai, My T.; Du, Ding-Zhu
    Virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem in ad hoc networks. Since the nodes in the virtual backbone need to carry other node's traffic, and node and link failure are inherent in wireless networks, it is desirable that the virtual backbone is fault tolerant. In this paper, we propose a new algorithm called Connecting Dominating Set Augmentation (CDSA) to construct a 2-connected virtual backbone which can resist the failure of one wireless node. We prove that CDSA has guaranteed quality, because the size of the CDSA constructed 2-connected backbone is within a constant factor of the optimal 2-connected virtual backbone size. Through extensive simulations, we demonstrate that CDSA can improve the fault tolerance of virtual backbone with marginal overhead.
  • 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.