Routing in Mobile Ad-Hoc Networks using Social Tie Strengths and Mobility Plans

ABSTRACT

We consider the problem of routing in a mobile ad-hoc network (MANET) for which the planned mobilities of the nodes are partially known a priori and the nodes travel in groups. This situation arises commonly in military and emergency response scenarios. Optimal routes are computed using the most reliable path principle in which the negative logarithm of a node pair’s adjacency probability is used as a link weight metric. This probability is estimated using the mobility plan as well as dynamic information captured by table exchanges, including a measure of the social tie strength between nodes. The latter information is useful when nodes deviate from their plans or when the plans are inaccurate. We compare the proposed routing algorithm with the commonly-used optimized link state routing (OLSR) protocol in ns-3 simulations. As the OLSR protocol does not exploit the mobility plans, it relies on link state determination which suffers with increasing mobility. Our simulations show considerably better throughput performance with the proposed approach as compared with OLSR at the expense of increased overhead. However, in the high-throughput regime, the proposed approach outperforms OLSR in terms of both throughput and overhead.

INTRODUCTION

 Mobile ad-hoc networks (MANETs) have been studied for several decades and, with recent advances in wireless communication technology, are expected to find increasing use in a wide range of applications. In general a MANET must be designed to accommodate arbitrary mobility of the constituent nodes (under reasonable speed constraints). The nodes may or may not move in groups, and their trajectories are generally unknown. Many MANET routing algorithms and protocols, both proactive and reactive, have been proposed over the years [1], some of which take advantage of known characteristics of the underlying network, and others which operate in the most general case. For example, the LANMAR protocol [2] is specifically designed for networks with group mobility, while Optimized Link State Routing (OLSR) [3], makes no assumptions on mobility. Many more such examples of environment-specific protocols exist. See [1] for a summary. In the last decade, researchers have shown that routing in delay-tolerant networks (DTNs) can be aided by dynamically gathered information about the social graph [4] of the underlying network [5] [6]. In particular, a node’s centrality, which in a social sense expresses its relative importance, can be used to determine its suitability for forwarding packets.

In this paper, we examine MANETs formed by a set of nodes participating in a collaborative activity for a finite time duration. An example is a military setting in which the nodes consist of mounted and dismounted soldiers carrying out a carefully planned mission. The mission plan includes the trajectory of each node, specified by waypoints, and nodes travel in groups. The trajectory information is useful for predicting node pair adjacencies and the group nature of the node travel gives rise to a novel adjacency prediction method using social tie strengths, which is beneficial when nodes deviate from their planned trajectories. This type of planned network, referred to as a tactical edge network, also arises in emergency response; for example, in disaster relief missions. A network of unmanned aerial vehicles (UAVs) with known flight plans is another potential example. Previous studies [7] [8] showed good results in using a “social tie centrality” metric for packet forwarding in information-centric networks. In this work, we derive a novel routing algorithm for tactical edge networks which exploits mobility plans and disseminates social tie information in a manner similar to [7]. Both pieces of information are used to make routing decisions by the algorithm, which we call Tactical Edge Network Social Routing (TENSR). We compare the performance of this algorithm in terms of throughput, delay, and overhead, to OLSR for several representative cases We find that significant throughput improvement relative to OLSR can be obtained by exploiting the mobility plan and social information.

CONCLUSIONS

We have developed a novel routing protocol for tactical edge networks which exploits known mission information such as mobility plans, as well as dynamic social information and position location information. The protocol has been compared to OLSR and shown to be superior in terms of throughput and approximately equal in terms of delay, at the expense of increased overhead. In the high-throughput regime, which is achived by reduction of the HELLO and information exchange intervals in both protocols, the TENSR protocol is superior to OLSR in both throughput and overhead.