The world of wireless sensor networks has seen tremendous interest in the recent past from researchers and industry. Inexpensive battery-powered sensors with limited computing and wireless networking capabilities, such as the Motes, have been deployed for various applications, such as border patrol and environmental monitoring. 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 transmit information over multiple hops to conserve energy. The objective of a sensor network is to maximize the operational time by considering sensing, computing, and communication costs together.
Special protocols are necessary if the nodes are moving, for example, communication between cars. The protocols need to take into account the high probability that messages are dropped due to communication channel impairments. In addition, the nodes are unlikely to keep an up-to-date copy of their neighbors due to frequent movement of the neighbors. Therefore, the algorithms and protocols designed for such mobile ad hoc sensor networks lie in the intersection of ad-hoc networks, computational geometry, databases, and graph theory.
Alon Efrat, Department of Computer Science
Class Hours
Office Hours
Mondays and Wednesdays 4.30 PM - 5.45 PM in Gould-Simpson 906
Mondays and Wednesday 2.30 PM - 4.00 PM Gould-Simpson 747 Or by appointment. - - -
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.
To be announced.
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.
Capacity Analysis
The worst-case capacity of wireless sensor networks [ PDF ]
Thomas Moscibroda, IPSN 2007.
Key Pre-Distribution in Sensor Networks
A key-management scheme for distributed sensor networks [ PDF ]
Eschenauer, L. and Gligor, V. D. 2002.
In Proc. 9th ACM Conference on Computer and Communications Security (CCS'02).
Establishing pairwise keys in distributed sensor networks [ Journal Version ] [ Conference Version ]
Liu, D., Ning, P., and Li, R. 2005.
ACM Trans. Information and System Security 8, 1 (Feb.), 41-77.
A Canonical Seed Assignment Model for Key Predistribution in Wireless Sensor Networks [ PDF ]
[ Conference Version ]
Patrick Tague and Radha Poovendran
To appear in ACM Transactions on Sensor Networks (TOSN), 2007.
Combinatorial design of key distribution mechanisms for distributed sensor networks [ PDF ]
Camtepe, S. A. and Yener
In Proc. 9th European Symposium on Research in Computer Security (ESORICS'04), LNCS 3193.
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.
Localization for Anchoritic Sensor Networks [ PDF ]
Baryshnikov and Jian Tan, Distributed Computing in Sensor Systems (DCOSS), 2007.
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.
Approximate Isocontours and Spatial Summaries for Sensor Networks [ PDF ]
Sorabh Gandhi, John Hershberger, and Subhash Suri. (Best Paper Award.) IPSN '07
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 ]
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