Расчет рейтинга и алгоритм сравнения интернет-провайдеров

 

, где N — общее количество измерений.

 

Значение критерия тарифных планов рассчитывается как выборочная дисперсия всех измерений скорости с устройств с уникальным идентификатором. Это было введено для того, чтобы не учитывать повторно тарифный план с устройства, с которого было получено несколько измерений скорости. В случае нескольких измерений для расчета берется максимальное значение. Формула для расчета:

 

, где N — это количество измерений, полученных с устройств с уникальным идентификатором.

 

Для расчета значения критерия времени вводится вектор [0.5 1.0 1.5] , элементы которого соответствуют следующим трем упомянутым выше периодам времени: ночь (24.00 - 8.00 ч), день (8.00 - 20.00 ч) и вечер (20.00 - 24.00 ч). Так как в вечернее нерабочее время число пользователей сети Интернет резко возрастает, этому периоду приписывается максимальный коэффициент, 1.5. В случае ночного периода, этот коэффициент минимальный, 0.5. Сам параметр критерия рассчитывается по формуле:

 

, где t_i – это одно из трех значений вектора [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, для критерия скорости определяется по следующей формуле:

 

, где am – амплитуда, соответствующая наиболее часто встречающейся скорости в гистограмме нормального распределения, нормированная на общее число измерений. Коэффициент 3 соответствует максимально возможному количеству белых карт и устанавливается независимо от измерений. Формула была выведена согласно следующим рассуждениям: чем больше разброс по скоростям и, соответственно, ниже максимальная амплитуда гистограммы, тем большую значимость получает критерий скорости. В этом случае количество белых карт стремится к максимальному. И наоборот, чем меньше разброс по скоростям, тем меньшее значение приобретает этот критерий с количеством белых карт, стремящимся к минимальному значению. Приведенную выше формулу можно также записать в следующем виде:

 

, где – это значение функции плотности вероятности в точке выборочного среднего. Нормальноераспределение задается функцией Гаусса:

 

. Принимая , получаем следующее выражение для функции плотности:

 

.

 

Аналогично рассчитывается численное значение критерия тарифных планов. Отличием является то, что дисперсия рассчитывается по измерениям скорости с устройств с уникальным идентификатором. Если с одного устройства получено несколько измерений, то берется максимальное значение. Это сделано для того, чтобы не учитывать повторно тарифный план одного и того же устройства (пользователя).

 

Для оценки критерия времени были выбраны следующие 3 интервала: 24.00-8.00 ч. (ночь), 8.00-20.00 ч. (день) и 20.00-24.00 ч. (вечер), с количествами измерений, N1, N2 и N3, соответственно. Количество белых карт рассчитывается по формуле, схожей по смыслу с формулами для предыдущих критериев:

 

. Числитель дроби равен максимальному значению среди значений в скобках: N1, N2, N3.

 

Закончив расчет количества белых карт, необходимо вернуться к схеме Simos для расчета веса каждого из критериев [3].

 

Согласно работе [1], для любой пары альтернатив (провайдеров) Au и Av имеются вектора оценок для каждого из имеющихся N критериев: Z_u=(Z_u1,...,Z_uN) . В нашем случае, Au и Av – это два сравниваемых провайдера, а zu – это набор значений критериев определенного провайдера связи. Выше было показано, как рассчитываются значения каждого из критериев. Коэффициент согласия αuv для сравнения операторов Au и Av вычисляется по формуле

 

. Сумма всех весов критериев равна 100, . В числителе суммирование проводится только по тем значениям весов критериев, для которых значения критериев провайдера Au лучше, либо равны, значениям критериев провайдера Av. Таким образом, – это набор критериев, для которых Au лучше, чем Av, для этих критериев и проводится суммирование весов.

 

Коэффициент несогласия βuv для сравнения операторов Au и Av, вычисляется по формуле

 

, где sj – размер шкалы соответствующего критерия. Сумма всех весов критериев равна 100. Максимальное значение выбирается среди тех значений критериев, где Au хуже, чем Av. Таким образом, – это набор критериев, для которых Au хуже, чем Av. Если таких критериев нет, т. е. , то значение коэффициента несогласия принимается равным нулю. В случае двух сравниваемых провайдеров, результирующие матрицы согласия (несогласия) имеют следующий общий вид:

 

. В матрице также присутствует абсолютный провайдер (αabs), задающий максимально возможные значения для каждого из критериев. Параметры для абсолютного провайдера выбираются равными значениям шкал критериев, данных выше.

 

Для получения численного значения рейтинга каждого из провайдеров, используется следующая формула:

 

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

 

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

 

Наиболее долгим по времени шагом является расчет значений критериев, т.е. выборочных средних и выборочных дисперсий. Со временем количество измерений может вырасти до сотен миллионов, поэтому важно, чтобы в алгоритм можно было добавлять новые выборки данных без пересчета предыдущих. Для рассмотрения возможности добавления новых данных, рассмотрим шаги, схематично описывающие работу всего алгоритма:

 

Шаг 1: Получение набора данных

 

Шаг 2: Определение весов критериев

 

Шаг 3: Расчет значений каждого из критериев (включая расчет сумм элементов выборки, сумм квадратов элементов и дисперсий всех критериев для каждого из провайдеров)

 

Шаг 4: Расчет матриц согласия и несогласия

 

Шаг 5: Расчет рейтингов по каждому из маршрутов и рейтинга в целом

 

Даже для нескольких сотен провайдеров шаги 4 и 5 занимают время на несколько порядков меньше, чем Шаг 3, включающий расчет сумм элементов. Поэтому очень важно не пересчитывать данные, полученные на этом шаге.

 

При добавлении следующей выборки данных, например, за следующий период времени (неделя, месяц) необходимо снова вернуться на Шаг 3 и рассчитать суммы и суммы квадратов элементов новой выборки. Очень важно также сохранять значения сумм, полученные для предыдущей выборки, так как они пригодятся для расчета значений критериев объединенной выборки. И так, при объединении двух выборок новые значения выборочного среднего и выборочной дисперсии рассчитываются следующим образом:

 

и . Объемы выборок предполагаются разными, 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

 

Авторы: Ефимова О.В., Пирогов С.А., Семенов С.А.