Urban delivery by Unmanned Aerial Vehicles (UAVs), or drones, is a promising logistics solution. While a dominant vision involves drones navigating autonomously through complex open airspace, this approach demands advanced perception and control capabilities. In contrast, this work explores an alternative vision: low-altitude drone flight along obstacle-free existing road networks, leveraging digital maps. To assess the feasibility of this approach, we investigate the indirect risks associated with drone failures, specifically, the risk that a falling drone causes a traffic-related accident. We show that, under dry conditions, the score risk meets the aviation-grade safety expectations (usually 10−6fatal injuries per flight hour) under any traffic level when vehicle speeds are low or moderate (below 50km/h), and under low traffic conditions (1 car every 100 seconds) when the vehicle speed is above 70 km/h. We also analyze the impact of contextual factor such as wet road conditions, and nighttime driving into the risk score: at low speed (30 km/h), the safety aviation requirements are always met. These findings represent a first step toward establishing the potential safety of road-aligned drone navigation in urban environments.

Unmanned Aerial Vehicles (UAVs) are increasingly permitted to operate within Visual Line of Sight (VLoS) under EU and US regulations. However, Beyond Visual Line of Sight (BVLoS) operations remain restricted, with waivers or certifications required. Extended Visual Line of Sight (EVLoS) offers a transitional solution, involving trained observers to assist pilots when visibility is obstructed. We propose enhancing EVLoS by integrating ground infrastructure, specifically city cameras and wireless communication networks already available on the ground, to replace human observers and enable BVLoS capabilities. Fixed and mobile cameras track drones to ensure regulatory compliance, while real-time data transmission via communication networks provides indirect oversight. The approach increases operational range, reliability, and redundancy through multi-hop connectivity. We introduce the Minimum Latency Problem (MLP), a UAV multi-trajectory optimization problem where UAVs are constantly tracked and monitored through ground antennas and city cameras, mimicking the human observers in EVLoS. Our goal is to minimize communication latency while ensuring that the number of antennas used for coverage is minimum. We prove MLP is$N P$-hard and propose an algorithm to solve it. Experiments on synthetic data demonstrate the effectiveness of our approach in matching coverage and latency requirements.

In this paper, we investigate the problem of deploying the minimum number of Unmanned Aerial Vehicles (UAVs) and determining their flying tours to collect data from all Internet of Things (IoT) sensors. We study this problem in a scenario with neighborhoods where a UAV can collect data from an IoT sensor if the distance between them is less than the wireless communication range of the IoT sensor. Since UAVs are powered by batteries with a limited amount of energy, we assume that the total energy consumed during the flying tour of each UAV is bounded by a given budget. We present the Minimum rooted drone Deployment Problem with Neighborhoods (MDPN), which is NP-hard, and propose two approximation algorithms for the single-depot case, where one of them is a bi-criteria approximation algorithm that returns a solution whose tour’s cost is violated by a factor of 1 + ε. Furthermore, we extend these two algorithms to the multi-depot scenario. Finally, we evaluate our algorithms in three different scenarios: the ideal one where the communication range is a circle and the data transfer rate is constant, and two more realistic scenarios where we introduce some degree of irregularity in the communication range and a non-constant rate in data transfer.

Unmanned aerial vehicles (UAVs) are crucial in various civilian applications, especially in Beyond Visual Line of Sight (BVLoS) operations. However, current regulations restrict BVLoS flights to specific corridors for safety reasons. This paper investigates the Drone Path Scheduling Problem (DPSP) whose goal is to assign time slots to each UAV by considering the corridors that UAVs need to traverse, and their starting time slot, in order to reach their destination such that the maximum slot for which all UAVs accomplished their mission is minimized. Time slots guarantee that each UAV accesses a corridor at a unique time, preventing multiple UAVs from using the same corridor simultaneously. We propose the Rec and the Heap-Based algorithms for unidirectional paths, demonstrating their optimality. For bidirectional paths, we offer sub-optimal solutions using Heap-Based and a 2-approximation algorithm called Bi-Alg. Furthermore, we present an Integer Linear Programming (ILP) formulation to optimally solve DPSP on unidirectional and bidirectional paths. Performance evaluations show the efficacy and scalability of our proposed algorithms compared to the ILP formulation.

We consider Internet of Things (IoT) sensors deployed inside an area to be monitored. Drones can be used to collect the data from the sensors, but they are constrained in energy and storage. Therefore, all drones need to select a subset of sensors whose data are the most relevant to be acquired, modeled by assigning a reward. We present an optimization problem called Multiple-drone Data-collection Maximization Problem (MDMP) whose objective is to plan a set of drones' missions aimed at maximizing the overall reward from the collected data, and such that each individual drone's mission energy cost and total collected data are within the energy and storage limits, respectively. We optimally solve MDMP by proposing an Integer Linear Programming based algorithm. Since MDMP is NP-hard, we devise suboptimal algorithms for single- and multiple-drone scenarios. Finally, we thoroughly evaluate our algorithms on the basis of random generated synthetic data.

Drones have become increasingly popular in a variety of fields, including agriculture, emergency response, and package delivery. However, most drone operations are currently limited to within Visual Line of Sight () due to safety concerns. Flying drones Beyond Visual Line of Sight () broadens to new challenges and opportunities, but also requires new technologies and regulatory frameworks to ensure that the drone is constantly under the control of a remote operator. In this work, we propose a novel graph-based multi-layer framework that closely resembles real-world scenarios and challenges in order to plan drone operations. Our framework includes layers of constraints such as ground risk, cellular network infrastructure, and obstacles, at different heights. From the multi-layer structure, a graph is constructed whose edges are weighted with a dependability score that takes into account the information of the layers, allowing efficient path planning of missions, using algorithms such as Dijkstra’s. Since the built graph can be really large, we also propose lighter graph-based corridors by considering only a limited portion of the original graph. Through extensive experimental evaluation on a real dataset, we demonstrate the effectiveness of our framework in solving the (), which can be efficiently solved by applying the Dijkstra’s algorithm.

The use of drones for collecting information and detecting bugs in orchards covered by nets is a challenging problem. The nets help in reducing pest damage, but they also constrain the drone’s flight path, making it longer and more complex. To address this issue, we model the orchard as an aisle-graph, a regular data structure that represents consecutive aisles where trees are arranged in straight lines. The drone flies close to the trees and takes pictures at specific positions for monitoring the presence of bugs, but its energy is limited, so it can only visit a subset of positions. To tackle this challenge, we introduce the Single-drone Orienteering Aisle-graph Problem (SOAP), a variant of the orienteering problem, where likely infested locations are prioritized by assigning them a larger profit. Additionally, the drone’s movements have a cost in terms of energy, and the objective is to plan a drone’s route in the most profitable locations under a given drone’s battery. We show that SOAP can be optimally solved in polynomial time, but for larger orchards/instances, we propose faster approximation and heuristic algorithms. Finally, we evaluate the algorithms on synthetic and real datasets to demonstrate their effectiveness and efficiency.

Cheap commercial off-the-shelf (COTS) First-Person View (FPV) drones have become widely available for consumers in recent years. Unfortunately, they also provide low-cost attack opportunities to malicious users. Thus, effective methods to detect the presence of unknown and non-cooperating drones within a restricted area are highly demanded. Approaches based on detection of drones based on emitted video stream have been proposed, but were not yet shown to work against other similar benign traffic, such as that generated by wireless security cameras. Most importantly, these approaches were not studied in the context of detecting new unprofiled drone types. In this work, we propose a novel drone detection framework, which leverages specific patterns in video traffic transmitted by drones. The patterns consist of repetitive synchronization packets (we call pivots), which we use as features for a machine learning classifier. We show that our framework can achieve up to 99% in detection accuracy over an encrypted WiFi channel using only 170 packets originated from the drone within 820ms time period. Our framework is able to identify drone transmissions even among very similar WiFi transmissions (such as video streams originated from security cameras) as well as in noisy scenarios with background traffic. Furthermore, the design of our pivot features enables the classifier to detect unprofiled drones in which the classifier has never trained on and is refined using a novel feature selection strategy that selects the features that have the discriminative power of detecting new unprofiled drones.

In this work, we investigate the impact of the wind in a drone-based delivery system. For the first time, to the best of our knowledge, we adapt the trajectory of the drone to the wind. We consider a truck-drone tandem delivery system. The drone actively reacts to the wind adopting the “most tailwind” trajectory available between the truck’s path and the delivery. The truck moves on a predefined route and carries the drone close to the delivery point. We propose the Minimum-energy Drone-trajectory Problem (MDP) which aims, when the wind affects the delivery area, at planning minimum-energy trajectories for the drone to serve the customers starting from and returning to the truck. We then propose two algorithms that optimally solve MDP under two different routes of the truck. We also analytically study the feasibility of sending drones with limited battery to deliver packages. Finally, we first numerically compare our algorithms on randomly generated synthetic and real data, and then we evaluate our model simulating the drone’s flight in the BlueSky simulator.

In this work, we investigate the use of drones in a delivery scenario formed by two contiguous areas. In one area the drones can freely fly on straight lines between any two locations (Euclidean metric), while in the other one the drones must follow the open space above the roads (Manhattan metric). We model this delivery scenario as a Euclidean-Manhattan-Grid (EM-grid). Given a set of customers to be served in an EM-grid, the objective is to find the distribution point (DP) for the drone that minimizes the overall traveled distance, considering that the drone has to do multiple round trips to/from the DP. In our view, the DP is optimized with respect to the set of customers and its computation must be light because it needs to be recomputed every time the set of customers varies. Accordingly, we define the Single Distribution Point Problem (SDPP) and devise sub-optimal time-efficient algorithms for solving it. We numerically compare the cost of our sub-optimal solutions with that of an optimal solution computed with a brute-force approach. Finally, using the BlueSky open air simulator, we compare the cost of our best solution with the cost of a solution that serves the costumers from a fixed DP, like the location of a delivery company’s depot. The fixed DP can perform very poorly for some customer instances, while our solution is highly adaptive and reduces the time and the distance covered by the drone.

In this paper, we consider the problem of using a drone to collect information within orchards in order to detect bugs. An orchard can be modeled as an aisle-graph, which is a regular data structure formed by consecutive aisles where trees are arranged in a straight line. For monitoring the presence of bugs, a drone flies close to the trees and takes videos and/or pictures that will be analyzed offline. As the drone’s energy is limited, only a subset of locations in the orchard can be visited with a fully charged battery. Those places that are most likely to be infested should be selected to promptly detect the parasite. We study the budgeted constrained position selection problem in the orchard from an algorithmic point of view. We present the Single-drone Orienteering Aisle-graph Problem (SOAP), a variant of the well-known orienteering problem where the finite resource is the drone’s battery. We first show that SOAP can be optimally solved for aisle-graphs in polynomial time. However, the optimal solution is not efficient for large orchards. Then, we propose two efficient heuristics that work even for large (orchard) instances. After a thorough analysis of the proposed solutions, we evaluate their performance by simulation experiments on both synthetic and real data sets.

We consider a delivery food service operated by Unmanned Aerial Vehicles (UAVs). Due to the absence of a dataset on UAVs deliveries in the literature, and since it is not possible to perform real tests, we create a dataset using an open Air Traffic Simulator (ATS). Precisely, we converted a set of food deliveries operated by wheeled vehicles, proposed in the literature [1], into a set of simulated UAVs deliveries. For each delivery, we ran a UAV flight from the source to the destination. The results showed that, as expected, the UAV’s course is shorter than the vehicle trajectory on the ground because the UAV follows an Euclidean path. Following that path, UAVs can be 5 to 8 times faster than wheeled vehicle, in absence of wind. Highly important, the ATS simulator allows to take care of the wind impact in a realistic way. Tailwind increases UAVs speed which becomes up to 10 times faster than the wheeled vehicles, whereas the headwind and crosswind slowdown the UAVs as the traffic slowdown the wheeled vehicles. Our work proves that air traffic simulators pave the way for realistic simulations of UAVs systems.

Localizing ground devices (GDs) is an important requirement for a wide variety of applications, such as infrastructure monitoring, precision agriculture, search and rescue operations, to name a few. To this end, unmanned aerial vehicles (UAVs) or drones offer a promising technology due to their flexibility. However, the distance measurements performed using a drone, an integral part of a localization procedure, incur several errors that affect the localization accuracy. In this paper, we provide analytical expressions for the impact of different kinds of measurement errors on the ground distance between the UAV and GDs. We review three range-based and three range-free localization algorithms, identify their source of errors, and analytically derive the error bounds resulting from aggregating multiple inaccurate measurements. We then extend the range-free algorithms for improved accuracy. We validate our theoretical analysis and compare the observed localization error of the algorithms after collecting data from a testbed using ten GDs and one drone, equipped with ultra wide band (UWB) antennas and operating in an open field. Results show that our analysis closely matches with experimental localization errors. Moreover, compared to their original counterparts, the extended range-free algorithms significantly improve the accuracy.

In this article, we study the orienteering aisle-graph single-access problem (OASP), a variant of the orienteering problem for a robot moving in a so-called single-access aisle graph, i.e., a graph consisting of a set of rows that can be accessed from one side only. Aisle graphs model, among others, vineyards or warehouses. Each aisle-graph vertex is associated with a reward that a robot obtains when it visits the vertex itself. As the energy of the robot is limited, only a subset of vertices can be visited with a fully charged battery. The objective is to maximize the total reward collected by the robot with a battery charge. We first propose an optimal algorithm that solves the OASP in O (m 2n 2) time for aisle graphs with a single access consisting of m rows, each with n vertices. With the goal of designing faster solutions, we propose four greedy suboptimal algorithms that run in at most O(mn\(m + n)) time. For two of them, we guarantee an approximation ratio of 1 2(1-1 e), where e is the base of the natural logarithm, on the total reward by exploiting the well-known submodularity property. Experimentally, we show that these algorithms collect more than 80% of the optimal reward.

The impact on the energy consumption of flying drones in favorable winds is investigated in this paper. A tandem system is considered, with only one drone and one truck. The truck moves on a predefined route and brings the drone close to the delivery point. Then, the drone plans its service route by choosing the take-off and landing points from which the delivery will be performed. We propose a constant time algorithm OSR to plan the drone route with minimum-energy service when the truck moves on a line in front of the deliveries (i.e., highway). Then, we devise the algorithm MS-OSR to plan a drone minimum-energy service route when the truck moves on a multiline that bounds a convex area where the deliveries take place. We found that OSR and MS-OSR plan drone service routes that save at least 30% and 60%, respectively, of the energy consumed by connecting the delivery and the truck following the shortest route, that is, following the perpendicular segment between the delivery point and the truck’s route.

The use of drones can be a valuable solution for the problem of delivering goods for many reasons. In fact, they can be efficiently employed in time-critical situations when there is a traffic jam on the roads, to serve customers in hard-to-reach places, or simply to expand the business. However, due to limited battery capacities and the fact that drones can serve a single customer at a time, a drone-based delivery system (DBDS) aims to minimize the drones’ energy usage for completing a route from the depot to the customer and go back to the depot for new deliveries. In general, the shortest delivery route could not be the optimal choice since external factors like the wind (which varies with time) can affect energy consumption. Previous work has mainly considered simplified DBDSs assuming architectures with a single drone and with static costs on paths. Moreover, in these non-centralized architectures, the drones themselves compute the routes on the fly employing their onboard processing resources, making this choice costly. In this paper we develop a centralized system for computing energy-efficient time-varying routes for drones in a multi-depot multi-drone delivery system. Specifically, we propose a novel centralized parallel algorithm called Parallel Shortest Route Update (PSRU) that, over time, updates the drones’ delivery routes avoiding the whole recomputation from scratch. A comprehensive evaluation proves that PSRU is up to 4. 5x faster than the state-of-the-art algorithms.

In this paper, we study the feasibility of sending drones to deliver goods from a depot to a customer by solving what we call the Mission-Feasibility Problem (MFP). Due to payload constraints, the drone can serve only one customer at a time. To this end, we propose a novel framework based on time-dependent cost graphs to properly model the MFP and tackle the delivery dynamics. When the drone moves in the delivery area, the global wind may change thereby affecting the drone's energy consumption, which in turn can increase or decrease. This issue is addressed by designing three algorithms, namely: (i) compute the route of minimum energy once, at the beginning of the mission, (ii) dynamically reconsider the most convenient trip towards the destination, and (iii) dynamically select only the best local choice. We evaluate the performance of our algorithms on both synthetic and real-world data. The changes in the drone's energy consumption are reflected by changes in the cost of the edges of the graphs. The algorithms receive the new costs every time the drone flies over a new vertex, and they have no full knowledge in advance of the weights. We compare them in terms of the percentage of missions that are completed with success (the drone delivers the goods and comes back to the depot), with delivered (the drone delivers the goods but cannot come back to the depot), and with failure (the drone neither delivers the goods nor comes back to the depot).

In this paper, we study the Orienteering Aislegraphs Single-column Problem (OASP), which is a variant of the route planning problem for an entity/robot moving along a specific aisle-graph consisting of a set of rows connected via just one column at one endpoint of the rows. Such constrained aislegraph may model, for instance, a vineyard or warehouse, where each vertex is assigned with a reward that a robot gains when visiting it for accomplishing a task. As the robot is energy limited, it must visit a subset of vertices before going back to the depot for recharging, while maximizing the total reward gained. It is known that the OASP for constrained aisle-graphs composed by m rows of length n is polynomially solvable in O(m2n2) time, which can be prohibitive for graphs of large dimensions. With the goal of designing more time efficient solutions, we propose four algorithms that iteratively build the solution in a greedy manner. These solutions take at most O(mn (m + n)) time, thus improving the optimal solution by a factor of n. Experimentally, we show that these algorithms collect more than 80% of the optimum reward. For two of them, we also guarantee an approximation ratio of 1/2(1 - 1/e)on the reward function by exploiting the submodularity property, where e is the base of the natural logarithm.

In this paper, we consider the Constant-cost Orienteering Problem (COP) where a robot, constrained by a limited travel budget, aims at selecting a path with the largest reward in an aisle-graph. The aisle-graph consists of a set of loosely connected rows where the robot can change lane only at either end, but not in the middle. Even when considering this special type of graphs, the orienteering problem is known to be intractable. We optimally solve in polynomial time two special cases, COP-FR where the robot can only traverse full rows, and COP-SC where the robot can access the rows only from one side. To solve the general COP, we then apply our special case algorithms as well as a new heuristic that suitably combines them. Despite its light computational complexity and being confined into a very limited class of paths, the optimal solutions for COP-FR turn out to be competitive in terms of achieved rewards even for COP. This is shown by means of extended simulations performed on both real and synthetic scenarios. Furthermore, our new heuristic for the general case outperforms state-of-art algorithms, especially for input with highly unbalanced rewards.

We study the possibility of using drones to implement an automated picking system in a warehouse. We imagine a warehouse divided into two contiguous areas: in one area, the drone moves according to the Euclidean distance, while in the other area, the drone moves according to the Manhattan distance. For each customer-order (CO), the automated picking system is in charge of gathering the items requested in the CO to a predefined location where the cart of the drone is positioned. For each item of the order, the drone flies to the location where the item is stored, grasps it, and brings it back to its cart. Our goal is to find the position of the drone's cart that minimizes the sum of the distances traversed by the drone to pick-up all the items of the CO. We propose algorithms to find such a location when the items to be collected are in Euclidean and Manhattan areas. We can prove a √2-approximation factor for our solutions. Moreover, we compare the efficiency of the automated picking system employing a drone with that of a traditional picking system employing a worker that pushes a cart, and we find under which conditions the drone can be more efficient.

We introduce a drone delivery system for the "last-mile" logistics of small parcels. The system serves mixed delivery areas modeled as EMs. The shortest path between two destinations of an EM concatenates the Euclidean-and Manhattan-distance metrics. The drone's mission consists in one delivery for each destination of the grid, and, due to the strict payload constraint, the drone returns to the warehouse after each delivery. Our goal is to set the drone's warehouse in the delivery area so as the sum of the distances between the locations to be served and the warehouse is minimized. We exactly solve the problem proposing an algorithm that takes logarithmic time in the length of the Euclidean side of the EM. We also devise two approximate solutions that select the warehouse among a constant number of vertices of the EM. Such solutions are almost as good as the exact solution and we prove a √2-approximation bound in the worst case. Finally, we propose an exact solution for the two warehouse problem in a Manhattan grid, and an approximate solution for EMs.

In this work, we evaluate the accuracy of the Drone Range-Free (DRF) localization algorithm presented in the literature on a simple test-bed built using the Decawave Ultra Wide Band (UWB) Sensors Kit MDEK1001 and a customary drone. DRF localizes an IoT device at the intersection of the perpendicular bisectors of two chords of its receiving disk. Despite its simplicity and elegance, DRF poses great challenges in a real implementation on the field because the device's receiving disk is in reality far from a perfect circle. We solve this problem by relaxing the range-free assumption and by discovering almost perfect inner-circles in the IoT-device receiving disk using the ability of the MDEK1001 sensors of taking distance measurements. With a set of simplified experiments that aim to localize a single antenna, we show that, using the inner-circle method, we significantly improve on the localization accuracy without loosing the DRF simplicity and elegance. The accuracy of the new inner-circle method, along with that of a simplified range-based multilateration method, is also proved by localizing three antennas posed at the vertices of a pre-determined triangle.

Unmanned Aerial Vehicles (UAVs) have enormous potentials for several important applications, such as search and rescue and structural health monitoring. An important requirement for these applications is the ability to accurately localize objects, such as sensors or ``smart-things'', equipped with wireless communication capability. However, most previous works in this area neglect the unavoidable errors that are involved in the localization process, thus resulting in poor performance in practice. In this paper, for the first time, we express the measurement error on the ground as a function of the rolling, altitude, and instrumental precision provided by the hardware on the drone. We takeaway two lessons from this analysis: to limit the ground error (i) all the waypoints used to measure the same node must be at a sufficiently large ground distance from the node itself, and (ii) they must not be collinear among themselves nor with the node. We validate the error expressions derived analytically through real experiments using the 3DR Solo Drone.

The localization of devices is a key ingredient of Internet of Things (IoT). However, localization requires deploying many anchor nodes that are nodes whose location is known a-priori. Anchor nodes are expensive and their utilization may be unfeasible in some cases, such as in search-and-rescue operations. In this work, we propose a range-free localization algorithm that replaces the anchor nodes with an off-the-shelf drone. During the mission, the drone scans the deployment area and regularly broadcasts a beacon consisting of the current drone's position projected on the ground. The sensors simply listen to the drone until they hear three special beacons and, after that, they locally compute their position. Our algorithm is able to ensure any user-defined localization precision just varying the distance betweenthe beacons. Differently from the other range-based localization algorithms proposed for drones, our algorithm guarantees the localization precision without requiring any specific hardware technology, except the ability to communicate. Since our algorithm does not take any measure, the height of the drone only affect the receiving area of the sensor. Due to the simplicity of the interaction between the drone and the sensors during the algorithm, this solution can localize very high dense networks, even using a slightly shorter drone's trajectory than the previous algorithms.

Many dependable systems rely on the integrity of the position of their components. In such systems, two key problems are secure localization and secure location verification of the components. Researchers proposed several solutions, which generally require expensive infrastructures of several fixed stations (anchors) with trusted positions. In this paper, we explore the approach of replacing all the fixed anchors with a single drone that flies through a sequence of waypoints. At each waypoint, the drone acts as an anchor and securely determines the positions. This approach completely eliminates the need for many expensive anchors. The main challenge becomes how to find a convenient path for the drone to do this for all the devices. The problem presents novel aspects, which make existing path planning algorithms unsuitable. We propose LocalizerBee, VerifierBee, and PreciseVerifierBee: three path planning algorithms that allow a drone to respectively measure, verify, and verify with a guaranteed precision a set of positions in a secure manner. They are able to securely localize all the positions in a generic deployment area, even in the presence of drone control errors. Moreover, they produce short path lengths and they run in a reasonable processing time.

We consider the problem of allocating N uniform data to K transmission channels so as the average Expected Delay (AED) is minimized. This problem arises in designing efficient data-diffusion broadcast algorithms in a smart environment. We show that the basic dynamic rogramming algorithm for solving the uniform pallocation problem can be speedup up to O(NK) time by applying an optimal algorithm to find the row-minima of totally monotone matrices. Such a new algorithm is always faster than the best previously known algorithm for the uniform allocation problem that runs in O(NKlogN). Moreover, it is computationally optimal for the uniform allocation of up to N data and K channels. We then reduce the largest allocation problem, i.e., the subproblem with exactly N data and K channels, to the problem of finding a minimum weight K-link path in a particular directed acyclic graph. We also present two heuristics and we show by extended simulations their effectiveness in practical scenarios. Both the K-link path algorithm and the heuristics are much faster than O(NK). We then compare the behaviours of our algorithms on the online version of the allocation problem in which new single items are inserted for broadcast.

In a sensor network, data might be stored in so-called storage nodes, which receive raw data from other nodes, compress them, and send them toward a sink. We consider the problem of locating k storage nodes in order to minimize the energy consumed for converging the raw data to the storage nodes as well as to converge the compressed data to the sink. This is known as the minimum k-storage problem. In general, the problem is NP-hard. However, we are able to devise a polynomial-time algorithm that optimally solves the problem in bounded-tree width graphs. We then characterize the minimum k-storage problem from the approximation viewpoint. We first prove that it is NP-hard to be approximated within a factor smaller than 1 + 1/e. We then propose a local search algorithm that guarantees a constant approximation factor. We conducted extended experiments to show that the algorithm performs very well, exhibiting very small deviation from the optimum and computational time. It is worth to note that our problem is a generalization to the well-known metric k-median problem and then the obtained results also hold for this case.

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.

We investigate the condition on transmission radius needed to achieve connectivity in duty-cycled wireless sensor networks (briefly, DC-WSNs). First, we settle a conjecture of Das et al. [2012] and prove that the connectivity condition on random geometric graphs (RGGs), given by Gupta and Kumar [1989], can be used to derive a weakly sufficient condition to achieve connectivity in DC-WSNs. To find a stronger result, we define a new vertex-based random connection model that is of independent interest. Following a proof technique of Penrose [1991], we prove that when the density of the nodes approaches infinity, then a finite component of size greater than 1 exists with probability 0 in this model. We use this result to obtain an optimal condition on node transmission radius that is both necessary and sufficient to achieve connectivity and is hence optimal . The optimality of such a radius is also tested via simulation for two specific duty-cycle schemes, called the contiguous and the random selection duty-cycle schemes. Finally, we design a minimum-radius duty-cycling scheme that achieves connectivity with a transmission radius arbitrarily close to the one required in random geometric graphs. The overhead in this case is that we have to spend some time computing the schedule.

Recent energy measurements on smartphones have shown that parallel communications (e.g., data transfer and voice call) require less energy than their stand-alone execution. Guided by these results, we investigate the possibility of scheduling communications in pairs for minimizing the energy consumption. We define two energy optimization problems to postpone delay-tolerant services and perform them in parallel with real-time services in order to save energy. The first problem, called single delay-tolerant assignment (SDA), allows at most one delay-tolerant service to be paired with each real-time service, whereas the second problem, called multiple delay-tolerant assignment (MDA), allows multiple delay-tolerant services to be paired (in different times) with the same real-time service. For the SDA problem, we propose an optimal algorithm. For the MDA problem, which is computationally intractable, we give an approximation algorithm. We evaluate the benefits of the energy-efficient pairing strategy via simulations on synthetic traces. The MDA algorithm can save up to the 60 percent of the energy consumption using 4G network assuming an intensive smartphone usage, while the SDA algorithm saves up to the 20 percent.

We investigate the condition on transmission radius needed to achieve connectivity in duty-cycled wireless sensor networks (briefly, DC-WSN). First, we settle a conjecture of Das et. al. (2012) and prove that the connectivity condition on Random Geometric Graphs (RGG), given by Gupta and Kumar (1989), can be used to derive a weak sufficient condition to achieve connectivity in DC-WSN. We also present a stronger result which gives a necessary and sufficient condition for connectivity and is hence optimal. The optimality of such a radius is also tested via simulation for two specific duty-cycle schemes, called the contiguous and the random selection duty-cycle scheme.

Convergecast is a typical form of data collection in wireless sensor networks (WSNs), wherein nodes sample data from the environment and send them to a common destination. In order to prolong the network lifetime, a duty-cycle mechanism is usually coupled with a routing tree structure, in which nodes are organized in clusters. Each cluster aggregates data and sends them towards the root of the tree. However, clusters can interfere each other if their active time is not properly chosen. Furthermore, scheduling can lead to a long data delivery delay when a duty-cycle mechanism is used. In this article, we introduce a receiver-oriented scheduling algorithm for cluster-tree WSNs which provides a bounded latency for convergecast data collection. In contrast with most of the existing works in the literature, where two nodes are assumed to interfere if they are at most 2 hops away, we address the more general and realistic case where interfering nodes can be up to t hops away from each other, where te2. We first show that the minimum-latency convergecast problem is NP-hard for cluster-based WSNs with arbitrary topologies. We then focus on tree-based WSNs and derive bounds on the latency for convergecast data collection. We also propose a heuristic to obtain a t-interference-free scheduling in O(nt) time, where n is the number of clusters in the WSN. We finally validate our findings by simulation on both synthetic topologies and routing trees obtained from WSN deployments.

Abstract We propose novel localization and routing protocols in an actor‐centric wireless sensor network consisting of an actor node and a large number of energy‐constrained sensors operating under L different periodic sleep–awake schedules. Specifically, we propose a semidistributed localization algorithm in which a small subset of sensors extracts their positions in polar coordinates based on the messages received from the actor, and subsequently localizes (also in polar coordinates) the remaining sensors. By modeling the deployed sensors as a two‐dimensional Poisson point process and applying well‐known results from the coupon collector's problem and Chernoff bounds, we analytically derive and also validate, by simulation, the sensor density required to localize all sensors in the network with high probability. The actor‐centric network can be modeled by a cluster adjacency graph G with the help of the already localized polar coordinates that logically partition the network into concentric coronas (around the actor), each subdivided in a varying number of clusters (of almost the same area). To avoid intercluster collisions in G, sensors in different clusters transmit on different channels. A lower bound on the number of channels required to schedule the transmissions without collisions is obtained by solving a distance‐2 vertex coloring problem on G. Optimal and quasioptimal fully distributed algorithms are provided to determine the channel assigned to each cluster in constant time. Finally, we apply these results to develop a geographic routing protocol: the messages generated from the sensors in a given cluster are routed toward the actor through the unique shortest path of G that starts from the node associated with the cluster and goes up to the corona where the actor resides. In each cluster, to avoid redundant retransmissions toward the actor, we select L leaders, one for each periodic sleep–awake schedule. © Wiley Periodicals, Inc. NETWORKS, Vol. 2012.

In the context of scheduling and timetabling, we study a challenging combinatorial problem which is very interesting for both practical and theoretical points of view. The motivation behind it is to cope with scheduled activities which might be subject to unavoidable disruptions, such as delays, occurring during the operational phase. The idea is to preventively plan some extra time for the scheduled activities in order to be "prepared” if a delay occurs, and absorb it without the necessity of rescheduling all the activities from scratch. This realizes the concept of designing robust timetables. During the planning phase, one should also consider recovery features that might be applied at runtime if disruptions occur. This leads to the concept of recoverable robust timetables. In this new concept, it is assumed that recovery capabilities are given as input along with the possible disruptions that must be considered. The main objective is the minimization of the overall needed time. The quality of a robust timetable is measured by the price of robustness, i.e., the ratio between the cost of the robust timetable and that of a nonrobust optimal timetable. We show that finding an optimal solution for this problem is NP-hard even though the topology of the network, which models dependencies among activities, is restricted to trees. However, we manage to design a paeudopolynomial time algorithm based on dynamic programming and apply it on both random networks and real case scenarios provided by Italian railways. We evaluate the effect of robustness on the scheduling of the activities and provide the price of robustness with respect to different scenarios. We experimentally show the practical effectiveness and efficiency of the proposed algorithm.

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.

Exploiting high density features of wireless sensor networks represents a challenging issue. In this context, anonymous, asynchronous and randomly distributed sensors are considered along with few devices, called actors, which are more powerful than sensors in terms of energy and transmission capabilities. The paper proposes a new distributed training protocol for coarse-grain localization purposes in high density environments. The aim is to auto-organize the sensors with respect to a virtual infrastructure centered at actors and constituted of concentric rings divided into sectors. Analytical study as well as experiments on the proposed protocol are provided. The obtained results show under which theoretical and practical settings the training process can be performed in a fast and high quality way with respect to the granularity of the required localization and the 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

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

In this paper we have developed a new service classification strategy in hybrid scheduling scheme to support differentiated quality of service (QoS) among the different set of clients. The scheme dynamically computes the data access probabilities and amalgamates the push and pull scheduling schemes to develop the hybrid scheduling framework. While a flat scheduling is used for push system, the major novelty of the work lies in differentiating the clients based on their priority-classes and incorporating the effect of priority in selecting an item from the pull-system. Modeling and analysis of the system is performed to get an average behavior of the QoS parameters like delay in our hybrid scheduling framework. Simulation results points out that the average waiting time for the highest priority clients can be kept very low, while simultaneously minimizing the number of requests dropped by assigning appropriate fraction of available bandwidth. It also demonstrates that by intelligent selection of the cut-off point, used to segregate push and pull systems, the overall cost associated with the system can be minimized.

Broadcast is an efficient and scalable technique for disseminating data over wireless channels to an arbitrary large number of clients. The prime objective of broadcast schedules, both on-line and off-line, is to minimize the average amount of time a client needs to wait before receiving its desired item. In off-line schedules, it is assumed that both the entire set of data items and the demand probability for each data is known in advance. Such schedules are guaranteed to obtain the minimum average waiting time only when a skewed partition of the data among multiple-channels and flat schedules per channel are assumed. On the contrary, the on-line broadcast schedules decide which item to transmit without any a-priori knowledge of either the entire set of data or the data demand probabilities. Although no optimal solutions are known for the latter schedules, the volatility of the set of data items to be transmitted makes on-line schedules much more desirable than its off-line counterparts. In this paper, a new on-line broadcast schedule for broadcast over multiple channels is presented. The strategy partitions the data among the broadcast channels in a balanced way, and adopts a hybrid push-pull broadcast schedule per channel. Simulation experiments point out that the results of our new algorithm outperforms the minimum average waiting time achieved by the optimal off-line schedule (skewed partition of data among channels and flat schedule for channel), and the on-line broadcast schedule based on the square root rule.

The ever-increasing popularity of Web services, growing demand for wireless multimedia and introduction of new, feature-enhanced, hand-held devices has already given birth to a new set of data-centric applications. Providing such applications with enhanced data processing capability calls for an efficient scheduling and transmission technique. The goal of most scheduling strategy lies in reducing the average waiting time. However, in most practical systems the variation of waiting time often results in client's impatience, thus provoking the clients to send repeated requests for the particular data item(s). In this paper we have developed a new hybrid scheduling framework for heterogeneous, asymmetric environments, by exploring the advantages of broadcasting very popular (push) data and dissemination of less popular (pull) data. The data access probabilities and the cut-off point used to segregate push and pull sets are dynamically computed. Packet fair scheduling (PFS) and stretch-optimal scheduling principle is deployed to obtain the push and pull schedule respectively. The framework explicitly takes care of the repeated requests originating from the impatient clients and minimizes the overall expected access time by obtaining an optimal cut-off point. Extensive performance analysis and simulation experiments are performed to show the efficiency of the system in reducing the overall expected access time (delay).

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.

In This work we present a hybrid push-pull algorithm which combines broadcasting of push data items, with dissemination upon request of pull items in asymmetric communication environments. These environments are made up only of one database server and many clients. Requests made by the clients are queued up for the pull items. The (pull) item with the number of pending requests is the one selected to be pulled. We present performance analysis of our scheme, and determine individual response time for each item disseminated and the overall time for the pull queue to be flushed. Next, we extend our algorithm by incorporating QoS factors, and, then, study its performance analytically.

In this paper we address the pure parsimony haplotyping problem: Find a minimum number of haplotypes that explains a given set of genotypes. We prove that the problem is APX-hard and present a 2k− 1-approximation algorithm for the case in which each genotype has at most k ambiguous positions. We further give a new integer-programming formulation that has (for the first time) a polynomial number variables and constraints. Finally, we give approximation algorithms, not based on linear programming, whose running times are almost linear in the input size.

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.

In this paper, we study efficient strategies for mapping onto parallel memory systems complete trees that are accessed by fixed templates (like complete subtrees, paths, or any combinations their of). These mappings are evaluated with respect to the following criteria: (1) the largest number of data items that can be accessed in parallel without memory conflicts; (2) the number of memory conflicts that can occur when accessing templates of size equal to the number of available memory modules, thereby exploiting the full parallelism of the system; (3) the complexity of the memory addressing scheme, i.e., the cost of retrieving the module where a given data item is mapped. We show that there exist trade-offs between these three criteria and the performance of different mapping strategies depends on the emphasis given on each of these criteria. More specifically, we describe an algorithm for mapping complete binary trees of height H onto M memory modules and prove that it achieves the following performance results: (1) conflict-free access to complete subtrees of size K and paths of size N such that N + K - [log K] /spl les/ M; (2) at most 1 conflict in accessing complete subtrees and paths of size M; (3) O(K/M + c) conflicts when accessing a composite template of K nodes consisting of c disjoint subsets, each subset being a complete subtree, or a path or a set of consecutive nodes in a level of the tree.

A multidimensional file is one whose data are characterized by several attributes, each specified in a given domain. A partial match query on a multidimensional file extracts all data whose attributes match the values of one or more attributes specified in the query. The disk allocation problem of a multidimensional file F on a database system with multiple disks accessible in parallel is the problem of distributing F among the disks such that the data qualifying for each partial match query are distributed as evenly as possible among the disks of the system. We propose an optimal solution to this problem for multidimensional files with pairwise prime domains based on a large and flexible class of maximum distance separable codes, namely, the redundant residue codes. We also introduce a new family of residue codes, called the redundant nonpairwise prime residue codes, to deal with files whose attribute domains are nonpairwise prime.

In this paper we study strategies for mapping complete tree data structures, that are accessed by fixed templates, onto parallel memory systems. These mappings are evaluated with respect to the following three different criteria: (i) the number of memory conflicts that can occur in a parallel access to the data structure; (ii) the largest number of elements that can be accessed in parallel without memory conflicts; (iii) the complexity of the memory addressing scheme. We show that there exist trade-offs between these criteria. We describe an algorithm COLOR for mapping complete trees onto EA memory modules and prove that it achieves the following performance: (i) conflict-free access to complete subtrees of size K and paths of size N, for M/spl ges/N+K-[log K]; (ii) at most 1 conflict when accessing complete subtrees and paths of size M; (iii) O((K/M)+c) conflicts when accessing a composite template of K nodes consisting of c disjoint subsets, each being a complete subtree, a path or a set of consecutive nodes in a level of the tree.

It is believed that broadcast is an efficient way to transmit data in an asymmetric communication system. Most of the previous work focused on either pull-based or push-based scheduling. However, for systems with a very large number of data items, none of these schemes is efficient. We propose a novel scheduling algorithm which uses both pull- and push-based schemes. In our approach, data items are divided into two disjoint sets: one consisting of more-popular items and the other of less-popular items. The items in the former set are broadcast by a push-based schedule, while those in the latter set by a pull-based schedule. By optimally selecting the cut-off point to distinguish these two sets, the new hybrid scheduling algorithm achieves a lower expected access time than other existing schedules.

We present a hardware-algorithm for sorting N elements using either a p-sorter or a sorting network of fixed I/O size p while strictly enforcing conflict-free memory accesses. To the best of our knowledge, this is the first realistic design that achieves optimal time performance, running in /spl Theta/(NlogN/plogp) time for all ranges of N. Our result completely resolves the problem of designing an implementable, time-optimal algorithm for sorting N elements using a p-sorter. More importantly, however, our result shows that, in order to achieve optimal time performance, all that is needed is a sorting network of depth O(log/sup 2/p) such as, for example, Batcher's classic bitonic sorting network.

We address the problem of designing efficient and scalable hardware-algorithms for computing the sum and prefix sums of a w/sup k/-bit, (k/spl ges/2), sequence using as basic building blocks linear arrays of at most w/sup 2/ shift switches, where w is a small power of 2. An immediate consequence of this feature is that in our designs broadcasts are limited to buses of length at most w/sup 2/. We adopt a VLSI delay model where the "length" of a bus is proportional with the number of devices on the bus. We begin by discussing a hardware-algorithm that computes the sum of a w/sup k/-bit binary sequence in the time of 2k-2 broadcasts, while the corresponding prefix sums can be computed in the time of 3k-4 broadcasts. Quite remarkably, in spite of the fact that our hardware-algorithm uses only linear arrays of size at most w/sup 2/, the total number of broadcasts involved is less than three times the number required by an "ideal" design. We then go on to propose a second hardware-algorithm, operating in pipelined fashion, that computes the sum of a kw/sup 2/-bit binary sequence in the time of 3k+[log/sub w/ k]=3 broadcasts. Using this design, the corresponding prefix sums can be computed in the time of 4k+[log/sub w/ k]-5 broadcasts.

The disk allocation problem addresses the issue of how to distribute large files among several disks so as to maximize the concurrent disk accesses in response to partial match queries. In the past, this problem has been studied for binary as well as for p-ary cartesian product files. We propose a strictly-optimal disk allocation strategy for non-uniform cartesian product files for every partial match query. Our strategy is based on a large and flexible class of maximum distance separable (MDS) codes, namely the redundant residue codes. A new family of residue codes, called the redundant non-pairwise prime residue codes, is also introduced.

Sorting networks of fixed I/O size p have been used, thus far, for sorting a set of p elements. Somewhat surprisingly, the important problem of using such a sorting network for sorting arbitrarily large datasets has not been addressed in the literature. Our main contribution is to propose a simple sorting architecture whose main feature is the pipelined use of a sorting network of fixed I/O size p to sort an arbitrarily large data set of N elements. A noteworthy feature of our design is that no extra data memory space is required, other than what is used for storing the input. As it turns out, our architecture is feasible for VLSI implementation and its time performance is virtually independent of the cost and depth of the underlying sorting network. Specifically, we show that by using our design N elements can be sorted in /spl Theta/(N/p log N/p) time without memory access conflicts. Finally, we show how to use an AT/sup 2/-optimal sorting network of fixed I/O size p to construct a similar architecture that sorts N elements in /spl Theta/(N/p log N/p log p) time.

Article Free Access Share on Conflict-free template access in k-ary and binomial trees Authors: M. Cristina Pinotti IEI, Consiglio Nazionale delle Ricerche, Via S. Maria, 46, 56126 Pisa, Italy IEI, Consiglio Nazionale delle Ricerche, Via S. Maria, 46, 56126 Pisa, ItalyView Profile , Sajal K. Das Department of Computer Sciences, University of North Texas, Denton, TX Department of Computer Sciences, University of North Texas, Denton, TXView Profile , Falguni Sarkar Department of Computer Sciences, University of North Texas, Denton, TX Department of Computer Sciences, University of North Texas, Denton, TXView Profile Authors Info & Claims ICS '97: Proceedings of the 11th international conference on SupercomputingJuly 1997 Pages 237–244https://doi.org/10.1145/263580.263641Published:11 July 1997Publication History 4citation269DownloadsMetricsTotal Citations4Total Downloads269Last 12 Months3Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We efficiently map a priority queue on the hypercube architecture in a load balanced manner, with no additional communication overhead. Two implementations for insert and deletemin operations are proposed on the single-port hypercube model. In a b-bandwidth, n-item priority queue in which every node contains b items in sorted order, the first implementation achieves optimal speed-up of O[min{log n, b(log n)/(log b+log log n)}] for inserting b pre-sorted items or deleting b smallest items, where b=O(n/sup 1/c/) with c>1. In particular, single insertion and deletion operations are cost-optimal and require O(log n/p+log p) time using O(log n/log log n) processors. The second implementation is more scalable since it uses a larger number of processors, and attains a 'nearly' optimal speed-up on the single-port hypercube. The insertion of log n pre-sorted items or the deletion of log n smallest items requires O(log log n)/sup 2/ time and O(log/sup 2/ n/log log n) processors. However, on the slightly more powerful pipelined hypercube model, we are able to reduce the time complexity to O(log log n) thus attaining optimal speed-up. To the best of our knowledge, our algorithms provide the first implementations of b-bandwidth distributed priority queues, which are load balanced and yet guarantee optimal speed-up.

We efficiently map a priority queue on the hypercube architecture in a load balanced manner, with no additional communication overhead, and present optimal parallel algorithms for performing insert and deletemin operations. Two implementations for such operations are proposed on the single port hypercube model. In a b-bandwidth, n-item priority queue in which every node contains b items in sorted order, the first implementation achieves optimal speed up of O(min{log n, b log n/log b+log log n}) for inserting b presorted items or deleting b smallest items, where b=O(n/sup 1/c/) with c>1. In particular, single insertion and deletion operations are cost optimal and require O(log n/p+log p) time using O(log n/log log n) processors. The second implementation is more scalable since it uses a larger number of processors, and attains a "nearly" optimal speedup on the single hypercube. Namely, the insertion of log n presorted items or the deletion of the log n smallest items is accomplished in O(log log n/sup 2/) time using O(log/sup 2/ n/log log n) processors. Finally, on the slightly more powerful pipelined hypercube model, the second implementation performs log n operations in O(log log n) time using O(log/sup 2/ n/log log n) processors, thus achieving an optimal speed up. To the best of our knowledge, our algorithms are the first implementations of b-bandwidth distributed priority queues, which are load balanced and yet guarantee optimal speed ups.

A new method is proposed for converting residue integers into a mixed radix notation. The method is based upon a modified formulation of the Chinese Remainder Theorem, and permits both conventional logic and look-up table implementations. Moreover, it represents the first method enabling optimal, residue-to-weighted system, asymptotic conversion time. To prove this, a constructive VLSI design has been devised, exhibiting time O(log s), where s is the total number of input bits. If compared with the existing mixed radix converting techniques, the method proposed considerably enhances the conversion time. To conclude, it is shown that, at the present state of the technology, practical ECL IC's implementation achieve 35–40 ns conversion times with RAMs and 60–70 ns with logic circuitry for dynamic ranges up to 300 bits.

Hybrid number systems (HNSs) represent a natural generalisation of weighted and residue number systems. In HNSs, an integer is represented by using both weighted and residue notations; their mathematical properties, which have been investigated in depth, are strongly dependent on the ratio of the residue to the weighted range of the representation. It is apparent that varying the residue-to-weighted-range ratio should enable us to optimise the mathematical performances of these systems. This paper shows that adding flexibility to hybrid systems is very simple. A general procedure is proposed whose complexity is the same as the well-known mixed radix converting algorithm. A VLSI architecture is presented and its area-time performances are evaluated.