BATS codes are a class of efficient random linear network coding variation that has been studied for multihop wireless networks mostly in scenarios of a single communication flow. Towards sophisticated multi-flow network communications, we formulate a network utility maximization (NUM) problem that jointly optimizes the BATS code parameters of all the flows and network scheduling. The NUM problem adopts a batch-wise packet loss model that can be obtained from the network local statistics without any constraints on packet loss patterns. Moreover, the NUM problem allows a different number of recoded packets to be transmitted for different batches in a flow, which is called adaptive recoding. Due to both the non-convex objective and the BATS code-related variables, the algorithms developed for the existing flow optimization problems can not be directed applied to solve our NUM problem. We introduce a two-step algorithm for solving the NUM problem, where the first step solves the problem with nonadaptive recoding schemes, and the second step optimizes adaptive recoding hop-by-hop from upstream to downstream in each flow. We perform various numerical evaluations and simulations to verify the effectiveness and efficiency of the algorithm.
翻译:BATS 代码是一个高效随机线性网络编码变异的类别,主要在单一通信流的情况下对多光线网络进行了研究。在复杂的多流网络通信方面,我们设计了一个网络效用最大化问题,共同优化所有流动和网络调度的BATS代码参数。NUM问题采用分批的包损失模型,可以从网络本地统计中获得,而不受包损失模式的限制。此外,NUM问题允许为流动中的不同批次(即适应性重新编码)传输不同数量的重新编码包。由于非编码目标以及与BATS代码相关的变量,为现有流量优化问题开发的算法无法用于解决我们的NUM问题。我们引入了一种分两步算法来解决NUM问题,第一步解决了非适应性重新编码计划的问题,第二步则优化了从上游到下游的适应性再编译包。我们进行了各种数字评估和模拟,以核实算法的有效性和效率。