Efficient communication strategies for ad-hoc wireless networks (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient communication strategies for ad-hoc wireless networks (extended abstract)

Full text

Pdf (1.56 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures table of contents

Puerto Vallarta, Mexico

Pages: 259 - 268

Year of Publication: 1998

ISBN:0-89791-989-0

Authors

Micah Adler	Department of Computer Science University of Toronto, 10 King's College Rd. Toronto ON, M5S3G4, Canada
Christian Scheideler	Heinz Nixdorf Institute and Dept. of Mathematics & Computer Science, Paderborn University, 33095 Paderborn, Germany

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 15, Citation Count: 14

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/277651.277692 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
	2	Noga Alon , F. R. K. Chung , R. L. Graham, Routing Permutations on Graphs Via Matchings, SIAM Journal on Discrete Mathematics, v.7 n.3, p.513-530, Aug. 1994 [doi>10.1137/S0895480192236628]
	3	Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, v.45 n.1, p.104-126, Aug. 1992 [doi>10.1016/0022-0000(92)90042-H]
	4	Reuven Bar-Yehuda , Amos Israeli , Alon Itai, Multiple communication im multihop radio networks, SIAM Journal on Computing, v.22 n.4, p.875-887, Aug. 1993 [doi>10.1137/0222055]
	5	Serdar Boztaş, A robust multi-priority topology-independent transmission schedule for packet radio networks, Information Processing Letters, v.55 n.5, p.291-295, Sept. 15, 1995 [doi>10.1016/0020-0190(95)00098-W]
	6	Danilo Bruschi , Massimiliano Del Pinto, Lower bounds for the broadcast problem in mobile radio networks, Distributed Computing, v.10 n.3, p.129-135, April 1997 [doi>10.1007/s004460050030]
	7	K.-C. Chen. Medium access control of wireless LANs for mobile computing. IEEE Network 8(5), pp. 50-63, 1994.
	8	Imrich Chlamtac , András Faragó, Making transmission schedules immune to topology changes in multi-hop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.23-29, Feb. 1994 [doi>10.1109/90.282605]
	9	I. Chlamtac, S. Kutten. On broadcasting in radio networks - problem analysis and protocol design. IEEE Trans. Commun. 33(12), 1985.
	10	I. Chlamtac , S. S. Pinter, Distributed nodes organization algorithm for channel access in a multihop dynamic radio network, IEEE Transactions on Computers, v.36 n.6, p.728-737, June 1987 [doi>10.1109/TC.1987.1676965]
	11	I. Chlamtac, O. Weinstein. The wave expansion approach to broadcasting in multihop radio networks. IEEE Trans. Commun. 39(3), pp. 426-433, 1991.
	12	I. Cidon , M. Sidi, Distributed Assignment Algorithms for Multihop Packet Radio Networks, IEEE Transactions on Computers, v.38 n.10, p.1353-1361, October 1989 [doi>10.1109/12.35830]
	13	R. Cole, B. Maggs, R. Sitaraman. Reconfiguring arrays with random faults. Manuscript, 1997.
	14	Robert Cypher , Friedhelm Meyer auf der Heide , Christian Scheideler , Berthold Vöcking, Universal algorithms for store-and-forward and wormhole routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.356-365, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237982]
	15	Shlomi Dolev , Evangelos Kranakis , Danny Krizanc , David Peleg, Bubbles: adaptive routing scheme for high-speed dynamic networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.528-537, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225270]
	16	Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
	17	Iris Gaber , Yishay Mansour, Broadcast in radio networks, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.577-585, January 22-24, 1995, San Francisco, California, United States
	18	R. Gallager. A perspective on multiaccess channels. IEEE Trans. Inform. Theory, Special Issue on Random Access Communications, 31, pp. 124-142, 1985.
	19	The Mobile Communications Handbook. J.D. Gibson (Ed.), CRC Press, 1996.
	20	F. K. Hwang, The time complexity of deterministic broadcast radio networks, Discrete Applied Mathematics, v.60 n.1-3, p.219-222, June 23, 1995 [doi>10.1016/0166-218X(94)00053-G]
	21	Mobile Computing, T. Imielinski, H. Korth (Eds.), Kluwer Academic Publishers, 1996.
	22	J.M. Jacobsmeyer. Congestion relief on power-controlled CDMA networks. IEEE J. Sel. Areas in Commun. 18(9), pp. 1758-1761, 1996.
	23	D.B. Johnson, D.A. Maltz. Protocols for adaptive wireless and mobile networking. IEEE Personal Comm. 3(1), 1996.
	24	C. Kaklamanis, A.R. Karlin, F.T. Leighton, V. Milenkovic, P. Raghavan, S.B. Rao, C. Thomborson, A. Trantilas. Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors. In Pwc. of the 1990 IEEE 31st Ann. Syrup. on Foundations o/ Computer Science, pp. 285-296, 1990.
	25	Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Power Consumption in Packet Radio Networks (Extended Abstract), Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, p.363-374, February 27-March 01, 1997
	26	Eyal Kushilevitz , Yishay Mansour, An Ω(D log(N/D)) lower bound for broadcast in radio networks, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.65-74, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164059]
	27	F.T. Leighton, B.M. Maggs, S.B. Rao. Universal packet routing algorithms. In Proc. o/ the 29th Ann. Syrup. on Foundations o} Computer Science, pp. 256-271, 1988.
	28	A. Myles, D.B. Johnson, C.E. Perkins. A mobile host protocol supporting route optimization and authentication. IEEE J. Sel. Areas in Commun., special issue on Mobile and Wireless Computing Networks, 13(5), pp. 839-349, 1995.
	29	C. Scheideler, Deterministic routing with bounded buffers: turning offline into online protocols, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.370, October 14-16, 1996
	30	P. Piret. On the connectivity of radio networks. IEEE Trans. on Inform. Theory 37(5), pp. 1490-1492, 1991.
	31	M.J. Post, P.E. Sarachik, A.S. Kershenbaum. A distributed evolutionary algorithm for reorganizing network communications. In Proc. IEEE MILCOM, 1985.
	32	Yuval Rabani , Éva Tardos, Distributed packet switching in arbitrary networks, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.366-375, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237983]
	33	P. Raghavan, Robust algorithms for packet routing in a mesh, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.344-350, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72972]
	34	Krishnamurthi Ravishankar , Suresh Singh, Asymptotically optimal gossiping in radio networks, Discrete Applied Mathematics, v.61 n.1, p.61-82, July 7, 1995 [doi>10.1016/0166-218X(93)E0176-Y]
	35	L.G. Roberts. Aloha Packet System with and without Slots and Capture, ASS Notes 8, Advanced Research Projects Agency, Network Information Center, Stanford Research Institute, Stanford, CA, 1972.
	36	A. Sen, M. Huson. A new model for scheduling packet radio networks. In Proc. of the 15th Ann. Joint Conf. o# the IEEE Computer and Communication Societies INFO- COM, pp. 1116-1124, 1996.
	37	S. Ulukus, R.D. Yates. Stochastic power control for cellular radio systems. Dept. of Electrical and Computer Engineering, Rutgers University, NJ. Submitted to IEEE Trans. Commun., September 1996.
	38	L.G. Valiant. A scheme for fast parallel communication. SIAM J. on Comput. 11(2), pp. 350-361, 1982.
	39	O. Weinstein. The wave expansion approach to broadcasting in multihop networks, M.Sc. Thesis, Computer Science Dept., Technion, Haifa, Israel, 1987.

CITED BY 14

	Andrzej Pelc, Broadcasting in radio networks, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
	Ioannis Chatzigiannakis , Sotiris Nikoletseas , Paul Spirakis, An efficient communication strategy for ad-hoc mobile networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.320-322, August 2001, Newport, Rhode Island, United States
	Kostas P. Hatzis , George P. Pentaris , Paul G. Spirakis , Vasilis T. Tampakas , Richard B. Tan, Fundamental control algorithms in mobile networks, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.251-260, June 27-30, 1999, Saint Malo, France
	Friedhelm Meyer auf de Heide , Christian Schindelhauer , Klaus Volbert , Matthias Grünewald, Energy, congestion and dilation in radio networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Ioannis Chatzigiannakis , Sotiris Nikoletseas , Paul Spirakis, Distributed communication algorithms for ad hoc mobile networks, Journal of Parallel and Distributed Computing, v.63 n.1, p.58-74, January 2003
	V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, End-to-end packet-scheduling in wireless ad-hoc networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Ioannis Chatzigiannakis , Sotiris Nikoletseas, Design and analysis of an efficient communication strategy for hierarchical and highly changing ad-hoc mobile networks, Mobile Networks and Applications, v.9 n.4, p.319-332, August 2004
	Klaus Volbert, Experimental analysis of adjustable sectorized topologies for static ad hoc networks: extended abstract, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA
	Christian Schindelhauer , Tamás Lukovszki , Stefan Rührup , Klaus Volbert, Worst case mobility in ad hoc networks, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002
	Ioannis Chatzigiannakis , Panagiotis Kokkinos , Christos Zaroliagis, Routing protocols for efficient communication in wireless ad-hoc networks, Proceedings of the 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networks, October 06-06, 2006, Terromolinos, Spain
	Andrea E. F. Clementi , Francesco Pasquale , Angelo Monti , Riccardo Silvestri, Communication in dynamic radio networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Andrea E. F. Clementi , Angelo Monti , Francesco Pasquale , Riccardo Silvestri, Broadcasting in dynamic radio networks, Journal of Computer and System Sciences, v.75 n.4, p.213-230, June, 2009
	Malika Boulkenafed , Valérie Issarny, A middleware service for mobile ad hoc data sharing, enhancing data availability, Proceedings of the ACM/IFIP/USENIX 2003 International Conference on Middleware, June 16-20, 2003, Rio de Janeiro, Brazil