Opportunistic Walks on Random Geometric Networks and Their Application in Scalability Analysis - eScholarship
Jose Joaquin Garcia-Luna-Aceves · 2013
Opportunistic Walks on Random Geometric Networks and Their Application in Scalability Analysis Ali Dabirmoghaddam J. J. Garcia-Luna-Aceves Department of Computer Engineering University of California, Santa Cruz Santa Cruz, California 95064 Email: {alid, jj}@soe.ucsc.edu Abstract—Opportunistic routing is studied as a representative example of location-aware greedy routing schemes. The routing process between an arbitrary source-destination pair is modeled as a directed random walk between the two ends in the underlying graph. The mean number of transmissions as well as the average multi-hop distance between arbitrary nodes are unified under a conceptual measure called expected length of the opportunistic walk in the induced network graph. We model this quantity as the mean time to absorption in a finite-state Markov chain. An explicit closed-form expression is presented to approximate the results and tight bounds are given. The accuracy of the results predicted by the analytical model is verified through simulation experiments. We also demonstrate an application of the foregoing model in defining proximity-based social models and identifying classes of social networks that are scalable. I. I NTRODUCTION Originated by Gupta and Kumar’s seminal analysis [1], it came to be believed that wireless networks are not fundamen- tally scalable in size due to mutual interference, concurrent transmissions and increased accumulation of the relaying traf- fic load throughout the network. Although various commu- nication models were examined in that work, one important aspect being neglected was a realistic interaction paradigm between nodes. In particular, it was assumed that sources and destinations are chosen uniformly and randomly within the net- work. This assumption disregards the natural drivers ruling the quality of social relationships in real-world networks of people. One such important element is the geographical dispersion between nodes. Numerous studies have shown that the physical distance plays a crucial role in initiating social interactions among people in both online and offline worlds [2]–[5]. Despite the tight dependency and extensive overlap be- tween the social networks and their underlying communication networks, due to the involved complexities, the mainstream literature has only studied the performance of such networks separately. Examples of studies on communication networks neglecting the latent social relationships are [1], [6], [7]. In contrast, several interaction patterns and social paradigms [8]– [10] are independently studied while the restrictions imposed by realistic underlying communication networks are over- looked. In this work, we present an analytical model that uses the geographical distance between nodes to capture the in- terplay between realistic communication algorithms and social relationships in composite networks. In the past few years, extensive research have been conducted on hop count statistics of wireless networks with geographic routing [11]–[13]. We revisit this problem and provide a Markov-chain formulation for it. For the routing algorithm, we study Opportunistic Routing [14] ( OR ) as a generic example for the broad class of location-aware greedy forwarding schemes. We model this routing algorithm as a directed random walk on the physical graph of the network. We call such a process an opportunistic walk and using that, we show how the notions of hop count ( HC ) and transmission count ( TX ) can be unified under a conceptual measure we call length of the opportunistic walk. By means of this analysis, we demonstrate that the per- hop progress towards destination can be approximated by an iid process. Such a process is described by a probability distri- bution that incorporates the collective impact of all important physical and geometrical properties of the network, e.g., link quality, node density, radio coverage, etc. The ultimate deriva- tion, presented by Theorem 1, bounds the expected length of the walk for all nodes within a certain but arbitrary maximum physical distance in a form expressed by the characteristic function of the foregoing distribution. For the social aspect, we use a power-law distribution on geographical distance to specify the frequency and quality of inter-node interactions. We finally demonstrate that how the combination of two models can be used to identify classes of composite networks that exhibit scalability. In short, the major contributions of this work can be summarized as follows: Presenting a fast, efficient and highly accurate method to calculate the expected hop count (E HC ) and expected number of transmissions (E TX ) between source-destination pairs at arbitrary distances under a greedy forwarding scheme. Using the geographical distance as the key ingredi- ent to interrelate the concepts of communication and social networks under realistic settings. Identifying classes of proximity-based social networks that result in scalable structures. The remainder is organized as follows. Section II provides a formal description of the problem. Section III describes a general framework for solving the problem using Markov chains and Section IV provides convenient tools for an effi- cient solution. Section V validates the analytical model using simulation results. Section VI discusses an application of the foregoing model in analysis of scalability in wireless social networks. Finally, Section VII concludes the paper.