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