Алгоритм сравнения интернет-провайдеров, основанный на семействе методов ELECTRE

Аннотация

В данной статье разработан многокритериальный метод сравнения Интернет-провайдеров, базирующийся на семействе методов принятия решений ELECTRE [1, 2]. Для сравнения провайдеров используются следующие критерии: 1) скорость передачи данных; 2) время суток проведения измерения скорости; 3) разнообразие тарифных планов провайдеров. Данная методика реализована в программе wiRating и может использоваться пользователями сети Интернет.
 
Ключевые слова: Метод ELECTRE, рейтинг провайдеров, многокритериальные методы принятия решений, схема Simos, измерения скорости связи Интернет
 

Введение

Для многих людей доступ к компьютеру и высокоскоростному интернету с каждым днем становятся все более и более значимыми. Мы используем компьютер и Интернет для того, чтобы выполнять домашние задания в школе, искать работу, планировать отдых и покупать билеты, смотреть фильмы, быть на связи с родными людьми и друзьями, что неоспоримо показывает высокую значимость цифровых технологий в жизни людей. С усовершенствованием программного обеспечения и оборудования, использующегося для осуществления связи, также растет количество провайдеров связи. Развивается доступ к Сети с помощью технологий радиодоступа, спутниковой и мобильной связи. В результате возникают вопросы, как о качестве, так и о возможности сравнения и выбора наиболее оптимального провайдера согласно тем или иным требованиям.
 
Как в повседневной жизни, так и в профессиональной деятельности мы часто сталкиваемся с необходимостью принятия решений, имея несколько конфликтующих критериев. Например, покупая автомобиль, мы руководствуемся такими критериями как цена, безопасность, комфорт, расход топлива и др. Первые два из перечисленных критериев могут рассматриваться как конфликтующие. В подобных ситуациях мы обычно интуитивно принимаем решение о важности различных критериев, но при большом количестве критериев также является очень полезным однозначно математически рассчитать влияние тех или иных критериев. Данная работа посвящена подобному расчету при необходимости выбора, имея несколько альтернатив.
 
Один из методов многокритериальной оценки, ELECTRE (ELimination Et Choix Traduisant la Eealite — исключение и выбор, отражающие реальность), был разработан в Европе в 60-ых годах XX века, с последующим развитием целого семейства методов принятия решений, таких как выбор, сравнение и сортировка. Метод работает для сравнения объектов по 3-12 критериям. Хотя бы по одному критерию должна собираться статистика.
 
В данной работе объектом являются провайдеры сети Интернет. К основным характеристикам провайдеров относятся такие факторы, как скорость передачи данных, стабильность связи, стоимость, зона покрытия, разнообразие тарифных планов, качество предоставления помощи пользователям и т.д. К сожалению не все из перечисленных характеристик являются доступными и поэтому не могут использоваться для расчета оценки провайдера.
 
Целью данной работы является разработка метода сравнения Интернет-провайдеров, используя варьируемый набор критериев. Выбранные критерии: 1) скорость передачи данных; 2) время суток проведения измерения скорости; 3) разнообразие тарифных планов провайдеров.
 

Теоретические основы алгоритма

Методы ELECTERE направлены на решение задач с уже заданными многокритериальными альтернативами. Оценка альтернатив является относительной, т.е. устанавливается условие превосходства одной альтернативы над другой. Попарное сравнение альтернатив с учетом численного значения веса каждого из критериев позволяет построить матрицы согласия/несогласия. Элементы этих матриц используются для расчета численного значения рейтингов каждой из альтернатив, т.е. каждого из провайдеров. В итоге, расчет рейтингов провайдеров, более подробно описанный ниже в данном разделе, проводится в три этапа: определение весов критериев, расчет матриц согласия/несогласия и расчет самих рейтингов.
 

Используемые данные

Для получения рабочего набора данных, проводится многократное измерение скорости передачи информации для каждого из провайдеров из точки А в точку Б (далее, по маршруту АБ) в разное время суток с разных устройств доступа в Интернет. В итоге, получаем набор пар значений: скорость передачи данных и время измерения скорости.

Определение критериев

Для сравнения провайдеров в данной работе был выбран ряд критериев. 1) Скорость передачи данных, обозначим сs (критерий скорости). Чем выше скорость, тем более высокую оценку получает провайдер. 2) Разнообразие тарифных планов провайдеров, сp (критерий тарифных планов). Чем больше вариация скоростей провайдера, тем разнообразнее тарифные планы и, следовательно, более высокий по оценке провайдер. 3) Время суток проведения измерения скорости, сt (критерий времени). Рассматриваются три периода времени: ночь (24.00 - 8.00 ч), день (8.00 - 20.00 ч) и вечер (20.00 - 24.00 ч). Более высокая оценка дается провайдеру, у которого преобладают вечерние тарифы с высокими скоростями передачи информации.
 
Одним из основных предположений, используемых в данной работе, является тот факт, что измерения скорости по маршрутам предполагаются одинаково распределенными, даже если измерения были проведены с разных устройств доступа в Интернет. Выборки данных также предполагаются однородными. Значение критерия скорости рассчитывается как выборочное среднее всех значений скоростей, полученных по одному маршруту по формуле:
 
Формула 1, где N — общее количество измерений.
 
Значение критерия тарифных планов рассчитывается как выборочная дисперсия всех измерений скорости с устройств с уникальным идентификатором. Это было введено для того, чтобы не учитывать повторно тарифный план с устройства, с которого было получено несколько измерений скорости. В случае нескольких измерений для расчета берется максимальное значение. Формула для расчета:
 
Формула 2, где N — это количество измерений, полученных с устройств с уникальным идентификатором.
 
Для расчета значения критерия времени вводится вектор [0.5 1.0 1.5] , элементы которого соответствуют следующим трем упомянутым выше периодам времени: ночь (24.00 - 8.00 ч), день (8.00 - 20.00 ч) и вечер (20.00 - 24.00 ч). Так как в вечернее нерабочее время число пользователей сети Интернет резко возрастает, этому периоду приписывается максимальный коэффициент, 1.5. В случае ночного периода, этот коэффициент минимальный, 0.5. Сам параметр критерия рассчитывается по формуле:
 
Формула 2, где ti – это одно из трех значений вектора [0.5 1.0 1.5] , в зависимости от того, в какой период времени было произведено измерение, i – номер измерения, N – общее число измерений.
 

Шкалы критериев

Максимальные значения критериев выбраны следующим образом: 100,000 кб/с для критерия скорости; 2,500,000,000 (что является максимальным значением дисперсии при максимальном значении скорости 100,000 кб/с и минимальном значении 0 кб/с) для критерия тарифных планов; 1.5 для критерия времени (максимальный элемент вектора критерия времени). Важно заметить, что эти значения могут варьироваться и не влияют на построение алгоритма и выводы, сделанные в данной работе.
 

Определение весов критериев

Веса критериев могут определяться несколькими способами. Во-первых, основываясь на мнениях пользователей, которые сопоставляют каждому критерию численное значение в пределах заданного интервала. Чем ближе значение к максимально возможному, тем больший вклад будет иметь этот критерий при расчете матриц согласия/несогласия и самих рейтингов.
 
Второй способ, также базирующийся на личном мнении пользователей, заключается в сопоставлении каждому критерию игровой карты. Этот метод был предложен во Франции автором Simos J. в 1990 г [3]. При наличии N критериев, пользователю дается N игральных карт, на каждой из которых отображено название критерия. Пользователю также дается набор белых карт того же размера, что и карты для каждого из критериев. Количество белых карт выбирается самим пользователем.
 
На следующем этапе мы просим пользователя отсортировать эти карты в порядке возрастания важности критерия согласно его личному выбору: первая карта соответствует наименее значимому критерию, последняя карта соответствует наиболее значимому критерию. Если нескольким критериям приписывается одинаковая значимость, то эти карты соединяются вместе в один набор. Также оговаривается, что разница важности каждого из двух следующих друг за другом критериев может варьироваться. Для этого пользователю предлагается вставить некоторое количество белых карт между всеми сортированными картами. Чем больше разница в важности критериев двух соседних карт (или наборов карт, в случае одинаковой важности), тем больше количество добавляемых белых карт. Отсутствие белых карт между двумя соседними критериями означает, что разница важности между ними принимается минимальной, обозначим ее u. Если между двумя соседними критериями была добавлена одна белая карта, то разница важности этих двух критериев принимается вдвое большей и равной 2u, аналогично поступают с большим количеством белых карт. Подробный пример расчета весов критериев, используя набор игральных карт, описан в работе [3]. Так как процесс расчета является очень громоздким, и используется строго по рекомендациям автора, в данной работе он не приводится.
 
В-третьих, количество белых карт можно также рассчитать, используя имеющуюся выборку измерений скорости. Для каждого из провайдеров скорость измеряется в разное время суток, и как следствие выборка является неоднородной. В данной работе для оценки провайдеров мы вынуждены пренебречь этой неоднородностью и считать выборку измерений распределенной нормально при достаточно большом количестве измерений. Число белых карт, n, для критерия скорости определяется по следующей формуле:
 
Формула 6, где am – амплитуда, соответствующая наиболее часто встречающейся скорости в гистограмме нормального распределения, нормированная на общее число измерений. Коэффициент 3 соответствует максимально возможному количеству белых карт и устанавливается независимо от измерений. Формула была выведена согласно следующим рассуждениям: чем больше разброс по скоростям и, соответственно, ниже максимальная амплитуда гистограммы, тем большую значимость получает критерий скорости. В этом случае количество белых карт стремится к максимальному. И наоборот, чем меньше разброс по скоростям, тем меньшее значение приобретает этот критерий с количеством белых карт, стремящимся к минимальному значению. Приведенную выше формулу можно также записать в следующем виде:
 
Формула 7, где Формула 8 – это значение функции плотности вероятности в точке выборочного среднего. Нормальноераспределение задается функцией Гаусса:
 
Формула 9. Принимая Формула 10, получаем следующее выражение для функции плотности:
 
Формула 11.
 
Аналогично рассчитывается численное значение критерия тарифных планов. Отличием является то, что дисперсия рассчитывается по измерениям скорости с устройств с уникальным идентификатором. Если с одного устройства получено несколько измерений, то берется максимальное значение. Это сделано для того, чтобы не учитывать повторно тарифный план одного и того же устройства (пользователя).
 
Для оценки критерия времени были выбраны следующие 3 интервала: 24.00-8.00 ч. (ночь), 8.00-20.00 ч. (день) и 20.00-24.00 ч. (вечер), с количествами измерений, N1, N2 и N3, соответственно. Количество белых карт рассчитывается по формуле, схожей по смыслу с формулами для предыдущих критериев:
 
Формула 12. Числитель дроби равен максимальному значению среди значений в скобках: N1, N2, N3.
 
Закончив расчет количества белых карт, необходимо вернуться к схеме Simos для расчета веса каждого из критериев [3].
 

Расчет матриц согласия, несогласия

Согласно работе [1], для любой пары альтернатив (провайдеров) Au и Av имеются вектора оценок для каждого из имеющихся N критериев: Zu=(Zu1,...,ZuN) . В нашем случае, Au и Av – это два сравниваемых провайдера, а zu – это набор значений критериев определенного провайдера связи. Выше было показано, как рассчитываются значения каждого из критериев. Коэффициент согласия αuv для сравнения операторов Au и Av вычисляется по формуле
 
Формула 13. Сумма всех весов критериев равна 100, Формула 14 . В числителе суммирование проводится только по тем значениям весов критериев, для которых значения критериев провайдера Au лучше, либо равны, значениям критериев провайдера Av. Таким образом, Формула 15 – это набор критериев, для которых Au лучше, чем Av, для этих критериев и проводится суммирование весов.
 
Коэффициент несогласия βuv для сравнения операторов Au и Av, вычисляется по формуле
 
Формула 16, где sj – размер шкалы соответствующего критерия. Сумма всех весов критериев равна 100. Максимальное значение выбирается среди тех значений критериев, где Au хуже, чем Av. Таким образом,Формула 17 – это набор критериев, для которых Au хуже, чем Av. Если таких критериев нет, т. е. Формула 18 , то значение коэффициента несогласия принимается равным нулю. В случае двух сравниваемых провайдеров, результирующие матрицы согласия (несогласия) имеют следующий общий вид:
 
Формула 19 . В матрице также присутствует абсолютный провайдер (αabs), задающий максимально возможные значения для каждого из критериев. Параметры для абсолютного провайдера выбираются равными значениям шкал критериев, данных выше.
 

Расчет рейтингов провайдеров

Для получения численного значения рейтинга каждого из провайдеров, используется следующая формула:
 
Формула 20, где j – номер провайдера, (n-1) – это число провайдеров без учета абсолютного провайдера. Формула показывает нормированную разницу между суммами коэффициентов согласия и несогласия для каждого из операторов. Для того чтобы рейтинги не были отрицательными, в случае, когда коэффициент согласия меньше коэффициента несогласия, шкала рейтингов сдвигается и нормируется. Итоговая формула имеет следующий вид: Формула 21
 

Обсуждение

До настоящего момент речь шла об измерениях, полученных по одному маршруту, т.е. если передача данных производится из города А в город Б с различных устройств, имеющих доступ в Интернет. В случае если имеются измерения по различным маршрутам и необходимо посчитать суммарный рейтинг, каждый из рейтингов входит в суммарный с весом, пропорциональным числу абонентов в городе, из которого производится измерение. В результате чего, рейтинги маршрутов с небольшим количеством пользователей войдут в суммарный рейтинг с меньшим весом, повышая приоритет маршрутов с большим числом пользователей.
 
Наиболее долгим по времени шагом является расчет значений критериев, т.е. выборочных средних и выборочных дисперсий. Со временем количество измерений может вырасти до сотен миллионов, поэтому важно, чтобы в алгоритм можно было добавлять новые выборки данных без пересчета предыдущих. Для рассмотрения возможности добавления новых данных, рассмотрим шаги, схематично описывающие работу всего алгоритма:
 
Шаг 1: Получение набора данных
 
Шаг 2: Определение весов критериев
 
Шаг 3: Расчет значений каждого из критериев (включая расчет сумм элементов выборки, сумм квадратов элементов и дисперсий всех критериев для каждого из провайдеров)
 
Шаг 4: Расчет матриц согласия и несогласия
 
Шаг 5: Расчет рейтингов по каждому из маршрутов и рейтинга в целом
 
Даже для нескольких сотен провайдеров шаги 4 и 5 занимают время на несколько порядков меньше, чем Шаг 3, включающий расчет сумм элементов. Поэтому очень важно не пересчитывать данные, полученные на этом шаге.
 
При добавлении следующей выборки данных, например, за следующий период времени (неделя, месяц) необходимо снова вернуться на Шаг 3 и рассчитать суммы и суммы квадратов элементов новой выборки. Очень важно также сохранять значения сумм, полученные для предыдущей выборки, так как они пригодятся для расчета значений критериев объединенной выборки. И так, при объединении двух выборок новые значения выборочного среднего и выборочной дисперсии рассчитываются следующим образом:
 
Формула 22 и Формула 23 . Объемы выборок предполагаются разными, N и K, для текущей и новой выборки, соответственно. Как видно из формул, зная суммы и суммы квадратов, рассчитать значения критериев для объединенной выборки не занимает много времени. Выборочная дисперсия является смещенной оценкой теоретической дисперсии, но разницей между смещенной и несмещенной оценками можно пренебречь при больших размерах выборки. Далее, как и прежде следует расчет новых матриц согласия/несогласия и новых рейтингов, занимающий относительно короткое время. Этот цикл повторяется каждый раз при добавлении новой выборки результатов измерений без необходимости пересчета результатов, полученных на предыдущем этапе.
 

Вывод

Разработан алгоритм многокритериальной оценки провайдеров связи Интернет. Данная методика реализована в программе wiRating и может использоваться пользователями сети Интернет для сравнения провайдеров в одном либо нескольких городах. По итогам работы программы рассчитываются рейтинги провайдеров, результаты представляются графически в виде гистограмм.
 

Литература

1. B. Roy, Multicriteria Methodology for Decision Aiding, Dordrecht: Kluwer Academic Publishers, 1996.
2. Б. Руа, Классификация и выбор при наличии многих критериев (метод ЭЛЕКТРА). В кн.: Вопросы анализа и процедуры принятия решений. – М.: Мир, 1976, – С. 80-107.
3. Jose Figueira, Bernard Roy Determining the weights of criteria in the ELECTRE type methods with a revised Simos’ procedure. // European Journal of Operational Research. – 2002. – Vol. 139. – P. 317–326.
 
УДК 004.021
 
Авторы: Ефимова О.В., Пирогов С.А., Семенов С.А.
 
Вверх