Energy aware routing in wireless sensor networks

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.

Αυτή η διατριβή ασχολείται με μεγάλης κλίμακας, πολλά-προς-ένα Ασύρματα Δίκτυα Αισθητήρων και το πρόβλημα της εξισορρόπησης του φορτίου και της κατανάλωσης ενέργειας. Τα δίκτυα αυτά αποτελούνται από έναν μεγάλο αριθμό αισθητήρων-κόμβων, οι οποίοι καλύπτουν μια γεωγραφική περιοχή. Σκοπός του δικτύου είναι η συλλογή των μετρήσεων σε ένα σημείο του δικτύου, για παράδειγμα σε κάποιον σταθμό βάσης, επίσης γνωστό ως απορροφητή (sink). Λόγω των περιορισμένων πόρων, οι κόμβοι πρέπει να χρησιμοποιούν τους γείτονές τους προκειμένου να επιτύχουν την επιδιωκόμενη λειτουργικότητα. Αντί να μεταδίδουν απευθείας στον απορροφητή, κάτι το οποίο θα απαιτούσε ισχυρό ενισχυτή στη κεραία, μεταφέρουν τα δεδομένα από κόμβο σε κόμβο με την μέθοδο των πολλαπλών-βημάτων (multi-hop). Αν τα δεδομένα ταξιδεύουν ασυμπίεστα τότε οι κόμβοι πιο κοντά στον απορροφητή είναι υποχρεωμένοι να μεταδίδουν περισσότερα πακέτα απ' ότι οι πιο απομακρυσμένοι, γι' αυτό μένουν από ενέργεια πολύ σύντομα. Αυτό το θέμα είναι γνωστό ως ενεργειακή οπή (energy hole) και προκαλείται από την άνιση κατανομή του φορτίου λόγω αυξημένης κυκλοφορίας (traffic) ανάμεσα στις διαφορετικές περιοχές του δικτύου.Η έννοια του φορτίου είναι κομβικής σημασίας στα μεγάλης κλίμακας ασύρματα δίκτυα αισθητήρων, όπου οι κόμβοι συνήθως σκορπίζονται τυχαία, αφού η τοποθέτηση σε συγκεκριμένες θέσεις δεν είναι μια πρακτική επιλογή. Λόγω αυτής της τυχαιότητας είναι απαραίτητο να χρησιμοποιούμε μέσες τιμές για σχεδόν όλα τα μεγέθη του δικτύου, με το φορτίο να μην αποτελεί εξαίρεση. Όμως, ένας συνεπής ορισμός για το μέσο φορτίο δεν είναι προφανής, αφού το φορτίο του κάθε κόμβου και η θέση του είναι τυχαίες μεταβλητές. Η υπάρχουσα βιβλιογραφία παρακάμπτει την τυχαιότητα με το να υπολογίζει την μέση τιμή μεταξύ κόμβων που έτυχε να βρεθούν ο ένας κοντά στον άλλο, μέσα σε μικρές περιοχές. Αυτή η προσέγγιση είναι ανεπαρκής, επειδή η μέση τιμή φορτίου μιας επιφάνειας είναι και αυτή τυχαία μεταβλητή και επίσης δεν μας επιτρέπει να χειριστούμε μεμονωμένα σημεία. Αυτή η διατριβή παρέχει έναν ορισμό για την μέση τιμή του φορτίου μιας επιφάνειας, βασισμένη στο στατιστικό μέγεθος της αναμενόμενης τιμής, ενώ η μέση τιμή φορτίου ενός σημείου θεωρείται ως το φορτίο μιας επιφάνειας που μειώνεται (ή συρρικνώνεται) σ' αυτό το σημείο. Αυτοί οι νέοι ορισμοί εφαρμόζονται στην περίπτωση του φορτίου κυκλοφορίας (traffic load) στα δίκτυα πολλαπλών-βημάτων. Ένα ενδιαφέρον αποτέλεσμα δείχνει ότι το φορτίο κυκλοφορίας αυξάνεται σε βήματα. Η απλούστερη μορφή αυτού του αποτελέσματος είναι το σταθερό βήμα, το οποίο καταλήγει σε μια αναλυτική έκφραση για το φορτίο κυκλοφορίας. Μια σύγκριση με μερικά πραγματικά δίκτυα (μέσω προσομοιώσεων) δείχνει ότι τα περισσότερα απ' αυτά περιγράφονται με ακρίβεια από το μοντέλο σταθερού βήματος.Η άνιση κατανομή του φορτίου κυκλοφορίας είναι ένα φαινόμενο που εμφανίζεται σε πολλά επίπεδα. Εκτός από το γνωστό πρόβλημα της ενεργειακής οπής, δηλαδή, οι κόμβοι κοντά στον απορροφητή καταναλώνουν πολύ περισσότερη ενέργεια απ' ότι οι πιο απομακρυσμένοι, το οποίο μπορεί να θεωρηθεί ως μια καθολική διακύμανση του φορτίου, υπάρχει επίσης μία ακόμα πιο έντονη διακύμανση του φορτίου κυκλοφορίας ανάμεσα σε κόμβους με την ίδια απόσταση από τον απορροφητή, η οποία μπορεί να περιγραφεί ως μία τοπική διακύμανση του φορτίου. Αυτή η άνιση κατανομή του φορτίου, τόσο καθολικά όσο και τοπικά, έχει ως αποτέλεσμα τη πολύ μεγάλη μείωση του χρόνου μέχρι ο πρώτος κόμβος να μείνει χωρίς ενέργεια μπαταρίας. Αυτή η διατριβή προτείνει μία μέθοδο εξισορρόπησης του φορτίου των κόμβων που ισαπέχουν από τον απορροφητή, μοιράζοντας την κυκλοφορία κάθε κόμβου μεταξύ των κόμβων του επόμενου βήματος (next hop nodes). Τελικά τα πακέτα ταξιδεύουν από τον κάθε κόμβο προς τον απορροφητή ακολουθώντας πεπλεγμένες διαδρομές. Ο προτεινόμενος μηχανισμός δρομολόγησης, ο οποίος ονομάζεται δρομολόγηση πλεξούδα (braided routing), είναι απλός και μπορεί να εφαρμοστεί πάνω σε οποιαδήποτε δρομολόγηση βασισμένη σε κόστος, προκαλώντας ασήμαντη επιβάρυνση (overhead). Αποτελέσματα προσομοιώσεων δείχνουν ότι η τοπική διακύμανση του φορτίου μειώνεται κατά 20-60% κατά μέσο όρο, ενώ ο χρόνος μέχρι τον πρώτο θάνατο κόμβου μπορεί ακόμη και να διπλασιαστεί σε μερικές περιπτώσεις και ο χρόνος ζωής αυξάνεται κατά 15% περίπου. Δρομολόγηση προσανατολισμένη στην ενέργεια είναι ένα δύσκολο έργο, λόγω της ύπαρξης της ενεργειακής οπής. Λαμβάνοντας υπόψη την αδυναμία διαδρομής (path impotence), δηλαδή, μία μετρική βασισμένη στην απόσταση μετάδοσης και στο υπόλοιπο ενέργειας της μπαταρίας του κόμβου, προτείνεται σ' αυτή την εργασία μία προσαρμοζόμενη δρομολόγηση η οποία επιτρέπει τους κόμβους να επιλέγουν διαφορετικό πατρικό κόμβο για να προωθήσουν τα πακέτα δεδομένων τους προς τον απορροφητή. Μια μεγάλη διαφορά από τις συμβατικές προσεγγίσεις είναι ότι η αδυναμία διαδρομής καθορίζεται από τον πιο αδύναμο κόμβο, αντί για το άθροισμα της μετρικής κατά μήκος της διαδρομής. Λόγω αυτού του τρόπου υπολογισμού η προτεινόμενη πολιτική διαδίδει τις τιμές της αδυναμίας διαδρομής σε όλο το δίκτυο πολύ αποδοτικά, με μικρό επιπλέον κόστος μηνυμάτων (για παράδειγμα δεν χρειάζεται συνεχώς κατασκευή δέντρων δρομολόγησης). Το πλήθος των μεταδιδόμενων μηνυμάτων (δηλαδή, η επιβάρυνση) διερευνάται αναλυτικά σ' αυτήν την διατριβή και επιπλέον δείχνεται αναλυτικά ότι δεν μπορούν να υπάρξουν αδιέξοδα. Αποτελέσματα προσομοιώσεων χρησιμοποιούνται για να αξιολογήσουν την προτεινόμενη πολιτική σε σχέση με άλλες οκτώ παρόμοιες πολιτικές που εμφανίζονται στην βιβλιογραφία. Αποδεικνύεται ότι όταν η επιβάρυνση λαμβάνεται υπόψη (για παράδειγμα, η ενέργεια που καταναλώνεται όταν μεταδίδεται ένα μήνυμα, παρόμοια με την μετάδοση των πακέτων δεδομένων), τότε η προτεινόμενη πολιτική αποδίδει καλύτερα από τις άλλες πολιτικές, κάτω από συγκεκριμένες συνθήκες σχετικά με το μέγεθος των μηνυμάτων συγκριτικά με το μέγεθος των πακέτων δεδομένων.