CSAIL Research Abstracts - 2005 link to http://publications.csail.mit.edu/abstracts/abstracts05/index.html link to http://www.csail.mit.edu
bullet Introduction bullet Architecture, Systems
& Networks
bullet Language, Learning,
Vision & Graphics
bullet Physical, Biological
& Social Systems
bullet Theory bullet

horizontal line

Modeling Sensor Networks

Wolfgang Lindner & Piotr Indyk

What:

We study a new model, simple and powerful enough to model complex networks, having nodes with different radiation patterns, or obstructions.

Why:

As the sensor technology becomes more powerful, it is natural to expect that sensors with non-circular radiation pattern will widely be used in the near future, changing current data acquisition and processing models fundamentally. Unfortunately, current structures to model ad-hoc networks fail for a variety of scenarios, e.g. non-circular radiation patterns.

How:

So far the most popular model to study sensor networks (mobile ad-hoc networks) is based on Unit Disk Graphs [1]. Nodes are located in the Euclidean plane, all having the same transmission radii normalized to one. Further, an edge between two nodes u and v exists, if their Euclidean distance is not greater than one ||u-v||<= 1. In other words u and v have to be within mutual transmission range, as shown in Figure 1, in order to be connected.

Figure 1

Many of the properties of an antenna used for reception are the same as its properties in transmission. It has the same directive pattern in both cases, and delivers maximum signal to the receiver when a signal comes from a direction in which the antenna has its best response. In the receiving case the antenna is the sources of power delivered to the receiver, rather than the load for a source of power (as in transmitting). Therefore, it is just natural to consider two nodes in a network connected, if, and only if, their radiation patterns overlap.

Figure 2

An edge between two nodes u and v exists, if their radiation pattern A and B overlap, with A and B are sets of points in the Euclidean plane. For the purpose of this paper we assume the radiation area of all circular sensors to be of the same size and shape. We further assume the radiation area of all elliptical sensors to be of identical size and shape. As Figure 2 shows nodes u and v are connected since their radiation patterns A and B intersect. In contrast, nodes v and w are not directly connected since the pattern B and C are not overlapping. Compared to Figure 1, w is connected to u since our model assumes each node has a radiation pattern associated with it. So we can derive a connection graph, connecting v and w using an additional hop. This model is simple and at the same time powerful enough to express more complex connection scenarios, e.g. involving directional sensors.

Progress:

By using this new model we were able to show that the diameter (i.e., the minimum number D such that any pair of nodes is within D hops from each other) of a sensor network can be substantially reduced, if a network contains sensors with non-circular antennas. This holds even if the sensor positions (location and direction) are chosen independently at random. We provided both computational simulations and theoretical bounds on the possible improvement.

Future:

We believe that our theoretical results as well as the model we propose will have a significant impact on future research in the area of hybrid ad-hoc networks, and in particular, their management of data. We therefore will continue our work in this area.

References:

[1] B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs. Discrete Mathematics, 86:165-177, 1990.

[2] Piotr Indyk and Wolfgang Lindner. Reducing Diameter of Sensor Networks Using Sensors with Non-circular Radiation Patterns. Submitted for publication 2005.

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu
(Note: On July 1, 2003, the AI Lab and LCS merged to form CSAIL.)