Mahendran Velauthapillai is McBride Professor of Computer Science in the Computer Science department at Georgetown University, Washington, DC. He was the first endowed chair in Sciences ever awarded at Georgetown University and with a lifetime appointment. Prof. Mahendran Veluathapillai holds B.Sc degree in Mathematics from the University of Sri Lanka (1977), a M.S degree in Mathematics from the University of Ohio(1980), a M.S degree in Computer Science from University of Purdue(1982), a Doctor of Computer Science (Ph.D.) from the University of Maryland (1986). His research areas are in learning theory, algorithms and bioinformatics.

## Establishing Communication, Non-Destructive Monitoring and the complexity of an Inverse Problem in a Sensor Network

Co-operative computations in a network of sensor nodes rely on an established, interference free and repetitive communication between adjacent sensors. This talk analyzes a simple randomized and distributed protocol to establish a periodic communication schedule S where each sensor broadcasts once to communicate to all of its neighbors during each period of S. The result obtained holds for any bounded degree network. The existence of such randomized protocols is not new. Our protocol reduces the number of random bits and the number of transmissions by individual sensors from

? (log^{2} n) to O (log n) where n is the number of sensor nodes. These reductions conserve power which is a critical resource. Both protocols assume upper bound on the number of nodes n and the maximum number of neighbor’s b. For a small multiplicative (i.e., a factor ? (1)) increase in the resources, our algorithm can operate without an upper bound on b.

Next we consider a sensor network for monitoring an environment. Assume that there is hidden value under each node of the sensor network covering the environment. The true value could represent a crack, material failure, temperature, intensity of vibration etc. However, when a measurement is taken at a node, the sensor measurement results in a readout which is a function of the true value of the node and its immediate neighbors. Now, given the sensor measurements, retrieving the true values is the inverse problem that we consider in this talk.