 
Оглавление
Организационно-технические системы: проектирование, функционирование, эксплуатация 2
ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ПРЕДЕЛЬНЫХ СВОЙСТВ РЕШЕНИЯ ДВУХУРОВНЕВОЙ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В БЕСПРОВОДНЫХ СЕТЯХ 2
ОБ ОДНОМ МЕТОДЕ РЕШЕНИЯ ПРОСТРАНСТВЕННЫХ НЕЛИНЕЙНЫХ КРАЕВЫХ ЗАДАЧ ДЛЯ УПРУГОГО НЕОДНОРОДНОГО ПОЛУШАРА 15
АНАЛИЗ И РАСЧЁТ НОРМАЛЬНОЙ РЕАКЦИИ ДАВЛЕНИЯ ДИСКОВОГО НОЖА НА МАТЕРИАЛ 24
ИССЛЕДОВАНИЕ ГАЗОДИНАМИЧЕСКИХ И ЭНЕРГЕТИЧЕСКИХ ПАРАМЕТРОВ ГЕНЕРАТОРА ОБЪЁМНОЙ ПЛАЗМЫ 30
ПРОЕКЦИОННЫЕ И ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ 39
РЕГУЛЯРНЫХ ИНТЕГРАЛЬНЫХ УРАВНЕНИЙ 39
МЕТОДИКА МАТЕМАТИЧЕСКОЙ ОБРАБОТКИ 52
ЭКСПЕРИМЕНТАЛЬНЫХ ДАННЫХ 52
ДЛЯ ПОЛУЧЕНИЯ ОБОБЩЕННЫХ ХАРАКТЕРИСТИК ПРОЦЕССОВ 52
ОПТИКО-ЭЛЕКТРОННЫЙ метод ИССЛЕДОВАНИЯ ЗОНЫ ЛАЗЕРНОЙ ЗАКАЛКИ МЕТАЛЛОВ 59
ПРИМЕНЕНИЕ МНОГОАГЕНТНОЙ СИСТЕМЫ ДЛЯ СОВЕРШЕНСТВОВАНИЯ УПРАВЛЕНИЯ ПРОЦЕССАМИ В ВАКУУМНО-НАПЫЛИТЕЛЬНЫМ ТЕХНОЛОГИЧЕСКИМ КОМПЛЕКСЕ 70
ВНЕДРЕНИЕ СКОРИНГА И ЕГО РЕАЛИЗАЦИЯ ПОСРЕДСТВОМ ДИСКРИМИНАНТНОГО АНАЛИЗА И НЕЙРОННЫХ СЕТЕЙ 79
Исследования человека и социальных систем 85
ОСОБЕННОСТИ ОРГАНИЗАЦИИ УЧЕБНЫХ ЗАНЯТИЙ ПО ФИЗИЧЕСКОМУ ВОСПИТАНИЮ В ВУЗЕ С УЧЕТОМ ЗДОРОВЬЕСБЕРЕГАЮЩИХ ОБРАЗОВАТЕЛЬНЫХ ТЕХНОЛОГИЙ 85
ИСПОЛЬЗОВАНИЕ БИОИМПЕДАНСНОГО АНАЛИЗА СОСТАВА ТЕЛА В ПРАКТИКЕ ТРЕНЕРА ПО АКВААЭРОБИКЕ 93
СУЩНОСТЬ ОБСТОЯТЕЛЬСТВ, СМЯГЧАЮЩИХ 101
АДМИНИСТРАТИВНУЮ ОТВЕТСТВЕННОСТЬ 101
Язык в системе коммуникаций: филологические и лингвистические исследования 107
ФУНКЦИОНАЛЬНОЕ ПОЛОЖЕНИЕ РЕГИОНАЛЬНЫХ ЯЗЫКОВ В РОССИЙСКИХ РЕГИОНАХ 107
РАЗВИТИЕ СИСТЕМЫ ПОВЫШЕНИЯ КВАЛИФИКАЦИИ ПЕДАГОГИЧЕСКИХ КАДРОВ РЕСПУБЛИКИ ТАТАРСТАН В КОНЦЕ 50-Х – НАЧАЛЕ 60-Х ГГ. XX В. 116
ОСЛОЖНЕННОЕ ПРЕДЛОЖЕНИЕ В СТИЛЕ НАУЧНОЙ РЕЧИ АНГЛИЙСКОГО, КАЗАХСКОГО И РУССКОГО ЯЗЫКОВ 125
ФОРМЫ И МЕТОДЫ ИСПОЛЬЗОВАНИЯ СТРАНОВЕДЧЕСКОГО МАТЕРИАЛА НА УРОКАХ АНГЛИЙСКОГО ЯЗЫКА 132
УНИВЕРСАЛЬНЫЕ И НАЦИОНАЛЬНЫЕ ОСОБЕННОСТИ ЯЗЫКОВОЙ КАРТИНЫ МИРА 141
О ВОПРОСАХ ПОЛИЯЗЫЧНОГО ОБРАЗОВАНИЯ В ДОУ 158
ПОЛИТИЧЕСКИЕ, СОЦИАЛЬНО-КУЛЬТУРНЫЕ И ЭКОНОМИЧЕСКИЕ ОСНОВЫ ФУНКЦИОНАЛЬНОГО РАЗВИТИЯ ТАТАРСКОГО ЯЗЫКА: ИСТОРИЧЕСКИЙ АСПЕКТ 165
РОЛЬ УЧЕБНОЙ ДИСКУССИИ ПРИ ОБУЧЕНИИ ИНОСТРАННОМУ ЯЗЫКУ 173
ПАРЕМИИ, ХАРАКТЕРИЗУЮЩИЕ ПОНЯТИЕ «ЗЛОЙ ДУХ» В АНГЛИЙСКОМ И РУССКОМ ЯЗЫКАХ (СТРУКТУРНО-ГРАММТИЧЕСКИЙ АНАЛИЗ) 181
НЕМЕЦКИЙ ИСТОРИЧЕСКИЙ РОМАН В ПАРАДИГМЕ ПОСТМОДЕРНИЗМА (НА ПРИМЕРЕ ТВОРЧЕСТВА С. НАДОЛЬНОГО) 189
О ГЛУБИННОЙ И ПОВЕРХОСТНОЙ СТРУКТУРЕ (НА МАТЕРИАЛЕ АНГЛИЙСКОГО СОЮЗА ‘THAT’) 198
Организационно-технические системы: проектирование, функционирование, эксплуатация
УДК 519.85
Кашина О.А, кандидат физико-математических наук, доцент, Институт вычислительной математики и информационных технологий ФГАОУ ВПО «Казанский федеральный университет».
ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ПРЕДЕЛЬНЫХ СВОЙСТВ РЕШЕНИЯ ДВУХУРОВНЕВОЙ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В БЕСПРОВОДНЫХ СЕТЯХ
Аннотация: Работа посвящена исследованию свойств решений задачи оптимального распределения ресурса в беспроводных сетях с мобильными абонентами на бесконечном горизонте планирования. Актуальность задачи обусловлена быстрым развитием систем мобильной связи, в том числе беспроводных распределённых самоорганизующихся сетей, состоящих из большого количества элементов, каждый из которых может выступать как в качестве источника, так и в качестве получателя пакетов данных. Передача данных осуществляется посредством радиоканала, ширина которого и подлежит распределению.
Ключевые слова: беспроводная сеть; мобильные абоненты; радиоканал; задача распределения ресурса; двухуровневая оптимизация; декомпозиция; функция Лагранжа; одномерная минимизация; стабилизация решения.
Рассмотрим «двухуровневую» задачу распределения ресурса в сетях с мобильными абонентами [1], состоящую в оптимальном распределении ресурса сети (ширины частотной полосы радиоканала) между зонами, на которые разбивается область покрытия сети. Значение целевой функции задачи в каждой точке вычисляется, исходя из предположения о том, что распределение выделенного зоне ресурса между абонентами, находящимися в этой зоне, также осуществляется оптимально. Предполагается, что лицо, принимающее решение (ЛПР) на верхнем уровне – уровне сети («менеджер сети»), периодически получает информацию о фактических координатах абонентов сети и решает задачу с обновлёнными данными. Некоторые параметры задачи также подвержены изменениям во времени. Нас интересуют свойства последовательности решений задачи при стремлении номера наблюдения к бесконечности.
Введём обозначения (для краткости будем опускать обозначение момента времени решения задачи, когда речь идёт об одном фиксированном моменте) – все дальнейшие обозначения (там, где это не оговаривается особо) относятся к фиксированному моменту времени.
Пусть C – общее количество распределяемого ресурса (ширина частотной полосы радиоканала);  – количество зон, на которые разбивается область покрытия сети;  – искомое количество ресурса, выделяемое зоне z; величина  – расходы, связанные с выделением зоне  ресурса в количестве ;  – доход, получаемый ЛПР от выделения зоне ресурса в количестве (при оптимальном распределении этого количества ресурса между абонентами, находящимися в зоне ),  .
Задача, решаемая в некоторый момент времени, состоит в том, чтобы оптимально распределить ресурс между зонами, при условии, что выделенный зоне ресурс оптимально распределяется между её абонентами:
 (1)
 , (2)
 . (3)
Будем считать, что для всех функции  выпуклые, возрастающие при  ; функции  заданы алгоритмически – посредством решения задачи:
 (4)
 , (5)
 (6)
Здесь z – номер зоны (z ),  – множество номеров абонентов, находящихся в зоне ; величина  – искомое количество ресурса, получаемого абонентом  ; величина  – плата абонента за полученный им ресурс в количестве ; величины  и  – нижнее и верхнее допустимые значения переменной ,  Здесь функции  предполагаются вогнутыми на  ,  , z=1,…,Z.
Таким образом,
 , (7)
где  – вектор, составленный из компонент , ;  – допустимое множество задачи (4) – (6) при фиксированном z
Как уже отмечалось выше, в формулировке задачи (1) – (3) (а значит, и задачи (4) – (6) для всех z) момент времени предполагается фиксированным (обозначим его через k). Значения параметров задачи в момент k+1, вообще говоря, отличаются от значений, имевших место быть в момент k: ввиду мобильности абонентов изменяется состав множеств , ввиду наличия случайных ошибок (неточностей измерений) меняются значения параметров функций (тарифы).
Для решения задачи (1) – (3) в фиксированный момент времени применим декомпозиционный подход [2, 3].
Зафиксируем номер z, введём переменную μ и запишем функцию Лагранжа (например, [4, с. 196]) для задачи (4) – (6):
 . (8)
С помощью функции (8) перепишем (7) в виде:
 , (9)
где  – прямое произведение отрезков  ,  . С помощью несложных преобразований функции (8) и изменения порядка оптимизации в_(9) запишем
 . (10)
«Внутренняя» задача в (10), т.е.
 ,
при фиксированных значениях и  распадается на одномерные задачи:
 . (11)
Обозначим через  решение задачи (11) при фиксированных , , . Тогда (10) примет вид:
 .
Обозначим здесь максимизируемую функцию через
 . (12)
Тогда
 . (13)
Таким образом, мы получили способ вычисления значения  , предполагающий решение задачи (13) любым из методов одномерной минимизации нулевого порядка. На каждом шаге реализации этого метода для вычисления значения (12) при фиксированных , и необходимо решить  задач вида (11), каждая из которых состоит в минимизации одномерной функции (функции от переменной ).
Теперь задача (1) – (3) может быть решена любым методом вогнутой максимизации (выпуклой минимизации) нулевого порядка. Однако при решении двухуровневых задач имеет смысл организовать параллельные вычисления, выполнив декомпозицию задачи. Для этого запишем (1) как
 . (14)
Введём переменную  и запишем функцию Лагранжа для задачи (14), (2), (3):
 , (18)
где  . Рассуждая как выше, получим задачу:
 , (15)
где
 , (16)
 – решение задачи:
 (17)
при фиксированных и  . Понятно, что задача (17) может быть решена любым методом одномерной минимизации 0-го порядка, а задача (15) – любым методом одномерной максимизации 0-го порядка.
Итак, решая (каким-либо методом одномерной максимизации) задачу (15), получаем (с заданной точностью) оптимальное решение  , оптимальное значение критерия задачи (1) – (3), равное  , оптимальное количество ресурса, выделяемое каждой зоне z, равное  , а также оптимальное количество ресурса, выделяемое абоненту j, равное  , , где  – решение задачи (16) при фиксированных z,  .
Обсудим вычислительные аспекты решения задачи (1) – (3). Реализация метода одномерной максимизации для задачи (15) предполагает вычисление величины  , что согласно (16) означает необходимость решения (каким-либо методом одномерной минимизации) Z задач (17) при фиксированном . В свою очередь, вычисление значения целевой функции задачи (17) при заданном требует нахождения значения  путём решения задачи_(13), для чего нужно решить задач (11) (тем же или другим методом одномерной минимизации). При проведении численных экспериментов мы использовали один и тот же метод одномерной оптимизации – метод золотого сечения (см., например, [4, с. 84], там же можно найти некоторые другие методы одномерной оптимизации).
Модельные функции были выбраны следующим образом: функции полагались квадратичными вогнутыми и такими, что  параметры функций генерировались случайным образом (они оставались постоянными на всём временном горизонте); функции были линейными, а именно,  ; все  Для проведения расчётов использовался пакет аналитических вычислений Wolfram Research Mathematica. Экспериментальным путём было получено правило согласования точности решения задачи одномерной минимизации на разных «уровнях вложенности»:  =0,1* , где i – уровень задачи (i=1 обозначает задачу (11), i=2 – задачу (10), i=3 – задачу (17), i=4 – задачу (15)), – длина отрезка локализации задачи уровня i. Полученное правило означает, что чем точнее локализуется решение задачи «верхнего уровня», тем выше требования к точности решения «внутренней» задачи.
На Рис.1 приведён результат решения одной из тестовых задач. Столбцы первой из таблиц имеют следующий смысл (слева направо): номер зоны z; количество абонентов в зоне z; значение тарифа  (платы за использование единицы ресурса); искомая величина  ; «чистый» доход зоны z – значение ; расходы зоны z – значение  ; прибыль зоны z – разность и . В последней строке указаны суммы значений соответствующих столбцов (последняя ячейка содержит найденное значение целевой функции задачи (1) – (3)). Столбцы второй таблицы, представленной на Рис. 1, имеют следующий смысл (слева направо): номер абонента; номер зоны, в которой находится абонент (на момент решения задачи); значение  ; значение  , соответствующее решению, представленному в первой таблице.
Рис. 1. Результат решения одной из тестовых задач
Рассмотрим теперь поведение последовательности решений задачи (1) – (3) в бесконечности. Обозначим через k номер момента времени, в который решается задача; пусть  – множество номеров абонентов, находящихся в зоне z в момент k. Предположим, что тарифы подвержены затухающему «белому шуму», т.е.  + , где  – значение тарифа в зоне z в момент k, а представляет собой гауссову случайную величину с нулевым математическим ожиданием и среднеквадратическим отклонением  , таким что  при k→∞. Относительно поведения абонентов будем считать, что они могут свободно перемещаться между зонами в соответствии с заданными вероятностями:  ≡ p{в момент k абонент j находится в зоне z}. При проведении численных экспериментов эти вероятности генерировались случайным образом и сохранялись постоянными для всей серии экспериментов? т.е. ≡ при всех k.
Обозначим через  оптимальное значение целевой функции задачи_ (1)_– (3) при  и  ; обозначим через  относительную частоту нахождения абонента j в зоне z к моменту k; тогда  есть «невязка», т.е. суммарная мера расхождения между относительными частотами и вероятностями событий «абонент j находится в зоне z». Положим  – среднее значение целевой функции задачи (1) – (3), вычисленное на момент k;  – среднеквадратическое отклонение значений целевой функции от среднего на момент k;  – значение коэффициента вариации на момент k.
Мы провели экспериментальное исследование поведения последовательностей { }, {} и { } при k→∞. Результаты вычислений приведены на Рис._2 – 4. Ось абсцисс на всех трёх представленных графиках соответствует номеру k, по оси ординат отложены значения , и , соответственно.
Рис. 2. График последовательности {}
Рис. 3. График последовательности {}
Рис. 4. График последовательности {}
Стремление к 0 последовательности {} (см. Рис. 2) вполне ожидаемо – оно непосредственно следует из общеизвестного статистического определения вероятности. Более информативны графики, представленные на Рис. 3 и 4 – они свидетельствуют о том, что при стабилизации (стремлении к константе) тарифов происходит стабилизация решения задачи (1) – (3). Для ЛПР это означает возможность на практике выбирать моменты решения задачи на основе анализа предыдущих решений и с использованием информации о фактическом местоположении абонентов (а не на основе вероятностных прогнозов).
Автор выражает благодарность профессору КФУ Игорю Васильевичу Коннову за идею и полезные обсуждения при выполнении работы и студентке КФУ Диане Хасановой за помощь в проведении численных экспериментов.
Литература
1._Konnov I.V., Kashina O.A., Laitinen E. Optimisation problems for control of distributed resources // International Journal of Modelling, Identification and Control. - 2011. - V.14, No 1-2. - P.65-72.
2._Konnov I.V., Kashina O.A., Laitinen E. Two-level decomposition method for resource allocation in telecommunication network // International Journal of Digital Information and Wireless Communications. - 2012. - V.2, No 2. - P. 150-155.
3._Konnov, Igor; Kashina, Olga; Laitinen, Erkki; Dual decomposition scheme for resource allocation problem in networks with moving nodes, 2012 Second International Conference on Digital Information Processing and Communications (ICDIPC), DOI: 10.1109/ICDIPC.2012.6257273. - 2012. - P. 31 – 35.
4. Коннов И.В. Нелинейная оптимизация и вариационные неравенства. – Казань, КГУ, 2013. – 508 с.
___________________________________________________________________
Kashina, O.A, Candidate of Sciences (Mathematics and Physics), Associate Professor of Institute of Computer Mathematics and Information Technologies, Kazan Federal University
EXPERIMENTAL STUDY OF LIMIT PROPERTIES OF SOLUTIONS TO A TWO-LEVEL RESOURCE ALLOCATION PROBLEM IN WIRELESS NETWORKS
Abstract: We study properties of solutions to a resource allocation problem in wireless networks over an infinite planning horizon. The relevance of the problem is due to the rapid development of mobile communication networks, including distributed self-organizing ones consisting of a large number of elements, each of which can serve both as a source and as a receiver of data packets. Data are transmitted via a radio channel, whose width is to be distributed among zones.
Key words: wireless network; mobile nodes; radio channel; resource allocation problem; two-level optimization; decomposition; Lagrange function; one-dimensional minimization; solution stabilization.
УДК 517.958:539.3
Тимергалиев С.Н., доктор ф.-м. н., профессор, Набережночелнинский институт ФГАОУ ВПО «Казанский (Приволжский) федеральный университет»
Углов А.Н.,кандидат ф.-м. н., доцент, Набережночелнинский институт ФГАОУ ВПО «Казанский (Приволжский) федеральный университет»
Якупова Г.А., старший преподаватель, Набережночелнинский институт ФГАОУ ВПО «Казанский (Приволжский) федеральный университет»
|
