New algorithms are presented to optimally place storage nodes in a sensor network consisting of a path so as to minimize the communication cost of convergecasting towards the sink the data gathered into storage nodes in reply to queries. Such algorithms are faster than previously known algorithms and require optimal running time for finding the optimal storage placement.

In this work, we consider a large-scale geographic area populated by tiny sensors and some more powerful devices called actors, authorized to organize the sensors in their vicinity into short-lived, actor-centric sensor networks. The tiny sensors run on miniature nonrechargeable batteries, are anonymous, and are unaware of their location. The sensors differ in their ability to dynamically alter their sleep times. Indeed, the periodic sensors have sleep periods of predefined lengths, established at fabrication time; by contrast, the free sensors can dynamically alter their sleep periods, under program control. The main contribution of this work is to propose an energy-efficient location training protocol for heterogeneous actor-centric sensor networks where the sensors acquire coarse-grain location awareness with respect to the actor in their vicinity. Our theoretical analysis, confirmed by experimental evaluation, shows that the proposed protocol outperforms the best previously known location training protocols in terms of the number of sleep/awake transitions, overall sensor awake time, and energy consumption.

Scalable energy-efficient training protocols are proposed for wireless networks consisting of sensors and a single actor, where the sensors are initially anonymous and unaware of their location. The protocols are based on an intuitive coordinate system imposed onto the deployment area, which partitions the sensors into clusters. The protocols are asynchronous, in the sense that the sensors wake up for the first time at random, then alternate between sleep and awake periods both of fixed length, and no explicit synchronization is performed between them and the actor. Theoretical properties are stated under which the training of all the sensors is possible. Moreover, both worst-case and average case analyses of the performance, as well as an experimental evaluation, are presented showing that the protocols are lightweight and flexible.

Abstract Given a vector (δ1,δ2,…,δt) of nonincreasing positive integers, and an undirected graphG= (V,E), anL(δ1,δ2,…,δt)‐coloring ofGis a functionffrom the vertex setVto a set of nonnegative integers such that ∣f(u) −f(v)∣ ≥ δi, ifd(u,v) =i, 1 ≤i≤t, whered(u,v) is the distance (i.e., the minimum number of edges) between the verticesuandv. An optimalL(δ1,δ2,…,δt)‐coloring forGis one minimizing the largest integer used over all such colorings. Such a coloring problem has relevant applications in channel assignment for interference avoidance in wireless networks. This article presents efficient approximation algorithms forL(δ1,δ2,…,δt)‐coloring of two relevant classes of graphs—trees, and interval graphs. Specifically, based on the notion of strongly simplicial vertices,O(n(t+ δ1)) andO(nt2δ1) time algorithms are proposed to find α‐approximate colorings on interval graphs and trees, respectively, wherenis the number of vertices and α is a constant depending ontand δ1,…,δt. Moreover, anO(n) time algorithm is given for theL(δ1,δ2)‐coloring of unit interval graphs, which provides a 3‐approximation. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 204–216 2007

This paper presents several fault-tolerant extensions of the Rate-Monotonic First-Fit multiprocessor scheduling algorithm handling both active and passive task copies. In particular, the technique of backup phasing delay is used to reduce the portions of active task copies that must be always executed and to deallocate active task copies as soon as their primary task copies have been successfully executed. It is also shown how to employ this technique while considering passive task duplication so as to over-book each processor with many passive task copies, assigning tasks to processors in such a way that tasks with equal or multiple periods have a high chance to be assigned to the same processor, and partitioning the processors into groups to avoid the mix of primary, active, and passive task copies on the same processor. Extensive simulations reveal a remarkable saving of both the overall number of processors used and the total computation time of the schedulability test (achieved especially by two new algorithms, called ARR3 and S-PR-PASS) with respect to previously proposed algorithms

The problem of data broadcasting over multiple channels consists in partitioning data among channels, depending on data popularities, and then cyclically transmitting them over each channel so that the average waiting time of the clients is minimized. Such a problem is known to be polynomially time solvable for uniform length data items, while it is computationally intractable for non-uniform length data items. In this paper, two new heuristics are proposed which exploit a novel characterization of optimal solutions for the special case of two channels and data items of uniform lengths. Sub-optimal solutions for the most general case of an arbitrary number of channels and data items of non-uniform lengths are provided. The first heuristic, called Greedy+, combines the novel characterization with the known greedy approach, while the second heuristic, called Dlinear, combines the same characterization with the dynamic programming technique. Such heuristics have been tested on benchmarks whose popularities are characterized by Zipf distributions. The experimental tests reveal that Dlinear finds optimal solutions almost always, requiring good running times, while Greedy+ is faster and scales well when changes occur on the input parameters, but provides worse solutions than Dlinear

Broadcast is an efficient and scalable way of transmitting data to an unlimited number of clients that are listening to a channel. Cyclically broadcasting data over the channel is a basic scheduling technique, which is known as flat scheduling. When multiple channels are available, a data allocation technique is needed to assign data to channels. Partitioning data among channels in an unbalanced way, depending on data popularities, is an allocation technique known as skewed allocation. The problem of data broadcasting over multiple channels is considered, assuming skewed data allocation to channels and flat data scheduling per channel, with the objective of minimizing the average waiting time of the clients. First, several algorithms, based on dynamic programming, are presented which provide optimal solutions for N data items and K channels. Specifically, for data items with uniform lengths, an O(NK log N) time algorithm is proposed, which improves over the previously known O(N/sup 2/K) time algorithm. When K/spl les/4, a simpler O(N log N) time algorithm is exhibited which requires only O(N) time if the data items are sorted. Moreover, for data items with nonuniform lengths, it is shown that the problem is NP-hard when K=2 and strong NP-hard for arbitrary K. In the former case, a pseudopolynomial algorithm is discussed whose time is O(NZ), where Z is the sum of the data lengths. In the latter case, an algorithm is devised with time exponential in the maximum data length, which can optimally solve, in reasonable time, only small instances. For larger instances, a new heuristic is devised which is experimentally tested on some benchmarks whose popularities are characterized by Zipf distributions. Such experimental tests reveal that the new heuristic proposed here always outperforms the best previously known heuristic in terms of solution quality.

Summary form only given. Broadcast is an efficient and scalable way of transmitting data to an unlimited number of clients that are listening to a channel. Cyclically broadcasting data over the channel is a basic scheduling technique, which is known as flat scheduling. When multiple channels are available, partitioning data among channels in an unbalanced way, depending on data popularities, is an allocation technique known as skewed allocation. In this paper, the problem of data broadcasting over multiple channels is considered assuming skewed data allocation to channels and fiat data scheduling per channel, with the objective of minimizing the average waiting time of the clients. Several algorithms, based on dynamic programming, are presented which provide optimal solutions for N data items and K channels. Specifically, for data items with uniform lengths, an O(NKlogN) time algorithm is proposed, which improves over the previously known O(N/sup 2/K) time algorithm. When K /spl les/ 4, faster O(N) time algorithms are exhibited. Moreover, for data items with nonuniform lengths, it is shown that the problem is NP-hard when K = 2, and strong NP-hard for arbitrary K. In the former case, a pseudo-polynomial algorithm is discussed, whose time is O(NZ) where Z is the sum of the data lengths.

The classification problem transforms a set of N numbers in such a way that none of the first N/2 numbers exceeds any of the last N/2 numbers. A comparator network that solves the classification problem on a set of r numbers is commonly called an r-classifier. We show how the well-known Leighton's Columnsort algorithm can be modified to solve the classification problem of N=rs numbers, with 1 /spl les/ s /spl les/ r, using an r-classifier instead of an r-sorting network. Overall, the r-classifier is used O(s) times, namely, the same number of times that Columnsort applies an r-sorter. A hardware implementation is proposed that runs in optimal O(s+logr) time and uses an O(rlogr(s + logr)) work. The implementation shows that, when N= rlogr, there is a classifier network solving the classification problem on N numbers in the same O(logr) time and using the same O(rlogr) comparators as an r-classifier, thus saying a logr factor in the number of comparators over an (rlogr)-classifier.

Given an integer /spl sigma/>1, a vector (/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/), of nonnegative integers, and an undirected graph G=(V, E), an L(/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/)-coloring of G is a function f from the vertex set V to a set of nonnegative integers, such that |f(u)-f(v)|/spl ges//spl delta//sub i/, if d(u,v)=i, for 1<i<(/spl sigma/-1), where d(u, v) is the distance (i.e., the minimum number of edges) between the vertices u and v. An optimal L(/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/)-coloring for G is one using the smallest range /spl lambda/ of integers over all such colorings. This problem has relevant application in channel assignment for interference avoidance in wireless networks, where channels (i.e., colors) assigned to interfering stations (i.e., vertices) at distance i must be at least /spl delta//sub i/ apart, while the same channel can be reused in vertices whose distance is at least /spl sigma/. In particular, two versions of the coloring problem - L(2, 1, 1) and L(/spl delta//sub 1/, 1,..., 1) - are considered. Since these versions of the problem are NP-hard for general graphs, efficient algorithms for finding optimal colorings are provided for specific graphs modeling realistic wireless networks, including rings, bidimensional grids, and cellular grids.

Several dynamic programming algorithms are considered which can be efficiently implemented using parallel networks with reconfigurable buses. The bit model of general reconfigurable meshes with directed links, common write, and unit-time delay for broadcasting is assumed. Given two sequences of length m and n, respectively, their longest common subsequence can be found in constant time by an O(mh)/spl times/O(nh) directed reconfigurable mesh, where h=min{m, n}+1. Moreover, given an n-node directed graph G=(V, E) with (possibly negative) integer weights on its arcs, the shortest distances from a source node /spl nu/ /spl epsiv/ V to all other nodes can be found in constant time by an O(n/sup 2/w) x O(n/sup 2/w) directed reconfigurable mesh, where w is the maximum are weight.

Several new number representations based on a residue number system are presented which use the smallest prime numbers as moduli and are suited for parallel computations on a reconfigurable mesh architecture. The bit model of linear reconfigurable mesh with exclusive write and unit-time delay for broadcasting on a subbus is assumed. It is shown how to convert in O(1) time any integer, ranging between 0 and n-1, from any commonly used representation to any new representation proposed in this paper (and vice versa) using an nxO(log2n/log log n) reconfigurable mesh. In particular, some of the previously known conversion techniques are improved. Moreover, as a byproduct, it is shown how to compute in O(1) time the Prefix Sums of n bits by a reconfigurable mesh having the above mentioned size, thus improving previously known results. Applications to the Prefix Sums of n h-bit integers and to Approximate String Matching with α mismatches are also considered. The Summation and the Prefix Sums can be computed in O(1) time using O(h log N+log2N/log log N)xNh and O(h2+log2N/log(h+log N))xO(N(h+log N)) reconfigurable meshes, respectively. Moreover, it is shown for the first time how to find in O(1) time all the occurrences of a pattern of length m in a text of length n, allowing less than α mismatches, using a reconfigurable mesh of size O(m log|Σ|)xO (n(log|Σ|+log2α/log log α)), where the pattern and the text are strings over a finite alphabet Σ and α < m

New heuristic algorithms are proposed for the Graph Partitioning problem. A greedy construction scheme with an appropriate tie-breaking rule (MIN-MAX-GREEDY) produces initial assignments in a very fast time. For some classes of graphs, independent repetitions of MIN-MAX-GREEDY are sufficient to reproduce solutions found by more complex techniques. When the method is not competitive, the initial assignments are used as starting points for a prohibition-based scheme, where the prohibition is chosen in a randomized and reactive way, with a bias towards more successful choices in the previous part of the run. The relationship between prohibition-based diversification (Tabu Search) and the variable-depth Kernighan-Lin algorithm is discussed, Detailed experimental results are presented on benchmark suites used in the previous literature, consisting of graphs derived from parametric models (random graphs, geometric graphs, etc.) and of "real-world" graphs of large size. On the first series of graphs, a better performance for equivalent or smaller computing times is obtained, while, on the large "real-world" instances, significantly better results than those of multilevel algorithms are obtained, but for a much larger computational effort.

Hard-real-time systems require predictable performance despite the occurrence of failures. In this paper, fault tolerance is implemented by using a novel duplication technique where each task scheduled on a processor has either an active backup copy or a passive backup copy scheduled on a different processor. An active copy is always executed, while a passive copy is executed only in the case of a failure. First, the paper considers the ability of the widely-used rate-monotonic scheduling algorithm to meet the deadlines of periodic tasks in the presence of a processor failure. In particular, the completion time test is extended so as to check the schedulability on a single processor of a task set including backup copies. Then, the paper extends the well-known rate-monotonic first-fit assignment algorithm, where all the task copies, included the backup copies, are considered by rate-monotonic priority order and assigned to the first processor in which they fit. The proposed algorithm determines which tasks must use the active duplication and which can use the passive duplication. Passive duplication is preferred whenever possible, so as to overbook each processor with many passive copies whose primary copies are assigned to different processors. Moreover, the space allocated to active copies is reclaimed as soon as a failure is detected. Passive copy overbooking and active copy deallocation allow many passive copies to be scheduled sharing the same time intervals on the same processor, thus reducing the total number of processors needed. Simulation studies reveal a remarkable saving of processors with respect to those needed by the usual active duplication approach in which the schedule of the non-fault-tolerant case is duplicated on two sets of processors.

Several new number representations based on the residue number system are presented which use the smallest prime numbers as moduli and are suited for parallel computations on a reconfigurable mesh architecture. It is shown how to convert in O(1) time any integer ranging between 0 and n-1, from any commonly used representation to any new representation proposed in the paper (and vice versa) using an n/spl times/O(log/sup 2/n/log log n) reconfigurable mesh. In particular, some of the previously known conversion techniques are improved. Moreover, as a by product, it is shown how to compute in O(1) time the prefix sums of n bits improving previously known results. Applications to the summation and prefix sums of N h-bit integers are also considered. The summation and the prefix sums can be computed in O(1) time using O(h log N+log/sup 2/N/log log N)/spl times/Nh and O(h/sup 2/+log/sup 2/ N/log(h+log N))/spl times/O(N(h+log N)) reconfigurable meshes, respectively, improving all previously known results for most values of h including, for instance, h=O(log N).

Hidden terminal interference is caused by the (quasi-) simultaneous transmission of two stations that cannot hear each other, but are both received by the same destination station. This interference lowers the system throughput and increases the average packet delay. Some random access protocols that reduce this interference have been proposed, e.g., BTMA protocol. However, the hidden terminal interference can be totally avoided only by means of code division multiple access (CDMA) schemes. In the paper, the authors investigate the problem of assigning orthogonal codes to stations so as to eliminate the hidden terminal interference. Since the codes share the fixed channel capacity allocated to the network in the design stage, their number must not exceed a given bound. The authors seek assignments that minimize the number of codes used. They show that this problem is NP-complete, and thus computationally intractable, even for very restricted but very realistic network topologies. Then, they present optimal algorithms for further restricted topologies, as well as fast suboptimal centralized and distributed heuristic algorithms. The results of extensive simulation set up to derive the average performance of the proposed heuristics on realistic network topologies are presented.>

Hidden terminal interference is caused by the simultaneous transmission of two stations that cannot hear each other, but are both received by the same destination station. The authors investigate the problem of assigning orthogonal codes to stations to eliminate the hidden terminal interference and minimize the number of codes used. It is shown that this problem is computationally intractable, even for very restricted but very realistic network topologies. Optimal algorithms for code assignment in special networks, as well as both centralized and distributed suboptimal heuristic algorithms for general topologies, are presented. The results of extensive simulations to derive the average performance of the proposed heuristics on realistic network topologies are presented.>

The use of a fault-tolerant VLSI system for storing and solving linear programming problems is presented. The system can bear multiple faults in processing elements and/or links and still function with an acceptable performance degradation. It is based on an interconnection pattern consisting of a complete binary tree in which spare links between cousin nodes are added so as to reconfigure it as a ternary tree. At any given time of a computation, faulty processing elements and/or links are circumvented by using such spare links. It is shown that the total silicon area required by this structure is only a constant factor higher than that of a complete binary tree. The result is used to give an efficient implementation of the simplex algorithm in which the time required to perform a single pivot step matches a previously established lower bound for tree machines in spite of faults.>

In an undirected graph, a subset X of the nodes is a total dominating set if each node in the graph is a neighbor of some node in X. In contrast, X is an irredundant set if the closed neighborhood of each node in X is not contained in the union of closed neighborhoods of the other nodes in X. This paper gives $O( n\log n )$ and $O( n^4 )$ time algorithms for finding, respectively, a minimum weighted total dominating set and a minimum weighted maximal irredundant set in a weighted interval graph, i.e., one that represents n intersecting intervals on the real line, each having a (possibly negative) real weight.

Abstract Two bipartite matching problems arising in Vehicle Scheduling are considered: the capacitated matching and the multicommodity matching. For the former, given a reasonable cost structure, we can exhibit a polynomial time algorithm, while the general case is conjectured to be NP‐hard. The latter problem is shown to be NP‐hard. A heuristic algorithm based on Lagrangean relaxation for the capacitated version of the multicommodity matching is also presented together with experimental results.

The use of a special-purpose VLSI chip for solving a linear programming problem is presented. The chip is structured as a mesh of trees and is designed to implement the well-known simplex algorithm. A high degree of parallelism is introduced in each pivot step, which can be carried out in O (log n) time using an m × n mesh of trees having an O(mn log m log3 n) area where m − 1 and n − 1 are the number of constraints and variables, respectively. Two variants of the simplex algorithm are also considered: the two-phase method and the revised one. The proposed chip is intended as being a possible basic block for a VLSI operations research machine.

In this paper we study the time slot assignment problem in clusters of SS/TDMA satellite systems interconnected through intersatellite links. We show that the problem of finding an assignment which minimizes the total transmission time is NP-complete, i.e., computationally intractable, even for quite restricted intersatellite link patterns and simplified system models. Successively, we focus our attention on clusters of two satellites, proposing a branch-and-bound optimal algorithm and two fast heuristic algorithms. We investigate the performance of the proposed heuristic algorithms both by a theoretical worst case bound and by simulation trials showing that the produced solutions are close to the optimal on the average.