Алгоритм пересечения - Intersection algorithm

В алгоритм пересечения это алгоритм согласования, используемый для выбора источников для оценки точного времени из ряда шумный источники времени. Он является частью современного Сетевой протокол времени. Это модифицированная форма Алгоритм Марзулло.[1][2]

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

Метод

Данный M интервалы формы c ± р (что значит [c−р,c+р]) алгоритм пытается найти интервал с M−ж источники. Значение ж называется количеством фальшивок, тех источников, которые являются ошибочными (фактическое значение находится за пределами группа уверенности ). Наилучшая оценка - это то, что предполагает наименьшее количество фальшивомонетчиков, ж. Результаты будут считаться действительными, если ж < M/ 2, иначе алгоритм вернет ошибку вместо интервала.

Алгоритм пересечения начинается с создания таблицы кортежей <смещение, тип>. Для каждого интервала есть три записи: нижняя конечная точка, средняя точка и верхняя конечная точка, обозначенные типами -1, 0 и +1 соответственно. Таким образом, интервал c ± р приводит к записям <c−р,−1>, <c, 0> и <c+р, + 1>. Затем эти записи сортируются по смещению.

Переменные: этот алгоритм использует ж как количество ложных тикеров, конечный счет и средний счет целые числа. Нижняя и верхний - значения смещений.

  2. [initialize best f] Начать с ж= 0, если допустимы все входные интервалы. Каждый раз, когда интервал не будет найден, f будет увеличиваться до тех пор, пока не будет найден интервал или ж ≥ M/2.
  3. [инициализировать] конечный счет= 0 и средний счет=0.
  4. [найти нижнюю конечную точку] Начать с начала списка (наименьшее смещение) рассмотреть каждый кортеж по порядку. конечный счет = конечный счет−тип. Если конечный счет ≥ M−ж тогда ниже = смещение и перейти к шагу 3, поскольку найдена (возможная) нижняя конечная точка. Если тип = 0, тогда средний счет = средний счет+1. Повторите со следующим кортежем. Если дойдете до конца списка, перейдите к шагу 6.
  5. [Обнаружена предварительная нижняя конечная точка, инициализировать, чтобы найти верхнюю конечную точку] установлено конечный счет=0.
  6. [определить количество средних точек] Начните с конца списка и двигайтесь в сторону меньших смещений. конечный счет = конечный счет+тип. Если конечный счет ≥ M−ж тогда верхний = смещение, перейдите к шагу 5. Если тип = 0, тогда средний счет = средний счет+1. Повторите для следующего кортежа. Если дойдете до конца списка, перейдите к шагу 6.
  7. если ниже ≤ верхний и средний счет ≤ ж затем верните интервал [нижняя конечная точка,восходящая точка] как результирующий доверительный интервал.
  8. [увеличить количество фальцетов] ж = ж+1. Если ж ≥ M/ 2 затем завершить работу и вернуть FAILED, в противном случае перейти к шагу 1.

использованная литература

  1. ^ «RFC 1305 - Спецификация, реализация и анализ сетевого протокола времени (версия 3)». tools.ietf.org. 2013. Получено 6 октября, 2013. Функциональная спецификация службы цифрового времени Версия T.1.0.5. Корпорация цифрового оборудования, 1989 г.
  2. ^ Функциональная спецификация службы цифрового времени Версия T.1.0.5. Корпорация DigitalEquipment, 1989 г.