Slotless Protocols for Neighbor Discovery in Wireless Networks

在过去的十年里，不需要任何固定基础设施的网络(移动自组织网络，MANET)得到了广泛的应用。在MANET中的两个设备开始通信之前，它们必须发现它们之间的相互存在，并使用称为邻居发现的过程来同步它们的时钟。由于MANET的所有参与者都是由电池供电的，因此节能的邻居发现是一个至关重要的要求。在这种协议中，一个设备在一组特定的频道上重复广播分组，而其他设备在短时间内重复打开它们的接收器。为了节省能源，这些设备在此期间休眠。两台设备都收到来自对方的第一个数据包后，已成功发现对方。最常见的邻居发现协议称为时隙协议。它们将时间细分为多个等长的间隔，称为时隙。在某些插槽中，设备保持休眠状态，而另一些插槽则是用于通信的活动插槽。一旦两个活动时隙在时间上重叠，则发现过程完成。活动时隙和休眠时隙的模式由特定的时间表定义。从邻居发现的角度来看，协议设计的问题是在确保低延迟的情况下，识别导致低能耗的调度。在过去的几年里，主动/被动时隙调度一直是一个活跃的研究领域，它保证了发现延迟的确定的最坏情况的界限。在这个项目中，我们考虑一种不同的范式，它可以被描述为无槽。在遵循此范例的协议中，传输设备以周期性间隔发送包，传输持续时间由包的大小确定。另一个设备也以周期性间隔打开其接收器，并在每个周期期间保持打开指定的持续时间。周期间隔的长度以及接收器的接通持续时间是在连续时间上绘制的。我们的初步工作表明，对于这些协议的几乎所有的参数化，可以保证确定的延迟界限，并且某些间隔长度的选择导致发现延迟比最著名的时隙协议短得多，同时消耗相同的能量。该项目的主要目标是开发无时隙协议的分析模型，并在此基础上开发性能优于所有现有协议的新型协议。然后实施这些协议以验证它们在真实网络中的行为。

Within the last decade, networks which do not require any fixed infrastructure (mobile ad-hoc networks, MANETS) have become widespread. Before two devices in a MANET can start communicating, they have to discover their mutual existance and synchronize their clocks using a procedure called neighbor discovery. Since all participants of a MANET are powered by batteries, power-efficient neighbor discovery is a crucial requirement. In such protocols, a device repeatedly broadcasts packets on a certain set of channels, whereas other devices repeatedly switch on their receivers for short amounts of time. To save energy, the devices sleep in the meantime. Two devices have discovered each other successfully once both have received a first packet from their opposite. Most common neighbor discovery protocols are referred to as slotted protocols. They subdivide time into multiple, equal-length intervals, called slots. In some slots, the device remains asleep, whereas other ones are active slots used for communication. The discovery procedure is complete once two active slots overlap in time. The pattern of active and sleep slots is defined by a specific schedule. The protocol design problem from the perspective of neighbor discovery is to identify schedules that lead to low energy consumptions, while ensuring low-latencies. In the last years, schedules of active/passive slots, which guarantee deterministic worst-case bounds on the discovery latencies have been an active field of research. In this project, we consider a different paradigm which may be characterized as slotless. In protocols following this paradigm, the transmitting device send packets at periodic intervals, with the transmission duration determined by the size of a packet. The other device switches on its receiver also at periodic intervals and remains on for a specified duration during each period. The lengths of the periodic intervals as well as the on-durations of the receiver are drawn over continuous time. Our preliminary work indicates that for almost all parametrizations of these protocols, deterministic latency bounds can be guaranteed and certain choices of interval lengths lead to significantly shorter discovery-latencies than the best known slotted protocols, while consuming the same amount of energy. The main goal of this project is to develop analytical models for slotless protocols and, based thereupon, to develop novel protocols with higher performances than all existing ones. These protocols are then implemented to verify their behavior in real-world networks.