maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2015-4-546-562mais-272Research ArticleОригинальные статьиArticlesИнструментальная система для поддержки разработки и исследования программно-конфигурируемых сетей подвижных объектовInstrumental Supporting System for Developing and Analysis of Software-Defined Networks of Mobile ObjectsСоколовВ. А.SokolovV. A.

докт. физ.-мат. наук., профессор, заведующий кафедрой теоретической информатики

ул. Советская, 14, г. Ярославль, 150000 Россия

 Doctor, Professor

Sovetskaya str., 14, Yaroslavl, 150000, Russia

valery-sokolov@yandex.ruКорсаковС. В.KorsakovS. V.

ул. Белинского, 28-75, г. Ярославль, 150047 Россия ассистент кафедры теоретической информатики

ул. Советская, 14, г. Ярославль, 150000 России ассистент кафедры теоретической информатики

 Belinskogo str., 28-75, Yaroslavl, 150047, Russia

Assistant Professor Sovetskaya str., 14, Yaroslavl, 150000, Russia

sta@stasoft.netСмирновА. В.SmirnovA. V.

канд. физ.-мат. наук., доцент кафедры теоретической информатики

ул. Советская, 14, г. Ярославль, 150000 Россия

Associate Professor

Sovetskaya str., 14, Yaroslavl, 150000, Russia

alexander_sm@mail.ruБашкинВ. А.BashkinV. A.

докт. физ.-мат. наук., доцент, доцент кафедры теоретической информатики

ул. Советская, 14, г. Ярославль, 150000 Россия

Associate Professor

Sovetskaya str., 14, Yaroslavl, 150000, Russia

v_bashkin@mail.ruНикитинЕ. С.NikitinE. S.

студент

ул. Советская, 14, г. Ярославль, 150000 Россия

student

Sovetskaya str., 14, Yaroslavl, 150000, Russia

nik.zhenya@gmail.comЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian FederationООО Нетше лабб Ярославский государственный университет им. П.Г. ДемидоваРоссияCEO, NETSHe Lab Ltd P.G. Demidov Yaroslavl State UniversityRussian Federation201520082015224546562Copyright © Соколов В.А., Корсаков С.В., Смирнов А.В., Башкин В.А., Никитин Е.С., 20152015Соколов В.А., Корсаков С.В., Смирнов А.В., Башкин В.А., Никитин Е.С.Sokolov V.A., Korsakov S.V., Smirnov A.V., Bashkin V.A., Nikitin E.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/272

В данной статье рассмотрены принципы организации беспроводных mesh-сетей  программно-конфигурируемых сетей подвижных объектов. Основное внимание уделяется вопросам построения эффективных алгоритмов маршрутизации для подобных сетей. Математической моделью системы является стандартная транспортная сеть. В качестве ключевого параметра системы маршрутизации рассматривается коэффициент доступности узла  функция, зависящая от ряда основных и дополнительных параметров ((mesh-факторовв), характеризующих маршрут между двумя узлами сети. Каждой паре (дуга, узел) сопоставляется композитный параметр, характеризующий 裂доступностьь узла по маршруту, начинающемуся данной дугой. Лучшим ((кратчайшимм) маршрутом между двумя узлами считается маршрут с наибольшим коэффициентом доступности. Описаны правила построения и обновления таблиц маршрутизации узлами сети. Получая анонс от соседа, узел имеет сведения об энергетике соединения, надежности соединения, времениполучения анонса, отсутствии промежуточных узлов, а также располагаемой пропускной способности. На основании этой информации ко всем маршрутам, проходящим через данного соседа, может быть применена пенализация (наложение штрафа) или поощрение (увеличение коэффициента доступности). Указанная схема пенализации / поощрения складывается из отдельных аспектов:1. Пенализация за актуальность информации.2. Пенализация / вознаграждение за надежность узла.3. Пенализация за энергетику соединения.4. Пенализация за располагаемую пропускную способность.На основе предложенных эвристических алгоритмов маршрутизации построен симулятор беспроводной mesh-сети подвижных объектов, описание и характеристики которого приведены в статье. Также рассмотрены особенности программной реализации симулятора.

This article describes the organization principles for wireless mesh-networks (software-defined net-works of mobile objects). The emphasis is on the questions of getting effective routing algorithms for such networks. The mathematical model of the system is the standard transportation network. The key parameter of the routing system is the node reachability coefficient — the function depending on several basic and additional parameters (“mesh-factors”), which characterize the route between two network nodes. Each pair (arc, node) is juxtaposed to a composite parameter which characterizes the “reacha-bility” of the node by the route which begins with this arc. The best (“shortest”) route between two nodes is the route with the maximum reachability coefficient. The rules of building and refreshing the routing tables by the network nodes are described. With the announcement from the neighbor the node gets the information about the connection energy and reliability, the announcement time of receipt, the absence of transitional nodes and also about the connection capability. On the basis of this informationthe node applies the penalization (decreasing the reachability coefficient) or the reward (increasing the reachability coefficient) to all routes through this neighbor node. The penalization / reward scheme has some separate aspects: 1. Penalization for the actuality of information. 2. Penalization / reward for the reliability of a node. 3. Penalization for the connection energy. 4. Penalization for the present connection capability. The simulator of the wireless mesh-network of mobile objects is written. It is based on the suggested heuristic algorithms. The description and characteristics of the simulator are stated in the article. The peculiarities of its program realization are also examined.

mesh-сетьсетевой протоколмаршрутизацияпенализацияэвристический алгоритмсимуляторmesh-networknetwork protocolroutingpenalizationheuristic algorithmsimulatorReferences“B.A.T.M.A.N. Advanced Documentation Overview”, 2014, http://www.open-mesh.org/projects/batman-adv/wiki.“B.A.T.M.A.N. Advanced Documentation Overview”, 2014, http://www.open-mesh.org/projects/batman-adv/wiki.Conner W. S. et al., “IEEE 802.11s Tutorial”, 2006, http://www.ieee802.org/802 tutorials/06-November/802.11s Tutorial r5.pdf.Conner W. S. et al., “IEEE 802.11s Tutorial”, 2006, http://www.ieee802.org/802 tutorials/06-November/802.11s Tutorial r5.pdf.“Mobile Mesh Networks for Military, Defense and Public Safety”, 2015, http://meshdynamics.com/military-mesh-networks.html.“Mobile Mesh Networks for Military, Defense and Public Safety”, 2015, http://meshdynamics.com/military-mesh-networks.html.Shen W. L. et al., “Autonomous Mobile Mesh Networks”, IEEE Transactions on Mobile Computing, 13:2 (2014), 364–376.Shen W. L. et al., “Autonomous Mobile Mesh Networks”, IEEE Transactions on Mobile Computing, 13:2 (2014), 364–376.Boukerche A. et al., “Routing protocols in ad hoc networks: A survey”, Computer Networks, 55:13 (2011), 3032–3080.Boukerche A. et al., “Routing protocols in ad hoc networks: A survey”, Computer Networks, 55:13 (2011), 3032–3080.Broch J. et al., “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols”, Proc. of ACM/IEEE International Conference on Mobile Computing and Networking, 1998, 85–97.Broch J. et al., “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols”, Proc. of ACM/IEEE International Conference on Mobile Computing and Networking, 1998, 85–97.Servetto S.D., Barrenechea G., “Constrained Random Walks on Random Graphs: Routing Algorithms for Large Scale Wireless Sensor Networks”, Proc. of 1st ACM International Workshop on Wireless Sensor Networks and Applications, 2002, 12–21.Servetto S.D., Barrenechea G., “Constrained Random Walks on Random Graphs: Routing Algorithms for Large Scale Wireless Sensor Networks”, Proc. of 1st ACM International Workshop on Wireless Sensor Networks and Applications, 2002, 12–21.Nelakuditi S. et al., “Adaptive Proportional Routing: A Localized QoS Routing Approach”, IEEE/ACM Transactions on Networking, 10:6 (2002), 790–804.Nelakuditi S. et al., “Adaptive Proportional Routing: A Localized QoS Routing Approach”, IEEE/ACM Transactions on Networking, 10:6 (2002), 790–804.Baumann R. et al., “Routing in Large-Scale Wireless Mesh Networks Using Temperature Fields”, IEEE Network, 2008, 25–31.Baumann R. et al., “Routing in Large-Scale Wireless Mesh Networks Using Temperature Fields”, IEEE Network, 2008, 25–31.Cormen T. H. et al., Introduction to Algorithms, MIT Press, 2009.Cormen T. H. et al., Introduction to Algorithms, MIT Press, 2009.Perkins Ch. E. et al., “Performance Comparison of Two On-demand Routing protocols for Ad Hoc Networks”, IEEE Personal Communications, 2001, 16–28.Perkins Ch. E. et al., “Performance Comparison of Two On-demand Routing protocols for Ad Hoc Networks”, IEEE Personal Communications, 2001, 16–28.Awerbuch B. et al., “On the Survivability of Routing Protocols in Ad Hoc Wireless Networks”, CERIAS Tech Report 2005–121, 2005.Awerbuch B. et al., “On the Survivability of Routing Protocols in Ad Hoc Wireless Networks”, CERIAS Tech Report 2005–121, 2005.Nelakuditi S., Zhang Zh.-L., “On Selection of Paths for Multipath Routing”, Proc. of IWQoS, 2001, 170–186.Nelakuditi S., Zhang Zh.-L., “On Selection of Paths for Multipath Routing”, Proc. of IWQoS, 2001, 170–186.Nguyen Ph. H. et al., “Distributed routing algorithms to manage power flow in agent-based active distribution network”, Innovative Smart Grid Technologies Conference Europe (ISGT Europe), IEEE PES, 2010, 1–7.Nguyen Ph. H. et al., “Distributed routing algorithms to manage power flow in agent-based active distribution network”, Innovative Smart Grid Technologies Conference Europe (ISGT Europe), IEEE PES, 2010, 1–7.Brunsch T. et al., “Smoothed Analysis of the Successive Shortest Path Algorithm”, 2015, arXiv: 1501.05493v1.Brunsch T. et al., “Smoothed Analysis of the Successive Shortest Path Algorithm”, 2015, arXiv: 1501.05493v1.Spielman D. A., Teng Sh.-H., “Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time”, Journal of the ACM, 51:3 (2004), 385–463.Spielman D. A., Teng Sh.-H., “Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time”, Journal of the ACM, 51:3 (2004), 385–463.

The authors declare that there are no conflicts of interest present.