Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Автоматическое проектирование беспроводной сети, алгоритмы и мат.аппарат 
:(
    Опции темы
Radagast
Дата 27.11.2009, 23:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 17.7.2008

Репутация: нет
Всего: нет



Есть набор датчиков в 2-мерном пространстве, для каждого заданы координаты (х,у). Есть набор точек (х,у) потенциального размещения станций беспроводной связи (WiFi/ZigBee/etc). Каждый датчик подсоединяется проводом макс. длиной L к ближайшей станции.  Макс. радиус действия беспроводной связи (т.е. макс. расстояние между 2мя соседними станциями) = R. Естественно, что R >> L. Также установлено ограничение на макс. кол-во датчиков, подключенных к одной станции. Каждая станция должна находиться в области действия другой, т.е. в целом они должны образовывать связный граф, без "островков". Нужно оптимально разместить станции так, чтобы их было минимальное количество.

В дальнейшем эта задача будет усложняться (3-мерное пространство, ограничение по пропускной способности станций, возможность регулировать R для некоторых станций и т.д.), но нужно хотя бы решить в нынешней формулировке. Поиск в Гугле подсказал, что это - "задача размещения" (Facility location), но в ее формулировках (по крайней мере тех, что я нашел) важно лишь расположение станций относительно клиентов (в моем случае - датчиков), и не принимается во внимание расположение станций друг относительно друга. Скорее всего, на 1м этапе решается чисто Facility location (алгоритмы известны, жаль только, что они NP-hard), а потом если граф станций получился разъединенным, буду как-то подгонять размещение станций и добавлять новые.

К сожалению, в универе я не уделял много внимания предметам по теории алгоритмов, линейному программированию, функциям оптимизации и пр. - сдал лабу и забыл smile моя нынешняя работа связана с построением GUI на C++. А вот моя дипломная работа будет по теме, описанной в первых 2 абзацах. И перед бесстрастной строкой поиска Гугла понимаю, что без достаточного опыта и знаний в этой области искать иголку в стоге сена буду доооооолго :(
Собственно вопросы такие:
1) Встречались ли вы с программами для автоматизированного проектирования сетей, которые сами рассчитывают оптимальное размещение узлов примерно по таким принципам, как я написал?
2) Какую литературу, сайты и ключевые слова для поиска можете подсказать? Можно и на русском, и на английском, я этот язык знаю достаточно хорошо.
3) и какие в общем возникают предположения, какими алгоритмами и методами лучше всего решить эту задачу? Какой мат. аппарат может в этом помочь?
Заранее спасибо.

Это сообщение отредактировал(а) Radagast - 28.11.2009, 00:07
PM MAIL   Вверх
KQT
Дата 10.12.2009, 02:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 14
Регистрация: 17.10.2007

Репутация: нет
Всего: нет



Задача (насколько я её понял: за чем нужны датчики - не догнал) об упаковке шаров, в предложеном случае - дисков на проскости. Фундаментальный труд по этой теме: Ласло Фейеш Тот "Расположение на плоскости на сфере и в пространстве" - рекомендую к прочтению.

В случае плоскости она решена: строго доказано, что круги расположенные в верщинах гексогональной рёшетки (в углах пчелиных сот) образуют оптимальное минимальное накрытие/плотнейшую упаковку. Малейшее шевеление условий задачи, например, если круги разноколиберные, приводит к NP-сложным агоритмам... Собственно, накой стоит вопрос сложности? Раз посчитал, вкопал вышки и загарай под вайфаем?..

Это сообщение отредактировал(а) KQT - 10.12.2009, 02:13
PM   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0561 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.