基于网络编码的无线Mesh网络启发式定向调度算法研究

虞 洋

(宿迁学院，江苏 宿迁 223800)

0 引言

在无线网络中引入网络编码思想的研究成果显著，因为无线信道本质上具有“多发”特性，其广播特性使得无线网络应用网络编码具有先天性优势。利用网络编码，无线网络中各个节点相互配合，使得一个节点发出的信号达到其非目的节点时，不再被当作无用的干扰，反而成为提高传输效率的潜在动力。网络编码比较传统的存储-转发方式，多了一步编码译码过程。网络编码在提高网络吞吐量、减小传输延迟、改善负载均衡、增强网络鲁棒性以及节省节点能耗等多个方面都具有独特的优势，可以广泛应用于无线组织网、网络安全、应用层内容的分发以及分布式的文件存储等领域。现已有杨林等[1-2]、郝建军等[3]、刘晗[4]、汤恒胜等[5]从不同角度对网络编码研究。本文运用结合定向天线技术的网络编码对多接口多信道无线Mesh网络公平性优化进行了研究，对网络公平性问题进行了建模，并在此基础上提出了链路调度与信道分配算法D-LSCA。仿真实验表明，通过与已有算法进行对比，D-LSCA算法表现出的网络性能更优。

1 算法描述

假设k(a)是会话a的预设的流权重，a∈A，k(a)越大，会话a所需的流速率越高。假设λ是比例因子，优化的目标为寻求最大化λ使得会话a的λk(a)比例的吞吐量得到公平的调度。考虑公平约束、定向天线约束、链路流量约束、数据流保护约束、传输干扰约束、链路容量约束，最终形成线性规划模型Max Fairness LP。

假设节点的每一个定向天线都能够在一定时隙Ts内分配个固定信道，同时，每隔Ts时隙进行一次信道状态的更新。定义π(e)为链路e的调度，调度π(e)包括链路e在时隙t与信道m上，传输那种类型的数据流b。那么，π(e)可以看作是一个三元组(t,m,b)，其中，t表示不同的时隙，m，m∈M表示信道，b表示数据流类型，b=0代表单播数据流，b=1代表编码数据流。由于最优信道分配是一个NP-hard问题，因此，通过求解Max Fairness LP，进一步提出一个启发式算法对进行链路调度与信道分配。

所提的算法目的是寻求一组近似的可行解以优化网络吞吐量。该链路调度与信道分配算法的关键在于用尽量少的时隙完成数据流对信道的分配。信道每Ts时隙更新一次，因此，每个Ts时隙，该算法都将被执行一次。Max Fairness LP已经对单播流与编码流的分配给出了解，不需要在对每一个信道上的流进行分配，而是简单地将网络内所有单播流看作一条单播流，即：fU(e)=∑m∈MfmU(e)，类似地，也将所有信道上的编码流看作是一条编码流，即：fNC(e)=∑m∈MfmNC(e)。

2 算法实现

在每个调度时隙Ts内，先对编码流进行调度，再对普通单播流进行调度。在对编码流进行调度时，首先，对未分配的编码流进行降序排列；其次，将第一条编码流分配给能够提供最大流速率的信道。假如信道m空闲，并且链路两端节点在定向天线的传输范围内，调度成功。网络内的节点通过发送HELLO消息通知邻居节点自身的定向天线角度信息，接收HELLO信息的节点通过更新自身天线缓存表保存一跳邻居节点的天线信息，并更新定向天线指标函数数值。当所有该编码流完成信道的分配，算法将所有与编码链路ENC的链路设为0，以保证编码链路不会重复分配，同时，节点的天线个数也要减1。

D-LSCA通过上述循环直到所有的编码链路得到分配后，算法开始对单播流进行分配，分配方法与编码流分配方法相似。当网络内所有数据流都得到分配，算法调度时隙增加，进入下一个调度周期。

Max Fairness LP规划的解已经包含了每一个会话的路由信息，因此，链路调度与信道分配算法的最后输出即为链路调度、信道分配与路由的联合算法，通过该算法，能够获得每一次会话的最优吞吐量的近似解。

3 仿真实验与结果分析

本文将D-LSCA与已有的路由算法进行性能比较。为了更好地分析网络编码、定向天线带来的策略优势，仿真结果与SP-omni，COPE，DDSR这3种算法进行比较。本文的网络拓扑结构选择经典的32节点的随机网络。每个节点的天线数量固定为4，会话数固定为50。

实验1：考察四种算法的吞吐量指标。仿真结果如图1所示。从仿真结果可以发现，随着可用信道数量的增加，每一种算法的网络吞吐量也随之增加，其变化趋势基本一致。4种算法中，D-LSCA与COPE对吞吐量的提升效果接近，D-LSCA略优于COPE，其次是DDSR，效果最差的为SP-omni。

图1 吞吐量的变化

实验2：考察4种算法的公平性指标。仿真结果如图2所示。从仿真结果可以发现， D-LSCA在公平性方面明显优于其他3种算法。SP-omni完全没有对公平性的考虑，显然会导致网络不平衡问题。COPE性能的下降。DDSR优于前面两种算法，但仍劣于D-LSCA算法。虽然两种算法都运用了定向天线机制，但D-LSCA通过规划求解考虑了网络公平性问题，因此，能够为无线Mesh网络提供更好的公平机制。

图2 公平性的变化

4 结语

本文研究了定向天线技术、网络编码技术对多接口多信道无线Mesh网络公平性问题的影响。通过求解线性规划初步获得了编码流与普通单播流组合，并在此基础上进一步提出了链路调度与信道分配算法D-LSCA。通过与SP-omni，COPE，DDSR算法进行仿真对比实验，结果表明，D-LSCA算法在网络吞吐量以及公平性问题上优于对比算法，优化效果明显。