Размещение узлов для связи с мобильными абонентами

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

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

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

Рис. 4.3

Пусть мобильный абонент находится а точке с координатами Вероятность того, что он установит связь с центром равна где — расстояние от точки с (координатами до

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

Вероятность того, что ни с одним из узлов абонент не сможет установить связь,

Наихудшая точка имеет координаты Тогда

где максимум берется по всем точкам района.

Если задать координаты центра векторами им) и то решение сводится к определению таких векторов и , при которых обеспечивается

или, переходя к аддитивной целевой функции,

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

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

Если дифференцируема, то коэффициенты можно вычислить по формулам [66]:

В случае, когда решение дает пределяют перемещение центров, при котором уменьшается т. е. положение улучшается.

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

Шаг 0. Первоначальное случайное размещение узлов.

Шаг 1. Определение направления перемещения узлов, которое обеспечивает максимальное снижение (4.25).

Шаг 2. Соответствующее перемещение узлов и переход к шагу 1.

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

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

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

Число необходимых реализаций, (как обычно, определяется требованием к точности решения [24].

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