* Faculty       * Staff       * Students & Alumni       * Committees       * Contact       * Institute Directory
* Undergraduate Program       * Graduate Program       * Courses       * Institute Catalog      
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Colloquia       * Seminars       * News       * Events       * Institute Events      
* Overview       * Lab Manual       * Institute Computing      
No Menu Selected

* News


A Local Facility Location Algorithm for Sensor Networks

Dr. Ran Wolff
Department of Computer Science and Electrical Engineering
University of Maryland, Baltimore County

Tuesday, February 1, 2005
DCC 330- 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.

Consider a sensor network comprised of thousands of battery operated sensors which collect data and transfer it to a number of gateways sensor, which have a more permanent power supply and which then transmit the data to the system's operators. Assume that although there may be quite a few available gateways (e.g., passer by vehicles, overflying airplanes, ground facilities, etc.) bandwidth and power considerations, or restrictions at the operators' side only permit that a fixed number of these facilitate the communication at every given time. The question then arises which are the $k$ potential gateways which will best support the sensors. Note that this problem should be continuously solved because the availability of the potential gateways, as well as the ability of sensors to communicate with them and the importance of the data generated by each sensor may vary considerably over time.

The problem described above is an instance of the well known facility location problem (FLP) which deals with finding the optimal way to provide a service to a (possibly) very large number of clients. FLP has been studied in many application areas, including the placement of distribution centers in the retail domain, of proxy servers in Internet domain, and of relay stations in the telecommunication domain. Since FLP is NP-hard, a hill-climbing heuristic is regularly used to provide an approximate solution. In this paper we show that a variation of the problem can be solved using a \emph{local} algorithm. Local algorithms are extremely useful in a sensor network scenario. This is because they allow restricting communication range of the sensor to the minimum which still provide full system connectivity, because they can operate in routerless networks, and because they allow solvingcomplex problems relying on just a handful of information gathered from nearby sensors. The local facility location algorithm we describe is entirely asynchronous, seamlessly supports failures and changes in the data during calculation, poses modest memory and computational requirements, and has the ability to provide an anytime solution which is guaranteed to converge to the exact same one that would be computed by a centralized algorithm given the entire data.

Short Bio: Ran Wolff received his B.A. and Ph.D. degrees in computer science from the Technion - Israel. He has numerous publications in the area of data mining and local algorithms for peer-to-peer, Grid, and sensor networks. Currently he is holding a postdoctoral position at the University of Maryland, Baltimore County under the supervision of Prof. Hillol Kargupta.
Host: Bolek Szymanski

Last updated: January 26, 2005