Abstract
We present a timed broadcast process calculus for wireless networks at the MAC-sublayer where time-dependent communications are exposed to collisions. We define a reduction semantics for our calculus which leads to a contextual equivalence for comparing the external behaviour of wireless networks. Further, we construct an extensional LTS (labelled transition system) which models the activities of stations that can be directly observed by the external environment. Standard bisimulations in this novel LTS provide a sound proof method for proving that two systems are contextually equivalent. In addition, the main contribution of the paper is that our proof technique is also complete for a large class of systems.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., Cayirci, E.: Wireless sensor networks: a survey. Computer Networks 38(4), 393–422 (2002)
Borgström, J., Huang, S., Johansson, M., Raabjerg, P., Victor, B., Pohjola, J.Å., Parrow, J.: Broadcast psi-calculi with an application to wireless protocols. In: Barthe, G., Pardo, A., Schneider, G. (eds.) SEFM 2011. LNCS, vol. 7041, pp. 74–89. Springer, Heidelberg (2011)
Cerone, A., Hennessy, M.: Modelling probabilistic wireless networks (extended abstract). In: Giese, H., Rosu, G. (eds.) FORTE 2012 and FMOODS 2012. LNCS, vol. 7273, pp. 135–151. Springer, Heidelberg (2012), http://www.scss.tcd.ie/~ceronea/works/ProbabilisticWirelessNetworks.pdf
Cerone, A., Hennessy, M., Merro, M.: Modelling mac-layer communications in wireless systems. Technical Report, Trinity College Dublin (2012), https://www.scss.tcd.ie/~acerone/works/CCCP.pdf .
Ghassemi, F., Fokkink, W., Movaghar, A.: Equational reasoning on mobile ad hoc networks. Fundamenta Informaticae 105(4), 375–415 (2010)
Godskesen, J.C.: A Calculus for Mobile Ad Hoc Networks. In: Murphy, A.L., Vitek, J. (eds.) COORDINATION 2007. LNCS, vol. 4467, pp. 132–150. Springer, Heidelberg (2007)
Hennessy, M.: A distributed Pi-calculus. Cambridge University Press (2007)
Hennessy, M., Rathke, J.: Bisimulations for a calculus of broadcasting systems. TCS 200(1-2), 225–260 (1998)
Hennessy, M., Regan, T.: A process algebra for timed systems. IaC 117(2), 221–239 (1995)
Honda, K., Yoshida, N.: On reduction-based process semantics. TCS 152(2), 437–486 (1995)
Kouzapas, D., Philippou, A.: A process calculus for dynamic networks. In: Bruni, R., Dingel, J. (eds.) FORTE 2011 and FMOODS 2011. LNCS, vol. 6722, pp. 213–227. Springer, Heidelberg (2011)
Lanese, I., Sangiorgi, D.: An operational semantics for a calculus for wireless systems. TCS 411(19), 1928–1948 (2010)
Merro, M.: An Observational Theory for Mobile Ad Hoc Networks (full paper). IaC 207(2), 194–208 (2009)
Merro, M., Ballardin, F., Sibilio, E.: A timed calculus for wireless systems. TCS 412(47), 6585–6611 (2011)
Milner, R.: Communicating and Mobile Systems: The π-calculus. Cambridge University Press (1999)
Nanz, S., Hankin, C.: Static analysis of routing protocols for ad-hoc networks. In: ACM SIGPLAN and IFIP WG, vol. 1, pp. 141–152. Citeseer (2004)
Nicollin, X., Sifakis, J.: The algebra of timed processes, atp: Theory and application. IaC 114(1), 131–178 (1994)
Prasad, K.V.S.: A calculus of broadcasting systems. In: Sannella, D. (ed.) ESOP 1994. LNCS, vol. 788, pp. 285–327. Springer, Heidelberg (1994)
Rappaport, T.S.: Wireless communications - principles and practice. Prentice-Hall (1996)
Rathke, J., Sobocinski, P.: Deconstructing behavioural theories of mobility. In: Ausiello, G., Karhumäki, J., Mauri, G., Ong, L. (eds.) Fifth IFIP ICTCScience. IFIP, vol. 273, pp. 507–520. Springer, Boston (2008)
Sangiorgi, D., Walker, D.: The Pi-Calculus — A Theory of Mobile Processes. Cambridge University Press (2001)
Singh, A., Ramakrishnan, C.R., Smolka, S.A.: A process calculus for mobile ad hoc networks. SCP 75(6), 440–469 (2010)
Tanenbaum, A.S.: Computer Networks, 4th edn. Prentice-Hall International, Inc. (2003)
Wang, M., Lu, Y.: A timed calculus for mobile ad hoc networks. arXiv preprint arXiv:1301.0045 (2013)
Yi, W.: A Calculus of Real Time Systems. Ph.D Thesis, Chalmers University (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 IFIP International Federation for Information Processing
About this paper
Cite this paper
Cerone, A., Hennessy, M., Merro, M. (2013). Modelling MAC-Layer Communications in Wireless Systems. In: De Nicola, R., Julien, C. (eds) Coordination Models and Languages. COORDINATION 2013. Lecture Notes in Computer Science, vol 7890. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38493-6_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-38493-6_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38492-9
Online ISBN: 978-3-642-38493-6
eBook Packages: Computer ScienceComputer Science (R0)