A survey of routing techniques for mobile communications networks

ABSTRACT

Mobile wireless networks pose interesting challenges for routing system design. To produce feasible routes in a mobile wireless network, a routing system must be able to accommodate roving users, changing network topology, and fluctuat- ing link quality. We discuss the impact of node mobility and wireless communication on routing system design, and we survey the set of techniques employed in or proposed for routing in mobile wireless networks.

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	Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
	2	V.H. MacDonald, The cellular concept, The Bell Syst. Tech. J. 44 (1965) 547-588.
	3	W.R. Young, Advanced mobile phone service: introduction, background, and objectives, The Bell Syst. Tech. J. 58 (1979) 1- 14.
	4	D. Cox, Wireless network access for personal communications, IEEE Commun. (December 1992) 96-115.
	5	Telecommunications Industry Association, Mobile station-base station compatibility standard for dual-mode wideband spread spectrum cellular system, TIA/EIAIS-95 (July 1993).
	6	ETSI, Digital european cordless telephone common interface, version 05.03 (May 1991).
	7	Radio Advisory Board of Canada, CT2Plus class 2: specification for the canadian common air interface for digital cordless telephony, including public access services, annex 1 to radio standards specification 120 (1992).
	8	John W. Ketchum, Routing in cellular mobile radio communications networks, Routing in communications networks, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
	9	Arif Merchant , Bhaskar Sengupta, Assignment of cells to switches in PCS networks, IEEE/ACM Transactions on Networking (TON), v.3 n.5, p.521-526, Oct. 1995 [doi>10.1109/90.469954]
	10	R.S. Kahn, J. Gronemeyer, J. Burchfiel and R. Kunzelman, Advances in packet radio technology, Proc. IEEE 66(11) (1978) 1468-1496.
	11	J. Jubin and J.D. Tornow, The DARPA packet radio network protocols, Proc. IEEE 75(1) (1987) 21-32.
	12	N. Shacham and J. Westcott, Future directions in packet radio architectures and protocols, Proc. IEEE75(1) (1987) 83-99.
	13	B. Leiner, D. Nielson and F. Tobagi, Issues in packet radio network design, Proc. IEEE 75(1) (1987) 6-20.
	14	Gregory S. Lauer, Packet-radio routing, Routing in communications networks, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
	15	Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
	16	W. Diepstraten, G. Ennis and P. Berlanger, DFWMAC: distributed foundation wireless medium access control, IEEE Document P802.11-93/190 (November 1993).
	17	A. Ephremedis, J.E. Wieselthier and D.J. Baker, A design concept for reliable mobile radio networks with frequency hopping signalling, Proc. IEEE 75(1) (1987) 56-73.
	18	Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
	19	C. R. Lin , M. Gerla, Multimedia transport in multihop dynamic packet radio networks, Proceedings of the 1995 International Conference on Network Protocols, p.209, November 07-10, 1995
	20	G. Lauer, Hierarchical routing design for SURAN, Proc. ICC (1986) pp. 93-101.
	21	J.L. Grubb, The traveller's dream come true, IEEE Commun. 29(11) (1991) 48-51.
	22	R.J. Leopold, Low-earth orbit global cellular communications network, Mobile Satellite Comm. Conf. , Adelaide, Australia (1990).
	23	R. Binder et al., Crosslink architectures for a multiple satellite system, Proc. IEEE 75(1) (1987) 74-82.
	24	J. Kaniyil et al., ``A global message network employing low earth-oribiting datellites, IEEE J. Select. Areas Commun. 10(2) (1992) 418-427.
	25	Upamanyu Madhow , Michael L. Honig , Kenneth Steiglitz, Optimization of wireless resources for personal communications mobility tracking, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.698-707, Dec. 1995 [doi>10.1109/90.477716]
	26	Michel Mouly , Marie-Bernadette Pautet , Thomas Haug, The GSM System for Mobile Communications, Telecom Publishing, 1992
	27	Telecommunications Industry Association, Cellular radiotelecommunication intersystem operation, TIA/EIA IS- 41B(1991).
	28	S. Mohan and R. Jain, Two user location strategies for personal communications services, IEEE Personal Commun. (First Quarter 1994) 42-50.
	29	J. G. Markoulidakis , G. L. Lyberopoulos , D. F. Tsirkas , E. D. Sykas, Evaluation of location area planning scenarios in future mobile telecommunication systems, Wireless Networks, v.1 n.1, p.17-29, Feb. 1995 [doi>10.1007/BF01196255]
	30	A. Bar-Noy and I. Kessler, Tracking mobile users in wireless communication networks, IEEE Trans. Inform. Theory 39(6) (1993) 1877-1886.
	31	H. Xie, S. Tabbane and D.J. Goodman, Dynamic location area management and performance analysis, Proc. 43rd IEEE Vehicular Tech. Conf. (1993) pp. 536-539.
	32	Yitzhak Birk , Yaron Nachman, Using direction and elapsed-time information to reduce the wireless cost of locating mobile units in cellular networks, Wireless Networks, v.1 n.4, p.403-412, 1995 [doi>10.1007/BF01985753]
	33	Amotz Bar-Noy , Ilan Kessler , Moshe Sidi, Mobile users: to update or not to update?, Wireless Networks, v.1 n.2, p.175-185, 1995 [doi>10.1007/BF01202540]
	34	Christopher Rose , Roy Yates, Minimizing the average cost of paging under delay constraints, Wireless Networks, v.1 n.2, p.211-219, 1995 [doi>10.1007/BF01202543]
	35	Ian F. Akyildiz , Joseph S. M. Ho, A mobile user location update and paging mechanism under delay constraints, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.244-255, August 28-September 01, 1995, Cambridge, Massachusetts, United States
	36	IETF Mobile-IP Working Group, IPv4 mobility support, working draft (1995).
	37	Ameritech Mobile Communications, Inc., Bell Atlantic Mobile Systems, Contel Cellular, Inc., GTE Mobile Communications, Inc., McCaw Cellular Communications, Inc., NYNEX Mobile Communications, Inc., PacTel Cellular, and Southwestern Bell Mobile Systems, Cellular digital packet data system specification (1993).
	38	K. Meier-Hellstern and E. Alonso, The use of SS7 and GSM to support high density personal communications, Proc. ICC (1992) pp. 1698-1702.
	39	V.N. Lo, R.S. Wolff and R.C. Bernhardt, Expected network database transaction volume to support personal communications services, 1st Int. Conf. Universal Personal Communications Services , Dallas, TX (1992).
	40	R. Jain, Y.-B. Lin, C. Lo and S. Mohan, A caching strategy to reduce network impacts of PCS, IEEE J. Select. Areas Commun. 12(8) (1994) 1434-1444.
	41	Joseph S. M. Ho , Ian F. Akyildiz, Local anchor scheme for reducing location tracking costs in PCNs, Proceedings of the 1st annual international conference on Mobile computing and networking, p.181-193, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215573]
	42	Baruch Awerbuch , David Peleg, Concurrent online tracking of mobile users, Proceedings of the conference on Communications architecture & protocols, p.221-233, September 03-06, 1991, Zurich, Switzerland
	43	V. Anantharam , M. L. Honig , U. Madhow , V. K. Wei, Optimization of a database hierarchy for mobility tracking in a personal communications network, Performance Evaluation, v.20 n.1-3, p.287-300, May 1994
	44	B.R. Badrinath, T. Imielinski and A. Virmani, Locating strategies for personal communication networks, Proc. Workshop on Networking of Personal Communications Applications (1992).
	45	M. Tamer Ozsu , P. Valduriez, Principles of distributed database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
	46	Lawrence W. Dowdy , Derrell V. Foster, Comparative Models of the File Assignment Problem, ACM Computing Surveys (CSUR), v.14 n.2, p.287-313, June 1982 [doi>10.1145/356876.356883]
	47	Narayanan Shivakumar , Jennifer Widom, User profile replication for faster location lookup in mobile environments, Proceedings of the 1st annual international conference on Mobile computing and networking, p.161-169, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215570]
	48	J. Postel, Internet protocol, Internet RFC791 (1981).
	49	David B. Johnson, Scalable support for transparent mobile host internetworking, Wireless Networks, v.1 n.3, p.311-321, 1995 [doi>10.1007/BF01200849]
	50	R. Droms, Dynamic host configuration protocol, Internet RFC 1541 (1993).
	51	Charles E. Perkins , Kevin Luo, Using DHCP with computers that move0, Wireless Networks, v.1 n.3, p.341-353, 1995 [doi>10.1007/BF01200851]
	52	D.B. Johnson and C. Perkins, Route optimization in Mobile IP, working draft (1996).
	53	G. Lauer, Address servers in hierarchical networks, Proc. ICC (1988) pp. 443-451.
	54	T.-C. Hou and V.O.K. Li, Position updates and sensitivity analysis for routing protocols in mobile packet radio networks, Proc. IEEEGLOBECOM (1985) pp. 243-249..
	55	B.W. Parkinson and S.W. Gilbert, NAVSTAR: global positioning system - ten years later, Proc. IEEE 71(10) (1983) 1177-1186.
	56	M. Rahnema, Overview of the GSM system and protocol architecture, IEEE Commun. (April 1993) 92-100.
	57	Bellcore, Generic criteria for version 1.0 wireless access communications systems (WACS) and supplement, Bellcore Technical Reference TR-INS-001313 1 (1993).
	58	Telecommunications Industry Association, Cellular system dual mode mobile station-base station compatibility standard, TIA/ EIAIS-54B (1992).
	59	Gregory P. Pollini , Kathleen S. Meier-Hellstern, Efficient routing of information between interconnected cellular mobile switching centers, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.765-774, Dec. 1995 [doi>10.1109/90.477722]
	60	Y.B. Lin, S. Mohan and A. Noerpel, PCS channel assignment strategies for hand-off and initial access, IEEE Personal Commun. (Third Quarter 1994) 47-56.
	61	S. Tekinary and B. Jabbari, Handover policies and channel assignment strategies in mobile cellular networks, IEEE Commun. 9(11) (1991) 42-46.
	62	S. Tekinary and B. Jabbari, A measurement based prioritization scheme for handovers in cellular and microcellular networks, IEEEJ. Select. Areas Commun. 10(8) (1992) 1343-1350.
	63	Y.-B. Lin, A. Noerpel and D.A. Harasty, Non-blocking channel assignment strategy for handoffs, Proc. IEEE 3rd Int. Conf. on Universal Personal Communications Services , San Diego, CA (1994).
	64	E. Buitenwerf et al., UMTS: fixed network issues and design options, IEEE Personal Commun. (February 1995) 30-37.
	65	M. Schwartz, Network management and control issues in multimedia wireless networks, IEEE Personal Commun. (June 1995) 8-16.
	66	Bala Rajagopalan, Mobility management in integrated wireless-ATM networks, Proceedings of the 1st annual international conference on Mobile computing and networking, p.127-141, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215566]
	67	M. Veeraraghavan , T. F. La Porta , R. Ramjee, A distributed control strategy for wireless ATM networks, Wireless Networks, v.1 n.3, p.323-339, 1995 [doi>10.1007/BF01200850]
	68	K. Y. Eng , M. J. Karol , M. Veeraraghavan , E. Ayanoglu , C. B. Woodworth , P. Pancha , R. A. Valenzuela, A wireless broadband ad-hoc ATM local-area network, Wireless Networks, v.1 n.2, p.161-174, 1995 [doi>10.1007/BF01202539]
	69	R. Cohen et al., The sink tree paradigm: connectionless traffic support on ATMLANs, Proc. IEEE INFOCOM (1994) pp. 821- 828.
	70	R. Mishra and M. Srivastava, Call establishment and rerouting in mobile computing networks, AT&T Technical Memo 11384- 940906-13TM(1994).
	71	Kam Lee, Adaptive network support for mobile multimedia, Proceedings of the 1st annual international conference on Mobile computing and networking, p.62-74, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215557]
	72	A.S. Acampora and M. Naghshineh, An architecture and methodology for mobile-executed handoff in cellular ATM networks, IEEE J. Select. Areas Commun. 12(8) (1994) 1365- 1375.
	73	A. Acampora and M. Nagshineh, Control and quality-of-service provisioning in high-speed microcellular networks, IEEE Personal Commun. (Second Quarter 1994) 36-43.
	74	David A. Levine , Ian F. Akyildiz , Mahmoud Naghshineh, The shadow cluster concept for resource allocation and call admission in ATM-based wireless networks, Proceedings of the 1st annual international conference on Mobile computing and networking, p.142-150, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215565]
	75	Fumio Teraoka , Yasuhiko Yokore , Mario Tokoro, A network architecture providing host migration transparency, Proceedings of the conference on Communications architecture & protocols, p.209-220, September 03-06, 1991, Zurich, Switzerland
	76	Hari Balakrishnan , Srinivasan Seshan , Randy H. Katz, Improving reliable transport and handoff performance in cellular wireless networks, Wireless Networks, v.1 n.4, p.469-481, 1995 [doi>10.1007/BF01985757]
	77	E.N. Gilbert and H.O. Pollack, Steiner minimal trees, SIAM J. Appl. Math. 16 (1968) 1-29.
	78	Baruch Awerbuch , Yossi Azar, Competitive multicast routing, Wireless Networks, v.1 n.1, p.107-114, Feb. 1995 [doi>10.1007/BF01196262]
	79	J.E. Wieselthier, C.M. Barnhart and A. Ephremides, A neural network approach to routing without interference in multihop radio networks, IEEE Trans. Commun. 42(1) (1994) 166-177.
	80	Abdelfettah Belghith , Leonard Kleinrock, A distributed routing scheme with mobility handling in stationless multi-hop packet radio networks, Proceedings of the symposium on Communications Architectures & Protocols, March 08-09, 1983, Austin, Texas
	81	M.B. Pursley and H.B. Russell, Routing in frequency-hop packet radio networks with partialband jamming, IEEE Trans. Commun. 41(7) (1993) 1117-1124.
	82	L.R. Ford Jr. and D.R. Fulkerson, Flows in Networks (Princeton University Press, Princeton, NJ, 1962).
	83	D. Beyer et al., Packet radio network research, development and application, Proc. SHAPEPacket Radio Symposium (1989).
	84	J. Stevens, Spatial reuse through dynamic power and routing control in common-channel random-access packet radio networks, SURAN Program Technical Note (SRNTN) 59 (1988). Available from the Defense Technical Information Center.
	85	R. Nelson and L. Kleinrock, The spatial capacity of a slotted ALOHA multihop packet radio network with capture, IEEE Trans. Commun. COM-32(6) (1984) 684-694.
	86	T.C. Hou and V.O.K. Li, Performance analysis of routing strategies in multihop packet radio networks, Proc. IEEE GLOBECOM (1984) pp. 487-492.
	87	T.C. Hou and V.O.K. Li, Transmission range control in multihop packet radio networks, IEEE Trans. Commun. COM- 34(1) (1986) 38-44.
	88	L. Kleinrock and J.A. Silvester, Optimum transmission radii for packet radio networks of why six is a magic number, Proc. National Telecommunications Conference (1978) pp. 4.3.1.-4.3.5.
	89	H. Takagi and L. Kleinrock, Optimal transmission ranges for randomly distributed packet radio terminals, IEEE Trans. Commun. 32(3) (1984) 246-257.
	90	M. Scott Corson , Anthony Ephremides, A distributed routing algorithm for mobile wireless networks, Wireless Networks, v.1 n.1, p.61-81, Feb. 1995 [doi>10.1007/BF01196259]
	91	K. Brayer, Packet switching for mobile earth stations via loworbit satellite network, Proc. IEEE72(11) (1994) 1627-1636.
	92	R.P. Lippmann, New routing and preemption algorithms for circuit-switched mixed media networks, Proc. of IEEEMILCOM (1985) pp. 660-666.
	93	E.M. Gafni and D.P. Bertsekas, Distributed algorithms for generating loop-free routes in networks with frequently changing topology, IEEE Trans. Commun. COM-29(1) (1981) 11-18.
	94	M.B. Pursley and H.B. Russell, Network protocols for frequency-hop packet radios with decoder sided information, IEEE J. Select. Areas Commun. 12(4) (1994) 612-621.
	95	I. Kleinrock and F. Kamoun, Hierarchical routing for large networks, Computer Networks 1 (1977) 155-174.
	96	W. T. Tsai , C. V. Ramamoorthy , W. K. Tsai , O. Nishiguchi, An Adaptive Hierarchical Routing Protocol, IEEE Transactions on Computers, v.38 n.8, p.1059-1075, August 1989 [doi>10.1109/12.30862]