Rui Fan, Allen Miu, Eugene Shih
6.856 Term Paper, December 2000.

Introduction

Wireless sensor networks used for surveillance are typically deployed in environments where positions and locations of network entities cannot be controlled. Rather, nodes tend to be randomly scattered over some terrain where objects of interest may traverse. One main purpose of these sensor nodes is to provide information about interesting events that occur in the environment. For example, in the military, tiny sensor nodes can be used to monitor enemy soldier and tank maneuvers in an area of conflict. When a moving tank is detected by some array of sensors, some information (e.g. velocity) about the tank should be reported by the sensor to the basestation of an ally.

In such a network, nodes have limited energy resources due to their size and the low energy density of small batteries. Therefore, computation and communication at each node should not be used without carefully considering the energy costs. In addition, the communication protocol should be designed in such a way so that nodes do not wastefully communicate. Note that in such a system, both transmitting and receiving can be costly. Therefore, collisions should be minimized and constant transmission prohibited.

Clearly, a media-access control (MAC) protocol will be needed to allow the nodes to share the wireless media. A good MAC protocol will provide high throughput while maintaining an equal share of the available bandwidth among the nodes. However, designing a good MAC protocol without any information about the topology of a network can be difficult. One beneficial piece of information that can help the MAC designer is the neighborhood size. Thus, we introduce the network neighborhood size estimation (N-EST) problem. Given a set of N nodes randomly scattered over some terrain, we wish to determine the number of neighbors n for each node. A node u is considered a neighbor of v if u is within a communication range r of v. All nodes have the same r and it is not necessary for any node to know the number of neighbors for any other node.

In this paper, we will present a parallel fully polynomial randomized approximation scheme with O((log N)^2) running time to estimate the neighborhood size for every node in the network.

[Gzipped PostScript (156KB)][PDF (1.03MB)]