Neighbor Discovery in Wireless Networks: Moving from two to the Multi-Device and Asymmetric Case

物联网依赖于高能效的无线通信来实现足够长的电池运行时间，或者能够使用能量收集来为设备供电。然而，建立第一个无线联系的过程，称为邻居发现，仍然非常耗能。为了建立第一次联系，每个设备定期向该信道发送分组，并定期调度用于检测来自其他设备的传入传输的接收窗口。为了节省能源，设备在不参与通信的时候休眠。当另一台设备正在执行接收窗口时，一旦发送了分组，就建立了第一次联系。主要目标是最大限度地减少延迟，直到在最坏的情况下才能建立第一次联系。为此，需要优化分组和接收窗口的调度。对于一个发射机和一个接收机的情况，该问题的最优解是已知的。但是，当多个设备同时发现彼此时，冲突的数据包在此过程中占主导地位，现有解决方案不再是最佳解决方案。此外，即使对于只有两个设备的情况，也不知道允许每个设备自主调整其能源预算的最佳协议。这两种情况都与物联网高度相关，物联网的异类设备数量不断增加，具有不同的能源需求。本项目的目标是为在这样的场景下高效的邻居发现过程创建理论基础。在此基础上，我们开发了实用的协议，其性能明显高于现有的解决方案。此外，我们还使用离散事件模拟和使用无线无线电硬件的真实世界实验来评估我们的结果。

The Internet of Things relies on energy-efficient wireless communications for achieving sufficiently long battery runtimes, or for being able to power devices using energy harvesting. However, the procedure for establishing a first wireless contact, called neighbor discovery, remains to be very energy-hungry. This particularly aggravates applications, in which such a procedure needs to be carried out continuously for detecting new devices in the environment.For establishing a first contact, every device transmits packets regularly to the channel, and regularly schedules reception windows for detecting incoming transmissions from other devices. For saving energy, the devices sleep whenever they don't participate in the communication. As soon as a packet is sent while another device is carrying out a reception window, a first contact has been established. The main goal is to minimize the latency until which a first contact can be established in the worst-case. Towards this, the schedule of packets and reception windows needs to be optimized. For the case of one transmitter and one receiver, an optimal solution is known for this problem. However, when multiple devices discover each other simultaneously, colliding packets become predominant in this procedure and existing solutions are no longer optimal. Furthermore, even for the case of only two devices, no optimal protocols that allow each device to adjust its energy-budget autonomously are known. Both scenarios are highly relevant in the Internet of Things, with its growing number of heterogeneous devices with different energy requirements. Goal of this project is creating the theoretical foundations for an efficient neighbor discovery procedure in such scenarios. Based thereupon, we develop practical protocols with a significantly higher performance than existing solutions. We furthermore evaluate our results using discrete event simulations and real-world experiments using wireless radio hardware.