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

Abstract

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.

• mesh-networks
• ad-hoc networks
• network topology
• one-hop communication
• multi-hop communication
• ALOHA protocol
• collision detection
• clique

Аннотация (на русском)

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

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

For citation

References

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. – P. 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. – P. 210-221.
3. Johnson D.B., Maltz D.A. Dynamic source routing in ad hoc wireless networks // Mobile computing. – Boston, MA: Springer US, 1996. – P. 153-181.
4. Keshavarzian A. et al. Energy-efficient link assessment in wireless sensor networks // IEEE INFOCOM 2004. – IEEE, 2004. – Vol. 3. – P. 1751-1761.
5. Khorov E.M. Introduction to modern wireless technologies. Multi-hop wireless networks: principles of construction and open problems // Informatsionno-tekhnologicheskii vestnik. – 2017. – No. 3. – P. 13. (In Russian)
6. Bazhenkov N. et al. Game-theoretic algorithms for the formation of decentralized wireless networks: diss. – Institute of Control Sciences named after V.A. Trapeznikov of the Russian Academy of Sciences, 2014. (In Russian)
7. Russell A. et al. Neighbor discovery in wireless networks with multipacket reception // IEEE Transactions on Parallel and Distributed Systems. – 2014. – Vol. 26. – No. 7. – P. 1984-1998. https://doi.org/10.1109/TPDS.2014.2321157
8. Ambatkar S.V. Neighbor node discovery for a wireless self-organizing ad-hoc peer-to-peer network / S.V. Ambatkar, P. Kulkarni; transl. V. Rentyuk // Besprovodnye tekhnologii. – 2017. – No. 1. – P. 19–21. (In Russian)
9. Li L. et al. A cone-based distributed topology-control algorithm for wireless multi-hop networks // IEEE/ACM Transactions on networking. – 2005. – Vol. 13. – No. 1. – P. 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. – Vol. 17. – No. 1. – P. 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. – Vol. 4. – P. 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. – Vol. 70. – No. 7-8. – P. 457-471.
14. Proakis J.G., Salehi M. Digital communications. – New York: McGraw-Hill, 2001. – Vol. 4. – P. 593-620.