Network longevity and connectivity are key design goals in any wireless sensor network deployment. In this context, we consider the placement of relay nodes and individual transmission power assignments. Specifically, given a planar deployment of sensors and a base station, we seek the placement of a limited number of relays and optimal sensor power assignments such that the network is connected. We present a polynomial-time bicriteria approximation algorithm for this problem. We also provide an optimal O(n2log n)-time algorithm for a restricted version where nodes lie on a simplified urban grid (that we call a comb-grid). We also study a related variant that assumes fixed transmission power values, with the goal of minimizing the number of relays. We provide extensive simulation results for the comb-grid case.

Developing and maintaining reliable object-oriented software requires a precise understanding of how individual classes must be used. Unfortunately, for many systems, especially those that are large, the available documentation is inadequate. Developers are left with incomplete information concerning the allowable set of call sequences that each class can accommodate. Techniques for reverse engineering this information and presenting it to developers in an intellectually scalable manner are critical. In this paper, we present four contributions to address this challenge. First, we describe a runtime trace collection system for large C++ applications. Second, we present a methodology for reverse engineering interface protocols from collected trace data. Third, we present a scalable, tunable algorithm for generating compact specifications of these protocols. Finally, we present a detailed case study involving the Mozilla Necko library. We consider popular applications in common use constructed using this library. The results are promising both in terms of the performance of the approach and the utility of the identified protocols.

Existing work on placing additional relay nodes in wireless sensor networks to improve network connectivity typically assumes homogeneous wireless sensor nodes with an identical transmission radius. In contrast, this paper addresses the problem of deploying relay nodes to provide fault tolerance with higher network connectivity in heterogeneous wireless sensor networks, where sensor nodes possess different transmission radii. Depending on the level of desired fault tolerance, such problems can be categorized as: 1) full fault-tolerant relay node placement, which aims to deploy a minimum number of relay nodes to establish k(k ? 1) vertexdisjoint paths between every pair of sensor and/or relay nodes and 2) partial fault-tolerant relay node placement, which aims to deploy a minimum number of relay nodes to establish k(k ? 1) vertex-disjoint paths only between every pair of sensor nodes. Due to the different transmission radii of sensor nodes, these problems are further complicated by the existence of two different kinds of communication paths in heterogeneous wireless sensor networks, namely, two-way paths, along which wireless communications exist in both directions; and one-way paths, along which wireless communications exist in only one direction. Assuming that sensor nodes have different transmission radii, while relay nodes use the same transmission radius, this paper comprehensively analyzes the range of problems introduced by the different levels of fault tolerance (full or partial) coupled with the different types of path (one-way or two-way). Since each of these problems is NP-hard, we develop O(?k2)-approximation algorithms for both one-way and two-way partial fault-tolerant relay node placement, as well as O(?k3)-approximation algorithms for both one-way and two-way full fault-tolerant relay node placement (? is the best performance ratio of existing approximation algorithms for finding a minimum k-vertex connected spanning graph). To facilitate the applications in higher dimensions, we also extend these algorithms and derive their performance ratios in d-dimensional heterogeneous wireless sensor networks (d ? 3). Finally, heuristic implementations of these algorithms are evaluated via QualNet simulations.

In contrast to existing work on the connected coverage problem in wireless sensor networks which assumes omnidirectional sensors with disk-like sensing range, this paper investigates a suite of novel problems related to connected coverage in directional sensor networks where sensors only sense directionally and have a sector-like sensing range. We first consider the problems of deploying a minimum number of directional sensors to form a connected network to cover either a set of point- locations (connected point-coverage deployment (CPD)) or the entire target sensing area (connected region-coverage deployment (CRD)). CPD is NP-hard as its subproblem of geometric sector cover (GSC) is NP-hard. We present two approximation algorithms for GSC as subroutines, and develop a general solution framework for CPD with approximation ratio sigma + O(1), where sigma is the approximation ratio of the selected GSC subroutine. We also describe two efficient deployment patterns with guaranteed covering density for CRD, and analyze their performance bounds with respect to arbitrary non-crossing deployment patterns. Extensive simulation results validate the correctness and merits of the presented algorithms and analysis.

Existing work on placing additional relay nodes in wireless sensor networks to improve network connectivity typically assumes homogeneous wireless sensor nodes with an identical transmission radius. In contrast, this paper addresses the problem of deploying relay nodes to provide fault-tolerance with higher network connectivity in heterogeneous wireless sensor networks, where sensor nodes possess different transmission radii. Depending on the level of desired fault-tolerance, such problems can be categorized as: (1) full fault-tolerance relay node placement, which aims to deploy a minimum number of relay nodes to establish k (k ges 1) vertex-disjoint paths between every pair of sensor and/or relay nodes; (2) partial fault-tolerance relay node placement, which aims to deploy a minimum number of relay nodes to establish k (k ges 1) vertex-disjoint paths only between every pair of sensor nodes. Due to the different transmission radii of sensor nodes, these problems are further complicated by the existence of two different kinds of communication paths in heterogeneous wireless sensor networks, namely two-way paths, along which wireless communications exist in both directions; and one-way paths, along which wireless communications exist in only one direction. Assuming that sensor nodes have different transmission radii, while relay nodes use the same transmission radius, this paper comprehensively analyzes the range of problems introduced by the different levels of fault-tolerance (full or partial) coupled with the different types of path (one-way or two-way). Since each of these problems is NP-hard, we develop O(sigmak2)-approximation algorithms for both one-way and two-way partial fault-tolerance relay node placement, as well as O(sigmak3)-approximation algorithms for both one-way and two-way full fault-tolerance relay node placement (sigma is the best performance ratio of existing approximation algorithms for finding a minimum k-vertex connected spanning graph). To facilitate the applications in higher dimensions, we also extend these algorithms and derive their performance ratios in d-dimensional heterogeneous wireless sensor networks (d ges 3). Finally, heuristic implementations of these algorithms are evaluated via simulations.

Topology control problems are concerned with the assignment of power levels to the nodes of an ad-hoc network so as to maintain a specified network topology while minimizing the energy consumption of the network nodes. A two-tiered network model has been proposed recently for prolonging the lifetime and improving the scalability in ad-hoc sensor networks. Such networks however may suffer from the failure of relay nodes causing the network to lose functionality. While considerable attention has been given to the issue of fault-tolerance in such networks, all of the prior work has been concerned with maintaining a 2-connected network. In this paper, we consider an alternative approach, namely optimal relay node fault recovery, in which the network topology is required to be just 1-connected and when a relay node fails, we replace that node with a new relay node that is placed in a position such that the power level assigned to the new node is optimal. In general this will not be the original node position or power assignment. We study three versions of optimal relay node fault recovery that vary in the degree to which the original network nodes can be reconfigured (i.e. have adjustments made to their power levels) when adding the new relay node into the network. For each version, we provide a polynomial time algorithm that provides an optimal placement and power assignment for the new relay node.

Controlling the topology of a wireless ad hoc network is very important from the point of view of performance. One known technique for controlling the topology is through the assignment of appropriate transmission power levels to the nodes. Such an assignment aims to minimize a specified function of the powers assigned to nodes. While this problem has been widely studied for the case of stationary wireless networks, few reported theoretical results for mobile wireless networks (MANETs). In this paper, we consider the topology control problem for MANETs from a theoretical perspective. We define a topology control problem under the constant rate mobile network model. In this model, all the n nodes in the network may move. Associated with each moving node are its constant moving speed and direction. The goal is to minimize the maximum power used by any network node in producing a connected network. We provide two polynomial algorithms for solving this problem: one for the decision version, the other for the optimization version.

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 consumption of the network nodes. While considerable theoretical attention has been given to the issue of topology control in wireless ad hoc networks, all of that work has concerned stationary networks. In this paper we carry out a theoretical study of a topology control problem in mobile wireless ad hoc networks (MANETs). For MANETs, we define a topology control problem under the Simple Mobile Network model, where there is one moving node and n stationary nodes. The goal is to minimize the maximum power used by any node in producing a connected network. We provide three polynomial algorithms for solving this problem. Surprisingly, the fastest algorithm runs as fast as the best known algorithm for stationary networks.

In this paper a distributed topology control for stationary and mobile ad hoc networks is described. A topology control algorithm is aimed at maintaining connectivity in a mobile network while minimizing power consumption under the MinMax objective. The algorithm is proactive so that the network connectivity is guaranteed at any time instant. In regard to the topology of the graph induced by the power assignments to the network nodes, the most common objective and the objective considered in this paper is that the network be connected

The topology of an ad hoc network has a significant impact on its performance in that a dense topology may induce high interference and low capacity, while a sparse topology is vulnerable to link failure and network partitioning. Topology control aims to maintain a topology that optimizes network performance while minimizing energy consumption. Existing topology control algorithms utilize either a purely centralized or a purely distributed approach. A centralized approach, although able to achieve strong connectivity (k-connectivity for k /spl ges/ 2), suffers from scalability problems. In contrast, a distributed approach, although scalable, lacks strong connectivity guarantees. We propose a hybrid topology control framework, cluster-based topology control (CLTC) that achieves both scalability and strong connectivity. By varying the algorithms utilized in each of the three phases of the framework, a variety of optimization objectives and topological properties can be achieved. In this paper, we present the CLTC framework; describe topology control algorithms based on CLTC and prove that k-connectivity is achieved using those algorithms; analyze the message complexity of an implementation of CLTC, namely, CLTC-A, and present simulation studies that evaluate the effectiveness of CLTC-A for a range of networks.

In this paper we present the design and implementation of a class ordering system that is driven by a parameterized cost model. The parameters to the model assign weights to the edge types that describe the relationships between the classes in the graphical representation of the program. The nodes in the graph are classes and the edges express relationships between the classes. Previous research has included three or four edge types in the graph. However, to accommodate the full complement of C++ language constructs, which include template classes and functions and nested classes, we extend the graph to include six edge types. The parameters to the cost model can be tuned to remove certain types of edges in an attempt to reduce the cost of the testing effort or to reduce the cost of breaking cycles in the graph. Our case study indicates that inclusion of inheritance edges in cycle breaking considerations may reduce the number of edge removals by a factor of two or more.

Topology control problems are concerned with the assignment of power values to the nodes of an ad hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called textbf monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be bf NP -complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is obtained. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.

The problem of maintaining an approximate solution for one-dimensional bin packing when items may arrive and depart dynamically is studied. In accordance with various work on fully dynamic algorithms, and in contrast to prior work on bin packing, it is assumed that the packing may be arbitrarily rearranged to accommodate arriving and departing items. In this context our main result is a fully dynamic approximation algorithm for bin packing MMP that is $\frac{5}{4}$-competitive and requires $\Theta(\log n)$ time per operation (i.e., for an Insert or a Delete of an item). This competitive ratio of $\frac{5}{4}$ is nearly as good as that of the best practical off-line algorithms. Our algorithm utilizes the technique (introduced here) whereby the packing of an item is done with a total disregard for already packed items of a smaller size. This myopic packing of an item may then cause several smaller items to be repacked (in a similar fashion). With a bit of additional sophistication to avoid certain "bad" cases, the number of items (either individual items or "bundles" of very small items treated as a whole) that needs to be repacked is bounded by a constant.

The problem of maintaining an approximate solution for one-dimensional bin packing when items may arrive dynamically is studied. In accordance with various work on dynamic algorithms, and in contrast to prior work on bin packing, it is assumed that the packing may be arbitrarily rearranged to accommodate arriving items. In this context we show that partially dynamic bin packing (Inserts only) can be solved within 1 + ε in amortized polylogarithmic time.

A new approach is given for scheduling a sequential instruction stream for execution "in parallel" on asynchronous multiprocessors. The key idea in our approach is to exploit the fine grained parallelism present in the instruction stream. In this context, schedules are constructed by a careful balancing of execution and communication costs at the level of individual instructions, and their data dependencies. Three methods are used to evaluate our approach. First, several existing methods are extended to the fine grained situation. Our approach is then compared to these methods using both static schedule length analyses, and simulated executions of the scheduled code. In each instance, our method is found to provide significantly shorter schedules. Second, by varying parameters such as the speed of the instruction set, and the speed/parallelism in the interconnection structure, simulation techniques are used to examine the effects of various architectural considerations on the executions of the schedules. These results show that our approach provides significant speedups in a wide-range of situations. Third, schedules produced by our approach are executed on a two-processor Data General shared memory multiprocessor system. These experiments show that there is a strong correlation between our simulation results, and these actual executions, and thereby serve to validate the simulation studies. Together, our results establish that fine grained parallelism can be exploited in a substantial manner when scheduling a sequential instruction stream for execution "in parallel" on asynchronous multiprocessors.>

Algorithms for transmission scheduling in multihop broadcast radio networks are presented. Both link scheduling and broadcast scheduling are considered. In each instance, scheduling algorithms are given that improve upon existing algorithms both theoretically and experimentally. It is shown that tree networks can be scheduled optimally and that arbitrary networks can be scheduled so that the schedule is bounded by a length that is proportional to a function of the network thickness times the optimum. Previous algorithms could guarantee only that the schedules were bounded by a length no worse than the maximum node degree times optimum. Since the thickness is typically several orders of magnitude less than the maximum node degree, the algorithms presented represent a considerable theoretical improvement. Experimentally, a realistic model of a radio network is given and the performance of the new algorithms is studied. These results show that, for both types of scheduling, the new algorithms (experimentally) perform consistently better than earlier methods.>

New algorithms for transmission scheduling in multihop broadcast radio networks are presented. Both link scheduling and broadcast scheduling are considered. In each instance scheduling algorithms are given that improve upon existing algorithms both theoretically and experimentally. Theoretically, it is shown that tree networks can be scheduled optimally, and that arbitrary networks can be scheduled so that the schedule is bounded by a length that is proportional to a function of the network thickness times the optimum. Previous algorithms could guarantee only that the schedules were bounded by a length no worse than the maximum node degree, the algorithms presented here represent a considerable theoretical improvement. Experimentally, a realistic model of a radio network is given and the performance of the new algorithms is studied. These results show that, for both types of scheduling, the new algorithms (experimentally) perform consistently better than earlier methods.

Much of the recent work on the automated design of VLSI chips has concentrated on routing problems associated with such designs. One major class of routing problems focuses on single-row routing. Recently, the traditional single-row routing model has been generalized to allow external wires. Under this generalized model, it is possible to route many more single-row routing instances than in the traditional model. There is, however, a clear disadvantage in the use of external wires, since they force a lengthening of the channels surrounding the single row of terminals. Thus, it is desirable for these generalized single-row routings to use a minimum number of external wires. A linear-time algorithm for determining the minimum number of external wires needed to route a given instance of single-row routing is provided here.>

The problem of optimally folding a Programmable Logic Array (PLA) is known to be NP-complete. Motivated by the practical importance of this problem, we address the question of obtaining good, though not necessarily optimal, foldings. Two sets of results are presented. First, we show that three natural variants of the folding problem are equivalent with respect to approximation, in the sense that either they are all efficiently approximable or none of them is efficiently approximable. Next, we show for one of the variants (optimal bipartite folding) that if there is a polynomial time approximation algorithm (heuristic) which, for every PLA, produces a folding that is within a fixed factor of an optimal folding, then for any constant $\varepsilon > 0$, there is a heuristic which, for every PLA, produces a folding that is within a factor of $(1+\varepsilon )$ of the optimal folding. This result strongly suggests that the optimal folding problem is not efficiently approximable for arbitrary PLAs. In a companion paper, we have presented efficient heuristics for certain restricted classes of PLAs.

The problem of finding a minimum cardinality feedback vertex set of a directed graph is considered. Of the classic NP-complete problems, this is one of the least understood. Although Karp showed the general problem to be NP-complete, a linear algorithm for its solution on reducible flow graphs was given by Shamir. The class of reducible flow graphs is the only nontrivial class of graphs for which a polynomial-time algorithm to solve this problem is known. The main result of this paper is to present a new class of graphs—the cyclically reducible graphs —for which minimum feedback vertex sets can be found in polynomial time. This class is not restricted to flow graphs, and most small graphs (10 or fewer nodes) fall into this class. The identification of this class is particularly important since there do not exist approximation algorithms for this problem having a provably good worst case performance. Along with the class and a simple polynomial-time algorithm for finding minimum feedback vertex sets of graphs in the class, several related results are presented. It is shown that there is no “forbidden subgraph” characterization of the class and that there is no particular inclusion relationship between this class and the reducible flow graphs. In addition, it is shown that a class of (general) graphs, which are related to the reducible flow graphs, are contained in the cyclically reducible class.

An investigation IS made of the worst-case performance of two related algorithms for scheduhng umt-execut~on-ume task systems w~th resources Unhke most prewous scheduhng results for task systems w~th resources, ~t ~s assumed that there are afixed number of processors m the system.This assumption has both practical and theoreucal interest An upper bound is gwen for the worst-case performance of critical path scheduhng for these task systems This bound depends on both the number of processors and the number of resources Moreover, it is shown that th~s is (asymptotically) the best possible upper bound It is also noted that exactly the same bound holds for the worst-case performance of Coffman-Graham scheduhng Categories and Subject Descriptors.D 4 1 [Operating Systems[' Process Management--scheduhng, F 2 2 [Analysis of Algorithms and Problem Complexity] Nonnumencal Algorithms and Problems--sequencing and scheduhng General Terms Algonthrns, Performance, Theory

Minimum execution time scheduling of unit execution time (UET) task systems with resources has been the subject of several papers over the past few years. Because such scheduling problems are, in general, NP-hard, a variety of heuristic methods for producing schedules have been studied, among them, critical path scheduling. The strongest results to date have been for systems where there is no processor constraint. These results may be utilized for systems with a processor constraint by treating the processors as an additional resource. Unfortunately, in those cases where the number of processors is close to the number of resources, this results in an upper bound which is somewhat misleading. In this paper we investigate the performance of critical path scheduling for UET task systems with resources and a fixed number of processors. An upper bound for the worst case performance of critical path scheduling is given. This bound depends both on the number of processors and on the number of different resources. Moreover, we show that this is the best possible (asymptotic) upper bound.

A set, V, of points in the plane is triangulated by a subset T, of the straight-line segments whose endpoints are in V, if T is a maximal subset such that the line segments in T intersect only at their endpoints. The weight of any triangulation is the sum of the Euclidean lengths of the line segments in the triangulation. We examine two problems involving triangulations. We discuss the problem of finding a minimum weight triangulation among all triangulations of a set of points and give counterexamples to two published solutions to this problem. Secondly, we show that the problem of determining the existence of a triangulation, in a given subset of the line segments whose endpoints are in V, is NP-Complete.