4430
правок
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями
Материал из WEGA
Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях (посмотреть исходный код)
Версия от 00:17, 14 декабря 2016
, 14 декабря 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 27: | Строка 27: | ||
Линейная программа LP (1) для нахождения потока, максимизирующего значение Я: | Линейная программа LP (1) для нахождения потока, максимизирующего значение Я: | ||
При условии | |||
Первые два ограничения представляют собой ограничения потока управления. Первое из них является ограничением сохранения потока; второе гарантирует, что пропускная способность линий связи не будет нарушаться. Третье ограничение касается радиостанций в вершинах. Вспомним, что вершина IWMN (беспроводной ячеистой мультирадиосети без интерференции?) v 2 V имеет I(v) радиостанций и, следовательно, может попасть в распределение не более чем I(v) каналов, 1 < i < K. Один из способов моделирования этого ограничения основан на наблюдении, что в силу ограничений интерференции вершина v может быть вовлечена не более чем в I(v) одновременных коммуникаций (с разными соседями, доступными в результате одного перехода). Иными словами, это ограничение следует из J2l<i<KJle=(u,v)€EXe,i,t +Jli<i<KJle=(v,u)€EXe,i,t < I(v): Четвертое ограничение касается нагруженности линий связи, что будет более детально рассматриваться в разделе «Планирование потока управления линий связи». Отметим, что все перечисленные ограничения являются обязательными условиями для любого допустимого решения. Однако эти ограничения не всегда являются достаточными. Таким образом, если найденное решение удовлетворяет этим ограничениям, оно может не быть допустимым. Следует начать с «хорошего», но не обязательно допустимого решения, удовлетворяющего всем ограничениям, и использовать его для построения допустимого решения, не ухудшая его качества. | |||
Решение этой задачи линейного программирования может рассматриваться как потоковый граф H= (V, EH), где EH = fe(i)j8e 2 E; 1 < i < Kg. Хотя оптимальное решение этой задачи дает наилучшее возможное значение A (скажем, A*) с практической точки зрения возможны дополнительные улучшения: | |||
• Поток управления может содержать ориентированные циклы. Такой случай может иметь место, поскольку алгоритм линейного программирования не старается напрямую минимизировать объем интерференции. Удаляя поток из ориентированного цикла (равное количество от каждого ребра), можно обеспечить ограничение сохранения потока; кроме того, поскольку в результате становится меньше передач, снижается объем интерференции. | |||
• Поток управления может использовать длинный путь, в то время как доступны более короткие. Отметим, что более длинные пути включают больше передач по линиям связи. В таком случае нередко возникает возможность снижения интерференции в системе за счет перераспределения потока на более короткие пути. | |||
Вышеприведенное рассуждение предполагает, что было бы практичным среди всех решений, обеспечивающих оптимальное значение A для A*, найти такое, для которого общее значение следующей величины будет минимальным: | |||
