Frequency scheduling algorithm with the allocation of the main and additional frequency bands.

Demichev Maksim Sergeevich Design Engineer of Information Security, JSC Scientific Production Enterprise "Radiosviaz" 660000, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31 mdemichev@yandex.ru Other publications by this author     Gaipov Konstantin Eduardovich PhD in Technical Science Docent, the department of Electronic Technology and Telecommunications, Reshetnev Siberian State University of Science and Technology 660000, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31 cyberjam@yandex.ru Other publications by this author     Demicheva Alena Alekseevna Student, the department of Security of Information Technologies, Reshetnev Siberian State University of Science and Technology 660031, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31 DemichevaAlena@yandex.ru Other publications by this author     Faizulin Rinat Faitulovich Postgraduate student, the department of Security of Information Technologies, Reshetnev Siberian State University of Science and Technology 660000, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31 cyberjam@yandex.ru

Malyshev Dmitrii Olegovich Postgraduate student, the department of Electronic Technology and Telecommunication, Reshetnev State University of Science and Technology 660000, Russia, Krasnoyarskii krai, g. Krasnoyarsk, pr. Krasnoyarskii Rabochii, 31 ma.hilfe@mail.ru

Введение. Современные системы беспроводной вычислительной сети, а также беспроводные системы связи, построены на статическом частотном планировании. Частотное планирование для пользователей в сотовой связи имеет характер динамического распределения, однако такое распределение осуществляется базовой станцией, по отношению к устройству сотовой связи, при этом не учитывается топология сети. Полностью динамическим частотным планированием системы сотовой связи нельзя назвать, так как выдача частот базовых станций осуществляется прямым назначением (статическим). При планировании в сетях, с множественной связностью на нескольких уровнях, таких как Mesh сети, одной из основных проблем является выбор частот, на которых будут взаимодействовать узлы Mesh сети между собой ^[2-5]. Большая часть систем беспроводной связи, в том числе Mesh сети, работают по стандарту 802.11 или 802.16 ^[10]. Известно достаточно большое количество подходов к решению задачи распределения частотного канала ^[1-9]. Однако многие из известных результатов, как показано в работе ^[11] не лишены недостатков ^[12].

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

При рассмотрении недостатков статического распределения частот, была поставлена цель: сформировать алгоритм распределения полос частот для некоторой топологии радиосети, где динамическим характером распределения является повторное применение разработанного алгоритма, в условиях изменения топологии радиосети. Тогда, пусть имеется N приемо-передающих радиоустройств (далее – узлы связи), имеющие некоторую взаимосвязанность, представляющую собой топологию радиосети, которую можно описать как ориентированный граф. Необходимо определить для каждого узла связи полосу частот, с применением повторного использования полос частот, исключающее интерференции, если это возможно в условиях рассчитанной топологии радиосети.

В данной работе представлено:

- алгоритм динамического частотного планирования с назначением дополнительных полос частот;

- пример работы алгоритма частотного планирования;

- описание алгоритма на языке C# (Приложение 1);

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

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

Решение. Для описания алгоритма решения поставленной задачи, введем основные переменные, списки и массивы:

1. Матрица А[i,j] – матрица смежности ^[13], описывает взаимосвязь узлов связи в топологии сети, где i – номер передающего узла (номер строки) связи, i∈[1..N], j – номер (номер столбца) принимающего узла связи, j∈[1..N].

2. Список Result[k] – список, где одна запись это основная и дополнительные полосы частот узлу связи k.

Формат записи в Result[k] для узла связи k (индекс k в качестве указателя на номер узла связи), рассматривается как массив, где Result[k,1] – запись основной полосы частот узла связи k, Result[k,m] – запись дополнительных полос частот, где m∈[2..M] и М – номер последней дополнительной полосы частот узла связи k.

Алгоритм распределения основных полос частот.

1. Составляем матрицу смежности А[i,j], согласно известной топологии радиосети, где в заголовке указывается «Номер узла связи». Пример на рисунке 1. Переход в пункт 2.

Рисунок 1. Пример матрицы смежности А[i,j].

2. Дополняем матрицу смежности А[i,j], областью заполнения и заголовком «Номер полосы частот». Пример на рисунке 2. Переход в пункт 3.

Рисунок 2. Матрицы смежности А[i,j], дополненная полем «Номер полосы частот».

На рисунке 1 и 2 область, выделенная серым цветом – заголовок, область выделенная белым цветом – рабочая область. Далее под матрицей смежности А[i,j] будет подразумеваться дополненный вариант, представленный на рисунке 2. В матрице А[i,j] две рабочие области – область связи (под номерами узлов связи, заполняется в пункте 1) и область полос частот (между заголовком «Номер полосы частот» и «Номер узла связи», заполняется в по ходу выполнения с пункта 3 по пункт 7).

3. В матрице А[i,j] первому номеру узла (i = 1) в области заполнения по строке и столбцу «Номер полосы частот» записываем 1. Result^[1,1] = 1. Пример на рисунке 3. Выбираем следующий узел (i = 2). Переход в пункт 4.

Рисунок 3. Назначение 1-ому узлу связи 1-ую полосу частот.

4. Выбираем строку и столбец узла связи i. В выбранной строке выделяем в единичных элементах столбцы Cn от первого элемента столбца, до элемента i. В выбранном столбце выделяем в единичных элементах строки Rn от первого элемента строки, до элемента i. Выделение осуществляется и в области заполнения «Номер полосы частот». Пример на рисунке 4. Переход в пункт 5.

Рисунок 4. Пример выделения строки и столбца i, с последующим выделением строки Rn и столбца Cn от узла N.

5. В области заполнения «Номер узла связи», на единичных элементах строк Rn выделяем столбцы Cn1 от первого элемента столбца, до единичного элемента строки Rn. На единичных элементах столбца Cn выделяем строки Rn1, от первого элемента строки, до единичного элемента столбца Cn. Выделение осуществляется и в области номеров полос частот. Пример на рисунке 5. Переход в пункт 6.

Рисунок 5. Пример выделения, строк Rn1 и столбцов Cn1, из единичных элементов столбца Cn и строки Rn соответственно.

6. Назначаем номер полосы частот для узла связи под номером i. Если в области заполнения «Номер полосы частот» (по строке и столбцу):

6.1. Присутствуют невыделенные и заполненные элементы, тогда узлу связи i назначается наименьший номер полосы частот из числа не выделенных номеров в строке или столбце и не равный номерам значений выделенных номеров (min), Result[i,1] = min;

6.2. Все заполненные элементы выделены, тогда узлу связи i назначается следующий наибольший номер полосы частот (max+1), Result[i,1] = max+1.

Записываем в область заполнения «Номер полосы частот» присвоенный номер полосы частот соответствующему узлу связи. Переход в пункт 7.

7. Все выделения снимаются. Если в матрице А[i,j] каждому узлу связи (i = N) назначена полоса частот – конец работы алгоритма, иначе выбираем следующий узел связи (i = i+1), переходим в пункт 4;

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

Алгоритм распределения дополнительных полос частот. Начало алгоритма в матрице А[i,j], начинается с первого номера узла связи (i = 1).

1. Выделяем строку и столбец узла связи i, в выделенной строке и столбце выделяем в единичных элементах столбцы Cn и строки Rn соответственно, выделение осуществляется и в области заполнения «Номер полосы частот». Пример на рисунке 6. Переход в пункт 2.

Рисунок 6. Пример выделения строки и столбца 1, с последующим выделением строки Rn и столбца Cn от узла 1.

2. В области заполнения «Номер узла связи», на единичных элементах строк Rn выделяем столбцы Cn1 от первого элемента столбца, до единичного элемента строки Rn. На единичных элементах столбца Cn выделяем строки Rn1, от первого элемента строки, до единичного элемента столбца Cn. Выделение осуществляется и в области номеров полос частот. Пример на рисунке 7. Переход в пункт 3.

Рисунок 7. Пример выделения, строк Rn1 и столбцов Cn1, из единичных элементов столбца Cn и строки Rn соответственно.

3. Назначаем дополнительные номера полос частот для узла связи под номером i. Если в области заполнения «Номер полосы частот» (по строке и столбцу):

3.1 Присутствуют невыделенные элементы, тогда узлу связи i назначаются дополнительные номера полос частот из числа не выделенных номеров в строке или столбце и не равный номерам значений выделенных номеров, Result[i,j] = n, где j – номер записи для одной назначенной полосы частот, который начинается с 2, n – номер назначенной дополнительной полосы частоты;

3.2 Все заполненные элементы выделены, назначение дополнительных полос частот не производится.

Переход в пункт 4.

4. Все выделения снимаются. Если в матрице А[i,j] каждому узлу связи (i = N) назначены дополнительные полосы частот – конец работы алгоритма, иначе выбираем следующий узел связи (i = i+1), переходим в пункт 1;

Вход новых узлов связи в сеть. Выход узла связи из сети.

Расчет полос частот для новых узлов связи в сеть необходимо производить как добавление новых узлов связи в конец матрицы A[i,j], и выполнить алгоритм распределения основных полос частот и дополнительных полос расчет для новых добавленных узлов связи.

Выход узла связи из сети осуществляется удалением соответствующей строки и столбца в матрице A[i,j], а также записи в списке Result, без перерасчета.

Определение значений для сформированных полос частот. На основе формулы из теоремы Шеннона-Хартли о пропускной способности канала связи в зависимости он уровня сигнал/шум (1), составим систему неравенств (2) решение которой является распределение ширины сформированных каналов связи, согласно «Алгоритма распределения основных полос частот».

В описанной формулы из теоремы Шеннона-Хартли (1) введены следующие обозначения:

(1)

v – скорость канала связи, бит/с;

f – ширина полосы частот канала связи, Гц;

SNR – отношение мощности сигнала к шуму.

В описанной системе неравенств (2) введены следующие обозначения:

– рассчитываемая ширина для полосы частот fn для узла связи M, Гц.

– требуемая скорость канала связи для узла связи M, бит/с;

– отношение мощности к сигналу для узла связи M;

– полоса частот fn, для группы узлов связи (или для одного узла связи, в зависимости результата «Алгоритма распределения основных полос частот»);

N – заданная ширина полосы частот для системы связи.

(2)

Пример. Имеется 9 узлов связи, которые образуют некоторую топологию радиосети, согласно рисунок 8. Необходимо, чтобы узлы связи 4, 5 и 6 удовлетворяли скорости передачи данных равным 100 Мбит/сек, остальные узлы связи – 10 Мбит/сек. Отношение сигнал/шум на каждом узле связи равен 23. Необходимо определить для каждого узла связи полосу частот с применением повторным применением полос частот, если на всю систему связи выделена ширина полосы частот равная 100 МГц.

Рисунок 8. Топология радиосети.

Составим матрицу смежности А[i,j] на основании известной топологии радиосети (рисунок 6), согласно пункту 1 и 2 алгоритма, также присвоим первому узлу связи 1-ую полосу частот, согласно пункту 3 алгоритма. Result^[1,1] = 1. Результат на рисунке 9.

Рисунок 9. Матрица смежности А[i,j].

Переходим к следующему узлу связи (i = 2). В соответствии с пунктом 4 выделим строку и столбец узла связи 2, рисунок 10.

Рисунок 10. Выделенная строка и столбец узла связи 2.

Выделяем столбцы Cn и строки Rn согласно пункту 4. Результат на рисунке 11.

Рисунок 11. Выделенные строка Rn и столбцы Cn узла связи 2.

Выделяем столбцы Cn1 согласно пункту 5. Из рисунка 11 видно, что столбцы Cn1 отсутствуют, так как отсутствуют единичные элементы на строке Rn.

Назначаем полосу частот для узла связи 2 в соответствии с пунктом 6 алгоритма, данный случай подходит под пункт 6.2, тогда назначаем узлу связи 2 номер полосы частот 2 и выполняем запись в область заполнения «Номер полосы частот». Все выделения снимаются. Result^[2,1] = 2 Результат на рисунке 12.

Рисунок 12. Результат назначения 2 узлу связи полосы частот.

Подобным решением узлу связи 3 будет назначен номер полосы частот 3, результат на рисунке 13. Рассмотрим решение назначения номера полосы частот для узла связи 4.

Выполним пункты 3, 4, 5, касательно узла связи 4, результат на рисунке 13.

Рисунок 13. Выделенные строки Rn, Rn1 и столбцы Cn узла связи 4.

В столбце области заполнения «Номер полосы частот», полосы частот 1, 2, 3 не выделены, тогда как в строке области заполнения «Номер полосы частот», полоса частот 1 выделена, значит, случай подходит под пункт 6.1. Назначаем узлу связи 4 номер полосы частот 2 и выполняем запись в область заполнения «Номер полосы частот». Все выделения снимаются. Результат на рисунке 14.

Рисунок 14. Результат назначения 3 и 4 узлу связи полосы частот.

Решение примера приведено на рисунке 15, итоговая запись списка Result на рисунке 16.

Рисунок 15. Общее решение примера.

Рисунок 16. итоговая запись списка Result.

Далее выполним назначение дополнительных полос частот для узлов связи топологии радиосети рисунка 8.

Рассмотрим назначение дополнительных полос частот для узла связи номер 7, так как при поиске дополнительных полос частот, для других узлов связи результатов не было. Выполним для узла связи выделение строки Rn, Rn1 и столбцы Cn, Cn1, согласно пункта 1 и 2 алгоритма распределения дополнительных полос частот. Результат на рисунке 17.

Рисунок 17. Выделенная строка Rn и столбцы Cn, Cn1 от узла связи 7.

Из рисунка 17 видно, что дополнительные полосы частот не могут быть номера полос 1 (собственная основная частота), 2 3, однако 4 полоса частот свободна, следовательно, назначаем узлу связи 7 дополнительную полосу частот – 4. Делаем запись в Result, общий результат решения на рисунке 18.

Рисунок 18. Назначение дополнительных полос частот для узла номер 7.

В соответствии с условиями составим систему неравенств (3) для определения значений для сформированных полос частот узлов связи.

(3)

Результат решения системы неравенств (3):

Для удовлетворения требованиям примера каждый из узел связи должен работать в на частотах, представленных на рисунке 18, в сопоставимости с результатом решения системы неравенств (3)

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

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

Приложение 1

Представленный фрагмент кода на языке C#, описывает работу «Алгоритма распределения основных полос частот» и «Алгоритм распределения дополнительных полос частот».

List Matrix = new List();

/*

Матрица смежности Matrix. Заполнение матрицы смежности, метод заполнения матрицы смежности, остается за правом выбора реализующего. Формат матрицы смежности Matrix, в соответствии с индексацией:

обозначения: УС – узел связи, F- частота, РБ – рабочая область

| | | 0 | | 1 | | 2 | | … | |index|

| 0 | | -1 | | -1 | | № F | | … | | № F |

| 1 | | -1 | | -1 | | № УС | | … | |№ УС|

| 2 | | № F | |№ УС| | РБ | | … | | РБ |

| … | | … | | … | | РБ | | … | | РБ |

|index| | № F | |№ УС| | РБ | | … | | РБ |

*/

List Result = new List();

/*

cписок Result. формат cписка Result: строка 0 – номер узла связи, строка 1 – основные частоты, последующие строки – резервные частоты, где запись 0 – отсутствие резервной частоты.

*/

List FreqList = new List();

/*

вспомогательный список частот, показывающий какие частоты можно выдавать узлу связи, а какие нет в процессе поиска. Формат cписка FreqList: строка 0 – номер полосы частот, строка 1 – возможность выбора полосы частот, где запись 0 – можно занимать полосу частот, 1 – нельзя занимать полосу частот.

*/

FreqList.Add(new List());

FreqList.Add(new List());

Matrix.Add(new List());

Matrix.Add(new List());

Matrix^[0].Add(-1);

Matrix^[0].Add(-1);

Matrix^[1].Add(-1);

Matrix^[1].Add(-1);

Matrix^[0][2] = 1;

Matrix^[2][0] = 1;

// Расчет основных полос частот

for (int i = 2; i < Matrix.Count; i++)

{

Result.Add(new List());

Result[i - 2].Add(i - 1);

}

Result^[0].Add(1);

FreqList^[0].Add(1);

FreqList^[1].Add(0);

for (int i = 3; i < Matrix.Count; i++)

{

int number_of_frequencies = 0;

for (int j = 2; j < Matrix.Count; j++)

{

if ((Matrix[i][j] == 1) && (number_of_frequencies != FreqList^[0].Count))

{

for (int k = 0; k < FreqList^[0].Count; k++)

{

if ((FreqList^[0][k] == Matrix^[0][j]) && (FreqList^[1][k] == 0))

{

number_of_frequencies++;

FreqList^[1][k] = 1;

k = FreqList^[0].Count;

}

}

if (number_of_frequencies != FreqList^[0].Count)

{

for (int n = 2; n < i; n++) // j

{

if ((Matrix[n][j] == 1) && (number_of_frequencies != FreqList^[0].Count) && (Matrix[n]^[0] != 0))

{

for (int k = 0; k < FreqList^[0].Count; k++)

{

if ((FreqList^[0][k] == Matrix^[0][n]) && (FreqList^[1][k] == 0))

{

number_of_frequencies++;

FreqList^[1][k] = 1;

k = FreqList^[0].Count;

}

}

}

}

}

for (int k = 0; k < FreqList^[0].Count; k++)

{

if ((FreqList^[0][k] == Matrix[j]^[0]) && (FreqList^[1][k] == 0))

{

number_of_frequencies++;

FreqList^[1][k] = 1;

k = FreqList^[0].Count;

}

}

for (int n = 2; n < i; n++)

{

if ((Matrix[j][n] == 1) && (number_of_frequencies != FreqList^[0].Count) && (Matrix^[0][n] != 0))

{

for (int k = 0; k < FreqList^[0].Count; k++)

{

if ((FreqList^[0][k] == Matrix[n]^[0]) && (FreqList^[1][k] == 0))

{

number_of_frequencies++;

FreqList^[1][k] = 1;

k = FreqList^[0].Count;

}

}

}

}

}

if (number_of_frequencies == FreqList^[0].Count)

{

int num = 0;

for (int k = 0; k < FreqList^[0].Count; k++)

{

if (FreqList^[0][k] > num)

{

num = FreqList^[0][k];

}

FreqList^[1][k] = 0;

}

num++;

Matrix^[0][i] = num;

Matrix[i]^[0] = num;

FreqList^[0].Add(num);

FreqList^[1].Add(0);

Result[i - 2].Add(num);

num = 0;

j = Matrix.Count;

number_of_frequencies = 0;

}

if ((j == (Matrix.Count - 1)) && (number_of_frequencies != FreqList^[0].Count))

{

int num = 0;

bool key = false;

for (int k = 0; k < FreqList^[0].Count; k++)

{

if ((FreqList^[1][k] == 0) && (key == false))

{

key = true;

num = FreqList^[0][k];

}

if ((FreqList^[1][k] == 0) && (key == true) && (num > FreqList^[0][k]))

{

num = FreqList^[0][k];

}

FreqList^[1][k] = 0;

}

Matrix^[0][i] = num;

Matrix[i]^[0] = num;

Result[i - 2].Add(num);

number_of_frequencies = 0;

}

}

}

// Расчет дополнительных полоса частот

for (int i = 2; i < Matrix.Count; i++)

{

int number_of_frequencies = 0;

for (int j = 2; j < Matrix.Count; j++)

{

if ((Matrix[i][j] == 1) && (number_of_frequencies != FreqList^[0].Count))

{

for (int k = 0; k < FreqList^[0].Count; k++)

{

if ((FreqList^[0][k] == Matrix^[0][j]) && (FreqList^[1][k] == 0))

{

number_of_frequencies++;

FreqList^[1][k] = 1;

k = FreqList^[0].Count;

}

}

if (number_of_frequencies != FreqList^[0].Count)

{

for (int n = 2; n < Matrix.Count; n++) // j

{

if ((Matrix[n][j] == 1) && (n != i) && (number_of_frequencies != FreqList^[0].Count) && (Matrix[n]^[0] != 0))

{

for (int k = 0; k < FreqList^[0].Count; k++)

{

if ((FreqList^[0][k] == Matrix^[0][n]) && (FreqList^[1][k] == 0))

{

number_of_frequencies++;

FreqList^[1][k] = 1;

k = FreqList^[0].Count;

}

}

}

}

}

for (int k = 0; k < FreqList^[0].Count; k++)

{

if ((FreqList^[0][k] == Matrix[j]^[0]) && (FreqList^[1][k] == 0))

{

number_of_frequencies++;

FreqList^[1][k] = 1;

k = FreqList^[0].Count;

}

}

for (int n = 2; n < Matrix.Count; n++)

{

if ((Matrix[j][n] == 1) && (n != i) && (number_of_frequencies != FreqList^[0].Count) && (Matrix^[0][n] != 0))

{

for (int k = 0; k < FreqList^[0].Count; k++)

{

if ((FreqList^[0][k] == Matrix[n]^[0]) && (FreqList^[1][k] == 0))

{

number_of_frequencies++;

FreqList^[1][k] = 1;

k = FreqList^[0].Count;

}

}

}

}

}

if (number_of_frequencies == FreqList^[0].Count)

{

j = Matrix.Count;

number_of_frequencies = 0;

}

if ((j == (Matrix.Count - 1)) && (number_of_frequencies != FreqList^[0].Count))

{

for (int k = 0; k < FreqList^[0].Count; k++)

{

if ((FreqList^[1][k] == 0) && (Result[i - 2][Result[i - 2].Count - 1] != FreqList^[0][k]))

{

Result[i - 2].Add(FreqList^[0][k]);

}

else

{

FreqList^[1][k] = 0;

}

}

number_of_frequencies = 0;

}

}

}