Abstract
Opportunistic networks (ON) are particular types of delay-tolerant networks in which users/network entities participate in order to propagate information. Besides the advantages of these networks (e.g. decentralization, independence of communication infrastructure) they raise new problems regarding for example effectiveness, message routing, message delivery, security issues, and trust. In this paper we introduce a formal description of an ON and of optimal communication topologies, for the non-cooperative and cooperative settings. We follow a game theoretic approach and allow users to express properties about how their messages should be handled in the network by means of a logical language (for instance, message privacy may be achieved by requiring that network nodes with internet access should be avoided on the communication path). We determine the complexity of associated verification and synthesis problems of network topologies.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Becchetti, L., Clementi, A.E.F., Pasquale, F., Resta, G., Santi, P., Silvestri, R.: Information spreading in opportunistic networks is fast. CoRR abs/1107.5241 (2011)
Clarke, E., Emerson, E.: Design and Synthesis of Synchronization Skeletons Using Branching Time Temporal Logic. In: Engeler, E. (ed.) Logic of Programs 1979. LNCS, vol. 125, pp. 52–71. Springer, Heidelberg (1981)
Fall, K.: A delay-tolerant network architecture for challenged internets. In: Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM 2003, pp. 27–34. ACM, New York (2003), http://doi.acm.org/10.1145/863955.863960
Felegyhazi, M., Hubaux, J.P., Buttyan, L.: Nash equilibria of packet forwarding strategies in wireless ad hoc networks. IEEE Transactions on Mobile Computing 5(5), 463–476 (2006), http://dx.doi.org/10.1109/TMC.2006.68
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, San Francisco (1979)
Gottlob, G., Greco, G., Scarcello, F.: Pure nash equilibria: hard and easy games. Journal of Artificial Intelligence Research, 215–230 (2003)
Han, B., Hui, P., Kumar, V.A., Marathe, M.V., Shao, J., Srinivasan, A.: Mobile data offloading through opportunistic communications and social participation. IEEE Transactions on Mobile Computing 99 (PrePrints) (2011)
Hui, P., Crowcroft, J., Yoneki, E.: Bubble rap: social-based forwarding in delay tolerant networks. In: Proceedings of the 9th ACM International Symposium on Mobile ad Hoc Networking and Computing, MobiHoc 2008, pp. 241–250. ACM, New York (2008), http://doi.acm.org/10.1145/1374618.1374652
Jain, S., Demmer, M., Patra, R., Fall, K.: Using redundancy to cope with failures in a delay tolerant network. SIGCOMM Comput. Commun. Rev. 35, 109–120 (2005), http://doi.acm.org/10.1145/1090191.1080106
Lilien, L., Kamal, Z., Bhuse, V., Gupta, A.: The concept of opportunistic networks and their research challenges in privacy and security. In: Makki, S., Reiher, P., Makki, K., Pissinou, N., Makki, S. (eds.) Mobile and Wireless Network Security and Privacy, pp. 85–117. Springer US (2007), http://dx.doi.org/10.1007/978-0-387-71058-7_5
Pal, R., Kosta, S., Hui, P.: Settling for less – a qos compromise mechanism for opportunistic mobile networks. In: Proceeding of the Thirteenth Workshop on MAthematical Performance Modeling and Analysis, MAMA (2011)
Pelusi, L., Passarella, A., Conti, M.: Opportunistic Networking: Data Forwarding in Disconnected Mobile Ad Hoc Networks. IEEE Communications Magazine 44(11), 134–141 (2006), http://dx.doi.org/10.1109/MCOM.2006.248176
Zhong, S., Li, L.E., Liu, Y.G., Yang, Y.R.: On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretic and cryptographic techniques. Wirel. Netw. 13(6), 799–816 (2007), http://dx.doi.org/10.1007/s11276-006-9855-1
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bulling, N., Köster, M., Popovici, M. (2012). A Game Theoretic Approach for Optimal Network Topologies in Opportunistic Networks. In: Fisher, M., van der Torre, L., Dastani, M., Governatori, G. (eds) Computational Logic in Multi-Agent Systems. CLIMA 2012. Lecture Notes in Computer Science(), vol 7486. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32897-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-32897-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32896-1
Online ISBN: 978-3-642-32897-8
eBook Packages: Computer ScienceComputer Science (R0)