Единое окно доступа к образовательным ресурсам

Десятая конференция разработчиков свободных программ: Тезисы докладов

Голосов: 0

В книге собраны тезисы докладов, одобренных Программным комитетом десятой конференции разработчиков свободных программ, которая прошла в городе Калуге 20-22 сентября 2013 года.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    Дневное заседание (14.50–18.10)                                 61


Сервер
   В качестве серверной платформы мы применяем в повседнев-
ной деятельности системы на базе Marvell ArmadaXP, которая со-
держит четыре раздельных узла на базе четырёхъядерных ARMv7-
совместимых SoC на 1.6 ГГц с поддержкой памяти DDR3 ECC и
SATA. Производительность одного ядра на ощупь соответствует
примерно средним PIII, что вместе с большим объёмом памяти (2–8
Гб с учётом поддержки PAE) позволяет вполне комфортно реализо-
вывать сборку пакетов и образов. Каждый отдельный узел способен
загружаться с USB Flash и внутреннего SATA HDD/SSD; выбор осу-
ществляется при помощи традиционного для ARM-систем загрузчика
uboot, взаимодействие с которым возможно посредством интерфейса
USB-serial. Работа с настроенной системой происходит через обычный
Ethernet.
   Замеченные недостатки:      существенно более низкая, чем теоре-
тически возможно, пропускная способность при работе с RAM; вы-
ключение или аппаратный сброс осуществляются сразу для всех уз-
лов;    при активном использовании пассивного охлаждения не хва-
тает, приходится применять продувку вентиляторами; сложности с
подбором совместимой памяти.
   Достоинства: достаточно мощная ARM-система; относитель-
но небольшой нагрев; возможность работы с большим объёмом па-
мяти, SATA-дисками, Ethernet.
   В остальном система получилась достаточно пригодная к исполь-
зованию и обслуживаемая.

Десктоп
   В качестве законченного решения для миниатюрной настольной
системы взят кубик SolidRun Cubox Pro на базе Marvell Dove; это
одноядерная система (ARMv7-совместимый SoC на 800 МГц) с 2 Гб
памяти и интерфейсами USB2, HDMI, S/PDIF, IR, eSATA. Она штат-
но загружается с microSD-карточки, что можно наблюдать с другого
компьютера, подключив USB-порт кабелем к отладочному microUSB-
порту Cubox, который заведён на USB-serial. Процессор на ощупь
напоминает PII-300, т.е. под легковесными окружениями вроде XFCE
и TDE машинка работает достаточно комфортно, а современные
вроде KDE4 запускать запускает, но уже заметно медленней. Отчасти


62                                                      21 сентября


это обусловлено небыстрым I/O, ведь microSD class 10 обеспечивает
всего 10 Мб/сек; после загрузки и кэширования бинарников в памяти
работать уже удобнее.
   Ожидается вторая версия Cubox с улучшенными характеристика-
ми по производительности SoC.
   Замеченные недостатки: весьма избирательная акселерация ви-
део (youtube скорее не посмотреть);     CPU недостаточно мощный,
чтобы тяжёлый Javascript вроде google search/mail обрабатывался без
заметных задержек.
   Достоинства:    весьма компактная законченная экономичная
платформа;   очень удобная организация загрузки; наличие воз-
можности задействовать ускорение видео.


Портатив

   Из мобильных компьютеров мы рассматривали Nexus 7 первого
выпуска (на Tegra 3)     это четырёхъядерный SoC на 1,2 ГГц с 1
Гб памяти, загружающийся со встроенной флэш-памяти. Из возмож-
ных вариантов загрузки      в качестве единственной ОС или kexec-
мультибут при помощи TWRP         был выбран последний как наибо-
лее удобный для экспериментов с несколькими окружениями (Plasma
Active и E17), размещёнными в соседних чрутах. Этот вариант также
позволяет легче, быстрей и безопасней разворачивать новые чруты,
не рискуя брикнуть устройство. К сожалению, задействовать ви-
деоускоритель в полной мере не удалось (артефакты в плазме), хотя
даже на программном рендеринге оба испробованных интерфейса до-
статочно быстры. В качестве одного из главнейших вопросов сразу же
выступает экранная клавиатура, которая в наличии в обоих проектах,
но доступна только для поддерживающих её приложений нормаль-
но работать с xterm не получится. Также работает WiFi и звук, а вот
с 3G-модемом проблемы: доступен код драйвера, но необходимые для
работы юзерспейсные хелперы недоступны.
   Можно было бы говорить о преимуществах, недостатках и даль-
нейшей разработке но Google благополучно выпустил вторую вер-
сию на совершенно другом SoC, поддержки которого пока нет.


Дневное заседание (14.50–18.10)                                         63


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

Благодарности
   Самая тяжёлая часть работы по поддержке ARMv7 в ALT Linux
была проведена Сергеем Большаковым; также хочется сказать спаси-
бо Ивану Овчеренко за примеры, советы и подсказки.

Игорь Воронин
МО, г. Шатура, Институт проблем лазерных информационных технологий
РАН

Образовательный проект по робототехнике УМКИ на
                  основе СПО

                               Аннотация
       Подготовка инженерно-технических кадров на основе СПО. Управ-
   ление множеством передвигающихся в пространстве роботов по зара-
   нее заданным алгоритмам. Локализация и идентификация положений
   роботов относительно реперных устройств и методом триангуляции.
   Использование сенсорных сетей для связи роботов в кластеры и груп-
   пы с идентичными алгоритмами управления.

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


64                                                    21 сентября




                     Рис. 1: Структура РСС




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


Дневное заседание (14.50–18.10)                                65


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

Существующие методы маршрутизации в РСС
   Существующие методы маршрутизации можно разделить на не-
сколько категорий [2] прямая, иерархическая и маршрутизация в за-
висимости от географического положения. Прямая маршрутизация
подразумевает передачу сообщений от узла к узлу в сети где, каждый
узел выполняет одинаковую функцию передачи и/или ретрансляции,
в отличие от иерархической, где выделяется узел сбора и обработки
информации. Минус прямой маршрутизации в том, что сети соби-
рающие информацию с какой-то области будут посылать множество
избыточной информации, особенно при значительной плотности сен-
сорной сети. Для того что бы избежать избыточности информации
используют специальные алгоритмы, направленные на получение ин-
формации не от узлов, а от определенной области сети. Например
в работе [3] описан алгоритм SPIN1 , где базовая станция посылает
запрос к определенному региону сенсорной сети. Получив запрос, уз-
лы области выполняют требование запроса, локально обмениваются
данными и посылают обратно обобщенный ответ.
   При иерархической же маршрутизации для сбора и обработки тре-
буется использовать узлы с большим запасом энергии, что хотя и
позволяет экономить на передачи уже обработанных данных значи-
тельно меньшего объема зачастую не приемлемо ввиду однородности
используемых приборов или других трудностей. Что бы не использо-
вать специализированные узлы существуют различные технологии.
Например, в работе [4] описана технология LEACH2 , когда функцию
сбора принимает поочередно несколько узлов сенсорной сети выбира-
емых по определенному алгоритму, тем самым распределяя нагрузку
узла сбора.
  1   SPIN  Sensor Protocols for Information via Negotiation
  2   LEACH   Low-Energy Adaptive Clustering Hierarchy


66                                                      21 сентября


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

Алгоритм маршрутизации с балансировкой трафика
    Сеть представляется, как граф G(N, M ) c N узлами и M гранями,
который представляет набор существующих узлов и возможные свя-
зи между ними соответственно. Каждый i-й узел изначально имеет
запас энергии Ei . Каждая грань ij имеет цену eij , которая соответ-
ствует стоимости передачи одного пакета данных от узла i к j. Счита-
ется, что есть K направлений передачи, а информация генерируется
со скоростью Qc и передается по каналу связи c со скоростью qc .
    Время жизни каждого узла будет равняться в такой системе

                                          Ei
                         Ti =
                                          qc     ec
                                                  ij
                                j∈M        j,c

     Тогда время жизни всей системы определим как:

                          Tsys = min Ti (qc )
                                     i∈N

     Задача максимизации времени жизни будет выглядеть:

                          M aximize Tsys
     При условиях:


                                qij > 0
                               qc         ec ≤ Ei
                                           ij
                         j∈M        j,c


Дневное заседание (14.50–18.10)                                 67


   Последнее условие   это ограничение потребления энергии каж-
дого узла.
   Так же необходимо условие сохранения потока информации:


                        Qc +          qij =          qik ,
                               i∈Sj           k∈Si


    где i   соответствует всем потокам информации от узлов к стокам
k
    Такая формулировка не применима напрямую, но служит для того
что бы показать что задача максимизации может быть решена точно
за полиномиальное время. В общем алгоритм маршрутизации должен
соответствовать задаче, поставленной перед сенсорной сетью. Когда
она направлена на сбор какой-либо информации, то основным пока-
зателем будет время работы и точность собранных данных. Если же
целью сети является информирование или оперативная реакция на
проявления окружающей среды, то в основным показателем будет,
первую очередь, время задержки доставки сообщений по сети. Рас-
пределение узлов может быть как равномерным, так и хаотическим в
зависимости от метода расстановки приборов. Если узлы были уста-
новлены вручную в определенные изначально места, то доставка со-
общений может происходить по заранее заданным маршрутам. В слу-
чае произвольной установки необходимо либо использовать способы
геометрической маршрутизации [5], либо устанавливать узлы с гло-
бальной информацией о всех имеющихся маршрутах и связях, для
расчета маршрутов и т.п.
    Часто узлы могут быть блокированы из-за недостатка заряда
батареи, выхода из строя по различным причинам, поэтому меха-
низм маршрутизации должен быть защищен от такого рода измене-
ний. Так же он должен учитывать особенности маломощных приемо-
передатчиков в БСС. Сенсорная сеть может содержать разное коли-
чество узлов, поэтому объем служебного трафика и данных не дол-
жен быть связан с числом узлов. Узлы сети работают от автоном-
ных источников питания, поэтому каждый алгоритм должен быть
энергоэффективным. Для увеличения времени жизни предлагается к
стандартному алгоритму маршрутизации по тому или иному способу
добавлять так же алгоритм распределения трафика представленный
ниже (см. рис 2).


68                                                     21 сентября




Рис. 2: Схема алгоритма распределения нагрузки. N      количество
                    узлов соседних с текущим



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


                                                                            69


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

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

Литература
[1] Giuseppe Anastasi, Marco Conti, Mario Di Francesco, Andrea Passarella,
     Energy conservation in wireless sensor networks: A survey , Ad Hoc
    Networks 7 (2009) pp. 537–568
[2] Jamal N. Al-Karaki, Ahmed E. Kamal Routing techniques in wireless
    sensor networks: a survey Wireless Communications, vol. 11 №6, (2004)
    pp. 6   28
[3] J. Kulik, W. R. Heinzelman, and H. Balakrishnan, Negotiation-Based
    Protocols for Disseminating Information in Wireless Sensor Networks ,
    Wireless Networks, vol. 8, (2002), pp. 169–85
[4] Heinzelman W., Chandrakasan A., Balakrishnan H. Energy-efficient
    communication protocol for wireless microsensor networks // Proceedings
    of the 33rd Hawaii international conference on system sciences. Maui (USA),
    2000.P. 8020–8029.
[5] Баскаков С.С. Маршрутизация по виртуальным координатам в бес-
    проводных сенсорных сетях , диссертация кандидата наук (2011) 218
    стр.


70                                                         Вне программы


Александр Гороховский              ∗
Киев, Национальный технический университет Украины       КПИ
Проект:      Chemical cocktail http://193.243.153.46/chemistry/

   Поиск уравнений реакций и стехиометрических
  коэффициентов для произвольно заданной смеси
      веществ, используя Chemistry::Harmonia


                                  Аннотация
        Рассмотрен концептуальный алгоритм и интерфейс новой подпро-
     граммы Perl-модуля Chemistry::Harmonia stoichiometry. С её по-
     мощью, для произвольно заданной смеси химических соединений мож-
     но найти все возможные „химически правильно“ сбалансированные
     уравнения реакций и фундаментальные наборы стехиометрических ко-
     эффициентов участников превращений.
        Её применение разнообразно: CLI, GUI и Internet приложения, в
     хемоинформатике      создание химических баз данных, для образова-
     тельных и научно-аналитических задач.
        Вдохновение для разработки автор черпал в сообществе GNU Linux,
     языка Perl и его модулей CPAN.
   Среди большого разнообразия способов поиска стехиометрических
коэффициентов (окислительно-восстановительных полуреакций, по-
атомный, по стадиям, структурно-схематический, основной и уско-
ренный электронный, электронно-ионный, механический) [1, 2, 3, 4, 5]
для уравнивания химических реакций, как наиболее универсальный
с точки зрения программной реализацией, наибольшее применение
получил алгебраический способ.
   Известными on-line ресурсами, предназначенными для уравнива-
ния химических реакций являются:
   • Химик: Уравнивание химических реакций (http://www.xumuk.
     ru/uravnivanie/index.php)
     • Автоуравнитель (http://www.ximicat.com/info.php) или Balance
       Chemical Equation (http://www.webqc.org/balance.php)
     • Calculator for Сhemical Equation Balancer (http://www.gregthatcher.
       com/Chemistry/BalanceChemicalEquations.aspx)

     ∗   an.gorohovski@gmail.com



    
Яндекс цитирования Яндекс.Метрика