Improving network performance through multipath utilization for wireless mesh networks

Abstract

In order to meet the increased demand for quality of service over wireless mesh networks, a large number of studies have suggested employingmultiple paths in parallel, in order to aggregate the scarce resources. Multipath utilization comes in many different flavoursincluding schemes that perform routing, resource allocation, flow and congestion control, and opportunistic forwarding.Multipath utilization has been shown to be advantageous in terms of delay, throughput, reliability, and load balancing.Two common performance goals are increased throughput and fault tolerance.For achieving reliability, multipath utilization is combined with redundancy.However, multipath utilization in wireless networks, is more complicated compared to their wired counterparts since transmissionsacross a link interfere with neighbouring links and may result in reduced network performance.In this thesis, static, random access, wireless mesh networks are considered, where receivers have multi-packetreception capabilities. Multiple unicast flows are forwarded to their destinations through node-disjoint paths.In the first part of the thesis, different forwarding schemes, employing multiple paths and different degrees of redundancyare compared in terms of delay and throughput.An analytical framework for expressing the throughput and delay of these schemes is evaluated, through Ns2 simulationsof various scenarios and is also extended for the case where link success probability is captured through the SINR model.In the second part of the thesis, multipath utilization for maximizing average aggregate flow throughput is addressed, for the aforementioned type of networks.A distributed flow rate allocation scheme that maximizes average aggregate flow throughput, while also providing bounded delay is proposed, thatdoes not employ any kind of redundancy.For the purposes of the suggested scheme, flow rate allocation is formulated as an optimization problem. A simple model for the average aggregate flow throughputis employed that captures both intra- and inter-path interference through the SINR model.As far as interference is concerned, two different variants of the suggested scheme are explored.In the first one, interference is approximated by considering only that link's dominant interferers.In the second variant, a simple topology is employed where receivers apply successive interference cancellation, instead oftreating interference as noise.For the evaluation process, Ns2 simulations of some illustrative topologies, along with several random wirelessones are employed. The proposed scheme is compared with three other simple flow allocation schemes both in termsof average aggregate flow throughput and flow delay.

Προκειμένου να ικανοποιηθούν οι αυξανόμενες απαιτήσεις για ποιότητα υπηρεσίας πάνω από ασύρματα δίκτυα πλέγματος, ένας μεγάλος αριθμός μελετών προτείνει την αξιοποίηση πολλαπλών μονοπατιών ταυτόχρονα με σκοπό να αθροιστούν οι πόροι τους. Υπάρχουν αρκετές διαφορετικές προσεγγίσεις αξιοποίησης πολλαπλών μονοπατιών οι οποίες περιλαμβάνουν σχήματα που πραγματοποιούν δρομολόγηση, δέσμευση πόρων, έλεγχο ροής και ευκαιριακή προώθηση κίνησης. Η ταυτόχρονη αξιοποίηση πολλαπλών μονοπατιών έχει αποδειχτεί επωφελής ως προς την καθυστέρηση, το ρυθμό διαμεταγωγής δεδομένων, τηναξιοπιστία και την ισοκατανομή φόρτου κίνησης. Δύο διαδεδομένοι στόχοι είναι ο αυξημένος ρυθμός διαμεταγωγής δεδομένων και η αξιοπιστία. Προς επίτευξη της αξιοπιστίας συγκεκριμένα, η αξιοποίηση πολλαπλών μονοπατιών συνδυάζεται με πλεονασμό.Παρ' όλα αυτά, η αξιοποίηση πολλαπλών μονοπατιών στα ασύρματα δίκτυα είναι πιο περίπλοκη, από ότι στα ασύρματα καθώς μεταδόσεις σε μία ζεύξη παρεμβάλλουν γειτονικές ζεύξεις και μπορεί να οδηγήσουν σε μειωμένη δικτυακή απόδοση. Στην παρούσα διδακτορική διατριβή, θεωρούνται στατικά, ασύρματα δίκτυα πλέγματος, τυχαίας προσπέλασης, όπου τα μονοπάτια αποτελούνται από πολλαπλές ζεύξεις. Επιπλέον, οι παραλήπτες έχουν δυνατότητα για λήψη πολλαπλών πακέτων. Πολλαπλές ροές κίνησης, τύπου μονοεκπομπής, προωθούνται προς τους προορισμούς, μέσω μονοπατιών που δεν έχουν κοινούς κόμβους.Στο πρώτο τμήμα της διατριβής, διαφορετικά σχήματα προώθησης κίνησης που αξιοποιούν πολλαπλά μονοπάτια και διαφορετικούς βαθμούς πλεονασμού συγκρίνονται ως προς την καθυστέρηση και το ρυθμό διαμεταγωγής δεδομένων. Αξιολογείται, μέσω προσομοιώσεων διαφόρων σεναρίων, στον προσομοιωτή δικτύων Ns2 ένα αναλυτικό πλαίσιο το οποίο εκφράζει την καθυστέρηση και το ρυθμό διαμεταγωγής δεδομένων για τα προαναφερθέντα σχήματα προώθησης κίνησης. Το συγκεκριμένο αναλυτικό πλαίσιο επεκτείνεται και αξιολογείται επίσης για την περίπτωση όπου η πιθανότητα λάθους μίας ζεύξης εκφράζεται μέσω του μοντέλου σηματοθορυβικής σχέσης.Στο δεύτερο μέρος της διατριβής, εξερευνάται το θέμα της αξιοποίησης πολλαπλών μονοπατιών με σκοπό την αύξηση του μέσου αθροιστικού ρυθμού διαμεταγωγής δεδομένων, για τον προαναφερθέντα τύπο δικτύων. Προτείνεται ένα κατανεμημένο σχήμα κατανομής ροής, το οποίο μεγιστοποιεί τον μέσο αθροιστικό ρυθμό διαμεταγωγής δεδομένων για όλες τις ροές, ενώ ταυτόχρονα, παρέχει πεπερασμένη καθυστέρηση. Δεν χρησιμοποιείταικανενός είδους πλεονασμός. Για τους σκοπούς του συγκεκριμένου σχήματος, η κατανομή ροής σε πολλαπλά μονοπάτια διατυπώνεται σαν ένα πρόβλημα βελτιστοποίησης. Το προτεινόμενο σχήμα βασίζεται σε ένα απλό μοντέλο για το μέσο αθροιστικό ρυθμό διαμεταγωγής δεδομένων, το οποίο εκφράζει τις παρεμβολές από γειτονικά μονοπάτια, αλλά και τις παρεμβολές από κόμβους του ίδιου μονοπατιού, μέσω του μοντέλου σηματοθορυβικής σχέσης.Αναφορικά με τις παρεμβολές, εξετάζονται δύο εκδοχές του προτεινόμενου σχήματος κατανομής ροής. Στην πρώτη εκδοχή, η παρεμβολή σε μία ζεύξηπροσεγγίζεται λαμβάνοντας υπόψη μόνο τους σημαντικότερους παρεμβολείς. Στη δεύτερη εκδοχή, οι παραλήπτες εφαρμόζουν την τεχνική της διαδοχικήςαπαλοιφής παρεμβολών. Για την διαδικασία αξιολόγησης, αξιοποιούνται προσομοιώσεις, τόσο ενδεικτικών όσο και τυχαίων ασύρματων σεναρίων, χρησιμοποιώντας τον προσομοιωτή δικτύων Ns2. Το προτεινόμενο σχήμα κατανομής ροής συγκρίνεται με άλλα απλάσχήματα κατανομής ροής, τόσο ως προς την καθυστέρηση όσο και ως προς το ρυθμό διαμεταγωγής δεδομένων.