Nature-inspired congestion control and avoidance in wireless sensor networks

Abstract

Ο στόχος της διατριβής είναι να διερευνήσει τεχνικές εμπνευσμένες από τη φύση στο πλαίσιο του ελέγχου συμφόρησης σε ασύρματα δίκτυα αισθητήρων, αντλώντας έμπνευση από τη νοημοσύνη σμήνους καθώς επίσης από μαθηματικά μοντέλα πληθυσμού που απαντώνται στη βιολογία. Δύο καινοτόμες, εμπνευσμένες από τη φύση, προσεγγίσεις ελέγχου και αποφυγής συμφόρησης προτείνονται που αποσκοπούν στη βελτίωση της επίδοσης, ιδίως όσον αφορά στο ποσοστό παράδοσης πακέτων, στη καθυστέρηση από άκρο σε άκρο και στην κατανάλωση ενέργειας σε μια ευρεία γκάμα εφαρμογών στα δίκτυα αισθητήρων. Και οι δύο προτεινόμενες προσεγγίσεις αναπτύχθηκαν στη βάση μηχανισμών που υπάρχουν στη φύση και παρουσιάζουν επιθυμητές ιδιότητες όπως αυτό-οργάνωση, αυτό-προσαρμοστικότητα και ευρωστία σε συνθήκες σφαλμάτων. Αυτές οι ιδιότητες δεν προγραμματίζονται ρητά στα δίκτυο αισθητήρων, αλλά προκύπτουν ως αποτέλεσμα της συλλογικής συμπεριφοράς μεταξύ των αλληλεπιδρώντων οντοτήτων. Επιπλέον, οι προτεινόμενες προσεγγίσεις είναι απλές στην υλοποίηση, εμπλέκουν ελάχιστη ανταλλαγή πληροφοριών και παρουσιάζουν πολύ καλή συμπεριφορά σε χαμηλή, μέση και υψηλή κίνηση πακέτων. Η πρώτη προσέγγιση (Flock-CC) στοχεύει σε εφαρμογές που δημιουργούν κίνηση δεδομένων έπειτα από την ανίχνευση κάποιου συμβάντος και υιοθετεί ένα μοντέλο νοημοσύνης σμήνους εμπνευσμένο από την συμπεριφορά των πουλιών για αποφυγή εμποδίων και προσανατολισμό σε κάποιο στόχο. Η βασική ιδέα είναι να «καθοδηγηθούν» τα πακέτα (πουλιά) ώστε να σχηματίσουν σμήνη και να οδηγηθούν προς το κόμβο-sink (πόλος έλξης), προσπαθώντας ταυτοχρόνως να αποφύγουν περιοχές συμφόρησης (εμπόδια) και περιοχές με «νεκρούς» κόμβους. Στην προτεινόμενη προσέγγιση που είναι εμπνευσμένη από τα σμήνη πουλιών, η κίνηση του κάθε πακέτου επηρεάζεται από: (α) τις δυνάμεις έλξης και απώθησης μεταξύ των πακέτων που γειτνιάζουν, (β) το περιορισμένο οπτικό πεδίο κάθε πακέτου, (γ) το τεχνητό μαγνητικό πεδίο προς το πόλο έλξης (κόμβος-sink), και (δ) τη τυχαιότητα. Η αξιολόγηση της επίδοσης της προσέγγισης Flock-CC δείχνει την αποτελεσματικότητα της στην εξισορρόπηση του φορτίου αξιοποιώντας τους διαθέσιμους πόρους του δικτύου. Η προσέγγιση Flock-CC παρουσιάζει αρκετά καλές επιδόσεις όσον αφορά στο ποσοστό παράδοσης πακέτων, στην απώλεια πακέτων, στη καθυστέρηση, και τη κατανάλωση ενέργειας, καθώς η κίνηση πακέτων αυξάνεται μέσα στο δίκτυο. Επιπλέον, επιτυγχάνει προσαρμογή στις μεταβαλλόμενες συνθήκες του δικτύου, ευρωστία σε συνθήκες απωλειών κόμβων, επεκτασιμότητα σε διαφορετικά μεγέθη δικτύων, και υπεροχή έναντι συμβατικών προσεγγίσεων ελέγχου συμφόρησης. Η δεύτερη προσέγγιση (LVCC) στοχεύει σε εφαρμογές συνεχούς ροής πακέτων (streaming) και επικεντρώνεται στο πώς η συμφόρηση μπορεί να προληφθεί, ή να ελεχθεί ομαλά, σε δίκτυα μικρής κλίμακας, ρυθμίζοντας το ρυθμό αποστολής πακέτων της κάθε ροής με βάση την εξίσωση ελέγχου πληθυσμού ζώων Lotka-Volterra. Η στρατηγική ελέγχου συμφόρησης με βάση την εξίσωση Lotka-Volterra εμπλέκει ελάχιστη ανταλλαγή πληροφοριών και είναι απλή στην υλοποίηση. Η αξιολόγηση της επίδοσης δείχνει ότι η προσέγγιση LVCC επιτυγχάνει προσαρμοστικότητα στη μεταβαλλόμενη κίνηση πακέτων, καθώς και δικαιοσύνη μεταξύ των ροών. Ωστόσο, η επεκτασιμότητα της είναι αμφισβητήσιμη καθώς το μέγεθος του δικτύου μεγαλώνει, και απαιτείται περαιτέρω έρευνα, όπως για παράδειγμα προσαρμοστική ρύθμιση των παραμέτρων ελέγχου. Η διδακτορική διατριβή αυτή χρησιμοποιεί με επιτυχία μηχανισμούς από τη φύση και αποδεικνύει τη χρησιμότητά τους στην πρόληψη και καταπολέμηση της συμφόρησης σε ασύρματα δίκτυα αισθητήρων κάτω από μεταβαλλόμενες συνθήκες του δικτύου και της κίνησης πακέτων επιτυγχάνοντας μείωση των απωλειών πακέτων και των αναμεταδόσεων, οδηγώντας σε μειωμένη καθυστέρηση και χαμηλή κατανάλωσης ενέργειας.

The thesis objective is to investigate nature inspired techniques in the context of congestion control in wireless sensor networks (WSNs), drawing inspiration from swarm intelligence and mathematical models of population biology. Two novel nature-inspired congestion control and avoidance approaches are proposed that aim at improving performance, in particular with respect to packet delivery ratio, end-to-end delay and energy consumption in a variety of sensor applications that follow either the event-based or the continuous-based (streaming) data delivery model. Both proposed congestion control approaches embody a nature-inspired development drive involving desirable properties (e.g self-organization, self-adaptation, robusteness). These properties are not explicitly programmed into the network, but emerge as a result of the collective behavior among interacting individuals. In addition, the proposed approaches are simple to implement at the individual node, involve minimal information exchange, and provide graceful performance degradation at low, medium and high traffic loads. The first approach targets event-based applications and adopts a swarm intelligence paradigm inspired by the obstacle avoidance behavior and the orientation behavior of bird flocks having global self-* properties (e.g. self-adaptation) achieved collectively without explicitly programming them into individual nodes. The main idea is to ‘guide’ packets (birds) to form flocks and flow towards the sink node (global attractor), whilst trying to avoid congestion regions (obstacles). In the proposed flock-based congestion control (Flock-CC) approach, the motion of each packet is influenced by: (a) the repulsive and attractive forces among closely located individuals, (b) the limited visual perception that defines the field of view (FoV), (c) the artificial magnetic field towards a global attractor, and (d) randomness. Performance evaluations show the effectiveness of the Flock-CC approach in balancing the offered load by exploiting available network resources. Flock-CC provides graceful performance degradation in terms of packet delivery ratio, packet loss, delay, and energy tax as the traffic load increases to even extreme levels. In addition, the proposed approach achieves adaptation to changing network and traffic conditions, robustness against failing nodes, even at extreme cases, scalability to different network sizes, and is shown to outperform typical conventional approaches. The second approach targets streaming applications and focuses on how congestion can be prevented, or if not gracefully controlled, in small-scale networks by regulating the rate of each traffic flow based on the Lotka-Volterra population model. The Lotka-Volterra based congestion control (LVCC) strategy involves minimal exchange of information and computation burden and is simple to implement at the individual node. Performance evaluations reveal that the LVCC approach achieves adaptability to changing traffic loads, scalability and fairness among flows, while providing graceful performance degradation, in terms of throughput and delay of individual streams, as the offered load increases. However, its scalability is questionable, and further work is required here, as for example the adaptive setting of its control parameters. This thesis successfully adapts techniques from nature and demonstrates their usefulness in combating congestion in WSNs under changing network and traffic conditions in the sense of reducing packet losses and thus retransmissions, leading to decreased delay and low levels of energy expenditure.