Heuristics of Channel Allocation in Radio Networks


https://doi.org/10.15217/issn1684-8853.2016.3.47

Полный текст:


Аннотация

Введение: любая радиосеть, обслуживающая некий географический район, ассоциируется с определенной помеховой обстановкой, которая описывается так называемой матрицей совместимости, которая в свою очередь определяет требуемые частотные ограничения между отдельными радиосетями. Инженерный подход к решению проблемы назначения частот может быть интерпретирован как попытка найти такой частотный план, который бы удовлетворял всем ограничениям матрицы совместимости и имел бы минимальную протяженность. Комбинаторная природа этой задачи делает получение оптимального решения нереальным, и единственной альтернативой оказывается использование некоего набора эвристических алгоритмов, основанных на свойствах указанной матрицы. Цель: статистически устойчивые выводы о сравнительной эффективности эвристических алгоритмов (известных и предлагаемых), которые тестируются путем рассмотрения различных матриц. Методы: группа сравниваемых алгоритмов включает в себя как детерминированные, так и стохастические. И те и другие реализуют последовательные попытки назначить частоты сетям в соответствии с определенной упорядоченностью последних. Реализованная «экспертная» система генерирует требуемое количество матриц совместимости. Каждая матрица представляет собой конкретную проблему частотного планирования, которая должна быть решена с помощью всех алгоритмов группы. Некоторые алгоритмы используют простое упорядочивание сетей в процессе решения, в то время как другие включают в себя также определенное упорядочивание частот. Получение нижней границы протяженности частотного плана, то есть «почти наверняка» лучшего возможного частотного плана, реализовалось с помощью двух предложенных модификаций адаптивного случайного поиска. Результаты: алгоритмы с двойным упорядочиванием (сетей и частот) демонстрируют существенный выигрыш в эффективности. Частотные планы, полученные с их помощью, оказываются на несколько процентов короче (иногда выигрыш достигает 10 %), чем планы, полученные с помощью алгоритмов с упорядочиванием только сетей. Предложенные алгоритмы адаптивного случайного поиска обеспечивают системе частотного планирования оценку ее близости к «почти оптимальной». Практическая значимость: реальные задачи частотного планирования для радиосетей должны решаться с помощью группы эвристических алгоритмов с последующим выбором лучшего результата. Предложенные алгоритмы с двойным упорядочиванием, несомненно, эффективнее и должны использоваться прежде других.

Об авторе

В. З. Ляндрес
Негевский университет им. Бен-Гуриона
Россия


Список литературы

1. Amad E., Capone A., Malucelli C., Mannino C. Optimization Problems and Models for Planning Cellular Networks. In: Handbook of Optimization in Тeleсоттипісаtion. Springer, 2006, pp. 917939.

2. Mishra A. Advanced Сellular Network Planning and Optimization. John Wiley & Sons, 2007. 542 p.

3. Luna F., Estebanez C., Leon C., Chaves-Gonzalez J. M., Nebro A. J., Aler R. Optimization Algorithms for Larger-scale Real World Instances of the Frequency Assignment Problem. Soft Computing, 2011, vol. 15, no. 5, pp. 975-990.

4. Maximal difference ineffectiveness for networks with only co-channel constraints is observed for the case of density 0.5.

5. Effectiveness of algorithms from the group FA is always higher than of algorithms from the group AF, so ordering of frequencies occurs to be positive.

6. The proposed algorithm of adaptive search asymptotically reduces to the exact value of minimal span. Its gain in comparison to the considered greedy algorithms varies from 5 to 15 %. Ordering of frequencies leads to the shortage of the required number of iterations, so the «double tuning» heuristic is more effective than «simple adaptive search».

7. Lempiainen J., Manninen M. Radio Interface Systуm Planning for M/GPS/UMTS. Kluwer Academic Publishers, 2001. 346 p.

8. Hale W. K. Frequency Assignment: Theory and Applications. Proc. of the IEEE, 1980, vol. 68, no. 12, pp. 1497-1514.

9. Lyandres V., Panich M. On some Algorithms of Vertices Coloring of the Weighted Graphs. Proc. of ORSA CSTS Conference "The Impact of Emerging Туchnology on Computer Science and Operations Research", January 5-7, Williamsburg, U.S.A., 1994, pp. 80-82.

10. Lyandres V., Gigi E., Santiago R. C. Channel Assignment for Cellular Mobile Network with Nonhomoge-neous Cells. IEE Proceedings Communications, 2006, vol. 153, no. 1, pp. 61-68.


Дополнительные файлы

Для цитирования: Ляндрес В.З. . Информационно-управляющие системы. 2016;(3):47-50. https://doi.org/10.15217/issn1684-8853.2016.3.47

For citation: Lyandres V. Heuristics of Channel Allocation in Radio Networks. Information and Control Systems. 2016;(3):47-50. (In Russ.) https://doi.org/10.15217/issn1684-8853.2016.3.47

Просмотров: 35


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1684-8853 (Print)
ISSN 2541-8610 (Online)