Abstract
A new single channel, time division multiple access (TDMA)-based broadcast scheduling protocol, termed the Five-Phase Reservation Protocol (FPRP), is presented for mobile ad hoc networks. The protocol jointly and simultaneously performs the tasks of channel access and node broadcast scheduling. The protocol allows nodes to make reservations within TDMA broadcast schedules. It employs a contention-based mechanism with which nodes compete with each other to acquire TDMA slots. The FPRP is free of the “hidden terminal” problem, and is designed such that reservations can be made quickly and efficiently with negligible probability of conflict. It is fully-distributed and parallel (a reservation is made through a localized conversation between nodes in a 2-hop neighborhood), and is thus scalable. A “multihop ALOHA” policy is developed to support the FPRP. This policy uses a multihop, pseudo-Bayesian algorithm to calculate contention probabilities and enable faster convergence of the reservation procedure. The performance of the protocol, measured in terms of scheduling quality, scheduling overhead and robustness in the presence of nodal mobility, has been studied via simulations. The results showed that the protocol works very well in all three aspects. Some future work and applications are also discussed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
European Telecommunications Standards Institute, Radio Equipment and Systems (RES): HIgh PErformance Radio Local Area Network (HIPERLAN), Type 1 Functional Specification, draft pr ETS 300 652 edition (December 1995).
Institute of Electrical and Electronics Engineers, IEEE P802.11 Draft Standard for Wireless LAN: Medium Access Control (MAC) and Physical Layer (PHY) Specification, draft p802.11d5.0 edition (July 1996).
M. Post, A. Kershenbaum and P. Sarachik, A distributed evolutionary algorithm for reorganizing network communications, in: Proc. of MILCOM (1985) pp. 133-139.
L.C. Pond and V.O.K. Li, A distributed time-slot assignment protocol for mobile multi-hop broadcast packet radio networks, in: Proc. of IEEE MILCOM (1989) pp. 70-74.
R. Ramaswami and K.K. Parhi, Distributed scheduling of broadcast in a radio network, in: Proc. of IEEE INFOCOM (1989) pp. 497-504.
A. Ephremides and T. Truong, Scheduling broadcasts in multihop radio networks, IEEE Transactions on Communications 38(4) (April 1990) 456-460.
A. Bhatnagar and T. Robertazzi, Layer net: A new self-organizing network protocol, in: Proc. of MILCOM (1990) pp. 845-850.
S. Ramanathan and E.L. Lloyd, Scheduling algorithms for multihop radio networks, IEEE/ACM Transactions on Networking 1 (1993) 166-177.
I. Cidon and M. Sidi, Distributed assignment algorithms for multihop packet radio networks, IEEE Transactions on Computers 38 (1989) 1353-1361.
N. Funabiki and Y. Takefuji, A parallel algorithm for broadcast scheduling problem in packet radio networks, IEEE Transactions on Communications 41 (1993) 828-831.
S. Ramanathan, A unified framework and algorithm for (T/F/C)DMA channel assignment in wireless networks, in: Proc. of INFOCOM, Kobe, Japan (April 1997).
A. Sen and M. Huson, A new model for scheduling packet radio networks, in: Proc. of INFOCOM (1996).
X. Ma and E.L. Lloyd, An incremental algorithm for broadcast scheduling in packet radio networks, in: Proc. of MILCOM (1998).
I. Chlamtac and A. Farago, Making transmission schedules immune to topology changes in multi-hop packet radio networks, IEEE/ACM Transactions on Networking 2 (1994) 23-29.
A. Farago, I. Chlamtac and H. Zhang, Time-spread multiple-access (tsma) protocols for multihop mobile radio networks, IEEE/ACM Transactions on Networking 5 (1997) 804-812.
J.-H. Ju and V.O.K. Li, An optimal topology-transparent scheduling method in multihop packet radio networks, IEEE/ACM Transactions on Networking 6 (1998) 298-306.
C. Zhu and M.S. Corson, A five phase reservation protocol (FPRP) for mobile ad hoc networks, in: Proc. of IEEE INFOCOM (1998).
F.A. Tobagi and L. Kleinrock, Packet switching in radio channels: part ii — the hidden terminal problem in carrier sense, multiple access modes and the busy tone solution, IEEE Transactions on Communications 23(12) (December 1975) 1417-1433.
C. Fullmer and J.J. Garcia-Luna-Aceves, Floor acquistion multiple access (FAMA) for packet-radio networks, in: Proc. of ACM SIGCOMM (1995).
K. Joseph, N.D. Wilson, R. Ganesh and D. Raychaudhuri, Packet CDMA versus dynamic TDMA for multiple access in an integrated voice/data pcn, IEEE Journal of Selected Areas in Communications 11 (1993) 870-884.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completenes (Freeman, New York, NY, 1979).
D. Bertsekas and R. Gallager, Data Networks, 2nd ed. (Prentice-Hall, Englewood Cliffs, NJ, 1992).
R.L. Rivest, Network control by Bayesian broadcast, Report MIT/LCS/TM-287, MIT, Laboratory for Computer Science, Cambridge, MA (1985).
J. Broch, D.A. Maltz, D.B. Johnson, Y.-C. Hu and J. Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, in: Proc. of MOBICOM (1998) pp. 85-97.
NAVSTAR GPS User Equipment Introduction, Department of Defense Document MZ10298.001 (February 1991).
L.F. Chang and S. Ariyavisitakul, Performance of a CDMA radio communications system with feed-back power control and multipath dispersion, in: Proc. of IEEE GLOBECOM (1991) pp. 1017-1021.
C. Zhu and M.S. Corson, An evolutionary-TDMA scheduling protocol (E-TDMA) for mobile ad hoc networks, in: Proc. of Advanced Telecommunications and Information Distribution Research Program (ATIRP) (March 2000).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Zhu, C., Corson, M. A Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks. Wireless Networks 7, 371–384 (2001). https://doi.org/10.1023/A:1016683928786
Issue Date:
DOI: https://doi.org/10.1023/A:1016683928786