Information Dissemination in Structured and Unstructured Networks (bibtex)
by George Koufoudakis
Abstract:
Recent technological advances like the fifth generation mobile phone system (5G), cloud/fog computing are expected to support numerous applications and wide de- ployment of network devices (e.g., Internet of Things, Wireless Sensor Networks), that is forecasted to reach 25 billion devices by 2020. The expected increment in human-type and machine-type communications introduce a wide variety of communication characteristics with different requirements regarding data rate, latency, mobility and reliability. In such environments, several applications and services that are available in different network locations, regularly need to disseminate information for various purposes like data collection or to reveal useful features (e.g., sink node location, routing information, service and resource discovery, discovery of network functions, etc). Consequently, information dissemination mechanisms need to be adapted in order to meet certain requirements (e.g., guarantee low-latency, save valuable network resources, etc). Blind flooding, one of the simplest broadcast mechanisms proposed in the literature, is suitable for the wired, small scale network paradigm of the early '80s and capable of reaching all network nodes in a deterministic manner. However, it requires a large amount of usually redundant messages in the network thus, consuming network resources (e.g., energy, bandwidth etc). An increasing volume of research attention has been observed recently regarding probabilistic flooding. Probabilistic flooding can be seen as a suitable alternative for pruning transmissions by employing some fixed probability for message forwarding among neighbor nodes. The basic idea is to employ small values for the previously mentioned forwarding probability in order to reduce message transmissions that would not result in coverage increment (i.e., the percentage of nodes that have received the information message). Due to its probabilistic nature, probabilistic flooding cannot deterministically provide a global outreach, rather it guarantees it with high probability. This thesis revisits probabilistic flooding adopting elements from algebraic graph theory. More specifically, probabilistic flooding is modeled in order to obtain an analytical expression of the coverage in the form of a polynomial. The largest roots of this polynomial are shown to be a satisfactory approximation of the threshold probability (i.e., the minimum value of the forwarding probability that allows for global outreach with high probability). Moreover, the polynomial's roots are also used to confirm existing results in literature, and --based on certain observations-- a novel algorithm is proposed for the estimation of the threshold probability. Subsequently, the coverage polynomial is further analyzed and fundamental properties of probabilistic flooding --not covered in the literature-- are revealed. In partic- ular, the previously mentioned polynomial is further studied, and a new polynomial that depends on the largest eigenvalue and the principal eigenvector of the network's adjacency matrix is derived. Furthermore, analytical expressions regarding (i) coverage; (ii) a lower bound of the forwarding probability allowing for global network outreach; and (iii) a lower bound of the termination time are also derived. It is shown that threshold probability is inversely proportional to the largest eigenvalue of the network's adjacency matrix and the probability of a node to receive the information message is proportional to the eigenvector centrality of the initiator node and itself for large values of time t. Based on the analytical results, a new probabilistic flooding policy, i.e., m-Probabilistic Flooding is proposed and it is shown that the requirements for global outreach are independent of the underlying network's spectral properties. The results of the analysis that took place in the context of this thesis can be applied to the newly emerging environment for information dissemination purposes. As shown by the simulation results, the analytical findings capture the behavior of probabilistic flooding and they have given a way to study such problems in modern wireless network environments, by employing elements of algebraic graph theory.
Reference:
George Koufoudakis, "Information Dissemination in Structured and Unstructured Networks", Ph.D. Thesis, Ionian University, 2019.
Bibtex Entry:
@phdthesis{koufoudakis2019thesis,
	Abstract = {Recent technological advances like the fifth generation mobile phone system (5G), cloud/fog computing are expected to support numerous applications and wide de- ployment of network devices (e.g., Internet of Things, Wireless Sensor Networks), that is forecasted to reach 25 billion devices by 2020. The expected increment in human-type and machine-type communications introduce a wide variety of communication characteristics with different requirements regarding data rate, latency, mobility and reliability. In such environments, several applications and services that are available in different network locations, regularly need to disseminate information for various purposes like data collection or to reveal useful features (e.g., sink node location, routing information, service and resource discovery, discovery of network functions, etc). Consequently, information dissemination mechanisms need to be adapted in order to meet certain requirements (e.g., guarantee low-latency, save valuable network resources, etc).
	Blind flooding, one of the simplest broadcast mechanisms proposed in the literature, is suitable for the wired, small scale network paradigm of the early '80s and capable of reaching all network nodes in a deterministic manner. However, it requires a large amount of usually redundant messages in the network thus, consuming network resources (e.g., energy, bandwidth etc).
	An increasing volume of research attention has been observed recently regarding probabilistic flooding. Probabilistic flooding can be seen as a suitable alternative for pruning transmissions by employing some fixed probability for message forwarding among neighbor nodes. The basic idea is to employ small values for the previously mentioned forwarding probability in order to reduce message transmissions that would not result in coverage increment (i.e., the percentage of nodes that have received the information message). Due to its probabilistic nature, probabilistic flooding cannot deterministically provide a global outreach, rather it guarantees it
	with high probability.
	This thesis revisits probabilistic flooding adopting elements from algebraic graph
	theory. More specifically, probabilistic flooding is modeled in order to obtain an analytical expression of the coverage in the form of a polynomial. The largest roots of this polynomial are shown to be a satisfactory approximation of the threshold probability (i.e., the minimum value of the forwarding probability that allows for global outreach with high probability). Moreover, the polynomial's roots are also used to confirm existing results in literature, and --based on certain observations-- a novel algorithm is proposed for the estimation of the threshold probability.
	Subsequently, the coverage polynomial is further analyzed and fundamental properties of probabilistic flooding --not covered in the literature-- are revealed. In partic- ular, the previously mentioned polynomial is further studied, and a new polynomial that depends on the largest eigenvalue and the principal eigenvector of the network's adjacency matrix is derived. Furthermore, analytical expressions regarding (i) coverage; (ii) a lower bound of the forwarding probability allowing for global network outreach; and (iii) a lower bound of the termination time are also derived. It is shown that threshold probability is inversely proportional to the largest eigenvalue of the network's adjacency matrix and the probability of a node to receive the information message is proportional to the eigenvector centrality of the initiator node and itself for large values of time t. Based on the analytical results, a new probabilistic flooding policy, i.e., m-Probabilistic Flooding is proposed and it is shown that the requirements for global outreach are independent of the underlying network's spectral properties.
	The results of the analysis that took place in the context of this thesis can be applied to the newly emerging environment for information dissemination purposes. As shown by the simulation results, the analytical findings capture the behavior of probabilistic flooding and they have given a way to study such problems in modern wireless network environments, by employing elements of algebraic graph theory.},
	Author = {Koufoudakis, George},
	Date-Modified = {2020-01-27 23:15:48 +0200},
	Keywords = {stphdthesis,olinet},
	Month = {February},
	School = {Ionian University},
	Title = {{{Information Dissemination in Structured and Unstructured Networks}}},
	Type = {{Ph.D. Thesis}},
	Year = {2019}}
Powered by bibtexbrowser