Βελτιστοποίηση Ορίων Bsc Σε Δίκτυα Κινητών Επικονωνιών

Abstract

Ο σκοπός της διπλωματικής εργασίας ήταν η ανάπτυξη αλγορίθμων για τη βελτιστοποίηση των ορίων των BSC ενός δικτύου κινητών επικοινωνιών. Η βασική επιδίωξη για αυτή τη βελτιστοποίηση ήταν η ελαχιστοποίηση των inter-BSC μεταπομπών. Το BSC ή χειριστής σταθμών βάσης είναι το κατεξοχήν τμήμα του δικτύου, το οποίο διευθύνει τους πόρους (διαύλους, μεταπήδηση συχνότητας, μεταπομπές) αυτών των σταθμών. Η μεταπομπή είναι ένας μηχανισμός, ο οποίος μεταφέρει μια κλήση από μια κυψέλη σε μια άλλη, καθώς ο χρήστης μετακινείται κατά μήκος της περιοχής κάλυψης ενός συστήματος κινητών επικοινωνιών. Inter - BSC μεταπομπές είναι οι μεταπομπές που συμβαίνουν μεταξύ κυψελών που ανήκουν σε διαφορετικά BSC. Ο ρυθμός επιτυχίας μιας τέτοιας μεταπομπής είναι σχετικά χαμηλός (γύρω στο 85%) σε σχέση με το ρυθμό επιτυχίας μιας intra - BSC μεταπομπής (γύρω στο 95%), με αποτέλεσμα να διακόπτονται πολλές κλήσεις, λόγω αποτυχίας των μεταπομπών. Για αυτό το λόγο στην παρούσα εργασία έγινε μια προσπάθεια υλοποίησης δυο αλγορίθμων, οι οποίοι ελαχιστοποιούν αυτές τις μεταπομπές.Στην παρούσα εργασία υλοποιήθηκαν δυο αλγόριθμοι, οι οποίοι βασίστηκαν σε αλγορίθμους γράφων. Ένα δίκτυο κινητών επικοινωνιών μπορεί να σχεδιαστεί με τη μορφή γράφου έχοντας ως κόμβους τις κυψέλες του δικτύου, ως πλευρές τις γειτονικές σχέσεις μεταξύ των κυψελών και ως βάρη των πλευρών τις προσπάθειες μεταπομπής μεταξύ των κυψελών.Ο πρώτος αλγόριθμος (BSC Border Optimization - BBO) είναι αλγόριθμος βελτίωσης μιας ήδη υπάρχουσας διάταξης. Παίρνει ως είσοδο μια αρχική διάταξη των σταθμών βάσης σε BSC και τη βελτιστοποιεί μετακινώντας σταθμούς από το ένα BSC στο άλλο, ανάλογα με τις προσπάθειες μεταπομπής. Ο αλγόριθμος αυτός αρχίζει με ένα ζευγάρι BSC, βρίσκοντας τα βέλτιστα όρια μεταξύ τους και στη συνέχεια συνεχίζει με άλλο ζευγάρι, μέχρι να ελεγχθούν όλα τα δυνατά ζευγάρια γειτονικών BSC. Η μετακίνηση των σταθμών από ένα BSC σε κάποιο άλλο γίνεται αν ο σταθμός έχει περισσότερες μεταπομπές με σταθμούς του άλλου BSC απ' ότι με σταθμούς του δικού του BSC.Ο δεύτερος αλγόριθμος (Breadth First Search Partition Algorithm - BPA) φτιάχνει εξαρχής μια διάταξη των σταθμών βάσης σε BSC, χωρίς να χρειάζεται κάποια αρχική διάταξη. Αυτός ο αλγόριθμος αποτελείται από δυο φάσεις: στην πρώτη φάση φτιάχνεται μια αρχική διάταξη με τη βοήθεια της μεθόδου διάσχισης γράφων Breadth First Search - BFS και στη δεύτερη φάση γίνεται βελτιστοποίηση της αρχικής διάταξης με την εφαρμογή του πρώτου αλγορίθμου (BBO).Οι αλγόριθμοι αυτοί υλοποιήθηκαν σε γλώσσα Excel Visual Basic for Applications και εφαρμόστηκαν πάνω στο δίκτυο του Cosmote. Τα αποτελέσματα που προέκυψαν ήταν αρκετά ικανοποιητικά, αφού η μείωση των inter - BSC μεταπομπών έφτανε το 45% περίπου.