Power-efficient topology control for static wireless networks with switched beam directional antennas

Topology control problems are associated with assignment of power levels to nodes of a wireless network so that the resulting graph topology satisfies certain properties. In this paper we consider the problem of power-efficient topology control with switched beam directional antennas taking into account their non-uniform radiation pattern within the beamwidth. Previous work in the area have all assumed a uniform gain model with these antennas which renders antenna orientation insignificant as a parameter in topology control algorithms. We present algorithms that take into account a model of non-uniform gain with the objectives of minimizing the total power and maximum power to keep the network connected. We consider two cases: one where the antenna orientation is assumed given and another where the antenna orientation needs to be derived as well. For the first case, we present optimal and approximation algorithms for constructing power-efficient topologies. For the second case, we prove the problem to be NP-complete and present heuristic solutions along with approximation bounds. Through comparison of the two cases by simulation, significant reductions are shown in the maximum as well as total power required to keep the network connected for the second case, thus demonstrating the benefits of using antenna orientation as parameter in topology construction.     

Topology control in constant rate mobile ad hoc networks

Topology control is the problem of assigning power levels to the nodes of an ad hoc network so as to create a specified network topology while minimizing the energy consumed by the network nodes. While considerable theoretical attention has been given to the issue of topology control in wireless ad hoc networks, all of that prior work has concerned stationary networks. When the nodes are mobile, there is no algorithm that can guarantee a graph property (such as network connectivity) throughout the node movement. In this paper we study topology control in mobile wireless ad hoc networks (MANETs). We define a mobility model, namely the constant rate mobile network (CRMN) model, in which we assume that the speed and direction of each moving node are known. The goal of topology control under this model is to minimize the maximum power used by any network node in maintaining a specified monotone graph property. Network connectivity is one of the most fundamental monotone properties. Under the CRMN model, we develop general frameworks for solving both the decision version (i.e. for a given value p > 0, will a specified monotone property hold for the network induced by assigning the power value p to every node?) and the optimization version (i.e. find the minimum value p such that the specified monotone property holds for the network induced by assigning the power value p to every node) of the topology control problems. Efficient algorithms for specific monotone properties can be derived from these frameworks. For example, when the monotone property is network connectivity, our algorithms for the decision and optimization versions have running times of O(n ² log² n) and O(n ⁴ log² n), respectively. Our results represent a step towards the development of efficient and provably good distributed algorithms for topology control problems for MANETs.     

Approximating the Minimum Number of Maximum Power Users in Ad hoc Networks

Topology control is the problem of assigning transmission power values to the nodes of an ad hoc network so that the induced graph satisfies some specified property. The most fundamental such property is that the network/graph be connected. For connectivity, prior work on topology control gave a polynomial time algorithm for minimizing the maximum power assigned to any node (such that the induced graph is connected). In this paper we study the problem of minimizing the number of maximum power nodes. After establishing that this minimization problem is NP-complete, we focus on approximation algorithms for graphs with symmetric power thresholds. We first show that the problem is reducible in an approximation preserving manner to the problem of assigning power values so that the sum of the powers is minimized. Using known results for that problem, this provides a family of approximation algorithms for the problem of minimizing the number of maximum power nodes with approximation ratios of 5/3 + ε for every ε > 0. Unfortunately, these algorithms, based on solving large linear programming problems, are not practical. The main results of this paper are practical algorithms with approximation ratios of 7/4 and 5/3 (exactly). In addition, we present experimental results, both on randomly generated networks, and on two networks derived from proximity data associated with the TRANSIMS project of Los Alamos National Labs. Finally, based on the reduction to the problem of minimizing the total power, we describe some additional results for minimizing the number of maximum power users, both for graph properties other than connectivity and for graphs with asymmetric power thresholds. A preliminary version of this paper was presented at the ADHOC-NOW’04 conference in Vancouver, Canada, July 2004. Prepared through collaborative participation in the Communications and Networks Consortium sponsored by the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes not withstanding any copyright notation thereon. Errol L. Lloyd is a Professor of Computer and Information Sciences at the University of Delaware. Previously he served as a faculty member at the University of Pittsburgh and as Program Director for Computer and Computation Theory at the National Science Foundation. From 1994 to 1999 he was Chair of the Department of Computer and Information Sciences at the University of Delaware. Concurrently, from 1997 to 1999 he was Interim Director of the University of Delaware Center for Applied Science and Engineering in Rehabilitation. Professor Lloyd received undergraduate degrees in both Computer Science and Mathematics from Penn State University, and a Ph.D. in Computer Science from the Massachusetts Institute of Technology. His research expertise is in the design and analysis of algorithms, with a particular concentration on approximation algorithms. In 1989 Professor Lloyd received an NSF Outstanding Performance Award, and in 1994 he received the University of Delaware Faculty Excellence in Teaching Award. Rui Liu received the B.S. degree in mathematics from Peking University, Beijing, China, in 1998, and the Ph.D. degree in Computer and Information Sciences from the University of Delaware in 2004. Since that time, he has been a Senior Associate Staff Scientist with Oracle|Retek. His research interests include design and analysis of algorithms for combinatorial optimization problems, and mobile computing. S.S. Ravi received his Ph.D. in Computer Science from the University of Pittsburgh in 1984. Since that time, he has been on the computer science faculty at the University at Albany – State University of New York, where he is currently a Professor. His areas of interest include design and analysis of algorithms, mobile computing, data mining and fault-tolerant computing.     

基于图论的无线传感器网络并行禁忌搜索信道分配方法

Wireless sensor networks are suffering from serious frequency interference. In this paper, we propose a channel assignment algorithm based on graph theory in wireless sensor networks. We first model the conflict infection graph for channel assignment with the goal of global optimization minimizing the total interferences in wireless sensor networks. The channel assignment problem is equivalent to the generalized graph coloring problem which is a NP complete problem. We further present a meta heuristic Wireless Sensor Network Parallel Tabu Search (WSN PTS) algorithm, which can optimize global networks with small numbers of iterations. The results from a simulation experiment reveal that the novel algorithm can effectively solve the channel assignment problem.     

New algorithms for multicast routing and wavelength assignment in multi-hop optical WDM networks

We study the problem of multicast routing and wavelength assignment (MC-RWA) in multi-hop optical WDM networks with respect to several target functions. Specially, we first study the MC-RWA problem under the target of minimize maximum hops, an efficient MC-RWA algorithm was proposed for that case. But for the objective of minimizing the total number of wavelength conversions, problem turns out to be NP-hard, we proposed a new approximation MC-RWA algorithm based on group Steiner tree. At last, combining the two objectives, a bi-factor approximation algorithm was introduced to minimize the both targets in the system simultaneously.     

Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while maintaining k-fault tolerance. Specifically, we require all links established by this power setting be symmetric and form a k-vertex connected subgraph of the network graph. This problem is known to be NP-hard. We show current heuristic approaches can use arbitrarily more power than the optimal solution. Hence, we seek approximation algorithms for this problem. We present three approximation algorithms. The first algorithm gives an O(kalpha)-approximation where is the best approximation factor for the related problem in wired networks (the best alpha so far is O(log k)). With a more careful analysis, we show our second (slightly more complicated) algorithm is an O(k)-approximation. Our third algorithm assumes that the edge lengths of the network graph form a metric. In this case, we present simple and practical distributed algorithms for the cases of 2- and 3-connectivity with constant approximation factors. We generalize this algorithm to obtain an O(k^2c+2)-approximation for general k-connectivity (2 les c les 4 is the power attenuation exponent). Finally, we show that these approximation algorithms compare favorably with existing heuristics. We note that all algorithms presented in this paper can be used to minimize power while maintaining -edge connectivity with guaranteed approximation factors. Recently, different set of authors used the notion of k-connectivity and the results of this paper to deal with the fault-tolerance issues for static wireless network settings.     

广义AND/OR图的自底向上的启发式搜索算法BFA0

本文首先根据三角模及其扩张运算概念,定义了一类新的更具普遍意义的模糊广义AND/OR图。根据新定义的启发式函数h(n,x)以及模糊广义AND/OR图的最佳解树之所有子树亦是最佳子解树的原理,提出了自底向上的启发式搜索算法BFAO·。文中证明了算法BFAO·的可采纳性。本文还提出了两类新的启发式函数的单调限制概念,并据此研究了算法BFAO·的单调限制性质,研究了两个BFAO·算法间的比较性质。     

FrogSim: distributed graph coloring in wireless ad hoc networks

Graph coloring, which is at the heart of several problems arising in wireless ad hoc networks, concerns the problem of assigning colors to the nodes of a graph such that adjacent nodes do not share the same color. This paper deals with the problem of generating valid colorings in a distributed way, while minimizing the number of colors used. Examples of related problems in wireless ad hoc networks are TDMA slot assignment, wakeup scheduling, and data collection. The presented algorithm is inspired by the desynchronization observed in the context of the calling behaviour of male Japanese tree frogs. Experimental results indicate that the proposed algorithm is very competitive with current state-of-the-art approaches.     

Efficient Minimization Method for a Generalized Total Variation Functional

Replacing the lscr² data fidelity term of the standard total variation (TV) functional with an lscr¹ data fidelity term has been found to offer a number of theoretical and practical benefits. Efficient algorithms for minimizing this lscr¹-TV functional have only recently begun to be developed, the fastest of which exploit graph representations, and are restricted to the denoising problem. We describe an alternative approach that minimizes a generalized TV functional, including both lscr²-TV and lscr¹-TV as special cases, and is capable of solving more general inverse problems than denoising (e.g., deconvolution). This algorithm is competitive with the graph-based methods in the denoising case, and is the fastest algorithm of which we are aware for general inverse problems involving a nontrivial forward linear operator.     

Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks

In this paper we study the problem of assigning transmission ranges to the nodes of a static ad hoc wireless network so as to minimize the total power consumed under the constraint that enough power is provided to the nodes to ensure that the network is connected. We focus on the Min-Power Symmetric Connectivity problem, in which the bidirectional links established by the transmission ranges are required to form a connected graph. Implicit in previous work on transmission range assignment under asymmetric connectivity requirements is the proof that Min-Power Symmetric Connectivity is NP-hard and that the MST algorithm has a performance ratio of 2. In this paper we make the following contributions: (1) we show that the related Min-Power Symmetric Unicast problem can be solved efficiently by a shortest-path computation in an appropriately constructed auxiliary graph; (2) we give an exact branch and cut algorithm based on a new integer linear program formulation solving instances with up to 35–40 nodes in 1 hour; (3) we establish the similarity between Min-Power Symmetric Connectivity and the classic Steiner Tree problem in graphs, and use this similarity to give a polynomial-time approximation scheme with performance ratio approaching 5/3 as well as a more practical approximation algorithm with approximation factor 11/6; and (4) we give the results of a comprehensive experimental study comparing new and previously proposed heuristics with the above exact and approximation algorithms.     

Feasibility of optimally assigning channels by exhaustive search in commercial multi-radio wireless mesh networks

Channel assignment problems in multi-radio wireless mesh networks (WMNs) have been shown to be NP-hard in various scenarios in the literature. By far, most of research efforts have focused on developing efficient approximation algorithms that run reasonably fast and provide good quality channel assignment rather than the optimal one. However, from the practical network design and deployment standpoint, engineers care more about whether it is feasible to optimally assign channels in the simplest way (i.e., exhaustive search), as most of existing commercial WMNs are of small/medium scale. In this paper, we attempt to answer this practical question. We study the complexity of general channel assignment problems with certain basic and common properties. The results show that the complexity in terms of the number of different possible assignments is exponential in the number of wireless links. Furthermore, we estimate the theoretical runtime of determining the optimal channel assignment by exhaustive search and validate it through experiments. We show that, given certain computing power (e.g., an off-the-shelf notebook PC), it is feasible to optimally solve channel assignment problems in small-scale and medium-scale commercial multi-radio WMNs. In other words, approximation algorithms are not needed for most of current commercial WMNs.     

Optimum Integrated Link Scheduling and Power Control for Multihop Wireless Networks

In this paper, a new mathematical programming formulation is developed for minimizing the schedule length in multihop wireless networks based on the optimal joint scheduling of transmissions across multi-access communication links and the allocation of transmit power levels while meeting the requirements on the signal-to-interference-plus-noise ratio at intended receivers. The authors prove that the problem can be represented as a mixed-integer linear programming (MILP) and show that the latter yields a solution that consists of transmit power levels that are "strongly Pareto optimal". It was demonstrated that the MILP formulation can be used effectively to derive optimal scheduling and power levels for networks with as many as 30 designated communication links. The authors show that the MILP formulation can also be effectively solved to provide upper and lower bounds (corresponding to an approximation factor Delta) for the optimum schedule length of networks with as many as 100 designated links. It is proved that the integrated link scheduling and power control problem (ILSP) is NP-complete. Consequently, a heuristic algorithm of polynomial complexity is developed and investigated for solving the problem in a timely and practical manner. The algorithm is based on the properties of a novel interference graph, i.e., the "generalized power-based interference graph", whose "chromatic" and "independence numbers" provide fundamental bounds for the ILSP. It is demonstrated that the frame length of schedules realized by the heuristic scheme resides in the 25th percentile of those attained by the optimal mechanism for randomly generated topologies with as many as 30 designated communication links. Furthermore, it is shown that the algorithm significantly outperforms a corresponding algorithm presented in the literature     

The geometry of weighted low-rank approximations

The low-rank approximation problem is to approximate optimally, with respect to some norm, a matrix by one of the same dimension but smaller rank. It is known that under the Frobenius norm, the best low-rank approximation can be found by using the singular value decomposition (SVD). Although this is no longer true under weighted norms in general, it is demonstrated here that the weighted low-rank approximation problem can be solved by finding the subspace that minimizes a particular cost function. A number of advantages of this parameterization over the traditional parameterization are elucidated. Finding the minimizing subspace is equivalent to minimizing a cost function on the Grassmann manifold. A general framework for constructing optimization algorithms on manifolds is presented and it is shown that existing algorithms in the literature are special cases of this framework. Within this framework, two novel algorithms (a steepest descent algorithm and a Newton-like algorithm) are derived for solving the weighted low-rank approximation problem. They are compared with other algorithms for low-rank approximation as well as with other algorithms for minimizing a cost function on a Grassmann manifold.     

Joint transmit beamforming and power control in multi-user MIMO downlink using a game theoretic approach

This study addresses the problem of jointly optimizing the transmit beamformers and power control in multi-user multiple-input multiple-output (MIMO) downlink. The objective is minimizing the total transmission power while satisfying the signal-to-noise plus interference ratio (SINR) requirement of each user. Before power control, it uses the maximum ratio transmission (MRT) scheme to determine the beamformers due to its attractive properties and the simplicity of handling. For power control it introduces a supermodular game approach and proposes an iterated strict dominance elimination algorithm. The algorithm is proved to converge to the Nash equilibrium. Simulation results indicate that this joint optimization method assures the improvement of performance.     

Routing and wavelength assignment of scheduled lightpath demands

We present algorithms that compute the routing and wavelength assignment (RWA) for scheduled lightpath demands in a wavelength-switching mesh network without wavelength conversion functionality. Scheduled lightpath demands are connection demands for which the setup and teardown times are known in advance. We formulate separately the routing problem and the wavelength assignment problem as spatio-temporal combinatorial optimization problems. For the former, we propose a branch and bound algorithm for exact resolution and an alternative tabu search algorithm for approximate resolution. A generalized graph coloring approach is used to solve the wavelength assignment problem. We compared the proposed algorithms to an RWA algorithm that sequentially computes the route and wavelength assignment for the scheduled lightpath demands.     

Computationally efficient bandwidth allocation and power control for OFDMA

The paper studies the problem of finding an optimal subcarrier and power allocation strategy for downlink communication to multiple users in an orthogonal-frequency-division multiplexing-based wireless system. The problem of minimizing total power consumption with constraints on bit-error rate and transmission rate for users requiring different classes of service is formulated and simple algorithms with good performance are derived. The problem of joint allocation is divided into two steps. In the first step, the number of subcarriers that each user gets is determined based on the users' average signal-to-noise ratio. The algorithm is shown to find the distribution of subcarriers that minimizes the total power required when every user experiences a flat-fading channel. In the second stage of the algorithm, it finds the best assignment of subcarriers to users. Two different approaches are presented, the rate-craving greedy algorithm and the amplitude-craving greedy algorithm. A single cell with one base station and many mobile stations is considered. Numerical results demonstrate that the proposed low complexity algorithms offer comparable performance with an existing iterative algorithm.     

The first constant factor approximation for minimum partial connected dominating set problem in growth-bounded graphs

The idea of virtual backbone has emerged to improve the efficiency of flooding based routing algorithms for wireless networks. The effectiveness of virtual backbone can be improved as its size decreases. The minimum connected dominating set (CDS) problem was used to compute minimum size virtual backbone. However, as this formulation requires the virtual backbone nodes to connect all other nodes, even the size of minimum virtual backbone can be large. This observation leads to consider the minimum partial CDS problem, whose goal is to compute a CDS serving only more than a certain portion of the nodes in a given network. So far, the performance ratio of the best approximation algorithm for the problem is \(O(\ln \varDelta ),\) where \(\varDelta\) is the maximum degree of the input general graph. In this paper, we first assume the input graph is a growth-bounded graph and introduce the first constant factor approximation for the problem. Later, we show that our algorithm is an approximation for the problem in unit disk graph with a much smaller performance ratio, which is of practical interest since unit disk graph is popular to abstract homogeneous wireless networks. Finally, we conduct simulations to evaluate the average performance of our algorithm.     

Joint optimal channel base station and power assignment forwireless access

The provision of personal communication services is the goal of the evolution of integrated communication systems. The fundamental problem underlying any phase (hand-off, new connection, etc.) of a dynamic resource allocation algorithm in a wireless network is to assign transmission powers, forward (downstream) and reverse (upstream) channels, and base stations such that every mobile of the system can establish a connection. Each one of these problems separately has been studied extensively. We consider the joint problem in a system with two base stations. An algorithm that achieves the optimal assignment is provided. It involves the computation of a maximum matching in a graph that captures the topological characteristics of the mobile locations. The traffic capacities, in terms of expected number of connections per channel, of the forward and reverse channel are obtained and compared, for both cases of power control and nonpower control. It turns out that when the transmission power is fixed, the capacities of the forward and reverse channel are different, while when power control is allowed they are the same. For systems with two mobiles the capacities of the forward and reverse channels are studied analytically. Finally, several versions of the two-way channel assignment problem are studied