Оценка времени обнаружения радиоузлов в полносвязной mesh-сети с учетом вероятности ошибки на сообщение

Аннотация

Процедура обнаружения радиоузлов в беспроводных mesh-сетях – это критический этап установления соединения, однако длительность обнаружения зависит от уровня помех в канале. Скорость построения маршрутов в беспроводных самоорганизующихся сетях напрямую определяется временем обнаружения соседних узлов. В условиях реального радиоканала этот процесс замедляется из-за потерь пакетов. В работе исследуется влияние вероятности ошибки на пакет (PER) на среднее время обнаружения всех соседних радиоузлов в сети в топологии «полносвязная группа». Задача сведена к классической задаче о коллекционере, что позволило получить аналитическое выражение для зависимости времени обнаружения от PER. Корректность полученной формулы подтверждена имитационным моделированием. Предложенная модель дает возможность количественно оценить задержки инициализации сети на этапе проектирования без проведения натурных испытаний. Результаты работы позволяют инженерам прогнозировать время развертывания mesh-сетей на этапе расчета радиопокрытия.

• mesh-сети
• ad-hoc
• топология сети
• one-hop
• multi-hop
• aloha
• collision detection
• clique

Abstract (in English)

The estimation of discovery duration in fully connected mesh-networks under non-zero bit error rates

Neighbor discovery is a fundamental step in establishing wireless mesh-networks, but its completion time is strongly affected by channel interference. Since route construction in self-organizing wireless networks relies on prior neighbor detection, any delays at this stage directly impact overall network setup time. In practical radio environments, packet losses further prolong the discovery process. In this work, we study how the packet error rate (PER) influences the average time required to discover all neighbors in a complete-graph topology. We reformulate this problem as a variant of the coupon collector problem, which leads to a closed-form analytical expression relating the mean discovery time to PER. The accuracy of the derived formula is verified through simulation. The proposed model allows network designers to quantitatively estimate initialization delays during the planning phase, eliminating the need for experimental measurements. The results offer a practical means to forecast mesh-network deployment timelines already at the radio-coverage calculation stage.

Для цитирования

Литература

1. Vasudevan S. et al. Neighbor discovery in wireless networks and the coupon collector's problem // Proceedings of the 15th annual international conference on Mobile computing and networking. – 2009. – С. 181-192.
2. Bao L., Garcia-Luna-Aceves J.J. A new approach to channel access scheduling for ad hoc networks // Proceedings of the 7th annual international conference on Mobile computing and networking. – 2001. – С. 210-221.
3. Johnson D.B., Maltz D.A. Dynamic source routing in ad hoc wireless networks // Mobile computing. – Boston, MA : Springer Us, 1996. – С. 153-181.
4. Keshavarzian A. et al. Energy-efficient link assessment in wireless sensor networks // IEEE INFOCOM 2004. – IEEE, 2004. – Т. 3. – С. 1751-1761.
5. Хоров Е.М. Знакомство с современными беспроводными технологиями. Многошаговые беспроводные сети: принципы построения и открытые задачи // Информационнотехнологический вестник. – 2017. – №. 3. – С. 13.
6. Базенков Н. и др. Теоретико-игровые алгоритмы формирования децентрализованных беспроводных сетей : дис. – Институт проблем управления им. ВА Трапезникова Российской академии наук, 2014.
7. Russell A. et al. Neighbor discovery in wireless networks with multipacket reception // IEEE Transactions on Parallel and Distributed Systems. – 2014. – Т. 26. – №. 7. – С. 1984-1998 https://doi.org/10.1109/TPDS.2014.2321157
8. Амбаткар С.В. Neighbor node discovery для беспроводной самоорганизующейся одноранговой сети типа Ad-hoc / С.В. Амбаткар, П. Кулкарни ; пер. В. Рентюк // Беспроводные технологии. – 2017. – № 1. – С. 19–21.
9. Li L. et al. A cone-based distributed topology-control algorithm for wireless multi-hop networks // IEEE/ACM Transactions on networking. – 2005. – Т. 13. – №. 1. – С. 147-159.
10. Burghal D., Tehrani A.S., Molisch A.F. On expected neighbor discovery time with prior information: Modeling, bounds and optimization // IEEE Transactions on Wireless Communications. – 2017. – Т. 17. – №. 1. – С. 339-351.
11. Vasudevan S., Kurose J., Towsley D. On neighbor discovery in wireless networks with directional antennas // Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. – IEEE, 2005. – Т. 4. – С. 2502-2512 https://doi.org/10.1109/INFCOM.2005.1498535
12. Motwani R., Raghavan P. Randomized algorithms. Cambridge Univ // Press. Cambridge, UK. – 1995.
13. Zhang L., Luo J., Guo D. Neighbor discovery for wireless networks via compressed sensing // Performance Evaluation. – 2013. – Т. 70. – №. 7-8. – С. 457-471.
14. Proakis J.G., Salehi M. Digital communications. – New York : McGraw-hill, 2001. – Т. 4. – С. 593-620.