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

EAGER：一种用于挑战环境中网络的新算法和图形模型

• 批准号: 0948184
• 负责人: Jie Wu
• 金额: $ 19.94万
• 依托单位: Temple University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-15 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0948184&HistoricalAwards=false
• 关键词: EAGER; New; Algorithmic; Graph; Model

EAGER: A New Algorithmic and Graph Model for Networking in Challenged EnvironmentsThis 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.

EIGER：挑战环境中网络的新算法和图模型这一建议提出了一个通用的图模型，该模型可以捕获挑战环境中网络的移动性(NICE)。这个模型被称为加权演化图，它捕捉了时空动态，同时保持了足够简单，以保持传统图模型的大部分优雅结构。我们首先提出了几个基于不同度量的路径优化问题，包括最早完成、最小跳数、最快和最大可靠性。然后，我们在这个新的模型中扩展了几个图的概念。该方案解决了一个基本问题：我们是否可以开发一个本地化的解决方案，在这个方案中，只使用每个节点上的局部信息来“修剪”图(通过移除跨时间和空间的节点/链接)？我们计划将该模型应用于三种不同的应用：(A)具有频繁开关传感器的动态传感器网络，(B)具有周期性运动轨迹的移动网络(如车辆网络)，以及(C)大学生携带iMotes/智能手机在周期性会议和课堂上维护联系记录的人际网络。该方案提出了一种应用该图模型来解决一组新的路径优化问题和其他图概念的有前途的独特方法。该模型可应用于动态传感器网络、动态时延网络和人员网络中的三个重要应用。我们预计，这项研究的见解和结果将为NICE的建模和分析提供指导。这项研究还将对广义图抽象下的动态和挑战网络的基本理论进行开拓和贡献。