Abstract
Future fog data networks are expected to be assisted by users cooperation and coding schemes. Given the finite I/O access bandwidth of the drives in the data servers and the explosive increase in the end users’ demand for download of the content from the servers, in this paper, we consider the implementation of instantly decodable network coding (IDNC) in full-duplex device-to-device (D2D) enabled cooperative distributed data networks. In particular, this paper is concerned with optimizing D2D communications with efficiently coded transmissions such that we offload traffic from the expensive backhaul of network servers. Previous works implementing IDNC have not focused on a cooperative architecture, therefore a new theoretical-graph model is proposed and the optimal problem formulation is presented. However, as the optimal solution suffers from the intractability of being NP-hard, it is not suitable for real-time communications. The complexity of the problem is addressed by presenting a greedy heuristic algorithm used over the proposed graph model. The paper shows that by implementing IDNC in a full-duplex cooperative D2D network model significant reduction in the number of downloads required from the servers can be achieved, which will result in saving valuable servers’ resources.
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
Similar content being viewed by others
Notes
- 1.
This first phase of the transmission is known as the initial transmission phase. During the initial transmission the servers will attempt to serve all files to the users in the network. However, some users will have received only a portion of the files requested due to channel erasure.
- 2.
A clique is a sub-set of the graph, where every distinct pair of vertices in the induced subgraph are pairwise adjacent. A maximal clique is one that cannot be a subset of a larger clique [4].
- 3.
An independent set is a set of vertices in a graph, no two of which are adjacent. A maximal independent set is an independent set that is not a subset of any other independent set [4].
- 4.
The degree of a vertex (\(\delta \)) in a graph is equal to the number of incident edges to that vertex [4].
References
Ahlswede, R., Cai, N., Li, S.-Y.R., Yeung, R.W.: Network information flow. IEEE Trans. Inf. Theory 46(4), 1204–1216 (2000)
Al-Habob, A.A., Sorour, S., Aboutorab, N., Sadeghi, P.: Conflict free network coding for distributed storage networks. In: 2015 IEEE International Conference on Communications (ICC), pp. 5517–5522. IEEE (2015)
Baran, P.: On distributed communications networks. IEEE Trans. Commun. Syst. 12(1), 1–9 (1964)
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications, vol. 290. Macmillan, London (1976)
Bonomi, F., Milito, R., Zhu, J., Addepalli, S.: Fog computing and its role in the internet of things. In: Proceedings of 1st Edition of the MCC Workshop on Mobile Cloud Computing, pp. 13–16. ACM (2012)
Cisco: Cisco visual networking index: global mobile data traffic forecast update. Technical report, February 2016
Dimakis, A.G., Godfrey, P.B., Wu, Y., Wainwright, M.J., Ramchandran, K.: Network coding for distributed storage systems. IEEE Trans. Inf. Theory 56(9), 4539–4551 (2010)
Dimakis, A.G., Ramachandran, K., Wu, Y., Suh, C.: A survey on network codes for distributed storage. Proc. IEEE 99(3), 476–489 (2011)
Edwards, C.S., Elphick, C.H.: Lower bounds for the clique and the chromatic numbers of a graph. Discret. Appl. Math. 5(1), 51–64 (1983)
Golrezaei, N., Molisch, A., Dimakis, A.G., Caire, G.: Femtocaching and device-to-device collaboration: a new architecture for wireless video distribution. IEEE Commun. Mag. 51(4), 142–149 (2013)
Papailiopoulos, D.S., Luo, J., Dimakis, A.G., Huang, C., Li, J.: Simple regenerating codes: network coding for cloud storage. In: 2012 Proceedings of IEEE INFOCOM, pp. 2801–2805. IEEE (2012)
Shanmugam, K., Golrezaei, N., Dimakis, A.G., Molisch, A., Caire, G.: FemtoCaching: wireless content delivery through distributed caching helpers. IEEE Trans. Inf. Theory 59(12), 8402–8413 (2013)
Sorour, S., Valaee, S.: On minimizing broadcast completion delay for instantly decodable network coding. In: 2010 IEEE International Conference on Communications (ICC), pp. 1–5. IEEE (2010)
Sorour, S., Valaee, S.: An adaptive network coded retransmission scheme for single-hop wireless multicast broadcast services. IEEE/ACM Trans. Netw. (TON) 19(3), 869–878 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Quinton, B., Aboutorab, N. (2018). Offloading of Fog Data Networks with Network Coded Cooperative D2D Communications. In: Hu, J., Khalil, I., Tari, Z., Wen, S. (eds) Mobile Networks and Management. MONAMI 2017. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 235. Springer, Cham. https://doi.org/10.1007/978-3-319-90775-8_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-90775-8_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-90774-1
Online ISBN: 978-3-319-90775-8
eBook Packages: Computer ScienceComputer Science (R0)