Содержание к диссертации
Введение
ГЛАВА 1. Способы построения беспроводных широкополосных сетей 10
Организация беспроводных широкополосных сетей 10
Классификация беспроводных технологий 14
Зона покрытия беспроводных широкополосных сетей 16
Показатели качества обслуживания беспроводных широкополосных сетей .21
Проблемы организации зоны покрытия беспроводных широкополосных сетей 22
Методы планирования зоны покрытия беспроводных широкополосных сетей 24
Модели пространственной организации беспроводных широкополосных сетей 26
Выводы по главе 29
ГЛАВА 2. Построение моделей и алгоритмов проектирования зоны покрытия беспроводных широкополосных сетей на плоскости 31
2.1. Постановка задачи моделирования зоны покрытия на плоскости 31
2.2. Решение задачи моделирования зоны покрытия на плоскости 31
2.3. Разработка математической модели пространственной организации беспроводных широкополосных сетей 32
2.4. Алгоритм построения зоны покрытия беспроводных широкополосных сетей по принципу нахождения точек множества с максимальным числом соседних точек 35
2.4.1. Модели построения зоны покрытия беспроводных широкополосных сетей, реализующие Алгоритм построения зоны покрытия беспроводных широкополосных сетей по принципу нахождения точек множества с максимальным числом соседних точек
2.5. Алгоритм построения зоны покрытия беспроводных широкополосных сетей основанный на понятии диаметра множества 51
2.5.1. Модели построения зоны покрытия беспроводных широкополосных сетей, реализующие Алгоритм построения зоны покрытия беспроводных широкополосных сетей основанный на понятии диаметра множества 52
Выводы по главе 62
ГЛАВА 3. Разработка моделей и алгоритмов пространственной организации беспроводных широкополосных сетей 63
3.1. Постановка задачи моделирования зоны покрытия в пространстве 63
3.2. Решение задачи моделирования зоны покрытия в пространстве 63
3.3. Алгоритм построения зоны покрытия беспроводных широкополосных сетей по принципу нахождения точек множества с максимальным числом соседних точек 64
3.3.1. Модели построения зоны покрытия беспроводных широкополосных сетей, реализующие Алгоритм построения зоны покрытия беспроводных широкополосных сетей по принципу нахождения точек множества с максимальным числом соседних точек 65
3.4. Алгоритм построения зоны покрытия беспроводных широкополосных сетей основанный на понятии диаметра множества 75
3.4.1. Модели построения зоны покрытия беспроводных широкополосных сетей, реализующие Алгоритм построения зоны покрытия беспроводных широкополосных сетей основанный на понятии диаметра множества 75
Выводы по главе 104
ГЛАВА 4. Организация зоны покрытия беспроводных широкополосных сетей офиса страховой компании 105
Проектирование зоны покрытия 105
Выводы по главе 117
Заключение 118
Литература
- Показатели качества обслуживания беспроводных широкополосных сетей
- Разработка математической модели пространственной организации беспроводных широкополосных сетей
- Алгоритм построения зоны покрытия беспроводных широкополосных сетей основанный на понятии диаметра множества
- Алгоритм построения зоны покрытия беспроводных широкополосных сетей по принципу нахождения точек множества с максимальным числом соседних точек
Введение к работе
Актуальность темы. В настоящее время беспроводные сети передачи информации являются одним из основных направлений развития телекоммуникационной индустрии. В течение нескольких последних лет беспроводные сети проходили процесс стандартизации, повышалась скорость передачи данных, цена становилась доступнее. В настоящее время беспроводные сети позволяют производить подключение там, где затруднено кабельное соединение или необходима полная мобильность; при этом они совместимы с проводными сетями. Необходимо так же принимать во внимание то, что беспроводные решения при проектировании сетей любого масштаба - от малого офиса до предприятия - экономят средства и время. Быстрота развертывания, широкие функциональные возможности по передаче трафика данных, IP-телефонии, видео, низкая стоимость - все это делает беспроводную технологию одним из самых быстрорастущих телекоммуникационных направлений.
Одной из важных задач при построении беспроводных широкополосных сетей является проектирование зон покрытия, которое предназначено для обеспечения заданного качества приема по всей области обслуживания. На этом этапе определяются граничные участки обслуживаемой территории, обеспечивающие заданное качество приема сигналов, уточняются частотные и мощностные характеристики передатчиков базовых станций. Процесс проектирования зоны покрытия представляет многопараметрическую итерационную задачу со многими неизвестными, требующую соответствующих ресурсов и времени на обработку данных, таких как: количество соединительных линий, пропускная способность каналов связи и т.д. Проблемам проектирования зоны покрытия беспроводных широкополосных сетей посвящено значительное количество работ, среди которых следует отметить работы российских и зарубежных ученых: В. М. Вишневского, С. Портного, И. Шахновича, G. Balbo, S. C. Bruell, L. Fratta, L. Kleinrock, M. Olivetty, H. Takagi, S.C. Borst, O.J. Boxma и др.
Таким образом, задача разработки моделей и алгоритмов пространственной организации зоны покрытия широкополосной сети является центральной при повышении качества обслуживания и сокращении времени передачи данных. Кроме того, необходимо разработать модели и алгоритмы пространственной организации беспроводной широкополосной сети, обеспечивающих своевременную и надежную передачу информации, которые повысят коэффициент использования полосы пропускания, сократят время реагирования базовой станции на запросы абонентских станций, а также обеспечат качество обслуживания (QoS) для различных видов трафика.
Цель диссертационной работы состоит в разработке моделей и алгоритмов проектирования непрерывной зоны покрытия беспроводной широкополосной сети и обеспечении качества обслуживания для любого числа потенциальных клиентов в пределах заданной территории.
Объектом исследования являются беспроводные широкополосные сети.
Предмет исследования - модели и алгоритмы пространственной организации беспроводных широкополосных сетей, обеспечивающих качественную доставку информации и высокоскоростную передачу данных в любое время и в любом месте зоны покрытия сети для максимального числа клиентов.
Задачи исследований. Для достижения указанной цели в работе сформулированы и решены следующие задачи:
-
Анализ способов организации беспроводных широкополосных сетей, методов и моделей проектирования зоны покрытия беспроводной широкополосной сети.
-
Исследование зоны покрытия беспроводной широкополосной сети, ее основных свойств и параметров.
-
Разработка математических моделей и алгоритмов пространственной организации беспроводных широкополосных сетей.
Методы исследований. Для достижения поставленной цели в диссертационной работе используются методы теории передачи информации, теории вероятностей, теории графов, дискретной математики, численных методов.
На защиту выносятся следующие основные результаты:
комплекс математических моделей пространственной организации беспроводных широкополосных сетей;
алгоритмы проектирования зоны покрытия;
Научная новизна полученных результатов заключается в разработке математических моделей и алгоритмов пространственной организации инфраструктуры беспроводных систем, позволяющих повысить качество функционирования с учетом требований к обслуживанию, а также системы моделирования зоны покрытия беспроводной широкополосной сети.
Практическая ценность и реализация результатов диссертации.
Результаты работы внедрены и используются на практике, что подтверждено соответствующими актами. Практическая значимость диссертационной работы состоит в следующем:
разработанные математические модели и алгоритмы позволяют научно обоснованно решать задачи проектирования зоны покрытия беспроводных широкополосных сетей;
разработанные математические модели и алгоритмы обеспечивают условия для передачи данных в сети с заданным качеством, за счёт наилучшего варианта размещения элементов ифрастуктуры сети, сокращение затрат и расширение областей применения.
Результаты, полученные в диссертационной работе, имеют как теоретическое, так и прикладное значение и могут найти свое применение при анализе и построении беспроводных широкополосных сетей. Разработанные алгоритмы были использованы при проектировании зоны покрытия сети офиса страховой компании ОАО СК «Альянс» для подключения абонентов к voip- серверу, обеспечивающее передачу голосовой и видеоинформации. Результаты диссертационной работы использованы в учебном процессе кафедры «Вычислительных систем и сетей» МИЭМ при изучении дисциплин на курсах «Новые информационные технологии», «Беспроводные сети и мобильные системы».
Достоверность научных результатов, выводов и рекомендаций, сформулированных в диссертации, базируется на комплексном применении теоретических и экспериментальных методов исследования. Проверка теоретических положений, разработанных в диссертационной работе, осуществлялась с помощью компьютерного моделирования и промышленного внедрения.
Апробация диссертационной работы. Положения данной диссертации докладывались и обсуждались на следующих конференциях:
на международных научно-технических конференциях «Information and Telecommunication Technologies in Intelligent Systems» (Швейцария, 2010 г);
на 14-ой Международной конференции «Распределенные компьютерные и телекоммуникационные сети: теория и приложения» (DCCN-2010);
на научно-методических совещаниях и семинарах ОАО СК «Альянс»;
на научно-технических конференциях студентов, аспирантов и молодых специалистов МИЭМ (2008 - 2011 гг.);
на научно-технических семинарах кафедры «Вычислительные системы и сети» МИЭМ (2008 - 2011 гг.).
Публикации. Основное содержание диссертационной работы и ее результатов отражено в научных и научно-технических работах автора. Всего автором опубликовано 7 научных работ из них 3 в журналах из перечня ВАК.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников. Работа изложена на 125 страницах, содержит 6 иллюстраций, 3 таблицы.
Показатели качества обслуживания беспроводных широкополосных сетей
Широкополосные системы и сети - это пространственно-распределенные системы массового обслуживания, которые позволяют передавать, накапливать и распределять информационные данные, тексты, изображения, передавать аудио и мультимедийную информацию, осуществлять передачу стереофонических программ, обеспечивать доставку электронной почты, а также предоставлять услуги Internet.
Для построения широкополосных сетей в настоящие время все чаще используются беспроводные каналы доступа[38].
Беспроводные широкополосные сети (БПШС) передачи данных позволяют объединить в единую информационную систему разрозненные локальные сети и компьютеры для обеспечения доступа всех пользователей этих сетей к единым информационным ресурсам без прокладки дополнительных проводных линий связи. БПШС обычно создаются в тех случаях, когда прокладка кабельной системы затруднена или экономически нецелесообразна. Примером могут служить предприятия, имеющие распределенную структуру (складские помещения, отдельные цеха, карьеры и пр.), наличие естественных преград при построении кабельных систем (рек, озер и т.д.), предприятия, арендующие офисы на небольшой срок, выставочные комплексы и гостиницы, предоставляющие доступ в Интернет для своих клиентов. Беспроводные сети уменьшают затраты на планирование и подготовку рабочего пространства, а также обновление оборудования и периферии [5],[13-17],[71-78].
Организация беспроводных широкополосных сетей Инфраструктура Инфраструктура беспроводной сети обеспечивает беспроводное взаимодействие пользователей и оконечных систем. Ее могут образовывать базовые станции, контроллеры доступа, программное обеспечение приложений, обеспечивающих установление соединений, и распределительная система. Эти компоненты участвуют в беспроводной связи и выполняют важные функции в конкретных применениях[ 10-12],[143].
Базовая станция — распространенный компонент инфраструктуры. Она обеспечивает передачу информационных сигналов беспроводных сетей, распространяющихся через воздушную среду, в проводную сеть, ее иногда называют распределительной системой [23],[25],[31],[33],[110].
Название базовой станции зависит от выполняемых ею функций. Например, точка доступа (access point) — это основная базовая станция беспроводных локальных сетей. Шлюзы и маршрутизаторы локальной сети — это примеры базовых станций с расширенными возможностями, обеспечивающих выполнение дополнительных функций в сети [59],[70].
Базовая станция может поддерживать соединения типа «точка-точка» или «точка-несколько точек». Системы типа «точка-точка» используется для организации протяженных беспроводных каналов связи. В случае конфигурации «точка-несколько точек» базовая станция может связываться с более чем одним компьютерным устройством или не с несколькими базовыми станциями [67].
Контроллер доступа обычно представляет собой аппаратный узел, располагаемый в проводной части сети, между точками доступа и защищаемой частью сети. Контроллеры доступа обеспечивают централизованный надзор за точками доступа с целью регулирования трафика между открытой беспроводной сетью и важными ресурсами. В некоторых случаях функции управления доступом выполняет точка доступа [140].
Помимо простых приложений, для доступа в интернет и функционирования особых, более сложных приложений через БПШС необходимо программное обеспечение такое, как интерфейс между пользовательским компьютерным устройством и оконечной системой, выполняющей приложение или содержащей базу данных. К ним относятся базы данных со структурой клиент-сервер, в которых часть или вся программа приложения располагается на клиентском устройстве и взаимодействует с СУБД. В таких случаях в дополнение к точкам доступа и контроллерам для осуществления связи между пользовательским компьютерным устройством и программой приложения либо базой данных, расположенной на централизованном сервере, важно иметь программное обеспечение, поддерживающее необходимое для работы подобных приложений соединение [111-114].
Основные типы приложений, обеспечивающих соединения:
Эмулятор терминала (therminal emulation). Программное обеспечение эмуляции терминала выполняется на компьютерном устройстве и заставляет его работать как терминал, обеспечивающий пользователя относительно простым интерфейсом, позволяющим ему взаимодействовать с приложением, выполняемым на другом компьютере.
Прямое соединение с базой данных (direct database connectivity). В случае прямого соединения с базой данных, что иногда называется технологией клиент-сервер, приложение выполняется на компьютерном устройстве пользователя. При такой конфигурации программное обеспечение на устройстве конечного пользователя выполняет все функции, возложенные на приложение, и обычно взаимодействует с базой данных, размещенной на центральном сервере.
Промежуточное программное обеспечение (wireless middleware). Осуществляет промежуточное соединение между пользовательским компьютерным устройством и программным обеспечением приложения или базой данных, размещенными на сервере[115-119].
Разработка математической модели пространственной организации беспроводных широкополосных сетей
Тепловой шум является результатом теплового движения электронов. Если сигналы разной частоты передаются в одной среде, может иметь место интермодуляционный шум.
Интермодуляционным шумом являются помеха, возникающие на частотах, которые представляют собой сумму, разность или произведение частот двух исходных сигналов. Например, смешивание двух сигналов, передаваемых на частотах f и їг соответственно, может привести к передаче энергии на частоте f + ґг.
Перекрестные помехи возникают вследствие нежелательного объединения трактов передачи сигналов. Перекрестные помехи могут возникать во время приема посторонних сигналов антеннами. Причиной дополнительных потерь мощности сигнала между передающей и принимающей антеннами является атмосферное поглощение, при этом основной вклад в ослабление сигнала вносят водные пары и кислород. Дождь и туман (капли воды, находящиеся во взвешенном состоянии в воздухе) приводят к рассеиванию радиоволн и, в конечном счете, к ослаблению сигнала. Указанные факторы могут быть основной причиной потерь мощности сигнала.
Показатели качества обслуживания беспроводных широкополосных сетей В настоящее время остро стоит вопрос обеспечения качества обслуживания QoS (Quality of Service) в беспроводной широкополосной сети. QoS - способность сети обеспечить необходимый сервис заданному трафику в широких технологических рамках.[1]
Необходимый сервис описывается многими параметрами. Отметим среди них самые важные. Качество обслуживания определяется следующими факторами:
Доступность - диапазон времени сетевой достижимости между входной и выходной точкой сети - это сетевая доступность. Доступность сети - это диапазон времени, в течение которого сеть доступна между определенными входной и выходной точками с параметрами, оговоренными в соглашении об уровне обслуживании (SLA).
Потери - это отношение правильно принятых пакетов к общему количеству пакетов, которые были переданы по сети. Потери выражаются в процентах отброшенных пакетов, которые не были доставлены по назначению. Обычно потери - это функция от доступности. Если сеть не загружена, то потери (во время отсутствия перегрузок) будут равны нулю. Во время перегрузок, однако, механизмы QoS будут определять, какие пакеты могут быть сброшены.
Задержка - это время, которое требуется пакету для того, чтобы после передачи дойти до пункта назначения. В случае голосовой передачи эта задержка определяется как время прохождения сигнала от говорящего к слушающему.
Колебания задержки - это разница между сквозным временем задержки, которая возникает при передаче по сети разных пакетов. Так, например, если для передачи одного пакета по сети требуется 100 мсек, а для передачи следующего пакета - 125 мсек, то колебание задержки составит 25 мсек.
Пропускная способность - это доступная пользователю полоса пропускания между двумя точками присутствия оператора.
Проблемы организации зоны покрытия беспроводных широкополосных сетей Любое здание имеет как капитальные стены, выполненные из кирпича или железобетона, так и обычные перегородки. Прохождение радиосигнала через капитальные стены можно считать весьма условным. В лучшем случае обеспечивается работа беспроводного оборудования в соседнем помещении причем, как правило, неуверенная. Причина заключается в том, что высокочастотный сигнал практически полностью поглощается и частично отражается поверхностью стены, которая в данной ситуации выступает в роле экрана. Перегородки (например, гипсокартон), ввиду значительно меньшей толщины и отсутствия армирования металлической сеткой, являются намного менее серьёзным препятствием, тем не менее, дают ощутимые потери. В любом случае выполнить беспроводное покрытие даже одного этажа здания с помощью обычной точки доступа практически нереально. Неизбежно образуются мертвые зоны, зоны с неуверенным покрытием и зоны в которых вообще нет сигнала[123-127].
Установлены 3 точки доступа (рис.1.1.), расположенные в разных помещениях офиса. Поскольку стены между комнатами выполнены из разного материала (перегородки и капитальные стены), то зоны покрытия каждой из точек доступа различны. Неизбежно образовались зоны с неуверенным покрытием, а в Холле 2 и Комнатах 205/205а зоны одновременного приема сигнала двух точек доступа (частично пересекающееся покрытие зон).
Алгоритм построения зоны покрытия беспроводных широкополосных сетей основанный на понятии диаметра множества
Во входных данных в модели рокЗ третьей координатой точек стал вектор е (формальная переменная), а в выходных данных третьей координатой центров стал вектор L. Кроме того, внутри модели третья координата ещё не покрытых точек запоминается в векторе и, тогда как первые две - в векторах v и w , соответственно. Все три переменных е, L и и ранее не использовались. В фактических данных к координатам X и 7 множества из 100 точек добавилась третья координата - вектор Z, а к координатам аиЬ множества из десяти точек добавилась третья координата - вектор с. Результаты выполнения модели рокЗ имеют теперь тоже три координаты. На трёхмерном множестве точек можно выполнять алгоритмы с предыдущими ограничениями и по числу точек у центра и при наличии ограниченного числа новых центров большего радиуса и неограниченного количества старых центров меньшего радиуса. Модели распределения точек между центрами тоже должны стать трёхмерными. Задача минимального покрытия множества точек решается в системах беспроводного сбора данных, когда объекты, поставляющие данные, неподвижны или мобильны.
Установлено, что первый алгоритм более универсальный, чем второй. Он позволяет реализовать все ограничения при решении задачи покрытия множества.
Второй алгоритм более быстродействующий и даёт более равномерное распределение точек между центрами. 1. Разработана обобщенная математическая модель организации беспроводной широкополосной сети на плоскости, обеспечивающая нахождение областей зоны покрытия и их центров для инфраструктуры беспроводной сети с учетом заданных ограничений и критериев. 2. Разработан комплекс алгоритмов и моделей организации беспроводной широкополосной сети на плоскости, который позволяет найти решение задачи покрытия множества точек: построение зоны покрытия по принципу нахождения точек множества с максимальным числом соседних точек; построение зоны покрытия основанное на понятии диаметра множества. 3. Проведено исследование свойств, особенностей применения алгоритмов и моделей в режиме моделирования зоны покрытия для случайной и заданной топологии сети, которое позволило выявить преимущества использования каждого алгоритма и модели. 4. Определены условия моделирования области покрытия беспроводной широкополосной сети. Проектирование БПШС является сложной многопараметрической задачей, решение которой возможно лишь при использовании системного подхода, учитывающего как расчет канала радиосвязи, частотно-территориальное планирование радиосетей, так и гарантированное обеспечение качества обслуживания всех абонентов сети.
Цель проектирования беспроводной широкополосной сети состоит в нахождении оптимальной зоны покрытия и достигается оптимальным выбором расположения базовых станций.
Основное требование - обеспечение качества обслуживания клиентов. Исходные данные - планировка помещений, проницаемость стен, перегородок, мебели и оборудования; число и расположение клиентов, скорость передачи данных. Постановка задачи - создание непрерывной зоны покрытия и обеспечение качества обслуживания для любого числа потенциальных клиентов в пределах заданной территории. Критерий качества обслуживания - обеспечение гарантированного клиентского трафика в любое время и в любом месте зоны покрытия сети для максимального заданного числа клиентов.
Задача проектирования зоны покрытия беспроводной широкополосной сети представляется как пространственная задача о минимальном покрытии множества точек в пространстве сферами радиуса R. Так же, как и в задаче моделирования на плоскости, каждая из множества точек должна быть покрыта как минимум одним сферой радиуса R. Определить для заданного множества точек в пространстве минимальное количество покрывающих их сфер радиуса R и расположение этих сфер в пространстве.
Рассмотрим случай, когда центры сфер должны быть расположены в покрываемых точках пространства. В этом случае задача имеет точное решение, которое можно найти методом прямого перебора.
Для определения минимального количества покрывающих сфер находится диаметр множества точек в пространстве - это максимальное расстояние между двумя точками множества. Другими словами, диаметр - это расстояние между двумя самыми удалёнными точками покрываемого множества. Диаметр множества делится на радиус R и результат округляется до ближайшего целого числа - получается минимальное число min покрывающих множество сфер. Метод прямого перебора рассматривает все наборы точек из множества мощности п по этому минимальному числу min и проверяет, все ли точки множества, не попавшие в этот набор, находятся на расстоянии, не большем R от одной из точек набора. Проверяется, таким образом, все ли точки множества оказались покрыты сферами с центрами в точках данного набора точек. Если хотя бы один такой набор найден, то перебор прекращается. Если для данного числа min такого набора не найдено, то min увеличивается на единицу и поиск продолжается. Время выполнения такой процедуры пропорционально 2 в степени п. Если число точек невелико, то можно применить и метод прямого перебора для нахождения минимального числа покрывающих множество сфер.
Построение зоны покрытия беспроводных широкополосных сетей по принципу нахождения точек множества с максимальным числом соседних точек.
Для множества точек большой мощности обычно используются эвристические алгоритмы, в которых для каждой из точек множества определяется количество соседних с ней точек множества, находящихся от неё не далее, чем на радиус R. Затем находится точка с максимальным числом таких соседей. Эта точка считается первым центром первого покрывающей сферы, если число её соседей (максимальное в множестве) больше нуля. После назначения первого центра и сам первый центр и его соседи удаляются из множества точек. Далее на следующих этапах алгоритма процедура поиска центров продолжается на уменьшающемся множестве точек, пока максимальное число соседей у всех точек не станет равным нулю, то есть останутся редкие разрозненные точки, или вообще точек не останется. Все эти оставшиеся точки (если они будут) тоже станут центрами покрывающих сфер.
Такой алгоритм выполняется быстро, но может и не найти оптимального решения. При выполнении такого алгоритма первые центры получат много соседей для последующего их обслуживания, а последние - мало, или вообще не получат их. Процедуру распределения точек между центрами можно выполнять и одновременно с назначением центров и после него. Во втором случае можно несколько сгладить неравномерное распределение точек между центрами, если начать распределять точки между центрами, начиная с центров, которые были назначены последними. В этом случае есть надежда, что слабо нагруженные центры заберут некоторые точки у сильно нагруженных центров.
Алгоритм построения зоны покрытия беспроводных широкополосных сетей по принципу нахождения точек множества с максимальным числом соседних точек
Результат работы модели pokpr(z,y,e,cb,r) несколько отличается от результатов работы моделей pokd3(x,y,e,cb,r) и pokcb(x,y,e,cb,r), но только по форме представления данных. Вместо координат покрывающих центров для уменьшения объёма модели в качестве результата выдаются их номера из вектора cb. Например, для первых трёх примеров работы pokpr(z,y,e,cb,r) из десяти точек возможными центрами являются нулевая, четвёртая и девятая точки множества (вектор СВ).
Первый и третий примеры с вектором СВ с радиусами десять и пять соответственно дают в качестве результата нулевой и первый элементы вектора СВ и, значит, покрывающими центрами являются нулевая и четвёртая точки множества. Второй пример с вектором СВ с радиусом семь даёт в качестве результата нулевой и второй элементы вектора СВ и, значит, покрывающими центрами являются нулевая и девятая точки множества. Координаты покрывающих центров можно взять из координат множества, имея номера покрывающих центров в множестве точек[37].
Далее, для последних четырёх примеров работы модели pokpr(z,y,e,cb,r) из десяти точек возможными центрами являются пять: с нулевой до четвёртой включительно (вектор сВ). Четвёртый пример с вектором сВ с радиусом десять даёт в качестве результата нулевой и первый элементы вектора сВ и, значит, покрывающими центрами являются нулевая и первая точки множества. Пятый пример с вектором сВ с радиусом семь даёт в качестве результата первый и второй элементы вектора сВ и, значит, покрывающими центрами являются первая и вторая точки множества.
В шестом и седьмом примерах с радиусами пять и четыре соответственно одна и та же точка из множества осталась не покрытой. Шестой пример с вектором сВ с радиусом пять даёт в качестве результата нулевой, второй и третий элементы вектора сВ, значит, покрывающими центрами являются нулевая, вторая и третья точки множества. Седьмой пример с вектором сВ с радиусом четыре даёт в качестве результата все пять возможных покрывающих центров и покрывающими центрами являются первые пять точек множества с нулевой по четвёртую включительно.
Работа модели показана на семи примерах для множества из десяти точек, координаты которых заданы векторами а, Ъ и с. Решений, обеспечивающих минимальное покрытие множества по числу покрывающих это множество центров и полученных как точными, так и эвристическими алгоритмами, может быть несколько. Несложно доработать все три модели так, чтобы можно было получить в качестве результата все такие решения и выбрать из них по неким критериям предпочтительное. Возможно и внесение самих этих критериев в модель.
Альтернативным ограничением задачи о минимальном покрытии, когда некоторые точки не могут быть покрывающими центрами, является ограничение, когда некоторые точки обязательно будут покрывающими центрами. Это альтернативное ограничение нетрудно учесть, убрав из множества точек эти обязательные покрывающие центры вместе с точками, которые они обслуживают, и решать задачу о минимальном покрытии на этом уменьшенном множестве точек в пространстве.
Ограничения, когда точки могут или не могут быть покрывающими центрами, возникают при создании дублирующей системы покрывающих множество точек в пространстве сфер радиуса г с центрами в точках этого множества. В принципе, любой из покрывающих центров может выйти из строя и требуется время, для того чтобы починить или заменить этот не исправный центр. Дублирующая система может быть создана двумя способами.
Первый способ — это когда для каждого центра может быть выделена дублирующая его обычная точка или обычные точки, которая или которые становятся центрами только при выходе из строя дублируемого ей или ими центра. После ремонта или замены неисправного центра дублирующая его точка или точки возвращаются в своё обычное состояние.
Для получения дубля каждого центра надо взять все точки, которые дублируемый центр обслуживает (в том числе и сам дублируемый центр) и определить покрывающие центры с тем ограничением, что дублируемый центр не может быть возможным покрывающим центром. Тут возможно и точное решение задачи с помощью модели pokpr(z,y,e,cb,r). Вектор сЪ будет иметь длину, на единицу меньшую, чем длины векторов с координатами точек покрываемого множества. Модель pokpr(z,y,e,cb,r) можно использовать при небольшой мощности покрываемого множества, когда ограничений на точки нет. В случае если все точки являются возможными центрами, длина вектора сЪ совпадает с длиной векторов с координатами. При этом значения элементов вектора сЪ совпадают с номерами этих элементов в этом векторе.
Второй способ - это создание дублирующей системы из обычных точек. Если какой-то из центров основной системы выходит из строя, то сразу начинает работать дублирующая система, все центры которой отличаются от центров основной системы минимального покрытия. Разумеется, основная система должна покрывать все точки множества, в том числе и центры дублирующей системы покрытия, и дублирующая система должна покрывать все точки множества, в том числе и центры основной системы минимального покрытия.
Для получения дубля всей системы покрывающих центров надо взять всё множество точек, которые дублируемая система центров обслуживает (в т. ч. и все покрывающие центры дублируемой системы) и определить покрывающие центры с тем ограничением, что все центры дублируемой системы минимального покрытия не могут быть возможными покрывающими центрами.
