Sensor networks and wireless ad-hoc networks are becoming increasingly important, and there is a huge body of works currently around them. Many of the interesting and important problems result from the special conditions, and has led to algorithms with geometric considerations. Sensors should be placed according to the details of the areas they need to cover (e.g. terrains, buildings, etc.). Transmitters are battery powered, hence their wireless communication range is short, or if they can control their range, would prefer to send most of their transmissions to a nearby station.

Special protocols are necessary, especially if nodes are moving (for example if communications is between cars). These protocols need to take into account the high probability that messages are dropped due to communication channel impairments. This implies for example that each message should be transmitted a few times, along different routes, to increase robustness. In general, these algorithms lie in the intersection between ad-hoc networks, computational geometry, databases and graph theory.

 

Alon Efrat, Department of Computer Science


Srinivasan Ramasubramanian, Department of Electrical and Computer Engineering

 

Class Hours
Mondays and Wednesdays 4.30 PM - 5.45 PM in Gould-Simpson 906

Office Hours
Mondays 1.30 PM - 3.00 PM Gould-Simpson 737 Alon Efrat
Tuesdays 10.00 AM - 11.00 AM ECE 320D Srinivasan Ramasubramanian
Wednesdays 10.00 AM - 11.00 AM ECE 320D Srinivasan Ramasubramanian
Thursdays - - -
Fridays 2.00 PM - 3.15 PM Gould-Simposon 720 Alon Efrat

 

The topics discussed in the seminar would include, but not limited to:

Algorithms for sensors and basement locations
Here we need to locate sensors in a way that a building or terrain would sensor a large enough area for surveillance. We also discuss other relevant location problems. (4; 3, 4, Appendix A): approximating functions asymptotically, some common recurrence formulas.

Protocols for maintaining connectivity between moving points
We will study routing algorithms and message forwarding mechanisms that are resilient to mobility in the network.

Indexing moving nodes, and location bases services
Here we study ways to efficiently maintain data-bases that can answer queries on a large number of objects which are moving in the plane. For example, to find cellular user which are currently within a certain region.

Code distributions between sensors
Sensors are becoming increasingly intelligent, and can run small programs to make process the data they collect on board, rather than sending the raw data. The code they are using might be update, and we will discuss in the seminar ways to distributes the code in an efficient way. The part involves some familiarity with compilers/operating system.

 

September 11 and 13, 2006
Rui Zhang, "Multi-dimensional range seearching"

September 18 and 20, 2006
YoungBeom Ryu and Shalini Rao, "General Reading"

September 25 and 27, 2006
Shrinivasa Kini and Sandeep Ahuja, "Geographical Routing"

October 2 and 4, 2006
Swaminathan and YoungBeom Ryu, "Geometric and Topological Methods in Routing"

October 9 and 11, 2006
Sulakshana Ramkumar, "Localization and Network Discovery"

October 16 and 18, 2006
To be decided

October 23, 2006
Mohammad Siam, "Lifetime Maximization for Multicasting"

October 25, 2006
"Range Queries in Sensor Networks"

October 30 and November 1, 2006
"Boundary Detection"

November 6 and 8, 2006
Ramabhadran, "Range queries"
Swaminathan and YoungBeom Ryu, "Boundary Recognition"

Friday, November 10, 2006 - 2.00 PM (Location: ILC 129)
Swaminathan and YongBeom Ryu, "Boundary Recognition"

November 15, 2006
Poorna, "Construction of Dominating Sets"

November 20 and 22, 2006
Sapna and Archana, "Energy Efficient Coordination"

November 27 and 29, 2006
Shrinivas Kini and Sandeep Ahuja, "Geographical Routing"

Friday December 1, 2006
Shalini and Aditi, "Medial Axis Routing"
Sulakshana, "Localization"

December 4, 2006
Harveer Sandhu, "Boundary Detection/Security"

December 6, 2006
Arvind Sethuraman, "Efficient Location Tracking"

Friday December 8, 2006
Ravi Sheshu, "GLIDER"

 

 

The final grade is determined by 90% quality of presentation and 10% participations in class.

 

Thanks to Prof. Subhash Suri, UCSB for allowing us to use his material. You can download all the papers as a tar.gz or zip file.

Localization and Network Discovery
Robust distributed network localization with noisy range measurements [ PDF ]
D. Moore, J. Leonard, D. Rus, S. Teller. Proc. ACM SenSys 2004.

Mobile-Assisted Localization in Wireless Sensor Networks [ PDF ]
N. B. Priyantha, H. Balakrishnan, E. Demaine, S. Teller. IEEE INFOCOM, Miami, FL, March 2005.

A theory of network localization [ PDF ]
J. Aspnes et al. IEEE Transactions on Mobile Computing.

Distributed Localization Using Noisy Distance and Angle Information [ PDF ]
Amitabh Basu, Jie Gao, Joseph S. B. Mitchell, and Girishkumar Sabhnani. MobiHoc 2005.

Force-Directed Approaches to Sensor Localization [ PDF ]
C. Erten, D. Forrester, A. Iyer, and S. G. Kobourov. 8th Workshop on Algorithm Engineering and Experiments (ALENEX) 2006.


Geographical Routing
Geographic Routing Made Practical [ PDF ]
Y.-J. Kim, R. Govindan, B. Karp, S. Shenker, Proc. of USENIX NSDI 2005.

GPSR: Greedy perimeter stateless routing for wireless networks [ PDF ]
B. Karp and H. T. Kung. Proc. Mobicom 2000.

Geographic Routing With Limited Information in Sensor Networks [ PDF ]
S. Subramanian and S. Shakkottai Proc. IPSN 2005.


Geometric and Topological Methods in Routing
 Locating and Bypassing Routing Holes in Sensor Networks [ PDF ]
Q. Fang, J. Gao and L. J. Guibas. Proc. INFOCOM 2004.

GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks [ PDF ]
Q. Fang, J. Gao, L. J. Guibas, V, de Silva, L. Zhang. Proc. INFOCOM 2005.

Geometric Spanner for Routing in Mobile Networks [ PDF ]
J. Gao, L. J. Guibas, J. Hershburger, L. Zhang, and A. Zhu. Proc. MobiHoc 2001.


Range Queries in Sensor Networks
 Multi-dimensional Range Queries in Sensor Networks [ PDF ]
X. Li, Y. J. Kim, R. Govindan, W. Hong. Proc. ACM SenSys 2003.

Fractionally cascaded information in a sensor network [ PDF ]
J. Gao, L. J. Guibas, J. Hershberger, L. Zhang. Proc. IPSN 2004.

Data-Centric Storage in Sensornets with GHT [ PDF ]
S. Ratnasamy, B. Karp, S. Shenker, D. Estrin, R. Govindan, L. Yin and F. Yu. Mobile Networks and Applications, 2003.


Data Aggregation: Various Aspects
 Resilient Aggregation in Sensor Networks [ PDF ]
David Wagner. Proc. SASN 2004.

Medians and Beyond: New Aggregation Techniques for Sensor Networks [ PDF ]
N. Shrivastava, C. Buragohain, D. Agrawal, S. Suri. Proc. ACM SenSys '04.

Robust Aggregation in Sensor Networks [ PDF ]
G. Kollios, J. Byers, J. Considine, M. Hadjieleftheriou, and F. Li. Proc. ICDE 2004.


Tracking and Geometric Reasoning
 Efficient Location Tracking Using Sensor Networks [ PDF ]
H. T. Kung and D. Vlah. Proc. IEEE Wireless Communications and Networking Conference, 2003.

Spatiotemporal Multicast in Sensor Networks [ PDF ]
Q. Huang, C. Lu and G.-C. Roman. Proc. SenSys 2003.

On Target Tracking with Binary Proximity Sensors [ PDF ]
W. Kim, K. Mechitov, J. Choi and S. Ham. Proc. IPSN 2005.


Construction of Connected Dominating Sets
 On Greedy Construction of Connected Dominating Sets in Wireless Sensor Networks [ PDF ]
Y. Li, M. T. Thai, F. Wang, C. Yi, P.-J. Wan, D.-Z Du, WCMC 2005.

An Extended Localized Algorithm for Connected Dominating Set Formation in Wireless Ad Hoc Networks [ PDF ]
F. Dai and J. Wu, IEEE Transactions on Parallel and Distributed Systems, October 2004.

Constant time distributed dominating set approximation [ PDF ]
F. Kuhn and R. Watternhofer.


Boundary Detection
Deterministic boundary recognition and topology extraction for large sensor networks [ PDF ]
A.Kröller, S.P. Fekete, D.Pfisterer, S.Fischer. Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 1000-1009.

Boundary Recognition in Sensor Networks by Topological Methods [ PDF ]
N. B. Priyantha, H. Balakrishnan, E. Demaine, S. Teller. IEEE INFOCOM, Miami, FL, March 2005.
Yue Wang, Jie Gao, Joseph S. B. Mitchell. Proc. 12th Annual ACM Conference on Mobile Computing and Networking (MobiCom 2006).

General Reading
 An analysis of a large scale habitat monitoring application [ PDF ]
R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson, D. Culler. ACM SenSys 2004.

Designing Secure Sensor Networks [ PDF ]
E. Shi and A. Perrig. Wireless Sensor Networks.

Embedded Sensor Networks [ PDF ]
John Heidemann and Ramesh Govindan