CAREER: Resource Management in Mobile ad hoc Networks - the Spatial Dimension

本研究的目标是发展对移动系统中分布式计算的空间方面的全面理解。传统上，分布式计算中的事件是按时间排序的。标量时钟和矢量时钟用于表示逻辑时间和因果关系。然而，节点的移动性为问题注入了一个新的空间维度。移动网络中节点之间的物理距离和网络距离是不相关的。此外，移动网络中的一些无线链路可能是单向的。因此，与物理距离不同，节点之间的网络距离不是对称关系。最后，如果两个移动节点的请求根据它们与第三个（资源）节点的距离来确定优先级，那么它们的相对优先级会随着时间的推移而变化。这与基于时间的事件的不可变相对顺序形成对比。因此，如果距离是排序请求的标准之一，那么针对互斥（使用逻辑时钟）等问题的现有解决方案就不能有效地用于移动计算中的资源分配。我们将开发移动计算中事件之间时空关系的一种新的形式化表示。时空矢量是朝这个方向迈出的一步。一个基于时空坐标的可能不变的事件排序的理论将被发展。这样的请求排序可以用于资源无死锁、无饥饿和公平的资源管理。将在MAC子层开发新的协议，使节点能够使用单向无线链路进行通信。我们将开发新的路由协议，利用该MAC子层协议，在单向和双向链路相结合的无线移动网络中正确路由分组。随后，将通过仿真实验和原型设计来评估这些解决方案的性能。研究生和本科生将积极参与项目的每一个阶段。

The goal of the proposed research is to develop a comprehensive understanding of the spatial aspect of distributed computing in mobile systems. Traditionally, events in a distributed computation are ordered by time. Scalar and vector clocks are used to represent logical time and causal dependencies. However, the mobility of nodes injects a new spatial dimension into the problem. The physical and network distances between nodes in a mobilenetwork are not correlated. Moreover, some wireless links in a mobile network may be unidirectional. Hence, unlike physical distance, the network distance between nodes is not a symmetric relation. Finally, if requests of two mobile nodes are being prioritized on the basis of their respective distances from a third (resource) node, their relative priority can change with time. This is in contrast to the immutable relative ordering of events based on time. Hence, if distance is one of the criteria for ordering requests, existing solutions for problems like mutual exclusion (using logical clocks) cannot be efficiently used for resource allocation in mobile computing. We will develop a new formal representation of the spatial-temporalrelationship between events in mobile computing. Space-time vectors are a step in this direction. A theory for a possibly immutable ordering of events based on their spatial-temporal coordinates will be developed. Such an ordering of requests could be used for resource deadlock free, starvation free and fair resource management. New protocols will be developed at the MAC sub-layer enabling nodes to communicate using unidirectional wireless links. We will develop new routing protocols that utilize this MAC sub-layer protocol, and can correctly route packetsin a wireless mobile network with a combination of unidirectional andbidirectional links.Subsequently, the performance of these solutions will be evaluatedthrough simulation experiments and prototyping. Graduate and undergraduate students will actively participate in every stage of the project.