Joint resource allocation and routing in wireless networks via convex approximation techniques

Abstract

The first topic of this thesis is the joint back pressure routing and power control problem (BPPC) in the context of cross-layer wireless networking. Our main objective is the end to end throughput maximization in wireless multi hop networks, which entails a key physical layer optimization problem, maximizing a weighted sum of link rates, with weights given by the differential queue backlogs. We prove that BPPC problem, which is central in cross-layer wireless networking, is NP hard. Drawing from related developments in the DSL literature, we use successive convex approximation strategies to approximate it, and come up with efficient centralized algorithms that provide approximate solutions to the BPPC problem. Our extensive simulation results prove that our proposed solutions deliver manifold improvements in end to end throughput relative to the prior art in networking, and illustrate the merits of the proposed algorithms. We then develop distributed algorithms for the approximation of BPPC, which are based on two different approximation approaches, the successive convex approximation approach, in which case we utilize the ADMoM method towards distributed implementation, and the iteratively re-weighted Minimum Mean Square Error approach. Our simulation results show that the proposed algorithms offer excellent throughput performance at low complexity. Finally, we deal with the joint multicast beamforming and admission control problem for one or more multicast groups, aiming to maximize the number of subscribers and to minimize the power required to serve them. The problem is NP-hard, but using convex approximation techniques, we develop an efficient approximation algorithm that yields good solutions at affordable worst-case complexity.

Το πρώτο θέμα της διατριβής είναι n από κοινού δρομολόγηση και έλεγχος ισχύος (BPPC) στη διαστρωματική σχεδίαση ασύρματων δικτύων. Στόχος είναι η μεγιστοποίηση της χωρητικότητας μεταφοράς ασύρματων δικτύων, που προϋποθέτει τη μεγιστοποίηση ενός ζυγισμένου αθροίσματος των χωρητικοτήτων των συνδέσμων, με συντελεστές ζύγισης τις διαφορές των ουρώ ν αναμονής στα άκρα τους. Αποδεικνύουμε ότι η βέλτιστη επίλυση του BPPC είναι απαγορευτικής πολυπλοκότητας. Χρησιμοποιούμε, από τη DSL βιβλιογραφία, τεχνικές διαδοχικών κυρτών προσεγγίσεων και καταλήγουμε σε αποτελεσματικούς κεντρικούς αλγορίθμους, παρέχοντας προσεγγιστικές λύσεις στο BPPC. Πειράματα προσομοιώσεων δείχνουν ότι οι προτεινόμενες λύσεις παρέχουν πολλαπλές βελτιώσεις στην χωρητικότητα μεταφοράς, σε σχέση με τις επικρατέστερες τεχνικές στη σχεδίαση ασύρματων δικτύων, και αναδεικνύουν τα πλεονεκτήματα των προτεινόμενων αλγορίθμων. Έπειτα, αναπτύσσουμε κατανεμημένους αλγορίθμους για την προσέγγιση του BPPC, βασιζόμενοι στην τεχνική των διαδοχικών κυρτών προσεγγίσεων, και στην μέθοδο ελαχιστοποίησης επαναληπτικά ζυγιζόμενου μέσου τετραγωνικού σφάλματος. Προσομοιώσεις δείχνουν ότι οι προτεινόμενοι αλγόριθμοι έχουν εξαιρετική απόδοση από πλευράς χωρητικότητας μεταφοράς των δικτύων, με χαμηλή πολυπλοκότητα. Τέλος, διαπραγματευόμαστε την από κοινού μορφοποίηση λοβών και έλεγχο πρόσβασης σε ασύρματη μετάδοση, με στόχο τη μεγιστοποίηση του αριθμού των συνδρομητών και την ελαχιστοποίηση ισχύος εκπομπής. Χρησιμοποιώντας τεχνικές κυρτής προσέγγισης, προτείνουμε ένα προσεγγιστικό αλγόριθμο, που αποδίδει καλές λύσεις με αποδέκτη μέγιστη πολυπλοκότητα.