4430
правок
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями
Материал из WEGA
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях (посмотреть исходный код)
Версия от 12:31, 26 декабря 2016
, 26 декабря 2016→Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
Решение этой задачи линейного программирования может рассматриваться как потоковый граф <math>H = (V, E^H) \;</math>, где <math>E^H = \{ e(i) | \forall e \in E, 1 \le i \le K \} \;</math>. Хотя оптимальное решение этой задачи дает наилучшее возможное значение <math>\lambda \;</math> (скажем, <math>\lambda * \;</math>), с практической точки зрения возможны дополнительные улучшения: | Решение этой задачи линейного программирования может рассматриваться как потоковый граф <math>H = (V, E^H) \;</math>, где <math>E^H = \{ e(i) | \forall e \in E, 1 \le i \le K \} \;</math>. Хотя оптимальное решение этой задачи дает наилучшее возможное значение <math>\lambda \;</math> (скажем, <math>\lambda^* \;</math>), с практической точки зрения возможны дополнительные улучшения: | ||
• Поток управления может содержать ориентированные циклы. Такой случай может иметь место, поскольку алгоритм линейного программирования не старается напрямую минимизировать объем интерференции. Удаляя поток из ориентированного цикла (равное количество от каждого ребра), можно обеспечить ограничение сохранения потока; кроме того, поскольку в результате становится меньше передач, снижается объем интерференции. | • Поток управления может содержать ориентированные циклы. Такой случай может иметь место, поскольку алгоритм линейного программирования не старается напрямую минимизировать объем интерференции. Удаляя поток из ориентированного цикла (равное количество от каждого ребра), можно обеспечить ограничение сохранения потока; кроме того, поскольку в результате становится меньше передач, снижается объем интерференции. | ||
| Строка 54: | Строка 54: | ||
Вышеприведенное рассуждение предполагает, что было бы практичным среди всех решений, обеспечивающих оптимальное значение | Вышеприведенное рассуждение предполагает, что было бы практичным среди всех решений, обеспечивающих оптимальное значение <math>\lambda \;</math> в виде <math>\lambda^* \;</math>, найти такое, для которого общее значение следующей величины будет минимальным: | ||
<math>\sum_{1 \le i \le K} \sum_{e = (v, u) \in E} \frac{f(e(i))}{c(e)}.</math> | |||
