Авторитетность издания
ВАК - К1
RSCI, ядро РИНЦ
Добавить в закладки
Следующий номер на сайте
№4
Ожидается:
09 Декабря 2024
Статьи журнала №3 2016
1. Естественно-языковой пользовательский интерфейс диалоговой системы [№3 за 2016 год]Авторы: Посевкин Р.В. (rus_posevkin@mail.ru) - Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики (Университет ИТМО) (аспирант); Бессмертный И.А. (bia@cs.ifmo.ru) - Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики (Университет ИТМО) (профессор), доктор технических наук;
Аннотация: Множество людей ежедневно взаимодействуют с различными программными системами. В результате внедрения компьютерных систем во все сферы человеческой жизни все больше проявляется проблема перехода от визуальных и командных интерфейсов к естественно-языковым. В статье рассмотрены методы компьютерной лингвистики и обработки естественного языка. Представлено полное описание всех стадий обработки естественного языка, таких как морфологический, синтаксический и семантический анализ. Рассмотрен ограниченный язык как подмножество естественного языка, на котором текст хорошо воспринимается носителем естественного языка без дополнительных усилий. Подобное решение позволяет сократить время анализа естественно-языковых элементов в диалоговой системе, а также помогает избежать неоднозначностей на лингвистическом уровне. Методы для работы с естественным языком могут применяться в программных системах машинного перевода, поисковых системах, системах автоматического реферирования и в экспертных системах. Представлено формальное описание диалоговой системы в контексте марковского процесса принятия решений. Разработан прототип естественно-языкового пользовательского интерфейса, который производит преобразования пользовательского запроса на естественном языке в SQL-запрос к БД. Интерфейс взаимодействует с БД, содержащей информацию о существующих программных библиотеках и фреймворках. Таким образом, использование методов обработки естественного языка позволяет разработать естественно-языковой пользовательский интерфейс для взаимодействия с диалоговой системой.
Abstract: Many people interact with software every day. Due to computer systems expansion to all fields of people’s activity the problem of transition from visual and command interfaces to natural language user interfaces is becoming more and more relevant. The article describes computational linguistics and natural language processing methods. It considers all phases of natural language processing such as morphological, syntactic and semantic analysis. Limited language is represented as a subset of natural language. This language allows avoiding linguistic uncertainty and decreases natural language elements processing time. Translation system is a part of a dialogue system. Methods of natural language manipulation are applied in machine translation software systems, search engines, data exchange, automatic abstracting and expert systems. The paper represents a formal definition of a dialogue system as a Markov decision process. The authors developed a prototype of natural language user interface for a structured data source. It converts natural language user’s query into SQL query to database. User interface interacts with a database that contains information about existent program libraries and frameworks. Consequently, using natural language processing methods makes it possible to develop natural language user interface providing a capability to interact with a dialogue system.
Ключевые слова: диалоговая система, обработка естественного языка, пользовательский интерфейс, бдKeywords: dialogue system, natural language processing, user interface, database
Просмотров: 15999
2. Использование вероятностного вывода в слабоформализованных базах знаний [№3 за 2016 год]
Авторы: Полещук Е.А. (eapoleschuk@corp.ifmo.ru) - Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики (Университет ИТМО) (аспирант); Платонов А.В. (avplatonov@corp.ifmo.ru) - Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики (Университет ИТМО) (аспирант);
Аннотация: В статье рассматривается процесс вероятностного вывода в слабоформализованных базах знаний. В качестве такой базы выбрана графическая модель представления знаний – семантическая сеть. Выбор обусловлен удобством представления автоматически извлеченных данных в виде графа со связями, а также удобством дальнейшего использования (чтения, изменения и поиска ошибок) данного графа. Также проводится сравнение широко используемого на данный момент продукционного подхода с предложенным, указываются основные недостатки продукционного подхода, которые необходимо учитывать при разработке подобных систем извлечения знаний. Целью исследования является извлечение новых знаний из автоматически полученных данных. Для достижения этой цели на графических моделях обычно производится логический вывод. Поскольку модель, а также способ получения данных (в данном случае автоматически или полуавтоматически) накладывают ограничения на механизм вывода, алгоритм вынужден работать в условиях неопределенности. Отсюда следует, что стандартные механизмы логического вывода, предусмотренные для данной модели, становятся неактуальными. В статье предлагается использовать вероятностный вывод и, следовательно, вероятностный язык логического программирования для его реализации. Также делается сравнение нескольких существующих языков вероятностного логического программирования, таких как PRISM, ICL и ProbLog. По результатам сравнения производится выбор языка вероятностного программирования для осуществления вывода. В качестве такого языка выбран язык ProbLog (в частности система ProbLog2), являющийся вероятностным расширением языка Prolog.
Abstract: The article introduces the process of probabilistic inference in weakly formalized knowledge bases. Semantic network is chosen as a graphical model of knowledge representation due to a convenient representation of automatically extracted data as a graph with links. The paper also contains a comparison of widely used production model approach with the proposed one. The authors describe main disadvantages of a production model approach that should be considered for developing such knowledge extraction systems.
The aim of the work is new knowledge extraction from an automatically built knowledge base. Usually logical inference is used to achieve this aim in graphical models. In our case a domain model as well as a process of knowledge building (in particular by automatic or semi-automatic methods) restrict logical inference mechanism, so this algorithm is forced to work in conditions of uncertainty. Thus, standard logical inference algorithms provided for such model become irrelevant.
The article proposes using probabilistic inference for the task and consequently using probabilistic inference programming language. The paper contains a comparison of several modern probabilistic logic programming languages like PRISM, ICL and ProbLog. The authors select a probabilistic logic programming language based on the results of this comparison. To implement probabilistic inference in a weakly formalized knowledge base we have selected ProbLog language (ProbLog2 in particular) that is a probability extension of Prolog.
Ключевые слова: вероятностный вывод, семантические сети, слабоформализованные базы знаний, problog, вероятностное логическое программирование, неопределенность данных, неопределенность отношенийKeywords: probabilistic inference, semantic network, weakly formalized knowledge bases, problog, probabilistic logic programming, data uncertainty, relationships uncertainty
Просмотров: 11133
3. Об эффективности наследования таблиц в СУБД PostgreSQL [№3 за 2016 год]
Авторы: Сорокин В.Е. (sorokinve@yandex.ru) - НИИ «Центрпрограммсистем» (ведущий научный сотрудник), кандидат технических наук;
Аннотация: Одним из следствий расширения использования объектно-ориентированного программирования явилось дополнение реляционных СУБД объектными чертами. На кроссплатформенную свободно распространяемую в исходных кодах объектно-реляционную СУБД PostgreSQL возлагаются большие надежды в импортозамещении инфраструктурного ПО. В ней сочетаются классические для реляционных СУБД принципы ACID с поддержкой сложных типов данных и наследованием таблиц, востребованных при моделировании объектов в БД. При работе со встроенным в PostgreSQL сложным типом jsonb достигнута характерная для объектно-ориентированных СУБД производительность. Для случаев предпочтительного использования базовых и композитных типов данных при моделировании в БД объектов реализован механизм наследования таблиц. В статье проведен сопоставительный анализ этого механизма с наиболее известными методами объектно-реляционного преобразования. Планируемая разработчиками PostgreSQL, но еще не реализованная поддержка единой индексации физических таблиц одной иерархии наследования отмечается ими в качестве основного фактора, ограничивающего применение наследования таблиц ввиду отсутствия поддержки в них уникальной и ссылочной целостности и снижения производительности запросов. Предлагаемое в статье в дополнение к существующему механизму наследования таблиц создание одной общей таблицы для иерархии наследуемых таблиц позволяет обеспечить целостность данных. Эксперименты по выполнению различных запросов свойств объектов, моделируемых в БД по классической модели объектно-реляционного преобразования и по предлагаемому дополненному наследованию таблиц, подтвердили высокую эффективность последнего, что позволяет рекомендовать его для широкого применения, особенно с перспективой появления единой индексации иерархии наследуемых таблиц.
Abstract: One of the consequences of extending the use of object-oriented programming was the addition of a relational DBMS the object features. On cross-platform open source object-relational DBMS PostgreSQL hopes in import substitution infrastructure software. It combines classic relational database ACID principles with complex data types and table inheritance support that are in demand in the simulation objects in the database. When working with the built-in complex type jsonb PostgreSQL is reached object-oriented DBMS performance. For the case of the preferred use of the base and composite data types for modeling objects in the database table inheritance is implemented. The article presents a comparative analysis of this mechanism with the most known methods of object-relational mapping. PostgreSQL developers planned but not yet implemented support single indexing for physical tables of one inheritance hierarchy is marked by them as the main factor restricting the use of inheritance tables due to the lack of support in unique and referential integrity and reduce the performance of the queries. The proposed in addition to existing table inheritance mechanism creating one common table for the hierarchy inherited tables allows you to ensure data integrity. Performed experiments on the execution different queries the properties of the objects modeled in the DB by the classical models of object-relational mapping and the proposed amended inheritance tables confirmed the high effectiveness of the latter, which allows to recommend it for widespread use, especially with the prospect of a single indexing hierarchy of inherited tables.
Ключевые слова: эффективность, sql-запрос, целостность данных, наследование таблиц, объектно-реляционное преобразование, postgresql, субд, объектно-реляционная бдKeywords: effectively, sql query, data integrity, inheritance tables, object-relational mapping, PostgreSQL, DBMS, object-relational database
Просмотров: 19211
4. О некоторых проблемах предметной области поддержки принятия решений [№3 за 2016 год]
Авторы: Тиханычев О.В. (tow65@yandex.ru) - 27 Центральный научно-исследовательский институт Минобороны России (старший научный сотрудник), кандидат технических наук;
Аннотация: В статье проанализировано существующее состояние описания предметной области систем поддержки принятия решений относительно как подходов к классификации таких систем, так и наличия их официального определения. Сделан вывод о том, что сложившаяся ситуация замедляет процессы создания и внедрения в практику управления систем поддержки принятия решений. С целью упорядочения предметной области проведено формализованное описание процесса принятия управленческих решений и введены понятия малого и большого циклов принятия решения. При этом под малым циклом понимается поиск оптимального решения в условиях заданной целевой функции и ограничений, под большим – поиск нетривиального решения, которое невозможно получить без модификации целевой функции или снятия части ограничений. На основе данного подхода предложено уточнить определение автоматизированной системы принятия решений и классификацию таких систем. В части уточнения классификации основным показателем в работе является деление по функционалу относительно реализуемого системой цикла принятия решения. В рамках новой классификации предложено взамен применяемого в настоящее время класса «относительно уровня пользователя» использовать класс «по функционалу», в состав которого включить информационные, расчетноинформационные и интеллектуальные системы. Данная классификация более полно соответствует современному пониманию автоматизированной системы поддержки принятия решений и позволит ускорить процесс внедрения таких систем в практику управления.
Abstract: The article analyzes the current state of a decision support domain: both in terms of classification principles of such systems and their official definition. This situation complicates the process of creation and application of decision support systems. To normalize this domain the author formalizes a description of a decision-making process and formulates the concepts of “small” and “extended” decision-making cycles. “Small” cycle refers to the process of finding an optimal solution in terms of a set objective function and the restrictions. “Big” cycle includes searching for a non-trivial solution, which cannot be obtained without modifying the objective function or restriction cancellation. Based on this approach the author proposes to clarify the definition of an automated decision-making system and its classification. The main indicator in clarifying the classification is functional defined by the type of a decision-making cycle. Within a new classification it is proposed to replace the currently used class “relative to the user level” by the class “by the functional”, which includes information, calculation and information and intelligent systems. The proposed classification completely corresponds to the modern understanding of automated decision-making support system and can accelerate the process of implementing such systems in management practice.
Ключевые слова: система поддержки принятия решений, экспертная система, классификация систем поддержки принятия решений, система информационной поддержки, интеллектуальная система, цикл принятия решенияKeywords: decision support system, expert system, classification decision-making support systems, information support system, intellectual system, decision-making cycle
Просмотров: 17657
5. Вычислительные процедуры обработки неточной временной информации [№3 за 2016 год]
Авторы: Фомин В.В. (v_v_fomin@mail.ru) - Российский государственный педагогический университет им. А.И. Герцена (профессор), доктор технических наук; Мальцев С.В. (maltsevsergey@live.com) - Российский государственный педагогический университет им. А.И. Герцена (аспирант);
Аннотация: В статье представлены результаты обширного исследования, обусловленного практической потребностью повышения эффективности методов представления, алгоритмов извлечения, обработки нечетких темпоральных данных. Акцент делается на онтологических моделях процессов прогнозирования и интерпретации при взаимодействии с неточной временной информацией. Предлагаются методология хранения данных, а также модели и унифицированные процедуры извлечения нечеткой информации. Непосредственно затрагивается вопрос о прагматике алгоритмов представления темпоральных данных через новый инструмент так называемой возможностной темпоральной информации в аналитических системах, где параметры неточности и оперативности являются критическими условиями в принятии бизнес-решений. Предлагаются решения проблем хранения и извлечения неточной временной информации за счет построения модели обработки нечетко-темпоральных отношений между временными точками и/или интервалами. Представлена концепция анализа и представления нечеткой темпоральности в рамках развития модели темпоральных реляционных БД с учетом критериев неточности, неоднозначности, неопределенности. Разработана алгебра возможностных отношений точек и/или интервалов, в ее рамках определены понятия возможностной временной точки и возможностного интервала, введены соответствующие значения возможностных временных точек и интервалов. Представлен фрагмент формализованного алгоритма реализации алгебры на примере расширения одного из отношений. Предлагается подход к разработке и моделированию нечеткого темпорального домена и отношений между возможностными интервалами и моментами времени. Дано описание реализованной библиотеки алгоритмов обработки отношений возможностных временных точек и/или интервалов, а также соответствующих процедур и функций на платформе стандарта SQL. Представлены результаты внедрения библиотеки алгоритмов при реализации коммерческого проекта аналитической системы для телекоммуникационной компании, а также определены направления дальнейшего развития прикладного инструментария, основанного на теории нечетко-темпоральной модели.
Abstract: The article presents the results of extensive research resulting from a practical need in improving the effectiveness of representation methods, extraction algorithms, processing fuzzy temporal data. The authors focus on ontological models of prediction and interpretation during interaction with imprecise temporal information. They propose a data storage methodology as well as models and unified procedures for extracting fuzzy information. The pragmatic of temporal data representation algorithms is considered using a new so-called possibilistic temporal information in analytical systems, where the parameters of inaccuracy and efficiency are crucial for making business decisions. The article proposes solutions for the problems of imprecise temporal information storage and retrieval by constructing a model of processing fuzzy temporal relations between time points and/or intervals. The concept of fuzzy temporal information analysis and presentation is described within development of temporal relational databases framework taking into account the criteria of inaccuracies, ambiguity and uncertainty. The authors developed he algebra of possibilistic relations between points and/or intervals. It defines the concept of possibilistic time point, possibilistic interval and corresponding values of possibilistic time points and intervals. The example of extension of one of the relations describes the fragment of a formalized algorithm of algebra implementation. The authors propose an approach to design and modeling a fuzzy temporal domain as well as the relations between possibilistic intervals and time points. The article describes an implemented library of algorithms for processing relations between possibilistic time points and/or intervals, as well as corresponding procedures and functions on SQL platform. At the end, the article describes the results of integration of the library of algorithms in a commercial project of analysis system for a telecommunication company. It also describes areas for further development of application tools based on the theory of a fuzzy-temporal model.
Ключевые слова: темпоральные бд, временная неопределенность, программы и алгоритмыKeywords: temporal databases, temporal uncertainty, programs and algorithms
Просмотров: 10216
6. Безопасность баз данных: проблемы и перспективы [№3 за 2016 год]
Авторы: Полтавцева М.А. (maria.poltavtseva@ibks.icc.spbstu.ru) - Санкт-Петербургский политехнический университет Петра Великого (доцент), кандидат технических наук; Хабаров А.Р. (al_xabarov@mail.ru) - Тверской государственный технический университет (доцент), кандидат технических наук;
Аннотация: Вопросы защиты данных являются критическими при обеспечении безопасности современных корпоративных систем. Статья посвящена сложившейся ситуации в области безопасности данных, находящихся под управлением систем БД. Сделан обзор существующих работ на указанную тему как отечественных, так и зарубежных авторов. Рассмотрены этапы эволюции систем защиты информации в СУБД. Выделены современные комплексные проблемы в области защиты данных теоретического и практического характера. При анализе проблем безопасности учтены новые направления развития СУБД, такие как in memory и NoSQL-решения. В статье выделены особенности БД с точки зрения информационной безопасности по отношению к другим видам ПО. Предложено базовое деление уязвимостей СУБД на основании выделенных особенностей. Сформулированы перспективные пути исследований и развития систем защиты для построения надежных и защищенных серверов по обработке информации.
Abstract: Data protection issues are critical when ensuring modern enterprise systems security. The paper is devoted to the current situation in database systems security. The paper provides an overview of existing publications, both Russian and foreign authors. It reviews the stages of a database information security systems evolution. The paper describes modern complex problems in DBMS data protection, both theoretical and practical. The analysis of security issues takes into account new directions of the database development, such as “in memory” and NoSQL DBMS. The article describes database features in terms of information security compared with other types of software. It includes the basic database vulnerabilities division based on selected features. The authors formulate promising ways of research and development of security systems for building reliable and secure information management systems.
Ключевые слова: бд, субд, информационная безопасность, nosql, уязвимости, защита данных, безопасность данных, поKeywords: database, DBMS, infosecurity, nosql, attack, data protection, data security, software
Просмотров: 32216
7. Построение модели угроз безопасности информации в автоматизированной системе управления критически важными объектами на основе сценариев действий нарушителя [№3 за 2016 год]
Авторы: Дроботун Е.Б. (drobotun@xakep.ru) - Военная академия воздушно-космической обороны им. Маршала Советского Союза Г.К. Жукова (докторант), кандидат технических наук; Цветков О.В. (drobotun@xakep.ru) - Военная академия воздушно-космической обороны им. Маршала Советского Союза Г.К. Жукова (начальник службы защиты государственной тайны );
Аннотация: Разработка и построение модели угроз безопасности информации в различных автоматизированных и информационно-вычислительных системах является одним из ключевых этапов деятельности по обеспечению безопасности информации в этих системах и их безопасного и правильного функционирования. На основе модели угроз безопасности информации определяются требования к системе защиты информации в автоматизированных и информационновычислительных системах, а также может быть определен комплекс организационных, технических и организационно-технических мер по обеспечению безопасности информации в автоматизированных и вычислительных системах различного назначения. В статье предлагается методика построения модели угроз для автоматизированных систем управления критически важными и потенциально опасными объектами, основанная на моделировании возможных сценариев действий нарушителя безопасности информации. Предложенная методика учитывает многоуровневость построения современных автоматизированных систем управления критически важными объектами и возможность реализации одной и той же угрозы безопасности информации с помощью различных сценариев нарушителями различных категорий. Применение предложенной методики позволит сократить время, необходимое для построения модели угроз безопасности информации в автоматизированных системах управления критически важными и потенциально опасными объектами.
Abstract: Development and construction of information security threat models in various automated and data-processing systems is one of key steps in ensuring information security in these systems and their safe and proper operation. Based on the information security threat model we can define the requirements to information security in automated data-processing systems.
We can also define a set of organizational, technical, organizational and technical measures to ensure information security in automated and computer systems for various purposes.
The article proposes a method of constructing a threat model for automated control systems of crucial and potentially dangerous objects. The method is based on modeling information security violator’s possible action scenarios. The proposed method takes into account a multilevel structure modern automated control systems for crucial objects and the possibility of implementing the same information security threats using different scenarios by different violators.
The proposed methodology would reduce the time for building a model of information security threats in automated control systems for crucial and potentially dangerous objects.
Ключевые слова: критическая информационная система, угроза безопасности информации, нарушитель безопасности информации, модель угроз, модель нарушителяKeywords: critical information system, nformation security threat, security information violator, threat model, violator’s model
Просмотров: 21598
8. Синтез систем защиты автоматизированных систем управления от разрушающих программных воздействий [№3 за 2016 год]
Авторы: Дроботун Е.Б. (drobotun@xakep.ru) - Военная академия воздушно-космической обороны им. Маршала Советского Союза Г.К. Жукова (докторант), кандидат технических наук;
Аннотация: Информатизация и автоматизация различных объектов производства, в том числе создающих потенциальную угрозу обеспечению безопасности жизнедеятельности, сделала обеспечение безопасности функционирования таких объектов одной из наиболее острых проблем современности. Процессы информатизации и автоматизации обусловливают появление новых видов угроз информационной безопасности, направленных на нарушение функционирования производственных объектов, которые могут быть подвергнуты деструктивным информационно-техническим воздействиям, и создающих потенциальную угрозу обеспечению безопасности жизнедеятельности. Данные факторы в сочетании с возрастающим уровнем зависимости общества от устойчивости функционирования объектов, создающих потенциальную угрозу обеспечению безопасности жизнедеятельности, требуют принятия комплекса мер (в том числе и технического характера), направленных на снижение риска нарушения или полного прекращения функционирования таких объектов в условиях информационно-технических воздействий. В статье представлен один из возможных подходов к построению рациональной (с точки зрения обеспечения требуемого уровня защищенности и минимального влияния системы защиты на защищаемую автоматизированную систему) системы защиты от разрушающих программных воздействий как основного вида информационно-технических воздействий, которым могут быть подвергнуты автоматизированные системы.
Abstract: Informatization and automation of various industrial facilities (including facilities that create potential safety threats) has made functioning safety of such objects one of the most important issues of modern age. Informatization and automation cause emergence of new types of threats for information security directed to violation of functioning of production objects that create a potential threat of safety, which can be exposed to destructive information and technical influences. These factors in combination with the increasing level of society dependence on functioning stability of the objects, which create potential safety threat, demand a package of measures (including technical measures) to decrease the risk of violation or complete cessation of such objects’ functioning under information and technical influences.
The article presents one of possible approaches to constructing rational (in the context of ensuring the demanded security level and minimum influence of protection system on a protected automated system) system of protection against destroying program influences as the main type of possible information and technical influences on automated control systems for crucial and potentially dangerous objects.
Ключевые слова: автоматизированная система управления технологическими процессами, потенциально опасный производственный объект, информационная безопасность, разрушающее программное воздействие, защита от разрушающих программных воздействийKeywords: automated control system of technological processes, potentially dangerous industrial object, infosecurity, destroying program influence, protection against destroying program influences
Просмотров: 11895
9. Алгоритм поиска оптимального расположения сенсоров для решения задачи мониторинга пространства [№3 за 2016 год]
Авторы: Кочкаров А.А. (AKochkarov@oaorti.ru) - Компания «РТИ», Финансовый университет при Правительстве Российской Федерации, (зам. директора Научно-тематического центра), кандидат физико-математических наук; Яцкин Д.В. (Danil@frtk.ru) - Московский физико-технический институт (государствнный университет) (аспирант);
Аннотация: Рассмотрены задача мониторинга пространства, переход к задаче обнаружения, а затем к задаче геометрического расположения сенсоров. Для решения поставленной задачи предлагается использовать децентрализованную сеть сенсоров. Устанавливаются отграничения и допущения, приводящие к задаче покрытия пространства. Проводится дискретизация задачи, обосновывается ее необходимость. Задача подробно рассматривается с математической точки зрения, разрабатывается алгоритм ее решения, оценивается его сложность. Проводится математическое и программное моделирование задачи. Разрабатывается программный комплекс, реализующий указанный алгоритм. По заданной карте местности и параметрам среды, а также с использованием ряда начальных условий, определяющихся физическими характеристиками сенсоров, программный комплекс позволяет рассчитать точки пространства, при размещении в которых устройств-обнаружителей задача мониторинга будет считаться решенной. На данном программном комплексе осуществлен ряд испытаний, показавших работоспособность, корректность и оптимальность разработанных подходов и алгоритма. Благодаря невысокой полиномиальной вычислительной сложности алгоритма, с помощью программного комплекса можно решать задачи мониторинга в конкретном случае и для больших зон мониторинга, и для сотен устройств-обнаружителей.
Abstract: The paper considers the task of space monitoring, an algorithm and software package to solve it. From this problem the authors move to the problem of detection, and then to the problem of geometrical sensors location. It is proposed to use a decentralized robotic network to solve th у proposed problem. The authors set limitations and assumptions for sensors location problem leading to the problem of space covering. They also discretize problem parameters. The paper describes the problem in detail from a mathematical point of view, develops the algorithm to solve it, estimates its complexity. There mathematical and software models of the problem. The authors develop a software package that implements the specified algorithm. The map of the area and a number of physical parameters of the sensor serve as input data for a software package. The package allows calculating points in space, where the placed devices (detectors) help to solve the monitoring problem. This software package was used for a series of tests. The tests showed efficiency, correctness and optimality of the developed approaches and the algorithm. Due to the low polynomial computational complexity of the algorithm the software package can solve monitoring tasks for the particular case of large areas of monitoring, as well as for a big number of sensors.
Ключевые слова: мониторинг, групповое управление, сеть сенсоров, мобильный сенсор, алгоритмы покрытия, теория множеств, покрытие пространства, сенсор, обнаружение, программный комплексKeywords: the automated information system, group management, robotic network, mobile robot, covering algorithms, set theory, covering space, sensor, detection, software package
Просмотров: 12583
10. Пчелиный алгоритм оптимизации для решения задачи планирования беспроводной сети [№3 за 2016 год]
Авторы: Скаков Е.С. (wallkirya@mail.ru) - Липецкий государственный педагогический университет (аспирант); Малыш В.Н. (vmalysh@mail.ru) - Липецкий филиал Российской академии народного хозяйства и государственной службы при Президенте Российской Федерации (профессор), доктор технических наук;
Аннотация: Статья посвящена решению проблемы планирования беспроводной сети. В ней сформулирована задача размещения базовых станций, учитывающая межсотовые помехи, затухание при распространении сигнала, несколько типов базовых станций. Решение задачи представляется в виде массива структур, хранящих информацию об одном местекандидате (тип установленной базовой станции, список подключенных к ней клиентов). Разработана модификация одного из метаэвристических методов – пчелиного алгоритма BCO (Bee Colony Optimization). Метод оптимизации подражанием пчелиной колонии относится к мультиагентным методам, основанным на моделировании интеллектуального поведения колоний агентов, так называемым методам роевого интеллекта. В природе подобным интеллектом обладают группы общественных насекомых, например, колонии муравьев, пчел, термитов. В основе предлагаемого алгоритма лежит понятие окрестности текущего решения. Для формирования окрестности используются небольшие операции по изменению текущей конфигурации беспроводной сети. Новое решение из окрестности текущего может быть получено при помощи одной из двух операций: смена типа одной станции на более дешевый, удаление одной базовой станции. Новый алгоритм реализован как ПО в среде разработки Delphi. Показано, что пчелиный алгоритм позволяет находить решение задачи размещения базовых станций за приемлемое время, на много порядков быстрее точного метода полного перебора. Выявлена зависимость качества решения поставленной задачи методом подражания пчелиной колонии от значений управляющих параметров алгоритма.
Abstract: The article is devoted to solving a wireless network planning task. The authors defined the problem of base stations’ location, taking into account the level of attenuation of signal during propagation, the level of inter -cell interference and several types of base stations. A problem solution is represented as a vector of structures, each structure stores data about one potential site (an installed base station type, a list of connected clients).
A modification of one of metaheuristic methods (bee colony optimization algorithm) has been developed. The bee colony optimization method is a multi-agent method based on simulation of intelligent behavior of agent colonies (the so-called swarm intelligence methods). Naturally, some groups of social insects (for example, colonies of ants, bees, termites) have such intellect. The proposed algorithm is based on the concept of current solution neighborhood. Little changes in current wireless network configuration are used to form the neighborhood. To obtain a new solution from the neighborhood of the current solution we can use one of the following two operations: changing the type of a station to more cheap or removing a base station.
The developed algorithm is implemented in Delphi programming environment. The article shows that the new algorithm helps to find the solution for the base station location problem in a reasonable time, much faster than the exact method of exhaustive search. The authors found out how the quality of the problem solution obtained by bee colony optimization algorithm depends on values of control parameters.
Ключевые слова: размещение базовых станций, пчелиный алгоритм, беспроводные сети, оптимизация, sirKeywords: base station location, bee colony optimization, wireless network, optimisation, sir
Просмотров: 14972
| 1 | 2 | 3 | 4 | Следующая → ►