Abstract
A simple model of multi-hop communication in ad-hoc networks is considered. Similar models are often adopted for studying energy efficiency and load balancing of different routing protocols. We address an orthogonal question never considered by the networking community: whether, regardless of specific protocols, two networks may be considered as equivalent from the viewpoint of the communication service they provide. In particular, we consider equivalent two networks with identical maximum and minimum inhibiting flow, and prove that this notion of equivalence coincides with a standard trace-based notion of equivalence borrowed from the theory of concurrency. We finally study the computational complexity of the proposed equivalence and discuss possible alternatives.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aceto, L., Fokkink, W., Verhoef, C.: Structural operational semantics. In: Bergstra, J., Ponse, A., Smolka, S. (eds.) Handobook of Process Algebra, pp. 197–292. North-Holland, Amsterdam (2001)
Ahuja, R., Magnanti, T., Orlin, J.: Network Flows, theory, algorithms, and applications. Prentice-Hall, New Jersey (1993)
Akkaya, K., Younis, M.F.: A survey on routing protocols for wireless sensor networks. Ad Hoc Networks 3(3), 325–349 (2005)
Akyildiz, I., Su, W., Sankarasubramaniam, Y., Cayirci, E.: A survey on sensor networks. IEEE Communications Magazine 40(8), 102–116 (2002)
Borgström, J., Nestmann, U., Alima, L.O., Gurov, D.: Verifying a structured peer-to-peer overlay network: The static case. In: Priami, C., Quaglia, P. (eds.) GC 2004. LNCS, vol. 3267, pp. 250–265. Springer, Heidelberg (2005)
Boukerche, A. (ed.): Algorithms and Protocols for Wireless Sensor Networks. Wiley-IEEE press (2008)
Cenciarelli, P., Gorla, D., Tuosto, E.: Network applications of graph bisimulation. In: Ehrig, H., Heckel, R., Rozenberg, G., Taentzer, G. (eds.) ICGT 2008. LNCS, vol. 5214, pp. 131–146. Springer, Heidelberg (2008)
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge (1990)
Fehnker, A., McIver, A.: Formal techniques for the analysis of wireless networks. In: 2nd International Symposium on Leveraging of Formal Maethods, Verification and Validation (IEEE-ISOLA), pp. 263–270. IEEE Press, New York (2006)
Ganjali, Y., Keshavarzian, A.: Load balancing in ad hoc networks: single-path routing vs. multi-path routing. In: INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, pp. 1120–1125. IEEE press, New York (2004)
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)
Kanellakis, P., Smolka, S.: CCS Expressions, Finite State Processes and Three Problems of Equivalence. Information and Conputation 86(1), 43–68 (1990)
Merro, M.: An observational theory for mobile ad hoc networks. In: Proc. of MFPS, ENTCS, vol. 173, pp. 275–293 (2007)
Merro, M., Sibilio, E.: A timed calculus for wireless networks. In: Proc. of FSEN (to appear, 2009)
Mezzetti, N., Sangiorgi, D.: Towards a calculus for wireless systems. In: Proc. of MFPS, ENTCS, vol. 158, pp. 331–353 (2006)
Milner, R.: Communication and Concurrency. Prentice Hall, New Jersey (1989)
Nanz, S., Hankin, C.: A framework for security analysis of mobile wireless networks. Theoretical Computer Science 367(1-2), 203–227 (2006)
Nehra, N., Patel, R.B., Bhat, V.K.: Routing with load balancing in ad hoc network: A mobile agent approach. In: 6th IEEE/ACIS International Conference on Computer and Information Science, pp. 489–495 (2007)
Park, D.: Concurrency and automata on infinite sequences. In: Deussen, P. (ed.) GI-TCS 1981. LNCS, vol. 104, pp. 167–183. Springer, Heidelberg (1981)
Phillips, C.A.: The network inhibition problem. In: Proc. of STOC, pp. 776–785. ACM Press, New York (1993)
Roughgarden, T.: On the severity of braess’s paradox: Designing networks for selfish users is hard. Journal of Computer and System Science 72(5), 922–953 (2006)
Singh, A., Ramakrishnan, C., Smolka, S.A.: A process calculus for mobile ad hoc networks. In: Lea, D., Zavattaro, G. (eds.) COORDINATION 2008. LNCS, vol. 5052, pp. 296–314. Springer, Heidelberg (2008)
Stockmeyer, L., Meyer, A.: Word Problems Requiring Exponential Time. In: Proc. of 5th Symp. on Theory of Computing (STOC), pp. 1–9. ACM Press, New York (1973)
Toh, C.: Ad Hoc Mobile Wireless Networks: Protocols and Systems. Prentice Hall, New Jersey (2002)
Tonguz, O.K., Ferrari, G.: Ad Hoc Wireless Networks: A Communication-Theoretic Perspective. John Wiley & Sons, Chichester (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cenciarelli, P., Gorla, D., Salvo, I. (2009). Depletable Channels: Dynamics and Behaviour. In: Kutyłowski, M., Charatonik, W., Gębala, M. (eds) Fundamentals of Computation Theory. FCT 2009. Lecture Notes in Computer Science, vol 5699. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03409-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-03409-1_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03408-4
Online ISBN: 978-3-642-03409-1
eBook Packages: Computer ScienceComputer Science (R0)