Resource allocation in wireless ad hoc networks

Abstract

Although most of the daily scenarios of using wireless networking are clearly based on a type of infrastructure, such as an access point or a base station, there is a lot of interest for the wireless ad hoc networks. There is a bouquet of scenarios that require wireless connectivity and could not be supported without the wireless ad hoc networking. However, the efficient operation of the ad hoc networks is closely related to the problem of the efficient resource allocation. Resource allocation in the wireless ad hoc networks is a multi-challenging problem, with various open issues related to the routing, scheduling and rate adaptation subproblems. In this dissertation, we propose novel schemes that cope with these challenges, utilizing practices and ideas that originate from the Backpressure and Opportunistic Routing algorithms. We either mathematically prove that our schemes succeed an optimized performance, or we adopt heuristic approaches that are inspired from the aforementioned algorithms. The evaluation of the proposed schemes is based on experimentation using large scale wireless testbeds and extended software tools that adapt to our requirements. The capability for experimentation on these wireless testbeds is provided due to our work on extending the state-of-the-art testbed framework. Our evaluation results are very promising, since we compare our algorithms with other well known schemes and we showcase significant improvements comparing to them.

Παρόλο που τα καθημερινά σενάρια χρήσης της ασύρματης δικτύωσης βασίζονται συνήθως σε κάποια μορφή υποδομής, όπως είναι τα σημεία πρόσβασης (access points) ή οι σταθμοί βάσης (base stations), υπάρχει εξίσου μεγάλο ενδιαφέρον και για τα ασύρματα αδόμητα δίκτυα. Υπάρχει μία πληθώρα σεναρίων που χρειάζονται ασύρματη συνδεσιμότητα και δεν μπορούν να υποστηριχτούν χωρίς την ασύρματη αδόμητη δικτύωση. Ωστόσο, η αποδοτική χρήση των ασύρματων αδόμητων δικτύων είναι στενά συνδεδεμένη με το πρόβλημα της αποδοτικής ανάθεσης πόρων. Η ανάθεση πόρων στα ασύρματα αδόμητα δίκτυα είναι ένα πρόβλημα με πολλές προκλήσεις, με πολλαπλά υπό διερεύνηση θέματα που σχετίζονται με την δρομολόγηση πακέτων, τον χρονικό καθορισμό των μεταδόσεων όπως και την προσαρμογή των ρυθμών εισαγωγής πακέτων μέσα στο δίκτυο. Σε αυτή την διατριβή, προτείνουμε καινοτόμα σχήματα που απαντούν σε αυτές τις προκλήσεις, χρησιμοποιώντας πρακτικές και ιδέες που προκύπτουν από τον Backpressure αλγόριθμο και την Opportunistic routing λογική. Εναλλακτικά, είτε αποδεικνύουμε μαθηματικά ότι τα προτεινόμενα σχήματα έχουν βέλτιστη συμπεριφορά, είτε υιοθετούμε ευριστικές προσεγγίσεις. Η αξιολόγηση τους βασίζεται σε πειραματισμό σε μεγάλης κλίμακας ασύρματες πειραματικές υποδομές και διευρυμένα εργαλεία λογισμικού που καλύπτουν τις δικές μας πειραματικές ανάγκες. Η δυνατότητα για ένα τέτοιο πειραματισμό προκύπτει από την δουλειά μας για επέκταση ενός αναγνωρισμένου λογισμικού για διαχείριση τέτοιων υποδομών. Τα αποτελέσματα της αξιολόγησης μας είναι πολλαπλώς υποσχόμενα, καθότι συγκρίνουμε τους αλγόριθμους μας με άλλους αναγνωρισμένους αλγόριθμους και δείχνουμε σημαντικές βελτιώσεις σε σχέση με τους δεύτερους.