Elsevier

Computer Networks

Volume 57, Issue 1, 16 January 2013, Pages 228-242
Computer Networks

Fairness-related challenges in mobile opportunistic networking

https://doi.org/10.1016/j.comnet.2012.08.019Get rights and content

Abstract

The fundamental challenge in opportunistic networking, regardless of the application, is when and how to forward a message. Rank-based forwarding techniques currently represent one of the most promising methods for addressing this message forwarding challenge. While these techniques have demonstrated great efficiency in performance, they do not address the rising concern of fairness amongst various nodes in the network. Higher ranked nodes typically carry the largest burden in delivering messages, which creates a high potential of dissatisfaction amongst them. In this paper, we adopt a real-trace driven approach to study and analyze the trade-offs between efficiency, cost, and fairness of rank-based forwarding techniques in mobile opportunistic networks.

Our work comprises three major contributions. First, we quantitatively analyze the trade-off between fair and efficient environments. Second, we demonstrate how fairness coupled with efficiency can be achieved based on real mobility traces. Third, we propose FOG, a real-time distributed framework to ensure efficiency–fairness trade-off using local information. Our framework, FOG, enables state-of-the-art rank-based opportunistic forwarding algorithms to ensure a better fairness–efficiency trade-off while maintaining a low overhead. Within FOG, we implement two real-time distributed fairness algorithms; Proximity Fairness Algorithm (PFA), and Message Context Fairness Algorithm (MCFA). Our data-driven experiments and analysis show that mobile opportunistic communication between users may fail with the absence of fairness in participating high-ranked nodes, and an absolute fair treatment of all users yields inefficient communication performance. Finally our analysis shows that FOG-based algorithms ensure relative equality in the distribution of resource usage among neighbor nodes while keeping the success rate and cost performance near optimal.

Introduction

Mobile opportunistic networks interconnect nodes with heterogeneous contact rates, unpredictable mobility, and limited resources. These mobile nodes communicate relying on both the transport of messages as well as multi-hop forwarding. Current forwarding techniques [3], [28], [19], [21], [9] are generally designed to efficiently select the most likely relay nodes to deliver a message to its destination. Within those techniques, rank-based forwarding [5], [7], [8] represents one of the most promising methods for addressing this message forwarding challenge. This method differs in the type of information used (e.g., information acquired during contacts [7], [8], or social interaction between users [5], [26], [25]), as well as how it is used to rank nodes in the network. A node with a lower rank will forward messages to nodes with higher ranks. This solution, however, creates a high potential of dissatisfaction among high ranked nodes that carry a heavier burden compared to others.

Ensuring fairness in mobile opportunistic networks is a crucial goal if rank-based forwarding algorithms are to be adopted in the future. In such networks, nodes can behave selfishly and try to only maximize their own utility without considering the global system-wide performance. Previous studies have considered absolute fair allocation of user resources [1], [18], [20]. They have shown that absolute fairness results in higher end-to-end delivery delays. They did not, however, investigate trade-offs between the three metrics in mobile opportunistic networks: fairness, end-to-end delay, and cost.

Throughout this paper, we adopt a real-trace driven approach to quantitatively analyze those trade-offs, and propose a real-time distributed framework for fairness in opportunistic networking. Our initial conference version compromises three major contributions [23]. First, we quantitatively analyze the impact of an absolute fair and efficient environment on the overall network performance. We show that in an unfair environment, selecting preferential or popular relay nodes in forwarding decisions is efficient and yields enhanced forwarding performance. We also show that absolute balancing across nodes causes significant end-to-end delay and severe performance degradation. Second, we study the trade-off between fairness, cost, and efficiency in opportunistic forwarding. Relying on our experimental datasets, we consider an offline approach to construct forwarding paths while ensuring both fairness and efficiency, and keeping the cost near optimal. Finally, we adopt a distributed real-time approach in order to efficiently discover these paths while utilizing only local information. We call our distributed real-time framework FOG (Fairness-based Opportunistic networkinG framework).

This journal paper adds the following contributions beyond the conference version [23]:

  • We address fairness in opportunistic forwarding more generally. While [23] focuses mainly on a trade-off between fairness and success delivery ratio, this paper extends that work to quantitatively study different trade-offs between fairness, cost and success rate. Cost metric is addressed after identifying the best performing algorithms with respect to the other two metrics. We look then at the cost within those nominal values. We investigate fairness issues of social-based forwarding algorithms such as PeopleRank [25] and Simbet [5] and contact-based forwarding such as Frequency (FR) [8] and Last_Contact (LC) [7].

  • We propose two real-time distributed algorithms to maximize the overall user satisfaction; Proximity Fairness Algorithm (PFA) and Message Context Fairness Algorithm (MCFA). While the main advantage of PFA is its simplicity which allows any rank-based forwarding algorithm to ensure minimum fairness without using additional network information, MCFA uses local information to make better forwarding decisions. MCFA enables cost performance aware message delivery in mobile opportunistic networks taking into account the number of message replicas in the network and user satisfaction of each message. We model the satisfaction a node derives from sending and receiving messages as a utility function. MCFA uses such utility in order to avoid overwhelming the popular nodes with many messages when other nodes can deliver them to theirs destination in a bounded delay.

  • Our real-trace analysis includes additional results that rely on a modified San Francisco [27] dataset that we synthesize. We show that FOG uses the two fairness algorithms PFA and MCFA to ensure relative equality in the distribution of resource usage among neighbor nodes while maintaining a high delivery success rate, and cost performance close to optimal. While the simplicity is considered as one of PFA algorithm strengths, we show that MCFA uses fewer message replicas compared to PFA and achieves a better success delivery ratio.

The remainder of this paper is organized as follows. Section 2 provides a brief overview of rank-based forwarding techniques and the experimental datasets used throughout the paper in our analysis. Section 3 discusses the fairness vs. efficiency vs. cost trade-offs. In Section 4 we adopt an offline approach to construct forwarding paths while ensuring both fairness and efficiency. In Section 5, we propose a real-time distributed framework for fairness in opportunistic networking, and implement two distributed algorithms that enable existing rank-based forwarding algorithms to be both fair and efficient. We then present the related work in the field of fair and efficient mobile opportunistic forwarding in Section 6. Finally, Section 7 concludes the paper.

Section snippets

Background and datasets

In this section we provide a brief overview on rank-based forwarding algorithms, and present the experimental datasets used in our analysis to improve the fairness of these forwarding algorithms. We also briefly describe our evaluation methodology used throughout the whole paper.

Fairness vs. efficiency vs. cost

Our discussion of trade-offs between efficiency, fairness, and cost highly depends on the definition of those three metrics. In this section, we first define these terms. We then quantitatively motivate the need to investigate these trade-offs using real experimental traces.

Can we be both efficient and fair?

In this section we quantitatively identify the trade-off relationship between fairness and efficiency. We first provide some intuition regarding the desired fairness we seek while introducing our satisfaction index metric. We then discuss an offline approach to verify, based on our experimental datasets, the availability of paths that would satisfy both efficiency and fairness.

A real-time distributed framework for fairness-based forwarding

We now propose a real-time distributed framework that maximizes the overall user satisfaction using existing state-of-the-art rank-based forwarding algorithms; it helps rank-based forwarding algorithms utilize potential nodes to forward messages while satisfying the fairness property given by Eq. (1). We call our systematic framework, Fairness-based Opportunistic networkinG (FOG). FOG is a framework that enables state-of-the-art rank-based opportunistic forwarding algorithms to ensure a better

Related work

Most interactions between people rely on the establishment of the sense of fair treatment. Computer networking communication, and more particularly peer-to-peer file sharing applications and services take into consideration the fair treatment of users. Fairness is therefore particularly important and challenging since it is considered a major incentive for peer-to-peer service usage in today’s Internet. Theses challenges are more critical in infrastructure-less wireless networks given the lack

Conclusion

Our work addresses the rising concern of fairness amongst various nodes in mobile-based opportunistic networks. Rank-based forwarding algorithms are typically designed to reduce the number of data replicas in the network to conserve bandwidth and reduce end-to-end delay. In these algorithms, higher ranked nodes carry a much heavier burden in delivering messages, which can create high levels of dissatisfaction amongst them. In this paper, we have proposed FOG a real-time distributed framework

Abderrahmen Mtibaa, Ph.D., is a postdoctoral research associate in the School of Computer Science at Carnegie Mellon University in Qatar. Graduated on June 2010 from the University of Paris VI and Technicolor Paris Research Lab. His current areas of interest include mobile opportunistic networks/DTN, wireless and ad hoc networks, mobility models, protocol design, routing/forwarding, network communities and social networking.

References (34)

  • S. Brin et al.

    The anatomy of a large-scale hypertextual web search engine

    Comput. Netw. ISDN Syst.

    (1998)
  • X. Zhang et al.

    Performance modeling of epidemic routing

    Comput. Netw.

    (2007)
  • A. Balasubramanian et al.

    Dtn routing as a resource allocation problem

    SIGCOMM Comput. Commun. Rev.

    (2007)
  • J. Burgess, B. Gallagher, D. Jensen, B. Levine, Maxprop: routing for vehicle-based disruption-tolerant networking, in:...
  • A. Chaintreau, A. Mtibaa, L. Massoulié, C. Diot, The diameter of opportunistic mobile networks, in: Proceedings of ACM...
  • E.M. Daly et al.

    Social network analysis for routing in disconnected delay-tolerant MANETs

  • S.R. Das, Ad hoc On-demand Distance Vector (AODV) Routing,...
  • H. Dubois-Ferriere, M. Grossglauser, M. Vetterli, Age matters: efficient route discovery in mobile ad hoc networks...
  • V. Erramilli et al.

    Diversity of forwarding paths in pocket switched networks

  • V. Erramilli et al.

    Delegation forwarding

  • S. Guo et al.

    Fair and efficient scheduling in data ferrying networks

  • Z.J. Haas, J. Deng, B. Liang, P. Papadimitratos, S. Sajama, Wireless Ad hoc Networks,...
  • W. Henzeilman, J. Kulik, H. Balaksrishnan, Adaptive protocols for information dissemination in wireless sensor...
  • R. Jain, D.M. Chiu, W.R. Hawe, A quantitative measure of fairness and discrimination for resource allocation in shared...
  • S. Jain, K. Fall, R. Patra, Routing in a delay tolerant network, in: Proceedings of ACM SIGCOMM,...
  • S. Jain, R.C. Shah, G. Borriello, W. Brunette, S. Roy, Exploiting mobility for energy efficient data collection in...
  • D. Johnson et al.

    Comparison of MANET routing protocols using a scaled indoor wireless grid

    Mob. Netw. Appl.

    (2008)
  • Cited by (0)

    Abderrahmen Mtibaa, Ph.D., is a postdoctoral research associate in the School of Computer Science at Carnegie Mellon University in Qatar. Graduated on June 2010 from the University of Paris VI and Technicolor Paris Research Lab. His current areas of interest include mobile opportunistic networks/DTN, wireless and ad hoc networks, mobility models, protocol design, routing/forwarding, network communities and social networking.

    Khaled A. Harras is currently an Assistant Teaching Professor in the Department of Computer Science at Carnegie Mellon University. He is the founder and director of the Networking Systems Lab and currently resides at CMU’s campus in Qatar. Khaled’s main research interests include delay and disruption tolerant networks, specifically protocol and architectural challenges in extreme networking environments, multimedia wireless sensor networks, social pervasive systems, and multi-interface networking and communication. He is a member of IEEE and the ACM.

    View full text