A neighbor detection algorithm based on multiple virtual mobile nodes for mobile ad hoc networks

详细信息    查看全文

• 作者：Behnaz Bostanipour ; ^{behnaz.bostanipour@unil.ch}Author Vitae ; Benoî ; t Garbinato ^{benoit.garbinato@unil.ch}Author Vitae
• 关键词：Neighbor detection ; Virtual mobile node ; MANET ; Proximity-based mobile applications ; Distributed algorithms ; Smartphone
• 刊名：Computer Networks
• 出版年：2017
• 出版时间：15 January 2017
• 年：2017
• 卷：112
• 期：Complete
• 页码：294-313
• 全文大小：1174 K
• 卷排序：112

文摘

We introduce an algorithm that implements a time-limited neighbor detector service in mobile ad hoc networks. The time-limited neighbor detector enables a mobile device to detect other nearby devices in the past, present and up to some bounded time interval in the future. In particular, it can be used by a new trend of mobile applications known as proximity-based mobile applications. To implement the time-limited neighbor detector, our algorithm uses n=k2n=2k virtual mobile nodes where k is a non-negative integer. A virtual mobile node is an abstraction that is akin to a mobile node that travels in the network in a predefined trajectory. In practice, it can be implemented by a set of real nodes based on a replicated state machine approach. Our algorithm implements the neighbor detector for real nodes located in a circular region. We also assume that each real node can accurately predict its own locations up to some bounded time interval Δpredict in the future. The key idea of the algorithm is that the virtual mobile nodes regularly collect location predictions of real nodes from different subregions, meet to share what they have collected with each other and then distribute the collected location predictions to real nodes. Thus, each real node can use the distributed location predictions for neighbor detection. We show that our algorithm is correct in periodically well-populated regions. We also define the minimum value of Δpredict for which the algorithm is correct. Compared to the previously proposed solution also based on the notion of virtual mobile nodes, our algorithm has two advantages: (1) it tolerates the failure of one to all virtual mobile nodes; (2) as n grows, it remains correct with smaller values of Δpredict. This feature makes the real-world deployment of the neighbor detector easier since with the existing prediction methods, location predictions usually tend to become less accurate as Δpredict increases. We also show that the cost of our algorithm (in terms of communication) scales linearly with the number of virtual mobile nodes.