Thesis: Proximity Structures for Wireless Networks

Advisor:
Dr. Mirela Damian
Assistant Professor
mire...@villanova.edu

Description:
This Project will focus on the design, analysis and OpenGL implementation of algorithms for constructing fundamental structures that form the core of the wireless communication, as well as simulation of applications running on top of these structures.

1	Power Efficient and Sparse Spanner for Wireless Ad Hoc Networks
2	Topology Control and Routing in Ad hoc Networks: A Survey
3	Topology Control for Ad-hoc Networks. Mirela Damian, Villanova University [presentation]
4	Modular Topology Control and Energy Model for Wireless Ad Hoc Sensor Networks (using OPNET)
5	V. Bahl, R. Wattenhofer, L. Li, and Y.M. Wang, “Distributed topology control for power efficient operation in multihop wireless ad hoc networks,” Proceedings of IEEE INFOCOM, April, 2001.
6	R. Ramanathan and R. Rosales-Hain, "Topology control of multihop Wireless networks using transmit power adjustment" , Proceedings of IEEE INFOCOM, March 2000.
7	Yu Wang Xiang-Yang Li, Wen-Zhan Song, “Efficient topology control for wireless ad hoc networks with nonuniform transmission ranges,” ACM WINET, 2003
8	Temporal Topology Control in Multi-channel Multihop Wireless Access Networks
9	Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks (requires password)
10	An Integrated Scheme for Fully-Directional Neighbor Discovery and Topology Management in Mobile Ad hoc Networks
11	Distributed Topology Control in Wireless Sensor Networks with Asymmetric Links
12	Distributed Topology Control of Wireless Networks (abstract only)
13	"Energy Conservation in Wireless Sensor Networks via Domatic Partitions,'' with Imran Pirwani. MOBIHOC, 2006
14	Span: An EnergyEfficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks
15	Maximizing the Lifetime of Dominating Sets, Thomas Moscibroda and Roger Wattenhofer
16	Approximating the domatic number by Feige, Halld´orsson, Kortsarz, and Srinivasan
17	Geography-informed Energy Conservation. for Ad Hoc Routing. Ya Xu
18	Adaptive Energy-Conserving Routing for Multihop Ad Hoc Networks (2000) , Ya Xu, John Heidemann, Deborah Estrin
19	PAMAS Power Aware Multi-Access protocol with Signalling for Ad Hoc Networks (1999), Suresh Singh, C.S. Raghavendra
20	Power-Aware Routing in Mobile Ad Hoc Networks (1998), Suresh Singh, Mike Woo, C. S. Raghavendra
21	A Channel Access Scheme for Large Dense Packet Radio Networks. Timothy J. Shepard
22	Tpology Control of Multihop Wireless Networks using Transmit Power Adjustment (2000), Ram Ramanathan, Regina Rosales-Hain
23	Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks (2001), Roger Wattenhofer, Li Li, Paramvir Bahl, Yi-Min Wang
24	Minimum Energy Mobile Wireless Networks (1998), Volkan Rodoplu, Teresa H. Meng
25	Energy Conserving Routing in Wireless Ad-hoc Networks (2000), Jae-Hwan Chang, Leandros Tassiulas
26	Energy-Efficient Communication Protocol for Wireless Microsensor Networks (2000), Wendi Rabiner Heinzelman, Anantha Chandrakasan, et al. [just a routing protocol, does not discuss power issues]
27	Reducing Power Consumption of Network Interfaces in Hand-Held Devices (Extended Abstract) (1996), Mark Stemm, et al.
28	Energy efficient distributed connected dominating sets construction in wireless sensor networks, Zeng Yuanyuan Wuhan University, Wuhan, Hubei, China, Xiaohua Jia City University of Hong Kong, Hong Kong, China, He Yanxiang Wuhan University, Wuhan, Hubei, China (Year of Publication: 2006)
29	K. Farkas, F. Maurer, L. Ruf, B. Plattner: Dominating Set Based Support for Distributed Services in Mobile Ad Hoc Networks - conference talk; In Proceedings of the 10th IEEE/IFIP Network Operations and Management Symposium (NOMS 2006); Vancouver, Canada; 3-7 April 2006.
30	A Faster Distributed Approximation Scheme for the Connected Dominating Set Problem for Growth-Bounded Graphs, ETH Technical Report 540, 2006
31	Energy Efficient Distributed Connected Dominating Sets Construction in Wireless Sensor Networks, July 2006
32	Polynomial-Time Approximation Scheme for Minimum Connected Dominating Set in Ad Hoc Wireless Networks, 2003
33	Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons, April 2005
34	Fast Distributed Well Connected Dominating Sets for Ad Hoc Networks (2004)
35	Local Approximation Schemes for Ad Hoc and Sensor Networks, Sep 2005
36	Constant-Time Distributed Dominating Set Approximation* ,2003
37	Localized probabilistic and dominating set based algorithm for efficient information dissemination in ad hoc networks 2004
38	Improved approximation algorithms for connected sensor cover, (April 2007)
39	Minimizing broadcast latency in ad hoc wireless networks (March 2007)
40	Size-restricted cluster formation and cluster maintenance technique for mobile ad hoc networks (March 2007)
41	Routing protocols for efficient communication in wireless ad-hoc networks (October 2006)
42	Local approximation schemes for ad hoc and sensor networks (Sep 2005)
43	Minimizing broadcast latency and redundancy in ad hoc networks (2003)
44	Constant density spanners for wireless ad-hoc networks (July 2005)
45	Polynomial-time data reduction for dominating set (2004)
46	Distributed low-cost backbone formation for wireless ad hoc networks (2005)
47	Localized construction of bounded degree and planar spanner for wireless ad hoc networks (2003)
48	A unified energy-efficient topology for unicast and broadcast 2005
49	Maximizing system lifetime in wireless sensor networks 2005
50	Constant density spanners for wireless ad-hoc networks 2005
51	A simple improved distributed algorithm for minimum CDS in unit disk graphs (August 2006)
52	On calculating connected dominating set for efficient routing in ad hoc wireless networks 1999
53	Virtual backbone based on MCDS for topology control in wireless ad hoc networks (2005 )
54	Probabilistic power management for wireless ad hoc networks 2005
55	TITAN: on-demand topology management in ad hoc networks 2005
56	Energy-efficient broadcasting in wireless ad hoc networks: performance benchmarking and distributed algorithms based on network connectivity characterization 2005
57	Bandwidth optimization by reliable-path determination in Mobile Ad-Hoc Networks 2004
58	Distributed construction of connected dominating set in wireless ad hoc networks 2004
59	Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks
60	Dominating-set-based Routing in Ad Hoc Networks
61	Interference in Wireless Multi-Hop Ad-Hoc Networks and Its Effect on Network Capacity
62	J.B.D. Cabrera, R. Ramanathan, C. Guitierrez, R. Mehra, "Stable Topology Control for Mobile Ad Hoc Networks", IEEE Communications Letters, Vol. 11, No. 7, July 2007, pp. 574-576
63	*R. Ramanathan, J. Redi, "A brief overview of ad hoc networks: challenges and directions", IEEE Communications Magazine* Vol. 40, Issue 5, May 2002**
64	Y. Wang and X.-Y. Li. Distributed spanner with bounded degree for wireless ad hoc networks. In Parallel and Distributed Computing Issues in Wireless networks and Mobile Computing, April 2002.
65	L. Li, J. I-Ialpern, V. Bahl, Y.-M. Wang, and R. Wattenhofer. Analysis of a cone-based distributed topology control algorithms for wireless multi-hop networks. In Proceedings of A CM Symposium on Principles of Distributed Computing, pages 264-273, August 2001.
66	Ravi Prakash " Unidirectional links prove costly in Wireless Ad-Hoc Networks " , Proceedings of the Discrete Algorithms and Methods for Mobile Computing and Communications - Dial M '99, Seattle, WA, August 20, 1998
67	Improved Greedy Algorithms for Constructing Sparse Geometric Spanners (2000), Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan
68	Efficient Construction of a Bounded Degree Spanner with Low Weight (1995) Sunil Arya, Michiel Smid
69	Constructing Plane Spanners of Bounded Degree and Low Weight (2002) Prosenjit Bose, Joachim Gudmundsson, Michiel Smid
70	A fast algorithm for constructing sparse Euclidean spanners, Gautam Das Giri Narasimhan
71	Optimally sparse spanners in 3-dimensional Euclidean space, Gautam Das Paul Heffernan Giri Narasimhan
72	There is a planar graph almost as good as the complete graph, P Chew
73	EFFICIENT CONSTRUCTION OF LOWWEIGHTED BOUNDED DEGREE PLANAR SPANNER, XIANG-YANG LI, YU WANG

	Sensor Networks + dominating set + interference
1	Interference Aware Dominating Set for Sensor Network 2006
2	Minimizing interference in ad hoc and sensor networks Sep 2005
3	Analysis of Interference in Ad-Hoc Networks 2003
4	Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks Ad Hoc Networks 2006
5	A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs 2006
6	Constant density spanners for wireless ad-hoc networks 2005
7	* Impact of interferences on connectivity in ad hoc networks 2005
8	A Robust Interference Model for Wireless Ad-Hoc Network 2005


	Open Problems
1	Algorithms for ad hoc and sensor networks 2004

	CDS Based Approach
1	A New Distributed Approximation Algorithm for Constructing Minimum Connected Dominating Set in Wireless Ad Hoc Networks, 2004
2	Receiver-based CDS Algorithm for Wireless Networks
3	A Fuzzy Logic Control Engine for CDS-based Backbone Maintenance in Wireless Networks
4	Connected Dominating Sets in Wireless Networks
5	An Effective Distributed Approximation Algorithm for Constructing Minimum Connected Dominating Set in Wireless Ad Hoc Networks
6	An Efficient Approximation Scheme for Minimum Connected Dominating Set in Wireless Ad Hoc Networks
7	Distributed Algorithms for Coloring and Domination in Wireless Ad Hoc Networks
8	CS547: Wireless Networking
9	A distributed algorithm for constructing energy-balanced connected dominating set in wireless sensor networks, International Journal of Sensor Networks (IJSNET), Vol. 2, No. 1/2, 2007
10	Distributed Algorithms for Coloring and Domination in Wireless Ad Hoc Networks
11	Localized Construction of Connected Dominating Set in Wireless Networks
12	Efficient Construction of Connected Dominating Set in Wireless Ad Hoc Networks
13	A distributed algorithm for computing Connected Dominating Set in ad hoc networks, Volume 1, Number 2 / 2006
14	On Greedy Construction of Connected Dominating Sets in Wireless Networks, Dec 2004
15	*L. Bao and J. J. Garcia-Luna-Aceves, "Topology Management in Ad Hoc Networks," Proc. MobiHoc 2003, pp. 129-140.*

	Simulation Framework / Tools
1	Simulation Framework for a Mobile Ad-Hoc Network
2	Ad Hoc Network Simulator, Written by Abhi Bhirud and Bhavin Parikh, under the guidance of Professor Rami Melhem and Professor Taieb Znati.
3	ad hoc network simulation
4	SWANS- Scalable Wireless Ad hoc Network Simulator - User Guide Here
5	SWANS++ - Extensions to the Scalable Wireless Ad-hoc Network Simulator
6	Programming Ad-hoc Networks of Mobile and Resource-Constrained Devices
7	JUNG - Java Universal Network/Graph Framework
8	Graphviz - Graph Visualization Software - Download for Windows

	Workshops / Conferences
1	The First International Workshop on Wireless Mesh and Ad Hoc Networks (WiMAN 2007) in conjunction with ICCCN 2007
2	HotMobile 2008 sponsored by ACM and Sigmobile Silverado Resort, Napa Valley, CA, USA February 25-26, 2008 Paper submissions due: October 16, 2007, 23:59 EST
3	ACM Student Research Competitions

	Important Links
1	Villanova, Arts and Sciences - Thesis Guidelines



	MANET wireless ad hoc network sensor network topology control thesis research OPNET model modeling simulation