EAGER: A New Algorithmic and Graph Model for Networking in Challenged Environments

Networking in Challenged Environments (NICE) is designed to meet the special networking needs of the 21st century, which includes the support of heterogeneous, anytime/anywhere networking, the robustness of the networks and network protocols explicitly designed to perform despite network dynamics and frequent disruptions, and the federation of networks across domains (including social networks) and technologies (wireless and acoustic). NICE requires support that is beyond current Internet capabilities, such as data delivery in the absence of end-to-end connection. These networks, developed from special technologies and applications, include (but are not limited to) wireless mobile ad hoc, sensor, underwater acoustic, aerial and ground vehicular, social, and delay/disruption tolerant networks (DTNs). These networks operate under special environments which pose unique challenges to the network design. One particular challenge is modeling and analyzing mobility. This SGER proposal presents a generalized graph model that can capture mobility in NICE. This model is called a weighted evolving graph which captures time-space dynamics while remaining simple enough to maintain most of the elegant structure of the traditional graph model. We first present several path optimization problems based on different metrics, including earliest completion, minimum hop, fastest and maximum reliability. We then extend several graph concepts in this new model. In reality, due to the nature of dynamic and challenged networks, it is too expensive to collect global information in both time and space to achieve one of the above global objectives. One fundamental issue is the following: can we develop a localized solution in which the graph is “trimmed” (by removing nodes/links across time and space) using only local information at each node? The merit of a trimmed graph is the reduction of searching complexity for routing and broadcasting. We plan to apply the proposed model to three different applications: (a) dynamic sensor networks with frequently switched on/off sensors, (b) mobile networks with cyclic movement trajectories (such as vehicular networks), and (c) people networks in which college students carrying iMotes/smart phones maintain contact records during periodic meetings and classes. The goals of the proposed research are the following. (1) Develop a novel graph theoretic model that captures both time and space for dynamic and challenged networks. (2) Propose a generic framework for solving various path optimization problems in the generalized graph model. (3) Present a localized trimming process for a reduction in searching complexity during the routing and broadcasting processes. The removal of nodes/links is guided by centrality metrics in social networks. (4) Study three applications of the model and localized trimming processes in sensor networks, DTNs, and people networks. (5) Simulate all three applications using simulation tools on both synthetic and real traces.

Intellectual Merit: The proposed graph theoretic model to capture NICE is a simple one. The proposal presents a promising and unique way of applying this graph model to address a new set of path optimization problems and other graph concepts. The proposal also studies efficient searching reductions through a local trimming process and casts some new light on efficient routing/broadcasting in NICE. Finally, the proposed model is applied to three important applications in dynamic sensor networks, DTNs, and people networks.

Broader Impact: The central theme fits well with the objective of the NeTS and NetSE programs on fundamental theoretical and algorithmic studies involving modeling of a complex network. We envision that insights and results from this research will provide guidelines for modeling and analyzing NICE. This research will also exploit and contribute to fundamental theories on dynamic and challenged networks under the generalized graph abstraction. The results obtained from this project should prove to be useful for various mobility applications and we believe that the proposed study will contribute to making these networks more practical.