谭国平，杨 阳，霍孝义，居美艳

（河海大学 计算机与信息学院 通信与信息系统研究所，江苏 南京211100）

0 引 言

网络编码的概念，使得网络能够达到最大流最小割定理所确定的最大理论容量，因而被广泛研究用于提高网络吞吐率、安全性、能量利用率［1－3］。文献 ［4］将网络编码技术添加到多播路由协议中，提出了基于部分网络编码［5］的实时多播协议PNCRM。本文运用多元回归分析对PNCRM 协议建模分析。

多元回归分析在预测方面的应用已经非常广泛。文献［6］提出基于稳健回归分析的实时多播协议性能预测方法，通过给定网络场景参数能够较好地预测协议性能，但其只选择了单个移动模型进行分析，且在网络仿真场景中各节点移动速度是随机的，无法准确描述节点移动速度对路由总开销的影响。本文针对文献 ［6］的不足选取随机路点、高斯马尔科夫和参考点组3种典型的移动模型对稳健回归分析的实时多播协议性能预测模型进行对比研究。通过对网络仿真场景中所有节点移动速度设为同一随机值，可以准确反映节点移动速度对路由总开销的影响，验证了该模型具有很好的预测性能。

1 移动模型

为了研究稳健回归分析的实时多播协议性能预测模型的预测效果，除了NS2中已有的随机路点移动模型，我们将高斯马尔科夫以及参考点组移动模型加入NS2中，对比预测模型在3种不同移动模型下的性能表现。

1.1 随机路点移动模型

随机路点移动模型［7］（rand waypoint mobility model，RWP）简单，易于实现，且应用广泛。在该模型中，节点首先在随机位置上选择一个随机目的地，以速度v朝着目的地移动，到达后停留一段时间Tpause，再以本次的目的地作为下次移动的起点，随机选择另一目的地，然后继续重复上述过程。其中，v∈［vmin，vmax］，服从均匀分布，vmin是节点最小移动速度，vmax是节点最大移动速度。Tpause∈［Tmin，Tmax］，服从均匀分布，Tmin、Tmax分别为节点最小暂停时间和最大暂停时间。

1.2 高斯马尔科夫移动模型

高斯马尔科夫移动模型［8］（Gauss－Markov mobility model，GM）中，节点在任意一个时刻的速度与先前一个时刻速度相关，因此节点的运动速度是平滑的，避免了速度或方向的突变行为。速度和方向计算公式如下

其中，vn和dn为节点在第n个时间间隔的速度和方向；α（α∈［0，1］）用来调节随机性；和表示当n→∞时速度和方向的平均值；vxn－1和dxn－1服从Gaussian分布。

在第n个时间间隔，节点的位置公式如下

其中，（xn，yn），（xn－1，yn－1）是节点在第n，n－1个时间间隔的坐标；vn－1，dn－1是节点在第n－1个时间间隔的速度和方向。

1.3 参考点组移动模型

参考点组移动模型［9］（reference point group mobility model，RPGM）是一种群组移动模型，在该模型中，每个组有一个称为参考点的逻辑中心，组逻辑中心的移动决定整组节点的移动。组内节点的移动是将组逻辑中心作为参考点，在其周围自由移动。假设同一组内的节点P、Q 在t1时刻的速度矢量公式为

上面描述的3种移动模型中，随机路点移动模型和高斯马尔科夫移动模型下各节点之间的移动是相互独立的，而参考点组移动模型节点以群组的模式移动，组内节点的移动并不是完全独立的，逻辑中心的移动决定本组节点的移动属性。通过加入3 种典型的移动模型，更好地反映PNCRM 协议的性能表现。

2 仿真数据及模型应用

2.1 PNCRM 仿真参数

为了获得PNCRM 性能预测模型的原始数据，通过设置不同的编码块长度、节点移动速度和接收节点个数取值来构造不同的网络场景并在NS2中进行仿真，然后对产生的追踪文件进行处理。

仿真场景见表1。

表1 PNCRM 仿真参数设置

2.2 预测模型构建

根据多元回归分析理论［10，11］，构建PNCRM 协议性能的预测模型，本文采用多项式函数作为各自变量与性能指标的关系类型

式中：P——协议性能；B——编码块长度；S——节点移动速度，每组仿真场景中所有节点的速度为同一随机值；N——节点个数；b0，b1，…，bp1＋p2＋p3是需要求解的回归系数，p1，p2，p3——各自变量的最高阶次，ε——随机误差项。

仿真实验中选取n组原始数据，n越大求得的回归方程系数越精确。回归方程的矩阵表示如下

实验过程中，为了全面评估PNCRM 协议的性能，选取了3个指标进行性能评估，分别是：

分组投递率 （packet delivery ratio）：它是接收节点收到的分组数与发送节点发送的分组数比值。分组投递率反映了路由协议的可靠性和正确性，特别是是在拓扑结构高度动态的移动自组网中，路由协议的可靠性至关重要，因此具有较高的分组投递率是设计移动自组网路由协议的一大准则。

总开销 （total overhead）：发送的控制分组数、数据分组数之和与接收到的数据分组数之比。它反映了路由协议的效率问题，由于移动自组网中无线带宽资源有限，因此路由协议的总开销越小越好。

端到端延时 （delay）：指分组从发送端到接收端所经历的时间。端到端延时直接影响通信服务质量和用户的满意度，对实时性业务影响更是如此。

本文选取总开销这一性能指标进行建模分析。运用极大似然估计的迭代加权最小二乘法对矩阵进行求解。

2.3 模型参数确定

因为多项式函数 （4）中各自变量的最高阶次未知，求解之前需要先确定P1，P2，P3的值。下面给出确定P3值的求解过程，P1，P2同理可得。

本文原始数据值个数n取150，NS2中仿真得到接收节点个数 （N）为5、10、15、25、35、45时与之对应的协议总开销 （TO） 平均值分别为4.883296、3.277822、2.399537、1.537478、1.125066、0.877239。将得到的数据导入Matlab的Cftool工具箱并选择多项式逼近，使用最小二乘拟合算法确定函数关系式。通过残差平方和、调整的判定系数和均方根误差3个指标作为判定拟合效果的标准。拟合效果如图1所示，得到TO 函数关系式

由式 （9）可知P3值为3，同理P1、P2值分别为3、3。所以TO 预测模型为

图1 协议总开销与接收节点个数的拟合效果

2.4 模型求解及检验

最小二乘估计是常用的求解回归系数的方法，在一切无偏估计类中，具有最小的方差。但是，当实际观测值中出现异常值时，随机误差项将不再服从正态分布，而是重尾分布，此时用最小二乘法求解回归系数是不准确的。采用极大似然估计 （M－估计）［12］的稳健回归分析能够有效地解决最小二乘法的不足，稳健回归在识别异常值方面具有显著的优越性。

在极大似然估计中，通过最小化一个关于残差的目标函数ρ对回归系数β进行求解，即

通过比较发现最小二乘法的目标函数就是

令ψ＝ρ′为目标函数关于回归系数β的导数，在稳健回归中称之为影响函数。为了求目标函数的最小值，令目标函数的导数为0 即可求得，则对上式求关于回归系数β的导数得

由以上分析可知权重由残差求得，残差由回归系数求得，而回归系数的求解又与权重有关，所以式 （14）的求解需要用迭代法，此过程称为迭代加权最小二乘法 （iteratively reweighted least－squares，IRLS）。

目标函数为Bisquare函数，其形式如下

求导得其权重函数为

其中，k为调和常数，为了能够提供95%的有效性且排除异常值的干扰，常取k ＝4.685σ，σ为残差的标准差，在实际应用中需用估计量代替。

根据式 （10）构建的预测模型，借助Matlab编程使用极大似然估计的迭代加权最小二乘法求解，得到表2。

采用多元回归模型的两种检验方法：①方程显著性检验，即F检验值反映回归模型效果的显著性。由F 分布表得F10，139（0.01）＝2.5365，表2 中F 检验值428.09382.5365，所以认为此回归模型高度显著。②变量显著性检验，即t检验值反映某个自变量对预测变量影响的显著性。由t分布表得t0.025（140）＝1.9771，所以表2中由t检验值可以删除B2、B3、S、S2和S3。

表2 TO 预测模型求解值

对式 （10）进行删除项处理，得到新的预测模型，运用Matlab编程求解，得到表3。

表3 重构后TO 预测模型求解值

由F分布表得F4，145（0.01）＝3.4512，表3中F检验值935.1099＞＞3.4512，认为此回归模型高度显著。由t分布表得t0.025（145）＝1.9765，所以表3中t检验值均满足显著性要求。因此，得到

同理，求得随机路点移动模型下预测模型为

参考点组移动模型下预测模型为

3 预测模型分析

运用多元回归分析构建PNCRM 性能预测模型的最终目的是预测PNCRM 在不同场景参数下的性能表现。为了检验所构建PNCRM 性能预测模型的预测效果，本文通过修改仿真参数选取不同于构建性能预测模型时自变量的取值来获得总开销 （TO）的观测值，对比其与通过所构建性能预测模型得到的预测值的差值，并计算其平均相对误差来衡量其预测效果，各自变量的取值及其它场景参数设置见表4。

表4 PNCRM预测模型检验仿真参数设置

通过改变节点移动速度和接收节点个数的取值组合产生不同的仿真场景，同样地，每个场景仿真多次取其平均值作为此场景下性能的最终值，其它参数与表1 的设置相同。

本文利用RWP、GM、RPGM 这3种移动模型，检验所构建的PNCRM 性能预测模型的预测效果。图2、图3、图4分别描述了3种移动模型的应用效果。

图2 随机路点移动模型的TO 预测模型应用

图3 高斯马尔科夫移动模型的TO 预测模型应用

图4 参考点组移动模型的TO 预测模型应用

图2、图3、图4 中各有3 条曲线，数据点标记符中，方块是观测值曲线，三角是预测值曲线，星号是残差值曲线。

4 结 论

由3组预测模型应用图可以发现，3种移动模型下TO预测模型的观测值曲线与预测值曲线基本吻合，计算得其平均相对误差分别为8.56%、9.27%、4.03%。比较可知，参考点组移动模型的TO 预测模型的误差变化范围明显小于其它两种移动模型，这是因为参考点组移动模型下的总开销比其它两种小得多，使得取值范围较小，进而误差值也相对较小。图中同样可以发现，高斯马尔科夫移动模型下TO 预测模型的残差值大部分为正值，而不是在0 值附近上下波动，且具有最大的平均相对误差，这是在以后的研究中需要改进的地方。同时，我们可以发现TO 预测模型的平均相对误差比较大，这是主要因为构建TO 预测模型所使用原始数据中的TO 值在1 至6 之间，变化范围较大。总体说来，所构建的预测模型能较准确地预测PNCRM 的TO 性能。

5 结束语

本文选取随机路点移动模型、高斯马尔科夫移动模型、参考点组移动模型分析PNCRM 性能预测模型的预测效果。预测模型在3种移动模型下所做预测的值与观测值的平均相对误差分别仅为8.56%、9.27%、4.03%，具有很好的预测效果。因预测模型中仅研究了编码块长度、节点移动速度、接收节点个数对预测性能影响，忽略了如编码包缓冲区长度，接收节点密度等其它因素的影响。未来的工作中一方面需要考虑这些因素对PNCRM 性能的影响，另一方面应该进一步探索对预测模型的简化处理，构建更加精确的预测模型。

［1］Zhang Z.Theory and applications of network error correction coding ［C］／／Proceedings of the IEEE，2011：406－420.

［2］Wang S，Vasilakos A，Jiang H，et al.Energy efficient broadcasting using network coding aware protocol in wireless ad hoc network ［C］／／Proc IEEE ICC，2011.

［3］Paramanathan A，Heide J，Pahlavani P，et al.Energy and data throughput for asymmetric intersession network coding［C］／／IEEE 17th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks，2012：358－363.

［4］TAN Guoping，PENG Xinhua，NI Xinyang，et al.Research on partial network coding based real－time multicast protocols in mobile Ad－Hoc networks ［J］.Microelectronics＆Computer，2012，29 （9）：39－41 （in Chinese）.［谭国平，彭新华，倪新洋，等.基于部分网络编码的移动自组网实时多播协议研究［J］.微电子学与计算机，2012，29 （9）：39－41.］

［5］Guo Bin，Chang Peiqiang，Lin Yu，et al.A practical network coding scheme over GF （2q）for multi－user cooperative communication ［C］／／IEEE Globecom，2011：1－5.

［6］TAN Guoping，HUO Xiaoyi，TAN Linfeng，et al.A method to predict the performance of wireless real－time multicast protocol based on robust regression analysis ［J］.Journal of Hohai University （Natural Sciences），2013，41 （6）：554－559 （in Chinese）.［谭国平，霍孝义，谭林风，等.基于稳健回归分析的实时多播协议性能预测方法 ［J］.河海大学学报 （自然科学版），2013，41 （6）：554－559.］

［7］Simaremare H，Syarif A，Abouaissa A，et al.Energy Consumption analysis of modified AODV routing protocol under random waypoint and reference point group mobility models［C］／／International Conference on Advanced Computer Science and Information Systems，2012：28－29.

［8］Rohrer JP，Cetinkaya EK，Narra H，et al.AeroRP performance in highly－dynamic airborne networks using 3D Gauss－Markov mobility model［C］／／Proceedings of Military Communications Conference.IEEE，2011：834－841.

［9］Amjad K.Performance analysis of DSR protocol under the influence of RPGM model in mobile AD－HOC networks ［C］／／31st International Conference on Distributed Computing Systems Workshops.IEEE，2011：100－104.

［10］Mohammad H Mokhtari，Ibrahim Busu，Hossein Mokhtari，et al.Neural network and multiple linear regression for estimating surface albedo from ASTER visible and near－infrared spectral bands［J］.Earth Interact，2013，17 （3）：1－20.

［11］Seal Victor，Raha Arnab，Maity Shovan，et al.A real time multivariate robust regression based flood prediction model using polynomial approximation for wireless sensor network based flood forecasting systems［C］／／Advances in Computer Science and Information Technology，2012：432－441.

［12］Yao Lili，Song Xiangdong.Variable bandwidth M－estimators of the partial linear regression models ［C］／／International Conference on Multimedia Technology，2011：2793－2796.