开始跟着实验室研二的学长学东西。因为线代概统这些课都没学，要搞的还挺多。拿到了一本网络编码的书和一些论文，当然还有补课的一些材料。
在学线性代数，希望能在这两个星期把这本书过一遍，搞清楚网络编码大概的框架。
《网络编码研究基础》
ISBN 978-7-115-43562-0
想法、初步的问题以及后续再读时需要详细了解的点，将通过引用框的形式列出，
0. 前言
数据在网络中通过拆分成包进行传输，路由结点可以将接收到的数据原样转发出去，也可以编码后再转发。牺牲一部分算力用于编解码，可以通过提高网络吞吐率、健壮性、安全性来提升传输性能，同时实现网络均衡。显然一个好的编码方案要关注的也是这几个方面。
编码是信息从一种形式转换到另一种形式的映射过程。
1. 绪论
几个转发技术
- 单播：一对一传输
- 广播：单源点向所有其他点发送数据
- 多播（组播）：单源点向特定多个点，或多源点向特定多个点发送
各自的优缺点？
多播和人的社会互动形式最接近。
网络编码
一种数据传输技术，中间结点可以选择直接转发经手的数据，或进行编码后再转发。
路由是一种特殊的网络编码？
主要相关学科：计算机网络、信息论、图论、线性代数。
新的方案有必要兼容现在通用的网络结构，或者提供尽可能小的转换成本。
信息传输速率的瓶颈显然是整个路径中最慢的一个/几个环节。数据在网络中多播传输的路径是树或森林（多源点），构造这样的树是 NP 问题。
NP 还是 NPC？
线性网络编码通过将结点接收的信息进行线性组合后再转发，编码方式可以通过向量代数的理论进行证明。
当接收带宽大于发送带宽时，可以考虑的一种方法是各节点将接收的数据压缩后转发，传出的数据大小减小，信息不变（无损压缩时）。线性网络编码是这样的一种“压缩”技术吗？这似乎不符合流的守恒（流出 = 流入）
蝴蝶网络演示线性网络编码
蝴蝶网络是一个 有向 无环 单源 多播 网。每个多播的宿点都收到了同样的数据，则宿点可以接收这样的一种包：它的大小与正常的包一样，但是可以根据宿点拥有的信息进行“补全”。牺牲宿点的算力，收益是部分信道可以只发送固定内容的包，而不是分片依次发送，这样可以提高传递信息的效率。
直接拿到信息所用的时间中，有一部分被分摊到了编解码上。传递的效率确实提升了，问题是宿点“获得”信息的效率是否提升。
网络编码传输的优点基本是构造最优传输时所追求的那几点，缺点是算力要求（属于边缘计算？），传输编解码策略实际上也需要占用带宽（通过写进协议等方法预置？安全性？）
网络编码和其他编码的区别
- 信源编码：压缩信息再传输
- 信道编码：降低噪声干扰？
- 加解密：防窃听
以上三种基本不在中间结点改动数据。
线性网络编码和非线性网络编码
定义一个信息集合，编码运算对它应该是封闭的。有限域比较符合。
否则解码规则不能正确识别？或者对封闭系统的研究比较成熟？
存在从线性编码网络构造非线性编码网络的方法。
线性编码比非线性好算。
代内编码和代间编码
一个数据块的信息从源点传输到宿点并完成解码的过程称为一代。代内编码只会包含当前块的数据，代间编码还会包含向前若干代的数据。一代解码失败时（数据损坏），代内编码需要重传该代信息，代间编码只要传递该代的部分信息。
一种冗余？包含前几代的编码块一定比代内小？“部分”信息如何从该代确定并拆分出来？期间的效率？
2. 相关理论与技术
多播连接：一个过程，过程中源点同时传输数据至所有宿点。基于网络编码的多播连接要求一个有向图，图中源点到任意宿点的最小割不小于多播率。
同步方式传输：每个结点接收全部输入信道的信息后才开始编码转发。
多播容量：同步传输时，各宿点能同时完整正确接收信息的前提下，源点的最大发送速度，即最大流。
多播率：实际发送速率。
最大流最小割定理：最大流等于最小割。
图论内容和运筹学（优化理论）内容。随机化搜索。
有限域及其运算。离散和线代内容。
验证方法：仿真测试。几个生成测试网络的算法和作者的改进。
3. 线性网络编码
结点将输入数据线性组合后发出。组合在字符集上封闭。
数学表达以及归纳证明，线性代数内容。 $GF(2^m)$
传输多字符时模型的修改。
构造网络编码方案的目的：确定各结点的编码方式、宿点的解码方式。
对于已知拓扑结构的单源多播网络，可以确定构造网络编码，通过矩阵运算解码。
结构未知或变动大时，还要利用信道传输相应的全局编码向量。数学上宿点有概率不能解码，通过调整有限域的阶来降低这个概率。
随机性网络编码和确定性网络编码的传输方法。
仿真实现：Windows 套接字编程函数。确定性和随机性编码的代码。
Python 行不行？相关的库？
感性地理解，网络编码是在数据传输过程中应用的一种融合技术，通过将待转发的信息“融合”在一起，提高结点一次转发中包含的信息量，因此“压缩”不是必要的效果。编码方案就是“融合”和“拆分”的策略，构造编码方案涉及图论、线性代数等知识。
4. 线性网络编码的导出与扩展
已知网络拓扑可以先求出多播率和编码系数再传输，未知时要用 Random Network Coding。
实际应用中的几个问题：
- 同一单源多播网络，每代的多播率需要变化，增加了计算量，保存每个多播率下的编码系数也需要空间
- 有分布式计算最小编码信道数的方法（启发式和 RNC 结合），但也只能求信道数而不能构造方案，且需要给定一个可行的多播率
- 部分文献和方法假定了多播率已知
现行的多播方案是如何确定多播率的？路由器的工作原理？
多播率应该尽量大（逼近/达到多播容量），以提高吞吐率。需要动态测试多播容量。
编码方案的导出和扩展技术：给定多播率和对应编码方案，可确定求出较大多播率和较小多播率的方案。
所以有未知拓扑下无假设地求出总体/局部多播率的方案吗
导出的较小多播方案类似于矩阵截断，取前缀。
几个证明，后面补上。
所以，多播率减小时只需要截取原来的矩阵即可得到新的适用矩阵。
导出较大的多播方案，定理 4.5。一个 $O(n^2)$ 的算法。
仿真测试部分。
成功测得多播容量的概率如何计算，在任何网络拓扑下都可以接受吗？
参考文献有点老？
5. 未知网络拓扑环境下最大吞吐率的网络编码多播
全局网络拓扑对源点不可知，宿点可以向源点反馈信息的网络，结点有足够算力和存储空间。分静态和动态网络拓扑讨论。
反馈时也属于通信过程，这里如何编码？
对于静态：源点随机试播，根据反馈信息调整。对于动态：传输数据时通过反馈来动态测试多播容量并调整多播率。
听起来不够健壮。
静态拓扑方案
蒙特卡罗方法试播， 当一定次数或临时容量比较稳定后停止，源点计算编码方案并广播多播率，宿点计算逆矩阵。
传输延时可能很高
有效性分析和仿真测试。
动态拓扑方案
基于重传和变多播率的随机线性网络编码方法（RNC-RVMR）：
- 宿点不能解码时，反馈到源点，源点重传
- 全局编码向量维数与源点输出信道数相等
基本思想：同时进行两个多播率的数据传输，一个测试，一个传数据。两者互为导出关系。
具体实现和证明。
仿真。
6. 网络编码优化构造研究
参与编码的结点数和信道数对效率有比较大的影响。指定吞吐率下确定最小编码结点数是 NP 问题，使用启发式。
一个优化方法：分布式测出多播容量，再使用遗传算法分布式构造最少编码信道方案，最后用确定性策略传输。主要手段：减少编码信道数，目的：减少编码代价。
减少编码信道数会不会影响吞吐率？
处理 NP 问题常用启发式搜索。
遗传算法的细节，基因片段存在各结点里。
搜索的效率
多播率和结点数互相制约。双目标优化问题。
网络编码的动机就是，在提升多播率的同时，减少传输过程中整个网络的状态需要转移的次数（一般代表各结点的一次转播/接收，这通常代表要消耗的时间）。状态之间的区别是，存在结点，它接收/转发的数据发生了变化。
7. 网络编码运算代价的估算与分析
时间复杂度分析和环境影响。
有限域的除法运算。
注意到一个结点会参与多个多播。
硬件电路计算有限域除法比较快，或者查找乘法表。但是两者都随有限域变化，考虑从有限域的代数结构出发。
以硬件时间为单位，计算加减乘除异或的时间复杂度。
求逆的复杂度。只考虑了高斯消元法。
估算整个编码方案的复杂度。
仿真验证计算结果。
8. 基于分级网络编码的一种数据传输方法
单极网络编码方法：源点播出信息，各结点转发，宿点收到所有信息后解码。
- 网络运算延迟不可忽略，且与有限域的次成平方关系，而有限域的阶不能小于宿点个数。
- 单级传输的多播率受最小割的限制
- 有限域的次只与宿点个数相关？
基于以上两个事实，减少宿点个数可以降低有限域的阶，而分主干网-子网进行多次解码编码传输可以将运算量分散，减少宿点的个数。
定义 8.1 单源多播网络存在主干网 - 子网结构时，数据在主干与子网的连接点解码，由连接点重新编码多播给其下的宿点。
如何区分主干？依据信道的容量？
如果考虑“极致”的分散运算，信息在每个中间结点都重新编解码一遍？
分级多播率优越性证明。
最小割的影响被限制在一个区域（子网/主干网）里
利用多播率在连接点出（可能）产生的变化，可以进行缓存转发（大变小）或“插播”（小变大）。
仿真
这是需要假设网络拓扑是一棵有根树吗
9. 基于随机线性网络编码的差错控制
网络编码的纠错。属于完善部分。
普通传输是如何纠错的？
几个名词：前向纠错、海明界（汉明码？）
网络编码的特点，出错可能在传输内容（信息/编码向量）的任一部分，出错的输入信道数据会在编码“压缩”时污染全部输出。
点-点检错 + 端-端重传，三维奇偶校验和反馈信道
三维奇偶校验
为什么用三维？校验位更多吗？
信息位构造成一个立方体矩阵，长宽高各增加1，利用多出来的三个相邻的层面记录校验位。生成和检验都是线性时间（$N = (a + 1)(b + 1)(c + 1)$）显然存在需要增加信息位凑成最小立方体的情况。
不能检出的错误：某个子立方体的八个顶点同时出错。
计算可知无法检错的概率量级在 $10^{-10}$ 以下。
如何选择立方体的尺寸。
有效性证明和仿真测试。
10. 多源多播网络编码优化的构造研究
多源多播构造编码的方法。
多源多宿多播（Multi-Source Multi-Sink Multicast）：宿点接收来自所有源点的数据，每个源点对应相同宿点集
一般多源多播：每个源点对应不同宿点集
多源多宿多播
构造一个含约束的单源多播问题（派生问题），证明等价性，将确定各源点多播率的问题转化为背包问题。求出多播率后，在单源多播确定性网络模型下构造编码。
添加一个根，以各源点为子结点，向它们分发数据。LIF 算法。问题是选取一组根向各源点广播数据的容量。组合优化问题。搜索算法。
普通的动态规划可行吗？
一般多源多播
还没有完全解决。从简单的拓扑结构入手。
划分子图的方法，各子图的边不重叠，每个子图包含且仅包含一组源点和对应宿点集，则特化成单源多播（多播森林）。数学问题。
从此处开始需要知道全局拓扑？
必须要求得可达信息率区域。