Search

The authors consider the problem of scheduling automated traffic in a city. Such automatic scheduling can improve efficiency of the system by decreasing delays, increasing capacity, and easing congestion. The algorithms described in this paper can be thought of as which belongs to a layer in the corresponding control--communication--computational system, which is responsible for generating timed trajectories for individual vehicles [S. Graham, G. Baliga, and P. Kumar, 'Issues in the convergence of control with communication and computing: Proliferation, architecture, design, services, and middleware,' in Proceedings of CDC '04, Nassau, Bahamas, December 2004]. Each vehicle has a specified route from its origin to its destination, and the task of the scheduler is to provide timed trajectories for all vehicles, which follow the respective vehicles' routes and further ensure that no collisions or deadlock will result. The authors' approach reduces the problem to a discrete-time graph-scheduling problem, by defining an appropriate graph to model the road network. Their main result is a sufficient condition on the graph of the road network and on the initial distribution of vehicles, under which there exists a scheduling algorithm that is guaranteed to clear the system in finite time. The nature of this result allows the design of provably correct scheduling algorithms that require only a small portion of future routes of all vehicles to be known, and are consequently able to work in real time. The authors also address the optimization of performance with respect to delay, by focusing on the 'one-step move' problem. Finding an optimal solution for the one-step problem would provide a greedy solution of the original network-wide scheduling problem, but is itself NP-hard. They present a polynomial time heuristic algorithm and evaluate its performance through simulations. Index Terms--Deadlocks, graph scheduling, smart vehicles, traffic networks, traffic scheduling.

Sensor networks are not just data networks with sensors being the sources of data. Rather, they are often developed and deployed for a specific application, and the entire network operation is accordingly geared toward satisfying this application. For overall system efficiency, it may be necessary for nodes to perform computations on data, as opposed to simply originating or forwarding data. Thus, the entire network can be viewed as performing an application-specific distributed computation. The topic of this article is to survey some lines of research that may be useful in developing a theory of in-network computation, which aims to elucidate how a wireless sensor network should efficiently perform such distributed computation. We review several existing approaches to computation problems in network settings, with a particular emphasis on the communication aspect of computation. We begin by studying the basic two-party communication complexity model and how to optimally compute functions of distributed inputs in this setting. We proceed to larger multihop networks, and study how block computation and function structure can be exploited to provide greater computational throughput. We then consider distributed computation problems in networks subject to noise. Finally, we review some randomized gossip-based approaches to computing aggregate functions in networks. These are diverse approaches spanning many different research communities, but together may find a role in the development of a more substantial theoretical foundation for sensor networks. [ABSTRACT FROM AUTHOR]

In wireless sensor networks, one is not interested in downloading all the data from all the sensors. Rather, one is only interested in collecting from a sink node a relevant function of the sensor measurements. This paper studies the maximum rate at which functions of sensor measurements can be computed and communicated to the sink node. It focuses on symmetric functions, where only the data from a sensor is important, not its identity. The results include the following. 1) The maximum rate of downloading the frequency histogram in a random planar multihop network with n nodes is O(1/log n) 2) A subclass of functions, called type-sensitive functions, is maximally difficult to compute. In a collocated network, they can be computed at rate O(1/n), and in a random planar multihop network at rate O(1/log n). This class includes the mean, mode, median, etc. 3) Another subclass of functions, called type-threshold functions, is exponentially easier to compute. In a collocated network they can be computed at rate O(1/log n), and in a random planar multihop network at rate O(1/log log n). This class includes the max, min, range, etc. The results also show the architecture for processing information across sensor networks. [ABSTRACT FROM AUTHOR]