Information Dissemination and Dominating Sets on Wireless Sensor Networks (bibtex)

by Konstantinos Skiadopoulos

Abstract:

Over the last decades, a large number of Wireless Sensor Networks have been deve- loped to monitor the conditions in the places where they are installed. Networks of this kind are constantly being installed, which due to functional requirements and technological advancements have an increased number of nodes. The amount of the produced data is enormous, and the collection and transmission of them centrally requires the use of innovative methods. In this thesis, two methods are proposed to address the problem of information dissemination in WSNs, that is, the transmission of data to and from the nodes of these networks. The first proposed method is based on the use of random walkers. Initially an in-depth original analysis of the performance of using one random walker to cover a WSN is presented. The result of this analysis is an analytic relation of the network coverage as a function of the time required, expressed as the number of random walker's hops. This analysis is supported by extensive simulations on various network models as well as its application to an experimental wireless network installed in Ionian University's buildings. The conclusion of this analysis is that the use of one random walker for the dissemination of information in WSNs achieves its goal with a low burden on the network's energy resources, which is a critical factor for their operation. The disadvantage of this method is the relatively long time for the completion of the process. Next, the use of multiple random walkers acting simultaneously is considered, in order to reduce the time required for the network coverage compared to the use of one random walker. The performance analysis of the use of multiple random walkers presented, is based on the results of the aforementioned analysis of the use of one random walker. The network coverage is initially examined, resulting a function of the time required for a given number of random walkers operating simultaneously on the network, in a detailed analytical form. This analytical form proved to beconsistent with a previously published work, which addresses the same issue for complete graphs. Then an analysis of the performance of multiple random walkers with Replication Mechanism is presented. Finally, an analytical form is derived, that enables the calculation of the number of random walkers needed for the coverage of a percentage of the network's nodes in a given time interval. All the analytical results are supported by extensive simulations on various network models as well as by their experimental application to the Ionian University Experimental Wireless Network. The second proposed method is based on the use of connected dominating sets. Connected Dominating Sets can ensure that all nodes in a network will either belong to them or they are at least a certain number of hops away from at least one node of them. This creates a backbone that facilitates the Dissemination of Information to and from the nodes of the network to which they belong. Initially, a distributed two-phase algorithm is proposed, which creates a d-hop connected dominating set. During the first phase, the network nodes collect the required topology information and during the second phase, starting from a network node, a d-hop Connected Dominating Set is created. The proposed algorithm is examined analytically for its correctness, the number of messages needed for the execution, and the processing and termination time. The algorithm's performance is compared through simulations with the performance of a centralized algorithm and with that of a relatively recently proposed distributed one. The result of the comparison is that the performance of the proposed algorithm is similar to that of the centralized one, in terms of the size of the produced set, and it significantly outperforms the distributed one in terms of both the size of the produced set and of the number of required messages. The number of required messages is a critical parameter for algorithms that run on WSNs because they consume the network's energy resources. Finally, a variation of the proposed algorithm that generates budget limited Connected Dominating Sets is presented. These are Connected Dominating Sets with an upper bound as to their size and are of great practical utility. This algorithm is supported by simulations that compare its performance with that of the main algorithm of this thesis. Both algorithms are also applied to simulations based on data drawn from an open database for New York City taxis traffic. The conclusion is that the production of budget limited Connected Dominating Sets, achieves results similar to those of the main algorithm, consuming lower computational resources.

Reference:

Konstantinos Skiadopoulos, "Information Dissemination and Dominating Sets on Wireless Sensor Networks", Ph.D. Thesis, Ionian University, 2019.

Bibtex Entry:

@phdthesis{skiadopoulos2019thesis, Abstract = {Over the last decades, a large number of Wireless Sensor Networks have been deve- loped to monitor the conditions in the places where they are installed. Networks of this kind are constantly being installed, which due to functional requirements and technological advancements have an increased number of nodes. The amount of the produced data is enormous, and the collection and transmission of them centrally requires the use of innovative methods. In this thesis, two methods are proposed to address the problem of information dissemination in WSNs, that is, the transmission of data to and from the nodes of these networks. The first proposed method is based on the use of random walkers. Initially an in-depth original analysis of the performance of using one random walker to cover a WSN is presented. The result of this analysis is an analytic relation of the network coverage as a function of the time required, expressed as the number of random walker's hops. This analysis is supported by extensive simulations on various network models as well as its application to an experimental wireless network installed in Ionian University's buildings. The conclusion of this analysis is that the use of one random walker for the dissemination of information in WSNs achieves its goal with a low burden on the network's energy resources, which is a critical factor for their operation. The disadvantage of this method is the relatively long time for the completion of the process. Next, the use of multiple random walkers acting simultaneously is considered, in order to reduce the time required for the network coverage compared to the use of one random walker. The performance analysis of the use of multiple random walkers presented, is based on the results of the aforementioned analysis of the use of one random walker. The network coverage is initially examined, resulting a function of the time required for a given number of random walkers operating simultaneously on the network, in a detailed analytical form. This analytical form proved to beconsistent with a previously published work, which addresses the same issue for complete graphs. Then an analysis of the performance of multiple random walkers with Replication Mechanism is presented. Finally, an analytical form is derived, that enables the calculation of the number of random walkers needed for the coverage of a percentage of the network's nodes in a given time interval. All the analytical results are supported by extensive simulations on various network models as well as by their experimental application to the Ionian University Experimental Wireless Network. The second proposed method is based on the use of connected dominating sets. Connected Dominating Sets can ensure that all nodes in a network will either belong to them or they are at least a certain number of hops away from at least one node of them. This creates a backbone that facilitates the Dissemination of Information to and from the nodes of the network to which they belong. Initially, a distributed two-phase algorithm is proposed, which creates a d-hop connected dominating set. During the first phase, the network nodes collect the required topology information and during the second phase, starting from a network node, a d-hop Connected Dominating Set is created. The proposed algorithm is examined analytically for its correctness, the number of messages needed for the execution, and the processing and termination time. The algorithm's performance is compared through simulations with the performance of a centralized algorithm and with that of a relatively recently proposed distributed one. The result of the comparison is that the performance of the proposed algorithm is similar to that of the centralized one, in terms of the size of the produced set, and it significantly outperforms the distributed one in terms of both the size of the produced set and of the number of required messages. The number of required messages is a critical parameter for algorithms that run on WSNs because they consume the network's energy resources. Finally, a variation of the proposed algorithm that generates budget limited Connected Dominating Sets is presented. These are Connected Dominating Sets with an upper bound as to their size and are of great practical utility. This algorithm is supported by simulations that compare its performance with that of the main algorithm of this thesis. Both algorithms are also applied to simulations based on data drawn from an open database for New York City taxis traffic. The conclusion is that the production of budget limited Connected Dominating Sets, achieves results similar to those of the main algorithm, consuming lower computational resources.}, Author = {Skiadopoulos, Konstantinos}, Date-Modified = {2020-01-27 23:16:10 +0200}, Keywords = {stphdthesis,olinet}, Month = {December}, Note = {Text in greek}, School = {Ionian University}, Title = {{{Information Dissemination and Dominating Sets on Wireless Sensor Networks}}}, Type = {{Ph.D. Thesis}}, Year = {2019}}

Powered by bibtexbrowser