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

РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ

На правах рукописи

Меркулов Владимир Евгеньевич

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ ДЛЯ АНАЛИЗА КАЧЕСТВА ОБСЛУЖИВАНИЯ В СОТОВЫХ СЕТЯХ

Специальность 05.13.17 - теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2004

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

Научный руководитель -заслуженный деятель науки РФ, академик РАЕН, доктор технических наук, профессор Г. П. Башарин

Официальные оппоненты: доктор физико-математических наук, профессор С. Я. Шоргин кандидат физико-математических наук, доцент В. А. Наумов

Ведущая организация: Институт проблем передачи информации РАН

Защита диссертации состоится "_"_2004 г. в_

час._мин. на заседании диссертационного совета К 212.203.08 в

Российском университете дружбы народов.

Адрес: 117923, г. Москва, ул. Орджоникидзе, 3

С диссертацией можно ознакомиться в научной библиотеке Российского университета дружбы народов по адресу: 117198, г. Москва, ул. Миклухо-Маклая, 6

Автореферат разослан "_"_2004 г.

Ученый секретарь

диссертационного совета

кандидат физико-математических наук,

доцент В. А. Кокотушкин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность проблемы

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

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

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

ЛТихвинский В. О. Сети подвижной связи третьего поколения. Экономические и технические аспекты развития в России. Под ред. Ю. В. Зубарева. — М.:

Радио и связь, 2004. — 312 с. Г' -----

I РОС НАЦИОНАЛЬНАЯ I I БИБЛИОТЕКА I

!

В. М., Наумова В. А., Степанова С. Н., Харкевича А. Д.", Iversen V. В., Kelly F. P., Rappaport S. S., Ross К. W., др.

Известные сегодня модели ТМО и теории телетрафика,-.применяемые для анализа ССПС, разработаны в основном зарубежными специалистами, такими как Everitt D., Iversen V. В., Rappaport S. S., Tran-Gia P. и др. В российской научной литературе работ, посвященных вопросам.теории телетрафика в ССПС очень мало. Можно лишь назвать работы Демьянова А.И., Ромашковой О.Н! и Шорина О.А. Некоторые базовые аспекты телетрафика в ССПС рассматриваются также в вышедшем в 2002 году учебном пособии Маковеевой М. М. и Шинакова Ю. С.2

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

Таким образом, разработка математических моделей и эффективных методов анализа ВВХ систем сотовой связи является весьма актуальной задачей, особенно для российской научной среды.

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

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

2Маковеева М.М., Щинаков Ю.С. Системы связи с подвижными объектами: Учеб. пособие для вузов. — М.: Радио и связь, 2002. — 440 с.

Научная новизна и результаты, выносимые на защиту, состоят в следующем:

— Разработан новый эффективный алгоритм вычисления точных значений стационарных вероятностей для модели одной соты с ожиданием;

— Впервые предложен эффективный аналитический метод приближенной оценки вероятностей блокировки в модели одной соты с повторными вызовами;

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

— Для фрагмента двухуровневой ССПС без переупаковки каналов построена модель нагрузки на макросоту. Предложенная модель позволяет применить метод эквивалентных замен для анализа требуемых ВВХ.

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

Практическая ценность работы. Аналитические методы и вычислительные алгоритмы, полученные в диссертации, предназначены для анализа характеристик качества обслуживания в сетях сотовой подвижной связи. Вычислительные алгоритмы и аналитические методы оценки ВВХ одной соты, представленные во второй главе работы, могут быть использованы непосредственно при анализе фрагментов сотовых сетей. Теоретические результаты главы 3 работы определяют границы, в которых для анализа характеристик иерархических ССПС могут применяться классические методы теории телетрафика. Результаты исследований используются в учебном процессе на кафедре систем телекоммуникаций РУДН для студентов, обучаю-

щихся по направлению "Прикладная математика и информатика", а также в курсовых и дипломных'работах.

Реализация результатов работы. Разработка математических моделей и вычислительных алгоритмов для анализа качества обслуживания в сотовых сетях проводилась в рамках НИР "Математическое моделирование и анализ информационно-вычислительных сетей и интеллектуальных систем" (государственный регистрационный номер 020602-1-175), выполняемой в соответствии с планами РУДН, а также при частичной поддержке программ "Университеты России", УР.03.01.004 (2002-2003) и УР.03.01.022 (2004).

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

— XXXVII-XL научных конференциях факультета физико-математических наук Российского университета дружбы народов (Москва, 2001-2004);

— научной сессии Российского научно-технического общества радиотехники, электроники и связи им. А. С Попова (Москва, 2002);

— 7-й международной конференции СопТЕЦ'2003 (Загреб, Хорватия, 2003);

— Международной конференции NEW2AN'2OO4 (Санкт-Петербург, Россия, 2004);

— Научной конференции МТУСИ, в секции 'Радиотехнические системы и устройства" (Москва, 2004);

— Семинарах кафедры систем телекоммуникаций РУДН (Москва, 2001-2004).

Публикации. По теме диссертации опубликовано 11 работ, из которых 3 - в центральной печати, 2 - в трудах международных конференций.

Структура и объем диссертации. Диссертация состоит из введения, трех глав; заключения, списка литературы из 86 наименований. Диссертация содержит 105 страниц текста, 33 рисунка и 1 таблицу.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

В разделе 1.6 анализируется роль теории телетрафика в решении проблемы оценки качества обслуживания в сотовых сетях, и формулируются следующие задачи:

1. Построение модели нагрузки на отдельную соту;

2. Анализ вероятностей блокировки в отдельной соте при различных параметрах функционирования базовой станции;

3. Построение модели нагрузки в иерархических ССПС. Данная задача включает в себя построение моделей нагрузки на отдельные микро- и макросоты;

4. Анализ вероятностей блокировки в иерархических ССПС.

Глава 2 посвящена решению задач, связанных с анализом отдельной соты одноуровневой сотовой сети.

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

Пусть £ - длительность обслуживания произвольного принятого в систему вызова при отсутствии блокировок и технических сбоев. Обычно для ССПС среднее значение £ берется порядка 2 мин. Пусть - время от момента принятия произвольного вызова на обслужи-вание в систему до момента его первого хендовера, а - время пребывания произвольного вызова в Д-й соте его маршрута, к — 2,3,_

Обозначим

С т т ,м 1

I .=2 к=2 \

(1)

- вероятность того, что произвольный принятый вызов потребует не менее т хендоверов, т = 1,2,...; £ (0 := 0. Тогда

Рп = (1 - ТТ2)П-1 П'?(т) Ь + (1 - д(т +1))(1 - «,)], ' (2)

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

Оценка Аг интенсивности нагрузки, создаваемой хендовер-вызо-вами, может быть получена по формуле

А2=А1(1-тг1)ЛГ, (3)

где Ах(1 — 7Г1) - интенсивность принятой нагрузки, создаваемой новыми вызовами, а N = Еп=1 пРп ' среднее количество хендоверов на один принятый вызов. В частном случае, если £ имеет экспонен-

циальное распределение с параметром цо, а с.в. £1 и ^^ к = 2,3,..., распределены одинаково, то N представимо в виде

77=___ш

где /* (1) - преобразование Лапласа ФР &.

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

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

' Пусть щ - суммарное количество вызовов, обслуживаемых системой и ожидающих в накопителе С?2> а, П2 - количество вызовов, ожидающих в накопителе Тогда пространство состояний рассматриваемой системы записывается в виде

5= {(щ,0) =0,С-д- 1}и{(п1,п2) :П1 = С - д,С + г2,п2 = О.тч} .

(5)

Для простоты дальнейшего изложения обозначим := (г,7), (г,;) Е 5 и 0(5,Ь), £ 5 - интенсивность перехода системы из состояния в в состояние 4.

Для нахождения ненормированных стационарных вероятностей (г,]) € 5 воспользуемся следующим алгоритмом.

Шаг 1. Положим Р0,о := 1 и выразим - рекурсивно следующие вероятности:

Шаг 2. Обозначим вероятности Рс-д,]>3 — 1,гх черезх1,...,хг1и

будем искать остальные вероятности в виде неоднородной линейной комбинации этих величин, т.е. в виде

Здесь и(х) - функция Хевисайда.

Шаг 4- Как и на предыдущем шаге, выразим вероятность Рс+п,о через известные вероятности соседних состояний. После этого, последовательно выражая вероятности заметим, что каждую из этих вероятностей можно выразить двумя способами: "слева", из уравнения баланса для состояния и "снизу", из уравнения баланса для состояния 8с+п,з-1- Это дает возможность построить гх линейных уравнений для неизвестных Х1,...,ХГ1, откуда они могут быть однозначно найдены.

Предложенный алгоритм позволяет свести решение СУР ртА = 0Т, которая имеет размерность {С — д) + (С + гг ~ 9), к решению системы линейных уравнений размерности .

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

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

В разделе 2.3 представлен приближенный метод вычисления вероятностей блокировки новых и хендовер-вызовов в одной соте ССПС с учетом эффекта повторных вызовов. Предложенный метод строится на анализе периодов времени (называемых интервалами блокировки), в течение которых рассматриваемая система, в силу нехватки свободных каналов, блокирует все предложенные новые вызовы, как первичные, так и повторные.

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

вызовов от одного абонента, г,^ = 1,2,____Будем предполагать, что

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

и= 1,2,....

Введем г - длительность произвольного интервала блокировки,

п т

и обозначим ап := £ /9т := £ щ, п,т =1,2,...; »=1 }=1

(8)

'{а„_1 < г}

- вероятность того, что п-й по счету первичный вызов, поступивший с момента начала произвольного интервала блокировки, попадет в этот же интервал, при условии, что предыдущие п — 1 первичных вызовов в него попали, п = 1,2,...;

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

предыдугцие ш — 1 повторных вызовов в него попали, п,т — 1,2,----

Тогда среднее число 0 блокированных повторных вызовов, соответствующих блокировке одного и того же произвольного первичного вызова, выражается из соотношения

Яп = Лх £ тЛ?-1 П *) [1 - Лае (я,+1)],

га» » 4=1 (Ю)

^=¿г Е П *(*) I1 - р<"+*)]

' п—1 к=1

где /11 - вероятность того, что блокировка первичного вызова повлечет повторный вызов, а Лг - вероятность того, что блокировка повторного вызова повлечет следующий повторный вызов.

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

» -1±9- пи

»1 - , (И)

где 7г° - вероятность блокировки новых вызовов в системе, идентичной рассматриваемой, но без повторений.

В диссертационной работе рассмотрены два частных случая описанной модели.

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

Лемма 2.2 Пусть случайная величина т имеет экспоненциальное распределение с параметром Сц. Тогда имеет место следующее соотношение:

Р{ап+/3ш <т}=рпят, 71,ш = 0,1,..., (12)

гдр п = _ а = _—

гоер- Я — А13+с>-

В силу леммы 2.2 для данного случая оценка вероятности блокировки ТГ1 может быть получена из соотношения

1 + Чк 1. 1 + 1 1 .

1-

1 = , ■ (13)

Заметим, что в этом случае величина п® есть эрланговская вероятность потерь.

Случай доступа с резервированием. При наличии резервных каналов в системе св. г имеет РН-распределение с трехдиагональной якобиевой матрицей А размерности д+13. Для данного случая имеет место следующее обобщение леммы 2.2.

Пусть модули собственных значений и собственные век-

торы матрицы А', Vк - решение системы уравнений ^2j=0UjVj =

(1,0, ...,о), Ьк = ик Е?=о «У. * = 0Г5-

Лемма 2.3 Пусть случайная величина т имеет РН-распределение с матрицей А. Тогда имеет место следующее соотношение:

Р {с*п + {¡т <г} = ^ ЬкРкЯ™, П,ТП = 0,1.....

*=0

Из леммы 2.3 следует, что в данном случае

(14)

*=0

£м?

*=о

(15)

Глава 3 посвящена анализу качества обслуживания в иерархических сетях сотовой связи. В этой главе рассмотрена модель кластера двухуровневой ССПС, состоящего из К микросот и одной покрывающей их макросоты. Рассматриваемая модель имеет следующие структурные параметры: С, Ск, к = 1,К - емкости макросоты и микросот; Цк, к = 1 ,К - интенсивности обслуживания абонентов в каждой из микросот; г*, 0 < г* < С, к = 1,К - индивидуальные

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

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

3Башарин Г.П., Бочаров П.П, Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. — М.: Наука, Гл. ред. физ.-мат. лит., 1989. — 336 с. (прил. 2 к гл. 5)

Пусть Ао - интенсивность суммарной предложенной нагрузки, ©о = j=Q~K ~ маршрутная матрица, описывающая движение абонентов внутри рассматриваемого кластера, ® = j=Y~¡¿ ~ ее главная подматрица, а А = (Ai,...,Хк) ~ решение матричного уравнения

AT(I-0) = A„(0oi.....во*). (16)

Легко показать, что при мгновенной переупаковке каналов функционирование рассматриваемой системы может быть описано марковским процессом X(í) = (Xi(í),...,X/í:(í)),í > 0, где Х\. (í) - количество абонентов fc-микросоты, обслуживаемых системой в. момент времени t, t > 0..

Теорема 3.1 Пусть для элементов вектора А выполняются соотношения Xk^kj = jk, k = l,K, j ф k. Тогда

а) Выполняются дополнительные условия

Ao0o*=A*0to, k=TJ{-, (17)

б) Выполняются условия частичного баланса

{р(п — e*)Ao0ofcl(n - е* 6 S) = р(п)р*п*0*О1

р(п - е* + ej)[ij(nj + l)0jtl(n - ejt 6 5) = р(п)^*п*0*у,

k,j = lГК\ n €5; (18)

и случайный процесс X(f), t > 0, имеет стационарное распределение мультипликативного вида

р<п)=сЙ$. Чш.бГ

(19)

в) Условия (17) являются необходимыми для того, чтобы (19) было стационарным распределением процесса X(f).

Лемма 3.2 Пусть для любых k,j € {1,..., К}, j ф к, выполняется соотношение.

в0квк]в}0 — в0]в]квк0-

(20)

Тогда для любого набора ¿1,¿2,...,»„, г* € {1,...,К}, к = 1,п, п 1,2,..., выполняется соотношение

Теорема 3.2 Условия (20) леммы 3.2 эквивалентны условиям теоремы 3.1.

По существу, (20)-(21) являются условиями обратимости марковского процесса Х(£). Результаты разделов 3.1 и 3.2 дают возможность выделить класс иерархических ССПС, для анализа которых применимы классические методы теории телетрафика, разработанные для мультипликативных систем и сетей массового обслуживания.

Раздел 3.3 посвящен анализу случая, когда переупаковка каналов в рассматриваемой системе не используется. При этом система разбивается на две подсистемы: подсистему §1, состоящую только из микросот, и подсистему §2, состоящую только из макросоты. При этом §х является частным случаем системы, рассмотренной в разделе 3.2, поэтому основную часть данного раздела занимает анализ подсистемы 8г, для которой строится модель поступающей нагрузки в виде пуассоновского потока с марковским управлением и вычисляются вероятности блокировки с использованием метода эквивалентных замен (МЭЗ).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

00110»!«] ■•■0»„_11„0«по — 0о«п0»„»п_1 •••0»з«10«1о-

(21)

оценить различные ВВХ этих систем- Ниже приводится краткая характеристика полученных результатов.

- Разработан новый эффективный алгоритм вычисления точных значений стационарных вероятностей для модели одной соты с ожиданием;

- Впервые предложен эффективный аналитический метод приближенной оценки вероятностей блокировки, в модели одной соты с повторными вызовами;

- Построена модель фрагмента двухуровневой ССПС с переупаковкой каналов, для которой сформулированы и доказаны условия мультипликативности стационарного распределения и дана подробная физическая интерпретация этих условий;

- Для фрагмента двухуровневой ССПС без переупаковки каналов построена модель нагрузки на макросоту. Предложенная модель позволяет применить метод эквивалентных замен для анализа требуемых ВВХ.

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

1. Башарин Г. П., Меркулов В. Е. Новые модели теории телетрафика для оценки качества обслуживания в сетях сотовой подвижной связи // Труды ЕУП Кокф. РНТОРЭС. — Т. 2. —

2002. - С. 183-185.

2. Башарин Г. П., Меркулов В. Е. Анализ пропускной способности в иерархических сетях сотовой связи // Электросвязь.—

2003. -№ 4. - С . 45-47.

3. Башарин Г. П., Меркулов В. Е., Смоленков Р. В. Некоторые модели для анализа характеристик качества обслуживания в сетях сотовой подвижной связи Ц Системы телекоммуникаций и моделирование сложных систем. — М.: Изд-во РУДН, 2002. — С. 5-13.

4. Башарин Г. П., Меркулов В. Е., Смоленков Р. В. Построение математической модели нагрузки одного кластера сотовой по-

движной связи // Системы телекоммуникаций и моделирование сложных систем. — М.: Изд-во РУДН, 2003.

5. Башарин Г. П. Дубовкина О. В., Меркулов В. Е. Оценка вероятностей блокировки в одной соте сети сотовой подвижной связи с учетом повторных вызовов // Системы телекоммуникаций и моделирование сложных систем. — М.: Изд-во РУДН, 2003.

6. Меркулов В. Е. Объектно-ориентированная модель для симуляции систем телекоммуникаций // Системы телекоммуникаций и моделирование сложных систем.— М.: Изд-во РУДН, 2003.

7. Basharin G. P., Merkulov V. Е. Performance Analysis of a Two-Layer Cellular Mobile Communication System Fragment // Вестник РУДН (Прикладная и компьютерная математика).—

2002.- Vol. I, no. l. - Pp. 14-24.

8. Basharin G. P., Merkulov V. E. Approximate Analysis of Repeated Calls Impact in Cellular Systems with Guard Channels // Вестник РУДН (Прикладная и компьютерная математика).— 2003.— Vol. 2, по. 1. - Pp. 5-12.

9. Basharin G. P., Merkulov V. E. Blocking Probability Analysis of New and Handover Calls in Cellular Mobile Networks with Repeated Attempts // Proc. ConTel Conf. — Vol. 1. — Zagreb:

2003.-Pp. 278-281.

10. Basharin G. P., Merkulov V. E. Analysis of Repeated Calls in Cellular Systems with Guard Channels // Proc. NEW2AN Conf. — Vol. 1.- St. Petersburg: 2004.- Pp. 119-122.

11. Башарин Г. П., Меркулова О. В., Меркулов В. Е. Анализ интенсивности возникновения хендовер вызовов в сети сотовой подвижной связи // Системы телекоммуникаций и моделирование сложных систем. — М.: Изд-во РУДН, 2004.

Меркулов Владимир Евгеньевич (Россия)

Математические методы и алгоритмы для анализа качества обслуживания в сотовых сетях

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

Merkulov Vladimir Evgenievich (Russia)

Mathematical Models and Algorithms for QoS Analysis in Cellular Mobile Networks

The thesis studies mathematical models of certain cellular communication system fragments and presents effective algorithms for their analysis. Four models are concerned: two models of a single cell (a model with finite queues for new and handover calls and a model with repeated calls) and two models of a single two-layer cellular network cluster (with and without channel repacking). For the first set of models new effective analytical and algorithmic approaches for evaluating their probability charactericstics are presented. For the concerned hierarchical cellular network models classic teletraffic methods are adopted.

#15796

Подписано в печать £ 0 9.01/- Формат 60x84/16. Тираж №0 экз. Усл. печ. л. 4 . Заказ В

Типография Издательства РУДН 117923, ГСП-1, г. Москва, ул. Орджоникидзе, д. 3

Введение

ГЛАВА 1. Принципы функционирования сетей сотовой подвижной связи

1.1 Структурные элементы ССПС.

1.2 Организация каналов связи и эстафетная передача обслуживания

1.3 Принципы частотно-территориального планирования.

1.4 Принципы распределения частот.

1.5 Иерархическая организация сот.

1.6 Задачи теории телетрафика в сетях сотовой подвижной связи

1.6.1 Построение модели и вычисление характеристик нагрузки

1.6.2 Анализ вероятностей блокировки в отдельной соте.

1.6.3 Анализ производительности ССПС иерархической структуры

ГЛАВА 2. Анализ вероятностей блокировки в отдельной соте сети сотовой связи

2.1 Оценка нагрузки, создаваемой переданными вызовами.

2.1.1 Метод оценки интенсивности возникновения хендовер-вызовов

2.1.2 Случай экспоненциального времени обслуживания.

2.2 Вычисление вероятностей блокировки в одной соте ССПС.

2.2.1 Построение математической модели.

2.2.2 Построение пространства состояний.

2.2.3 Вычисление стационарных вероятностей и ВВХ.

2.3 Приближенный метод вычисления вероятностей блокировки в одной соте ССПС с учетом повторных вызовов.

2.3.1 Построение математической модели.

2.3.2 Изложение метода для общего случая.

2.3.3 Случай полного доступа

2.3.4 Случай доступа с резервированием.

2.4 Примеры численного анализа.

2.4.1 Вычисление ВВХ одной соты ССПС.

2.4.2 Вычисление вероятностей блокировки в одной соте ССПС с учетом повторных вызовов.

ГЛАВА 3. Анализ производительности одного кластера двухуровневой

3.1 Постановка задачи.

3.2 Случай мгновенной переупаковки каналов.

3.2.1 Построение математической модели.

3.2.2 Построение марковского процесса.

3.2.3 Вывод условий мультипликативности.

3.3 Случай отсутствия переупаковки каналов.

3.3.1 Предварительные замечания.

3.3.2 Анализ избыточной нагрузки подсистемы Si.

3.3.3 Вычисление вероятностей блокировки при одинаковой интенсивности обслуживания и отсутствии индивидуальных потолков

3.4 Пример численного анализа.

3.4.1 Вычисление ВВХ одного кластера ССПС с переупаковкой каналов

3.4.2 Вычисление вероятностей блокировки в одном кластере ССПС без переупаковки каналов.

Интерес к системам и сетям сотовой подвижной связи (ССПС) [4, 25, 28, 33, 68, 80] в настоящее время черезвычайно велик. Системы сотовой связи первого и второго поколений развернуты во многих странах мира, в том числе в России и других странах СНГ. В США, ряде европейских стран, в том числе и в России, уже внедряются системы сотовой связи третьего поколения [24, 39].

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

Естественно, что проектирование ССПС на начальном этапе их развития сводилось к решению таких радиотехнических задач, как выбор числа и расположения сот на заданной территории [68, 80], частотное планирование [5, 80], проектирование антенн [28, 80], решение задач электромагнитной совместимости [4, 28, 80] и т.п. В последнее десятилетие появилось также немало работ, в которых ставятся и решаются задачи теории телетрафика. К ним относятся задачи сигнализации [29, 31, 35], эффективные алгоритмы доступа и обеспечения качества обслуживания, а также многие другие [7, 14, 20, 27, 34, 63]. Параллельно с аналитическими методами также широко применяются методы статистического моделирования [3, 30, 38].

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

Расчет производительности систем сотовой связи традиционно строился на интуитивных и грубых оценках производительности, построенных, например, на основе классических формул Эрланга [33, 70], которые были получены еще в 20-е годы прошлого века. Однако сети сотовой связи, как отдельный класс сетей телекоммуникаций, ставят перед теорией телетрафика большое количество задач новых типов, которые не возникают в традиционных стационарных кабельных сетях и требуют применения усовершенствованных методов теории телетрафика, таких, как многомерное распределение Эрланга, мультипликативные распределения разных типов, сложные модели нагрузки а также эффективные численные методы вычисления необходимых для практики параметров [12, 20, 27, 62, 73, 81]. Естественно, что использование известных подходов не исключает и разработку новых методов теории телетрафика оценки вероятностно-временных характеристик (ВВХ) систем сотовой связи.

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

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

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

ЗАКЛЮЧЕНИЕ

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

1. В разделе 2.2 разработан новый эффективный алгоритм вычисления точных значений стационарных вероятностей для модели одной соты с ожиданием;

2. В разделе 2.3 впервые предложен эффективный аналитический метод приближенной оценки вероятностей блокировки в модели одной соты с повторными вызовами;

3. В разделе 3.2 построена модель фрагмента двухуровневой ССПС с переупаковкой каналов, для которой сформулированы и доказаны условия мультипликативности стационарного распределения и дана подробная физическая интерпретация этих условий;

4. В разделе 3.3 для фрагмента двухуровневой ССПС без переупаковки каналов построена модель нагрузки на макросоту. Предложенная модель позволяет применить метод эквивалентных замен для анализа требуемых ВВХ.

1. Агафонов С. А., Герман А. Д., Муратова Т. В. Дифференциальные уравнения: Учебние для вузов. Под ред. В. С. Зарубина, А. П. Крищен-ко. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2000. - 348 с.

2. Андрианов В. И., Соколов А. В. Средства мобильной связи.— СПб.: БХВ-Петербург, 2001. 256 с.

3. Апанасович В. В., Тихоненко О. М. Цифровое моделирование стохастических систем. — Мн.: Изд-во "Университетское", 1986.— 127 с.

4. Вабков В. Ю., Вознюк М. А., Дмитриев В. И. Системы мобильной связи.- СПб.: СПбГУТ, 1999.- 330 с.

5. Вабков В. Ю., Вознюк М. А., Михайлов П. А. Сети мобильной связи. Частотно-территориальное планирование. — СПб.: СПбГУТ, 2000.— 196 с.

6. Вашарин Г. П. О вычислении моментов обслуженной и избыточной нагрузок сложной системы // Изв. АН СССР, Техническая кибернетика. — 1972. — № 1.-С. 42-51.

7. Вашарин Г. П. Лекции по математической теории телетрафика. — М.: Изд-во РУДН, 2004. 186 с.

8. Вашарин Г. П., Бочаров П. П., Коган Я. А. Анализ очередей в вычислительных сетях. Теория и методы расчета. — М.: Наука. Гл. ред. физ.-мат. лит., 1989.-336 с.

9. Вашарин Г. П., Кокотушкин В. А., Наумов В. А. Метод эквивалентных замен в теории телетрафика // Итоги науки и техники. — 1980. — Т. 11.- С. 82-122.

10. Башарин Г. П., Куренков Б. Е. Анализ избыточных потоков в сетях коммутации каналов // Проблемы передачи информации. — 1987. — Т. XXIII, № 3. С. 54-63.

11. Башарин Г. П., Меркулова О. В., Меркулов В. Е. Анализ интенсивности возникновения хендовер вызовов в сети сотовой подвижной связи / / Системы телекоммуникаций и моделирование сложных систем. — М.: Изд-во РУДН, 2004.

12. Башарин Г. П., Меркулов В. Е. Новые модели теории телетрафика для оценки качества обслуживания в сетях сотовой подвижной связи // Труды LVII Конф. РНТОРЭС. Т. 2. - 2002. - С. 183-185.

13. Башарин Г. П., Меркулов В. Е. Анализ пропускной способности в иерархических сетях сотовой связи // Электросвязь. — 2003. — № 4. — С. 4547.

14. Башарин Г. П., Меркулов В. Е., Смоленков Р. В. Некоторые модели для анализа характеристик качества обслуживания в сетях сотовой подвижной связи // Системы телекоммуникаций и моделирование сложных систем. М.: Изд-во РУДН, 2002. - С. 5-13.

15. Башарин Г. П., Меркулов В. Е., Смоленков Р. В. Построение математической модели нагрузки одного кластера сотовой подвижной связи / / Системы телекоммуникаций и моделирование сложных систем. — М.: Изд-во РУДН, 2003.

16. Башарин Г. П. Дубовкина О. В., Меркулов В. Е. Оценка вероятностей блокировки в одной соте сети сотовой подвижной связи с учетом повторных вызовов // Системы телекоммуникаций и моделирование сложных систем. М.: Изд-во РУДН, 2003.

17. Боровков А. А. Теория вероятностей: Учебное пособие для вузов. — М.: Наука. Гл. ред. физ.-мат. лит., 1986. — 432 с.

18. Бочаров П. П., Печипкин А. В. Теория массового обслуживания: Учебник. М.: Изд-во РУДН, 1995. - 529 с.

19. Вентцелъ Е. СОвчаров JJ. А. Теория случайных процессов и ее инженерные приложения. — М.: Высш. школа, 2000. — 383 с.

20. Вишневский В. М. Теоретические основы проектирования компьютерных сетей. — М.: Техносфера, 2003. — 512 с.

21. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. — М.: Наука, 1984.

22. Громаков Ю. А. Стандарты и системы подвижной радиосвязи.— М.: Эко-Трендз, 2000. 240 с.

23. Демьянов А. И. Методика достоверного оценивания пространственного распределения нагрузки сотовых сетей связи // Электросвязь. — 2002. — №2.-С. 39-41.

24. Зубарев Ю. Б. Основные подходы к внедрению систем подвижной связи 3-го поколения // Вестник связи. — 2000. — № 7.

25. Карташевский В. Г., Семенов С. Н., Фирстова Т. В. Сети подвижной связи. — М.: Эко-Трендз, 2001. — 302 с.

26. Корнышев Ю. П., Пшеничников А. П., Харкевич А. Д. Теория телетрафика. — М.: Радио и Связь, 1996.

27. Лагутин В. С., Степанов С. Н. Телетрафик мультисервисных сетей связи. — М.: Радио и связь, 2000. — 320 с.

28. Маковеева М. М., Шинаков Ю. С. Системы связи с подвижными объектами: Учеб. пособие для вузов. — М.: Радио и связь, 2002. — 440 с.

29. Меркулов В. Е. Алгоритм распределения нагрузки в сети системы сигнализации №7 // Системы телекоммуникаций и моделирование сложных систем. — М.: Изд-во ПАИМС, 2000.

30. Меркулов В. Е. Объектно-ориентированная модель для симуляции систем телекоммуникаций // Системы телекоммуникаций и моделирование сложных систем. — М.: Изд-во РУДН, 2003.

31. Меркулов В. Е., Салуэнъя А. С. Разработка программных средств для построения и анализа плана маршрутизации в сетях системы сигнализации №7 // Системы телекоммуникаций и моделирование сложных систем.- М.: Изд-во ПАИМС, 1999.

32. Наумов В. А. Численные методы анализа марковских систем. Учебное пособие. М.: Изд-во РУДН, 1985. - 36 с.

33. Ратынский М. В. Основы сотовой связи. Под ред. Д. Б. Зимина. — М.: Изд-во РУДН, 2002. 291 с.

34. Ромашкова О. Н. Обработка пакетной нагрузки в информационных сетях.- М.: МИИТ, 2001.- 196 с.

35. Самуйлов К. Е. Методы анализа и расчета сетей ОКС7: Монография. — М.: Изд-во РУДН, 2002.- 291 с.

36. Самуйлов К. Е., Никитина М. В. Сети сотовой подвижной связи в стандарте GSM // Сети. 1996. - № 6. - С. 10-14.

37. Степанов С. Н. Численные методы анализа систем с повторными вызовами. М.: Наука, 1983. — 230 с.

38. Таха X. А. Ввдение в исследование операций. Пер. с англ. — М.: Издательский дом "Вильяме", 2001. — 912 с.

39. Тихвинский В. О. Сети подвижной связи третьего поколения. Экономические и технические аспекты развития в России. Под ред. Ю. Б. Зубарева. — М.: Радио и связь, 2004. — 312 с.

40. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. СПб.: Изд-во "Лань", 2002. - 736 с.

41. Цыбаков Б. С. Модель телетрафика на основе самоподобного случайного процесса // Радиотехника. — 1999. — № 5. — С. 24-31.

42. Чеканов С. А. Моделирование и анализ пространственных случайных процессов // Электросвязь. — 2002. — № И. — С. 34-37.

43. Basharin G. P., Merkulov V. Е. Performance Analysis of a Two-Layer Cellular Mobile Communication // Вестник РУДН (Прикладная и компьютерная математика). — 2002. — Vol. 1, no. 1. — Pp. 14-24.

44. Basharin G. P., Merkulov V. E. Approximate Analysis of Repeated Calls Impact in Cellular Systems with Guard Channels // Вестник РУДН (Прикладная и компьютерная математика).— 2003.— Vol. 2, по. 1.— Pp. 5-12.

45. Basharin G. P., Merkulov V. E. Blocking Probability Analysis of New and Handover Calls in Cellular Mobile Networks with Repeated Attempts // Proc. ConTel Conf. Vol. 1. - Zagreb: 2003. - Pp. 278-281.

46. Basharin G. P., Merkulov V. E. Analysis of Repeated Calls in Cellular Systems with Guard Channels // Proc. NEW2AN Conf. Vol. 1. — St. Petersburg: 2004.-Pp. 119-122.

47. Boggia G., Camarda P. Modeling Dynamic Channel Allocation in Multicellular Communication Networks // IEEE J SAC. — 2001. Vol. 19, no. 11. — Pp. 2233-2242.

48. Bolotin V. A. Modeling Call Holding Time Distributions for CCS Network Design and Performance Analysis // IEEE JSAC. — 1994. — Vol. 12, no. 3. — Pp. 433-438.

49. Borst S., Boucherie R. J., Boxma 0. J. ERMR: a Generalized Equivalent Random Method for Overflow Systems with Repacking // Proc. ITC 16. — Vol. 1.- 1999.- Pp. 119-125.

50. Chuang J. C. Performance Issues and Algorithms for Dynamic Channel Assignment // IEEE JSAC. 1993. - Vol. 11, no. 7. - Pp. 995-963.

51. Cohen J. W. Basic Problems of Telephone Traffic Theory and the Influence of Repeated Calls // Philips Telecom. 1957. - Vol. 18, no. 2. - Pp. 49-100.

52. Cooper R. B. Introduction to Queueing Theory.— New-York, Oxford: Springer-Verlag, 1981. 360. pp.

53. Ekici E., Ersoy C. Multi-Tier Cellular Network Dimensioning // Wireles Networks. 2001. - no. 7. - Pp. 401-411.

54. Everitt D., Manfield D. Performance Analysis of Cellular Mobile Communication Systems with Dynamic Channel Assignment // IEEE JSAC. — 1989. — Vol. 7, no. 8.- Pp. 1172-1180.

55. Fang Y., Clamtac I., Lin Y. B. Channel Occupancy Time and Handoff Rate for Mobile Computing and PCS Networks // IEEE Trans, on Computers. — 1998. Vol. 47, no. 6. - Pp. 679-692.

56. Fortet R., Grandjean C. Congestion in a loss system when some calls want several devices simultaneously // Electrical Communication. — 1964. — Vol. 39. Pp. 513-526.

57. Gudmundson M. Cell Planning in Manhattan Environments // Proc. IEEE Vehicular Technology Conf. — Denver: 1992.

58. International Mobile Telecommunications-2000 (IMT-2000).— ITU-T Recommendation M.687-2, 1997.

59. Iversen V. B. The Exact Evaluation of Multi-Service Loss Systems with Access Control // 7th Nordic Teletraffic Seminar. — Vol. 1. — 1987. — Pp. 5661.

60. Iversen V. B. Review of the Convolution Algorithm for Evaluating Service Integrated Systems // Proc. COST-257. — Leidschendam: 1997.

61. Iversen V. B. Traffic Engineering of Cellular Wireless Communication Systems // COST-255 Symposium. Aachen: 2000.

62. Iversen V. B. Teletraffic Engineering Handbook. ITU-D, 2002. - 323 pp.

63. Iversen V. В., Stepanov S. N. The Calculation of Stationary Performance Measures of Loss Models with Access Control Based on the Concept of Truncation // 14th Nordic Teletraffic Seminar. Vol. 1. - 1998. - Pp. 277-286.

64. Kaufman J. S. Blocking in a Shared Resource Environment // IEEE Trans, on Communications. — 1981. — Vol. 29, no. 10. — Pp. 1474-1481.

65. Kelly F. P. Reversibility and Stochastic Networks. — Chichester: John Wiley & Sons, 1979.

66. Lagrange X. Multitier Cell Design // IEEE Comm. Magazine.— 1997.— no. 8. Pp. 60-64.

67. Lee W. С. Y. Mobile Cellular Telecommunication Systems.— New-York: McGraw Hill, 1989.

68. Marsan M. A., Carolis G., et al. An Approximate Model for the Computation of Blocking Probabilities in Cellular Systems with Repeated Calls // Proc. ITC-11. Vol. 1. - Yokohama: 1998. - Pp. 188-194.

69. Mouly M., Pautet M.-B. The GSM System for Mobile Communication.— Europe Media Duplication, 1992.

70. Onur E., Delic H., Ersoy C. e. a. On the Retrial and Redial Phenomena in GSM Networks // Proc. of the IEEE Wireless Comm. and Networking Conf. Chicago: 2000. - Pp. 885-889.

71. Orlik P. V., Rappaport S. S. On the Handoff Arrival Process in Cellular Communications // Wireless Networks. — 2001. — Vol. 7, no. 2.— Pp. 147157.

72. Persson H., Karlsson J. M. Handover Problems in Wireless Networks // 16th Nordic Teletraffic Seminar. Vol. 1. - 2002. - Pp. 241-252.

73. Rahnema M. Overview of the GSM System and Protocol Architecture // IEEE Comm. Magazine. 1993. - no. 4. - Pp. 92-100.

74. Rappaport S. S., Ни L. R. Personal Communication Systems Using Multiple Hierarchical Cellular Overlays // IEEE JSAC.- 1995.- Vol. 13, no. 2.-Pp. 406-415.

75. Retrial Queues / Ed. by G. I. Falin, J. G. C. Templeton. — Chapman h Hall, 1997.

76. Roberts J. W. A Service System With Heterogeneous User Requirements: Application to Multi-Service Telecommunication Systems // Perf. of Data Communication Systems and Their Application. — North-Holland Publ. Co., 1981.-Pp. 423-431.

77. Ross К. W. Multiservice Loss Models for Broadband Communication Networks. — London, Berlin, New-York: Springer-Verlag, 1995. — 343 pp.

78. Stasiak V. В., Glabowski M. Point-to-Point Blocking Probability in Switching Networks with Reservation // Proc. ITC-16. Vol. 3. - 2001. — Pp. 519528.

79. The Mobile Communications Handbook / Ed. by J. D. Gibson, E. M. Gibson. CRC Press, 1999. - 720 pp.

80. Tran-Gia P., Leibnitz K., Tutschku K. Teletraffic Issues in Mobile Communication Network Planning // Proc. ITC-11. — Vol. 1. — Yokohama: 1998. — Pp. 48-57.

81. Tran-Gia P., Mandjes M. Modeling of Customer Retrial Phenomenon in Cellular Mobile Networks // IEEE JSAC.- 1997.- Vol. 15.- Pp. 14061414.

82. Tsang D. H., Ross K. W. Algorithms to Determine Exact Blocking Probabilities for Multirate Tree Networks // IEEE Trans, on Communications. — 1990. Vol. 38, no. 8. - Pp. 1266-1271.

83. Wilkinson R. I Theories For Toll Traffic Engineering in the USA 11 Bell Systems Tech. Journal. — 1956. Vol. 35. - Pp. 421-514.

84. Zander R., Karlsson J. M. Layer Selection and Handover Prioritization in Hierarchical Cellular Networks // 16th Nordic Teletraffic Seminar. — Vol. 1. — 2002.-Pp. 1-12.

85. Zeng Q. A., Agrawal D. P. Handoff in Wireless Mobile Networks // Handbook of Wireless Networks and Mobile Computing (ed. by Ivan Stojmen-ovic). John Wiley & Sons, 2002.