Новые подходы к решению проблем в системах связи и компьютерных сетях: динамический хаос

Архив

"КТ" уже писала о динамическом хаосе и синергетике. Мы будем исходить из того, что эти научные направления знакомы читателям. Цель статьи - дать обзор некоторых исследований по применению динамического хаоса и родственных областей знания в системах связи и компьютерных сетях, включая Интернет.

«Компьютерра» уже писала о динамическом хаосе и синергетике (см., например, тему номера «Хаос», «КТ» #275, 1998). Мы будем исходить из того, что эти научные направления знакомы читателям ¹. Цель статьи - дать обзор некоторых исследований по применению динамического хаоса и родственных областей знания в системах связи и компьютерных сетях, включая Интернет. Не претендуя на исчерпывающее описание предмета, сосредоточимся на четырех направлениях, в которых за последнее время наметился серьезный прогресс.

Коммуникационные и компьютерные сети.
Анализ архитектуры и режимов функционирования

Распределенные системы, в том числе компьютерные сети, WWW, сотовые и ad-hoc-системы связи и т. п., обычно обладают сложной топологией. Недавние исследования показали, что они представляют собой результат действия самоорганизующихся процессов, управляемых общими, довольно простыми законами. Их свойства резко отличаются от свойств случайных сетей.

Подобные системы, состоящие из большого числа взаимодействующих элементов, могут демонстрировать интересные и неожиданные временные и пространственные эффекты. Один из них - возникновение шума, имеющего спектральную плотность мощности вида 1/f ². Это часто связано с появлением, без какой-либо настройки параметров, масштабно-инвариантных пространственных структур. В этом случае говорят, что система эволюционировала к состоянию самоорганизованной критичности.

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

Для изучения подобных явлений в сложных сетях необходим адекватный теоретический аппарат. Работы по его созданию и применению интенсивно ведутся. Недавно в журнале «Physica A» для координации исследований в этой области открыт специальный раздел «Сложные системы и сети».

Одним из интересных подходов к анализу таких объектов являются модели малого мира (small world models), смысл которых можно объяснить на следующем примере. Население земного шара 12 декабря 1999 года достигло 6 миллиардов человек. Тем не менее, несмотря на огромное число людей на планете, структура социальных сетей такова, что все мы очень тесно связаны друг с другом [2-4]. Оказывается, два случайно выбранных человека, как правило, связаны весьма короткой цепочкой промежуточных знакомств. Типичная длина такой цепочки около шести звеньев. На жаргоне это явление называется эффектом малого мира.

Первой попыткой объяснения эффекта малого мира было использование модели случайного графа. Предположим, что имеется сообщество, состоящее из N членов. В среднем каждый из них имеет z знакомств (рис. 1а). Это означает, что во всем сообществе имеется Nz/2 контактов между людьми. Модель предполагает, что эти связи устанавливаются между случайно выбранными парами. Оказалось, что такая модель действительно демонстрирует эффект малого мира. Средняя длина D цепочки, соединяющей двух случайных людей, согласно этой модели равна D = lg N/lg z. Поскольку lg N медленно увеличивается с ростом N, D также мало даже для очень больших систем.

В качестве примера изучались свойства сети гиперссылок между документами в WWW. К моменту проведения исследований в Сети имелось N ~ 8•10⁸ документов. Средняя же длина цепочки («расстояние» между документами) составляла около 19.

Однако модель случайных графов не определяет всех свойств реальных сетей. В частности, она не предсказывает кластеризацию в сети. В случайном графе вероятность того, что две персоны будут знакомы между собой, не зависит от того, какие персоны выбраны. С другой стороны, кластеры (группы связанных между собой элементов) существуют во многих реальных сетях. Можно ввести коэффициент кластеризации C, представляющий собой среднюю долю таких пар в общем числе пар соседей узла, которые также являются соседями друг друга. В полностью связанной сети, в которой каждый знает каждого, C = 1. В случайном графе C ~ 1/N, что является очень малой величиной при очень большом размере сети. Было выяснено, что в реальных сетях значение C хотя и много меньше единицы, однако существенно превосходит 1/N.

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

Оказывается, модель, узлы которой имеют одновременно некоторое количество локальных и случайных «дальних» связей (рис. 1в), демонстрирует и эффект малого мира, и кластеризацию.

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

О применении моделей этого типа для анализа структуры и функционирования сетей связи и компьютерных сетей см. [5-7].

Хаотическое кодирование информации

Рис. 2. Хаотическое кодирование может быть организовано на основе естественного языка: на рисунке слева приведена фраза, использующаяся для построения функции хаотического кодирования; сама функция F (на рисунке справа) реализована с помощью кусочно-линейного одномерного отображения x®F(x), на котором эта фраза «записана».

Процесс, обладающий свойствами динамического хаоса, может использоваться как носитель информации, как средство ее преобразования к новому виду и, наконец, как комбинация того и другого (рис. 2). В случае использования хаоса для преобразования сигнала можно говорить о дополнительном - хаотическом - кодере в передатчике (рис. 3).

Приведем ряд приложений хаотического кодирования, которые сейчас активно исследуются.

Структуризация информационного пространства

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

Новые принципы организации многопользовательского доступа

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

Гибкий контроль качества информационных потоков

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

Рис. 4. Пример изображения с разной степенью деградации в результате хаотического кодирования: (а) исходная фотография; (б) признаки исходного изображения отсутствуют; (в) фотография искажена до неприемлемого для потребителя уровня, но собака на ней ясно видна.

Приватность информационного обмена

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

К настоящему времени предложен и апробирован ряд конкретных алгоритмов и схем хаотического кодирования (см., например, [8-10]), обеспечивающих различную степень конфиденциальности. С их помощью достигаются: а) более высокая эффективность защиты мультимедийной информации, нежели у распространенного алгоритма DES; б) большие скорости кодирования; в) устойчивость по отношению к шуму. Среди этих методов есть потоковые, пригодные для использования в сетях на физическом уровне.

Волоконно-оптическая связь с применением динамического хаоса

В 1998 году Рой (Roy) и ван Виггерен (Van Wiggeren) из Технологического института штата Джорджия продемонстрировали использование хаотических колебаний для кодирования информации при передаче от лазера-передатчика к лазеру-приемнику через волоконно-оптический кабель.

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

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

Ранее подобная схема исследовалась при экспериментах по маскировке информации в радиосистемах [1, 11], но в этой работе хаос был впервые использован для передачи сообщений в полностью оптической системе. Статья в Science [12] описывала передачу сигналов со скоростью 10 Мбит/с. Позже была реализована передача потока битов со скоростями до 250 Мбит/с.

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

СВЧ-системы связи с применением хаоса

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

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

Рассмотрим три наиболее продвинутые с экспериментальной точки зрения схемы. Схема с дифференциальным переключением хаотических режимов (Differential Chaos Shift Keying, DCSK) функционирует следующим образом .

Каждый передаваемый бит представляется двумя фрагментами хаотической последовательности. Первый фрагмент используется как реферативный, второй же несет информацию. Значение «1» кодируется передатчиком путем повторения одной и той же последовательности, а при передаче «0» за реферативным фрагментом следует его инвертированная копия. В приемнике хаотический сигнал задерживается на время T/2, где T - длина бита, и определяется корреляция между исходным и задержанным сигналами. Битам со значениями «1» и «0» отвечают положительная и отрицательная корреляции со значениями «1» и «-1», соответственно. Поэтому решение о значении поступившего бита может быть принято пороговым устройством. Отметим, что сформированный модулятором сигнал в соответствии с классической схемой передачи информации модулирует высокочастотный синусоидальный сигнал и лишь затем излучается [13].

Модифицированная схема DCSK (FM-DCSK) положена в основу лабораторного макета цифровой системы связи со скоростью передачи данных 512 кбит/с, работающего в диапазоне 2,4 ГГц. Макет разработан группой исследователей из Хельсинкского технологического университета и представлен в августе этого года на конференции ECCTD 2001 [14].

Другая идея применения хаоса в системах радиосвязи имеет отправной точкой сверхширокополосное импульсное радио (UWB Pulse Radio). Начиная с конца 1970-х годов развивались идеи использования коротких импульсов для радиосвязи и радиолокации [15]. В отличие от традиционных схем связи, где в качестве носителя информации используются протяженные во времени узкополосные синусоидальные носители, в сверхширокополосных импульсных системах носителями информации служат очень короткие импульсы с очень широким спектром. Интерес к импульсным системам никогда не угасал, однако о широком коммерческом применении речь тогда не шла. Но во второй половине 1990-х годов были разработаны прототипы таких систем связи. Их достоинствами являются: сверхширокополосность, обеспечивающая устойчивые характеристики передачи даже в неблагоприятных условиях распространения сигнала; малая спектральная плотность излучения; высокие скорости передачи информации. Кроме того, подобные системы могут (потенциально) работать в тех же диапазонах, что и традиционные системы связи, не мешая последним. Таким образом обеспечивается более эффективное использование эфира.

Структуры передатчика и приемника в UWB Pulse Radio радикально отличаются от традиционных. В них отсутствует разделение системы на низкочастотную и высокочастотную части. Ультракороткие импульсы, являющиеся носителями информации, имеют спектр мощности, простирающийся от единиц мегагерц до 2-3 ГГц. Непосредственно на этот сигнал накладывается передаваемая информация.

Технология обладает значительным потенциалом по скорости передачи данных и числу пользователей (продемонстрирована скорость передачи информации 40-50 Мбит/с). Однако ее особенность заключается в том, что если импульсы будут следовать почти периодически, то в среднем спектре мощности сигнала возникнут нежелательные спектральные компоненты. Чтобы этого не происходило, импульсы должны следовать, например, по случайному закону. Реализация этой идеи возможна с помощью хаотического кодирования расстояний между импульсами [16].

Рис. 6. Так выглядят сигналы на экране осциллографа при сверхширокополосной прямохаотической передаче информации. Голубым цветом показан исходный информационный сигнал. Желтым - поток хаотических радиоимпульсов на входе приемника. Скорость передачи 100 Мбит/с.

Еще одна разновидность систем связи с использованием хаоса - прямохаотические схемы [18] - не только обладает многими преимуществами сверхширокополосных импульсных систем, но также рядом дополнительных достоинств. В прямохаотической схеме связи (ПХСС) информационный сигнал вводят в хаотический сигнал, который генерируется непосредственно в радио- или СВЧ-диапазоне (рис. 6). Это осуществляется либо путем модуляции параметров передатчика, либо путем модуляции хаотического сигнала информационным. Извлечение информационного сигнала из хаотического также осуществляют в области высоких или сверхвысоких частот. ПХСС могут работать как в широкой, так и в сверхширокой полосе частот. По оценкам, они способны обеспечить скорости передачи информации от десятков мегабит до 1 Гбит/с. Первые эксперименты с широкополосными ПХСС были проведены весной 2000 года, когда в диапазоне 1 ГГц и полосе частот 100 МГц была экспериментально продемонстрирована скорость передачи данных до 70 Мбит/с [18-19]. В сверхширокополосной ПХСС с полосой частот 2.5 ГГц в сентябре 2001 года достигнуты скорости передачи до 200 Мбит/с.

Новый взгляд на структуру коммуникационных сигналов

Работы по использованию хаоса для передачи информации важны не только потому, что ведут к многообещающим практическим результатам. Развитие этой технологии заставляет по-новому взглянуть на традиционное представление об информативных и неинформативных сигналах. В науке мы привыкли иметь дело с аналоговой или цифровой информацией в «легко извлекаемой» форме. Но информация может быть скрыта и в сигналах, выглядящих шумоподобно. Как мы видели, она может быть весьма эффективно передана и принята, например, с помощью хаотических сигналов, а не гармонических колебаний, которые всегда использовались в радио и телевидении. Это знание заставляет ученых по-новому посмотреть на связь информации с динамическими системами [20] и может однажды привести к более глубокому пониманию того, как организована коммуникация, например, биологических систем - в частности, нейронов.

[i42326]

Литература

1. «Компьютерра» #47[275]. 1998.

2. M. Kochen. The Small World. Ablex (Norwood). 1989.

3. D.J. Watts. Small Worlds. Princeton University Press (Princeton). 1999.

4. V.T.J. Newman. Models of Small Worlds. A Review. ArXiv: cond-mat/0001118 v2. 2000.

5. R. Albert, H. Jeong, A.-L. Barabasi. Diameter of the World-Wide Web. Nature. 1999. V. 401. P. 130.

6. J.M. Kleinberg. Navigation in Small World. Nature, 1999.

7. R. Albert, H. Jeong, A.-L. Barabasi. Error and Attack Tolerance of Complex Networks. Nature. 2000. V. 406. P. 378.

8. Успехи современной радиоэлектроники. Специальный выпуск. 2000. № 11.

9. J. Fridrich. Symmetric Ciphers Based on Two Dimensional Chaotic Maps. Int. J. Bifurcation And Chaos. 1998. V. 8. P. 1259.

10. Z. Gao. Method and Apparatus for Encryption, Decryption and Authentication Using Dynamical Systems. US Patent № 5,365,589. 1994.

11. А.С. Дмитриев, Л.В. Кузьмин, А.И.Панас, С.О.Старков. Эксперименты по передаче информации с использованием хаоса через радиоканал. Радиотехника и электроника. 1998. V. 43. № 9. С. 1115.

12. G.D. VanWiggeren, R. Roy. Communication with Chaotic Lasers. Science. 1998. V. 279. P. 1198.

13. M.P.Kennedy, G. Kolumban, G. Kis. Chaotic Modulation for Robust Digital Communications over Multipass Channels. Jnt. J. Bifurcation and Chaos. 2000. V. 10. N 4. P.695.

14. K. Krol, L. Azzinnari et al. An Experimental FM-DCSK Chaos Radio System. Proceedings of ECCTD’01. 2001. V. 3. P. 17.

15. M.Z. Win, R. A. Scholtz. Impulse Radio: How it works. IEEE Communications Letters. 1998. V. 2. N 1. P. 10.

16. N. Rulkov, M. Sushchik et al. Digital Communication Using Chaotic Pulse Generators. ArXiv: chao-dyn/9908015/ 1999.

17. Носитель информации - хаос. Новые известия. 8 апреля 2000.

18. А.С. Дмитриев, Б.Е. Кяргинский, Н.А. Максимов, А.И. Панас, С.О. Старков. Прямохаотическая передача информации в СВЧ-диапазоне. 2000. Препринт ИРЭ РАН № 1 (635). Радиотехника и электроника 2001. Т. 46. № 2. С. 224.

19. G. Deco, B. Schurmann. Information Dynamics. Springer. 2000.

---

1 (обратно к тексту) - Динамическим хаосом обычно называют сложное, «квазислучайное» поведение детерминированных систем. Синергетика изучает возникновение устойчивых упорядоченных структур (режимов) в системах с таким поведением. - Л.Л.-М.
2 (обратно к тексту) - Характерного для хаотических процессов. - Л.Л.-М.