Управление передачей пакетов в сенсорных сетях тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Линский, Евгений Михайлович

• Линский, Евгений Михайлович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Линский, Евгений Михайлович

Введение

1 Постановка задачи

1.1 Сенсорные сети.

1.2 Анализ источников ненадежности при передаче пакетов.

1.2.1 Искажение пакетов.

1.2.2 Вброс пакетов в сеть.

1.2.3 Удаление пакетов из сети.

1.2.4 Выводы.

1.3 Модель сенсорной сети.

1.4 Алгоритм передачи, учитывающий требования надежности, экономичности и оперативности

1.5 Оптимизационная задача управления передачей пакетов

1.6 Выводы.

2 Передача с дублированием пакетов

2.1 Оптимизационные соотношения

2.2 Решение алгоритмом динамического программирования.

2.3 Решение алгоритмом ветвей и границ.

2.4 Применение гибридного алгоритма.

2.5 Результаты моделирования.

2.5.1 Передача штатных сообщений

2.5.2 Передача срочных сообщений.

2.6 Выводы.

3 Передача с кодированием пакетов

3.1 Применение кодов Рида-Соломона.

3.2 Оптимизационные соотношения

3.3 Решение методом ветвей и границ.

3.4 Решение алгоритмом локального поиска.

3.5 Применение гибридного алгоритма.

3.6 Результаты моделирования.

3.7 Выводы.

4 Сравнение алгоритмов передачи и учет критерия живучести

4.1 Сравнение адаптивной и неадаптивной передачи.

4.1.1 Анализ для двух маршрутов.

4.1.2 Анализ для N маршрутов.

4.2 Учет критерия живучести сети.

4.2.1 Определение критерия живучести сети.

4.2.2 Алгоритм контроля живучести.

4.3 Выводы.

Введение диссертации (часть автореферата) на тему «Управление передачей пакетов в сенсорных сетях»

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

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

Каждый сенсор — это устройство, состоящее из пяти базовых компонент: датчик, процессор, память, беспроводной передатчик и источник питания. Ресурс источника питания обычно ограничен, что фактически определяет время жизни сенсора, тесно связано с его вычислительными возможностями и влияет на мощность передатчика.

В настоящее время сфера применения сенсорных сетей довольно обширна [1], [2]: мониторинг окружающей среды и среды естественного обитания, раннее диагностирование поломок устройств в промышленности, управление дорожным движением, контроль за безопасностью объектов.

Целью протокола передачи пакетов является надежная доставка сообщений по маршрутам, построенным протоколом маршрутизации, как между сенсорами и базовой станцией, так и между отдельными сенсорами. В данной диссертационной работе рассматриваются протоколы передачи пакетов, качество которых оценивается с учетом следующих критериев: надежность (вероятность доставки), оперативность (время доставки), экономичность (энергозатраты). Основным источником ненадежности являются компрометированные узлы, удаляющие пересылаемые через них пакеты.

Основной целью работы является разработка и исследование алгоритмов, которые управляют передачей пакетов в сенсорной сети.

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

Научная новизна диссертационной работы заключается в следующем.

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

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

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

4. Разработан алгоритм контроля живучести сети при использовании алгоритма АИП. Этот алгоритм позволяет увеличить срок жизни сети по сравнению с аналогами.

Практическая ценность и реализация результатов. Практическая ценность работы определяется тем, что предложенный алгортитм адаптивной избыточной передачи пакетов способствует как повышению надежности передачи, так и понижению энергозатрат сети.

Публикации. Материалы, отражающие основное содержание и результаты диссертационной работы, опубликованы в 5 печатных работах ([3, 4, 5, 6, 7]). В том числе 2 работы [5, 7] опубликованы в журналах, реферируемых ВАК.

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

1. Алгоритм адаптивной избыточной передачи пакетов для сенсорной сети.

2. Алгоритм нахождения оптимальных параметров алгоритма АИП при передаче однопакетных сообщений, учитывющий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у других алгоритмов.

3. Алгоритм нахождения оптимальных параметров алгоритма АИП при передаче многопакетных сообщений, учитывющий ограничения на максимальную вычислительную сложность и обеспечивающий выигрышщ по этому параметру у других алгоритмов.

4. Алгоритм контроля живучести сенсорной сети, увеличивающий срок жизни сети по сравнению с аналогами.

Объем и структура работы. Диссертационная работа состоит из введения, 4 разделов, заключения и списка использованных источников.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Линский, Евгений Михайлович

Основные результаты данной диссертационной работы могут быть сформулированы следующим образом.

1. Разработан алгоритм адаптивной избыточной передачи (АИП), учитывающий требования надежности, экономичности и оперативности. В отличие от существующих алгоритмов предложенный алгоритм учитывает характеристики используемых маршрутов. Предложенный алгоритм существенно выгоднее по энергопотреблению, чем существующие аналоги.

2. Разработаны следующие алгоритмы настройки параметров управления передачей пакетов. a) Алгоритм нахождения оптимальных параметров АИП для однопакетных сообщений, учитывающий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у аналогов. b) Алгоритм нахождения оптимальных параметров АИП для многопакетных сообщений, учитывающий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у аналогов. с) Алгоритм контроля живучести сети при использовании АИП, увеличивающий срок жизни сети по сравнению с аналогами.

Заключение

В данной работе рассматривалась задача управления надежной передачей пакетов в сенсорной сети в присутствии компрометированных узлов, выбрасывающих передаваемые через них пакеты. Была рассмотрена передача трех типов сообщений: штатных однопакетных, срочных однопакетных и многопакетных.

Список литературы диссертационного исследования кандидат технических наук Линский, Евгений Михайлович, 2007 год

1. Chee-Yee Ghong and Srikanta P.Kumar. Sensor networks: Evolution, opportunities, and challenges. March 2003.

2. Алекс Карабуто. "Сенсорные сети: как скоро?". 25 августа 2004 года.

3. Е.М. Линский, Г.С. Евсеев. "Расчет параметров алгоритма гарантированной доставки для сенсорных сетей". Фонд алгоритмов и программ, инвентарный номер ВНТИЦ 50200601922, 2006.

4. Е. М. Линский. "К вопросу об управлении передачей в сенсорных сетях". Сборник докладов научной сессии аспирантов ГУАП 2007, Санкт-Петербург, 2007.

5. Е. М. Линский. "К вопросу об управлении передачей пакетов в сенсорных сетях". Системы управления и информационные технологи, №2.2(28), 2007.

6. Е. Linsky and G. S. Evseev. Reliable packet transmission for sensor networks. In Proceedings of XI international symposium on problems of redundancy in information and control systems, 2007.

7. Е.М. Линский, Г.С. Евсеев. "Сравнение протоколов адаптивной и неадаптивной передачи пакетов для сенсорной сети". Информационно-управляющие системы, №5 , Санкт-Петербург, 2007.

8. J. M. Kahn, R. H. Katz, and K. S. J. Pister. Mobile networking for smart dust. In MobiCom, 1999.

9. Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci. A survey on sensor networks. August 2002.

10. Shamila Makki, Niki Pissinou, and Tirthankar Bhowmick. Leach protocol for assigning cluster-heads using a deterministic and stochastic approach for wireless sensor networks. In International Conference on Wireless Networks, pages 963-968, 2004.

11. Matthias Lott, Alexey Sitalov, Evgeny Linsky, , and Hui L. Performance analysis of multicast transmission in wlan. In In Vehicular Technology Conference. VTC 2003-Spring. The 57th IEEE Semiannual, pages 12231227, April 2003.

12. Lingxuan Hu and David Evans. Secure aggregation for wireless networks. In SAINT-W '03: Proceedings of the 2003 Symposium on Applications and the Internet Workshops (SAINT'03 Workshops), page 384, Washington, DC, USA, 2003.

13. Bartosz Przydatek, Dawn Xiaodong Song, and Adrian Perrig. Sia: secure information aggregation in sensor networks. In SenSys, pages 255-265, 2003.

14. А.Д. Фомин. "Распределенная верификация результата агрегации данных в сенсорных сетях". Программные продукты и системы, №2, 2007.

15. Panagiotis Papadimitratos, Zygmunt J. Haas, and Emin Sirer. Path set selection in mobile ad hoc networks. In MobiHoc '02: Proceedings of the 3rd A CM international symposium on Mobile ad hoc networking & computing, pages 1-11, New York, NY, USA, 2002.

16. E. M. Линский. "Сравнение производительности протоколов маршрутизации в ad hoc сетях". Труды конференции БИКАМП'ОЗ, Санкт-Петербург, Россия, 2003.

17. С. Karlof and D. Wagner. Secure routing in wireless sensor networks: Attacks and countermeasures. August 2002.

18. Adrian Perrig, Robert Szewczyk, J. D. Tygar, Victor Wen, and David E. Culler. Spins: security protocols for sensor networks. Wirel. Netw., 8(5):521-534, 2002.

19. S. Bezzateev, E.Jung, E. Krouk, К. H. Lee, and E. Linsky. Subcodes of goppa codes for multi-level access control systems. In Proceedings of NEW2AN'04, St. Petersburg, Russia, 2004.

20. E. M. Линский. "Использование одного класса кодов Гоппы для организации системы многоуровневого доступа к информации". In Сборник докладов научной сессии аспирантов ГУАП 2004, Санкт-Петербург, 2004.

21. E. Linsky and E. Krouk. LDPC Code Based Cryptosystem for Encryption on PHY. In Proceedings of ISBC'06, Moscow, Russia, 2006.

22. E. M. Линский. "Криптосистема на ldpc-кодах для защиты информации на физическом уровне". Вопросы передачи и защиты информации, 2006.

23. Alfred Menezes, Paul С. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.

24. Sencun Zhu, Sanjeev Setia, and Sushil Jajodia. Leap: efficient security mechanisms for large-scale distributed sensor networks. In ACM Conference on Computer and Communications Security, pages 62-72, 2003.

25. Фомин А.Д. DPS: Эффективная схема управления ключами в больших сенсорных сетях. Вопросы передачи и защиты информации: Сборник статей / СПбГУАП. СПб., 2006.

26. S. Buchegger and J. Le Boudec. Nodes bearing grudges: Towards routing security, fairness, and robustness in mobile ad hoc networks, in pdp'02, 2002.

27. B. Parno, M. Luk, E. Gaustad, and A. Perrig. Secure sensor network routing: A clean-state approach. 2006.

28. C.E. Perkins. Ad Hoc Networking. Addison-Wesley, 2001.

29. J. Deng, R. Han, and S. Mishra. Intrusion-tolerant routing for wireless sensor networks. Elsevier Journal on Computer Communications. Special Issue on Dependable Wireless Sensor Networks, 2005.

30. Sergio Marti, T. J. Giuli, Kevin Lai, and Mary Baker. Mitigating routing misbehavior in mobile ad hoc networks. In Mobile Computing and Networking, pages 255-265, 2000.

31. A. D. Wood, L. Fang, J. A. Stankovic, and T. He. Sigf: A family of configurable, secure routing protocols for wireless sensor networks. In A CM SASN, October 2006.

32. Ieee std. 802.11, part 11: Wireless lan medium access control (mac) and physical layer (phy) specifications, 1997.

33. N.F. Maxemchuk. Dispersity Routing in Store and Forward Networks. PhD thesis, University of Pennsylvania, May 1975.

34. G.A. Kabatyanskii and E.A. Krouk. Coding decreases delay of messages in networks. In Proceedings of IEEE International Symposium on Information Theory.

35. Ф.Дж. Мак-Вильямс and Н.Дж.А. Слоэн. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

36. A. Barg, Е. Krouk, and Н. van Tilborg. On the complexity of minimum distance decoding of long linear codes. IEEE Transactions on Information Theory, pages 1392 1405, 1999.

37. W. W. Peterson and E. J. Weldon. Error-correcting Codes. MIT Press, 1972.

38. Christian Huitema. The case for packet level fee. In Walid Dabbous and Christophe Diot, editors, Protocols for High-Speed Networks, volume 73 of IFIP Conference Proceedings, pages 109-120. Chapman & Hall, 1996.

39. E. Schooler and J. Gemmell. Using multicast fee to solve the midnight madness problem, 1997.

40. John Byers, Michael Luby, Michael Mitzenmacher, and Ashu Rege. A digital fountain approach to reliable distribution of bulk data. In Proceedings of ACM SIGCOMM '98, September 2-4, 1998, 1998.

41. Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman, and Volker Stemann. Practical loss-resilient codes. In STOC, pages 150-159, 1997.

42. Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, and Daniel A. Spielman. Analysis of low density codes and improved designs using irregular graphs. In STOC, pages 249-258, 1998.

43. M.O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM, 36(2):335-348, April 1989.

44. P. Papadimitratos and Z.J. Haas. Secure message transmission in mobile ad hoc networks. In Proceedings of the ACM Workshop on Wireless Security (WiSe'03), San Diego, С A, USA, pages 41-50, September 2003.

45. S.D. Muruganathan, D.C.F. Ma, R.I. Bhasin, and A.O. Fapojuwo. A centralized energy-efficient routing protocol for wireless sensor networks. EEE Communications Magazine, 43(3):S8—13, 2005.

46. Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In HICSS, 2000.

47. Stephanie Lindsey and Cauligi S. Raghavendra. Pegasis: Power-efficient gathering in sensor information systems, 2002.

48. P. Garda, 0. Romain, B. Granado, A. Pinna, D. Faura, and K. Hachicha. Architecture of an intelligent beacon for wireless sensor networks. In IEEE 13th Workshop Neural Networks for Signal Processing, pages 151-158, 2003.

49. Ming-Zeng Hu Zhi-Yan Cao, Zheng-Zhou Ji. An image sensor node for wireless sensor networks. In International Conference on Information Technology: Coding and Computing, volume 2, pages 740-745, 2005.

50. D. Ganesan, R. Govindan, S. Shenker, and D. Estrin. Highly-resilient, energy-efficient multipath routing in wireless sensor networks, 2001.

51. S. De, C. Qiao, and H. und. Meshed multipath routing with selective forwarding: An efficient strategy in wireless sensor networks, 2003.

52. Budhaditya Deb, Sudeept Bhatnagar, and Badri Nath. Reinform: Reliable information forwarding using multiple paths in sensor networks, in 28th annual ieee conference on local computer networks (lcn 2003), october 2003.

53. Jian Yin and Sanjay Kumar Madria. A hierarchical secure routing protocol against black hole attacks in sensor networks. In SUTC '06: Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and

54. Trustworthy Computing -Vol 1 (SUTC'06), pages 376-383, Washington, DC, USA, 2006.

55. Afrand Agah, Mehran Asadi, and Sajal K. Das. Prevention of dos attack in sensor networks using repeated game theory. In Hamid R. Arabnia, editor, ICWN, pages 29-36. CSREA Press, 2006.

56. E.C. Вентцель. Теория вероятностей. M.: Наука, 3 edition, 1962.

57. D. Whiting, R. Housley, and N. Ferguson. Counter with cbc-mac (ccm), 2002.

58. Э. Рейнгольд and Ю. Нивергельт and H. Део. Комбинаторные алгоритмы: теория и практика. М.: Мир, 1980.

59. Т. Corman, С. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, 1990.

60. M. M. Ковалев. Дискретная оптимизация (целочисленное программирование). М.: Едиториал УРСС, 2003.

61. А. В. Ахо and Д. Э. Хопкрофт and Д. Д. Ульман. Структуры данных и алгоритмы. М: Издательский дом Вильяме, 2003.

62. И. В. Романовский. Субоптимальные решения. Петрозаводск: ПетрГУ, 1998.