Search

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. [ABSTRACT FROM PUBLISHER]

Broadcasting is an efficient and scalable way of transmitting data over wireless channels to an unlimited number of clients. In this paper the problem of allocating data to multiple channels is studied, assuming flat data scheduling per channel and the presence of unrecoverable channel transmission errors. The objective is that of minimizing the average expected delay experienced by the clients. Two different channel error models are considered: the Bernoulli model and the simplified Gilbert–Elliot one. In the former model, each packet transmission has the same probability to fail and each transmission error is independent from the others. In the latter one, bursts of erroneous or error-free packet transmissions due to wireless fading channels are modeled. Particular cases are detected where optimal solutions can be found in polynomial time. For general cases, simulations show that good sub-optimal solutions can be found on benchmarks whose item popularities follow Zipf distributions. [ABSTRACT FROM AUTHOR]

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 FROM AUTHOR]

Abstract: Phenomenal advances in nano-technology and packaging have made it possible to develop miniaturized low-power devices that integrate sensing, special-purpose computing, and wireless communications capabilities. It is expected that these small devices, referred to as sensors, will be mass-produced and deployed, making their production cost negligible. Due to their small form factor and modest non-renewable energy budget, individual sensors are not expected to be GPS-enabled. Moreover, in most applications, exact geographic location is not necessary, and all that the individual sensors need is a coarse-grain location awareness. The task of acquiring such a coarse-grain location awareness is referred to as training. In this paper, two scalable energy-efficient training protocols are proposed for massively-deployed sensor networks, where sensors are initially anonymous and unaware of their location. The training protocols are lightweight and simple to implement; they are based on an intuitive coordinate system imposed onto the deployment area which partitions the anonymous sensors into clusters where data can be gathered from the environment and synthesized under local control. [Copyright &y& Elsevier]

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. In this paper, 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 0(NK log N) time algorithm is proposed, which improves over the previously known 0(N2K) time algorithm. When K ≤ 4, a simpler 0(NlogN) time algorithm is exhibited which requires only 0(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. [ABSTRACT FROM AUTHOR]

Abstract: The large development of wireless services and the scarcity of the usable frequencies require an efficient use of the radio spectrum which guarantees interference avoidance. The channel assignment problem (CAP) achieves this goal by partitioning the radio spectrum into disjoint channels, and assigning channels to the network base stations so as to avoid interference. On a flat region without geographical barriers and with uniform traffic load, the network base stations are usually placed according to a regular plane tessellation, while the channels are permanently assigned to the base stations. This paper considers the CAP problem on the honeycomb grid network topology, where the plane is tessellated by regular hexagons. Interference between two base stations at a given distance is avoided by forcing the channels assigned to such stations to be separated by a gap which is proportional to the distance between the stations. Under these assumptions, the CAP problem on honeycomb grids can be modeled as a suitable coloring problem. Formally, given a honeycomb grid and a vector of positive integers, an -coloring of is a function from the vertex set to a set of nonnegative integers such that , if , where is the distance (i.e. the minimum number of edges) between the vertices and . An optimal -coloring for is one minimizing the largest used integer over all such colorings. This paper presents efficient algorithms for finding optimal -, - and -colorings of honeycomb grids. Such colorings use less colors than those needed by the cellular and square grids with the same number of vertices. [Copyright &y& Elsevier]

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. This paper shows how the well-known Leighton's Columnsort algorithm can be modified to solve the classification problem of N = rs numbers, with 1 ≤ s ≤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 + log r) time and uses an O(r log r(s + log r)) work. The implementation shows that, when N = r log r, there is a classifier network solving the classification problem on N numbers in the same O(log r) time and using the same O(r log r) comparators as an r-classifier, thus saving a log r factor in the number of comparators over an (r log r)-classifier. [ABSTRACT FROM AUTHOR]

This paper presents a constant slow-down, optimal and locally normal simulation for basic reconfigurable meshes on hypercubes, if the log-time delay model for broadcasting is assumed. Such a simulation algorithm is based on: (i) an O(log B) time algorithm for the segmented scan problem on a (2n−1)-node toroidal X-tree, where B is the size of the longest segment; this algorithm is time optimal; (ii) a constant slow-down optimal and locally normal simulation algorithm for basic reconfigurable meshes on the mesh of toroidal X-trees; and (iii) a constant slow-down optimal simulation of locally normal algorithms for meshes of toroidal X-trees on the hypercube. [Copyright &y& Elsevier]

Given an integer σ > l, a vector (δ[sub 1], …, δ[sub σ-1]) of nonnegative integers, and an undirected graph G = (V, E), an L(δ[sub 1], δ[sub 2], ···, δ[sub σ-1)-coloring of G is a function λ from the vertex set V to a set of nonnegative integers such that f(u) - f(v) ≥ δ[sub 1], if d(u, v) = i, 1 ≤ i ≤ σ -1, where d(u, v) is the distance (i.e., the minimum number of edges) between the vertices u and v. An optimal L(δ[sub 1], δ[sub 2], …, δ[sub σ-1])-coloring for G is one using the smallest range λ 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 δ[sub i] apart, while the same channel can be reused in vertices whose distance is at least σ. In particular, two versions of the coloring problem—L(2, 1, 1) and L(δ[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. [ABSTRACT FROM AUTHOR]

Since the divergence between the processor speed and the memory access rate is progressively increasing, an efficient partition of the main memory into multibanks is useful to improve the overall system performance. The effectiveness of the multibank partition can be degraded by memory conflicts, that occur when there are many references to the same memory bank while accessing the same memory pattern. Therefore, mapping schemes are needed to distribute data in such a way that data can be retrieved via regular patterns without conflicts. In this paper, the problem of conflict-free access of arbitrary paths in bidimensional arrays, circular lists and complete trees is considered for the first time and reduced to variants of graph-coloring problems. Balanced and fast mappings are proposed which require an optimal number of colors (i.e., memory banks). The solution for bidimensional arrays is based on a particular Latin Square. The functions that map an array node or a circular list node to a memory bank can be calculated in constant time. As for complete trees, the mapping of a tree node to a memory bank takes time that grows logarithmically with the number of nodes of the tree. The problem solved here has further application in minimizing the number of frequencies assigned to the stations of a wireless network so as to avoid interference. [Copyright &y& Elsevier]

Investigates the problem of assigning channels or codes to the cells of a cellular radio network to avoid interference and minimize the number of channels used. Adaptation of the randomized saturation degree heuristic to the channel assignment problem (CAP); Components of a cellular network; How CAP is solved by local search algorithms.

Presents several number representations based on a Residue Number System which use the smallest prime numbers as moduli and are suited for parallel computations on a reconfigurable mesh architecture. Assumption of the bit model of linear reconfigurable mesh; Improvement of some of the previously known conversion techniques.

Proposes a dynamic programming algorithms using parallel networks with reconfigurable buses. Components of the reconfigurable networks model; Solutions for Longest Common Subsequence and Single-Source Shortest Paths problems; Dependence of several variants of the model with partitions, subbus arbitration and local memory size.

Focuses on the implementation of a fault-tolerant rate Rate-Monotonic first-fit scheduling in hard-real-time computer systems. Ability of the Rate-Monotonic scheduling algorithm to meet the deadlines of periodic tasks; Extension of the Rate-Monotonic First-Fit assignment algorithm; Tasks that should make use of the active and the passive duplication.

Proposes the heuristic algorithms for the Graph Partitioning problem. Areas of computer science where the partitioning problem arise; Test beds and experimental setup; Details on the greedy construction algorithm for the problem; Prohibition-based search; Fixed-Tabu Search (TS) for graph partitioning; Randomized prohibition; Conclusions.