10.14489/vkit.2015.03.pp.028-032

DOI: 10.14489/vkit.2015.03.pp.028-032

Махорин А. О., Падалко С. Н., Терентьев М. Н.
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ МНОГОШЛЮЗОВОЙ БЕСПРОВОДНОЙ САМООРГАНИЗУЮЩЕЙСЯ СЕТИ ПРОИЗВОЛЬНОЙ ТОПОЛОГИИ В АЭРОКОСМИЧЕСКОЙ СИСТЕМЕ
(с. 28-32)

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

Ключевые слова: многошлюзовая беспроводная самоорганизующаяся сеть; система мониторинга; маршрути-зация; самоорганизация; математическая модель.

Makhorin A. O., Padalko S. N., Terentiev M. N.
MATHEMATICAL MODEL OF MULTI-GATEWAY WIRELESS AD HOC NETWORK FOR AEROSPACE SYSTEM
(pp. 28-32)

Abstract. This article presents principles of functioning and a related problem of message routing in a monitoring system based on a multi-gateway wireless ad hoc network used in aerospace systems. One of key ideas proposed by the authors is to formulate the message routing problem which has combinatorial nature as a general 0-1 linear programming model that allows solving it with existing powerful state-of-the-art solvers like ILOG CPLEX or IBM OSL. Most approaches used today to solve similar problems are based mainly on heuristic algorithms, so any change in the problem formulation (e.g. adding some extra specific constraints) makes the heuristics inappropriate. Unlike that the proposed approach has the advantage that new constraints can be introduced into the formulation easily and do not affect the solver. In the article only a general optimization framework is discussed to illustrate how to formulate essential constraints specific to the message routing problem in a 0-1 linear programming format. The optimization model is based on a flow single-commodity network, where source, conservative, and sink nodes model, respectively, sensors, routers, and receivers of a multi-gateway wireless ad hoc network. The essential constraints includes: conservative constraints that model data flows between nodes, role constraints that model possible changes in the role of every node, geometric constraints that model the network topology, and cover constraints that model the monitoring area. It is well known that introducing general (non-binary) integer variables makes the model much more difficult to solve with branch-and-bound-based solvers, so to get rid of such variables as well as non-linear inequalities that appear due to geometric and cover constraints a standard technique based on Tseitin's transformation is applied.

Keywords: Multi-gateway wireless ad hoc network; Monitoring system; Message routing; Self-organization; Mathematical model.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

А. О. Махорин, С. Н. Падалко, М. Н. Терентьев (Московский авиационный институт (национальный исследовательский университет)) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

A. O. Makhorin, S. N. Padalko, M. N. Terentiev (Moscow Aviation Institute (National Research University) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Непрерывный круглосуточный медицинский контроль психофизиологического состояния и координат космонавтов с использованием беспроводной сенсорной сети / С. М. Макарова и др. // Вестник Московского авиационного института. 2012. Т. 19, № 2. С. 177 – 181.
2. Падалко С. Н., Терентьев М. Н. Автоматизи-рованное проектирование адаптивных дискретных бес-проводных сенсорных сетей для космических систем. М.: Изд-во МАИ, 2013. 128 с.
3. Papadimitriou I., Georgiadis L. Minimum-energy Broadcasting in Wireless Networks // Mobile Networks and Applications. 2006. V. 11, N 3. P. 361 – 375.
4. Alzoubi K. M., Wan P.-J., Frieder O. Distributed Heuristics for Connected Dominating Sets in Wireless ad Hoc Networks // Journal of Communications and Networks. 2002. V. 4, N 1. P. 22 – 29.
5. ILOG CPLEX 11.0 User's Manual. ILOG S. A., 2008. 532 p.
6. Optimization Subroutine Library Guide and Refer-ence SC23-0519. IBM Corp., 2001.
7. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984. 496 с.
8. Татт У. Теория графов. М.: Мир, 1988. 424 с.
9. Tseitin G. S. On the Complexity of Derivation in Propositional Calculus // Studies in Constructive Mathemat-ics and Mathematical Logic. 1968. V. 2. P. 56 – 62.

Eng

1. Makarova S. M., Padalko S. N., Strogonova L. B., Terent'ev M. N. (2012). Continuous medical monitoring of psychophysiological state and coordinate astronauts using wireless sensor networks. Vestnik Moskovskogo aviatsionnogo instituta, 19(2), pp. 177-181.
2. Padalko S. N., Terent'ev M. N. (2013). Automated design of adaptive discrete wireless sensor networks for space systems. Moscow: Izdatel'stvo MAI.
3. Papadimitriou I., Georgiadis L. (2006). Minimum-energy broadcasting in wireless networks.Mobile Networks and Applications, 11(3), pp. 361-375. doi: 10.1007/s11036-006-5189-6
4. Alzoubi K. M., Wan P.-J., Frieder O. (2002). Dis-tributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Net-works, 4(1), pp. 22-29. doi: 10.1109/JCN.2002.6596929
5. ILOG CPLEX 11.0 User's Manual. (2008). ILOG S. A.
6. Optimization Subroutine Library Guide and Refer-ence SC23-0519. (2001). IBM Corp.
7. Fillips D., Garsia-Dias A. (1984). Methods of net-works analysis. Moscow: Mir.
8. Tatt U. (1988). Graph theory. Moscow: Mir.
9. Tseitin G. S. (1968). On the complexity of derivation in propositional calculus. Studies in Constructive Mathematics and Mathematical Logic, 2, pp. 56-62.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

DOI: 10.14489/vkit.2015.03.pp.028-032

Скопируйте DOI статьи и перейдите по ссылке https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

В комментарии к заказу обязательно укажите DOI статьи.

Eng

This article is available in electronic format (PDF).

DOI: 10.14489/vkit.2015.03.pp.028-032

Copy the article DOI and follow the link https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

Please specify the article DOI in the order comments.