557_Obrabotka_informatsii_i_matematicheskoe_modelirovanie_2014_

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

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

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

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

Работа поддержана РФФИ (14-01-31089).

Литература

1.Jadhawar P., Mohammadi A.H., Yang J., Tohidi B. Subsurface carbon dioxide storage through clathrate hydrate formation // Advances in the Geological Storage of Carbon Dioxide. – Springer. Printed in the Netherlands. – 2006. – P. 111-126.

2.Бык С.Ш., Макогон Ю.Ф., Фомина В.И. Газовые гидраты. – М.: Химия, 1980.

3.Истомин В.А., Якушев В.С. Газовые гидраты в природных условиях. –

М.: Недра, 1992.

61

ИССЛЕДОВАНИЕ ОДНОЙ ЗАДАЧИ МОДЕРНИЗАЦИИ БАЗОВЫХ СТАНЦИЙ СОТОВОЙ СВЯЗИ С ИСПОЛЬЗОВАНИЕМ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

Колоколов А.А.1, Леванова Т.В.1, Поздняков Ю.С.2 1 ОмФИМ им. С.Л. Соболева СО РАН, Омск

2 ОмГУ им. Ф.М. Достоевского, Омск e-mail: [e-mail], тел. [phone]

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

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

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

Вданной работе рассматривается следующая задача модернизации базовых станций сотовой связи (баз). Имеется множество базовых станций, каждая из которых обеспечивает доступ в Интернет на определенной территории. Оборудование станций характеризуется мощностью, определяющей его тип, и может работать по нескольким стандартам связи (2G и 3G). Дальность распространения сигнала зависит от мощности базовой станции и влияет на количество обслуживаемых станцией клиентов. Если базы находятся в достаточной близости друг от друга, то зоны их обслуживания пересекаются, что приводит к нестабильности связи, и, как следствие, потере клиентов. Согласно санитарным нормам число станций, работающих с высокой мощностью, должно быть ограничено. Для улучшения качества связи оператор выделяет некоторый объем финансовых ресурсов на модернизацию отдельных станций до стандарта нового поколения 4G [3]. Указано минимально необходимое количество станций для переоборудования. Стоимость модернизации определяется размещением станции и типом устанавливаемого оборудования. Требуется выбрать такие станции, подлежащие модернизации до стандарта 4G, для которых количество обслуживаемых клиентов будет максимальным.

62

Построим математическую модель рассматриваемой задачи, используя следующие обозначения:

I – множество станций возможного размещения оборудования 4G; R – множество типов оборудования различной мощности;

cr	– стоимость размещения на станции i				оборудования типа r ,			i I ,
i
r R ;
t r	–	количество	клиентов,	которые	могут	быть	обслужены		с
i
использованием оборудования типа r , размещенного на станции i , i I ,								r R ;
srq	–	штраф, отражающий		количество	потерянных клиентов			ввиду
ij
некачественной связи в области пересечения зон обслуживания станций i								и	j с
оборудованием типов r			и q соответственно, i, j I , r, q R ;
br	– максимально допустимое количество станций с оборудованием
типа r , r R ;
	–	минимальное количество станций,				которое	необходимо

модернизировать;– общий объем выделяемых средств на модернизацию.

Введем переменные модели:

1, если на станции i устанавливается оборудование типа r; zir 0 иначе, i I, r R.

Модель нелинейного целочисленного программирования имеет вид:

tir zir sijrq zir zqj max			(1)
i I r R		i I r R j I q R
при условиях
zir ;			(2)
i I r R
zir	br ,	r R;	(3)
i I
cir zir		;	(4)
i I r R
zir	1,	i I;	(5)
r R
zr {1,0},		i I , r R.	(6)
i

Целевая функция (1) состоит в максимизации суммарного количества подключаемых абонентов к переоборудованным станциям. Неравенство (2) отражает наличие нижней границы для общего числа модернизируемых станций. Условия (3) устанавливают максимально допустимое количество станций с оборудованием каждого типа. Ограничениями (4) гарантируется, что суммарные затраты не превышают объем выделенных финансовых средств. Условия (5) указывают, что на каждой станции можно разместить не более одного вида оборудования.

63

Для рассматриваемой задачи на основе модели (1)-(6) может быть построена модель целочисленного линейного программирования. Для этого

введем дополнительные переменные					xrq	{1,0},	i, j I , r, q R ;	изменим
					ij
целевую функцию:
		tir zir sijrq xijrq max;						(7)
		i I r R		i I r R j I q R
и добавим новые ограничения
		zr zq 1 xrq ,				i, j I ,	r, q R;	(8)
		i	j		ij
		xrq {1,		0},	i, j I , r, q R,			(9)
		ij
которые связывают переменные			z r	и	xrq	по следующему правилу: если обе
			i		ij
переменные z r и	z q	одновременно равны 1, то xrq 1. Нами показано, что имея
i	j					ij

оптимальное решение задачи (2)-(9) можно получить оптимальное решение задачи (1)-(6).

Экспериментальные исследования построенной математической модели

(2)-(9) выполнялись на тестовых примерах различной размерности с применением системы GAMS на ПК с процессором Intel® Core™ i5–2430M 2,40 GHz и с 4 ГБ оперативной памяти. Для каждого примера, содержащего менее 50 станций, было получено оптимальное решение за приемлемое время (не более 10 минут). При увеличении размерности до 150 станций решено около 50% задач.

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

Работа поддержана грантом РФФИ (проект 14-01-00656).

Литература

1.Колоколов А.А., Леванова Т.В., Лореш М.А. Алгоритмы муравьиной колонии для задач оптимального размещения предприятий // Омский научный вестник. – 2006. – № 4(38). – C. 62–67.

2.Колоколов А.А., Леванова Т.В., Поздняков Ю.С. Алгоритмы искусственной иммунной системы для вариантной задачи размещения телекоммуникационных центов // Известия Иркутского государственного университета. Серия: математика. – 2013. – №1. – С. 35–44.

3.Что такое LTE и 4G от МегаФона. – URL:

http://habrahabr.ru/company/megaphone/blog/15153/	(дата	обращения:
02 февраля 2014).

64

ВОССТАНОВЛЕНИЕ ДВУМЕРНОЙ ФУНКЦИИ ПО ЛУЧЕВОМУ ПРЕОБРАЗОВАНИЮ

Кривцов Ю.В. СибГУТИ, Новосибирск

e-mail: [e-mail], тел.: [phone]

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

Литература 1. Ф. Наттерер. Математические аспекты компьютерной томографии. – Москва:

Мир, 1990.

МАРКОВСКИЙ ПОДХОД К ОПИСАНИЮ ПРОЦЕССА ИНФОРМАЦИОННОГО ОБМЕНА ПО УСТАНОВЛЕННОМУ ЛОГИЧЕСКОМУ СОЕДИНЕНИЮ ПРОТОКОЛА ТСР

Тоискин В.Е.

Филиал военной академии РВСН имени Петра Великого, Серпухов e-mail: [e-mail], тел.: [phone]

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

65

Известно, что самым распространенным стеком протоколов является стек TCP/IP. Транспортный уровень данного стека представлен протоколами TCP и UDP. UDP протокол позволяет приложениям отправлять инкапсулированные IP-дейтаграммы без установления соединения. Это уменьшает временные затраты процесса передачи информации, но при этом не гарантирует его надежность. Данный протокол является простым и имеет определенную область применения, например мультимедиа приложения. Однако большинству пользовательских приложений требуется надежная, последовательная передача. Данный сервис предоставляет протокол TCP. Протокол TCP устанавливает логические соединения между объектами прикладного уровня, причем в каждом соединении участвуют только два объекта [1]. При этом весь процесс обмена сегментами между двумя хостами можно разделить на три этапа: установление логического соединения, ведение информационного обмена и завершение соединения.

Этап установления соединения рассмотрен в работе [2]. При успешном исходе данного этапа, два хоста осуществляют последовательную передачу сегментов по установленному логическому соединению. В процессе передачи протокол ТСР использует различные механизмы. Управление скоростью передачи осуществляется путем ограничения количества сегментов, которые могут быть переданы без получения квитанции - механизм скользящего окна. Управление повторной передачей сегментов при отсутствии квитанции на их прием, осуществляется механизмом тайм-аута повторной передачи.

Процедура передачи информации по установленному логическому соединению базируются на эмпирическом определении параметров сети в определённые промежутки времени и зависит от поведения других сетевых устройств. Поэтому очевидна необходимость разработки математического и научно-методического аппарата оперативного определения основных регулируемых параметров протокола ТСР. Исходя из этого, актуальной является задача определения вероятностных и временных характеристик процесса передачи.

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

Для получения обобщенных результатов по анализируемому протоколу был последовательно рассмотрен процесс доведения сообщения состоящего одного, двух, трех и более сегментов (w), с различной величиной скользящего окна (v) и различным количеством возможных повторов (m). Вариант графа поглощающей конечной марковской цепи (ПКМЦ) исследуемого процесса при w=1, v=1 и m=1, представлен на рисунке 1.

66

Рисунок 1 – Граф ПКМЦ для варианта w=1, v=1 и m=1

Состояния в которых находится процесс показанный на рисунке 1 следующие: S0 – хост А передал сегмент хосту В и запустил таймер повторной передачи на время рассчитанное по алгоритму Якобсона [1] (τпп); S1 – по истечению τпп хост А не получил квитанции от хоста В, повторно передал сегмент хосту В запустив таймер на время 2τпп (согласно алгоритму Карна [1]); S2 – хост В получил сегмент от хоста А, передал квитанцию; S3 – хост А получил положительную квитанцию от хоста В (сообщение передано); S4 – по истечению 2τпп хост А не получил квитанции от хоста В, разрыв соединения, возврат к процедуре установления соединения. При этом переходы из одного состояния в другое описываются переходными вероятностями и возможны в следующих случаях: S0→S1 – за время τпп хост А не получил ответа от хоста В;

S1→S4 – за время 2τпп хост А не получил ответа от хоста В; S0→S2 и S1→S2 – переданный сегмент успешно доставлен хосту В; S2→S0 – хост А получил

запрос на повтор от хоста В, т.к. принятый сегмент искажен; S2→S1 и S2→S4 – хост В передал квитанцию, квитанция не доставлена за время тайм-аута; S2→S3 – хост А получил подтверждение о приеме сегмента; переходы S3→S3 и S4→S4 указывают на то, что состояния S4 и S4 поглощающие.

Анализ вариантов информационного обмена с большим количеством сегментов, с различными значениями скользящего окна и количества возможных повторов показывает, что с увеличением значений w, v и m получаются графы, частью которых является граф с меньшим значением w, v и m. Кроме того, существует ряд закономерностей, позволяющих машинным способом найти все элементы матрицы переходных вероятностей. В качестве примера для иллюстрации этих закономерностей рассмотрим вариант доведения сообщения при w=4, v=4 и m=2 (рисунок 2).

67

Рисунок 2 – Граф ПКМЦ для варианта w=4, v=4 и m=4 с пояснениями

Для синтеза матрицы переходных вероятностей при различных значениях w, v и m было получено выражение для определения количества состояний процесса передачи (n):

v 1

n w(m 1) 2 (w a) ,

a 0

где w – количество сегментов; m – возможное количество повторов сегмента по истечению тайм-аута; v – размер скользящего окна в сегментах.

Используя алгоритм изложенный в [3] и определив количество состояний процесса передачи информации можно исследовать вероятностные и временные характеристики процесса информационного обмена по протоколу ТСР в конкретных условиях функционирования сети с учётом динамики её загруженности, а также определить величины тайм-аутов и размер скользящего окна для повышения уровня качества услуг предоставляемых сетью.

Литература

1.Таненбаум, Э.С. Компьютерные сети. 4е-издание. / Э.С. Таненбаум. – СПб: «Питер», 2003. – 992 с.

2.Тоискин, В.Е. Марковский подход к математическому моделированию процесса установки виртуального соединения по протоколу ТСР / В.Е. Тоискин, С.Е. Потапов, Т.А. Исаева, С.В. Рябцев // Труды РНТОРЭС им. А.С. Попова. Науч. сес., посвящ. Дню радио. – /Выпуск LXVIII – М. : РНТОРЭС,

2013. – С. 81-85.

68

3. Цимбал, В.А. Монография. Качество информационного обмена в сетях передачи данных. Марковский подход. / В.А. Цимбал. – Серпухов: СВИ РВ,

2009. – 161 с.

ДВАЖДЫ УНИВЕРСАЛЬНОЕ КОДИРОВАНИЕ ИСТОЧНИКОВ СИМВОЛАМИ НЕРАВНОЙ ДЛИТЕЛЬНОСТИ

Трофимов В.К., Храмова Т.В. СибГУТИ, Новосибирск

e-mail: [e-mail], [e-mail]

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

Пусть буквы конечного алфавита A, называемого в дальнейшем входным,

порождаются источником W , где W			Wk , W	– некоторое множество
		k 0	k
источников, причем если в W только конечное число L различных не пустых
			положим WL 1 WL 2 ... .
множеств источников Wk , k 0, L , то

Последовательность букв , порождаемых источником будем разбивать на

последовательности u ,	длины		u		N , и кодировать словами выходного m-
буквенного алфавита	B y1, y2,..., ym , буквы которого имеют различные

стоимости, либо, что то же самое, различные длительности. Следовательно, каждому кодовому алфавиту ставится в соответствие его вектор длительностей

t ,t

m , где

t( y

,...,t

t

)

, j 1, m . Кодирование

t

2

j

j

ставит в соответствие

1

слову

u

кодовое

слово (u) . Рассматривается только дешифруемые

кодирования,

т.е.

такие

кодирования, по

которым

однозначно

можно

восстановить

переданное

сообщение. Если

кодовые

(u)

u AN

слова

обладают свойством префикса, то кодирование дешифруемо [1].

Сумму

длительностей всех букв входящих в слово (u) , назовем его стоимостью и

обозначим (u) . Стоимостью кодирования назовем отношение средней длительности кодового слова к длине кодируемого блока. Стоимость кодирования будем обозначать L(N,, , t ) . Разность между L(N,, , t ) и H ( )C(t ) , где H ( ) – энтропия источника, а C(t ) – пропускная способность канала, зависящая только от входного алфавита, назовем избыточностью кодирования и обозначим R N,, , t :

69

подробно изучена в [5–9].

R N,, , t L(N,, , t ) H ( )C(t ) .

Величину R N,W , t , определяемую равенством

R N,W , t inf sup R N,, , t

W

назовем избыточностью универсального кодирования для множества источников W , при кодировании словами алфавита B c неравнозначными символами. Если W содержит единственный источник , то мы имеем дело с известным источником. Такое кодирование подробно изучено в работах [2–4]. Если же мы имеем дело с множеством бернуллиевских или марковских

источников W s , s 0 , то величина R N, s , t

Для равных длительностей букв входного алфавита, кодирование множества

источников W

Wk

изучалось в [10], где установлено, что если

W , то

k 0

k

существует кодирование 0 , такое, что

R N,,0 ,

R N,Wk ,

0 log k

t1

t1

,

N

1,1,...,1

где

t

Построенное

кодирование

автор

назвал

дважды

1

.

универсальным. Основной результат настоящего сообщения имеет вид:

Теорема.

Если

множество

источников W

является объединением

конечного или счетного множества источников Wk , k 0,1,..., для каждого из

которых существует универсальное кодирование 1 с выходным алфавитом B, имеющим вектор длительностей t , с известной избыточностью универсального

кодирования, равной R N,Wk , t , то справедливо неравенство

		R N,,1,				R N,Wk ,				1 log k
					t				t
										N ,
где 1 не зависит от , N,				.
			t
Пусть		– множество стационарных источников, тогда из									данной
теоремы вытекает
Следствие.		Для множества всех стационарных источников существует
слабо универсальное кодирование								1 буквами имеющими разные
длительности, т.е. существует кодирование 1 , такое, что для любого
выполняется равенство lim R N,, ,								0 .
							t
		N

Литература

1.Фано Р. Передача информации. Статист. теория связи.// «Мир», М.: 1965.

2.Шеннон К. Математическая теория связи. Работы по теории информации и кибернетике. – 1969. – Ил., М. – С.243-332.

3.Чисар И. О каналах без шума. // Пробл. передачи информ. 1970. Т.6. № 4. – С.3-15.

70