Opportunistic Neighbour Prediction Using an Artificial Neural Network

1. Introduction

Mobile ad-hoc network (MANET) mobility can lead to dynamic behaviour and problems such as sub-optimal routing or link breaks caused by nodes changing their position. Potentially intermittent connectivity poses a significant challenge in performing end-to-end routing. Location prediction for mobility management has been studied in geographic routing protocols such as Chen et al. (2006), Chou et al. (2008), and Son et al. (2004), and has also been used for QoS; Shah and Nahrstedt (2002), Stojmenovic et al. (2000), and Cadger et al. (2011). Geographic routing is localized and does not build end-to-end paths instead performing forwarding on a hop-by-hop basis. It does however still rely on continuous connectivity to an extent; if a node is unable to find a suitable next hop using the forwarding condition then the packet will be dropped. Although this is common in conventional infrastructure as well as ad-hoc routing, it is not always desirable. Opportunistic networking is a subfield of Delay Tolerant Networking (DTN). DTNs acknowledge the possibility that connections between network nodes may be intermittent; both in terms of end-to-end connection (which might never be possible using conventional routing) or even nodes being completely disconnected from all other devices for large periods of time. Existing ad-hoc routing protocols generally rely on continuous connectivity for building paths, and are unable to cope with prolonged periods of isolation or intermittent connectivity.

Opportunistic networking is an attempt to provide communications in DTNs and other scenarios with intermittent and potentially unpredictable connectivity. Opportunistic networks make forwarding decision on a hop-by-hop basis using local information. Where opportunistic networking differs from geographic routing is its use of the store-and-forward paradigm; if a node does not have any suitable neighbours or is completely disconnected from the network then it will store the message until it finds a suitable next hop. Mobility is therefore a significant factor in most opportunistic networking protocols, being both the cause of and solution to intermittent connectivity. If devices are able to accurately predict where either they or their current neighbours would be at a particular time then they could make forwarding decisions with the aim of increasing reception potential or saving energy. In Li and Shatz (2008) a geographic routing protocol with some similarities to opportunistic networking allows nodes to favour neighbours who are moving towards the destination over static nodes.

Wireless infrastructure networks such as WLANs and cellular networks have employed techniques from the field of machine learning such as artificial neural networks (NN) (Capka and Boutaba, 2004) and Hidden Markov Models (Prasad and Agrawal, 2010) for location prediction, which boast high accuracy and success. However, all of these works are reliant on either WLAN or cellular infrastructure as they formulate location prediction as a discrete classification problem in which the aim is to classify a user’s location in terms of proximity to a wireless access point or cell and which makes them unsuitable for use in ad-hoc or opportunistic networks. An approach which is able to predict locations in a manner which is not dependent on the existence of infrastructure and requires knowledge of the area is therefore highly desirable. This led to the consideration of continuous regression techniques instead of discrete classification for location in prediction in MANETs. In Cadger et al. (2012) three location prediction algorithms were used to predict future device locations using MANET mobility traces with a NN performing best. The difference between Cadger et al. (2012) and previous works in infrastructure networks such as Capka and Boutaba (2004) and Prasad and Agrawal (2010) is that Cadger et al. is able to take previous coordinates and use these to predict the future coordinates for that device, without the need for any infrastructure or area-specific knowledge which makes it suitable for opportunistic networks.