时延约束下的分批稀疏码设计及其性能限研究

BATched Sparse (BATS) code, which employs fountain code as outer code and network code as inner code, is a low complexity technique providing end-to-end reliability. Research work show that BATS code has the ability to provide the reliable transmission as well as to meet the requirement of transmission delay. At present, the study on delay performance of BATS code is still in the initial stage, and there is no exploration of BATS code with delay constraint. The project intends to investigate the intrinsic relationship among inner codes and delay distribution by considering the characteristics of WMNs and BATS. Our goal is to design the optimal BATS code with both high efficiency and low complexity under delay contraint. Towards this end, it includes: (1) Establish a BATS-based delay model for WMNs, and analyze the delay distribution in dynamic networks; (2) Study the behavior of achievable coding rate in dynamic networks by means of network information theory and the probabilistic method; (3) Build a joint optimization of achievable coding rate, delay, and energy to design inner codes by means of network coding theory and the optimization theory.

分批稀疏码（Batched Sparse Code）以喷泉码为外码，网络编码为内码，在降低复杂度的同时，能提供高效可靠的端到端通信。研究表明分批稀疏码有能力在保证数据传输质量的同时，满足传输对时延的要求。目前，针对分批稀疏码时延特性的研究还处于初步阶段，且对时延约束条件下的分批稀疏码设计问题尚无研究。本项目拟结合无线多跳网络和分批稀疏码的特点，深入研究内码与时延间的内在联系，设计和优化具有时延约束的高效低复杂度分批稀疏码方案。其包括：(1)建立无线多跳环境下分批稀疏码的时延模型，着重分析在能量和缓存等资源受限条件下的时延分布情况；(2)结合网络信息论和概率性方法，重点研究动态网络中分批稀疏码的可达编码码率；(3)建立基于可达编码码率、时延和能量等的联合优化模型，协同网络编码理论和优化理论，设计并优化内码算法。

本项目针对无线多跳网络，分析并揭示分批稀疏码的时延特性，研究不同约束条件下的秩分布规律，设计可实际应用的重编码方案，保证时延约束下端到端数据传输的可靠性和有效性。.针对分批稀疏码的时延特性，本项目主要考虑传输过程中的排队时延和处理时延。其中，排队时延与信息流的调度策略有关。为此，本项目研究了多跳无线网络中内码与调度的联合设计问题。首先引入了一种新的网络工具来将内码与调度联系起来，并利用图的独立集来表述编码约束和调度约束，并建立了网络效用最大化问题。通过分析该优化问题的性质，揭示了期望批量转移矩阵秩与最大独立集之间的关系。根据它们之间的关系，提出了联合编码和调度规则，并证明了周期性调度可用于实现可证明的性能保证。数值结果表明，所提算法能够接近多跳无线网络的利用率，且有较低的端到端延迟。.然后，考虑了处理时延与译码时延和译码成功率之间的关系。分批稀疏码只有当译码器接收到足够数量的编码数据包才能恢复出原始数据包，等待编码数据包的时间即译码延迟。本研究提出了一种累进编译码方案来减少译码时延，设计了一种自适应编码器（即AEW-BATS码)。针对AEW-BATS码在编码开销较小的情况下，解码性能较差。进一步建立了一个线性优化问题来优化每个扩展窗口的度分布。仿真结果验证了相比已提出的分批稀疏码，本研究的方法在降低译码时延的同时能够保证译码成功率不下降。.除了研究时延约束外，本研究还探讨了其他约束条件下的秩分布规律。具体的，研究了源节点和中间节点传输的数据包总数最小化问题。通过在不同的节点上允许不同的编码决策，该问题被建模为一个非线性整数规划(NLIP)问题。随后，推导了一个非迭代公式来简化期望批量转移矩阵秩的计算。通过考虑大有限域和放宽整数约束，得到了原最大化NLIP问题最优值的上界。本研究还分别推导了集中式和分布式算法来寻找NLIP问题的次优解，在复杂性和性能之间进行权衡。数值结果表明，提出的内码的性能优于标准BATS，并且非常接近于上界。