Диссертация (1137248), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

Безусловным плюсом данногорешения является существенное сокражение издержек на регулярнуюсмену энергетических режимов. К недостаткам подхода относят суще­ственное увеличение задержек передачи данных.2. Сеть последовательно меняет энергетические схемы своей работы вме­сте с переходами стока между участками траектории. Сток для каждо­го энергетического режима накапливает общее время работы в нем,и пока это время меньше оптимального , переводит в него сеть приочередном проходе по -му участку. Достоинством подхода являетсяуменьшение задержек передачи на начальном этапе работы сети.

Од­нако постепенно в цикле работы сети будет все больше и больше пауз,связанных с завершением использования определенных схем (общее вре­68мя для них становится равным оптимальному ).3. В каждом цикле время работы сети в -м режиме определяется исходяиз следующего соотношения: = *Таким образом, обеспечивается регулярное функционирование сети безбольших задержек при передаче данных. Однако резко возрастает энер­гия, затрачиваемая на постоянную схему конфигураций.Предлагаемый метод решения общей задачи ПДС заключается в сведе­нии задачи нахождения маршрута стока к оптимизационной задаче частично­целочисленного линейного программирования.Введем следующие целочисленные переменные: =⎧⎪⎨1, если (j-k) входит в последовательность смены конфигураций⎪⎩0, в обратном случае =⎧⎪⎨1, если > 0⎪⎩0, если = 0Пусть = || || - матрица смежности графа : =⎧⎪⎨1, если (, ) ∈ ⎪⎩0, если (, ) ̸∈ Тогда постановка задачи ПДС в терминах частично-целочисленного ли­нейного программирования будет иметь вид:69 (1 , 2 , .

. . , ) =∑︁ → (3.4)=1при следующих ограничениях∑︁=1 +∑︁∑︁ − ≤ , = 1..(3.5)=1 =1,̸=∑︁0, = 1(3.6),+1 = 1(3.7)=1∑︁=1∑︁ ==0,̸=∑︁+1∑︁ , = 1..(3.8)=1,̸= = , = 1..(3.9)=0 · ≤ ≤ · , = 1..(3.10) − + · ≤ − 1, ∀, ∈ [1..], ̸= (3.11) ≤ , ∀, ∈ [1..], ̸= (3.12) ∈ {0, 1}, , ∈ NПо сравнению с задачей (3.1) целевая функция не изменилась.

По преж­нему - это общее время автономной работы сети, складывающееся из сум­марной продолжительности пребывания стока на всех позициях. Однако те­перь в каждое ограничение из набора (3.5) добавлены дополнительные слага­емые, связанные с энергией, затрачиваемой на смену энергетических схем.Для построения маршрута в структуру задачи вводятся некоторые искус­ственные дополнения. Так как движение может начинаться с любой точки,70в графе позиций стока появляются дополнительные виртуальные вершины– 0 и + 1, чтобы зафиксировать начало и конец маршрута. Тогда марш­рут стока будет выглядеть следующим образом. Изначально сток находитсяв вершине 0, затем перемещается в одну из вершин, определяемую модельюкак оптимальное начало маршрута.

После прохождения всех вершин, длякоторых > 0, сток перемещается в конечную точку маршрута – + 1.Генерация маршрута обеспечивается ограничениями (3.6) - (3.8). Для вы­полнения равенства (3.6) происходит установка в 1 одной из переменных 0, .Аналогично окончание маршрута фиксируется установкой в 1 одной из пере­менных ,+1 . Чтобы в каждую вершину входила только одна дуга, исполь­зуется ограничение (3.9). Так, если = 1, должна быть одна и только однадуга, входящая в k-ю вершину и, наоборот, если = 0, входящих дуг бытьне должно. Выражение (3.8) выравнивает входящий и исходящий потоки длякаждой посещаемой вершины, что автоматически обеспечивает построениемаршрута. Однако при этом не исключаются возможности образования цик­лов, не связанных с основным маршрутом. На рис.

3.2 показан пример такогоцикла.Рис. 3.2. Пример изолированного циклаДля этого в модель вводится дополнительное ограничение (3.11), анало­гичное тому, что применяется в известной задаче коммивояжера и ее поста­71новке в виде задачи ЦЛП [58]. Вспомогательные переменные служат дляприсвоения посещенным вершинам индексов в соответствии с порядком про­хода стока через них: если = 1, то < .

Таким образом, становитсяневозможным повторное посещение одной и той же вершины графа.Ограничения (3.10) связывают две части задачи и ограничивают марш­рут только теми позициями , для которых > 0. и представляютсобой соответственно минимальное и максимальное время нахождения стокана каждой из позиций. Данные величины в приведенной выше постановке за­дачи играют больше формальную роль. Лишь можно настраивать, изме­няя поведение мобильного стока. При больших значениях перемещениестока будет сильно ограничено из-за необходимости оставаться на каждойпозиции длительное время. фактически выполняет только роль связкивещественных переменных и двоичных переменных .

Более того, необхо­димо задавать его таким образом, чтобы искусственно не ограничить общеевремя работы сети. На практике вместо следует подставлять большоечисло, превышающее время работы одного узла сети на минимальной на­грузке:∈ ,∈ > maxНаконец, ограничения (3.12) разрешают переходы только по ребрам гра­фа .3.3. Метод решения задачи планирования движениястокаОчевидно, что задача частично-целочисленного линейного программи­рования является в общем виде NP-трудной [2], точное решение не может72быть получено за допустимое время для больших значений даже на самыхмощных вычислителях.

Сложность обусловлена наличием целочисленных пе­ременных и, как следствие, комбинаторным характером общих приемов ре­шения подобных задач [38].Необходимость решения задач большой размерности обусловлена следу­ющим практическим фактором. Результаты имитационного моделирования(см. следующую главу), говорят о том, что управляемую мобильность целе­сообразно применять в больших сетях, состоящих из нескольких сотен уз­лов. Такие сети покрывают территории в несколько десятков квадратныхкилометров. Учитывая необходимость сохранять в определенных пределахзадержки передачи данных, общее количество позиций стока также должнобыть большим.Предлагаемый далее метод направлен на снижение вычислительной слож­ности задачи при сохранении значения целевой функции близким к оптималь­ному. Метод принимает во внимание следующие особенности рассматривае­мой предметной области:1. Поиск оптимального маршрута не является целью задачи оптимизации,так как считается, что сток неограничен в ресурсах.

Следовательнонеобязательно искать путь, проходящий через каждую вершину одинраз.2. Энергетические затраты на перенастройку сети, определяемые величи­нами − пренебрежимо малы по сравнению с затратами на передачуданных.Разделим задачу (3.4) на две подзадачи. Первая подзадача (LP) анало­гична оптимизационной проблеме (3.1), то есть она включает только одиннабор ограничений без учета дополнительной энергии Σ . В результате еерешения находится подмножество ̃︀ ⊆ : ∀ ∈ ̃︀ > 0.73Вторая подзадача (ROUTE) будет решать проблему построения марш­рута по найденному подмножеству позиций ̃︀ и набору ограничений на пере­мещения стока, задаваемому матрицей .

Данная задача может быть реше­на одним из эвристических алгоритмов [14], например “Идти в ближайшуюнепосещенную вершину”. Однако в ходе ее решения может быть полученапринципиальная невозможность построения такого маршрута. Например, нарис. 3.3 показан пример решения задачи LP, по которому невозможно по­строить маршрут. Серым цветом обозначены вершины из , входящие вомножество ̃︀ , получаемое в результате решения задачи LP.Невозможность построения маршрута (необязательно проходящего черезкаждую вершину ровно один раз) означает существование разбиения множе­ства ̃︀ :̃︀ = ̃︀1 ∪ ̃︀2 ∪ .

. . ∪ ̃︀ : ∀, ∈ [1..] : ̃︀ ∩ ̃︀ = ∅, ∀ ∈ , ∈ : (, ) ̸∈ В таком случае происходит возврат к первой подзадаче, но в ее структурудобавляется ряд фиксирующих ограничений одного из двух видов:Рис. 3.3. Пример решения задачи LP1. = 0. То есть позиция стока исключается из рассмотрения на следу­74ющем шаге. Обозначим множество таких позиций через 0 .2. >= . Другими словами, позиция назначается как обязательнаядля посещения стоком. Множество таких позиций обозначим через 1 .Отметим, что множества 0 и 1 являются непересекающимися, так как однаи та же вершина не может быть отмечена одновременно как обязательная изапрещенная для посещения стоком.Таким образом, получится итерационный алгоритм (далее обозначаетсяITER), который может быть представлен в общем виде на псевдокоде:Алгоритм 1 Общий алгоритм решения задачи ПДС (ITER)Входные данные: = ( , ), Γ = { (1), (2), .

. . ()}Выходные данные: Маршрут движения стока Π1: 0 ← ∅2: 1 ← ∅3: цикл4:̃︀ = ( , 0 , 1 , Γ )5:Π ← (̃︀ , )6:если Π == NULL7:Изменить 0 , 18:конец если9: пока Π = NULLОпределим достаточные условия выполнения алгоритма за конечное чис­ло шагов.Лемма 3.3.1. Если |0 | = − 1, итерационный процесс останавливается.Доказательство Если |0 | = − 1, то остается только одна вершина, незафиксированная ограничением вида = 0.

Задача LP в таком случаепринимает вид: = → 75при условиях: ≤ , = 1..Решением задачи будет = min∈[1..] . Очевидно, что маршрут сто­ка будет включать только точку , то есть получится сценарий непо­движного стока.Теорема 3.3.2. Пусть 0 - множество вершин, запрещенных для посеще­ния на i-м шаге алгоритма. Тогда итерационный процесс выполняется мак­симум за шагов (где - количество вершин в графе позиций стока ),если 0 ⊂ 0+1 .Доказательство Согласно алгоритму, 01 = ∅. Исходя из условия теоре­мы, |0 | < |0+1 |. Возьмем крайний случай последовательного добавления в0 одного элемента на каждой итерации.

Тогда |01 | = 0, |02 | = 1, . . . |0 | = − 1. Но согласно лемме 3.3.1, если |0 | = − 1, итерационный процессостанавливается.Из теоремы 3.3.2 следует один из возможных алгоритмов решения задачиITER - увеличение на каждом шаге множества 0 . Для этого предлагаетсянесколько эвристик:∙ 0 = 0 ∪ {} : ∈ ̃︀ , ∀ ∈ ̃︀ : ≥ . То есть из вершин, полученныхв результате решения задачи LP, выбирается такая, для которой времяпребывания стока наименьшее.∑︀∑︀∙ 0 = 0 ∪ ̃︀ : ∀ ∈ [1..], ̸= : ∈̃︁ ≥ ∈̃︁ .

Характеристики

Список файлов диссертации