We address the problem of gathering information in sensor webs consisting of sensors nodes, wherein a round of communication sensor nodes have messages to be sent to a distant central node (called the base station) over the shortest path. There is a wide range of data gathering applications like target and hazard detection, environmental monitoring, battlefield surveillance, etc. Consequently, efficient data collection solutions are needed to improve the performance of the network. In this article, we take into account the fact that interference can occur at the reception of a message at the receiver sensor. In order to save redundant retransmissions and energy, we assume a known distribution of sources (each node wants to transmit at most one packet) and one common destination. We provide a number of scheduling algorithms jointly minimizing both the completion time and the average packet delivery time. We define our network model using directional antennas and consider Ring, Tree, and Grid Network (and its generality) topologies. All our algorithms run in low-polynomial time. Networks of such devices can autonomously perform various sensing tasks such as environmental (seismic, meteorological) monitoring and military surveillance, enemy tracking, target detection, distribution of timing and position information, and multi-hop communication [1] . The sensor could be sensing the temperature, the pressure, oil leak, radiation, etc. Generally, these networks are referred to as wireless ad-hoc sensor networks or simply sensor networks. It can also be a collection of mobile sensor nodes that dynamically form a temporary network without the use of any existing network infrastructure or centralized administration. In other words, the primary application of such networks has been in disaster relief operations, military use, conferencing, and environment sensing. A typical application in web is gathering of sensed data at a distant central processing system named the base station (BS) (or the root node in the network graph). This root node is assumed to be with greater computational, storage, and transmission capabilities than the rest of the nodes in the network. The root node typically serves as an entry point to the sensor network, integrating the sensor network with wired network. In each round of this data gathering application, all the data from all nodes need to be collected and transmitted to the BS, where the end-user can access the data. In some sensor network applications, data collection may be needed only from a region and, therefore, a subset of nodes will be used. A simple approach to accomplishing this data gathering task is for each node to transmit its data directly to the BS. Since the BS is typically located far away, the energy cost to transmit to the BS from any node is quite high. Therefore, an improved approach is to use few and multi-hop transmissions as possible to the BS. In contrast, in many emerging and envisioned applications, sensor networks will be both distributed and wireless (in terms of communication and power) [2] . Distribution is necessary for improving the sensing quality-when the precise location of a signal is unknown, then distributed sensors will allow sensing to take the place closer to the event of interest than by any signal sensor. Distribution also improves robustness to environmental obstacles, which is especially crucial in situations where sensing requires line-of-sight. The sensor units, thus, need to rely on finite, local energy sources and wireless communications channels. Finally, shorter range communication is generally much cheaper than longer range communication because the radio-signal power can drop off with a quadratic power of distance [3] . As a result, it is much cheaper to transmit information using multi-hopping among sensor units. One way to reduce the amount of data that must be transmitted (and reduce energy) in radio networks is scheduling forwarded information gathered by sensor nodes. The scheduling process is intended to prevent collisions that might arise from improper or inefficient use of the network resources by random messaging across the network without taking into account the network model. Then, we aim to solve the problem for a given certain topology of radio network and a network model, initial information (messages) located at some nodes, and a single designated destination. We consider the Ring and the Tree networks and give optimal scheduling solutions that achieve a minimum completion time as well as a minimum average delivery time. For the Grid network topology (and its extensions) we propose an approximation algorithm to our problem providing a 1.5 approximation ratio for maximum completion time. We present low-polynomial time solutions for our problem for the above-mentioned network topologies and we also provide some useful insights. Our research can be practically implemented in those networks; for example, whenever a node has a packet to transmit, it sends a very short message (to save battery energy) called a ''Schedule Request'' to a central computer (BS) that serves as the only destination in the network. The requests can be sent over an upstream control channel (or multiple upstream control channels) using, for example, ALOHA or CDMA random-access Y. Revah and M. Segal
The case of grids is considered in REF where a 1.5-approximation algorithm is presented.
Improved Algorithms for Data-Gathering Time in Sensor Networks II: Ring, Tree, and Grid Topologies
International Journal of Distributed Sensor Networks
Computer Science