Размещено на http://www.allbest.ru/

О построении сложных неоднородных компьютерных сетей с использованием подвижных средств радиосвязи

М. В. Синьков, П. В. Трубников

Институт проблем регистрации информации НАН Украины

ул. Н. Шпака, 2, 03113 Киев, Украина

Cформулирована задача построения неоднородных компьютерных сетей и уделено внимание структурам части сети, связанной с подвижными средствами радиосвязи.

Ключевые слова: неоднородные компьютерные сети, подвижные средства радиосвязи, стационарные станции.

Постановка проблемы

Новые постановки задач в народном хозяйстве требуют новых подходов к компьютеризации, построению компьютерных сетей и привлечению к их функционированию в качестве источников информации новых нетрадиционных технических средств. К ним в полной мере относятся средства подвижной радиосвязи.

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

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

Анализ последних достижений и публикаций

Необходимо подчеркнуть, что несколько ранее [1, 2] такие подвижные сети связи практически использовались в основном силовыми структурами и системами обеспечения безопасности. В последнее время, по мере расширения классов решаемых задач, такие средства связи начинают применяться достаточно широко в энергетике, газовой и нефтяной промышленности. При этом, конечно, расширяется необходимость активного взаимодействия пользователей подвижной части с пользователями стационарных компьютерных сетей.

Цель работы

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

Результаты исследований

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

Вышесказанное позволяет сформулировать следующие основные задачи.

1. Определение оптимального числа стационарных станций и их размещение в заданном регионе со сравнительно гладким рельефом с целью обеспечения связью с любым абонентом в произвольной точке.

2. Задача п. 1 для негладкого рельефа местности и с учетом разновысотности отдельных частей заданного региона.

Рассмотрим приведенные выше задачи.

Пусть задана некоторая область с указанием частей, которые в обслуживании не нуждаются, а также частей, которые обслуживаются существующими средствами. При этом зона действия стационарной станции определяется заданной наименьшей допустимой вероятностью обеспечения связи с любым пользователем

Как подчеркивалось выше, рассматриваемая область может быть представлена в одном случае плоскостью, а в другом случае поверхностью, учитывающей специфику рельефа.

Для начала рассмотрим плоскую задачу. В этом случае плотное покрытие выбранной плоской зоны возможно тремя способами: 1) правильными одинаковыми треугольниками; 2) квадратами; 3) шестиугольниками. Предположим, что стационарная станция располагается в геометрическом центре указанных фигур. Тогда полный охват всей рассматриваемой области зависит от возможной плотной упаковки совокупностью из этих фигур. Наиболее предпочтительным вариантом является случай заполнения рассматриваемой области шестиугольниками. Это связано с тем, что правильный шестиугольник наилучшим образом заполняет круг. При этом возникнет некоторое перекрытие, которое повысит уверенный прием.

Покрытие выбранного региона может осуществляться стационарными станциями в двух основных вариантах: однотипными и разнотипными станциями.

Рассмотрим случай применения разнотипных станций. Покажем, что это не может дать оптимального решения по экономическому критерию. Действительно, пусть площадь всего региона обслуживания -- S. Площадь покрытия стационарной станцией i-го типа Si, а стоимость этой станции -- mi. Если количество станций i-го типа равно xi, то целевая функция задачи будет иметь вид

, (1)

где n -- число типов стационарных станций. Минимум необходимо найти при следующих ограничениях:

, (2)

. (3)

Задача (1)-(3) -- это обычная задача линейного программирования. Ограничения образуют в n-мерном пространстве многоугольник, лежащий на гиперплоскости (2), что показано на рисунке.

Размещено на http://www.allbest.ru/

Геометрическая интерпретация задачи (1)-(3)

Как известно из теории линейного программирования [3], экстремум функции (1) достигается только в вершинах этого многоугольника, которые лежат на осях координат. Поэтому все их координаты, кроме одной, имеют нулевые значения. То есть оптимальное решение задачи (1)-(3) имеет вид:

, (4)

. (5)

Таким образом, решение задачи сводится к выбору размеров ячейки гексагональной сети, которой необходимо покрыть заданную область. Выбор оптимального решения проводится простым сравнением целевой функции для различных типов стационарных станций.

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

Пусть задана область С, которая должна обслуживаться сетью стационарных станций

Pij(x, y).

Здесь i -- тип стационарной станции; она характеризуется зоной обслуживания, найденной по рельефу местности, и стоимостью Fi; j - текущий номер; x, y -- координаты стационарных станций.

В области С есть подобласти Сk:

, (6)

которые не нуждаются в обслуживании.

Таким образом, область обслуживания

(7)

Если есть набор стационарных станций

, (8)

то область, обслуживаемая ими:

, (9)

где -- область, покрываемая стационарной станцией i-го типа с номером j, расположенной в точке xj, yj c учетом рельефа местности. Для построения этой области требуется специальный алгоритм.

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

(10)

когда будет минимизироваться целевая функция

(11)

при выполнении условия

, (12)

т.е. область обслуживания полностью покрывается областями обслуживания всех стационарных станций.

Рассмотрим постановку задачи с неплоским рельефом местности региона в дискретном представлении.

Пусть С -- область, которую нужно покрыть связью. Ее можно описать с помощью матрицы принадлежности М.

Рассмотрим дискретную двумерную координатную сетку. Если дискрета i, j принадлежит области C, то элемент матрицы Мij равен единице, в противном случае нулю:

, (13)

(14)

Те области, обслуживание которых необязательно, можно описать обнулением соответствующих элементов матрицы М: Мij = 0, если i, j может не обслуживаться. Таким образом, область обслуживания полностью описывается матрицей принадлежности М размерностью n m

Обслуживание области С описывается матрицей обслуживания S. Она строится следующим образом. Пусть в точке i, j находится стационарная станция с областью покрытия . Поставим в соответствие ей матрицу Sr размерами n m. Матрицу Sr заполним по следующему правилу:

(15)

Это условие выражает принадлежность ячейки p, q к области обслуживания

Такая матрица обслуживания соответствует каждой стационарной станции системы. Для построения общей матрицы обслуживания S необходимо сложить матрицы обслуживания всех стационарных станций

, (16)

где n -- общее количество стационарных станций. Однако при этом некоторые элементы матрицы S могут быть больше 1. Это те элементы, которые соответствуют ячейкам перекрытия зон действия стационарных станций.

Чтобы S(i, j) принимало только два значения, что нужно для дальнейших построений, матрицу S нужно после выполнения сложения матриц (16) скорректировать по правилу

(17)

С учетом такого представления задача формулируется следующим образом.

Заданы:

Технические характеристики стационарных станций, позволяющие по рельефу местности построить область обслуживания

2. Экономические характеристики станции: Fi -- цена стационарной станции i-го типа.

Область обслуживания С, характеризуемая матрицей принадлежности М.

Необходимо определить такой набор стационарных станций и их координат

(18)

где -- номера типов; -- координаты расположения k-й стационарной станции, при этом будет минимизироваться суммарная стоимость всего оборудования

. (19)

При выполнении ограничения

компьютерный сеть стационарный связь

M = S. (20)

Это задача с линейной целевой функцией и нелинейными ограничениями.

Выводы

Задача покрытия местности сетью стационарных станций является оптимизационной задачей, использование результатов решения которой может дать существенный экономический эффект и повышение надежности связи.

Наилучшее покрытие заданного региона с плоским рельефом должно осуществляться совокупностью однотипных стационарных станций.

Решение задачи покрытия заданного региона с неплоским рельефом сводится к решению сформулированной выше оптимизационной задачи, для чего требуется создание и разработка соответствующего специального алгоритма.

Значительный интерес для теории и практики имеет задача обеспечения стабильной связью существенно увеличивающегося числа пользователей. Эта задача относится к задачам теории массового обслуживания и может быть сформулирована в следующем виде: определение оптимального числа стационарных станций и их размещение в заданном регионе с целью уменьшения вероятности отказа в связи при увеличении числа пользователей.

Литература

1. Ли У. Техника подвижных систем связи. -- М.: Радио и связь, 1985. -- 392 с.

2. Овчинников А.М., Воробьев С.В., Сергеев С.И. Открытые стандарты цифровой транкинговой радиосвязи. -- М.: Связь и бизнес, 2000. -- 166 с.

3. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. -- М: Физматгиз, 1963. -- 691 с.

Размещено на Allbest.ru