Примеры самоорганизующихся сетей и их сравнительная оценка

В предыдущей статье мы предложили один из возможных критерий качества организации системы.

Рассмотрим систему, которая представляет собой канал коллективного доступа - подсистему Z^* и совокупность маршрутизаторов, которые определяют маршруты между каждой парой абонентов этого канала - подсистему Z^**:

Рисунок 1

Предположим, что в этой системе используется статическая маршрутизация, (сеть типа ad hoc) то есть маршруты заданы таким образом, что каждой паре абонентов X_i и X_j соответствует единственный (непосредственный) маршрут X_i - X_j. При таких условиях подсистема Z^** может находиться в единственном состоянии и, следовательно, H(Z^**)=0. Если в процессе эксплуатации системы, условия радиослышимости в канале меняются, то H(Z^*)>0. Но подсистема Z^** никак не реагирует на эти изменения, поэтому H₀=H₁, и R=H₀-H₁=0. Следовательно, система предельно неорганизованна.

Допустим теперь, что подсистема Z^** построена таким образом, что каждому непосредственному маршруту X_i - X_j, (кроме маршрутов от X_k) ставиться в «жесткое» соответствие единственный обходной маршрут вида X_i – X_k - X_j (X_k – некая общая «точка доступа», вариант построения сети ad hoc):

Рисунок 2

В данном случае, энтропия H(Z^**) не может равняться нулю, поскольку подсистема Z^** реагирует на изменение состояний радиолучей – отказ основного маршрута приводит к использованию обходного маршрута.

Попытаемся оценить уровень организации такой системы. Действуем поэтапно, в соответствии с выражениями (3.2) – (3.6).

1) Будем считать, что вероятность отказа любого радиолуча в канале равна P. Тогда

H(Z*)= - Cmj {Pj (1- P)m-j log2[ Pj (1- P)m-j]

(3.1)

где

m – общее число радиолучей в радиосети, равное

m = n(n-1)/2

(3.2)

n – общее число маршрутизаторов, включая «точку доступа».

2) Если считать, что каждый маршрутизатор (кроме точки доступа) выбирает обходной или основной маршрут с равной вероятностью (по принципу «орёл – решётка»), то

H(Z**) = log2 2(n-1)(n-2)/2 = (n-1)(n-2)/2

(3.3)

3) Общее число ситуаций в Z^*, которым соответствует однозначная реакция подсистемы Z^**, ограничено. Действительно (см. рисунок 2), если абонент X_i намерен передать пакет X_j, то он воспользуется обходным маршрутом X_i – X_k - X_j только в том случае, если вышел из строя радиолуч X_i - X_j. Аналогичным образом, абонент X_j воспользуется обходным маршрутом X_j – X_k – X_i только при отказе радиолуча X_i - X_j и т.д.

И вообще, однозначное соответствие состояния подсистемы Z^**состоянию сети Z^* возможно только тогда, когда изменения состояний радиолучей будут происходить только в пределах подмножества E₁ (на рисунке 2 эти лучи выделены жирными линиями). Причем в любой из таких ситуаций P(Z_j^*|Z_k^**)=1.

Изменения структуры вне E₁ на поведение системы не влияют, так как любая неудачная попытка передачи пакета по основному маршруту между любыми X_iE₁ всегда приводит к передаче того же пакета по обходному маршруту (независимо от состояния радиолуча X_i - X_k) Поэтому:

H (Z*|Z**) =CLk Pk(1-P)L-k {-Cn-1j Pj(1-P)n-(j+1) log2 [Pj(1-P)n-(j+1))]}

(3.4)

где L = (n-1)(n-2)/2 – число радиолучей в E₁.

Графики зависимостей Н(Z^*) и R от величины P (для сети, включающей в себя 8 маршрутизаторов), приведены на рисунке 3.

Рассматривая эти графики, нетрудно заметить, что рассматриваемая система далека от совершенства: RН(Z^*) только при весьма надежных каналах связи (P0.05).

Рисунок 3

Но, при определённых условиях, уровень организации такой системы может быть признан достаточно высоким. Например, если радиолучи, связывающие абонентов сети с общей «точкой доступа», обладают достаточно высокой надежностью – с вероятностью отказа =0.15, а остальные каналы менее надежны – с P0.5, то

H(Z*)= -CLk Pk log2[Pk(1-P)L-k] - Cn-1j  j(1-)n-(j+1) log2[ j(1-)n-(j+1)]	(3.5)
H (Z*|Z**) =CLk Pk(1-P)L-k {-Cn-1j  j(1-)n-(j+1) log2 [j(1-)n-(j+1))]}	(3.6)

и величина R сопоставима с H(Z^*) даже при P=0.5 (см. рисунок 4).

Отметим что в данном случае, степень организации системы увеличивается за счёт уменьшения энтропии H(Z^*), которое, в свою очередь, достигается за счёт повышения надежности части радиолучей. Очевидно, что при их стопроцентной надёжности (то есть при =0) величина H(Z^*) станет равной R, и уровень организации в системе может считаться идеальным.

Теперь предположим, что все элементы системы «сверхнадежны». Тогда, система, после завершения этапа её развертывания, будет описываться «железобетонным» графом, который всегда соответствует заранее известному «замыслу системы». Очевидно, что такая система не способна к адаптации, (она просто не нужна), а какая либо информация об её состоянии – бесполезна, поскольку H(Z^*)=H(Z^**)=0. Но, к сожалению, построить такие простые и надёжные сети (тем более, в полевых условиях) далеко не всегда возможно.

Рисунок 4

По-видимому, в самоорганизующихся полевых сетях потребуется реализация более совершенных алгоритмов динамической маршрутизации, основанных на полном знании текущей топологии сети. К таким алгоритмам, прежде всего, следует отнести алгоритмы «состояния связей», используемые в протоколах типа OSPF.

С другой стороны, повышение уровня организации требует наличия и своевременного распространения достоверной информации об изменениях топологической структуры сети, которая не может быть получена без определенного расхода «энергии» или ресурсов сети. Причём расход «энергии», необходимый для получения и распространения такой информации, может с избытком поглотить выигрыш от её использования. Например, служебный поток, содержащий полную информацию о структуре сети связи, может превысить её пропускную способность.

Поэтому, есть основания предполагать, что высокоорганизованные протоколы маршрутизации могут найти применение только в высокоскоростных сетях (типа wi-fi). В низкоскоростных УКВ-сетях более целесообразна реализация алгоритмов типа ad-hoc.

Критерий качества организации системы

Напомним, что в первой части мы рассмотрели основные особенности самоорганизующихся систем.
Интуитивно, отсутствие организации отождествляется с хаосом. На основании этой интуитивной предпосылки, в кибернетике появилось специфическое понятие организации, которое применимо к широкому кругу объектов и систем и дает численную меру статистических связей между элементами системы - R.

Это понятие основано на следующих рассуждениях. Пусть имеется некая система, которая состоит из отдельных частей или подсистем (не обязательно однородных). Каждая из этих подсистем, в процессе их существования или деятельности может принимать некоторое множество состояний, над которым задано конкретное распределение вероятностей.

Если все подсистемы разобщены, то есть поведение одной подсистемы никак не влияет на поведение других, или, иными словами, все подсистемы независимы, то система будет являться предельно неорганизованной.

Другой предельный (идеальный) случай – когда состояние одной подсистемы однозначно определяет состояние всех остальных.

Если подсистемы разобщены, то энтропия множества состояний каждой подсистемы Z может быть определена следующим образом:

H(Z) = - Pk log2 Pk	(2.1)

где k = 1, 2, … N – возможные состояния подсистемы Z_i, а P_ik – вероятность того, что эта подсистема окажется в состоянии k. При этом если P_k=0.5, то

H(Z) = log2N

(2.2)

В предельно неорганизованной системе общая энтропия будет максимальна и равна сумме энтропий её подсистем. Так, для системы, состоящей из двух подсистем – Z^* и Z^**, будем иметь:

H0 (Z*, Z**) = H (Z*) + H (Z**)	(2.3)

Если в системе имеются связи между её элементами (подсистемами), то есть эти элементы взаимно влияют друг на друга, то система организуется, и общая энтропия становится меньше суммы энтропий её элементов, и будет составлять:

H1 (Z*, Z**) = H (Z**) + H (Z*|Z**) = H (Z*) + H (Z**|Z*)	(2.4)

где H (Z^*|Z^**) – условная энтропия, которая определяется выражением:

H (Z*|Z**) = - P(Zk**) P(Zj *|Zk**) log2 P(Zj *|Zk**)

(2.5)

где P(Z_j^*|Z_k^**) – вероятность состояния Z_j^*, если имеет место состояние Z_k^**.

Величина H (Z^*|Z^**) всегда удовлетворяет следующему условию:

0  H (Z*|Z**)  H (Z*)	(2.6)

при этом величина H(Z^*|Z^**)=0 только в том случае, если каждое состояние Z_j^* однозначно определяется состоянием Z_k^**. При таких условиях все P(Z_j^*|Z_k^**)=1, и H(Z^*|Z^**)=0 (в силу того, что log1=0). Данный случай соответствуют идеальной организации системы.

Таким образом, в результате организации системы её энтропия H₁ будет ниже максимальной энтропии H₀. Это уменьшение энтропии может служить численной мерой организованности системы – R:

R = H0 – H1 = H (Z*) - H(Z*|Z**)

(2.7)

при этом величина R=0 будет соответствовать предельно неорганизованной системе, а величина R=Н(Z^*) – системе, которая организована идеально.

Следует отметить, что величина R определяет уровень организации системы в процессе её функционирования (в динамике), а именно: величина R может быть больше нуля только тогда, когда система способна адаптироваться к изменениям состояний её элементов.

Далее мы приведем примеры самоорганизующихся сетей связи.

Самоорганизующиеся системы связи и их основные особенности

Введение

Наверное, вы не раз задумывались над поразительным отличием систем, которые существуют в природе, от систем, созданных человеком (например, современными системами связи). Первые - устойчивы к внешним воздействиям и склонны к росту и развитию. Для вторых – характерно резкое ухудшение их функционирования даже при незначительных нарушениях условий эксплуатации или при ошибках в управлении.

Само собой напрашивается вывод: нужно позаимствовать опыт организации систем, который накоплен природой, и использовать этот опыт в нашей деятельности. Но, для этого необходимо выяснить основные законы построения «природных» систем, основные принципы их организации, а также механизмы возникновения и изменения порядка в этих системах. При этом основное внимание должно быть сосредоточено не на процессах управления обменом информацией (будем считать, что эти процессы нам хорошо известны), а на принципах построения, организации и развития таких систем.

Подобного рода идеи достаточно глубоко рассматривались ещё в первой половине прошлого столетия, но, в силу относительно скромных технических возможностей того времени, широкого практического применения в системах связи не нашли. В настоящее же время активно разрабатываются системы, в которых многие задачи (в основном, связанные с маршрутизацией) решаются автоматически. Такие системы, основаны на представлении всех возможных структур системы как её состояний, возникающих в результате многовариантного и неоднозначного воздействия на эту систему «извне».

Но более интересны (и, по-видимому, ещё более перспективны) те системы, которые способны не только к адаптации к случайно сложившимся ситуациям, но и к образованию новых структур, которые более сложны, чем исходные. Такая способность в какой-то степени соответствует естественному механизму природного движения: от элементарного и примитивного — к более сложному и более совершенному.

Основным особенностям таких систем (применительно к вопросам организации связи) и посвящена данная статья. В этом статье рассмотрены:

● основные признаки организации и самоорганизации;

● один из возможных критериев оценки качества организации;

● методика оценки системы по данному критерию (на конкретных примерах);

● возможный вариант структуры системы управления системой связи.

Если вас заинтересует данная проблема, то кое-какая информация может быть получена из Интернета. Ключевые слова: открытая система, кибернетика, синергетика, энтропия.

Основные свойства организованных и самоорганизующихся систем

Известно, что система может считаться организованной, если она обладает следующими свойствами:

Система должна быть открытой, то есть система должна реагировать на какие либо внешние воздействия.

Организация может иметь место лишь в системах достаточного уровня сложности, поскольку недостаточно сложные системы не способны ни к спонтанной адаптации, ни, тем более, к эволюции.

Фундаментальный принцип организации – возможность возникновения нового порядка через флуктуации состояний элементов системы.

Такие флуктуации (случайные отклонения) могут подавляться за счёт отрицательных обратных связей, обеспечивающих сохранение прежнего состояния системы (например, с помощью механизмов адаптации к случайным сбоям её элементов).

Но в более сложных открытых системах, могут использоваться алгоритмы коллективного поведения элементов и подсистем, которые, через кратковременное «хаотическое» состояние, приводят, либо к разрушению прежней структуры, либо к возникновению нового порядка. Яркий пример – «взрывной» характер потоков служебной информации при адаптации к изменениям состояний линий сети связи, которые могут возникнуть при использовании динамической маршрутизации.

Открытая система должна быть достаточно далека от «точки равновесия» (тупиковой ситуации). В точке равновесия (тупике) сколь угодно сложная система не способна к какой-либо организации. В положении, близком к «равновесию» и без достаточного притока воздействий на систему извне, любая система будет неуклонно приближаться к «гибели», поскольку организованная система не всегда способна возвращаться в то состояние, в котором она когда-то была.

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

При этом, для того, чтобы предотвратить (или хотя бы отсрочить) «гибель» системы, самоорганизующаяся система должна иметь «внешнюю поддержку». Действительно, если изменение состояния системы обусловлено только воздействием суммы случайных факторов (например, спонтанными изменениями условий радиослышимости в системах связи), то «время жизни» такой системы будет ограничено и такая система не способна эффективно противостоять необратимым воздействиям внешней среды. Например, система связи может быть живучей только в том случае, если в ней будут присутствовать механизмы позитивного воздействия на эту систему, которые обеспечивают:

- ремонт (или замену) поврежденных узлов и линий;

- укрепление структуры системы путем ввода в её состав новых элементов;

- организацию маневров имеющимися ресурсами (частотами, каналами и т.д.).

Это свойство имеет решающее значение – только при получении ресурсов «извне» (и наличии механизмов «усвоения» этих ресурсов) система будет способна к эволюции. При недостатке же таких ресурсов, система будет постепенно деградировать.

Так же необходимо отметить, что очень важным является критерий качества организации системы.

Реализация модели канала

Продолжение темы имитационного моделирования канала коллективного доступа.

При построении алгоритма имитации работы всех каналов сети, сеть рассматривается как совокупность параллельно протекающих процессов. Каждый процесс есть некоторая последовательность событий, приводящих к изменению состояний синхронных автоматов, описывающих поведение элементов сети, причём, под событием понимается любое изменение сигналов на входах этих автоматов.

В общем случае, эти процессы не должны считаться независимыми, а а должны взаимодействовать между собой.

Принципы взаимодействия процессов могут быть проиллюстрированы следующим примером. Представим себе фрагмент сети, включающий в себя N абонентов, работающий на одной и той же частоте. Такой фрагмент может рассматриваться как система массового обслуживания с одним прибором, который обслуживает некий поток требований от N станций. Если требование, придя в систему, застаёт прибор свободным, то оно занимает прибор и обслуживается в нём в течение некоторого промежутка времени, после чего покидает систему. В противном случае, требование поступает в очередь к прибору, где будет дожидаться завершения обслуживания всех ранее поступивших в систему требований. Причём эта очередь «виртуальна» - требования могут быть сосредоточены как в одном узле, так и распределены по разным узлам.

В такой системе, на начальных фазах обслуживания, «передатчик» каждого узла может находиться в одном из следующих состояний:

1. ожидание очередного кадра;
2. ожидание освобождения канала;
3. запуск таймера, определяющего время начала передачи кадра (основной принцип канального протокола – «слушать», прежде чем «вещать»);
4. ожидание завершения данного интервала;
5. захват канала и передача кадра.

Переход «передатчика» из одного состояния в другое, осуществляется под воздействием комбинаций входных сигналов. Эти сигналы могут поступать, как извне - от модуля, имитирующего поведение «высшего» уровня, так и от других автоматов - автоматов того же уровня.

Например, (см. рисунок 1), переход автомата из состояния «ожидание кадра» в состояние «ожидание освобождения канала» осуществляется при появлении сигнала «требование передачи», а переход в следующее состояние – «запуск таймера отсрочки» - зависит от состояний аналогичных автоматов, претендующих на тот же канал.

Если какой либо другой аналогичный автомат находится в состоянии «захват канала», то рассматриваемый автомат будет получать сигнал «канал занят».

Рисунок 1

Из рассматриваемого примера видно, что в моделируемой сети могут сосуществовать параллельные «типовые» процессы, каждый из которых может находиться в своём уникальном состоянии. Но, при их имитации на одной ЭВМ, эти события необходимо рассматривать последовательно. Поэтому, совокупность параллельно протекающих процессов должна быть представлена в виде упорядоченной последовательности моментов наступления событий во времени.

При таких условиях, сканируя эту последовательность, и определяя, в каждый наступивший момент реакции автоматов на изменения входных сигналов, можно сымитировать любую ситуацию в системе. При этом, любая сложившаяся ситуация может быть представлена в виде вектора Z=║Z_n║, каждый элемент которого - Z_n, соответствует конкретному автомату - M_n, а значение этого элемента – состоянию данного автомата. Например, если некий автомат M₁ занял канал, (состояние St₄), а автомат M₂ ожидает его освобождения (состояние St₁), то фрагмент вектора Z будет содержать информацию, которая показана на рисунке 2:

Конечный автомат	Текущее состояние
M1	St4
M2	St1
.	.

Рисунок 2

При наступлении особого состояния, (изменении входных сигналов), этот вектор модифицируется с помощью следующего алгоритма:

- поочерёдно рассматриваются состояния всех автоматов;

- при рассмотрении каждого состояния определяется соответствующая ему выходная комбинация - µ;

- на основании полученных µ отыскиваются входные комбинации для всех автоматов - λ;

- найденные входные комбинации фиксируются в памяти ЭВМ;

- с помощью таблиц переходов определяются новые состояния автоматов.

В принципе, такие операции («ревизии» состояний системы) можно производить на каждом такте имитации – любая ситуация может считаться особым состоянием.

Но такое решение нецелесообразно, поскольку потребует больших затрат машинного времени. Более целесообразно считать особыми состояниями только те ситуации, которые определяют моменты выхода автоматов из пассивных состояний - состояний ожидания.

В основном, моменты выхода из пассивных состояний определяются таймерами, поскольку именно они определяют моменты системного времени, соответствующие узловым точкам в имитируемых параллельных процессах.

Состояния этих таймеров – числа T_k, которые соответствуют моментам активизации тех или иных автоматов. Если таймер запущен, то это число должно каким-то образом уменьшаться, и в тот момент, когда оно станет равным нулю, заданный тайм-аут должен считаться завершённым.

Как в реальной системе, так и в имитационной модели, могут одновременно работать k таймеров, причём каждый из них может завершить отсчёт в конкретный момент времени – T_k. Имея такие числа можно определить момент наступления ближайшего особого состояния системы, которое может быть определено с помощью проверки условия (1):

TR = min Tk	(1)
k

Далее, после активизации соответствующих процессов, значения всех запущенных таймеров уменьшается на величину T_R, позволяя тем самым определить момент наступления следующего особого состояния.

Следует отметить, что особые события могут порождаться не только таймерами, но и всеми другими автоматами. Причём эти автоматы могут находиться в пассивных состояниях, время выхода из которых – T_a, определить нельзя.

В таких случаях возможно следующее решение – если входной сигнал не меняет состояния автомата, то считать T_a = ∞. В противном же случае считать, что T_a = 0.

Для определения значения T_a можно воспользоваться таблицей переходов, действуя следующим образом:

1. выделить строку такой таблицы, которая соответствует текущему состоянию автомата;
2. убедиться в том, что текущая комбинация входных сигналов соответствует «петле», то есть возвращает автомат в то же состояние, в котором он уже находиться;
3. если это условие выполняется – то T_a : = ∞, в противном случае - T_a : = 0.

Например, в представленной на рисунке 3 таблице переходов, выделенные элементы соответствуют активным состояниям автомата, которые следует считать особыми событиями, а все остальные элементы – пассивным состояниям автомата.

Состояние	Символы входного алфавита
	λ0	λ1	λ2	λ3	λ4	λ5	λ*
St0	St0	St1	St4	St4	-	-	-
St1	St2	St1	St4	St4	-	-	-
St2	-	-	-	-	-	-	St3
St3	-	-	-	-	St3	-	-
St4	St0	-	St4	St4	-	-	-

Рисунок 3

Рассмотренный принцип имитации поведения сложных систем с дискретными событиями может являться основой для построения других аналогичных моделей. При этом программные модули, обеспечивающие имитацию квазипараллельных процессов в системе, могут оставаться неизменными – если потребуется исследовать поведение групповых каналов, основанных на использовании иных протоколов, то программное обеспечение может оставаться неизменным, и только модели поведения «передатчиков» и «приёмников» могут быть представлены в виде таблиц иного содержания.

В то же время, данный принцип может являться основой для обеспечения наглядной интерпретации поведения системы. Но это возможно лишь только в том случае, если основными мотивами расчленения модели на операторы и блоки (конечные автоматы) будут являться не только «вычислительные удобства» для программистов, но и категории, понятия и образы, которые понятны и привычны для большинства специалистов, работающих в данной области.