Содержание к диссертации
Введение
ГЛАВА 1. Особенности построения вероятностных моделей одноранговых сетей .
1.1. Принципы построения файлообменных и потоковых одноранговых сетей.
1.2. Вероятностные модели функционирования одноранговых сетей .
1.3. Особенности построения моделей и анализа показателей функционирования беспроводных сетей .
1.4. Цели и задачи исследований. 47
ГЛАВА 2. Модель процесса буферизации данных в потоковых одноранговых сетях .
2.1. Параметры и вероятностные характеристики модели.
2.2. Построение математической модели. 57
2.3. Аналитический метод расчета матрицы переходных вероятностей.
2.4. Анализ показателей эффективности одноранговой сети.
ГЛАВА 3. Анализ вероятностных характеристик моделей беспроводных взаимодействий устройств .
3.1. Модель выделения ресурсов беспроводной сети объёмами случайного размера.
3.2. Вероятностная модель взаимодействия беспроводных устройств .
3.3. Примеры численного анализа показателей эффективности функционирования беспроводной сети взаимодействующих устройств.
Заключение 112
Список источников 114
- Вероятностные модели функционирования одноранговых сетей
- Особенности построения моделей и анализа показателей функционирования беспроводных сетей
- Построение математической модели.
- Вероятностная модель взаимодействия беспроводных устройств
Вероятностные модели функционирования одноранговых сетей
Ниже в данном разделе более подробно рассмотрен наиболее распространённый на сегодняшний день пиринговый протокол обмена данными BitTorrent [34, 42, 61, 64], являющийся одной из реализаций самой используемой технологии обмена данными в одноранговых сетях. Он позволяет пользователям распространять большие объёмы данных, не предъявляя жестких требований к их техническому оборудованию и ширине полосы пропускания, по сравнению с протоколами HTTP или FTP. При традиционном централизованным подходе - размещении файлов на сервере, являющемся хранителем и единственным источником информации, вся нагрузка приходится на оборудование сервера, что может привести к невозможности передачи данных большому количеству пользователей. Протоколы типа BitTorrent являются альтернативным методом распространения данных, который позволяет использовать пропускную способность канала связи всех пользователей, пытающихся получить эти данные, с целью увеличения общей производительности и надежности системы распространения информации. При размещении файла в сети BitTorrent пользователь, предоставляющий файл, делает его доступным всем пользователям сети. Такой пользователь, имеющий весь файл целиком, называется сидом (англ. seed - источник, сеятель). Наличие в сети хотя бы одного сида позволяет другим пользователям начать загрузку этого файла на свои устройства. Процесс распространения файла называется раздачей (англ. seeding – сеять, раздавать). Пользователь, который пока не имеет всех частей файла и продолжает загружать их от других пользователей, называется личером (англ. leecher – пиявка). Новые личеры, запрашивающие тот же файл, подключаются к раздаче и начинают получать разные части этого файла. Когда какой-либо личер получил несколько частей файла, протокол BitTorrent позволяет ему самому стать источником тех частей файла, которые уже доступны ему. Это позволяет личерам взять на себя небольшую часть задачи сида, увеличивающуюся по мере скачивания файла, и начать помогать ему, распределяя нагрузку по раздаче. Таким образом, личер одновременно загружает и раздает данные. После того, как один из личеров закончил загрузку файла, он также становится сидом, помогая оставшимся личерам получить файл целиком.
Такое распределение нагрузки в системе BitTorrent приводит к лавинообразному распространению файла между пользователями. По мере присоединения все большего числа пользователей к раздаче вероятность успешной загрузки файла увеличивается. По сравнению с традиционным централизованным способом распространения данных такой метод позволяет значительно уменьшить требования к оборудованию и ширине полосы пропускания первоисточника файла. Он также обладает повышенной устойчивостью к отказам, уменьшает зависимость доступности файла от первоначального источника.
Чтобы начать распространение файлов в системе BitTorrent, достаточно разместить на веб-сервере специальный файл с расширением .torrent. Этот специальный торрент-файл содержит информацию о распространяемом файле или нескольких файлах, которые будут распространяться через систему BitTorrent, о их размере, хеш-сумме для проверки целостности и адресе трекер-сервера. Пользователи, желающие получить распространяемый файл должны получить торрент-файл и загрузить его в клиентское приложение, реализующее протокол BitTorrent. Трекер-серверы или трекеры отвечают за то, чтобы помочь пользователям найти друг друга. Обмен данными между клиентами и трекером происходит по протоколу HTTP. Пользователь отсылает трекеру свой адрес и информацию из торрент-файла, в ответ на это он получает адреса других пользователей, скачивающих или раздающих этот же файл. Далее пользователь периодически информирует трекер о ходе процесса и получает обновлённый список адресов полностью или частично имеющих запрошенный файл.
Чтобы публикуемый файл был доступен, необходимо, чтобы в системе находился хотя бы один сид. Требования к полосе пропускания трекера и веб-сервера очень малы, в то время как сид, начинающий раздачу файла, должен раздать, по крайней мере, одну полную копию оригинального файла.
Все вопросы по передаче данных решаются между пользователями без участия трекера, которому время от времени передается информация о скоростях загрузки и раздачи, хотя это делается только в целях сбора статистики. Трекер несет ответственность только за то, чтобы помочь пирам найти друг друга, возвращая запрашивающему пиру случайные наборы адресов пиров. Этот алгоритм наиболее отказоустойчив, так как большинство других алгоритмов либо слишком сложны, либо слишком быстро сегментируются, т.е. одна часть пиров перестает «видеть» другую часть.
Протокол BitTorrent разделяет файл на порции данных - фрагменты фиксированного размера, обычно 256 Кбайт. Это позволяет протоколу отслеживать, какие именно части файла имеет каждый пользователь. Механизм обмена так называемыми «буферными картами» - информацией о доступных порциях данных, приводит к небольшим дополнительным затратам трафика, но позволяет надежно использовать все доступные ресурсы.
Алгоритм выбора частей файла для загрузки существенно влияет на эффективность обмена данными и производительность системы в целом. При выборе очередной порции данных для скачивания личеры обычно отдают предпочтение той порции, которая находится в наличии у наименьшего числа пользователей. Такой алгоритм позволяет быстрее распространять те части файла, которые наиболее востребованы, откладывая передачу часто встречающихся частей на более позднее время. Это значительно уменьшает вероятность того, что пользователь, готовый отдать какую-либо из доступных ему частей файла, будет простаивать из-за отсутствия требуемой части.
Особенности построения моделей и анализа показателей функционирования беспроводных сетей
Принцип обмена данными в потоковых сетях P2P (далее будем опускать термин Р2Р для краткости изложения) идентичен принципу обмена данными в файлообменных сетях P2P на базе протокола BitTorrent [34, 46, 64], который в необходимом объёме описан в главе 1 диссертационной работы. Однако при построении модели потоковой сети следует учитывать, что ограничения на время доставки порции данных в оборудование пользователя имеют решающее значение.
Для построения модели буферизации данных в потоковой сети необходимо определить понятие буфера [74, 1]. Буфер пользователя потоковой сети – это область памяти его терминала, предназначенная для кэширования недавно загруженных порций данных. Под порцией данных понимается фрагмент потоковых данных конечного размера, например, фрагмент размера 256 кбайт или фрагмент для воспроизведения на экране терминала в течение 1 с. На рис. 2.1 показаны схемы буферов пользователей потоковой P2P-сети, в которых может храниться до 9 порций данных, например, от «A» до «I». Цифрами на рис. 2.1 обозначены номера позиций (мест) буфера, при этом порция «A» из позиции 8 будет воспроизведена уже на следующем такте, а порция «I» в позиции 0 расположена дальше всего от воспроизведения. В показанном на рис. 2.1 примере у i -го пользователя имеются все порции данных, а у j -го пользователя не загружены порции «C», «F» и «G», поэтому буферные карты этих пользователей имеют вид
Пользователи могут загружать порции данных, как от сервера, так и друг от друга. Для этого они регулярно обмениваются между собой буферными картами. В буферной карте каждого пользователя содержится информация о том, какие порции данных пользователь уже успел загрузить и, следовательно, готов ими обмениваться. После того, как пользователь получил буферную карту другого пользователя (так называемого «целевого пользователя»), он может загрузить одну или несколько порций данных, находящихся в буфере целевого пользователя. При этом имеется возможность загружать порции данных от одного или нескольких соседних целевых пользователей одновременно.
Заметим, что вновь подключившийся к сети пользователь имеет пустой буфер и не только бесполезен для остальных пользователей с точки зрения получения от него порций данных, но и конкурирует с ними за загрузку имеющихся у пользователей сети порций данных [24]. При отключении пользователя с заполненным буфером он лишает остальных возможности загрузить от него порции данных. Таким образом, и подключения, и отключения пользователей ухудшают показатели качества функционирования сети, что особенно критично при использовании технологии P2P для распространения потоковых данных в мобильных сетях. Это будет учтено в модели сети заданием вероятностей а подключения пользователя к сети и /? отключения пользователя от сети (рис. 2.2).
Модель подключения и отключения пользователя На возможность обмена порциями данных между пользователями влияют также задержки передачи информации от источников потоковых мультимедийных данных – так называемые «лаги» (рис. 2.3). Лаг определяет сдвиг по времени между пользователями потоковой P2P-сети, воспроизводящими одно и то же потоковое видео [86, 129, 24, 27, 69].
Сдвиги по времени (лаги) между терминалами пользователей Лаги имеют порядок нескольких секунд, например, когда i -й пользователь (рис. 2.4) видит на своем экране момент гола в трансляции футбольного матча (порция данных «F»), а n-й пользователь в это же время видит на своем экране ещё только передачу, приведшую к этому голу (порция «A»). Лаги оказывают влияние на показатели качества сети, поскольку они уменьшают зоны «пересечения» буферов пользователей, и поэтому число доступных для обмена порций данных в буферах пользователей снижается.
Влияние лагов на пересечение буферов пользователей Важными параметрами, влияющим на показатели качества функционирования сети, являются ограничения на максимально доступные скорости загрузки и раздачи для различных пользователей [87, 27], которые могут отличаться в зависимости от типа подключения, фонового трафика и других условий, что проиллюстрировано на рис. 2.5.
Для большинства пользователей выполняется условие d(n) u(n), поскольку для типичного подключения к сети максимальная скорость загрузки выше максимальной скорости раздачи данных. Таким образом, даже если согласно буферной карте у целевого пользователя (h-го пользователя на рис. 2.6) имеются все недостающие порции данных, то п -й пользователь может не успеть загрузить их все из-за ограничения на скорость раздачи целевого пользователя. /г-пользователь u(h)=2 d(n)=5 w-пользователь
В случае, когда согласно буферной карте у целевого пользователя имеется несколько порций данных из числа недостающих, но загрузка их всех невозможна из-за ограничения на скорость раздачи целевого пользователя, необходимо определить, какие именно из доступных порций данных будут выбраны для загрузки от целевого пользователя. Это определяется с помощью «стратегии загрузки» (англ. Download Strategy), задачей которой является определение номера места буфера для загрузки очередной порции данных [86, 1]. Основными стратегиями выбора порций данных для загрузки в потоковых сетях являются стратегии Latest First (LF) и Greedy (Gr). При стратегии LF пользователь пытается загрузить наиболее «свежие», реже всего встречающиеся в сети, порции данных, а при стратегии Gr выбираются самые «старые», наиболее близкие к воспроизведению порции данных (рис. 2.8). Кроме того, возможность многоуровневого кодирования данных позволяет загружать потоковое видео с разными уровнями качества, что особенно актуально при использовании технологии P2P для распространения потокового контента в мобильных сетях [88, 23]. Так, пользователю не всегда целесообразно загружать данные для просмотра в высоком качестве, если технические возможности его соседей (скорость загрузки d(n), характеристики видеоплеера) позволяют просматривать видео лишь в более низком качестве. Выбор стратегии существенно влияет на показатели эффективности функционирования системы. Так, при использовании стратегии LF повышается вероятность непрерывного просмотра, стратегия Gr значительно снижает задержку начала воспроизведения видеопотока, а применение стратегии, учитывающей требования пользователей к уровням качества просмотра видео, позволяет оптимизировать функционирование сети по нескольким критериям.
Построение математической модели.
В данном разделе диссертационной работы исследована модель выделения радиоресурсов пользователям беспроводной сети, реализованной на базе технологии LTE. Модель учитывает особенности выделения ресурсов, описанные в разделе 1.3 диссертационной работы, и которые, по сути, заключаются в том, что объём ресурса соты сети ограничен, а запросы пользователей (абонентов, устройств и пр.) порождают требования на предоставление им ресурса, объём которого, вообще говоря, является случайной величиной с заданным распределением. В этом и заключается отличие предлагаемой в диссертации модели от известных ранее моделей. Во-первых, в известных моделях мультисервисных сетей с потерями [78, 11] в явном виде отсутствовал параметр, определяющий наличие ресурса заданного ограниченного объёма, и, во-вторых, требования пользователей к занимаемому ресурсу являлись детерминированными. Например, в работах Ф. Келли [37], К. Росса [56], Г.П. Башарина [80], С.Н. Степанова [142], К.Е. Самуйлова [127, 11] и других известных специалистов в области теории телетрафика, посвященных анализу мультисервисных сетей с потерями, эти требования определялись как некоторые константы, соответствующие числу условных единиц ширины полосы пропускания, занимаемой в сети соединением пользователя.
В данном разделе, во-первых, исследована мультисервисная многопотоковая модель, для которой получено стационарное распределение описывающего ее функционирование марковского процесса, и показано, что это стационарное распределение имеет мультипликативный вид. Во-вторых, исследован важный случай, когда на систему поступает один поток заявок, но для обслуживания каждой заявки требуется не один, а несколько типов ресурса. Для этой модели также получено стационарное распределение, а также формулы для вычисления ее основных вероятностных характеристик. Идея построения модели и начальные исследования были проведены в [121], а в [120, 122] получены нижеизложенные результаты, где автор участвовал в выводе и проверке корректности основных уравнений, в получении формул для вероятностных характеристик, а также в проведении численного эксперимента и анализе показателей эффективности функционирования соты беспроводной сети. Перейдем к описанию математических моделей, которые построены в терминах многолинейных систем массового обслуживания (СМО).
Рассмотрим многолинейную СМО, изображенную на рис. 3.1, c N co приборами, на которую поступают L независимых пуассоновских потоков заявок с интенсивностями Л1,Л2,...,Я1 соответственно. Длительности обслуживания заявок независимы между собой, от поступающих потоков и экспоненциально распределены с параметром //г для заявок типа /. Обозначим R общий объём ресурса имеющегося в системе для обслуживания заявок и будем считать, что объём ресурса, требуемого заявкам типа / является случайной величиной (св.) с функцией распределения (ФР) F,(x), не зависящей от процессов поступления и обслуживания заявок. Обсуживающимся заявкам присваивается номер, причем так, чтобы заявка с номером i имела i-е по величине остаточное время обслуживания. Этот номер следует отличать от порядкового номера заявки. При поступлении новой заявки все находящиеся на обслуживании заявки перенумеровываются. Для обслуживания каждой заявки требуется некоторый случайный объём ресурса, а поступившая заявка теряется, если в момент поступления свободного ресурса системы не достаточно. В момент начала обслуживания заявки суммарный объём занятого ресурса увеличивается на величину выделенного ей ресурса, а в момент окончания обслуживания заявки суммарный объём занятого ресурса уменьшается на ту же величину.
В момент завершения интервала постоянства либо с вероятностью Aj /(Я + //(/1,...,4)) поступает новая заявка, либо с вероятностью //(/1,...,/ t)/(A + //(/1,...,/ t)) завершается обслуживание. При нумерации обслуживаемых заявок в порядке убывания их остаточных времён обслуживания, в момент окончания обслуживания систему покидает заявка с максимальным номером. Поэтому, если ti - момент завершения обслуживания, то в этот момент процесс X(f) переходит из состояния (k,lJ2,..Jk,c1,...,Ck) в состояние (к-1,11,...,1к_х,сх,...,ск_ . В момент ti поступления заявки возможен переход процесса X(t) в различные состояния. Пусть поступившей в момент ti заявке типа J требуется ресурс объёма с и обозначим d:=c1 +с2 + ... + ск суммарный объём занятого в этот момент ресурса.
Вероятностная модель взаимодействия беспроводных устройств
Отношение сигнала к интерференции плюс шум (SINR, Signal to Interference plus Noise Ratio) является одной из основных характеристик качества канала в беспроводных сетях связи [4, 5, 9]. Предполагается, что формула для вычисления величины SINR имеет вид - базовая мощность сигнала рассматриваемого передатчика, / - расстояние между передатчиком и приемником, а – коэффициент потерь (path loss exponent), принимающий значение от 2 (при условии прямой видимости) до 6 (в худшем случае), / - мощность интерферирующего сигнала от других передатчиков, а2 - мощность шума. Заметим, что принцип повторного использования частот (Frequency Reuse) в беспроводных сетях связи поколения 4G/5G (4h/5h Generation) позволят назначать одну и ту же единицу ресурса сети (например, один и тот же ресурсный блок LTE) нескольким парам взаимодействующих терминалов, если интерференция не превосходит определенного стандартами уровня [4, 5, 9].
Рассмотрим случай, когда несколько принимающих терминалов (приемников) и один передающий терминал (передатчик), образующие т.н. кластер, расположены на плоскости внутри круга радиуса г0, причем передающий терминал расположен в центре круга. Такой кластер образуется, например, при проведении интерактивного занятия преподавателя с учениками, когда можно предположить, что передающий терминал располагается в центре круга, а принимающие терминалы равномерно распределены внутри круга. Для передачи данных на каждую пару взаимодействующих терминалов внутри кластера планировщиком распределения радио ресурсов в беспроводной сети назначается по одному ресурсному блоку LTE, и тогда сигналы взаимодействующих пар не будут интерферировать друг с другом. Но если в соседнем помещении также проходит интерактивное занятие, и там использованы те же ресурсные блоки, то пары из соседних кластеров, использующие один и тот же ресурсный блок, будут создавать помехи друг другу. Сведем задачу к анализу взаимодействия двух пар терминалов в двух кластерах, как показано на рис. 3.3.
Остальные пары, которые создают помехи целевой паре TR0, обозначим Щ=(Тх,Щ) и будем называть их интерферирующими. Расстояние между Rxt и Тхг обозначим R., а расстояние между Тх0 и Txt обозначим Д.. Мощность интерферирующего сигнала от пары TR является функцией от расстояния между приемником Rxt из целевой пары и интерферирующим передатчиком Тхп таким образом, она будет зависеть от расстояния между Тхг и Rx0, которое обозначим Д.
Рассмотрим систему, показанную на рис. 3.3, с одним источником интерференции (/ = 1). Тогда в условиях отсутствия шума искомой характеристикой является отношение сигнал-интерференция SIR, вычисляемое по формуле Будем считать, что R0, U1и / являются св. с заданными ФР. Тогда задача состоит в нахождении числовых характеристик св. SIR. Для решения задачи ниже предлагается метод нахождения совместной плотности распределения св. R0 и Д, что в свою очередь позволяет вычислять, например, начальные моменты E[SIRj св. SIR.
Как видно из формулы (3.23), св. SIR прямо пропорциональна св. Д, которая в свою очередь зависит от св. R0. В этом случае для нахождения характеристик св. SIR необходимо найти совместное распределение св. R0 и Д. Введем обозначения: :=i , &:=t/15 :=Г1, Ъ Ц, тогда
В разделе 3.3 диссертационной работы приведен пример численного анализа с использованием формул (3.27)-(3.29) для случая равномерно распределенных св. R и их и у. В рассматриваемом примере полученный выше метод использован для расчета математического ожидания отношения сигнал-интерференция, которое определяется следующей формулой:
Чтобы численно проиллюстрировать применение полученных в разделе 3.1 теоретических результатов, рассмотрим отдельную соту сети LTE с одной базовой станцией, которая обслуживает клиентов, пользующихся услугой видеоконференции. Пусть каждый клиент генерирует видеопоток высокого качества в восходящем канале со средней скоростью 1 Мбит/с. Тогда, если предположить, что в одной конференции участвуют четыре клиента, то каждый из них должен отдавать свой видеопоток и принимать три потока от других клиентов. Таким образом, средняя скорость в восходящем канале для одного клиента составляет 1 Мбит/с, а в нисходящем канале - 3 Мбит/с. Если запрос клиента по каким-либо причинам не сможет удовлетворить требованиям услуги видеоконференции к пропускной способности, то ему будет отказано в ее предоставлении. В рассматриваемом примере двумя типами ресурсов для клиентов являются ширина полосы пропускания восходящего и нисходящего каналов. Для стандарта LTE пиковая скорость передачи данных в идеальных условиях для нисходящего и восходящего каналов равны соответственно 150 Мбит и 75 Мбит в секунду.
В рассматриваемом нами примере [122] число типов ресурсов М = 2 с ограничениями R1 = 75 (для восходящего канала) и i = 150 (для нисходящего канала). При этом допустим, что максимальное количество абонентов на одной базовой станции не может превышать JV = 100. Пусть требования клиентов к ресурсу каждого типа распределены по закону Эрланга 2-го порядка, т.е. функция распределения совместного требования имеет вид:
На рис. 3.4 и 3.5 показаны вероятность блокировки и средние значения занятых ресурсов, вычисленные по формулам (3.19) и (3.20) соответственно. Для нахождения среднего квадратического отклонения необходимо найти 2-й момент объёма занятого ресурса, который можно получить по формуле, аналогичной формуле (3.20): которого расположен передатчик Тх0, а интерферирующий передатчик Тх1 - в кольце вокруг передатчика Тх0 внутренним радиусом г0 и внешним радиусом h0, как показано на рис. 3.7. Тогда св. R0 расстояния от целевого передатчика Тх0 до соответствующего ему приемника и св. U1 расстояния от целевого передатчика Тх0 до интерферирующего передатчика Тх1 имеют распределения Д(г) = 2г, 0 г 1,
По предложенному выше методу были рассчитаны математическое ожидание и среднеквадратическое отклонение отношения сигнал-интерференция, показанные на рис. 3.8 в зависимости от математического ожидания расстояния [ ] между целевым передатчиком Тх0 и интерферирующим передатчиком Тх1.
Из графика видно, что с ростом расстояния между целевым и интерферирующим передатчиками обе числовые характеристики отношения сигнал-интерференция растут, поскольку мощность интерферирующего сигнала убывает.
Также для иллюстрации метода из раздела 3.2 был рассмотрен еще один случай взаимодействия двух устройств в беспроводной сети. Предполагается, что все передатчики расположены согласно пуассоновскому точечному процессу с плотностью Л, целевой приемник Rx0 расположен внутри круга радиуса г0 с центром в точке, где расположен его соответствующий передатчик Гх0, и при этом предполагается, что интерферирующие передатчики не могут находится внутри этого круга. Как и в предыдущем примере, интересующим нас показателем качества функционирования беспроводной сети является отношение сигнала к шуму SIR.
