改进的无线多跳mesh网络数据分发算法

周 宇，杨 维

（北京交通大学 电子信息工程学院，北京100044）

0 引 言

现有的无线mesh网络在尽可能提高系统吞吐量的同时，要保证传输的实时性和稳定性，也就是降低系统时延［1－3］。

现阶段研究无线mesh网络的文献中许多都是关于网络构建的，对mesh节点间数据分发机制的研究比较少。对于无线mesh网络中的数据分发问题，有学者提出了一些经典数据分发的策略［4］。这些策略的主要思想分为3 种：第1种是通过组播树的方式，以 “推”的方式主动发送数据，但是由于一直在主动发送数据，数据块会重传输，造成网络资源不合理利用，吞吐量下降；第2种是通过 “拉”的方式，在某个节点需要数据的时候向相邻节点请求数据，这种方式主要的问题是请求数据的时延会比较大；第3种是第1种和第2种的结合，可以在一定程度进一步上降低控制信息开销和减少数据传输时延［5］，但是对算法要求较高，实际无线mesh网络中不宜采用。本文主要是在第2种Mesh－Pull算法基础上，综合考虑了传输时延和吞吐量对于网络性能的影响，提出一种改进的BMesh－Pull算法，改善无线mesh网络数据传输性能。

1 现有Mesh－Pull算法的问题

Mesh－Pull算法核心就是调度节点在请求数据的时候给邻居节点发送请求消息，邻居节点收到请求信息之后再发送需要的数据块给调度节点。Mesh－Pull这种分发方式不需要考虑整个网络中的节点信息，但是存在的问题是不一定当前时刻传输的数据块是用户最需要的，而用户最需要的数据块却有可能一直在缓存区等待传输，造成很大的传输时延。这样的数据传输方式就会造成用户观看视频时候的不流畅，影响用户体验。同时，带宽往往能决定网络的容量和传输效率，带宽衰减越小的网络传输效率也会越大［6］。对于无线mesh网络数据传输而言，要保证数据传输的连续性，就需要严格控制噪声引起的信号衰减［7，8］。

图1建立了无线mesh网络中的数据分发方式模型。其中给每个邻居节点缓存的数据块编号，不同的编号表示每个节点缓存含有不同的数据块。在Mesh－Pull的算法中，调度节点i开始发出数据请求信息，调度节点i就与相应的邻居节点交换可用数据的消息，同时查看该邻居节点是否含有请求的数据块，邻居节点如果拥有该数据块，就会告诉请求节点自己有该数据块，这时请求节点就会从所有含请求数据块的邻居节点中选择最合适的邻居节点请求数据，完成后再进行下一轮数据请求。

图1 Mesh－Pull的数据分发方式

从Mesh－Pull分发方式可以看出，每一次数据请求过程中，发送请求和响应请求都需要等待一段时间，这样就会造成网络传输时延较大，吞吐量较低，影响网络传输性能。

2 改进的BMesh－Pull数据分发算法

改进的BMesh－Pull算法是在Mesh－Pull算法的基础上，综合考虑了传输时延和吞吐量对于网络数据传输的影响。其核心思想是在建模中通过优先级调度算法先确立了需要传输的数据块不同的优先级。再利用带宽和信噪比的关系为该数据块分配合适的响应邻居节点。

图2给出了改进的BMesh－Pull数据分发算法的思想流程图。无线Mesh节点i开始第N 次数据请求，根据优先级调度算法，确定最需要在网络中传输的数据块a，完成数据块优先级的调度，再通过带宽和信噪比估计为该数据块a选择最合适的邻居节点j，完成数据分发的过程。

改进的BMesh－Pull算法考虑了传输时延和网络吞吐量的问题，建立了最优化选择机制。

图2 BMesh－Pull数据分发算法的思想流程

3 数据分发建模

如图3所示给出了一个数据分发的滑动窗口。在传输中，网络将要传输的数据内容分为许多个大小一样的数据块，每个数据块都会有一个编号。其中数据块c表示当前播放时刻，数据块d表示播放过错过了的数据，数据块a表示已经到达的数据，数据块b表示缺失的需要传输的数据块。从滑动窗口的示意图可以直观看到数据块的紧急程度。

图3 滑动窗口

数据分发建模前先定义了一些参数如表1所示，这些参数用于描述改进的BMesh－Pull数据分发算法。

表1 BMesh－Pull算法用到的描述参数

改进的数据分发算法的核心有两个部分，首先通过优先级调度算法选择最需要在网络中传输的数据块a，再通过带宽和信噪比估计为数据块a选择最合适的邻居节点j。

要确定节点i请求数据时最需要在网络中传输的数据块a，分别要从数据块的优先级以及数据块最少的提供者的数量这两方面对每个需要传输的数据块定义请求顺序的优先级［9］。在这里定义了一个优先级算法的公式

其中，Fia表示数据块a 对于节点i的优先级大小。0≤β≤1，β越大表示更需要考虑数据提供者的数量，β越小表示更需要考虑迫切需要数据块的程度。通过比较Fia的大小，就会得到一个需要在网络中传输的数据块的优先级顺序，按照这个优先级顺序再对邻居响应节点发送请求信息。

要为数据块a选择最合适的邻居节点j，分别从是带宽和信噪比的影响两个角度考虑。

（1）带宽W 的考虑：核心思想是考虑所有含有数据块a的邻居节点n，把邻居节点n在前p 个周期中发送给节点i的带宽信息数据作为前p 个周期的带宽估计，根据得到的信息选择第p＋1 个周期时与节点i传输带宽最大的邻居节点n。

令BWi［n］［p＋1］来表示第p＋1周期时节点i选择邻居节点n 进行数据传输时的带宽估计。用下面的公式表示在第p＋1周期时节点i对其邻居节点n 有效带宽估计

（2）信噪比SNR 影响的考虑：信噪比越高往往可以使得信号的传输更为快速有效［10］。信噪比也是会影响网络传输性能的重要因素。信噪比在网络中往往是不确定的，建模的时候把节点之间的信噪比大小控制在一定的范围之内选择随机的值，这样是比较符合实际的情况。

在这里定义了SNRMIN 表示信噪比SNR 的临界值，SNRAVR ［ikn］表示邻居节点n前m 个周期中与节点i 传输数据的信噪比平均值。基本思想是在第m＋1个周期时考虑节点i的SNRAVR ［ikn］，把SNRAVR ［ikn］的值与SNRMIN 进行比较来选择最合适邻居节点j。

判断的方式是首先考虑传输带宽最大的邻居节点A，若SNRAVR ［ikA］的值大于SNRMIN 则选择邻居节点A作为最合适邻居节点，若SNRAVR ［ikA］小于SNRMIN则继续考虑传输带宽第二大的邻居节点B，接着以此类推从而直到选择出满足信噪比要求中传输带宽最大的邻居节点作为最合适邻居节点j。

4 仿真实验和性能分析

采用了Matlab 软件来进行网络仿真分析。总共设定100个对等的节点来模拟无线mesh 网络中的mesh 节点，每一个节点其邻居节点个数设为10 个。初始带宽设定为10 MHz。初始信噪比范围由Matlab中的随机函数所产生，最小的值作为临界值SNRMIN。

4.1 节点的吞吐量

通过设定上述的仿真环境，编写仿真程序，图4 中显示了加入了最优化选择机制和没有加入最优化选择机制两种条件下，β节点平均吞吐量之间的关系。其中横轴表示影响因子β，纵轴表示节点平均吞吐量 （kbps）。定义节点的吞吐量为在网络中的单位时间里每个节点从其它节点获得的数据量。加入最优化选择机制指的采用改进的BMesh－Pull最优化算法，没有加入最优选择机制指的是采用现有的Mesh－Pull算法。

β是最优化选择的关键影响因子，在实验中分别选取了β＝0，0.4，0.6，0.9，1这几个值，来综合考虑β与吞吐量的关系。

图4 节点平均吞吐量和β的关系

图4中仿真结果可以看到，在加入最优化选择机制条件下，除了β＝0.4的时候，节点平均吞吐量对比没有加入最优选择机制条件下降了5.3%，但是其余的情况下节点平均吞吐量对比没有加入最优选择机制条件提高了5.2%－37.5%，说明了加入最优化选择机制提高了节点平均吞吐量。同时，在β＝0.6时，节点平均吞吐量达到最大，说明数据块的紧急程度和数据块的最少提供者数量这两种因素都是影响节点平均吞吐量的关键性因素，缺了任何一部分都会对节点平均吞吐量有很大的影响，与理论分析的结果相对应。

4.2 启动延时

无线Mesh网络系统性能的一个重要指标就是节点的启动延时，该指标特别会影响流媒体传输效率，关系到用户的切身体验。图5所示了10到24号节点与启动时延的关系。其中横轴表示节点编号的名称，纵轴表示各节点从开始请求数据时到传输完成的启动时延 （ms）。将节点启动时延定义为能够使流媒体文件中最开始数据块正常传输所需要的时间。

图5 相对应节点与启动时延的关系

图5仿真结果可以发现，在加入了最优化选择机制的条件下，选取的15个节点中有12个节点的启动延时相比没有加入最优选择机制条件都有1ms－5ms上的降低，只有3个节点启动延迟相比没有加入最优选择机制条件有所增加。这说明了加入了最优化选择机制可以降低网络的传输时延，这也是与理论分析的结果相对应的。

5 结束语

本文重点研究了现有Mesh－Pull的流媒体数据分发策略所存在的时延高和吞吐量低的问题，提出了一种改进的BMesh－Pull数据分发优化算法。该算法主要从吞吐量和传输时延这两个角度出发，选择了最符合无线mesh网络传输性能要求的两个节点完成数据传输过程，实现网络传输性能的改善。通过Matlab仿真可以发现，改进的BMesh－Pull数据分发算法是有效的。BMesh－Pull数据分发算法相比Mesh－Pull算法在节点平均吞吐量和节点启动延时两个方面的传输性能都有了改进。通过采用BMesh－Pull算法可以在保持Mesh－Pull算法基本优势的同时还能有效解决了时延和吞吐量问题，使得BMesh－Pull算法相比Mesh－Pull算法时延降低了1ms－5ms，同时吞吐量有了5.2%－37.5%的提升。综合可以表明，BMesh－Pull算法比Mesh－Pull分发算法在改善网络时延和吞吐量方面更为优越，可以实现提高网络吞吐量和降低网络数据传输时延的目的。

［1］SUN Zhixin，CHEN Yadang，REN Zhiguang.Data transmission strategy of P2Ppattern live video media streaming system［J］.Journal on Communications，2011，32 （6）：1－4 （in Chinese）.［孙知信，陈亚当，任志广.基于P2P流媒体直播系统的数据传输策略 ［J］.通信学报，2011，32 （6）：1－4.］

［2］LI Zhijie，FANG Xuming.Method of cross－layer scheduling in wireless mesh networks［J］.Journal of the China Railway Society，2012，34 （10）：61－64 （in Chinese）. ［李志杰，方旭明.无线Mesh网络中一种QoS保证的跨层调度方法 ［J］.铁道学报，2012，34 （10）：61－64.］

［3］CHEN Lerui，KONG Jinsheng.Research on network routing optimisation based on improved genetic algorithm ［J］.Computer Applications and Software，2013，30 （4）：135－137（in Chinese）.［陈乐瑞，孔金生.基于改进遗传算法的网络路由优化研究［J］.计算机应用与软件，2013，30 （4）：135－137.］

［4］SUN Shuang.Research on live scheduling algorithm in P2P media streaming based on Donet［D］.Qinghuangdao：Yanshan University，2010 （in Chinese）.［孙爽.基于Donet的P2P流媒体直播调度算法研究［D］.秦皇岛：燕山大学，2010.］

［5］ZHANG Hong.Strategy of distributing streaming media data in P2Pnetwork ［J］.Heilongjiang Science and Technology Information，2013 （22）：149 （in Chinese）.［张弘.P2P网络的流媒体数据分发策略浅析［J］.黑龙江科技信息，2013 （22）：149.］

［6］LIU Jiansheng，WEI Nanqing，YUE Guangxue，et al.Research on scheduling technologies of large－scale media streaming over peer－to－peer networks ［J］.Microelectronics ＆ Computer，2011，28 （8）：90－93 （in Chinese）.［刘建生，魏楠青，乐光学，等.P2P大规模流媒体调度技术研究 ［J］.微电子学与计算机，2011，28 （8）：90－93.］

［7］Zhang Baoxin，Mouftah HT.Destination－driven shortest path tree algorithms ［J］.Journal of High Speed Network，2006，15 （2）：123－130.

［8］LIU Tie，SHI Guomei，HUANG Qiuyuan，et al.An improved SNR estimation algorithm in OFDM ［J］.Microcomputer Applications，2013，2 （6）：29－32 （in Chinese）. ［刘铁，时国美，黄秋元，等.一种改进的OFDM 系统中信噪比估计算法 ［J］.网络新媒体技术，2013，2 （6）：29－32.］

［9］BAO Rongzhen，CAI Ming.Graph coloring－based scheduling algorithm for P2P media streaming ［J］.Journal of Computer Applications，2011，31 （1）：190－193 （in Chinese）. ［鲍 荣真，蔡明.基于图着色的P2P流媒体数据调度算法 ［J］.计算机应用，2011，31 （1）：190－193.］

［10］FENG Jianchun.Design and implementation of hf digital receiver with high SNR ［D］.Wuhan：Wuhan University of Technology，2010 （in Chinese）.［冯建春.高信噪比短波数字接收机的设计与实现 ［D］.武汉：武汉理工大学，2010.］

［11］CHEN Lerui，KONG Jinsheng.Research on network routing optimisation based on improved genetic algorithm ［J］.Computer Applications and Software，2013，30 （4）：135－137 （in Chinese）.［陈乐瑞，孔金生.基于改进遗传算法的网络路由优化研究［J］.计算机应用与软件，2013，30 （4）：135－137.］