Программные продукты и системы, 2011, № 1

Программные продукты и системы
№ 1, 2011 г.

3

УДК 004.023

МЕТОДЫ УПРЕЖДАЮЩЕГО ПРОГНОЗИРОВАНИЯ 

СОСТОЯНИЯ ШИРОКОПОЛОСНОЙ СЕТИ СВЯЗИ

А.И. Власов, к.т.н.; В.В. Иванов; И.А. Косолапов 

(Московский государственный технический университет (МГТУ) им. Н.Э. Баумана,

ivanov@tsystems.su)

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

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

Ключевые слова: фрактальные свойства, самоподобный трафик, распределение, параметр Херста.

Для достижения требуемой точности при про
ектировании гетерогенных широкополосных сетей 
передачи данных целесообразно построить модель 
будущей сети, учитывая типы сервисов, предоставляемых на данной сети передачи данных, а 
также количество пользователей. Результаты моделирования должны иметь точность 10–20 %, 
этого достаточно для большинства целей и не требует слишком много машинного времени. Следует 
иметь в виду, что для моделирования поведения 
реальной сети необходимо учитывать ее рабочие 
параметры: задержки используемых кабелей, коммутационного и серверного оборудования.

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

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

Пусть {Xk; k=0, 1, 2, …} – стационарный слу
чайный процесс.

Учитывая стационарность и предположение о 

существовании и конечности двух первых моментов, введем обозначения: m=E[Xt] – среднее значение, 
или 
математическое 
ожидание;
2=

=E[Xt–m2] – дисперсия; R(k)=E[(Xt+k–m)(Xt–m)] –
корреляционная функция; r(k)=R(k)/r(0)=R(k)/2

– коэффициент корреляции.

Под {X(m)} усреднением по шкале времени бу
дем понимать переход к такому процессу, где




km

m
k
i

i km m 1

1
X
X
m 





.

При моделировании сетевого трафика значе
ния Xk интерпретируются как число пакетов (реже 

– как суммарный объем данных в байтах), поступивших в канал или сеть в течение k-го интервала 
времени. Исходный процесс при этом уже является усредненным. В некоторых случаях, когда есть 
необходимость избежать такого начального усреднения, рассматривается точечный процесс, или 
поток событий, то есть последовательность моментов поступления единичных пакетов в сеть [2].

Случайный процесс X(t) является самоподоб
ным с параметром Херста H, если X(t) и –HZ(t)
имеют идентичные конечномерные распределения 
вероятностей для всех a>0. Отметим, что на практике обычно встречаются не строго самоподобные, а асимптотически самоподобные процессы. 

Параметр Херста H(0,5, 1) определяет сте
пень самоподобия процесса. Чем ближе этот параметр к единице, тем более ярко проявляются 
фрактальные свойства. Напротив, равенство Н=0,5
свидетельствует об отсутствии самоподобия.

Самоподобные процессы, в том числе описы
вающие явления в сетях передачи данных, обладают рядом свойств, существенно отличающих их 
от потоков, рассматриваемых в классической теории телетрафика [1].

Долговременная зависимость. Самоподобные 

процессы обладают гиперболически затухающим 
коэффициентом корреляции вида

 







2H
2H
2H
1
r k
k
1
2k
k
1
2






или (для асимптотически самоподобных процессов) корреляционной функцией R(k)k2H–2L(t) при 
k, где L(t) – медленно меняющаяся функция 

на бесконечности (то есть



 
t

L tx
lim
1
L t


для всех 

x>0). Следовательно, корреляционная функция является несуммируемой – ряд, образованный последовательными 
значениями 
корреляционной 

функции, расходится. Это свойство характеризует 
практически все самоподобные процессы и отличает их от процессов без долговременной зависимости, у которых корреляционная функция убывает по показательному закону и суммируема [2].

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

Программные продукты и системы
№ 1, 2011 г.

4

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

Медленно убывающая дисперсия. При усред
нении процесса дисперсия выборочного среднего затухает медленнее, чем величина, обратная 
размеру выборки, по закону 2(X(m))m2H–2 при 
m, в то время как для традиционных стационарных 
случайных 
процессов 
2(X(m))=

2
1
m

 (X), то есть уменьшается обратно пропор
ционально объему выборки.

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

ошибочной [3]. С данным свойством связано и нехарактерное поведение индекса дисперсии, или 
индекса разброса, для отсчетов процесса (IDC), 
также называемого фактором Фано. IDC определяется как отношение дисперсии числа событий 
на заданном временном интервале Т к математическому ожиданию этой величины:

 
 
 

Var N T

F T

E N T











.

Здесь N(T) – число событий исследуемого 

потока, наступивших в интервале (окне) Т. Для 
самоподобных 
процессов 
логарифм 
индекса 

разброса F(T) линейно возрастает: ln[F(T)–1]=
=(2H–1)lnT+y.

Распределения с весомыми хвостами. Слу
чайная величина Z имеет распределение с весомым хвостом (РВХ), если вероятность P[Z>x]cx

при x→∞, то есть хвост распределения затухает по 
степенному закону. Пример распределения с весомым хвостом – распределение Парето. При 0<α<2
величина Z обладает бесконечной дисперсией, при 
0<α<1 среднее значение также бесконечно. Наиболее существенная особенность случайной величины, обладающей распределением с весомым 
хвостом, – чрезвычайная изменчивость. С вероятностью, которая не является пренебрежимо малой, 
в выборке может присутствовать некоторое число 
очень больших значений. Такие распределения 
существенно снижают точность статистических 
оценок; скажем, конечный объем выборки приводит к заниженной оценке среднего и дисперсии [4].

Наличие РВХ во внешних по отношению к 

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

Часто при рассмотрении самоподобных про
цессов говорят о комплексе взаимосвязанных понятий: самоподобии, масштабировании, долговременной зависимости, РВХ и степенных законах 
статистических характеристик. Этот комплекс 
свойств отличает процессы, называемые самоподобными, от классических случайных процессов, 
например пуассоновского.

Исследуемый трафик. Многочисленные из
мерения показывают наличие существенно самоподобных свойств трафика в клиент-серверных 
ИС различной архитектуры – от классических 
двухзвенных до многоуровневых с web-доступом 
и терминальных.

Фрактальный характер можно рассмотреть на 

примере среза трафика, полученного при работе 
удаленного подразделения из нескольких рабочих 
мест с сервером СУБД. Параметры среза трафика 
следующие: длительность – 21 936 с; длительность – 6,093 ч; число пакетов – 688108; интенсивность λ – 31,368 с-1; средний объем пакета –
193,2 байта; рабочих мест – 25; параметр Херста 
Н (IDC) – 0,729; параметр Херста Н (автокорреляция) – 0,724 [5].

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

Сервером СУБД является сервер Oracle8i; 

приложение (биллинговая система оператора связи) реализовано по классической двухзвенной 
клиент-серверной схеме, то есть сетевое взаимодействие происходит на базе TNS/SQL*net поверх 
TCP. Поскольку пропускная способность рассматриваемого канала (100 Мбит/с FastEthernet) существенно превышает суммарный трафик, а сторонняя нагрузка в день исследований пренебрежимо 
мала, срез можно считать свободным трафиком 
(в терминологии, введенной И. Норросом), то есть
трафиком, полностью определяемым своим источником и не испытывающим влияния сети.

Корреляционная 
структура.
Графическое 

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

На рисунке 1 приведен график коэффициента 

корреляции для процесса, соответствующего исследуемому срезу трафика. Если процесс самоподобен, угловой коэффициент β=2-2H. При полученном значении β=0,55004 параметр Херста оказывается равным 0,724.

На рисунке 2а для сравнения приведена 

кривая, соответствующая значениям коэффици

Программные продукты и системы
№ 1, 2011 г.

5

ента корреляции строго самоподобного процессса [5].

Очевидно, что выборочные оценки достаточно 

точно соответствуют идеальной кривой, особенно 
при увеличении аргумента k. Существенную роль 
долговременной зависимости в исходном процессе 
можно выявить и на основе анализа так называемого перемешанного процесса, который получается из исходного путем перестановки интервалов 
между поступлениями пакетов в случайном порядке [3]. В таком процессе (рис. 2б) корреляция 
убывает существенно быстрее, стремясь к нулю.

Параметр Херста. Традиционно самоподо
бие в стохастическом процессе выявляется путем 
определения параметра Херста Н. Тот факт, что 
0,5<H<1, то есть значение параметра Херста отлично от 0,5, считается достаточным основанием 
для признания процесса самоподобным (по крайней мере, асимптотически) [6].

Следует отметить, что значение Н, близкое к 

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

В рассматриваемом случае значения парамет
ра Херста, определенные из вида кривой коэффициента корреляции и путем анализа IDC (0,724 и 
0,729 соответственно), практически совпадают. 
При этом значение говорит о существенно выраженных фрактальных свойствах.

На рисунке 3 приведены значения ln[F(T)-1]

в зависимости от lnT. Для процесса с перемешанными случайным образом интервалами значение 
получается существенно меньше: H=0,563. Этот 
факт совместно с видом корреляционной структуры исходного и перемешанного процессов позволяет утверждать, что для рассматриваемого 
трафика самоподобие заключено не столько в тяжелом распределении интервалов, сколько в долгосрочной зависимости – группировке коротких 
интервалов в пачки [3].

Применение свойств самоподобия сетевого 

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

Алгоритм статистического мультиплексирова
ния потоков широко используется в телекоммуникациях, поскольку позволяет экономно использовать пропускную способность магистральных каналов. Рассмотрим простейший пример передачи 
информации от многих источников по одному магистральному каналу. В принципе, за каждым из 
источников можно закрепить определенную часть 
ресурсов магистрального канала (скажем, разделив их по частоте). В этом случае каждый источник может использовать только ту часть ресурсов, 
которая ему отведена. Другой способ передачи, 
называемый статистическим мультиплексированием, состоит в том, что потоки отдельных источников складываются (агрегируются) в магистральном канале с экономией пропускной способности dC [4].

Рассмотрим второй вариант более подробно. 

Допустим, имеются n отдельных (парциальных) 
источников. Пусть процессы 1(M[1], D[1]), …, 

Рис. 1. Значения коэффициента корреляции 

(логарифмический масштаб)

Рис. 2. График коэффициента корреляции 

для трафика: 

а) в сравнении с кривой коэффициента корреляции 

строго самоподобного процесса (1) при β=0,55; 

б) в сравнении с кривой коэффициента корреляции 
с перемешанными случайным образом интервалами

Рис. 3. Определение параметра Херста Н 

по значениям IDC

Программные продукты и системы
№ 1, 2011 г.

6

n(M[n], D[n]) имеют одинаковые математические ожидания M[i]= и дисперсии D[i]=2

(рис. 4). Тогда при условии независимости и одинаковом распределении 1, 2, …, n коэффициент 
вариации результирующего процесса  в магистральном канале будет равен




.

1
2
n

1
2
n

2

D
D
...

cov
M
M
...

n D

n M
т












   
 













   
 


























Как видим, коэффициент вариации представ
ляет собой отношения среднеквадратичного отклонения процесса к его математическому ожиданию. В данном случае коэффициент вариации отражает степень сглаживания результирующего 
процесса  при увеличении количества мультиплексируемых парциальных каналов. Эффект зрительного сглаживания процесса  при росте n
достигается благодаря более быстрому росту 
среднего процесса  по отношению к его среднеквадратическому отклонению [2].

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

Типичный вид агрегированного сетевого тра
фика показан на рисунке 5.

Каждая точка на данном графике представляет 

собой количество байтов, переданных в магистральном канале за 1 секунду. Длительность реализации составляет 3000 точек, или 50 минут. Коэф
фициент Херста соответствует примерно 0,8. Как 
видно из рисунка, процесс имеет высокую изменчивость (поскольку подчиняется распределению с
тяжелым хвостом) и его вряд ли можно назвать 
сглаженным. Чтобы такой трафик передавать без 
потерь, пропускная способность канала должна 
соответствовать уровню пиковых выбросов, то
есть в данном случае быть не менее 1,4105 бит/с
[2]. Поскольку средний уровень трафика все-таки 
достаточно низкий, можно заметить, что пропускная способность будет расходоваться неэффективно. Другими словами, коэффициент использования 
такого канала будет низким.

С развитием направления самоподобия все 

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

На основании изложенного можно сделать 

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

Литература

1. Шелухин О.И., Тенякшев А.М., Осин А.В. Фракталь
ные процессы в телекоммуникациях. Монография; [под ред. 
О.И. Шелухина]. М.: Радиотехника, 2003. 480 с.

2. Miloucheva I., Muller E., Anzaloni A. A practical approach 

to a forecast Quality of Service parameters considering outliers. 
2003.

3. Foag J., Wild T.
Traffic prediction algorithm for 

speculative network processors // 17th Intl. Symposium for High 
Performance Computing Systems and Applications HPCS 2003. Sherbrooke, May 2003.

4. Олифер В.Г., Олифер Н.А. Компьютерные сети. Прин
ципы, технологии, протоколы. СПб: Питер, 1999.

5. Управление 
неоднородными 
сетями. 
URL: 

http://www.citforum.ru/nets/tpns/glava_16.shtml (дата обращения: 
12.12.2010).

6. Trajcovic L., Neudhardt A., Internet traffic prediction //

Centre for Systems Science, Simon Fraser University, Vol. 12, Is. 1, 
Mar. 2000.

Рис. 5. Усредненная по блокам длины m=1 с. 

Реализация lbl-pkt-5

Рис. 4. Схема статистического мультиплексирования 
1(M[1], D[1]), …, n(M[n], D[n]) с получением 

в магистральном канале процесса 

Программные продукты и системы
№ 1, 2011 г.

7

УДК 658.51

ПРОГРАММА ТРАНСФОРМАЦИИ ТОПОЛОГИИ 

СУБМИКРОННЫХ СВЕРХБОЛЬШИХ ИНТЕГРАЛЬНЫХ СХЕМ 

ДЛЯ ТЕХНОЛОГИИ ДВОЙНОГО ФОТОШАБЛОНА

(Работа выполнена при частичной финансовой поддержке ФЦП «Научные и научно-педагогические кадры 

инновационной России» на 2009–2013 гг., ГК № П2292, и гранта Президента РФ по государственной поддержке 

ведущих научных школ, грант НШ-3484.2010.9)

Л.А. Зинченко, д.т.н.; А.Е. Аверьянихин 

(МГТУ им. Н.Э. Баумана, lyudmillaa@mail.ru)

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

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

TPLConverter.

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

КМОП-технологии. 

Известно, что при проектировании и произ
водстве интегральных схем основную роль играют 
процессы литографии. При достижении физических пределов процесса фотолитографии, связанных с негативным влиянием эффекта взаимной 
дифракции, затраты на совершенствование производства интегральных схем экспоненциально возрастают. Поэтому их производители всеми способами пытаются расширить физические пределы 
разрешающей способности проекционной оптической литографии с помощью таких инноваций, 
как, например, фазосдвигающие фотошаблоны и 
внеосевое освещение. Среди множества различных подходов в документах ITRS [1] выделяются 
два основных направления дальнейшего развития 
литографии: литография жестким ультрафиолетом 
(EUV) и методики двойного экспонирования 
(double exposure), к которым и относится экспонирование с двойным фотошаблоном.

Технология двойного фотошаблона является 

одним из возможных вариантов развития электроники по пути дальнейшей миниатюризации. Основная идея этого подхода заключается в последовательном применении двух шаблонов во время 
прожига фоторезиста для получения рисунка с 
размерами элементов, которых невозможно достичь с помощью обычных методов оптической литографии. Однако процедура декомпозиции топологии сверхбольших интегральных схем (СБИС)
на две подчасти не является тривиальной и требует оценки всех возможных альтернативных реше
ний с учетом технологических ограничений. Выполнить это вручную весьма сложно, поэтому переход к проектированию по технологии двойного 
фотошаблона требует широкого использования 
САПР. На рынке программных продуктов только 
начинает появляться ПО для решения задачи автоматизации проектирования по технологии двойного фотошаблона. В [1] отмечается, что задача 
разработки такого ПО является одной из важнейших проблем дальнейшего развития литографии.

Общие сведения о программе 

TPLConverter

В работе [2] предложены алгоритмы преодо
ления принципиальных ограничений оптической 
фотолитографии для разрешения противоречия 
между негативным влиянием эффекта взаимной 
дифракции и необходимостью уменьшения проектных норм технологии. В основе выбранного 
математического аппарата для описания процесса 
подготовки топологии субмикронных СБИС для 
последующего воспроизводства по технологии 
двойного фотошаблона лежит понятие графа ограничений [3]. Были проанализированы известные 
методы его построения, и на основе сравнительного анализа выбран как наиболее эффективный хорошо известный метод сканирующей линии [3]. 

Для учета особенностей технологии двойного 

фотошаблона в [2] предложено использовать граф 
противоречий, хранящий информацию об имеющихся противоречиях в топологии СБИС, вызванных негативным влиянием эффекта взаимной 
дифракции. В той же работе описан алгоритм 
трансформации топологии СБИС для технологии 
двойного фотошаблона.

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

 ввод заданной топологии СБИС в формате 

GDSII;

Программные продукты и системы
№ 1, 2011 г.

8

 задание параметров технологии двойного 

фотошаблона;

 оценка заданной топологии субмикронной 

СБИС на возможность воспроизводства по технологии двойного фотошаблона;

 модификация топологии СБИС в случае 

удовлетворения ограничений технологии двойного фотошаблона при последующем ее воспроизводстве по данной технологии;

 вывод полученных результатов в форма
те GDSII.

С 
целью
обеспечения 
применения 
ПО

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

Технологическое ограничение представляет 

собой противоречие, выражающееся в задании 
определенных ограничений на взаимное расположение геометрических объектов. Рядом компаний 
были предложены различные форматы формализованного описания технологических ограничений. Они апробированы в промышленном применении и доказали свою эффективность. Для возможности интеграции с САПР ведущих мировых 
производителей выбран формат, используемый в 
САПР Calibre фирмы Mentor Graphics [4]. 

В данном формате файл ограничений пред
ставляет собой последовательность записей, которые хранят технологические ограничения в формализованном виде. Каждая строка имеет вид
conflict=RET nmdpc ca FILE mypitches MAP 
conflict, где RET задает название утилиты обработчика; FILE – имя файла; MAP является обязательным ключевым словом, задающим один из 
перечисляемых системных типов данных. 

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

Необходимо отметить, что под параметрами 

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

Оценка и трансформация топологии СБИС для 

технологии двойного фотошаблона выполняются 
на основе подходов, описанных в [2].

Выбор формата ввода и вывода информации о 

топологии СБИС GDSII обусловлен тем, что фактически он является промышленным стандартом 
описания топологии СБИС и используется для 
хранения информации об их послойной структуре. 

Файл этого стандарта двоичный, с описанием простейших геометрических форм, текста, меток и 
другой информации. Однако указанный формат 
сложен для автоматизации трансформации топологии СБИС, в связи с чем в программе 
TPLConverter
использован внутренний формат 

описания топологии СБИС.

При создании ПО также были учтены совре
менные тенденции развития САПР СБИС, отражающиеся
в разработке все большего числа 

кроссплатформенных программных продуктов. 
Программа TPLConverter является кроссплатформенной и может использоваться в ОС Windows и 
*Unix. Это позволяет обеспечить совместимость 
разработанного ПО
с существующими САПР 

СБИС и возможность использования ПО TPLConverter в интегрированных маршрутах проектирования СБИС.

Особенности реализации программы

TPLConverter

Программа TPLConverter включает 4 основ
ные подсистемы (рис. 1).

Управляющая подсистема предназначена для 

управления ходом трансформации топологии 
СБИС, а модуль ввода информации – для задания 
информации пользователем. В этом модуле проверяется соответствие входного файла поддерживаемому формату GDSII. Там же производится 
синтаксический разбор исходного файла топологии СБИС в формате GDSII, что позволяет распределять отдельные геометрические объекты топологии СБИС по соответствующим структурам 
данных. В этом же модуле есть функции обработки заданных входных параметров технологии 
двойного фотошаблона.

Модуль обработки информации включает 

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

Рис. 1. Основные подсистемы

программного обеспечения TPLConverter

Ввод исходных 

данных

Обработка 
информации

Вывод 

результатов

Управляющая подсистема

Программные продукты и системы
№ 1, 2011 г.

9

Модуль вывода информации отвечает за вы
вод результатов: модифицированной топологии 
СБИС в формате GDSII для технологии двойного 
фотошаблона, а также вспомогательной информации.

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

При детализации описания жизненного цикла 

использована методология RUP (Rational Unified 
Process) [5]. После структурно-функциональной 
декомпозиции получены шаблоны классов ПО, 
выполнено их наполнение кодом, реализующим 
указанные выше алгоритмы.

Разработка ПО велась под управлением сис
темы контроля версий, что позволило обеспечить 
одновременную работу группы программистов.

В качестве лингвистического обеспечения вы
бран язык С++. Это объясняется простотой обработки сложных структур данных, хранящих информацию о топологии СБИС. 

При разработке были использованы библиоте
ки GDSIILib и GraphViz.

Библиотека GDSIILib
содержит основные 

функции для доступа к файлу топологии формата 
GDSII. Библиотека GraphViz является разработанным специалистами лаборатории AT&T пакетом 
утилит по автоматической визуализации графов, 
заданных в виде описания на языке dot. Пакет 
распространяется с открытыми исходными фай
лами по лицензии CPL (Common Public License) и 
работает на многих операционных системах, 
включая GNU/Linux, Mac OS, Unix-подобные, 
Microsoft Windows. Эта библиотека широко используется при ПО для визуализации структурированных данных.

Диаграмма компонентов ПО TPLConverter в 

нотациях языка UML показана на рисунке 2, список компонентов с кратким описанием приведен в 
таблице.

Компоненты программы TPLConverter

Компонент
Описание

objectstorage.cpp
Компонент хранения объектов

persistentobject.cpp Базовый компонент описания 

объекта

GDSIIFile.cpp
Компонент обработки файлов 
GDSII

main.cpp
Основной файл программы

elements.cpp
Описание объектов и структур 
данных

splitter.cpp
Механизм разделения слоя

types.cpp
Компонент хранения различных 
типов данных формата

Особенности применения 
программы TPLConverter

Программа TPLConverter
может использо
ваться на персональном компьютере типа IBM PC. 
Для ее работы необходимы процессор Pentium 4
3.0 ГГц, оперативная память 2 Гб, жесткий диск 
с 1 Гб свободного пространства, DVD-RW-дисковод.

Для работы в диалоговом режиме требуются 

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

На ЭВМ должно быть установлено следующее 

ПО: ОС Linux Debian или ее аналоги либо ОС не 

Рис. 2. Диаграмма компонентов программы TPLConverter

Программные продукты и системы
№ 1, 2011 г.

10

ниже Windows XP. Необходимо наличие компилятора gcc, библиотек GDSIILib и GraphViz.

Запуск программы может выполняться из ко
мандной строки Unix-shell или из командной строки эмулятора терминала Windows.

Для апробации разработанного ПО была вы
полнена трансформация топологии 8-битного дешифратора. На рисунке 3а приведена исходная 
топология 8-битного дешифратора (слой поликремния). Однако выход годных интегральных 
схем был очень низок из-за негативного влияния 
эффекта взаимной дифракции. 

С использованием разработанной программы 

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

В заключение отметим, что разработанное ПО

TPLConverter может найти широкое применение 
при
проектировании топологии субмикронных 

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

Разработанное ПО не требует значительных 

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

Программа TPLConverter найдет применение

как в виде отдельного полнофункционального 
приложения, так и в составе интегрированных 
маршрутов проектирования СБИС. 

Дальнейшее развитие системы идет по пути 

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

Литература

1. URL: http://www.itrs.net (дата обращения: 10.11.2010).
2. Зинченко Л.А., Резчикова Е.В., Аверьянихин А.Е. Ал
горитмы трансформации топологии субмикронных СБИС // 
Вест. МГТУ им. Н.Э. Баумана. № 1. 2011.

3. Shervani N. Algorithms for VLSI physical design 

automation // Kluwer Academic Publishes, 1995. 538 p.

4. URL: 
http://www.mentor.com/
(дата 
обращения: 

10.11.2010).

5. URL: http://www-01.ibm.com/software/awdtools/rup/ (да
та обращения: 10.11.2010).

УДК 62-529

СИСТЕМА ТЕХНИЧЕСКОГО ЗРЕНИЯ 

В ЗАДАЧАХ НАВИГАЦИИ МОБИЛЬНЫХ ОБЪЕКТОВ

С.В. Миронов; А.В. Юдин (МГТУ им. Н.Э. Баумана, skycluster@gmail.com)

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

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

Ключевые слова: техническое зрение, робот, навигация, автоматизация, программное обеспечение.

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

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

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

а)

б)

Рис. 3. Пример работы программы TPLConverter 

(слой поликремния)

Программные продукты и системы
№ 1, 2011 г.

11

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

Применение технического зрения в навигации 

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

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

Архитектура системы управления 

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

Рассмотрим техническое зрение на примере

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

Внешние датчики и исполнители, используе
мые в робототехническом комплексе (РК), не могут быть подсоединены к компьютеру напрямую 

через стандартные низкоуровневые интерфейсы, 
такие как PCI или ISA. Для решения этой проблемы используются платы расширения, представляющие собой один или несколько вспомогательных контроллеров. Вспомогательные контроллеры 
в отличие от главного компьютера работают на 
более низких тактовых частотах, а связь с ним 
осуществляется по интерфейсу общего назначения 
(например, CAN, USB, I2C).

В данном случае система технического зрения 

РК – совокупность программных модулей, принимающих, передающих и обрабатывающих информацию, полученную с помощью видеокамер 
(рис. 2).

Физические устройства и кабели, которые 

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

Подсистема анализа визуальных данных.

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

Модуль «Драйвер видеокамеры» позволяет

выделять очередной кадр из поступающего видеопотока. Модуль представляет собой интерфейс к 
компоненту операционной системы. Например, 
для Linux таким компонентом может быть код, использующий библиотеки v4l/v4l2; для Windows могут использоваться средства DirectX (DirectDraw).

Модуль «Распознаватель» выделяет и клас
сифицирует изображения. Получая их в виде на
Рис. 2. Основные компоненты системы 

технического зрения

Примечание: Д1, Д2 – датчики, К1 – компьютер, МК1 –
микроконтроллер.

Рис. 1. Общие принципы взаимодействия подсистем

Программные продукты и системы
№ 1, 2011 г.

12

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

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

Подсистема принятия решений.
Данная 

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

 построение и поддержание непротиворечи
вого представления об окружающем мире;

 разработка стратегии решения поставлен
ных задач;

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

Следует выделить две наиболее общие части 

этой подсистемы – модули «Построитель карты» и 
«Искусственный интеллект».

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

Модуль «Искусственный интеллект» отвеча
ет за планирование действий РК. Результаты планирования выражаются в виде команд различным 
исполнительным механизмам.

Взаимодействие системы технического зре
ния с исполнительными центрами. Поскольку 
решаемая задача навигации ставит жесткие ограничения на время обработки сигналов всех датчи
ков, необходимо обеспечить предобработку их 
данных без передачи информации главному компьютеру. Для решения этой задачи применяется 
метод делегирования полномочий системы принятия решений, который заключается в том, что подсистемы принятия решений присутствуют в виде 
связанных между собой агентов как на компьютере, так и на контроллере (рис. 3). Этот подход позволяет оперативно реагировать на нештатные ситуации, фиксируемые датчиками контроллера 
(Д2). При этом в системе по-прежнему возможно 
наличие контроллеров, не имеющих собственного
агента принятия решений (например МК1). Для 
решения проблемы синхронизации агентов им назначаются роли (клиент/сервер). Клиентская часть 
системы берет на себя функции реагирования на 
нештатные ситуации, в то время как серверная 
часть – долговременное планирование и анализ 
данных датчиков на непротиворечивость.

Используются следующие типы протоколов 

передачи данных.

1. Протокол программного взаимодействия с 

модулем построения карты, который стандартизирует интерфейсы системных вызовов, выполняемых из подпрограмм драйверов датчиков в подпрограмму построения карты. Язык описания интерфейсов – C (Метка 1).

2. Протокол взаимодействия вынесенных дат
чиков с агентом принятия решений (Метка 2).

3. Протокол синхронизации агентов принятия 

решения (Метка 3).

Таким образом, система представлена набором 

модулей верхнего и нижнего уровней. Модули 
нижнего уровня связаны шиной нижнего уровня. 
Центр нижнего уровня отвечает за координацию 

Примечание: Д1, Д2, Д3 – датчики, К1 – компьютер, МК1, 
МК2 – микроконтроллеры.

Рис. 3. Подход к построению взаимодействия 
исполнительной подсистемы и подсистемы 

принятия решений с делегированием полномочий