Методы декомпозиции разреженных cистем линейных алгебраических уравнений для оценки трафика обобщенного мультиграфа

Abstract

Проблема определения местонахождения датчиков в сети для мониторинга потоков стала объектом повышенного интереса в последние несколько лет из-за ее значимости в областях управления и контроля трафика. Основой для моделирования процессов оценки потоков в обобщенной мультисети является разреженная недоопределенная система линейных алгебраических уравнений специального вида. Датчики расположены в узлах мультисети для заданных долей потоков на дугах в пределах соответствующего диапазона. Рассматриваемая проблема местоположения датчиков, как известно, является NP-полной. Разработаны эффективные алгоритмы определения рангов матриц каждой из независимых подсистем, полученных в результате применения теории декомпозиции. Из равенства суммы рангов матриц независимых подсистем и числа неизвестных в независимых подсистемах следуют условия единственности решения специальной разреженной системы линейных алгебраических уравнений. Результаты исследования могут быть также применены для построения оптимальных решений задач математического программирования. = The problem of locating sensors on the network to monitor flows has been object of growing interest in the past few years, due to its relevance in the field of traffic management and control. The basis for modeling the processes of estimating flows in generalized multinetwork is a sparse underdetermined system of linear algebraic equations of a special type. Sensors are located in the nodes of the multinetwork for the given traffic levels on arcs within range covered by the sensors, that would permit traffic on any unobserved flows on arcs to be exactly. The problem being addressed, which is referred to in the literature as the Sensor Location Problem (SLP), is known to be NP-complete. In this paper the effective algorithms are developed to determine the ranks of the matrices of each of the independent subsystems obtained as a result of applying the theory of decomposition. From the equality of the sum of the ranks of the matrices of independent subsystems and the number of unknowns in independent subsystems, the uniqueness conditions for the solution of a special sparse system of linear algebraic equations follow. The results of the research can also be applied to constructing optimal solutions to problems of mathematical programming.