广播网络中的异或编码传输优化

考虑有一个编码节点R和两个目的节点DA，DB的广播网络，如图4-1所示。在该网络拓扑结构下，存在两条数据流：流A和流B，记该网络中流的数量为Flownum=2，对应为SA→DA和SB→DB，SA和SB表示两个源节点，DA和DB表示两个目的节点。P表示源节点SA经过中继节点R发送至目的节点DA的数据包，Q表示源节点SB经过中继节点R发送至目的节点DB的数据包。左右两个带点的箭头表示目的节点DB，DA能分别获得源节点SA，SB发送至中继节点R的数据包。

每个广播时间按间隙进行划分，它们之间的时间间隔为[t，t+1）。在每个时间段开始启动时，传输至目的节点DA或DB的数据包到达节点R。在每个时间槽内，许多数据包通过节点R进行传输。本章假定所有的数据包由一定长度的位数构成，且满足均匀分布条件。

图4-1　网络拓扑图(www.xing528.com)

数据传输率。当r≤ri，i=1，2时，目的节点i正确地接收所有传输过来的数据包。这里的收包为物理层的操作，如解调操作。便于研究，假定r∈{r1，r2}，且编码节点选取max{r1，r2}个编码后的数据包直接发送给两个目的节点。这样，对每个目的节点来说，最多数量的数据包在每个给定的时间槽内得到传输。

组群异或。为简化问题，以两个数据包x1，x2为例，异或编码操作是将这两个数据包进行逐位模2相加，表示为x1⊕x2。当目的节点缓存中包含参与编码的原始数据包时，目的节点就能准确对收到的编码数据包进行解码。以目的节点DB为例，当该节点缓存中存在数据包x1时，它就能对接收到的编码数据包x1⊕x2进行同样异或解码x1⊕（x1⊕x2），从而得到对应源节点发送的数据包x2。

数据包到达。源节点数据包在传输过程中具有如下特性：任何发送到目的节点DA（DB）的数据包到达节点R的同时，该数据包的拷贝以概率p1（p2）被目的节点DB（DA）接收。该概率对应于随机事件且相互独立。数据包分别以λ1和λ2的数据率进行传输。

假设目的节点缓存大小为D，编码节点为每条流分配的流虚拟缓存大小为M。在图4-1中，缓存大小为2，见图中深色方框部分；流虚拟缓存大小为3，见图中流透明部分。