автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Анализ и разработка алгоритмов управления и обработки информации в распределенных сетях датчиков

Введение.

Глава 1. Обзор существующих разработок в области РСД.

1.1 Задачи, решаемые РСД.

1.2 Способы построения РСД.

1.3 Обзор работ в области РСД.

1.4 Постановка задачи диссертационной работы.

1.5 Выводы.

Глава 2. Математическая модель РСД и ее функциональная декомпозиция.

2.1 Анализ интенсивности трафика в РСД.

2.2 Характеристики работы узлов РСД.

2.3 Характеристики качества обслуживания, предоставляемого РСД.

2.4 Энергетические характеристики и время работы РСД.

2.5 Выводы.

Глава 3. Архитектура РСД, осуществляющей распределенный мониторинг параметрического поля.

3.1 Общая структура РСД.

3.2 Алгоритм прикладного уровня.

3.3 Протокол маршрутизации.

3.4 Протокол канального уровня.

3.5 Протокол уровня доступа к среде.

3.6 Алгоритм обработки собираемых РСД данных.

3.7 Выводы.

Глава 4. Исследование РСД методом имитационного моделирования.

4.1 Построение имитационной модели РСД.

4.2 Идентификация модели канала связи.

4.3 Экспериментальная проверка математической модели РСД.

Актуальность работы.

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

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

Построение системы мониторинга территориально-распределенных характеристик представляет собой достаточно непростую задачу. Измерение 5 значений наблюдаемой характеристики, изменяющейся как в пространстве, так и во времени, может порождать значительный поток информации, которая должна быть доставлена оператору. Сеть, объединяющая устройства по сбору информации и являющаяся неотъемлемой частью системы мониторинга территориально-распределенной системы, должна обеспечивать надежную и своевременную доставку этой информации от наблюдаемой системы к оператору. Дополнительную сложность вносит то обстоятельство, что во многих системах, особенно природных, затруднительно либо вовсе невозможно подготовить инфраструктуру для построения такой сети. Все эти факторы обуславливают интерес исследователей в данной области к распределенным, безынфраструктурным системам сбора, доставки и обработки информации.

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

Цель работы.

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

В данной работе поставлены и решены следующие задачи:

1. Получение выражений для нахождения интенсивности потоков передаваемой в РСД информации;

2. Получение выражений для нахождения временных характеристик работы РСД и характеристик качества предоставляемого ею обслуживания;

3. Получение выражений для нахождения энергетических характеристик работы РСД и времени ее работы;

4. Разработка системы имитационного моделирования РСД;

5. Изучение различных вариантов построения РСД и эффекта от их применения. 7

Методы исследования.

Для решения поставленных задач использовался математический аппарат теории систем массового обслуживания, теории графов, а также имитационное моделирование на ЭВМ.

Научная новизна.

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

Практическая ценность.

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

Апробация работы.

Основные результаты работы были представлены на:

- конференции КОГРАФ-2001 (г. Нижний Новгород, 2001);

- третьей всероссийской научно-практической конференции «Современные проблемы создания и эксплуатации радиотехнических систем» (г. Ульяновск, 2001);

- седьмой нижегородской сессии молодых ученых (технические науки) (г. Нижний Новгород, 2002);

- региональном молодежном научно-техническом форуме «Будущее технической науки нижегородского региона» (г. Нижний Новгород, 2002);

- международной российско-германской конференции «Датчики и системы» (г. Санкт-Петербург, 2002).

Публикации.

Основное содержание диссертации отражено в 9 печатных работах [19].

Положения, выносимые на защиту.

1. Математическая модель РСД, осуществляющей мониторинг территориально-распределенной характеристики наблюдаемой системы;

2. Методика расчета характеристик работы РСД на основании ее параметров и характера изменения наблюдаемой величины;

3. Результаты экспериментального анализа на базе имитационного моделирования эффекта от применения в РСД различных протоколов и алгоритмов.

Структура и объем работы.

Текст диссертационной работы состоит из введения, четырех глав,

4.5 Выводы

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

Далее, в данной главе была осуществлена проверка математической модели РСД, построенной в главе 2. Для этого результаты моделирования сопоставлялись с результатами расчетов по полученным в главе 2 выражениям для ряда характеристик работы РСД, включая:

- интенсивность трафика, обслуженного в моноканале РСД;

- среднюю задержку передачи сообщения на одном шаге маршрутизации;

- среднее время доставки извещения стоку;

- СКО значений НВ;

- остаточный уровень энергии сенсорных узлов;

- средний уровень энергии узлов сети;

- степень покрытия сетью обслуживаемой территории.

На основании сопоставления результатов моделирования и расчетных значений было сделано заключение о точности определения значений перечисленных характеристик с помощью построенной в настоящей работе математической модели РСД и о границах применимости данной модели.

221

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

222 Заключение

Настоящая диссертационная работа посвящена изучению распределенной сети датчиков (РСД), осуществляющей территориально-распределенный мониторинг значений наблюдаемой величины (НВ).

В ходе выполнения данной диссертационной работы были получены следующие результаты:

- выполнена функциональная декомпозиция РСД, осуществляющей территориально-распределенный мониторинг значений НОВ, основанная на пространственно непрерывной модели характеристик РСД;

- построена математическая модель рассматриваемой РСД, ориентированная на быстрый расчет характеристик ее работы -интенсивности порожденного, переданного и обслуженного трафика, различных задержек при передаче сообщений, времени доставки информации от сенсорных узлов к стокам, СКО воссозданных на стороне оператора значений НВ от ее реальных значений, энергопотребления сенсорных узлов, покрытия сетью обслуживаемой территории, времени работы сети и ряда других величин;

- построены математические модели протокола доступа к среде С8МА с механизмом предотвращения синхронизации потоков сообщений, алгоритма адаптивного управления скоростью передачи узла и алгоритма периодического отключения приемопередатчика узла с ожиданием готовности узла-получателя сообщения к приему, и получены выражения для расчета характеристик их работы;

- построенная математическая модель РСД реализована в виде набора функций в среде МАТЬАВ;

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

223 коммуникационных протоколов и алгоритм обработки данных, собираемых РСД; создана система имитационного моделирования, реализующая разработанную архитектуру РСД и позволяющая проанализировать исчерпывающий набор ее характеристик и исследовать разнообразные эффекты, возникающие при работе РСД, как предусмотренные ее математической моделью, так и не предусмотренные ею (в том числе эффект от применения различных усовершенствований протоколов и алгоритмов РСД); построена математическая модель канала связи РСД, использующей предложенные коммуникационные протоколы, и определено оптимальное значение содержащегося в ней эмпирического параметра, обеспечивающее минимум СКО расчетных значений пропускной способности канала от результатов моделирования; осуществлена проверка математической модели РСД путем сопоставления результатов моделирования с результатами расчетов по полученным выражениям для промежуточных и результирующих характеристик работы РСД; определены границы применимости математической модели РСД по ряду наиболее важных параметров - плотности размещения сенсорных узлов, числу узлов в моноканале и интенсивности переданного трафика; исследован ряд аспектов работы РСД, не учитываемых ее математической моделью, включая эффект от применения различных усовершенствований протоколов и алгоритмов, и даны рекомендации по их использованию.

1. Зайцев И.В. Анализ распределенной сети датчиков // КОГРАФ-2001: Тез. докл. Н.Новгород, 2001.

2. Зайцев И.В. Самоорганизующаяся беспроводная распределенная сеть датчиков // Труды третьей всероссийской научно-практической конференции «Современные проблемы создания и эксплуатации радиотехнических систем». Ульяновск, 2001. - С. 25-28.225

3. Зайцев И.В. Масштабируемый протокол маршрутизации для распределенных сетей датчиков // Тез. докл. регионального молодежного научно-технического форума «Будущее технической науки нижегородского региона». Н.Новгород, 2002. - С. 70.

4. Зайцев И.В. Построение энергетически эффективных беспроводных сетей датчиков в задачах мониторинга параметрических полей // Труды международной российско-германской конференции «Датчики и системы». Санкт-Петербург, 2002. - Т. 3, С. 72-76.

5. Elson J., Estrin D. Time synchronization for wireless sensor networks // Proceedings of the 15th International Parallel and Distributed Processing Symposium, San Francisco, California, April 2001, pp. 1965-1970.

6. Rentala P., Musunuri R., Gandham S., Saxena U. Survey on sensor networks. Department of Computer Science, University of Texas at Dallas, Richardson, 2001.

7. Sohrabi K., Gao J., Ailawadhi V., Pottie G.J. Protocols for self-organization of a wireless sensor network // IEEE Personal Communications, October 2000, Volume 7, Issue 5, pp. 16-27.

8. Estrin D., Girod L., Pottie G., Srivastava M. Instrumenting the world with wireless sensor networks // Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, Salt Lake City, Utah, May 2001, pp. 2033-2036.

9. Kahn J.M., Katz R.H., Pister K.S.J. Next century challenges: Mobile networking for smart dust // Proceedings of the 5th annual ACM/IEEE2261.ternational Conference on Mobile Computing and Networking, Seattle, Washington, August 1999, pp. 483-492.

10. Shih E., Cho S.-H., Ickes N., Min R., Sinha A., Wang A., Chandrakasan A. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks // Proceeding of ACM SIGMOBILE Conference, Rome, Italy, July 2001, pp. 272-286.

11. Savvides A., Han C.-C., Srivastava M.B. Dynamic fine-grained localization in ad-hoc networks of sensors // Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking, Rome, Italy, July 2001, pp. 166-179.

12. Misra P. Routing protocols for ad hoc mobile wireless networks. http://www.cis.ohio-state.edu/~jain/cis788-99/adhocrouting/index.html

13. Ye F., Chen A., Liu S., Zhang L. A scalable solution to minimum cost forwarding in large sensor networks // Proceedings of Tenth International Conference on Computer Communications and Networks, Phoenix, Arizona, October 2001, pp. 304-309.

14. Banerjee S., Khuller S. A clustering scheme for hierarchical control in multi-hop wireless networks // Proceedings of IEEE INFOCOM 2001 Conference, Anchorage, Alaska, April 2001, vol. 2, pp. 1028-1037.

15. Ramanathan R., Steenstrup S. Hierarchically organized, multihop mobile wireless networks for quality-of-service support // Mobile Networks and Applications, June 1998, vol. 3, no. 1, pp. 101-119.

16. Tanenbaum A. Computer networks. Prentice Hall, New Jersey, 1981.

17. Rappaport T.S. Wireless communications: principles and practice. Prentice Hall, New Jersey, 1996.

18. Kleinrock L., Tobagi F. Packet switching in radio channels, part 1 : Carrier sense multiple-access models and their throughput-delay characteristics // IEEE Transactions on Communications, COM-23, 1975, pp. 1400-1416.

19. Tobagi F., Kleinrock L. Packet switching in radio channels, part 2: Hidden-terminal problem in carrier sense multiple access and the busy-tone solution // IEEE Transactions on Communications, COM-23, 1975, pp. 1417-1433.

20. Bharghavan V., Demers A., Shenker S., Zhang L. MACAW: A media access protocol for wireless LANs // Proceedings of ACM SIGCOMM Conference, London, UK, August 1994, pp. 212-225.

21. Fullmer C., Garcia-Luna-Aceves J.J. Floor Acquisition Multiple Access (FAMA) for Packet Radio Networks // Proceedings of ACM SIGCOMM Conference, Cambridge, Massachusetts, August 1995, pp. 262-273.

22. Fullmer C., Garcia-Luna-Aceves J.J. Solutions to Hidden Terminal Problems in Wireless Networks // Proceedings of ACM SIGCOMM Conference, Cannes, France, September 1997, pp. 39-49.

23. Singh S., Raghavendra C. PAMAS power aware multi-access protocol with signalling for ad hoc networks // ACM Computer Communication Review, July 1998, vol. 28, no. 3, pp. 5-26.228

24. Singh S., Woo M., Raghavendra C. Power-aware routing in mobile ad hoc networks // Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking, Dallas, Texas, October 1998, pp. 181-190.

25. ANSI/IEEE Std 802.11 1999 Edition.

26. Bluetooth, http://www.bluetooth.com

27. Stemm M., Katz R. Measuring and reducing energy consumption of network interfaces in hand-held devices // IEICE Transactions on Communications, 1997, vol. E80-B, no. 8, pp. 1125-1131.

28. Woo A., Culler D. A transmission control scheme for media access in sensor networks // Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking, Rome, Italy, July 2001, pp. 221-235.

29. Ye W., Heidemann J., Estrin D. An energy-efficient MAC protocol for wireless sensor networks // Proceedings of IEEE INFOCOM Conference, New York, June 2002.

30. Kasten O. Energy consumption model. Eidgenossische Technische Hochschule Zurich.

31. Doherty L. Algorithms for position and data recovery in wireless sensor networks. Research Project, Dept. of Electrical Engineering and Computer Sciences, University of California, Berkeley, 2000.

32. Savarese C., Rabaey J., Beutel J. Locationing in distributed ad-hoc wireless sensor networks // Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, Salt Lake City, Utah, May 2001, pp. 2037-2040.

33. Girod L., Estrin D. Robust range estimation using acoustic and multimodal sensing // Proceedings of IEEE/RSI International Conference on Intelligent Robots and Systems (IROS 2001), Maui, Hawaii, October 2001.

34. Meguerdichian S., Slijepcevic S., Karayan V., Potkonjak M. Localized algorithms in wireless ad-hoc networks: location discovery and sensor exposure // Proceedings of ACM International Symposium on Mobile Ad Hoc229

35. Networking and Computing, Long Beach, California, October 2001, pp. 106116.

36. Bhardwaj M., Garnett T., Chandrakasan A. Upper bounds on the lifetime of sensor networks // Proceedings of IEEE International Conference on Communications, Helsinki, Finland, June 2001, pp. 785-790.

37. Fortune S. Voronoi diagrams and Delaunay triangulations. Computing in Euclidean Geometry, 2nd edition, edited by D.Z. Du and F. Hwang, World Scientific, Singapore, 1995, pp. 225-265.

38. Nandagopal T., Kim T., Gao X., Bharghavan V. Achieving MAC layer fairness in wireless packet networks // Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking, Boston, Massachusetts, August 2000, pp. 87-98.

39. ComNet III. http://www.caci.com

40. Artifex. http://www.artis-software.com

41. Fall K., Varadhan K., editors, ns notes and documentation. The VINT project, UC Berkeley, LBL, USC/ISI, and Xerox PARC, November 1997. http://www.mach.cs.berkeley.edu/ns/

42. The CMU Monarch project's wireless and mobility extension to ns. The CMU Monarch Project, School of Computer Science, Carnegie Mellon University. http://www.monarch.cs.cmu.edu

43. Perrone F., Nicol D., Liu J., Elliot C., Pearson D. Simulation modeling of large-scale ad-hoc sensor networks // Proceedings of 2001 Simulation Interoperability Workshop, London, UK, June 2001.