Switch-and-Navigate: Controlling Data Ferry

We consider the problem of controlling mobile data ferries for message delivery among disconnected, scattered domains in a highly partitioned network. Existing work on data ferry control mostly focuses on predetermined ferry routes, assuming full observations at the ferry and no explicit Quality of Service (QoS) constraints on the resulting communications. In this paper, we aim at designing a QoS-enabled ferry control solution, which handles both partial observations and bounded message delays. To this end, we extend our previous work on data ferry control with partial observations into a comprehensive hierarchical framework called Switch-and-Navigate (SAN), which consists of a global switch policy for determining the best domain to visit and a local navigation policy per domain for searching for nodes within individual domains. Under the assumption of Markovian node mobility, both the global and the local control problems are formulated as Partially Observable Markov Decision Processes (POMDPs) to maximize the discounted effective throughput over all domains. Due to the fact that the optimal solution to POMDP is PSPACE-hard, we develop heuristic policies and further approximations for efficient computation. Simulation results show that the proposed policies can significantly improve the performance over predetermined alternatives. ### Switch-and-Navigate: 控制数据摆渡在有界消息延迟下的移动性 #### 概述 本研究探讨了在高度分区的网络中控制移动数据摆渡（数据摆渡指的是在网络断开连接的不同域之间传输数据的移动节点）的问题。传统上，数据摆渡控制的研究主要集中在预设的数据摆渡路径上，假定了摆渡节点可以全面观察到网络状态，并且没有明确的服务质量（QoS）约束。本论文旨在设计一种能够处理部分观察和有界消息延迟的QoS感知数据摆渡控制方案。 #### 核心贡献 为了解决这一问题，研究团队提出了一种名为“Switch-and-Navigate”（简称SAN）的综合分层框架。该框架包括两部分：全局切换策略用于决定访问哪个最佳领域，而每个领域的本地导航策略则负责在各自的领域内寻找节点。为了最大化所有领域的折扣有效吞吐量，在假设节点移动符合马尔可夫过程的情况下，将全局和本地控制问题都建模为部分可观测马尔可夫决策过程（POMDP）。考虑到POMDP的最佳解决方案是PSPACE难的问题，研究人员开发了启发式策略和进一步的近似算法来实现高效的计算。 #### 技术细节 - **问题背景**：在高度分区的移动自组织网络（HP-MANET）中，由于物理障碍、有限的无线电传输范围、恶劣环境条件或安全原因，网络被分割成多个永久断开连接的自治领域。这种环境下，传统的通信方式变得不可行，因此需要一种能够跨越这些分割区域的数据传输机制。 - **现有工作**：大多数现有的数据摆渡控制方法关注于预设的摆渡路径，并假定摆渡节点具有完整的网络观测能力，缺乏对QoS的显式考虑。 - **QoS感知控制方案**：本研究提出了一个能够处理不完全信息和限定消息延迟的控制方案。通过引入SAN框架，不仅解决了如何在不同的领域间进行有效的选择，还提供了如何在单个领域内部高效搜索目标节点的方法。 - **模型构建**：在假设节点移动遵循马尔可夫过程的基础上，利用POMDP对全局和局部控制问题进行了建模。这有助于在不完全信息条件下做出最优决策，从而提高整体的有效吞吐量。 - **优化策略**：考虑到POMDP的求解复杂度很高，研究团队设计了启发式策略和近似算法，以实现更高效的计算过程。这些方法在保持一定精度的同时，大大减少了计算时间。 - **实验验证**：通过模拟实验验证了所提出的策略相对于预设路径方法的显著性能提升。实验结果表明，在不完全信息和有界消息延迟的约束下，SAN框架能够显著提高数据摆渡控制的有效性和效率。 #### 结论与展望 本研究提出的Switch-and-Navigate框架为解决高度分区网络中的数据摆渡控制问题提供了一个新的视角。通过结合全局切换策略和本地导航策略，以及利用POMDP进行优化决策，该方案能够在不完全信息条件下实现高效率的数据传输。未来的研究可以进一步探索更多类型的网络环境和更复杂的QoS需求，以扩展该方案的应用范围。