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

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

Рассмотрим систему, которая представляет собой канал коллективного доступа - подсистему 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 может быть больше нуля только тогда, когда система способна адаптироваться к изменениям состояний её элементов.

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