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

На правах рукописи

ЧИТАЕВ Илья Владимирович

МЕТОДЫ И АЛГОРИТМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ ПРОВОДНЫХ ТЕЛЕКОММУНИКАЦИОННЫХ СЕТЕЙ МИНИМАЛЬНОЙ СТОИМОСТИ

Специальность 05.13.12 - Системы автоматизации проектирования (технические системы)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Рязань 2006

Работа выполнена на кафедре систем автоматизированного проектирования вычислительных средств (САПР ВС) Рязанского государственного радиотехнического университета.

Научный руководитель: заслуженный деятель науки и техники РФ, доктор технических наук, профессор Вячеслав Петрович Корячко.

Официальные оппоненты:

доктор технических наук, профессор Цветков Игорь Анатольевич кандидат физико-математических наук, доцент Мамонов Сергей Станиславович

Ведущая организация: ГНИИ ИТТ «Информика», г. Москва.

Защита состоится «21» июня 2006 г. в 12 часов на заседании диссертационного совета Д212.211.02 в Рязанском государственном радиотехническом университете по адресу: г. Рязань, ул. Гагарина, д. 59/1.

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

Автореферат разослан «12.» а*-*- /_2006 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 390005, г.Рязань, ул.Гагарина, д. 59/1, Рязанский государственный радиотехнический университет.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

И.А. Телков

А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В последние годы в Российской Федерации наблюдается развитие рынка информационных и телекоммуникационных услуг. Новые технологии активно внедряются в различные сферы жизни. В связи с этим важной становится проблема передачи данных. Однако существующая на данный момент инфраструктура сетей недостаточно развита, а линии связи (особенно в регионах) не удовлетворяют пользователей ни по качеству, ни по скорости передачи данных, в связи с чем возникает задача проектирования новых и модернизации существующих линий связи. Примером активно развивающихся сетей являются некоммерческие научно-образовательные сети, такие как 1Ш№1е1, Ш3пе1:, И1ЕЕпе1, ЯЕЬАР^-1Р, ЯиНЕР-Яаёю-МБи, РОСКОН и др.

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

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

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

Значительный вклад в решение задачи построения минимальных сетей внесли Александер Р., Артамонов Г.Т., Бондарев В.М., Вороной Г.Ф., Рублинецкий В.И., Киндл Р., Литтл Дж., Мелзак 3., Митчелл Дж., Прим Р.К., Псиола В.В., Рове С., Хакими С. и другие исследователи.

Объект исследования. Объектом исследования являются проводные телекоммуникационные сети.

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

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

1) минимизация затрат на соединение узлов телекоммуникационной сети на взвешенной плоскости;

2) минимизация затрат на объединение узлов телекоммуникационной сети на взвешенной плоскости в сеть заданной топологии.

Основные задачи. В работе поставлены следующие основные задачи:

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

• исследование существующих методов построения минимальных топологий сети;

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

• определение предварительного направления трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;

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

• объединение точек на взвешенной плоскости в минимальную по стоимости сеть заданной топологии.

Методы исследования. Для решения поставленных задач использован аппарат вычислительной геометрии, теории графов и математического анализа.

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

• сформулирована и решена задача определения минимума стоимости прокладки линии связи между двумя узлами телекоммуникационной сети, расположенными в соседних областях взвешенной плоскости;

• определено необходимое условие минимума стоимости прокладки линии связи между двумя узлами телекоммуникационной сети, расположенными в соседних областях взвешенной плоскости, разделенных произвольной кривой;

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

• предложен алгоритм определения минимальной по стоимости трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;

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

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

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

Апробация результатов диссертации. Результаты, полученные в ходе работы над диссертацией, докладывались на VI международной школе-семинаре аспирантов, магистров и студентов «Современные информационные технологии», Минск, июнь 2003 г.; 9-й всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 21-23 апреля 2004 г.; 10-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 20-22 апреля 2005 г.; VIII международной школе-семинаре аспирантов, магистров и студентов «Современные информационные технологии», Минск, июнь 2005 г.; 14-Й международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 6-8 декабря 2005 г.; Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники "Информационно-телекоммуникационные системы", Москва, 14-16 декабря 2005 г.; 39-й научно-технической конференции РГРТА, 30 января - 4 февраля 2006 г.; 11-й всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 19-21 апреля 2006 г.

Публикации. Основные результаты диссертации опубликованы в 11 работах.

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

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка (90 источников), изложенных на 138 страницах (содержит 6 таблиц, 67 рисунков), и 2 приложений. Общий объем диссертации 201 страница.

СОДЕРЖАНИЕ РАБОТЫ

Общая характеристика работы содержит основные сведения о работе.

Во введении обоснована актуальность темы диссертационной работы и приведена ее структура.

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

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

, . я

/ = 1,л, и, пи 1 = 0, если ыу, и = и. Плоскость V взвешенна, т.е. для

>•1

каждой области и, поставлен в соответствие коэффициент к1 >0, учитывающий стоимость прокладки единицы длины линии связи внутри данной области £/, и стоимость единицы длинны самой линии связи. Такая плоскость и называется взвешенной. Тогда стоимость соединения точек А1 и А} определяется как сумма геометрических длин линий, проходящих через области и,, взвешенную коэффициентами к, > 0

<=1

где Р,,т и - точки входа в область и выхода из /-области

соответственно, т - количество областей, пересекаемых ] -путем (в общем случае т*п), ] - номер прокладываемого пути, - длина пути

между и Р,_ои,. Необходимо минимизировать стоимость соединений узлов проводной телекоммуникационной сети (А1, А}) путем выбора оптимальных последовательностей проходимых путями областей и, и расчета точек и

Р,^, входа в эти области и, и выхода из них.

Показано, что существующие алгоритмы определения маршрута трассы (алгоритмы трассировки) нельзя использовать для поиска минимальной по стоимости трассы на взвешенной плоскости.

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

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

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

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

Рис. 1. Построение кратчайшей линии связи между двумя точками, расположенными в соседних областях, разделенных произвольной кривой

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

sin а, _ к2 sina2 кх

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

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

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

АОч.ЭТ)

N<».0)

: ВОк»)

Рис. 2. Построение кратчайшей линии связи между двумя точками, разделенными прямой линией

Введено понятие коэффициента улучшения стоимости прокладки трассы Р*к), который равен отношению стоимости прокладки трассы по прямой, соединяющей две точки, к стоимости прокладки найденной оптимальной трассы:

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

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

1.

Н|(к«,0) 0,Ос.О) 01(ад,0)

I

к! ВОь.уО

О^О)

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

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

К

вша, = 51па2 = —.

К

Это аналогично полному преломлению света.

Определено условие, при котором трасса «переходит» в область с меньшей стоимостью прокладки единицы длины линии связи:

<У.У, -(V*.1 - - -*!<>. + >«))* < 0 .

Найдены коэффициент улучшения стоимости прокладки трассы Б® для данного случая и его предельные значения:

Ч Г1(х)<Р1(х)

/г<*> =

, Р1(х)>Р,(х)

НтР<4,=.

У.+У,

.Щгтп)

НО».»)

Рис. 4. Построение кратчайшей линии связи между двумя точками, разделенными двумя прямыми

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

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

ж з и к

Рис. 5. Построение кратчайшей линии связи между двумя точками в трех

областях

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

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

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

• предварительный этап;

• этап улучшения.

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

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

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

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

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

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

Ч-П *■« м-и

Рис. 6. Три графовые модели для нахождения предварительной трассы соединения двух точек на взвешенной плоскости

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

В диссертационной работе доказано, что минимальная по стоимости трасса соединения двух точек на взвешенной плоскости обладает свойствами метрики:

1) Б(А,В) = 0, если А = В ;

2) 5(Л,5) = ЯВ,Л);

3) +

Из третьей аксиомы метрики выведено следующее следствие: |5(Л,С) - 5(С, 5)| < Я(А, В) < 5(/4,С) + 5(С, В).

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

Четвертая глава посвящена экспериментальной проверке работы разработанных алгоритмов. Для проведения эксперимента был выбран участок карты Рязанской области (рис. 7). Карта разбита на 30 областей с различной стоимостью прокладки единицы длины линии. Необходимо объединить в сеть минимальной стоимости 14 объектов на карте. Для данного примера были просчитаны стоимость всех трасс линий связи и построены три топологии: «звезда», «дерево», «кольцо».

Рис. 7. Участок карты Рязанской области, разбитый на области с различной стоимостью прокладки

В первой части проводимого эксперимента были рассчитаны следующие параметры:

• среднее уменьшение стоимости прокладки между парой точек на взвешенной плоскости: Сср = 29,9 %;

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

Построены графики числа трасс, стоимость прокладки которых уменьшилась на определенное количество процентов (рис. 8,а) и графики числа трасс, расход кабеля которых увеличился на определенное количество процентов (рис. 8,6).

сети: Ьср = 10,8 % .

Рис. 8. Графики числа трасс, стоимость прокладки которых уменьшилась на определенное количество процентов (а), и графики числа трасс, расход кабеля которых увеличился на определенное количество процентов (б)

Во второй части проводимого эксперимента было определено:

• сокращение стоимости прокладки линий связи между узлами телекоммуникационной сети заданной топологии;

• увеличение расхода кабеля, необходимого для построения сети заданной топологии;

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

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

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

Топология с, с2 С% и и ь* Пег 1Ч.Г

«Звезда» 3384,6 4909,1 31,1% 1235,9 1161,2 6,4% 5 55

«Дерево» 9179,7 16382,6 43,9% 3069,9 2551,2 16,9% 9 43

«Кольцо» 4571,3 5859,6 21,9% 1540,2 1410,0 8,5% - -

Анализ результатов показывает, что предлагаемые алгоритмы позволяют сократить расходы, связанные с прокладкой линий связи при построении сетей, на ~20-30 % и сократить вычисления в ~2 раза.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Корячко В.П., Митрошин А А., Читаев И В. Алгоритм проектирования кластерной системы узлов телекоммуникационной сети // Известия Белорусской инженерной академии. Минск, 2003, №1(15)/1. С.255-259.

2. Митрошин A.A., Читаев И.В. Минимальная стоимость соединения двух точек на взвешенной плоскости как метрика // Новые информационные технологии, Межвузовский сборник научных трудов. Рязань, 2006. С. 5861.

3. Читаев И.В. Алгоритм построения диаграммы Вороного // Новые информационные технологии: Межвузовский сборник научных трудов. Рязань, 2003. С.126-129.

4. Читаев И.В. Анализ методов построения телекоммуникационных сетей минимальной стоимости // Тезисы докладов X всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании». Рязань, 2005. С.106-108.

5. Читаев И.В., Жошкин A.C. Разработка программного обеспечения • соединения двух точек на взвешенной дискретной плоскости // Новые

информационные технологии: Межвузовский сборник научных трудов. Рязань, 2006. С. 123-126.

6. Читаев И.В. Методы построения телекоммуникационных сетей минимальной стоимости // Сборник материалов Всероссийского конкурса инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники "Информационно-телекоммуникационные системы" / Под. ред. А.О. Сергеева. М.: ГНИИ ИТТ "Информика", 2005. С.80.

7. Читаев И.В. Построение кратчайшей линии связи между двумя узлами сети на регионах с различной стоимостью прокладки // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Материалы 14-й Международной науч.-техн. конф. Рязань: Рязанская государственная радиотехническая академия, 2005. С.147-148.

8. Читаев И.В. Построение линии связи минимальной стоимости между двумя узлами на взвешенных регионах, разделенных прямыми линиями // Новые информационные технологии: Межвузовский сборник научных трудов. Рязань, 2006. С.120-123.

9. Читаев И.В. Построение линии связи минимальной стоимости между двумя узлами, расположенными в разных полуплоскостях с различной стоимостью прокладки единицы длины линии связи // Тезисы докладов IX всероссийской научно-технической конференции студентов, молодых

¿се6 А

»11291 /Ш

ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании». Рязань, 2004. С.87-88.

Ю.Читаев И.В. Разработка топологии телекоммуникационных сетей для нужа управления образованием в регионах // Стратегия управления в информационном обществе: Материалы Международной научно-практической конференции, посвященной 15-летию Санкт-Петербургской академии управления и экономики / Под ред. A.B. Миловзорова; Упр. по делам развития образования; Академия управления и экономики Санкт-Петербурга; Ряз. филиал Санкт-Петербургской академии управления и экономики. Рязань, 2005, С.79-80.

П.Читаев И.В. Соединение двух узлов сети на взвешенной плоскости II Тезисы докладов XI Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании». Рязань, 2006. С.94-95.

ЧИТАЕВ Илья Владимирович Методы и алгоритмы автоматизированного проектировании проводных телекоммуникационных сетей минимальной стоимости АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук Подписано в печать 05 06 2006 г Формат 60x84 1/16 Бумага газетная.

Печать офсетная. Гарнитура Times Уел печ л 1,0

Уч -изд. я 1,0. Тираж 100 ж Заказ №

Рязанский государственный радиотехнический университет

390005, Рязань, ул Гагарина, д 59/1

Редакционноеиздят-сльский цетр РГРТУ

• Стр.

Общая характеристика работы.

Введение.

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

1.1 Описание алгоритмов построения сетей минимальной стоимости.

1.1.1 Алгоритмы построения минимальных остовных деревьев. 1.1.2 Алгоритмы построения деревьев Штейнера.

1.1.3 Алгоритмы построения минимальных гамильтоновых контуров.

1.1.4 Анализ предложенных алгоритмов.

1.2 Алгоритмы определения маршрута трассы.

1.2.1 Конструкторская трассировка.

Ь 1.2.2 Строительная трассировка.

1.2.3 Анализ алгоритмов трассировки.

1.3 Анализ близких задач.

Выводы по первой главе.

Глава 2. Разработка математического аппарата соединения двух точек на взвешенной плоскости.

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

2.1.1 Решение уравнений третьей степени (метод Кардано).

2.1.2 Решение уравнений четвертой степени (метод Феррари).

2.2 Соединение точек, расположенных в полуплоскости с высокой стоимостью прокладки.

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

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

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

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

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

Выводы по второй главе.

Глава 3. Разработка алгоритмов соединения точек на взвешенной плоскости и объединение п точек в сеть заданной топологии.

3.1 Разработка алгоритма соединения двух точек на взвешенной плоскости.

3.1.1 Предварительный этап соединения двух точек на взвешенной плоскости.

Вариант 1.

Вариант 2.

Вариант 3.

3.1.2 Улучшение пути, соединяющего две точки на взвешенной плоскости.

3.2 Разработка алгоритма объединения точек на взвешенной плоскости в сеть заданной топологии.

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

Выводы по третьей главе.

Глава 4. Экспериментальная проверка работы разработанных алгоритмов.

4.1 Разработка автоматизированной системы построения сети заданной топологии на взвешенной плоскости.

4.2 Описание вычислительного эксперимента.

1 4.3 Анализ полученных результатов.

Выводы по четвертой главе.

Актуальность темы

В последние годы в Российской Федерации наблюдается развитие рынка информационных и телекоммуникационных услуг. Новые технологии активно внедряются в различные сферы жизни. В связи с этим важной становится проблема передачи данных. Однако существующая на данный момент инфраструктура сетей недостаточно развита, а линии связи (особенно в регионах) не удовлетворяют пользователей ни по качеству, ни по скорости передачи данных, в связи с чем возникает задача проектирования новых и модернизация существующих линий связи. Примером активно развивающихся сетей являются некоммерческие научно-образовательные сети, такие как RUNNet, RBnet, FREEnet, RELARN-IP, RUHEP-Radio-MSU, РОСКОН и др.

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

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

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

Цель работы

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

1) минимизация затрат на соединение узлов телекоммуникационной сети на взвешенной плоскости;

2) минимизация затрат на объединение узлов телекоммуникационной сети на взвешенной плоскости в сеть заданной топологии.

Основные задачи

В работе поставлены следующие основные задачи:

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

• исследование существующих методов построения минимальных топологий сети;

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

• определение предварительного направления трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;

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

• объединение точек на взвешенной плоскости в минимальную по стоимости сеть заданной топологии.

Методы исследования.

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

Научная новизна.

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

• сформулирована и решена задача определения минимума стоимости прокладки линии связи между двумя узлами телекоммуникационной сети, расположенными в соседних областях взвешенной плоскости;

• определено необходимое условие минимума стоимости прокладки линии связи между двумя узлами телекоммуникационной сети, расположенными в соседних областях взвешенной плоскости, разделенных произвольной кривой;

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

• предложен алгоритм определения минимальной по стоимости трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;

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

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

Достоверность.

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

Практическая ценность работы

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

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

Апробация результатов диссертации

Результаты, полученные в ходе работы над диссертацией, докладывались на VI Международной школе-семинаре аспирантов, магистров и студентов «Современные информационные технологии», Минск, июнь 2003 г.; 9-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 21-23 апреля 2004 г.; 10-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 20-22 апреля 2005 г.; VIII Международной школе-семинаре аспирантов, магистров и студентов

Современные информационные технологии», Минск, июнь 2005 г.; 14-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 6-8 декабря 2005 г.; Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники "Информационно-телекоммуникационные системы", Москва, 14-16 декабря 2005г.; 39-й научно-технической конференции РГРТА, 30 января - 4 февраля 2006 г.; 11-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 19-21 апреля 2006 г.

Публикации

Основные результаты диссертации опубликованы в 11 работах.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, библиографического списка (90 источников), изложенных на 138 страницах (содержит 6 таблиц, 67 рисунков), и 2 приложений. Общий объем диссертации - 201 страница.

Выводы по четвертой главе

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

Разработанные в диссертационной работе модели и алгоритмы можно применять при построении новых и расширении существующих сетей, например, некоммерческих научно-образовательных сетей, таких как RUNNet, RBnet, FREEnet, RELARN-IP, RUHEP-Radio-MSU, РОСКОН и др.

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

1. Алексеев В.Б. Теорема Абеля в задачах и решениях М.: МЦНМО, 2001.- 192 е.: ил.

2. Архангельский А.Я. Программирование в C++Builder 5. М.: ЗАО «Издательство БИНОМ», 2000г. - 1152 е.: ил.

3. Артамонов Г.Т. Топология регулярных вычислительных сетей и сред. -М.: Радио и связь, 1985. 192 с.

4. Аттеков А.В., Галкин С.В., Зарубин B.C. Методы оптимизации: Учеб. для вузов / Под ред. B.C. Зарубина, А.П. Крищенко. М.: Изд-во МГТУ им. Баумана, 2001.440 е.: ил.

5. Берж К. Теория графов и ее применения М.: Иностранная литература, 1962.-319 е.: ил.

6. Бермант А.Ф., Араманович И.Г. Краткий курс математического анализа.-М.: Наука, 1973.-736 с.

7. Бет Верити. Кабельные системы: проектирование, монтаж и обслуживание. М.: КУДИЦ-ОБРАЗ, 2004. - 400 е.: ил.

8. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования- Ростов н/Д: Феникс, 1998. 368 е.: ил.

9. Бондарев В.М., Рублинецкий В.И., Сигалов B.JI. Точное решение задачи строительной трассировки ДАН УССР, 1988, №6, сер. «А», с. 67-70.

10. Грин Д., Кнут Д. Математические методы анализа алгоритмов. М.: Мир, 1987.- 120 е.: ил.

11. Дейтел Харви, Дейтел Пол. Как программировать на С++: Пер. с англ. -М.: ЗАО «Издательство БИНОМ», 1999. 1024 е.: ил.

12. М.Ерзин А.И. Задачи проектирования оптимальной сети сбора нефти // Труды школы-семинара «Физика нефтяного пласта», Новосибирск, 2002. -с. 101-104.

13. Инструкция по проектированию линейно-кабельных сооружений связи -М.: Гипросвязь, 1993.

14. Калверт Ч., Рейсдорф К. Borland C++Builder 5. Энциклопедия программиста: Пер. с англ. К.: Издательство «ДиаСофт», 2001. - 944 е.: ил.

15. Каляев А.В., Мелихов А.Н., Курейчик В.М., Гузик В.Ф., Калашников В.А. Автоматизация проектирования вычислительных структур. Издательство Ростовского университета, 1983. 224с.: ил.

16. Карманов В.Г. Математическое программирование 2-е изд., перераб. -М.: Наука, 1980. - 256 е.: ил.

17. Киржнер В.М., Рублинецкий В.И. О процедуре «иди в ближайший» в задаче коммивояжера. Выч. мат. и выч. техн., Харьков, 1973, вып. IV, с.40-41.

18. Кнут Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. М.: Издательский дом «Вильяме», 2002. - 720 е.: ил.

19. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е изд.: Пер. с англ. М.: Издательский дом «Вильяме», 2005. -1296 е.: ил.

20. Корн Г. и Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1970.- 720 с.

21. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. Учебник для ВУЗов М.: "Энергоатомиздат", 1987г. - 400с.: ил.

22. Корячко В.П., Митрошин А.А., Читаев И.В. Алгоритм проектирования кластерной системы узлов телекоммуникационной сети // Известия Белорусской инженерной академии. Минск, 2003г, №1(15)/1. с.255-259.

23. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-432 с.

24. Кудрявцев П.С. Курс истории физики. М.: Просвещение, 1982. - 448 с.

25. Кульгин М.В. Компьютерные сети: практика построения. 2-е изд. -СПб.: Питер, 2003. - 462 е.: ил.

26. ЗЬЛипский В. Комбинаторика для программистов М.: Мир, 1988 - 319 с.

27. Литтл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм решения задачи коммивояжера. Экономика и мат. методы, 1965, №1, с. 13-22.

28. Макконнелл Дж. Основы современных алгоритмов. 2-е дополненное издание - М.: Техносфера, 2004. - 368 е.: ил.

29. Зб.Оре О. Теория графов. М.: Наука, 1968. 352 е.: ил.

30. Палмер М., Синклер Р.Б. Проектирование и внедрение компьютерных сетей. Учебный курс. 2-е изд., перераб. и доп.: Пер. с англ. - СПб.: БХВ-Петербург, 2004. - 752 е.: ил.

31. Попков В.К., Кауль С.Б., Нечепуренко М.И. и др. Методы оптимизации структур зоновых сетей связи. Отв. ред. Алексеев А.С. Новосибирск, 1983.-181 с.

32. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. - 478 с.

33. Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения. -Кибернетич. сб., М.: Мир, 1961, вып. 2, с. 95-107.

34. Псиола В.В. Об одном эвристическом параллельном алгоритме решения задачи Штейнера. Изв. вузов, М.: Приборостроение, 1997. - с. 53-60.

35. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Главная редакция физико-математической литературы издательства «Наука», 1975. - 320с.

36. Техническое зрение роботов / Под ред. Пью А.; Пер. с англ. Миронова Д.Ф.; Под ред. Катыса Г.П.- М.: Машиностроение, 1987. 320 е.: ил.

37. Руководство по строительству линейных сооружений магистральных и внутризоновых кабельных линий связи М.: «Радио и связь», 1986.

38. Семенов А.Б. Проектирование и расчет структурированных кабельных систем и их компонентов. М.: Компания АйТи; ДМК Пресс, 2005. - 416 е.: ил.

39. Структурированные кабельные системы / Семенов А.Б., Стрижаков С.К., Сунчелей И.Р. 5-е изд. - М.: Компания АйТи; ДМК Пресс, 2004. -640+16 е.: ил.

40. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учебное пособие. Изд. 2-е, испр. - М.: ФИЗМАТЛИТ, 2003. - 240 е.: ил.

41. Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне. // Вычислительные методы и программирование. Т.З, 2002. с. 14-39.

42. Скворцов В.А. Примеры метрических пространств. М.: МЦНМО, 2002. -24с.: ил.

43. Советов Б.Я. Яковлев С.А. Построение сетей интегрального обслуживания. Л.: Машиностроение. Ленингр. отд-ние, 1990. - 332 е.: ил.

44. Компьютерные сети. 4-е издание / Таненбаум Э. СПб.: Питер, 2003. -992 е.: ил. - (Серия «Классика computer science»)

45. Тужилин А.А., Фоменко А.Т. Элементы геометрии и топологии минимальных поверхностей. М., Наука, 1991. 176 е.: ил.

46. Уилсон Р. Введение в теорию графов. М.: Мир, 1977. - 207 с.

47. Фень Юань Программирование графики для Windows. СПб.: Питер, 2002. - 1072 е.: ил.

48. Филипс Д., Гарсиа-Диас А. Методы анализа сетей: Пер. с англ. М.: Мир, 1984.-496 е.: ил.

49. Франка П. С++: учебный курс СПб: ЗАО «Издательство «Питер», 1999. - 528 с: ил.

50. Харари Ф. Теория графов. М.: Мир, 1973. - 300 с.

51. Харари Ф., Пальмер Э. Перечисление графов. М.: Мир, 1977. - 324 с.

52. Холингвэрт Д., Баттерфилд Д., Сворт Б. C++Builder 5. Руководство разработчика, том 1. Основы: Пер. с англ. М.: Издательский дом «Вильяме», 2001. - 880 е.: ил.

53. Холингвэрт Д., Баттерфилд Д., Сворт Б. C++Builder 5. Руководство разработчика, том 2. Сложные вопросы программирования: Пер. с англ. -М.: Издательский дом «Вильяме», 2001. 832 е.: ил.

54. Читаев И.В., Жошкин А.С. Разработка программного обеспечения соединения двух точек на взвешенной дискретной плоскости // Новыеинформационные технологии, Межвузовский сборник научных трудов, Рязань, 2006г. с. 123-126.

55. Читаев И.В. Построение линии связи минимальной стоимости между двумя узлами на взвешенных регионах, разделенных прямыми линиями // Новые информационные технологии, Межвузовский сборник научных трудов, Рязань, 2006г. с. 120-123.

56. Петербурга; Ряз. филиал Санкт-Петербургской академии управления и экономики. Рязань , 2005г., с. 79-80.

57. Якобсон А., Буч Г., Рамбо Дж. Унифицированный процесс разработки программного обеспечения. СПб.: Питер, 2002. - 496 е.: ил.

58. Alexander, R. S. 1989 (September). Construction of optimal-path maps for homogeneous-cost-region path-planning problems. Ph.D. thesis, Dept. of Computer Science, U.S. Naval Postgraduate School, Monterey, CA, USA.

59. Chung S., Condon A. Parallel implementation of Boruvka's minimum spanning tree algorithm. In Proc. 10th Int'l Parallel Processing Symp. (IPPS'96), pages 302-315, April 1996.

60. Chazelle B. A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity. Journal of the ACM, 47 (2000), 1028-1047.

61. Dixon В., Rauch M. and Tarjan R. E. 1992. Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput. 21, 1184 -1192.

62. Hakimi. S. L. Steiner's Problem in Graphs and Its Implications. // Networks. 1971. V. l.P. 113-133.

63. Jeff Erickson. Minimum spanning trees. Lecture notes: Fall 2002 — CS 373: Combinatorial Algorithms.

64. Graham R. L. and Hell P. On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1): 43-57, 1985.

65. Kindl R., Rowe C. and Shing Man-Tak A Stochastic Approach to the Weighted-Region Problem: Design and Testing of a Path Annealing Algorithm, Monterey, 1991.

66. Lucena A. and Beasley J. E. A Branch and Cut Algorithm for the Steiner Problem in Graphs. // Networks. 1998. V. 31. P. 39 59.

67. Melzak Z.A. On the problem of Steiner //Canad. Math. Bull. 1960. V.4 P. 143148

68. Mitchell J. S. B. and Keirsey D. Planning Strategic Paths Through Variable Terrain Data, SPIE, Applications of Artificial Intelligence, volume 485, 172179, 1984.

69. Mitchell J. S. B. and Papadimitriou С. H. The weighted region problem, to appear in Journal of the ACM, 1990.

70. Parodi A. M. Multi-goal real-time global path planning for an autonomous land vehicle using a high-speed graph search processor, Proceedings of the 1985 IEEE Conference on Robotics and Automation, 161-167, 1985.

71. Rowe N. C. Roads, rivers, and rocks: optimal two-dimensional route planning around linear features for a mobile agent. To appear in International Journal of Robotics Research, 1990.

72. Rowe N. C. and Richbourg R. F. An Efficient Snell's-Law Method for Optimal-Path Planning Across Multiple Homogeneous-Cost Regions, accepted to International Journal of Robotics Research, to appear 1990.

73. Rowe N. C. and Richbourg R. F. An efficient Snell's-law method for optimal-path planning across multiple two-dimensional irregular homogeneous-cost regions. To appear in International Journal of Robotics Research, 1990.

74. Rowe N. C. and Ross R. S. Optimal grid-free path planning across arbitrarily-contoured terrain with anisotropic friction and gravity effects. Accepted to IEEE Transactions on Robotics and Automation, January 1990.

75. Warme D.M. Spanning Trees in Hypergraphs with Applications to Steiner Trees. // Ph.D. Thesis, Computer Science Dept., The University of Virginia, 1998.