Информатика 2014 апрельиюнь
 Скачать 0.69 Mb.
|
|
ИНФОРМАТИКА 2014 апрель-июнь № 2 УДК 004.725 Ю.И. Воротницкий, В.П. Кочин, Д.А. Стрикелев ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ ОПТИМИЗАЦИИ СТРУКТУРЫ БЕСПРОВОДНОЙ СЕТИ С ЗАДАННЫМ КАЧЕСТВОМ ОБСЛУЖИВАНИЯ Описывается математическая модель оптимизации расположения точек доступа Wi-Fi с за- данным качеством обслуживания. Разрабатывается модифицированный генетический алгоритм оптимизации расположения точек доступа Wi-Fi. Проводится апробация результатов для тестово- го здания. Введение Задачи проектирования и оптимизации сетей передачи данных, актуальные на данный момент в науке и промышленности, характеризуются высокой вычислительной сложностью и немонотонным, «зашумленным» ландшафтом пространства решений. При решении этих за- дач традиционные аналитические методы оптимизации либо неприменимы, либо находят ло- кальные субоптимальные решения, далекие от глобальных экстремумов, а методы полного перебора неприменимы из-за размерности пространства решений. Это обусловило появление и развитие нового класса эвристических методов, основанных на имитации механизмов, дей- ствующих в природе, в частности генетических алгоритмов. Назовем их наиболее важные преимущества: – высокая степень распараллеливаемости на различных уровнях (как микро-, так и макро-); – эффективность при решении многокритериальных задач по следующим причинам: по- иск ведется в различных областях пространства решений одновременно, не требуется априор- ного задания весов критериев, на выходе получаются множества решений с различными прио- ритетами критериев. 1. Постановка задачи Требуется определить оптимальное расположение точек доступа Wi-Fi в заданном помещении с целью организации беспроводного доступа к мультимедийным ресурсам с требуемым качеством обслуживания и с учетом особенностей организации учебного про- цесса вуза – требований на возможность подключения заданного количества пользователей в аудиториях [1]. Размещение пользователей в помещении задается выражением { , } , 1, , i U x y i R (1) где R – общее число пользователей; x, y – координаты пользователей. Подключение пользователей к точкам доступа задано матрицей UM размерностью R x N: 1, если -й пользователь подключен к -й точке доступа; 0, если -й пользователь не подключен к -й точке доступа, ij i j UM i j (2) где R – количество пользователей; N – количество точек доступа. Помещение представляет собой множество стен с заданными координатами их углов, толщиной и проницаемостью материала стены ' '' ; ; ; ; , 1, , i i i i i i W f x x x h i M (3) 118 Ю.И. ВОРОТНИЦКИЙ, В.П. КОЧИН, Д.А. СТРИКЕЛЕВ где M – количество стен в здании; f i (x) – уравнение i-й стены с граничными условиями x ’ i , x ’’ i ; h i – толщина i-й стены; ε i – диэлектрическая проницаемость стены. Возможность подключения пользователей к точке доступа определяется ее техниче- скими характеристиками, а также мощностью сигнала, ослабляемого при прохождении пре- пятствий. Для расчета ослабления сигнала применяется выражение, полученное в [2] и зависящее от следующих аргументов: d – расстояния в свободном пространстве, которое проходит волна; h – толщины стены, через которую проходит волна; k – коэффициента ослабления материала стены; f – частоты волны. С помощью выражения [2] становится возможным вычислить ослабление сигнала при распространении из точки (x i , y i ) в точку (x i ’, y i ’): ψ ; ; ; x y i i i i x y x y (4) Для расчета скорости доступа при заданной мощности сигнала и количестве пользовате- лей применяется выражение, приведенное в [3]. На основе данного выражения и требований качества сервиса положим: 1, если -й пользователь подключен с соблюдением требований ; φ 0 в противном случае. i i QoS P (5) Таким образом, целевая функция оптимизации приобретет вид 1 1 1 ; ; ; max; 1, 1, , R N x y ij i i i i i j N ij i UM x y x y UM i R (6) где x i , y i – координаты i-го пользователя; x j x , y j y – координаты j-й точки доступа Wi-Fi. Искомым решением задачи является множество координат точек доступа X (размерно- сти N), X i = {x i x , x i y }. 2. Генетический алгоритм оптимизации размещения точек доступа В рамках описанной математической модели задачи решением будет являться набор ко- ординат точек доступа. Координаты каждой точки будут определяться геном, а их множество – формировать хромосому. Первым шагом алгоритма является генерация начальной популяции решений. В классиче- ских генетических алгоритмах начальная популяция генерируется случайным образом. Однако в рассматриваемом случае это может привести к росту вычислительной сложности и к вырожде- нию конечного решения. В связи с этим предлагается двухэтапный алгоритм формирования ис- ходной популяции. На первом этапе необходимо определить места с наибольшим количеством пользователей Wi-Fi и центры этих «скоплений». Для решения подобных задач исследователями применялись такие алгоритмы кластеризации, как K-means, C-means, Fuzzy-clustering и др. [4–6]. Решаемая задача характеризуется рядом ограничений: количеством пользователей, подключаемых к точке доступа; геометрией помещения (возможно, ближайший клиент будет находиться через стенку, но по мощности будет самый худший); вычислительной сложностью, с учетом того что необходимо сгенерировать популяцию с Q количеством особей. Таким образом, ни один из перечисленных выше алгоритмов не удовлетворяет условиям задачи. В связи с этим в данной статье предложен следующий алгоритм (рис. 1). ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ ОПТИМИЗАЦИИ СТРУКТУРЫ СЕТИ 119 Рис. 1. Схема алгоритма генерации начальной популяции Геометрическая конфигурация помещения, в котором размещаются точки доступа, впи- сывается в прямоугольник с координатами левого нижнего угла (x min ; y min ) и правого верхнего угла (x max ; y max ). Вся площадь раcположения точек доступа Wi-Fi разбивается на U 2 квадратов. При этом U определяется соотношением 2 2 1 , U N U (7) где N – количество точек доступа Wi-Fi, которые необходимо разместить. Далее определяется количество абонентов в каждом квадрате, для чего точки доступа помещаются в квадрат с вероятностью p i u , пропорциональной количеству абонентов: , u i i R p R (8) где R i – количество абонентов в i-м квадрате; R – общее количество абонентов. На втором этапе работы алгоритма точка доступа случайным образом помещается внутри i-го квадрата. Также необходимо учитывать, что осуществить установку точки доступа возле 120 Ю.И. ВОРОТНИЦКИЙ, В.П. КОЧИН, Д.А. СТРИКЕЛЕВ стены технически более просто. Для учета данного допущения определяется расстояние H до ближайшей стены, и если H 0 , где H 0 – эталонное расстояние равное 0,5 м, то точку доступа перемещаем к стене по перпендикуляру. На следующем этапе определяется алгоритм подключения клиентов к точке доступа (рис. 2): 1. Если R k <R k max , где R k – количество подключенных клиентов к точке доступа k, R k max – максимально разрешенное количество абонентов точки доступа k, то переходим к шагу 2; ина- че, если не существует точки доступа с R k <R k max , устанавливаем скорость доступа для клиента в точке X B = 0. 2. Для клиента в точке X рассчитываем скорость доступа B k при подключении к точке доступа K. 3. Подключаем клиента к точке доступа с max(B k ). Рис. 2. Схема алгоритма подключения клиентов к точке доступа Оценивание приспособленности хромосом в популяции состоит в расчете функции при- способленности (фитнес-функции) для каждой хромосомы этой популяции: , i b B i i F c (9) где B – пороговая скорость подключения клиентов к сети, определяемая моделью трансляции качества услуг QoS; b i – скорость подключения i-го клиента к сети; c i – штрафная функция для точки доступа, для которой b i ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ ОПТИМИЗАЦИИ СТРУКТУРЫ СЕТИ 121 ной функции для точки доступа k, для которой выполняется условие b i b i и удовлетворять соотношению max min i i i k i c c (10) При рассмотрении качества услуг (Quality of Service, или QoS) в зависимости от конкрет- ного типа решаемой задачи начальные метрики критерия формулируются с точки зрения поль- зователя на пользовательском уровне. В качестве характеристик прикладного уровня исполь- зуются время задержки при передаче файла и характеристики потока. В качестве характеристик транспортно-сетевого уровня используются пропускная способность, время задержки, джиттер, вероятность потери пакета. В качестве характеристики физического уровня используется мощ- ность сигнала. Так как характеристика физического уровня является непосредственно измеряе- мой (оцениваемой) в процессе оптимизации, авторы предлагают последовательное использова- ние трех преобразований, каждое из которых выполняется по своим правилам. На первом этапе необходимо осуществить преобразование характеристик пользовательского уровня в характе- ристики прикладного уровня, на втором этапе – преобразование характеристик прикладного уровня в характеристики транспортно-сетевого уровня, на третьем этапе – преобразование ха- рактеристик транспортно-сетевого уровня в характеристики физического уровня. Таким образом, штрафная функция для точек доступа будет иметь вид const , i B b i c e (11) где const– константа, которая зависит от количества точек доступа, участвующих в оптимиза- ции, и параметра B,который определяется моделью трансляции качества услуг QoS: const ( 1), B R e (12) Фитнес-функция будет иметь вид const i i b B B b i F e (13) В качестве оператора мутации выступает одно из следующих преобразований: удаление точки доступа с вероятностью α; включение точки доступа с вероятностью β. Смотрим, какие точки доступа выключе- ны, случайно выбираем одну, включаем ее в точке со случайной координатой (генерация слу- чайных координат должна попадать в разрешенную координату); смещение с вероятностью γ точки доступа Wi-Fi в новое положение. На первом этапе для скрещивания случайным образом выбираются пары хромосом из ро- дительской популяции. Это временная популяция, состоящая из хромосом, отобранных в ре- зультате селекции и предназначенных для дальнейших преобразований операторами скрещи- вания и мутации с целью формирования новой популяции потомков. Само скрещивание происходит по следующим правилам: 1. Для пары хромосом вычисляются вероятности 2 1 1 1 F F F p c , c c p p 1 2 1 , где F 1 и F 2 – значения фитнес-функции для двух хромосом. 2. Далее проверяются следующие утверждения: точка доступа присутствует в первой хромосоме, но отсутствует во второй. Тогда с ве- роятностью p 1 c она присутствует в потомке, с вероятностью p 2 c не присутствует; точка доступа присутствует во второй хромосоме, но отсутствует в первой. Тогда с ве- роятностью p 2 c она присутствует в потомке, с вероятностью p 1 c не присутствует; точка доступа присутствует в обеих хромосомах. Тогда координаты точки доступа потомка берутся с вероятностью p 1 c из первой хромосомы, с вероятностью p 2 c из второй хро- мосомы. 122 Ю.И. ВОРОТНИЦКИЙ, В.П. КОЧИН, Д.А. СТРИКЕЛЕВ После скрещивания размер популяции является увеличенным по отношению к своему нормальному уровню. Для корректировки этой ситуации на финальном этапе итерации прово- дится отбор наиболее приспособленных индивидов на основе значений функции приспособ- ленности. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наименьшими значениями функции приспособленности. Таким образом, в алгоритме будет использована тур- нирная селекция, при которой в результате скрещивания пары хромосом будет выбрана особь с наилучшим значением функции приспособленности. На основе модифицированного генетического алгоритма был создан программный ком- плекс оптимизации расположения точек доступа Wi-Fi. Для создания программного комплекса использовались язык программирования C++ и библиотека MPI. Для проведения вычислительного эксперимента предполагалось, что необходимо разме- стить четыре точки доступа Wi-Fi в помещении с девятью комнатами, одна из которых поточ- ная аудитория, при этом количество пользователей в комнатах известно. Расчет расположения точек доступа Wi-Fi производился на компьютере со следующими параметрами: операционная система Windows 7, двухъядерный процессор Intel Pentium Dual E2160 1,8 ГГц, оперативная память 2048 Мб. Для отображения результатов вычисления был создан графический интерфейс. В процес- се вычисления проводилась выборка хромосом для оценки сходимости алгоритма. Результат вычисления показан на рис. 3. Рис. 3. Размещение точек доступа Wi-Fi с наилучшим значением фитнес-функции Среднее время работы программного комплекса составило 915 с при размере популяции 60 особей. В результате проведенного эксперимента удалось установить следующие закономерно- сти: при увеличении количества точек доступа W-Fi размер популяции увеличивается по полиномиальному закону; при увеличении количества точек доступа W-Fi время работы алгоритма увеличивается по экспоненциальному закону. Данные зависимости объясняются многократным вычислением целевой функции на каж- дой итерации. Таким образом, при увеличении количества точек доступа Wi-Fi до 50 время ра- боты алгоритма может составить до года в зависимости от размера популяции и геометрии по- ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ ОПТИМИЗАЦИИ СТРУКТУРЫ СЕТИ 123 мещения. В связи с этим в дальнейшем вычисления будут проводиться с использованием вы- числительных ресурсов суперкомпьютера СКИФ-БГУ. В настоящее время для расчетов до- ступны 65 узлов, в каждом из которых два двухъядерных процессора AMD Opteron 2,2 ГГц. Таким образом, скорость работы алгоритма увеличится примерно в 300 раз по сравнению с вы- числениями на тестовой рабочей станции. Использование ресурсов суперкомпьютера СКИФ-БГУ позволит, во-первых, рассчитать оптимальное расположение точек доступа Wi-Fi при их достаточно большом количестве, во- вторых, увеличить точность полученных результатов. Заключение Предложенный генетический алгоритм позволяет получить размещение точек доступа Wi-Fi при условии наиболее полного соблюдения требований заданного качества услуг. Дан- ный алгоритм характеризуется высокой степенью распараллеливаемости, что позволяет при расчетах использовать ресурсы суперкомпьютерных кластерных систем. Список литературы 1. Воротницкий, Ю.И. Мобильные компьютерные устройства в «облачной» информаци- онно-образовательной среде общеобразовательной школы / Ю.И. Воротницкий, М.Г. Зеков, А.Н. Курбацкий. – Минск : Ривш, 2012. – 100 с. 2. Кочин, В.П. Быстрая оценка мощности Wi-Fi-сигнала при прохождении препятствий в пределах здания / В.П. Кочин, Ю.И. Воротницкий, Д.А. Стрикелев // Вестник БГУ. Сер. 1. – 2013. – № 1. – С. 45–50. 3. Воротницкий, Ю.И. Оценка пропускной способности информационного канала бес- проводной связи с заданной мощностью сигнала / Ю.И. Воротницкий, В.П. Кочин, Д.А. Стрикелев // Информатизация образования. – 2013. – № 3. – С. 28–32. 4. Jain, A. Data Clustering: A Review / A. Jain, M. Murty, P. Flynn // ACM Computing Sur- veys. – 1999. – Vol. 31, no. 3. – P. 264–323. 5. Прикладная статистика: классификация и снижение размерности / С.А. Айвазян [и др.]. – М. : Финансы и статистика, 1989. – 607 p. 6. Gorban, A.N. Principal Graphs and Manifolds. Ch. 2 / A.N. Gorban, A.Y. Zinovyev // Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods, and Techniques. – Hershey, PA, USA, 2009. – P. 28–59. Поступила 12.03.2014 Белорусский государственный университет, Минск, пр. Независимости, 4 e-mail: kochyn@bsu.by Y.I. Vorotnitsky, V.P. Kochyn, D.A. Strikelev A GENETIC ALGORITHM FOR WI-FI NETWORK STRUCTURE OPTIMIZATION UNDER THE GIVEN QUALITY OF SERVICE A mathematical model for optimal placement of Wi-Fi access points under the given quality of service is developed. A modified genetic algorithm for optimal placement of Wi-Fi access points is worked out. Probation of the results is carried out for a test area. |