by Apostolos Demertzis
Abstract:
This thesis focuses on large-scale, many-to-one Wireless Sensor Networks (WSNs) and how to balance traffic load and consequently energy consumption. They consist of a large number of small and inexpensive sensor nodes that are spread over a large geographical area. The purpose of this network type is to deliver the sensed data to a single point, e.g., some sort of a base station, also known as sink. Due to their limited resources, nodes have to rely on their neighbors in order to provide the intended functionality. Instead of transmitting directly to the sink, which would require a powerful antenna amplifier, they transfer the sensed data from node to node in a multi-hop manner. If data are traveling uncompressed then nodes closer to the sink have to transfer many more packets than the distant ones, therefore, they run out of energy quickly. This issue is known as energy hole problem and it is caused by the uneven distribution of traffic load among the different network areas. Load is a key magnitude in large-scale WSNs, where nodes are usually spread at random, since deliberate positioning is not a practical approach. Due to this randomness it is necessary to use average values for almost all networks' magnitudes, load being no exception. However, a consistent definition for the average load is not obvious, since both nodal load and position are random variables. Current literature circumvents randomness by computing the average value over nodes that happen to fall near to each other, i.e., within small areas. This approach is insufficient, because the small area's average is still a random variable and also it does not permit us to deal with single points. This thesis provides a definition for the area's average load, based on the statistical expected value, whereas a point's average load is seen as the load of an area that has been reduced (or contracted) to that point. These new definitions are applied in the case of traffic load in multi-hop networks. An interesting result shows that traffic load increases in steps. The simplest form of this result is the constant step, which results in an analytical expression for the traffic load. A comparison with some real-world networks (by means of simulations) shows that most of them are accurately described by the constant step model. Uneven distribution of traffic load is a multi-layer phenomenon. Apart from the well-known energy hole problem, i.e., nodes close to the sink consume much more energy than distant ones, which can be seen as the global variation of load, there is also an even more acute variation of traffic load among nodes with the same distance from the sink, which can be described as the local variation of load. This uneven distribution of traffic load, both globally and locally, results in a severe shortening of the time until first node runs out of battery. This thesis proposes a method for balancing the load of nodes that are equally-distant from the sink, by sharing each one's traffic among its next-hop neighbors. Eventually, packets are traveling from each node to the sink by following interlaced paths. The proposed routing mechanism, called braided routing, is a simple one and can be applied over any cost-based routing, incurring a negligible overhead. Simulation results show that the local variance of load is reduced nearly 20-60\% on average while the time until first death can be prolonged more than twice in many cases and the lifetime is increased about 15\%. Energy-aware routing in WSNs is a challenging task due to the energy hole problem. Taking into account path impotence, i.e., a metric based on the transmission distance and the energy left at the nodes' batteries, an adjustable routing policy is proposed here that allows nodes to choose different parent nodes for forwarding their data packets toward the sink node. A major difference from the conventional approaches is that path impotence is determined by the most impotent node, instead of adding up the metric along the path. Due to this difference, the proposed policy propagates path impotence values throughout the network efficiently, with reduced extra control messages (e.g., no need to continuously reconstruct routing trees). The number of messages sent by the particular policy (i.e., overhead) is analytically investigated here and, in addition, it is analytically shown that no deadlocks are possible. Simulation results are used for evaluating the proposed policy against other eight similar policies that appear in the literature. It is demonstrated that when the introduced overhead is taken into account (e.g., energy is consumed when transmitting messages similarly to data packet transmissions), the proposed policy outperforms the other policies under certain conditions, related to the size of the message compared to the size of data packets.
Reference:
Apostolos Demertzis, "Energy-Aware Routing in Wireless Sensor Networks", Ph.D. Thesis, Ionian University, 2019.
Bibtex Entry:
@phdthesis{demertzis2019thesis,
abstract = {This thesis focuses on large-scale, many-to-one Wireless Sensor Networks (WSNs) and how to balance traffic load and consequently energy consumption. They consist of a large number of small and inexpensive sensor nodes that are spread over a large geographical area. The purpose of this network type is to deliver the sensed data to a single point, e.g., some sort of a base station, also known as sink. Due to their limited resources, nodes have to rely on their neighbors in order to provide the intended functionality. Instead of transmitting directly to the sink, which would require a powerful antenna amplifier, they transfer the sensed data from node to node in a multi-hop manner. If data are traveling uncompressed then nodes closer to the sink have to transfer many more packets than the distant ones, therefore, they run out of energy quickly. This issue is known as energy hole problem and it is caused by the uneven distribution of traffic load among the different network areas.
Load is a key magnitude in large-scale WSNs, where nodes are usually spread at random, since deliberate positioning is not a practical approach. Due to this randomness it is necessary to use average values for almost all networks' magnitudes, load being no exception. However, a consistent definition for the average load is not obvious, since both nodal load and position are random variables. Current literature circumvents randomness by computing the average value over nodes that happen to fall near to each other, i.e., within small areas. This approach is insufficient, because the small area's average is still a random variable and also it does not permit us to deal with single points. This thesis provides a definition for the area's average load, based on the statistical expected value, whereas a point's average load is seen as the load of an area that has been reduced (or contracted) to that point. These new definitions are applied in the case of traffic load in multi-hop networks. An interesting result shows that traffic load increases in steps. The simplest form of this result is the constant step, which results in an analytical expression for the traffic
load. A comparison with some real-world networks (by means of simulations) shows that most of them are accurately described by the constant step model.
Uneven distribution of traffic load is a multi-layer phenomenon. Apart from the well-known energy hole problem, i.e., nodes close to the sink consume much more energy than distant ones, which can be seen as the global variation of load, there is also an even more acute variation of traffic load among nodes with the same distance from the sink, which can be described as the local variation of load. This uneven distribution of traffic load, both globally and locally, results in a severe shortening of the time until first node runs out of battery. This thesis proposes a method for balancing the load of nodes that are equally-distant from the sink, by sharing each one's traffic among its next-hop neighbors. Eventually, packets are traveling from each node to the sink by following interlaced paths. The proposed routing mechanism, called braided routing, is a simple one and can be applied over any cost-based routing, incurring a negligible overhead. Simulation results show that the local variance of load is reduced nearly 20-60\% on average while the time until first death can be prolonged more than twice in many cases and the lifetime is increased about 15\%.
Energy-aware routing in WSNs is a challenging task due to the energy hole problem. Taking into account path impotence, i.e., a metric based on the transmission distance and the energy left at the nodes' batteries, an adjustable routing policy is proposed here that allows nodes to choose different parent nodes for forwarding their data packets toward the sink node. A major difference from the conventional approaches is that path impotence is determined by the most impotent node, instead of adding up the metric along the path. Due to this difference, the proposed policy propagates path impotence values throughout the network efficiently, with reduced extra control messages (e.g., no need to continuously reconstruct routing trees). The number of messages sent by the particular policy (i.e., overhead) is analytically investigated here and, in addition, it is analytically shown that no deadlocks are possible. Simulation results are used for evaluating the proposed policy against other eight similar policies that appear in the literature. It is demonstrated that when the introduced overhead is taken into account (e.g., energy is consumed when transmitting messages similarly to data packet transmissions), the proposed policy outperforms the other policies under certain conditions, related to the size of the message compared to the size of data packets.},
author = {Demertzis, Apostolos},
date-modified = {2021-11-13 20:43:30 +0200},
keywords = {stphdthesis,olinet, R:ENERGY:LR},
month = {6},
school = {Ionian University},
title = {{{Energy-Aware Routing in Wireless Sensor Networks}}},
type = {{{Ph.D. Thesis}}},
year = {2019}}