Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях: различия между версиями

'''Объединенный алгоритм маршрутизации, распределения каналов и планирования линий связи'''

<math>\frac{f(e(i))}{c(e)} + \sum_{e' \in I(e)} \frac{f(e'(i))}{c(e')} \le c(q), \; \forall e \in E, 1 \le i \le K</math>. (5)

Первые два ограничения представляют собой ограничения потока управления. Первое из них является ограничением сохранения потока; второе гарантирует, что пропускная способность линий связи не будет нарушаться. Третье ограничение касается радиостанций в вершинах. Вспомним, что вершина 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): Четвертое ограничение касается нагруженности линий связи, что будет более детально рассматриваться в разделе «Планирование потока управления линий связи». Отметим, что все перечисленные ограничения являются обязательными условиями для любого допустимого решения. Однако эти ограничения не всегда являются достаточными. Таким образом, если найденное решение удовлетворяет этим ограничениям, оно может не быть допустимым. Следует начать с «хорошего», но не обязательно допустимого решения, удовлетворяющего всем ограничениям, и использовать его для построения допустимого решения, не ухудшая его качества.