A set of identical, mobile agents is deployed in a weighted network. Each agent has a battery--a power source allowing it to move along network edges. An agent uses its battery proportionally to the distance traveled. We consider two tasks: convergecast, in which at the beginning, each agent has some initial piece of information, and information of all agents has to be collected by some agent; and broadcast in which information of one specified agent has to be made available to all other agents. In both tasks, the agents exchange the currently possessed information when they meet. The objective of this paper is to investigate what is the minimal value of power, initially available to all agents, so that convergecast or broadcast can be achieved. We study this question in the centralized and the distributed settings. In the centralized setting, there is a central monitor that schedules the moves of all agents. In the distributed setting every agent has to perform an algorithm being unaware of the network. In the centralized setting, we give a linear-time algorithm to compute the optimal battery power and the strategy using it, both for convergecast and for broadcast, when agents are on the line. We also show that finding the optimal battery power for convergecast or for broadcast is NP-hard for the class of trees. On the other hand, we give a polynomial algorithm that finds a 2-approximation for convergecast and a 4-approximation for broadcast, for arbitrary graphs.In the distributed setting, we give a 2-competitive algorithm for convergecast in trees and a 4-competitive algorithm for broadcast in trees. The competitive ratio of 2 is proved to be the best for the problem of convergecast, even if we only consider line networks. Indeed, we show that there is no ( @math 2-∈)-competitive algorithm for convergecast or for broadcast in the class of lines, for any @math ∈>0.
A wireless sensor network (WSN) consists of sensors implanted in an environment for collecting and transmitting data regarding changes in the environment based on the requests from a controlling device (called base station) using wireless communication. WSNs are being used in medical, military, and environment monitoring applications. Broadcast (dissemination of information from a central node) and convergecast (gathering of information towards a central node) are important communication paradigms across all application domains. Most sensor applications involve both convergecasting and broadcasting. The time taken to complete either of them has to be kept minimal. This can be accomplished by constructing an efficient tree for both broadcasting as well as convergecasting and allocating wireless communication channels to ensure collision-free communication. There exist several works on broadcasting in multihop radio networks (a.k.a. ad hoc networks), which can also be used for broadcasting in WSNs. These algorithms construct a broadcast tree and compute a schedule for transmitting and receiving for each node to achieve collision-free broadcasting. In this paper, we show that we need a new algorithm for applications, which involve both convergecasting and broadcasting since the broadcast tree may not be efficient for convergecasting. So we propose a heuristic algorithm (convergecasting tree construction and channel allocation algorithm (CTCCAA)), which constructs a tree with schedules assigned to nodes for collision free convergecasting. The algorithm is capable of code allocation (direct sequence spread spectrum (DSSS) frequency hopping spread spectrum (FHSS)), in case multiple codes are available, to minimize the total duration required for convergecasting. We also show that the same tree can be used for broadcasting and is as efficient as a tree exclusively constructed for broadcasting. The time-complexity of deterministic and randomized protocols for achieving broadcast (distributing a message from a source to all other nodes) in arbitrary multi-hop radio networks is investigated. In many such networks, communication takes place in synchronous time-slots. A processor receives a message at a certain time-slot if exactly one of its neighbors transmits at that time-slot. We assume no collision-detection mechanism; i.e., it is not always possible to distinguish the case where no neighbor transmits from the case where several neighbors transmit simultaneously. We present a randomized protocol that achieves broadcast in time which is optimal up to a logarithmic factor. In particular, with probability 1 --E, the protocol achieves broadcast within O((D + log n s) ‘log n) time-slots, where n is the number of processors in the network and D its diameter. On the other hand, we prove a linear lower bound on the deterministic time-complexity of broadcast in this model. Namely, we show that any deterministic broadcast protocol requires 8(n) time-slots, even if the network has diameter 3, and n is known to all processors. These two results demonstrate an exponential gap in complexity between randomization and determinism. Wireless ad hoc radio networks have gained a lot of attention in recent years. We consider geometric networks, where nodes are located in a Euclidean plane. We assume that each node has a variable transmission range and can learn the distance to the closest active neighbor at any time. We also assume that nodes have a special collision detection (CD) capability so that a transmitting node can detect a collision within its transmission range. We study the basic communication problem of collecting data from all nodes called convergecast. Recently, there appeared many new applications such as real-time multimedia, battlefield communications and rescue operations that impose stringent delay requirements on the convergecast time. We measure the latency of convergecast, that is the number of time steps needed to collect the data in any n-node network. We propose a very simple randomized distributed algorithm that has the expected running time O(logn). We also show that this bound is tight and any algorithm needs @W(logn) time steps while performing convergecast in an arbitrary network. One of the most important problems in wireless ad hoc networks is to minimize the energy consumption, which maximizes the network lifetime. We study the trade-off between the energy and the latency of convergecast. We show that our algorithm consumes at most O(nlogn) times the minimum energy. We also demonstrate that for a line topology, the minimum energy convergecast takes n time steps while any algorithm performing convergecast within O(logn) time steps requires @W(n logn) times the minimum energy. We consider variations of a problem in which data must be delivered to mobile clients en route, as they travel toward their destinations. The data can only be delivered to the mobile clients as they pass within range of wireless base stations. Example scenarios include the delivery of building maps to firefighters responding to multiple alarms. We cast this scenario as a parallel-machine scheduling problem with the little-studied property that jobs may have different release times and deadlines when assigned to different machines. We present new algorithms and also adapt existing algorithms, for both online and offline settings. We evaluate these algorithms on a variety of problem instance types, using both synthetic and real-world data, including several geographical scenarios, and show that our algorithms produce schedules achieving near-optimal throughput. This paper concerns the message complexity of broadcast in arbitrary point-to-point communication networks. Broadcast is a task initiated by a single processor that wishes to convey a message to all processors in the network. The widely accepted model of communication networks, in which each processor initially knows the identity of its neighbors but does not know the entire network topology, is assumed. Although it seems obvious that the number of messages required for broadcast in this model equals the number of links, no proof of this basic fact has been given before. It is shown that the message complexity of broadcast depends on the exact complexity measure. If messages of unbounded length are counted at unit cost, then broadcast requires T(u V u) messages, where V is the set of processors in the network. It is proved that, if one counts messages of bounded length , then broadcast requires T(u E u) messages, where E is the set of edges in the network. Assuming an intermediate model in which each vertex knows the topology of the network in radius r ≥ 1 from itself, matching upper and lower bounds of T(min u E u, u V u 1+T(l) r ) is proved on the number of messages of bounded length required for broadcast. Both the upper and lower bounds hold for both synchronous and asynchronous network models. The same results hold for the construction of spanning trees, and various other global tasks. Wireless sensor networks consist of sensor nodes with sensing and com- munication capabilities. We focus on data-aggregation problems in energy- constrained sensor networks. The main goal of data-aggregation algorithms is to gather and aggregate data in an energy efficient manner so that net- work lifetime is enhanced. In this article we present a survey of data-aggre- gation algorithms in wireless sensor networks. We compare and contrast different algorithms on the basis of performance measures such as lifetime, latency, and data accuracy. We conclude with possible future research directions. Sensor networks are distributed event-based systems that differ from traditional communication networks in several ways: sensor networks have severe energy constraints, redundant low-rate data, and many-to-one flows. Data-centric mechanisms that perform in-network aggregation of data are needed in this setting for energy-efficient information flow. In this paper we model data-centric routing and compare its performance with traditional end-to-end routing schemes. We examine the impact of source-destination placement and communication network density on the energy costs and delay associated with data aggregation. We show that data-centric routing offers significant performance gains across a wide range of operational scenarios. We also examine the complexity of optimal data aggregation, showing that although it is an NP-hard problem in general, there exist useful polynomial-time special cases.