Mesh网络中网络编码技术的研究

1 第一章第一章 无线无线 MeshMesh 网络简介网络简介 一 无线一 无线 MeshMesh 网络的定义网络的定义 无线 Mesh 网络即 无线网格网络 是一种高容量 高速率的新型宽带无 线分布式网络 属于一种多跳 Multi Hop 网络 在无线 Mesh 网络中 任何无 线设备节点都可以同时作为接入点和路由器 网络中的每个节点都可以发送和 接收信号 传统的 WLAN 一直存在的可伸缩性低和健壮性差等诸多问题由此迎刃 而解 并且它可以与一个或者多个对等节点进行直接通信 又由于它是以一条 条较短的无线网络连接代替以往长距离的连接 从而保证数据可以以高速率 在节点之间快速传递 无线 Mesh 网络的广播特性为网络编码的应用提供了一 个很好的平台 网络编码能够缩短文件共享的时间 同时更好地利用网络资源 网络编码的文件共享在内容分发时间上明显优于没有网络编码的情况 这种结构的最大好处在于 如果最近的 AP 由于流量过大而导致拥塞的话 那么数据可以自动重新路由到一个通信流量较小的邻近节点进行传输 依此类 推 数据包还可以根据网络的情况 继续路由到与之最近的下一个节点进行传 输 直到到达最终目的地为止 与传统的交换式网络相比 无线 Mesh 网络去掉了节点之间的布线需求 但 仍具有分布式网络所提供的冗余机制和重新路由功能 在无线 Mesh 网络里 如 果要添加新的设备 只需要简单地接上电源就可以了 它可以自动进行自我配 置 并确定最佳的多跳传输路径 添加或移动设备时 网络能够自动发现拓扑 变化 并自动调整通信路由 以获取最有效的传输路径 2 图 1 1 主干 WMNs 图 1 2 桥接 WMNs 二 无线二 无线 MeshMesh 网络的优势和作用网络的优势和作用 与传统的 WLAN 相比 无线 Mesh 网络具有几个无可比拟的优势 1 快速部署和易于安装 安装 Mesh 节点非常简单 将设备从包装盒里取 出来 接上电源就行了 由于极大地简化了安装 用户可以很容易增加新的节 点来扩大无线网络的覆盖范围和网络容量 在无线 Mesh 网络中 不是每个 3 Mesh 节点都需要有线电缆连接 这是它与有线 AP 最大的不同 Mesh 的设计目 标就是将有线设备和有线 AP 的数量降至最低 因此大大降低了总成本和安装时 间 仅这一点带来的成本节省就是非常可观的 无线 Mesh 网络的配置和其他网 管功能与传统的 WLAN 相同 用户使用 WLAN 的经验可以很容易应用到 Mesh 网络 上 2 非视距传输 NLOS 利用无线 Mesh 技术可以很容易实现 NLOS 配置 因 此在室外和公共场所有着广泛的应用前景 与发射台有直接视距的用户先接收 无线信号 然后再将接收到的信号转发给非直接视距的用户 按照这种方式 信号能够自动选择最佳路径不断从一个用户跳转到另一个用户 并最终到达无 直接视距的目标用户 这样 具有直接视距的用户实际上为没有直接视距的邻 近用户提供了无线宽带访问功能 无线 Mesh 网络能够非视距传输的特性大大扩 展了无线宽带的应用领域和覆盖范围 3 健壮性 实现网络健壮性通常的方法是使用多路由器来传输数据 如果 某个路由器发生故障 信息由其他路由器通过备用路径传送 E mail 就是这样 一个例子 邮件信息被分成若干数据包 然后经多个路由器通过 Internet 发送 最后再组装成到达用户收件箱里的信息 Mesh 网络比单跳网络更加健壮 因为 它不依赖于某一个单一节点的性能 在单跳网络中 如果某一个节点出现故障 整个网络也就随之瘫痪 而在 Mesh 网络结构中 由于每个节点都有一条或几条 传送数据的路径 如果最近的节点出现故障或者受到干扰 数据包将自动路由 到备用路径继续进行传输 整个网络的运行不会受到影响 4 结构灵活 在单跳网络中 设备必须共享 AP 如果几个设备要同时访 问网络 就可能产生通信拥塞并导致系统的运行速度降低 而在多跳网络中 设备可以通过不同的节点同时连接到网络 因此不会导致系统性能的降低 Mesh 网络还提供了更大的冗余机制和通信负载平衡功能 在无线 Mesh 网络中 每个设备都有多个传输路径可用 网络可以根据每个节点的通信负载 情况动态地分配通信路由 从而有效地避免了节点的通信拥塞 而目前单跳网 络并不能动态地处理通信干扰和接入点的超载问题 5 高带宽 无线通信的物理特性决定了通信传输的距离越短就越容易获得 高带宽 因为随着无线传输距离的增加 各种干扰和其他导致数据丢失的因素 4 随之增加 因此选择经多个短跳来传输数据将是获得更高网络带宽的一种有效 方法 而这正是 Mesh 网络的优势所在 在 Mesh 网络中 一个节点不仅能传送 和接收信息 还能充当路由器对其附近节点转发信息 随着更多节点的相互连 接和可能的路径数量的增加 总的带宽也大大增加 此外 因为每个短跳的传输距离短 传输数据所需要的功率也较小 既然 多跳网络通常使用较低功率将数据传输到邻近的节点 节点之间的无线信号干 扰也较小 网络的信道质量和信道利用效率大大提高 因而能够实现更高的网 络容量 比如在高密度的城市网络环境中 Mesh 网络能够减少使用无线网络的 相邻用户的相互干扰 大大提高信道的利用效率 因此 无线 Mesh 网络不论在家庭 企业还是公共场所等领域都具有广阔的 应用前景 第二章第二章 网络编码的分析与研究网络编码的分析与研究 一一 网网络络编编码码 N Ne et tw wo or rk k C Co od di in ng g 的的定定义义 传统的通信网络传送数据的方式是存储转发 即除了数据的发送节点和接 收节点以外的节点只负责路由 而不对数据内容做任何处理 中间节点扮演着 转发器的角色 长期以来 人们普遍认为在中间节点上对传输的数据进行加工 不会有任何收益 然而R Ahlswede等人于2000年提出的网络编码理论彻底推翻 了这种传统观点 他们从信息论的角度出发 严格证明了 网络编码可以帮助 我们达到通信网络的最大容量 从而最大限度的利用网络的现有资源 网络编码是一种融合了路由和编码的信息交换技术 它的核心思想是网络 节点不仅参与数据转发 还参与数据处理 可大幅提高网络性能 根据图论中 的最大流 最小割定理 数据的发送方和接收方通信的最大速率不能超过双方之 间的最大流值 或最小割值 如果采用传统多播路由的方法 一般不能达到该 上界 R Ahlswede等人以蝴蝶网络的研究为例 指出通过网络编码 可以达到 多播路由传输的最大流界 提高了信息的传输效率 从而奠定了网络编码在现 代网络通信研究领域的重要地位 目前为止 网络编码作为一种提高网络吞吐量的有效方式 已经取得了巨 5 大的进展 网络编码将传统网络中节点只能转发或存储数据的性质进行了扩展 允许节点对来自不同链路的数据包进行编码组合 使得网络性能可以达到最大 流传输的理论极限 从而最大限度地利用网络资源 网络编码不但可以用在组 播通信网络中而且还可以用在非组播网络中以提高网络容量 Katti 等人就提 出一种提高无线网络单播通信吞吐量的网络编码技术COPE 并给出它的一个具 体实现方案 另一方面 网络编码在提高网络的通信容量的同时 在负载均衡 降低能量消耗等方面也有不容忽视的作用 二 网络编码的工作原理二 网络编码的工作原理 网络编码作为一种新的技术在宽带无线自组织网络中有很好的应用 通过 网络编码 中间节点可以将接收信息进行编码并发送出去 提高了网络吞吐量 和健壮性 为不对现有网络的软硬件设备和相应的协议做很大的修改 可以选 择在高层实现网络编码 无线传感器网络 无线格状 Mesh 网等无线自组织 网络都可以使用网络编码技术显著提高多跳链路的传输性能 式网络中的应用 等方面 目前网络编码的研究热点集中在网络编码节点选取方案 网络编码算 法的设计 网络编码复杂度分析 网络编码的性能分析 网络编码与系统安全 性分析 网络编码在无线分布 其基本工作原理是把不同的信息转化成位数更小的 痕迹 然后在目标节 点进行演绎还原 这样就不必反复传输或者复制全部信息了 痕迹可以在多个 中间节点间的多条路径上反复传递 然后再被送往最终的目的端点 它不需要 额外的容量和路由 只需把信息的痕迹转换成位流即可 而这种转换现有的网 络基础设施是可以支持的 从广义上来讲 就是网络中的节点将接收到的信息进行编码后再转发出去 的多点传送技术 多点传送 也称组播 是网络中的一种重要的通信方式 当 一个或几个节点同时向若干个其他节点发送数据时 往往要借助其他节点的传 递 网络编码技术打破了传统限制 它允许中继节点对接收到的信息进行编码 并将接收到的多个数据包按照某种特定算法重新组合再发送出去 如图2 1所示 为一无线通信领域3节点拓扑的实例 节点A 节点B相互传递信息a b 图2 1 中的箭头代表有向链路 假设每条链路的容量为 1 图2 1 a 采用传统的 通信方式 A首先向S发送信息a 然后B向S发送信息b S然后依次把信息a和b分 6 别广播给节点A和节点B 这样经过4条链路的传输节点B可以获得信息a 而节 点A可以获得信息b 但是当信息a和b准备通过节点S进行转发时 如果应用网络 编码技术 将a和b作模2和运算后直接转发出去 则在节点B处 根据接收到的信息 可恢复出a来 同理 在节点A处也可以恢复出信息b来 从而可以译码得到信息 b 采用了网络编码技术后 见图2 1 b 只需要使用3条链路就可以实现传统 方式的所有通信要求 从实例可以看出 网络编码技术可以显著地提高多点传送 的数据率 图 2 1 无线单播系统传统传输方式与网络编码技术比较 按网络编码的构造方式分 主要有两种 一种是由R K oetter和M Medard 给出的网络编码的代数构造方式 这种构造方式是在知道整个网络的拓扑信息 的情况下 用一个系统转移矩阵来描述信源输入信息和信宿上接收到的信息之 间的关系 并通过构造符合要求的系统转移矩阵来实现网络编码 另一种是 P Sander 等人提出了一种实现网络编码的多项式时间算法这种方法将网络编码 的构造进一步简化 它也是在己知拓扑的情况下 首先通过最小割最大流算法 找到完成组播所需的路径的集合 在找出的这个子图上 再自上而下的确定各 个节点所需要进行的操作 其次 网络编码又可以分为线性和非线性两大类 其中线性方法的编码和解码都相对简单 因此 一般都倾向于用线性方法 Li 指出在有向网络中 如果一个网络编码问题有解 则一定有线性解 从理论上 保证了线性算法的有效性 三 三 无线无线 MeshMesh 网络中网络编码的文件共享模型网络中网络编码的文件共享模型 在这里的文件共享模型中将发送机制分为盲转发 BF 带网络编码的盲转 送 BF NC 选择性转发 SF 带网络编码的选择性转发 SF NC 4种类型 其 中前两种机制是最大限度发送 不管网络中的节点对其要发送的数据是不是需 要 盲转发没有采用网络编码 而带网络编码的盲转发是在节点接收到数据以 7 后 产生要发送的数据块的线性组合 与盲转发不同 选择性转发机制是在节 点含有邻近节点需要的数据块情况下才转发 1 盲转发 当节点接收到一个新的数据块 获取媒质接人机会后 盲目地向邻近节点 转发数据块 即使没有一个邻近节点对它拥有的数据块感兴趣 只要监听到信 道空闲 就按接收的次序调度发送 先接收到的先发送 2 带网络编码的盲转发 与第一种很相似 仍然是基于盲目转发的机制 所不同的是节点向邻近节 点转发数据块的线性组合 即是网络编码后的数据块 3 选择性转发 节点周期性地查询接收报表 如果至少有一个邻近节点对它所拥有的数据 块感兴趣 那么转发数据块 而且优先发送熵最大的数据包 每个节点维持一 个接收报表 该表提供每个邻近节点数据块的完全信息 通过与邻接节点交换 信息来建立 维持和更新这些报表 4 带网络编码的选择性转发 与选择性转发一样 节点选择性地转发数据块 所不同的是发送的是网络 编码后的数据块 用实验仿真的结果进行分析 假设节点之问的发射功率是固定的 发射半径 网络中的所有节点分 4R 布在面积为S的区域里 模型的网络节点数目为N N满足不等式 本文的网络节点数 2 10S N R 将文件分成大小相等的数据块 假设同一个时间片 2 10S N R 100 20 60C 里 网络系统中信源的数量 信源的位置为 即信源的位置可以在面 1 n S p S 积为S的区域里的任何位置 假定网络中的丢包率为L O 为了更方便地研究上 述方案对网络吞吐量的改善 采取C 编程进行分析 实验仿真运行在理想的 8 802 11MAC协议上 信道没有任何损耗 网络中的节点公平地获得媒介接入机 会 图2 2 图2 3分别表示采用盲转发机制 选择转发机制时 网络编码和数 据块数目对文件分发时间的影响 图2 4表示4种不同机制对网络性能的影响 图2 2 盲转发机制 节点数与传输时间的关系 图2 3 选择转发机制 节点数与传输时间的关系 9 图2 4 4种机制 节点数与发送时间的关系 根据上图可得出以下结论 1 网络编码可以加速内容的分发 减少服务时间 节约无线网络的带宽 2 在节点数目中等或多的情况下 网络编码更能体现其优势 这是符合逻 辑的 因为当网络中的节点数目增多时 节点可从更多的邻近节点接收数据块 和网络中的信息将变得多样化 因此 从每次传送中获取的增益将更大 3 增加数据块的数目将改进系统性能 事实上 当把文件分为多个数据块 的时候 节点只要下载完整数据块就开始传送数据块 而不必等到下载完整文 件 因此 数据块越多 节点越快进人分发过程 系统的性能越好 4 节点间的合作策略影响网络编码对网络性能改善程度 从图2 4中可以 看出 SF NC SF的合作策略比BF NC BF能更好地提高网络吞吐量 相同条 件下 SF NC比SF的文件分发时间平均减少8 34 BF NC的文件分发时间比 BF平均减少15 结果证明 网络编码在选择性发送机制下能够提高系统容量 就系统传输 时间来说 基于网络编码的机制优于无网络编码的机制 这是因为网络编码减 少传输次数 可以达到最大的网络容量 四 无线四 无线meshmesh 网中网络编码的按需无线路由协议网中网络编码的按需无线路由协议 现在 学术界又提出一个支持无线网络编码技术COPE 的按需路由协议 OCR 以提高无线mesh 网中的网络吞吐量 在路由发现过程中 该协议主动地 探测编码机会并灵活地寻求 增加编码机会 最短路径 以及 避免拥塞 10 之间的折衷 用实验仿真的结果进行分析 可以使用通用的网络仿真平台NS2 对下列3 种传输方式进行仿真比较 1 COPE OCR 利用OCR 协议建立路径后将COPE 应用在网络的数据传输中 2 COPE AODV 利用AODV 协议建立路径后 应用COPE 同上述传输方式 3 AODV 使用AODV 协议建立路径 在数据传输过程中没有任何技术对其支 持 其中 方式1 在NS2 上独立设计实现 方式2 在NS2 28提供的AODV 源码上 实现 方式3 使用NS2 28 提供的源码 仿真参数设置如下 MAC层协议采用 IEEE 802 11 DCF 信道容量为2Mbit s 节点的传输范围为250m 节点的数据 发送队列大小为50 数据源为CBR 流 数据包大小为512byte 为了直观地说明OCR 协议的优点 本文首先在固定一个网络拓扑的前提下 比较上述3 种传输方式的性能 将该拓扑假设为某高校的校园网 在1200m 1200m 的场景中均匀地分布着61个静止节点 任意2个相邻节点间距离为150m 每次实验时间为600s 间隔5s 依次生成10条随机的数据流开始数据传输 数据 发送速率从8kbit s 逐渐增长到112kbit s 选择20个不同的速率值以模拟不同 网络负载的情况 图2 5 不同数据流量下3 种传输方式的网络吞吐量变化 11 图2 6 不同数据流量下3 种传输方式的平均端到端延迟变化 图2 7 编码数量变化 图2 8 解码出错数量变化 12 图2 9 随机网络中的编码机会数量统计 图2 5和图2 6分别显示了不同数据发送速率下的3 种传输方式的网络吞吐 量变化以及平均端到端延迟变化 通过观察图2 5和图2 6可以看出 COPE AODV 和AODV 的网络吞吐量和平均端到端延迟曲线整体区分并不是非常明显 大部分 时候基本重合 而从数据发送速率大于20kbit s 开始 由于网络负荷开始增 大 冲突开始出现 路由节点的发送队列中开始积累数据包 此时拥有较多编 码机会的COPE OCR 方式的优势开始体现 从图2 5和图2 6 中可以看出 此时 COPE OCR 与COPE AODV 和AODV 的网络吞吐量曲线和平均端到端延迟曲线区分 开始明显 直至数据发送速率大于112kbit s 以后 由于网络严重拥塞 此 时COPE OCR 对网络吞吐量的提高才变得十分有限 7 2 左右 图2 7和图2 8分别显示了不同数据发送速率下COPE OCR 与COPE AODV 的节 点编码数量和解码出错数量的变化 从图2 7和图2 8可以看出 随着数据发送 率的增加COPE OCR 的编码次数和解码出错次数均远远大于COPE AODV 而 COPE OCR 由于比COPE AODV 拥有更多的编码机会 此时网络并没有拥塞 仍 处于良好传输的状态 观察图2 5 图2 7 和图2 8可以看出 在这个阶段 COPE OCR 下的网络吞吐量 编码数量以及解码出错数量继续保持上升趋势 通 过对3种方式下网络传输的仿真结果分析可知 随着网络负载的增加 3种传输 方式下的网络都经历了从空闲到拥塞的过程 但COPE AODV的网络吞吐量与AODV 相比 并没有太大的提高 AODV的部分相关代码如下 ifndef aodv rqueue h define aodv rqueue h include 13 include include The maximum number of packets that we allow a routing protocol to buffer define AODV RTQ MAX LEN 64 packets The maximum period of time that a routing protocol is allowed to buffer a packet for define AODV RTQ TIMEOUT 30 seconds class aodv rqueue public Connector public aodv rqueue void recv Packet Handler abort void enque Packet p inline int