Abstract
A MAC protocol specifies how nodes in a sensor network access a shared communication channel. Desired properties of a MAC protocol are: it should be contention-free (avoid collisions); it should be distributed and self-stabilize to topological changes in the network; topological changes should be contained, namely, affect only the nodes in the vicinity of the change; it should not assume that nodes have a global time reference, that is, nodes may not be time-synchronized. We give a set of TDMA-based MAC protocols for asynchronous wireless sensor networks satisfying all of these requirements. The communication complexity, number and size of messages, for the protocols to stabilize is small, poly-logarithmic in the network size.
Similar content being viewed by others
References
Abramson N. (1970). The ALOHA system—another alternative for computer communications. Proceedings of AFIPS Conf. 37: 295–298
Akyildiz I., Su W., Sankarasubramaniam Y. and Cayirci E. (2002). A survey on sensor networks. IEEE Commun. Mag. 40(8): 102–114
Ammar, M.H., Stevens, D.S.: A distributed TDMA rescheduling procedure for mobile packet radio networks. In: Proceedings of IEEE International Conference on Communications (ICC), pp. 1609–1613, Denver, CO, June (1991)
Arisha, K.A., Youssef, M.A., Younis, M.F.: Energy-aware TDMA-based MAC for Sensor Networks. IEEE Workshop on Integrated Management of Power Aware Communications, Computing and Networking (IMPACCT 2002), New York City, New York, May 2002
Arumugam, M., Kulkarni, S.S.: Self-stabilizing deterministic TDMA for sensor networks. In: Proceedings of the Second International Conference on Distributed Computing and Internet Technology (ICDCIT), LNCS 3816, pp. 69–81, Bhubaneswar, India, December 22–24 (2005)
Arvind K. (1994). Probabilistic clock synchronization in distributed systems. IEEE Trans. Parallel Distrib. Syst. 5(5): 474–487
Cerpa, A., Estrin, D.: ASCENT: adaptive self-configuring sensor network topologies. In: Proceedings of INFOCOM’02 (2002)
Chen, B., Jamieson, K., Balakrishnan, H., Morris, R.: Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. In: Proceedings of ACM International Conference on Mobile Computing and Networking (MOBICOM’01) (2001)
Chlamtac, I., Franta, W.R., Levin, K.: BRAM: The broadcast recognizing access method. IEEE Trans. Commun. 27(8) (1979)
Cidon I. and Sidi M. (1989). Distributed assignment algorithms for multihop packet radio networks. IEEE Trans. Comput. 38(10): 1353–1361
Crane R. (2003). Propagation Handbook for Wireless Communication System Design. CRC Press LLC, Boca Raton
ElBatt, T., Ephremides, A.: Joint scheduling and power control for wireless ad hoc networks. In: IEEE Computer and Communications Conference (INFOCOM), June 2002
Farber, D., Feldman, J., Heinrich, F.R., Hopwood, M.D., Larson, K.C., Loomis, D.C., Rowe, L.A.: The distributed computing system. In: Proceedings of IEEE COMPCON, pp. 31–34, San Francisco, CA, February 1973
Gupta P. and KumarP.R. (1998). Critical power for asymptotic connectivity in wireless networks. In: McEneany, W.M., Yin, G. and Zhang, Q. (eds) Stochastic Analysis, Control, Optimization and Applications, A Volume in Honor of W.H. Fleming, pp 547–566. Birkhauser, Basel
Herman, T., Tixeuil, S.: A distributed TDMA slot assignment algorithm for wireless sensor networks. ALGOSENSORS, pp. 45–58 (2004)
Magdon-Ismail, M., Sivrikaya, F., Yener, B.: Problem of Power Optimal Connectivity and Coverage in Wireless Sensor Networks. ACM Wireless Networks (in press)
Kalidindi, R., Ray, L., Kannan, R., Iyengar, S.S.: Distributed energy-aware MAC protocol for wireless sensor networks. In: International Conference on Wireless Networks, Las Vegas, Nevada, June 2003
Kannan R., Kalidindi R., Iyengar S.S. and Kumar V. (2003). Energy and rate based MAC protocol for wireless sensor networks. ACM SIGMOD Record 32(4): 60–65
Kleinrock L. and Scholl M.O. (1980). Packet switching in radio channels: new conflict-free multiple access schemes. IEEE Trans. Commun. 28(7): 1015–1029
Kleinrock L. and Tobagi F.A. (1975). Packet switching in radio channels: Part I—Carrier sense multiple-access modes and their throughput-delay characteristics. IEEE Trans. Commun. 23(12): 1400–1416
Martin J. (1978). Communication Satellite Systems. Prentice Hall, New Jersey
McCormick S.T. (1983). Optimal approximation of sparse hessians and its equivalence to a graph coloring problem. Math. Programm. 26: 153–171
Monks, J.P., Bharghavan, V., Hwu, W.: A power controlled multiple access protocol for wireless packet networks. In: Proceedings of the IEEE INFOCOM 2001, Anchorage, Alaska, April, 2001
Moscibroda, T., Wattenhofer, R.: Coloring unstructured radio networks. In: 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Las Vegas, Nevada, USA, July 2005
Moscibroda, T., Wattenhofer, R.: Maximal independent sets in radio networks. In: 24th ACM Symposium on the Principles of Distributed Computing (PODC), Las Vegas, Nevada, USA, July 2005
Muqattash A., Krunz, M.: Power controlled dual channel (PCDC) medium access protocol for wireless ad hoc networks. In: Proceedings of the IEEE INFOCOM 2003 Conference, San Francisco, April 2003
Muqattash, A., Krunz, M.: CDMA-based MAC protocol for wireless ad hoc networks. In: Proceedings of the ACM MobiHoc 2003 Conference, Annapolis, Maryland, June 2003
Nelson R. and Kleinrock L. (1985). Spatial TDMA: a collision free multihop channel access protocol. IEEE Trans. Commun. 33(9): 934–944
OPNET Technologies Inc., http://www.opnet.com/
Rajendran, V., Obraczka, K., Garcia-Luna-Aceves, J.J.: Energy-efficient, collision-free medium access control for wireless sensor networks. In: Proceedings of ACM SenSys’03, pp. 181–192 (2003)
Roberts, L.G.: ALOHA packet system with and without slots and capture. Comput. Commun. Rev. 5(2), (1975)
Singh, S., Raghavendra, C.S.: Power efficient MAC protocol for multihop radio networks. In: Nineth IEEE International Personal, Indoor and Mobile Radio Communications Conference (PIMRC’98), pp. 153–157 (1998)
Sohrabi, K., Pottie, G.: Performance of a novel self-organization protocol for wireless ad-hoc sensor networks. In: IEEE Vehicular Technology Conference, Amsterdam, The Netherlands, (1999)
Tobagi F. and Kleinrock L. (1977). Packet switching in radio channels: Part IV—Stability considerations and dynamic control in carrier sense multiple-access. IEEE Trans. Commun. 25(10): 1103–1119
Truong, T.V.: TDMA in mobile radio networks: an assessment of certain approaches. In: Proceedings of IEEE GLOBECOM, pp. 504–507. Atlanta, GA, November, 1984
Viterbi A.J. (1995). CDMA: Principles of Spread Spectrum Communication. Addison-Wesley, Reading
Woo, A., Culler, D.: A transmission control scheme for media access in sensor networks. In: Proceedings of Mobicom 2001, pp. 221–235
Wu S.L., Tseng Y.C. and Sheu J.P. (2000). Intelligent medium access for mobile ad hoc networks with busy tones and power control. IEEE J. Selected Areas Commun. (JSAC) 18(9): 1647–1657
Xu, Y., Heidemann, J., Estrin, D.: Geography-informed energy conservation for ad hoc routing. In: Proceedings of ACM International Conference on Mobile Computing and Networking (MOBICOM’01) (2001)
Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. IEEE standards 802.11, January 1997
Ye W., Heidemann J. and Estrin D. (2004). Medium access control with coordinated, adaptive sleeping for wireless sensor networks. IEEE/ACM Trans. Networking 12(3): 493–506
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of the paper appears in the Proceedings of the 18th Annual Conference on Distributed Computing (DISC 2004), LNCS 3704, pp 245–259, Trippenhuis, Amsterdam, The Netherlands, October 2004.
Rights and permissions
About this article
Cite this article
Busch, C., Magdon-Ismail, M., Sivrikaya, F. et al. Contention-free MAC protocols for asynchronous wireless sensor networks. Distrib. Comput. 21, 23–42 (2008). https://doi.org/10.1007/s00446-007-0053-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00446-007-0053-x