This EAGER proposal presents a generalized graph model that can capture mobility in Networking in Challenged Environments (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.
The proposal addresses one fundamental issue: 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 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 proposed model can be applied to three important applications in dynamic sensor networks, DTNs, and people networks. 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.
